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

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.
  
  
  
• 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
    
  • SortToLeft
    Analog zu SortToRight ...
  • SortToBalance
    
• 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...

Kommentare 2