Datenstrukturen und Algorithmen

Felder als Datenstrukturen

Feld-Typen (10 Min)

Überlege, ob alle Anweisungen compilieren bzw. zur Laufzeit funktionieren:

String[] a1 = new String[ 100 ];
Object[] a2 = (String[]) a1;
Object[] a3 = a1;
Object[] a4 = new String[]{ "1", "2", "3" };
String[] a5 = (String[]) a4;
String[] a6 = { "1", "2", "3" };
Object[] a7 = a6;
Object[] a8 = { "1", "2", "3" };
String[] a9 = (String[]) a8;

int[] b1 = new int[100];
Object[] b2 = (int[]) b1;
Object[] b3 = new int[100];
int[] b4 = (int[]) b3;

Ein Feld-Join für alle Typen?

Die folgende Utility-Funktion ist praktisch, um Felder zusammenzulegen.

public static String[] join( String[] first, String[] second )
{
  if ( null == first && null == second )
    return null;
  if ( null == first )
    return second;
  if ( null == second )
   return first;

  String[] newArray = new String[ first.length + second.length ];

  System.arraycopy( first,  0, newArray, 0,            first.length );
  System.arraycopy( second, 0, newArray, first.length, second.length );

  return newArray;
}

Kann man die Funktion nicht mit Object[] für alle Felder erweitern, oder muss man für jeden Feldtyp wie int[], float[] eine eigene Funktion schreiben?

Eigenschaften eines Feld-Objektes

Lege ein Feld vom Typ StringBuffer[] an und initialisiere es mit zwei StringBuffer-Objekten. Ist ein clone() eines StringBuffer-Feldes flach oder tief?

Klasse java.util.Arrays

Beantworte mit wenigen Zeilen die Frage, was ist das kleinste Element eines Feldes von Ganzzahlen ist. Die Laufzeit ist uninteressant.

Lösung kleinstes Element

Felder bestimmter Typen erzeugen **

Was schreibe die API-Dokumentation zur Methode Array.newInstance()?

Überlege, ob folgende Anweisungen übersetzt und ausgeführt werden können?

int[]    a1 = (int[])    Array.newInstance( int.class, 1 );
Object[] a2 = (Object[]) Array.newInstance( int.class, 1 );
String[] a3 = (String[]) Array.newInstance( String.class, 1 );
Object[] a4 = (Object[]) Array.newInstance( String.class, 1 );
String[] a5 = (String[]) Array.newInstance( Object.class, 1 );

Hilft das Wissen, um die Funktion join() zu vereinfachen, wenn man etwa Point[], String[], int[] zusammenhängen möchte?

Comparator/Comparable

Das Interface java.util.Comparator *

Was passiert, wenn man folgendes ausführen möchte:

String strings[] = { "A", "B", "C" };
Arrays.sort( strings );

Point[] points = {
 new Point( 9, 3 ),
 new Point( 3, 4 ),
 new Point( 4, 3 ),
 new Point( 1, 2 ),
};

Arrays.sort( points );

Die Funktion sort() aus java.util.Arrays kann nur nach Kriterien sortieren, die sie kennt. Sollen unbekannte Objekte miteinander verglichen werden, so müssen wir der Methode sort() ein spezielles Objekt mitgeben, welches das Sortierkriterium beachtet.

Schreibe einen Vergleichs-Comparator für java.awt.Point-Objekte. Als Vergleichsmöglichkeit soll die Distanz zum Nullpunkt verwendet werden. Ist der Abstand eines Punktes p1 vom Nullpunkt kleiner als der Abstand eines Punktes p2, so soll gelten p1 < p2. Nutze eine eigene Funktion oder die Objektmethode distance() der java.awt.Point-Klasse.

Lösung

Adressen im Feld

Schreibe eine Bean-Klasse Address für Adressen. Eine Adresse soll die Strasse, Ort und PLZ speichern. Neben einem Standard-Konstruktor soll Address auch einen parametrisierten Konstruktor besitzen, der Strasse, Ort und PLZ direkt annimmt.

Setze ein paar Adressen in ein Feld und sortiere es nach dem Ort.

Address[] addresses = {
 new Address( "Immengarten 6",     "Hannover",    30177 ),
 new Address( "Petzelstrasse 84",  "Langenhagen", 30855 ),
 new Address( "Friedrichswall 11", "Hannover",    30159 )
};

Füge ein zweites Sortierkriterium hinzu: Ist der Ort gleich, soll als zweites nach der PLZ sortiert werden.

CompoundComparator

Werden Comparatoren immer komplexer, so lohnt es sich, diese aus einfachen Teilen zusammenzusetzen. Verstehe den CompoundComparator, und setze die beiden Kriterien für die Adresse aus zwei Comparatoren zusammen.

Die Schnittstellen der Collection-API

Die Hierarchie der Collection-Klasse und Schnittstellen *

Baue eine einfache Vererbungshierarchie der Collection-Klassen auf. Beginne mit der Klasse ArrayList. Füge dann in das Diagramm List, AbstractList, Collection, AbstractCollection, Set, AbstractSet, TreeSet, Queue und HashMap ein.

Nach StringBuffer suchen (15 Min)

Fülle eine beliebige Collection mit String-Objekten. Frage mit contains(), ob ein String in der Sammlung ist.

Ändere den Datentyp String auf StringBuffer. Ändert sich dadurch etwas?

Leere Wörter löschen

Gegeben ist ein String mit einem Satz

String s = "Wald ist überflüssig. Auf anderen Planeten gibt es auch keine Bäume.";

Laufe über den String und geben alle Wörter aus. (Dass diese die Satzzeichen enthalten, kann im ersten Schritt ignoriert werden.)

String tokens = s.split( " " );
for ( int i = 0; i < tokens.length; i++ )
{
  String token = tokens[ i ];
}

Aus einem Satz sollen alle "leeren Worte", das sind Artikel, Präpositionen -- also Wörter wie "der", "das", "er", "sie", "ein", "eine", "keine", "auf" -- gelöscht werden. Die Groß-Kleinschreibung soll keine Rolle spielen.

public static Collection removeEmptyWords( String s )
{
}

Das Ergebnis soll ein Collection mit kleingeschriebenen nicht-leeren Wörtern sein, also etwa {"wald", "überflüssig", "anderen", "planeten", "gibt", "keine", "bäume" }.

Lösung

Welche meiner Termine liegen an Feiertagen?

Gegeben ist eine Liste von Feiertagen

Collection holidays = new ArrayList();
holidays.add( new GregorianCalendar(2007, Calendar.DECEMBER, 24) );
holidays.add( new GregorianCalendar(2008, Calendar.JANUARY,   1) );

und eine Liste von eigenen Terminen

Collection myDates = new ArrayList();
myDates.add( new GregorianCalendar(2007, Calendar.DECEMBER, 22) );
myDates.add( new GregorianCalendar(2007, Calendar.DECEMBER, 24) );

Wie kann man leicht herausfinden, welche Tage aus den Terminen ein Feiertag ist? Am Ende soll eine Liste stehen, die man so ausgeben kann:

for ( Iterator iterator = myDatesWithHolidays.iterator(); iterator.hasNext(); )
{
  Calendar cal = (Calendar) iterator.next();
  System.out.println( SimpleDateFormat.getDateInstance().format( cal.getTime() ) );
}

Ausgabe dann: 24.12.2007

Listen

Felder dekoriert

Was ergibt die folgende Anweisung?

Arrays.asList( new String[]{"Eins", "Zwei"} ).add( "Drei" );

Implementierung der Klasse java.util.ArrayList *

Ein eigener Keller *

Wir wollen nun einen Stapelspeicher implementieren. Dieser hat wie ein Stapel Teller die Eigenschaft, dass immer oben Elemente eingefügt werden und dann nur von oben weggenommen werden können. Schreibe eine Klasse Keller, die drei Methoden implementiert:

  1. push(Object) (Ein Element in den Keller einfügen.)
  2. Object pop() (Das oberste Element vom Keller nehmen.)
  3. boolean isEmpty() (Ist der Keller leer?)

Lösung

Tolles Design bei java.util.Stack *

Welche Methoden besitzt ein java.util.Stack? Gibt es Methoden, die für einen java.util.Stack unangebracht sind?
Wenn man sich die Vererbungshierarchie der Klasse java.util.Stack ansieht, so fällt auf, dass sie von java.util.Vector abgeleitet wird.
Bewerte die Implementierung und begründe. Was bedeutet dies?

Ein UPN-Taschenrechner **

Viele einfache Programmiersprachen erlauben arithmetische Ausdrücke in umgekehrt Polnischer Notation (UPN). Ein bekanntes Beispiel dafür ist Postscript.
Programmiere einen Taschenrechner, der mittels des java.util.StringTokenizer einen String (wie etwa 12 34 23 + *) parst und das Ergebnis auswertet.

Mengen

Die Klassen für Mengen *

  1. Erzeuge jeweils ein Objekt vom Typ java.util.HashSet und java.util.TreeSet.
  2. Füge die Zeichenketten "möchtest", "du", "wertvolle", "dinge", "sehen", "so", "blicke", "dorthin", ",", "wohin", "die", "große", "menge", "nicht", "sieht". ein. Bei dieser Anzahl von Zeichenketten ist es vielleicht schlau, eine Funktion zu nutzen, die eine Folge von Zeichenketten in ein Set einfügt. Überlege, wie man intelligent die Methoden asList() aus java.util.Arrays und addAll(Collection) aus java.util.Set nutzen kann.
  3. Gib mit toString() die Elemente aus. Was fällt auf?
  4. Wenn man einen String wie "so" einfügt, der schon in der Menge enthalten ist, was macht die add()-Methode und was ist ihre Rückgabe?
  5. Füge ein Datums-Objekt java.util.Date mit new Date() ein. Was ist die Konsequenz?

Lösung

Sortierte Bäume mit Teilbereichen ** (30 Minuten)

In einem java.util.TreeSet lassen sich Werte einer Menge speichern, löschen und erfragen, jedoch schneller als in einer herkömmlichen Liste. Angenehme Begleiterscheinung ist, dass die Elemente gleich sortiert sind (java.util.TreeSet implementiert java.util.SortedMap).

Fülle ein java.util.TreeSet-Objekt mit allen Samstagen und Sonntagen eines Jahres. Nutzte dazu folgende Quellcodevorlage:
Calendar cal = Calendar.getInstance();

for ( int day = 1, maxDay = cal.getActualMaximum( Calendar.DAY_OF_YEAR ); 
      day <= maxDay; 
      day++ ) 
{
   cal.set( Calendar.DAY_OF_YEAR, day );

   // System.out.println( cal.getTime() );
}

Welche Samstage und Sonntage liegen in einem gewissen Intervall, etwa den Sommerferien? Wie viele sind es?

Lösung

Assoziativspeicher

Feld zu Map *

Schreibe eine Funktion Map convertToMap(Object[][]), die ein zweidimensionales Feld in eine java.util.Map konvertiert. Ein Beispiel:

Map colorMap = convertToMap( new String[][]{
  {"rot",  "#FF0000"},
  {"grün", "#00FF00"},
  {"blau", "#0000FF"}
} );
System.out.println( colorMap );   // {blau=#0000FF, grün=...

Der erste Eintrag im Feld soll der Schlüssel, der zweite der Wert sein.

Lösung

Klasse java.util.HashMap und java.util.StringTokenizer *

Man möchte gerne in einem Satz einige Wörter ersetzen, zum Beispiel alle Wörter "doof" durch "unschlau" und "pfusch" durch "ungünstig". Überlege, wie man eine Klasse WordFilter mit einer Methode addWordPair(String find, String replace) ausstatten kann, sodass die Methode String replace(String s) alle Wörter im Parameter untersucht und gegebenenfalls die Ersetzungen vornimmt.

Lösung

Funktionszeiger *

Hin und wieder vermisst man die Möglichkeit, in Java Funktionszeiger zu implementieren. Dabei ist Polymorphie eine schöne Sache. Verstehe das folgende Beispiel.

Klasse java.util.Hashtable *

Erzeuge eine java.util.Hashtable und fülle sie mit willkürlichen Werten.  Blicke kurz auf die Implementierung der Hashtable und skizziere kurz die Idee, die hinter dem Algorithmus steckt.

Versuche anschließend die Methoden contains() und containsKey() zu verstehen. Worin genau besteht der Unterschied? Was lässt sich über die Laufzeit der beiden Methoden sagen?

Schlüssel in einer java.util.Hashtable **

Bewerte das folgende Beispiel:

HashMap map = new HashMap();
Point p = new Point( 2, 4 );
map.put( p, p.toString() );
p.setLocation( 4, 2 );
map.get( p );              // ?

Was muss für Elemente eines Assoziativspeichers gelten?

Hash-Funktionen **

Die Klasse java.util.Hashtable benutzt die vom Object geerbte Methode hashCode(), um den Hashwert zu berechnen. Sieh in ein paar Klassen hinein (etwa java.awt.Point, java.lang.String) und

a) dokumentiere wie die jeweilige Hashfunktion arbeitet.
b) erzeuge Objekte und gebe den Hashwert aus.
c) versuche zwei verschiedene Objekte zu finden, deren Hashwert gleich ist.

Methodenvergleich der java.util.Map **

Eine java.util.HashMap hat als java.util.Map mit java.util.Collections nichts zu tun. Dennoch gibt es einige Schnittpunkte mit anderen Datenstrukturen. Betrachte dazu die Methoden.

Beantworte weiterhin:

E-Mail-Adressen verwalten und erfragen *

Entwickle eine Klasse EMails, mit der man E-Mails von Benutzern verwalten kann. Fülle die folgende Klasse sinnvoll aus:

class EMails
{
  Map emails = ...

  /**
   * Speichert Name und E-Mail-Adresse wie [Chr. Ullenboom, Ulli@java-tutor.com].
   */
  void add( String name, String email ) {
  }

  /**
   * Sucht nach der E-Mail-Adresse mit dem exakten Namen.
   */
  String lookup( String name ) {
  }

  /**
   * Gibt alle Schlüssel-/Wertepaare auf dem Bildschirm (System.out) aus.
   */
  void list() {
  }
}

Wenn die E-Mail-Adresse mit dem Präfix "mailto:" beginnt, dann wollen wir dies abschneiden.

Suche unter http://koders.com eine Java-Funktion mit Levenstein-Abstand, damit sich Ähnlichkeiten bestimmen lassen. Realisiere damit eine Funktion, die auch E-Mail-Adressen liefert, wenn der Name nicht 100%ig passt.

Lösung

Design der Klasse java.util.Properties *

Korrigiere für die Klasse java.util.Properties das untere Beispiel:

myProps = new Properties();
String firstKey = "firstKey";
Integer firstValue = new Integer(3);
myProps.put(firstKey, firstValue);

Wovon wird hier ausgegangen? Was sagt die Dokumentation zur put()-Methode? Welche Verwandtschaft besitzt java.util.Properties zu java.util.Hashtable? Vergleiche getProperty() aus java.util.Properties und get(). Bewerte das schlampige Design.

Binärdaten in ein Property-Objekt einfügen **

Leider kann man den Inhalt einer java.util.Hashtable nicht ohne weiteres als ASCII speichern, da sie Binärinformationen enthalten könnte. Mit Bytefeldern kann man jedoch einen Trick anwenden. Die Byteinformationen können in einen String konvertiert werden. Da dieser dann ungültige Einträge besitzen könnte, muss man jedoch den String in einen gültigen lesbaren String umwandeln. Dazu kann man die Klassen java.net.URLEncoder und java.net.URLDecoder nutzen.

Erstelle eine Unterklasse von java.util.Properties und implementiere putBin(String, byte[]) und byte[] getBin(String) so, dass die Binärinformationen als kodierte Strings abgelegt werden.

Lösung

Algorithmen zu den Datenstrukturen

Anzahl Auftreten

Fülle eine Liste mit 100 ganzzahligen Zufallszahlen (Tipp: Random#nextInt(int n)). Wie oft kommt das kleinste und größte Element in der Liste vor? (Die Laufzeit ist nebensächlich.)

String#split(), Arrays.asList(), Collections.addAll(), Collections.frequency()

Kombiniere geschickt die drei Methoden String#split(), Arrays.asList(), Collections.frequency(), um herauszufinden, wie oft das Wort "dumm" im String vorkommt.

String s = "dumm wird man nicht, dumm bleibt man";

Collections.singleton() und Collections.nCopies() **

Die Klasse java.util.ArrayList definiert zwar eine remove()-Methode durch die Schnittstelle java.util.Collection, jedoch löscht die Methode nur das erste Element, welches angesprochen wird. Schreibe eine statische Methode removeAllElements(l,e), welche alle Elemente e in der Liste l löscht. Versuche dazu gewinnbrindend die Methode Collections.singleton() einzusetzen.

Wo lässt sich durch singleton() (oder auch nCopies()) ein Konstruktor verbessern:

import java.util.ArrayList;
import java.util.List;

public class Person
{
  private List adresses;

  public Person( String address )
  {
    adresses = new ArrayList();
    adresses.add( address );
  }

  public Person( List adresses )
  {
    this.adresses = adresses;
  }
}

Erzeuge mit einem kurzen Ausdruck ein String-Feld mit 10 leeren (also "") Strings.

7 aus 49 *

In einem Lottospiel werden 7 Zahlen aus 49 gezogen. Bilde eine Liste mit 49 Zahlen und ziehe 7. Überlege, wie man die Funktion shuffle() aus java.util.Collections dafür nutzen kann.

Lösung

Ergänzendes

Vergleich der Datenstrukturen *

Wir wollen für die Klassen und Schnittstellen java.util.Set, java.util.List, java.util.Map, java.util.HashSet, java.util.TreeSet, java.util.Hashtable, java.util.HashMap und java.util.TreeMap einen Entscheidungsbaum aufbauen. Folgende Überlegungen sollten angestellt werden: