数据结构课程的内容 线性结构（线性表、栈、队、串、数组） 逻辑结构 树结构 非线性结构 图结构 颜序结构 链式结构 数据结构： 物理（存储）结构 索引结构 散列结构 插入运算 删除运筧 数据运算 修改运算 查拢运算 排序运算 习
1 数据结构课程的内容
第9章查找 9.1基本概念 9.2静态查找表 9.3动态查找表 9.4哈希表 教材第8、11和12章省略，因《操作系统》课程会涉及
2 9.1 基本概念 9.2 静态查找表 9.3 动态查找表 9.4 哈希表 第9章 查找 教材第8、11和12章省略，因《操作系统》课程会涉及
9.1基本概念 是一种数据结构 查找表 由同一类型的数据元素（或记录)构成的集合。 查找 查询(Searching)特定元素是否在表中。 查找成功 若表中存在特定元素，称查找成功，应输出该记录； 查找不成功 否则，称查找不成功（也应输出失败标志或失败位置） 静态查找 只查找，不改变集合内的数据元素。 动态查找 既查找，又改变（增减）集合内的数据元素。 关键字 记录中某个数据项的值，可用来识别一个记录 (预先确定的记录的某种标志) 主关键字 可以唯一标识一个记录的关键字 例如“学号” 次关键字 识别若干记录的关键字 例如“女
3 9.1 基本概念 ——若表中存在特定元素，称查找成功，应输出该记录； ——否则，称查找不成功（也应输出失败标志或失败位置） 查找表 查 找 查找成功 查找不成功 静态查找 动态查找 关键字 主关键字 次关键字 ——由同一类型的数据元素（或记录）构成的集合。 ——查询(Searching)特定元素是否在表中。 ——只查找，不改变集合内的数据元素。 ——既查找，又改变（增减）集合内的数据元素。 ——记录中某个数据项的值，可用来识别一个记录 ( 预先确定的记录的某种标志) ——可以唯一标识一个记录的关键字 例如“学号” 例如“女” 是一种数据结构 ——识别若干记录的关键字
讨论： 讨论1：查找的过程是怎样的？ 给定一个值K,在含有个记录的文件中进行搜索，寻找 个关键字值等于K的记录，如找到则输出该记录，否则输 出查找不成功的信息。 讨论2：对查找表常用的操作有哪些？ “特定的”=关键 必 查询某个“特定的”数据元素是否在表中 查询某个“特定的”数据元素的各种属性； 在查找表中插入一元素； 冬.从查找表中删除一元素。 讨论3：有哪些查找方法？ 例如查字典 查找方法取决于表中数据的排列方式 针对静态查找表和动态查找表的查找方法也有所不同
4 讨论2：对查找表常用的操作有哪些？ ❖ 查询某个“特定的”数据元素是否在表中； ❖ 查询某个“特定的”数据元素的各种属性； ❖ 在查找表中插入一元素； ❖ 从查找表中删除一元素。 讨论3：有哪些查找方法？ 查找方法取决于表中数据的排列方式; 讨论： 讨论1：查找的过程是怎样的？ 给定一个值K，在含有n个记录的文件中进行搜索，寻找 一个关键字值等于K的记录，如找到则输出该记录，否则输 出查找不成功的信息。 例如查字典 针对静态查找表和动态查找表的查找方法也有所不同。 “特定的”=关键 字
讨论4：如何评估查找方法的优劣？ 明确：查找的过程就是将给定的K值与文件中各记录的关 键字项进行比较的过程。所以用比较次数的平均值来评 估算法的优劣。称为平均查找长度ASL。 ∑sc Average Search Length 其中： 统计意义上的 n是文件记录个数； 数学期望值 P是查找第i个记录的查找概率（通常取等概率，即P,=1/n); C是找到第个记录时所经历的比较次数。 物理意义：假设每一元素被查找的概率相同，则查找每 元素所需的比较次数之总和再取平均，即为 显然，ASL值越小，时间效率越高
5 讨论4：如何评估查找方法的优劣？ 明确：查找的过程就是将给定的K值与文件中各记录的关 键字项进行比较的过程。所以用比较次数的平均值来评 估算法的优劣。称为平均查找长度ASL。 = = n i ASL Pi Ci 1 其中： n是文件记录个数； Pi是查找第i个记录的查找概率（通常取等概率,即Pi =1/n）; Ci是找到第i个记录时所经历的比较次数。 统计意义上的 数学期望值 物理意义：假设每一元素被查找的概率相同，则查找每一 元素所需的比较次数之总和再取平均，即为 ASL。 显然，ASL值越小，时间效率越高。 Average Search Length