Verkettete Listen: Modifikation (2)


Eine Variante der Routinen zum Einfügen oder Löschen am Listenanfang wird gelegentlich verwendet, um sich lokal eine Freiliste an Listenelementen zu halten für den Fall, daß DISPOSE nicht richtig funktioniert; bei manchen Implementierungen ist (oder war?) das leider so.
VAR Frei: liste; (* mit NIL initialisieren! *)

PROCEDURE gibKnoten(VAR p: liste);
BEGIN IF Frei = NIL THEN NEW(p)
      ELSE p := Frei; Frei := p^.nach;
      END;
END gibKnoten;

PROCEDURE nimmKnoten(VAR p: liste);
BEGIN p^.nach := Frei; Frei := p;
END nimmKnoten;
Außer am Listenanfang kommen oft auch Modifikationen im Inneren  einer Liste vor, an einer etwa durch einen Suchvorgang gefundenen Stelle. Dabei kommt es im Grunde gar nicht so sehr auf die Liste als konkrete Speicherstruktur  an, sondern vielmehr auf die lineare Folge der Datenwerte.  Das Einfügen oder Entfernen eines Datenelements hinter  einem über einen Zeiger q zugänglichen Einstiegs-Element geht fast genauso wie am Listenanfang; der Nachfolgerverweis im Einstiegselement wirkt als Anker für den Rest der Liste:
PROCEDURE einfuegenach(a: atom; q: liste);
VAR p: liste;
BEGIN NEW(p);
      p^.wert := a; p^.nach := q^.nach; q^.nach := p;
END einfuegenach;

PROCEDURE entfernenach(VAR a: atom; q: liste);
VAR p: liste;
BEGIN p := q^.nach; a := p^.wert; q^.nach := p^.nach;
      DISPOSE(p);
END entfernenach;
Der Zeiger q braucht hier kein Referenzparameter zu sein, da er nicht verändert wird (es schadet aber auch nichts).


zurück | Inhalt | Index | vor | Vorlesung

Klaus Lagally, 22. Februar 2000, 19:36