資結/演算法

抽象資料型態 (Abstract Data Type, ADT)

資料型態 (Data Type)

Def:

A data type is a collection of objects and a set of operations that act on those objects。

 

資料型態,是一組 物件 (objects),及作用於這些物件的 操作 (operations) 集合

 
例如:

int 是一 Data Type
Data Objects 由 正負號 及 0~9 所組成之整數集合
Operations + – * / = > < ≥ ≤ …

 


 

抽象資料型態 (Abstract Data Type, ADT)

抽象資料型態,是一種組織過的資料型態,
提供 『物件 (objects)』 與 『作用於這些物件的 操作 (operations)』的 規範
而非 實際表示法 與 具體實現 的方式。

 

操作規範 (The specification of the operation)

基本上,包含了:

  1. 函式名稱 (Function Name)
  2. 參數型態 (The type of its argument)
  3. 結果型態 (The type of its result)
  4. 函式功能的描述 (不必說明內部表示法或實作細節)

 

ADT 是 Implementation-Independent。
ADT 規範每個操作 要做什麼 (what)而非 如何做 (how)

 
在大部分物件導向程式中,ADT 可以用 介面 (interface) 來表示,
C 語言 沒有實作 ADT 的明確方法,但仍可以使用相同的概念,來設計自有的資料型態。

 
 

優點

使用 ADT 的好處是,使用者僅需操作其所提供的函式。
 
依賴倒置原則 (Dependency Inversion Principle, DIP) 所述:

介面的中心思想是: "封裝隔離"
也就是外部類別只需要呼叫介面提供的方法,不用也不需要知道內部如何實作。
 
依據『介面導向程式設計』,善用介面的好處,使得系統具有高維護性與彈性,
不論是擴充或重構,外部呼叫類別僅會受到最小幅度的影響 (甚至不受影響)。

 

舉例

Stack 堆疊 的 ADT 描述:
Data Objects: 一個含有零個或多個元素的有限有序串列。
 
Operations,[回傳型態] [操作名稱] ::= [規格內容]:

  1. Stack Create(n) ::= 建立一個容量為 n 的空 Stack 並回傳,對所有 n ∈正整數
  2. Boolean IsFull(stack) ::= 回傳堆疊是否已滿
  3. Boolean IsEmpty(stack) ::= 回傳堆疊是否為空
  4. Stack Push(stack, item) ::= 若堆疊未滿,插入元素 item 至堆疊頂端,並回傳此堆疊物件
  5. Element Pop (stack) ::= 若堆疊未空,移除並回傳堆疊頂端的元素

 
每種語言 (或每個人) 對 ADT 的描述不盡相同,
以上僅為 Stack 的常見 ADT 之一。
 
例如有些會補充:
Integer Size() ::= 回傳此堆疊中,元素的個數。
Element Top() ::= 回傳堆疊頂端的元素,但是不移除
 


 

總結

在資料結構設計上,
應用抽象化 (Abstraction),引出了 抽象資料型態 (Abstract Data Type, ADT) 的概念,
運用 ADT 的觀點,可以更精確的 (mathematical) 了解資結。
 
範例原始檔
 
 

作者: 鄭中勝
喜愛音樂,但不知為何總在打程式 ? 期許能重新審視、整理自身所學,幫助有需要的人。

在《抽象資料型態 (Abstract Data Type, ADT)》中有 2 則留言

發表迴響