Algorithmen und Datenstrukturen in C/ Datenstrukturen

Elementare Datenstrukturen stellen die Grundlage für Algorithmen dar. In ihnen werden Daten abgespeichert.

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.

Funktionen

Es gibt einige Funktionen, 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.

• 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.

• 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.

statische Datenstrukturen

Einer statische Datenstruktur wird während der Programmierung eine feste Größe zugewiesen. Diese lässt sich zur Laufzeit des Programmes nicht mehr ändern. Benötigt man trotzdem eine größere Struktur, muss man eine neue erstellen, und die Daten vollständig in diese neue Datenstruktur schreiben.

Die einzige statische Datenstruktur in diesem Buch ist das Feld.

dynamische Datenstrukturen

Dynamische Datenstrukturen können in ihrer Größe während der Laufzeit verändert werden.

In diesem Buch werden unter anderem verkettete Listen, Bäume und Graphen behandelt.