リスト構造は、必要に応じてメモリを確保するデータ構造であり、データ件数に依存しないプログラム が記述できる。その応用として、集合処理を考えてみる。
2進数を用いた集合計算
リストによる集合の前に、もっと簡単な集合処理を考える。 データ件数の上限が少ない場合には、2進数を用いるとC言語のビット演算命令で 和集合、積集合が考えられるので、簡単となる。
以下のプログラムは、0〜31の数字を2進数の各ビットに対応付けし、 ba = {1,2,3} , bb = {2,4,6} , bc= {4,6,9} を要素として持つ集合で、ba ∩ bb , bb ∩ bc の計算を行う例である。
void bit_print( unsigned int x ) { for( int i = 0 ; i < 32 ; i++ ) if ( (x & (1 << i)) != 0 ) printf( "%d " , i ) ; printf( "\n" ) ; } void main() { unsigned int ba = (1<<1) | (1<<2) | (1<<3) ; // ba = {1,2,3} unsigned int bb = (1<<2) | (1<<4) | (1<<6) ; // bb = {2,4,6} unsigned int bc = (1<<4) | (1<<6) | (1<<9) ; // bc = {4,6,9} bit_print( ba & bb ) ; // ba ∩ bb bit_print( bb & bc ) ; // bb ∩ bc bit_print( ba | bc ) ; // ba ∪ bc }
このような、2進数を用いた処理で有名なものとして、エラトステネスのふるいによる素数がある。 このアルゴリズムでは、各bitを整数に対応付けし、 素数で無いと判断した2進数の各桁に1の目印をつけていく方式である。
unsigned int prime = 0 ; void filter() { for( int i = 2 ; i < 32 ; i++ ) { if ( (prime & (1 << i)) == 0 ) { for( int j = i + i ; j < 32 ; j += i ) prime |= (1 << j) ; } } for( int i = 2 ; i < 32 ; i++ ) { if ( (prime & (1 << i)) == 0 ) printf( "%d\n" , i ) ; } }
リスト処理による積集合
前述の方法は、リストに含まれる/含まれないを、2進数の0/1で表現する方式である。 しかし、2進数であれば、unsigned int で 32要素、unsigned long long int で 64 要素が上限となってしまう。 (32bitコンピュータ,gccの場合)
しかし、リスト構造であれば、リストの要素として扱うことで、要素件数は自由に扱える。 また、今までの授業で説明してきた cons() などを使って表現すれば、 簡単なプログラムでリストの処理が記述できる。
// 先週までに説明してきたリスト構造と補助関数 struct List { int data ; struct List* next ; } ; struct List* cons( int x , struct List* n ) { struct List* ans ; ans = (struct List*)malloc( sizeof( struct List ) ) ; if ( ans != NULL ) { ans->data = x ; ans->next = n ; } return ans ; } void print( struct List* p ) { for( ; p != NULL ; p = p->next ) { printf( "%d " , p->data ) ; } printf( "\n" ) ; } int find( struct List* p , int key ) { for( ; p != NULL ; p = p->next ) if ( p->data == key ) return 1 ; return 0 ; }
例えば、積集合(a ∩ b)を求めるのであれば、リストa の各要素が、リストb の中に含まれるか find 関数でチェックし、 含まれたものだけを、ans に加えていく…という考えでプログラムを作ると以下のようになる。
struct List* set_prod( struct List* a , struct List* b ) { struct List* ans = NULL ; for( ; a != NULL ; a = a->next ) { if ( find( b , a->data ) ) ans = cons( a->data , ans ) ; } return ans ; } void main() { struct List* a = cons( 1 , cons( 2 , cons( 3 , NULL ) ) ) ; struct List* b = cons( 2 , cons( 4 , cons( 6 , NULL ) ) ) ; struct List* c = cons( 4 , cons( 6 , cons( 9 , NULL ) ) ) ; print( set_prod( a , b ) ) ; print( set_prod( b , c ) ) ; }
例題として、和集合、差集合などを考えてみよう。
リストの共有と削除の問題
リスト処理では、mallocを使うが、メモリリークをさせないためには、使用後のリストの廃棄は重要である。 リストの全要素を捨てる処理であれば、以下のようになるであろう。
void list_free( struct List* p ) { while( p != NULL ) { struct List* d = p ; p = p->next ; free( d ) ; // 順序に注意 } }
一方、前説明の和集合のプログラムを以下のように作った場合、list_freeの処理は問題となる。
struct List* set_union( struct List*a , struct List*b ) { struct List* ans = b ; for( ; a != NULL ; a = a->next ) if ( !find( b , a->data ) ) ans = cons( a->data , ans ) ; return ans ; } void main() { struct List*a = cons( 1 , cons( 2 , cons( 3 , NULL ) ) ) ; struct List*b = cons( 2 , cons( 3 , cons( 4 , NULL ) ) ) ; struct List*c = set_union( a , b ) ; // a,b,cを使った処理 // 処理が終わったので、a,b,cを捨てる list_free( a ) ; list_free( b ) ; list_free( c ) ; // c = { 1 , (bのリスト) } // (b)の部分は先のlist_free(b)で解放済み }