2 - Datenstrukturen

• Gruppenbildung (1 Byte = 8 Bits, …) und Speicheradresse

  • Problem: große Zahl an Elementen eines Datentyps effizient zu verwalten

Datentypen

• z. Bsp. Zeichen (char), Ganzzahlen (integer)

Datenstrukturen

• Container, die endliche Zahl an Elementen eines Datentyps effizient verwalten

• typische Operationen

  • über Elemene iterieren

  • Element einfügen, löschen

• Wahl der passenden Datenstruktur entscheidend für Performance eines Algorithmus

• Graph

• Hashtabelle

• Vorrangwarteschlange

• Halde

• Feld

• verkettete Liste

• Stapel

• Warteschlange

• Baum

• Feld

  • Dynamische Felder

  • Mehrdimensionale Felder

  • Zirkuläre Felder

• sequenzielle Datenstruktur, bei der Reihenfolge der Elemente durch Speicherort festegelgt ist

  • direkter Zugriff über ganzzahligen Index

  • Einfügen und Löschen ineffizient, weil alle nachfolgenden Elemente verschoben werden müssen

  • Felder haben feste (maximale) Größe

  • Felder variabler Größe: Verfahren zur dynamischen Allokation von Speicher erforderlich

• Größe passt sich an Anzahl der Elemente an

• Problem: bei Speicherallokation müssen alle Elemente vom “alten” in das neue (größere bzw. kleinere) Feld kopiert werden

• Strategien zur Vermeidung häufiger Reallokation

• dienen Speicherung von Tabellen/Matrizen

• Zugriff über mehrere Indizes

• Ablage im Speicher sequenziell

• Speicherbereich bei Erreichen des Endes am Anfang fortgesetzt

• Position des ersten Elements entspricht nicht zwangsläufig erstem Speicherblock

• schnelles Einfügen & Entfernen am Anfang und Ende des Feldes

• Eignung für Warteschlangen mit fester, maximaler Größe

• für Implementierung: Indices des erste und letzten Elements gespeichert

• sequenzielle Datenstruktur, bei der Reihenfolge der Elemente durch Zeiger auf jeweilig nächstes Element festgelegt ist

• Elemente können an beliebigen Orten im Speicher abgelegt sein

• keine feste Größe - beliebig erweiterbar

• Einfügen und Löschen nach gegebenem Elemnt sehr effizient

• direkter Zugriff auf Element ineffizeint, da evtl. komplette Liste durchlaufen werden muss

Array:

• hintereinander im Speicher

verkettete Liste:

• an beliebigen Orten im Speicher

• doppelt verkettete Liste

• zirkuläre Liste

• Skip-Listen

• sequenzielle Datenstruktur zur Umsetzung des LIFO-Prinzips (last in first out)

• Element kann nur am oberen Ende hinzugefügt werden

• nur oberstes Element kann entfernt werden

• direkter Zugriff nur auf oberstes Element

• wenn maximale Größe bekannt: Implementierung als Array geeignet (Hinzufügen und Entfernen am Ende des Arrays)

• Implementierung als verkettete Liste flexibler

• Eingabelogik für Anwendung von Operationen

• Erst Operanden eingegeben, dann darauf anzuwendende Operator

• sequenzielle Datenstruktur zur Umsetzung des FIFO-Prinzips (first in first out)

• Hinzufügen von Elementen nur am Anfang

• Entnehmen von Elementen nur am Ende

• wenn maximale Größe bekannt: Implementierung als Array geeignet (in Form von Ringspeicher mit Zeigern auf Anfang und Ende der Warteschlange)

• Implementierung al verkettete Liste flexibler

• hierarchische Datenstruktur

• Knoten = Elemente

• Kanten = Verbindungen zwischen zwei Knoten

• Wurzel = einziges Element ohne Vorgänger

• Blätter = Knoten ohne Nachfolger

• Innere Knoten = Knoten mit Vorgänger und Nachfolger

• Pfad = Folge unterschiedlicher, durch Kanten verbundener Knoten

• zusamenhängend und nicht-zyklisch

  • genau ein Pfad zwischen Wurzel und jedem Knoten

• ansonsten: kein Baum, sonder Datenstruktur

• maximal zwei Kinder pro Knoten (linkes und rechtes Kind)

• am häufigsten verwendete Form eines Baumes

• voll

  • alle Knoten haben zwei oder keine Kinder

• vollständig

  • jede Ebene außer der letzten vollständig befüllt

  • letzte Ebene von links nach rechts befüllt

• perfekt

  • alle inneren Knoten haben genau zwei Kinder

  • alle Blätter auf gleicher Ebene

• Level-Order-Traversierung

  1. Besuche die Wurzel

  2. Durchlaufe alle Knoten der Ebene darunter von links nach rechts

  3. Wiederhole Schritt 2 für die nächste Ebene bis zum Baumende

• Preorder-Traversierung

  1. Besuche die Wurzel

  2. Durchlaufe den linken Teilbaum

  3. Durchlaufe den rechten Teilbaum

• Postorder-Traversierung

  1. Durchlaufe den linken Teilbaum

  2. Durchlaufe den rechten Teilbaum

  3. Besuche die Wurzel

• Inorder-Traversierung

  1. Durchlaufe den linken Teilbaum

  2. Besuche die Wurzel

  3. Durchlaufe den rechten Teilbaum

• Verfahren der Tiefensuche lassen sich elegant rekursiv implementieren

• Breitensuche nicht rekursiv implementierbar, aber z. Bsp. mit Warteschlange