Rekursive Datenstrukturen

Rekursive oder dynamische Datenstrukturen bestehen aus verketteten Objekten, den Knoten. Diese Datenstrukturen sind dynamisch, weil zur Laufzeit des Programmes neue Knoten erzeugt und verkettet werden. Die so erzeugten Datenstrukturen können dynamisch wachsen und schrumpfen. Solange Speicher vorhanden ist, können neue Elemente erzeugt und eingefügt werden.

  1. Lineare Liste
    • verkettete Folge von Elementen eines Datentyps
    • mögliche Operationen:
      1. Erzeugen()
      2. EinfuegenElement(inhalt)
      3. AnhaengenElement(inhalt)
      4. LoeschenElement()
      5. GeheErstes()
      6. GeheLetztes()
      7. HoleEintrag(inhalt)
      8. SchreibeEintrag(inhalt)
      9. GeheNaechstes()
      10. ListeLeer()
      11. ListenEnde()
      Bei Positionen 1 bis 9 handelt es sich um Methoden ohne Rückgabewert.
      Die Methoden 10 und 11 geben einen Wahrheitswert zurück.
      Die angegebenen Operationen entsprechen dem in Thüringen für das Zentralabitur vorausgesetzten ADT Liste. Sie wurden lediglich an die Java-Syntax angepasst.
      Angenommen, man hat mit dem Befehl
      adtListe TestListe = new adtListe;
      eine neue Testliste erzeugt, dann würde der Befehl
      TestListe.EinfuegenElement(inhalt)
      ein neues Element in die Liste einfügen.
    Lineare Liste
  2. Ringliste
    • verkettete Folge von Elementen eines Datentyps
    • zusätzliche Verknüpfung von "letzten Element" wieder zurück zum ersten Element
    • mögliche Operationen:
      1. Erzeugen()
      2. EinfuegenElement(inhalt)
      3. LoeschenElement()
      4. GeheErstes()
      5. HoleEintrag(inhalt)
      6. SchreibeEintrag(inhalt)
      7. GeheNaechstes()
      8. ListeLeer()
    Ringliste

    Bsp.: Problem des Josephus
  3. Stapel (Keller, Stack)
    • verkettete Folge von Elementen eines Datentyps
    • mögliche Operationen:
      1. Erzeugen eines Stapels
      2. Einfügen eines Elementes am Ende - push
      3. Entnehmen eines Elementes am Ende - pop
      4. Test, ob Stapel leer ist
    • Prinzip: LIFO = Last In First Out

      Bsp.: Tellerstapel, Stapel vom Zementsäcken, ...
    Stapel
  4. Schlange (Queue)
    • verkettete Folge von Elementen eines Datentyps
    • mögliche Operationen:
      1. Erzeugen einer Schlange
      2. Einfügen eines Elementes am Ende
      3. Entnehmen eines Elementes am Anfang
      4. Test, ob die Schlange leer ist
    • Prinzip: FIFO = First In First Out

      Bsp.: Autobahnstau (einspurig), Druckerwarteschlange, ...
    Schlange