代码大全(经典教材)-第十二章 复杂数据类型


第十二章 复杂数据类型 189 把标志转换独立在函数中。当你使用变换数据的方法来建立直接存取标志时,应把对数据 的转换操作放在函数中,函数的使用消除了在不同地方使用不同转换方法的可能性,当需要对 变换作改动时也非常容易。同时,要恰当地命名转换函数以清楚地说明使用函数的目的,比如 GetKeyFromAge()就是一个很好的名称。 还要把转换函数放入含有表定义和其它与表有关子程序的模块中。当转换函数与数据表距 离比较近时,如果要改动数据表的活,也比较容易想起改动转换函数。 12.2.3 变址存取 有时依靠简单的数字变换还不足把数据转换为直接存取标志。这时可以用变址存取方法解 决某些问题。 当使用变址时,首先用基本数据在变址表中找到一个标志,然后利用这个标志查找你感兴 趣的主要数据。 假设你在考虑一个存货问题, 并且其中有一张含有 100 项的清单, 每一项都含有一个在 0000 到 9999 之间的四位数。在这种情况下,如果你想用四位数作为标志来直接进入一个描述 了某一项某些方面的表,就要先建立一个有 10,000 个入口的变址数组。这一个数组中除了那些 与上述 100 个 4 位数相应的入口外,其余入口都是空的。如图 12-4 所表示的那样,这些入口指 向一个描述了清单中的项,但入口数要远远小于 10,000 的表。 图 12-4 变址存取 变址存取方法主要有三个优点。首先,如果主查寻表中每一个入口占用的空间都很大的话, 那么建立一个有许多空入口的变址表所浪费的空间要比建立有许多空入口的主查寻表浪费的空 间少得多。比如上例中如果主查寻表每个入口占用 10 个字书,而变址表每个入口占用 5 个字节 的话,就可以节约 (10-5)*9900=49500 个字节。 第二个优点是即使使用变址表没有节约空间, 对变址表中的入口进行操作也要比对主查 第十二章 复杂数据类型 190 寻表口进行操作容易得多。比如,假设有一个含有雇员姓名、雇佣日期和工资等信息的表,你 可以建立一个通过姓名来查寻主表的变址表,还可以建立一个工资查寻主表的变址表,而且你 也可以建立通过雇佣日期查寻主表的第三个变址表。 使用变址存取的第三个优点是表驱动方法所共有的良好维护性。存在表中的数据维护起来 要比淹没在代码中的数据容易得多。为了增强灵活性,可以把变址存取代码放在子程序中,当 你需要由数据得到一个直接存取标志时再调用这个子程序,当需要改动表时,对子程序中的变 址存取代码进行修改要比对散布在程序中的同样代码进行修改容易得多。 12.2.4 阶梯存取 另一种表存取方法是阶梯法。这种存取方法不如变址法直接,但要比变址法节约空间。 阶梯法的主要思想是如图 12-5 所示的阶梯结构,其核心是表中的入口对数据范围而不是 对不同数据点有效的。例如你正在编写一个评分程序,"B" 入口的取值范围可以是从 77.5%到 9 0%。下面是一些你可能遇到的评分范围: ≥90% A < 90.0% B < 77.5% C < 65.0% D < 50.0% F 这是一个很难用表来查寻的问题,因为你无法用一个简单的转换函数来得到从 A 到 F 的直 接存取标志。这对变址存取法来说也是比较困难的,因为上面的数都是浮点型的。或许你会考 虑把浮点型转化为整型,就这个问题而言,这样作是可行的。不过为了说明阶梯法,我们把解 决方案限制为只能用浮点型数。 图 12-5 阶梯活确定入口 使用阶梯法时,首先把每个范围的上界放入表中,然后用一个循环来查找超过每一个范围 上界的分数。当你找到某一分数第一次超过某一范围上界的地方时,也就知道了该分数应属于 哪一级。使用这一技术时,必须仔细而且恰当地处理每一个范围的边界。下面是一段给一组学 生的分数分级的 Basic 程序; 'set up data for grading table 第十二章 复杂数据类型 191 RangeLimit(1) = 50.0 Grade(1) = 'F' RangeLimit(2) = 65.0 Grade(2) = 'D' RangeLimit(3) = 77.5 Grade(3) = 'C' RangeLimit(4)= 90.0 Grade(4)= 'B' RangeLimit(5)= 100.0——这是范围边界 Grade(5) = 'A' MaxGradeLevel = 5 ... 'assign a grad to a student based on the student's score GradeLevel= 1 StudentGrade = ”A" while( StudentGrade = "A" and GradeLevel < MaxGradeLevel ) if( StudentScore < RangeLimit( GradeLevel ) ) then StudentGrade = Grade ( GradeLevel) end if GradeLevel = GradeLevel + 1 end 虽然这是一个非常简单的例子,你可以很容易地把它推广到多个学生、多等级方法(例如, 不同水平的分数对应不同的级)中。 阶梯方法优于其它表驱动方法之处,在于它比较善于处理不规则的数据。上面这个评分例 子的简单之处在于虽然不同等级之间间隔是不规则的,但是数据已经经过四舍五入了,其结尾 部是 0 或 5。阶梯法对于不是以 0 或 5 结尾的数也是同样有效的。你可以用阶梯法来处理统计 学中概率分布问题,比如下面的数据: 0.458747 $0.00 0.547651 $254.32 0.627764 $514.77 0.778883 $747.82 0.893211 $l,042.65 0.957665 $5,887.55 0.976544 $12,836.98 0.987889 $27,234.12 像这样不规则的数据是很难用函数把它们转换为直接存取标志的,但是用阶梯法却很容易 解决这个问题。 同时这种方法也具有表驱动方法的共同优点。它也是非常灵活而且容易更改的。如果上例 第十二章 复杂数据类型 192 中的分级范围要进行变动的话,只要改动 RangeLimit 数组中的入口就可以了。你可以很容易地 改动程序中等级赋值部分,以使得它可以接受不同级和相应的分数范围的表。在程序中把分数 转换成了百分数,事实上你也可以直接使用自然分数而不必将其转换为百分数。 以下是在使用阶梯法时应该注意的几个问题: 注意边界。要保证已经把每一台阶范围的上界值都考虑在内了。使用阶梯搜寻法来找出所 有不在最高一级范围内的值,然后把剩下的值全部归入最高一级中。有时候需要人为地为最高 一级范围添加一个上界。 同时应小心不要错误地用“<”来代替“<=”。要保证循环在找出属于最高一级范围内的 值后恰当地结束,同时也要保证恰当地处理了范围边界。 应使用交叉搜寻而不是顺序性搜寻。在上面的评分示例中,循环顺序地按照分级界限来进 行分级工作。如果表稍微大一些的话,进行顺序搜寻的代价将是非常巨大的。如果出现了这种 情况,你可以用“准交叉”搜寻来代替顺序搜寻,之所以称其为准交叉搜寻是因为绝大多数交 叉搜寻的目的都是为了寻找某个值。而在这种情况下,你想找到的是值属于的类别而不是值本 身。在交叉搜寻算法中,必须正确地决定值的归宿,同时,也要特别注意考虑边界问题。 考虑使用变址存取方法来代替阶梯存取法。有时使用变址存取法来代替阶梯存取法会更好 。阶梯法中所需要的搜寻是时间累积的,如果运算速度是你考虑的重点的话,可以考虑用变址 法来代替阶梯法,即以牺牲空间为代价来换取速度。 显然,并不是在所有情况下这种替换都是可行的。在评分的例子中或许这是可行的。如果 只有一百个待分级的分数,并且这些分数也比较规则的话,建立一个变址表并不会占用太大的 内存,因而是可能的。但是如果分数是很不规则的,则无法使用变址法。因为你无法用这种方 法进入存有 0.458747 或 0.513392 这类数的入口。 在很多情况下往往几种方法都是可行的。这时设计的要点是从几种方法中选出一种适用的, 而不是过多地考虑从中选择出一种最好的。找到一种较好的方法,并避免灾难性的后果,往往 比竭力找出最好的方法要实用,也合适得多。 最后一点应注意的是把阶梯表放入它自己的子程序中。 12.2.5 其它的表查寻的例子 在本书的其它章节中出现了一些表查寻的例子。在那些地方使用它们的目的是为了强调其 它观点而不是为了强调表查寻本身,下面是它们所在的章节: · 在保险表中查寻保险费用:见 15.3 节 · 在表查寻中查找的代价:见 28.3 节 · 逻辑变量的值(A 或 B或 C):见 29.2 节 · 贷款偿还表中的计算:见 29. 4 节 12.3 抽象数据类型(ADTS) 抽象数据类型是由数据及对数据的操作组成的。这些操作既向程序的其余部分描述了数 据,也允许程序其余部分改变它所描述的数据。在“抽象数据类型”中的数据指的是广义的数 据。抽象数据类型可能是图形窗口及影响该窗口的操作,也可能是一个文件及对文件的操作。 第十二章 复杂数据类型 193 甚至还可能是一个保险费用表及对该表的操作。 抽象数据类型通常是作为模块来实现的。模块和抽象数据类型都是数据以及对数据进行的 操作的组合。要想详细了解模块的问题,请参阅第六章。 通常关于编程的课本在讲到抽象数据类型时往往会让人感到味同嚼蜡。他们总是喜欢这样 说:“你可以把抽象数据类型当作一个有许多操作来定义的数学模型。”接着,便是一些令人厌 烦的关于如何编写存取堆栈、队列或表的子程序的内容。这些书总是使人感到自己永远也不可 能方便地使用抽象数据类型。 这些关于抽象数据类型的干巴巴的解释根本没有说到点子上。抽象数据类型是应该令人激 动的,因为你用它们来解决的是客观世界中的实体问题,而不是计算机中的实体问题,你可以 向表格中加入一个空格,可以向窗口类型表中加入一个新的类型,也可以在特快列车上加挂一 节车厢而不是向链表结构中加入一个结点。不要低估了应在问题域而不是在计算机域中工作这 一准则的威力。这并不是说你不应该用抽象数据类型来实现堆栈、队列和表。你应该这样做。 但是抽象数据在客观世界问题中的威力要比在课本中讲的要强大得多。 12.3.1 需要用到抽象数据类型的例子 下面是一些需要用到抽象数据类型的情形。我们将在首先讨论这些具体情况之后再来看一 下抽象数据类型(ADT)的具体理论。 假设你正在编写一个用一系列打印页、点阵规模和字体来控制向屏幕输出的程序,程序中 的一部分要对字体进行操作。如果你使用抽象数据类型(ADT)的话,那么就需要把一组字体 子程序和它们作用的数据——打印页名称、点阵大小和字体属性组成一个集合。这个由字体子 程序及其数据组成的集合,就是一个抽象数据类型(ADT)。 如果不用抽象数据类型(ADT)的话,你就不得不用麻烦得多的方法来操作字体。比如, 你需要把字体改为 12 点阵的,那么你很可能要用如下的代码: CurrentFont.Size = 12 如果要在程序中的几个地方改变点阵规模,那么在程序中就会有许多类似的代码散布其中。 如果你要把字体置为黑体的话,可能要使用如下的语句: CurrentFont.Attribute = CurrentFont.Attribute or 02h 如果你很幸运的话,实际代码行可能会比上面的简单一些,但最好也只能是下面这个样子: CurrentFont.Bold =True 采用这种方法来编程的话,那么在程序中就会在许多地方出现非常类似的代码行,而且如 果你要设置打印页名称的话,你将使用如下的代码: CurrentFont.Typeface = TIMES_ROMAN 12.3.2 使用抽象数据类型的好处 这并不是说上面的编程方法是不好的。但是我们可以用更好的编程方法来代替它,从而获 得很多收益,何乐而不为呢? 下面就是使用抽象数据类型的一些优点: 第十二章 复杂数据类型 194 可以隐含实现细节。对字体数据的信息隐蔽意味着当需要变动字体时,你只需在程序中的 某一处作出改动而不会影响程序的其它地方。比如你如果不用抽象数据类型的话,那么在需要 改动字体时,你就不得不在程序中每一个设置了字体的地方进行修改,而不是只在一处进行修 改。如果进行了信息隐蔽,那么即使你想把数据从存在内存改为存放在外部文件中,或是想用 其它语言重写全部字体子程序,也不会对程序其余部分产生什么影响。 把改动的影响限制在局部。如果你需要更加丰富的字体,并且要支持更多的操作时,只需 在一处作出改动就可以了,程序的其余部分将不受影响。 更容易改进性能。如果你需要改进字体性能的话,只要修改几个已经明确定义的子程序就 可以了,而不必在整个程序中到处进行修改。 减少修改时犯错误的可能性。通过使用抽象数据类型,你可以用对子程序 SetCurrentFont ToBold()简单修改,来代替对 CurrentFont.Attribute= CurrentFont.Attribute or 02h 的语 句的复杂修改,从而减少了犯错误的地方有:使用了错误的结构名称、使用了错误的域名称或者 使用了错误的逻辑操作(比如误用了“and ”来代替“or”),还有可能使用了错误的属性值( 误用了 20h 而不是 02h);而在修改了程序时,你可能犯的唯一错误便是调用了错误的子程序, 而这个错误又是很容易发现的。 使程序成为自说明的。在上面的设置字体的语句中,你用 SetCurrentFontToBold()子程序 来代替原来语句所获得的可读性是不可同日而语的。 WoodField 和 Dumsmore 和 Shen 曾于 1981 年进行过如下实验:他们用两个内容相同的程序 —— 一个被分成 8 个按功能划分的子程序,而另一个被分成 8 个抽象数据类型子程序,对计算 机专业研究生和高年级本科生进行测试,结果接受抽象数据类型程序测试学生对程序的理解程 度要比另一组高出 30%。 避免了在程序中四处传递数据的麻烦。在前面的设置字体的例子中,如果不使用数据的话, 那么你将不得不直接改变 CurrentFont 的值,或者将其在每一个处理它的子程序中传递。而通 过使用抽象数据类型,你既不必把 CurrentFont 在程序中四处传递也不必使用全局数据。在抽 象数据类型中将有一个含有 CurrentFont 数据的结构,对这个结构只有在 ADT 内部的子程序才 能进行直接存取,而 ADT 之外的子程序则无需关心这个结构。 你可以直接处理客观世界中的实体而不是计算机专业的结构。通过使用抽象数据类型,你 可以对处理字体的操作进行定义,从而可以使程序的其余部分是以字体的名义来进行操作,而不 是以数组存取、记录定义或者逻辑变量的名义来进行操作。 在这种情况下,为了定义抽象数据类型,你将首先定义几个控制字体的子程序,很可能是 如下几个子程序: SetCurrentFonSize(size) SetCurrentFontToBold() SetCurrentFontToItalic() SetCurrentFontToRegular() SetCurrentFontToTypeFace(FaceName) 在这些子程序内部的代码,可能是非常短的,而且很可能与你所见到的不使用抽象数据类 型时的代码差不多。但它们的区别在于现在你可以把对字体的操作独立在一组子程序中, 从 而为程序其余与字体有关的部分提供了较高的抽象程度,而且也避免了在改动字体操作时影响 第十二章 复杂数据类型 195 程序的其余部分。把对数据的操作隐含在存取子程序后面相当于在宇宙飞船中加装的减压舱, 宇航员可以通过减压能进入太空,也可以再从太空通过减压舱回飞船。但飞船内的空气却不会 泄漏进太空。 12.3.3 关于抽象数据类型的其它例子 下面是关于抽象数据类型更多的例子: 假设你正在编写一个控制核反应堆冷却系统的软件,那么你可以通过定义下述操作而把 冷却系统处理成抽象数据类型: GetReactoTemperature() SetCirculationRate(Rate) OpenValue(ValueNumber) CloseValue(ValueNumber) 特定的环境将决定实现这些操作的具体代码,程序的其余部分将通过这些函数来处理这个 冷却系统,而不必担心数据结构实现细节、数据结构限制、改动等问题。 下面是关于抽象数据类型及对它的可能操作的例子: 表: 灯: 初始化表 开灯 在表中加入项 关灯 从表中去掉项 从表中读下一项 文件: 堆栈: 打开文件 初始化堆栈 读取文件 把项压入堆栈 写文件 从堆钱中弹出项 设置当前位置 读取栈顶 关闭文件 通过研究上述这些例子,我们可以得出几条准则: 把典型的计算机专业数据结构建为抽象数据类型。绝大多数关于抽象数据类型的讨论都集 中在把典型的计算机专业数据结构建为抽象数据类型。正如你从上面的例子中发现的,你可以 用抽象数据类型来代表堆栈、表等数据结构。 你需要提出疑问的是这些堆栈、表所代表的到底是什么?比如,如果堆栈所代表的是一组 雇员,那么应把抽象数据类型当作雇员而不是堆栈来处理。又比如假设表所代表的是一组帐单, 那么应把 ADT 作为帐单而不是作为表来对待。总之,应从尽可能高的抽象水平上来处理问题。 把常见的目标如文件等处理为抽象数据类型(ADT)。 绝大多数语言中都含有一些你可能 非常熟悉的抽象数据类型,只不过你没有意识到罢了。 文件操作就是一个很好的例子。当向磁 盘写文件时,操作系统会把读/写磁头放置在一个特定的物理地址上, 而在你放弃一个旧文件 时,又会分配一个新的磁盘扇区并查找交叉代码。 操作系统提供了一个低层次的抽象, 并提 供了这个层次的抽象数据类型, 高级语言将可能提供稍高一些的抽象出乎并可以提供更高层次 第十二章 复杂数据类型 196 的抽象数据类型。高级语言可以使你避免与复杂而繁琐的操作系统调用和数据缓冲区操作细节 打交道。这种能力可以使你把一段磁盘空间当作“文件”来处理。 与此类似,你也可能对抽象数据类型进行分层。如果你在数据结构操作层次(如压入或弹出 堆钱)上使用了抽象数据类型(ADT),那很好。接着,你可以在比它更高的层次上使用处理客观 世界真实问题的 ADT。 即使是简单的问题也应考虑使用抽象数据类型(ADT)。不要在碰到复杂得可怕的数据结构时 才考虑使用抽象数据类型。在使用 ADT 的示例表中有一个非常简单的例子——只有开灯和关灯 两个操作的灯控制问题。你可能会认为“开”和“关”两个操作过于简单了,不值得为它们分 别编写专门的子程序,但事实上,即使是简单的问题也可以因为使用 ADT 而受益。把对灯的操 作放入 ADT 中,可以提高代码的自我说明程度并区改善其易改动性,并把改动的影响限制在 Tu rn_Light_0n()和 Turn_Light_Off()两个子程序中,同时也降低了数据传递的工作量。 可以提供一对互补的操作。绝大多数操作都需要有与其相对应的、效果相反的操作。如果 有一个打开灯的操作,那么就需要一个关灯的操作。如果有向表中添加项的操作,那么就要有 从表中去除项的操作。因此,当你设计抽象数据类型时,应检查每一个功能以确定是否有与其 互补的功能。不要根据直觉,而是根据需要来决定是否设计互补功能。 应相对 ADT 所存储的介质独立地引用它。假设有一张非常大的保险费用表,你不得不把它 存储在磁盘中,你可能会把它作为一个“保险费用文件”,并且用诸如 ReadRateFile()之类的 存取子程序来访问它。但是,如果把它作为文件来处理的话,你就暴露了超过实际需要的信息。 如果你对程序作出改动,把保险费用表由存放在磁盘中改为存放在内存中,那么把它作为文件 来引用的代码就会变得不正确而且是令人困惑的了。应努力使存取子程序的名字与数据存取方 式是相互独立的,而且应该引用抽象数据类型如保险费用表。你应该用 ReadRateTable()来代 替 ReadRateFile()作为存取子程序的名称。 12.3.4 用 ADT 来处理多事件数据 如果你正在为 ADT 定义基本操作,可能会发现需要处理一种类型的几条而不是一条数据。 例如,在处理字体时,你可能需要跟踪许多字体。用 ADT 的术语来说,你所需要跟踪的每一种 字体都是一个“事件”。一种办法是建立几个分立的 ADT 来处理你要跟踪的每一个字体事件。但 更好的办法是用一个 ADT 来处理这个多事件字体数据。这通常意味着设计建立和取消事件及其 它功能,以便用它们来处理多事件数据。 字体 ADT 原来可能会包括如下功能: SetCurrentFontsize(size) SetCurrentFontToBold() SetCurrentFontToItalic() SetCurrentFontToRegular() SetCurrentFontToTypeFace(Face_Name) 如果你想一次不止处理一个事件,那么,需要加入如下的建立和取消字体事件的几个功能: CreateFont(FontID) DeleteFont(FontID) 第十二章 复杂数据类型 197 SetCurrentFont(FontID) 在其中引入了 FontID 这一符号,用它来作为建立和取消字体事件时的跟踪标志。至于其它 操作,你可以从处理 ADT 接口的三种方法中任选一种: 隐蔽地使用字体事件。设计一个新的函数来调用某一设置当前特定字体事件的函数——比 如 SetCurrentFont(FontID)。设置当前字体使其它函数在被调用时可能使用当前字体。当你用 这种方法时,可以不必把 FontID 作为其它函数的参数。 每次使用 ADT 函数时,显示识别事件。在某种情况下,你没有用来表示“当前字体”的符 号。使用 ADT 函数的子程序不必跟踪字体数据。但它们必须使用字体识别标志。这需要在每个 子程序中都加入 FontID 来作为参数。 显示提供 ADT 函数要用到的数据。用这种方法时,需要在每一个用到 ADT 函数的子程序内 部说明 ADT 所用数据。换句话说,你要建立一个传递到每一个 ADT 功能子程序中的 Font 数据结 构。同时,要把 ADT 功能子程序设计成每当它们被调用时,它们就会使用传入其中的 Font 数据。 这时,你不在需要使用字体识别标志,因为你跟踪的就是字体数据本身(虽然这种数据可以直接 从 Font 数据结构中得到,但你还是应该通过 ADT 功能子程序来存取它,这种方法称为把记录保 持为“封闭”的。将在后面详细讨论)。 这种方法的优点是 ADT 功能子程序不必根据字体识别标志来寻找字体信息。其缺点是这种 方法会使程序其余部分面临危险。因为数据是可以被直接存取的,所以它很容易被错误改动。 在抽象数据类型(ADT)内部,有许多种处理多事件数据的方法可供选择,但在 ADT 外部则只 有上述三种方法可供选择。 12.3.5 混合抽象级别(要避免!) 如果你只在 ADT 功能子程序内部才对数据结构进行存取,而且在程序其余各部分只通过 ADT 功能子程序来存取数据,那么你就保持了一致的抽象级别。如果不这样作,那么就产生了 混合抽象级别问题,这足以抵消由使用 ADT 而带来的所有好处。其直接后果是在修改程序时非 常容易犯错误。因为这时你会错误地以为修改了存取子程序便等于修改了程序中所有存取方式。 我们继续使用前面的飞船减压舱隐喻来说明问题:如果说 ADT 中的功能子程序相当于飞船 上减压船的话,那么对功能子程序的不一致使用就相当于在减压舱门上钻了个孔。这个孔可能 不至于使飞船中的空气一下了漏光,但是只要时间足够,它便足以毁掉整个飞船。在程序中如 果你使用了混合抽象级别,那么当你对程序进行修改时,程序便会变得越来越令人难以理解, 其功能会逐渐退化直至最后它成为完全无法维护的。 开放和封闭的记录 随着混合抽象级别而来的是“封闭”和“开放”记录的思想。当一个子程序直接用到了在 其中的记录或结构的任一个域时,便称这个域或结构是开放的:而如果记录或结构的任一个域 都没有被直接使用时,就称它是“封闭”的。向前面所提到的那样,你可以把使用封闭记录作 为处理多事件数据的一种方法。一个数据是可直接存取的这一事实,并不意味着你必须开放它。 除非是受到 ADT 功能了程序的限制,否则就该把记录保持为封闭的。 当你在用处理多事件数据的三种方法进行选择时,应选择 FontID 法而不是 FontRecord 第十二章 复杂数据类型 198 法。 12.3.6 抽象数据类型与信息隐蔽、模块和目标 抽象数据类型和信息隐蔽是互相联系的概念。当你使用 ADT 时,就已经隐蔽了它的实现细 节。这也正是从抽象数据类型通往信息隐蔽之路。当你使用信息隐蔽时,首先要寻找可以隐蔽 的内容。最明显的需要隐蔽的内容就是抽象数据类型(ADT)的实现细节。这也是从信息隐蔽通往 抽象数据类型的道路。 抽象数据类型这一概念与模块的思想也是相互联系的。在直接支持模块语言中,你可以在 模块中实现抽象数据类型。模块与抽象数据类型一样,都是由数据以及作用在数据上的操作组 成的。 抽象数据类型这一概念与目标的概念也是相互联系的。“目标”是一个比较广义的概念,但 它通常指的是数据及使用在数据上的操作。从这个观点来说,所有的目标都是抽象数据类型。 “目标”的思想事实上也利用了继承性和多形性的概念。把目标当作抽象数据类型的想法事实 上便是把继承性和多形性加到了一起。抽象数据类型只是目标思想的一部分而不是全部。 12.3.7 抽象数据类型所需要的语言支持 有些语言对 ADT 的支持要比其它语言更强有力。Ada 语言对抽象数据类型的支持近乎完美 的。比如在字体的例子中,Ada 允许把所有的字体功能子程序都放入一个“包”中。你可以把 几个子程序声明为开放的,而其条子程序则只在包中才是可用的。你可以限制 Font 的定义,从 而禁止 ADT 功能的子程序对 Font 的内部进行操作。这些子程序可以声明 Font 数据。但是它们 不能对任一属于 Font 的域进行操作,也不知道 Font 的内部结构。 在其它语言,如 C、Fortran、Basic 和 Pascal 中,你可以把 ADT 放入单一的一个源文件中, 开放某些子程序而把其余子程序保持为专用的 C 对 ADT 的支持也是比较有力的,因为它支持多 重源文件(模块)和专用子程序。而其它语言对 ADT 的支持能力则取决于特定的实现细节。换句 话说,在其它语言中,含有 ADT 的程序不一定是可移植的。 在任一种给定的语言中,无论你怎样有效地隐含子程序,隐含数据都是一个棘手的问题。 仍以字体程序为例:如果你在功能子程序外说明了一个 Font 变量,就可以在任意能够引用这个 变量的地方对其内部进行操作。这时它总是一个开放的记录,这意味着它很可能成为一个错误 的记录。只有通过规定,编程标准和你痛苦的失败经历才能使其保持为封闭的。 12.4 小 结 · 恰当地对数据进行结构化,可以使程序更简单、更容易理解也更容易维护。 · 可以用表来代替复杂的逻辑结构。当你被程序的复杂逻辑迷惑时,应考虑是否可用查 寻表来简化程序。 · 抽象数据类型是降低复杂性的有力武器。它使你可以分层编写程序,而且是从问题域 而不是程序语言细节来编写顶层的程序。 第十三章 顺序程序语句 199 第十三章 顺序程序语句 目录 13.1 必须有明确顺序的程序语句 13.2 与顺序无关的程序语句 13.3 小结 相关章节 常见的几个控制方面问题:见第 17 章 有条件的代码:见第 14 章 循环代码:见第 15 章 从这章起,论点已由程序的数据中心论转移到控制中心论方面。这章介绍一种最简单的控 制流——按顺序放置程序语句和程序块。 虽然组织顺序式程序代码(Straight Line Code)是件相对比较简单的事情,但是组织形式 的技巧却影响到代码的质量、正确性、可读性与可维护性。 13.1 必须有明确顺序的程序语句 必须按先后顺序往下执行的语句,是最简单的一类有顺序关系的语句,举例如下: 按顺序执行的 Pascal 程序例子: RecordData ( Data ); CalculateResultFromData( Data, Results ); PrintResults ( Results ); 除非代码段中发生了什么不可思议的事情,否则程序将按语句的先后顺序往下执行,即要 得到计算结果必须先读取数据,而只是计算出结果后才能有结果输出。 这个例子中默认的一个概念是语句间的依赖性。第三个程序语句依赖于第二个,而第二个 则依赖于第一个。这个例子中一个语句对另一个的依赖关系,由子程序名就看得很清楚。在下 面的代码段中,这种依赖关系就不是很明确。 虽不明显但仍有依赖关系的 C 程序: ComputeMonthlyRevenues( Revenues ); ComputeQuarterlyRevenues( Revenues ); ComputeAnnualRevenues( Revenues ); 这个例子中,计算季度收入时是假设月度收入已经算出了的。如果对会计学很了解或有一 些常识,我们应当知道在算出季度收入之后,才能算出年度收入。这里存在着依赖关系,但仅 从代码本身却不很明显。下面这个代码中,程序语句间的依赖关系更不明显,这种依赖关系从字 第十三章 顺序程序语句 200 面上是看不出来的。 依赖关系隐藏的 Basic 程序: CALL ComputeMarketingExpenses CALL ComputeMISExpenses CALL ComputeAccountingExpenses CALL PrintExpenseSummary 由于各子程序的调用没有参数,你或许能猜出各子程序是通过模块数据或全局变量等方式 获得数据的。假设是在 ComputeMarketingExpenses()子程序中来初始化全局变量,其它子程序 也就得到了各自需要的数据。在这种情况下,这个子程序必须在其它各子程序前被调用才行, 但在这个代码中你无法从通读程序得知。 当程序语句间有依赖关系时,你需要把它们按一定的先后顺序组织起来而使这种依赖性更 明显。下面提供一些这方面的指导。 组织代码使它们间的依赖关系明显。在上面的 Basic 程序中,ComputeMarketingExpense() 没有必要初始化全局变量。这个子程序的名字表明它计算的是市场数据,而不是 MIX 或 MIS 会 计数据。在 ComputeMarketingExpense()中初始化全局变量是个不太好的习惯,应当改掉。为 何我们要在这个子程序中初始化全局变量而不是在其它两个子程序中呢?除非你有什么正当理 由,否则你必须另写一个子程序——InitializeExpense()去初始化全局变量。这个子程序的名 字已经很清楚地表明它应当在其它子程序前被调用。 子程序的名字应当清轻地表明依赖关系。在上面例子中,ComputeMarketingExpense()的 名字起得不好,因为它仅说明它是计算市场费用的,但同时它却初始化了全局变量。假如你不 乐意另写一个初始化数据的子程序,那么你至少应该给 ComputeMarketingExPense()起一个能 描述其作用名字。本例中,起个 ComputeMarketingExpenseAndInitGlobelData()名字是较为准 确的。你或许要说太可怕了,名字那么长,但这个名字却实实在在地反映了其作用,因而显得 不可怕。原来的子程序名名不符实才害人呢? 使用子程序参数使依赖关系明显。在上面这个例子中,因为子程序间无参数传递,你不知 道其它各子程序是否用了同一个数据。重写上代码段,使子程序间有参数传递,这样在代码中 就留下一些表明执行先后顺序的线索,下面是重写的代码段。 用数据传递来显示程序语句间依赖关系的 Basic 例子: CALL InitializeExpenseData(ExpenseData) CALL ComputeMarketingExpenses(ExpenseData) CALL ComputeMISExpense(ExpenseData) CALL ComputeAccounting(ExpenseData) CALL PrintExpenseSummary(ExpenseData) 因为所有子程序都用了 ExpenseData 这个参数,你可能得到暗示,即所有子程序都用了同 一数据,因而语句的先后顺序是重要的。但反过来想也不算错,既然有数据传递,那么是否该 说明执行顺序并不重要呢?下面是一个例子。 有数据传递并不表明语句间依赖关系的 Basic 例子: CALL ComputeMarketingExpense(MarketingData) 第十三章 顺序程序语句 201 CALL ComputeMISExpenses(MISData) CALL ComputeAccountingExpenses(AccountingData) CALL PrintExpenseSummary(MarketingData,MISData,AccouningData) 既然前三个程序语句中没有用到任何相同的参数,这个代码表明调用各子程序的次序并不 重要,因为第四个子程序用到了前三个子程序的数据,你可能想到这个子程序必须在其它三个 子程序后执行。 注明不明确的依赖关系。首先写一个没有次序依赖关系的代码,然后再写一个有明显依赖 关系的代码。如果你还觉得依赖关系不够明显,那么就用注释注明这种依赖关系。注明不明确 的依赖关系,是说明你代码设想的一个方面,而这对编写出易维护、易修改的代码至关重要。 在 Basic 例子中,写出这些行的注释是很有帮助的。下面程序语句的次序依赖关系很隐藏, 但用注释来注明的 Basic 程序: ' Compute expense data.each of the routines acceses the ' global data structure ExpenseData.ComputeMarketingExpenses ' should be called first because it initlializes Expenses ' PrintExpenseSummary should be called last because it uses ' data calculatal by the other routines. CALL ComputeMarketingExpenses CALL ComputeMISExpenses CALL ComputeAccountingExpenees CALk PrintExpenseSummary 这个例子中,代码没有用技巧来使语句的依赖关系变得明显。最好还是用那些技巧来表明 这种关系而不要用注释。但若你想让别人无论何时都能很明白你的程序,或因为某些原因你不 能通过改进表明这种关系,那就只好用注释了。 13.2 与顺序无关的程序语句 可能有这种情形,即代码中某些语句或程序块的先后顺序并不重要,一个语句并不依赖于 或说逻辑上从属于另一些语句,但实实在在的情况是,次序是影响可读性、性能、维护性的。 而且当语句执行顺序的依赖关系不存在时,可用下面的准则来组织这些语句或程序块的顺序。 指导原则是“接近原则”,使相关操作组织在一起。 13.2.1 使代码能由上读到下 作为一种基本原则,应使程序能由上读到下,而不要到处转移。专家们认为"从上到下"的 次序对可读性最有帮助。简单地使控制流在运行时从上到下是不够的。如果为获得某一所需的 信息而必须去通读你的全部代码,那你就该重新去组织一下你的代码。下面举例说明: InitMarketingData(MarketingData); InitMISData(MISData); InitAccountingData(AccountingData); 第十三章 顺序程序语句 202 ComputeQuarterlyAccountingData(AccountingData); ComputeQuarterlyMISData(MISData); ComputeQuarterlyMarketingData(MarketingData); ComputeAnnualMISData(MISData); ComputeAnnualMarketingData(MarketingData); ComputeAnnua1AccountingData(AccountingData); PrintMISData(MISData); PrintAccountingData(AccountingData); PrintMarketingData(MarketingData); 假如你想知道 MarketingData 是怎样算出来的,你必须从最后一行开始,上溯搜查所有有 关 MarketingData 的语句直到第一行,其实 MarketingData 仅在另外两行出现过,但你却不能 放过每一个语句而得从头看到尾。换句话说,你得看完整个代码才能知道 MarketingData 中如 何算出的。下面是修改后的程序: InitMarketingData(MarketingData); ComPuteQuarterlyMarketingData(MarketingData); ComputeAnnualMarketingData(MarketingData); PrintMarketingData(MarketingData); InitMISData(MISData); ComputeQuarterlyMISData(MISData); ComputeAnnualMISData(MISData); PrintMISData(MISData); InitAccountingData(AccountingData); ComputeQuarterlyAccountingData(AccountingData); ComputeAnnualAccountingData(AccountingData); PrintAccountinData(AccountingData); 这个代码比上一个在几个方面要好。要查的每个变量都局部化了,用到同一变量的语句都 集中到一起。变量赋值后紧接着就用到这些数据。代码段中每个变量集中出现在一处。或许更 重要的一点是代码可能被分割成市场、MIS、会计数据等几个子程序,但前一个代码能看出这种 可能性吗? 13.2.2 使同一变量局部化 有不同参数出现的代码段是一个“脆弱的窗口”。在这个窗口内,很有可能无意中加上了新 的代码行,无意中改变了变量,或读着读着忘了这个变量的值是多少。因此把一个变量出现的 语句集中到一起总是一个好主意,例如上面这个例子。 把变量的再现局部化到一起的观点,其优点是不言自明的,但它却受制于常规的评价方法。 一个评价变量局部化方法是计算变量的跨度(span)。例子如下。 用来计算变量跨度的 Pascal 程序示例: a:=0; b:=0; c:=0; 第十三章 顺序程序语句 203 a:=b+c; 在这个例子中,第一次出现 a 和第二次出现 a 的语句间隔了两行,因此 a 的跨度为 2。两 次出现 b 的语句之间隔了一行,因此 b 的跨度为 1。而 C 的跨度则为 0,下面是例子。 跨度为 1 和 0 的 Pascal 程序例子: a:=0; b:=0; c:=0; b:=a+1; b:=b/c; 在这个例子中,第一次和第二次出现 b 的语句间隔了一条语句,因此 b 的跨度为 1;而第 二次与第三次之间无插入行,因此此时跨度为 0。 平均跨度取各个跨度的平均值,上例中以 b 为例,平均跨度为(l+0)/2=0.5。当你坚持把 同一变量出现的语句集中一起时,你能使读者把注意力一直都集中在一起。如果同一变量出现 得很分散,那么读者就只能在你的程序中满天飞了,因此把同一变量局部化的主要优点在于提 高程序的可读性。 13.2.3 使变量存活时间尽可能短 与变量跨度相关的另一概念是变量“存活时间”,即变量存活期涉及到的程序语句的总行数。 一个变量的生命由第一次出现它的程序语句开始,而终止于最后一次出现它的语句。 不像变量跨度,存活时间不受存活期间变量被用过多少次的影响,假如变量第一次出现在 第一行而最后一次出现在第 25 行,那么存活时间是 25 行,假如在这 25 行中这个变量仅被用了 两次(即只在第 1,25 行),那么跨度是 23 条语句,假如变量从第一行到 25 行中行行都出现,那 么平均跨度为 0,但存活时间依然为 25 条语句。下面的图显示了跨度和存活时间的具体含义: “长的存活时间”意味着变量存活期间有许多条语句,“短的存活时间”意味着变量存活时 只出现过几条语句;跨度则指变量出现的密度情况。 跟变量跨度一样,在考虑存活时间时要使它尽可能地小,使存活期间出现的语句条数最小。 同样地,减小存活时间也降低了变量出现窗口的脆弱性。当你想改变变量时,若存活时间短, 那么最早和最晚出现该变量的两条语句间的语句条数就小,因而减小了有意无意的修改出错的 可能性。 减小存活时间的另一大好处是在编码时你能在头脑中有一幅很清晰的画面。假如一个变量 在第 10 行赋值而在第 45 行才被用到,你可能认为在这期间也会用到这个变量,老想着这种可 能性,头脑当然很乱了。假如在第 44 行给一个变量赋值而在第 45 行马上就用到,那么之间不 可能有别的语句,你只需在这小的范围内考虑这个变量就行了。 第十三章 顺序程序语句 204 图 13-1 存活时间与跨度图 小的存活时间能减小初始化的错误,顺序式程序代码往往倾向于采用循环。若你把初始化 数据的地方放到远离你循环的地方,当你修改循环时,你很可能忘了去修改初始化值。把初始 化代码与循环代码紧放在一起,你就可能减小修改程序带来的初始化错误。 最后,小的存活时间使你编的代码可读性好,读者脑中装的代码愈少,你的代码便愈是易 懂。同样地,存活时间愈小,当你编辑或调用代码时变量出现的范围也愈小。 计算变量的存活时间 我们规定计算变量的存活时间是这样的:第一次和最后一次出现该变量的语句间总共有的 语句行数(包括两个端点)。下面是例子: 这个 Pascal 程序不好,变量存活时间长。 l {Initialize all variables } 2 3 RecordIndex := 0 4 Total := 0 5 Done := False ... 27 while (RecordIndex ProjectedTotal) ——Total 的最后引用 71 Done := True; ——Done 的最后引用 这里几个变量存活时间分别为: RecordIndex (第 29 行-第 3 行+1)=27 Total (第 70 行-第 4 行+4)=67 Done (第 71 行-第 5 行+1)=67 平均存活时间 (27+67+67)/3=54 这个平均存活时间显得太长。 把上例重新写一下使出现变量的语句比较靠拢。 这个 Pascal 程序较好,因为变量存活时间短。 ... 26 RecordIndex:=0 ——RecordIndex 的初始化从第 3 行向下移 27 while (RecordIndex< RecordCount) do 28 begin 29 RecodIndex:=RecordIndex+1; ... 63 Total:=0 ——Total 和 Done 的初始化从第 4、5 行向下移 64 Done:=False 65 while not Done begin ... 70 if (Total>ProjectedTotal) 71 Done:=True; 在这个例子中,各变量存活时间计算如下: Recordlndex (第 29 行-第 26 行+1)=4 Totel (第 70 行-第 63+1)=8 Done (第 71 行-第 64 行+1)=8 平均存活时间 (4+8+8)/3=7 我们能靠直观觉得第二个例子比第一个例子好,因为初始化的语句和用到该变量的语句较 靠近。计算出两个例子的平均存活时间很有意义:54 行的平均存活时间与 7 行的平均存活时间 相比,正好从数据上说明了为什么我们的直观是正确的。 本章前面有几个例子,有一个含 InitMarketingData()的子程序经过重新合理编写后,使出 第十三章 顺序程序语句 206 现同一变量的语句较为靠近,因而同时减小了平均跨度和平均存活时间,程序得以改进,读者 可自行计算一下改进的程序。 那么仅从数字上能说明短的存活时间的代码就比长的存活时间的代码好吗?同样地,小跨 度的代码就一定比长跨度的代码好吗?研究人员还没有一个定量的答案。但有一点是肯定的, 即减小变量跨度和存活时间对设计程序来说是一个好的思想。 假如用跨度和存活时间来衡量全局变量你会发现,全局变量的跨度和存活时间都相当之大, 这是为何要避免用全局变量的重要原因之一。 13.2.4 相关语句组织在一起 把相关的语句放在一起,这些语句之所以能放在一起是因为它们用一个数据,所起作用相 同、或语句的执行是有先后之分的,下一句的执行依赖于上一句的结果。 检查是否把相关语句很好地组织在一起的一个简单办法是,把代码的子程序列出来并把相 关的语句用框线框框起来,如果组织得很好,那么就应当如图 13-2 所示那样,各框之间无交叉。 图 13-2 如果代码组织得好.画出相关语句的框与框之间无交叉部分,这些框是一个一个叠起来的 如果组织得不好,很有可能是使用 goto 引起的,那么画出图就如图 13-3 所示,框与框之 间有交叉,这时应重新编写和组织代码,以便把有关的语句更好地组织在一起。 一旦你组织好了相关语句,你会发现他们内部之间联系非常紧密,但这一组相关语句与其 前后的语句却无太大联系。这时你可以把这组紧密联系的程序语句写成一个子程序。 13.2.5 检查表 组织顺序式程序代码 · 把语句间的依赖关系表示得很清楚吗? · 子程序名是否把依赖关系表示得很清楚? · 子程序的参数是否把依赖关系表示得很清楚? · 若代码的依赖关系不清楚,用注释注明了吗? · 代码能从上读到下吗? · 变量的出现靠得很近吗? ——从跨度和存活时间来考虑。 第十三章 顺序程序语句 207 图 13-3 如果代码组织得不好,画出的相关语句的框与框之间有交叉,这种情形很可能是用 goto 引起的 · 是否把相关语句组织在一起? · 是否把相对独立的各相关语句写成子程序了? 13.3 小 结 · 组织顺序式代码最好的原则是整理出依赖关系。 · 用合适的子程序名、参数表、注释来标明依赖关系。 · 如果代码没有明显依赖关系,把相关语句组织在一起,特别是使用同一参数的那些语句。 第十四章 条件语句 208 第十四章 条件语句 目录 14.l if 语句 14.2 case 语句 14.3 小结 相关章节 经常遇到的有关控制语句的几个问题:见第 17 章 顺序式程序代码:见第 13 章 使用循环的代码:见第 15 章 条件语句是控制别的语句是否执行的语句,有些语句如 if,else,case,switch 能控制别 的程序语句是否执行。虽然循环控制语句如 while 和 for 通常也认为是条件语句,但习惯上一 般把它们单独讨论。在第 15 章的循环语句中,将讲到 while 和 for 的用法。 14.1 if 语句 你所用语言可能不同,但你总会用几种 if 语句。最简单的是常用的 if 和 if-then 语句, if-then-else 稍复杂一点,长链形式的 if-then-else 更复杂。 假如你所使用的语言不支持结构形式的 if-then-else 语句,可以用第 17.6 节中用到的 技巧来模仿它,即用 goto 语句模仿结构化结构。 14.1.1 简单 if-then 语句 编写 if 语句时请参考以下几点: 在代码中,先按正常情况的路径往下编写,然后再写异常清况。在编写代码时,一定要使 得正常情况的路径在代码中显得很清晰。记住,异常情况一定不要使正常情况路径产生模糊。 这对程序的可读性及功能是很重要的。 在出现等号情况时,一定要弄清程序的流向。当读取数据或计算循环的控制变量时,用’ <’替代’<=’或用’<’替代’<=’都同样会产生边界错误(所谓边界错误指在控制循环或重复 时,由于控制变量的某一边界值出错或超出范围而使整个程序无法继续下去的错误)。在循环时, 一定要弄清结束点,以避免产生边界错误,在条件语句中,一定要弄清等号时的情形,以避免 产生边界错误。 把正常情况放在 if 后面而不是 else 后面。你当然希望正常的情况在程序中先处理,这样 按层层递推的方法,按先正常后不正常情况,按直线式往下排。下面这个例子犯了好多随意安 排正常不正常情况的毛病: OpenFile (InputFile,Status) 第十四章 条件语句 209 if Status=Error then ErrorType=FileOpenError ——错误情况 else ReadFile(InputFile,FileData,Status) ——正常情况 if Status= Success then SummarizeFileData(FileData,SummaryData,Status) ——正常情况 if Status=Error then ErrorType=DataSummaryError —一错误情况 else PrinSummary(SummaryData) SaveSummaryData(SummaryData,Status) if Status=Error then ErrorType=SummarySaveError ——错误情况 else UpdateAllAccounts ——正常情况 EraseUndoFile ErrorType=None end if end if else ErrorType=FileReadError ——错误情况 end if end if 这段代码中是很难让人苟同,因为正常情况和异常情况都混杂在一起。在代码中很难看出 整个程序是按正常情况的路径贯穿的。另外,因为异常情形有时也出现在 if 语句后而非 else 之 后,因此很难相信程序是按正常情况的线索贯穿的。下面重新写了这段代码,先集中编写了正 常情形,然后才编写异常情形。这样寻找和读起来,都很容易发现哪些是正常情况。 OpenFile(InputFile,Status) if Status<>Etror then ReadFile(InputFile,FileData,Status) ——正常情况 if Status=Success then SummaryFileData(FileData,SummaryData,Status) ——正常情况 if Status<>Error then PrintSummary(SummarData) ——正常情况 SaveSummaryData(SummaryData,Status) if Status<> Error then UpdateAllAccounts ——正常情况 EraseUndoFile ErrorType=None else ErrorType=SummarySaveError /* 错误情况 */ end if 第十四章 条件语句 210 else ErrorType = DataSummaryError /* 错误情况 */ end if else ErrorTyre = FileReadError /* 错误情况 */ end if else ErrorType=FileOpenError /* 错误情况 */ end if 在以上例子中,可以顺着主程序流的 if 语句去发现哪些是正常情况,修改后的代码使人集 中阅读主程序流而不是费力地去寻找异常情况,整个程序读起来轻松明快。把异常情况都放在 程序的后部,就是很好地处理了异常情况的代码。 if 语句后跟上一个有意义的语句。有时你可能碰到下面这个例子,if 语句后什么也没有。 If(SomeTest) ; else { /* do something*/ ⋯ } 若你是一个有经验的编程员,绝对不会这样去编程,这样显得很呆板。改进的方法是把 if 的条件逻辑取反,把 else 后的可执行语句移到 if 后,然后去掉 else 语句,改正如下: 去掉了 if 语句后空语句情况的 C 程序例子: if(!SomeTest) { /* do something */ } 考虑是否需要 else 语句。如果你真的想用一个简单 if 语句,考虑到底是否真的就需用一 个 if-then-else 语句的形式。通用动力公司(General Motors)在分析了用 PL/I 编写的 代码且发现仅 17%的 if 语句后跟 else 语句,而这用了 else 语句的情况中,也有 50~80%的 仅用一个 else 语句(Elshoff 1976)。 一种观点认为编写 else 语句(如果需要,跟上一个空语句),是要表明 else 情况已经考虑 过了。为了表明考虑过了 else 情况而编一个空 else 语句,可能显得多余,但至少说明你并没 有忽略 else 情况。如果你的 if 语句后无 else,除非原因很明显,否则用注释来标明为什么 else 语句不需要。例子如下: 这是一个 Pascal 程序例子,用注释说明为什么不要 else 语句是很有帮助。 { if color is valid } 第十四章 条件语句 211 if ( Min.Color<=Color and Color<=Max.Color ) begin { do some thing } ⋯ end; { else color is invalid } { Screen not written to -- safely ignore command } 检查 else 语句的正确性。检查代码时,像 if 语句这样的主要语句是应当检查到的。但也 应当检查 else 语句,以确保其正确。 检查 if 语句和 else 语句是否弄反了。一个常见的错误是在编写 if-then 语句时,把该跟 在 if 后的代码与该跟在 else 后的代码正好弄反了,或者使 if 中的判断逻辑正好弄反了。检查 你的代码避免这种错误。 14.1.2 if-then-else 语句 假如你所使用的语言不支持 case 语句,或者只是部分支持,那么你会发现,你得经常编写 if-then-else 语句。如下例子中,代码要把输入的字符归类,因而用到如下语句: 用 if-then-else 语句排序字符的 C 语言例子。 if( InputChar < SPACE ) CharType=ControlChar; else if( InputChar==' ' || InputChar==',' || InputChar=='.' || InputChar=='!' || InputChar=='(' || InputChar==')' || InPutChar==':' || InputChar==';' || InputChar=='?' || InPutChar=='-' ) CharType=Punctuation; else if( '0' <= InputChar && InputChar <= '9' ) CharType=Digit; else if( 'a' <= InputChar && InputChar <= 'z' ) || ( 'A' <= InputChar && InputChar <= 'Z' ) CharType=Letter; 以下几条是在编写 if-then-else 时要遵循的: 用布尔函数调用(boolean function 亦称逻辑函数)简化程序。上面代码不好读的一个原 因是把字符进行排序的条件过于复杂。为了提高可读性,可以用布尔函数来代替这些判断条件。 用布尔函数调用的 if-then-else 的 C 语言程序例子。 if(IsControl(InPutChar)) CharType=ControlChar; else if(IsPunctuation(InPutChar)) CharType=Punctuation; else if(IsDigit(InputChar)) CharType=Digit; else if(IsLetter(InputChar)) 第十四章 条件语句 212 CharType=Letter; 把最常见的情形放在最开始。把最常见的情形放在最开始,你就可以少读许多处理异常情 况的代码,而直接读常见情况的代码。这样就提高了寻找常见情况的效率。在上述例子中,字 母该是最常见的情况,但检查是否为标点代码却放在最先。把检查字母的代码放在最开始修改 如下: 这个 C 语言的例子中,把处理最常见情况的代码放在最先: if(IsLetter(InputChar)) ——这个判断最常见,放在第一位 CharType=Letter; else if(IsPunctuation(InputChar)) CharType=Punctuation; else if(IsDigit(InPutChar)) CharType=Digit; else if(IsControl(InputChar)) ——这个判断最少见,放在最后 CharType=ControlChar; 保证覆盖全部情况。最后用一个 else 语句处理那些你未曾想到的错误信息。这个错误信息 很有可能是由你而非用户引起的,所以一定要正确处理这种情况,下面例子中,增加了处理其 它情况的代码。 这个 C 语言程序例子,用缺省情况应付可能出现的其它情况。 if(IsLetter(InputChar)) CharType=Letter; else if(IsPunctuation(InputChar)) CharType=Punctuation; else if(IsDigit(InputChar)) CharType=Digit; else if(IsControl(InputChar)) CharType=ControlChar; else PrintMsg("Internal Error: Unexpectecd type of character detected."); 假如你所使用的语言支持别的结构能代替 If-then-else,替换掉 if-then-else 形式。少 数几种语言,如 Ada 支持 case 语句,能很方便地替换大多数的 if-then-else,那就用 case 语句,case 语句易写易读,较 if-then-else 结构为好!下面用 Ada 的 Case 语句来归类输入字 符: 这个 Ada 语言程序用 Case 语句代替了 if-then-else。 case InputChar is when 'a'..'z' | 'A'..'Z' => CharType := Letter; when ' ' | ',' | '.' | '!' | '(' | ')' | ':' | ';' | '?' | '-' => CharType := Punctuation; when 'o'..'9' => CharType:=Digit; when nul..us=> 第十四章 条件语句 213 CharType:=ControlChar; others=> PUT_LINE("internal Error: Unexpected type of character detected."); end case; 14.2 case 语句 case 语句和 switch 语句因语言不同其结构也变化很大。许多版本的 Basic 语言根本就不 支持 case 语句。C 语言支持的 case 语句,其分支变量每次只能对应一个值。Pascal 中的 case 语句也只对应一定范围内的数据。Ada 支持 case 语句,并且它用表示值的范围和组合的能力很 强。 在 Apple Macintosh 和 Microsoft Windows 环境中编程,大型的 case 语句经常用到。随着 交互式事件驱动程序的日益普及,case 语句的使用频率越来越高。下面部分指出了怎样有效地 使用 case 语句。 14.2.1 选择最有效的方法来组织各种情况 在 case 语句有许多方法可以用于组织各种情况。假如 case 语句很小,仅有三种选择和相 应的三条响应的语句,那么你怎样组织这个 case 语句都行。如果你的 case 语句很大,如在事 件驱动程序中用到的 case 语句,把各种情况组织成一个合理的顺序是很重要的。下面是可能的 组织方法。 把各种情况按字母或数字顺序组织。如果各种情况是同等重要的,按 A-B-C 顺序安排, 以提高可读性。每个事件都可很容易从整体中挑出来。 把正常情况的事件放在最开始。如果是一个正常情况及几个异常情况,把正常情况放在最 先,并用注释标明哪些是正常情况哪些是异常情况。 按出现频率组织情况。把最经常执行的情况放在最先,而最不可能的情况放在最后。这种 方法有两大好处。首先,读者很容易找出最普遍的情况。读者为寻找某个具体的情况而浏览整 个程序,极有可能就是找最常见的那种情况。把常见的情况放在代码的最开始,读者能很快找 到它。第二,机器执行起来也快。每一种情况都在代码中有相应的执行语句,机器执行都要花 时间搜索,如果有 12 种情况而最后一个情况是要执行的。那么机器要搜索 12 条 if 语句,直到 最后发现相应的情况。若把最普遍情况放在最先,你就可以减少机器的搜索区间,这样就可提 高代码的效率。 14.2.2 用 case 语句该注意的几点 下面是用 case 语句时要注意的几点: 使每种情况对应的执行语句最简单。每种情况对应执行代码应当短些。短的执行代码结构 显得清楚。如果某个情况对应的执行代码显得很复杂,应当把它写成一个子程序然后对应这种 情况调用子程序,而不是在这种情况之后直接跟上复杂的执行代码。 不要为了用 case 语句而去定义伪交量。一个 case 语句应当用在易被归类的简单数据上。 假如数据不简单,用 if-then-else 代替 case。伪变量显得很乱,应当避免使用。下面是几个 反例: 这个 Pascal 程序编得不好,因为它定义了一个 case 伪变量。 第十四章 条件语句 214 Action:=UserCommand[1]; case Action of 'c': Copy; 'd': DeleteCharacter; 'f': Format; 'h': Help; else PrintErrorMsg('Error: Invalid command.'); end;{case} 控制 case 语句的变量是 Action。在本例中,变量 Action 是通过取 UserCommand 字符串的 第一个字母形成的,字符串由用户自己输入。 这种勉强的编码方法非常不可取,也产生了许多问题。在 case 语句中,你自己定义了变量, 但真实的数据可能并不如你所期望那样产生预期动作。比如在上例中,读者把 copy 的第一个字 母 C 定义替代 copy,并且能正确调用 copy()子程序。但另一方面,如果用户想在 case 语句中 定义"cement overshoes","clambake" ,"cellalite"抽出第一个字母来代替这个变量,那么 也为 c,调用的却是 Copy()子程序。case 语句中的 else 语句也可能出毛病,因为它只管错误 命令的第一个字母而不管这个命令本身。 若不用定义伪变量的方法,则可用 if-then-else 来达到检查整个命令串的目的。以下是 重新编写的代码: 这个 Pascal 程序较好,用 if-then-else 代替 case 中的伪变量。 if( UserCommand='Copy' ) then Copy else if( UserCommand='delete' ) then DeleteCharacter else if( UserCommand='format' ) then Format else if( UserCommand='help' ) then Help else PrintErrorMsg( 'Error: Invalid command.' ); 若用缺省语句只用合法的缺省。有时还有一种情况,你就想把这种情况编写成缺省语句。 这种做法有时虽很诱人,但却不足取。要这样你就没有利用 case 语句的好处,并且失去利用缺 省语句检查错误的能力。 这样使用 case 语句不便于修改。如果用合法的缺省,增加一种新情况是很容易的事情—— 你只需增加一种情况并编写相应的执行代码就行了。假如用了缺省,修改起来很困难。若你要 增加一种新情况则要先编一个新的缺省情况,然后把以前用作缺省的情况改为一般情况,才能 使整个 case 语句写成合法代码。在编写程序时从一开始时就该用合法缺省。 用缺省语句检查错误。如果缺省语句不用作处理一些操作,也不支持某些情况,就把诊断 信息放在里面。下面是这样的例子: 第十四章 条件语句 215 这个 Pascal 程序较好,用缺省情况发现错误。 case Letter of 'a': PrintArchives; 'p': {no action required,but case was considered} ; 'q': PrinrQuarterlyReport; 's': PrintSummary; else PrintErrorMsg('Internal Error 905:Call Customer assistance.'); end; {case} 缺省语句中的信息对调试和编写代码都是很有用的,用户最喜欢的信息是在系统运行失败 时给出“内部错误,请调用客户支持”之类的信息;或者最坏的情形,但结果是错误的却好像 是正确的,直到检查到了为止。如果缺省语句不仅仅用作发现错误,那么就意味着对每一种情 况的选择都应当正确,应当检查以确保进入 case 语句的值都合法。如果有进入 case 语句的值 不合法的,修改对应情况的语句,以便使缺省能真正检查错误。 在 C 语言中,每个情况对应的代码段都应当有一个结束语句。C 语言是一种通用的高级语 言,在 case 语句中执行每种情况都并不自动跳出,因而你得给它一个明确的结束命令,如果你 不给每种情况一个结束的语句,执行完这种情况的代码后接着转入执行下一个情况的代码。如 果真是这样,那就犯了编程中的大忌。下面这个例子正是这样。 这个 C 语言程序中 case 语句没用好 switch(Inputvar) { case('A'): if(test) { /* statement l*/ case('B'): /* sratement 2*/ /* statement 3*/ /* statement 4*/ } /* if(test) */ break; } 这个例子编得不好,因为整个控制结构混在一起了,这种嵌套结构很难理解,要修改例子 中的'A' 情况和'B' 情况比做脑部手术更难。若你真的要修改这两种情况,倒还不如推翻了重 写。你可能一次就写出正确的代码。总的说来,在用 case 语句时,不要忘了在每种情况中安排 一个结束代码。 在 C 语言中,case 语句的最后都应当准确无误地标明结束。假如你有意地在最后不标明结 束,那么用注释说明你为什么要这样。 第十四章 条件语句 216 14.2.3 检查表 条件语句 if-then 语句 • 正常情况路径在代码中流向是否很分明? • if-then 语句在出现等号时流向是否正确? • else 语句是否有必要? • else 语句正确吗? • if 语句和 else 语句正确吗?它们是否弄反了? • 正常情况是否跟在 if 后而非 else 后? if-then-else 语句 • 复杂的条件是否封装成布尔函数调用了? • 最常见情况放在前面吗? • 全部情况都覆盖住了吗? • if-then-else 语句是最好的选择吗?——用 case 语句代替是否更好? case 语句 • 各情况的安排次序有含义吗? • 每种情况对应的操作简单吗?——如需要调用别的子程序。 • case 语句中的变量有实际意义吗?它是为了用 case 语句而单纯地定义出来的伪变量 吗? • 缺省语句的用法是否合法(规范)? • 用缺省语句检查和报告异常情况吗? • 在 C 语言中,每一情况的结尾用了 break 了吗? 14.3 小 结 • 注意 if 和 else 的顺序,特别是在处理好多异常情况时,务必使正常情况流向清晰。 • 组织好 if-then-else 和 case 语句中的几种情况,使可读性最好。 • 在 case 语句中用缺省值,在 if-then-else 中的最后一个 else 中获取意外错误。 • 各种控制结构并不都同样有用,在编码时选用最合适的控制结构。 第十五章 循环语句 217 第十五章 循环语句 目录 15.1 选择循环类型 15.2 控制循环 15.3 编写循环的简单方法——从里到外 15.4 循环与数组的关系 15.5 小结 相关章节 一般控制语句应当注意的几个问题:见第 17 章 直接式程序代码:见第 13 章 条件语句代码:见第 14 章 所谓循环指任何一种类型的重复性控制结构。这种结构让代码的某一块被重复执行。几种 常见的的循环类型有 Basic 中的 FOR NEXT 语句、Fortran 中的 DO 语句、Pascal 中的 while-do 和 for 语句、C 语言中的 while 和 for 语句以及 Ada 中的 loop 语句等,使用循环是用程序化语言 编程时最复杂的情形之一,知道如何及何时用哪种循环是编写高质量软件的决定性因素。 15.1 选择循环类型 在大多数语言中,你总可以用上几种循环类型。 · 计数循环要执行给定的循环次数.也可能就只循环一次。 · 条件循环事先并不知道要执行多少次循环,而要在每次重复之前检查是否满足循环条 件。只要满足循环条件,循环不断继续下去,除非用户退出循环或出错。 · 死循环只要开始便无限执行下去。在心脏起搏器、微波炉、巡航控制等系统中,把死 循环置入其中。 以上几种循环的不同首先在于其灵活性——循环前检验一下是否满足退出循环的条件。循 环还在于把控制循环的语句放置在何处。你可以把控制循环的语句放在循环体的开始,中间或 结尾。这种特性告诉你循环是否至少要执行一次。如果控制循环的语句放在开始那么循环体可 能不被执行。而若放在结尾,循环体至少要执行一次。若放在中间,有一部分循环体至少要执 行一次,而另一部分(控制循环语句之后)则可能一次也不执行。 在选用循环结构时,灵活性和控制循环语句的位置是关键。表 15-1 列出了几种语言的循环 类型和控制循环语句的位置。 第十五章 循环语句 218 表 15-1 循环类型 语言 循环类型 特性 放置位置 Ada for 计数循环 开始 while 条件循环 开始 loop-with-exit 条件循环 通常在中间 loop n/a 无(用于死循环) Basic FOR-NEXT 计数循环 开始 WHILE-WEND 条件循环 开始 DO LOOP 条件循环 开始或结尾 C do-while 条件循环 开始 while 条件循环 开始 Fortran Do 计数循环 开始 Pascal for 计数循环 开始 repeat-until 条件循环 结尾 while 条件循环 开始 15.1.1 while 循环 初学者有时认为 while 循环是要不断地作判断。当 while 的条件为假时,循环立即停止;而 不问在循环中哪些语句被执行了。虽然 while 循环不全是条件循环,但一般把它看成是条件循 环。假如事先你并不知道循环的次数,那就用 while 循环。与初学者想法正好相反,使循环中 止的语句在每次循环时只执行一次,而主要要考虑的事情是确定把控制循环的语句放在开始还 是结尾。 把控制循环的语句放在开头的循环 把控制循环语句放在开始的循环在 C、Basic、Pascal、Ada 中是 while 循环,在 Fortran、 汇编或其它语言中,可模仿 while 循环。 若想把控制循环的语句放在开始,最好选 while 循环。有些研究人员建议除非不能用,否 则一定要作这种循环类型。若认同这种评论,那么读者在读你的代码时所需理解的循环结构种 类就减少了。如果你只用一种基本的循环类型,读者就会慢慢适应你的这种编程风格,如果你 用几种循环类型,你就使读者很烦——他们要熟悉这几种循环类型,而你自己也要精通这几种 类型。 把控制循环的语句放在末尾的循环 有时你想用条件循环,但又想使循环至少执行一次,那么用 while 循环并把控制循环的语 句放在循环体的末尾。当然你也可以在 C 中用 do-while 循环,在 Pascal 中用 repeat-while 循环、 在 Basic 中用 DO-LOOP-WHILE 循环、或在 Ada 中用 loop-with-exit 循环结构。也可在 Fortran、 汇编或其它语言中模仿这种把控制循环的语句放在结尾的循环。 C 语言的一大好处便是 while 和 do-while 这两种循环结构所用控制循环和语句相同,两者 唯一的区别在于 while 把控制语句放在开始而 do-while 把控制语句放在结尾。Pascal 的 while 第十五章 循环语句 219 循环和 repeat-until 循环有两点不同:跟 C 语言一样,while 控制循环语句放在开头,而 repeat-until 则放在末尾。而另一奇怪的不同之处在于 repeat-until 的循环条件在逻辑上与对应的 while 循环 的条件正好相反。如果 while 的条件是“当⋯不循环”,则 repeat-until 的条件是“当⋯循环”。 这种区别比控制循环语句的放置位置更让人容易糊涂,因此一般建议选用把控制循环语句放在 开头的 while 循环。 15.1.2 Loop-with-exit 循环 Loop-with-exit 循环是把终止条件放在循环体中间而不是开头或结尾的循环。Ada 支持 Loo-with-exit 循环,你也以在 C 中用 while 和 break,或在其他语言中用 goto 来模仿这种循环结 构。 正常的 loop-with-exit 循环 正常的 loop-with-exit 循环包含循环头、循环体(含结束条件)循环尾,如下面 Ada 程序例 子: 一个常见的 Ada 的 Loop-with-exit 例子程序: loop ⋯ exit when(some exit condition); ⋯ end loop; 用到 loop-with-exit 循环的情况是,在循环体退出前至少执行循环体中部分情况一次。 下面的 C 语言子程序用到了 loop-with-exit 循环。 /* Compute scores and ratings */ score=0; GetNextRating(&RatingIncrement); 这些行出现在这里 Rating=Rating + RatingIncrement; while(Scroe < TargetScore && RatingIncrement!=0) { GetNextScore(&ScoreIncrement); Scroe=Score + ScoreIncrement; GetNextRating(&RatingIncrement); 这些行出现在这里 Rating=Rating + RatingIncrement; } 上例中,循环体中的最后两行重复了循环体前的两行。在修改程序时,你可能忘了同时修 改这两处,而其它的编程人员或许根本就没有意识到这两处是一样的,而需要一起修改,这样 因为改得不彻底程序会出错。下面告诉你怎样修改这个程序。 这个 C 程序用了 loop-with-exit 循环,易于修改。 /*Compute scores and ratings. The loop uses a FOREVER macro 第十五章 循环语句 220 and a break statement to emulate a loop-with-exit loop. */ Score = 0; FOREVER { GetNextRating( &RatingIncrement ); Rating = Rating + RatingIncrement ); If (!( Score < TargetScore && RatingIncrement != 0 )) - 这是循环退出条件 break; GetNextScore( &SoreIncrement); Score = Score + ScoreIncrement; } 下面用 Ada 写了一段代码; 这个 Ada 程序用到了 loop-with-exit 循 环 - Compute scores and ratings Score := 0; Loop GetNextRating( RatingIncrement ); Rating := Rating + RatingIncrement; exit when ( not ( Score < TargetScore and RatingIncrement!=0 )); GetNextscore ( ScoreIncrement ) ; Score := Score + ScoreIncrement; end loop; 在用 loop-with-exit 循环时,请遵循以下几点 : · 把所有的终止循环语句放在一起。分散放置终止语句可能使一个或几个其它的终止语 句在调试、修改、测试时被忽视。 · 用注释阐明。如果一种语言不支持 loop-with-exit 循环结构(实际上,Ada 之外的 任何语言都不支持),那么用注释标明哪些地方你用了 loop-with-exit 循环技术。 loop-with-exit 循环是单进单出的结构化控制结构,而且是 Ada 循环控制中较为常用的 一种。它较之其他种类的循环显得简单易懂。有人把 loop-with-exit 在中间结束循环和其它 在开始或末尾结束循环的循环作比较发现,初学者中有高达 25%人用 loop-with-exit 循环。 研究人员从这个研究中得出结论认为,loop-with-exit 循环结构更接近于人对循环控制的理 解。 但是 loop-with-exit 循环用得并不普遍。问题在于对这种循环是否是一个好的方法的无 穷无尽的争论。除非最后确实证明,否则我要说 loop-with-exit 循环是一个很好的技巧,你 尽可能地使用。 第十五章 循环语句 221 不正常的 loop-with-exit 循环 为避免循环无法作用在边界情况上,用到另一种 loop-with-exit 循环。 这个 C 语言用 goto 直接进入循环体内部,显得很不好: goto Start; while(expression) { /* do something */ ... Start; /* do something else */ ... } 乍一看,上面这个程序与以前的 loop-with-exit 例子相似。这种编程方法用在循环体的前 半部分 do-something 第一次要跳过而不执行,但后部分/*do something else*/第一次却 需执行的情况。这也是种单进单出的结构:唯一的进口在循环体的上边的 goto 语句,唯一的出 口是 while 语句。这种方法有两个问题:用了 goto 语句并且显得很乱。 在 C 中,不用 goto 语句同样能达到效果,如下面有这个子程序。如果一种语言不支持 break 或 leave,可用 goto 去模仿。 这个 C 程序较好,没有用 goto 却达到同样效果 FOREVER { /* do something else */ ... if ( !( expression ) ) break; /* do something */ ... } 15.1.3 for 循环 当你想使程序块循环给定次数时,for 循环是一个好的选择。在 C、Pascal、Basic、Ada 中用 for 循环,在 Fortran 中用 DO 语句。 用 for 循环做简单动作时,不需设内部循环控制变量。你所需做的是在循环之前设一个控 制变量就可以不管了。你不需在循环内部设任何控制。若在某些条件下必须跳出循环,选用 while 循环更好。 第十五章 循环语句 222 当然,不要强行修改控制标志值使循环终止,这时可用 while 循环替代。for 循环仅用于 简单情形,大多数复杂的循环还是需要 while 循环。 15.2 控制循环(Controlling The Loop) 在编写循环时会出哪些错?当然包括以下错误:忽略了与循环有关的变量或累加器初始 化、不正确的嵌套、不正确的循环中断、忘记给循环变量一个增量或给错了增量、用不正确的 循环指标访问数组元素。 你可以先来看两个例子以对上述问题有一个感性认识。首先,应减少影响循环的因素,简 化、简化、再简化。第二,把循环体内部当作一个子程序看————把控制语句尽可能地放在循环 体外,以明确循环体执行的条件。不要让读者看了循环主体本身后才弄清循环控制。可以把循 环体看作一个黑盒子:周围的程序只判断控制条件而不知里面的内容。 这个 C 程序把循环体作为一个黑盒子; while(!eof(InputFile)&& MoreDataAvailable) { } 循环到底在什么条件下终止?在这个程序中,你只知道当 eof(InPutFile)为真而 MoreDataAvailable 为假时才退出循环。 15.2.1 进入循环 下面几条告诉你如何进入循环: 仅从一个入口进入循环。许多循环控制结构允许你从开头中间或末尾进入循环。你从循环 头部进入循环,大可不必多口进入。 把初始化循环的代码紧放在循环前头。最近原则提倡把相关语句放在一起。如果把相关语 句分散在程序的各处。修改时可能顾及不全而产生修改错误。如把相关语句放在一起。可避免 在修改时出错。 把与循环体相关的初始化循环的语句放在一起。如果不这样,当你扩大循环体或修改时很 可能忘了修改初始化循环的代码。当你把一个循环体拷贝到子程序里时,你就可能因为忘了一 起拷贝初始化部分而出错。把初始化部分放在远离循环的地方(在数据定义区域)或内务处理 区就可能产生初始化循环出错的麻烦。 在 C 中,用 FOREVER 宏编写死循环或事件循环。有时你想写一个无终止的循环,如埋 植在心脏起搏器中或微波炉中的循环,有时你也可能写一个循环,在响应某一事件时才终止, 这就是事件循环。你可能有许多方法编制循环,但下面的宏定义在 c 中是标准的: 这个 c 语言程序用了一个死循环: #define FOREVER for(;;) ... 第十五章 循环语句 223 FOREVER——这里是无限循环 { ... } 在 Pascal 中,用 while(真)结构编写死循环或事件循环。如果希望循环有条件终止,在 Pascal 中用 goto 或 exit 离开循环。在这种情况下,goto 或 exit 是一个保护性的结构性编程结构, 保证了循环的单口退出,保证了单入单出的结构性编程需要,下面的 Pascal 程序是标准的建立 死循环的方法; 这个 Pascal 程序编写了一个死循环: while(True) begin {infinite loop} ... end; 以上是用 Pascal 和 C 编写死循环和事件循环的标准方法。伪死循环像 for i:=-i to 999 使得循环的替换性很差。因为试图用循环次数不会超出极限以达到死循环目的——可能 9999 就是一个合法值(没超出范围)。这个伪死循环在修改时也可能出错。 在 C 中,只要允许就用 for 循环。C 的 for 循环是这种语言强有力的结构之一。它不仅灵 活性强,而且把循环控制代码封装在一起,增加了其可读性。程序员在修改软件时易犯的错误 是;修改了循环前面的初始化循环的代码,但却忘了修改其后面的有关代码。在 C 的 for 循环 中,所有相关代码集中在循环的顶部,修改起来很容易。如果在 C 中能用 for 循环替代别的类 型的循环,尽量这样做。 当 while 循环更合适时,别用 for 循环。在 C 中乱用 for 循环的一例是在 for 的条件中用了 while 循环的条件,下例便是这种情形: 这个 C 中程序虽是 for 循环却用了 while 循环的条件头: /* read all the records from a file */ for(rewind(InFile).RecCount = 0; !feof(InFile); RecCount++) { fgets(InputRec[RecCount-1], MAX_CHARS, InFile); } C 语言的 for 循环比其它语言的 for 循环优点在于,它的初始化和结束条件很灵活,而这 种灵活性带来的固有缺点是把控制条件放在了循环头,因而对循环体就无法控制了。 把控制循环的语句放到 for 循环头如初始化循环变量、终止循环或转向终止的表达式。上 例中,fgets()语句使循环转向中止,但 RecCount 语句却没起到这个作用,它是内部语句, 没有起到控制循环的作用。把 RecCount 语句放在循环头而把 fgets()语句放在循环体中是一 个错误,它使人误解为是 RecCount 在控制循环。 在这种情形下,若想用 for 循环而不用 while 循环,那就把控制循环的语句放在循环头, 而把不起这个作用的其他语句放到循环体中。下面这个程序用了正确的循环头: 第十五章 循环语句 224 这个 c 语言的例子,循环头很不一般: RecCount = 0; for( rewind(InFile); !feof(InFile); fgets(InputRec[RecCount], MAX_CHARS, InFile) ); { RecCount++; } 这个程序的循环头中的内容都与循环的控制有关,rewind()语句初始比循环,feof() 语句检查是否该终止循环,fgets()语句转向终止操作。修改 RecCount 语句并不使循环转向 终止,因而不把它放在循环头,在这种情况下用 while 循环或许是最合适的,但要用得好,仍 要用 for 循环头的形式。在这里给出了用 while 循环写的程序。 这个 C 程序较好地用了 while 循环: /* read all the records from a file */ rewind(InFile); RecCount = 0; while(!feof(InFile)) { fgets(InputRec[RecCount], MAX_CHARS, InFile); RecCount++; } 15.2.2 处理好循环体 以下几点对处理好循环体会有帮助: 用 begin 和 end 或{和}把循环体括起来。如果你容易忘记从哪到哪是循环体,就用括号 把它们括起来。括号不占任何空间和运算时间,也不破坏可读性,相反,括号能保证你不出错, 因此尽量用就是了。 尽量避免用空循环。在 C 中有可能出现空循环。要检查某一工作是否完成时,把检查作为 循环条件就可能出现了只有一句的空循环。如下例: 这个 c 程序是一个空循环: while((InputChar= getch())!=' \n') ; 此例中,循环为空循环,因为它只做了两件事,循环动作中——InputChar=getch()和检 查循环是否该终止——InputChar!='\n'下面是修改后的程序,循环所做的工作对读者来说相当 清楚,程序也显得明朗。 把空循环改为有操作语句的循环的 c 程序: do InputChar = getch(); 第十五章 循环语句 225 while(InputChar!=’\n’); 这个程序较好,因为在三行中完成一个操作总比在一行外加一个分号完成一个操作好。 把循环的“内务处理”工作放在循环的开头或结尾。“内务处理”工作指像 i := i+1 这 样的表达式,它的作用不是循环要做的事情,而是去控制循环。下面的例子中,内务处理工作 在末尾处完成。 这个 Pascal 程序把完成内务处理的语句放在末尾; StringIdx:=1; TtlLength:=0; while not eof(InputFile) do begin {do the work of the loop} ReadString(InputFile, StringIdx, Str); ... {prepare for next pass through the loop--housekeeping} StringIex:=StringIdx+1; TtLength:=TtLength + Length(Str) 这里是内务处理语句 end; 一般来说,你所初始化的循环变量往往是在内务处理部分要修改的变量。 使每个循环仅执行一项功能。一个循环一次做两件事并不能说这两件事是同时完成的。循 环应当像子程序一样一个只完成一件事且应做好。如果两个循环的效率比用一个循环的效率低, 那先用两循环编码并注明它们能合成一个循环以提高效率,然后用标准测试程序来对这部分进 行测试,如有必要最后才合并成一个循环。 15.2.3 退出循环 以下几点对如何退出循环会有帮助: 确保循环能终止。先要在脑中模仿,确信在各种条件下循环都能终止。这一点很重要。仔 细考虑正常与异常情形下循环的终止问题。 使循环的终止条件明显。如果用 for 循环且不用 goto 或 break 语句来退出循环,终止条件 应该很明显。同样,若用 while 或 repeat-until 循环,并把控制条件放在 while 或 repeat- until 句子中,循环中止条件也会很明显。关键是要把控制条件放在一处。 循环中不要强制改变控制循环变量从而达到提前终止循环的目的。下面这个程序就是这样 的: 这个 Pascal 程序强行改变循环控制变量: for i =1 to 100 do 第十五章 循环语句 226 begin { some Code } ... if(...) then i = 101 这里做得不好 {more code} ... end; 这个程序的本意是在某些条件下,改变控制变量的值为 101,这样大于 i 的范围 1~100, 循环终止。一个优秀的程序员是避免这样做的。一旦写好了 for 循环,控制变量就不在你的控 制之下了。若实在想在某些条件下终止,用 while 循环就能满足对终止条件的需求。 尽量避免直接用到循环控制变量的终值。这样用显得很不好。循环控制变量的终值随语言 和用法的不同而不同,在正常和异常情况下退出循环也会不同。即使你知道终值是什么,但别 人在读程序时却要考虑才知道。在循环体中的适当位置先把终值赋给一个变量,这种方法好些。 下面这个程序就乱用了终值。 这个 C 程序乱用了循环控制变量的终值: for ( i=0; i=SAFETY_LIMIT) begin PrintErrorMsg("Internal Error : Safety-Counter Violation."); exit(Error) 这里是安全计数器代码 end; ... until( Nodeˆ.Next = Nil ); 这个 Pascal 程序引进一个安全计数器,可能会导致额外的错误。如果安全计数器不是每个 循环都用,当你修改用到安全计数器的循环代码时,可能忘了去修改安全计数器。如果你用安 全计数器相当熟练,那么它就不会比别的语句更容易出错。 15.2.4 用 break 和 continue 语句 break 语句是一种辅助控制结构,它能使循环提前退出,break 使循环从正常出口退出,程 序继续执行接在循环后的程序。这里说的 break 是指属同一类的语句,在 C 中是 break,在 Pascal 中是 exit 或类似的结构,包括不支持 break 的语言中有相似功能的 goto 语句。 continue 语句和 break 一样同是辅助循环控制语句,但正好相反,continue 使程序又回到 控制体的开始并执行下一个循环。continue 语句是 if-then 语句的简写形式,而后者可能使 循环的余下部分不被执行。 用 break 和 continue 一定要谨慎。用 break 语句就不可能再把循环体看作一个黑盒子, 把控制循环退出的条件都写在一个语句里,这是简化循环的有力手段。用了 break 语句就要使 人从头到尾看你的循环体内容才能理解循环控制,这样就使得循环更难读了。 有选择性地用 break 语句。有些计算机科学家认为这种结构是合法的技巧,而另一些则认 为不然。既然你不知用 continue 和 break 好还是不好,那么你用它时应当小心可能用错了。其 实情形很简单,若非一定要用,尽可能不用。 在 while 循环中,若要用布尔量标志时就应考虑用 break 语句。在 while 循环中有时要增 第十五章 循环语句 228 加一个逻辑标志来模拟循环体的出口,这就使得程序难读。有时为了好看,在有几个 if 语句时, 下一个比上一个要缩进几列,这时可用 break,把 break 放在独立的语句段之后,使它靠近它 所属的代码段能减少嵌套,使程序易读。 要特别小心一个循环中许多 break 语句分散出现的情形。一个循环中包含了许多 break, 则表明对循环的结构或者对周围代码的作用还考虑得不清楚。若 break 语句出现多了,就表明 该循环若用许多小循环替代可能更好,因为一个大循环会有许多出口。循环中有多个 break 并 不说明一定有错误,但起码给出一个信号;这种用法不太好! 如果用 goto 来模拟 break,转向执行的语句应紧接在循环的后面。有时你很想让循环的出 口指向的不是紧跟在循环后的第一条语句而是更远,这时你就可能离用 goto 来做的危险尝试不 远了,或者你就处于那种要用 goto 来结束循环的境地。不要因为用了 goto 而把问题弄复杂了。 把 continue 放在循环的头前检查。continue 语句的一种很好的用法是把它放在循环的头 部检查,若满足某一条件才执行循环体。如下例程序,循环要做的是先读入记录,然后看是否 满足一定条件,若不满足,就放弃这个记录;若满足,就处理这个记录。这时把 continue 放在 循环的头部: 用 continue 比较安全的伪代码程序: while(not eof(File)) do read( Record, File ) if( Record.type<>TargetType ) then continue {process record of TargetType} ... end while 这种用 continue 的方法可使你避免在用 if 语句时,需把循环体往后缩几列的做法。但是若 continue 出现在循环体的中间或结尾,那最好还是用 if-then 替代。 15.2.5 检查循环边界 一个简单的循环通常要注意三种情况:初始情况、中间情况、结束情况。当你要编写一个 循环时,你头脑中要想清楚:在初始、中间、结尾情况下都不会出现边界错误。如果初始或结 尾情形可能出问题,仔细检查一下,如果循环包含了复杂的计算,拿出计算器核算一下。 进行这种检查是高效率与低效率程序员关键不同之处,高效率的程序员在脑中或用手算一 下,因为他们知道:这样做可以帮助发现问题。 低效率的程序员总是随意地编写,反复修改到最后发现应该是怎样做。如果循环不按设想 的那样去做,低效率的程序员总要把'<'改成'<='。如果这样还行不通,他们就要改变循环控制 变量了,或者加或者减 1。到最后,他们用这种方法幸运时,撞对了,但很可能把简单的错误 改得更隐晦。即使这种试凑方法最后把循环改对了,程序员也不知道为什么就改对了。 在脑中先想想或先算算有几个好处。如,在编程阶段减少错误,在调试时能很快发现错误, 第十五章 循环语句 229 且能更好地理解整个程序。先想想能使你知道代码是如何运行的,而试凑者则不然。 15.2.6 使用循环控制变量 以下几点对如何用循环变量有帮助; 在循环和数组中,只能用整数。一般说来,循环计数器应当是整数值,浮点数不好使。如, 你把 1.0 加到 42,897.0 上去得到的是 42,897.0 而非 42,898.0,若这种情形发生在循环计数器 上,就发生死循环了。 要用有意义的变量名使得循环嵌套易读。循环变量通常就用作数组下标。如果数组是一维 的,你可以用 i,j 或 k 作下标去标识它。但是若数组是二维或多维的,你就要用有意义的下标 去标明你在做什么了。有意义的数组下标名能清楚说明每一层循环的目的和要处理的数组元素。 下面这段代码没有遵循上述规则,用无意义的变量名 i、j、k: 这个 Pascal 程序用了无意义的变量名: for i:=1 to NumPayCodes do for j := 1 to 12 do for k := 1 to NumDivisions do Sum := Sum + Transaction[j,i,k]; 你明白 Transaction 下标的意义吗?i、j、k 告诉你 Transaction 的含义了吗?一旦这样 定义 Transaction,在循环中你就无法确定下标的顺序是否对了。 这个 Pascal 程序的循环变量意义明朗: for PayCodeIdx := 1 to NumPayCodes do for Month := 1 to 12 do for DivisionIdx := 1 to NumDivisions do Sum := Sum + Transaction[Month, PayCodeIdx, DivisionIdx]; 这回你知道 Transction 数组下标的含义了吗?在本例中,答案很清楚:变量 Paycodelndex、 Month、DivisionIdx 很清楚地给出了各自代表意思,而 i、j、k 则不能。计算机在读下标时同 样简单,但人读起来却觉得第二个比第一个简单多了。记住,你的最基本读者是人而非计算机。 用有意义的变量名以避免循环变量用重复了。若习惯都用 i、j、k 作变量可能引起冲突—— 一个循环中不同地方用了同一个循环变量名,如下例子: 这个 c 程序中循环变量冲突: for(i=0; i -1 ) do Begin DoSomething( Data ); GetData (InputFile , Data ); End; 这个所谓的一般例子包含了一个错误。当 Data 等于-1时,条件部分检查到-1就退出 循环,这时,DoSomething()不可能执行。而用 goto 的程序在检查到-1前已经执行过了 DoSomething()。写有这个程序的书,本想用它来说明用结构化写程序显得多么容易。但没 想到转换却带来了错误。但该书作者也不用感到害臊,因为别的书也有类似的错误。 下面这个程序没用 goto 但是正确。 这个 Pascal 程序与有 goto 的程序是同一目的,但这里无 goto 且程序正确。 Repeat GetData (InputFile , Data ); If ( not eof( InputFile ) ) then DoSomething ( Data ); Until (Data = -1 or eof( InputFile ) ); 即使程序的转换正确,但这个例子还是显得很虚假,因为它们把 goto 的用法看得太繁 琐了。上述情况并不是那种思想的程序员愿用 goto 的情形。下面这种情形是常见的,即使 极不愿用 goto 的程序员有时为了增强程序的可读性与可维护性,却选用了 goto。 下面几节给出了一些情况,在这种情形下,是否用 goto,在有经验的程序员那是有争议 的,讨论用和不用 goto 的一些代码,最后得到一个折衷答案。 16.1.4 出错处理和 goto 语句 写交互式程序代码要做的几件事是,要特别注意出错处理和出错时要清除资源。下面这 个代码要清除一组文件。程序首先读入要清除的文件组,然后找到每一个文件,覆盖掉并清 除它,程序每一步都要检错。 这个 Pascal 程序用 goto 来处理出错和清除资源: procedure PurgeFiles( var ErrorState : ERROR_CODE ); {This routine purges a group of files.} var FileIndex : Integer; FileHandle : FILEHANDLE_T; FileList : FILELIST_T; 第 16 章 少见的控制结构 237 NumFileToPurge : Integer; Label END_PROC; Begin MakePurgeFileList ( FileList ,NumFilesToPurge ); ErrorState := Success; FileIndex := 0; While ( FileIndex < NumFileToPurge ) do Begin FileIndex := FileIndex + 1 ; If not FindFile ( FileList[ FileIndex ], FileHandle ) then Begin ErrorState := FileFindError; Goto END_PROC ——这里是一个 goto End; If not OpenFile(FileHandle) then Begin ErrorState:=FileOpenError; Goto END_PROC ——这里是一个 goto End; If not OverWriteFile(FileHandle) then Begin ErrorState:=FileOverWriteError; Goto END_PROC ——这里是一个 goto End; If Erase( FileHandle ) then Begin ErrorState := FileEraseError; Goto END_PROC ——这里是一个 goto End End;{while} END_PROC; ——这里是 goto 的标号 DeletePurgeFileList( FileList ,NumFilesToPurge ) 第 16 章 少见的控制结构 238 End; {PurgeFiles} 这个程序是那种有经验程序员肯定要用 goto 的情形。同样的,当程序要分配和清除资 源时(像内存、或处理字形、窗口、打印机),也要用 goto。这种情形下用 goto 通常是为了 复制代码或清除资源。若遇到这种情况,程序员就要掂量是 goto 的缺点令人讨厌呢?还是 复制代码那令人头痛的维护更讨厌呢?最后还是认为 goto 的缺点更可忍受。 可以用许多方法重新编写上述程序而不用 goto,把两种比较一下。下面是不用 goto 的 方法: 用 if 嵌套重新写程序。用嵌套的 if 语句重新写程序时,嵌套 if 语句是为了在上一个条 件满足后才进到这一层嵌套的。这是不用 goto 的标准的、书本式的结构化编程方法。下面 用标准的方法重新编程。 这 Pascal 代码用 if 嵌套来避免用 goto: procedure PurgeFiles( var ErrorState : ERROR_CODE ); {This routine pruges a group of files.} var FileIndex : Ingeter; FileHandle : FILEHANDLE_T; FileList : FILELIST_T; NumFilesToPurges: Integer; begin MakePurgeFileList( FileList , NumFilesToPurge ); ErrorState := Success; FileIndex := 0; While ( FileIndex < NumFilesToPurge and ErrorState = Success ) do—— 这个 While 已经改为增 加测试错误 状态 begin FileIndex := FileIndex + 1 ; If FindFile ( FileList[ FileIndex ] , FileHandle ) then Begin If OpenFile ( FileHandle ) then begin If OverWriteFile ( FileHandle ) then Begin If not Erase ( FileHandle ) then Begin ErrorState := FileEraseError End 第 16 章 少见的控制结构 239 end else {couldn’t overwritefile} begin ErrorState := FileOverWriteError end end else {couldn’t open file} begin ErrorState := FileOpenError end end else {couldn’t find file} begin ErrorState := FileFindError ——这行与调用它的语句距离有 23 行 end end; {While} DeletePurgeFileList( FileList ,NumFilesToPurge ) end; {PurgeFiles} 习惯于编程不用 goto 的人对这段代码可能看得很清楚。如果你把程序写成了上面例子 这样,那么在读时你就不必担心由 goto 带来很大跳跃了。 用 if 嵌套的主要弊病是嵌套层次太多、太深。为了读懂代码,你得同时把所有嵌套的 if 都记在脑中。而且处理出错的代码距引起它的代码距离太远:如在上例中,ErrorState 到 FileFindError 的距离是23行。 用 goto 的程序,发现错误的语句离处理出错的语句都不超过四行,而且你无需同时把 整个结构都放在脑中,你尽可把不成立的条件置之不理而集中精力于下一步操作。由此看来, 在这种情况下 goto 倒是更可读与易维护了。 重新编程时可调一个状态变量。定义一个状态变量以指示程序是否处于错误状态。上例 中已经用到了 ErrorState 这个状态变量,因而下面还用它: 这个 Pascal 代码设置状态变量以免用 goto: procedure PurgeFiles( var ErrorState : Error_CODE ); {This routine pruge a group of files.} var FileIndex : Integer; FileHandle : FILEHANDLE_T; FileList : FILELIST_T; NumFilesToPurge : Integer; 第 16 章 少见的控制结构 240 begin MakePurgeFileList ( FileList , NumFilesToPurge ); ErrorState := Success ; 这个 While 测 试已经增 加了一个 ErrorState FileIndex := 0; While ( FileIndex < NumFilesToPurge ) and ( ErrorState = Success ) do begin FileIndex := FileIndex + 1; if not FindFile( FileList[ FileIndex ] , FileHandle ) then begin ErrorState := FileFindError; end; if ( ErrorState = Success ) then —— 测试这个状态变量 begin if not OpenFile( FileHandle ) then begin ErrorState := FileOpenError end end; if ( ErrorState = Success ) then —— 测试这个状态变量 begin if not OverwriteFile( FileHandle ) then begin ErrorState := FileOverwriteError end end; if ( ErrorState = Success ) then —— 测试这个状态变量 begin if not Erase( FileHandle ) then begin ErrorState := FileEraseError end end end; {while} DeletePurgeFileList( FileList , NumFilesToPurge ) end; {PurgeFiles} 第 16 章 少见的控制结构 241 设置状态变量的好处是避免 if-then-else 结构的嵌套层次太深,且易于理解。这种方 法也使跟在 if-then-else 条件后的实际操作语句离测试条件更近,且完全不用 else 语句。 为理解嵌套 if 语句是需动一番脑筋的,而设置状态变量的方法则易于理解,因为它接 近于人的思维方式。你要先找到文件,如果无错,就打开文件;如果还不出错,覆盖文件; 如果还不出错…。 这种方法的不足之处在于状态变量并不如所想象的那么好,使用状态变量时你要表示清 楚,否则读者不能理解变量是什么意思。在上例中,用了有含义的整数类型的状态变量相当 有帮助。 各方法比较。三种方法各有优点。goto 方法避免嵌套太深和不必要的条件测试,但同时 也有 goto 固有的弊病;嵌套的 if 方法避免用 goto 但嵌套深且增大了程序的复杂性;设置 状态变量法避免用 goto 且不会使嵌套太深,但增加了额外的条件判断。 状态变量法相对前两个好些。因为它使程序易读且使问题简化,但它不可能在所有情况 下都好用。从整体上来讲,这三种方法在编程时都能用得很好,这时就需要全盘考虑,权衡 利弊,选择最好的方法。 16.1.5 goto 和 else 语句中的共用代码 一种挑战性的情况是,若程序有两个条件测试语句和一个 else 语句,而你又只想执行 一个条件语句中的代码和 else 中的部分代码,这时就得用 goto 语句,下面这个例子是迫使 你用 goto 的情况; 这个 C 语言程序用 goto 转向执行 else 中的共用代码: if ( StatusOK ) { if ( DataAvail ) { ImportantVar = x; Goto MID_LOOP; } } else { ImportantVar = GetVal( ); MID_LOOP ; /* lots of code */ …… } 这个程序的高明之处在于它用了一个逻辑的迂回——它可不像你所见的那么好读,但若 不用 goto 你很难再写出另外的样子出来。如果你认为你能很容易地不用 goto 就写出新程序 来。那么让别人检查看看。好些有经验的程序员都写错了。 第 16 章 少见的控制结构 242 改写的方法有几种,你可以复制代码、把共用的代码放在一个子程序里面,且从两个地 方调用它、或重新写条件测试语句。在多数语言中,改写并不比写原程序快,虽然应当是一 样快的。除非循环在程序中多次使用,否则编写时不用考虑效率。 改写最好的方法莫过于把/*lots of code*/部分放在一个子程序里。你可以在代码原来 出现的地方和 goto 语句转向的地方调用它而保留原结构的条件语句。下面是程序: 这个 C 程序把 else 中的共同程序部分写成一个子程序 if ( StatusOK ) { if ( DataAvail ) { ImportantVar = x; DoLotOfCode( ImportantVar ); } } else { ImportantVar = GetVal( ); DoLotsOfCode( ImportantVar ); } 通常,写一个新子程序(C 中可用宏定义)是最好的方法。但有时把代码放进一个子程 序中实际是不可能的。这时只能修改原结构中的条件部分而无需把共用部分放到一个子程序 中。 这个 C 程序用 else 中的共用代码替换 goto: if ( ( StatusOK && DataAvai ) || !StatusOK ) { if ( StatusOK && DataAvail ) ImportantVar = x; Else ImportantVar = GetVal( ); /* lots of code */ …… } 这种转换方法不会出错但很机械。程序意义虽然一样,但却多出来的两个地方测试 StatusOK 和一个地方测试 DataAvail。使得条件测试显得很麻烦。注意:第一个 if 条件中 StatusOK 值不必测试两次,你也可以把第二个 if 的条件中对 DataAvail 的测试减少。 16.1.6 使用 goto 方法的总结 用 goto 是一个个人爱好的问题。我的意见是,十个 goto 中有九个可以用相应的结构化结 构来替换。在那些简单情形下,你可以完全替换 goto,在复杂情况下,十个中也有九个可以不 用:你可以把部分代码写成一个小的子程序调用;用嵌套 if 语句;用状态变量代替;或者重新 第 16 章 少见的控制结构 243 设计控制条件的结构。消除 goto 是很难的,但它却是很好的脑力活动,前面讨论过的方法会对 你有所帮助。 如果 100 个用 goto 的情形中有一个靠 goto 很好地解决问题的方法,这时你要把它用得好 些。只要问题能解决,我们是不约束用不用 goto 的,但应当注意,最好还是少用或不用 goto 编程,因为有些问题你可能还没弄清楚。 下面对用 goto 的方法作一总结: · 若语言不支持结构化语句,那就用 goto 去模仿结构化控制结构,但一定要写得正确。 不要把 goto 灵活性用得出了格。 · 能用结构化结构的地方尽量不用 goto. · 评价 goto 的性能的方法是看其是否提高效率,在多数情况下,你可以把 goto 替换而 增加可读性且不失效率。在少数例外情况下,用 goto 确实有效且不能用别的方法来 代替。 · 每个程序至多用一个 goto 语句,除非你是用它来模仿结构化的结构。 · 使 goto 语句转向循环前面而不要往后转移,除非是在模仿结构化结构中。 · 保证 goto 转向的语句标号都要用上,若有没有用到的,则表明掉了部分代码,或该 转向那部分代码没有标上标号。所有给出的标号都要用上,若没用上,就去掉。 · 应保证 goto 语句不会产生执行不到的代码。 · 用不用 goto 应全面考虑,程序员对用不用 goto 考虑后,选择了 goto,那么这个 goto 可能是好的选择。 16.2 Return 语句 return 和 exit 语句都属控制结构语句,它们使程序从一个子程序中退出。它们使子程序 从正常出口退出到调用它的程序中去。这里 return 泛指有类似作用的一类词:return、exit 和相似的结构,下面说明如何使用 return 语句。 减少每个程序中的 return 语句。如果你在看一个子程序的后部分,而又不清楚在前面是 否有 return,那么就很难读懂这个程序。 用 return 增强可读性。有些子程序中,一旦你知道了答案,就想退回到调用它的程序中 去,如果子程序不需要清除,那么不立即退出意味着要执行别的代码。 下面这段程序是个较好的例子。它从子程序中多个地方退出,满足多种情况。 这个 C 程序是较好地从子程序中多个地方退出的例子: int Compare ( int Value1, int Value2 ) { if ( Value1 < Value2 ) return( LessThan ); 第 16 章 少见的控制结构 244 else if ( Value1 > Value2 ); return( GreaterThan ); else return( Equal ); } 16.3 递归调用 在一个递归调用中,子程序本身只解决很小一部分问题,而把问题分成许多小片段,然后 调用自己,来解决比本身更小的片段。递归调用一般在这种情形下,即解决问题的一小部分很 容易,但整个问题很复杂。 递归调用不常用,但若用好了,它能解决其他方法不好解决的大问题。下面是递归解决排 序算法的例子。 这个 Pascal 程序用递归解决排序算法: Procedure QuickSort ( FirstIdx : integer; LastIdx : integer; Names : NAME_ARRAY ); var MidPoint : integer; begin if ( LastIdx > FirstIdx ) then begin Partition( FirstIdx , LastIdx , Names , MidPoint ); QuickSort( FirstIdx , MidPoint – 1 , Names ); QuickSort( MidPoint + 1 , LastIdx , Names ); 这里是递归调用 end end; 这个程序中,排序算法把一个数组分成两部分,然后调用自己再去排序那两个半个的数组, 如此下去,直到不能再分为止。 一般说来,递归调用代码较短,执行速度慢,占用堆栈空间大。若问题较小,递归调用可 得到简单、巧妙的解;对稍大的问题,它们产生简单、巧妙、难于理解的解。对大多数问题, 递归调用得到很大的复杂解——在这种情形下,简单的循环或许更好理解。用递归要有选择。 16.3.1 递归调用的例子 假设你用一个数据结构代表一个迷宫。一个迷宫就是一个网格,在网格的每一点上你可以 向左转,也可向右转,可以向上,亦可向下。在每一点上,你有不止一种选择。 那么你如何写一个程序去解决这个问题即通过迷宫呢?若用递归调用,问题相当直观。从 第 16 章 少见的控制结构 245 起始点开始,试走各种可能的路径,直到最后走出迷宫。第一次你走到一个点,试着往左:若 不能往左,就试着向上或向下;若都不行,那就往右,你不用怕迷路,因为每过一点,你做下 标记,因此你不会从同一个地方走过两次。 下面是用递归写的代码: 用递归写过迷宫的 C 程序 BOOLEAN function FindPathThroughMaze ( MAZE_T MAZE , POINT Position ) { /* if the position has already been tried,don’t try it again */ if (alreadyTried(Maze,Position)) return(FALSE); /* if this position is the exit,declare success */ if (ThisIsTheExit(maze,Position)) return(TRUE); /* remember that this position has been tried */ RememberPosition(Maze,Position); /* check the paths to the left,up,down,and to the right; if any path is successful,stop looking */ if ( MoveLeft( Maze , Position , &NewPosition ) ) if ( FindPathThroughMaze ( Maze , NewPosition ) ) return( TRUE ); if ( MoveUp( Maze , Position , &NewPosition ) ) 第 16 章 少见的控制结构 246 if ( FindPathThroughMaze ( Maze , NewPosition ) ) return (TRUE); if ( MoveDown ( Maze , Position , &NewPosition ) ) if ( FindPathThroughMaze ( Maze , NewPosition ) ) return (TRUE ); if ( MoveRight ( Maze , Position , &NewPosition ) ) if ( FindPathThroughMaze ( Maze , NewPosition ) ) return ( TRUE); return( FALSE ); } 代码的第一行检查是否已经走过那点。写递归程序要防止无限递归调用。在上例中,若不 检查是否走过,那可能产生无限递归。 程序第二段检查这一点是否是通向迷宫出口的。如果 ThisIsTheExit()返回 TRUE(真),那 么子程序也返回真。 第三句记录下这一点已经走过。这样防止走入循环路径而导致无限递归调用。 下面各行找出各左、上、下、右的路径。在找出通过迷宫的路径以后,程序返回 TRUE。 这个程序的思想很直观。许多人觉得递归调用自己而感到不舒服,但在本例中,其它方法 肯定都复杂而递归调用是很好的。 16.3.2 怎样用递归 下面是用递归的几点建议: 要保证递归能终止。检查程序确保含有一个不再用递归调用的路径,这通常表明程序已经 满足条件不再需要递归了。在迷宫例子中,条件测试 AlreadyTried()和 ThisIsTheExit()保证 递归调用停止。 设置安全计数器防止无限递归。如果不许用简单的条件测试,如上例所示,要防止无限递 归,那就应设安全计数器。安全计数器应当是每次递归时不能改动的变量,可用一个全局变量 或把安全计数器作为程序的参数。 下面是例子: 用安全变量防止无限递归的 Pascal 程序: Procedure RecursiveProc( var SafetyCounter : integer ); /*这个递归程序必须可以改变 SafetyCounter 的值,它在其中是一个 Var 参数*/ begin if ( SafetyCounter > SAFETY_LIMIT ) then exit; SafetyCounter : = SafetyCounter + 1; …… end; 第 16 章 少见的控制结构 247 在上例中,如果超出安全计数器的范围,则停止递归调用。 把递归调用限制在一个子程序里。循环递归调用(A 调用 B,B 调用 C,C 调用 A)是很危险 的,因为程序很难检查。在一个程序内的递归调用就够麻烦的,要理解程序间的递归调用太难。 如果你的程序用了循环递归,那就修改代码,使递归在一个子程序中。如果你不能修改且认为 这种递归是最好的方法,那就一定要设置安全计数器。 要注意堆栈。写递归调用无法计算程序要用多少堆栈空间,而且也无法事先预测程序是如 何运行的。你可采取几个步骤来控制程序运行时的行为。 首先,若用了安全计数器,在设置安全计数器的最大值时,要考虑到可能分配给你多大的 堆栈空间。安全计数器的最大值要限制在不使堆栈溢出的范围内。 其次,你可估算一下,在运行递归程序时要用多少内存。在运行之前,用可辨识的值充满 相应内存;0 和 0xCC 是一个很好的值,把程序编译一下,然后用 DEBUG 去看对应的内存,看看 程序占用了多少堆栈空间。查查 0 和 0xCC 没有被改变的点。然后用这点来估计你程序占用的堆 栈。 不要用递归去计算阶乘或菲波那契(fibounacci)数。计算机教科书上经常出现的一个问题 是给出了许多不太好的递归调用例子。典型例子是计算阶乘或计算 fibounacci 数列。递归调用 是一个强有力的工具,但用在这里都显得很笨。假如我请人给我编一个计算阶乘的程序,而他 用递归调用算法,那我宁愿换个人。下面是用递归调用计算阶乘的程序: 这个 Pascal 程序用递归调用算阶乘不太好: Function Factorial(Number:integer):integer; begin If ( Number = 1 ) then Factorial := 1 Else Factorial := Number * Factorial ( Number – 1 ); end; 除了速度慢,计算机用到的内存难以估计外,递归调用在这个程序中要比用循环难懂多了。 下面用循环编程序: 这个 Pascal 程序用循环来计算阶乘比较好: Function Factorial( Number : integer ) : integer; var IntermediateResult : integer; Factor : integer; begin IntermediateResult := -1; For Factor := 2 to Number do IntermediateResult := InterMediateResult * Factor ; Factorial := IntermediateResult end; 你可以从这件事得到三点教训。第一,计算机教科书的这些所谓的例子对于说明递归的作 第 16 章 少见的控制结构 248 用没有一点好处;第二点也就是最重要的一点,递归调用的功能要比用来计算阶乘和 fibonacci 数列强大得多。有时你可用堆栈加循环做递归调用能做的同样的事情。有时用这种方法好,有 时另一种更合适,你得仔细权衡选用一种。 16.3.3 检查表 少见的控制结构 goto · goto 是最后的选择吗?用 goto 使程序更好读更好维护吗? · 用 goto 是为效率的目的吗?用 goto 达到此目的了吗? · 一个程序是否只用一个 goto 呢? · goto 只转向前面的程序段而不是转向其后面的程序段吗?(后面指已执行过程序) · goto 所转向的标号都有了吗? return · 每个子程序的 return 数目是否最少? · return 增强了可读性了吗? 递归调用 · 用递归调用的代码含使递归结束的语句吗? · 程序设置了安全计数器来保证递归调用终止了吗? · 是否只在一个程序中用递归调用? · 递归调用的深度是否限制在程序堆栈容量可满足的条件下? · 递归调用是实现程序的最优途径吗?它比循环更简单吗? 16.4 小 结 · 有些情况下,goto 是编出易读易维护程序的最好方法。 · 多重 return 有时增强了程序的可读性与可维护性,并且防止多重嵌套逻辑,但没必要 只想到怎样用好 return。 · 在问题较简单时,递归调用能把问题很巧妙解决。要慎用递归调用。 第十七章 常见的控制问题 249 第十七章 常见的控制问题 目录 17.1 布尔表达式 17.2 复合语句(块) 17.3 空语句 17.4 防止危险的深层嵌套 17.5 结构化编程的作用 17.6 用 goto 模拟结构化结构 17.7 控制结构和复杂性 17.8 小结 相关章节 条件代码;见第 14 章 循环的代码:见第 5 章 少见的控制结构:见第 16 章 不讨论在编写控制结构时碰到的几个问题,那么关于控制的任何讨论都是不完全的。这一 章所讲的东西是细节性的、实用性很强的。若你想看有关控制结构的理论,那就请集中精力看 17.5 节关于“结构化编程的作用”和 17.7 节中关于“对控制结构和复杂性之间关系”的研究好 了。 17.1 布尔表达式 除了那些按顺序往下计算的最简单控制结构,几乎所有的结构都依赖于对布尔表达式的计 算。 用 True 和 False 作为布尔变量 用 True 和 False(真和假)作为布尔表达式结果的标识符,而不要用 0 和 1。像 Pascal 之类 的语言有布尔型变量来支持定义 True 和 False 作为标识符。要弄清楚,对布尔型变量,你还只 能用 True 和 False 来给它赋值而不能用其它的,对那些没有布尔型变量的语言,你需用一些规 则来使布尔表达式易读。如下例子; 这个 Basic 程序任意定义布尔变量的值: 1200 IF PRINTERROR = 0 GOSUB 2000 ' initialize printer 1210 IF PRINTERROR = 1 GOSUB 3000 ' notify user of error 1230 ' 1240 IF REPORTSELECTED = 1 GOSUB 4000 ' print report 第十七章 常见的控制问题 250 1250 IF SUMMARYSELEEED = I GOSUB 5000 'print summary 1260 ' 1270 lF PRINTERROR = 0 G0SUB 6000 'clean up successful printing 如果类似 0 和 1 这样的标志很普遍的话,那会有什么错呢?问题是当测试条件为真还是假 的时候程序应当执行 GOSUB 吗?不清楚。在程序段中没有什么规则来说明是“1”代表真,“0” 代表假。正好相反,甚至“l”和“0”是否表示“真”和“假”的意思都弄不清楚。比如在 IF REPORTSELECTED = l 这一行,“1”很容易代表第一个记录,“2”代表第二个,“3”代表第三个, 在这个代码中,并没有什么标准说明”1”表示的是真还是假,同样,对“0”也是如此。 用 True 和 False 之类的词来表示布尔表达式的结果,如果所用语言不支持这种类型,用预 定义宏或全局变量的方法来创造一个。下面的例子用全局变量 True,False 来重新编写: 这个 Basic 程序用全局变量(True 和 False)来表示布尔变量的值: 110 TRUE = 1 110 FALSE =0 ⋯⋯ 1200 IF PRINTERROR = FALSE GOSUB 2000 ' initialize printer 1210 IF PRINTERROR = TRUE GOSUB 3000 ' notify user of error 1230 ' 1240 IF REPORTSELECTED = FALSE GOSUB 4000 ' print report 1250 IF SUMMARYSELECTED = TURE GOSUB 5000 ' print Sllttifi13Yy 1260 ' 1270 IF PRINTERROR = FALSE GOSUB 6000 ' clean up successful printing 用 True 和 False 作变量名使得用意很清楚。你不用记“1”和“0”表示什么意思,也不用 偶尔回头检查。而且在重新编写了以后发现,原程序中的那些“1”和“0”并不作为布尔量的 标志。IF REPORTSELECTED = 1 这一行根本不是一个布尔测试表达式,它只是检查第一个记录被 选中了没有。 这种方法可告诉读者这一行是用作布尔测试目的。你不太可能用 TRUE 来表示 FALSE(假) 的意思,但把“l”当作“0”的意思却有可能,而且用 True 和 False 还可避免那令人眼花缭乱 的“0”和“1”在程序中到处出现的。下面几点意见对在布尔测试条件定义 True 和 False 很有 帮助。 在 C 中用 1 == 1 的形式定义 TRUE 和 FALSE。在 C 中,有时很难记住是否 TRUE 等于 1 和 FALSE 等于 0 或者正好相反,你得记住测试 FALSE 和测试空终止符或其它零值一样。否则用下面定义 TRUE 和 FALSE 的方法来避免出现这个问题。 这个 C 程序用易于记住的方法定义布尔量: # define TRUE (1 ==1) # define FALSE(!TRUE) 隐含地把布尔变量与 False 比较。如果所用语言支持布尔变量,把测试表达式当作布尔表 达式来看待显得清楚。比如: while( not Done)⋯ while( a = b)⋯ 用上面的表达式比用下面的清楚: 第十七章 常见的控制问题 251 while( Done = False )⋯ while ( (a = b) = True ) ⋯ 用隐含的比较方式可减少测试条件语句中词的个数,读程序时可少记好多东西,因此表达 式读起来就简单些。 如果使用的语言不支持布尔变量,你就得去模仿。你也可能有时不能用这种技巧,因为在 有些语句像 while(not Done)之类语句,不能模仿 True 和 False 用来作检测。 使复杂的表达式简单些 采用以下几步来简化表达式: 把复杂的测试条件用中间的布尔变量变成几个部分。宁愿定义几个奇怪的中间变量并给它 们赋值,这样可编写简单的测试条件。 把复杂的表达式写成一个布尔型函数。如果测试条件要经常重复用到或很分散,把这部分 代码写成函数。如下例,测试条件很复杂。 这个 Pascal 程序的测试条件很复杂: if ( ( eof ( InputFile ) and ( Not InputError ) ) and ( ( MIN_ACCEPTABLE_ELEMENTS_C<CountElementsRead ) and (CountElementsRead<= MAX_ELEMENTS_ C= = or ( Not ErrorProcessing) )then { do something or other } ⋯ 如果你对测试条件部分不感兴趣的话,那要你读这个程序真是一件可怕的事情。把这部分 写成一个函数,就能把条件部分独立起来,除非读者感兴趣,否则可以忽略这部分。下面这个 程序给出了怎样把 if 的条件部分写成一个函数: 这个 Pascal 程序把测试条件部分写成一个布尔型函数: Function FileReadError ( var FILE InputFile; Boolean InputError; Integer CountElementsRead ): Boolean; begin if ( ( eof ( InputFile ) and ( Not InputError ) ) and ( ( MIN_ACCEPTABLE_ELEMENTS_C<CountElementsRead = and ( CountElementsRead< = MAX_ ELEMENTS _C= = or ( Not ErrorPocessing ) )then FileReadError := False 第十七章 常见的控制问题 252 else FileReadError:=True; end; 上例中把 Error_Processing 定义为一个标志现在过程状态的布尔型函数。现在,当你读整 个主程序时,可不必去管复杂的测试条件部分: 这个 Pascal 的主程序没有复杂的测试条件: if( not FileReadError( InPutFile, InPutError, CountElementsRead) then { do something of other } ⋯ 如果测试条件仅用一次,你可能认为没有把这部分写成一个子程序的必要。但把这部分编 成一个子程序并给出一个合适的名字,那么不仅能增大可读性,而且让你一看就明白这部分代 码的作用,因而很有必要这样做。 用决策表代替复杂的条件。有时复杂的测试条件涉及几个变量。若用决策表去编这个测试 条件部分则显得比用 if 或 case 好。一个决策表使得开始编程时很容易,因为它仅需几行代码 而且不需什么复杂的控制结构。这种减小复杂性的方法会降低出错的机会。若要修改数据,仅 需修改决策表而无需修改程序本身,仅需更改数据结构的内容。 17.1.3 编写肯定形式的布尔型表达式 不少人对较长的否定形式的表达式理解起来很困难。也就是说大多数人对否定太多的句子 来困难。为避免出现复杂的否定形式布尔型表达式,你可依从以下几点: 在 if 语句中,把条件从否定形式转化为肯定形式,再把 if 和 else 语句后跟着的代码对换。 如下例所示: 这个 Pascal 程序乱用否定形式的测试条件 if( not StatusOK ) begin {do something} ⋯ end else begin {do something else} ⋯ end; 你可以把程序改为肯定形式表达式: 这个 Pascal 程序用肯定形式的布尔型测试条件显得很直观: if( StatusOK ) begin ——这个测试条件转换为肯定形式 {do somthing else} ——这个模块中的代码巳经转换 ⋯ end; else begin 第十七章 常见的控制问题 253 {do something} ⋯ end; 这一段代码与前一段代码实际上是一回事,但比前一个好读,因为把否定形式的表达式转 换成了肯定形式的表达式。 当然,你可以选用不同的变量名,但其中一个要与真值的意思相反。在上例中,可用 ErrorDetected 替换 StatusOK,它在 StatusOK 错误时表示正确的意思。 用 DeMorgen 定律去简化否定形式的布尔型测试条件。DeMorgen 定律揭示了在取反时一 个表达式与另一个表达式之间的关系。比如下面这个代码段; 否定形式测试条件的 Pascal 程序: if( not DisplayOK or not PrinterOK ) then ⋯ 在逻辑上它与下面这段代码相等,这个 Pascal 程序应用了 DeMorgen 定律简化: if(( not DisplayOK and PrinterOK )) then⋯ 这里你无需对调 if 和 else 语句后的可执行代码。上述两个表达式在逻辑上是一致的。把 DeMorgen 定律应用于逻辑运算 and 或 or 或其它运算时,你把每个运算取反,对换 and 和 or, 然后整个表达式取反,表 17-l 归纳了 DeMorgen 定律各种可能的转换。 表 17-1 应用 DeMorgen 定律转换逻辑表达式 初始表达式 相应表达式 not A and not B not(A or B) not A and B not(A or not B) A and not B not(not A or B) A and B not (not A and not B) Not A or not B not(A and B) Not A or B * not(A and not B) A or not B not (not A and B) A or B not (not A and not B) *例子中已用到 17.1.4 用括号使布尔型表达式清晰 如果布尔型表达式较复杂,用括号使表达式意思更明晰,而不能仅依靠语言运算的顺序。 读者并不了解语言是怎样去运算布尔型表达式的,因此用括号可解决这个问题,读者无需知道 内部细节。如果你是一个聪明的程序员,你不必依赖自己和读者来记运算优先级,特别是几种 语言混用时,用括号不像打电报,你无需为多写的字符付出代价。 下面这个例子没有适当多用括号,这个 C 程序表达式中少许多括号: if ( a< b = = c = =d ) ⋯ 这个程序一开始就被那个条件表达式弄得昏头转向,但更令人难以捉摸的是不清楚条件表 达式的意思是 ( a< b )= =( c = =d ) 呢还是( ( a 0 ) do ⋯ 假如算了整个式子,在最后一次循环时就会出错,当变量 i 等于 MaxElements+1 时,表达 式 item 目等于 item[MaxElements+1],这个数组下标有错误(超出维数)。或许你要说你仅看 数组的值,不改变它,也就无所谓。这种说法在 Macintosh 和 MS-DOS 操作系统中是正确的, 但若操作系统是一个保护模式,像 Microsoft Windows 或 OS/2,你可能就改变了保护性。在 Pascal、basic 中也是这样。 可重写测试条件,避免出错。 这个 Pascal 程序测试条件正确: while( i<= MaxElements) do if( item[i] <> 0) then … 这个程序正确是因为除非 i 小于或等于 MaxElements,否则不计算 item[i]。 第十七章 常见的控制问题 255 许多高级的语言提供在前部分防止这类错误的规则。比如,C 和 Pascal 用短路法计算,如 果第一个运算 and 是假,那么第二个运算不再执行,因为整个式就已经是假了。也就是说,在 C 和 Pascal 中。 if something False and somecondition 被计算的部分是 if Something False。当 Something 被证明为假时,整个计算停止。 短路计算类似于 or 操作。在 C 和 Pascal 中, if something True or somecondition 假如 if somethingTrue 是真,那么就仅执行这一部分,整个计算停止。正是考虑到这种方 法,下面的语句较好而合法的。 用短路法计算测试条件的 Pascal 例子: if ((Denominator <>0) and (Item/Denominator>MinVal))do⋯ 当 Demominator 等于 0 时,整个表达式计算会出现被 0 除错误。但既然当第一部分为真(不 等 0)时第二部分才被计算,因而不会出现 Denominator 被零除的情形,也就不会出被零除的错 误。 另外,既然 and 操作是从左到右运算的,下面的语句可能出错; 这个 Pascal 程序不能用短路法避免错误; if((Item/Denominator0 ) do ⋯ 在这个例子中,Item/Denominator 在判断 Denominator<> 0 之前运算,所以程序会出现被 零除错误。 不同的语言采用不同的运算方法,而语言设计者又倾向于擅自采用所爱好的表达算法。因 此要查你所用语言是何种算法,就得查阅相应版本的手册。但既然读者对这方面理解得不如你 那么深,那就用括号标明你的意图,而不仅仅依赖于运算顺序和短路运算法。 17.1.6 按数轴上的顺序编写数字算式 按数轴的顺序组织数字运算。一般说来,仔细组织程序的数字测试条件,以便于比较,如 下例: MinElmts <= i and i<= MaxElmts i < MinElmts or MaxElmts < i 这种思想是按从小到大的顺序从左到右安排各部分。上例中,第一行 MinElmts 和 MaxElmts 是两个端点,因此把它放在这句的两端。变量 i 假设处于这两者之间,因此放在句子中间。第 二句的目的是检查 i 是否超出范围,因此 i 放在句子的两端而 MinElmts 和 MaxElmts 放在里面。 这种方法一下子就勾画出你作比较的意图。 MinElnts <= i and i<= MaxElmts MinElmts MaxElmts Valid values for I 第十七章 常见的控制问题 256 i < MinElm or MaxElmts < i MinElmts MinElmts Valid values for i 如果仅把 i 与 MinElmts 比较,i 的位置随条件的不同而变化,如果 i 被认为是小些,你得 这样写比较语句: while(iMinElmts and I 10) then if( Qty > 100) then if( Qty > 1000) then Discount :=0.10 else Discount := 0.05 else Discount := 0.025 else Discount := 0.0; 这个程序的测试条件太乱太散,这有几个原因。一个原因是测试条件显得多余。当你测试 Qty 是否比 1000 大时,你就无需测试它是否比 100 大了,更不用说 10,考虑到这一点,重新写 代码:这个 Pascal 程序把 if 嵌套转化为 if-then-else 的形式: if( Qty > 1000) then Discount := 0.10 else if( Qty > 100) then Discount >= 0. 05 else if( Qty >10) then Discount := 0.025 else Discount := 0; 这个程序就比上一个好多了,因为测试条件中比较的数值是速增的。如果数值不是那么有 规律地增长,你可替换嵌套的 if 语句如下: 这个 Pascal 程序把 if 嵌套转化为 if-then-else,在这里数值是无规律的: if(Qty > 1000) then Discount := 0.10 else if( Qty > 100 and Qty <= 1000) then Discount := 0.05 else if( Qty > 10 and Qty <= 100) then Discount := 0.025 else if( Qty <= 10) Discount := 0 这个程序与前一程序的主要区别在于 else-if 的测试表达式不依赖于前一测试结果,这 第十七章 常见的控制问题 261 段代码也可不要 else 语句,且测试条件可按任意顺序放置。代码可包含 4 个 if 语句而无 else。 用 else 语句的原因是可避免不必要的重复测试。 把 if 嵌套改成 case 语句。你可以把某些类型的 if 语句测试条件(恃别是用到整数)用 case 语句来代,而不用 if-else 来代替。但这种技巧并非所有语言都能用。若能用,这种技巧 的效果很好。下面这个 Pascal 程序用了这种技巧: 这个 Pascal 程序把 if 嵌套转换成 case 语句: case Qty of 0..10: Discount := 0. 0; 11..100: Discount := 0. 025; 101..1000: Discount := 0. 05; else Discount := 0. 10; end;{case} 这个例子读起来很轻松,把它与前几页的多次缩排程序例子比较,显得相当清楚。 把深层嵌套的代码写成一个子程序。如果深层嵌套出现在一个循环中,你可把循环的内部 写成一个子程序。这种技巧当嵌套是条件控制和重复时显得特别有效。把 if-then-else 分支留 在主程序里以显示清楚决策分支,而把各分支里的代码写成一个子程序。下面这个程序就需用 上述方法改造: 这个 C 程序的嵌套代码需分别写成子程序: while( ! feof( TransFile )) { /* read transaction record */ ReadTransRec(TransFile,TransRec); /* process transaction depending on type of transaction */ if( TransRec.TransType = = Deposit ) { /* process a deposit */ if(TransRec.AccountType = = Checking) { if( TransRec.AcctSubType == Business) MakeBusinessCheckDep( TransRec.AcctNum , TransRec.Amount ); else If(TransRec.AcctSubType = = personal ) MakePersonalCheckDep( TransRec.AccNum,TransRec.Amount ); else if(TransRec. AcctSubType == School ) MakeSchoolCheckDep( TransRec.AcctNum,TransRec.Amount ); } else if (TransRec.AccountType = = Savings ) 第十七章 常见的控制问题 262 MakeSavingsDep(TransRec.AcctNum,TransRec.Amount ); else if(TransRec.AccountType = = DebitCard ) MakeDebitCardDep(TransRec.AcctNum , TransRec.Amount ); else if(TransRec.AccountType==MoneyMarket) MakeMoneyMarketDep(TransRec.AcctNum,TransRec.Amount ); Else if(TransRec.AccountType==CD) MakeCDDep(TransRec.AcctNum ,TransRec.Amount); } else if (TransRec.TransType==Withdrawal) { /* process a withdrawal */ if( TransRec.AccountType == Checking) MakeCheckingWithdrawal( TransRec.AcctNum ,TransRec.Amount ); else if(TransRec.AccountType = = Savings ) MakeSavingsWithdrawal(TransRec.AcctNum , TransRec.Amount ); Else if (TransRec.AccountType = = DebitCard ) MakeDebitCardWithdrawal( TransRec.AccyNum, TransRec.Amount); } else if( TransRec.TransType = = Transfer) { MakeFundsTransfer(TransRec.SrcAcctType,TransRec.TgAcctType, TransRec.AcctNum,TransReC.Amount); } else { /* process unknown kind of transaction */ LogTransError(”Unknown Transaction Type”,TransRec); } } 虽然很复杂,但这个程序还不是你见到的最次的一个。它的嵌套仅有四层,并且写得很清 楚,有编排形式,功能分解得也很完整,特别是对 TransRec。的处理。尽管有这些好处,但还 是应该把内层 if 的内容写成子程序。 这个 C 程序较好,把嵌套内的内容写成子程序: While(!feof( TransFile) ) { /* read transaction record */ ReadTransRec(TransFile,TransRec); /* process transaction depending on type of transaction */ 第十七章 常见的控制问题 263 If( TransRec.TransType== Deposit) { ProcessDeposit(TransRec.AccountType, TransRec.AcctsubType); TransRec.AcctNum,TransRec.Amount); } else if ( TransRec.TransType==Withdrawal) { ProcessWithdrawal( TransRec.AccountType,TransRec.AcctNum, TransRec.Amount ); } else if( TransRec TransType== Transfer) { MakeFundsTransfer( TransRec.SrcAcctType, TransRec.TgtAcctType, TransRec.AcctNum,TransRec.Amount); } else ( /* process unknown transaction type */ LogTransError(”Unknown Transaction Type”,TransRec); } 新子程序部分的代码只是简单地从原程序中提取出来并形成子程序(这里没有写出来)。新 的程序有几个优点。第一,仅有两层嵌套,使得结构显得简单、易懂;第二,你可在显示器的 一屏上阅读、修改、调试这个较短的 while 循环,不会因为需几幕显示,几页打印而限制你的 眼界;第三,把 processDeposit()和 processWithdrawal()功能写成子程序具有了易于修 改的一切优点;第四,现在可容易看出代码能写成 switch-case 语句形式,那样就显得更易读 了。如下例子:这个 C 程序较好,嵌套内的内容写成子程序且用了 switch-case 语句: while(!feof( TransFile )) { /* read transaction record */ ReadTransRec( TransFile ,TransRec ); /* process transaction depending on type of transaction */ switch(TransRec.TransType) { case( Deposit ); ProcessDeposit(TransRec.AccountType,TransRec AcctSubType, TransRec.AcctNum , TransRec.Amount ); 第十七章 常见的控制问题 264 break; case(Withdrawal ); ProcessWithdrawal( TransRec.AccountType, TransRec.AcctNum, TransRec.Amount); break; case( Transfer ); MakeFundsTransfer(TransRec SrcAcctType,TransRec.TgtAcctType, TransRec. AcctNum,TransRec.Amount); break; default: /* process unknown transaction type */ LogTransError(”Unknown Transaction Type”,TransRec); break; } } 重新设计深层嵌套代码。一般说来,复杂代码表明还没有完全理解你的程序,应使其更简 单些。深层嵌套提示需把某些部分写成一个子程序或需重新设计复杂的那部分程序。这虽然并 不意味着就需要去修改程序,但若无充分理由,还是要修改。 17.5 结构化编程的作用 结构化编程是什么意思?结构化编程的核心基于这样一种简单思想,即程序总是单入单出 的结构,即程序只能从一个地方开始且也只能从一个地方退出的代码块,没有其它的进口与出 口。 17.5.l 结构化编程的好处 为何本书还要在整整一章去讨论一个 20 年的老话题——结构化编程呢?每个人都用它吗? 否。并非每个人都用结构化编程,且许多人认为他们不用。Gerald Weingerg 调查了大约 100 家软件公司并访问了数千名程序员。他报告说,大约仅有 5%的代码是完全结构化的;20% 的程序结构化程度很高(这比 1986 年是一个提高);50%的程序显示了用结构化编程的努力, 但并不成功,而还有 25%的程序则显示丝毫没有被过去 20 年的结构化思想影响。 有些程序员不相信结构化编程的作用。他们错误地认为结构化编程是多此一举与浪费时间, 且编程效率低,打击编程员的积极性和降低其编程效率,有些报告证实了有这种对结构化编程 抵制的行为。 尽管有这些否定意见,结构化编程的有效性是证据确凿的,观察实验数据发现结构化编码 使总编程效率增加,再考虑到限制条件和复杂性,产量增量显得更大,从 200%~600%不等。 第十七章 常见的控制问题 265 通用汽车公司(General Motors)一项研究表明结构化技巧可节省时间和培训近六个月(Elsoff 1977)。 除了提高产量,结构化编程还可提高可读性。在一项试验中,36 个专业程序员要理解结构 化和非结构化的 Fortran 程序,结果显示,对结构化程序的理解得分为 56 分(100 分制),而非 结构化程序的则仅有 42 分。这表明更多结构化编程比非结构化编程要提高 33 个百分点 (Sheppardetal 1978)。 结构化编程的执行进程是一个有序的、有规律的过程,而不是不可预测地到处转移。程序 可以从上往下读下来,执行大抵也按这个顺序。源程序无规律性会在机器中产生一些无意义的 不好读的程序执行路径。而低可读性则意味着不好理解,程序质量差。 17.5.2 结构化编程设计的三个组成部分 “结构化”这个词是这许多年来使用频率极高的调,被应用到软件开发的各个领域,包括 结构化分析、结构化设计、结构化实现。不同的结构化方法并没有统一起来,它们都是同时出 现的,结构化是它们好处的标志。 许多人错误地理解结构化编程,把这个词在几个方面被乱用。首先,结构化编程不是缩排 编写的方法,这种方法对程序的结构毫无益处;第二,结构化编程不是自上而下的设计,这只 是编程的一些细节问题;第三,结构化编程不是一种节约时间的技巧。但以上几点在面向对象 程序设计时是正确的。 下面几节讨论构成结构化编程的三个方面。 顺序编程 一个顺序程序指一组按顺序执行的语句。典型的顺序语句包括赋值和子程序调用。如下两 例: 这个 Pascal 程序包含顺序代码: {a sequence of assignment statements} a := 1; b := 2; c := 3; {a sequence of calls to routines} Writeln(a); Writeln(b); Writeln(c); 选择 选择是一种控制结构。这种结构使语句有选择地被执行。If-then-else 就是一个普通的 例子。或者 If-then 语句,或者 else 语句被执行,但不会两者都不执行,总有一个被选择执 行。 case 语句是另一种选择控制的例子。Pascal 和 Ada 中的 case 语句及 C 中的 switch 语句 第十七章 常见的控制问题 266 都属 case 类的例子。在每一种语句中,都有几种情况被选择去执行。一般说来 case 语句和 if 语句在概念上是相似的。如果一种语言不支持 case 语句,可用 if 去模仿它。下有两例: 有选择句子的 Pascal 程序: { selection in an if statement } if( a = 0) then { do something } else {do something else} {selection in a case statement} case( Shape ) of Square: DrawSquare; Circle: DrawCircle; Pentagon: DrawPentagon; DoubleHelix: DrawDoubleHelix; end; 重复 重复也是一种控制结构,它使一组语句被多次执行。重复常指“loop”(循环),常见的几 种重复有 basic 中的 FOR-NEXT、Fortran 中的 Do、Pascal 和 C 中的 while 和 for 等语句。如 果不用 goto,那么重复将是控制结构的技巧。下面是用 Ada 编的重复例子: Ada 编的重复的例子: 一 example of iteration using a for loop for INDEX in FIRST..LAST loop DO_SOMETHING(INDEX); end loop --example of iteration using a while loop INDEX := FIRST; while( INDEX <= LAST ) loop DO_SOMETHING( INDEX ); INDEX := INDEX + l; End loop; 一 example of iteration using a loop-with exit loop INDEX:=FIRST; 第十七章 常见的控制问题 267 loop exit when INDEX > LAST; DO_SOMETHING ( INDEX ); INDEX := INDEX + 1; end loop; 17.6 用 goto 模拟结构化结构 汇编、Fortran、一般 Basic 或其它有些语言不支持结构化控制结构,那你可能要问:我怎 么写结构化程序呢?正如 goto 的批评者所指出,你可以用三种结构化结构中的一种或几种来取 代每一控制结构,也可用一个或几个 goto 来取代三种结构化结构。如果你的语言没有提供其它 控制程序流的方法,那么避免用 goto 的结论就没什么意义了。这种情况下,你可用 goto 去模 拟三种结构化编程结构,只是 goto 要尽量少用。 17.6.1 模拟 if-then-else 语句 如果你想用 goto 来模拟 if-then-else 语句,首先用注释行的形式写出测试条件和 if- then-else 语句,如下例所示,这里用 Fortran 写,但你也可很容易地采用汇编、Ihac 或其它 语言写: 用注释行写出 if-then-e1se 的测试条件的程序; C if (A < B ) then C else C endif 其次,在注释行间写代码。作为一般的方法,为了转向分支,你对注释行中的条件取反, 对应于重写的条件是真——即原条件为假时转向分支。为了对原条件取反,把条件两边用括号 括上,并在其前面加上.NOT.运算,用一个 goto 语句从 if 部分转到 else 部分去,下面是程 序: 用 Fortran 填充了 if-then-else 条件的程序: C if( A< B= then IF(.NOT.(A. LT. B))GOTO 1100 CODE TO PERFORM IF THE ORIGINAL CONDITION IN COMMENTS IS TRUE … GOTO 1200 C else 1100 CONTINUE CODE TO PERFORM IF THE ORIGINAL CONDITION IN COMMENTS IS FALSE … 1200 CONTINUE C endif 注意到注释行中的 if、else、endif 语句往后退了几格与正式程序对齐,以免代码的逻辑 结构受到注释行的影响。 下面是相应的 Basic 程序段: 第十七章 常见的控制问题 268 用 goto 模拟 if-then-else。测试条件的 Basic 程序: 1000 ' if ( A0.5) do 1000 IF (.NOT. ( I .LT. MAXI .AND.X .GT. 0.5 ) ) GOTO 1010 C DO SOMETHING C … GOTO 1000 1010 CONTINUE C end while 这里要注意的地方跟上面讨论 case 语句一样,可以参考前述,注意的是循环初始化是明显 给出的,作为提醒,和前面的 for 的条件一样,这里 While 的条件在被取代后要取反。 17.6.4 模拟控制结构概述 用 goto 来模拟结构化控制结构可帮你用某种语言编程。正如,DavidGriex 指出,选择何 种语言并不重要,你要确定的是你该怎样编程。理解把程序编成某种程序语言的程序与用某种 语言编程之间的区别是本书的关键。许多编程原则并不依赖于某种语言,而仅给你提供了一种 方法。 如果所用语言不支持结构化结构或易于产生其它问题,努力弥补这种缺陷,形成一套你自 已的编程风格、标准、库子程序或其它观点。 通过模拟结构化编程的结构,那些汇编、一般 Basic、Fortran 等语言对结构化控制结构的 限制也就不复存在了。最后你能把程序从一种语言转化成另一种你碰巧要用的语言。 17.7 控制结构和复杂性 注意控制结构的一个原因是,它们对于克服程序的复杂性有很大贡献。不用控制结构,会 增加程序的复杂性。用得好则能降低复杂性。 标量一个程序复杂性的方法是,若要理解程序你得一次连续在脑中记住多少目标程序语句, 结构的处理是编程中最困难的方面,也是为什么需要特别注意结构性的原因,这也是程序在处 理“快速中断”(quick interruption)时手忙脚乱的原因,这里快速中断相当于要求一个杂技 员手上拿着东西的同时要不断向空中抛三个球做杂耍的情形差不多。 程序的复杂性很大程度上决定了要理解一个程序要花多大努力。TomMcCabe 在一本书中认 为一个程序的复杂性就决定于它的控制流。别的研究人员在此之外还确认了别的影响复杂性的 因素,但都承认,控制流若不是最大的,起码也是影响复杂性的最大原因。 17.7.1 程序复杂性的重要性 计算机科学起码在二十年前就注意到了程序复杂性的重要了。二十年前,Edager Dijkstra 就意识到复杂性的危险,他说:“一个聪明的程序员总是清楚地知道自己的脑力容量有限,因此 第十七章 常见的控制问题 270 他得十分小心谨慎地完成编程任务”(1972)。这并不意味着为了处理很复杂的问题你得增大你 的脑力,而是说你得想办法尽可能降低复杂性。 控制流的复杂性很重要,因为它和低的可读性和频繁的出错紧密联系在一起(McCabe 1976, Shen at al 1985).William T.ward 在 Hewlett-Packard 公司用 McCabe 的复杂性度量标准来 研究软件的可读性问题时,得到一个很有意义的结果(1989)。把 McCabe 的复杂性度量原理用 于确定一个 77,000 行程序的出错范围。这个程序的最后错误率为每一千行 0.31 个错,而另一 个 125,000 行程序最后出错率为每一千行 0.02 个错。ward 发现,由于这两个程序的复杂性较 低,因此这两个程序的出错数比 Hewlett-Packard 的其它程序都低。 17.7.2 减少复杂性的常用方法 下面两种方法可以帮助降低程序复杂性。首先,你可以做一些动脑筋练习来提高在脑中打 底稿的能力。但大多数程序都很大,而人同时考虑的问题一般都不能超过 5~9 个,因此靠提高 脑子的容量来帮助降低复杂性能力有限,第二,要降低程序的复杂性就要求你彻底理解你所要 解决的问题。 怎样度量复杂性 你可能要问怎样从直觉上判断哪些因素使程序变得复杂了还是简单了呢?研究人员已经把 他们的直觉归纳出来并形成了几条度量复杂性的方法,或许最有影响的数字技巧是 Tom McCabe 的方法,这种方法通过计算程序的“决定点”(decision point)的数目来度量复杂性,见表 17 -2。 表 17-2 计算程序决定点的技巧 --------------------------------------------------------------------------------- 1.从 1 开始一直往下通过程序。 2.遇到下列关键词或其同类的词加 1。 if while repeat for and or 3.case 语句中每一种情况都加 1,如果 case 语句没有缺省情况再加 1 如下例: if (( ( Status = Success ) and Done ) or (not Done and ( NumLines >= MaxLines)) ) then… 在这个程序中,从 1 算 起 ,遇 到“ if”得 2,遇 到“ and”得 3,遇 到“ or”得 4,又遇到一个“and” 得 5,这样程序总共含有 5 个决定点。 有了复杂性度量数日该怎样判断程序的复杂性 当你已经算出决定点的数目时,你可用算得的数目分析程序的复杂性。如果数目是: 0~5 程序可能很好 6~10 得想办法简化程序 10 以上 得把部分代码写成子程序并在原程序调用 把部分程序写成子程序并不能减少整个程序的复杂性,它仅仅是把决定点转移到别的地方, 但它却降低了一次涉及到的复杂性。既然你的目的是降低一次要在你脑中考虑的问题数目,因 此编成子程序降低复杂性的方法是有帮助的。 第十七章 常见的控制问题 271 决定点的最大数目为 10 并不是一个绝对的极限,而仅用这个数目作为一种提醒标志,来告 诉你程序需重新设计一下,不要死套这个规则,比如一个 case 语句有许多种情况,因而决定点 数目会比 10 大得多,但你却不能把它分解成子程序。这种 case 语句在事件驱动程序中用得很 多,如 Microsoft Windows 和 Apple Macintosh 中的许多程序。在这些程序中一个长的 Case 语句可能是降低程序复杂性的最好方法。 17.7.3 度量程序复杂性的其它方法 McCabe 的度量程序复杂性的方法并不是唯一的方法,但它却是用得最多的方法,特别当考 虑控制流问题时。其它的方法包括用到数据的次数、控制结构中嵌套层次、代码的行数、变量 连续出现的程序行行数及输入输出点的数目。另有一些研究人员已经开发了以上各方法的综合 方法。 17.7.4 检查表 控制结构方面 · 表达式用 True 和 False 而非 1 和 0? · 布尔型表达式的值是否隐含地与 False 比较? · 是否通过定义中间布尔型变量和布尔型函数及用决策表的方法来简化表达式? · 布尔型表达式是用肯定形式写出来的吗? · 在 C 中,数值、字符,指针是显式与 0 比较的吗? · begin 和 end 能保持平衡吗? · 为了使程序看起清楚,需要的地方用 begin 和 end 对标明了吗? · 空语句看起来清楚吗? · 通过诸如重新组合测试条件、转化为 if-then-else 或 case 语句或把嵌套内代码写成子 程序的方法来简化嵌套语句了吗? · 如果程序的决定点数超过 10,有什么正常理由不重新设计它吗? 17.8 小 结 · 使布尔型表达式简单可读性高对代码的质量很有好处。 · 深层嵌套使程序难懂,不过可用相对简单方法避免这样做。 · 结构化编程是一个简化程序的思想,用顺序编程、选择或循环中的一种或几种方法的组 合可编出任何程序。 · 作这种简化程序的思想可提高程序的产量和质量。 · 如果所用语言不支持结构化结构,你能模仿它们。你应该把程序编成某种语言的程序而 不是用某种语言编程的。 · 降低复杂性是编写高质量的代码的关键。 第十八章 布局和风格 272 第十八章 布局和风格 目录 18.1 基本原则 18.2 布局技巧 18.3 布局风格 18.4 控制结构布局 18.5 单条语句布局 18.6 注释布局 18.7 子程序布局 18.8 文件、模块和程序布局 18.9 小结 相关章节 文档代码:见第 19 章 从这一章开始转向计算机编程的美学问题——源程序代码的规划布局问题,组织得很好的 代码无论从直观上还是从内心里都产生一种愉悦的感觉,这恐怕是非程序员很少能达到的境界。 使那些对自己工作很有自豪感的程序员能从他们代码的优美结构得到极大的艺术满足。 这一章所讨论的技巧并不影响速度、内存的使用及其它程序外观方面的问题,所影响的仅 仅是怎样很容易地理解代码、检查代码、日后很容易地修改代码等。它也影响到别人如何很轻 松地去读、去理解、当你不在时去修改代码。 这一章尽是些人们在谈到要注意细节时涉及到的小细节问题。在整个编程过程中,注意这 些细节问题对程序最后质量和最后维护性都产生很大影响。对编码过程来说这些细节是必不可 少,以致到最后无法改变。如果你是和一个小组一起工作,在编程前要和全组的人一起看看本 章的内容并形成一个全组统一的风格。 你可能不太同意这一章的所有问题,但与其说是要你同意本章的观点还不如说是要让你考 虑涉及到格式化风格的许多问题,如果你有高血压,请翻过本章,这里的观点都是要引起争论 的。 18.1 基本原则 本节介绍布局原理,其它各节介绍实例。 18.1.1 布局的几个例子 考虑表 18-1 列出的程序。 第十八章 布局和风格 273 表 18-1 Pascal 布局的例子 procedure InsertionSort ( Var Data : SortArray_t ; FirstElmt : Integer LastElmt : Integer ) ; { use the insertion sort technique to sort the “Data” array in ascending order. This routine assumes that Data [ FirstElmt ] is not the FirstElmt element in Data and that Data [ FirstElmt - 1 ] can be accessed. }Const SortMin = ’’ ; Var SortBoundary : Integer ; { upper end of sorted range } InsertPos: Integer ; {position to insert element } InsertVal : SortElmt_t ; {value to insert} LowerBoundary : SortElmt_t ; {first value below range to sort} begin { Replace element at lower boundary with an element guaranteed to be first in a sorted list } LowerBoundary : = Data[ FirstElmt_t ] ; Data [FirstElmt-1] : = SortMin ; {The elements in positions FirstElmt through SortBoundary-1 are always sorted. In each pass through the loop, SortBoundary is increased, and the element at the position of new SortBoundary Probably isn’t in its sorted place in the array,so it’s Inserted into the proper place somewhere between FirstElmt and SortBoundary.}for SortBoundary : = FirstElmt + 1 to stElmt do begin InsertVal : = Data[SortBoundary] ; InsertPos : = SortBoundary ;while InsertVal <= Data[ InsertPos – 1 ] do begin Data[InsertPos] : = Data[ InsertPos – 1 ] ; InsertPos : = InsertPos – 1 ; end; Data [ InsertPos ] : = InsertVal ;end;{Replace orginal lower-boundary element }Data[ FirstElmt – 1 ] : = LowBoundary ; End; { InsertionSort} 这个程序从语法上来说是正确的。它用注释说明得很清楚,而且变量名也有含义、逻辑思路 也很清楚。如果不信,读完这段程序看看哪出错了。这段程序所缺省的是一个好的布局,这是 一个极端的例子。若用好坏标准数轴来表示的话,这个例子的布局是要处于负无穷大方向的。 表 18-2 的例子稍好些: 表 18-2 Pascal 程序布局的例子 procedure InsertionSort( Var Data : SortArray_t ; FirstElmt:Integer ; LastElmt : Integer ) ; { use the insertion sort technique to sort the “Data” array in ascending order. This routine assumes that Data[ FirstElmt ] is not the first element in Data and that Data[ FirstElmt – 1 ] can be accessed. } Const SortMin = ’’ ; Var SortBoundary : Integer ; { upper end of sorted range } InsertPos : Integer ; {position to insert element } InsertVal : SortElmt_t ; {value to insert} LowerBoundary :SortElmt_t ; {first value below range to sort} begin { Replace element at lower boundary with an element guaranteed to be first in a sorted list } 第十八章 布局和风格 274 LowerBoundary : = Data[ FirstElmt_t ] ; Data[ FirstElmt –1 ] : = SortMin ; {The elements in positions FirstElmt through SortBoundary-1 are always sorted. In each pass through the loop, SortBoundary is increased, and the element at the position of the new SortBoundary Probably isn’t in its sorted place in the array, so it’s inserted into the proper place somewhere between FirstElmt and SortBoundary.} for SortBoundary : = FirstElmt +1 to LastElmt to do begin InsertVal : = Data[ SortBoundary ]; InsertPos : = SortBoundary; while InsertVal < Data[ InsertPos - 1 ] do begin Data[ InsertPos ] := Data[ InsertPos-1 ] ; InsertPos := InsertPos –1 ; end; Data[ InsertPos ] := InsertVal ; end; { Replace orginal lower-boundary element } Data[ FirstElmt-1 ] : = LowBoundary ; end; { InsertionSort } 这段程序与表 18-1 的一样。虽然大多数人要说这段代码的布局要比前一段的要好得多,但 它还是显得不太好读。这段代码的布局还是显得拥挤而且无法看出程序的逻辑结构。它处于好 坏标准数轴的 0 位置。第一个例子是一个分行的过程,而第二个则什么也没有。我见过一些程 序有上千行那么长,其结构布局跟这个例子一样差劲,既无文件说明,也无好的的变量名,读 起来跟这个例子一样难受。第二个例子是为计算机格式化的,而无丝毫迹象表明,编程者想让 人读这一段程序。表 18-3 则是一个改进: 表 18-3 Pascal 程序布局例子 procedure InsertionSort ( Var Data : SortArray_t; FirstElmt: Integer; LastElmt : Integer ); { use the insertion sort technique to sort the “Data” array in ascending order. This routine assumes that Data[FirstElmt] is not the FirstElmt element in Data and that Data[ FirstElmt-1 ] can be accessed. } Const SortMin = ’ ’; Var 第十八章 布局和风格 275 SortBoundary : Integer; { upper end of sorted range } InsertPos : Integer; {positionto insert element } InsertVal : SortElmt_t; {value to insert} LowerBoundary : SortElmt_t; {first value below range to sort} begin { Replace element at lower boundary with an element guaranteed to be first in a sorted list } LowerBoundary := Data[FirstElmt_t]; Data[FirstElmt-1] := SortMin; { The elements in positions FirstElmt through SortBoundary-1 are always sorted. In each pass through the loop, SortBoundary is increased, and the element at the position of the new SortBoundary Probably isn’t in its sorted place in the array, so it’s Inserted into the proper place somewhere between FirstElmt and SortBoundary. } for SortBoundary := FirstElmt + 1 to LastElmt do begin InsertVal := Data[ SortBoundary ]; InsertPos := SortBoundary; while InsertVal< Data[InsertPos-1] do begin Data[InsertPos] := Data[ InsertPos-1 ] ; InsertPos := InsertPos-1; end; Data[ InsertPos ] := InsertVal; end; { Replace orginal lower-boundaryelement } Data[ FirstElmt-1 ] := LowBoundary; end; { InsertionSort } 这个程序的布局在好坏标准数轴的绝对正方向上。这个程序的布局完全按本章讲的原则来 设计。这个程序易读得多,而注释和好的变量名都显而易见,变量名与第一个程序一样好,但 第一个程序的布局太差,显示不出这种好处来。 这段程序与前两个的唯一差别只在有空格——其实代码和注释都一模一样。加空格只是有 利于人的阅读,计算机可认为这三段程序是一样的。你和计算机对程序的感觉不一样是当然的 事情。 另一种格式化的例子见图 18-l。这种方法是基于源代码格式的,由 Ronald M.Baecker 和 Aaron Marcus 创建。这种方法中,除了用空格外,这种方法还用到了阴影、不同字体及别的排版 技巧,Baecker 和 Marcus 创造了一种能按类似图 18-1 所示的方法打印出通常源代码的工具。 虽然这种工具还没有商业化,但由于它支持源代码的布局设计,因而不出几年就会普及。 第十八章 布局和风格 276 用排序技巧把“Data”数组按递增的顺序排序。程序中的 data 数组的第一个元素并不是 Data[FirstElmt]而是 Data[FirstElmt-1]。 图 18-l 用排版技巧来格式源代码 18.1.2 格式化的基本原理 格式化的基本原理是用直观的布局显示程序的逻辑结构。 第十八章 布局和风格 277 使程序看起来显得漂亮,目的是为显示程序的结构。如果一种技巧使结构看起来更好而另 一种技巧也是这样,那就选两种技巧中最好的一个。本章提供了许多格式形式很好但扰乱了逻 辑结构的例子。实际上优化考虑结构并不会使程序难看——除非代码的逻辑结构本身就很别扭。 那种使好代码显得更好、坏代码显得更差的技巧,要比使所有代码都显得好看的技巧更有用。 18.1.3 人和计算机对程序的解释 对程序的结构来说,布局是一个有用的线索,虽然计算机并不理睬 begin 和 end 之类的词, 但人却易于从这些看得见的标志中得到线索,考虑表 18-4 中的代码段,其中用缩排的方法使人 看起觉得每次循环时三条语句都被执行了一次。 如果代码不用括号,那么编译程序执行第一条语句 MAX_ELMTS 次,而第二条、第三条语句 仅执行一次。这种缩排的方式使你我都很清楚地觉得编程员是希望这三条语句一起执行,而应 该放在一个大括号中的,但编译程序却并不这么看。 表 18-4 这个 C 语言程序的布局对人和计算机来说理解是不一样的。 表 18-4 /* swap left and right elements for while array */ for (i=0; I statement1 ; statement2 ; … when GreenColor => statement1 ; statsment2 ; … when Others => statement1 ; statement2 ; … end case; Ada 语言中一个控制结构总有一个起始语句——if-then,while-loop,case-or 等,并且 都有一个对应的结束语句。控制结构中间的缩排却是公认的,但选用别的关键词却有些限制。 表 18-9 抽象地表示了这种格式化形式: 表 18-9 纯块结构布局形式的抽象例子 A ██████████ B ██████ C ███████ D ███ 上例中,A 语句是控制结构的开始,而 D 语句则是结束。这两语句间的其它语句对齐、缩 排。有关格式化控制结构的争论,部分起源于有些语言根本不需块结构。有时 if-then 语句之 后仅限一条语句而不是通常所说的语句块,这时你却得加 begin-end 对或开括号“{”和闭括 号“}”来制造出一个完整块而不是直接在控制结构后跟一条语句了事。程序中的 begin 和 end 不成双,这就产生了在哪去放置 begin 和 end 的问题。通常缩排的问题仅仅是因为你得补偿语 言在设计结构上的不足。下面讨论不同的补偿方法。 18.3.2 行尾布局 如果你所用的不是 Ada 语言,你就不能用纯块结构布局。你得真正用 begin 和 end 关键词 来实现块结构。其中一种方法是“行尾布局”,指一大组语句几乎要退格到行尾的布局方法。这 种行尾缩排方法使下面的一组语句与开始这个控制结构的关键词对齐,而下面的参数行与第一 个参数行对齐排下来。表 18-10 是一个抽象的例子: 第十八章 布局和风格 282 表 18-10 行尾布局形式的抽象例子 A ██████████ B ████ C ██████ D ██ 这个例子中,A 语句是控制结构的开始,D 则是结束,B、C、D 语句与 A 语句的块结构关键 词对齐。B、C、D 统一缩排说明它们是一组的,表 18-11 是一个用这种格式的 Pascal 例子。 表 18-11 行尾布局 Pascal 例子 while PixelColor = RedColor do begin statement1 ; statement2 ; … end ; 这个例子中,begin 放在第一行末尾但不作为相应的关键词,有些人愿意把 begin 作为关 键词,但在这两点间选一个作关键词仅仅是这种风格的一个细节问题。行尾布局风格有几种可 接受的变样,表 18-12 是一个例子: 表 18-12 这种形式的 Pascal 程序虽少见,但这种行尾布局形式也是可行的 if( SoldCount > 1000 )then begin Markdown := 0.10 ; Profit := 0.05 ; end else Markdown := 0.05 ; 这个例子中程序块与 then 后的 begin 对齐,但在最后一行 else 与 then 关键词对齐。这使 得逻辑结构很清楚。 如果你认为前面的 case 语句不怎么样,你可能想要打破这种形式。如果条件表达式变得复 杂了,那么这种布局形式对于理解逻辑结构是无用的或说是有误的。表 18-13 的例子给出了用 复杂控制表达式打破上面例子的布局形式: 表 18-13 这个 Pascal 程序更典型,其中的行尾布局已被破坏 if ( SoldCount > 10 and PrevMonthSales > 10 ) then if ( SoldCount > 100 and PrevMonthSales > 10 ) then if ( SoldCount > 1000 ) then begin Markdown := 0.10; Profit := 0.05 end else Markdown := 0.05 else Markdown := 0.025 else Markdown := 0.0 ; 第十八章 布局和风格 283 这个例子末尾的 else 语句怎样?它们也都与其相应的关键词对齐了,但却不能说这种编 排形式使逻辑结构更清楚了。如修改第一行使其长度变化,那么按行尾布局的要求所有相应语 句的缩排格数都要跟着变,这就在修改程序时产生别的布局形式不会产生的问题。 简言之,不用行尾布局是因为其不精确。它很难有连续性和维修性。本章中你到处可能见 到行尾布局所产生的问题。 18.3.3 模拟纯块结构 若使用的语言不支持纯块结构,那么替代行尾布局的一个较好的选择是,使用语言去模仿 Ada 的纯块结构,表 18-14 是你要模仿的纯块结构抽象表示: 表 18-14 纯块结构布局形式的抽象例子: A ██████████ B ████ C ██████ D ███ 在这种布局形式中,A 句开始块结构,而 D 语句则结束块结构,这表明 begin 需在 A 语句 的结尾而 end 在 D 语句中,要模仿纯块结构,其抽象过程如表 18-15 所示: 表 18-15 模仿纯块结构布局的抽象例子 A ██████████ B █████████ C ██████████ D ████ 表 18-16、18-17、18-18 是以上类型的具体的 Pascal 例子: 表 18-16 模仿纯 if 块结构的 Pascal 例子 If PixelColor = RedColor then begin statement1 ; statement2 ; … end; 表 18-17 模仿纯 While 块结构的 Pascal 例子 while PixelColor = RedColor do begin statement1 ; statement2 ; … end; 表 18-18 模仿纯 case 块结构的 Pascal 例子 case PixelColor of RedCelor : begin statement1; statement2; … end; GreenColor : begin 第十八章 布局和风格 284 statement1; statement2; … end else begin statement1; statement2; … end end; 这种控制语句内句子对齐的形式显得很好,你能连续地应用这种结构形式,它的维护性也 很好。这种形式符合格式化的基本原理且能显示代码的逻辑结构。因此这种形式充分可行。要 注意的是这种形式在 Pascal 中不常用,但在 C 中用得很多。 18.3.4 用 begin 和 end 作块的边界 取代纯块结构的一个替换方法是使用 begin 和 end 作为块的边界而成对出现。用这种方法 时,begin 和 end 作为控制语句下的一个语句而非作为控制语句的一个部分。 模仿纯块结构的抽象结构如表 18-19。 表 18-19 模仿纯块结构布局形式的抽象例子 A ████████████ B ███████ C ████████ D ████ 在把 begin-end 作块边界的方法中,我们是把 begin 和 end 用为块结构本身的一部分而不 是作为控制语句的一部分。你得把 begin 置于块的开始(而非放在控制语句的末尾),而把 end 放在块的结尾(而非作为控制结构的结束符)。作为一种抽象的表示方法,可把这种结构如 18-20 表示出来: 表 18-20 用 begin 和 end 作为块边界的抽象例子 A ████████████ ██████████ B ██████████ C ██████████ █████ 表 18-21、18-22、18-23 分别给出这种形式的具体 Pascal 例子。 表 18-21 在 if 块中用 begin 和 end 作块边界的 Pascal 例子 if PixelColor = RedColor then begin statement1 ; statement2 ; … end; 第十八章 布局和风格 285 表 18-22 在 while 块中用 begin 和 end 作块边界的 Pascal 例子 while PixelColor= RedColor do begin statement1; statement2; … end; 表 18-23 在 case 块中用 begin 和 end 作块边界的 Pascal 例子 case PixelColor of RedColor, begin statement1; statement2; end; GreenColor: begin statement1; statement2; end else begin statement1; statement2; end end; 这种对齐块中语句的方法显得很好,它满足了格式化的基本原理又充分体现了逻辑结构。 在所有情形下都能连续使用且维护性很好。 18.3.5 哪种形式是好 很容易回答哪种形式最次。行尾布局是最次的,这种形式无连续性且难维修。 如果用 Ada 编程,用纯块结构的缩排方法。 如果用 C 或 Pascal 编程,选择使用模仿纯块方法或 begin-end 作块边界的方法。这两种方 法基本上没有什么区别,选择你所喜欢的。 以上各种形式都不是绝对的,都需要考虑各种偶然的因素,并采取综合兼顾的方法。你可能觉 得这种或那种更美观。本书都用到了多种程序方法,通过看例子你可领略这些风格的异同。一 旦选定某种形式,你应连续地应用去发现好布局的优点。 18.4 控制结构布局 对于一些程序来讲,布局基本上是一个美学问题,但是控制结构的布局却影响到程序的可读性 第十八章 布局和风格 286 和理解性,因而是个需要考虑的问题。 18.4.1 关于格式化控制结构块的几点好意见 涉及到控制结构块的布局时需注意到几点细节,以下提供一些指导。 begin-end 对应当退格。在表 18-24 中 begin-end 对与控制结构语句对齐了,但 begin-end 对内的语句相对 begin 退了两格。 表 18-24 begin-end 对内语句缩排的 Pascal 例子 for i := 1 to Maxlines do begin 与 for 对齐 begin Readline(i); 这两个语句缩进两格 PrecessLine(i); end —— end 与 for 对齐 这种方法看起来很好,但它却违反了格式化基本原理。它并没有显示出代码的逻辑结构。 这种方法中,begin 和 end 好像既不是控制结构的一部分,也不属于它们之间语句组的一部分。 表 18-25 是这种方法的示意图。 表 18-25 引起错误导向的缩排方法的抽象例子 A ████████████ B ██████ C ██████ D ████████ E ███ 这个例子中,语句 B 属于 A 吗?它看起来不像是 A 语句的一部分。如果你已用了这种方 法,把它改成前面讲过的两种布局形式,这样你的格式化会更清楚些。 用了 begin-end 对的代码不要进行两次缩排。反对 begin-end 对无缩排的对立面,反对 begin-end 对中再次缩排,这种方法如 18-26 所示,begin 和 end 相对控制语句退后几格,而它 们之间包含的语句又退后了几格。 表 18-26 用 begin-end 对缩排两次的 Pascal 例子 for i := 1 to MaxLines do begin ReadLine(i); ProcessLine(i); end 这是另外一种看起来很好但却违反了格式化基本原理的另一布局形式。研究表明,一次缩 排与两次缩排在理解上是差不多的,但却不能正确反映代码的逻辑结构。ReadLine()和 ProcessLine()看起来好像从属于 begin-end 对,但事实上却不是。 这种方法增加了程序逻辑结构的复杂性,表 18-27 和表 18-28 中哪一个看起来更复杂? 表 18-27 抽象结构 1 █████████████ ████ ███████ ████████ ███ 第十八章 布局和风格 287 表 18-28 抽象结构 2 █████████████ ████ ███████ ████████ ███ 上述两个抽象结构都代表了 for 循环的结构。虽然两者形式表示同一代码,但抽象结构 1 却显得比抽象结构 2 更复杂。如果你的嵌套有两至三层,那么这种两次缩排的形式会使你的程 序产生四到六次退格。这种布局会使代码显得比原来的更复杂。避免的方法是用纯块结构模仿 法,或用 begin 和 end 作块边界并与其内部语句对齐的方法。 18.4.2 其它方法 虽然块的缩排是格式化控制结构的主要方法,但也有另外几种可供选用的方法。以下提供 几点参考。 段之间用空行。有些代码的块不能用 begin-end 对来划分。一个逻辑块——同一类的一组 语句——应当像写英语文章一样一起形成一段。把这样的逻辑块(段)之间用空行隔开。表 18-29 的例子便是用空格隔开的例子。 表 18-29 应当组织成块并隔开的 C 语言例子 Cursor.Start = StartingScanLine; Cursor.Ed = EndingScanLine; Window.Title = EditWindow.Title; Window.Dimensions = EditWindow.Dimensions; Window.ForegroundColor = UserPreferences.ForegroundColor; Window.BlinkRate = UserPreference.ForegroundColor; Windows.BackgroundColor = UserPreferences.BackgroundColor; SaveCursor(Cursor); SetCursor(Cursor); 这段代码是正确的,但有两条理由应当用空行。第一,当一组语句与执行顺序无关时,你 可以如上例随意混在一起,无需为计算机作进一步的排序。但是作为读者都希望从你的特定程 序顺序中获得某些线索,以判定哪些句子该属于同一组。在一段程序中加上空行使你很清楚地 知道哪些语句是属于一起的。修改程序如表 18-30 所示。 修改后的代码显示出程序要做两件事,但: 表 18-30 这个 C 程序把语句适当分组后分开 Windows.Dimensions = EditWindow.Dimensions; Window.Title = EditWindow.Title; Window.BackgroundColor = UserPreferences.BackgroundColor; Windows.ForgroundColor = UserPreferences.ForegroundColor; Cursor.Start = StartingScanLine; Cursor.End = EndingScanLine; 第十八章 布局和风格 288 Cursor.BlinkRate = EditMode.BlinkRate; SaveCursor(cursor); SetCursor(Cursor); 上一个例子不分组也无空行,使人觉得好像这些语句都有联系似的。 第二个加空行分段后,若想给每块写上注释,那这里相当于自然地留下了空间。本例中若 要加上注释则更提高了布局的透明性。 单条语句的程序块也要坚持格式化。单语句程序块是一个控制结构仅跟一条语句,比如 if 测试条件后仅跟一条语句。这种情形中,begin 和 end 对于保证正确的编译是不必要的了。这 种情况有如表 18-31 所示的三种可选格式。 表 18-31 这个 Pascal 例子提供三种 for 的单语句块的选择模式 if( expression ) then ——格式 1 one-statement; if( expression ) then begin ——格式 2a one-statement; end; if( expression ) then ——格式 2b begin one-statement; end; if( expression ) then one-statement; ——格式 3 这三种方法各有千秋。格式 1 是单条语句退格作为一个块方式,它显得很协调。格式 2(2a 或 2b)也很协调,它在 if 测试条件后增加了语句,完了再加上 begin 和 end 对,因而减少了 出错的机会。这种错误常很隐含,因为你所增加的句子都是退格写的,不注意是看不出来的; 但是计算机却不理会这种退格。格式 3 是这样一种形式,当把它拷回到另的地方去时,作为一 个整体拷贝出错的机会很少。这种格式的一个不好之处便是在一个面向行调试器中,调试器把 这整行当作一行看待且不显示在 if 测试条件后的行是否被执行。 我曾用过格式 1,并且常成为修改时出错的受害者。我也不喜欢缩排方式的变异情况格式, 因而总是避免用它,我比较喜欢用格式 2 的两种情况,因为它们看起来协调且易修改。不管你 用哪种格式,你要一直都用这种格式。 对于复杂的表达式,把单独的条件列成单独的一行。把复杂条件的每一部分写成自己单独 的一行。表 18-32 显示了一个没注意可读性的例子。 这个例子是为计算机格式化的而不是为读者。 表 18-32 这个 Pascal 例子的表达式可读性极差 if ( ( '0' <= InChar and InChar <= '9' ) or ( 'a' <= InChar and InChar <= 'z' ) or ( 'A' <= InChar and InChar <= 'Z' )) then
还剩99页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 6 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

chizemin

贡献于2012-10-18

下载需要 6 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!