In der Informatik ist ein abstrakter Datentyp (ADT) ein mathematisches Modell für eine bestimmte Klasse von Datenstrukturen, die ähnliches Verhalten haben; oder für bestimmte Datentypen von einer oder mehr Programmiersprachen, die ähnliche Semantik haben. Ein abstrakter Datentyp wird indirekt nur durch die Operationen definiert, die darauf und durch mathematische Einschränkungen auf die Effekten durchgeführt (und vielleicht gekostet werden können) jener Operationen.

Zum Beispiel konnte eine abstrakte Stapel-Datenstruktur durch drei Operationen definiert werden: das fügt einen Datenartikel auf die Struktur ein, der einen Artikel daraus herauszieht (mit der Einschränkung, dass jeder Knall immer den am meisten kürzlich gestoßenen Artikel zurückgibt, der noch nicht knallen gelassen worden ist), und, der Daten oben auf der Struktur erlaubt, ohne Eliminierung untersucht zu werden. Wenn man die Leistungsfähigkeit von Algorithmen analysiert, die Stapel verwenden, kann man auch angeben, dass alle Operationen dieselbe Zeit nehmen, egal wie viele Sachen in den Stapel gestoßen worden sind, und dass der Stapel einen unveränderlichen Betrag der Lagerung für jedes Element verwendet.

Abstrakte Datentypen sind rein theoretische Entitäten, verwendet (unter anderem), um die Beschreibung von abstrakten Algorithmen zu vereinfachen, Datenstrukturen zu klassifizieren und zu bewerten, und die Typ-Systeme von Programmiersprachen formell zu beschreiben. Jedoch kann ein ADT durch spezifische Datentypen oder Datenstrukturen auf viele Weisen und auf viele Programmiersprachen durchgeführt werden; oder hat auf einer formellen Spezifizierungssprache beschrieben. ADTs werden häufig als Module durchgeführt: Die Schnittstelle des Moduls erklärt Verfahren, die den ADT Operationen manchmal mit Anmerkungen entsprechen, die die Einschränkungen beschreiben. Diese Informationsverheimlichungsstrategie erlaubt der Durchführung des Moduls, geändert zu werden, ohne die Kundenprogramme zu stören.

Der Begriff-Auszug-Datentyp kann auch als eine verallgemeinerte Annäherung mehrerer algebraischer Strukturen, wie Gitter, Gruppen und Ringe betrachtet werden. Das kann als ein Teil des Sachgebiets der künstlichen Intelligenz behandelt werden. Der Begriff von abstrakten Datentypen ist mit dem Konzept der Datenabstraktion verbunden, die in der objektorientierten Programmierung und dem Design durch Vertragsmethodiken für die Softwareentwicklung wichtig ist.

Das Definieren eines abstrakten Datentyps (ADT)

Ein abstrakter Datentyp wird als ein mathematisches Modell der Datengegenstände definiert, die einen Datentyp sowie die Funktionen zusammensetzen, die auf diesen Gegenständen funktionieren.

Es gibt keine Standardvereinbarung, um sie zu definieren. Eine breite Abteilung kann zwischen "befehlenden" und "funktionellen" Definitionsstilen angezogen werden.

Befehlende abstrakte Datentyp-Definitionen

In der "befehlenden" Ansicht, die an der Philosophie von befehlenden Programmiersprachen näher ist, wird eine abstrakte Datenstruktur als eine Entität konzipiert, die — das Meinen veränderlich ist, dass es in verschiedenen Staaten zu verschiedenen Zeiten sein kann. Einige Operationen können den Staat des ADT ändern; deshalb ist die Ordnung, in der Operationen bewertet werden, wichtig, und dieselbe Operation auf denselben Entitäten kann verschiedene Effekten, wenn durchgeführt, zu verschiedenen Zeiten — gerade wie die Instruktionen eines Computers, oder die Befehle und Verfahren einer befehlenden Sprache haben. Um diese Ansicht zu unterstreichen, ist es üblich, um zu sagen, dass die Operationen durchgeführt oder angewandt, aber nicht bewertet werden. Der befehlende Stil wird häufig verwendet, wenn man abstrakte Algorithmen beschreibt.

Abstrakte Variable

ADT befehlende Definitionen hängen häufig vom Konzept einer abstrakten Variable ab, die als der einfachste nichttriviale ADT betrachtet werden kann. Eine abstrakte Variable V ist eine veränderliche Entität, die zwei Operationen zulässt:

• (V, x), wo x ein Wert der unangegebenen Natur ist; und
• (V), das gibt einen Wert nach;

mit der Einschränkung das

• (V) immer gibt den Wert x verwendet im neusten (V, x) Operation auf derselben Variable V zurück.

Als auf so vielen Programmiersprachen wird die Operation (V, x) häufig V  x (oder eine ähnliche Notation) geschrieben, und (V) wird einbezogen, wann auch immer eine Variable V in einem Zusammenhang verwendet wird, wo ein Wert erforderlich ist. So, zum Beispiel, wie man allgemein versteht, sind V  V + 1 eine Schnellschrift für (V, (V) + 1).

In dieser Definition wird es implizit angenommen, dass, einen Wert in eine Variable versorgend, U keine Wirkung auf den Staat einer verschiedenen Variable V hat. Um diese Annahme ausführlich zu machen, konnte man die Einschränkung das hinzufügen

• wenn U und V verschiedene Variablen, die Folge {(U, x) sind; (V, y)} ist zu {(V, y) gleichwertig; (U, x)}.

Mehr allgemein nehmen ADT Definitionen häufig an, dass jede Operation, die den Staat eines ADT Beispiels ändert, keine Wirkung auf den Staat jedes anderen Beispiels (einschließlich anderer Beispiele desselben ADT) hat — wenn die ADT Axiome nicht andeuten, dass die zwei Beispiele (aliased) in diesem Sinn verbunden werden. Zum Beispiel, wenn sie die Definition der abstrakten Variable erweitert, um abstrakte Aufzeichnungen einzuschließen, muss die Operation, die ein Feld von einer Rekordvariable R auswählt, eine Variable V nachgeben, der aliased zu diesem Teil von R ist.

Die Definition einer abstrakten Variable V kann auch die versorgten Werte x auf Mitglieder eines spezifischen Satzes X, genannt die Reihe oder den Typ V einschränken. Als auf Programmiersprachen können solche Beschränkungen die Beschreibung und Analyse von Algorithmen vereinfachen, und ihre Lesbarkeit verbessern.

Bemerken Sie, dass diese Definition nichts über das Ergebnis einbezieht, (V) zu bewerten, wenn V, d. h. vor dem Durchführen jeder Operation auf V uninitialisiert ist. Ein Algorithmus, der so tut, wird gewöhnlich ungültig betrachtet, weil seine Wirkung nicht definiert wird. (Jedoch gibt es einige wichtige Algorithmen, deren Leistungsfähigkeit stark abhängt in der Annahme, dass solch ein gesetzlich ist, und einen willkürlichen Wert in der Reihe der Variable zurückgibt.)

Beispiel-Entwicklung

Einige Algorithmen müssen neue Beispiele von einem ADT (wie neue Variablen oder neue Stapel) schaffen. Um solche Algorithmen zu beschreiben, schließt man gewöhnlich in die ADT Definition a Operation ein, die ein Beispiel des ADT gewöhnlich mit zu gleichwertigen Axiomen nachgibt

• das Ergebnis ist von jedem Beispiel S im Gebrauch durch den Algorithmus verschieden.

Dieses Axiom kann gestärkt werden, um auch teilweisen aliasing mit anderen Beispielen auszuschließen. Andererseits erlaubt dieses Axiom noch Durchführungen , ein vorher geschaffenes Beispiel nachzugeben, das unzugänglich zum Programm geworden ist.

Vorbedingungen, Postbedingungen und invariants

In befehlend-artigen Definitionen werden die Axiome häufig durch Vorbedingungen ausgedrückt, die angeben, wenn eine Operation durchgeführt werden kann; Postbedingungen, die die Staaten des ADT vorher und nach der Ausführung jeder Operation verbinden; und invariants, die Eigenschaften der ADT angeben, die durch die Operationen nicht geändert werden.

Beispiel: abstrakter Stapel (Befehlsform)

Als ein anderes Beispiel konnte eine befehlende Definition eines abstrakten Stapels angeben, dass der Staat eines Stapels S nur durch die Operationen modifiziert werden kann

• (S, x), wo x ein Wert der unangegebenen Natur ist; und
• (S), das gibt einen Wert infolgedessen nach;

mit der Einschränkung das

• Für jeden Wert x und jede abstrakte Variable V, die Folge von Operationen {(S, x); V  (S)} sind zu {V  x} gleichwertig;

Seit der Anweisung {können V  x} nicht definitionsgemäß den Staat S ändern, diese Bedingung deutet an, dass {V  (S)} S zum Staat wieder herstellen, den es vor {(S, x)} hatte. Von dieser Bedingung und von den Eigenschaften von abstrakten Variablen folgt es, zum Beispiel, dem die Folge

: {(S, x); (S, y); U  (S); (S, z); V  (S); W  (S); }\

wo x, y, und z irgendwelche Werte sind, und U, V, W pairwise verschiedene Variablen sind, ist zu gleichwertig

: {U  y; V  z; W  x }\

Hier wird es implizit angenommen, dass Operationen auf einem Stapel-Beispiel den Staat keines anderen ADT Beispiels einschließlich anderer Stapel modifizieren; das, ist

• Für irgendwelche Werte x, y, und irgendwelche verschiedenen Stapel S und T, die Folge {(S, x); (T, y)} ist zu {(T, y) gleichwertig; (S, x)}.

Eine ADT Stapel-Definition schließt gewöhnlich auch eine GeBoolean-schätzte Funktion (S) und Operation ein, die ein Stapel-Beispiel mit zu gleichwertigen Axiomen zurückgibt

•  S für jeden Stapel S (ist ein kürzlich geschaffener Stapel von allen vorherigen Stapeln verschieden)
• () (ist ein kürzlich geschaffener Stapel leer)

• ((S, x)) (macht das Stoßen von etwas in einen Stapel es nichtleer)

Stil des einzelnen Beispiels

Manchmal wird ein ADT definiert, als ob nur ein Beispiel davon während der Ausführung des Algorithmus bestanden hat, und alle Operationen auf dieses Beispiel angewandt wurden, das nicht ausführlich in Notenschrift geschrieben wird. Zum Beispiel könnte der abstrakte Stapel oben mit Operationen (x) definiert worden sein und , die auf "dem" einzigen vorhandenen Stapel funktionieren. ADT Definitionen in diesem Stil können leicht umgeschrieben werden, um vielfache koexistierende Beispiele des ADT, durch das Hinzufügen eines ausführlichen Beispiel-Parameters (wie S im vorherigen Beispiel) zu jeder Operation zuzulassen, die verwendet oder das implizite Beispiel modifiziert.

Andererseits kann ein ADTs nicht bedeutungsvoll definiert werden, ohne vielfache Beispiele anzunehmen. Das ist der Fall, wenn eine einzelne Operation zwei verschiedene Beispiele des ADT als Rahmen nimmt. Für ein Beispiel, denken Sie, die Definition des Stapels ADT mit einer Operation zu vermehren (S, T), der überprüft, ob die Stapel S und T dieselben Sachen in derselben Ordnung enthalten.

Funktionelle ADT Definitionen

Eine andere Weise, einen ADT zu definieren, der am Geist der funktionellen Programmierung näher ist, soll jeden Staat der Struktur als eine getrennte Entität denken. In dieser Ansicht wird jede Operation, die den ADT modifiziert, als eine mathematische Funktion modelliert, die den alten Staat als ein Argument nimmt, und den neuen Staat als ein Teil des Ergebnisses zurückgibt. Verschieden von den "befehlenden" Operationen haben diese Funktionen keine Nebenwirkungen. Deshalb ist die Ordnung, in der sie bewertet werden, immateriell, und dieselbe Operation, die auf dieselben Argumente (einschließlich derselben Eingangsstaaten) angewandt ist, wird immer dieselben Ergebnisse (und Produktionsstaaten) zurückgeben.

In der funktionellen Ansicht, insbesondere gibt es keinen Weg (oder Bedürfnis), um eine "abstrakte Variable" mit der Semantik von befehlenden Variablen (nämlich, mit und Operationen) zu definieren. Anstatt Werte in Variablen zu versorgen, passiert man ihnen als Argumente für Funktionen.

Beispiel: abstrakter (funktioneller) Stapel

Zum Beispiel konnte eine ganze funktionell-artige Definition eines Stapels ADT die drei Operationen verwenden:

• : nimmt einen Stapel-Staat und einen willkürlichen Wert, gibt einen Stapel-Staat zurück;
• : nimmt einen Stapel-Staat, gibt einen Wert zurück;
• : nimmt einen Stapel-Staat, gibt einen Stapel-Staat zurück;

mit den folgenden Axiomen:

• ((s, x)) = x (verlässt das Stoßen eines Artikels auf einen Stapel es oben)
• ((s, x)) = s (macht die Wirkung auf)

In einer funktionell-artigen Definition gibt es kein Bedürfnis nach einer Operation. Tatsächlich gibt es keinen Begriff des "Stapel-Beispiels". Von den Stapel-Staaten kann als seiend potenzielle Staaten einer einzelnen Stapel-Struktur gedacht werden, und, wie man betrachtet, sind zwei Stapel-Staaten, die dieselben Werte in derselben Ordnung enthalten, identische Staaten. Diese Ansicht spiegelt wirklich das Verhalten von einigen konkreten Durchführungen wider, wie verbundene Listen mit dem Kuddelmuddel lernt.

Statt eine funktionelle Definition eines Stapels kann ADT die Existenz eines speziellen Stapel-Staates, des leeren Stapels annehmen, der durch ein spezielles Symbol wie Λ oder" benannt ist"; oder definieren Sie Operation, die keine Argumente nimmt und diesen speziellen Stapel-Staat zurückgibt. Bemerken Sie, dass die Axiome das einbeziehen

• (Λ, x)  Λ\

In einer funktionellen Definition eines Stapels braucht man kein Prädikat: Statt dessen kann man prüfen, ob ein Stapel durch die Prüfung leer ist, ob es Λ gleich ist.

Bemerken Sie, dass diese Axiome die Wirkung von (s) oder (s) nicht definieren, wenn s kein durch a zurückgegebener Stapel-Staat ist. Seit Blättern der nichtleere Stapel sind jene zwei Operationen (folglich Invalide) wenn s = Λ unbestimmt. Andererseits deuten die Axiome (und der Mangel an Nebenwirkungen) dass (s, x) = (t, y) wenn und nur wenn x = y und s = t an.

Als in einigen anderen Zweigen der Mathematik ist es üblich, um auch anzunehmen, dass die Stapel-Staaten nur diejenigen sind, deren Existenz von den Axiomen in einer begrenzten Zahl von Schritten bewiesen werden kann. Im Stapel ADT Beispiel oben bedeutet diese Regel, dass jeder Stapel eine begrenzte Folge von Werten ist, die der leere Stapel (Λ) nach einer begrenzten Zahl von s wird. Durch sich schließen die Axiome oben die Existenz von unendlichen Stapeln nicht aus (der Hrsg. für immer sein kann, jedes Mal einen verschiedenen Staat nachgebend), oder kreisförmige Stapel (dass Rückkehr zu demselben Staat nach einer begrenzten Zahl von s). Insbesondere sie schließen Staaten s solch dass (s) = s oder (s, x) = s für einen x nicht aus. Jedoch, da man solche Stapel-Staaten mit den gegebenen Operationen nicht erhalten kann, wie man annimmt, bestehen sie "nicht".

Datenabstraktion bezieht sich auf, nur wesentliche Auskunft zum Außenwort gebend und ihre Hintergrunddetails verbergend d. h. die erforderliche Information im Programm zu vertreten, ohne die Details zu präsentieren.

Datenabstraktion ist eine Programmierung (und Design) Technik, die sich auf die Trennung der Schnittstelle und Durchführung verlässt.

Wollen wir ein echtes Lebensbeispiel eines Fernsehens nehmen, von dem Sie sich drehen können und, den Kanal zu ändern, um das Volumen anzupassen, und Außenbestandteile wie Sprecher, Videorecorder und DVD-Spieler hinzuzufügen, ABER Sie wissen nicht, dass es inneres Detail ist d. h. wissen Sie nicht, wie es Signale über die Luft oder durch ein Kabel erhält, wie es sie übersetzt, und sie schließlich auf dem Schirm zeigt.

So können wir sagen, dass ein Fernsehen seine innere Durchführung von seiner Außenschnittstelle trennt. Sie können seine Schnittstellen, wie der Macht-Knopf, der Kanalwechsler und die Volumen-Kontrolle verwenden, ohne Kenntnisse seines internals zu haben.

Jetzt, wenn wir in Bezug auf C ++ Programmierung, C ++ sprechen, stellen Klassen großes Niveau der Datenabstraktion zur Verfügung. Sie stellen genügend öffentliche Methoden der Außenwelt zur Verfügung, um die Funktionalität des Gegenstands zu verwenden und Gegenstand-Daten (d. h. Staat) zu manipulieren, ohne wirklich zu wissen, wie die Klasse innerlich durchgeführt worden ist.

Zum Beispiel kann Ihr Programm einen Anruf zur Sorte Funktion machen ohne zu wissen, welchen Algorithmus die Funktion wirklich verwendet, um die gegebenen Werte zu sortieren. Tatsächlich konnte sich die zu Grunde liegende Durchführung der Sortieren-Funktionalität zwischen Ausgaben der Bibliothek, und ändern, so lange die Schnittstelle dasselbe bleibt, wird Ihr Funktionsanruf noch arbeiten.

In C ++ verwenden wir Klassen, um unsere eigenen abstrakten Datentypen (ADT) zu definieren. Zum Beispiel können Sie den cout Gegenstand der Klasse iostream zu Strom-Daten zur Standardproduktion verwenden:

1. einschließen

das Verwenden namespace std;

int Hauptsache

{\

cout

Hier brauchen Sie nicht zu verstehen, wie cout den Text auf dem Schirm des Benutzers zeigt. Sie müssen nur die öffentliche Schnittstelle wissen, und die zu Grunde liegende Durchführung von cout ist frei sich zu ändern.

Zugriffsetiketten machen Abstraktion geltend:

In C ++ verwenden wir Zugriffsetiketten, um die abstrakte Schnittstelle zur Klasse zu definieren. Eine Klasse kann Null oder mehr Zugriffsetiketten enthalten:

Mit einem öffentlichen Etikett definierte Mitglieder sind für alle Teile des Programms zugänglich. Die Datenabstraktionsansicht von einem Typ wird von seinen öffentlichen Mitgliedern definiert.

Mit einem privaten Etikett definierte Mitglieder sind nicht zugänglich, um zu codieren, der die Klasse verwendet. Eine private Abteilung verbirgt die Durchführung vor dem Code, der den Typ verwendet.

Es gibt keine Beschränkungen dessen, wie oft ein Zugriffsetikett erscheinen kann. Jedes Etikett gibt das Zugriffsniveau der folgenden Mitglied-Definitionen an. Das angegebene Zugriffsniveau bleibt in Kraft, bis auf das folgende Etikett gestoßen wird, oder die richtige geschweifte Schlussklammer des Klassenkörpers gesehen wird.

Vorteile der Datenabstraktion:

Datenabstraktion stellt zwei wichtige Vorteile zur Verfügung:

Klasse internals wird vor unachtsamen Benutzerniveau-Fehlern geschützt, die den Staat des Gegenstands verderben könnten.

Die Klassendurchführung kann sich mit der Zeit als Antwort auf sich ändernde Voraussetzungen oder Programmfehler-Berichte entwickeln, ohne Änderung im Benutzerniveau-Code zu verlangen.

Indem

er Datenmitglieder nur in der privaten Abteilung der Klasse definiert, ist der Klassenautor frei, Änderungen in den Daten vorzunehmen. Nur die Klassen eigener Code würde untersucht werden müssen, um zu sehen, was die Änderung betrifft, können haben. Wenn Daten öffentlich waren, könnte jede Funktion, die direkt auf die Datenmitglieder der alten Darstellung zugegriffen hat, die neue Darstellung einschlagen.

Datenabstraktionsbeispiel:

Jeder C ++ Programm, wo Sie eine Klasse mit öffentlichen und privaten Mitgliedern durchführen, ist ein Beispiel der Datenabstraktion. Denken Sie das folgende Beispiel:

einschließen das Verwenden namespace std;

Klassenviper {\

Publikum:

//Konstrukteur

Viper (interne Nummer i = 0)

{\

ganz = ich;

}\

//verbinden Sie zur Außenwelt

Leere addNum (int Zahl)

{\

ganz + = Zahl;

}\ //verbinden Sie zur Außenwelt

interne Nummer getTotal

{\

kehren Sie ganz zurück;

};

privat:

//verborgene Daten von der Außenseite der Welt

int Summe;

};

int Hauptsache {\

Viper a;

a.addNum (10);

a.addNum (20);

a.addNum (30);

cout

Wenn der obengenannte Code kompiliert und durchgeführt wird, erzeugt er folgendes Ergebnis:

Ganze 60

Über der Klasse fügt Zahlen zusammen hinzu, und gibt die Summe zurück. Die öffentlichen Mitglieder addNum und getTotal sind die Schnittstellen zur Außenwelt, und ein Benutzer muss sie wissen, die Klasse zu verwenden. Das private ganze Mitglied ist etwas, was der Benutzer darüber nicht zu wissen braucht, aber für die Klasse erforderlich ist, um richtig zu funktionieren.

Das Entwerfen der Strategie:

Abstraktion trennt Code in die Schnittstelle und Durchführung. So, während Sie Ihren Bestandteil entwerfen, müssen Sie Schnittstelle unabhängig der Durchführung halten, so dass, wenn Sie sich ändern, zu Grunde liegende Durchführung dann verbindet, würde intakt bleiben.

In diesem Fall, was auch immer Programme diese Schnittstellen verwenden, würden sie nicht zusammengepresst und würden gerade eine Wiederkompilation mit der letzten Durchführung brauchen.

Typische Operationen

Einige Operationen, die häufig für ADTs angegeben werden (vielleicht unter anderen Namen) sind

• (s, t), der prüft, ob zwei Strukturen in einem Sinn gleichwertig sind;
• (s), das schätzt etwas Standardkuddelmuddel-Funktion vom Staat des Beispiels;
• (s) oder (s), der eine menschlich-lesbare Darstellung des Staates der Struktur erzeugt.

In befehlend-artigen ADT Definitionen findet man häufig auch

• , der ein neues Beispiel des ADT nachgibt;
• (s), das bereitet ein neuerschaffenes Beispiel s auf weitere Operationen vor, oder fasst es zu einem "anfänglichen Staat" neu;
• (s, t), der Beispiel s in einer Zustandentsprechung zu diesem von t stellt;
• (t), das führt s  , (s, t) durch, und gibt s zurück;
• (s) oder (s), der das Gedächtnis und die anderen durch s verwendeten Mittel zurückfordert;

Die Operation ist nicht normalerweise wichtig oder bedeutungsvoll, da ADTs theoretische Entitäten sind, die Gedächtnis nicht "verwenden". Jedoch kann es notwendig sein, wenn man die Lagerung analysieren muss, die durch einen Algorithmus verwendet ist, der den ADT verwendet. In diesem Fall braucht man zusätzliche Axiome, die angeben, wie viel Gedächtnis jedes ADT Beispiel Gebrauch, als eine Funktion seines Staates, und wie viel seiner in die Lache dadurch zurückgegeben wird.

Beispiele

Einige allgemeine ADTs, die sich nützlich in einer großen Vielfalt von Anwendungen erwiesen haben, sind

• Behälter
• Deque
• Liste
• Karte
• Mehrkarte
• Mehrsatz
• Vorzugswarteschlange
• Warteschlange
• Satz
• Stapel
• Schnur
• Baum

Jeder dieser ADTs kann auf viele Weisen und Varianten, nicht notwendigerweise gleichwertig definiert werden. Zum Beispiel ein Stapel kann ADT oder kann keine Operation haben, die erzählt, wie viele Sachen gestoßen und noch nicht knallen gelassen worden sind. Diese Wahl macht einen Unterschied nicht nur für seine Kunden sondern auch für die Durchführung.

Durchführung

Das Einführen eines ADT bedeutet, ein Verfahren oder Funktion für jede abstrakte Operation zur Verfügung zu stellen. Die ADT Beispiele werden durch eine konkrete Datenstruktur vertreten, die durch jene Verfahren gemäß den Spezifizierungen des ADT manipuliert wird.

Gewöhnlich gibt es viele Weisen, denselben ADT mit mehreren verschiedenen konkreten Datenstrukturen durchzuführen. So, zum Beispiel, kann ein abstrakter Stapel durch eine verbundene Liste oder durch eine Reihe durchgeführt werden.

Eine ADT Durchführung wird häufig als ein oder mehr Module paketiert, deren Schnittstelle nur die Unterschrift (Zahl und Typen der Rahmen und Ergebnisse) von den Operationen enthält. Die Durchführung des Moduls — nämlich, die Körper der Verfahren und der konkreten Datenstruktur verwendet — kann dann vor den meisten Kunden des Moduls verborgen werden. Das macht es möglich, die Durchführung zu ändern, ohne die Kunden zu betreffen.

Wenn das Einführen eines ADT, jedes Beispiel (in befehlend-artigen Definitionen) oder jeder Staat (in funktionell-artigen Definitionen) gewöhnlich durch einen Griff von einer Sorte vertreten wird.

Moderne objektorientierte Sprachen, wie C ++ und Java, unterstützen eine Form von abstrakten Datentypen. Wenn eine Klasse als ein Typ verwendet wird, ist es ein abstrakter Typ, der sich auf eine verborgene Darstellung bezieht. In diesem Modell wird ein ADT normalerweise als eine Klasse durchgeführt, und jedes Beispiel des ADT ist ein Gegenstand dieser Klasse. Die Schnittstelle des Moduls erklärt normalerweise die Konstrukteure als gewöhnliche Verfahren und die meisten anderen ADT Operationen als Methoden dieser Klasse. Jedoch fasst solch eine Annäherung vielfache in einem ADT gefundene Vertretungsvarianten nicht leicht kurz zusammen. Es kann auch die Dehnbarkeit von objektorientierten Programmen untergraben.

In einem reinen objektorientierten Programm, das Schnittstellen als Typen verwendet, verweisen Typen auf Handlungsweisen nicht Darstellungen.

Beispiel: Durchführung des Stapels ADT

Als ein Beispiel ist hier eine Durchführung des Stapels ADT oben auf der C Programmiersprache.

Befehlend-artige Schnittstelle

Eine befehlend-artige Schnittstelle könnte sein:

typedef struct stack_Rep stack_Rep;/*-Typ: Beispiel-Darstellung (eine undurchsichtige Aufzeichnung). * /

typedef stack_Rep *stack_T;/*-Typ: Behandeln Sie zu einem Stapel-Beispiel (ein undurchsichtiger Zeigestock). * /

Typedef-Leere *stack_Item;/*-Typ: Wert, der im Stapel (willkürliche Adresse) versorgt werden kann. * /

stack_T stack_create (Leere);/* Schaffen neues Stapel-Beispiel, am Anfang leer. * /

Leere stack_push (stack_T s, stack_Item e);/* Fügen einen Artikel an der Oberseite vom Stapel Hinzu. * /

stack_Item stack_pop (stack_T s);/* Entfernen den Spitzenartikel vom Stapel und geben es zurück. * /

interne Nummer stack_empty (stack_T ts);/*-Kontrolle, ob Stapel leer ist. * /

</Quelle>

Diese Durchführung konnte auf die folgende Weise verwendet werden:

einschließen

stack_T t = stack_create ;/* Schaffen ein Stapel-Beispiel. * /

interne Nummer foo = 17;/* Eine willkürliche Gegebenheit. * /

t = stack_push (t, &foo);/*-Stoß die Adresse von 'foo' auf den Stapel. * /

…

Leere *e = stack_pop (t);/* Bekommen den Spitzenartikel und löschen ihn vom Stapel. * /

wenn (stack_empty (t)) {…}/* etwas Tun, wenn Stapel leer ist. * /

…</Quelle>

Diese Schnittstelle kann auf viele Weisen durchgeführt werden. Die Durchführung kann willkürlich ineffizient sein, da die formelle Definition des ADT oben nicht angibt, wie viel Raum der Stapel verwenden kann, noch wie lange jede Operation nehmen sollte. Es gibt auch nicht an, ob der Stapel feststellt, dass t fortsetzt, nach einem Anruf s  (t) zu bestehen.

In der Praxis sollte die formelle Definition angeben, dass der Raum zur Zahl von Sachen gestoßen und noch nicht knallen gelassen proportional ist; und dass jede der Operationen oben in einer unveränderlichen Zeitdauer unabhängig von dieser Zahl fertig sein muss. Um diese zusätzlichen Spezifizierungen zu erfüllen, konnte die Durchführung eine verbundene Liste oder eine Reihe (damit verwenden, dynamisch in der Größe anzupassen), zusammen mit zwei ganzen Zahlen (eine Artikel-Zählung und die Reihe-Größe)

Funktionell-artige Schnittstelle

Funktionell-artige ADT Definitionen sind für funktionelle Programmiersprachen, und umgekehrt passender. Jedoch kann man eine funktionelle Stil-Schnittstelle sogar auf einer befehlenden Sprache wie C zur Verfügung stellen. Zum Beispiel:

typedef struct stack_Rep stack_Rep;/*-Typ: Schobern Sie Zustanddarstellung (eine undurchsichtige Aufzeichnung) auf. * /

typedef stack_Rep *stack_T;/*-Typ: Behandeln Sie zu einem Stapel-Staat (ein undurchsichtiger Zeigestock). * /

Typedef-Leere *stack_Item;/*-Typ: Artikel (willkürliche Adresse). * /

stack_T stack_empty (Leere);/*-Umsatz der leere Stapel-Staat. * /

stack_T stack_push (stack_T s, stack_Item x);/* Fügt x an der Oberseite von s Hinzu, gibt den resultierenden Staat zurück. * /

stack_Item stack_top (stack_T s);/*-Umsatz der Artikel zurzeit an der Oberseite von s. * /

stack_T stack_pop (stack_T s);/* Entfernen den Spitzenartikel von s, gibt den resultierenden Staat zurück. * /

</Quelle>

Das Hauptproblem besteht darin, dass C an Müll-Sammlung Mangel hat, und das diesen Stil macht, unpraktisch zu programmieren; außerdem sind Speicherzuteilungsroutinen in C langsamer als Zuteilung in einem typischen Müllmann, so ist der Leistungseinfluss von so vielen Zuteilungen noch größer.

ADT Bibliotheken

Viele moderne Programmiersprachen, wie C ++ und Java, kommen mit Standardbibliotheken, die mehrere allgemeine ADTs, wie diejenigen durchführen, die oben verzeichnet sind.

Eingebaute abstrakte Datentypen

Die Spezifizierung von einigen Programmiersprachen ist über die Darstellung von bestimmten eingebauten Datentypen absichtlich vage, nur die Operationen definierend, die auf ihnen getan werden können. Deshalb können jene Typen als "eingebauter ADTs" angesehen werden. Beispiele sind die Reihe auf vielen scripting Sprachen, wie Awk, Lua und Perl, der als eine Durchführung der Karte oder Tabelle ADT betrachtet werden kann.

Siehe auch

• Anfängliche Algebra
• Konzept (allgemeine Programmierung)
• Design durch den Vertrag
• Formelle Methoden
• Funktionelle Spezifizierung
• Ersatz-Grundsatz von Liskov
• Objektorientierte Programmierung
• Typ-System
• Typ-Theorie
• Algebraischer Datentyp
• Verallgemeinerter algebraischer Datentyp

Weiter

Außenverbindungen

• Abstrakter Datentyp im NIST Wörterbuch von Algorithmen und Datenstrukturen