「抽象データ型」の版間の差分

削除された内容 追加された内容
編集の要約なし
1行目:
'''抽象データ型'''(ちゅうしょうデータがた、{{lang-en-short|abstract data type}}、ADT)'''とは、データ構造とそれを直接操作する手続きをまとめてデータ型の定義とすることでデータ抽象<ref>データ抽象(data abstraction)とは、データ型の詳細定義とその操作に関する手続きを情報の局所性が高まるようにソースコード中の一カ所にまとめて記述するための記法のことを言う。情報が一カ所に局所的にまとめて記載されているため、非公開(private)部分の変更であればその定義部分の詳細を変更するだけでソースコード全体の修正が完了する。
 
データ型の詳細定義とその操作手続きの局所的記述を実現する方法は複数あり、抽象データ型はその一例である。</ref>を実現する手法またはそのひとまとまりとして定義されたデータ型を言う。通常のデータ型であれば変数宣言で変数に束縛されるものは値であるが、抽象データ型の世界において値に相当するものはデータ構造とその操作<ref>言語に応じて名称が異なり、C++であればメンバ関数(member function)、JAVAであればメソッド(method)と呼ばれる</ref>のまとまり<ref>データ型の値に相当するこのまとまりのことを抽象データ型の実体(インスタンス , instance)と呼ぶ。</ref>である。
6行目:
 
== 概要 ==
[[エドガー・ダイクストラ]]らの構造化プログラミングは仮想機械モデルに基づく段階的詳細化法(stepwise<ref>{{lang-en-short|stepwise refinement)refinement}}</ref>をもたらしたが、データ構造の変更を行うと変更部分がソースコード中に散在してしまうという弱点があった。データ抽象の概念はその欠点を補完するものであった。抽象データ型はデータ抽象の具体的手法として1974年にB.H.Liskovの提案した言語CLUにおいて提案された<ref>参考文献5</ref>。
 
==インタフェースと実装の分離==
13行目:
抽象データ型の強みはユーザーから実装が隠蔽されていることである。インタフェースのみが公開されるのである。このことは、抽象データ型がいろいろな方法で実装されうることを意味するが、インタフェースに忠実な限りユーザープログラムは影響を受けないのである。
 
例えば、二分探索木抽象データ型はいくつかの方法で実装できる。例えば、[[二分木]]([[:en:binary tree]]),[[、{{仮リンク|AVL木]]([[:|en:|AVL tree]]),[[}}、{{仮リンク|赤黒木]]([[:|en:|red black tree]]),}}、配列である。しかし実装に関わらず二分探索木はinsert, remove, find「挿入」「削除」「検索」といった同じ操作が可能である。
 
== 抽象データ構造 ==
26行目:
[[有理数]]は計算機においてはそのまま扱うことはできない。有理数の抽象データ型は以下のように定義できる。
 
'''コンストラクタ''': 2つの整数a, <math>a</math>、<math>b</math> を用いて有理数の抽象データ型のインスタンスを作成する。ここで <math>a</math> は分子で <math>b</math> は分母である。
 
'''関数''': 加算,減算,乗算,除算,指数計算,比較,約分,実数への変換
 
完全な記述にするためには、それぞれの関数はデータに言及して記述されるべきである。例えば、有理数<math>a/b</math>と<math>c/d</math>を乗算するときには結果は<math>ac/bd</math>と定義される。通常入力,出力,実行前条件,実行後条件,抽象データ型に対する仮定も記述される。
 
== 脚注 ==