前期期末試験までの授業予定( 7/10 リスト追加+課題, 7/17 stackとque+課題 7/24 リストで集合計算 )
最初のリスト生成の説明では、補助関数 cons を用いて、直接リストを生成していた。
しかし、実際にはデータを入力しながらの処理となるであろう。
最も単純なリスト挿入
struct List* top = NULL ; int main() { int x ; while( scanf( "%d" , &x ) == 1 ) { top = cons( x , top ) ; } print( top ) ; // 前回示したリスト全要素表示 return 0 ; }
ここで示したコードは、新しい要素を先頭に挿入していく処理となる。このため、作られたリストは、与えられた要素順とは逆順となる。この方法は、リストを管理するポインタが1つで分かりやすい。
要素を末尾に追加
前に示した方法は、逆順になるので、与えられた要素が末尾に追加する方法を示す。
struct List* top = NULL ; struct List** tail = &top ; int main() { int x ; while( scanf( "%d" , &x ) == 1 ) { *tail = cons( x , NULL ) ; tail = &((*tail)->next) ; } print( top ) ; // 前回示したリスト全要素表示 return 0 ; }
この方法は、次回にデータを追加する場所(末尾だからNULLが入っている)を覚える方式である。ただし、リストへのポインタのポインタを使う方法なので、少しプログラムがわかりづらいかもしれない。
理解の確認のために、末尾のポインタを動かす部分の式を、型で解説すると以下のようになる。
途中でデータ挿入・データ削除
リスト構造の特徴は、途中にデータを入れたり、途中のデータを抜くのが簡単にできる所。そのプログラムは以下のようになるだろう。
void insert( struct List*p , int data ) { // あえて、補助関数consを使わずに書いてみる struct List* n ; n = (struct List*)malloc( sizeof( struct List ) ) ; ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(A) if ( n != NULL ) { n->data = data ; ~~~~(B) n->next = p->next ; ~~~~~~~(C) p->next = n ; } // consを使って書けば、簡単 // p->next = cons( data , p->next ) ; }
void remove_after( struct List* p ) { struct List* del = p->next ; p->next = del->next ; free( del ) ; }
理解度確認
上記プログラムinsert() の中の、下線部(A),(B),(C)の型は何か答えよ。
レポート課題
以下に示すようなデータを扱うリスト構造を作り、そのリストを扱うプログラムを作成せよ。
( 出席番号 % 3 ) + 1 の番号の課題に取り組むこと。
- 緯度(latitude)経度(longitude)とその場所の都市名(city)
- 名前(name)と誕生日(month,day)(1つの変数に2月7日を0207のように保存するのは禁止)
- 複素数(re,im)
このようなプログラムを作るのであれば、以下の例を参考に。
struct NameAgeList { char name[ 20 ] ; // 名前 int age ; // 年齢 struct NameAgeList* next ; // 次のデータへのポインタ } ; struct NameAgeList* na_cons( char* nm, int ag, struct NameAgeList*p ) { struct NameAgeList* ans ; ans = (struct NameAgeList*)malloc( sizeof( struct NameAgeList ) ) ; if ( ans != NULL ) { strcpy( ans->name , nm ) ; ans->age = ag ; ans->next = p ; } return ans ; }