Datenstruktur Bedeutung, Erklärung und Definition.
In der Informatik ist eine Datenstruktur eine bestimmte Art Daten zu verwalten und miteinander zu verknĂŒpfen, um in geeigneter Weise auf diese zugreifen und diese manipulieren zu können. Datenstrukturen sind immer mit bestimmten Operationen verknĂŒpft, um eben diesen Zugriff und diese Manipulation zu ermöglichen.Die Definition von Datenstrukturen erfolgt im Allgemeinen durch die Angabe einer konkreten Spezifikation zur Datenhaltung und der dazu nötigen Operationen. Diese konkrete Spezifikation legt das allgemeine Verhalten der Operationen fest und abstrahiert damit von der konkreten Implementation der Datenstruktur.
Wird der Schwerpunkt der Betrachtung auf die konkrete Implementation der Operationen verschoben, so wird anstelle des Begriffs Datenstruktur auch hĂ€ufig von einem Abstrakten Datentypen gesprochen. Der Ăbergang von der Datenstruktur zu einem Abstrakten Datentyp ist dabei nicht klar definiert, sondern hĂ€ngt einzig von der Betrachtungsweise ab.
Von den meisten Datenstrukturen gibt es neben ihrer Grundform viele Spezialisierungen, die eigens fĂŒr die ErfĂŒllung einer bestimmten Aufgabe spezifiziert wurden. So sind beispielsweise B-BĂ€ume als Spezialisierung der Datenstruktur Baum besonders gut fĂŒr Implementationen von Datenbanken geeignet.
Bei vielen Algorithmen hÀngt der Ressourcenbedarf, also sowohl die benötigte Laufzeit als auch der Speicherplatzbedarf von der Verwendung geeigneter Datenstrukturen ab.
| Table of contents |
|
1.1 Array (Feld)
2 Literatur1.2 Liste 1.3 Stack 1.4 Warteschlange 1.5 Vorrangwarteschlange 1.6 Baum 1.7 Heap 1.8 Graph |
Grundlegende Datenstrukturen
Die folgenden Datenstrukturen sind in der Regel fĂŒr die klassische imperative Programmierung entwickelt und optimiert worden. Andere Programmierparadigmen wie die funktionale Programmierung können durchaus andere Datenstrukturen erfordern.
Array (Feld)
Das Array ist die einfachste verwendete Datenstruktur. Es speichert Objekte so, dass ein Zugriff auf die Objekte ĂŒber einen Index möglich wird, dieser entspricht einem Wert, der zu der Startadresse des Arrays im Speicher hinzuaddiert wird um die Adresse des Objektes zu errechnen. Die notwendigen Operationen sind das indizierte Speichern und Lesen, die auf jedes Objekt im Array direkt zugreifen können, ohne danach suchen zu mĂŒssen, da die Speicheradresse durch den Index bekannt ist. Im eindimensionalen Fall wird das Array hĂ€ufig als Vektor bezeichnet sowie es im zweidimensionalen Fall Tabelle genannt wird. Arrays sind aber keinesfalls nur auf zwei Dimensionen beschrĂ€nkt, sondern werden beliebig mehrdimensional verwendet. Wegen ihrer Einfachheit und grundlegenden Bedeutung bieten die allermeisten Programmiersprachen eine konkrete Umsetzung dieser Datenstruktur als zusammengesetzten Datentyp Array im Grundsprachumfang an.
Ein Sonderfall bildet das Assoziative Array, bei dem nicht ĂŒber einen numerischen Index, sondern ĂŒber einen SchlĂŒssel auf die gespeicherten Daten zugegriffen wird. Eine weitere Spezialisierung des assoziativen Arrays ist die Hashtabelle.
Die Liste ist eine Datenstruktur zur dynamischen Speicherung von beliebig vielen gleichen Objekten. Dabei beinhaltet jedes Listenelement als Besonderheit einen Verweis auf das nĂ€chste Element, wodurch die Gesamtheit der Objekte zu einer Verkettung von Objekten wird. Die zu einer Liste gehörenden Operationen sind relativ unspezifiziert. Sie werden oft in komplizierteren Datenstrukturen verwenden und statt ĂŒber Operationen wird dort aus EffizienzgrĂŒnden meist direkt auf ihre Elemente zugegriffen. Die in Programmbiblioteken angebotenen Listen sind in ihrer zugrunde liegenden Datenstruktur meist viel komplexer und stellen nicht selten gar keine echten Listen dar, geben sich nach auĂen aber als solche aus. Listen sind stets linear.
So ist bei BinÀrbÀumen die Anzahl der Kinder höchstens zwei und in balancierten BÀumen gilt zusÀtzlich, dass sich die Höhe des linken und rechten Teilbaums an jedem Knoten höchstens um eins unterscheiden.
Bei SuchbÀumen sind die Elemente in der Baumstruktur geordnet abgelegt, so dass man schnell Elemente im Baum finden kann. Man unterscheidet hier weiter in binÀre SuchbÀume mit AVL-BÀumen als balancierte Version und B-BÀumen sowie einer Variante, den B*-BÀumen. Spezialisierungen von B-BÀumen sind wiederum 2-3-4-BÀume, welche oft als Rot-Schwarz-BÀume implementiert werden.
BĂ€ume sind in ihrem Aufbau zwar mehrdimensional jedoch in der Verkettung der Objekte oft unidirektional. Die Verkettung der gespeicherte Objekte beginnt bei der Wurzel des Baums und von dort in Richtung der Knoten des Baums.
Diese Seite ist ein Artikel über Datenstruktur. Seite Versuche, zum von von Beschreibung über bereitzustellen Datenstruktur. Sie konnten Tatsachen über auch finden Datenstruktur. Erklärung von Datenstruktur.Liste
Stack
In einem so genannten Stack kann eine beliebige Anzahl von Objekten gespeichert, jedoch können die gespeicherten Objekte nur in umgekehrter Reihenfolge wieder gelesen werden. Dies entspricht dem LIFO-Prinzip.
FĂŒr die Definition und damit die Spezifikation des Stack ist es unerheblich, welche Objekte in ihm gespeichert werden. Zu einem Stack gehören zumindest die Operationen
Ein Stack wird gewöhnlich als Liste implementiert, kann aber auch ein Vektor sein.Warteschlange
In einer Warteschlange (engl. queue) kann eine beliebige Anzahl von Objekten gespeichert, jedoch können die gespeicherten Objekte nur in dergleichen Reihenfolge wieder gelesen werden, wie sie gespeichert wurden. Dies entspricht dem FIFO-Prinzip.
FĂŒr die Definition und damit die Spezifikation der Queue ist es unerheblich, welche Objekte in ihm gespeichert werden. Zu einer Queue gehören zumindest die Operationen
Eine Warteschlange wird gewöhnlich als Liste implementiert, kann auch aber auch ein Vektor sein.Vorrangwarteschlange
Eine Spezialisierung der Warteschlange ist die Vorrangwarteschlange, die auch PrioritĂ€tswarteschlange bzw. engl. Priority Queue genannt wird. Dabei wird vom FIFO-Prinzip abgewichen. Die DurchfĂŒhrung der enqueue Operation, die in diesem Fall auch insert Operation genannt wird, sortiert das Objekt gemÀà einer gegebenen PrioritĂ€t, die jedes Objekt mit sich fĂŒhrt, in die Vorrangwarteschlange ein. Die dequeue Operation liefert immer das Objekt mit der höchsten PrioritĂ€t. Vorrangwarteschlangen werden meist mit Heaps implementiert.Baum
BÀume sind spezielle Formen von Graphen in der Graphentheorie. Als Datenstruktur werden meist nur Out-Tree verwendet. Dabei können ausgehend von der Wurzel mehrere gleichartige Objekte miteinander verkettet werden, so dass die lineare Struktur der Liste aufgebrochen wird und eine Verzweigung stattfindet. Da BÀume zu den meist verwendeten Datenstrukturen in der Informatik gehören, gibt es viele Spezialisierungen.Heap
Der Heap vereint die Datenstruktur eines Baums mit den Operationen einer Vorrangwarteschlange. HĂ€ufig hat der Heap neben den minimal nötigen Operationen wie insert, remove und extractMin auch noch weitere Operationen wie merge oder changeKey. Je nach Reihenfolge der PrioritĂ€t in der Vorrangwarteschlange wird ein Min-Heap oder ein Max-Heap verwendet. Weitere Spezialisierungen des Heap sind der BinĂ€re Heap, der Binomial-Heap und der Fibonacci-Heap. Heaps werden meistens ĂŒber BĂ€ume aufgebaut.Graph
Ein Graph ermöglicht es als Datenstruktur die UnidirektionalitĂ€t der VerknĂŒpfung zu ĂŒberwinden. Die Operationen sind auch hier das EinfĂŒgen, Löschen und Finden eines Objekts. Die bekanntesten ReprĂ€sentation von Graphen im Computer sind die Adjazenzmatrix, die Inzidenzmatrix und Adjazenzliste.Literatur