Lineare Datenstrukturen

Wichtige Inhalte zum Thema "Lineare Datenstrukturen"

Im normalen Unterricht und auch in den zentralen Abituraufgaben werden vor allem drei lineare Datentypen immer wieder thematisiert:

• Stacks (Stapelspeicher)
• Queues (Schlangenspeicher)
• Lists (lineare Listen)

Stacks, Queues und Lists sind abstrakte Datentypen (ADTs), das heißt, sie werden allein durch die mit den Daten möglichen Operationen definiert. Am Beispiel Stack sieht das so aus:

Stack

• init: erzeugt einen neuen leeren Stack,
• push(x): fügt das Element x in den Stack ein,
• pop(): löscht das zuletzt eingefügte Element, falls der Stack nicht leer ist,
• top(): liefert das zuletzt eingefügte Element zurück, falls der Stack nicht leer ist,
• empty(): liefert true zurück, falls der Stack leer ist, andernfalls false.

Hier zum Vergleich die "offizielle" Dokumentation der Klasse Stack, wie sie sich oft im Anhang der NRW-Abituraufgaben findet. In dieser Dokumentation finden sich dann anschaulichere Formulierungen wie zum Beispiel bei push() wird das Element bzw. Objekt "oben auf den Stapel gelegt". Diese Beschreibung ist allerdings nicht mehr rein abstrakt, sondern schon recht konkret, aber für Schüler(innen) leichter begreifbar als die rein abstrakte Definition. Abstrakt ist die offizielle Dokumentation dennoch in dem Sinne, dass keinerlei Angaben über eine mögliche Implementation des Stacks gemacht werden.

Abiturrelevant könnte vielleicht das LIFO-Prinzip sein, das für den ADT Stack typisch ist: Last in, first out. Im Unterricht stellt man sich dazu immer einen Stapel Teller vor. Der Teller, der zuletzt oben auf den Stapel gelegt wurde, wird auch als erster wieder weggenommen.

In den Abituraufgaben des Landes NRW kommt der Datentyp Stack nicht so häufig vor, bisher eigentlich nur drei mal:

• 2009: Stapel mit Klausuren
• 2011: Kartenstapel bei einem Kartenspiel
• 2013: Ahnentafel von Goethe
• 2016: Warentransport

Bei der Ahnentafel von Goethe werden die einzelnen Personen zwar in einem Baum gespeichert, der Pfad von einer Person X zu ihren Vorfahren soll in einer Methode gibIndividuum() allerdings in Form eines Stacks gespeichert werden:

Stack pfadZumIndividuum = new Stack();

Bei der Aufgabe von 2016 geht es um einen Containerhafen, hier werden mehrere Stapel von Containern verwaltet.

In keiner der Abituraufgaben müssen die Schüler(innen) Methoden der Klasse Stack selbst implementieren. Die Methoden der Klasse Stack werden aber von anderen Algorithmen verwendet, um bestimmte Probleme zu lösen oder Aufgaben zu erledigen.

Queue

Auch eine Queue oder Schlange kann abstrakt definiert werden. Aufgaben mit diesem Datentyp kommen im Zentralabitur NRW etwas häufiger dran als Stack-Aufgaben, daher lohnt es sich in der Abiturvorbereitung, wenn die Zeit knapp ist, zunächst die Klasse Queue zu wiederholen.

• 2007: Schlange mit Personen
• 2008: Prioritätsschlange mit Patienten
• 2012: Wiedergabeliste eines Players
• 2015: Notrufe einer Polizeizentrale
• 2017: Autofähre

Was die Sache etwas komplizierter macht: Oft wird keine einfache Queue eingesetzt, sondern eine Priority Queue, also eine Prioritäts-Warteschlange. Eine solche Priority Queue lässt sich im Prinzip völlig simpel implementieren: Zunächst implementiert man eine einfache Queue, dann erzeugt man einen Array aus drei oder vier Queue-Objekten, jenachdem, wie viele Prioritäten zu verwalten sind. Jede Priorität wird dann in einer eigenen Queue verwaltet.

Im schriftlichen Abitur wird den Schüler(innen) die Sache allerdings nicht ganz so einfach gemacht.

Ein Implementationsdiagramm aus der Aufgabe von 2017 (Autofähre)

Hier sehen wir ein Implementationsdiagramm aus einer Abituraufgabe von 2017. Es geht um eine Autofähre und die Autos, die sich vor der Fähre in mehreren parallelen Spuren (Queues) aufstellen. Die Klasse Spur hat ein Attribut schlange der Klasse Queue. In diesem Attribut können die Autos gespeichert werden, die in der jeweiligen Spur gerade auf die Fähre warten.

An sich ist die offizielle Klasse Queue abstrakt in dem Sinne, dass alle möglichen Objekte in ihr gespeichert werden können (Inhaltstyp bzw. ContentType = Objekte der Klasse Object). Allerdings macht eine solche Implementierung manchmal Probleme, vor allem dann, wenn man Objekte aus dem Datentyp extrahieren möchte, wie es beispielsweise bei Methoden wie gibErstesFahrzeug() der Fall ist. Normalerweise muss man dazu ein Typecasting durchführen wie

Fahrzeug vorne = (Fahrzeug) schlange.front();

An sich würde schlange.front() nur eine Instanz der Klasse Objekt liefern. Durch die Angabe

Queue<Fahrzeug>

im Java-Quelltext legt man aber den Inhaltstyp der Schlange auf Objekte der Klasse Fahrzeug fest, so dass bei der Extraktion von Objekten kein Typecasting notwendig ist.

Eine typische Aufgabe zum Thema Queue sieht dann im Abitur zum Beispiel so aus:

"Erläutern Sie, warum die Klasse Queue zur Modellierung innerhalb der Klasse Spur geeignet ist und erläutern Sie eine Alternative."

oder

"Implementieren Sie die Methode ermittleGesamtgewicht der Klasse Spur."

Hier sollen die Schüler(innen) eine Methode implementieren, mit der das Gesamtgewicht der Fahrzeuge einer Spur ermittelt werden soll, damit die Fähre nicht umkippt, wenn zu viele schwere Fahrzeuge auf der linken oder rechten Seite der Fähre stehen. Dazu müssen die Schüler(innen) dann die Methoden der Klasse Queue verwenden, um die einzelnen Fahrzeuge zu extrahieren und deren Einzelgewicht zu summieren. Natürlich darf die Reihenfolge der Fahrzeuge durch das Anwenden dieser Methode nicht verändert werden. Dumm nur, dass man immer nur auf das erste Fahrzeug der Queue zugreifen kann. Also muss man die Queue Stück für Stück abbauen und dann wieder 1:1 rekonstruieren. Bei einer Queue ist das allerdings - im Gegensatz zu einem Stack - recht einfach: Man nimmt das vordere Fahrzeug, analysiert es und steckt es dann gleich wieder hinten in die Queue hinein. Allerdings muss man sich dann in einer Hilfsvariable merken, welches das erste Fahrzeug der ursprünglichen Queue ist.

List

Das ist wohl der am häufigsten verwendete Datentyp in den Aufgaben zum Zentralabitur NRW:

• 2010: Liste mit Büchern
• 2011: Kartenspiel, für die Karten, die man in der Hand hält
• 2012: Wiedergabeliste eines Musikplayers
• 2013: Kopfrechentraining
• 2014: Druckerwarteschlange
• 2016: Warentransport
• 2017: Autofähre
• 2018: Einbruchsliste
• 2019: Radiosender
• 2020: Sitzplätze im Zug

Die offizielle Dokumentation der Klasse List ist sehr umfangreich und enthält Methoden, die wohl noch aus der Zeit stammen, als die Leute mit sogenannten Cassettenrecordern Musik hörten. Da gibt es dann Methoden wie hasAccess(), die den Wert true liefert, wenn es ein aktuelles Objekt in der Liste gibt (wenn die Cassette eingelegt ist?). Oder die Methode next(), die die Liste (die Cassette) um ein Objekt (einen Song) weiterspult. Eine Methode previous() ist in der aktuellen Dokumentation von 2020 nicht vorgesehen. Mit toFirst() und toLast() kommt man zum ersten bzw. zum letzten Lied der Cassette. Mit getContent() wird das aktuelle Objekt zurückgegeben, falls es überhaupt ein solches gibt. Bei der Cassette würde also das Lied abgespielt, das gerade unter dem Wiedergabe-Kopf ist.

Nun kommen ein paar Methoden, die über die Möglichkeiten eines Cassettenrecorders hinausgehen. Mit setContent() kann man ein neues Objekt mitten in die Liste einfügen, allerdings wird dabei das bisherige aktuelle Element überschrieben, durch das neue Objekt also ersetzt. Mit insert() dagegen kann man ein neues Objekt in die Liste einfügen, und zwar vor dem aktuellen Objekt. Mit append() hängt man ein neues Objekt an das Ende der Liste. Auch ein remove() gibt es, hier wird das aktuelle Objekt gelöscht und das Objekt hinter dem aktuellen Objekt wird zum neuen aktuellen Objekt.

Mit concat() schließlich werden zwei Listen zusammengefügt, und zwar wird die als Parameter übergebene Liste an die vorhandene Liste angehängt.

Für nähere Informationen lesen Sie bitte die offiziele Dokumentation der Klasse List selbst.

Sehen wir uns nun die Abituraufgabe aus dem Jahr 2020 etwas näher an, in der die Klasse List eine Rolle spielt. Hier zunächst ein Implementationsdiagramm:

Implementationsdiagramm der Modellierung für die Verwaltung der Sitzplatzreservierungen in Zügen

Eine Bahngesellschaft besitzt mehrere Züge und will jetzt eine Sitzplanreservierung modellieren. Die Hauptklasse dieses Systems ist Verwaltung. Diese Klasse hat ein Attribut zuege, das ein Objekt der Klasse List<Zug> ist. Diese Liste kann also nur Objekte der Klasse Zug speichern.

Ein jedes Zug-Objekt wiederum hat ein Attribut waggons, das ebenfalls ein Objekt der Klasse List ist. Diese Liste kann Objekte der Klasse Waggon speichern.

Dieses System könnte man jetzt theoretisch weiterführen. Jeder Waggon könnte wieder ein Attribut haben, das ein Objekt der Klasse List ist, wobei diese Liste dann Objekte der Klasse Sitzplatz speichert.

Da aber die Zahl der Sitzplätze in einem Waggon eine feste Größe ist, hat man sich hier entschieden, die Sitzplätze in einem einfachen Array zu speichern.

Wie sehen nun typische Aufgabenstellungen in dieser typischen Klausur aus?

"Erläutern Sie im Sachkontext, welche Argumente dafür sprechen, die Datensammlung für die Züge als lineare Liste und die Datensammlung für die Sitzplätze als Feld (Array) zu realisieren."

Das sollte nicht allzu schwer sein, bringt daher auch nur 7 Punkte.

Dann kommt eine Methode wasLiefereIch() der Klasse Waggon im Java-Quelltext. Hier müssen die Schüler(innen) diese Aufgaben lösen:

• "Analysieren Sie die Methode und geben Sie für das Waggonobjekt zu „Waggon 15“ aus Abbildung 1 die Rückgabewerte für die Methodenaufrufe wasLiefereIch(true) und wasLiefereIch(false) an.
• Erläutern Sie, welche Eigenschaft ein Waggonobjekt hat, wenn der Aufruf wasLiefereIch(true) die Rückgabe -1 liefert.
• Erläutern Sie die Aufgabe der Methode im Sachzusammenhang"

Abbildung 1 ist dabei eine schematische Darstellung eines Zuges mit den Waggons und den Sitzplätzen.

In der nächsten Teilaufgaben sollen die Schüler(innen) dann einen Algorithmus entwickeln und erläutern und schließlich auch implementieren, in dem es um die Reservierung von Sitzplätzen geht. Dazu müssen die Methoden der Klasse List eingesetzt werden.

Auch in den beiden folgenden Teilaufgaben geht es um Modellierungen unter Zuhilfename von Methoden der Klasse List; am Ende wird eine alternative Modellierung vorgeschlagen, die von den Schüler(innen) dann kritisch beurteilt werden soll.

Tipps für die Abiturvorbereitung

Arbeiten Sie sich zunächst in die Klasse List ein, Sie sollten im Schlaf mit den vielen Methoden der Klasse umgehen können.

Dann sollten Sie sich möglichst viele Implementationsdiagramme aus den alten Abituraufgaben ansehen, die hier leider nicht im Originaltext zur Verfügung gestellt werden können, da der Stark-Verlag sämtliche Rechte an den alten Aufgaben aufgekauft hat. Die Bücher aus dem Stark-Verlag sind übrigens nicht schlecht, weil hier nicht nur die Aufgaben und Erwartungen abgedruckt, sondern auch sehr ausführlich erläutert werden.

Wenn Sie dann noch Zeit haben, kommt die Klasse Queue dran, vergessen Sie dabei nicht die priority Queue.

Wenn Sie dann immer noch etwas Zeit haben, schauen Sie sich die Klasse Stack an, die ja nun nicht so oft drangekommen ist, aber man weiß ja nie...

Und immer überlegen: Wann setzt man am besten welche Klasse ein? Oft wird verlangt, dass Sie begründen, warum für die Modellierung ein Stack, eine Queue oder eine List verwendet wird, oder dass Sie alternative Möglichkeiten diskutieren, also zum Beispiel den Stack durch einen einfachen Array ersetzen.

Was bisher noch nicht (oder so gut wie nicht) verlangt wurde, war die komplette Implementierung einer solchen Klasse. Einen einfachen Stack oder eine simple Queue sollten Sie allerdings im Schlaf implementieren können, wenn Sie guten Informatik-Unterricht hatten.

Was überhaupt nicht verlangt wurde, war die dynamische Implementation eines Stacks, einer Queue oder einer Liste, also mit Hilfe von Zeigern. Wenn was implementiert wurde, dann entweder mit einfachen Arrays oder mit Hilfe einer anderen Datenstruktur. Man kann beispielsweise die Methoden einer List verwenden, um einen Stack zu implementieren.

Viel Erfolg dann bei der anstehenden Informatik-Klausur!