Dr. Matthias Grabert Abteilung Angewandte Informationsverarbeitung 15. Mai 2004
Claudia Fischer Blatt 3






C++ mit Data Mining Anwendungen (SS 2004)


Abgabetermin: 27. Mai 2004

Binäre Suchbäume (10 Punkte)

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).

Sehr große Zahlen (10 Punkte)

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$<100>$
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!