выполнения глубокого копирования в конструктор копирования

Question

У меня есть стек класса, который определяется следующим образом:

#ifndef STACK_H 
#define STACK_H 
#include "MyException.h" 
#include <iostream> 

using namespace std; 

template<class T> 
class Stack; 

template<class T> 
ostream& operator<<(ostream&,Stack<T>&); 

template<class T> 
class Stack 
{ 
public: 

    friend ostream& operator<< <T>(ostream&,Stack<T>&); 

    /*The constructor for the Stack class*/ 
    Stack(); 

    /*The copy constructor*/ 
    Stack(const Stack<T>& other); 

    Stack<T>& operator=(const Stack<T>& other); 

    /*The destructor for the stack class*/ 
    ~Stack(); 

    void push(const T& el); 

    T pop(); 

    bool isEmpty(); 

private: 
    /*The node class.*/ 
    class Node 
    { 
     public: 
      Node(const T& data, Node* n = 0) 
      { 
       element = data; 
       next = n; 
      } 

      T element; 
      Node* next; 
    }; 

    /*The top of the stack*/ 
    Node* top; 
}; 
#include "Stack.C" 
#endif 

И я должен выполнить глубокую копию на мой конструктор копирования. Но то, что я сделал, это создать временный массив и скопировать все элементы в объекте, полученном параметром, в массив, а затем узел в массив, а затем поместить все их в узел, определенный в классе Stack. Это, как я это сделал:

template<class T> 
    Stack<T>::Stack(const Stack<T>& other) 
    { 

     top = NULL; 

     if(other.top == NULL) 
     { 
      this->top=NULL; 
     } 

     else 
     { 

      Node* count; 
      count= other.top; 

      int num=1; 

      while(count->next != NULL) 
      { 
       num++; 
       count = count->next; 
      } 
      cout<<"test"<<endl; 



      T arr[num]; 
      arr[0] = other.top->element; 



      Node* count2; 
      count2= other.top; 

      for(int i = 1 ; i<num; i++) 
      { 
       arr[i] = count2->next->element; 

       count2 = count2->next; 
      } 

      T temp; 
      for(int i =0, j=num-1; i<num/2 ; i++, j--) 
      { 
       temp = arr[i]; 
       arr[i] = arr[j]; 
       arr[j] = temp; 
      } 


      for(int i =0; i<num; i++) 
      { 
       push(arr[i]); 
       cout<<arr[i]<<endl; 
      } 
     } 
    } 

Можно предположить, что мой толчок (сопзЬ T & эл) и поп() работает отлично. Может ли кто-нибудь помочь мне выполнить глубокую копию?

Answer 1

Нет причин для массива для глубокого копирования стека. Поскольку у вас есть все указатели на узлы в вашей текущей цепочке стека, просто перейдите в этот связанный список. Необычная часть этого алгоритма включает в себя переадресацию новых узлов по мере их ввода и тем самым сохранить исходный порядок стека. Существует несколько способов сделать это, но я предпочитаю использовать один указатель на указатель, который всегда содержит адрес указателя, который будет заполнен следующей копией.

Stack(const Stack<T>& other) 
    : top(nullptr) 
{ 
    const Node* p = other.top; 
    Node **pp = &top; 
    while (p) 
    { 
     *pp = new Node(*p); 
     p = p->next; 
     pp = &(*pp)->next; 
    } 
    *pp = nullptr; 
} 

Когда это будет сделано, стек будет реплицирован с глубокой копией и сохранит порядок исходных объектов. И я настоятельно рекомендую выполнить копию Node(const Node&) copy-ctor, которая копирует элемент данных только и устанавливает следующий указатель на нуль.

Как это работает

В конце концов, это не более чем одного сканирования копии списка дальновидной связаны между собой. Указатель pp всегда содержит адрес следующего указателя, которому будет назначен новый узел. Важно помнить, что указатель, который он адресует, - часть списка, а не какой-то временной указатель. Первоначально pp присваивается адрес верхнего указателя, который уже не был инициализирован до NULL. Оттуда повторяется до тех пор, пока мы не закончим узлы:

1. Назначьте копию текущего узла источника *pp. Это означает, что указатель, адресованный pp, получит новый адрес узла.
2. Предварительный номер pp, чтобы удерживать адрес члена next самого узла, который он только что назначил. Это станет следующей целью следующей вставки
3. Передвиньте указатель источника на следующий узел источника.

Это повторяется до тех пор, пока мы не закончим узлы. В то время pp содержит адрес последнего Указатель узла next, которому должно быть присвоено значение null, чтобы наш список правильно завершился. Это цель закрытия *pp = nullptr;. При этом список теперь завершается, и теперь объект имеет реплику связанного списка исходного объекта.

Некоторые блюда для размышления. Что произойдет, если исходный список изначально пуст? Будет ли это работать с круговым списком (ответ: нет, даже не попробуйте).