雙鏈表列表模板複製構造器指派操作符

Question

我用C++編寫了一個簡單的雙向鏈表實現使用模板。但是，我有一些複製構造函數和賦值運算符的問題。我的代碼給了我分段錯誤，我不知道如何解決它，哪裏是錯誤（問題是拷貝構造函數和賦值運算符）：

#include <iostream> 
using namespace std; 

template <class T> 
class MyNode 
{ 
public: 
    MyNode(const T &e = T(), MyNode *n = NULL, MyNode *p = NULL) : element(e), next(n), previous(p) {} 
    ~MyNode() {} 
    T element; 
    MyNode *next; 
    MyNode *previous; 

}; 

template <class T> 
class MyList 
{ 
private: 
    MyNode<T> *head; 
    MyNode<T> *tail; 

public: 
    MyList() 
    { 
     head = new MyNode<T>(); 
     tail = new MyNode<T>(); 
    } 
    ~MyList() 
    { 
     clear(); 
     delete head; 
     delete tail; 
    } 
    MyList(const MyList& otherList) 
    { 
     while (otherList.head->next!=NULL) 
     { 
      MyNode<T> *curr = otherList.head->next; 
      insertLast(curr->element); 
      otherList.head->next = curr->next; 
     } 
    } 

    MyList& operator=(const MyList& otherList) 
    { 
     if(this == &otherList) 
      return *this; 

     while (otherList.head->next!=NULL) 
     { 
      MyNode<T> *curr = otherList.head->next; 
      insertLast(curr->element); 
      otherList.head->next = curr->next; 
     } 

     return *this; 
    } 

    bool isEmpty() 
    { 
     return (head->next == NULL); 
    } 

    void insertFirst(const T &e) 
    { 
     if (isEmpty()) 
     { 
      MyNode<T> *newNode = new MyNode<T>(e); 
      head->next = newNode; 
      tail->previous = newNode; 
     } 
     else 
     { 
      MyNode<T> *actualFirst = head->next; 
      MyNode<T> *newNode = new MyNode<T>(e, actualFirst); 
      actualFirst->previous = newNode; 
      head->next = newNode; 
     } 
    } 
    void insertLast(const T &e) 
    { 
     if (isEmpty()) 
     { 
      MyNode<T> *newNode = new MyNode<T>(e); 
      head->next = newNode; 
      tail->previous = newNode; 
     } 
     else 
     { 
      MyNode<T> *actualLast = tail->previous; 
      MyNode<T> *newNode = new MyNode<T>(e, NULL, actualLast); 
      actualLast->next = newNode; 
      tail->previous = newNode; 
     } 
    } 

    bool remove(MyNode<T> *r) 
    { 
     if (isEmpty()) 
     { 
      return false;; 
     } 
     MyNode<T> *removeNode = tail->previous; 
     while (removeNode!=NULL) 
     { 
      if (removeNode==r) 
      { 
       break; 
      } 
      removeNode = removeNode->previous; 
     } 
     if (removeNode==NULL) 
     { 
      return false; 
     } 
     else 
     { 
      MyNode<T> *afterRemove = removeNode->next; 
      MyNode<T> *beforeRemove = removeNode->previous; 
      if (afterRemove==NULL) 
      { 
       tail->previous = beforeRemove; 
      } 
      else 
      { 
       afterRemove->previous = beforeRemove; 
      } 
      if (beforeRemove==NULL) 
      { 
       head->next = afterRemove; 
      } 
      else 
      { 
       beforeRemove->next = afterRemove; 
      } 
      delete removeNode; 
      return true; 
     } 
    } 

    void clear() 
    { 
     while (tail->previous!=NULL) 
     { 
      MyNode<T> *remove = tail->previous; 
      tail->previous = remove->previous; 
      delete remove; 
     } 
    } 

    void show() 
    { 
     while (head->next!=NULL) 
     { 
      MyNode<T> *curr = head->next; 
      std::cout << curr->element << "\n"; 
      head->next = curr->next; 
     } 
    } 

}; 

int main() 
{ 
    MyList<int> l1; 
    l1.insertLast(1); 
    l1.insertLast(2); 
    l1.insertLast(3); 
    //l1.show(); 

    MyList<int> l2(l1); 
    //l2 = l1; 
    l2.show(); 

    return 0; 
} 

Answer 1

如果你想複製一個列表，你有做一個深層複製：

MyList(const MyList& otherList) 
{ 
    if (otherList.head == nullptr) 
     head = tail = nullptr;      // if "otherList" is empty the new list is empty too. 
    else 
    { 
     head = new MyNode<T>(otherList.head);  // allocate head and copy data 
     MyNode<T> tempOther* = otherList.head->next; 
     MyNode<T> temp* = head; 
     while (tempOther != nullptr) 
     { 
      temp->next = new MyNode<T>(tempOther, nullptr, temp); // allocate next elemnt and copy data (predecessor is "temp") 
      temp = temp->next;          // temp refers to last element of list 
      tempOther = tempOther->next;       // step one forward 
     } 
     tail = temp; 
    } 
} 

assigne運算符的工作方式與複製構造函數類似。

此外，您不需要爲head和tail分配節點。 head只是指向第一個元素的指針，而tail只是指向列表最後一個元素的指針。

MyList() 
    : head(nullptr) 
    , tail(nullptr) 
{} 

適應isEmpty，insertFirst和insertLast這樣的：

bool isEmpty() { return head == nullptr); } 

void insertFirst(const T &e) 
{ 
    if (isEmpty()) 
     head = tail = new MyNode<T>(e); 
    else 
    { 
     MyNode<T> *newNode = new MyNode<T>(e, head, nullptr); 
     head->previous = newNode; // new node is predecessor of head 
     head = newNode ;   // new head is new node 
    } 
} 

void insertLast(const T &e) 
{ 
    if (isEmpty()) 
     head = tail = new MyNode<T>(e); 
    else 
    { 
     MyNode<T> *newNode = new MyNode<T>(e, nullptr, tail); 
     tail->next = newNode; // new node is successor of tail 
     tail = newNode ;  // new tail is new node 
    } 
} 

適應方法remove這樣的：

bool remove(MyNode<T> *r) 
{ 
    MyNode<T> *removeNode = head; 
    while (removeNode != nullptr) // search the node to remove 
    { 
     if (removeNode == r)   // break if node to remove is found 
      break; 
     removeNode = removeNode->next; // setp on forward 
    } 
    if (removeNode == r) // if node was found remove it 
    { 
     if (removeNode == head) 
      head = removeNode->next;  // if head is removed, new head is successor of head 
     if (removeNode == tail) 
      tail = removeNode->previous; // if tail is removed, new tail is predecessor of tail 
     if (removeNode->previous!= nullptr) 
      removeNode->previous->next = removeNode->next;  // new succesor of predecessor is successor 
     if (removeNode->next != nullptr) 
      removeNode->next->previous = removeNode->previous; // new prdecessor of successor is predecessor 
     delete removeNode; 
     return true; 
    } 
    return false; 
} 

最後clear和show：

void clear() 
{ 
    MyNode<T> *curr = head; 
    while (curr != nullptr) 
    { 
     MyNode<T> *del = curr; 
     curr = curr->next; 
     delete del; 
    } 
    head = tail = nullptr; 
} 

void show() 
{ 
    MyNode<T> *curr = head; 
    while (curr != nullptr) 
    { 
     std::cout << curr->element << "\n"; 
     curr = curr->next; 
    } 
}