Datenstruktur

aus www.iwiki.de, der freien Wissensdatenbank

In der Informatik werden Datenstrukturen eingesetzt, um Daten auf einfache Art und Weise zu manipulieren und zu verwalten. Zu den Vorteilen des Einsatzes von Datenstrukturen gehören unter anderem die Möglichkeit komplexe reale und abstrakte Sachverhalte abbilden zu können, sowie eine effizientere Speicherung von großen Datenmengen einhergehend mit schnelleren Suchmöglichkeiten.

Inhaltsverzeichnis

1 Begriffe
- 1.1 elementare Datenstrukturen
- 1.2 komplexe Datenstrukturen
  - 1.2.1 statische komplexe Datenstrukturen
  - 1.2.2 dynamische komplexe Datenstrukturen
2 wesentliche Datenstrukturen
3 Siehe auch
4 Literatur
5 Weblinks

[bearbeiten]

Begriffe

Datenstruktur: Eine Datenstruktur setzt sich zusammen aus einem Datentyp und den darauf definierten Operationen.

Datentyp: Der Datentyp beschreibt den Wertebereich der Datenstruktur.; Ein Beispiel dafür ist der Datentyp Integer der im Allgemeinen (32 Bit, vorzeichenbehaftet) den Wertebereich von −2.147.483.648 bis 2.147.483.647 beschreibt.

Operation: Eine Operation besteht aus einer Verknüpfung einer festgelegten Anzahl an Operanden des Wertebereichs zu einem Ergebnis, das ebenfalls Element des Wertebereiches ist.; Ein Beispiel aus der Mathematik dafür ist eine Funktion f mit den Argumenten (Operanden) x und y, beides Elemente der natürlichen Zahlen und einer Verknüpfung x+y: $\mathsf{f(x,y)=x+y}$ .; Ein Beispiel aus der Programmierung ist der Methodenaufruf concat(string a, string b).

[bearbeiten]

elementare Datenstrukturen

Elementare Datenstrukturen können genau einen Wert beinhalten. Eine Variable eines Standartdatentyps (Integer, Boolean, Char, ...) ist eine elementare Datenstruktur.

[bearbeiten]

komplexe Datenstrukturen

Komplexe Datenstrukturen können mehrere Werte aufnehmen und unterschiedliche Strukturen ausbilden. Teilweise werden sie von der Programmiersprache angeboten, teilweise werden sie durch den Programmierer definiert. Zu unterscheiden sind hier statische und dynamische Datenstrukturen.

[bearbeiten]

statische komplexe Datenstrukturen

Die Anzahl der Werte, die in dieser Struktur abgelegt werden können, ist fest. Die Größe der Datenstruktur kann im allgemeinen während der Laufzeit eines Programms nicht mehr geändert werden, der Inhalt jedoch schon. Der Zugriff auf den Inhalt erfolgt direkt. Beispiele für statische komplexe Datenstrukturen sind Structs und Arrays.

Zur Veranschaulichung dient ein Java-Array. Bei der Initialisierung wird dem Array eine feste Größe zugewiesen: myArray = int[10]; Der Zugriff auf die einzelnen Werte erfolgt direkt durch Angabe der Position: inhalt = myArray[2];

[bearbeiten]

dynamische komplexe Datenstrukturen

Die Größe beziehungsweise die Anzahl der Werte ist bei dynamischen Strukturen änderbar. Der Zugriff auf die Werte erfolgt indirekt durch Operationen.

Der Inhalt eines Listenelements lässt sich beispielsweise durch den Aufruf myList.nextElement.getValue(); erreichen.

[bearbeiten]

wesentliche Datenstrukturen

Felder: Enthalten n Werte, der Zugriff erfolgt direkt. Java-Arrays im Speziellem werden in der Vorlesung "Programmieren 1" behandelt.

Zeiger: Der Zeiger gehört zu den elementaren Datentypen. Der Wertebereich erstreckt sich über alle realen Hauptspeicheradressen.

Liste: Die Liste gehört zu den dynamischen Datenstrukturen. Sie besteht aus einzelnen Elementen, die gleich einer Kette miteinander verbunden sind. Zur Laufzeit können Listenelemente beliebig verändert, entfernt und eingefügt werden.

Baum: Der Baum gehört zu den dynamischen Datenstrukturen. Ein Baumelement hat genau ein Vorgängerelement und zwei oder mehr Nachfolgerelemente. Elemente können beliebig verändert, entfernt und hinzugefügt werden.

[bearbeiten]

Siehe auch

[bearbeiten]

Literatur

Bernd Breutmann: data and algorithms. Carl-Hanser-Verl., Leipzig 2001, ISBN 3-446-21591-3
Michael Goodrich, Roberto Tamassia: Data Structures and Algorithms in Java 2nd Edition. John Wiley and Sons, New York 2001, ISBN 0-471-38367-8

[bearbeiten]