《C++面向對象高效程式設計（第2版）》——2.9 抽象資料類型

本節書摘來自異步社群出版社《c++面向對象高效程式設計（第2版）》一書中的第章，第2.1節，作者： 【美】kayshav dattatri，更多章節内容可以通路雲栖社群“異步社群”公衆号檢視。

c++面向對象高效程式設計（第2版）

有時，人們談論的是抽象資料類型（abstract data type），而不是資料抽象（data abstraction），這可能讓學習oop的人感到困惑。其實，它們的關系非常密切。

抽象資料類型是由程式員定義的新類型，附帶一組操控新類型的操作。定義新抽象類型将直接應用資料抽象的概念。抽象資料類型也稱為程式員定義類型（programmer defined type）。

任何語言基本上都支援内置資料類型（如整數、浮點數、字元等），而且通常會提供一組操控這些内置類型1的操作。當我們使用這些内置（或語言定義）類型時，并不知道也不關心（使用了資料抽象和封裝）如何實作這些資料類型。但是，語言（更精确地說是語言編譯器的實作者）非常了解實作，知道如何實作這些内置類型。進一步而言，語言定義類型的使用者不能直接通路這些類型的内部表示，而且必須使用語言提供的操作來操控它們。

例如，我們在使用語言提供的浮點數時，并不知道浮點類型的内部表示2。但是，我們肯定知道類似+和-的操作可用于浮點數計算。當我們使用浮點類型時，便間接地使用了語言編譯器的實作者所提供的内部表示，而且隻能使用語言已定義的操作。這也讓特定編譯器和特定機器彼此獨立，是以，我們可以在任何機器上運作任何語言編譯器（即我們獲得了實作獨立）。

支援結構化程式設計的語言（pascal、algol和c等）也允許使用者定義新類型，它們被稱為使用者定義類型（user defined type）或程式員定義類型（programmer defined type）。這些使用者定義類型在它們的實作中使用語言定義類型。另外，支援結構化程式設計的語言也允許程式員為使用者定義類型定義一組操作（不要與類似+和-這樣的操作混淆）。但是，主要的問題是，使用者定義類型的實作并未封裝。要使用程式員定義類型必須完全了解該類型的實作，但是語言并不會保護新類型的實作者，也就是說，缺少資料封裝（在c中使用static資料，可實作一些封裝）。新類型通常定義為一個組合，由資料結構和一組用于操控該資料結構的

圖2-4

函數組成，後者通過特定的方式通路資料結構。原則上，任何新類型的使用者都必須使用這些函數來操作新類型，換言之，使用者不應該直接通路或修改資料結構。但是，由于語言無法強制執行這條規則，是以無需了解資料結構如何使用，任何人都可以編寫新函數操作資料結構。也就是說，這樣做并未防止非法通路實作。在pascal、algol、c等語言中，隻有在使用者遵守隐性規則的前提下，才能確定資料完整，而語言不能強制執行這條規則。從本質上而言，新類型隻不過是由一組函數（或操作）支援的資料結構。

舉個簡單的例子，帶有push()和pop()這樣操作的stack（棧）類，其資料結構可以是一個數組或連結清單（棧通過數組或連結清單實作），在需要時通過push()和pop()操作修改資料結構。此外，我們還要考慮多個棧的建立和銷毀。為簡單起見，我們僅以整數棧為例，儲存在棧中的元素類型相同。在後續的章節中，我們将介紹如何用模闆類實作泛型棧（generic stack）。