Zum Menü springen.

Übungsblatt 6: Dynamische Datenstrukturen

Nachtrag: Aufgabe 5-1 Teil (a)

Verwenden Sie die Java-Anwendung „MsaRacer“ zur Analyse des Laufzeitverhaltens der vier implementierten Lösungsverfahren des Maximum–Sub-Array–Problems. Die Anwendung besteht aus einem Java-Archiv, in dem alle .class- und .java-Dateien gebündelt sind. Starten Sie die Anwendung durch Doppelklick auf die .jar-Datei oder durch folgenden Kommandozeilen-Befehl:
$ java -jar MsaRacer.jar

Ergänzend können Sie das Java-Werkzeug „MsaTimer“ auf der Kommandozeile wie folgt benutzen:
$ java MsaTimer Klassenname Arraylänge > /dev/null

Die Klasse MsaTimer finden Sie zusammen mit der Anwendung „MsaRacer“ bei den Maximum–Sub-Array–Unterlagen.

Aufgabe 6-1

In ihrer einfachsten Form besteht eine nicht-leere lineare Liste aus nichts weiter als einem Wert („Kopf“ der Liste, hier eine Ganzzahl) und einem Verweis auf die Liste der restlichen Werte („Rumpf“).

Implementieren Sie eine Klasse LinearList mit genau diesen beiden Feldern. Nennen Sie den Kopf head und den Rumpf tail. Ziehen Sie auch die Einführung zum Kapitel 5 „dynamische Datenstrukturen“ der Vorlesung „Algorithmen und Datenstrukturen 1“ zu Rate.

Aufgabe 6-2

Die folgenden Teilaufgaben beziehen sich auf Ihre Lösung aus Aufgabe 6-1 und auf die bereitgestellte Klasse MutableLinearList, die Ihre Lösung durch Vererbung erweitert.

  1. MutableLinearList ist eine lineare Liste mit zusätzlichen Objektmethoden zum Verändern und Abfragen der Liste. Studieren Sie wenigstens eine dieser Methoden so weit, dass Sie ihre Funktionsweise detailliert beschreiben können.
    Merke: Nicht das Was ist am wichtigsten, sondern das Warum!
  2. Schreiben Sie eine Methode start(), in der eine lineare Liste vom Typ MutableLinearList erzeugt wird. Die Liste soll genau die drei Elemente 42, 8 und 15 in dieser Reihenfolge haben.
  3. In Java stellt das Paket java.util einen ganzen Sack voll mit verschiedenen dynamischen Datenstrukturen zur Verfügung. Die Klasse java.util.LinkedList ist eine fertige Implementierung einer doppelt verketteten linearen Liste. Finden Sie heraus, welche Methoden(aufrufe) in LinkedList denen in MutableLinearList am ehesten entsprechen.

Aufgabe 6-3 *

Verwenden Sie eine LinkedList zur Implementierung eines Stapels für Strings. Ihr Stapel soll eine eigene Klasse sein mit den beiden Objektmethoden push(String) und pop().

Zusatzaufgabe 6-4

Schreiben Sie ein Programm, welches das Problem der „Türme von Hanoi“ für eine beliebige Scheibenanzahl lösen kann. Ihr Programm soll für die interne Modellierung der drei Pfosten drei Instanzen Ihres Stapels aus Aufgabe 6-3 verwenden. Bei jeder Bewegung soll Ihr Programm eine Ausgabe der folgenden Art erzeugen:
Scheibe n von Pfosten x nach Pfosten y

(Bonus-Punkte für eine graphische Darstellung!)

$Id: HEADER.html,v 1.3 2007/12/11 20:08:46 arne Exp $