第6单元 集合与字典.pptVIP

第六章 集合与字典 从逻辑结构上看，集合和字典都是最简单的数据结构，它们的元素之间没有任何确定的依赖关系。字典是关联的集合。 作为抽象数据类型，集合和字典之间的主要区别，在于它们的操作。 集合主要考虑集合之间的并、交和差操作；字典主要关心其元素的检索、插入和删除。 6.1 集合及其抽象数据类型6.1.1 基本概念 数学中集合是一些互不相同元素的无序汇集。这些元素称为该集合的成员。集合中的成员可以是一个原子（不可再分解）；也可以是一个结构，甚至又是一个集合。集合中的各个元素应该是互不相同的。 元素是或不是集合A的成员，可表示为 列举法：定义一个有穷集，可以将成员放在一对花括号中，成员之间用逗号隔开。 例如｛１，2，４｝ 谓词描述法: 集合的大小: 集合中所包含的元素的个数。 空集不包含任何元素的集合，记作Ф。 数据结构中讨论的集合，一般有以下限制：数据结构讨论的集合总限制为有穷集；假定集合中所有元素属同一类型；并且假设元素之间存在一个小于关系“＜”，也称为有序集。 6.1.2 主要运算 集合可以定义测试一个元素是否存在于集合中、增加一个元素、删除一个元素等运算，但集合更加关心下面的一些运算。 求并集： 求交集： 求差集： 子集： A是B的子集 如果集合A是B的子集，反过来也称集合B是A的超集。 相等：两个集合互为子集，则称它们相等。 例如：若Ａ＝｛ａ，ｂ，ｃ｝，Ｂ＝｛ｂ，ｄ｝，则有Ａ∪Ｂ＝｛ａ，ｂ，ｃ，ｄ｝，Ａ∩Ｂ＝｛ｂ｝，Ａ－Ｂ＝｛ａ，ｃ｝。另外，Ａ不等于Ｂ，同时Ａ和Ｂ相互都不是子集关系。 6.2 集合的实现 6.2.1 位向量表示 在实际应用中的许多集合，往往都存在一个公认的超集。例如，ASCII码字符集是各种算机能够表示的字符集的超集；所有大小写英文字母的集合是各种字母集合的超集。 对于字母集合，如果按集合中每个字符的ASCII码将它们存储到一个字符数组中，则集合将占用较多的存储空间（最多需要8*26*2=416bit）。 如果英文字母超集中的每个字母对应1-56中的一个数值，则字母集可以表示为一个有52个分量的向量，每个分量的1或0表示相应数值的字母是否在该集合中。这样每个字母集合只占用很少的存储空间（52bit）。 位向量是一种每个元素都是二进制位（即0/1值）的数组。当表示的集合存在某个不太大的公共超集时，采用位向量的方式来表示这种集合往往十分有效。 存储结构 假设需要表示的集合的公共超集中，共有ｎ个不同的元素，为叙述的方便，不妨假设这些元素就是整数0，１，２，…，ｎ-1等。 每个集合可以采用一个有ｎ位的位向量来表示。若整数ｉ是这个集合的一个元素，则位向量中对应的位为１（真），否则为0（假）。 由于C语言中无法直接定义位数组，要定义位向量需要借助其它方式。一种比较自然的方式，是用长度为n/8的字符数组表示长度为n的字位数组。一个字符用8位二进制编码，它实际上包含了8个二进制位。 typedef struct { int size; //字符数组的长度 char * array; //位向量空间。每一数组元素保存8位。 } BitSet; 假设n是为向量的位数，因为n不一定是8的整数倍，所以由表达式（n+7）/8计算出来的是能保证容纳下所有的位向量的最少字节数。 为了便于操作的实现，位向量的下标在字符的8位中应该从右至左递增排列。 如图给出了公共超集从0到9的整数集合采用位向量表示的存储结构示意图，以及集合S={1,3,5,7,9}的实际存储。 当用位向量表示集合时，所占空间的大小与公共超集的大小ｎ成正比，而与要表示的集合的大小无关。 算法实现 以位向量表示集合，只有两个集合都是某个公共集合的子集时，它们互相运算才是有效的。由于在位向量定义里并没有关于集合元素的实际信息，只能要求参与运算的两个位向量长度相同。 位运算 假设x和y都是8位的字符，其值分别是： X= Y= 对x和y做各种字位运算，得到的结果如下： ~x x y x ^ y x | y x 3 y 5 空集合的创建 与空顺序表的的创建类似，不同之处在于这里省略了每个集合中实际元素个数的变量: BitSet * createEmptySet (int n) 将整数index的元素插入集合 将值为index的元素插入集合S的过程，通过将位向量中下标为index的位置为1来完成： int insert (BitSet * s, int index) 将整数