Datenstrukturen

Attachments:

• List

1. dynamisch

   Annotations:

   • 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

Attachments:

• Array

1. Programmierung

   Attachments:

   • 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

      Annotations:

      • andere Datenstrukturen verwalten Objekte aus Klassen

Attachments:

• Queue

1. FIFO

   Annotations:

   • 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

Attachments:

• Stack

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

   Annotations:

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

Annotations:

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

1. BinaryTree

   Attachments:

   • Binär Baum
   1. BinarySearchTree

      Annotations:

      • 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

      Attachments:

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

         Annotations:

         • 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

   Attachments:

   • 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

Attachments:

• Graphen

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

      Annotations:

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

   Annotations:

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

   Annotations:

   • 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

   Annotations:

   • Backtracking-Algorithmen

   Attachments:

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

   Attachments:

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