数据结构基础知识07--高考信息技术一轮，二轮复习 数据结构基础知识（浙教版2019）

数据结构基础知识（七） 【知识要点】 1.查找的概念和基本方法 （1）查找的概念：查找又称检索，计算机根据所给条件查找出满足条件的对象，即在存储的一批数据内寻找出一个特定的数据，或者确定在该批数据内是否存在这样的数据。若没有找到满足条件的对象，则返回特定值，表明查找失败；若查找到满足条件的对象，则表明查找成功，一般要求返回该对象的存储位置或对象值本身。查找是一种查询数据的技术，其目标是能以较少的步骤或在较短的时间内找到所需的对象。程序将按照查找的结果（找到或未找到）来决定接下来应执行的步骤。 （2）查找的基本方法：查找的方法很多，对不同的数据结构有不同的查找方法。例如，对已排好序的数据序列，可采用对分查找；对树形结构数据，可采用树形查找；无论数据序列是否有序，都可采用顺序查找。 2.顺序查找算法的基本思想 顺序查找的基本思想是从第一个数据开始，按顺序逐个将数据与给定的数据（查找键）进行比较，若某个数据和查找键相等，则查找成功，输出所查数据的位置；反之，输出未找到。 3.顺序查找算法的代码实现 （1）顺序查找本质上是一种枚举算法思想，顺序查找程序就是用循环来枚举所有要查找的对象，然后在循环体内用条件判断当前枚举出的对象是否等于查找对象。 （2）假设 n 个数据依次存储在长度为 n 的数组 a 中，查找键为 key，自定义函seq_search(a,key)返回数组 a 中首个值为 key 的元素下标，若找不到 key 则返回-1 def seq_search(a,key): for i in range(len(a)): if a[i]==key: return i else: return -1 4.二分查找算法的基本思想 （1）二分查找又称对分查找，是一种效率很高的查找方法但被查找的数据序列必须是有序的。 （2）首先将查找键与有序数组内处于中间位置的元素进行比较，如果二者相等，则查找成功；否则根据数组元素的有序性，确定应该在数组的前半部分还是后半部分继续查找。在新确定的范围内，继续按上述方法进行查找，直到查找成功或确定找不到（查找空间为空）。 5.二分查找算法的代码实现 （1）假设n个递增数据依次存储在长度为n的数组a中，查找键为key，自定义函数binary_search(a,key)返回数组a中某个值为key的元素下标，若找不到key则返回-1。 def binary _search(a,key): L,R=O,len(a)-1 while L<=R: m=(L+R)//2 #左偏 #m=(L+R+1)//2 #右偏也可 if key==a[m]: return m elif key<a[m]: R=m-1 else: L=m+1 return -1 (2)二分查找算法也可以使用递归函数bsearch(a,L,R,key)来实现,其中L和R分别表示查找区间的左、右边界,参考代码如下: def bscarch(a,L,R,key): if L>R: return -l m=(L+R)//2 #左偏 #m=(L+R+1)//2 #右偏也可 if key==a[m]: return m elif key<a[m]: return bsearch(a,L,m-1,key) else: return bsearch(a,m+1,R,key) 6.二分查找最优解问题 （1）问题特征 被查找的数据（满足条件的解）必须是有序的；不仅仅要找到满足条件的解，而且要找到最优解，因此不能中途跳出循环，而是要等到循环正常结束后才能确认找到的解为最优解。根据最优解在序列中的位置，可分为查找满足条件的最小值或最大值问题。 （2）基本模型 ①已知数组 a[0:n]为非递减有序序列，输出第一个不小于key的元素下标，若 a[n-1]<key，则输出 n。可推广到求满足条件的最小值问题。 ②已知数组 a[0:n]为非递减有序序列，输出最后一个不大于 key 的元素下标，若 a[0]>key，则输出-1。可推广到求满足条件的最大值问题。 7.二叉排序树 （1）二叉排序树也称为二叉查找树，这种结构的二叉树既能实现排序功能，也能实现查找功能。 （2）二叉排序树的特性 ①若它的左子树非空，则左子树上所有节点的值均小于它的根节点的值。 ②若它的右子树非空，则右子树上所有节点的值均大于它的根节点的值。 ③左，右子树本身又各是一棵二叉排序树。 （3）典型的二叉排序树图示 在该二叉排序树的基础上插入数据值为6的新节点,则得到新的二叉排序树如图。 【例题剖析】 例1：在数组a中存储的数据依次为“3，6，5，11，15，20，13，32”。现使用顺序查找算法在数组a中查找数据20，共需查找的