テストを返却した後、前回の授業の続き。 リストの生成と挿入削除について説明を行う。

// 前回の授業で説明した時のコード
struct List {
int  data ;
struct List* next ;
} ;
struct List* cons( int x , struct List* n ) {
struct List* ans ;
ans = (struct List*)malloc( sizeof( struct List ) ) ;
if ( ans != NULL ) {
ans->data = x ;
ans->next = n ;
}
return ans ;
}

リストの入力と追加

top = cons(1,cons(2,…)) といった方法では、動作確認の時にしか使えない。 実際にデータを入力しながら、リストに保存するプログラムを考える。 前述の cons() の補助関数を使えば、簡単に記載ができる。

struct List* top = NULL ;
int x ;
while( scanf( "%d" , &x ) == 1 ) {
top = cons( x , top ) ;
}
// 11,22,33の順でデータを与えると、
//   top[◯]→[33|◯]→[22|◯]→[11|×]

しかし、この方法では、データを11,22,33の順序で与えても、 生成されるリストは、逆順となってしまう。

そこで、リストの末尾を覚えるポインタを作っておいて、 下記のように記述すれば良い。

struct List* top = NULL ;
struct List** tail = &top ;
int x ;
while( scanf( "%d" , &x ) == 1 ) {
*tail = cons( x , NULL ) ;
tail = &( (*tail)->next ) ;
}
// 11,22,33の順でデータを与えると、
//   top[◯]→[11|◯]→[22|◯]→[33|×]

リストへの挿入・削除

リスト処理の良い点は、必要に応じてメモリを確保していくため、 配列の容量オーバーといった問題を気にしなくて良い所。 一方、配列で途中にデータを挿入する場合、 挿入場所を作るために後続のデータを１つ後ろにずらす処理が必要となる。 また、配列の途中のデータを抜く場合、 後続データを１つ前にずらす処理が必要となる。 でも、リスト構造であれば、ポインタの繋ぎ変えだけで済む。

// 挿入
// ポインタpには、挿入したい場所の直前のセルの場所。
void insert( struct List* p , int x ) {
p->next = cons( x , p->next ) ;
}
// 削除
void delete( struct List* p ) {
struct List* d = p->next ;
p->next = p->next->next ;
free( d ) ;
}