1.3　抽象數據類型

1．數據類型

數據類型是指性質相同的值的集合以及定義在該值集上的運算集合。C語言常用的基本數據類型有整型、字符型、指針類型等。數據類型規定了數據的取值范圍和允許執行的運算。例如，若在C語言中聲明int a,b，則可以給變量a和b賦值0，但不可以賦值2.5，這超出了int型變量的取值范圍。a和b之間可以執行加法運算，但不可以執行求交集運算，這也超出了int型變量所允許的運算范圍。

2．抽象數據類型

了解一個數據類型的對象（變量、常量）在計算機內的表示是有一定用處的，但如果每個數據使用者都要考慮基本數據類型的實現細節，這將給數據使用者增加一項繁雜的工作，并且使用者一旦隨意改變數據存儲表示，也會滋生不可預知的錯誤。目前普遍認為對數據類型進行抽象，對使用者隱藏一個數據類型的實現是一個好的設計策略，由此產生了抽象數據類型。

抽象數據類型（Abstract Data Type，ADT）是一個數學模型以及在其上定義的運算集合。其最主要的兩個特征是數據封裝和信息隱蔽。數據封裝是指把數據和操縱數據的運算組合在一起的機制。信息隱蔽是指數據的使用者只需知道這些運算的定義（也稱規范）便可訪問數據，而無須了解數據的存儲以及運算算法的實現細節。通過實行數據封裝和信息隱蔽，可使數據的使用和實現相分離。

本書中，抽象數據類型的定義格式如下：

3．數據結構與抽象數據類型

本書將一種數據結構視為一個抽象數據類型，從規范和實現兩方面來討論數據結構。規范是對數據結構中數據元素及其關系、運算給出定義，即邏輯結構和運算的定義組成了數據結構的規范。規范指明了一個數據結構可以“做什么”。數據結構的使用者通過規范中的說明使用一個數據結構，不必了解具體的實現細節。數據的存儲表示和運算算法的描述構成數據結構的實現，它解決了“怎樣做”的問題。