リスト(アルゴリズムC 第1巻 p.20) についてはプログラミング I でも習いましたが、 もう少し複雑なリストの繋ぎ換えについて扱います。 復習の意味でも、もう一度繋ぎ方を確認してください。
次のようなリストがある。
このリストに対して、以下のような操作を行なう場合の手順を図示しなさい。
ただし、繋ぎ換える順番に注意すること。
繋ぎ換えるときに一番注意しなければいけないのが、
各ノードはひとつ以上の矢印で差されていなければならない
ということです。同じような繋ぎ換えをするにしても、繋ぎ換える順番は重要です。
次の図の失敗例では、1 のノードがどこからも差されなくなってしまったために、
0 から 1 に繋げなくなってしまっています。
問題1は、次の 4 のノードを先頭(つまり head の次)に移動させる場合の
書き方を参考にして書いてみてください(色は着けなくていいです)。
リスト中の 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で見たように、交換するノードが隣接しているときと、そうでないときで、 繋ぎ換え方が違ってきます。まず関数の始めで、交換するノードが隣接しているか どうかをチェックし、それによって処理を換えます。
リストを逆順に並べ換える関数 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のように、実際にどのように繋ぎ換えれば 良いかを紙に書いて考えてから、関数を作ると良いでしょう。
ちょっとズルいかな、と自分でも思ってしまうような方法でも構いませんが、 その場合は、処理は効率的か、何か問題はないか、などを考えてみてください。