ホーム » スタッフ » 斉藤徹 » 双方向リストと2分木

2011年9月
« 8月   10月 »
 123
45678910
11121314151617
18192021222324
252627282930  

最近の投稿(電子情報)

アーカイブ

カテゴリー

双方向リストと2分木

後期1発目で、どこまで説明していたっけ?状態から、確認しながらスタート。 後の双方向・2分木の利点を理解してもらうために、 改めて「リスト構造」の利点・欠点について質問をする。

双方向リスト

基本、シーケンシャルアクセスの単純リストでは、 次のデータ参照は簡単だけれども、テキストエディタみたいなものを作る場合、 1つ前の行を参照…が単純リストでは不便。 そこで1つ前の行に戻れればいいということで、双方向リストを紹介。

struct BDList {
struct BDList* prev ;
int  data ;
struct BDList* next ;
} ;

このデータ構造の特徴を理解してもらうための簡単なプログラムとして、 双方向リストの指定ポインタの後ろに1件データ追記を紹介。

void insert( struct BDList* p , int x ) {
struct BDList* n ;
n = (struct BDList*)malloc( sizeof( struct BDList ) ) ;
if ( n != NULL ) {
n->data = x ;
n->prev = p ;
n->next = p->next ;
p->next->prev = n ;
p->next = n ;
}
}

しかしながら、この補助関数 insert() では、最前のデータを作ることはできない。 1つ前バージョンの補助関数を作ったり、最前データだけ特別処理でプログラムを 書くこともできるけど煩雑になり、プログラムの間違いの可能性も高くなる。 こういう場合は一般的に番兵を用いる。 最前および最尾に、実際には利用しないダミーデータを入れておけば、 特別処理を書かなくて済む。

また、最前・最尾のダミーでは、無駄なデータが2ヶ所現れてしまう。 しかし、最前の番兵データの1つまえを実際の最尾データ、実際の最尾データの次を最前の番兵データとすれば、番兵は1つで済む。こういう構造であれば、末尾が先頭に つながっている構造なので、「双方向循環リスト」と呼ばれる。 となるようにポインタ

2分木の導入

単純リストでは、目的データを検索する場合、シーケンシャルアクセスしかできないため、 検索にはO(N)の処理となってしまう。 高速に検索したいのであれば、配列ならばランダムアクセスができるため、 二分探索法が利用でき、処理もO(log N)となる。 リスト構造でも、二分探索法のように速くかつ、途中にデータの挿入削除のできるように したい。この場合に使われるのが2分木。

struct Tree {
int  data ;
struct Tree* left ;
struct Tree* right ;
} ;