Grundlagen von Datenstrukturen in C
Horowitz, Sahni, Anderson-Freed
Grundlagen von Datenstrukturen in C
Von E. Horowitz, S. Sahni u. S. Anderson-Freed.
International Thomson Publishing, Bonn 1994. 620 S., Hardcover
ISBN 3-929821-00-1
Das vorliegende Buch ist die Übersetzung von "Fundamentals of Data Structures in C", das seinerseits aus einem Buch über Datenstrukturen in Pascal hervorgegangen ist. Es richtet sich vorwiegend an Dozenten und Studenten der Informatik, da es als Lehrbuch konzipiert und auch als Grundlage für Vorlesungen gedacht ist. Die Programme werden in Standard (ANSI) C angegeben.
Die behandelten Themen sind: Felder und Strukturen (z. B. Unions, Sparse-Matrizen); Stapel und Warteschlangen; einfach und doppelt verkettete Listen, einschließlich dynamischer Speicherverwaltung; Bäume in Feld- und verketteter Darstellung (z. B. Min-/Max-Heaps, Such- und Auswahlbäume); Graphen (u. a. Optimierungen, Aktivitätsnetze); verschiedene Sortieralgorithmen (u. a. Quicksort, Sortieren durch Mischen, externes Sortieren großer Datenmengen); statisches und dynamisches Hashing; Heap-Strukturen (z. B. Min-Max-, binomische, Fibonacci-Heaps); Suchstrukturen (u. a. optimale binäre Suchbäume, AVL-, 2-3-, 2-3-4-, Rot-Schwarz-, B-, Spreiz-Bäume, Tries).
In einem Großteil des Buches werden die Datenstrukturen mit Hilfe von abstrakten Datentypen eingeführt, worauf konkrete z. T. generische Implementierungen in C aufbauen. Die Algorithmen zur Behandlung der Datenstrukturen werden zumeist rekursiv formuliert und in den Beispielprogrammen durch rekursive Funktionen realisiert. Ein besonderes Augenmerk gilt der Speicher- und Zeitkomplexität der Algorithmen. In Leistungsanalysen werden die (ggf. amortisierten) Komplexitäten berechnet und in der asymptotischen Notation dargestellt. Damit werden verschiedene Algorithmen auf ihre Leistungsfähigkeit hin verglichen, wobei auch auf die praktische Leistungsmessung mit geeigneten Testdaten eingegangen wird. Zahlreiche Abbildungen und Tabellen ergänzen die Erläuterungen. Am Ende von Abschnitten und Kapiteln befinden sich Übungen, von denen anspruchsvolle oder umfangreiche besonders gekennzeichnet sind. Jedes Kapitel besitzt ein Literaturverzeichnis, in dem auf die Originalliteratur und auf weiterführende Texte verwiesen wird.
Trotz des theoretischen Ansatzes bleibt dieses Buch in seiner Darstellung praxisnah und ist damit auch für Programmierer interessant. In den Beispielprogrammen befinden sich ein paar Druckfehler, die einem geübten C-Programmierer aber keine Schwierigkeiten bereiten, und einige wenige aufgrund der Übersetzung auftretende Mängel fallen nicht ins Gewicht. Insgesamt ist die Art der Präsentation ein guter Kompromiß zwischen Theorie und Anwendung.
T. Stroh, Siegen
| Dieses Buch können Sie direkt bei amazon.de |  | |
