《数据结构》 第九章
《 数据结构》 第九章
数据结构 第九章查找 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
数据结构 9.12有序表的查找 折半查找每次将待查记录所在区间缩小一半。 适用条件:采用顺序存储结构的有序表。 算法实现:设表长为n,loW、hgh和md分别 指向待查元素所在区间的上界、下界和中点,k为 给定值。 初始时,令lowW=1,hgh= mid=L(ow +high)/2] 让k与md指向的记录比较: 若k=r[mid]key,查找成功。 若kr[mid]key,则ow=mid+r° 重复上述操作,直至low>high时,查找失败。 算法参见P220
数据结构 tjm 9.1.2 有序表的查找 折半查找:每次将待查记录所在区间缩小一半。 适用条件：采用顺序存储结构的有序表。 算法实现：设表长为n，low、high和mid分别 指向待查元素所在区间的上界、下界和中点，k为 给定值。 初始时，令low=1，high=n， mid=(low+high)/2。 让k与mid指向的记录比较： 若k=r[mid].key，查找成功。 若kr[mid].key，则low=mid+1。 重复上述操作，直至low>high时，查找失败。 算法参见P220
数据结构 例:找21 234567891011 513192137566475808892 low mid 1234567891011 513192137566475808892 Ow mid high 2345678 513192137566475808892 lowmid high
数据结构 tjm 例：找21 low mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 lowmid high
数据结构 例:找70 375664 188 low m d high 1319 37566475808892 ml d bt舒6号想 low mid high 3192137566475808892 low high mid 234 011 513192137566475808892 high low
数据结构 tjm 例：找70 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 high low
数据结构 判定树 为了分析二分查找的性能,可以用二叉树来描述二分 查找过程:树中每个结点表示表中一个元素,结点中 的值为该元素在表中的位置。把当前查找区间的中点 作为根结点,左子区间和右子区间分别作为根的左子 树和右子树,左子区间和右子区间再按此方法类推, 由此得到的二叉树称为二分查找的判定树。 i312137566475|80892 判定树: 5(8①D 找21:比较次数=3,在树上 找85:比较次数=3,不在树上
数据结构 tjm 判定树 为了分析二分查找的性能，可以用二叉树来描述二分 查找过程：树中每个结点表示表中一个元素，结点中 的值为该元素在表中的位置。把当前查找区间的中点 作为根结点，左子区间和右子区间分别作为根的左子 树和右子树，左子区间和右子区间再按此方法类推， 由此得到的二叉树称为二分查找的判定树。 2 5 8 11 1 4 7 10 3 9 判定树： 6 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找 21：比较次数 = 3，在树上 找 85：比较次数 = 3，不在树上
数据结构 索引顺序表查找—分块查找 查找过程:将表分成几块,块内无序,块间有 序;先确定待查记录所在块,再在块内查找。 适用条件:分块有序表。 算法实现: 用数组存放待查记录。 建立索引表,每个索引表结点含有最大关键字 城和指向本块第一个结点的指针
数据结构 tjm 索引顺序表查找——分块查找 查找过程：将表分成几块，块内无序，块间有 序；先确定待查记录所在块，再在块内查找。 适用条件：分块有序表。 算法实现： 用数组存放待查记录。 建立索引表，每个索引表结点含有最大关键字 域和指向本块第一个结点的指针