Datenstrukturen

Datenstrukturen

1. Lineare Datenstrukturen

   • List
     • List
     • dynamisch
       • 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
       • Vorteil?
     • Programmierung
       • Methoden
         • einfügen
           • Objekte
             • am Ende der Liste = append(object)
             • hinter dem aktuellen Element = insert(object)
           • Listen
             • am Ende der Liste = concat(list)
           • Inhalte
             • am aktuellen Element = setContent(objekt)
         • auslesen
           • Inhaltsobjekt des aktuellen Elements = getContent()
         • entfernen = remove()
         • Initialisierne
       • durchlaufen
   • Array
     • Array
     • Programmierung
       • Array
       • Initialisierung
       • Durchlaufen
         • Eindimensionaler Array
         • Zweidimensionaler Array
       • Methoden
     • Statisch
       • festgelegte Plätze
         • genauer Speicherplatz
     • Vorteil
       • kann Datentypen verwalten
         • andere Datenstrukturen verwalten Objekte aus Klassen
   • Queue
     • Queue
     • FIFO
       • First In First Out: das Element, das zuerst eingefügt wurde wird auch zuerst entfernt
     • Programmierung
       • Initialisieren
       • Methoden
         • einfügen - enqueue(object)
         • löschen - dequeue()
         • auslesen - front()
       • Durchlaufen
   • Stack
     • Stack
     • Programmierung
       • Initialisieren
       • Methoden
         • einfügen - push(object)
         • entfernen - pop()
         • auslesen - top()
       • Implementierung
     • LIFO
       • Last In First Out das zuletz eingefügte Objekt wird als erstes Ausgegeben

2. Nicht-lieneare Datenstrukturen

   • Tree
     • Bäume können neben Objekten auch Datentypen verwalten und ebenfalls von anderen Datenstrukturen verwaltet werden
     • BinaryTree
       • Binär Baum
       • BinarySearchTree
         • 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
         • Binärer Suchbaum
         • Suche erfolgt binär (rekursiv)
         • Das Einfügen von Content erfolg rekursiv
         • Verwendung des Interfaces ComparableContent
           • Die Klasse der Objekts, die mit dem Suchbaum verwaltet werden sollen, muss von ComparableContent erben und die Methoden isGreater(...), isLess(...) und isEqual(..) überschreiben
         • Jeder Binäre Suchbaum besteht aus einer Wurzel und aus einem linken und einem rechten Teilbaum
         • Baumstruktur vom Grad 2
       • Baumstruktur vom Grad 2
         • Jeder Knoten hat mind. keinen und maximal zwei Nachfolger
       • Jeder Binärbaum besteht aus einer Wurzel und aus einem rechten und einem linken Teilbaum
     • Traversierung
       • Traversierung und Spannbäume
       • Pre-Order (W-R-L)
       • In-Order (R-W-L)
       • Post-Order (R-L-W)
     • Knoten
       • Grad des Knotens: Anzahl seiner Nachfolger
       • Wurzel
         • Die Zählung der Ebenen beginnt an der Wurzel mit 0
         • Ist die Wurzel eines Baumes leer, ist der Baum leer
       • Blatt
         • keine Nachfolger
     • Pfade können niemals eine Kreis bilden
     • Jeder Baum besteht aus einer Wurzel und aus einem rechten und einem linken Teilbaum
   • Graphen
     • Graphen
     • Kanten
       • Unidirektional
         • gerichteter Graph
       • Bidirektional
         • Die Graphen der Abiturklasse sind immer unidirektional
         • ungerichteter Graph
       • Gewicht
     • Knoten
       • Der Grad eines Knotens ist die Anzahl seiner Nachbarknoten
     • Darstellung
       • Adjazenzliste
       • Adjazenzmatrix
     • vollständig/zusammenhängend
       • 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
     • Durchsuchen
       • Backtracking-Algorithmen
       • minimale Spannbäume und ihre Algorithmen
       • Tiefensuche
       • Breitensuche
     • kürzester Weg
       • minimale Spannbäume und ihre Algorithmen
       • Dijkstra
       • Spannbaum
       • Kruskal
       • Prim