Algorithmen und Programmierung II

Aufgabe 1 (3 P.)

Entwickle eine Klasse mit einer rekursive Methode

public static void printPermutations(char[] aWord, int length)

die alle Permutationen der ersten length Zeichen in aWord, jeweils gefolgt von den übrigen (unveränderten) Zeichen am Bildschirm ausgibt. Die Zeichen in aWord dürfen dabei modifiziert werden. Schreibe auch eine main-Methode zum Testen von printPermutations.

Hinweis: Um i Elemente zu permutieren, kann man nacheinander jedes dieser Elemente an eine feste Position bringen (z.B. die erste oder letzte) und für jede solche Konstellation die übrigen i-1 Elemente permutieren.

Aufgabe 2 (4 P.)

In der Vorlesung wurde eine Beispiel eines Stacks vorgestellt, dessen Element, in einer (einfach verketteten) Liste verwaltet wurden. Die Elemente dabei waren vom Typ Object.

Implementiere nun eine Liste, deren Elemente ganze Zahlen (ints) sind. Außerdem soll die Liste eine Methode

public String toString()

haben, wobei der zurückgegebene String die (Stringrepräsentation der) in Liste enthaltenen Zahlen enthält, jeweils getrennt durch ein Leerzeichen und in der Reihenfolge wie sie in der Liste auftauchen.

Nebenbemerkung:

Man kann dann alle Listenelemente einer Liste list einfach ausgeben, indem man System.out.println(list.toString()) aufruft. Die toString-Methode eines Objektes wird auch implizit vom Compiler aufgerufen, wenn man das Objekt mit dem +-Operator vor oder hinter einen String hängt, z.B. bei System.out.println("Liste: "+list).

Aufgabe 3 (7 P.)

Entwickle eine Prozedur

public static List getSortedList(int[] anArrayOfInt),

die die Zahlen aus einem gegebenen Feld derart in eine neu erzeugte verkettete Liste überträgt, daß diese dort in aufsteigender Reihenfolge stehen.

Schreibe auch eine main-Methode, mit der getSortedList ausgiebig getestet werden kann. Die Ausgabe der sortierten Liste soll dabei toString aus der vorhergehenden Aufgabe verwenden.

Aufgabe 4 (4 P.)

Schreibe eine Methode

public static 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.

Zum Testen wende man splitToWords auf interaktiv eingegeben Zeilen an.

Ihr werdet bei dieser Aufgabe einige Methoden von String benötigen; seht diese in java.lang.String in der API-Doc nach.

Einige Hinweise zur Ein-/Ausgabe in Java:

Für die Standarteingabe -- also normalerweise der Tastatureingabestrom -- gibt es in Java den InputStream System.in. Nun sind InputStreams in Java für die binäre Eingabe gedacht. Will man eine buchstabenbasierte Eingabe, so sollte man in Java einen Reader verwenden. Um nun aus einen InputStream einen Reader zu zu machen, verwendet man den InputStreamReader: mit dem Aufruf

new InputStreamReader(System.in)

erhalten wir dann einen (InputStream)Reader für die Standarteingabe. (Analog gibt es für die Ausgabe OutputStream, Writer und OutputStreamWriter.) Mit dem InputStreamReader kann man bereits buchstabenweise lesen. Wenn wir aber einen Reader benutzen wollen, der uns eine ganze Zeile auf einmal liefern kann, so verwendet man einen BufferedReader. Diesen kann man aus einen bereits existierenden Reader konstruieren, also:

BufferedReader aBufferedReader =
  new BufferedReader(new InputStreamReader(System.in));

Dann kann man je eine Zeilen mit dem Aufruf aBufferedReader.readLine() holen. Der Aufruf gibt die Zeile - ohne das abschließende Zeilenumbruchzeichen -- als einen String zurück. Er kann eine eine IOException werfen. Siehe auch readLine() in der API doc.

Wenn ihr diese Klassen benutzt, importiert die java.io-Bibliothek. Schreibt dazu ganz oben in eurer Java-Quelldatei (d.h. über der ersten Klassendefinition) die Zeile "import java.io.*;". Das sorgt dafür, daß dem Compiler alle Klassen der Bibliothek bekannt sind. Alternativ kann man die Klassen einzelnd importieren, z.B. import java.io.BufferedReader;, oder diese mit ihrem voll qualifizierten Namen verwenden, etwa mit java.io.BufferedReader statt BufferedReader.