理解使用本地引用构建链表的逻辑

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++.这是使用指针指针.变量名称可怕地命名为btw.它是如何工作的:

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

在每种情况下,lastptrRef保持包含NULL条目的指针的地址push.此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在这里辜负它的名字.建立一个前瞻性列表的双重目的是创造性的,我会批准,但最终它使它有点混乱.