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

Inhaltsverzeichnis
Vorwort
1 Java ist auch eine Sprache
2 Sprachbeschreibung
3 Klassen und Objekte
4 Der Umgang mit Zeichenketten
5 Mathematisches
6 Eigene Klassen schreiben
7 Angewandte Objektorientierung
8 Exceptions
9 Generics, innere Klassen
10 Die Klassenbibliothek
11 Threads und nebenläufige Programmierung
12 Datenstrukturen und Algorithmen
13 Raum und Zeit
14 Dateien und Datenströme
15 Die eXtensible Markup Language (XML)
16 Grafische Oberflächen mit Swing
17 Grafikprogrammierung
18 Netzwerkprogrammierung
19 Verteilte Programmierung mit RMI und Web–Services
20 JavaServer Pages und Servlets
21 Applets
22 Midlets und die Java ME
23 Datenbankmanagement mit JDBC
24 Reflection und Annotationen
25 Logging und Monitoring
26 Sicherheitskonzepte
27 Java Native Interface (JNI)
28 Dienstprogramme für die Java-Umgebung
Stichwort

Download:
- ZIP, ca. 14,1 MB
Buch bestellen
Ihre Meinung?

Spacer
<< zurück
Java ist auch eine Insel (8. Auflage) von Christian Ullenboom
Programmieren mit der Java Standard Edition Version 6
Buch: Java ist auch eine Insel (8. Auflage)

Java ist auch eine Insel (8. Aufl.)
8., aktual. Auflage, geb., mit DVD
1.475 S., 49,90 Euro
Galileo Computing
ISBN 978-3-8362-1371-4
Pfeil 12 Datenstrukturen und Algorithmen
Pfeil 12.1 Datenstrukturen und die Collection-API
Pfeil 12.1.1 Designprinzip mit Schnittstellen, abstrakten und konkreten Klassen
Pfeil 12.1.2 Die Basis-Schnittstellen Collection und Map
Pfeil 12.1.3 Das erste Programm mit Container-Klassen
Pfeil 12.1.4 Die Schnittstelle Collection
Pfeil 12.1.5 Schnittstellen, die Collection erweitern, und Map
Pfeil 12.1.6 Konkrete Container-Klassen
Pfeil 12.1.7 Welche Klasse nehmen?
Pfeil 12.1.8 Generische Datentypen in der Collection-API
Pfeil 12.1.9 Die Schnittstelle Iterable und das erweiterte for
Pfeil 12.2 Mit einem Iterator durch die Daten wandern
Pfeil 12.2.1 Die Schnittstellen Enumeration und Iterator
Pfeil 12.2.2 Iteratoren von Sammlungen und das erweiterte for
Pfeil 12.2.3 Fail-Fast Iterator und die ConcurrentModificationException
Pfeil 12.3 Listen
Pfeil 12.3.1 Auswahlkriterium ArrayList oder LinkedList
Pfeil 12.3.2 Die Schnittstelle List
Pfeil 12.3.3 ArrayList
Pfeil 12.3.4 LinkedList
Pfeil 12.3.5 Der Feld-Adapter Arrays.asList()
Pfeil 12.3.6 toArray() von Collection verstehen – die Gefahr einer Falle erkennen
Pfeil 12.3.7 Primitive Elemente in den Collection-Datenstrukturen
Pfeil 12.4 Vergleichen von Objekten
Pfeil 12.4.1 Die Schnittstellen Comparator und Comparable
Pfeil 12.4.2 Algorithmen mit Such- und Sortiermöglichkeiten
Pfeil 12.4.3 Den größten und kleinsten Wert einer Collection finden
Pfeil 12.4.4 Sortieren
Pfeil 12.5 Mengen (Sets)
Pfeil 12.5.1 HashSet
Pfeil 12.5.2 TreeSet – die Menge durch Bäume
Pfeil 12.5.3 LinkedHashSet
Pfeil 12.6 Stack (Kellerspeicher, Stapel)
Pfeil 12.6.1 Die Methoden von Stack
Pfeil 12.6.2 Ein Stack ist ein Vector – aha!
Pfeil 12.7 Queues (Schlangen) und Deques
Pfeil 12.7.1 Die Schnittstelle Queue
Pfeil 12.7.2 Blockierende Queues und Prioritätswarteschlangen
Pfeil 12.7.3 Deque-Klassen
Pfeil 12.8 Assoziative Speicher
Pfeil 12.8.1 Die Klassen HashMap und TreeMap
Pfeil 12.8.2 Einfügen und Abfragen der Datenstruktur
Pfeil 12.8.3 equals(), hashCode() und IdentityHashMap
Pfeil 12.8.4 Das Problem von veränderbaren Elementen
Pfeil 12.8.5 Aufzählungen und Sichten auf den Assoziativspeicher
Pfeil 12.8.6 Der Gleichheitstest, Hash-Wert und Klon einer Hash-Tabelle
Pfeil 12.8.7 Die Arbeitsweise einer Hash-Tabelle
Pfeil 12.8.8 Multi-Maps
Pfeil 12.9 Die Properties-Klasse
Pfeil 12.9.1 Properties setzen und lesen
Pfeil 12.9.2 Properties verketten
Pfeil 12.9.3 Eigenschaften ausgeben
Pfeil 12.9.4 Hierarchische Eigenschaften
Pfeil 12.9.5 Properties speichern
Pfeil 12.9.6 Klassenbeziehungen: Properties und Hashtable
Pfeil 12.10 Algorithmen in Collections
Pfeil 12.10.1 Ersetzen, Kopieren, Füllen, Umdrehen, Rotieren, Durchmischen
Pfeil 12.10.2 Mit der Halbierungssuche nach Elementen fahnden
Pfeil 12.10.3 Nicht-änderbare Datenstrukturen
Pfeil 12.10.4 Häufigkeit eines Elements
Pfeil 12.10.5 nCopies()
Pfeil 12.10.6 Singletons
Pfeil 12.11 Synchronisation der Datenstrukturen
Pfeil 12.11.1 Lock-free-Algorithmen aus java.util.concurrent
Pfeil 12.11.2 Wrapper zur Synchronisation
Pfeil 12.11.3 CopyOnWriteArrayList und CopyOnWriteArraySet
Pfeil 12.12 Die Klasse BitSet für Bitmengen
Pfeil 12.12.1 Ein BitSet anlegen, füllen und erfragen
Pfeil 12.12.2 Mengenorientierte Operationen
Pfeil 12.12.3 Methodenübersicht
Pfeil 12.12.4 Primzahlen in einem BitSet verwalten


Galileo Computing - Zum Seitenanfang

12.10 Algorithmen in Collections Zur nächsten ÜberschriftZur vorigen Ü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 Funktionen 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 Funktionen, 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;
  • Wrapper um existierende Datenstrukturen zu legen.

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-Funktionen arbeiten auf allgemeinen Collection-Objekten. Nutzt die Collections-Klasse keine List-Objekte, arbeitet sie doch nur mit Collection-Objekten und nicht mit Iteratoren.

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


Beispiel Elemente gehen geordnet in eine Liste hinein und kommen durchgeschüttelt wieder heraus. Das wahllose Vertauschen der Elemente übernimmt Collections.shuffle(). Da shuffle() allgemein auf List-Objekten arbeitet, können wir hier LinkedList-, Vector- und ArrayList-Objekte einsetzen.

Listing 12.27 com/tutego/insel/util/Shuffle.java, main()

List<String> v = new ArrayList<String>(); 
Collections.addAll( v, "Bube", "Dame", "König", "Ass" ); 
Collections.shuffle( v ); 
System.out.println( v );  // z.B. [König, Ass, Bube, Dame]


Galileo Computing - Zum Seitenanfang

12.10.1 Ersetzen, Kopieren, Füllen, Umdrehen, Rotieren, Durchmischen Zur nächsten ÜberschriftZur vorigen Überschrift

Mit replaceAll(List<T> list, T oldVal, T newVal) werden die Elemente einer Liste gesucht und durch einen neuen Wert ersetzt. Die Funktion copy(List<? super T> dest, List<? extends T> src) kopiert alle Elemente von src in die Liste dest und überschreibt dabei solche, die eventuell schon an den entsprechenden Positionen der Zielliste liegen. Die Zielliste muss mindestens so lang wie die Quellliste sein, andernfalls wird eine IndexOutOfBoundsException ausgelöst. Hat das Ziel weitere Elemente, ist das egal, weil copy() diese nicht antastet.

Die Funktion fill(List<? super T> list, T obj) belegt eine Liste in linearer Zeit mit lauter identischen Elementen. Das heißt aber, dass es immer das gleiche Objekt ist, das an allen Positionen sitzt. Es ist die Frage, ob dies immer so sinnvoll und nützlich ist. Die Funktion reverse(List<?> list) dreht die Reihenfolge der Elemente in einer Liste um. Die Laufzeit ist linear zur Anzahl der Elemente. Und rotate(List<?> list, int distance) bewegt die Elemente um distance Positionen.


Beispiel Die Monate sollen um zwei Positionen nach rechts und wieder zurück geschoben werden.

Listing 12.28 com/tutego/insel/util/RotateTheList.java, main()

List<String> list = new ArrayList<String>( 
  Arrays.asList( new DateFormatSymbols().getShortMonths() ) ); 
System.out.println( list );  // [Jan, Feb, Mrz, Apr, Mai, Jun, Jul, Aug, Sep,  
                             // Okt, Nov, Dez, ] 
Collections.rotate( list, 2 ); 
System.out.println( list );  // [Dez, , Jan, Feb, Mrz, Apr, Mai, Jun, Jul, Aug,  
                             // Sep, Okt, Nov] 
Collections.rotate( list, –2 ); 
System.out.println( list );  // [Jan, Feb, Mrz, Apr, Mai, Jun, Jul, Aug, Sep,  
                             // Okt, Nov, Dez, ]


class java.util.Collections


  • static <T> void copy( List<? super T> dest, List<? extends T> src )
    Kopiert alle Elemente von src nach dest. Ist dest zu klein, gibt es eine IndexOutOfBoundsException. Ist die Zielliste größer als die Quellliste, lässt copy() die letzten Elemente von dest unangetastet.
  • static <T> void fill( List<? super T> list, T obj )
    Füllt die Liste list mit dem Element obj. Vorhandene Elemente werden mit obj überschrieben.
  • static boolean replaceAll( List<T> list, T oldVal, T newVal )
    Sucht nach dem Auftreten von oldVal über equals() in der Liste und ersetzt die gefundenen Elemente durch newVal. Die Größe der Liste ändert das nicht. Die Rückgabe ist true, wenn mindestens ein Element ersetzt wurde.
  • static void reverse( List<?> list )
    Kehrt die Reihenfolge der Elemente in der Liste um.
  • static void rotate( List<?> list, int distance )
    Bewegt die Elemente der Liste um distance Positionen.
  • static void shuffle( List<?> list )
    Würfelt die Elemente der Liste durcheinander. Dafür wird ein Standard-Generator für Zufallszahlen verwendet.
  • static void shuffle( List<?> list, Random rnd )
    Würfelt die Elemente der Liste durcheinander und benutzt dafür den Random-Generator rnd.

Galileo Computing - Zum Seitenanfang

12.10.2 Mit der Halbierungssuche nach Elementen fahnden Zur nächsten ÜberschriftZur vorigen Überschrift

Die Collection-Klassen enthalten mit contains(Object) eine Methode, die entweder true oder false zurückgibt, wenn ein Element gefunden wurde oder nicht. Die Position eines Elements in einer List liefert die Objektfunktion indexOf(Object). Ist die Liste sortiert, lässt sich eine Suche schneller durch das Halbierungsverfahren durchführen, was Java durch die Funktion binarySearch() in den Klassen Arrays und Collections bietet.

Der Halbierungssuche (auch binäre Suche, engl. binary search) liegt eine einfache Idee zugrunde: Wir beginnen die Suche nach einem Objekt in der Mitte der Liste. Ist das gesuchte Objekt kleiner als das mittlere Listenelement, dann muss es sich links von der Mitte befinden, andernfalls rechts. Die Liste wird also in zwei gleich große Abschnitte unterteilt, von denen nur einer weiter durchsucht werden muss. Diesen Vorgang wiederholen wir so oft, bis das Element gefunden wurde. Auf diese Weise ist die Suche sehr schnell und benötigt höchstens log(n) Listenhalbierungen bei einer Liste mit n Elementen. Es ist jedoch gut möglich, dass das gesuchte Element in der Liste nicht vorkommt. Dieser Fall wird erkannt, wenn durch das wiederholte Halbieren der Liste ein Listenabschnitt mit nur einem Element entstanden ist. Stimmt dieses eine Element nicht mit dem gesuchten Objekt überein, ist das Ergebnis der Suche ein »Nicht gefunden«. Die Suche nach einem nicht vorhandenen Element ist geringfügig aufwändiger als eine erfolgreiche Suche, benötigt aber ebenfalls nur logarithmisch viele Halbierungsschritte. Enthält die Liste mehrere gleiche Elemente, dann ist nicht gesichert, welches davon bei der Suche gefunden wird. Besteht die Liste etwa aus zehn Zahlen mit dem Wert 22, dann liefert der Algorithmus das fünfte Element.

Die statische Methode binarySearch() nimmt ein Feld oder eine Liste als Argument und liefert folgende Rückgabe:

  • Ist das Element in der Liste, so liefert binarySearch() die Position des Objekts.
  • Gibt es ein Element mehrmals in der Liste, wird irgendein Index zurückgegeben.
  • Wurde kein passendes Element gefunden, ist das Ergebnis eine negative Zahl und beschreibt recht trickreich die Stelle, an der der Algorithmus den letzten Vergleich durchgeführt hat.
  • Ist die Liste nicht sortiert, kann die Halbierungssuche nicht richtig funktionieren, da sie möglicherweise in die falsche Richtung läuft und das Element sich in der anderen Hälfte der unterteilten Liste befindet. Eine nicht sortierte Liste lässt sich mit sort() sortieren. Es ist aber immer noch schneller, in einer unsortierten Liste zu suchen – Laufzeit O(n) –, als erst die Liste zu sortieren – Laufzeit O(n log(n)) – und darin mit der Halbierungssuche zu suchen – Laufzeit O(log(n)). Wenn ausreichend viele Suchvorgänge nacheinander in der gleichen Liste durchzuführen sind, lohnt sich das vorherige Sortieren der Liste natürlich.

Ist das gesuchte Element nicht in der Liste, so ist der Rückgabewert (–Einfügepunkt –1), und der Einfügepunkt ist die Position in der Liste, an die der Wert gemäß Sortierung eingesetzt werden kann. Wir können folgende Programmzeilen verwenden, um einen nicht gefundenen Wert gleich passend einzufügen:

int pos = Collections.binarySearch( l, key ); 
if ( pos < 0 ) 
  l.add( -pos – 1, key );

Von binarySearch() gibt es zwei Varianten: Die erste Funktion nimmt an, dass die Werte in ihrer natürlichen Form sortiert sind. Die zweite arbeitet wieder mit einem Comparator-Objekt zusammen.


class java.util.Collections


  • static <T extends Object & Comparable<? super T>> int binarySearch( List<? extends T> list, T key ) Sucht ein Element in der Liste. Gibt die Position zurück oder einen Wert kleiner 0, falls kein passendes Element in der Liste ist.
  • static <T> int binarySearch( List<? extends T> list, T key, Comparator<? super T> c ) Sucht ein Element mit Hilfe des Comparator-Objekts in der Liste. Gibt die Position oder einen Wert kleiner 0 zurück, falls kein passendes Element in der Liste ist.

Galileo Computing - Zum Seitenanfang

12.10.3 Nicht-änderbare Datenstrukturen Zur nächsten ÜberschriftZur vorigen Überschrift

Diverse Collections.unmodifiableXXX()-Funktionen legen eine Hülle um eine Datenstruktur und lassen nur die Lese-Methoden zum Container durch, blockieren aber Modifizierungsbefehle wie add() durch eine UnsupportedOperationException.


Galileo Computing - Zum Seitenanfang

12.10.4 Häufigkeit eines Elements Zur nächsten ÜberschriftZur vorigen Überschrift

Collections.frequency(Collection<?>, Object) gibt die Anzahl der Elemente zurück, die zu einem Suchobjekt equals()-gleich sind.


Beispiel Ermittle die Anzahl der »:-)«-Smilies:

String s = "Hallo :-) Suppi :-)"; 
int i = Collections.frequency( Arrays.asList(s.split("\\s")), ":-)" ); 
System.out.println( i );    // 2


class java.util.Collections


  • static int frequency( Collection<?> c, Object o )
    Liefert die Anzahl der Elemente, die mit o gleich sind. Genauer gesagt muss für alle Elemente e aus der Collection c gelten: o == null ? e == null : o.equals(e). Ist c null, folgt eine NullPointerException.

Galileo Computing - Zum Seitenanfang

12.10.5 nCopies() Zur nächsten ÜberschriftZur vorigen Überschrift

Die statische Funktion nCopies() erzeugt eine Liste mit der gewünschten Anzahl von Elementen aus einem Objekt.


class java.util.Collections


  • static <T> List<T> nCopies( int n, T o )
    Erzeugt eine unveränderbare Liste mit n Elementen von o.

Die Liste besteht nicht aus einer Anzahl Kopien des Elements (mit clone()), sondern aus einer Liste, die ein Element immer wiederholt. Daher sind auch nur Leseoperationen wie get() oder contains() erlaubt, doch keine Veränderungen. Infolgedessen ist der Einsatzbereich der Liste beschränkt, jener der Funktion aber nicht. Denn die Elemente der Liste können als Ausgang für eine modifizierbare Datenstruktur gelten, der sich eine Liste übergeben lässt. Das gilt zum Beispiel für eine ArrayList, die im Konstruktor eine andere Liste akzeptiert, der sie die Werte entnimmt.


Beispiel Initialisiere eine Liste mit 10 Leerstrings, und hänge an eine Liste zwei Zeichenketten mit ».« an:

List<String> list = new ArrayList<String>( Collections.nCopies(10, "") ); 
list.addAll( Collections.nCopies(2, ".") ); 
System.out.println( list );   // [, , , , , , , , , , ., .]

Ein Collections.nCopies(1, value) entspricht einem Singleton, für das Java aber eine eigene Funktion bereithält.


Galileo Computing - Zum Seitenanfang

12.10.6 Singletons topZur vorigen Überschrift

Singletons sind Objekte, die genau ein Exemplar realisieren. Die Klasse Collections bietet drei Funktionen, die ein gegebenes Element in eine immutable Menge, Liste oder einen Assoziativspeicher setzt:


class java.util.Collections


  • static <T> Set<T> singleton( T o )
  • static <T> List<T> singletonList( T o )
  • static <K,V> Map<K,V> singletonMap( K key, V value )

Auf den ersten Blick erscheinen die Funktionen ziemlich unnütz. Sie sind jedoch immer dann nützlich, wenn Methoden vorhanden sind, die zwar Sammlungen annehmen – auch wenn sie nur aus einem Element bestehen –, aber mit einzelnen Elementen nicht viel anfangen können.

Löschen von Elementen in einer Sammlung

Die Collection-Klassen bieten bisher keine Lösung zum Löschen aller Vorkommen eines Elements. Zwar gibt es die Collection-Methode remove(Object), doch löscht diese nur das erste Vorkommen. Um alle Vorkommen zu löschen, ist entweder eine Schleife zu schreiben oder singleton() zu nutzen. Uns hilft beim Löschen aller Elemente die Methode removeAll(Collection), doch erwartet sie als Argument eine Collection, die wir ja gerade durch singleton() bekommen, da ein Set eine Erweiterung von Collection ist. Auf diese Weise entfernt unsere Funktion removeAll(Collection c, Object o) jedes Vorkommen eines Objekts aus der Datenstruktur.

Listing 12.29 com/tutego/insel/util/SingletonDemo.java, removeAll()

public static void removeAll( Collection<?> c, Object o ) 
{ 
  c.removeAll( Collections.singleton(o) ); 
}


Ihr Kommentar

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






<< 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

 Tipp
Zum Katalog: Coding for Fun





 Coding for Fun


 Buchempfehlungen
Zum Katalog: Objektorientierte Programmierung





 Objektorientierte
 Programmierung


Zum Katalog: Einstieg in Eclipse 3.4






 Einstieg in
 Eclipse 3.4


Zum Katalog: Java 6 lernen mit Eclipse






 Java 6 lernen
 mit Eclipse


Zum Katalog: NetBeans Platform 6






 NetBeans
 Platform 6


Zum Katalog: Java und XML






 Java und XML


Zum Katalog: Visual C# 2008






 Visual C# 2008


Zum Katalog: IT-Handbuch für Fachinformatiker






 IT-Handbuch für
 Fachinformatiker


Zum Katalog: C++ von A bis Z






 C++ von A bis Z


 Shopping
Versandkostenfrei bestellen in Deutschland und Österreich
InfoInfo




Copyright © Galileo Press 2009
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.


[Galileo Computing]

Galileo Press, Rheinwerkallee 4, 53227 Bonn, Tel.: 0228.42150.0, Fax 0228.42150.77, info@galileo-press.de