算法与数据结构(c语言)第6章集合与字典

《算法与数据结构(c语言)第6章集合与字典》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章集合与字典从逻辑结构上看，集合和字典都是最简单的数据结构，它们的元素之间没有任何确定的依赖关系。字典是关联的集合。作为抽象数据类型，集合和字典之间的主要区别，在于它们的操作。集合主要考虑集合之间的并、交和差操作；字典主要关心其元素的检索、插入和删除。目录6.1集合及其抽象数据类型6.1.1基本概念6.1.2主要运算6.1.3抽象数据类型6.2集合的实现6.2.1集合的位向量表示6.2.2集合的单链表表示6.3字典及其抽象数据类型6.3.1基本概念6.3.2抽象数据类型6.4字典的顺序表示6

2、.4.1存储结构6.4.2算法的实现6.4.3有序顺序表与二分法检索6.5字典的散列表示6.5.1基本概念6.5.2散列函数6.5.3碰撞的处理6.5.4散列文件6.1集合及其抽象数据类型6.1.1基本概念集合是数学中最基本的概念，也是一种基本数据结构。在数学中，集合是一些互不相同元素的无序汇集。这些元素称为该集合的成员。集合中的成员可以是一个原子（不可再分解）；也可以是一个结构，甚至又是一个集合。集合中的各个元素应该是互不相同的。列举法:定义一个有穷集，可以将成员放在一对花括号中，成员之间用逗号

3、隔开。例如｛１，2，４｝谓词描述法:集合的大小:集合中所包含的元素的个数。空集子集超集数据结构中讨论的集合，一般有以下限制：1）数据结构讨论的集合总限制为有穷集；2）假定集合中所有元素属同一类型；并且假设元素之间存在一个小于关系“＜”，也称为有序集。6.1.2主要运算集合也可以定义测试一个元素是否存在于集合中、增加一个元素、删除一个元素等运算，但集合更加关心下面的一些运算。求并集：求交集：求差集：子集：A是B的子集如果集合A是B的子集，反过来也称集合B是A的超集。相等：例如：若Ａ＝｛ａ，ｂ，ｃ｝，

4、Ｂ＝｛ｂ，ｄ｝，则有Ａ∪Ｂ＝｛ａ，ｂ，ｃ，ｄ｝，Ａ∩Ｂ＝｛ｂ｝，Ａ－Ｂ＝｛ａ，ｃ｝。另外，Ａ不等于Ｂ，同时Ａ和Ｂ相互都不是子集关系。……上面集合间的运算，都可以通过增加元素、删除元素和成员测试等运算来实现。例如：已知集合A和B，求它们的并集，只要以集合A（或B）为基础，把集合B（或A）的元素逐个插入。如果要求两个集合的交集，只要从A（或B）出发，检查各元素是否在B（或A）中出现，把那些也在另一个集合里出现的元素插入（初态为空集）的集合中即可。求A与B的差集A−B时，只要以A为基础，对每个B中的元素

5、做删除运算即可。6.1.3抽象数据类型ADTSetisoperationsSetcreateEmptySet(void)创建一个空集合。intmember（SetＡ，DataTypeｘ）当ｘ∈Ａ时返回真值，否则取假值。intinsert（SetＡ，DataTypeｘ）使ｘ作为Ａ的一个成员,如果ｘ本来就是Ａ的成员，则Ａ不变。intdelete（SetＡ，DataTypeｘ）将ｘ从Ａ中删除，如果ｘ本来就不在Ａ中，则不改变Ａ。intunion（SetＡ，SetＢ，SetＣ）求集合Ａ和Ｂ的并集

6、，结果在集合Ｃ中。intintersection（SetＡ，SetＢ，SetＣ）求集合Ａ和Ｂ的交集，结果在集合Ｃ中。intdifference（SetＡ，SetＢ，SetＣ）求集合Ａ和Ｂ的差集，结果在集合Ｃ中。intsubset（SetＡ，SetＢ）当且仅当Ａ是Ｂ的子集时，函数值才为真。endADTSet6.2集合的实现位向量表示单链表表示6.2.1位向量表示位向量是一种每个元素都是二进制位（即0/1值）的数组。当表示的集合存在某个不太大的公共超集时，采用位向量的方式来表示这种集合往

7、往十分有效。假设需要表示的集合的公共超集中，共有ｎ个不同的元素，为叙述的方便，不妨假设这些元素就是整数0，１，２，…，ｎ-1等。每个集合可以采用一个有ｎ位的位向量来表示。若整数ｉ是这个集合的一个元素，则位向量中对应的位为１（真），否则为0（假）。存储结构由于在C语言中无法直接定义位数组，要定义位向量，需要借助其它方式。一种比较自然的方式，是用长度为n/8的字符数组表示长度为n的字位数组。一个字符用8位二进制编码，它实际上包含了8个二进制位。位向量表示集合的存储结构：typedefstruct{in

8、tsize;/*字符数组的长度*/char*array;/*位向量空间。每一数组元素保存8位。*/}BitSet;下图给出了一个公共超集是从0到9的整数集合，采用位向量表示的存储结构示意图。从图中可以看出每个整数所对应的二进制位的位置。当集合S={1,3,5,7,9}时,它的实际存储状态如图（b）所示(注意其中元素的排列方法)。用位向量表示集合时，所占空间的大小与公共超集的大小ｎ成正比，而与要表示的集合的大小无关。算法实现以位向量表示集合，只有两个集合都是某个公共集合的子集时，它们