算法表達(dá)中的抽象機(jī)制(一）

簡(jiǎn)介

要用計(jì)算機(jī)解決一個(gè)稍為復(fù)雜的實(shí)際問(wèn)題，大體都要經(jīng)歷如下的步驟。

1. 將實(shí)際問(wèn)題數(shù)學(xué)化，即把實(shí)際問(wèn)題抽象為一個(gè)帶有一般性的數(shù)學(xué)問(wèn)題。這一步要引入一些數(shù)學(xué)概念，精確地闡述數(shù)學(xué)問(wèn)題，弄清問(wèn)題的已知條件、所要求的結(jié)果、以及在已知條件和所要求的結(jié)果之間存在著的隱式或顯式的聯(lián)系。
2. 對(duì)于確定的數(shù)學(xué)問(wèn)題，設(shè)計(jì)其求解的方法，即所謂的算法設(shè)計(jì)。這一步要建立問(wèn)題的求解模型，即確定問(wèn)題的數(shù)據(jù)模型并在此模型上定義一組運(yùn)算，然后借助于對(duì)這組運(yùn)算的調(diào)用和控制，從已知數(shù)據(jù)出發(fā)導(dǎo)向所要求的結(jié)果，形成算法并用自然語(yǔ)言來(lái)表述。這種語(yǔ)言還不是程序設(shè)計(jì)語(yǔ)言，不能被計(jì)算機(jī)所接受。
3. 用計(jì)算機(jī)上的一種程序設(shè)計(jì)語(yǔ)言來(lái)表達(dá)已設(shè)計(jì)好的算法。換句話說(shuō)，將非形式自然語(yǔ)言表達(dá)的算法轉(zhuǎn)變?yōu)橐环N程序設(shè)計(jì)語(yǔ)言表達(dá)的算法。這一步叫程序設(shè)計(jì)或程序編制。
4. 在計(jì)算機(jī)上編輯、調(diào)試和測(cè)試編制好的程序，直到輸出所要求的結(jié)果。

在這里，我們只關(guān)心第3步，而且把注意力集中在算法程序表達(dá)的抽象機(jī)制上，目的是引人一個(gè)重要的概念--抽象數(shù)據(jù)類型，同時(shí)為大型程序設(shè)計(jì)提供一種相應(yīng)的自頂向下逐步求精、模塊化的具體方法，即運(yùn)用抽象數(shù)據(jù)類型來(lái)描述程序的方法。

從機(jī)器語(yǔ)言到高級(jí)語(yǔ)言的抽象

我們知道，算法被定義為一個(gè)運(yùn)算序列。這個(gè)運(yùn)算序列中的所有運(yùn)算定義在一類特定的數(shù)據(jù)模型上，并以解決一類特定問(wèn)題為目標(biāo)。這個(gè)運(yùn)算序列應(yīng)該具備下列四個(gè)特征。

1. 有限性，即序列的項(xiàng)數(shù)有限，且每一運(yùn)算項(xiàng)都可在有限的時(shí)間內(nèi)完成;
2. 確定性，即序列的每一項(xiàng)運(yùn)算都有明確的定義，無(wú)二義性;
3. 可以沒(méi)有輸入運(yùn)算項(xiàng)，但一定要有輸出運(yùn)算項(xiàng);
4. 可行性，即對(duì)于任意給定的合法的輸入都能得到相應(yīng)的正確的輸出。

這些特征可以用來(lái)判別一個(gè)確定的運(yùn)算序列是否稱得上是一個(gè)算法。

但是，我們現(xiàn)在的問(wèn)題不是要判別一個(gè)確定的運(yùn)算序列是否稱得上是一個(gè)算法，而是要對(duì)一個(gè)己經(jīng)稱得上是算法的運(yùn)算序列，回顧我們?cè)?jīng)如何用程序設(shè)計(jì)語(yǔ)言去表達(dá)它。

算法的程序表達(dá)，歸根到底是算法要素的程序表達(dá)，因?yàn)橐坏┧惴ǖ拿恳豁?xiàng)要素都用程序清楚地表達(dá)，整個(gè)算法的程序表達(dá)也就不成問(wèn)題。

作為運(yùn)算序列的算法，有三個(gè)要素。

1. 作為運(yùn)算序列中各種運(yùn)算的運(yùn)算對(duì)象和運(yùn)算結(jié)果的數(shù)據(jù);
2. 運(yùn)算序列中的各種運(yùn)算;
3. 運(yùn)算序列中的控制轉(zhuǎn)移。

這三種要素依序分別簡(jiǎn)稱為數(shù)據(jù)、運(yùn)算和控制。

由于算法層出不窮，變化萬(wàn)千，其中的運(yùn)算所作用的對(duì)象數(shù)據(jù)和所得到的結(jié)果數(shù)據(jù)名目繁多，不勝枚舉。最簡(jiǎn)單最基本的有布爾值數(shù)據(jù)、字符數(shù)據(jù)、整數(shù)和實(shí)數(shù)數(shù)據(jù)等;稍復(fù)雜的有向量、矩陣、記錄等數(shù)據(jù);更復(fù)雜的有集合、樹(shù)和圖，還有聲音、圖形、圖像等數(shù)據(jù)。

同樣由于算法層出不窮，變化萬(wàn)千，其中運(yùn)算的種類五花八門(mén)、多姿多彩。最基本最初等的有賦值運(yùn)算、算術(shù)運(yùn)算、邏輯運(yùn)算和關(guān)系運(yùn)算等;稍復(fù)雜的有算術(shù)表達(dá)式和邏輯表達(dá)式等;更復(fù)雜的有函數(shù)值計(jì)算、向量運(yùn)算、矩陣運(yùn)算、集合運(yùn)算，以及表、棧、隊(duì)列、樹(shù)和圖上的運(yùn)算等:此外，還可能有以上列舉的運(yùn)算的復(fù)合和嵌套。

關(guān)于控制轉(zhuǎn)移，相對(duì)單純。在串行計(jì)算中，它只有順序、分支、循環(huán)、遞歸和無(wú)條件轉(zhuǎn)移等幾種。

我們來(lái)回顧一下，自從計(jì)算機(jī)問(wèn)世以來(lái)，算法的上述三要素的程序表達(dá)，經(jīng)歷過(guò)一個(gè)怎樣的過(guò)程。

最早的程序設(shè)計(jì)語(yǔ)言是機(jī)器語(yǔ)言，即具體的計(jì)算機(jī)上的一個(gè)指令集。當(dāng)時(shí)，要在計(jì)算機(jī)上運(yùn)行的所有算法都必須直接用機(jī)器語(yǔ)言來(lái)表達(dá)，計(jì)算機(jī)才能接受。算法的運(yùn)算序列包括運(yùn)算對(duì)象和運(yùn)算結(jié)果都必須轉(zhuǎn)換為指令序列。其中的每一條指令都以編碼(指令碼和地址碼)的形式出現(xiàn)。與算法語(yǔ)言表達(dá)的算法，相差十萬(wàn)八千里。對(duì)于沒(méi)受過(guò)程序設(shè)計(jì)專門(mén)訓(xùn)練的人來(lái)說(shuō)，一份程序恰似一份"天書(shū)"，讓人看了不知所云，可讀性極差。

用機(jī)器語(yǔ)言表達(dá)算法的運(yùn)算、數(shù)據(jù)和控制十分繁雜瑣碎，因?yàn)闄C(jī)器語(yǔ)言所提供的指令太初等、原始。機(jī)器語(yǔ)言只接受算術(shù)運(yùn)算、按位邏輯運(yùn)算和數(shù)的大小比較運(yùn)算等。對(duì)于稍復(fù)雜的運(yùn)算，都必須一一分解，直到到達(dá)最初等的運(yùn)算才能用相應(yīng)的指令替代之。機(jī)器語(yǔ)言能直接表達(dá)的數(shù)據(jù)只有最原始的位、字節(jié)、和字三種。算法中即使是最簡(jiǎn)單的數(shù)據(jù)如布爾值、字符、整數(shù)、和實(shí)數(shù)，也必須一一地映射到位、字節(jié)和字中，還得一一分配它們的存儲(chǔ)單元。對(duì)于算法中有結(jié)構(gòu)的數(shù)據(jù)的表達(dá)則要麻煩得多。機(jī)器語(yǔ)言所提供的控制轉(zhuǎn)移指令也只有無(wú)條件轉(zhuǎn)移、條件轉(zhuǎn)移、進(jìn)入子程序和從子程序返回等最基本的幾種。用它們來(lái)構(gòu)造循環(huán)、形成分支、調(diào)用函數(shù)和過(guò)程得事先做許多的準(zhǔn)備，還得靠許多的技巧。

直接用機(jī)器語(yǔ)言表達(dá)算法有許多缺點(diǎn)。

1. 大量繁雜瑣碎的細(xì)節(jié)牽制著程序員，使他們不可能有更多的時(shí)間和精力去從事創(chuàng)造性的勞動(dòng)，執(zhí)行對(duì)他們來(lái)說(shuō)更為重要的任務(wù)。如確保程序的正確性、高效性。
2. 程序員既要駕馭程序設(shè)計(jì)的全局又要深入每一個(gè)局部直到實(shí)現(xiàn)的細(xì)節(jié)，即使智力超群的程序員也常常會(huì)顧此失彼，屢出差錯(cuò)，因而所編出的程序可靠性差，且開(kāi)發(fā)周期長(zhǎng)。
3. 由于用機(jī)器語(yǔ)言進(jìn)行程序設(shè)計(jì)的思維和表達(dá)方式與人們的習(xí)慣大相徑庭，只有經(jīng)過(guò)較長(zhǎng)時(shí)間職業(yè)訓(xùn)練的程序員才能勝任，使得程序設(shè)計(jì)曲高和寡。
4. 因?yàn)樗臅?shū)面形式全是"密"碼，所以可讀性差，不便于交流與合作。
5. 因?yàn)樗鼑?yán)重地依賴于具體的計(jì)算機(jī)，所以可移植性差，重用性差。

這些弊端造成當(dāng)時(shí)的計(jì)算機(jī)應(yīng)用未能迅速得到推廣。

克服上述缺點(diǎn)的出路在于程序設(shè)計(jì)語(yǔ)言的抽象，讓它盡可能地接近于算法語(yǔ)言。

為此，人們首先注意到的是可讀性和可移植性，因?yàn)樗鼈兿鄬?duì)地容易通過(guò)抽象而得到改善。于是，很快就出現(xiàn)匯編語(yǔ)言。這種語(yǔ)言對(duì)機(jī)器語(yǔ)言的抽象，首先表現(xiàn)在將機(jī)器語(yǔ)言的每一條指令符號(hào)化:指令碼代之以記憶符號(hào)，地址碼代之以符號(hào)地址，使得其含義顯現(xiàn)在符號(hào)上而不再隱藏在編碼中，可讓人望"文"生義。其次表現(xiàn)在這種語(yǔ)言擺脫了具體計(jì)算機(jī)的限制，可在不同指令集的計(jì)算機(jī)上運(yùn)行，只要該計(jì)算機(jī)配上匯編語(yǔ)言的一個(gè)匯編程序。這無(wú)疑是機(jī)器語(yǔ)言朝算法語(yǔ)言靠攏邁出的一步。但是，它離算法語(yǔ)言還太遠(yuǎn)，以致程序員還不能從分解算法的數(shù)據(jù)、運(yùn)算和控制到匯編才能直接表達(dá)的指令等繁雜瑣碎的事務(wù)中解脫出來(lái)。

到了50年代中期，出現(xiàn)程序設(shè)計(jì)的高級(jí)語(yǔ)言如Fortran，Algol60，以及后來(lái)的PL/l，Pascal等，算法的程序表達(dá)才產(chǎn)生一次大的飛躍。

誠(chéng)然，算法最終要表達(dá)為具體計(jì)算機(jī)上的機(jī)器語(yǔ)言才能在該計(jì)算機(jī)上運(yùn)行，得到所需要的結(jié)果。但匯編語(yǔ)言的實(shí)踐啟發(fā)人們，表達(dá)成機(jī)器語(yǔ)言不必一步到位，可以分兩步走或者可以筑橋過(guò)河。即先表達(dá)成一種中介語(yǔ)言，然后轉(zhuǎn)成機(jī)器語(yǔ)言。匯編語(yǔ)言作為一種中介語(yǔ)言，并沒(méi)有獲得很大成功，原因是它離算法語(yǔ)言還太遠(yuǎn)。這便指引人們?nèi)ピO(shè)計(jì)一種盡量接近算法語(yǔ)言的規(guī)范語(yǔ)言，即所謂的高級(jí)語(yǔ)言，讓程序員可以用它方便地表達(dá)算法，然后借助于規(guī)范的高級(jí)語(yǔ)言到規(guī)范的機(jī)器語(yǔ)言的"翻譯"，最終將算法表達(dá)為機(jī)器語(yǔ)言。而且，由于高級(jí)語(yǔ)言和機(jī)器語(yǔ)言都具有規(guī)范性，這里的"翻譯"完全可以機(jī)械化地由計(jì)算機(jī)來(lái)完成，就像匯編語(yǔ)言被翻譯成機(jī)器語(yǔ)言一樣，只要計(jì)算機(jī)配上一個(gè)編譯程序。

上述兩步，前一步由程序員去完成，后一步可以由編譯程序去完成。在規(guī)定清楚它們各自該做什么之后，這兩步是完全獨(dú)立的。它們各自該如何做互不相干。前一步要做的只是用高級(jí)語(yǔ)言正確地表達(dá)給定的算法，產(chǎn)生一個(gè)高級(jí)語(yǔ)言程序;后一步要做的只是將第一步得到的高級(jí)語(yǔ)言程序翻譯成機(jī)器語(yǔ)言程序。至于程序員如何用高級(jí)語(yǔ)言表達(dá)算法和編譯程序如何將高級(jí)語(yǔ)言表達(dá)的算法翻譯成機(jī)器語(yǔ)言表達(dá)的算法，顯然毫不相干。

處理從算法語(yǔ)言最終表達(dá)成機(jī)器語(yǔ)言這一復(fù)雜過(guò)程的上述思想方法就是一種抽象。匯編語(yǔ)言和高級(jí)語(yǔ)言的出現(xiàn)都是這種抽象的范例。

與匯編語(yǔ)言相比，高級(jí)語(yǔ)言的巨大成功在于它在數(shù)據(jù)、運(yùn)算和控制三方面的表達(dá)中引入許多接近算法語(yǔ)言的概念和工具，大大地提高抽象地表達(dá)算法的能力。

在運(yùn)算方面，高級(jí)語(yǔ)言如Pascal，除允許原封不動(dòng)地運(yùn)用算法語(yǔ)言的四則運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、算術(shù)表達(dá)式、邏輯表達(dá)式外，還引入強(qiáng)有力的函數(shù)與過(guò)程的工具，并讓用戶自定義。這一工具的重要性不僅在于它精簡(jiǎn)了重復(fù)的程序文本段，而且在于它反映出程序的兩級(jí)抽象。在函數(shù)與過(guò)程調(diào)用級(jí)，人們只關(guān)心它能做什么，不必關(guān)心它如何做。只是到函數(shù)與過(guò)程的定義時(shí)，人們才給出如何做的細(xì)節(jié)。用過(guò)高級(jí)語(yǔ)言的讀者都知道，一旦函數(shù)與過(guò)程的名稱、參數(shù)和功能被規(guī)定清楚，那么，在程序中調(diào)用它們便與在程序的頭部說(shuō)明它們完全分開(kāi)。你可以修改甚至更換函數(shù)體與過(guò)程體，而不影響它們的被調(diào)用。如果把函數(shù)與過(guò)程名看成是運(yùn)算名，把參數(shù)看成是運(yùn)算的對(duì)象或運(yùn)算的結(jié)果，那么，函數(shù)與過(guò)程的調(diào)用和初等運(yùn)算的引用沒(méi)有兩樣。利用函數(shù)和過(guò)程以及它們的復(fù)合或嵌套可以很自然地表達(dá)算法語(yǔ)言中任何復(fù)雜的運(yùn)算。

在數(shù)據(jù)方面，高級(jí)語(yǔ)言如Pascal引人了數(shù)據(jù)類型的概念，即把所有的數(shù)據(jù)加以分類。每一個(gè)數(shù)據(jù)(包括表達(dá)式)或每一個(gè)數(shù)據(jù)變量都屬于其中確定的一類。稱這一類數(shù)據(jù)為一個(gè)數(shù)據(jù)類型。 因此，數(shù)據(jù)類型是數(shù)據(jù)或數(shù)據(jù)變量類屬的說(shuō)明，它指示該數(shù)據(jù)或數(shù)據(jù)變量可能取的值的全體。對(duì)于無(wú)結(jié)構(gòu)的數(shù)據(jù)，高級(jí)語(yǔ)言如Pascal，除提供標(biāo)準(zhǔn)的基本數(shù)據(jù)類型--布爾型、字符型、整型和實(shí)型外，還提供用戶可自定義的枚舉類型、子界類型和指針類型。這些類型(除指針外)，其使用方式都順應(yīng)人們?cè)谒惴ㄕZ(yǔ)言中使用的習(xí)慣。對(duì)于有結(jié)構(gòu)的數(shù)據(jù)，高級(jí)語(yǔ)言如Pascal，提供了數(shù)組、記錄、有限制的集合和文件等四種標(biāo)準(zhǔn)的結(jié)構(gòu)數(shù)據(jù)類型。其中，數(shù)組是科學(xué)計(jì)算中的向量、矩陣的抽象;記錄是商業(yè)和管理中的記錄的抽象;有限制的集合是數(shù)學(xué)中足夠小的集合的勢(shì)集的抽象;文件是諸如磁盤(pán)等外存儲(chǔ)數(shù)據(jù)的抽象。人們可以利用所提供的基本數(shù)據(jù)類型(包括標(biāo)準(zhǔn)的和自定義的)，按數(shù)組、記錄、有限制的集合和文件的構(gòu)造規(guī)則構(gòu)造有結(jié)構(gòu)的數(shù)據(jù)。 此外，還允許用戶利用標(biāo)準(zhǔn)的結(jié)構(gòu)數(shù)據(jù)類型，通過(guò)復(fù)合或嵌套構(gòu)造更復(fù)雜更高層的結(jié)構(gòu)數(shù)據(jù)。這使得高級(jí)語(yǔ)言中的數(shù)據(jù)類型呈明顯的分層，如圖1-6所示。

高級(jí)語(yǔ)言中數(shù)據(jù)類型的分層是沒(méi)有窮盡的，因而用它們可以表達(dá)算法語(yǔ)言中任何復(fù)雜層次的數(shù)據(jù)。

在控制方面，高級(jí)語(yǔ)言如Pascal，提供了表達(dá)算法控制轉(zhuǎn)移的六種方式。

(1)缺省的順序控制";"。

(2)條件(分支)控制:"if表達(dá)式(為真)then S1 else S2;" 。

(3)選擇(情況)控制:

"Case 表達(dá)式 of

值1: S1

值2: S2

...

值n: Sn

end"

(4)循環(huán)控制:

"while 表達(dá)式(為真) do S;" 或

"repeat S until 表達(dá)式(為真);" 或

"for變量名:=初值 to/downto 終值do S;"

(5)函數(shù)和過(guò)程的調(diào)用，包括遞歸函數(shù)和遞歸過(guò)程的調(diào)用。

(6)無(wú)條件轉(zhuǎn)移goto。

這六種表達(dá)方式不僅覆蓋了算法語(yǔ)言中所有控制表達(dá)的要求，而且不再像機(jī)器語(yǔ)言或匯編語(yǔ)言那樣原始、那樣繁瑣、那樣隱晦，而是如上面所看到的，與自然語(yǔ)言的表達(dá)相差無(wú)幾。

程序設(shè)計(jì)語(yǔ)言從機(jī)器語(yǔ)言到高級(jí)語(yǔ)言的抽象，帶來(lái)的主要好處是：

1. 高級(jí)語(yǔ)言接近算法語(yǔ)言，易學(xué)、易掌握，一般工程技術(shù)人員只要幾周時(shí)間的培訓(xùn)就可以勝任程序員的工作；
2. 高級(jí)語(yǔ)言為程序員提供了結(jié)構(gòu)化程序設(shè)計(jì)的環(huán)境和工具，使得設(shè)計(jì)出來(lái)的程序可讀性好，可維護(hù)性強(qiáng)，可靠性高；
3. 高級(jí)語(yǔ)言遠(yuǎn)離機(jī)器語(yǔ)言，與具體的計(jì)算機(jī)硬件關(guān)系不大，因而所寫(xiě)出來(lái)的程序可移植性好，重用率高；
4. 由于把繁雜瑣碎的事務(wù)交給了編譯程序去做，所以自動(dòng)化程度高，開(kāi)發(fā)周期短，且程序員得到解脫，可以集中時(shí)間和精力去從事對(duì)于他們來(lái)說(shuō)更為重要的創(chuàng)造性勞動(dòng)，以提高程序的質(zhì)量。