Aufgabe:
Es soll ein Programm StackSort konzipiert werden, das beliebig viele (zufällig erzeugte) Elemente auf einem unsortierten Stapel durch Umstapeln mittels eines Hilfsstapels endgültig sortiert in einem dritten Stapel ablegt. Dort soll das kleinste Element oben liegen.
a) Notieren Sie am Beispiel des unsortierten Stapels {5;13;6;2;11;7}, welche Bewegungen (Umstaplungen) hier nötig sind. Grundsätzlich sollte vom unsortierten zuerst auf den Hilfsstapel bewegt werden, außer dies ist nicht sinnvoll. Bedenken Sie, dass nur das oberste Element (anfangs die 5) eines Stapels sichtbar ist. Notieren Sie jede Bewegung in einer Liste (rechts abgebildet ein Vorschlag). Bedenken Sie auch jeweils, welche Abfragen notwendig sind. Zeigen Sie, dass hier 16 Umstapelungen nötig sind.
U 5 13 6 2 11 7
H -
S -
U 13 ...
H 5
S -
b) Beschreiben Sie in Form eines Struktogramms
einen geeigneten Algorithmus hierzu. Hilfreich kann sein, zuvor
alle möglichen Situationen im Verlauf des Umstapelns und die
notwendige Bewegung geordnet zu notieren. Als Hilfsmaterial können
Sie hier eine vorbereitete Tabelle ansehen.
Tipps: Das
Struktogramm sollte nur wenige Schleifen und meist Abfragen enthalten.
Vor einem Größenvergleich muss sicher sein, dass keine
der beiden Stapel leer ist.
c) Kontrollieren Sie Ihr Struktogramm, indem Sie den in a) notierten Ablaufplan mit dem vom Struktogramm geforderten Ablauf vergleichen.
d) Implementieren Sie auf Grundlage des korrigierten Struktogramms ein Programm StackSort, das auch schrittweise zeigt, welche Umstapelungen für die Sortierung im Stapel Sort vorgenommen werden müssen und diese Anzahl zählt.
Hinweise: Idealerweise haben Sie bereits vorher einen abstrakten Datentyp (ADT) Stapel implementiert, dessen Prozeduren und Funktionen Sie nun nutzen können. Dies geschieht in Delphi durch Referenz auf diesen ADT im Modul stacksort.prg: uses ..., stapel;
Im ADT Stapel sollten vorhanden sein:
s_create (stack); //
Stapel erzeugen
s_push (stack, inh); // neues Element
auf Stapel
s_pop (stack); // Element vom Stapel
nehmen
inh := s_show (stack); // obersten Inhalt
zeigen
leer := s_isempty (stack); // Abfrage
Übergeben wird jeweils stack, ein Zeiger auf das oberste Element, der im ADT ggf. aktualisiert wird.
Nützliche Delphi-Schnipsel:
type
tStack = RECORD
inh:Integer;
next:pStack; END;
pStack = ^tStack;
var unsort, hilf,
sort: pStack;
Download (* nicht öffentlich)
Zu den Literaturlisten
Zurück zur Übersicht aller Unterrichtsmaterialien
Lösungen: Tabelle und Struktogramm mit Variante
(aber erst selbst bearbeiten!)
