{"id":2601,"date":"2009-11-09T14:00:21","date_gmt":"2009-11-09T13:00:21","guid":{"rendered":"https:\/\/www.herr-rau.de\/wordpress\/?p=2601"},"modified":"2023-05-24T14:09:02","modified_gmt":"2023-05-24T12:09:02","slug":"einfach-verkettete-listen-meine-materialsammlung","status":"publish","type":"post","link":"https:\/\/www.herr-rau.de\/wordpress\/2009\/11\/einfach-verkettete-listen-meine-materialsammlung.htm","title":{"rendered":"Einfach verkettete Listen: meine Materialsammlung"},"content":{"rendered":"
(12 Kommentare.<\/a>)<\/small> <\/div>\n

Ich habe schon mal<\/a> etwas \u00fcber Listen geschrieben, wo ich das Konzept etwas ausf\u00fchrlicher erkl\u00e4re. Ich wiederhole ein bisschen davon hier, will aber vor allem mein bisher erstelltes Material pr\u00e4sentieren, falls es jemand brauchen kann. (Zielgruppe: bayerische Informatiklehrer der 11. Klassen.)<\/em><\/p>\n\n\n\n

Einf\u00fchrung<\/h3>\n\n\n\n

Nehmen wir an, wir wollen ein Computerspiel programmieren. Im Spiel gibt es einen Helden, Threepwood<\/strong> genannt. Und es gibt viele Gegenst\u00e4nde<\/strong>, die Threepwood aufheben und mitnehmen und wieder loswerden kann, darunter: Schaufel, Klavier, Spielkarte<\/strong>.<\/p>\n\n\n\n

Diese Bausteine werden jeweils separat programmiert und man hat eine Welt voller Gegenst\u00e4nde mit einem Helden drin. Wie kommt der Held aber an die Gegenst\u00e4nde?<\/p>\n\n\n\n

Diese Verbindung wird durch eine Liste<\/strong> hergestellt. Threepwood hat neben der \u00fcblichen Spiel-Attributen wie St\u00e4rke, Geschicklichkeit, Lebenspunkte<\/em> auch ein Attribut Ausr\u00fcstung<\/em>. Die ersten drei Attribute sind vom Typ „ganze Zahl“, englisch integer<\/em>, k\u00f6nnen also Werte von 0 bis 100 annehmen (genauer: von -2147483648 bis 2147483647, aber wir brauchen nur den kleinen mittleren Bereich). Das Ausr\u00fcstungsattribut ist vom Typ „Liste“.<\/p>\n\n\n\n

In Java sieht das so aus:<\/p>\n\n\n\n

int st\u00e4rke;\nint geschicklichkeit;\nint lebenspunkte;\nListe ausr\u00fcstung; <\/code><\/pre>\n\n\n\n
Das erste Wort ist der Datentyp<\/strong> des Attributs, das zweite Wort ein Bezeichner daf\u00fcr, den man sich selbst aussuchen kann.<\/p>\n\n\n\n
Typische Methoden einer Liste sind: etwas hinten einf\u00fcgen, etwas vorne einf\u00fcgen, nach etwas suchen, die Liste sortieren, etwas entfernen, das erste oder letzte Element entfernen und einige weitere.<\/p>\n\n\n\n
Im Spiel wird die Liste dann so eingesetzt:<\/p>\n\n\n\n
threepwood.ausr\u00fcstung.einf\u00fcgenVorn(schaufel);\nthreepwood.ausr\u00fcstung.einf\u00fcgenVorn(klavier);\nthreepwood.ausr\u00fcstung.einf\u00fcgenVorn(spielkarte);<\/code><\/pre>\n\n\n\n
Und schon tr\u00e4gt er drei Sachen mit sich herum. Soll er die Schaufel loswerden, dann schreibt man:<\/p>\n\n\n\n
threepwood.ausr\u00fcstung.entfernen(schaufel);<\/code><\/pre>\n\n\n\n
Und schon hat der die Schaufel nicht mehr, egal ob sie vorher am Anfang oder Ende der Liste oder irgendwo dazwischen war.<\/p>\n\n\n\n
Wie die Liste das genau macht, Gegenst\u00e4nde hinzuzuf\u00fcgen und zu entfernen, zu sortieren, zu durchsuchen, das muss den Programmierer dabei nicht interessieren. Den Informatiker und Elftkl\u00e4ssler schon, denn Listen sind ein zentraler Gegenstand im Informatikunterricht dieser Jahrgangsstufe.<\/p>\n\n\n\n
Material zu den Listen<\/h3>\n\n\n\n
Einfach verkettete Listen sehen so aus:<\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Was da unten baumelt wie P\u00e4ckchen am Adventskalender sind die verwalteten Elemente, also im Spiel oben die Gegenst\u00e4nde. Die h\u00e4ngen an Knoten, weil die Liste die Knoten dazu benutzt, die ganze Arbeit zu erledigen (sortieren, einf\u00fcgen etc.). Das geht die verwalteten Elemente n\u00e4mlich nichts an.<\/p>\n\n\n\n
Die Methoden der Liste – Einf\u00fcgen vorn, hinten oder vor einem bestimmten zweiten Element; durchsuchen und sortieren – werden nach dem Lehrplan der 11. Klasse alle rekusiv programmiert. Um das f\u00fcr Sch\u00fcler verst\u00e4ndlicher zu machen, habe ich verschiedene Pr\u00e4sentationen angelegt, die ich hier zeigen will. Als Materialgrube f\u00fcr inzeressierte Lehrer und Sch\u00fcler, nicht als Einf\u00fchrung die rekursiven Methoden einer Liste. Wer also gar nichts \u00fcber Rekursion wei\u00df, wird mit die Folien allein m\u00f6glicherweise nicht weit kommen.<\/p>\n\n\n\n
Pr\u00e4sentationen I<\/h3>\n\n\n\n
Beispiel: Einf\u00fcgen eines Datenelements vor einem anderen<\/h4>\n\n\n\n
Wenn ein Datenelement vor einem bestimmten anderen eingef\u00fcgt 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\u00fcck bis zum Anfang durchlaufen, da jeder Knoten aus technischen Gr\u00fcnden etwas zur\u00fcckmeldet.<\/p>\n\n\n\n
Das ist die erste Methode, die Sch\u00fclern Schwierigkeiten bereitet, finde ich. Der R\u00fcckgabewert wird dazu genutzt, den Nachfolger neu zu besetzen (wenn auch meist mit dem alten Wert).<\/p>\n\n\n\n
\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n<\/figure>\n\n\n\n
Weitere Beispiele<\/h4>\n\n\n\n
Pr\u00e4sentationen in dieser Art gibt es noch zu:<\/p>\n\n\n\n