CS计算机代考程序代写 Java compiler Programmierung

Programmierung
Generics
Michael Goedicke
michael.goedicke@paluno.uni-due.de auf der Basis von Folien von V Gruhn

Listen, Bäume etc sind eigentlich allgemeine Strukturen
▪ Die unterschiedlichen bisher betrachteten Implementierungen einer Liste sahen entweder einen festen Typ vor (z.B. Dokument, Student etc) als Element oder allgemein Object vor. Mit Object als Element ist es ohne weiteres möglich, Listen von unterschiedlichen Typen aufzubauen:
LinkedList dokumente = new LinkedList(); dokumente.add(new Dokument()); dokumente.add(new Dokument()); dokumente.add(new String(“Hallo Welt”));
▪ Zur Erinnerung: Jede Klasse erbt automatisch von Object. ▪ Die Methode durchsuchen(…) würde zur Laufzeit(!) eine
ClassCastException werfen, sobald sie versucht, ein Objekt in
den Typ Dokument zu casten, das diesen Typ nicht hat.
▪ Ein Dilemma: Wir wollen dem Compiler den Typ der Elemente in der
Liste mitteilen und gleichzeitig die Implementierung der Liste nicht auf Elemente bestimmter Typen beschränken, damit wir sie immer wiederverwenden können.
M. Goedicke – Programmierung WiSe 2020/2021
2

Die verkette Liste: generische Strukturen sehen Platzhalter vor, die später gefüllt werden können
▪ Die Platzhalten müssen jedoch immer mit Elementen gleichen Typs versorgt werden!
M. Goedicke – Programmierung WiSe 2020/2021
3

Die generische verkettete Liste: wie kann erreicht
werden, dass der Platzhalter festgelegt werden
kann
▪ Seit Version 5 bietet Java eine komfortable Möglichkeit, einerseits wiederverwendbare und andererseits typensichere Datenstrukturen zu konstruieren: Generics.
▪ Wir erweitern unser Interface Liste dazu um einen formalen Typparameter, sozusagen ein Stellvertreter für den später wirklich verwendeten Typ. Dieser muss in der Deklaration des Interfaces bzw. der Klasse angegeben werden und steht in < >. Damit ersetzen wir alle Vorkommen von Object.
▪ Konvention ist, Typparameter als einfache Großbuchstaben anzugeben, hierT.
▪ Achtung: funktioniert auch für Interfaces!
public interface List {
public void add(T value);
public void add(int index, T value); public void clear();
public T get(int index);
public int indexOf(T value);
public boolean isEmpty();
public void remove(int index); public int size();
}
Typparameter T festgelegt in in der Deklaration unseres Interfaces.
Alle Vorkommen von Object werden gegen T ausgetauscht
M. Goedicke – Programmierung WiSe 2020/2021
4

Die generische verkettete Liste, die Grundstruktur
▪ Unsere Implementierungen von Node und LinkedList müssen entsprechend angepasst werden:
public class LinkedList implements List { private Node head;
…
}
public class Node { private T value; private Node next;
… }
Platzhalter
M. Goedicke – Programmierung WiSe 2020/2021
5

Die generische verkettete Liste
▪ Mit diesen Anpassungen können wir dem Compiler mitteilen, welchen Typ die Liste in unserer Klasse Ordner enthält:
public class Ordner {
private String beschriftung; private List dokumente; public Ordner(String beschriftung) {
this.beschriftung = beschriftung;
this.dokumente = new LinkedList(); }
}
Generics!
▪ Positiver Nebeneffekt: Der Code wird lesbarer, da sofort ersichtlich ist, was sich eigentlich in der Liste befindet / befinden darf.
▪ Anmerkung: Primitive Datentypen können hier nicht verwendet werden, ausschließlich Referenztypen. Folgende Anweisung ist also ungültig und führt zu einem Kompilierfehler:
private List zahlen; ▪ Jedoch geht: Integer statt int
M. Goedicke – Programmierung WiSe 2020/2021
6

Die generische verkettete Liste
▪ Auf den Typecast in der Methode durchsuchen() können wir nun verzichten, da der Compiler weiß, dass nur Objekte vom Typ
Dokument in der Liste sein können:
public Dokument durchsuchen(String titel) { for (Dokument dok: this.dokumente) {
if (dok.getTitel().equals(titel)) { return dokument;
} }
return null; }
▪ Zum Vergleich die alte Version, ohne Generics:
public Dokument durchsuchen(String titel) { for (Object object: dokumente) {
Dokument dokument = (Dokument) object; if (dokument.getTitel().equals(titel)) {
return dokument; }
}
return null; }
M. Goedicke – Programmierung WiSe 2020/2021
7

Die generische verkettete Liste
▪ Generics sind ein wesentlicher Bestandteil der Java Klassenbibliothek, viele der vordefinierten Klassen und Interfaces machen davon starken Gebrauch.
▪ Zwei Beispiele sind die Interfaces Comparable und Comparator, die wir beim Sortieren von Objekten kennengelernt haben:
public class OrdnerComparator implements Comparator {
@Override
public int compare(Ordner o1, Ordner o2) { // TODO Ordner vergleichen…
return result;
} }
M. Goedicke – Programmierung WiSe 2020/2021
8

Die generische verkettete Liste: Spezifikation von geforderten Typ-Parameter-Eigenschaften
▪ Häufig werden Eigenschaften für die Typ-Parameter gefordert.
▪ Zwei Beispiele sind die Interfaces Comparable und Comparator, …
werden für das Suchen und Sortieren benötigt :
public class List > {
…
T current = head…
…
current.compareTo(…)
}
M. Goedicke – Programmierung WiSe 2020/2021
9

Eine (kleine) Anzahl von Möglichkeiten und
Einschränkungen für generische Klassen gibt es in
Java
▪ Wildcard upperbound: class Structure {…}
> Mögliche aktuelle Parameter müssen Unterklassen von SomeClassOrInterface sein
▪ Wildcard lowerbound: class Structure {…}
> Mögliche aktuelle Parameter müssen Oberklassen von SomeClassOrInterface sein.
▪ Eine Reihe von Einschränkungen gelten:
▪ Siehe http://docs.oracle.com/javase/tutorial/java/generics/restrictions.html ▪ Primitive Typen (int,…) können nicht als Typen fungieren stattdessen
(Integer,…)
▪ Keine Arrays von Parameter-Typen
M. Goedicke – Programmierung WiSe 2020/2021
10

Die verkettete Liste: Klassenbibliothek
▪ Die Java Runtime Environment (JRE) enthält eine Klassenbibliothek, die viele Klassen und Interfaces bereitstellt:
▪ Die Programmierbibliothek enthält Klassen für die Entwicklung von Benutzeroberflächen, Datenbank- und Netzwerkverbindungen, verteilten Anwendungen, usw.
▪ Im Paket java.util befinden sich u. a. dynamische Datenstrukturen. ▪ Insbesondere stellt die Klassenbibliothek eine (doppelt) verkettete Liste
bereit.
M. Goedicke – Programmierung WiSe 2020/2021
11

Die verkettete Liste: Klassenbibliothek
‹‹interface››
Iterable
im Paket java.lang
‹‹interface››
Collection
‹‹interface››
Queue
‹‹interface››
List
‹‹interface››
Deque
AbstractList
AbstractSequentialList
ArrayList
Vector
LinkedList
doppelt verkettete Liste
M. Goedicke – Programmierung WiSe 2020/2021
12

Die verkettete Liste: Klassenbibliothek
▪ Wenn eine Klasse das Iterable-Interface implementiert, dann können die Instanzen dieser Klassen in einer foreach-Schleife verwendet werden und wir verstehen nun, wie das Iterable-Interface typsicher eingesetzt werden kann.
List liste = new LinkedList();
for (int i = 0; i < 10; i++) { liste.add(i); } for (Integer i : liste) { Jeder primitive Datentyp hat in Java auch einen entsprechenden Referenztypen – für int ist dies die Klasse Integer. Die Umwandlung kann automatisch erfolgen, dies nennt man Autoboxing. } System.out.println(i); List liste = new LinkedList(); for (int i = 0; i < 10; i++) { liste.add(i); } Iterator iterator = liste.iterator(); while (iterator.hasNext()){ System.out.println(iterator.next()); } ‹‹interface›› Iterable iterator():Iterator ‹‹interface›› Iterator hasNext():boolean next():Object remove():void M. Goedicke – Programmierung WiSe 2020/2021 13 Die verkettete Liste: Klassenbibliothek ▪ Das Collection-Interface definiert die Grundfunktionalität der meisten Datenstrukturen im Paket java.util. ▪ Das List-Interface definiert die speziellen Eigenschaften einer Liste. Ein anderer Datentyp ist z.B. java.util.Set. Darstellung für Generics in UML ‹‹interface›› Collection E +add(E):boolean +addAll(Collection):boolean +clear():void +contains(Object):boolean +containsAll(Collection):boolean +isEmpty():boolean +remove(Object):boolean +removeAll(Collection) +size():int ... ‹‹interface›› List E +add(E):boolean +add(int, E):boolean +get(int):E +indexOf(Object):int +remove(Object):boolean +set(int, E):E ... M. Goedicke – Programmierung WiSe 2020/2021 14 Die verkettete Liste: Klassenbibliothek ▪ Das Queue-Interface und das Deque-Interface definieren Eigenschaften einer Queue (s. später), die als Sonderfall einer verketteten Liste betrachtet werden kann. ▪ Die Klassen AbstractList und AbstractSequentialList implementieren v.a. solche Methoden, die einen Spezialfall einer anderen Methode darstellen. ▪ Beispielsweise wird die Methode add(Object) durch einen Aufruf von add(size(), Object) implementiert. ArrayList E +ArrayList() +ArrayList(int) ... ▪ Die Klasse ArrayList implementiert das List-Interface mit Hilfe eines Arrays. Wenn man den Konstruktor ArrayList(int) verwendet, dann kann man die initiale Größe des Arrays festlegen (die sich mit der Zeit aber ändern kann). M. Goedicke – Programmierung WiSe 2020/2021 15 Die verkettete Liste: Klassenbibliothek ▪ Die Klasse LinkedList realisiert das List-Interface durch eine doppelt verkettete Liste. ▪ Die beiden Listentypen unterscheiden sich in zentralen Aspekten: • Der Zugriff auf die Elemente ist bei einer ArrayList schneller als bei einer LinkedList . • Dagegen sind Einfüge- und Löschoperationen bei einer ArrayList aufwendiger als bei einer LinkedList. 3 6 1 2 3 4 5 1 2 M. Goedicke – Programmierung WiSe 2020/2021 16 Die verkettete Liste: Klassenbibliothek ▪ Wenn man die Klassen des Pakets java.util verwenden möchte, dann muss man sie importieren: import java.util.List; import java.util.LinkedList; public class Test { ... } import java.util.*; public class Test { ... } ▪ Die Klasse java.util.Collections enthält Klassenmethoden, die zusätzliche Operationen auf Listen realisieren: binäre Suche, Sortieren, Bestimmung von Minimum und Maximum, usw. ▪ Die meisten Operationen setzen allerdings voraus, dass die Elemente der Liste das Comparable-Interface implementieren. M. Goedicke – Programmierung WiSe 2020/2021 17 Die verkettete Liste: Klassenbibliothek main()-Methode List liste = new LinkedList(); for (int i = 10; i > 0; i–) {
liste.add(i);
}
for (Integer i : liste) { System.out.print(′′[′′ + i + ′′]->′′);
}
System.out.println(); Collections.sort(liste); for (Integer i : liste) {
System.out.print(′′[′′ + i + ′′]->′′); }
Die Wrapper-Klasse Integer des primitiven Datentyps int implementiert das Comparable-Interface.
Konsole
[10]->[9]->[8]->[7]->[6]->[5]->[4]->[3]->[2]->[1]-> [1]->[2]->[3]->[4]->[5]->[6]->[7]->[8]->[9]->[10]->
M. Goedicke – Programmierung WiSe 2020/2021
18

Die verkettete Liste: Klassenbibliothek
▪ Wenn man eine Liste mit Hilfe einer Schleife durchläuft, dann führen Einfüge- und Löschoperationen im Schleifenrumpf manchmal zu unerwarteten Ergebnissen:
main()-Methode
List liste = new ArrayList(); for (int i = 1; i <= 10; i++) { liste.add(i); } for (int i = 0; i < liste.size(); i++) { System.out.print(′′[′′ + liste.get(i) + ′′]->′′); liste.remove(0);
}
Konsole
[1]->[3]->[5]->[7]->[9]->
M. Goedicke – Programmierung WiSe 2020/2021
19

Die verkettete Liste: Klassenbibliothek
List liste = new ArrayList(); for (int i = 0; i <= liste.size(); i++) { liste.add(i); } Endlosschleife ▪ Wenn man eine Liste mit Hilfe eines Iterators durchläuft, dann führen Änderungen an der Liste zu einem Laufzeitfehler – allerdings nicht zu einem Kompilierfehler! List liste = new ArrayList(); liste.add(1);
for (Integer i: liste) {
liste.add(1);
}
Laufzeitfehler: ConcurrentModificationException
M. Goedicke – Programmierung WiSe 2020/2021
20

Map
▪ Das Interface Map dient zur Speicherung von Schlüssel-Wert- Paaren. Hierbei werden eindeutig Schlüsselobjekte vom Typ K (key) auf Wertobjekte vom Typ V (value) abgebildet.
▪ Das Interface bietet unter anderem Operationen zum Einfügen, Auslesen und Löschen von Schlüssel-Wert-Paaren.
▪ Die Schlüsselobjekte müssen eindeutig sein. Duplikate von Schlüsselobjekten sind nicht erlaubt.
▪ Das Interface ist in dem Paket java.util.Map enthalten. Es gibt mehrere Implementierungen des Interfaces. Neben anderen sind diese:
▪ HashMap (java.util.HashMap) ▪ TreeMap (java.util.TreeMap)
M. Goedicke – Programmierung WiSe 2020/2021
21

Map
▪ HashMap
▪ BieteteinenschnellenZugriffaufdieObjekteanhandeines
Hashwertes
▪ Die Klasse der Schlüsselobjekte sollte die Methoden hashCode() und equals(), welche von Objekt geerbt werden, sinnvoll überschreiben.
▪ Es gibt keine Garantie über die Reihenfolge in welcher die Schlüssel-Werte Paare in der HashMap abgelegt werden. Diese kann sich während der Laufzeit ändern.
M. Goedicke – Programmierung WiSe 2020/2021
22

Map
▪ TreeMap
▪ DerZugriffaufdieSchlüssel-WertPaareistlangsameralsbei
der HashMap.
▪ Bietet aber eine eindeutige Sortierung der Schlüsselwerte.
▪ Die Schlüsselobjekte müssen entweder das Interface Comparable implementieren oder der TreeMap muss ein Comparator übergeben werden.
M. Goedicke – Programmierung WiSe 2020/2021
23

Map – Hashwert
▪ Die Hashfunktion muss einen int-Wert zurückgeben. Viele Java- Klassen enthalten bereits eine eigene Hashfuktion z.B. String.
▪ Für eigene Klassen sollte die Methode hashCode() überschrieben werden. In der Regel wird der Hashwert als Funktion über die Klassenattribute gebildet. Dies kann zum Beispiel mit der Methode: Objects.hash(Object … values) erreicht werden.
M. Goedicke – Programmierung WiSe 2020/2021
24

Map – Auszug von Methoden der Map
▪ V put (K key, V value)
▪ Fügt value in Map unter Schlüssel key ein
▪ Gibt den Wert des unter key gespeicherten Objektes zurück
▪ V remove (Object key)
▪ Entfernt Objekt, das unter key abgelegt ist
▪ Gibt den Wert zum gelöschten Schlüssel zurück
▪ V get(Object key)
▪ Gibt Wert-Objekt zum dazugehörigen key zurück
▪ int size()
▪ Anzahl der Schlüssel-Wert-Paare in Map
▪ Set keySet()
▪ Gibt Menge aller Schlüssel zurück (Schlüssel einzigartig, daher
Set)
▪ Collection values()
▪ Gibt Menge aller Werte zurück (inkl. Duplikate, daher Collection statt Set)
M. Goedicke – Programmierung WiSe 2020/2021
25

Map – Auszug von Methoden der Map
M. Goedicke – Programmierung WiSe 2020/2021
26