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