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** readStringsAndSort(char *filename);
     Dateinformat:
     /Wort1/
     ...
     /Wortn/
     Die Funktion liest die Strings aus der Datei und gibt sie in einem Array in sortierter Form zurück. Die Länge der Wortliste ist Ihnen nicht bekannt. Sie kann beliebig lang sein. Wie die Strings sortiert werden bleibt Ihnen überlassen.
     Tip: Schreiben Sie eine Funktion int insertStrIntoArry( char** strarry, char *string); die einen eingelesenen String in ein Array einsortiert.

   • int writeSortedStrings(char *filename, char** strarry);
     Die Funktion schreibt das (sortierte) Array von Strings in eine Datei zurück.

   • char** readStrings(char *filename);
     Dateinformat:
     /Wort1/
     ...
     /Wortn/
     Die Funktion liest die (Such-)Strings aus der Datei und gibt sie in einem Array zurück. Das Array muss nicht sortiert werden!
     Die Länge der Wortliste ist Ihnen nicht bekannt. Sie kann beliebig lang sein.

   • int fügeElementEin( char** binaerbaum, char *string);
   • char* binaereSuche( char** strarry, char *string);

   Schreiben Sie ein Programm, das die Strings mit readStringsAndSort einliest und mit writeSortedStrings wieder ausgibt. (Programm da511-???.c )

2. Schreiben Sie auch ein Programm, das die zu sortierenden Daten mit readStringsandSort einliest, anschlie&suml;end die Suchwöter mittels readStrings einliest und im Array mittels binaereSuche sucht. Das Suchergebnis auf dem Bildschirm ausgegeben werden. (Programm 512-???.c)

3. Implementieren Sie die Funktion
   
   • char* interpolationsSuche(char** strarry, char *string);
     
   gemäß der Interpolationsuche. (Programm 513-???.c )

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