Datenstruktur
Eine Datenstruktur ist eine bestimmte Art Daten zur Organisation in einem Informatiksystem anzuordnen.Bei vielen Algorithmen kann die asymptotische Laufzeit durch Verwendung bestimmter Datenstrukturen verbessert werden, z.B. bei Dijkstra's Algorithmus durch die Verwendung eines Fibonacci-Heaps. Allerdings ist diese Datenstruktur so kompliziert, dass die Laufzeit in der Theorie zwar besser wäre, praktisch gesehen der Implementierungsaufwand sowie die in das Debugging zu investierende Arbeitszeit die — relativ geringe — tatsächliche Beschleunigung des Algorithmus kaum lohnt.
In der Wikipedia werden die folgenden Datenstrukturen beschrieben:
- Arrays (auch Felder, Elemente gleichen Datentyps))
- eindimensional (Vektoren)
- zweidimensional (Tabellen)
- mehrdimensional
- Bäume
- Graph (bzw. die zugrundeliegende Datenstruktur Adjazenzliste oder Adjazenzmatrix)
- Hashtabelle (auch assoziatives Array)
- Heapss (en: Haufen, Halde)
- Binärer Heap (eindimensionales Array)
- Fibonacci-Heap
- Min-Max-Heap
- Deap
- Listen, meist verkettet
- Stack
- Verbunde, (Records, Units, Elemente unterschiedlichen Datentyps)
- Warteschlange (auch Schlange, Queue)
- Priority Queue (normalerweise mit Hilfe von Heaps implementiert)
- Priority Queue (normalerweise mit Hilfe von Heaps implementiert)
Literatur