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

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

この章の概要

この章の概要です。


配列とは

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

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

配列を使うにあたっては、まず宣言や定義を行います。このとき、配列に格納できる要素数を指定します。C言語の場合、後から要素数を変更できません。

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

C言語の配列は次のように宣言します。

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

多くのプログラミング言語では、配列の要素数をあとから取得する簡単な方法があるものですが、C言語では多少の工夫が必要です(C言語編 逆引き「配列の要素数を求める」)。

具体的には、sizeof演算子を使い、「配列全体の大きさ / 配列の要素1つ分の大きさ」という計算を行います。よく使うので、関数形式マクロを用意しておくことが多いです。次のサンプルプログラムでは、SIZE_OF_ARRAYマクロを定義しています。

#include <stdio.h>

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

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

    printf( "%zu\n", SIZE_OF_ARRAY(array) );

    return 0;
}

実行結果:

5

要素の参照

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

添字は、プログラミング言語の種類によっては、整数でなくてもいい場合もありますが、一般的には整数を使います。特に、添字に文字列を使う配列は、連想配列と呼ばれます。

添字の下限値は、ほとんどのプログラミング言語では 0 ですが、1 を下限値としているものもあります。また、下限値を自由に変更できる言語もあります。C言語は、下限値を 0 としています。

添字の下限値が 0 の場合、上限値は「配列の要素数 - 1」ということになります。

下限値より小さい値、あるいは上限値より大きい値を添字にして、配列の要素をアクセスしようとする行為は不正です。C言語では未定義の動作です。

添字を使って、配列 array の 3番目の要素をアクセスするコードは、次のようになります。

array[3] = 10;       // array[3] に 10 を代入
int n = array[3];    // n に array[3] の値を代入

添字に変数を用いることによって、さらに柔軟なアクセスが可能です。配列の要素を順番にアクセスする処理(走査)が典型的です。

#include <stdio.h>

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

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

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

    return 0;
}

実行結果:

0
1
2
3
4

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


要素の追加

要素を追加すると要素数が増えることになりますが、通常の配列は、宣言時点で要素数を固定しているので、単純には要素の追加は実現できません。

実現する方法としては大きく2通りあります。

1つは、実際に存在している要素の個数よりも、配列の要素数を大きくしておくことです。管理の手間はありますが、使っていない部分に要素を追加できます。

#include <stdio.h>

int main(void)
{
    // 実在する要素は 5個だが、配列は要素数 10 で宣言
    int array[10] = { 0, 1, 2, 3, 4 };
    size_t count = 5;

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

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

    return 0;
}

実行結果:

0
1
2
3
4
999

もう1つの方法は、realloc関数による再割り当てを行って、配列の大きさを拡張することです。この方法では、配列を malloc関数などを使って確保する必要があります。この方法の具体的なプログラムは、この後で取り上げます。

いずれの方法を使っても、要素を追加する位置が末尾以外の場合には、追加したい位置にあった要素と、その後続にあるすべての要素を、末尾へ向かってずらして、空きを作ってやらなければなりません。

要素をずらすことには、問題が2つあります。

1つは処理時間です。要素を追加するという目的から考えると、要素をずらすために割く処理時間は無駄といえます。要素を追加することが不可避であり、この処理時間が無視できないようであれば、配列を使うことを諦めて、連結リスト第3章)などのデータ構造を検討しましょう。

もう1つは、要素をずらすと添字が変わってしまうことです。たとえば、ある要素が 8番目にあるという情報を、変数に保存しておくことで記憶していたとすると、要素の位置がずれるのと同時に、その変数の値も更新されなければなりません。そのような管理は間違いやすく、バグの原因になりやすいです。

realloc関数を使う方法では、要素を指すポインタでも問題が起こります。realloc関数を使うと、メモリアドレスが変化するので、要素をずらさないとしても、ポインタが指し示す先に元の要素はなくなっている可能性があります。要素を指すポインタが必要なら、realloc関数を呼んだ後で、取得しなおす必要があります。

ここからは、realloc関数を使って、末尾へ要素を追加する実例と、末尾以外へ追加する実例を取り上げます。

末尾への追加

末尾への追加は、要素をずらす必要がないので、比較的簡単です。

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

int main(void)
{
    size_t size = 5;
    int* array = malloc( sizeof(int) * size );
    for( size_t i = 0; i < size; ++i ){
        array[i] = i;
    }

    // 末尾に要素を追加したいので、要素数を増やす
    ++size;
    int* tmp = realloc( array, sizeof(int) * size );
    if( tmp == NULL ){
        free( array );
        exit( EXIT_FAILURE );
    }
    array = tmp;
    array[size - 1] = 999;

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

    free( array );

    return 0;
}

実行結果:

0
1
2
3
4
999

realloc関数の使い方についての詳細は、C言語編第35章を参照してください。変数 tmp を経由させていることには理由があります。

要素数を管理しなければならない面倒さがあります。管理しておかないと、配列の末尾が分からないですし、要素数を増やすときに realloc関数の第2引数に渡すべき値もわからなくなってしまいます。

【上級】ここでは realloc関数で要素を1つ分だけ増やしていますが、再割り当ての処理は時間がかかるので、頻繁に追加が起こるのなら一気にたくさん増やしたほうがいいでしょう。

末尾以外への追加

末尾以外への追加のときには、要素をずらす作業が必要です。

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

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

int main(void)
{
    size_t size = 5;
    int* array = malloc( sizeof(int) * size );
    for( size_t i = 0; i < size; ++i ){
        array[i] = (int)i;
    }

    // 要素を追加したいので、要素数を増やす
    ++size;
    int* tmp = realloc( array, sizeof(int) * size );
    if( tmp == NULL ){
        free( array );
        exit( EXIT_FAILURE );
    }
    array = tmp;

    // 先頭に要素を追加する
    // まず、array[0]~array[size-2] にある要素を、array[1]~array[size-1] にずらし、
    // そのあとで、array[0] に新しい要素を代入する。
    for( size_t i = size - 1; i > 0; --i ){
        array[i] = array[i - 1];
    }
    array[0] = 999;

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

    free( array );

    return 0;
}

実行結果:

999
0
1
2
3
4

末尾以外の位置に要素を追加する場合、追加位置を含めた後続の要素を1つずつずらしていく作業が必要になります。この処理は非常に間違いやすく、慎重に書かなければなりません。

C言語で符号無し整数型を使う場合、特に注意が必要です。負数にならないように注意しないと、無限ループになったり、不正な位置を参照したりします。

実装の難しさの面でいえば、memmove関数を使ったほうが簡単でしょう。

// string.h のインクルードが必要
memmove( &array[1], &array[0], sizeof(int) * (size - 1) );

変数size から 1 引いているのは、実際に要素を代入する前に size を +1 しているからです。ここは実装次第です。

コピー先とコピー元は重なり合っているので、memcpy関数はダメです。


要素の削除

要素の削除に関しても、要素の追加と同じ問題があります。末尾以外の要素を削除すると、削除された要素より後ろの要素を、先頭側へ向かってずらす必要がありそうです。

単純に考えればその通りですが、少し工夫して、要素をずらさずに削除を実現する手法もあります。そちらは後述するとして、まずは要素をずらす方法での実装を見ていきます。

次のサンプルプログラムは、要素数 10 の配列から、3番目にある要素を削除しています。

#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 };

    // 3番目の要素を削除する
    // array[4]以降の要素を、1つずつ先頭側へずらすことで実現
    for( size_t i = 4; i < SIZE_OF_ARRAY(array); ++i ){
        array[i - 1] = array[i];
    }

    // 配列の全要素を出力する
    for( size_t 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

要素をずらす処理は、memmove関数を使うこともできます。

// string.h のインクルードが必要
size_t i = 3;  // 挿入位置の添字
memmove( &array[i], &array[i + 1], sizeof(int) * (SIZE_OF_ARRAY(array) - i + 1) );

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

次のサンプルプログラムは、実際に存在している要素の個数を、変数count で管理しています。要素数が必要な箇所では、この変数の値を使うようにすれば、要素の削除後に取り残された部分を無視できます。

#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 };
    size_t count = SIZE_OF_ARRAY(array);

    // 3番目の要素を削除する
    // array[4]以降の要素を、1つずつ先頭側へずらすことで実現
    for( size_t i = 4; i < count; ++i ){
        array[i - 1] = array[i];
    }
    --count;

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

    return 0;
}

実行結果:

0
1
2
4
5
6
7
8
9

要素をずらさずに削除する

削除した要素より後ろにあった要素をずらさずに、そのまま残しておくという解決策もあり得ます。

要素が削除された箇所に、削除済みであるという何かしらのマークを付けます。

#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 };

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

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

    return 0;
}

実行結果:

0
1
2
4
5
6
7
8
9

サンプルプログラムでは、UNUSED という記号定数を用意し、これを未使用な領域であることを示す値として使っています。UNUSED の具体的な値として -1 を選択していますが、これはもちろん、本物の要素の値として -1 がないことが前提です。

この辺りは悩ましいところで、すべての値があり得る場合には、UNUSED として適切な値が選べないかもしれません。その場合には、もう1つ配列を用意して、使用中か未使用かのフラグだけを管理させるといった対応が必要です。

要素がなくなった箇所をうまく扱う必要がある点に難しさがあります。サンプルプログラムの要素の値を出力するループでは、UNUSED かどうかを調べて、UNUSED なら無視しています。配列の要素の値を使おうとするたびに、このようなチェックをしなければなりません。


要素の探索

配列の中から、目的の値を持った要素を探し出したいという場面はよくあります。さらに考察してみると、望む結果のかたちにはいくつかパターンがありそうです。

  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 };

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

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

    return 0;
}

実行結果:

2個見つかりました。

これは単純明快でしょう。配列を先頭から順番に調べ、目的の値と一致する要素の数をカウントしています。

【上級】この方法は、線形探索と呼ばれる探索アルゴリズムです(【探索】第1章

先ほど、目的の値があるかどうか調べることにも流用できると説明しましたが、効率面から言えば、やや非効率ではあります。というのも、存在しているかどうかだけを知りたいのであれば、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 };

    // 7 を探す
    for( size_t 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 };

    // 7 を探す
    for( size_t 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 };

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


    // 7 を探す
    for( size_t 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( size_t i = 0; i < next_result_index; ++i ){
            printf( "%zu番目にあります。\n", result_array[i] );
        }
    }

    free( result_array );

    return 0;
}

実行結果:

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

まとめ


練習問題

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

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

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


解答ページはこちら


参考リンク


更新履歴

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

≪さらに古い更新履歴を展開する≫



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

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

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

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポストフォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る