アルゴリズムとデータ構造 補足資料5-2 「サンプルプログラムsetop.c」 横浜国立大学 理工学部 数物・電子情報系学科 富井尚志 集合の表現 • A = { 1, 2, 4, 5} – A は、要素 1, 2, 4, 5をもつ集合 • 表現方法1:ビット列の位置で表す – 位置=要素 – その位置のビットが1(True)→その要素が集合Aに存在する – その位置のビットが0(False)→その要素は集合Aには存在しない 位置:要素 12345678 ビット 11011000 → 1101100 ≡ A = { 1, 2, 4, 5} とみなす • 表現方法2:配列に代入する – 添え字は特に意味を持たない – 要素がこれ以上存在しないこと(終わり)を示す必要がある A[N]={1,2,4,5,-1} • • 「表現」=「みなす」(データ構造を定義した人=使う人、が決める) どちらの方法がよい、という議論はこの際しない。 サンプルプログラム: setop.c 集合の印刷 (一部抜粋) 配列名=配列へのポインタ に注目 関数printsetからは、main関数のブロック内だけで有効な 配列変数s[MAX]にポインタを使って参照することができる。 printsetの仮引数aは、int型配列への「ポインタ」変数。 printset内では、配列aとして扱う(配列sを参照する)ことができる。 配列sの実体は、main関数にある。 /**************************************************************** アルゴリズムとデータ構造 サンプルプログラム setop.c <<集合演算>> copyright (c) 1995,96,97 T.Mori <[email protected]> ****************************************************************/ #include <stdio.h> #define MAX 100 /* MAX は 配列の最大値要素数 */ #define EOSET -1 /* 集合の終りを表すマーク */ #define NOTMEMBER -2 /* 集合の要素がないことを表すマーク */ #define TRUE #define FALSE 1 /* 真 */ 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"); } アドレス(32bit) 中身(1記憶単位は8bit) … … s 0x 40ea 0800 s[0] 0000 0000 0x 40ea 0801 0000 0000 0x 40ea 0802 0000 0000 0x 40ea 0803 0000 0011 (s+1) 0x 40ea 0804 s[1] 0000 0000 0x 40ea 0805 0000 0000 0x 40ea 0806 0000 0000 0x 40ea 0807 0000 0100 (s+2) 0x 40ea 0808 s[2] 0000 0000 0x 40ea 0809 0000 0000 0x 40ea 080a 0000 0000 0x 40ea 080b 0000 0010 (s+3) 0x 40ea 080c s[3] 0000 0000 0x 40ea 080d 0000 0000 0x 40ea 080e 0000 0000 0x 40ea 080f 0000 0110 (s+4) 0x 40ea 0810 … s[4] 0000 0000 … int s[100]; … f(s); … s = 0x 40ea 0800 s[0] 3 s[1] 4 s[2] 2 … s[15] … EOSET … a[99] … … 配列sの実体はメモリの中に、 アドレスを伴なって存在する。 配列名sは、sの先頭アドレスを 示す。 void f(int a[]) a 0x 40ea 0800 { printf(“a[0]=%d, a[1]=%d\n”, a[0], a[1]); } 3, 4 と表示される: 関数fからは、aの名前で実体を参照する。 int main( void) 変数 int s[MAX] s[0] 3 s[1] 4 s = 0x 40ea 0800 s[2] 2 … s[15] … EOSET … a[99] … … printf("s[]: "); printset(s); return 0; void printset( int a[] ) 仮引数 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[0] 3 s[1] 4 s = 0x 40ea 0800 s[2] 2 … s[15] … EOSET printf("s[]: "); printset(s); return 0; s[]: … a[99] … … int main( void) 変数 int s[MAX] s[0] 3 s[1] 4 s = 0x 40ea 0800 s[2] 2 … s[15] … EOSET printf("s[]: "); printset(s); return 0; s[]: … a[99] … … int main( void) 変数 int s[MAX] s[0] 3 s[1] 4 s = 0x 40ea 0800 s[2] 2 … s[15] … EOSET printf("s[]: "); printset(s); return 0; … a[99] … … printset(40ea0800) void printset( int a[] ) 仮引数 int a[] 40ea0800 変数 int i s[]: for (i = 0; a[i] != EOSET; i++) { printf("%d ",a[i]); } printf("\n"); 戻り値なし(void) int main( void) 変数 int s[MAX] s[0] 3 s[1] 4 s = 0x 40ea 0800 s[2] 2 … s[15] … EOSET … a[99] … printf("s[]: "); printset(s); return 0; … 値渡しによる 関数呼び出し Call by Value printset(40ea0800) void printset( int a[] ) 仮引数 int a[] ポインタによる参照 Reference 参照渡しによる 関数呼び出しに相当 Call by Reference s[]: 40ea0800 変数 int i for (i = 0; a[i] != EOSET; i++) { printf("%d ",a[i]); } printf("\n"); 戻り値なし(void) int main( void) 変数 int s[MAX] s[0] 3 s[1] 4 s = 0x 40ea 0800 s[2] 2 … s[15] … EOSET printf("s[]: "); printset(s); return 0; … a[99] … … printset(40ea0800) void printset( int a[] ) 仮引数 int a[] 40ea0800 変数 int i s[]: for (i = 0; a[i] != EOSET; i++) { printf("%d ",a[i]); } printf("\n"); 戻り値なし(void) 0 int main( void) 変数 int s[MAX] s[0] 3 s[1] 4 s = 0x 40ea 0800 s[2] 2 … s[15] … EOSET printf("s[]: "); printset(s); return 0; … a[99] … … printset(40ea0800) void printset( int a[] ) 仮引数 int a[] 40ea0800 変数 int i a[0] s[]: for (i = 0; a[i] != EOSET; i++) { printf("%d ",a[i]); } printf("\n"); 戻り値なし(void) 0 int main( void) 変数 int s[MAX] s[0] 3 s[1] 4 s = 0x 40ea 0800 s[2] 2 … s[15] … EOSET printf("s[]: "); printset(s); return 0; … a[99] … … printset(40ea0800) void printset( int a[] ) 仮引数 int a[] 40ea0800 変数 int i a[0] s[]: 3 for (i = 0; a[i] != EOSET; i++) { printf("%d ",a[i]); } printf("\n"); 戻り値なし(void) 0 int main( void) 変数 int s[MAX] s[0] 3 s[1] 4 s = 0x 40ea 0800 s[2] 2 … s[15] … EOSET printf("s[]: "); printset(s); return 0; … a[99] … … printset(40ea0800) void printset( int a[] ) 仮引数 int a[] 40ea0800 変数 int i s[]: 3 for (i = 0; a[i] != EOSET; i++) { printf("%d ",a[i]); } printf("\n"); 戻り値なし(void) 1 int main( void) 変数 int s[MAX] s[0] 3 s[1] 4 s = 0x 40ea 0800 s[2] 2 … s[15] … EOSET printf("s[]: "); printset(s); return 0; … a[99] … … printset(40ea0800) void printset( int a[] ) 仮引数 int a[] 40ea0800 変数 int i a[1] s[]: 3 for (i = 0; a[i] != EOSET; i++) { printf("%d ",a[i]); } printf("\n"); 戻り値なし(void) 1 int main( void) 変数 int s[MAX] s[0] 3 s[1] 4 s = 0x 40ea 0800 s[2] 2 … s[15] … EOSET printf("s[]: "); printset(s); return 0; … a[99] … … printset(40ea0800) void printset( int a[] ) 仮引数 int a[] 40ea0800 変数 int i a[1] s[]: 3 4 for (i = 0; a[i] != EOSET; i++) { printf("%d ",a[i]); } printf("\n"); 戻り値なし(void) 1 サンプルプログラム: setop.c 集合の印刷 (一部抜粋) 配列名=配列へのポインタ に注目 関数printsetからは、main関数のブロック内だけで有効な 配列変数s[MAX]にポインタを使って参照することができる。 printsetの仮引数aは、int型配列への「ポインタ」変数。 printset内では、配列aとして扱う(配列sを参照する)ことができる。 配列sの実体は、main関数にある。 サンプルプログラム: setop.c 重複除去のアルゴリズム (一部抜粋) 配列名=配列へのポインタ に注目 関数rmdupでは、二つの添え字 i と j を使って 配列aの2か所を参照する。 rmdupからは、配列名aによって配列sを参照している。 →main関数内のsの内容が書き換えられる。 /**************************************************************** アルゴリズムとデータ構造 サンプルプログラム setop.c <<集合演算>> copyright (c) 1995,96,97 T.Mori <[email protected]> ****************************************************************/ #include <stdio.h> /* 重複を除去する関数 */ void rmdup(int a[]) { int i,j,d; #define MAX 100 /* MAX は 配列の最大値要素数 */ #define EOSET -1 /* 集合の終りを表すマーク */ #define NOTMEMBER -2 /* 集合の要素がないことを表すマーク */ #define TRUE #define FALSE /* 重複する要素にマークをつける */ for(i=0; a[i] != EOSET; i++) for(j=i+1; a[j] != EOSET; j++) if (a[j] == a[i]) 1 /* 真 */ 0 /* 偽 */ a[j] = NOTMEMBER; /* マークのついた要素をつめるように配列を作り直す */ d = 0; for(i=0; a[i] != EOSET; i++) if (a[i] == NOTMEMBER) d++; /* 要素の移動距離を1だけ増やす */ else { if (d > 0) a[i-d] = a[i]; /* 距離 d だけ 要素を前方に移動 */ } a[i-d] = a[i]; /* 配列の最後のマークも移動 */ 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; } } int main( void) void rmdup( int a[] ) 変数 int s[MAX] s = 0x 40ea 0800 仮引数 int a[] s[0] s[1] s[2] s[3] s[4] s[5] … 変数 int i 3 4 2 6 2 9 … 変数 int j printf("rmdup(s)\n"); rmdup(s); printf("s[]: "); printset(s); return 0; 変数 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; for(i=0; a[i] != EOSET; i++) if (a[i] == NOTMEMBER) d++; else { if (d > 0) a[i-d] = a[i]; } a[i-d] = a[i]; 戻り値なし(void) int main( void) 変数 int s[MAX] s = 0x 40ea 0800 s[0] s[1] s[2] s[3] s[4] s[5] … 3 4 2 6 2 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] s[4] s[5] … 3 4 2 6 2 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 仮引数 int a[] s[0] s[1] s[2] s[3] s[4] s[5] … 変数 int i 3 4 2 6 2 9 … 変数 int j printf("rmdup(s)\n"); rmdup(s); printf("s[]: "); printset(s); return 0; rmdup(s) 40ea0800 変数 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; for(i=0; a[i] != EOSET; i++) if (a[i] == NOTMEMBER) d++; else { if (d > 0) a[i-d] = a[i]; } a[i-d] = a[i]; 戻り値なし(void) rmdupからは、配列名aによって配列sを参照している: 配列aだと思えばよい。 a[0] a[1] a[2] a[3] a[4] a[5] 3 4 2 6 2 9 void rmdup( int a[] ) 仮引数 int a[] … 変数 int i … 変数 int j 40ea0800 変数 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; rmdup(s) d = 0; for(i=0; a[i] != EOSET; i++) if (a[i] == NOTMEMBER) d++; else { if (d > 0) a[i-d] = a[i]; } a[i-d] = a[i]; 戻り値なし(void) i= 0 a[0] a[1] a[2] a[3] a[4] a[5] 3 4 2 6 a[j] == a[i] ? j= 1 2 9 … … i= 0 a[0] a[1] a[2] a[3] a[4] a[5] 3 4 2 6 2 a[j] == a[i] ? j= 2 9 … … i= 0 a[0] a[1] a[2] a[3] a[4] a[5] 3 4 2 6 2 9 a[j] == a[i] ? j= 3 … … i= 0 a[0] a[1] a[2] a[3] a[4] a[5] 3 4 2 6 2 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 2 a[j] == a[i] ? j= 2 9 … … i= 1 a[0] a[1] a[2] a[3] a[4] a[5] 3 4 2 6 2 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 2 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 2 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 2 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 NOT NUMBER 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 NOT NUMBER 9 … … a[j] == a[i] ? j= … a[j] == EOSET までループ(内側のループ) i= a[0] a[1] a[2] a[3] a[4] a[5] 3 4 2 6 NOT NUMBER 9 … a[i] == EOSET までループ(外側のループ) … … a[j] == a[i] ? j= … 0 i= a[0] a[1] a[2] a[3] 3 4 2 6 d= 0 a[4] NOT NUMBER a[5] 9 a[6] NOT NUMBER a[7] NOT NUMBER a[8] 1 … … i= 1 a[0] a[1] a[2] a[3] 3 4 2 6 d= 0 a[4] NOT NUMBER a[5] 9 a[6] NOT NUMBER a[7] NOT NUMBER a[8] 1 … … 2 i= a[0] a[1] a[2] a[3] 3 4 2 6 d= 0 a[4] NOT NUMBER a[5] 9 a[6] NOT NUMBER a[7] NOT NUMBER a[8] 1 … … 3 i= a[0] a[1] a[2] a[3] 3 4 2 6 d= 0 a[4] NOT NUMBER a[5] 9 a[6] NOT NUMBER a[7] NOT NUMBER a[8] 1 … … 4 i= a[0] a[1] a[2] a[3] 3 4 2 6 a[4] NOT NUMBER d= 1 a[5] 9 a[6] NOT NUMBER a[7] NOT NUMBER a[8] 1 … … a[0] a[1] a[2] a[3] 3 4 2 6 i= 5 a[4] a[5] NOT NUMBER d= a[ i-d] = a[i]; 9 1 a[6] NOT NUMBER a[7] NOT NUMBER a[8] 1 … … i= 5 a[0] a[1] a[2] a[3] a[4] a[5] 3 4 2 6 9 9 d= 1 a[ i-d] = a[i]; a[6] NOT NUMBER a[7] NOT NUMBER a[8] 1 … … i= 6 a[6] a[0] a[1] a[2] a[3] a[4] a[5] 3 4 2 6 9 9 d= NOT NUMBER 2 a[7] NOT NUMBER a[8] 1 … … 7 i= a[0] a[1] a[2] a[3] a[4] a[5] 3 4 2 6 9 9 a[6] a[7] NOT NUMBER d= NOT NUMBER 3 a[8] 1 … … 8 i= a[0] a[1] a[2] a[3] a[4] a[5] 3 4 2 6 9 9 a[6] NOT NUMBER a[7] a[8] NOT NUMBER 1 d= a[ i-d] = a[i]; 3 … … 8 i= a[0] a[1] a[2] a[3] a[4] a[5] 3 4 2 6 9 1 a[6] NOT NUMBER a[7] a[8] NOT NUMBER 1 d= a[ i-d] = a[i]; 3 … … i= a[0] a[1] a[2] a[3] a[4] a[5] 3 4 2 6 9 1 a[…] … a[.] a[8] EOSET d= 1 … a[ i-d] = a[i]; 15 … … void 15 int a[] ) i = rmdup( 仮引数 ` int a[] a[0] a[1] a[2] a[3] a[4] a[5] 3 4 2 6 9 1 a[…] 変数 int i … 変数 int j 40ea0800 変数 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; for(i=0; a[i] != EOSET; i++) if (a[i] == NOTMEMBER) d++; else { if (d > 0) a[i-d] = a[i]; } a[i-d] = a[i]; 戻り値なし(void) int main( void) void 15 int a[] ) i = rmdup( 変数 int s[MAX] s = 0x 40ea 0800 仮引数 int a[] s[0] s[1] a[0] a[1] s[2] a[2] s[3] a[3] s[4] a[4] s[5] a[5] 3 44 22 66 printf("rmdup(s)\n"); rmdup(s); printf("s[]: "); printset(s); return 0; rmdup(s) 29 91 a[…] … 変数 int i …… 変数 int j 40ea0800 変数 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; for(i=0; a[i] != EOSET; i++) if (a[i] == NOTMEMBER) d++; else { if (d > 0) a[i-d] = a[i]; } a[i-d] = a[i]; 戻り値なし(void) int main( void) 変数 int s[MAX] s[0] 3 s = 0x 40ea 0800 s[1] s[2] s[2] s[3] s[3] s[4] s[4] s[5] s[5] 44 22 66 29 91 s[…] … …… printf("rmdup(s)\n"); rmdup(s); printf("s[]: "); printset(s); return 0; rmdup(s)の呼び出し前 rmdup(s) s[0] s[1] s[2] s[3] s[4] s[5] … 3 4 2 6 2 9 … rmdup(s)から参照されて、 main関数内の自動配列変数sの中身が 変更された。 int main( void) 変数 int s[MAX] s[0] s = 0x 40ea 0800 s[1] s[2] s[2] s[3] s[3] s[4] s[4] s[5] s[5] 3 44 22 66 printf("rmdup(s)\n"); rmdup(s); printf("s[]: "); printset(s); return 0; rmdup(s) s[]: 3 4 2 6 9 1 5 6 8 29 91 s[…] … ……
© Copyright 2025 ExpyDoc