前期授業がどこまで進んでいたか、学生＆自分が忘れているので、 単純リスト構造の復習から説明を行う。

リストによるQueue

リスト構造によるstackの実現方法の説明が終わっているので、 次にリストを用いた待ち行列Queueの説明を行う。 最初に、top,tail の２つのポインタを使う事例を説明し、 その後に、循環リストにすればポインタが１つにすることができることを説明する。 特に、この循環リストは、プロセスキューのようなループするデータを表現するのに 向いていることを紹介する。

毎年ながら、このネタの説明の時には、図を書き間違え、トッチらかった説明をしてしまう。反省。

双方向リスト

エディタのカーソル移動を例にしながら、次のデータ参照と同様に前方データ参照が 必要な事例として紹介する。 そして、このような時に使われるのが、双方向リスト。

struct BDList { // 双方向リストの宣言
int    data ;
struct BDList* prev ;  // １つ前のデータへのポインタ
struct BDList* next ; // 次のデータへのポインタ
} ;
// 双方向リスト生成の補助関数
struct BDList* bdcons( struct BDList*p ,
int x , struct BDList* n ) {
struct BDList* ans ;
ans = (struct BDList*)malloc( sizeof( struct BDList ) ) ;
if ( ans != NULL ) {
ans->prev = p ;
ans->data = x ;
ans->next = n ;
}
return ans ;
}
void main() {
// リスト生成のサンプル
struct BDList* top ;
top = bdcons( NULL , 1 , NULL ) ;
top->next = bdcons( top , 2 , NULL ) ;
top->next->next = bdcons( top->next , 3 , NULL ) ;
// リスト順次参照のサンプル
struct BDList* p ;
for( p = top ; p != NULL ; p = p->next )
printf( "%d" , p->data ) ;
for( p = top->next->next ; p != NULL ; p = p->prev )
printf( "%d" , p->data ) ;
}
// 指定データの後ろに、データを挿入する処理
void bdinsert( struct BDList* p , int x ) {
struct BDList* n = bdcons( NULL , x , NULL ) ;
if ( n != NULL ) {
n->prev = p ;       // (1)
n->next = p->next ; // (2)
p->next->prev = p ; // (3)
p->next = n ;       // (4)
}
}

これらの説明の後、循環双方向リストを解説する。