185.A02 Grundlagen der Programmkonstruktion 2015S 1 Aufgabenblatt GPK2 zu Grundlagen der Programmkonstruktion für die Übung am 21. Mai 2015 Dieses Aufgabenblatt gilt nur für Teilnehmer(innen) an „Grundlagen der Programmkonstruktion“, nicht für Teilnehmer(innen) an „Programmkonstruktion“ oder „Programmierpraxis“. Bitte lösen Sie alle Aufgaben auf diesem Aufgabenblatt und bringen Sie die Lösungen zur Übung am 21. Mai 2015 in den HS14 mit. Ablauf und Beurteilung erfolgen wie bei der ersten Übungseinheit. 1 Reihenfolgen Eine im Detail unbekannte, zu Beginn leere Datenstruktur x ist vorgegeben. Mittels add fügt man einen Wert (vom Typ int) in die Datenstruktur ein. Ein Aufruf von remove entfernt einen Wert aus der Datenstruktur und gibt ihn zurück. Folgender Java-Code wird ausgeführt: x.add(1); x.add(2); System.out.print(x.remove() + ", "); x.add(3); x.add(4); System.out.print(x.remove() + ", "); System.out.print(x.remove()); Je nach Datenstruktur (Fälle a bis c) wird dabei folgende Zeile ausgegeben: a) 1, 2, 3 b) 2, 4, 3 c) 1, 3, 2 Aufgaben: • Beschreiben Sie für a) bis c), welche Art von Datenstruktur x sein könnte. Achtung: Nicht jede dieser Datenstrukturen muss einen allgemein bekannten Namen haben. • Implementieren Sie die Datenstrukturen entsprechend a) bis c) jeweils mit den Methoden add und remove, wobei die Daten in Arrays abgelegt werden. 185.A02 Grundlagen der Programmkonstruktion 2 2015S 2 Binärbaum und Liste Lösen Sie folgende Programmieraufgaben ohne Zuhilfenahme vordefinierter Methoden aus Java-Bibliotheken: • Erweitern Sie die Klasse IntTree aus der Vorlesung vom 4. 5. 2015 um zwei Methoden, die jeweils eine Liste (vom Typ IntQueueElem aus derselben Vorlesung) zurückgeben. Das Ergebnis einer Methode enthält die Elemente des Baums in aufsteigender Reihenfolge, das der anderen Methode in absteigender Reihenfolge. • Erweitern Sie IntQueueElem um eine Methode, die ein Array zurückgibt, das die Elemente der Liste in derselben Reihenfolge wie die Liste enthält. Die Größe des Arrays soll der Länge der Liste entsprechen. • Erweitern Sie IntTree um einen Konstruktor mit einem int-Array als Parameter, wobei die Werte im Array aufsteigend sortiert sind. Der erzeugte Baum soll alle Elemente des Arrays enthalten, und alle linken und rechten Teilbäume sollen annähernd gleich groß sein. • Testen Sie den Code, indem Sie – einen Baum aus Zufallszahlen aufbauen (ohne den neuen Konstruktor), – den Baum in eine aufsteigend sortierte Liste umwandeln, – die Liste in ein Array umwandeln, – aus dem Array einen neuen Baum aufbauen, – beide Bäume in absteigend sortierte Listen umwandeln – und schließlich diese beiden Listen miteinander vergleichen. 3 Bubblesort Wandeln Sie die Methode bubbleSort aus der Vorlesung vom 11. 5. 2015 so ab, dass die Variable done nicht mehr benötigt wird. Stattdessen wird der Rumpf der äußeren Schleife so oft wiederholt ausgeführt wie das Array Einträge hat. Beantworten Sie dazu folgende Fragen: • Warum terminiert die abgewandelte Methode? • Wie ändert sich der Aufwand im besten, durchschnittlichen und schlechtesten Fall? • Wie hoch ist der Aufwand der ursprünglichen (unveränderten) Methode bubbleSort wenn das Array vor dem Sortieren a) schon sortiert ist, b) Zufallszahlen enthält bzw. c) umgekehrt sortiert ist? • Wie hoch ist der Aufwand der veränderten Methode bubbleSort wenn das Array vor dem Sortieren a) schon sortiert ist, b) Zufallszahlen enthält bzw. c) umgekehrt sortiert ist? 185.A02 Grundlagen der Programmkonstruktion 4 2015S 3 Klassen und Objekte Geben Sie tiefgehende Antworten auf folgende Fragen in Bezug auf Java: • Wodurch unterscheiden sich Konstruktoren syntaktisch und inhaltlich von Methoden? Kann man statt Konstruktoren stets Initialisierungsmethoden verwenden? Kann man statt Initialisierungsmethoden stets Konstruktoren verwenden? • Wozu benötigt und wie verwendet man die Pseudovariable this sowie Aufrufe der Form this(...)? Angenommen, this und this(...) würde es nicht geben. Wie könnte man entsprechende Anwendungsfälle stattdessen lösen? • Aus welchen Gründen sind Objektvariablen meist private? Welche Vor- und Nachteile ergeben sich daraus? • Warum werden Ihrer Meinung nach Objektvariablen gleich bei der Objekterzeugung mit einem Default-Wert belegt, lokale Variablen aber nicht? Auf diese Frage gibt es keine Standardantwort. Sie müssen Ihre eigene Meinung ergründen und mit kleinen Beispielen belegen bzw. hinterfragen. • Warum werden Ihrer Meinung nach aus Klassen erzeugte Objekte in Java immer über Referenzen angesprochen, elementare Werte (z.B. vom Typ int) aber nicht? Muss das auch in anderen Sprachen stets so sein? Auch hier brauchen Sie keine Standardantwort geben, sondern sollen Ihre eigene Meinung ergründen, belegen und hinterfragen. 5 Datenstrukturen Beantworten Sie folgende Fragen im Detail, nicht nur oberflächlich: • Wodurch unterscheiden sich in Java Objekte vom Typ Map von Arrays? In welchen Fällen ist welche dieser Datenstrukturen vorteilhaft? • Der Typ Deque stellt zahlreiche Methoden bereit um FIFO- und LIFO-Verhalten zu erreichen. Geben Sie einen Überblick über diese Methoden. Welche der Methoden passen gut zusammen, und durch welche Kombinationen von Methoden wird welches Verhalten erreicht? • Anhand welcher Kriterien kann man entscheiden, ob für eine gegebene Aufgabenstellung Map (bzw. ein Array) oder Deque (bzw. Queue) besser geeignet ist? • Angenommen, eine gewünschte Datenstruktur kann als Liste oder binärer Baum implementiert werden. Anhand welcher Kriterien treffen Sie die Auswahl? • Die binäre Suche in einem Array ist sehr effizient, die Erzeugung eines dafür notwendigen sortierten Arrays oft aber nicht. Unter welchen Bedingungen ist der gesamte Ansatz (sortiertes Array erzeugen und darin suchen) vorteilhaft, in welchen nicht?