第10章排序 10.1查找的基本概念 10.2静态查找表 10.3动态查找表 10.4哈希表
1 10.1 查找的基本概念 10.2 静态查找表 10.3 动态查找表 10.4 哈希表 第10章 排序
10.1查找的基本概念 是一种数据结构 查找表由同一类型的数据元素(或记录)构成的集合。 查找 查询特定元素是否在(数据元素集合)表中的过程。 查找成功若表中存在特定元素,称查找成功,应输出该记录; 查找不成功—否则,称查找不成功(也应输出失败标志或失败位置 静态查找—只查找,不改变数据元素集合内的数据元素。 动态查找—既查找,又改变(增减)集合内的数据元素 关键字 记录中某个数据项的值,可用来识别一个记录 (预先确定的记录的某种标志 主关键字 可以唯一标识一个记录的关键字—刚如“学号 次关键字识别若干记录的关键字一例如“女
2 10.1 查找的基本概念 ——若表中存在特定元素，称查找成功，应输出该记录； ——否则，称查找不成功（也应输出失败标志或失败位置） 查找表 查 找 查找成功 查找不成功 静态查找 动态查找 关键字 主关键字 次关键字 ——由同一类型的数据元素（或记录）构成的集合。 ——查询特定元素是否在(数据元素集合）表中的过程。 ——只查找，不改变数据元素集合内的数据元素。 ——既查找，又改变（增减）集合内的数据元素。 ——记录中某个数据项的值，可用来识别一个记录 ( 预先确定的记录的某种标志) ——可以唯一标识一个记录的关键字 例如“学号” 例如“女” 是一种数据结构 ——识别若干记录的关键字
讨论: 查找的过程是怎样的? 给定一个值K,在含有η个记录的文件中进行搜索,寻找 一个关键字值等于K的记录,如找到则输出该记录,否则输 出查找不成功的信息。 对查找表常用的操作有哪些? 特定的”=关键 查询某个“特定的”数据元素是否在表中 查询某个“特定的”数据元素的各种属性; 在查找表中插入一元素 从查找表中删除一元素 有哪些查找方法? 例如查字典 查找方法取决于表中数据的排列方式; 针对静态查找表和动态查找表的查找方法也有所不同
3 讨论2：对查找表常用的操作有哪些？ ❖ 查询某个“特定的”数据元素是否在表中； ❖ 查询某个“特定的”数据元素的各种属性； ❖ 在查找表中插入一元素； ❖ 从查找表中删除一元素。 讨论3：有哪些查找方法？ 查找方法取决于表中数据的排列方式; 讨论： 讨论1：查找的过程是怎样的？ 给定一个值K，在含有n个记录的文件中进行搜索，寻找 一个关键字值等于K的记录，如找到则输出该记录，否则输 出查找不成功的信息。 例如查字典 针对静态查找表和动态查找表的查找方法也有所不同。 “特定的”=关键 字
如何评估查找方法的优劣? 明确:查找的过程就是将给定的K值与文件中各记录的关 键字项进行比较的过程。所以用比较次数的平均值来评 估算法的优劣。称为平均查找长度AS Average Search L eno 其中: 统计意义上的 n是文件记录个数; 数学期望值 P是查找第个记录的查找概率(通常取等概率即P;=1/n); c是找到第个记录时所经历的比较次数。 物理意义:假设每一元素被查找的概率相同,则查找每一 元素所需的比较次数之总和再取平均,即为 显然,ASL值越小,时间效率越高
4 讨论4：如何评估查找方法的优劣？ 明确：查找的过程就是将给定的K值与文件中各记录的关 键字项进行比较的过程。所以用比较次数的平均值来评 估算法的优劣。称为平均查找长度ASL。 = = n i ASL Pi Ci 1 其中： n是文件记录个数； Pi是查找第i个记录的查找概率（通常取等概率,即Pi =1/n）; Ci是找到第i个记录时所经历的比较次数。 统计意义上的 数学期望值 物理意义：假设每一元素被查找的概率相同，则查找每一 元素所需的比较次数之总和再取平均，即为 ASL。 显然，ASL值越小，时间效率越高。 Average Search Length
10.2静态查找表 静态查找表主要有三种结构: 顺序表 有序顺序表 索引顺序表 针对静态查找表的查找算法主要有: 顺序查找(线性查找) 折半查找(二分查找) 分块查找(索引顺序查找)
5 针对静态查找表的查找算法主要有： 10.2 静态查找表 顺序查找（线性查找） 折半查找（二分查找） 分块查找（索引顺序查找） 静态查找表主要有三种结构： 顺序表 有序顺序表 索引顺序表