Dr. Johannes Mayer Abteilung Angewandte Informationsverarbeitung 10. Januar 2006
Axel Blumenstock Blatt 10
Christian Ehrhardt


Uni Logo



Allgemeine Informatik III / Systemnahe Software I (WS 2005/2006)


Abgabetermin: 17. Dezember 2005

Hash Mich (10 Punkte)

In Blatt 8 haben wir einen Worthäufigkeitszähler implementiert. Als Datenstruktur lag ein dynamischer Binärbaum zu Grunde, in dem jedes gelesene Wort nachgeschlagen werden konnte. Falls es gefunden wurde, wurde ein assoziierter Zähler inkrementiert, ansonsten ein neuer Eintrag mit dem Zählerstand 1 angelegt. Schließlich wurde der Baum durchlaufen und (Teile davon) als Worthäufigkeitstabelle ausgegeben.

\includegraphics[width=80mm]{baum1}
Die in diesem Ablauf notwendigen Operationen setzen keineswegs voraus, dass die Datenstruktur ein Binärbaum ist. Wir können Vorbedingungen und Effekte dieser Operationen ohne Bezug auf die konkrete Implementierung beschreiben und zu einem abstrakten Datentyp namens Map (oder: Abbildung) zusammenfassen.

Zweck einer solchen Map ist, eine Menge von Schlüssel-Werte-Paaren so zu verwalten, dass jederzeit ein neuer Wert mit einem Schlüssel assoziiert werden sowie der zu einem Schlüssel gehörende Wert nachgeschlagen werden kann. Um unsere Implementierung nicht mehr auf eine Abbildung von Wörtern auf Häufigkeiten (Typ: char * -> int) festzulegen, sondern für Daten beliebigen Typs offen zu halten, verwenden wir für Schlüssel und Werte nunmehr untypisierte Zeiger (also void *).

Im einzelnen soll unser Interface folgende Operationen umfassen:

Im Beispielverzeichnis zu diesem Blatt finden Sie zwei Dateien: die Headerdatei map.h, die im Wesentlichen obiges Map-Interface enthält, sowie wordfreq.c, welches dieses Interface anwendet, um analog zu Blatt 8 einen Worthäufigkeitszähler zu realisieren.

  1. (7 Punkte) Implementieren Sie in einer Datei treemap.c dieses Interface als unbalancierter Binärbaum, ganz analog zu Blatt 8. Die Hashfunktion benötigen Sie hier natürlich nicht. Funktionen wie createEntry(), die nicht speziell mit Binärbäumen zu tun haben, sollten Sie in einer weiteren Quelltextdatei (map.c) ablegen.
  2. (3 Punkte) Schreiben Sie ein Makefile. Es soll insbesondere für das Target wf-tree den Worthäufigkeitszähler mit der Objektdatei treemap.o compilieren.
  3. (Zusatzaufgabe, 5 Punkte) Implementieren Sie dasselbe Interface aus map.h als Hashtabelle in hashmap.c und erweitern Sie das Makefile entsprechend, so dass für das Target wf-hash die Objektdatei hashmap.o ohne treemap.o herangezogen wird. Auf diese Weise umgehen wir Namenskonflikte.

Die genaue Umsetzung einer Hashtabelle sei Ihnen überlassen. Sie können sich aber an folgenden Eckpunkten orientieren:

Viel Erfolg!



Fußnoten

... Funktionen1
Deklaration: typedef int (*Hasher)(void *) bzw. typedef int (*Comparator)(void *, void *)
... Inhalte2
In praktischen Anwendungen wäre die Freigabe der Inhalte möglicherweise nicht gewünscht.


Axel Blumenstock 2006-01-10