WS 97/98: Algorithmen und Programmierung III - Übungsblatt 2
Abgabe bis 28.10., 16 Uhr
Aufgabe 2.1 (4 Punkte)
Für die Doppelkopfschlange aus Aufgabe 1.1 soll angegeben werden
a) eine Signatur für einen abstrakten Datentyp dequeue
in Miranda,
b) eine Implementierung von dequeue.
dequeue ist geeignet zu testen.
Aufgabe 2.2 (7 Punkte)
Für einfache Schlangen mit den Operationen append, remove
bieten sich zwei alternative Implementierungen an: Feld bzw. Geflecht.
Ein Modul Queues soll Schlangenobjekte beider Arten verwalten
und auch die verschiedenen Repräsentationen ineinander überführen können.
Seine Schnittstelle sieht wie folgt aus:
DEFINITION MODULE Queues;
TYPE ArrayQueue; LinkedQueue;
PROCEDURE appendA(x: INTEGER; q: ArrayQueue);
PROCEDURE removeA(q: ArrayQueue): INTEGER;
PROCEDURE newA(): ArrayQueue;
PROCEDURE appendL(x: INTEGER; q: LinkedQueue);
PROCEDURE removeL(q: LinkedQueue): INTEGER;
PROCEDURE newL(): LinkedQueue;
PROCEDURE AtoL(q: ArrayQueue): LinkedQueue;
PROCEDURE LtoA(q: LinkedQueue): ArrayQueue;
END Queues.
Verfasse hierzu das Implementierungsmodul!
21.10.1997