Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


3. Elementare Datenstrukturen



Abstrakte Datentypen

Wir haben weiter oben gesehen, daß es oft zweckmäßiger ist, Algorithmen und Datenstrukturen mit Hilfe der auszuführenden Operationen zu beschreiben, als durch Einzelheiten der Implementation. Wenn eine Datenstruktur auf diese Weise definiert ist, wird sie abstrakter Datentyp genannt. Die Grundidee besteht darin, die »Vorstellung« davon, was die Datenstruktur leisten sollte, von jedweder speziellen Implementation zu trennen.

Das entscheidende Merkmal eines abstrakten Datentyps besteht darin, daß nichts, was sich außerhalb der Definitionen der Datenstruktur und der mit ihr operierenden Algorithmen befindet, auf irgendetwas Bezug nehmen darf, was sich innerhalb befindet, außer über Funktions- und Prozeduraufrufe für die grundlegenden Operationen. Der hauptsächliche Anlaß für die Entwicklung von abstrakten Datentypen bestand darin, daß ein Mechanismus für die Organisation umfangreicher Programme benötigt wurde. Durch sie ergibt sich ein Weg, um die Größe und Komplexität der Schnittstelle zwischen (potentiell komplizierten) Algorithmen und zugehörigen Datenstrukturen und (einer potentiell großen Anzahl von) Programmen, die die Algorithmen und Datenstrukturen verwenden, in Grenzen zu halten. Dadurch wird es leichter, das umfangreiche Programm zu verstehen, und es wird einfacher, die grundlegenden Algorithmen zu verändern oder zu verbessern.

Stapel und Schlangen sind klassische Beispiele von abstrakten Datentypen: Die meisten Programme brauchen sich nur mit ein paar wohldefinierten elementaren Operationen zu beschäftigen, aber nicht mit den Details von Verkettungen und Indizes.

Felder und verkettete Listen können umgekehrt als Weiterentwicklungen eines elementaren abstrakten Datentyps betrachtet werden, der lineare Liste genannt wird. Sie alle können solche Operationen wie Einfügen, Entfernen und Zugreifen, angewandt auf eine zugrunde liegende elementare Struktur von sequentiell angeordneten Elementen, unterstützen. Diese Operationen genügen, um die Algorithmen zu beschreiben, und die Abstraktion der linearen Liste kann in den Anfangsstadien der Entwicklung von Algorithmen von Nutzen sein. Wie wir jedoch gesehen haben, liegt es im Interesse des Programmierers, sorgfältig zu definieren, welche Operationen verwendet werden sollen, da die verschiedenen Implementationen sehr unterschiedliche Leistungsmerkmale haben können. Zum Beispiel wäre es aufwendig, für das Sieb des Eratosthenes anstelle eines Feldes eine verkettete Liste zu verwenden, da die Effizienz dieses Algorithmus davon abhängt, daß man in der Lage ist, von jeder Position im Feld schnell zu jeder anderen zu gelangen, während die Benutzung eines Feldes anstelle einer verketteten Liste für das Problem des Josephus aufwendig wäre, da die Effizienz des Algorithmus vom Verschwinden entfernter Elemente abhängt.

Mit den linearen Listen bieten sich viele weitere Operationen an, die wesentlich kompliziertere Algorithmen und Datenstrukturen für eine effiziente Unterstützung erfordern. Die beiden wichtigsten sind das Sortieren der Elemente nach der wachsenden Folge ihrer Schlüssel (Gegenstand der Kapitel 8-13) und das Suchen eines Elements mit einem bestimmten Schlüssel (Gegenstand der Kapitel 14-18).

Ein abstrakter Datentyp kann verwendet werden, um einen anderen zu definieren: Wir benutzen verkettete Listen und Felder, um Stapel und Schlangen zu definieren. Tatsächlich verwenden wir die von Pascal bereitgestellten Abstraktionen »Zeiger« (pointer) und »Datensatz« (record), um verkettete Listen aufzubauen, und die von Pascal bereitgestellte Abstraktion »Feld« (array) zum Aufbau von Feldern. Außerdem sahen wir weiter oben, daß wir verkettete Listen mit Feldern aufbauen können. In Kapitel 36 werden wir sehen, daß Felder manchmal mit Hilfe verketteter Listen aufgebaut werden sollten! Der wirkliche Vorteil abstrakter Datentypen besteht darin, daß es uns dadurch möglich wird, auf geeignete Weise umfangreiche Systeme auf verschiedenen Abstraktionsebenen zu konstruieren. Diese Abstraktionsebenen reichen von den Anweisungen in Maschinensprache, die vom Computer verwendet werden, über die vielfältigen Möglichkeiten, die die Programmiersprache bietet, bis zum Sortieren, Suchen und anderen hochentwickelten Möglichkeiten, wie sie durch in diesem Buch behandelte Algorithmen geschaffen werden, ja sogar bis hin zu den noch höheren Abstraktionsebenen, welche die Anwendung implizieren könnte.

Im vorliegenden Buch haben wir es mit relativ kleinen Programmen zu tun, die recht eng mit den zu ihnen gehörigen Datenstrukturen verknüpft sind. Solange es möglich ist, an der Schnittstelle zwischen unseren Algorithmen und ihren Datenstrukturen von Abstraktion zu sprechen, ist es tatsächlich zweckmäßiger, wenn wir uns auf höhere Abstraktionsebenen (näher zur Anwendung) konzentrieren; die Idee der Abstraktion sollte uns dabei nicht hindern, die effizienteste Lösung für ein spezielles Problem zu finden. Wir stellen uns hier auf den Standpunkt, daß es auf die Leistungsfähigkeit ankommt! Programme, bei deren Entwicklung dies beachtet wurde, kann man dann mit einiger Zuversicht bei der Entwicklung höherer Abstraktionsebenen für umfangreiche Systeme benutzen.

Gleichgültig, ob abstrakte Datentypen explizit verwendet werden oder nicht, befreit uns das nicht von der Pflicht, genau zu formulieren, was unsere Algorithmen tun. Tatsächlich ist es oft zweckmäßig, die Schnittstellen mit den hier bereitgestellten Algorithmen und Datenstrukturen als abstrakte Datentypen zu definieren; Beispiele hierzu sind in den Kapiteln 11 und 14 zu finden. Darüber hinaus ist der Anwender der Algorithmen und Datenstrukturen verpflichtet, klar festzulegen, was er von ihnen erwartet - die richtige Kommunikation zwischen dem Nutzer eines Algorithmus und demjenigen, der ihn implementiert (auch wenn das ein und dieselbe Person ist) ist der Schlüssel zum Erfolg beim Aufbau umfangreicher Systeme. Programmierumgebungen, die die Entwicklung großer Systeme unterstützen, besitzen Möglichkeiten, die es gestatten, dies auf systematische Weise zu tun.

Wie schon erwähnt wurde, bestehen reale Datenstrukturen selten einfach aus ganzen Zahlen und Verkettungen. Knoten enthalten oft eine große Menge an Informationen und können zu etlichen unabhängigen Datenstrukturen gehören. Zum Beispiel kann eine Datei, die aus Personaldaten besteht, Datensätze mit Namen, Adressen und verschiedenen anderen Informationen über Angestellte enthalten, und jeder Datensatz kann zu einer Datenstruktur für das Suchen nach bestimmten Angestellten gehören, zu einer anderen für die Beantwortung statistischer Fragen usw. Selbst wenn man nur die in diesem Kapitel beschriebenen einfachen Datenstrukturen verwendet, ist es möglich, recht komplexe Strukturen aufzubauen: Die Datensätze können umfangreicher und komplexer sein, doch die Algorithmen sind die gleichen. Dennoch müssen wir darauf achten, daß wir keine Algorithmen entwickeln, die nur für kleine Datensätze brauchbar sind; wir werden am Ende von Kapitel 8 und am Anfang von Kapitel 14 auf diese Frage zurückkommen.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]