文档介绍：数据结构--静态查找表
￡静态查找表
￡概述
ADT StaticSearchTable {
数据对象D：D是具有相同特性的数据元素的集合。各个数据元
素均含有类型相同，可唯一标识数据元素键字有序均可应用。
（3）性能分析
①查找算法的判定树
判定树：描述查找过程的二叉树。
判定树中圆形结点为内部结点；方形结点为外部结点（由内部结点的
空指针域链接）。树中每个圆形结点标识表中一个记录，结点中的值为该
记录在表中的位置。方形结点中的值v为：第i结点的值< v <第i＋1结点的
值；若i结点为第1个结点则v <第1个结点的值；若i结点为最后一个结点则
v >最后一个结点的值。
多不超过树的深度，而具有n个结点的判定树的深度为，所以，
显然，折半查找法在查找成功（或不成功）时进行比较的关键字个数最
折半查找法在查找成功时和给定值进行比较的关键字个数至多为。
例如，上述11个元素的表的例子。查找21的过程如红线所示，查找
85的过程如蓝线所示。
判定树和查找21(红线)，85(蓝线)的过程
6
3
9
1
4
7
10
2
5
8
11
-1
3-4
6-7
9-10
1-2
2-3
4-5
5-6
7-8
8-9
10-11
11-
②折半查找的平均查找长度
假定有序表的长度n＝2h-1（反之，h＝log2(n+1)）,则描述折半查找的
判定树是深度为h的曼二叉树。假设表中每个记录的查找概率相等
(Pi = 1/n)，则查找成功时折半查找的平均查找长度：
对任意的n，当n较大(n>50)时，可有下列近似结果：
（4）折半查找算法的特点
特点：只适用于有序表，且限于顺序存储结构（对线性链表无法进行
折半查找）。
（5）斐波那契查找
斐波那契序列：F0 = 0, F1= 1, Fi = Fi-1+ Fi-2, i≥2。
算法思想：假设开始时表中记录个数比某个斐波那契数小，即n＝Fu-1，
[Fu-1].key进行比较，若相等，则查找成功；若
key < [Fu-1].key，[1][Fu-1]的子表中进
行查找，[Fu-1＋1][Fu-1]的子表中进行查找，
后一子表的长度为Fu-2-1。
特点：①斐波那契查找的平均性能比折半查找好，但最坏情况下的性能
却比折半查找差。
②分割时只需进行加、减运算。
（6）插值查找
[i].key
的查找方法。
[h]分别为有序表中具有最小关键字和最大关键字的记录。显然，
这种插值查找只适于关键字均匀分布的表，在这种情况下，对表长较大的顺序
表，其平均性能比折半查找好。
令
，[l]和
￡索引顺序表的查找
（1）分块查找
分块查找又称索引顺序查找，这是顺序查找的一种改进方法。在此
查找法中，除表本身以外，尚需建立一个“索引表”。如下例所示。
例如，，表中含有18个记录，可分成
3个子表(R1, R2, …, R6)、(R7, R8, …, R12)和(R13, R14, …, R18)。对每一个子
表（或称块）建立索引项。索引表按关键字有序，则表或者有序或者分块
有序。
22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53
索引表
最大关键字
起始地址
22 48 86
1 7 13
表及其索引表
索引项包括：
关键字项：其值为该子表内的最大关键字。
指针项：指示该子表的第一个记录在表中的位置。
分块有序：即后一个子表中的所有记录的关键字均大于前一个子表中
的最大关键字。
分块查找的算法思想：
①确定待查记录所在的块（子表）；
②在块中顺序查找
（2）性能分析
分块查找的平均查找长度为：
其中：Lb为查找索引表确定所在块的平均查找长度，Lw为在块中查找元素的
平均查找长度。
ASLbs＝Lb＋Lw
①用顺序查找确定所在块
；又假定表中每个记录的查找概率相等，则每
一般情况下