第四章 程序编码 一、复习要求 1. 了解什么是结构化程序设计，以及结构化程序设计的原则。 2. 了解程序设计风格4个方面的要求。 3. 了解提高程序效率的方法。 4. 了解程序设计语言的分类和特点。 5. 掌握度量程序复杂性的McCabe方法和Halstead方法。 二、内容提要 1. 结构化程序设计 结构化程序设计技术是60年代中期提出来的，它主要包括两个方面： ( 在编写程序时，强调使用几种基本控制结构，通过组合嵌套，形成程序的控制结构。尽可能避免使用会使程序质量受到影响的GOTO语句。 ( 在程序设计过程中，尽量采用自顶向下和逐步细化的原则，由粗到细，一步步展开。 (1) 结构化程序设计的原则 ( 使用语言中的顺序、选择、重复等有限的基本控制结构表示程序逻辑。 ( 选用的控制结构只准许有一个入口和一个出口。 ( 程序语句组成容易识别的块，每块只有一个入口和一个出口。 ( 复杂结构应该用基本控制结构进行组合嵌套来实现。 ( 语言中没有的控制结构，可用一段等价的程序段模拟，但要求该程序段在整个系统中应前后一致。 ( 严格控制GOTO语句，仅在用一个非结构化的程序设计语言去实现一个结构化的构造，或者在某种可以改善而不是损害程序可读性的情况下才可以使用GOTO语句。 大量采用GOTO语句实现控制路径，会使程序路径变得复杂而且混乱，因此要控制GOTO语句的使用。但有时完全不用GOTO语句进行程序编码，比用GOTO语句编出的程序可读性差。例如，在查找结束时，文件访问结束时，出现错误情况要从循环中转出时，使用布尔变量和条件结构来实现就不如用GOTO语句来得简洁易懂。 对于常用的高级程序设计语言，一般都具备前述的几种基本控制结构。即使不具备等同的结构，也可以采用仿真来实现。下面以FORTRAN77为例进行说明，参看图4.1。 基本控制结构  用FORTRAN77模拟基本控制结构   判断语句 if ( p ) S1; else S2;  IF ( p ) THEN S1 ELSE S2 ENDIF   先判断型循环语句 while ( p ) S;  100 CONTINUE IF ( p ) THEN S GOTO 100 ENDIF   后判断型循环语句 do S; while ( p );  100 CONTINUE S IF ( p ) GOTO 100   图4.1 用FORTRAN77语句实现基本控制结构 (2) 程序设计自顶向下，逐步求精 在详细设计和编码阶段，应当采取自顶向下，逐步求精的方法，把一个模块的功能逐步分解，细化为一系列具体的步骤，进而翻译成一系列用某种程序设计语言写成的程序。 例如，要求用筛选法求100以内的素数。所谓筛选法，就是从2到100中去掉2,3,…,9,10的倍数，剩下的就是100以内的素数。为了解决这个问题，可先按程序功能写出一个框架。 main ( ) { 建立2到100的数组A[ ]，其中A[i]＝i； - - - - - - - - - - - - -- - - - - - - - - - - - 1 建立2到10的素数表B[ ]，其中存放2到10以内的素数；- - - - - - - - - - - - 2 若A[i]＝i是B[ ]中任一数的倍数，则剔除A[i]；- - - - - - - - - - - - - - - - - - - - 3 输出A[ ]中所有没有被剔除的数；- - - - - - - - - - - - - - - - - - -- - - - - - - - - - - - 4 } 上述框架中每一个加工语句都可进一步细化成一个循环语句。 main ( ) { /*建立2到100的数组A[ ]，其中A[i]＝i*/ - - - - - - - - - - - - - - - - - - - - - - - - 1 for （i = 2；i <= 100；i++）A[i] = i； /* 建立2到10的素数表B[ ]，其中存放2到10以内的素数*/ - - - - - - - - - - - 2 B[1] =2； B[2] = 3； B[3] = 5； B[4] = 7； /*若A[i]＝i是B[ ]中任一数的倍数，则剔除A[i]*/ - - - - - - - - - - - - - - - - - - - - 3 for （j = 1； j <= 4； j++） 检查A[ ]所有的数能否被B[j]整除并将能被整除的数从A[]中剔除；- - - - - - - - 3.1 /*输出A[ ]中所有没有被剔除的数*/ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -4 for （i = 2； i <= 100； i++） 若A[i]没有被剔除，则输出之；- - - - - - - - -- - - - - - - - - - - - - - - - - - - - - - - - - -4.1 } 继续对3.1和4.1细化下去，直到最后每一个语句都能直接用程序设计语言来表示为止。 main ( ) { for （i = 2；i <= 100；i++）A[i] = i； B[1] =2； B[2] = 3； B[3] = 5； B[4] = 7； /*若A[i]＝i是B[ ]中任一数的倍数，则剔除A[i]*/ for （j = 1； j <= 4； j++） /*检查A[ ]所有的数能否被B[j]整除并将能被整除的数从A[ ]中剔除*/ for （i = 2； i <= 100； i++） if （A[i]／B[j]*B[j] == A[i]）A[i] = 0； /*输出A[]中所有没有被剔除的数*/ for （i = 2； i <= 100； i++） /*若A[i]没有被剔除，则输出之*/ if （A[i] != 0） printf（“A[%d]＝%d\n”，i，A[i]）； } 自顶向下，逐步求精方法的优点： ① 自顶向下，逐步求精方法符合人们解决复杂问题的普遍规律。可提高软件开发的成功率和生产率； ② 用先全局后局部，先整体后细节，先抽象后具体的逐步求精的过程开发出来的程序具有清晰的层次结构，因此程序容易阅读和理解； ③ 程序自顶向下，逐步细化，分解成一个树形结构（如图4.2所示）。在同一层的结点上做的细化工作相互独立。在任何一步发生错误，一般只影响它下层的结点，同一层其它结点不受影响。在以后的测试中，也可以先独立地一个结点一个结点地做，最后再集成。 ④ 程序清晰和模块化，使得在修改和重新设计一个软件时，可复用的代码量最大； ⑤ 每一步工作仅在上层结点的基础上做不多的设计扩展，便于检查； ⑥ 有利于设计的分工和组织工作。 (3) 数据结构的合理化 H.Mills指出，结构化程序设计主要是想从程序的控制结构入手，消除不适应的、容易引起混乱的GOTO语句。这只是问题的一个方面，而问题的另一方面，过去没有注意到的是数据结构的合理化问题，即数据结构访问的规范化，标准化问题。 假如数据结构中常使用数组、指针等数据类型，则对它们必须采取随机访问，这样势必产生访问上的混乱。例如，要访问数组元素A[i][j]，必须先对下标i，j访问，造成访问忽前忽后，这与GOTO语句造成的混乱类似，同样是有害的。H.Mills指出，解决这一问题的办法是用栈和队列去代替数组和指针。栈与队列分别是按后进先出（LIFO）和先进先出（FIFO）的原则进行存取的。在程序中用栈和队列代替数组和指针，用合理的规范的顺序存取代替随机存取，将克服随机存取带来的麻烦。而且有人做了证明，所有使用数组和指针的程序，都可以使用栈和队列的程序等价替换。 2．程序设计风格 在软件生存期中，人们经常要阅读程序。特别是在软件测试阶段和维护阶段，编写程序的人与参与测试、维护的人都要阅读程序。因此，阅读程序是软件开发和维护过程中的一个重要组成部分，而且读程序的时间比写程序的时间还要多。70年代初，有人提出在编写程序时，应使程序具有良好的风格。 程序设计风格包括4个方面：源程序文档化，数据说明，语句结构和输入／输出方法，力图从编码原则的角度提高程序的可读性，改善程序质量。 (1) 源程序文档化 ① 符号名的命名 符号名即标识符，包括模块名、变量名、常量名、子程序名、数据区名、缓冲区名等。 ( 这些名字应能反映它所代表的实际东西，应有一定实际意义。 ( 名字不是越长越好，过长的名字会使程序的逻辑流程变得模糊，给修改带来困难。所以应当选择精炼的意义明确的名字，改善对程序功能的理解。 ( 必要时可使用缩写名字，但缩写规则要一致，并且要给每一个名字加注释。 ( 在一个程序中，一个变量只应用于一种用途。就是说，在同一个程序中一个变量不能身兼几种工作。 ② 程序的注释 夹在程序中的注释是程序员与日后的程序读者之间通信的重要手段。正确的注释能够帮助读者理解程序，可为后续阶段进行测试和维护，提供明确的指导。因此，注释决不是可有可无的，大多数程序设计语言允许使用自然语言来写注释，这就给阅读程序带来很大的方便。一些正规的程序文本中，注释行的数量占到整个源程序的1／3到1／2，甚至更多。 ( 序言性注释 ：通常置于每个程序模块的开头部分，它应当给出程序的整体说明，对于理解程序本身具有引导作用。有些软件开发部门对序言性注释做了明确而严格的规定，要求程序编制者逐项列出的有关项目包括：程序标题、有关本模块功能和目的的说明、主要算法、接口说明、有关数据描述、模块位置、开发简历等。 ( 功能性注释 ：嵌在源程序体中，用以描述其后的语句或程序段是在做什么工作，不要解释下面怎么做，因为解释怎么做常常是与程序本身重复的，并且对于阅读者理解程序没有什么帮助。 书写功能性注释，要注意：·用于描述一段程序，而不是每一个语句；·用缩进和空行，使程序与注释容易区别；·注释要正确。 ③ 视觉组织 利用空格、空行和移行，提高程序的可视化程度。 ( 恰当地利用空格，可以突出运算的优先性，避免发生运算的错误。 ( 自然的程序段之间可用空行隔开； ( 对于选择语句和循环语句，把其中的程序段语句向右做阶梯式移行。这样可使程序的逻辑结构更加清晰，层次更加分明。 (2) 数据说明 在编写程序时，需注意数据说明的风格。为了使程序中数据说明更易于理解和维护，必须注意以下几点。 ( 数据说明的次序应当规范化，使数据属性容易查找。 ( 当多个变量名用一个语句说明时，应当对这些变量按字母的顺序排列。 ( 如果设计了一个复杂的数据结构，应当使用注释来说明在程序实现时这个数据结构的固有特点。 (3) 语句结构 在设计阶段确定了软件的逻辑流结构，但构造单个语句则是编码阶段的任务。语句构造力求简单，直接，不能为了片面追求效率而使语句复杂化。 ( 在一行内只写一条语句，并且采取适当的移行格式，使程序的逻辑和功能变得更加明确。 ( 程序编写首先应当考虑清晰性，不要刻意追求技巧性，使程序编写得过于紧凑。 ( 程序编写得要简单，写清楚，直截了当地说明程序员的用意。 ( 除非对效率有特殊的要求，程序编写要做到清晰第一，效率第二。不要为了追求效率而丧失了清晰性。事实上，程序效率的提高主要应通过选择高效的算法来实现。 ( 首先要保证程序正确，然后才要求提高速度。反过来说，在使程序高速运行时，首先要保证它是正确的。 ( 让编译程序做简单的优化。 ( 尽可能使用库函数。 ( 避免使用临时变量而使可读性下降。 ( 尽量用公共过程或子程序去代替重复的功能代码段。 ( 用调用公共函数去代替重复使用的表达式。 ( 使用括号来清晰地表达算术表达式和逻辑表达式的运算顺序。 ( 避免不必要的转移。同时如果能保持程序的可读性，则不必用GOTO语句。 ( 尽量只采用三种基本的控制结构来编写程序。 ( 用逻辑表达式代替分支嵌套。 ( 避免使用空的ELSE语句和IF…THEN IF…的语句。 ( 避免使用ELSE GOTO和ELSE RETURN结构。 ( 使与判定相联系的动作尽可能地紧跟着判定。 ( 避免采用过于复杂的条件测试。 ( 尽量减少使用“否定”条件的条件语句。不要让读者绕弯子想。 ( 避免过多的循环嵌套和条件嵌套； ( 不要使GOTO语句相互交叉。 ( 避免循环的多个出口。 ( 使用数组，以避免重复的控制序列。 ( 尽可能用通俗易懂的伪码来描述程序的流程，然后再翻译成必须使用的语言。 ( 数据结构要有利于程序的简化。 ( 要模块化，使模块功能尽可能单一化，模块间的耦合能够清晰可见。 ( 利用信息隐蔽，确保每一个模块的独立性。 ( 从数据出发去构造程序。 ( 不要修补不好的程序，要重新编写。也不要一味地追求代码的复用，要重新组织。 ( 对太大的程序，要分块编写、测试，然后再集成。 ( 对递归定义的数据结构尽量使用递归过程。 ( 注意计算机浮点数运算的特点，例如，浮点数运算 10.0*0.1 通常不等于1.0 。 ( 不要单独进行浮点数的比较。用它们做比较，其结果常常发生异常情况。 ( 避免不恰当地追求程序效率，在改进效率前，要做出有关效率的定量估计。 ( 在程序中应有出错处理功能，一旦出现故障时不要让机器进行干预，导致停工。 此外，对于程序中的变量，标号，注释等，还需要给予一些注意。例如， ( 变量名中尽量不用数字。 ( 显式说明所有的变量。 ( 确保所有变量在使用前都被初始化。 ( 确保注释与代码完全一致。 ( 不仅对代码做注释，而且对每条注释都加以编号。 ( 不注释不好的代码，要重新编写。 ( 程序格式的安排应有助于读者理解程序。 ( 注释不要过于繁琐。 ( 遵循国家标准。 ( 经常反躬自省：“如果我不是编码的人，我能看懂它吗？”考虑它的可理解性达到什么程度。 (4) 输入和输出 (I / O) 输入和输出信息是与用户的使用直接相关的。输入和输出的方式和格式应当尽可能方便用户的使用。因此，在软件需求分析阶段和设计阶段，就应基本确定输入和输出的风格。系统能否被用户接受，有时就取决于输入和输出的风格。 不论是批处理的输入／输出方式，还是交互式的输入／输出方式，在设计和程序编码时都应考虑下列原则： ( 对所有的输入数据都进行检验，从而识别错误的输入，以保证每个数据的有效性； ( 检查输入项的各种重要组合的合理性，必要时报告输入状态信息； ( 使得输入的步骤和操作尽可能简单，并保持简单的输入格式； ( 输入数据时，应允许使用自由格式输入； ( 应允许缺省值； ( 输入一批数据时，最好使用输入结束标志，而不要由用户指定输入数据数目； ( 在以交互式输入／输出方式进行输入时， 要在屏幕上使用提示符明确提示交互输入的请求，指明可使用选择项的种类和取值范围。同时，在数据输入的过程中和输入结束时，也要在屏幕上给出状态信息； ( 当程序设计语言对输入／输出格式有严格要求时， 应保持输入格式与输入语句的要求的一致性； ( 给所有的输出加注解，并设计输出报表格式。 输入／输出风格还受到许多其它因素的影响。如输入／输出设备（例如终端的类型，图形设备，数字化转换设备等）、用户的熟练程度、以及通信环境等。 Wasserman为“用户软件工程及交互系统的设计”提供了一组指导性原则，可供软件设计和编程参考。 ( 把计算机系统的内部特性隐蔽起来不让用户看到； ( 有完备的输入出错检查和出错恢复措施，在程序执行过程中尽量排除由于用户的原因而造成程序出错的可能性； ( 如果用户的请求有了结果，应随时通知用户； ( 充分利用联机帮助手段，对于不熟练的用户，提供对话式服务，对于熟练的用户，提供较高级的系统服务，改善输入／输出的能力； ( 使输入格式和操作要求与用户的技术水平相适应。对于不熟练的用户，充分利用菜单系统逐步引导用户操作；对于熟练的用户，允许绕过菜单，直接使用命令方式进行操作； ( 按照输出设备的速度设计信息输出过程； ( 区别不同类型的用户，分别进行设计和编码； ( 保持始终如一的响应时间； ( 在出现错误时应尽量减少用户的额外工作。 在交互式系统中，这些要求应成为软件需求的一部分，并通过设计和编码，在用户和系统之间建立良好的通信接口。 3. 程序效率 (1) 讨论效率的准则 程序的效率是指程序的执行速度及程序所需占用的内存的存储空间。讨论程序效率的几条准则为： ( 效率是一个性能要求，应当在需求分析阶段给出。软件效率以需求为准，不应以人力所及为准。 ( 好的设计可以提高效率。 ( 程序的效率与程序的简单性相关。 一般说来，任何对效率无重要改善，且对程序的简单性、可读性和正确性不利的程序设计方法都是不可取的。 (2) 算法对效率的影响 源程序的效率与详细设计阶段确定的算法的效率直接有关。在详细设计翻译转换成源程序代码后，算法效率反映为程序的执行速度和存储容量的要求。 转换过程中的指导原则是： ( 在编程序前，尽可能化简有关的算术表达式和逻辑表达式； ( 仔细检查算法中的嵌套的循环，尽可能将某些语句或表达式移到循环外面； ( 尽量避免使用多维数组； ( 尽量避免使用指针和复杂的表； ( 采用“快速”的算术运算； ( 不要混淆数据类型，避免在表达式中出现类型混杂； ( 尽量采用整数算术表达式和布尔表达式； ( 选用等效的高效率算法； 许多编译程序具有“优化”功能，可以自动生成高效率的目标代码。它可剔除重复的表达式计算，采用循环求值法、快速的算术运算，以及采用一些能够提高目标代码运行效率的算法来提高效率。对于效率至上的应用来说，这样的编译程序是很有效的。 (3) 影响存储效率的因素 在大中型计算机系统中，存储限制不再是主要问题。在这种环境下，对内存采取基于操作系统的分页功能的虚拟存储管理，给软件提供了巨大的逻辑地址空间。这时，存储效率与操作系统的分页功能直接有关，并不是指要使所使用的存储空间达到最少。 采用结构化程序设计，将程序功能合理分块，使每个模块或一组密切相关模块的程序体积大小与每页的容量相匹配，可减少页面调度，减少内外存交换，提高存储效率。 在微型计算机系统中，存储容量对软件设计和编码的制约很大。因此要选择可生成较短目标代码且存储压缩性能优良的编译程序，有时需采用汇编程序。通过程序员富有创造性的努力，提高软件时间与空间效率。 提高存储效率的关键是程序的简单性。 (4) 影响输入／输出的因素 输入／输出可分为两种类型：一种是面向人（操作员）的输入／输出；一种是面向设备的输入／输出。如果操作员能够十分方便、简单地录入输入数据，或者能够十分直观、一目了然地了解输出信息，则可以说面向人的输入／输出是高效的。至于面向设备的输入／输出，分析起来比较复杂。从详细设计和程序编码的角度来说，可以提出一些提高输入／输出效率的指导原则： ( 输入／输出的请求应当最小化； ( 对于所有的输入／输出操作，安排适当的缓冲区，以减少频繁的信息交换。 ( 对辅助存储（例如磁盘），选择尽可能简单的，可接受的存取方法； ( 对辅助存储的输入／输出，应当成块传送； ( 对终端或打印机的输入／输出，应考虑设备特性， 尽可能改善输入／输出的质量和速度； ( 任何不易理解的，对改善输入／输出效果关系不大的措施都是不可取的； ( 任何不易理解的所谓“超高效”的输入／输出是毫无价值的； ( 好的输入／输出程序设计风格对提高输入／输出效率会有明显的效果。 4. 程序设计语言 程序编码阶段的任务是将软件的详细设计转换成用程序设计语言实现的程序代码。因此，程序设计语言的性能和设计风格对于程序设计的效能和质量有着直接的关系。 (1) 程序设计语言特性的比较 ① 软件心理学的观点 因为从设计到编码的转换基本上是人的活动，因此语言的性能对程序员的心理影响，将对转换产生重大影响。程序员总是希望选择简单易学、使用方便的语言，以减少程序出错率，提高软件可靠性。从心理学的观点，影响程序员心理的语言特性有如下六种： ( 一致性 ：它表示一种语言所使用符号的兼容程度、允许随意规定限制、以及允许对语法或语义破例的程度。同是一个符号，给予多种用途，会引起许多难以察觉的错误。 ( 二义性 ：虽然语言的编译程序总是以一种机械的规则来解释语句，但读者则可能用不同的方式来理解语句。例如，对于一个逻辑表达式 A ≥“0”and A ≤“9”，读者可能对这个逻辑表达式有不同的理解。 如果一个程序设计语言缺乏一致性和存在二义性，那么用这种语言编写出来的程序可读性就差，同时用这种语言编程也容易出错。 ( 简洁性（紧凑性）：表示程序员为了用该语言编写程序，必须记忆的有关编码的信息量。可用语言支持块结构和结构化程序的能力、可使用的保留字和缩写字的种类、数据类型的种类和缺省说明、算术运算符和逻辑运算符的种类、系统内标准函数的数目等来衡量。 遗憾的是，语言的简洁性与程序的一致性常常是抵触的。 ( 局部性 ：指程序设计语言的联想（综合）特性。综合的特性使人们能够对事物从整体上进行记忆和识别。在编码过程中，由语句组合成模块，由模块组装为程序体系结构，并在组装过程中实现模块的高内聚和低耦合，可使程序的局部性加强。 ( 线性 ：指程序的联想（顺序）特性。人们总是习惯于按逻辑线性序列理解程序。如果程序中线性序列和逻辑运算较多，会提高可读性。如果存在大量的分支和循环，就会破坏顺序状态，增加理解上的困难。直接实现结构化程序可提高程序的线性特性。 ( 传统 ：人们学习一种新的程序设计语言的能力受到传统的影响。具有Pascal基础的程序人员在学习C语言时不会感到困难，因为C保持了Pascal所确立的传统语言特性。但是要求同一个人去学习APL或者LISP这样一些语言，传统就中断了。 ② 软件工程的观点 从软件工程观点，程序设计语言的特性应着重考虑软件开发项目的需要。为此，对于程序编码，有如下一些工程上的性能要求： ( 详细设计应能直接地容易地翻译成代码程序 ：把设计变为程序的难易程度，反映了程序设计语言与设计说明相接近的程度。所选择的程序设计语言是否具有结构化的构造，复杂的数据结构，专门的输入／输出能力，位运算和串处理的能力，直接影响到从详细设计变换到代码程序的难易程度，以及特定软件开发项目的可实现性。 ( 源程序应具有可移植性 ：源程序的可移植性通常有三种解释：① 对源程序不做修改或少做修改就可以实现处理机上的移植或编译程序上的移植；② 即使程序的运行环境改变（例如，改用一个新版本的操作系统），源程序也不用改变；③ 源程序的许多模块可以不做修改或少做修改就能集成为功能性的各种软件包，以适应不同的需要。 为改善软件的可移植性，主要是使语言标准化。在开发软件时，应严格地遵守 ISO 或ANSI、GB的标准，而不要去理会特定编译器提供的非标准特性。 ( 编译程序应具有较高的效率。 ( 尽可能应用代码生成的自动工具 ：有效的软件开发工具是缩短编码时间，改善源代码质量的关键因素。使用带有各种有效的自动化工具的“软件开发环境”，支持从设计到源代码的翻译等各项工作，可以保证软件开发获得成功。 ( 可维护性 ：源程序的可读性，语言自身的文档化特性（涉及标识符的允许长度、标号命名、数据类型的丰富程度、控制结构的规定等）是影响到可维护性的重要因素。 ③ 程序设计语言的技术性能 在计划阶段，极少考虑程序语言的技术特性。但在选定资源时，要规划将要使用的支撑工具，就要确定一个具体的编译器或者确定一个程序设计环境。如果软件开发组的成员对所要使用的语言不熟悉，那么在成本及进度估算时必须把学习的工作量估算在内。 一旦确定了软件需求，待选用的程序语言的技术特性就显得非常重要了。如果需要复杂的数据结构，就要仔细衡量有哪些语言能提供这些复杂的数据结构。如果首要的是高性能及实时处理的能力，就可选用适合于实时应用的语言或效率高的语言。如果该应用有许多输出报告或繁杂的文件处理，最好是根据软件的要求，选定一种适合于该项工作的语言。 软件的设计质量与程序设计语言的技术性能无关（面向对象设计例外）。但在实现软件设计转化为程序代码时，转化的质量往往受语言性能的影响。因而也会影响到设计方法。 语言的技术性能对测试和维护的影响是多种多样的。例如，直接提供结构化构造的语言有利于减少循环带来的复杂性（即McCabe复杂性），使程序易读、易测试、易维护。另一方面，语言的某些技术特性却会妨碍测试。例如，在面向对象的语言程序中，由于实行了数据封装，使得监控这些数据的执行状态变得比较困难；由于建立了对象类的继承结构，使得高内聚、低耦合的要求受到破坏，增加了测试的困难。此外，只要语言程序的可读性强，而且可以减少程序的复杂性，这样的程序设计语言对于软件的维护就是有利的。 总之，通过仔细地分析和比较，选择一种功能强而又适用的语言，对成功地实现从软件设计到编码的转换，提高软件的质量，改善软件的可测试性和可维护性是至关重要的。 (2) 程序设计语言的分类 目前，用于软件开发的程序设计语言已经有数百种之多，对这些程序设计语言的分类有不少争议。同一种语言可以归到不同的类中。从软件工程的角度，根据程序设计语言发展的历程，可以把它们大致分为4类。 ① 从属于机器的语言（第一代语言）：它是由机器指令代码组成的语言。对于不同的机器就有相应的一套机器语言。用这种语言编写的程序，都是二进制代码的形式，且所有的地址分配都是以绝对地址的形式处理。存储空间的安排，寄存器、变址的使用都由程序员自己计划。因此使用机器语言编写的程序很不直观，在计算机内的运行效率很高但编写出的机器语言程序其出错率也高。 ② 汇编语言（第二代语言）：汇编语言比机器语言直观，它的每一条符号指令与相应的机器指令有对应关系，同时又增加了一些诸如宏、符号地址等功能。存储空间的安排可由机器解决。不同指令集的处理器系统就有自己相应的汇编语言。从软件工程的角度来看，汇编语言只是在高级语言无法满足设计要求时，或者不具备支持某种特定功能（例如特殊的输入／输出）的技术性能时，才被使用。 ③ 高级程序设计语言（第三代语言） ( 传统的高级程序设计语言 ：如FORTRAN、COBOL、ALGOL、BASIC等。这些程序语言曾得到广泛应用。目前，它们都已有多种版本。有的语言得到较大的改进，甚至形成了可视的开发环境，具有图形设计工具、结构化的事件驱动编程模式、开放的环境，使用户可以既快又简便地编制出windows下的各种应用程序。 ( 通用的结构化程序设计语言 ：它具有很强的过程功能和数据结构功能，并提供结构化的逻辑构造。这一类语言的代表是PL/1，PASCAL，C和Ada。此外，COBOL78、Turbo BASIC等也应归入第三代程序语言范围。 ( 专用语言 ：专用语言是为特殊的应用而设计的语言。通常具有自己特殊的语法形式，面对特定的问题，输入结构及词汇表与该问题的相应范围密切相关。有代表性的专用语言有APL、Lisp、PROLOG、Smalltalk、C++、FORTH等。从软件工程的角度来看，专用语言支持了特殊的应用，将特定的设计要求翻译成可执行的代码。但是它们的可移植性和可维护性比较差。 ④ 第四代语言（4GL）：4GL用不同的文法表示程序结构和数据结构，但是它是在更高一级抽象的层次上表示这些结构，它不再需要规定算法的细节。4GL兼有过程性和非过程性的两重特性。程序员规定条件和相应的动作这是过程性的部分，并且指出想要的结果，这是非过程部分。然后由4GL 语言系统运用它的专门领域的知识来填充过程细节。 Martin把第四代语言分为以下几种类型： ( 查询语言 ：用户可利用查询语言对预先定义在数据库中的信息进行较复杂的操作。 ( 程序生成器 ：只需很少的语句就能生成完整的第三代语言程序，它不必依赖预先定义的数据库作为它的着手点。 ( 其它4GL ：如判定支持语言、原型语言、形式化规格说明语言等。 (3) 程序设计语言的选择 为某个特定开发项目选择程序设计语言时，既要从技术角度、工程角度、心理学角度评价和比较各种语言的适用程度，又必须考虑现实可能性。有时需要作出某种合理的折衷。 在选择与评价语言时，首先要从问题入手，确定它的要求是什么? 这些要求的相对重要性如何? 再根据这些要求和相对重要性来衡量能采用的语言。 通常考虑的因素有 ① 项目的应用范围；② 算法和计算复杂性；③ 软件执行的环境；④ 性能上的考虑与实现的条件；⑤ 数据结构的复杂性；⑥ 软件开发人员的知识水平和心理因素等。其中，项目的应用范围是最关键的因素。 针对计算机的4个主要应用领域，为语言做一个粗略的分类。例如，在科学与工程计算领域内，C，C++ 语言得到了广泛的应用，但FORTRAN仍然是应用最广泛的语言。在商业数据处理领域中，通常采用COBOL，RPG语言编写程序，当然也可选用SQL语言或其它专用语言。在系统程序设计和实时应用领域中，汇编语言或一些新的派生语言，如BLISS，PL／S，Ada，C++等得到了广泛的应用。在人工智能领域以及问题求解，组合应用领域，主要采用LISP和PROLOG语言。 新的更强有力的语言，虽然对于应用有很强的吸引力，但是因为已有的语言已经积累了大量的久经使用的程序，具有完整的资料、支撑软件和软件开发工具，程序设计人员比较熟悉，而且有过类似项目的开发经验和成功的先例，由于心理因素，人们往往宁愿选用原有的语种。所以应当彻底地分析，评价，介绍新的语言，以便从原有语言过渡到新的语言。 5. 程序复杂性度量 程序复杂性主要指模块内程序的复杂性。它直接关联到软件开发费用的多少，开发周期的长短和软件内部潜伏错误的多少。同时它也是软件可理解性的另一种度量。 减少程序复杂性，可提高软件的简单性和可理解性，并使软件开发费用减少，开发周期缩短，软件内部潜藏错误减少。 (1) 代码行度量法 度量程序的复杂性，最简单的方法就是统计程序的源代码行数。此方法基于两个前提： ·程序复杂性随着程序规模的增加不均衡地增长； ·控制程序规模的方法最好是采用分而治之的办法。将一个大程序分解成若干个简单的可理解的程序段。 方法的基本考虑是统计一个程序模块的源代码行数目，并以源代码行数做为程序复杂性的度量。若设每行代码的出错率为每100行源程序中可能有的错误数目， 例如每行代码的出错率为1％，则是指每100行源程序中可能有一个错误。 Thayer曾指出，程序出错率的估算范围是从0.04％～7％之间，即每100行源程序中可能存在0.04～7个错误。他还指出，每行代码的出错率与源程序行数之间不存在简单的线性关系。Lipow进一步指出，对于小程序，每行代码的出错率为1.3％～1.8％； 对于大程序，每行代码的出错率增加到2.7％～3.2％之间，但这只是考虑了程序的可执行部分，没有包括程序中的说明部分。Lipow及其他研究者得出一个结论：对于少于100个语句的小程序，源代码行数与出错率是线性相关的。随着程序的增大，出错率以非线性方式增长。所以，代码行度量法只是一个简单的，估计得很粗糙的方法。 (2) McCabe度量法 McCabe度量法是一种基于程序控制流的复杂性度量方法。McCabe定义的程序复杂性度量值又称环路复杂度，它基于一个程序模块的程序图中环路的个数。 如果把程序流程图中每个处理符号都退化成一个结点，原来联结不同处理符号的流线变成连接不同结点的有向弧，这样得到的有向图就叫做程序图。 计算有向图G的环路复杂性的公式： V (G)＝m－n＋2 其中，V（G）是有向图G中的环路个数，m是图G中有向弧个数，n是图G中结点个数。 以图4.3为例，其中，结点数n＝11，弧数m＝12，则有 V（G）＝m－n＋2＝12－11＋2＝3。即McCabe环路复杂度度量值为3。 它也可以看做由程序图中的有向弧所封闭的区域个数。 当分支或循环的数目增加时，程序中的环路也随之增加，因此McCabe环路复杂度度量值实际上是为软件测试的难易程度提供了一个定量度量的方法，同时也间接地表示了软件的可靠性。实验表明，源程序中存在的错误数以及为了诊断和纠正这些错误所需的时间与McCabe环路复杂度度量值有明显的关系。 Myers建议，对于复合判定，例如（A＝0）∩（C＝D）∪（X＝'A'）算做三个判定。 利用McCabe环路复杂度度量时，有几点说明。 ( 环路复杂度取决于程序控制结构的复杂度。当程序的分支数目或循环数目增加时其复杂度也增加。环路复杂度与程序中覆盖的路径条数有关。 ( 环路复杂度是可加的。例如，模块A的复杂度为3，模块B的复杂度为4，则模块 A与模块B的复杂度是7。 ( McCabe建议，对于复杂度超过10的程序，应分成几个小程序，以减少程序中的错误。Walsh用实例证实了这个建议的正确性。他发现，在McCabe复杂度为10的附近，存在出错率的间断跃变。 ( McCabe环路复杂度隐含的前提是：错误与程序的判定加上例行子程序的调用数目成正比。而加工复杂性、数据结构、录入与打乱输入卡片的错误可以忽略不计。 (3) Halstead的软件科学 Halstead软件科学研究确定计算机软件开发中的一些定量规律，它采用以下一组基本的度量值，这些度量值通常在程序产生之后得出，或者在设计完成之后估算出。 ① 程序长度，即预测的Halstead长度 令n1表示程序中不同运算符（包括保留字）的个数，令n2表示程序中不同运算对象的个数，令H表示“程序长度”，则有 H = n1 ( log2 n1 + n2 ( log2 n2 这里，H是程序长度的预测值，它不等于程序中语句个数。在定义中，运算符包括： 算术运算符 赋值符（= 或 := ） 数组操作符 逻辑运算符 分界符（，或 ；或 : ） 子程序调用符 关系运算符 括号运算符 循环操作符等。 特别地，成对的运算符，例如“BEGIN…END”、“FOR…TO”、“REPEAT …UNTIL”、“WHILE…DO”、“IF…THEN…ELSE”、“（…）”等都当做单一运算符。 运算对象包括变量名和常数。 ② 实际的Halstead长度 设N1为程序中实际出现的运算符总个数，N2为程序中实际出现的运算对象总个数， N为实际的Halstead长度，则有 N = N1 + N2 ③ 程序的词汇表 Halstead定义程序的词汇表为不同的运算符种类数和不同的运算对象种类数的总和。若令n为程序的词汇表，则有 n = n1 + n2 图4.4是用FORTRAN语言写出的交换排序的例子。 SUBROUTINE SORT（X，N） DIMENSION X（N） IF（N .LT. 2） RETURN DO 20 I = 2, N DO 10 J = 1, I IF （X（I）.GE. X（J）） GO TO 10 SAVE = X（I） X（I）= X（J） X（J）= SAVE 10 CONTINUE 20 CONTINUE RETURN END 图4.4 一个交换排序程序的例子 因此有： 预测的词汇量 H = n1 ( log2 n1 + n2 ( log2 n2 = 10 ( log2 10 + 7 ( log2 7 = 52.87 实际的词汇量 N = N1 + N2 = 28 + 22 = 50 程序的词汇表 n = n1 + n2 = 10 + 7 = 17 ④ 程序量V，可用下式算得 V = ( N1 + N2 ) ( log2 ( n1 + n2 ) 它表明了程序在“词汇上的复杂性”。其最小值为 V* = ( 2 + n2*) ( log2 ( 2 + n2* ) 这里，2表明程序中至少有两个运算符：赋值符“:=”和函数调用符“f ( )”，n2* 表示输入／输出变量个数。对于图4.4的例子，利用n1，N1，n2，N2，可以计算得 V = ( 28 + 22 ) ( log2 ( 10 + 7 ) = 204 等效的汇编语言程序的V＝328。这说明汇编语言比FORTRAN 语言需要更多的信息量（以bit表示）。 ⑤ 程序量比率（语言的抽象级别） L = V*∕V 或 L = ( 2∕n1 ) ( ( n2∕N2 ) 这里，N2 = n2 ( log2 n2。它表明了一个程序的最紧凑形式的程序量与实际程序量之比，反映了程序的效率。其倒数 D = 1∕L 表明了实现算法的困难程度。有时，用L表达语言的抽象级别，即用L衡量在表达程序过程时的抽象程度。对于高级语言，它接近于1，对于低级语言，它在0～1之间。下面列出的是根据经验得出的一些常用语言的语言抽象级别。 语 言  L的平均值   English Prose（英语散文） PL/1 ALGOL68 FORTRAN Assembler（汇编语言） 2.16 1.53 2.12 1.14 0.88   ⑥ 程序员工作量 E = V∕L ⑦ 程序的潜在错误 Halstead度量可以用来预测程序中的错误。 认为程序中可能存在的差错应与程序的容量成正比。因而预测公式为 B = ( N1 + N2 ) ( log2 ( n1 + n2 )∕3000 = V∕3000 B表示该程序的错误数。例如，一个程序对75个数据库项共访问1300次，对150个运算符共使用了1200次，那么预测该程序的错误数： B = ( 1300 + 1200 ) ( log2 ( 75 + 150 )∕3000 = 6.5 即预测该程序中可能包含6～7个错误。 ⑧ Halstead的重要结论之一是：程序的实际Halstead长度N可以由词汇表n算出。即使程序还未编制完成，也能预先算出程序的实际Halstead长度N， 虽然它没有明确指出程序中到底有多少个语句。 这个结论非常有用。经过多次验证，预测的Halstead长度与实际的Halstead长度是非常接近的。 Halstead度量是目前最好的度量方法。 但它也有缺点： ( 没有区别自己编的程序与别人编的程序。这是与实际经验相违背的。这时应将外部调用乘上一个大于1的的常数Kf（应在1～5之间，它与文档资料的清晰度有关）。 ( 没有考虑非执行语句。补救办法：在统计n1、n2、N1、N2时，可以把非执行语句中出现的运算对象，运算符统计在内。 ( 在允许混合运算的语言中，每种运算符必须与它的运算对象相关。如果一种语言有整型、实型、双精度型三种不同类型的运算对象，则任何一种基本算术运算符（＋、－、×、／）实际上代表了 种运算符。如果语言中有4种不同类型的算术运算对象， 那么每一种基本算术运算符实际上代表了种运算符。 在计算时应考虑这种因数据类型而引起差异的情况。 ( 没有注意调用的深度。Halstead公式应当对调用子程序的不同深度区别对待。在计算嵌套调用的运算符和运算对象时，应乘上一个调用深度因子。这样可以增大嵌套调用时的错误预测率。 ( 没有把不同类型的运算对象，运算符与不同的错误发生率联系起来，而是把它们同等看待。例如，对简单IF语句与WHILE语句就没有区别。实际上，WHILE语句复杂得多，错误发生率也相应地高一些。 ( 忽视了嵌套结构（嵌套的循环语句、嵌套IF语句、括号结构等）。一般地，运算符的嵌套序列，总比具有相同数量的运算符和运算对象的非嵌套序列要复杂得多。解决的办法是对嵌套结果乘上一个嵌套因子。 三、例题分析 【例1】下图是使用Basic语言编写的一个打印A，B，C三数中最小者的程序的流程图。其中出现了6个GOTO语句，一个向前，5个向后，程序可读性很差。 if ( A < B ) goto 120; if ( B < C ) goto 110; 100 print C; goto 140; 110 print B; goto 140; 120 if ( A < C ) goto 130; goto 100; 130 print A; 140 试利用基本控制结构，将程序中的GOTO语句消去。 答案：使用if - then - else结构化构造，则上述程序段可改成如下形式。 if ( A < B and A < C ) then print A else if ( A >= B and B < C ) then print B else print C; 分析：理清程序流程图中每一条执行路径，适当利用复合的条件测试于判断语句，对每一个最终的打印处理，保留一个分支进入它。这样可以消除众多的GOTO语句，甚至可以消除嵌套的判断语句结构。这种程序结构清晰，可读性好。 【例2】设在闭区间 [a..b] 上函数F(X) 有唯一的一个零点，如下图所示。下面给出一个用C语言写出的程序段，用二分法求方程F(X)＝0 在区间 [a..b] 中的根。程序段中X0、X1 是当前求根区间 [X0..X1] 的下上界，Xm是该区间的中点，eps 是一个给定的很小正数，用于迭代收敛的判断。在程序中采取了用goto语句和标号finish控制在循环中途转出循环。 〖程序〗 F0 = F (a); F1 = F (b); if ( F0 * F1 <= 0 ) { X0 = a; X1 = b; for ( i = 1; i <= n; i++) { Xm = (X0 + X1) / 2; Fm = F(Xm); if ( abs (Fm) < eps || abs (X1－X0) < eps ) goto finish; if ( F0 * Fm > 0 ) { X0 = Xm; F0 = Fm; } else X1 = X; } finish： printf (“\n The root of this equation is %d\n”，Xm ); } 这类循环结构出现了两个循环出口。一个是for循环的正常出口：当循环控制变量i超出了循环终值n时退出循环；另一个是for循环的非正常出口：当某种条件满足时，从循环中间某处转出循环，执行循环后面的语句。它不满足结构化的要求。 试利用结构化程序设计要求的几种基本控制结构，消除其中的goto语句，使得每一个部分都是单入口单出口。 答案：利用一个布尔变量finished（该变量的初值为false），当循环中求到了要求的结果时，将此变量的值改变为true，表示循环应结束，while 循环测试到finished为true，就自动退出循环，执行后续的语句。 〖程序〗 F0 = F(a); F1 = F(b); if ( F0 * F1 <= 0 ) { X0 = a; X1 = b; i = 1; finished = 0; /* 设置控制循环结束的布尔变量 */ while ( i <= n && finished == 0 ) { /* 单入口单出口 */ Xm = (X0 + X1) / 2; Fm = F(Xm); if ( abs(Fm) < eps | | abs(X1－X0) < eps ) finished = 1; if ( finished == 0) { if ( F0 * Fm > 0 ) { X0 = Xm; F0 = Fm; } else X1 = X; } } } 分析：此程序段中各种结构均为单入口与单出口，且没有goto语句，可以说它是一个结构化的程序。它的结构很简单，只有一重循环，但由于引入一个布尔变量来控制循环结束，可读性比较差。在只有一重循环的情形，差的程度还不很明显，在多重循环的情形，引入多个布尔变量，可读性就很差了。理解程序的时间差几倍到几十倍不止。因此，对于这种单入口多出口的循环，R.S.Pressman明确说明，用goto语句可得到较好的清晰性。在C中提供了一个可直接转向循环之后的语句break，使用它可获得较好的效果。 〖程序〗 F0 = F(a); F1 = F(b); /*区间两端点的函数值*/ if ( F0 * F1 <= 0 ) { /*区间中没有根，不做*/ X0 = a; X1 = b; /*设置当前求根区间的两个端点*/ for ( i = 1; i <= n; i++) { /*最多允许迭代n次*/ Xm = (X0 + X1) / 2; Fm = F(Xm); /*求中点及中点的函数值*/ if ( abs(Fm) < eps | | abs(X1－X0) < eps) break; /*求到, 转出循环*/ if ( F0 * Fm > 0 ) /*没有求到，缩小求根区间*/ { X0 = Xm; F0 = Fm; } /*向右缩小区间*/ else X1 = X; /*向左缩小区间*/ } } 这段程序不是结构化的程序，利用了C语言中的一个语句break，它的功能是将控制转移到它所在循环的后面第一个后续语句处。由于将转移语句与转出条件的判断直接联系在一起，可读性较好。 【例3】试说明下面的两个程序段的功能是什么？可否用另一些等效的程序段来代替它，以提高其可读性。 (1) A[I] = A[I] + A[T]; (2) for ( i = 1; i <= n; i ++ ) A[T] = A[I] - A[T]; for ( j = 1; j <= n; j ++ ) A[I] = A[I] - A[T]; V[i][j] = ( i / j ) * ( j / i ); 答案：(1) 的功能是对换A[I] 与A[T] 的内容。等效的程序段可以是： WORK = A[T]; A[T] = A[I]; A[I] = WORK; (2) 的功能是建立一个单位矩阵V。等效的程序段可以是： for ( i = 1; i <= n; i ++ ) for ( j = 1; j <= n; j ++ ) if ( i == j ) V[i][j] = 1; else V[i][j] = 0; 分析：阅读这两段程序，读者可能不易看懂，有时还需用实际数据试验一下。对于(1)，如果我们给A[I] 赋值3，给A[T] 赋值5，在运算后发现A[I] 中变成了5，A[T] 中变成了3。这段程序就是交换A[I] 和A[T] 中的内容。目的是为了节省一个工作单元。如果改一下： WORK = A[T]; A[T] = A[I]; A[I] = WORK; 就能让读者一目了然。 对于(2)，除法运算（／）在除数和被除数都是整型量时，其结果只取整数部分，而得到整型量。因此， i / j为0， 当i < j时 j / i为0， 当j < i时 得到的数组 V[i][j] = ( i／j ) * ( j／i ) = 0，当i ≠ j时 ( i／j ) * ( j／i ) = 1，当i ＝ j时 这样得到的结果V是一个单位矩阵。如果直截了当地说明作者的意图： if ( i == j ) V[i][j] = 1; else V[i][j] = 0; 让读者可以很容易地理解。所以，在程序设计时，应当首先考虑清晰性，不要玩技巧。 【例4】有一种循环结构，叫做N+1/2循环。其流程图如下所示。这种控制结构不属于基本控制结构：它既不是先判断型循环，又不是后判断型循环。试修改此流程图，将它改为用基本控制结构表示的等效的流程图。 答案：等效的控制流程图如下图中 (a) 所示。 分析：先判断型循环要求在进入循环体之前，先判断是否要继续执行此循环。因此，在这种控制结构的入口处应是一个判断语句。这种循环的循环体可能一次也不执行。参看图 (b)。 (a) 修改N+1/2循环 (d) 另一个方案 【例5】下面是两个程序流程图，试分别用N-S图和PAD表示之，并计算它们的McCabe复杂性度量。 答案：对应的N-S图如下。 对应PAD图如下。 McCabe复杂性度量都为3。 四、习题 【4-1】从下列关于模块化程序设计的叙述中选出5条正确的叙述。 ① 程序设计比较方便，但比较难以维护。 ② 便于由多个人分工编制大型程序。 ③ 软件的功能便于扩充。 ④ 程序易于理解，也便于排错。 ⑤ 在主存储器能够容纳得下的前提下，应使模块尽可能大，以便减少模块的个数。 ⑥ 模块之间的接口叫做数据文件。 ⑦ 只要模块之间的接口关系不变，各模块内部实现细节的修改将不会影响别的模块。 ⑧ 模块间的单向调用关系叫做模块的层次结构。 ⑨ 模块越小，模块化的优点越明显。一般来说，模块的大小都在10行以下。 【4-2】结构化程序设计有时被错误地称为“无GOTO语句”的程序设计。请说明为什么会出现这样的说法，并讨论环绕着这个问题的一些争论。 【4-3】从下面关于程序编制的叙述中，选出三条正确的叙述。 ① 在编制程序之前，首先必须仔细阅读给定的程序说明书。然后，必须如实地依照说明书编写程序。说明书中常会有含糊不清或难以理解的地方。程序员在作业时应该对这些地方作出适当的解释。 ② 在着手编制程序时，重要的是采用既能使程序正确地按设计说明书进行处理，又易于出错的编写方法。 ③ 在编制程序时，首先应该对程序的结构充分考虑，不要急于开始编码，而要象写软件文档那样，很好地琢磨程序具有什么样的功能，这些功能如何安排等等。 ④ 考虑到以后的程序变更，为程序编写完整的说明书是一项很重要的工作。只要有了完整的程序说明书，即使程序的编写形式难以让他人看懂也没有什么关系。 ⑤ 编制程序时不可缺少的条件是，程序的输入和输出数据的格式都应确定。其他各项规定都是附带的，无足轻重。 ⑥ 作为一个好的程序，不仅处理速度要快，而且易读易修改等等也都是重要的条件。为了能得到这样的程序，不仅要熟悉程序设计语言的语法，还要注意采用适当的规程和单纯的表现方法，注意使整个程序的结构简洁。 【4-4】从下列叙述中选出5条符合程序设计风格指导原则的叙述。 ① 嵌套的重数应加以限制。 ② 尽量多使用临时变量。 ③ 不滥用语言特色。 ④ 不用可以省略的括号。 ⑤ 使用有意义的变量名。 ⑥ 应尽可能把程序编得短些。 ⑦ 把常见的局部优化工作留给编译程序去做。 ⑧ 注解越少越好。 ⑨ 程序的格式应有助于读者理解程序。 ⑩ 应尽可能多用GOTO语句。 【4-5】从供选择的答案中选出应该填入下面 ( ) 中的正确答案。 A. 允许用户建立、修改、存储正文的计算机程序是 ( )。 ① BOOtstrap ② Editor ③ Loader ④ Textformatter B. 程序语言的编译系统和解释系统相比，从用户程序的运行效率来看 ( )。 ① 前者运行效率高 ② 两者大致相同 ③ 后者运行效率高 ④ 不能确定 C. FORTRAN语言的源程序是 ( ) 结构。 ① 块状 ② 分程序嵌套 ③ 既是块状，又是嵌套 ④ 既不是块状，又不是嵌套的 D. 国际上最广泛使用的商用及行政管理语言是 ( )。 ① COBOL ② BASIC ③ FORTRAN ④ PL/1 E. 国际上最流行的数值计算的程序设计语言是 ( )。 ① BASIC ② ALGOL ③ FORTRAN ④ C F. 美国国防部主持开发了高级程序设计语言Ada，在它研制开始时，经反复比较，确定以高级语言 ( ) 作为Ada研究的出发点。 ① LISP ② ALGOL ③ ALGOL68 ④ PL/1 G. 在人工智能领域，目前最广泛使用的高级语言是 ( )。 ① Ada ② FORTRAN ③ COBOL ④ LISP 【4-6】从供选择的答案中选出应该填入下面 ( ) 中的正确答案。 A. 汇编程序是指 ( )。 ① 用汇编语言写的程序 ② 符号程序 ③ 汇编语言的处理程序 B. 为了实现递归子程序的正确调用，人们必须用 ( ) 来保存 ( ) 及有关信息。 ① 堆栈 ② 线性表 ③ 队列 ④ 树 ⑤ 入口点 ⑥ 返回地址 ⑦ 断点 C. UNIX操作系统是 ( ) 研制的，它是用程序语言 ( ) 书写实现的。 ① Bell实验室 ② DEC公司 ③ IBM公司 ④ PASCAL ⑤ 并发PASCAL ⑥ MODULA ⑦ C 【4-7】下面给出一个求实函数方程F(x)在自变量区间 [a, b] 中的全部实根的算法。首先阅读此程序，然后 (1) 画出消去全部goto语句的结构化程序流程图。 (2) 将它改成N_S图。 (3) 计算该程序的McCabe复杂性度量。 在算法中，a与b是区间[a, b]的两端点值；eps1与eps2是用户要求的求解精度。如果区间中点的函数值的绝对值小于eps1或新的小区间的长度小于eps2，就认为这个中点为根。 float BinRoot ( float a, float b, float eps1, float eps2 ) { float low= a, high = b, mid, fmid; float flow = Func(low), fhigh := Func(high); label L1, L2, L3; //标号说明，给定某些程序地址 if ( flow * fhigh > 0.0 ) { BinRoot = 0; goto L3; } //无实根 L1: mid = (low + high) / 2; fmid = Func(mid); if ( abs ( fmid ) <= eps1 ) { L2: BinRoot = mid; goto L3; } else if ( high - mid <= eps2 ) goto L2; else if ( flow * fmid > 0.0 ) { low = mid; flow = fmid; goto L1; } else { high = mid; goto L1 }; L3: } 【4-8】从供选择的答案中选出适当的字句填入下面关于程序生产率的描述中的 ( ) 内。 (1) 1960年底Dijkstra提倡的 ( A ) 是一种有效的提高程序设计效率的方法。 (2) Dijkstra为了使程序结构易于理解，把基本控制结构限于顺序、( B )、( C ) 3种，应避免使用 ( D )。 (3) ( A ) 不仅提高程序设计的生产率，同时也容易进行程序的 ( E )。 供选择的答案： A. ① 标准化程序设计 ② 模块化程序设计 ③ 多道程序设计 ④ 宏语言 ⑤ 结构化程序设计 ⑥ 汇编语言 ⑦ 表格处理语言 B, C. ① 分支 ② 选择 ③ 重复 ④ 计算 ⑤ 输入输出 D. ① GOTO语句 ② DO语句 ③ IF语句 ④ REPEAT语句 E. ① 设计 ② 调试 ③ 维护 ④ 编码 【4-9】用某种软件复杂性度量算法来度量不同类型的程序时，得出的度量值是否真正反映了它们的复杂性? 如果对同类型的程序进行度量，其结果是否就比较有价值? 【4-10】软件复杂性有哪几类？软件复杂性度量模型应遵循哪些基本原则？ 五、习题解答 【4-1】正确的叙述有②、③、④、⑦、⑧。如果程序结构的模块化满足评价的标准（高内聚，低耦合），这样的结构是容易编码，容易测试，容易理解，容易修改，容易维护的。程序的功能也容易扩充。特别适合于大型程序编制时，多人分工合作，协同完成任务的情形。因为是采用自顶向下，逐层分解来划分模块结构的，所以模块之间的调用关系是分层次的模块结构，就叫做模块的层次结构。模块之间的信息传递叫做模块的接口，模块之间传递信息可以通过参数表、全局变量或全局数据结构、数据文件、专门的通信模块，不是专指数据文件。划分模块时，模块大小要适中。模块太大，控制路径数目多、涉及的范围广、变量的数目多、总体复杂性高，可理解性、可修改性、可靠性就会变差。模块太小，模块个数增大，调用的系统开销就会增大。所以要有一个权衡。 【4-2】早在1963年，针对当时流行的ALGOL语言，Peter Naur指出，在程序中大量地，没有节制地使用GOTO语句，会使程序结构变得非常混乱。但是很多人还不太注意这一问题。以致许多人写出来的程序仍然是纷乱如麻的。 1965年，E.W.Dijkstra在一次会议上提出，应当把GOTO语句从高级语言中取消。并指出，程序的质量与程序中包含的GOTO语句的数量成反比。在这种思想的影响下，当时新开发的几种高级程序设计语言，例如LISP、ISWIM、BLISS等，都把GOTO语句取消了。 1966年，Bohm与Jacopini证明了任何单入口单出口的没有“死循环”的程序都能由三种最基本的控制结构构造出来。这三种基本控制结构就是“顺序结构”、“选择IF－THEN－ELSE结构”、“重复DO－WHILE或DO－UNTIL结构”。 1968年，Dijkstra在写给<ACM>（美国计算机协会通讯）杂志编辑部的信中再次建议从一切高级语言中取消GOTO语句，只使用三种基本控制结构编写程序。他的建议引起了激烈的争论。争论集中在如何看待GOTO语句的问题上。赞成取消 GOTO 语句的一方认为，GOTO语句对程序清晰性有很大破坏作用，凡是使用GOTO语句多的程序，其控制流时而GOTO向前，时而GOTO向后，常使程序变得很难理解，从而增加查错和维护的困难，降低程序的可维护性。但以D.E.Knuth为代表的另一方认为，GOTO 语句虽然存在着破坏程序清晰性的问题，但不应完全禁止。因为GOTO语句概念简单，使用方便，在某些情况下，保留GOTO语句反能使写出的程序更加简洁，并且GOTO语句可直接得到硬件指令的支持。经过争论，人们认识到，不是简单地去掉GOTO语句的问题，而是要创立一种新的程序设计思想、方法和风格，以显著提高软件生产率和软件质量，降低软件维护的成本。 70年代初N.Wirth在设计Pascal语言时对GOTO语句的处理可被当做对GOTO 语句争论的结论。在Pascal语言中设置了支持上述三种基本控制结构的语句；另一方面，GOTO语句仍然保留在该语言中。不过，N.Wirth解释说，通常使用所提供的几种基本控制结构已经足够，习惯于这样做的人不会感到GOTO语句的必要。也就是说，在一般情况下，可以完全不使用GOTO语句。如果在特殊情况下，由于特定的要求，偶然使用GOTO语句能解决问题，那也未尝不可，只是不应大量使用罢了。 事实上，大量采用GOTO语句实现控制路径，会使程序路径变得复杂而且混乱，从而使程序变得不易阅读，给程序的测试和维护造成困难，还会增加出错的机会，降低程序的可靠性。因此要控制GOTO语句的使用。但有时完全不用GOTO语句进行程序编码，比用GOTO语句编出的程序可读性差。例如，在查找结束时，文件访问结束时，出现错误情况要从循环中转出时，使用布尔变量和条件结构来实现就不如用GOTO语句来得简洁易懂。 【4-3】①、④、⑥。编制程序的过程实际上是根据设计的结果，用某种机器能够识别的程序设计语言，将设计翻译成机器代码的过程。因此，必须如实地按照设计说明书编写程序。至于设计说明书中含糊不清的地方，应当在编程时与分析人员或设计人员协商，对这些地方做出适当的解释。另外，考虑到将来的程序修改，必须为程序编写完整的说明书，同时程序必须编写得容易让别人看得懂，这样程序才容易修改，修改时不容易出错，而且容易验证修改后得结果。还有，编写程序的人不须重新考虑程序要完成什么功能，这些已经在软件分析与设计过程中充分考虑过了。 【4-4】①、③、⑤、⑦、⑨是正确的。因为 ① 条件语句和循环语句嵌套得过多会增加程序的复杂性，从而增加程序的出错率。③ 虽然国际以至国内已经发表了编程语言的标准，但各个计算机厂商在推出自己的计算机系统的同时，也推出了针对自己机器特色的程序设计语言的非标准版本，如果利用这些语言的非标准特性编写程序，就会给将来程序的移植带来困难。为了提高程序的可移植性，应当只使用语言的标准版本，不要滥用语言的非标准特色。⑤ 给在程序中使用的变量赋予与实际含义相符的名字，可以提高程序的可读性，从而提高程序的可维护性。⑦ 程序优化的工作最好交给编译程序来做，程序员应把主要注意力放在提高程序的可读性、清晰性、简洁性、正确性、一致性等方面，从而保证软件的可靠性和可维护性。⑨ 程序的可读性是至关重要的。所以程序的格式应有助于读者理解程序。 【4-5】A. ②, B. ①, C. ①, D. ①, E. ③, F. ②, G. ④ 除以上几种论述外，其它的叙述都不对。例如，程序中加入临时变量，可能会改变程序执行中的时序关系，造成程序出错。在表达式中加入括号，可以明确标明表达式的运算优先关系，避免因语言方面的原因可能潜藏的错误。程序模块的大小要适中，不是编得越短越好。注解加多少，由问题得难度来决定，但决不是可有可无的。最后要限制GOTO 语句的使用，因为它可能会造成思路混乱、极易出错。 A.计算机用户通常是使用“编辑程序（Editor）”对源程序文本进行录入、编辑、存储的，不用自举程序（Bootstrap）、连接程序（Loader）或文本格式化程序（Textformatter）。 B. 解释系统是边解释源程序边执行该源程序，编译程序是先编译出源程序的对应目标代码，再执行这些目标代码。所以编译程序编出的目标代码运行效率高。 C. FORTRAN程序是以SUBROUTINE为单元的块状结构，对每一个SUBROUTINE进行编译后通过连接形成整个程序系统。它不是嵌套的。 D. 国际上最流行的商业和行政管理语言是COBOL语言。 E. 国际上最流行的用于数值计算的语言是FORTRAN语言。 F. 美国国防部主持开发高级程序设计语言Ada时，曾确定以ALGOL语言作为Ada研究的出发点。所以，Ada、ALGOL、Pascal、BASIC和C都是ALGOL系的一些程序语言。 G. 在人工智能领域，目前最广泛使用的高级语言是Lisp。 【4-6】A. ③ B. ①、⑥ C. ①、⑦ A. 汇编程序实际是指汇编语言的处理程序。而用汇编语言写成的源程序一般称为汇编语言程序。 B. 为了实现递归子程序的正确调用，一般使用堆栈来保存每次调用后返回到上一层程序的返回地址、本次递归调用时的形式参数、局部变量等。 C. UNIX操作系统是Bell实验室研制的，用C语言写出来的。 【4-7】(1) 结构化的程序流程图： (2) N-S图： (3) 环路复杂性度量 V(G) = 6 【4-8】A. ⑤, B. ②, C. ③, D. ①, E. ③ 1960年Dijkstra提倡的结构化程序设计方法，反对（后来改为尽量避免）在程序中使用GOTO语句，认为使用顺序、选择、重复等三种基本控制结构进行组合、嵌套，就可以构造出整个程序。这种程序设计方法可以提高程序的生产率，还有利于将来程序的维护。 【4-9】开发规模相同，但复杂性不同的软件，花费的成本和时间会有很大的差异。因此到目前为止，还没有一个软件复杂性度量的方法能够全面、系统地度量任一软件的复杂性，某一种度量方法只偏重于某一方面。所以，用某一种软件复杂性来度量不同类型的程序，所得到的度量值不一定真正反映它们的复杂性。但对同一类型的程序，按某种视点来度量它们的复杂性，其结果还是比较有价值的。 【4-10】K.Magel从六个方面描述软件复杂性： ① 理解程序的难度； ② 改错及维护程序的难度； ③ 向他人解释程序的难度； ④ 按指定方法修改程序的难度； ⑤ 根据设计文档编写程序的工作量； ⑥ 执行程序时需要资源的程度。 软件复杂性度量模型应遵循的基本原则： ⑴ 软件复杂性与程序大小的关系不是线性的； ⑵ 控制结构复杂的程序较复杂； ⑶ 数据结构复杂的程序较复杂； ⑷ 转向语句使用不当的程序较复杂； ⑸ 循环结构比选择结构复杂，选择结构又比顺序结构复杂； ⑹ 语句、数据、子程序和模块在程序中的次序对软件复杂性都有影响； ⑺ 全程变量、非局部变量较多时程序较复杂； ⑻ 参数按地址传递比按值传递更复杂； ⑼ 函数副作用比显式参数传递更难以琢磨； ⑽ 具有不同作用的变量共用一个名字时较难理解； ⑾ 模块间或过程间联系密切的程序较复杂； ⑿ 嵌套深度越深程序越复杂。 最典型的两种程序复杂性度量的方法中，McCabe环路复杂性度量就是针对基本原则(2)制定的度量模型；Halstead软件科学则是针对程序中操作符和操作数的出现频度而制定的度量模型。