抽象データ型

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

コンピュータサイエンスでは抽象データ型ADT)はデータ型の数学モデルです抽象データ型は、ユーザーの観点からのデータの動作(セマンティクス)によって定義されます。具体的には、可能な値、この型のデータに対する可能な操作、およびこれらの操作の動作の観点から定義されます。この数学的モデルは、データの具体的な表現であり、ユーザーではなく実装者の視点である データ構造とは対照的です。

正式には、ADTは、「論理的な動作が一連の値と一連の操作によって定義されるオブジェクトのクラス」として定義される場合があります。[1]これは数学の代数的構造に類似しています。「振る舞い」が意味するものは作者によって異なり、振る舞いの形式仕様の2つの主要なタイプは、公理的(代数的)仕様抽象モデルです。[2]これらは、それぞれ抽象機械公理的意味論操作的意味論に対応しています。一部の著者は、計算の複雑さも含みます(「コスト」)、時間(コンピューティング操作の場合)とスペース(値の表現の場合)の両方の観点から。実際には、抽象化が完全ではないため、多くの一般的なデータ型はADTではなく、ユーザーは、表現に起因する算術オーバーフローなどの問題に注意する必要があります。たとえば、整数は固定幅の値(32ビットまたは64ビットの2進数)として格納されることが多いため、最大値を超えると 整数のオーバーフローが発生します。

ADTは、コンピューターサイエンスの理論的概念であり、アルゴリズム、データ構造、およびソフトウェアシステムの設計と分析に使用され、コンピューター言語の特定の機能に対応していません。主流のコンピューター言語は、正式に指定されたADTを直接サポートしていません。ただし、さまざまな言語機能はADTの特定の側面に対応しており、適切なADTと簡単に混同されます。これらには、抽象型不透明(OPAQUE)型プロトコル、および契約による設計が含まれます。ADTは、 CLU言語の開発の一環として、1974年にBarbaraLiskovとStephenN.Zillesによって最初に提案されました。[3]

抽象データ型

たとえば、整数はADTであり、値...、-2、-1、0、1、2、...として定義され、加算、減算、乗算、除算の演算によって、より大きい値とともに定義されます。 、より小さいなど。これらは、コンピューターによる整数の表現方法に関係なく、(整数の除算に注意して)使い慣れた数学に従って動作します。[a]明示的に、「振る舞い」には、さまざまな公理(加算の結合法則や可換性など)、および演算の前提条件(ゼロで除算できない)に従うことが含まれます。通常、整数はデータ構造内で2進数として表され、ほとんどの場合2の補数として表されますが、2進化10進数または1の補数ですが、ほとんどの場合、ユーザーは表現の具体的な選択ではなく抽象化を操作でき、型が本当に抽象的であるかのようにデータを使用できます。

ADTは、操作だけでなく、値のドメイン、および定義された操作に対する制約で構成されます。「インターフェース」は通常、操作のみを指し、場合によっては、事前条件や事後条件など、操作に対するいくつかの制約を指します。ただし、操作間の関係などの他の制約には適用されません。

たとえば、後入れ先出し構造である抽象スタックは、次の3つの操作で定義できpushます。、データ項目をスタックに挿入します。pop、データ項目を削除します。およびpeekまたはtop、スタックの最上位のデータ項目に削除せずにアクセスします。先入れ先出し構造である抽象キューにも、次の3つの操作がenqueueあります。、データ項目をキューに挿入します。dequeue、最初のデータ項目を削除します。front、キュー内の最初のデータ項目にアクセスしてサービスを提供します。これらが完全な定義である場合、これら2つのデータ型とそれらの非常に異なる予想される順序付けの動作を区別する方法はありません。したがって、スタックの場合、各ポップは、まだポップされていない最後にプッシュされたアイテムを常に返す(および削除する)ことを指定し、キューの場合は、(対照的に)ポップが最も最近プッシュされたアイテムで動作することを指定するという制約が導入されます。 。

アルゴリズムの効率を分析する場合、スタックにプッシュされたデータ項目の数に関係なく、すべての操作に同時に時間がかかり、スタックが各要素に一定量のストレージを使用するように指定することもできます。ただし、時間範囲は必ずしもADTの定義の一部とは見なされません。

はじめに

抽象データ型は純粋に理論的なエンティティであり、(とりわけ)抽象アルゴリズムの記述を単純化し、データ構造を分類および評価し、プログラミング言語の型システムを正式に記述するために使用されます。ただし、ADTは、特定のデータ型またはデータ構造によって、さまざまな方法で、多くのプログラミング言語で実装できます。または形式仕様言語で記述されています。ADTは、多くの場合、モジュールとして実装されます。モジュールのインターフェイスは、ADT操作に対応するプロシージャを宣言し、場合によっては制約を説明するコメントを付けます。この情報隠蔽戦略により、クライアントプログラム に影響を与えることなく、モジュールの実装を変更できます。

抽象データ型という用語は、格子、群、環などの多くの代数的構造の一般化されたアプローチと見なすこともできます。[4]抽象データ型の概念は、データ抽象化の概念に関連しており、ソフトウェア開発の契約方法論によるオブジェクト指向プログラミングおよび設計で重要です。[5]

抽象データ型の定義

抽象データ型は、データ型を構成するデータオブジェクトと、これらのオブジェクトを操作する関数の数学モデルとして定義されます。それらを定義するための標準的な規則はありません。「命令型」(または「運用型」)と「機能型」(または「公理的」)の定義スタイルの間には、大きな区分があります。

命令型の定義

命令型プログラミング言語の理論では、抽象データ構造は変更可能なエンティティとして考えられています。つまり、さまざまな時点でさまざまな状態にある可能性があります一部の操作では、ADTの状態が変更される場合があります。したがって、操作が評価される順序は重要であり、同じエンティティに対する同じ操作は、異なる時間に実行された場合、異なる影響を与える可能性があります。これは、コンピューターの指示、または命令型言語のコマンドと手順に類似しています。この見方を強調するために、操作は評価されるのではなく、実行または適用されると言うのが通例です。、抽象的なアルゴリズムを記述するときによく使用される命令型のスタイルに似ています。(詳細については、DonaldKnuthによるTheArt of Computer Programmingを参照してください)。

抽象変数

ADTの命令型の定義は、抽象変数の概念に依存することがよくあります。これは、最も単純で自明でないADTと見なすことができます。抽象変数Vは、次の2つの操作を許可する可変エンティティです。

  • storeVx)ここで、x不特定の性質の値です。
  • fetchV)、それは値を生成します、

その制約で

  • fetchV )は、同じ変数Vに対する最新のVx )演算で使用された値xを常に返しますstore

保存する前のフェッチを禁止したり、特定の結果が得られるように定義したり、(あまり望ましくないが)動作を指定しないままにしたりすることができます。

多くのプログラミング言語と同様に、演算storeVx)はVx(または同様の表記法)と記述されることが多く、値が必要なコンテキストで変数Vfetchが使用される場合は常に(V)が暗黙指定されます。したがって、たとえば、VV + 1は、一般に(VV)+ 1) の省略形であると理解されています。storefetch

この定義では、名前は常に別個のものであると暗黙的に想定されています。変数Uに値を格納しても、別個の変数Vの状態には影響しません。この仮定を明確にするために、次のような制約を追加できます。

  • UVが別個の変数である場合、シーケンス{ storeU x ; storeVystore )}は{ (Vy);と同等です。storeUx)}。

より一般的には、ADT定義は、ADT公理が特定のインスタンスを特定の方法で接続されている(エイリアスを参照)と定義しない限り、1つのADTインスタンスの状態を変更する操作は同じADTの他のインスタンスの状態に影響を与えないと想定することがよくあります。 。最も一般的なそのような接続は次のとおりです。

  • エイリアシング。2つ以上の名前がまったく同じデータオブジェクトを参照します。
  • (同じまたは他の)ADTのインスタンスを含むようにADTが定義されている構成。
  • 参照。ADTは(同じまたは他の)ADTのインスタンスを参照するように定義されています。

たとえば、抽象変数の定義を拡張して抽象レコードを含める場合、レコード変数RのフィールドFに対する操作には、Rとは異なるが、Rの一部でもあるFが明らかに含まれます。

ADTの定義は、そのインスタンスに格納されている値を、それらの変数の範囲と呼ばれる特定のセットXのメンバーに制限する場合があります。たとえば、スタックやキューなどの集合体のADTは、キュー内のすべてのアイテムを整数に、または少なくともすべてを単一のタイプに制限する場合があります(同質性を参照)。プログラミング言語と同様に、このような制限により、アルゴリズムの記述と分析が簡素化され、読みやすさが向上する可能性があります。

この定義は、 V初期化されていない場合、つまりVに対して操作を実行する前に、fetchV)を評価した結果については何も意味しないことに注意してくださいこれを行うアルゴリズムは、(a)ADTがそのような操作を禁止しているため、または(b)その効果がADTによって定義されていないために、無効と見なされる場合があります。ただし、その効率がそのようなaが正当であるという仮定に強く依存し、変数の範囲内の任意の値を返す重要なアルゴリズムがいくつかあります。[要出典]storefetch

インスタンスの作成

一部のアルゴリズムでは、一部のADTの新しいインスタンス(新しい変数や新しいスタックなど)を作成する必要があります。このようなアルゴリズムを説明するために、通常、ADT定義にADTcreateのインスタンスを生成する()演算を含めます。これは、通常、次のような公理を使用します。

  • ()の結果はcreate、アルゴリズムですでに使用されているインスタンスとは異なります。

この公理は、他のインスタンスとの部分的なエイリアシングも除外するように強化される可能性があります[説明が必要]公理などの実際の使用では、create()の実装により、プログラムにアクセスできなくなった以前に作成されたインスタンスを生成できる場合があります。ただし、そのようなインスタンスでさえ「同じ」であると定義することは、特に抽象的には困難です(ただし、再利用されたメモリのブロックでさえ、特定の意味で「同じオブジェクト」にすぎません)。

例:抽象スタック(命令型)

別の例として、抽象スタックの命令型定義では、スタックSの状態を操作によってのみ変更できること を指定できます。

  • pushSx)、ここでx不特定の性質の値です。
  • popS)、結果として値を生成し、

その制約で

  • 任意の値xおよび任意の抽象変数Vに対して、操作のシーケンス{ pushSx); VpopS )}はVxと同等です。

割り当てVxは、定義上、Sの状態を変更できないため、この条件は、VpopS )がSpushを(Sx )の前の状態に復元することを意味します。この条件と抽象変数のプロパティから、たとえば、シーケンスは次のようになります。

{ pushSx); pushSy); UpopS); pushSz); VpopS); WpopS)}

ここで、xy、およびzは任意の値であり、UVWはペアごとに異なる変数であり、 次のようになります。

{ Uy ; Vz ; Wx }

ここでは、スタックインスタンスに対する操作は、他のスタックを含む他のADTインスタンスの状態を変更しないと暗黙的に想定されています。あれは、

  • 任意の値xy、および任意の個別のスタックSおよびTの場合、シーケンス{ pushSx); pushTypush )}は{ (Ty);と同等です。pushSx)}。

抽象スタック定義には通常、ブール値関数emptyS)とcreateスタックインスタンスを返す()演算も含まれ、公理は 次のようになります。

  • create()≠ S以前のスタックS(新しく作成されたスタックは以前のすべてのスタックとは異なります)。
  • emptycreate())(新しく作成されたスタックは空です);
  • not emptypushSx))(スタックに何かをプッシュすると、空ではなくなります)。

シングルインスタンススタイル

ADTは、アルゴリズムの実行中に1つのインスタンスのみが存在するかのように定義され、すべての操作がそのインスタンスに適用された場合がありますが、明示的には示されていません。たとえば、上記の抽象スタックは、既存のスタックのみを操作する操作 x pushおよびpop)を使用して定義できます。このスタイルのADT定義は、暗黙のインスタンスを使用または変更するすべての操作に明示的なインスタンスパラメーター(前の例の Sなど)を追加することで、ADTの複数の共存インスタンスを許可するように簡単に書き換えることができます。

一方、一部のADTは、複数のインスタンスを想定しないと意味のある定義ができません。これは、単一の操作がADTの2つの異なるインスタンスをパラメーターとして受け取る場合です。例として、スタックSTに同じアイテムが同じ順序で含まれて いるかどうかをチェックする操作compareST )を使用して、抽象スタックの定義を拡張することを検討してください。

機能スタイルの定義

関数型プログラミングの精神に近いADTを定義する別の方法は、構造の各状態を個別のエンティティと見なすことです。このビューでは、ADTを変更する操作は、古い状態を引数として取り、結果の一部として新しい状態を返す数学関数としてモデル化されます。命令型の操作とは異なり、これらの関数には副作用がありません。したがって、それらが評価される順序は重要ではなく、同じ引数(同じ入力状態を含む)に適用された同じ操作は、常に同じ結果(および出力状態)を返します。

特に、機能ビューでは、命令変数のセマンティクス(つまり、withfetchおよびstoreoperations)を使用して「抽象変数」を定義する方法(または必要性)はありません。値を変数に格納する代わりに、それらを引数として関数に渡します。

例:抽象スタック(機能)

たとえば、抽象スタックの完全な機能スタイルの定義では、次の3つの操作を使用できます。

  • push:スタック状態と任意の値を取り、スタック状態を返します。
  • top:スタック状態を取り、値を返します。
  • pop:スタック状態を取り、スタック状態を返します。

機能スタイルの定義では、操作は必要ありませんcreate実際、「スタックインスタンス」の概念はありません。スタック状態は、単一のスタック構造の潜在的な状態であると考えることができ、同じ順序で同じ値を含む2つのスタック状態は同一の状態と見なされます。このビューは、ハッシュ短所を持つリンクリストなど、いくつかの具体的な実装の動作を実際に反映しています

()の代わりにcreate、抽象スタックの機能スタイルの定義は、Λや "()"などの特別な記号で指定された特別なスタック状態である空のスタックの存在を想定する場合があります。bottomまたは、引数をとらずにこの特別なスタック状態を返す()演算を定義します。公理はそれを意味することに注意してください

  • push(Λ、x)≠Λ。

スタックの機能スタイルの定義では、述語は必要ありませんempty。代わりに、スタックがΛに等しいかどうかをテストすることで、スタックが空であるかどうかをテストできます。

これらの公理は、 sが。によって返されるスタック状態でない限り、(s)または(s)top効果pop定義ないことに注意してください。スタックを空にしないため、 s =Λの場合、これら2つの操作は未定義(したがって無効)になります。一方、公理(および副作用の欠如)は、 x = yおよびs = tの場合に限り、 (sx)= ty)を意味します。 pushpushpushpush

数学の他のいくつかの分野と同様に、スタック状態は、有限のステップ数で公理から存在を証明できる状態のみであると想定するのが通例です。上記の抽象スタックの例では、このルールは、すべてのスタックが有限の値のシーケンスであり、有限数のpopsの後に空のスタック(Λ)になることを意味します。上記の公理自体は、無限スタック(pop永遠に、異なる状態を生成するたびに編集できる)または循環スタック(有限数のpopsの後に同じ状態に戻る)の存在を除外しません。特にs= sまたはs poppushx)= s for somexただし、特定の操作ではそのようなスタック状態を取得できないため、「存在しない」と見なされます。

複雑さを含めるかどうか

公理に関する振る舞いの他に、ADT操作の定義にそれらのアルゴリズムの複雑さを含めることも可能です。C ++標準テンプレートライブラリの設計者であるAlexanderStepanovは、STL仕様に複雑さの保証を含め、次のように主張しています。

抽象データ型の概念を導入した理由は、交換可能なソフトウェアモジュールを許可するためでした。これらのモジュールが同様の複雑さの動作を共有しない限り、交換可能なモジュールを持つことはできません。あるモジュールを同じ機能動作で複雑さのトレードオフが異なる別のモジュールに置き換えると、このコードのユーザーは不愉快に驚かれることでしょう。私は彼にデータの抽象化について好きなことを何でも言うことができました、そして彼はまだコードを使いたくないでしょう。複雑さのアサーションは、インターフェイスの一部である必要があります。

— アレクサンダー・ステパノフ[6]

抽象データ型付けの利点

カプセル化

抽象化は、ADTの実装が特定の特性と能力を持っているという約束を提供します。これらを知ることは、ADTオブジェクトを利用するために必要なすべてです。

変更のローカリゼーション

ADTの実装が変更された場合、ADTオブジェクトを使用するコードを編集する必要はありません。実装への変更は引き続きインターフェイスに準拠する必要があり、ADTオブジェクトを使用するコードはインターフェイスで指定されたプロパティと機能のみを参照できるため、ADTが使用されるコードを変更せずに実装を変更できます。 。

柔軟性

すべて同じプロパティと機能を備えたADTのさまざまな実装は同等であり、ADTを使用するコードではある程度互換的に使用できます。これにより、さまざまな状況でADTオブジェクトを使用するときに大きな柔軟性が得られます。たとえば、ADTのさまざまな実装は、さまざまな状況でより効率的である可能性があります。それぞれが望ましい状況で使用できるため、全体的な効率が向上します。

典型的な操作

ADTに(おそらく他の名前で)指定されることが多いいくつかの操作は次のとおりです。

  • comparest)、2つのインスタンスの状態がある意味で同等であるかどうかをテストします。
  • hashs )、インスタンスの状態からいくつかの標準ハッシュ関数を計算します。
  • prints)またはshows)、インスタンスの状態の人間が読める表現を生成します。

命令型のADT定義では、多くの場合、

  • create()、ADTの新しいインスタンスを生成します。
  • initializes)、これは、新しく作成されたインスタンスsをさらなる操作のために準備するか、またはそれを何らかの「初期状態」にリセットします。
  • copyst)、インスタンスsをtと同等の状態にします。
  • clonet)、screate()、copyst )を実行し、 sを返します
  • frees)またはdestroys )、 sによって使用されるメモリおよびその他のリソースを再利用します。

freeADTは「メモリを使用」しない理論上のエンティティであるため、この操作は通常、関連性や意味がありません。ただし、ADTを使用するアルゴリズムで使用されるストレージを分析する必要がある場合に必要になることがあります。その場合、各ADTインスタンスが使用するメモリの量を、その状態の関数として指定する追加の公理と、によってプールに返されるメモリの量が必要ですfree

多種多様なアプリケーションで有用であることが証明されているいくつかの一般的なADTは、

これらのADTのそれぞれは、必ずしも同等ではないが、多くの方法と変形で定義される可能性があります。たとえば、抽象スタックには、countプッシュされてまだポップされていないアイテムの数を示す操作がある場合とない場合があります。この選択は、クライアントだけでなく実装にも違いをもたらします。

抽象グラフィカルデータ型

コンピュータグラフィックス用のADTの拡張が1979年に提案されました:[ 7]抽象グラフィカルデータ型(AGDT)。Nadia MagnenatThalmannDanielThalmannによって紹介されましたAGDTは、構造化された方法でグラフィックオブジェクトを構築する機能を備えたADTの利点を提供します。

実装

ADTの実装とは、抽象操作ごとに1つのプロシージャまたは関数を提供することを意味します。ADTインスタンスは、ADTの仕様に従って、これらのプロシージャによって操作される 具体的なデータ構造によって表されます。

通常、いくつかの異なる具体的なデータ構造を使用して、同じADTを実装する方法はたくさんあります。したがって、たとえば、抽象スタックは、リンクリストまたは配列によって実装できます。

クライアントが実装に依存するのを防ぐために、ADTは1つ以上のモジュールに不透明(OPAQUE)型としてパッケージ化されることが多く、そのインターフェイスには操作のシグネチャ(パラメータと結果の数とタイプ)のみが含まれます。モジュールの実装(つまり、プロシージャの本体と使用される具体的なデータ構造)は、モジュールのほとんどのクライアントから隠すことができます。これにより、クライアントに影響を与えることなく実装を変更できます。実装が公開されている場合は、代わりに透過データ型と呼ばれます。

ADTを実装する場合、各インスタンス(命令型の定義)または各状態(機能型の定義)は通常、ある種のハンドルで表されます。[8]

C ++Javaなどの最新のオブジェクト指向言語は、抽象データ型の形式をサポートしています。クラスが型として使用される場合、それは非表示の表現を参照する抽象型です。このモデルでは、ADTは通常、クラスとして実装され、ADTの各インスタンスは通常そのクラスのオブジェクトです。モジュールのインターフェースは通常、コンストラクターを通常のプロシージャーとして宣言し、他のほとんどのADT操作をメソッドとして宣言します。そのクラスの。ただし、このようなアプローチでは、ADTにある複数の表現型バリアントを簡単にカプセル化することはできません。また、オブジェクト指向プログラムの拡張性を損なう可能性があります。インターフェイスを型として使用する純粋なオブジェクト指向プログラムでは、型は表現ではなく動作を参照します。

例:抽象スタックの実装

例として、 Cプログラミング言語での上記の抽象スタックの実装を次に示します

命令型インターフェース

命令型のインターフェースは次のようになります。

typedef struct stack_Rep stack_Rep ; //タイプ:スタックインスタンス表現(不透明なレコード)typedef stack_Rep * stack_T ; //タイプ:スタックインスタンスへのハンドル(不透明なポインター)typedef void * stack_Item ; //タイプ:スタックインスタンスに格納されている値(任意のアドレス)          
                 
                   

stack_T stack_create void ); //新しい空のスタックインスタンスを作成しますvoidstack_push stack_T s stack_Item x ); //スタックの一番上にアイテムを追加しますstack_Itemstack_pop stack_T s ; //スタックから一番上のアイテムを削除し、それを返しますbool stack_empty stack_T s ); //スタックが空かどうかをチェックします                
     
            
                

このインターフェイスは、次のように使用できます。

#include <stack.h>           //スタックインターフェースを含む 

stack_T s = stack_create (); //新しい空のスタックインスタンスを作成しますintx = 17 ;    
   
stack_push s x ); //スタックの一番上にxのアドレスを追加しますvoid * y = stack_pop s ); // xのアドレスをスタックから削除し、それを返しますif stack_empty s )){ } //スタックが空の場合は何かを行います           
        
        

このインターフェースは、さまざまな方法で実装できます。上記のADTの正式な定義では、スタックが使用できるスペースの量や、各操作にかかる時間が指定されていないため、実装は任意に非効率になる可能性があります。また、 xs )の呼び出し後もスタック状態sが存在し続けるかどうかも指定しませんpop

実際には、正式な定義では、スペースがプッシュされてまだポップされていないアイテムの数に比例することを指定する必要があります。また、上記のすべての操作は、その数に関係なく、一定の時間内に終了する必要があります。これらの追加仕様に準拠するために、実装では、リンクリスト、または2つの整数(アイテム数と配列サイズ)とともに配列(動的なサイズ変更を使用)を使用できます。

機能的なインターフェース

関数型ADT定義は、関数型プログラミング言語に適しています。その逆も同様です。ただし、Cのような命令型言語でも、機能スタイルのインターフェイスを提供できます。次に例を示します。

typedef struct stack_Rep stack_Rep ; //タイプ:スタック状態表現(不透明なレコード)typedef stack_Rep * stack_T ; //タイプ:スタック状態へのハンドル(不透明なポインター)typedef void * stack_Item ; //タイプ:スタック状態の値(任意のアドレス)             
                    
                      

stack_T stack_empty void ); //空のスタック状態を返しますstack_Tstack_push stack_T s stack_Item x ; //スタック状態の一番上にアイテムを追加し、結果のスタック状態を返しますstack_T stack_pop stack_T s ); //スタック状態から最上位のアイテムを削除し、結果のスタック状態を返しますstack_Item stack_top stack_T s ); //スタック状態の最上位アイテムを返します                    
     
                  
               

ADTライブラリ

C ++やJavaなどの多くの最新のプログラミング言語には、上記のようないくつかの一般的なADTを実装する標準ライブラリが付属しています。

組み込みの抽象データ型

一部のプログラミング言語の仕様は、特定の組み込みデータ型の表現について意図的にあいまいであり、それらに対して実行できる操作のみを定義しています。したがって、これらのタイプは「組み込みADT」と見なすことができます。例としては、AwkLuaPerlなどの多くのスクリプト言語の配列があります。これらは抽象リストの実装と見なすことができます。

も参照してください

メモ

  1. ^ 抽象代数の整数の特徴付けと比較してください。

引用

  1. ^ Dale&Walker 1996、p。3.3。
  2. ^ Dale&Walker 1996、p。4.4。
  3. ^ Liskov&Zilles1974
  4. ^ ルドルフ・リドゥル(2004)。抽象代数スプリンガー。ISBN 978-81-8128-149-4、第7章、セクション40。
  5. ^ 「オブジェクト指向プログラミングとは何ですか?」採用| アップワーク2015-05-05 2016年10月28日取得
  6. ^ アラバマ州スティーブンス(1995年3月)。「アルスティーブンスはアレックスステパノフにインタビューします」ドブ博士の日記2015年1月31日取得
  7. ^ D. Thalmann、N。MagnenatThalmann(1979)。抽象グラフィカルデータ型の設計と実装IEEE。土井10.1109 /CMPSAC.1979.762551、Proc。第3回国際コンピュータソフトウェアおよびアプリケーション会議(COMPSAC'79)、IEEE、シカゴ、米国、pp.519-524
  8. ^ ロバートセッジウィック(1998)。Cのアルゴリズムアディソン/ウェスリー。ISBN 978-0-201-31452-6、定義4.4。

参考文献

  • リスコフ、バーバラ; Zilles、Stephen(1974)。「抽象データ型を使用したプログラミング」。高級言語に関するACMSIGPLANシンポジウムの議事録SIGPLAN通知。9. pp。50–59。CiteSeerX10.1.1.136.3043 _ 土井10.1145 /800233.807045
  • デール、ネル; ウォーカー、ヘンリーM.(1996)。抽象データ型:仕様、実装、およびアプリケーションジョーンズ&バートレットラーニング。ISBN 978-0-66940000-7

さらに読む

外部リンク