Das bisherige Programm zur Verwaltung von Personendaten soll nun auf eine Hash-Organisation umgestellt werden.
Eine Hash-Funktion bestimmt aus einem Ordnungsbegriff (z.B. Name) die Position in einem Array, wo ein Verweis auf den zugehörigen Datensatz zu finden ist. Diese Funktion ist surjektiv, aber im allgemeinen nicht injektiv, d.h. zwei verschiedene Begriffe können auf dieselbe Positionsnummer abgebildet werden. In diesem Fall werden diese Datensätze, wie folgendem Bild zu entnehmen ist, einfach verkettet.
Zur Hash-Funktion:
Gegeben seien folgende Definitionsmodule:
DEFINITION MODULE Persons;
FROM StdIO IMPORT FILE;
TYPE
PersDat;
(* hidden type: pointer to a person's record*)
PROCEDURE WriteRec(f: FILE; pers: PersDat);
(* f - open stream for writing
* writes data with one blank as separator
*)
PROCEDURE ReadRec(f:FILE; VAR pers: PersDat):BOOLEAN;
(* f - open stream for reading !
* reads one record assuming whitespace as separator
* TRUE, if done, otherwise FALSE
*)
PROCEDURE hash(p: PersDat): CARDINAL;
(* RETURNS 0 on error, >0 otherwise *)
END Persons.
DEFINITION MODULE PersonsList;
(* based on module ``Persons'' *)
FROM StdIO IMPORT FILE;
IMPORT Persons;
CONST NumberEntries = 31;
TYPE
Range = [0 .. NumberEntries-1];
Element; (*hidden type*)
PersList = ARRAY Range OF Element;
HashProc = PROCEDURE(Persons.PersDat):CARDINAL;
PROCEDURE InitPersList(fromFile: FILE;
VAR persList: PersList;
hash: HashProc): BOOLEAN;
(* Procedure Persons.ReadRec is used
* result of hash is transformed into range ``Range''
* all data from file ``fromFile'' are stored in
* array ``persList'' according to the transformed hash-number
* returns FALSE, if error
*)
PROCEDURE WritePersList(to: FILE; persList: PersList);
(* the data of all stored persons
* are written to open stream ``to''
* ascending to the hash-number
* Procedure Persons.WriteRec is used
*)
END PersonsList.
Die Hash-Funktion soll aus dem Namen einer Person einen Index im Bereich Range berechnen. Dazu werden die Ordnungsnummern der einzelnen Buchstaben gewichtet mit 10-er Potenzen aufaddiert. Es handelt sich also um die Auswertung eines Polynoms, dessen Koeffizienten die Ordnungsnummern der Buchstaben sind und die einzelnen Glieder 10-er Potenzen sind - dies sollten Sie geschickt mit dem Horner-Schema machen:
hash(name) = ORD(name[0]);
hash(name) = hash(name)*10 + ORD(name[1]);
hash(name) = hash(name)*10 + ORD(name[2]);
...
hash(name) = hash(name)*10 + ORD(name[n]);
hash(name) = hash(name) MOD MaxIndex;
Implementieren Sie die zugehörigen Implementationsmodule sowie ein Hauptprogramm, das zum Test eine Menge von Daten aus einer als Argument übergebenen Datei in die Hash-Liste PersList einliest und danach in aufsteigender Reihenfolge der Hash-Werte wieder auf die Standardausgabe ausgibt. Viel Erfolg!