递归深拷贝队列C++（使用双向链表实现）

Question

我正在使用双向链表构建队列。我希望我的深拷贝构造函数递归地深拷贝整个队列，但是当我执行以下操作时出现分段错误：

// Recursive helper method for deep copy constructor
void queue::copyAllNodes(Node* og, Node *cpy) {
    if(og == nullptr) back = og;
    else {
        cpy->previous = og->previous;
        cpy->data = og->data;
        cpy->next = og->next;
        copyAllNodes(og->next, cpy->next);
    }
}

我的构造函数有另一个辅助函数，允许我传入原始节点和我想要复制的复制节点。

Answer 1

首先，了解您实际上并不是在此处复制 任何内容。您只是通过递归和分配指针进行枚举。在 best 那是一个浅拷贝；实际上，您的算法完全被破坏了。有种递归复制链表的方法，包括双向链表。这样做是否明智是另一回事。

单向列表

在进入双向链表的主题之前，请考虑单向链表的基本情况。假设您有一个包含如下节点的链表：

template<class T>
struct Node
{
    T data;
    Node *next;

    Node(T dat, Node *nxt = nullptr)
        : data(std::move(dat))
        , next(nxt)
    {
    }
};

现在假设你想递归地做一个深拷贝。在最简单的形式中，递归复制的算法是：

Node *copyDeep(const Node *p)
{
    Node *res = nullptr;
    if (p)
        res = new Node(p->data, copyDeep(p->next));
    return res;
}

双向列表

引入双链接节点（next 和 prev 成员）使这更具挑战性，但难度不大。首先必须修改节点以包含新成员：

struct Node
{
    T data;
    Node *next;
    Node *prev;

    Node(T dat, Node *nxt = nullptr)
        : data(std::move(dat))
        , next(nxt)
        , prev(nullptr)
    {
    }
};

由此，可以修改 copyDeep 以记住添加的节点以用作递归调用的添加参数。一种方法是：

Node *copyDeep(Node *p, Node *prev = nullptr)
{
    if (p)
    {
        Node *res = new Node(p->data);
        res->prev = prev
        res->next = copyDeep(p->next, res);
        return res;
    }
    return nullptr;
}

在两种情况下，迭代地执行此操作更容易、更快且不易出错（包括堆栈溢出）。在回答你的问题时，是的，你可以递归地复制一个链表。这样做是否是个好主意，我留给你。

递归深拷贝队列C++（使用双向链表实现）

Deep copy queue recursively C++ (Implemented using a doubly linked list)

c++

queue

doubly-linked-list

recursive-datastructures