リスト処理の応用として、集合演算について説明を行う。 今日は、わざと間違ったプログラムを書いて、どう変なのかを色々と聞いてみた。
まずは、集合演算を簡単にするための補助プログラム。 間違っている所をなぜ?と聞いたけど、反応が悪かったかな….
(( リストから特定データを探す/間違ったプログラム )) int find( struct List* p , int x ) { for( ; p != NULL ; p = p->next ) { if ( p->data == x ) return 1 ; else return 0 ; } } (( リストから特定データを探す )) int find( struct List* p , int x ) { for( ; p != NULL ; p = p->next ) if ( p->data == x ) return 1 ; return 0 ; }
次に、実際に集合演算A∩Bの計算例。これも、findを使わなかったら…という例を書いて 考えてもらった。徐々に自分で考えて、○○がダメじゃ?といった意見が飛び交うようになってきた。
(( リストの集合積/正しい例 )) struct List* list_and( struct List*p1 , struct List*p2 ) { struct List* ans = NULL ; for( ; p2 != NULL ; p2 = p2->next ) { if ( find( p1 , p2->data ) ) ans = cons( p2->data , ans ) ; } return ans ; } (( リストの集合積/findを使わずに間違った場合 )) struct List* list_and( struct List*p1 , struct List*p2 ) { struct List* ans = NULL ; for( ; p2 != NULL ; p2 = p2->next ) { for( ; p1 != NULL ; p1 = p1->next ) { if ( p1->data == p2->data ) ans = cons( p2->data , ans ) ; } } return ans ; }
最後にリスト処理で作られたデータを捨てる処理。
(( リスト全部を捨てる/安易に書いたダメな例 )) void list_free( struct List* p ) { for( ; p != NULL ; p = p->next ) free( p ) ; } (( リスト全部を捨てる )) void list_free( struct List* p ) { struct List* d ; while( p != NULL ) { d = p ; p = p->next ; free( d ) ; } }
ダメな例とかを説明していたら、再帰でかけるんじゃ?みたいな意見を言う人がいたので、 実際に説明する。 「親亀こけたら子亀もこける。親亀が自殺するときゃ、子亀を確実に殺してから死にましょう」 と説明したら、その倫理観はやばいよね~みたいに受けた。説明用の倫理観は別な話。
(( 自分が死ぬ前に、尻尾は先に殺しましょう )) void list_free( struct List* p ) { if ( p != NULL ) { list_free( p->next ) ; free( p ) ; } }