Home > Informatik > Stufe Q1 > ADTs

14.2 Abstrakte Datentypen

Allgemeines - Abstrakte Datentypen - Stack - Queue - Dictionary - List - ADTs im Abitur - Axiome

Allgemeines

Eine Datenstruktur hat einen bestimmen Aufbau (daher auch das Wort "Struktur" in "Datenstruktur"). Ein Array beispielsweise besteht aus einer definierten Anzahl von Elementen des gleichen Datentyps, die im Arbeitsspeicher des Rechners hintereinander angeordnet sind. Wenn die Speicheradresse des ersten Array-Elements bekannt ist, so kann mit Hilfe des Index die Adresse eines gesuchten Elementes berechnet werden.

In der Informatik hat sich nun aber der Begriff "Abstrakter Datentyp" durchgesetzt. Diese Begriff steht in engem Zusammenhang mit dem Begriff der algorithmischen Abstraktion, der Datenabstraktion und vor allem der Datenkapselung; im Grunde beschreibt ein abstrakter Datentyp nichts anderes als eine Datenkapsel.

Wenn wir einen abstrakten Datentyp (kurz: ADT) definieren, müssen wir uns überhaupt nicht um die "Struktur" oder "innere Organisation" oder "Implementierung" der Daten kümmern, wir legen einfach nur fest, welche Operationen dieser ADT ausführen können soll. Mehr nicht.

ADT Stack / Stapel

Das wollen wir uns mal an einem Beispiel klar machen. Einer der bekanntesten Abstrakten Datentypen ist der Stack oder Stapelspeicher:

asdf

Ein Stapel Teller

Ein Stapel Teller ist ein gutes Beispiel für einen Stack. Der ADT Stack wird durch folgende Operationen definiert:

  • Init(): Erzeugt einen leeren Stack.
  • Push(x): Das Element x wird hinzugefügt.
  • Pop(): Das zuletzt hinzugefügte Element wird entfernt.
  • Top(): Der Wert des zuletzt hinzugefügten Elementes wird zurückgeliefert.
  • Empty(): Falls der Stack leer ist, wird TRUE zurückgeliefert, sonst FALSE.

Diese fünf Operationen beschreiben die Arbeitsweise eines Stacks vollständig. Bei der Definition des ADT werden nur die Operationen angegeben. Wie die Operationen intern arbeiten oder wie sie implementiert wurden, ist dabei völlig uninteressant. Spontan würde man einen solchen Stack in Java sicherlich mit Hilfe eines Arrays implementieren, aber auch völlig andere Möglichkeiten wären denkbar. Hier tritt wieder das Prinzip der Datenkapselung in den Vordergrund.

ADT Queue / Schlange

Ein weiteres wichtiges Beispiel für einen Abstrakten Datentypen ist die Queue oder Schlange. Hier die vollständige Definition dieses ADTs:

  • Init(): Erzeugt eine leere Queue.
  • Enqueue(x): Das Element x wird hinzugefügt.
  • Dequeue(): Das zuerst hinzugefügte Element wird entfernt.
  • Front(): Der Wert des zuerst hinzugefügten Elementes wird zurückgeliefert.
  • Empty(): Falls die Queue leer ist, wird TRUE zurückgeliefert, sonst FALSE.

Beispiele für Schlangen finden sich im Alltagsleben jede Menge, zum Beispiel als Warteschlange vor einer Kaufhauskasse.

ADT List / Liste

Ein drittes Beispiel für einen linearen ADT ist die Liste. Hier die (unvollständige) Definition der Operationen des ADT List aus der englischen Wikipedia

Implementation of the list data structure may provide some of the following operations:

  • a constructor for creating an empty list;
  • an operation for testing whether or not a list is empty;
  • an operation for prepending an entity to a list
  • an operation for appending an entity to a list
  • an operation for determining the first component (or the "head") of a list
  • an operation for referring to the list consisting of all the components of a list except for its first (this is called the "tail" of the list.)

Listen finden sich zum Beispiel auf dem Bildschirm eines Medienspielers, der eine Liste von Musikstücken oder Filmen anzeigt. Mit den Cursortasten der Fernbedienung kann man zum Anfang oder zum Ende der Liste springen sowie sich nach oben und unten durch die Liste durcharbeiten.

Gerade im Zentralabitur NRW spielen Listen eine enorm wichtige Rolle. Allerdings ist die NRW-Liste kein ADT, sondern eine Java-Klasse mit sehr vielen Methoden.

ADT Binary search tree / Binärer Suchbaum

Das vierte Beispiel steht für einen nicht-linearen ADT, nämlich für den binären Suchbaum, den wir bereits in der Folge 12.3 kurz kennengelernt haben, als es um schnelle Suchalgorithmen ging, und mit dem wir uns auch noch ausführlich beschäftigen werden. Wenn man hier im Internet sucht, findet man viele verschiedene Operationen für den binären Suchbaum. Hier ein Beispiel:

  • Init(): Erzeugt einen leeren Suchbaum
  • Insert(x): Das Element x wird hinzugefügt.
  • Delete(x): Das Element x wird entfernt.
  • Find(x): Das Element x wird gesucht
  • FindMax(): Das größte Element wird gesucht und zurückgeliefert
  • FindMin(): Das kleinste Element wird gesucht und zurückgeliefert

Bäume, vor allem binäre Suchbäume gibt es überall dort, wo viele Daten systematisch verwaltet werden müssen. Vor allem das Suchen in großen Datenmengen wird durch solche Suchbäume schlagartig vereinfacht.

Dies war eine kleine Übersicht über vier wichtige abstrakte Datentypen. Es gibt viele andere ADTs, aber für den Informatikunterricht in NRW sind diese vier ADTs die wichtigsten. Im Folgenden werden wir uns mit jedem einzelnen dieser vier ADTs näher beschäftigen, dabei beginnen wir mit dem ADT Stack.

Seitenanfang -
Weiter mit dem ADT Stack...