WikiDer > Datenstruktur

Datastructuur

EIN Datenstruktur ist in der Informatik eine Art und Weise, wie die Elemente (in diesem Zusammenhang auch Komponenten, Teile oder Elemente genannt) eines Verbunds Variable kohärent. Die Struktur bestimmt die Art und Weise, wie die Elemente ausgewählt werden können und damit, wie und mit welcher Effizienz Daten gespeichert, modifiziert und abgerufen werden können. Darüber hinaus können Datenstrukturen zu komplexeren Datenstrukturen kombiniert werden.

Arten von Datenstrukturen

Es können mindestens zwei Klassen von Datenstrukturen unterschieden werden.

  1. Aufzeichnung Eine Zusammenstellung von Feldern, die mit einem eindeutigen Namen angesprochen werden können. Beispiele hierfür sind Datensätze in Pascal und Strukturen in C. Diese Aufzeichnungen sind bereits beim Schreiben des Programms definiert.
  2. Container EIN Container ist eine Datenstruktur, die eine variable Anzahl von Objekten enthält. Der Zugriff auf diese Objekte ist je nach Containertyp unterschiedlich.

Einige moderne Skriptsprachen, wie z Javascript, Python, perl oder Rubin, verwenden nicht mehr die erste Art zugunsten anderer Konstruktionen wie a assoziatives Array. Das hat alles damit zu tun, dass Computer immer schneller werden und die statische Aufzeichnung leicht durch eine dynamische Konstruktion ersetzt werden kann. Früher hätte dies die Maschine unnötig verlangsamt und unnötigen Speicher verschwendet. Das heißt jedoch nicht, dass diese Lösungen von vornherein besser sind.

Container

Behälter auf mindestens eine Weise in zwei Gruppen unterteilt werden können. Nämlich die konzeptionellen Container (eine abstrakte Datenstruktur) und die Implementierungen dieser Konzepte. Die Unterscheidung zwischen diesen beiden Gruppen ist nicht in allen Fällen gleich klar, da einige Konzepte nur eine Implementierung haben. In diesen Fällen sind die beiden Konzepte synonym.

Konzept

Beispiele für abstrakte Container sind:

  • Array — Schnellzugriff über eine Nummer. Größe ist vorgegeben, Größenanpassung ist teuer. Ein zweidimensionales Array (auf das über zwei Zahlen zugegriffen wird) wird als Matrix bezeichnet.
  • aufführen — Zugriff nur über vorheriges oder nächstes Element. Einfügen oder Subtrahieren ist billig.
  • Warteschlange (oder Warteschlange oder fifo) — Greifen Sie nur auf das zuerst hinzugefügte Element zu.
  • Stapel (oder lifo) — Greifen Sie nur auf das zuletzt hinzugefügte Element zu.
  • Assoziatives Array (oder Wörterbuch oder Karte) — Elemente können nach einem eindeutigen Schlüssel gesucht werden. Dies sieht aus wie ein Wörterbuch, daher der Name Wörterbuch. Der Zugriff auf ein Element ist normalerweise ziemlich schnell, aber viel langsamer als auf ein Array. Die Entfernung ist in der Regel günstig. Fügen Sie etwas teurer, aber vernünftig hinzu. Dies hängt alles von der gewählten Implementierung ab.
  • Sammlung (oder einstellen, gespenstisch.) — Enthält nur eindeutige Suchschlüssel.
  • Tasche — Enthält nicht eindeutige Suchschlüssel.

Implementierung

Beispiele für Container-Implementierungen sind:

  • Array — Wird für Array-, Queue-, Stack-Implementierung verwendet. Ein Bit-Array wird auch für die Sammlungsimplementierung verwendet, weist jedoch im Vergleich zu den anderen Implementierungen Einschränkungen auf.
  • Baumstruktur (einschließlich Haufen) — Wird für die Implementierung von assoziativem Array, Liste, Sammlung, Tasche verwendet.
  • Hash-tabelle — Wird für die Implementierung eines assoziativen Arrays, einer Liste, einer Sammlung und eines Beutels verwendet. Der Zugriff ist fast so schnell wie ein Array, aber hier (wie bei einem Array) muss von Zeit zu Zeit eine teure Größenänderung vorgenommen werden.
  • Verlinkte Liste (unidirektional, bidirektional) – Wird für die Implementierung von Listen, Warteschlangen und Stack verwendet.

Alle Behälter können mit a . verwendet werden Iterator durchlaufen werden.

Siehe die Kategorie Datenstrukturen von Wikimedia Commons für Mediendateien zu diesem Thema.