11.1 实验目的及实验条件 11.1.1 实验目的 第 11 章算法与程序设计实验 本实验单元的内容是 算法与程序设计实验, 包括查找算法 排序算法 递归算法等, 所选择的编程软件 / 环境为 Microsoft Visual Basic 6.0, 本实验单元的目的如下 : 1. 训练程序设计与利用算法求解问题的思维, 训练程序设计与算法技能 2. 掌握结构化程序设计, 掌握利用 Visual Basic 语言进行结构化程序设计 ; 3. 掌握基本数据结构, 如数组的使用, 掌握利用 Visual Basic 语言操作数组 ; 4. 掌握程序调试能力, 能够利用 Visual Basic 调试程序, 包括设置断点 观察变量值 单步执行等 ; 5. 深入理解典型算法, 具备 ( 利用 Visual Basic) 实现典型算法的能力 ; 6. 掌握 Visual Basic 语言控件数组的使用 ; 7. 深刻理解全局变量与局部变量, 掌握全局变量与局部变量的合理运用 ; 8. 掌握用户界面设计能力 11.1.2 实验条件 1. 中央处理器 CPU: Intel 双核 2.0GHz 以上 ; 2. 内存 RAM: 2 GB 以上 ; 3. 硬盘 :320G 以上 ; 4. 操作系统 :Microsoft Windows XP 或 Windows 7; 5. 开发工具 :Microsoft Visual Basic 6.0 企业版 ( 含 MSDN 帮助 ) 11.2 实验项目及任务 本实验单元设置如下实验项目 : 项目 11-1: 查找算法程序设计 ; 项目 11-2: 排序算法程序设计 ; 项目 11-3: 递归算法程序设计 ; 项目 11-4: 四则运算计算器程序设计 ; 11.2.1 实验项目一 : 查找算法程序设计 本实验项目中, 应完成如下任务 : 1. 任务 1: 进入 Visual Basic 编程环境, 新建一个标准应用程序 ; 2. 任务 2: 利用控件或控件数组建立程序的输入输出界面, 要求设计的界面简洁 美观, 控件要对齐, 布局合理, 控件的大小 字体等协调, 便于操作 ; 3. 任务 3: 或者利用输入对话框 (InputBox) 输入数据 ; 4. 任务 4: 建立数组, 将从界面获取的输入数据存入数组 ; 5. 任务 5: 编制查找算法 ( 遍历查找 / 二分查找 ) 程序, 依据输入的查询信息查找并显示 ; 6. 任务 6: 运行程序, 测试程序是否如预想的工作 下面给出一些具体查找任务 :
2 大学计算机实验 给定一组数字, 查找其中的最大值和最小值 ; 给定一份成绩单 ( 姓名 成绩 ), 查找最高分 最低分及获得最高分 最低分的学生姓名 ; 给定一份电话簿 ( 姓名 电话号码 ), 查找某人的电话号码或某电话号码对应的姓名 ; 给定一份电话簿 ( 姓名 电话号码 ), 根据姓名的片段信息, 如姓或名字中的一两个字, 查找出姓名和电话号码 ( 可能有多个 ) 11.2.2 实验项目二 : 排序算法程序设计 本实验项目中, 应完成如下任务 : 1. 任务 1: 进入 Visual Basic 编程环境, 新建一个标准应用程序 ; 2. 任务 2: 利用控件或控件数组建立程序的输入输出界面 ; 3. 任务 3: 或者利用输入对话框 (InputBox) 输入数据 ; 4. 任务 4: 建立数组, 将从界面获取的输入数据存入数组 ; 5. 任务 5: 编制排序算法程序, 对输入的数据排序并显示 ; 6. 任务 6: 运行程序, 测试程序是否如预想的工作 ; 7. 任务 7: 设置断点并以调试方式执行程序, 观察变量值 ; 8. 任务 8: 以单步执行方式执行程序, 观察变量值 下面给出一些具体排序任务 : 任意输入 n 个数, 对其按照从小到大的顺序排序, 以逗号分隔的形式输出结果 ; 由左至右设置 n 个文本框, 随机输入 n 个数, 对其按照从小到大的顺序排序, 然后按此顺序将其重新显示在自左至右的 n 个文本框中 ; 随机输入 n 个数, 对其按照从小到大的顺序排序, 并动态显示排序算法的执行过程和结果 11.2.3 实验项目三 : 递归算法程序设计 本实验项目中, 应完成如下任务 : 1. 任务 1: 进入 Visual Basic 编程环境, 新建一个标准应用程序 ; 2. 任务 2: 利用控件建立程序的输入输出界面 ; 3. 任务 3: 编制递归算法程序, 计算并显示结果 ; 4. 任务 4: 利用程序调试手段观察递归程序的运行过程, 观察函数如何调用自身 ; 5. 任务 5: 试着利用循环结构编写程序, 以达到与递归程序相同的效果 可编制下列程序 : 任意输入正整数 n, 求 n!, 显示结果 ( 要求利用递归程序实现 ) 任意输入正整数 n, 以此计算并输出 1!,2!,3!,4!, 直至 n! ( 要求利用递归程序实现 ); 汉诺塔程序 11.2.4 实验项目四 : 四则运算计算器程序设计 本实验项目中, 应完成如下任务 : 1. 任务 1: 分析并设计四则运算计算器的功能 ; 2. 任务 2: 进入 Visual Basic 环境, 新建一个标准应用程序 ; 3. 任务 3: 利用控件或控件数组建立四则运算计算器的界面 ; 4. 任务 4: 定义四则运算计算器程序的全局变量 ;
第 11 章算法与程序设计实验 3 5. 任务 5: 书写四则运算计算器程序的代码 ; 6. 任务 6: 调试并使程序运行 ; 7. 任务 7: 测试四则运算计算器程序的正确性, 即带小数点的加减乘除功能 ; 8. 任务 8: 完善程序, 保证运算器不允许输入具有两个小数点的数 11.3 基础知识 数组 : 在程序设计中, 为了处理方便, 把具有相同类型的若干变量按有序的形式组织起来 这些按序排列的同类数据元素的集合称为数组 全局变量 : 也称为外部变量, 是在函数的外部定义的, 它的作用域为从变量定义处开始, 到本程序文件的末尾 全局变量全部存放在静态存储区, 在程序开始执行时给全局变量分配存储区, 程序行完毕就释放 局部变量 : 在程序中, 只在特定的过程或函数中可以访问的变量, 是相对与全局变量而言的 在 Visual BASIC 中, 有些变量在整个应用程序中有效 ( 称全局变量 ), 有些变量在窗体内有效 ( 称窗体变量 ), 还有些变量只在对应的程序段中有效 ( 称局部变量 ) 查找 / 搜索 : 日常生活中, 我们往往需要从大量的数据中寻找需要的信息, 我们称之为搜索 (Search) 在计算机中进行搜索, 则需要事先把这些数据输入到计算机中, 并按一定的结构对其进行存储, 然后才能对其进行搜索 遍历搜索 : 最基本的搜索策略是逐个检查数据结构中的每个元素, 直到找到所要找的, 即遍历策略, 或称穷举搜索 二分查找 : 将要查找的数据集从中间位置一分为二, 判断要查找的数据属于其中的哪一个集合 ; 然后对新的集合再一分为二进行判断, 这样逐步缩小范围直到找到为止 因为该算法策略是每次将新的搜索范围缩小到原范围的二分之一, 因此称为二分查找或折半查找 排序 : 是生活中一类常见的问题, 排序实质上就是把一组数据按照递增或递减的顺序排列起来 冒泡排序算法 : 依次对数组中相邻的两个数据进行比较, 将大的放前, 小的放后, 经过一轮比较移位后, 数组中最小的元素就会被找到, 并被放到数组的尾部 ; 然后再对剩余数组中剩余的数据按上述过程进行比较移位, 经过 N-1( 数组长度减 1) 次后, 数组中的数据就被排序了 由于上述算法的排序过程类似气泡上升的过程, 因此该算法被称为冒泡排序算法 递归 (Recursion): 子程序对自身进行调用 递归算法能够把一个大型复杂的问题层层转化为一个本质与原问题相同而规模较小的问题来求解, 而且只需少量的程序代码就可描述出解题过程所需要的多次重复计算 11.4 相关软件介绍 本实验单元所使用的编程软件同实验单元 10, 相关软件介绍见 10.4 节 11.5 实验操作指导 本节对本实验单元的实验提供指导 需要注意的是, 这里只对部分实验提供具体的 答案性的指导, 其他实验项目学生参考这些操作指导即可完成 11.5.1 冒泡排序算法的程序实现及调试 1. 界面设计 (1) 建立一个新的项目文件, 一个名为 Form1 的窗体 (2) 在窗体上添加控件, 包括两个 Frame(Frame1 Frame2), 四个 Lable(Lable1 Lable2 Lable3
4 大学计算机实验 Lable4), 两个 Command(Command1 Command2), 利用 Visual Basic 提供的对齐 布局等功能调整控件的位置, 使之对齐并美观, 结果如图 11.1 所示 图 11.1 创建窗体和控件 (3) 更改控件设置, 实现结果如图 11.2 所示 图 11.2 冒泡排序程序的界面设计 2. 代码与调试 (1) 容易出现的错误 : 用循环实现数组遍历的时候, 容易出现数组下标越界的情况 程序代码如图 11.3 所示, 运行程序, 单击 排序 按钮会出现错误, 提示是 下标越界
第 11 章算法与程序设计实验 5 图 11.3 数组下标越界, 程序运行出错界面单击 调试, 则会在代码的相应位置以黄色背景提示, 如图 11.4 所示 图 11.4 数组下标越界的代码错误提示修改双重 for 循环的范围, 将循环计数器 i 和 j 的上界设为 8, 运行程序, 单击 排序, 则排序后的最终结果如图 11.5 所示
6 大学计算机实验 图 11.5 程序修改后的运行结果 (2) 设置断点调试程序 : 当程序没有明显的错误但运行结果却不符合预期时, 需要利用调试手段分析程序, 这种过程称为调试 调试的一个常用手段是设置程序运行的断点, 即程序运行到断点所在语句后暂停, 你可以查看并分析变量的值, 然后使之继续运行 设置方法是用鼠标左键单击代码行的左侧, 则会出现一个紫红色的圆点, 同时此行代码的背景也变为紫红色 对一个方法或程序可以设置多个断点, 如图 11.6 所示 当运行程序的时候, 程序执行到断点处会停下, 可以查看程序中的变量目前的值 例如, 当程序执行到第一个断点处, 程序的执行停止, 将鼠标放置在变量 i 处, 就会显示当前 i 的值为 0, 如图 11.6 所示 图 11.6 断点调试示意 (3) 单步调试 : 单步调试是另一种常用的程序调试手段, 支持编程人员逐条语句运行程序, 监测变量值的变化, 从而修正程序中的问题 操作方法是单击 调试 菜单, 出现下拉菜单后选
第 11 章算法与程序设计实验 7 择 逐语句, 如图 11.7 所示 Visual Basic 也提供了 逐过程 运行到光标处 等调试手段 图 11.7 单步调试示意在对程序进行逐语句调试的时候, 编译器会对程序代码的执行过程进行提示, 使程序执行到的当前代码行的背景变为黄色, 并有箭头标出 此时, 可以查看程序中各个变量的当前值, 如图 11.8 所示 图 11.8 单步调试并查看变量值 (4) 运行结果 : 经过上面几步, 将程序调试好后, 运行程序, 则会出现图 11.9 所示的排序结果
8 大学计算机实验 11.5.2 四则运算计算器的程序实现 图 11.9 冒泡排序程序的运行结果 1. 计算器功能 (1) 按下数字键, 在液晶屏上会出现数字, 这是最基本的功能 (2) 第一次按下运算键, 再按下数字键, 将重新输入第二个数字 ; 再次按下运算键, 将算出前两个数的结果, 接着再按数字键, 将又开始新数字的输入 (3) 输入数字后, 按下 等于 键, 仍输出原来的数字 ; 输入运算符和第二个数字后再按下 等于 键, 将得到二者的结果 然后重复第二 三步 (4) 按下 清除, 数据被全部清除 2. 界面设计 (1) 建立一个新的项目文件, 里面包含一个名为 Form1 的窗体 (2) 添加控件, 包括一个标签框 (Lable1), 一个 Text 框 (Text1), 和 17 个按钮 其中, 17 个按钮采用控件数组的方法建立, 具体操作为 : 先在窗体上建立一个按钮 (Command1), 选中 Command1, 执行复制 (Copy); 在窗体上任意部位单击右键, 选择粘贴 (Paste), 系统会提示是否创建控件组, 选择 是 ; 重复上面步骤, 直至创立完 17 个按钮为止如图 11.10 所示 该控件数组的特点是 17 个按钮使用的名称都是 Command1, 只是 Index 属性不同
第 11 章算法与程序设计实验 9 图 11.10 创建控件数组 (3) 按表 11.1 设置各控件的属性值, 设置完成后进行屏幕布局, 调整各控件的位置与对齐关系, 使之形成图 11.11 所示的窗体 图 11.11 计算器界面 表 11.1 计算器例子中的控件对象属性设置值 对象 属性 设置值 对象 属性 设置值 窗体 Caption 四则运算计算器 Caption 7 按钮 8 Left 0 Index 7 按钮 1 Caption 0 Caption 8 按钮 9 Index 0 Index 8 按钮 2 Caption 1 Caption 9 按钮 10 Index 1 Index 9 按钮 3 Caption 2 Caption 按钮 11 Index 2 Index 10 按钮 4 Caption 3 按钮 12 Caption =
10 大学计算机实验 对象 属性 设置值 对象 属性 设置值 Index 3 Index 11 按钮 5 Caption 4 Caption + 按钮 13 Index 4 Index 12 按钮 6 Caption 5 Caption - 按钮 14 Index 5 Index 13 按钮 7 Caption 6 Caption 按钮 15 Index 6 Index 14 文本框 Text1 0 Caption 按钮 16 Multiline False Index 15 标签 1 Caption 关于 Caption 清除按钮 17 Index 16 3 编写代码 ( 注意属性设置要与表 11.1 一致 ) (1) 在 Form1 的通用声名区里声明窗体级全局变量, 这些变量在整个窗体的所有函数中都可以访问和赋值, 具体方法, 在代码窗口左侧对象列表框中选择 通用, 则光标自动定位在通用声名区里, 如图 11.12 所示 Dim Num1, Num2 As Single ' 表示第 1 个操作数和第 2 个操作数 Dim StrNum1, StrNum2 As String ' 表示第 1 个操作数字符串和第 2 个操作数字符串 Dim FirstNum As Boolean ' 判断是否是数字开头 Dim PointFlag As Boolean ' 判断是否已有小数点 Dim Runsign As Integer ' 保存输入的运算符号 Dim SignFlag As Boolean ' 判断是否已有运算符号 图 11.12 在窗体通用声名区里声明窗体级全局变量 (2) 在 Form_Load 事件里给变量赋初始值, 对窗体级全局变量进行初始化 如图 11.13 所示 图 11.13 在 Form_Load 事件里给变量赋初始值 (3) 选定控件数组中的任意一个按钮对象, 在其 Click 事件中输入下列代码 : Private Sub Command1_Click (Index As Integer) Select Case Index Case 0 To 9 ' 处理按数字按钮 0~9 的情况 If FirstNum Then ' 如果是数字开头 StrNum1 =Str(Index) ' 实型转换为字符型 FirstNum = False ' 初赋值为假 Else ' 非初赋值
第 11 章算法与程序设计实验 11 StrNum1 = StrNum1+Str(Index) End If Text1.Text = StrNum1 ' 显示 Case 10 If Not PointFlag Then ' 如果没有小数点 If FirstNum Then ' 如果是第一个字符 StrNum1 = "0." FirstNum = False Else StrNum1 = StrNum1 + "." End If Else ' 已有小数点 Exit Sub ' 则退出单击事件 End If PointFlag = True Text1.Text = StrNum1 Case 12 To 15 FirstNum = True ' 使下一次可以输入新数据 PointFlag = False ' 还原标记值 If SignFlag Then ' 前面已有运算符未运算 Call RunCal Else SignFlag = True StrNum2 = StrNum1 ' 把字符串 1 复制给字符串 2 StrNum1 = "" ' 字符串 1 清空 End If Runsign = Index ' 保存键入的运算符 () Case 11 ' 等号按钮 If Not SignFlag Then Text1.Text = StrNum1 equal = Val(StrNum1) FirstNum = True PointFlag = False Else Call RunCal SignFlag = False End If Case Else ' 清除按钮, 初始化所有变量 Num1 = 0 Num2 = 0 StrNum1 = "" StrNum2 = "" FirstNum = True PointFlag = False Runsign = 0 SignFlag = False Text1.Text = "0." End Select End Sub (4) 在本段程序中用了一个过程 RunCal, 建立过程 (Procedure), 可以在 Form1 的 General 部分直接输入, 也可以通过菜单里的 Add Procedure 添加 RunCal 的代码如下, 如图 11.14 所示 :
12 大学计算机实验 (5) 保存程序 11.6 思考题 图 11.14 编写过程 RunCal 的代码 11.1 四则运算计算器程序中, 控件数组的作用是什么? 如果不使用控件数组, 能否实现? 11.2 全局变量和局部变量有什么区别? 为什么不把所有的变量设为全局变量? 11.3 数组这种数据结构在什么情况下使用? 11.4 Visual Basic 提供了哪几种调试手段? 他们各有什么作用? 11.5 递归算法计算 n! 程序中, 观察当 n 多大时, 程序运行过程中出现溢出错误, 为什么? 11.6 递归算法和循环 / 迭代算法有什么相同点和异同点? 11.7 四则运算计算器程序中, 各个全局变量有什么作用? 11.8 实验项目四与本单元其他实验项目相比较, 有什么特点? 11.9 事件驱动的程序设计与结构化程序设计的区别有哪些? 试举例说明之 11.10 观察某个冒泡排序算法对 n 个数排序时, 执行了多少次比较大小的操作