HASH GAME - Online Skill Game GET 300

　　(4) 掌握哈希表查找技术以及哈希表与其他表的本质区别。 (5) 灵活运用各种查找算法解决一些综合应用问题。 练习 教材中p265习题1、2、3和5。 上机实习题 教材中p166题3和5。 第10章 内 排 序 10.6 基数排序 本章小结 10.1 排序的基本概念 10.2 插入排序 10.3 交换排序 10.4 选择排序 10.5 归并排序 10.7 各种内排序方法的比较和选择 例10.4 假设哈希表长度m=13,采用除留余数法哈希函数建立如下关键字集合的哈希表：{16,74,60,43,54,90,46,31,29,88,77}。 解：n=11,m=13,除留余数法的哈希函数为h(k)=k mod p,p应为小于等于m的素数,假设p取值13。则有： h(16)=3,h(74)=9,h(60)=8,h(43)=4, h(54)=2,h(90)=12,h(46)=7,h(31)=5, h(29)=3, h(88)=10,h(77)=12。 注意：存在冲突。 示例: 有一个关键码 key = 962148, 哈希表大小 m = 25, 即 HT[25]。取质数 p= 23。哈希函数 hash ( key ) = key % p。则哈希地址为 hash ( 962148 ) = 962148 % 23 = 12。 可以按计算出的地址存放记录。需要注意的是, 使用上面的哈希函数计算出来的地址范围是 0到 22, 因此, 从23到24这几个哈希地址实际上在一开始是不可能用哈希函数计算出来的, 只可能在处理冲突时达到这些地址。 平方取中法 此方法在词典处理中使用十分广泛。 它先计算构成关键码的标识符的内码的平方, 然后按照哈希表的大小取中间的若干位作为哈希地址。 设标识符可以用一个计算机字长的内码表示。因为内码平方数的中间几位一般是由标识符所有字符决定, 所以对不同的标识符计算出的哈希地址大多不相同。 在平方取中法中, 一般取哈希地址为2的某次幂。例如, 若哈希地址总数取为 m = 8r，则对内码的平方数取中间的 r 位。如果 r = 3，所取得的哈希地址参看图的最右一列。 标识符 内码 内码的平方 哈希地址 A 01 01 001 A1 0134 20420 042 A9 0144 23420 342 B 02 4 004 DMAX 100 443 DMAX1 0415013034 0 352 AMAX 0 236 AMAX1 0115013034 0 652 标识符的八进制内码表示及其平方值 折叠法 此方法把关键码自左到右分成位数相等的几部分, 每一部分的位数应与哈希表地址位数相同, 只有最后一部分的位数可以短一些。 把这些部分的数据叠加起来, 就可以得到具有该关键码的记录的哈希地址。 有两种叠加方法： 移位法 — 把各部分的最后一位对齐相加； 分界法 — 各部分不折断, 沿各部分的分界来回折叠, 然后对齐相加, 将相加的结果当做哈希地址。 示例: 设给定的关键码为 key = , 若存储空间限定 3 位, 则划分结果为每段 3 位。 上述关键码可划分为 4段： 239 385 878 41 把超出地址位数的最高位删去, 仅保留最低的3位，做为可用的哈希地址。 移 位 法 分 界 法 一般当关键码的位数很多，而且关键码每一位上数字的分布大致比较均匀时，可用这种方法得到哈希地址。 以上介绍了几种常用的哈希函数。在实际工作中应根据关键码的特点，选用适当的方法。有人曾用“轮盘赌”的统计分析方法对它们进行了模拟分析，结论是平方取中法最接近于“随机化”。 处理冲突的闭哈希方法 因为任一种哈希函数也不能避免产生冲突，因此选择好的解决冲突的方法十分重要。 为了减少冲突，对哈希表加以改造。若设哈希表 HT 有 m 个地址, 将其改为 m 个桶。其桶号与哈希地址一一对应, 第 i (0 ? i m) 个桶的桶号即为第 i 个哈希地址。 每个桶可存放 s 个表项, 这些表项的关键码互为同义词。如果对两个不同表项的关键码用哈希函数计算得到同一个哈希地址，就产生了冲突，它们可以放在同一个桶内的不同位置。 只有当桶内所有 s 个表项位置都放满表项后再加入表项才会产生溢出。 通常桶的大小 s 取的比较小, 因此在桶内大多采用顺序搜索。 闭哈希也叫做开地址法。在闭哈希情形, 所有的桶都直接放在哈希表数组中。因此每个桶只有一个表项 ( s = 1 )。 若设哈希表中各桶的编址为 0 到 m-1, 当要加入一个表项 R2时, 用它的关键码 R2.key, 通过哈希函数 hash ( R2.key ) 的计算，得到它的存放桶号 j。 10.4.3 哈希冲突解决方法 1. 开放定址法 开放定址法是一类以发生冲突的哈希地址为自变量,通过某种哈希冲突函数得到一个新的空闲的哈希地址的方法。 (1)线性探查法。线性探查法是从发生冲突的地址(设为d)开始,依次探查d的下一个地址(当到达下标为m-1的哈希表表尾时,下一个探查的地址是表首地址0),直到找到一个空闲单元为止(当m≥n时一定能找到一个空闲单元)。线性探查法的数学递推描述公式为： d0=h(k) di=(di-1+1) mod m (1≤i≤m-1) (2)平方探查法。设发生冲突的地址为d,则平方探查法的探查序列为：d+12,d+22,…。平方探查法的数学描述公式为： d0=h(k) di=(d0+i2) mod m (1≤i≤m-1) 平方探查法是一种较好的处理冲突的方法,可以避免出现堆积问题。它的缺点是不能探查到哈希表上的所有单元,但至少能探查到一半单元。 例10.5 对上例构造的哈希表采用线性探查法解决冲突。 解：h(16)=3,h(74)=9,h(60)=8,h(43)=4, h(54)=2,h(90)=12,h(46)=7,h(31)=5, h(29)=3 冲突 d0=3,d1=(3+1) mod 13=4 仍冲突 d2=(4+1) mod 13=5 仍冲突 d3=(5+1) mod 13=6 h(88)=10 h(77)=12 冲突 d0=12,d1=(12+1) mod 13=0 建立的哈希表ha[0..12]如下表所示。 下标 0 1 2 3 4 5 6 7 8 9 10 11 12 k 77 54 16 43 31 29 46 60 74 88 90 探查次数 2 1 1 1 1 4 1 1 1 1 1 哈希表ha[0..12] h(16)=3, h(74)=9, h(60)=8, h(43)=4, h(54)=2, h(90)=12,h(46)=7, h(31)=5, h(29)=3, h(88)=10, h(77)=12 当发生冲突时, 探查下一个桶。当循环 m-1次后就会回到开始探查时的位置, 说明待查关键码不在表内, 而且表已满, 不能再插入新关键码。 用平均搜索长度ASL (Averagy Search Length) 衡量哈希方法的搜索性能。 搜索成功的平均搜索长度 ASLsucc 是指搜索到表中已有表项的平均探查次数。它是找到表中各个已有表项的探查次数的平均值。 搜索不成功的平均搜索长度 ASLunsucc 是指在表中搜索不到待查的表项，但找到插入位置的平均探查次数。它是表中所有可能哈希到的位置上要插入新元素时为找到空桶的探查次数的平均值。 下标 0 1 2 3 4 5 6 7 8 9 10 11 12 k 77 54 16 43 31 29 46 60 74 88 90 探查次数 2 1 1 1 1 4 1 1 1 1 1 哈希表ha[0..12] 搜索成功的平均搜索长度为： 搜索不成功的平均搜索长度为：(查找下一个空格) (3) 双哈希法 使用双哈希方法时, 需要两个哈希函数。 第一个哈希函数 Hash( ) 按表项的关键码 key 计算表项所在的桶号 H0 = Hash(key)。 一旦冲突，利用第二个哈希函数 ReHash( ) 计算该表项到达“下一个”桶的移位量。它的取值与 key 的值有关, 要求它的取值应是小于地址空间大小 TableSize, 且与 TableSize 互质的正整数。 若设表的长度为 m = TableSize，则在表中寻找“下一个”桶的公式为： j = H0 = Hash(key)， p = ReHash(key)； j = ( j + p ) % m； p是小于m且与m互质的整数 利用双哈希法, 按一定的距离, 跳跃式地寻找“下一个”桶, 减少了“堆积”的机会。 双哈希法的探查序列也可写成： Hi = (H0 + i * ReHash(key) ) % m， i =1, 2, …, m-1 最多经过 m-1次探查, 它会遍历表中所有位置, 回到H0 位置。 示例：给出一组表项关键码{ 22, 41, 53, 46, 30, 13, 01, 67 }。哈希函数为： Hash(x)＝(3x) % 11。 哈希表为 HT[0..10]，m = 11。因此，再哈希函数为 ReHash(x) = (7x) % 10 +1。 Hi = ( Hi-1 + (7x) % 10 +1 ) % 11, i = 1, 2, ? H0(22) = 0 H0(41) = 2 H0(53) = 5 H0(46) = 6 H0(30) = 2 冲突 H1 = (2+1) = 3 H0(13) = 6 冲突 H1 = (6+2) = 8 H0(01) = 3 冲突 H1 = (3+8) = 0 冲突 H2 = (0+8) = 8 冲突 H3 = (8+8) = 5 冲突 H4 = (5+8) = 2 冲突 H5 = (2+8) = 10 H0(67) = 3 冲突 H1 = (3+10) = 2 冲突 H2 = (2+10) = 1 22 67 41 30 53 46 13 01 (1) (3) (1) (2) (1) (1) (2) (6) 0 1 2 3 4 5 6 7 8 9 10 1 8 2 5 3 4 6 7 搜索成功的平均搜索长度 搜索不成功的平均搜索长度 每一哈希位置的移位量有10种：1, 2, ?, 10。先计算每一哈希位置各种移位量情形下找到下一个空位的比较次数, 求出平均值； 再计算各个位置的平均比较次数的总平均值。 22 67 41 30 53 46 13 01 (1) (3) (1) (2) (1) (1) (2) (6) 0 1 2 3 4 5 6 7 8 9 10 Rehash( )的取法很多。例如, 当m是质数时, 可定义 ReHash(key) = key % (m-2) +1 ReHash(key) = ?key / m? % (m-2)+1 当 m 是 2 的方幂时，ReHash(key) 可取从 0 到 m-1 中的任意一个奇数。 2. 拉链法 拉链法是把所有的同义词用单链表链接起来的方法。在这种方法中,哈希表每个单元中存放的不再是记录本身,而是相应同义词单链表的头指针。由于单链表中可插入任意多个结点,所以此时装填因子α根据同义词的多少既可以设定为大于1,也可以设定为小于或等于1,通常取α=1。 例10.6 对上例构造的哈希表采用拉链法解决冲突。 解：采用拉链法解决冲突建立的链表如下图所示。 h(16)=3, h(74)=9, h(60)=8, h(43)=4, h(54)=2, h(90)=12, h(46)=7, h(31)=5, h(29)=3, h(88)=10, h(77)=12 搜索成功的平均搜索长度为： 搜索不成功的平均搜索长度为： 哈希表分析 哈希表是一种直接计算记录存放地址的方法，它在关键码与存储位置之间直接建立了映象 当选择的哈希函数能够得到均匀的地址分布时, 在搜索过程中可以不做多次探查。 由于很难避免冲突, 增加了搜索时间。冲突的出现, 与哈希函数的选取 (地址分布是否均匀), 处理冲突的方法 (是否产生堆积) 有关。 在实际应用中使用关键码进行哈希时, 如在用作关键码的许多标识符具有相同的前缀或后缀，或者是相同字符的不同排列的场合，不同的哈希函数往往导致哈希表具有不同的搜索性能。 下图给出一些实验结果。 算法分析 设哈希表的装填因子为 其中 n 是表中已有的表项个数，m 是最多可容纳表项个数。 可用 ? 表明哈希表的装满程度。? 越大, 表中表项数越多, 表装得越满, 发生冲突可能性越大。 ? 越小，表中表项数越少，空间浪费越大。 通过对线性探查法的分析可知, 为搜索一个关键码所需进行的探查次数的期望值 P 大约是 (2-?)/(2-2?)。虽然平均探查次数较小, 但在最坏情况下的探查次数会相当大。 搜索关键码时所需对桶的平均访问次数 从图中可以看出，开哈希法优于闭哈希法；在哈希函数中，用除留余数法作哈希函数优于其它类型的哈希函数，最差的是折叠法。 当装填因子 ? 较高时, 选择的哈希函数不同, 哈希表的搜索性能差别很大。在一般情况下多选用除留余数法, 其中的除数在实用上应选择不含有20以下的质因数的质数。 对哈希表技术进行的实验评估表明, 它具有很好的平均性能, 优于一些传统的技术, 如平衡树。但哈希表在最坏情况下性能很不好。如果对一 个有 n 个关键码的哈希表执行一次搜索或插入操作，最坏情况下需要 O(n) 的时间。 Knuth对不同的冲突处理方法进行了概率分析。 用不同的方法溢出处理冲突时哈希表的平均搜索长度如图所示。 哈希表的装填因子 ? 表明了表中的装满程度。越大, 说明表越满, 再插入新元素时发生冲突的可能性就越大。 哈希表的搜索性能, 即平均搜索长度依赖于哈希表的装填因子, 不直接依赖于 n 或 m。 不论表的长度有多大, 我们总能选择一个合适的装填因子, 以把平均搜索长度限制在一定范围内。 例 求哈希表大小并设计哈希函数 设有一个含200个表项的哈希表，用二次探查法解决冲突，按关键码查询时找到一个新表项插入位置的平均探查次数不超过1.5，则哈希表项应能够至少容纳多少个表项。再设计哈希函数（设搜索不成功的平均搜索长度为 Un＝1 / (1 -α), 其中 α为装填因子） 解答：设表中表项个数 n = 200，搜索不成功的平均搜索长度 Un＝1 / (1 -α) ? 1.5 ? ? ? 1/3 ? n / m = 200 / m = ? ? 1/3 m ? 600 本章小结 本章基本学习要点如下： (1) 理解查找的基本概念,包括静态查找表和动态查找表、内查找和外查找之间的差异。 (2) 重点掌握线性表上各种查找算法,包括顺序查找、二分查找和分块查找的基本思路、算法实现和查找效率等。 (3) 掌握各种树表的查找算法,包括二叉排序树、AVL树和B-树的基本思路、算法实现和查找效率等。 然后，通过计算上述平衡二叉树中的结点个数，来建立高度 与结点个数之间的关系。设N(h)为Th的结点数，从图10.12中 可以看出有下列关系成立： N(1)=1，N(2)=2，N(h)=N(h-1)+N(h-2)+1 当h1时，此关系类似于定义Fibonacci数的关系： F(1)=1，F(2)=1，F(h)=F(h-1)+F(h-2) 通过检查两个序列的前几项就可发现两者之间的对应关系： N(h)=F(h+2)-1 由于Fibonacci数满足渐近公式：F(h)= 其中， 故由此可得近似公式：N(h)= 即：h≈log2(N(h)+1) 所以，含有n个结点的平衡二叉树的平均查找长度为O(log2n)。 9.3.3 B-树 B-树又称为多路平衡查找树,是一种组织和维护外存文件系统非常有效的数据结构。 B-树中所有结点的孩子结点最大值称为B-树的阶,通常用m表示,从查找效率考虑,要求m≥3。一棵m阶B-树或者是一棵空树,或者是满足下列要求的m叉树： (1) 树中每个结点至多有m个孩子结点(即至多有m-1个关键字)； (2) 除根结点外,其他结点至少有?m/2?个孩子结点(即至少有?m/2?-1=?(m-1)/2?个关键字)； (3) 若根结点不是叶子结点,则根结点至少有两个孩子结点； (4) 每个结点的结构为： n p0 k1 p1 k2 p2 … kn pn 其中,n为该结点中的关键字个数,除根结点外,其他所有结点的n大于等于?m/2?-1,且小于等于m-1；ki(1≤i≤n)为该结点的关键字且满足ki＜ki+1；pi(0≤i≤n)为该结点的孩子结点指针且满足pi(0≤i≤n-1)结点上的关键字大于等于ki且小于ki+1,pn结点上的关键字大于kn。 (5) 所有叶子结点都在同一层上,即B-树是所有结点的平衡因子均等于0的多路查找树。 一棵5阶B-树 在B-树的存储结构中,各结点的类型定义如下： #define MAXM 10 /*定义B-树的最大的阶数*/ typedef int KeyType; /*KeyType为关键字类型*/ typedef struct node /*B-树结点类型定义*/ { int keynum; /*结点当前拥有的关键字的个数*/ KeyType key[MAXM]; /*[1..keynum]存放关键字,[0]不用*/ struct node *parent; /*双亲结点指针*/ struct node *ptr[MAXM];/*孩子结点指针数组[0..keynum]*/ } BTNode; B-树的查找 在B-树中查找给定关键字的方法类似于二叉排序树上的查找,不同的是在每个记录上确定向下查找的路径不一定是二路(即二叉)的,而是n+1路的。因为记录内的关键字序列是有序的数量key[1..n],故既可以用顺序查找,也可以用折半查找。在一棵B-树上顺序查找关键字为k的方法为： 将k与根结点中的key[i]进行比较： (1) 若k=key[i],则查找成功； (2) 若k＜key[1],则沿着指针ptr[0]所指的子树继续查找； (3) 若key[i]＜k＜key[i+1],则沿着指针ptr[i]所指的子树继续查找； (4) 若k＞key[n],则沿着指针ptr[n]所指的子树继续查找。 2. B-树的插入 将关键字k插入到B-树的过程分两步完成： (1) 利用前述的B-树的查找算法找出该关键字的插入结点(注意B-树的插入结点一定是叶子结点)。 (2) 判断该结点是否还有空位置,即判断该结点是否满足n＜m-1,若该结点满足n＜m-1,说明该结点还有空位置,直接把关键字k插入到该结点的合适位置上(即满足插入后结点上的关键字仍保持有序)； 若该结点有n=m-1,说明该结点已没有空位置,需要把结点分裂成两个。 分裂的做法是,取一新结点,把原结点上的关键字和k按升序排序后,从中间位置(即?m/2?=?(m+1)/2?之处)把关键字(不包括中间位置的关键字)分成两部分,左部分所含关键字放在旧结点中,右部分所含关键字放在新结点中,中间位置的关键字连同新结点的存储位置插入到父亲结点中。如果父结点的关键字个数也超过Max,则要再分裂,再往上插,直至这个过程传到根结点为止。 例如 关键字序列为： {1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15}。 创建一棵5阶B-树。 建立B-的过程如下图所示。 3. B-树的删除 B-树的删除过程与插入过程类似,只是稍为复杂一些。要使删除后的结点中的关键字个数≥?m/2?-1,将涉及到结点的“合并”问题。在B-树上删除关键字k的过程分两步完成： (1) 利用前述的B-树的查找算法找出该关键字所在的结点。 (2) 在结点上删除关键字k分两种情况：一种是在叶子结点上删除关键字；另一种是在非叶子结点上删除关键字。 (3) 在非叶子结点上删除关键字的过程：假设要删除关键字key[i](1≤i≤n),在删去该关键字后,以该结点ptr[i]所指子树中的最小关键字key[min]来代替被删关键字key[i]所在的位置(注意ptr[i]所指子树中的最小关键字key[min]一定是在叶子结点上),然后再以指针ptr[i]所指结点为根结点查找并删除key[min](即再以ptr[i]所指结点为B-树的根结点,以key[min]为要删除的关键字,然后再次调用B-树上的删除算法),这样也就把在非叶子结点上删除关键字k的问题转化成了在叶子结点上删除关键字key[min]的问题。 (4) 在B-树的叶子结点上删除关键字共有以下三种情况： ① 假如被删结点的关键字个数大于Min,说明删去该关键字后该结点仍满足B-树的定义,则可直接删去该关键字。 ② 假如被删结点的关键字个数等于Min,说明删去关键字后该结点将不满足B-树的定义,此时若该结点的左(或右)兄弟结点中关键字个数大于Min,则把该结点的左(或右)兄弟结点中最大(或最小)的关键字上移到双亲结点中,同时把双亲结点中大于(或小于)上移关键字的关键字下移到要删除关键字的结点中,这样删去关键字k后该结点以及它的左(或右)兄弟结点都仍旧满足B-树的定义。 ③ 假如被删结点的关键字个数等于Min,并且该结点的左和右兄弟结点(如果存在的话)中关键字个数均等于Min,这时,需把要删除关键字的结点与其左(或右)兄弟结点以及双亲结点中分割二者的关键字合并成一个结点。如果因此使双亲结点中关键字个数小于Min,则对此双亲结点做同样处理,以致于可能直到对根结点做这样的处理而使整个树减少一层。 例如,对于上例生成的B-树,给出删除8,16,15,4等四个关键字的过程。 9.3.4 B+树 在索引文件组织中,经常使用B-树的一些变形,其中B+树是一种应用广泛的变形。一棵m阶B+树满足下列条件： (1) 每个分支结点至多有m棵子树。 (2) 除根结点外,其他每个分支结点至少有?(m+1)/2?棵子树。 (3) 根结点至少有两棵子树,至多有m棵子树。 (4) 有n棵子树的结点有n个关键字。 (5) 所有叶子结点包含全部(数据文件中记录) 关键字及指向相应记录的指针(或存放数据文件分块后每块的最大关键字及指向该块的指针),而且叶子结点按关键字大小顺序链接(可以把每个叶子结点看成是一个基本索引块,它的指针不再指向另一级索引块,而是直接指向数据文件中的记录)。 (6) 所有分支结点(可看成是索引的索引)中仅包含它的各个子结点(即下级索引的索引块)中最大关键字及指向子结点的指针。 一棵4阶的B+树 m阶的B+树和m阶的B-树,定义中的前三点是相同的,主要的差异是： (1) 在B+树中,具有n个关键字的结点含有n棵子树,即每个关键字对应一棵子树,而在B-树中,具有n个关键字的结点含有(n+1)棵子树。 (2) 在B+树中,每个结点(除根结点外)中的关键字个数n的取值范围是?m/2?≤n ≤m,根结点n的取值范围是1≤n≤m；而在B-树中,它们的取值范围分别是?m/2?-1≤n ≤m-1和1≤n≤m-1。 (3) B+树中的所有叶子结点包含了全部关键字,即其他非叶子结点中的关键字包含在叶子结点中,而在B-树中,叶子结点包含的关键字与其他结点包含的关键字是不重复的。 (4) B+树中所有非叶子结点仅起到索引的作用,即结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针,不含有该关键字对应记录的存储地址。而在B-树中,每个关键字对应一个记录的存储地址。 (5) 通常在B+树上有两个头指针,一个指向根结点,另一个指向关键字最小的叶子结点,所有叶子结点链接成一个不定长的线 哈希表的基本概念 哈希表(Hash Table)又称散列表,是除顺序表存储结构、链接表存储结构和索引表存储结构之外的又一种存储线性表的存储结构。 哈希表 (Hashing) 在现实中经常遇到按给定的值进行查询的事例。为此, 必须考虑在记录的存放位置和用以标识它的数据项(称为关键码)之间的对应关系，选择适当的数据结构, 很方便地根据记录的关键码检索到对应记录的信息。 表项的存放位置及其关键码之间的对应关系可以用一个二元组表示： ( 关键码key，表项位置指针addr ) 这个二元组构成搜索某一指定表项的索引项。 考虑到搜索效率, 可以考虑哈希表结构。 静态哈希方法 哈希方法在表项存储位置与其关键码之间建立一个确定的对应函数关系Hash( )，使每个关键码与结构中一个唯一存储位置相对应： Address ＝ Hash ( Rec.key ) 在搜索时, 先对表项的关键码进行函数计算,把函数值当做表项的存储位置, 在结构中按此位置取表项比较。若关键码相等, 则搜索成功。在存放表项时, 依相同函数计算存储位置, 并按此位置存放。此方法称为哈希方法。 在哈希方法中使用的转换函数叫做哈希函数。按此方法构造出来的表或结构就叫做哈希表。 使用哈希方法进行搜索不必进行多次关键码的比较, 搜索速度比较快, 可以直接到达或逼近具有此关键码的表项的实际存放地址。 哈希函数是一个压缩映象函数。关键码集合比哈希表地址集合大得多。因此有可能经过哈希函数的计算，把不同的关键码映射到同一个哈希地址上，这就产生了冲突。 示例：有一组表项，其关键码分别是 12361, 07251, 03309, 30976 采用的哈希函数是 hash(x) = x % 73 + 13420 其中，“%”是除法取余操作。 则有：hash(12361) = hash(07250) = hash(03309) = hash(30976) = 13444。就是说, 对不同的关键码, 通过哈希函数的计算, 得到了同一哈希地址。我们称这些产生冲突的哈希地址相同的不同关键码为同义词。 由于关键码集合比地址集合大得多, 冲突很难避免。所以对于哈希方法, 需要讨论以下两个问题： 构造哈希函数时的几点要求： 哈希函数应是简单的，能在较短的时间内 计算出结果。 哈希函数的定义域必须包括需要存储的全 部关键码, 如果哈希表允许有 m 个地址时, 其值域必须在 0 到 m-1 之间。 哈希函数 对于给定的一个关键码集合, 选择一个计算 简单且地址分布比较均匀的哈希函数, 避免或尽量减少冲突； 拟订解决冲突的方案。 直接定址法 此类函数取关键码的某个线性函数值作为哈希地址： Hash ( key ) ＝ a * key + b { a, b为常数 } 这类哈希函数是一对一的映射，一般不会产生冲突。但是，它要求哈希地址空间的大小与关键码集合的大小相同。 哈希函数计算出来的地址应能均匀分布在整 个地址空间中 : 若 key 是从关键码集合中随 机抽取的一个关键码, 哈希函数应能以同等 概率取0 到 m-1 中的每一个值。 示例：有一组关键码如下：{ 942148, 941269, 940527, 941630, 941805, 941558, 942047, 940001 }。哈希函数为 Hash (key) = key - 940000 Hash (942148) = 2148 Hash (941269) = 1269 Hash (940527) = 527 Hash (941630) = 1630 Hash (941805) = 1805 Hash (941558) = 1558 Hash (942047) = 2047 Hash (940001) = 1 可以按计算出的地址存放记录。 数字分析法 设有 n 个 d 位数, 每一位可能有 r 种不同的符号。这 r 种不同符号在各位上出现的频率不一定相同。 可根据哈希表的大小, 选取其中各种符号分布均匀的若干位作为哈希地址。 计算各位数字中符号分布均匀度 ? k 的公式： 其中， 表示第 i 个符号在第 k 位上出现的次数，n/r 表示各种符号在 n 个数中均匀出现的期望值。计算出的 ? k 值越小，表明在该位 (第 k 位) 各种符号分布得越均匀。 9 4 2 1 4 8 ①位， ? 1 = 57.60 9 4 1 2 6 9 ②位， ? 2 = 57.60 9 4 0 5 2 7 ③位， ? 3 = 17.60 9 4 1 6 3 0 ④位， ? 4 = 5.60 9 4 1 8 0 5 ⑤位， ? 5 = 5.60 9 4 1 5 5 8 ⑥位， ? 6 = 5.60 9 4 2 0 4 7 9 4 0 0 0 1 ① ② ③ ④ ⑤ ⑥ 若哈希表地址范围有 3 位数字, 取各关键码的 ④⑤⑥ 位做为记录的哈希地址。 数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况，它完全依赖于关键码集合。如果换一个关键码集合，选择哪几位要重新决定。 除留余数法 设哈希表中允许地址数为 m, 取一个不大于 m, 但最接近于或等于 m 的质数 p 作为除数, 利用以下函数把关键码转换成哈希地址： hash ( key ) = key % p p ? m 其中, “%”是整数除法取余的运算，要求这时的质数 p 不是接近2的幂。 1. 二叉排序树上的查找 因为二叉排序树可看做是一个有序表,所以在二叉排序树上进行查找,和二分查找类似,也是一个逐步缩小查找范围的过程。递归查找算法SearchBST()如下(在二叉排序树bt上查找关键字为k的记录,成功时返回该结点指针,否则返回NULL)： BSTNode *SearchBST(BSTNode *bt,KeyType k) { if (bt==NULL bt-key==k) /*递归终结条件*/ return bt; if (kbt-key) return SearchBST(bt-lchild,k); /*在左子树中递归查找*/ else return SearchBST(bt-rchild,k); /*在右子树中递归查找*/ } 2. 二叉排序树的插入和生成 在二叉排序树中插入一个新记录,要保证插入后仍满足BST性质。其插入过程是： 若二叉排序树T为空,则创建一个key域为k的结点,将它作为根结点； 否则将k和根结点的关键字比较,若二者相等,则说明树中已有此关键字k,无须插入,直接返回0； 若kT-key,则将k插入根结点的左子树中, 否则将它插入右子树中。 35 15 45 50 40 25 10 20 30 28 插入新结点28 二叉排序树的插入 每次结点的插入，都要从根结点出发搜索插入位置，然后把新结点作为叶结点插入。 int InsertBST(BSTNode *p,KeyType k) /*在以*p为根结点的BST中插入一个关键字为k的结点。插入成功返回1,否则返回0*/ { if (p==NULL) /*原树为空, 新插入的记录为根结点*/ { p=(BSTNode *)malloc(sizeof(BSTNode)); p-key=k;p-lchild=p-rchild=NULL; return 1; } else if (k==p-key) /*存在相同关键字的结点,返回0*/ return 0; else if (kp-key) return InsertBST(p-lchild,k);/*插入到左子树中*/ else return InsertBST(p-rchild,k); /*插入到右子树中*/ } 二叉排序树的生成,是从一个空树开始,每插入一个关键字,就调用一次插入算法将它插入到当前已生成的二叉排序树中。从关键字数组A[0..n-1]生成二叉排序树的算法CreatBST()如下： BSTNode *CreatBST(KeyType A[],int n) /*返回树根指针*/ { BSTNode *bt=NULL; /*初始时bt为空树*/ int i=0; while (in) { InsertBST(bt,A[i]); /*将A[i]插入二叉排序树T中*/ i++; } return bt; /*返回建立的二叉排序树的根指针*/ } 输入数据 { 53, 78, 65, 17, 87, 09, 81, 15 } 53 53 78 53 78 65 53 78 65 17 53 78 65 87 17 53 78 65 09 17 87 53 78 65 81 17 87 09 53 78 65 15 17 87 09 81 例9.2 已知一组关键字为{25,18,46,2,53,39,32,4,74,67,60,11}。按表中的元素顺序依次插入到一棵初始为空的二叉排序树中,画出该二叉排序树,并求在等概率的情况下查找成功的平均查找长度。 解：生成的二叉排序树如右图所示。 3. 二叉排序树的删除 在二叉排序树中删除一个结点时，必须将因删除结点而断开的二叉链表重新链接起来，同时确保二叉搜索树的性质不会失去。 为保证在删除后树的搜索性能不至于降低，还需要防止重新链接后树的高度增加。 删除叶结点，只需将其双亲结点指向它的指针清零，再释放它即可。 被删结点右子树为空，可以拿它的左子女结点顶替它的位置，再释放它。 被删结点左子树为空，可以拿它的右子女结点顶替它的位置，再释放它。 被删结点左、右子树都不为空，可以在它的右子树中寻找中序下的第一个结点(即关键码最小),用它的值填补到被删结点中，再来处理这个结点的删除问题。 53 78 65 17 87 09 23 45 删除45 右子树空, 用左子女顶替 53 78 65 17 87 09 23 88 53 78 88 17 94 09 23 删除78 左子树空, 用右子女顶替 53 94 88 17 09 23 53 78 81 17 94 09 45 删除78 在右子树上找中序下第一个结点填补(即右子树的最小关键码结点) 23 65 53 81 88 17 94 09 45 23 65 删除二叉排序树结点的算法DeleteBST()如下(指针变量p指向待删除的结点,指针变量q指向待删除结点*p的双亲结点)： void Delete1(BSTNode *p,BSTNode *r) /*当被删*p结点有左右子树时的删除过程*/ { BSTNode *q; if (r-rchild!=NULL) Delete1(p,r-rchild); /*递归找最右下结点*/ else /*找到了最右下结点*r*/ { p-key=r-key; /*将*r的关键字值赋给*p*/ q=r; r=r-lchild; /*将左子树的根结点放在被删结点的位置上*/ free(q); /*释放原*r的空间*/ } } void Delete(BSTNode *p) /*从二叉排序树中删除*p结点*/ { BSTNode *q; if (p-rchild==NULL) /**p结点没有右子树的情况*/ { q=p; p=p-lchild; /*其右子树的根结点放在被删结点的位置上*/ free(q); } else if (p-lchild==NULL) /**p结点没有左子树*/ { q=p; p=p-rchild; /*将*p结点的右子树作为双亲结点的相应子树/ free(q); } else Delete1(p,p-lchild); /**p结点既有左子树又有右子树的情况*/ } int DeleteBST(BSTNode *bt,KeyType k) /*在bt中删除关键字为k的结点*/ { if (bt==NULL) return 0; /*空树删除失败*/ else { if (kbt-key) return DeleteBST(bt-lchild,k); /*递归在左子树中删除为k的结点*/ else if (kbt-key) return DeleteBST(bt-rchild,k); /*递归在右子树中删除为k的结点*/ else { Delete(bt); /*调用Delete(bt)函数删除*bt结点*/ return 1; } } } 9.3.2 平衡二叉树(AVL) 若一棵二叉树中每个结点的左、右子树的高度至多相差1,则称此二叉树为平衡二叉树。在算法中,通过平衡因子(balancd factor,用bf表示)来具体实现上述平衡二叉树的定义。平衡因子的定义是：平衡二叉树中每个结点有一个平衡因子域,每个结点的平衡因子是该结点左子树的高度减去右子树的高度。从平衡因子的角度可以说,若一棵二叉树中所有结点的平衡因子的绝对值小于或等于1,即平衡因子取值为1、0或-1,则该二叉树称为平衡二叉树。 平衡二叉树和不平衡二叉树 定义AVL树的结点的类型如下： typedef struct node /*记录类型*/ { KeyType key; /*关键字项*/ int bf; /*增加的平衡因子*/ InfoType data; /*其他数据域*/ struct node *lchild,*rchild; /*左右孩子指针*/ } BSTNode; 平衡化旋转 如果在一棵平衡的二叉搜索树中插入一个新结点，造成了不平衡。此时必须调整树的结构，使之平衡化。 平衡化旋转有两类： 单旋转 (左旋和右旋) 双旋转 (左平衡和右平衡) 每插入一个新结点时, AVL 树中相关结点的平衡状态会发生改变。因此, 在插入一 个新结点后，需要从插入位置沿通向根的路径回溯，检查各结点的平衡因子。 如果在某一结点发现高度不平衡，停止回溯。从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点。 如果这三个结点处于一条直线上，则采用单旋转进行平衡化。单旋转可按其方向分为左单旋转和右单旋转, 其中一个是另一 个的镜像，其方向与不平衡的形状相关。 如果这三个结点处于一条折线上，则采用双旋转进行平衡化。双旋转分为先左后右和先右后左两类。 A B C A B C 右单旋转 左单旋转 B A C 左右双旋转 B A C 右左双旋转 A B C C B A A C B B C A AVL树的插入 在向一棵本来是高度平衡的AVL树中插入一个新结点时，如果树中某个结点的平衡因子的绝对值 balance 1，则出现了不平衡，需要做平衡化处理。 算法从一棵空树开始，通过输入一系列对象关键码，逐步建立AVL树。在插入新结点时使用平衡旋转方法进行平衡化处理。 16 16 例，输入关键码序列为 { 16, 3, 7, 11, 9, 26, 18, 14, 15 }，插入和调整过程如下。 0 3 16 3 -1 0 7 0 1 -2 左右双旋 7 3 16 0 0 0 7 3 11 0 -1 1 7 3 16 16 11 9 0 -1 -2 右单旋 3 7 16 9 0 0 0 1 3 7 11 26 9 16 11 0 1 1 2 2 18 18 0 3 16 3 -1 0 16 0 2 右左双旋 7 3 9 0 0 0 18 26 11 -1 7 3 26 16 11 9 -1 左单旋 9 7 16 14 0 0 1 7 11 26 26 9 1 1 11 15 18 2 3 18 16 -2 左右双旋 7 3 0 0 0 11 7 14 9 -1 16 15 0 1 11 26 26 14 1 -2 9 从空树开始的建树过程 AVL树的删除 (1) 如果被删结点x最多只有一个子女，那么问题比较简单: 将结点x从树中删去。 因为结点x最多有一个子女，可以简单地把x的双亲结点中原来指向x的指针改指到这个子女结点； 如果结点x没有子女，x双亲结点的相应指针置为NULL。 将原来以结点x为根的子树的高度减1。 (2) 如果被删结点x有两个子女: 搜索 x 在中序次序下的直接前驱 y (同样可以找直接后继)。 把 结点y 的内容传送给结点x，现在问题转移到删除结点 y。把结点y当作被删结点x。 因为结点y最多有一个子女，我们可以简单地用(1)给出的方法进行删除。 A B C D E F G H I J K L M N O P Q R S T 0 0 0 0 0 0 0 -1 -1 -1 -1 -1 -1 -1 1 1 1 1 1 树的初始状态 举例 A B C D E F G H I J K L M N O P Q R S T 0 0 0 0 0 0 0 -1 -1 -1 -1 -1 -1 -1 1 1 1 1 1 删除结点P 寻找结点P在中序下的直接前驱O, 用O顶替P, 删除O。 用O取代P A B C D E F G H I J K L M N O Q R S T 0 0 0 0 0 0 -1 -1 -1 -1 -1 -1 -1 1 0 1 2 1 删除结点P 左单旋转 O与R的平衡因子同号, 以R为旋转轴做左单旋转, M的子树高度减 1。 A B C D E F G H I J K L M N O Q R S T 0 0 0 0 0 0 -1 -2 -1 -1 -1 -1 -1 1 0 0 1 删除结点P M的子树高度减 1, M发生不平衡。M与E的平衡因子反号, 做左右双旋转。 0 向上继续调整 A B C D E F G H I J N K L M O R 0 0 0 0 0 -1 0 0 -1 -1 -1 -1 0 1 0 0 删除结点P 0 0 T Q 0 S 在平衡二叉树上进行查找的过程和在二叉排序树上进行查找的过程完全相同，因此，在平衡二叉树上进行查找关键字的比较次数不会超过平衡二叉树的深度。 在最坏的情况下，普通二叉排序树的查找长度为O(n)。那么，平衡二叉树的情况又是怎样的呢？下面分析平衡二叉树的高度h和结点个数n之间的关系。 首先，构造一系列的平衡二叉树T1，T2，T3，…，其中，Th（h=1，2，3，…）是高度为h且结点数尽可能少的平衡二叉树，如图10.12中所示的T1，T2，T3和T4。为了构造Th，先分别构造Th-1和Th-2，使Th以Th-1和Th-2作为其根结点的左、右子树。对于每一个Th，只要从中删去一个结点，就会失去平衡或高度不再是h（显然，这样构造的平衡二叉树在结点个数相同的平衡二叉树中具有最大高度）。 图10.12 结点个数n最少的平衡二叉树 练习 教材中p217习题2、3和5。 上机实验题 教材中p217题1、2和3。 (4)掌握图的其他运算,包括最小生成树、最短路径、拓扑排序等算法。 (5)灵活运用图这种数据结构解决一些综合应用问题。 第9章 查找 9.1 查找的基本概念 本章小结 9.2 线 查找的基本概念 被查找的对象是由一组记录组成的表或文件,而每个记录则由若干个数据项组成,并假设每个记录都有一个能惟一标识该记录的关键字。 在这种条件下,查找的定义是：给定一个值k,在含有n个记录的表中找出关键字等于k的记录。若找到,则查找成功,返回该记录的信息或该记录在表中的位置；否则查找失败,返回相关的指示信息。 采用何种查找方法? (1) 使用哪种数据结构来表示“表”,即表中记录是按何种方式组织的。 (2) 表中关键字的次序。是对无序集合查找还是对有序集合查找? 若在查找的同时对表做修改运算(如插入和删除),则相应的表称之为动态查找表,否则称之为静态查找表。 由于查找运算的主要运算是关键字的比较,所以通常把查找过程中对关键字需要执行的平均比较次数(也称为平均查找长度)作为衡量一个查找算法效率优劣的标准。平均查找长度ASL(Average Search Length)定义为： 其中,n是查找表中记录的个数。pi是查找第i个记录的概率,一般地,均认为每个记录的查找概率相等,即pi=1/n(1≤i≤n),ci是找到第i个记录所需进行的比较次数。 9.2 线性表的查找 在表的组织方式中,线性表是最简单的一种。三种在线性表上进行查找的方法： (1) 顺序查找 (2) 二分查找 (3) 分块查找。 因为不考虑在查找的同时对表做修改,故上述三种查找操作都是在静态查找表上实现的。 查找与数据的存储结构有关,线性表有顺序和链式两种存储结构。本节只介绍以顺序表作为存储结构时实现的顺序查找算法。定义被查找的顺序表类型定义如下： #define MAXL 表中最多记录个数 typedef struct { KeyType key; /*KeyType为关键字的数据类型*/ InfoType data; /*其他数据*/ } NodeType; typedef NodeType SeqList[MAXL]; /*顺序表类型*/ 9.2.1 顺序查找 顺序查找是一种最简单的查找方法。 它的基本思路是：从表的一端开始,顺序扫描线性表,依次将扫描到的关键字和给定值k相比较,若当前扫描到的关键字与k相等,则查找成功；若扫描结束后,仍未找到关键字等于k的记录,则查找失败。 例如,在关键字序列为{3,9,1,5,8,10,6,7,2,4}的线的元素。 顺序查找过程如下： 开始: 3 9 1 5 8 10 6 7 2 4 第1次比较: 3 9 1 5 8 10 6 7 2 4 i=0 第2次比较: 3 9 1 5 8 10 6 7 2 4 i=1 第3次比较: 3 9 1 5 8 10 6 7 2 4 i=2 第4次比较: 3 9 1 5 8 10 6 7 2 4 i=3 第5次比较: 3 9 1 5 8 10 6 7 2 4 i=4 第6次比较: 3 9 1 5 8 10 6 7 2 4 i=5 第7次比较: 3 9 1 5 8 10 6 7 2 4 i=6 查找成功,返回序号6 顺序查找的算法如下(在顺序表R[0..n-1]中查找关键字为k的记录,成功时返回找到的记录位置,失败时返回-1)： int SeqSearch(SeqList R,int n,KeyType k) { int i=0; while (in R[i].key!=k) i++; /*从表头往后找*/ if (i=n) return -1; else return i; } 从顺序查找过程可以看到(不考虑越界比较in),ci取决于所查记录在表中的位置。如查找表中第1个记录R[0]时,仅需比较一次；而查找表中最后一个记录R[n-1]时,需比较n次,即ci=i。因此,成功时的顺序查找的平均查找长度为： 查找成功时的平均比较次数约为表长的一半 。 9.2.2 二分查找 二分查找也称为折半查找要求线性表中的结点必须己按关键字值的递增或递减顺序排列。它首先用要查找的关键字k与中间位置的结点的关键字相比较,这个中间结点把线性表分成了两个子表,若比较结果相等则查找完成;若不相等,再根据k与该中间结点关键字的比较大小确定下一步查找哪个子表,这样递归进行下去,直到找到满足条件的结点或者该线性表中没有这样的结点。 例如,在关键字有序序列{2,4,7,9,10,14,18,26,32,40}中采用二分查找法查找关键字为7的元素。 二分查找过程如下： 开始: 2 4 7 9 10 14 18 26 32 40 low=0 high=9 mid=(0+9)/2=4 第1次比较: 2 4 7 9 10 14 18 26 32 40 low=0 high=3 mid=(0+3)/2=1 第2次比较: 2 4 7 9 10 14 18 26 32 40 low=2 high=3 mid=(2+3)/2=2 第3次比较: 2 4 7 9 10 14 18 26 32 40 R[2].key=7 查找成功,返回序号2 查找元素7 mid=(low+high)/2 其算法如下(在有序表R[0..n-1]中进行二分查找,成功时返回记录的位置,失败时返回-1)： int BinSearch(SeqList R,int n,KeyType k) { int low=0,high=n-1,mid; while (low=high) { mid=(low+high)/2; if (R[mid].key==k) /*查找成功返回*/ return mid; if (R[mid].keyk) /*继续在R[low..mid-1]中查找*/ high=mid-1; else low=mid+1; /*继续在R[mid+1..high]中查找*/ } return -1; } 二分查找过程可用二叉树来描述,我们把当前查找区间的中间位置上的记录作为根,左子表和右子表中的记录分别作为根的左子树和右子树,由此得到的二叉树,称为描述二分查找的判定树或比较树。 下标：0 1 2 3 4 5 6 7 8 9 数值：2 4 7 9 10 14 18 26 32 40 mid=(low+high)/2 R[mid] 数值作为根结点 二分查找的判定树 利用二叉判定树求二分查找的平均查找长度。 该树的结点总数为：n=2h-1, h=log2(n+1) 查找树中第i层上的结点需要比较i次，第i层上的结点个数最多为2i-1，在等概率情况下，二分查找成功时的平均查找长度为： ASL= 例10.1对于给定11个数据元素的有序表{2,3,10,15,20,25,28,29,30,35,40},采用二分查找,试问： (1)若查找给定值为20的元素,将依次与表中哪些元素比较？ (2)若查找给定值为26的元素,将依次与哪些元素比较？ (3)假设查找表中每个元素的概率相同,求查找成功时的平均查找长度和查找不成功时的平均查找长度。 二分查找判定树 (2)若查找给定值为26的元素,依次与25,30,28元素比较,共比较3次。 (3)在查找成功时,会找到图中某个圆形结点,则成功时的平均查找长度： (1)若查找给定值为20的元素,依次与表中25,10,15,20元素比较,共比较4次。 在查找不成功时,会找到图中某个方形结点,则不成功时的平均查找长度： 9.2.3 分块查找 分块查找又称索引顺序查找,它是一种性能介于顺序查找和二分查找之间的查找方法。 它要求按如下的索引方式来存储线块中记录个数为s=?n/b?,最后一块即第b块的记录数小于等于s；每一块中的关键字不一定有序,但前一块中的最大关键字必须小于后一块中的最小关键字,即要求表是“分块有序”的；抽取各块中的最大关键字及其起始位置构成一个索引表IDX[0..b-1],即IDX[i](0≤i≤b-1)中存放着第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的,所以索引表是一个递增有序表。 索引表的数据类型定义如下： #define MAXI 索引表的最大长度 typedef struct { KeyType key; /*KeyType为关键字的类型*/ int link; /*指向对应块的起始下标*/ } IdxType; typedef IdxType IDX[MAXI]; /*索引表类型*/ 例如,设有一个线个记录,其关键字序列为{8,14,6,9,10,22,34,18,19,31,40,38,54,66, 46,71,78,68,80,85, 100, 94,88,96,87}。假设将25个记录分为5块,每块中有5个记录,该线性表的索引存储结构如下图所示。 采用二分查找索引表的分块查找算法如下(索引表I的长度为m)： int IdxSearch(IDX I,int m,SeqList R,int n,KeyType k) { int low=0,high=m-1,mid,i; int b=n/m; /*b为每块的记录个数*/ while (low=high) /*在索引中二分查找*/ { mid=(low+high)/2; if (I[mid].key=k) high=mid-1; else low=mid+1; } if (lowm) /*在块中顺序查找*/ { i=I[low].link; while (i=I[low].link+b-1 R[i].key!=k) i++; if (i=I[low].link+b-1) return i; else return -1; } return -1; } 若以二分查找来确定块,则分块查找成功时的平均查找长度为： 若以顺序查找确定块,则分块查找成功时的平均查找长度为： 9.3 树表的查找 当表的插入或删除操作频繁时,为维护表的有序性,需要移动表中很多记录。这种由移动记录引起的额外时间开销,就会抵消二分查找的优点。也就是说,二分查找只适用于静态查找表。若要对动态查找表进行高效率的查找,可采用下面介绍的几种特殊的二叉树或树作为表的组织形式,在这里将它们统称为树表。下面将分别讨论在这些树表上进行查找和修改操作的方法。 9.3.1 二叉排序树 二叉排序树(简称BST)又称二叉查找(搜索)树,其定义为：二叉排序树或者是空树,或者是满足如下性质的二叉树： (1) 左子树上所有记录的值 均小于根记录的值； (2) 右子树上所有记录的值 均大于根记录的值； (3) 左、右子树本身又各是 一棵二叉排序树。 35 15 45 50 40 25 10 20 30 二叉排序树的查找算法 在二叉排序树上进行搜索，是一个从根结点开始，沿某一个分支逐层向下进行比较判等的过程。它可以是一个递归的过程。 假设想要在二叉排序树中搜索关键码为 x 的元素，搜索过程从根结点开始。 如果根指针为NULL，则搜索不成功；否则用给定值 x 与根结点的关键码进行比较： 若给定值等于根结点关键码，则搜索成功，返回搜索成功信息并报告搜索到结点地址。 若给定值小于根结点的关键码，则继续递归搜索根结点的左子树； 否则。递归搜索根结点的右子树。 搜索45 搜索成功 搜索28 搜索失败 35 15 45 50 40 25 10 20 30 设树的高度为h，最多比较次数不超过h。 如果对一棵二叉搜索树进行中序遍历，可以按从小到大的顺序，将各结点关键码排列起来，所以也称二叉搜索树为二叉排序树。 在讨论二叉排序树上的运算之前,定义其结点的类型如下： typedef struct node /*记录类型*/ { KeyType key; /*关键字项*/ InfoType data; /*其他数据域*/ struct node *lchild,*rchild; /*左右孩子指针*/ } BSTNode; 考虑顶点v0,A0[i][j]表示由vi到vj,经由顶点v0的最短路径。只有从v2到v1经过v0的路径和从v2到v3经过v0的路径,不影响v2到v1和v2到v3的路径长度,因此,有： 考虑顶点v1,A1[i][j]表示由vi到vj,经由顶点v1的最短路径。存在路径v0-v1-v2,路径长度为9,将A[0][2]改为9,path[0][2]改为1,因此,有： 考虑顶点v2,A2[i][j]表示由vi到vj,经由顶点v2的最短路径。存在路径v3-v2-v0,长度为4,将A[3][0]改为4；存在路径v3-v2-v1,长度为4,将A[3][1]改为4。存在路径v1-v2-v0,长度为7,将A[1][0]改为7。将path[3][0]、path[3][1]和path[1][0]均改为2。因此,有： 考虑顶点v3,A3[i][j]表示由vi到vj,经由顶点v3的最短路径。存在路径v0-v3-v2,长度为8比原长度短,将A[0][2]改为8；存在路径v1-v3-v2-v0,长度为6(A[1][3]+A[3][0]=2+4=6)比原长度短,将A[1][0]改为6；存在路径v1-v3-v2,长度为3,比原长度短,将A[1][2]改为3；将path[0][2]、path[1][0]后path[1][2]均改为3。因此,有： 从0到0路径为：0,0 路径长度为：0 从0到1路径为：0,1 路径长度为：5 从0到2路径为：0,3,2 路径长度为：8 从0到3路径为：0,3 路径长度为：7 从1到0路径为：1,3,2,0 路径长度为：6 从1到1路径为：1,1 路径长度为：0 从1到2路径为：1,3,2 路径长度为：3 从1到3路径为：1,3 路径长度为：2 A= Path= 从2到0路径为：2,0 路径长度为：3 从2到1路径为：2,1 路径长度为：3 从2到2路径为：2,2 路径长度为：0 从2到3路径为：2,3 路径长度为：2 从3到0路径为：3,2,0 路径长度为：4 从3到1路径为：3,2,1 路径长度为：4 从3到2路径为：3,2 路径长度为：1 从3到3路径为：3,3 路径长度为：0 弗洛伊德算法如下： void Floyd(int cost[][MAXV],int n) { int A[MAXV][MAXV],path[MAXV][MAXV];int i,j,k; for (i=0;in;i++) for (j=0;jn;j++) { A[i][j]=cost[i][j]; path[i][j]=-1; } for (k=0;kn;k++) for (i=0;in;i++) for (j=0;jn;j++) if (A[i][j](A[i][k]+A[k][j])) { A[i][j]=A[i][k]+A[k][j]; path[i][j]=k; } Dispath(A,path,n); /*输出最短路径*/ } 8.6 拓扑排序 设G=(V,E)是一个具有n个顶点的有向图,V中顶点序列v1,v2,…,vn称为一个拓扑序列,当且仅当该顶点序列满足下列条件： 若vi,vj是图中的边(即从顶点vi到vj有一条路径),则在序列中顶点vi必须排在顶点vj之前。 在一个有向图中找一个拓扑序列的过程称为拓扑排序。 课程代号 课程名称 先修课程 C1 高等数学 无 C2 程序设计 无 C3 离散数学 C1 C4 数据结构 C2,C3 C5 编译原理 C2,C4 C6 操作系统 C4,C7 C7 计算机组成原理 C2 例如,计算机专业的学生必须完成一系列规定的基础课和专业课才能毕业,假设这些课程的名称与相应代号有如下关系： 课程之间的先后关系可用有向图表示 ： 对这个有向图进行拓扑排序可得到一个拓扑序列：C1-C3-C2-C4-C7-C6-C5。也可得到另一个拓扑序列：C2-C7-C1-C3-C4-C5-C6,还可以得到其他的拓扑序列。学生按照任何一个拓扑序列都可以顺序地进行课程学习。 拓扑排序方法如下： (1) 从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它。 (2) 从网中删去该顶点,并且删去从该顶点发出的全部有向边。 (3) 重复上述两步,直到剩余的网中不再存在没有前驱的顶点为止。 为了实现拓扑排序的算法,对于给定的有向图,采用邻接表作为存储结构,为每个顶点设立一个链表,每个链表有一个表头结点,这些表头结点构成一个数组,表头结点中增加一个存放顶点入度的域count。即将邻接表定义中的VNode类型修改如下： typedef struct /*表头结点类型*/ { Vertex data; /*顶点信息*/ int count; /*存放顶点入度*/ ArcNode *firstarc; /*指向第一条弧*/ } VNode; void TopSort(VNode adj[],int n) { int i,j;int St[MAXV],top=-1; /*栈St的指针为nt==0) /*入度为0的顶点入栈*/ { top++; St[top]=i; } while (top-1) /*栈不为空时循环*/ { i=St[top];top--; /*出栈*/ printf(%d ,i); p=adj[i].firstarc; while (p!=NULL) { j=p-adjvex; adj[j].count--; if (adj[j].count==0) { top++; St[top]=j; } p=p-nextarc; /*找下一个相邻顶点*/ } } } 8.7 AOE网与关键路径 若用前面介绍过的带权有向图(DAG)描述工程的预计进度,以顶点表示事件,有向边表示活动,边e的权c(e)表示完成活动e所需的时间(比如天数),或者说活动e持续时间。 图中入度为0的顶点表示工程的开始事件(如开工仪式),出度为0的顶点表示工程结束事件。则称这样的有向图为AOE网(Activity On Edge)。 通常每个工程都只有一个开始事件和一个结束事件,因此表示工程的AOE网都只有一个入度为0的顶点,称为源点(source),和一个出度为0的顶点,称为汇点(converge)。 如果图中