Verkettete Listen: Wertvergleich

Wenn wir zwei Variable p und q vom Typ liste haben, wobei wir an p und q je ein (irgendwann über newlist und cons aufgebautes) Geflecht angehängt haben, so liefert der Vergleich p = q nicht etwa die Information, ob die beiden Listen dieselben Datenwerte in derselben Reihenfolge enthalten, sondern stattdessen die Information, ob es sich um dasselbe konkrete Objekt  handelt.

Die Abfrage auf gleiche Wertefolgen ist aufwendiger; sehen wir uns dazu erst ihre funktionale Definition an:

isequal(newlist, newlist) = true
isequal(newlist, cons(a,x)) = false
isequal(cons(a,x), newlist) = false
isequal(cons(a,x), cons(b,y)) = ((a = b) isequal(x,y))
Bei der Implementierung in Modula 2 müssen wir darauf achten, daß wir keine NIL-Werte dereferenzieren dürfen, und daß ein Objekt sich selbst gleich ist. 
PROCEDURE isequal(p, q: liste): BOOLEAN;
BEGIN IF p = q THEN RETURN TRUE
      ELSIF p = NIL THEN RETURN FALSE
      ELSIF q = NIL THEN RETURN FALSE
      ELSE RETURN (p^.wert = q^.wert) 
                  AND isequal(p^.nach, q^.nach)
      END;
END isequal;
Dies läßt sich auch iterativ formulieren, wobei die beiden Wertparameter p und q die beiden Listen soweit wie nötig durchlaufen; hier haben wir ein Beispiel dafür, daß eine LOOP-Schleife nicht mit EXIT, sondern mit RETURN verlassen wird. 
PROCEDURE isequal(p, q: liste): BOOLEAN;
BEGIN LOOP IF p = q THEN RETURN TRUE
           ELSIF p = NIL THEN RETURN FALSE
           ELSIF q = NIL THEN RETURN FALSE
           ELSIF p^.wert <> q^.wert THEN RETURN FALSE
           ELSE p := p^.nach; q := q^.nach;
           END;
      END;
END isequal;
zurück | Inhalt | Index | vor | Vorlesung
Klaus Lagally, 22. Februar 2000, 19:36