Allgemeine Informatik II SoSe 2001
Prof. Dr. H. Neumann $\bullet$ Dr. K. Murmann $\bullet$ S. Geschwentner $\bullet$ Dr. F. Schwenker

9. Aufgabenblatt (bis zum 19.07.2001)

16. Aufgabe:
Zur Speicherung von eindimensionalen Mustern wurden in der Aufgabe 13 folgende Datenstrukturen definiert:

  CONST PATTERN_LENGTH = 16;
  TYPE 
    COLOR = (WHITE, BLACK);
    PATTERN = ARRAY [0..PATTERN_LENGTH-1] OF COLOR;
    TREE = POINTER TO NODE;
    NODE = RECORD
                color: COLOR;
                left, right: TREE;
           END;

1. Implementieren sie folgende Modula-2-Funktionsprozedur:

   
    PROCEDURE BlackPixels(t : TREE) : CARDINAL
   

   Funktionalität: Liefert die Anzahl der schwarzen Pixel des Musters das durch den Binärbaum t repräsentiert wird. Diesen Wert ermitteln Sie bitte auf dem Binärbaum selbst, nicht durch explizite oder implizite Umwandlung des Baumes in die zugehörige 0-1-Folge!

2. Es sei nun eine Menge von solchen Mustern, jeweils repräsentiert als Binärbaum, in einer linked list mit NIL Zeiger (siehe auch Aufgabe 3) abgespeichert. Diese Liste soll sortiert werden. Das Resultat der Sortierung soll eine Liste sein, in der die Muster vom Listenkopf beginnend bishin zum Listenende nach der Anzahl der schwarzen Pixel (verwende Prozedur BlackPixels) aufsteigend sind.

   Implementieren Sie hierfür eine Prozedur ShakerSort für linked lists ( array-Version: siehe Aufgabe 15). Bei den Vertauschungsoperation in der Sortierung der Liste sollen die Elemente der Liste vertauscht werden, nicht die Information die in den Listenelementen gespeichert ist.

Testen Sie die von Ihnen implementierten Prozeduren, mit der folgenden Mustersequenz
(0 : schwarz, 1 : weiss) :

0000-1101-0000-0000
0100-0000-1011-0000
0010-0001-1000-0010
0000-0000-0011-0000
0000-0101-0011-0100
1111-0001-0000-1111
0101-0100-1010-1010