Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


3. Elementare Datenstrukturen



Speicherzuweisung

Wie oben gezeigt wurde, ermöglichen die Zeiger von Pascal einen bequemen Weg für die Implementierung von Listen, doch es gibt hierzu Alternativen. In diesem Abschnitt erläutern wir, wie Felder verwendet werden können, um verkettete Listen zu implementieren, und wie dies mit der tatsächlichen Darstellung der Listen in einem Pascal-Programm zusammenhängt. Wie schon gesagt sind Felder eine recht direkte Darstellung des Speichers des Computers, so daß die Analyse der Art und Weise, wie eine Datenstruktur als Feld implementiert wird, einen gewissen Einblick vermitteln wird, wie sie auf einer niedrigen Ebene im Computer dargestellt werden könnte. Insbesondere ist es interessant zu sehen, wie verschiedene Listen gleichzeitig dargestellt werden könnten.

Bei der Darstellung einer verketteten Liste als Array benutzen wir Indizes anstelle von Verkettungen. Wir könnten so vorgehen, daß wir ein Feld von Datensätzen der obigen Art definieren, dabei aber ganze Zahlen (integers) (für die Feldindizes) anstelle der Verkettungen (links) für das nächste Feld (next) verwenden. Eine Alternative, die sich oft als geeigneter erweist, ist die Verwendung von »parallelen Feldern«: Wir bewahren die Elemente in einem Feld key[1..N] und die Verkettungen in einem Feld next[1..N] auf. Somit verweist key[next[head]] auf das erste Element in der Liste, key[next[next[head]]] auf das zweite, usw. Der Vorteil bei der Verwendung paralleler Felder liegt darin, daß die Struktur den Daten »übergestülpt« werden kann: Das Feld key enthält einzig und allein Daten, während die gesamte Struktur in dem parallelen Feld next gespeichert ist. Beispielsweise kann eine andere Liste unter Verwendung des gleichen Datenfeldes und eines anderen parallelen »Verkettungsfeldes« aufgebaut werden, oder es können weitere Daten mit Hilfe weiterer paralleler Felder hinzugefügt werden. Der folgende Code implementiert die elementaren Listenoperationen unter Verwendung von parallelen Feldern:

    var key,next: array[0..N] of integer;
        x,head,z: integer;
    procedure listinitialize;
      begin
      head:=0; z:=1; x:=1;
      next[head]:=z; next[z]:=z
      end;
    procedure deletenext(t: integer);
      begin 
      next[t]:=next[next[t]]
      end;  
    procedure insertafter(v: integer; t: integer);
      begin 
      x:=x+1;
      key[x]:=v; next[x]:=next[t];
      next[t]:=x
      end;

Der »Zeiger« x ersetzt die Speicherzuweisungsfunktion new: Er zeigt jeweils auf die nächste unbesetzte Position im Feld.

Abbildung 3.5 zeigt, wie die Liste aus unserem Beispiel in parallelen Feldern dargestellt werden könnte und in welcher Beziehung diese Darstellung zu der von uns verwendeten grafischen Darstellung steht. Auf der linken Seite sind die Felder key und next so zu sehen, wie sie erscheinen, wenn S L A I T in eine ursprünglich leere Liste eingefügt werden, wobei S, L und A nach head, I nach L und T nach S eingefügt werden. head nimmt die Position 0 und z die Position 1 ein (dies wird durch listinitialize gesetzt); da next[0] den Wert 4 hat, ist das erste Element in der Liste key[4] (A); da next[4] den Wert 3 hat, ist das zweite Element in der Liste key[3] (L) usw. In der zweiten Skizze von links sind die Indizes für das Feld next durch Linien ersetzt worden: Anstatt eine »4« auf next[0] zu setzen, zeichnen wir eine Linie vom Knoten 0 hinunter zum Knoten 4 usw. In der dritten Skizze entwirren wir die Verkettungen, so daß die Elemente der Liste nacheinander angeordnet werden; auf der rechten Seite zeichnen wir schließlich die Knoten einfach in unserer üblichen grafischen Darstellung.

Abbildung 3.5
Abbildung 3.5 Implementation einer verketteten Liste als Feld.

Die Kernfrage besteht in der Überlegung, wie die Standard-Prozeduren new und dispose implementiert werden können. Wir setzen voraus, daß der einzige Platz für Knoten und Verkettungen die Felder sind, die wir benutzt haben; diese Annahme führt uns zu dem Problem, daß das System Möglichkeiten bieten soll, innerhalb einer fixen Datenstruktur (dem Speicher selbst) andere schrumpfende und wachsende Datenstrukturen zur Verfügung zu stellen. Nehmen wir zum Beispiel an, daß der A enthaltende Knoten aus dem Beispiel in Abbildung 3.5 entfernt und dann freigegeben werden soll. Es ist eine Sache, die Verkettungen so umzuordnen, daß dieser Knoten nicht mehr in der Liste verkettet ist, doch was tun wir mit dem Platz, der durch diesen Knoten belegt wird? Und wie finden wir Platz für einen Knoten, wenn new aufgerufen wird und mehr Platz benötigt wird?

Beim Nachdenken über diese Fragen wird der Leser sehen, daß die Lösung klar ist: Es muß eine verkettete Liste verwendet werden, um die Übersicht über den freien Platz zu behalten! Wir bezeichnen diese Liste als die »free-list«. Wenn wir dann einen Knoten aus unserer Liste entfernen, geben wir ihn frei, indem wir ihn in die free-list einfügen, und wenn wir einen neuen Knoten benötigen, bekommen wir ihn, indem wir ihn aus der free-list entfernen. Dieser Mechanismus ermöglicht es, daß mehrere verschiedene Listen das gleiche Feld belegen.

Ein einfaches Beispiel mit zwei Listen (aber ohne free-list) ist in Abbildung 3.6 dargestellt. Es sind zwei als Listenkopf dienende Knoten hd1=0 und hd2=6 vorhanden, doch beide Listen können sich das gleiche z teilen. (Um mehrfache Listen aufzubauen, müßte die oben angegebene Prozedur listinitialize modifiziert werden, so daß mehr als ein Kopf verwaltet werden kann.) Nun hat next[0] den Wert 4, daher ist das erste Element in der ersten Liste key[4] (O); da next[6] den Wert 7 hat, ist das erste Element in der zweiten Liste key[7] (T), usw. Die anderen Skizzen von Abbildung 3.6 zeigen das Ergebnis des Ersetzens der Werte von next durch Linien, das Entwirren der Knoten und den Übergang zu unserer einfachen grafischen Darstellung, genau wie im Falle von Abbildung 3.5. Die gleiche Methode könnte angewandt werden, um mehrere Listen im gleichen Feld zu speichern, wobei eine von ihnen - wie oben beschrieben - eine free-list wäre.

Abbildung 3.6
Abbildung 3.6 Zwei Listen, die sich in den gleichen Platz teilen.

Wenn die Speicherverwaltung durch das System gewährleistet wird, wie dies in Pascal der Fall ist, gibt es keinen Grund, in der dargestellten Weise einzugreifen. Die obige Beschreibung dient der Veranschaulichung der Art und Weise, wie die Speicherverwaltung durch das System erfolgt. (Wenn das System des Lesers keine Speicherverwaltung realisiert, liefert die obige Beschreibung einen Ausgangspunkt für deren Verwirklichung.) Das tatsächliche Problem, welches das System lösen muß, ist noch wesentlich komplizierter, da nicht alle Knoten die gleiche Größe haben müssen. Weiterhin befreien manche Systeme den Anwender von der Notwendigkeit, Knoten explizit freizugeben, indem sie »garbage collection«-Algorithmen zum Entfernen aller Knoten, auf die sich keine der Verkettungen bezieht, benutzen. Eine Reihe recht eleganter Algorithmen zur Speicherverwaltung wurde entwickelt, um diese beiden Situationen handzuhaben.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]