Eine einfache Liste für ganzzahlige Werte mit den Anforderungen aus der Aufgabenstellung (siehe Einfach verkettete Liste) könnte so aussehen:
// Time-stamp: "11.05.03 13:38 einfacheListe.java klaus@wachtler.de" // // Lösung der Übungsaufgabe: Erstellen einer einfach verketteten Liste // Die eigentliche Liste besteht aus einer Referenz auf das erste Element. public class einfacheListe { // Datentyp für ein Element der Liste: private class ListenElement { private int nutzdaten; // die Daten eines Elements private ListenElement next; // Verweis auf Nachfolger public ListenElement( int daten ) { nutzdaten = daten; next = null; } // fügt hinter sich ein neues Element ein: public void einf_dahinter( int wert ) { // dazu den bisherigen Nachfolger merken, um // ihn später als Nach-Nachfolger einsetzen zu können: ListenElement uebernaechster = next; // neues Element schaffen und anhängen: next = new ListenElement( wert ); // bisherigen Nachfolger dahinter setzen: next.setNext( uebernaechster ); } public void setDaten( int daten ) { nutzdaten = daten; } public int getDaten() { return nutzdaten; } public void setNext( ListenElement next_neu ) { next = next_neu; } public ListenElement getNext() { return next; } // sucht nach einem Wert, und liefert das ListenElement // (falls gefunden), oder null. public ListenElement sucheWert( int wert ) { // Schleife notfalls über alle Elemente: ListenElement aktuellesElement = this; do { if( aktuellesElement.getDaten()==wert ) { return aktuellesElement; } aktuellesElement = aktuellesElement.getNext(); } while( aktuellesElement.getNext()!=null ); // wenn alle Elemente nicht paßten, dann ist die Suche // fehlgeschlagen: return null; } // sucht nach dem Vorgänger eines Werts, und liefert das // ListenElement (falls gefunden), oder null. public ListenElement sucheVorgaengerVonWert( int wert ) { // Schleife notfalls über alle Elemente: ListenElement aktuellesElement = this; do { if( aktuellesElement.next!=null && aktuellesElement.next.getDaten()==wert ) { return aktuellesElement; } aktuellesElement = aktuellesElement.getNext(); } while( aktuellesElement.getNext()!=null ); // wenn alle Elemente nicht paßten, dann ist die Suche // fehlgeschlagen: return null; } // Ausgabe einer Liste in einen String: // Element ausgeben, dann ggf. den Rest public String toString() { return ( " El." + nutzdaten + ( next==null ? "." : ", " + next.toString() ) ); } } // class ListenElement private ListenElement anfang; public einfacheListe() { anfang = null; } // fügt einen neuen Wert am Anfang ein: public void einf_vorn( int wert ) { // das bisherige erste Element merken, um es später zum // zweiten zu machen (auch wenn das bisherige erste // null ist, also die Liste bisher leer ist): ListenElement zweites = anfang; // ein neues erstes Element erzeugen, und mit wert // initialisieren: anfang = new ListenElement( wert ); // das bisherige erste Element (oder null) hinten // anhängen: anfang.setNext( zweites ); } // fügt einen neuen Wert am Ende ein: public void einf_hinten( int wert ) { // Wenn die Liste noch leer ist, dann einfach ein // Element an den Anfang setzen: if( anfang==null ) { anfang = new ListenElement( wert ); } else { // Suche nach dem letzten Element: ListenElement letztes = anfang; while( letztes.getNext()!=null ) { letztes = letztes.getNext(); } // letztes hat jetzt keinen Nachfolger mehr. // Das wird geändert: letztes.einf_dahinter( wert ); } }
// versucht, ein neues Element wert hinter einem gegebenen Wert // hinterwas einzusetzen. // Das kann natürlich fehlschlagen, wenn das Element, hinter // dem eingefügt werden soll, gar nicht existiert. // Dementsprechend wird true zurückgegeben, wenn alles geklappt // hat; sonst false. public boolean einf_HinterWert( int hinterwas, int wert ) { // Leere Liste? if( anfang==null ) { return false; } else { ListenElement element = anfang.sucheWert( hinterwas ); if( element==null ) { return false; } else { element.einf_dahinter( wert ); return true; } } } // versucht, ein neues Element wert vor einem gegebenen Wert // vorwas einzusetzen. // Das kann natürlich fehlschlagen, wenn das Element, vor // dem eingefügt werden soll, gar nicht existiert. // Dementsprechend wird true zurückgegeben, wenn alles geklappt // hat; sonst false. public boolean einf_VorWert( int vorwas, int wert ) { // Leere Liste? if( anfang==null ) { return false; } // dann könnte es natürlich sein, daß gleich vor das erste // Element eingefügt werden soll: else if( anfang.getDaten()==vorwas ) { einf_vorn( wert ); return true; } else { ListenElement element = anfang.sucheVorgaengerVonWert( vorwas ); if( element==null ) { return false; } else { element.einf_dahinter( wert ); return true; } } } // sucht nach einem Wert, und liefert true, wenn der gesuchte Wert // enthalten ist: public boolean sucheWert( int wert ) { // Leere Liste? if( anfang==null ) { return false; } else { return anfang.sucheWert( wert )!=null; } } // versucht, ein Element wert aus der Liste zu löschen. // Das kann natürlich fehlschlagen, wenn das Element, das // gelöscht werden soll, gar nicht existiert. // Dementsprechend wird true zurückgegeben, wenn alles geklappt // hat; sonst false. public boolean entf_wert( int wert ) { // Leere Liste? if( anfang==null ) { return false; } // dann könnte es natürlich sein, daß gleich das erste // Element gelöscht werden soll: else if( anfang.getDaten()==wert ) { anfang = anfang.getNext(); return true; } else { // Ansonsten brauchen wir den Vorgänger des zu löschenden // Elements; dessen Nachfolger muß gelöscht werden: ListenElement element = anfang.sucheVorgaengerVonWert( wert ); if( element==null ) { return false; } else { element.setNext( element.getNext().getNext() ); return true; } } } // Ausgabe einer Liste in einen String: // Element ausgeben, dann den Rest public String toString() { return "Liste: " + ( anfang==null ? "-" : anfang.toString() ); } } // public class einfacheListe
Und hier das zugehörige Testprogramm:
// Time-stamp: "(17.05.02 11:53) teste_einfacheListe.java [Klaus@Wachtler.de]" // // javac teste_einfacheListe.java einfacheListe.java // java teste_einfacheListe // // Testprogramm für class einfacheListe import java.util.*; public class teste_einfacheListe { public static void main( String args[] ) { einfacheListe l = new einfacheListe(); // ein paar jeweils von vorne her einfügen: l.einf_vorn( 45 ); l.einf_vorn( 34 ); // ein paar von hinten: l.einf_hinten( 112 ); l.einf_hinten( 123 ); System.out.println( l.toString() ); // ist der Wert 45 enthalten? System.out.println( "45 ist " + ( l.sucheWert( 45 ) ? "" : "nicht " ) + "enthalten" ); // ist der Wert 123 enthalten? System.out.println( "123 ist " + ( l.sucheWert( 123 ) ? "" : "nicht " ) + "enthalten" ); // Die (nicht existierende) 30 löschen: if( l.entf_wert( 30 ) ) { System.out.println( l.toString() ); } else { System.out.println( "die 30 kann nicht gelöscht werden!" ); } // Die 123 löschen: if( l.entf_wert( 123 ) ) { System.out.println( l.toString() ); } else { System.out.println( "die 123 kann nicht gelöscht werden!" ); } // Die 112 löschen: if( l.entf_wert( 112 ) ) { System.out.println( l.toString() ); } else { System.out.println( "die 112 kann nicht gelöscht werden!" ); } // Hinter der 45 noch eine 50 einfügen: if( l.einf_HinterWert( 45, 50 ) ) { System.out.println( l.toString() ); } else { System.out.println( "hinter 45 kann nichts eingefügt werden!" ); } // Die 45 löschen: if( l.entf_wert( 45 ) ) { System.out.println( l.toString() ); } else { System.out.println( "die 45 kann nicht gelöscht werden!" ); } // Vor der 34 noch eine 30 einfügen: if( l.einf_VorWert( 34, 30 ) ) { System.out.println( l.toString() ); } else { System.out.println( "vor 34 kann nichts eingefügt werden!" ); } // Vor der 50 noch eine 48 einfügen: if( l.einf_VorWert( 50, 48 ) ) { System.out.println( l.toString() ); } else { System.out.println( "vor 50 kann nichts eingefügt werden!" ); } // Vor der nicht existierenden 10 noch eine 8 einfügen // (klappt hoffentlich nicht): if( l.einf_VorWert( 10, 8 ) ) { System.out.println( l.toString() ); } else { System.out.println( "vor 10 kann nichts eingefügt werden!" ); } } } // public class teste_einfacheListe
Die Ausgabe sieht folgendermaßen aus:
Liste: El.34, El.45, El.112, El.123. 45 ist enthalten 123 ist nicht enthalten die 30 kann nicht gelöscht werden! Liste: El.34, El.45, El.112. Liste: El.34, El.45. hinter 45 kann nichts eingefügt werden! Liste: El.34. Liste: El.30, El.34. vor 50 kann nichts eingefügt werden! vor 10 kann nichts eingefügt werden!
Die Musterlösung in C++ ist auffallend ähnlich der Java-Version (siehe Java-Version):
// Time-stamp: "11.05.03 17:12 einfacheListe.cpp klaus@wachtler.de" // // Lösung der Übungsaufgabe: Erstellen einer einfachen Liste // // ANSI-C++ // // Linux: g++ -Wall einfacheListe.cpp && ./a.out // // VC++ 6.0: cl /Zi /GX einfacheListe.cpp // .\einfacheListe #include <iostream> using namespace std; // Die eigentliche Liste besteht aus einem Zeiger auf das erste Element. class einfacheListe { private: // Datentyp für ein Element der Liste: class ListenElement { private: int nutzdaten; // die Daten eines Elements ListenElement *next; // Verweis auf Nachfolger public: // Konstruktor ListenElement( int daten = 0 ) { nutzdaten = daten; next = NULL; } // Destruktor // Achtung! Weil das delete next den Destruktor gleich wieder // für den Nachfolger aufruft, in dem wiederum ein delete next // steht, wird rekursiv die gesamte Liste ab dem aktuellen Element // freigegeben! // Wenn man nur ein Element freigeben will, aber nicht seine // Nachfolger, dann muß man zuvor sein next zu NULL setzen! virtual ~ListenElement() { delete next; } // fügt hinter sich ein neues Element ein: void einf_dahinter( int wert ) { // dazu den bisherigen Nachfolger merken, um // ihn später als Nach-Nachfolger einsetzen zu können: ListenElement *uebernaechster = next; // neues Element schaffen und anhängen: next = new ListenElement( wert ); // bisherigen Nachfolger dahinter setzen: next->setNext( uebernaechster ); } void setDaten( int daten ) { nutzdaten = daten; } int getDaten() { return nutzdaten; } void setNext( ListenElement *next_neu ) { next = next_neu; } ListenElement *getNext() { return next; } // sucht nach einem Wert, und liefert das ListenElement // (falls gefunden), oder NULL. ListenElement *sucheWert( int wert ) { // Schleife notfalls über alle Elemente: ListenElement *aktuellesElement = this; do { if( aktuellesElement->getDaten()==wert ) { return aktuellesElement; } aktuellesElement = aktuellesElement->getNext(); } while( aktuellesElement->getNext()!=NULL ); // wenn alle Elemente nicht paßten, dann ist die Suche // fehlgeschlagen: return NULL; } // sucht nach dem Vorgänger eines Werts, und liefert das // ListenElement (falls gefunden), oder NULL. ListenElement *sucheVorgaengerVonWert( int wert ) { // Schleife notfalls über alle Elemente: ListenElement *aktuellesElement = this; do { if( aktuellesElement->next!=NULL && aktuellesElement->next->getDaten()==wert ) { return aktuellesElement; } aktuellesElement = aktuellesElement->getNext(); } while( aktuellesElement->getNext()!=NULL ); // wenn alle Elemente nicht paßten, dann ist die Suche // fehlgeschlagen: return NULL; } // Ausgabe einer Liste in einen ostream: // Element ausgeben, dann ggf. den Rest virtual void tostream( ostream &o ) const { o << " El." << nutzdaten; if( next==NULL ) { o << "."; } else { o << ", "; next->tostream( o ); } } }; // class ListenElement ListenElement *anfang; public: // Konstruktor einfacheListe() { anfang = NULL; }
// Destruktor virtual ~einfacheListe() { // Listenelemente freigeben: delete anfang; } // fügt einen neuen Wert am Anfang ein: void einf_vorn( int wert ) { // das bisherige erste Element merken, um es später zum // zweiten zu machen (auch wenn das bisherige erste // NULL ist, also die Liste bisher leer ist): ListenElement *zweites = anfang; // ein neues erstes Element erzeugen, und mit wert // initialisieren: anfang = new ListenElement( wert ); // das bisherige erste Element (oder NULL) hinten // anhängen: anfang->setNext( zweites ); } // fügt einen neuen Wert am Ende ein: void einf_hinten( int wert ) { // Wenn die Liste noch leer ist, dann einfach ein // Element an den Anfang setzen: if( anfang==NULL ) { anfang = new ListenElement( wert ); } else { // Suche nach dem letzten Element: ListenElement *letztes = anfang; while( letztes->getNext()!=NULL ) { letztes = letztes->getNext(); } // letztes hat jetzt keinen Nachfolger mehr. // Das wird geändert: letztes->einf_dahinter( wert ); } } // versucht, ein neues Element wert hinter einem gegebenen Wert // hinterwas einzusetzen. // Das kann natürlich fehlschlagen, wenn das Element, hinter // dem eingefügt werden soll, gar nicht existiert. // Dementsprechend wird true zurückgegeben, wenn alles geklappt // hat; sonst false. bool einf_HinterWert( int hinterwas, int wert ) { // Leere Liste? if( anfang==NULL ) { return false; } else { ListenElement *element = anfang->sucheWert( hinterwas ); if( element==NULL ) { return false; } else { element->einf_dahinter( wert ); return true; } } } // versucht, ein neues Element wert vor einem gegebenen Wert // vorwas einzusetzen. // Das kann natürlich fehlschlagen, wenn das Element, vor // dem eingefügt werden soll, gar nicht existiert. // Dementsprechend wird true zurückgegeben, wenn alles geklappt // hat; sonst false. bool einf_VorWert( int vorwas, int wert ) { // Leere Liste? if( anfang==NULL ) { return false; } // dann könnte es natürlich sein, daß gleich vor das erste // Element eingefügt werden soll: else if( anfang->getDaten()==vorwas ) { einf_vorn( wert ); return true; } else { ListenElement *element = anfang->sucheVorgaengerVonWert( vorwas ); if( element==NULL ) { return false; } else { element->einf_dahinter( wert ); return true; } } } // sucht nach einem Wert, und liefert true, wenn der gesuchte Wert // enthalten ist: bool sucheWert( int wert ) { // Leere Liste? if( anfang==NULL ) { return false; } else { return anfang->sucheWert( wert )!=NULL; } } // versucht, ein Element wert aus der Liste zu löschen. // Das kann natürlich fehlschlagen, wenn das Element, das // gelöscht werden soll, gar nicht existiert. // Dementsprechend wird true zurückgegeben, wenn alles geklappt // hat; sonst false. bool entf_wert( int wert ) { // Leere Liste? if( anfang==NULL ) { return false; } // dann könnte es natürlich sein, daß gleich das erste // Element gelöscht werden soll: else if( anfang->getDaten()==wert ) { ListenElement *zweites = anfang->getNext(); // kurz merken // Das bisherige erste Element muß gelöscht werden. // Dazu: // 1. seinen Nachfolger abhängen (damit beim folgenden Frei- // geben nicht der gesamte Listenrest freigegeben wird): anfang->setNext( NULL ); // 2. das erste Element löschen: delete anfang;
// jetzt das zweite Element zum ersten machen: anfang = zweites; return true; } else { // Ansonsten brauchen wir den Vorgänger des zu löschenden // Elements; dessen Nachfolger muß gelöscht werden: ListenElement *element = anfang->sucheVorgaengerVonWert( wert ); if( element==NULL ) { return false; } else { // das zu löschende Element ist jetzt element->getNext(). // Dieses Element kurz merken, damit wir es zum Schluß // freigeben können: ListenElement *zuloeschen = element->getNext(); element->setNext( element->getNext()->getNext() ); // auch hier den Nachfolger plattmachen, damit beim // Freigeben von zuloeschen nicht der ganze Listenrest // freigegeben wird: zuloeschen->setNext( NULL ); delete zuloeschen; return true; } } } // Ausgabe einer Liste in einen String: // Element ausgeben, dann den Rest void tostream( ostream &o ) const { o<< "Liste: "; if( anfang==NULL ) o << "-"; else anfang->tostream( o ); } }; // class einfacheListe ostream &operator<<( ostream &o, const einfacheListe &l ) { l.tostream( o ); return o; } int main( int nargs, char **args ) { einfacheListe l; // ein paar jeweils von vorne her einfügen: l.einf_vorn( 45 ); l.einf_vorn( 34 ); // ein paar von hinten: l.einf_hinten( 112 ); l.einf_hinten( 123 ); cout << l << endl; // ist der Wert 45 enthalten? cout << "45 ist " << ( l.sucheWert( 45 ) ? "" : "nicht " ) << "enthalten" << endl; // ist der Wert 123 enthalten? cout << "123 ist " << ( l.sucheWert( 123 ) ? "" : "nicht " ) << "enthalten" << endl; // Die (nicht existierende) 30 löschen: if( l.entf_wert( 30 ) ) { cout << l << endl; } else { cout << "die 30 kann nicht gelöscht werden!" << endl; } // Die 123 löschen: if( l.entf_wert( 123 ) ) { cout << l << endl; } else { cout << "die 123 kann nicht gelöscht werden!" << endl; } // Die 112 löschen: if( l.entf_wert( 112 ) ) { cout << l << endl; } else { cout << "die 112 kann nicht gelöscht werden!" << endl; } // Hinter der 45 noch eine 50 einfügen: if( l.einf_HinterWert( 45, 50 ) ) { cout << l << endl; } else { cout << "hinter 45 kann nichts eingefügt werden!" << endl; } // Die 45 löschen: if( l.entf_wert( 45 ) ) { cout << l << endl; } else { cout << "die 45 kann nicht gelöscht werden!" << endl; } // Vor der 34 noch eine 30 einfügen: if( l.einf_VorWert( 34, 30 ) ) { cout << l << endl; } else { cout << "vor 34 kann nichts eingefügt werden!" << endl; } // Vor der 50 noch eine 48 einfügen: if( l.einf_VorWert( 50, 48 ) ) { cout << l << endl; } else { cout << "vor 50 kann nichts eingefügt werden!" << endl; } // Vor der nicht existierenden 10 noch eine 8 einfügen // (klappt hoffentlich nicht): if( l.einf_VorWert( 10, 8 ) ) { cout << l << endl; } else { cout << "vor 10 kann nichts eingefügt werden!" << endl; }
return 0; } // main( int nargs, char **args )
Die wesentlichen Unterschiede zur Java-Version sind:
next.getDaten()
eigentlich
(*next).getDaten()
schreiben, um von dem Zeiger aus (next) erst mit *
zum eigentlichen Objekt zu kommen, von dort aus
mit .
das Element (hier: getDaten()) zu erreichen. Es
wird hier dann die vereinfachende Schreibweise next->getDaten()
verwendet.
ifdef TESTPROGRAMM
... stillzulegen.
Die Ausgabe sieht folgendermaßen aus:
Liste: El.34, El.45, El.112, El.123. 45 ist enthalten 123 ist nicht enthalten die 30 kann nicht gelöscht werden! Liste: El.34, El.45, El.112. Liste: El.34, El.45. hinter 45 kann nichts eingefügt werden! Liste: El.34. Liste: El.30, El.34. vor 50 kann nichts eingefügt werden! vor 10 kann nichts eingefügt werden!
www.wachtler.de