抽象データ型
有理数は計算機においてはそのまま扱うことはできない。有理数の抽象データ型は以下のように定義できる。
コンストラクタ: 2つの整数 a {\displaystyle a} 、 b {\displaystyle b} を用いて有理数の抽象データ型のインスタンスを作成する。ここで a {\displaystyle a} は分子で b {\displaystyle b} は分母である。
関数: 加算,減算,乗算,除算,指数計算,比較,約分,実数への変換
完全な記述にするためには、それぞれの関数はデータに言及して記述されるべきである。例えば、有理数 a / b {\displaystyle a/b} と c / d {\displaystyle c/d} を乗算するときには結果は a c / b d {\displaystyle ac/bd} と定義される。通常は入力、出力、実行前条件、実行後条件、抽象データ型に対する仮定も記述される。
抽象データ構造とは、実際のデータ構造による実装に関わらず、操作の集合とその計算量により定義されるデータのための抽象的な領域のことである。
具体的なデータ構造の選択がアルゴリズムの効率的な実装にとって重要である一方、抽象データ構造の選択は効率的なアルゴリズムの設計とその計算量の推定にとって極めて重要である。
この概念はプログラミング言語の理論で用いられる抽象データ型の概念に非常に近い。多くの抽象データ構造や抽象データ型の名前は具体的なデータ構造の名前と一致する。