Datenstrukturen

Adjunto:

• List

1. dynamisch

   Nota:

   • 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

Adjunto:

• Array

1. Programmierung

   Adjunto:

   • 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

      Nota:

      • andere Datenstrukturen verwalten Objekte aus Klassen

Adjunto:

• Queue

1. FIFO

   Nota:

   • 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

Adjunto:

• Stack

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

   Nota:

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

Nota:

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

1. BinaryTree

   Adjunto:

   • Binär Baum
   1. BinarySearchTree

      Nota:

      • 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

      Adjunto:

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

         Nota:

         • 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

   Adjunto:

   • 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

Adjunto:

• Graphen

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

      Nota:

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

   Nota:

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

   Nota:

   • 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

   Nota:

   • Backtracking-Algorithmen

   Adjunto:

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

   Adjunto:

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