Abstrakter Datentyp und Datenstruktur

Es ist ziemlich schwierig für mich, diese Begriffe zu verstehen. Ich habe auf Google gesucht und ein wenig auf Wikipedia gelesen, bin mir aber immer noch nicht sicher. Ich habe bisher festgestellt, dass:

Abstrakter Datentyp ist eine Definition eines neuen Typs, der dessen Eigenschaften und Operationen beschreibt.

Datenstruktur ist eine Implementierung von ADT. Viele ADT können als dieselbe Datenstruktur implementiert werden.

Wenn ich richtig denke, bedeutet Array als ADT eine Sammlung von Elementen und als Datenstruktur, wie es in einem Speicher gespeichert ist. Stack ist ADT mit Push- und Pop-Operationen, aber können wir etwas über die Stack-Datenstruktur sagen, wenn ich damit meine, dass ich Stack als Array in meinem Algorithmus implementiert habe? Und warum ist Haufen nicht ADT? Es kann als Baum oder Array implementiert werden.

Einfach ausgedrückt ist ein ADT (Abstract Data Type) eher eine logische Beschreibung, während eine Datenstruktur konkret ist.

Stellen Sie sich ein ADT als ein Bild der Daten und der Vorgänge vor, mit denen diese bearbeitet und geändert werden sollen.

Eine Datenstruktur ist das Reale, Konkrete . Es kann innerhalb eines Algorithmus implementiert und verwendet werden.

ADT ist für eine Schnittstelle ( was es tut ), was eine Datenstruktur für eine Klasse ist ( wie es tut ).

Einige Beispiele:

ADT: List
DS:  ArrayList, LinkedList...

ADT: Map
DS:  HashMap, TreeMap...

Ich denke, du verstehst, worum es geht.

Abstrakter Datentyp: ADT kann als ein Satz von Datenwerten und zugehörigen Operationen definiert werden, die unabhängig von einer bestimmten Implementierung genau angegeben werden. Ein abstrakter Datentyp ist also eine organisierte Sammlung von Informationen und eine Reihe von Vorgängen, mit denen diese Informationen verwaltet werden. Der Operationssatz definiert die Schnittstelle des ADT. Solange der ADT die Bedingungen der Schnittstelle erfüllt, spielt es keine Rolle, wie der ADT implementiert ist. Da in ADT die Datenwerte und Operationen nicht als Implementierung in einer Computersprache, sondern mit mathematischer Genauigkeit definiert werden, können wir über die Auswirkungen der Operationen, die Beziehungen zu anderen abstrakten Datentypen, unabhängig davon, ob ein Programm den Datentyp implementiert, nachdenken.

Der grundlegende Unterschied zwischen dem abstrakten Datentyp (ADT) und dem konkreten Datentyp besteht darin, dass der letztere es uns ermöglicht, die konkrete Darstellung zu betrachten, während der erstere die Darstellung vor uns verbirgt. Ein ADT kann ein reines ADT oder ein aktualisierbares ADT sein. Ein reiner ADT ist einer, bei dem alle Operationen reine Funktionen sind. Dies bedeutet, dass Operationen keine Nebenwirkungen haben. Insbesondere ändern oder aktualisieren sie dort keine Eingabeargumente. Sie verwenden diese Argumente nur, um eine Ausgabe zu generieren, die neue Werte von ADT (oder anderen Typen) sind. Die meisten Betontypen sind rein. Beispielsweise ändert keine Operation für Ganzzahlen tatsächlich eine Ganzzahl. Stattdessen erzeugen alle Operationen wie '+' neue Ausgaben.

Bei einem aktualisierbaren ADT ändern einige Vorgänge tatsächlich die Werte des ADT. Angenommen, wir hatten eine Operation namens 'pop', die einen Stapel als Argument genommen und geändert hat. ("An Ort und Stelle", "destruktiv") durch Entfernen des Elements mit der höchsten Priorität. Diese Operation würde als unrein angesehen, und das gesamte ADT wäre dann auch unrein. Ein ADT kann ein benutzerdefiniertes ADT sein.

Wir wissen, dass ein abstrakter Datentyp ein Datentyp ist, der die folgenden zwei Bedingungen erfüllt:

1. Die Darstellung oder Definition des Typs und der Operationen sind in einer einzigen syntaktischen Einheit enthalten.

2. Die Darstellung von Objekten des Typs ist vor den Programmeinheiten, die den Typ verwenden, verborgen, sodass nur die in der Typdefinition angegebenen direkten Operationen für diese Objekte möglich sind.

Ein benutzerdefinierter abstrakter Datentyp sollte Folgendes bereitstellen:

1. Eine Typdefinition, die es Programmeinheiten ermöglicht, Variablen des Typs zu deklarieren, aber die Darstellung dieser Variablen verbirgt.

2. Eine Reihe von Operationen zum Bearbeiten von Objekten des Typs.

Ein Beispiel für einen benutzerdefinierten abstrakten Datentyp ist die Struktur. 'C' bietet vier Grundtypen: int, char, float und double. 'C' bietet dem Programmierer jedoch auch die Möglichkeit, seine eigenen Typen zu definieren. Struktur ist ein solches Beispiel. Eine Struktur ist ein Aggregat aus verschiedenen Teilen, wobei jedes Teil von einem vorhandenen Typ ist.

struct abc

{int x;

float y;

};

Die obige Strukturdefinition erstellt keine Variablen, sondern einen neuen Typ. Variablen dieses Typs können auf ähnliche Weise wie Variablen eines eingebauten Typs erstellt werden.

struct abc a;

Mit dem Schlüsselwort typedef können wir neue Typnamen für unsere neuen Typen erstellen.

Beispielsweise:

typedef struct abc AB;

Dabei ist AB ein neuer Typname, der jetzt zum Erstellen neuer Typen verwendet werden kann.

AB b;

Datenstrukturen: Folgendes sind die charakteristischen Merkmale von Datenstrukturen:

1. Es enthält Komponentendatenelemente, die atomar oder eine andere Datenstruktur (immer noch eine Domäne) sein können.

2. Eine Reihe von Operationen an einem oder mehreren Komponentenelementen.

3. Definiert Regeln, wie Komponenten miteinander und mit der Struktur als Ganzes in Beziehung stehen (Assertions).

Datenstrukturen:

Eine Datenstruktur kann statisch oder dynamisch sein. Eine statische Datenstruktur hat eine feste Größe. Diese Bedeutung unterscheidet sich von der Bedeutung des statischen Modifikators. Arrays sind statisch; Sobald wir die Anzahl der Elemente definiert haben, die es aufnehmen kann, ändert sich die Anzahl nicht mehr. Eine dynamische Datenstruktur wächst und schrumpft zur Ausführungszeit je nach Inhalt. Eine dynamische Datenstruktur wird über Links implementiert.

Datenstrukturen können ferner in lineare Datenstrukturen und nichtlineare Datenstrukturen eingeteilt werden. In linearen Datenstrukturen hat jede Komponente einen eindeutigen Vorgänger und Nachfolger mit Ausnahme des ersten und des letzten Elements, wohingegen im Fall nichtlinearer Datenstrukturen keine solche Einschränkung besteht, da Elemente auf jede gewünschte Weise angeordnet werden können, die auf die Art und Weise beschränkt ist, die wir verwenden repräsentieren solche Typen.

Erstens können Terminologien in Datenstrukturen sehr verwirrend sein.

ADT ist wie eine Theorie oder ein Modell oder eine Richtlinie usw., die angibt, wie sich eine Datenstruktur verhalten soll, welche Art von Operationen sie unterstützen soll usw. Drei grundlegende abstrakte Datentypen sind Container, Wörterbücher und Prioritätswarteschlangen. Zum Beispiel sagt uns das Wörterbuch, dass jede Datenstruktur, die dieses Wörterbuch-ADT implementiert, Schlüssel-Wert-Paare, eine Suche basierend auf Schlüsseln, das Einfügen von Elementen, das Finden des Nachfolgers und des Vorgängers eines gegebenen Schlüssels usw. unterstützen muss.

Jetzt ist alles andere, was dies über ADT implementiert, Datenstruktur (DS) . Datenstrukturen sind reale Dinge, die Sie in Ihre Probleme implementieren und in Bibliotheken finden. Im Falle eines Wörterbuchs können Sie sich dafür entscheiden, es über ein Array oder eine verknüpfte Liste zu implementieren.

Ich denke , es entsteht echte Verwirrung , wenn jemand seinen DS als ADT bezeichnet. Einige Leute nennen beispielsweise den oben genannten DS "Dictionary" anstelle von DictImplementation, was vollkommen legal ist. Dies führt nur zu Verwirrung.

Ref: Skiena: Das Algorithmus-Design-Handbuch