第8回 リスト操作２（6月9日）

今日の課題

• カーソル版 線型リスト

■ カーソル版 線型リスト

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

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

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

データ構造

個々のノードについて

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

リスト全体について

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

定数

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

操作のサブルーチン

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

■ 動作の様子

初期状態

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

push操作の様子

pop操作の様子

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

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

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

□ 宿題（小レポート）

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

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

2006.6.6 by tokuhisa