Algorithmen und Datenstrukturen

Der moderne Digital-Computer wurde entwickelt, um komplizierte und zeitraubende Berechnungen zu erleichtern und zu beschleunigen. Bei den meisten Anwendungen spielt seine Fähigkeit, grosse Mengen von Informationen zu speichern und wieder zugänglich zu machen, die wichtigste Rolle (und wird als Haupteigenschaft betrachtet); seine Fähigkeit zu rechnen, d.h. zu kalkulieren, Arithmetik auszuführen, ist in vielen Fällen nahezu belanglos.

Dieses Kapitel enthält in der Hauptsache eine ausgiebige Menge von Beispielen, die die Vërwendung der im vorangehenden Kapitel behandelten Datenstrukturen erläutern und zeigen, wie stark die Wahl der Struktur der zugrunde liegenden Daten die Algorithmen beeinflusst, die eine bestimmte Aufgabe ausführen.

In Kapitel 2 wurden die Array-, Record- und Set-Strukturen als grundlegende Datenstrukturen eingeführt. Sie sind grundlegend, weil sie die Bausteine für komplexere Strukturen darstellen und in der Praxis sehr häufig vorkommen. Der Sinn der Definition eines Datentyps und der späteren Spezifikation einer Variablen von diesem Typ ist die Festlegung des Wertebereichs dieser Variablen und damit auch ihres Speicherschemas. So vereinbarte Strukturen (Typen) heissen daher statisch. Es gibt aber viele Probleme, die weit kompliziertere Datenstrukturen erfordern. Wesentlich für diese Probleme ist die Veränderbarkeit ihrer Strukturen während der Ausführung. Solche veränderbaren Strukturen heissen dynamisch. Natürlich sind die Komponenten dieser Strukturen auf irgendeiner tieferen Stufe statisch, d.h. von einem Grundtyp. Dieses Kapitel ist der Konstruktion, Analyse und Verwaltung dynamischer Datenstrukturen gewidmet.