第九章查找 学习要点 熟练掌握顺序查找、二分查找和分块查找的方法 并能够灵活使用 理解二叉排序树的定义，熟练掌握二叉排序树的 相关运算和查找过程 掌握哈希表的建立方法和查找过程。 熟练掌握各种查找方法在等概率下的平均查找长 度的计算方法
n 熟练掌握顺序查找、二分查找和分块查找的方法 并能够灵活使用。 n 理解二叉排序树的定义，熟练掌握二叉排序树的 相关运算和查找过程。 n 掌握哈希表的建立方法和查找过程。 n 熟练掌握各种查找方法在等概率下的平均查找长 度的计算方法。 学习要点 第九章 查找
?基本概念 查找表：是由同一类型的数据元素（或记录）构 成的集合，由于“集合”中的数据元素之间存在着 松散的关系，因此查找表是一种应用灵便的数据 结构 有关操作 ◆ 查询某个“特定的”数据元素是否在查找表 中 检索某个“特定的”数据元素的各种属性； 在查找表中插入一个数据元素； 从杏找夫中训士其个数捏云麦
l 查找表 ：是由同一类型的数据元素(或记录)构 成的集合,由于“集合”中的数据元素之间存在着 松散的关系，因此查找表是一种应用灵便的数据 结构。 l 有关操作 u 查询某个“特定的”数据元素是否在查找表 中 u 检索某个“特定的”数据元素的各种属性； u 在查找表中插入一个数据元素； u 从查找表中删去某个数据元素。 v 基本概念
基本概念 查找表的分类 静态查找表：仅作查询和检索操作的查找表。 动态查找表：在查找过程中同时插入查找表中 不存在的数据元素，或者从查找表中删除已存 在的某个数据元素，此类表为动态查找表。 关键字 是数据元素（或记录）中某个数据项的值，用以标 识（识别一个数据元素（或记录）。若此关键字可以 识别唯一的一个记录，则称之谓“主关键字”。若 此关键字能识别若干记录，则称之谓“次关键字
l 查找表的分类 u 静态查找表：仅作查询和检索操作的查找表。 u 动态查找表：在查找过程中同时插入查找表中 不存在的数据元素，或者从查找表中删除已存 在的某个数据元素，此类表为动态查找表。 l 关键字 是数据元素(或记录)中某个数据项的值，用以标 识(识别)一个数据元素(或记录)。若此关键字可以 识别唯一的一个记录，则称之谓“主关键字” 。若 此关键字能识别若干记录，则称之谓“次关键字” 。 v 基本概念
冬基本概念 查找 根据给定的某个值，在查找表中确定一个其关 键字等于给定值的数据元素或（记录）。 若查找表中存在这样一个记录，则称“查找成 功”，查找结果：给出整个记录的信息，或指示 该记录在查找表中的位置；否则称“查找不成 功”，查找结果：给出“空记录”或“空指针
l 查找 根据给定的某个值，在查找表中确定一个其关 键字等于给定值的数据元素或(记录)。 若查找表中存在这样一个记录，则称“查找成 功” ，查找结果：给出整个记录的信息，或指示 该记录在查找表中的位置；否则称“查找不成 功” ，查找结果：给出“空记录”或“空指针” 。 v 基本概念
冬查找的基本概念 查找操作的性能分析 冬查找速度（时间复杂度） 冬占用存储空间多少（空间复杂度） 平均查找长度ASL(Average Search Length): 为确定记录在表中的位置，需和给定值进行比较 的关键字的个数的期望值叫查找算法的~ 对于一个含有个元素的表，查找成功时的平均 查找长度可表示为ASL= i=l
v 查找的基本概念 对于一个含有n个元素的表，查找成功时的平均 查找长度可表示为ASL= n i i i p c 1 查找操作的性能分析 v查找速度(时间复杂度) v占用存储空间多少(空间复杂度) v平均查找长度ASL(Average Search Length)： 为确定记录在表中的位置，需和给定值进行比较 的关键字的个数的期望值叫查找算法的~