配列 | Programming Place Plus アルゴリズムとデータ構造編【データ構造】 第1章

アルゴリズムとデータ構造編【データ構造】 第1章 配列

先頭へ戻る

この章の概要

この章の概要です。


配列とは

配列は、最も基本的なデータ構造と言えます。実際、ほとんどのプログラミング言語では、配列を簡単に利用できるようになっています(C言語編の配列の記事はこちら⇒第25章

配列は、要素を連続的に並べたデータ構造です。添字(そえじ)と呼ばれる値を使って、任意の要素を直接的に参照できます。

配列を使う際には、単独の変数と同様、宣言や定義を必要とします。このとき、配列に格納できる要素数を指定します。C言語の場合、後から要素数を変更することはできません。

C99 では、要素数の指定に(定数だけではなく)変数の値を利用できるようになりました。

C言語の場合、1つの配列内には同じ型の値しか格納できません。例えば、int型専用の配列、struct MyData型専用の配列といった具合です。

配列の宣言は次のように行います。

int array[5];                    /* 要素数 5 の配列. 要素は不定 */
int array[] = { 0, 1, 2, 3, 4 }; /* 0,1,2,3,4 という要素を持つ配列. 要素数は自動判断により 5 */

要素の参照

要素を参照するには、添字を使います。インデックスと表現することもあります。

添字は、プログラミング言語の種類によっては、整数でないこともありますが、一般的な配列では整数を使います。整数の代わりに文字列を使って参照を行うような配列は、連想配列と呼ばれます。こちらは機会を改めて紹介します。

添字が、配列の要素数の上限を超えてしまわないように注意が必要です。例えば、要素数が 10個の配列に対して、11個目の要素を参照するような指定が安全であるかどうかは、言語によって差異があります。

これは下限の方も同様ですが、先頭の要素を表す添字が幾つなのかは、プログラミング言語によって異なることがあります。C言語では、先頭の要素は 0番目と表現されるので、添字は 0 になりますが、言語によっては、1番目と考えるものや、下限値を幾つにするかを指定できるものもあります。

C言語では、配列の範囲外を参照することは、未定義の動作となり危険です。

添字を使って、要素を直接参照できるという性質は、配列の大きな長所になっています。つまり、どの位置に何が格納されているかを把握しているのであれば、探し出す手間がまったくかからないため、非常に高速に処理できるのです。

要素を参照するコードは次のようになります。

#include <stdio.h>

#define SIZE_OF_ARRAY(array)	(sizeof(array)/sizeof(array[0]))

int main(void)
{
    int array[] = { 0, 1, 2, 3, 4 };
    int num, i;

    num = array[2];
    array[2] = 10;
    array[5] = 10;   /* 範囲外アクセス. 動作は未定義 */
    num = array[6];  /* 範囲外アクセス. 動作は未定義 */

    /* 配列の全要素を出力する */
    for( i = 0; i < SIZE_OF_ARRAY(array); ++i ){
        printf( "%d\n", array[i] );
    }

    return 0;
}

要素の追加

要素数が固定されている配列に対して、要素を追加することはできません。するとすれば、どこかに新しい要素を割り込ませて、後続の要素をずらすことになります。その場合、割り込まれた要素の個数の分だけ、他の要素を配列から追い出す必要があります。

realloc関数を使って、動的な配列を実現している場合は、要素を追加できます。しかしその場合でも、末尾以外の位置に追加するには、後続の要素をずらさなくてはならない点に変わりはありません。

まず、末尾へ追加する例を挙げます。

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

#define ARRAY_SIZE   (5)

int main(void)
{
    int* array;
    int* tmp;
    int i;

    array = malloc( sizeof(int) * ARRAY_SIZE );
    for( i = 0; i < ARRAY_SIZE; ++i ){
        array[i] = i;
    }

    /* 末尾に要素を追加したい */
    tmp = realloc( array, sizeof(int) * (ARRAY_SIZE * 2) );
    if( tmp == NULL ){
        free( array );
        exit( EXIT_FAILURE );
    }
    array = tmp;
    array[ARRAY_SIZE] = 999;

    /* 全要素を出力 */
    for( i = 0; i < ARRAY_SIZE + 1; ++i ){
        printf( "%d\n", array[i] );
    }

    free( array );

    return 0;
}

実行結果:

0
1
2
3
4
999

C言語による実装は、realloc関数を使って、配列そのものを作り直すという方法になります。見ての通り、非常に面倒です。

しかし、あらかじめ配列の要素数に余裕を持たせておけば、末尾への追加は高速に行えます。

#include <stdio.h>

#define ARRAY_SIZE		(10)  /* 配列の要素数 */

int main(void)
{
    int array[ARRAY_SIZE] = { 0, 1, 2, 3, 4 };
    int size = 5;
    int i;

    /* 
        この時点で、配列の要素数は 10 だが、使っているのは 5個
    */

    /* 末尾へ追加 */
    array[size++] = 999;

    /* 配列の全要素を出力する */
    for( i = 0; i < ARRAY_SIZE; ++i ){
        printf( "%d\n", array[i] );
    }

    return 0;
}

実行結果:

0
1
2
3
4
999
0
0
0
0

実際の要素数を一杯まで使わず、現実の末尾を記憶しておくことで実現しています。初期化の時点で、現実の要素は 0, 1, 2, 3, 4 の 5個ですから、次に要素を追加できる位置は 5番目となります。変数size は、現実の要素数を表しており、末尾へ要素を追加するのなら、array[size] へ格納すればいいということです。

次に、配列の先頭への追加を考えます。

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

#define ARRAY_SIZE   (5)

int main(void)
{
    int* array;
    int* tmp;
    int i;

    array = malloc( sizeof(int) * ARRAY_SIZE );
    for( i = 0; i < ARRAY_SIZE; ++i ){
        array[i] = i;
    }

    /* 先頭に要素を追加したい */
    tmp = realloc( array, sizeof(int) * (ARRAY_SIZE * 2) );
    if( tmp == NULL ){
        free( array );
        exit( EXIT_FAILURE );
    }
    array = tmp;
    memmove( &array[1], &array[0], sizeof(int) * ARRAY_SIZE );
    array[0] = 999;

    /* 全要素を出力 */
    for( i = 0; i < ARRAY_SIZE + 1; ++i ){
        printf( "%d\n", array[i] );
    }

    free( array );

    return 0;
}

実行結果:

999
0
1
2
3
4

末尾以外の位置に要素を追加する場合、追加位置を含めた後続の要素を1つずつずらす作業が必要になります。これを memmove関数を使って実現しています。

要素をずらしていく作業は、配列の要素数が多ければ多いほど、時間が掛かる処理です。要素数が多い配列において、頻繁にこの作業が必要になるようならば、恐らく、データ構造の選定ミスと言えます。

要素の削除

要素の削除に関しても、要素の追加と同じ問題があります。つまり、配列の先頭や、途中の要素を削除すると、後続の要素がずれるということです。これは配列の要素数が多ければ多いほど、大きな処理コストが掛かってしまいます。

#include <stdio.h>

#define SIZE_OF_ARRAY(array)	(sizeof(array)/sizeof(array[0]))

int main(void)
{
    int array[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int i;

    /* 3番目の要素を削除する */
    for( i = 4; i < SIZE_OF_ARRAY(array); ++i ){
        array[i-1] = array[i];
    }

    /* 配列の全要素を出力する */
    for( i = 0; i < SIZE_OF_ARRAY(array); ++i ){
        printf( "%d\n", array[i] );
    }

    return 0;
}

実行結果:

0
1
2
4
5
6
7
8
9
9

サンプルプログラムのように、後続の要素をずらす作業が必要です。この作業をしている for文は、結構間違いやすい箇所で、かなり注意深く実装する必要があります。もちろん、memmove関数を使っても構いませんが、どちらにしても単純明快な記述は不可能です。

また、実行結果を見ると分かるように、最後に 9 が 2つ出力されています。これは、配列の要素数は固定なので、途中の要素を削除して、後続の要素をずらしていった結果、末尾に取り残される要素ができてしまうためです。

あえて後続の要素をずらさず、そのまま残しておくという解決策もあり得ます。その場合は、削除した箇所には、削除済みであるという何かしらのマークを付ける必要があるでしょう。このマーク付けの処理が面倒であったり、無駄な処理コストになったりしますが、添字がずれないという利点があります。

#include <stdio.h>

#define SIZE_OF_ARRAY(array)	(sizeof(array)/sizeof(array[0]))
#define UNUSED                  (-1)

int main(void)
{
    int array[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int i;

    /* 3番目の要素を削除する */
    array[3] = UNUSED;

    /* 配列の全要素を出力する */
    for( i = 0; i < SIZE_OF_ARRAY(array); ++i ){
        if( array[i] == UNUSED ){
            puts( "UNUSED" );
        }
        else{
            printf( "%d\n", array[i] );
        }
    }

    return 0;
}

実行結果:

0
1
2
UNUSED
4
5
6
7
8
9

サンプルプログラムでは、UNUSED という記号定数を用意し、これを未使用な領域であることを示す値として使っています。UNUSED の具体的な値として -1 を選択していますが、これはもちろん、本物の要素の値として -1 が存在しないことが前提です。この辺りは悩ましいところで、全ての値が存在し得る場合には、UNUSED として適切な値が選べないかも知れません。その場合には、もう1つ配列を用意して、使用中か未使用かのフラグだけを管理させるといった対応が必要になります。


要素の探索

配列の中から、目的の値を持った要素を探し出したいという場面はよくあります。更に考察すると、

  1. 配列の中に、目的の値が存在しているかどうかが知りたい。
  2. 配列の中に、目的の値が何個あるか知りたい。
  3. 配列のどの位置に、目的の値があるか知りたい。ただし、一番最初に見つけたものだけで構わない。
  4. 配列のどの位置に、目的の値があるか知りたい。ただし、一番最後に見つけたものだけで構わない(逆順の探索)
  5. 配列のどの位置に、目的の値があるか知りたい。しかも、すべて抜き出したい。

といったように、目的はさまざまです。

実は、データ構造の中から、目的のデータを探し出すという操作は、アルゴリズムの分野そのものです。これは、探索アルゴリズムとかサーチアルゴリズムなどと呼ばれるものです。ですから詳しい解説は、専用の章に譲り、ここでは幾つかの事例に絞って簡単に解説するに留めます。

まず、先ほどの使用場面のうち、2番を実装することによって、1番目は自動的に満たされます。つまり、目的の値を持った要素の個数を調べ、それが 1以上であれば、1番目の用途(値が存在しているか)が満たされる訳です。

#include <stdio.h>

#define SIZE_OF_ARRAY(array)	(sizeof(array)/sizeof(array[0]))

int main(void)
{
    int array[] = { 3, 7, 9, 14, 7, 22 };
    int i, count;


    /* 7 を探す */
    count = 0;
    for( i = 0; i < SIZE_OF_ARRAY(array); ++i ){
        if( array[i] == 7 ){
            ++count;
        }
    }

    printf( "%d個見つかりました。\n", count );

    return 0;
}

実行結果:

2個見つかりました。

これは、単純明快でしょう。配列を先頭から順番に調べ、個数をカウントしています。

先ほど、目的の値が存在しているかを調べることにも流用できることを説明しましたが、効率面から言えば、やや非効率ではあります。というのも、存在しているかどうかだけを知りたいのであれば、1個見つけた時点で即座に for文を抜け出せるはずだからです。また、変数count のようなものを作る必要もありません。

#include <stdio.h>

#define SIZE_OF_ARRAY(array)	(sizeof(array)/sizeof(array[0]))

int main(void)
{
    int array[] = { 3, 7, 9, 14, 7, 22 };
    int i;


    /* 7 を探す */
    for( i = 0; i < SIZE_OF_ARRAY(array); ++i ){
        if( array[i] == 7 ){
            puts( "見つかりました。" );
            return 0;
        }
    }

    puts( "見つかりませんでした。" );

    return 0;
}

実行結果:

見つかりました。

目的の値を持った要素の位置を調べることも、基本的には同じ方法で実装できます。

#include <stdio.h>

#define SIZE_OF_ARRAY(array)	(sizeof(array)/sizeof(array[0]))

int main(void)
{
    int array[] = { 3, 7, 9, 14, 7, 22 };
    int i;


    /* 7 を探す */
    for( i = 0; i < SIZE_OF_ARRAY(array); ++i ){
        if( array[i] == 7 ){
            printf( "%d番目にあります。\n", i );
            return 0;
        }
    }

    puts( "見つかりませんでした。" );

    return 0;
}

実行結果:

1番目にあります。

厄介なのは、目的の値の位置をすべて見つけ出したい場合です。問題なのは、探し出した結果もまた配列になってしまうという点です。

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

#define SIZE_OF_ARRAY(array)	(sizeof(array)/sizeof(array[0]))

int main(void)
{
    int array[] = { 3, 7, 9, 14, 7, 22 };
    int* result_array;
    int next_result_index;
    int i;


    result_array = malloc( sizeof(int) * SIZE_OF_ARRAY(array) );
    next_result_index = 0;


    /* 7 を探す */
    for( i = 0; i < SIZE_OF_ARRAY(array); ++i ){
        if( array[i] == 7 ){
            result_array[next_result_index++] = i;
        }
    }

    if( next_result_index == 0 ){
        puts( "見つかりませんでした。" );
    }
    else{
        for( i = 0; i < next_result_index; ++i ){
            printf( "%d番目にあります。\n", result_array[i] );
        }
    }

    free( result_array );

    return 0;
}

実行結果:

1番目にあります。
4番目にあります。

まとめ

[長所]

[短所]


練習問題

問題① 配列の中身を逆順にするプログラムを作成して下さい。このとき、対象となる配列自身を書き換えるタイプと、対象は書き換えずに新たな配列を作り出すタイプとを実装して下さい。

問題② 整数が格納された配列から、偶数の値を持つ要素数を数えるプログラムを作成して下さい。

問題③ 2つの配列に、共通して含まれている値を探し出すプログラムを作成して下さい。


解答ページはこちら


参考リンク



更新履歴

'2015/12/27 SIZE_OF_ARRAYマクロの定義を修正。

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

'2011/10/18 目的の値の位置をすべて見つけ出したい場合のサンプルに、stdlib.h の #include が抜けていたのを修正。

'2011/10/1 各サンプルの Perl版を作成。

'2011/7/31 新規作成。



前の章へ(第0章 はじめに)

次の章へ(第2章 多次元配列)

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

Programming Place Plus のトップページへ


このエントリーをはてなブックマークに追加
rss1.0 取得ボタン RSS