Embed Size (px)
Citation preview
Eine Umgebung zur Steuerung von
Multimedia-Dokumenten
(Am Beispiel klassischer Sortierverfahren)
Diplomarbeit
Jochen Lienhard
Institut f�ur Informatik
Albert{Ludwigs{Universit�at Freiburg i. Brg.
Prof. Dr. Th. Ottmann
April 1996
Vorwort
Im Zuge der Entwicklung von schnelleren Prozessoren und leistungsf�ahigeren Rechnern ist
der Bereich Multimedia weiter in den Vordergrund getreten. Gerade bei Lehr- und Lern-
software ist es wichtig, den Sto� mit Animationen und Simulationen anzureichern, um ein
leichteres Verstehen der Informationen m�oglich zu machen.
Mit dieser Arbeit wende ich mich in erster Linie an Studenten, die die Grundkenntnisse in
klassischen Sortierverfahren erworben haben. Es soll ihnen erm�oglicht werden, einfach und
schnell verschiedene Kapitel mit Text und Animation zu rekapitulieren.
An dieser Stelle m�ochte ich mich bei Professor Dr. Thomas Ottmann bedanken, der die
Entstehung dieser Arbeit erm�oglicht hat. Mein besonderer Dank gilt vor allem Christian
Bacher f�ur zahlreiche Programmiertips.
Weiterhin gilt mein Dank Herrn Morice und den Mitarbeitern des Institutes f�ur den Wis-
senschaftlichen Film in G�ottingen sowie allen Kommilitoninnen, Kommilitonen und Mitar-
beitern des Institutes f�ur Informatik, die bei Fragen und Problemen stets hilfsbereit waren.
Jochen Lienhard
Erkl�arung
Hiermit versichere ich, da� ich die vorliegende Arbeit selbst�andig und nur unter Verwen-
dung der angegebenen Hilfsmittel angefertigt habe.
Freiburg, im April 1996 Jochen Lienhard
Inhaltsverzeichnis
1 Einleitung 7
2 Algorithmen-Animationen 9
2.1 De�nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Verschiedene Systeme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 XTango . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3 Vom Algorithmus zur Animation 13
3.1 Kriterien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2.1 ANIM.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2.2 ANIMscenes.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4 Das Benutzerinterface 23
4.1 Inhaltsverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2 Textbereich . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.3 Filmsequenzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.4 Ober �ache von XTango . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5 Darstellungsarten 31
5.1 Balkendarstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.1.1 Standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.1.2 Variationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.2 Punktdarstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.3 Baumdarstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.4 Animation mit Programmtext . . . . . . . . . . . . . . . . . . . . . . . . . 36
5
Inhaltsverzeichnis Inhaltsverzeichnis
6 Erweiterungen und Ver�anderungen 37
6.1 Inhaltsverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
6.2 Popupmen�us . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
6.3 Text�les . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
6.4 Filmsequenzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
7 Zusammenfassung 41
A Installationshinweise 43
B Liste der Animationen 45
C Einige XTango-Funktionen 47
Bibliographie 51
6
Kapitel 1
Einleitung
In vielen Bereichen des Lebens halten Multimedia-Dokumente ihren Einzug. Schon auf
einigen Bahnh�ofen gibt es Computer, die n�aheres �uber die Stadt und ihre Sehensw�urdig-
keiten mitteilen. Auf einem ber�uhrungssensitiven Display kann man an einer virtuellen
Stadtf�uhrung teilnehmen. Hierbei werden Texte �uber Bauwerke, Filmausschnitte oder Bil-
der von Geb�auden und erkl�arende Tonausgaben miteinander verkn�upft. Das Ziel solcher
Dokumente ist es, dem Benutzer einen �Uberblick zu verscha�en. Es ist einfacher, audio-
visuelle Informationen zu verarbeiten als reine Textinformationen. Bei diesen verliert der
Benutzer schnell das Interesse und die Aufmerksamkeit.
Nicht nur auf Bahnh�ofen, sondern auch in privaten Haushalten gibt es inzwischen Multime-
dia-Dokumente. Neben Reisef�uhrern, die die gleiche Funktion wie die oben genannten Do-
kumente haben, gibt es auch Lexika. Diese w�urzen die \trockenen\ Texte mit Bildern und
Filmausschnitten.
Auch in Schulen und Universit�aten regt sich das Interesse an Multimedia-Dokumenten. Mit
ihrer Hilfe soll es den Sch�ulern und Studenten leichter gemacht werden, bereits erlernten
Sto� zu rekapitulieren.�Uber das World Wide Web hat man die M�oglichkeit, auf Daten in der ganzen Welt zuzu-
greifen. Darunter be�nden sich bisher kaum Informationen, die ein gezieltes Lernen erm�ogli-
chen. Der Grund liegt darin, da� die meisten Anbieter von Informationen mit einem System
arbeiten, in das der Benutzer keine eigenen Links setzen kann. Programme mit bestimmten
Abschnitten eines Postscript-Files zu verkn�upfen, ist ebenfalls nicht m�oglich.
Es existiert jedoch ein System, das diese Idee bereits realisiert: Hyper-G [5]
Mit seiner Hilfe kann man von einem Postscript-File Links auf Animationen oder Filmse-
quenzen setzen. Der Link ist an eine Position im Text gebunden und wird durch einfaches
Anklicken aktiviert. Sein Ziel ist genau de�niert. Es kann zum Beispiel eine andere Seite
desselben Textes sein. Wenn jedoch auf eine Animation zugegri�en werden soll, so mu�
man ein Shellskript schreiben, das den UNIX-Befehl zum Aufruf des Programmes enth�alt.
Auf dieses Skript zeigt dann der Link und f�uhrt es beim Aktivieren aus. Der gro�e Nachteil
dieses Systems liegt darin, da� der Benutzer nicht erkennen kann, ob er nun auf eine andere
Textseite oder zu einer Animation springt. Man hat also eigentlich Links unterschiedlicher,
7
KAPITEL 1. EINLEITUNG
aber nicht erkennbarer Typen. In dieser Arbeit wurde das Problem dadurch gel�ost, da�
Animationen und Filmsequenzen durch eigenst�andige Men�us gesteuert werden, was in den
Abschnitten 4.1 und 4.3 erl�autert wird.
Die Zeit, die zwischen einem Mausklick und der gew�unschten Aktion vergeht, ist bei Hyper-
G meist ziemlich lang. Dies liegt daran, da� das System auf den Server zur�uckgreifen mu�
und von dort die Informationen holt. Dadurch kommt es h�au�g zu langen Wartezeiten.
Damit es nicht zu solchen \Leerlaufzeiten\ kommt, ist diese Arbeit ein \stand alone\ Pro-
gramm. Alle ben�otigten Daten k�onnen auf der Festplatte gespeichert werden. Ihr Speicher-
bedarf ist sehr gering. Die zugeh�origen Filme werden auf einer CD-ROM belassen und von
dort bei Bedarf nachgeladen. Damit fallen die langen Wartezeiten weg.
Viele Funktionen von Hyper-G sind f�ur einen Benutzer, der keinen Internet-Anschlu� be-
sitzt, nicht nutzbar, ben�otigen aber dennoch Platz auf der Festplatte.
Die Kosten, die beim Suchen und Transferieren von Daten im Internet entstehen, fallen
beim Verwenden dieser Arbeit ganz weg. Der Benutzer greift in sein Regal, legt die CD-
ROM ein und hat unmittelbar den gesuchten Themenbereich auf dem Bildschirm.
Mit Texten und Filmsequenzen allein ist es schwierig, sich manche Algorithmen zu ver-
deutlichen. Um dies zu erleichtern, bietet sich der Einsatz von Algorithmen-Animationen
an. Gegen�uber Filmsequenzen ben�otigen sie viel weniger Speicherplatz. Der interessanteste
Punkt jedoch ist die Interaktion, die sie anbieten. Es ist beispielsweise m�oglich, die Daten
selbst einzugeben, die Geschwindigkeit zu steuern oder die Animation einzufrieren.
Zur Erstellung solcher Animationen wird ein System ben�otigt, das den Ablauf eines Algo-
rithmus in bewegte Bilder umsetzt. Die Entwicklung im Bereich der Algorithmen-Animation
wird im Kapitel 2 erl�autert. In dem anschlie�enden Kapitel wird der Weg vom Algorith-
mus bis zu Animationen anhand eines speziellen Systems genauestens beschrieben. Das
Kapitel 4 befa�t sich mit der Ober �ache des Multimedia-Dokumentes. Das letzte Kapitel
zeigt, wie man die Steuerung dieses Dokumentes zum Entwurf von anderen Dokumenten
verwenden kann.
8
Kapitel 2
Algorithmen-Animationen
2.1 De�nition
Was sind eigentlich Algorithmen-Animationen? Wozu dienen sie? Welche M�oglichkeiten
gibt es, eine Algorithmen-Animation zu erstellen?
Diese und weitere Fragen kommen jedem in den Sinn, der zum ersten Mal den Begri�
Algorithmen-Animationen h�ort. J. Stasko schrieb, da� sie dynamische graphische Illustra-
tionen von Computeralgorithmen seien und als Lernhilfe dienen, um zu erkl�aren, wie ein
Algorithmus funktioniert [7]. Weiter de�niert er den Begri� mit den Worten: \Algorithm
animation is the process of abstracting the data, opertions, and semantics of computer
programs, and then creating dynamic graphical views of those abstractions [9].\ Wenn Da-
ten, Operationen und die Semantik eines Computerprogrammes abstrahiert werden und
aus dieser Abstraktion dann dynamische Bilder entstehen, so spricht J. Stasko von einer
Algorithmen-Animation. Tre�end ist auch eine Bemerkung von M. Brown:"Ein Sprichwort
sagt:'Ein Bild sagt mehr als tausend Worte` und bewegte Bilder sagen noch viel mehr aus
[3].\
Genau darin liegt der Zweck von Animationen: Sie sollen den zugrunde liegenden Algo-
rithmus anschaulich machen. Wenige Menschen k�onnen sich anhand eines Computerpro-
grammes den Sinn und den genauen Ablauf des Verfahrens verdeutlichen. Die Animation
soll dies jedoch erm�oglichen.
2.2 Motivation
John Stasko, Albert Badre und Clayton Lewis fertigten eine Studie zu dem Thema \Do
Algorithm Animations Assist Learning?\[7] an. Zwanzig Studenten hatten sich f�ur diesen
Test zur Verf�ugung gestellt. Sie wurden in zwei gleich gro�e Gruppen aufgeteilt. Ihre Auf-
gabe war es nun, sich mit der Datenstruktur von Priority Queues vertraut zu machen.
Beide Gruppen bekamen eine textuelle Beschreibung des Algorithmus. W�ahrend die erste
9
2.3. VERSCHIEDENE SYSTEME KAPITEL 2. ALGORITHMEN-ANIMATIONEN
sich 45 Minuten mit dem Text befassen sollte, beendete die zweite nach bereits 30 Minu-
ten das Lesen und studierte in den verbleibenden 15 Minuten das Verfahren anhand einer
Animation, die mit XTango erstellt wurde.
In einem anschlie�enden Test wurde das neu erlernte Wissen der Studenten analysiert.
Neben wahr-falsch Aussagen wurden auch Fragen zur Komplexit�at und zur Wirkung der
einzelnen Operationen gestellt. Die Studenten, die nur den Text gelesen hatten, ben�otigten
45 Minuten zur Beantwortung aller Fragen. Die andere Gruppe hingegen war nach bereits
37.6 Minuten mit dem Test fertig. Bei der Korrektur stellte sich heraus, da� mehr Stu-
denten, die sich den Algorithmus zus�atzlich mit einer Animation verdeutlicht hatten, die
Fragen richtig beantwortet hatten als Personen der anderen Gruppe.
Zwar mag diese Studie, da sie nur mit einer kleinen Zahl von Studenten durchgef�uhrt
wurde, nicht repr�asentativ sein, aber sie zeigt eine Tendenz auf, die die Benutzung von
Algorithmen-Animationen unterst�utzt.
Bevor man sich jedoch mit einer Animation befa�t, sollte man in den Grundz�ugen den
Algorithmus kennen, der dargestellt wird. Es ist n�amlich nicht m�oglich, jede Operation
eines Verfahrens darzustellen.
2.3 Verschiedene Systeme
Das erste gr�o�ere Projekt von Algorithmen-Animationen war der Farb�lm Sorting Out
Sorting (SOS) [1], der im Jahre 1980 an der Universit�at von Toronto erstellt wurde.
In 30 Minuten werden die elementaren Sortierverfahren pr�asentiert. Als Darstellungsar-
ten werden Balken- und Punktdarstellungen verwendet (vgl. Abschnitt 5.1 und 5.2). Die
verschiedenen Verfahren werden in Wettl�aufen miteinander verglichen. Um sich einen �Uber-
blick �uber verschiedene Sortierverfahren zu scha�en, ist dieser Film wohl ausreichend. Falls
man jedoch ein Verfahren genauer untersuchen will, so st�o�t man schnell an eine Grenze.
An diesem Punkt w�are Interaktion sehr w�unschenswert.
Mit Brown University Algorithm Simulator and Animator (BALSA) [1] [3] schuf
M. Brown mit einigen Mitarbeitern das erste interaktive Algorithmen-Animations-Paket.
Es wurde 1983 f�ur Apollo Workstations in C programmiert. BALSA unterst�utzt das simul-
tane Ablaufen verschiedener Verfahren und zeigt im Gegensatz zu SOS auch Graphenalgo-
rithmen oder Baumstrukturen. Der zu visualisierende Algorithmus wird in Standard-Pascal
implementiert. Im Gegensatz zu BALSA hat der Benutzer in der nachfolgenden Version
Balsa-II die M�oglichkeit, die Animationen in Farbe darzustellen. Desweiteren wird ein
anderer Rechner ben�otigt, n�amlich ein Apple Macintosh. Den Verlauf der Animation kann
man selbstverst�andlich �uber Buttons steuern.
Vor einigen Jahren waren Apple Macintosh-Rechner f�uhrend auf dem Markt der graphi-
schen Darstellung. Inzwischen wurden sie aber von leistungsf�ahigeren Workstations ab-
gel�ost. Daher war eine neue Weiterentwicklung von BALSA gefordert. Diese gipfelte in
dem in Modula-3 geschriebenen System Zeus [1], das auf DEC-Workstations lau��ahig ist.
Die Soundunterst�utzung, die schon in Balsa-II im Ansatz vorhanden war, wurde weiter
ausgebaut. Auch der Tendenz zur 3-dimensionalen Visualisierung von Animationen wurde
10
KAPITEL 2. ALGORITHMEN-ANIMATIONEN 2.4. XTANGO
Rechnung getragen [4]. Bisher hat Zeus den Durchbruch auf dem freien Markt noch nicht
gescha�t. Es wird haupts�achlich von seinen Entwicklern benutzt.
2.4 XTango
Ein weiteres System zur Visualisierung von Algorithmen ist TANGO (Transiton-based
ANimation GeneratiOn) [1][9]. Es wurde von John Stasko entwickelt und verwendet die
sogenannte path-transition paradigm Methode. Sie erzeugt eine \glatte\ Animation, die an
die Qualit�at von Zeichentrick�lmen heranreicht. Die meisten anderen Systeme setzen ihre
Animationen aus Schnappsch�ussen zusammen. Bei TANGO werden nur der Anfangspunkt
und der Endpunkt einer Bewegung angegeben.
Die Basis des Systems bilden vier abstrakte Datentypen: location, image, path und transi-
tion.
Die location gibt die Position der darzustellenden Elemente in einem Koordinatensystem
an. Sie besteht aus einem Paar (x,y). Man kann sie mit verschiedenen Operationen mani-
pulieren (vgl. Abschnitt 3.2.2 ANIMDraw).
Der Datentyp image wird in zwei Bereiche aufgeteilt: primary image und composite image.
Das primary image repr�asentiert die Grundstruktur, die bearbeitet werden soll. Die Daten,
die zur Erstellung dienen, bestehen hierbei aus den locations der einzelnen Elemente, der
Darstellungsform (z. B. Rechtecke oder Kreise), sowie weiteren Informationen �uber Sicht-
barkeit und Farbe.
Das composite image ist f�ur weitere Details verantwortlich. Als Beispiel seien die Zahlen-
werte in den Rechtecken (Abbildung 5.1) aufgef�uhrt.
Der path gibt den Weg an, entlang dem eine Ver�anderung durchgef�uhrt werden soll. Wenn
zwei Objekte vertauscht werden sollen, so wird ein path erzeugt, in dem ihre locations und
die Art der Bewegung - auf gerader Linie oder bogenf�ormig - stehen. Auch beim Aufblinken
von Objekten wird ein Pfad ben�otigt. In diesem Fall enth�alt er nicht ihre locations sondern
ihren F�ullwert (vgl. Abschnitt 3.2.2 ANIMCompare). Zur Manipulation eines path stehen
viele Operationen zur Verf�ugung. Rotate erzeugt zu einem path den um die angegebene
Gradzahl gedrehten path.
Die transition ist f�ur die eigentlichen Aktionen zust�andig. Sie besteht aus einem transition
type, dem zugeh�origen image und dem path. Der transition type beschreibt die Art der
transition. Ein Beispiel w�are die Bewegung (TANGO TRANS TYPE MOVE).
Die aktuelle TANGO-Version ist in C geschrieben. Sie ist auf jeder UNIX-Ober �ache (damit
auch unter LINUX) installierbar. Da sie die Tools des X11-Window-Systems verwendet,
wird sie auch mit XTango bezeichnet.
Zu dem System geh�oren einige Animationen bekannter Algorithmen. Anhand dieser Bei-
spiele ist es m�oglich, neue Strukturen f�ur andere Verfahren zu erarbeiten.
In dieser Arbeit wird XTango mit OSF/Motif unterst�utzt. Es ist aber auch m�oglich, mit
einer Athena-Version zu arbeiten.
Wettl�aufe zwischen verschiedenen Algorithmen werden bei XTango nicht vorgesehen. Im
Zuge dieser Arbeit sind jedoch Animationen entstanden, die einen Vergleich zwischen den
11
2.4. XTANGO KAPITEL 2. ALGORITHMEN-ANIMATIONEN
Verfahren Sortieren durch Auswahl, Sortieren durch Einf�ugen und Bubblesort animieren.
Damit ist ein entscheidender Nachteil gegen�uber den Versionen von BALSA ausger�aumt
worden.
XTango ist eine freie Software und auf dem ftp-Server von cc.gatech.edu zu �nden.
12
Kapitel 3
Vom Algorithmus zur Animation
3.1 Kriterien
Die in den Abschnitten 5.1 bis 5.3 erl�auterten Darstellungsformen bilden die Grundlage
f�ur die meisten Algorithmen-Animationen im Bereich der klassischen Algorithmen. Beim
L�osen geometrischer Probleme ist es notwendig, andere Arten der Darstellung zu entwer-
fen.
Bevor man damit beginnt, eine Animation zu entwerfen, sollte man sich dar�uber klar wer-
den, wie man den Ablauf des Algorithmus darstellen will.
Zun�achst betrachtet man die Struktur, in der die Werte, auf die der Algorithmus zugreift,
gespeichert sind. Im Falle der klassischen Sortierverfahren ist dies in der Regel ein Array.
Man k�onnte folglich die Werte wie in Abbildung 3.1 darstellen. Allerdings ist die Aussa-
gekraft dieses Bildes nicht sehr hoch. Die Struktur der Speicherung ist zwar zu erkennen,
aber die Gr�o�e der Werte - was bei Sortierverfahren von au�erordentlicher Bedeutung ist
- wird erst bei genauerer Betrachtung deutlich. Die Darstellung der Werte als Balken oder
Punkte wird diesem Kriterium gerecht.
a: 15 2 43 17 4 8 47
Abbildung 3.1: Gespeicherte Daten in einem Array
Wenn die �au�ere Form der Animation fest liegt, kann man sich der inneren widmen. Man
mu� �uberlegen, welche Operationen des Algorithmus in Aktionen der Animation umgesetzt
werden sollen. Bei den klassischen Sortierverfahren sind das Vergleichen von Schl�usseln und
das Vertauschen die wesentlichen Gesichtspunkte. Sie bilden die Grundlage f�ur die Laufzeit-
absch�atzung der Algorithmen. Daher sollten sie in die visuelle Darstellung aufgenommen
werden.
Die Frage der Realisierung ist in diesen beiden F�allen leicht zu beantworten. Der Vergleich
13
3.2. BEISPIEL KAPITEL 3. VOM ALGORITHMUS ZUR ANIMATION
mehrerer Werte wird durch simultanes Aufblinken und das Vertauschen durch die Bewe-
gung der Objekte animiert.
Selbstverst�andlich gibt es noch weitere Operationen, die wichtig sind, um einen Algorith-
mus zu verstehen. Diese sind dann meistens nur bei sehr speziellen Verfahren notwendig
(z. B. die Wahl des Pivotelementes bei Quicksort). Es ist jedoch darauf zu achten, da�
die Anzahl der visualisierten Operationen nicht �uberhandnimmt. Ansonsten besteht die
M�oglichkeit, da� der Betrachter verwirrt und von den vielen blinkenden und sich bewegen-
den Objekten \erschlagen\ wird.
Desweiteren mu� sofort erkennbar sein, welche Aktion zu welcher Operation geh�ort. Dies
ist die schwierigste Arbeit eines Programmierers von Algorithmen-Animationen. Da er mit
dem zu visualisierenden Algorithmus sehr vertraut ist, verliert er leicht den Blick des neu-
tralen Betrachters. Dieser ist aber notwendig, um das Verfahren verst�andlich darzustellen.
Wenn nun diese Punkte gekl�art sind, kann man mit der eigentlichen Programmierung be-
ginnen.
3.2 Beispiel
Am Beispiel des Programmes \Sortieren durch Auswahl\ wird die Realisierung der in
Abschnitt 3.1 erarbeiteten Kriterien erl�autert. Zur Visualisierung dient das in Abschnitt 2.4
beschriebene XTango-System. Die Konstruktion der Animation besteht aus drei Teilen:
Der erste ist ANIM.c. Hierbei steht ANIM f�ur den Namen des Animationsprogrammes. In
ihm wird die Art der Animation festgelegt. Es handelt sich um ein Programmst�uck, in dem
der Algorithmus von \Sortieren durch Auswahl\ realisiert wird. Dabei werden Funktionen
aus ANIMscenes.c ben�otigt. Dies wird im Abschnitt 3.2.1 dargestellt.
Im zweiten Teil (ANIMscenes.c) be�nden sich die Funktionen, die in ANIM.c ben�otigt
werden und auf XTango basieren. Sie beschreiben die eigentlichen Animationsbefehle. Es
werden beispielsweise Rechtecke, Texte und ihre Bewegungswege de�niert. F�ur andere Ani-
mationen kann dieser Teil meist ohne �Anderungen �ubernommen werden. Auf diesen Bereich
wird in Abschnitt 3.2.2 eingegangen. F�ur interessierte Leser sei hier auch auf [8] verwiesen.
Der dritte Teil ist das XTango-Paket, das in xtango.o zusammengefa�t ist. Darin wird der
Aufbau des XTango-Windows beschrieben und die Funktionsweise der einzelnen Buttons
festgelegt. Auf dieses File soll hier nicht weiter eingegangen werden, da �Anderungen an
ihm das ganze XTango-Paket zerst�oren k�onnen. Falls der Leser sich n�aher mit den Imple-
mentierungsdetails befassen m�ochte, sei ihm angeraten, sich die Quellcodes von XTango
anzusehen.
14
KAPITEL 3. VOM ALGORITHMUS ZUR ANIMATION 3.2. BEISPIEL
3.2.1 ANIM.c
In ANIM.c wird das Programm \Sortieren durch Auswahl\ in C implementiert.
Nach dem Einlesen der zu sortierenden Daten wird der Reihe nach das i-kleinste Element,
i = 1; :::; N � 1, bestimmt und an die richtige Position gesetzt [6].
Die Funktionen ANIMInit, ANIMInput, ANIMDraw, ANIMCompare, ANIMExchange und
ANIMIn place werden in ANIMscenes.c de�niert und in Abschnitt 3.2.2 genauer erkl�art.
Sie dienen der Visualisierung des Verfahrens.
Erl�auterung der einzelnen Funktionen:
BEGIN Die Routine initialisiert das XTango-Paket.
Dabei werden die in Abschnitt 4.4 erl�auterten Buttons und die Dimensionen
des Fensters, in dem die Animationen ablaufen, de�niert.
Dieser Aufruf mu� am Anfang jedes XTango-Programmes stehen.
Init Die Funktion initialisiert die ben�otigte Grundstruktur.
Input An dieser Stelle werden die eingegebenen Daten in die XTango-Struktur
�ubergeben.
Draw Beim Aufruf dieser Funktion werden die Daten als Rechtecke - entsprechend
ihrer Gr�o�e skaliert - gezeichnet. Die Position der Objekte wird hier
gespeichert, um bei sp�ateren Aktionen sofort zur Verf�ugung zu stehen.
Compare Die Funktion vergleicht zwei Objekte miteinander. Dabei blinken die
entsprechenden Rechtecke mehrmals auf.
Exchange An dieser Stelle werden zwei Werte vertauscht. Bei dieser Animation
wurde ein bogenf�ormiger Weg f�ur die Objekte gew�ahlt.
In place Die Funktion ver�andert die Farbe eines Rechteckes und zeigt damit an,
da� dieses Objekt nicht mehr bewegt werden mu�.
END Die Routine beendet das XTango-Paket und schlie�t das XTango
Fenster. Dieser Aufruf mu� am Ende jedes XTango-Programmes stehen.
Die Aufrufe dieser Funktionen sind durch Fettdruck hervorgehoben.
Alle anderen Befehlszeilen werden f�ur den Sortieralgorithmus ben�otigt.
#include <stdio.h>
#include \xtango.h\
void ANIMInit(), ANIMInput(), ANIMDraw(), ANIMCompare(),
ANIMExchange(), ANIMIn place();
static NAME FUNCT fnc[ ]=
ff\Init\, 1, fVOID, (FPTR)ANIMInitgg,f\Input\, 1, fVOID, (FPTR)ANIMInputgg,f\Draw\, 1, fVOID, (FPTR)ANIMDrawgg,f\Compare\, 1, fVOID, (FPTR)ANIMComparegg,f\Exchange\, 1, fVOID, (FPTR)ANIMExchangegg,f\In place\, 1, fVOID, (FPTR)ANIMIn placeggg ;
15
3.2. BEISPIEL KAPITEL 3. VOM ALGORITHMUS ZUR ANIMATION
main()
fint n, i, j, min, count, temp, a[50];
TANGOalgoOp(fnc, \BEGIN\);
printf(\Input number of elements in arraynn\);scanf(\%d\,&n);
TANGOalgoOp(fnc, \Init\);
printf(\Enter the elementsnn\);for (count=0; count<n; ++count)
f/* Einlesen der zu sortierenden Elemente */
scanf(\%d\,&a[count]);
TANGOalgoOp(fnc, \Input\, a, count, a[count]);
gTANGOalgoOp(fnc, \Draw\, a, n);
for (i=0; i<n; ++i)
fmin = i;
for (j=i+1; j<n; ++j)
fTANGOalgoOp(fnc, \Compare\, a, j, a, min);
if (a[j] < a[min])
min = j;
gTANGOalgoOp(fnc, \Exchange\, a, i, a, min);
temp = a[min];
a[min] = a[i];
a[i] = temp;
TANGOalgoOp(fnc, \In place\, a, i);
gTANGOalgoOp(fnc, \END\);
g
F�ur Leser, die sich f�ur den C-Code des Programmes n�aher interessieren, m�ochte ich auf
allgemeine C-B�ucher verweisen.
16
KAPITEL 3. VOM ALGORITHMUS ZUR ANIMATION 3.2. BEISPIEL
3.2.2 ANIMscenes.c
Das File ANIMscenes.c besteht aus folgenden Funktionen:
void ANIMInit(); Initialisierung der Grundstruktur
void ANIMInput(); Verkn�upfung zwischen den eingegebenen Daten und der
XTango-Struktur
void ANIMDraw(); Erzeugen und Realisieren der graphischen Darstellung
void ANIMCompare(); Vergleichen zweier Objekte durch simultanes Aufblinken
void ANIMExchange(); Vertauschen zweier Objekte
void ANIMIn place(); Farb�anderung eines Objektes, das seinen Endpunkt erreicht hat
In diesem File wird auf die XTango-Befehle zur�uckgegri�en. Eine genaue Beschreibung der
XTango-Funktionen und der zu �ubergebenden Variablen ist in Anhang C zu �nden.
In den ersten Zeilen dieses Programmteils steht, welche Files eingebunden werden. Um die
XTango-Umgebung nutzen zu k�onnen, ben�otigt man xtango.h, w�ahrend stdio.h f�ur die Ein-
und Ausgabe unerl�a�lich ist.
#include<xtango.h>
#include<stdio.h>
Im Folgenden werden die Funktionen de�niert, die im Hauptprogramm relevant sind.
/***** Initialisieren *****/
void
ANIMInit()
fASSOCinit();
ASSOCmake(\DATA\,2);
ASSOCmake(\TEXT\,1);
g
Die Routine ASSOCinit reserviert die Verbindungen mit den Namen ID (2 Parameter),
ID3 (3 Parameter) und IMAGE AT (2 Parameter) und initialisiert das sogenannte ASSOC-
Paket. Es stellt eine Verbindung zwischen den Daten des Hauptprogrammes und den Ob-
jekten der Animation dar. Alle Funktionen, die mit der Vorsilbe ASSOC beginnen, geh�oren
zu diesem Paket. ASSOCmake(\DATA\,2) reserviert eine Verbindung mit dem Namen DA-
TA, die zwei Parameter besitzt. Der eine Parameter repr�asentiert in diesem Beispiel die
Positionsangabe im Array, der andere den Wert an dieser Position.
/***** �Ubergabe der Daten *****/
void
ANIMInput(id,index,val)
int id;
int index;
17
3.2. BEISPIEL KAPITEL 3. VOM ALGORITHMUS ZUR ANIMATION
int val;
fASSOCstore(\DATA\,id,index,val);
g
ASSOCstore weist der Struktur DATA die zu animierenden Daten zu. Hierbei entspricht
id dem Arrayname, index der Position und val dem Wert.
/***** Zeichnen der Animation *****/
void
ANIMDraw(id,n)
int id; /* Name des Arrays */
int n; /* Gr�o�e des Arrays */
fdouble width; /* Variablen */
int i;
int item;
int max val;
int vals[50];
double yvals[50];
TANGO LOC center;
TANGO IMAGE rect, text;
TANGO PATH path;
TANGO TRANS delay;
double x, y;
char str[5];
TANGO COLOR c;
#de�ne SX 0.1
#de�ne SY 0.9
#de�ne SIDE 0.8
width = SIDE/(2.0*(double)n); /* Breite der Rechtecke */
max val = 0;
for (i=0; i<n; ++i) /* Bestimme die max. H�ohe */
fif ((item = (int)ASSOCretrieve(\DATA\,id,i))>max val)
max val = item;
vals[i] = item; /* Speichern der Daten in lokalem Array */
g
for (i=0; i<n; ++i) /* Skalierung der Elemente */
fyvals[i] = (double)vals[i] / (double)max val;
g
18
KAPITEL 3. VOM ALGORITHMUS ZUR ANIMATION 3.2. BEISPIEL
/* Erzeugen des Primary Image */
TWISTcreate image array(NULL,id,n,TANGO IMAGE TYPE RECTANGLE,
1,0,SX,SY,NULL,width,yvals,SIDE,width,1,TANGO COLOR GREEN,0.0);
for (i=0; i<n; ++i)
f/* Composite Images werden erzeugt */
rect = (TANGO IMAGE) ASSOCretrieve(\ID\,id,i);
center = TANGOimage loc(rect,TANGO PART TYPE C);
TANGOloc inquire(center,&x,&y);
sprintf(str,\%d\,vals[i]);
text = TANGOimage create(TANGO IMAGE TYPE TEXT,x,y,1,
TANGO COLOR BLACK,\�xed\,str,1);
ASSOCstore(\TEXT\,rect,text);
g
path = TANGOpath null(10);
delay = TANGOtrans create(TANGO TRANS TYPE DELAY,text,path);
TANGOtrans perform(delay);
TANGOpath free(1,path);
TANGOtrans free(1,delay);
g
Zun�achst werden die Elemente auf einen bestimmten Bereich skaliert. Danach wird das
primary image erzeugt, wobei die Objekte als Rechtecke dargestellt werden. Dies geschieht
mit dem Befehl TWISTcreate image array. Die Variablen, die �ubergeben werden, bestim-
men beispielsweise die Gr�o�e und die Position der Objekte (vgl. Anhang C). Die composite
images realisieren die Zahlen, die in der Animation in jedem Rechteck zu sehen sind. Sie
werden mit dem Aufruf TANGOimage create erzeugt und jedem Rechteck einzeln zugewie-
sen. Der path und die transition sorgen daf�ur, da� die images gezeichnet werden.
/***** Simultanes Aufblinken zweier Objekte *****/
void
ANIMCompare(id1,n1,id2,n2)
int id1; /* Name des Array von Objekt 1 */
int n1; /* Position von Objekt 1 */
int id2; /* Name des Array von Objekt 2 */
int n2; /* Position von Objekt 2 */
fTANGO IMAGE rect1,rect2;
TANGO PATH path,�llpath;
TANGO TRANS �ll[2],compose;
double ash[4];
rect1 = (TANGO IMAGE) ASSOCretrieve(\ID\,id1,n1);
rect2 = (TANGO IMAGE) ASSOCretrieve(\ID\,id2,n2);
19
3.2. BEISPIEL KAPITEL 3. VOM ALGORITHMUS ZUR ANIMATION
ash[0] = 1.0; /* hal�ll */
ash[2] = -1.0; /* outline */
ash[1] = ash[3] = 0.0;
path = TANGOpath create(4, ash, ash);
�llpath = TANGOpath iterate(path,4.0);
�ll[0] = TANGOtrans create(TANGO TRANS TYPE FILL,rect1,�llpath);
�ll[1] = TANGOtrans create(TANGO TRANS TYPE FILL,rect2,�llpath);
compose = TANGOtrans compose(2,�ll[0],�ll[1]);
TANGOtrans perform(compose);
TANGOpath free(2,path,�llpath);
TANGOtrans free(3,�ll[0],�ll[1],compose);
g
Zun�achst werden die beiden Rechtecke bestimmt, auf die die Operation angewandt wer-
den soll. Der Befehl ASSOCretrieve stellt die Verbindung zu ihnen her. Im path wird
der Grad der F�ullung der Objekte festgelegt. Er wird mit dem Befehl TANGOpath create
erzeugt. Da er bisher jedoch nur ein einmaliges Aufblinken beschreibt, wird er mit TAN-
GOpath iterate vervielfacht. Mit diesem neuen path werden zwei transitions de�niert. Mit
TANGOtrans compose werden diese beiden verkn�upft und mit TANGOtrans perform aus-
gef�uhrt.
/***** Vertauschen zweier Objekte *****/
void
ANIMExchange(id1,n1,id2,n2)
int id1;
int n1;
int id2;
int n2;
fTANGO IMAGE rect1,rect2,text1,text2;
TANGO LOC loc1,loc2;
TANGO PATH path1,path2;
TANGO TRANS move[4],compose;
rect1 = (TANGO IMAGE) ASSOCretrieve(\ID\,id1,n1);
rect2 = (TANGO IMAGE) ASSOCretrieve(\ID\,id2,n2);
loc1 = TANGOimage loc(rect1,TANGO PART TYPE SW);
loc2 = TANGOimage loc(rect2,TANGO PART TYPE SW);
text1 = (TANGO IMAGE) ASSOCretrieve(\TEXT\,rect1);
text2 = (TANGO IMAGE) ASSOCretrieve(\TEXT\,rect2);
path1 = TANGOpath motion(loc1,loc2,TANGO PATH TYPE CLOCKWISE);
path2 = TANGOpath rotate(path1,180);
move[0] = TANGOtrans create(TANGO TRANS TYPE MOVE,rect1,path1);
move[1] = TANGOtrans create(TANGO TRANS TYPE MOVE,text1,path1);
move[2] = TANGOtrans create(TANGO TRANS TYPE MOVE,rect2,path2);
20
KAPITEL 3. VOM ALGORITHMUS ZUR ANIMATION 3.2. BEISPIEL
move[3] = TANGOtrans create(TANGO TRANS TYPE MOVE,text2,path2);
compose = TANGOtrans compose(4,move[0],move[1],move[2],move[3]);
TANGOtrans perform(compose);
ASSOCstore(\ID\,id1,n1,rect2); /* reset assocs due to exchange */
ASSOCstore(\ID\,id2,n2,rect1);
TANGOpath free(2,path1,path2);
TANGOtrans free(5,move[0],move[1],move[2],move[3],compose);
g
Neben den Rechtecken werden auch die als Text dargestellten Zahlenwerte bestimmt, denn
beide zusammen bilden das Objekt, das bearbeitet wird. Danach werden die locations der
zu vertauschenden Objekte und die entsprechenden paths erzeugt. Mit deren Hilfe k�onnen
die transitions de�niert werden, die f�ur die Vertauschung zust�andig sind.
/***** F�ullen eines Objektes *****/
void
ANIMIn place(id,n)
int id;
int n;
fTANGO IMAGE rect,text;
TANGO PATH path,col;
TANGO TRANS �ll,color,clean;
double f = 1.0;
rect = (TANGO IMAGE) ASSOCretrieve(\ID\,id,n);
path = TANGOpath create(1,&f,&f);
�ll = TANGOtrans create(TANGO TRANS TYPE FILL,rect,path);
TANGOtrans perform(�ll);
text = (TANGO IMAGE) ASSOCretrieve(\TEXT\,rect);
col = TANGOpath color(TANGO COLOR WHITE);
color = TANGOtrans create(TANGO TRANS TYPE COLOR,text,col);
TANGOtrans perform(color);
clean = TANGOtrans create(TANGO TRANS TYPE REFRESH,NULL,path);
TANGOtrans perform(clean);
TANGOpath free(1,path);
TANGOtrans free(1,�ll);
g
Zuerst wird das Rechteck bestimmt, das gef�ullt werden soll. Der path wird hier nur f�ur
eine Farb�anderung ben�otigt, die durch die transition ausgef�uhrt wird. Im Anschlu� wird
noch die Farbe des entsprechenden Zahlenwertes ge�andert. Mit der transition clean wird
sichergestellt, da� Pixel, die von den vorherigen images stammen, gel�oscht werden.
21
3.2. BEISPIEL KAPITEL 3. VOM ALGORITHMUS ZUR ANIMATION
22
Kapitel 4
Das Benutzerinterface
Das in dieser Arbeit beschriebene Multimedia-Dokument ist ein Fenster auf der X11 Ober-
�ache einer UNIX-Rechners. Es wurde unter der Verwendung von OSF/Motif programmiert
und ist im Wesentlichen in folgende drei Bl�ocke aufgeteilt:
Inhaltsverzeichnis, Textbereich und Filmsequenzen.
Diese werden nun genauestens erl�autern.
4.1 Inhaltsverzeichnis
Abbildung 4.1: Steuerung der Multimedia-Umgebung
Die in Abbildung 4.1 gezeigten Buttons dienen der Navigation durch das Multimedia-
Dokument. Sie haben �ahnliche Funktionen wie das Inhaltsverzeichnis in einem Buch und
23
4.1. INHALTSVERZEICHNIS KAPITEL 4. DAS BENUTZERINTERFACE
werden durch das Klicken mit der linken Maustaste aktiviert. Im folgenden Abschnitt wer-
den die E�ekte der einzelnen Buttons konkret beschrieben.
Wie man Abbildung 4.1 entnehmen kann, wurde die Untergliederung des Buches in Kapitel
und Abschnitte durch verschiedene Schrifttypen und Schriftarten hervorgehoben. Dadurch
kann der Benutzer sehr leicht die Struktur des Buches erfassen und die Zugeh�origkeit ein-
zelner Themen erkennen.
Die Funktionsweise der Buttons wird im Wesentlichen in zwei Bereiche aufgeteilt. Zum
einen dienen sie dem Aufschlagen der entsprechenden Seite, zum anderen wird bei man-
chen ein Untermen�u erzeugt, mit dessen Hilfe dann die zugeh�origen Animationen gesteuert
werden k�onnen.
\2 Sortieren\, \2.1 Elementare Sortierverfahren\ und \2.2 Quicksort\ haben lediglich die
Funktion, die entsprechende Seite des Buches anzuzeigen. Da es sich bei diesen Abschnit-
ten um einf�uhrende Texte handelt, die noch nicht auf spezielle Sortierverfahren eingehen,
wurde auf Animationen verzichtet. (Sie w�urden zu diesem Zeitpunkt den Benutzer nur
verwirren und w�aren v�ollig aus dem Zusammenhang gerissen.) Damit aber dennoch die
M�oglichkeit besteht, sich zu jeder Zeit einen kleinen �Uberblick zu verscha�en, existieren
einige Filmsequenzen, auf die ich in Abschnitt 4.3 n�aher eingehen werde.
Abbildung 4.2: Das Untermen�u
Die Buttons \2.1.1 Sortieren durch Auswahl\, \2.1.2 Sortieren durch Einf�ugen\, \2.1.4
Bubblesort\ und \2.2.1 Quicksort: Sortieren durch rekursives Teilen\ haben die gleichen
Untermen�us (vgl. Abbildung 4.2). Diese unterst�utzen die folgende Auswahl:
Im oberen Bereich wird die Art der Animation bestimmt. Die Darstellung der zu sor-
tierenden Werte als Balken ist der Standardwert. Die n�achste M�oglichkeit besteht darin,
die Werte als Punkte im zweidimensionalen Raum zu positionieren. Die eine Dimension
beschreibt die Position, die andere die Gr�o�e des Wertes. Der dritte Button ist besonders
f�ur diejenigen Benutzer interessant, die sich die Animation anhand des Programmtextes
24
KAPITEL 4. DAS BENUTZERINTERFACE 4.1. INHALTSVERZEICHNIS
verdeutlichen wollen. Das hei�t, w�ahrend das Verfahren l�auft, wird die aktuelle Programm-
zeile hervorgehoben.
Der untere Bereich unterst�utzt die Eingabe der Werte, die in den Animationen darge-
stellt werden sollen. Hierbei hat man die Auswahl zwischen der \Computereingabe\, der
\Benutzereingabe\ und einem \Zufallsgenerator\. Die Computereingabe verwendet Daten,
die f�ur die aktuelle Animation besonders geeignet sind. W�ahrend bei der Balkenanimati-
on beliebige Werte bearbeitet werden k�onnen, mu� bei der Punktvariante darauf geachtet
werden, da� der h�ochste Wert kleiner ist als die Anzahl der Elemente. Falls bei der Be-
nutzereingabe dieses Kriterium mi�achtet wird, macht das Programm nach Bet�atigen des
\OK\ Buttons darauf aufmerksam und bearbeitet statt dessen die Standardwerte f�ur die
Punktanimation. Mit dem Zufallsgenerator hat der Benutzer die M�oglichkeit, k Werte zwi-
schen 0 und k zu erzeugen, wobei k eine ganze positive Zahl ist. Hierbei verwende ich den
Algorithmus von Lehmer1, da viele Zufallsgeneratoren bei jedem Aufruf auf die Rechner-
zeit zugreifen. Dies f�uhrt zu keiner gleichm�a�igen Verteilung der Werte.
Der \OK\ Button best�atigt die get�atigte Wahl. Mit \Cancel\ kann man, ohne eine Anima-
tion zu starten, zum Hauptprogramm zur�uckkehren. \Help\ informiert den Benutzer �uber
die hier aufgef�uhrten M�oglichkeiten.
In Abbildung 4.1 sind jedoch noch andere Kn�opfe vorhanden, die bisher nicht erw�ahnt
wurden. \2.1.3 Shellsort\ hat ein �ahnliches Untermen�u wie das oben genannte. Bei dem
Verfahren Shellsort ist es aber nicht sinnvoll, eine Punktanimation zur Verf�ugung zu stel-
len. Diese Variante w�urde dem Benutzer nicht den geringsten Einblick in den Algorithmus
geben, da die vorsortierten Teilfolgen in einer Punktmenge kaum erkennbar sind. Auch bei
\2.2.2 Quicksort-Varianten\ habe ich auf diese Art der Animation verzichtet. Die unter-
schiedliche Wahl des Pivotelementes k�onnte bei der Punktdarstellung nur von Quicksort-
experten erkannt werden.
Die Eingabeart und das Best�atigen erfolgen auf die schon erkl�arte Weise.
\2.3 Heapsort\ bietet im Bereich der Wahl der Animation ein v�ollig anderes Bild. Eine reine
Balken- oder gar eine Punktvariante zu verwenden, w�are hier nicht angebracht. Vielmehr
habe ich mich entschlossen, eine gemischte Balken-Baum-Animation zu programmieren.
Die Balken stellen die Werte dar, wie sie im Array gespeichert sind. Der Baum dagegen ist
die Heapstruktur, die das Verfahren ben�otigt. F�ur eine schnelle �Ubersicht stelle ich dem
Benutzer auch eine reine Baumanimation zur Verf�ugung, die nat�urlich auch gemischt mit
dem Programmtext vorliegt.
Bei der Eingabeart und der Best�atigung habe ich auch hier keine �Anderungen vorgenom-
men.
Falls der Benutzer ein Untermen�u noch nicht beendet hat und ein neues w�ahlt, so f�uhrt
dies zu keinen Komplikationen. Das alte wird dann einfach vom Programm geschlossen.
1Mit diesem Verfahren werden Pseudozufallszahlen erzeugt. Die der Berechnung zugrundeliegenden
Werte sind so gew�ahlt, da� die Zufallszahlen eine bessere Verteilung aufweisen, als wenn sie mit anderen
Zufallsgeneratoren erzeugt werden.
25
4.2. TEXTBEREICH KAPITEL 4. DAS BENUTZERINTERFACE
4.2 Textbereich
Der Textbereich ist eine gro�e wei�e Fl�ache neben den Buttons des Inhaltsverzeichnisses.
In ihm werden die in Abschnitt 4.1 erw�ahnten Kapitel dargestellt. Das hei�t, hier erscheint
die aktuelle Seite. Bei diesem Multimedia-Dokument wurden einige Abschnitte aus dem
Buch \Algorithmen und Datenstrukturen\ [6] verwendet. Der Text ist als Postscript�le
vorhanden.
Da mir der TEX-Code des Buches vorlag, konnte ich eine �Anderung vornehmen, die dem
Benutzer sehr zugute kommt. Texte werden in der Regel mit einer Schriftgr�o�e von zehn
oder zw�olf Punkten dargestellt. Bei einem Ausdruck mag dies eine ideale Gr�o�e sein. Wenn
man den Text aber auf dem Bildschirm lesen will, so ist das Schriftbild zu klein. Aus diesem
Grund habe ich die Schriftgr�o�e bei diesem Text�le ge�andert. Nun kann der Benutzer ohne
Anstrengungen den Text lesen.
Beim Starten des Programmes wird die erste Seite des Postscript�les in den Textbereich
geladen. Hierf�ur verwende ich ein Postscripttool (psselect) und das Programm Ghostscript,
das unter UNIX zur Verf�ugung gestellt wird. Psselect wird mit der Option -pX gestartet,
wobei X f�ur die zu ladende Seite steht. Ghostscript erzeugt aus der Postscript-Seite eine
Pixmap, die anschlie�end im Textbereich erscheint.
Der Benutzer hat nun die M�oglichkeit, �uber das Inhaltsverzeichnis oder durch seitenweises
Bl�attern zu der gew�unschten Seite zu gelangen. Hierf�ur stehen ihm die Buttons \Previous\,
\Next\, \Previous -5\, \Next +5\, \Previous -10\ und \Next +10\ zur Verf�ugung. Man
kann also f�unf bzw. zehn Seiten �uberspringen.
Abbildung 4.3: Steuerung zum Umbl�attern der Seiten
Wenn eine Seite mit Hilfe dieser Optionen aufgeschlagen wird, so erscheint kein Popup-
men�u. Dies l�a�t sich nur durch die in Abschnitt 4.1 de�nierten Buttons erreichen.
Auf einigen Seiten des Textes erscheinen gewisse Stellen von einem roten Rechteck um-
randet. Dabei handelt es sich um Verweise an andere Stellen des Multimedia-Dokumentes.
Wenn man in diesen Bereich mit der linken Maustaste klickt, so wird die Seite, auf die
verwiesen wurde, geladen. (Die Verankerung der Links im Text wird in Abschnitt 6.3 be-
schrieben.)
Falls der Textbereich nicht den ganzen Text darstellt, was bei kleinen Bildschirmen oder
durch �Andern der Fenstergr�o�e durchaus m�oglich ist, so existieren rechts und unterhalb
des Bereiches Scrollbars, mit deren Hilfe man den Text verschieben kann.
26
KAPITEL 4. DAS BENUTZERINTERFACE 4.3. FILMSEQUENZEN
4.3 Filmsequenzen
In Zusammenarbeit mit dem Institut f�ur den Wissenschaftlichen Film und dem Institut
f�ur Informatik ist ein Film �uber das Thema \Klassische Algorithmen\ entstanden. Hierbei
wurden die von mir programmierten Animationen zur Visualisierung der verschiedenen
Verfahren verwendet. Die fertigen Filmsequenzen wurden mir vom Institut f�ur den Wis-
senschaftlichen Film zur Verf�ugung gestellt.
Da sie im MPEG-Format gespeichert sind, ben�otigt man einen Viewer, der dieses Format
verarbeiten kann. Auf den meisten UNIX-Rechnern ist ein solcher Viewer vorhanden. Da-
her habe ich darauf verzichtet, in mein Programm-Paket einen solchen einzubinden. Bei
der Installation der Programme wird der Benutzer gefragt, welchen MPEG-Viewer er ver-
wendet.
Man hat in diesem Multimedia-Dokument nun die M�oglichkeit, zwischen den einzelnen
Filmsequenzen auszuw�ahlen. Beim Aufruf des Programmes erscheint unter den Buttons
f�ur das Durchbl�attern der Textseiten der in Abbildung 4.4 dargestellte Bereich. Mit dem
Button \Play\ wird die aktuelle Filmsequenz gestartet und mit \Stop\ beendet. Nach
nochmaligem Dr�ucken von \Play\ beginnt die Simulation wieder von vorne.
Aktuelle Filmsequenz:
Einf�uhrung in die
Klassischen Sortierverfahren
Play Stop
Abbildung 4.4: Steuerung der Filmsequenzen
Wenn der Benutzer den linken Mausbutton im Bereich \Einf�uhrung in die Klassischen
Sortierverfahren\ dr�uckt, erscheint ein Popup-Men�u mit allen zur Verf�ugung stehenden
Filmen. Darin kann man den gew�unschten ausw�ahlen und mittels \Play\ starten. Der Titel
dieser Wahl steht nun an der Stelle von \Einf�uhrung in die Klassischen Sortierverfahren\.
Dadurch erkennt man, welche Filmsequenz ausgew�ahlt wurde.
27
4.4. OBERFL�ACHE VON XTANGO KAPITEL 4. DAS BENUTZERINTERFACE
4.4 Ober �ache von XTango
Abbildung 4.5: Die Benutzerober �ache von XTango
28
KAPITEL 4. DAS BENUTZERINTERFACE 4.4. OBERFL�ACHE VON XTANGO
Die Bedeutung der einzelnen Buttons:
Der Fensterbereich �uber der Animation wird nach links verschoben.
Das hei�t, die Animation wandert nach rechts.
Der Fensterbereich �uber der Animation wird nach rechts verschoben.
Der Fensterbereich �uber der Animation wandert nach oben.
Der Fensterbereich �uber der Animation wandert nach unten.
in Die Animation wird vergr�o�ert.
out Die Animation wird verkleinert.
run animation 1 Die Animation wird gestartet.
pause Die Animation wird angehalten.
unpause Die Animation f�ahrt an der Stelle fort, an der sie unterbrochen wurde.
patterns 2 colors Diese Option verwandelt die Farben in verschiedene Muster.
(Default Wert)
�ll styles Bei dieser Option werden die Farben ignoriert und die Objekte
gef�ullt dargestellt.
mode 3 by frame Die Animation l�auft langsam ab. (Default Wert)
by scenes Die Animation l�auft schneller ab.
none Die Animation l�auft sehr schnell ab; dabei k�onnen L�ocher
in der Animation auftreten.
debug Der Debugger gibt die Funktionsaufrufe und die �ubergebenen Werte aus.
o� Der Debugger wird deaktiviert. (Default Wert)
on Der Debugger wird aktiviert.
refresh Der Fensterbereich wird neu gezeichnet. Dadurch werden Bereiche,
die von anderen Fenstern �uberlagert waren, wiederhergestellt.
quit Das Programm wird beendet und das XTango-Fenster geschlossen.
Die Scrollbar (in Abbildung 4.5 vertikal am rechten Rand) steuert
die Geschwindigkeit der Animation. Je weiter oben der Balken ist,
desto schneller l�auft die Animation ab.
1Der Button wechselt nach dem Dr�ucken von \run animation\ nur noch zwischen \pause\ und
\unpause\.2Dieser Button tritt nur bei monochromer Ausgabe auf.3Der Unterschied tritt nur bei sehr langsamen Rechnern auf.
29
4.4. OBERFL�ACHE VON XTANGO KAPITEL 4. DAS BENUTZERINTERFACE
30
Kapitel 5
Darstellungsarten
5.1 Balkendarstellung
5.1.1 Standard
Bei dieser Art der Animation habe ich die zu sortierenden Werte als Balken dargestellt.
Zuerst werden die Elemente auf den Bereich 0.0 bis 1.0 skaliert. Das gr�o�te Element nimmt
den Wert 1.0 an. Entsprechend der Anzahl wird anschlie�end die Breite und die Position
der Rechtecke berechnet. Sie werden nach dem Start angezeigt. In der Mitte erscheint
dabei der zugeh�orige Wert. Das gew�ahlte Verfahren sorgt nun daf�ur, da� die Werte sortiert
werden. Das Vergleichen stelle ich durch das Aufblinken der beiden Rechtecke dar. Wenn
zwei Elemente vertauscht werden, wandern sie auf einem halbkreisf�ormigen Pfad. Das linke
der beiden Elemente bewegt sich oberhalb, das rechte unterhalb einer gedachten Linie, auf
der die Rechtecke stehen. Sobald ein Element seine endg�ultige Position erreicht hat, wird
es gef�ullt dargestellt.
Abbildung 5.1: Vor dem Sortieren Abbildung 5.2: Nach dem Sortieren
31
5.1. BALKENDARSTELLUNG KAPITEL 5. DARSTELLUNGSARTEN
5.1.2 Variationen
Bei dem Verfahren Quicksort habe ich die Standardvariante mit einigen Zus�atzen verse-
hen, um die verschiedenen Operationen, die ben�otigt werden, klarer darstellen zu k�onnen.
Die Skalierung und Positionierung der Rechtecke habe ich �ubernommen. Da bei Quicksort
die Wahl des Pivotelementes sehr wichtig ist, stelle ich es gr�un gef�ullt dar. Dies wird in
Abbildung 5.4 deutlich. Leider kann es in den Abbildungen 5.4 { 5.6 nur grauwertig darge-
stellt werden. Die beiden Zeiger, die nun �uber die restlichen Werte wandern, habe ich als
kleine Balken unter den eigentlichen Rechtecken positioniert. Zur besseren Unterscheidung
wurde der rechte gr�un (in Abbildung 5.4 gezackt) und der linke schwarz gef�arbt. Der rechte
Zeiger wandert nun nach links, der linke nach rechts, bis sie �ubereinander laufen. Dann
wird das Pivotelement an der richtigen Stelle positioniert und blau gef�arbt. Der rekursive
Aufruf wird durch eine Box dargestellt. Das hei�t, die Elemente, die im rekursiven Aufruf
behandelt werden, sind von einer schwarzen Linie umrandet, was in Abbildung 5.5 deut-
lich wird. Bei mehreren rekursiven Aufrufen kann man dadurch die Schachtelung bzw. die
Rekursionstiefe erkennen (vgl. Abbildung 5.6).
Wenn das Sortierverfahren geendet hat, wird auch die Wahl der Pivotelemente deutlich.
Dies ist besonders bei dem randomisierten Quicksort interessant.
Abbildung 5.3: Vor dem Sortieren Abbildung 5.4: Vor dem Aufteilungsschritt
Die abnehmenden Inkremente spielen bei dem Verfahren Shellsort eine wichtige Rol-
le. Daher habe ich auch in diesem Fall einige Ver�anderungen gegen�uber der Standard-
Balkenanimation vorgenommen. Es ist wichtig, welches der aktuelle Inkrementwert ist.
Dieser erscheint in der linken oberen Ecke der Animation. Die Gr�o�e der Balken wurde
reduziert, das hei�t, das gr�o�te Element wird nicht mehr auf den Wert 1.0, sondern auf 0.3
skaliert. Auch die Vergleichs- und Vertauschoperationen habe ich abge�andert. Die Recht-
32
KAPITEL 5. DARSTELLUNGSARTEN 5.1. BALKENDARSTELLUNG
Abbildung 5.5: Rekursiver Aufruf Abbildung 5.6: Nach dem Sortieren
ecke blinken nicht mehr auf. Sie wandern nach unten. So wird es f�ur den Benutzer sofort
ersichtlich, ob die zu vergleichenden Elemente bereits eine dem Inkrement entsprechend
vorsortierte Folge bilden. In der Abbildung 5.7 wird eine Teilfolge mit Inkrement 3 bear-
beitet, so da� sie in Abbildung 5.8 sortiert vorliegt. Beim Vertauschen habe ich auf den
halbkreisf�ormigen Pfad verzichtet. Stattdessen werden die Elemente einfach nach rechts
bzw. nach links verschoben.
Abbildung 5.7: Teilfolge wird hervorgehoben Abbildung 5.8: Teilfolge wurde sortiert
33
5.2. PUNKTDARSTELLUNG KAPITEL 5. DARSTELLUNGSARTEN
5.2 Punktdarstellung
Mit der Punktdarstellung erh�alt man eine Art der Animation, die es erm�oglicht, das Sor-
tieren gro�er Datenmengen zu visualisieren. Beim Verfahren Quicksort kann der Benutzer
dabei die rekursive Abarbeitung erkennen und bei Bubblesort wird das Aufsteigen der
gro�en Elemente besonders deutlich. Die Punktdarstellung folgt dem Prinzip, die zu sor-
tierenden Werte entsprechend ihrer Gr�o�e (x-Koordinate) und ihrer Position im Array
(y-Koordinate) darzustellen. Durch diese Angaben wird jeder Punkt genau bestimmt, wie
in Abbildung 5.9 zu erkennen ist. Die Ver�anderungen, die durch die Sortierverfahren ein-
treten, werden sofort angezeigt. Am Ende der Animation sieht man die Punkte von links
unten nach rechts oben aufgereiht (vgl. Abbildung 5.10).
Abbildung 5.9: Vor dem Sortieren Abbildung 5.10: Nach dem Sortieren
5.3 Baumdarstellung
Eine Baumstruktur wird bei den klassischen Sortierverfahren kaum ben�otigt. Nur im Falle
von Heapsort ist es von Vorteil, auf diese Darstellungsart zur�uckgreifen zu k�onnen. Da die
zu sortierenden Elemente in einem Array vorliegen, kann man jedem Element sofort seine
Position im Heap zuordnen. Man mu� nur zuvor die H�ohe des Heaps bestimmen. Diese
ist aber durch log(#Elemente) gegeben. Daraus l�a�t sich ein Heap konstruieren, der den
Animationsbereich optimal ausf�ullt.
Die Vergleichsoperationen werden, wie schon bei der Balkendarstellung, durch simultanes
Aufblinken realisiert. Zwei Objekte werden miteinander vertauscht, indem sie einer gedach-
ten Linie zwischen ihnen folgen.
Ist ein Heap hergestellt, dann be�ndet sich das gr�o�te Element an der Wurzel. Dieses wan-
dert nun an den unteren Rand des Animationsbereiches und damit aus der Heapstruktur
34
KAPITEL 5. DARSTELLUNGSARTEN 5.3. BAUMDARSTELLUNG
heraus (vgl. Abbildung 5.12). Danach nimmt das Element, das im Heap im untersten Ni-
veau und ganz rechts steht, den Platz an der Wurzel ein. Sofort wird die Heapbedingung
wieder hergestellt und der n�achste Wert kann den Heap verlassen.
Abbildung 5.11: Positionierung der Ele-
mente
Abbildung 5.12: Ausgabe des maxima-
len Elementes
Zur besseren Verdeutlichung des Verfahrens Heapsort habe ich mich nicht auf eine rei-
ne Baumdarstellung beschr�ankt, sondern sie mit einer Balkendarstellung kombiniert. Das
hei�t, ich nutze nicht den vollst�andigen Raum f�ur den Heap. Diesem wird die linke H�alfte
des Animationsbereiches zugewiesen, w�ahrend rechts die Operationen am Array dargestellt
werden. Hierbei greife ich auf die in Abschnitt 5.1 erl�auterte Balkendarstellung zur�uck.
Abbildung 5.13: Vor dem Sortieren Abbildung 5.14: Nach dem Sortieren
35
5.4. ANIMATION MIT PROGRAMMTEXT KAPITEL 5. DARSTELLUNGSARTEN
5.4 Animation mit Programmtext
Um die verschiedenen Sortierverfahren dem Benutzer n�aherzubringen, habe ich eine wei-
tere Darstellungsform der Animationen programmiert. Dabei m�ochte ich die Operationen,
die bei den Verfahren ablaufen, im Programmtext aufzeigen. Diesen habe ich in keiner fe-
sten Programmiersprache gehalten, sondern die Algorithmen in Pseudo-Pascal formuliert.
W�ahrend nun eine Operation in der Animation ausgef�uhrt wird - sei es nun eine Balken-
oder eine Baumdarstellung - erscheint der aktuelle Programmtext rot. So kann man genau
das Verfahren verfolgen. Selbstverst�andlich wird nicht jede Befehlszeile markiert. Es w�are
nicht sinnvoll, die BEGIN- und END-Zeilen jedesmal aufblinken zu lassen. Deshalb habe
ich mich auf die wesentlichen Operationen beschr�ankt - wie zum Beispiel das Vertauschen
oder das Vergleichen.
Abbildung 5.15: Bubblesort mit Programmtext
36
Kapitel 6
Erweiterungen und Ver�anderungen
Meine Umgebung zur Steuerung von Multimedia-Dokumenten soll nicht nur auf das Bei-
spiel klassischer Sortierverfahren beschr�ankt bleiben. Deshalb m�ochte ich in den folgenden
Abschnitten erl�autern, wie man mit schon kleinen �Anderungen ein Dokument f�ur ande-
re Bereiche erstellen kann. Diese Ver�anderungen m�ussen am Programm sortieren.c (vgl.
Anhang A) vorgenommen werden.
6.1 Inhaltsverzeichnis
Das Inhaltsverzeichnis stellt das wichtigste Steuerungsinstrument dieses Multimedia-Doku-
mentes dar. Es ist auch relativ einfach, dieses zu ver�andern. In der Funktion initInhalt(),
die am Ende des Programmes steht, wird das Inhaltsverzeichnis initialisiert.
Zun�achst wird die Anzahl der Buttons anhand der Variablen maxbutton festgelegt. Da-
nach werden die verschiedenen Popupmen�us erl�autert. Darauf werde ich in Abschnitt 6.2
zur�uckkommen.
button[0].text=\2. Sortieren\; /* Button-Text * /
button[0].level=0; /* Schriftart */
button[0].page=1; /* passende Seite */
button[0].menue=0; /* Popup Men�u */
button[0].verzeichnis=NULL; /* Verzeichnis, in dem
die Animationen sind */
Jeder Button besteht aus f�unf Komponenten:
1. text: Hier steht in Anf�uhrungszeichen der Text, der im Button erscheinen soll.
2. level: �Uber den Level wird die Schriftgr�o�e gesteuert. Man kann damit die Struktur von
Kapiteln und Abschnitten verdeutlichen. Es stehen die Werte 0{4 zur Verf�ugung, wobei 0
f�ur die gr�o�te Schrift steht.
37
6.2. POPUPMEN�US KAPITEL 6. ERWEITERUNGEN UND VER�ANDERUNGEN
3. page: Dies ist die Seitennummer, die zu dieser �Uberschrift geh�ort.
4. menue: Mit dieser Zahl wird bezeichnet, welches Popupmen�u beim Dr�ucken des Buttons
erscheinen soll. 0 steht daf�ur, da� kein Popupmen�u erscheint. Ansonsten stehen noch die
Zahlen 1{5 zur Verf�ugung. Die verschiedenen Men�us werde ich, wie schon erw�ahnt, sp�ater
erl�autern.
5. verzeichnis: An dieser Stelle steht das Unterverzeichnis, in dem die Animationen oder
andere Dinge, die durch das Popupmen�u gesteuert werden, liegen.
Am Ende dieser Funktion wird noch eine weitere Variable gesetzt. Sie hei�t maxpage und
gibt die Gesamtzahl der Seiten an.
6.2 Popupmen�us
F�unf verschiedene Popupmen�us wurden von mir programmiert. Sie unterscheiden sich nur
in kleinen Punkten voneinander. Daher d�urfte es gen�ugen, wenn ich die E�ekte von Men�u 1
(Abbildung 4.2) erl�autere. Es w�are jedoch von Vorteil, wenn der Programmierer einige
Grundkenntnisse �uber OSF/Motif h�atte. An dieser Stelle sei auf [2] verwiesen, das mir als
Grundlage diente.
Dennoch m�ochte ich kurz einige wichtige Informationen darlegen:
An jeden Button ist eine Funktion gebunden, die beim Anklicken ausgef�uhrt wird. Durch
XtAddCallback wird die Verbindung zwischen Button und Funktion erzeugt. Dabei werden
der Name der Funktion und einige Variablen �ubergeben.
Die Buttons m�ussen in sogenannten Boxen untergebracht sein. Dadurch entsteht eine �uber-
sichtliche Struktur.
Auch k�onnen verschiedene Argumente bei der Realisierung der Buttons eingebracht wer-
den, wie zum Beispiel die Farbe, Schrift etc.
Ich ho�e, dies wird gen�ugen, um sich eine gewisse Vorstellung von der Struktur der Pro-
grammierung mit OSF/Motif zu verscha�en.
Jedes Popupmen�u besteht im Wesentlichen aus vier Funktionen: menue1, initAnim1, init-
Date und initOK.
Die beiden zuletzt genannten werden von allen Popups aufgerufen, w�ahrend die ersten bei-
den mit der entsprechenden Nummer versehen sind.
In der Funktion inhaltCB - sie wird aufgerufen, wenn ein Button des Inhaltsverzeichnisses
gedr�uckt wird - wird in einer case-Abfrage das entsprechende Popupmen�u aufgerufen (z.B.
menue1). In menue1 wird das Popupfenster de�niert. Dabei teile ich es in drei Bereiche auf;
einen f�ur die Animationsarten, einen f�ur die Eingabearten und einen f�ur die Best�atigung
der getro�enen Wahl bzw. f�ur den Abbruch. Die Trennung zwischen den beiden ersten Be-
reichen wird durch einen Separator f�ur den Benutzer sichtbar gemacht. Diese zwei Bereiche
sind Radioboxen; das hei�t, ihre Buttons werden bei der De�nition mit einem Wert true
oder false belegt. Nur einer darf allerdings auf true gesetzt werden. Dieser Button erscheint
nun so, als w�are er gedr�uckt. Klickt man auf einen anderen, so wird dieser auf true gesetzt.
Der vorherige nimmt aber automatisch den Wert false an.
Vor der Radiobox f�ur die Eingabeart habe ich noch eine kleine Textzeile eingef�ugt. Sie
38
KAPITEL 6. ERWEITERUNGEN UND VER�ANDERUNGEN 6.3. TEXTFILES
verdeutlicht, wozu die Wahlm�oglichkeiten dienen.
In der Funktion menue1 werden nun die anderen drei Funktionen aufgerufen.
initAnim1 besteht aus drei De�nitionen. Jede legt einen Button mit dem entsprechenden
Text fest. Mit der Funktion XtAddCallback wird jedem seine Wirkung zugewiesen, die dar-
in besteht, die globale Variable animatio zu manipulieren.
initDate hat dieselbe Struktur. Vor dem Erzeugen der Buttons wird jedoch noch eine wei-
tere Funktion setcomputer aufgerufen, die in das File /tmp/daten1 Computerdaten f�ur die
XTango-Animationen schreibt. In den zugeh�origen Callbacks wird keine Variable, sondern
dieses File manipuliert. Das hei�t, die entsprechenden Daten - seien es nun Benutzer-,
Zufalls- oder Computerdaten - werden in /tmp/daten gespeichert.
initOK de�niert die drei Buttons OK, Cancel und Help. An die ersten beiden ist der
Callback pop down gebunden. Er zerst�ort das entstandene Popup. Der zu Help geh�oren-
de Callback kreiert ein neues Fenster, welches das andere erkl�art. An den OK-Button ist
noch ein weiterer Callback gebunden (okCB). Hier wird entschieden, welche Animation
ausgew�ahlt wurde und nun ausgef�uhrt wird.
6.3 Text�les
Das Postscript�le, das die Grundlage f�ur mein Multimedia-Dokument bildet, steht im Ver-
zeichnis ps�les (vergleiche auch Anhang A) und tr�agt den Namen sortieren.ps. Wenn der
Benutzer nun ein anderes Text�le verwenden m�ochte, mu� er entweder das vorhandene
ersetzen oder im Programm sortieren.c in der Funktion ladeGraphik die Bezeichnung sor-
tieren.ps entsprechend umbenennen.
Selbstverst�andlich mu� der Wert maxpage - wie in Abschnitt 6.1 erw�ahnt - gegebenenfalls
neu gesetzt werden.
Die Links, die ich in meinem Text�le verwende, k�onnen nicht �ubernommen werden. Falls
keine Verweise existieren, sollte aus der Funktion ladeGraphik die Zeile \setzeLink(page);\
entfernt werden. Auch inputCB wird dann nicht ben�otigt. Das hei�t, man mu� den Aufruf
von inputCB entfernen.
Falls der Benutzer eigene Links de�nieren will, so ist dies nat�urlich m�oglich, wenn auch
etwas zeitaufwendig.
Zun�achst mu� man zu jedem neuen Link eine Position angeben. Diese bezeichnet die linke
obere Ecke eines Rechtecks, das dem Benutzer anzeigt, da� hier ein Verweis existiert. An-
hand der Funktion initLink kann man erkennen, welche Koordinaten f�ur welchen Punkt
innerhalb des Textbereiches zust�andig sind. Neben den Koordinaten wird nat�urlich auch
die Gr�o�e des Rechtecks mit den Variablen dx und dy festgelegt. Auf welche Seite der Link
zeigen soll, mu� in den Wert ziel eingetragen werden. Die Seite, auf der das Rechteck nun
erscheint, entspricht der Variablen quell.
links[0].quell=5; /* Seite, auf der der Link erscheinen soll */
links[0].ziel=6; /* Seite, auf die der Link zeigen soll */
39
6.4. FILMSEQUENZENKAPITEL 6. ERWEITERUNGEN UND VER�ANDERUNGEN
links[0].x=210; /* x-Koordinate des Links */
links[0].y=540; /* y-Koordinate des Links */
links[0].dx=105; /* x-Distanz des Rechtecks, das den Link markiert */
links[0].dy=25; /* y-Distanz des Rechtecks */
Da die Anzahl der Links bei meinem Dokument beschr�ankt ist, habe ich darauf verzichtet,
eine Struktur zu entwerfen, die in logarithmischer Laufzeit zu einer Seite ihre zugeh�origen
Verweise bestimmt.
Will ein Benutzer eine gr�o�ere Anzahl von Links verwenden, so mu� er in sortieren.h die
Gr�o�e des Arrays links entsprechend festlegen. Die Variable quell des letzten Elementes
des Arrays habe ich auf Null gesetzt. Folglich mu�te ich mich bei den Durchl�aufen dieser
Struktur nicht auf eine feste Anzahl festlegen.
6.4 Filmsequenzen
Wie ich schon in Abschnitt 4.3 erw�ahnt habe, stehen dem Benutzer einige Filmsequenzen
zur Verf�ugung. Diese sind in dem Verzeichnis movies untergebracht. Ihre Namen sind fort-
laufend numeriert. Das bedeutet: �lm0.mpeg, �lm1.mpeg, �lm2.mpeg, etc.
Es ist wichtig, da� diese Bezeichnungen beibehalten werden, da sie auch von meinem
Hauptprogramm verwendet werden. In der Funktion initFilmButton wird jeder Sequenz
ein weiterer Name zugeordnet, der gleichzeitig ihren Inhalt erl�autern soll. Anschlie�end
wird f�ur jede Sequenz ein Button de�niert.
Dies ist die einzige Stelle, die an dem Programm sortieren.c ver�andert werden mu�. Sollte
das Array f�ur die Speicherung der Namen zu klein sein - ich habe die Gr�o�e auf 20 Elemente
festgelegt - so kann man in sortieren.h die globale Variable entsprechend ver�andern. Die
for-Schleife, in der die Buttons de�niert werden, mu� dann bis zum neuen Wert laufen.
Falls der Benutzer noch andere, hier nicht aufgef�uhrte �Anderungen vornehmen will, so
d�urfte er damit keine Probleme haben. Die beiden Programmteile sortieren.c und sortie-
ren.h sind sehr gut kommentiert. Sollten dennoch irgendwelche Fragen auftauchen, so bin
ich gerne bereit, tatkr�aftige Unterst�utzung zu leisten.
40
Kapitel 7
Zusammenfassung
Das schnelle und unkomplizierte Erstellen von Multimedia-Dokumenten wurde in den letz-
ten Jahren immer wichtiger. Deshalb habe ich mit meiner Arbeit eine neue Umgebung
zur Steuerung von Multimedia-Dokumenten entwickelt. Das Ziel dieser Arbeit ist, hieraus
verschiedene Benutzerober �achen in allen m�oglichen Bereichen zu erstellen, die Filme, Ani-
mationen und Text optimal verbinden.
Schw�achen, die bei anderen Multimedia-Dokumenten (z. B. \Animated Algorithms\ von
Peter Gloor, Scott Dynes und Irene Lee) vorhanden sind, versuchte ich zu vermeiden.
An diesen Programmen st�ort mich, da� sie nicht sehr benutzerfreundlich sind. Man kann
nicht sofort erkennen, welche Handlung welchen E�ekt hervorruft. Auch ihre starre Kon-
�guration mi��el mir sehr. Dies habe ich bei meiner Steuerung und meinen Animationen
vermieden.
Den Text zum Thema \klassische Sortierverfahren\ stellte ich in den Mittelpunkt meines
Programmes, da B�ucher immer noch eine wichtige Basis der Informationsbescha�ung sind.
Anhand des Inhaltsverzeichnisses kann man sehr schnell und pr�azise die gesuchten Infor-
mationen �nden. Daher �ubernahm ich diese Struktur.
Der Benutzer kann durch diese Steuerung leicht zum eigentlichen Punkt seiner Fragestel-
lung vordringen. Damit dann kein Suchen mehr n�otig ist, habe ich die Animationen an das
Inhaltsverzeichnis gebunden. So kann man sich sofort den gew�ahlten Bereich darstellen
lassen.
Mit XTango ist es auch m�oglich, andere Animationen zu programmieren. Es w�are sicher
interessant, Animationen zum Thema Fibonacci-Heaps zu entwerfen. Dies w�urde aber den
Rahmen meiner Arbeit sprengen und soll nur als Ausblick auf k�unftige Projekte dienen.
Auf reine Soundobjekte habe ich verzichtet, da sie in diesem Zusammenhang den Benutzer
nicht ansprechen. Bei einem Thema, das sich mit den verschiedenen Manipulationsarten
von Sounds besch�aftigt, sind sie dagegen sehr von Vorteil. Doch es sollte jemandem, der sich
mit dieser Materie und mit der hier vorliegenden Arbeit besch�aftigt hat, nicht schwerfallen,
eine Buttonsteuerung f�ur Soundobjekte zu entwerfen. Als Vorlage mag ihm die Steuerung
der Filmsequenzen dienen.
Diese habe ich getrennt von dem Text programmiert, damit zus�atzlich zum Inhaltsver-
41
KAPITEL 7. ZUSAMMENFASSUNG
zeichnis eine weitere M�oglichkeit existiert, einen schnellen �Uberblick �uber das Thema zu
gewinnen. Bei den meisten Multimedia-Dokumenten ist der Mangel an einer kurzen und
pr�agnanten Information �uber Inhalt und Thema des Programmes ein gro�es Manko.
Durch die Filmsequenzen wird das Datenvolumen meines Programm-Pakets sehr umfang-
reich. Die eigentlichen Programme kann man auf wenigen Disketten unterbringen. Dennoch
sollte man sich �uberlegen, ob man dieses Paket nicht auf eine CD-ROM brennen l�a�t. Es
best�unde die M�oglichkeit, fertig compilierte Programmteile f�ur verschiedene Betriebssyste-
me zur Verf�ugung zu stellen. Da die Filme in einem Standardformat vorliegen, k�onnen sie
von jedem System verarbeitet werden.
Selbstverst�andlich w�are es denkbar, weitere Pakete zu entwerfen und sie entweder auf diesel-
be CD-ROM zu plazieren oder eine ganze Serie zu erstellen. Damit k�onnte jeder Benutzer,
ohne viel Speicherplatz auf seiner Festplatte zu verbrauchen, bestimmte Themen in Ruhe
rekapitulieren.
Ich denke, da� diese Vision in den kommenden Jahren immer deutlichere Formen annehmen
wird und ho�e, da� meine Arbeit ihren Teil zu dieser Entwicklung beitr�agt.
42
Anhang A
Installationshinweise
Dies ist ein Multimedia-Programm-Paket �uber klassische Sortierverfahren. Das Paket kann
auf jedem UNIX-Rechner installiert werden. Verwendet werden die Standard-X11-Bibliothe-
ken, der cc-Compiler und die OSF/Motif Bibliothek.
Man ben�otigt folgende Files:
sortieren.tar.gz
movies.tar.gz
Zun�achst wird das Hauptpaket mit
gunzip sortieren.tar.gz
dekomprimiert und danach mit
tar xvf sortieren.tar
entpackt.
Dabei entsteht folgende Verzeichnisstruktur:
Sortieren
Bubblesort ps�les xtango movies docHeapsort
InsertsortQuicksort
Selectionsort
Shellsort
include lib src doc
((((
((((
((((
(((((((
����������
PPPPPPP
PPP
hhhh
hhhh
hhhh
hhhh
hhh
((((
(((((
���
HHH
hhhh
hhhhh
43
ANHANG A. INSTALLATIONSHINWEISE
Im Hauptverzeichnis Sortieren stehen folgende Files:
INSTALL Durch Ausf�uhren dieses Programmes wird das komplette Paket installiert.
README Dieses File enth�alt Hilfen zur Installation.
Make�le Dies ist das Make�le f�ur das Hauptprogramm sortieren.
sortieren.c enth�alt den C-Code des Hauptprogrammes.
sortieren.h ist die zugeh�orige Headerdatei.
In den Verzeichnissen Bubblesort, Heapsort, Insertsort, Quicksort, Selectionsort und Shell-
sort stehen die Quellcodes der Animationen. Dort werden auch die fertigen Animationen
untergebracht.
Das Verzeichnis ps�les enth�alt das zugeh�orige Postscript-File und ein Programm, das das
Lesen einzelner Seiten erlaubt.
In xtango sind die f�ur die Animationen ben�otigten XTango-Objekte zu �nden. Beispiels-
weise enth�alt das Unterverzeichnis xtango/lib das in Abschnitt 3.2 erw�ahnte xtango.o-File,
w�ahrend in xtango/doc Informationsmaterial (z.B. [8]) �uber das XTango-Paket liegt.
Diese Arbeit ist in doc als Postscript-File zu �nden. Dadurch hat der Benutzer die M�oglich-
keit, bei Problemen sofort nachzuschauen.
Im Verzeichnis movie werden einige Filmsequenzen untergebracht.
Dazu mu� das File movies.tar.gz mit
gunzip movies.tar.gz und
tar xvf movies.tar
dekomprimiert und entpackt werden.
Durch das Ausf�uhren des Programmes INSTALL wird das komplette Paket installiert. Zu-
erst werden drei Files erstellt. In ihnen werden die Pfade des lokalen Verzeichnisses und des
Programmes gs gespeichert. In dem dritten steht, welcher MPEG-Player verwendet wird.
Dieser Name mu� von dem Benutzer selbst eingegeben werden.
Danach werden die verschiedenen Make�les ausgef�uhrt. Diejenigen, die in den Verzeich-
nissen Bubblesort, Heapsort, Insertsort, Quicksort, Selectionsort und Shellsort stehen, sind
identisch, da sie XTango ben�otigen.
Falls bei der Installation Probleme auftreten sollten, stehe ich selbstverst�andlich gerne zur
Verf�ugung.
44
Anhang B
Liste der Animationen
Algorithmus Darstellungsart
Bubblesort Balkendarstellung
Bubblesort Punktdarstellung
Bubblesort Balkendarstellung mit Programmtext
Heapsort Balken-Baum Darstellung
Heapsort Baumdarstellung
Heapsort Baumdarstellung mit Programmtext
Sortieren durch Einf�ugen Balkendarstellung
Sortieren durch Einf�ugen Punktdarstellung
Sortieren durch Einf�ugen Balkendarstellung mit Programmtext
Quicksort mit Pivotelement rechts Balkendarstellung
Quicksort mit Pivotelement rechts Punktdarstellung
Quicksort mit Pivotelement rechts Balkendarstellung mit Programmtext
Quicksort mit Balkendarstellung
Median-of-Three-Strategie
randomisiertes Quicksort Balkendarstellung
Sortieren durch Auswahl Balkendarstellung
Sortieren durch Auswahl Punktdarstellung
Sortieren durch Auswahl Balkendarstellung mit Programmtext
Shellsort Balkendarstellung
Shellsort Balkendarstellung mit Programmtext
Vergleich zwischen Sortieren durch Balkendarstellung
Auswahl, Sortieren durch Einf�ugen
und Bubblesort
Vergleich zwischen Sortieren durch Punktdarstellung
Auswahl, Sortieren durch Einf�ugen
und Bubblesort
45
ANHANG B. LISTE DER ANIMATIONEN
46
Anhang C
Einige XTango-Funktionen
Dies ist eine Auswahl von XTango-Funktionen, die zum Erstellen der in dieser Arbeit
beschriebenen Animationen notwendig waren.
void ASSOCinit()
initialisiert das ASSOC-Paket und stellt drei Verbindungen zwischen den Daten des Pro-
gramms und den Animationsobjekten zur Verf�ugung:
ID mit 2 Parametern
ID3 mit 3 Parametern
IMAGE AT mit 2 Parametern
void ASSOCmake(name,params)
char *name;
int params;
stellt eine Verbindung zur Verf�ugung. Ihre Bezeichnung wird mit der Variablen name und
die Anzahl der Parameter mit params festgelegt.
void ASSOCstore(name,p1,p2,p3,p4,p5,p6)
char *name;
int p1,p2,p3,p4,p5,p6;
weist der Verbindung mit der Bezeichnung name die entsprechenden Parameter zu. Hierbei
entspricht p1 beispielsweise dem Namen eines Arrays, w�ahrend p2 und p3 Position und Wert
angeben. Die Anzahl der Parameter ist um eins gr�o�er als beim Erzeugen.
int ASSOCretrieve(name,p1,p2,p3,p4,p5)
char *name;
int p1,p2,p3,p4,p5;
liefert den Wert, der mit der Verbindung name verkn�upft ist. Die Parameter p1 und p2
bezeichnen hierbei wieder den Namen und die Position.
47
ANHANG C. EINIGE XTANGO-FUNKTIONEN
TANGO PATH TANGOpath create(n,xo�sets,yo�sets)
int n;
double xo�sets[ ], yo�sets[ ]
erzeugt einen path der L�ange n, wobei xo�sets und yo�sets die Versetzungspositionen be-
schreiben.
TANGO PATH TANGOpath color(color)
TANGO COLOR color;
erzeugt einen path, der die bisherige Farbe in die Farbe color verwandelt.
TANGO PATH TANGOpath rotate(path,deg)
TANGO PATH path;
int deg;
erzeugt einen path, der um deg Grad gedreht wurde. Der Wert von deg sollte zwischen 0
und 360 liegen. Ist deg=180, so wird ein path erzeugt, der den umgekehrten Weg beschreibt.
Dies ist sehr n�utzlich beim Vertauschen von zwei Objekten.
TANGO PATH TANGOpath null(num)
int num;
erzeugt einen leeren path. Seine L�ange ist num, die xo�sets und yo�sets jedoch sind Null.
TANGO PATH TANGOpath iterate(path,factor)
TANGO PATH path;
double factor;
erzeugt einen um den Faktor factor vervielfachten path.
TANGO PATH TANGOpath motion(fromloc,toloc,type)
TANGO LOC fromloc,toloc;
TANGO PATH TYPE type;
erzeugt einen path, der von der location fromloc zu toloc f�uhrt. Der type gibt die Bewe-
gungsart an:
TANGO PATH TYPE STRAIGHT in gerader Linie
TANGO PATH TYPE CLOCKWISE bogenf�ormig im Uhrzeigersinn
TANGO PATH TYPE COUNTERCLOCKWISE bogenf�ormig gegen den Uhrzeigersinn
void TANGOpath free(num,p1,p2,p3,p4,p5,p6,p7,p8,p9,p10)
int num;
TANGO PATH p1,p2,p3,p4,p5,p6,p7,p8,p9,p10;
gibt den Speicherplatz frei, der von p1, p2 usw. belegt wurde. Die Anzahl der paths wird
mit num angegeben.
TANGO TRANS TANGOtrans create(type,image,path)
TANGO TRANS TYPE type;
TANGO IMAGE image;
TANGO PATH path;
erzeugt zu einem image und einem path eine transition. Der Wert type beschreibt die Art
der transition. Die wichtigsten sind:
TANGO TRANS TYPE MOVE bewegt das image entlang dem path.
48
ANHANG C. EINIGE XTANGO-FUNKTIONEN
TANGO TRANS TYPE VISIBLE ver�andert die Sichtbarkeit des images.
TANGO TRANS TYPE COLOR ver�andert die Farbe gem�a� dem path.
TANGO TRANS TYPE FILL f�ullt beispielsweise ein Rechteck aus.
TANGO TRANS TANGOtrans compose(num,t1,t2,t3,t4,t5,t6,t7,t8,t9,t10)
int num;
TANGO TRANS t1,t2,t3,t4,t5,t6,t7,t8,t9,t10;
verkn�upft mehrere transitions. Ihre Anzahl wird mit num angegeben.
void TANGOtrans perform(trans)
TANGO TRANS trans;
f�uhrt die transition trans aus.
void TANGOtrans free(num,t1,t2,t3,t4,t5,t6,t7,t8,t9,10)
int num;
TANGO TRANS t1,t2,t3,t4,t5,t6,t7,t8,t9,t10;
gibt den Speicherplatz der transitions t1, t2 usw. frei. Der Wert num beschreibt die Anzahl
der transitions.
TANGO LOC TANGOimage loc(image,part)
TANGO IMAGE image;
TANGO PART TYPE part;
liefert die location zu dem image. Hat part den Wert TANGO PART TYPE C (center), so
ist die location der Mittelpunkt des image. Folgende Werte kann part ebenfalls annehmen:
TANGO PART TYPE NW, TANGO PART TYPE N, TANGO PART TYPE NE,
TANGO PART TYPE E, TANGO PART TYPE SE, TANGO PART TYPE S,
TANGO PART TYPE SW und TANGO PART TYPE W. Sie entsprechen den Himmels-
richtungen.
void TANGOloc inquire(loc,x,y)
TANGO LOC loc;
double x,y;
schreibt die x-Komponente der location in x und die y-Komponente in y.
TANGO IMAGE TANGOimage create(type,p1,p2,...,pn)
TANGO IMAGE TYPE type;
param p1,p2,...,pn;
erzeugt ein image vom Typ type. Die wichtigsten Arten und ihre Parameter werden hier
aufgez�ahlt.
TANGO IMAGE TYPE LINE (lx,ly,vis,color,sx,sy,wid,sty,arrow)
double lx,ly,sx,sy,wid,sty; TANGO COLOR color; int vis,arrow;
Die Parameter lx und ly geben die Startposition der Linie an. Mit sx und sy wird die Distanz
von Anfangs- und Endpunkt bestimmt. wid beschreibt die Dicke der Linie (0.0=d�unn,
1.0=dick). Mit sty kann man den Stil der Linie beein ussen (gepunktet=0.0, gestrichelt=0.5
oder durchgehend=1.0). Die Farbe color kann die Werte TANGO COLOR WHITE,
TANGO COLOR BLACK, TANGO COLOR RED, TANGO COLOR GREEN,
TANGO COLOR BLUE etc. annehmen. Wenn vis=1, dann wird die Linie sichtbar. Bei
49
ANHANG C. EINIGE XTANGO-FUNKTIONEN
vis=0 bleibt sie unsichtbar. Mit der Variablen arrow kann man festlegen, ob die Linie eine
Pfeilspitze besitzen soll (0=keine Pfeilspitze, 1=Pfeilspitze am Endpunkt, 2=Pfeilspitze
am Anfangspunkt, 3=Pfeilspitze an beiden Enden).
TANGO IMAGE TYPE RECTANGLE (lx,ly,vis,color,sx,sy,�ll)
double lx,ly,sx,sy,�ll; int vis; TANGO COLOR color;
Das Rechteck wird durch seine linke obere Ecke (lx,ly) und den Abstand (sx,sy) zur rechten
unteren Ecke bestimmt. Der Parameter �ll kann Werte zwischen 0.0 und 1.0 annehmen (0.0
entspricht der Au�enlinie, 1.0 einem gef�ullten Rechteck).
TANGO IMAGE TYPE CIRCLE (lx,ly,vis,color,radius,�ll)
double lx,ly,radius,�ll; int vis; TANGO COLOR color;
Der Mittelpunkt des Kreises ist durch lx und ly, der Radius durch radius gegeben.
TANGO IMAGE TYPE TEXT (lx,ly,vis,color,fname,str,ctr)
double lx,ly; TANGO COLOR color; int vis,ctr; char *str, *fname;
Die linke obere Ecke des Bereiches, in dem der Text erscheinen soll, wird durch lx und ly
bestimmt, falls ctr=0. Wenn ctr=1, dann beschreiben die beiden Werte den Mittelpunkt
des Bereiches. Mit fname wird der Fontname angegeben. Der Text, der erscheinen soll,
steht im Parameter str.
void TWISTcreate image array(as,id,n,ty,hrz,x,y,xs,xqu,ys,yqu,sp,vis,col,�ll)
char *as;
int id,n;
TANGO IMAGE TYPE ty;
int hrz;
double x,y,xs[ ],xqu,ys[ ],yqu,sp;
int vis,col;
double �ll;
erzeugt das Bild eines eindimensionalen Arrays. Falls as NULL ist, so wird die Verbin-
dung ID verwendet. Mit id und n wird der Name des Arrays und seine Gr�o�e angege-
ben. TANGO IMAGE TYPE LINE, TANGO IMAGE TYPE RECTANGLE oder TAN-
GO IMAGE TYPE CIRCLE k�onnen mit ty angegeben werden. Der Parameter hrz be-
schreibt die Anordnung des Arrays (0=vertikal, 1=horizontal). Der Anfangspunkt wird
durch x und y de�niert. xs ist ein Array, in dem die Breite jedes Rechteckes steht. Ent-
sprechend ist ys f�ur die H�ohe zust�andig. Falls die Breite bzw. die H�ohe jedes Rechteckes
gleich ist, so steht dies in xqu bzw. yqu. Mit sp wird die Distanz zwischen den Objekten
angegeben.
50
Literaturverzeichnis
[1] P. A. BLAINE, R. M. BAECKER, I. S. SMALL,
A Principled Taxonomy of Software Visualization
Journal of Visual Languages and Computing (1993) 4, 211-266
[2] H.-J. BREDE, N. JOSUTTIS, S. LEMBERG, A. L�ORKE,
Programmieren mit OSF/Motif
Addison-Wesley (Deutschland) GmbH (1991)
[3] M. H. BROWN,
MacBALSA Version Aleph
Palo Alto, CA 94302 (1989)
[4] M. H. BROWN, M. A. NAJORK,
Algorithm Animation Using 3D Interactive Graphics
ACM UIST'93, NEW YORK (1993) 93-100
[5] W. DALITZ, G. HEYER,
Hyper-G Das Internet-Informationssystem der 2. Generation
dpunkt, Verlag f�ur digitale Technologie GmbH (1995)
[6] T. OTTMANN / P. WIDMAYER,
Algorithmen und Datenstrukturen
BI Wissenschaftsverlag Mannheim/Wien/Z�urich (1990)
[7] J. T. STASKO, A. BADRE, C. LEWIS,
Do Algorithm Animations Assist Learning?
An Empirical Study and Analysis
ACM INTERCHI 93 conference proceedings, NEW YORK (1993) 61-66
[8] J. T. STASKO, D. HAYES,
XTANGO Algorithm Animation Designer's Package
College of Computing Georgia Institute of Technology Atlanta, (1991)
51
LITERATURVERZEICHNIS LITERATURVERZEICHNIS
[9] J. T. STASKO
The Path-Transition Paradigm:
A Practical Methodology for Adding Animation to Program Interfaces
College of Computing Georgia Institute of Technology Atlanta, (1991)
52
![ZZZ KDOOVJUHHQKRXVHV FRP - KASVUHOONED...o¶ruguh gh prqwdjh tx¶lo idxw vxlyuh )lqlvvh] xq orw j olvwhv vh upipudqw dx orw hq txhvwlrq /h irqghphqw qh idlw sdv sduwlh gh od olyudlvrq](https://img.pdfslide.org/doc/110x75/60942747d66c8c26391d62e3/zzz-kdoovjuhhqkrxvhv-frp-kasvuhooned-oruguh-gh-prqwdjh-txlo-idxw-vxlyuh.jpg)
