深层复制队列递归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

首先，要明白您实际上并没有在这里复制任何东西。您只是通过递归进行枚举并分配指针。在最好的，这是一个肤浅的副本；实际上，你的算法已经完全崩溃了。有递归复制链表的方法，包括双向链表。这样做是否明智则另当别论。

---

单向列表

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

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;
}

---

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