0

我正在研究数据结构和链表，但我没有得到如何在没有递归的情况下制作链表副本的概念。有人可以解释一下吗。

4

5 回答 5

2

一个简单的迭代逻辑的伪代码是：

  1. 从原始列表的开头开始，origHead。
  2. 设置一个临时指针指向原始列表的头部，tempNode = origHead.
  3. 如果tempNode= NULL，则转到第 17 步。
  4. 如果tempNode != origHead，则转到第 10 步。
  5. 为复制列表的头部分配内存，copyListHead.
  6. 设置copyListHead->next为NULL。
  7. 设置一个临时指针指向复制列表的头部，copyListTempNode = copyListHead.
  8. tempNode = tempNode->next.
  9. 转到第 3 步。
  10. 为节点分配内存newCopyNode。
  11. 复制tempNode->data到newCopyNode->data.
  12. 设置newCopyNode->next为 NULL。
  13. 指向。copyListTempNode->next_newCopyNode
  14. copyListTempNode = newCopyNode.
  15. tempNode = tempNode->next.
  16. 转到第 3 步。
  17. 停止。
于 2013-03-11T06:12:14.700 回答
1

这个怎么运作

  1. 声明两个指针：一个dst指针，它将是最终的函数结果，以及next指向指针的指针，它始终保存将接收下一个节点分配的指针的地址。next指针指向指针最初保存 的地址dst。

  2. 虽然我们仍有要复制的节点 ( src != NULL)，但请执行以下操作：

    • 分配一个新节点，将结果指针分配给*next.
    • 将节点数据从 复制src到*next。
    • 分配next来保存node->next我们刚刚分配的成员的地址。该成员可以使用&(*next)->next.
    • 将输入源指针前进到其下一个节点：src = src->next.
    • 重复（2）。

  3. 一旦完成，总是*next的值NULL。这确保添加到列表中的最终节点（如果有）具有NULL它的next指针。如果根本没有节点添加到列表中（例如，何时src调用NULL我们的函数），则会将 的值设置dst为 NULL，因为它是dst当前保存在 中的地址next。

  4. 将 的值dst作为函数结果返回。

该算法的代码如下所示：

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

Node* CopyList(const Node* src)
{
    Node *dst = NULL, **next = &dst;
    while (src)
    {
        // allocate new node
        *next = malloc(sizeof(**next));
        if (*next)
        {
            // copy_node() for complex duplication
            (*next)->data = src->data; 

            // reposition our next-link to the address of ptr->next
            //  of the node we just added.
            next = &(*next)->next;

            // and finally, advance the source pointer
            src = src->next;
        }
        else
        {
            perror("Failed to allocate node.");
            exit(EXIT_FAILURE);
        }
    }
    *next = NULL;
    return dst;
}

注意：这也是从串行输入文件构建前向链接列表的好方法。它确保头部只初始化一次，并且每个后续节点总是附加到最后一个节点的next指针。

于 2013-03-11T06:09:27.457 回答
1

没有递归 === 使用迭代。P码：

LinkedList *l1 = (the_head), *l2 = copy_node(l1);
for (tmp l1->next; tmp != NULL; tmp = tmp->next, l2 = l2->next) {
    l2->next = copy_node(tmp);
}
于 2013-03-11T05:40:37.177 回答
0

完全没有理由为此使用递归——简单的迭代效果很好。复制一个节点。如果指向下一个节点的指针不为空，则对下一个节点重复该过程（并将next刚刚复制的节点中的链接设置为指向您复制的下一个节点）。

于 2013-03-11T05:40:49.223 回答
0

将链表复制到空列表的简单方法是使用递归，如下所示，

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

Node* copy_list(Node* list) {
    if (list == NULL) return NULL;

    Node* result = new Node;
    result->value = list->value;
    result->next = copy_list(list->next);
    return result;
}

但是如果你不想使用递归，那么你必须手动复制每个不为空的列表，方法是使用循环，直到你得到 (node)->next = NULL 作为检查。

于 2013-03-11T05:45:03.397 回答