アルゴリズムとデータ構造
演習第 2 回
リスト

リスト(アルゴリズムC 第1巻 p.20) についてはプログラミング I でも習いましたが、 もう少し複雑なリストの繋ぎ換えについて扱います。 復習の意味でも、もう一度繋ぎ方を確認してください。

問題1印刷用 PostScript

次のようなリストがある。
head→1→2→3→4→5→tail
このリストに対して、以下のような操作を行なう場合の手順を図示しなさい。 ただし、繋ぎ換える順番に注意すること。

繋ぎ換えるときに一番注意しなければいけないのが、 各ノードはひとつ以上の矢印で差されていなければならない ということです。同じような繋ぎ換えをするにしても、繋ぎ換える順番は重要です。 次の図の失敗例では、1 のノードがどこからも差されなくなってしまったために、 0 から 1 に繋げなくなってしまっています。
繋ぎ換えの注意点

問題1は、次の 4 のノードを先頭(つまり head の次)に移動させる場合の 書き方を参考にして書いてみてください(色は着けなくていいです)。
書き方の例

問題2

リスト中の 2 つのノードを入れ替える関数 exchange を作成しなさい。 ファイルは ex02-skel.c を用いること。 2 つのノードが隣接している場合と、そうでない場合で、 処理を分ける必要があることに注意せよ。

実行例:
% ./a.out
Head - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - Tail

=> exchange(1,2)
Head - 2 - 1 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - Tail
=> exchange(1,2)
Head - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - Tail
=> exchange(4,7)
Head - 1 - 2 - 3 - 7 - 5 - 6 - 4 - 8 - 9 - Tail
=> exchange(4,7)
Head - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - Tail

問題1で見たように、交換するノードが隣接しているときと、そうでないときで、 繋ぎ換え方が違ってきます。まず関数の始めで、交換するノードが隣接しているか どうかをチェックし、それによって処理を換えます。

問題3

リストを逆順に並べ換える関数 reverse を作成しなさい。 ファイルは問題2と同じく ex02-skel.c を用いること。 リスト中のデータが逆順になるならば、どのような方法を用いても良い。 また必要であれば、ファイル中の他の関数を使用しても良い。

実行例:
% ./a.out
Head - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - Tail

=> reverse()
Head - 9 - 8 - 7 - 6 - 5 - 4 - 3 - 2 - 1 - Tail

地道に繋ぎ換えていく場合は、問題1のように、実際にどのように繋ぎ換えれば 良いかを紙に書いて考えてから、関数を作ると良いでしょう。

ちょっとズルいかな、と自分でも思ってしまうような方法でも構いませんが、 その場合は、処理は効率的か、何か問題はないか、などを考えてみてください。


Written by わかまつなおき