gpt4 book ai didi

c - 了解链表排序

转载 作者:行者123 更新时间:2023-11-30 19:04:37 26 4
gpt4 key购买 nike

我无法理解这段代码如何对链表进行排序。

node* sort(node *head) {
struct node* point;
struct node* small;
struct node* stay;
int temp;
stay = head;

while (stay != NULL) {
point = stay->next;
small = stay;
while (point != NULL) {
if (point->data < small->data) {
small = point;
}
point = point->next;
}
temp = stay->data;
stay->data = small->data;
small->data = temp;
stay = stay->next;
}
return head;
}

我试图在纸上遵循它,我的思考过程让我相信,如果我们要运行这个函数,列表将像这样排序:

5 -> 2 -> 1 -> 3  
2 -> 5 -> 1 -> 3
2 -> 1 -> 5 -> 3
2 -> 1 -> 3 -> 5

我的理解是,第一个while循环每次都会遍历列表,直到到达最后一个节点,而第二个while循环则比较两个节点pointsmall。如果需要切换数据,下一段代码实际上会进行切换,然后stay移动到列表中的下一个节点,point就是该节点在那之后。代码如何知道返回到第一个节点并继续比较,以便 2 与 1 交换?感谢您的帮助。

最佳答案

这段代码实现了选择排序:从stay(small ==stay)开始,搜索后面的最小值,并一旦找到(即到达列表末尾)交换。

请注意,如果 stay 是最小的,它会与自身交换(您可以通过之前进行适当的测试来防止这种情况:if(small !=stay) {/* swap */}.

实际上,您的排序步骤如下:

5 -> 2 -> 1 -> 31 -> 2 -> 5 -> 31 -> 2 -> 5 -> 3 (second node swapped with itself)1 -> 2 -> 3 -> 51 -> 2 -> 3 -> 5 (fourth node swapped with itself)

实际上,还有一步,因为最后一个节点总是与其自身交换(while(stay != NULL) 仅在最后最后一个节点之后停止)。

第一个节点从一开始就被正确处理(在外循环的第一次运行中),因为 stay 最初设置为 head

关于c - 了解链表排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51681672/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com