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

双方向リスト

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

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

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

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分木の導入

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

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