夏休み開け最初でかつ、テスト前最後の授業なので、 集合演算に関係するネタで復習を行いながら説明。

最初に、リスト構造の説明をするが、単純な復習では面白くないので、 他の教科書で多い 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++ ;
}
}
}

ビット演算を使った集合処理

テストの範囲外というネタで、ビット演算が集合処理に使えることを説明。 要素に含まれれば対応ビットが１という説明をする。

/* 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が表示される */
}