1

好的，所以我是第一次尝试 C++，因为看起来我将不得不在即将到来的大学课程中使用它。我有几年的编程经验，但在非垃圾收集领域并不多。

我有一个类，一个用于双向链表的节点。所以基本上它有一个值和两个指向其他节点的指针。主构造函数看起来像Node(const std::string & val, Node * prev, Node * next). 该练习包括一个复制构造函数，该构造函数对另一个节点进行浅拷贝，并在其上方添加一条注释，说明将其更改为深拷贝。

这就是我认为的意思：

Node(const Node & other)
      : value(other.value)
{
  prev = new Node(other.prev->value, other.prev->prev, other.prev->next);
  next = new Node(other.next->value, other.next->prev, other.next->next);
}

这似乎实现了使更改复制的节点不会影响新节点的目标。但是，当我这样做时，我在堆上分配新的东西。这让我很担心，因为我认为这意味着我也应该在节点的析构函数中删除它。但这现在与另一个构造函数不一致，其中指向节点的指针刚刚传入，已经指向某些东西。我不能在这种情况下正确地进入析delete构函数，对吗？nextprev

我真的很困惑，感谢指导！

编辑：这是代码（在我上面的更改之前），根据要求：

#include <string>

//! Node implements a doubly-linked list node
class Node {
    friend class LinkedList;  //!< LinkedList can access private members of Node
public:

    //!  Constructor
    Node(const std::string & v, Node * p, Node * n) :
      value(v), prev(p), next(n)
    {
    }

    //! Change to deep copy
    Node(const Node & other) :
      value(other.value), prev(other.prev), next(other.next)
    {
    }

    //!  Read-only public methods for use by clients of the LinkedList class
    const std::string & GetValue() const
    {
      return value;
    }


    Node * GetPrevious()const
    {
      return prev;
    }


    Node * GetNext()const
    {
      return next;
    }

    //! Change to deep copy
    Node & operator=(const Node & other)
    {
        if(this!=&other)
        {
            value=other.value;
            prev=other.prev;
            next=other.next;
        }
        return *this;
    }

 private:
    std::string value;        //!< value stored in the node
    Node * prev;            //!< pointer to previous node in the list
    Node * next;            //!< pointer to next node in the list
};
4

5 回答 5

2

通常“深拷贝”涉及遍历数据结构并复制整个事物。在您的情况下，给定一个节点，制作列表的完整副本。

于 2009-01-22T05:51:31.670 回答
2

深拷贝制作结构的完整拷贝。我所说的结构是指协同工作以执行任务的对象的集合。如果您有一个汽车类，其中每个车轮和车身都有一个对象 - 深度副本将复制整个汽车（并复制车轮和车身）。

在您的情况下，“整个结构”是列表。只有在“列表级别”执行深层复制操作才有意义。节点的深层副本将复制节点指向的数据 - 但不会将自己分配为列表的一部分（因为节点应该不知道“主”列表对象）。

List* List::CopyList()
{
    List* nlist = new List();
    ListNode* node = NULL, prev = NULL;
    ListNode* newNodes = new ListNode[m_nodeCount];
    int i = 0;
    while ((node == NULL && node = m_first) || (node = node->Next()) != NULL)
    {
        newNodes[i] = node->CopyNode(); // also makes a new copy of the node's data
        newNodes[i]->SetNext(NULL);
        newNodes[i]->SetPrev(prev);
        if (prev) prev->SetNext(newNodes[i]);
        prev = newNodes[i];
        ++i;
    }

    if (m_len > 0)
        nlist->SetFirst(newNodes[i]);
    if (m_len > 1)
        nlist->SetLast(newNodes[m_len - 1]);
    return nlist;
}

注意：我只是从我的屁股中提取了那个代码，所以它没有经过测试。希望它有所帮助:)

于 2009-01-22T06:02:52.193 回答
2

首先，我不太确定应该如何理解练习的目标。副本应该有多深？在像你这样的解决方案中，this->next->next仍然other.next->next是同样的事情。这个对象也应该被复制吗？清单的其余部分？它在哪里结束？当然可以深度复制整个列表，但我认为这将是单个节点的复制构造函数的一种非常出乎意料的行为。

也许value成员变量是一个指针，应该被深度复制？这对我来说更有意义。

但回到你的解释：

Node a(...);
// ... more code that adds a whole list to a
Node b(a);

您的实施存在两个问题。为一个b->next->prev点到a，而我怀疑它应该点回b。其次，您需要考虑极端情况，其中a可能是列表中的第一个或最后一个节点。

对于你的主要问题：你当然是对的，新创建的对象需要delete再次被 d 。无论您只是复制prevandnext节点还是整个列表，我都会说该副本的用户有责任再次删除所有复制的节点。我假设对于一个正常的、未复制的列表，该列表的用户将遍历所有节点，并在完成列表后一个接一个地手动删除它们。他不会假设一个节点的析构函数会删除整个列表。副本也是如此，它们的行为应该相同。复制内容的用户应删除所有副本。（在实践中，您可能会有一个list类，它为您完成所有节点管理）。

但是同样，如果节点的复制构造函数复制整个列表，甚至只是其中的几个节点，这将是非常出乎意料的，人们总是会忘记清理所有这些副本。但这不是你的节点类的错，而是练习要求。

于 2009-01-22T06:28:14.687 回答
2

你的担心是对的。

通过将指针传递给 Node 构造函数，没有关于随指针传递的所有权信息。这是构造函数的糟糕设计。要么你应该传递一个引用来表明你不拥有下一个节点，要么传递一个 std::auto_ptr<> 来表明你必须拥有所有权。有人可能会争辩说 next 或 prev 可能是 NULL（列表的开头或结尾），因此您不能使用引用，但这可以通过使用替代构造函数来克服。

当然也有例外：
Node 类是否是另一个类的私有成员。如果是这种情况，Node 类的使用完全由所有者控制，因此其正确使用将由所属类控制。

您没有提供的是析构函数的定义。有了这个，我们将能够判断节点是否实际上拥有传递给构造函数的指针的所有权（或者 next 和 prev 是否​​已经是智能指针）？

于 2009-01-22T06:28:20.473 回答
1

如果每个节点都复制它指向的节点，那么您可以安全地删除析构函数中的对象。如果您要传递指针（作为构造函数 Node(const std::string & v, Node * p, Node * n)），那么您不会“拥有”指针，也不应该删除它们。如果这是链表类的一部分，那么该类应该拥有指针并根据需要删除对象。您还可以使 Node 成为链表类的私有子类，以避免用户（或您自己）弄乱您的指针。

您在实现中的递归也犯了一个错误，复制构造函数包含一层深层复制并调用“普通”构造函数，该构造函数采用指针，使其变浅。这意味着您的深度复制只有一层深度。它应该重复调用复制构造函数，如下所示：

Node(const Node & other) : value(other.value)
{
  prev = new Node(*(other.prev));
  next = new Node(*(other.next));
}

AFAIK 虽然在这里使用深拷贝没有任何好处，但我能想到的唯一实际应用是在复制整个列表时，这可以在表示所述列表的类中更有效地处理。

于 2009-02-02T12:12:15.610 回答