====================================================================== Dokumentation zu "Trees" Version 1.0 Autor: Nicolas Benezan, Postwiesenstr. 2, D7000 Stuttgart 60 ====================================================================== Kopierrecht ­­­­­­­­­­­ Das komplette Packet (Quelltext, Dokumentation und Objectcode) ist Public Domain Software. Es darf beliebig kopiert und verbreitet werden solange... * mein Name und dieser Kopierrechtshinweis erhalten bleiben, * die Vollständigkeit des ganzen Packets gewährleistet ist, und * mit dem Vertrieb dieser Software kein Gewinn erwirtschaftet wird. Die Kommerzielle Nutzung ohne meine ausdrückliche schriftliche Genehmigung ist untersagt. Ferner ist allen Personen, die in irgend einer Weise etwas mit "Data Becker" zu tun haben, insbesondere für "Data Becker" arbeiten oder deren Produkte verkaufen, jegliche Verwendung dieser Software verboten. Verbesserungsvorschläge sind stets willkommen. Falls Sie Veränderungen am Programm vornehmen, dokumentieren Sie diese bitte gut verständlich. Es würde mich freuen, wenn Sie mich über größere Veränderungen in Kenntnis setzen würden. (c) 1988 by Nicolas Benezan. Übersicht ­­­­­­­­­ * Umfang des Packets * Einleitung * Beschreibung der Prozeduren * Sonstiges Umfang des Packet ­­­­­­­­­­­­­­­­­ Das komplette Packet "Trees" beinhaltet folgendes: * Trees.dok Diese Dokumentation * Trees.def, -.mod Quelltext * Trees.sym, -.obj Code (Stand 15.Jul.1989) Einleitung ­­­­­­­­­­ AVL-Bäume (siehe Amok#7) sind sehr gut dazu geeignet, große Datenmengen sortiert im Speicher zu halten und einen schnellen, gezielten Zugriff auf Datensätze zu ermöglichen. Bei kleineren Datenmengen lohnt sich jedoch der Aufwand nicht. Deshalb entstand das Modul "Trees", das hier folgende Unterschiede zum Modul "AVL" aufweist: Vorteile: - nur ein Bruchteil an Codelänge, deshalb auch für kleinere Programme interessant, - geht sparsamer mit Speicher um, da weniger Overhead, - bei kleineren Datenmengen (durchschnittlich) schneller als AVL, - keine Rekursionen (außer bei Do), kein großer Stack nötig; Nachteile: - Maschinennah programmiert (viele ADDRESS-Parameter usw.), deshalb stilmäßig nicht so schön, - in ungünstigen Fällen (hoher Grad an Vorsortierung) und großen Datenmengen uneffizient, da kein ausgeglichener Baum entsteht (Extremfall: Liste), - keine Prozedur zum Löschen von Elementen vorhanden. Beschreibung der Prozeduren ­­­­­­­­­­­­­­­­­­­­­­­­­­­ InitTree() ---------- Diese Prozedur erzeugt einen Baum zur späteren Verwendung und erstellt die internen Strukturen zu dessen Verwaltung. Es muß eine Vergleichsprozedur angegeben werden, die später jeweils die Adressen von zwei Datenrecords übergeben bekommt und je nachdem, ob die ersten Daten kleiner, gleich oder größer als die zweiten einsortiert werden sollen eine negative Zahl, 0 oder eine positive zurückgibt (gilt für aufsteigendes sortieren, sonst umgekehrt). InitTree() gibt TRUE zurück, falls genügend Speicher zum Erzeugen des Baums vorhanden war. Bei FALSE konnte der Baum nicht erzeugt werden. DiscardTree() ------------- ist das Gegenteil von InitTree und entfernt einen Baum nach der letzten Verwendung aus dem Speicher. dabei werden auch alle Elemente gelöscht. Add() ----- fügt einen neuen Datensatz in einen Baum ein, ohne ihn im Speicher zu verschieben, oder zu kopieren. Allerdings muß den eigentlichen Daten zur Verwaltung eine TreeNode-Struktur vorangestellt werden, z.B.: Node = RECORD node: TreeNode; data: DataRecord; END; Da kein neuer Speicher benötigt wird, kann diese Prozedur nicht fehlschlagen. Put() ----- fügt einen neuen Datensatz zu einem Baum hinzu, wobei dieser in einen neuen Speicherbereich kopiert wird. Der Umstand mit dem TreeNode ist hier nicht erforderlich, es kann z.B. direkt eine lokale Variable für den Parameter Data verwendet werden. Allerdings braucht die Prozedur wegen dem Kopieren der Daten etwas länger und sie kann bei Speichermangel fehlschlagen. Als Resultat wird die neue Adresse des Datensatzes zurückgegeben (nützlich für Zeigerreferenzen innerhalb des Baums) oder NIL, falls Put() fehschlug. Get() ----- sucht einen Datensatz im Baum und gibt dessen Adresse zurück, falls er gefunden wurde (andernfalls NIL). Dazu wird die Adresse eines Dummy- Datensatzes angegeben, der nur die für die Compare-Prozedur benötigten Schlüsseldaten enthält. Do() ---- Diese Prozedur geht den ganzen Baum vom kleinsten zum größten Element durch und ruft jedesmal mit der Adresse des entsprechenden Datensatzes als Parameter auf. Zusätzlich wird jedesmal als Referenz auf Zusatzdaten übergeben, was folgenden Sinn hat. Wegen der Modula-2- Definition muß die Prozedur global auf Modulebene liegen. Ohne wäre es nicht möglich, eine reentrante Prozedur zu schreiben, die Do() verwendet und zusätzliche (lokale) Daten übergibt. NodesInTree() ------------- gibt die Anzahl der vorhandenen Elemente eines Baums an. Sonstiges ­­­­­­­­­ Mit TreesAllocProc und TreesDeallocProc können alternative Speicherver- waltungsroutinen eingestellt werden (z.B. aus den Modulen MemSystem oder Clusters). Vorsicht: Wenn Sie Datensätze selbst allozieren und mit Add() hinzufügen, sollten Sie natürlich eine zu TreesAllocProc compatible Allocate-Prozedur verwenden.