36顺序查找算法及程序实现课件.ppt

1、36 顺序查找算法及程序实现顺序查找算法及程序实现1查找查找查找是一种查询数据的技术，其目标是能以比较少的步骤查找是一种查询数据的技术，其目标是能以比较少的步骤或较短时间内找到所需的对象。程序将按照查找的结果或较短时间内找到所需的对象。程序将按照查找的结果(找到或找到或未找到未找到)来决定接着应执行的步骤。查找的方法很多，对不同的来决定接着应执行的步骤。查找的方法很多，对不同的数据结构有不同的查找方法。参加选考的同学，只需要掌握顺数据结构有不同的查找方法。参加选考的同学，只需要掌握顺序查找和对分查找两种方法。序查找和对分查找两种方法。2顺序查找算法顺序查找算法顺序查找的基本思想是从第一个数据开

2、始，按顺序逐个将顺序查找的基本思想是从第一个数据开始，按顺序逐个将数据与给定的数据数据与给定的数据(查找键查找键)进行比较，若某个数据和查找键相进行比较，若某个数据和查找键相等，则查找成功，输出所查数据的位置；反之，输出未找到。等，则查找成功，输出所查数据的位置；反之，输出未找到。顺序查找算法的处理过程顺序查找算法的处理过程假定在数组假定在数组d中有中有n个数据，查找键已经存储在变量个数据，查找键已经存储在变量key中。中。其处理过程是：从数组其处理过程是：从数组d的第的第1个元素个元素d(1)开始，依次判断各元素开始，依次判断各元素的值是否与查找键的值是否与查找键key相等，若某个数组元素相

3、等，若某个数组元素d(i)的值等于的值等于key，则结束处理则结束处理(找到了指定的数据找到了指定的数据)；若找遍了所有的；若找遍了所有的n个元素，无个元素，无任何元素的值等于任何元素的值等于key，则结束处理，则结束处理(输出未找到信息输出未找到信息)。顺序查找算法流程图顺序查找算法流程图3顺序查找算法的程序结构顺序查找算法的程序结构程序实现代码：程序实现代码：k0 For i1 To n If a(i)key Then ki Next i If k0 Then 输出查找成功输出查找成功 Else 输出查找不成功输出查找不成功 End If 本节的学习要求掌握顺序查找算法的基本思想，能本节的

4、学习要求掌握顺序查找算法的基本思想，能用程序来实现顺序查找的算法。考查方式为选择题与填用程序来实现顺序查找的算法。考查方式为选择题与填空题。空题。1为找自己第一次上幼儿园时的照片，小张同学依次翻开自为找自己第一次上幼儿园时的照片，小张同学依次翻开自己的多本相册来逐张查找。这种查找方法为己的多本相册来逐张查找。这种查找方法为 ()A无序查找无序查找 B顺序查找顺序查找C对分查找对分查找 D随机查找随机查找B B 2由由10个数组成的数列：个数组成的数列：25、36、45、87、96、84、71、65、99、27，从中查找数据，从中查找数据36时，最适合的查找方式是时，最适合的查找方式是 ()A随

5、机查找随机查找 B顺序查找顺序查找 C对分查找对分查找 D模糊查找模糊查找B B3英文字典中的单词是按字母英文字典中的单词是按字母ASCII从小到大排列的，习惯从小到大排列的，习惯上将这种排法叫做字典排列。要在字典中快速查找某一个上将这种排法叫做字典排列。要在字典中快速查找某一个单词单词(如如Best)的解释，下列最适合的查找方法是的解释，下列最适合的查找方法是()A顺序查找顺序查找 B对分查找对分查找C倒序查找倒序查找 D随机查找随机查找B B 4某数组有某数组有7个元素，依次分别是个元素，依次分别是11、25、37、48、56、62、69，若采用顺序查找法在该数组中查找数据，若采用顺序查找

6、法在该数组中查找数据25，需，需要查找的次数是要查找的次数是 ()A1 B2 C3 D4B B 5在数组在数组23、41、54、26、84、52、65、21中查找数字中查找数字52，采，采用从后往前顺序查找，需要查找的次数是用从后往前顺序查找，需要查找的次数是()A2次次 B3次次 C7次次 D1次次B B 6.某校在进行新生录取工作时，建立了一个数据库，某校在进行新生录取工作时，建立了一个数据库，共有共有650位新生位新生(没有重名没有重名)的记录，现需要找出某的记录，现需要找出某个学生是否已经报名参加该校的暑期军训。个学生是否已经报名参加该校的暑期军训。Private Sub Comman

7、d1_Click()Dim search As Integer,Stu As String search 0 Stu Text1.Text For i 1 To 650 If Stu a(i)Then _ Exit For End If Next i If search 0 Then MsgBox“找到该学生，在数组位置：找到该学生，在数组位置：”Str(search)Else mxgbox“找不到该学生找不到该学生”End IfEnd Sub 已知在一个事件过程中已经完成已知在一个事件过程中已经完成650个学生的数据录入，学生姓名个学生的数据录入，学生姓名信息存放在数组信息存放在数组a(1

8、to 650)中，中，Command1_Click事件过程完成了事件过程完成了在对象在对象Text1中输入学生姓名后，中输入学生姓名后，在在Label1中输出查找结果。程序中中输出查找结果。程序中画线部分应填入画线部分应填入_，该程序，该程序主要采用了主要采用了_算法。算法。Search=i顺序查找顺序查找7现在的学业水平考试都进行网上报名，小李设计了一个现在的学业水平考试都进行网上报名，小李设计了一个模拟查询的程序，实现查询某位考生已经报考的科目信模拟查询的程序，实现查询某位考生已经报考的科目信息。设数组息。设数组zkh用来存放学生的报名序号，数组用来存放学生的报名序号，数组name和和bm

9、k分别存储对应考生的姓名和已报考科目信息。程序分别存储对应考生的姓名和已报考科目信息。程序运行界面如下图所示：运行界面如下图所示：输入报名序号与考生姓名，若报名序号存在且考输入报名序号与考生姓名，若报名序号存在且考生姓名输入正确，则显示考生已报考科目信息。生姓名输入正确，则显示考生已报考科目信息。部分代码如下所示：部分代码如下所示：Private Sub Command1_Click()Dim i As Integer,s As Integer Dim z As String,n As String,k As String z Text1.Text n Text2.Text For i 1 T

10、o n If Name(i)Then s i Exit For End If Next i If s 0 Then Label3.Caption “该考生已报考的科目是：该考生已报考的科目是：”Else msgbox“找不到该考生找不到该考生”End IfEnd SubPrivate Sub Form_Load()考生报名序号、姓名和报考科目数组赋值部分，忽略考生报名序号、姓名和报考科目数组赋值部分，忽略End Sub(1)该程序采用的算法是该程序采用的算法是_。请将划线处的语句或表达式填充完整。请将划线处的语句或表达式填充完整。(2)划线处应填入划线处应填入_。(3)划线处应填入划线处应填入

11、_。顺序查找算法顺序查找算法bmk(s)z=zkh(i)And n8要求从某一字符串中删除指定的字符要求从某一字符串中删除指定的字符(假设所含的英文字假设所含的英文字母均为小写字母母均为小写字母)，并将处理后的字符串重新输出。，并将处理后的字符串重新输出。程序界面如图所示，在文本框程序界面如图所示，在文本框Text_1中输入原始字符串，在中输入原始字符串，在文本框文本框Text_2中输入需要删除的字符，单击中输入需要删除的字符，单击“删除此字符删除此字符”按按钮钮(Command1)后，在文本框后，在文本框Text_3中输出处理后的结果。中输出处理后的结果。注：该示例程序在素材文件夹下注：该示

12、例程序在素材文件夹下vb31文件中。文件中。解决此问题的算法流程图如图所示，相应的解决此问题的算法流程图如图所示，相应的Visual Basic程序如下：程序如下：Dim p As String,k As StringPrivate Sub Command1_Click()Dim s As Integer,result As String,flag As Boolean result “”p Text_1.Text k Text_2.Text For s 1 To Len(p)flag f(s)If Not flag Then result result End If Next s End S

13、ubFunction f(s As Integer)As Boolean If Mid(p,s,1)k Then f TrueEnd Function(1)解决此问题的算法是解决此问题的算法是_(选填：顺选填：顺序查找或对分查找序查找或对分查找)在程序和划线处，填入适当的语句或表在程序和划线处，填入适当的语句或表达式，把程序补充完整。达式，把程序补充完整。(2)程序中划线处应填入程序中划线处应填入_。(3)程序中划线处应填入程序中划线处应填入_。顺序查找顺序查找Mid(p,s,1)Text_3.Text=result9普源为晚上的班级联欢会设计了一个抽奖程序，将所有普源为晚上的班级联欢会设计了

14、一个抽奖程序，将所有同学的编号和对应的姓名分别保存在数组同学的编号和对应的姓名分别保存在数组a(全班共全班共50个个同学，编号为同学，编号为1到到50)和数组和数组b中，程序会随机产生一个中，程序会随机产生一个1到到50的正整数的正整数(同时包括同时包括1和和50)，作为中奖编号。，作为中奖编号。程序界面如图所示，左边列表框程序界面如图所示，左边列表框List1中显示同学的编号中显示同学的编号和姓名，单击和姓名，单击“抽奖抽奖”按钮按钮(Command1)，在标签，在标签Label3中显示抽中的编号，同时在标签中显示抽中的编号，同时在标签Label4中显示中显示“恭喜恭喜*同学同学”，其中具体

15、同学的姓名从数组，其中具体同学的姓名从数组b中获取。中获取。解决此问题的程序段如下：解决此问题的程序段如下：Dim a(1 To 50)As IntegerDim b(1 To 50)As StringFunction search(m As Integer)As Integer search 0 For i 1 To 50 If m a(i)Then search a(i)End If Next iEnd FunctionPrivate Sub Command1_Click()Dim c As Integer,t as Integer Randomize Label3.Caption Str

16、(c)t search(c)If t 0 Then Label4.Caption “恭喜恭喜”“同学同学”End IfEnd SubPrivate Sub Form_Load()此过程用于对数组此过程用于对数组a和数组和数组b进行初始赋值，代码略进行初始赋值，代码略End Sub(1)函数函数search中所用的算法是中所用的算法是_。在程序和划线处，填入适当的语句或表达式，在程序和划线处，填入适当的语句或表达式，把程序补充完整：把程序补充完整：(2)程序中划线处应填入程序中划线处应填入_。(3)程序中划线处应填入程序中划线处应填入_。顺序查找算法顺序查找算法c=Int(Rnd()*50+1)

17、b(c)10.学校的每个学生卡卡号都是唯一的，卡内记录学学校的每个学生卡卡号都是唯一的，卡内记录学生的个人信息。下列程序的功能是：在文本框生的个人信息。下列程序的功能是：在文本框Text1中输入捡到的学生卡卡号，单击中输入捡到的学生卡卡号，单击“查找查找”按钮按钮Command1，查找失主的信息，并在标签，查找失主的信息，并在标签Label3中中显示。部分显示。部分VB程序代码如下所示：程序代码如下所示：定义存放卡号的数组定义存放卡号的数组a，存放学生卡卡号，存放学生卡卡号定义存放学生信息的数组定义存放学生信息的数组b，存放学生个人信息，存放学生个人信息Private Sub Command1

18、_Click()Const n 1000 Dim i As Integer,f As Integer Dim x As String,s As String x f 0 For i 1 To n If Then f i Exit For End If Next i If Then Label3.Caption “该学生是该学生是”Str(b(i)Else Label3.Caption “没有该卡号没有该卡号”End IfEnd Sub在程序划线处，填入适当的语句或在程序划线处，填入适当的语句或表达式，把程序补充完整：表达式，把程序补充完整：(1)程序中划线处应填入程序中划线处应填入_。(2)程序中划线处应填入程序中划线处应填入_。(3)程序中划线处应填入程序中划线处应填入_。Val(Text1.text)x=a(i)f0