中国地质大学（武汉）：《数据结构和VC编程》课程教学资源（课件讲稿）第八章 查找

第八章查找 8.1查找的基本概念 关键字、查找、静态查找、动态查找、平均查 找长度 8.2静态查找表 1、无序表的查找 算法8.1 如书第252页所示 PT PRESS 退出

第 八 章 查找 8．1查找的基本概念 关键字、查找、静态查找、动态查找、平均查 找长度 8．2静态查找表 1、无序表的查找 算法8．1 如书第252页所示 退出

1、有序表的查找 (1)、线性查找 算法8.2 如书第253页所示 (2)、折半查找（二分查找） 算法8.3 如书第253页所示 PT PRESS 然东续了一列 n

1、有序表的查找 （1）、线性查找 算法8．2 如书第253页所示 （2）、折半查找（二分查找） 算法8．3 如书第253页所示

6 3 9 1 4 7 10 2 5 8 11) 图8-1 (3)、斐波那契查找 (4)、插值查找 PT PRESS 然东续了一列 n

图8-1 （3）、斐波那契查找 （4）、插值查找

1、分块查找（索引顺序表的查找） 块内最大关键字54 94 154 块起始地址 0 6 12 L.elem[[町36 54 43 28 49 25 58 74 63 65 7694101138146123 i0123456789101112131415 图8-2 PT PRESS 按续不一

1、分块查找（索引顺序表的查找） 图8-2

8.3动态查找表 8.3.1B树 1、 B树的定义 树结点包含的数据为： n,Po,(k1,P1,(k2P2),(k3,P3)..(kPn) PT PRESS 按续不一列 n

8．3动态查找表 8．3．1 B树 1、 B树的定义 树结点包含的数据为： n, p0 ,(k1 , p1 ),(k2 ,p2 ),(k3,p3 )……(kn ,pn )

root 51 A 1230 6678 B C 37 152025 3541 535465 68697176 798493 图8-3 PT PRESS 然东续了一 n

图8-3

1、B树的查找 2、B树的插入 root 51 A 667178 B C 53545765 6869 7276 798493 图8-4 PT PRESS 续不一 n

1、B树的查找 2、B树的插入 图8-4

a 30 30 b 6 20 40 20 40 g d 10 15 25 45 50 1015 2⑤ 35 38 45 50 (a)一棵三阶B树 (b)插入38后 今 30 30,40y b b 20 40,50 20 37 50 d e h d i 1015 25 35 38 55 10 15 25 35 38 45 55 (c)插入55后 (d) 插人37后 a ,3040 30,40 30 0 b 15 40 10,20 10,20 m 10 20 37 50 d k e g d h 1518 25 5 12 18 33 38 45 (e)插入5后 ()插入18后 (g)插入12后 图8-5 PT PRESS 续不一

图8-5

1、B树的删除 (1)、待删关键字在叶结点中 51 65,7178~ B C D 535457 6669 7276 79 8493 图8-6 PT PRESS 按续不一 n

1、B树的删除 （1）、待删关键字在叶结点中 图8-6

51 A 6678 B C 53545765 68697176 79 8493 图8-7 PT PRESS 然东续了一列 n

图8-7