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

Aus VoWi
Zur Navigation springen Zur Suche springen

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 = k mod 7

Pseudocode[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

  • ) "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.