冒泡排序 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 语句可以检查程序是否正常运行。我发现在第一个运行-through之后，4成功冒泡如下：

3 2 1 0 4

然而，在将 cur 指针重新设置为 3 和 next 到 2 之后，下一个运行-through 提供以下内容：

2 1 0 4 3

最终，我们以

结束

0 4 3 2 1

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

Answer 1

我会看第三个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，在至少出于清楚的原因。

Answer 2

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

linked 列表纯粹按顺序处理，因此如果不添加人工 '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，则它们被视为 'true'。这意味着 while(swapped) 本质上等同于 while(swapped != 0)，而 next && ... 等同于 next != NULL && ...。 while(swapped != 0) 中的条件意味着当内部 for 的某些执行没有将 swapped 设置为 1 时循环将终止，这发生在列表中没有项目大于其后继者——即当列表被排序时。

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

node **prev变量指向一个指针，指针指向当前节点。当 'current' 和 'next' 节点需要交换时，'previous' link 不应再指向 'current' 节点，而是指向 'next' 节点代替。当然，人们可能会保留指向 'previous node' 的指针，并为 (previous node)->link 分配一个新值——但这在列表中的第一个节点没有 'previous node' 的情况下是行不通的但由 head 变量指向。必须使用附加条件来验证当前节点是否是解决此不一致的第一个节点。有一个指向指针的指针，它最初指向 head 然后指向 'previous node'.link 使整个代码更简单、更短，也更快。

冒泡排序 C 中的链表

Bubble sorting a linked list in C

c

sorting

linked-list