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

23.4 課題 23

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

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

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

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

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

課題 23.3
リストの応用 I

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

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

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

割り当てメモリを数珠繋ぎにすることで、不定量のメモリを扱うことが できる。
    strcut LIST {
        struct LIST *next; /* 次の要素へのポインタ */
        void *data;        /* 実際のデータへのポインタ */
    };

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

追加挿入

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

削除

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

応用

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



Noriyo Kanayama