配列とその応用

Ⅰ．配列とその応用

配列（ array ）
1. 1 次元配列
  
  　　配列として宣言された変数（ x1，x2 ）は，ポインタ（ x3, x4 ）のような働きをしますが，配列変数をポインタへ代入する（ 05 行目），ポインタを他のポインタに代入する（ 12 行目）のは可能であっても，配列変数を他の配列変数に代入すること（ x2 = x1 など）は許されない，x3++ は許されるが x1++ は許されない，など，多少ポインタとは異なります．
```
01	#include <stdio.h>
02	int main()
03	{
04		int x1[] = {1, 2, 3}, x2[3], *x3, *x4 = new int [3];
05		x3 = x2;   // x3 = &x2[0];
06		for (int i1 = 0; i1 < 3; i1++) {
07			x2[i1] = x1[i1];   // x2 = x1; は許されない
08			x4[i1] = 10 * (i1 + 1);
09		}
10		for (int i1 = 0; i1 < 3; i1++)
11			printf("i1 %d x1 %d x2 %d x3 %d x4 %d\n", i1, x1[i1], x2[i1], x3[i1], x4[i1]);
12		x3 = x4;
13		for (int i1 = 0; i1 < 3; i1++)
14			printf("i1 %d x1 %d x2 %d x3 %d x4 %d\n", i1, x1[i1], x2[i1], x3[i1], x4[i1]);
15		return 0;
16	}
				
```
  04 行目
  
  　　配列 x1，x2 を定義し，x1 に対しては初期設定を行っています．また，x3，x4 をポインタ変数として定義し，x4 には，3 つの int 型データを記憶できる領域を確保し，そのアドレスで初期設定を行っています．この結果，確保された領域のデータを，x4[i] （ i = 0, 1, 2 ）のように，配列変数と同じような参照が可能になります．
  
  05 行目
  
  　　x2 を x3 に代入しています．x2 は配列変数ですが，ポインタと非常に似た働きをします．この代入は，コメントに書かれたようなことを意味し，x2 と x3 が同じ配列を指すことになります．その結果，x2 の要素の値を変更すれば，x3 の対応する要素の値も変化します（逆も同様）
  
  06 行目～ 09 行目
  
  　　「 x2 = x1; 」のような操作は許されないため，07 行目において，x1 の各要素の値を x2 の対応する要素に代入しています．また，x4 が指す領域の値を設定しています（ 08 行目）．この結果，10，11 行目の文によって，以下に示すような結果が得られます．また，概念的には，その下に示した図のような状態になります．
  i1 0 x1 1 x2 1 x3 1 x4 10 i1 1 x1 2 x2 2 x3 2 x4 20 i1 2 x1 3 x2 3 x3 3 x4 30
  
  12 行目
  
  　　x4 を x3 に代入しています．その結果，x3 と x4 が同じ配列を指すことになり，x3 の要素の値を変更すれば，x4 の対応する要素の値も変化します（逆も同様）．13，14 行目の文によって，以下に示すような結果が得られ，概念的には，その下に示した図のような状態になります．
  i1 0 x1 1 x2 1 x3 10 x4 10 i1 1 x1 2 x2 2 x3 20 x4 20 i1 2 x1 3 x2 3 x3 30 x4 30
  　　また，以下のプログラムに示すように，複数のデータを記憶するために配列を使用しても，標準関数 malloc や new 演算子を使用しても，上で述べた点を除き，各要素の参照方法はほとんど同じです．ただし，確保可能な領域の大きさは異なってくる可能性があります（コンパイラやコンピュータによって異なる可能性がある）．例えば，以下に示すプログラムの断片において，配列を使用する場合は正しく動作せず，malloc や new 演算子を使用する場合は正しく動作します．これは，new 演算子を使用した場合，その領域が，プログラム実行時に任意に確保や解放を繰り返すことができるメモリ領域（ヒープ領域，ヒープメモリ，heap memory ）に確保されるからです．
```
//	int x[5000000];   // 実行できない
//	int *x = (int *)malloc(5000000 * sizeof(int));   // 実行可
	int *x = new int [5000000];   // 実行可
	x[4999999] = 100;
	printf("%d\n", x[4999999]);
				
```
2. 2 次元配列
  
  　　多次元配列の場合も，1 次元配列の場合と同様，配列を使用しても，new 演算子を使用しても，各要素の参照方法に関する限りほとんど同じです．大きな違いは，連続した領域が確保されるか否かといった点です．連続した領域が確保されるか否かといった問題は，プログラムの実行時間に大きな影響を与える場合があります（連続領域の方が実行時間が短い）．
```
01	#include <stdio.h>
02	int main()
03	{
04		int x1[][2] = {{1, 2}, {3, 4}, {5, 6}}, *x2, **x3, **x4;
05		x2 = &x1[0][0];   // x2 = x1[0]; でも可
06	//		m 行 n 列の (i, j) 要素の位置： i * n + j
07		for (int i1 = 0; i1 < 3; i1++) {
08			for (int i2 = 0; i2 < 2; i2++)
09				printf("x1 %d x2 %d\n", x1[i1][i2], x2[i1*2+i2]);
10		}
11		x3 = new int *[3];
12		for (int i1 = 0; i1 < 3; i1++)
13			x3[i1] = new int [2];
14		x4 = x3;
15		x3[0][0] = 10;
16		x3[0][1] = 20;
17		x3[1][0] = 30;
18		x3[1][1] = 40;
19		x3[2][0] = 40;
20		x3[2][1] = 50;
21		for (int i1 = 0; i1 < 3; i1++) {
22			for (int i2 = 0; i2 < 2; i2++)
23				printf("x3 %d x4 %d\n", x3[i1][i2], x4[i1][i2]);
24		}
25	//		以下は許されない（x3[0][0]，x3[0][1] だけは参照できる）
26		int *x5 = &x3[0][0];   // int *x5 = x3[0]; でも可
27		for (int i1 = 0; i1 < 3; i1++) {
28			for (int i2 = 0; i2 < 2; i2++)
29				printf("x3 %d x5 %d\n", x3[i1][i2], x5[i1*2+i2]);
30		}
31		return 0;
32	}
				
```
  04 行目
  
  　　3 行 2 列の 2 次元配列 x1，及び，3 つのポインタ変数 x2，x3，x4 を定義しています．初期設定を行う場合，最も左側の要素数だけは省略可能です（省略しなくても構わない）．
  
  05 行目
  
  　　配列宣言を行った場合，全ての要素は連続した領域に確保されるため，その全体，または，一部を 1 次元配列として扱うことができます．x2 には，連続領域の先頭アドレスが代入されるため，x2 は，要素数が 6 個の 1 次元配列となります．また，x2 = $(x1[1][1]) のような代入を行えば，変数 x2 は，要素数が 3 である 1次元配列となります．勿論，x2 は，x1 と同じ領域を指しているため，x2 を介して要素の値を変更すれば，対応する x1 の要素の値も変化します（逆も同様）．この行を実行した結果，概念的には，右図のような結果になります．
  
  07 行目～ 10 行目
  
  　　x1 及び x2 の値を出力しています．06 行目のコメントに記したように，m 行 n 列の 2 次元配列を 1 次元配列としてみた場合，2 次元配列の i 行 j 列要素は，1 次元配列の i * n + j 要素に対応します．出力結果は以下に示すとおりです．
  x1 1 x2 1 x1 2 x2 2 x1 3 x2 3 x1 4 x2 4 x1 5 x2 5 x1 6 x2 6
  
  11 行目
  
  　　int 型に対するポインタを記憶する領域を 3 個確保し（ x3[0]，x3[1]，x3[2] ），その先頭アドレスを x3 に代入しています．
  
  12 行目～ 13 行目
  
  　　int 型データを記憶する領域を 2 個確保し，そのアドレスを，11 行目で確保したポインタを記憶する各領域（ x3[i1] ）に代入しています．この結果，概念的に，右図のような状態になります（ x4，x5 の部分，及び，10，20，･･･など，各要素の値は除く）
  
  14 行目
  
  　　この代入によって，x3 と x4 は，同じ 2 次元配列となります．また，15 行目～ 24 行目の文によって，以下に示すような出力が得られます．
  x3 10 x4 10 x3 20 x4 20 x3 30 x4 30 x3 40 x4 40 x3 40 x4 40 x3 50 x4 50
  
  26 行目
  
  　　x5 に x3[0][0] のアドレスを代入しています．new 演算子を使用して配列を確保した場合，通常の配列の場合とは異なり，全てのデータが連続した領域に確保されるとは限りません．そのため，配列全体を 1 次元配列として処理することは不可能です．この場合，x3 の 1 行目だけは正しく扱えますが，下に示す出力結果からも明らかなように，2 行目以降は，意味が無い出力となってしまいます（このような参照は避けるべきです）．この例の場合，int *x5 = &x3[0][0];，int *x5 = &x3[1][0];，int *x5 = &x3[2][0]; などの方法によって，各行を要素数が 2 である 1 次元配列として扱うことが可能です．
  x3 10 x5 10 x3 20 x5 20 x3 30 x5 1628620015 x3 40 x5 134280023 x3 40 x5 12594745 x3 50 x5 0

キュー（ queue ）

　　キューは，次に述べるスタックと正反対の概念であり，待ち行列に対応します．切符売り場の前で並ぶ，銀行の窓口で並ぶ，などの現象を表すのに使用されます．待ち行列の場合，先に並んだ人ほど早く処理（切符を買う，銀行における用事を済ます，など）を受けられ，後から来た人は必ず待ち行列の最後に並ぶことになります．このように，最初に入れたデータを最初に取り出せるようなデータ構造のことを，FIFO（ First In First Out ）と呼びます．

　　以下に示すのは，キューを処理するためのプログラム例です．このプログラムでは乱数を使用していますが，C/C++ における乱数生成関数 srand，rand は，16 ビットを使用しているためその周期が短く（最大でも，32767 ），あまり質が良い乱数を生成してくれません．そこで，以下の節においても同様ですが，メルセンヌ・ツイスタを使用しています．ただし，C++11 で記述可能であれば，C++ の標準ライブラリであるメルセンヌ・ツイスター法による擬似乱数生成エンジンを使用できます．また，実際の問題を解くためには，queue クラスを使用した方が，プログラムを書きやすいと思います．

001	/****************************/
002	/* キュー                   */
003	/*      coded by Y.Suganuma */
004	/****************************/
005	#include <stdio.h>
006	#include <stdlib.h>   // RAND_MAXを使用する場合も必要
007	#include <time.h>
008	#include "MT.h"
009	
010	#define MAX 3   // 最大待ち行列長
011	
012	int QUE[MAX], first, last;   // 待ち行列，先頭，最後尾
013	
014	/****************************/
015	/* 待ち行列長の計算         */
016	/*      return : 待ち行列長 */
017	/****************************/
018	int que_len()
019	{
020		int len = 0;
021		if (first >= 0) {
022			if (last >= first)
023				len = last - first + 1;
024			else
025				len = MAX - first + last + 1;
026		}
027		return len;
028	}
029	
030	/************************************/
031	/* 待ち行列に追加                   */
032	/*      k : 追加データ              */
033	/*      return : 0 : 正常           */
034	/*               1 : オーバーフロー */
035	/************************************/
036	int queue(int k)
037	{
038		int ind = 0;
039		if (first < 0) {
040			QUE[0] = k;
041			first  = 0;
042			last   = 0;
043		}
044		else {
045			int n = (last + 1) % MAX;
046			if (QUE[n] > 0)
047				ind = 1;
048			else {
049				QUE[n] = k;
050				last   = n;
051			}
052		}
053		return ind;
054	}
055	
056	/****************************/
057	/* 待ち行列の先頭を削除     */
058	/*      return : 削除データ */
059	/****************************/
060	int dequeue()
061	{
062		int ind = 0;
063		if (first >= 0) {
064			ind        = QUE[first];
065			QUE[first] = 0;
066			first      = (first + 1) % MAX;
067			if (QUE[first] <= 0) {
068				first = -1;
069				last  = -1;
070			}
071		}
072		return ind;
073	}
074	
075	/*************/
076	/* main 関数 */
077	/*************/
078	int main()
079	{
080				// 初期化
081		first = -1;
082		last  = -1;
083		for (int i1 = 0; i1 < MAX; i1++)
084			QUE[i1] = 0;
085		init_genrand((unsigned)time(NULL));   // init_genrand(123), C/C++: srand(seed);
086				// 実行
087					// 追加1
088		printf("   待ち行列長 %d\n", que_len());
089		int k = (int)(1000 * genrand_real3());   // C/C++: k = (int)(1000 * (double)rand() / RAND_MAX)
090		if (queue(k) > 0) {
091			printf("***error*** オーバーフロー\n");
092			exit(1);
093		}
094		printf("%d を最後尾に追加\n", k);
095		printf("   待ち行列長 %d\n", que_len());
096					// 追加2
097		k = (int)(1000 * genrand_real3());
098		if (queue(k) > 0) {
099			printf("***error*** オーバーフロー\n");
100			exit(1);
101		}
102		printf("%d を最後尾に追加\n", k);
103		printf("   待ち行列長 %d\n", que_len());
104					// 削除1
105		int n = dequeue();
106		if (n > 0) {
107			printf("先頭 %d を削除\n", n);
108			printf("   待ち行列長 %d\n", que_len());
109		}
110					// 追加3
111		k = (int)(1000 * genrand_real3());
112		if (queue(k) > 0) {
113			printf("***error*** オーバーフロー\n");
114			exit(1);
115		}
116		printf("%d を最後尾に追加\n", k);
117		printf("   待ち行列長 %d\n", que_len());
118					// 追加4
119		k = (int)(1000 * genrand_real3());
120		if (queue(k) > 0) {
121			printf("***error*** オーバーフロー\n");
122			exit(1);
123		}
124		printf("%d を最後尾に追加\n", k);
125		printf("   待ち行列長 %d\n", que_len());
126					// 削除2
127		n = dequeue();
128		if (n > 0) {
129			printf("先頭 %d を削除\n", n);
130			printf("   待ち行列長 %d\n", que_len());
131		}
132					// 追加5
133		k = (int)(1000 * genrand_real3());
134		if (queue(k) > 0) {
135			printf("***error*** オーバーフロー\n");
136			exit(1);
137		}
138		printf("%d を最後尾に追加\n", k);
139		printf("   待ち行列長 %d\n", que_len());
140					// 追加6
141		k = (int)(1000 * genrand_real3());
142		if (queue(k) > 0) {
143			printf("***error*** オーバーフロー\n");
144			exit(1);
145		}
146		printf("%d を最後尾に追加\n", k);
147		printf("   待ち行列長 %d\n", que_len());
148		return 0;
149	}

081 行目～ 084 行目

　　先頭，及び，最後尾の値を -1 で初期設定しておきます（待ち行列が無い状態）．また，配列 QUE の要素も 0 で初期設定しておきます．

085 行目

　　乱数の初期設定です．常に同じ乱数系列を使用したい場合は，コメントにあるように，適当な初期値を与えます．

089 行目

　　genrand_real3() は，(0, 1) 区間の一様乱数を返します．この結果，k の値は 1 ～ 999 内のいずれかの値となります．

045 行目

　　基本的に，待ち行列への追加データは，QUE[last + 1] に記憶されますが，(last + 1) >= MAX の場合は，QUE[0] に記憶されます．指定された位置に，既にデータが存在する場合は，オーバーフローになります．待ち行列からデータを削除する場合や，待ち行列の長さを求める場合も，同じような処理が必要です．このプログラムを実行すると，以下に示すような結果が得られます．

	   待ち行列長 0
	410 を最後尾に追加
	   待ち行列長 1
	320 を最後尾に追加
	   待ち行列長 2
	先頭 410 を削除
	   待ち行列長 1
	137 を最後尾に追加
	   待ち行列長 2
	241 を最後尾に追加
	   待ち行列長 3
	先頭 320 を削除
	   待ち行列長 2
	888 を最後尾に追加
	   待ち行列長 3
	***error*** オーバーフロー

メルセンヌ・ツイスタ（ MT.h ）

/*
   A C-program for MT19937, with initialization improved 2002/1/26.
   Coded by Takuji Nishimura and Makoto Matsumoto.

   Before using, initialize the state by using init_genrand(seed)  
   or init_by_array(init_key, key_length).

   Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
   All rights reserved.                          

   Redistribution and use in source and binary forms, with or without
   modification, are permitted provided that the following conditions
   are met:

     1. Redistributions of source code must retain the above copyright
        notice, this list of conditions and the following disclaimer.

     2. Redistributions in binary form must reproduce the above copyright
        notice, this list of conditions and the following disclaimer in the
        documentation and/or other materials provided with the distribution.

     3. The names of its contributors may not be used to endorse or promote 
        products derived from this software without specific prior written 
        permission.

   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
   A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
   CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
   EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
   PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
   PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
   LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.


   Any feedback is very welcome.
   http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
   email: m-mat @ math.sci.hiroshima-u.ac.jp (remove space)
*/

/*
   The original version of http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/CODES/mt19937ar.c was modified by Takahiro Omi as
   - delete line 47 "#include<stdio.h>"
   - delete line 174 int main(void){...}
   - change N -> MT_N
   - change N -> MT_N
   - change the file name "mt19937ar.c" -> "MT.h"
*/


/* Period parameters */  
#define MT_N 624
#define MT_M 397
#define MATRIX_A 0x9908b0dfUL   /* constant vector a */
#define UPPER_MASK 0x80000000UL /* most significant w-r bits */
#define LOWER_MASK 0x7fffffffUL /* least significant r bits */

static unsigned long mt[MT_N]; /* the array for the state vector  */
static int mti=MT_N+1; /* mti==MT_N+1 means mt[MT_N] is not initialized */

/* initializes mt[MT_N] with a seed */
void init_genrand(unsigned long s)
{
    mt[0]= s & 0xffffffffUL;
    for (mti=1; mti<MT_N; mti++) {
        mt[mti] = 
	    (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti); 
        /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
        /* In the previous versions, MSBs of the seed affect   */
        /* only MSBs of the array mt[].                        */
        /* 2002/01/09 modified by Makoto Matsumoto             */
        mt[mti] &= 0xffffffffUL;
        /* for >32 bit machines */
    }
}

/* initialize by an array with array-length */
/* init_key is the array for initializing keys */
/* key_length is its length */
/* slight change for C++, 2004/2/26 */
void init_by_array(unsigned long init_key[], int key_length)
{
    int i, j, k;
    init_genrand(19650218UL);
    i=1; j=0;
    k = (MT_N>key_length ? MT_N : key_length);
    for (; k; k--) {
        mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525UL))
          + init_key[j] + j; /* non linear */
        mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */
        i++; j++;
        if (i>=MT_N) { mt[0] = mt[MT_N-1]; i=1; }
        if (j>=key_length) j=0;
    }
    for (k=MT_N-1; k; k--) {
        mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941UL))
          - i; /* non linear */
        mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */
        i++;
        if (i>=MT_N) { mt[0] = mt[MT_N-1]; i=1; }
    }

    mt[0] = 0x80000000UL; /* MSB is 1; assuring non-zero initial array */ 
}

/* generates a random number on [0,0xffffffff]-interval */
unsigned long genrand_int32(void)
{
    unsigned long y;
    static unsigned long mag01[2]={0x0UL, MATRIX_A};
    /* mag01[x] = x * MATRIX_A  for x=0,1 */

    if (mti >= MT_N) { /* generate N words at one time */
        int kk;

        if (mti == MT_N+1)   /* if init_genrand() has not been called, */
            init_genrand(5489UL); /* a default initial seed is used */

        for (kk=0;kk<MT_N-MT_M;kk++) {
            y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
            mt[kk] = mt[kk+MT_M] ^ (y >> 1) ^ mag01[y & 0x1UL];
        }
        for (;kk<MT_N-1;kk++) {
            y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
            mt[kk] = mt[kk+(MT_M-MT_N)] ^ (y >> 1) ^ mag01[y & 0x1UL];
        }
        y = (mt[MT_N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
        mt[MT_N-1] = mt[MT_M-1] ^ (y >> 1) ^ mag01[y & 0x1UL];

        mti = 0;
    }
  
    y = mt[mti++];

    /* Tempering */
    y ^= (y >> 11);
    y ^= (y << 7) & 0x9d2c5680UL;
    y ^= (y << 15) & 0xefc60000UL;
    y ^= (y >> 18);

    return y;
}

/* generates a random number on [0,0x7fffffff]-interval */
long genrand_int31(void)
{
    return (long)(genrand_int32()>>1);
}

/* generates a random number on [0,1]-real-interval */
double genrand_real1(void)
{
    return genrand_int32()*(1.0/4294967295.0); 
    /* divided by 2^32-1 */ 
}

/* generates a random number on [0,1)-real-interval */
double genrand_real2(void)
{
    return genrand_int32()*(1.0/4294967296.0); 
    /* divided by 2^32 */
}

/* generates a random number on (0,1)-real-interval */
double genrand_real3(void)
{
    return (((double)genrand_int32()) + 0.5)*(1.0/4294967296.0); 
    /* divided by 2^32 */
}

/* generates a random number on [0,1) with 53-bit resolution*/
double genrand_res53(void) 
{ 
    unsigned long a=genrand_int32()>>5, b=genrand_int32()>>6; 
    return(a*67108864.0+b)*(1.0/9007199254740992.0); 
} 
/* These real versions are due to Isaku Wada, 2002/01/09 added */

スタック（ stack ）

　　プログラムの途中で関数を呼んだとき，その関数における処理が終了すると，再び元のプログラムに戻り，呼び出した関数の次の文から実行が継続します．このようなことが可能であるためには，関数を呼び出したときの状態をどこかに記憶しておき（スタックへ push ），関数における処理が終了した後，記憶した内容を元に戻す（スタックの pop ）必要があります．このようなときに使用されるのがスタックです．スタックは，必要なデータを積み上げていき（ push ），必要になったとき最も最後に積み上げたデータを取り出します（ pop ）．キューとは逆の概念になり，「元に戻す」機能を持った様々なソフトウェアもスタックを利用しています．このように，最後に入れたものを最初に取り出すようなデータ構造のことを，LIFO （ Last In First Out ）と言います．C++ の標準ライブラリ内の stack クラスを利用すれば，簡単に実現できます．

［演習１］配列を利用し（上で述べた stack クラスを利用してはいけない），スタックを実現するプログラムを書け．データの生成には乱数を使用し，push，及び，pop 機能を示現する関数を必ず含めること．また，様々なケースに対して正しく動作することを確認すること．