Dr. Matthias Grabert Abteilung Angewandte
Informationsverarbeitung 15. Mai 2004
Claudia Fischer Blatt 3
C++ mit Data Mining Anwendungen (SS 2004)
Abgabetermin: 27. Mai 2004
Schreiben Sie ein Template für binäre Suchbäume.
Zur Erinnerung:
Binäre Suchbäume sind Binärbäume, in denen Daten so abgelegt werden,
dass für jeden Teilbaum die Elemente im linken Teilbaum kleiner (oder gleich)
sind als das Wurzelelement und dieses kleiner (oder gleich) als die
Elemente im rechten Teilbaum.
Beim Anlegen eines Baums soll eine Funktion mitübergeben
werden, mit deren Hilfe die Daten sortiert werden.
Desweiteren soll es natürlich möglich sein, Datensätze
einzuzufügen und zu löschen. (Natürlich so, dass die Daten
innerhalb des Baumes immernoch sortiert sind.) Außerdem soll es eine Funktion
zur sortierten Ausgabe der Datensätze geben, eine Funktion,
die überprüft, ob ein bestimmter Datensatz vorhanden ist und
eine Funktion, die den Baum wieder zerstört (und den
Speicherplatz wieder freigibt).
Sie dürfen davon ausgehen, dass für den Datentyp, der das
Template benützt, ein -Operator (d.h. ein Ausgabeoperator) definiert ist.
Schreiben Sie außerdem ein kurzes Programm, dass Ihr Template
mithilfe eines einfachen Datentyp testet (z.B. int oder char).
Bei Templates kann nicht nur der Datentyp variabel sein,
sondern auch die Variable selber. Schreiben Sie ein Template
'hugeint' für große natürliche Zahlen. Die Anzahl der Stellen
MAX_Stellen soll variabel sein. Die Zeile
hugeint
soll z.B. eine hundertstellige Zahl erzeugen.
Es sollte eine Funktion existieren, die aus einer Zahl vom Typ
long eine 'hugeint' erzeugt. Wird diese Funktion ohne Parameter
aufgerufen, so soll die Zahl den Wert Null haben. Außerdem
sollten einige der üblichen Operationen auf den natürlichen Zahlen
definiert sein: Addition, Subtraktion und Multiplikation, sowie
Inkrementierung und Dekrementierung (um 1) und Division mit Rest (div und mod).
(Überprüfen Sie bitte, ob das Ergebnis positiv ist.) Sie dürfen davon
ausgehen, dass das Ergebnis als hugeint mit MAX_Stellen
darstellbar ist. Überprüfen Sie aber, ob das Ergebnis positiv ist.
Zusätzlich soll es noch eine
Funktion für die Ausgabe geben und eine, die eine 'hugeint'
kopieren kann.
Testen Sie auch dieses Template mit einem kurzen Programm.
Bitte verwenden Sie Exeptions um Fehler abzufangen.
Viel Erfolg!
Claudia Fischer
2004-05-15