先頭へ戻る

連結リスト②(双方向・循環) 解答ページ | Programming Place Plus アルゴリズムとデータ構造編【データ構造】 第4章

Programming Place Plus トップページアルゴリズムとデータ構造編

先頭へ戻る

問題①

問題① 双方向循環リストの末尾から先頭に向かって、要素の値を出力する関数を作成してください。


双方向循環リストにおいて、ダミーの先頭要素があるのなら、リストの末尾の要素は、gHead.prev を参照するだけで簡単に取得できます。あとは、prevポインタをたどる操作を、gHead に戻ってくるまで繰り返すだけです。

/*
    要素を逆順に出力する
*/
void print_list(void)
{
    struct LinkedList_tag* p = gHead.prev;

    if( p == NULL ){
        puts( "リストは空です。" );
        return;
    }

    while( p != &gHead ){
        printf( "%d\n", p->value );
        p = p->prev;
    }
}

この関数を試すにあたって、双方向循環リストの初期化や、要素の登録処理を作らなければならないはずです。あえてコードは示さないことにしますが、単方向循環リストと双方向線形リストのサンプルをよく検討すれば、何とかなると思います。

問題②

問題② 単方向循環リストから目的の要素を探し出す関数を作成してください。このとき、リスト内の要素のメモリアドレスを引数に取るようにし、その位置から探索を始めるように実装してください。


次のように関数化できます。

/*
    指定の値を持った要素を探す

    引数:
        start:  探索を開始する位置。
        value:  探す値。
    戻り値:
        start から探索を開始し、最初に見つけた value を持つ要素のメモリアドレスを返す。
        見つからなければ NULL を返す。
    備考:
        探索は、引数start の位置から開始され、最初に見つけた要素を返す。
*/
struct LinkedList_tag* search_elem(struct LinkedList_tag* start, int value)
{
    struct LinkedList_tag* p = start;

    do {
        if( p->value == value ){
            return p;
        }
        p = p->next;
    } while( p != start );

    return NULL;
}

循環リストですから、どこから開始したとしても、nextポインタをたどっていくだけでリストを周回できます。

終了判定は少し考えさせられるかもしれません。1周したかどうかが基準となるので、開始位置のメモリアドレスと、現在参照している要素のメモリアドレスとの一致を見ることになります。上の例では、do-while文にしていますが、条件式を変えずに普通の while文を使うと、リスト内の要素が start で指定した要素1つだけのとき、start が探索されなくなってしまいます。

なお、先頭にダミーの要素がある場合、上の例のままだとダミー要素も探索対象に含まれます。これを避けるためダミーの要素かどうかを判定するコードを仕込むことは当然可能ですが、処理時間を浪費することになります。この辺りの問題を解決する必要があるのなら、ダミー要素を使わないで実装することも検討しないといけません。

問題③

問題③ 双方向線形リストにおいて、要素を途中に挿入する関数を作成してください。前章の insert_elem関数と同じ引数・戻り値を持つように実装してください。


双方向版なので、prevポインタの付け替えが追加されます。

/*
    要素を挿入する

    引数:
        value:  挿入する値。
        pos:    挿入する位置にある値。この値を持った要素を探し、その要素の直後に挿入する。
    戻り値:
        成功したら 0以外、失敗したら 0 を返す。
*/
int insert_elem(int value, int pos)
{
    // 追加位置を探す
    struct LinkedList_tag* p = search_elem( pos );
    if( p == NULL ){
        return 0;
    }

    // 追加する要素を作る
    struct LinkedList_tag* elem = malloc( sizeof(struct LinkedList_tag) );
    if( elem == NULL ){
        fputs( "メモリ割り当てに失敗しました。", stderr );
        exit( 1 );
    }
    elem->value = value;
    elem->next = p->next;  // p と p->next の隙間に挿入する
    elem->prev = p;        // p と p->next の隙間に挿入する

    p->next = elem;           // p の直後に挿入された
    elem->next->prev = elem;  // elem->next にとっての prev は、挿入された elem

    return 1;
}


参考リンク


更新履歴

’2011/9/24 新規作成。



第4章のメインページへ

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー