|
Übungen zu Algorithmen und Datenstrukturen 2 WS 98/99 |
4. Übung - abzugeben am 3. 11. 1998 in Ihrer Übungsgruppe
4.a Programm
Schreiben Sie ein Programm gemäß folgender Interface Definition:
DEFINITION OF MODULE Hash;
CONST N*=..; (*Größe einer Hashtabelle, z.B. 11, 31, ... *)
TYPE KeyT*=LONGINT;
DataT*=.......;
TableT*=POINTER TO ARRAY N OF EntryT;
PROCEDURE Init*(VAR t:TableT; VAR err:BOOLEAN);
PROCEDURE CleanUp*(VAR t:TableT);
PROCEDURE Dump*(t:TableT);
PROCEDURE Get*(t:TableT; k:KeyT; VAR f:BOOLEAN; VAR d:DataT);
PROCEDURE Put*(VAR t:TableT; k:KeyT; d:DataT);
END Hash.
Anmerkungen:
- Divisionrestverfahren, lineare Kollisionsstrategie
- Besprechung der geforderten Funktionen erfolgt in der Übung
- Sicherheitsabfragen nicht vergessen (HALT, ASSERT)
4.b Programm
Fügen Sie zu obigem Programm die folgenden Prozeduren hinzu:
PROCEDURE Del*(VAR t:TableT; k:KeyT);
PROCEDURE Analyse*(t:TableT; VAR ..............);
Die folgenden Überlegungen zu Analyse sind als Anregung zu verstehen.
Bitte überlegen Sie selbst, welche Informationen
über eine Hashtabelle von Interesse sein könnten.
Beispiele.: Anzahl der belegten Elemente, Anzahl der als
gelöscht markierten Elemente, durchschnittliche Länge von
"Kollisionsketten", .........)
Da Sie dabei für das Löschen von Elementen die Datenstruktur
für die Hashtabelle und die Implementierung der unter a
angeführten Prozeduren ändern müssen, genügt für die Abgabe
von a und b eine vollständige Gesamt-Implementierung.
4.c Diskussion
- Überlegen Sie, was man machen kann, wenn der
Schlüsseltyp nicht gleich INTEGER oder LONGINT (wie in
dem einfachen zu programmierenden Beispiel) ist.
Hinweis:
Faltung, Basistransformation, ...
- Überlegen Sie ferner, welche Probleme auftreten, wenn
Sie aus einer Hashtabelle mit z.B. linearer
Kollisionsstrategie Elemente
"mirnichts-dirnichts" löschen. Welche
Maßnahme könnten Sie sich als Abhilfe vorstellen?
- Machen Sie sich auch den Begriff Belegungsfaktor und die
Bedeutung von Reorganisationsläufen bewußt.
Last modified:
hoermanseder@fim.uni-linz.ac.at 98-10-21