计算机专业 80● 网上教学改革 数据结构（本） 授课教师：范颖
计算机专业 网上教学改革 数 据 结 构（本） 授课教师：范颖
一、第八章查找解析 本章课程主要介绍查找的相关概念，掌握顺序查 找和折半查找的步骤和算法，掌握二叉排序树的 有关操作，了解哈希函数的构造和处理冲突的方 法。 www.open.ha.cn
www.open.ha.cn 一、第八章查找解析 ▪ 本章课程主要介绍查找的相关概念，掌握顺序查 找和折半查找的步骤和算法，掌握二叉排序树的 有关操作，了解哈希函数的构造和处理冲突的方 法
一、 第八章查找解析 ■1、有关查找的基本概念。 查找表：同一类型的记录构成的集合。 关键字：记录中某个数据项的值，用它可以识别 和确定一个记录。 查找：给定一个确定的值，在查找表中确定一个 记录，其相应的关键字等于给定值的操作。 www.open.ha.cn
www.open.ha.cn 一、第八章查找解析 ▪ 1、有关查找的基本概念。 查找表：同一类型的记录构成的集合。 关键字：记录中某个数据项的值，用它可以识别 和确定一个记录。 查找：给定一个确定的值，在查找表中确定一个 记录，其相应的关键字等于给定值的操作
一、 第八章查找解析 ■2、 线性表的几种查找。 (1)顺序查找：从表的一端开始逐个进行记录的关 键字和给定值的比较。 (2)折半查找：又称二分查找。前提条件是查找表 中记录相应的关键字值必须按升序或降序排列。 (3)分块查找：索引顺序查找，一种稀疏索引，同 时每个子表（称为块)之间是递增有序的，但块 内是无序的，即块外有序块内无序。 www.open.ha.cn e
www.open.ha.cn 一、第八章查找解析 ▪ 2、线性表的几种查找。 （1）顺序查找：从表的一端开始逐个进行记录的关 键字和给定值的比较。 （2）折半查找：又称二分查找。前提条件是查找表 中记录相应的关键字值必须按升序或降序排列。 （3）分块查找：索引顺序查找，一种稀疏索引，同 时每个子表（称为块）之间是递增有序的，但块 内是无序的，即块外有序块内无序
第八章查找解析 ·3、顺序查找怎么进行的。 找64 111098 7 6 54 32 10 64513192137566475808892 0 监视哨 比较次数： 比较次数=5 查找第1个元素： 1 查找第2个元素： 2 查找第n个元素： n 查找第i个元素：i 查找不成功： n+1 平均查找长度ASL=(n+1)/2 www.open.ha.cn 6
www.open.ha.cn 一、第八章查找解析 ▪ 3、顺序查找怎么进行的。 i 11 10 9 8 7 6 5 4 3 2 1 0 5 13 19 21 37 56 64 75 80 88 92 找64 64 监视哨 i i i i 比较次数： 比较次数=5 查找第1个元素： 1 查找第2个元素： 2 ………. 查找第n个元素： n 查找第i个元素： i 查找不成功： n+1 平均查找长度ASL=（n+1）/2
一、 第八章查找解析 ■4、折半查找怎么进行的。 查找过程：每次将待查找记录所在区间缩小一半 算法实现：设表长为n,low、high和mid分别指向 待查元素所在区间的上界、下界和中点，k为给定 值。初始时，令 low=0,high=n-1,mid=(low+high)/2 ■让k与mid指向的记录比较 若k==A[mid.key,查找成功 若kAmid.key,则low=mid+1 重复上述操作，直至Iow>high时，查找失败 www.open.ha.cn
www.open.ha.cn 一、第八章查找解析 ▪ 4、折半查找怎么进行的。 查找过程：每次将待查找记录所在区间缩小一半 算法实现：设表长为n，low、high和mid分别指向 待查元素所在区间的上界、下界和中点，k为给定 值。初始时，令 low=0,high=n-1,mid=(low+high)/2 ▪ 让k与mid指向的记录比较 若k= =A[mid].key，查找成功 若kA[mid].key，则low=mid+1 ▪ 重复上述操作，直至low>high时，查找失败
一、 第八章查找解析 4、折半查找怎么进行的。 ■问：在(12,23,26,37,54,60,68,75,82,96)个元素中 查找96需要比较几次？ 01234 6789 12232637546068758296 low=0 mid=4 high=9 low=5 mid=7 high=9 8=lo'high=9 mid=8 找到，比较4次mid=9☐ low=hight=9 www.open.ha.cn 8
www.open.ha.cn 一、第八章查找解析 ▪ 4、折半查找怎么进行的。 ▪ 问：在(12,23,26,37,54,60,68,75,82,96)个元素中 查找96需要比较几次？ 12 23 26 37 54 60 68 75 82 96 0 1 2 3 4 5 6 7 8 9 mid=4 mid=7 low=0 high=9 low=5 high=9 mid=8 8=lo w high=9 找到，比较4次 mid=9 low=hight=9
一、 第八章查找解析 ·4、折半查找怎么进行的。 ·折半查找判定树若把查找过程中每次比较的位置 对应树中的一个结点，则查找过程就是一颗二叉 搜索树，也是一颗理想平衡二叉树。 判定树的根结点的值是查找表的中间元素的下标； ■ 左子树的结点是关键字小于中间元素的左子表， 左子树的根结点是左子表的中间元素的下标； ·右子树的结点是关键字大于中间元素的右子表， 右子树的根结点是右子表的中间元素的下标； www.open.ha.cn
www.open.ha.cn 一、第八章查找解析 ▪ 4、折半查找怎么进行的。 ▪ 折半查找判定树若把查找过程中每次比较的位置 对应树中的一个结点，则查找过程就是一颗二叉 搜索树，也是一颗理想平衡二叉树。 ▪ 判定树的根结点的值是查找表的中间元素的下标； ▪ 左子树的结点是关键字小于中间元素的左子表， 左子树的根结点是左子表的中间元素的下标； ▪ 右子树的结点是关键字大于中间元素的右子表， 右子树的根结点是右子表的中间元素的下标； ▪ …………
一、 第八章查找解析 ·4、折半查找怎么进行的。 构造判定树的方法是逐次取序列和子序列中间记 录的下标。 0123 4 567 89 12232637546068758296 4=(0+9)/2 54 元素一定时，判定树是唯一的。 对n个元素查找时，比较次数为： 1=(043)/2 7=(5+9)/2 23) 5 5=5+6/2h=Llog2nJ+1或h=「log2(n+1)] 0 2生(2+3)/2 2 60 5 8=(8+9)/2 在等概率条件下，成功查找的平 26 82 均查找长度ASL: （1+2*2+3*4+4*3)/10=2.9 3 6 9 ⑦ 68 (96 www.open.ha.cn
www.open.ha.cn 一、第八章查找解析 ▪ 4、折半查找怎么进行的。 ▪ 构造判定树的方法是逐次取序列和子序列中间记 录的下标。 54 23 12 26 37 75 60 68 82 96 0 1=(0+3)/2 2=(2+3)/2 3 4=(0+9)/2 5 6 7=(5+9)/2 8=(8+9)/2 9 5=(5+6)/2 12 23 26 37 54 60 68 75 82 96 0 1 2 3 4 5 6 7 8 9 元素一定时，判定树是唯一的。 对n个元素查找时，比较次数为： h=log2n+1 或h= log2 (n+1) 在等概率条件下，成功查找的平 均查找长度ASL： （1+2*2+3*4+4*3）/10 = 2.9
一、 第八章查找解析 ■ 5、分块查找怎么进行的。 ■适用条件：分块有序表。 算法实现 （1)要对索引表进行查找以确定给定值所在的块 由于索引表有序，则可用顺序查找，也可用折半 查找。 (2)在该块中查找给定的值，由于块内不一定有 序，所以要用顺序查找。 www.open.ha.cn ⑦
www.open.ha.cn 一、第八章查找解析 ▪ 5、分块查找怎么进行的。 ▪ 适用条件：分块有序表。 ▪ 算法实现 （1）要对索引表进行查找以确定给定值所在的块， 由于索引表有序，则可用顺序查找，也可用折半 查找。 （2）在该块中查找给定的值，由于块内不一定有 序，所以要用顺序查找