Abstrakter Datentyp - Abstract data type

In der Informatik ist ein abstrakter Datentyp ( ADT ) ein mathematisches Modell für Datentypen . Ein abstrakter Datentyp wird durch sein Verhalten ( Semantik ) aus der Sicht eines Benutzers der Daten definiert, und zwar im Hinblick auf mögliche Werte, mögliche Operationen auf Daten dieser Art und das Verhalten dieser Operationen. Dieses mathematische Modell steht im Gegensatz zu Datenstrukturen , die konkrete Darstellungen von Daten sind und die aus der Sicht eines Implementierers und nicht eines Benutzers sind.

Formal kann ein ADT als eine "Klasse von Objekten definiert werden, deren logisches Verhalten durch eine Menge von Werten und eine Menge von Operationen definiert ist"; dies ist analog zu einer algebraischen Struktur in der Mathematik. Was mit "Verhalten" gemeint ist, variiert je nach Autor, wobei die beiden Haupttypen formaler Verhaltensspezifikationen die axiomatische (algebraische) Spezifikation und ein abstraktes Modell sind; diese entsprechen der axiomatischen Semantik bzw. der operationalen Semantik einer abstrakten Maschine . Einige Autoren beziehen auch die Rechenkomplexität ("Kosten") mit ein, sowohl hinsichtlich der Zeit (für Rechenoperationen) als auch des Raums (für die Darstellung von Werten). In der Praxis sind viele gängige Datentypen keine ADTs, da die Abstraktion nicht perfekt ist und die Benutzer Probleme wie den arithmetischen Überlauf berücksichtigen müssen , die auf die Darstellung zurückzuführen sind. Ganzzahlen werden beispielsweise häufig als Werte mit fester Breite (32-Bit- oder 64-Bit-Binärzahlen) gespeichert und erfahren daher einen ganzzahligen Überlauf, wenn der Maximalwert überschritten wird.

ADTs sind ein theoretisches Konzept in der Informatik, das beim Entwurf und der Analyse von Algorithmen , Datenstrukturen und Softwaresystemen verwendet wird und nicht den spezifischen Merkmalen von Computersprachen entspricht – Mainstream-Computersprachen unterstützen formal spezifizierte ADTs nicht direkt. Jedoch entsprechen verschiedene Sprachmerkmale bestimmten Aspekten von ADTs und werden leicht mit ADTs im eigentlichen Sinne verwechselt; Dazu gehören abstrakte Typen , undurchsichtige Datentypen , Protokolle und Design by Contract . ADTs wurden erstmals 1974 von Barbara Liskov und Stephen N. Zilles als Teil der Entwicklung der CLU- Sprache vorgeschlagen.

Beispiele

Beispielsweise ganze Zahlen sind ein ADT, als die Werte definiert , ..., -2, -1, 0, 1, 2, ..., und durch die Operationen der Addition, Subtraktion, Multiplikation und Division, zusammen mit mehr als , kleiner als usw., die sich nach bekannter Mathematik (unter Beachtung der Ganzzahldivision ) verhalten , unabhängig davon, wie die Ganzzahlen vom Computer dargestellt werden. Explizit beinhaltet "Verhalten" das Befolgen verschiedener Axiome (Assoziativität und Kommutativität der Addition usw.) und Voraussetzungen für Operationen (kann nicht durch Null dividiert werden). Typischerweise werden ganze Zahlen in einer Datenstruktur als Binärzahlen dargestellt , meistens als Zweierkomplement , können aber auch binär codiert dezimal oder im Einerkomplement sein , aber der Benutzer wird von der konkreten Wahl der Darstellung abstrahiert und kann die Daten einfach als Datentypen.

Ein ADT besteht nicht nur aus Operationen, sondern auch aus Werten der zugrunde liegenden Daten und aus Einschränkungen für die Operationen. Eine "Schnittstelle" bezieht sich typischerweise nur auf die Operationen und vielleicht auf einige der Einschränkungen der Operationen, insbesondere auf Vorbedingungen und Nachbedingungen, aber nicht auf andere Einschränkungen, wie beispielsweise Beziehungen zwischen den Operationen.

Zum Beispiel könnte ein abstrakter Stack , der eine Last-In-First-Out-Struktur ist, durch drei Operationen definiert werden: push, die ein Datenelement in den Stack einfügt; pop, das ein Datenelement daraus entfernt; und peekoder top, das auf ein Datenelement oben auf dem Stapel zugreift, ohne es zu entfernen. Eine abstrakte Warteschlange , die eine First-In-First-Out-Struktur ist, hätte auch drei Operationen: enqueue, die ein Datenelement in die Warteschlange einfügt; dequeue, das das erste Datenelement daraus entfernt; und front, das auf das erste Datenelement in der Warteschlange zugreift und es bedient. Es gibt keine Möglichkeit, diese beiden Datentypen zu unterscheiden, es sei denn, es wird eine mathematische Einschränkung eingeführt, die für einen Stapel festlegt, dass jeder Pop immer das zuletzt gesendete Element zurückgibt, das noch nicht gepoppt wurde. Bei der Analyse der Effizienz von Algorithmen, die Stacks verwenden, kann man auch angeben, dass alle Operationen gleich lange dauern, unabhängig davon, wie viele Datenelemente in den Stack verschoben wurden, und dass der Stack für jedes Element eine konstante Speichermenge verwendet.

Einführung

Abstrakte Datentypen sind rein theoretische Einheiten, die (unter anderem) verwendet werden, um die Beschreibung abstrakter Algorithmen zu vereinfachen, Datenstrukturen zu klassifizieren und auszuwerten und um die Typsysteme von Programmiersprachen formal zu beschreiben . Jedoch kann ein ADT wird implementiert durch bestimmte Datentypen oder Datenstrukturen , in vielerlei Hinsicht und in vielen Programmiersprachen; oder in einer formalen Spezifikationssprache beschrieben . ADTs werden oft als Module implementiert : Die Schnittstelle des Moduls deklariert Prozeduren, die den ADT-Operationen entsprechen, manchmal mit Kommentaren , die die Einschränkungen beschreiben. Diese Strategie zum Verbergen von Informationen ermöglicht es, die Implementierung des Moduls zu ändern, ohne die Client- Programme zu stören .

Der Begriff abstrakter Datentyp kann auch als verallgemeinerter Ansatz einer Reihe von algebraischen Strukturen wie Gittern, Gruppen und Ringen angesehen werden. Der Begriff abstrakter Datentypen hängt mit dem Konzept der Datenabstraktion zusammen , das in der objektorientierten Programmierung und im Entwurf von Vertragsmethoden für die Softwareentwicklung wichtig ist .

Einen abstrakten Datentyp definieren

Ein abstrakter Datentyp ist definiert als ein mathematisches Modell der Datenobjekte, aus denen ein Datentyp besteht, sowie der Funktionen, die auf diesen Objekten operieren. Es gibt keine Standardkonventionen für deren Definition. Man kann grob zwischen "imperativen" und "funktionalen" Definitionsstilen unterscheiden.

Definition im Imperativ-Stil

In der Philosophie der imperativen Programmiersprachen wird eine abstrakte Datenstruktur als veränderliche Einheit verstanden – das heißt , sie kann sich zu unterschiedlichen Zeiten in verschiedenen Zuständen befinden . Einige Operationen können den Status des ADT ändern; Daher ist die Reihenfolge, in der Operationen ausgewertet werden, wichtig, und dieselbe Operation auf denselben Entitäten kann unterschiedliche Auswirkungen haben, wenn sie zu unterschiedlichen Zeiten ausgeführt wird – genau wie die Anweisungen eines Computers oder die Befehle und Prozeduren einer imperativen Sprache. Um diese Ansicht zu unterstreichen, ist es üblich zu sagen, dass die Operationen ausgeführt oder angewendet und nicht ausgewertet werden . Der Imperativ-Stil wird häufig verwendet, wenn abstrakte Algorithmen beschrieben werden. (Siehe The Art of Computer Programming von Donald Knuth für weitere Details)

Abstrakte Variable

Definitionen von ADT im Imperativstil hängen oft vom Konzept einer abstrakten Variablen ab , die als die einfachste nicht-triviale ADT angesehen werden kann. Eine abstrakte Variable V ist eine veränderliche Entität, die zwei Operationen zulässt:

  • store( V , x ) wobei x ein Wert nicht näher bezeichneter Natur ist;
  • fetch( V ), das ergibt einen Wert,

mit der Einschränkung, dass

  • fetch( V ) gibt immer den Wert x zurück , der in der letzten store( V , x ) Operation für dieselbe Variable V verwendet wurde .

Wie in so viele Programmiersprachen, die Operation store( V , x ) wird oft geschrieben Vx (oder eine ähnliche Schreibweise) und fetch( V ) wird angedeutet , wenn eine Variable V in einem Kontext verwendet wird , in dem ein Wert erforderlich ist. So kann beispielsweise VV + 1 wird allgemein als eine Abkürzung für verstanden store( V , fetch( V ) + 1).

In dieser Definition wird implizit angenommen, dass das Speichern eines Wertes in einer Variablen U keine Auswirkung auf den Zustand einer eindeutigen Variablen V hat . Um diese Annahme explizit zu machen, könnte man die Einschränkung hinzufügen, dass

  • wenn U und V unterschiedliche Variablen sind, wird die Folge { store( U , x ); store( V , y )} ist äquivalent zu { store( V , y ); store( U , x )}.

Allgemeiner gesagt gehen ADT-Definitionen oft davon aus, dass jede Operation, die den Zustand einer ADT-Instanz ändert, keine Auswirkungen auf den Zustand einer anderen Instanz hat (einschließlich anderer Instanzen desselben ADT) – es sei denn, die ADT-Axiome implizieren, dass die beiden Instanzen verbunden sind ( aliased ) in diesem Sinne. Wenn beispielsweise die Definition einer abstrakten Variablen um abstrakte Datensätze erweitert wird , muss die Operation, die ein Feld aus einer Datensatzvariablen R auswählt, eine Variable V ergeben, die mit diesem Teil von R als Alias ​​versehen ist .

Die Definition einer abstrakten Variablen V kann auch die gespeicherten Werte x auf Mitglieder einer bestimmten Menge X beschränken , die als Bereich oder Typ von V bezeichnet wird . Wie in Programmiersprachen können solche Einschränkungen die Beschreibung und Analyse von Algorithmen vereinfachen und ihre Lesbarkeit verbessern.

Beachten Sie, dass diese Definition nichts bedeutet über das Ergebnis der Auswertung fetch( V ) , wenn V ist nicht initialisierten , das heißt, bevor sie eine Durchführung storeBetrieb auf V . Ein Algorithmus, der dies tut, wird normalerweise als ungültig angesehen, da seine Wirkung nicht definiert ist. (Es gibt jedoch einige wichtige Algorithmen, deren Effizienz stark von der Annahme abhängt, dass ein solches fetchzulässig ist und einen beliebigen Wert im Bereich der Variablen zurückgibt.)

Instanzerstellung

Einige Algorithmen müssen neue Instanzen einiger ADTs erstellen (z. B. neue Variablen oder neue Stacks). Um solche Algorithmen zu beschreiben, schließt man normalerweise in die ADT-Definition eine create()-Operation ein, die eine Instanz des ADT liefert, normalerweise mit Axiomen äquivalent zu

  • das Ergebnis von create() unterscheidet sich von jeder Instanz, die vom Algorithmus verwendet wird.

Dieses Axiom kann verstärkt werden, um auch teilweises Aliasing mit anderen Instanzen auszuschließen. Andererseits erlaubt dieses Axiom immer noch Implementierungen von create(), um eine zuvor erstellte Instanz zu liefern, die für das Programm unzugänglich geworden ist.

Beispiel: abstrakter Stapel (Imperativ)

Als weiteres Beispiel könnte eine Definition eines abstrakten Stapels im Imperativ-Stil angeben, dass der Zustand eines Stapels S nur durch die Operationen geändert werden kann

  • push( S , x ), wobei x ein Wert nicht näher bezeichneter Natur ist;
  • pop( S ), was als Ergebnis einen Wert ergibt,

mit der Einschränkung, dass

  • Für jeden Wert x und jede abstrakte Variable V ist die Operationsfolge { push( S , x ); Vpop( S )} entspricht Vx .

Da die Zuordnung Vx per definitionem nicht den Zustand ändern kann , S , bedeutet diese Bedingung , dass Vpop( S ) stellt S in den Zustand vor dem hatte push( S , x ). Aus dieser Bedingung und aus den Eigenschaften abstrakter Variablen folgt beispielsweise, dass die Folge

{ push( S , x ); push( S , y ); Upop( S ); push( S , z ); Vpop( S ); Wpop( S ) }

wobei x , y und z beliebige Werte sind und U , V , W paarweise unterschiedliche Variablen sind, ist äquivalent zu

{ Uy ; Vz ; Wx }

Hier wird implizit angenommen, dass Operationen auf einer Stack-Instanz den Zustand einer anderen ADT-Instanz, einschließlich anderer Stacks, nicht ändern; das ist,

  • Für alle Werte x , y und alle unterschiedlichen Stapel S und T ist die Sequenz { push( S , x ); push( T , y )} ist äquivalent zu { push( T , y ); push( S , x )}.

Eine abstrakte Stack-Definition enthält normalerweise auch eine boolesche Funktion empty( S ) und eine create( )-Operation, die eine Stack-Instanz zurückgibt, mit Axiomen äquivalent zu

  • create() ≠ S für jeden vorherigen Stapel S (ein neu erstellter Stapel unterscheidet sich von allen vorherigen Stapeln);
  • empty( create()) (ein neu erstellter Stack ist leer);
  • not empty( push( S , x )) (Wenn Sie etwas in einen Stapel schieben, wird es nicht leer).

Einzelinstanz-Stil

Manchmal wird ein ADT so definiert, als ob nur eine Instanz davon während der Ausführung des Algorithmus existiert hätte und alle Operationen auf diese Instanz angewendet wurden, die nicht explizit notiert ist. Zum Beispiel könnte der obige abstrakte Stack mit Operationen push( x ) und pop( ) definiert worden sein, die auf dem einzigen existierenden Stack operieren . ADT-Definitionen in diesem Stil können leicht umgeschrieben werden, um mehrere koexistierende Instanzen des ADT zuzulassen, indem ein expliziter Instanzparameter (wie S im vorherigen Beispiel) zu jeder Operation hinzugefügt wird, die die implizite Instanz verwendet oder modifiziert.

Andererseits können einige ADTs nicht sinnvoll definiert werden, ohne mehrere Instanzen anzunehmen. Dies ist der Fall, wenn eine einzelne Operation zwei verschiedene Instanzen des ADT als Parameter verwendet. Betrachten Sie als Beispiel, die Definition des abstrakten Stapels mit einer Operation compare( S , T ) zu erweitern, die überprüft, ob die Stapel S und T die gleichen Elemente in der gleichen Reihenfolge enthalten.

Definition im funktionalen Stil

Eine andere Möglichkeit, ein ADT näher am Geist der funktionalen Programmierung zu definieren , besteht darin, jeden Zustand der Struktur als separate Einheit zu betrachten. In dieser Ansicht wird jede Operation, die den ADT modifiziert, als mathematische Funktion modelliert , die den alten Zustand als Argument verwendet und den neuen Zustand als Teil des Ergebnisses zurückgibt. Im Gegensatz zu den imperativen Operationen haben diese Funktionen keine Nebenwirkungen . Daher ist die Reihenfolge, in der sie ausgewertet werden, unerheblich, und dieselbe Operation, die auf dieselben Argumente (einschließlich derselben Eingabezustände) angewendet wird, gibt immer dieselben Ergebnisse (und Ausgabezustände) zurück.

Insbesondere in der funktionalen Sicht gibt es keine Möglichkeit (oder Notwendigkeit), eine "abstrakte Variable" mit der Semantik zwingender Variablen (nämlich mit fetchund storeOperationen) zu definieren. Anstatt Werte in Variablen zu speichern, übergibt man sie als Argumente an Funktionen.

Beispiel: abstrakter Stack (funktional)

Eine vollständige Definition eines abstrakten Stapels im funktionalen Stil könnte beispielsweise die drei Operationen verwenden:

  • push: nimmt einen Stack-Zustand und einen beliebigen Wert, gibt einen Stack-Zustand zurück;
  • top: nimmt einen Stack-Zustand an, gibt einen Wert zurück;
  • pop: nimmt einen Stack-Zustand, gibt einen Stack-Zustand zurück.

In einer funktionalen Stildefinition ist keine createOperation erforderlich. Tatsächlich gibt es keinen Begriff von "Stack-Instanz". Die Stack-Zustände können als potenzielle Zustände einer einzelnen Stack-Struktur betrachtet werden, und Zwei-Stack-Zustände, die dieselben Werte in derselben Reihenfolge enthalten, werden als identische Zustände betrachtet. Diese Ansicht spiegelt tatsächlich das Verhalten einiger konkreter Implementierungen wider, z. B. verknüpfte Listen mit Hash-Nachteilen .

Anstelle von create() kann eine funktionale Definition eines abstrakten Stapels die Existenz eines speziellen Stapelzustands annehmen, des leeren Stapels , gekennzeichnet durch ein spezielles Symbol wie Λ oder "()"; oder definieren Sie eine bottom()-Operation, die keine Argumente akzeptiert und diesen speziellen Stack-Zustand zurückgibt. Beachten Sie, dass die Axiome implizieren, dass

  • push(Λ, x ) Λ.

In einer funktionalen Definition eines Stapels braucht man kein emptyPrädikat: stattdessen kann man testen, ob ein Stapel leer ist, indem man testet, ob er gleich ist.

Beachten Sie, dass diese Axiome die Wirkung von top( s ) oder pop( s ) nicht definieren , es sei denn, s ist ein von a zurückgegebener Stack-Zustand push. Da pushder Stapel nicht leer bleibt, sind diese beiden Operationen undefiniert (daher ungültig), wenn s = Λ ist. Andererseits implizieren die Axiome (und das Fehlen von Nebenwirkungen) dass push( s , x ) = push( t , y ) genau dann, wenn x = y und s = t ist .

Wie in einigen anderen Zweigen der Mathematik wird auch hier angenommen, dass die Stapelzustände nur solche sind, deren Existenz aus den Axiomen in endlich vielen Schritten bewiesen werden kann. Im obigen abstrakten Stack-Beispiel bedeutet diese Regel, dass jeder Stack eine endliche Folge von Werten ist, die nach endlich vielen pops zum leeren Stack (Λ) wird . Die obigen Axiome allein schließen die Existenz von unendlichen Stapeln (die für popimmer bearbeitet werden können und jedes Mal einen anderen Zustand ergeben) oder kreisförmigen Stapeln (die nach einer endlichen Anzahl von pops in den gleichen Zustand zurückkehren ) nicht aus. Insbesondere schließen sie Zustände s nicht aus, so dass pop( s ) = s oder push( s , x ) = s für einige x . Da man solche Stack-Zustände mit den gegebenen Operationen jedoch nicht erhalten kann, wird davon ausgegangen, dass sie "nicht existieren".

Ob Komplexität einzubeziehen ist

Neben dem Verhalten in Bezug auf Axiome ist es auch möglich, deren algorithmische Komplexität in die Definition einer ADT-Operation einzubeziehen . Alexander Stepanov , Designer der C++ Standard Template Library , hat Komplexitätsgarantien in die STL-Spezifikation aufgenommen und argumentiert:

Der Grund für die Einführung des Begriffs abstrakter Datentypen war, austauschbare Softwaremodule zuzulassen. Sie können keine austauschbaren Module haben, es sei denn, diese Module weisen ein ähnliches Komplexitätsverhalten auf. Wenn ich ein Modul durch ein anderes Modul mit dem gleichen Funktionsverhalten, aber mit unterschiedlichen Kompromissen bei der Komplexität ersetze, wird der Benutzer dieses Codes unangenehm überrascht sein. Ich könnte ihm alles über die Datenabstraktion sagen, was mir gefällt, und er würde den Code trotzdem nicht verwenden wollen. Komplexitätszusicherungen müssen Teil der Schnittstelle sein.

—  Alexander Stepanov

Vorteile der abstrakten Datentypisierung

Verkapselung

Abstraktion verspricht, dass jede Implementierung des ADT bestimmte Eigenschaften und Fähigkeiten hat; diese zu kennen ist alles, was erforderlich ist, um ein ADT-Objekt zu verwenden.

Lokalisierung von Veränderungen

Code, der ein ADT-Objekt verwendet, muss nicht bearbeitet werden, wenn die Implementierung des ADT geändert wird. Da alle Änderungen an der Implementierung weiterhin der Schnittstelle entsprechen müssen und da Code, der ein ADT-Objekt verwendet, nur auf Eigenschaften und Fähigkeiten verweisen darf, die in der Schnittstelle angegeben sind, können Änderungen an der Implementierung vorgenommen werden, ohne dass Änderungen am Code erforderlich sind, wenn der ADT verwendet wird .

Flexibilität

Verschiedene Implementierungen des ADT mit denselben Eigenschaften und Fähigkeiten sind äquivalent und können in Code, der den ADT verwendet, etwas austauschbar verwendet werden. Dies bietet eine große Flexibilität bei der Verwendung von ADT-Objekten in verschiedenen Situationen. Zum Beispiel können verschiedene Implementierungen des ADT in verschiedenen Situationen effizienter sein; es ist möglich, jede in der Situation zu verwenden, in der sie bevorzugt werden, wodurch die Gesamteffizienz erhöht wird.

Typische Operationen

Einige Operationen, die oft für ADTs (möglicherweise unter anderen Namen) angegeben werden, sind

  • compare( s , t ), das testet, ob die Zustände zweier Instanzen in gewissem Sinne äquivalent sind;
  • hash( s ), die eine Standard- Hash-Funktion aus dem Zustand der Instanz berechnet ;
  • print( s ) oder show( s ), die eine für Menschen lesbare Darstellung des Zustands der Instanz erzeugen.

In ADT-Definitionen im Imperativstil findet man oft auch

  • create(), die eine neue Instanz des ADT ergibt;
  • initialize( s ), das eine neu erstellte Instanz s für weitere Operationen vorbereitet oder in einen "Anfangszustand" zurücksetzt;
  • copy( s , t ), das die Instanz s in einen Zustand versetzt, der dem von t entspricht ;
  • clone( t ), das screate(), copy( s , t ) ausführt und s zurückgibt ;
  • free( s ) oder destroy( s ), die den Speicher und andere von s verwendete Ressourcen zurückfordern .

Die freeOperation ist normalerweise nicht relevant oder sinnvoll, da ADTs theoretische Einheiten sind, die keinen "Speicher verwenden". Dies kann jedoch erforderlich sein, wenn der Speicher analysiert werden muss, der von einem Algorithmus verwendet wird, der den ADT verwendet. In diesem Fall benötigt man zusätzliche Axiome, die angeben, wie viel Speicher jede ADT-Instanz in Abhängigkeit von ihrem Zustand verwendet und wie viel davon von an den Pool zurückgegeben wird free.

Beispiele

Einige gängige ADTs, die sich in einer Vielzahl von Anwendungen bewährt haben, sind

Jeder dieser ADTs kann auf viele Arten und Varianten definiert werden, die nicht unbedingt äquivalent sind. Ein abstrakter Stack kann beispielsweise eine countOperation haben oder nicht, die angibt, wie viele Elemente gepusht und noch nicht gepoppt wurden. Diese Wahl macht nicht nur für seine Kunden einen Unterschied, sondern auch für die Implementierung.

Abstrakter grafischer Datentyp

1979 wurde eine Erweiterung von ADT für Computergrafik vorgeschlagen: ein abstrakter grafischer Datentyp (AGDT). Es wurde von Nadia Magnenat Thalmann und Daniel Thalmann eingeführt . AGDTs bieten die Vorteile von ADTs mit der Möglichkeit, grafische Objekte strukturiert aufzubauen.

Implementierung

Das Implementieren eines ADT bedeutet, für jede abstrakte Operation eine Prozedur oder Funktion bereitzustellen. Die ADT-Instanzen werden durch eine konkrete Datenstruktur dargestellt , die von diesen Prozeduren gemäß den ADT-Spezifikationen manipuliert wird.

Normalerweise gibt es viele Möglichkeiten, denselben ADT unter Verwendung mehrerer verschiedener konkreter Datenstrukturen zu implementieren. So kann beispielsweise ein abstrakter Stack durch eine verkettete Liste oder durch ein Array realisiert werden .

Um zu verhindern, dass Clients von der Implementierung abhängig sind, wird ein ADT oft als undurchsichtiger Datentyp in einem oder mehreren Modulen verpackt , deren Schnittstelle nur die Signatur (Anzahl und Typen der Parameter und Ergebnisse) der Operationen enthält. Die Implementierung des Moduls – nämlich die Körper der Prozeduren und die konkrete verwendete Datenstruktur – kann dann den meisten Clients des Moduls verborgen bleiben. Dadurch ist es möglich, die Implementierung zu ändern, ohne die Clients zu beeinträchtigen. Wenn die Implementierung verfügbar gemacht wird, wird sie stattdessen als transparenter Datentyp bezeichnet.

Bei der Implementierung eines ADT wird jede Instanz (in Definitionen im Imperativ-Stil) oder jeder Zustand (in Definitionen im funktionalen Stil) normalerweise durch eine Art Handle dargestellt .

Moderne objektorientierte Sprachen wie C++ und Java unterstützen eine Form abstrakter Datentypen. Wenn eine Klasse als Typ verwendet wird, handelt es sich um einen abstrakten Typ, der auf eine versteckte Repräsentation verweist. In diesem Modell wird ein ADT normalerweise als Klasse implementiert , und jede Instanz des ADT ist normalerweise ein Objekt dieser Klasse. Die Schnittstelle des Moduls deklariert normalerweise die Konstruktoren als normale Prozeduren und die meisten anderen ADT-Operationen als Methoden dieser Klasse. Ein solcher Ansatz kapselt jedoch nicht ohne weiteres mehrere Darstellungsvarianten, die in einem ADT gefunden werden. Es kann auch die Erweiterbarkeit objektorientierter Programme untergraben. In einem rein objektorientierten Programm, das Schnittstellen als Typen verwendet, beziehen sich Typen auf Verhaltensweisen, nicht auf Darstellungen.

Beispiel: Implementierung des abstrakten Stacks

Als Beispiel ist hier eine Implementierung des abstrakten Stapels oben in der C - Programmiersprache .

Benutzeroberfläche im Imperativ-Stil

Eine Schnittstelle im Imperativ-Stil könnte sein:

typedef struct stack_Rep stack_Rep;       // type: stack instance representation (opaque record)
typedef stack_Rep* stack_T;               // type: handle to a stack instance (opaque pointer)
typedef void* stack_Item;                 // type: value stored in stack instance (arbitrary address)

stack_T stack_create(void);               // creates a new empty stack instance
void stack_push(stack_T s, stack_Item x); // adds an item at the top of the stack
stack_Item stack_pop(stack_T s);          // removes the top item from the stack and returns it
bool stack_empty(stack_T s);              // checks whether stack is empty

Diese Schnittstelle könnte wie folgt verwendet werden:

#include <stack.h>          // includes the stack interface

stack_T s = stack_create(); // creates a new empty stack instance
int x = 17;
stack_push(s, &x);          // adds the address of x at the top of the stack
void* y = stack_pop(s);     // removes the address of x from the stack and returns it
if (stack_empty(s)) { }     // does something if stack is empty

Diese Schnittstelle kann auf viele Arten implementiert werden. Die Implementierung kann beliebig ineffizient sein, da die obige formale Definition des ADT weder angibt, wie viel Platz der Stapel verwenden darf, noch wie lange jede Operation dauern soll. Sie gibt auch nicht an, ob der Stack-Zustand s nach einem Aufruf xpop( s ) weiter besteht.

In der Praxis sollte die formale Definition angeben, dass das Leerzeichen proportional zur Anzahl der verschobenen und noch nicht geöffneten Elemente ist; und dass jede der oben genannten Operationen in einer konstanten Zeit abgeschlossen werden muss, unabhängig von dieser Zahl. Um diese zusätzlichen Spezifikationen zu erfüllen, könnte die Implementierung eine verknüpfte Liste oder ein Array (mit dynamischer Größenänderung) zusammen mit zwei ganzen Zahlen (einer Elementanzahl und der Arraygröße) verwenden.

Funktionale Benutzeroberfläche

ADT-Definitionen im funktionalen Stil sind besser für funktionale Programmiersprachen geeignet und umgekehrt. Man kann jedoch auch in einer imperativen Sprache wie C eine funktionale Schnittstelle bereitstellen. Zum Beispiel:

typedef struct stack_Rep stack_Rep;          // type: stack state representation (opaque record)
typedef stack_Rep* stack_T;                  // type: handle to a stack state (opaque pointer)
typedef void* stack_Item;                    // type: value of a stack state (arbitrary address)

stack_T stack_empty(void);                   // returns the empty stack state
stack_T stack_push(stack_T s, stack_Item x); // adds an item at the top of the stack state and returns the resulting stack state
stack_T stack_pop(stack_T s);                // removes the top item from the stack state and returns the resulting stack state
stack_Item stack_top(stack_T s);             // returns the top item of the stack state

ADT-Bibliotheken

Viele moderne Programmiersprachen wie C++ und Java werden mit Standardbibliotheken geliefert, die mehrere gängige ADTs implementieren, wie die oben aufgeführten.

Integrierte abstrakte Datentypen

Die Spezifikation einiger Programmiersprachen ist absichtlich vage bezüglich der Darstellung bestimmter integrierter Datentypen und definiert nur die Operationen, die mit ihnen ausgeführt werden können. Daher können diese Typen als "integrierte ADTs" angesehen werden. Beispiele sind die Arrays in vielen Skriptsprachen wie Awk , Lua und Perl , die als Implementierung der abstrakten Liste angesehen werden können.

Siehe auch

Anmerkungen

Zitate

Verweise

Weiterlesen

Externe Links