homedukeOOP mit Java: Konzept der abstrakten Datentypen Prof. Dr. Uwe Schmidt FH Wedel

Konzept der abstrakten Datentypen

weiter

weiter

Begriffe

ADT
Beschreibung eines Datentyps vollständig durch die auf dem Datentyp definierten Operationen und deren Beziehungen untereinander.
weiter
Idee
aus der Mathematik:
 
Definition einer Struktur durch ein Axiomensystem
weiter
Beispiel
Peano-Axiome für natürliche Zahlen
weiter

weiter

Beispiel: Stack

types
  Stack, Integer, Boolean
 
operations
  create  :                 -> Stack
  push    : Stack x Integer -> Stack
  pop     : Stack           -> Stack
  top     : Stack           -> Integer
  isEmpty : Stack           -> Boolean
 
preconditions
  pre-pop(s) = not isEmpty(s)
  pre-top(s) = not isEmpty(s)
 
var
  s : Stack;
  i : Integer;
 
axioms
  isEmpty(create())  = true
  isEmpty(push(s,i)) = false
  pop(push(s,i))     = s
  top(push(s,i))     = i
weiter

weiter

Bestandteile

types
Aufzählung aller verwendeten ADT's
weiter
operations
Aufzählung aller auf dem ADT definierten Operationen einschließlich Parametertypen und Resultattyp
Signaturen der Operationen
weiter
preconditions
Vorbedingungen für nur teilweise definierte Operationen
weiter
var
Wertenamen und deren Typen, die in den Axiomen verwendet werden
weiter
axioms
Gesetze, die die Beziehungen zwischen den Operationen festlegen
weiter
merke
Eine Implementierung für einen ADT muss alle Gesetze erfüllen
weiter
merke
Eine Implementierung für einen ADT muss nur diese Gesetze erfüllen
weiter
Operationen
sind Funktionen
weiter
partielle
Operationen (Funktionen) sind nicht für alle möglichen Parameter definiert.
weiter
Vorbedingungen
spezifizieren, wann die Operationen moglich sind
weiter
totale
Operationen sind immer definiert.
weiter
Operationsarten
Konstruktoren
Operationen, bei denen der ADT nur als Resultattyp auftritt
weiter
Attributfunktionen
Operationen, bei denen der ADT nur als Parametertyp auftritt
weiter
Prädikate
Attributfunktionen mit Booleschem Resultat
weiter
modifizierende Funktionen
Operatoren, bei denen der ADT sowohl als Parametertyp als auch als Resultattyp vorkommt.
weiter

Letzte Änderung: 29.04.2013
© Prof. Dr. Uwe Schmidt
Prof. Dr. Uwe Schmidt FH Wedel