c++ - 在c中的链表中找到最小的两个节点

Question

我试图在 C++ 中的链表中找到最小的两个数字(不使用任何内置函数)。

我尝试这样做如下:

我的逻辑是:

(1) 假设链表中的第一个节点是minimum1，第二个节点是minimum2。比较一下。较大的变为minimum2，较小的变为minimum1。

(2) 从第三个节点开始(第三个因为我们已经覆盖了第一和第二个)在一个while循环中直到我们到达NULL，从而遍历所有列表。

(3) 将新遍历的节点与minimum1和minimum2进行比较。如果此节点小于 minimum1，则将其值放入 minimum1。 minimum2 现在将包含 minimum1 的值，minimum1 将包含新找到的小于 minumum1< 的节点的值.

下面是我的代码，它获取要创建的节点数，连续读取所有节点的值(只需在每个数字后继续按 Enter)，并从所有节点创建链表节点。这些工作正常。

代码

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>

struct node
{
    int freq;
    struct node* next;
};
typedef struct node node;
node* tree;

// Finding minimum two elements:
void find_two_min(node** List, node** lmin1, node** lmin2)
{
    int i;
    node* temp = *List;
    node *min1, *min2;
    node* var1 = *List;
    node* second = (*List)->next;
    if (var1 > second)
    {
        min2 = var1;
        min1 = second;
    }
    else
    {
        min1 = var1;
        min2 = second;
    }
    while (temp->next->next->next != NULL)
    {
        if (temp->freq < min2->freq)
        {
            min1 = min2;
            min2 = temp;
        }
        else if (temp->freq < min1->freq)
        {
            min1 = temp;
        }
        temp = temp->next;
    }
    *lmin1 = min1;
    *lmin2 = min2;
}

void main()
{
    int size, data;
    node *min1, *min2;
    int count = 0; // This flag is to check whether it's the first node inside the do-while loop.
    tree = NULL;
    printf("Enter the number of nodes:\n");
    scanf("%d", &size);
    printf("Enter the elements:\n");
    node* prev;
    do
    {
        scanf("%d", &data);
        if (count == 0)
        {
            node* temp;
            temp = (node*) malloc(sizeof(node));
            temp->freq = data;
            temp->next = NULL;
            prev = temp;
            tree = prev;
        }
        else
        {
            node* temp;
            temp = (node*) malloc(sizeof(node));
            temp->freq = data;
            temp->next = NULL;
            prev->next = temp;
            prev = prev->next;
        }
        --size;
        ++count;
    }
    while (size > 0);

    printf("Printing linked list:\n");
    node* temp1;
    temp1 = tree;
    while (temp1 != NULL)
    {
        printf("%d, ", temp1->freq);
        temp1 = temp1->next;
    }
    node* temp5 = tree;
    find_two_min(&temp5, &min1, &min2);
    printf("\nThe two minimum numbers are min1: %d and min2: %d.\n", min1->freq, min2->freq);
}

我的代码不适用于以下输入(它给出了错误的输出):

Enter the number of nodes:
4
Enter the elements:
0
-5
-2
8
Printing linked list:
0, -5, -2, 8,
The two minimum numbers are min1: 0 and min2: -5.

它应该打印“min1: -5”和“min2: -2”，但我不知道为什么不打印。

谁能帮我解决这个问题？任何用作引用的 C/C++ 算法或代码段都值得赞赏。谢谢。

注意:我不能使用任何内置函数。

Answer 1

如果试图同时做两件事让你感到困惑，

then do only 1 thing,

然后，通过另一项独特的努力来遵循这一点。

即

1st - 编写 search1() 以找到最小的项目并记录节点指针。

第二 - 编写 search2() 来查找最小的项目，但将节点地址与先前找到的最小节点进行比较的想法添加到您的 search2 中。当已经找到时，跳过它，就好像根本不存在一样。

---

实现 search1，调试它，使其正常工作。

---

之后

实现search2，(可能是一个拷贝)并传入在search1中找到的节点指针。每次找到 search2 的最小节点的可能更新时，插入一个测试以确定这个节点是否匹配之前找到的