用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 nextn");
        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 exitedn");
        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

但是，在将当前指针重新设置为3并紧挨着2之后，下一次运行提供了以下内容:

2 1 0 4 3

最后，我们以 结束

0 4 3 2 1 

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

Answer 1

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

链表是完全按顺序处理的，所以如果不添加人工的"索引"(index)，沿着列表迭代递增，就不允许这种简单的优化。这就是为什么总是遍历整个列表并在没有交换项时终止是最简单的，因此列表是排序的:

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变量指向一个指针，该指针指向当前节点。当'current'和'next'节点需要交换时，'previous'链接不应该再指向'current'节点，而是指向'next'节点。当然，可以将指针保留到"前一个节点"并为(previous node)->link分配一个新值-但这在列表中的第一个节点的情况下不起作用，该列表没有"前一个节点"，但由head变量指向。必须使用附加条件来验证当前节点是否是解决此不一致的第一个节点。有一个指针指向指针，最初指向head，然后指向'previous node'.link，使整个代码更简单，更短，也更快一点。

Answer 2

我会看第三个while

    while(next != NULL)
    {
      prev->link = next; 
      cur->link = next->link;
      next->link = cur;
      prev = next;
      next = cur->link;
    }

在这里你总是移动元素而不测试它们是否必须移动-例如cur->i > next->i .

顺便说一下，如果它的保护为真，第二个while只执行一次，所以它和if是一样的，所以我将使用if，至少为了清晰的原因。