MODULE Hash; IMPORT Out; CONST TABLEN*= 7; (* Tabellenlaenge, Primzahl!, bitte aendern Sie ... *) EMPTY= 0; (* fuer Status: Element von Anfang an leer *) FULL= 1; (* fuer Status: Element enthaelt einen Wert *) DEL= 2; (* fuer Status: Element wurde geloescht, key beinhaltet letzten Wert *) TEST= TRUE; (* Schalter fuer Testausgaben direkt aus dem Modul *) TYPE KeyT*=INTEGER; (* Typ des Schluessels *) DataT*=ARRAY 11 OF CHAR; (* Datenwerte (Beispiel) *) EntryT=RECORD (* Eintrag in der Hashtabelle *) status: SHORTINT; (* Status des Eintrages: EMPTY/FULL/DELeted*) key: KeyT; (* Schluessel im Eintrag *) data: DataT; (* Daten im Eintrag *) END; (*record*) VAR table: ARRAY TABLEN OF EntryT; (* Hashtabelle *) PROCEDURE Init*(); VAR pos: INTEGER; BEGIN (*Init*) FOR pos:=0 TO LEN(table)-1 DO table[pos].status:=EMPTY END (*for*) END Init; PROCEDURE Dump*(); VAR pos: INTEGER; BEGIN (*Dump*) Out.Ln; Out.String(" Pos Stat Key = Data"); FOR pos:=0 TO LEN(table)-1 DO Out.Ln; Out.Int(pos, 6); CASE table[pos].status OF EMPTY: Out.String(" Empty "); |FULL: Out.String(" Full "); Out.Int(table[pos].key,8); Out.String(" = "); Out.String(table[pos].data); |DEL: Out.String(" Del "); Out.Int(table[pos].key,8); END (*case*) END (*for*) END Dump; (* Input: k (Schluessel, der gesucht werden soll) Output: ipos zeigt die Position an, an welcher der Schluessel k (moeglichst "nahe der Hausadresse") eingefuegt werden koennte. Es wird aber nicht ueberprueft, ob an dieser Stelle ipos auch noch der Platz fuer einen neuen Wert ist. found (wurde Schluessel k gefunden) wenn found nach Aufruf auf TRUE ist, dann zeigt pos auf den gefundenen Eintrag. pos kann natuerlich gleich ipos sein, falls sich vorher in der Sondierungsfolge keine geloeschten Elemente befinden. Ueber den boolschen Wert TEST laesst sich steuern, ob die Prozedur Testausgaben auf dem Bildschirm machen soll. *) PROCEDURE HFind(k:KeyT; VAR found:BOOLEAN; VAR pos, ipos: INTEGER); VAR home, try: INTEGER; BEGIN (*HFind*) home:=k MOD LEN(table); pos:=home; IF TEST THEN Out.F(" ( home=# ", pos) END; (*if*) try:=0; WHILE (try