|
|
抽象數據類型
(abstract data type 簡稱adt)
是指一個數學模型以及定義在此數學模型上的一組操作。
抽象數據類型需要通過固有數據類型(高級編程語言中已實現的數據類型)來實現。
抽象數據類型是與表示無關的數據類型，是一個數據模型及定義在該模型上的一組運算。對一個抽象數據類型進行定義時，必須給出它的名字及各運算的運算符名，即函數名，並且規定這些函數的參數性質。一旦定義了一個抽象數據類型及具體實現，程序設計中就可以像使用基本數據類型那樣，十分方便地使用抽象數據類型。
抽象數據類型的描述包括給出抽象數據類型的名稱、數據的集合、數據之間的關係和操作的集合等方面的描述。抽象數據類型的設計者根據這些描述給出操作的具體實現，抽象數據類型的使用者依據這些描述使用抽象數據類型。
抽象數據類型描述的一般形式如下：
adt 抽象數據類型名稱 {
數據對象：
……
數據關係：
……
操作集合：
操作名1：
……
……
操作名n：
}adt抽象數據類型名稱
抽象數據類型定義（adt）
作用：抽象數據類型可以使我們更容易描述現實世界。例：用綫性表描述學生成績表，用樹或圖描述遺傳關係。
定義：一個數學模型以及定義在該模型上的一組操作。
關鍵：使用它的人可以衹關心它的邏輯特徵，不需要瞭解它的存儲方式。定義它的人同樣不必要關心它如何存儲。
例：綫性表這樣的抽象數據類型，其數學模型是：數據元素的集合，該集合內的元素有這樣的關係：除第一個和最後一個外，每個元素有唯一的前趨和唯一的後繼。可以有這樣一些操作：插入一個元素、刪除一個元素等。 |
|
抽象數據類型
abstract data type
ChouxiQng shUjU leixing
抽象數據類型(abstract data勺pe)與表示
無關的數據類型。數據類型由一個對象集合(值集)
和在該集合上定義的若幹合法運算所組成的運算集
合組成。抽象數據類型用數學方法定義對象集合和
運算集合，僅通過運算的性質刻畫數據對象，而獨立
於計算機中可能的表示方法。其目的在於隱蔽運算
實現細節和內部數據結構，同時嚮用戶提供該數據
類型的完整信息。
抽象數據類型的概念是逐步形成的。60年代
末到70年代，人們將用戶自定義的類型稱作抽象數
據類型。傳統的算法語言沒有用戶自定義類型的設
施。到60年代末，為了實現算法細節和數據內部結
構的隱蔽，SIMIJLA67語言中引人了類，隨後出現
了模塊概念。模塊可分成模塊式和模塊體，模塊式
定義外部可見的運算接口，模塊體對外不可見，其中
可定義私有的數據結構和運算。通過接口和實現的
分離，模塊提供了用戶自定義類型的手段，達到數據
抽象、信息隱蔽的目的。在這個意義下，模塊所定義
的數據類型稱作抽象數據類型。實際上，模塊提供
了一種抽象數據類型實現的手段。這種手段在
入玉月ula-2，八da等語言中得到進一步的完善和發展。
用戶自定義數據類型的另一優點是設計與實現相分
離，可將模塊式看作設計規約，而模塊體是相應的實
現。這種分離推動了軟件規約的研究，也進一步推
動了抽象數據類型的研究。
當用一個數據類型去模擬一類客觀對象時，可
先給出該類型的性質和功能的描述，然後用已有的
語言設施和數據類型實現所需的功能，並證明實現
的正確性。僅通過模塊式描述數據類型的型構是不
夠的，還必須用抽象的方法完整地描述對象的性態
和功能。這就是用抽象數據類型表示功能規約。這
時，抽象數據類型完全獨立於具體表示，反映出純抽
象的性質。抽象數據類型的規約方法主要有二:其
一是代數方法;其二是模型方法。代數方法基於G.
Birkhoff，J .D.LipSOn等的異調代數理論，經5.21115，
J.A.Guttag等人的發展，其理論基礎日趨完善，並逐
步應用於軟件工程實踐，成為有代表性的抽象數據
類型規約方法。模型方法基於C.A.R.HOare的前
後斷言方法，它通過已定義的(抽象)數據類型來給
出所要定義的新類型的抽象模型。
采用代數方法，抽象數據類型的規約由兩部分
組成，一是語法部分，二是公理部分。語法部分給出
了抽象數據類型的名及其上運算的定義域和值域，
公理部分則通過給出一組刻畫各運算之間相互關係
的方程來定義各運算的含義。從語義的角度，代數
規約的語義是一類代數。在語法正確的基礎上，語
義正確性是指相應代數滿足規約中公理部分的所有
公理。通常，具語義正確性的語義模型代數有多個 |
|
- : abstract data type
|
|
|