ホーム » スタッフ » 斉藤徹 » リスト処理と集合演算

2010年7月
« 6月   8月 »
 123
45678910
11121314151617
18192021222324
25262728293031

最近の投稿(電子情報)

アーカイブ

カテゴリー

リスト処理と集合演算

リスト処理の応用として、集合演算について説明を行う。 今日は、わざと間違ったプログラムを書いて、どう変なのかを色々と聞いてみた。

まずは、集合演算を簡単にするための補助プログラム。 間違っている所をなぜ?と聞いたけど、反応が悪かったかな….

(( リストから特定データを探す/間違ったプログラム ))
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 ) ;
}
}