1.2 结构化程序设计

结构化程序设计是一个程序设计人员所具备的基本知识。要想实现一个完整又合理的计算机程序，就应当采用结构化程序设计方法进行程序设计（即规划所要制作软件的整体框架，然后分模块设计），并且选用某一种计算机语言来表示（实现之前设计的程序结构框架）。因此，语言本身只是工具，要想很好地掌握C语言，首先就要对结构化程序设计进行深入学习和理解。下面先介绍一下结构化程序设计的概念和方法，以及结构化程序设计的灵魂要素——算法。

1.2.1 程序设计的概念

什么是程序设计？就从著名计算机科学家沃思（Nikiklaus Wirth）提出的一个公式说起：

程序设计=数据结构+算法

数据结构到底是什么呢？数据结构即非数值计算的程序设计问题中描述计算机的操作对象，以及它们之间的关系和操作；算法是对特定问题求解步骤的一种描述，是对具体问题的具体实现（代码实现方法）。形象地说，“程序设计”就像“盖房子”，数据结构就像砖、瓦，而算法就是设计图纸。若想盖房子，首先必须有原材料（即数据结构），但是这些原料不会自动地盖起想要的房子，必须按照设计图纸（即算法）上说明的方法一砖一瓦地去砌，这样才能修建起理想中的房子。程序设计也一样，使用的编译工具中有各种功能语句或基本结构，它们不会自动排列成需要的程序代码，必须按照程序规定的功能去编写（就像人既要遵守法律又要生活一样），而程序功能的实现就是算法的具体体现（用你选择的程序设计语言实现之前的设计图纸——算法）。所以通俗地说，程序设计就是你在必须按照特定规则的前提下，把特定的功能和基本结构按照符合规则的顺序编写出正确的程序代码，这样就可以形成一个有特定功能的程序。

数据结构是程序设计这座大厦的基础，没有基础，无论设计有多么高明，这座大厦都不可能建造起来。算法则是程序设计的思想和灵魂，没有灵魂的程序不能叫程序，它只是一堆杂乱无章的符号而已。程序设计的基本目标是用算法对问题涉及的数据进行处理，从而获得所期望的效果。

也就是说，数据结构和算法是一个程序设计人员所应具备的基本知识。算法是灵魂，数据结构是加工对象，算法是解决“做什么”和“怎么做”的问题。程序中的操作语句实际上就是算法的体现，显然，不了解算法就谈不上程序设计。由于算法的重要性，本节先介绍算法的初步知识。

1.2.2 程序的灵魂——算法

做任何事情都要有一定的步骤。例如，要想做一顿美味可口的饭菜，就要去菜市场买菜、洗菜、切菜，然后炒菜。这些步骤都是按照一定的顺序进行的，缺一不可。算法就是程序设计的基本思想、方法和实现步骤。

1.算法的概念

算法是对要解决一个问题或要完成一项任务所采取的方法和具体步骤的描述，包括需要什么数据（输入什么数据、输出什么结果）、采用什么结构、使用什么语句及如何安排这些语句等。

2.算法实例

下面将举两个简单的算法实例。

例1-1 实现两个变量交换数据的过程。

好比有两个缸子，一个装满了油，另一个装满了水，要互换缸子里的油和水，就需要第三个缸子。同理，已知变量x和y中分别存放了数据，现在要交换其中的数据。为了达到交换的目的，需要引进一个中间变量m，其算法如下：

（1）将x中的数据送给变量m，即x→m。

（2）将y中的数据送给变量x，即y→x。

（3）将m中的数据送给变量y，即m→y。

例1-2 演示输入三个不相同的数，求出其中最小数的过程。

先设置一个变量min，用于存放最小数。当输入a、b、c三个不相同的数后，先将a与b进行比较，把小者送给变量min，再把c与min进行比较，若c<min，则将c的数值送给min，最后min中就是三个数中的最小数，具体算法如下：

（1）若a<b，则a→min，否则b→min。

（2）再将c与min进行比较，若c<min，则c→min。这样，min中存放的即是三个数中的最小数。

例1-3 演示输入两个正整数a和b（a>b），求它们的最大公约数的过程。

求两个正整数a、b（a>b）的最大公约数，可以归结为求数列：

a，b，r1，r2，…，rn-1，rn，rn+1，0

此数列的首项与第二项是a和b，从第三项开始的各项分别是前两项相除所得的余数，如果余数为0，它的前项rn+1就是a和b的最大公约数，这种方法叫做欧几里德辗转相除法，其算法如下：

（1）输入a和b（a>b）。

（2）求a/b的余数r。

（3）如果r≠0，则将b→a，r→b，再次求a/b的余数r，转至（3）。

（4）输出最大公约数b。

3.算法特性

一个算法应该具有以下5个重要的特征。

● 有穷性：一个算法必须保证执行有限次步骤之后结束，而不是无穷无尽的。例1-3中，如果r的值永远都不等于0，则循环永远都不会停止，这不是有穷的步骤。

● 确切性：算法的每一步骤必须有确切的定义，不应当是含糊的、模棱两可的。例1-1中，如果说将x中的数据送给一个变量，这就是不确切，计算机无法执行。因为不知道送给哪一个变量，所以要指明变量m。

● 输入：一个算法有0个或多个输入，以描述程序中的运算对象的初始情况，所谓0个输入，是指算法本身就给定了初始条件（算是一种隐含的内部输入），如例1-2和例1-3分别需要3个和2个输入。也有的算法可以不要任何输入，如计算从1到100的和就是0个输入。

● 输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。例1-1、例1-2和例1-3分别要求输出交换后的数据，三个数中的最小值和两个数的最大公约数。没有输出的算法是毫无意义的。当然算法的输出不一定都要计算机打印输出。

● 有效性：算法中的每一个步骤都应当有效地执行，并能得到确定的结果。例如，若b=0，则a/b是不能有效执行的。

4.关于算法的认识

同一问题可以用不同的算法来解决。例如，求1+2+3+…+100的和，可以采用如下方法：先求1+2+3，再加4，一直加到100，最后得到结果5050；也可以采用这样的方法：1+2+3+…+100=（1+99）+（2+98）+（3+97）+…+（49+51）+100+50= 5050；或者采用下一种方法：1+2+3+…+100=（1+100）+（2+99）+…+（50+51）=50×101=5050。显然，对于心算来说，后两种方法更简便，而累加更适用于计算机解题。由此可见，一个算法质量的好坏将会影响到算法乃至程序的效率。因此，为了更有效地解决问题，不仅需要保证算法的正确性，还要进行算法分析，考虑算法的质量，选择合适算法和改进算法。

5.算法的描述

说话用语言来表述，编程用结构化程序设计语言表述，对于算法的描述，我们可以使用自然语言、结构化流程图或者其他形式表述。

自然语言就是我们日常使用的语言。例1-1、例1-2和例1-3都是用自然语言描述的。用自然语言描述算法比较习惯和容易接受，但是叙述较烦琐和冗长，容易出现“歧义性”，一般不采用这种方法。而用流程图描述算法，能够将解决问题的步骤清晰、直观地表示出来，一般采用流程图描述算法。

流程图是用一组几何图形表示各种类型的操作，在图形上用简明扼要的文字和符号表示具体的操作，并用带有箭头的流线表示操作的先后次序。表1-1列出了流程图的基本符号及其含义。

图1-1、图1-2和图1-3分别是例1-1、例1-2和例1-3的流程图。需要注意的是，流程图仅仅描述了算法，但计算机是无法识别和执行用流程图表示的算法的，还必须使用某种计算机语言（如C语言）编写出程序，然后计算机才能运行此程序，得到所需的结果。

通过图1-1、图1-2和图1-3可以看出，流程图是表示算法的较好工具。一个流程图包括以下几个部分：

● 表示相应操作的框。

● 带箭头的流程线。

● 框内外必要的文字说明。

1.2.3 程序设计三剑客——三大基本结构

在1.2.2节中提到的传统流程图描述方法，是用流程线很随意地描述程序转移功能。如果一个程序中多处出现这种转移情况，将会导致程序流程内部混乱，不清楚该执行那一行代码，程序结构杂乱无章，这样的程序是非常令人难以理解和接受的，而且不符合结构化设计的思想。为此提出了程序的三种基本结构：顺序结构、选择结构和循环结构。结构化程序设计就是利用这三种结构来构建程序。

1.循规蹈矩——顺序结构

顺序结构表示程序中的各操作是按照它们出现的先后顺序执行的，其流程如图1-4所示。图中的S1和S2表示两个中间处理过程，这些处理步骤可以是一个非转移操作或多个非转移操作序列，甚至可以是空操作，也可以是三种基本结构中的任一结构。整个顺序结构只有一个入口点A和一个出口点B。这种结构的特点是，程序从入口点A开始，按顺序执行所有操作，直到出口点B处，因此称为顺序结构。事实上，不论程序中包含了什么样的数据结构还是运用了什么样的算法，程序的总流程都会是顺序执行的。

2.精挑细选——选择结构

选择结构表示程序的处理步骤出现了分支，即它需要根据某一特定的条件选择其中的一个分支代码段进行执行。选择结构有单选择、双选择和多选择三种形式。

双选择是典型的选择结构形式，其流程如图1-5所示，图中的S1和S2与顺序结构中的说明相同。由图中可见，在结构的入口点A处是一个判断框，表示程序流程出现了两个可供选择的分支，如果条件满足执行S1处理，否则执行S2处理。值得注意的是，在这两个分支中只能选择一条且必须选择一条执行，但不论选择了哪一条分支执行，最后流程都一定到达结构的出口点B处。

当S1和S2中的任意一个处理为空时，说明结构中只有一个可供选择的分支，如果条件满足执行S1处理，否则顺序向下跳过条件内部的代码直接执行流程出口B处。也就是说，当条件不满足时，什么也没执行，所以称为单选择结构，如图1-6所示。

多选择结构是指程序流程中遇到如图1-7所示的S1、S2、…、Sn等多个分支，程序执行方向将根据条件确定。如果满足条件1则执行S1分支，如果满足条件n则执行Sn分支，总之要根据判断条件选择多个分支的其中之一执行。不论选择了哪一条分支，最后流程要到达同一个出口B处。如果所有分支的条件都不满足，则直接到达出口。

3.反反复复——循环结构

循环结构表示程序反复执行某个或某些操作，直到循环执行条件为假（或为真）时才可终止循环。在循环结构中最主要的是，什么情况下执行循环？哪些操作需要循环执行？其流程如图1.8所示。图中虚线框内的操作称为循环体，是指从循环入口点A到循环出口点B之间的处理步骤，这就是需要循环执行的部分。而什么情况下执行循环则要根据条件判断。

1.2.4 实现“结构化程序设计”的方法

结构化程序设计是最基本的程序设计，这种程序设计方法简单，设计出来的程序可读性强，容易理解，便于维护，不但提高了程序的可靠性，而且也保证了程序的质量。结构化程序设计的每种结构，只有一个入口和一个出口，这是结构化设计的一个原则。遵循结构化程序设计的原则，按照结构化程序设计方法设计出的程序具有明显的优点。

（1）程序易于阅读、理解和维护。程序员采用结构化编程方法，将一个复杂的程序分解成若干个子结构，便于对模块的控制、降低程序结构的复杂性，因此结构化程序设计容易编写程序，同时便于验证程序的正确性。

（2）提高了编程工作的效率，降低了软件开发成本。由于结构化编程方法能够把错误控制到最低限度，因此能够减少调试和查错的时间。事实上，一个程序除了数据结构和算法两个主要要素以外，还应当采用结构化程序设计方法进行程序设计，并且用一种计算机语言表示，由此，1.2.1节中沃思提出的公式可以被扩展表示为：

程序设计=数据结构+算法+结构化程序设计方法+语言工具和环境

也就是说，以上四个方面是程序设计最基本的要素。

结构化程序设计的基本思想是，把一个完整的程序当成一个模块。这个模块可以通过简单规则不停地细分成若干个有意义的子模块。采用“自顶向下，逐步求精”的程序设计方法和“单入口、单出口”的控制结构。自顶向下、逐步求精的程序设计方法从问题本身开始，将任务逐步细化，将解决问题的步骤分解为由基本程序结构模块组成的结构化程序框图；“单入口、单出口”的思想认为一个复杂的程序，如果它仅是由顺序、选择和循环三种基本程序结构通过组合、嵌套构成，那么这个新构造的程序一定是一个单入口、单出口的程序。据此就很容易编写出结构良好、易于调试的程序来。

具体来说，采取以下方法保证得到结构化的程序。

● 自顶向下。

● 逐步细化。

● 模块化设计。

● 结构化编码。

以写文章为例来说明“自顶向下，逐步求精”这种设计思想：作者在没有正式开始写文章之前，会先拟好提纲，想好整个文章分成哪几个部分，然后再进一步考虑每个部分分成哪几节，每一节分成哪几段，每一段应该包含什么内容。

这种写文章的方法不像写信一样提笔就写，想到哪里写到哪里。自上而下的设计方法需要考虑周全，结构清晰，易于理解，在程序设计中也方便开发人员独立开发。它将问题由抽象逐步具体化，方便验证算法的正确性，如果每一层设计都没有问题，则算法就是正确的。如果发现某一层的某一部分有问题，只需要直接修改某一部分就可以了。

下面举例说明“自顶向下，逐步求精”这种结构化程序设计方法。

例1-4 找出1000以内的所有完数。一个数如果恰好等于它的因子之和，这个数就称为“完数”。例如6=1+2+3。

对于本程序，采用自顶向下逐步求精的方法来处理问题，先进行“顶层设计”。如图1-9所示，首先输入1～1000，然后找出1000内的完数，然后打印所有完数。

A部分可以细化为图1-10。初始化变量i的值为1，当i的值小于等于1000，循环初始化xi的取值范围为1～1000。

B部分可以细化为图1-11。对于xi，可以分为两步：第一步找出它所有的因子，第二步比较因子的和是否与xi相等。

B1部分可以细化为图1-12。用1到xi-1整除xi，如果余数为0，就是xi的因子。这样就可以求出xi的所有因子。

B2部分可以细化为图1-13。把xi的所有因子的和赋值给hi，比较hi是否等于xi，如果等于xi就是完数。

C部分可以细化为图1-14。循环打印所有完数。

可以看出，结构化程序设计方法用来解决人脑思维能力的局限性和所处理问题的复杂性之间的矛盾。在设计好一个结构化的算法之后，还要善于进行结构化编码。即用高级语言正确地实现三种基本结构。如果所用的语言是像C这样的结构化的语言，进行结构化编程就不是很难。