Datenstrukturen

Anlagen:

• List

1. dynamisch

   Anmerkungen:

   • eine Liste kann dynamische erweitert werden. Man muss vor dem anlegen einer Liste noch nicht genau wissen, wie viele Speicherplätze (Listeneinträge) man braucht
   1. Vorteil?
2. Programmierung
   1. Methoden
      1. einfügen
         1. Objekte
            1. am Ende der Liste = append(object)
            2. hinter dem aktuellen Element = insert(object)
         2. Listen
            1. am Ende der Liste = concat(list)
         3. Inhalte
            1. am aktuellen Element = setContent(objekt)
      2. auslesen
         1. Inhaltsobjekt des aktuellen Elements = getContent()
      3. entfernen = remove()
      4. Initialisierne
   2. durchlaufen

Anlagen:

• Array

1. Programmierung

   Anlagen:

   • Array
   1. Initialisierung
   2. Durchlaufen
      1. Eindimensionaler Array
      2. Zweidimensionaler Array
   3. Methoden
2. Statisch
   1. festgelegte Plätze
      1. genauer Speicherplatz
3. Vorteil
   1. kann Datentypen verwalten

      Anmerkungen:

      • andere Datenstrukturen verwalten Objekte aus Klassen

Anlagen:

• Queue

1. FIFO

   Anmerkungen:

   • First In First Out: das Element, das zuerst eingefügt wurde wird auch zuerst entfernt
2. Programmierung
   1. Initialisieren
   2. Methoden
      1. einfügen - enqueue(object)
      2. löschen - dequeue()
      3. auslesen - front()
   3. Durchlaufen

Anlagen:

• Stack

1. Programmierung
   1. Initialisieren
   2. Methoden
      1. einfügen - push(object)
      2. entfernen - pop()
      3. auslesen - top()
   3. Implementierung
2. LIFO

   Anmerkungen:

   • Last In First Out das zuletz eingefügte Objekt wird als erstes Ausgegeben

Anmerkungen:

• Bäume können neben Objekten auch Datentypen verwalten und ebenfalls von anderen Datenstrukturen verwaltet werden

1. BinaryTree

   Anlagen:

   • Binär Baum
   1. BinarySearchTree

      Anmerkungen:

      • Wird ein element aus dem Suchbaum entfernt (und kein einzelner Teilbaum kann nachrücken) wird sein Nachfolger entweder das größte Element des linken Teilbaums oder das kleinste Element des rechten Teilbaums

      Anlagen:

      • Binärer Suchbaum
      1. Suche erfolgt binär (rekursiv)
      2. Das Einfügen von Content erfolg rekursiv
      3. Verwendung des Interfaces ComparableContent

         Anmerkungen:

         • Die Klasse der Objekts, die mit dem Suchbaum verwaltet werden sollen, muss von ComparableContent erben und die Methoden isGreater(...), isLess(...) und isEqual(..) überschreiben
      4. Jeder Binäre Suchbaum besteht aus einer Wurzel und aus einem linken und einem rechten Teilbaum
      5. Baumstruktur vom Grad 2
   2. Baumstruktur vom Grad 2
      1. Jeder Knoten hat mind. keinen und maximal zwei Nachfolger
   3. Jeder Binärbaum besteht aus einer Wurzel und aus einem rechten und einem linken Teilbaum
2. Traversierung

   Anlagen:

   • Traversierung und Spannbäume
   1. Pre-Order (W-R-L)
   2. In-Order (R-W-L)
   3. Post-Order (R-L-W)
3. Knoten
   1. Grad des Knotens: Anzahl seiner Nachfolger
   2. Wurzel
      1. Die Zählung der Ebenen beginnt an der Wurzel mit 0
      2. Ist die Wurzel eines Baumes leer, ist der Baum leer
   3. Blatt
      1. keine Nachfolger
4. Pfade können niemals eine Kreis bilden
5. Jeder Baum besteht aus einer Wurzel und aus einem rechten und einem linken Teilbaum

Anlagen:

• Graphen

1. Kanten
   1. Unidirektional
      1. gerichteter Graph
   2. Bidirektional

      Anmerkungen:

      • Die Graphen der Abiturklasse sind immer unidirektional
      1. ungerichteter Graph
   3. Gewicht
2. Knoten

   Anmerkungen:

   • Der Grad eines Knotens ist die Anzahl seiner Nachbarknoten
3. Darstellung
   1. Adjazenzliste
   2. Adjazenzmatrix
4. vollständig/zusammenhängend

   Anmerkungen:

   • ein Graph ist vollständig, wenn zwischen zwei Knoten je eine Kante besteht
   • ein Graph ist zusammenhängend, wenn zwischen je zwei Knoten ein Weg existiert
5. Durchsuchen

   Anmerkungen:

   • Backtracking-Algorithmen

   Anlagen:

   • minimale Spannbäume und ihre Algorithmen
   1. Tiefensuche
   2. Breitensuche
6. kürzester Weg

   Anlagen:

   • minimale Spannbäume und ihre Algorithmen
   1. Dijkstra
   2. Spannbaum
   3. Kruskal
   4. Prim