テスト返却にて、嫌味も織り交ぜながらの解説の後、 30分ほど時間があったので、次のステップ。

リストへの追加

前回までの授業では、リストは直接記述していたが、 データを読み取りながらのリスト生成を説明する。

まずは基本ということで、リストの先頭挿入。 ただし、データの入力順序とは逆になってしまう。

struct List* top = NULL ;
int x ;
while( scant( "%d" , &x ) == 1 ) {
top = cons( x , top ) ;
}

この欠点の修正ということで、末尾追加型を示す。 Listへのポインタのポインタがわかりづらいけど…

struct List* top = NULL ;
struct List** tail = &top ;
while( scant( "%d" , &x ) == 1 ) {
*tail = cons( x , NULL ) ;
tail = &((*tail)->next) ;
}

ポインタのポインタは分かりづらいので、改めて式の一部分が 型でどうなっているのかを示す。

リストへの途中挿入

リストが使われる利点は、データの途中挿入。 以下のプログラムは、昇順に並んでいるデータの、適切な場所にデータを 途中挿入するプログラム。 一つ前のnext部を変更する必要があるため、 ひとまずは分かりやすいプログラムということで、p->next でループを回す。 本当は、List**を使いたいんだけどね…

void insert( struct List *p , int x ) {
for( ; p->next != NULL ; p = p->next ) {
if ( p->next->data > x ) {
p->next = cons( x , p->next ) ;
break ;
}
}
}

ただし、このプログラムは、データの先頭や末尾への追加は正しく動かない。 このためよく用いられるテクニックは、先頭と末尾に本来なら使わないダミーデータを 入れておき、先頭末尾の特別処理を書かずにすませる方法をとる。 このような方法を番兵(sentinel)と呼ぶ。