如何在链表中实现深层复制构造函数？-解网

问：

对于我目前正在处理的这个问题，我正在尝试在此链表中创建一个方法，该方法执行从一个项目到另一个项目的深度复制。现在，这个方法的内部是空的，因为我无法为我的生活做任何事情。有什么方法可以在下面注释的代码区域中获得一些帮助来实现这个深层复制构造函数？谢谢。

#include <string>
#include <iostream>
#include <cstddef>

using std::string;

class Item { 

public:

  string s; 

  Item(const char *a_s = "") { 
    s = a_s;
  }

  Item(string a_s) {
    s = a_s;
  }
};


class List {

  private:

      class ListNode { 

        public: 
          Item item; 
          ListNode * next; 
          ListNode(Item i) { 
            item = i;
            next = nullptr;
          }
      }; 

      ListNode * head; 
      ListNode * tail;

  public:

      class iterator {

        ListNode *node;

      public:
        iterator(ListNode *n = nullptr) {
          node = n;
        }

        Item& getItem() { return node->item; } //Not sure how this works
        void next() { node = node->next; }
        bool end() { return node==nullptr; }

      };



  public:

      List() {
        head = nullptr;
        tail = nullptr; //Sets the head and tail
      }

      List(const List & copy) { //Trying to create a copy constructor right here.

      }

      bool empty() { //Tells you if the list is empty
        return head==nullptr;
      }

      void append(Item a) { 

        ListNode *node = new ListNode(a);
          if ( head == nullptr ) {
            head = node;
            tail = node;
          } else {
            tail->next = node;
            tail = node;
          }
      }

      bool remove (Item &copy);

      void traverse() {
        ListNode *tmp = head;
        while(tmp != nullptr) {
          tmp = tmp->next;
        }
      }

      iterator begin() const {
        return iterator(head);
      }

};

    bool List::remove(Item &copy)
    {
      if (!empty()) {
        copy = head->item;
        ListNode *tmp = head->next;
        delete head;
        head = tmp;
        if (head==nullptr)
          tail = nullptr;
        return true;
      }
      return false;
    }


int main() {
   List l;
   l.append("eggs");

   List l2 = l; 

   std::cout << "done.\n";

   return 0;
}

C++ 链表复制构造函数 deep-copy

@PaulMcKenzie的建议因指针而变得更好。通常我避免这种方法，因为每次插入时，您都必须在插入之前寻找末端。指针使狩猎蓝精灵变得容易。不要忘记通过添加一个析构函数来执行清理和一个赋值运算符来处理来完成三法则您可能会发现复制和交换习语非常有用。tailtailList l2; l2 = l;

0赞 PaulMcKenzie 9/19/2019

@user4581301 -- 是的，我犹豫要不要发布解决方案，直到我看到有一个尾指针。一旦我看到列表的末尾是 O（1）操作，然后就去它并循环。append()

0赞 Laurel Link 9/19/2019

所以我想在 for 循环中使用 append（）函数将第一个对象中的项目附加到第二个对象？

0赞 PaulMcKenzie 9/19/2019

@JohnHarrison -- 是的。你已经写好了所有的代码，只是你还没有弄清楚如何使用它。

答：

1赞 PaulMcKenzie 9/19/2019 #1

假设它工作正常，您可以对中的每个项目在循环中重复调用它。append()copy

考虑到如何使用指针实现链表，这种方法使其成为理想的解决方案。你写了这个函数，所以这只是一个战略性地使用它的问题。tailappend

但是请注意，如果您实现了没有尾部指针的链表（您必须遍历到列表的末尾），这种方法仍然有效，但效率非常低且不令人满意。append

下面是一个示例（未经测试）：

List(const List & copy) : head(nullptr), tail(nullptr) 
{ 
     ListNode *copyNode = copy.head;
     while (copyNode)
     {
         append(copyNode->item);
         copyNode = copyNode->next;
     }
 }

请注意，这未针对边界条件进行测试，因此您可能需要在必须通过循环之前检查是否为空。copy

下面是一个适用于简单案例的示例

如何在链表中实现深层复制构造函数？

How do I implement a deep copy constructor into a linked list?

评论

评论