Algorithmen und Datenstrukturen 10 - CIP-Pool Informatiksu75heja/aud/ss2012/aud10.pdf · Besprechung Blatt 9 ADT Generics Datentypen Vorbereitung Blatt 10 1 Besprechung Blatt 9 Fragen

Besprechung Blatt 9 ADT Generics Datentypen Vorbereitung Blatt 10

Algorithmen und Datenstrukturen 10

Stefan Ploner

28. Juni 2012

Algorithmen und Datenstrukturen 10 Stefan Ploner


1 Besprechung Blatt 9Fragen

2 ADTAllgemeinBeispiele

3 GenericsMotivation & BeispielType ErasureWrapper-Klassen und (Un-)Boxing

4 DatentypenVerkettete Listen und BinarbaumeBinary Heaps

5 Vorbereitung Blatt 10Hinweise



Fragen

Fragen zu Blatt 9?



Allgemein

Schema eines ADTs

adt [Name]sorts [Verwendete Datentypen]ops[Methodensignaturen]axs[Axiome]end [Name]



Allgemein

Operationstypen

3 Operationstypen:

1 (Primar-)Konstruktoren (Operationen zum Erreichen jedesmoglichen Zustands, minimale Anzahl)

2 Hilfskonstruktoren (alles andere was den ADT zuruckgibt)

3 Projektionen (andere Ruckgabewerte)

ADT-Konstruktoren werden meist durch Java-Konstruktorenabgebildet. Java-Methoden sind auch moglich, diese mussen beiPrimarkonstruktoren static sein.



Allgemein

Primarkonstruktoren, Normalform

Primarkonstruktoren

• benotigen keine eigenen Axiome

• werden durch die Verwendung in den anderen Operationendefiniert

Normalform

• Objekt, das durch eine minimale Zahl vonPrimarkonstruktoren dargestellt ist.



Beispiele

Queue: T

Gesucht: ADT mit den Methoden

• create

• enqueue

• dequeue

• empty

• head

• tail

Beachte: Fur die Definition des ADTs ist es egal, ob man enqueueoder dequeue rekursiv definiert. Wir definieren dequeue rekursiv.



Beispiele

QUEUE: T

ops

create: -> QUEUE

enqueue: T x QUEUE -> QUEUE

dequeue: QUEUE -> QUEUE

empty: QUEUE -> BOOL

head: QUEUE -> T

axs

A1: empty(create()) = TRUE

A2: empty(enqueue(x, q)) = FALSE

A3: head(create()) = ERROR oder NULL

A4: head(enqueue(x, q)) = x falls empty(q) = TRUE

= head(q) sonst

A5: dequeue(create()) = ERROR oder NULL

A6: dequeue(enqueue(x, q)) = q falls empty(q) = TRUE

= enqueue(x, dequeue(q)) sonst



Beispiele

ADT auswerten (Queue : int)

tail(enqueue(head(enqueue(27, dequeue(enqueue(42, enqueue(13,create))))), enqueue(99, enqueue(5, create))))= tail(enqueue(

head(enqueue(27, dequeue(enqueue(42, enqueue(13, create))))),enqueue(99, enqueue(5, create))

))

Bei tail interessiert nur das zuletzt hinzugefugte Element!

= head(enqueue(27, dequeue(enqueue(42, enqueue(13, create)))))

Jetzt von innen nach außen auflosen:

= head(enqueue(27, dequeue(enqueue(42, [13]))))= head(enqueue(27, dequeue([13, 42])))= head(enqueue(27, [42])) = head([42, 27]) = 42



Beispiele

STACK: T

ops

create: -> STACK

push: T x STACK -> STACK

pop: STACK -> STACK

top: STACK -> T

empty: STACK -> BOOL

axs

A1: empty(create()) = TRUE

A2: empty(push(x, s)) = FALSE

A3: pop(create()) = ERROR oder NULL

A4: pop(push(x, s)) = s

A5: top(create()) = ERROR oder NULL

A6: top(push(x, s)) = x

A7: push(top(s), pop(s)) = s falls s != create()

push wird bereits ueber die anderen Axiome definiert



Motivation & Beispiel

Listenklassen in der Java APIProblemstellung: Man mochte einer Speicherstruktur dynamischDaten hinzufugen und entfernen.

Bisher: Manuelles Erstellen und Kopieren von ArraysBesser: Moglichkeiten der Java API nutzen

List v = new ArrayList();

v.add("foo"); // add "foo"

v.add("bar"); // add "bar"

v.set(5, "bla"); // IndexOutOfBoundsException

System.out.println(v.get(0)); // print "foo"

v.remove(0); // remove "foo"

System.out.println(v.get(0)); // print "bar"




Generische Listenklassen

Probleme einer ArrayList:

List v = new ArrayList();

v.add("foo");

Integer i = (Integer)v.get(0); // runtime error

Der selbe Code mit Generics:

List<String> v = new ArrayList<String>();

v.add("bar");

Integer i = v.get(0); // compiler error

Generics dienen der Ubersichtlichkeit, Fehlersuche undPerformance. Die Java API stellt komplett implementiertegenerische Datenstrukturen fur viele Anwendungsfalle bereit!




Zeit fur ein Beispiel!




public class Array<T> implements Comparable<Array<T>> {

private Object[] array;

public Array(int n) {

array = new Object[n];

}

@SuppressWarnings("unchecked")

public T get(int i) {

return (T)array[i]; // Cast von Object nach T

}

public void set(int i, T o) {

array[i] = o;

}

// vergleicht nur die Laengen, nicht die Elemente!

public int compareTo(Array<T> other) {

return array.length - other.array.length;

}

}Algorithmen und Datenstrukturen 10 Stefan Ploner


Type Erasure

Type Erasure

Generics werden in Java durch “Type Erasure” umgesetzt. Dabeipassiert beim Kompilieren im Prinzip folgendes:

• alle generischen Typen (z.B. T) werden durch den Basistyp(meist Object) ersetzt

• an allen Stellen, wo außerhalb der Klasse gen. Parametertypenverwendet werden, werden entsprechende Casts hinzugefugt

• die Casts werden dabei (also beim Kompilieren) gepruft,wodurch ClassCastExceptions zur Runtime verhindert werden



Type Erasure

Type Erasure

ArrayList<Integer> list = new ArrayList<Integer>();

list.add(5);

int value = list.get(5);

Nach Type Erasure:

ArrayList<Object> list = new ArrayList<Object>();

list.add((Integer)5);

int value = (Integer)list.get(5);

Nach dem Kompilieren wird trotz unterschiedlichen Typparameterndie selbe Klasse verwendet. Die Werte der Typparameter sind zurLaufzeit nicht mehr bekannt.



Type Erasure

Folgen von Type Erasure:

• statische Variablen und Methoden werden geteilt

• entsprechend konnen diese keine gen. Klassentypen enthalten

• die Bedingung “obj instanceof T” ist nicht moglich

• auf generischen Typen sind keine Konstruktor-Aufrufe und nurMethodenaufrufe des Basistyps moglich

Es konnen auch keine Arrays eines gen. Typs angelegt werden.Als Workarround kann man ein Object[]-Array verwenden, jedochmussen dann intern Casts nach T hinzugefugt werden. (→Beispiel)



Wrapper-Klassen und (Un-)Boxing

Wrapper-Klassen

• Generic Type Parameter erlauben nur Object und dessenUnterklassen als Argument

• ValueTypes erben nicht von Object (boolean, char, int, ...)

• stattdessen mussen sogenannte “Wrapper-Klassen” verwendetwerden (Boolean, Char, Integer, ...)

• dabei wird der ValueType in die Klasse eingepackt (“Boxing”)

class Integer {

int value;

// probably useful Methods

}



Wrapper-Klassen und (Un-)Boxing

Boxing und UnboxingVorsicht: Obwohl es sich um Klassen handelt, weisenWrapper-Klassen keine typische Referenzsemantik auf(Stichwort: Immutable Objects)

Ausfuhrliches Rechenbeispiel:

Integer a = new Integer(5), b;

b = a;

a += 5; // a = a + 5;

// a is now 10, b is still 5

Zeile 3:

1 a wird implizit nach int konvertiert (unboxing)

2 die Rechnung 5 + 5 wird ausgefuhrt

3 10 wird implizit nach Integer konvertiert, dabei wird eine neueInstanz erstellt (boxing)



Verkettete Listen und Binarbaume

Einfach verkettete Liste

Listenelemente bestehen aus

• Wert (Referenz oder Werttyp selbst)

• Referenz zum nachsten Element

Listenklasse besteht aus

• Referenz zum ersten Listenelement oder Sentinel

• Optional: Variable zum Mitzahlen der Elementanzahl beimHinzufugen / Entfernen (spart spateres nachzahlen)




Doppelt verkettete Liste

Listenelemente bestehen aus

• Wert (Referenz oder Werttyp selbst)

• Referenz zum nachsten Element

• Referenz zum vorherigen Element

Listenklasse besteht aus

• Referenz zum ersten Listenelement oder Sentinel

• Optional: Variable zum Mitzahlen der Elementanzahl beimHinzufugen / Entfernen (spart spateres nachzahlen)

• Optional, wenn die Liste keinen Ring bildet: Referenz zumletzten Listenelement (z.B. fur umgekehrte Iteratoren)




Binarbaume

Konnen entweder in einem Array (kompakter) oder mit Zeigern(variable Große) implementiert werden.

So konnte ein Element aussehen:

class BinBaumElement<T>

{

BinBaumElement left;

T value;

BinBaumElement right;

}

Oberklasse wie bei Listen, Kopfelement durch die Wurzel ersetzen.




Index des Kind- / Vaterelements in Binarbaumen

(wenn der Array ab Index 0 gefullt wird)

• linkes Kind: 2i + 1

• rechtes Kind: 2i + 2

• Vater: (i − 1)/2 (eigentlich die Formel fur das linke Kind, beimrechten ist das Ergebnis 0,5 zu viel. Aber: Integer-Division)



Binary Heaps

Binary Heaps

• Binarbaum

• Vaterelement immer kleiner / großer als beide Kinder

• immer balanciert (im Gegensatz zu Suchbaumen)

Mit Heaps konnen Vorrangwarteschlangen (priority-queues)effizient umgesetzt werden, da das Element mit der hochstenPrioritat schnell gefunden wird.



Binary Heaps

Einfugen in einen Max-Heap

• neues Element hinten an den Heap anhangen

• solange das Vaterelement kleiner ist, neues Element mit demVaterelement tauschen (Hochblubbern)

Achtung: Bevor man auf Vater- oder Kindelemente zugreift, mussman prufen, ob diese auch existieren!



Binary Heaps

Herausnehmen aus einem Max-Heap

• gewunschtes Element aus dem Heap nehmen

• hinterstes Element an die freie Stelle verschieben

• wenn das Vaterelement kleiner ist• solange das Vaterelement kleiner ist, tausche das Element mit

dem Vaterelement (Hochblubbern)

sonst• solange das großere Kindelement großer ist, tausche mit

diesem (Versickern)

Bemerkung: Die if-else-Bedingung dient nur der Ubersicht.Sie ist uberflussig, da sich die Schleifen gegenseitig ausschließen.

Beim fur einen Heap ublichen Entfernen des Wurzelelements kannnaturlich nur der Versickern-Fall eintreten.



Hinweise

10.1 Compiler-Warnungen bei Generics

Befehl zum Anzeigen der Warnungen:javac -Xlint:unchecked filename.java

Nicht alle Warnungen konnen behoben werden (v.a. bei Arrays:Generic Array-Creation, Cast eines Object-Arrayelements in denGeneric-Type).Andere sollten behoben werden (z.B. fehlende Typparameter).

Warnungen konnen per @SuppressWarnings(“unchecked”) vorVariablen-, Methoden- und Klassendeklarationen fur denentsprechenden Bereich unterdruckt werden. Der Bereich sollteimmer minimal gewahlt werden (nie auf die gesamte Klasse).



Hinweise

10.2 Stack vs. Stack auf Heap

• Rekursion aufmalen und die Variablenbelegungen undVeranderungen grob dazu skizzieren bewirkt wunder

• dabei bedenken, dass mit jedem Methodenaufruf neue lokaleVariablen angelegt werden



Hinweise

10.3a) Beispiel equals-Methode

public class Auto {

private String farbe; // never null

private int tueren = 5;

public boolean equals(Object o)

{

if (o == null) return false;

if (!(o instanceof Auto)) return false;

Auto a = (Auto)o;

return farbe.equals(a.farbe)

&& tueren == a.tueren;

}

}

Beim delegieren von equals-Aufrufen auf NullPointer aufpassen!



Hinweise

10.3b) Vergleiche mit dem Comparable Interface

• es gibt keine Vergleichsoperatoren fur Referenztypen

• das Comparable<T>-Interface definiert diecompareTo(T other)-Instanzmethode

• Ruckgabewert (this ist die aufrufende Instanz):• < 0: this ist “kleiner” als other• == 0: die Elemente sind gleich (entspricht equals)• > 0: this ist “großer” als other

• a.compareTo(b) >= 0 ist also im Prinzip a >= b⇒ Vergleichsoperator einfach zwischen die 2 Objekte schieben

Details in der API.



Hinweise

10.4 MergeQueue

• den Aufbau einer Liste klar vor Augen haben

• die Funktionalitat einer Liste kann direkt in denListenelementen integriert sein

• ADTs direkt ubernehmen, sind mehrere Definitionen gegeben,muss in der Methode zwischen den verschiedenen Fallenunterschieden werden


Documents

Algorithmen und Datenstrukturen 10 - CIP-Pool Informatiksu75heja/aud/ss2012/aud10.pdf · Besprechung Blatt 9 ADT Generics Datentypen Vorbereitung Blatt 10 1 Besprechung Blatt 9 Fragen