|
算法表達中的抽象機制(一） 簡介 要用計算機解決一個稍為復(fù)雜的實際問題，大體都要經(jīng)歷如下的步驟。
在這里，我們只關(guān)心第3步，而且把注意力集中在算法程序表達的抽象機制上，目的是引人一個重要的概念--抽象數(shù)據(jù)類型，同時為大型程序設(shè)計提供一種相應(yīng)的自頂向下逐步求精、模塊化的具體方法，即運用抽象數(shù)據(jù)類型來描述程序的方法。
從機器語言到高級語言的抽象
我們知道，算法被定義為一個運算序列。這個運算序列中的所有運算定義在一類特定的數(shù)據(jù)模型上，并以解決一類特定問題為目標。這個運算序列應(yīng)該具備下列四個特征。
這些特征可以用來判別一個確定的運算序列是否稱得上是一個算法。 但是，我們現(xiàn)在的問題不是要判別一個確定的運算序列是否稱得上是一個算法，而是要對一個己經(jīng)稱得上是算法的運算序列，回顧我們曾經(jīng)如何用程序設(shè)計語言去表達它。 算法的程序表達，歸根到底是算法要素的程序表達，因為一旦算法的每一項要素都用程序清楚地表達，整個算法的程序表達也就不成問題。 作為運算序列的算法，有三個要素。
這三種要素依序分別簡稱為數(shù)據(jù)、運算和控制。 由于算法層出不窮，變化萬千，其中的運算所作用的對象數(shù)據(jù)和所得到的結(jié)果數(shù)據(jù)名目繁多，不勝枚舉。最簡單最基本的有布爾值數(shù)據(jù)、字符數(shù)據(jù)、整數(shù)和實數(shù)數(shù)據(jù)等;稍復(fù)雜的有向量、矩陣、記錄等數(shù)據(jù);更復(fù)雜的有集合、樹和圖，還有聲音、圖形、圖像等數(shù)據(jù)。 同樣由于算法層出不窮，變化萬千，其中運算的種類五花八門、多姿多彩。最基本最初等的有賦值運算、算術(shù)運算、邏輯運算和關(guān)系運算等;稍復(fù)雜的有算術(shù)表達式和邏輯表達式等;更復(fù)雜的有函數(shù)值計算、向量運算、矩陣運算、集合運算，以及表、棧、隊列、樹和圖上的運算等:此外，還可能有以上列舉的運算的復(fù)合和嵌套。 關(guān)于控制轉(zhuǎn)移，相對單純。在串行計算中，它只有順序、分支、循環(huán)、遞歸和無條件轉(zhuǎn)移等幾種。 我們來回顧一下，自從計算機問世以來，算法的上述三要素的程序表達，經(jīng)歷過一個怎樣的過程。 最早的程序設(shè)計語言是機器語言，即具體的計算機上的一個指令集。當時，要在計算機上運行的所有算法都必須直接用機器語言來表達，計算機才能接受。算法的運算序列包括運算對象和運算結(jié)果都必須轉(zhuǎn)換為指令序列。其中的每一條指令都以編碼(指令碼和地址碼)的形式出現(xiàn)。與算法語言表達的算法，相差十萬八千里。對于沒受過程序設(shè)計專門訓(xùn)練的人來說，一份程序恰似一份"天書"，讓人看了不知所云，可讀性極差。 用機器語言表達算法的運算、數(shù)據(jù)和控制十分繁雜瑣碎，因為機器語言所提供的指令太初等、原始。機器語言只接受算術(shù)運算、按位邏輯運算和數(shù)的大小比較運算等。對于稍復(fù)雜的運算，都必須一一分解，直到到達最初等的運算才能用相應(yīng)的指令替代之。機器語言能直接表達的數(shù)據(jù)只有最原始的位、字節(jié)、和字三種。算法中即使是最簡單的數(shù)據(jù)如布爾值、字符、整數(shù)、和實數(shù)，也必須一一地映射到位、字節(jié)和字中，還得一一分配它們的存儲單元。對于算法中有結(jié)構(gòu)的數(shù)據(jù)的表達則要麻煩得多。機器語言所提供的控制轉(zhuǎn)移指令也只有無條件轉(zhuǎn)移、條件轉(zhuǎn)移、進入子程序和從子程序返回等最基本的幾種。用它們來構(gòu)造循環(huán)、形成分支、調(diào)用函數(shù)和過程得事先做許多的準備，還得靠許多的技巧。 直接用機器語言表達算法有許多缺點。
這些弊端造成當時的計算機應(yīng)用未能迅速得到推廣。 克服上述缺點的出路在于程序設(shè)計語言的抽象，讓它盡可能地接近于算法語言。 為此，人們首先注意到的是可讀性和可移植性，因為它們相對地容易通過抽象而得到改善。于是，很快就出現(xiàn)匯編語言。這種語言對機器語言的抽象，首先表現(xiàn)在將機器語言的每一條指令符號化:指令碼代之以記憶符號，地址碼代之以符號地址，使得其含義顯現(xiàn)在符號上而不再隱藏在編碼中，可讓人望"文"生義。其次表現(xiàn)在這種語言擺脫了具體計算機的限制，可在不同指令集的計算機上運行，只要該計算機配上匯編語言的一個匯編程序。這無疑是機器語言朝算法語言靠攏邁出的一步。但是，它離算法語言還太遠，以致程序員還不能從分解算法的數(shù)據(jù)、運算和控制到匯編才能直接表達的指令等繁雜瑣碎的事務(wù)中解脫出來。 到了50年代中期，出現(xiàn)程序設(shè)計的高級語言如Fortran，Algol60，以及后來的PL/l，Pascal等，算法的程序表達才產(chǎn)生一次大的飛躍。 誠然，算法最終要表達為具體計算機上的機器語言才能在該計算機上運行，得到所需要的結(jié)果。但匯編語言的實踐啟發(fā)人們，表達成機器語言不必一步到位，可以分兩步走或者可以筑橋過河。即先表達成一種中介語言，然后轉(zhuǎn)成機器語言。匯編語言作為一種中介語言，并沒有獲得很大成功，原因是它離算法語言還太遠。這便指引人們?nèi)ピO(shè)計一種盡量接近算法語言的規(guī)范語言，即所謂的高級語言，讓程序員可以用它方便地表達算法，然后借助于規(guī)范的高級語言到規(guī)范的機器語言的"翻譯"，最終將算法表達為機器語言。而且，由于高級語言和機器語言都具有規(guī)范性，這里的"翻譯"完全可以機械化地由計算機來完成，就像匯編語言被翻譯成機器語言一樣，只要計算機配上一個編譯程序。 上述兩步，前一步由程序員去完成，后一步可以由編譯程序去完成。在規(guī)定清楚它們各自該做什么之后，這兩步是完全獨立的。它們各自該如何做互不相干。前一步要做的只是用高級語言正確地表達給定的算法，產(chǎn)生一個高級語言程序;后一步要做的只是將第一步得到的高級語言程序翻譯成機器語言程序。至于程序員如何用高級語言表達算法和編譯程序如何將高級語言表達的算法翻譯成機器語言表達的算法，顯然毫不相干。 處理從算法語言最終表達成機器語言這一復(fù)雜過程的上述思想方法就是一種抽象。匯編語言和高級語言的出現(xiàn)都是這種抽象的范例。 與匯編語言相比，高級語言的巨大成功在于它在數(shù)據(jù)、運算和控制三方面的表達中引入許多接近算法語言的概念和工具，大大地提高抽象地表達算法的能力。 在運算方面，高級語言如Pascal，除允許原封不動地運用算法語言的四則運算、邏輯運算、關(guān)系運算、算術(shù)表達式、邏輯表達式外，還引入強有力的函數(shù)與過程的工具，并讓用戶自定義。這一工具的重要性不僅在于它精簡了重復(fù)的程序文本段，而且在于它反映出程序的兩級抽象。在函數(shù)與過程調(diào)用級，人們只關(guān)心它能做什么，不必關(guān)心它如何做。只是到函數(shù)與過程的定義時，人們才給出如何做的細節(jié)。用過高級語言的讀者都知道，一旦函數(shù)與過程的名稱、參數(shù)和功能被規(guī)定清楚，那么，在程序中調(diào)用它們便與在程序的頭部說明它們完全分開。你可以修改甚至更換函數(shù)體與過程體，而不影響它們的被調(diào)用。如果把函數(shù)與過程名看成是運算名，把參數(shù)看成是運算的對象或運算的結(jié)果，那么，函數(shù)與過程的調(diào)用和初等運算的引用沒有兩樣。利用函數(shù)和過程以及它們的復(fù)合或嵌套可以很自然地表達算法語言中任何復(fù)雜的運算。 在數(shù)據(jù)方面，高級語言如Pascal引人了數(shù)據(jù)類型的概念，即把所有的數(shù)據(jù)加以分類。每一個數(shù)據(jù)(包括表達式)或每一個數(shù)據(jù)變量都屬于其中確定的一類。稱這一類數(shù)據(jù)為一個數(shù)據(jù)類型。 因此，數(shù)據(jù)類型是數(shù)據(jù)或數(shù)據(jù)變量類屬的說明，它指示該數(shù)據(jù)或數(shù)據(jù)變量可能取的值的全體。對于無結(jié)構(gòu)的數(shù)據(jù)，高級語言如Pascal，除提供標準的基本數(shù)據(jù)類型--布爾型、字符型、整型和實型外，還提供用戶可自定義的枚舉類型、子界類型和指針類型。這些類型(除指針外)，其使用方式都順應(yīng)人們在算法語言中使用的習(xí)慣。對于有結(jié)構(gòu)的數(shù)據(jù)，高級語言如Pascal，提供了數(shù)組、記錄、有限制的集合和文件等四種標準的結(jié)構(gòu)數(shù)據(jù)類型。其中，數(shù)組是科學(xué)計算中的向量、矩陣的抽象;記錄是商業(yè)和管理中的記錄的抽象;有限制的集合是數(shù)學(xué)中足夠小的集合的勢集的抽象;文件是諸如磁盤等外存儲數(shù)據(jù)的抽象。人們可以利用所提供的基本數(shù)據(jù)類型(包括標準的和自定義的)，按數(shù)組、記錄、有限制的集合和文件的構(gòu)造規(guī)則構(gòu)造有結(jié)構(gòu)的數(shù)據(jù)。 此外，還允許用戶利用標準的結(jié)構(gòu)數(shù)據(jù)類型，通過復(fù)合或嵌套構(gòu)造更復(fù)雜更高層的結(jié)構(gòu)數(shù)據(jù)。這使得高級語言中的數(shù)據(jù)類型呈明顯的分層，如圖1-6所示。
高級語言中數(shù)據(jù)類型的分層是沒有窮盡的，因而用它們可以表達算法語言中任何復(fù)雜層次的數(shù)據(jù)。 在控制方面，高級語言如Pascal，提供了表達算法控制轉(zhuǎn)移的六種方式。 (1)缺省的順序控制";"。 (2)條件(分支)控制:"if表達式(為真)then S1 else S2;" 。 (3)選擇(情況)控制: "Case 表達式 of 值1: S1 值2: S2 ... 值n: Sn end" (4)循環(huán)控制: "while 表達式(為真) do S;" 或 "repeat S until 表達式(為真);" 或 "for變量名:=初值 to/downto 終值do S;" (5)函數(shù)和過程的調(diào)用，包括遞歸函數(shù)和遞歸過程的調(diào)用。 (6)無條件轉(zhuǎn)移goto。 這六種表達方式不僅覆蓋了算法語言中所有控制表達的要求，而且不再像機器語言或匯編語言那樣原始、那樣繁瑣、那樣隱晦，而是如上面所看到的，與自然語言的表達相差無幾。 程序設(shè)計語言從機器語言到高級語言的抽象，帶來的主要好處是：
|
|
|
