Dr. Andreas Borchert Abteilung Angewandte
Informationsverarbeitung 24. Juni 2004
Michael Wiedemann Blatt 7
Allgemeine Informatik II (SS 2004)
Abgabetermin: 1. Juli 2004
Nachdem es uns gelungen ist, eine bestehende (beliebig lange) Liste zu erstellen, zu bearbeiten und gegebenenfalls wieder auszugeben, wollen wir das Ganze ein wenig verfeinern.
Die möglichen Nachteile einer linearen Liste liegen auf der Hand:
Die Liste kann nur in eine Richtung abgearbeitet werden, man muss aufpassen, dass man nicht über das Ende einer Liste hinausgeht, usw.
Deswegen realisieren wir eine Zuteilung über einen doppelt verketteten Ring. Folgendes sollte unser neues Oberon-Programm bewältigen können:
- Aufbau eines doppelt verketteten Ring, das heißt, das letzte Element der Liste ist verkettet mit dem ersten Element. Die Einträge der Liste kommen wiederum entweder von der Standardeingabe oder aus einer Datei.
- Statt ein Element durch einen Zufallsgenerator zu bestimmen, wird dieses Mal eine Laufweite count angegeben. Diese gibt an, welches Element des Ringes gelöscht werden soll (man beginnt bei einem Element, dann werden count Schritte vollzogen, gelöscht, dann wieder count Schritte, gelöscht, usw.). Dabei kann diese Laufweite größer sein als die Anzahl der Elemente. Falls dies der Fall ist, wird einfach vorne wieder angefangen (wir laufen im Kreis). Bei jedem Löschvorgang soll das gerade gelöschte Element ausgegeben werden.
- Das ganze Spiel soll sich solange wiederholen, bis nur noch ein Element im Ring übrig bleibt. Dieses soll dann, quasi als Sieger des Auswahlprozesses, ausgegeben werden.
- Aufgrund der Verkettung des Ringes besteht die Möglichkeit, vorwärts oder rückwärts durch den Ring zu gehen. Diese Funktionalität soll mittels Flags in der Argumentverarbeitung realisiert werden. Daraus ergibt sich folgender gewünschter Programmaufruf:
Ringeinteilung [-i inputfile] [-f -b] count
- Die Flags -f bzw. -b geben die Richtung an. Dabei sollte maximal eine der beiden Flags zulässig sein, das heißt, bei -f -b sollte abgebrochen werden. Kommt keine der beiden Flags, sollte standardmäßig vorwärts durch den Ring gelaufen werden. Die Angabe count sollte wieder nur Werte größer als Null annehmen.
Die Fortgeschrittenen unter Euch können versuchen, die in der Vorlesung angesprochene Modularisierung zu realisieren. Ansonsten gelten generell wieder die Tipps zu Listen vom vorherigen Blatt.
Viel Erfolg!
Michael Wiedemann
2004-06-24