文档介绍：￡概述
￡查找表
￡相关术语
￡类型说明
￡静态查找表
￡概述
￡顺序表的查找
￡有序表的查找
￡索引顺序表的查找
￡动态查找表
￡概述
￡二叉排序树和平衡二叉树
￡ B-树和B+树
￡哈希表
￡定义
￡哈希函数的构造
￡处理冲突的方法
￡哈希表的查找及其分析
第九章查找
￡静态查找表
￡概述
ADT StaticSearchTable {
数据对象D:D是具有相同特性的数据元素的集合。各个数据元
素均含有类型相同,可唯一标识数据元素的关键字。
数据关系R:数据元素同属一个集合。
基本操作P:
Create (&ST, n);
操作结果:构造一个含n个数据元素的静态查找表ST。
Destroy (&ST);
初始条件:静态查找表ST存在。
操作结果:销毁表ST。
Search (ST, key);
初始条件:静态查找表ST存在,key为和关键字类型相同的给定值。
操作结果:若ST中存在其关键字等于key的数据元素,则函数值为
该元素的值或在表中的位置,否则为“空”。
Traverse (ST, Visit ( ));
初始条件:静态查找表ST存在,Visit是对元素操作的应用函数。
操作结果:按某种次序对ST的每个元素调用函数visit ( )一次且仅
一次。一旦visit ( )失败,则操作失败。
} ADT StaticSearchTable
(1)静态查找表的抽象数据类型定义:
(2)查找操作的性能分析
衡量查找算法好坏的依据:其关键字和给定值进行过比较的记录个
数的平均值。
平均查找长度(Average Search Length):为确定记录在查找表中
的位置,需和给定值进行比较的关键字个数的期望值,称为查找算法在
查找成功时的平均查找长度。
对于含有n个记录的表,查找成功时的平均查找长度为:
(9-1)
其中:Pi为查找表中查找第i个记录的概率,且
;Ci为找到表中其关
键字与给定值相等的第i个记录时,和给定值已进行过比较的关键字个数。
查找算法的平均查找长度=
查找成功时的平均查找长度+ 查找不成功时的平均查找长度
静态查找表可以有不同的表示方法,在不同的表示方法中,实现查找操作的方法也不同。
一、顺序查找表
顺序查找是最基本,最简单的查找方法。其查找过程为:从表中第n个记录开始,逐个进行记录的关键字和给定值的比较。若某个关见键字与给定值像相等,则查找成功,找到所查找记录;反之,若直之第一个记录,其关键字与给定值不等,则表明表中没有所查记录,查找不成功。
(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)顺序查找算法的特点
优点:算法简单且适应面广。它对表的结构无任何要求,无论
记录是否按关键字有序均可应用。
上述顺序查找表的查找算法简单,
但平均查找长度较大,特别不