リストによる集合演算
夏休み開け最初でかつ、テスト前最後の授業なので、 集合演算に関係するネタで復習を行いながら説明。
最初に、リスト構造の説明をするが、単純な復習では面白くないので、 他の教科書で多い typedef によるリスト宣言の説明を行う。
リストで集合演算
可変データ長であり、挿入削除が容易なので、リスト構造が集合情報 を扱うのに向いているといった説明の後、積集合のプログラムを示す。 テストなら和集合、差集合といったネタも豊富とだけ言っておく。
/* find,consは復習の時点で示しておいた */ struct List*cap( struct List*p , struct list*q ) { struct List* ans = NULL ; for( ; p != NULL ; p = p->next ) { if ( find( q , p->data ) ) ans = cons( p->data , ans ) ; } return ans ; }
構造体と配列で集合演算
リストを扱っていても、まだまだ構造体の理解も怪しい。 データ件数と配列による構造体で、集合を扱う事例を説明。 配列演算とリスト演算の対比を狙う。
struct Set { int size ; int array[ 10 ] ; } ; struct Set p = { 4 , { 1 , 2 , 3 , 4 } } ; struct Set q = { 5 , { 2 , 4 , 6 , 8 , 10 } } ; struct Set a ; cap( &a , &p , &q ) ; for( i = 0 ; i < a.size ; i++ ) printf( "%d\n" , a.array[ i ] ) ; /* この処理に見合うcap() を作れ! */ ------------------------------------ void cap( struct Set* ans , struct Set* p , struct Set* q ) { int i , j ; ans->size = 0 ; for( i = 0 ; i < p->size ; i++ ) { for( j = 0 ; j < q->size ; j++ ) { if ( p->array[ i ] == q->array[ j ] ) break ; if ( j < q->size ) { ans->array[ ans->size ] = p->array[ i ] ; ans->size++ ; } } }
ビット演算を使った集合処理
テストの範囲外というネタで、ビット演算が集合処理に使えることを説明。 要素に含まれれば対応ビットが1という説明をする。
/* A9876543210 */ int p = 0x1E ; /* 00000011110, p={1,2,3,4} */ int q = 0x554 ;/* 10101010100, q={2,4,6,8,10} */ for( i = 0 ; i < 11 ; i++ ) { if ( (p & q) & (1≪i) ) printf( "%d\n" , i ) ; /* 2,4が表示される */ }