第5章计算机软件开发

第5章计算机软件开发

骆耀祖制作

本章学习目标

本章介绍了程序设计的一些基本术语和

原理。通过本章的学习，读者应该掌握

计算机的程序设计基础、程序语言的数

据类型、基本控制结构，算法与数据结

构、程序设计语言与翻译系统、知道软

件工程方法。本章重点是结构化程序设

计，理解面向对象及其应用场合；理解

软件开发和软件工程的概念。

5.7程序设计基本概念

黎人们用以同计算机“交谈”的语言，称之计算

机语言O

器计算机每做的一次动作，一个步骤，都是按照

已经用计算机语言编好的程序来执行的，程序

是计算机要执行的有序指令的集合，而程序全

部都是用我们所掌握的语言来编写的。所以人

们要控制计算机一定要通过计算机语言向计算

机发出命令。

«计算机所能识别的语言只有机器语言。

5.7.7程序设计语言概述

般人们把需要计算机做的工作写成一定形式的指

令，并把它们存储在计算机内存中，让计算机

按顺序自动执行。这种可以连续执行的计算机

指令的集合被称为“程序”。程序实际上是用

计算机语言描述的对某一问题的解决步骤，而

编制程序就是为计算机安排指令序列。

龄人与计算机之间交流信息必须使用人和计算机

都能理解的程序设计语言。计算机程序设计人

员可以选择各种各样的程序设计语言或程序开

发工具来开发软件。

直

接

机器语言（由和构成的代码）〕对

01硬

件

计算机语言<汇编语言（英文缩写的助记符）操

作

高级语言

1、采用比较接近人们习惯的自然语言

2、具有很大的通用性（即不受具体机器指令的约束）

3、面向算法编写程序

5.7.7程序设计语言概述

耶迄今为止，程序设计语言有超过几百种之多，程序设

计语言可以分为五大类：机器语言、汇编语言、第三

代语言3GL(ThirdGenerationLanguage)>第四代语言

(4GL)和第五代语言(5GL)。而这些语言又可以分为低

级语言和高级语言。

®低级语言是一种面向机器的语言，它们对计算机硬件

的依赖程度很高。一种面向机器的语言只能运行在某

种专门的计算机上。用机器语言编制的程序不能被移

植到其它计算机上。机器语言和汇编语言都是低级语

R。

«高级语言是一种非面向机器的语言。用高级语言编制

的程序可以运行于多种不同类型的计算机和操作系统

之上。第三代、第四代和第五代语言都是高级语言。

1.机器语言

®每个计算机系统都有一套自己的指令系统，指

令系统中的每一条指令就称为机器指令，而机

器指令的集合就称为机器语言。机器语言由二

进制代码。和1组成，二进制代码。和1对应于计

算机中电信号的两种状态，如电位的高和低、

电流的有或无、电容的充电或放电等。因此，

计算机能识别二进制表示的机器指令，并能直

接执行机器指令。

器一般来说，机器指令由操作码和操作数两部分

组成。操作码告诉计算机进行什么样的操作，

操作数是将要被操作的对象。有时，操作数也

可以用地址码来表示，地址码告诉计算机到什

么地方去取操作数。

有机器语言的优点是可以被计算机直接理

解和执行，执行速度快，且占用内存少。

缺点是面向机器，通用性差。它要求程

序设计人员熟练掌握计算机的全部机器

指令，且要求对计算机硬件结构有很好

的了解。用机器语言编写的程序可读性

很差，不易于调试和维护。

2.汇编语言

给汇编语言是第二代程序设计语言。在汇编语言

中，人们采用了有助于记忆的符号（称为指令

助记符）来表示机器指令中的操作码和地址码。

指令助记符是一些有意义的英文单词的缩写和

符号。例如，汇编语言中采用英文单词的缩写

和符号等来表示操作码。如用ADD表示加法

（addition）、用SUB表示减法（subtract）、

用MOV表示数据的传送（move）、用JMP表示

程序的跳转（jump）等等。而操作数可以直接

用十进制数书写，地址码可以用寄存器名、存

储单元的符号地址等表示。

«用汇编语言编写的程序称为汇编语言源程序。因为计

算机只能识别用二进制代码表示的机器指令，而不能

识别汇编语言源程序中的指令助记符。因此必须将由

汇编语言编写的源程序翻译成由机器语言组成的目标

程序，这个程序就叫做汇编程序，而这个翻译的过程

就叫做汇编。汇编程序的工作过程如图5.1所示。

辨与机器语言相比，汇编语言有许多优点，程序设计人

员可以用汇编语言写出语句少、质量高、执行速度快

的程序。但是，汇编语言仍是一种面向机器的语言，

通用性差。它要求程序设计人员对计算机的硬件结构

如计算机的指令系统、CPU中寄存器的结构及存储器

单元的寻址方式等等有较详细的了解，并且要求程序

设计人员具有较高的编程技巧。

汇编语言程序-------土-------1

»机器语言程序

源程序汇编目标程序

0%

3.高频语言

❷事实上，高级语言包括了第三代、第四

代、第五代语言，但本小节所说“高级

语言”主要是指第三代语言。

<>高级语言是一种接近人的自然语言和数

学语言的程序设计语言。它易学易用，

并且不依赖于计算机硬件系统。用高级

语言编写的程序不但表达直观，可读性

好，而且与具体机器无关，便于移植，

通用性好。

«高级语言是按照一定的“语法规则”，由表达各种不

同意义的“关键字”和“表达式”组成。例如，用

PRINT表示显示，用数学运算符表示加号，用

表示乘号等。这些用英语单词表示的关键字和数学符

号简化了程序设计人员开发应用程序的过程。

®高级语言摆脱了具体机器的指令系统，不再依赖于机

器，它们是面向算法过程的语言。用过程化语言编程，

不但要告诉计算机“做什么”，还要告诉计算机“怎

么做”。用高级语言编程时，程序设计人员可以应用

自顶向下的程序设计方法及结构化的程序控制结构

（顺序结构、选择结构、循环结构）来开发程序。在

程序中，无论是主程序还是过程子程序，其程序结构

只能由三种基本结构（顺序结构、选择结构、循环结

构）嵌套而成

4.第四代语言(4GL)

器第四代语言比第三代语言更接近于人的自然语

言，它是一种非过程化的语言。用非过程化语

言编程时，只需告诉计算机“做什么”，而无

需告诉计算机“怎么做”，即无需编写“怎么

做”的实现模块，语言的具体操作过程由计算

机系统自动完成。使用非过程化语言只需要说

明所要完成的加工和条件，给出输入数据并指

明输出形式，就能得到所需结果。(但是必须

指出，“怎么做”的实现模块仍然是用传统语

言来开发的。)第四代语言简单易学，易于使

用。用第四代语言编程省时省力，用户无需很

多程序设计知识就能开发应用程序。

懿许多第四代语言主要应用于数据库领域。结构

化查询语言SQL(StructuredQueryLanguage)

就是第四代语言的代表。SQL是目前非常流行

的用于关系型数据库的符合ANSI标准的第四代

语言。SQL被作为关系型数据库管理系统的标

准语言，它具有数据查询、数据定义、数据操

纵和数据控制功能，可以用来执行如更新数据

库中的数据，从数据库中提取数据等操作。目

前，大多数流行的关系型数据库管理系统，如

Oracle、Sybase、MicrosoftSQLServer、

Access等都采用了SQL语言标准。

5.第五代语言(5GL)

籍第五代语言是非过程化的语言，它们提

供了可视化的图形界面来生成源代码。

通常第五代语言使用第三代语言或第四

代语言的编译程序来转换得到相应的机

器语言程序。有些面向对象的开发工具

和网页开发工具也属于第五代语言二例

如VisualBasic、VisualC++、Java就属

于第五代语言。

5.7.2高级语言与翻译系统

第通常把用高级语言编写的程序也称为“源程

序”，把用二进制代码表示的程序称为“机器

代码程序”或者“目标程序”。由于计算机只

能识别和执行由二进制代码组成的机器语言，

因此，用高级语言编写的源程序，必须经过一

个“语言处理程序”将它“翻译”成计算机能

够接受的目标程序后，才能被计算机执行。这

种具有翻译功能的语言处理程序可以分为两大

类：编译程序（又称为编译器）和解释程序

（又称为解释器）。

莓(1)编译类：编译是指在应用源程序执行之

前，就将程序源代码“翻译”成目标代码，因

此其目标程序可以脱离其语言环境独立执行。

e现在大多数的编程语言都是编译型的。

图5.2用编译方式执行一个源程序的过程

编译连接计算

辨（2）解释类：应用程序源代码一边由相应语言

的解释器“翻译”成目标代码，一边执行。

器缺点是：效率比较低，而且不能生成可独立执

行的可执行文件，应用程序不能脱离其解释器,

但这种方式比较灵活，可以动态地调整、修改

应用程序。

图5.3用解释方式执行一个源程序的过程

5.1.3程序设计语言的选择

(1)系统用户的要求

如果所开发的系统由用户负责维护，用户通常要求用

他们熟悉的语言书写程序。

(2)可以使用的编译程序

运行目标系统的环境中可以提供的编译程序往往限制

了可以选用的语言的范围。

(3)可以得到的软件工具

如果某种语言有支持程序开发的软件工具可以利用，

则目标系统的实现和验证都变得比较容易。

(4)工程规模

(5)程序员的知识

完全掌握一种新语言需要实践。

(6)软件可移植性要求

如果目标系统将在几台不同的计算机上运行，或者预

期的使用寿命很长，那么选择一种标准化程度高、程序

可移植性好的语言就是很重要的。

(7)软件的应用领域

选择语言时应该充分考虑目标系统的应用范围。

5.2C语言

<>5.2.1C语言简介

黔在C语言诞生以前，系统软件主要是用汇

编语言编写的。由于汇编语言程序依赖

于计算机硬件，其可读性和可移植性都

很差；但一般的高级语言又难以实现对

计算机硬件的直接操作（这正是汇编语

言的优势），于是人们盼望有一种兼有

汇编语言和高级语言特性的新语言。

金七十年代早期，美国贝尔实验室的Dennis

Ritchie研制出了C语言。C语言同时具有汇编语

言和高级语言的优点，其特点是：语言简洁、

紧凑，使用方便、灵活；运算符极其丰富，可

移植性好，可以直接操纵硬件；生成的目标代

码质量高，可移植性好（较之汇编语言），程

序执行效率高。

铅80年代初，美国国家标准化协会（ANSI）,制

定了ANSIC标准（1989年再次做了修订）。目

前，在微机上广泛使用的C语言编译系统有

MicrosoftC、TurboC、BorlandC等。虽然它

们的基本部分都是相同的，但还是有一些差异,

所以请注意所使用的C编译系统的特点和规定。

LC语言程序的总体结构

辨一个完整的C语言程序，是由一个main。函数

(又称主函数)和若干个其它函数结合而成的,

或仅用一个main。函数构版。

爵【例5,1】仅由main。函数构成的C语言程序。

❷/*仅由main。函数构成的C语言程序示例*/

®main()

®{printfCcThisisaCprogram.\n^)；

0)

0程序运行结果为：

金ThisisaCprogram.

【怫a】

■【例5.2】由main。函数和1个其它函数max()

构成的c语言程序。

«intmax(intx,inty)

e{return(x>y?x:y);}

.main()

辨{intnuml,num2;

卷printf(ctInputthefirstintegernumber:");

辨scanf("％d”，&numl);

辨printfC4Inputthesecondintegernumber:9,);

®scanf("％cT,&num2);

®printf("max=%d\rT,max(numl,num2));

籍程序运行情况：

Inputthefirstintegernumber:6一」

Inputthesecondintegernumber:9一」

max=9

龄由上面的程序可知：函数是c语言程序

的基本单位。main。函数的作用，相当

于其它高级语言中的主程序；其它函数

的作用，相当于子程序。

一个C语言程序，总是从main。函数开

始执行，而不论其在程序中的位置。当

主函数main。执行完毕时，亦即程序执

行生毕。习惯上，将主函数main。放在

最前面。

2.函数的一般结构

«任何函数（包括主函数main。）都是由函数说明和函

数体两部分组成。其一般结构如下：

非［函数类型］函数名（函数参数表）函数

说明部分

«｛说明语句部分；

给执行语句部分；函数体部分

辨）

0函数说明由函数类型（可缺省）、函数名和函数参数

表三部分组成，其中函数参数表的格式为：

®数据类型形参［,数据类型形参2……］

522C语言的组成

等1.C语言的数据类型

-C语言的数据类型可分类如下：

金（1）基本类型：分为整型、实型（又称浮点

型）、字符型和枚举型四种。

龄（2）构造类型：分为数组类型、结构类型和共

用类型三种。

船（3）指针类型。

•（4）空类型。

啰C语言中的数据，有常量和变量之分，它们分

别属于上述这些类型。

2,常量和变量

e在程序运行过程中，其值不能被改变的量称为

常量。常量的类型有：整型常量、实型常量、

字符常量和符号常量。常量的类型，可通过书

写形式来判别。

器在程序运行过程中，其值可以被改变的量称为

变量。变量有两个要素：

龄（1）变量名。每个变量都必须有一个名字—变

量名，变量命名遵循标识符命名规则。

龄（2）变量值。在程序运行过程中，变量值存储在

内存中。在程序中，通过变量名来引用变量的

值。

0-WIK-MPIWI-

3.语句

据程序是由一行一行的语句(statement)所

组成的。语句是程序最小的可执行单元,

将这些可执行单元组合起来，可以构成

程序块、子程序、函数、模块、类…等

更高等的可执行单元。

喘语句是由关键字(Keyword)＞标识符

(Identifier)及特殊符号所组成的。

4.关键字

器关键字(Keyword)是由英文字母所组合而

成的，C语言的关键字共有32个，根据关

键字的作用，可分其为数据类型关键字、

控制语句关键字、存储类型关键字和其

它关键字四类。

器关键字又称为保留字，是由C内部定义的,

其用途在指示程序如何运作。其用法C都

有所规定，必须遵循这些规定，否则会

产生错误。

啰（1）数据类型关键字（12个）：char,double,

enum,float,int,long,short,signed,struct,

union,unsigned,void

黔（2）控制语句关键字（12个）：break,case,

continue,default,do,else,for,goto,if,

return,switch,while

能（3）存储类型关键字（4个）：auto,extern,

register,static

龄（4）其它关键字（4个）：const,sizeof,typedef,

volatile

标识符

0除了C预先定义的关键字之外，可以自己定义新字，例

如：Do_It_Yourself>M$、kj…,这些自己定义出来的

字称为标识符。定义标识符时，必须合乎C的规定，C

对于定义标识符的规定如下：

给（1）标识符由英文字母、中文字、数字及下划线构成。

辨（2）标识符的第一个字符必须是英文字母、中文字、或

是下划线，例如以下都是正确的标识符：A、x、CD、

sun、力口油站、_计数器…。

给（3）标识符的第二个以后的字符可以是英文字母、中文

字、下划线或是数字，例如：A钱、每个_500_元、

_520_...o

辨（4）若标识符的第一个字符是下划线（_）,则标识符之

中须含有英文字母、中文字、或数字，例如_、、

—…都不能当作标识符。

6.特殊符号

能C所使用的特殊符号很多，在键盘上，除

了英文字母之外，其它符号C几乎都会使

用到，例如+、一、*、/这几个符号分

别表示算术运算的加减乘除。

j

5.2.3碟程序的语句

辨了解语句的组成元素之后，下面介绍C

语言中常见的语句种类。

给与其它高级语言一样，C语言也是利用

函数体中的可执行语句，向计算机系统

发出操作命令。按照语句功能或构成的

不同，可将C语言的语句分为五类。

a1.空语句

非空语句仅由一个分号构成。显然，空语句什么

操作也不执行。

©2.变量声明语句

器在预设的情况下，程序所使用的可变数据（称

为“变量”（variable））都必须先声明才可以使

用，假设我们想利用X来存放整数类型的数据,

那么须先利用以下语句声明变量X：

®intX;

黔以语句的组成元素来说，语句中的Int是关键字,

而X则是定义的变量的标识符。

辨3.表达式语句

器表达式语句由表达式后加一个分号构成。最典

型的表达式语句是，在赋值表达式后加一个分

号构版的赋值语句。例如，"num=5"是一个

赋值表达式，而“num=5;"却是一个赋值语句。

e在外观上，赋值语句跟数学的方程式类似，例

如：

0X=123;

辞但赋值语句不是数学的方程式。在数学的方程

式中，上面的X及Y称为未知数，而程序语言则

将上面的X及Y称为变量，变量是一个可存放数

据的地方，如图54所示。

图5.4变量与数据的存储

・此变量叫X'

X=123X123此位置存放X的值

舂对“X=123”语句来说，是把等号右边

的数据存放到等号左边的变量X所对应的

存储单元中。这个语句中的号，和

数学上的等号的意义是大不相同的，例

如：A=A+2这个语句在数学上是不成

立的，而在计算机程序里，却是合法的,

相反的，AX2=30这个式子在数学上是

成立的，但是在C程序语言里面却是错误

的，因为在C程序语言里面，号左边

必须是一个变量名称，而不能是算术表

达式。

图5.5X=Y+10的运行过程

(1)取出Y的“值”

②运算2+10=12

1(3)放入X的“地址”

华图5.5表示了“X二丫+10”的运算过

程。

◎因止匕，A=A+2这个语句的含意是：将变量A的

存储单元中所存放的数据取出来加上2之后，

再存回A的存储单元的意思。

4.控制语句

辨控制语句完成一定的控制功能。C语言

只有9条控制语句，又可细分为三种：

0(1)选择结构控制语句

器if()〜else〜，switch。〜

(2)循环结构控制语句

do〜while。，for()〜,while。〜，break,

continue

辨(3)其它控制语句

goto,return

器在C语言中，除实现顺序、选择和循环三

种基本结构的9条控制语句外，输入输出

操作均由标准库函数（不是C语言的组成

部分）来实现。学习C语言，不仅要学习

这9条控制语句和各种运算符，而且要学

习并掌握常用标准库函数的使用。

5.复合语句

辨复合语句是由大括号括起来的一组(也

可以是1条)语句构成。例如：

啰main()

{……

{……}/*复合语句。

注意：右括号后不需要分号。*/

5.2.4函数调用

辨函数调用语句由一次函数调用加一个分

号(语句结束标志)构成。

理例如，printf("ThisisaCfunction

statement,");

龄以上语句会在DOS窗口显示nThisisaC

functionstatement/1这串字，其中printf

是函数名称。

5.3算法与数据结构

图算法与数据结构是计算机程序的两个最基本的

概念。在谈到算法与数据结构二者的关系时，

瑞士著名计算机科学家尼可莱沃思(Nikiklaus

Wirth)在1976年曾提出这样一个公式：

给算法+数据结构=程序

午准确地说，一个程序规定了某个数据结构上的

一个算法。

器算法是程序的核心，它在程序设计乃至在整个

计算机科学中都占据重要地位。

5.3.7算法概述

©计算机解题一般可分解成若干操作步骤。

通常把完成某一任务的操作步骤称为求

解该问题的算法。程序就是用计算机语

言描述的算法。由于组成计算机程序的

基本单位是指令，因此计算机程序就是

按照工作步骤事先编排好的具有特殊功

能的指令序列，其中每条指令表示一个

或多个操作。

籍韦氏新世界词典将“算法”定义为：解

决某种问题的任何专门的方法。

欧几里德算法

<5给定两个正整数力和〃求它们的最大公因子

（即能同时整除力和〃的最大正整数）的步骤

如下：

黎（1）以〃除力并令所得余数为八，必小于〃；

聂（2）若r=0算法结束，输出结果〃，否则继续

步骤3；

老（3）将/7置换为/77,，置换为〃并返回步骤1继

续进行；

为欧几里德算法既表述了一个数的求解过程，同

时又表述了一个判定过程。该过程可以判定刀

和〃是互质的，即除1以外力和〃没有公因子

这个命题的真假。

i.算法的性质

器(1)有穷性：一个算法必须总是(对任何合法的输入

值)在执行有限步之后结束。换言之，任何算法必须

在有限时间内完成。

0而且每一步都可在合理的有穷时间内完成。

器(2)确定性：算法中的每个步骤都必须有明确的定义,

不允许存在多义性和模棱两可的解释。

0(3)能行性：算法中描述的每步操作都应是可执行的。

例如，当B=0时A/B就无法执行，不符合能行性的要

求。

«(4)输入：一个算法必须有0个(自动生成初始数据)

或多个输入。

*(5)输出：一个算法必须产生一个或多个输出信息。

2.算法的描述

辞算法是对解题过程的精确描述。定义解

决问题的算法对程序员来说通常是最具

挑战性的任务，它既是一种技能又是一

门艺术，要求程序员懂得结构化程序设

计概念并具有创造性。对算法的描述是

建立在语言基础之上的。在将算法转化

为高级语言源程序之前，通常先采用文

字或图形工具来描述算法。文字工具如

自然语言、伪代码等，图形工具如传统

流程图、N—S流程图等。

(1)自然语言

席自然语言是人们日常所用的语言，使用

自然语言不用专门训练，所描述的算法

也通俗易懂。然而其缺点也是明显的：

首先是由于自然语言的歧义性容易导致

算法执行的不确定性；其次是由于自然

语言表示的串行性，因此当一个算法中

循环和分支较多时就很难清晰地表示出

来；此外，自然语言表示的算法不便转

换成用计算机程序设计语言表示的程序。

(2)传统流程图

⑤多情况选择型

(CASE型)

③先判定型循环④后判定型循环

(DO-WHILE)(DO-UNTIL)

辨复合语句的性质：

耶(1)在语法上和单一语句相同，即单一语

句可以出现的地方，也可以使用复合语

句。

龄(2)复合语句可以嵌套，即复合语句中也

可出现复合语句。

®ANSI(AmericanNationalStandardsInstitute)

颁布了流程图的标准，这些标准规定了用来表

示程序中各种操作的流程图符号。例如，流程

图只能使用图5,6所给出的五种基本控制结构。

通常，在流程图中用流程线(带箭头的实线)

来连接大部分图框，这些流程线表示了程序的

执行顺序。

等流程图可以很方便地表示顺序、选择和循环结

构，因此可以表示任何程序的逻辑结构。另外，

用流程图表示的算法不依赖于任何具体的计算

机和计算机程序设计语言，从而有利于不同环

境的程序设计。流程图对算法的描述优于其他

语言，直观形象，易于理解，已经为世界各国

的程序设计人员普遍使用。

(3)N—S流程图

PP

A=1=2

BAA

B一

1AlA2........./

①顺序型②选择型

⑤多分支选择理

DQ—阳ILEP

S(CASE型)

S

DO-UNTILP

③WHILE重复型④UNTIL重复型

逑N—S流程图又称为结构化流程图，于1973年

由美国学者I.Nassi和B・Shneiderman提出。

与传统流程图不同，N—S图不用带箭头的流程

线来表示程序流程的方向。采用一系列矩形框

来表示各种操作，全部算法写在一个大的矩形

框内，在大框内还可以包含其它从属于它的小

框，这些框一个接一个从上向下排列，程序流

程的方总是从上向下。如图5.7所示。

:;N—S结构化流程图比较适合于表达三种基本结

构，适于结构化程序设计，因此很受程序员欢

迎。

(4)伪代码

给伪代码，是指不能够直接编译运行的程

序代码，它是用介于自然语言和计算机

语言之间的文字和符号来描述算法和进

行语法结构讲解的一个工具。它表面上

很像高级语言的代码，但又不像高级语

言那样要接受严格的语法检查。它比真

正的程序代码更简明，更贴近自然语言。

它不用图形符号，因此书写方便、格式

紧凑、易于理解，便于向计算机程序设

计语言算法程序过渡。

求解超时工资算法的伪代码

MAINMODULE：〃主模块

CALLinitialization//初始化

CALLProcess〃处理

CALLWrap-UP〃打印输出

END

PROCESSMODULE：〃处理模块

DOWHILENotEOF〃开始循环

CALLReadaRecord〃读入一个记录

CALLCalculate〃计算

CALLAccumulateTotals〃累加到总和

ENDDO

RETURN

令CALCULATEOVERTIMEPAYMODULE：〃计算超时工资模块

IFOvertimeHours>0THEN〃如果超时工作

OvertimePay=OvertimeHours*1.5*PayRate

«〃超时工资=超时小时数*1.5*超时工作每小时报酬

给ELSE〃否则

«OvertimePay=0〃超时工资为0

ENDIF

«RETURN

e【例5.1】求1+2+3+…+100之和，分

别用传统流程图、N—S流程图及自然语

言描述其算法，并将该算法转化为C语言

源程序。

龄设变量x表示加数，y表示被加数。

(a)传统流程图(b)N-S流程图

<W1)采用图形工具描述算法如图5.8所

/pSO

e(2)采用自然语言描述算法如下：

辨将1赋值给X

公将2赋值给R

华将x与y相加结果存放在x中

您将y加1结果存放在y中

有若y小于或等于io。转到步骤3继续执行,

否则算法结束，结果为x

器(3)将上述算法转化为C语言源程序:

给main()

®{intX,Y;

辱X=l;

«Y=2;

®while(Y<=100)

》X=X+Y;

>Y=Y+1;

®printf(n%dn,X);

®I

【例5.2】汉诺塔问题

«印度的一座神庙里，由一个铜座支撑着三根宝

石柱子。在第一根柱子上，按照从大到小的顺

序套放着64个直径大小不一的金盘。现在要

将第一根柱子上的64个盘子借助第二根柱子

全部移到第三根柱子上。在移动时应遵守下面

的规则：

籍1每次只能移动一个盘子。

能2盘子只能在三根柱子上移动，不能放在其他

地方。

靠3在移动过程中，必须始终保持大盘在下，小

盘在上。

器当这64个盘子全部移到第三根柱子上，世界

末日就要到了。这就是著名的汉诺塔问题。

华汉诺塔问题只能用递归方法而不能用其

他方法来求解。所谓递归就是将一个较

大的问题归结为一个或多个比原问题简

单，且在结构上与原问题相同子问题的

求解方法。递归是计算学科中的一个重

要概念。

尊根据递归方法，可以将64个盘子的汉诺塔问

题转化为求解63个盘子的汉诺塔问题。如果

63个盘子的汉诺塔问题能够解决，则可以先

将63个盘子先移动到第二个柱子上再将最后

一个盘子直接移动到第三个柱子上，最后又一

次将63个盘子从第二个柱子移动到第三个柱

子上这样则可以解决64个盘子的汉诺塔问题。

依此类推，63个盘子的汉诺塔求解问题可以

转化为62个盘子的汉诺塔求解问题，62个盘

子的汉诺塔求解问题又可以转化为61个盘子

的汉诺塔求解问题，……直到1个盘子的汉诺

塔求解问题。再由1个盘子的汉诺塔的求解求

出2个盘子的汉诺塔直到解出64个盘子的

河涅性I、吊旦而

靠下面用C语言对该问题的求解算法进行描述:

&hanoi(intn,charleft,charmiddle,charright)

懿if(n==1)move(1,one,three);

0else{

懿hanoi(n-1,left,right,middle);

0move(1,left,right);

&hanoi(n-1,middle,left,right);

•}}

给注：〃表示〃个盘子的汉诺塔问题，left表示第

一个柱子，middle表示第二个柱子，right表

示第三个柱子。函数hanoi(n-1,left,right,middle)

表示n-1阶汉诺塔从第一个柱子借助第三个柱

子先移到第二个柱子上，函数

move(1,left,_,right)表示将第一个柱子上最后一

个盘手直接放到第三个柱子上，函数hanoi(n-

1,middle,left,rignt)表示第n-1个盘子从第二个

柱子借助第一个柱子移到第三个柱子上。

4,算法设计的基本策略思想

卷可以看到：用计算机求解一个实际问题,

首先要从这个问题中抽象出一个数学模

型，然后设计一个解此数学模型的算法,

根据算法编写程序，经过调试、编译、

连接和运行，完成该问题的求解。所谓

从实际问题中抽象出一个数学模型，就

是要用数学的方法抽象其本质的内容，

实现对该问题的正确认识。

靠对大型问题进行算法设计，一般采用

“自顶向下，逐步求精”的方法，把大

问题分解为若干小问题，逐步求精。大

型问题的算法设计，可归纳为六个基本

策略思想。分别为：分割求解法、动态

规划法、子目标法、图的搜索法、回溯

法、分支与界限法。

(1)分割求解法。

❾分而治之的策略思想。它把一个大问题

划分为原问题的较小子问题，先求出各

子问题的解答，然后把各子问题的解答

合并成整个问题的解。因为由分割法产

生的子问题的大小，往往是原问题的较

小规模，因而通常是递归地使用这种方

法。

靠对所有的子问题都进行解答。计算过程

是从小的子问题到较大的子问题，每次

的答案存入一个表格中，作为下面处理

问题的基础。每个子问题的解决依赖于

一系列子问题的结果。如何找出后面的

子问题，要依赖于前面一系列子问题的

递推关系式，这就是动态规划策略的核

心。

（3）子目标法

律就是倒推法。即从某个目标或解出发，

倒推到这个问题的初始陈述。也就是从

某个已知的特定解出发，反过来求这个

解与已知条件之间存在的关系，从而得

到一般解的方法。

(4)图的搜索法

O如果把问题的求解过程用图或树这种结

构来描述，即图中的每一个节点代替问

题的状态，节点间的连线表示某种可操

作的规则，那么问题的求解空间就可由

隐含图来描述。图的搜索方式就是用某

种策略选择可操作的某种规则，并把状

态过程用图结构记录下来，一直到得出

解为止，也就是从隐含图中搜索除含有

解路径的子图来。

①回溯法

器在问题的求解过程中，有时会发现使用某一不

适合的操作会阻挠或延迟到达目标的过程。在

这种情况下，需要有这样的控制策略：先试一

试某一操作，如果以后发现这个操作不适合，

则允许退回去，另选一个操作来进行。这就是

回溯法的控制策略。

0回溯法本质是一种搜索算法，但和图的搜索算

法不同，回溯法在搜索过程中不保存完整的搜

索树的结构，只记住当前工作的一条路径，回

溯就是对这条路径进行修正；图的搜索方式则

在搜索过程中记忆下完整的搜索树。

(6)分支界限法

籍分支界限法的设计策略是：利用分支、

限界的方法构造一棵搜索树，求出搜索

树中每个节点上的实际花费函数，求出

花费函数最大(小)值的那种结构。这

就是说，分支界限法是建立一个局部路

径(或分支)的队列。每次都有限扩展

当前具有最大(小)消耗值分支路径的

端节点n(其估价函数为f(n)=g(n)),直

到生成含有目标节点的路径为止。

5.算法分析

给解一个问题往往有若干不同的算法，这些算法

决定着根据该算法编写的程序性能的好坏。在

保证算法正确性的前提下，如何确定算法的优

劣就是一个值得研究的课题。

给在算法的分析中一般应考虑以下3个问题：

O(1)算法的时间复杂度；

给(2)算法的空间复杂度；

e(3)算法是否便于阅读修改和测试。

等算法时间复杂度是指算法中有关操作次

数，用T(n)表示。丁为英文单词Time的

第一个字母，T(n)中的。表示问题规模的

大小。如在累加乘和中。表示待加数的

个数，在矩阵相加问题中。表示矩阵的

阶数，在图中。表示顶点数等。

舂例如，在上面的汉诺塔问题中，考虑当n=64

时，需要移动多少次，要用多少时间。根据上

面的算法，n个盘子的汉诺塔问题需要移动的

盘子数是n-1个盘子的汉诺塔,问题需要移动的

盘子数的2倍加1于是：

0h(n)=2h(n-1)+1

器=2(2h(n-2)+1)+1=22h(n-2)+2+1

有=23h(n-3)+22+2+1

0=2nh(0)+2n-1+..+22+2+1

0=2n-1+...+22+2+1=2n-1

辞因此要完成汉诺塔的搬迁需要移动盘子的次数

为：

<>264-1=18446744073709551615

酷如果每秒移动一次，也需要花费大约5849亿

年的时间。假定计算机以每秒1000万个盘子

的速度进行搬迁，则需要花费大约58490年的

时间。由此可知，理论上可以计算的问题在实

际上并不一定能行。这是属于算法复杂性方面

的研究内容。

察汉诺塔问题主要讲的是算法的时间复杂性。关

于汉诺塔问题算法的时间复杂度可以用一个指

数函数0(2〃)来表示。显然，当〃很大(如

10000)时，计算机是无法处理的。而在算法

的时间复杂度的表示函数是一个多项式，如

0("2)时则可以处理。

«对于较复杂的算法，应将它分成容易估算的几

个部分后计算整个算法的时间复杂度。最好不

要采用指数级和阶乘级的算法，而应尽可能选

用多项式级或线性级等时间复杂度较小的算法。

另外还要在算法最好、平均和最坏的情况下区

别执行效率的不同。

绘一个问题求解算法的时间复杂度大于多

项式如指数函数时，算法的执行时间将

随。的增加而急剧增长，以致即使是中

等规模的问题也不能求解出来。在计算

复杂性中将这一类问题称为难解性问题。

人工智能领域中的状态图搜索问题、解

空间的表示或状态空间搜索问题就是一

类典型的难解性问题。

e在计算复杂性理论中，将所有可以在多项式时

间内求解的问题称为尸类问题，而将所有在多

项式时间内可以验证的问题称为N尸类问题。尸

类问题采用的是确定性算法，N尸类问题采用

的是非确定性算法。P类问题的算法是N尸类

问题算法的一种特例。

«算法的空间复杂度是指算法在执行过程中所占

存储空间的大小，用S(n)表示。S为英文单词

Space的第一个字母。与算法的时间复杂度相

同，算法的空间复杂度S(n)也可表示为S(n尸「

(g(n))。

532数据结构的基本概念

争数据结构是加工的对象。一个程序要进

行计算或处理，总是以某些数据为对象

的。而要设计一个好的程序就需将这些

松散的数据按某种要求组成一种数据结

构。

卷在讨论数据结构之前，先简单地介绍几

个相关概念。

«1.数据：在计算机科学中，数据是描述客观事物的数

字、字符及所有能输入到计算机中并被计算机程序处

理的符号的集合。

等2.数据元素：组成数据的基本单位称为数据元素。在

计算机程序中通常将数据元素作为一个整体进行处理。

有时，一个数据元素由若干个数据项组成，在这种情

况下，称数据元素为记录。例如，一个学生的基本信

息可以作为一个数据元素，其中的每一项（如学号、

姓名、性别、年龄等）为一个数据项。数据项是数据

的不可分割的最小单位。最简单的数据元素仅含有一

个数据项。

舂3.数据结构：随着计算机应用的不断扩展和深入，计

算机系统处理的数据量越来越大，许多数据并不是相

互孤立的，而是存在着某种相互关系，即某种组织形

式。所以确切地说，数据结构是指数据之间的相互关

系，即数据的组织形式。

冬每种高级语言都会提供若干种数据类型，供用

户在程序设计中直接使用。数据类型可以区分

为简单类型的构造类型两大类。简单类型如整

型、实型、字符型和布尔型，它们仅含有一个

组成成份；构造类型如数组、字符串和记录，

它们都由多个成份来构成。所谓构造类型，其

实就是由高级语言直接提供的预先定义好的数

据结构。而在程序设计中，用户有时必须自行

构造各种较复杂的数据结构。

能任何一种数据类型都是值集合和运算集合的统

一体。当高级语言定义一种数据类型时，它不

仅决定了该类型数据的取值形式与范围，同时

决定了在该类型的数据上所能执行的操作的种

类。所以当使用由高级语言提供的数据类型时,

用户只需了解该类型允许使用的值集，以及在

该类型数据上可以执行的操作集，用不着关心

它们的存储和实现细节。而对于用户自定义的

数据结构，则从结构的建立到各种操作的算法,

全都要由用户自己实现。换句话说，数据结构

本身包含着算法，要通过一定的算法将它建立

或撤消，并实现施加在其上的各种基本操作，

例如插入或删除其中的某个数据成份等。

j

4.数据结构的研究内容

辨数据结构主要是研究程序设计中计算机

所操作的对象以及它们之间的关系和运

算，概括地说是三个方面，即：数据的

逻辑结构、数据的存储结构（或称物理

结构）及数据的运算。

(I)数据的逻辑结构

❾数据的逻辑结构是指数据元素之间的逻

辑关系，它只抽象地反映数据元素间的

相互关系，而不考虑数据在计算机中的

具体存储方式，是独立于计算机的。

器根据元素之间关系的不同特性，数据结

构的一般逻辑结构有：线性结构、树形

结构和图状结构(或称网状结构)。

辱线性结构中的数据元素之间存在一个对一个的

关系。如图5.11(a)所示。一维数组是最简

单的线性结构的例子，堆栈、队列和链表也是

其重要实例。

给树形结构形状如一棵倒置的树。树形结构中的

元素之间存在一个对多个的关系。如图5.11

(O所示。树是非线性结构中最重要的一类

数据结构，应用十分广泛。如果限制树的所有

分枝都不超过两个后继结点，便成了二叉树。

如图5.11(b)所示。

0图状结构中的元素之间存在多个对多个的关系。

任何两个结点之间都可能存在某种联系。如图

5.11(d)所示。图状结构是更为灵活、应用

面也更宽的一类数据结构。

(b)树形结构(d)图状结构

（2）数据的存储结构

«数据的存储结构是指数据在存储器中的存储方

式。数据的存储结构也可以说是逻辑结构在计

算机存储设备上的物理实现，有时也被称为数

据的物理结构。

e数据存储结构的基本组织方式有：顺序存储结

构和链式存储结构。

莓顺序存储结构借助元素在存储器中的相对位置

来表示数据元素的逻辑关系；而链式存储结构

借助指针来表示数据元素之间的逻辑关系，通

常在数据元素上增加一个或多个指针类型的属

性来实现这种表示方式。

rW、N，hIII|*LIIiwrI*41

(3)数据结构的基本运算(操作)

❸・建立数据结构

卷•撤消数据结构

非■插入数据元素。在一个给定的数据结构中，在指定位置上增添

一个新的元素。

等•删除数据元素。对一个给定的数据结构，删除某个指定节点。

0更新数据元素。在一个给定的数据结构中，改变某个元素的值,

它等于插入和删除两个操作的组合。

冷■查找数据元素。在一个给定的数据结构中，找出满足指定条件

的元素。

0排序。对一个给定的数据结构中的所有的元素按照一定的条件

将它们重新排列顺序。

给■遍历。在一个给定的数据结构中，从第一个结点开始，依次访

问各个结点，以便进行某种处理。每个结点只能被访问一次。

辨•判定某个数据结构是否为空或是否已达到最大允许的容量。

等•统计数据元素的个数。

莓数据的操作是定义在数据的逻辑结构上的，但

数据操作的具体实现要在数据的存储结构上进

行，所以数据的操作与数据的逻辑结构和存储

结构有直接的关系。每种数据结构都有自己的

一个数据操作的集合，即除了上面所说的几种

数据操作之外，还有针对自己的结构的数据操

作。止匕外，同一种数据操作在不同的数据结构

上实现的效率并不相同。例如，插入操作在顺

序存储结构上实现的效率比在链式存储结构上

实现的效率更低。

j

5.学碱叱构的目的

辨在计算领域中，数据结构是计算机算法

设计的基础，在计算科学中占有十分重

要的地位。对于计算机应用人员来说，

学会在程序设计中选择适当的数据结构,

可简化算法、节省空间、提高效率。

给例：印度的工程师常使用数组而不是链

表

533最简单的数据结构-线性表

O(1)定义

专线性表的逻辑结构是n个数据元素的有

限序列：

专其中n为表中数据元素的个数，定义为

表的长度。线性表中的所有数据元素a：

必须是相同的数据类型。

||、吧IIII

(2)线性表的逻辑结构特征

争线性表的逻辑结构特征是：数据元素之

间呈线性关系。

❸第1个：无前驱，有1个后继；

❸最后一个：有1个前驱，无后继；

金其它：有1个前驱，有1个后继。

3）线性表的存储结构

靠线性表的存储结构分为两类，一类是顺序存储

结构（又称为静态存储结构），另一类是链式

存储结构（又称为动态存储结构）。

线性表的顺序存储，是用一组地址连续的存储

单元依次存放线性表的数据元素，使逻辑上相

邻的数据元素存储在物理上相邻的存储单元中,

而数据元素之间的关系由存储单元的邻接关系

唯一确定。这种采用顺序存储结构存储的线性

表，也称为顺序表。由于线性表中的所有数据

元素的数据类型是相同的，因此每个元素占用

同样大小的存储单元。

给例如线性结构8=(D,R),其中D=

{a,b,c,d,e,f),R={(b,c),

(c,d),(d,a),(a,f),(f,e)}o

将D中的元素存放在以起始地址s开始的

连续存储单元中，为叙述简单，设每个

数据元素(结点)只存放一个字符(即

字符a,b,c,d,ef),每个结点占一个存储

单元，其顺序存储结构如图5.12所示。

图5.12顺序存储结构和链式存储结构

(a)顺序存储结构(b)链式存储结构

«顺序存储结构的线性表的优点是：简单、直观，可随

机存取任一元素；缺点是如果在数据元素中要插入或

删除一个元素，将要引起在此元素以后的大量元素的

移动，工作量很大。另外，对于长度可变的线性表，

难以确定存储空间容量。存储空间太少不够用，太多

则浪费。

«链式存储结构中，每个数据元素的存储包括两部分：

一部分用于存放数据元素的值称为数据域，另一部分

用于存放其直接后继元素的存储地址，称为指针域。

通常将数据域和指针域两部分合称为一个结点

(node)o在链表中，使用指针联系元素，链表的每

个数据元素可以存放在任意存储单元，相邻数据元素

的存储空间可以不连续，线性表中各元素的存储顺序

与元素之间的关系可以不一致，而数据元素之间的关

系是由指针来确定的。

器采用链式存储结构存储的线性表，称为线性链

表。线性链表又可因链接方式的不同而分为多

种，一般有单链表、双向链表和循环链表。以

下只讨论单链表，简称为链表。

器在链表中，为了确定表中第一个元素的位置，

需要一个指针指向第一个结点，称此指针为头

指针，第一个结点也称为头结点。为了标识最

后一个结点，将最后一个结点的指针置为空，

用或"NULL”表示。若线性表为空表时,

则头指针为空。前述数据结构B=(D,R)的

链式存储结构如图5.12(b)所示，其中head为

头指针。

有插入、删除和存取数据元素是所有数据结构的

基本操作。若对线性表的这些基本操作加以一

定的限制，则形成下面几种特殊的线性表：

e(1)后进先出(LastInFirstOut),简称LIFO

的线性表，它的所有插入删除和存取都是在线

性表的表尾进行的。这种限定只能在一端进行

插入和删除的线性表，称之为堆栈(stack)或简

称栈。实例：堆起的盘子；箱子中的物体；谷

堆。应用：递归算法的实现；计算机中多重过

程调用时现场的保存；编程中某些问题的求解

(如老鼠走迷宫问题、背包问题)。

0(2)先进先出(FirstInFirstOut),简称FIFO

的线性表，它的所有插入都是在线性表的一端

进行的，而所有的删除和存取又都在线性表的

另一端进行。这种限定只能在表的一端进行插

入，在另一端进行删除的线性表称为队列。实

例：排队队列。应用：计算机的键盘缓冲区实

现、操作系统中的多进程/多任务管理、网络

中数据传输的串行/并行转换、计算机中的硬

件中断排队、银行业中的业务模拟分析系统。

(3)限定所有插入删除和存取都在表的两端进

行的线性表。

辨此外，在编程时常用到的数组也是线性表的推

广形式之一。

5.4面向对象程序设计语言的基本概念

^传统的高级语言程序由一个主程序和若

干个子程序及函数组成，程序运行时总

是从主程序开始，由主程序调用各子程

序和函数。程序设计人员在编写程序时

必须将整个程序的执行顺序十分精确地

设计好，然后程序按指定的顺序执行。

所以，传统的高级语言称为面向过程的

语言。如BASIC、C、FORTRAN、

PASCAL>Ada等都是典型的过程性语言。

绘传统的“面向过程”的方法学是把世界

分成两个部分，分别认知：

器(1)数据(Data)：用于描述各种状态的

数据结构；

障(2)过程(Procedures)：就是操作这些

状态数据的程序，有时也称为“算法”。

靠传统的“面向过程”的方法学认为数据是静态

的，是不会自行改变的，需要使用各种各样的

过程来改变数据。它采用过程性语言编程，其

主要特征是：程序由“数据定义”加上“算法”

组成，IP:程序=数据结构+算法。

专“面向对象”的方法学认为世界是由各种各样

的对象（object）组成的，面向对象程序设计

的基本元素是对象，一个对象可以包含数据以

及对这些数据进行的一组操作。每一个对象都

有两个特征：状态（也称为属性、数据）与行

为（也称为方法、操作）。

8每个对象都是通过自己的行为来变化自身的状态，一

切变化都是对象自身、或对象间的协调而产生的。换

句话说，对象中的数据仅属于对象本身，系统中的其

它对象不允许直接对对象中的数据进行操作，只可以

向对象发送消息。程序中的一切操作都是通过向对象

发送消息来实现的。对象根据所接收到的消息，启动

有关方法来执行相应的操作，从而达到访问对象中数

据的目的。

器面向对象方法的最大优点就是可以重用现存的对象，

把对软件的改动限制在很小的范围内，从而使软件的

调试和修改更方便，使软件更经得起变化。在开发程

序时，面向对象方法可以大大地节省程序设计的时间

«采用面向对象方法，程序开发团队可以采用那些在结

构化程序开发中所用的分析、设计和编程的技术和工

具。现今，许多开发人员使用统一建模语言UML

(UnifiedModelingLanguage)。UML包含了用于面

向对象方法中进行分析、设计和编制文档的标准符号

表不法。

器在九十年代后期，对象管理小组OMG(Object

ManagementGroup)采纳了UML作为标准。对象管理

小组是一个为面向对象应用开发制定指导方针及标准

规范的国际性组织。除了UML,对象管理小组还采用

CORBA(CommonObjectRequestBroker

Architecture)作为一种程序设计标准。CORBA定义了

网络中分处于不同程序中的对象相互通信的方法。

5.4.1面向对象概述

o1.对象（Object）

®“对象”是面向对象程序设计的核心。在现实生活中,

对象可泛指任何事物，包括具体实体（客观世界中的

任何事物）和抽象概念（主观世界中的任何事物）。

出在面向对象程序设计中，对象的概念就是对现实世界

中对象的模型化，它是代码和数据的组合，同样具有

自己的状态和行为。对象的状态用数据来表示，称为

对象的属性；而对象的行为用对象中的代码来实现，

称为对象的方法。总之，任何对象都由状态（也称为

属性、数据）和行为（也称为方法、操作）组成。换

句话说，一个对象可以包含数据及对这些数据进行访

问和处理的一组操作。

II-I.IIMLIIiwrI441

2.属性(Property)

龄属性用来表示对象的特性。不同的对象有不同的属性。

例如，一本书有书名、书号、作者、出版社、出版日

期、价格等属性，这些属性会因书的不同而不同。

®以VisualBasic为例，VB中的每个对象都有一组特定的

属性。如文本框的属性有名称(Name)、标题

(Caption)＞文本内容(Text)、字体大小(Font)、是否

可见(Visible)等。一般来说，每个对象的属性都有

一组默认值。对大多数属性都可采用系统提供的默认

值，当默认值不能满足要求时可以由用户自己来设置

所需的属性值。

等对象的属性反映了对象的状态。在程序系统中，属性

也就是对象所拥有的数据。

03.事件驱动

龄面向对象程序设计语言是事件驱动的，

程序设计人员只需编写响应用户动作的

程序，而不必考虑每个步骤按什么顺序

执行。在这种机制下，不必编写一个大

型程序，而是建立一个由若干个微小程

序组成的应用程序，这些微小的应用程

序都可以由用户操作来触发。这样就使

编程工作变得比较简单。下面具体讲述

几个相关概念。

令（1）事件

辱事件（Event）是面向对象程序设计中对应于“消息”

的术语。

给对象的事件，是一种特定的操作，是指由系统事先设

定的、能被对象识别和响应的动作。一个事件可以是

在键盘上按键、在窗体上单击鼠标、窗体打开或关闭、

或者向文本框输入一个值。例如，在VB中，鼠标的单

击（Click）、双击（Dblclick）,窗体的装载（Load）

等都是事件。

卷通常情况下，事件可以是由用户操作引起的，也可以

是来自系统、其它应用程序或应用程序内部消息触发。

每一种对象能识别的事件是不同的。例如窗体能识别

单击和双击事件，而命令按钮能识别单击事件却不能

识别双击事件。但是，多数事件类型为大多数对象所

共有。例如命令按钮和窗体都可以对单击（Click）事

件做出响应。

<>(2)事件过程

需响应某个事件所执行的操作是通过一段程序代

码来实现的，这样的一段程序代码称为事件过

程(EventProcedure),也称为事件字程序。

一个对象能识别一个或多个事件，因此可以使

用一个或多个事件过程对用户或系统的事件作

出响应。但在程序中究竟使用多少事件过程，

则要由设计者根据程序的具体要求来确定。相

同事件发