Datenstruktur

Grundlegende Datenstrukturen

Auflistung

Die einfachste Art der Datenstruktur ist ein lineares Array. Auch als eindimensionales Array bekannt. Ein Array enthält mehrere Werte desselben Typs (Integer, Floats, String usw.). Der Zugriff auf Elemente innerhalb des Arrays ist sehr schnell. Ein Array hat normalerweise eine feste Größe. Nachdem die Größe des Arrays zu Beginn festgelegt wurde, ist es möglicherweise nicht mehr möglich, die Größe des Arrays zu erhöhen, ohne ein neues größeres Array zu erstellen und alle Werte in das neue Array zu kopieren. In der Informatik ist eine Array-Datenstruktur oder einfach ein Array eine Datenstruktur, die aus einer Sammlung von Elementen (Werten oder Variablen) besteht, von denen jedes durch mindestens einen Array-Index oder Schlüssel identifiziert wird. Ein Array wird so gespeichert, dass die Position jedes Elements aus seinem Indextupel durch eine mathematische Formel berechnet werden kann.

Zum Beispiel kann ein Array von 10 ganzzahligen Variablen mit den Indizes 0 bis 9 als 10 Worte an den Speicheradressen 2000, 2004, 2008, 2036 gespeichert werden, so dass das Element mit Index i die Adresse 2000 + 4 × i hat.

Da das mathematische Konzept einer Matrix als ein zweidimensionales Gitter dargestellt werden kann, werden zweidimensionale Arrays manchmal auch als Matrizen bezeichnet. In einigen Fällen wird der Begriff "Vektor" in der Informatik verwendet, um sich auf ein Array zu beziehen, obwohl Tupel anstelle von Vektoren das korrektere mathematische Äquivalent sind. Arrays werden oft verwendet, um Tabellen zu implementieren, insbesondere Nachschlagetabellen; das Wort Tabelle wird manchmal als Synonym für Array verwendet.

Arrays gehören zu den ältesten und wichtigsten Datenstrukturen und werden von fast jedem Programm verwendet. Sie können auch zur Implementierung vieler anderer Datenstrukturen, wie Listen und Zeichenketten, verwendet werden. Sie nutzen die Adressierungslogik von Computern effektiv aus. In den meisten modernen Computern und vielen externen Speichergeräten ist der Speicher ein eindimensionales Array von Wörtern, dessen Indizes ihre Adressen sind. Prozessoren, insbesondere Vektorprozessoren, sind oft für Array-Operationen optimiert.

Arrays sind nützlich, da die Elementindizes zur Laufzeit berechnet werden können. Diese Funktion ermöglicht es unter anderem, mit einer einzigen iterativen Anweisung beliebig viele Elemente eines Arrays zu verarbeiten. Aus diesem Grund müssen die Elemente einer Array-Datenstruktur die gleiche Größe haben und sollten die gleiche Datendarstellung verwenden. Der Satz gültiger Index-Tupel und die Adressen der Elemente (und damit die Elementadressierungsformel) sind normalerweise, aber nicht immer, während der Verwendung des Arrays festgelegt.

Der Begriff "Array" wird oft für den Array-Datentyp verwendet, eine Art von Datentyp, der von den meisten höheren Programmiersprachen bereitgestellt wird und aus einer Sammlung von Werten oder Variablen besteht, die durch einen oder mehrere zur Laufzeit berechnete Indizes ausgewählt werden können. Array-Typen werden oft durch Array-Strukturen implementiert; in einigen Sprachen können sie jedoch auch durch Hashtabellen, verknüpfte Listen, Suchbäume oder andere Datenstrukturen implementiert werden.

Verknüpfte Liste

Eine verknüpfte Datenstruktur ist ein Satz von Informationen/Daten, die durch Verweise miteinander verbunden sind. Die Daten werden oft als Knoten bezeichnet. Die Verweise werden oft als Links oder Pointer bezeichnet. Von hier an werden die Begriffe Knoten und Zeiger für diese Konzepte verwendet.

In verknüpften Datenstrukturen werden Zeiger nur dereferenziert oder auf Gleichheit verglichen. Daher unterscheiden sich verknüpfte Datenstrukturen von Arrays, bei denen Zeiger addiert und subtrahiert werden müssen.

Verknüpfte Listen, Suchbäume und Ausdrucksbäume sind allesamt verknüpfte Datenstrukturen. Sie sind auch wichtig für Algorithmen wie topologisches Sortieren und Set-Union-Find.

Stapel

Ein Stapel ist eine grundlegende Datenstruktur, die logischerweise als lineare Struktur gedacht werden kann, die durch einen realen physischen Stapel oder Stapel repräsentiert wird, eine Struktur, bei der das Einfügen und Löschen von Elementen an einem Ende, dem so genannten oberen Ende des Stapels, stattfindet. Das Grundkonzept kann veranschaulicht werden, indem man sich Ihren Datensatz als einen Stapel von Tellern oder Büchern vorstellt, bei dem man nur den obersten Gegenstand vom Stapel nehmen kann, um Dinge von ihm zu entfernen. Diese Struktur wird in der gesamten Programmierung verwendet.

Die grundlegende Implementierung eines Stacks wird auch als "Last In First Out"-Struktur bezeichnet; es gibt jedoch verschiedene Varianten von Stack-Implementierungen.

Es gibt grundsätzlich drei Operationen, die auf Stapeln durchgeführt werden können. Sie sind:

• Einfügen ("Schieben") eines Artikels in einen Stapel
• Löschen ("Popping") eines Elements aus dem Stapel
• Anzeige des Inhalts des obersten Elements des Stapels ("Peeking")

Warteschlange

Eine Warteschlange ist ein abstrakter Datentyp oder eine lineare Datenstruktur, bei der das erste Element von einem Ende (dem "Schwanz") eingefügt wird und die Löschung eines vorhandenen Elements vom anderen Ende (dem "Kopf") aus erfolgt. Eine Warteschlange ist eine "First In First Out"-Struktur. "First In First Out" bedeutet, dass Elemente, die als erste in die Warteschlange gestellt werden, als erste herauskommen und Elemente, die als letzte in die Warteschlange gestellt werden, als letzte herauskommen. Ein Beispiel für eine Warteschlange sind Warteschlangen von Personen. Die erste Person in der Schlange geht zuerst, und die letzte Person in der Schlange geht zuletzt.

Der Prozess des Hinzufügens eines Elements zu einer Warteschlange wird als "Enqueuing" und der Prozess des Entfernens eines Elements aus einer Warteschlange als "Dequeuing" bezeichnet.

Grafik

Ein Graph ist ein abstrakter Datentyp, der die Konzepte von Graphen und Hypergraphen aus der Mathematik implementieren soll.

Eine Graphen-Datenstruktur besteht aus einer endlichen (und möglicherweise veränderbaren) Menge geordneter Paare, Kanten oder Bögen genannt, von bestimmten Entitäten, Knoten oder Eckpunkten genannt. Wie in der Mathematik wird gesagt, dass eine Kante (x,y) auf x zeigt oder von x nach y geht. Die Knoten können Teil der Graphenstruktur sein oder externe Entitäten, die durch ganzzahlige Indizes oder Referenzen dargestellt werden. Eine Graphen-Datenstruktur kann auch jeder Kante einen Kantenwert zuordnen, z.B. eine symbolische Bezeichnung oder ein numerisches Attribut.

Baum

Der Baum ist eine der leistungsstärksten fortgeschrittenen Datenstrukturen. Sie taucht häufig in fortgeschrittenen Fächern wie Künstliche Intelligenz (KI) und Design auf. Überraschenderweise ist der Baum in einer viel grundlegenderen Anwendung wichtig - der Führung eines effizienten Index.

Wenn ein Baum verwendet wird, besteht eine hohe Wahrscheinlichkeit, dass ein Index verwendet wird. Die einfachste Art eines Index ist eine sortierte Liste von Schlüsselfeldern. Ein Baum hat normalerweise eine definierte Struktur. Im Falle eines Binärbaums können Sie mit Hilfe einer binären Suche jedes beliebige Element finden, ohne jedes Element ansehen zu müssen.

Der Baumdatentyp ist ein Graphentyp, was bedeutet, dass viele Algorithmen, die für das Durchlaufen eines Graphen entwickelt wurden, auch mit einem Baum funktionieren. Die Algorithmen können jedoch sehr ähnlich sein und müssen einen dedizierten Startknoten haben, d.h. den Knoten, der keine anderen Knoten mit ihm verbindet.

Das Problem mit einer einfachen, geordneten Liste tritt auf, wenn Sie anfangen, neue Einträge hinzuzufügen und die Liste sortiert halten müssen - dies kann relativ effizient erfolgen, erfordert aber einige Änderungen. Außerdem ist ein linearer Index nicht leicht gemeinsam zu nutzen, da der gesamte Index "gesperrt" werden muss, wenn ein Benutzer ihn bearbeitet, während ein "Zweig" eines Baumes gesperrt werden kann, so dass die anderen Zweige von anderen Benutzern bearbeitet werden können (da sie nicht betroffen werden können).

Hash-Tabelle

Eine Hashtabelle ist ein Array, bei dem jeder Index auf eine verknüpfte Liste zeigt, die auf einem Hashwert basiert. Ein Hash-Wert ist ein Wert, der durch eine Hash-Funktion bestimmt wird. Eine Hash-Funktion bestimmt einen eindeutigen Wert auf der Grundlage der Daten, die sie speichert. Dies ermöglicht den Zugriff auf die Daten in konstanter Zeit, da der Computer immer weiß, wo er suchen muss.

Jeder Knoten zeigt auf einen anderen Knoten.