我是一名初学者，正在学习使 bubble sort 与链表一起工作。我看到一个 geeksforgeeks 页面谈论这个（https://www.geeksforgeeks.org/bubble-sort-for-linked-list-by-swapping-nodes/），并适应了我的情况.我已经让代码正常工作，但我无法理解这种排序中的逻辑是如何工作的。据我了解，“头”充当基点，它始终表示第一个节点。但是据我所知，head 指针应该始终与节点一起移动（如果节点 a 和 b 交换，并且 head 指向 a，那么即使在交换之后，head 也会继续指向 a），这似乎与第一条语句相矛盾。
这是我的代码：
typedef struct Node{
int Nid;
char Nname[9];
int Ngrades;
struct Node *next;
}NODE;
int bubbleSortID(NODE** head, int count){
NODE** h;
NODE* temp;
for (int i = 0; i <= count; i++) {
h = head;
for (int j = 0; j < count-1; j++) {
NODE* p1 = *h;
NODE* p2 = p1->next;
if (p1->Nid > p2->Nid) {
temp = p2->next;
p2->next = p1;
p1->next = temp;
*h = p2;
}
h = &(*h) -> next;
}
}
}
void getID(NODE *head){ //used to print result
while (head != NULL){
printf("%d %s %d \n", head->Nid, head->Nname, head->Ngrades);
head = head->next;
}
}
given input:
10355112 jack 80
10311103 tom 85
10355107 zenry 70
10355014 tim 95
10355123 mary 85
11355123 helloo 1000
expected output:
10311103 tom 85
10355014 tim 95
10355107 zenry 70
10355112 jack 80
10355123 mary 85
11355123 helloo 1000有人可以帮我理解这段代码发生了什么吗？
回答1
据我了解，“头”作为基点，它始终表示第一个节点。
是的，但不要将此 head 变量与另一个变量 h 混淆，后者并不总是（间接）指向第一个节点。
还要注意当h = &(*h) -> next;被执行时，h和head不再是同一个指针，*h也不再是链表的第一个节点。 h 已成为该节点的 next 指针的地址，该节点在下一次迭代中将被 p1 引用的节点之前。
据我所知，head 指针应该始终与节点一起移动（如果节点 a 和 b 交换，并且 head 指向 a，那么即使在交换之后，head 也会继续指向 a），
没错，这就是执行 *h = p2 的原因，以便保证 *h 指向具有较小 value 的节点，并且不会坚持交换之前的状态。这成为 if 块之后的不变量：无论该块是否被执行， *h 指的是在比较中使用的另一个节点后面的节点，并且它们的顺序正确。