Rheinwerk Computing < openbook > Rheinwerk Computing - Professionelle Bücher. Auch für Einsteiger.
Professionelle Bücher. Auch für Einsteiger.

Inhaltsverzeichnis
Vorwort
1 Java ist auch eine Sprache
2 Imperative Sprachkonzepte
3 Klassen und Objekte
4 Der Umgang mit Zeichenketten
5 Eigene Klassen schreiben
6 Exceptions
7 Äußere.innere Klassen
8 Besondere Klassen der Java SE
9 Generics<T>
10 Architektur, Design und angewandte Objektorientierung
11 Die Klassenbibliothek
12 Einführung in die nebenläufige Programmierung
13 Einführung in Datenstrukturen und Algorithmen
14 Einführung in grafische Oberflächen
15 Einführung in Dateien und Datenströme
16 Einführung in die <XML>-Verarbeitung mit Java
17 Einführung ins Datenbankmanagement mit JDBC
18 Bits und Bytes und Mathematisches
19 Die Werkzeuge des JDK
A Die Klassenbibliothek
Stichwort

Download:
- Aufgaben, ca. 1,1 MB
- Programme, ca. 12,8 MB

Buch bestellen
Ihre Meinung?

Spacer
Java ist auch eine Insel von Christian Ullenboom
Das umfassende Handbuch
Buch: Java ist auch eine Insel

Java ist auch eine Insel
Galileo Computing
1308 S., 10., aktualisierte Auflage, geb., mit DVD
ca. 49,90 Euro, ISBN 978-3-8362-1802-3
Pfeil 13 Einführung in Datenstrukturen und Algorithmen
Pfeil 13.1 Datenstrukturen und die Collection-API
Pfeil 13.1.1 Designprinzip mit Schnittstellen, abstrakten und konkreten Klassen
Pfeil 13.1.2 Die Basis-Schnittstellen Collection und Map
Pfeil 13.1.3 Die Utility-Klassen Collections und Arrays
Pfeil 13.1.4 Das erste Programm mit Container-Klassen
Pfeil 13.1.5 Die Schnittstelle Collection und Kernkonzepte
Pfeil 13.1.6 Schnittstellen, die Collection erweitern und Map
Pfeil 13.1.7 Konkrete Container-Klassen
Pfeil 13.1.8 Generische Datentypen in der Collection-API
Pfeil 13.1.9 Die Schnittstelle Iterable und das erweiterte for
Pfeil 13.2 Listen
Pfeil 13.2.1 Erstes Listen-Beispiel
Pfeil 13.3 Mengen (Sets)
Pfeil 13.3.1 Ein erstes Mengen-Beispiel
Pfeil 13.3.2 Methoden der Schnittstelle Set
Pfeil 13.4 Assoziative Speicher
Pfeil 13.4.1 Die Klassen HashMap und TreeMap
Pfeil 13.4.2 Einfügen und Abfragen der Datenstruktur
Pfeil 13.4.3 Über die Bedeutung von equals() und hashCode()
Pfeil 13.5 Mit einem Iterator durch die Daten wandern
Pfeil 13.5.1 Die Schnittstelle Iterator
Pfeil 13.5.2 Der Iterator kann (eventuell auch) löschen
Pfeil 13.6 Algorithmen in Collections
Pfeil 13.6.1 Die Bedeutung von Ordnung mit Comparator und Comparable
Pfeil 13.6.2 Sortieren
Pfeil 13.6.3 Den größten und kleinsten Wert einer Collection finden
Pfeil 13.7 Zum Weiterlesen

Rheinwerk Computing - Zum Seitenanfang

13.6 Algorithmen in CollectionsZur nächsten Überschrift

Um Probleme in der Informatik zu lösen, ist die Wahl einer geeigneten Datenstruktur nur der erste Schritt. Im zweiten Schritt müssen Algorithmen implementiert werden. Da viele Algorithmen immer wiederkehrende (Teil-)Probleme lösen, hilft uns auch hier die Java-Bibliothek mit einigen Standardalgorithmen weiter. Dazu zählen etwa Methoden zum Sortieren und Suchen in Containern und zum Füllen von Containern. Einige Algorithmen sind Teil der jeweiligen Datenstruktur selbst, andere wiederum befinden sich in der Extraklasse java.util.Collections. Diese Utility-Klasse, die wir nicht mit dem Interface Collection verwechseln dürfen, bietet Methoden, um zum Beispiel

  • Listen zu sortieren, zu mischen, umzudrehen, zu kopieren und zu füllen,
  • Elemente nach der Halbierungssuche zu finden,
  • die Anzahl equals()-gleicher Elemente zu ermitteln,
  • Extremwerte zu bestimmen,
  • Elemente in einer Liste zu ersetzen und
  • Wrapper um existierende Datenstrukturen zu legen.
Abbildung

Abbildung 13.6: UML-Diagramm von Collection

Viele Algorithmen sind nur auf List-Objekten definiert, denn der einfache Typ Collection reicht oft nicht aus. Das ist nicht erstaunlich, denn wenn ein Container keine Ordnung definiert, kann er nicht sortiert werden. Auch die binäre Suche erfordert Container mit einer impliziten Reihenfolge der Elemente. Nur Min- und Max-Methoden arbeiten auf allgemeinen Collection-Objekten. Nutzt die Collections-Klasse keine List-Objekte, arbeitet sie doch nur mit Collection-Objekten und nicht mit Iteratoren.

Alle Methoden sind statisch, sodass Collections eine Utility-Klasse wie Math ist. Ein Exemplar von Collections lässt sich nicht anlegen – der Konstruktor ist privat.

Beispiel

Fülle eine Liste mit Strings, sortiere die Strings, und suche nach einem String:

List<String> list = new ArrayList<String>();
Collections.addAll( list, "Doha,Berlin,Wesel".split( "," ) )
;
Collections.sort( list )
;
System.out.println( Collections.binarySearch( list, "Wesel" ) >= 0 ); // true


Rheinwerk Computing - Zum Seitenanfang

13.6.1 Die Bedeutung von Ordnung mit Comparator und ComparableZur nächsten ÜberschriftZur vorigen Überschrift

Die Ordnung der Elemente spielt bei Daten eine große Rolle. Um Elemente in einem TreeSet sortiert zu halten oder in einer Liste das größte Element zu finden, muss die Ordnung definiert sein.

Um Ordnung herzustellen, unterscheidet Java zwei Wege:

  • Elemente können eine natürliche Ordnung haben. Dann implementieren Klassen die Schnittstelle Comparable. Beispiele sind String, Date und Integer.
  • Ein externes Vergleichsobjekt, das die Schnittstelle Comparator implementiert, stellt fest, wie die Ordnung für zwei Elemente ist.

Um Such- oder Sortieroperationen möglichst unabhängig von Klassen zu machen, die eine natürliche Ordnung besitzen oder die eine Ordnung über einen externen Comparator definiert bekommen, haben Utility-Klassen wie java.util.Arrays oder java.util.Collections oft zwei Arten von Methoden: einmal mit einem zusätzlichen Comparator-Parameter und einmal ohne. Wird kein Comparator angegeben, so müssen die Objekte vom Typ Comparable sein.

class java.util.Arrays
  • static void sort(Object[] a)
    Sortiert die Elemente. Zum Vergleichen wird vorausgesetzt, dass sie die Klasse Comparable implementieren. Falls sie dies nicht tun, wird eine Ausnahme ausgelöst.
  • static <T> void sort(T[] a, Comparator<? super T> c)
    Vergleicht die Objekte mit einem externen Comparator. Falls die Objekte auch noch Comparable implementieren, wird diese Sortierordnung nicht genutzt.
  • static int binarySearch(Object[] a, Object key)
    Sucht binär nach key. Die Objekte im Feld müssen Comparable implementieren.
  • static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)
    Sucht im sortierten Feld. Der Comparator bestimmt das Sortierkriterium.
class java.util.Collections
  • static <T extends Comparable<? super T>> void sort(List<T> list)
  • static <T> void sort(List<T> list, Comparator<? super T> c)
  • static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)
  • static <T> int binarySearch(List<? extends T> list, T key,
    Comparator<? super T> c)

Die Datenstrukturen, die eine Sortierung verlangen, wie TreeSet oder TreeMap, nehmen entweder einen Comparator entgegen oder erwarten von den Elementen eine Implementierung von Comparable.


Rheinwerk Computing - Zum Seitenanfang

13.6.2 SortierenZur nächsten ÜberschriftZur vorigen Überschrift

Mit zwei statischen sort()-Methoden bietet die Utility-Klasse Collections die Möglichkeit, die Elemente einer Liste stabil zu sortieren.

class java.util.Collections
  • static <T extends Comparable<? super T>> void sort(List<T> list)
    Sortiert die Elemente der Liste gemäß ihrer natürlichen Ordnung, die ihnen die Implementierung über Comparable gibt.
  • static <T> void sort(List<T> list, Comparator<? super T> c)
    Sortiert die Elemente der Liste gemäß der Ordnung, die durch den Comparator c festgelegt wird. Eine mögliche natürliche Ordnung spielt keine Rolle.

Die Sortiermethode arbeitet nur mit List-Objekten. Bei den anderen Datenstrukturen wäre das ohnehin kaum sinnvoll, weil diese entweder unsortiert sind oder extern eine bestimmte Ordnung aufweisen, wie oben schon angemerkt wurde. Eine analoge Sortiermethode sort() für die Elemente von Arrays bietet die Klasse Arrays.

Beispielprogramm zum Sortieren

Das folgende Programm sortiert eine Reihe von Zeichenketten aufsteigend.

Listing 13.5: com/tutego/insel/util/CollectionsSortDemo.java, main()

List<String> list = Arrays.asList(
"Saskia", "Regina", "Angela", "Astrid", "Manuela", "Silke",
"Linda", "Daniela", "Silvia", "Samah", "Radhia", "Mejda", "Tanja"
);
Collections.sort( list );

System.out.println( list );

Die statische Methode Arrays.asList() baut aus einem String-Feld (getarnt als Vararg) eine Liste auf. Die Liste im Ergebnis ist veränderbar.

Strings sortieren, auch unabhängig von der Groß- und Kleinschreibung

Die Klasse String realisiert über die Implementierung von Comparable eine natürliche Sortierung. Alle String-Objekte, die in einem Feld sind, können problemlos über Array.sort() sortiert werden, und alle Strings in Collection-Sammlungen können über Collections.sort() sortiert werden.

Um unabhängig von der Groß- und Kleinschreibung zu sortieren, bietet die Klasse String eine praktische Konstante: String.CASE_INSENSITIVE_ORDER. Das ist ein Comparator<String>, der gut als Argument für sort() passt. Im Übrigen ist es die einzige statische Variable der Klasse.

Beispiel

Füge in ein TreeSet eine Liste von Strings ein, die sortiert unabhängig von der Groß-/Kleinschreibung gehalten werden.

<TreeSet<String> set = new TreeSet<String>( String.CASE_INSENSITIVE_ORDER );
Collections.addAll( set, "noah", "abraham", "Isaak", "Ismael",
"moses", "JESUS", "Muhammed" );
System.out.println( set ); // [abraham, Isaak, Ismael, JESUS, moses, Muhammed, noah]

Tipp

Für länderabhängige Vergleiche helfen spezielle Untertypen von Comparator: die Collator-Objekte.

List<String> list = Arrays.asList( "A", "b", "ä", "ß", "S", "s" );
Comparator<Object> collator = Collator.getInstance( Locale.GERMAN )
;
Collections.sort( list, collator );
System.out.println( list ); // [A, ä, b, s, S, ß]

Daten in umgekehrter Reihenfolge sortieren

Da es keine spezielle Methode reverseSort() gibt, ist hier ein spezielles Comparator-Objekt im Einsatz, um Daten entgegengesetzt zu ihrer natürlichen Reihenfolge zu sortieren. Mit der statischen Methode reverseOrder() der Klasse Collections können wir ein geeignetes Comparator-Exemplar anfordern.

Beispiel

Sortiere Zeichenfolgen absteigend:

List<String> list = new ArrayList<String>();
Collections.addAll( list, "Adam", "Eva", "Set", "Enosch", "Kenan", "Mahalalel" );
Comparator<String> comparator = Collections.reverseOrder()
;
Collections.sort( list, comparator );
System.out.println( list ); // [Set, Mahalalel, Kenan, Eva, Enosch, Adam]

Eine andere Möglichkeit für umgekehrt sortierte Listen besteht darin, erst die Liste mit Collections.sort() zu sortieren und anschließend mit Collections.reverse(List<?> list) umzudrehen. Das Umdrehen ist jedoch ein zusätzlicher Durchlauf, der mit dem reverseOrder()-Comparator vermieden wird. Zudem ist die Lösung mit einem Comparator über reverseOrder() stabil. Für einen existierenden Comparator liefert Collections.reverseOrder(Comparator<T> cmp) einen Comparator<T>, der genau umgekehrt arbeitet.


Rheinwerk Computing - Zum Seitenanfang

13.6.3 Den größten und kleinsten Wert einer Collection findenZur nächsten ÜberschriftZur vorigen Überschrift

Bisher kennen wir die überladenen statischen Methoden min() und max() der Utility-Klasse Math für numerische Datentypen. Es gibt aber auch statische Methoden min() und max() in Collections und Arrays, die das kleinste und größte Element einer Sammlung ermitteln. Die Laufzeit ist linear zur Größe der Sammlung. Die Methoden unterscheiden nicht, ob die Elemente der Datenstruktur schon sortiert sind oder nicht.

class java.util.Collections
  • static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll)
  • static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp)
  • static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)
  • static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp)

Wir sehen, dass es eine überladene Version der jeweiligen Methode gibt, da für beliebige Objekte eventuell ein Comparator-Objekt erforderlich ist, das den Vergleich vornimmt. Es sei auch bemerkt, dass dies mit die komplexesten Beispiele für Generics sind.

Aufbauen, Schütteln, Beschneiden, Größensuche

In unserem nächsten Beispiel geht es darum, dass zwei Spieler aus einem Kartenspiel mit 56 Karten je 10 zufällige Karten bekommen. Die Karten sind Java-enums. Derjenige mit der höchstwertigen Karte (ein Ass ist zum Beispiel mehr »wert« als eine Sieben) gewinnt, wobei auch beide gewinnen können, wenn sie die gleiche höchstwertige Karte haben. Auf die Anzahl der Karten kommt es nicht an.

Listing 13.6: com/tutego/insel/util/BestCard.java

package com.tutego.insel.util;

import java.util.*;

public class BestCard
{
enum Cards { ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT,
NINE, TEN, JACK, QUEEN, KING, ALAS }
public static void main( String[] args )
{
// Initialisiere Kartenspiel, beginne mit 14 Karten
List<Cards> cards = new ArrayList<Cards>( EnumSet.allOf( Cards.class ) );

// Verdopple zweimal die Karten auf insgesamt 56
cards.addAll( cards );
cards.addAll( cards );

// Vermische Karten
Collections.shuffle( cards );

// Der erste Spieler bekommt die ersten 10 Karten
List<Cards> player1 = new ArrayList<Cards>( cards.subList( 0, 10 ) );

// Der zweite Spieler bekommt die nächsten 10 Karten
List<Cards> player2 = new ArrayList<Cards>( cards.subList( 11, 20 ) );

// Größte Karte suchen, also die Karte mit der größten Ordinalzahl
System.out.printf( "Spieler 1: %s%nSpieler 2: %s%n", player1, player2 );
Cards bestCardPlayer1 = Collections.max( player1 );
Cards bestCardPlayer2 = Collections.max( player2 );
System.out.println( "Beste Karte Spieler 1: " + bestCardPlayer1 );
System.out.println( "Beste Karte Spieler 2: " + bestCardPlayer2 );

// Enums implementieren Comparable. Ausgeben, wer die beste Karte hat
int winner = bestCardPlayer1.compareTo( bestCardPlayer2 );
if ( winner > 0 )
System.out.println( "Spieler 1 gewinnt" );
else if ( winner < 0 )
System.out.println( "Spieler 2 gewinnt" );
else
System.out.println( "Beide Spieler gewinnen" );
}
}

Das Beispiel baut im ersten Schritt eine Liste mit Card-Objekten auf und schüttelt diese mit shuffle() durch. Dann ordnet subList() je zehn Karten dem ersten und dem zweiten Spieler zu. In dem Kontext wäre nicht unbedingt eine Kopie in eine neue ArrayList nötig gewesen, doch das ist bei einer Weiterführung des Beispiels vermutlich nützlicher, denn subList() ist eine Live-Ansicht, und wir könnten sonst keine Elemente aus der Unterliste löschen und hinzufügen, ohne dabei gleichzeitig die gesamten 56 Karten anzugreifen.

Aufzählungen sind Enum-Objekte, die Comparable implementieren und daher eine natürliche Ordnung haben. Aus diesem Grunde funktioniert max() überhaupt, was ein Ordnungskriterium zur Extremwertsuche benötigt. Aus den Karten der beiden Spieler ist so die größte Karte leicht ermittelt.

Implementierung der Extremwertmethoden bei Comparable-Objekten

Wenn wir ein String-Objekt in eine Liste packen oder ein Double-Objekt in eine Menge, werden sie korrekt gesucht, da insbesondere die Wrapper-Klassen die Schnittstelle Comparable implementieren.

An der Implementierung Collections.min() ohne extra Comparator lässt sich gut der Aufruf von compareTo() ablesen:

Listing 13.7: java/util/Collections.java, min()

public static <T extends Object & Comparable<? super T>>
T min( Collection<? extends T> coll )
{
Iterator<? extends T> i = coll.iterator();
T candidate = i.next();

while( i.hasNext() )
{
T next = i.next();
if ( next.compareTo(candidate) < 0 )
candidate = next;
}
return candidate;
}

Die generische Schreibweise verlangt, dass die Elemente in der Collection vom Typ Comparable sein müssen und somit eine compareTo()-Methode vorhanden ist.



Ihr Kommentar

Wie hat Ihnen das <openbook> gefallen? Wir freuen uns immer über Ihre freundlichen und kritischen Rückmeldungen.

>> Zum Feedback-Formular
<< zurück
  Zum Katalog
Zum Katalog: Java ist auch eine Insel





Java ist auch eine Insel
Jetzt bestellen


 Ihre Meinung?
Wie hat Ihnen das <openbook> gefallen?
Ihre Meinung

 Buchempfehlungen
Zum Katalog: Java ist auch eine Insel






 Java ist auch
 eine Insel


Zum Katalog: Java SE Bibliotheken






 Java SE Bibliotheken


Zum Katalog: Professionell entwickeln mit Java EE 7






 Professionell
 entwickeln mit
 Java EE 7


Zum Katalog: Einstieg in Eclipse






 Einstieg in
 Eclipse


Zum Katalog: Einstieg in Java






 Einstieg in
 Java


 Shopping
Versandkostenfrei bestellen in Deutschland und Österreich
InfoInfo




Copyright © Rheinwerk Verlag GmbH 2011
Für Ihren privaten Gebrauch dürfen Sie die Online-Version natürlich ausdrucken. Ansonsten unterliegt das <openbook> denselben Bestimmungen, wie die gebundene Ausgabe: Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Alle Rechte vorbehalten einschließlich der Vervielfältigung, Übersetzung, Mikroverfilmung sowie Einspeicherung und Verarbeitung in elektronischen Systemen.


[Rheinwerk Computing]

Rheinwerk Verlag GmbH, Rheinwerkallee 4, 53227 Bonn, Tel.: 0228.42150.0, Fax 0228.42150.77, service@rheinwerk-verlag.de