Algorithmen und Datenstrukturen in C: Elementare Datenstrukturen
Aus Wikibooks
Elementare Datenstrukturen stellen die Grundlage für Algorithmen dar. In ihnen werden Daten abgespeichert.
Inhaltsverzeichnis |
[Bearbeiten] Bestandteile
Datenstrukturen bestehen aus einer Menge von Daten, bei denen man jeweils den Schlüssel und den eigentlichen Datensatz unterscheidet. Über den Schlüssel kann man den jeweiligen Datensatz identifizieren. Außerdem dient er als Kriterium für Sortier- und Suchalgorithmen. Der eigentliche Datensatz kann hingegen beliebig groß und von einem beliebigen Typ sein. So wäre es zum Beispiel möglich Datensätze, von denen einer ein Bild und der andere eine Audiodatei enthält zu sortieren, da ja nicht nach dem eigentlichen Inhalt, sondern nach dem Schlüssel sortiert wird.
[Bearbeiten] Einige typische Operationen
Es gibt einige Operationen, die mit jeder Datenstruktur möglich sind. Die konkrete Umsetzung in einer Programmiersprache ist aber teilweise grundlegend anders, wodurch es zu sehr unterschiedlichen Laufzeiten kommt.
[Bearbeiten] I. Anfrageoperationen
SUCHE(D, s): Sucht den Schlüssel s in der Datenstruktur D, liefert einen Zeiger auf das entsprechende Element zurück, bzw. einen leeren Zeiger, wenn das Element nicht existiert.
MINIMUM(D): Liefert einen Zeiger auf das Element mit dem kleinsten Schlüssel in der Datenmenge D zurück.
MAXIMUM(D): Liefert einen Zeiger auf das Element mit dem größten Schlüssel in der Datenmenge D zurück.
SUCC(D, s): Liefert einen Zeiger auf das Element zurück, dessen Schlüssel der Nachfolger (Successor), also der nächstgrößere, von s ist.
PRED(D, s): Liefert einen Zeiger auf das Element zurück, dessen Schlüssel der Vorgänger(Predecessor), also der nächstkleinere, von s ist.
[Bearbeiten] II. Modifikationsoperationen
INSERT(D, x) Fügt das Element auf das der Zeiger x zeigt in die Datenstruktur D ein.
DELETE(D, x) Löscht das Element auf das der Zeiger x zeigt aus der Datenstruktur D.
[Bearbeiten] statische und dynamische Datenstrukturen
Der Unterschied zwischen statischen und dynamischen Datenstrukturen besteht darin, dass die Größe von dynamischen Datenstrukturen während der Laufzeit geändert werden kann. Das ist bei statischen Datenstrukturen nicht der Fall.
Alle in diesem Buch vorkommenen Datenstrukturen sind dynamisch mit Ausnahme des Feldes bzw. Arrays.
<< Inhaltsverzeichnis | Verkettete Listen >>
