next up previous contents
Next: 22. 記憶クラスとモジュール Up: 21. データ構造 Previous: 3. より高度なリスト

4. 課題 21

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

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

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

課題 21.2
双方向リンクドリスト

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

課題 21.3
リンクドリストの応用 I

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

課題 21.4
リンクドリストの応用 II

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

但し、並べ替えにおいては、リストの挿入・削除を用いるようにする こと。

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

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

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

    strcut LIST {
        struct *next;
        struct *data;
    };

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

追加挿入

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

削除

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

応用

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



Noriyo Kanayama 平成14年11月26日