Subsections
3 リストを使わない方法
3.1 固定長さの配列を使う方法
3.1.1 原理
もっとも単純な方法は，配列に入力データを格納する方法である．教科書のList 2-1(p.70)の方法である．このプログラムをプリントのリスト1にフロー チャートを図1に示す．このプログラムの大きな問題点は，
- データを10個以上，入力すると，プログラムがクラッシュする．
それで，最初から配列を大きくする方法もある．ただ，データ数が分からないと，それも 限界がある．とてつもなく大きな配列を用意することも考えられるが，そうすると次の問 題が生じる．
- メモリー領域の大部分に値が格納されないことが生じ，メモリーの無駄遣いにな る．
このようにデータ数が分からない場合，配列を使うのははなはだ無駄が生じやすい．
3.1.2 フローチャート
教科書のList 3-1(p.70-71)あるいはこのプリントのリスト1のプログラム のフローチャートを図1に示す．このプログラムは，おもに，
- キーボードの整数を配列に格納する．
- 格納された配列を合計する．
![\includegraphics[keepaspectratio,scale=1.0]{figure/flow_1.eps}](img3.png)
3.1.3 プログラム
固定長の配列を使うプログラムのリスト1に示す．これは，教科書の List 3-1(p.70-71)と同じである(転載について)．ここで使われているプログラムのテクニックは，すで に学習済みであるが，分かりにくいものだけ述べておく．
- 2行目 #include <stdlib.h>
これは，コンパイルの作業を行う前に，ソースファイルに，stdlib.hというヘッ ダーファイルを取り込む命令(プリプロセッサー) である．このプログラムでは， main関数の戻り値をEXIT_SUCCESSとしている．EXIT_SUCCESSの定義 がstdlib.hに書かれている．私のコンパイラーでは，
#define EXIT_SUCCESS 0
となっていた．戻り値を示すリスト1の32行目は，return 0;
と同じである． - 4行目 #define NMAX 10
これもプリプロセッサーで，ソースプログラムをコンパイルする前に，文字列 NMAXを10に置き換える．文字列を置き換えるので，これを文字列置換と言う．いっ ぺんに多くの文字列や値を置き換えたいときに便利である．置き換える元の文字をすべ て大文字で書くのが習慣となっている．
- 16行目 if(buf)
これには，比較の演算子がない．変数bufの値の真/偽を判断することになる．最 初，if文を学習したときのことを思い出してほしい．C言語では，
- 値が0の時は，偽である．
- 値が0以外の時は，真である．
となっていた．
- 25行目 sum=n=0
代入演算子(=)は右辺から評価していく．このことから，この文は次のように解釈する．
- n=0が実行される．すなわち，nに0が代入される．
- n=0という文の値は0となる．この0がsumに代入される．
リスト1 固定長の配列を使い合計を計算するプログラム(転載について)
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 #define NMAX 10
5
6 int main(void)
7 {
8 int buf,sum,count,n;
9 int array[NMAX];
10
11 count=0;
12 do
13 {
14 printf("整数を入力してください（0を入力すると終了）:");
15 scanf("%d",&buf);
16 if(buf)
17 {
18 array[count]=buf;
19 ++count;
20 }
21 } while(buf!=0);
22
23 /* 合計値を算出 */
24 printf("--入力されたのは以下の数です--\n");
25 for(sum=n=0;n<count;++n)
26 {
27 printf("%d \t",array[n]);
28 sum+=array[n];
29 }
30 printf("\n----\n以上の数の合計値は%dです。\n",sum);
31
32 return EXIT_SUCCESS;
33 }
3.2 配列のサイズを実行の最初に決める
3.2.1 原理
ユーザーに合計を計算するデータの数を最初に聞いて，その分，配列を用意する方法であ る．通常であれば，これは良い方法である．一般的に，よく使われる方法である．ただし，最初に決めた配列をこえてのデータ入力ができない．ユーザーの気が変わって， データ数を増加させるときに問題が発生する．さらに，ユーザー自身，データの個数が分 からないときには，対応ができない．
3.2.2 フローチャート
教科書のList 3-2(p.72)あるいはこのプリントのリスト2のプログラム のフローチャートを図2に示す．このプログラムは，おもに，
- ユーザーが指定したデータ数分の配列領域を確保する．
- キーボードの整数を配列に格納する．
- 格納された配列を合計する．
![\includegraphics[keepaspectratio,scale=1.0]{figure/flow_2.eps}](img4.png)
3.2.3 プログラム
最初に配列のサイズを決めてそれに値を代入するプログラムをリスト2 に示す．これは，教科書のList 3-2(p.72)と同じである(転載について)．ここで使われているプログラム のテクニックは，次の通りである．
- 12行目 array=(int *)malloc(sizeof(int)*count);
少々複雑に見えるが，処理される順に見ていけば簡単である．
- 最初にsizeof(int)が評価される．関数sizeof()は，型のバイト数を 返す．ここでは，整数型intのバイト数である4が返される．
- 次に，この4とデータ数であるcountの乗算が行われる．この結果は，デー タを格納するために必要なバイト数の計算になっている．
- malloc()関数は，Memory ALLOCate(記憶割付)の略で，引数で渡 されたバイト数のメモリーを確保して，その先頭のポインター(アドレス)を返す．
- (int *)はキャストと呼ばれる強制型変換である．mallocで返される ポインターは強制的に整数型としている．従って，ポインターを+1加算すると， アドレスは4つ進むことになる．
- 整数型のポインター(アドレス)を整数型のポインターarrayに代入してい る．
- 7行目 int *arrayと21行目 array[n]
ポインターで宣言しているものを配列として使っている．これは，配列がどのように処 理されているか，考えればよく分かる．配列array[n]は，*(array+n)と評価 される．すなわち，配列array[n]は，ポインターarrayにn加算したポ インター(アドレス)が示す値と言うことである．このようなことから，配列で宣言して いなくても，配列のように使うことができるのである．
- 35行目 free(array);
関数free()は，そのプログラムで使用しているメモリー領域を開放するた めにある．ここでは，12行目のmallocで確保された領域を解放している．
リスト2 最初に配列の サイズを決めてから値を代入するプログラム(転載について)
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 int main(void)
5 {
6 int buf,sum,count,n,i;
7 int *array;
8
9 /* 入力するデータの個数を最初に聞いて，必要なメモリを確保 */
10 printf("何個の数値を入力しますか：");
11 scanf("%d",&count);
12 array=(int*)malloc(sizeof(int)*count);
13
14 n=0;
15 do
16 {
17 printf("整数を入力してください（0を入力すると終了）:");
18 scanf("%d",&buf);
19 if(buf)
20 {
21 array[n]=buf;
22 ++n;
23 }
24 } while(buf!=0);
25
26 /* 合計値を算出 */
27 printf("--入力されたのは以下の数です--\n");
28 for(sum=i=0;i<n;++i)
29 {
30 printf("%d\t",array[i]);
31 sum += array[i];
32 }
33 printf("\n----\n以上の数の合計値は %d です。\n",sum);
34
35 free(array);
36 return EXIT_SUCCESS;
37 }
3.3 実行時に配列のサイズを拡張する
3.3.1 原理
データの数が分からないので，最初に小さな配列を用意する．データ数が多く不足した 場合，さらに大きな配列を用意する方法である．この方法も良さそうですが，以下のような問題があります．
- 配列のコピー回数が多く，コストがかかりすぎる．
- コピー回数を減らすために，一度に多くの配列の領域を確保すると，大きな使わ れないメモリー領域ができてしまう可能性がある．
3.3.2 フローチャート
教科書のList 3-3(p.74)あるいはこのプリントのリスト3のプログラム のフローチャートを図3に示す．このプログラムは，おもに，
- キーボードの整数を配列に格納する．
- 配列の範囲を超える場合，より多くのメモリーを確保する．
- 確保された多くのメモリーに元のデータをコピーする．
- 不要になったメモリー領域は，解放する．
- 格納された配列を合計する．
![\includegraphics[keepaspectratio,scale=1.0]{figure/flow_3.eps}](img5.png)
3.3.3 プログラム
リスト3に示す．これは，教科書のList 3-3(p.74)と同じである(転載について)．このプログラムで使われている主なテクニックは，以下の通りである．
- 3行目 #include <memory.h>
これは，30行目のmemcpy()関数を使うために必要で，その関数の宣言などが書か れている．
- 30行目 memcpy(temp, array, sizeof(int)*size)
memcpy()関数は，MEMory CoPY(メモリー複写)の略で，メモリーの内容 をコピーする．ここでは，ポインターarrayが示す場所から4*sizeバイト分 のデータを，先頭をポインターtempが示す場所としてコピーする．
リスト3 実行時に配列 のサイズを拡張する方法(転載について)
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <memory.h>
4
5 int main(void)
6 {
7 int buf,sum,count,n,size;
8 int *array,*temp;
9
10 /* 最初の配列サイズは10 */
11 size=10;
12 array=(int*)malloc(sizeof(int)*size);
13
14 count=0;
15 do
16 {
17 printf("整数を入力してください（0を入力すると終了）:");
18 scanf("%d",&buf);
19 if(buf)
20 {
21 array[count]=buf;
22 ++count;
23 /* 配列が満杯になったら，倍の大きさに拡張する */
24 if(count==size)
25 {
26 /* 新しい大きなメモリブロックを確保して，
27 元の内容をコピー。
28 realloc()を使っても同様の作業が行われる */
29 temp=(int*)malloc(sizeof(int)*size*2);
30 memcpy(temp,array,sizeof(int)*size);
31 free(array);
32 array=temp;
33 size*=2;
34 }
35 }
36 } while(buf!=0);
37
38 /* 合計値を算出 */
39 printf("--入力されたのは以下の数です--\n");
40 for(sum=n=0;n<count;++n)
41 {
42 printf("%d\t",array[n]);
43 sum+=array[n];
44 }
45 printf("\n----\n以上の数の合計値は%dです。\n",sum);
46
47 free(array);
48 return EXIT_SUCCESS;
49 }
[転載について]
このペー
ジ中のリスト1とリスト2，リスト3のプロ
グラムは，教科書として使用している以下の書籍
| 書名 | プログラミングの宝箱 アルゴリズムとデータ構造 ISBN4-7973-2419-8 |
| 著作者 | 紀平拓男・春日伸弥 |
| 出版社 | ソフトバンク パブリッシング株式会社 |