Datenstruktur

Für andere Verwendungen siehe Datenstruktur (Disambiguierung).
Nicht zu verwechseln mit Datentyp.
Informationen zur Datenstruktur von Wikipedia finden Sie unter Wikipedia: Verwaltung § Datenstruktur und -entwicklung.
Eine Datenstruktur, die als a bekannt ist Hash-tabelle.

Im Informatik, a Datenstruktur ist ein Daten Organisations-, Management- und Speicherformat, das normalerweise ausgewählt wird effizient Zugang zu Daten.[1][2][3] Genauer gesagt ist eine Datenstruktur eine Sammlung von Datenwerten, die Beziehungen zwischen ihnen und die Funktionen oder Vorgänge, die auf die Daten angewendet werden können.[4] d.h. es ist ein algebraische Struktur um Daten.

Verwendungszweck

Datenstrukturen dienen als Grundlage für Abstrakte Datentypen (ADT). Der ADT definiert die logische Form des Datentyps. Die Datenstruktur implementiert die physikalische Form des Datentyps.[5]

Verschiedene Arten von Datenstrukturen sind für verschiedene Arten von Anwendungen geeignet, einige sind auf bestimmte Aufgaben hochspezialisiert. Zum Beispiel verwenden relationale Datenbanken häufig B-Baum Indizes für das Abrufen von Daten,[6] während Compiler Implementierungen werden normalerweise verwendet Hash -Tische nach Identifikatoren nachschlagen.[7]

Datenstrukturen bieten ein Mittel, um große Datenmengen effizient für Verwendungen wie groß zu verwalten Datenbanken und Internet -Indexierungsdienste. Normalerweise sind effiziente Datenstrukturen für effizientes Entwerfen von entscheidender Bedeutung Algorithmen. Einige formale Designmethoden und Programmiersprachen Betonen Sie eher Datenstrukturen als Algorithmen als wichtiger Organisationsfaktor für das Softwaredesign. Datenstrukturen können verwendet werden, um die Speicherung und das Abrufen von Informationen zu organisieren, die in beiden gespeichert sind Haupterinnerung und Sekundärgedächtnis.[8]

Implementierung

Datenstrukturen basieren im Allgemeinen auf der Fähigkeit von a Computer Daten an jedem Ort in seinem Speicher abrufen und speichern, angegeben durch a Zeiger- eine Bit -String, die a darstellt Speicheradresse, das kann selbst in Erinnerung gespeichert und vom Programm manipuliert werden. Und so kam es dass der Array und Aufzeichnung Datenstrukturen basieren auf der Berechnung der Adressen von Datenelementen mit Rechenoperationen, während verknüpfte Datenstrukturen basieren auf der Speicherung von Adressen von Datenelementen in der Struktur selbst.

Die Implementierung einer Datenstruktur erfordert normalerweise das Schreiben eines Satzes von Verfahren das erzeugt und manipuliert Instanzen dieser Struktur. Die Effizienz einer Datenstruktur kann nicht getrennt von diesen Vorgängen analysiert werden. Diese Beobachtung motiviert das theoretische Konzept eines Zusammenfassung Datentyp, eine Datenstruktur, die indirekt durch die Operationen definiert wird, die darauf ausgeführt werden können, und die mathematischen Eigenschaften dieser Operationen (einschließlich ihrer Raum- und Zeitkosten).[9]

Beispiele

Hauptartikel: Liste der Datenstrukturen
Die Standardtyphierarchie der Programmiersprache Python 3.

Es gibt zahlreiche Arten von Datenstrukturen, die im Allgemeinen auf einfacherem Aufbau basieren Primitive Datentypen. Bekannte Beispiele sind:[10]

  • A Byte ist die kleinste Datenmenge, die viele CPUs kann vom Speicher in ein Register oder zurück in a kopieren Einzel -CPU -Anweisungdaher a Bytestream ist die effizienteste Möglichkeit, Big Data über einen Computer auszuführen, daher Stream -Verarbeitung. [11]
  • Ein Array ist eine Reihe von Elementen in einer bestimmten Reihenfolge, in der Regel alle denselben Typ (abhängig von der Sprache können einzelne Elemente entweder alle zum gleichen Typ sein oder von nahezu jedem Typ sein). Auf Elemente werden mit einem Ganzzahlindex zugegriffen, um anzugeben, welches Element erforderlich ist. Typische Implementierungen weisen zusammenhängende Speicherwörter für die Elemente von Arrays zu (dies ist jedoch nicht immer eine Notwendigkeit). Arrays können festgelegt oder resizierbar sein.
  • A verlinkte Liste (Auch nur gerufen aufführen) ist eine lineare Sammlung von Datenelementen jeglicher Art, genannt Knoten, 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 über ein Array besteht darin, dass Werte immer effizient eingefügt und entfernt werden können, ohne den Rest der Liste zu verlegen. Bestimmte andere Operationen, wie z. Zufallszugriff Zu einem bestimmten Element sind jedoch in Listen langsamer als in Arrays.
  • A Aufzeichnung (auch genannt Tupel oder Struktur) ist ein Daten sammeln Struktur. Ein Datensatz ist ein Wert, der andere Werte enthält, typischerweise in fester Zahl und Sequenz und typischerweise mit Namen indiziert. Die Elemente von Aufzeichnungen werden normalerweise genannt Felder oder Mitglieder.
  • A Union ist eine Datenstruktur, die angibt, welche von einer Reihe von zulässigen primitiven Typen in ihren Fällen gespeichert werden kann, z. schweben oder lange Ganzzahl. Kontrast zu a Aufzeichnung, was definiert werden könnte, um einen Schwimmer zu enthalten und eine Ganzzahl; Während es in einer Gewerkschaft jeweils nur einen Wert gibt. Es wird genügend Platz zugeordnet, um den breitesten Mitglied des Mitglieds zu enthalten.
  • A Tagged Union (auch genannt Variante, Variantenaufzeichnung, Diskriminierte Gewerkschaft, oder Union Union) enthält ein zusätzliches Feld, das seinen Stromtyp für eine erweiterte Sicherheitstypsicherheit angibt.
  • Ein Objekt ist eine Datenstruktur, die Datenfelder enthält, wie es ein Datensatz tut, sowie verschiedene verschiedene Methoden die auf dem Dateninhalt arbeiten. Ein Objekt ist eine In-Memory-Instanz einer Klasse von a Taxonomie. Im Zusammenhang mit Objekt orientierte Programmierung, Aufzeichnungen sind als bekannt als einfache alte Datenstrukturen sie von Objekten zu unterscheiden.[12]

Zusätzlich, Hashes, Grafiken und Binärbäume sind andere häufig verwendete Datenstrukturen.

Sprachunterstützung

Die meisten Assemblersprachen und einige Sprachen auf niedriger Ebene, wie zum Beispiel BCPL (Basic kombinierte Programmiersprache), fehlt integrierte Unterstützung für Datenstrukturen. Andererseits viele hochrangige Programmiersprachen und einige höhere Versammlungssprachen, wie z. MasmSie haben eine spezielle Syntax oder eine andere integrierte Unterstützung für bestimmte Datenstrukturen wie Datensätze und Arrays. Zum Beispiel die C (ein direkter Nachkomme von BCPL) und Pascal Sprachen Unterstützung Strukturen und Aufzeichnungen zusätzlich zu Vektoren (eindimensional Arrays) und mehrdimensionale Arrays.[13][14]

Die meisten Programmiersprachen bieten eine Art von Art von Bibliothek Mechanismus, mit dem Datenstrukturimplementierungen durch verschiedene Programme wiederverwendet werden können. Moderne Sprachen sind normalerweise mit Standardbibliotheken ausgestattet, die die häufigsten Datenstrukturen implementieren. Beispiele sind die C ++ Standard -Vorlagenbibliothek, das Java -Sammlungsrahmen, und die Microsoft .NET Framework.

Moderne Sprachen unterstützen auch im Allgemeinen auch Modulare Programmierungdie Trennung zwischen dem Schnittstelle eines Bibliotheksmoduls und seiner Implementierung. Einige bieten undurchsichtige Datentypen Dadurch können Kunden Implementierungsdetails ausblenden. Objektorientierte Programmiersprachen, wie zum Beispiel C ++, Java, und Smalltalk, normalerweise verwenden Klassen für diesen Zweck.

Viele bekannte Datenstrukturen haben gleichzeitig Versionen, mit denen mehrere Computer -Threads gleichzeitig auf eine einzelne Betoninstanz einer Datenstruktur zugreifen können.[15]

Siehe auch

Verweise

  1. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Einführung in Algorithmen, dritte Ausgabe (3. Aufl.). Die MIT -Presse. ISBN 978-0262033848.
  2. ^ Black, Paul E. (15. Dezember 2004). "Datenstruktur". In Pieterse, Vreda; Black, Paul E. (Hrsg.). Wörterbuch von Algorithmen und Datenstrukturen [Online]. Nationales Institut für Standards und Technologie. Abgerufen 2018-11-06.
  3. ^ "Datenstruktur". Enzyklopädie Britannica. 17. April 2017. Abgerufen 2018-11-06.
  4. ^ Wegner, Peter; Reilly, Edwin D. (2003-08-29). Enzyklopädie der Informatik. Chichester, Großbritannien: John Wiley und Söhne. S. 507–512. ISBN 978-0470864128.
  5. ^ "Abstrakte Datentypen". Virginia Tech - CS3 -Datenstrukturen und Algorithmen.
  6. ^ Gavin Powell (2006). "Kapitel 8: Erstellen schneller Datenbankmodelle". Datenbankdesign beginnen. Wrox Publishing. ISBN 978-0-7645-7490-0.
  7. ^ "1.5 Anwendungen einer Hash -Tabelle". Universität Regina - CS210 Lab: Hash Tabelle. Archiviert von das Original am 2021-04-27. Abgerufen 2018-06-14.
  8. ^ "Wenn Daten zu groß sind, um in den Hauptspeicher zu passen". homes.sice.indiana.edu.
  9. ^ Dubey, R. C. (2014). Fortgeschrittene Biotechnologie: Für B SC- und M SC -Studenten der Biotechnologie und anderer biologischer Wissenschaften. Neu -Delhi: S Chand. ISBN 978-81-219-4290-4. OCLC 883695533.
  10. ^ Seymour, Lipschutz (2014). Datenstrukturen (Überarbeitet zuerst Ed.). Neu -Delhi, Indien: McGraw Hill Education. ISBN 9781259029967. OCLC 927793728.
  11. ^ Cline, Marshall. "C ++ FAQ: Die Regeln für Bytes, Zeichen und Charaktere".
  12. ^ Walter E. Brown (29. September 1999). "C ++ Sprache Hinweis: POD -Typen". Fermi National Accelerator Laboratory. Archiviert von das Original Am 2016-12-03. Abgerufen 6. Dezember 2016.
  13. ^ "Das GNU C -Handbuch". Kostenlose Software -Stiftung. Abgerufen 2014-10-15.
  14. ^ Van Canneyt, Michaël (September 2017). "Kostenloser Pascal: Referenzhandbuch". Kostenloser Pascal.
  15. ^ Mark Moir und Nir Shavit. "Gleichzeitige Datenstrukturen" (PDF). cs.tau.ac.il.

Literaturverzeichnis

Weitere Lektüre

Externe Links