8 C程序设计基础（第2版）
先将a与b进行比较，若a 根据以上几个例子可以看出，使用传统的流程图主要由带箭头的线、文字说明和不同形状的框构成。采用传统的流程图可以清晰直观地反映出整个算法的步骤和每一步的先后顺序。因此，在相当长的一段时间内，传统流程图成为很流行的一种算法描述方式，但是当算法相当复杂，篇幅很长时，使用传统的流程图就会显得费时又费力。随着结构化程序设计思想的推行与发展，渐渐的衍生出N-S结构化流程图。 3．伪代码 伪代码（pseudocode）是一种算法描述语言。使用伪代码的目的是为了使被描述的算法可以容易地以任何一种编程语言（Pascal、C、Java等）实现。因此，伪代码必须结构清晰、代码简单、可读性好并且类似自然语言。 用各种算法描述方法所描述的同一算法，只要该算法实现的功能不变，就允许在算法的描述和实现方法上有所不同。 1.2.4 算法的复杂度 找到求解一个问题的算法后，接着就是该算法的实现，至于是否可以找到实现的方法，取决于算法的可计算性和计算的复杂度，该问题是否存在求解算法，能否提供算法所需要的时间资源和空间资源。 算法的复杂度是对算法运算所需时间和空间的一种度量。在评价算法性能时，复杂度是一个重要的依据。算法的复杂度的程度与运行该算法所需要的计算机资源的多少有关，所需要的资源越多，表明该算法的复杂度越高；所需要的资源越少，表明该算法的复杂度越低。在计算机的资源中，最重要的是运算所需的时间资源和存储程序、数据所需的空间资源，所以算法的复杂度有时间复杂度和空间复杂度之分。 对于任意给定的问题，设计出复杂度尽可能低的算法是在设计算法时考虑的一个重要目标。另外，当给定的问题已有多种算法时，选择其中复杂度最低者是在选用算法时应遵循的一个重要准则。因此，算法的复杂度分析对算法的设计或选用有着重要的指导意义和实用价值。 算法的时间复杂度是指算法需要消耗的时间资源。一般情况下，问题的规模越大，时间复杂度越大，算法的执行率越低。 算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。 1.2.5 结构化程序设计方法 程序设计初期，由于计算机硬件条件的限制，运算速度与存储空间都迫使程序员追求高效率，编写程序成为一种技巧与艺术而程序的可理解性、可扩充性等因素被放到第二位。这一时期的高级语言如FORTRAN、COBOL、ALGOL、BASIC等，由于追求程序的高效率而不太注重所编写程序的结构，其存在的一个典型问题就是程序中的控制随意跳转，即 第1章 编程思想 9 不加限制地使用goto语句。goto语句允许程序从一个地方直接跳转到另一个地方去。这样做的好处是程序设计十分方便灵活，减少了人工复杂度，但其缺点也是十分突出的，一大堆跳转语句使得程序的流程十分复杂紊乱，难以看懂也难以验证程序的正确性，如果有错，排起错来更是十分困难。这种转来转去的流程图所表达的混乱与复杂，正是软件危机中程序人员处境的一个生动写照，而结构化程序设计，就是要把这团乱麻理清。 经过研究，人们发现任何复杂的算法都可以由顺序结构、选择（分支）结构和循环结构这3种基本结构组成。因此，人们构造一个算法的时候，也仅以这3种基本结构作为“建筑单元”，遵守3种基本结构的规范。基本结构之间可以并列、可以相互包含但不允许交叉，不允许从一个结构直接转到另一个结构的内部去。正因为整个算法都是由3种基本结构组成的，就像用模块构建的一样，所以结构清晰、易于正确性验证、易于纠错，这种方法就是结构化方法。遵循这种方法的程序设计就是结构化程序设计，C语言就是一种结构化语言。 1．顺序结构 顺序结构表示程序中的各操作是按照它们出现的先后顺序执行的，其流程如图1.4所示。整个顺序结构只有一个入口点和一个出口点。这种结构的特点是：程序从入口点开始，按顺序执行所有操作，直到出口点处，所以称为顺序结构。程序的总流程都是顺序结构的。 2．选择结构 选择结构表示程序的处理步骤出现了分支，它需要根据某一特定的条件选择其中的一个分支执行。选择结构有单选择、双选择和多选择3种形式。 双选择是典型的选择结构形式，其流程如图1.5所示，在这两个分支中只能选择一条且必须选择一条执行，但不论选择了哪一条分支执行，最后流程都一定到达结构的出口 点处。 图1.4 顺序结构 图1.5 选择结构 多选择结构是指程序流程中遇到多个分支，程序执行方向将根据条件确定。要根据判断条件选择多个分支的其中之一执行。不论选择了哪一条分支，最后流程都要到达同一个出口点处。如果所有分支的条件都不满足，则直接到达出口点处。 3．循环结构 循环结构表示程序反复执行某个或某些操作，直到某条件为假（或为真）时才可终止循环。在循环结构中最主要的是：什么情况下执行循环？哪些操作需要循环执行？循环结构的基本形式有两种：当型循环和直到型循环，其流程如图1.6（a）和图1.6（b）所示。图中A的操作称为循环体，是指从循环入口点到循环出口点之间的处理步骤，这就是需要循环执行的部分，而什么情况下执行循环则要根据条件判断。 10 C程序设计基础（第2版） 当型结构：表示先判断条件，当满足给定的条件时执行循环体，并且在循环终端处流程自动返回到循环入口点；如果条件不满足，则退出循环体直接到达流程出口点处。因为是“当条件满足时执行循环”，即先判断后执行，所以称为当型循环，其流程如图1.6（a） 所示。 直到型循环：表示从结构入口点处直接执行循环体，在循环终端处判断条件，如果条件不满足，返回入口点处继续执行循环体，直到条件为真时再退出循环到达流程出口点处，即先执行后判断。因为是“直到条件为真时为止”，所以称为直到型循环，其流程如图1.6（b）所示。循环结构也只有一个入口点和一个出口点，循环终止是指流程执行到了循环的出口点。图中所表示的A处理可以是一个或多个操作，也可以是一个完整的结构或一个 过程。 （a）当型循环 （b）直到型循环 图1.6 循环结构 通过3种基本控制结构可以看到，结构化程序中的任意基本结构都具有唯一入口点和唯一出口点，并且程序不会出现死循环。在程序的静态形式与动态执行流程之间具有良好的对应关系。 1.2.6 算法举例 【例1.4】 计算n!。 分析： n!即1×2×3×4×?×(n–1) ×n，因此可以一步一步的采用基本的方法进行计算，即： S1：1*2求得结果等于2； S2：再用S1求得的结果2乘以3，等于6； ?? Sn–1：用Sn–1求得的结果乘以n，最终求得n！（S为步骤Step的缩写）。 这样的计算方式固然也能够求出正确的答案，但是计算的过程过于烦琐。所以可以设两个变量，一个表示乘数，一个表示被乘数。 算法表示如下： 设a为乘数，b为被乘数； 第1章 编程思想 11 S1：输入n； S2：令a=1；b=2； S3：计算a*b，并把两数的乘积放在a中； S4：使b的值加1；如果b?n，则返回到S3，否则结束运行，输出a即为所求。 【例1.5】 求2008—3200年中的哪些年是闰年。 分析： 如果某年是闰年，它要么能被4整除但不能被100整除，如：2008年、2020年；要么能被400整除，如2000年、2400年。 根据如上分析，我们可以设计算法如下： 设判断的年份为N； S1：设N＝2008； S2：如果N能被4整除，转入S3； 如果N不能被4整除，就输出N不是闰年 转入S5； S3：如果N不能被100整除，就输出N是闰年 转入S5； 如果N能被100整除，就转入S4； S4：如果N不能被400整除，就输出N不是闰年 转入S5； 如果N能被400整除，就输入N是闰年 转入S5； S5：令N=N+1； S6：当N?3200时，转入S2继续执行，否则停止算法。 闰年的计算方法虽然只是简单的循环和判断，但这些简单的循环和判断却是组成结构化程序的基本要素。 1.3 上机编程准备 1.3.1 Turbo C集成开发环境 进入Turbo C 2.5集成开发环境后，屏幕上显示的内容如图1.7所示。 图1.7 Turbo C 2.5集成开发环境 12 C程序设计基础（第2版） 图中第2行为Turbo C 2.5主菜单，中间窗口为编辑区，接下来是信息窗口，最底下一行为参考行。这4个窗口构成了Turbo C 2.5的主屏幕，以后的编程、编译、调试以及运行都将在这个主屏幕中进行。下面详细介绍主菜单的内容。 主菜单在Turbo C 2.5主屏幕的第2行，显示下列内容：File、Edit、Run、Compile、Project、Options、Debug、Break/watch。 除Edit项外，其他各项均有子菜单，只要用Alt键加上某项中第1个字母（即大写字母）就可进入该项的子菜单中。 1．File（文件）菜单 按Alt+F键可进入File菜单，该菜单包括以下内容。 （1）Load（加载）：装入一个文件，可用类似DOS的通配符（如*.c）来进行列表选择，也可装入其他扩展名的文件，只要给出文件名（或只给路径）即可。 （2）Pick（选择）：将最近装入编辑窗口的8个文件列成一个表让用户选择，选择后将该程序装入编辑区，并将光标置在上次修改过的地方，其热键为Alt+F3。 （3）New（新文件）：说明文件是新的，默认文件名为NONAME.C，存盘时可改名。 （4）Save（存盘）：将编辑区中的文件存盘，当文件名是NONAME.C时，将询问是否更改文件名，其热键为F2。 （5）Write to（存盘）：可由用户给出文件名将编辑区中的文件存盘。 （6）Directory（目录）：显示目录及目录中的文件，并可由用户选择。 （7）Change dir（改变目录）：显示当前目录，用户可以改变显示的目录。 （8）OS shell（暂时退出）：暂时退出Turbo C 2.5到DOS提示符下。若想回到Turbo C中，只要在DOS状态下输入exit即可。 （9）Quit（退出）：退出Turbo C。 2．Edit（编辑）菜单 按Alt+E组合键可进入Edit菜单，若再按回车键，则光标出现在编辑窗口，此时用户可以进行文本编辑。编辑方法基本与WordStar相同，可按F1键以获得有关编辑方法的帮助信息。Edit命令简介如表1.1所示。 表1.1 Edit命令简介表 PageUp PageDn Home End Ctrl+Y Ctrl+T Ctrl+KB Ctrl+KK Ctrl+Q 向前翻页 向后翻页 将光标移到所在行的开始 将光标移到所在行的结尾 删除光标所在的一行 删除光标所在处的一个词 设置块开始 设置块结尾 查找Turbo C 2.5双界符的后匹配符 Ctrl+Q Ctrl+KP Ctrl+F1 Ctrl+KC Ctrl+KY 查找Turbo C 2.5双界符的前匹配符 块文件打印 如果光标所在处为Turbo C 2.5库函数，则获得有关该函数的帮助信息 块拷贝 块删除 Ctrl+KR 读文件 Ctrl+KW 存文件 3．Run（运行）菜单 按Alt+R键可进入Run菜单，该菜单包括以下各项。 （1）Run（运行程序）：运行由Project/Project name项指定的文件或当前编辑区的文