C++如何創建鏈接列表的副本作爲類對象？

Question

我想使用LinkedList類的duplicate（）方法制作鏈接列表的副本。我一直在摸索着如何使這種方法奏效。

重複的方法需要做一個精確的副本，返回一個指向新列表的指針。我希望能夠在新列表上調用LinkedList方法。我應該返回一個LinkedList指針嗎？或節點指針？我覺得我在這裏完全錯過了一些簡單的東西。

我該如何將新頭節點的位置存儲在LinkedList指針中？

//LinkedList.h 
#pragma once 

#include<string> 

using namespace std; 

struct Node { 
    string nodeData; 
    Node* nextNode; 
}; 

class LinkedList { 
public: 
    LinkedList(); 

    ~LinkedList(); 

    bool insert(string givenData); 

    bool remove(string givenData); 

    void print() const; 

    int count() const; 

    int find(string givenData) const; 

    bool removeAll(); 

    LinkedList* duplicate() const; 

private: 
    Node* head; 
}; 


//LinkedList.cpp duplicate() method 
LinkedList* LinkedList::duplicate() const { 
    LinkedList* newList; 
    Node* newHeadNode = new Node; 
    Node* newNode = new Node; 

    newHeadNode->nodeData = head->nodeData; 
    newHeadNode->nextNode = head->nextNode; 

    Node* currentNode = head->nextNode; 
    Node* previousNode = head; 

    while ((currentNode) && (newNode->nodeData > currentNode->nodeData)) { 
     previousNode = currentNode; 
     currentNode = currentNode->nextNode; 

     newNode->nextNode = previousNode->nextNode; 
     previousNode->nextNode = newNode; 
    } 
} 

Answer 1

你duplicate()代碼中有幾個邏輯問題。

該代碼可以被簡化爲以下：

LinkedList::LinkedList() 
    : head(NULL) 
{ 
} 

LinkedList* LinkedList::duplicate() const 
{ 
    LinkedList* newList = new LinkedList; 

    Node* currentNode = head; 
    Node* previousNode = NULL; 

    while (currentNode) 
    { 
     Node* newNode = new Node; 
     newNode->nodeData = currentNode->nodeData; 
     newNode->nextNode = NULL; 

     if (!newList->head) 
      newList->head = newNode; 

     if (previousNode) 
      previousNode->nextNode = newNode; 
     previousNode = newNode; 

     currentNode = currentNode->nextNode; 
    } 

    return newList; 
} 

這就是說，如果一個Node *tail成員添加到LinkedList，然後duplicate()可以在insert()，其本身可以大大簡化方面來實現：

LinkedList::LinkedList() 
    : head(NULL), tail(NULL) 
{ 
} 

bool LinkedList::insert(string givenData) 
{ 
    Node* newNode = new Node; 
    newNode->nodeData = givenData; 
    newNode->nextNode = NULL; 

    if (!head) 
     head = newNode; 

    if (tail) 
     tail->nextNode = newNode; 
    tail = newNode; 

    return true; 
} 

LinkedList* LinkedList::duplicate() const 
{ 
    LinkedList* newList = new LinkedList; 

    Node* currentNode = head; 
    while (currentNode) 
    { 
     newList->insert(currentNode->nodeData); 
     currentNode = currentNode->nextNode; 
    } 

    return newList; 
} 

如果添加tail是不是一種選擇，那麼至少考慮添加一個可選的Node*參數insert()代替：

Node* LinkedList::insert(string givenData, Node *after) 
{ 
    Node* newNode = new Node; 
    newNode->nodeData = givenData; 
    newNode->nextNode = NULL; 

    if (!head) { 
     head = newNode; 
    } 
    else { 
     if (!after) { 
      after = head; 
      while (after->nextNode) { 
       after = after->nextNode; 
      } 
     } 
     newNode->nextNode = after->nextNode; 
     after->nextNode = newNode; 
    } 

    return newNode; 
} 

LinkedList* LinkedList::duplicate() const 
{ 
    LinkedList* newList = new LinkedList; 

    Node* currentNode = head; 
    Node *newNode = NULL; 

    while (currentNode) 
    { 
     newNode = newList->insert(currentNode->nodeData, newNode); 
     currentNode = currentNode->nextNode; 
    } 

    return newList; 
} 

Answer 2

如果你試圖做一個deep copy（賦值運算符）鏈表，可以考慮使用recursion。

比較this針對通過的第二個列表的參考。如果它們不一樣，則列表clear。如果傳入的列表中有頭指針，則調用遞歸方法。該方法需要node* n。檢查它是否退出，如果有，請用n的下一個指針調用它自己。然後它應該將n的數據添加到列表的頭部。因爲這是遞歸的，所以AddHead調用會在堆棧上等待，直到遞歸完成，然後以相反順序調用，從而導致列表的正確排序。

如果你只是在做一個拷貝構造函數，你可以簡單地設置*this等於傳入的列表。例如。

LinkedList (const LinkedList& other) { 
    count = 0; 
    head = nullptr; 
    *this = other; 
} 

Answer 3

您正在混淆指針和數據的作用，開始。

所有節點都有到下一個節點的「鏈接」。如果要複製列表，則需要創建每個節點的副本，並將它們連接起來。這意味着你不應該將新節點連接到舊節點，而只是將它們之間的新節點連接起來。

newHeadNode->nextNode = head->nextNode;因此是錯誤的。

此外，你的類有一個插入方法，你可以使用，並且可能已經正確地創建了一個節點並設置了舊的尾節點指針。

你的函數體應該像

LinkedList* LinkedList::duplicate() const { 
    // create a new list 
    LinkedList* newList = new LinkedList(); 
    // start from the first node of the old list 
    currnode = this->head; 

    // until currnode is valid 
    while(currnode){ 
     // insert the data in the new list (the new list will deal with the pointers) 
     newList->insert(currnode->data); 
     // go to the next node of the old list 
     currnode = currnode->nextNode; 
    } 

    return newList; 

} 

Answer 4

看起來像雷米Lebeau在這裏之前，我可以回到這裏。唯一可以補充的是稍微更緊湊一點，更困惑的方式來編寫duplicate。這是一個很好的例子，說明一個額外的間接程度如何能夠節省一些工作，所以我會放在這裏。

//LinkedList.cpp duplicate() method 
LinkedList* LinkedList::duplicate() const { 
    // make a new empty list 
    LinkedList* newList = new LinkedList; 

    //get the first node from the list to be duplicated 
    Node * getp = head; 

    //Here be where we get a bit weird. Rather than getting a pointer to the 
    //head node like we did with the source list, we are going to get a pointer 
    //to the head itself! Crazy, right? 
    //But if you think about it, it means we can use head just like any other 
    //pointer to a node (which it is) without having to write any special code 
    //specifically to handle the head or having to carry around previousNode 
    //pointers and other overhead 
    Node ** putpp = &newList->head; 

    //Loop through the source list 
    while (getp != NULL) 
    { 
     *putpp = new Node; //make a new node and insert it into the list 
          //wherever putpp is currently pointing, head or 
          //any node's next 
     (*putpp)->nodeData = getp->nodeData; // copy the source node's data 
     putpp = &(*putpp)->nextNode; // point at the new node's next so we can 
             // add the next new node 
     getp = getp->nextNode; // point at the next source node 
    } 
    *putpp = NULL; // null the last next pointer to end the list 
    return newList; 
}