アルゴリズムと
データ構造
第11回
集合
集合とは
集合と要素
集合：ものの集まり
要素：集合中の個々のもの
要素はそれ以上分解できないもの（アトム）でも
集合でもよい
各要素はすべて互いに異なる
同じ要素を含む集合：多重集合
集合とは
集合の例
X 1,5
X 5,1
N 1,2,3,4,...
/* 要素に1と5を持つ集合 */
/* 要素には順序なし：上の集合と同じ */
/* 自然数の集合 */
1,2,3,4,...
Z 0
1,2,3,4,...
/* 整数の集合 */
集合とは
集合の用語
aが集合Xの要素→
aはXに属する
a X
2つの集合XとYの要素が同じ→XとYは等しい
X Y
要素数が有限：有限集合
要素数が無限：無限集合
集合とは
集合の要素数
要素数n
X n
X
X 1
X 0
要素数無限大
要素数1（1個でも集合）
要素数0：空集合 で表す
集合とは
部分集合
集合Aのすべての要素が集合Bの要素となってい
る→AはBに含まれる： AはBの部分集合
A B
例：1, 3 1,3,5
A B かつ B A ならば A B
A B かつ A B ならばAはBの真部分集合
集合とは
集合の演算
和
集合Aと集合Bの少なくとも一方に属す要素の集合
積
集合Aと集合Bの両方に属す要素の集合
差
集合Aの要素であり集合Bに属さない要素の集合
集合とは
集合の演算
和
積
A
B
A B
差
A
B
A B
A
B
A B
配列による集合
配列で集合を表現
すべての要素が整数の集合→整数配列で実現
配列への格納順序は任意
並べ替える必要なし
配列全体をそっくり集合として取り扱い
集合の要素数と配列の要素数を等しく
動的に配列を確保
配列による集合
配列による集合の実装
集合への要素の追加（Add）
追加しようとする要素がすでに存在しているかをチェッ
クし、存在していなければ追加
配列の最後尾に挿入
集合からの要素の削除（Remove）
削除しようとする要素が存在するかをチェックし、存在
していれば削除
配列から削除したあと、隙間を埋める
配列による集合
配列による集合の実装
集合の和（Union）
一方の集合に、もう一方の集合の全要素を追加
集合の積（Intersection）
2つの集合の全要素を比較し、両方の集合に含まれて
いる要素のみ取り出し
集合の差（Difference）
一方の集合の各要素のうち、もう一方の集合の全要
素と一致しない要素のみを取り出し
ビットベクトルによる集合
ビットベクトルで集合を表現
要素の有無を、各ビットの0、1で表現
1になっているビットの要素が存在
空集合なら全ビットが0
32ビットなら{0,1,...,31}を要素とする集合が表現可能
下位
上位
00000000000000000000000000000000
第31ビット
第0ビット
ビットベクトルによる集合
ビットベクトルによる集合の例
空集合
00000000000000000000000000000000
{1,5,7,23}
00000000100000000000000010100010
ビットベクトルによる集合
ビットベクトルによる集合の実装
ある要素のみの集合の生成（SetOf）
第0ビットのみ1のビットベクトルを要素の値分左シフト
要素が集合に含まれるかの判定（IsMember）
SetOfで判定する要素を生成して集合と論理積をとり、
全ビットが0になれば含まれない
ビットベクトルによる集合
ビットベクトルによる集合の実装
要素が集合に含まれるかの判定（含まれる場合）
01001000110011000000111000000000
00000000000000000000010000000000
00000000000000000000010000000000
ビットベクトルによる集合
ビットベクトルによる集合の実装
要素が集合に含まれるかの判定（含まれない場合）
01001000110011000000101000000000
00000000000000000000010000000000
00000000000000000000000000000000
ビットベクトルによる集合
ビットベクトルによる集合の実装
集合への要素の追加（Add）
SetOfで追加する要素を生成して集合と論理和をとる
集合からの要素の削除（Remove）
SetOfで追加する要素を生成したあと全ビット反転し、集合と論理
積をとる
集合に含まれる要素数（Size）
集合のビットベクトルから1を引いたものを生成し、集合と論理積
をとる
上記の処理を、全ビットが0になるまで行った回数が要素数
ビットベクトルによる集合
ビットベクトルによる集合の実装
集合への要素の追加
01001000110011000000101000000000
00000000000000000000010000000000
01001000110011000000111000000000
ビットベクトルによる集合
ビットベクトルによる集合の実装
集合からの要素の削除
01001000110011000000111000000000
01
1
01
01
01
01
01
01
00
10
10
10
11
01
01
01
01
01
01
01
01
00
11
01
00
10
10
10
11
01
01
01
0
01001000110011000000101000000000
ビットベクトルによる集合
ビットベクトルによる集合の実装
集合に含まれる要素数
00
1000
10000
10
1000
10
10000000
10
10
1000000000
00
11
01
00
11
01
01
00
11
00
10
10
10
11
01
01
01
01
01
00
10
11
0111111111
00
1000
10000
10
1000
10
10000000
10
10000000000
ビットベクトルによる集合
ビットベクトルによる集合の実装
集合の和
2つの集合の論理和をとる
集合の積
2つの集合の論理積をとる
集合の差
引く集合を反転し、引かれる集合との論理積をとる
ビットベクトルによる集合
ビットベクトルによる集合の実装
集合の差
01001000110011000000101000101010
11
00
11
01
00
11
00
10
11
00
11
00
11
00
11
00
10
11
00
11
00
11
01
00
11
01
00
10
10
1
0
01
01
01001000010010000000000000001000
© Copyright 2024 ExpyDoc
