静态查找表顺序表的查找——顺序查找有序表的查找——折半查找索引....ppt

静态查找表
顺序表的查找——顺序查找
有序表的查找——折半查找
索引顺序表的查找——分块查找
动态查找表
二叉排序树
哈希表(散列表)
哈希函数的构造方法
处理冲突的方法
哈希表的查找及其分析
第九章查找(Search)
基本概念——查找
查找
在数据集合(查找表)中寻找满足某种条件的“特定的”数据元素。
查找结果通常有两种可能:
查找成功
即找到满足条件的数据对象。这时作为结果,可报告该对象在结构中的位置,还可给出该对象中的具体信息。
查找不成功
查找失败。作为结果,可给出一个“空”记录或“空”指针,还应报告一些信息,如失败标志、位置等。
查找表(Search Table)
同一数据类型的对象(或记录)组成的用于查找的数据集合。
查找表的操作
静态查找表(Static Search Table)——静态环境,查找表的结构在各类操作的前后不发生改变:
查询某个“特定的”数据元素是否在查找表中;
检索某个“特定的”数据元素的各种属性。
动态查找表(Dynamic Search Table)——动态环境,为保持较高的查找效率, 查找表结构在执行插入和删除等操作的前后将自动进行调整,结构可能发生变化:
在查找表中插入一个数据元素;
从查找表中删去某个数据元素。
查找表
关键字或键(Key):
在每个记录中有若干属性。可以识别一个数据元素的属性的值称为关键字或键。
主关键字
其值可唯一地标识这个记录;
使用基于主关键字的查找,查找结果应是唯一的。
次关键字
可以识别若干个记录的关键字称为。
使用基于次关键字的查找,结果可能是多个记录,即查找结果不唯一。
查找:
根据给定的某个值,在查找表中确定一个其关键字等于给定值的记录或数据元素。
关键字
时间复杂度——查找算法的时间效率
在查找过程中关键字的平均比较次数或平均读写磁盘次数(只适合于外部查找)。
平均查找长度ASL(Average Search Length)。
为确定记录在表中的位置,需和给定值进行比较的关键字个数的期望值。
设查找第 i 个元素的概率为 Pi , 查找到第 i 个元素所需比较次数为 Ci , 则查找成功的平均搜索长度:
通常是查找结构中对象总数 n 或文件结构中物理块总数 n 的函数。
空间复杂度——算法所需的存储空间
算法的复杂性
查找方法评价
关键字类型说明
typedef float KeyType; //实型
typedef int KeyType; //整型
typedef char *KeyType; //字符串型
数据元素类型定义
typedef struct{
KeyType key; //关键字域
…//其他域
}ElemType;
类型说明
顺序表的查找——顺序查找
有序表的查找——折半查找(二分查找)
索引顺序表的查找——分块查找
查找方法的比较
静态查找表(Static Search Table)
1、顺序表的查找——顺序查找
顺序查找及算法
性能分析
特点
顺序查找(Sequential Search)
所谓顺序查找,又称线性查找,主要用于在顺序表或线性链表结构中进行查找。
从表的最后一个记录开始,顺序用各记录的关键字与给定值 x 进行比较;
若找到相等的记录, 则查找成功;给出该记录在表中的位置;
若整个表都已检测完仍未找到关键字与 x 相等的对象,则查找失败;给出失败信息。
typedef struct{
ElemType *elem; //数据元素存储空间基址
//建表时按实际长度分配,0号单元留空
int length; //表长度
}SSTable;
顺序存储结构