Algorithmen und Programmierung III 

         WS 2002/2003                   Übung 6                          H. Schweppe
        

        Ausgabe: 21.11.2002
        Abgabe:     3.12.2002  16.00

Aufgabe 6.1 ( 10  P)  
a) (5) Gesucht ist eine "dynamische Implementierung" von Vektoren mit Hilfe von Feldern ohne Kopieroperationen bei Vergrößerung des Vektors. Die Schnittstelle lautet: 
i
nterface dynamicVector {
       // model: sequence (xi), i=0,... of objects
    // inv: MAX = 10000; 
    public void createDV(int m);
    public Object objectAt(int i);  
         // pre: true
         // post: if an object has been already inserted at     
         //       position i return it, else return null
   public void insertDV( Object x); 
        // pre: true
        // post: for all i >= r  objectAt(i) == null 
        // => x == objectAt(r), && r==R+1,   insert at rear

   public void insertAt(int i, Object x);
        // pre: true
        // post: objectAt(i) == x
}

Das Feld soll mit Länge m initialisiert. Hat es bei Aufruf von insertAt(i,obj) die  Gesamtlänge 
s = c*m < i,  wird es  um die Länge k*m   mit minimalem k so erweitert , dass s + k*m >  i . 
b) (3) wie lauten Abstraktionsfunktion und Repräsentationsinvariante? 
c) (2) Welche Laufzeit und welchen Platzbedarf hat der Zugriff auf ein Feldelement im schlechtesten Fall , wenn n Elemente in das Feld eingefügt wurden.

Aufgabe 6.2 (  6  P)  

a) (4) Gesucht ist ein externer Iterator für Mengen ganzer Zahlen, die als class IntSetMixed  (siehe Vorlesung, Quelltext im Netz ) implementiert sind. Testen Sie den Iterator mit einer lesenden Aktion (z.B. "Iteriere über alle Elemente und gib den Wert aus"). 
b(1) ) Geben Sie Gründe an, die für die Verwendung von Iteratoren sprechen. Welche sprechen dagegen?  
c) (1) Warum ist die
remove() Operation des Iterator-Interface kritisch? Geben Sie ein Beispiel an, aus dem das deutlich wird. 

Aufgabe 6.3 (  10  P)  
a)  (6 P) Erweitern Sie die  Klasse LinkedList des java.util-Pakets zu einer sortierten Liste. Hinweis: verwenden Sie das Interface Comparable (aus java.lang). Java Dokumentation benutzen! Test nicht vergessen!
b) (4 P) machen Sie das Gleiche mit der Klasse für einfach verkettete Listen, die für Aufgabe 1.4 vorgegeben wurde und vergleichen Sie die Lösungen. 

Aufgabe 6.4 ( 6  P)  
a)(1) Gegeben die Klassen
  
class Fahrzeug {...
        public String getTyp();
        public int getGeschwindigkeit();
        public date getBaujahr();
}
   und
   
class Transportmittel{...
         public int Sitzplätze();
         public int maxGewicht();
}
Gesucht ist eine Klasse class TransportFahrzeug, die beide Klassen im Sinne von Mehrfachvererbung vereinigt. Gäbe es in Java mehrfach erbende Klassen würde man schreiben: class TransportFahrzeug extends Fahrzeug, Transport {..}. Geben Sie eine Möglichkeiten zur Definition von TransportFahrzeug in Java an, bei denen   Code von Fahrzeug bzw. Transportmittel wiederverwendet wird.

b) (1)  Gegeben die Variablenvereinbarungen  IF1 x;  IF2 y;  IF1 und IF2 sind Java Interfaces. Geben Sie die genauen Bedingungen dafür an, dass die Typzuweisung x = y;  aus Sicht des Java-Übersetzers korrekt ist. 

c) (4) Zeichnen Sie alle freien Bäume mit  den Knoten x, y und z;  alle Wurzelbäume mit Knoten x,y,z und Wurzel x,  alle geordneten Bäume mit Knoten x,y,z  mit der Wurzel x,  und alle binären Bäume mit  Knoten x,y,z mit Wurzel x.

d) (Bonusaufgabe, 4 Punkte) Schreiben Sie eine Haskell - Funktion, die alle Knoten eines binären Baums traversiert (beliebige Reihenfolge) und eine Operation auf dem Wert jedes Knotens ausführt. Rufen Sie die Funktion z.B. mit einer Funktion "verdoppeln" und einem Binärbaum auf, dessen Knotenwerte ganze Zahlen sind. 

 
32 Punkte + 4 Bonuspunkte