P2 Lists & Sets: Datenstrukturen

Autor: Urs Battaglia

„Ordnung ist das halbe Leben“ heisst ein schönes Sprichwort. Wir fassen einzelne lose Blätter in Aktenhüllen zusammen oder legen sie in einem Ordner ab. Wir stellen die Stifte in einen Stifthalter, damit sie nicht überall verstreut herumliegen, wir stellen die Bücher fein säuberlich in ein Bücherregal, usw. Grundsätzlich verfolgen wir mit der Ordnung immer zwei Dinge:

1. Wir wollen gleiche Gegenstände zusammenfassen, egal ob es Blätter, Stifte, Bücher, Kleider oder Schuhe sind.
2. Zusammengefasste Gegenstände können sortiert und damit in eine geeignete Reihenfolge gebracht werden.

1. Die wichtige Aufgabe des Ordnens wird in der Programmierung von Datenstrukturen (Container) übernommen, welche Daten (Gegenstände) aufnehmen und danach gegebenfalls sortiert werden können.
2. Datenstrukturen helfen bei der Zusammenfassung ähnlicher Daten und sorgen damit für Ordnung im Programm und im Speicher.
3. Wie im täglichen Leben ein Schrank, eine Schublade oder ein Ordner ist auch der Platz in einer Datenstruktur beschränkt. Durch die Grösse der einzelnen Daten und den verfügbaren Speicherplatz, kann die Datenmenge bestimmt werden.
4. Daten können ganz unterschiedlich strukturiert sein. In einer Schublade liegen die Socken wild durcheinander, während die Bücher im Regal schön in Reih und Glied stehen und die Namen im Adressverzeichnis sogar alphabetisch sortiert sind. So stehen auch in der Programmierung für verschiedene Aufgaben verschiedene Datenstrukturen zur Verfügung.

1. Ich kann Ordnungs- und Sortierprobleme aus dem Alltag auf die Programmierung übertragen und mit Hilfe einer geeigneten Datenstruktur beschreiben.
2. Ich kenne verschiedene Datenstrukturen (Array, Liste, Stapelspeicher (Stack), Warteschlange, …) und kann deren Unterschiede und Verwendungszwecke beschreiben und an Beispielen erklären.
3. Ich kann Anhand des verwendeten Datentyps und der Anzahl zu erwartender Daten den benötigten Speicherplatz abschätzen.
4. Ich kann für eine beliebige Problemstellung die geeignete Datenstruktur auswählen und diese in einer Programmiersprache implementieren.
5. Ich kann in einer Programmiersprache die Daten einer Datenstruktur beliebig manipulieren (löschen, einfügen, vergleichen, sortieren, …)

• Statistische Erfassung und Auswertung von Ereignissen
  • Prüfungsnoten
  • Datenverkehr in einem Netzwerk
• Sortieralgorithmen (Abenteuer Informatik - Kapitel 2)
• Rucksackproblem (Abenteuer Informatik - Kapitel 3)

• P0 Basics: EVA-Prinzip, Codierung von Ein- und Ausgabewerten
• I0 Konzepte von Information
• i1_datenrepresentation
• A3.2 Dynamic Programming: Dynamisches Programmieren

• Früher hat man alles selbst gestrickt. Dann rein gar nichts mehr. Jetzt exemplarische Datenstrukturen. — Paul Miotti 2008/06/24
• Das Zusammenspiel von Collections und Closures führt zum Thema „Abstrakte Datentypen“ und damit sehr direkt zu OO Themen. Zwingend? — Vincent Tscherter 2008/10/17 12:00
• Der Begriff Datenstrukturen wird vor allem in älteren Lehrmitteln für „struct, record, tupel, …“ angewendet. Collections hingegen (was hier offensichtlich die Meinung ist) werden häufig als Datensammlungen (bzw. abstrakte Datentypen) übersetzt. — Philipp Gressly Freimann 2009/01/23 15:34