Datenstruktur - Data structure

Eine als Hashtabelle bekannte Datenstruktur .

In der Informatik , eine Datenstruktur ist eine Datenorganisation, Management und Speicherformat , das einen effizienten Zugriff und Modifikation ermöglicht. Genauer gesagt ist eine Datenstruktur eine Sammlung von Datenwerten, den Beziehungen zwischen ihnen und den Funktionen oder Operationen, die auf die Daten angewendet werden können, dh es handelt sich um eine algebraische Struktur über Daten .

Verwendungszweck

Datenstrukturen dienen als Grundlage für abstrakte Datentypen (ADT). Der ADT definiert die logische Form des Datentyps. Die Datenstruktur implementiert die physische Form des Datentyps.

Verschiedene Arten von Datenstrukturen eignen sich für verschiedene Arten von Anwendungen, und einige sind auf bestimmte Aufgaben hoch spezialisiert. Beispielsweise verwenden relationale Datenbanken häufig B-Baum- Indizes zum Abrufen von Daten, während Compiler- Implementierungen normalerweise Hash-Tabellen verwenden , um Bezeichner nachzuschlagen.

Datenstrukturen bieten ein Mittel zur effizienten Verwaltung großer Datenmengen für Anwendungen wie große Datenbanken und Internet-Indexierungsdienste. Normalerweise sind effiziente Datenstrukturen der Schlüssel zum Entwerfen effizienter Algorithmen . Einige formale Designmethoden und Programmiersprachen betonen eher Datenstrukturen als Algorithmen als den wichtigsten Organisationsfaktor beim Softwaredesign. Datenstrukturen können verwendet werden, um das Speichern und Abrufen von Informationen zu organisieren, die sowohl im Hauptspeicher als auch im Sekundärspeicher gespeichert sind.

Implementierung

Datenstrukturen basieren im Allgemeinen auf der Fähigkeit eines Computers , Daten an jedem Ort in seinem Speicher abzurufen und zu speichern, der durch einen Zeiger angegeben wird – eine Bitfolge, die eine Speicheradresse darstellt , die selbst im Speicher gespeichert und vom Programm manipuliert werden kann. Somit basieren die Array- und Datensatz- Datenstrukturen auf der Berechnung der Adressen von Datenelementen mit arithmetischen Operationen , während die verknüpften Datenstrukturen auf dem Speichern von Adressen von Datenelementen innerhalb der Struktur selbst basieren.

Die Implementierung einer Datenstruktur erfordert normalerweise das Schreiben einer Reihe von Prozeduren , die Instanzen dieser Struktur erstellen und manipulieren. Die Effizienz einer Datenstruktur kann nicht getrennt von diesen Operationen analysiert werden. Diese Beobachtung motiviert das theoretische Konzept eines abstrakten Datentyps , einer Datenstruktur, die indirekt durch die Operationen, die darauf ausgeführt werden können, und die mathematischen Eigenschaften dieser Operationen (einschließlich ihres Platz- und Zeitaufwands) definiert wird.

Beispiele

Python 3. Die Standardtyphierarchie.png

Es gibt zahlreiche Arten von Datenstrukturen, die im Allgemeinen auf einfacheren primitiven Datentypen aufbauen :

  • Ein Array ist eine Anzahl von Elementen in einer bestimmten Reihenfolge, normalerweise alle vom gleichen Typ (je nach Sprache können einzelne Elemente entweder alle den gleichen Typ haben oder fast jeden Typ haben). Auf Elemente wird über einen ganzzahligen Index zugegriffen, um anzugeben, welches Element erforderlich ist. Typische Implementierungen weisen zusammenhängende Speicherwörter für die Elemente von Arrays zu (aber dies ist nicht immer eine Notwendigkeit). Arrays können eine feste Länge haben oder in der Größe veränderbar sein.
  • Eine verknüpfte Liste (auch nur Liste genannt ) ist eine lineare Sammlung von Datenelementen jeglichen Typs, die als Knoten bezeichnet werden, wobei jeder Knoten selbst einen Wert hat und auf den nächsten Knoten in der verknüpften Liste zeigt. Der Hauptvorteil einer verknüpften Liste gegenüber einem Array besteht darin, dass Werte immer effizient eingefügt und entfernt werden können, ohne den Rest der Liste zu verschieben. Bestimmte andere Operationen, wie der wahlfreie Zugriff auf ein bestimmtes Element, sind jedoch auf Listen langsamer als auf Arrays.
  • Ein Datensatz (auch Tupel oder struct genannt ) ist eine aggregierte Datenstruktur . Ein Datensatz ist ein Wert, der andere Werte enthält, normalerweise in fester Anzahl und Reihenfolge und normalerweise nach Namen indiziert. Die Elemente von Datensätzen werden normalerweise Felder oder Member genannt .
  • Eine Union ist eine Datenstruktur, die angibt, welcher von mehreren zulässigen primitiven Typen in ihren Instanzen gespeichert werden darf, zB float oder long integer . Vergleichen Sie mit einem Datensatz , der so definiert werden könnte, dass er einen Gleitkommawert und eine ganze Zahl enthält; wohingegen in einer Union immer nur ein Wert vorhanden ist. Es wird genügend Speicherplatz zugewiesen, um den breitesten Member-Datentyp aufzunehmen.
  • Eine getaggte Union (auch Variant- , Variant-Datensatz , diskriminierte Union oder disjunkte Union genannt ) enthält ein zusätzliches Feld, das ihren aktuellen Typ angibt, um die Typsicherheit zu erhöhen.
  • Ein Objekt ist eine Datenstruktur, die wie ein Datensatz Datenfelder enthält, sowie verschiedene Methoden, die mit den Dateninhalten arbeiten. Ein Objekt ist eine speicherinterne Instanz einer Klasse aus einer Taxonomie . Im Kontext der objektorientierten Programmierung werden Datensätze als einfache alte Datenstrukturen bezeichnet , um sie von Objekten zu unterscheiden.

Darüber hinaus sind Graphen und binäre Bäume andere häufig verwendete Datenstrukturen.

Sprachunterstützung

Den meisten Assemblersprachen und einigen Low-Level-Sprachen wie BCPL (Basic Combined Programming Language) fehlt die integrierte Unterstützung für Datenstrukturen. Auf der anderen Seite haben viele höhere Programmiersprachen und einige höhere Assemblersprachen wie MASM eine spezielle Syntax oder andere integrierte Unterstützung für bestimmte Datenstrukturen wie Datensätze und Arrays. Beispielsweise unterstützen die Sprachen C (ein direkter Nachkomme von BCPL) und Pascal zusätzlich zu Vektoren (eindimensionalen Arrays ) und mehrdimensionalen Arrays Strukturen bzw. Datensätze .

Die meisten Programmiersprachen verfügen über eine Art Bibliotheksmechanismus , der es ermöglicht, Datenstrukturimplementierungen von verschiedenen Programmen wiederzuverwenden. Moderne Sprachen werden normalerweise mit Standardbibliotheken geliefert, die die gängigsten Datenstrukturen implementieren. Beispiele sind die C++ Standard Template Library , das Java Collections Framework und das Microsoft .NET Framework .

Moderne Sprachen unterstützen im Allgemeinen auch die modulare Programmierung , die Trennung zwischen der Schnittstelle eines Bibliotheksmoduls und seiner Implementierung. Einige bieten undurchsichtige Datentypen , die es Clients ermöglichen, Implementierungsdetails auszublenden. Objektorientierte Programmiersprachen wie C++ , Java und Smalltalk verwenden zu diesem Zweck typischerweise Klassen .

Viele bekannte Datenstrukturen haben gleichzeitige Versionen, die es mehreren Rechen-Threads ermöglichen, gleichzeitig auf eine einzige konkrete Instanz einer Datenstruktur zuzugreifen.

Siehe auch

Verweise

Literaturverzeichnis

Weiterlesen

Externe Links