Lernmaterialien für Datenstrukturen an der Hochschule Ostwestfalen-Lippe

- verkettete (lineare) Liste

- einfach/doppelt verkettete Liste

• Spezielle Kennzeichnung erforderlich für

• Listenanfang (Anker)

• Listenende

• leere Liste 

• Ziel: Datenstruktur mit logarithmischem Aufwand für Suche, Einfügen und Löschen von Schlüsseln

• Prinzip: Verwendung sortierter verkettet gespeicherter Liste mit zusätzlichen Zeigern

• Elemente werden in Sortierordnung ihrer Schlüssel verkettet

• Führen mehrerer Verkettungen auf 2 oder mehreren Ebenen: Verkettung auf Ebene 0 verbindet alle Elemente; z. B. Verkettung auf Ebene 1 verbindet jedes zweite Element 

• Elemente = Knoten

• Knoten besitzt 0 – 2 Nachfolger

• Oberster Knoten = Wurzel

• Besitzt ein Knoten keinen Nachfolger = Blatt

• Darstellung beginnt immer mit der Wurzel

• Verbindungen zwischen Knoten = Kanten

• Kind / Eltern – Elemente

• Baumhöhe: Max(Kanten) bis zum untersten Blatt

• Tiefe: Anzahl Kanten bis zum gesuchten Knoten

• Geordnet:

• Linke Kind-Elemente ≤ Eltern-Element

• Rechte Kind-Elemente ≥ Eltern-Element 

1. Terminkalender

- Zugriff auf nächster Termin

- Einfügen neuer Termine

2. To-Do-Liste

- Priorisierung von Einträgen (Reihenfolge)

• int, double, char, boolean 

- lassen sich in Strukturen zusammenfassen

• Gekapselt Daten (verbirgt tatsächliche Repräsentation)

• Zugriff erfolgt nicht direkt auf der Variable, sondern über Funktionen (  Schnittstellen )

• Instanziierung eines ADTs

• Konkrete Ausprägung eines ADT mit konkreten Daten

• OOP: ADT = Klasse, Instanziierung = Objekt der Klasse

• Beispiel:

• Stack

• Queue

• Liste 

• LIFO-Prinzip (last in – first out)

• Zugriff nur auf den Anfang des Stapels

• Operationen:

• CREATE: Erzeuge leeren Stack

• PUSH(S, x): Fügt das Element x als oberstes Element von S ein

• POP(S): Löschen des Elementes, das als letztes in den Stack S eingefügt wurde

• TOP(S): Abfragen des Elementes, das als letztes in den Stack S eingefügt wurde

• EMPTY(S): Abfragen, ob der Stack S leer ist 

• Als Array oder Liste

• Max. Elementanzahl: n

• Einträge: A[1…n]

• Stackpointer top[A] verweist auf das zuletzt eingefügte Element

• Ist top[A] = 0, so ist der Stack leer

• A[top[A]] ist das oberste Element

• Achtung: Beim Array ist die Elementanzahl begrenzt; Bei einer Liste nicht. 

• FIFO (First-In-First-Out)

• Spezielle Form der Liste

• Zugriff auf 1. Element 

• Operationen:

• CREATE: Erzeugt die leere Schlange

• ENQUEUE (Q, x): Fügt das Element x am Ende der Schlange Q ein

• DEQUEUE (Q): Löschen des Elementes, das am längsten in der Schlange verweilt (erstes Element)

• FRONT (Q): Abfragen des ersten Elementes in der Schlange

• EMPTY (Q): Abfragen, ob die Schlange leer ist 

ABER: perfekte Skip-Listen zu aufwendig bezüglich Einfügungen und

• Löschvorgängen (vollständige Reorganisation erforderlich, Kosten O(n))