Cas09/Put.MOD

   1 MODULE Put;
   2
   3   FROM IO IMPORT
   4     WrLn, WrStr, RdCard, WrCard, OK;
   5
   6   FROM Storage IMPORT
   7     ALLOCATE;
   8
   9   CONST
  10     MaxBrGrad = 50;
  11
  12   TYPE
  13     Lista = POINTER TO Grad;
  14     Grad = RECORD
  15              Info: CARDINAL;
  16              Veza: Lista;
  17            END;
  18     Mreza = ARRAY  [1 .. MaxBrGrad] OF Lista;
  19     Posecen = ARRAY [1 .. MaxBrGrad] OF BOOLEAN;
  20
  21   VAR
  22     m: Mreza;
  23     BrojGr: CARDINAL;
  24     GPoc, GKra: CARDINAL;
  25
  26   PROCEDURE Ubaci(VAR L: Lista; G: CARDINAL);
  27     VAR
  28       Tek, Novi: Lista;
  29   BEGIN
  30     IF (L = NIL) OR (G < L^.Info) THEN
  31       NEW(Novi);
  32       Novi^.Info:= G;
  33       Novi^.Veza:= L;
  34       L:= Novi;
  35     ELSE
  36       Tek:= L;
  37       WHILE (Tek^.Veza # NIL) AND (Tek^.Veza^.Info < G) DO
  38         Tek:= Tek^.Veza;
  39       END;
  40       IF (Tek^.Veza = NIL) OR (Tek^.Veza^.Info > G) THEN
  41         NEW(Novi);
  42         Novi^.Info:= G;
  43         Novi^.Veza:= Tek^.Veza;
  44         Tek^.Veza:= Novi;
  45       END;
  46     END;
  47   END Ubaci;
  48
  49   PROCEDURE Povezi(G1, G2: CARDINAL);
  50   BEGIN
  51     Ubaci(m[G1], G2);
  52     Ubaci(m[G2], G1);
  53   END Povezi;
  54
  55   PROCEDURE Unos(VAR G1, G2: CARDINAL);
  56     VAR
  57       G: CARDINAL;
  58   BEGIN
  59     REPEAT
  60       WrStr('Unesite broj gradova (od 2 do ');
  61       WrCard(MaxBrGrad, 1);
  62       WrStr(') ---- ');
  63       BrojGr:= RdCard();
  64       WrLn;
  65     UNTIL OK AND (2 <= BrojGr) AND (BrojGr <= MaxBrGrad);
  66     FOR G:= 1 TO BrojGr DO
  67       m[G]:= NIL;
  68     END;
  69     REPEAT
  70       WrStr('Unesite dva grada koji su povezani linijom.');
  71       REPEAT
  72         WrLn;
  73         WrStr('Unesite red. br. prvog grada (ili 0 za kraj unosa linija) -- ');
  74         G1:= RdCard()
  75       UNTIL OK AND (G1 <= BrojGr);
  76       IF G1 > 0 THEN
  77         REPEAT
  78           WrStr('Unesite red. br. drugog grada ------------------------------ ');
  79           G2:= RdCard();
  80         UNTIL OK AND (1 <= G2) AND (G2 <= BrojGr) AND (G1 # G2);
  81         Povezi(G1, G2);
  82       END;
  83       WrLn;
  84     UNTIL G1 = 0;
  85     REPEAT
  86       WrLn;
  87       WrLn;
  88       WrStr('Unesite red. br. pocetnog grada -- ');
  89       G1:= RdCard();
  90     UNTIL OK AND (1 <= G1) AND (G1 <= BrojGr);
  91     REPEAT
  92       WrLn;
  93       WrStr('Unesite red. br ciljnog grada -- ');
  94       G2:= RdCard();
  95     UNTIL OK AND (1 <= G2) AND (G2 <= BrojGr) AND (G1 # G2);
  96   END Unos;
  97
  98   PROCEDURE NadjiPut(Od, Do, brojGr : CARDINAL);
  99     VAR
 100      Pos: Posecen;
 101      Reseno: BOOLEAN;
 102      i: CARDINAL;
 103      Resenje: ARRAY [1 .. MaxBrGrad] OF CARDINAL;
 104
 105     PROCEDURE Pokusaj(Od, Br: CARDINAL; VAR Reseno: BOOLEAN);
 106       VAR
 107         Pok: Lista;
 108     BEGIN
 109       Pos[Od]:= TRUE;
 110       Resenje[Br]:= Od;
 111       IF Od = Do THEN
 112         Reseno:= TRUE;
 113         WrLn;
 114         WrStr('Put koji treba precji je sledeci:');
 115         WrLn;
 116         FOR i:= 1 TO Br DO
 117           WrCard(Resenje[i], 4);
 118         END;
 119       ELSE
 120         Pok:= m[Od];
 121         WHILE (Pok # NIL) AND NOT Reseno DO
 122           WHILE (Pok # NIL) AND Pos[Pok^.Info]  DO
 123             Pok:= Pok^.Veza;
 124           END;
 125           IF Pok # NIL THEN
 126             Pokusaj(Pok^.Info, Br + 1, Reseno);
 127           END;
 128         END;
 129       END;
 130     END Pokusaj;
 131
 132   BEGIN
 133     Reseno:= FALSE;
 134     FOR i:= 1 TO BrojGr DO
 135       Pos[i]:= FALSE;
 136     END;
 137     Pokusaj(Od, 1, Reseno);
 138   END NadjiPut;
 139
 140 BEGIN
 141   Unos(GPoc, GKra);
 142   NadjiPut(GPoc, GKra, BrojGr);
 143 END Put.