RSS
この章の概要です。
配列は、もっとも基本的なデータ構造と言えます。実際、ほとんどのプログラミング言語では、配列を簡単に利用できるようになっています（Ｃ言語編の配列の記事はこちら⇒第２５章）
配列は、要素を連続的に並べたデータ構造です。添字（そえじ）と呼ばれる値を使って、任意の要素を直接的に参照できます。
配列を使うにあたっては、まず宣言や定義を行います。このとき、配列に格納できる要素数を指定します。Ｃ言語の場合、後から要素数を変更できません。
Ｃ言語の場合、１つの配列内には同じ型の値しか格納できません。たとえば、int型専用の配列、struct MyData型専用の配列といった具合です。
Ｃ言語の配列は次のように宣言します。
int array1[5]; // 要素数 5 の配列. 要素は不定
int array2[] = { 0, 1, 2, 3, 4 }; // 0,1,2,3,4 という要素を持つ配列. 要素数は自動判断により 5多くのプログラミング言語では、配列の要素数をあとから取得する簡単な方法があるものですが、Ｃ言語では多少の工夫が必要です（Ｃ言語編 逆引き「配列の要素数を求める」）。
具体的には、sizeof演算子を使い、「配列全体の大きさ / 配列の要素１つ分の大きさ」という計算を行います。よく使うので、関数形式マクロを用意しておくことが多いです。次のサンプルプログラムでは、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 を下限値としているものもあります。また、下限値を自由に変更できる言語もあります。Ｃ言語は、下限値を 0 としています。
添字の下限値が 0 の場合、上限値は「配列の要素数 - 1」ということになります。
下限値より小さい値、あるいは上限値より大きい値を添字にして、配列の要素をアクセスしようとする行為は不正です。Ｃ言語では未定義の動作です。
添字を使って、配列 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添字を使って、要素を直接参照できるという性質は、配列の大きな長所になっています。どの位置に何が格納されているかを把握しているのであれば、探し出す手間がまったくかからないため、非常に高速に処理できるのです。
要素を追加すると要素数が増えることになりますが、通常の配列は、宣言時点で要素数を固定しているので、単純には要素の追加は実現できません。
実現する方法としては大きく２通りあります。
１つは、実際に存在している要素の個数よりも、配列の要素数を大きくしておくことです。管理の手間はありますが、使っていない部分に要素を追加できます。
#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もう１つの方法は、realloc関数による再割り当てを行って、配列の大きさを拡張することです。この方法では、配列を malloc関数などを使って確保する必要があります。この方法の具体的なプログラムは、この後で取り上げます。
いずれの方法を使っても、要素を追加する位置が末尾以外の場合には、追加したい位置にあった要素と、その後続にあるすべての要素を、末尾へ向かってずらして、空きを作ってやらなければなりません。
要素をずらすことには、問題が２つあります。
１つは処理時間です。要素を追加するという目的から考えると、要素をずらすために割く処理時間は無駄といえます。要素を追加することが不可避であり、この処理時間が無視できないようであれば、配列を使うことを諦めて、連結リスト（第３章）などのデータ構造を検討しましょう。
もう１つは、要素をずらすと添字が変わってしまうことです。たとえば、ある要素が 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
999realloc関数の使い方についての詳細は、Ｃ言語編第３５章を参照してください。変数 tmp を経由させていることには理由があります。
要素数を管理しなければならない面倒さがあります。管理しておかないと、配列の末尾が分からないですし、要素数を増やすときに 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] = (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末尾以外の位置に要素を追加する場合、追加位置を含めた後続の要素を１つずつずらしていく作業が必要になります。この処理は非常に間違いやすく、慎重に書かなければなりません。
Ｃ言語で符号無し整数型を使う場合、特に注意が必要です。負数にならないように注意しないと、無限ループになったり、不正な位置を参照したりします。
実装の難しさの面でいえば、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]以降の要素を、１つずつ先頭側へずらすことで実現
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]以降の要素を、１つずつ先頭側へずらすことで実現
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 として適切な値が選べないかもしれません。その場合には、もう１つ配列を用意して、使用中か未使用かのフラグだけを管理させるといった対応が必要です。
要素がなくなった箇所をうまく扱う必要がある点に難しさがあります。サンプルプログラムの要素の値を出力するループでは、UNUSED かどうかを調べて、UNUSED なら無視しています。配列の要素の値を使おうとするたびに、このようなチェックをしなければなりません。
配列の中から、目的の値を持った要素を探し出したいという場面はよくあります。さらに考察してみると、望む結果のかたちにはいくつかパターンがありそうです。
データ構造の中から目的のデータを探し出すという処理は、探索アルゴリズム（サーチアルゴリズム）と呼ばれる分野にあたります。つまり、「アルゴリズムとデータ構造」の「アルゴリズム」にあたるものです。そのため、詳しい解説は、探索アルゴリズムのコーナーで行うことにして、ここではいくつかの事例に絞って簡単に解説するに留めます。
まず、先ほどの使用場面のうち、２番を実装することによって、１番は自動的に実現できます。つまり、目的の値を持った要素の個数を調べ、それが 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個見つかりました。これは単純明快でしょう。配列を先頭から順番に調べ、目的の値と一致する要素の数をカウントしています。
【上級】この方法は、線形探索と呼ばれる探索アルゴリズムです（【探索】第１章）
先ほど、目的の値があるかどうか調べることにも流用できると説明しましたが、効率面から言えば、やや非効率ではあります。というのも、存在しているかどうかだけを知りたいのであれば、１個見つけた時点で即座に 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番目にあります。
問題① 配列の中身を逆順にするプログラムを作成してください。このとき、対象となる配列自身を書き換えるタイプと、対象は書き換えずに新たな配列を作り出すタイプとを実装してください。
問題② 整数が格納された配列から、偶数の値を持つ要素数を数えるプログラムを作成してください。
問題③ ２つの配列に、共通して含まれている値を探し出すプログラムを作成してください。
SIZE_OF_ARRAYマクロの定義を修正。
≪さらに古い更新履歴を展開する≫
Programming Place Plus のトップページへ
| はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
| X で ポスト／フォロー | LINE で送る | noteで書く |
|
RSS
|
管理者情報 | プライバシーポリシー |