抽象數(shù)據(jù)類型

與機器語言、匯編語言相比，高級語言的出現(xiàn)大大地簡便了程序設計。但算法從非形式的自然語言表達到形式化的高級語言表達，仍然是一個復雜的過程，仍然要做很多繁雜瑣碎的事情，因而仍然需要抽象。

對于一個明確的數(shù)學問題，設計它的算法，總是先選用該問題的一個數(shù)據(jù)模型。接著，弄清該問題所選用的數(shù)據(jù)模型在已知條件下的初始狀態(tài)和要求的結果狀態(tài)，以及隱含著的兩個狀態(tài)之間的關系。然后探索從數(shù)據(jù)模型的已知初始狀態(tài)出發(fā)到達要求的結果狀態(tài)所必需的運算步驟。把這些運算步驟記錄下來，就是該問題的求解算法。

按照自頂向下逐步求精的原則，我們在探索運算步驟時，首先應該考慮算法頂層的運算步驟，然后再考慮底層的運算步驟。所謂頂層的運算步驟是指定義在數(shù)據(jù)模型級上的運算步驟，或叫宏觀運算。它們組成算法的主干部分。表達這部分算法的程序就是主程序。其中涉及的數(shù)據(jù)是數(shù)據(jù)模型中的一個變量，暫時不關心它的數(shù)據(jù)結構;涉及的運算以數(shù)據(jù)模型中的數(shù)據(jù)變量作為運算對象，或作為運算結果，或二者兼而為之，簡稱為定義在數(shù)據(jù)模型上的運算。由于暫時不關心變量的數(shù)據(jù)結構，這些運算都帶有抽象性質(zhì)，不含運算的細節(jié)。所謂底層的運算步驟是指頂層抽象的運算的具體實現(xiàn)。它們依賴于數(shù)據(jù)模型的結構，依賴于數(shù)據(jù)模型結構的具體表示。因此，底層的運算步驟包括兩部分:一是數(shù)據(jù)模型的具體表示;二是定義在該數(shù)據(jù)模型上的運算的具體實現(xiàn)。我們可以把它們理解為微觀運算。于是，底層運算是頂層運算的細化;底層運算為頂層運算服務。為了將頂層算法與底層算法隔開，使二者在設計時不會互相牽制、互相影響，必須對二者的接口進行一次抽象。讓底層只通過這個接口為頂層服務，頂層也只通過這個接口調(diào)用底層的運算。這個接口就是抽象數(shù)據(jù)類型。其英文術語是Abstract Data Types，簡記ADT。

抽象數(shù)據(jù)類型是算法設計和程序設計中的重要概念。嚴格地說，它是算法的一個數(shù)據(jù)模型連同定義在該模型上、作為該算法構件的一組運算。這個概念明確地把數(shù)據(jù)模型與作用在該模型上的運算緊密地聯(lián)系起來。事實正是如此。一方面，如前面指出過的，數(shù)據(jù)模型上的運算依賴于數(shù)據(jù)模型的具體表示，因為數(shù)據(jù)模型上的運算以數(shù)據(jù)模型中的數(shù)據(jù)變量作為運算對象，或作為運算結果，或二者兼而為之;另方面，有了數(shù)據(jù)模型的具體表示，有了數(shù)據(jù)模型上運算的具體實現(xiàn)，運算的效率隨之確定。于是，就有這樣的一個問題:如何選擇數(shù)據(jù)模型的具體表示使該模型上的各種運算的效率都盡可能地高?很明顯，對于不同的運算組，為使組中所有運算的效率都盡可能地高，其相應的數(shù)據(jù)模型具體表示的選擇將是不同的。在這個意義下，數(shù)據(jù)模型的具體表示又反過來依賴于數(shù)據(jù)模型上定義的那些運算。特別是，當不同運算的效率互相制約時，還必須事先將所有的運算的相應使用頻度排序，讓所選擇的數(shù)據(jù)模型的具體表示優(yōu)先保證使用頻度較高的運算有較高的效率。數(shù)據(jù)模型與定義在該模型上的運算之間存在著的這種密不可分的聯(lián)系，是抽象數(shù)據(jù)類型的概念產(chǎn)生的背景和依據(jù)。

應該指出，抽象數(shù)據(jù)類型的概念并不是全新的概念。它實際上是我們熟悉的基本數(shù)據(jù)類型概念的引伸和發(fā)展。用過高級語言進行算法設計和程序設計的人都知道，基本數(shù)據(jù)類型已隱含著數(shù)據(jù)模型和定義在該模型上的運算的統(tǒng)一，只是當時還沒有形成抽象數(shù)據(jù)類型的概念罷了。事實上，大家都清楚，基本數(shù)據(jù)類型中的邏輯類型就是邏輯值數(shù)據(jù)模型和或(∨)、與(∧)、非(┐)三種邏輯運算的統(tǒng)一體；整數(shù)類型就是整數(shù)值數(shù)據(jù)模型和加(+)、減(-)、乘(*)、除(div)四種運算的統(tǒng)一體；實型和字符型等也類同。每一種基本類型都連帶著一組基本運算。只是由于這些基本數(shù)據(jù)類型中的數(shù)據(jù)模型的具體表示和基本運算的具體實現(xiàn)都很規(guī)范，都可以通過內(nèi)置(built-in)而隱蔽起來，使人們看不到它們的封裝。許多人已習慣于在算法與程序設計中用基本數(shù)據(jù)類型名和相關的運算名，而不問其究竟。所以沒有意識到抽象數(shù)據(jù)類型的概念已經(jīng)孕育在基本數(shù)據(jù)類型的概念之中。

回到定義算法的頂層和底層的接口，即定義抽象數(shù)據(jù)類型。根據(jù)抽象數(shù)據(jù)類型的概念，對抽象數(shù)據(jù)類型進行定義就是約定抽象數(shù)據(jù)類型的名字，同時，約定在該類型上定義的一組運算的各個運算的名字，明確各個運算分別要有多少個參數(shù)，這些參數(shù)的含義和順序，以及運算的功能。一旦定義清楚，算法的頂層就可以像引用基本數(shù)據(jù)類型那樣，十分簡便地引用抽象數(shù)據(jù)類型;同時，算法的底層就有了設計的依據(jù)和目標。頂層和底層都與抽象數(shù)據(jù)類型的定義打交道。頂層運算和底層運算沒有直接的聯(lián)系。因此，只要嚴格按照定義辦，頂層算法的設計和底層算法的設計就可以互相獨立，互不影響，實現(xiàn)對它們的隔離，達到抽象的目的。

在定義了抽象數(shù)據(jù)類型之后，算法底層的設計任務就可以明確為:

1. 賦每一個抽象數(shù)據(jù)類型名予具體的構造數(shù)據(jù)類型，或者說，賦每一個抽象數(shù)據(jù)類型名予具體的數(shù)據(jù)結構;
2. 賦每一個抽象數(shù)據(jù)類型上的每個運算名予具體的運算內(nèi)容，或者說，賦予具體的過程或函數(shù)。

因此，落實下來，算法底層的設計就是數(shù)據(jù)結構的設計和過程與函數(shù)的設計。用高級語言表達，就是構造數(shù)據(jù)類型的定義和過程與函數(shù)的說明。

不言而喻，由于實際問題千奇百怪，數(shù)據(jù)模型千姿百態(tài)，問題求解的算法千變?nèi)f化，抽象數(shù)據(jù)類型的設計和實現(xiàn)不可能像基本數(shù)據(jù)類型那樣可以規(guī)范、內(nèi)置、一勞永逸。它要求算法設計和程序設計人員因時因地制宜，自行籌劃，目標是使抽象數(shù)據(jù)類型對外的整體效率盡可能地高。

下面用一個例子來說明，對于一個具體的問題，抽象數(shù)據(jù)類型是如何定義的。

考慮拓撲排序問題:已知一個集合S={a₁,a₂, ... ,a_m}，S上已規(guī)定了一個部分序<。要求給出S的一個線性序{a₁‘,a₂‘, ... ,a_m‘}，即S的一個重排，使得對于任意的1<=j<k<=m，不得有a_k‘<a_j‘。這里所謂S上的部分序<，是指S上的一種序關系，它對于S中的任意元素x,y和z，具有如下三個性質(zhì):

1. 不得有x<x；(反自反性）
2. 若x<y，則不得有y<x；（反對稱性）
3. 若x<y，,且y<z，則x<z；(傳遞性)。

其中x<y讀作x先于y,或等價地讀作x是y的前驅(qū)，或y是x是后繼。

由于已知的S上的部分序<可以用一個有向圖G來表示，而要求的S的線性序可以用一個隊列Q來表示，所以問題的數(shù)據(jù)模型包括一類有向圖和一類隊列。我們將其分別取名為Digraph和Queue。其中G=G(V，E)是Digraph中的一個有向圖，結點集V=S，有向邊集E是由<決定的S的元素間的有向連線的全體;Q=S={a₁,a₂, ... ,a_m}是Queue中的一個隊列。在G中，a_i和a_j之間有一條起于a_i止于a_j的有向連線的充分必要條件是a_i<a_j。具體地說，比如S={a₁，a₂, ... ,a₁₀}，而<如表1-3所示，則G(V,E)如圖1-7，而Q={a₇，a₉，a₁，a₂，a₄，a₆，a₃，a₅，a₈，a₁₀}。這個Q只是問題的一個解。顯然問題的解不唯一，容易舉出Q‘={a₁，a₂，a₇,a₉，a₁₀，a₄，a₆，a₃，a₅，a₈}是另一個解。

表1-3 S={a₁,a_2,...,a₁₀}中的部分序

在數(shù)據(jù)模型Digraph和Queue的基礎上，容易擬定出算法高層的宏觀運算步驟，我們稱之為算法的主干部分，并用非形式的自然語言表述如下：

1.φ->Q;

2.檢測G。

(1)當G≠φ時;

①在G中出任意一個無前驅(qū)的結點，記為a；

②將a加到Q的末尾;

③在G中刪去結點a以及以a為起點的所有有向邊;

④轉(zhuǎn)向2。

(2)當C=φ時，算法結束，問題的解在Q中。

用高級語言中的控制結構語句成分，替換上述主干算法中自然語言的控制轉(zhuǎn)移術語，則主干算法可用自然語言和高級語言的混合語言改述如下:

φ->Q;
while G≠φ do
begin
a:=G中任意一個無前驅(qū)的頂點;
將a加到Q的末尾; 從G中刪去結點a以及以a為起點的所有有向邊;
end;

我們看到，其中那些還未能用高級語言表達的語句或語句成分，正是算法需要定義在數(shù)據(jù) 模型Digraph和Queue上的運算?，F(xiàn)分別將它們列出。

對于Digraph中的G:

1. 檢測G是否非空圖;
2. 在G中找任意一個無前驅(qū)的結點;
3. 在G中刪去一個無前驅(qū)的結點，以及以該結點為起點的所有有向邊。

對于Queue中的Q:

1. 初始化Q為空隊列;
2. 將一個結點加到Q的末尾。

如果還考慮到已知G的初始狀態(tài)如何由輸入形成和Q的結果狀態(tài)的輸出，那么，對于Digraph和Queue還需要補充定義若干有關的運算。為了簡單，這里從略。

由于高級語言為抽象數(shù)據(jù)類型的定義提供了很好的環(huán)境和工具，再復雜的數(shù)據(jù)模型都可 以通過構造數(shù)據(jù)類型來表達，再復雜的運算都可以借助過程或函數(shù)來描述。因此，上述由數(shù)據(jù)模型和數(shù)據(jù)模型上定義的運算綜合起來的抽象數(shù)據(jù)類型很容易用高級語言來定義。

對于抽象數(shù)據(jù)類型mgraph，定義如下三個運算:

(l)function G_empty(G:Digraph):boolean;

{檢測圖G是否非空。如果G=φ，則函數(shù)返回true，否則返回false}

(2)function G_front(G:Digraph):nodetype；

{在有向圖G中找一個無前驅(qū)的結點。nodetype是結點類型名，它有待用戶定義，下同}

(3)Procedure delete_G_front(var G:Digraph;a:nodetype);

{在G中刪去結點a以及以a為起點的所有有向邊}

對抽象數(shù)據(jù)類型Queue，定義如下兩個運算:

(l)Procedure init_Q(var Q:Queue); {初始化隊列Q為空隊列}

(2)Procedure add_Q_rear(a:nodetype;var Q:Queue) {將結點a加到隊列Q的末尾}

這樣，我們便定義了ADT Digraph和ADT Queue。

有了抽象數(shù)據(jù)類型Digraph和Queue的上述定義，拓撲排序問題的主干算法即可完全由高級語言表達成主程序。

Program topsort(input，ouput);
type
nodetype=…
Digraph=…
Queue=…
Function G_empty(G:Digraph):boolean;
...
Function G_front(G:Dlgraph):nodetype;
...
Procedure delete_G_front(var G:Digraph;a:nodetype);
...
Procedure init_Q(var Q:Queue);
...
Procedure add_Q_rear(a:nodetype;var Q:Queue);
...
var
a:nodetype;
G:Digraph;
Q:Queue;
begin
…       {輸入并形成G的初始狀態(tài)即拓撲排序前的狀態(tài)}
init_Q(Q);
while not G_empty(G) do
begin
a:=G_front(G);
add_Q_rear(a，Q);
delete_G_front(G，a);
end;
…
{輸出Q中的結果}
end;

為了簡明，我們在其中略去了輸入、拓撲排序前G的狀態(tài)的形成和結果輸出三個部分。至于構造數(shù)據(jù)類型nodetype，Digraph和Queue的表示，函數(shù)G_empty，G_front，過程delete_G_front，init_Q和add_Q_rear等的實現(xiàn)，則留待算法的底層設計去完成。需要指出的是，nodetype通常用記錄表示，而Digraph和Queue都有多種表示方式。因而G_empty，G_front，delete_G_front，init_Q和add_Q_rear也有多種的實現(xiàn)方式。

但是，只要抽象數(shù)據(jù)類型Digraph和Queue的定義不變，不管上述構造數(shù)據(jù)類型的表示和過程與函數(shù)的實現(xiàn)如何改變，主程序的表達都不會改變;反過來，不管主程序在哪里調(diào)用抽象數(shù)據(jù)類型上的函數(shù)或過程，上述構造數(shù)據(jù)類型的表示和過程與函數(shù)的實現(xiàn)都不必改變。算法頂層的設計與底層的設計之間的這種獨立性，顯然得益于抽象數(shù)據(jù)類型的引人。而這種獨立性給算法和程序設計帶來了許多好處。

使用抽象數(shù)據(jù)類型帶來的好處

使用抽象數(shù)據(jù)類型將給算法和程序設計帶來很多好處，其中主要的有下面幾條。

1. 算法頂層的設計與底層的設計被隔開，使得在進行頂層設計時不必考慮它所用到的數(shù)據(jù)和運算分別如何表示和實現(xiàn);反過來，在進行數(shù)據(jù)表示和運算實現(xiàn)等底層設計時，只要抽象數(shù)據(jù)類型定義清楚，也不必考慮它在什么場合被引用。這樣做，算法和程序設計的復雜性降低了，條理性增強了。既有助于迅速開發(fā)出程序的原型，又有助于在開發(fā)過程中少出差錯，保證編出的程序有較高的可靠性。
2. 算法設計與數(shù)據(jù)結構設計隔開，允許數(shù)據(jù)結構自由選擇，從中比較，可優(yōu)化算法和提高程序運行的效率。
3. 數(shù)據(jù)模型和該模型上的運算統(tǒng)一一在抽象數(shù)據(jù)類型中，反映了它們之間內(nèi)在的互相依賴和互相制約的關系，便于空間和時間耗費的折衷，滿足用戶的要求。
4. 由于頂層設計和底層設計被局部化，在設計中，如果出現(xiàn)差錯，將是局部的，因而容易查我也容易糾正。在設計中常常要做的增、刪、改也都是局部的，因而也都很容易進行。因此，可以肯定，用抽象數(shù)據(jù)類型表述的程序具有很好的可維護性。
5. 編出來的程序自然地呈現(xiàn)模塊化，而且，抽象的數(shù)據(jù)類型的表示和實現(xiàn)都可以封裝起來，便于移植和重用。
6. 為自頂向下逐步求精和模塊化提供一種有效的途徑和工具。
7. 編出來的程序結構清晰，層次分明，便于程序正確性的證明和復雜性的分析。

數(shù)據(jù)結構、數(shù)據(jù)類型和抽象數(shù)據(jù)類型

數(shù)據(jù)結構、數(shù)據(jù)類型和抽象數(shù)據(jù)類型，這三個術語在字面上既不同又相近，反映出它們在含義上既有區(qū)別又有聯(lián)系。

數(shù)據(jù)結構是在整個計算機科學與技術領域上廣泛被使用的術語。它用來反映一個數(shù)據(jù)的內(nèi)部構成，即一個數(shù)據(jù)由哪些成分數(shù)據(jù)構成，以什么方式構成，呈什么結構。數(shù)據(jù)結構有邏輯上的數(shù)據(jù)結構和物理上的數(shù)據(jù)結構之分。邏輯上的數(shù)據(jù)結構反映成分數(shù)據(jù)之間的邏輯關系，物理上的數(shù)據(jù)結構反映成分數(shù)據(jù)在計算機內(nèi)的存儲安排。數(shù)據(jù)結構是數(shù)據(jù)存在的形式。

數(shù)據(jù)是按照數(shù)據(jù)結構分類的，具有相同數(shù)據(jù)結構的數(shù)據(jù)屬同一類。同一類數(shù)據(jù)的全體稱為一個數(shù)據(jù)類型。在程序設計高級語言中，數(shù)據(jù)類型用來說明一個數(shù)據(jù)在數(shù)據(jù)分類中的歸屬。它是數(shù)據(jù)的一種屬性。這個屬性限定了該數(shù)據(jù)的變化范圍。為了解題的需要，根據(jù)數(shù)據(jù)結構的種類，高級語言定義了一系列的數(shù)據(jù)類型。不同的高級語言所定義的數(shù)據(jù)類型不盡相同。Pascal語言所定義的數(shù)據(jù)類型的種類如圖1-8所示。

其中，簡單數(shù)據(jù)類型對應于簡單的數(shù)據(jù)結構;構造數(shù)據(jù)類型對應于復雜的數(shù)據(jù)結構;在復雜的數(shù)據(jù)結構里，允許成分數(shù)據(jù)本身具有復雜的數(shù)據(jù)結構，因而，構造數(shù)據(jù)類型允許復合嵌套;指針類型對應于數(shù)據(jù)結構中成分數(shù)據(jù)之間的關系，表面上屬簡單數(shù)據(jù)類型，實際上都指向復雜的成分數(shù)據(jù)即構造數(shù)據(jù)類型中的數(shù)據(jù)，因此這里沒有把它劃入簡單數(shù)據(jù)類型，也沒有劃入構造數(shù)據(jù)類型，而單獨劃出一類。

數(shù)據(jù)結構反映數(shù)據(jù)內(nèi)部的構成方式，它常常用一個結構圖來描述:數(shù)據(jù)中的每一項成分數(shù)據(jù)被看作一個結點，并用方框或圓圈表示，成分數(shù)據(jù)之間的關系用相應的結點之間帶箭號的連線表示。如果成分數(shù)據(jù)本身又有它自身的結構，則結構出現(xiàn)嵌套。這里嵌套還允許是遞歸的嵌套。

由于指針數(shù)據(jù)的引入，使構造各種復雜的數(shù)據(jù)結構成為可能。按數(shù)據(jù)結構中的成分數(shù)據(jù)之間的關系，數(shù)據(jù)結構有線性與非線性之分。在非線性數(shù)據(jù)結構中又有層次與網(wǎng)狀之分。 由于數(shù)據(jù)類型是按照數(shù)據(jù)結構劃分的，因此，一類數(shù)據(jù)結構對應著一種數(shù)據(jù)類型。數(shù)據(jù)類型按照該類型中的數(shù)據(jù)所呈現(xiàn)的結構也有線性與非線性之分，層次與網(wǎng)狀之分。一個數(shù)據(jù)變量，在高級語言中的類型說明必須是讀變量所具有的數(shù)據(jù)結構所對應的數(shù)據(jù)類型。

最常用的數(shù)據(jù)結構是數(shù)組結構和記錄結構。數(shù)組結構的特點是：

1. 成分數(shù)據(jù)的個數(shù)固定，它們之間的邏輯關系由成分數(shù)據(jù)的序號(或叫數(shù)組的下標)來體現(xiàn)。這些成分數(shù)據(jù)按照序號的先后順序一個挨一個地排列起來。
2. 每一個成分數(shù)據(jù)具有相同的結構(可以是簡單結構，也可以是復雜結構)，因而屬于同一個數(shù)據(jù)類型(相應地是簡單數(shù)據(jù)類型或構造數(shù)據(jù)類型)。這種同一的數(shù)據(jù)類型稱為基類型。
3. 所有的成分數(shù)據(jù)被依序安排在一片連續(xù)的存儲單元中。

概括起來，數(shù)組結構是一個線性的、均勻的、其成分數(shù)據(jù)可隨機訪問的結構。由于這種結構有這些良好的特性，所以最常被人們所采用。在高級語言中，與數(shù)組結構相對應的數(shù)據(jù)類型是數(shù)組類型，即數(shù)組結構的數(shù)據(jù)變量必須說明為array [i] of T₀ ，其中i是數(shù)組結構的下標類型，而T₀是數(shù)組結構的基類型。

記錄結構是另一種常用的數(shù)據(jù)結構。它的特點是:

1. 與數(shù)組結構一樣，成分數(shù)據(jù)的個數(shù)固定。但成分數(shù)據(jù)之間沒有自然序，它們處于平等地位。每一個成分數(shù)據(jù)被稱為一個域并賦予域名。不同的域有不同的域名。
2. 不同的域允許有不同的結構，因而允許屬于不同的數(shù)據(jù)類型。
3. 與數(shù)組結構一樣，它們可以隨機訪問，但訪問的途徑靠的是域名。

在高級語言中記錄結構對應的數(shù)據(jù)類型是記錄類型。記錄結構的數(shù)據(jù)的變量必須說明為記錄類型。

抽象數(shù)據(jù)類型的含義在上一段已作了專門敘述。它可理解為數(shù)據(jù)類型的進一步抽象。即把數(shù)據(jù)類型和數(shù)據(jù)類型上的運算捆在一起，進行封裝。引入抽象數(shù)據(jù)類型的目的是把數(shù)據(jù)類型的表示和數(shù)據(jù)類型上運算的實現(xiàn)與這些數(shù)據(jù)類型和運算在程序中的引用隔開，使它們相互獨立。對于抽象數(shù)據(jù)類型的描述，除了必須描述它的數(shù)據(jù)結構外，還必須描述定義在它上面的運算(過程或函數(shù))。抽象數(shù)據(jù)類型上定義的過程和函數(shù)以該抽象數(shù)據(jù)類型的數(shù)據(jù)所應具有的數(shù)據(jù)結構為基礎。