Algorithmen und Datenstrukturen 2 WS 1999/2000

5. Übung - abzugeben am 23. 11. 1999 in Ihrer Übungsgruppe

5 Programm-Dokumentation + Test + Modifikationen + Tests

(* Divisionrestverfahren, lineare Kollisionsstrategie mit Schrittweite 1 *)
DEFINITION OF MODULE Hash;
  CONST TABLEN*= 7;              (* Tabellenlänge, Primzahl!, bitte ändern Sie ... *)
  TYPE  KeyT*= INTEGER;          (* Typ des Schlüssels *)
        DataT*=ARRAY 11 OF CHAR; (* Datenwerte (Beispiel) *)

  PROCEDURE Init*();
     (* Initialisierung der Hashtabelle *)
  PROCEDURE Dump*();
     (* Ausgane der Hashtabelle (zu Testzwecken) *)
  PROCEDURE Del*(k:KeyT);
     (* Löschen des Eintrags mit Schlüsel k, so vorhanden *)
  PROCEDURE Put*(k:KeyT; d:DataT);
     (* Einfügen/Update des Eintrages mit Schlüssel k mit/auf Daten d *)
  PROCEDURE Get*(k:KeyT; VAR found:BOOLEAN; VAR d:DataT);
     (* Suchen des Wertes mit Schlüssel k in der Tabelle.
        Nach Aufruf zeigt found an, ob der Eintrag vorhanden ist.
        Rückgabe der Daten des gefundenen Eintrages in d. *)
END Hash.

Eine Version 0 des Modules Hash finden Sie hier: [Modul Hash (Version 0)]

Dokumentation:
Leider hat der Schreiber des Modules auf einen Großteil der Dokumentation vergessen. Dokumentieren Sie daher das Programm (quasi als Nachweis, daß Sie es gelesen/verstanden haben). Insbesondere die Prozeduren HFind und Put verdienen dabei Ihre volle Aufmerksamkeit. Überlegen Sie genau, was diese Prozeduren machen.

Test + (eventuell notwendige) Fehlerkorrektur:
Kontrollieren und testen Sie das bestehende Programm. Falls Fehler auftreten, machen Sie bitte die entsprechenden Änderungen und dokumentieren Sie auch, warum Sie die jeweilige Modifikation durchgeführt haben.

Test 2:
Rechnen Sie auch die folgenden Operationen "per Hand" aus. Dokumentieren Sie das Ergebnis (handschriftlich) in der folgenden Liste. Führen Sie dann die Testfälle mit dem Programm durch und vergleichen Sie.

Operation	Wert	Hausadr.	c	durchlaufene Sondierungsfolge	Adresse	Anmerkungen
Initialisierung (1, Init)
Wert einfügen (2, Put)	3		1
Wert einfügen (2, Put)	17		1
Wert einfügen (2, Put)	26		1
Wert einfügen (2, Put)	6		1
Wert einfügen (2, Put)	19		1
Wert einfügen (2, Put)	18		1
Tabelle ausgeben (5, Dump)
Löschen (3, Del)	17		1
Löschen (3, Del)	19		1
Tabelle ausgeben (5, Dump)
Abfrage (4, Get)	18		1
Abfrage (4, Get)	17		1
Wert einfügen (2, Put)	18		1
Wert einfügen (2, Put)	10		1
Wert einfügen (2, Put)	8		1
Wert einfügen (2, Put)	19		1
Tabelle ausgeben (5, Dump)
Wert einfügen (2, Put)	22		1			Überlauf ABBRUCH!

(Für die einfache Bedienung des Testtreibers sind die Operationscodes in der Tabelle mit angegeben.)

Tabelle bei Dump Nummer 1:

Index:	(0)	(1)	(2)	(3)	(4)	(5)	(6)
Schlüssel k/key:
Status:

Tabelle bei Dump Nummer 2:

Index:	(0)	(1)	(2)	(3)	(4)	(5)	(6)
Schlüssel k/key:
Status:

Tabelle bei Dump Nummer 3:

Index:	(0)	(1)	(2)	(3)	(4)	(5)	(6)
Schlüssel k/key:
Status:

Programmmodifikation:
Modifizieren Sie das Modul Hash so, daß es statt linearer Kollisionsstrategie mittels Doppelhash nach der Quotientenmethode arbeitet. Dokumentieren Sie die Änderungen.

Test:
Testen Sie das modifizierte Programm.

Test 2 des modifizierten Programmes:
Rechnen Sie auch die folgenden Operationen "per Hand" aus. Dokumentieren Sie das Ergebnis (handschriftlich) in der folgenden Liste. Führen Sie dann die Testfälle mit dem Programm durch und vergleichen Sie.

Operation	Wert	Hausadr.	c	durchlaufene Sondierungsfolge	Adresse	Anmerkungen
Initialisierung (1, Init)
Wert einfügen (2, Put)	3
Wert einfügen (2, Put)	17
Wert einfügen (2, Put)	26
Wert einfügen (2, Put)	6
Wert einfügen (2, Put)	19
Wert einfügen (2, Put)	18
Tabelle ausgeben (5, Dump)
Löschen (3, Del)	17
Löschen (3, Del)	19
Tabelle ausgeben (5, Dump)
Abfrage (4, Get)	18
Abfrage (4, Get)	17
Wert einfügen (2, Put)	18
Wert einfügen (2, Put)	10
Wert einfügen (2, Put)	8
Wert einfügen (2, Put)	19
Tabelle ausgeben (5, Dump)
Wert einfügen (2, Put)	22					Überlauf ABBRUCH!

(Für die einfache Bedienung des Testtreibers sind die Operationscodes in der Tabelle mit angegeben.)

Tabelle bei Dump Nummer 1:

Index:	(0)	(1)	(2)	(3)	(4)	(5)	(6)
Schlüssel k/key:
Status:

Tabelle bei Dump Nummer 2:

Index:	(0)	(1)	(2)	(3)	(4)	(5)	(6)
Schlüssel k/key:
Status:

Tabelle bei Dump Nummer 3:

Index:	(0)	(1)	(2)	(3)	(4)	(5)	(6)
Schlüssel k/key:
Status: