ホーム » スタッフ » 斉藤徹 » テスト返却とデータ構造の共有問題

2011年12月
« 11月   1月 »
 123
45678910
11121314151617
18192021222324
25262728293031

最近の投稿(電子情報)

アーカイブ

カテゴリー

テスト返却とデータ構造の共有問題

2分木とハッシュ法を範囲とする中間テストの返却と、 後期期末までの授業のための導入部分を説明する。

テスト解説の後は、データの共有と削除に伴う問題点を紹介し、 来週からの授業の導入とする。

データの共有が発生する場合の代表的な例として、リストを用いた集合における、 和集合とそのリスト廃棄で説明を行う。

// すべてのリストを捨てる処理
void list_free( struct List* p ) {
struct List* del ;
while( p != NULL ) {
del = p ;
p = p->next ;
free( del ) ;
}
}
// 補助関数:find
int find( struct List* p , int key ) {
for( ; p != NULL ; p = p->next )
if ( p->data == key )
return 1 ;
return 0 ;
}
// 和集合
struct List* add( struct List* p1 , struct List* p2 ) {
for( ; p1 != NULL ; p1 = p1->next ) {
if ( ! find( p2 , p1->data ) )
p2 = cons( p1->data , p2 ) ;
}
return p2 ;
}
void main() {
struct List* p1 = cons( 1 , cons( 2 , cons( 4 , NULL ) ) ) ;
struct List* p2 = cons( 2 , cons( 3 , NULL ) ) ;
struct List* p3 = add( p1 , p2 ) ;
// p1 = { 1 , 2 , 4 }
// p2 = { ※2 , 3 }
// p3 = { 4 , 1 , ※2 , 3 } , ※の部分が共有されている
list_free( p3 ) ;
list_free( p2 ) ; // ※の部分は既に前処理で消されている
// のでリストの廃棄処理でトラブル。
list_free( p1 ) ;
}