Abstrakte Datentypen

Ein abstrakter Datentyp (ADT) beschreibt einen Verbund von Daten (z.B. eine Variable, eine Liste oder einen Binärbaum) und Methoden, mit denen auf die Daten zugegriffen werden kann. Dabei gilt, dass auf die in einem Objekt des Datentyps gespeicherten Daten ausschließlich über die festgelegten Methoden zugegriffen werden darf.

Im letzten Kapitel wurde Datentypen vorgestellt, bei denen jeweils nur ein Wert gespeichert wird. In diesem Kapitel werden abstrakte Datentypen vorgestellt, in welchen mehr als ein Wert gespeichert werden kann:

  • ADT dynamische Reihung,
  • ADT Stapel,
  • ADT Schlange,
  • ADT Binärbaum.

ADT dynamische Reihung

Ein Beispiel für eine Definition eines abstrakten Datentyps ist der vom niedersächsischen Kultusministerium vorgegebene ADT dynamische Reihung:

Dynamische Reihung
Die Nummerierung der dynamischen Reihung beginnt mit dem Index 1. Der in den Operationen verwendete Parameter index zur Übergabe einer Position ist dabei jeweils so zu wählen, dass er sich in einem zulässigen Bereich befindet.

DynArray()
Eine leere dynamische Reihung wird angelegt.

isEmpty(): Wahrheitswert
Wenn die Reihung kein Element enthält, wird der Wert wahr zurückgegeben, sonst der Wert falsch.

getItem(Ganzzahl index): Inhalt
Der Inhalt des Elements an der Position index wird zurückgegeben.

append(Inhalt inhalt)
Der übergebene Inhalt wird als neues Element am Ende der dynamischen Reihung angefügt.

insertAt(Ganzzahl index, Inhalt inhalt)
Der Inhalt wird als neues Element an der Position index in die dynamische Reihung eingefügt. Das sich vorher an dieser Position befindende Element und alle weiteren werden nach hinten verschoben. Entspricht index der Länge der Reihung +1, so wird ein neues Element am Ende der dynamischen Reihung angefügt.

setItem(Ganzzahl index, Inhalt inhalt)
Der Inhalt des Elementes an der Position index wird durch den übergebenen Inhalt ersetzt.

delete(Ganzzahl index)
Das Element an der Position index wird entfernt. Alle folgenden Elemente werden um eine Position nach vorne geschoben.

getLength(): Ganzzahl
Die Anzahl der Elemente der dynamischen Reihung wird zurückgegeben.

Quelle: Niedersächsisches Kultusministerium, 2017

In JavaScript kann der ADT dynamische Reihung wie folgt realisiert werden:

class DynArray {
  constructor() {
    this.inhalt = [];
  }
  isEmpty() { if (this.inhalt.length == 0) { return true;
    } else { return false; } };
  getItem(idx) { return this.inhalt[idx-1]; };
  append(val) { this.inhalt.push(val); };
  insertAt(idx, val) { this.inhalt.splice(idx-1, 0, val); };
  setItem(idx, val) { this.inhalt[idx-1] = val; };
  delete(idx) { this.inhalt.splice(idx-1, 1); };
  getLength() { return this.inhalt.length; };
  getDynArray() { return this.inhalt.slice(0); };
}

Zusätzlich zu der Festlegung durch das Kultusministerium wurde die Methode getDynArray() hinzugefügt, damit alle momentan gespeicherten Daten ausgelesen werden können.

Im folgenden Programm wird gezeigt, wie ausschließlich mit den Methoden des ADTs im ADT dynamische Reihung Daten gespeichert, verändert und herausgelesen werden können:

In einem neuen Fenster starten: ADT dynamische Reihung


ADT Stapel (Stack)

Der abstrakte Datentyp Stapel (englisch Stack) wird vom niedersächsischen Kultusministerium wie folgt festgelegt:

Stapel

Stack()
Ein leerer Stapel wird angelegt.

isEmpty(): Wahrheitswert
Wenn der Stapel kein Element enthält, wird der Wert wahr zurückgegeben, sonst der Wert falsch.

top(): Inhalt
Der Inhalt des obersten Elements des Stapels wird zurückgegeben, das Element aber nicht entfernt.

push(Inhalt inhalt)
Ein neues Element mit dem angegebenen Inhalt wird auf den Stapel gelegt.

pop(): Inhalt
Der Inhalt des obersten Elements wird zurückgegeben und das Element wird entfernt.

Quelle: Niedersächsisches Kultusministerium, 2017

In JavaScript kann der ADT Stapel wie folgt realisiert werden:

class Stack {
  constructor() {
    this.inhalt = [];
  }
  isEmpty() { if (this.inhalt.length == 0) { return true; 
    } else { return false; } };
  top() { return this.inhalt[this.inhalt.length-1] };
  push(val) { this.inhalt.push(val) };
  pop() { return this.inhalt.pop() };
  getStack() { return this.inhalt.slice(0) };
}

Zusätzlich zu der Festlegung durch das Kultusministerium wurde die Methode getStack() hinzugefügt, damit alle momentan gespeicherten Daten ausgelesen werden können.

Im folgenden Programm wird gezeigt, wie ausschließlich mit den Methoden des ADTs im ADT Stapel Daten gespeichert, verändert und herausgelesen werden können:

In einem neuen Fenster starten: ADT Stapel


ADT Schlange (Queue)

Der abstrakte Datentyp Schlange (englisch Queue) wird vom niedersächsischen Kultusministerium wie folgt festgelegt:

Schlange

Queue()
Eine leere Schlange wird angelegt.

isEmpty(): Wahrheitswert
Wenn die Schlange kein Element enthält, wird der Wert wahr zurückgegeben, sonst der Wert falsch.

head(): Inhalt
Der Inhalt des ersten Elements der Schlange wird zurückgegeben, das Element aber nicht entfernt.

enqueue(Inhalt inhalt)
Ein neues Element mit dem angegebenen Inhalt wird angelegt und am Ende an die Schlange angehängt.

dequeue(): Inhalt
Der Inhalt des ersten Elements wird zurückgegeben und das Element wird entfernt.

Quelle: Niedersächsisches Kultusministerium, 2017

In JavaScript kann der ADT Schlange wie folgt realisiert werden:

class Queue {
  constructor() {
    this.inhalt = [];
  }
  isEmpty() { if (this.inhalt.length == 0) { return true; 
    } else { return false; } };
  head() { return this.inhalt[0] };
  enqueue(val) { this.inhalt.push(val) };
  dequeue() { return this.inhalt.shift() };
  getQueue() { return this.inhalt.slice(0) };
}

Zusätzlich zu der Festlegung durch das Kultusministerium wurde die Methode getQueue() hinzugefügt, damit alle momentan gespeicherten Daten ausgelesen werden können.

Im folgenden Programm wird gezeigt, wie ausschließlich mit den Methoden des ADTs im ADT Schlange Daten gespeichert, verändert und herausgelesen werden können:

In einem neuen Fenster starten: ADT Schlange


ADT Binärbaum (BinTree)

Der abstrakte Datentyp Binärbaum (englisch BinTree) wird vom niedersächsischen Kultusministerium wie folgt festgelegt:

Binärbaum

BinTree(Inhalt inhalt)
Ein Baum wird erzeugt. Die Wurzel erhält den übergebenen Inhalt als Wert.

isLeaf(): Wahrheitswert
Die Anfrage liefert den Wert wahr, wenn der Baum keinen linken und keinen rechten Teilbaum besitzt, sonst liefert sie den Wert falsch.

getLeft(): BinTree
Die Operation gibt den linken Teilbaum zurück. Existiert kein linker Teilbaum, so ist das Ergebnis null.

getRight(): BinTree
Die Operation gibt den rechten Teilbaum zurück. Existiert kein rechter Teilbaum, so ist das Ergebnis null.

setLeft(BinTree b)
Der übergebene Baum wird als linker Teilbaum gesetzt.

setRight(BinTree b) Der übergebene Baum wird als rechter Teilbaum gesetzt.

getItem(): Inhalt Die Operation gibt den Inhaltswert der Wurzel des aktuellen Baumes zurück.

setItem(Inhalt inhalt) Die Operation setzt den Inhaltswert der Wurzel des aktuellen Baumes.

Quelle: Niedersächsisches Kultusministerium, 2017

Mit dem ADT Binärbaum kann ein binärer Baum realisiert werden, der z.B. bei der Huffman-Kodierung verwendet wird:

Die Daten in einem Binärbaum werden nicht wie in einer dynamischen Reihung hintereinander in einer Liste gespeichert. Ein Element des Binärbaums (ein Knoten) hat einen Vorgänger und zwei Nachfolger. Dadurch kann eine Datenstruktur entstehen, bei welcher die Tiefe eines Teils des Baums ausgewertet werden kann. Zum Beispiel entscheidet bei der Huffman-Kodierung die Tiefe eines Zweigs des Binärbaums, wie lang der Code für ein Zeichen in der zu komprimierenden Zeichenfolge ist, das sich am Ende des Zweigs befindet.

Der Binärbaum selbst wird nicht als abstrakter Datentyp festgelegt, sondern der Knoten eines Binärbaums. In JavaScript kann der ADT Binärbaum für einen Knoten des Binärbaums wie folgt realisiert werden:

class BinTree {
  constructor(inhalt) {
    this.inhalt = inhalt;
    this.links = null;
    this.rechts = null;
  }  
  isLeaf() { return (this.links === null && this.rechts === null); };
  getLeft() { return this.links; };
  getRight() { return this.rechts; };
  setLeft(knot) { this.links = knot; };
  setRight(knot) { this.rechts = knot; };
  getItem() { return this.inhalt };
  setItem(val) { this.inhalt = val };
}

Damit ein Binärbaum entstehen und auch ausgegeben werden kann, müssen einige Algorithmen ergänzt werden. Im folgenden wird beispielhaft gezeigt, wie eine Objektschablone (Klasse) gewichteterSortierterBinaerBaum() für einen sortierten gewichteten Binärbaum programmiert werden kann. Dabei bedeutet:

  • sortiert: wenn ein neuer Wert in den Binäbaum eingefügt wird, kommt er nach links, wenn er kleiner als der Wert im Knoten ist. Ist er größer als der Wert im Knoten, kommt er nach rechts. Auf diese Weise wird der richtige Platz im Binärbaum für den neuen Wert gesucht.

  • da die Eingabe von Werten in einen sortierten Binärbaum oft zufällig ist, kann ein ungewichteter Binärbaum unsymmetrisch aussehen:

  • Bei einem gewichteten Binärbaum werden Methoden ergänzt, mit welchen die Werte im Binärbaum so verteilt werden, dass der Baum möglichst symmetrisch relativ zur Wurzel ist:

Eine Klasse gewichteterSortierterBinaerBaum() kann mit Hilfe des ADTs Binärbaum wie folgt festgelegt werden:

class BinTree {
  constructor(inhalt) {
    this.inhalt = inhalt;
    this.links = null;
    this.rechts = null;
  }  
  isLeaf() { return (this.links === null && this.rechts === null); };
  getLeft() { return this.links; };
  getRight() { return this.rechts; };
  setLeft(knot) { this.links = knot; };
  setRight(knot) { this.rechts = knot; };
  getItem() { return this.inhalt };
  setItem(val) { this.inhalt = val };
}

class gewichteterSortierterBinaerBaum {
  constructor() {
    this.wurzel = null;
  }
  knotenEinfuegen(knoten, neuerKnoten) {
    if (neuerKnoten.getItem() < knoten.getItem()) {
      if (knoten.getLeft() === null) { knoten.setLeft(neuerKnoten); }
      else { this.knotenEinfuegen(knoten.getLeft(), neuerKnoten); }
    }
    if (neuerKnoten.getItem() > knoten.getItem()) {
      if (knoten.getRight() === null) { knoten.setRight(neuerKnoten); }
      else { this.knotenEinfuegen(knoten.getRight(), neuerKnoten); }
    }
  };
  inhaltEinfuegen(inhalt) {
    var neuerKnoten = new BinTree(inhalt);
    if (this.wurzel === null) { this.wurzel = neuerKnoten; }
    else { this.knotenEinfuegen(this.wurzel, neuerKnoten); }
  };
  findeMinKnoten(knoten) {
    if (knoten.getLeft() === null) return knoten;
    else return this.findeMinKnoten(knoten.getLeft());
  };
  knotenEntfernen(knoten, zahl) {
    if (knoten === null) { return null;
    } else if (zahl < knoten.getItem() && knoten.getLeft() != null) {
        knoten.setLeft(this.knotenEntfernen(knoten.getLeft(), zahl));
        return knoten;
    } else if (zahl > knoten.getItem() && knoten.getRight() != null) {
        knoten.setRight(this.knotenEntfernen(knoten.getRight(), zahl));
        return knoten;
    } else if (zahl === knoten.getItem()) {
        if (knoten.getLeft() === null && knoten.getRight() === null) {
          knoten = null; return knoten;
        }
        if (knoten.getLeft() === null && knoten.getRight() != null) {
          knoten = knoten.getRight(); return knoten;
        }
        if (knoten.getRight() === null && knoten.getLeft() != null) {
          knoten = knoten.getLeft(); return knoten;
        }
        if (knoten.getRight() != null && knoten.getLeft() != null) {
          var bleibtDa = this.findeMinKnoten(knoten.getRight());
          knoten.setItem(bleibtDa.getItem());
          knoten.setRight(this.knotenEntfernen(knoten.getRight(), bleibtDa.getItem()));
          return knoten;
        }
    } else return knoten;
  }
  inhaltEntfernen(inhalt) {
    this.wurzel = this.knotenEntfernen(this.wurzel, inhalt);
  };
  maxTiefefunction() {
    var tiefeBerechnen = function(knoten) {
      if (knoten === null) return 0;
      return Math.max(1 + tiefeBerechnen(knoten.getLeft()), 1 + tiefeBerechnen(knoten.getRight()));
    }
    return tiefeBerechnen(this.wurzel);
  };
  knotenArrSpeichern(knoten, knotenArr) {
    if (knoten == null) return;
    this.knotenArrSpeichern(knoten.getLeft(), knotenArr);
    knotenArr.push(knoten);
    this.knotenArrSpeichern(knoten.getRight(), knotenArr);
  };
  bGewichtHelfer(knotenArr, start, ende) {
    if (start > ende) return null;
    var mitte = parseInt((start + ende)/2, 10);
    var knoten = knotenArr[mitte];
    knoten.setLeft(this.bGewichtHelfer(knotenArr, start, mitte - 1));
    knoten.setRight(this.bGewichtHelfer(knotenArr, mitte + 1, ende));
    return knoten;
  };
  baumGewichten(wurzel) {
    var knotenArr = [];
    this.knotenArrSpeichern(wurzel, knotenArr);
    var n = knotenArr.length;
    return this.bGewichtHelfer(knotenArr, 0, n-1);
  };
};

In der Klasse gewichteterSortierterBinaerBaum sind einige rekursive Methoden enthalten. Eine rekursive Methode ruft sich selbst bei der Ausführung des Programms auf. Mit Hilfe des rekursiven Programmieransatzes kann ein Binärbaum gebaut werden, bei welchem zum Zeitpunkt der Festlegung des Binärbaums unbekannt ist, welche Tiefe er haben wird. Ausgegeben wird der Binärbaum mit der Methode bDrucker(asb, xT, yT, level, dX), die ebenfalls eine rekursive (sich selbst aufrufende) Methode ist, damit ein unsymmetrischer Binärbaum unbekannter Tiefe ausgegeben werden kann:

function bDrucker(asb, xT, yT, level, dX) {
  let yDeltaD = 15;
  let yDL = 0;
  if (asb.rechts != null) {
    yDL = yDeltaD*level;
    push();
      stroke(47, 79, 79, 150);
      strokeWeight(4);
      line(xT, yT, xT+dX, yT+yDL);
    pop();
    bDrucker(asb.rechts, xT+dX, yT+yDL, level+1, dX/2);
  }
  if (asb.links != null) {
    yDL = yDeltaD*level;
    push();
      stroke(112, 128, 144, 150);
      strokeWeight(4);
      line(xT, yT, xT-dX, yT+yDL);
    pop();
    bDrucker(asb.links, xT-dX, yT+yDL, level+1, dX/2);
  }
  fill(255, 255, 255, 150);
  ellipse(xT, yT, 32, 32);
  fill(0);
  textSize(14);
  textAlign(CENTER);
  text(asb.inhalt, xT, yT+6);
}

Angelegt wird ein sortierter Binärbaum mit folgender Anweisung:

let binaerBaumVar = new gewichteterSortierterBinaerBaum();

In den Binärbaum werden mit folgender Anweisung 60 Elemente sortiert eingefügt:

for (var count = 0; count < 60; count++) {
  binaerBaumVar.inhaltEinfuegen((mathRandomInt(1, 100)));
}

Mit folgender Anweisung wird der sortierte Binärbaum gewichtet, was bedeutet, dass die Elemente symmetrisch zur Wurzel angeordnet werden:

binaerBaumVar.wurzel = binaerBaumVar.baumGewichten(binaerBaumVar.wurzel);

Ein funktionsfähiges Beispiel für einen sortierten gewichteten Binärbaum ist folgendes Programm. Entfernt man die Zeile 115

binaerBaumVar.wurzel = binaerBaumVar.baumGewichten(binaerBaumVar.wurzel);

indem man z.B. zwei Schrägstriche davor setzt, dann entsteht ein ungewichteter sortierter Binärbaum.

In einem neuen Fenster starten: ADT Binärbaum