5-0.

Compilieren, starten und testen Sie die Programme in diesem Kapitel.

5-1.

Planen und implementieren Sie ein Programm, das einen permutierten Index erzeugt.
Ein permutierter Index ist einer, bei dem jede Wortgruppe durch jedes Wort der
Wortgruppe indiziert wird. Mit folgender Eingabe

The quick brown fox
jumped over the fence
würde die Ausgabe
The quick brown fox
jumped over the fence
The quick brown fox
jumped over the fence
jumped over the fence
The quick brown fox
jumped over the fence
The quick brown fox

lauten. Ein guter Algorithmus dafür wird in The AWK Programming Language von
Aho, Kernighan und Weinberger (Addison-Wesley, 1988) vorgeschlagen.

Diese Lösung teilt das Problem in drei Schritte:

1. Lies jede Eingabezeile und erzeuge eine Anzahl von Rotationen dieser Zeile.
Jede Rotation stellt das nachste Wort der Eingabe an die erste Position und rotiert
das vorherige erste Wort an das Ende der Wortgruppe. Die Ausgabe dieser Phase
für die erste Eingabezeile wäre:
The quick brown fox
quick brown fox The
brown fox The quick
fox The quick brown
Es ist natürlich erforderlich zu wissen, wo die originale Wortgruppe endet und wo
der rotierte Beginn anfangt.

2. Sortiere die Rotationen.

3. Derotiere und schreibe den permutierten Index, was als Teilaufgaben das Finden
des Trennzeichens, das Zusammensetzen der Wortgruppe und die ordentlich
formatierte Ausgabe erfordert.

5-2. / 5-3.

Schreiben Sie eine vollkommen neue Version des Studentenbenotungsprogramms, die
Datensätze für durchgefallene Studenten mit Hilfe von vectors extrahiert. Schreiben
Sie eine weitere Version unter Benutzung von lists. Messen Sie die Performance für
Eingabedateien von zehn, 1.000 und 10.000 Zeilen.

Indem wir einen typedef benutzen, können wir eine Version des Programms
schreiben, die entweder eine vector- oder list-basierte Lösung enthält. Schreiben und
testen Sie diese Version des Programmes.

5-6.

Schreiben Sie die Funktion durchgefallene aus Abschnitt 5.1.1 auf Seite 109 so um,
dass die Datensätze der durchgefallenen Studenten nicht mehr aus dem Eingabevector
v entfernt werden, sondem die Datensätze der bestandenen Studenten an den Anfang
des vectors kopiert und danach die Funktion resize aufruft, um die übrigen Elemente
vom Ende von v zu entfernen. Wie verhält sich die Performance dieser Lösung im
Vergleich zu der in Abschnitt 5.1.1 auf Seite 109?

5-10.

Palindrome sind Worte die von links nach rechts und von rechts nach links gleich
geschrieben werden. Schreiben Sie ein Programm, das alle Palindrome in einem
Waörterbuch finden kann. Finden Sie als nächstes das längste Palindrom.