资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,2.4,查找,2.4.1,什么是查找,查找(search)是一种查询数据或信息的技术，其目标是能以比较少的步骤或较短的时间找到所需的对象。查询的方法很多，对不同的数据构造有不同的查找方法。例如，对以排序好的固定规模的数据序列进展查找时，其方法有对分查找等；对某些简洁的构造的查找，可用树型查找方法等等。查字典、查资料是我们常常进展的查找工作，在这里，是以在程序的某个数组变量中存储的一批数据内，查找出特定的一个数据，或者确定在该数组内无这样的数据，作为查找的目的。通常，程序将依据查找的结果(找到或未找到)来预备执行后面的哪个计算步骤。,2.4.2,顺序查找,1、观看挨次查找的处理过程,假定被查找的数据如8个存储在有8个元素的数组变量 d 中，要查找的数据这个数据称为查找键已经存储在变量 key 中。,挨次查找算法的输入输出说明,输入：查找键设在变量 key 中。,被查找的数据设在数组变量 d 中。,输出：假设找到，结果是，值为 key 的数据所在的数组元素的下标。,未找到，结果是，0。,开始,i1,i=N？,ii+1,结束,Y,N,N,di=key？,Y,未找到，输出结果：0,找到，输出结果：i,2、挨次查找算法流程图,m=0,key=Int(InputBox(“请输入要查找的数据，即查找键key值：“,“对数组d进展挨次查找“,0),i=1,Do While i=8,If d(i)=key Then,MsgBox“找到，数组下标值是：“&i,0,“挨次查找“,m=1,Exit Do,End If,i=i+1,Loop,If m=0 Then,MsgBox“未找到，结果是：“&m,0,“挨次查找“,End If,3、挨次查找算法的VB编程代码(以规模为8的数组d举例),建立循环构造,从第一个元素开头遍历，逐个检验是否与查找键相等。,2.4.3,对分查找,1、观看对分查找的处理过程,假定被查找的数据如16个存储在有16个元素的数组变量 d 中，并且，数组 d 是有序的已经按非递减次序排列。要查找的数据这个数据称为查找键已经存储在变量 key 中。参考P38图2.22,对分查找算法的输入输出说明,输入：查找键设在变量 key 中。,被查找的数据设在有序数组变量 d 中。,输出：假设找到，结果是，值为 key 的数据所在的数组元素的下标。,未找到，结果是，0。,对分查找的根本方法是：在查找范围i，j内，可以利用数据的有序性，而不必逐个数据地进展查找，进展简洁地计算后，可得到查找范围的中点位置，并使用变量如m，记录这个中点位置。,把查找范围i，j的中点位置上的数据 dm 与查找键 key 进展比较，结果必定是如下三种状况之一：,1 key dm 查找键大于中点处的数据 dm 。依据与1类似的理由，必需在新的范围m+1，j中连续查找。,因此，除了消逝状况2，在通过一次比较后，新的查找范围大约是原查找范围的一半。,举例观看图2.22对分查找过程中查找范围的变化。,2,5,7,8,15,17,22,25,37,42,55,67,72,75,87,92,d,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,i,m,j,第1次：初值 i1，j16，m8，key22,因 keydm，故i，m范围不存在值为key的数据。,因key=22，dm=8,对分查找过程中查找范围的变化,2,5,7,8,15,17,22,25,37,42,55,67,72,75,87,92,d,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,i,m,j,第3次：i5，j7，m6，key22,i=m+1=4+1=5,int(i+j)/2)=int(5+7)/2)=6,因 keydm，故i，m范围不存在值为key的数据。,对分查找过程中查找范围的变化,因key=22，dm=17,2,5,7,8,15,17,22,25,37,42,55,67,72,75,87,92,d,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,i，j，m,第4次：i7，j7，m7，key22,i=m+1=6+1=7,int(i+j)/2)=int(7+7)/2)=7,因 dm=key 故输出：“找到，数组下标值是：”&m,对分查找过程中查找范围的变化,因key=22，dm=22,对分查找过程中查找范围的变化,2,5,7,8,15,17,22,25,37,42,55,67,72,75,87,92,d,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,i,m,j,2,5,7,8,15,17,22,25,37,42,55,67,72,75,87,92,d,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,i,m,j,2,5,7,8,15,17,22,25,37,42,55,67,72,75,87,92,d,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,i,m,j,2,5,7,8,15,17,22,25,37,42,55,67,72,75,87,92,d,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,i，j，m,P38图2.22对分查找过程中查找范围的变化,2、对分查找算法的流程图,使用对分查找算法在具有n个数据的数组变量d中查找key时，因事先并不能确定比较的次数，但可以通过条件来把握重复是否连续进展。每进展一次比较后，当状况1(key dm)消逝即尚未找到key时，应把原查找范围的一半作为新的查找范围，在这个新的范围内连续查找key。但这是需要前提的，即新的查找范围内必需至少有一个数据。由此得到的连续进展重复的条件是：,查找范围i，j中的数据个数,j-i+10,即,i=j,开始,i1,j n,im+1,结束,N,N,dm=key,Y,未找到，输出结果：0,找到，输出结果：m,i=j,计算中点：m INT(I+j)/2),dm key,jm-1,N,Y,Y,i=1:j=n:b=0,Do While i=j,m=Int(i+j)/2),If d(m)=key Then,b=1,Text2.Text=“找到，数组下标值是：“&m,Exit Do,ElseIf d(m)key Then,i=m+1,Else,j=m-1,End If,Loop,If b=0 Then,Text2.Text=“未找到，结果是：“&b,End If,3、对分查找算法的VB编程代码(以规模为n的数组d举例),对分查找是先取中间元素和查找键比较，假设不相等则缩小近一半的查找范围，在剩下的元素中连续查找。,循环初始值,实践体验,现代化学的元素周期律是1869年俄国科学家门得列夫(Dmitri Mendeleev)首创的，他将当时的63种元素依原子量大小并以表的形式排列，把有相像化学性质的元素放在同一行，就是元素周期表的雏形。利用周期表，门得列夫成功的猜测当时尚未觉察的元素的特性(镓、钪、锗)。1913年英国科学家莫色勒利用阴极射线撞击金属产生X射线，觉察原子序越大，X射线的频率就越高，因此他认为核的正电荷预备了元素的化学性质，并把元素依照核内正电荷(即质子数或原子序)排列，经过多年修订后才成为当代的周期表。,在周期表中，元素是以元素的原子序排列，最小的排行最先。表中一横行称为一个周期，一列称为一个族。,1、主题参考教材P39,查找原子序数。,2、要求,元素周期表是化学学习中常常要使用的，通过查阅元素周期表，我们可以知道元素名称、元素符号、原子序数及原子量等信息。现在要求构建一个数组，按原子序数存放对应元素的元素符号。试设计一个算法，使得输入元素符号后，就能快速查找到对应的原子序数。,小结,1、把握查找的概念；,2、挨次查找是依据数组元素的先后次序，从第一个元素开头进展遍历，逐个检验是否和查找键相等。,3、对分查找的前提是待查找的数据是有序的。对分查找是先取中间的元素和查找键比较，假设不相等则缩小近一半的查找范围，在剩下的元素中连续查找。,4、对分查找的效率远高于挨次查找。,5、在数组中的查找结果，假设找到，输出结果是，值为 key 的数据所在的数组元素的下标；假设未找到，输出结果是，0。,
展开阅读全文