Liste, Stapel, Schlange

Diese drei Begriffe werden oft in der objektorientierten Programmierung verwendet. Im Rahmen von Scratch (das betrifft die Zielgruppe) sind diese Anwendungen etwas überdimensioniert. Aber sie sind in Scratch eingeschränkt möglich und sollen deshalb für Interessierte kurz angeschnitten werden: das Array und die Liste.

Die Informatik nutzt zwei verschiedene grundlegende Strukturen, um Elemente linear im Speicher zu verwalten:
Die Datenstruktur Array speichert eine fixe Anzahl von gleichartigen bzw. gleich großen Elementen, die im Speicher zusammenhängend abgelegt werden. Die Größe eines Arrays wird beim Erzeugen des Arrayobjektes festgelegt. Weil die Größe des Arrays nicht mehr geändert werden kann, bezeichnet man das Array als eine statische Struktur.
Jedem Element ist eine Zahl (ein Index) zugewiesen. Mit einem Index kann man gezielt auf ein Element zugreifen.
Die Datenstruktur Liste speichert eine variable Anzahl von Elementen. Im Speicher können die Elemente irgendwo stehen. Die einzelnen Elemente sind miteinander ¨
verkettet. Die Größe einer Liste ist variabel. Zur Laufzeit kann eine Liste beliebig viel Elemente aufnehmen. Man bezeichnet deshalb eine Liste als eine dynamische Struktur.
Auf die einzelnen Elemente kann nur in der gegebenen Reihenfolge zugegriffen werden. Ausgehend vom ersten Element muss man allen Nachbar-Referenzen folgen, um
das gewünschte Element zu erreichen.

So weit kurz die Theorie. Scratch benutzt eine Mischform aus Array und Liste und bezeichnet das Ergebnis als Liste. Listen lassen sich in der Palette Variablen generieren. Sobald dies geschehen ist, stehen entsprechende Blockbefehle zu Verfügung.

hg

Ablegen von Elementen:

füge ( ) zu Liste hinzu: das entsprechende Element wir immer am Ende der Liste eingefügt. Ist die Liste leer, kommt das Element an die erste Stelle.

füge ( ) bei 1 in Liste ein: das entsprechend Element wir an der entsprechenden Position in die Liste eingefügt. Alle anderen Elemente werden automatisch nach hinten verschoben.

ersetze Element x von Liste durch Element: Wenn die Position eines Elementes bekannt ist, kann dieses Element durch ein anderes ersetzt werden.

Löschen von Elementen:

Es gibt zwei Löschbefehle. Der eine Befehl löscht die komplette Liste, bei dem anderen muss die Position des zu löschenden Elements bekannt sein. Wenn das Element gelöscht ist, rutschen die anderen Elemente entsprechend vor.

Verwaltung der Liste:

Scratch stellt mehrere Befehle zur Verwaltung der Liste bereit. Mit diesen Befehlen kann gezielt nach einem Objekt gesucht werden, es kann die Länge der Liste ausgelesen werden, die Liste kann sichtbar oder unsichtbar gemacht werden.

Erstellen und Verwalten einer Liste

Die Einsatzmöglichkeit der Listenstruktur soll an einem einfachen Beispiel aufgezeigt werden. In einer Liste werden 100 Zufallszahlen (Wert zwischen 1 und 100) gespeichert. Anschließend wir überprüft, wie oft jede Zahl generiert wurde. In einem dritten Schritt werden alle doppelt und mehrfach generierten Zufallszahlen aus der Liste gelöscht. In einem vierten Schritt wird wieder geprüft, wie oft jetzt jede Zahl in der Liste vorhanden ist.

Das gesamte Programm wird dementsprechend in vier Blöcke aufgeteilt. Zum Starten der einzelnen Blöcke braucht man keinen Befehl aus der Palette der Ereignisse; es genügt, den entsprechenden Block anzuklicken.

      

Beide Listen werden zuerst gelöscht. 100 Felder der Liste Test2 werden mit dem Wert 0 vorbelegt, denn zu Beginn kommen alle Zufallszahlen zwischen 1 und 100 null mal vor. Anschließend werden 100 Zufallszahlen im Bereich 1 bis 100 generiert.

   

Dieser Programmteil überprüft die Häufigkeit der vorkommenden Zufallszahlen. Die Schleifenvariable i durchsucht die Liste Test von Feld 1 bis Feld 100. Über die Variable j wird geprüft, welche Zahl zwischen 1 und 100 im Feld gespeichert wurde. Wenn der Feldinhalt von Test mit der Zählvariable j identisch ist, wird in der Liste Test2 das entsprechende Zahlenfeld um 1 erhöht. Aus dem Beispielsdurchlauf ist zu erkennen, dass die Zahl 3 z.B. viermal generiert wurde, die Zahlen 9 und 11 keinmal.

Im nächsten Programmteil werden alle mehrfach vorkommenden Zahlen gelöscht. Wie aus dem Beispiel ersichtlich wird, wird die Liste Test von 100 Elementen auf 68 gekürzt. 32 Zahlen sind also mehrfach vorgekommen oder anders ausgedrückt; von 100 denkbaren Zufallszahlen zwischen 1 und 100 wurden nur 68 generiert. Die Variablen i und j bezeichnen zwei Felder in der Liste Test. Da zu Beginn 100 Zahlen denkbar sind, wird die Zählschleife auf 100 gesetzt. Jedes Mal, wenn eine Zahl gestrichen wird, wird diese Schleifenzahl um 1 erniedrigt. Die erste Zahl der Liste wird mit allen folgenden Zahlen der Liste verglichen. Sind Zahlen identisch, wird die zweite Zahl gestrichen und die Schleifenzahl k erniedrigt. Anschließend wird die zweite Zahl der Liste mit allen folgenden verglichen, bei Gleichheit  wieder die höher stehende Vergleichszahl gestrichen und k erniedrigt. Dieses Verfahren wird solange wiederholt, bis die Liste Test abgearbeitet ist.

 

Der vierte Programmteil greift noch einmal den zweiten Programmteil auf und listet die erzeugten Zufallszahlen und deren Anzahl auf. Wenn alle Programmteile richtig gearbeitet haben, dürfen in der Liste Test2  nur die Zahlen 0 und 1 erscheinen.

Sortieren einer Liste

Damit man mit Listen vernünftig arbeiten kann, sollte sie sortiert vorliegen. Ein gern angeführtes Beispiel ist das Telefonbuch. Scratch enthält zwar Befehlsmöglichkeiten, Elemente in einer Liste zu finden. Mit sortierten Listen geht es jedoch schneller. An dieser Stelle soll jetzt nicht über Sortieralgorithmen und ihre unterschiedlichen Fähigkeiten diskutiert werden, sondern hier soll ein einfaches Verfahren vorgestellt werden, mit dem man verständlich arbeiten kann. Dieses Verfahren ist als BubbleSort bekannt.

Schritt Was tun Ergebnis dieses Schrittes
  Ausgangslage 3 4 1 5 2
1 Wähle das erste Paar: 3 und 4 3 4 1 5 2
2 3 ist nicht größer als 4, also nichts tun 3 4 1 5 2
3 Wähle zweites Paar: 4 und 1 3 4 1 5 2
2 4 ist größer als 1, also tauschen 3 1 4 5 2
3 Wähle drittes Paar: 4 und 5 3 1 4 5 2
2 4 ist nicht größer als 5, also nicht tun 3 1 4 5 2
3 Wähle viertes Paar; 5 und 2 3 1 4 5 2
2 5 ist größer als 2, also vertauschen 3 1 4 2 5
4 Endes des Array erreicht, größte Zahl am Ende des Arrays 3 1 4 2 5
5 In diesem Durchgang wurde getauscht, also noch ein Durchgang 3 1 4 2 5
1 Wähle das erste Paar: 3 und 1 3 1 4 2 5
2 3 ist größer als, also vertauschen 1 3 4 2 5
3 Wähle zweites Paar: 3 und 4 1 3 4 2 5
2 3 ist nicht größer als 4, also nichts tun 1 3 4 2 5
3 Wähle drittes Paar: 4 und 2 1
 3 4 2 5
2 4 ist größer 2, also vertauschen 1 3 2 4 5
4 Ende des Durchgangs, da letztes Feld richtig ist 1 3 2 4 5
5 In diesem Durchgang wurde getauscht, also noch ein Durchgang 1 3 2 4 5
1 Wähle erstes Paar: 1 und 3 1 3 2 4 5
2 1 ist nicht großer als 3, also nicht tun 1 3 2 4 5
3 Wähle zweites Paar: 3 und 2 1 3 2 4 5
2 3 ist größer als 2, also vertauschen 1 2 3 4 5
4 Ende des Durchgangs, da die beiden letzten Felder bereits richtig sind 1 2 3 4 5
5 In diesem Durchgang wurde getauscht, also noch ein Durchgang 1 2 3 4 5
1 Wähle erstes Paar: 1 und 2 1 2 3 4 5
2 1 ist nicht größer 2, also nichts tun 1 2 3 4 5
4 Ende des Durchgangs, die letzten drei Felder sind richtig 1 2 3 4 5
5 In diesem Durchgang wurde nicht getauscht, also kein Durchgang mehr 1 2 3 4 5

Das entsprechende Programm könnte wie folgt aussehen:

Näheres zu diesem und anderen Sortierverfahren findet man im Internet bzw., auf den anderen Seiten dieser Homepage.

Schlange

In der Informatik werden mit dem Begriff Schlange die Funktionen isEmpty, enqueue, dequeue und front verbunden. Die Schlange ist eine Liste mit wenigen Funktionen. isEmpty testet, ob die Liste leer ist, enqueue fügt ein Element am Ende der Liste ein, dequeue entfernt das erste Element der Liste und front liest das erste Element der Liste. Die Funktionsweise einer Schlange oder Queue lässt sich sehr einfach durch das Kürzel FiFo beschreiben: First in, first out. Mit Scratch lassen sich Schlangen gut realisieren. isEmpty kann durch den Befehlsblock Länge von (Liste) mit Vergleich auf Null realisieren, enqueue durch den Befehl füge  (x) zu (Liste) hinzu,  dequeue durch den Befehl lösche (1) aus (Liste), und front durch den Befehl Element (1) von (Liste). Eine Simulation soll die Funktionsweise der Schlange zeigen:

Durch Druck auf den blauen Button wird automatisch ein Namen aus einer Liste Namen ausgewählt und in die Liste Patienten eingefügt. Der erste Patient in der Liste wird automatisch aufgerufen. Die Behandlungsdauer ist zufallsabhängig. Für den grünen Button wird das folgende Skript benötigt:

Für den blauen Button steht das folgende Skript zur Verfügung:

Eine Zufallsnamenliste ist sehr einfach zu erzeugen:

 

 

Stapel

Mit Stapel sind Funktionen wie isEmpty, push, pop und top. isEmpty testet ob der Stapel (Liste) leer ist, push fügt ein Element zu Beginn der Liste ein, pop entfernt das erste Element einer Liste und top listet das erste Element der Liste auf. Wie für die Schlange gibt es auch für den Stapel oder Stack eine kurze Beschreibung FiLo: First in, last out. Wie bei der Schlange lassen sich in Scratch auch Stapel realisieren. isEmpty kann durch den Befehlsblock Länge von (Liste) mit Vergleich auf Null realisieren, push durch den Befehl füge  (x) bei (1)  in (Liste) ein,  pop durch den Befehl lösche (1) aus (Liste), und top durch den Befehl Element (1) von (Liste). Die Simulation eines Rangiergleises soll die Funktionsweise des Stapels verdeutlichen: Vorgegeben ist ein Güterbahnhof mit drei Abstellgleisen A, B und C. Auf Gleis A stehen nummerierte Wagons, die so rangiert werden sollen, dass sie anschließend sortiert auf Gleis C stehen. Einige Vorgaben müssen beachtet werden:

Bild aus Ablauf

 

Für die oben abgebildete Situation kann nach folgender Strategie vorgegangen werden:

Ein grober Algorithmus kann wie folgt formuliert werden:

Wagons werden so lange von A nach C geschoben, wie dies die gewünschte Ordnung zulässt.

Wenn der nächste Wagon in A eine größere Nummer hat als der erste auf Gleis C, müssen die falschen Wagons aus C in B abgestellt werden.

Wenn Gleis A leer ist, werden die Funktionen der Gleise A und B getauscht.

Etwas genauer ist das Struktogramm:

Daraus lässt sich das Programm entwickeln.