SoftEng 版 (精华区)
发信人: Sun (大灯泡), 信区: SoftEng
标 题: 软体设计的思维(转载)
发信站: 哈工大紫丁香 (2000年09月03日17:03:51 星期天), 转信
【 以下文字转载自 Programming 讨论区 】
【 原文由 lofe 所发表 】
软体设计的思维
林俊杰 著
第 １ 节 前言
常常有人问笔者：要学什麽程式语言比较好？同样这批人在学会某种程式语言後，
又常会问说：接下来要学什麽程式语言呢？为什麽学会电脑语言却又写不出程式来呢？
相信读者中必然也有不少人有类似的问题，但可能找不到适当的答案。因此你这时你
不禁会怀疑：电脑到底可以干啥？
基本上这源自於一个很简单的误解，因为不少初学者认为除了了解键盘如何使用、
电源如何起动外，学电脑最主要的目的是要学会如何写程式！而不是用来处理资料、
编辑文书......。当然啦！如果有心人想对电脑科学做更深入的研究，当然是乐观其成
的，但可惜的是入门者常常是在走错路後才恍然大误。这不但浪费时间，也相对的浪费
金钱。有□於此，笔者希望能透过这篇文章，让有心大众能少走些冤枉路，而加速迈向
成功的终点。
第 ２ 节 你要电脑为你做什麽
为什麽需要写程式呢？理由很简单，就是因为你对电脑有所求！希望它能为你作些
事。点子（计画）的来源可能是前夜周公来托梦，或者是因应他人的需要（例如朋友、
客户、或是自己）而产生的。你应该详细的思考一下你对电脑的要求，你希望它作些什麽
事，程式必须有何功能？输入资料的型式（是图片、文字叙述、电话号码......）？输出
的结果？型式？......越周详的考虑，对於往後的工作进行会有越佳的帮助。
一般而言，这些杂七杂八的要求可能会显得十分混乱，特别是由那些不懂电脑的所
开出的规格，更是匪夷所思，摸不著头绪。而身为工程师的您，你的工作便是分析出程式
的功能。这有点像是室内设计师的工作，你的客户只可能会告诉你，这□要摆张桌子，
但不告诉你尺寸；他可能会突然想到椅子上必需要镶入珠宝，但却不会去考虑椅子是红
还是黑的......。因此，充份的沟通是有必要的，软体工作者应该充份的了解客户的需要
。当然这点做起来可能很难，特别是当你的客户是暴发户型的大老板时，那麽此时必需要
以心理医师的方法慢慢的诱导出你所要知道的细节。
如果你写程式的原因是要交作业的话，尽可能的弄清楚文字说明的意义，该达到的
目标一点都不可少，与主题无观的应予抛开。想一想下面这个问题（这题是七十九年度
程式设计比赛校内初赛的一个问题）：
“设计一程式，以之判读一般之中序算术式，是否为有效或无效之运算式。
式子中所涉及的运算元暂定为由Ａ到Ｚ或ａ到ｚ的单一字元，可为使用之
运算子则包括加、减、乘、除及括号与次方。程式的输入为一中序的运算式，
而其输出为一判读之结果。”
这边要特别解释一下：中序运算式指的是我们一般所列的式子，例如 1+2=3 。
题目就这麽多，条件也说的很明白了。让我们来整理分析一下它到底要作什麽。
关键字句在於“判读一般之中序算术式，是否为有效或无效之运算式”，说得清楚些
，就是说判断一个式子是否正确，例如 1 + 2 是对的, 但 1 +* 3 就不对了。另外，
我们必需知道哪些符号是合法的，由“加、减、乘、除及括号与次方”此句中我们知道
可以用“＋”、“－”、“＊”、“／”、“（”、“）”、及“次方”。前面的符号
都没问题了，但“次方”就麻烦了，因此电脑的符号系中似乎没有强制限定次方符号，
例如 BASIC 是以 ^ 为次方符号，FORTRAN 是以 **，甚至Ｃ语言根本就没次方这回事。
此时，尽可能的与试务人员交换意见，或者明白的在你的说明文件中定义次方符号。但
因为这场比赛是以 BASIC 撰写的，因此便以 BASIC的 ^ 表示了。接著，在“运算元暂定
为由Ａ到Ｚ或ａ到ｚ的单一字元”此句中我们知道一个算式必需以英文符号代入运算，
例如 x=y+z，但相对的，23+12 就是不合语法的了。并且，题目中只要我们辨别出运算式
是否正确即可，不必画蛇添足，算出到底是多少来。另外题目中并未提到“运算式的来源
”，究竟是经键盘输入或是由档案中取出呢？但经了解後是由键盘输入。而以上就是对
有限条件题目的分析。
在你仔细的分析完这个问题後，你可能会发现解决这个问题对你而言可能是力不可及
，或者是所需时日甚多，无法如期完成，或是有现成的套装软体可以立刻解决此需求的...
.... 而无论如何，这就是我们所以要分析定义问题的缘故。
第 ３ 节 仔细的思考软体的结构
经过一番努力後，你已经定出一套完整的规格，此时你大概也有个谱了。然而这只是
第一步罢了，系统结构尚未建立呢！因此别兴奋的太早，接下来你应该要把梦想落实，
一步一步的具体化。规划的目的除了在描绘具体的软体结构外，重点是要进行模组的建立
，资料格式的规划，模组间的通讯协定（Protocol）等工作。
关於规画软体，有很多理论上的设计方法。但有谚曰：『一图胜过千言万语』。画图
是帮助我们规画程式的最佳方法。几个比较著名的方法，例如流程图、拿西－尼得门图
(Nassi-Shneiderman)、及下面要谈的 DFD 图。
第３．１节 ＤＦＤ图
一般的软体，最基本上可分为“输入”、“处理”、“输出”三部份；所谓的“资讯
”，其实所指的就是经过处理後的“资料”，因此ＤＦＤ图便应运而生了。ＤＦＤ图的
精神就在於资料流程的规划、各处理单元的动作、并且可以作更深一步的切分。ＤＦＤ图
有几个符号，介绍给大家认识一下：
┌——┐
│ │ 外界个体 系统输入的起点或输出的终点
└——┘
□—□
│ │ 转换程序 执行输入资料处理转换成输出资料的单元
□—□
□———→ 资料流 用以连接不同的程序，以表示资料传送的方向
——□ □—→
↓ │ 资料储存所 资料储存的地方，箭头表示资料的来源及输出的方向
〓〓〓〓〓〓〓
举一个银行自动柜员机的 DFD 图：
┌————┐ 提款卡密码 □———□ 付款讯息 ┌——┐
│ 终端机 │——————→ │柜员机│ ————→ │点钞│
│ 键盘 │——————→ │ 系统 │ │付款│
└————┘ 提款金额 □———□ └——┘
《第 A 层次的 DFD 图》
这是最初步的，未经细部规划的。但一个雏型已经产生了。下一步工作是逐步的将
DFD 图分解成细节。
┌————┐ 提款卡密码 □———□ 帐户资料
│ 终端机 │—————→│总行电│←—————□
│ 键盘 │——┬——→│脑查核│————□ │
└————┘ │ □—┬—□ 帐户 │ │
│提款 │查核 │ │
│金额 │结果 ↓ │
│ ↓ 〓〓〓〓〓〓
│ □———□ 银行的辅助除存装置
□——→│柜员机│ 例如磁带机
│ 电脑 │
□—┬—□
│ 付款讯息 ┌——┐
□——————→│点钞│
│付款│
└——┘
《第 B 层次的 DFD 图》
┌————┐ 提款卡密码 □———□ 付款讯息 ┌——┐
│ 终端机 │——————→ │柜员机│ ————→ │点钞│
│ 键盘 │——————→ │ 系统 │ : │付款│
└————┘ 提款金额 □———□ : └——┘
. ...
. ...
. ....
. :.
. □———□ 帐户资料 .
提款卡密码 │银行电│←—————□ .
—————→│脑查核│————□ │ .
—————→□—┬—□ 帐户 │ │ .
提款金额 │查核 │ │ .
. │结果 ↓ │ .
. ↓ 〓〓〓〓〓〓 .
. □———□ 银行的辅助除存装置 .
. │柜员机│ 例如磁带机 .
. │ 电脑 │ .
□—┬—□ .
│ 付款讯息 .
□—————————→
《资料流程的分解》
第３．２节 由上而下的程式设计 (TOP-DOWN DESIGN)
由上而下的设计哲学，是一种逐步细致化的设计概念。就像你写生时，必然是先打
草稿，既而以大号画笔勾勒轮廓，再用更细些的笔描绘出细部构造。很少有人是拿细笔
一笔一笔刻划的，即使有，也不容易画得好。可能的结果是画虎反类犬。有个人找了位
建□师帮它设计一幢洋房；数周後，他去找建□师看看设计图。於是建□师便拿了张图
告诉他说：“让我们来看看厕所屋顶的水管设计图”。“可是我还不知道房子到底是什麽
样呢？”顾客说。诚所谓纲举目张，当结构设计好之後，细节就可一一浮现了。并且，
由上而下的方式，不仅运用於初期的规划，也应用於编码 (CODING)、测试时。
一般而言，一个完整的程式是具有“层次性”的。大部份看来就像例图这般：
（当然实际情况会复杂多了）
┌———┐
│主程式│
└—┬—┘
│
┌—————┼——————┐
│ │ │
│ │ │
│ │ │
┌———┴—┐ ┌—┴———┐┌—┴———┐
│主要模组Ａ│ │主要模组Ｂ││主要模组Ｃ│ ．．．．．
└—————┘ └——┬——┘└—————┘
│
┌———┴┬—————┐
│ │ │
│ │ │
┌—┴———┐
│次要模组Ｄ│．．．．．．．．．．．
└—————┘
（模组在下一节介绍）
因此我们对一个程式的结构应该是由顶端主程式开始思考，再逐步的往下深入，像
盖房子要先打地基，再建一楼，再建......如此一层层的堆上的。在作由上而下设计时，
要避免“向下思考”，也就是说先不要考虑下一层模组的工作。并且也不要在规划时期就
急著编码。不然何必先规划呢？
同样的，当程式在编码 coding 时，则能够先写上层的模组，再继续往下写。写好
一个上层模组後，可以先进行模拟测试，完成後再继续下一步骤的工作。
不过由上而下的设计、编码、测试都只是大原则罢了。一个专业的设计师真正在工作
时可能也会由下而上的设计、编码、测试。为什麽呢？因为我们可能会须要一些低阶的
副程式，例如视窗副程式、绘图驱动程式、通讯程式等等，不过要注意的是，这种由下
而上的写作方式依然还是得在由上而下的订定整体结构後才实行，不然常常会发生上下
模组无法衔接的情况，这就像开挖隧道一样，你可以分两组人马分别从两端开挖，但精密
的测量和协调绝对是必需的，否则将会出现两条隧道......。
第３．２节 结构化的程式设计
将到结构化，很多人便会想到“ｇｏｔｏ”叙述的存废问题。理想中我们的确不希望
见到ｇｏｔｏ的存在，但对於那些老旧的程式语言而言 (BASIC, FORTRAN, COBOL...)，
去除 GOTO 叙述是几近不可能的！
那麽到底结构化程式设计的本质是什麽呢？在结构化设计的理论中，任何一个程式的
流程都可以被分类为三种形态：循序、二元分歧、回圈。也就是说经由这三类的基本指令
就可以构成一整个程式。
│ │ │
│ │ │
↓ ↓ ↓
┌————┐ ／＼ ／＼
│ 处理 │ ／ ＼ ／ ＼
│ 方块 │ 〈 判别 〉 ┌→〈 〉
└————┘ ＼ ／ │ ＼ ／
│ ＼／ if │ ＼／
│ │ │ │
↓ │ │ │
┌——┴——┐ │ ↓
then │ │ else │ ┌————┐
│ │ └—┤ │
↓ ↓ │ │
└————┘
循序结构 选择结构 回圈结构
另外，整个程式的流程是极顺畅的由起点到终点，而不是用 goto 指令改变程式的
流程。结构化的程式在阅读上十分容易，因为阅读者不必跳来跳去阅读，而是一目了然
的！下面附的是一个用Ｃ＋＋所写的□例，读者可以感受一下她的优美性：
int main( int argc, char *argv[] )
{
if ( argc != 2 )
{
cerr << "Usage: lookup classname\n";
return 1;
}
Dictionary& classDefinitions = *( new Dictionary );
for ( int i = 0; i < CLASSDEFINITIONS; i++ )
{
String& className = *( new String(classNames[i]));
String& classDef = *( new String( classDefs[i] ) );
Association& entry =
*(new Association(className,classDef));
classDefinitions.add( entry );
} // end for all class definitions
Association& definition =
classDefinitions.lookup( *(new String ( argv[1] ) ));
if ( definition == NOOBJECT )
{
cout << "A definition for " << argv[1] <<
" was not found in the dictionary.\n";
}
else
{
cout << definition;
}
} // End Function main //
第３．３节 模组化程式设计
模组是一套功能独立的程序，这麽说或许有点笼统，现实中来讲，一件单一的工作
可以说是一个模组。例如我们可能会需要一个“管理档案”的模组，来做一些建档、开档
、读档、写档、关档、删档的工作。而很明显的，一个大模组可能还包含几个小模组，说
『包含』可能不适合，但我们或许可以认为一个大模组是架构在小模组上的，就像“管理
档案”的模组底下还有建挡、开档....这些次要模组。一个模组内部具备了程序及资料
变数，因此像是一个“独立王国”似的。模组和模组间经由“呼叫”的方式以达成资料的
交换、工作的转换。因此一个程式的结构或可以看成很多模组的组合。
┌程式——————————————————————————┐
│ ┌模组Ｂ———————┐│
│ ┌模组Ａ————————┐ │ ││
│ │ │ │ ┌模组┐ ││
│ │ ┌模组A-1 ————┐│ └————┼ Ｄ ┼——┘│
│ │ │ ┌模组A-1-1 ││ ┌模组Ｃ—┼ ┼┐ │
│ │ │ │ │││ │ └——┘│ │
│ │ │ │ │││ │ │ │
│ │ │ └————┘││ │ ┌模组C-1 ┐ │ │
│ │ └————————┘│ │ │ │ │ │
│ │ ┌模组A-2 ———┐ │ │ │ │ │ │
│ │ │ │ │ │ │ │ │ │
│ │ │ │ │ │ │ │ │ │
│ │ │ │ │ │ │ │ │ │
│ │ └———————┘ │ │ └————┘ │ │
│ │ │ │ │ │
│ └———————————┘ │ │ │
│ └————————┘ │
│ │
└————————————————————————————┘
你可以把上图看成一间房子，里头有三个大房间，大房间里又有小房间，小房间里
有小柜子......。以模组Ａ来讲，他又包含了Ａ－１和－２模组，此时我们可以发现一个
现象：整个模组 A 的公共变数资料，模组 A-1 和 A-2 都可以用得到，因为这并未超过
它的有效□围，反之模组 A-1 的变数并不能对模组 A 及模组 A-2 发生影响，但却可以
影响 A-1-1 模组。不过在大部份情况下，各个模组还有自己的私有变数值。另一种模组
的组合情况会和模组Ｄ一样，是一个共用的模组。这就像是 PRINT 这种模组一样，大家
都要用的。
另一个我们关心的问题是模组间参数的传递。除了某些语言先天上的限制外，模组间
讯息的传递应该尽可能的不要经由“公共变数”来传递，否则一些公用变数的意外改变，
其副作用是很难预料的。一般而言，一次所传递的参数个数不要超过七个！为什麽是“七
”呢？这不是明牌号码，是由心理学家所研究出来的结果。因为一般正常人同一时间内
大概能注意七件事情，当然会有所差异，不过其□围总在７±２之间。也就是说超过这个
□围的，可能较难为人所了解。不过若真有需要，可以考虑传递整个资料聚合体，例如
Pascal 的 RECORD，或Ｃ的结构......等。
一个模组该有多大？笔者认为实在没有什麽好限制的，而且也没什麽标准可以用来
明确的告诉我们模组该有多大多小。当然了，在某些软体专案里可能会用长度来限制模组
大小，以达到模组化的目的，但设计师仍然可以投机取巧，先撰写好他的程式，再依一定
长度来切，不过以这种方式所产生的模组大概都不会是很好的模组罢了。那麽我们要如何
衡量某个模组是不是太大，该减肥了呢？读者应该可由後面提到衡量模组紧密性的观点
来看。但不可否认的，太长的模组不仅不易了解及侦错，它本身或许还能再被细分成更小
的模组。
基於模组的性质，我们必需从两方面来讨论它。第一点是由模组本身“内部”的内容
来看，分析其内容的『紧密性』，这就像一个工厂的生产线，其工作内容是否相关，可能
某些工人的工作是在锻造钢板，有些是在焊结钢板，这些都算是蛮密切的关系，但如果有
些工人作的事是织布，这之间的关系就小了。第二点是由模组与模组间的『关联性』，
这就像一栋大厦中的住户间的关系，或许有的是亲戚，有的是朋友或同事，但也可能毫无
关系。
紧密性
———
偶然紧密性：一个单一模组或许做了几件工作，但这几件工作都没什关联，充其量只是
一种随机的组合。读者若搞不懂的，请将『紧密』那两个字遮起来不要看，
因为这个紧密不是一个形容词。这种情况有点像是一家百货公司，东西卖得
很多，不过彼此实在没什关联。
逻辑紧密性：相对於偶然紧密性。一个模组里的工作是有关系的。这就像是“美食街”
这类餐馆一样，卖的都是食物，是要填饱肚子的。
时间紧密性：如果一个模组里的工作必需在同一段时间内执行，便具有此特性。例如
开门锁这件工作一样，在你转动钥匙的当时，还要用手转动门把才行。
程序紧密性：如一模组内的单一工作有一定的执行顺序，便称为具备了程序紧密性。
好比说你必需先打开电源，才能用电脑一样。
沟通紧密性：如一模组内的工作集中的存取某一些特定的相同资料，例如你和班上的
同学为了交老师的报告，必需参考一些资料，但相信不少人，甚至大部份人
都会找同一本书来参考。
顺序紧密性：如果一个模组内的“很多”工作有先後的顺序，和程序紧密性的“单一”
不同。例如你先得爬上二楼，才能上三楼，然後再上五楼。
功能紧密性：假如一个模组的工作都是相同的话。例如某个模组的功能就仅仅是作两整数
Ａ与Ｂ的相加而已。
偶然紧密性 时间紧密性 沟通紧密性 功能紧密性
│ │ │ │
│ 逻辑紧密性 │ 程序紧密性 │ 顺序紧密性 │
│ │ │ │ │ │ │
│ │ │ │ │ │ │
│ │ │ │ │ │ │
↓ ↓ ↓ ↓ ↓ ↓ ↓
│←（低）——————— ＜＜紧密度＞＞ ——————（高）→│
关联性
———
缺乏关联性：这由字面上就知道，模组和模组间毫无瓜葛。
资料关联性：模组之间传递的资料是一个一个参数。
记号关联性：模组与模组间传递资料的方式不是传递一个个单一的参数列，而是整个
资料结构（资料的聚合体）。就像你写信给某人，寄的不是一张张的信纸，
而是一本书加上几盒磁片，或许还有油画......。
控制关联性：模组间所传递的资料若不是”单纯的资料“，而是一些控制的旗号。这就像
美国总统下给驻波斯湾官兵的命令不是一本厚厚的攻击计划，而只是攻击的
代码而已。这样海珊就不知道布希要宰他了。
外界关联性：模组与模组共同运用一个特定的 IO 装置。
共同关联性：模组与模组之间共用同一部份的资料。就像薪资模组和出席模组共用人事
资料一样。
内容关联性：若一个模组会用到另一个模组的控制资料，或者可以从另一模组中间开始
执行。这种情况必需尽力避免。
缺乏关联性 记号关联性 外界关联性 内容关联性
│ │ │ │
│ 资料关联性 │ 控制关联性 │ 共同关联性 │
│ │ │ │ │ │ │
│ │ │ │ │ │ │
│ │ │ │ │ │ │
↓ ↓ ↓ ↓ ↓ ↓ ↓
│←（低）——————— ＜＜关联度＞＞ ——————（高）→│
一般而言，我们希望模组内的紧密度越高越好，而模组间的关联度越低越好。不过
这只是希望如此罢了，真实的程式绝对不可能是如此，但设计师还是可以用这些标准去
衡量模组化的程度。
透过模组化的设计方式，我们可以一步步的建立通用性的程式库 (libaries)，也
可以引用过去所建立好的程式库。当然写作一个通用性的模组并不会是一件很容易的工作
，因为该模组的功能在不同的情况下必须满足不同的需求。例如一个输出副程式，可能
早期是写给单色显示系统的，但时代的进步，使得程式也必须支援彩色显示系统了，此时
程式库便须要修改了。这点就成为软体维护上的一个问题了。
第 ４ 节 资料结构与演算法
最近看到不少人都在参加″电脑择友″的活动。参加这活动的男男女女将条件填在
表格上，寄给主办单位的电脑，处理後将形成″最佳″的配对资料。但笔者要偷偷的告诉
你们，要换成是笔者，就根本不会期待这个结果是正确的！当然啦！如果有人因此而陷入
热恋，那我们应当祝福他们，但请不要告诉他们说：有个姓林的电脑狂说电脑择友是唬人
的！
诸如电脑如何由众人中依条件找出配对的方法，或是电脑鼠走迷宫，事实上都是按照
一套已经预先建立好的方法来进行，此便称为演算法。广义的演算法解释是这样的：凡是
一个程式的执行，必然是按照一定的规则步骤去进行。整个程式的流程便是一个演算法，
但一个大的演算法可以是（或必然是）许多演算法个体的结合。但通常我们常常会讨论
一些特殊用途的方法，例如刚刚举的电脑择友，数字从小到大的依序排列，乃至於计算机
的微分解法，都可归类为狭义的演算法。而资料结构与演算法则是一体的两面。正确来说
是密不可分的，更保守来讲演算法就是资料结构，资料结构就是演算法！但若要笔者来分
的话，笔者则将资料结构定义为一个“资料的抽象描述方式”，而演算法则是“处理资料
的方法”。
“条条大路通罗马”这句话可以说是程式设计千古不朽的铭言啊！因为解决一个问题
的方法必然不会是唯一的，举例说从台湾到美国，你可以考虑坐飞机，也可以搭船，当然
啦，如果你自愿游泳渡过太平洋笔者也不反对。但是“效率”与“实行成功性”便成为
我们必需好好考虑的要素。坐飞机无疑是最有效率的选择，但却不适合大量货物的运送，
因此此时你便得考虑船运。如果你没钱买机票或船票，那麽游泳可能便是你最後的抉择了
.......。选择正确的演算法，会使程式的效率大为提高，并且可以确保程式是否能正确
完美的执行。并且对於某些特殊问题的解答将会获致意想不到的效果。
其实整个资讯科学可以分成两大类别：一是实务派，也就是真正投入工业生产的，
把演算法实际“实作”的；另外一类是学术派的，他们的工作主要是研究规划特定的演算
法，但两者并非相冲突的。一位好的程式设计师通常也应该是一位好的演算法设计者，
否则他也必需要会正确的引用已知的特定演算法。但很多″玩家″倒不重视这些了，他们
总以为程式会跑就好了！这是一个很危险的想法，也是不正确的（但这也是专家和玩家的
分野）。理由就像上面所讲的。
不但设计演算法是一们学问，实作演算法（编码）更是一门大学问！一个好的编码
结果必然会有较佳的执行效率，例如“压缩程式”（像 LHARC, PKZIP, PKARC 啦...）
其实大部分用的都是相同的演算法，但其压缩後的缩减比例和计算速度却都有很大的差别
，因此演算法实作的重要性自然不在话下。
由於这篇文章不是讨论资料结构与演算法的专书，笔者的目的是在给各位读者一个
演算法上的概念。但相信藉由举一些著名的演算法为实例必然可以引起读者较高的兴趣。
排序
——
排序法几乎是每一位学电脑的必修的项目。方法很多，笔者举两个极端的例子，它们
分别是“泡沫排序法”和“快速排序法”。假定有一堆散乱无序的数字：（由小而大排）
23,64,2,73
若是用泡沫排序法来解决的话，它会这麽做：依次比较一对数字，如果後者大於前者
，则互换排列；用这个方式从头到尾循环进行，直到没有交换的情况发生才算完成。
执行过程：
┌——┬——————————————————————┐
│步骤│排列情况 │
├——┼——————————————————————┤
│ １│23,64,2,73 第一回合 │
│ │^^ ^^ │
├——┼——————————————————————┤
│ ２│23,2,64,73 │
│ │ ^ ^^ 大小互换 │
├——┼——————————————————————┤
│ ３│23,2,64,73 因为发生过交换，所以必须继续执行 │
│ │ ^^ ^^ │
├——┼——————————————————————┤
│ ４│2,23,64,73 第二回合 │
│ │^ ^^ │
├——┼——————————————————————┤
│ ５│2,23,64,73 │
│ │ ^^ ^^ │
├——┼——————————————————————┤
│ ６│2,23,64,73 并未发生交换 │
│ │ ^^ ^^ │
└——┴——————————————————————┘
另一个解决排序问题的方法是“快速排序法 Quick Sort“，相对於泡泡排序法，
Quick 的效率有明显的改善。假定有 n 个数字等待排序，若以泡泡排序解决，理论上须
费时 n 平方的基本时间单位，如果用快速排序法来做，理论上所花费的时间大约是 n 的
1.2 次方左右的基本单位时间。当然实作时会有很大的出入，不过，事实很明显，采用
快速排序法的确能节省较多的时间。快速排序法是如何动作的呢？以一个较简单的概念
来解释，同样是 23,64,2,73 这个数列，Quick 的作法是这样的：
(A)
取一个数 m 为基准，使得剩下的数字可分为两堆，第一堆的任一个数字都小於
等於 m，另一个数列中的任一数字都大於 m。
(B)
将 (A) 步骤所分离出的两个新数列分别再以同样的方法分割，直到不能再分割
为止。
也就是说，QUICK 采用的方法是一个“各个击破”的方式。
第４．１节 选择适当的方法
如前面所提到的，QUICK SORT 的效率高於泡泡排序，但这便表示我们在各种需要
排序资料的场合都应毫不考虑的应用 QUICK SORT 吗？答案并非肯定的，很简单的道理：
如果它真是那麽没用的，它并没有存在的需要！换句话说，泡泡排序在某些场合可能有用
。而这也是本节讨论的重点：适时、适地的选择适当的演算法。
设计程式时常常必需要分析我们所要处理资料的特性，而采取适当的演算法，换句话
说，程式设计师应该要了解资料与演算法的特性。就以上述的泡泡与快速排序的问题来看
，泡泡排序的执行时间与资料个数的关系呈现出一个指数图形，而快速排序则呈现一个
对数的关系。如图所示：
＾ ＾
时间│ + 时间│ ********
│ + │ ***
│ + │ **
│ + │ *
│++ │*
└——————> └———————>
个数ｎ 个数ｎ
泡泡排序法 快速排序法
这表示：当要待排序的资料个数ｎ小於某个□围时，泡泡排序的效率可能会较快速
排序来得快。例如以统计学生成绩来讲，统计一个班的成绩便适用泡泡排序法，因为通常
学生都在五十人上下；但统计一整个年级的成绩就适用快速排序了，因为数量极大。
由上例我们便知道演算法对程式执行效率的影响。在电脑科学界中，有一个最广为
人知的定理便是『空间与时间』的相对关系。在一个理想的环境中，当你在选择演算法及
资料结构时，便需考虑到：到底是花多一点时间来处理资料还是用较多的记忆空间来争取
较快的速度呢？举一个明显的例子，就以『串列』来说，单向串列的每一个节点仅须要
记住指向下一个节点的位址值（当然也可以指向前一个），而双向串列则须记住前後两个
节点的位址，因此双向串列便较单向串列需要更多额外的记忆体。但有得必有所失，双向
串列在做“巡视（TRAVEL）”动作时较单向串列便要快了。理由是因为“回溯（reverse）
”节点时，必需从头计算前一个节点的位址。另一个则可举前面所提的排序法，做“递回
式快速排序”时要耗去不少堆叠的空间，甚至有可能造成堆叠过满的情况，当然解决的
方式不会是采用泡泡排序的，通常我们都会应用非递回的 quick sort 来作。另一个在
生活中常见的实例便是发生在碟式中文系统上，你要是设定较少的字型缓冲区，相对主
记忆体会有较多空间可用，但显示或列印速度便被牺牲了；反之设定较多的缓冲区供中文
应用，显示速度固然加快了，但剩馀的可用空间反而少了，这个结果常常导致很多套装
软体无法执行。
因此在设计程式时应该考虑将重点放在节省时间还是节省记忆体上。假定你设计一个
在中文系统下执行的软体，那你可能必需要尽力的节省记忆体了，因为碟式中文系统常要
花去不少记忆空间。但假使你正在设计一个飞机场的航管系统，那便务必求快，否则空难
的发生将会是家常便饭的事......。
另一个选择演算法所要考虑的要件是“可读性”的问题。固然选择又快又小的演算法
是我们的目标，但各种演算法中，不乏高度数学化、不易为人了解的方法。例如字串的
搜索法就难倒不少工程师了。想从这篇文章中找出『演算法』这个字串有什方法呢？一般
人类直觉上会先比较第一个字，相符後再比第二个字......重覆这样的步骤。这种很笨拙
的『暴力法』的确不太好。有个方法叫 K.M.P., Kunth - Morris - Pratt 法，它的工作
方式是将要比对的字串中每个字元的相对位置，再决定比较失败时要从那里继续工作。
另外还有 BM 法、RK 法，说实话并不容易了解，况且效率不会说有很高的差异（其中
ＲＫ法要用到大量记忆体）。因此很多工程师便乾脆继续用他的暴力法，而舍弃快、但
不易了解的方法。理由是因为这些方法可能造成测试上的困难。另外要程式设计师对於
一个不了解的演算法加以实作，可能不能得到很好的编码（当然这和设计师的经验有关）
。所以便有人认为写程式应该采取 KISS 的规则来，KISS 是 Keep It Simple and Stupid
之简称，而不是 kiss 的意思，就是让程式的流程简单而且“□拙”，这点和我们的校训
『勤□诚勇』好像是相通的。
第４．２节 效率的考量
提到演算法，就不得不让我们考虑到效率的问题。一般对效率的定义是指完成某件
工作所需的时间、空间比。我们可以从几个方面来讨论。
（一）与机器的影响
程式的执行效果在不同电脑上的执行成果，差异是显而易见的，而改善硬体环境则是
提升软体效率最明显的途径。这也是人类为什麽致力於制造更高速的电脑。例如气象局
便需要超级电脑，因为明天的天气总不能等到後天才算出来吧！无论如何，软体还是应该
尽力地提升本身的效率，而不能依恃硬体的进步。否则仍无法发挥整体应有的效能，甚而
形成系统的浪费。
（二）与程式语言的差异
程式语言对於软体效率甚至目标的可行性究竟有多大影响呢？这点在计算机科学界
一直争论不休。但一般而言，在同样的结构、相同的演算法，用不同的程式语言所编出的
程式大概会有１５％～２０％的影响。这是不是说用组合语言写出的作品会有较高的效率
呢？非也非也。良好的计划直接影响了编码的品质。同样的模组若同时以组合语言和高阶
结构化语言撰写，一般的结果通常告诉我们采取组合语言实作将发生悲剧！组合语言通常
会多出１／３的花费（花费指的是用了多少记忆体和时间）。科学家发现“编译程式”的
好坏才是整个问题的关键。现今结构化的编译器对於“最佳化”的处理已经是相当的优秀
了。各位如果手边有 Turbo C 2.0 和 MSC 6.0 编译器的话，不妨自己做个比较，你便会
有惊人的发现。同样的你也可以要求编译器产生组合语言程式码，看看编译器的处理手法
是不是比你用组合语言撰写来的高明。但专业的应用上，我们常是用高阶语言写好原始
程式，再用组合语言作低阶的最佳化，例如绘图函式这类对速度要求极高的部份。
但考虑一下“维护”与“除错”，结构化程式便较非结构化程式语言甚至组合语言
来得容易的多了！况且，每个程式必然都会发生错误！如果因为求一部份模组的“技巧性
”，而导致整体工程的延宕，是很划不来的。
（三）与演算法的影响
事实上，演算法对於整个程式才具有真正决定性的效率影响，理由在上一节就说过了
，为了避免读者忘记，请再参考前面的理由。
（四）与软体结构的影响
与其说是与软体结构的影响，倒不如看成整个系统流程的合理性。事实上整个资讯
科学所关心的，不仅仅只是程式该怎麽写，系统运作的方式也是我们所关心的。因为我们
或是一些机关在处理事情的流程和做法上，常常有重覆而不合理的地方。这种情形或许在
人工作业时期可以谅解，但在电脑化的时代只是多馀的浪费罢了。例如说图书馆的书目
管理，一本书至少须要书名卡、作者卡，还有书籍本身的出借纪录，而借书人的借书证上
还要登记这个人借书的纪录。各种资料实在有够多也有够杂，但如果在电脑上，你还用
这种方法来为每一本书建立各种档案，真是浪费记忆体的行为。事实上书籍只要一个资料
档就可以解决了（理想中），借阅人要查询资料的程序也简单多了；借书证上也不必填
一堆东西，一切都是由电脑来整理归类资料。换句话说，系统的合理性，是影响整个软体
最基本的变因。
第５．１节 程式语言
程式语言依照年代和特性的先後可以分成四类。各代有各代的特色，也因此在软体
设计方式上有不同的方法：
第一代 组合语言／机械语言
最原始的程式只是一堆 CPU 所能了解的指令集，它们都是数字，不过实在很难了解，
像“23 EA 73 66”这样的数字代表什意义呢？除了 CPU 和天才外，恐怕没人能了解，
因此我们便用一些简字符号来代表某个机械码指令，例如 80X86 的 MOV、ADD 等等。
它的特点便是非结构化、极低阶的运算方式、但执行速度极快，不过很难为人了解，因此
在设计上常常造成很多困难， 不过许多较好的编译器都会提供巨集 MACRO，提供较佳的
设计途径。
第二代 非结构化语言
这代语言的黄金时期是在 1960 和 1970 年代。这时代的作业系统正在发展分时系统
，硬体环境相当严苛。BASIC、FORTRAN、COBOL.....都是这类语言的代表。他们的特色是
非结构化，也就是说 GOTO 用的很多，此外缺乏模组化的结构。大家可以看看 BASIC 是
什样子的，大概也就差不多了。
第三代 结构化程式语言
第三代程式语言起於 1960 年末。这代语言都具有严密的区块结构、更抽象的资料
封包方式、结构化的语法结构、适当的资料形态、程序与函数的结构相当完整。Pascal
是最具代表性的程式语言，事实上它当初设计的目的便是指导人们以结构化的思考方式
来写作程式，也因此成为研究计算机科学者必修的语言。Ｃ语言一直是我的最爱，它本来
是贝尔实验室用来发展ＵＮＩＸ作业系统的，但目前许多应用软体也用Ｃ语言来写（例如
dBASE)。Ｃ语言不但具有像 Pascal 的结构，它本身具备了一些低阶的特性，五十馀个
强有力的运算子，使得这个语言的结构更是完美。
第三代语言还有两种较特别的族类，一个是人工智慧 (AI) 用的程式语言，另一种是
物件导向程式语言 (Object Oriented Programming Language, OOPL)。人工智慧语言可以
用 LISP 和 PROLOG 为代表。这些语言的特点在於它们对符号处理能力很强，PROLOG 对於
阶层性的串列还可以自动回溯。OOPL 则应以 SmallTalk 为代表。Smalltalk 和Ｃ一样也
是贝尔实验室的产品。它允许我们将有关的资料与程序（OOP 术语叫方法 METHOD）捆成
一包“物件 Object”，相类似的新物件可以经由“遗传”旧物件而来。整个 Smalltalk
就有三四百个库存的物件，一位 Smalltalk 的设计师只要遗传这些物件就可以了。最近
渐趋热门的 C++ 则是在这股 OOP 风潮下，由原先的Ｃ语言加强而成的。
第四代程式语言 ４ＧＬｓ
第四代程式语言又较第三代来的高阶并且更抽象化。以前程式设计师必需费时於设计
很多演算法。但经由第四代程式语言，设计师只要描述它所要的需求（requirement)，
就可以轻易地设计出程式来，例如 dBASE 等。不过目前大部份 4GL 都用在资料库或商业
方面，并不易运用於其它的□围，例如系统程式的设计。不过等将来人工智慧的技术发展
成熟了，相信 4GL 必然会成为主流。
笔者强烈地推荐以第三代以後的语言来设计程式，第三代语言的好处在於它能够很
简单将各类演算法实作出来，并且又具有易於除错和维护的优点。第四代语言则可以节省
大量的时间在细节的设计上。第二代语言如 BASIC 或 FORTRAN 要真和 Pascal 或Ｃ比起
来，实在是很可怜的。
第５．２节 考虑系统
笔者认为有时真实世界的作业环境对於程式设计者常常会是一场梦魇。此话怎讲？
因为我们常常看到教科书上不断的提示说：降低程式对於电脑（机器）的依赖性。这句话
实在说得很暧昧。假如你今天设计一个在ＰＣ上使用的电动玩具，你将会发现各机器的差
异是如此的大，光显示器常见就四、五种了，还有各家音效卡也不一样，透过 BIOS 来作
绘图的工作似乎是很愚笨的一件事，因为像 F-19 这类模拟飞行的游戏玩起来将会像骑三
轮车一样缺乏速度感！与系统的相依性越低，可能就必需降低不少效率！这真是一个让人
伤脑筋的问题。我们实在不得不承认：一套软体的发展的确受限於电脑硬体环境的限制。
笔者提出一些解决的参考方案：将与硬体高度相关的部份独立成模组；在规划程式的当初
最好考虑将要采取的系统或是周边装置。不过，仔细想想，大部份程式实在不是很有必要
依靠机器，顶多也是一部份罢了！
另一个 PC 使用者常见的问题是在於『编译器』的问题！特别常见於用ＴＣ的人身上
。虽然程式语言几乎都有国际标准的语法（例如 ANSI, ISO 等），但移植到各种电脑、
作业系统、编译器上就会出现『方言』，这导致程式原始码（source code）的可携性降
低。这就像是湖南老乡见到山东大汉一样，虽然讲的都是中国话，但沟通上实在有困难。
解决这个问题有两点建议：（一）当你开始写程式时，就必需按标准来写，即使有部份要
用到方言的语法，必须分开独立并且要详细的指明。（二）下定决心，将终身大事托付给
你的编译器吧。
第６节 撰写程式的风格
程式设计本质上至少有一半具有艺术创作的特性，好的程式往往就是一件艺术品。
而你，电脑艺术家，具有你自己的风格，你自己的创意，因此你的作品将会处处显露出
你独特的个性。
当然这麽说并不是要你将程式『画』得像毕卡索的作品一样，但至少你的程式应该
具备一些特性：明确的定义、详尽正确的注解、善用缩格与空白等等。当然你可以培养出
你特殊的气质，展现在你的程式中。
注 解
———
注解是说明程式码内容的文字，明白而清晰的注解使得程式码容易阅读与了解，
很多人多懒於撰写注解，他们常见的藉口不外：
我的程式本来就很容易了解了
我当然看得懂我自己写的程式了
诸如此类都不过是推拖之辞罢了！人们常常忘记一些琐碎的问题，这当然也包括他们
自己的程式在内。到底这个函数的参数代表什麽意义呢？他的传回值又是什麽？萤幕的
左上角是（０，０）还是（１，１）？ 这些都应是注解的内容之一。但我们须要写多少
的注解？注解的内容又该有多详细呢？ Planger 说：『好的注解不能代替坏的编码，
然而好的编码是否就能够取代注解，那就不得而知了。』烂的注解就像撒旦一样，会给你
错误的指引。通常的规则是把注解分两类来写：前言性注解（prologue comments）和功能
注解（functional comments）。前言式的注解一般是放在模组的前端来指明该模组的技术
简明资料，大概包含了：
（一）功能和目的
（二）介面说明
A. 说明参数意义
B. 说明传回值的意义
C. 所需参考到的模组
（三）资料的规格和限制
变数的使用方式和□围，例如标明萤幕左上端是 (1,1)....
（四）发展纪录
谁设计了这个模组，修改的日期和所修改的内容等等历史资料
功能性注解则是安插於程式码中来说明某一区块程式码的功能。写注解并不是写文章
，不必写的长篇大论，但也不要太简略到用几个简字符号。有部份注解的内容可能是在
除错时留下来的，这些注解最好在除错完成後便去除，以免造成误解。另外关於注解要用
英文还是中文来写，笔者倒认为“易懂”才是重点，用中文不一定会比较烂。
变数的命名
—————
常常看许多人用了一些毫无意义的变数名称，像 A,B,C,D,X,Y,Z,PP,SS,TT..
乱七八糟，而这种情况特别常见於初学者。这种习惯不是很好，甚至比那些没写注解的
差上一级，当然要是注解没写，变数名称又乱写的，真应该好好反省了。变数的命名应该
以明白易了解为主。许多人为什麽用无意义的符号来做为变数名称的原因是因为嫌多打
几个字太累，或是占空间等等。不过还有一种是较夸张的行为，就是变数名称写的有够长
，例如：AmountOfYear、KiloMeterPerSecond等等，的确是有点矫枉过正，不过还是比
那些用无意义简字符号来的好。在为变数命名的当初，最好能建立一个『字典』来说明
缩写与展开字的关系。例如：
KM = Kilo meter = 公里
Sec = second = 秒
rec = record = 纪录
当然最好能够将该变数的意义附加在表格後面，建立一个『变数字典』，方便程式
设计工作的进行。
缩 格
———
在结构化的程式中，缩格可以很明显的分别出每一个区块，和各区块间的关系。
例如说：
.... ....
..... .....
if 逻辑判断 then if 逻辑判断 then
begin begin
..... 叙述 ..... 叙述
.... ....
..... .....
for 回圈控制 for 回圈控制
begin begin
..... .....
....叙述 ....叙述
..... .....
..... .....
end end
.... ....
...叙述 ...叙述
end end
.... ....
....... .......
有『锯齿』状的缩格 缺乏『锯齿』状的缩格
缩格与不缩格的效果相当的明显，你要缩多少格都没啥关系，现代的编译器都会自动
辨识，但是对於某些程式语言有『栏位』限制的，例如 FORTRAN 等等，会稍微麻烦点，
但可以尽量的作出这个效果来。另一个焦点是在於像 begin 和 end 这一类“标示区块”
起迄点的位置。以Ｃ来说，它以｛ 表示 begin，以 ｝来象徵 end，结果笔者看到的写法
就有一大堆：
┌———————┐┌——————┐┌———————————┐
│for (......) {││for (.....) ││for (.) { .... .... } │
│ ..... ││{ ││ │
│ ...... ││ ..... ││ │
│ .... ││ ....... ││ │
│} ││} ││ │
└———————┘└——————┘└———————————┘
＜＜几种Ｃ程式的缩格＞＞
不胜枚举啊！笔者是喜欢用中间那个方式，有些教科书则是用第一种，第三种则常见
於只有一行叙述的函数中，这种情况在Ｃ＋＋的教本中特别常见。用缩格时不要担心这是
否影响整个原始码的长度等等，这是多馀的。较长的原始码不会导致程式的效率降低，
但乱七八糟的原始码是铁定会出问题的。
运算式
———
从两个方面来看一个运算式的写法：第一是运算式本质上的复杂度，第二是表示的
方法。以第一个角度来看，这样的式子：
x = 26 * ( 22 + y * 7 ^ z + ( 164 / 64 mod 7 ) )
实在不太理想，因为太多的括号和不明显的本意让人读起来很辛苦，并且，没有经过
最佳化处理的式子也会降低不少效率，例如说：
x = 2/3 + 5/3
在这个式子中，电脑必需做两次的浮点数（简而言之就是带小数）的计算，分别是
2/3=0.666666 和 5/3=1.666666，但如果你写成 x = ( 2 + 5 ) / 3 ，只需做一次
7/3=2.333333 的浮点计算了，而电脑作整数计算远较浮点计算快，这样写效率便提高了。
第二个观点是表示的方法。特别以Ｃ语言为例是因为它所有的运算符号是众语言中
数一数二多的，例如以下的逻辑判别式来说实在有够暧昧：
!x == 3 && y != 6
但是加了括号後就明白多了：
( (!x) == 3 ) && ( y != 6)
善用括号和空白是很重要的！
第７节 除错与测试
除错常常是设计师头痛的来源。每个程式几乎都不免有错，不论是生手或老手的作品
都一样。我们在设计程式之初总会有美丽的憧憬：当我作好规划，然後编码，再修改一些
『小错误』，这个程式就完成了！事实不然，或许你写程式的速度的确很快，但你永远也
无法知道你将会花多少时间和精力在除错上，这真是一个可悲的事实！另一方面，『除错
』这件工作即使是在科学昌明的今日，也缺乏一套好方法，和一些好工具来协助我们除错
，虽然新的除错工具不断的在出现，但除错依旧还是一件令人沮丧的工作。
一般而言，错误被区分为语法上的错误和逻辑上的错误。语法错误的原因主要来自
打字错误或一些无意义的语法，较严重的可能是指令或变数名称的误用，不过这种错误
一般而言都不太麻烦，绝大多数语法上的错误都会由编译器侦测出来。因此我们较关心
是逻辑上的错误。
在讲除错前先说说测试。测试和除错是两码子事，测试工作主要是在运用一些假设的
状况，来查验程式是正常或有错误，因此测试的方式和测试的样本就很重要了，因为没有
正确的发现程式有错，问题将会在日後如山洪一样的暴发出来。当测试工作一开始进行，
并不会断然的立即测试一整个系统是不是正常，因为你一定会发现有错，但找不出错误在
哪，因为程式实在太大了。一般我们会先进行模组测试，等一个个的模组都验证无误後，
系统或许也应该没问题了。测试程式的方式有主要两种策略：黑箱 (Black box) 和白箱
(White box) 两种测试方法，互有利弊。
白箱
——
白箱测试的方式就好像拍摄模组的Ｘ光照片後，再仔细的分析。有四个主要的测试
方向：（一）至少将模组中所有的独立路径测试过一次。（二）测试所有逻辑判断的流程
。（三）以『边界值』来测试模组，例如对於位元组的资料型态，则以边界值０和ｆｆｈ
来测。（四）测试内部所有的资料结构。简而言之，白箱测试就是将模组的内容作执行
路径的分析，因此模组就像是玻璃屋一样，一览无遗。理论上白箱测试应该每一条路径
都须检查，但实际上却有遗漏的可能，特别是在大型的模组中，白箱测试的工作更是复
杂，不过白箱测试仍是必需的。
黑箱
——
黑箱测试用来判定程式是否正确的作了我们要它作的事情。经由这个测试程序，可以
验证程式是否达到我们的要求。例如说我们要测试一台“换钞机”，你可以分别投入各种
币值的钞票，换出对应的零钱出来。这个时候，用来测试的数据就很重要了！因为你的
测试数据不可能包含将来所有可能发生的情况，但你却要保证测试能找出所有的错误！当
然这似乎是不可能办到的。所以我们可以拿以前真正实际应用时的数据，例如说拿百元钞
换十元币，五百元换五角等等。拿实际数据来测有个好处，就是常见的正确情况和常见的
错误情况都包含在里面了，因此可以证明程式在真实情况下的可信度。当然你也可以产生
小鸟
--
※ 修改:．haojs 于 Sep 3 16:54:10 修改本文．[FROM: bbs.hit.edu.cn]
--
※ 转寄:．武汉白云黄鹤站 bbs.whnet.edu.cn．[FROM: bbs.hit.edu.cn]
--
☆ 来源:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: haojs.bbs@bbs.whnet.]
--
※ 转载:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: sunner.hit.edu.cn]
Powered by KBS BBS 2.0 (http://dev.kcn.cn)
页面执行时间：414.562毫秒