Bitte unbedingt beachten:

Übungsblatt 5

Abgabe: 14.12.95 um 12:00 Uhr

Aufgabe 1 [30 Punkte]

1. Implementieren Sie die Binäre Suche. Die Suchelemente sind diesmal aber keine Zahlen, sondern Zeichenketten (Strings). In C werden Zeichenketten über Zeiger verwaltet. Sie müssen also die Zeichenketten über eine Array aus Zeigern vom Typ char* verwalten. Folgende Funktionen müssen Sie schreiben:
   • char** leseWoerterAusDatei(char *filename);
     Dateinformat:
     /Wort1/
     ...
     /Wortn/
     Die Länge der Wortliste ist Ihnen nicht bekannt. Sie kann beliebig lang sein.
   • int schreibeWoerterSortiertInDatei(char *filename, char** binaerbaum);
   • char** leseSuchWoerterAusDatei(char *filename);
     Dateinformat:
     /Wort1/
     ...
     /Wortn/
     Die Länge der Wortliste ist Ihnen nicht bekannt. Sie kann beliebig lang sein.
   • int fügeElementEin( char** binaerbaum, char *string);
   • char* binaereSuche( char** binaerbaum, char *string);

   Schreiben Sie ein Programm, das die Strings mit leseWoerterAusDatei einliest, in das Array an der richtigen Stelle (sortiert) einfügt und den resultierenden Binärbaum mit schreibeWoerterSortiertInDatei wieder ausgibt. Schreiben Sie auch ein Programm, das die zu sortierenden Daten mit leseWoerterAusDatei einliest, in das Array an der richtigen Stelle (sortiert) einfügt, die Suchwöter mittels leseSuchWoerterAusDatei einliest und das Suchergebnis auf dem Bildschirm ausgibt.

2. Implementieren Sie die Funktion
   
   • char* interpolationsSuche(char** binaerbaum, char *string);
     
   gemäß der Interpolationsuche.

3. Vergleichen Sie das Laufzeitverhalten der Suchverfahren aus 1. und 2. bei einer großen Anzahl von Wörtern (>1000).

Aufgabe 2 [20 Punkte]

• 7,2,7,3,3,7,4,4,4,7,5,5,5,5,7,6,6,6,6,6,7