Transcript
Institut für Informatik Prof. Dr. Oliver Vornberger Ann-Katrin Becker, M.Sc. Nils Haldenwang, M.Sc.
Universität Osnabrück, 15.12.2015 http://www-lehre.inf.uos.de/~ainf Testat bis 06.01.2016, 14:00 Uhr
Übungen zu Algorithmen Wintersemester 2015/2016 Blatt 10: Abstrakte Datentypen Aufgabe 10.1: Fragen (30 Punkte) Beantworten Sie Ihrer Tutorin bzw. Ihrem Tutor Fragen zur Algorithmenveranstaltung. Aufgabe 10.2: KellerListe (25 Punkte) Implementieren Sie in einer Klasse KellerListe das aus der Vorlesung und im Anhang befindliche Interface Liste. Verwenden Sie dabei einen oder mehrere Keller als interne Hilfsspeicher. Sie können Ihre Implementierung mit der im Anhang befindlichen Klasse KellerListeTest testen. Musterlösung: import AlgoTools.IO;
/** * Implementation des Interface Liste mittels zwei Kellern als * interne Datenstruktur. * * Die Idee besteht darin, im ersten Keller von oben nach unten alle Listenelement * wobei das oberste immer das aktuelle Element ist. Bei allen Listenoperation wer * geeigneten Elemente derart auf den Zweiten Keller geschoben, so dass Elemente v * Element immer auf dem zweiten Keller liegen. */ public class KellerListe implements Liste { private Keller tmp1; private Keller tmp2; public KellerListe() { tmp1 = new VerweisKeller(); tmp2 = new VerweisKeller(); } /** * Siehe {@link Liste} */ public boolean empty(){
return tmp1.empty() && tmp2.empty(); } /** * Siehe {@link Liste} */ public boolean endpos(){ return tmp1.empty(); } /** * Siehe {@link Liste} */ public void reset(){ while(!tmp2.empty()){ tmp1.push(tmp2.top()); tmp2.pop(); } } /** * Siehe {@link Liste} */ public void advance(){ if(endpos()) throw new RuntimeException("Liste ist am Ende, kann nicht löschen."); tmp2.push(tmp1.top()); tmp1.pop(); } /** * Siehe {@link Liste} */ public Object elem(){ return tmp1.top(); } /** * Siehe {@link Liste} */ public void insert(Object x){ tmp1.push(x); } /** * Siehe {@link Liste} 2
*/ public void delete(){ if(endpos()) throw new RuntimeException("Liste ist am Ende, kann nicht löschen."); tmp1.pop(); }
}
Aufgabe 10.3: VerweisSchlange (25 Punkte) Implementieren Sie den ADT Schlange gemäß dem im Anhang befindlichen Interface Schlange.java aus dem Skript mit Hilfe von Verweisen in einer Klasse VerweisSchlange. Eine VerweisSchlange hat folgende Gestalt: a
a
head:
head:
head:
tail:
tail:
tail:
neu erzeugt
mit einem Element ’a’
Testen Sie Ihre VerweisSchlange VerweisSchlangeTest.
b
c
mit den drei Elementen ’a’, ’b’ und ’c’
mit
Hilfe
der
im
Anhang
befindlichen
Klasse
Musterlösung: /***************************
VerweisSchlange.java
***************************/
/** * Implementiert den Abstrakten Datentyp Schlange mit Hilfe von Verweisen * und die darauf definierten Operationen: empty, enq, deq, front */ public class VerweisSchlange implements Schlange { /** * Verweis auf den Schlangenanfang. */ private Eintrag head; /** * Verweis auf das Schlangenende. */ private Eintrag tail;
3
/** * Erzeugt eine leere VerweisSchlange. */ public VerweisSchlange() { head = tail = null; } /** * Testet, ob die VerweisSchlange leer ist. * * @return true, falls die Schlage leer ist, sonst false. */ public boolean empty() { return head == null; } /** * Fuegt eine Element in die Schlange ein. * * @param x Objekt, welches eingefuegt werden soll. */ public void enq(Object x) { if (empty()) tail = head = new Eintrag(); else { tail.next = new Eintrag(); tail = tail.next; } tail.inhalt = x; tail.next = null;
// Neuen anhaengen // Schlangenende 1 weitersetzen // x zuweisen // Schlangenende
} /** * Entfernt das vorderste Schlangenelement. * * @throws RuntimeException Wird geworfen, falls die Schlange leer ist. * */ public void deq() { if (empty()) // Falls Schlange leer, dann Abbruch throw new RuntimeException("deq: Schlange ist leer"); 4
head = head.next;
// Naechtster Eintrag wird aktuell
if (head == null) tail = null;
// wenn Kopf auf kein Objekt verweist // Schlangenende setzen
} /** * Liefert das vorderste Element der Schlange. * * @return Das vorderste Schlangenelement. * @throws RuntimeException Wird geworfen, falls die Schlange leer ist. * / * public Object front() { if (empty()) // Falls Schlange leer, dann Abbruch throw new RuntimeException("front: Schlange ist leer"); return head.inhalt; } } /***************************
VerweisSchlangeTest.java
*********************/
import AlgoTools.IO; /** * Programm zum Testen der Methoden des ADT Schlange. Liest Zeichenketten und * reiht sie in eine Schlange ein. Bei Eingabe einer leeren Zeichenkette wird * die jeweils vorderste aus der Schlange ausgegeben und entfernt. */ public class VerweisSchlangeTest { public static void main(String argv[]) { Schlange schlange = new VerweisSchlange();
// konstruiere leere Schlange
IO.println("Bitte Schlange Fuellen durch Eingabe eines Wortes, "); IO.println("Schlangen-Kopf Entfernen durch Eingabe von RETURN."); do { String eingabe = IO.readString("Input: 5
");
if (eingabe.length() > 0) schlange.enq(eingabe);
// falls Eingabe != RETURN // fuege in Schlange ein
// falls EINGABE == RETURN else if (!schlange.empty()){ // sofern Schlange nicht leer IO.println("entfernt: " + schlange.front()); schlange.deq(); // entferne Frontelement } } while (!schlange.empty()); IO.println("Schlange ist jetzt leer."); } }
Aufgabe 10.4: Superliste (20 Punkte) Implementieren Sie die von der im Anhang befindlichen klasse VerweisListe.java aus der Vorlesung abgeleitete Klasse SuperListe, indem Sie die folgenden Methoden ergänzen: 1. public void umdrehen(): invertiert die Reihenfolge der Elemente in der Liste. Nach dem Umdrehen soll das erste Element der SuperListe das aktuelle Element sein. 2. public void unique(): löscht alle Duplikate aus der Liste. Nutzen Sie die Methode equals der Klasse Object, um Elemente der Liste zu vergleichen. Nach dem Entfernen soll das erste Element der SuperListe das aktuelle Element sein. 3. public Object elem(int n): liefert das nte Element der Liste. Achten Sie auf geeignete Fehlerbehandlung. Sie dürfen hier vernachlässigen, dass durch die Operation evtl. der Zustand der Liste verändert wird, es muss also nachher nicht unbedingt das gleiche Element das aktuelle Element sein wie vorher. Testen Sie Ihre SuperListe, VerweisListeTest.java.
mit
der
im
Anhang
befindlichen
Klasse
Musterlösung: /******************************
SuperListe.java
******************************/
import AlgoTools.IO; /** * Erweitet die Klasse VerweisListe um drei nuetzliche Operationen. */
6
public class SuperListe extends VerweisListe { /** * Invertiert die Reihenfolge der Elemente in der Liste. */ public void umdrehen() { Schlange s=new VerweisSchlange(); reset(); while(!empty()) { s.enq(elem()); delete(); } while(!s.empty()) { // fuegt vor dem aktuellen Element ein und // macht das eingefuegte Element zum aktuellen insert(s.front()); s.deq(); } } /** * Entfernt alle Duplikate aus der Liste. */ public void unique(){ boolean doppel=false; reset(); Liste hilf=new VerweisListe(); Object temp; // fuer alle Elemente in unserer Liste while(!endpos()){ // merke aktuelles Element temp=elem(); // gehe bisher ueberpruefte Elemente durch while(!hilf.endpos() && !doppel){ doppel=temp.equals(hilf.elem()); hilf.advance(); } // jetzt ist entweder: // ein doppeltes Element gefunden worden // oder: 7
// alle Elemente verglichen hilf.reset(); // falls kein Duplikat gefunden: // zu hilf hinzufuegen if(!doppel) hilf.insert(temp); // falls Duplikat gefunden: // fuege es nicht hinzu. // in jedem Fall: aktuelles Element loeschen delete(); doppel=false; } // hilf zurueck in die Hauptliste while(!hilf.endpos()){ insert(hilf.elem()); hilf.delete(); } } /** * Liefert das Element an Stelle n. * @param n der Index des zu liefernden Elementes * @return das Element an Stelle n * @throws RuntimeException falls Liste weniger als n Elemente */ public Object elem(int n){ if(n <= 0) throw new RuntimeException("n muss > 0 sein."); reset(); for(int i=1; i
