Anwendung einer binaeren Verweiskettenmethode beim Aufbau von Listen Die in dieser Schrift beschriebene Methode beruht auf der Untersuchung und Auswertung bestimmter Bits, die den Namen der einzelnen Eintragungen entnommen werden. Diese Bits bestimmen die Anordnung der Eintragungen in der Verweiskette und sind daher massgeblich fuer Suche und Listenerweiterung. Diese Methode bietet folgende Vorteile: Der Aufbau einer oder mehrerer Listen geht ohne zeitaufwendige Verschiebungen vor sich. Die Anzahl der noetigen Suchschritte isk klein. Wie in dieser Schrift gezeigt wird, weicht die mittlere Anzahl der noetigen Suchschritte, ausgedrueckt als Funktion der mit N bezeichneten Anzahl der Eintragungen, nur wenig von log_2 N ab. In vielen Progrmamen, speziell in Assemblerprogrammen, werden waehrend des Programmlaufs mehrere Listen aufgebaut, deren endgueltige Laenge zu Programmbegin nicht festliegt. So kommt es, dass die Verwendung herkoemmlicher Methoden beim Listenaufbau, die eine getrennte Reservierung von Arbeitsspeichern fuer jede einzelne Liste erfordern, in den meisten Faellen entweder zu einer unvollstaendigen Ausnuetzung des Arbeitsspeichers oder aber zu zeitaufwendigen Verschiebungen fuehrt. In diesem Aufsatz wird eine binaere Verweiskettenmethode beschrieben, mit der diese Schwierigkeiten geloest werden koennen. Diese Methode wird bereits in einem Assemblerprogramm fuer den Telefunken-Rechner TR 440 werwendet. Ganz allgemein bietet die Verwendung einer binaeren Verweiskette beim Aufbau von Listen folgende Vorteile: Einerseits sind bei der Suche nach einzelnen Eintragungen nur wenig Suchschritte noetig, wodurch ein schneller Zugriff ermoeglicht wird. Andererseits koennen die einzelnen Eintragungen beliebig angeordnet werden, ohne dass dies den Suchvorgang beeinflusst. Daher sind beim Aufbau einer einzelnen Liste keine Verschiebungen noetig. Aus dem gleichen Grunde koennen mehrere Listen parallel aufgebaut werden, ohne dass Anordnung und Speicherbedraf der einzelnen Listen vorher festgelegt werden muss. Fuer alle Listen kann dabei ein gemeinsamer Spiecher verwendet werden, der erst verlaengert werden muss, wenn er vollstaendig belegt ist. Ein weiterer Vorteil ist, dass fuer einzelne Eintragungen kein festes Format vorgeschrieben werden muss. 1. Aufbau einer Liste Jede Liste besteht aus einer Menge von Eintragungen und der Werweiskette. Eine Eintragung besteht aus einem Wert und einem Namen, der den Wert eindeutig definiert. Die Verweiskette vesteht aus einzelnen Knoten. Jeder Knoten enthaelt 2 Adressen und eine Bitnummer (siehe Bild 1). Bild 1. Aufbau eines Knotens. ... Der Aufbau einer Liste laesst sich am besten an Hand eines Beispiels (Bild 2) erklaeren. Die Liste in diesem Beispiel enthaelt 5 Eintragungen, die die Namen 44, F4, 5A, A1 und B2 tragen. Diese Namen werden in dem Beispiel intern im Tetradencode dargestellt und daher durch die Bitfolgen 0L00 0L00, LLLL 0L00, 0L0L L0L0, L0L0 0000L und L0LL 00L0 repraesentiert. Selbstverstaendlich haette auch ein beliebiger anderer Code gewaehlt werden koennen, ohne dass sich am Aufbau der Liste etwas wesentliches geaendert haette. Wie Bild 2 zeigt, ist jeder Knoten der Liste ein Eingang in eine Unterliste. Die Adressen, die im Knoten enthalten sind, verweisen auf die Eingaenge zweier weiterer Unterlisten, und zwar einer rechten und einer linken. Die Unterlisten koennen auch Eintragungen sein und bilden dann die Endpunkte der Verweiskette. Bild 2. Beispiel fuer eine Liste. ... Bild 3. Erweiterte Liste. ... Bild 4. Unsortierte Liste. ... Die Namen einer linken Unterliste unterscheiden sich von den Namen der zugehoerigen rechten Unterliste in mindestens einem Bit. Die Bitnummer des ersten dieser Bits ist in dem Knoten, der auf die zwei Listen verweist, angegeben: Bei allen Namen der linken Unterliste hat dieses Bit den Wert 0, bei den Namen der rechten Unterliste den Wert L. 2. Der Suchvorgang Vor der Suche nach einem Wert muss der Name des Wertes und die Adresse des Eingangs der zu durchsuchenden Liste bereitgestellt werden. Bei der Suche wird zunaechst das durch die Bitnummer des Eingangskontens angegebene Bit des bereitgestellten Namens untersucht, und je nachdem, ob dieses Bit den Wert 0 oder L hat, wird der durch die linke oder rechte Adresses angegebene Knoten als neuer Eingangsknoten behandelt. Dieses Verfahren wird solange fortgesetzt, bis auf eine Eintragung verwiesen wird. Wenn der Name dieser Eintragung nicht mit dem bereitgestellten Namen uebereinstimmt, ist in der Liste kein Wert mit dem bereitgestellten Namen enthalten. 3. Konstruktion einer Liste Gleich bei der Eroeffnung besteht eine Liste aus einem Knoten, der auf zwei dummy-Eintragungen weist. Die Namen dieser Eintragungen sind natuerlich besonders gekennzeichnet und koennen daher nicht mit anderen Namen verwechselt werden. Die Konstruktion einer Liste besteht nach Herstellung dieses Anfangszustandes nur mehr darin, dass einzelne Listenelemente der Reihe nach in die Liste eingetragen werden. Jeder Eintragungsvorgang besteht aus drei Schritten: Dem bereits beschriebenen Suchvorgang, dem Vergleich des gefundenen Namens mit dem bereitgestellten Namen und der eigentlichen Eintragung. Beim Vergleich der beiden Namen wird die Bitnummer des ersten Bits, in dem sich die beiden Namen unterscheiden, festgestellt. Beim Eintragen des neuen Elementes wird die Liste um einen neuen Knotenpunkt erweitert. Dieser enthaelt die beim Namensvergleich ermittelte Bitnummer und die Adresse des neuen Listenelements. Der neue Knoten wird so in die Verweiskette eingefuegt, dass die bei der Suche nach dem neuen Element durchlaufenden Knoten aufsteigende Bitnummern aufweisen. Bei der Einfuegung des neuen Knotens muss daher eine bestimmte alte Verweisadresse durch die Adresse des neuen Knotens ersetzt werden. Die alte Verweisadresse wird in den neuen Knoten eingesetzt. Als Beispiel fuer das Ergebnis einer solchen Erweiterung wird in Bild 3 die um ein Element mit dem Namen 10 (= 000L 0000) erweiterte liste des Bildes 2 gezeigt. 4. Sortierte und unsortierte Liste Wenn bei der Konstruktion einer Liste, so wie beschrieben wurde, worgegangen wird, findet man, falls man die Endpunkte der Verweiskette im Gegenuhrzeigersinn untersucht, dass die Namen lexikographisch sortiert sind. Auf Grund dieser Anordnung koennen die Eintragungen leicht in einer sortierten Folge ausgegeben werden. Legt man auf eine solche sortierte Liste keinen Wert, dann braucht beim Aufbau der Liste nicht darauf geachtet werden, dass die einzelnen Bitnummern aufsteigende Zahlenfolgen bilden. Bild 4 zeigt eine unsortierte Liste mit den gleichen Eintragungen wie die Liste in Bild 3. Auf den Suchvorgang hat der Unterschied zwischen sortierten und unsortierten Listen keinen Einfluss. 5. Anzahl der noetigen Suchschritte Unter der Voraussetzung, dass die Verweiskette gleichmaessig aufgebaut ist, werden bei Listen, die N Eintragungen enthalten, log_2 N Suchschritte benoetigt, um eine bestimmte Eintragung zu finden. Im allgemeinen sind Verweiskette jedoch nicht gleichmaessig aufgebaut. Man benoetigt daher nicht fuer alle Eintragungen die gleiche Anzahl von Suchschritten. Fuer die mittlere Anzahl S(N) der Suchschritte, die bei der Suche in Listen mit N Eintragungen noetig sind, wird im naechsten Abschnitt folgende Formel abgeleitet: ... 6. Ableitung der Formel fuer S(N) S(N) ist der Erwartungswer fuer die Anzahl der Suchschritte, die noetig sind, um eine beliebige Eintragung in einer beliebigen Liste mit N Eintragungen zu finden. Die Namen der Eintragungen werden durch beliebige Bitfolgen von ausreichender Laenge dargestellt. Und zwar muss die Laenge der Namen so gross sein, dass die Anzahl der Eintragungen genuegend klein gegenueber der Anzahl der durch die Bitfolgen darstellbaren Namen ist. Unter dieser Voraussetzung ist S(N) der Mittelwer fuer die Anzahl der Suchschritte bei allen moeglichen Suchvorgaengen in allen moeglichen Listen mit N Eintragungen. ... Literatur In den nachstehend angefuehrten Arbeiten wird eine Methode beschrieben, die gleichfalls Verweisketten verwendet. Diese Methode unterscheidet sich von der hire beschriebenen Methode im wesentlichen dadurch, dass bei der Interpretation der Knoten nicht einzelne bestimmte Bits, sondern der Reihe nach die Buchstaben, aus denen die Namen zusammengesetzt sind, untersucht werden. [1] Fredkin, E., Trie Memory. Comm. ACM 3 (Sept. 1960), S. 490 bis 499. [2] Sussenguth, E. H., Use of Tree Structures for Processing Files, Comm. ACM 6 (Mai, 1963), S. 272-279.