アルゴリズムとデータ構造 補足資料 5-2
「サンプルプログラム setop.c 」
横浜国立大学
理工学部
数物・電子情報系学科
富井尚志
集合の表現
• A = { 1, 2, 4, 5}
–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.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 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");
}
アドレス （ 32bit ）
中身（ 1記憶単位は 8bit）
… …
0x 40ea 0800
0000 0000
0x 40ea 0801 0000 0000
0x 40ea 0802 0000 0000
0x 40ea 0803 0000 0011
0x 40ea 0804 0000 0000
0x 40ea 0805 0000 0000
0x 40ea 0806 0000 0000
0x 40ea 0807 0000 0100
0x 40ea 0808 0000 0000
0x 40ea 0809 0000 0000
0x 40ea 080a 0000 0000
0x 40ea 080b 0000 0010
0x 40ea 080c 0000 0000
0x 40ea 080d 0000 0000
0x 40ea 080e 0000 0000
0x 40ea 080f 0000 0110
0x 40ea 0810 0000 0000
… …
s[0]
s[1]
s[2]
s[3]
s[4]
s
(s+1)
(s+2)
(s+3)
(s+4)
s[0] s[1] s[2] … s[15] … a[99]
3 4 2 … EOSET … …
s = 0x 40ea 0800
配列 s の実体はメモリの中に、
アドレスを伴なって存在する。
配列名 s は、 s の先頭アドレスを 示す。
int s[100];
… f(s);
…
void f(int a[]) {
printf(“a[0]=%d, a[1]=%d\n”, a[0], a[1]);
}
0x 40ea 0800 a
3, 4
と表示される：
関数 f からは、 a の名前で実体を参照する。
仮引数 int a[]
for (i = 0; a[i] != EOSET; i++) { printf("%d ",a[i]);
}
printf("\n");
戻り値なし（ void ） void printset( int a[] )
printf("s[]: ");
printset(s);
return 0;
int main( void)
変数 int s[MAX]
s[0] s[1] s[2] … s[15] … a[99]
3 4 2 … EOSET … …
s = 0x 40ea 0800
変数 int i
printf("s[]: ");
printset(s);
return 0;
int main( void) 変数 int s[MAX]
s[]:
s[0] s[1] s[2] … s[15] … a[99]
3 4 2 … EOSET … …
s = 0x 40ea 0800
printf("s[]: ");
printset(s);
return 0;
int main( void) 変数 int s[MAX]
s[]:
s[0] s[1] s[2] … s[15] … a[99]
3 4 2 … EOSET … …
s = 0x 40ea 0800
printf("s[]: ");
printset(s);
return 0;
int main( void) 変数 int s[MAX]
s[]:
s[0] s[1] s[2] … s[15] … a[99]
3 4 2 … EOSET … …
s = 0x 40ea 0800
printset(40ea0800)
40ea0800
仮引数 int a[]
for (i = 0; a[i] != EOSET; i++) { printf("%d ",a[i]);
}
printf("\n");
戻り値なし（ void ） void printset( int a[] )
変数 int i
printf("s[]: ");
printset(s);
return 0;
int main( void) 変数 int s[MAX]
s[]:
s[0] s[1] s[2] … s[15] … a[99]
3 4 2 … EOSET … …
s = 0x 40ea 0800
printset(40ea0800)
40ea0800
仮引数 int a[]
for (i = 0; a[i] != EOSET; i++) { printf("%d ",a[i]);
}
printf("\n");
戻り値なし（ void ） void printset( int a[] )
変数 int i
値渡しによる 関数呼び出し Call by Value
ポインタによる参照 Reference
参照渡しによる 関数呼び出しに相当 Call by Reference
printf("s[]: ");
printset(s);
return 0;
int main( void) 変数 int s[MAX]
s[]:
s[0] s[1] s[2] … s[15] … a[99]
3 4 2 … EOSET … …
s = 0x 40ea 0800
printset(40ea0800)
40ea0800
仮引数 int a[]
for (i = 0; a[i] != EOSET; i++) { printf("%d ",a[i]);
}
printf("\n");
戻り値なし（ void ） void printset( int a[] )
0
変数 int i
printf("s[]: ");
printset(s);
return 0;
int main( void) 変数 int s[MAX]
s[]:
s[0] s[1] s[2] … s[15] … a[99]
3 4 2 … EOSET … …
s = 0x 40ea 0800
printset(40ea0800)
40ea0800
仮引数 int a[]
for (i = 0; a[i] != EOSET; i++) { printf("%d ",a[i]);
}
printf("\n");
戻り値なし（ void ） void printset( int a[] )
0
変数 int i
a[0]
printf("s[]: ");
printset(s);
return 0;
int main( void) 変数 int s[MAX]
s[]: 3
s[0] s[1] s[2] … s[15] … a[99]
3 4 2 … EOSET … …
s = 0x 40ea 0800
printset(40ea0800)
40ea0800
仮引数 int a[]
for (i = 0; a[i] != EOSET; i++) {
printf("%d ",a[i]);}
printf("\n");
戻り値なし（ void ） void printset( int a[] )
0
変数 int i
a[0]
printf("s[]: ");
printset(s);
return 0;
int main( void) 変数 int s[MAX]
s[]: 3
s[0] s[1] s[2] … s[15] … a[99]
3 4 2 … EOSET … …
s = 0x 40ea 0800
printset(40ea0800)
40ea0800
仮引数 int a[]
for (i = 0; a[i] != EOSET; i++) { printf("%d ",a[i]);
}
printf("\n");
戻り値なし（ void ） void printset( int a[] )
1
変数 int i
printf("s[]: ");
printset(s);
return 0;
int main( void) 変数 int s[MAX]
s[]: 3
s[0] s[1] s[2] … s[15] … a[99]
3 4 2 … EOSET … …
s = 0x 40ea 0800
printset(40ea0800)
40ea0800
仮引数 int a[]
for (i = 0; a[i] != EOSET; i++) { printf("%d ",a[i]);
}
printf("\n");
戻り値なし（ void ） void printset( int a[] )
1
変数 int i
a[1]
printf("s[]: ");
printset(s);
return 0;
int main( void) 変数 int s[MAX]
s[]: 3 4
s[0] s[1] s[2] … s[15] … a[99]
3 4 2 … EOSET … …
s = 0x 40ea 0800
printset(40ea0800)
40ea0800
仮引数 int a[]
for (i = 0; a[i] != EOSET; i++) {
printf("%d ",a[i]);}
printf("\n");
戻り値なし（ void ） void printset( int a[] )
1
変数 int i
a[1]
サンプルプログラム： 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.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 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;
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]; /* 配列の最後のマークも移動 */
}
仮引数 int a[]
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 ） void rmdup( int a[] )
printf("rmdup(s)\n");
rmdup(s);
printf("s[]: ");
printset(s);
return 0;
int main( void)
変数 int s[MAX]
s[0] s[1] s[2] s[3] s[4] s[5] …
3 4 2 6 2 9 …
s = 0x 40ea 0800
変数 int i
変数 int j
変数 int d
printf("rmdup(s)\n");
rmdup(s);
printf("s[]: ");
printset(s);
return 0;
int main( void) 変数 int s[MAX]
rmdup(s)
s[0] s[1] s[2] s[3] s[4] s[5] …
3 4 2 6 2 9 …
s = 0x 40ea 0800
printf("rmdup(s)\n");
rmdup(s);
printf("s[]: ");
printset(s);
return 0;
int main( void) 変数 int s[MAX]
rmdup(s)
s[0] s[1] s[2] s[3] s[4] s[5] …
3 4 2 6 2 9 …
s = 0x 40ea 0800
printf("rmdup(s)\n");
rmdup(s);
printf("s[]: ");
printset(s);
return 0;
int main( void) 変数 int s[MAX]
rmdup(s)
s[0] s[1] s[2] s[3] s[4] s[5] …
3 4 2 6 2 9 …
s = 0x 40ea 0800 仮引数 int a[]
40ea0800for(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 ） void rmdup( int a[] )
変数 int i
変数 int j
変数 int d
rm dup (40 ea0 800 )
rmdup(s)
a[0] a[1] a[2] a[3] a[4] a[5] …
3 4 2 6 2 9 …
40ea0800
仮引数 int a[]
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 ） void rmdup( int a[] )
変数 int i 変数 int j 変数 int d
rmdup からは、配列名 a によって配列 s を参照している
: 配列 a だと思えばよい。
a[0] a[1] a[2] a[3] a[4] a[5] …
3 4 2 6 2 9 …
i = 0
1 j =
a[j] == a[i] ?
a[0] a[1] a[2] a[3] a[4] a[5] …
3 4 2 6 2 9 …
i = 0
2 j =
a[j] == a[i] ?
a[0] a[1] a[2] a[3] a[4] a[5] …
3 4 2 6 2 9 …
i = 0
3 j =
a[j] == a[i] ?
a[0] a[1] a[2] a[3] a[4] a[5] …
3 4 2 6 2 9 …
i = 0
… j =
a[j] == a[i] ?
a[j] == EOSET までループ（内側のループ）
a[0] a[1] a[2] a[3] a[4] a[5] …
3 4 2 6 2 9 …
i = 1
2 j =
a[j] == a[i] ?
i に 1 を追加（外側のループ）
a[0] a[1] a[2] a[3] a[4] a[5] …
3 4 2 6 2 9 …
i = 1
3 j =
a[j] == a[i] ?
a[0] a[1] a[2] a[3] a[4] a[5] …
3 4 2 6 2 9 …
… j =
a[j] == a[i] ?
a[j] == EOSET までループ（内側のループ）
i = 1
a[0] a[1] a[2] a[3] a[4] a[5] …
3 4 2 6 2 9 …
i = 2 i に 1 を追加（外側のループ）
3 j =
a[j] == a[i] ?
a[0] a[1] a[2] a[3] a[4] a[5] …
3 4 2 6 2 9 …
i = 2
4 j =
a[j] == a[i] ビンゴ！
a[0] a[1] a[2] a[3] a[4] a[5] …
3 4 2 6
NUMBERNOT9 …
i = 2
4 j =
a[j] == a[i] ビンゴ！
a[0] a[1] a[2] a[3] a[4] a[5] …
3 4 2 6
NUMBERNOT9 …
i = 2
… j =
a[j] == a[i] ?
a[j] == EOSET までループ（内側のループ）
a[0] a[1] a[2] a[3] a[4] a[5] …
3 4 2 6
NUMBERNOT9 …
i = …
… j =
a[j] == a[i] ?
a[i] == EOSET までループ（外側のループ）
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] …
3 4 2 6
NUMBERNOT9
NUMBERNOT NUMBERNOT1 …
i = 0
0
d =
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] …
3 4 2 6
NUMBERNOT9
NUMBERNOT NUMBERNOT1 …
i = 1
0
d =
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] …
3 4 2 6
NUMBERNOT9
NUMBERNOT NUMBERNOT1 …
i = 2
0
d =
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] …
3 4 2 6
NUMBERNOT9
NUMBERNOT NUMBERNOT1 …
i = 3
0
d =
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] …
3 4 2 6
NUMBERNOT9
NUMBERNOT NUMBERNOT1 …
i = 4
1
d =
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] …
3 4 2 6
NUMBERNOT9
NUMBERNOT NUMBERNOT1 …
i = 5
1 d =
a[ i-d] = a[i];
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] …
3 4 2 6 9 9
NUMBERNOT NUMBERNOT1 …
i = 5
1 d =
a[ i-d] = a[i];
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] …
3 4 2 6 9 9
NUMBERNOT NUMBERNOT1 …
i = 6
2
d =
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] …
3 4 2 6 9 9
NUMBERNOT NUMBERNOT1 …
i = 7
3
d =
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] …
3 4 2 6 9 9
NUMBERNOT NUMBERNOT1 …
i = 8
3 d =
a[ i-d] = a[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
NUMBERNOT NUMBERNOT1 …
i = 8
3 d =
a[ i-d] = a[i];
a[0] a[1] a[2] a[3] a[4] a[5] a[…] a[.] a[8] …
3 4 2 6 9 1 …
EOSET1 …
15 i =
… d =
a[ i-d] = a[i];
a[0] a[1] a[2] a[3] a[4] a[5] a[…]
3 4 2 6 9 1 …
` 15 i =
40ea0800
仮引数 int a[]
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 ） void rmdup( int a[] )
変数 int i
変数 int j
変数 int d
printf("rmdup(s)\n");
rmdup(s);
printf("s[]: ");
printset(s);
return 0;
int main( void)
変数 int s[MAX]
s[0] s[1] s[2] s[3] s[4] s[5] …
3 4 2 6 2 9 …
s = 0x 40ea 0800
a[0] a[1] a[2] a[3] a[4] a[5] a[…]
3 4 2 6 9 1 …
15 i =
40ea0800
仮引数 int a[]
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 ） void rmdup( int a[] )
変数 int i 変数 int j 変数 int d
re tu rn
rmdup(s)
printf("rmdup(s)\n");
rmdup(s);
printf("s[]: ");
printset(s);
return 0;
int main( void)
変数 int s[MAX]
s[0] s[1] s[2] s[3] s[4] s[5] …
3 4 2 6 2 9 …
s = 0x 40ea 0800
s[0] s[1] s[2] s[3] s[4] s[5] s[…]
3 4 2 6 9 1 …
rmdup(s)
s[0] s[1] s[2] s[3] s[4] s[5] …
3 4 2 6 2 9 …
rmdup(s) の呼び出し前
rmdup(s) から参照されて、
main 関数内の自動配列変数 s の中身が
変更された。
printf("rmdup(s)\n");
rmdup(s);
printf("s[]: ");
printset(s);
return 0;
int main( void)
変数 int s[MAX]
s[0] s[1] s[2] s[3] s[4] s[5] …
3 4 2 6 2 9 …
s = 0x 40ea 0800
s[0] s[1] s[2] s[3] s[4] s[5] s[…]
3 4 2 6 9 1 …
rmdup(s)
s[]: 3 4 2 6 9 1 5 6 8
