TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 24

(a) Gegeben ist eine Hashtabelle in Form eines Feldes $feld$ mit der festgelegten Größe $m$. Jedes Element $feld[j](j=0,....,m-1)$ dieses Feldes besteht aus folgenden Komponenten:

• $feld[j].key$ enthält den Schlüssel des Datensatzes;
• $feld[j].daten$ enthält die eigentlichen Daten;
• $feld[j].zustand$ enthält einen der folgenden Werte:
  • $besetzt:feld[j]$ enthält einen gültigen Datensatz;
  • $frei:feld[j]$ ist frei und war nie besetzt;
  • $wiederfrei:feld[j]$ war schon besetzt, ist aber wieder frei.

Schreiben Sie eine Prozedur in Pseudocode, welche diese Hashtabelle für die Verwendung mit $LinearemSondieren$ korrekt und vollständig initialisiert, aber auch keine überflüssigen Zuweisungen vornimmt.

(b) Nehmen Sie an, dass eine Hashfunktion $b(k)$ existiert, die aus einem Schlüssel $k$ einen Hashindex für die oben deklarierte Tabelle berechnet. Schreiben Sie eine Prozedur in Pseudocode, die den Datensatz mit dem Schlüssel $gesucht$ aus der Tabelle entfernt, falls er enthalten ist. Zur Behandlung von Kollisionen wird lineares Sondieren mit konstanter Schrittweite $c$ verwendet.

Beispiel (a)

Initalisierung
Feld := neues Feld(m);
für i = 0,.., m - 1 {
  feld.zustand := frei;
}

Beispiel (b)

 Entferne(feld, k, c)
 m := Länge von Feld;
 b := h(k);
 solange feld[b].zustand != frei {
   wenn feld[b].key = k {
     feld[b].zustand := wiederfrei;
     retourniere "Element gelöscht";
   }
   b := (b + c mod m);
 }
 retourniere "Element nicht gefunden";