链接列表泡泡排序的麻烦

Question

我是一个初学者，学习使泡沫排序与链接列表一起工作。我看到了一个geeksforgeeks页面，谈论了这一点（），并适应了我的情况。我已经获得了适当工作的代码，但是我很难了解逻辑在此分类中的工作原理。为了理解“头”作为基点，它总是指示第一个节点。但是据我所知，头指针应始终与节点一起移动（如果节点A和B交换，并且头指向A，那么即使在交换后，头也会继续指向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

有人可以帮助我了解此代码中发生的情况吗？

Answer 1

我的理解“头”充当基点，它总是指示第一个节点。

是的，但是不要将此 head 变量与另一个变量， h 变量混淆，该变量并非始终在第一个节点处（间接）点。

另请注意，当 h =＆amp;（*h） - ＆gt; Next; 被执行， h 和 head 不再是相同的指针，*H 不再是第一个节点列表。然后， H 已成为下一个指针的地址，该节点是在下一个迭代中由 p1 引用的节点之前的。

据我所知

这就是为什么> *h = p2 已执行，因此*h 可以保证指向具有较小值的节点，并且不遵守交换之前的节点。这成为 block 块之后的不变性：是否执行该块，*h 是指比较中使用的另一个节点背后的节点，他们处于正确的顺序。