Verkettete Listen: tiefe Kopie


Wenn wir zwei Variable p und q vom Typ liste haben, wobei wir an p ein (irgendwann über newlist und cons aufgebautes) Geflecht angehängt haben, so erzeugt die Zuweisung q := p keineswegs  ein neues  Geflecht gleichen Inhalts, sondern einen weiteren Zugriffspfad  auf dasselbe Geflecht, also ein Alias. Eine Veränderung über einen der beiden Pfade p und q wird damit auch über den anderen  Pfad sichtbar, da es sich ja um dasselbe Objekt handelt. Außerdem haben wir, falls q bereits einen legalen Pointer auf ein Haldenobjekt enthielt, diesen jetzt überschrieben, und womöglich ist dieses Objekt dadurch sogar unerreichbar  geworden (sofern wir nicht daran gedacht haben, es freizugeben, wenn es nicht mehr benötigt wird).

Um solche Überraschungen zu vermeiden, ist es dringend zu empfehlen, sich den Effekt jeder  Pointer-Manipulation durch eine Handskizze  zu veranschaulichen!

Will man statt eines Alias wirklich ein neues  Listenobjekt mit gleichem Inhalt wie ein gegebenes Objekt haben, das man dann unabhängig vom anderen verändern kann, so kann das nur über eine explizite tiefe Kopie geschehen, die einen neuen Zugriffspfad liefert:

PROCEDURE copy(l: liste; VAR p: liste);
BEGIN IF l = NIL THEN p := NIL
      ELSE NEW(p);
           p^.wert := l^.wert;
           copy(l^.nach, p^.nach);
      END
END copy;
Auch hier gibt es eine nicht ganz leicht zu verstehende iterative Version:
PROCEDURE copy(l: liste; VAR p: liste);
VAR q: liste;
BEGIN IF l = NIL THEN p := NIL;
      ELSE NEW(p); q := p;
           WHILE l <> NIL 
           DO q^.wert := l^.wert; l := l^.nach;
              IF l = NIL THEN q^.nach := NIL
              ELSE NEW(q^.nach); q := q^.nach;
              END;
           END;
      END;
END copy;

zurück | Inhalt | Index | vor | Vorlesung

Klaus Lagally, 22. Februar 2000, 19:36