Algorithmen und Programmierung II

 


SS 2002 Dr. Hannes Federrath
Übung 6 Natalie Ardet
Abgabe bis zum Do. 13.06.02

Die Lösung der Aufgaben und die Abgabe der Lösungen erfolgt in Zweiergruppen!

Hinweis: Benutze die Ressourcen der ALP2 Webseite.

Aufgabe 1 (12 P.)

In der Vorlesung wurde die Klasse Node vorgestellt, um eine einfach verkettete Liste zu realisieren. Die Klasse Knoten ist eine Variante der Klasse Node. Sie bietet eine Anzahl von Zugriffsmethoden und anders als in der Vorlesung jedes Element kennt seinen Nachfolger.

Hinweis: Die Vorbedingungen (engl. preconditions) die erfüllt werden müssen bevor man eine Methode aufrufen darf stehen als Kommentare jeweils vor der Methode. Die Vorbedingungen müssen vom Aufrufer überprüft werden.

public class Knoten {    
    
    public Knoten(Object inhalt, Knoten nachfolger) {
        this.inhalt = inhalt;
        this.nachfolger = nachfolger;
    }

    public Knoten(Object inhalt) {
        this.inhalt = inhalt;
        this.nachfolger = null;
    }

    public Object gibInhalt(){
            return inhalt;
    }

    public void setzeNachfolger(Knoten nachfolger) {
        this.nachfolger = nachfolger;
    }

    public boolean hatNachfolger() {
        return (nachfolger!=null);
    }

    public Knoten gibNachfolger() {
        return nachfolger;
    }
    public boolean istGueltig() {
        return (inhalt != null);
    }
   /**
     * @preconditions istGueltig() 
     */
    public String toString() {
        return inhalt.toString();
    }

    private Knoten nachfolger;
    private Object inhalt;
}

Ziel der Aufgabe ist es eine Klasse List zu schreiben die eine einfach verkettete Liste von Knoten enthält. Die Klasse List muss dabei folgende Anforderungen erfüllen:

  1. Eine Liste enthält eine einfach verkettete Liste von Knoten.
  2. Eine Methode entfernen() löscht die erste Erscheinung eines gegebenen Elements aus der Liste. Folgende Vorbedingungen gelten für diese Methode: das Element hat nicht den Wert "null" und die Liste ist nicht leer.
  3. Eine Methode istLeer() gibt den Boole'schen Wert "true" zurück wenn die Liste keine Elemente enthält, ansonsten gibt sie "false" zurück.
  4. Eine Methode anhaengen() fügt ein gegebenes Element am Ende der Liste ein. Der Wert des Elements ist nicht "null". 
  5. Eine Methode toString() gibt eine Zeichenkette zurück (d.h. ein Exemplar der Klasse String). Die zurückgegebene Zeichenkette enthält den Wert der Elemente der Liste, jeweils getrennt durch ein Leerzeichen und in der Reihenfolge in der sie in der Liste sind.
  6. Die Elementen sind Exemplare der Java-Klasse "Object" 
  7. Die Klasse List enthält mindestens die Methoden die in der Schnittstellendefinition  "ListeSchnittstelle" definiert sind.

Die Anforderungen 2 bis 6 werden in Java wie folgt aufgeschrieben:

public interface ListeSchnittstelle {
    /**
     * @preconditions inhalt!=null, !istLeer()
     */
    void entfernen(Object inhalt);
    boolean istLeer(); 
    /**
     * @preconditions !istLeer() 
     */
    String toString();
    /**
     * @preconditions inhalt!=null 
     */
    void anhaengen(Object inhalt);
}

Damit der Java-Übersetzer die Anforderung 7 überprüfen kann, wird die Klasse List wie folgt deklariert:

public class List implements ListeSchnittstelle {
    // Hier kommen Eure Methoden und Attribute hin.

Schreibe die beschriebene Klasse List in Java.

Aufgabe 2 (8 + 2 + 2 = 12 P.)

Hinweis: Die Ergebnisse der 1.Aufgabe dürfen für diese Aufgabe wiederverwendet werden.

1. Entwickle eine Klasse Sortierer die eine Methode bietet die Zeichenketten aus einem gegebenen Feld derart in eine neu erzeugte verkettete Liste überträgt, dass diese dort in aufsteigender Reihenfolge stehen. Die Signatur der Methode ist:

public void einfuegen(String[] woerter) 

2. Erweitere die Klasse um eine Methode toString() die eine Zeichenkettenrepräsentation der Wörter in der sortierten Liste zurückgibt. Jedes Wort  wird von einem Zeilenumbruchzeichen \n gefolgt. Die Signatur ist:

public String toString()

3. Schreibe ein Programm, das Wörter aus einer Textdatei ließt, sie mit Hilfe der Klasse Sortierer alphabetisch sortiert und in eine neue Datei schreibt. Das Lesen erfolgt mit der Methode leseWoerter() der Klasse DateiLeser. Das Schreiben erfolgt mit der Methode schreibeWoerter() der Klasse DateiSchreiber.

Aufgabe 3 ( 12 P.)

Schreibe eine Methode

public String[] splitToWords(String aString),

die einen gegebenen String von durch Leerzeichen getrennten "Wörtern" interpretiert und ein Feld zurückgibt, das diese Wörter (in gleicher Reihenfolge) enthält. Die Anzahl der Feldelemente soll gleich der Anzahl der vorkommenden Wörter sein.

Ihr werdet bei dieser Aufgabe einige Methoden der Klasse String benötigen; seht diese in java.lang.String in der API-Doc nach. Die Klasse StringTokenizer aus der Java API darf nicht verwendet werden.


04.06.2002