循環リストと双方向リスト

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

リストによるQueue

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

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

双方向リスト

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

struct BDList { // 双方向リストの宣言
    int    data ;
    struct BDList* prev ;  // 1つ前のデータへのポインタ
    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)
    }
}

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

 

2015年12月

    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    

アーカイブ

Google

このブログ記事について

このページは、T-Saitohが2009年9月30日 13:15に書いたブログ記事です。

ひとつ前のブログ記事は「Robot Watch の記事に歯みがきロボコンの記載」です。

次のブログ記事は「データベース・ガイダンス・内部スキーマ」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。