一算法评价 ·判定树：描述查找过程的二叉树叫~ ·有n个结点的判定树的深度为Ilog2n+1 ·折半查找法在查找过程中进行的比较次数最多不 超过其判定树的深度 ·折半查找的ASL 设表长n=2-1,h=log2(n+1),即判定树是深度为h的满二叉树 设表中每个记录的查找概率相等印，=】 n 则：-含-空-空2ga-1go+w-1 n i=
– 算法评价 • 判定树：描述查找过程的二叉树叫~ • 有n个结点的判定树的深度为log2n+1 • 折半查找法在查找过程中进行的比较次数最多不 超过其判定树的深度 • 折半查找的ASL log ( 1) 1 log ( 1) 1 1 2 1 1 1 2 1, log ( 1), 2 2 1 1 1 1 2 + − + − + = = = = = = − = + = − = = n n n n j n c n ASL p c n p n h n h h j j n i i n i i i i h 则： 设表中每个记录的查找概率相等 设表长 即判定树是深度为 的满二叉树
·9.1.4分块查找 -查找过程：将表分成几块，块内无序，块 间有序；先确定待查记录所在块，再在块 内查找 一适用条件：分块有序表 一算法实现 ·用数组存放待查记录，每个数据元素至少含有 关键字域 ·建立索引表，每个索引表结点含有最大关键字 域和指向本块第一个结点的指针 一算法描述
• 9.1.4 分块查找 –查找过程：将表分成几块，块内无序，块 间有序；先确定待查记录所在块，再在块 内查找 –适用条件：分块有序表 –算法实现 • 用数组存放待查记录,每个数据元素至少含有 关键字域 • 建立索引表，每个索引表结点含有最大关键字 域和指向本块第一个结点的指针 –算法描述
索引表 22 48 86 查38 7 13 123456789101112131415161718 2212138920334244382448605874578653 ★查找过程： (1)先确定待查记录所在的块（子表） (2)然后在块中顺序查找
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53 22 48 86 1 7 13 索引表 查38 查找过程： （1）先确定待查记录所在的块（子表） （2）然后在块中顺序查找
一分块查找方法评价 ASLbs =Lp +Lw 其中：L,一一查找索引表确定所在块的平均查找长度 L。一一在块中查找元素的平均查找长度 若将表长为的表平均分成b块，每块含s个记录，并设表中每个记录的 查找概率相等，则： @啊预直钱箱定所在块仪字+片立-生”县护+】 (②)用折半查找确定所在块：45L=g,+)+氵
–分块查找方法评价 2 (2) log ( 1) ( ) 1 2 1 2 1 2 1 1 1 (1) 2 1 1 s s n ASL s s b s n i s j b ASL n b s L L ASL L L b s s i b j b s w b b s b w + + = + + + + + = + = = + = = 用折半查找确定所在块： 用顺序查找确定所在块： 查找概率相等，则： 若将表长为 的表平均分成 块，每块含 个记录，并设表中每个记录的 — —在块中查找元素的平均查找长度 其中： — —查找索引表确定所在块的平均查找长度
查找方法比较 顺序查找 折半查找 分块查找 ASL 最大 最小 两者之间 表结构 有序表、无序表 有序表 分块有序表 存储结构 顺序存储结构 顺序存储结构顺序存储结构 线性链表 线性链表
ASL 最大 最小 两者之间 表结构 有序表、无序表 有序表 分块有序表 存储结构 顺序存储结构 线性链表 顺序存储结构 顺序存储结构 线性链表 查找方法比较 顺序查找 折半查找 分块查找