Datenstrukturen und Algorithmen

Arrays als Datenstrukturen

Array-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 Array-Join für alle Typen?

Die folgende Utility-Methode ist praktisch, um Arrays 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 Methode nicht mit Object[] für alle Arrays erweitern, oder muss man für jeden Array-Typ wie int[], float[] eine eigene Methode schreiben?

Eigenschaften eines Array-Objektes

Lege ein Array vom Typ StringBuilder[] an und initialisiere es mit zwei Exemplaren. Ist ein clone() eines StringBuffer-Arrays flach oder tief?

Klasse java.util.Arrays

Beantworte mit wenigen Zeilen die Frage, was ist das kleinste Element eines Arrays von Ganzzahlen ist.

Lösung kleinstes Element

Array 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 Methode 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 Methode 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 Methode oder die Objektmethode distance(...) der java.awt.Point-Klasse.

Lösung

Adressen im Array

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 Array 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. Seit Java 8 vereinfacht die API das bilden von zusammengesetzten Comparatoren.

Die Schnittstellen der Collection-API

Die Hierarchie der Collection-Klasse und Schnittstellen *

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

Nach StringBuilder suchen (15 Min)

Wähle eine beliebige Collection-Klasse und fülle sie mit ein paar Städten, die als String-Objekte gegeben sind. Frage den Anwender über eine Konsoleneingabe nach einer Stadt. Teste mit contains(...), ob ein String in der Sammlung ist.

Ändere den Datentyp String auf StringBuilder. Ä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<String> 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

Listen

Arrays dekoriert

Was ergibt die folgende Anweisung?

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

Implementierung der Klasse java.util.ArrayList *

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 String split(...) einen String (wie etwa 12 34 23 + *) parst und das Ergebnis auswertet.

Lösung

Mengen

Die Klassen für Mengen *

  1. Erzeuge jeweils ein Objekt vom Typ java.util.HashSet und java.util.TreeSet:
    TreeSet<String> baumSatz = ...
    HashSet<Object> hashSatz = ...
  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 Methode 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("so")-Methode und was ist ihre Rückgabe?
  5. Füge ein Datums-Objekt java.util.Date mit add(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<Date>-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 );
   if (    cal.get( Calendar.DAY_OF_WEEK ) == Calendar.SATURDAY
        || cal.get( Calendar.DAY_OF_WEEK ) == Calendar.SUNDAY ) {
     // System.out.println( cal.getTime() );
  }
}

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

Lösung

Assoziativspeicher

Farben einlesen

Kopiere die Datei https://raw.githubusercontent.com/codebrainz/color-names/master/output/colors.csv lokal auf die Festplatte. Lies die Datei ein mit

List<String> lines = Files.readAllLines( Paths.get( "datei.txt" ) );

Zerlege die Zeile, extrahiere den Farbnamen (2. Spalte) und RGB-Wert und übertrage sie auf ein Color-Objekt der Art:

class Color { String name; int rgb; }

Sammle alle Color-Objekte in einem HashMap, wobei der Schlüssel der Name der Farbe ist und der Wert das zugehörige Color-Objekt. Frage über die Kommandozeile nach einem Farbnamen und liefere den assozierten RGB-Wert.

Ändere HashMap in eine TreeMap; die Sortierung soll nach den Namen (unabhängig der Groß-Kleinschreibung) erfolgen.

Array zu Map *

Schreibe eine Methode Map convertToMap(String[][]), die ein zweidimensionales Array in eine java.util.Map konvertiert. Ein Beispiel:

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

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

Lösung

Klasse java.util.HashMap und split() *

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. Laufe den String ab, in dem s.split("\\s+") die Wörter generiert.

Lösung

TreeMap: Feiertage verwalten

Wir bauen uns einen Datenstruktur mit Feiertagen und dessen Namen auf. Eine TreeMap soll Schlüssel vom Typ LocalDate.of(year, month, day) enthalten mit dem Namen des Feiertags als assoziieren Wert.

TreeMap<LocalDate, String> holidays = new TreeMap<>();
holidays.put( LocalDate.of(...), "..." );

Erfrage mit einem JOptionPane.showInputDialog(..) einen Tag und teste, ob er ein Feiertag ist.

Gib alle Feiertage im Herbst aus.

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.

Interna der Klasse java.util.Hashtable *

Erzeuge eine java.util.Hashtable und fülle sie mit willkürlichen Werten. Blicke kurz auf die Implementierung der Hashtable (nicht HashMap!) 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.HashMap **

Bewerte das folgende Beispiel:

Map<Point,String> 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 Klassen java.util.HashMap/Hashtable benutzen 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 wenig zu tun, da Collections die Typen um Collection in den Mittelpunkt setzen. 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<String,String> emails = ...

  /**
   * Speichert Name und E-Mail-Adresse wie [Chr. Ullenboom, Ulli@supernase.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 Methode, 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.

Properties in XML speichern

Erfrage über das System-Objekt die Properties-Eigenschaften und gebe sie als XML-Objekt auf dem Bildschirm aus.

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

Leider kann man den Inhalt einer java.util.HashMap nicht ohne weiteres als ASCII speichern, da sie Binärinformationen enthalten könnte. Mit Byte-Arrays 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.)

Anzahl Elemente suchen

Gegeben ist eine Liste mit Strings. Wie beantwortet man die Frage, wie oft ein String in diesem Array vorkommt?

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<String> adresses;

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

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

Erzeuge mit einem kurzen Ausdruck ein String-Array 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 Methode 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:

Automatisches Sortieren von Elementen

Bilde einen PriorityQueue und füge die Elemente 1, 9, 3, 10 ein. Hole drei Elemente entfernend aus der Queue. Füge 1, 12 als neue Elemente ein. Lese schlussendlich in einer Schleife alle Elemente löschend aus. Welche Reihenfolge geben der Iterator und toString()?

Lösung

Hashtable, ConcurrentHashMap, sichere Map

Lege eine Hashtable, eine ConcurrentHashMap und eine Map mit einer Collections.synchronizedMap() an. Führe mit jeweils 1, 2, 4, 8, 16, 32 Threads die nachfolgend genannten Operationen 1 Millionen mal aus:

  1. Im Kern wahlfreier Zugriff auf einige Elemente, wobei Treffer und nicht-Treffer dabei sind.
  2. put(...) und remove(...) sollten auch vereinzelt vorkommen.

ArrayBlockingQueue und Threads

Erzeuge eine ArrayBlockingQueue<String> der Größe 2 und zwei Runnable's, die einen Verweis auf die Queue bekommen. Der erste Runnable soll Strings produzieren, der andere konsumieren, doch sich dabei 100 ms Zeit lassen. Achte beim Herausnehmen und Einlegen auf die richtigen Methode.

Neue Iteratoren braucht das Land

1. In Datenstrukturen wie Listen können Elemente mehrfach vorkommen. Schreibe einen UniqueFilterIterator, der Elemente einer Collection nur einmal liefert.

Iterator uniqueIterator = new UniqueFilterIterator( list.iterator( ) );

2. Ein Iterator läuft in der Regel jedes Element einer Datenstruktur ab. Schreibe einen ArrayListIterator, bei dem man Liste, Start-/Endindex angeben kann. Kann man auch subList(...).iterator() einsetzen?