見出し画像

（答案提出）C言語教室 第21回 - 循環リスト（設計編）

Akio van der Meer

単方向リストの答案を提出し、双方向リストの答案も提出した私としては、「もうリストについてはそれなりに制覇したかな」なんて生意気になっていたら、諸先輩方からツッコミの嵐を受けて、自分の未熟さを改めて思い知る。

でもこれが楽しい。ツッコミをいただくと視野が広がるのがわかる。
これだからC言語教室は辞められない。

今回もどうぞ宜しくお願いします。

課題

番兵ノードを用い循環リストで実装した双方向リストを使って、以下のリスト処理を行う関数を書きなさい。

1. リストの先頭に要素を追加する。
2. リストの最後に要素を追加する。
3. リストの先頭の要素を削除する。
4. リストの最後の要素を削除する。

https://note.com/kazushinakamura/n/n6b9e768054cd?magazine_key=m07bb4da8df3e

答案作成上のポイント整理

あれ？循環リストなら、『リストの先頭に要素を追加する』のも『リストの最後に要素を追加する』のも一緒じゃね？？？

、、、ああそうか、最初と最後の間に番兵がいるわ。
（そういう意味ですよね？）

双方向リストという指示ですが、最初と最後がわかりやすいように単方向の矢印をつけました。


1. リストの先頭に要素を追加する

  1. 新たにノード(N-new)を生成

  2. N-newに値をセットする

  3. 番兵nodeの次のnode(N-next)を取得する（N-nextが存在しなかった場合は、番兵node自身となる）

  4. 番兵node->nextに、N-newをセットする

  5. N-new->prevに、番兵nodeをセットする

  6. N-new->nextに、N-nextをセットする（N-nextが存在しなかった場合は、番兵nodeをセットすることになる）

  7. N-next->prevに、N-newをセットする（N-nextが存在しなかった場合は、番兵nodeにセットすることになる）


2. リストの最後に要素を追加する。

  1. 新たにノード(N-new)を生成

  2. N-newに値をセットする

  3. 番兵nodeの前のnode(N-prev)を取得する（N-prevが存在しなかった場合は、番兵node自身となる）

  4. 番兵node->prevに、N-newをセットする

  5. N-new->nextに、番兵nodeをセットする

  6. N-new->prevに、N-prevをセットする（N-prevが存在しなかった場合は、番兵nodeをセットすることになる）

  7. N-prev->nextに、N-newをセットする（N-prevが存在しなかった場合は、番兵nodeにセットすることになる）


3. リストの先頭の要素を削除する。

  1. 番兵nodeの次のnode(N-del)を取得する

  2. N-delが存在しなかった場合（N-del == 番兵node）は、-1を返して削除処理を終了する

  3. N-delの次のnode(N-next)を取得する（N-nextが存在しなかった場合は、番兵nodeをセットすることになる）

  4. 番兵node->nextに、N-nextをセットする

  5. N-next->prevに、番兵nodeをセットする

  6. N-delを解放する


4. リストの最後の要素を削除する。

  1. 番兵nodeの前のnode(N-del)を取得する

  2. N-delが存在しなかった場合（N-del == 番兵node）は、−1を返して削除処理を終了する

  3. N-delの前のnode(N-prev)を取得する（N-prevが存在しなかった場合は、番兵nodeをセットすることになる）

  4. 番兵node->prevに、N-prevをセットする

  5. N-prev->nextに、番兵nodeをセットする

  6. N-delを解放する


演習

1. リストに引き数で渡した値を持つノードのアドレスを返す関数を書きなさい。

2. リストに含まれるノードへのポインタと値を引き数とし、渡したノードの位置に渡した値のノードを挿入する関数を書きなさい。その結果、渡したノードは挿入したノードの次のノードとなります。

3. リストに含まれるノードへのポインタを渡して、そのノードをリストから削除する関数を書きなさい。なお番兵ノードを渡した場合は削除してはいけません。

https://note.com/kazushinakamura/n/n6b9e768054cd?magazine_key=m07bb4da8df3e

1. リストに引き数で渡した値を持つノードのアドレスを返す関数

  1. 番兵nodeから順にnodeを参照し、引数で渡した値をもつnodeを検索する

  2. 見つかった場合、そのnodeへのポインタをリストにセットして終了

  3. 見つかるより先に番兵nodeに戻った場合は、検索失敗として-1を返す


2. リストに含まれるノードへのポインタと値を引き数とし、渡したノードの位置に渡した値のノードを挿入する関数

その結果、渡したノードは挿入したノードの次のノードとなります。

  1. 新たにノード(N-new)を生成

  2. N-newに値をセットする

  3. 引数のポインタが指すnode(N-prev)を取得する

  4. N-Prevの次のnode（N-next)を取得する

  5. N-Prev->nextに、N-newをセットする

  6. N-new->prevに、N-Prevをセットする

  7. N-new->nextに、N-nextをセットする

  8. N-next->prevに、N-newをセットする


3. リストに含まれるノードへのポインタを渡して、そのノードをリストから削除する関数

なお番兵ノードを渡した場合は削除してはいけません。

  1. 引数のポインタが指すnode(N-del)を取得する

  2. N-delが存在しなかった場合（N-del == 番兵node）は、−1を返して削除処理を終了する

  3. N-delの次のnode(N-next)を取得する（N-nextが存在しなかった場合は、番兵nodeをセットすることになる）

  4. N-delの前のnode(N-prev)を取得する（N-prevが存在しなかった場合は、番兵nodeをセットすることになる）

  5. N-prev->nextに、N-nextをセットする

  6. N-next->prevに、N-prevをセットする

  7. N-delを解放する

※ 削除するnodeを指していたリストはN-Prevを指すようにする。


後記

こんな感じかな。

さて、一息ついて、コーディングに入るか。

こうやって考えている間が楽しい。

今日はこれでおしまい。



ここまで読んでいただき、有り難うございました。

これまでの収益は全て、それを必要としておられる方々へ、支援機関を通して寄付させていただきました。この活動は今後も継続したいと思っています。引き続きよろしくお願いいたします。