(Abstract Data Type 簡稱ADT)
是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。
抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型(高級(jí)編程語言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來實(shí)現(xiàn)。
抽象數(shù)據(jù)類型是與表示無關(guān)的數(shù)據(jù)類型,是一個(gè)數(shù)據(jù)模型及定義在該模型上的一組運(yùn)算。對(duì)一個(gè)抽象數(shù)據(jù)類型進(jìn)行定義時(shí),必須給出它的名字及各運(yùn)算的運(yùn)算符名,即函數(shù)名,并且規(guī)定這些函數(shù)的參數(shù)性質(zhì)。一旦定義了一個(gè)抽象數(shù)據(jù)類型及具體實(shí)現(xiàn),程序設(shè)計(jì)中就可以像使用基本數(shù)據(jù)類型那樣,十分方便地使用抽象數(shù)據(jù)類型。
抽象數(shù)據(jù)類型的描述包括給出抽象數(shù)據(jù)類型的名稱、數(shù)據(jù)的集合、數(shù)據(jù)之間的關(guān)系和操作的集合等方面的描述。抽象數(shù)據(jù)類型的設(shè)計(jì)者根據(jù)這些描述給出操作的具體實(shí)現(xiàn),抽象數(shù)據(jù)類型的使用者依據(jù)這些描述使用抽象數(shù)據(jù)類型。
抽象數(shù)據(jù)類型描述的一般形式如下:
ADT 抽象數(shù)據(jù)類型名稱 {
數(shù)據(jù)對(duì)象:
……
數(shù)據(jù)關(guān)系:
……
操作集合:
操作名1:
……
……
操作名n:
}ADT抽象數(shù)據(jù)類型名稱
抽象數(shù)據(jù)類型定義(ADT)
作用:抽象數(shù)據(jù)類型可以使我們更容易描述現(xiàn)實(shí)世界。例:用線性表描述學(xué)生成績表,用樹或圖描述遺傳關(guān)系。
定義:一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。
關(guān)鍵:使用它的人可以只關(guān)心它的邏輯特征,不需要了解它的存儲(chǔ)方式。定義它的人同樣不必要關(guān)心它如何存儲(chǔ)。
例:線性表這樣的抽象數(shù)據(jù)類型,其數(shù)學(xué)模型是:數(shù)據(jù)元素的集合,該集合內(nèi)的元素有這樣的關(guān)系:除第一個(gè)和最后一個(gè)外,每個(gè)元素有唯一的前趨和唯一的后繼。可以有這樣一些操作:插入一個(gè)元素、刪除一個(gè)元素等。