Die Überschriften a) bis d) verweisen auf die vorhergehenden Seiten, f) bis h) auf nachfolgende Seiten:| www.r-krell.de |
| Webangebot für Schule und Unterricht, Software, Fotovoltaik und mehr |
Willkommen/Übersicht > Informatik > Informatik mit Java, Seite e)
Teil e): Lineare Abstrakte Datentypen (Keller, Schlangen, Listen)
und einige Anwendungen (z.B. Tiefen- und Breitensuche)
Die Überschriften a) bis d) verweisen auf die vorhergehenden Seiten, f) bis h) auf nachfolgende Seiten:
a) Grundlegendes zu Java, benötigte Software (inkl. Downloadadressen) und Installation
b) Erste Java-Programme (u.a. Autorennen u. Aufzug) sowie Verweise (Links) auf fremde Java-Seiten
c) Sortieren und Suchen in Java sowie grafische Oberflächen mit der Java-AWT
d) Adressbuch- und Fuhrpark-Verwaltung sowie Datei-Operationen mit Java
e) Lineare Abstrakte Datentypen (Keller, Schlangen, Listen) und einige Anwendungen (z.B. Tiefen- und Breitensuche)
f) Abstrakter Datentyp Baum ([binärer] Sortierbaum, Rechenbaum, Spielbaum)
g) Abstrakter Datentyp Graph (Adjazenzmatrix u. -listen, typische Fragestellungen, Tiefen- u. Breitensuche)
h) Bau eines Compilers Java -> 1_AMOR (Syntaxdiagramm, Scanner, Parser, Variablentabelle, Codeerzeuger)
Eine vollständige Übersicht aller Java-Seiten gibt's auf der Informatik-Hauptseite!
zum Seitenanfang / zum Seitenende
Die Adressbuch- und Fuhrparkverwaltung (siehe meine Java-Seite d)) oder ähnliche Beispiele machen deutlich, dass viele Computer-Anwendungen Daten ablegen und bei Bedarf wieder holen müssen. Es lohnt sich daher, grundsätzlich über geschickte Datenspeicherung nachzudenken.
Der Umgang mit Dateien hat gezeigt, dass es für die Programmiererin oder den Programmierer einer Anwendung keineswegs nötig ist, die technischen Einzelheiten der Datenspeicherung zu kennen: Wer Daten aus einer Hochsprache in eine Datei ablegt, muss sich nicht mit FAT- oder NTFS-Dateisystemen herumschlagen, Clustergrößen oder Besonderheiten von Disketten- oder Festplatten kennen: Sie oder er schreibt einfach mit writeObject in einen FileOutputStream und liest bei Bedarf aus dem FileInputStream. Das heißt, es reicht eine abstrakte Vorstellung, wie in etwa eine Datei funktioniert (nämlich ähnlich wie ein Tonband oder wie eine Audiokassette, wo die Datensätze gleich Musik-Titeln irgendwie in einer Reihe hintereinander stehen und dass z.B. nach dem Lesen eines Datensatzes das Band, der Lesekopf oder der Dateizeiger oder was auch immer automatisch zum nächsten Datensatz weiter rückt, sodass beim nächsten Aufruf von readObject der nachfolgende Datensatz gelesen wird -- so wie beim Abspielen einer Kassette nach dem Hören eines Titels der nächste kommt). Dann braucht man nur noch ein paar Methoden (wie eben writeObject, readObject oder close), um mit dem Datenspeicher zu arbeiten.
Dabei haben Dateien gegenüber den bisher als Datenspeicher benutzten statischen Reihungen (Arrays) den Vorteil, dass sie dynamisch sind: Beim Anlegen muss man nicht angeben, wie groß die Datei wird. Sie belegt auf der Festplatte nur den Platz, den die tatsächlich abgelegten Datensätze benötigen. Andererseits ist der Dateizugriff relativ langsam und es nervt besonders, dass man aufwändig alle (anderen) Datensätze in eine neue Datei kopieren muss, wenn man nur einen Datensatz ändern will.
Ein besserer Datenspeicher wäre also vorzugsweise dynamisch und sollte das Hinzufügen oder Entfernen eines Datensatzes mit möglichst wenig Aufwand ermöglichen (am liebsten in jeweils nur einem Schritt und nicht abhängig von der Anzahl der bereits gespeicherten Daten).
Natürlich soll ein Datenspeicher anfangs leer sein, wenn er gerade neu erzeugt wurde. Weiterhin muss es möglich sein, Datensätze in den Speicher rein zu tun oder raus zu holen - wobei das Rausholen natürlich nur funktionieren kann, wenn (noch) Datensätze im Speicher sind und dieser nicht etwa leer ist. Und für viele Zwecke wäre es noch schön, wenn man sich auch mal einen Datensatz ansehen kann, ohne den Speicher zu verändern, also ohne den Datensatz ganz heraus holen und damit aus dem Speicher entfernen zu müssen. Mit diesen Forderungen haben wir den Datenspeicher schon soweit beschrieben, dass wir Methoden für die Bedienung des Speichers angeben können (oder - in objektorientierter Sprechweise - dass wir die Fähigkeiten des Speichers durch Methoden angeben können), die am einfachsten in einem Java-Interface vor- bzw. festgeschrieben werden [das vorangestellte E_ deutet auf die Zugehörigkeit zu dieser Java-Seite e) hin]:
| public interface E_Speicher // legt nur fest, welche Methoden jeder Datenspeicher haben muss - Krell, 29.5.2004 - www.r-krell.de { public void rein (Object element); // packt das übergebene Element in den Speicher public boolean istLeer(); // sagt, ob der Speicher leer ist public Object zeige(); // zeigt ein Element ohne Ändern des Speichers public Object raus(); // zeigt ein Element und löscht es aus dem Speicher |
Dabei wird als Typ für einen Datensatz (hier Element genannt) bewusst der allgemeinste Objekttyp Object benutzt, um das Speichern von Daten beliebiger Sorte zu ermöglichen. Die Bedienung des Datenspeichers mit rein und raus soll ja immer gleich erfolgen, egal was gespeichert wird. Außerdem sei betont, dass zeige ein gespeichertes Element als Ergebniswert an die aufrufende Stelle gibt und nicht etwa wirklich auf dem Bildschirm anzeigt - dafür muss, sofern das überhaupt gewünscht ist, das Programm bzw. Objekt sorgen, das zeige oder raus benutzt.
Um die Entwurfs-Überlegungen und -Entscheidungen für solche Datenspeicher deutlich zu machen, erfolgt hier die eigene Entwicklung ohne Rückgriff auf ähnliche, in Java vordefinierte Modelle.
zum Seitenanfang / zum Seitenende
1. linearer abstrakter Datentyp: Keller
Oben wurde noch nicht festgelegt, welches Element gezeigt oder heraus geholt wird, wenn der Datenspeicher viele Elemente enthält und zeige oder raus aufgerufen werden. Eine einfache Organisation der Daten orientiert sich an käuflichen Speicherelementen für Parkmünzen, Pfefferminz-Tabletten oder an Warmhalte-Maschinen für Teller in einem Restaurant: Die Elemente sind in einer (oft vertikalen) Reihe linear angeordnet und jeweils die Münze, der Teller bzw. der Datensatz oder das Element, der/die/das als Letztes mit rein gespeichert wurde, ist oben zu sehen (d.h. würde von zeige genannt) und wird beim nächsten raus als Erstes wieder entfernt. Man spricht von einem LIFO-Speicher (LIFO = last in - first out), einem Stack, Stapel oder eben von einem Keller.
Die Funktionalität des Kellers - Zugriff nur an einem Ende; wie viele Teller und welche Teller in der Maschine stecken bzw. was außer dem obersten Element vielleicht sonst im Speicher ist, ist nicht zu sehen - kann durch so genannte Axiome bzw. durch die Forderung „keller.rein (x) => x = keller.raus();" (wobei das ausgekellerte Element oder Objekt x eben genau das vorher eingekellerte x sein soll) beschrieben werden.
Daraus lässt sich aber noch nicht ableiten, wie der Keller nun tatsächlich programmiert werden muss. Dafür gibt es nach wie vor verschiedene Möglichkeiten, die auch vor dem Anwender des Kellers versteckt gehalten werden sollen - schließlich soll der Benutzer des Kellers nur über die im Interface festgelegten Methoden auf den Keller zugreifen und sich ebensowenig Gedanken über dessen tatsächliche Realisierung machen müssen, wie oben der Benutzerin einer Datei FAT und Cluster egal waren. Auch dem Benutzer einer Küche ist das technische Innenleben z.B. eines Kühlschranks zu Recht egal: Hauptsache, dass Gerät kühlt, passt in das entsprechende Schrankelement der Einbauküche und lässt sich durch die Tür füllen oder leeren. Das Kühlaggregat ist irgendwo hinten versteckt und für den Kühlschrankbenutzer nicht erreichbar und braucht von ihm auch nicht verstanden zu werden. Wird der Kühlschrank einmal durch ein besseres, energiesparenderes Modell, das vielleicht auch weniger brummt, ersetzt, so soll der neue Kühlschrank in das selbe Loch der Einbauküche passen. Für den Benutzer darf sich nichts ändern: Er wird nach wie vor einfach die Tür aufmachen, um an gekühlte Lebensmittel zu kommen. Der Kühlschrank-Hersteller kann die Funktionalität auf unterschiedliche Weise einbauen - und in die Rolle eines Keller-Herstellers schlüpfen wir jetzt:
zum Seitenanfang / zum Seitenende
Keller - 1. Versuch: mit Reihung
Zunächst soll die vertraute Reihung zum Einsatz kommen - auch wenn deren Größe leider festgelegt werden muss, was eine Obergrenze für die Anzahl der speicherbaren Element
bedeutet. Man könnte das neueste Element immer in die Komponente mit dem Index 0 in der Reihung schreiben (dann wäre zeige ganz einfach: man zeigt immer den Inhalt aus
reihe[0]). Dieses Vorgehen hat aber den Nachteil, dass man bei Einfügen eines weiteren Elements alle anderen Elemente jeweils um eine Position verschieben muss - das dauert
und hat nicht den oben erhofften 1-Schritt-Aufwand. Deshalb ist es besser, die Reihe von links nach rechts zu füllen und sich jeweils zu merken, wie voll sie ist. Eine solche
Möglichkeit wird jetzt gezeigt:
| public class E_Keller implements E_Speicher // 1. Versuch: mit Reihung { // Alle Datenfelder leider nicht privat, damit später auch von der (vom // Keller abgeleiteten) Schlange aus der Zugriff möglich ist! final int MAX = 1000; // Maximale Elementzahl (statisch!) Object[] reihe; // Reihung als eigentliches Speicherelement int nr; // nr ist immer der Index das zuletzt eingefügten Elements, das // beim Keller auch das ist, das zuerst raus muss public E_Keller() { reihe = new Object[MAX]; // neue Reihung wird angelegt nr = -1; // Index -1 bedeutet leer! } public void rein (Object element) { nr = (nr + 1)%MAX; // modulo Max wegen später zu entwickelnder Schlange, reihe[nr] = element; //.. für den Keller reicht noch nr++ } public boolean istLeer() { return (nr == -1); // genau dann true, wenn nr == -1 ist. } public Object zeige() { return (reihe[nr]); } public Object raus() { Object altesElement = reihe[nr]; nr--; return (altesElement); } } |
Alle Methoden haben 1-Schritt-Aufwand (ohne Schleifen!). Man veranschauliche sich mit einem Bleistifttest, wie hier durch Erhöhen oder Erniedrigen von nr vor Eintrag bzw. nach Entfernen eines Elements aus der reihe tatsächlich den Kelleranforderungen entsprochen wird. Außerdem liegt es in der Verantwortung des Benutzers, vor der Verwendung von zeige oder raus den Keller mit istLeer zu prüfen, ob die gewünschten Operationen überhaupt möglich sind. Eine Fehlerkontrolle oder -behandlung wurde deshalb hier nicht vorgesehen.
zum Seitenanfang / zum Seitenende
Keller - Ein erster Praxis-Test
Um den Keller auszutesten, könnte ein kleines Programm nach folgendem Bauplan geschrieben und gestartet werden:
| public class E_KellerTest //Krell, 29.5.2004 -- www.r-krell.de { public void führeAus() { E_Keller keller = new E_Keller(); System.out.println("Ist der neu erzeugte Keller leer? "+ keller.istLeer()); keller.rein ("Das");keller.rein ("ist"); keller.rein ("ein"); keller.rein ("Test"); System.out.println(keller.zeige()); while (! keller.istLeer()) { System.out.println(keller.raus()); } } public static void main (String[] s) { E_KellerTest testObjekt = new E_KellerTest(); testObjekt.führeAus(); } } |
Erwartungsgemäß funktioniert unser Keller und liefert folgende Ausgabe:
zum Seitenanfang / zum Seitenende
Keller - 2. Versuch: mit rekursiven Knoten
Nach außen ist der vorstehende Keller schon voll funktionsfähig, aber die Verwendung der statischen Reihung mit Platz für 1000 Objekte ist noch nicht ganz optimal. Eine
dynamische Struktur mit rekursiven Knoten (hier in Minimalausstattung) kann helfen:
| public class E_Knoten //Krell, 29.5.2004 -- www.r-krell.de { Object inhalt; E_Knoten zeiger; // rekursive Definition: zeiger enthält gleichartigen Knoten // bzw. einen Verweis auf das vorige Objekt gleichen Typs //natürlich wären private Datenfelder mit Zugriffsmethoden "schöner" } |
Mehrere dieser Knoten können eine Speicherstruktur bilden (aus anderen Programmiersprachen als Zeigerstruktur bekannt), die man sich am besten grafisch veranschaulicht:
Damit ergibt sich dann folgender Programmtext für die zweite, bessere (weil dynamische) Keller-Implementation:
| public class E_Keller implements E_Speicher //Krell, 29.5.2004 -- www.r-krell.de { E_Knoten kopf; // Verankerung der Struktur. Nicht privat, damit vererbbar public E_Keller () { kopf = null; } public boolean istLeer() { return (kopf == null); } public Object zeige() { return (kopf.inhalt); } public Object raus() { Object altesElement = kopf.inhalt; kopf = kopf.zeiger; return (altesElement); } public void rein (Object neuesElement) { E_Knoten neu = new E_Knoten(); // mit einem passenden Konstruktor in E_Knoten neu.inhalt = neuesElement; // ließen sich diese Zeilen natürlich neu.zeiger = kopf; // eleganter zusammenfassen kopf = neu; } } |
Natürlich verläuft auch hier der Praxis-Test ebenso erfolgreich wie oben beschrieben - für den Benutzer (hier ein Objekt von KellerTest) ändert sich beim Austausch der Keller nichts (so, wie sich für den Küchenbenutzer der Kühlschrank-Austausch nicht weiter bemerkbar macht).
zum Seitenanfang / zum Seitenende
2. linearer abstrakter Datentyp: Schlange
Obwohl es viele schöne Anwendungen für Keller gibt, so trifft man - z.B. in der Warteschlange vor der Supermarktkasse - auch auf Situationen, wo besser das Element zuerst raus kommt, das als Erstes gespeichert wurde (bzw. die Person dran kommt, die schon am längsten in der Schlange steht). Hier immer den zuletzt Gekommenen zuerst abzufertigen, würde sicher für einigen Unmut sorgen. rein und raus sollen also auf die verschiedenen Enden der linearen Struktur wirken. Weiterhin soll es keinen Zugriff auf Elemente mitten in der Schlange geben; Vordrängeln o.ä. ist strikt verboten. Eine passende Struktur heißt FIFO-Speicher (FIFO = first in - first out), Queue oder eben Schlange.
Gegenüber dem Keller muss nur eine der beiden Operationen, rein oder raus, so geändert werden, dass sie jetzt auf das andere Ende der Liste verketteter Knoten wirkt. Da - wie oben erläutert - für raus die Pfeil-/Verkettungsrichtung wichtiger ist, ist es leichter, rein auf das andere Ende wirken zu lassen, das damit zum hinteren Ende der Schlange wird (wo man sich anstellen muss und so in die Schlange rein kommt: „Hinten anstellen, bitte!"). Um dieses hintere Ende immer rasch erreichen zu können (ohne jeweils die ganze Speicherkette vom Kopf bis ganz hinten durchgehen zu müssen), bietet sich ein weiteres klassenglobales Datenfeld schwanz an, das den letzten Knoten aufnimmt (sprich: auf den letzten [=jüngsten] Knoten zeigt). kopf zeigt weiterhin auf das vordere Ende, wo man an der Kasse dran kommt und dann mit dem bezahlten Einkauf die Schlange verlassen kann.
Da nur schwanz dazu kommt und nur die Methode rein verändert werden muss, bietet sich die Klassen-Vererbung an - hier gezeigt an der dynamischen Implementation mit Knoten:
Die Schlange erbt alles vom Keller (in der 2. Version), fügt den schwanz dazu und überschreibt das bisherige rein mit einer eigenen, gleichnamigen aber inhaltlich abgewandelten
Methode (für das hintere Ende)
| public class E_Schlange extends E_Keller // erweitert den Keller zur Schlange (dynamische Implementation mit Knoten) -- Krell, 29.5.04 { E_Knoten schwanz; // kopf existiert schon im und durch den Keller public E_Schlange () { super(); // Keller-Konstruktor aufrufen schwanz = null; // zusätzlich } public void rein (Object neuesElement) // wirkt jetzt am Ende { E_Knoten neu = new E_Knoten (); neu.inhalt = neuesElement; neu.zeiger = null; // letztes Element immer ohne Nachfolger if (istLeer()) { kopf = neu; //bisher 1. Element: auch kopf muss auf den neuen Knoten zeigen } else { schwanz.zeiger = neu; //sonst: Vorgänger muss auf den neuen Knoten zeigen } schwanz = neu; //immer zeigt auch der Schwanz auf den letzten Knoten } } |
Zum Test kann der oben (rosa unterlegte) KellerTest so abgeändert werden, dass überall Keller durch Schlange ersetzt wird. Die Ausgabe sollte sich natürlich ändern, nämlich wie?
Leider kann das Testprogramm nicht einfach auf E_Speicher abgeändert werden, und damit gleichermaßen und unverändert für Keller und Schlange verwendbar sein. Zwar stehen alle auftretenden Methoden schon in E_Speicher, aber noch ohne Inhalt. Und von einem Interface kann - anders als von einer Klasse - kein neues Objekt etwa mit E_Speicher allgemein = new E_Speicher(); erzeugt werden. Außerdem wüsste das TestObjekt dann auch nicht, welche der beiden rein-Methoden es verwenden muss, die vom Keller oder die vom Speicher („Polymorphie") (bzw. gar keine, weil in E_Speicher ja noch gar kein Rumpf angegeben ist). Da Java die späte Bindung erlaubt, ist trotzdem eine Verallgemeinerung möglich, sofern man beim Aufruf von führeAus durch Übergabe eines geeigneten Parameters wie 'k' oder 's' dafür sorgt, dass der noch als allgemeines E_Speicher-Objekt definierte speicher zumindest beim Erzeugen ein konkretes Objekt einer der beiden richtigen Klassen wird. Die Erzeugung kann auch außerhalb von führeAus erfolgen, sofern E_Speicher speicher; auch außerhalb als globales Datenfeld definiert wurde. Java, das beim Compilieren des Programms noch nicht weiß, mit welchem Parameter führeAus aufgerufen wird, arbeitet trotzdem beim Aufruf zur Laufzeit mit der passenden Methode entweder für den Keller oder die Schlange - je nachdem, als was speicher erzeugt wird!
public void führeAus (char wahl) //wahl z.B. aus Kommandozeilenparametern von main { E_Speicher speicher; if (wahl == 'k') { speicher = new E_Keller(); } else { speicher = new E_Schlange(); } System.out.println ("Ist der neu erzeugte Speicher leer? "+ speicher.istLeer()); speicher.rein ("Das"); speicher.rein ("ist"); speicher.rein ("ein"); speicher.rein ("Test"); System.out.println (speicher.zeige()); while (! speicher.istLeer()) { System.out.println (speicher.raus()); } } |
Eine andere, interaktive Möglichkeit zum Testen von Keller und Schlange gibt's mit einem Java-Applet auf einer Sonderseite:
Interaktiver Test von Keller und Schlange mit einem Java-Applet
zum Seitenanfang / zum Seitenende
Referat über Keller und Schlangen
Ursprünglich für eine Lehrerfortbildungsveranstaltung geschrieben, habe ich das oben skizzierte Konzept von Keller und Schlange nochmal ausführlicher notiert. Und als Folge der an meinen Vortrag anschließenden Diskussion habe ich noch zwei alternative Varianten ausprobiert und dargestellt, nämlich Keller und Schlange als gleichberechtigte Erben von einer gemeinsamen abstrakten Oberklasse sowie die - erst ab der Java-Version (1.)5 mögliche - Typisierung so genannter generischer Keller und Schlangen. Entweder als pdf-Datei zum Online-Lesen in neuem Fenster
Referat Keller-und-Schlange.pdf (39 Seiten, 560 kB)
oder - gemeinsam mit den Quelltexten der vorgestellten Java-Programme - zum Download in einer Archiv-Datei: keller-und-schlange.zip (335 kB).
zum Seitenanfang / zum Seitenende
Wegsuche im Labyrinth
- eine nichttrivale Verwendung von Keller oder Schlange bei der Tiefen- bzw.
Breitensuche
Das oben vorgestellte Testprogramm, egal ob konkret oder mit später Bindung, ist recht einfach und macht die
Notwendigkeit eines Kellers oder eine Schlange nicht sehr deutlich. Dazu bedarf es anderer, zum Teil schon
angedeuteter Beispiele aus dem Alltag. Die Vorteile abstrakter Datentypen wie Keller oder Schlange werden
natürlich nur augenfällig, wenn sich die gleichen Strukturen in einer Vielzahl verschiedener Anwendungen
unverändert verwenden lassen. Hier sind der Unterricht und auch die Fantasie der Schülerinnen und Schüler
gefordert.
Aus der Fülle möglicher Anwendungen sei hier die Wegsuche in einem Labyrinth heraus gegriffen. In einem zufällig erzeugten Labyrinth soll ein Weg von S (Start) nach Z (Ziel) gefunden werden. Da S und Z auch von freien Feldern umgeben sein können, versagen Verfahren wie „immer mit der rechten Hand an der Wand entlang". Nach längerer Überlegung, für die man im Unterricht aus ausreichend Zeit einräumen muss, kann möglicherweise folgendes Verfahren entwickelt werden:
zum Seitenanfang / zum Seitenende
Tiefensuche (mit Keller)
Vom dem Kästchen oder Punkt, auf dem man sich gerade befindet (anfangs also dem Startpunkt S), sucht man - am besten nach einem festen Schema, in dem man z.B. der Reihe
nach den östlichen, nördlichen, westlichen und schließlich südlichen Nachbarn ausprobiert - einen freien, bisher noch unbesuchten Nachbarn. Dort geht man hin, speichert die
Koordinaten vorsorglich im Keller, und verfährt von dort aus ebenso, d.h. sucht wieder einen freien Nachbarn, um dorthin weiter zu gehen, usw. Erreicht man auf diese Weise das
Ziel, ist alles bestens. Gerät man in eine Sackgasse (erkennbar daran, dass es keinen freien unbesuchten Nachbarn mehr gibt), so zieht man sich Schritt für Schritt aus der Sackgasse
zurück und probiert es vom jeweiligen Vorgängerpunkt (den man zum Glück im Keller findet) mit einem anderen, hoffentlich besseren unbesuchten Nachbarn.
zum Seitenanfang / zum Seitenende
Breitensuche (mit Schlange)
Die Tiefensuche findet nicht immer den schnellsten Weg. Das motiviert zur Suche nach besseren Suchmethoden. Vermutlich nur mit Hilfe lässt sich folgende Strategie entwickeln, die sich außerhalb des Computers nur für riesige Pfadfinder-Gruppen eignet: Die ganze Gruppe startet beim Startpunkt S. Bei diesem und bei jedem folgenden Punkt wird immer nach dem gleichen Verfahren vorgegangen: gibt es mehrere unbesuchte Nachbarn, teilt sich die Gruppe und jeder Nachbar wird von einem Teil der Pfadfinder besucht (dafür müssen immer noch genügend Gruppenmitglieder zur Verfügung stehen). Erreicht endlich irgendein Pfadfinder das Ziel, ruft er ganz laut und die Suche stoppt. Vom Rufer (am Ziel) lässt sich jetzt der Weg zum Startpunkt zurück verfolgen und ausgeben. Die Grafik zeigt, dass natürlich abseits des Weges auch noch viele Sucher unterwegs waren (alle vom Start aus betretenen Punkte wurden mit a, alle von einem a-Punkt aus erreichten Punkte wurden mit b bezeichnet usw.). Es gibt aber keine kürzeren Wege (= mit weniger Zwischenpunkten) als den gefundenen!
Interaktiver Test der Wegsuchen im Labyrinth (mit Java-Applet)
zum Seitenanfang / zum Seitenende
3. linearer abstrakter Datentyp: Liste
Für viele Anwendungen ist es doch eine starke Einschränkung, wenn man nur an die Datensätze am Ende des Speichers heran kommt. Sicher könnte man Keller oder Schlange vorübergehend teilweise in einen Zwischenspeicher (am liebsten natürlich wieder in einen linearen ADT) entleeren, bis man das gesuchte Element oder eine passende Einfügestelle gefunden hat. Aber dann muss wieder viel kopiert werden, steigt der Aufwand und ein Zugriff ist nicht mehr unabhängig von der Anzahl der gespeicherten Elemente in einem Schritt zu realisieren. Also wird nun ein Datenspeicher gesucht, der zwar auch wieder linear organisiert und dynamisch ist, aber wo man trotzdem an jeder beliebigen Stelle in (oder vor oder hinter) der Kette der vorhandenen Elemente mit rein ein neues Element einfügen kann, oder wo man sich jedes beliebige Element mit zeige ansehen oder es mit raus löschen kann (sofern die Liste nicht leer ist). Neben den ganz oben im Interface E_Speicher schon festgelegten Methoden muss es also noch weitere Methoden zur Auswahl der richtigen Stelle oder des richtigen Elements geben.
Bei der einfachen Liste lehnt man sich dabei an die Möglichkeiten der Dateien an (vgl. meine Java-Seite d) bzw. den Tonband-Vergleich oben im ersten Abschnitt „Abstrakter Datentyp (ADT) - Motivation und Anforderungen" auf dieser Seite e)): Man kann (mit anDenAnfang) den Datenspeicher sozusagen an den Beginn zurück spulen und/oder mit weiter immer von einem Titel bzw. gespeicherten Element zum nächsten gehen - aber nur nach hinten in Richtung auf das Dateiende zu. Es ist nicht möglich, Datensätze in dieser Richtung zu überspringen oder sich umgekehrt um einen Datensatz nach vorne zu bewegen. Die einzige Möglichkeit, nach vorne zu kommen, besteht in der Verwendung von anDenAnfang, was aber immer direkt nach ganz vorne führt. Mit diesen beiden Methoden, anDenAnfang und weiter, kann man trotzdem jeden Datensatz der Liste auswählen und ihn dadurch zum aktuellen Datensatz erklären. zeige und raus zeigen dann das aktuell ausgewählte Element oder löschen es dabei noch aus dem Speicher.
rein könnte wahlweise das aktuelle Element ersetzen (was nicht so schön wäre, wenn man ein neues Element nur aufnehmen kann, wenn man dabei ein altes löscht. So bekommt
man eine Liste nie wirklich voll!) oder rein könnte vor oder hinter dem aktuellen Element das neue Element einfügen. Hält man sich vor Augen, dass man später die einfache Liste
vielleicht mal zu einer sortierten Liste erweitern will - also z.B. einen neuen Schüler an die passende Stelle in eine nach Nachnamen alphabetisch sortierte Klassenliste aufnehmen
will - so hat das Einfügen vor dem aktuellen Element unschätzbare Vorzüge: Um die richtige Stelle z.B. für „Müller" zu finden, muss man mit anDenAnfang ganz vorne, etwa bei
„Altenbach" anfangen. Wenn man dann mit weiter und zeige „Begisholli" liest, weiß man noch nicht, ob man „Müller" einfügen kann. Vielleicht kommen noch „Krell" und
„Lehmann". Man muss also weiter und weiter gehen. Erst wenn man nach „Meier" endlich auf „Ngyen" trifft, weiß man, dass man dazwischen „Müller" einfügen muss(te).
Inzwischen ist aber schon „Ngyen" aktuell (sonst hätte man den Namen nicht mit zeige lesen können). Ein zurück zu „Meier" ist nicht mehr möglich - in der Liste gib's kein
Zurück, s.o.! Nach „Meier" kann also nicht mehr eingefügt werden. Wird aber mir rein vorm aktuellen Element eingefügt, dann stört es nicht, dass „Ngyen" schon aktuell ist -
„Müller" kommt dann nämlich genau an die richtige Stelle!
Damit man dann aber auch noch einen Namen wie „Zafiris"ganz hinten an die Liste anfügen kann, muss man aktuell praktisch noch hinter das letzte Element setzen können. Diese
Positionierung des Auswahlzeigers soll dann durch das Ergebnis true der Kontrollmethode istAmEnde (besser wäre eigentlich istHintermEnde) überprüfbar werden, weil man dort
kein aktuelles Element mehr zeigen oder raus nehmen kann.
Solche Überlegungen machen übrigens einen wichtigen Teil der Informatik aus und sind völlig unabhängig von der verwendeten Programmiersprache. Durchdachte Entwürfe zeichnen die Meisterin oder den Meister des Faches aus. Schlechte Entwürfe und Konzeptionen führen auch bei noch so raschem Tippen und selbst bei zusätzlicher Verwendung von fünf selten genutzten Befehlen aus peppigen Bibliotheken nicht mehr zu guten Implementationen.
Aber zurück zur Liste: Diese soll hier wieder mit einer Kette aus rekursiven Knoten realisiert werden, wobei wieder jeder Knoten genau ein Element beliebigen (Objekt-)Typs als
Inhalt aufnehmen soll (ähnlich wie oben die grün unterlegte Kette beim 2. Keller). Die Knoten sind also wieder Objekte von der schon angegebenen Klasse E_Knoten. Fügt man in
eine solche Kette ein Element ein, muss man - obwohl das Element rechts neben der Einfügestelle das aktuelle ist - trotzdem nur den zeiger des Knotens links davor ändern,
nämlich auf den neuen Knoten richten (mit dem neuen Element als Inhalt). Hat man also nur einen Hilfszeiger auf den aktuellen Knoten, kommt man an den linken Knoten (gegen
die Pfeilrichtung der Verkettung) nicht dran - es sei denn, durch mühsames Durchgehen der ganzen Kette wieder von ganz vorne. Also ist es besser, einen Hilfszeiger voraktuell
auf das Knoten links vom aktuellen zu setzen, weil man dort bei rein, aber auch bei raus, arbeiten muss, in dem man dort den zeiger verbiegt. Da man für zeige bequem vom
voraktuellen Knoten in einem Schritt nach rechts zum aktuellen Knoten mit dem gesuchten Inhalt kommt, ist ein Hilfszeiger auf den aktuellen Knoten gar nicht nötig. Das erleichtert
dann das Aktuellmachen hinter dem letzten Element, weil man keinen Zeiger ins Leere setzen muss, sondern einfach den letzten Knoten mit voraktuell referenziert.
Andererseits entstehen jetzt Probleme, wenn man den ersten Knoten ganz links aktuell machen will (nämlich mit anDenAnfang): voraktuell müsste noch links davon irgendwo hin
zeigen. Dann kann man aber nicht mit voraktuell.zeiger zum ersten Knoten gelangen (wenn es den Knoten voraktuell nicht gibt, kann er auch keinen zeiger haben).
Entweder sind aufwändige Fallunterscheidung mit vielen if-Anweisungen in den Methoden nötig, oder man klebt einfach links an die Liste noch einen zusätzlichen Knoten vor den
Knoten mit dem ersten Element davor. Der Inhalt dieses zusätzlichen Knotens ist egal, wir brauchen nur seinen zeiger. Man spricht daher von einem dummy-Knoten (oder
ungenauer auch von einem dummy-Element) wegen dummy = leer, taub.
| public class E_Liste //Krell, 29.5.2004 -- www.r-krell.de { E_Knoten dummy, voraktuell; public E_Liste() //Konstruktor { dummy=new E_Knoten(); dummy.zeiger=null; voraktuell=dummy; } public void anDenAnfang() //erstes echtes Element wird aktuell { voraktuell=dummy; } public void rein(Object neuerInhalt) { //Es wird vor dem aktuellem Element E_Knoten neu=new E_Knoten(); //das neue eingefügt neu.inhalt=neuerInhalt; neu.zeiger=voraktuell.zeiger; voraktuell.zeiger=neu; weiter(); //das bisherige aktuelle Element bleibt aktuell } public Object zeige() //zeigt aktuelles Element { return (voraktuell.zeiger.inhalt); } public void weiter() //macht Nachfolger des aktuellen Elements aktuell { voraktuell=voraktuell.zeiger; } public boolean istAmEnde() //Abfrage, ob aktuell schon hinter der Liste steht. { //Wenn true, kein zeige oder raus mehr möglich, ... return (voraktuell.zeiger==null); //.. aber noch rein, um ein neues Element } //ganz hinten anzufügen! public Object raus() //nimmt das aktuelle Element heraus { //Nachfolger des entfernten Elements wird aktuell Object hilf=voraktuell.zeiger.inhalt; voraktuell.zeiger=voraktuell.zeiger.zeiger; return(hilf); } public boolean istLeer() //Abfrage ob Liste leer ist, d.h. außer { //dem Dummy-El. gar keine Elemente enthält return(dummy.zeiger==null); } } |
zum Seitenanfang / zum Seitenende
Implementation der ADTs in Java
Die hier vorgestellten linearen abstrakten Datentypen 1 bis 3 (Keller bis Liste) sind natürlich so universell verwendbar und auch in ähnlicher Weise in vielen Informatikbüchern beschrieben, dass vergleichbare Implementationen auch mit der Java-JDK bzw. -SDK als Bibliotheksklassen mitgeliefert werden, nämlich u.a. Stack, Vector, ArrayList und LinkedList.
Eine Übersicht über dort verwendete Namen und Methoden und ihren exemplarischen Gebrauch zeigt mein kommentiertes Testprogramm auf einer Sonderseite (allerdings noch ohne die neuen Datenstrukturen, die mit Java 5 mitgeliefert werden):
Demonstration mit Java mitgelieferter linearer abstrakter Datentypen
zum Seitenanfang / zum Seitenende
4. linearer abstrakter Datentyp: Sortierte Liste
Neben der normalen Liste interessieren oft auch geordnete Listen, in denen die Element in einer (einmal ausgewählten) festen Ordnung stehen. Damit man in einer solchen sortierten Liste nicht ordnungsschädigend herumpfuschen kann, wird sie hier nicht als vererbte Erweiterung einer normalen Liste implementiert (weil dann weiter und rein zur Verfügung stünden, und damit auch an falscher Stelle eingefügt werden kann). Vielmehr wird die normale Liste vor dem Anwender versteckt und der Zugriff nur noch über neue Methoden wie sortRein oder löscheGesucht ermöglicht.
Damit aber überhaupt eine Anordnung der Objekte möglich ist, muss eine Ordnungsrelation definiert werden. Dies geschieht hier mit der Methode vergleicheMit. Ein konkretes Beispiel für vergleicheMit befindet sich bereits am Ende meiner Java-Seite d).
| public interface E_ObjektMitOrdnung // Krell, 29.5.2004 -- www.r-krell.de { public double vergleicheMit (Object anderes, char sortKrit); // Hiermit wird -- ähnlich wie durch compareTo für Strings -- die Reihenfolge // zweier Objekte festgelegt. Anders als bei der vordef. Java-Methode bzw. Com- // parable kann noch ein Sortierkriterieum gewählt werden. Speichert man z.B. // Schüler mit Namen, Vornamen, Zeugnisnote und Alter, so soll mit dem zu über- // gebenden Buchstaben ausgesucht werden, welches Datenfeld der Sortierschlüssel // ist. Bei sortKrit='v' könnte z.B. alphabet. nach Vornamen sortiert werden, // während bei 'z' Schüler nach ihren Zeugnisnoten verglichen/geordnet werden. // Details müssen natürlich bei den konkreten Klassen formuliert werden, die // dieses Interface implementieren. // a.vergleicheMit(b, sortKrit) < 0 bedeutet a<b; ==0 <=> a=b; >0 <=> a>b // bezüglich des gewählten Sortierkriteriums. } |
Damit gelingt dann die Implementation einer sortierten Liste für Objekte, die das Interface E_ObjektMitOrdnung implementieren, etwa nach folgendem Muster:
| // Sortierte Liste -- Krell, 29.5.04 (www.r-krell.de) // Die sortierte Liste erwartet von den Elementen nur die im Interface E_ObjektMitOrdnung // festgelegte Methode. Andere Eigenschaften oder Fähigkeiten werden nicht verlangt. // Insofern ist diese Liste fast so allgemein wie die einfache Liste für beliebige // Objekte, nur dass statt Object jetzt E_ObjektMitOrdnung als Elementtyp verlangt wird. // Die tatsächliche Speicherung der Elemente geschieht in einer normalen einfachen Liste, // wobei die richtigen Stellen mit den dort vorhandenen Methoden wie anDenAnfang, weiter,.. // usw. gesucht bzw. gefunden werden. public class E_SortListe { E_Liste normaleListe; char sortKrit; public E_SortListe (char sortierKriterium) // Konstruktor: { // erzeugt normale Liste als Speicher normaleListe = new E_Liste(); // und legt einmalig das Sortierkriterium fest sortKrit = sortierKriterium; } public void sortRein (E_ObjektMitOrdnung neuerInhalt) //neues Element an der richtigen Stelle { // einfügen. "richtig" = entsprechend dem beim normaleListe.anDenAnfang(); // Erzeugen der Liste angegeben Kriterium while(!normaleListe.istAmEnde() && ((E_ObjektMitOrdnung)normaleListe.zeige()).vergleicheMit(neuerInhalt, sortKrit)<0) { normaleListe.weiter(); } normaleListe.rein(neuerInhalt); } public E_ObjektMitOrdnung zeigeGesucht (E_ObjektMitOrdnung gesucht) { //(erstes) Element finden und zurückgeben, das normaleListe.anDenAnfang(); // mit gesucht bezüglich des Sortierkriteriums while(!normaleListe.istAmEnde() // übereinstimmt && ((E_ObjektMitOrdnung)normaleListe.zeige()).vergleicheMit(gesucht, sortKrit)<0) { normaleListe.weiter(); } if (!normaleListe.istAmEnde() && ((E_ObjektMitOrdnung)normaleListe.zeige()).vergleicheMit(gesucht, sortKrit)==0) { return ((E_ObjektMitOrdnung)normaleListe.zeige()); } else { return (null); // gesuchtes Element nicht gefunden } } public E_ObjektMitOrdnung löscheGesucht (E_ObjektMitOrdnung gesucht) { //(erstes) Element zurückgeben und löschen, das normaleListe.anDenAnfang(); // mit gesucht bzgl. des Sortierkriteriums while(!normaleListe.istAmEnde() // übereinstimmt && ((E_ObjektMitOrdnung)normaleListe.zeige()).vergleicheMit(gesucht, sortKrit)<0) { normaleListe.weiter(); } if (!normaleListe.istAmEnde() && ((E_ObjektMitOrdnung)normaleListe.zeige()).vergleicheMit(gesucht, sortKrit)==0) { return ((E_ObjektMitOrdnung)normaleListe.raus()); } else { return (null); // gesuchtes Element war gar nicht vorhanden } } } |
Auch der Umgang mit der sortierten Liste kann auf einer Sonderseite probiert werden:
Interaktiver Test der sortierten Liste (mit Java-Applet)
Betrachtet man oben die Methode zeigeGesucht, so ist ihr Aufwand leider linear von der Anzahl der Elemente in der Liste abhängig. Bei der Suche in sortierten Reihungen waren hingegen mit dem Halbierungsverfahren schon ein Algorithmus verwendet worden, der viel rascher, nämlich schon nach ~ log2(Elementzahl) Schritten zum Ziel fand. Über eine Verbesserung der Suche sollte also noch nachgedacht werden -- eine Möglichkeit zeigt meine nächste Seite, „Informatik mit Java", Teil f)!
zurück zur Informatik-Hauptseite
(Die anderen Java-Seiten werden entweder mit dem Menü hier am Seitenanfang oder
am besten auch auf der Informatik-Hauptseite ausgewählt)