文档介绍：静态查找表
顺序表的查找
有序表的查找
索引顺序表的查找
动态查找表
二叉排序树和平衡二叉树
B_树和B+树
哈希表
什么是哈希表
哈希函数的构造方法
处理冲突的方法
哈希表的查找及其分析
第九章查找
基本概念
查找表:是由同一类型的数据元素(或记录)构成的集合。表中的每个记录由若干个数据项构成,其中可以唯一地标识一个记录的数据项称为主关键字。
查找操作类型:
①在查找表中查询某个记录是否存在
②检索某个记录的各种属性
③在查找表中插入一个记录
④从查找表中删除一个记录
根据对查找表所进行查找操作的不同,查找表可被分为两类:
静态查找表 
动态查找表
平均查找长度:为确定记录在查找表中的位置,通常把查找过程中对关键字需要进行的平均比较次数,称为平均查找长度ASL。
9. 1 静态查找表
若对查找表只作查询和检索操作,则称此类查找表为静态查找表。
静态查找表可以有不同的表示方式,在不同的表示方法中,实现查找操作的方法也不同:
顺序表的查找
有序表的查找
静态树表的查找
顺序索引表的查找
当以顺序表或线性链表表示静态查找表时,可采用顺序查找法。
顺序查找的过程为:
从表的一端开始,顺序扫描线性表,依次将扫描到的记录关键字与给定值K相比较,若相等,则查找成功;若扫描结束后,仍未找到,则查找失败。
顺序表的查找
typedef struct{ ElemType *elem; // 数据元素存储空间基址, int length; // 表中元素个数 } SSTable;
顺序表的类型描述:
int Search(SSTable ST, KeyType key) { // 在顺序表ST中查找其关键字等于给定值的数据元素 // 若找到,则返回其在ST中的位序,否则返回0 i = 1; // i 的初值为第1个元素的位序 while( i<= && ([i].key!=key) ) ++i; // 依次进行判定 if (i <= ) return i; // 找到满足判定条件的数据元素为第 i 个元素 else return 0;
//该查找表中不存在满足判定的元素 }
顺序表查找算法(基于顺序存储结构):
int Search_Seq(SSTable ST, KeyType key)
{
int i;
[0].key=key; // 哨兵
for( i=; [i].key != key; --i );
// 从后往前找
return i; // 找不到时,i为0
}
顺序表查找算法(改进算法):
性能分析:
在等概率的情况下,顺序查找成功时的平均查找长度为:
ASL = (n+1) / 2
不成功时的平均查找长度为:ASL = n+1。
所以顺序查找的平均查找长度为:ASL= 3(n+1) / 4。
 
当记录的查找概率不相等时,应把记录按查找概率从大到小重新排列,以提高查找效率。在查找概率无法预先确定时,可以在记录中附设一个频度域,并使顺序表中的记录始终按访问频度非递减有序排列。
顺序查找的优点是:算法简单,且对表的结构无任何要求。
缺点是:查找效率低,当n较大时,不宜采用顺序查找。
有序表的查找
当静态查找表是有序表,即表中结点是按关键字有序,并采用顺序存储结构时,可用折半查找法。
折半查找的查找的过程是:
先确定待查记录所在的范围(区间),然后逐步缩
小查找范围,直到找到该记录或者找不到为止。
所谓“折半”的含义是指,先将给定值和所查区间中
间位置的记录的关键字进行比较,若相等,则查找成
功,否则,依给定值大于或小于该关键字继续在后半个
区间或前半个区间中进行查找。