|
|
1. Datenstrukturen und Algorithmen
Datenstrukturen speichern in der Anwendung zentrale Informationen. Organisiert werden sie über Listen, Mengen, Queues und Assoziativspeicher. In Java werden die Schnittstellen und Klassen rund um Datenstrukturen Collection-API genannt. Da so viele Typen zur Auswahl stehen, ist es Gegenstand von diesem Kapitel, Ordnung in das Chaos zu bringen und durch die Aufgaben den Einsatz der entsprechenden Sammlungen zu verdeutlichen.
Voraussetzungen
Datenstrukturen Listen, Mengen, Assoziativspeicher abgrenzen können
Datentypen
List,ArrayListundLinkedListkennenDatentypen
Set,HashSetundTreeSetkennenDatentypen
Map,HashMapundTreeMapkennenUnterschied zwischen Queue und Deque kennen
Ordnung mit
Comparatorschaffen könnenIteratoren einsetzen und implementieren können
Datenstrukturen threadssicher verwenden können
Optional: Interesse an der Open-Source-Bibliothek Guava für weitere Datenstrukturen
Verwendete Datentypen in diesem Kapitel:
Noch mehr Aufgaben findest du im Buch: ›Captain CiaoCiao erobert Java: Das Trainingsbuch für besseres Java. 300 Java-Workshops, Aufgaben und Übungen mit kommentierten Lösungen‹
1.1. Die Typen der Collection-API
Die Liste der verwendeten Typen ist ja diesmal lang. Allerdings folgt das Design einem grundlegenden Prinzip, sodass es dann doch nicht so kompliziert ist:
Schnittstellen beschreiben die Funktionalität einer Datenstruktur, das »was wird geboten«.
Klassen nutzen verschiedene Strategien, um die Vorschriften aus den Schnittstellen umzusetzen; sie stehen für das »wie wird es implementiert«.
Als Entwickler müssen wir Schnittstellen und Implementierungen kennen, und zur Wiederholung schauen wir uns die zentralen Typen noch einmal an, die uns in diesem Kapitel öfter begegnen werden:
Festzuhalten ist:
Iterableist die allgemeinste Schnittstelle, die für das steht, was abgelaufen werden kann;IterableliefertIterator-Instanzen. Nicht nur Datenstrukturen sindIterable.Collectionist die oberste Schnittstelle, die wirklich für Datenstrukturen steht. Sie schreibt Methoden vor zum Hinzufügen von Elementen zur Sammlung oder zum Löschen.Unter
Collectionstehen die eigentlichen Abstraktionen, ob es sich um eine Liste, Menge oder Queue handelt. Darunter finden sich die Implementierungen.Einige Operationen befinden sich nicht bei den Datentypen selbst, sondern sind ausgelagert in eine Klasse
Collections. Ähnliches gilt für Arrays, wo es auch eine Utility-KlasseArraysgibt.
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 müssen bei der Auswahl angestellt werden:
Zugriff über Schlüssel
Duplikate erlaubt
schneller Zugriff
sortiertes Iterieren
threadsicher
Sollte der Zugriff von einem Schlüssel auf einen Wert erfolgen, so ist das im Allgemeinen ein Assoziativspeicher, das heißt eine Implementierung der Schnittstelle Map. Implementierungen von Map sind HashMap, TreeMap und Hashtable. Allerdings sind auch Listen besondere Assoziativspeicher, wobei der Index eine ganze Zahl ist, der bei 0 beginnt und aufsteigend ist. Listen funktionieren immer dann ganz gut, wenn der Schlüssel eine kleine Ganzzahl ist und es wenig Leerräume gibt. Eine Assoziation von beliebigen Ganzzahlen auf Objekte lässt sich mit einer Liste nicht gut abbilden.
Duplikate sind in Listen erlaubt, allerdings nicht in Mengen und Assoziativspeichern. Es gibt durchaus Anforderungen, dass eine Menge vermerken soll, wie oft ein Element vorkommt, doch das muss selbst implementiert werden mit einem Assoziativspeicher, der das Element mit einem Zähler verbindet.
Einen schnellen Zugriff erlauben alle Datenstrukturen. Die Frage ist nur, wonach man fragt. Eine Liste kann nicht schnell die Frage beantworten, ob ein Element vorhanden ist oder nicht, denn die Liste muss dafür von vorne nach hinten durchlaufen werden. Bei einem Assoziativspeicher oder einer Menge ist diese Abfrage durch die interne Organisation der Daten sehr viel schneller. Dieser Existenztest lässt sich bei Datenstrukturen, die intern mit dem Hashing-Verfahren arbeiten, noch etwas schneller beantworten als bei Datenstrukturen, die Elemente sortiert halten.
Listen lassen sich sortieren, und das Ablaufen liefert die Elemente in der sortierten Reihenfolge. Ein TreeSet und eine TreeMap sind ebenfalls nach einem Kriterium sortiert. Die Datenstrukturen mit dem Hashing-Verfahren haben keine benutzerdefinierte Sortierung.
Datenstrukturen lassen sich in drei Gruppen einteilen: Datenstrukturen seit Java 1.0, Datenstrukturen seit Java 1.2 und Datenstrukturen seit Java 5. In den ersten Java-Versionen wurden die Datenstrukturen Vector, Hashtable, Dictionary und Stack eingeführt. Diese Datenstrukturen sind alle threadsicher, doch werden sie heute nicht mehr verwendet. In Java 1.2 wurde die Collection-API eingeführt, alle Datenstrukturen sind nicht threadsicher. Unter Java 5 ist das neue Paket java.util.concurrent eingeführt worden, alle Datenstrukturen dort sind sicher gegen nebenläufige Veränderungen.
1.2. Listen
Bei den Aufgaben wollen wir mit der einfachsten Datenstruktur einsteigen, den Listen. Listen sind Sequenzen von Informationen, bei der die Reihenfolge beim Anhängen neuer Elemente beibehalten wird und Elemente mehrfach vorkommen können. Auch null ist als Element erlaubt.
1.2.1. Singen und Kochen: Listen ablaufen und Eigenschaften prüfen ⭐
Captain CiaoCiao stellt eine neue Mannschaft zusammen. Alle in der Crew haben einen Namen und einen Beruf:
record CrewMember( String name, Profession profession ) {
enum Profession { CAPTAIN, NAVIGATOR, CARPENTER, COOK, MUSICIAN, DOCTOR }
}Bei jeder Crew achtet Captain CiaoCiao darauf, dass es genauso viele Köche wie Musiker gibt.
Aufgabe:
Schreibe eine Methode
areSameNumberOfCooksAndMusicians(List<CrewMember>), dietruezurückgibt, wenn es gleich viele Köche wie Musiker gibt, sonstfalse.
Beispiel:
CrewMember captain = new CrewMember( "CiaoCiao", CrewMember.Profession.CAPTAIN );
CrewMember cook1 = new CrewMember( "Remy", CrewMember.Profession.COOK );
CrewMember cook2 = new CrewMember( "The Witch Cook", CrewMember.Profession.COOK );
CrewMember musician1 = new CrewMember( "Mahna Mahna", CrewMember.Profession.MUSICIAN );
CrewMember musician2 = new CrewMember( "Rowlf", CrewMember.Profession.MUSICIAN );
List<CrewMember> crew1 = List.of( cook1, musician1 );
System.out.println( areSameNumberOfCooksAndMusicians( crew1 ) ); // true
List<CrewMember> crew2 = List.of( cook1, musician1, musician2, captain );
System.out.println( areSameNumberOfCooksAndMusicians( crew2 ) ); // false
List<CrewMember> crew3 = List.of( cook1, musician1, musician2, captain, cook2 );
System.out.println( areSameNumberOfCooksAndMusicians( crew3 ) ); // true1.2.2. Kommentare aus Listen filtern ⭐
Bonny Brain liest ein altes Logbuch von Captain Dipturus Dimwit, das wiederholt immer vier Einträge enthält:
Magnetkompasskurs [1]
Geschwindigkeit der Wasserströmung
Wetter
Kommentare und allgemeine Beobachtungen
Bonny Brain sucht nach einem bestimmten Eintrag in den Kommentaren, daher sollen aus einer Liste mit Zeichenfolgen der erste, zweite und dritte Eintrag gelöscht werden, dass nur noch der vierte Eintrag mit dem Kommentar übrigbleibt.
Aufgabe:
Realisiere eine Methode
void reduceToComments(List<String> lines), die jeweils den ersten, zweiten und dritten Eintrag in der übergebenen Liste löscht und nur den vierten behält.
Beispiele:
"A1", "A2", "A3", "A4", "B1", "B2", "B3", "B4", "C1", "C2", "C3", "C4"→"A4", "B4", "C4"leere Liste → nichts passiert
"A1"→ AusnahmeIllegal size 1 of list, must be divisible by 4
1.2.3. Listen kürzen, denn Abschwung gibt es nicht ⭐
Für Captain CiaoCiao soll es immer nur bergauf gehen; wenn er Zahlenfolgen liest, sollen sie immer nur aufsteigen.
Aufgabe:
Schreibe eine Methode
trimNonGrowingNumbers(List<Double> numbers), die die Liste abschneidet, wenn die nächste Zahl nicht mehr größer oder gleich der vorherigen ist.Bedenke: Die übergebene Liste muss veränderbar sein, sodass Elemente gelöscht werden können.
Beispiele:
Wenn die Liste die Zahlen 1, 2, 3, 4, 5 enthält, bleibt die Liste so.
Enthält die Liste die Zahlen 1, 2, 3, 2, 1, wird die Sequenz gekürzt zu 1, 2, 3.
1.2.4. Essen mit Freunden: Elemente vergleichen, Gemeinsamkeiten finden ⭐
Bonny Brain plant auf dem Festland eine Party, und in einem großen Kreis sollen immer zwei Gäste nebeneinandersitzen, die mindestens eine Gemeinsamkeit haben. Gäste sind durch den folgenden Typ deklariert:
public record Guest(
boolean likesToShoot,
boolean likesToGamble,
boolean likesBlackmail
) { }Aufgabe:
Schreibe eine Methode
int allGuestsHaveSimilarInterests(List<Guest> guests), die-1liefert, wenn alle Gäste einen Nachbarn haben, der in mindestens einer Eigenschaft übereinstimmt. Andernfalls ist die Rückgabe>= 0und der Index auf genau dem ersten Gast, der falsch sitzt, also mit keinem seiner Nachbarn etwas gemeinsam hat.Der Typ
Guestkann beliebig erweitert werden.
1.2.5. Listen auf gleiche Reihenfolge der Elemente prüfen ⭐
Fat Donny Bone Spurs und Ally Al Lyons schmuggeln sich in die Selbsthilfegruppe der anonymen Freibeuter und sollen Captain CiaoCiao berichten, wer im Gesprächskreis rechts neben wem sitzt. Beide versuchen, sich zu erinnern. Sie fangen bei ihren Aufzählungen nicht zwangsläufig mit derselben Person an.
Aufgabe:
Schreibe eine Methode
boolean isSameCircle(List<String> names1, List<String> names2), die testet, ob die Namen in den beiden Listen in der gleichen Reihenfolge unmittelbar aufeinanderfolgen. Bedenke, dass die Personen im Kreis sitzen und die letzte Person in der Liste neben der ersten Person der Liste »sitzt«. Namen der Personen können mehrfach vorkommen.
Beispiele:
Liste 1:
Alexandre, Charles, Anne, Henry. Liste 2:Alexandre, Charles, Anne, Henry→ stimmen übereinListe 1:
Anne, Henry, Alexandre, Charles, Liste 2:Alexandre, Charles, Anne, Henry→ stimmen übereinListe 1:
Alexandre, Charles, Anne, Henry. Liste 2:Alexandre, Charles, Henry, Anne→ stimmen nicht übereinListe 1:
Anne, Henry, Alexandre, Charles, Liste 2:Alexandre, William, Anne, Henry→ stimmen nicht überein
1.2.6. Und jetzt das Wetter: Wiederholte Elemente finden ⭐
Napoleon Nase unterhält sich mit Bonny Brain über das Wetter: »Wir hatten die letzten Monate so viele Regentage hintereinander, das war schlecht für Kaperungen.« Bonny Brain antwortet: »So viele Regentage waren das nicht hintereinander!«. Wer hat recht?
Gegeben ist eine Liste von Wetterdaten:
Regen, Sonne, Regen, Regen, Hagel, Schnee, Sturm, Sonne, Sonne, Sonne, Regen, Regen, Sonne
In der Liste kommt Sonne dreimal hintereinander vor. Das wollen wir wissen. Zwar kommt Regen in der Liste insgesamt häufiger vor, doch das ist für die Lösung nicht relevant.
Aufgabe:
Lege eine neues Record
WeatherOccurrencefür Wetterinformationen an:record WeatherOccurrence( String weather, int occurrences, int startIndex ) { }Implementiere eine Methode
WeatherOccurrence longestSequenceOfSameWeather(List<String> weather), die verrät,welches Wetter
wie oft am häufigsten direkt hintereinander in der Liste auftaucht und
wo die längste Liste anfängt.
Kommt ein Wetter hintereinander gleich oft vor, kann die Methode frei entscheiden, was sie liefert. Elemente dürfen
nullsein.
1.2.7. Bon-Ausgaben erzeugen ⭐
Ein Kassenbon enthält Einträge und Informationen wie Anzahl, Produktname, Preis, Gesamtsumme.
Programmiere in dieser Aufgabe einen Kassenbon.
Aufgabe:
Lege eine neue Klasse
Receiptfür den Bon an.Ein Bon besteht aus Einträgen vom Typ
Item. Lege die KlasseItemals geschachtelten Typ inReceipt.Jedes
Itemhat einen Namen und einen (brutto) Preis, der in Cent gespeichert ist.ReceiptsolltoString()überschreiben und einen formatierten Bon liefern:Gib alle Produkte und die Summe aus.
Einträge können auf dem Bon mehrmals vorkommen und sollen zusammengefasst werden. Es stehen zum Beispiel nicht
Nüsse,Nüsseuntereinander, sondern2x Nüsse. Die Einträge müssen für die Gleichwertigkeit den gleichen Namen und Preis haben.Verwende
NumberFormat.getCurrencyInstance(Locale.GERMANY), um die Währung zu formatieren.
Beispiel:
Mit dem Aufbau
Receipt receipt = new Receipt(); receipt.addItem( new Receipt.Item( "Peanuts", 222 ) ); receipt.addItem( new Receipt.Item( "Lightsaber", 19999 ) ); receipt.addItem( new Receipt.Item( "Peanuts", 222 ) ); receipt.addItem( new Receipt.Item( "Log book", 1000 ) ); receipt.addItem( new Receipt.Item( "Peanuts", 222 ) ); System.out.println( receipt );ist die Ausgabe:
3x Peanuts 2,22 € 6,66 € 1x Lightsaber 199,99 € 199,99 € 1x Log book 10,00 € 10,00 € Sum: 216,65 €
1.2.8. Alles schmeckt besser mit Käse: In Listen Elemente einfügen ⭐
Captain CiaoCiao mag Gemüse, aber wenn, dann muss ordentlich Käse dazu.
Aufgabe:
Schreibe eine Methode
insertCheeseAroundVegetable(List), die eine Liste von Rezeptzutaten bekommt und immer dann, wenn Gemüse in der Liste vorkommt, die Zutat »Käse« direkt davor oder dahinter ergänzt.Die Liste muss veränderbar sein.
Beispiele:
Gnocchi, Zucchini, Paprika, Sahne, Brühe, Milch, Butter, Zwiebel, Tomate, Salz, Pfeffer → Gnocchi, Zucchini, Käse, Paprika, Käse, Sahne, Brühe, Milch, Butter, Zwiebel, Käse, Tomate, Käse, Salz, Pfeffer
Käse → Käse
Greife auf eine feste Menge von Gemüsesorten zurück.
1.2.9. Elemente mit dem Iterator suchen und Covid Cough finden ⭐⭐
Bonny Brain rennt zum Hafen und sucht Covid Cough, der in seinem Schiff Desinfektionsmittel bunkert. Jedes Schiff enthält eine Liste mit Passagiernamen. Schiffe sind durch folgende kleine Klasse deklariert:
class Ship {
private List<String> persons = new ArrayList<>();
void addName( String name ) { persons.add( name ); }
boolean contains( String name ) { return persons.contains( name ); }
@Override public String toString() {
return "" + persons;
}
}Am Hafen liegen 100 Schiffe, die in einer LinkedList<Ship> gespeichert sind. Covid Cough versteckt sich in einem unbekannten Schiff, simulieren wir das:
final int NUMBER_OF_SHIPS = 100;
List<Ship> ships = new LinkedList<>();
for ( int i = 0; i < NUMBER_OF_SHIPS; i++ )
ships.add( new Ship() );
ships.get( new Random().nextInt( ships.size() ) ).addName( "Covid Cough" );Bonny Brain kommt an einem der vielen Zugänge zum Hafen an und rechts sowie links von ihr liegen Schiffe:
int index = new Random().nextInt( ships.size() );
ListIterator<Ship> iterator = ships.listIterator( index );Der einzige Zugriff auf die Schiffe ist durch den ListIterator gegeben. Bedenke, dass man mit dem ListIterator nur nach vorne und zurück gehen kann, es gibt keinen wahlfreien Zugriff!
Aufgabe:
Besuche mit dem
ListIteratordie Schiffe, und finde Covid Cough.Gibt es eine Strategie, wie wir die Person am schnellsten finden? Es ist bekannt, wie viele Schiffe es insgesamt gibt, nämlich 100. Da der Index bekannt ist, an der Bonny Brain den Hafen betritt, weiß man auch, wie viele Schiffe links und rechts vom Eingang liegen.
1.2.10. Elemente verschieben, Reise nach Jerusalem spielen ⭐
Bei einer Geburtstagsfeier spielen die Gäste Reise nach Jerusalem (engl. musical chairs). Die Personen sitzen auf Stühlen, und wenn die Musik anfängt zu spielen, stehen sie auf und laufen um die Stühle. Die Namen der Gäste befinden sich in einer Liste.
Aufgabe A:
Lege eine neue Klasse
MusicalChairsan.Lege einen Konstruktor
MusicalChairs(String... names)an, der die Namen intern speichert.Implementiere die Methode
toString(), die die Namen kommasepariert liefert.Schreibe eine Methode
rotate(int distance), die die Namen in der Liste um die Positiondistancenach rechts verschiebt. Die rechts herausfallenden Elemente werden links wieder eingeschoben. Die Operation ist in place, die (interne) Liste selbst wird also verändert, und die Methode liefert keine Rückgabe.
Nutze für die Aufgabe eine passende Methode aus |
Beispiel:
MusicalChairs musicalChairs =
new MusicalChairs( "Laser", "Milka", "Popo", "Despot" );
musicalChairs.rotate( 2 );
System.out.println( musicalChairs ); // Popo, Despot, Laser, MilkaAufgabe B:
Schreibe eine weitere Methode
void rotateAndRemoveLast(int distance), die zunächst die Liste umdistancePositionen nach rechts verschiebt und dann das letzte Element löscht.Ergänze eine Methode
String play(), dierotateAndRemoveLast(…)in einer Schleife so oft aufruft, bis es nur noch ein Element in der Liste gibt; dann steht der Sieger fest, und er wird als String zurückgegeben. Die Distanz ist bei jedem Durchlauf zufällig.
Berücksichtige bei der Lösung den Fall, dass die Liste leer sein könnte.
1.2.11. Fragespiel mit Planeten programmieren ⭐⭐
Captain CiaoCiao nimmt neue Rekruten an, und um ihr Wissen zu testen, fragt er sie nach dem Durchmesser der Planeten des Sonnensystems. Er wünscht sich dafür eine interaktive Anwendung, bei der zufällig ein Planet ausgewählt wird, und die Rekruten müssen den Durchmesser kennen.
Die Planeten sind als Aufzählungstyp vordefiniert:
enum Planet {
JUPITER( "Jupiter", 139_822 ), SATURN( "Saturn", 116_464 ),
URANUS( "Uranus", 50_724 ), NEPTUNE( "Neptune", 49_248 ),
EARTH( "Earth", 12_756 ), VENUS( "Venus,", 12_104 ),
MARS( "Mars", 6_780 ), MERCURY( "Mercury", 4_780 ),
PLUTO( "Pluto", 2_400 );
public final String name;
public final int diameter; // km
Planet( String name, int diameter ) {
this.name = name;
this.diameter = diameter;
}
}
Aufgabe:
Programmiere eine Konsolenanwendung, die im ersten Schritt eine zufällige Reihenfolge aller Planeten aufbaut. Überlege, wie wir die Methode
shuffle(…)ausjava.util.Collectionsdafür nutzen können.Iteriere über diese zufällige Folge von Planeten, und erzeuge eine Konsolenausgabe, die nach dem Durchmesser dieser Planeten fragt. Als Auswahlmöglichkeit soll der Rekrut vier Durchmesser in Kilometer angezeigt bekommen, wobei ein Durchmesser der korrekte ist und drei Durchmesser von unterschiedlichen Planeten stammen.
Gibt der Rekrut den richtigen Durchmesser ein, erscheint auf dem Bildschirm eine Meldung; wenn der falsche Durchmesser eingegeben wurde, meldet die Konsolenausgabe den korrekten Durchmesser.
Beispiel:
What is the diameter of planet Uranus (in km)? 49248 km 50724 km 12756 km 139822 km 50724 Correct! What is the diameter of planet Pluto (in km)? 12104 km 4780 km 2400 km 12756 km 11111 Wrong! The diameter of Pluto is 2400 km. What is the diameter of planet Jupiter (in km)? 139822 km 6780 km 2400 km 49248 km ...
1.2.12. Implementierung der Klasse java.util.ArrayList verstehen ⭐⭐
Eine java.util.ArrayList ist eine wichtige Datenstruktur. Sie konkurriert direkt mit einem Array. Zwei Fragen kommen in den Sinn: Wie ist die ArrayList eigentlich implementiert, und wie groß könnte der Geschwindigkeitsunterschied sein?
Unter https://github.com/AdoptOpenJDK/openjdk-jdk11/blob/master/src/java.base/share/classes/java/util/ArrayList.java kann man die Quellen der Implementierung einsehen. Schaffe dir einen Überblick.
Intern nutzt die Implementierung für die Daten das Array
elementData. Wie gelingt die Implementierung vonget(int)undset(…)? Wie sind die "Kosten"?Wo wird das Array-Objekt
elementDataangelegt?Eine
ArrayListist in der Regel immer ein bisschen größer als die Anzahl der aktuellen Elemente, als Art Puffer. Die Größe nennt man Kapazität. Wenn man einArrayList-Objekt mit dem Standard-Konstruktor aufbaut, für wie viele Elemente ist im Array Platz?Wenn beim Einfügen das Array zu klein ist, vergrößert
ensureCapacity(…)das Array. Wie funktioniert die Methode? Welche Strategie steckt dahinter?Baue eine
ArrayListmit dem Standard-Konstruktor auf und füge 1.000 Elemente an. Wie viele Kopieroperationen sind nötig?
1.3. Mengen
Mengen enthalten ihre Elemente nur einmal. Sie können unsortiert oder sortiert sein. Java sieht für die Abstraktion die Schnittstelle Set vor, zwei wichtige Implementierungen sind HashSet und TreeSet.
Bei Mengen stellt sich eine ganze Reihe von Fragen:
Ist die Menge leer?
Welche Elemente befinden sich in der Menge?
Ist ein gefragtes Element in der Menge, ja oder nein?
Wenn zwei Mengen gegeben sind, enthalten sie beide die gleichen Elemente?
Wie sieht eine neue Menge aus, wenn zwei Mengen vereinigt werden?
Enthält die Menge eine andere Menge vollständig, ist also eine Menge eine Teilmenge einer anderen?
Was ist bei zwei Mengen die Schnittmenge, also welches sind die Elemente, die in beiden Mengen vorkommen?
Wie sieht die Differenzmenge aus, wenn man also Elemente aus einer Menge löscht, die in einer anderen Menge vorhanden sind?
Einige dieser Operationen lassen sich direkt über den Datentyp Set beantworten. So gibt es z. B. die Methoden isEmpty() oder contains(…). Insbesondere die Mengenoperationen sind nicht sehr gut abgebildet, und Programmierer müssen für sie manchmal Umwege gehen. Für Teilmengen gibt es beispielsweise die Collections-Methode disjoint(Collection<?>, Collection<?>), doch sie liefert ein boolean, das besagt, ob die beiden Sammlungen kein gemeinsames Element haben.
Beantworten wir einige der Fragen durch Aufgaben.
1.3.1. Teilmengen bilden, Gemeinsamkeiten herausfinden ⭐
Die Tochter von Bonny Brain datet Cora Corona, und sie wollen herausfinden, ob sie zusammenpassen. So schreiben beide auf, was sie mögen. Das sieht so aus:
Set<String> hobbies1 = Set.of(
"Candy making", "Camping", "Billiards", "Fishkeeping", "Eating",
"Action figures", "Birdwatching", "Axe throwing" );
Set<String> hobbies2 = Set.of( "Axe throwing", "Candy making", "Camping",
"Action figures", "Case modding", "Skiing", "Satellite watching" );
Aufgabe:
Wie viel Prozent Übereinstimmung haben beide? Mit welchen Methoden können wir die Frage beantworten?
Schaue nach Methoden in |
1.3.2. Alle in einem Wort enthaltenen Wörter ermitteln ⭐⭐
Captain CiaoCiao fängt eine geheime Nachricht ab, und der Text besteht aus Wörtern, die scheinbar zusammenhangslos sind. Nach etwas Grübeln fällt ihm auf, dass in den Wörtern andere Wörter stecken. In »Rhabarbermarmelade« findet er unter anderem »Rhabarber«, »marmelade«, »arme«, »arm«, »lade«, »hab«.
Ein Programm soll herausfinden, welche gültigen Wörter ein gegebenes Wort enthält. Um herauszufinden, was ein gültiges Wort ist, kann man auf eine Wortliste aus dem Internet zurückgreifen:
Aufgabe:
Schreibe ein Programm mit einer statischen Methode
Collection<String> wordList(String string, Collection<String> words), die alle instringenthaltenen Teil-Strings generiert und genau die Wörter in einerCollectionzurückliefert, die in dem Wörterbuchwordsgültige Wörter sind und mindestens drei Buchstaben lang sind.
Beispiel für das englische Wörterbuch:
wordList( "wristwatches", words )→[wrist, wristwatch, wristwatches, rist, ist, twa, twat, wat, watch, watches, tch, tche, che, hes]abibliophobia→[abib, bib, bibl, bibliophobia, pho, phobia, hob, obi, obia]
Eine Datei mit Wörtern lässt sich so in eine Datenstruktur überführen: |
1.3.3. Mit einem UniqueIterator doppelte Elemente ausschließen ⭐⭐
In anderen Datenstrukturen, zum Beispiel Listen, können Elemente mehrfach vorkommen. Schreibe einen UniqueIterator, der Elemente einer Collection nur einmal liefert. null kommt als Element nie vor.
Die generischen Typen werden wie folgt deklariert:
public class UniqueIterator<E> implements Iterator<E> {
public UniqueIterator( Iterator<? extends E> iterator ) {
// ...
}
// usw.
}Am Konstruktor ist abzulesen, dass der neue Iterator einen existierenden Iterator als Parameter bekommt. Ein Beispiel mit Ergebnis könnte so aussehen:
Iterator<String> names = List.of( "Io", "Oz", "Oz", "Io", "Lu" ).iterator();
UniqueIterator<String> uniqueNames = new UniqueIterator<>( names );
while ( uniqueNames.hasNext() )
System.out.println( uniqueNames.next() ); // Io Oz Lu1.4. Assoziativspeicher
Assoziativspeicher verbinden Schlüssel mit Werten. In anderen Programmiersprachen werden sie auch Dictionary genannt. Java schreibt über die Schnittstelle Map die Operationen für alle Implementierungen vor. Zwei wichtige Implementierungen sind HashMap und TreeMap.
1.4.1. Zweidimensionale Arrays in Map konvertieren ⭐
Datentypen, die von Collection erben, sind relativ flexibel in der Annahme von Daten, so lassen sich zum Beispiel die Elemente einer List über addAll(Collection) in ein Set kopieren. Auch Arrays lassen sich mit Arrays.asList(…) direkt als Collection nutzen.
Der Datentyp Map ist weniger flexibel, es lassen sich nicht einfach Arrays oder andere Collection-Sammlungen in eine Map überführen.
Aufgabe:
Schreibe eine Methode
Map<String, String> convertToMap(String[][]), die ein zweidimensionales Array in einejava.util.Mapkonvertiert.Der erste Eintrag im Array soll der Schlüssel, der zweite der Wert sein.
Die Schlüssel implementieren korrekt
hashCode()undequals(…).Kommt später im Array der gleiche Schlüssel nochmals vor, überschreibt die Methode das frühere Pärchen.
Schlüssel und Werte dürfen nicht
nullsein und müssen zu einer Ausnahme führen.
Beispiel:
String[][] array = {
{ "red", "#FF0000" },
{ "green", "#00FF00" },
{ "blue", "#0000FF" }
};
Map<String, String> colorMap = convertToMap( array );
System.out.println( colorMap ); // {red=#FF0000, green=#00FF00, blue=#0000FF}1.4.2. Text in Morsecode konvertieren und umgekehrt ⭐
Captain CiaoCiao muss zu einer entfernten Insel eine Nachricht über Morsecode verschicken. Ein Morse-Funkspruch besteht aus kurzen und langen Symbolen, die mit den Zeichen . und - angedeutet sind.
Kopiere die folgende Definition in eine neue Klasse Morse:
// A .- N -. 0 ----- // B -... O --- 1 .---- // C -.-. P .--. 2 ..--- // D -.. Q --.- 3 ...-- // E . R .-. 4 ....- // F ..-. S ... 5 ..... // G --. T - 6 -.... // H .... U ..- 7 --... // I .. V ...- 8 ---.. // J .--- W .-- 9 ----. // K -.- X -..- // L .-.. Y -.-- // M -- Z --..
Aufgabe:
Lege eine neue Klasse
Morsean.Schreibe zwei Methoden:
String encode(String string). Sie nimmt einen String an und konvertiert ihn in Morsecode. Jedes Zeichen der Zeichenfolge soll im entsprechenden Morsecode ausgegeben werden. Jeder Block soll dabei in der Ausgabe durch ein Leerzeichen getrennt sein. Nicht bekannte Zeichen werden übersprungen. Kleinbuchstaben sollen wie Großbuchstaben gewertet werden. Zwischen den Wörtern gibt es zwei Leerzeichen.String decode(String string). Macht aus Morsecode wieder die Originalzeichenketten. Die zwei Leerzeichen für Worttrenner werden wieder zu einzelnen Leerzeichen.
1.4.3. Worthäufigkeit mit Assoziativspeicher merken ⭐⭐
Girly Gossip lauscht auf dem Deck einer Gruppe, damit sie Captain CiaoCiao später erzählen kann, was gerade diskutiert wird. Wichtig ist das, was als Wort oder Wortfügung oft genannt wird.
Aufgabe:
Schreibe eine Methode
List<String> importantGossip(String... words), die aus einem Vararg von Zeichenfolgen genau die fünf Zeichenketten in einer Liste zurückliefert, die am häufigsten im übergebenen Array vorkommen.
Beispiel:
String[] words = {
"Baby Shark", "Corona", "Baby Yoda", "Corona", "Baby Yoda", "Tiger King",
"David Bowie", "Kylie Jenner", "Kardashian", "Love Island", "Bachelorette",
"Baby Yoda", "Tiger King", "Billie Eilish", "Corona"
};
System.out.println( importantGossip( words ) );gibt aus
[Baby Yoda, Corona, Tiger King, Baby Shark, Bachelorette]
Bedenke, dass es nicht um die einzelnen Wörter wie Baby oder Yoda geht, sondern immer um den gesamten String, also etwa Baby Yoda oder Baby Shark.
1.4.4. Farben einlesen und vorlesen lassen ⭐⭐
Bonny Brain bekommt ein neues Design für ihre Flaggen, doch die Designer sprechen nur Kauderwelsch:
Für den Hintergrund nehmen wir #89cff0 oder #bcd4e6 und für den Text vielleicht #fffaf0 oder #f8f8ff.
Sie findet heraus, dass eine Angabe wie #RRGGBB für den Rot-, Grün-, Blauanteil einer Farbe steht, hexadezimal kodiert. Zum Glück gibt es »Übersetzungstabellen« wie https://tutego.de/download/colors.csv, die Zeilen enthält wie
amber,"Amber",#ffbf00,255,191,0 aqua,"Aqua",#0ff,0,255,255 blush,"Blush",#de5d83,222,93,131 wine,"Wine",#722f37,114,47,55
Teilweise stehen in der Datei die Farbwerte nur mit drei Symbolen, etwa wie im Beispiel aqua mit 0ff. In dem Fall werden die einzelnen Farbangaben verdoppelt, also wird aus #RGB dann #RRGGBB.
Aufgabe:
Lege für die Repräsentation von Farben eine neue Klasse
Coloran. Jede Farbe hat einen Namen (String name) und einen RGB-Wert (int rgb). Schreibe — oder generiere über die IDE — die MethodetoString(). Ergänze weitere Methoden, falls das sinnvoll ist.Lege eine neue Klasse
ColorNamesan.Gib der Klasse eine Objektvariable
HashMap<Integer, Color> colorMap, damit sichColorNamesintern alleColor-Objekte in einerMapmerken kann; die Schlüssel derMapsind die RGB-Werte als Ganzzahl, und der assoziierte Wert ist das entsprechendeColor-Objekt.Kopiere die Datei https://tutego.de/download/colors.csv lokal auf die Festplatte.
Lege einen Konstruktor an, der die Datei einliest. Wir können dafür den
Scannereinsetzen, oder die Datei komplett mitFiles.readAllLines(Paths.get("colors.csv"))einlesen, was eineList<String>liefert.Zerlege jede Zeile der CSV-Quelle, extrahiere den Farbnamen (2. Spalte) und RGB-Wert (3. Spalte). Tipp: Der Farbwert lässt sich mit einer Java-Methode in eine Ganzzahl konvertieren:
Integer.decode("#722f37")liefert7483191. Bedenke, dass Farbangaben in der Form#RGBund#RRGGBBauftreten können.Übertrage den Farbnamen und Ganzzahlwert auf
Color-Objekte, und setze sie in dieMap.Füge eine Methode
decode(int rgb)ein, die für einen RGB-Wert das assoziierteColor-Objekt liefert.
Beispiel:
mapper.decode( 7483191 )→Optional['Wine' is RGB #722F37]mapper.decode( 7 )→Optional.empty
1.4.5. Namen einlesen und Längen verwalten ⭐
Bonny Brain spielt gerne Namens-Kreuzworträtsel, wo jeder Eintrag ein Name ist. Oftmals fällt ihr kein Name mit einer gewissen Länge ein — eine Software soll helfen!
Aufgabe:
Die Datei http://tutego.de/download/family-names.txt enthält Nachnamen. Speichere die Datei auf dem eigenen Dateisystem.
Lies die Datei ein. Dafür können wir zum Beispiel die Klasse
Scannereinsetzen oder dieFiles-MethodereadAllLines(Path).Sortiere die Namen in ein
TreeMap<Integer, List<String>>ein: Der Schlüssel ist die Länge des Namens, die Liste enthält alle Namen mit der gleichen Länge.Liste auf der Kommandozeile alle Namen aufsteigend der Länge nach auf.
Frage von der Kommandozeile nach einer Länge und gibt alle Namen dieser Länge aus, solange die Länge nicht 0 oder negativ ist.
1.4.6. Fehlende Zeichen finden ⭐⭐
Captain CiaoCiao hat sich die Schriftrollen vom Toten Meer (Cumexhopp-Rollen) ergaunert und keiner konnte den Text bisher entschlüsseln. Er möchte es schaffen! Viele Zeichen sind jedoch unleserlich, während andere Zeichen gut lesbar sind. Auch ist gut erkenntlich, wie viele Zeichen das Wort hat.
Aufgabe:
Lege eine neue Klasse mit
main(…)-Methode an und kopiere die zwei Listen in das Programm:List<String> words = Arrays.asList( "house", "mouse", "horn", "cannon" ); List<String> missingLettersWords = Arrays.asList( "_ouse", "ho__", "ca__on", "gun", "__e__", "_____" );Ordne jedem Wort aus
missingLettersWordsalle möglichen Wörter aus dem Wörterbuchwordszu, bei denen der Unterstrich unbekannte Zeichen symbolisiert.Die Länge der vorgeschlagenen Wörter aus dem Wörterbuch muss gleich der Wortlänge des »unleserlichen« Worts sein.
Es muss mindestens ein Zeichen gegeben sein.
Beispiel:
Mögliche Bildschirmausgabe aus den gegebenen Listen:
_ouse -> [mouse, house] ho__ -> [horn] ca__on -> [cannon] gun -> No results __e__ -> No results _____ -> No results
1.4.7. Anzahl Wege zum dreiköpfigen Affen berechnen ⭐⭐
Nach einer durchzechten Nacht in Manhattan vermisst Captain CiaoCiao seinen dreiköpfigen Affen. Er muss das Stofftier irgendwo auf dem Weg verloren haben! Aber wo könnte es sein? Seine Mannschaft muss alle Straßen vom Start zum Ziel ablaufen. Das Einzige, woran Captain CiaoCiao sich noch erinnern kann, ist dass er nicht über die Diagonale gekommen ist.
Das Bild zeigt 4 × 4 Straßenblöcke und es gibt 14 Möglichkeiten. Nach einiger Zeit des Suchens findet die Crew das Stofftier, Glück gehabt!
Captain CiaoCiao überlegt: Was wäre, wenn es 5 oder 10 Blöcke gäbe — wäre die Anzahl der Wege dann nicht viel zu groß zum Suchen?
Die Antwort auf die Frage liefert die Mathematik. Was hier gesucht wird, ist ein monotoner Pfad für ein Quadrat mit n × n Zellen. Die Anzahl möglicher Pfade liefert die Catalan-Zahl, die wie folgt berechnet wird:
Cn = (2n)! / (n+1)! n!
Aufgabe:
Setze die Formel durch eine Methode
BigInteger catalan(BigInteger n)um. Greife intern auf eine eigene MethodeBigInteger factorial(BigInteger n)zur Fakultätsberechnung zurück.In der Formel müssen drei Fakultäten berechnet werden: n!, (n+1)! und (2n)!. Es ist (n+1)! nichts anderes als n! × (n+1) ist, also muss n! zweimal berechnet werden; auch entsteht auf dem Weg zur Berechnung von (2n)! das Zwischenergebnis (n+1)! Viele Multiplikationen müssen also doppelt gemacht werden, daher sollen die Produkte in einem Cache zwischengespeichert werden: greife dafür auf den Datentyp
WeakHashMapzurück.Vergleiche die Zeiten, wenn wir die
catalan(…)-Methode mit den gleichen Parametern zweimal aufrufen. Als Vorlage nutze folgenden Code:long start = System.nanoTime(); BigInteger catalan1000 = catalan( BigInteger.valueOf( 1000 ) ); long end = System.nanoTime(); System.out.println( catalan1000 ); System.out.println( TimeUnit.NANOSECONDS.toMillis( end - start ) );
1.4.8. Feiertage in einem sortierten Assoziativspeicher verwalten ⭐
In einer TreeMap sind die Elemente automatisch sortiert. TreeMap implementiert java.util.NavigableMap, was HashMap hingegen nicht tut. Die Ordnung bestimmt entweder ein externer Comparator, oder die Elemente haben eine natürliche Ordnung.
Der API-Dokumentation entnehmen wir, dass firstEntry() und lastEntry() das kleinste bzw. größte Element liefern. Der Rückgabetyp ist Map.Entry<K,V>.
Ist ein Schlüssel key gegeben, liefern folgende Methoden eine Rückgabe relativ zu diesem Schlüssel:
ceiling*(K key): Liefert ein Ergebnis, das größer oder gleich diesem Schlüssel ist.floor*(K key): Liefert ein Ergebnis, das kleiner oder gleich dem gegebenen Schlüssel ist.lower*(K key): Liefert ein Ergebnis, das echt kleiner als der gegebene Schlüssel ist.higher*(K key): Liefert ein Ergebnis, das echt größer als der gegebene Schlüssel ist.
Alle Methoden liefern null, wenn es keine Antwort auf die Frage gibt.
Für Teilmengen bieten sich die folgenden Methoden an:
SortedMap<K,V> subMap(K fromKey, K toKey)NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
Im ersten Fall ist fromKey inklusiv und toKey exklusiv; das entspricht der üblichen Konvention von Java. Mit der zweiten Methode lässt sich präziser steuern, ob das Start- oder Endelement dazugehört.
Aufgabe:
Baue einen sortierten Assoziativspeicher auf:
NavigableMap<LocalDate, String> dates = new TreeMap<>( Map.of( LocalDate.of( 2024, Month.JANUARY, 1 ), "New Year's Day", … ) );Die Typisierung
<LocalDate, String>bedeutet, dass ein temporaler TypLocalDatemit einem String assoziiert werden soll.Die Klasse
LocalDateimplementiertComparable, das heißt, die Elemente haben eine natürliche Ordnung.Fülle die Datenstruktur mit einigen Paaren für reale oder fiktive Feiertage.
Beantworte mit den passenden Methoden von
NavigableMapfolgende Fragen:Was ist laut Datenstruktur der früheste und letzte Feiertag?
Die Weihnachtsferien enden am 06.01. Was ist nach den Weihnachtsferien der erste Feiertag?
Welche Datumswerte liegen in den Weihnachtsferien vom 23.12. – 06.01. (Datumswerte inklusiv)?
Lösche alle eingetragenen Feiertage, die in den Weihnachtsferien liegen, aus der Datenstruktur.
1.4.9. Gemeinsamkeiten bestimmen: Partygedeck und Mitbringsel ⭐
Bonny Brain plant eine Party, und alle Familien bringen etwas mit:
Set<String> gombonoGifts = new HashSet<>();
Collections.addAll( gombonoGifts, "Vodka", "BBQ Grill", "kneading soap" );
Set<String> banannaGifts = new HashSet<>();
Collections.addAll( banannaGifts, "Vodka", "drinking helmet" );
Set<String> cilimbiGifts = new HashSet<>();
Collections.addAll( cilimbiGifts,
"drinking helmet", "Money box", "Vodka", "water pistol" );
List<Set<String>> families =
Arrays.asList( gombonoGifts, banannaGifts, cilimbiGifts );Da Bonny Brain eine perfekte Strategin ist, will sie wissen, ob Dinge mehrfach mitgebracht werden.
Aufgabe:
Schreibe eine Methode
printMultipleGifts(List<Set<String>> families), die ausgibt, welche Dinge wie oft mitgebracht werden.Was wurde mehr als einmal mitgebracht?
Beispiel:
Mögliche Ausgabe bei den oberen Belegungen:
{drinking helmet=2, kneading soap=1, water pistol=1, Money box=1, BBQ Grill=1, Vodka=3} drinking helmet Vodka
1.5. Properties
Die Klasse Properties ist ein besonderer Assoziativspeicher, der nur Strings mit Strings assoziiert. Die Klasse repräsentiert nicht nur eine Datenstruktur, sondern kann auch Dateien lesen und schreiben, die sogenannten Property-Dateien. Das sind Textdateien, die in der Regel zur Konfiguration verwendet werden. Schlüssel-Wert-Paare sind in der Datei durch = getrennt. Auch lassen sich die Werte in einem XML-Format lesen und schreiben, doch das ist unüblich.
1.5.1. Komfortablen Properties-Dekorator entwickeln ⭐⭐
Die Klasse Properties enthält Schlüssel-Wert-Paare, wobei die Schlüssel immer nur Strings sind. Mögliche Konvertierungen müssen Entwickler selbst vornehmen, was lästig ist.
Aufgabe:
Schreibe eine Klasse PropertiesConfiguration, die ein Properties-Objekt dekoriert. Die allgemeinste Methode liefert ein Optional, das entweder gefüllt ist oder leer, wenn es den Schlüssel nicht gibt:
Optional<String> getString(String key)
Der Vorteil beim Optional ist, dass einfach Alternativen für Default-Werte bestimmt werden können: conf.getProperty("rank").orElse("Captain").
Weitere Methoden von PropertiesConfiguration sollen Konvertierungen durchführen:
Optional<Boolean> getBoolean(String key)OptionalLong getLong(String key)OptionalDouble getDouble(String key)Optional<BigInteger> getBigInteger(String key)
Wenn es zu dem Schlüssel keinen assoziierten Wert gab, ist der Behälter leer. Wenn die Konvertierung zu einem Fehler misslingt, führt das ebenfalls zu einem leeren Behälter.
Beispiel für die API:
Properties root = new Properties();
root.setProperty( "likes-rum", "true" );
root.setProperty( "age", "55" );
root.setProperty( "income", "123456789012" );
root.setProperty( "hobbies", "drinking, gambling\\, games, swearing competitions" );
root.setProperty( "weakness_of_character", "" );
PropertiesConfiguration conf = new PropertiesConfiguration( root );
Optional<Boolean> maybeLikesRum = conf.getBoolean( "likes-rum" );
OptionalLong maybeAge = conf.getLong( "age" );
Optional<BigInteger> maybeIncome = conf.getBigInteger( "income" );
System.out.println( maybeLikesRum ); // Optional[true]
System.out.println( maybeAge ); // OptionalLong[55]
System.out.println( maybeIncome ); // Optional[123456789012]Optionale Ergänzung: Listen erfragen
Fortgeschrittene Entwickler können folgende Methode implementieren:
List<String> getList(String key). Liefert eine Liste von kommaseparierten Strings. Das Komma selbst kann durch\,ausmaskiert werden.
Ein Beispiel:
List<String> hobbies = conf.getList( "hobbies" );
List<String> weaknessOfCharacter = conf.getList( "weakness_of_character" );
System.out.println( hobbies ); // [drinking, gambling, games, swearing competitions]
System.out.println( hobbies.size() ); // 3
System.out.println( weaknessOfCharacter ); // []Optionale Ergänzung: Binäre Werte speichern
Eine java.util.HashMap kann beliebige Typen assoziieren, bei einer Properties können nur Strings mit Strings assoziiert werden. Sind andere Datentypen, wie byte-Arrays, zu speichern, müssen sie in einen String konvertiert werden. Ein byte[] kann auf unterschiedliche Weise in einen ASCII-String konvertiert werden, etwa über die BASE64-Kodierung; Java kann das über die Klasse Base64.
Da Properties eher gelesen als geschrieben werden, reichten uns bisher die get*(…)-Methoden. Bei folgender Ergänzung sollen zwei neue Methoden geschrieben werden, eine zum Setzen und eine zum Abfragen:
void putBinary(String key, byte[] bytes)Optional<byte[]> getBinary(String key)
Ein Anwendungsbeispiel:
conf.putBinary( "binary", new byte[]{ 0, 1, 127, (byte) 254, (byte) 255 } );
System.out.println( conf.getString( "binary" ) ); // Optional[AAF//v8=]
conf.getBinary( "binary" ).ifPresent( binary ->
System.out.printf( "%d %d %d %d %d",
binary[0], binary[1], binary[2], binary[3], binary[4] )
);1.5.2. INI-Dateien einlesen und als Properties repräsentieren ⭐⭐
In der Windows-Welt gibt es INI-Dateien für Konfigurationen. Das Dateiformat ist sehr einfach:
Mit
[Sektion]werden Bereiche gestartetSchlüssel-Wert-Paare werden mit
=getrennt, wie auch die Java-Properties.Zeilenkommentare beginnen mit
;oder#.Am Anfang können Schlüssel-Wert-Paare ohne vorherige Sektion erscheinen, das sind dann globale Properties.
Aufgabe:
Schreibe ein Programm, was Strings im INI-Format in ein
Properties-Objekt überführt.Die Sektionen werden zu Präfixen, die Schlüssel folgen mit
.separiert.
Beispiel:
date=9.6.2020 [personal] name=CiaoCiao rank=Captain # Some details [professional.detail] job=pirat tough_cookie=
Aus dem gegebenen Beispiel soll ein Properties-Objekt mit folgenden Einträgen entstehen:
date=9.6.2020 personal.name=CiaoCiao personal.rank=Captain professional.detail.job=pirat professional.detail.tough_cookie=
Melde Fehler, wenn es zu einem Schlüssel mehrere Assoziationen gibt. Melde auch einen Fehler, wenn es eine Zeile ohne = gibt. Schlüssel ohne Werte, wie in tough_cookie= sind in Ordnung.
link:solutions/src/main/java/com/tutego/exercise/util/IniParser.java[Lösung
1.6. Stapelspeicher (Stack) und Warteschlangen (Queue)
Eine allgemeine Liste erlaubt in Java den Zugriff auf die Elemente über einen Index, wir nennen so einen Zugriff auch wahlfreien Zugriff, weil wir die Wahl haben, an jeder Stelle ein Element zu erfragen. Es gibt Datenstrukturen, die deutlich eingeschränkter sind und z. B. nur Elemente am Anfang oder am Ende einfügen oder löschen können. Dazu zählen:
Stapelspeicher (Stacks)
Warteschlangen (Queues)
Bei einem Stapelspeicher kann man nur an einem Ende Elemente einfügen und muss an diesem Ende die Elemente wieder entnehmen. Das Prinzip wird auch LIFO genannt: Last In, First Out. Im Gegensatz dazu steht die Queue. Bei ihr wird zunächst das als Erstes ausgelesen, was auch als Erstes hinzugefügt wurde. Das Prinzip heißt FIFO: First In, First Out.
Reine Stacks und Queues gibt es in Java nicht, nur Schnittstellen, die von Listen implementiert werden.
1.6.1. UPN-Taschenrechner programmieren ⭐
Mathematische Ausdrücke schreiben wir in der Regel in der Infixnotation, bei der die Operatoren zwischen den Operanden stehen, etwa 47 + 11. Prinzipiell kann der Operator aber auch vor den Operanden stehen, wie + 47 11, oder dahinter, wie in 47 11 +.
Die Taschenrechner von Hewlett-Packard hatten in den 1980er-Jahren eine besondere Eingabe etabliert, die umgekehrte polnische Notation (UPN). Das ist eine Postfix-Notation, bei der die Operatoren hinter den Werten stehen. Der Vorteil für die Computer ist, dass der Vorrang — Punktrechnung geht vor Strichrechnung — von den Nutzern schon aufgelöst wurde, was die Programmlogik im Taschenrechner vereinfacht. Auch PostScript nutzt diese Darstellung, denn über einen Stack können mathematische Ausdrücke einfach ausgewertet werden.[2]
Wir wollen einen UPN-Rechner programmieren.
Aufgabe:
Schreibe ein Programm, das als Erstes einen String wie etwa
"12 34 23 + *"in Tokens zerlegt. Tipp: Zum Zerlegen lässt sichsplit(…)vonStringoder einScannernutzen.Nach dem Zerlegen soll das Ergebnis auswertet werden. Beginne mit einem festen String zum Testen.
Lies von der Kommandozeile einen String ein, sodass wir einen echten UPN-Taschenrechner haben.
Welche Fehler und Probleme müssen behandelt und abgefangen werden? Wie sollten wir Fehler behandeln?
1.6.2. Designfehler bei java.util.Stack erkennen ⭐⭐
Die Java-Bibliothek bietet zwar eine Klasse java.util.Stack, die wird in der Praxis allerdings nicht verwendet.
Welche Methoden besitzt ein
Stack? Gibt es Methoden, die für einenStackunangebracht sind?Wenn man sich die Vererbungshierarchie der Klasse
Stackansieht, so fällt auf, dass sie vonjava.util.Vectorabgeleitet wird. Bewerte die Implementierung aus der Sicht eines API-Designers. Ist das Design eher gut oder eher schlecht? Kann es vielleicht die First-In-First-Out-Semantik zerstören?
1.7. BitSet
Die Klasse BitSet ist eine platzsparende und performante Alternative zu boolean-Arrays. Nützlich ist die Datenstruktur dann, wenn man eine Abbildung einer Ganzzahl auf einen Wahrheitswert benötigt. Die Datenstruktur kann schnell beantworten, ob ein Index (eine positive Ganzzahl) mit true oder false assoziiert ist. Wenn die Anzahl der Bits zu groß wird, oder wenn es große Lücken gibt, ist https://github.com/brettwooldridge/SparseBitSet eine gute Alternative.
1.7.1. Vergiss kein Schiff ⭐
Einmal im Jahr findet eine Übung statt, bei der 13 Schiffe geentert werden müssen. Jedes der Schiffe ist durch eine Zahl von 10 bis 22 eindeutig gekennzeichnet. An Ende bekommt Bonny Brain eine Liste von Schiffen, die von der Crew überfallen wurden. Die Liste kann so aussehen:
{10, 20, 21, 15, 16, 17, 18, 19, 11, 12, 13, 14, 22 }
Bisweilen bekommt sie Listen, bei denen Zahlen fehlen oder doppelt auftauchen:
{10, 20, 21, 15, 16, 17, 18, 22 }
{10, 20, 21, 10, 15, 16, 10 }
Solche Listen zeigen Bonny Brain, dass bei der Übung Schiffe vergessen oder wiederholt überfallen wurde. Da eine händische Prüfung lästig ist, soll eine Software die Prüfung übernehmen.
Aufgabe:
Lege eine neue Klasse mit einer neuen statischen Methode
checkForCompletedCompetition(int... shipIds)an. Übergeben werden die IDs der Schiffe.Melde, welches Schiffe mehrfach überfallen wurden. Die Anzahl ist egal.
Melde, wenn ein Schiff nicht überfallen wurde und welches das war.
Schreibe das Programm so, dass keine zwei ineinadergeschachtelten Schleifen verwendet werden. Anders gesagt: Die Laufzeit soll nicht quadratisch sein.
1.7.2. Finde doppelte Einträge, und löse das tierische Chaos ⭐
Captain CiaoCiao füttert vor dem Zubettgehen die Tiere seines Privatzoos. Doch da er vom Rum etwas angeschickert ist, vergisst er, das Tor zu schließen. Am nächsten Morgen bemerken Gabi Gräte und Fred Fritte, dass Tiere fehlen. Schnell laufen sie zu Captain CiaoCiao: »Einige Tiere sind entflohen!« — »Beim Klabautermann! Welche?«, fragt der Captain. Die beiden überlegen und zeichnen auf (Schreiben ist nicht ihre Stärke):
🐩🐏🐴🦋🐙
🐴🐏🐧🐸🦋🐌
Captain CiaoCiao stellt fest, dass beide ein schlechtes Gedächtnis haben, und will nur Tiere suchen lassen, die von beiden genannt werden.
Aufgabe:
Schreibe eine Methode
String sameSymbols(String, String), die eine Zeichenfolge mit den gemeinsamen Symbolen zurückliefert. Auf die Reihenfolge kommt es nicht an, alle Unicode-Zeichen sind möglich.Da wir über den
Stringlaufen müssen und dieser »höhere« Unicodezeichen enthält, die durch zweicharausgerückt werden, soll die Lösung aufstring.codePoints().forEach(consumer)zurückgreifen. Diese Anweisung läuft über alle Zeichen des Stringsstringund ruft den übergebenenIntConsumerfür jedes Zeichen auf. Das ist eine Anwendung der Stream-API, die wir uns im folgenden Kapitel genauer anschauen werden.
Beispiele:
sameSymbols("🐩🐏🐴🦋🐙", "🐴🐏🐧🐸🦋🐌")→"🐏🐴🦋"sameSymbols("abcy", "bcd")→"bc"sameSymbols("abc", "def")→""
Da das Ergebnis eilt, ist die Methode so zu implementieren, dass die Laufzeit linear mit der Länge der Zeichenfolgen ist, in Informatiksprech: O(N+M), wenn N und M die Längen der Zeichenfolgen sind. Es sind alle Unicode-Zeichen erlaubt.
1.8. Threadsichere Datenstrukturen
Für die bisherigen Aufgaben rund um die Datenstrukturen ArrayList, LinkedList, HashSet, TreeSet usw. haben wir nie mehr als den Main-Thread benötigt. Bei den folgenden Aufgaben kommen mehr Threads und nebenläufige Zugriffe ins Spiel, und dann müssen wir threadsichere Datenstrukturen verwenden. Für die Lösungen wollen wir auf die Datentypen aus dem Paket java.util.concurrent zurückgreifen, in der eine ganze Reihe von threadsichere Datenstrukturen deklariert werden, die auch bei einer beliebigen Anzahl paralleler Zugriffe korrekt arbeiten und eine sehr gute Performance aufweisen.
1.8.1. Unterschied zwischen HashMap, Synchronized-Wrapper, ConcurrentHashMap verstehen
Die Datenstrukturen aus der Collection-API sind nicht threadsicher. Im Paket java.util.concurrent gibt es dahingehend Datenstrukturen, auf die man mit vielen Threads zugreifen kann.
Lege eine
HashMapan und schreibe mit vielen Threads nebenläufig in die Datenstruktur; sie wird kaputt gehen, wie kann man das sehen?Nutze den Synchonized-Wrapper
Collections.synchronizedMap()und versuche es erneut. Wie ist das Ergebnis?Nutze eine
ConcurrentHashMap. Was passiert hier, wenn man mit mehreren Threads darauf zurückgreift? Was hat sie für einen Vorteil gegenüber dem Synchronized-Wrapper?Es gibt noch
Hashtable, woher kommt die Klasse und nutzt man sie noch?
1.8.2. Schiff beladen ⭐⭐
Captain CiaoCiao und Crew macht sich bereit für das nächste große Abenteuer auf der Insel Gazorpazorp. 5 Mitarbeiter stellen Kisten und Fässer auf die Laderampe, und 10 Mitarbeiter verstauen die Waren im Schiff. Auf der Laderampe können höchstens 5 Objekte gleichzeitig stehen.
Aufgabe:
Erzeuge für die Rampe eine
ArrayBlockingQueue<String>der Kapazität 5.Erzeuge zwei verschiedene
Runnable-ImplementierungenLoaderundUnloader, die einen Verweis auf dieArrayBlockingQueuebekommen.Der
Loaderstellt Strings auf die Rampe (zufällige Strings aus einer Menge von Produktnamen).Der
Unloadersoll Strings von der Rampe nehmen und auf dem Bildschirm ausgeben.Es brauchen
LoaderundUnloaderfür ihre Arbeit zufällig zwischen 1 und 2 Sekunden.
5 Threads sollen
Unloaderund 10 ThreadsLoadersein.
Für das Hinzufügen und Herausnehmen gibt es unterschiedliche Methoden. Der Unterschied ist wichtig, sonst kann es zu Programmfehlern kommen:
Aus den Methodennamen kann man die Semantik nicht ableiten, den Unterschied muss man lernen. Für unsere Aufgabe kommt nur eine Spalte und diese Methoden in Frage. |
1.8.3. Wichtige Nachrichten als Erstes bearbeiten ⭐⭐
Eine PriorityQueue hat eine interne Sortierung, sodass die Elemente mit einer höheren Priorität nach vorne wandern. Die Priorität ergibt sich entweder aus der natürlichen Ordnung der Elemente, die Comparable implementieren, oder einem externen Comparator. »Kleine« Elemente haben eine größere Priorität und wandern in der PriorityQueue nach vorne. Am Ende der Queue stehen die Elemente mit der niedrigsten Priorität. (Das ist so wie bei den Impfungen: Die Priorisierungsgruppe 1 bekommt den Stoff zuerst.)
Captain CiaoCiao bekommt von verschiedenen Seiten Arbeitsaufträge, aber alles von Bonny Brain hat oberste Priorität. Jeder Arbeitsauftrag von Bonny Brain enthält das Kosewort »Little Canon«, das den Captain wissen lässt, dass er ihr Kanönchen ist und dass es Zeit ist, sofort in Aktion zu treten.
Aufgabe:
Lege folgendes Record in das Projekt:
record Message( String message, LocalDateTime timestamp ) { Message( String message ) { this( Objects.requireNonNull( message ), LocalDateTime.now() ); } @Override public String toString() { return "'%s', %s".formatted( message, timestamp.format( DateTimeFormatter.ofPattern("mm:ss.SSSSSSS") ) ); } }toString()setzt die Nachricht in einfache Anführungszeichen und zeigt vom Zeitstempels nur die Minuten und Sekunden an, denn das reicht für einen schnellen optischen Vergleich, welche Nachricht jünger oder älter ist.Implementiere für
MessageeinenComparator, der eine Ordnung schafft, sodass Nachrichten mit dem Kosewort »kleiner« sind als Nachrichten ohne Kosewort, damit das später als höhere Priorität gewertet werden kann. Wenn beide Nachrichten ein Kosewort enthalten oder beide Nachrichten kein Kosewort enthalten, sind sie gleich »groß«.Erweitere den
Comparatorum eine weitere Vergleichslogik, so dass der Zeitstempel berücksichtigt wird und eine frühere Nachricht auch früher bearbeitet wird.Initialisiere die
PriorityQueuemit Nachrichten, und beobachte, wie Nachrichten mit dem Kosewort in der Queue nach vorne wandern.
Beispiel:
Unter der Annahme, dass PriorityQueue<Message> tasks eine korrekt initialisierte Datenstruktur ist, wird es bei folgendem Programm zu der dargestellten Ausgabe kommen:
tasks.add( new Message( "Treasure Hunt" ) );
System.out.println( "= " + tasks );
tasks.add( new Message( "Little Canon, Family Movie Night!" ) );
System.out.println( "= " + tasks );
tasks.add( new Message( "Build a pirate ship" ) );
System.out.println( "= " + tasks );
System.out.println( tasks.remove() + "\n" + "= " + tasks );
System.out.println( tasks.remove() + "\n" + "= " + tasks );
tasks.add( new Message( "Capture the Flag" ) );
System.out.println( "= " + tasks );
tasks.add( new Message( "Bury the treasure, Little Canon" ) );
System.out.println( "= " + tasks );
tasks.add( new Message( "Little Canon, make a treasure map" ) );
System.out.println( "= " + tasks );
for ( int i = 0; i < 4; i++ )
System.out.println( tasks.remove() + "\n" + "= " + tasks );Die Ausgabe ist:
= ['Treasure Hunt', 44:20.8500129] = ['Little Canon, Family Movie Night!', 44:20.8580242, 'Treasure Hunt', 44:20.8500129] = ['Little Canon, Family Movie Night!', 44:20.8580242, 'Treasure Hunt', 44:20.8500129, 'Build a pirate ship', 44:20.8590231] 'Little Canon, Family Movie Night!', 44:20.8580242 = ['Treasure Hunt', 44:20.8500129, 'Build a pirate ship', 44:20.8590231] 'Treasure Hunt', 44:20.8500129 = ['Build a pirate ship', 44:20.8590231] = ['Build a pirate ship', 44:20.8590231, 'Capture the Flag', 44:20.8665477] = ['Bury the treasure, Little Canon', 44:20.8665477, 'Capture the Flag', 44:20.8665477, 'Build a pirate ship', 44:20.8590231] = ['Bury the treasure, Little Canon', 44:20.8665477, 'Little Canon, make a treasure map', 44:20.8665477, 'Build a pirate ship', 44:20.8590231, 'Capture the Flag', 44:20.8665477] 'Bury the treasure, Little Canon', 44:20.8665477 = ['Little Canon, make a treasure map', 44:20.8665477, 'Capture the Flag', 44:20.8665477, 'Build a pirate ship', 44:20.8590231] 'Little Canon, make a treasure map', 44:20.8665477 = ['Build a pirate ship', 44:20.8590231, 'Capture the Flag', 44:20.8665477] 'Build a pirate ship', 44:20.8590231 = ['Capture the Flag', 44:20.8665477] 'Capture the Flag', 44:20.8665477 = []
1.8.4. Wenn verbraucht, dann neu ⭐⭐⭐
Der Ausdruck new BigInteger(1024, new SecureRandom()) erzeugt eine große Zufallszahl vom Typ BigInteger.
Aufgabe:
Schreibe eine eigene Klasse
SecureRandomBigIntegerIterator, dieIteratorimplementiert und unendlich vieleBigIntegerliefern kann.Immer dann, wenn die Zahl abgefragt und »verbraucht« wird, soll ein Hintergrund-Thread automatisch eine neue Zufallszahl berechnen.
1.9. Googles Java SE-Ergänzung Guava
Auch wenn die Java Standard Bibliothek die zentralen Datenstrukturen wie Listen, Mengen, Assoziativspeicher mitbringt, fehlt doch einiges. Es gibt z. B. keine bidirektionalen Maps, keine Tabellen, keine konfigurierbare Cache-Implementierung, es gibt keine Bags, so etwas wie Mengen, die allerdings einen Zähler verwalten für die Anzahl gleicher Elemente.
Zwei bekannten Erweiterungen der Standardbibliotheken sind:
Apache Commons Collections: https://commons.apache.org/proper/commons-collections/
Die folgenden Aufgaben lassen sich ganz gut mit den erweiterten Möglichkeiten von Guava nutzen.
Nimm zur Vorbereitung folgende Dependency in der Maven-POM mit auf:
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>30.1-jre</version>
</dependency>1.9.1. Telefonnummern Wörtern zuweisen ⭐⭐
Bonny Brain findet ein altes Telefonbuch und dort sind die Nummern über Buchstaben kodiert, vermutlich, um sie sich leichter merken zu können. Sie möchte die Nummern in ihre Kontaktverwaltung übertragen und benötigt eine Umrechnung in die Ziffernfolge.
Die Zuordnung von Buchstaben zu den Ziffern sieht so aus:
| Nummer | Buchstaben |
|---|---|
0 | - |
1 | - |
2 | A, B, C |
3 | D, E, F |
4 | G, H, I |
5 | J, K, L |
6 | M, N, O |
7 | P, Q, R, S |
8 | T, U, V |
9 | W, X, Y, Z |
Aufgabe:
Schreibe eine Methode, die aus einem String mit Buchstaben die korrekte Nummernfolge macht.
Bonny Brain erkennt, dass das Umsetzen von Nummern in Buchstaben clever ist. Schreibe eine Methode, die aus einer Ziffernfolge alle denkbaren Symbolfolgen generiert. 0 soll dabei 0 bleiben und 1 ebenso 1.
Beispiel:
String number = "624";
List<String> words = numberToWords( number );
words.forEach( word -> System.out.println( word + " -> " + wordToNumber( word ) ) );liefert die Ausgabe
NAG -> 624 NAH -> 624 NAI -> 624 NBG -> 624 NBH -> 624 NBI -> 624 NCG -> 624 NCH -> 624 NCI -> 624 MAG -> 624 MAH -> 624 MAI -> 624 MBG -> 624 MBH -> 624 MBI -> 624 MCG -> 624 MCH -> 624 MCI -> 624 OAG -> 624 OAH -> 624 OAI -> 624 OBG -> 624 OBH -> 624 OBI -> 624 OCG -> 624 OCH -> 624 OCI -> 624
1.9.2. Windgeschwindigkeit in Beaufortskala konvertieren ⭐
Captain CiaoCiao ist mit der Beaufortskala vertraut und sowieso mit jeder Arbeit von Sir Francis Beaufort, den er für die genauen Seekarten bewundert.
Der Urlaub auf einem echten Segelboot ist gar nicht mehr entspannend, als bei einem Unglück der Steuermann Suki Sushi von Bord gegangen ist; nun muss ein Leichtmatrose das Windmessgerät ablesen und Captain CiaoCiao die Windgeschwindigkeit übermitteln. Die Windgeschwindigkeit möchte Captain CiaoCiao aber gar nicht wissen, sondern nur die Beaufortskala.
| Beaufortskala | Windgeschwindigkeit | Bezeichnung |
|---|---|---|
0 Bft | 0 km/h | Windstille |
1 Bft | 1 - 5 km/h | leichter Zug |
2 Bft | 6 - 11 km/h | leichte Brise |
3 Bft | 12 - 19 km/h | schwache Brise |
4 Bft | 20 - 28 km/h | mäßige Brise |
5 Bft | 29 - 38 km/h | frische Brise |
6 Bft | 39 - 49 km/h | starker Wind |
7 Bft | 50 - 61 km/h | steifer Wind |
8 Bft | 62 - 74 km/h | stürmischer Wind |
9 Bft | 75 - 88 km/h | Sturm |
10 Bft | 89 - 102 km/h | schwerer Sturm |
11 Bft | 103 - 117 km/h | orkanartiger Sturm |
12 Bft | > 117 km/h | Orkan |
Aufgabe:
Schreibe eine Methode, die die Windgeschwindigkeit in die Beaufortskala konvertiert.
1.9.3. Feststellen, ob jemand noch nicht überfallen wurde ⭐
Captain CiaoCiao hat seine Prinzipien: Hat er einen reichen Händler ausgeraubt, ist er anständig genug, ihn nicht wieder auszurauben. Deshalb schreibt er alle Namen seiner Opfer in eine Art Logbuch. Doch kodiert er die Namen, damit sich ein Händler nicht selbst verschonen kann. Außerdem muss das Logbuch kompakt sein, denn Captain CiaoCiao möchte immer eine ausgedruckte Version bei sich tragen.
Das Logbuch von Captain CiaoCiao soll eine spezielle Datenstruktur mit dem Namen Bloomfilter sein. Damit kann man effizient — und mit wenig Speicherverbrauch — überprüfen, ob ein Element nicht in einem Container enthalten ist, aber nur mit einer gewissen Wahrscheinlichkeit eine Antwort bekommen, ob ein Element enthalten ist. Für Captain CiaoCiao ist das in Ordnung, denn sein Logbuch hilft ihm festzustellen, ob ein Name definitiv nicht vorkommt und somit ein Kandidat für den nächsten Überfall ist.
Aufgabe:
Gegeben ist folgende Liste früherer Opfer:
String[] names = { "Thomas Geldregen", "Rainer Reichtum", "Heinz Goldsocken", "Gisela von Prunk", "Herbert Gönnemeyer", "Linda Edel", "Florian Silber" };Nutze die Klasse
BloomFiltervon Guava und kopiere die Namen in diese Datenstruktur.Erfrage von der Kommandozeile einen Namen und teste, ob dieser nicht in der Datenstruktur ist.
Das Guava-Team hat unter https://github.com/google/guava/wiki/HashingExplained#bloomfilter eine kurze (englische) Einführung geschrieben. |
Noch mehr Aufgaben findest du im Buch: ›Captain CiaoCiao erobert Java: Das Trainingsbuch für besseres Java. 300 Java-Workshops, Aufgaben und Übungen mit kommentierten Lösungen‹