next up previous contents
Next: 23. キュー・スタック Up: 22. データ構造 Previous: 3. より高度なリスト

4. 課題 22

cd c を実行した後で( ~/c に移動した後で )、以下の課題を やってみよ。

課題 22.1
片方向リンクトリスト

片方向リストの例(「より柔軟なリスト」を参照)を用いて、 ユーザーが入力した文字列を記憶し、入力終了後それらを順に出力する プログラムを作成せよ。但し、入力の終わりは ^D であると する。

課題 22.2
双方向リンクトリスト

22.1 の課題を改良し、双方向リンクドリストへと変更せよ。 その上で、入力された文字列を逆順に表示するプログラムを作成せよ。

課題 22.3
リストの応用 I

課題 21.3 を改良し、学生データをリストへと格納するように せよ。また、通年成績も学生データ構造に格納するようにせよ。

課題 22.4
リストの応用 II

課題22.3 を改良し、学生データのリストを通年成績の良いもの順に 並べ替えるようにせよ(並べ替え用の関数を作成せよ)。最後に、 成績順に出力するようにせよ。

但し、並べ替えのアルゴリズムには色々なものが考えられるが、ここで は単純に、学生データが登録されたリストをAとすると、別のリストBを作り、 Aのリストの中で成績が最高のものを A から B に移し変えるようにし よう。こうすると、Aからは最高の成績のものがいなくなるので、当然 2番目に成績の良いものが A の中では最高の成績となっているので、 先ほどの手順を繰り返し、A の中の最高の成績のものを B のリストの 末尾に付け加えるようにする。これを繰り返せば自動的にリストB には 成績順に並んだリストが出来ているという訳である。

作成したプログラムをメイルで creport まで送りなさい。題は、kadai22 とする事。

前回の復習
リンクトリスト

割り当てメモリを数珠繋ぎにすることで、不定量のメモリを扱えうことが できる。

    strcut LIST {
        struct LIST *next; /* 次の要素へのポインタ */
        void *data;        /* 実際のデータへのポインタ */
    };

ポインタ next には次のオブジェクトのアドレスを保存する。最後の オブジェクトであるならば、NULL ポインタを代入しておく。

追加挿入

リンクトリストの最後尾へのオブジェクトの追加の場合は、オブジェクトを 割り当てた後、リストの最後尾のオブジェクトの next に割り当てたオブジェクト のアドレスを代入するだけで良いが、リストに新しいオブジェクトを挿入する 場合には、挿入する前のオブジェクトの next ポインタと挿入するオブジェクトの next ポインタを変更する必要がある。

削除

リストからのオブジェクトの削除においては、next ポインタの調整をした後に オブジェクトのメモリからの削除を行わなければならない。また、先頭オブジェクト のアドレスの持ち方によっては、先頭への挿入や削除の場合のみ特別な操作が 必要になる場合がある。

応用

リストの応用として、双方向(前後)のポインタを持たせる場合や、 更にその応用として先頭と末尾のポインタを繋げてリング状にするなどの場合 がある。



Noriyo Kanayama