データ構造 - 配列
配列(Array)は、最も基礎的であり、最もよく使われるデータ構造の一つです。
配列とは、同じ型の要素がメモリ上に連続して格納された集合です。
配列の定義とメモリレイアウト
C言語では、配列を宣言するとメモリ上に連続した領域が割り当てられ、各要素にはインデックスで直接アクセスできます。
上の図は、5つのint要素を持つ配列のメモリ上のレイアウトを示しています。開始アドレスを0x1000、各intを4バイトとすると、次のようになります:
- arr[0]アドレス0x1000に位置します
- arr[1]アドレス0x1004(0x1000 + 4)に位置します
- arr[i]アドレス0x1000 + i × 4 に位置します
この連続して格納される特性により、配列は開始アドレス + オフセットという方法で、O(1) 時間で任意の要素にアクセスできます。
1次元配列
例
#include <stdio.h>
int main() {
/* 1次元配列を宣言して初期化する */
int arr[5] = {10, 20, 30, 40, 50};
/* 各要素に順にアクセスする */
printf("配列要素: ");
for (int i = 0; i < 5; i++) {
printf("%d ", arr[i]);
}
printf("\n"); /* 出力: 配列要素: 10 20 30 40 50 */
/* インデックスで直接アクセス、時間計算量 O(1) */
printf("arr[2] = %d\n", arr[2]); /* 出力: 30 */
return 0;
}
int main() {
/* 1次元配列を宣言して初期化する */
int arr[5] = {10, 20, 30, 40, 50};
/* 各要素に順にアクセスする */
printf("配列要素: ");
for (int i = 0; i < 5; i++) {
printf("%d ", arr[i]);
}
printf("\n"); /* 出力: 配列要素: 10 20 30 40 50 */
/* インデックスで直接アクセス、時間計算量 O(1) */
printf("arr[2] = %d\n", arr[2]); /* 出力: 30 */
return 0;
}
多次元配列
C言語は多次元配列をサポートしており、最も一般的なのは2次元配列で、行列などのテーブルデータを表すのに使われます。
2次元配列はメモリ上では依然として行ごとに連続して格納されており(行優先格納)、行と列のインデックスの計算によって2次元のビューにマッピングされます。
例
#include <stdio.h>
int main() {
/* 3行4列の2次元配列を宣言 */
int matrix[3][4] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}
};
/* 2次元配列を走査:外側のループで行、内側のループで列を処理 */
printf("2次元配列 (3×4 行列):\n");
for (int i = 0; i < 3; i++) { /* i は行インデックス */
for (int j = 0; j < 4; j++) { /* j は列インデックス */
printf("%2d ", matrix[i][j]);
}
printf("\n");
}
/* 特定の要素にアクセス:matrix[行][列] */
printf("matrix[1][2] = %d\n", matrix[1][2]); /* 出力: 7 */
return 0;
}
int main() {
/* 3行4列の2次元配列を宣言 */
int matrix[3][4] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}
};
/* 2次元配列を走査:外側のループで行、内側のループで列を処理 */
printf("2次元配列 (3×4 行列):\n");
for (int i = 0; i < 3; i++) { /* i は行インデックス */
for (int j = 0; j < 4; j++) { /* j は列インデックス */
printf("%2d ", matrix[i][j]);
}
printf("\n");
}
/* 特定の要素にアクセス:matrix[行][列] */
printf("matrix[1][2] = %d\n", matrix[1][2]); /* 出力: 7 */
return 0;
}
2次元配列のメモリアドレス計算式:
元素地址 = 起始地址 + (i × 列数 + j) × sizeof(元素类型)。ここで i は行インデックス、j は列インデックスです。
配列の基本操作
上の図は、配列の挿入と削除操作の主要な手順を示しています。挿入時は、対象位置以降の要素を順に後方へ移動してスペースを確保します。削除時は、対象位置以降の要素を順に前方へ移動して空いた部分を埋めます。
走査
例
#include <stdio.h>
/* 配列の全要素を走査して出力
時間計算量:O(n)、n は配列長 */
void traverse(int arr[], int n) {
printf("走査結果: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {15, 28, 43, 56, 71};
int n = sizeof(arr) / sizeof(arr[0]); /* 配列の長さを計算 */
traverse(arr, n);
return 0;
}
/* 配列の全要素を走査して出力
時間計算量:O(n)、n は配列長 */
void traverse(int arr[], int n) {
printf("走査結果: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {15, 28, 43, 56, 71};
int n = sizeof(arr) / sizeof(arr[0]); /* 配列の長さを計算 */
traverse(arr, n);
return 0;
}
挿入
例
#include <stdio.h>
/* 配列の指定位置に要素を挿入する
引数:arr 配列, n 現在の要素数, pos 挿入位置(0-based),
value 挿入する値, capacity 配列の総容量
時間計算量:O(n)、最悪の場合 n 個の要素を移動する必要があります
戻り値:挿入後の要素数、容量不足の場合は -1 を返す */
int insert(int arr[], int n, int pos, int value, int capacity) {
if (n >= capacity) {
printf("配列が満杯のため、挿入できません\n");
return -1;
}
if (pos < 0 || pos > n) {
printf("挿入位置が無効です\n");
return -1;
}
/* 後ろから前へ、pos 以降の要素を1つずつ後方へ移動 */
for (int i = n; i > pos; i--) {
arr[i] = arr[i - 1];
}
arr[pos] = value; /* 新しい位置にデータを書き込む */
return n + 1; /* 要素数を1増やす */
}
int main() {
int arr[10] = {10, 20, 30, 40}; /* 容量は10、現在4つの要素がある */
int n = 4;
printf("挿入前: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n"); /* 出力: 挿入前: 10 20 30 40 */
n = insert(arr, n, 2, 25, 10); /* インデックス2に25を挿入 */
printf("挿入後: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n"); /* 出力: 挿入後: 10 20 25 30 40 */
return 0;
}
/* 配列の指定位置に要素を挿入する
引数:arr 配列, n 現在の要素数, pos 挿入位置(0-based),
value 挿入する値, capacity 配列の総容量
時間計算量:O(n)、最悪の場合 n 個の要素を移動する必要があります
戻り値:挿入後の要素数、容量不足の場合は -1 を返す */
int insert(int arr[], int n, int pos, int value, int capacity) {
if (n >= capacity) {
printf("配列が満杯のため、挿入できません\n");
return -1;
}
if (pos < 0 || pos > n) {
printf("挿入位置が無効です\n");
return -1;
}
/* 後ろから前へ、pos 以降の要素を1つずつ後方へ移動 */
for (int i = n; i > pos; i--) {
arr[i] = arr[i - 1];
}
arr[pos] = value; /* 新しい位置にデータを書き込む */
return n + 1; /* 要素数を1増やす */
}
int main() {
int arr[10] = {10, 20, 30, 40}; /* 容量は10、現在4つの要素がある */
int n = 4;
printf("挿入前: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n"); /* 出力: 挿入前: 10 20 30 40 */
n = insert(arr, n, 2, 25, 10); /* インデックス2に25を挿入 */
printf("挿入後: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n"); /* 出力: 挿入後: 10 20 25 30 40 */
return 0;
}
削除
例
#include <stdio.h>
/* 配列の指定位置の要素を削除する
引数:arr 配列, n 現在の要素数, pos 削除位置(0-based)
時間計算量:O(n)、最悪の場合 n 個の要素を移動する必要があります
戻り値:削除後の要素数 */
int delete(int arr[], int n, int pos) {
if (n <= 0) {
printf("配列が空のため、削除できません\n");
return 0;
}
if (pos < 0 || pos >= n) {
printf("削除位置が無効です\n");
return n;
}
/* 前から後ろへ、pos 以降の要素を1つずつ前方へ移動 */
for (int i = pos; i < n - 1; i++) {
arr[i] = arr[i + 1];
}
return n - 1; /* 要素数を1減らす */
}
int main() {
int arr[10] = {10, 20, 30, 40, 50};
int n = 5;
printf("削除前: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n"); /* 出力: 削除前: 10 20 30 40 50 */
n = delete(arr, n, 2); /* インデックス2の要素(30)を削除 */
printf("削除後: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n"); /* 出力: 削除後: 10 20 40 50 */
return 0;
}
/* 配列の指定位置の要素を削除する
引数:arr 配列, n 現在の要素数, pos 削除位置(0-based)
時間計算量:O(n)、最悪の場合 n 個の要素を移動する必要があります
戻り値:削除後の要素数 */
int delete(int arr[], int n, int pos) {
if (n <= 0) {
printf("配列が空のため、削除できません\n");
return 0;
}
if (pos < 0 || pos >= n) {
printf("削除位置が無効です\n");
return n;
}
/* 前から後ろへ、pos 以降の要素を1つずつ前方へ移動 */
for (int i = pos; i < n - 1; i++) {
arr[i] = arr[i + 1];
}
return n - 1; /* 要素数を1減らす */
}
int main() {
int arr[10] = {10, 20, 30, 40, 50};
int n = 5;
printf("削除前: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n"); /* 出力: 削除前: 10 20 30 40 50 */
n = delete(arr, n, 2); /* インデックス2の要素(30)を削除 */
printf("削除後: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n"); /* 出力: 削除後: 10 20 40 50 */
return 0;
}
検索
順序が整っていない配列から目的の値を探す最も直接的な方法は、配列全体を走査して1つずつ比較することです。これを線形探索と呼びます。
例
#include <stdio.h>
/* 線形探索:配列内で目的の値を検索
時間計算量:O(n)、最悪の場合、配列全体を走査する必要があります
戻り値:目的の要素のインデックス、見つからない場合は -1 を返す */
int search(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; /* 見つかった場合はインデックスを返す */
}
}
return -1; /* 見つからない場合 */
}
int main() {
int arr[] = {43, 17, 89, 25, 61};
int n = 5;
int idx = search(arr, n, 89);
if (idx != -1) {
printf("目標値 89 を見つけました。インデックスは %d です\n", idx); /* 出力: 目標値 89 を見つけました。インデックスは 2 */
} else {
printf("目標値が見つかりませんでした\n");
}
return 0;
}
/* 線形探索:配列内で目的の値を検索
時間計算量:O(n)、最悪の場合、配列全体を走査する必要があります
戻り値:目的の要素のインデックス、見つからない場合は -1 を返す */
int search(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; /* 見つかった場合はインデックスを返す */
}
}
return -1; /* 見つからない場合 */
}
int main() {
int arr[] = {43, 17, 89, 25, 61};
int n = 5;
int idx = search(arr, n, 89);
if (idx != -1) {
printf("目標値 89 を見つけました。インデックスは %d です\n", idx); /* 出力: 目標値 89 を見つけました。インデックスは 2 */
} else {
printf("目標値が見つかりませんでした\n");
}
return 0;
}
配列の長所と短所
| 長所 | 説明 |
|---|---|
| O(1) ランダムアクセス | インデックスを使えば定数時間で任意の要素にアクセスでき、これが配列の最大の利点です |
| メモリ連続 | 連続して格納することでCPUキャッシュのヒット(空間的局所性)が向上し、アクセス効率が高まります |
| 実装が簡単 | 構文が直感的で、ほとんどのプログラミング言語でネイティブにサポートされている型です |
| 短所 | 説明 |
|---|---|
| サイズ固定 | C言語の静的配列はコンパイル時にサイズが決まり、動的に拡張できません |
| 挿入/削除が遅い | 配列の途中で要素を挿入または削除する場合、多くの要素を移動する必要があり、時間計算量は O(n) です |
| スペースの無駄 | 宣言した配列が大きすぎて実際の使用量が少ない場合、メモリの無駄が生じます |
こうした限界こそが、次の章で学ぶ、より柔軟な動的構造を生み出しました——リンクリスト。
操作の計算量まとめ
| 操作 | 時間計算量 | 説明 |
|---|---|---|
| インデックスによるアクセス | O(1) | アドレスを直接計算する |
| 末尾に挿入 | O(1) | 要素の移動が不要 |
| 先頭/途中に挿入 | O(n) | 後続の要素を移動する必要がある |
| 末尾の要素を削除 | O(1) | 要素の移動が不要 |
| 先頭/途中の要素を削除 | O(n) | 後続の要素を移動する必要がある |
| 線形探索 | O(n) | 1つずつ比較する |
| 二分探索(ソート済み配列) | O(log n) | 配列がソート済みである必要がある |