查找第四节

《查找第四节》由会员分享，可在线阅读，更多相关《查找第四节（4页珍藏版）》请在装配图网上搜索。

1、第四节(教材 5.4)查找算法的程序实现1教学要求理解怎么用VB来实现简单问题的查找算法2教学设计建议 在第二章中我们学习了顺序查找和对分查找的算法，这两种算法相对排序来说要比较容易理 解，在教学设计时，教师可让学生通过自主学习形式完成对分查找算法和顺序查找算法实例 的 VB 程序设计。本节建议用 2 课时，其中学生实践活动的时间应不少于2/3。 教学过程框图如图5.11 所示： 在进行学生自主学习、实践活动之前，教师需讲解清楚界面要求，需要用到哪些设控件、各 控件的属性需要做哪些设置，在编制程序时，应该分析清楚哪个事件发生时完成哪些计算与 处理，通过哪些事件的发生来完成整个程序功能。各个控件

2、属性值的设置可参考下表。 参考控件属性表控件 属性 属性值 说明Form1 Caption 查找程序 显示程序的功能Command1 Caption 查找 说明命令按钮的作用Text1text空串输入数据Backcolor黄色MultiLineTrue一个数据输入完成后键入回车Text2text空串显示查找的结果Backcolor蓝色MultiLineTrue一个数据输入完成后键入回车Text3text空串显示查找的次数Backcolor蓝色MultiLineTrue一个数据输入完成后键入回车List1BackColor蓝色输出数组 d 中的所有数据Lable1Caption输入查找键说明文本

3、框 text1 的作用Lable2Caption查找的结果说明文本框text2的作用Lable3Caption查找的次序说明文本框text3的作用Lable4Caption数组d中的数据说明列表框List1的作用应用程序的各事件处理过程功能如下：Form_load事件处理过程 1)随机产生一组128个按增序排列整数存储到数组d中 2)将这里128个随机数显示在列表框Listl中。Text1.text_click 事件处理过程1)将各文本框清空，Textl.text、Text2.text、Text3.text置空串，为下一次查找做好准备。Command1_click事件处理过程1)当命令按钮按下

4、时，从Text1.text读取需要查找的键值；2) 调用 Search 函数开始进行查找；3) 在文本框Text2.text输出查找的结果；4) 在文本框Text3.Text输出查找次数。Search 函数 1)按顺序查找或对分查找算法进行查找；2) 若找到，返回查找键值所在的位置值，未找到，返回0adj函数 美化输出的显示函数在这儿，数组d和查找次数nc在多个事件处理过程都要用到，要定义为全局变量。 随机数的产生函数 RND 需要讲解清楚，它是一个伪随机函数，能随机产生一个01 之间的 实数，使用时，必须在程序中加入一条Randomize Timer语句，才能保证每次运行产生的随 机数不同，

5、否则从第二次开始，每次执行程序所产生的随机数都与第一次产生的完全相同 Timer()函数返回一个Single类型的值，代表从午夜开始到现在经过的秒数。课本中使用Fix(Timer() Mod 67+13*Rnd(),可使程序每次运行时产生的随机数都不相同。但是Fix(Timer() Mod 67+13*Rnd()的产生值有可能为0,这样就有可能在数组中存在两个相同的键值，在对 分查找时没法保证键值唯一性，所以适当修改一下语句 dv=dv+ Fix(Timer() Mod 67+13*Rnd() 为dv=dv+ Fix(Timer() Mod 67+13*Rnd()+1就可以了。在顺序查找时，如

6、果有键值相同的情况， 则返回第一个找到的位置即可。查找程序参考的用户界面如下：图 5.12 对分查找与顺序查找比较 顺序查找的参考代码如下：Dim d(1 To 128) As Integer定义全局变量数组d,查找次数ncDim nc As IntegerFunction adj(a As String, n As Integer) As String美化输出的显示函数Dim sa As Stringsa = a: na = Len(a)For i = 1 To n - nasa = + saNext iadj = sa将字符串a转化为长度为n的字符串，不足时候在前面补足空格End Func

7、tionFunction search(k As Integer) As Integer 顺序查找算法Dim pos As IntegerFor i = 1 To 128nc = nc + 1If d(i) = k Then pos = i: Exit For 依次查找，找到第一个相同的值，查找到就结束Next isearch = pos返回找到的位置, 未找到时返回 0End FunctionPrivate Sub Command1_Click()Dim k, pos As Integerpos = search(Val(Text1.Text) 将寻找结果存入 pos， 0 表示找不到If

8、pos = 0 Then Text2.Text =找不到Else Text2.Text =在 d( + Str(pos) + )中Text3.Text = ncnc = 0为下一次查找做好准备End SubPrivate Sub Form_Load()For i = 1 To 128d(i) = Fix(Timer() Mod 67 + 13) * Rnd * 10)使用 timer()使程序每次重新运行 List1.AddItem adj(Str(i), 3) + : + adj(Str(d(i), 6)时产生的随机数不一样Next iEnd SubPrivate Sub Text1_Cli

9、ck()Text1.Text = 为下一次查找做好准备Text2.Text = Text3.Text = End Sub对分查找与顺序查找的界面设计相同，控件属性设计可参考表 5.4.1，算法流程图可参见书 本图 2.4.4，程序代码与顺序查找不同在于： 1随机数的产生要保证是增序，不能有重复键值。修改 Form_load 代码如下：Private Sub Form_Load()Dim dv As Integerdv = 2For i = 1 To 128dv = dv + Fix(Timer() Mod 67 + 13) * Rnd) + 1 随机产生递增序列的整数 d(i) = dvLis

10、t1.AddItem adj(Str(i), 3) + : + adj(Str(d(i), 6)Next iEnd Sub2. Search函数的处理算法不一致，在对分查找时，把查找范围(i, j)的中间位置上的数据d(m)与查找键key进行比较，1) 若keyd(m),查找键大于中点处的数据d(m)，由于数据是按递增排列的，因而在新范围 (m+1, j)中继续查找；3) key=d(m)，找到了需要的数据；对分查找的 search 函数代码如下：数Function search(key As Integer) As Integer对分查找算法Dim pos, i, j As Integeri

11、 = 1: j = 128: nc = 0Do While i = jnc = nc + 1m = Fix(i + j) / 2)If d(m) = key Then search = m: Exit FunctionEnd IfIf key d(m) Then计算(i，j)的中间位置，进行折半查找找到，返回在数组中的序号判断在下半部分，还是在下半部分Fix(x)函数的功能是取不大于x的最大整数j = m - 1ElseEnd IfLoopsearch = 0返回结果 0，表示未找到End Function 其它代码同顺序查找，可参考顺序查找代码部分。对分查找的前提是键值已经进行排序，它 的查

12、找速度很快，无论是否查找到，最多进行L|og2 （N+1）次查找，Liog2（N+1）表示对它 进行下取整，即大于等于的log2N的最小整数，而顺序查找在最坏情况下（找不到或者在最 后一个），查找的次序需要N次，最好情况是1次（在第一个），平均查找次数N/2。关于学生实践活动实施建议 顺序查找和对分查找都作为学生实践活动的内容，由学生通过自主学习来完成，对界面设计 的要求和Timer（）函数、Rnd（）函数的功能和特性教师要讲解清楚，并提供适当帮助。在活动评价时，可根据界面设计合理情况及测试数据执行情况进行评价，评价指标可参照书 本的要求进行，也可参照下面评价表的指标进行。参考评价指标表活动主

13、题评价指标（活动满分 6 分）顺序查找测试数据产生正确、查找结果全正确、界面设计合理6 分测试数据产生、查找结果比较正确、界面设计正确5 分测试数据产生、查找结果有部分正确（如未找到情况处理） 3 分 算法表达正确，但程序无法运行或结果错 2 分对分查找 测试数据产生正确、查找结果全正确、界面设计合理 6 分 测试数据产生、查找结果比较正确、界面设计正确5 分测试数据产生、查找结果有部分正确（如未找到情况处理） 3 分 算法表达正确，但程序无法运行或结果错 2 分3. 练习题解答及补充练习：（1）使用对分查找，查找目录J时，会查经H、L,查找乙会查经H、L、N,最后查找z 未找到。（ 2）1）查找Gene：对分查找快，对分查找3次，顺序查找6次2）查找Alice:顺序查找快，顺序查找1次，对分查找4次3）查找Bruce:对分查找快，对分查找4次，顺序查找8次4）查找Sue：对分查找快，对分查找4次，顺序查找8次5）使用顺序查找Floyd，查找了 5个数据，使用对分查找，查问了 1个数据 （3）使用对分查找最多查问 log25001 个数据，使用顺序查找最多查问 5000 次，所以对分查找效率比较高。