C语言chap3 C程序的流程的控制.ppt

3.1 算法 通过前两章的学习，不少读者可能已经悟出，计算机尽管可以完成许多极其复杂的工作，但实质上这些工作都是按照人事先编好的程序的规定进行的。所以人们常把程序称为计算机的灵魂。随着计算机应用的日益广泛和深入，人们在研究和开发新的软、硬件技术的同时，也对程序本身和程序设计方法进行了深入的探讨。1976年瑞士计算机科学家Niklaus Wirth在他的惊世之作中提出了一个著名的公式： 算法 + 数据结构 = 程序 他认为，“程序就是在数据的某些特定表示方式和结构的基础上对抽象算法的具体表述”。Wirth企图用这个公式来对程序进行一个概括性的定义。从今天的观点来看，它只能是对过程化程序的一个抽象定义，对面向对象的程序而言则不尽然。不过对学习C语言这样的面向过程的程序设计语言而言，是完全适用的。也就是说，面向过程的程序有两大要素：算法和数据结构。数据结构是程序所处理的对象——数据的表示和组织形式。数据类型就是其重要内容。关于数据结构的概念在学习完第5、6、7章后，才会有较深的体验。 3.1.1 算法的组成要素与基本性质 算法含有两大要素： （1）操作 算法是由一系列操作组成的。每个操作的确定不仅取决于问题的需求，还取决于它们取自哪个操作集，它与使用的工具系统有关。如算盘上的操作集由进、退、上、下、去等组成；做菜的操作集包括坐锅、加油、炒、煮、炸、蒸、焖、加水、加调料等；驾驶汽车的操作包括踩离合器、踩油门、开电门、换档、左转、右转、开灯、关灯等。计算机算法要由计算机实现，组成它的操作集是计算机所能进行的操作。而且这些操作的描述与程序设计语言的级别有关。在高级语言中所描述的操作主要包括：算术运算(+、-、*、/)、逻辑运算(“与”、“或”、“非”等)、关系运算(==、＞=、＜=、＞、＜、!=等)、函数运算、位运算、I/O操作等。计算机算法是由这些操作所组成的。 （2）控制结构 算法的另一要素是其控制结构。每一个算法都要由一系列的操作组成。同一操作序列，按不同的顺序执行，就会得出不同的结果。控制结构即如何控制组成算法的各操作的执行顺序。结构化程序设计方法要求：一个程序只能由三种基本控制结构(或由它们派生出来的结构)组成。1966年Bohm和Jacopini证明，由这三种基本结构可以组成任何结构的算法，解决任何问题。这三种基本结构是： (1) 顺序结构。顺序结构中的语句是按书写的顺序执行的，即语句的执行顺序与书写顺序一致。这种结构像一串珍珠项链一样清晰可读。这是一种理想的结构，但是光有这样的结构不可能处理复杂的问题。 一般说来，程序中的语句是顺序执行的。但是，顺序执行的程序的功能是非常有限的。为了提高程序的灵活性，必须采用不同的程序流程结构。 (2) 选择结构。最基本的选择结构是当程序执行到某一语句时，要进行一下判断，从两种路径中选择一条。例如，要在两个数a,b中取一个最大的数就要经过比较判断，决定是将a还是将b输出。选择结构给程序注入最简单的智能。 由二分支选择，可以派生出多分支选择结构。 (3) 循环结构(或称重复结构)。这种结构是将一条或多条语句重复地执行若干遍。就像驴子拉磨一样，虽然每一圈的操作都比较简单，而且相同，但磨上若干圈后就能把麦子磨成面粉。众所周知，电子计算机的一大优势是速度快。当能把一个复杂问题用循环结构来实现时，就能充分地发挥计算机的高速度的优势。 2. 算法的基本性质 简单地说，算法就是进行操作的方法和操作步骤。例如，菜谱实际上是做菜肴的算法，乐谱实际上是演奏的算法，计算机程序是用某种程序设计语言描述的解题算法。通常认为算法有如下一些性质： （1）有效性 有效性指算法所规定的操作都应当是能够有效执行的。例如，对于操作汽车的算法，有效的操作就是加速、刹车、换档、转动方向盘、鸣笛等，要让汽车执行“跳起”就是无效的操作。同样，一个计算机算法必须是计算机能够执行的。 （2）确定性 确定性具有两重意义：一是所描述的操作应当具有明确的意义，不应当有歧义性。例如，不能发出这样的操作指令：“执行一个算术操作”。因为它既没有指出算术操作的类型，也没有指出操作数。 确定性的另一重意义： · 操作作序列只有一个初始动作，序列中每一动作仅有一个后继动作； · 序列终止表示问题得到解答或问题没有解答，不能没有任何结论。 （3）有穷性 有穷性指算法所规定的操作序列必须在允许的时间内结束。例如，一个计算机算法要执行100年以上，就失去有穷性。 3.1.2 算法描述工具 为了描述算法，人们创建了许多算法描述工具。下面介绍程序设计中常用的几种方法，并主要介绍如