ホーム » スタッフ » 斉藤徹 » 共有のあるポインタの問題点と、双方向リスト

2004年10月
« 9月   11月 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

最近の投稿(電子情報)

アーカイブ

カテゴリー

共有のあるポインタの問題点と、双方向リスト

リスト構造の一括 free のプログラムを示した後、ポインタの先に共有がある 場合の問題点として、破壊系リスト処理(nconcを例として示した)で、 後処理の一括 free の呼び出しの有無が判断が困難である事例をしめす。 ガベージコレクタ等の解説は、リスト構造全般の話が終了した時点で行う予定。

双方向リスト

単純リストが、可変長・次参照のみ、配列が固定長・ランダムアクセスである 点を強調する。この後で、エディタを作る場合の処理の特徴として、 前・次の参照、途中の挿入削除を説明する。この解決策としての双方リストの 説明を行う。

struct BDList {
struct BDList* prev ;
int            data ;
struct BDList* next ;
} ;
struct BDList* bdcons( struct BDList* p ,
int            x ,
struct BDList* n )
{ struct BDList* m ;
/* malloc行を穴埋めとして質問 */
m = (struct BDList*)malloc( sizeof( struct BDList ) ) ;
if ( m != NULL ) {
m->prev = p ;
m->data = x ;
m->next = n ;
}
return m ;
}
void main() {
struct BDList* top ;
/* 下記 top のイメージ図を示し */
top = bdcons( NULL , 1 ,
bdcons( NULL , 2 ,
bdcons( NULL , 3 , NULL ) ) ) ;
/* 双方向リストにするための以下2行を穴埋め質問 */
top->next->prev = top ;
top->next->next->prev = top->next ;
}

この後、双方向リストのプログラム事例として、後方 insert を 穴埋め形式で質問し、ポインタの繋ぎ換えをイメージ図で説明する。