Robert Sedgewick: Algorithmen

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


3. Elementare Datenstrukturen



In diesem Kapitel betrachten wir die grundlegenden Methoden der Organisation von Daten für die Verarbeitung durch Programme. Für viele Anwendungen ist die Wahl der richtigen Datenstruktur tatsächlich die einzige wesentliche Entscheidung, die bei der Implementation erforderlich ist; nachdem diese Wahl getroffen ist, werden nur noch sehr einfache Algorithmen benötigt. Für ein und dieselben Daten erfordern manche Datenstrukturen mehr oder weniger Platz als andere; für die gleichen Operationen mit den Daten führen manche Datenstrukturen zu mehr oder weniger effizienten Algorithmen als andere. Dieses Thema wird uns in diesem Buch durchgehend beschäftigen, da die Wahl des Algorithmus und die der Datenstruktur in enger Wechselwirkung stehen und wir ständig nach Wegen zur Einsparung von Zeit oder Platz durch die richtige Entscheidung bei dieser Wahl suchen.

Eine Datenstruktur ist kein passives Objekt; wir müssen stets die Operationen berücksichtigen, die mit ihr ausgeführt werden sollen (und die Algorithmen, die für diese Operationen verwendet werden). Dieses Konzept wird mit dem Begriff des abstrakten Datentyps formalisiert, den wir am Schluß dieses Kapitels erörtern werden. Unser vorrangiges Interesse gilt jedoch konkreten Implementationen, und wir werden uns auf spezifische Darstellungen und Operationen konzentrieren.

Wir werden uns mit Feldern, verketteten Listen, Stapeln, Schlangen und anderen einfachen Varianten beschäftigen. Das sind klassische Datenstrukturen mit einem breiten Anwendungsgebiet; zusammen mit den Bäumen (siehe Kapitel 4) bilden sie die Grundlage für praktisch alle Algorithmen, die in diesem Buch betrachtet werden. Im vorliegenden Kapitel behandeln wir grundlegende Darstellungsarten und fundamentale Verfahren zur Handhabung dieser Strukturen, arbeiten einige spezifische Beispiele für ihre Anwendung durch und erörtern damit zusammenhängende Fragen wie die Speicherverwaltung.


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