Doppelstunde 1: Konzept „Verkettung“
Ziel der Stunde ist, dass die Schülerinnen und Schüler verstehen, wie man eine Kette von Objekten bilden kann, indem sich jedes Objekt seinen Nachfolger merkt. Dabei wird zunächst nicht programmiert, stattdessen werden Schreibtischtests und Rollenspiele eingesetzt, um das Konzept der Verkettung darzustellen. Ausgehend von einem vorstellbaren Szenario nähert man sich der tatsächlichen Implementation im Computer.
Der Einstieg ist ein Szenario aus der „realen Welt“ (Präsentation 01_verkettung.odp): Die Reihenfolge der Patienten in einem Wartezimmer wird nicht zentral verwaltet, indem sich eine Person merkt, wer wann an der Reihe ist. Stattdessen wird durch eine einfache Regel dafür gesorgt, dass eine „Kette“ von Patienten gebildet: Jeder merkt sich die nächste Person, die nach ihm drankommt. Die Sprechstundenhilfe muss sich damit nur noch merken, wer vorne in der Schlange steht.
Eine alternative Lösung wäre, dass jeder Patient sich seinen Vorgänger merkt. Beim Betreten des Wartezimmers meldet sich der bisherige Letzte und der neue Patient muss sich diesen merken. Wenn die Sprechstundenhilfe den nächsten Patienten aufruft, geht derjenige, der keinen Vorgänger mehr hat, ins Behandlungszimmer. Sein Nachfolger weiß jetzt, dass er keinen Vorgänger mehr hat und damit als nächstes dran ist. Dieser Ansatz ist ebenfalls denkbar und möglich, führt aber nicht zu der hier beabsichtigten verketteten Liste. Hier gibt es ggf. Schwierigkeiten, wenn man später eine Person an der n-ten Position einfügen möchte.
Den Schülerinnen und Schülern wird das Szenario inklusive der Regeln beschrieben und sie bekommen den Auftrag, in Gruppenarbeit ein Regelwerk zu erarbeiten, damit das System funktionieren kann. Aufgabe der Lehrkraft ist in dieser Phase, die Ideen der Schülerinnen und Schüler in die richtige Richtung zu lenken, indem Situationen beschrieben werden, in der ihre bisherige Lösung fehlschlagen würde.
Nach der Erarbeitung werden die Vorschläge gesammelt und festgehalten. Die Präsentation enthält ein mögliches Regelwerk, nach der man arbeiten kann. Es bietet sich an, an der Tafel mit Strichmännchen (oder Bildern auf Karten mit Magneten) zu erarbeiten, was passiert, wenn ein neuer Patient ins Wartezimmer kommt bzw. was getan wird, wenn ein der nächste Patient zur Behandlung gerufen wird.
Zur Vertiefung erarbeitet man danach einen Algorithmus, mit dem man das Durchzählen, das Entfernen von Patienten und das wahlfreie Einfügen (an beliebigen Stelle, nicht nur der letzten) durchführen kann. Die erarbeitete Technik wird dann in einem Rollenspiel angewandt. Dazu können Sie mit Hilfe der Kopiervorlage 01_rollenspiel_verkettung.ods Kärtchen erstellen lassen. Die Kopiervorlage geht davon aus, dass der Kurs zwischen 8 und 24 Mitglieder hat. Tragen Sie dazu die Namen der Kursmitglieder in der ersten Tabelle im grauen Bereich ein. Wenn Sie die Namen in eine zufällige Reihenfolge bringen wollen, klicken Sie auf den Button „Namen mischen“. Dies funktioniert nur, wenn Sie beim Öffnen Makros aktiviert haben. Wenn Sie das nicht wünschen, werden die Namen in der Reihenfolge der Eintragung verwendet.
Drucken Sie die Tabelle „Karten“ aus, nach Möglichkeit zweiseitig (drehen an langer Seite) – auf diese Weise erhält jedes Kursmitglied ein Kärtchen mit dem Namen auf der einen und der „Rolle“ auf der anderen Seite. Ein/e Schüler/in ist die Sprechstundenhilfe und muss die Aufgaben erledigen. Sie kennt den ersten Patienten im Wartezimmer. Fünf Kursmitglieder sitzen im Wartezimmer und kennen jeweils ihren Nachfolger (mit Ausnahme des letzten). Zwei weitere Kursmitglieder werden später im Wartezimmer platziert.
Die letzte Seite der Tabelle ist für Sie gedacht, darauf steht, welche Ereignisse zu behandeln sind: Anhängen eines neuen Patienten, Einfügen eines Patienten an einer bestimmten Position in der Kette, Zählen der Patienten und Entfernen eines Patienten. Es wurden bewusst nicht alle Kursmitglieder mit Rollen versehen, damit z.B. das Durchzählen nicht einfach durch Zählen der Personen im Raum erledigt werden kann. Die zufällige Reihenfolge sorgt dafür, dass die Kursmitglieder auch nicht ohne Kenntnis der Verkettung wissen können, wer auf wen folgt. Wenn sich die Abfolge der Patienten im Wartezimmer ändert, sollen die Änderungen auch durch Überschreiben der Einträge auf den Kärtchen repräsentiert werden.
Im Arbeitsblatt 01_verkettung.odt nähert man sich weiter der tatsächlichen Implementation einer verketteten Liste an. Der erste Teil kann als Partner- oder Einzelarbeit durchgeführt werden, der zweite Teil ist als Einzelarbeit gedacht. Für den ersten Teil muss wieder ein wenig Vorbereitung investiert werden. Drucken Sie die Tabellen aus der Datei 01_verkettete_liste.ods aus:
- Tabelle „Listenknoten“: Für jede Gruppe benötigen Sie etwa sieben Listenknoten-Karten. Drucken Sie die Tabelle doppelseitig, so dass auf der Vorderseite jeweils „new Listenknoten(…)“ steht und auf der Rückseite der Inhalt des Listenknotens. Beachten Sie, dass die vierstelligen Nummern innerhalb jeder Gruppe eindeutig sein müssen.
- Tabelle „Liste“: Für jede Gruppe benötigen Sie zwei bis drei Listen-Karten.
Zur Durchführung der ersten Verkettungsübung legt man die Listenkarten offen auf den Tisch sowie die Listenknoten-Karten so, dass die Vorderseite (!) sichtbar ist. Die Karten werden zufällig auf dem Tisch verteilt. Dann ist die Aufgabe für die Schülerinnen und Schüler, die auf dem Arbeitsblatt genannten Listenoperationen durchzuführen. Dabei dürfen Kärtchen zwar umgedreht werden, aber nicht mehr verschoben werden.
- Eine Liste A wird erzeugt: Auf ein Listen-Kärtchen wird der Name „A“ geschrieben.
- An die Liste A wird ein Wert X angehängt: Ein Listenknoten-Kärtchen wird umgedreht. Das Umdrehen der Kärtchen entspricht im Folgenden immer dem Erzeugen eines neuen Listenknotens. Der Wert wird an die entsprechende Stelle auf die Karte geschrieben und der Liste wird die Nummer des ersten Listenknotens eingetragen.
- Wenn weiter hinten Werte angehängt werden, muss zuerst über die Nachfolger-Verweise der letzte Knoten gesucht werden. Dann wird diesem sein neuer Nachfolger eingetragen.
- In späteren Aufgaben werden neue Werte weiter vorne eingefügt oder entfernt. Dabei müssen Nachfolger-Verweise überschrieben werden oder der Liste muss ein neuer „Erster Knoten“ gesetzt werden.
Im zweiten Teil betrachtet man verkettete Listen, wie man sie sich im Arbeitsspeicher des Computers vorstellen kann. Auf dem Blatt wird der Arbeitsspeicher eines imaginären Computers dargestellt1 , der über 100 Speicherzellen verfügt. Jede dieser Speicherzellen kann eine Zahl von 00 bis 99 abspeichern. Die Speicherzellen sind zeilenweise durchnummeriert, d.h. die erste Zeile enthält die Speicherzellen von 00 bis 09, die zweite Zeile von 10 bis 19 usw.
Dieser Speicher enthält zwei Listen, die über den gesamten Speicher verstreut sind. Man kann die Listen durchlaufen, indem man die Nachfolger-Verweise verfolgt. Die Speicherzelle 02 (unten im blauen Kreis) verweist auf den ersten Knoten der Liste A (seine Adresse ist 16), die Speicherzelle 03 verweist auf den Anfang von Liste B (Adresse 34).
Bildquelle: Speicher mit zwei Listen ZPG Informatik [CC BY-NC-SA 3.0 DE], aus 01_unterrichtsverlauf.odt
Jeder Listenknoten besteht aus zwei aufeinanderfolgenden Speicherzellen. Im Beispiel rechts sind das die rot bzw. grün eingerahmten Zellen. Die erste Zelle ist der Datenwert, die zweite Zelle gibt die Adresse des Nachfolgers an. Wenn die zweite Zelle eine 00 enthält, steht dies für „kein Nachfolger“, d.h. das Ende der Liste.
Die rechte Tabelle enthält nochmals die identischen Zahlen, die im zweiten Teil der Aufgaben überschrieben werden können.
1 Die Darstellung ist von MikrSimD inspiriert. Zur Vereinfachung wurde die Hexadezimaldarstellung allerdings durch eine Dezimaldarstellung ersetzt.
Unterrichtsverlauf: Herunterladen [odt][187 KB]
Weiter zu DS 2: Verkettung implementieren