集合和字典

集合及其表示

基本概念

• 用位向量实现集合
当集合是全集合 { 0, 1, 2, …, n } 的一个子集，且 n 是不大的整数时，可用位(0, 1)向量来实现集合。
当全集合是由有限个可枚举的成员组成时，可建立全集合成员与整数 0, 1, 2, …的一一对应关系，用位向量来表示该集合的子集。
一个二进位有两个取值1或0，分别表示在集合与不在集合。如果采用16位无符号短整数数组bitVector[]作为集合的存储，就要考虑如何求出元素 i 在bitVector数组中的相应位置。
代码

用有序链表实现集合

• 用有序链表来表示集合时，链表中的每个结点表示集合的一个成员。

• 各结点所表示的成员 e0, e1, …, en 在链表中按升序排列，即 e0 < e1 < … < en。

• 集合成员可以无限增加。因此，用有序链表可以表示无穷全集合的子集。

等价类与并查集

等价关系与等价类(Equivalence Class)

• 在求解实际应用问题时常会遇到等价类问题。

• 从数学上看，等价类是对象（或成员）的集合，在此集合中所有对象应满足等价关系。

• 若用符号“”表示集合上的等价关系，则对于该集合中的任意对象x, y, z，下列性质成立：
• 自反性：x=x (即等于自身)。
• 对称性：若 x=y, 则 y=x。
• 传递性：若 x=y且 y=z, 则 x=z。

• 因此，等价关系是集合上的一个自反、对称、传递的关系。

• “相等”(=)就是一种等价关系，它满足上述的三个特性。

• 一个集合 S 中的所有对象可以通过等价关系划分为若干个互不相交的子集 S1, S2, S3, …，它们的并就是 S。这些子集即为等价类。

• 确定等价类的方法
确定等价类的方法分两步走：
• 读入并存储所有的等价对( i, j )；
• 标记和输出所有的等价类。

并查集 (Union-Find Sets)

• 并查集支持以下三种操作：
• Union (Root1, Root2) //合并操作
• Find (x) //查找操作
• UFSets (s) //构造函数
• 对于并查集来说，每个集合用一棵树表示。
• 为此，采用树的双亲表示作为集合存储表示。集合元素的编号从0到 n-1。其中 n 是最大元素个数。

• 在双亲表示中，第 i 个数组元素下标代表包含集合元素 i 的树结点。根结点的双亲为 -k，表示集合中的元素个数为k。

• 同一棵树上所有结点所代表的集合元素在同一个子集合中。为此，需要有两个映射：
• 集合元素到存放该元素名的树结点间的对应；
• 集合名到表示该集合的树的根结点间的对应。

• 初始时, 用构造函数 UFSets(s) 构造一个森林, 每棵树只有一个结点, 表示集合中各元素自成一个子集合。

• 用 Find(i) 寻找集合元素 i 的根。如果有两个集合元素 i 和 j, Find(i) == Find(j), 表明这两个元素在同一个集合中，

• 如果两个集合元素 i 和 j 不在同一个集合中,可用 Union(i, j) 将它们合并到一个集合中。
代码

• Find 和 Union 操作性能不好。假设最初 n 个元素构成 n 棵树组成的森林，parent[i] = -1。做处理Union(n-2, n-1), …, Union(1, 2), Union(0, 1)后，将产生退化的树。

• 执行一次Union操作所需时间是 O(1)，n-1次Union操作所需时间是O(n)。

• 若再执行Find(0), Find(1), …, Find(n-1), 若被搜索的元素为 i，完成 Find(i) 操作需要时间为O(i+1)，完成 n 次搜索需要的总时间将达到O(n^2)

• 改进的方法
• 按树的结点个数合并：结点个数多的树的根结点作根
• 按树的高度合并：高度高的树的根结点作根
• 压缩元素的路径长度

字典

• 字典是一些元素的集合，每个元素有一个称作关键码（key）的域，不同元素的关键码互不相同。
• 文件（File）
• 表格（Table）

• 在讨论字典抽象数据类型时，把字典定义为<名字-属性>对的集合。根据问题的不同，可以为名字和属性赋予不同的含义。

• 例如，在图书馆检索目录中，名字是书名，属性是索书号及作者等信息；在计算机活动文件表中，名字是文件名，属性是文件地址、大小等信息。

• 一般来说，有关字典的操作有如下几种：
• 确定一个指定的名字是否在字典中；
• 搜索出该名字的属性；
• 修改该名字的属性；
• 插入一个新的名字及其属性；
• 删除一个名字及其属性。
• 用文件记录（record）或表格的表项（entry）来表示单个元素时，用：（关键码key，记录或表项位置指针adr）构成搜索某一指定记录或表项的索引项。

字典的线性表描述

• 字典可以保存在线性序列 (e1,e2,…) 中，其中ei 是字典中的元素，其关键码从左到右依次增大。为了适应这种描述方式，可以定义有序顺序表和有序链表。

• 用有序链表来表示字典时，链表中的每个结点表示字典中的一个元素，各个结点按照结点中保存的数据值非递减链接，即e1≤e2 ≤ …。因此，在一个有序链表中寻找一个指定元素时，一般不用搜索整个链表。

• 有序顺序表顺序搜索的时间代价
• 衡量一个搜索算法的时间效率的标准是：在搜索过程中关键码平均比较次数，也称为平均搜索长度ASL (Average Search Length)，通常它是字典中元素总数 n 的函数。
• 设搜索第 i 个元素的概率为 pi, 搜索到第 i 个元素所需比较次数为 ci, 则搜索成功的平均搜索长度:
• 在顺序搜索情形，搜索第 个元素需要比较 次，假定按等概率搜索各元素：
• 这与一般顺序表情形相同。但搜索不成功时不需一直比较到表尾，只要发现下一个元素的值比给定值大，就可断定搜索不成功。设一个有 n 个表项的表，查找失败的位置有n+1个，可以用决策树加以描述。搜索成功时停在内结点，搜索失败时停在外结点。
也就是说，现在是对位置的统计



• 判定树是一种扩充二叉树。内结点代表顺序表中已有的元素，外结点代表失败结点，它表示在两个相邻已有元素值之间的值。
• 假定表中所有失败位置的搜索概率相同，则搜索不成功的平均搜索长度：
时间代价为O(n)。为了加速搜索，在有序顺序表的情形，可以采用折半搜索，它也称二分搜索，时间代价可减小到O(log2n)。
• 二分搜索

• 有序链表的实现
代码

散列表

• 如果在元素存储位置与其关键码之间建立一个确定的对应函数关系Hash()， 使得每个关键码与唯一的存储位置相对应：Address ＝ Hash(key)

• 在插入时依此函数计算存储位置并按此位置存放。在搜索时对元素的关键码进行同样的计算，把求得的函数值当做元素存储位置，然后按此位置搜索。这就是散列方法。

• 使用散列方法进行搜索不必进行多次关键码的比较, 搜索速度比较快, 可以直接到达或逼近具有此关键码的表项的实际存放地址。

• 散列函数是一个压缩映象函数。关键码集合比散列表地址集合大得多。因此有可能经过散列函数的计算，把不同的关键码映射到同一个散列地址上，这就产生了冲突。

• 对不同的关键码，通过散列函数的计算，得到了同一散列地址。称这些产生冲突的散列地址相同的不同关键码为同义词。

• 由于关键码集合比地址集合大得多, 冲突很难避免。所以对于散列方法, 需要讨论以下两个问题：
• 对于给定的一个关键码集合，选择一个计算 简单且地址分布比较均匀的散列函数，避免或尽量减少冲突；
• 设计解决冲突的方案。

• 构造散列函数时的几点要求：
• 散列函数应是简单的，能在较短的时间内计算出结果。
• 散列函数的定义域必须包括需要存储的全部关键码，如果散列表允许有 m 个地址时，其值域必须在 0 到 m-1 之间。
• 散列函数计算出来的地址应能均匀分布在整个地址空间中 : 若 key 是从关键码集合中随机抽取的一个关键码, 散列函数应能以同等概率取0 到 m-1 中的每一个值。

• 直接定址法
• 此类函数取关键码的某个线性函数值作为散列地址：
• {a, b为常数}
• 这类散列函数是一对一的映射，一般不会产生冲突。但它要求散列地址空间的大小与关键码集合的大小相同。

• 数字分析法
• 设有 n 个 d 位数, 每一位可能有 r 种不同的符号。这 r 种不同符号在各位上出现的频率不一定相同。根据散列表的大小, 选取其中各种符号分布均匀的若干位作为散列地址。
• 计算各位数字中符号分布均匀度的公式：
其中表示第 个符号在第 位上出现的次数， 表示各种符号在 个数中均匀出现的期望值。
• 计算出的  值越小，表明在该位 (第 k 位) 各种符号分布得越均匀。
• 数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况，它完全依赖于关键码集合。如果换一个关键码集合，选择哪几位要重新决定。

• 除留余数法
• 设散列表中允许地址数为m，取一个不大于 m，但最接近于或等于 m 的质数 p 作为除数，用以下函数把关键码转换成散列地址:
• 其中，“%”是整数除法取余的运算，要求这时的质数 p 不是接近 2 的幂。

• 平方取中法
• 它首先计算构成关键码的标识符的内码的平方, 然后按照散列表的大小取中间的若干位作为散列地址。
• 设标识符可以用一个计算机字长的内码表示。因为内码平方数的中间几位一般是由标识符所有字符决定, 所以对不同的标识符计算出的散列地址大多不相同。
• 在平方取中法中, 一般取散列地址为8的某次幂。例如, 若散列地址总数取为 m = 8r，则对内码的平方数取中间的 r 位。

• 折叠法

• 此方法把关键码自左到右分成位数相等的几部分, 每一部分的位数应与散列表地址位数相同, 只有最后一部分的位数可以短一些。

• 把这些部分的数据叠加起来, 就可以得到具有该关键码的记录的散列地址。

• 有两种叠加方法：
• 移位法：把各部分最后一位对齐相加。
• 分界法：各部分不折断，沿各部分的分界来回折叠, 然后对齐相加。
• 示例: 设给定的关键码为 key = 23938587841, 若存储空间限定 3 位, 则划分结果为每段 3 位。 上述关键码可划分为 4 段：239 385 878 41
叠加，然后把超出地址位数的最高位删去, 仅保留最低的3 位，做为可用的散列地址。

处理冲突的闭散列方法

• 线性探查法 (Linear Probing)
• 需要搜索或加入一个表项时, 使用散列函数计算关键字在表中的位置： H0 = hash ( key )
• 一旦发生冲突，在表中顺次向后寻找下一 个位置 Hi ： Hi = ( Hi-1 +1 ) % m， i =1, 2, …, m-1
• 即用以下的线性探查序列在表中寻找下一 个位置： H0 +1, H0 +2, …, m-1, 0, 1, 2, …, H0-1
• 亦可写成如下的通项公式： Hi = ( H0 + i ) % m， i =1, 2, …, m-1

• 平方探查(Quadratic probing)
• 设H0 = hash(key), 一旦发生冲突，在表中顺次向后寻找下一个位置
• 通项公式

• 二次散列(Double Hashing)
• hash1(key)=d, 当其地址d已经被其他元素占有了，则计算 hash2(key) =c, 在表中顺次检查相应的地址 d+c, d+2c, d+3c。

处理冲突的开散列方法（链地址法）

• 开散列方法首先对关键码集合用某一个散列函数计算它们的存放位置。

• 若设散列表地址空间的位置从 0～m1, 则关键码集合中的所有关键码被划分为 m 个子集，具有相同地址的关键码归于同一子集。我们称同一子集中的关键码互为同义词。每一个子集称为一个桶。

• 通常各个桶中的表项通过一个单链表链接起来，称之为同义词子表。

• 所有桶号相同的表项都链接在同一个同义词子表中，各链表的表头结点组成一个向量。

• 向量的元素个数与桶数一致。桶号为i的同义词子表的表头结点是向量中第 i 个元素。

• 示例：给出一组表项关键码{Burke,Ekers,Broad, Blum, Attlee, Alton, Hecht, Ederly }。散列函数为：Hash (x)＝ord (x)－ord (‘A’)

• 通常，每个桶中的同义词子表都很短，设有n个关键码通过某一个散列函数，存放到散列表中的 m 个桶中。那么每一个桶中的同义词子表的平均长度为 n / m。以搜索平均长度为 n /m 的同义词子表代替了搜索长度为 n 的顺序表，搜索速度快得多。