第9章?查找9.1查找的基本概念9.2静态查找9.3动态查找
第9章 查找 9.1 查找的基本概念 9.2 静态查找 9.3 动态查找
本章主要知识点：，查找的基本概念和衡量查找算法效率的标准，静态香找表，主要包括顺序香找方法和索引顺序方法，动态查找表，主要包括二又排序树
本章主要知识点： ● 查找的基本概念和衡量查找算法效率的标准 ● 静态查找表，主要包括顺序查找方法和索引顺序方 法 ● 动态查找表，主要包括二叉排序树
9.1.查找的基本概念查找查询特定元素是否在（数据元素集合）表中的过程若表中存在特定元素，称查找成功，应输出该记录；查找成功否则，称查找不成功（也应输出失败标志或失败位置查找不成功静态查找只查找，不改变数据元素集合内的数据元素，动态查找既查找，又改变（增减）集合内的数据元素，关键字记录中某个数据项的值，可用来识别一个记录例如“学号主关键字可以唯一标识一个记录的关键字次关键字识别若干记录的关键字例如“女
9.1 查找的基本概念 ——若表中存在特定元素，称查找成功，应输出该记录； ——否则，称查找不成功（也应输出失败标志或失败位置） 查 找 查找成功 查找不成功 静态查找 动态查找 关键字 主关键字 次关键字 ——查询特定元素是否在(数据元素集合）表中的过程。 ——只查找，不改变数据元素集合内的数据元素。 ——既查找，又改变（增减）集合内的数据元素。 ——记录中某个数据项的值，可用来识别一个记录 ——可以唯一标识一个记录的关键字 例如“学号” 例如“女” ——识别若干记录的关键字
讨论：如何评估查找方法的优劣？明确：查找的过程就是将给定的K值与文件中各记录的关键建字项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为平均查找长度ASLPAverageSearchASLPC二Lengthi=1其中:n是文件记录个数：P;是要查找数据元素的出现概率（通常查找成功，取P：=1/n）C是查找相应数据元素需进行的比较次数物理意义：假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为ASL。显然，ASL值越小，时间效率越高
讨论：如何评估查找方法的优劣？ 明确：查找的过程就是将给定的K值与文件中各记录的关 键字项进行比较的过程。所以用比较次数的平均值来评 估算法的优劣。称为平均查找长度ASL。 其中： n是文件记录个数； Pi是要查找数据元素的出现概率（通常查找成功，取Pi =1/n）; Ci是查找相应数据元素需进行的比较次数。 物理意义：假设每一元素被查找的概率相同，则查找每一元 素所需的比较次数之总和再取平均，即为ASL。 显然，ASL值越小，时间效率越高。 Average Search Length
9.2静态查找静态查找问题数据元素的存储结构主要是顺序存储结构静态查找主要有三种情况：无序序列有序序列索引结构
9.2 静态查找 静态查找主要有三种情况： 无序序列 有序序列 索引结构 静态查找问题数据元素的存储结构主要是顺序存储结构