有序表的查找—一折半查找 第九章查找 折半查找的平均查找长度的计算: 记h=log(n+1),即有n=2-1,则描述折半查找的判定树是深 度为h的满二叉树。设表中每个记录的查找概率均相等(P=1/n), 则查找成功时折半查找的平均查找长度 ASLb=∑PC1=∑j21 其中为层数,2H1为该层结点数。 记S=∑j2,1则 S=2+221+3.2+…+(h-1) h-2 +h.2 2S=2+2.22+3.23+…+(h-1).241+h2h 2S-S=h.2h-(20+21+…+2-) 故有S=∑j21=h2-(2 (2-1)=(n+1)log2(n+1)-n n+1 因为4SLb ==log2(n+1) 当n>1时,有、212=p(l+)-丁 第16页
第九章 查找 第16页 折半查找的平均查找长度的计算： 记 h=log2 (n+1) ，即有 n=2h -1，则描述折半查找的判定树是深 度为h的满二叉树。设表中每个记录的查找概率均相等（Pi=1/n）， 则查找成功时折半查找的平均查找长度 其中j为层数，2 j-1为该层结点数。 记 ，则 故有 因为 当n>>1时，有 有序表的查找——折半查找
有序表的查找—一折半查找 第九章查找 说明: 折半查找的效率比顺序查找高。 而排序本身是一种很费时的操作,即使采用高效率的排一 序方法也要花费 o(nlog2n)的时间代价。 另外,折半查找仅适用于顺序存储结构,为保持表的有序 性,在顺序结构里插入和删除都必须移动大量的结点。故 折半查找特别适用于那些一经建立就很少改动,而又经常 需要查找的线性表,而对那此查找少而又经常需要改动的 线性表,可来用链表作存储结构,进行版序查找; 第17页一
第九章 查找 第17页 说明： 折半查找的效率比顺序查找高。 有序表的查找——折半查找 而排序本身是一种很费时的操作，即使采用高效率的排 序方法也要花费 O(nlog2n) 的时间代价。 另外，折半查找仅适用于顺序存储结构，为保持表的有序 性，在顺序结构里插入和删除都必须移动大量的结点。故 折半查找特别适用于那些一经建立就很少改动，而又经常 需要查找的线性表，而对那此查找少而又经常需要改动的 线性表，可采用链表作存储结构，进行顺序查找；
十索引顺序表的查找—一分块查找 第九章查找 以索引顺序表表示静态査找表时,可采用分块查找( Blocking Search)方法来进行查找 分块查找又称索引顺序查找,它是一种性能介于顺序查找和 折半查找之间的方法 分块查找法要求按如下的索引方式来存储一个线性表: 将表R[1.n均分为b块,前b-1块中结点个数为s=「n/b],第 b块的结点数小于或等于S。每一块中的关键字不一定有序,但 一前一块中的最大关键字必须小于后一块中的最小关键字,即要 求表是“分块有序”的。抽取各块中的最大关键字及起始位 置,构成一个索引表ID[1.b。由于表R是分块有序的,所以 索引表应是一个递增有序表。 第
第九章 查找 第18页 索引顺序表的查找——分块查找 以索引顺序表表示静态查找表时，可采用分块查找（ Blocking Search）方法来进行查找。 分块查找又称索引顺序查找，它是一种性能介于顺序查找和 折半查找之间的方法。 分块查找法要求按如下的索引方式来存储一个线性表： 将表 R[1..n] 均分为b块，前b-1块中结点个数为 ，第 b块的结点数小于或等于S。每一块中的关键字不一定有序，但 前一块中的最大关键字必须小于后一块中的最小关键字，即要 求表是 “分块有序”的。抽取各块中的最大关键字及起始位 置，构成一个索引表 ID[1..b]。由于表R是分块有序的，所以 索引表应是一个递增有序表
索引顺序表的查找—一分块查找 第九章查找 示例3分块有序表的索引存储表示 索引表 最大关键字224886 起始地垃 713 图9.6表及其索引表 2212138|920334244|38{2448605874498653 子表1 子表2 子表3 分块查找的算法思想: ①1)查找索引表,确定待查关键字所在的块(子表)。由于索引表 是按记录关健字有序,故宜采用折半查找法 2)在所确定的块中查找是否存在关键字与给定值相同的记录。此 时需采用顺序查找法 故分块査找的算法实际上是折半查找算法和顺序查找算法的 简单合成。 第19页
第九章 查找 第19页 示例3 分块有序表的索引存储表示 分块查找的算法思想： (1) 查找索引表，确定待查关键字所在的块（子表）。由于索引表 是按记录关健字有序，故宜采用折半查找法； (2) 在所确定的块中查找是否存在关键字与给定值相同的记录。此 时需采用顺序查找法。 故分块查找的算法实际上是折半查找算法和顺序查找算法的 简单合成。 22 48 86 1 7 13 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53 索引表 最大关键字 起始地址 子表1 子表2 子表3 索引顺序表的查找——分块查找 图9.6 表及其索引表
索引顺序表的查找—分块查找 第九章查找 外块查找的算法外析 分块查找实际上是两次查找过程,故整个算法的平均查 找长度是两次查找的平均查找长度之和,即 ASLhs Ln+Lwy 其中 L:查找索引表所在子表的平均查找长度 在子表中顺序查找记录的平均查找长度 设将表均匀分布成b个子表,每个子表包含s个记录(最后 个子表可能不足s个记录),并设表中每个记录的查找概率 一均相等,即每个子表的查找概率为1/b,子表中每个记录的查 一找概率为1/s (1)若用顺序査找确定所在块,则 与表长n有关, 与块中记录个数有关 AS =L+L b ∑j+∑ b+1s+11n +s)+1°(9-15) 20
第九章 查找 第20页 分块查找的算法分析 分块查找实际上是两次查找过程，故整个算法的平均查 找长度是两次查找的平均查找长度之和，即 ASLbs=Lb+Lw， 其中 Lb：查找索引表所在子表的平均查找长度 Lw：在子表中顺序查找记录的平均查找长度 设将表均匀分布成b个子表，每个子表包含s个记录（最后 一个子表可能不足s个记录），并设表中每个记录的查找概率 均相等，即每个子表的查找概率为1/b，子表中每个记录的查 找概率为1/s。 (1) 若用顺序查找确定所在块，则 索引顺序表的查找——分块查找 与表长n有关， 与块中记录个数s有关