Neben den Arrays gibt es in Pascal noch weitere zusammengesetzte Typen, die jeweils für spezielle Anwendungsgebiete besonders geeignet sind. Zu jedem skalaren Typ T läßt sich ein Typ SET OF T deklarieren, der als Werte alle möglichen Mengen von Werten des Typs T annimmt:
TYPE FRUCHT = (APFEL, BIRNE, ORANGE);
OBST = SET OF FRUCHT;
FAMSTAND = (LEDIG, VERHEIRATET, GETRENNT, GESCHIEDEN, VERWITWET);
VAR LIEFERBAR, AUSVERKAUFT: OBST;
ZAHLENMENGE: SET OF 1..30;
KOMMANDOS: SET OF 'A' .. 'E';
STATISTIK2: SET OF FAMSTAND;
Die Variablen LIEFERBAR und AUSVERKAUFT können also die folgenden Werte annehmen:
[ ] [APFEL] [BIRNE] [ORANGE] [APFEL, BIRNE] [APFEL, ORANGE] [BIRNE, ORANGE] [APFEL, BIRNE, ORANGE]
Dies sind alle möglichen Mengen, die aus den drei Früchten gebildet werden können (2 hoch 3 Möglichkeiten). Um die Operationen mit Mengen in Pascal zu verstehen, müssen Sie sich nur an den Mengenlehreunterricht erinnern, und die in der Mathematik üblichen geschweiften Mengenklammern (»{« »}«) durch die eckigen Klammern (»[« »]«) in Pascal ersetzen. Praktisch alle Operationen der Mengenlehre sind auch in Pascal verfügbar. Sind A und B Mengenausdrücke des gleichen Typs, so sind folgende Operationen möglich:
| A + B | bildet die Vereinigungsmenge von A und B, das sind alle Elemente, die in A oder B enthalten sind. |
| A * B | bildet die Schnittmenge von A und B, das sind alle Elemente, die gleichzeitig in A und B enthalten sind. |
| A - B | bildet die Differenzmenge von A und B, das sind alle Elemente, die in A und nicht in B enthalten sind. |
| A = B | testet die Mengen A und B auf Gleichheit. Das heißt, jedes Element von A ist Element von B und umgekehrt. |
| A<>B | liefert das Ergebnis NOT (A=B) |
| A <= B | prüft, ob A Teilmenge von B ist. |
| A >= B | prüft, ob A Obermenge von B ist. |
| a in B | prüft, ob das Element a in der Menge B enthalten ist. |
| [ ] | bildet die leere Menge |
| [a,b] | bildet die Menge, die aus den Elementen a und b besteht. |
| [a..b] | bildet die Menge, die alle Werte zwischen a und b (einschließlich) beinhaltet. Ist a>b, so bezeichnet [a..b] die leere Menge []. |
Wichtig ist die Tatsache, daß A und B den gleichen Elementtyp besitzen:
[LEDIG, VERHEIRATET] + [APFEL..BIRNE]
ist offenbar ein sinnloser Ausdruck. Wie in der Mathematik ist [APFEL] nicht gleich APFEL. Das erste ist eine einelementige Menge (vom Typ OBST) und das andere ein Wert des Aufzählungstyps FRUCHT. Außerdem enthält eine Menge kein Element doppelt.
Allgemein gesprochen werden Mengen überall dort verwendet, wo Werte eines Typs in ungeordnete Gruppen mit gewissen Eigenschaften aufgeteilt werden sollen. Um zum Beispiel in einem Gemüseladen Buch über die lieferbaren Früchte zu führen, eignen sich die Mengenvariablen LIEFERBAR und AUSVERKAUFT.
LIEFERBAR:= [APFEL, BIRNE, ORANGE];
AUSVERKAUFT:= [];
LIEFERBAR:= LIEFERBAR + [BIRNE];
AUSVERKAUFT:= AUSVERKAUFT - [BIRNE];
LIEFERBAR:= LIEFERBAR * [BIRNE..ORANGE];
IF [APFEL,ORANGE]<= LIEFERBAR THEN
WRITELN('Apfel und Orange lieferbar');
IF LIEFERBAR * AUSVERKAUFT <>[] THEN
WRITELN('Fehler in der Buchführung');
IF APFEL IN AUSVERKAUFT THEN
LIEFERBAR:= LIEFERBAR - AUSVERKAUFT;
Sie sollten sich die Mühe machen, die Bedeutung jeder einzelnen Anweisung in Worte zu fassen, um die teilweise recht komplexen Operationen zu verstehen. Mengenoperationen mit Mengen des Typs SET OF CHAR werden in vielen Programmen zur Vereinfachung von Abfragen benutzt:
REPEAT READ(CH) UNTIL CH IN ['J','Y','N']; IF CH IN ['0'..'9'] THEN ... IF CH IN ['0'..'9','A'..'Z'] THEN ...
Grundsätzlich beschränkt jeder Computer die Größe einer Menge. Als Grundtyp für Mengen scheidet deshalb neben dem Typ REAL auch der Typ INTEGER aus. Zum Beispiel gibt es bereits für eine Variable des (zulässigen) Typs SET OF 1..30 genau 2 hoch 30 = 10737341824 verschiedene Werte!
Pascal 2.0 erlaubt nur Mengen von Typen, die nicht mehr als 96 Werte annehmen können. Durch diese Grenze können auch Mengen von Zeichen (SET OF CHAR) dargestellt werden, die jedoch keine Grafikzeichen (respektive Großbuchstaben) enthalten dürfen, für die gilt:
ORD(CH)>=96
Das Programm in Bild 60 zeigt die Wirkung der Mengenoperationen am Beispiel des Typs SET OF CHAR. Nach den obigen Erläuterungen erübrigt sich eine weitere Diskussion des Programmlistings:
PROGRAM MENGENLEHRE (INPUT,OUTPUT);
TYPE MENGE = SET OF CHAR;
VAR A,B : MENGE;
E : CHAR;
PROCEDURE EINGABE(VAR M: MENGE);
VAR CH: CHAR;
BEGIN
M:= []; READ(CH);
WHILE NOT EOLN DO
BEGIN M:= M + [CH]; READ(CH) END;
END; (* EINGABE *)
PROCEDURE AUSGABE (M: MENGE);
VAR CH: CHAR;
BEGIN
FOR CH:= ' ' TO CHR(95) DO
IF CH IN M THEN WRITE(CH:3);
WRITELN
END; (* AUSGABE *)
BEGIN
WRITE('Menge A:'); EINGABE(A);
WRITE('Menge B:'); EINGABE(B);
WRITE('Menge A:'); AUSGABE(A);
WRITE('Menge B:'); AUSGABE(B);
WRITE('A + B :'); AUSGABE(A+B);
WRITE('A * B :'); AUSGABE(A*B);
WRITE('A - B :'); AUSGABE(A-B);
WRITE('A = B :'); WRITELN(A=B);
WRITE('A<= B :'); WRITELN(A<=B);
END.
Bild 60: Mengenoperationen
Wegen der sehr kompakten Speicherung der Werte eignen sich Mengen auch für die folgende Anwendung. Es sollen die Primzahlen von 1 bis 10000 gedruckt werden. Das einfachste Verfahren zur Bestimmung von Primzahlen wird durch das Sieb des Erasthotenes beschrieben:
Man beginnt mit einer Tabelle aller Zahlen im Intervall 1 bis 10000. Nun streicht man nacheinander alle Vielfachen der Zahlen 2, 3, 5, 7, 11 etc. Am Schluß bleiben also nur die Primzahlen in der Tabelle stehen, da sie durch keine der anderen Zahlen teilbar sind.
Bild 61: Sieb des Erasthotenes
Bild 61 zeigt den Anfang der Tabelle, wobei jeweils die Vielfachen von 2, 3, 5 und 7 gestrichen wurden. Man könnte also das Streichen der Vielfachen folgendermaßen in Pascal programmieren:
PROGRAM SIEB1 (INPUT, OUTPUT);
(* Dieses Programm ist nicht korrekt, da die Größe einer *)
(* Menge 96 Elemente nicht überschreiten darf. *)
CONST MAX = 10000;
VAR TEILBAR: SET OF 0..MAX;
P, Z, I: INTEGER;
BEGIN
TEILBAR:=[]; (* noch ist keine Zahl gestrichen worden *)
P:=1;
REPEAT
(* suche nächste Primzahl als Teiler *)
REPEAT
P:=P+1
UNTIL NOT( P IN TEILBAR);
(* streiche Vielfache von P *)
Z:= P*P;
WHILE Z<=MAX DO
BEGIN
TEILBAR:= TEILBAR + [Z];
Z:= Z + P
END;
UNTIL P*P>MAX;
(* Drucke die übriggebliebenen Primzahlen: *)
FOR I:= 2 TO MAX DO
IF NOT(I IN TEILBAR) THEN WRITE(I:6);
WRITELN
END.
Bild 62: Programm Sieb1
Wie bereits erwähnt, dürfen Mengen in Pascal 2.0 maximal 96 Elemente beinhalten. Daher wird die Menge TEILBAR aus Bild 62 durch ein Array von Mengen mit jeweils 96 Elementen realisiert. Die erste Menge enthält also die Zahlen von 0 bis 95, die zweite die Zahlen zwischen 96 und 191 etc. Damit erhält man das korrekte Programm in Bild 63:
PROGRAM SIEB2 (INPUT, OUTPUT);
(* Dieses Programm bestimmt alle Primzahlen im Bereich von *)
(* 1 bis MAX. Dabei simuliert das Array TEILBAR eine Menge *)
(* mit MAX Elementen. Die Darstellung erfolgt durch MAX96 *)
(* Mengen mit jeweils SETSIZE Elementen *)
CONST MAX = 10000;
SETSIZE = 96; (* Für Pascal 2.0 *)
MAX96 = 105; (* = MAX DIV SETSIZE + 1 *)
VAR TEILBAR: ARRAY[0..MAX96] OF SET OF 0..95;
P, Z, I: INTEGER;
FUNCTION PRIM(Z:INTEGER): BOOLEAN;
(* Prüfe, ob die Zahl Z prim ist, d.h. Z ist nicht in *)
(* der Menge der teilbaren Zahlen *)
BEGIN
PRIM:= NOT((Z MOD SETSIZE) IN TEILBAR[Z DIV SETSIZE])
END; (* PRIM *)
BEGIN
FOR I:= 0 TO MAX96 DO
TEILBAR[I]:=[]; (* noch wurde keine Zahl gestrichen *)
P:=1;
REPEAT
(* suche nächste Primzahl als Teiler *)
REPEAT
P:=P+1
UNTIL PRIM(P);
(* streiche Vielfache von P *)
WRITELN('Streiche Vielfache von', P:4);
Z:= P*P;
WHILE Z<=MAX DO
BEGIN
I:= Z DIV SETSIZE;
TEILBAR[I]:= TEILBAR[I] + [Z MOD SETSIZE];
Z:= Z + P;
END;
UNTIL P*P>MAX;
(* Drucke die übriggebliebenen Primzahlen: *)
FOR I:= 2 TO MAX DO
IF PRIM(I) THEN WRITE(I:6);
WRITELN
END.
Bild 63: Programm Sieb2
Aufgaben
1. Schreiben Sie eine Funktion, die die Anzahl der Elemente in einer Menge als Ergebnis liefert.
2. Geben Sie Mengenausdrücke an, durch welche die in den Venn-Diagrammen (Bild 64) schraffierten Mengen berechnet werden.
TYPE MENGE = SET OF 0 .. 95; VAR A, B: MENGE; A:= [1,3,5,7]; B:= [2,4,6,7,10];
Bild 64: Venn-Diagramme
3. Schreiben Sie ein Programm, das die ersten 500 Primzahlen in einem Array A speichert. Im Gegensatz zum Programm SIEB2 prüfen Sie hierbei für jede Zahl, ob sie durch eine der bereits gespeicherten kleineren Primzahlen teilbar ist. Sie können den Algorithmus verbessern, indem Sie von Anfang an die Vielfachen von 2 und 3 ausschließen. Vergleichen Sie die Programmlaufzeiten!