back to top   1 Rekursion

 

Eine interessante Anwendung der bisher dargestellten Konzepte Iteration und Methoden bieten rekursive Algorithmen.
Bekannte Beispiele für die Anwendung der Rekursion sind u.a.:
Fakultät n!:
n! = n * (n-1)!   für n >= 2
n! = 1   für n = 1

Fibonacci-Zahlen f(n):
f(n) = f(n-2) + f(n-1)     für n >= 3
f(n) = 1   für n = 1, 2

Generell lassen sich rekursiv formulierbare Problem sowohl rekursiv als auch iterativ lösen. Unter Implementierungsgesichtspunkte ist jedoch die iterative Variante schwieriger umzusetzen und zu überblicken. Jedoch ist ihr Zeitverhalten dem der aufwendigeren Rekursion -- insbesondere bei aufwendigen Berechnungen -- überlegen.
Mit hilfe der Rekursion lassen sich viele Algorithmen kurz und elegant formulieren. Für die rechnertechnische Umsetzung hingegen stellt die Realisierung der Rekursion zusätzlichen aufwand (insbesondere bei hoher Rekursionstiefe) durch den zusätzlichen Speicherplatzaufwand (Stack!) dar.

Die Rekursion benötigt meist einen Kellerspeicher (engl. Stack). In diesem Kellerspeicher werden die einzelnen Funktionsaufrufe gespeichert. Man kann also davon ausgehen, daß in diesem Speicher der gesamte Verlauf des "Prozesses" gespeichert ist. Bei einem iterativen Programm spiegeln die einzelnen Variablen den Zustand des Berechnungsprozesses wieder - bei der Rekursion ist dieser Zustand über den gesamten Kellerspeicher verteilt. Würde man eine Berechnung anhalten und zu einem späteren Zeitpunkt weiterführen wollen, so müßte man sich bei einem iterativen Programm nur die Werte der Variablen merken, bei einem rekursiven Programm benötigt man auch noch den Inhalt des Kellerspeichers.

Beispiel 16 (Rekursive Realisierung der Fakultätsberechnung):


int fakultaet(int n)
{
   if ( n == 1 )
   {
      return  1;
   } //end if
   else
   {
      return  n * fakultaet(n-1); //calling fakultaet recursively!
   } //end else
} //end fakultaet()

Ablaufbeispiel:


(fakultät 6)
(* 6 (fakultät 5))
(* 6 (* 5 (fakultät 4)))
(* 6 (* 5 (* 4 (fakultät 3))))
(* 6 (* 5 (* 4 (* 3 (fakultät 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (fakultät 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720

Beispiel 17 (Iterative Realisierung der Fakultätsberechnung):


int fakultaet(int n)
{
   int i,
   int fak = 1;

   for ( i=2; i<=n; i++ )
   {
      fak *= i;
   } //end for
   return fak;
} //end fakultaet

Ablaufbeispiel:
Aufruf: fakultät 6

i
fak
n
1
1
6
1
2
6
2
3
6
6
4
6
24
5
6
120
6
6
720
7
6

Die Information über den Prozeßfortschritt wächst in der rekursiven Variante kontinuierlich. Bei der iterativen Variante bleibt sie konstant. Bei vielen Programmiersprachen wäre die zweite, iterative Variante aber auch nicht sparsamer mit dem Speicherverbrauch, da die ständigen Funktionsaufrufe im Keller gespeichert würden. Hier hätte man nur einen Vorteil mittels do...while und for. Doch es gibt Interpretierer, die diesen Mangel nicht aufweisen. Deshalb kann die Rekursionsvariante genauso sparsam wie die iterative Methode mit dem Speicher umgehen -- sie tut es nur im Allgemeinen nicht.
Generell bleibt festzuhalten: die Rekursion eignet sich in hervorragender Weise als Denk- und Anschauungsmodell, jedoch kann es in der konkreten Umsetzung gute Gründe (Speicherplatzbedarf, zu erwartende Laufzeit) geben, die für die iterative Implementierung sprechen.

Abschliessend sei noch das Problem unendlicher Rekusion angerissen. Dies tritt z.B. auf, wenn einen Rekursionsendpunkt übersehen wurde. Hier könnte als Überwachungshilfsmittel bei jedem Funktionsaufruf die Rekursionstiefe als Parameter übergeben werden. Mittels dieses Sicherheitszähler wäre es möglich, die Rekursion bei einer bestimmten Tiefe kontrolliert abzubrechen.

Weitere verbreitete Anwendungen rekursiver Vorgehensweisen sind der Sortieralgorithmus QuickSort sowie Baumtraversierungen und das recursive descent Verfahren im Compilerbau.

back to top   2 Elementare Datenstrukturen

 

Im folgenden Teilkapitel werden die Grundlagen elementarer Datenstrukturen, welche die Basis vielfältigster Anwendungsgebiete bilden, einführend erläutert.

2.1 Statische Datenstrukturen

Statische Datenstrukturen sind solche, die von der Problemgröße -- d.h. dem zu erwartenden Datenumfang des zu lösenden Problems -- unabhängig sind.
Dieser Typ beansprucht einen konstant großen Hauptspeicheranteil, unabhängig von der tatsächlichen Nutzung. Hieraus ergeben sich drei prinzipielle Fälle:

  1. Die verarbeiteten Daten beanspruchen exakt den reservierten Speicherplatz
  2. Die verarbeiteten Daten beanspruchen den reservierten Speicherplatz nicht vollständig
  3. Die verarbeiteten Daten beanspruchen mehr als den reservieren Speicherplatz

Rein intuitiv ergibt sich bereits der Eindruck, dass Fall 1 das Optimum mit den zur Verfügung stehenden Mitteln darstellt. Ebenfalls augenscheinlich ist dabei, dass dies nur äußerst selten eintreten dürfte; insbesondere wenn nicht alle jemals durch das Programm zu verarbeiten Daten bereits zum Programmerstellungszeitpunt bekannt sind.
Fall 2 zeichnet sich durch ein gewisses Maß an Ineffizienz aus. Es wird durch den Speicherverschnitt, also die Differenz zwischen reserviertem und tatsächlich benötigtem Hauptspeicheranteil, charakterisiert. Die Applikation ist aber in jedem Falle lauffähig, jedoch kann ihr (unnötiger) Speicherkonsum negative Seiteneffekte auf andere ausgeführte Programme haben.
Im dritten Fall kann das Programm nicht auf den beabsichtigten Daten ausgeführt werden, da nicht genügend Speicherplatz zur Verfügung steht.

Im aufgezeigten Spannungsfeld bewegt sich üblicherweise der Einsatz statischer Datenstrukturen. Es gilt deshalb bereits in der Designphase abzuwägen, ob dieser Datenstrukturtyp gewählt werden sollte.
Eindeutig für statische Datenstrukturen spricht ihre leichte Handhabbarkeit und geringer Verwaltungsaufwand.

Das (uns) bekannteste Beispiel einer rein statischen Datenstruktur ist die Klasse. Zur Definitionszeit wird dort statisch ein maximal zur Verfügung stehender Speicherplatz angegeben. Dieser Speicherplatz läßt sich grob aus der Summe der definierten Attribute berechnen. Für jedes Objekt einer Klasse wird zum Erzeugungszeitpunkt genau die durch die Klassendefinition vorgegebene Speicherplatzmenge reserviert. Dieser Speicheranteil wird unabhängig von der tatsächlichen Nutzung über die gesamte Lebensdauer jedes Objekts durch das System angeboten.

Beispiel 4


   public class Person
   {
      long     personalausweisNr;
      Datum    geburtsdatum;
   } //end class Person

   public class Datum
   {
      byte tag;
      byte monat;
      int jahr;
   } //end class Datum
   

Der Speicherplatzbedarf eines nach der Klassendefinition aus Beispiel 4 erzeugten Personen-Objekts errechnet sich wie folgt:

   Speicherplatz(Person) = Speicherplatz(personalausweisNr) + Speicherplatz(geburtsdatum)
                         = Speicherplatz(long)              + Speicherplatz(Datum)
                         = 64 Bit                           + Speicherplatz(tag)+Speicherplatz(monat)+Speicherplatz(jahr)
                         = 64 Bit                           + Speicherplatz(byte)+Speicherplatz(byte)+Speicherplatz(int)
                         = 64 Bit                           + 8 Bit + 8 Bit + 32 Bit
                         = 112 Bit
                         = 14 Byte.
   

Dieser Speicherplatzbedarf ist konstant für alle Ausprägungen von Person; unabhängig davon, ob der tatsächliche Inhalt auch mit weniger Platz dargestellt werden könnte.

Die wichtigste Datenstruktur statisch definierter Größe ist das Feld -- oder der Array. Ein Array ist eine in ihrer Größe unveränderliche Liste von gleichartigen Elementen.

Java-Syntax:
Eine Array ist strukturelle identisch den skalaren Datentypen. Jedoch mit zwei wesentlichen Unterschieden: Zum Ersten werden als syntaktische Kennzeichnung dem Typ oder dem gewählten Variablen- oder Attributnamen leere eckige Klammern nachgestellt. Zum Zweiten muß eine explizite Speicherplatzreservierung durch den new-Operator vorgenommen werden.


   int[] numbers;
   numbers = new int[100];
   

Definiert unter dem Namen numbers einen Array zur Aufnahme von int-Werten. Der new-Operator reserviert Speicherplatz zur Aufnahme von 100 int-Werten.

In der Erstellungsphase werden durch den new-Operator alle Elemente des Arrays automatisch initialisiert (mit 0 für Zahlen-artige (d.h. numerische) Arrays, false bei boole'schen, '\0' bei char-Arrays und null bei allen sonstigen).

Alternativ kann ein Array auch durch implizite Größenangabe definiert werden. Hierzu ist es notwendig alle aufzunehmenden Werte zu kennen, und in der Definition anzugeben.

Beispiel 5:


   String[] Städte = {"Augsburg", "Ulm", "München", "Berlin"};
   

Definiert implizit einen Array mit vier Speicherplätzen zur Aufnahme von String-Objekten. Die Erstbelegung ist durch die angegebenen Werte vorgenommen.

Der Zugriff auf Arrayelemente geschieht durch Angabe des Speicherplatzes in eckigen Klammern. Zur Beachtung: der erste Speicherplatz trägt die Nummer 0!


   if (Städte[2] == "München")
   { ...
   

Greift auf das dritte Arrayelement zu.
Erfolgt ein Zugriff auf ein nicht definiertes Arrayelement, d.h. außerhalb der fest definierten Grenzen, so lößt das Laufzeitsystem eine ArrayIndexOutOfBoundsException aus, sofern der Compiler nicht bereits zum Übersetzungzeitpunkt den Fehler entdecken konnte.

Basierend auf dem bisher gezeigten lassen sich auch Arrays von Arrays oder Multiarrays definieren. Dies geschieht durch Angabe eines weiteren Paares aus leeren eckigen Klammern für jede gewünschte Dimension.

Beispiel 6:


   int[][] tageEinesJahres = new int[12][31];
   

Die Anweisung in Beispiel 6 reserviert Speicherplatz für 12*31 int-Werte. Der Zugriff erfolgt analog den eindimensionalen Arrays. So addressiert tageEinesJahres[4][12] im vierten Array (erste Dimension) das 12 Element. Absolut handelt es sich dabei um das Element mit Nummer 104 (wg. 3*31+12-1)

2.2 Dynamische Datenstrukturen

Im vorangegangenen Kapitel wurde bereits mit der Klasse java.util.Vector eine dynamische Datenstruktur zur Realisierung von Beziehungen mit Maximalmultiplizität größer 1 verwendet.

Definition:dynamische Datenstruktur
ist eine Datenstruktur aus statischen Elementen, die durch im Programm abgelegte Routinen dynamisch zur Ausführungszeit der Applikation an die Problemgröße angepaßt werden kann.

Basisprinzip aller im Folgenden diskutierten dynamischen Datenstrukturen ist der mehrfache Einsatz typ- und damit strukturgleicher Elemente. Mit anderen Worten: Das integrierte Zusammenspiel mehrerer Ausprägungen derselben Klasse.
Ein wesentliches Klassifierungsmittel wird mithin zunächst die Ausgestaltung des Zusamenspiels der Objekte, und erst zweitranging deren intern (nur leicht variierende) Struktur sein.

2.2.1 Verkettete Listen

Die wichtigste dynamische Datenstruktur ist die verkette Liste. Sie existiert in verschiedenen Ausprägungen u. a. als einfach und doppelt (oder allgemein als mehrfach) verkettete Liste.

Klassendefinition eines Elements einer verketteten linearen Liste


   class Node
   {
      Object   content;
      Node     next;
   } //end class Node
   

Die Abbildung zeigt die Definition eines Elements (auch: Knoten (engl. Node)) einer verketteten Liste.

Eine solche Liste bietet Platz zur Aufnahme einer Menge von einzelnen Datenelementen. In der Klassendefinition durch das Attribut content ausgedrückt. Die interne Strukturierung dieses Datums ist nicht näher festgelegt, deshalb wurde im vorliegenden Beispiel mit der Klasse Object der allgemeinste in Java verfügbare Strukturtyp als Datentyp des Attributs festgelegt.
Ein zusätzliches Attribut vom Knotentyp selbst ermöglicht die Bildung der Strukturbeziehung, konkret die Vernetzung der einzelnen Informationsträger.

Beispiel 7:


   package LinearListPkg;

   public class LinearList
   {
      private Node first=null;
      private Node mostRecent=null;

      public void addNode(Object newContent)
      {
         Node newNode = new Node();
         newNode.setContent(newContent);

         if (mostRecent != null)
         {
            //appending node to an existing list
             mostRecent.setNext(newNode);
         } //end if
         else
         {
            //mostRecent == null => first node of list
            first = newNode;
         } //end else
         mostRecent = newNode;
         newNode.setNext(null);
      } //end addNode()
      public void deleteSpecificContent(Object contentToDelete)
      {
         Node currentlyProcessedNode = first;
         Node predecessorNode=null;

         while (currentlyProcessedNode != null)
         {
            if ( (((currentlyProcessedNode.getContent()).toString()).compareTo(contentToDelete.toString())) == 0 )
            {
               if ( predecessorNode != null )
               {
                  predecessorNode.setNext( currentlyProcessedNode.getNext() );
               } //end if
               else
               {
                  first = currentlyProcessedNode.getNext();
               } //end else
               Node node2delete = currentlyProcessedNode;
               node2delete = null;
               //currentlyProcessedNode = null; //delete node
            } //end if
            predecessorNode = currentlyProcessedNode; //save predecessor
            if (currentlyProcessedNode != null)
            {
               currentlyProcessedNode = currentlyProcessedNode.getNext();
            } //end if
         } //end while
      } //end deleteSpecificNode()
      public void printList()
      {
         Node currentlyProcessedNode;
         if (first != null)
         {
            //list exists
            currentlyProcessedNode = first;
            do
            {
               System.out.println( (currentlyProcessedNode.getContent()).toString() );
               currentlyProcessedNode = currentlyProcessedNode.getNext();
            }
            while (currentlyProcessedNode != null);
         } //end if
      } //end printList()
   } //end class LinearList

   class Node
   {
      private Object content;
      private Node   next;

      public Object getContent()
      {
         return content;
      } //end getContent()
      public void setContent(Object newContent)
      {
         content = newContent;
      } //end setContent
      public void setNext(Node newNext)
      {
         next = (Node) newNext;
      } //end setNext()
      public Node getNext()
      {
         return next;
      } //end getNext()
   } //end class Node
   

Einordnung von vier Listenelementen in eine zuvor erzeugte leere Liste.


   import LinearListPkg.LinearList;

   public class LinearListTest1
   {
      public static void main(String[] argv)
      {
         LinearList myList = new LinearList();
         myList.addNode( (Object) new Integer(1) );
         myList.addNode( (Object) new Integer(3) );
         myList.addNode( (Object) new Integer(2) );
         myList.addNode( (Object) new Integer(1) );

         myList.printList();

         myList.deleteSpecificContent( (Object) new Integer(1) );

         System.out.println("after deletion");

         myList.printList();

      } //end main()
   } //end class LinearListTest1

   

Die Ausgabe liefert:
1
3
2
1
after deletion
3
2

Die Abbildung illustriert die aufgebaute Datenstruktur als UML-Klassendiagramm.

Darstellung der aufgebauten verketteten Liste

Innerhalb jedes Node-Objekts wird die gespeicherte Information durch das Attribut content abgebildet. Das Attribut next verweist auf den nachfolgenden Listeneintrag, welcher ebenfalls wieder ein Node-Objekt ist. Der Listenabschluß wird durch ein null im Verweisfeld des letzten Objekts markiert.

Elementlöschung:
Die Löschung eines Elements vollzieht sich in zwei Schritten:

  1. Korrektur des Nachfolgerverweises
  2. Löschung des nicht mehr benötigten Objekts

Situation nach Umhängen der Next-Verweise

Zunächst werden die Verweise korrigiert, hierbei ist zwischen dem Fall des Löschens innerhalb der Liste und des Löschens des ersten Elements zu unterscheiden. Aus Praktikabilitätsgesichtspunkten nimmt das Kopfelement einer Liste eine Sonderstellung ein. Es dient generell als Listeneinstiegspunkt für auf der ganzen Liste operierende Zugriffe (z.B. Suche). Dieselbe Argumentation läßt sich auch zur Einräumung einer Sonderstellung des letzten Listenelementes heranziehen, sofern neue Elemente nur am Listenende angefügt werden. Hierbei ist es nur notwendig das neu erzeugte Node-Objekt mit dem letzten Listenelement zu verknüpfen. Zusätzlich ist in beiden Varianten für einige Operationen besonderer Aufwand, in Form zusätzlichen Speichers und zusätzlicher Zugriffe zur Konsistenzerhaltung, zu betreiben.

Neue Listenstruktur nach Elementlöschung

Nach Korrektur der Verweise können die abgekoppelten Objekte aus dem Speicher entfernt werden. Dies geschieht durch explizite Zuweisung der null an die entsprechende Referenz. Ergänzend ist noch das Verweisattribut des jetzt letzten Knotens auf den herausgehobenen Wert null -- das vereinbarte Symbol des Listenendes -- zu setzen.

Erweiterungen und spezielle Implementierungen:

Je nach Gestaltung der Verweise werden veschiedene Listengrundtypen unterschieden:

Doppelt verkettete Liste Dieser Listentyp führt grundsätzlich zwei Verweise mit, sowohl den bekannten Vorwärtszeiger, als auch einen zuätzlichen Rückwärtszeiger, der jeden Listenknoten mit seinem Vorgänger verbindet.

Doppelt verkettete Liste

Zyklische Listen Hier wird das Konzept der linearen Liste soweit verallgemeinert, das vom expliziten Beginn und Ende zugunsten eines vollständigen Zyklus abgegangen wird.

Einfach verkettete zyklische Liste

Analoges gilt für doppelt verkettete zyklische Listen.

Listenimplementierungen bilden die Grundlage vielfacher praktischer Anwendungsfälle und haben wegen der Allgemeinheit des Ansatzes gepaart mit der Leitungsfähigkeit des Konzepts große Verbreitung gefunden.

Bemerkungen:
Das vorgestellte Beispiel enthält keine Vereinbarungen über eine von der Einordnungsreihenfolge abweichende Sortierreihenfolge. Ebenfalls sind keine Restriktionen zur Behandlung des Neueinfügens bereits existierender Information gegeben. Auch spezifiziert die allgemeine lineare Liste keine eindeutige Mimik bei Löschung eines mehrfach auftretenden Wertes. Generell sind sowohl die Entfernung aller Einträge dieses Wertes, als auch nur die Beschränkung auf das erste Auftreten denkbar (das erste Vorgehen läßt sich durch mehrfaches Ausführen des zweiten umsetzen).
Die bei Listen auftretende ineffiziente Speichernutzung liegt auf dem unvermeidlichen Niveau der Teilnutzung der angebotenen Datentypen -- verkörpert durch das oder die Informationsattribut(e) -- und die Verweise. Ist aber dennoch der starren statischen Variante vorzuziehen.

2.2.2 Bäume

Die bisher betrachteten dynamischen Datenstrukturen sind ihrem Wesen nach eindimensional. Bereits bei den statischen Datensturkturen sind mit den mehrdimensionalen Feldern höherdimensionale Strukturen eingeführt worden.
Ein flexibleres Analogon hierzu bilden die im Folgenden andiskutierten Bäume.

Im Grunde genommen erweitert ein Baum das aus den Listen bekannte Nachfolger-Verweiskonzept.

Prinzipieller Aufbau eines Baumknotens mit drei Kindknoten


   class Node
   {
      Object   content;
      Node     child1;
      Node     child2;
   } //end class Node
   

Die Erweiterung findet konkret in der Vervielfachung der zugelassenen Nachfolger ausdruck. Die Abbildung stellt die Klassendefinition eines Baumes zweiten Grades dar.

Zur Terminologie:
Die Elemente eines Baumes werden Knoten genannt. Der oberste Kntoen eines Baumes wird Wurzel (engl. root) genannt. Knoten lassen sich in Ebenen (Stufen) einteilen. Die Ebene eines Knotens ist die Anzahl der Knoten auf dem Pfad (bestehend aus den graphisch als Pfeil dargestellten Verweisen) von diesem Knoten zur Wurzel (ohne ihn selbst). Beispielsweise steht der Knoten mit dem Inhalt 12 auf Stufe 2.
Falls jeder Knoten eine bestimmte Anzahl von direkten Nachfolgern besitzen muss, die in einer vorherbestimmten Reihenfolge erscheinen, so wird ein solcher Baum n-ärer-Baum genannt (entsprechend im Falle von n=2: binärer Baum oder Binärbaum).
Knoten ohne Nachfolger (am Ende eines Pfades) werden Blattknoten, Knoten im Inneren eines Baumes (d.h. Knoten mit Nachfolger) entsprechend innere Knoten genannt.

Ein Binärbaum

Beispielbinärer Suchbaum
Ein binärer Suchbaum ist ein Binärbaum dessen Knoten (oder konkreter: Nachfolgerverweise) durch nachstehende Eigenschaft gekennzeichnet sind: Jeder einem Knoten nachgeordnete Linkenachfolgerknoten trägt einen kleineren Wert als der Knoten selbst. Jeder rechte Nachfolgerknoten einen größeren Wert als der akutelle Knoten selbst. Ausgenommen hiervon sind nur die Blattknoten, die keine Nachfolger besitzen.
Durch die Einordnung in einem solchen Baum entsteht eine geordnete Folge, die durch geeignetes Durchlaufen des Baumes geordnet ausgegeben werden kann.
Dieser Durchlauf kann folgendermassen umgesetzt werden:
Besuche zunächst absteigend den linkesten Knoten und gebe den dort gespeicherten Wert aus, steige anschliessend eine Stufe hinauf und gebe den dort abgelegten Wert aus, steige anschliessend rechts hinab und verfahre gemäß der beschriebenen Vorschrift.
Dieses Verfahren läßt sich durch einen rekursiven Dreizeiler leichter und auch verständicher ausdrücken:


   traverse(Node n)
   {
      if (n != null)
      {
         traverse( n.getLeft() );
         visit(n);
         traverse( n.getRight() );
      } //end if
   } //end traverse()
   

Für den Aufruf traverse(root) liefert es den gesamten Suchbaum in geordneter Reihenfolge.

2.3 Praktische Anwendungsfälle

Auf Basis der vorgestellten dynamischen und statischen Datenstrukturen lassen sich verschiedenste elementare Primitive, welche zur Lösung vielfälltiger Probleme eingesetzt werden können, realiseren.
Nachfolgend sollen hiervon einige kurz skizziert werden.

2.3.1 Stack/Stapel

Dynamische Datenstrukturen wie die in Punkt 2.2.1 dieses Kapitels vorgestellten verketteten Listen sind durch verschiedene Freiheitsgrade gekennzeichnet. Insbesondere ermöglichen Sie das Einfügen, Entfernen und den Zugriff auf beliebige Listenelemente. Stapel bilden eine auf Listen basierende Datenstruktur mit eingeschränktem Zugriff.
Ein Stack wächst nur nach oben, d.h. jedes mit push neu hinzugefügte Element oben auf dem Stapel abgelegt, entsprechend kann mit pop nur das aktuell oberste Element entnommen werden. Zugriffe auf Elemente innerhalb des Stapels sind in der Grundform nicht erlaubt.
Das erste bzw. letzte (oberste) Element eines Stapels wird mit bottom of stack bzw. top of stack bezeichnet.
Gemäß der durch push und pop ausgedrückten Mimik kann ein solcher Stapel auch als last in first out (Abk. LIFO) Liste bezeichnet werden.

Auf einem Stapel können nur zwei Grundoperationen ausgeführt werden:

Stack mit fünf Elementen und Darstellung der beiden Elementaroperationen push und pop

Die Abbildung zeigt einen Stack mit fünf Elementen, sowie die beiden zugelassenen Elementaroperationen push und pop.

Anwendungsbeispiel Berechnung arithmetischer Ausdrücke:
Mithilfe von Stacks lassen sich beliebig lange arithmetische Ausdrücke berechnen.
Der in der Abbildung dargestellten Stapelzustände spiegeln die Stadien der Ausdrucksberechnung wider.
Zu berechnen: 3+5*7/4-1 (ohne Berücksichtigung der Operatorpräzedenzen).
Allgemeines Vorgehen:

  1. Ablegen der Operanden und des Operators
  2. Berechnung und Ablage des (Teil-)Ergebnisses

Die Existenz einer Einlesereoutine, innerhalb der bereits eine geeignete Eingabeprüfung durchgeführt wird, ist vorausgesetzt.
Eine mögliche Implementierung der Berechnungsroutine könnte wie folgt gestaltete sein:


   double calculate(double op1, char operator, double op2)
   {
      switch(operator)
      {
         case '+': return (op1+op2);
                   break;
         case '-': return (op1op2);
                   break;
         case '*': return (op1*op2);
                   break;
         case '/': return (op1/op2);
                   break;
      } //end switch
   } //end double()
   

Die Berechnung erfolgt sukzessive durch push(), push(), push(), push(calculate(pop(),pop(),pop)), ... solange bis keine Eingabeoperanden mehr zur Verfügung stehen. Das Resultat ist auf dem Stack abgelegt.
Die Abbildung zeigt die verschiedenen Stapelzustände

Berechnung des arithmetischen Ausdrucks 3+5*7/4-1 (ohne Berücksichtungung der Präzedenzen) mithilfe eines Stacks

2.3.2 Queue/Schlange

Eine weitere elementare Datenstruktur, die durch Einschränkungen aus linearen Listen hervorgeht, ist die Schlange oder engl. Queue.
Sie unterscheidet sich von den aus Abschnitt 2.3.1 bekannten Stacks lediglich durch die Ausgestaltung der bei Stacks als push und pop bezeichneten Einfüge- bzw. Entnahmeoperation.
Eine Schlange ist eine durch die Einordnungsreihenfolge geeordnete Datenstruktur, aus der gemäß der Eintrittsreihenfolge Elemente einzeln entommen werden können. Dieses Charakteristikum nennt man auch first in first out (Abk. FIFO). Es entspricht dem intuitiv von einer Warteschlange (ohne Vordrängler und entmutigte Wartende) erwarteten Aussehen.

2.3.3 Heap/Halde

Die bisher dargestellten Datenstrukturen zeichnen einerseits durch ihre Mächtigkeit (resultierend aus der Allgemeinheit in der die Struktur und die darauf ablaufenden Operationen beschrieben sind) und andererseits durch ihre Anschaulichkeit aus. Zwar ist das Denkmodell eines binären Baumes anschaulich und auch in der Programmiersprache adäquat umsetzbar, da auch hier mehrdimensionale und netzartige Strukturtypen zugelassen sind. Jedoch gerät die intuitive Umsetzung bei der beabsichtigen Speicherung auf einem Sekundärspeichermedium (Diskette, Festplatte, CD,...) schnell an ihre Grenzen. All diesen Medien ist das Unvermögen der Speicherung netzartiger Datenstrukturen in Dateien gemein.

Allgemein läßt sich dieses Problem auf eine bijektive Abbildung zwischen beliebig strukturierter Eingangsdatenstruktur und zwangsweise linear strukturierter Zieldatenstruktur reduzieren. Wichtig hierbei (deshalb auch die Forderung nach Bijektivität) ist die Wiedergewinnungsmöglichkeit aus dem linearisierten Pendant.

Ein mögliches Vorgehen soll am Beispiel des besprochenen Binärbaums illustriert werden.

Besuchsreihenfolge der Baumknoten

Zunächst wird eine Abspeicherungsreihenfolge für den Baum gewählt. Gemäß dieser Reihenfolge werden die existierenden Knoten traversiert und ihre Nutzinformation abgespeichert. Die angelegten Verweise werden duch die Abbildung auf das Speichermedium in eine andere Form überführt.
Als Besonderheit müssen auch die nicht existierenden Knoten in die Betrachtung einbezogen werden, um eine einfachere Zuordnung zwischen Sekundärspeicher- und Hauptspeicherstruktur zu erhalten. Hierzu wird die Information der nicht vorhandenen Knoten auf einen reservierten Wert gesetzt (z.B. null).

Eine mögliche Darstellung zum Ausdrucks des Baums ist mithilfe eines Arrays dargestellt:

Darstellung eines binären Baums als Array

Auch in dieser Speicherstruktur bleiben die Grundcharakteristika gewahrt. So können die Kinder eines Knotens der im Feld mit Index n abgelegt ist als 2n bzw. 2n+1 angesprochen werden.

back to top   3 Speicherverwaltung

 

3.1 Referenzen

In Kapitel II wurde mit dem new-Operator der Mechanismus zur Erzeugung eineObjekts vorgestellt. Dieser Operator stellt die einzige Möglichkeit dar, innerhalb eines Java-Programmes Speicherplatz zur Aufnahme eines neuen Objekts anzufordern. Dieser -- auch Allokation genannte -- Vorgang ist klar gegenüber der Erzeugung einer Referenz auf ein bestehendes Objekts abzugrenzen.

DefinitionReferenz:
Eine Referenz ist eine Variable eines Typs, die auf einen Speicherplatz verweist, der einen Wert dieses Typs (oder eines kompatiblen Typs) beinhaltet.

Während der linken Seite eines new-Operators immer eine Referenz auf einen neuen, d.h. bisher innerhalb des Programms nicht benutzten, Speicherplatz zugewiesen wird, führt die Platzierung eines Objekts auf der rechten Seite eines Ausdrucks zur Zuweisung dieser Adresse an die linke Seite.

Beispiel 8:


   Integer myFirstInt;
   Integer mySecondInt = new Integer(84); //object creation!
   Integer myThirdInt;

   myFirstInt = new Integer(42); //object creation!

   myThirdInt = new Integer(100); //object creation!

   myThirdInt = mySecondInt;
   

Das Codefragment deklariert zunächst drei Variablen vom selben Typ java.lang.Integer. mySecondInt wird direkt nach der Deklaration mit einem neu erstellten Objekt initialisiert, die Variable erhält einen Speicherplatz zugewiesen, in dem der Wert 84 abgelegt wird.
Anschließend wird der bereits deklarierten Variable myFirstInt ein neu erzeugtes Objekt zugewiesen. Analog für die Variable myThirdInt.
Durch die bekannte Zuweisung eines existierenden Objekts an den Speicherplatz eines gültigen Typs wird ein neuer Verweis auf den bereits existierenden Speicherplatz unter anderem Namen angelegt.
Die einzelnen Schritte sind im Zeitablauf geordnet in unterstehender Abbildung dargestellt.

Zeitliche Abfolge der Speicherzuweisungen und -belegungen

3.2 Speicherverwaltung und -bereinigung

Die in obenstehender Abbildung illustrierte Endsituation zeigt dem Objekt myFirstInt, das auf den ursprünglich definierten Speicherplatz verweist auch zwei Variablen (oder Objekt-Referenzen), die auf denselben Speicherplatz zeigen (mySecondInt und myThirdInt).
Auffallend jedoch ist, dass Verweis mehr auf den Speicherplatz mit dem Wert 100 existiert. Folglich kann auch dieser Speicherplatz über kein Attribut und keine Variable des Java-Programms angesprochen werden.

Definitiongarbage:
Diese "herrenlosen" (besser: referenzlosen) Speicherplätze, die zwar durch das Programm erzeugt wurden, jedoch nicht mehr durch es zugreifbar sind, werden als garbage (nach dem engl. Wort für Abfall) bezeichnet.

Als Lösung des aus der Ansammlung von Speichermüll während der Programmausführung resultierenden Problems bietet sich ein explizites Freigabekonstrukt an. Verschiedene Programmiersprachen (wie C/C++, Pascal) bieten solch einen Aufruf an.
Allerindings behebt dies nur die Speicherplatzverschwendung für Hauptspeicher-Ressourcen die bekanntermaßen nicht mehr benötigt werden. Jedoch stellt bietet es keinen Schutz vor der im Beispiel eingetretenen Situation. Dort wird eine Referenz umgesetzt, hierdurch wird das angelegte Objekt im Hauptspeicher nicht mehr erreichbar. Es entsteht ein Speicherleck (engl. memory leak) -- der reservierte Speicher ist innerhalb des Programmablaufs unwiederbringlich verloren.
Ein pauschales Löschen des Objekts im Hauptspeicher ist nicht praktikabel, da sich im Programm nicht ermitteln läßt ob noch andere Verweise auf das Objekt existieren. Diese würden durch ein vorschnelles Löschen ungültig (sog. dangling references); was zu schweren Programmfehlern (durch Zugriff auf einen nicht existierenden Speicherplatz) führen kann. Ist die erwähnte Referenz hingegen einmal verändert, bietet die Programmiersprache keine Handhabe zur Löschung des nun (offensichtlich) nicht mehr benötigten Speicherplatzes.

Als Ausweg dieses Dilemmas bietet sich lediglich eine Übertragung der Verantwortung von der Programmierspache an das Laufzeitsystem, welches die Speicherplatzverwaltung übernimmt, an.
Diese als automatic garbage collection bekannte Mimik ist in den Java-Interpretern umgesetzt. Ein Teil des Interpreters prüft zyklisch den gesamten verwalteten Speicher auf nicht mehr erreichbare Speicherplätze, und gibt diese im Bedarfsfalle automatisch frei.
Der Programmierer hat (nahezu) keinerlei Möglichkeit in diesen Automatismus einzugreifen. Lediglich der Aufruf System.gc() ermöglicht es innerhalb des Java-Codes die sofortige Speicherbereinigung vorzuschlagen -- die Entscheidung über die tatsächliche Ausführung zum gegebenen Zeitpunkt obliegt weiter dem Laufzeitsystem. Hintergrund dieser Restriktion ist die Zielsetzung ein möglichst konstantes Laufzeitverhalten zu gewährleisten. Aus diesem Grunde werden Läufe des garbage collectors in Zeitfenster verlagert, in denen wenig Programmaktivitäten den Hauptspeicher beanspruchen (z.B. Ein-/Ausgabebehandlung).




separator line
Service provided by Mario Jeckle
Generated: 2004-06-07T12:31:55+01:00
Feedback Feedback       SiteMap SiteMap
This page's original location This page's original location: http://www.jeckle.de/vorlesung/sei/kIV.html
RDF metadata describing this page RDF description for this page