0

私はデータ構造とリンクリストを研究していますが、再帰なしでリンクリストのコピーを作成する方法の概念を理解していません。誰かがこれを説明できますか？

4

5 に答える 5

2

単純な反復ロジックの疑似コードは次のようになります。

  1. 元のリストの先頭から開始しorigHeadます。
  2. 元のリストの先頭を指す一時ポインタを設定しますtempNode = origHead。
  3. tempNode=の場合NULL、手順 17 に進みます。
  4. の場合tempNode != origHeadは、手順 10 に進みます。
  5. コピー リストの先頭にメモリを割り当てますcopyListHead。
  6. に設定copyListHead->nextしNULLます。
  7. コピー リストの先頭を指す一時ポインタを設定しますcopyListTempNode = copyListHead。
  8. tempNode = tempNode->next.
  9. 手順 3 に進みます。
  10. ノードにメモリを割り当てますnewCopyNode。
  11. にコピーtempNode->dataしnewCopyNode->dataます。
  12. newCopyNode->nextNULL に設定します。
  13. をポイントcopyListTempNode->nextしnewCopyNodeます。
  14. copyListTempNode = newCopyNode.
  15. tempNode = tempNode->next.
  16. 手順 3 に進みます。
  17. 止まる。
于 2013-03-11T06:12:14.700 に答える
1

Without recursion === using iteration. P-code:

LinkedList *l1 = (the_head), *l2 = copy_node(l1);
for (tmp l1->next; tmp != NULL; tmp = tmp->next, l2 = l2->next) {
    l2->next = copy_node(tmp);
}
于 2013-03-11T05:40:37.177 に答える
1

使い方

  1. 2 つのポインターを宣言します。dst最終的な関数の結果となるポインターと、次のノード割り当てを受け取るポインターのアドレスnextを常に保持するポインター ツー ポインターです。ポインタツーポインタは、最初に のアドレスを保持します。nextdst

  2. 複製するノードがまだある間に ( src != NULL)、次の操作を行います。

    • 新しいノードを割り当て、結果のポインタを に割り当てます*next。
    • ノード データを からsrcにコピーします*next。
    • 割り当てたばかりのメンバーnextのアドレスを保持するように割り当てます。node->nextそのメンバーは を使用して取得でき&(*next)->nextます。
    • 入力ソース ポインタを次のノードに進めます: src = src->next。
    • (2)まで繰り返します。

  3. 終了したら、常に*nextの値NULL。これにより、リストに追加された最後のノードが存在する場合、そのノードNULLのnextポインターが確実に保持されます。リストにノードがまったく追加されていない場合 (たとえば、関数が呼び出されたとき)、代わりに の値が NULL に設定srcされます。これは、現在 に保持されている のアドレスであるためです。NULLdstdstnext

  4. dstの値を関数の結果として返します。

このアルゴリズムのコードを以下に示します。

typedef struct Node
{
    int data;
    struct Node *next;
} Node;

Node* CopyList(const Node* src)
{
    Node *dst = NULL, **next = &dst;
    while (src)
    {
        // allocate new node
        *next = malloc(sizeof(**next));
        if (*next)
        {
            // copy_node() for complex duplication
            (*next)->data = src->data; 

            // reposition our next-link to the address of ptr->next
            //  of the node we just added.
            next = &(*next)->next;

            // and finally, advance the source pointer
            src = src->next;
        }
        else
        {
            perror("Failed to allocate node.");
            exit(EXIT_FAILURE);
        }
    }
    *next = NULL;
    return dst;
}

注: これは、シリアル入力ファイルから順方向リストを作成する良い方法でもあります。これにより、ヘッドが一度だけ初期化され、後続のすべてのノードが常に最後のノードのnextポインターに追加されます。

于 2013-03-11T06:09:27.457 に答える
0

There's no reason to use recursion at all for this -- simple iteration works perfectly well. Copy a node. If the pointer to the next node isn't null, repeat the process for the next node (and set the next link in the node you just copied to point to the next one you copy).

于 2013-03-11T05:40:49.223 に答える
0

リンクされたリストを空のリストにコピーする簡単な方法は、以下のように再帰を使用することです。

struct Node {
    int value;
    Node* next;
};

Node* copy_list(Node* list) {
    if (list == NULL) return NULL;

    Node* result = new Node;
    result->value = list->value;
    result->next = copy_list(list->next);
    return result;
}

ただし、再帰を使用したくない場合は、(node)->next = NULL をチェックとして取得するまで、ループを使用して空でないリストにそれぞれを手動でコピーする必要があります。

于 2013-03-11T05:45:03.397 に答える