Embed Size (px)
Citation preview
(1)
Zweites Semester Wirtschaftsinformatik
SS 2018
DHBW Mosbach
Prof. Dr. Herbert Neuendorf
Übungen zur Programmierung II
Alle Lösungen werden gezeigt und am selben Ort wie die Skripte zur Verfügung gestellt
(11)
Spezielle Klassen und Methoden
String-Operationen
Hüllklassen
Clonen
(12)
Hüllklassen, Strings, java.util.Arrays etc.
1. Schreiben Sie ein Programm, das beim Aufruf drei Kommandozeilenparameter übergeben bekommt – und zwar :
Eine reelle Zahl, einen Operator (entweder + oder - ) und eine weitere reelle Zahl.
Das Programm soll die beiden Zahlen je nach Operator addieren oder subtrahieren und das Ergebnis ausgeben.
Gehen Sie davon aus, dass der User immer genau drei sinnvolle Strings in args übergibt.
Tipp: Verwenden Sie Methoden der Hüllklasse Double und der Klasse String .
2#. Schreiben Sie ein Programm, das einen Text von der Tastatur einliest (oder hart enthält).
Der Text soll unter Berücksichtigung typischer Satzzeichen in seine einzelnen Wörter zerlegt werden.
Alle Wörter (nicht die Satzzeichen) sollen in Kleinschreibweise in ein Array übernommen werden.
Lassen Sie das Array sortieren und ausgeben.
Tipp: Verwenden (importieren) Sie die Klasse java.util.StringTokenizer und die Klasse java.util.Arrays .
3. Schreiben Sie ein Programm, das die Wirkung der Bitoperatoren (& | ^ ~) auf int-Werte darstellt.
Der User gibt zwei int-Werte a und b ein. Deren Bitmuster soll auf der Konsole ausgegeben werden.
Ferner sollen die Bitmuster der Operationen a&b, a|b, a^b, ~a und ~b ausgegeben werden.
Tipp: Verwenden Sie die Hüllklasse Integer mit ihrer statischen Methode toBinaryString( ) .
Übung 1:
(13)
Verwenden von Hüllklassen : java.math.BigInteger
Schreiben Sie eine Klasse BigBruch zum Addieren und Subtrahieren mit rationalen
Brüchen. Verwenden Sie intern bei Rechnungen nur die auf den BigInteger-Objekten
zur Verfügung stehenden Rechenmethoden. Kürzen ist nicht gefordert.
Testen Sie mit einigen Objekten :
class BigBruch {
private BigInteger zaehler ;
private BigInteger nenner ;
public BigBruch( int z, int n ){ } // alternativ: public BigBruch( String z, String n )
public BigBruch( BigInteger z, BigInteger n ) { }
public BigBruch add( BigBruch b ) { }
public BigBruch negate( ){ }
public BigBruch subtract( BigBruch b ){ }
public String toString( ) { }
}
Übung 2 :
(15)
Pakete
Nutzen der Klassen bestehender Pakete
(16)
Verwenden der Klassen eines Pakets:
Schreiben Sie ein Programm, das feststellt, ob ein vorgegebenes Jahr ein Schaltjahr ist !
Eingabe: Jahreszahl.
Ausgabe: Ob es sich um ein Schaltjahr handelt oder nicht
Verwenden Sie die JDK-Klasse GregorianCalendar :
a) Nutzen Sie die JDK-Doku, um herauszufinden, zu welchem Paket diese Klasse gehört
b) Die JDK-Doku informiert über die Methoden dieser Klasse :
Suchen Sie nach einer Methode zur Schaltjahrberechnung!
(… der englische Begriff für "Schaltjahr" ist "Leap Year" … )
Verwenden Sie diese Klasse und die geeignete Methode.
Dazu müssen Sie die Klasse GregorianCalendar importieren.
Übung 4 :
(17)
Referenzieren + Verwenden eines Pakets :
Verwenden Sie aus den JMathTools das Paket JMathPlot
Liegt als Datei jmathplot.jar vor : http://code.google.com/p/jmathplot/
Im Netz finden sich Anwendungsbeispiele.
Durch Referenzieren im Projekt (Add External Jars …) wird Paketstruktur sichtbar.
Für einfache Plots reicht : import org.math.plot.* ; import javax.swing.* ;
1. Lassen Sie eine 2d-Funktion plotten - definiert durch x- und y-Werte in zwei double[ ]-Arrays.
2. Lassen Sie die 3d-Funktion : z = sin(π⋅x)*cos(π⋅y) plotten, zB im Bereich [0;2] für x und y.
Hierfür müssen die korrespondierenden x,y,z-Werte in drei double[ ]-Arrays vorliegen.
Um das Plot zu visualisieren, muss es als Panel einem Frame hinzugefügt werden – z.B. :
Plot2DPanel plot = new Plot2DPanel( ); // bzw: Plot3DPanel plot = new Plot3DPanel( );
plot.addLinePlot( "MyPlot", x, y ); // bzw: plot.addGridPlot( "sin*cos", x, y, z );
JFrame frame = new JFrame( "Verlauf" );
frame.setSize( 600, 600 );
frame.setContentPane( plot );
frame.setVisible( true );
Weitere Bestandteile :
JMathIO JMathArray
Übung 5#:
(18)
Exceptions
Werfen + Fangen
Schreiben von Exceptions
(19)
Exceptions
a) Abfangen von Ausnahmen :
Im folgenden Programm werden - getriggert durch eine Zufallszahl - verschiedene
Ausnahmen ausgelöst.
Erweitern Sie das Coding, so dass diese Ausnahmen einzeln abgefangen und die
exception message am Bildschirm ausgegeben wird – Methode getMessage( ).
class ExceptionTest {
public static void main( String[] args ) {
int rd = (int)(Math.random() * 2);
if (rd == 0) rd = 7/0 ; // ArithmeticException
if (rd == 1) new String( "Hallo" ).charAt(13) ; // StringIndexOutOfBoundsException
if (rd == 2) new Integer( "Hallo" ) ; // NumberFormatException
}
}
Übung 6 :
(20)
Exceptions
b) Abfangen von Ausnahmen :
Schreiben Sie eine Methode public static void throwEx( ) .
In ihr werden ganzzahlige Zufallszahlen z zwischen 0 und 2 mit Math.random() ermittelt.
Wenn z==0 dann soll eine RuntimeException geworfen werden.
Wenn z==1 dann soll eine Exception geworfen werden.
Wenn z==2 dann terminiert die Methode normal.
Rufen Sie die Methode in main() auf.
Fangen Sie alle Ausnahmen in richtiger Reihenfolge ab.
Lassen Sie die Rückgabe von getMessage( ) des Fehlerobjekts ausgeben.
Fügen Sie auch einen finally -Block hinzu.
Verifizieren Sie (durch Ausgabe auf Konsole), dass dieser immer durchlaufen wird.
Übung 6 :
(21)
Exceptions
c) Auslösen und Abfangen von Ausnahmen :
Erstellen Sie eine Klasse Bruch mit int-Attributen für Zähler und Nenner
Geben Sie der Klasse einen Konstruktor mit Parametern für Zähler und Nenner,
der eine IllegalArgumentException auslöst, wenn versucht wird, einen Bruch mit
Nenner gleich 0 anzulegen.
Testen Sie das Verhalten dieser Klasse.
Welchen Wert hat eine Bruch-Referenz, wenn eine Ausnahme ausgelöst wird ?
Übung 6 :
(22)
Exceptions
d) Kontrollierte Ausnahmen :
Erstellen Sie die Klassen AEx und BEx , die beide direkt von Exception erben, sowie ein Testprogramm mit den folgenden Methoden :
public static void throwAE( ) throws AEx { throw new AEx( ) ; }
public static void throwBE( ) throws BEx { throw new BEx( ) ; }
public static void callAB( ) throws AEx, BEx { throwAE( ); throwBE( ) ; }
Was passiert, wenn man bei der ersten Methode die Deklaration throws AEx durch throws Exception ersetzt ?
Wie verhält sich der Compiler, wenn man in throwBE( ) keine Ausnahme auslöst, den Zusatz throws BEx im Methodenkopf aber beibehält ?
Erklären Sie die Logik, mit der der Compiler solche kontrollierten Ausnahmen hinsichtlich throws–Deklaration überprüft …
Übung 6 :
(23)
Exceptions
e) Performance :
Messen Sie die Zeit (mit System.currentTimeMillis() ) für den häufigen Aufruf der folgenden beiden
Methodenvarianten – z.B. jeweilige Zeit für eine Million Aufrufe :
public static boolean test1( Object x ) {
return x instanceof Integer ;
}
public static boolean test2( Object x ) {
try{ Integer i = (Integer) x ; return true ; }
catch( Exception e ){ return false ; }
}
Experimentieren Sie dazu mit :
1.) Funktionierenden Aufrufen, die keine Exceptions erzeugen und true zurück liefern :
Integer iObj = new Integer( 5 ) ; test1( iObj ) ; test2( iObj ) ;
2.) Aufrufen, die eine Exceptions erzeugen bzw. false zurück liefern :
Double dObj = new Double( 2.5 ) ; test1( dObj ) ; test2( dObj ) ;
Was können Sie feststellen über den internen Aufwand der Laufzeitumgebung bezüglich der beiden
Methoden test1( ) und test2( ) in den beiden Fällen ?
Übung 6 :
(24)
Reflection
Nutzung Class-Objekt
(25)
Klassendeskriptor
Schreiben Sie (analog Bsp. 2a im Skript) ein Programm, dem der User einen vollen Klassennamen als
String s übergibt - d.h. inklusive Paketangabe - z.B. javax.swing.JButton .
Erzeugen Sie für diese Eingabe ein Class-Objekt : Class cs = Class.forName( s ) ;
1. Welche gecheckten Exceptions müssten Sie behandeln ?
2. Lassen Sie mittels des Class-Objekts alle Oberklassen-Namen der fraglichen Klasse ausgeben.
3. Erzeugen Sie mittels cs.newInstance( ) ein Objekt der fraglichen Klasse und lassen Sie sich
dafür den Inhalt von toString( ) ausgeben.
Übung 7 :
class ClassInfo {
public static void main( String[] args ) {
String s = IO.promptAndReadString( "Klassenname: " ) ;
Class cs = Class.forName( s ) ;
// …
Object o = cs.newInstance( ) ;
// …
}
}
(26)
Nutzung von Reflection
Schreiben Sie einen "typsicheren"
adaptiven Datenbehälter, bei dem der erste
übergebene Typ bestimmt, welche weiteren
Objekte typmäßig noch zugelassen sind.
Dazu wird in put() bei der ersten
Datenübergabe (wenn size noch 0 ist) der
Typ des übergebenen Objekts mittels
o.getClass() in der Class-Variablen c
festgehalten.
Bei allen folgenden Datenübergaben wird der
Klassentyp von c mit dem Klassentyp des
neuen Datenelements verglichen.
Falls diese sich unterscheiden wird das
Datenelement nicht übernommen und false
zurück geliefert.
Falls die Klassentypen identisch sind wird
das neue Datenelement in das Array
abgelegt, size hochgezählt und true zurück
geliefert.
Übung 8
class GenericFake {
private Object[ ] arr ;
private int size = 0 ;
private Class c ;
public GenericFake( int s ){ arr = new Object[ s ] ; }
public boolean put( Object o ) {
// … implementieren !
}
public static void main( String[] args ) {
GenericFake g = new GenericFake( 10 ) ;
boolean check ;
check = g.put( "hallo" ) ; // gibt Typ String vor !
check = g.put( new Integer(1) ) ; // abgewiesen
check = g.put( "alle" ) ; // akzeptiert
check = g.put( new java.util.Date() ) ; // abgewiesen
}
}
(27)
Generics
Typregeln und Kompatibilitäten
Schreiben generischer Klassen
(28)
Generics – Generische Klasse
Verwenden Sie folgendes Code-Fragment
und ergänzen Sie die Klasse Familie …
… so dass eine Familie mit drei internen
Objekten namens vater, mutter, kind
erzeugt werden kann …
… wobei vater, mutter, kind vom
beliebigen, aber selben Typ sind.
Instanziieren Sie ein Familie-Objekt so,
dass das Coding in main lauffähig ist.
Erzeugen Sie ein zweites Familie-Objekt,
dessen interne Objekte von einem ganz
anderen Typ sind – z.B. Integer.
Übung 9
class Familie<T> {
private T vater ;
private T … ;
…
public Familie( … ) {
…
}
public void setKind( … ) {
…
}
public static void main( String[ ] args ) {
Familie<…> f1 = new Familie<…>( "Vater", "Mutter" ) ;
f1.setKind( "Kind" ) ;
}
}
(29)
1. Binäre Kompatibilität
Zeigen Sie, dass die Class-Objekte, die zu verschiedenen Type-Invocations
(Typbelegungen) einer generischen Klasse TestKlasse<T> gehören, nicht nur äquivalent,
sondern auch identisch sind.
2. Generisches Erzeugen von Arrays - fragliche Workarounds :
Die folgende generische Methode kompiliert !
Warum funktioniert die generische Erzeugung von Arrays leider doch nicht so einfach ?
Tipp : Methode ausprobieren …
Übung 10
public static <E> E[ ] test1( int size ) {
Object[ ] arr = new Object[ size ] ;
return (E[ ]) arr ;
}
(30)
Generics - Zuweisungskompatibilität
Verwenden Sie die generische Klasse TierKaefig<E> und die angegebenen Klassenhierarchie.
Testen und erklären Sie, ob damit die folgenden Zuweisungsvarianten … :
Variante 1:
TierKaefig<Tier> kaefig = new TierKaefig<Katze>( ) ;
Variante 2:
TierKaefig<Hund> kaefig = new TierKaefig<Tier>( ) ;
Variante 3:
TierKaefig<?> kaefig = new TierKaefig<Katze>( ) ;
kaefig.setInsasse( new Katze( ) ) ;
Variante 4:
TierKaefig kaefig = new TierKaefig( ) ;
kaefig.setInsasse( new Hund( ) ) ;
…
� nicht compilierbar sind,
� mit einer Typ-Warnung compilierbar sind,
� einen Laufzeitfehler erzeugen oder
� ohne Probleme lauffähig sind.
Übung 11:
class TierKaefig<E> {
private E insasse ;
public void setInsasse( E x ) {
insasse = x ;
}
public E getInsasse( ) {
return insasse ;
}
}
class Tier { }
class Katze extends Tier { }
class Hund extends Tier { }
(34)
Algorithmen & Datenstrukturen
Suchen & Sortieren
(35)
Eigenschaften von Algorithmen - Terminierung nicht selbstverständlich
Stellen Sie (durch Überlegung oder Ausprobieren) fest, ob bzw. für welche Zahlen x der
folgende "Algorithmus" / die Funktion f terminiert :
public int f( int x ){
while( x > 0 ){
if( x%5 == 0 ) x = x + 6;
else x = x - 3;
}
return x;
}
Betrachten Sie Werte x im Bereich [0 , 20] .
Übung 12 :
(36)
Zeitvergleich - Lineare Suche vs. Binary Search bei sortiertem Array
Testen Sie Suchverfahren mit der Klasse SortierteReihe :
Diese soll der im Skript enthaltenen Klasse entsprechen - wobei die Methode insert
übergebene Daten vom Typ int einfach nacheinander im Array ablegt. Übergeben Sie dazu
beim Aufruf von insert die Daten in bereits sortierter Reihenfolge - z.B. Vielfache von 3.
Ferner die Methoden int linSearch( int key ) und int binSearch( int key ) .
Erzeugen Sie eine Instanz von SortierteReihe und füllen Sie deren Array mit der
gewünschten Zahl schon sortierter Elemente.
Lassen Sie das Array nach einer vorhandenen Zahl durchsuchen.
Verwenden Sie beide Such-Methoden und stoppen Sie die jeweils erforderlichen Zeit
mittels System.currentTimeMillis( ) . ( Evtl. genauer : System.nanoTime( ) )
Vergleichen Sie die benötigten Zeiten.
Anmerkung: Um messbare Zeiten zu erhalten, muss man ziemlich viele Datenelemente
durchsuchen lassen. Selbst dann ist der Unterschied (im Gegensatz zu Sortiervorgängen)
nicht beeindruckend.
Übung 13:
(37)
Zeitvergleich - Verschiedene Sortierverfahren auf Arrays :
Klasse Reihung :
Diese soll der im Skript enthaltenen Klasse entsprechen, wobei die Methode insert
übergebene Daten vom Typ int einfach nacheinander im Array ablegt.
Ferner sollen die Methoden selectionSort bubbleSort quickSort enthalten sein, deren
Coding dem Skript entnommen werden kann - Parametrisierung anpassen.
Ferner eine Methode aSort, die intern die Methode java.util.Arrays.sort verwendet.
Die Methoden sollen auf einem Integer-Array s arbeiten.
Fragen Sie den User nach der Zahl der Elemente des zu sortierenden Arrays.
Erzeugen Sie eine Instanz von Reihung und füllen Sie ein Array mit der gewünschten Zahl von
int-Zufallszahlen :
Verwenden Sie dazu die Klasse java.util.Random und geben Sie einen festen Initialwert
(seed) beim Konstruktoraufruf vor, um bei jedem Programmlauf die selben Zufallszahlen zu
erhalten.
Übung 14 :
(38)
Zeitvergleich - Sortierverfahren auf Arrays :
Rufen Sie die verschiedenen Sortierverfahren auf und
lassen Sie das Array s sortieren.
Stoppen Sie die jeweils zum Sortieren erforderliche
Zeit.
Vergleichen Sie die benötigten Zeiten der verschiedenen
Verfahren und testen Sie, wie sich die Zeiten mit der
Datenmenge entwickeln.
Verwenden Sie zum Zeitstoppen die Methode
System.currentTimeMillis( )
Protokollieren Sie Ihre Ergebnisse von Hand, indem Sie
die Zeit t [ms] in Abhängigkeit von der Datenmenge n
notieren und auftragen t(n) .
(Kleine Tabelle bzw. Freihand-Plot)
Übung 14 :
class Reihung {
private int[] s;
private int counter = 0 ;
public Reihung( int size ) {
s = new int[size] ;
}
public void insert( int x ) {
s[counter] = x;
counter++;
}
public void bubbleSort( ) {
for ( int i=0 ; i <s.length-1 ; i++ ) {
for ( int j=0 ; j<s.length-1 ; j++ ) {
if( s[ j ] > s[ j+1 ] ) {
swap( s, j, j+1 ) ;
} } } }
// … weitere Sortiermethoden …
}
n
t Gute Frage von Prof. Deck : Begründen Sie, warum in der Klasse
java.util.Arrays für das Sortieren eines int-Arrays der etwas schnellere
QuickSort verwendet wird - für das Sortieren eines Object-Arrays dagegen
der langsamere MergeSort ?
(39)
Sortier- und Suchverfahren auf ObjektArrays
Schreiben Sie die Klasse :
Mitarbeiter implements Comparable<Mitarbeiter>
mit Attributen int id und String name. Schlüssel für
Mitarbeiter-Objekte sei die id.
Die Klasse habe entsprechende Methoden Konstruktor,
equals, hashCode, toString, compareTo.
Schreiben Sie die Klasse ObjektReihung, deren Array s
von Typ Mitarbeiter ist.
Geben Sie der Klasse ObjektReihung die Methoden
bubbleSort und binSearch, durch deren Aufruf das
interne Array s behandelt wird.
Übung 15:
class ObjektReihung {
private Mitarbeitzer[ ] s;
private int counter = 0 ;
public ObjektReihung( int size ) {
s = new int[size] ;
}
public void insert( Mitarbeiter x ) {
s[counter] = x;
counter++;
}
public Mitarbeiter get( int m ) {
return s[m];
}
// …
}
Testen Sie die Implementierung, indem Sie eine ObjektReihung-Instanz erzeugen und der
Methode insert in unsortierter Reihenfolge Mitarbeiter-Objekte übergeben.
Lassen Sie das interne Array s sortieren, den Inhalt des sortierten Arrays auf der
Konsole ausgeben - und dann nach einem Mitarbeiter mit einer eingegebenen id suchen.
(40)
Sortier- und Suchverfahren auf ObjektArrays
Anmerkungen :
Nicht besetzte Plätze (null-Werte) im Array sind (bei binärer Suche und Sortieren) ein
Problem. Besetzen Sie deshalb alle Plätze des Arrays s mit Mitarbeiter-Objekten.
(Auch java.util.Arrays.sort wirft eine Exception, wenn es auf ein Objekt-Array mit null-Werten angewandt wird …)
Um Mitarbeiter mit zufällig verteilten id zu erhalten, können Sie sich von der Klasse
java.util.Random zufällig verteilte int-Werte aus dem Bereich [0, max] geben lassen :
Random rd = new Random( ) ; int id = rd.nextInt( max ) ; // bzw.:
Mitarbeiter m = new Mitarbeiter( rd.nextInt(max), "N.N" ) ;
Übung 15:
(41)
Sortier- und Suchverfahren auf ObjektArrays
Gehen Sie vor wie in Aufgabe 16 - aber lassen Sie mit null besetzte Plätze zu
Schreiben Sie die Methoden :
bubbleSortNull
Diese soll null-Werte als größer als jedes belegte Datenelement ansehen. Auf diese Weise
stehen nach dem Sortieren alle null-Werte am Ende des sortierten Array.
binSearchNull
Diese soll davon ausgehen, dass alle null-Werte am Ende stehen.
Der Index high soll auf den Index der höchsten mit einem Objekt belegten Array-Position
gesetzt werden. Damit kann der sonst unveränderte Code der binären Suche arbeiten.
Testen Sie mit einem Array, in dem null-Werte vorkommen - z.B. so belegt :
int size = IO.promptAndReadInt("Anzahl = ") ; ObjektReihungNull r = new ObjektReihungNull( size ) ;
Random rd = new Random() ;
for( int i=0; i<size; i=i+3 ){ // Hinterlässt Plätze mit null-Werten
Mitarbeiter m = new Mitarbeiter( rd.nextInt(1000), "N.N" ) ; r.insert(m) ;
}
Übung #:
(42)
Algorithmen & Datenstrukturen
Stack & Queue
Verkettete Listen
(43)
Arraybasierte Stacks / Queues :
1.) Verwenden Sie das Coding für einen Stack :
Erstellen Sie eine Stack-Klasse mit Methoden push() und pop().
Auf dem Stack sollen int-Werte abgelegt werden.
Instanziieren Sie ein Objekt der Stack-Klasse und rufen Sie deren Methoden auf.
Beachten Sie die Reihenfolge, in der die Daten mittels pop( ) vom Stack geholt werden.
Versuchen Sie, mehr Elemente als möglich auf den Stack zu legen bzw. abzuholen
⇒ Fälle overflow + underflow
2.) Verwenden Sie das Coding für eine Queue:
Erstellen Sie eine Queue-Klasse mit den Methoden put() und get().
In der Queue sollen int-Werte abgelegt werden.
Instanziieren Sie ein Objekt der Queue-Klasse und rufen Sie deren Methoden auf.
Beachten Sie die Reihenfolge, in der die Daten mittels get( ) aus der Queue geholt werden.
Versuchen Sie, mehr Elemente als möglich in die Queue zu stellen bzw. abzuholen
⇒ Fälle overflow + underflow
Übung 16 :
(44)
"Dynamischer" (adaptiver) Stack :
Entwickeln Sie eine adaptive Klasse BetterStack.
Diese Klasse soll einen "quasi-dynamischen Stack" mittels Array für int-Werte darstellen:
In der Methode push( ) soll nun der overflow-Fall vom Benutzer verborgen bleiben :
Es soll in diesem Fall ein doppelt so großes Array neu angelegt werden und der Inhalt des bisherigen Arrays hineinkopiert werden - mittels System.arraycopy .
Die Arrayvariable muss am Ende der Operation auf das neue Array zeigen …
In der Methode pop( ) soll geprüft werden, ob das bisherige Array nur noch halb gefüllt ist.
In diesem Fall soll ein nur noch halb so großes Array neu angelegt werden und der Inhalt des bisherigen Arrays hineinkopiert werden.
Die Arrayvariable muss am Ende der Operation auf das neue Array zeigen …
Der Stack wird mit fester Standardgröße angelegt – oder man kann dies dem Konstruktor vorgeben.
Testen Sie ein Objekt der Klasse. Überprüfen Sie, ob Vergrößerungs- und Verkleinerungsvorgang korrekt arbeiten, ohne dass Sie Daten verlieren !
Übung 17 :
(45)
Verkettete Liste :
1.) Erstellen Sie drei Klassen :
a) Die nichtausführbaren Klasse Node und List :
Diese sollen den im Skript enthaltenen Klassen entsprechen, durch die eine unsortierte
verkettete Liste dargestellt wurde - unter Verwaltung von head und tail :
Es sollen int-Werte gespeichert werden.
Fügen Sie zur Klasse List die Methoden add( ) und contains( ) hinzu (Skript!)
b) Die ausführbare Klasse UList :
Erzeugen Sie in main( ) ein List-Objekt.
Stellen Sie ganzzahlige Zufallszahlen zwischen 0 und 100 in die Liste.
Verwenden Sie die Klasse java.util.Random und deren Methode nextInt( int max ) .
2.) Erweitern Sie die Klasse List um folgende public Methoden : …
Übung 18 :
(46)2.) Verkettete Liste :
String toString( )
Methode soll gesamten aktuellen Inhalt der Liste als String zusammenstellen.
int get( int pos )
Gibt Element an pos zurück - wirft RuntimeException, wenn pos nicht existent.
int indexOf( int data )
Liefert Position des Elements mit Wert data - wirft RuntimeException, wenn data nicht existent.
boolean remove( int n )
Methode soll den n-ten Knoten aus der Liste entfernen - liefert false, wenn dieser nicht existiert.
boolean remove( )
Methode soll den letzten Knoten aus der Liste entfernen - liefert false, wenn Liste leer ist.
int sum( )
Methode soll die Summe der Werte zurückliefern, die in der Liste gespeichert sind.
int size( )
Methode soll die Anzahl der Werte zurückliefern, die in der Liste gespeichert sind.
double mean( )
Methode soll den Mittelwert der gespeicherten Zahlen zurückliefern.
void clear( ) :
Methode soll die Liste leeren.
List reverse( ) : // #
Methode soll eine invertierte Liste zurückliefern, die die Daten in umgekehrter Folge enthält.
Übung 18 :
(47)
p = p.next
Node r = new Node(p.val)
r.next = res.head
45
head
3r
Erzeugen invertierte Liste - Lösung
class LinkedList {
private Node head ;
private Node tail ;
// ...
public LinkedList reverse( ) {
LinkedList res = new LinkedList( ) ;
Node p = head ;
while( p != null ) {
Node r = new Node( p.val ) ;
if( res.tail == null ) res.tail = r ;
r.next = res.head ;
res.head = r ;
p = p.next ;
}
return res ; }
}
Zuerst wird neue leere Liste res erzeugt. An diese werden neue Listknoten vorne eingefügt. Wert der neuen Listelemente ist Wert der alten Listelemente.
Reihenfolge umgekehrt, da jeder neue Knoten auf den aktuellen head zeigt und dann selbst zum head wird.
r.next = res.head // null
res.head = r 45
r
head
p = head
45 3 12
List res = new List( )
Node r = new Node( p.val )
45r
headInitialzustand res
1
2
34 res.head = r
45
head
3r
(48)
Mächtigere Klasse Node – andere Formulierung von LinkedList :
Verwenden Sie in der Klasse Node einen interessanteren Konstruktor :
Machen Sie sich klar, dass man dann addFirst( ) wie folgt formulieren kann :
Schreiben Sie eine neue Klasse LinkedList2 mit den Methoden :
� boolean addFirst( Object obj )
� Object get( int pos ) // wirft für sinnlosen Wert von pos eine IndexOutOfBoundsException
� int size( ) // Anzahl der gespeicherten Elemente
Testen Sie Ihre neu implementierte Listenklasse - z.B. mit Integer-Objekten !
Übung 19 :class Node {
public Object val ; public Node next ;
public Node( Object data, Node next ) {
this.val=data ; this.next=next ;
}
public boolean addFirst( Object obj ) {
head = new Node( obj, head ) ;
return true ;
}
Verwalten Sie nur die head-Referenz,
verzichten Sie auf die tail-Referenz
(50)
Stack als verkettete Liste + Erweiterungen:
1.) Realisieren Sie in einer nichtausführbaren Klasse Stack (sowie einer zugehörigen
Knotenklasse Node) einen Stack für int-Werte in Form einer verketteten Liste.
Entnehmen Sie das Coding für die Methoden push( ) und pop( ) dem Skript.
2.) Erzeugen Sie in main() der ausführbaren Klasse StackTest eine Instanz von Stack.
Legen Sie Daten auf den Stack mittels push() und entnehmen Sie Daten mittels pop().
Verfolgen Sie die Entwicklung des Stack-Objekts im Debugger!
Wenn Ihr Stack funktioniert, setzen Sie die Übung mit den umseitigen Erweiterungen fort …
Übung 20 :
(51)Stack als verkettete Liste – Erweiterungen :
3.) Erweitern Sie Ihre Klasse Stack um folgende public Methoden + testen Sie diese :
a) void clear ( ) : Der gesamte Stack soll "auf einen Schlag" geleert werden.
b) boolean isEmpty( ) : Wenn Stack leer, soll true zurückgeben, andernfalls false.
c) int size( ) : Liefert Anzahl der Elemente, die auf dem Stack liegen
d) int peekTop( ) :
Die Methode soll den Wert des obersten Datenelements zurückliefern, ohne dieses
vom Stack zu enfernen. Bei leerem Stack soll eine RuntimeException geworfen werden.
e) int peek( int pos ) :
Die Methode soll den Wert des Elements an der Stelle pos zurückliefern. Die Element-
zählung soll von oben nach unten (bei 1 beginnend) erfolgen: Das oberste Element auf
dem Stack habe die Position 1, das darunter die Position 2, usw. Wenn eine nicht
vorhandenen Position vorgegeben wird, soll eine RuntimeException geworfen werden.
f) boolean contains( int x ) :
Die Methode soll den Stack nach einem Wert x durchsuchen.
g) int[ ] toArray( ) :
Gibt ein Array zurück, das die Elemente des Stacks enthält (evtl. von Länge 0).
Übung 20 :
(55)
Interfaces java.util.Iterator und java.lang.Iterable
Die Dateniteration wird durch ein Iterator-Objekt geleistet mit den Methoden :
boolean hasNext( ) ; Object next( ) ; remove( ) ;
Das Interface Iterable hat nur eine Methode : Iterator iterator( ) ;
Schreiben Sie eine Klasse Standorte. Dies enthält als Daten ein String-Array :
private final String[ ] meineListe = { "Mos", "MA", "S", "VS", "KA", "RV" } ;
Diese Klasse soll die Interfaces Iterator und Iterable implementieren.
class Standorte implements Iterator, Iterable { /* … */ }
Testen Sie Ihre Implementierung, indem Sie ein Standorte-Objekt in einer forEach-Schleife
iterieren. Dies funktioniert für alle iterablen Objekte:
Es wird automatisch next( ) aufgerufen
Standorte st = new Standorte( ) ;
for( Object s : st ) IO.writeln( s ) ;
Übung 21 :
<<Interface>>
Iterator
public boolean hasNext( )
public Object next( )
public void remove( )Der Compiler zeigt Warnungen, da wir beim
Implementieren den Raw-Type verwenden.
(56)
Interfaces java.util.Iterator und java.lang.Iterable
Anmerkungen zu den zu implementierenden Methoden :
Iterator iterator( ) :
Die Methode liefert this zurück - ein Objekt unserer Klasse istzugleich sein eigener Iterator.
Zudem setzt sie den internen cursor auf 0.
boolean hasNext( ) :
Liefert true, solange cursor noch nicht die Länge des Arrays überschritten hat - sonst false.
void remove( ) :
Nicht unterstützt – deshalb : throw new UnsupportedOperationException( ) ; // uc RT
Object next( ) :
Liefert nacheinander die im Array gespeicherten Objekte – und merkt sich durch Hochzählen
des internen cursors, wo die Abfrage steht.
Wenn alles abgefragt wurden und dennoch weiter zugegriffen wird, dann :
throw new NoSuchElementException( ) ; // uc RT
Übung 21 :
(60)
Collection Framework
Nutzen vorhandener Klassen
(62)Collection Framework
1. Ergänzen Sie folgendes Coding, so dass jedes Element der Liste l1 auch in der Liste l2 vorkommt, die
Liste l2 aber keine Dublikate mehr enthält !
List<Integer> l1 = new LinkedList<Integer>( ) ;
l1.add( new Integer(3) ); l1.add( new Integer(4) ); l1.add( new Integer(3) ); l1.add( new Integer(6) );
System.out.println( l1 );
List<Integer> l2 = new ArrayList<Integer>( ) ;
Verwenden Sie ein zwischengeschaltetes HashSet oder TreeSet …
2. Schreiben Sie ein Programm, dass mittels eines Set-Objekts die Ziehung der Lottozahlen simuliert :
Lasse Sie dazu wiederholt eine ganzzahlige Zufallszahl zwischen 1 und 49 generieren und in das Set
einfügen, bis dieses sieben verschiedene Elemente enthält. Geben Sie den Set-Inhalt aus.
Wie könnte man sich den Inhalt des Set-Objekts als Integer[ ] - Array geben lassen ?
3. Realisieren Sie die aus der Logik bekannten Mengenoperationen : Vereinigung, Schnitt und Differenz
mit den in Collection enthaltenen Methoden auf Basis von Set -Objekten.
Gegeben sind die Sets s1 und s2 of Integer
Realisieren Sie : s1∪ s2 s1 ∩ s2 s1 \ s2 wobei das Ergebnis der Operation im Set s1
erzeugt wird – durch Aufruf der Methoden auf s1.
Übung 22
(63)
Collection Framework Queues + Stacks
Verwenden Sie ein Objekt vom Typ ArrayDeque , um ganz einfach einen generischen
Stack<E> zu bauen …
… mit den typischen öffentlichen Methoden void push( E e ) und E pop( ) .
Testen Sie den Stack mit einigen Objekten einer beliebigen Klasse.
Anmerkung :
Auch die JDK-Docu empfiehlt, nicht mehr java.util.Stack zu verwenden, sondern …
"A more complete and consistent set of LIFO stack operations is provided by the Deque interface
and its implementations, which should be used in preference to this class.
For example : Deque<Integer> stack = new ArrayDeque<Integer>( ) ; "
Übung 23
(64)
Collection Framework
Nötige Klassen-Infrastruktur
Arbeiten Sie mit einer Klasse Konto (Attribute name, kontoStand, kontoNummer).
Das vergleichsrelevante Attribut sei kontoNummer.
Geben Sie der Klasse Konto eine konsistente Klasseninfrastruktur :
→ equals, hashCode, toString, compareTo
Konto-Objekte sollen zusätzlich durch zwei Komparatoren auch nach Namen und (ganzzahligem - durch
Cast zu int) Kontostand sortierbar sein.
Wenn alles funktioniert verändern Sie testweise den Namen der Methode hashCode in hashcode.
Welche Auswirkung hat dies auf die Wirkungsweise der Methoden add( ) und contains( ) der Klasse
HashSet, wenn Sie Objekte Ihrer Konto-Klasse an ein HashSet-Objekt übergeben ?
Übung 24
(66)
Threading
Scheiben nebenläufiger Klassen
Starten von Threads
join-Operationen
Synchronisationsprobleme
(67)
Threads - Synchronisations-Problem
Verwenden Sie die Klassen Lager und Lieferant, um zu testen, dass bei fehlender
Synchronisation falsche Lagerbestands-Werte entstehen :
Erzeugen Sie in einer Klasse Lagerverwaltung ein Lager und zwei Lieferanten für das
selbe Lager.
Starten Sie die Lieferanten, joinen Sie diese - und geben Sie den Lagerbestand aus.
Überzeugen Sie sich, dass die Werte (ohne synchronized) nicht korrekt sind !
Übung 25
class Lieferant extends Thread {
private Lager lg;
public Lieferant(Lager lg) { this.lg = lg; }
public void run( ) {
for( int i=0; i<100000; i++ ) lg.anliefern(1) ;
}
}
class Lager {
private volatile int bestand = 0;
public int getBestand( ) { return bestand; }
// nicht synchronisiert:
public void anliefern( int i ) {
int b = bestand + i; bestand = b;
}
}
Tritt auch auf mit: bestand++
Auch dies ist eine nicht-atomare Op.
(68)
Threads - Nicht-atomare Operationen
Weisen Sie nach, dass die Anweisung in++ für eine int-Variable in sowie die Wert-
Zuweisung eines long-Wertes für eine long-Variable lg = lg+1 nicht atomar sind.
Dies kann etwa dadurch geschehen, dass man zwei Threads auf entsprechende
statische Attribute oft (z.B. je 10000 mal) zugreifen lässt.
Schreiben Sie eine Klasse, die Runnable implementiert und die Variablen int in und
long lg als statische Attribute hat.
In der run( )-Methode wird oft (in einer Schleife) in++ und lg=lg+1 ausgeführt.
Starten Sie in main() zwei Threads dieser Klasse und joinen Sie diese.
Geben Sie danach den Wert von in und lg aus.
Übung 26
(69)
Threads - Paralleles Rechnen
Erstellen Sie ein Programm, bei dem ein boolean Array von mehreren Threads
analysiert wird.
Verwenden Sie dazu den Code im Skript (Version ohne ResultHandler).
Jeder Thread zählt in einem Array-Segment die Anzahl der Vorkommens von true-
Werten und meldet diese an das Hauptprogramm zurück.
Füllen Sie das Array anfangs einfach komplett mit true - dann ist klar, was das
richtige Endergebnis ist.
Variieren Sie die Anzahl NUM der Threads und vergleichen Sie die Laufzeiten
(messbar mit System.currentTimeMillis() oder System.nanoTime() ).
Vergleichen Sie diese auch mit einem Single-Thread Programm (NUM = 1)
Bis zu welcher Zahl von Threads NUM wird Berechnung schneller ?
Was bewirkt jede weitere Vergrößerung von NUM ?
Übung 27
