集合の表現 - 横浜国立大学富井研究室

アルゴリズムとデータ構造
補足資料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
#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の２か所を参照する。
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[…]
…
……

Download Report