1.5.4　集合

從邏輯結構上看，集合的元素之間沒有任何確定的依賴關系，主要考慮集合之間的并、交和差操作。

1．集合的定義

數學意義上的集合概念在計算機科學上有著廣泛的用途。

定義8　在研究某一類對象時，可把這類對象的整體稱為集合，組成一個集合的對象稱為該集合的元素。

設A是一個集合，a是集合A中的元素，可表示為a∈A，讀作a屬于A。如果a不是集合A的元素，則表示為a?A，讀作a不屬于A。

有限個元素x₁，x₂，…，x_n組成的集合，稱為有限集合。無限個元素組成的集合，稱為無限集合。把不含元素的集合，稱為空集，記為?。

2．集合之間的關系

（1）設兩個集合A，B包含的元素完全相同，則稱集合A和B相等，表示為A=B。

應指出，一個集合中元素排列的順序是無關緊要的。另外，有限集合A中不同元素的個數稱為集合的基數，表示為#A或|A|。

（2）設兩個集合A和B，當A的元素都是B的元素時，稱A包含于B，或稱A是B的子集，表示為A?B；當A?B且A≠B時，稱A是B的真子集，表示為A?B。應指出，空集?是任何集合的一個子集。

如果所研究的集合皆為某個集合的子集，則稱該集合為全集，記為E。

接下來，由子集的概念引出另一個重要概念——冪集。

設A是一個集合，則A的所有子集組成的集合稱為A的冪集，表示為ρ（A）。

例如：設A={a，b，c}，則有ρ（A）={?，{a}，{b}，{c}，{a，b}，{b，c}，{a，c}，{a，b，c}}。

（3）從（1）和（2）可知，對于任意兩個集合A和B，A=B的充要條件是A?B且B?A。

3．集合的運算

（1）設有兩個集合A和B，則由A和B的所有共同元素構成的集合，稱為A和B的交集，表示為A∩B。

（2）設有兩個集合A和B，則所有屬于A或屬于B的元素組成的集合，稱為A和B的并集，表示為A∪B。

（3）設有兩個集合A和B，則所有屬于A而不屬于B的一切元素組成的集合，稱為B對A的補集，表示為A-B。設有全集E和集合A，則稱E-A是集合A的補集，表示為。

（4）設有兩個集合A和B，則所有序偶<a，b>組成的集合，稱為A，B的笛卡兒乘積，表示為A×B，那么，A×B={<a，b>|a∈A且b∈B}。

序偶集合的元素排列是有順序的，不能任意顛倒。

4．集合的表示

表示集合的方法有很多，表示方法的不同將造成查找等運算的算法也不同，所以集合的表示方法將直接影響集合運算的效率。在計算機應用中，集合有以下幾種表示方法：位向量、線性表、搜索樹、跳表和散列表，這里簡單介紹前兩種。

（1）只考慮集合U的子集，用位串來表示集合。如果集合U具有n個元素，那么U的任何子集S能夠用一個長度為n的位串來表示，稱為位向量。當且僅當U的第i個元素包含在S中時，向量中第i個元素為1。例如：U={1，2，3，4，5，6，7，8，9}，那么S={2，3，5，7}可以用位串011010100表示。這種表示法使得實現非?？焖俚臉藴始线\算成為可能，但是所需的存儲空間較大。

（2）用線性表來表示集合元素。當然，這個方法只有對有限集合才是可行的。