先頭へ戻る

多次元配列 解答ページ | Programming Place Plus アルゴリズムとデータ構造編【データ構造】 第2章

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

先頭へ戻る

問題①

問題① 多次元配列で、任意の行を削除する方法を考えてください。


多次元配列で行を削除するという行為は、一次元配列で要素を削除することと同じです。第1章で見たように、配列から要素を削除すると、後続の要素を前方にずらすことになるため、非効率と言えます。多次元配列の場合、1行を構成する要素をまとめて前方へずらすことになります。

実際のプログラムは次のようになります。

#include <stdio.h>
#include <string.h>

#define ARRAY_COL_NUM    3      // 配列の列の数
#define ARRAY_ROW_NUM    5      // 配列の行の数

int main(void)
{
    int array[ARRAY_ROW_NUM][ARRAY_COL_NUM] = { 
        {  0,  1,  2 },
        { 10, 11, 12 },
        { 20, 21, 22 },
        { 30, 31, 32 },
        { 40, 41, 42 }
    };


    // 2行目を削除する
    for( int y = 3; y < ARRAY_ROW_NUM; ++y ){
        memmove( array[y - 1], array[y], sizeof(array[y]) );
    }

    // 配列の全要素を出力する
    for( int y = 0; y < ARRAY_ROW_NUM; ++y ){
        for( int x = 0; x < ARRAY_COL_NUM; ++x ){
            printf( "%2d ", array[y][x] );
        }
        printf( "\n" );
    }

    return 0;
}

実行結果:

 0  1  2
10 11 12
30 31 32
40 41 42
40 41 42

memmove関数を使って、後続の行を1行ずつ前方へずらす方法を採っています。

最後尾にあった1行が重複していますが、ここをどうするかはその時々に応じて判断することになるでしょう。第1章で見たように、それと分かるような未使用値で埋めておくという方法も考えられます。

問題②

問題② ジャグ配列では、各行の要素数が異なるため、何らかの手段を用いないと、要素を順番にたどるときに行の終りが分かりません。解決方法を考えてください。


格納されている情報が文字列であれば、末尾の ‘\0’ を探せばよいですから、それは問題ありません(これはC言語特有の事情ですが)。

文字列の ‘\0’ は良いヒントになります。文字列でなくても、何らかの末尾を表す値を作り、必ず末尾に置いておくという考え方ができそうです。

#include <stdio.h>
#include <stdlib.h>

#define ARRAY_ROW_NUM   4    // 配列の行数
#define END_OF_ROW     -1    // 行の終端を表す値

int main(void)
{
    int* array[ARRAY_ROW_NUM];

    array[0] = malloc( sizeof(int) * 5 );
    array[0][0] = 0;
    array[0][1] = 1;
    array[0][2] = 2;
    array[0][3] = 3;
    array[0][4] = END_OF_ROW;

    array[1] = malloc( sizeof(int) * 3 );
    array[1][0] = 10;
    array[1][1] = 11;
    array[1][2] = END_OF_ROW;

    array[2] = malloc( sizeof(int) * 4 );
    array[2][0] = 20;
    array[2][1] = 21;
    array[2][2] = 22;
    array[2][3] = END_OF_ROW;

    array[3] = malloc( sizeof(int) * 5 );
    array[3][0] = 30;
    array[3][1] = 31;
    array[3][2] = 32;
    array[3][3] = 33;
    array[3][4] = END_OF_ROW;


    // 配列の全要素を出力する
    for( int y = 0; y < ARRAY_ROW_NUM; ++y ){
        for( int x = 0; array[y][x] != END_OF_ROW; ++x ){
            printf( "%2d ", array[y][x] );
        }
        printf( "\n" );
    }

    return 0;
}

実行結果:

 0  1  2  3
10 11
20 21 22
30 31 32 33

すべての行の終わりに、END_OF_ROW を置くようにしてあります。このような目印があれば、実行結果のように、有効な部分だけを奇麗に出力できます。

問題③

問題③ 3次元以上の多次元配列について、その性質や利用価値を考えてみてください。


配列としての性質は特に変わりません。何次元に拡張しても同様です。

問題は利用価値ですが、ほとんどの場合、3次元配列が限度であり、4次元配列以上は使いません。なぜかというと、人間がイメージすることが不可能だからでしょう。1次元配列なら列、2次元なら表、3次元なら箱のような構造がイメージできますが、4次元以上になってくるとイメージできません。イメージできないものをコード化するのは非常に困難です。

もし、4次元以上の配列を使おうとしていたら、立ち止まって、設計を見直すべきです。


参考リンク


更新履歴

’2018/3/29 「row」「col」の表現が逆になっている箇所があったのを修正。

’2014/4/19 Perl版のサンプルを削除。

’2011/10/8 各サンプルの Perl版を作成。

’2011/8/14 新規作成。



第2章のメインページへ

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

Programming Place Plus のトップページへ



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