Dies ist eine alte Version des Dokuments!
Datenstrukturen
1. Was sind Datenstrukturen?
Datenstrukturen sind spezielle Konzepte zur Organisation und Speicherung von Daten in einem Computerprogramm. Sie bestimmen, wie Daten angeordnet und verwaltet werden, um effiziente Zugriffe und Operationen zu ermöglichen.
Zweck von Datenstrukturen:
- Effiziente Speicherung und Verwaltung von Daten
- Schneller Zugriff und Bearbeitung
- Grundlage für die Implementierung von Algorithmen
Unterschied zu Datentypen:
- Datentypen beschreiben die Art einzelner Werte (z. B. Ganzzahl, Zeichenkette).
- Datenstrukturen beschreiben die Anordnung und Beziehung mehrerer Werte (z. B. Liste, Baum).
2. Datenstrukturen
Es gibt verschiedene Arten von Datenstrukturen, die je nach Anwendungsfall eingesetzt werden. Hier eine Übersicht der wichtigsten:
2.1 Liste (Array) und Verkettete Liste
Liste (Array):
- Geordnete Sammlung von Elementen, die über Indizes angesprochen werden.
- Feste Größe (bei klassischen Arrays).
- Direkter Zugriff auf Elemente.
Beispiel:
[3, 7, 9, 12]
Verkettete Liste:
- Besteht aus Knoten (Nodes), die jeweils Daten und einen Verweis auf den nächsten Knoten enthalten.
- Dynamische Größe.
- Kein direkter Zugriff per Index.
Visualisierung:
[Head] → [Daten | Next] → [Daten | Next] → NULL
2.2 Stack (Stapel) und Queue (Warteschlange)
Stack (Stapel):
- Prinzip: LIFO (Last In – First Out).
- Letztes eingefügtes Element wird zuerst entfernt.
- Operationen: `push` (einfügen), `pop` (entfernen).
Beispiel:
Stapel von Tellern: Der zuletzt oben gelegte Teller wird zuerst genommen.
Queue (Warteschlange):
- Prinzip: FIFO (First In – First Out).
- Erstes eingefügtes Element wird zuerst entfernt.
- Operationen: `enqueue` (einfügen), `dequeue` (entfernen).
Beispiel:
Warteschlange im Supermarkt: Wer zuerst kommt, wird zuerst bedient.
2.3 Bäume und Graphen
Bäume:
- Hierarchische Struktur mit Wurzel (Root) und Knoten (Nodes).
- Jeder Knoten kann mehrere Kinder haben.
- Beispiel: Binärbaum (max. 2 Kinder pro Knoten).
Visualisierung:
Root
/ \
Node1 Node2
Graphen:
- Sammlung von Knoten (Vertices) und Kanten (Edges), die die Knoten verbinden.
- Kann gerichtet oder ungerichtet sein.
- Beispiel: Straßennetz, soziale Netzwerke.
Visualisierung:
(A) --- (B) | | (C) --- (D)