リストと再帰の演習
リストは長さが変化するつながったデータ構造のため、決まった回数を繰り返す for 文より、再帰や while のほうが処理の相性がよい。このため再帰で扱うことも多い。
再帰によるリストの表示は、
リストが終わりかどうか調べ終わりなら関数を抜ける
今注目しているノードのデータを表示する
次以降のリストを、この関数を使って表示する
という手順で実現できる。
code: listrecursive1.c
void list_disp(Node *l){
if(l == NULL) return;
printf("%d\n", l->data);
list_disp(l->next);
}
リストの先頭のデータを表示をし printf("%d\n", l->data)
残りのリストを表示すればよい list_disp(l->next)
関数が呼ばれたときに、リストがつながっていない（終わっている）ことを l == NULL でチェックしている。
再帰によるリストの表示を使うと、逆順で表示することも簡単に記述できる。
リストが終わりかどうか調べ終わりなら関数を抜ける
次以降のリストを、この関数を使って表示してから
今注目しているノードのデータを表示する
という手順で実現できる。
code: listrecursive2.c
void list_disp(Node *l){
if(l == NULL) return;
list_disp(l->next);
printf("%d\n", l->data);
}
ノードの検索(search)も再帰的に書ける
リストが終わりなら見つからなかったので NULL を返す
注目しているノード（の次）が目的のノードなら、ポインタを返す
次以降のリストについて、この関数で検索した結果を返す
とすればよいので listrecursive3.c のようになる。
code:listrecursive3.c
Node * node_search(Node *list, int data){
if(list->next == NULL) return NULL;
if(list->next->data == data) return list;
return node_search(list->next, data);
}
注目しているノード自体(list)でなく、注目しているノードの次 (list->next) を返すのは、ノードの削除に対応するため。
クイズ
1から10が順につながったリストを想定して、data として5を検索するときの動作の様子を、机上で追いかけてみよう
演習
1)1から10の数字をリストとして持って、最後のノード(10)へのポインタを返す関数を再帰で書いてみよう。これはリストのつなぎかえで半分ずつ交換するときに必要となる。 考え方は次の３つである
もしも最後のノードがなければNULLを返す（どんな状況だろうか）
最後のノードならそのポインタを返す
次以降のリストの最後のノードへのポインタを、この関数を使いみつけて返す