アルゴリズムとデータ構造 補足資料4-1 「メモリと配列」 横浜国立大学 理工学部 数物・電子情報系学科 富井尚志

（ASCIIコードなら’A’、10進数なら65） アドレス（32bit） 中身（1記憶単位は8bit） … 0x 40ea 0800 1101 0000 0x 40ea 0801 0000 0111 0x 40ea 0802 0100 1011 0x 40ea 0803 1011 1111 0x 40ea 0804 0100 1100 0x 40ea 0805 1000 1110 0x 40ea 0806 1010 0100 0x 40ea 0807 0x 40ea 0808 0100 0001 0x 40ea 0809 1011 0111 0x 40ea 080a 0x 40ea 080b 0x 40ea 080c 0x 40ea 080d 0110 1111 0x 40ea 080e 1010 0111 0x 40ea 080f 0101 0000 0x 40ea 0810 計算機の記憶（メモリ）の構造： すべての記憶領域には、記憶単位ごとに 　連続する番号（アドレス）が付されている 記憶単位の中身には、値が書き込まれている CPUは、任意のアドレスを指定することで 　そのアドレスの記憶領域の中身を 　　読み出す/書き込む 　ことができる 　（Random Access Memory : RAM） たとえば、 アドレス0x40ea080a番地の中身は、 01000001 　（ASCIIコードなら’A’、10進数なら65） （システムによって異なるがここでは） アドレスは32bit （左図では16進表記） 記憶単位は8bit (単位は[Byte]) アドレスは0x00000000～0xffffffff なので、232=4GByte の空間が限界

printf(“a:%x = %d\n”, &a, a); return 0; } アドレス（32bit） 中身（1記憶単位は8bit） … 0x 40ea 0800 1101 0000 0x 40ea 0801 0000 0111 0x 40ea 0802 0100 1011 0x 40ea 0803 1011 1111 0x 40ea 0804 0000 0000 0x 40ea 0805 0x 40ea 0806 0x 40ea 0807 0001 0100 0x 40ea 0808 0100 0001 0x 40ea 0809 1011 0111 0x 40ea 080a 0x 40ea 080b 0x 40ea 080c 0100 1100 0x 40ea 080d 0110 1111 0x 40ea 080e 1010 0111 0x 40ea 080f 0101 0000 0x 40ea 0810 int main(void) { int a; a = 20; printf(“a:%x = %d\n”, &a, a); return 0; } &a a 実行すると、以下の結果が出た。 a: 40ea0804 = 20 この場合のaは？ 　→int型（32bitの箱）の変数aは、 　　中身が20 （2進数では10100） 00000000 00000000 00000000 00010100 a int 型（32bit） aは、物理的にどこに存在する？ 　→ 記憶（メモリ）の中 　　 （ＯＳに割り当ててもらう； 毎回変わる） aは、具体的にどこ？ 　→ 今回は0x 40ea 0804番地からの4バイト分 　→ &a == 0x 40ea 0804 （aのアドレス）

printf(“b==%x , b[0]==%d\n”, b, b[0]); return 0; } b b[0] アドレス（32bit） 中身（1記憶単位は8bit） … 0x 40ea 0800 0000 0000 0x 40ea 0801 0x 40ea 0802 0x 40ea 0803 0x 40ea 0804 0x 40ea 0805 0x 40ea 0806 0x 40ea 0807 0001 0100 0x 40ea 0808 0100 0001 0x 40ea 0809 1011 0111 0x 40ea 080a 0x 40ea 080b 1101 0000 0x 40ea 080c 0100 1100 0x 40ea 080d 0110 1111 0x 40ea 080e 1010 0111 0x 40ea 080f 0101 0000 0x 40ea 0810 int main(void) { int b[10]; b[0] = 0; printf(“b==%x , b[0]==%d\n”, b, b[0]); return 0; } b b[0] (b+1) b[1] 実行すると、以下の結果が出た。 b==40ea08000, b[0]= 0 この場合のbは？ 　→int型（32bitの箱）の配列変数bは、 　　10個の要素で構成され、 　　b[0]の中身が0, b[1]～b[9]の中身は不定 (b+2) b[2] b[0] b[1] b[2] b[3] … b[9] 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00010100 b[3] (b+3) 01000001 10110111 01000001 11010000 10個 01001100 01101111 10100111 01010000 … 01010000 01100100 00100000 00000000 int 型（32bit） b[4] (b+4) 今回の配列bのアドレスは0x40ea0800 b==0x40ea0800

printf(“b==%x , b[0]==%d\n”, b, b[0]); return 0; } b == 0x40ea0800 int main(void) { int b[10]; b[0] = 0; printf(“b==%x , b[0]==%d\n”, b, b[0]); return 0; } b == 0x40ea0800 b[0] (b+1) == 0x40ea0804 b[1] ? 実行すると、以下の結果が出た。 b==40ea08000, b[0]= 0 この場合のbは？ 　→int型（32bitの箱）の配列変数bは、 　　10個の要素で構成され、 　　b[0]の中身が0, b[1]～b[9]の中身は不定 (b+2) == 0x40ea0808 b[2] ? b[0] b[1] b[2] b[3] … b[9] 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00010100 b[3] ? (b+3) == 0x40ea080c 01000001 10110111 01000001 11010000 10個 01001100 01101111 10100111 01010000 … 01010000 01100100 00100000 00000000 int 型（32bit） b[4] (b+4) == 0x40ea0810 今回の配列bのアドレスは0x40ea0800 b==0x40ea0800

抽象化 多次元配列のデータ構造も 厳密には「アドレス」（ポインタ）と そのセルの「中身」（値）だが、、、 「モデル」（図） で考えればよい。 b[0] b[1] ? b[0] b[1] b[2] b[3] b[4] b[5] b[6] b[7] b[8] b[9] ? b[2] ? 抽象化 b[3] ? ※ ? は不定値 （初期値が設定されていない：時と場合によって値が異なる） ことを表す b[4]

c[0] = ‘Y’; c[1]=‘N’; c[2]=‘U’; c[3]=‘\0’; アドレス（32bit） 中身（1記憶単位は8bit） … 0x 40ea 0800 0000 0000 0x 40ea 0801 0x 40ea 0802 0101 1001 0x 40ea 0803 01001110 0x 40ea 0804 0101 0101 0x 40ea 0805 0x 40ea 0806 0x 40ea 0807 0001 0100 0x 40ea 0808 0100 0001 0x 40ea 0809 1011 0111 0x 40ea 080a 0x 40ea 080b 1101 0000 0x 40ea 080c 0100 1100 0x 40ea 080d 0110 1111 0x 40ea 080e 1010 0111 0x 40ea 080f 0101 0000 0x 40ea 0810 int main(void) { char c[10]; c[0] = ‘Y’; c[1]=‘N’; c[2]=‘U’; c[3]=‘\0’; printf(“c==%x , c[]==%s\n”, c, c); return 0; } c c[0] (c+1) c[1] (c+2) c[2] 実行すると、以下の結果が出た。 c==40ea08002, c[]= YNU (c+3) c[3] (c+4) c[4] この場合のcは？ 　→char型（8bitの箱）の配列変数cは、 　　10個の要素で構成され、 　　c[0]の中身が’Y’, c[1]の中身が’N’, c[2]の中身が’U’, c[3]の中身が’\0’, c[4]～c[9]の中身 　　　　　　　　　　　　　　　　　　　　　　　　　は不定 c[5] (c+5) (c+6) c[6] (c+7) c[7] (c+8) c[8] c[0] c[1] c[2] c[3] … c[9] 01011001 (c+9) c[9] 01001110 01010101 10個 00000000 … 11010000 char 型（8bit） 今回の配列cのアドレスは0x40ea0802 c==0x40ea0802

c[0] = ‘Y’; c[1]=‘N’; c[2]=‘U’; c[3]=‘\0’; int main(void) { char c[10]; c[0] = ‘Y’; c[1]=‘N’; c[2]=‘U’; c[3]=‘\0’; printf(“c==%x , c[]==%s\n”, c, c); return 0; } c == 0x40ea0802 c[0] Y (c+1) == 0x40ea0803 c[1] N (c+2) == 0x40ea0804 c[2] U 実行すると、以下の結果が出た。 c==40ea08002, b[]= YNU (c+3) == 0x40ea0805 c[3] \0 (c+4) == 0x40ea0806 c[4] ? この場合のcは？ 　→char型（8bitの箱）の配列変数cは、 　　10個の要素で構成され、 　　c[0]の中身が’Y’, c[1]の中身が’N’, c[2]の中身が’U’, c[3]の中身が’\0’, c[4]～c[9]の中身 　　　　　　　　　　　　　　　　　　　　　　　　　は不定 c[5] (c+5) == 0x40ea0807 ? (c+6) == 0x40ea0808 c[6] ? (c+7) == 0x40ea0809 c[7] ? (c+8) == 0x40ea080a c[8] ? c[0] c[1] c[2] c[3] … c[9] 01011001 ? (c+9) == 0x40ea080b c[9] 01001110 01010101 10個 00000000 … 11010000 char 型（8bit） 今回の配列cのアドレスは0x40ea0802 c==0x40ea0802

多次元配列のデータ構造も 厳密には「アドレス」（ポインタ）と そのセルの「中身」（値）だが、、、 「モデル」（図） で考えればよい。 c[0] Y c[1] N c[2] U c[3] \0 c[4] ? c[5] ? c[0] c[1] c[2] c[3] c[4] c[5] c[6] c[7] c[8] c[9] Y N U \0 ? c[6] ? c[7] ? c[8] ? c[9] ? ※ ? は不定値 （初期値が設定されていない：時と場合によって値が異なる） ことを表す

printf(“k==%x , (k+1)==%x\n”, k, (k+1) ); アドレス（32bit） 中身（1記憶単位は8bit） … 0x 40ea 0800 0000 0000 0x 40ea 0801 0x 40ea 0802 0x 40ea 0803 0000 1000 0x 40ea 0804 0x 40ea 0805 0x 40ea 0806 0x 40ea 0807 0000 0010 0x 40ea 0808 0x 40ea 0809 0x 40ea 080a 0x 40ea 080b 0000 0001 0x 40ea 080c 0x 40ea 080d 0x 40ea 080e 0x 40ea 080f 0000 0111 0x 40ea 0810 int main(void) { int k[2][3]={ {4,2,1}, {7,10,3} }; printf(“k==%x , (k+1)==%x\n”, k, (k+1) ); printf(“*k==%x, *(k+1)==%x, k[1]==%x\n”, *k, *(k+1), k[1] ); printf(“(*k+1)==%x, (*k+2)==%x\n”, (*k+1), (*k+2) ); printf(“**k==%d, k[0][0]==%d, &k[0][0]==%x\n”, **k, k[0][0], &k[0][0] ); printf(“*(*(k+1)+1)==%d, k[1][1]==%d, &k[1][1]==%x\n”, *(*(k+1)+1), k[1][1], &k[1][1] ); return 0; } k[0] k k[0][0] k[0] = *k k[0][1] (k[0]+1) = (*k+1) k[0][2] (k[0]+2) = (*k+2) k[1] 実行すると、以下の結果が出た。 k==40ea0800, (k+1)==40ea080c *k==40ea0800, *(k+1)=40ea080c, k[1]=40ea080c (*k+1)==40ea0804, (*k+2)==40ea0808 **k==4, k[0][0]==4, &k[0][0]==40ea0800 *(*(k+1)+1)==10, k[1][1]==10, &k[1][1]==40ea0810 ？？？！ (k+1) k[1][0] k[1]= *(k+1) k[1][1] (k[1]+1)= (*(k+1)+1)

k[0] 多次元配列のデータ構造も 厳密には「アドレス」（ポインタ）と そのセルの「中身」（値）だが、、、 「モデル」（図） で考えればよい。 k k[0][0] 4 k[0][1] 2 k[i][j] j i 1 2 4 7 10 3 k[0][2] 1 k[1] 7 (k+1) k[1][0] 10 k[1][1]

補足 メモリの記憶単位の大きさ（1語長）は、アーキテクチャによって異なる アドレスの大きさは、アーキテクチャやOSによって異なる 今回の例（PC）では1語=8bit（=1Byte） 情報処理技術者試験で用いられる仮想システムのCOMET IIでは1語=16bit アドレスの大きさは、アーキテクチャやOSによって異なる 今回の例（PC UNIX）では32bit COMET IIでは16bit 複数語をまとめて用いる場合の物理配置順序はアーキテクチャによって異なる Little Endian Big Endian いずれにしても、「アルゴリズム」と「データ構造」を考えるときは「アーキテクチャ」（実装）を意識せず、「モデル」（図）で考えればよい 「アーキテクチャ」と「モデル」の橋渡しをするのがOSの役割