Was ist ein abstrakter Datentyp in der objektorientierten Programmierung?

Question

Was ist ein abstrakter Datentyp in der objektorientierten Programmierung? Ich habe das Wiki zu diesem Thema durchgesehen, aber es ist mir immer noch nicht klar. Könnte das jemand klären?

Answer 1

Eine abstrakte Klasse ist ein Verallgemeinerungskonzept. Es ist eine Klasse, die Sie erfinden, um sie nur als Basisklasse für die Vererbung zu verwenden, aber nicht, um daraus Objekte zu instanziieren.

Und abstrakter Datentyp ( ADT ) ist nicht unbedingt ein OOP-Konzept. Es ist ein älterer Begriff, um die Konzepte von z.B. Stack und Queue in Bezug auf ihre Funktionalität zu beschreiben, ohne die Implementierung zu beschreiben.

Answer 2

Es gibt einen Unterschied zwischen einem " abstrakter Datentyp " und ein " abstrakte Klasse ".

Eine abstrakte Klasse ist eine, die möglicherweise nicht für alle Methoden, die sie definiert, Definitionen hat. Sie können daher eine abstrakte Klasse nicht direkt instanziieren. Sie müssen eine Unterklasse erstellen und diese dann instanziieren.

Eine abstrakter Datentyp ist eine Modell einer bestimmten Art von Datenstruktur, z. B. einer Stapel . Ein Stapel hat push()- und pop()-Operationen, die ein genau definiertes Verhalten aufweisen.

Der abstrakte Datentyp (ADT) selbst bezieht sich auf dieses Modell, nicht auf eine bestimmte Implementierung in einer bestimmten Programmiersprache oder einem bestimmten Paradigma . Sie können einen Stack in einer objektorientierten Sprache implementieren, aber auch in einer funktionalen Programmiersprache.

ADTs ermöglichen eine Diskussion über die Eigenschaften von Stapeln, Warteschlangen usw., die für alle korrekten Implementierungen des ADTs gelten.

Answer 3

Nun, es geht um alles Abstraktion . Die Abstraktion ist besonders bei der Programmierung nützlich. Der Hauptvorteil ist die Fähigkeit, Realisierungsdetails zu verbergen. Man versteckt sie innerhalb eines Moduls (sog. "Server-Module") und stellt eine öffentliche Schnittstelle für andere Module (sog. "Client-Module") bereit. Und jetzt haben wir drei verschiedene Möglichkeiten:

Server-Modul kann eine abstrakte Datenstruktur (ADS) selbst.

In diesem Fall enthält er die ADS-Entität selbst. Die öffentliche Schnittstelle besteht aus einigen Prozeduren (und vielleicht einigen Konstanten).

Schnittstelle des Server-Moduls (stack_ads.h):

#ifndef STACK_ADS
#define STACK_ADS

const int capacity = 10;

void clear();
int size();
int pop();
void push(int value);

#endif STACK_ADS

Implementierung (stack_ads.cpp):

#include "stack_ads.h"

int items[capacity];
int top = -1;

void clear()
{
  top = -1;
}

int size()
{
  return top + 1;
}

int pop()
{
  top -= 1;
  return items[top + 1];
}

void push(int value)
{
  top += 1;
  items[top] = value;
}

Im Client-Modul (main.cpp) importieren wir das Server-Modul und verwenden die Datenstruktur direkt.

#include <iostream>
#include "stack_ads.h"

int main (int argc, char* const argv[]) 
{
  push(1);
  push(2);
  push(3);

  std::cout << pop() << std::endl;
  std::cout << pop() << std::endl;
  std::cout << pop() << std::endl;

  return 0;
}

Server-Modul kann eine abstrakter Datentyp (ADT) in Form von struct/record.

Im Client-Modul können wir Variablen dieses Typs deklarieren. Da es einem Modul freisteht, mehr als eine Variable des exportierten Typs zu deklarieren, kann es mehr als eine Datenstruktur haben. Jede abstrakte Datenstruktur ist eine Variable vom abstrakten Datentyp.

Schnittstelle (stack_adt.h):

#ifndef STACK_ADT
#define STACK_ADT

const int capacity = 10;

typedef struct
{
  int items[capacity];
  int top;
} StackADT;

void clear(StackADT* stack);
int size(StackADT* stack);
int pop(StackADT* stack);
void push(StackADT* stack, int value);  

#endif STACK_ADT

Implementierung (stack_adt.cpp):

#include "stack_adt.h"

void clear(StackADT* stack)
{
  stack->top = -1;
}

int size(StackADT* stack)
{
  return stack->top + 1;
}

int pop(StackADT* stack)
{
  stack->top -= 1;
  return stack->items[stack->top + 1];
}

void push(StackADT* stack, int value)
{
  stack->top += 1;
  stack->items[stack->top] = value;
}

Client-Modul:

#include <iostream>
#include "stack_adt.h"

int main (int argc, char* const argv[]) 
{
  StackADT stack1;
  StackADT stack2;
  stack1.top = -1;
  stack2.top = -1;

  push(&stack1, 1);
  push(&stack1, 2);
  push(&stack1, 3);

  std::cout << pop(&stack1) << std::endl;
  std::cout << pop(&stack1) << std::endl;
  std::cout << pop(&stack1) << std::endl;

  push(&stack2, 10);
  push(&stack2, 20);
  push(&stack2, 30);

  std::cout << pop(&stack2) << std::endl;
  std::cout << pop(&stack2) << std::endl;
  std::cout << pop(&stack2) << std::endl;

  return 0;
}

Schließlich kann das Servermodul eine abstrakter Datentyp (ADT) in Form von Klasse .

Wenn unsere Sprache OOP unterstützt, können wir ADT mit Hilfe von Klassen beschreiben. Und im Client-Modul können wir wiederum Variablen dieses Typs deklarieren. In der objektorientierten Terminologie wird der Typ als Klasse und die Variable mit diesem Typ wird als Objekt .

Server-Modul-Schnittstelle (Stack.h):

#ifndef STACK
#define STACK

const int capacity = 10;

class Stack
{
public:
  Stack();
  void clear();
  int size();
  int pop();
  void push(int value);
private:
  int items[capacity];
  int top;
};

#endif STACK

Implementierung (Stack.cpp):

#include "Stack.h"

Stack::Stack()
{
  this->top = -1;
}

void Stack::clear()
{
  this->top = -1;
}

int Stack::size()
{
  return this->top + 1;
}

int Stack::pop()
{
  this->top -= 1;
  return this->items[this->top + 1];
}

void Stack::push(int value)
{
  this->top += 1;
  this->items[this->top] = value;
}

Die Unterschiede zwischen den beiden letzten Optionen sind:

• Die oben erwähnte Terminologie (Typ <-> Klasse, Variable <-> Objekt).
• In der Nicht-Klassen-ADT muss die formale Parameterliste jeder Prozedur eine Variable s vom Typ Stack enthalten. In der Klasse Stack wird die Angabe der Datenstruktur s nicht mit den anderen Formalparametern nach dem Namen der Prozedur aufgeführt, sondern steht allein in Klammern vor dem Namen der Prozedur. In der Smalltalk-Terminologie wird der formale Parameter vor dem Prozedurnamen als Empfänger .
• Der Ort der Verfahren. In der Nicht-Klassen-ADT befinden sich die Prozeduren außerhalb der Stack-Struktur. In der Klasse befinden sich die Prozeduren innerhalb der Klasse. In der objektorientierten Terminologie werden Prozeduren, die Empfänger haben und daher innerhalb eines Klassentyps enthalten sind, als Methoden .

Client-Code:

#include <iostream>
#include "stack.h"

int main (int argc, char* const argv[]) 
{
  Stack stack1;
  Stack stack2;

  stack1.push(1);
  stack1.push(2);
  stack1.push(3);

  std::cout << stack1.pop() << std::endl;
  std::cout << stack1.pop() << std::endl;
  std::cout << stack1.pop() << std::endl;

  stack2.push(10);
  stack2.push(20);
  stack2.push(30);

  std::cout << stack2.pop() << std::endl;
  std::cout << stack2.pop() << std::endl;
  std::cout << stack2.pop() << std::endl;

  return 0;
}

Answer 4

Ein abstrakter Datentyp (ADT) ist ein mathematisches Modell eines Datentyps. Er beschreibt die Operationen, die mit den Daten durchgeführt werden können, und die mathematische Definition dieser Operationen durch Gleichungen.

So kann man beispielsweise das Verhalten eines Zahlenstapels ganz abstrakt mit Operationen wie pop(), push(), top() und vielleicht einem konstanten Symbol für den leeren Stapel modellieren.

Hier sind zum Beispiel einige Gleichungen, die Teil der Definition eines Zahlenstapels sein könnten:

pop(empty) = empty  // silently ignores popping an empty stack
pop(push(N,S)) = S  // i.e. pop removes the top element of push(N,S)
top(push(N,S)) = N  // return topmost element of the stack without changing the stack

Ein abstrakter Datentyp ist keineswegs dasselbe wie eine Klasse in einem Objektmodell - obwohl sie einige Ähnlichkeiten aufweisen.

Hier die Namen der wichtigsten Begriffe: Anfangsalgebra-Semantik, Isomorphismus, Quotienten, Kongruenzen

Der Sinn eines abstrakten Datentyps besteht darin, das Verhalten einer ganzen Klasse von äquivalenten Typdarstellungen zu verstehen, indem man Gleichungen und etwas ausgefallene Mathematik verwendet, die zeigt, dass jede Implementierung "isomorph" ist - d.h. dass beide Implementierungen genau äquivalent sind, soweit es das beobachtbare Verhalten betrifft.

Der Wikipedia-Eintrag zu diesem Thema ist ziemlich gut: http://en.wikipedia.org/wiki/Abstract_data_type

Hier sind einige gute (aber sehr theoretische) Kursnotizen, die genau beschreiben, was ein ADT ist http://www-compsci.swan.ac.uk/~csulrich/ftp/adt/adt.pdf

Obwohl sie oberflächlich betrachtet dem Konzept einer "Klasse" in einigen objektorientierten Programmiersprachen ähnelt, ist eine "Klasse" kein ADT, aber eine Klasse kann zur Implementierung eines bestimmten ADT verwendet werden.

Im Allgemeinen ist das ADT-Konzept wahrscheinlich eher auf die funktionale Programmierung als auf die objektorientierte Programmierung anwendbar, da nicht alle objektorientierten Programmiersprachen über Klassen verfügen und ADT-artiges Denken weniger effektive OO-Designs hervorbringt.

• Hier ist ein Papier, das die Probleme beim Denken in ADTs in einer OO-Sprache aufzeigt: http://portal.acm.org/citation.cfm?id=74885
• Im Grunde zeigt das Papier, dass die "Klasse", die Sie zur Implementierung eines ADT verwenden, am Ende mit vielen winzig kleinen Methoden bedeckt ist (die wie die Basis von ADT-Gleichungen aussehen), anstatt ein paar mächtige, hochabstrakte Methoden zu haben.

Answer 5

Definition:

Ganz grob gesagt, Abstrakter Datentyp (ADT) ist eine Art, eine Datenstruktur zu betrachten: sich auf das konzentrieren, was sie tut, und ignorieren, wie sie es tut seine Aufgabe.

Abstrakte Datentypen werden in erster Linie durch ihre Schnittstelle definiert: die zulässigen Operationen, die mit ihnen durchgeführt werden können. Der zugrundeliegende Mechanismus, der zur sie zu implementieren, ist für den Benutzer normalerweise nicht sichtbar.

---

Beispiele:

Stack , Queue y PriorityQueue sind einige der Beispiele für ADTs, sie sind abstrakter als Arrays, verknüpfte Listen und viele andere Datenspeicherstrukturen.

Der einem Stapel zugrunde liegende Mechanismus kann zum Beispiel ein Array oder es kann ein LinkedList . Der zugrunde liegende Mechanismus für eine PriorityQueue kann ein Array oder eine besondere Art von Baum, genannt Heap .

---

Code:

Hier ist ein Java-Beispiel für den abstrakten Datentyp namens PriorityQueue die unter Verwendung des Heap implementiert wurde:

class Heap {
  private Node heapArray[];
  public void insert(Node node) {...}
  public Node remove() {...}
}

class PriorityQueue {
  private Heap heap;
  public void insert(Node node) { 
    heap.insert(node);
  }
  public Node remove() {
    return heap.remove();
  }
}

Hier können Sie sehen, dass die Methoden für die PriorityQueue Klasse werden einfach um die Methoden für die zugrunde liegende Heap Klasse. In ähnlicher Weise können Sie Array anstelle von Heap um die gleiche Funktionalität zu implementieren, auch wenn im Falle von Array benötigen Sie mehr Code, um Vorgänge wie Einfügen und Entfernen zu erledigen. Dieses Beispiel sollte es konzeptionell klar machen, dass eine PriorityQueue ist ein ADT, der auf verschiedene Weise implementiert werden kann, z. B. durch Verwendung von Heap, Arrays und so weiter.

Obwohl ADTs in objektorientierten Programmiersprachen (OOP) sinnvoller sind, sind sie nicht auf OOP-Sprachen beschränkt und können auch mit Nicht-OOP-Sprachen erstellt werden.

---