先頭へ戻る

両端キュー 解答ページ | Programming Place Plus アルゴリズムとデータ構造編【データ構造】 第11章

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

先頭へ戻る

問題①

問題① 動的配列によって実装された両端キューに、インデックスによる直接アクセスを行う機能を追加してください。


deque_set関数と deque_get関数を次のような仕様で追加します。

/*
    両端キューの要素の値をセットする

    引数:
        queue:  両端キュー
        index: 添字
        value: セットする値

    要素を追加するのではなく、既存の要素を書き換えるので、
    範囲外アクセスに注意すること。
*/
void deque_set(Deque deque, size_t index, int value);

/*
    両端キューの要素の値を返す

    引数:
        queue:  両端キュー
        index: 添字
    戻り値:
        index の位置にある要素の値

    要素を追加するのではなく、既存の要素を書き換えるので、
    範囲外アクセスに注意すること。
*/
int deque_get(Deque deque, size_t index);

要素の値をセットすることと、要素を追加することとの違いは意識してください。両端キューに要素が 5個入っているとすれば、有効な添字の範囲は 0~4 であり、この範囲外の値を指定することは不正です。

動作確認用の main関数は次のように準備しておきます。

// main.c

#include <stdio.h>
#include "deque.h"


int main(void)
{
    Deque deque = deque_create();

    for( size_t i = 0; i < 10; ++i ){
        deque_push_back( deque, (int)i );
    }

    for( size_t i = 0; i < 10; ++i ){
        printf( "%d\n", deque_get( deque, i ) );
    }

    for( size_t i = 0; i < 10; ++i ){
        deque_set( deque, i, (int)(10 - i) );
    }

    for( size_t i = 0; i < 10; ++i ){
        printf( "%d\n", deque_get( deque, i ) );
    }


    deque_delete( deque );
    return 0;
}

実行結果が、次のようになれば成功です。

実行結果:

0
1
2
3
4
5
6
7
8
9
10
9
8
7
6
5
4
3
2
1

まずは、本編の「動的配列による実装①」での実装に対して機能追加してみます。deque.c に追加するコードだけ取り上げます。

/*
    両端キューの要素の値をセットする
*/
void deque_set(Deque deque, size_t index, int value)
{
    assert(0 <= index && index < deque->count);

    deque->array[deque->head + index] = value;
}

/*
    両端キューの要素の値を返す
*/
int deque_get(Deque deque, size_t index)
{
    assert(0 <= index && index < deque->count);

    return deque->array[deque->head + index];
}

範囲外アクセスは assert でチェックしています。どんな手段で対処しても構いませんが、範囲外アクセスが起こり得るという意識はつねに持つようにしてください。

要素は、動的配列の中央部分から前後に追加していく実装なので、添字の計算方法には注意が必要です。つねに、head の位置を確認して、その位置を 0番目と考えてください。


次に、本編の「動的配列による実装②」での実装に対する追加です。こちらも、deque.c に追加するコードだけ取り上げます。

/*
    両端キューの要素の値をセットする
*/
void deque_set(Deque deque, size_t index, int value)
{
    assert(0 <= index && index < deque->count);

    deque->array[(deque->head + index) % deque->size] = value;
}

/*
    両端キューの要素の値を返す
*/
int deque_get(Deque deque, size_t index)
{
    assert(0 <= index && index < deque->count);

    return deque->array[(deque->head + index) % deque->size];
}

リングバッファになっているので、添字の計算がさらに複雑になっています。head の位置を 0番目と考える点は共通ですが、head が配列の末尾付近にある可能性もありますから、配列の要素数で除算した余りを最終的な添字とする必要があります。


参考リンク


更新履歴

’2018/2/22 要素数を意味している「サイズ」について、「要素数」に表記を改めた。

’2015/1/17 新規作成。



第11章のメインページへ

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

Programming Place Plus のトップページへ



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