第 4 章
4.1
4.1.1
常用算法及其程序实现
算法和数据结构
算法的概念
首先， 给出算法一个广义的定义： 为解决一个实际问题而采取的方法和步骤称为 “算法” (Algorithm)，或称“算法”是问题 方法的描述。其实，日常生活中有许多算法的例子。 比如到商场购物，基本的方法与步骤是: 挑选商品、询问价格、交款提货。每一个基本步骤 又可以细分为若干个子方法和步骤， 比如在挑选商品时， 会挑选商品的规格、 色彩和功能等。 购物者的大脑根据商品的情况与事先预定的条件进行判断并完成购物的过程， 实际上就是在 实现 “购物”问题的算法。对类似于购物的许多事情，人们已经非常熟悉，常常意识不 到要首先“设 法” ，但这个过程却是普遍存在的。 同理， 要用 机解决某个实际问题， 就需要为 机设计好 该问题的方法和步骤， 而且这个方法和步骤要符合 机运算的特点和能力， 这就是计算机算法。 要把算法 “告诉” 给计算机， 就需要编写能描述该算法的 机程序， 即程序是用程序设计语言对算法的实现， 是一种计算机可以识别、接受的算法的描述形式，所以，在设计计算机算法时，不但要考虑 算法的可执行性（能够被执行）和执行的有限性（能够在有限个执行步骤中得到运算结果） ， 还要考虑其是否易于利用程序设计语言来实现。而对于程序的优劣，则要通过它的有效性、 通用性、可读性和可维护性等来判定。其中有效性表示其运行时的高效率；通用性表示其对 同类问题的适应能力； 可读性和可维护性则表示当程序在运行中产生故障时， 或计算要求发 生局部改变时，能及时、方便地修正或修改程序。 通常，根据所处理的对象和用途可将算法分为两大类：数值算法和非数值算法。数值算 法主要解决科学计算问题，例如求方程的根、求函数的定积分等。非数值算法则要解决广泛 存在的各类管理问题，例如信息检索、信息分类管理和决策支持、判定等。
4.1.2
算法描述
常用的算法描述方法有：自然语言描述、流程图描述和程序设计语言描述等。 用自然语言描述算法，虽然通俗易懂，但文字冗长，书写不便，特别是文字的“二义性” 会导致描述不清，因此在实际的程序设计工作中并不采用。 流程图是一种直观易懂的描述方法。 该方法用一些规定的框图、 流程线和框图中的说明 文字、算式等来表示各种类型的操作与步骤，既符合计算机程序的特点，又比较容易理 掌握。在第2章中我们已经看到了一些它的应用。 利用程序设计语言描述算法是我们本课程的学习目的， 因为只有它才是计算机可以接受 并执行的算法描述。在第 2 章中通过学习程序的基本结构（顺序、分支和循环） ，我们已看 到了一些算法的程序描述，本章将继续学习利用程序设计语言描述算法的方法。
4.1.3
数据结构概念
一些对人来讲看似十分简单的问题，比如按从小到大的次序排列读入的 10 个任意数， 用计算机实现却并不是容易的事， 要编程实现这些算法就要学习和掌握支持实现这些算法的
基本工具。其中主要是掌握算法语言所提供的语句和它所支持的数据结构。 关于语句，主要是掌握它们的语法规则和语句功能的应用，对此，我们通过第 2 章的学 习已经具有不少的经验和理 本节仅介绍数据结构的基本概念。 数据结构包括数据的逻辑结构和存储结构： 逻辑结构描述数据之间的位置和次序关系，比如一个简单变量，没有左邻和右舍，是一 个完全独立的量；但一维数组中的元素，则除了第一个元素前没有元素，最后一个元素后没 有元素外，其它的所有元素之前和之后都有相邻的元素和确定的位置关系。 存储结构则描述数据在 机存储器中的存放形式和次序关系。 由于 机的存储器单 元都是顺序编号的，所以任何数据在 机内都是以一列（或行）的形式存放的。如何把一 个复杂的数据集合，如两维数组中的数存放到 机存储器中，就有着多于一种的可能。但 不同的存储形式 了不同的数据存取操作，所以一种存储形式也就 了一组可能的运 算。本章将主要学习数组结构的基本知识和应用。
4.2
数组及其它数据类型的定义和应用
前面所使用的字符串、数值型、逻辑型等数据类型都是简单类型，通过一个命名的变量 来存取一个数据。 然而在实际应用中经常要处理同一性质的成批数据， 有效的办法是通过数 组来 。
4.2.1
数组的概念
1. 引例 例 4.1 若我们要求一个班 100 个学生的平均成绩，然后统计高于平均分的人数。按以 前简单变量使用和循环结构相结合，求平均成绩程序段如下： aver=0 for I=1 to 100 mark=inputbox(“请输入每位学生的成绩”) aver=aver+mark next I aver=aver/100 但若要统计高于平均分的人数，则无法实现。因为存放学生成绩的变量名 mark 是一个 简单变量，只能存放一个学生的成绩。在循环体内输入一个学生的成绩，就把前一个学生的 成绩冲掉。 若要统计高于平均分的人数， 必须再重复输入 100 人的成绩。 这样带来两个问题： 其一，输入数据的工作量成倍增加；其二，若本次输入的成绩与上次不同，则统计的结果不 '。 若要保存 100 个学生的成绩，按简单变量的使用，必须逐一命名为 mark1，mark2，… mark100；要输入 100 个学生的成绩，则要写 100 句输入语句；要计算平均分或其他的处理， 则程序的编写工作量将更难以承受，由此引入了数组。 用数组解决求 100 人的平均分和高于平均分的人数，程序代码如下： Private Sub Form1_Load(ByVal sender As System.Object, _ ByVal e As System.EventArgs) Handles MyBase.Load Dim mark(99) As Integer '数组声明，mark数组有100个元素 Dim aver!, overn%, I% aver = 0

下一页