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

Schreiben Sie eine Prozedur in detailliertem Pseudocode, die in eine gegebene Hashtabelle T ein neues Element e mit dem Schlüssel e.key mit Verkettung der Überläufer einfügt - dabei soll jede Liste in der Hashtabelle aufsteigend nach den Schlüsseln der Elemente sortiert werden.

Fügen Sie mit Ihrer Prozedur die Elemente <1,6,7,25,21,11> in dieser Reihenfolge in eine Anfangs leere der Größe sieben ein. Verwenden sie die Hashfunktion $h_{\text{1}}(k)$ = k mod 7

Pseudocode

Einfügen(var T,e)
i := h(e.key);
if (T[i] = NULL) {
  T[i] := e;
  e.next := NULL;
} andernfalls {
  np := T[i];
  prev := NULL;
  während (np.key < e.key UND np.next != NULL) {
    prev := np;
    np := np.next;
  }
  wenn (prev = NULL) {
    wenn (e.key > np.key) {
      T[i].next := e;
      e.next := NULL;
    } andernfalls {
      e.next := T[i];
      T[i] := e;
    }
  } andernfalls {
    prev.next := e;
    e.next := np;
  }
}

Beispielfolge

• ) "1" wird an der Stelle 1 eingefügt.
• ) "6" wird an der Stelle 6 eingefügt.
• ) "7" wird an der Stelle 0 eingefügt.
• ) "25" wird an der Stelle 4 eingefügt.
• ) "21" wird an der Stelle 0 eingefügt, da 0 != NULL, wird "21" hinter "7" eingefügt. (Da "21" > "7")
• ) "11" wird an der Stelle 4 eingefügt, da 4 != NULL und "11" < "25", wird "11" vor "25" eingefügt.

Die leeren Kästchen symbolisieren jeweils den Speicherplatz für die Zeiger auf die Elemente. Die Pfeile symbolisieren die Zeiger. Der rote und der grüne Pfeil sollen den sonderfall bei dem Element 11 anzeigen.