Datenstrukturen
Next: Funktionalität und Implementierung des Up: Implementierung des Rahmenprogrammes Previous: Implementierung des Rahmenprogrammes
Datenstrukturen
- Wesentlichstes Element ist ein assoziatives Array, das als universelles und dynamisches Hash [Blu98] gestaltet wurde
. Hierbei wurden zur Kollisionsbehandlung nicht verkettete Listen, sondern Binärbäume
verwandt, um eine weitere Beschleunigung zu erhalten. Von der ursprünglichen Absicht, diese zusätzlich zu balancieren,
um so eine Datenstruktur mit Zugriffszeiten von 
im Average-Case und 
im Worst-Case zu erhalten,
wurde abgesehen, da erste Versuche zeigten, daß selten mehr als 5 Elemente pro Baum auftraten. Mit dem Umkopieren bei
Vergrößerung des Hashs wird jeweils gewartet, bis der Belegungsfaktor den Wert 2 erreicht hat. - Auch wenn keine Balancierung integriert wurde, finden in obiger Datenstruktur immer noch relativ viele Kopieroperationen statt. Daher wurde diese Struktur in erster Linie dazu verwendet, Zeiger auf die Elemente einer normalen verketteten Liste zu verwalten. Der Zugriff verlängert sich hierdurch nur um einen weiteren Dereferenzierungsschritt. Zudem tritt häufig der Fall auf, daß die Objekte unabhängig von den Schlüsseln durchmustert werden müssen. Beides wird durch diese Kombination gewährleistet.
- Die ansonsten komplizierteste Struktur stellt das Mengensystem dar. Jede Menge wird mit je zwei Listen versehen, die Zeiger auf die jeweiligen Ober- und Untermengen beinhalten. Bei der Speicherung werden diese durch die Indizes der entsprechenden Mengen im Mengensystem ersetzt; beim Laden werden die Zeiger erneut bestimmt. Da die Größe jeder Menge somit nur rekursiv bestimmt werden kann, wird sie stets in einer Variablen gehalten, so daß sie bei Vereinigungs- oder Löschvorgängen unmittelbar aus den ebenfalls gespeicherten Größen der Teilmengen bestimmt werden kann.
- Während der Bearbeitung des Stundenplans ändern sich die Daten vom Mengeneditor abwärts nur selten. Daher werden die wichtigsten Ergebnisse, wie z.B. die Struktur des Mengensystems, zusätzlich in Matrixform zwischengespeichert, die einen schnelleren Zugriff erlaubt. Da diese Matrizen nach größeren Veränderungen jeweils anhand der eigentlichen Strukturen (vgl. Abschnitt 8.4.1) neu erstellt werden, kann hier die Indizierung wesentlich effektiver erfolgen.
Next: Funktionalität und Implementierung des Up: Implementierung des Rahmenprogrammes Previous: Implementierung des Rahmenprogrammes (c) Martin Loehnertz 1999