抽象資料類型
维基百科，自由的百科全书
在計算中，抽象資料類型（Abstract data type，ADT）是一組資料以及相應運算的規格。如某個資料類型是抽象的，且獨立於各種具體的實作。其可用數學定義，或者可用作為程式設計中的界面。界面提供一個建構子，建新的資料時，其返回一個抽象把柄（handle）且若干運算函式接受將抽象把柄作為參數。
目录 |
[编辑] 範例
在程式語言（或函式庫）和教科書中，常見的幾個抽象資料類型如下︰
[编辑] 界面和實作的分離
當實現在程式時，抽象資料類型只顯現出其界面，並將實作加以隱藏。使用者只需關心它的界面，而不是如何實作。未來更可以改變實作的方式。（其支援資訊隱藏原理，或保護程式免受變化的衝擊。）
抽象資料類型的強處在於對使用者隱藏了實作細節，僅公開其界面。這表示抽象資料類型可以用各種方法來實作，只要遵循其界面，就不會影響到使用者。
在抽象資料類型和資料結構之間，有一個實作上的微妙差別。例如，列表的抽象資料類型可以陣列為基礎、或者使用鏈表來實作。列表即是一種具良好運算（加入元素、移除元素等等）定義的抽象資料類型。鏈表是以指標為基礎的資料結構，且可用來建立一個列表。鏈表常用於列表的抽象資料類型。
類似地，二元樹搜尋法的抽象資料結構可以幾個方式實作︰二叉樹、AVL樹、紅黑樹、陣列等等。且無須關心其實作，二元樹搜尋法總是有相同的運算（插入、移除、尋找…等等）。
從實作中分離出界面，並不表示使用者不該知道實作的方法，而是使用者不能依賴於實作細節。例如，一個抽象資料類型可以用腳本語言建立，或其它可以被反編譯的語言（如 C語言）。即使使用者可發現實作的方法，只要所有客戶端程式遵循該界面，且改變實作方式時不會產生影響，那就仍是抽象資料類型。
在物件導向的用語中，抽象資料類型相當於類別；抽象資料類型的實體就相當於物件。某些語言包含了用於宣告抽象資料類型的建構子。例如，C++ 和 Java 為此提供了類別建構子。
[编辑] 抽象資料結構
抽象資料結構即根據所要運算的資料以及其計算複雜性所定義的抽象儲存區，而不關心具體的資料結構的實作。
就實作高效率的演算法而言，對資料結構的選擇相當重要。抽象資料結構的選擇，決定了高效率的演算法的設計，和估計其計算複雜性。
這個概念與程式語言理論中所使用的抽象資料類型非常接近，大致上抽象資料結構和抽象資料類型的名稱，和具體的資料結構的名稱一致。
[编辑] 內建抽象資料類型
一部分抽象資料類型在程式設計中相當普遍且實用，所以在某些程式語言中，成為原生類型、或加進標準函式庫中。例如，Perl 的陣列可以用列表或雙端佇列之類的抽象資料類型來實作，哈希表也可以用 Map 或 Table 來做。C++ 標準函式庫和 Java 函式庫也提供了列表、堆疊、佇列、Map、優先權佇列和字串。
[编辑] 實際範例
[编辑] 作為抽象資料類型的有理數
有理數（可以 a/b 格式表示的數，且 a 和 b 都是整數）本來是不能在電腦中表示出來。不過可以合理的抽象資料類型來定義，如下。
構造︰使用兩個整數 a 與 b 建立實體，其中 a 為分子，b 為分母。
運算︰加法、減法、乘法、除法、乘幕、比較、約分，轉成實數（浮點數）。
要完成整個規格，就要根據資料來定義所有的運算。例如，當兩個有理數 a/b 和 c/d 相乘時，相乘的結果就要定義為 ( a c ) / ( b 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 編寫一個結構，以及隨同的一組資料結構，可使用陣列或鏈表來存放記錄；當建構子函式返回一個抽象把柄時，就對使用者隱藏了真實的實作過程。
[编辑] 參閱
- 抽象化
