10. ANSI-C-Aufgabe: Binäre Bäume und Funktionszeiger

Letztes Update: Dienstag, 16. August 2016 - 16:41 Uhr

Original-Aufgabenstellung:

In der letzten Übungsaufgabe in diesem Semester wollen wir uns noch einmal den binären Bäumen widmen.

Dieser binäre Baum wird durch sortiertes Einfügen aufgebaut. Vom Wurzelknoten aus wird der Baum nach links bzw. rechts erweitert, je nachdem, ob der eingefügte Knoten größer oder kleiner dem Vorgängerknoten ist. Der Baum ist nicht ausbalanciert, zumindest so lange nicht, wie nur eingefügt und gelöscht wird.

Es soll ein Interface geschrieben werden, welches uns das Einfügen, Umgestalten, Löschen und Traversieren im Baum erlaubt.

Anforderungen

  • Die durch den Header vorgegeben Funktionen sollen implementiert werden.

  • Die zu implementierenden Funktionen können nicht nur direkt, sondern auch über eine Indirekt-Funktion mit Hilfe eines Funktionszeigers aufgerufen werden.
    • sort (Sortierfunktionen)
    • change (Manipulationsfunktionen)
    • prad (Prädikatsfunktionen)
    Alle anderen Funktionen passen auf eine dieser 3 Schnittstellen. Die Schnittstellen sind aus den Funktionsbeschreibungen zu erstellen.

  • gprof (Bonusanteil)
    Profiling bietet eine recht einfache Möglichkeit, das Laufzeitverhalten eines Programms zu überwachen, Schwachstellen zu erkennen und u.U. mit neuen Algorithmen die Laufzeit zu optimieren. Um ein Programm mit gprof zu testen, muß man es mit der gcc Compileroption -pg uebersetzen. Nun wird standardmäßig eine sogenannte profiling Datei mit dem Namen gmon.out erzeugt. Ist das Programm einmal übersetzt, muß es gestartet werden. Das Programm verhält sich dann wie immer und macht auch die gleichen Ausgaben. Beim Beenden des Programms werden alle profiling Informationen in die gmon.out geschrieben. Existiert diese Datei bereits, wird sie überschrieben. Die profiling Datei wird in das aktuelle Arbeitsverzeichnis geschrieben.
    Mit dem Programm gprof kann diese profiling Datei nun ausgewertet werden. Dazu wird das Programm wie folgt aufgerufen:
      gprof -b <Programmname>

  • Wie in den letzten Übungen auch, ist ein eigener Test, der die korrekte Funktionsweise aller Prozeduren demonstriert, zu schreiben.

Hinweise

  • Binäre Bäume
    Der abgebildete Baum wurde mit Hallo erzeugt, oder Hallo wurde zuerst in den Baum eingefügt. Danach wurden Anton und Moritz in den Baum eingefügt. In welcher Reihenfolge beide eingefügt wurden ist egal, da es nichts am Baum ändert. Anton ist vom Standpunkt eines String gesehen kleiner als Hallo, wird daher links eingefuegt, Moritz ist größer als Hallo, wird daher rechts eingefügt. Anna ist kleiner als Hallo und kleiner als Anton, folglich wird sie links von Anton eingefügt, etc.
    Beispielbaum

  • Die in den Knoten gespeicherten Namen werden case-insensitive betrachtet.

  • Sortierungen
    Es gibt 3 Sortieralgorithmen, die in den Funktionen beschrieben sind. Ein paar Grafiken sollen den Output verdeutlichen.
    • SortToRight
      rechtssortierter Baum
    • SortToLeft
      Analog zu SortToRight ...
    • SortToBalance
      ausbalancierter Baum

  • Zum Löschen im Baum gibt es 2 Funktionen. Die eine ist trivial (removePartTree()) und löscht von einem bestehenden Objekt das Objekt selbst und alles was dran hängt. Diese Funktion muß von jedem realisiert werden!

    Die andere (removeTree()) löscht nur ein Objekt aus dem Baum und organisiert den daran hängenden Teilbaum nach folgendem Wirth-Algorithmus:
    PROCEDURE delete(x:INTEGER; var p: ref);
    	var q: ref;
    	PROCEDURE del(var r: ref);
    	BEGIN IF r^.right <> NIL THEN del (r^.right) ELSE
    		BEGIN q^.key := r^.key;
    			q^.count := r^.count;
    			q := r;
    			r := r^.left
    		END
    	END;
    BEGIN{delete}
    	IF p=NIL THEN writeln('Wort nicht im Baum') ELSE
    	IF x < p^.key THEN delete(x,p^.left) ELSE
    	IF x > p^.key THEN delete(x,p^.right) ELSE
    	BEGIN {entferne p^} q:=p;
    		IF q^.right = NIL THEN p:=q^.left ELSE
    		IF q^.left = NIL THEN p:=q^.right
       ELSE del(q^.left);
    		dispose(q);
    	END
    END {delete}
    Dieser Algorithmus muß natürlich auf die bestehenden Belange angepaßt werden. So kann z.B. count und key vernachläßigt werden, da wir ja nur ein wort in unserem Baum haben. Diese Funktion muß für Bonuspunkte realisiert werden.

  • Das Programm kann als Bibliothek kompiliert werden, muß aber nicht.

  • Bonuspunkte
    Wer diese Aufgabe lösen muß, um die C-Übung zu bestehen, der braucht nur eine "abgespeckte" Version zu implementieren.

    Um jedoch die 5 Bonuspunkte zu erhalten, müssen folgende Aspekte implementiert werden:
    • sortToBalance()
    • removeTree()
    • Rekursionen - der Baum muß rekursiv bearbeitet werden.
    • gprof - Arbeitet euch in die Hilfe von gprof ein, da von euch erklärt werden soll, was die einzelnen Zeilen des Ausgabegraphen bedeuten.

Gutes Gelingen!

 

Download Beispiel-Lösungsvorschlag, Quelltext inkl. Projektdateien für VC6 (ZIP-Archiv, 48 KB)

 

Zur Aufgaben-Übersicht

 

Gefällt dir die C Übungsaufgabe? Schreibe doch einen Kommentar...

 

Neuen Kommentar abgeben

7ukmf