《数据结构》 第九章
《 数据结构》 第九章
数据结构 第九章查找 9.1静态查找表 91.1顺序表的查找 912有序表的查找 9.2动态查找表 921二叉排序树和平衡二叉树 922B树和B+树 93哈希表 931什么是哈希表 932哈希函数的构造方法 933处理冲突的方法 934哈希表的查找及其分析
数据结构 tjm 第九章 查找 9.1 静态查找表 9.1.1 顺序表的查找 9.1.2 有序表的查找 9.2 动态查找表 9.2.1 二叉排序树和平衡二叉树 9.2.2 B-树和B+树 9.3 哈希表 9.3.1 什么是哈希表 9.3.2 哈希函数的构造方法 9.3.3 处理冲突的方法 9.3.4 哈希表的查找及其分析
数据结构 查找表:由同一类型的数据元素构成的集合 对查找表的常用操作: 查询某特定元素是否在表中存在 查询某特定元素的各种属性 在查找表中插入一个数据元素 在查找表中删除一个数据元素 查找:也叫检索,是根据给定的某个值,在表中确 定一个关键字等于给定值的数据元素。 关键字:可以标识一个数据元素的某个数据项。 主关键字:可以唯一地识别一个数据元素的关键字 静态查找表:只进行查询某元素在表中与否或检索 某元素的各种属性操作的表。 动态查找表:查找时同时进行插入表中无的元素或 删除表中有的某元素的表
数据结构 tjm 查找表：由同一类型的数据元素构成的集合。 对查找表的常用操作： 查询某特定元素是否在表中存在 查询某特定元素的各种属性 在查找表中插入一个数据元素 在查找表中删除一个数据元素 查找：也叫检索，是根据给定的某个值，在表中确 定一个关键字等于给定值的数据元素。 关键字：可以标识一个数据元素的某个数据项。 主关键字：可以唯一地识别一个数据元素的关键字。 静态查找表：只进行查询某元素在表中与否或检索 某元素的各种属性操作的表。 动态查找表：查找时同时进行插入表中无的元素或 删除表中有的某元素的表
数据结构 91静态查找表 静态查找表的ADT参见P216 查找过程:从表的一端开始逐个进行记录的关键字 和给定值的比较。 作为静态查找表存储结构的顺序表的类型定义参见 P216 顺序表的查找算法参见P216
数据结构 tjm 静态查找表的ADT参见P216 查找过程：从表的一端开始逐个进行记录的关键字 和给定值的比较。 作为静态查找表存储结构的顺序表的类型定义参见 P216 顺序表的查找算法参见P216 9.1 静态查找表
找64 数据结构 例: 01234567891011 64513192137566475808892 监视哨 比较次数 查找第n个元素:1〈比较次数 ■■■■■■■■■■ 查找第个元素:n-i+1 查找失败: n+1 顺序查找方法的平均查找长度ASL 对含有n个记录的表,ASL=∑PC 设表中每个元素的查找概率相等P=元 则ASL=∑Pc=∑(n-1+1) 1n(n+1)n+1
数据结构 tjm i 例: 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找64 64 监视哨 i i i i 比较次数： 查找第n个元素： 1 ………. 查找第i个元素： n-i +1 查找失败： n+1 顺序查找方法的平均查找长度ASL: = = n i i i n ASL p c 1 对含有 个记录的表， 2 1 2 1 ( 1) ( 1) 1 1 1 1 + = + = = − + = = = = n n n n n i n ASL p c n p n i n i i i i 则 设表中每个元素的查找概率相等 比较次数 =5