Exkurs - Datenstrukturen

Datenstrukturen

Datenstrukturen ermöglichen es, strukturierte Daten als Einheit zu verwalten.

Betrachte als Beispiel einen Lottoschein mit mehreren Tipps.

Wenn man die Daten eines solchen Lottoscheins erfassen möchte, benötigt man Datenstrukturen. Im vorliegenden Fall liegt eine Reihung von Tipps vor, wobei jeder Tipp eine Reihung aus 6 Zahlen ist. Die Struktur der Daten lässt sich hier also als Reihung von Reihungen beschreiben.

Eine solche Reihung von Reihungen lässt sich in Python mit geschachtelten Listen darstellen:

# Lottoschein
schein = [[3, 6, 19, 21, 38, 41], [4, 9, 17, 37, 38, 39], [18, 23, 28, 36, 38, 46]]

Im Folgenden werden einige wichtige Datenstrukturen kurz vorgestellt und es wird aufgezeigt, wie man diese Datenstrukturen in Python mit Hilfe von Listen implementieren kann.

Reihung von Daten

Bei einer Reihung werden Daten desselben Typs zu einer Einheit zusammengefasst.

In Python kann jede Reihung mit einer Liste dargestellt werden. So kann die oben gezeigte Reihung durch die Liste [10, 15, 21, 33, 37, 40] repräsentiert werden.

Datenverbund

Bei einem Verbund werden Daten zu einer Einheit zusammengefasst, die von unterschiedlichem Typ sein können.

In Python kann man einen Verbund mit einer Liste ["Albert", "Einstein", 1879, 1955] oder durch ein Tupel ("Albert", "Einstein", 1879, 1955) darstellen.

Schachtelung von Reihung und Verbund

Reihungen und Verbunde können auch ineinander geschachtelt werden.

Eine solche Schachtelung lässt sich mit Hilfe von Listen nachbilden: [["Albert", "Einstein", [14, 3, 1879], [18, 5, 1955]], ...]

Eine Sonderform bilden Reihungen von Reihungen, die auch als mehrdimensionale Reihungen bezeichnet werden.

Ein solches magisches Quadrat lässt sich wie folgt mit Listen beschreiben: [[16, 5, 9, 4], [2, 11, 7, 14], [3, 10, 6, 15], [13, 8, 12, 1]]

Liste

Eine Liste ist eine endliche Folge von Elementen, bei der man flexibel neue Elemente hinzufügen und vorhandene Elemente entfernen kann.

Eine solche dynamische Listenstruktur lässt sich wie folgt beschreiben: ["Anna", "Peter", "Tim", "Greta", "Katrin"]

Baum

Eine Baum ist eine Datenstruktur, bei der jeder Knoten Nachfolgerknoten haben kann.

Der in der Abbildung gezeigte Stammbaum lässt sich mit Listen z. B. so darstellen: ["Andreas", ["Peter", ["Matthias"], ["Katharina"]], ["Christiane", ["Winfried"], ["Ursula"]]]

Graph

Ein Graph ist eine Datenstruktur, bei der Knoten mit Kanten verbunden sind.

Der in der Abbildung gezeigte Graph lässt sich mit Listen z. B. so darstellen: [["TR", ["KO", "KL"]], ["KO", ["TR", "MZ", "KL"]], ["MZ", ["KO", "KL"]], ["KL", ["TR", "KO", "MZ"]]]

Bemerkung

Wir werden einige dieser Datenstrukturen in weiteren Kapiteln aufgreifen und systematischer behandeln. Weitere Datenstrukturen (wie Stapel und Schlagen) werden bei Bedarf eingeführt.