ポインタ虎の巻

リスト構造

構造体を使った応用例として、リスト構造が挙げられる。リスト構造は非常に本質的なデータ構造の一つであり、応用範囲が非常に広い。このリスト構造に習熟することがC言語初級卒業試験であるといっても過言ではない。

なぜリスト構造がこれほどに重要なのかというと、削除や挿入が簡単に出来るからである。配列の場合、とくに挿入はコスト高である。配列データの次に新しいデータを挿入するには、それ以降のデータを全部1つづつずらしてやらなければならない。削除の場合にもデータを詰める作業をするか、別個にフラグを持たせて「無効データ」をマーキングしてやる必要がある。

それに対し、リスト構造は挿入を低いコストで行うことができるが、その代わりに配列のように添字によるランダムアクセスはできなくなる。だから、添え字によるランダムアクセスのコストと、挿入のコストとのトレードオフとして選択すべきであるが、一般に有用なケースは非常に多い。

またリスト構造は、より複雑な構造を作り上げる基礎となるデータ構造である。次と前の双方向にポインタを持つ双方向リストもあるし、二進木のように2つのポインタを持っても、多分木のようにそれ以上のポインタを持っても良いが、それらを使いこなすための基礎は、単純なリスト構造である。

また、検索の局面では、整列された配列ではバイナリサーチが使えて速いのだが、リスト構造では基本的に順次アクセスによる線形探査に限られることになり遅くなる。これを効率化するために、二進木探査やハッシュのような出来の良いアルゴリズムが存在する。これらの基礎もやはりリスト構造である。そのため、リスト構造をしっかり理解することが、中級プログラムの前提である。

ポインタを使わないリスト構造

まず、ポインタを使わずにリスト構造を実現してみよう。

struct List {
	int data;
	int next;
};
struct List MyList[128];

とりあえず、すべてグローバルで宣言されているものとする。それゆえ、確保された MyList 配列は現在すべて0が入っている。この時、次のルールを定める。

  1. dataメンバに、有用なデータが入っている。
  2. nextメンバには、そのデータの次のデータを表す添字番号が入っている。
  3. nextメンバが 0 であれば、未使用である。
  4. nextメンバが -1 であれば、それが最後のデータである。
  5. MyList[0] に入っているは、有効なデータではなくて、単に最初のデータの添字番号が MyList[0].next に入っているだけである。

要するに、あるデータを参照すると、その次のデータは next メンバで示されるデータであるということである。先頭はデータの値がダミーである MyList[0] であり、これから始まって、順に「チェーンを辿るように」参照していけば良い。そして、チェーンの最後を示す MyList[i].next == -1 を見つけたら、そこで終わる。これがリスト構造である。

リスト構造の参照

この時、「10,100,1000」の3つのデータが入ったリストを作るとしよう。その具体的表現は1つに定まらず、いろいろあっても良い。たとえば、

MyList[0].data = 0; /* このデータはダミー。*/
MyList[0].next = 1;
MyList[1].data = 10;
MyList[1].next = 2;
MyList[2].data = 100;
MyList[2].next = 3;
MyList[3].data = 1000;
MyList[3].next = -1; /* 次のデータはない。*/

でも、

MyList[0].data = 0; /* このデータはダミー。*/
MyList[0].next = 4;
MyList[1].data = 100; /* 2番目のデータ */
MyList[1].next = 3;
MyList[2].data = 100;
MyList[2].next = 0;   /* このデータは使われていない */
MyList[3].data = 1000; /* 3番目のデータ */
MyList[3].next = -1;  /* 次のデータはない。*/
MyList[4].data = 10;  /* 1番目のデータ */
MyList[4].next = 1;

でも構わない。データを順に参照していくと、最初の構造では「(0)→1→2→3」の順にアクセスするが、後の構造では「(0)→4→1→3」の順でアクセスすることになる。このように、参照する順番を添字番号とは切り離すのが中心的なアイデアである。

だからこの参照プログラムは次のようになる。

void chaseList( void )
{
    int at = MyList[0].next;
    while( at != -1 ) {
        printf( "data = %d\n", MyList[at].data );
        at = MyList[at].next;
        if( at == 0 ) {
            fprintf( stderr, "起こり得ない\n" );
            exit( 1 );
        }
    }
}

リスト構造のデータ削除

値が 100 であるデータを削除してみよう。

void delete100( void )
{
    int at = MyList[0].next;
    int prev = 0;
    while( at != -1 ) {
        if( MyList[at].data == 100 ) {
            MyList[prev].next = MyList[at].next;
            MyList[at].next = 0;  /* 無効データにする */
            printf( "値が100のデータを削除しました!\n" );
            break;
        }
        prev = at;
        at = MyList[at].next;
        if( at == 0 ) {
            fprintf( stderr, "起こり得ない\n" );
            exit( 1 );
        }
    }
    if( at == -1 ) {
        printf( "値が100のデータは見つかりませんでした\n" );
    }
}

となる。後のデータ構造でこの関数を実行すると、次のようなデータに更新される。

MyList[0].data = 0; /* このデータはダミー。*/
MyList[0].next = 4;
MyList[1].data = 100; /* 2番目のデータ */
MyList[1].next = 0;
MyList[2].data = 100;
MyList[2].next = 0;   /* このデータは使われていない */
MyList[3].data = 1000; /* 3番目のデータ */
MyList[3].next = -1;  /* 次のデータはない。*/
MyList[4].data = 10;  /* 1番目のデータ */
MyList[4].next = 3;

このアルゴリズムで、リストの最初のデータを削除する場合でも、最後のデータを削除する場合でも、正しく動くことを確認されたい。

ポインタを使ったリスト構造

復習になるが、リスト構造は自己参照構造体と呼ばれる構造体によって定義される。

struct List {
        int data;
        struct List *next;
};

この宣言で、struct List を定義している中で、strut List を使っているのは矛盾しているのではないかと思うならば、前頁を参照されたい。ルールは少しだけ変更される。

  1. dataメンバに、有用なデータが入っている。
  2. nextメンバには、そのデータの次のデータを指し示すポインタが入っている。
  3. nextメンバが NULL(==0) であれば、未使用か最後のデータである。
  4. MyList[0] に入っているは、有効なデータではなくて、単に最初のデータのポインタが MyList[0].next に入っているだけである。

これで順次参照と削除を書き直してみる。そうすると、

void chaseList( void )
{
    struct List *at = MyList[0].next;
    while( at != NULL ) {
        printf( "data = %d\n", at->data );
        at = at->next;
    }
}


void delete100( void )
{
    struct List *at = MyList[0].next;
    struct List *prev = &MyList[0];
    while( at != NULL ) {
        if( at->data == 100 ) {
            prev->next = at->next;
            at->next = NULL;  /* 無効データにする */
            printf( "値が100のデータを削除しました!\n" );
            break;
        }
        prev = at;
        at = at->next;
    }
    if( at == NULL ) {
        printf( "値が100のデータは見つかりませんでした\n" );
    }
}

これで同等の処理ができることになる。構造体ポインタのメンバ参照なので、アロー演算子を使うことに注意されたい。また、リストの繋ぎ替えは順番が重要なことにも注意されたい。

リスト構造の挿入

では挿入をしてみよう。というのか、順次読んで行って、結果としてソートされたリストを得るような、挿入ソートアルゴリズムになる。

void insertList( struct List *ins )
{
    struct List *at   = myList[0].next;
    struct List *prev = &myList[0];
    while( at != NULL ) {
        if( ins->data >= at->data ) {
            ins->next = prev->next;
            prev->next = ins;
            break;
        }
        prev = at;
        at = at->next;
    }
    if( at == NULL ) { /* 最後に追加は特別扱い */
        ins->next = NULL;
        prev->next = ins;
    }
}

ポイントは操作が1つ前のもの(prev)に対して行われることである。挿入の繋ぎ替えは順番に注意を払い、まだ必要なデータをつぶしてしまわないように気をつけられたい。

また、この挿入ソートは、配列の場合には「比較コストが低い」が「交換コストの高い」特徴を持つために、バブルソートよりも良好だが選択ソートよりも効率が悪い傾向にあるが、リスト構造を取れば交換コストを下げることができるので、クイックソートをしたくない場合にオススメのやり方になるし、既にある程度逆順に揃っていることが前提となる場合には、楽で効率の良いやり方でもある。(正順にある程度揃っている場合には、直前に挿入したデータを at や prev の初期値としてポイントしておけば良い。)



copyright by K.Sugiura, 1996-2006