在链表中插入节点时递归如何工作？

Question

我无法理解这些函数的工作原理：

Answer 1

如果你 post 整个代码在这里，而不是只 post 一部分会更好。

为了理解列表中节点的插入，首先你应该尝试理解 - fold() 函数在做什么？

递归函数的定义fold():

void *fold(void (*func)(void *, Node *), void *accum, Node *head) {
  if (head == NULL) {
    return accum;
  } else {
    func(accum, head);
    return fold(func, accum, head->next);
  }
}

首先了解fold()函数的参数：

void (*func)(void *, Node *) ：一个函数指针，它可以指向任何带有两个参数的函数——第一个是 void * 类型，第二个是 Node * 和 return 类型没什么。
void *accum : accum 是指向 void 类型的指针，也就是可以转换为任何其他指针类型的通用指针。
Node *head : head 是指向 Node 类型的指针。

现在，让我们解码 fold() 函数定义：

      if (head == NULL) {
          return accum;
      .....
      .....

这是递归的终止条件——当head是NULLreturnaccum（这是一个void指针）。

如果 head 不是 NULL 那么

  } else {
    func(accum, head);
    .....
    .....

调用func(accum, head)，意思是调用传递给fold()的函数作为第一个参数，并传递accum和head作为参数。

在insert()中，调用fold()为-

fold(tail, &ptr, *head);

tail() : 函数
&ptr：指向Node类型
*head : head 列表指针

现在检查 tail() 定义 -

static void tail(void *accum, Node *node) {
  *(Node ***)accum = &(node->next);
}

因为第一个参数 accum 是 void 指针，&ptr 被传递给它，我们知道 ptr 包含 Node ** 类型的地址。所以我们可以将 accum 转换为 (Node ***) 并解引用它将给出 Node ** 指针。 node->next的类型是struct node *，Node是struct node的别名，也就是说node->next的类型是Node *，地址是Node **。因此，我们可以将 &(node->next) 分配给 accum。分配后，accum 将包含传递给 tail().

的 node 指针的地址 next

调用func()后，fold()调用自身（递归调用）：

    return fold(func, accum, head->next);
 }
}

注意现在accum包含当前正在处理的列表节点的下一个指针的地址，传递head->next意味着递归调用将处理列表的下一个节点并且这个递归调用赋值next 节点的地址传递给 accum 指针。有了这么多的理解，现在我可以说，这个递归调用最终会将列表最后一个节点的地址 next 分配给 accum.

当此递归 wind-up 和 return 编辑到 insert() 时，ptr 将具有列表最后一个节点的地址 next。在 fold() 调用后，我们在 insert() 中有以下内容：

*ptr = new;

即将 new 节点分配给最后一个节点的 next 指针，这意味着将新创建的节点插入到列表的最后一个。

在类似的线路上，尝试解码 map 函数和程序的其他部分。

在链表中插入节点时递归如何工作？

How does recursion work when inserting nodes in linked lists?

c

pointers

recursion

linked-list

abstract-data-type