[UE ALGO 2 Homepage] Ü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:

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


Last modified: hoermanseder@fim.uni-linz.ac.at 98-10-21