(****************************************************************************)
(*  Bibliotheks-Modul LISTE.BIB  Listenoperationen fuer geordnete Listen    *)
(*  Setzt das Vorhandensein des Typs 'ListenInhalt' sowie die Funktion      *)
(*  'kleiner' voraus, die zwei Werte vom Typ 'ListenInhalt' vergleicht      *)
(*  t Liste   definiert eine nach 'kleiner' geordnete Liste                 *)
(*  (f passt(X,Y:ListenInhalt):boolean)                                     *)
(*  p Einfuegen(var L:Liste; E:ListenInhalt)                                *)
(*  p Suchen(L:Liste; E:ListenInhalt; var P:Liste) sucht das Element E in   *)
(*       in der Liste S und gibt das Ergebnis im Zeiger P zurueck. Falls    *)
(*       das Element E in S nicht vorhanden ist, erhaelt P den Wert NIL     *)
(*  p Loeschen(var L:Liste; P:Liste) loescht aus der Liste das Element, auf *)
(*       das P zeigt. Die Prozedur prueft nicht, ob P wirklich auf ein      *)
(*       ListenElement zeigt.                                               *)
(****************************************************************************)

TYPE   Liste         = ^ListenEintrag;
       ListenEintrag = RECORD
                         Eintrag   : ListenInhalt;
                         Naechster : Liste
                       END;

FUNCTION passt(X, Y : ListenInhalt) : boolean;
  BEGIN
    passt:=not(kleiner(X,Y) or kleiner(Y,X))
  END;

PROCEDURE Einfuegen(var L : Liste; E : ListenInhalt);
  VAR p,q : Liste;
  BEGIN
    q:=NIL; p:=L;
    WHILE p<>NIL DO WITH p^ DO
        IF kleiner(Eintrag,E) THEN BEGIN q:=p; p:=naechster END ELSE p:=NIL;
    new(p); p^.Eintrag:=E;
    IF q=NIL THEN BEGIN p^.Naechster:=L; L:=p END
             ELSE BEGIN p^.Naechster:=q^.naechster; q^.Naechster:=p END;
  END;

PROCEDURE Loeschen(VAR L : Liste; P : Liste);
  VAR q : Liste;
  BEGIN q:=P^.Naechster;
    IF q<>NIL THEN BEGIN P^:=q^; dispose(q) END
    ELSE IF P=L THEN BEGIN L:=NIL; dispose(p) END
    ELSE BEGIN
           q:=L; WHILE q^.Naechster<>P DO q:=q^.Naechster;
           q^.Naechster:=P^.Naechster; dispose(P)
         END
  END;

PROCEDURE Suchen(L : Liste; E : ListenInhalt; VAR P : Liste);
  VAR gefunden : boolean;
  BEGIN
    P:=L; gefunden:=FALSE;
    WHILE (P<>NIL) AND (NOT gefunden) DO
      BEGIN
        gefunden:=passt(P^.Eintrag,E); IF not gefunden THEN P:=P^.Naechster
      END
  END;