|
|
Bei Amazon kaufen|
Umschlagtext
Fundierte Kenntnisse über Datenstrukturen und Algorithmen sind Voraussetzung für die Entwicklung effizienter Programme. Dieses Lehrbuch zeigt, wie Datenstrukturen entworfen werden, wie sie sich verhalten und welche effizienten Algorithmen es für ihre Manipulation gibt. Es basiert auf der objektorientierten Programmierung in ANSI/ISO C++.
Ausgehend vom Prinzip des abstrakten Datentyps werden die für die Praxis wichtigen Methoden der Datenorganisation, wie z.B. Tabellen-, Listen- und Baumstrukturen, sowie Mengendarstellungen, Graphen und Files behandelt. Dazu gehören auch die Algorithmen für grundlegende Such- und Sortieraufgaben und Programme für die Implementierung der Abstrakten Typen. Mit Hilfe zahlreicher Anwendungsbeispiele und Übungsaufgaben vermitteln die Autoren den Stoff auf sehr anschauliche und nachvollziehbare Weise. Im Internet: Alle vorgestellten Algorithmen und Anwendungsbeispiele sowie die Lösungen der Aufgaben aus dem Buch. Inhaltsverzeichnis
Vorwort
1 Grundlagen 1.1 Datenabstraktion und Datenstrukturierung 1.1.1 Datentypen 1.1.2 Abstrakte Datentypen 1.1.3 Datenstrukturen 1.2 Datentypen in C++ 1.2.1 Skalare Datentypen 1.2.2 Statische Datentypen 1.2.3 Dynamische Strukturen 1.3 Einblick in die Sprache C++: Strukturiertes Programmieren 1.3.1 Programmstruktur 1.3.2 Ausdrücke 1.3.3 Kontrollanweisungen 1.3.4 Funktionen 1.4 Einblick in die Sprache C++: Objektorientiertes Programmieren 1.4.1 Grundbegriffe 1.4.2 Klassen 1.4.3 Überladen von Operatoren 1.4.4 Ableitung von Klassen (Vererbung) 1.4.5 Templates 1.5 Algorithmen und Methoden ihres Entwurfs 1.5.1 Rekursion 1.5.2 Divide-and-Conquer-Algorithmen 1.6 Analyse von Algorithmen 1.6.1 Charakteristische Operationen und Komplexitätsfunktion 1.6.2 ONotation 1.6.3 Komplexitätsklassen 1.6.4 Omega- und Theta-Notation 1.7 Aufgaben 2 Tabellen 2.1 Abstrakter Datentyp Table 2.1.1 Abstraktion 2.1.2 Beispiele der Anwendung 2.1.3 Implementation 2.2 Suchen 2.2.1 Sequenzielles Suchen 2.2.2 Binäres Suchen 2.3 Sortieren 2.3.1 Direktes Sortieren durch Einfügen 2.3.2 Direktes Sortieren durch Auswählen 2.3.3 Direktes Sortieren durch Austauschen 2.3.4 Indirekte Sortierung 2.3.5 QuickSort 2.3.6 MergeSort 2.4 Hashing 2.4.1 Hashfunktion 2.4.2 Kollisionsbehandlung 2.5 ADT HashTable 2.5.1 Abstraktion 2.5.2 Implementation 2.6 Aufgaben 3 Strings 3.1 Abstrakter Datentyp String 3.2 Mustererkennung 3.2.1 Einfaches Verfahren 3.2.2 Verfahren von Rabin-Karp 3.3 Implementation des ADT String 3.4 Aufgaben 4 Stapel und Schlangen 4.1 Abstrakter Datentyp Stack 4.2 Implementation des ADT Stack 4.2.1 Implementation als Array 4.2.2 Implementation als gekettete Liste 4.3 Anwendungen von Stapeln 4.4 Abstrakter Datentyp Queue 4.5 Implementation des ADT Queue 4.5.1 Implementation des ADT Queue als Array 4.5.2 Implementation als gekettete Liste 4.6 Anwendungen von Schlangen 4.6.1 Radix Sortieren 4.6.2 Permutationen 4.7 Stapel und Schlangen mit Freiplatzverwaltung 4.8 Deques 4.9 Aufgaben 5 Lineare Listen 5.1 Abstrakter Datentyp List 5.2 Implementation des ADT List 5.2.1 Datenstruktur 5.2.2 Implementation als einfach gekettete Liste 5.2.3 Implementation als doppelt gekettete Liste 5.3 Geordnete Liste 5.4 Komplexität von Suchalgorithmen 5.5 Anwendungen 5.5.1 Sortieren von Listen 5.5.2 Polynomarithmetik 5.5.3 Dünn besetzte Matrizen 5.6 Aufgaben 6 Bäume 6.1 Allgemeine Bäume 6.2 Binäre Bäume 6.2.1 Definition und Eigenschaften 6.2.2 Darstellungen 6.3 ADT BinaryTree 6.3.1 Öffentliche Sicht 6.3.2 Implementationssicht 6.3.3 Traversieren von Binärbäumen 6.4 Syntaxbäume 6.5 Entscheidungsbaum 6.6 Mehrwegbäume 6.7 Aufgaben 7 Mengen 7.1 Abbildungen 7.1.1 ADT Mapping 7.1.2 Implementation des ADT Mapping 7.2 Wörterbuch 7.2.1 Abstrakter Datentyp Dictionary 7.2.2 Binärer Suchbaum 7.2.3 Implementation des ADT Dictionary als binären Suchbaum 7.2.4 2-3-4-Baum 7.2.5 Implementation des ADT Dictionary als 2-3-4-Baum 7.3 Disjunkte Mengen 7.3.1 Abstrakter Datentyp DisjointSets 7.3 .2 Implementation des ADT DisjointSets 7.4 Prioritätswarteschlange 7.4.1 Abstrakter Datentyp PriorityQueue 7.4.2 Heap 7.4.3 Implementation des ADT PriorityQueue als Heap 7.4.4 HeapSort 7.5 Datenkomprimierung 7.5.1 Huffman-Baum 7.5.2 Code-Komprimierung 7.6 Digitalbäume 7.6.1 Tries 7.6.2 Patricia-Bäume 7.7 Aufgaben 8 Graphen 8.1 Graphen und binäre Relationen 8.2 Digraphen 8.2.1 Definition und Terminologie 8.2.2 Darstellungen 8.2.3 Abstrakter Datentyp Digraph 8.3 Traversierungsalgorithmen 8.3.1 Tiefensuche 8.3.2 Spannbaum der Tiefensuche 8.3.3 Zusammenhangskomponenten 8.3.4 Breitensuche 8.3.5 Topologisches Sortieren 8.3.6 Transitive Hülle 8.4 Kürzeste und längste Wege 8.4.1 Kürzeste Wege von einem Knoten zu allen anderen Knoten 8.4.2 Kürzeste Wege zwischen allen Knoten 8.4.3 Längste Wege und CPM-Verfahren 8.5 Ungerichtete Graphen 8.5.1 Zweifacher Zusammenhang 8.5.2 Minimaler Spannbaum 8.6 Aufgaben 9 Files 9.1 System-Fileverwaltung 9.2 Das C++-Stream-Konzept 9.2.1 I/OStream-Klassen 9.2.2 Temporär gespeicherte Files 9.2.3 Formatsteuerung 9.2.4 Permanent gespeicherte Files 9.3 Speicherungsmethoden 9.3.1 Sequenzielle Speicherung 9.3.2 Indexsequenzielle Speicherung 9.3.3 Gestreute Speicherung 9.3.4 Baumstrukturierte Speicherung 9.4 Externes Sortieren 9.4.1 Das Sort/Merge-Konzept 9.4.2 Die Sortierphase von Sort/Merge 9.4.3 Ausgeglichenes k-Weg-Mischen 9.4.4 Mehrphasen-Mischen 9.5 Aufgaben Literatur Register |