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

问题描述

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

#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)->next);

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

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

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

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

我非常感谢有关此代码如何工作的任何见解。谢谢你。

标签： clinked-list

解决方案

这使用了一种称为forward-chaining的技术，我相信您已经理解了这一点（使用指向指针的指针来前向链接链表结构）。

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

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

newNode->next = *headRef

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

它接受一个指向指针的指针headRef作为参数，以及一些要放入被管理的链表的数据。
在分配一个新节点并将数据保存在其中之后，它将新节点的指针设置为当前存储在取消引用next的指针到指针中的任何值（所以..一个指针）这就是我上面提到的那一行所完成的。 headRef
然后它将新节点的地址存储在它刚刚从中提取先前地址的同一位置；IE*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线的作用（我一直在喋喋不休；我希望有些东西卡住了）。

上面程序的输出是这样的（显然实际地址值会有所不同，取决于您的实例和实现）：

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

希望有帮助。

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

问题描述

解决方案

推荐阅读