# 先週の講義のメモが残してないので、1週遅れで記載。
前回の説明では、リストを処理で手作業で作っていたが、 データの入力に合わせて追加して区処理を説明する。
先頭挿入型の追加処理
配列でデータを扱えば、C言語では固定サイズになるため、リスト構造を使えば不定長の データの取り扱いも楽。
struct List { int data ; struct List* next ; } ; struct List* cons( int x , struct List* n ) { struct List* ans ; if ( (ans = (struct List*)malloc( sizeof(struct List ))) != NULL ) { ans->data = x ; ans->next = n ; } return ans ; } void main() { struct List* top = NULL ; int x ; while( scanf( "%d" , &x ) == 1 ) { top = cons( x , top ) ; } }
このプログラムでは、リストの先頭に次々とデータを挿入していく。 このためデータは、挿入順と逆に並ぶことになる。
末尾追加型の追加処理
前の例では、管理するためのポインタがtopだけで良いため、シンプルではあるが、 データが逆順になってしまう。データの挿入順に並びたいのであれば、以下のような プログラムとなる。
void main() { struct List* top = NULL ; struct List** tail = &top ; int x ; while( scanf( "%d" , &x ) == 1 ) { *tail = cons( x , NULL ) ; tail = &( (*tail)->next ) ; } }
しかしこのプログラムでは、tail の宣言が『Listへのポインタのポインタ』といった宣言で、 必ずしも読みやすいものではない。しかし、式の部分的な型が何なのかを明確に 理解できれば、イメージ図があれば、それなりに理解もできるようになるはず。
// ややこしい部分の型を考える。 &( (*tail)->next ) の型は? tail : List** *tail : List* (List**の先を参照) (*tail)->next : List* (List*の先のnext部を参照) &( (*tail)->next ) : List** (next部のアドレスを取り出す)