第三单元 查找算法.ppt

技术 技术 第三单元　查找算法 夯实考点 考点1　顺序查找 1.查找算法 所谓查找就是在指定的数据中寻找某一特定的数据。 查找结果有两种,找到(查找成功)和未找到(查找失败)。 2.顺序查找的基本思想 从第一个数据开始,从左往右(或从上到下)将数据按顺序逐个与给定的关键字进行比较,若某个数据和给定的关键字相等,则查找成功,找到并输出第一个与关键字相等的数据的位置;反之,查找失败。若有n个数,则可能的最多查找次数为n。 3.顺序查找算法基本框架 假设:要查找的数为key,待查找的数存放在数组d中。 For语句框架: 　　For i=1 to n 若d(i)=key,则表示找到,做相应处理 　　Next i 若in表示未找到 Do While语句框架: 　　i=1 　　Do while i=n 　　　　若d(i)=key,则表示找到,做相应处理 　　　　i=i+1 　　Loop 若in表示未找到 4.顺序查找的程序实现 在n个数组元素中依次查找,找到第1个满足条件的值,查找即结束,输出找到元素所在的位置;若找不到,输出“未找到”。 程序实现: 设:(1)要查找的数据是key(在文本框Text1中输入),查找的数据存放在数组 d中。 (2)pos为找到数的位置,pos=0表示未找到。 (3)p记录查找的次数。 key=Val(Text1.Text)　Val要根据实际情况决定是否要添加 　p=0 　pos=0 　find=False　find=False表示未找到,find=True表示找到 　i=1 　Do While i=n And find=False　表示还没找完并且还未找到,则继续查找,not find也可表示为find=False 　　　p=p+1 　　　If key=d(i) Then 　　　　pos=i 　　　　find=True 　　　End If 　　　i=i+1 　Loop 　If find Then 也可表示为If find=True Then 　　Text2.Text=在d(+Str(pos)+)中 　Else 　　Text2.Text=未找到 　End If 典例1 某查找算法的部分VB代码如下: t=False i=0 Do While i7 And t = False 　　i=i+1 　　If a(i)=key Then t=True Loop If t=False Then i=0 数组元素a(1)到a(7)的数据依次为“3,5,1,5,8,9,5”,当变量key值为5时,运用该算法处理后,变量i的值是(　　) A.0 B.2 C.4 D.7 解析:本题主要考查的是顺序查找的实现过程。本程序的功能是查找数组中第一个与目标数据相等的数,若找到将其在数组中的位置赋给变量i,结束查找;若找不到,变量i=0。因为目标值key=5,它和数组中第二个数正好相等,因此i=2。 答案:B 典例2 编写一个VB程序,实现如下功能:在列表框List1中显示十个字符串,十个字符串存放在数组s中,在文本框Text1中输入一个字符串,单击“统计”按钮,统计字符串出现的次数,若出现次数大于0,则在文本框Text2中显示实际次数,若出现次数为0,则在文本框Text2中显示“找不到”。 程序运行效果如图3-1所示。 为实现上述功能,请在程序划线处填入合适的语句: 程序①处语句为　 ;? 程序②处语句为　 ;? 程序③处语句为　 。? 解析:要查找的字符为st,st通过文本框Text1中输入得到,因此①处语句为Text1.Text;将要查找的字符串按顺序与数组s中元素比较,如果相等,则进行计数,因此②处语句为s(i)=st;根据题目“若出现次数大于0,则在文本框Text2中显示实际次数,若出现次数为0,则在文本框Text2中显示“找不到”。可知③处的语句为num0或num0。 答案:①Text1.Text　②s(i)=st　③num0或num0 典例3 某6位学生的学号存储在数组元素a(1)到a(6)中,其数据依次为“2015001,2015003,2015078,2015010,2015788,2015666”。使用顺序查找算法查找学号2015700,则共需查找次数为(　　) A.0 B.5 C.6 D.7 解析:本题考查的是顺序查找算法的实现过程。由于给定的数组中没有 数据2015700,因此需要与数组中每个数进行比较,因此共需查找次数为 6次。