C++ Linked Listのコピーをクラスオブジェクトとして作成するにはどうすればよいですか？

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

言われているので、あなたがLinkedListにNode *tailメンバーを追加する場合、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*パラメータを追加することを検討10代わりに：

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を2番目のリストの渡した参照と比較してください。同じでない場合は、リスト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

私はこれに戻ることができる前にここに入っているように見えます。私が加えることができるのは、少しタイトで、もう少し混乱しているのは、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; 
}