Nächste Seite: A.2.7 Geschlossenes Hashing Aufwärts: A.2 Lösungen Vorherige Seite: A.2.5 Einfach verkettete Liste Inhalt
Als Beispieldatentyp wird wieder der Student aus Java-Version verwendet. Zur Demonstration der Referenzsemantik (siehe unten) wird allerdings noch eine Methode setVorname( String ) eingefügt, um ein Objekt im Nachhinein manipulieren zu können:
// Time-stamp: "11.05.03 15:35 Student.java klaus@wachtler.de"
//
// Testklasse zum Einfügen in einen Container
import java.util.*;
public class Student
{
private String VorName;
private String NachName;
public int Matrikelnummer;
public Student()
{
VorName = NachName = "?";
Matrikelnummer = -1;
}
public Student( String v, String n, int m )
{
VorName = v;
NachName = n;
Matrikelnummer = m;
}
public String toString()
{
return "<" + VorName + " "
+ NachName + " "
+ Matrikelnummer + ">";
}
// vergleicht zwei Studenten auf Gleichheit
public boolean equals( Object s )
{
return Matrikelnummer==((Student)s).Matrikelnummer;
}
public void setVorname( String neuerVorname )
{
VorName = neuerVorname;
}
} // class Student
Die Lösung besteht ansonsten aus einer leicht modifizierten Version der Musterlösung Einfach verkettete Liste:
Die wesentlichen Änderungen bestehen aus dem Ersatz des int-Typs durch Object sowie des Operators == durch den Aufruf der Object-Methode equals().
// Time-stamp: "11.05.03 13:53 einfacheListeGenerisch.java klaus@wachtler.de"
//
// Lösung der Übungsaufgabe: Erstellen einer einfach verketteten Liste
// eines beliebigen Typs
//
// 11.05.2003 kw Beim Vergleich von Objekten == durch equals() ersetzt
// Die eigentliche Liste besteht aus einer Referenz auf das erste
// Element (diese ist bei einer leeren Liste null);
// jedes Element wiederum hat Nutzdaten und eine Referenz auf
// das nachfolgende Element (oder null).
public class einfacheListeGenerisch
{
// Datentyp für ein Element der Liste:
private class ListenElement
{
private Object nutzdaten; // die Daten eines Elements
private ListenElement next; // Verweis auf Nachfolger
public ListenElement( Object daten )
{
nutzdaten = daten;
next = null;
}
// fügt hinter sich ein neues Element ein:
public void einf_dahinter( Object 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( Object daten )
{
nutzdaten = daten;
}
public Object 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( Object wert )
{
// Schleife notfalls über alle Elemente:
ListenElement aktuellesElement = this;
do
{
if( aktuellesElement.getDaten().equals( 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( Object wert )
{
// Schleife notfalls über alle Elemente:
ListenElement aktuellesElement = this;
do
{
if( aktuellesElement.next!=null
&&
aktuellesElement.next.getDaten().equals( 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 einfacheListeGenerisch()
{
anfang = null;
}
// fügt einen neuen Wert am Anfang ein:
public void einf_vorn( Object 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( Object 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( Object hinterwas, Object 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( Object vorwas, Object 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().equals( 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 ihn, falls vorhanden:
public Object sucheWert( Object wert )
{
// Leere Liste?
if( anfang==null )
{
return null;
}
else
{
ListenElement gefunden = anfang.sucheWert( wert );
return gefunden!=null ? gefunden.getDaten() : 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( Object 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().equals( 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 einfacheListeGenerisch
Die hier vorgestellte Lösung realisiert eine Referenzsemantik; Wenn der Aufrufer also nach dem Einfügen von Werten die Objekte manipuliert, wirkt sich dies auf den Inhalt der Liste aus.
Kurz vor Ende des Testprogramms wird zur Demonstration einer der vorher eingefügten Werte (Hein) geändert, und anschließend der Listeninhalt nochmals ausgegeben:
// Time-stamp: "11.05.03 18:37 teste_einfacheListeGenerisch.java klaus@wachtler.de"
//
// javac teste_einfacheListeGenerisch.java einfacheListe.java
// java teste_einfacheListeGenerisch
//
// Testprogramm für class einfacheListeGenerisch
import java.util.*;
public class teste_einfacheListeGenerisch
{
public static void main( String args[] )
{
einfacheListeGenerisch l = new einfacheListeGenerisch();
// ein paar jeweils von vorne her einfügen:
l.einf_vorn( new Student( "K.", "Meier", 123456 ) );
Student Hein = new Student( "Hein", "Blöd", 987654 );
l.einf_vorn( Hein );
// einen von hinten:
l.einf_hinten( new Student( "E.", "Steinberger", 876543 ) );
System.out.println( l.toString() );
Student gefunden;
// ist der Student mit der Matrikelnummer 987654 enthalten?
gefunden = (Student)l.sucheWert( new Student( "", "", 987654 ) );
System.out.println( "987654 ist "
+ ( ( gefunden!=null )
? "so: " + gefunden.toString()
: "nicht"
)
+ " enthalten"
);
// ist der Student mit der Matrikelnummer 333333 enthalten?
gefunden = (Student)l.sucheWert( new Student( "", "", 333333 ) );
System.out.println( "333333 ist "
+ ( ( gefunden!=null )
? "so: " + gefunden.toString()
: "nicht"
)
+ " enthalten"
);
// Die (nicht existierende) 333333 löschen:
if( l.entf_wert( new Student( "", "", 333333 ) ) )
{
System.out.println( "333333 gelöscht; " + l.toString() );
}
else
{
System.out.println( "der 333333 kann nicht gelöscht werden!" );
}
// Die 876543 löschen:
if( l.entf_wert( new Student( "", "", 876543 ) ) )
{
System.out.println( "876543 gelöscht; " + l.toString() );
}
else
{
System.out.println( "der 987654 kann nicht gelöscht werden!" );
}
// Hinter Hein noch einen einfügen:
if( l.einf_HinterWert( Hein, new Student( "S.", "Schmidt", 542366 ) ) )
{
System.out.println( l.toString() );
}
else
{
System.out.println( "hinter Hein kann nichts eingefügt werden!" );
}
System.out.println( l );
// Der zu Anfang eingefügte Hein wird jetzt geändert.
// Dadurch ändert sich auch der Inhalt der Liste!
Hein.setVorname( "Hinnerk" );
System.out.println( l );
}
} // public class teste_einfacheListeGenerisch
Die Referenzsemantik ist im Vergleich der letzten beiden Zeilen der Ausgabe zu erkennen:
Liste: El.<Hein Blöd 987654>, El.<K. Meier 123456>, El.<E. Steinberger 876543>. 987654 ist so: <Hein Blöd 987654> enthalten 333333 ist nicht enthalten der 333333 kann nicht gelöscht werden! 876543 gelöscht; Liste: El.<Hein Blöd 987654>, El.<K. Meier 123456>. Liste: El.<Hein Blöd 987654>, El.<S. Schmidt 542366>, El.<K. Meier 123456>. Liste: El.<Hein Blöd 987654>, El.<S. Schmidt 542366>, El.<K. Meier 123456>. Liste: El.<Hinnerk Blöd 987654>, El.<S. Schmidt 542366>, El.<K. Meier 123456>.
Um die C++-Version aus Einfach verkettete Liste generisch zu machen, muß man:
class... durch
template<class T> class.. ersetzen
ListenElement<T> ersetzen
Wie in C++ eher üblich wird hier eine Wertsemantik implementiert, das heißt bei jedem Einfügevorgang wird eine Kopie des einzufügenden Objekts erzeugt und diese Kopie wird in die Liste eingehängt. Die Kopie wird freigegeben, wenn das Element aus der Liste gelöscht wird, oder die gesamte Liste aufgelöst wird. Dadurch ist die Lebensdauer der Listenelemente vollständig von der Lebensdauer der einzufügenden Objekte entkoppelt.
// Time-stamp: "17.09.04 12:28 einfacheListeGenerisch.h klaus@wachtler.de"
//
// Testprogramm zur Übungsaufgabe: Erstellen einer generischen Liste
//
// ANSI-C++
//
// Änderungen:
// 11.05.2003 kw aufgeteilt in Headerdatei (einfacheListeGenerisch.h)
// und Testprogramm (templliste.cpp),
// Klasse von "beliebigeListe" zu
// "einfacheListeGenerisch" umbenannt,
// ListenElement jetzt als Unterklasse in
// einfacheListeGenerisch
#ifndef _EINFACHELISTE_GENERISCH_H_
#define _EINFACHELISTE_GENERISCH_H_
#include <iostream>
using namespace std;
// Die eigentliche Liste besteht aus einem Zeiger auf das erste Element.
template<class T>class einfacheListeGenerisch
{
private:
// Datentyp für ein Element der Liste:
class ListenElement
{
private:
// Die folgende Zeile entscheidet darüber, daß dieser Container
// eine Wertsemantik implementiert:
// (nutzdaten) ist ein komplettes Objekt vom Typ T der
// Nutzdaten, und erhält beim Erzeugen eines ListenElements
// durch Zuweisung eine Kopie der einzufügenden Daten (siehe im
// Konstruktor die Zeile:
// nutzdaten = daten;
// .
// Eine Referenzsemantik würde man erhalten, wenn hier anstatt
// T nutzdaten;
// stehen würde:
// T *nutzdaten_p;
// und die restlichen Methoden entsprechend angepaßt würden
// (der Konstruktor ListenElement( const T &daten ) müßte dann
// beispielsweise enthalten:
// nutzdaten_p = &daten;
// ).
// Dann wäre in den ListenElementen keine Kopie, sondern ein
// Zeiger auf die Originaldaten vorhanden, und eine Änderung der
// eingefügten Objekte ginge einher mit einer Änderung des
// Containerinhalts.
T nutzdaten; // die Daten eines Elements
ListenElement *next; // Verweis auf Nachfolger
public:
// Konstruktor
ListenElement( const T &daten )
{
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( const T &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( const T &daten )
{
nutzdaten = daten;
}
const T &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( const T &wert )
{
// Schleife notfalls über alle Elemente:
ListenElement *aktuellesElement = this;
do
{
if( aktuellesElement->getDaten()==wert )
{
return aktuellesElement;
}
aktuellesElement = aktuellesElement->getNext();
}
// Änderung 04.07.2002 KW: in der bisherigen Form:
// while( aktuellesElement->getNext()!=NULL );
// wird versehentlich das letzte Element der Liste nicht geprüft!
// Besser ist es so;
while( aktuellesElement!=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( const T &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
einfacheListeGenerisch()
{
anfang = NULL;
}
// Destruktor
virtual ~einfacheListeGenerisch()
{
// Listenelemente freigeben:
delete anfang;
}
// fügt einen neuen Wert am Anfang ein:
void einf_vorn( const T &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( const T &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( const T &hinterwas, const T &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( const T &vorwas, const T &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 einen Zeiger darauf, oder NULL:
const T *sucheWert( const T &wert )
{
// Leere Liste?
if( anfang==NULL )
{
return NULL;
}
else
{
ListenElement *LE_gefunden = anfang->sucheWert( wert );
return LE_gefunden ? &(LE_gefunden->getDaten()) : 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( const T &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 einfacheListeGenerisch
template<class T> ostream &operator<<( ostream &o,
const einfacheListeGenerisch<T> &l
)
{
l.tostream( o );
return o;
}
#endif /* _EINFACHELISTE_GENERISCH_H_ */
Probiert wird im Testprogramm sowohl eine Liste des (elementaren) Typs int als auch eine Liste einer eigenen Klasse Student:
// Time-stamp: "11.05.03 18:37 teste_einfacheListeGenerisch.cpp klaus@wachtler.de"
//
// Lösung der Übungsaufgabe: Erstellen einer generischen Liste
//
// ANSI-C++
//
// Linux: g++ -Wall teste_einfacheListeGenerisch.cpp && ./a.out
//
// Änderungen:
// 04.07.2002 kw In ListenElement::sucheWert( T wert )
// wurde bisher versehentlich das letzte Element
// nicht mehr geprüft.
//
// 11.05.2003 kw aufgeteilt in Headerdatei (einfacheListeGenerisch.h)
// und Testprogramm (teste_einfacheListeGenerisch.cpp),
// Klasse von "beliebigeListe" zu
// "einfacheListeGenerisch" umbenannt
#include <iostream>
using namespace std;
#include "einfacheListeGenerisch.h"
#include <string>
class Student
{
public:
// Konstruktor
Student( string Vorname = "",
string Nachname = "",
int Matrikelnummer = 0
)
: Vorname( Vorname ),
Nachname( Nachname ),
Matrikelnummer( Matrikelnummer )
{
}
// copy-Konstruktor
Student( const Student &rechteSeite )
: Vorname( rechteSeite.Vorname ),
Nachname( rechteSeite.Nachname ),
Matrikelnummer( rechteSeite.Matrikelnummer )
{
}
// Destruktor
virtual ~Student()
{
}
// Zuweisung Student = Student
Student & operator=( const Student &rechteSeite )
{
Vorname = rechteSeite.Vorname;
Nachname = rechteSeite.Nachname;
Matrikelnummer = rechteSeite.Matrikelnummer;
return *this;
}
// Vergleich Student == Student
bool operator==( const Student &rechteSeite ) const
{
return Matrikelnummer == rechteSeite.Matrikelnummer;
}
// Ausgabe auf einen ostream
virtual void streamout( ostream & s ) const
{
s << "(" << Vorname
<< "," << Nachname
<< "," << Matrikelnummer << ")";
}
void setVorname( string neuerVorname )
{
Vorname = neuerVorname;
}
private:
string Vorname;
string Nachname;
int Matrikelnummer;
}; // class Student...
// ggf. nach Student.cpp kopieren:
ostream &operator<<( ostream &s, const Student &obj )
{
obj.streamout( s );
return s;
}
int main( int nargs, char **args )
{
// Liste mit int-Werten:
einfacheListeGenerisch<int> 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;
}
// Liste mit Studenten:
einfacheListeGenerisch<Student> sl;
// ein paar jeweils von vorne her einfügen:
sl.einf_vorn( Student( "K.", "Meier", 123456 ) );
Student Hein( "Hein", "Blöd", 987654 );
sl.einf_vorn( Hein );
// einen von hinten:
sl.einf_hinten( Student( "E.", "Steinberger", 876543 ) );
cout << "Studentenliste=" << sl << endl;
const Student *p_gefunden;
// ist der Student mit der Matrikelnummer 987654 enthalten?
p_gefunden = sl.sucheWert( Student( "", "", 987654 ) );
cout << "987654 ist ";
if( p_gefunden )
{
cout << "so: " << *p_gefunden;
}
else
{
cout << "nicht";
}
cout << endl;
// ist der Student mit der Matrikelnummer 333333 enthalten?
p_gefunden = sl.sucheWert( Student( "", "", 333333 ) );
cout << "333333 ist ";
if( p_gefunden )
{
cout << "so: " << *p_gefunden;
}
else
{
cout << "nicht";
}
cout << " enthalten" << endl;
// Die (nicht existierende) 333333 löschen:
if( sl.entf_wert( Student( "", "", 333333 ) ) )
{
cout << "333333 gelöscht; Studentenliste=" << sl << endl;
}
else
{
cout << "die 333333 kann nicht gelöscht werden!" << endl;
}
// Die 876543 löschen:
if( sl.entf_wert( Student( "", "", 876543 ) ) )
{
cout << "876543 gelöscht; Studentenliste=" << sl << endl;
}
else
{
cout << "der 876543 kann nicht gelöscht werden!" << endl;
}
// Hinter Hein noch einen einfügen:
if( sl.einf_HinterWert( Hein, Student( "S.", "Schmidt", 542366 ) ) )
{
cout << sl << endl;
}
else
{
cout << "hinter Hein kann nichts eingefügt werden!" << endl;
}
// Der zu Anfang eingefügte Hein wird jetzt geändert.
// Dadurch ändert sich NICHT der Inhalt der Liste, da
// Wertsemantik!
Hein.setVorname( "Hinnerk" );
cout << sl << endl;
return 0;
} // main( int nargs, char **args )
Die letzten beiden Zeilen der Ausgabe sind identisch (im Gegensatz zur Java-Version; siehe Java-Version), obwohl zwischenzeitlich der vorher eingefügte Hein geändert wurde; also hat dieser Container eine Wertsemantik:
Liste: El.34, El.45, El.112, El.123. 45 ist enthalten 123 ist enthalten die 30 kann nicht gelöscht werden! Liste: El.34, El.45, El.112. Liste: El.34, El.45. Liste: El.34, El.45, El.50. Liste: El.34, El.50. Liste: El.30, El.34, El.50. Liste: El.30, El.34, El.48, El.50. vor 10 kann nichts eingefügt werden! Studentenliste=Liste: El.(Hein,Blöd,987654), El.(K.,Meier,123456), El.(E.,Steinberger,876543). 987654 ist so: (Hein,Blöd,987654) 333333 ist nicht enthalten die 333333 kann nicht gelöscht werden! 876543 gelöscht; Studentenliste=Liste: El.(Hein,Blöd,987654), El.(K.,Meier,123456). Liste: El.(Hein,Blöd,987654), El.(S.,Schmidt,542366), El.(K.,Meier,123456). Liste: El.(Hein,Blöd,987654), El.(S.,Schmidt,542366), El.(K.,Meier,123456).