Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


2. Pascal



Datentypen

Die meisten Algorithmen im vorliegenden Buch operieren mit einfachen Datentypen: ganze Zahlen, reelle Zahlen, Zeichen oder Zeichenfolgen. Eines der wichtigsten Merkmale von Pascal ist, daß es die Möglichkeit bietet, aus diesen elementaren Bausteinen komplexere Datentypen aufzubauen. Dies ist eines der »fortgeschrittenen« Merkmale, dessen Nutzung wir vermeiden, um unsere Beispiele einfach zu gestalten und uns mehr auf die Funktionsweise der Algorithmen anstatt auf die Eigenschaften ihrer Daten zu konzentrieren. Wir bemühen uns, dies ohne Beschränkung der Allgemeingültigkeit zu tun: Tatsächlich macht es bereits die Verfügbarkeit von solchen weiterführenden Möglichkeiten, wie Pascal sie besitzt, einfach, einen Algorithmus aus einem »Spielzeug«, das mit einfachen Datenstrukturen operiert, in ein »Arbeitspferd« zu verwandeln, das mit komplexen Datensätzen (records) arbeitet. Wenn sich die grundlegenden Verfahren am besten mit Hilfe von anwenderdefinierten Typen beschreiben lassen, werden wir diese auch verwenden. Zum Beispiel basieren die geometrischen Verfahren in den Kapiteln 24-28 auf Typen für Punkte, Linien, Polygone usw.

Manchmal liegt der Fall vor, daß die richtige Darstellung von Daten auf niedriger Ebene der Schlüssel für die Leistungsfähigkeit ist. Im Idealfall sollte die Art und Weise, wie ein Programm arbeitet, nicht davon abhängen, wie die Zahlen dargestellt sind oder wie die Zeichen gepackt sind (um zwei Beispiele zu nennen). Der Preis, den man hinsichtlich der Leistungsfähigkeit zahlen muß, wenn man dieses Ideal anstrebt, ist jedoch oft zu hoch. In der Vergangenheit reagierten Programmierer in dieser Situation mit dem drastischen Schritt, zur Assembler- oder Maschinensprache überzugehen, wo es wenig Beschränkungen bezüglich der Darstellung gibt. Glücklicherweise besitzen höhere Programmiersprachen Mechanismen zur Schaffung sinnvoller Darstellungen, ohne daß solche extremen Wege beschritten werden müssen. Das gibt uns die Möglichkeit, so manchem wichtigen klassischen Algorithmus gerecht zu werden. Natürlich sind solche Mechanismen notwendigerweise maschinenabhängig, und wir werden sie nicht sehr ausführlich betrachten, außer um darauf hinzuweisen, wann sie geeignet sind. Auf diese Frage wird in den Kapiteln 10, 17 und 22 ausführlicher eingegangen, wo Algorithmen betrachtet werden, die auf der binären Darstellung von Daten beruhen.

Wir versuchen auch zu vermeiden, uns bei der Betrachtung von Algorithmen, die mit Zeichen und Zeichenfolgen operieren, mit Fragen der maschinenabhängigen Darstellung zu beschäftigen. Oft vereinfachen wir unsere Beispiele, indem wir nur mit den Großbuchstaben A bis Z arbeiten und dabei einen einfachen Code verwenden, bei dem der i-te Buchstabe des Alphabets durch die ganze Zahl i dargestellt wird. Die Darstellung von Zeichen und Zeichenfolgen ist ein derart fundamentaler Bestandteil der Schnittstelle zwischen Programmierer, Programmiersprache und Maschine, daß man sicher sein sollte, daß man sie vollständig versteht, bevor man Algorithmen für die Verarbeitung derartiger Daten implementiert; die in diesem Buch angegebenen Verfahren, die auf vereinfachten Darstellungen beruhen, lassen sich dann leicht anpassen.

Wann immer dies möglich ist, benutzen wir ganze Zahlen (integers). Programme, die reelle Zahlen (real) verarbeiten, fallen in den Bereich der numerischen Analysis. Typisch ist, daß ihre Leistungsfähigkeit eng mit den mathematischen Eigenschaften der Darstellung zusammenhängt. Auf diese Frage kommen wir in den Kapiteln 37, 38, 39, 41 und 43 zurück, wo einige grundlegende numerische Algorithmen erörtert werden. Bis dahin geben wir ganzen Zahlen den Vorzug, selbst dort, wo reelle Zahlen geeigneter erscheinen mögen, um die geringe Effizienz und die Ungenauigkeit zu vermeiden, die normalerweise mit der »Gleitkomma« -Darstellung einhergeht.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]