抽象資料型別
![本頁使用了標題或全文手工轉換](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
![]() |
抽象資料型別(英語:Abstract data type,縮寫:ADT)是電腦科學中具有類似行為的特定類別的資料結構的數學模型;或者具有類似語意的一種或多種程式語言的資料類型。抽象資料類型是間接定義的,通過其上的可執行的操作以及這些操作的效果的數學約束(與可能的代價)。
例如,抽象的堆疊(stack)由3個操作定義:推入push,彈出pop(接受約束:每次彈出返回的是最新被推入且沒有被彈出的資料,也就是後進先出),檢視堆疊頂端資料peek。當分析使用堆疊演算法的效率,所有這3個操作用時相同,無論堆疊中包含多少項資料;並且對每項資料棧使用了常數大小的儲存。
抽象資料類型(ADT)是純粹理論實體,用於簡化描述抽象演算法,分類與評價資料結構,形式描述程式語言的型別系統。一個ADT可以用特定資料類型或資料結構實作,在許多程式語言中有許多種實作方式;或者用形式規範語言描述。ADT常實作為模組(module):模組的介面聲明了對應於ADT操作的常式(procedure),有時用註釋描述了約束。
範例
[編輯]在程式語言(或函式庫)和教科書中,常見的幾個抽象資料型別如下:
介面和實作的分離
[編輯]實現於程式時,抽象資料型別只顯現出其介面,並將實作加以隱藏。用戶只需關心它的介面,而不是如何實作。未來更可以改變實作的方式。(其支援資訊隱藏原理,或保護程式免受變化的衝擊。)
抽象資料型別的強處在於對用戶隱藏了實作細節,僅公開其介面。這表示抽象資料型別可以用各種方法來實作,只要遵循其介面,就不會影響到用戶。
在抽象資料型別和資料結構之間,有一個實作上的微妙差別。例如,列表的抽象資料型別可以陣列為基礎、或者使用連結串列來實作。列表即是一種具良好運算(加入元素、移除元素等等)定義的抽象資料型別。連結串列是以指標為基礎的資料結構,且可用來建立一個列表。連結串列常用於列表的抽象資料型別。
同樣地,二叉樹搜尋法的抽象資料結構可以幾個方式實作:二叉樹、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 編寫一個結構,以及隨同的一組資料結構,可使用陣列或連結串列來存放記錄;當建構子函數返回一個抽象控制代碼時,就對用戶隱藏了真實的實作過程。
參閱
[編輯]
|
|
|
|