ADT[數學模型]

簡介

抽象數據類型（AbstractDataType，ADT）是計算機科學中具有類似行為的特定類別的數據結構的數學模型；或者具有類似語義的一種或多種程式設計語言的數據類型。抽象數據類型是間接定義的，通過其上的可執行的操作以及這些操作的效果的數學約束（與可能的代價）。

例如，抽象的堆疊（stack）由3個操作定義：推入push，彈出pop（接受約束：每次彈出返回的是最新被推入且沒有被彈出的數據，也就是後進先出），查看堆疊頂端數據peek。當分析使用堆疊算法的效率，所有這3個操作用時相同，無論堆疊中包含多少項數據；並且對每項數據棧使用了常量大小的存儲。

抽象數據類型（ADT）是純粹理論實體，用於簡化描述抽象算法，分類與評價數據結構，形式描述程式設計語言的類型系統。一個ADT可以用特定數據類型或數據結構實現，在許多程式設計語言中有許多種實現方式；或者用形式規範語言描述。ADT常實現為模組（module）：模組的接口聲明了對應於ADT操作的例程（procedure），有時用注釋描述了約束。

示例

在程式語言（或庫）和教科書中，常見的幾個抽象數據類型如下：

•關聯數組

•複數

•容器

•雙端佇列

•列表

•Multimap

•優先佇列

•佇列

•集合

•堆疊

•字元串

•樹

接口和實現的分離

實現於程式時，抽象數據類型只顯現出其接口，並將實現加以隱藏。用戶只需關心它的接口，而不是如何實現。未來更可以改變實現的方式。（其支持信息隱藏原理，或保護程式免受變化的衝擊。）

抽象數據類型的強處在於對用戶隱藏了實現細節，僅公開其接口。這表示抽象數據類型可以用各種方法來實現，只要遵循其接口，就不會影響到用戶。

在抽象數據類型和數據結構之間，有一個實現上的微妙差別。例如，列表的抽象數據類型可以數組為基礎、或者使用鍊表來實現。列表即是一種具良好運算（加入元素、移除元素等等）定義的抽象數據類型。鍊表是以指針為基礎的數據結構，且可用來創建一個列表。鍊表常用於列表的抽象數據類型。

同樣地，二叉樹搜尋法的抽象數據結構可以幾個方式實現：二叉樹、AVL樹、紅黑樹、數組等等。且無須關心其實現，二叉樹搜尋法總是有相同的運算（插入、移除、查找等等）。

從實現中分離出接口，並不表示用戶不該知道實現的方法，而是用戶不能依賴於實現細節。例如，一個抽象數據類型可以用腳本語言創建，或其它可以被反編譯的語言（如C語言）。即使用戶可發現實現的方法，只要所有客戶端程式遵循該接口，且改變實現方式時不會產生影響，那就仍是抽象數據類型。

在面向對象的用語中，抽象數據類型相當於類別；抽象數據類型的實體就相當於對象。某些語言包含了用於宣告抽象數據類型的構造函式。例如，C++ 和 Java 為此提供了類的構造函式。

抽象數據結構

抽象數據結構即根據所要運算的數據以及其計算複雜性所定義的抽象存儲區，而不關心具體的數據結構的實現。

就實現高效率的算法而言，對數據結構的選擇相當重要。抽象數據結構的選擇，決定了高效率的算法的設計，和估計其計算複雜性。

這個概念與程式語言理論中所使用的抽象數據 類型非常接近，大致上抽象數據結構和抽象數據類型的名稱，和具體的數據結構的名稱一致。

內置抽象數據類型

一部分抽象數據類型在程式設計中相當普遍且實用，所以在某些程式語言中，成為原生類型、或加進標準庫中。例如，Perl 的數組可以用列表或雙端佇列之類的抽象數據類型來實現，散列表也可以用 Map 或 Table 來做。C++ 標準庫和 Java 庫也提供了列表、堆疊、佇列、Map、優先權佇列和字元串。

實際示例

作為抽象數據類型的有理數

有理數（可以 a/b 格式表示的數，且 a 和 b 都是整數）本來是不能在電腦中表示出來。不過可以合理的抽象數據類型來定義，如下。

構造：使用兩個整數 a 與 b 創建實體，其中 a 為分子，b 為分母。

運算：加法、減法、乘法、除法、乘幕、比較、約分，轉成實數（浮點數）。

ADT[數學模型]

要完成整個規格，就要根據數據來定義所有的運算。例如，當兩個有理數 a/b 和 c/d 相乘時，相乘的結果就要定義為 。還有輸入、輸出、先決條件、後置條件，以及對抽象數據類型的各種假定。

堆疊

堆疊的抽象數據類型接口，以C語法編寫：

用法

抽象數據類型可以如下方式使用：

各種實現

上述堆疊的抽象數據類型，一開始可以使用數組來實現，然後改用鍊表，而不會傷到任何用戶的代碼。有多少方法可以實現抽象數據類型，取決於程式語言。例如，上述示例可使用C 編寫一個結構，以及隨同的一組數據結構，可使用數組或鍊表來存放記錄；當構造函式函式返回一個抽象句柄時，就對用戶隱藏了真實的實現過程。

參閱

•抽象化