C语言 了解使用本地引用构建链表背后的逻辑

Question

下面是使用本地参考逻辑创建链表的代码。 无法理解 for 循环中的代码，尤其是第二行。(见// HERE(

有人可以详细说明这种逻辑是如何工作的。

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

struct Node* buildWithLocalRef()
{
int i=0;
struct Node *head = NULL;
struct Node **lastptrRef = &head;
for(i=1;i<6;i++)
{
push(lastptrRef,i);
lastptrRef = &((*lastptrRef)->next); // HERE
}
return head;
}
int main()
{
struct Node* head;
head = buildWithLocalRef();
printList(head);
return 0;
}

Answer 1

您看到的技术是通过前向链接构建链表。这是从头到尾构建有序列表的最直接、最明智的方法，其中列表没有尾部指针(而你的没有(。

这里没有"参考"。这不是C++。这是使用指向指针的指针。变量名称命名得很糟糕，顺便说一句。它的工作原理是这样的：

1. 最初列表为空，head为NULL
2. 指向指针的指针，lastptrRef将始终保存下一个指针的地址(不是地址;存在差异(以填充新的动态节点分配。最初，指针到指针保存head指针的地址，该地址最初是NULL的(有意义，这是您希望第一个节点挂起的位置(。
3. 循环循环时，将在push中分配一个新节点。该节点的next指针设置为lastptrRef指向的指针中的任何值(在函数中作为head_ref传递(，然后将lastptrRef指向的指针更新为新的节点值。
4. 最后，lastptrRef获得刚刚添加的节点中next成员的地址，并重复该过程。

在每种情况下，lastptrRef保存包含输入push时NULL的指针的地址。此push函数使其更难理解。(稍后会详细介绍(。直接完成正向链接更容易理解，在这种情况下，它会更容易理解

struct Node* buildWithLocalRef()
{
struct Node *head = NULL;
struct Node **pp = &head;
for (int i = 1; i < 6; i++)
{
*pp = malloc(sizeof **pp);
(*pp)->data = i;
pp = &(*pp)->next;
}
*pp = NULL;
return head;
}

在这里，pp始终保存下一个指针的地址，我们将用新的节点分配填充。最初，它包含head的地址。插入每个节点时，pp设置为插入的最新节点内next指针的地址，从而使您能够在下一次迭代中继续链。循环完成后，pp将next指针的地址保存在列表中的最后一个节点中(或者未插入任何内容的head地址;考虑如果我们完全拉出循环会发生什么(。我们希望NULL终止列表，因此执行最终*pp = NULL;。

您发布的代码执行相同的操作，但方式更加复杂，因为push旨在将项目推到列表的前面(显然(。该函数始终将head_ref指向的指针设置为添加的新节点，并且节点的next始终首先设置为*head_ref中的旧值。因此，可以通过这样做来构建堆栈：

struct Node* buildStack()
{
struct Node *head = NULL;
for (int i = 1; i < 6; i++)
push(&head, i);
return head;
}

现在，如果您打印生成的链表，则数字将按输入的相反顺序排列。事实上，push在这里名副其实。双重用途它来构建一个前向链列表是有创意的，我会承认这一点，但最终它让它有点混乱。