Blatt07.pdf

Institut für Numerische Mathematik
Dr. Andreas F. Borchert und Dr. Michael C. Lehn
8. Dezember 2016
Blatt 7
Objektorientierte Programmierung mit C++
(WS 2016/2017)
Abgabe bis zum 15. Dezember 2016, 16:00 Uhr
Lernziele:
• Entwicklung von Unterklassen zur Navigation in der übergeordneten Klasse
• Implementierung einfacher Iteratoren
Aufgabe 8: Navigieren in Tries
Die zuvor erarbeitete Implementierung für die Trie-Datenstruktur sah noch keine Navigati-
onsmöglichkeit vor.
Eine Unterklasse Trie::Pointer von Trie ist zu entwickeln, die das Navigieren unterstützt, ohne dabei die internen Zeiger preiszugeben.
Folgendes Code-Beispiel demonstriert die gewünschte Funktionalität:
Trie::Pointer ptr = trie.descend();
if (ptr.defined()) {
for (char ch: key) {
if (!ptr.descend(ch)) break;
if (ptr.exists()) {
cout << *ptr << endl;
}
}
}
Aufgabe 9: Navigieren in Tries II
Mit dem Trie::Pointer lässt sich noch nicht auf einfache Weise ermitteln, welche weitergehen-
den Unterbäume zur Verfügung stehen.
Ein Iterator des Typs Trie::Pointer::Iterator ist zu implementieren, um über die weiterführenden Zeichen zu iterieren.
Die folgenden Bedingungen müssen erfüllt werden:
• Trie::Pointer muss die Methoden begin und end unterstützen
• Der Iterator muss den Operator „!=“ unterstützen
• Der Iterator muss das Prefix-Inkrement unterstützen
• Der Iterator muss die Dereferenzierung unterstützen
Mit Hilfe der Iteratoren kann das Rätsel gelöst werden, welches Wort aus /usr/dict/words die meisten Präfixe enthält, die zugleich auch Wörter aus der gleichen Sammlung sind.