抽象データ型
出典: フリー百科事典『ウィキペディア（Wikipedia）』
抽象データ型(abstract data type)は、データとデータに対する行うことができる操作の集合についての記述である。このようなデータ型は様々な実装から独立しているという意味で抽象である。定義は数理的なものか、インタフェースとして記述することができる。インタフェースには、新しいデータへの抽象ハンドルを返すコンストラクタと、抽象ハンドルを引数としてとる関数（操作）が存在する。
目次 |
[編集] 例
教科書に書かれているものや、プログラミング言語やそのライブラリにおいて実装されている抽象データ型には以下のようなものがある。
- 文字列(String)
- リスト(List)
- 連結リスト(en:Linked List)
- スタック(Stack)
- キュー(en:Queue)
- 二分探索木(en:Binary search tree)
- 優先度つきキュー(en:Priority queue)
- 複素数(en:Complex number)
- 連想配列(en:Associative array)
- マルチマップ(en:Multimap)
- 集合
[編集] インタフェースと実装の分離
プログラムが実装されたとき、抽象データ型は実装を隠蔽するインタフェースを表す。実装は将来において変更されうるので、抽象データ型のユーザーは実装ではなくインタフェースに関心がある。
抽象データ型の強みはユーザーから実装が隠蔽されていることである。インタフェースのみが公開されるのである。このことは、抽象データ型がいろいろな方法で実装されうることを意味するが、インタフェースに忠実な限りユーザープログラムは影響を受けないのである。
例えば、二分探索木抽象データ型はいくつかの方法で実装できる。例えば、二分木(en:binary tree),AVL木(en:AVL tree),赤黒木(en:red black tree),配列である。しかし実装に関わらず二分探索木はinsert, remove, findといった同じ操作が可能である。
[編集] 抽象データ構造
抽象データ構造とは、実際のデータ構造による実装に関わらず、操作の集合とその計算量により定義されるデータのための抽象的な領域のことである。
具体的なデータ構造の選択がアルゴリズムの効率的な実装にとって重要である一方、抽象データ構造の選択は効率的なアルゴリズムの設計とその計算量の推定にとって極めて重要である。
この概念はプログラミング言語の理論で用いられる抽象データ型の概念に非常に近い。多くの抽象データ構造や抽象データ型の名前は具体的なデータ構造の名前と一致する。
[編集] 組み込みの抽象データ型
抽象データ型のうちいくつかはプログラムにおいて一般的かつ有用なため、プログラミング言語の中にはそれらを言語の型とするか標準ライブラリに加えているものがある。例えば、Perlの配列はリストかDeque抽象データ型の実装で、Perlのハッシュはマップかテーブル抽象データ型で記述されていると考えることができる。一方、C++の標準ライブラリやJavaのライブラリはリスト,スタック,キュー,マップ,優先度つきキュー,文字列等をクラスとして提供している。
[編集] 具体例
[編集] 抽象データ型としての有理数
有理数は計算機においてはそのまま扱うことはできない。有理数の抽象データ型は以下のように定義できる。
コンストラクタ: 2つの整数a, bを用いて有理数の抽象データ型のインスタンスを作成する。ここでaは分子でbが分母である。
関数: 加算,減算,乗算,除算,指数計算,比較,約分,実数への変換
完全な記述にするためには、それぞれの関数はデータに言及して記述されるべきである。例えば、有理数a / bとc / dを乗算するときには結果はac / bdと定義される。通常、入力,出力,実行前条件,実行後条件,抽象データ型に対する仮定も記述される。
[編集] スタック
[編集] インターフェース
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言語においては構造体と配列または連結リストを用いて書くことができるが、コンストラクタ関数が抽象ハンドルを返すことで実装をユーザーから隠さなければならない。C++やJavaのようなオブジェクト指向言語においては、抽象データ型は通常、データはデータメンバとして、操作はメンバ関数として表現される。加えて、C++やJavaのような言語はデータへのアクセスをデータを操作するためのメンバ関数のみに対して許可するしくみを備えている。また、オブジェクト指向の抽象データ型を使う場合は、ユーザーはそれを継承した派生クラスを用いることができることが多い。
