我创建了一个由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循环来纠正此问题，但是在大多数情况下，这会导致段错误。当然，这里的另一件事是我的逻辑可能是完全错误的，并且可能有一种更好的方法来实现此目的。您能只交换节点的内容而不交换指针本身就摆脱困境吗？任何帮助将非常感激。提前致谢
用于排序数组的普通气泡排序实现利用了直接寻址和数组的已知大小：它们自然使用索引（即项目的序数），因此它们可以轻松地随着工作的进行而缩小排序的区域，因为他们知道最终项目中已经有多少个项目了。
链表是纯粹按顺序处理的，因此，如果不添加人工“索引”（沿表迭代递增），就不允许进行这种简单的优化。这就是为什么最简单的方法是始终遍历整个列表并在没有更多项目交换时终止，因此对列表进行了排序是最简单的：
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使整个代码更简单，更短并且也更快。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句