再帰を使用してリンクリストを逆転させるコードスニペットを理解するのに役立つ

Question

私はCでリンクリストを使って試験を勉強しています。このコードスニペットを自分自身に "批評"しました。私の人生のために、私は残りがどのように逆転されたか理解できません。ここは...それはMr.Nick Parlante（StanfordのCIS図書館）のLinked Listの問題です。 私はMr. Nickのコメントに入れます。 RecursiveReverse（）ソリューション

は、おそらく最も難しい部分は RecursiveReverse（&残りは）残りを逆に実際にはない概念を受け入れています。次に、1つのフロントノードをリストの末尾まで取得するためのトリック があります。どのように トリックが動作するかを確認するために図面を作ってください。

void RecursiveReverse(struct node** headRef) { 
struct node* first; 
struct node* rest; 
if (*headRef == NULL) return; // empty list base case 
first = *headRef; // suppose first = {1, 2, 3} 
rest = first->next; // rest = {2, 3} 
if (rest == NULL) return; // empty rest base case 
RecursiveReverse(&rest); // Recursively reverse the smaller {2, 3} case 
         // after: rest = {3, 2} 
first->next->next = first; // put the first elem on the end of the list 
first->next = NULL; // (tricky step -- make a drawing) 
*headRef = rest; // fix the head pointer 

}

私は何が起こっているかを追跡するための試みで無数の図面を作った、と私はちょうどRecursiveRest（&残りは）実際に残りの部分を反転させる方法を理解することはできません。助けてください。私はかなり不満を感じています。私が最終的に得られるのは、より小さな "休息"です。何も逆転しません。 ありがとうございます。

Answer 1

再帰は、基本的な手順にどのように分解されるのかを見るのが難しいため、通常は理解しにくいです。

通常、再帰的な部分は既に完了していると考えられ、組み合わせ手順についての理由はアルゴリズムを設計するときに最も便利です。

あなたは再帰的なアルゴリズムは、あなたが仕事で二つの方法があることを心に留めておく必要がありどのように機能するかを視覚化しようとしている：あなたが終了ケースを見つけるまで

• は小さい問題で元の問題の分解を
• 終了ケースの解答
• 結果の組み合わせ。

これは双方向の通りです。まず、問題を解消しながら、最終ケースまで一方通行します。最後のケースを解決します。その後、部分的な結果を組み合わせながら、最初に戻ります。

あなたの場合は、このようになる可能性があります。 [A-B]はリストを意味することに注意してください。

[A-B-C-D-E] // RecursiveReverse([A, B, C, D, E]) 
(A [B-C-D-E]) // this means we are calling RecursiveReverse([B, C, D, E]) 
(A (B [C-D-E])) // this means we are calling RecursiveReverse([C, D, E]) 
(A (B (C [D-E]))) // this means we are calling RecursiveReverse([D, E]) 
(A (B (C (D [E])))) // this means we are calling RecursiveReverse([E]) 
        // hit the end case and solve it trivially 
(A (B (C (D [E])))) // solved 
(A (B (C [E-D]))) // and go back while applying the combination case 
(A (B [E-D-C])) // combine 
(A [E-D-C-B]) // combine 
[E-D-C-B-A] // combine 

これが役立ちます。それぞれで

Answer 2

1. コードが 現在の次のノード（第一及び 残り）を覚えてステップ。
2. 再帰的逆転（&休憩） が機能し、残りのリストを逆転させると仮定します。
3. 次に、残りのノードは、コールが返るときに最後の位置 になります。 最後の コードを3行チェックするだけです。
4. 残りは ポイントに変更され、最初に NULL（first-> next = NULL）を指しています。すなわち最初に最後に移動します リストの