Grundlagen Informatik II 10. Übung Hinweis: Auf der Seite http://wwwuser.tuchemnitz.de/~wuha/grundlagen_if_2/aufgaben.php finden Sie für alle Aufgaben je eine Vorgabedatei. Aufgabe 1 Implementieren Sie die Datenstruktur Stack (Stapel). Bei einem Stack werden neue Elemente am Anfang eingefügt (auf den Stack gelegt) und auch am Anfang wieder entnommen. Verwenden Sie eine einfach verkettete Liste. Verwenden Sie die vorgegebene Deklaration und ergänzen Sie alle fehlenden Funktionen. Achten Sie darauf, dass selbst bei fehlerhafter Verwendung der Klasse (z.b. Entnahme eines Elements bei leerem Stack) keine Speicherzugriffsfehler auftreten. Aufgabe 2 Implementieren Sie die Datenstruktur PriorityQueue (Warteschlange mit Prioritäten). Die Entnahme von Elementen ist identisch zur Funktionalität bei der normalen Queue: Es wird das vorderste Element der Schlange ausgegeben und entfernt. Neu eingefügte Element werden allerdings nicht immer am Ende der Schlange eingereiht, sondern werden so eingefügt, dass die Schlange nach der Priorität sortiert ist. Ganz vorn in der Schlange steht also immer das Element mit der höchsten Priorität. Werden mehrere Elemente mit der selben Priorität eingefügt, werden Sie in der Reihenfolge ausgegeben, in der sie eingefügt wurden. Hinweise: Verwenden Sie die Lösungen früherer Aufgaben. Prüfen Sie insbesondere, welche Funktionen Sie gegenüber die Klasse Queue ändern müssen, und welche Sie übernehmen können. Die Struktur für ein Listenelement für ein Listenelement ist in dieser Aufgabe so geändert, dass neben den Daten auch noch eine Priorität gespeichert wird. Außerdem werden als Daten jetzt Zeichenketten verwendet. Sie müssen Funktionen aus früheren Übungen entsprechend anpassen, falls Sie sie verwenden wollen. Extraaufgaben: Verwenden Sie die Klasse PriorityQueue um ein einfaches Sortierverfahren zu implementieren. Um welches Verfahren handelt es sich? Schreiben Sie eine alternative Implementation der Klasse Stack bei der Sie ein dynamisch angelegtes Feld anstatt einer einfach verketteten Liste verwenden. Es ist akzeptabel, wenn bei dieser Variante der Stack eine Maximalkapazität hat, die bei der Erzeugung festgelegt ist. Die Klasse sollte in diesem Falle aber die Einhaltung der Maximalkapazität prüfen. Das Ziel besteht darin, dass die Klasse die Lösung aus Aufgabe 1 ersetzen kann, ohne dass der Quellcode, der die Klasse benutzt geändert werden muss. Fragen an: [email protected]chemnitz.de Webseite zur Übung: http://wwwuser.tuchemnitz.de/~wuha/grundlagen_if_2/uebersicht.php