再帰を使用した2-dリンクリストコピーコンストラクタ

Question

各ノードに右ポインタと下位ポインタがある2-d単一リンクリストを作成しようとしています。私はコピーコンストラクタの実装に多くの問題を抱えていました。なぜなら、再帰が行く方法であると確信しています。再帰ではかなり悪いです。あなたが見ているものを変更する必要はありますか、それとも大丈夫ですか？ここで

はヘッダで宣言です：

typedef int elementType; 
struct node; 
typedef node* nodePtr; 
struct node 
{ 
    elementType elt; 
    nodePtr right = NULL; 
    nodePtr below = NULL; 
}; 

class LinkedList 
{ 
protected: 
    nodePtr head, tail; 
    int size; 
public: 
    LinkedList(); 
    LinkedList(const LinkedList &list); // copy constructor 

    void recursiveCreate(nodePtr ptr); 
} 

これは私のcppファイルでアップフロントの大きなもの

LinkedList::LinkedList(const LinkedList &list) 
{ 
    nodePtr current = NULL; 

    if (list.head == 0) 
     head == 0; 

    else 
    { 
     current = list.head; 
     recursiveCreate(current);  
    } 
} 

void LinkedList::recursiveCreate(nodePtr ptr) 
{ 
    nodePtr n = new node; //create new node 
    n->elt = ptr->elt;  //copy value into that new node 
    n->right = ptr->right; //move right n pointer 
    n->below = n->below; //move right below pointer 
    recursiveCreate(ptr->right); //call on right node 
    recursiveCreate(ptr->below); //call on below node 
} 

Answer 1

です：これは、バイナリツリーではなく、リンクされたリストです。それをリンクされたリストと呼ぶだけで、混乱が起こります。

トピックでは、再帰はリンクされたリストに行く方法ではありません。木の場合、それは可能性があります。しかし、あなたが持っているものは、いくつかの理由でうまくいかない。

1）終了条件はありません。再帰はNULLポインタに移り、悪いことを行います。最初にrecursiveCreateに出て、nodePtrがNULLの場合は終了します。

2）現在のノードを間違ったものを指すように設定しています。たとえば、

n->right = ptr->right; 

は、間違ったリストのノードを指しています。それはほぼ確実な悪い終わりです。 recursiveCreateによって作成されたノードをポイントします。

のは、これが見えるように持っているだろうかを見てみましょう：

nodePtr LinkedList::recursiveCreate(nodePtr ptr) 
{ 
    if (ptr == nullptr) 
    { 
     return nullptr; // source tree stops here 
    } 
    nodePtr n = new node; //create new node 
    n->elt = ptr->elt;  //copy value into that new node 
    n->right = recursiveCreate(ptr->right); //call on right node 
    n->below = recursiveCreate(ptr->below); //call on below node 
    return n; 
} 

と

LinkedList::LinkedList(const LinkedList &list) 
{ 
    nodePtr current = nullptr; 

    if (list.head == nullptr) // NAG!!! For Crom's sake! 0 is not a pointer! 
     head == nullptr;  // Use nullptr and get type checking working for you. 

    else 
    { 
     head = recursiveCreate(list.head);  
    } 
} 

特別ボーナスオペレータ

LinkedList & operator=(LinkedList list) // pass by reference. Copy constructor copies 
             // for you 
{ 
    std::swap(head, list.head); // steal head from copy and give copy the empty 
    return *this; // all done. 
}