3

首先，我意识到 StackOverflow 上有多个关于此的主题。我在理解其中一些人的反应时遇到了一点麻烦。我正在创建这个，希望有人可以帮助我理解这个过程。

如果这个问题看起来相对新手，我深表歉意，但我正在尽力理解它。

我正在学习数据结构，并被要求根据提供的标头创建 LinkedList 实现文件。

这是作业，所以请不要“这里是确切的代码”类型的答案。欢迎使用伪代码、步骤和提示。

这是我目前正在处理的标题部分：

typedef std::string ElementType;

class LinkedList
{
private:
   class Node
   {
   public:
      ElementType data;
      Node * next;

      Node( )
      : data( ElementType( ) ), next( NULL )
      { }

      Node( ElementType initData )
      : data( initData ), next( NULL )
      { }
   }; // end of Node class

   typedef Node * NodePointer;

public:
   LinkedList( );
   /* Construct a List object

      Precondition: none.
      Postcondition: An empty List object has been constructed.
   */

   LinkedList( const LinkedList &source );
   /* Construct a copy of a List object.

      Precondition: None. 
      Postcondition: A copy of source has been constructed.
   */

   ~LinkedList( );
   /* Destroys a List object.

      Precondition:  None.
      Postcondition: Any memory allocated to the List object has been freed.
   */

   const LinkedList & operator=( const LinkedList &rightSide );
   /* Assign a copy of a List object to the current object.


private:
   NodePointer first;
   int mySize;
};

到目前为止，我已经创建了析构函数，你能检查并确保它是正确的吗？

//Destructor
LinkedList::~LinkedList() 
{ 
    NodePointer ptr = first;

    while(ptr != 0 ) {
        NodePointer next = ptr->next;
        delete ptr;
        ptr = next;
    }
    first = 0;
}

现在这是我迷路的部分......创建复制构造函数的基本步骤是什么？我已经完成了简单的默认构造函数，但是我对应该在复制构造函数上做什么感到有点困惑。

我也对重载 = 运算符感到有些困惑，我认为它与复制构造函数非常相似。

编辑

我第一次尝试复制构造函数：

LinkedList::LinkedList(const LinkedList & source)
{
    //create a ptr to our copy
    Node * copy_node = source.first;
    //where we will be inserting our copy
    Node * insert_node = first;

    while(copy_node != nullptr) 
    {
        //insert our new copy node
        insert_node = new Node(copy_node->data);
        //move to our next node
        copy_node = copy_node->next;

        if(copy_node != nullptr) {
            insert_node = insert_node->next;
        } else {
            insert_node = first;
        }

        //update size
        mySize++;

    }
}

我觉得那里少了点什么。

4

2 回答 2

3

创建复制构造函数的基本步骤是什么？我已经完成了简单的默认构造函数，但是我对应该在复制构造函数上做什么感到有点困惑。

嗯，很明显，你需要复制源代码。如果源是 N 个节点的列表，那么您需要构建另一个 N 节点列表，每个节点都是源中相应节点的副本。

所以遍历源节点并创建它们的副本。

我也对重载 = 运算符感到有些困惑，我认为它与复制构造函数非常相似。

是的，除非您需要先处理当前节点。然而，实现赋值的一种简单而安全的方法是复制和交换，因此定义一个正确的交换成员：

void swap(LinkedList& other)
{
   std::swap(first, other.first);
   std::swap(size, other.size);
}

然后用它来实现赋值：

LinkedList& operator=(const LinkedList& source)
{
   LinkedList(source).swap(*this);
   return *this;
}

这会创建一个临时副本，它是 的副本source，然后将其与 交换*this，因此 的旧内容*this被临时销毁，并*this以复制的数据结束。

注意返回类型应该是非常量的，从赋值运算符返回一个常量引用是不习惯的。

于 2013-11-03T21:20:56.763 回答
2

最简单的方法是实现一个函数，将新节点添加到列表中，并在构造函数内的循环中调用它：

LinkedList(const LinkedList& rhs)
{
   Node* node = rhs.first;
   while (node) {
     add(node.data);
     node = node->next;
   }
}

void add(ElementType data)
{
   Node* node = new Node(data);
   // add node somehow
   // I'd recommend to keep pointer to the tail
}

请注意，此实现并非异常安全！

编辑：为复制构造函数添加了复制功能，这是异常安全的第一步：

LinkedList(const LinkedList& rhs)
{
  copy(rhs.first, first);
}

void copy(Node* src, Node*& dest)
{
 // handle the head element separately
 if (!src) {
   return; // empty list
 } else {
   dest = new Node(src->data); // equivalent to first = new Node...
   src = src->next;
 }

 // copy the rest of the list
 Node* p = dest; 
 while (src) {
   p->next = new Node(src->data);
   src = src->next;
   p = p->next;
 }
}
于 2013-11-03T21:17:58.413 回答