Nächste Seite: A.2.6 Einfach verkettete Liste Aufwärts: A.2 Lösungen Vorherige Seite: A.2.4 Binäre Suche Inhalt
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!