/* Listenimplementierung nach dem Konzept von Balzert, Abschnitt 3.7.1. Weitere Konzepte sind aus Aho, Hopcroft, Ullman, Abschnitt 2.1 entnommen. Unsere Darstellung hier ist NICHT objekt-orientiert. Die Algorithmen könnten also in analoger Form in C oder PASCAL usw. implementiert werden. Ein weiteres Beispiel wird später die Objekt-orientierte Umsetzung des Listen-ADTs illustrieren. LISTEN ALS ABSTRAKTE DATENTYPEN: Aus mathematischer Sicht sind Listen über einem Datentyp MyDataType endliche Folgen von Elementen aus der Menge MyDataType. Zur Erinnerung: Eine Folge f der Länge n über dem Datentyp MyDataType ist eine Funktion f : { 1,...,n } -> MyDataType Anstelle der Funktionsnotation wird - da der Definitionsbereich immer der Abschnitt 1.."Länge der Folge" der natürlichen Zahlen ist - häufig die Aufzählung der Bildwerte unter f gewählt: Ist f(1) = y1, ... , f(n) = yn, notieren wir die Folge f durch f = < y1, ... , yn > Mit <> bezeichnen wir die leere Folge, d.h. die Funktion mit leerem Definitionsbereich. Mit LIST = MyDataType* (hochgestellter *) wird die Menge aller endlichen Folgen über dem Datentyp T bezeichnet. Mit l1^l2 wird die Konkatenation der Listen l1 und l2 bezeichnet: ^ = Bei einer nicht leeren Liste l bezeichnet head(l) das erste Element: head() = y1 Bei einer nicht leeren Liste l bezeichnet tail(l) die List, welche aus l durch Entfernen des ersten Elementes entsteht: tail() = < y2, ... , yn > Offenbar gilt für nicht leere Listen l l = ^ tail(l) Die Menge aller in der Liste l enthaltenen Elemente (also das Bild unter der Funktion l) bezeichnen wir mit ran(l) ("Range of function l"): ran() = { a,b,c,d,e } Ist Liste l1 identisch mit einem Anfangsstück von Liste l2, sagen wir "l1 ist ein Präfix von l2" und schreiben l1 <= l2: <= Für den Abstrakten Datentyp LISTE ist es praktisch, eine Zusammensetzung einer jeden Liste aus zwei Teilen zu definieren: l = part1(l) ^ part2(l) damit lassen sich sequenzielle Leseoperationen, Einfügen vor einem bestimmten Element und Löschen eines bestimmten Elementes elegant spezifizieren: head(part2(l)) ist immer das "gerade betrachtete Element der Liste l". Damit wird jede endliche Folge aus LISTE also nicht durch die eigentliche Liste l allein, sondern durch das Tripel (l, part1(l), part2(l)) mit der invarianten Bedingung l = part1(l) ^ part2(l) repräsentiert. Den Kopf von part2(l) bezeichnen wir als die "aktuelle Listenposition": Ein im aktuellen Zustand der Liste ausgeführte Leseoperation gibt head(part2(l)) zurück, eine Löschoperation entfernt genau head(part2(l)) aus der Liste, ein Einfügeoperation fügt genau vor head(part2(l)) in die Liste ein. Wir können jetzt auf abstrakter Ebene die auf dem ADT sinnvollen Operationen völlig unabhängig von der konkreten Implementierung (die kommt weiter unten) definieren: (1) Erzeugen einer neuen leeren Liste: // PRE: true MyDataType* lstInit() // POST: lstInit() = <> and lstInit() = part1(lstInit())^part2(lstInit()) (2) Anhängen eines Datenobjektes von Typ MyDataType an die existierende Liste l: //PRE: l in MyDataType* and l = part1(l)^part2(l) void lstAppend(MyDataType x, LIST l) //POST: l = part1(l)^part2(l) and part1(l) = (part1(l)@PRE) // and part2(l) = (part2(l)@PRE)^ AND x = x@PRE (3) Einfügen eines Datenobjektes von Typ MyDataType vor der aktuellen Position der Liste l, d.h. VOR head(part2(l)): //PRE: l in MyDataType* and l = part1(l)^part2(l) void lstInsert(MyDataType x, LIST l) //POST: l = part1(l)^part2(l) // and part1(l) = (part1(l)@PRE) ^ // and part2(l) = part2(l)@PRE AND x = x@PRE (4) Löschen des Elementes an der aktuellen Position der Liste: //PRE: l in MyDataType* and l = part1(l)^part2(l) public static void lstDelete(LIST l) //POST: l = part1(l)^part2(l) // and part1(l) = part1(l)@PRE // and ( part2(l)@PRE = <> => part2(l) = part2(l)@PRE ) // and ( part2(l)@PRE != <> => part2(l) = tail(part2(l)@PRE) ) (5) Abfrage auf leere Liste: //PRE: l in MyDataType* and l = part1(l)^part2(l) boolean lstIsEmpty(LIST l) //POST: (lstIsEmpty(l) <=> l = <>) // and l = part1(l)^part2(l) // and part1(l) = part1(l)@PRE and part2(l) = part2(l)@PRE (6) Rücksetzen der aktuellen Position auf den Listenanfang: //PRE: l in MyDataType* and l = part1(l)^part2(l) void lstRewind(LIST l) //POST: l = part1(l)^part2(l) and l = l@PRE and part1(l) = <> (7) Lesen des an der aktuellen Position befindlichen Elementes - Weiterrücken der aktuellen Position um einen Platz Richtung Listenende: //PRE: l in MyDataType* and l = part1(l)^part2(l) MyDataType lstNext(LIST l) //POST: l = part1(l)^part2(l) // and l = l@PRE // and ( not (part2(l)@PRE = <>) // => lstNext(l) = head(part2(l)@PRE) // and part2(l) = tail(part2(l)@PRE) // and ((part2(l)@PRE = <>) => part1(l) = (part1(l)@PRE) ) (8) Suchen des ersten Datenobjektes ab (und einschliesslich) aktueller Listenposition, welches den Schlüsselwert k besitzt. Die aktuelle Listenposition wird im Erfolgsfall auf den gefundenen Datensatz gestezt, andernfall, andernfalls auf das Listenende. //PRE: l in MyDataType* and l = part1(l)^part2(l) //PRE: l in MyDataType* and l = part1(l)^part2(l) MyDataType lstSearchNextKey(int k, LIST l) //POST: l = part1(l)^part2(l) // and l = l@PRE // and ( lstSearchNextKey(k,l) = null // => part2(l) = <> and (forall x in ran(part2(l)@PRE) . x.key != k) ) // and ( lstSearchNextKey(k,l) != null // => (lstSearchNextKey(k,l) = head(part2(l)) // and head(part2(l)).key = k // and (exists l1 in MyDataType* . l1^part2(l) = part2(l)@PRE // and (forall x in ran(l1) . x.key != k))) ) // IMPLEMENTIERUNG DES LISTEN ADTs: In Java gehören Klassen zu den Referenz-Typen der Programmiersprache. Die Klasse MyDataType (siehe unten) modelliert die Nutzdaten, die mit Hilfe des Listenpaketes verwaltet werden sollen: Ein Datenobjekt vom Typ MyDataType besteht aus dem Tripel (key,name,salary). In einer oder mehreren Listen sollen (bis auf Speichergrenzen) unbeschränkt viele Datensätze dieses Types verwaltet werden können. Die Verwaltung geschieht mittels der oben eingeführten Operationen des ADTs. Die Klasse Link (siehe unten) modelliert einen Listenelement bestehend aus den eigentlichen Nutzdaten vom Typ MyData (Bezeichnung 'data') PLUS dem Verweis auf das Nachfolgerelement. Da 'data' vom Typ MyData ist, modellieren wir also mit class Link die Elemente von FOLGEN UEBER MyDataType-Objekten. Für Folgen über einem anderen Datentyp T würden wir statt 'MyDataType data' einfach 'T data' schreiben. Das Konzept der Verzeigerung mittels 'Link next' würde sich nicht ändern. */ // Datentyp der Nutzdaten class MyDataType { int key; String name; int salary; MyDataType(int k, String n, int s) { key = k; name = n; salary = s; } } // Datentyp der Listenelemente class Link { // Der Nutzdateninhalt des Listenelements: MyDataType data; // Rekursiver Verweis auf ein Element vom // Typ class Link, d.h. Verweis // auf das nächste Folgenelement Link next; } // Datentyp der Listen; jede Liste besteht aus einem oder mehreren Elementen // vom Typ Link. Jede Liste ist durch genau ein Objekt vom Typ LIST identifiziert. // In den Komponenten first,last,predecessorActualPtr steht die - von unserer // speziellen Implementierung abhängige - Verwaltungsinformation, die wir // zur Realisierung der ADT-Operationen brauchen: // Wir führen zwei Hilfslistenelemente 'first' und 'last' ein, die immer // existieren und den Listenkopf und das Listenende repräsentieren, // ohne selber Nutzdaten zu enthalten. Die leere Sequenz '<>' wird // dadurch repräsentiert, dass die sie implementierende Liste // ausser den auf sich gegenseitig // verweisenden Listenelementen 'first' und 'last' keine weiteren enthält. // // Die nicht-leere Sequenz wird in Java // durch (n+2) Variablen v0,v1,...,v_(n+1) vom Typ Link implementiert, // so dass v0 == first und first.next == v1 // v1.data == i1 und v1.next == v2 // v2.data == i2 und v2.next == v3 // ... // v_n.data == i_n und v_n.next == last // v_(n+1) == last und last.next == v_n // Die Nachfolger-Referenz des Hilfselementes 'last' zeigt also // bei nicht-leerer Sequenz immer auf das letzte definierte Element // der Sequenz. class LIST { Link first; Link last; Link predecessorActualPtr; LIST() { first = new Link(); last = new Link(); first.next = last; last.next = first; predecessorActualPtr = first; } } public class ListHandler { /*********************************************************************************** * Erzeugen einer neuen leeren Liste, identifiziert durch einen * LIST HANDLE. Der Liste Handle l = lstInit() repräsentiert von jetzt ab die * abstrakte Liste l. ***********************************************************************************/ // PRE: true public static LIST lstInit() { return new LIST(); } // POST: lstInit() = <> and lstInit() = part1(lstInit())^part2(lstInit()) /*********************************************************************************** * Anhängen eines Datenobjektes von Typ MyDataType an die existierende * Liste l. ***********************************************************************************/ //PRE: l in MyDataType* and l = part1(l)^part2(l) public static void lstAppend(MyDataType x, LIST l) { Link newElement = new Link(); newElement.data = x; newElement.next = l.last; l.last.next.next = newElement; l.last.next = newElement; } //POST: l = part1(l)^part2(l) and part1(l) = (part1(l)@PRE) // and part2(l) = (part2(l)@PRE)^ and x = x@PRE /*********************************************************************************** * Einfügen eines Datenobjektes von Typ MyDataType vor der aktuellen Position * der Liste l, d.h. VOR head(part2(l)) ***********************************************************************************/ //PRE: l in MyDataType* and l = part1(l)^part2(l) public static void lstInsert(MyDataType x, LIST l) { Link newElement = new Link(); newElement.data = x; newElement.next = l.predecessorActualPtr.next; l.predecessorActualPtr.next = newElement; l.predecessorActualPtr = newElement; if (l.predecessorActualPtr.next == l.last) { l.last.next = newElement; } } //POST: l = part1(l)^part2(l) // and part1(l) = (part1(l)@PRE) ^ // and part2(l) = part2(l)@PRE and x =x@PRE /*********************************************************************************** * Löschen des Elementes an der aktuellen Position der Liste ***********************************************************************************/ //PRE: l in MyDataType* and l = part1(l)^part2(l) public static void lstDelete(LIST l) { if ( l.predecessorActualPtr.next != l.last ) { l.predecessorActualPtr.next = l.predecessorActualPtr.next.next; if ( l.predecessorActualPtr.next == l.last ) l.last.next = l.predecessorActualPtr; } } //POST: l = part1(l)^part2(l) // and part1(l) = part1(l)@PRE // and ( part2(l)@PRE = <> => part2(l) = part2(l)@PRE ) // and ( part2(l)@PRE != <> => part2(l) = tail(part2(l)@PRE) ) /*********************************************************************************** * Abfrage auf leere Liste ***********************************************************************************/ //PRE: l in MyDataType* and l = part1(l)^part2(l) public static boolean lstIsEmpty(LIST l) { return ( l.first.next == l.last ); } //POST: (lstIsEmpty(l) <=> l = <>) // and l = part1(l)^part2(l) // and part1(l) = part1(l)@PRE and part2(l) = part2(l)@PRE /*********************************************************************************** * Rücksetzen der aktuellen Position auf den Listenanfang ***********************************************************************************/ //PRE: l in MyDataType* and l = part1(l)^part2(l) public static void lstRewind(LIST l) { l.predecessorActualPtr = l.first; } //POST: l = part1(l)^part2(l) and l = l@PRE and part1(l) = <> /*********************************************************************************** * Lesen des an der aktuellen Position befindlichen Elementes - * Weiterrücken der aktuellen Position um einen Platz Richtung Listenende ***********************************************************************************/ //PRE: l in MyDataType* and l = part1(l)^part2(l) public static MyDataType lstNext(LIST l) { if ( l.predecessorActualPtr.next != l.last ) { l.predecessorActualPtr = l.predecessorActualPtr.next; return l.predecessorActualPtr.data; } return null; } //POST: l = part1(l)^part2(l) // and l = l@PRE // and ( not (part2(l)@PRE = <>) // => lstNext(l) = head(part2(l)@PRE) and part2(l) = tail(part2(l)@PRE) ) // and ( (part2(l)@PRE = <>) => part1(l) = (part1(l)@PRE) ) /*********************************************************************************** * Suchen des ersten Datenobjektes ab (und einschliesslich) aktueller * Listenposition, welches den Schlüsselwert k besitzt. Die aktuelle Listenposition * wird im Erfolgsfall auf den gefundenen Datensatz gesetzt, andernfalls * auf das Listenende. ***********************************************************************************/ //PRE: l in MyDataType* and l = part1(l)^part2(l) //PRE: l in MyDataType* and l = part1(l)^part2(l) public static MyDataType lstSearchNextKey(int k, LIST l) { Link tmpLink = l.predecessorActualPtr.next; while ( tmpLink != l.last ) { if ( tmpLink.data.key == k ) return tmpLink.data; else { l.predecessorActualPtr = l.predecessorActualPtr.next; tmpLink = l.predecessorActualPtr.next; } } return null; } //POST: l = part1(l)^part2(l) // and l = l@PRE // and ( lstSearchNextKey(k,l) = null // => part2(l) = <> and (forall x in ran(part2(l)@PRE) . x.key != k) ) // and ( lstSearchNextKey(k,l) != null // => (lstSearchNextKey(k,l) = head(part2(l)) // and head(part2(l)).key = k // and (exists l1 in MyDataType* . l1^part2(l) = part2(l)@PRE // and (forall x in ran(l1) . x.key != k))) ) // /*********************************************************************************** * Ausgabe des Listenkopfes head(l), die aktuelle Listenposition steht danach * am Kopf von tail(l). ***********************************************************************************/ //PRE: l in MyDataType* and l = part1(l)^part2(l) public static MyDataType lstHead(LIST l) { lstRewind(l); return lstNext(l); } //POST: l = part1(l)^part2(l) // and part1(l) = <> // and l = l@PRE // and ( lstIsEmpty(l) => lstHead(l) = null ) // and ( not lstIsEmpty(l) => lstHead(l) = head(l) /*********************************************************************************** * Suchen des ersten Datenobjektes ab (und einschliesslich) Listenanfang, * welches den Schlüsselwert k besitzt. Die aktuelle Listenposition * wird im Erfolgsfall auf den gefundenen Datensatz gestezt, andernfall, andernfalls * auf das Listenende. ***********************************************************************************/ //PRE: l in MyDataType* and l = part1(l)^part2(l) public static MyDataType lstSearchKey(int k, LIST l) { lstRewind(l); return lstSearchNextKey(k,l); } //POST: l = part1(l)^part2(l) // and l = l@PRE // and ( lstSearchNextKey(k,l) = null // => part2(l) = <> and (forall x in ran(l) . x.key != k) ) // and ( lstSearchNextKey(k,l) != null // => (lstSearchNextKey(k,l) = head(part2(l)) // and head(part2(l)).key = k // and (forall x in ran(part1(l)) . x.key != k)) ) // // // Hilfsfunktionen // static void printAll(LIST l) { MyDataType d; int iCnt = 1; System.out.println("----------------- LISTENAUSGABE START --------------------------"); lstRewind(l); d = lstNext(l); while ( d != null ) { System.out.println(iCnt + " : key = " + d.key + " name = " + d.name + " salary = " + d.salary); iCnt = iCnt + 1; d = lstNext(l); } System.out.println("----------------- LISTENAUSGABE ENDE --------------------------\n\n"); } // // Hauptprogramm // public static void main(String args[]) { MyDataType tmpData; LIST l = lstInit(); System.out.println("Liste l ist " + ((lstIsEmpty(l)) ? "" : " NICHT") + " leer"); System.out.println("1. Element anfügen: (1,name1,1000)"); lstAppend(new MyDataType(1,"name1",1000),l); System.out.println("Liste l ist " + ((lstIsEmpty(l)) ? "" : " NICHT") + " leer"); printAll(l); System.out.println("2. Element anfügen: (3,name3,3000)"); lstAppend(new MyDataType(3,"name3",3000),l); printAll(l); System.out.println("3. Element VOR name3 einfügen: (2,name2,2000)"); lstRewind(l); tmpData = lstHead(l); lstInsert(new MyDataType(2,"name2",2000),l); printAll(l); System.out.println("4. Element am Listenanfang einfügen: (0,name0,0)"); lstRewind(l); lstInsert(new MyDataType(0,"name0",0),l); printAll(l); System.out.println("nach key 2000 suchen und DAVOR Element einfügen: (5,name5,5000)"); tmpData = lstSearchKey(2000,l); if ( tmpData != null ) { System.out.println("key 2000 gefunden: name = " + tmpData.name + " salary = " + tmpData.salary); lstInsert(new MyDataType(5,"name5",5000),l); } else { System.out.println("key 2000 NICHT gefunden"); } printAll(l); System.out.println("nach key 2 suchen und DAVOR Element einfügen: (5,name5,5000)"); tmpData = lstSearchKey(2,l); if ( tmpData != null ) { System.out.println("key 2 gefunden: name = " + tmpData.name + " salary = " + tmpData.salary); lstInsert(new MyDataType(5,"name5",5000),l); } else { System.out.println("key 2 NICHT gefunden"); } printAll(l); System.out.println("nach key 3 suchen und Listenelement löschen"); tmpData = lstSearchKey(3,l); if ( tmpData != null ) { System.out.println("key 3 gefunden: wird gelöscht"); lstDelete(l); } else { System.out.println("key 3 NICHT gefunden"); } printAll(l); tmpData = lstHead(l); System.out.println( "Listenkopf = (" + tmpData.key + "," + tmpData.name + "," + tmpData.salary + ")"); tmpData = lstNext(l); System.out.println( "Listenkopf von tail(l) = (" + tmpData.key + "," + tmpData.name + "," + tmpData.salary + ")"); } }