Claus Schönleber

Hitchhacker´s Guide To PASCAL  [Vol. 2]

 [ zurück | weiter ]
  [ Start | Beispielprogramme Download | Home ]

Inhalt

Typisierte 
 Konstanten
Sets (Mengen)
Rekursion
Records
Dateien
 (Random Access)
Pointer
Algorithmen
- Hashing
- Sortieren
 
 

Mengen (Sets)

Seltsamerweise gehören Mengen zu den am wenigsten benutzten Strukturen in PASCAL. Wahrscheinlich liegt das an dem mit viel Mystik behafteten Namen (siehe Mengenlehre). Genau damit hat das Ganze aber zu tun. Einsatzgebiet von Sets ist die Kontrolle, ob ein bestimmtes Datum zu einer vorgegebenen Menge gehört. Dabei können verschiedene Mengen auch mittels Mengenoperationen (Schnittmenge, Vereinigungsmenge,...) manipuliert werden.

Bei der Benutzung der Mengen kommt man weg von der imperativen Formulierung und hin zu einer Art der Beschreibung einer Lösung, die nicht mehr so viel mit dem "wie" als vielmehr mit dem "was" zu tun hat. 

Menge (Set)
Eine Menge oder Set ist eine Ansammlung von Daten desselben Typs, die als Einheit angesehen werden. Die in einer Menge enthaltenen Daten werden Elemente genannt.
Beispiele 
Alle druckbaren Zeichen, alle Elemente eines selbstdefinierten Typs, alle Zahlen zwischen 1 und 100, alle Ziffern,...
Zunächst ein einfaches Beispiel, bei dem Mengen implizit, d.h. nicht ausdrücklich, verwendet werden. Stellen Sie sich vor, Sie formulieren eine Benutzeroberfläche für ein Programm in Form eines Menüs. Die einzelnen Funktionen des Menüs können durch Tippen des Anfangsbuchstabens ausgelöst werden. Dabei dürfen natürlich nur bestimmte Buchstaben eingegeben werden, andernfalls soll die Eingabe wiederholt werden. Zugelassene Buchstaben sind 'A','B','C','Q' und die entsprechenden Kleinbuchstaben. Somit kann man folgendes Programmfragment formulieren:
VAR c : char;
  .
  .
  .

  REPEAT
    c := readkey;
  UNTIL c IN ['A','B','C','Q','a','b','c','q'];
  .
  .
Sie sehen, man kann sich einen langen logischen Ausdruck aus vielen "(c = ..) AND ..." sparen, wenn man hier eine Menge einführt. Denn die eckige Klammer bezeichnet eine Menge und der Operator IN prüft, ob das Zeichen in "c" zu der Menge gehört. IN ist also die Beziehung "Element von". 

Mengen können natürlich auch explizit deklariert werden. Das geht mit Hilfe folgender Konstruktion:

VAR <name> : SET OF <mengentyp>;
Dabei kann <mengentyp> ein einfacher Standardtyp, Teilbereichtyp oder selbstdefinierter Typ sein.

Folgende Operationen sind für Mengen zugelassen:
 
 

Operation Symbol
Vereinigungsmenge +
Schnittmenge  *
Komplementmenge -
Mitglied, Element von  IN
Gleicheit, Äquivalenz =
Ungleichheit, Antivalenz <>
Teilmenge <=
Obermenge >=
[Mengenoperationen]

 

Sets: Union, Intersection, Complement

Beipiele:

VAR vokale,konsonanten,buchstaben,
    x,y,z : SET OF char;
.
.
.
  buchstaben := ['A'..'Z'];
  vokale := ['A','E','I','O','U'];
  (* Komplementmenge von "vokale" bzgl. buchstaben *)
    konsonanten := buchstaben - vokale;
  (* Vereinigungsmenge *) 
    x := vokale + konsonanten;
  (* Schnittmenge *)
    y := ['A','B','C','D','E'];
    z := ['B','C','K','L','M'];
    x := y * z; (* x enthält 'B' und 'C' *)
.
.
Merksatz: Variablen vom Typ Menge enthalten nicht ein Datum aus der Menge, sondern immer die gesamte Menge, die ihnen per Zuweisung zugeordnet wurde! 
 
 
SET ARRAY
Jedes Element ist Repräsentant 
(i.e. kommt nur einmal vor)
Mehrere Komponenten können mit demselben Inhalt belegt werden.
In einer Menge gibt es keine Ordnung. Entscheidend ist nur das Vorhandensein. Komponentenlisten sind geordnet. Entscheidend ist die Position in der Liste.
Mathematisches Synonym
Menge n-Tupel
[Mengeneigenschaften im Vergleich zu Feldern]

Deswegen können solche Variablen auch nicht direkt auf dem Bildschirm mit "write" ausgegeben werden. Aber auch dieses Problem ist lösbar und wird im folgenden Vorschlag demonstriert. Um die Anwendung von Sets in eienr Anwendung zu üben, werden wir hier das Programm "Sieb des Erathostenes" aus Kurs 1 umformulieren und mit Hilfe von Mengen lösen.

PROGRAM erato2;
  CONST n = 255;
  VAR   allnumbers,prim : SET OF 2..n;
        next,nprim,i    : integer;
BEGIN
  prim := [];
  next := 2;
  allnumbers := [2..n];

  REPEAT
    IF NOT (next IN allnumbers) THEN
      next := succ (next)
    ELSE
    BEGIN 
      prim := prim + [next];
      nprim := next;
      WHILE (nprim <= n) DO
      BEGIN
        allnumbers := allnumbers - [nprim];
        nprim := nprim + next;
      END;
    END;
  UNTIL (allnumbers = []);

  FOR i := 1 TO n DO
    IF (i IN prim) THEN
      write (i:8);
END.


Da die Menge in "prim" nicht einfach so ausgegeben werden kann, kommt hier unsere schon bewährte Hilfskonstruktion zum Einsatz, die wir schon im Beispielprogramm "Lotto" aus Kurs 1  verwendet haben.

Wichtig beim Einsatz von Mengen ist, daß Variablen von diesem Typ immer alle Elemente einer definierten Menge enthalten, und zwar ohne eine Ordnung, d.h. ohne Reihenfolge. Stellen Sie sich eine SET-Variable immer als Kasten vor, in dem alle Dinge wahllos herumliegen. Weiterhin kann jedes Datum nur einmal vorkommen. Mit Hilfe der zugelassenen Operationen können Mengen vergrößert oder verkleinert werden, wie das in obigem Beispiel auch kräftig gemacht wird. Die Zahlen, die als Primzahlen erkannt sind, werden mitsamt ihren Vielfachen ("nprim") aus der Menge der Zahlen herausgenommen bis sie leer ist. Eine leere Menge enthält kein Element.

Die leere Menge ist das neutrale Element der Mengen. Genau wie die 0 für die Addition, die 1 für die Multiplikation oder der Leerstring ('') für die Strings stellt die leere Menge die "Null" für Mengenoperationen dar. Sie wird mit [] bezeichnet. Die Variable "prim" wird so initialisiert, da anfangs ja keine Primzahlen ermittelt worden sind.

 

 [ zurück | weiter ]
   (c) 2001 Schoenleber.com