軟體設計的思維
林俊杰 著 Jul 17 15:33:32 1994
同【物件導向的天空】一文, 本文亦曾發表於「建中青年」刊物第 94 期。
第 １ 節 前言
常常有人問筆者：要學什麼程式語言比較好？同樣這批人在學會某種程式語言後，
又常會問說：接下來要學什麼程式語言呢？為什麼學會電腦語言卻又寫不出程式來呢？
相信讀者中必然也有不少人有類似的問題，但可能找不到適當的答案。因此你這時你
不禁會懷疑：電腦到底可以幹啥？
基本上這源自於一個很簡單的誤解，因為不少初學者認為除了瞭解鍵盤如何使用、
電源如何起動外，學電腦最主要的目的是要學會如何寫程式！而不是用來處理資料、
編輯文書......。當然啦！如果有心人想對電腦科學做更深入的研究，當然是樂觀其成
的，但可惜的是入門者常常是在走錯路後才恍然大誤。這不但浪費時間，也相對的浪費
金錢。有鑑於此，筆者希望能透過這篇文章，讓有心大眾能少走些冤枉路，而加速邁向
成功的終點。
第 ２ 節 你要電腦為你做什麼
為什麼需要寫程式呢？理由很簡單，就是因為你對電腦有所求！希望它能為你作些
事。點子（計畫）的來源可能是前夜周公來托夢，或者是因應他人的需要（例如朋友、
客戶、或是自己）而產生的。你應該詳細的思考一下你對電腦的要求，你希望它作些什麼
事，程式必須有何功能？輸入資料的型式（是圖片、文字敘述、電話號碼......）？輸出
的結果？型式？......越週詳的考慮，對於往後的工作進行會有越佳的幫助。
一般而言，這些雜七雜八的要求可能會顯得十分混亂，特別是由那些不懂電腦的所
開出的規格，更是匪夷所思，摸不著頭緒。而身為工程師的您，你的工作便是分析出程式
的功能。這有點像是室內設計師的工作，你的客戶只可能會告訴你，這裏要擺張桌子，
但不告訴你尺寸；他可能會突然想到椅子上必需要鑲入珠寶，但卻不會去考慮椅子是紅
還是黑的......。因此，充份的溝通是有必要的，軟體工作者應該充份的了解客戶的需要
。當然這點做起來可能很難，特別是當你的客戶是暴發戶型的大老板時，那麼此時必需要
以心理醫師的方法慢慢的誘導出你所要知道的細節。
如果你寫程式的原因是要交作業的話，盡可能的弄清楚文字說明的意義，該達到的
目標一點都不可少，與主題無觀的應予拋開。想一想下面這個問題（這題是七十九年度
程式設計比賽校內初賽的一個問題）：
“設計一程式，以之判讀一般之中序算術式，是否為有效或無效之運算式。
式子中所涉及的運算元暫定為由Ａ到Ｚ或ａ到ｚ的單一字元，可為使用之
運算子則包括加、減、乘、除及括號與次方。程式的輸入為一中序的運算式，
而其輸出為一判讀之結果。”
這邊要特別解釋一下：中序運算式指的是我們一般所列的式子，例如 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 編譯器的話，不妨自己做個比較，你便會
有驚人的發現。同樣的你也可以要求編譯器產生組合語言程式碼，看看編譯器的處理手法
是不是比你用組合語言撰寫來的高明。但專業的應用上，我們常是用高階語言寫好原始
程式，再用組合語言作低階的最佳化，例如繪圖函式這類對速度要求極高的部份。
但考慮一下“維護”與“除錯”，結構化程式便較非結構化程式語言甚至組合語言
來得容易的多了！況且，每個程式必然都會發生錯誤！如果因為求一部份模組的“技巧性
”，而導致整體工程的延宕，是很划不來的。
（三）與演算法的影響
事實上，演算法對於整個程式才具有真正決定性的效率影響，理由在上一節就說過了
，為了避免讀者忘記，請再參考前面的理由。
（四）與軟體結構的影響
與其說是與軟體結構的影響，倒不如看成整個系統流程的合理性。事實上整個資訊
科學所關心的，不僅僅只是程式該怎麼寫，系統運作的方式也是我們所關心的。因為我們
或是一些機關在處理事情的流程和做法上，常常有重覆而不合理的地方。這種情形或許在
人工作業時期可以諒解，但在電腦化的時代只是多餘的浪費罷了。例如說圖書館的書目
管理，一本書至少須要書名卡、作者卡，還有書籍本身的出借紀錄，而借書人的借書證上
還要登記這個人借書的紀錄。各種資料實在有夠多也有夠雜，但如果在電腦上，你還用
這種方法來為每一本書建立各種檔案，真是浪費記憶體的行為。事實上書籍只要一個資料
檔就可以解決了（理想中），借閱人要查詢資料的程序也簡單多了；借書證上也不必填
一堆東西，一切都是由電腦來整理歸類資料。換句話說，系統的合理性，是影響整個軟體
最基本的變因。
(待續)
留言列表
國家自強 (1)
