Datenstrukturen

Anexos:

• List

1. dynamisch

   Anotações:

   • 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

Anexos:

• Array

1. Programmierung

   Anexos:

   • 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

      Anotações:

      • andere Datenstrukturen verwalten Objekte aus Klassen

Anexos:

• Queue

1. FIFO

   Anotações:

   • 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

Anexos:

• Stack

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

   Anotações:

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

Anotações:

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

1. BinaryTree

   Anexos:

   • Binär Baum
   1. BinarySearchTree

      Anotações:

      • 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

      Anexos:

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

         Anotações:

         • 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

   Anexos:

   • 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

Anexos:

• Graphen

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

      Anotações:

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

   Anotações:

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

   Anotações:

   • 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

   Anotações:

   • Backtracking-Algorithmen

   Anexos:

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

   Anexos:

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