第3章C程序的流程设计

《第3章C程序的流程设计》由会员分享，可在线阅读，更多相关《第3章C程序的流程设计（150页珍藏版）》请在金锄头文库上搜索。

1、第三章 C程序的流程控制,3.1 算法,计算机实质上是按照人事先编好的程序的规定进行工作的。 1976年瑞士计算机科学家Niklaus Wirth提出了一个著名的公式： 算法 + 数据结构 = 程序,图3.1 Niklaus Wirth,他认为，“程序就是在数据的某些特定表示方式和结构的基础上对抽象算法的具体表述”。 面向过程的程序有两大要素：算法和数据结构。数据结构是程序所处理的对象数据的表示和组织形式。数据类型就是其重要内容。,3.1.1 算法的组成要素与基本性质 算法含有两大要素： （1）操作 算法是由一系列操作组成的。每个操作的确定不仅取决于问题的需求，还取决于它们取自哪个操作集，它与

2、使用的工具系统有关。如算盘上的操作集；做菜的操作集；驾驶汽车的操作等。 计算机算法要由计算机实现，组成它的操作集是计算机所能进行的操作。而且这些操作的描述与程序设计语言的级别有关。在高级语言中所描述的操作主要包括：算术运算、逻辑运算、关系运算、函数运算、位运算、I/O操作等。计算机算法是由这些操作所组成的。,（2）控制结构 算法的另一要素是其控制结构。每一个算法都要由一系列的操作组成。同一操作序列，按不同的顺序执行，就会得出不同的结果。 结构化程序设计方法要求：一个程序只能由三种基本控制结构(或由它们派生出来的结构)组成。 1966年Bohm和Jacopini证明，由这三种基本结构可以组成任何

3、结构的算法，解决任何问题。这三种基本结构是：,(1) 顺序结构。语句的执行顺序与书写顺序一致。 一般说来，程序中的语句是顺序执行的。但是，顺序执行的程序的功能是非常有限的。为了提高程序的灵活性，必须采用不同的程序流程结构。 (2) 选择结构。最基本的选择结构是当程序执行到某一语句时，要进行一下判断，从两种路径中选择一条。 由二分支选择，可以派生出多分支选择结构。 (3) 循环结构(重复结构)。这种结构是将一条或多条语句重复地执行若干遍。就像驴子拉磨一样，虽然每一圈的操作都比较简单，而且相同，但磨上若干圈后就能把麦子磨成面粉。,2. 算法的基本性质 （1）有效性 有效性指算法所规定的操作都应当是

4、能够有效执行的。例如，对于操作汽车的算法，有效的操作就是加速、刹车、换档、转动方向盘、鸣笛等，要让汽车执行“跳起”就是无效的操作。同样，一个计算机算法必须是计算机能够执行的。 （2）确定性 确定性具有两重意义：一是所描述的操作应当具有明确的意义，不应当有歧义性。例如，不能发出这样的操作指令：“执行一个算术操作”。因为它既没有指出算术操作的类型，也没有指出操作数。 确定性的另一重意义： 操作作序列只有一个初始动作，序列中每一动作仅有一个后继动作； 序列终止表示问题得到解答或问题没有解答，不能没有任何结论。 （3）有穷性 有穷性指算法所规定的操作序列必须在允许的时间内结束。,3.1.2 算法描述工

5、具 为了描述算法，人们创建了许多算法描述工具。 1. 流程图 流程图是一种流传很广的算法描述工具。这种工具的特点是用一些图框表示各种类型的操作，用线表示这些操作的执行顺序。图3.2为其中常用的一些符号。,图3.2 常用的流程图标准化符号,平行四边形表示数据，其中可注明数据名称、来源、用途或其它的文字说明。 处理矩形表示各种处理功能。例如，执行一个或一组特定的操作，从而使信息的值、信息形式或所在位置发生变化。矩形内可注明处理名称或其简要功能。 预定义过程带有双竖边线的矩形，表示已命名的处理。该处理为在另外地方已得到详细说明的一个操作或一组操作。例如库函数或其它已定义的函数等。矩形内可注明特定处理

6、名称或其简要功能。 菱形表示判断。菱形内可注明判断的条件。它只有一个入口，但可以有若干个可供选择的出口，在对定义的判断条件求值后，有一个且仅有一个出口被选择。求值结果可在表示出口路径的流线附近写出。 流线直线表示执行的流程。当流程自上向下或由左向右时，流程线可不带箭头，其它情况应加箭头表示流程。 端点。扁圆形表示转向外部环境或从外部环境转入的端点符。例如，程序流程的起、始点。 注解。注解是程序的编写者向阅读者提供的说明。注解符由纵边线构成，它用虚线连接到被注解的符号或符号组上。,图3.3(a)、(b)、(c)中的虚线框，分别为用流程图表示的三种基本流程控制结构。这三种基本结构有一个明显的特征：

7、单入口和单出口。从整体上看都相当于一个处理框。用它们所组成的程序来龙去脉十分清晰。,（a）顺序结构,（b）选择结构,（c）重复结构,图3.3 用流程图描述的三种流程基本结构,例3.1 用流程图描述从三个数中取最大数的算法。 从三个数中取最大数的算法思路是：假定这三个数是a,b,c，则首先可以比较a,b两数，从中选大者；然后再用这个大数与数c比较，从中取大者。这时得到的大数，就是三个数中的最大数。这个算法用流程图描述如图3.4（a）所示。 通常，求解一个问题的算法不是唯一的。例如图3.4（b）也是一个三数中取大的算法。这个算法与图3.4（a）所示算法的不同在于： 算法结构不同：图3.4（a）所示

8、算法采用了两个选择结构，而图3.4（b）所示算法采用了一个循环结构和一个选择结构。 算法的灵活性不同：图3.4（b）中的算法可以用来求任意个数中的最大数。,（a）一个三数中取大的算法,（b）另一个三数中取大的算法,图3.4 三数中取大算法的流程图描述,用流程图表示算法灵活、自由、形象、直观，可以表示任何算法。它允许用流线使流程任意转移。但这却是程序设计中的一个隐患，程序中如果允许流程毫无限制地任意转移，就会使程序如同一团乱麻一样难以阅读和维护，如图3.5所示。这种程序叫做BS程序(a Bowl of Spaghetti的缩写，意为“一碗面条”似的)。,图3.5 无限制地使用流线形成BS流程结构

9、,结构化程序设计主张限制这种无规律的任意转向，采用三种基本结构作为构成程序的基本单位。这样就必须限制流线的使用。,2. N-S图描述 灵活的流线是程序中隐藏错误的祸根。针对这一弊病，1973年美国学者I. Nassi和B. Shneiderman提出了一种无流线的流程图，称为N-S图。它的三种基本结构如图3.6所示。 N-S图的每一种基本结构都是一个矩形框，整个算法可以像堆积木一样堆成。其中，（a）为三个操作组成的顺序结构；（b）为二分支的选择结构；（c）为当型重复结构，即当命题P 为“真”时，就重复执行S。 由于N-S图中没有了流线，所以绝对不会出现由于乱用流线造成的BS算法结构。,（c）当

10、型重复结构,（a）顺序结构,（b）选择结构,图3.6 用N-S图描述三种基本流程结构,图3.7（a）、（b）给出了用与图3.4（a）、（b）流程图对应的N-S图。注意，空白的处理框表示没有操作。,（a）采用选择结构,（b）采用当型重复结构,图3.7 三数中取大算法的N-S图描述,3. 伪代码 伪代码(pseudo code)是用介于自然语言与计算机语言之间的文字符号算法描述的工具。可以用程序设计语言，或使用自然语言与程序设计语言的混合体。一般专业人员习惯用伪代码进行算法描述。 下面是与图3.7相对应的三数中取大算法的伪代码描述。 （1）与图3.7（a）相对应的三数中取大算法的伪代码描述：,输入

11、a,b,c； if(a=b) max=a; else max=b if(max=c) 输出max; else 输出c；,（2）与图3.7（b）相对应的三数中取大算法的伪代码描述：,初始化：mac=0,i=1; 当（i=max) max=n; ) 输出max;,（3）与图3.7（c）相对应的三数中取大算法的伪代码描述：,初始化：mac=0,i=1; ( 输入n; i+; if(n=max) max=n; ) 直到（i3） 输出max;,3.1.3 自顶向下，逐步细化的算法设计过程 算法设计是一个智力过程。设计复杂问题的算法更是一个高强度的智力劳动。实践证明，保证算法设计正确的一个方法是要让问题的

12、复杂性能够在人的智力容易控制范围之内。为此人们提出了一种自顶向下、逐步细化的算法设计方法。 按照这种方法，解题之初不要一下子就力图触及到问题解法的细节，而应当从问题的全局出发，给出高度概括、抽象的算法，通常是把这些问题的求解分成可以独立求解的若干子问题；接着对每一个子问题，再进行分解；最后对不可再分的子问题分别设计算法，而且设计的过程也是从概括逐步细化。一般说来，上层解决的是“做什么”的过程，逐步细化的过程是解决“怎么做”的过程。 在用伪代码描述算法时，随着逐步细化，最终可以用程序设计语言代替算法中的伪代码。等到全部伪代码都用某种程序设计语言描述了，程序设计也就基本完成了。,例3.2 用自顶向

13、下、逐步细化的方法设计三数中取大算法的过程。 这里，仅考虑采用伪代码描述的方法。 (1) 首先，把该问题分析为：,s1: 输入三数a,b,c; s2: 从a,b,c中找出大数赋给max; s3: 输出max。,这一阶段算法是用汉语描述的，描述了按顺序要完成的三个“做什么”。可以用s1,s2,s3代表第1步、第2步、第3步。s是步(step)的缩写。 (2) 在前一阶段的基础上考虑各个“做什么”的实现途径，把算法细化为：,s1: 调用scanf()函数； s2: 设计一个函数max3 (a,b,c); s3: 调用printf()函数。,这一阶段是用混合语言写算法。,(3) 写主函数的条件已经成

14、熟。,int main(void) /*三数中取大数*/ float a,b,c, max; float max3(float x,float y, float z); printf (Input 3 numbers a b c:); scanf (%f%f%f, ,(4) 设计max 3()的算法。仍按逐步细化的方法，先给出概要算法。设三个参数为float x, float y, float z。,s2.1: 从x与y中取大数送m中； s2.2: 从m与z中取大数送m中； s2.3: 返回m给主调函数。,进一步细化得,s2.1: if(xy) m=x; else m=y; s2.2: if(

15、mz) m=m; else m=z; s2.3: return (m);,这就很容易用C语言立刻写出函数max3()了：,float max 3 (float x, float y, float z) float m; if (xy) m=x; else m=y; if (mz) m=m; else m=z; return (m); ,一次执行结果：,Input 3 numbers a b c: 34.7 45.9 678 The max is: 678.000000,3.2 判断,3.2.1 命题的“真”、“假”与C语言中的逻辑值 不论是选择结构，还是循环结构，流程的改变都是由判断决定的。即

16、需要根据判断决定选择，根据判断决定是否循环以及循环的结束。通常，判断是针对命题的“真”、“假”进行的。例如，下面是一些命题： （行驶中）前面的交通信号灯是红色的。 今天下雨。 ab。 abc，即ab 且bc。 ab 或cb。 如果a不能被b整除。 这些命题的值都只能是一个逻辑（布尔）值：“真”或“假”。 早期的C语言不提供专门的逻辑（布尔）类型，规定用非0值表示“真”，用0值表示“假”。这样，不管任何表达式，只要其值为非0（包括负数），就说明其为“真”；只要其值为0，就说明其为“假”。从而给判断带来很大的灵活性。 在C99中，增加了_Bool类型，并增加了头文件，在其中定义了宏bool、true和false，用true存储1，用false存储0。,3.2.2 关系运算与关系表达式 关系表达式和逻辑表达式是C语言中描述命题的两种基本形式。 1. C语言的关系运算符 关系运算是指对两个表达式值的大小比较。C语言中提供有如下6个关系运算符： (大于) =(大