第９回 リスト操作２（6月16日）

今日の課題

• カーソル版 線型リスト

■ カーソル版 線型リスト

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

メリットは、「メモリ確保の時間がかからない」、「メモリ使用量が明確」である。

デメリットは、「データ数の上限を動的に変更できない」である。

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

■ データ構造

ノード

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

リスト

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

初期状態

格納部分と空き部分の様子

■ 表示のアルゴリズム

1. インデックスを head の指すノードとする。
2. インデックスが終端（EOL）を指さない限り以下を実行する。
3. インデックスの指すノードのデータを表示する。
4. インデックスの指すノードの次のノードにインデックスを移す。

■ push アルゴリズム

1. free から空きノードを得る。（free の指す所が変わる）
2. head の先頭に空きノードを付ける。

■ remove アルゴリズム

1. 先頭を除去する場合

   

2. 途中を除去する場合

   

□ 課題1

list0901.c の実行結果をプリントアウトし、動作の説明を書き込め。

⇒ list0901.c 、 ⇒ Makefile

□ 課題2

list0902.c、および、list0903.c は、リストのデータをセーブしたりロードしたりする。セーブファイルはtmp1である。Makefile を完成させて、動作を確認せよ。

⇒ list0902.c 、 ⇒ list0903.c

□ 課題3

本プリントで説明したリスト構造では、ダミーノードを使用していない。そのため、remove の際、場合分けを要した。そこで、ダミーノードを使用するタイプのカーソル型リストのライブラリを作成せよ。そして、list0901.c、list0902.c、list0903.c は変更することなく動作することを確認せよ。

ヒント：cursorlist.h は次の部分が変更点である。

typedef struct {
  int max;              // ノードの配列のサイズ
  Node *nodes;          // ノードの配列の先頭、0番目はダミーノード
  Index free;           // 追加可能個所のリストの先頭
} List;

UNIX の上手な使い方：シンボリックリンク（ソフトリンクともいう）

2つのバージョンの cursorlist.h と cursorlist.c を使うことになる。同じディレクトリに同一の名前のファイルは2つ存在できないので、ファイル名を変更するしかない。しかし、list0901.c や Makefile のファイル名を変更するのは面倒である。

そこで、シンボリックリンクを使うと便利である。シンボリックリンクは、1つのファイルに対して複数のファイル名を与えるものである。Windowsでのショートカットと同じ働きをする。（詳しくは、man ln を実行してマニュアルを読もう。）

具体的には、まず、ダミーノードを使用しないプログラムのファイル名を cursorlist1.c、cursorlist1.h に変更し、ダミーノードを使用するプログラムのファイル名を cursorlist2.c、cursorlist2.h とする。

次に、ダミーノードを使用しないプログラムをコンパイルするときは、以下のようにする。

1. rm cursorlist.?
2. ln -s cursorlist1.c cursorlist.c
3. ln -s cursorlist1.h cursorlist.h

■ 宿題

課題1の説明付き実行結果、および、課題2のコンパイルに使った Makefile を提出せよ。

課題3については、cursorlist2.c および cursorlist2.h をプリントアウトして、変更個所に下線を引く。そして、ダミーノードを使用するメリットを述べよ。

2005.6.15 by tokuhisa