両端キュー　解答ページ | 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;
}

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

実行結果：

まずは、本編の「動的配列による実装①」での実装に対して機能追加してみます。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 が配列の末尾付近にある可能性もありますから、配列の要素数で除算した余りを最終的な添字とする必要があります。

はてなブックマークに保存	Pocket に保存	Facebook でシェア
X でポスト／フォロー	LINE で送る	noteで書く
RSS	管理者情報	プライバシーポリシー

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

問題①

参考リンク

更新履歴