Power-Programmierung/CD1.mdf/modula2/library/fst/modula1/dyndatso.mod

Text File | 1993-07-28 | 3KB | 106 lines

MODULE DynDatSort;
(* Sortieren von positivn INTEGERn mit Hilfe von Dynamischen Daten-
   strukturen. Die zu sortierenden INTEGER müssen explizit eingegeben
   werden. Durch Eingabe einer negativen Zahl wird die Eingabe
   beendet und es erfolgt eine sortierte Ausgabe der Zahlen.  *)

FROM SYSTEM IMPORT SIZE;
FROM Storage IMPORT ALLOCATE;
FROM IO IMPORT RdInt,WrStr,WrInt,WrLn;
FROM InOut IMPORT ReadInt;

TYPE tpToKnoten=POINTER TO tKnoten;
     tKnoten=RECORD
                naechsterKn:tpToKnoten;
                KnotenWert:INTEGER;
              END;  (* RECORD *)
VAR pKnoten:tpToKnoten;
    pRoot,pVorgaenger:tpToKnoten;
    Wert:INTEGER;

PROCEDURE  CreateKnoten(Wert:INTEGER):tpToKnoten;
(* erzeuge Knoten mit dem KnotenWert Wert *)
  VAR plKnoten:tpToKnoten;
      Knoten:tKnoten;
      (* wird nur für die Beschaffung von Speicher benötigt *)
  BEGIN (* Create Knoten *)
    ALLOCATE(plKnoten,SIZE(Knoten));
    WITH plKnoten^ DO
      KnotenWert:=Wert;
      naechsterKn:=NIL
    END;
    RETURN plKnoten
  END CreateKnoten;

PROCEDURE SearchPred(start:tpToKnoten;
                     Wert:INTEGER):tpToKnoten;
(* suche ab dem Knoten start den Knoten mit KnotenWert>Wert
 * Rueckgabewert:NIL falls kein Vorgaenger,
 *sonst Zeiger auf diesen Knoten *)
  VAR p1,p2:tpToKnoten;
  BEGIN  (* SearchPred *)
    p1:=NIL;
    p2:=start;
    WHILE (p2<>NIL) & (p2^.KnotenWert<=Wert) DO
      p1:= p2;
      p2:=p1^.naechsterKn;
    END;  (* WHILE *)
    RETURN p1
  END SearchPred;

PROCEDURE OutSortedData(start:tpToKnoten);
(* gibt die sortierten Daten aus *)
  VAR p1,p2:tpToKnoten;
  cnt:INTEGER;
  BEGIN
    cnt:= 1;
    p1:=start;
    WHILE (p1<>NIL) DO
      IF (cnt MOD 11)=0 THEN WrLn END;
      WrInt(p1^.KnotenWert,6);
      INC(cnt);
      p1:=p1^.naechsterKn;
    END (* WHILE *)
  END OutSortedData;

BEGIN  (* MAIN *)
  pRoot:=NIL;
  WrStr('Bitte positive zahlen eingeben ');
  WrStr('  (Eingabeende durch negative Zahl)');
  WrLn;
  LOOP
    LOOP
      WrStr('Bitte Zahl eingeben: ');
      ReadInt( Wert);
      IF Wert>MAX(INTEGER) THEN WrLn;
                                 WrStr('Wert zu groß!');
      ELSE EXIT
      END;  (* IF *)
    END;   (* LOOP *)
    WrLn;
    IF Wert>=0 THEN
       pKnoten:=CreateKnoten(Wert);
       pVorgaenger:=SearchPred(pRoot,Wert);
       IF pVorgaenger=NIL THEN
          IF pRoot=NIL THEN
             pRoot:=pKnoten;
          ELSE
               pKnoten^.naechsterKn:=pRoot;
               pRoot:=pKnoten
          END   (* IF *)
       ELSE
          pKnoten^.naechsterKn:=pVorgaenger^.naechsterKn;
          pVorgaenger^.naechsterKn:=pKnoten;
       END   (* IF *)
    ELSE
       OutSortedData(pRoot);
       EXIT
    END  (* IF *)
  END  (* LOOP *)
END DynDatSort.