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）用线性表来表示集合元素。当然，这个方法只有对有限集合才是可行的。