ポインターとデータ構造

データ構造

例：算術式

a * b + c * d - e
-> (((a,*,b),+,(c,*,d)),-,e)

基本構造は (x,y,z) y は演算子、x,z は被演算数。 struct 風に書くと、

struct Enzan {
	Hi_enzan_suu x;
	Enzan_shi    y;
	Hi_enzan_suu z;
};

これを計算の手順と考える。次の例では、同じ計算が出てくる。

a * b + a * b * c
-> ((a,*,b),+,((a,*,b),*,c)))

同じ物が２度以上出てくることを考え、算術式に名前づけをおこなう。

(A,(B,a,*,b),+,(C,B,*,c))

この場合構造は(n,x,y,z)で n はこの部分算術式につけられた名前。 struct 風に書くと、

struct Enzan {
	struct Enzan *n;
	Hi_Enzan_suu  x;
	Enzan_shi     y;
	Hi_Enzan_suu  z;
};

長さが不定なデータ構造(例えば誕生日を入れた名簿)を作ることを考える。再帰的な型定義が使える場合、

struct s {
	struct a {
		int year,month,day;
		char name[40];
	} birthday;
	struct s next;
};

のようにすると、「たくさんの」誕生日と名前を連ねることができる。が、この構造の終わりを定義できない。ここで、next を次の名簿の「名前」とすると、構造自体は完結することができる。この「名前」をポインタと呼ぶ。

struct s {
	struct a {
		int year,month,day;
		char name[40];
	} birthday;
	struct s *next;
};

Ｃ言語におけるポインタ関係の演算には以下のようなものがある。

線形リスト(linear list)は「次のデータへのポインタ」を構造体のメンバとしてもっている。普通、最後のデータであることを示すためには NULL ポインタ(nil)が使われる。線形リストを使ったスタック(LIFO バッファ)のプログラム例を示す。

プログラム例１
 プログラム例２

双方向リストは、前方への探索とともに後方への探索もできるように、前後２つのリストへのポインタを持っている。次のプログラムは双方向リストを使った待ち行列(Queue, FIFO バッファ)の例である。

プログラム例3

このプログラムで空の待ち行列は下図のように表される。

ここで、待ち行列にデータが入ると、新しいリストを作成し、ポインタを以下のように書き換える。

待ち行列からのデータの取り出しは、以下のように右端のリストから行われる。データを取り出して不要になったリストは free()によって削除される。

上のスタックのプログラム例では、スタックが空の時に pop()したときのエラーチェックを行っていない。エラーを検出して端末に出力し終了するようにプログラムを書き換えよ。
一般にはリスト構造を使わずに十分な配列を用意することで、スタックを実現することが多い。この方法でプログラムを作成せよ。
Ｃ言語の main関数を、
main(int argc, char **argv)
で呼び出すとコマンドラインからの引数を渡すことができる。ここで、argc は引数の数であり、argv は引数の文字列(ポインタ)へのポインタである。引数を表示するプログラムを作りなさい。