Как реализовать конструктор глубокого копирования в связанный список? - PullRequest
Новая
       76

Как реализовать конструктор глубокого копирования в связанный список?

0 голосов
/ 19 сентября 2019

Для этой проблемы, над которой я сейчас работаю, я пытаюсь создать метод в этом связанном списке, который выполняет глубокое копирование из одного элемента в другой.Прямо сейчас внутренняя часть метода пуста, потому что я не могу заставить что-либо работать ради своей жизни.Есть ли какой-нибудь способ, которым я мог бы получить некоторую помощь, реализуя этот конструктор глубокого копирования в области кода ниже, которая прокомментирована?Спасибо. 

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

1 Ответ

1 голос
/ 19 сентября 2019

Предполагая, что append() работает правильно, вы можете просто вызывать его несколько раз в цикле для каждого элемента в copy.

Этот подход, учитывая то, как вы реализовали свой связанный список с указателем tail, делает его идеальным решением.Вы написали функцию append, так что это просто вопрос ее стратегического использования.

Тем не менее, имейте в виду, что если вы внедрили свой связанный список без указателя хвоста (куда вы должны были перейтиконец списка к append), этот подход все еще будет работать, но будет крайне неэффективным и не удовлетворительным.

Вот пример (не проверенный): 

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

Примечаниечто это не было проверено на граничные условия, поэтому вам может потребоваться проверить, является ли copy пустым, прежде чем проходить цикл.

Вот пример, который работает для простого случая

...