テスト返却にて、嫌味も織り交ぜながらの解説の後、 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)と呼ぶ。