Datenstrukturen in Pascal und BASIC, 1984 mit 12 Pascal- und 8 BASIC-Programmen Coll. Programmieren von Mikrocomputern

Wegen der starken Betonung von algorithmischen Verfahren in Literatur und Ausbildung ist die Darstellung von Datenstrukturen etwas in den Hintergrund getreten. Hinzu kommt, d~ Prograrnrniersprachen wie BASIC nur einige wenige Datentypen kennen. Dabei wird die Programmierung von Algorithmen ganz wesentlich von der Art der gewiihlten Daten­ struktur mitbestimmt. 1m vorliegenden Band werden daher die wichtigsten Datentypen wie - Felder - Verbunde (Records) - Mengen Listen Stacks Schlangen Baume - Graphen vorgestellt und ihre Realisierung in Pascal und BASIC diskutiert. Dabei wird insbesondere auf die Eigenarten der beiden Programmiersprachen eingegangen. In 20 Programmen - hauptsiichlich aus dem nichtmathematischen Bereich - wird die vielfiiltige Anwendungsm6glichkeit dieser Datenstrukturen aufgezeigt, z. B. Hashsuche - optimale Binarcodierung - Serienaddierer - Zigarettenautomat - Stammbaum - Entwicklung einer Waldpopulation - Simulation einer Warteschlange Einleitung Es tiberrascht, dat.) es keine allgemein akzeptierte Defmition fUr Datenstrukturen (engl. data structures) gibt (vgl. [7], [8]). Fa~t man die der Datenstruktur zugrunde lie­ gende Relationen als Kanten eines Graphs auf, so kann man natUrlich jede Datenstruktur als gerichteten Graphen defmieren (siehe [8]). Neuere Bestrebungen zielen darauf hin, Datenstrukturen abstrakt tiber Axiome zu defmieren (Lisko v und Zilles 1974, Guttag 1975). Einige Beispiele dazu werden im folgenden gegeben (siehe auch [2]). Allgemein gesprochen sind Datenstrukturen die Objekte, mit denen Algorithmen operieren. Die Operationen sind sornit Ordnen, Sortieren, Durchsuchen, Speichern, Vergleichen usw.

1 Aufzählungs- und Unterbereichstyp.- 1.1 Serienaddierer (Pascal).- 1.2 Zigarettenautomat (Pascal).- 2 Menge.- 2.1 Potenzmenge (Pascal).- 2.2 Balkenwaage (Pascal).- 3 Verbund.- 3.1 Komplexes Hornerschema (Pascal).- 3.2 Volumenberechnung (Pascal).- 4 Feld.- 4.1 Lateinische Quadrate (Pascal).- 4.2 Waldpopulation (BASIC).- 4.3 Ziffernfolge (BASIC).- 5 Liste.- 5.1 Hashsuche (BASIC).- 5.2 Josephsproblem (Pascal).- 5.3 Zweifachverkettete Liste (BASIC).- 6 Stack.- 6.1 Klammerprüfung (Pascal).- 6.2 Arithmetischer Term (Pascal).- 7 Schlange.- 7.1 Warteschlange (BASIC).- 8 Baum.- 8.1 Erzeugung eines Binärbaumes (Pascal).- 8.2 Stammbaum (BASIC).- 8.3 Optimale Codierung (BASIC).- 9 Heap.- 9.1 Heapsort (Pascal).- 10 Graph.- 10.1 Mehrstufige Verbindungen in einem Graphen (BASIC).