c - 冒泡排序 C 中的链表

Question

我创建了一个包含 5 个节点的链表:

typedef struct node
{
    int i;
    struct node* link;
}node;

node* head = NULL;

当打印出来时，这给出:

4 3 2 1 0

头指针设置为指向 4。然后我编写了一个函数来对链表进行冒泡排序，如下所示:

void sort(void)
{
     node* cur = head;
     node* next = cur->link;
     node* prev = NULL;

     while(cur->i > next->i)
     {
        printf("cur is greater than next\n");

        while(prev != head)
        {
          cur->link = next->link;
          next->link = cur;
          head = next;
          next = cur->link;
          prev = head;
        }
        while(next != NULL)
        {
          prev->link = next; 
          cur->link = next->link;
          next->link = cur;
          prev = next;
          next = cur->link;
        }
        printf("second while loop exited\n");

        for (node* ptr = head; ptr != NULL; ptr = ptr->link)
        {
           printf("%d", ptr->i);
        }

        cur = head;
        next = cur->link;

      } 
}

有多种 printf 语句可以检查程序是否正常运行。我发现第一次跑通后，4成功冒泡如下:

3 2 1 0 4

但是，在将 cur 指针重新设置为 3 和 2 之后，下一个运行提供以下内容:

2 1 0 4 3

最终，我们完成了

0 4 3 2 1 

因此可以看出“3”、“2”和“1”被夸大了。我尝试了各种条件来代替第三个 while 循环来纠正这个问题，但在大多数情况下，这会导致段错误。当然，这里的另一件事是我的逻辑可能完全错误，可能有更好的方法来实现它。你可以只交换节点的内容而不交换指针本身吗？任何帮助将非常感激。提前致谢

Answer 1

用于排序数组的普通冒泡排序实现利用直接寻址和数组的已知大小:它们自然使用索引，即项目的序数，因此它们可以随着工作的进行轻松缩小排序的区域，因为他们知道有多少元素已经在他们的最终位置。

链表是完全按顺序处理的，因此它不允许在不添加人工“索引”的情况下进行这种简单的优化，沿着列表迭代递增。这就是为什么总是遍历整个列表并在没有更多项目被交换时终止是最简单的原因，因此列表已排序:

void sort(void)
{
    int swapped = 1;

    while(swapped)
    {
        node **prev = &head, *curr, *next;

        swapped = 0;
        for(curr = head; curr; prev = & curr->link, curr = curr->link)
        {
            next = curr->link;

            if(next && curr->i > next->i)
            {
                curr->link = next->link;
                next->link = curr;
                *prev = next;

                swapped = 1;
            }
        }
    }
}

编辑 – 一些解释，以回答 Matthew2015 评论中的问题。

C 中的逻辑条件需要一个数值或指针表达式，如果它们分别不为零或不为 NULL，则它们被视为“真”。这意味着 while(swapped)本质上等同于 while(swapped != 0)和 next && ...相当于next != NULL && ... . while(swapped != 0)中的情况意味着循环将在执行内部 for 时终止。不设置 swapped至 1 ，当列表中没有任何项大于其后继项时会发生这种情况 - 也就是说，当列表已排序时。

for循环条件表达式为curr单独，相当于 curr != NULL .这使得 for沿着列表循环迭代，直到没有“当前”节点。

node **prev变量指向一个指针，该指针指向当前节点。当“当前”和“下一个”节点需要交换时，“上一个”链接不应再指向“当前”节点，而是指向“下一个”节点。当然，可以保留指向“前一个节点”的指针并为 (previous node)->link 分配一个新值。 — 但如果列表中的第一个节点没有“前一个节点”但被 head 指向，那将不起作用多变的。必须使用附加条件来验证当前节点是否是解决此不一致的第一个节点。有一个指向指针的指针，它最初指向 head然后到'previous node'.link使整个代码更简单、更短，也更快一些。