c - 了解在 C 中使用双指针创建单向链表的代码

Question

我试图理解下面用于创建单向链表的代码如何使用双指针工作。

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

void push(struct Node** headRef, int data) {

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;   
    newNode->next = *headRef;
    *headRef = newNode;
}

//Function to implement linked list from a given set of keys using local references
struct Node* constructList(int keys[], int n) {
    struct Node *head = NULL; 
    struct Node **lastPtrRef = &head; 
    int i, j;
    for(i = 0; i < n; i++) {
        push(lastPtrRef, keys[i]);
        lastPtrRef = &((*lastPtrRef)->next); //this line
        if((*lastPtrRef) == NULL) {
            printf("YES\n");
        }
    }

    return head;
}

int main() {
    int keys[] = {1, 2, 3, 4};
    int n = sizeof(keys)/sizeof(keys[0]);

    //points to the head node of the linked list
    struct Node* head = NULL;

    head = constructList(keys, n); //construct the linked list

    struct Node *temp = head;

    while(temp != NULL) { //print the linked list
        printf(" %d -> ", temp->data);
        temp = temp->next;
    }
}

我理解在函数 push() 中使用双指针的目的，它允许您在函数内部更改指针 headRef 指向的内容。但是在函数 constructList() 中，我不明白下面这行是如何工作的:

lastPtrRef = &((*lastPtrRef)->next);

最初 lastPtrRef 将指向指向 NULL 的 head。在第一次调用 push() 时，在 constructList() 的 for 循环中，head 指向的值发生了变化(它指向包含值 1 的新节点)。因此，在第一次调用 push() 之后，lastPtrRef 将指向 head，head 指向值为 1 的节点。但是，之后将执行以下行:

lastPtrRef = &((*lastPtrRef)->下一个);

由此，lastPtrRef 被赋予新添加节点的下一个成员所指向的地址。在这种情况下，head->next 为 NULL。

我不太确定在调用 push() 之后更改 lastPtrRef 的目的是什么。如果你想建立一个链表，你不希望 lastPtrRef 有指向包含 1 的节点的指针的地址，因为你想将下一个节点(将包含 2)推到列表的头部(这是 1)？

在 constructList 的 for 循环中对 push() 的第二次调用中，我们传递了指向 head->next (NULL) 和值 2 的 lastPtrRef。在 push() 中创建了新节点，包含值 2，newNode->next 指向 head->next，它是 NULL。 push 中的 headRef 被更改为指向 newNode(其中包含 2)。

也许我对代码的理解有误，但似乎通过更改 lastPtrRef 指向的内容，包含 1 的节点被忽略了。如果我们更改 lastPtrRef 持有的地址，我看不到链表是如何创建的。

如果您对这段代码的工作原理有任何见解，我将不胜感激。谢谢。

Answer 1

这使用了一种称为前向链接的技术，我相信您已经理解了这一点(使用指针到指针来前向链接链表构造)。

push 这个简单的事实让这个实现变得困惑函数似乎被设计为将项目填充到列表的头部，但在本示例中，它将它们填充到列表的尾部。那么它是如何做到的呢？

需要理解的重要部分是 push 中这个看似微不足道的小声明。 :

newNode->next = *headRef

这可能看起来不重要，但我向你保证它很重要。函数push ，在这种情况下，严重不公平地对待这个功能的真正作用。实际上它更像是一个通用的 insert .关于该功能的一些事实

• 它接受一个指向指针的指针 headRef作为参数，以及一些数据放入被管理的链表中。
• 分配一个新节点并在其中保存数据后，它设置新节点的next。指向当前存储在取消引用 中的任何值的指针 headRef pointer-to-pointer(所以..一个指针)这就是我上面提到的行所完成的。
• 然后它将新节点的地址存储在它刚刚从中提取先前地址的同一位置；即 *headRef
• 有趣的是，它没有返回值(它是 void )，这进一步让人有些困惑。事实证明它不需要。

返回调用者时，起初似乎没有任何变化。 lastPtrRef仍然指向某个指针(实际上是与以前相同的指针；它必须，因为它是按值传递给函数的)。但是现在那个指针指向刚刚分配的新节点。此外，该新节点的 next指针指向 *lastPtrRef 中的任何在函数调用之前(即函数调用之前 lastPtrRef 指向的指针中的任何值是)。

这很重要。这就是那行代码强制执行的内容，这意味着如果您使用 lastPtrRef 调用它寻址指向 NULL 的指针(例如初始循环入口处的 head)，该指针将接收新节点，以及新节点的 next指针将为 NULL .如果您随后更改 lastPtrRef 中的地址指向 next最后插入的节点的指针(指向 NULL；我们刚刚介绍过)，并重复该过程，它将在那里挂起另一个节点，设置该节点的 next指向 NULL 的指针等。每次迭代，lastPtrRef地址最后一个节点的 next指针，始终为 NULL .

就是这样push被用来构造一个正向链表。最后一个想法。如果你有这个链表，你会得到什么:

#include <stdio.h>
#include <stdlib.h>

struct Node
{
    int data;
    struct Node* next;
};

void push(struct Node** headRef, int data)
{
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = *headRef;
    *headRef = newNode;
}

int main()
{
    //points to the head node of the linked list
    struct Node* head = NULL;
    push(&head, 1);
    push(&head->next, 2);
    push(&head->next, 3);

    for (struct Node const *p = head; p; p = p->next)
        printf("%p ==> %d\n", p, p->data);
}

这个看似无辜的例子进一步说明了我说 push 的原因更像是一个通用的 insert比什么都重要。这只是填充初始头节点。

push(&head, 1);

然后通过使用新节点的地址 next 附加到该节点指针作为第一个参数，类似于你的 constructList正在做，但没有 lastPtrRef变量(我们这里不需要它):

push(&head->next, 2);

但是接下来:

push(&head->next, 3);

嗯。与先前调用相同的指针地址，那么它将做什么？提示:记住那是什么 newNode->next = *headRef line 确实如此(我一直在喋喋不休地谈论它；我希望有什么东西卡住了)。

上面程序的输出是这样的(显然实际地址值会有所不同，具体取决于您的实例和实现):

0x100705950 ==> 1
0x10073da90 ==> 3
0x100740b90 ==> 2

希望对您有所帮助。