第7回 リスト操作（6月2日）

今日の課題

• カーソル版 線型リスト

■ カーソル版 線型リスト

線型リストを配列変数で実現する方法。

メリットは、「メモリ確保の時間がかからない」、「メモリ使用量が明確」、「ファイルへの保存とファイルからの読み込みが簡単」である。デメリットは、「データ数の上限を動的に変更できない」である。

ヘッダファイル cursorlist.h 　　ソースファイル cursorlist.c

データ構造

個々のノードについて

• データ data
• 次ノードへのインデックス（ポインタ） next

リスト全体について

• ノードの配列 nodes
• 配列の大きさ max
• 配列の空き部分の先頭を表すインデックス free
• 配列の格納部分の先頭を表すインデックス head（ダミーヘッド）

定数

EOL ： Next がこれ以上辿れないことを表す。

操作のサブルーチン

• リスト全体の準備
• ノードの表示 / リストの表示 / リスト全体のダンプ
• ヘッドの準備
• push操作 / pop操作 / remove操作

■ 動作の様子

初期状態

ヘッドの準備（Dataに値を持たないダミーノード）

push操作の様子

pop操作の様子

remove操作の様子（指定したデータを持つノードの削除）

※ NEXT の値は、0 以上の整数である。unsigned long int を使うことで、非常に大きなメモリ空間を扱うことができる。したがって、Index = 0 のところは使用できない。

■ 表示のアルゴリズム (clist_print_list)

1. インデックス i を head のノードとする。
2. もし、i が EOL ならば return
3. i のノードの次のノードに i を移す。
4. i が終端（EOL）でないならば以下を実行する。
5. i の指すノードのデータを表示する。

□ 宿題（小レポート）

cursorlist.c は、重要なコードの並びかたをぐちゃぐちゃにしている。 正しく動作するように、並び換えよう。

小レポートには、手書きでコメントを書きこんだ cursorlist.c のソース コード、および、list0701.c の実行結果 を記載せよ。

2008.5.25 by tokuhisa