《数据结构》课程PPT教学课件（2015）第9章 查找

《数据结构》 第九章查找

《 数据结构》 第九章 查找

数据结构 第九章查找 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

数据结构 9.1.2有序表的查找 折半查找：每次将待查记录所在区间缩小一半。 适用条件：采用顺序存储结构的有序表。 算法实现：设表长为n,Iow、high和mid分别 指向待查元素所在区间的上界、下界和中点，k为 给定值。 初始时，令low=1,high=n, mid=L(Iow+high)/2。 让k与mid指向的记录比较： 若k=r[mid].key,查找成功。 若kr[mid].key,则low=mid+1。 重复上述操作，直至Iow>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 1 2 3 ￥ 6 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 lowmid high m

数据结构 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 2 4■ 5 6 7 8 9 10 11 51319 2137 566475 8088 92 low mid high 吉扇 9 10 19 高品64 75 80 88克 low mid high 日品高1高品 2 3 4 038站 9 645 low mid high 8 664 9 580 low high mid 2 3 4 5 61 7 d 9 1011 5 13 19 21 37 56 64 75 80 88 92 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

数据结构 判定树 为了分析二分查找的性能，可以用二叉树来描述二分 查找过程：树中每个结点表示表中一个元素，结点中 的值为该元素在表中的位置。把当前查找区间的中点 作为根结点，左子区间和右子区间分别作为根的左子 树和右子树，左子区间和右子区间再按此方法类推， 由此得到的二叉树称为二分查找的判定树。 日T吊37品64$08然克 3 891011 判定树： 10 8 找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，不在树上

数据结构 索引顺序表查找一分块查找 查找过程：将表分成几块，块内无序，块间有 序；先确定待查记录所在块，再在块内查找。 适用条件：分块有序表。 算法实现： 用数组存放待查记录。 建立索引表，每个索引表结点含有最大关键字 域和指向本块第一个结点的指针。 m

数据结构 tjm 索引顺序表查找——分块查找 查找过程：将表分成几块，块内无序，块间有 序；先确定待查记录所在块，再在块内查找。 适用条件：分块有序表。 算法实现： 用数组存放待查记录。 建立索引表，每个索引表结点含有最大关键字 域和指向本块第一个结点的指针