3

RobertSedwickによるAlgorithmsの本でリストトラバーサルについて読んでいます。関数の定義を以下に示します。トラバースおよび削除関数は反復カウンターパートを持つことができますが、traverseRは持つことができないと述べられています。なぜtraverseRは反復的なカウンターパートを持つことができないのですか？再帰呼び出しが機能の終わりではない場合、つまりトラバースの場合のように、反復することはできません。私の理解は正しいですか？

お手数をおかけしますが、よろしくお願いいたします。

void traverse(link h, void visit(link))
  { 
    if (h == 0) return;
    visit(h); 
    traverse(h->next, visit);
  }
void traverseR(link h, void visit(link))
  { 
    if (h == 0) return;
    traverseR(h->next, visit);
    visit(h); 
  }
void remove(link& x, Item v)
  { 
    while (x != 0 && x->item == v) 
      { link t = x; x = x->next; delete t; }
    if (x != 0) remove(x->next, v); 
  }
4

6 に答える 6

5

traverseRコールスタックを使用して、リストのすべてのノードへのポインタを格納します。これにより、コールスタックがほどけるときに、逆の順序でアクセスできるようになります。

呼び出しスタックなしで（つまり非再帰的に）これを行うには、これらのポインターをに格納するための他のスタックのようなデータ構造が必要になります。

他の関数は、現在のノードで機能して先に進むだけで、再帰関数呼び出しが戻った後に使用するために何も保存する必要はありません。これは、末尾再帰をループに置き換えることができることを意味します（コードを変更するか、コンパイラーによっては、それが可能であると判断して変換自体を行うことによって）。

于 2012-09-04T13:08:21.643 に答える
4

リストが単一リンクであると仮定すると、ノードから前のノードへのポインターがないため、逆の順序でリストに繰り返しアクセスすることはできません。

の再帰的実装がtraverseR本質的に行うことは、リストを暗黙的に逆にして、順方向にリストにアクセスすることです。

于 2012-09-04T13:06:23.037 に答える
1

スタックを使用する反復バージョンを作成できtraverseRます。ループ内で、あるノードから別のノードに反復し、スタック上のノードをプッシュします。リストの最後に到達したら、別のループで、アクセスしたノードをポップしてアクセスします。

しかし、彼は基本的に再帰バージョンが行うことです。

于 2012-09-04T13:09:30.910 に答える
1

O（1）の余分なスペースだけで、つまり以前にアクセスしたノードのスタックなしで、単一リンクリストを逆の順序でトラバースすることができます。ただし、これは少し注意が必要であり、スレッドセーフではありません。

これの秘訣は、リストを最初から最後までトラバースし、そのように所定の位置で反転してから、最初に戻ってトラバースし、途中で再び反転することです。

これはリンクリストであるため、元の場所に戻すのはかなり簡単です。ノードに到達したら、そのnextポインタの現在の値を保存し、リスト内の前のノードのアドレスで上書きします（詳細についてはコードを参照してください）。 ）：：

void traverseR(node *list, void (*visit)(node *)) { 
    node *prev = nullptr;
    node *curr = list;
    node *next;

    if (!curr)
        return;

    // Traverse forwards, reversing list in-place as we go.
    do {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    } while (curr->next);

    // fix up so we have a fully reversed list
    curr->next = prev;
    prev = nullptr;

    // Traverse the reversed list, visiting each node and reversing again
    do { 
        visit(curr);
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    } while (curr->next);
}

リンクリストを扱うほとんどすべてのものと同様に、私は（少なくともIMO）それらはほとんど常に純粋な知的演習として扱われるべきであると付け加える義務があると感じています。それらを実際のコードで使用すると、通常は純損失になります。通常、コードは遅く、壊れやすく、理解しにくいだけでなく、通常はかなりのメモリを浪費します（各ノードに格納するデータがかなり大きい場合を除いて、ポインタはデータと同じ量のスペースを使用することがよくあります）自体）。

于 2012-09-04T15:00:50.660 に答える
0

なぜtraverseRは反復的なカウンターパートを持つことができないのですか？再帰呼び出しが機能の終わりではない場合、つまりトラバースの場合のように、反復することはできません。私の理解は正しいですか？

正しい。関数traverseとremoveは、それ自体の呼び出しで終了します。それらは末尾再帰関数です。それ自体への呼び出しtraverseRは、関数の終わりではありません。traverseR末尾再帰ではありません。

一般に、再帰には、スタックフレームを作成し、後で破棄するという費用がかかります。この費用は、再帰を反復に変更することにより、末尾再帰関数を使用して完全に回避できます。ほとんどのコンパイラは末尾再帰関数を認識し、再帰を反復に変換します。

于 2012-09-04T13:23:56.297 に答える
0

traverseR反復の意味に応じて、の反復バージョンを作成することができます。リストを1回トラバースするように制限されている場合、それは不可能です。しかし、多くの処理時間を犠牲にすることができれば、それを行うことができます。従来の速度とメモリのトレードオフでは、使用するメモリが少なくなります。

void traverseRI(link h, void visit(link))
{
    if (h == 0) return;

    link last = 0;

    while (last != h)
    {
        link test = h;
        while (test->next != last)
        {
            test = test->next;
        }

        visit(test);
        last = test;
    }
}
于 2012-09-04T13:59:11.597 に答える