In der Informatik unterscheidet man üblicherweise zwischen
Verfahren zur Lösung von Problemen und ihrer Implementation
in einer bestimmten Programmiersprache auf bestimmten Rechnern.
Man nennt die Verfahren Algorithmen.
Sie sind das zentrale Thema der Informatik.
Die meisten Algorithmen erfordern jeweils geeignete Methoden
zur Strukturierung der von den Algorithmen manipulierten Daten.
Algorithmen und Datenstrukturen gehören also zusammen.
Die richtige Wahl von Algorithmen und Datenstrukturen
ist ein wichtiger Schritt zur Lösung eines Problems mit
Hilfe von Computern.
Thema dieses Buches ist das systematische Studium von
Algorithmen und Datenstrukturen aus
vielen Anwendungsbereichen.
In diesem Kapitel werden grundsätzliche
Überlegungen zum Algorithmenbegriff und zur Leistungsanalyse
vorausgeschickt. Ferner werden einige einfache Datenstrukturen behandelt.
Wie wichtig die richtige Algorithmenwahl zur Lösung eines
Problems sein kann, zeigt ein von Jon Bentley vorgeschlagenes Problem,
das in diesem Kapitel genauer diskutiert wird. Es handelt sich um das
Maximum-Subarray-Problem.
Lineare Listen basieren auf dem in der Mathematik wohlbekannten
Konzept einer endlichen Folge von Elementen eines bestimmten
Grundtyps. Man denke etwa an eine endliche Folge ganzer oder reeller
Zahlen. Man kann an eine Folge ein Element anhängen, ein Element
an einer bestimmten Stelle einfügen oder entfernen und aus zwei
Folgen durch Hintereinanderhängen (Verketten) eine neue Folge
machen.
Statt das Einfügen und Entfernen von Elementen an einer
beliebigen Position innerhalb einer linearen Liste zuzulassen,
genügt es für viele Anwendungen, wenn diese Operationen am
Anfang oder am Ende einer Liste ausgeführt werden
können. Dies führt zu den Datenstrukturen Stapel und
Schlangen.
Im letzten Abschnitt wird eine mögliche Implementation von
verkettet gespeicherten lineare Listen vorgestellt, die es erlaubt,
alle drei Operationen Suchen, Einfügen und Entfernen von
Schlüsseln für eine Liste von N Elementen mit hoher
Wahrscheinlichkeit in Zeit O(log N) auszuführen. Diese von
W. Pugh vorgeschlagene Datenstruktur mit dem Namen Skip-Liste ist ein
erstes Beispiel für eine randomisierte Datenstruktur.
Zurück