Effiziente Algorithmen und Datenstrukturen bilden ein zentrales Thema der Informatik. Wer programmiert, sollte zu den wichtigsten Problembereichen grundlegende Lösungs verfahren kennen; er sollte auch in der Lage sein, neue Algorithmen zu entwerfen, ggf. als Kombination bekannter Verfahren, und ihre Kosten in Bezug auf Laufzeit und Spei cherplatz zu analysieren. Datenstrukturen organisieren Information so, daß effiziente Algorithmen möglich werden. Dieses Buch möchte entsprechende Kenntnisse und Fähig keiten vermitteln; es wendet sich vornehmlich an Studierende der Informatik im Grund studium. Vorausgesetzt werden lediglich Grundkenntnisse der Programmierung, wie sie etwa durch Umgang mit einer Sprache wie PASCAL gegeben sind. Zum Verständnis werden zwar keine tiefergehenden mathematischen Vorkenntnisse, aber doch die Bereit schaft zum Umgang mit einfacher mathematischer Notation benötigt. Gelegentlich kom men bei der Analyse von Algorithmen auch etwas anspruchsvollere Berechnungen vor. Diese werden sorgfältig erklärt, und die benötigten Techniken werden im Rahmen des Buches eingeübt. Grundlage für das Buch waren Vorlesungen zu Datenstrukturen und zu geometrischen Algorithmen, die ich an der Universität Dortmund gehalten habe; diese wurden später zu einem Kurs "Datenstrukturen" für die Fernuniversität Hagen ausgearbeitet und dort bereits einige Jahre eingesetzt. Der Stoffumfang des Buches umfaßt den einer einsemestri gen vierstündigen Vorlesung, die in Dortmund und Hagen jeweils im 3. Semester ange boten wird.

Inhalt
1 Einführung.- 1.1 Algorithmen und ihre Analyse.- 1.2 Datenstrukturen, Algebren, Abstrakte Datentypen.- 1.3 Grundbegriffe.- Aufgaben.- Literaturhinweise.- 2 Programmiersprachliche Konzepte zur Konstruktion von Datenstrukturen.- 2.1 Atomare Typen.- 2.2 Typkonstruktoren / Strukturierte Typen.- 2.3 Zeigertypen.- Literaturhinweise.- 3 Grundlegende Datentypen.- 3.1 Sequenzen (Folgen, Listen).- 3.2 Stacks.- 3.3 Queues.- 3.4 Abbildungen.- 3.5 Binäre Bäume.- 3.6 (Allgemeine) Bäume.- Aufgaben.- Literaturhinweise.- 4 Datentypen zur Darstellung von Mengen.- 4.1 Mengen mit Durchschnitt, Vereinigung, Differenz.- 4.2 Dictionaries: Mengen mit INSERT, DELETE, MEMBER.- 4.3 Priority Queues: Mengen mit INSERT, DELETEMIN.- 4.4 Partitionen von Mengen mit MERGE, FIND.- Aufgaben.- Literaturhinweise.- 5 Graphen und Graph-Algorithmen.- 5.1 Gerichtete Graphen.- 5.2 Ungerichtete Graphen.- Aufgaben.- Literaturhinweise.- 6 Sortieralgorithmen.- 6.1 Einfache Sortierverfahren: Direktes Auswählen und direktes Einfügen.- 6.2 Divide-and-Conquer-Methoden: Mergesort und Quicksort.- 6.3 Verfeinertes Auswählen und Einfügen: Heapsort und Baumsortieren.- 6.4 Untere Schranke für allgemeine Sortierverfahren.- 6.5 Sortieren durch Fachverteilen: Bucketsort und Radixsort.- Aufgaben.- Literaturhinweise.- 7 Geometrische Algorithmen.- 7.1 Plane-Sweep-Algorithmen für Mengen orthogonaler Objekte in der Ebene.- 7.2 Divide-and-Conquer-Algorithmen für orthogonale Objekte in der Ebene.- 7.3 Suchen auf Mengen orthogonaler Objekte.- 7.4 Plane-Sweep-Algorithmen für beliebig orientierte Objekte.- Aufgaben.- Literaturhinweise.- 8 Externes Suchen und Sortieren.- 8.1 Externes Suchen: B-Bäume.- 8.2 Externes Sortieren.- Aufgaben.- Literaturhinweise.- Mathematische Grundlagen.- I Einige Summenformeln.- II EinigeGrundlagen der Wahrscheinlichkeitsrechnung und Kombinatorik.- III Umgang mit Binomialkoeffizienten.- IV Harmonische Zahlen.- V Umwandlung von Rekursion in eine Summe.- VI Fibonacci-Zahlen.- Literatur.