在 C 中对链表进行排序时的无限循环

Question

我是C编程的新手，我必须对我的链表进行排序。该链表表示已由用户输入创建的多项式。每个节点都有一个系数和一个幂。当我尝试对列表进行排序并将其 return 到打印它的主函数时，没有打印任何内容（我认为我的程序永远不会退出 while 循环）。

这里我创建了结构：

struct node
{
    int sunt;
    int dun;
    struct node* next;
};
typedef struct node* Poly;

这是我对列表进行排序的代码（head 是我的初始列表名称）：

struct node* poly = head;

struct node* temp;
int length = 0;

while (poly != NULL)
{
    length++;
    poly = poly->next;
}

poly = head;

while (length > 0)
{
    int i = 0;
    while ((poly != NULL) && (poly->next != NULL))
    {
        if (poly->dun > poly->next->dun)
        {
            temp = poly;
            poly = poly->next;
            poly->next = temp;
            if(i = 0)
            {
                head = poly;
            }
            i ++;
        }
        else
        {
            if(i = 0)
            {
                head = poly;
            }
            i ++;
        }
        poly = poly->next;
    }
    length --;
    poly = head;
}
return head;

这里是我在 main 函数中打印列表的地方（POLYmake 函数是我创建和排序列表的地方）：

poly1 = POLYmake();

while(poly1 != NULL)
{
    printf("%d %d \n", poly1->sunt, poly1->dun);
    poly1 = poly1->next;
}

我知道这很复杂，但我对C没有经验，希望你能帮助我。

Answer 1

这个循环

while(length > 0)

永远是真的，因为当你完成你的列表时，你只会将它减一。

另外，代码如下：

if(i = 0)
{
    head = poly;
}

应该是

if(i == 0)
{
    head = poly;
}

Answer 2

首先...

if(i=0)

是错误的，因为它设置了 i

虽然我认为还有更多...您将下一个节点 -> 下一个设置为当前节点，反之亦然，但是，您没有设置前一个节点 -> 下一个或下一个节点的 - >next 也是如此，因此您很可能会创建一个循环，即 next 两个都包含相同的指针。您需要绑定列表中的所有链接才能执行此操作，这很痛苦！

所以应该是：

node* prev = null

[...] ensure you set the prev after each iteration

then
node* swap1 = poly;
node* swap2 = poly->next;

swap1->next = swap2->next; (which you'd have to null check for beforehand)
swap2->next = swap1;
prev->next = swap2;

但是：从概念上讲，您交换整个链接只是为了交换一些数字。您可以在链表条目中嵌入一个结构指针（其中包含您感兴趣的 ACTUAL 值），然后交换它们而不是动态重组您的列表本身。

故事的寓意是，链表不是冒泡排序的最佳结构。

Answer 3

我认为你打破了你的链表并在内部循环的第一个 if 分支中形成了一个循环

temp = poly; // (1) 
poly = poly->next; // (2)
poly->next = temp; // (3)

假设您有一个列表 a -> b -> c -> ... 并输入 if then poly points to a so will temp after (1)。在 (2) 之后 poly 将指向 b。 (3) 语句然后将 b 的下一个指针赋值给 temp，即 a。这导致循环 a -> b -> a -> b -> ... 并且你永远不会到达 c 并因此永远停留在循环中。如果交换 a 和 b，则应将 a 的下一个指针设置为 c。

编辑：此外，还必须更新前一个节点（其下一个指针指向多边形）。为此，前一个节点可以保存在单独的 prev 指针中，并且 prev->next 可以设置为交换后两个节点中第一个的那个节点。

Answer 4

让我们关注这个

temp = poly;
poly = poly->next;
poly->next = temp;

大概的想法是交换列表中的两个元素。那么让我们来看一个列表

item1 -> item2 -> item3 -> item4 -> NULL

假设item2的poly点需要和item3交换。您要做的第一件事是将 temp 设置为 poly，因此 temp 和 poly 都指向 item2。

item1 -> item2 -> item3 -> item4 -> NULL
         poly
         temp

然后你移动 poly 指向 poly->next 也就是 item3

item1 -> item2 -> item3 -> item4 -> NULL
                  poly
         temp

然后将 poly 的 next 指针设置为指向 item2

的 temp

             V------------
item1 -> item2 -> item3 -|  item4 -> NULL
                  poly
         temp

请注意，现在没有任何内容指向 item4。这是内存泄漏。另请注意，您的列表以循环结尾，这意味着您永远不会遇到 NULL，也永远不会退出内部循环。

如何解决？

您会注意到 poly 之前的项目也需要更改其 next 指针，因此您将需要一个 previous 指针。我就是这样做的

// Set up the loop before you start
struct node* previous = NULL;
poly = head;
while (poly != NULL && poly->next != NULL)
{
    if (poly->dun > poly->next->dun)
    {
        if (previous == NULL)
        {
            head = poly->next;
        }
        else
        {
            previous->next = poly->next;
        }
        struct node* tail = poly->next->next;
        poly->next->next = poly;
        poly->next = tail;
    }
    previous = poly;
    poly = poly->next;
}

我认为这行得通。还没有测试过。

Answer 5

用实际代码展示了一个简单的算法。

typedef struct node Node;
Node *bubbleSort(Node *head){
    if(head == NULL || head->next == NULL)//no need sort
        return head;

    Node anchor = { 0, 0, head }, *sentinel = NULL;
    while(1){
        Node *prev = &anchor, *curr = prev->next, *next = curr->next;
        if(next == sentinel)
            break;
        while(next != sentinel){
            Node *rest = next->next;
        //  prev --> curr --> next --> rest
            if(curr->dun > next->dun){
                prev->next = next;
                next->next = curr;
                curr->next = rest;

                prev = next;
                //curr = curr;
                next = curr->next;
            } else {
                prev = curr;
                curr = curr->next;
                next = curr->next;
            }
        }
        sentinel = curr;
    }

    return anchor.next;
}

在 C 中对链表进行排序时的无限循环

Infinite loop while sorting a linked list in C

c

sorting

linked-list