数据结构--静态查找表.ppt

数据结构--静态查找表
1
￡ 静态查找表
￡ 概述
ADT StaticSearchTable {
数据对象D：D是具有相同特性的数据元素的集合。各个数据元
素均含有类型相同，可唯一标识数据元字和给定值的比较。若某个关见键字与给定值像相等，则查找成功，找到所查找记录；反之，若直之第一个记录，其关键字与给定值不等，则表明表中没有所查记录，查找不成功。
（1）顺序存储结构的类型定义
typedef struct {
ElemType *elem; //数据元素存储空间基址，建表时按
//实际长度分配，0号单元留空
int length; //表长度
} SSTable
int Search_Seq(SSTable ST,
KeyType kval) {
// 在顺序表ST中顺序查找其关键字等于
// key的数据元素。若找到，则函数值为
// 该元素在表中的位置，否则为0。
[0].key = kval; // 设置“哨兵”
for (i=; --i);
// 从后往前找
return i; // 找不到时，i为0
} // Search_Seq
[i].key!=kval;
（3）性能分析
假设n＝，则顺序查找的平均长度为：
ASL = nP1 + (n－1)P2 + … + 2Pn-1 + Pn
①只考虑查找成功时的情况
在顺序查找的过程中，式（9－1）中Ci取决于所查记录在表中的位置。
假设查找每个记录的概率相等，即 Pi＝1/n。则在等概率情况下顺序查
找的平均查找长度为：
（3）性能分析
②考虑查找成功和查找不成功时的情况
顺序查找中，不论给定值key为何值，查找不成功时和给定值进行比较的关
键字个数均为n＋1。
假设查找成功与不成功的可能性相同，对每个记录的查找概率也相等，则
Pi＝1/(2n)，此时顺序查找的平均查找长度为：
缺点：平均查找长度较大，特别是当n很大时，查找效率较低。
（4）顺序查找算法的特点
优点：算法简单且适应面广。它对表的结构无任何要求，无论
记录是否按关键字有序均可应用。
（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，则继