メモリ管理３（高度な配列操作）

配列とポインタの応用例として，多次元配列と動的配列について，メモリマップを意識しながら理解しよう．

教科書の該当範囲：第６章（ただし，メモリマップは説明なし），第10.2.4節

多次元配列

１次元配列（基本的な配列）

たとえば，３つの int 型変数からなる１次元配列 int a[3] は，次のように定義（宣言・初期化）される：

int a[3] = { 0, 1, 2 };

ちなみにこれは，次のような長たらしいソースと同じことでした：

int a[3];

a[0] = 0;
a[1] = 1;
a[2] = 2;

また，これらの配列要素 a[i]（i = 0 〜 2）は，メモリ内では要素番号順に連続的に配置される．

ここまでは，前期の内に学習済み．

多次元配列（配列の配列の ... の配列）

Ｃでは，配列の配列（２次元配列）とか，さらにその配列（３次元配列）などの多次元配列も定義できる．たとえば，３つの int 変数からなる１次元配列がさらに２つ集まってできた２次元配列 int b[2][3] は，次のように定義される：

int b[2][3] = {
	{ 0, 1, 2 },
	{ 3, 4, 5 }
};

ここで，配列[3]が２つだから 配列[3][2]...ではないことに注意しよう．この多次元配列は全体的には要素数２の配列であって，その各要素が要素数３の配列となっている． ...という考え方から，Ｃでは，添字（そえじ；要素番号；index）の並べ方は，数学の「行列」と同じように， 行番号→列番号（縦方向→横方向）の順である．

同じ「行列」とは云え，人気ラーメン店などの「待ち行列（queue）」は１次元，数学の「行列（matrix）」は２次元．両者は別物ですよ．

そしてこの例では，各配列要素は次のように初期化されることになる：（添字の変化に注意して，上と比べてみよう．）

int b[2][3];

b[0][0] = 0;	// 0 行目開始
b[0][1] = 1;
b[0][2] = 2;

b[1][0] = 3;	// 1 行目開始
b[1][1] = 4;
b[1][2] = 5;

これらの配列要素 b[i][j] （i = 0 〜 1，j = 0 〜 2）のメモリ内の配置はどうなるか？考えてみよう．

多次元配列のメモリマップ（多次元配列と１次元配列の相互変換）

実際のメモリアドレスは１次元であるため，２次元配列とはいっても，メモリの中では１次元的に（１列に並んで）格納されることになる．つまり，上の２次元配列 int b[2][3] は，メモリマップ的には，次の１次元配列 int c[6] とまったく同じことになる：

int c[6] = { 0, 1, 2, 3, 4, 5 };

または：

int c[6];		// int b[2][3]

c[0] = 0;		// b[0][0]
c[1] = 1;		// b[0][1]
c[2] = 2;		// b[0][2]

c[3] = 3;		// b[1][0]
c[4] = 4;		// b[1][0]
c[5] = 5;		// b[1][0]

ここで，配列要素の格納順序に注意しよう．配列 b[2][3] と配列 c[6] の初期化コードを比較せよ．

配列 b と c の間で要素番号の対応関係を調べてみると，結局，W 行 H 列の２次元配列 b[H][W] の要素 b[y][x] は，１次元配列 c[W*H] の要素 c[y*W + x] に対応することになる．次の図は，そのイメージである．

ところで，１次元配列 a[N] では，要素数 N を省略できる場合があった． int a[] = { ... } とか， int func(int a[], ...) のように．（ただし，「いつでも省略して良い」とは言っていない!! 省略できる場合もあるし，できない場合もある．）

ところが，２次元配列 b[H][W] の場合，横方向の要素数 W は，各要素のアドレスの計算（y*W + x）に必要となるので，省略できない．つまり，int func(int b[][], ...) とするのは間違い．

ただし，縦方向の要素数 H については省略できる．つまり，最低限， int func(int b[][W], ...) などとしなければならないだがこれでは，非対称で不格好だ．また，バッファオーバランも気になる．

したがって，２次元配列の要素数については，省略できる場合でも省略せず， int func(int b[H][W], ...) と書くべき．

なお，２次元配列を１次元配列として取り扱うには，次のようにポインタへキャストすればよい：

int b[2][3] = {{...}, {...}};
int *c;

c = (int *)b;	// ２次元配列 b[2][3] を１次元配列 c[6] とみなす

こうしておけば，２次元配列の要素 b[y][x] を１次元配列の要素 c[y*3 + x] と見なして取り扱えるようになる．

ポインタと配列の関係については，前期に学習済み．

これらの説明が本当であるか，次のタスクに取り組み，確認してみよう．

タスク１：配列次元の変換

上の説明の通り２次元配列 b[2][3] を１次元配列 c[6] として取り扱えることを確かめるため，すべての要素 b[y][x] および c[y*3 + x] を表示するプログラムを作成せよ．

ソース 2d.c：

#include <stdio.h>

int main(void)
{
	int b[2][3] = {{0, 1, 2}, {3, 4, 5}};
	int *c;
	...

	c = ...;

	for (y = ...) {
		for (x = ...) {
			printf("b[%d][%d] = %d\t", y, x, b[y][x]);
			printf("c[%d*3 + %d] = %d\n", y, x, c[y*3 + x]);
		}
	}
	...
}

動的配列

静的配列（通常の配列，固定長配列）

まず，次のような配列の利用方法は，ありがちな間違い． array-1.c：

#include <stdio.h>

int main(void)
{
	int	n;

	printf("配列のサイズ > "); 
	scanf("%d", &n);

	int a[n];	/* まちがい */

	a[0] = 123;	/* ...配列に対する何らかの処理 */

	return (0);
}

処理系によっては，これでも実行できる場合もある．本科目の実験室の環境では実行できる．しかし，Ｃ言語の標準規格（本科目で対象としている ANSI C89，ISO C90）には違反している．本実験室の環境では，この違反について，次のコンパイル方法で確認できる：

$ cc ソース.c -Wall -ansi -pedantic
0.c: 関数 ‘main’ 内:
0.c:10:9: 警告: ISO C90 は可変長の配列 ‘a’ を禁止しています
...

警告（warning）を全部（all），些細（pedantic）なことまで表示．

...残念でした．標準Ｃの通常の配列は，静的配列（固定長配列）であり，要素数を実行時には変更できない．要素数を変えるには，ソースコードを書き換え，コンパイルし直す必要がある．

...これはめんどくさいぞ．ということで，新規格の C99 では可変長でも OK になった．しかし，更に新しい規格 C11 以降では，取り下げらてしまった．（可変長配列ではメモリ領域を確保しやすい一方，解放しづらいし，狭いスタック領域しか使えないので，メモリ不足の実行時エラーに陥りやすい．）結局，可変長配列は，まだまだ，標準機能として，どこでも使える訳ではない．実験室のPCでは使えるけど，本授業では使用禁止．

いつでも何でも最新版が良い，とは限りません．枯れた技術を使えば，例えば，我社の開発用 PC では動いたのに，顧客の業務用 PC では動かない... という残念な事態を避けられる．

あーそれと，１行コメントの「//」も，実は，C99 や C++ 用であり，ANSI C では違反なので，今回だけ，封印しておきますよ．禁止まではしません．

そうすると，配列を利用するプログラムの実行中に，実際にデータを入力してみたら，配列要素の個数が足りなくなってしまった...ということはありえる話だ．Ｃ言語では，配列要素の個数をプログラムの実行中に簡単には変えられないので，とりあえずの解決策としては，充分に大きな配列を用意しておき，その一部だけを使うことになるだろう． array-2.c：（見せかけだけの可変長配列）

#include <stdio.h>

#define	SIZE	1000000		/* かなり大きめに設定しておく */

int main(void)
{
	int	a[SIZE];	/* 全部で SIZE個の要素を用意 */
	int	n;

	printf("使いたい配列のサイズ > "); 
	scanf("%d", &n);
	if (n >= SIZE) { perror("多過ぎ!!"); return (1); }

	...	/* SIZE個の内 n個だけを使用する何らかの処理 */
}

しかしこれでは， 有限なメモリ資源を無駄使いすることになってしまうだろう．また，これでも要素数が不足してしまう場合もあるだろう．

動的配列（可変長配列）

標準Ｃ言語で動的配列（可変長配列）を実現するには，次のようなメモリ管理用ライブラリ関数を利用しよう：

malloc(データサイズ）：指定されたデータサイズ分のメモリ領域を確保する．（memory allocate）

「メモリ領域を割り当てる」とも云う．通常の変数・配列に割り当てられているサイズの狭いスタック領域とは異なる場所... サイズの広いヒープ領域が利用される．

戻り値は，確保された領域の先頭アドレスとなる．ただし，確保に失敗した場合には NULL となる．

NULL は，特殊なアドレスを表すマクロ定数． fopen() でも使ったなー．

かなりテキトーな使用例：（このままでは不完全・不適切...）

char	*s;
s = malloc(sizeof(char)*100);	/* char s[100]; とほぼ同じこと */
if (s == NULL) goto ERROR;

calloc(要素数, データサイズ）：指定された要素数分だけまとめて malloc し，領域内をすべてゼロに初期化する．（clear & allocate）

注意：malloc() ではクリアしない．つまり，メモリ領域内にゴミデータが残ったままの状態となる．

かなりテキトーな使用例：（　〃　）
```
int	*a;
a = calloc(100, sizeof(int));	/* int a[100] = {}; とほぼ同じこと */
if (a == NULL) goto ERROR;
```
free(先頭アドレス)：不要になったメモリ領域を解放する．

かなりテキトーな使用例：（　〃　）

a = malloc(...);
...
free(a);

メモリの解放をしないまま，確保だけを繰り返して行くと，いつかメモリ不足に陥って，そのプログラムを中断しなければならなくなってしまう．さらに，他のアプリやシステムの動作にも影響を及ぼす場合もある．この現象は，メモリリーク（memory leak）と呼ばれており， よくある（しかも重大な）バグである． 不要になったメモリについては必ず free( ) せよ!!

スタックのメモリ領域は，関数の開始／終了の際，自動的に確保／解放される．一方，ヒープのメモリ領域は，確保も解放もコードによって明示する必要がある．

これらのライブラリ関数は，ヘッダファイル stdlib.h の中でプロトタイプ宣言されている．詳しくは，教科書 pp.253-254 を参照しよう．

なお，メモリ領域のデータサイズの指定には通常， sizeof 演算子が利用される：

sizeof(型) または sizeof(値)：指定された型・値のデータサイズ（バイト数）を計算する．

この sizeof は関数ではなく演算子ね．関数の場合，引数には値だけしか指定できない．この sizeof では，型も引数にできるので関数ではない．

結局，次のように記述するのが正解となる． array-3.c：

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

int main(void)
{
	int	n;
	int	*a;

	printf("配列のサイズ > "); 
	scanf("%d", &n);

	a = (int *)malloc(sizeof(int)*n);	/* int a[n] のメモリ領域を確保 */
	if (a == NULL) return (1);		/* 確保できなかった場合のエラー処理 */

	...

	free(a);				/* 使い終わったらメモリ領域を解放 */

	return (0);
}

固定配列では変数の宣言時にメモリ領域が確保されていた．

一方，動的配列ではポインタの宣言時には配列の実体はまだ存在せず， malloc() の実行時に配列のメモリ領域が確保される．

なお，malloc( ) と calloc( ) では，この例の (int *) のように， 戻り値の型を適切にキャストしてやる必要がある． 面倒ではあるが，その代わり，これらの関数では，あらゆる型の動的配列に適用できるようになっている．

また，プログラム終了時には自動的に free( ) してもらえるが...，コンピュータ任せにはせず，プログラマが意識的に free( ) すべきだ．特に，長期間に渡って異常終了せずに連続動作すべきシステム（例：銀行，通信，等）では，非常に重要だ．タスク２でこの関数の重要性を確認しよう．

なお，malloc( ) と free( ) の関係は，ちょうど， fopen( ) と fclose( ) の関係と同様である．要するに，前処理（準備）と後処理（片付け）だ．

前処理については，準備しなければ本処理を実行できない訳で，省略するとプログラムは動かない．準備は絶対に必要だ．

一方，後処理については，本処理が実行できた後のことなので，省略しても動いてしまう訳で，片付けは不要では？いや，その考えは甘え． 本処理が１回だけの場合なら後処理なしでも動くが，複数回の場合にはうまく行かないだろう． 後処理は次回の処理の準備のための準備として必要． 片付けを怠らないこと!!

なお，fclose() の呼出前には， NULL のチェックが必要でしたが， free() では不要．

タスク２：確保可能メモリ容量の確認

とにかく 1 MB ずつのメモリ確保 (char *)malloc(1024*1024) を free( ) せずに繰り返すプログラム malloc.c を作成し，手元のコンピュータで確保可能なメモリ容量の最大値を確認せよ．

PC自体の動作が不安定になる場合もある．覚悟して実行しよう．もし，フリーズしたら，電源ボタン長押しでシャットダウンし，再起動．

1 KB（キロバイト）＝ 1024 B（byte，バイト）
1 MB（メガバイト）＝ 1024 KB
1 GB（ギガバイト）＝ 1024 MB

ヒント：わざと間違えてメモリリークを発生させてみる問題．前期に試した fclose( ) せずに fopen( ) を繰り返すプログラム fclose1.c を参考にしよう．

誤解しないこと．「malloc( ) できたメモリ容量＝コンピュータのメモリ容量」 ではない．

確保可能 ≠ 使用可能
現代のシステムでは，仮想記憶（ディスクをメモリとして利用する機能）が装備されているので，実際のメモリ容量以上のメモリを使用可能．（つまり，「確保可能メモリ容量＞全メモリ容量」かもしれない．）
メモリ領域の一部は，他のデータやプログラムによってすでに確保されている．（つまり，「確保可能メモリ容量＜全メモリ容量」であるとも言える．）

なお，一体どっちなんだー？とか，気にしないでよい．確かなのは，メモリ容量には制限がある（＝無限ではない）ということだけだ．とにかく，malloc( ) したら，最後に必ず，free( ) せよ!!

さらに，静的配列では何MB まで使用可能か？たとえば，char a[1024*1024*...]; などとして探ってみよう．大きなメモリ領域を使いたい場合にも，動的配列が有効だとわかるだろう．

前々回に調べたスタック領域のサイズと比べてみよう．スタックは意外と狭かったよね？

タスク３：Tic-Tac-Toe の開発

Tic-tac-toe（三目並べゲーム）について，基本プログラムのソース ttt.c をダウンロードし，これを元にして，ゲーム盤を任意の大きさ n × n に変更できるように拡張せよ．ただし，標準Ｃ言語（ANSI C89）の規則に従うこと．

ヒント：静的２次元配列の部分をすべて動的１次元配列に置き換えること．メイン関数で malloc() を使う他，各ユーザ関数の引数 (int bd[N][N], ...) を (int *bd, int n, ...)， bd[y][x] を bd[y*N + x]，等々と変更．後片付けも忘れるな．

また，余裕がある人は，勝敗判定や人工知能（PC対ユーザ）などの処理を追加し，ゲームとしての完成度を高めてみよう．

本日の課題

レポートを提出せよ．

質問 Q1〜Q5 に回答し，電子メールで提出せよ．

提出方法：電子メール
- 宛先：yanagawa@kushiro-ct.ac.jp
- 件名：c-1028
- 発信者：pXXXXXX@kushiro.kosen-ac.jp
提出期限：2024.11.11月17:00（提出遅れは減点対象）
課題：
- Q1. タスク１で作成した 2d.c のソースコードをコピー＆ペーストせよ．*
- Q2. タスク２で作成した malloc.c のソースコードをコピー＆ペーストせよ．*
- Q3. タスク３で作成した ttt.c のソースコードをコピー＆ペーストせよ．*
不完全・未完成でも提出OK．減点あり．

ソースコードのインデントを適切に整えること．

余計なコード（コメント化部分など）も減点対象となる．完成したと思っても安心せず，提出前に，充分に，ソースコードをクリーニングしておくこと．
調査：
- Q4. 今回の学習時間は？* 約○時間
  学習時間＝授業時間＋自習時間． 学習の開始から調査，課題取組，レポートの完成までにかかった時間の合計，分単位は切り上げ． 課題にかかった時間だけではない． 時間の長短はレポートの成績評価には反映されないので，正直に答えてください．
- （Q5. 感想・意見など）

注意事項：

メール本文の先頭に名乗り（クラス，番号，氏名）を記述．
メール本文の末尾に署名（氏名，所属，等）を記述．
コードや実行結果は，添付や埋込みではなく，メール本文に記述．
ソースコードのインデントの乱れは減点対象．
メールの送信形式を必ず「テキスト形式 or プレーンテキスト」>に変更せよ．

「HTML」等では，せっかく整えたインデントが乱される．