基本介紹
- 中文名：抽象數據類型
- 外文名：Abstract Data Type
- 簡稱：ADT
- 領域：計算機科學
簡介,示例,接口和實現的分離,抽象數據結構,內置抽象數據類型,實際示例,作為抽象數據類型的有理數,堆疊,用法,各種實現,參閱,
簡介
抽象數據類型（AbstractDataType，ADT）是計算機科學中具有類似行為的特定類別的數據結構的數學模型；或者具有類似語義的一種或多種程式設計語言的數據類型。抽象數據類型是間接定義的，通過其上的可執行的操作以及這些操作的效果的數學約束（與可能的代價）。
例如，抽象的堆疊（stack）由3個操作定義：推入push，彈出pop（接受約束：每次彈出返回的是最新被推入且沒有被彈出的數據，也就是後進先出），查看堆疊頂端數據peek。當分析使用堆疊算法的效率，所有這3個操作用時相同，無論堆疊中包含多少項數據；並且對每項數據棧使用了常量大小的存儲。
抽象數據類型（ADT）是純粹理論實體，用於簡化描述抽象算法，分類與評價數據結構，形式描述程式設計語言的類型系統。一個ADT可以用特定數據類型或數據結構實現，在許多程式設計語言中有許多種實現方式；或者用形式規範語言描述。ADT常實現為模組（module）：模組的接口聲明了對應於ADT操作的例程（procedure），有時用注釋描述了約束。
示例
在程式語言（或庫）和教科書中，常見的幾個抽象數據類型如下：
接口和實現的分離
實現於程式時，抽象數據類型只顯現出其接口，並將實現加以隱藏。用戶只需關心它的接口，而不是如何實現。未來更可以改變實現的方式。（其支持信息隱藏原理，或保護程式免受變化的衝擊。）
抽象數據類型的強處在於對用戶隱藏了實現細節，僅公開其接口。這表示抽象數據類型可以用各種方法來實現，只要遵循其接口，就不會影響到用戶。
在抽象數據類型和數據結構之間，有一個實現上的微妙差別。例如，列表的抽象數據類型可以數組為基礎、或者使用鍊表來實現。列表即是一種具良好運算（加入元素、移除元素等等）定義的抽象數據類型。鍊表是以指針為基礎的數據結構，且可用來創建一個列表。鍊表常用於列表的抽象數據類型。
同樣地，二叉樹搜尋法的抽象數據結構可以幾個方式實現：二叉樹、AVL樹、紅黑樹、數組等等。且無須關心其實現，二叉樹搜尋法總是有相同的運算（插入、移除、查找等等）。
從實現中分離出接口，並不表示用戶不該知道實現的方法，而是用戶不能依賴於實現細節。例如，一個抽象數據類型可以用腳本語言創建，或其它可以被反編譯的語言（如C語言）。即使用戶可發現實現的方法，只要所有客戶端程式遵循該接口，且改變實現方式時不會產生影響，那就仍是抽象數據類型。
抽象數據結構
就實現高效率的算法而言，對數據結構的選擇相當重要。抽象數據結構的選擇，決定了高效率的算法的設計，和估計其計算複雜性。
這個概念與程式語言理論中所使用的抽象數據類型非常接近，大致上抽象數據結構和抽象數據類型的名稱，和具體的數據結構的名稱一致。
內置抽象數據類型
一部分抽象數據類型在程式設計中相當普遍且實用，所以在某些程式語言中，成為原生類型、或加進標準庫中。例如，Perl 的數組可以用列表或雙端佇列之類的抽象數據類型來實現，散列表也可以用 Map 或 Table 來做。C++ 標準庫和 Java 庫也提供了列表、堆疊、佇列、Map、優先權佇列和字元串。
實際示例
作為抽象數據類型的有理數
有理數（可以 a/b 格式表示的數，且 a 和 b 都是整數）本來是不能在電腦中表示出來。不過可以合理的抽象數據類型來定義，如下。
構造：使用兩個整數 a 與 b 創建實體，其中 a 為分子，b 為分母。
運算：加法、減法、乘法、除法、乘幕、比較、約分，轉成實數（浮點數）。
要完成整個規格，就要根據數據來定義所有的運算。例如，當兩個有理數 a/b 和 c/d 相乘時，相乘的結果就要定義為
。還有輸入、輸出、先決條件、後置條件，以及對抽象數據類型的各種假定。
堆疊
堆疊的抽象數據類型接口，以C語法編寫：
long stack_create(); /* 建立新的堆疊實體*/void stack_push(long stack, void *item); /* 將一個項目堆入堆疊*/void *stack_pop(long stack); /* 從堆疊頂部取得項目*/void stack_delete(long stack); /* 刪除堆疊*/
用法
抽象數據類型可以如下方式使用：
long stack;struct foo *f;stack = stack_create(); /* 建立堆疊*/stack_push(stack, f); /* 將foo 結構加入堆疊*/f = stack_pop(stack); /* 從堆疊取得頂部的結構*/
各種實現
上述堆疊的抽象數據類型，一開始可以使用數組來實現，然後改用鍊表，而不會傷到任何用戶的代碼。有多少方法可以實現抽象數據類型，取決於程式語言。例如，上述示例可使用C 編寫一個結構，以及隨同的一組數據結構，可使用數組或鍊表來存放記錄；當構造函式函式返回一個抽象句柄時，就對用戶隱藏了真實的實現過程。
