リスト構造の生成。テスト直しの後に実施した説明が抜けているので、 リストの生成と処理の部分も含めて2週分を記載。

リスト生成の基礎

リスト構造のイメージを分かってもらうために、面倒だけど データ生成を単調に書いた例。

struct List {
int data ;
struct List* next ;
} ;
// 最初は単純に...
// malloc失敗チェックは省略
struct List* top ;
top = (struct List*)malloc( sizeof( struct List ) ) ;
top->data = 1 ;
top->next = (struct List*)malloc( sizeof( struct List ) ) ;
top->next->data = 2 ;
top->next->next = NULL ;

さすがに面倒なので、補助関数を使う。

// 補助関数を使って
struct List* cons( int x , struct List* n ) {
struct List* ans =
(struct List*)malloc( sizeof( struct List ) ) ;
if ( ans != NULL ) {
ans->data = x ;
ans->next = n ;
}
return ans ;
}
struct List* top = cons( 1 , cons( 2 , NULL ) ) ;

リストを使った簡単な処理

リストの末端には、これ以上データが続いていないことを表すNULLが入っている。

void print( struct List* p ) {
for( ; p != NULL ; p = p->next )
printf( "%d¥n" , p->data ) ;
}
int sum( struct List* p ) {
int s = 0 ;
for( ; p != NULL ; p = p->next )
s += p->data ;
return s ;
}
void main() {
struct List* top = cons( 1, cons( 2, cons( 3, NULL ) ) ) ;
print( top ) ;
printf( "%d¥n" , sum( top ) ) ;
}

リスト構造の応用では、2分木なども説明するので、その説明の導入として、 再帰で同じ処理を書いてみる。

void print( struct List* p ) {
if ( p != NULL ) {
printf( "%d¥n" , p->data ) ;
print( p->next ) ;
}
}
int sum( struct List* p ) {
if ( p == NULL ) {
return 0 ;
} else {
return p->data + sum( p->next ) ;
}
}

入力しながらリストを追加

手作業でリストを生成するような処理では、汎用性が無いので、 データを入力しながらリストを生成してみる。

void main() {
struct List* top = NULL ;
int x ;
while( scanf( "%s" , &x ) == 1 ) {
top = cons( x , top ) ;
}
}

しかし、上記の例では、新しい要素をリストの先頭に挿入する方法なので、 データは入力順序と逆順に保存される。 入力順序と同じように、最後のデータが末尾に入るように書くには、 末尾に挿入するデータの場所を覚えるポインタ(tail)を使って、 以下のように書くことができる。

void main() {
struct List* top = NULL ;
struct List** tail = &top ;
int x ;
while( scanf( "%s" , &x ) == 1 ) {
*tail = cons( x , NULL ) ;
tail = &( (*tail)->next ) ;
}
}