アルゴリズムとデータ構造 補足資料5-2 「サンプルプログラムsetop.c」 横浜国立大学 理工学部 数物・電子情報系学科 富井尚志

集合の表現 A = { 1, 2, 4, 5} 表現方法１：ビット列の位置で表す 表現方法２：配列に代入する 位置＝要素 その位置のビットが1(True)→その要素が集合Ａに存在する その位置のビットが0(False)→その要素は集合Ａには存在しない 位置：要素　１２３４５６７８ ビット　　　１１０１１０００ 　　　　　　　　　　　　　　　→　１１０１１００ ≡ A = { 1, 2, 4, 5} とみなす 表現方法２：配列に代入する 添え字は特に意味を持たない 要素がこれ以上存在しないこと（終わり）を示す必要がある Ａ［Ｎ］＝｛１，２，４，５，－１｝ 「表現」＝「みなす」（データ構造を定義した人＝使う人、が決める） どちらの方法がよい、という議論はこの際しない。

サンプルプログラム： setop.c 集合の印刷 （一部抜粋） 配列名＝配列へのポインタ に注目 集合の印刷　（一部抜粋） 配列名＝配列へのポインタ　に注目 関数printsetからは、main関数のブロック内だけで有効な 配列変数s[MAX]にポインタを使って参照することができる。 printsetの仮引数aは、int型配列への「ポインタ」変数。 printset内では、配列aとして扱う（配列sを参照する）ことができる。 配列sの実体は、main関数にある。

/. アルゴリズムとデータ構造 サンプルプログラム setop /**************************************************************** アルゴリズムとデータ構造 サンプルプログラム setop.c <<集合演算>> copyright (c) 1995,96,97 T.Mori <mori@forest.dnj.ynu.ac.jp> ****************************************************************/ #include <stdio.h> #define MAX 100 /* MAX は 配列の最大値要素数 */ #define EOSET -1 /* 集合の終りを表すマーク */ #define NOTMEMBER -2 /* 集合の要素がないことを表すマーク */ #define TRUE 1 /* 真 */ #define FALSE 0 /* 偽 */ void rmdup(int a[ ]); void printset(int a[ ]); void set_intersec(int a[ ],int b[ ], int c[ ]); void set_union(int a[ ],int b[ ], int c[ ]); void set_difference(int a[ ], int b[ ], int c[ ]); main() { int s[MAX] = {3,4,2,6,2,9,9,9,1,5,2,9,6,8,6,EOSET}; int t[MAX] = {1,2,3,4, 7,8,9,10,EOSET}; int u[MAX] = {1, 3,4,5,6,7, 9, EOSET}; int v[MAX]; printf("s[]: "); printset(s); /* 配列の名前だけを指定すると配列自身を指定したことになる． * 正確にいうと，配列が配置されている記憶領域の先頭の番地 * を表す． */ /* 略 */ return 0; } /* 集合の印刷 */ void printset(int a[]) { int i; for (i = 0; a[i] != EOSET; i++) { printf("%d ",a[i]); } printf("\n");

printf(“a[0]=%d, a[1]=%d\n”, a[0], a[1]); } s[3] 0x 40ea 0800 (s+3) a アドレス（32bit） 中身（1記憶単位は8bit） … 0x 40ea 0800 0000 0000 0x 40ea 0801 0x 40ea 0802 0x 40ea 0803 0000 0011 0x 40ea 0804 0x 40ea 0805 0x 40ea 0806 0x 40ea 0807 0000 0100 0x 40ea 0808 0x 40ea 0809 0x 40ea 080a 0x 40ea 080b 0000 0010 0x 40ea 080c 0x 40ea 080d 0x 40ea 080e 0x 40ea 080f 0000 0110 0x 40ea 0810 int s[100]; … f(s); s = 0x 40ea 0800 s s[0] s[0] s[1] s[2] … s[15] a[99] 3 4 2 EOSET (s+1) s[1] 配列sの実体はメモリの中に、 アドレスを伴なって存在する。 配列名sは、sの先頭アドレスを 　　　示す。 (s+2) s[2] void f(int a[]) { printf(“a[0]=%d, a[1]=%d\n”, a[0], a[1]); } s[3] 0x 40ea 0800 (s+3) a 3, 4 と表示される： 関数fからは、aの名前で実体を参照する。 s[4] (s+4)

void printset( int a[] ) return 0; int main( void) 変数 int s[MAX] s = 0x 40ea 0800 s[0] s[1] s[2] … s[15] a[99] 3 4 2 EOSET printf("s[]: "); printset(s); void printset( int a[] ) return 0; 仮引数 int a[] 変数 int i for (i = 0; a[i] != EOSET; i++) { printf("%d ",a[i]); } printf("\n"); 戻り値なし（void）

int main( void) 変数 int s[MAX] s = 0x 40ea 0800 s[0] s[1] s[2] … s[15] 3 4 2 EOSET printf("s[]: "); printset(s); return 0; s[]:

int main( void) 変数 int s[MAX] s = 0x 40ea 0800 s[0] s[1] s[2] … s[15] 3 4 2 EOSET printf("s[]: "); printset(s); return 0; s[]:

void printset( int a[] ) return 0; int main( void) 変数 int s[MAX] s = 0x 40ea 0800 s[0] s[1] s[2] … s[15] a[99] 3 4 2 EOSET printf("s[]: "); printset(s); printset(40ea0800) void printset( int a[] ) return 0; 仮引数 int a[] 40ea0800 変数 int i for (i = 0; a[i] != EOSET; i++) { printf("%d ",a[i]); } printf("\n"); s[]: 戻り値なし（void）

void printset( int a[] ) return 0; int main( void) 変数 int s[MAX] s = 0x 40ea 0800 s[0] s[1] s[2] … s[15] a[99] 3 4 2 EOSET 値渡しによる 関数呼び出し Call by Value printf("s[]: "); printset(s); printset(40ea0800) void printset( int a[] ) return 0; 仮引数 int a[] 40ea0800 ポインタによる参照 Reference 変数 int i 参照渡しによる 関数呼び出しに相当 Call by Reference for (i = 0; a[i] != EOSET; i++) { printf("%d ",a[i]); } printf("\n"); s[]: 戻り値なし（void）

void printset( int a[] ) return 0; int main( void) 変数 int s[MAX] s = 0x 40ea 0800 s[0] s[1] s[2] … s[15] a[99] 3 4 2 EOSET printf("s[]: "); printset(s); printset(40ea0800) void printset( int a[] ) return 0; 仮引数 int a[] 40ea0800 変数 int i for (i = 0; a[i] != EOSET; i++) { printf("%d ",a[i]); } printf("\n"); s[]: 戻り値なし（void）

void printset( int a[] ) return 0; int main( void) 変数 int s[MAX] s = 0x 40ea 0800 s[0] s[1] s[2] … s[15] a[99] 3 4 2 EOSET printf("s[]: "); printset(s); printset(40ea0800) void printset( int a[] ) return 0; 仮引数 int a[] 40ea0800 変数 int i a[0] for (i = 0; a[i] != EOSET; i++) { printf("%d ",a[i]); } printf("\n"); s[]: 戻り値なし（void）

void printset( int a[] ) return 0; int main( void) 変数 int s[MAX] s = 0x 40ea 0800 s[0] s[1] s[2] … s[15] a[99] 3 4 2 EOSET printf("s[]: "); printset(s); printset(40ea0800) void printset( int a[] ) return 0; 仮引数 int a[] 40ea0800 変数 int i for (i = 0; a[i] != EOSET; i++) { printf("%d ",a[i]); } printf("\n"); a[0] s[]: 3 戻り値なし（void）

void printset( int a[] ) return 0; int main( void) 変数 int s[MAX] s = 0x 40ea 0800 s[0] s[1] s[2] … s[15] a[99] 3 4 2 EOSET printf("s[]: "); printset(s); printset(40ea0800) void printset( int a[] ) return 0; 仮引数 int a[] 40ea0800 変数 int i 1 for (i = 0; a[i] != EOSET; i++) { printf("%d ",a[i]); } printf("\n"); s[]: 3 戻り値なし（void）

void printset( int a[] ) return 0; int main( void) 変数 int s[MAX] s = 0x 40ea 0800 s[0] s[1] s[2] … s[15] a[99] 3 4 2 EOSET printf("s[]: "); printset(s); printset(40ea0800) void printset( int a[] ) return 0; 仮引数 int a[] 40ea0800 変数 int i 1 a[1] for (i = 0; a[i] != EOSET; i++) { printf("%d ",a[i]); } printf("\n"); s[]: 3 戻り値なし（void）

void printset( int a[] ) return 0; int main( void) 変数 int s[MAX] s = 0x 40ea 0800 s[0] s[1] s[2] … s[15] a[99] 3 4 2 EOSET printf("s[]: "); printset(s); printset(40ea0800) void printset( int a[] ) return 0; 仮引数 int a[] 40ea0800 変数 int i 1 a[1] for (i = 0; a[i] != EOSET; i++) { printf("%d ",a[i]); } printf("\n"); s[]: 3 4 戻り値なし（void）

サンプルプログラム： setop.c 集合の印刷 （一部抜粋） 配列名＝配列へのポインタ に注目 集合の印刷　（一部抜粋） 配列名＝配列へのポインタ　に注目 関数printsetからは、main関数のブロック内だけで有効な 配列変数s[MAX]にポインタを使って参照することができる。 printsetの仮引数aは、int型配列への「ポインタ」変数。 printset内では、配列aとして扱う（配列sを参照する）ことができる。 配列sの実体は、main関数にある。

サンプルプログラム： setop.c 重複除去のアルゴリズム （一部抜粋） 配列名＝配列へのポインタ に注目 重複除去のアルゴリズム　（一部抜粋） 配列名＝配列へのポインタ　に注目 関数rmdupでは、二つの添え字 i と j を使って 配列aの２か所を参照する。 rmdupからは、配列名aによって配列sを参照している。 →main関数内のsの内容が書き換えられる。

/. アルゴリズムとデータ構造 サンプルプログラム setop /**************************************************************** アルゴリズムとデータ構造 サンプルプログラム setop.c <<集合演算>> copyright (c) 1995,96,97 T.Mori <mori@forest.dnj.ynu.ac.jp> ****************************************************************/ #include <stdio.h> #define MAX 100 /* MAX は 配列の最大値要素数 */ #define EOSET -1 /* 集合の終りを表すマーク */ #define NOTMEMBER -2 /* 集合の要素がないことを表すマーク */ #define TRUE 1 /* 真 */ #define FALSE 0 /* 偽 */ void rmdup(int a[ ]); void printset(int a[ ]); void set_intersec(int a[ ],int b[ ], int c[ ]); void set_union(int a[ ],int b[ ], int c[ ]); void set_difference(int a[ ], int b[ ], int c[ ]); main() { int s[MAX] = {3,4,2,6,2,9,9,9,1,5,2,9,6,8,6,EOSET}; int t[MAX] = {1,2,3,4, 7,8,9,10,EOSET}; int u[MAX] = {1, 3,4,5,6,7, 9, EOSET}; int v[MAX]; /* 略 */ /* 重複除去 */ printf("rmdup(s)\n"); rmdup(s); printf("s[]: "); printset(s); return 0; } /* 重複を除去する関数 */ void rmdup(int a[]) { int i,j,d; /* 重複する要素にマークをつける */ for(i=0; a[i] != EOSET; i++) for(j=i+1; a[j] != EOSET; j++) if (a[j] == a[i]) a[j] = NOTMEMBER; /* マークのついた要素をつめるように配列を作り直す */ d = 0; if (a[i] == NOTMEMBER) d++; /* 要素の移動距離を1だけ増やす */ else { if (d > 0) a[i-d] = a[i]; /* 距離 d だけ要素を前方に移動 */ } a[i-d] = a[i]; /* 配列の最後のマークも移動 */

int main( void) void rmdup( int a[] ) 変数 int s[MAX] s = 0x 40ea 0800 … 3 4 2 6 9 変数 int i 変数 int j printf("rmdup(s)\n"); rmdup(s); printf("s[]: "); printset(s); 変数 int d for(i=0; a[i] != EOSET; i++) for(j=i+1; a[j] != EOSET; j++) if (a[j] == a[i]) a[j] = NOTMEMBER; d = 0; if (a[i] == NOTMEMBER) d++; else { if (d > 0) a[i-d] = a[i]; } return 0; 戻り値なし（void）

int main( void) 変数 int s[MAX] s = 0x 40ea 0800 s[0] s[1] s[2] s[3] … 3 4 2 6 9 printf("rmdup(s)\n"); rmdup(s); printf("s[]: "); printset(s); return 0; rmdup(s)

int main( void) 変数 int s[MAX] s = 0x 40ea 0800 s[0] s[1] s[2] s[3] … 3 4 2 6 9 printf("rmdup(s)\n"); rmdup(s); printf("s[]: "); printset(s); return 0; rmdup(s)

int main( void) void rmdup( int a[] ) 変数 int s[MAX] s = 0x 40ea 0800 … 3 4 2 6 9 rmdup(40ea0800) 変数 int i 変数 int j printf("rmdup(s)\n"); rmdup(s); printf("s[]: "); printset(s); 変数 int d for(i=0; a[i] != EOSET; i++) for(j=i+1; a[j] != EOSET; j++) if (a[j] == a[i]) a[j] = NOTMEMBER; d = 0; if (a[i] == NOTMEMBER) d++; else { if (d > 0) a[i-d] = a[i]; } return 0; rmdup(s) 戻り値なし（void）

rmdupからは、配列名aによって配列sを参照している: 配列aだと思えばよい。 仮引数 int a[] a[0] a[1] a[2] void rmdup( int a[] ) rmdupからは、配列名aによって配列sを参照している: 配列aだと思えばよい。 仮引数 int a[] 40ea0800 a[0] a[1] a[2] a[3] a[4] a[5] … 3 4 2 6 9 変数 int i 変数 int j 変数 int d for(i=0; a[i] != EOSET; i++) for(j=i+1; a[j] != EOSET; j++) if (a[j] == a[i]) a[j] = NOTMEMBER; d = 0; if (a[i] == NOTMEMBER) d++; else { if (d > 0) a[i-d] = a[i]; } rmdup(s) 戻り値なし（void）

i = a[0] a[1] a[2] a[3] a[4] a[5] … 3 4 2 6 9 a[j] == a[i] ? j = 1

i = a[0] a[1] a[2] a[3] a[4] a[5] … 3 4 2 6 9 a[j] == a[i] ? j = 2

i = a[0] a[1] a[2] a[3] a[4] a[5] … 3 4 2 6 9 a[j] == a[i] ? j = 3

i = a[0] a[1] a[2] a[3] a[4] a[5] … 3 4 2 6 9 a[j] == a[i] ? j = … a[j] == EOSET までループ（内側のループ）

i = 1 iに1を追加（外側のループ） a[0] a[1] a[2] a[3] a[4] a[5] … 3 4 2 6 9 a[j] == a[i] ? j = 2

i = 1 a[0] a[1] a[2] a[3] a[4] a[5] … 3 4 2 6 9 a[j] == a[i] ? j = 3

i = 1 a[0] a[1] a[2] a[3] a[4] a[5] … 3 4 2 6 9 a[j] == a[i] ? j = … a[j] == EOSET までループ（内側のループ）

i = 2 iに1を追加（外側のループ） a[0] a[1] a[2] a[3] a[4] a[5] … 3 4 2 6 9 a[j] == a[i] ? j = 3

i = 2 a[0] a[1] a[2] a[3] a[4] a[5] … 3 4 2 6 9 a[j] == a[i] ビンゴ！ j = 4

i = 2 a[0] a[1] a[2] a[3] a[4] a[5] … 3 4 2 6 9 a[j] == a[i] ビンゴ！ j = NOT NUMBER 9 a[j] == a[i] ビンゴ！ j = 4

a[j] == EOSET までループ（内側のループ） i = 2 a[0] a[1] a[2] a[3] a[4] a[5] … 3 4 2 6 NOT NUMBER 9 a[j] == a[i] ? j = … a[j] == EOSET までループ（内側のループ）

a[i] == EOSET までループ（外側のループ） a[0] a[1] a[2] a[3] a[4] a[5] … 6 NOT NUMBER 9 a[j] == a[i] ? j = …

i = a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] … 3 4 2 6 9 1 d = a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] … 3 4 2 6 NOT NUMBER 9 1 d =

i = 1 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] … 3 4 2 6 9 1 d = NOT NUMBER 9 1 d =

i = 2 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] … 3 4 2 6 9 1 d = NOT NUMBER 9 1 d =

i = 3 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] … 3 4 2 6 9 1 d = NOT NUMBER 9 1 d =

i = 4 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] … 3 4 2 6 9 1 d = 1 NOT NUMBER 9 1 d = 1

i = 5 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] … 3 4 2 6 9 1 d = 1 NOT NUMBER 9 1 d = 1 a[ i-d] = a[i];

i = 5 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] … 3 4 2 6 9 1 d = 1 NOT NUMBER 1 d = 1 a[ i-d] = a[i];

i = 6 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] … 3 4 2 6 9 1 d = 2 NOT NUMBER 1 d = 2

i = 7 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] … 3 4 2 6 9 1 d = 3 NOT NUMBER 1 d = 3

i = 8 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] … 3 4 2 6 9 1 d = 3 NOT NUMBER 1 d = 3 a[ i-d] = a[i];

i = 8 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] … 3 4 2 6 9 1 d = 3 NOT NUMBER d = 3 a[ i-d] = a[i];

i = 15 a[0] a[1] a[2] a[3] a[4] a[5] a[…] a[.] a[8] … 3 4 2 6 9 1 d = EOSET d = … a[ i-d] = a[i];

void rmdup( int a[] ) i = 15 仮引数 int a[] ` a[0] a[1] a[2] a[3] a[4] 40ea0800 a[0] a[1] a[2] a[3] a[4] a[5] a[…] 3 4 2 6 9 1 … 変数 int i 変数 int j 変数 int d for(i=0; a[i] != EOSET; i++) for(j=i+1; a[j] != EOSET; j++) if (a[j] == a[i]) a[j] = NOTMEMBER; d = 0; if (a[i] == NOTMEMBER) d++; else { if (d > 0) a[i-d] = a[i]; } 戻り値なし（void）

int main( void) void rmdup( int a[] ) i = 15 変数 int s[MAX] s = 0x 40ea 0800 仮引数 int a[] 40ea0800 a[0] a[1] a[2] a[3] a[4] a[5] a[…] 3 4 2 6 9 1 … s[0] s[1] s[2] s[3] s[4] s[5] … 3 4 2 6 9 変数 int i 変数 int j printf("rmdup(s)\n"); rmdup(s); printf("s[]: "); printset(s); 変数 int d for(i=0; a[i] != EOSET; i++) for(j=i+1; a[j] != EOSET; j++) if (a[j] == a[i]) a[j] = NOTMEMBER; d = 0; if (a[i] == NOTMEMBER) d++; else { if (d > 0) a[i-d] = a[i]; } return 0; return rmdup(s) 戻り値なし（void）

int main( void) 変数 int s[MAX] s = 0x 40ea 0800 s[0] s[1] s[2] s[3] … 3 4 2 6 9 s[0] s[1] s[2] s[3] s[4] s[5] s[…] 3 4 2 6 9 1 … printf("rmdup(s)\n"); rmdup(s); printf("s[]: "); printset(s); return 0; rmdup(s)の呼び出し前 s[0] s[1] s[2] s[3] s[4] s[5] … 3 4 2 6 9 rmdup(s) rmdup(s)から参照されて、 main関数内の自動配列変数sの中身が 変更された。

int main( void) 変数 int s[MAX] s = 0x 40ea 0800 s[0] s[1] s[2] s[3] 6 9 1 … s[0] s[1] s[2] s[3] s[4] s[5] … 3 4 2 6 9 printf("rmdup(s)\n"); rmdup(s); printf("s[]: "); printset(s); return 0; rmdup(s) s[]: 3 4 2 6 9 1 5 6 8