Einfach verkettete Listen: meine Materialsammlung

Ich habe schon mal etwas über Listen geschrieben, wo ich das Konzept etwas ausführlicher erkläre. Ich wiederhole ein bisschen davon hier, will aber vor allem mein bisher erstelltes Material präsentieren, falls es jemand brauchen kann. (Zielgruppe: bayerische Informatiklehrer der 11. Klassen.)

Einführung

Nehmen wir an, wir wollen ein Computerspiel programmieren. Im Spiel gibt es einen Helden, Threepwood genannt. Und es gibt viele Gegenstände, die Threepwood aufheben und mitnehmen und wieder loswerden kann, darunter: Schaufel, Klavier, Spielkarte.

Diese Bausteine werden jeweils separat programmiert und man hat eine Welt voller Gegenstände mit einem Helden drin. Wie kommt der Held aber an die Gegenstände?

Diese Verbindung wird durch eine Liste hergestellt. Threepwood hat neben der üblichen Spiel-Attributen wie Stärke, Geschicklichkeit, Lebenspunkte auch ein Attribut Ausrüstung. Die ersten drei Attribute sind vom Typ “ganze Zahl”, englisch integer, können also Werte von 0 bis 100 annehmen (genauer: von ‑2147483648 bis 2147483647, aber wir brauchen nur den kleinen mittleren Bereich). Das Ausrüstungsattribut ist vom Typ “Liste”.

In Java sieht das so aus:

int stärke;
int geschicklichkeit;
int lebenspunkte;
Liste ausrüstung;

Das erste Wort ist der Datentyp des Attributs, das zweite Wort ein Bezeichner dafür, den man sich selbst aussuchen kann.

Typische Methoden einer Liste sind: etwas hinten einfügen, etwas vorne einfügen, nach etwas suchen, die Liste sortieren, etwas entfernen, das erste oder letzte Element entfernen und einige weitere.

Im Spiel wird die Liste dann so eingesetzt:

threepwood.ausrüstung.einfügenVorn(schaufel);
threepwood.ausrüstung.einfügenVorn(klavier);
threepwood.ausrüstung.einfügenVorn(spielkarte);

Und schon trägt er drei Sachen mit sich herum. Soll er die Schaufel loswerden, dann schreibt man:

threepwood.ausrüstung.entfernen(schaufel);

Und schon hat der die Schaufel nicht mehr, egal ob sie vorher am Anfang oder Ende der Liste oder irgendwo dazwischen war.

Wie die Liste das genau macht, Gegenstände hinzuzufügen und zu entfernen, zu sortieren, zu durchsuchen, das muss den Programmierer dabei nicht interessieren. Den Informatiker und Elftklässler schon, denn Listen sind ein zentraler Gegenstand im Informatikunterricht dieser Jahrgangsstufe.

Material zu den Listen

Einfach verkettete Listen sehen so aus:

Was da unten baumelt wie Päckchen am Adventskalender sind die verwalteten Elemente, also im Spiel oben die Gegenstände. Die hängen an Knoten, weil die Liste die Knoten dazu benutzt, die ganze Arbeit zu erledigen (sortieren, einfügen etc.). Das geht die verwalteten Elemente nämlich nichts an.

Die Methoden der Liste – Einfügen vorn, hinten oder vor einem bestimmten zweiten Element; durchsuchen und sortieren – werden nach dem Lehrplan der 11. Klasse alle rekusiv programmiert. Um das für Schüler verständlicher zu machen, habe ich verschiedene Präsentationen angelegt, die ich hier zeigen will. Als Materialgrube für inzeressierte Lehrer und Schüler, nicht als Einführung die rekursiven Methoden einer Liste. Wer also gar nichts über Rekursion weiß, wird mit die Folien allein möglicherweise nicht weit kommen.

Präsentationen I

Beispiel: Einfügen eines Datenelements vor einem anderen

Wenn ein Datenelement vor einem bestimmten anderen eingefügt werden soll, wird die Liste einmal durchlaufen bis zu dem gesuchten Element. (Oder bis zum Schluss, was auch immer zuerst kommt.) Dann wird das neue Datenelement mit einem neuen Knoten eingebaut. Danach wird die Liste wieder zurück bis zum Anfang durchlaufen, da jeder Knoten aus technischen Gründen etwas zurückmeldet.

Das ist die erste Methode, die Schülern Schwierigkeiten bereitet, finde ich. Der Rückgabewert wird dazu genutzt, den Nachfolger neu zu besetzen (wenn auch meist mit dem alten Wert).

Diese Diashow benötigt JavaScript.

Weitere Beispiele

Präsentationen in dieser Art gibt es noch zu:

  • allgemein: Funktion ohne Rückgabewert
  • allgemein: Funktion mit Rückgabewert
  • Berechnen der Länge einer Liste
  • Einfügen eines Datenelements vor einem bestimmten anderen (s.o.)
  • Einfügen eines Datenelements ganz hinten
  • Suchen nach einem bestimmten Datenelement in der Liste

Hier gibt’s alle Präsentationen (odp) zum Herunterladen. Technische Hinweise unten.

Präsentationen II

Angefangen habe ich aber nicht mit diesen abstrakten Präsentationen, sondern mit meinen Dschinn. Die Vorgeschichte:

Im Reich der Schätze und Dschinn

Harun ar-Raschid, Kalif von Baghdad, der herrlichsten Stadt des Landes und aller anderen Länder unter der Sonne, hatte viele Frauen, viele Paläste, viele Schätze. Eifersüchtig hütete er seinen Besitz und war stets voller Misstrauen, deshalb verfügte er, dass jedes Stück durch einen Dschinn, einen Geist, bewacht werden sollte.
Jeder Dschinn erhielt eine Kiste für das Gut, das er bewachen konnte. So konnte es dem Dschinn egal sein, was er bewachte, Hauptsache, es passte in die Kiste.
Nun hatte Harun so viel Besitztümer, dass er sie nicht zählen konnte, so viele, dass er ihre Namen nicht wusste, so viele, dass er sie nicht zu finden wusste, wenn es ihm nach einem besonderen Kleinod verlangte.
Deshalb verfügte er, dass sich in Zukunft Verwalter um die Fülle seines Besitzes kümmern sollten. Den ersten unter ihnen, Jaffar, ernannte er zum Herren über die Schätze, also Juwelen und Perlen und Ringe und anderes Geschmeide.
Jaffar erhielt eine magische Lampe, in der ein Dschinn wohnte, der einen Schatz bewachte. Und dieser Dschinn hatte ebenfalls eine Lampe, und in dieser hauste ein weiterer Dschinn mit seinem Schatz, und auch der hatte wieder eine Lampe mit einem Dschinn darin.
Nur der letzte Dschinn, der bewachte zwar auch noch einen Schatz, er hatte auch eine Lampe, aber diese Lampe war leer und kein weiterer Dschinn wohnte darin.

Beispiel: Einfügen eines Datenelements vor einem anderen

Das ist die gleiche Methode wie oben in der Diaschau, nur eben mit Dschinns. Aus technischen Gründen diesmal als Video ohne Blättermöglichkeit oder Ton – früher war das Flash, aber das baue ich nach und nach aus dem Blog aus:

Weitere Beispiele

Präsentationen in dieser Art gibt es noch zu:

  • Berechnen der Länge einer Liste (einfach)
  • Berechnen der Länge einer Liste (composite pattern)
  • Suchen nach einem bestimmten Datenelement in der Liste (einfach)
  • Einfügen eines Datenelements vorn (einfach und composite)
  • Einfügen eines Datenelements vor einem bestimmten anderen (einfach, s.o.)
  • Einfügen eines Datenelements ganz hinten (einfach)
  • Einfügen eines Datenelements ganz hinten (composite pattern)
  • Volle Listen, leere Listen, Vorteil des Datenelement-Interface

Anmerkungen

Einsatz im Unterricht: Powerpoint-Karaoke

Die Präsentationen habe ich zur Visualisierung eingesetzt, aber auch zum Ausfragen. Mit einer bekannten oder unbekannten Präsentation muss ein Schüler eine (natürlich bekannte) Methode erklären. Auch gut zur Wiederholung.

Die technische Seite

Die Dschinn-Bilder habe ich mit Inkscape und meinem Grafiktablett gezeichnet. (Tipp: Umrisse zeichnen, farbig ausfüllen, dann die Umrisslinien entfernen.) Um die Bilder in Präsentationen einbinden zu können, exportiere ich sie im Format PNG.

Die Präsentationen mache ich mit Open Office Impress. Dabei sind alle Bilder als verknüpfte Dateien gespeichert. Das heißt, es existiert zu jedem Motiv nur eine Bilddatei, die im selben Verzeichnis wie das Präsentationsdokument liegt. Der Nachteil: wenn ich schlaftrunken nur die Präsentation mit in die Schule nehme und die dazu gehörenden Bilddateien vergesse, dann kann ich mit dem Dokument wenig anfangen. Der Vorteil: wenn ich an den Grafiken etwas ändern möchte (Farbe ändern, Turban verschieben), muss ich nur die externe Datei verändern und – abrakadabra! – alle Präsentationen sind aktualisiert.

Bei den anderen Präsentationen habe ich mit Formatvorlagen gearbeitet, wenn auch nicht ganz systematisch. Das heißt, es gibt die Vorlagen “Knoten aktiv”, “Knoten inaktiv” und “Knoten wartend”; wenn ich in der Vorlage zum Beispiel die Farbe ändere, ändert sich auch die Farbe bei allen entsprechend zugewiesenen Knoten.

Die Dschinn-Filme erzeuge ich mit E.M. PowerPoint Video Converter. Das ist viel einfacher als das Abfilmen mit Video Capture, allerdings funktioniert das nur mit Microsoft Powerpoint, so dass ich dafür meine Impress-Dateien auch mal in diesem Format speichere. Aber ein Film, mit der fehlenden Kontrolle über die Geschwindigkeit des Voranschreitens, ist kein gutes Medium, sich mit diesen Inhalten zu beschäftigen. Die Sicherheit, selbst entscheiden zu können, wann es weitergeht, gibt eben das: Sicherheit.

Was ich gerne hätte

Ich hätte gerne eine Möglichkeit, Präsentationen in HTML-Seiten (wie dieses Blog) einzubauen, so dass auch die einzelnen Objekte auf einer Folie der Reihe nach gezeigt und eben auch wieder verborgen werden. Reinfliegen muss ja gar nichts, einfaches Erscheinen und Verschwinden reicht. Mein zugegeben recht altes Powerpoint kennt zwar solch eine Funktion (als Webseite speichern/Veröffentlichen/Weboptionen/Folienanimationen), das Ergebnis funktioniert aber nur unter dem Internet Explorer.
Bis jetzt kenne ich sonst nur Lösungen, die die vollständige Folie als Grafik präsentieren, mit allen Elementen darauf, die jemals auf ihr gezeigt wurden. So eine Diaschau habe ich bei der ersten Präsentation oben benutzt; bei trickfilmartigen Folien führt das aber zu unbrauchbaren Ergebnissen.

Denn: Diese Listen-Visualisierungen mit Dschinns sind keine Präsentationen im herkömmlichen Sinn, sondern kleine Trickfilme. Vermutlich sollte ich gar nicht erst mit Präsentationssoftware anfangen. Viel lieber wäre mir, das in einer Programmiersprache schreiben zu können. Das gäbe elegantere, flexiblere und leichter zu verändernde Filme. (Ich könnte die Befehle zur grafischen Darstellung gleich in die Java-Listenmethoden hineinschreiben. Dann gäb’s keine separaten Filme mehr, sondern die Java-Klassen würden selbst die Filme produzieren.)
Leider habe ich kaum Erfahrung mit dem Einbinden von Grafiken oder überhaupt GUI-Elementen in Java. Mir reicht eine Ein- und Ausgabezeile, die Darstellung reizt mich nicht. VBA kann ich auch nicht, das will ich aber auch nicht.

12 Antworten auf „Einfach verkettete Listen: meine Materialsammlung“

  1. bzgl. “Was ich gerne hätte”:
    An dieser Stelle fällt mir ganz spontan Flash ein!
    Es gibt diverse Powerpoint zu Flash Konverter. Da Flash sehr verbreitet ist, sollte es bzgl. der Browserkompatibilität keine Probleme geben!

  2. Meine Schulzeit ist nun schon eine Weile her, aber das dort gelernte “eine Liste ist entweder leer oder ein Element gefolgt von einer Liste” hat mir auch im Studium noch geholfen.

  3. Flash: Letztlich habe ich den Film oben ja als Flash eingebunden. Mir fehlt nur noch eine Möglichkeit, den Betrachter den Film manuell weiterzuschalten. Und da muss ich wohl Flash lernen und gleich mit Flash schreiben, oder ein Java-Applet schreiben. Aber ich schau mich mal weiter bei Konvertern um.

    Diese Listendefinition spielt für den aktuellen Lehrplan leider keine große Rolle. Ich kenne sie vom funktionalen Programmieren – sehr elegant.

    (An rekursives Denken muss man sich wirklich gewöhnen. Ein Schüler fing heute an, eine eigene Methode zu schreiben, um die Position eines Elements in der Liste zu ermitteln. Das funktioniert eigentlich genauso wie laengeGeben(), nur mit anderer Abbruchbedingung. Aber erst mal versucht man es doch immer imperativ. Aber schön, aus solchen falschen Ansätzen lernt man.)

  4. Mit Quicktime müsste das gehen. Zumindest kann Keynote (das Apple-Powerpoint) einen QT-Film erstellen, der auf Mausklicks wartet, wenn immer auch die Präsentation drauf wartet.
    Wie du jetzt aus OO oder PP Win den QT-Film rausbekommst, weiß ich nicht, aber technisch möglich müsste es ein.

  5. @Marc: Diese Version von Listen (Head/Tail Lists) wird in Prolog verwendet, ist sonst aber nicht so häufig. Die verkettete Liste funktioniert ähnlich aber nicht gleich.

    Was den Programmierer angeht, so sollte der schon um die Details seiner Listen wissen. Zwar wird er das (vor allem in Java) nicht selbst implementieren, aber er sollte sich für die passende Liste entscheiden, je nach dem welche Art von Zugriffen oft ausgeführt wird. Man muss ja nicht permanent Rechenzeit verschwenden. ;-)

    Sehr schön, dass das die Schüler bei Dir lernen, ich hatte nicht das Glück (Info in 12 und 13). Aber… ist der sensationelle Guybrush Threepwood den Schülern überhaupt bekannt? 8-)

  6. @AD Danke! Hab’s kurz ausprobiert, und ja, aus Keynote kann ich nicht nur einen Quicktime-Film exportieren, der auf Klicks wartet bei Folienübergang und benutzerdefinierter Animation (und den ich in eine Webseite einbauen kann), sondern ebenso eine Flash-Animation mit den gleichen Eigenschaften (die ich ebenfalls einbauen kann).

    Mit Impress kann ich zwar auch direkt nach Flash exportieren, aber eben nur die Folienübergänge und nicht die Animationen. Das gilt auch für die kostenlosen PP2Flash-Konverter, die ich ausprobiert habe

    Das Konvertieren Impress>PP>Keynote klappt zwar in Details nicht so recht, aber darum kann ich mich kümmern.

    Und nein, ich glaube, Guybrush kennen die Schüler nicht mehr. Letztes Jahr gab’s noch welche in der 13., die die SPiele gespielt haben oder noch spielten, aber ich denke, das war’s. (Mein Deutsch-LK kennt “Gremlins” nicht. Dabei kommt der doch immer um die Weihnachtszeit im Fernsehen.)

  7. Vielleicht wird dir SVG gefallen – sehr klare, sehr logische Syntax (im Wesentlichen XML). Das Umschalten zwischen SVGs kannst du z.B. durch Applets oder simple iframes mit Buttons darunter lösen. Dann sieht es so aus, als ob du Animationen startest.
    Mit SVG kann du auch z.B. Live Elemente mit der Maus verschieben (lassen). Da es sich um ein Vektorformat handelt, ist auch die Skalierung kein Problem – in der Schule groß, im Web halt kleiner.
    Tja – bloß der Explorer kann kein SVG – nur mit Plugin – aber irgendwas ist ja immer.

  8. Schau ich mir mal an. Aber früher oder später werde ich wohl doch mal in die Grafik bei Java einsteigen müssen. (SVG ist ein schönes Format. Ich arbeite selber viel mit Inkscape.)

  9. Komisch das Monkey Island keiner mehr kennt, immerhin gab es dieses Jahr ein neuen Teil, eine Remake und ne Ei-Pot Version.
    Aber was ich schreiben wollte,.. in Open Office läßt sich die Präsentation (das Gegenstück zu PowerPoint heißt dort Impress) direkt als Flash exportieren. Vielleicht hilft das weiter :) LG

  10. imperativ = falsch? .… also es gibt immer wieder gruende dinge nicht recursiv zu schreiben.

  11. Iterativ ist natürlich nicht falsch. (Ich sage den Schülern ja auch, dass man alle rekursiven Methoden auch iterativ programmieren kann; dass ein Rechner beim Rechnen ohnehin früher oder später jeden rekursiven Aufbau intern in einen iterativen umwandelt, weil er anders gar nicht rechnen kann.)

    Aber die Schüler sollen in diesem Jahr lernen, rekursiv zu programmieren. Iterativ können sie ja schon, und wenn sie nicht nach rekursiven Lösungen suchen, gewöhnen sie sich nicht daran bzw. werden sie das Prinzip nicht so leicht verstehen.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.