Ringlisten


Bisher haben wir als Endemarkierung einer verketteten Liste immer einen Vorwärtsverweis mit dem Wert NIL verwendet (gestreckte Liste). Manchmal ist es vorteilhaft, stattdessen dort einen Verweis auf das erste Element der Liste einzutragen, wenn dieses über einen Anker zugänglich ist; so erhalten wir eine Ringliste. Sie kann ebensogut zur Ablage von Datenwerten verwendet werden, aber man muß auf Sonderfälle beim Übergang zwischen einer einelementigen und einer leeren Liste achten, und das Kopfelement muß seinen Platz behalten, weil ein Zeiger vom Ende her darauf verweist:

Ringlisten
PROCEDURE einfuege(a: atom; VAR l: liste);
VAR p: liste;
BEGIN NEW(p); 
      IF l = NIL THEN l := p ELSE p^ := l^
      END; 
      l^.nach := p; l^.wert := a;
END einfuege;
Beim Entfernen geht alles sinngemäß rückwärts:
PROCEDURE entferne(VAR a: atom; VAR l: liste);
VAR p: liste;
BEGIN a := l^.wert; p := l^.nach;
      IF l = p THEN l := NIL ELSE l^ := p^
      END;
      DISPOSE(p);
END entferne;
Als Ausgleich für diese Komplikationen kommt jetzt eine neue Möglichkeit hinzu: die Datenelemente  sind jetzt ein logischer Ring, und indem wir den Anker weiter wandern lassen, können wir ihn bei einem beliebigen Element beginnen lassen.

Zum Löschen einer Ringliste hängen wir am einfachsten alle Elemente aus.

PROCEDURE delete(l: liste);
VAR p: liste;
BEGIN WHILE l <> NIL
      DO p := l^.nach;
         IF l = p THEN l := NIL ELSE l^.nach := p^.nach
         END;
         DISPOSE(p);
      END;
END delete;

zurück | Inhalt | Index | vor | Vorlesung

Klaus Lagally, 22. Februar 2000, 19:36