5  Elementare Datenstrukturen

Literatur: Kapitel 11 [CLR90].

Inhalt Stacks und Queues ·verzeigerte Listen ·Bäume ·Implementierungsmöglichkeiten

• "`dynamische Mengen"': veränderbar
• viele verschiedene Varianten
• Unterschieden nach
  • Zugriffsmöglichkeiten (Schnittstelle)
  • Repräsentierung
• zwei Arten von Zugriffen
  • modifizend
  • lesend (queries)
• Beispiele für Zugriffe:
  • Suchen
  • Einfügen, Löschen
  • Minimum, Maximum bestimmen
  • Vorläufer, Nachfolger bestimmen
  • ...
• Beispiele für Repräsentierungen:
  • (einfach o. doppelt) verzeigerte Listen
  • Bäume unterschiedlichster Art (balanciert, Heaps ...)
  • Hashstrukturen

• Stack/Queue: dynamische (Multi-)Mengen mit spezifischer Strategie zum Einfügen und Löschen:
  • Stack: Lifo: last-in, first-out
    • Push: Einfügen
    • Pop: Entfernen
  • Queue: Fifo: first-in, first-out
    • Enqueue: Einfügen
    • Dequeue: Entfernen

• Implementiert als Array 1... n
• dynamischer Inhalt: Elemente S[1], ..., S[top]
• Komplexität: O(1)

Stack-empty(S)
  if top == 0 then return true else false;

Push(S,x)
  top    := top + 1;
  S[top] := x;

Pop(S)
  if Stack-empty(S)
  then error "underflow"
  else top  := top  -1;
       return S[top+1];

• Array als Ringpuffer (circular buffer)
• zwei Pointer: head and tail: erste benutzte und erste freie
• Komplexität: O(1)

Enqueue(Q,x) =
  Q[tail] := x;
  if tail == length(Q)
     then tail := 1       // start again with 1
     else tail := tail + 1;


Dequeue(Q) =
  x := Q[head]
  if head == length(Q)
     then head := 1        // start again with 1
     else head := head + 1
  return x;
  

• lineare Datenstuktur
• keine wahlfreier Zugriff wie beim Array, sonder über Zeiger
• Verschiedene Varianten:
  • einfach verzeigert: nur prev
  • doppelt verzeigert: prev und next
  • zirkulär

List-search(L,k)     // k: key  
  x  := head;
  while  x != nil and x.key != k
     do  x := next(x);

  return x;

List-insert(L,x)            // vorne Einfuegen
  next(x) := head;
  if head != nil then prev(head) := x
     head := x;
  prev(x) := nil;

List-delete(L,x)
  if prev(x) != nil
     then next(prev(x)) := next(x)
     else          head := next(x)
  if next(x) != nil
     then prev(next(x)) := prev(x);