WS 97/98: Algorithmen und Programmierung III - Übungsblatt 9
Abgabe bis 15.1., 12.30 Uhr
Aufgabe 9.1 (6 Punkte)
Ein Modul Sets verwalte linear geordnete Mengen in zwei
alternativen Repräsentationen - als sortierte Felder und als Suchbäume:
DEFINITION MODULE Sets;
TYPE BaseType = ...
TYPE SetA, SetT; (* Sets as arrays and sets as trees *)
PROCEDURE newSetA(): SetA;
PROCEDURE newSetT(): SetT;
PROCEDURE insertA(elem: BaseType; set: SetA) .....
PROCEDURE insertB(elem: BaseType; set: SetB) .....
.....
PROCEDURE a2t(set: SetA): SetT; (* generates tree from array *)
PROCEDURE t2a(set: SetT): SetA; (* generates array from tree *)
END Sets.
Die Prozeduren a2t und t2a erzeugen aus einem gegebenen
Mengenobjekt ein anderes mit gleichem abstrakten Wert, aber anderer
Repräsentation. Gesucht sind die Repräsentationen für SetA und
SetT sowie die Implementierungen von a2t und t2a.
Aufgabe 9.2 (6 Punkte)
Häufig interessiert man sich für diejenigen Elemente x einer lienear
geordneten Menge M, die zwischen zwei vorgegebenen Werten a und b liegen,
z.B. alle Namen in einem Namensverzeichnis, die mit dem Buchstaben Y
beginnen: { x | x<-M; "Y"<=x<"Z"}. Diese Elemente kann man zwar mit
einer Traversierungsoperation finden, eine gezielte Suche ist aber oft
effizienter. In Miranda beispielsweise hätten wir
abstype set*
with ...
traverse :: (*->bool) -> set* -> [*]
Damit leistet traverse p mit p x = a<=x<=b zwar das
Gewünschte, aber eben um den Preis des Durchsuchens der ganzen Menge.
Besser wäre also eine Erweiterung der Signatur um eine Spezialoperation
list :: (*,*) -> set* -> [*]
die bei einer Repräsentation der Menge als Suchbaum ähnlich wie die
Suchoperation vorgeht und zur Berechnung von list(a,b)s die
Bereiche mit a>x und x>b erst gar nicht betrachtet.
a) Implementiere für die Repräsentation set* == bintree* (8.3.1)
die Funktion list!
b) Implementiere für die Repräsentation
IMPLEMENTATION MODULE Menge; (* als Suchbaum (8.3.1) *)
TYPE Baum = POINTER TO Knoten;
Knoten = RECORD wert: B;
links, rechts: Baum END;
VAR anker: Baum;
.....
eine entsprechende Prozedur
PROCEDURE auflisten(von,bis: B; wie: Proc)
wobei wie das Auflisten präzisiert. Wie beim Traversieren ist
TYPE Proc = PROCEDURE(B) .
6.1.1998