skripta-spa1-sadrzaj.tex

   1 % skripta-spa1-sadrzaj.tex
   2 % Skripta za predmet Strukture podataka i algoritmi 1, DMI, PMF, NS
   3 % ovaj fajl sadrzi glavni sadrzaj skripte koji se ukljucuje u jedan
   4 % od pomocnih fajlova koji ce primeniti adekvatna formatiranja,
   5 % npr za jednu ili dve kolone
   6
   7 % osnovne informacije koje ce se prikazati na naslovnoj strani,
   8 % kao i u informacijama u generisanom pdfu
   9 \newcommand{\autor}{Vladimir Kurbalija, Milos Radovanovic, Doni Pracner}
  10 \newcommand{\naslov}{Skripta za vezbe iz predmeta "Strukture podataka
  11   i algoritmi 1"}
  12 \newcommand{\datum}{Februar 2013, Novi Sad}
  13 \newcommand{\verzija}{ver 13a-\varijacija}
  14 %varijacija je definisana u fajlu koji ukljucuje ovaj
  15
  16 \title{\naslov -- \verzija}
  17 \author{\autor}
  18 \date{\datum}
  19
  20 %change the default font
  21 \usepackage{lmodern}
  22 \usepackage{beramono}
  23 \renewcommand{\familydefault}{\sfdefault}
  24
  25 \usepackage{pifont}
  26
  27 %podesavanja outputa za pdf verzije
  28 \usepackage[bookmarks,pdffitwindow=false,unicode=true,%
  29 pdftitle={\naslov -- \verzija},%
  30 pdfauthor={\autor}%
  31 ]{hyperref}
  32
  33 \usepackage{graphicx}
  34 \usepackage{listings}
  35 \usepackage{amsthm}
  36 \usepackage{amsmath}
  37 \usepackage{latexsym}
  38 \usepackage{multicol}
  39
  40 \begin{document}
  41
  42 %customize the itemize environments
  43
  44 \let\olditemize=\itemize
  45 \def\itemize{
  46 \olditemize
  47   \setlength{\itemsep}{1pt}
  48   \setlength{\parskip}{0pt}
  49   \setlength{\parsep}{0pt}
  50   \setlength{\topsep}{-1cm}
  51   \setlength{\partopsep}{1pt}
  52 }
  53
  54 %% specijalni blokovi koji služe kao podsetnici u radu ili napomene
  55 \newcommand{\skica}[1]{
  56     \noindent \framebox{\parbox[c]{0.9\textwidth}{  {\small** \textit{#1}  }}
  57     \newline }
  58 }
  59
  60 \newcommand{\skicas}[1]{
  61     \framebox{* \textit{#1} *}
  62 }
  63
  64 %boldovane skice visokog prioriteta
  65 \newcommand{\skicab}[1]{
  66   \noindent \framebox{\parbox[c]{0.9\textwidth}{ {\small***
  67         \textbf{#1} }} \newline } }
  68
  69 \newcommand{\kod}[1]{{\small\texttt{#1}}}
  70
  71 % ako je sledeci red odkomentarisan nista od skica nece biti ispisano
  72 % u finalni dokument
  73
  74 % \renewcommand{\skica}[1]{}
  75
  76 % title u skladu sa uobičajenim na Departmanu
  77 \newcommand{\makemytitle}{
  78   \begin{center}
  79         \makebox{%
  80         \includegraphics[width=2cm]{grbPMF}
  81         \parbox[b]{65ex}{\centering
  82                 Univerzitet u Novom Sadu\\
  83                 Prirodno-matematički fakultet\\
  84                 Departman za matematiku i informatiku}
  85         \includegraphics[width=2cm]{grbUNS}
  86         }
  87         \vspace{10ex}
  88
  89         \parbox[b]{\textwidth}{{\Large {\bf
  90               Vladimir Kurbalija, \href{mailto:kurba@dmi.rs}{kurba@dmi.rs}\\
  91               Miloš Radovanović, \href{mailto:radacha@dmi.rs}{radacha@dmi.rs}\\
  92               Doni Pracner, \href{mailto:doni.pracner@dmi.rs}{doni.pracner@dmi.rs}}}}
  93         \vspace{5ex}
  94
  95         {\Large {\bf Skripta za vežbe iz predmeta }}
  96
  97         {\Huge {\bf
  98             \setlength{\baselineskip}{1.5\baselineskip}Strukture
  99               podataka i algoritmi 1}}
 100
 101         \vspace{5ex}
 102         %\vfill
 103
 104         \verzija \ -- \datum
 105
 106         \end{center}
 107         \thispagestyle{plain}
 108 %       \newpage
 109 }
 110
 111 \makemytitle
 112
 113 % theorems, definition etc.
 114 %''''''''''''''''''''''''''
 115
 116 \theoremstyle{definition}
 117 \newtheorem{def1}{Definicija}
 118 \theoremstyle{plain}
 119 \newtheorem{theo}{Teorema}
 120 \newtheorem{lema}{Lema}
 121
 122 \lstloadlanguages{Modula-2}
 123
 124 \lstset{
 125         basicstyle=\footnotesize\ttfamily,
 126         showstringspaces=false,
 127         breaklines=true
 128 }
 129
 130 \lstdefinestyle{codeblock}{
 131         basicstyle=\footnotesize\ttfamily,
 132         keywordstyle=\textbf,
 133         columns=[l]fixed,
 134         breakatwhitespace=true,
 135 %        prebreak=\P,
 136 %        postbreak=\ding{229}\space,
 137         language=Modula-2
 138 }
 139
 140 \lstdefinestyle{numcodeblock}{
 141   style=codeblock,
 142   numbers=left
 143 }
 144
 145 \lstnewenvironment{codeblock}{\lstset{style=codeblock}}{}
 146
 147
 148 % ----------------==================--------------------------------------
 149 %                 Pravi pocetak rada
 150
 151
 152 Programi u ovoj skripti su testirani sa kompajlerom 'Native XDS Modula
 153 2'. Za verzije pre 2.60 je neophodno dodatno instalirati i TSCP (Top
 154 Speed Compatibility Pack), pošto je potreban za neke od modula koji se
 155 ne nalaze u ISO standardu Module 2. U novijim verzijama su i ovi
 156 moduli uključeni u standardnu instalaciju.
 157
 158 Sav sadržaj se može koristiti u skladu sa {\ttfamily CC-BY-NC-SA} licencom. \url{http://creativecommons.org/licenses/by-nc-sa/3.0/}
 159
 160 \tableofcontents
 161
 162 %\newpage
 163
 164 \mainstart
 165
 166 \section{Ilustracija efikasnosti algoritma}
 167
 168 \subsection{Zadatak: Pronaći sve pitagorine
 169 trojke do zadate granice}
 170
 171 Pitagorina trojka su tri broja $a,b,c$ za koje važi $a^2 + b^2 = c^2\\$
 172
 173 \begin{lstlisting}[style=codeblock]
 174 MODULE Trojke1;
 175 (* Pitagorine trojke koriscenjem "Brute-force" *)
 176 FROM InOut IMPORT WriteString, WriteLn, WriteCard;
 177 CONST
 178   Gr = 100;
 179 VAR
 180   a, b, c : [1 .. Gr];
 181 BEGIN
 182   FOR a := 1 TO Gr DO
 183     FOR b := 1 TO Gr DO
 184       FOR c := 1 TO Gr DO
 185         IF a*a + b*b = c*c THEN
 186           WriteLn;
 187           WriteString('a = ');
 188           WriteCard(a,2);
 189           WriteString(', b = ');
 190           WriteCard(b,2);
 191           WriteString(', c = ');
 192           WriteCard(c,2)
 193         END
 194       END
 195     END
 196   END
 197 END Trojke1.
 198 \end{lstlisting}
 199
 200 \begin{codeblock}
 201 MODULE Trojke2;
 202 (*Pitagorine trojke koriscenjem zaokrugljivanja*)
 203 FROM InOut IMPORT WriteString, WriteLn, WriteCard;
 204 FROM MathLib0 IMPORT sqrt;
 205 CONST
 206   Gr = 100;
 207 VAR
 208   a, b, c : CARDINAL;
 209   creal : REAL;
 210 BEGIN
 211   FOR a := 1 TO Gr DO
 212     FOR b := 1 TO Gr DO
 213       creal := FLOAT(a*a) + FLOAT(b*b);
 214       creal := sqrt(creal);
 215       c := TRUNC(creal);
 216       IF creal = FLOAT(c) THEN
 217         WriteLn;
 218         WriteString(' a = ');
 219         WriteCard(a,2);
 220         WriteString(', b = ');
 221         WriteCard(b,2);
 222         WriteString(', c = ');
 223         WriteCard(c,2)
 224       END
 225     END
 226   END
 227 END Trojke2.
 228 \end{codeblock}
 229
 230 Sledeći primer koristi Euklidovu teoremu i malo drugačiji pristup.
 231 Ako uzmemo neka dva prirodna broja $m$ i $n$, tada se iz njih može
 232 izvesti jedna Pitagorina trojka koja lako zadovoljava potrebne uslove:
 233 \[
 234 \begin{array}{l}
 235 a = 2mn\\
 236 b = m^2 - n^2\\
 237 c = m^2 + n^2
 238 \end{array}
 239 \]
 240 Odnosno kad probamo da proverimo da li je ovo
 241 Pitagorina trojka dobijamo:
 242 \[
 243 \begin{array}{r@=l}
 244 a^2 + b^2 & c^2\\
 245 (2mn)^2 + (m^2 - n^2)^2 & (m^2 + n^2)^2
 246 \end{array}
 247 \]
 248
 249 \begin{codeblock}
 250 MODULE Trojke3;
 251 (* Pitagorine trojke koriscenjem teoreme *)
 252 FROM InOut IMPORT WriteString, WriteLn, WriteCard;
 253 CONST
 254   Gr = 10;
 255 VAR
 256   a, b, c, m, n : CARDINAL;
 257 BEGIN
 258   FOR m := 1 TO Gr DO
 259     FOR n := 1 TO m-1 DO
 260       a := 2*m*n;
 261       b := m*m - n*n;
 262       c := m*m + n*n;
 263       WriteLn;
 264       WriteString('a = ');
 265       WriteCard(a,2);
 266       WriteString(', b = ');
 267       WriteCard(b,2);
 268       WriteString(', c = ');
 269       WriteCard(c,2)
 270     END
 271   END
 272 END Trojke3.
 273 \end{codeblock}
 274
 275 Sledeća dva metoda traže trojke sa nekim specifičnim osobinama.
 276
 277 \begin{codeblock}
 278 MODULE Trojke4;
 279 (* Pitagorine trojke kod kojih je razlika
 280    izmedju katete i hipotenuze tacno 1 *)
 281 FROM InOut IMPORT WriteString, WriteLn, WriteCard;
 282 CONST
 283   Gr = 10;
 284 VAR
 285   a, b, c, m, n : CARDINAL;
 286 BEGIN
 287   FOR m := 2 TO Gr DO
 288     n := m - 1;
 289     a := 2*m*n;
 290     b := m*m - n*n;
 291     c := m*m + n*n;
 292     WriteLn;
 293     WriteString('a = ');
 294     WriteCard(a,2);
 295     WriteString(', b = ');
 296     WriteCard(b,2);
 297     WriteString(', c = ');
 298     WriteCard(c,2)
 299   END
 300 END Trojke4.
 301 \end{codeblock}
 302
 303 \begin{lstlisting}[style=codeblock]
 304 MODULE Trojke5;
 305 (* Pitagorine trojke kod kojih je razlika
 306    izmedju kateta jedan *)
 307 FROM InOut IMPORT WriteString, WriteLn, WriteCard;
 308 CONST
 309   Gr = 7;
 310 VAR
 311   a, b, c, m, n, w, i, temp : CARDINAL;
 312 BEGIN
 313   w := 1;
 314   n := 0;
 315   FOR i := 1 TO Gr DO
 316     m := n + w;
 317     a := 2*m*n;
 318     b := m*m - n*n;
 319     c := m*m + n*n;
 320     WriteLn;
 321     WriteString('a = ');
 322     WriteCard(a,2);
 323     WriteString(', b = ');
 324     WriteCard(b,2);
 325     WriteString(', c = ');
 326     WriteCard(c,2);
 327     temp := w;
 328     w := 3*w + 4*n;
 329     n := 2*temp + 3*n
 330   END
 331 END Trojke5.
 332 \end{lstlisting}
 333
 334 \manbreakJK
 335
 336 \subsection[Zadatak: Maksimalna suma susednih elemenata u
 337 nizu]{Zadatak: Maksimalna suma proizvoljnog broja susednih elemenata u
 338   nizu celih brojeva}
 339
 340 \begin{lstlisting}[style=codeblock]
 341 MODULE MaxNiza1;
 342 (* Prvo resenje. Brute Force: O(n^3)  *)
 343 FROM InOut IMPORT WriteString,ReadInt,
 344            WriteInt,WriteCard,WriteLn;
 345 CONST
 346   N = 10;
 347 TYPE
 348   Interval = [1..N];
 349 VAR
 350   Max, Suma : INTEGER;
 351   d,g,i,Ood,Doo : Interval;
 352   X : ARRAY Interval OF INTEGER;
 353 BEGIN
 354   WriteString(' Unesite niz X ');
 355   WriteLn;
 356   FOR i := 1 TO N DO
 357     ReadInt(X[i]);
 358     WriteLn
 359   END;
 360   Max := 0;
 361   FOR d := 1 TO N DO
 362     FOR g := 1 TO N DO
 363       Suma := 0;
 364       FOR i := d TO g DO
 365         Suma := Suma + X[i]
 366       END;
 367       IF Suma > Max THEN
 368         Max := Suma;
 369         Ood := d;
 370         Doo := g
 371       END
 372     END
 373   END;
 374   WriteLn;
 375   WriteString(' Maksimum je ');
 376   WriteInt(Max,3);
 377   WriteString(' u intervalu od ');
 378   WriteCard(Ood,3);
 379   WriteString(' do ');
 380   WriteCard(Doo,3)
 381 END MaxNiza1.
 382
 383 MODULE MaxNiza2;
 384 (* Drugo resenje: O(n^2).
 385    Koristi se cinjenica da je suma X[d..g]
 386    izracunljiva iz X[d..g-1].  *)
 387 FROM InOut IMPORT WriteString,ReadInt,
 388            WriteInt,WriteCard,WriteLn;
 389 CONST
 390   N = 10;
 391 TYPE
 392   Interval = [1..N];
 393 VAR
 394   Max, Suma : INTEGER;
 395   d,g,i,Ood,Doo : Interval;
 396   X : ARRAY Interval OF INTEGER;
 397 BEGIN
 398   WriteString(' Unesite niz X ');
 399   WriteLn;
 400   FOR i := 1 TO N DO
 401     ReadInt(X[i]);
 402     WriteLn
 403   END;
 404   Max := 0;
 405   FOR d := 1 TO N DO
 406     Suma := 0;
 407     FOR g := d TO N DO
 408       Suma := Suma + X[g];
 409       IF Suma > Max THEN
 410         Max := Suma;
 411         Ood := d;
 412         Doo := g
 413       END
 414     END
 415   END;
 416   WriteLn;
 417   WriteString(' Maksimum je ');
 418   WriteInt(Max,3);
 419   WriteString(' u intervalu od ');
 420   WriteCard(Ood,3);
 421   WriteString(' do ');
 422   WriteCard(Doo,3)
 423 END MaxNiza2.
 424 \end{lstlisting}
 425
 426 \begin{codeblock}
 427 MODULE MaxNiza3;
 428 (* Trece resenje: O(n^2).
 429    Koristi pomocni niz u kome je na i-tom mestu
 430    suma podniza x[1..i] *)
 431 FROM InOut IMPORT WriteString,ReadInt,
 432            WriteInt,WriteCard,WriteLn;
 433 CONST
 434   N = 10;
 435 TYPE
 436   Interval = [1..N];
 437 VAR
 438   Max, Suma : INTEGER;
 439   d,g,i,Ood,Doo : Interval;
 440   X : ARRAY Interval OF INTEGER;
 441   Pom : ARRAY [0..N] OF INTEGER;
 442 BEGIN
 443   WriteString(' Unesite niz X ');
 444   WriteLn;
 445   FOR i := 1 TO N DO
 446     ReadInt(X[i]);
 447     WriteLn
 448   END;
 449   Pom[0] := 0;
 450   FOR i := 1 TO N DO
 451     Pom[i] := Pom[i-1] + X[i]
 452   END;
 453   Max := 0;
 454   FOR d := 1 TO N DO
 455     FOR g := d TO N DO
 456       Suma := Pom[g] - Pom[d-1];
 457       IF Suma > Max THEN
 458         Max := Suma;
 459         Ood := d;
 460         Doo := g
 461       END
 462     END
 463   END;
 464   WriteLn;
 465   WriteString(' Maksimum je ');
 466   WriteInt(Max,3);
 467   WriteString(' u intervalu od ');
 468   WriteCard(Ood,3);
 469   WriteString(' do ');
 470   WriteCard(Doo,3)
 471 END MaxNiza3.
 472 \end{codeblock}
 473
 474 \begin{codeblock}
 475 MODULE MaxNiza4;
 476 (* Cetvrto resenje. Najbolje moguce: O(n)  *)
 477 FROM InOut IMPORT WriteString,ReadInt,
 478            WriteInt,WriteCard,WriteLn;
 479 CONST
 480   N = 10;
 481 TYPE
 482   Interval = [1..N];
 483 VAR
 484   Max, MaxDovde : INTEGER;
 485   i,d,Ood,Doo : Interval;
 486   X : ARRAY Interval OF INTEGER;
 487 BEGIN
 488   WriteString(' Unesite niz X ');
 489   WriteLn;
 490   FOR i := 1 TO N DO
 491     ReadInt(X[i]);
 492     WriteLn
 493   END;
 494   Max := 0;
 495   MaxDovde := 0;
 496   FOR i := 1 TO N DO
 497     IF MaxDovde = 0 THEN
 498       d := i
 499     END;
 500     MaxDovde := MaxDovde + X[i];
 501     IF MaxDovde < 0 THEN
 502       MaxDovde := 0
 503     END;
 504     IF MaxDovde > Max THEN
 505       Ood := d;
 506       Doo := i;
 507       Max := MaxDovde
 508     END
 509   END;
 510   WriteLn;
 511   WriteString(' Maksimum je ');
 512   WriteInt(Max,3);
 513   WriteString(' u intervalu od ');
 514   WriteCard(Ood,3);
 515   WriteString(' do ');
 516   WriteCard(Doo,3)
 517 END MaxNiza4.
 518 \end{codeblock}
 519
 520 \section{Stringovi}
 521
 522
 523 Stringovi -- odnosno nizovi znakova -- ne postoje kao ugrađeni tip u
 524 jeziku Modula 2. Ovo daje slobodu da se niz znakova definiše na dužinu
 525 najadekvatniju za konkretnu primenu. U opštem slučaju definišemo npr:
 526 \begin{codeblock}
 527   TYPE
 528      String = ARRAY [1..30] OF CHAR;
 529 \end{codeblock}
 530
 531 Operacije nad stringovima se najčešće uvoze iz modula \kod{Str}. One
 532 sve prihvataju \emph{otvorene nizove znakova} (strukture definisane sa
 533 \kod{ARRAY OF CHAR}), tako da im se može proslediti niz proizvoljne
 534 dužine.
 535
 536 Određivanje stvarne dužine stringa (tj koliko od maksimalnog
 537 kapaciteta niza je zapravo zauzeto sadržajem) se može izvesti na
 538 sledeći način:
 539 \begin{codeblock}
 540      duzina := Length(str)
 541 \end{codeblock}
 542
 543 Leksikografsko poređenje dva stringa se ne može vršiti standardnim
 544 operatorima kao što su \kod{< > =}. Ovo je delom zato što se radi o
 545 nizovima, a delom i zato što se ne vidi direktno koji deo niza je
 546 popunjen stvarnim sadržajem. Za ovo se koristi komanda \kod{Compare},
 547 koja prihvata dva stringa kao parametre, a vraća broj koji predstavlja
 548 njihov odnos. Taj broj će biti 0 ako su stringovi jednaki, veći
 549 od nule ako je prvi string ``veći'', i manji od nule ako je prvi
 550 string ``manji''. Ovo se lako pamti kad primetimo da je odnos
 551 između \kod{Compare} i 0 isti kao i između prvog i drugog stringa.
 552
 553 \begin{codeblock}
 554   IF    Compare(str1, str2) > 0 THEN
 555      WriteString("Prvi string je veci");
 556   ELSIF Compare(str1, str2) < 0 THEN
 557      WriteString("Prvi string je manji");
 558   ELSE (* moraju biti jednaki *)
 559      WriteString("Jednaki su");
 560   END;
 561 \end{codeblock}
 562
 563 Postoji i modul \kod{Strings} koji ima nešto drugačije definisane
 564 procedure, no na njih se sada nećemo fokusirati.
 565
 566 \section{Rad sa fajlovima}
 567
 568 \subsection{Modul FIO}
 569
 570 U ovom modulu je definisan tip \kod{File}, koji predstavlja jedan fajl
 571 sa kojim radimo. Da bi ga koristili moramo ga uvesti u program (isto
 572 kao što uvozimo i komande).
 573
 574 \begin{quote}U primerima se pretpostavlja da je ``f'' tipa \kod{File}, ``str'' niz
 575 znakova, ``i'' tipa \kod{INTEGER}, ``c'' tipa \kod{CARDINAL} i ``ch''
 576 tipa \kod{CHAR}. Dodatna promenljiva ``n'' tipa \kod{INTEGER} služi za
 577 formatiranje slično kao u modulu \kod{InOut}.
 578 \end{quote}
 579
 580 Promenljiva tipa \kod{File} se mora vezati za neki fajl
 581 jednom od sledećih komandi:
 582 \begin{itemize}
 583 \item \kod{f := Open(str);} -- otvara se postojeci fajl za čitanje\\
 584 \item \kod{f := Create(str);} -- kreira se fajl za pisanje\\
 585 \item \kod{f := Append(str);} -- otvara se postojeći fajl za
 586   dopisivanje na kraj
 587 \end{itemize}
 588
 589 Po završetku rada fajl se mora zatvoriti, u našem primeru to bi bilo
 590 \kod{Close(f);}
 591
 592 Procedure za čitanje i pisanje su vrlo slične onima iz modula
 593 \kod{IO}, osim što imaju dodatni parametar „\kod{f}“ koji označava
 594 fajl sa kojim se radi.
 595 \begin{itemize}
 596 \item \kod{RdStr(f,str)} -- učitava ceo red u string str\\
 597 \item   \kod{RdItem(f,str)} -- učitava jednu reč u string str (učitava znakove iz fajla dok ne naiđe na separator)\\
 598 \item   \kod{i:= RdInt(f); c:= RdCard(f)} -- učitava broj, koji se dobija kao rezultat procedure\\
 599 \item   \kod{ch:= RdChar(f)} -- vraća jedan znak iz fajla
 600 \end{itemize}
 601
 602 Analogne su i procedure za pisanje različitih tipova u fajl:
 603 \begin{itemize}
 604 \item \kod{WrStr(f,str); WrInt(f,i,n);}\ \kod{WrCard(f,c,n);}\
 605   \kod{WrChar(f,ch);}
 606 \end{itemize}
 607
 608
 609 Prelom reda se eksplicitno upisuje u fajl komandom \kod{WrLn(f);}.
 610
 611 Da bi odredili da li smo stigli do kraja fajla možemo koristiti
 612 \kod{EOF}. U pitanju je logička promenljiva koja se uvozi iz modula
 613 FIO kao bilo kakva normalna komanda. Ona označava da li smo poslednjom
 614 operacijom čitanja stigli do kraja fajla.  Ne menja joj se vrednost
 615 pri operacijama otvaranja i zatvaranja fajlova, odnosno neće se pri
 616 tome resetovati na \kod{FALSE}, pa na ovo treba obratiti pažnju pri
 617 radu.
 618
 619 \subsection{Zadatak: ispis sadržaja fajla na ekran}
 620
 621 Potrebno je sve redove iz fajla učitati i ispisati ih na ekran.
 622
 623 \begin{lstlisting}[style=codeblock]
 624 MODULE ispis;
 625 FROM FIO IMPORT File, Open, Close, EOF, RdStr;
 626 FROM InOut IMPORT WriteString, WriteLn, ReadString;
 627
 628 PROCEDURE ispisF(ime: ARRAY OF CHAR);
 629 VAR
 630   f:File;
 631   s : ARRAY[1..100] OF CHAR;
 632 BEGIN
 633   f:=Open(ime);
 634   EOF := FALSE;
 635   WHILE NOT EOF DO
 636       RdStr(f,s);
 637       WriteString(s);
 638       WriteLn;
 639   END;
 640   Close(f);
 641 END ispisF;
 642
 643 VAR
 644   ime: ARRAY[1..100] OF CHAR;
 645 BEGIN
 646   WriteString("unesite ime fajla:");
 647   ReadString(ime);
 648   ispisF(ime);
 649 END ispis.
 650 \end{lstlisting}
 651
 652 \subsection{Zadatak: spisak studenata}
 653
 654 Napraviti program koji iz fajla učitava podatke o studentima, dodaje
 655 novog studenta u spisak i snima fajl.  U fajlu se u svakom redu nalazi
 656 podatak o jednom studentu, redom prezime, ime i godina rođenja,
 657 razdvojeni razmacima.
 658
 659 \begin{lstlisting}[style=codeblock]
 660 MODULE nizslog;
 661 FROM InOut IMPORT WriteString, WriteLn,
 662      WriteCard, ReadCard, ReadString;
 663 FROM FIO IMPORT File, Open, Create, Close, EOF,
 664     RdItem, RdCard, WrStr, WrCard, WrLn;
 665 FROM Str IMPORT Compare;
 666
 667 CONST
 668     MaxStud = 100;
 669 TYPE
 670     String = ARRAY[1..30] OF CHAR;
 671     Student = RECORD
 672         ime, prez: String;
 673         god: CARDINAL;
 674     END;
 675     Studenti = ARRAY[1..MaxStud] OF Student;
 676
 677 PROCEDURE UcitajF(fajl:String;
 678           VAR spisak: Studenti; VAR n:CARDINAL);
 679 VAR
 680     f:File;
 681 BEGIN
 682     n:=0;
 683     f:= Open(fajl);
 684     EOF := FALSE;
 685     WHILE NOT EOF DO
 686         INC(n);
 687         RdItem(f, spisak[n].prez);
 688         RdItem(f, spisak[n].ime);
 689         spisak[n].god := RdCard(f);
 690     END;
 691     Close(f);
 692 END UcitajF;
 693
 694 PROCEDURE Ispisi(spisak:Studenti; n:CARDINAL);
 695 VAR
 696     i: CARDINAL;
 697 BEGIN
 698     FOR i:=1 TO n DO
 699         WriteString(spisak[i].prez);
 700         WriteString(" ");
 701         WriteString(spisak[i].ime);
 702         WriteString(" ");
 703         WriteCard(spisak[i].god,1);
 704         WriteLn;
 705     END;
 706 END Ispisi;
 707
 708 PROCEDURE IspisiF(fajl:String;
 709           spisak:Studenti; n:CARDINAL);
 710 VAR
 711     f:File;
 712     i: CARDINAL;
 713 BEGIN
 714     IF (n>0) AND (n<=MaxStud) THEN
 715         f:=Create(fajl);
 716         (* pravimo takav fajl da ne
 717            postoji zadnji prazan red *)
 718         FOR i:=1 TO n-1 DO
 719             WrStr(f,spisak[i].prez);
 720             WrStr(f," ");
 721             WrStr(f,spisak[i].ime);
 722             WrStr(f," ");
 723             WrCard(f,spisak[i].god,1);
 724             WrLn(f);
 725         END;
 726         WrStr(f,spisak[n].prez);
 727         WrStr(f," ");
 728         WrStr(f,spisak[n].ime);
 729         WrStr(f," ");
 730         WrCard(f,spisak[n].god,1);
 731         Close(f);
 732     END;
 733 END IspisiF;
 734
 735 PROCEDURE NoviStudent(VAR spisak:Studenti;
 736                       VAR n:CARDINAL);
 737 VAR
 738     stud,temp:Student;
 739     i:CARDINAL;
 740     dodaj:BOOLEAN;
 741 BEGIN
 742     IF n<MaxStud THEN
 743         WriteString("Prezime novog studenta?");
 744         ReadString(stud.prez);
 745         WriteString("Ime novog studenta?");
 746         ReadString(stud.ime);
 747         WriteString("Godina rodjenja");
 748         WriteString("novog studenta?");
 749         ReadCard(stud.god);
 750         (* proverimo da li vec postoji *)
 751         i:=1;
 752         dodaj := TRUE;
 753         WHILE (i<=n) AND dodaj DO
 754             temp := spisak[i];
 755             IF (temp.god = stud.god) &
 756               (Compare(temp.prez,stud.prez)=0) &
 757               (Compare(temp.ime,stud.ime)=0) THEN
 758                 dodaj:=FALSE;
 759             END;
 760             INC(i);
 761         END;
 762         IF dodaj THEN
 763             INC(n);
 764             spisak[n]:=stud;
 765         ELSE
 766             WriteString("podaci vec postoje!");
 767         END;
 768     ELSE
 769         WriteString("popunjen kapacitet!");
 770     END;
 771 END NoviStudent;
 772
 773 VAR
 774     spisak : Studenti;
 775     fajl:String;
 776     n:CARDINAL;
 777 BEGIN
 778     fajl:="studenti.txt";
 779     UcitajF(fajl, spisak, n);
 780     Ispisi(spisak, n);
 781     NoviStudent(spisak,n);
 782     IspisiF(fajl, spisak, n);
 783 END nizslog.
 784 \end{lstlisting}
 785
 786 \section{Liste i pokazivači}
 787
 788 Za rad sa pokazivačima je potrebno iz modula \kod{Storage} uvesti procedure
 789 \kod{ALLOCATE} i \kod{DEALLOCATE}. U kodu se tada mogu koristiti i njihovi
 790 skraćeni oblici \kod{NEW} i \kod{DISPOSE}.
 791
 792 \subsection{Zadatak: Formiranje, štampanje i brisanje listi}
 793
 794
 795 \begin{lstlisting}[style=codeblock]
 796 MODULE liste;
 797 FROM InOut IMPORT WriteString, WriteLn, WriteInt,
 798         ReadInt, ReadCard;
 799 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
 800 TYPE
 801   brojevi = POINTER TO brojSlog;
 802   brojSlog = RECORD
 803       info:INTEGER;
 804       veza:brojevi;
 805   END;
 806 VAR
 807   n,i:CARDINAL;
 808   lista : brojevi;
 809   br:INTEGER;
 810
 811 PROCEDURE DodajPoc(VAR lista:brojevi; br:INTEGER);
 812 (* dodaje broj br na pocetak liste *)
 813 VAR
 814   temp:brojevi;
 815 BEGIN
 816   NEW(temp);
 817   temp^.info := br;
 818   temp^.veza := lista;
 819   lista := temp;
 820 END DodajPoc;
 821
 822 PROCEDURE Stampaj(lista:brojevi);
 823 VAR
 824   temp:brojevi;
 825 BEGIN
 826   temp:=lista;
 827   WHILE temp # NIL DO
 828       WriteInt(temp^.info,0);
 829       WriteLn;
 830       temp := temp^.veza;
 831   END;
 832 END Stampaj;
 833
 834 PROCEDURE Unisti(VAR lista:brojevi);
 835 VAR
 836   temp:brojevi;
 837 BEGIN
 838   temp:=lista;
 839   WHILE temp # NIL DO
 840         lista:=lista^.veza;
 841         DISPOSE(temp);
 842         temp:=lista;
 843   END;
 844 END Unisti;
 845
 846 BEGIN
 847   lista := NIL;
 848   WriteString('unesite n (broj brojeva): ');
 849   ReadCard(n);
 850   WriteString('unesite brojeve: ');
 851   WriteLn;
 852   FOR i:= 1 TO n DO
 853       ReadInt(br);
 854       DodajPoc(lista,br);
 855   END;
 856   WriteString('sadrzaj liste:');
 857   WriteLn;
 858   Stampaj(lista);
 859   Unisti(lista);
 860   WriteString('memorija je oslobodjena');
 861   WriteLn;
 862 END liste.
 863 \end{lstlisting}
 864
 865 Alternativno je poziv \kod{DodajPoc} moguće zameniti pozivom jedne od
 866 sledeće dve procedure čime se dobija dodavanje elementa na kraj liste,
 867 ili kreiranje sortirane liste:
 868
 869 \begin{lstlisting}[style=codeblock]
 870 PROCEDURE DodajKraj(VAR lista:brojevi; br:INTEGER);
 871 (* dodaje element na kraj liste *)
 872 VAR
 873   tekuci, temp :brojevi;
 874 BEGIN
 875   NEW(temp);
 876   temp^.info := br;
 877   temp^.veza := NIL;
 878   IF lista = NIL THEN
 879      (* prazna lista *)
 880      lista:=temp;
 881   ELSE
 882      tekuci := lista;
 883      WHILE tekuci^.veza#NIL DO
 884         tekuci:=tekuci^.veza;
 885      END;
 886      tekuci^.veza := temp;
 887   END;
 888 END DodajKraj;
 889
 890 PROCEDURE DodajSort(VAR lista:brojevi; br:CARDINAL);
 891 (* dodaje broj tako da lista ostane sortirana
 892    (podrazumeva se da je vec sortirana) *)
 893 VAR
 894   temp, tekuci : brojevi;
 895 BEGIN
 896   NEW(temp);
 897   temp^.info:=br;
 898   temp^.veza:=NIL;
 899   IF (lista = NIL) OR (lista^.info>=br) THEN
 900   (*prazna lista ili na pocetak*)
 901     temp^.veza:=lista;
 902     lista := temp;
 903   ELSE
 904   (*negde u listi*)
 905     tekuci:= lista;
 906     WHILE (tekuci^.veza # NIL) AND
 907           (tekuci^.veza^.info<=br) DO
 908       tekuci:=tekuci^.veza;
 909     END;
 910     temp^.veza := tekuci^.veza;
 911     tekuci^.veza:=temp;
 912   END;
 913 END DodajSort;
 914 \end{lstlisting}
 915
 916 \subsection{Zadatak: Prikaz osnovih operacija nad listama}
 917
 918 \begin{lstlisting}[style=codeblock]
 919 MODULE liste2;
 920 FROM InOut IMPORT WriteString, WriteLn,
 921            WriteCard, ReadCard;
 922 FROM IO IMPORT RdKey;
 923 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
 924 TYPE
 925   skupZn = SET OF CHAR;
 926   brojevi = POINTER TO brojSlog;
 927   brojSlog = RECORD
 928       info:CARDINAL;
 929       veza:brojevi;
 930   END;
 931 VAR
 932   lista : brojevi;
 933   menu,prazno:CHAR;
 934
 935 PROCEDURE DodajPoc(VAR lista:brojevi; br:INTEGER);
 936 (* dodaje broj pom na pocetak liste *)
 937 VAR
 938   temp:brojevi;
 939 BEGIN
 940   (* kreiramo novi element *)
 941   NEW(temp);
 942   temp^.info := br;
 943   (* treba da pokazuje na ostatak liste *)
 944   temp^.veza := lista;
 945   (* pocetak liste je novi element *)
 946   lista := temp;
 947 END DodajPoc;
 948
 949 PROCEDURE Unos(VAR lista:brojevi);
 950 (* dodaje n brojeva u listu *)
 951 VAR
 952   n,i,br:CARDINAL;
 953 BEGIN
 954   WriteString('unesite n (broj brojeva): ');
 955   ReadCard(n);
 956   FOR i:= 1 TO n DO
 957       WriteString("unesite broj ");
 958       WriteCard(i,0);
 959       WriteString(": ");
 960       ReadCard(br);
 961       DodajPoc(lista,br);
 962   END;
 963 END Unos;
 964
 965 (* -- procedure za stampu -- *)
 966
 967 PROCEDURE Stampaj(lista:brojevi);
 968 (* stampa sadrzaj liste na ekran *)
 969 VAR
 970   temp:brojevi;
 971 BEGIN
 972   WriteLn;
 973   WriteString("Sadrzaj liste:");
 974   WriteLn;
 975   temp:=lista;
 976   WHILE temp # NIL DO
 977       WriteCard(temp^.info,0);
 978       WriteLn;
 979       temp := temp^.veza;
 980   END;
 981 END Stampaj;
 982
 983 PROCEDURE StampajK(VAR lista:brojevi);
 984 (* stampa k-ti element (k unosi korisnik) *)
 985 VAR
 986   temp:brojevi;
 987   k,brojac:CARDINAL;
 988 BEGIN
 989   WriteString("unesite redni broj elementa:");
 990   ReadCard(k);
 991   temp:=lista;
 992   brojac := 1;
 993   WHILE (temp# NIL) AND (k>brojac) DO
 994     temp:=temp^.veza;
 995     INC(brojac);
 996   END;
 997   IF (temp#NIL) THEN
 998     WriteCard(temp^.info,2);
 999   ELSE
1000     WriteString("greska! - ne postoji element");
1001     WriteString(" u listi sa rednim brojem ");
1002     WriteCard(k,2);
1003   END;
1004   WriteLn();
1005 END StampajK;
1006
1007 PROCEDURE StampajMinimum(VAR lista:brojevi);
1008 (* nalazi i stampa minimalni element liste *)
1009 VAR
1010   temp:brojevi;
1011   min:CARDINAL;
1012 BEGIN
1013   IF (lista=NIL) THEN
1014     WriteString("prazna lista!");
1015   ELSE
1016     min:=lista^.info;
1017     temp:=lista^.veza;
1018     WHILE temp # NIL DO
1019       IF temp^.info < min THEN
1020         min := temp^.info;
1021       END;
1022       temp := temp^.veza;
1023     END;
1024     WriteString("Minimalni element liste je ");
1025     WriteCard(min,0);
1026   END;
1027   WriteLn;
1028 END StampajMinimum;
1029
1030 (* -- pomocne procedure, bez ispisa  -- *)
1031
1032 PROCEDURE UListi(lista:brojevi;
1033                  br: CARDINAL):BOOLEAN;
1034 (* vraca da li se 'br' nalazi u listi 'lista' *)
1035 VAR
1036   temp:brojevi;
1037 BEGIN
1038   temp:=lista;
1039   WHILE (temp # NIL) AND (temp^.info # br) DO
1040     (* dok ne dodjemo do kraja liste
1041        ili ne nadjemo broj *)
1042       temp := temp^.veza;
1043   END;
1044   IF temp#NIL THEN
1045     (* znaci da nismo na kraju liste,
1046        tj da je nadjen broj *)
1047     RETURN TRUE;
1048   ELSE (* temp = NIL *)
1049     RETURN FALSE;
1050   END;
1051 END UListi;
1052
1053 PROCEDURE IzbaciIzListe(VAR lista:brojevi;
1054                         br: CARDINAL):BOOLEAN;
1055 (* izbacuje broj 'br' iz liste, naravno ako
1056    postoji i vraca da li je operacija uspesno
1057    obavljena *)
1058 VAR
1059   temp,prethodni:brojevi;
1060 BEGIN
1061   (* proverimo da li je prvi element *)
1062   IF (lista # NIL) AND (lista^.info = br) THEN
1063     temp:=lista;
1064     lista :=lista^.veza;
1065     DISPOSE(temp);
1066     RETURN TRUE;
1067   ELSE
1068   (* trazimo u ostatku liste *)
1069     temp:=lista;
1070     prethodni:=NIL;
1071     WHILE (temp # NIL) AND (temp^.info # br) DO
1072         (* dok ne dodjemo do kraja liste
1073            ili ne nadjemo broj *)
1074         prethodni:=temp;
1075         temp := temp^.veza;
1076     END;
1077     IF temp#NIL THEN
1078       (* znaci da nismo na kraju liste,
1079          odnosno da smo nasli broj *)
1080       (* prevezemo listu oko elementa *)
1081       prethodni^.veza:=temp^.veza;
1082       DISPOSE(temp);
1083       RETURN TRUE;
1084     ELSE
1085       RETURN FALSE;
1086     END;
1087   END;
1088 END IzbaciIzListe;
1089
1090 PROCEDURE IzbaciIzListeSve(VAR lista:brojevi;
1091                         br: CARDINAL):CARDINAL;
1092 (* izbacuje sve brojeve 'br' iz liste, naravno ako
1093    postoje i vraca koliko ih je bilo *)
1094 VAR
1095   temp,prethodni:brojevi;
1096   brojac : CARDINAL;
1097 BEGIN
1098   brojac := 0;
1099   (* uklanjamo sa pocetka koliko je potrebno *)
1100   WHILE (lista # NIL) AND (lista^.info = br) DO
1101     temp:=lista;
1102     lista :=lista^.veza;
1103     DISPOSE(temp);
1104     INC(brojac);
1105   END;
1106   (* trazimo u ostatku liste *)
1107   IF (lista # NIL) THEN
1108     temp:=lista;
1109     WHILE (temp^.veza # NIL)  DO
1110         (* idemo do poslednjeg elementa liste *)
1111         prethodni:=temp;
1112         temp := temp^.veza;
1113         IF temp^.info = br THEN
1114           (* prevezemo listu oko elementa *)
1115           prethodni^.veza:=temp^.veza;
1116           DISPOSE(temp);
1117           INC(brojac);
1118           (* vracamo se jedan korak da bi
1119           u novom krugu proverili i ovaj element *)
1120           temp := prethodni;
1121         END;
1122     END;
1123   END;
1124   RETURN brojac;
1125 END IzbaciIzListeSve;
1126
1127 (* - procedure sa interakcijom sa korisnikom - *)
1128
1129 PROCEDURE IzbacivanjeEl(VAR lista:brojevi);
1130 (* izbacuje uneti broj iz liste koristeci proceduru IzbaciIzListe *)
1131 VAR
1132   br:CARDINAL;
1133 BEGIN
1134   WriteString("unesite broj za izbacivanje: ");
1135   ReadCard(br);
1136   IF IzbaciIzListe(lista,br) THEN
1137     WriteString("broj je izbacen iz liste");
1138   ELSE
1139     WriteString("greska! - broj ne postoji");
1140   END;
1141   WriteLn;
1142 END IzbacivanjeEl;
1143
1144 PROCEDURE IzbacivanjeElSvi(VAR lista:brojevi);
1145 (* izbacuje sve primeke unetog broj iz liste
1146    koristeci proceduru IzbaciIzListeSve *)
1147 VAR
1148   br, ukupno:CARDINAL;
1149 BEGIN
1150   WriteString("unesite broj za izbacivanje: ");
1151   ReadCard(br);
1152   ukupno := IzbaciIzListeSve(lista,br);
1153   WriteString("Iz liste je izbaceno ");
1154   WriteCard(ukupno,3);
1155   WriteString(" el.");
1156   WriteLn;
1157 END IzbacivanjeElSvi;
1158
1159 PROCEDURE IzbacivanjeK(VAR lista:brojevi);
1160 (* izbacuje k-ti element iz liste *)
1161 VAR
1162   temp,tekuci:brojevi;
1163   k,brojac:CARDINAL;
1164 BEGIN
1165   IF lista=NIL THEN
1166     WriteString("lista je prazna, nema ");
1167     WriteString("elemenata za izbacivanje");
1168   ELSE
1169     WriteString("unesite redni broj elementa");
1170     WriteString(" koji zelite izbaciti:");
1171     ReadCard(k);
1172     IF k=1 THEN (*izbacivanje prvog *)
1173       temp:=lista;
1174       lista := lista^.veza;
1175       DISPOSE(temp);
1176     ELSE
1177       tekuci := lista;
1178       brojac := 2; (*gledamo jedan unapred*)
1179       WHILE (tekuci^.veza# NIL) AND (k>brojac) DO
1180         (* idemo kroz listu do k-tog el *)
1181         tekuci:=tekuci^.veza;
1182         INC(brojac);
1183       END;
1184       IF (tekuci^.veza#NIL) THEN
1185          (* pamtimo element za brisanje *)
1186          temp:=tekuci^.veza;
1187          (* prevezujemo listu oko njega*)
1188          tekuci^.veza:=tekuci^.veza^.veza;
1189          DISPOSE(temp);
1190       ELSE
1191         WriteString("greska! - ne postoji el ");
1192         WriteString("u listi sa rednim brojem ");
1193         WriteCard(k,2);
1194       END;
1195       WriteLn();
1196     END;
1197   END;
1198 END IzbacivanjeK;
1199
1200 PROCEDURE Pretraga(lista:brojevi);
1201 (* provera da li se uneti broj nalazi u listi *)
1202 VAR
1203   br:CARDINAL;
1204 BEGIN
1205   WriteString("unesite trazeni broj");
1206   ReadCard(br);
1207   IF UListi(lista,br) THEN
1208     WriteString("broj postoji u listi");
1209   ELSE
1210     WriteString("broj ne postoji u listi");
1211   END;
1212   WriteLn;
1213 END Pretraga;
1214
1215 (* -- oslobadjanje memorije -- *)
1216
1217 PROCEDURE Unisti(VAR lista:brojevi);
1218 VAR
1219   temp:brojevi;
1220 BEGIN
1221   temp:=lista;
1222   WHILE temp # NIL DO
1223         lista:=lista^.veza;
1224         DISPOSE(temp);
1225         temp:=lista;
1226   END;
1227 END Unisti;
1228
1229 BEGIN
1230   (* pocinjemo od prazne liste *)
1231   lista := NIL;
1232   REPEAT
1233      WriteLn;
1234      WriteString("Ilustracija rada sa");
1235      WriteString(" listama brojeva");
1236      WriteLn;
1237      WriteString("=============================");
1238      WriteLn;
1239      WriteString("s - Stampa");WriteLn;
1240      WriteString("u - Unos");WriteLn;
1241      WriteString("i - Izbacivanje br iz liste");
1242      WriteLn;
1243      WriteString("v - izbacivanje svih br iz liste");
1244      WriteLn;
1245      WriteString("e - izbacivanje k-tog El.");
1246      WriteLn;
1247      WriteString("k - stampanje k-tog elementa");
1248      WriteLn;
1249      WriteString("m - Minimalni broj u listi");
1250      WriteLn;
1251      WriteString("p - Pretraga el. u listi");
1252      WriteLn;
1253      WriteLn;
1254      WriteString("q - kraj rada (Quit)");WriteLn;
1255       REPEAT
1256         menu := CAP(RdKey());
1257       UNTIL menu IN skupZn{'S','U','E','I','V',
1258                            'M','K','P','Q'};
1259       IF menu#'Q' THEN
1260         CASE menu OF
1261          'S' : Stampaj(lista);|
1262          'U' : Unos(lista);|
1263          'I' : IzbacivanjeEl(lista);|
1264          'V' : IzbacivanjeElSvi(lista);|
1265          'E' : IzbacivanjeK(lista);|
1266          'K' : StampajK(lista); |
1267          'M' : StampajMinimum(lista); |
1268          'P' : Pretraga(lista);|
1269         END;
1270         WriteLn;
1271         WriteString("--- pritisnite bilo koji ");
1272         WriteString("taster za povratak u meni");
1273         prazno:=RdKey();
1274       ELSE
1275         WriteString("Kraj rada")
1276       END;
1277       WriteLn;
1278   UNTIL menu='Q';
1279   Unisti(lista);
1280 END liste2.
1281 \end{lstlisting}
1282
1283
1284 \subsection{Zadatak: Prikaz operacija nad listama sa jedinstvenim ključem}
1285
1286 \begin{lstlisting}[style=codeblock]
1287 MODULE Radnici;
1288
1289 FROM InOut IMPORT WriteString, ReadString,
1290            WriteLn, WriteCard, ReadCard, Done;
1291 FROM IO IMPORT RdKey;
1292 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1293
1294 TYPE
1295   skupZn = SET OF CHAR;
1296   str = ARRAY [1..20] OF CHAR;
1297   radnici = POINTER TO slog;
1298   slog = RECORD
1299            ime, prez : str;
1300            broj : CARDINAL;
1301            sled : radnici
1302          END;
1303 VAR
1304   meni, pom : CHAR;
1305   rad : radnici;
1306
1307   PROCEDURE Clear();
1308   VAR
1309     br: CARDINAL;
1310   BEGIN
1311     FOR br:=1 TO 100 DO
1312       WriteLn;
1313     END;
1314   END Clear;
1315
1316   PROCEDURE Spisak(rad : radnici);
1317   BEGIN
1318     WHILE rad # NIL DO
1319       WriteString(rad^.ime);
1320       WriteString(' ');
1321       WriteString(rad^.prez);
1322       WriteCard(rad^.broj, 8);
1323       WriteLn;
1324       rad := rad^.sled
1325     END
1326   END Spisak;
1327
1328   PROCEDURE Zaposli(VAR rad : radnici);
1329   VAR
1330     novi, tek : radnici;
1331     nadjen : BOOLEAN;
1332   BEGIN
1333     NEW(novi);
1334     REPEAT
1335       WriteString('Ime, prezime i jedinstveni');
1336       WriteString(' broj novog radnika: ');
1337       WriteLn;
1338       ReadString(novi^.ime);
1339       ReadString(novi^.prez);
1340       ReadCard(novi^.broj);
1341       nadjen := FALSE;
1342       tek := rad;
1343       WHILE NOT nadjen AND (tek # NIL) AND
1344             (tek^.broj <= novi^.broj) DO
1345         IF novi^.broj = tek^.broj THEN
1346           nadjen := TRUE
1347         ELSE
1348           tek := tek^.sled
1349         END
1350       END
1351     UNTIL Done AND NOT nadjen;
1352     IF (rad = NIL) OR (novi^.broj<rad^.broj) THEN
1353       novi^.sled := rad;
1354       rad := novi
1355     ELSE
1356       tek := rad;
1357       WHILE (tek^.sled # NIL) AND
1358             (tek^.sled^.broj < novi^.broj) DO
1359         tek := tek^.sled
1360       END;
1361       novi^.sled := tek^.sled;
1362       tek^.sled := novi
1363     END
1364   END Zaposli;
1365
1366   PROCEDURE Otpusti(VAR rad : radnici);
1367   VAR
1368     tek, pom : radnici;
1369     br : CARDINAL;
1370   BEGIN
1371     REPEAT
1372       WriteLn;
1373       WriteString('Unesite redni broj radnika:');
1374       ReadCard(br)
1375     UNTIL Done;
1376     WriteLn;
1377     IF rad = NIL THEN
1378       WriteString('Greska.')
1379     ELSIF br = rad^.broj THEN
1380       pom := rad;
1381       rad := rad^.sled;
1382       DISPOSE(pom)
1383     ELSE
1384       tek := rad;
1385       WHILE (tek^.sled # NIL) AND
1386             (tek^.sled^.broj < br) DO
1387         tek := tek^.sled
1388       END;
1389       IF (tek^.sled = NIL) OR
1390          (tek^.sled^.broj > br) THEN
1391         WriteString('Greska.')
1392       ELSE
1393         pom := tek^.sled;
1394         tek^.sled := tek^.sled^.sled;
1395         DISPOSE(pom)
1396       END
1397     END
1398   END Otpusti;
1399
1400   PROCEDURE Inform(rad : radnici);
1401   VAR
1402     br : CARDINAL;
1403   BEGIN
1404     REPEAT
1405       WriteLn;
1406       WriteString('Unesite redni broj radnika:');
1407       ReadCard(br)
1408     UNTIL Done;
1409     WriteLn;
1410     WHILE (rad # NIL) AND (rad^.broj < br) DO
1411       rad := rad^.sled
1412     END;
1413     IF (rad = NIL) OR (rad^.broj # br) THEN
1414       WriteString('Greska.')
1415     ELSE
1416       WriteString(rad^.ime);
1417       WriteString(' ');
1418       WriteString(rad^.prez)
1419     END
1420   END Inform;
1421
1422   PROCEDURE Bankrot(VAR rad : radnici);
1423   VAR
1424     pom : radnici;
1425   BEGIN
1426     WHILE rad # NIL DO
1427       pom := rad;
1428       rad := rad^.sled;
1429       DISPOSE(pom)
1430     END
1431   END Bankrot;
1432
1433 BEGIN
1434   rad := NIL;
1435   REPEAT
1436     Clear;
1437     WriteString('s - spisak svih zaposlenih');
1438     WriteLn;
1439     WriteString('z - zaposljavanje radnika');
1440     WriteLn;
1441     WriteString('o - otpustanje radnika');
1442     WriteLn;
1443     WriteString('i - informacije o radniku');
1444     WriteLn;
1445     WriteString('b - bankrot firme');
1446     WriteLn;
1447     WriteString('k - kraj rada');
1448     WriteLn;
1449     REPEAT
1450       meni := RdKey();
1451     UNTIL CAP(meni) IN skupZn{'S', 'Z', 'O',
1452                               'I', 'B', 'K'};
1453     Clear;
1454     IF CAP(meni) # 'K' THEN
1455       CASE CAP(meni) OF
1456         'S' : Spisak(rad)|
1457         'Z' : Zaposli(rad)|
1458         'O' : Otpusti(rad)|
1459         'I' : Inform(rad)|
1460         'B' : Bankrot(rad)
1461       END;
1462       WriteLn;
1463       WriteString('-- pritisnite bilo koji ');
1464       WriteString('taster za nastavak --');
1465       pom := RdKey()
1466     END
1467   UNTIL CAP(meni) = 'K'
1468 END Radnici.
1469 \end{lstlisting}
1470
1471 Procedura \kod{Spisak} se može realizovati i u rekurzivnoj verziji:
1472
1473 \begin{lstlisting}[style=codeblock]
1474   PROCEDURE Spisak(rad : radnici);
1475   BEGIN
1476     IF rad # NIL THEN
1477       WriteString(rad^.ime);
1478       WriteString(' ');
1479       WriteString(rad^.prez);
1480       WriteCard(rad^.broj, 8);
1481       WriteLn;
1482       Spisak(rad^.sled)
1483     END
1484   END Spisak;
1485 \end{lstlisting}
1486
1487 \subsection[Zadatak: Dve liste osoba sa istim sadržajem]{Zadatak: Dve
1488   liste osoba koje dele sadržaj, jedna sortirana po visini, druga po
1489   težini}
1490
1491 Sa tastature učitavati po dva broja koji opisuju osobu (visina i
1492 težina) i smeštati ih u povezane listu, tako da postoji neopadajuće
1493 uređenje i po visini i po težini.
1494
1495 \begin{lstlisting}[style=codeblock]
1496 MODULE VisTez;
1497 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1498 FROM IO IMPORT WrLn, WrStr, RdCard, WrCard;
1499 FROM SYSTEM IMPORT TSIZE;
1500 TYPE
1501   pok = POINTER TO element;
1502   element = RECORD
1503               visina, tezina : CARDINAL;
1504               Vveza, Tveza : pok
1505             END;
1506 VAR
1507   pocV, pocT : pok;
1508   vis, tez : CARDINAL;
1509 PROCEDURE Ispisi(pocV, pocT : pok);
1510 VAR
1511   tek : pok;
1512 BEGIN
1513   tek := pocV;
1514   WrStr('Po visini:');
1515   WrLn;
1516   WHILE tek # NIL DO
1517     WrCard(tek^.visina, 6);
1518     tek := tek^.Vveza
1519   END;
1520   WrLn;
1521   tek := pocT;
1522   WrStr('Po tezini:');
1523   WrLn;
1524   WHILE tek # NIL DO
1525     WrCard(tek^.tezina,6);
1526     tek := tek^.Tveza
1527   END
1528 END Ispisi;
1529
1530 PROCEDURE Ubaci(VAR pocV, pocT : pok;
1531                 vis, tez : CARDINAL);
1532 VAR
1533   novi, tek, iza : pok;
1534   nadjen : BOOLEAN;
1535 BEGIN
1536   IF pocV = NIL THEN
1537     ALLOCATE(pocV, TSIZE(element));
1538     pocV^.visina := vis;
1539     pocV^.tezina := tez;
1540     pocV^.Vveza := NIL;
1541     pocV^.Tveza := NIL;
1542     pocT := pocV
1543   ELSE
1544     ALLOCATE(novi, TSIZE(element));
1545     novi^.visina := vis;
1546     novi^.tezina := tez;
1547     tek := pocV;
1548     nadjen := FALSE;
1549     WHILE (tek # NIL) AND NOT nadjen DO
1550       nadjen := vis <= tek^.visina;
1551       IF NOT nadjen THEN
1552         iza := tek;
1553         tek := tek^.Vveza
1554       END
1555     END;
1556     novi^.Vveza := tek;
1557     IF tek = pocV THEN
1558       pocV := novi
1559     ELSE
1560       iza^.Vveza := novi
1561     END;
1562     tek := pocT;
1563     nadjen := FALSE;
1564     WHILE (tek # NIL) AND NOT nadjen DO
1565       nadjen := tez <= tek^.tezina;
1566       IF NOT nadjen THEN
1567         iza := tek;
1568         tek := tek^.Tveza
1569       END
1570     END;
1571     novi^.Tveza := tek;
1572     IF tek = pocT THEN
1573       pocT := novi
1574     ELSE
1575       iza^.Tveza := novi
1576     END
1577   END
1578 END Ubaci;
1579
1580 BEGIN
1581   pocV := NIL;
1582   pocT := NIL;
1583   WrStr('Unesite visinu ---- ');
1584   vis := RdCard();
1585   WHILE vis > 0 DO
1586     WrStr('Unesite tezinu ---- ');
1587     tez := RdCard();
1588     Ubaci(pocV, pocT, vis, tez);
1589     WrLn;
1590     WrStr('Unesite visinu ---- ');
1591     vis := RdCard()
1592   END;
1593   WrLn;
1594   Ispisi(pocV, pocT)
1595 END VisTez.
1596 \end{lstlisting}
1597
1598 \section{Polinomi preko listi}
1599
1600 \subsection{Moduli}
1601
1602 Polinomi su predstavljeni pomoću pokazivača. Apstraktni tip podataka
1603 \kod{Polinom} je definisan u globalnom modulu.
1604
1605 \paragraph{PolinomL.DEF} \
1606
1607 \begin{lstlisting}[style=codeblock]
1608 DEFINITION MODULE PolinomL;
1609 TYPE
1610   Polinom = POINTER TO Monom;
1611   Monom = RECORD
1612             k : REAL;
1613             st : CARDINAL;
1614             veza : Polinom
1615           END;
1616
1617 PROCEDURE Anuliraj(VAR p: Polinom);
1618 PROCEDURE Unos(VAR p: Polinom);
1619 PROCEDURE Stampaj(p: Polinom; d: CARDINAL);
1620 PROCEDURE Kopiraj(p: Polinom;
1621                   VAR kopija: Polinom);
1622 PROCEDURE UbaciMonom(mon:Polinom;
1623                      VAR p: Polinom);
1624 PROCEDURE PromeniZnak(VAR p: Polinom);
1625 PROCEDURE Saberi(p1, p2: Polinom;
1626                  VAR zbir: Polinom);
1627 PROCEDURE SaberiNa(p: Polinom; VAR rez: Polinom);
1628 PROCEDURE Oduzmi(p1,p2: Polinom;
1629                  VAR razlika: Polinom);
1630 PROCEDURE MonomPuta(p, mon: Polinom;
1631                     VAR mp : Polinom);
1632 PROCEDURE Puta(p1, p2: Polinom; VAR pr: Polinom);
1633 PROCEDURE Kolicnik(p1, p2: Polinom;
1634                    VAR kol, ost: Polinom;
1635                    VAR ok : BOOLEAN);
1636 PROCEDURE PolinomNaN(p: Polinom; n: CARDINAL;
1637                      VAR rez: Polinom);
1638 PROCEDURE DisposePolinom(VAR p: Polinom);
1639
1640 END PolinomL.
1641 \end{lstlisting}
1642
1643 \paragraph{PolinomL.MOD} \
1644
1645 \begin{codeblock}
1646 (* Modul za rad sa polinomima preko listi
1647    verzija 2012, rev 1 *)
1648 IMPLEMENTATION MODULE PolinomL;
1649 FROM InOut IMPORT Write, WriteString, WriteLn,
1650            WriteCard, ReadCard, Done;
1651 FROM RealInOut IMPORT WriteReal, ReadReal;
1652 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1653
1654 PROCEDURE Anuliraj(VAR p: Polinom);
1655 BEGIN
1656   p := NIL;
1657 END Anuliraj;
1658
1659 PROCEDURE Kopiraj(p: Polinom; VAR kopija: Polinom);
1660 VAR
1661   pomocni: Polinom;
1662 BEGIN
1663   IF p = NIL THEN
1664     kopija := NIL
1665   ELSE
1666     NEW(kopija);
1667     kopija^ := p^;
1668     p := p^.veza;
1669     pomocni := kopija;
1670     WHILE p <> NIL DO
1671       NEW(pomocni^.veza);
1672       pomocni := pomocni^.veza;
1673       pomocni^ := p^;
1674       p := p^.veza
1675     END
1676   END
1677 END Kopiraj;
1678
1679 PROCEDURE Stampaj(p: Polinom; d: CARDINAL);
1680
1681   PROCEDURE StampajMonom(m : Polinom);
1682   BEGIN
1683     WITH m^ DO
1684       IF st <> 0 THEN
1685         IF ABS(k) <> 1.0 THEN
1686           WriteReal(ABS(k), d)
1687         END;
1688         Write('x');
1689         IF st <> 1 THEN
1690           Write('^');
1691           WriteCard(st, 1)
1692         END
1693       ELSE
1694         WriteReal(ABS(k), d)
1695       END
1696     END
1697   END StampajMonom;
1698
1699 BEGIN
1700   IF p = NIL THEN
1701     WriteReal(0., d)
1702   ELSE
1703     IF p^.k < 0.0 THEN
1704       WriteString(' - ')
1705     END;
1706     StampajMonom(p);
1707     p := p^.veza;
1708     WHILE p <> NIL DO
1709       IF p^.k > 0.0 THEN
1710         WriteString(' + ')
1711       ELSE
1712         WriteString(' - ')
1713       END;
1714       StampajMonom(p);
1715       p := p^.veza
1716     END
1717   END
1718 END Stampaj;
1719
1720 PROCEDURE UbaciMonom(mon:Polinom; VAR p: Polinom);
1721 VAR
1722   stari, tekuci, kopija: Polinom;
1723 BEGIN
1724   IF mon # NIL THEN
1725     NEW(kopija);
1726     kopija^ := mon^;
1727     tekuci := p;
1728         stari := NIL;
1729     WHILE (tekuci#NIL) AND (tekuci^.st>kopija^.st) DO
1730       stari := tekuci;
1731       tekuci := tekuci^.veza
1732     END;
1733     kopija^.veza := tekuci;
1734     IF tekuci = p THEN
1735       p := kopija
1736     ELSE
1737       stari^.veza := kopija
1738     END;
1739     IF (tekuci#NIL) AND (kopija^.st = tekuci^.st) THEN
1740       kopija^.k := kopija^.k + tekuci^.k;
1741       kopija^.veza := tekuci^.veza;
1742       DISPOSE(tekuci);
1743       IF kopija^.k = 0.0 THEN
1744         IF p = kopija THEN
1745           p := kopija^.veza
1746         ELSE
1747           stari^.veza := kopija^.veza
1748         END;
1749         DISPOSE(kopija)
1750       END
1751     END
1752   END
1753 END UbaciMonom;
1754
1755 PROCEDURE Unos(VAR p : Polinom);
1756 VAR
1757   i, n: CARDINAL;
1758   novi: Polinom;
1759 BEGIN
1760   Anuliraj(p);
1761   REPEAT
1762     WriteLn;
1763     WriteString('Unesite broj monoma n (n>=0) ');
1764     ReadCard(n);
1765   UNTIL Done;
1766   WriteLn;
1767   FOR i := 1 TO n DO
1768     NEW(novi);
1769     WITH novi^ DO
1770       REPEAT
1771         WriteString('Unesite koeficijent monoma br.');
1772         WriteCard(i, 1);
1773         WriteString(' (<> 0) ');
1774         ReadReal(k);
1775         WriteLn
1776       UNTIL k <> 0.0;
1777       REPEAT
1778         WriteLn;
1779         WriteString('Unesite eksponent monoma br.');
1780         WriteCard(i, 1);
1781         WriteString(' (>=0) ');
1782         ReadCard(st);
1783       UNTIL Done;
1784       WriteLn;
1785     END;
1786     UbaciMonom(novi, p);
1787     DISPOSE(novi);
1788   END
1789 END Unos;
1790
1791 PROCEDURE Saberi(p1, p2: Polinom; VAR zbir: Polinom);
1792 BEGIN
1793   Kopiraj(p1, zbir);
1794   WHILE p2 <> NIL DO
1795     UbaciMonom(p2, zbir);
1796     p2 := p2^.veza
1797   END
1798 END Saberi;
1799
1800 PROCEDURE SaberiNa(p: Polinom; VAR rez: Polinom);
1801 BEGIN
1802   WHILE p <> NIL DO
1803     UbaciMonom(p,rez);
1804     p := p^.veza;
1805   END;
1806 END SaberiNa;
1807
1808 PROCEDURE PromeniZnak(VAR p: Polinom);
1809 VAR
1810   t: Polinom;
1811 BEGIN
1812   t := p;
1813   WHILE t <> NIL DO
1814     t^.k := - t^.k;
1815     t := t^.veza
1816   END
1817 END PromeniZnak;
1818
1819 PROCEDURE Oduzmi(p1,p2: Polinom; VAR razlika: Polinom);
1820 BEGIN
1821   Kopiraj(p2, razlika);
1822   PromeniZnak(razlika);
1823   WHILE p1 <> NIL DO
1824     UbaciMonom(p1, razlika);
1825     p1 := p1^.veza
1826   END
1827 END Oduzmi;
1828
1829 PROCEDURE MonomPuta(p, mon: Polinom; VAR mp: Polinom);
1830 VAR
1831   tekuci: Polinom;
1832 BEGIN
1833   Anuliraj(mp);
1834   IF (mon <> NIL) AND (p <> NIL) THEN
1835     NEW(mp);
1836     mp^.k := p^.k * mon^.k;
1837     mp^.st := p^.st + mon^.st;
1838     p := p^.veza;
1839     tekuci := mp;
1840     WHILE p <> NIL DO
1841       NEW(tekuci^.veza);
1842       tekuci := tekuci^.veza;
1843       tekuci^.k := p^.k * mon^.k;
1844       tekuci^.st := p^.st + mon^.st;
1845       p := p^.veza
1846     END;
1847     tekuci^.veza := NIL
1848   END
1849 END MonomPuta;
1850
1851 PROCEDURE Puta(p1, p2: Polinom; VAR pr: Polinom);
1852 VAR
1853   pomocni: Polinom;
1854 BEGIN
1855   Anuliraj(pr);
1856   IF (p1 <> NIL) AND (p2 <> NIL) THEN
1857     MonomPuta(p1, p2, pr);
1858     p2 := p2^.veza;
1859     WHILE p2 <> NIL DO
1860       MonomPuta(p1, p2, pomocni);
1861       REPEAT
1862         UbaciMonom(pomocni, pr);
1863         pomocni := pomocni^.veza
1864       UNTIL pomocni = NIL;
1865       p2 := p2^.veza
1866     END
1867   END
1868 END Puta;
1869
1870 PROCEDURE Kolicnik(p1, p2: Polinom; VAR kol, ost: Polinom; VAR ok: BOOLEAN);
1871
1872   PROCEDURE Deli(VAR kol, ost: Polinom);
1873   VAR
1874     novi, pomocni: Polinom;
1875   BEGIN
1876     IF ost <> NIL THEN
1877       IF ost^.st >= p2^.st THEN
1878         NEW(novi);
1879         novi^.k := - ost^.k / p2^.k;
1880         novi^.st := ost^.st - p2^.st;
1881         MonomPuta(p2, novi, pomocni);
1882         Saberi(ost, pomocni, ost);
1883         novi^.k := - novi^.k;
1884         UbaciMonom(novi, kol);
1885         DISPOSE(novi);
1886         Deli(kol, ost)
1887       END
1888     END
1889   END Deli;
1890
1891 BEGIN (* Kolicnik *)
1892   ok := TRUE;
1893   Anuliraj(kol);
1894   IF p2 = NIL THEN
1895     ok := FALSE
1896   ELSE
1897     Kopiraj(p1, ost);
1898     Deli(kol, ost)
1899   END
1900 END Kolicnik;
1901
1902 PROCEDURE PolinomNaN(p: Polinom; n: CARDINAL;
1903                      VAR rez: Polinom);
1904 VAR
1905   i: CARDINAL;
1906 BEGIN
1907   IF n = 0 THEN
1908     NEW(rez);
1909     rez^.k := 1.0;
1910     rez^.st := 0;
1911     rez^.veza := NIL;
1912   ELSIF n = 1 THEN
1913         Kopiraj( p, rez );
1914   ELSE
1915     rez := p;
1916     FOR i := 2 TO n DO
1917       Puta(rez, p, rez)
1918     END
1919   END;
1920 END PolinomNaN;
1921
1922 PROCEDURE DisposePolinom(VAR p: Polinom);
1923 VAR
1924   pomocni: Polinom;
1925 BEGIN
1926   pomocni := p;
1927   WHILE pomocni # NIL DO
1928     p := p^.veza;
1929     DISPOSE(pomocni);
1930     pomocni := p
1931   END
1932 END DisposePolinom;
1933
1934 END PolinomL.
1935 \end{codeblock}
1936
1937
1938 \subsection{Zadatak: Sabiranje sa unapred određenim polinomom}
1939
1940 Želimo da ispišemo uneti polinom uvećan za\\ $x^5 - 3x^4 + 4x + 7$.
1941
1942 \begin{lstlisting}[style=codeblock]
1943 MODULE polinom;
1944 FROM PolinomL IMPORT Polinom, Stampaj, Anuliraj, DisposePolinom, UbaciMonom, Unos, Saberi;
1945 FROM InOut IMPORT WriteString, WriteLn;
1946 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1947
1948 VAR
1949   p,q,rez,pom : Polinom;
1950
1951 BEGIN
1952   (* korisnik unosi prvi polinom *)
1953   WriteString("Unesite polinom:");
1954   WriteLn;
1955   Unos(p);
1956   (* drugi polinom kreiramo mi,
1957      monom po monom *)
1958   Anuliraj(q); (* isto sto i q:=NIL; *)
1959   (* formiramo monom x^5 *)
1960   NEW(pom);
1961   pom^.st:=5;
1962   pom^.k:=1.0;
1963   (* dodajemo ga u polinom *)
1964   UbaciMonom(pom,q);
1965   DISPOSE(pom);
1966   (* -3 x^4 *)
1967   NEW(pom);
1968   pom^.st := 4;
1969   pom^.k := -3.0;
1970   UbaciMonom(pom,q);
1971   DISPOSE(pom);
1972   (* 4 x *)
1973   NEW(pom);
1974   pom^.st := 1;
1975   pom^.k := 4.0;
1976   UbaciMonom(pom,q);
1977   DISPOSE(pom);
1978   (* 7 (x^0) *)
1979   NEW(pom);
1980   pom^.st := 0;
1981   pom^.k := 7.0;
1982   UbaciMonom(pom,q);
1983   DISPOSE(pom);
1984   (* saberemo polinome *)
1985   Saberi(p, q, rez);
1986   (* odstampamo rezultat *)
1987   Stampaj(rez,0);
1988   WriteLn;
1989   (* oslobadjanje zauzete memorije *)
1990   DisposePolinom(p);
1991   DisposePolinom(q);
1992   DisposePolinom(rez);
1993 END polinom.
1994 \end{lstlisting}
1995
1996 \subsection{Zadatak: Suma k polinoma}
1997
1998 Napisati program koji ucitava broj k (1<=k<=50) i k polinoma, a nakon
1999 toga izracunava njihovu sumu
2000
2001 \begin{lstlisting}[style=codeblock]
2002 MODULE PolSuma;
2003
2004 FROM PolinomL IMPORT Polinom, Anuliraj, DisposePolinom, Unos, Stampaj, SaberiNa;
2005 FROM InOut IMPORT WriteLn, WriteString, ReadCard, WriteCard;
2006 CONST
2007   maxk = 50;
2008 TYPE
2009   nizPol = ARRAY [1..maxk] OF Polinom;
2010 VAR
2011   i, k: CARDINAL;
2012   suma : Polinom;
2013   p : nizPol;
2014 BEGIN
2015   REPEAT
2016     WriteString('Unesite broj k (1 <= k <= ');
2017     WriteCard(maxk, 1);
2018     WriteString(') ');
2019     ReadCard(k);
2020     WriteLn;
2021   UNTIL (1 <= k) AND (k <= maxk);
2022   FOR i := 1 TO k DO
2023     WriteLn;
2024     WriteString('Unos ');
2025     WriteCard(i, 1);
2026     WriteString('. polinoma.');
2027     WriteLn;
2028     Unos(p[i])
2029   END;
2030   Anuliraj(suma);
2031   FOR i := 1 TO k DO
2032     SaberiNa(suma, p[i])
2033   END;
2034   WriteLn;
2035   WriteString('Njihova suma je:');
2036   WriteLn;
2037   Stampaj(suma, 4);
2038   DisposePolinom(suma);
2039   FOR i := 1 TO k DO
2040     DisposePolinom(p[i]);
2041   END;
2042 END PolSuma.
2043 \end{lstlisting}
2044
2045 \section{Stek i red opsluživanja}
2046
2047 \subsection{Zadatak: Ilustracija pisanja u fajl uz pomoć bafera}
2048
2049 \begin{lstlisting}[style=codeblock]
2050 DEFINITION MODULE QueueInfo;
2051 CONST
2052   Maxqueue = 100;
2053 TYPE
2054   InfoTip = CHAR;
2055
2056 END QueueInfo.
2057
2058 IMPLEMENTATION MODULE QueueInfo;
2059 END QueueInfo.
2060
2061 DEFINITION MODULE RedOpsl1;
2062 FROM QueueInfo IMPORT InfoTip,Maxqueue;
2063 TYPE
2064   Niz = ARRAY[1..Maxqueue] OF InfoTip;
2065   RedOpslTip = RECORD
2066         Prvi, Zadnji : CARDINAL;
2067         Element : Niz
2068   END;
2069
2070 PROCEDURE MakeNull(VAR q : RedOpslTip);
2071 PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
2072 PROCEDURE First(VAR q : RedOpslTip;
2073                 VAR x : InfoTip;
2074                 VAR ok : BOOLEAN);
2075 PROCEDURE PopFirst(VAR q : RedOpslTip;
2076                    VAR ok : BOOLEAN);
2077 PROCEDURE AddRear(VAR q : RedOpslTip;
2078                   x : InfoTip;
2079                   VAR ok : BOOLEAN);
2080
2081 END RedOpsl1.
2082
2083 IMPLEMENTATION MODULE RedOpsl1;
2084 FROM QueueInfo IMPORT Maxqueue,InfoTip;
2085
2086 PROCEDURE MakeNull(VAR q : RedOpslTip);
2087 BEGIN
2088   WITH q DO
2089     Prvi := 0;
2090     Zadnji := 0
2091   END
2092 END MakeNull;
2093
2094 PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
2095 BEGIN
2096   RETURN q.Zadnji = 0
2097 END Empty;
2098
2099
2100 PROCEDURE First(VAR q : RedOpslTip;
2101                 VAR x : InfoTip;
2102                 VAR ok : BOOLEAN);
2103 BEGIN
2104   IF Empty(q) THEN
2105     ok := FALSE
2106   ELSE
2107     ok := TRUE;
2108     WITH q DO
2109       x := Element[Prvi]
2110     END
2111   END
2112 END First;
2113
2114 PROCEDURE AddOne(i : CARDINAL) : CARDINAL;
2115 BEGIN
2116   IF i = Maxqueue THEN
2117     RETURN 1
2118   ELSE
2119     RETURN i+1
2120   END
2121 END AddOne;
2122
2123 PROCEDURE PopFirst(VAR q : RedOpslTip;
2124                    VAR ok : BOOLEAN);
2125 BEGIN
2126   IF Empty(q) THEN
2127     ok := FALSE
2128   ELSE
2129     ok := TRUE;
2130     WITH q DO
2131       IF Prvi = Zadnji THEN
2132         MakeNull(q)
2133       ELSE
2134         Prvi := AddOne(Prvi)
2135       END
2136     END
2137   END
2138 END PopFirst;
2139
2140 PROCEDURE AddRear(VAR q : RedOpslTip;
2141                   x : InfoTip;
2142                   VAR ok : BOOLEAN);
2143 BEGIN
2144   WITH q DO
2145     IF AddOne(Zadnji) = Prvi THEN
2146       ok := FALSE
2147     ELSE
2148       ok := TRUE;
2149       IF Empty(q) THEN
2150         Prvi := 1;
2151         Zadnji := 1
2152       ELSE
2153         Zadnji := AddOne(Zadnji)
2154       END;
2155       Element[Zadnji] := x
2156     END
2157   END
2158 END AddRear;
2159
2160 END RedOpsl1.
2161
2162 MODULE Bafer;
2163 FROM RedOpsl1 IMPORT RedOpslTip, MakeNull, Empty, First, PopFirst, AddRear;
2164 FROM FIO IMPORT File,WrChar, Create, Close;
2165 IMPORT IO;
2166
2167 CONST
2168   ImeIzlaza = 'izlaz.txt';
2169
2170 VAR
2171   izlaz : File;
2172   znak : CHAR;
2173   buffer : RedOpslTip;
2174
2175 PROCEDURE IsprazniBafer(VAR dat : File;
2176                         VAR buf : RedOpslTip);
2177 VAR
2178   znak : CHAR;
2179   ok : BOOLEAN;
2180 BEGIN
2181   WHILE NOT Empty(buf) DO
2182     First(buf, znak, ok);
2183     PopFirst(buf, ok);
2184     WrChar(dat, znak)
2185   END
2186 END IsprazniBafer;
2187
2188 PROCEDURE BaferWrite(VAR dat : File;
2189                      VAR buf : RedOpslTip;
2190                      znak : CHAR);
2191 VAR
2192   ok : BOOLEAN;
2193 BEGIN
2194   AddRear(buf, znak, ok);
2195   IF NOT ok THEN
2196     IsprazniBafer(dat, buf);
2197     AddRear(buf, znak, ok)
2198   END
2199 END BaferWrite;
2200
2201 BEGIN
2202   izlaz := Create(ImeIzlaza);
2203   MakeNull(buffer);
2204   IO.WrStr('Unesite tekst, koji treba da se unese u datoteku ');
2205   IO.WrStr(ImeIzlaza);
2206   IO.WrChar('.');
2207   IO.WrLn;
2208   IO.WrStr('Unos zavrsite tackom.');
2209   IO.WrLn;
2210   znak := IO.RdChar();
2211   WHILE znak # '.' DO
2212     BaferWrite(izlaz, buffer, znak);
2213     znak := IO.RdChar();
2214   END;
2215   IsprazniBafer(izlaz, buffer);
2216   Close(izlaz)
2217 END Bafer.
2218 \end{lstlisting}
2219
2220 \subsection%
2221 {Zadatak: Ispitivanje da li reč pripada gramatici wcw$^+$}
2222
2223 Reč pripada ovoj gramatici ako joj se prvi deo (w) sastoji samo od
2224 slova 'a' i 'b', sledi slovo 'c' a nakon njega obrnuta reč reči w.
2225
2226 \begin{lstlisting}[style=codeblock]
2227 DEFINITION MODULE Stek;
2228 CONST
2229   Maxstack = 100;
2230 TYPE
2231   Niz = ARRAY [1..Maxstack] OF CHAR;
2232   StekTip = RECORD
2233             Top : CARDINAL;
2234             Element : Niz
2235           END;
2236 PROCEDURE MakeNull(VAR s : StekTip);
2237 PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
2238
2239 PROCEDURE Top(VAR s : StekTip;
2240               VAR x : CHAR;
2241               VAR ok : BOOLEAN);
2242 PROCEDURE Pop(VAR s : StekTip;
2243               VAR ok : BOOLEAN);
2244 PROCEDURE Push(VAR s : StekTip;
2245                x : CHAR;
2246                VAR ok : BOOLEAN);
2247 END Stek.
2248
2249
2250 IMPLEMENTATION MODULE Stek;
2251
2252 PROCEDURE MakeNull(VAR s : StekTip);
2253 BEGIN
2254   s.Top := 0
2255 END MakeNull;
2256
2257 PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
2258 BEGIN
2259   RETURN s.Top = 0
2260 END Empty;
2261
2262 PROCEDURE Top(VAR s : StekTip;
2263               VAR x : CHAR;
2264               VAR ok : BOOLEAN);
2265 BEGIN
2266   IF Empty(s) THEN
2267     ok := FALSE
2268   ELSE
2269     ok := TRUE;
2270     WITH s DO
2271       x := Element[Top]
2272     END
2273   END
2274 END Top;
2275
2276 PROCEDURE Pop(VAR s : StekTip;
2277               VAR ok : BOOLEAN);
2278 BEGIN
2279   IF Empty(s) THEN
2280     ok := FALSE
2281   ELSE
2282     ok := TRUE;
2283     DEC(s.Top)
2284   END
2285 END Pop;
2286
2287 PROCEDURE Push(VAR s : StekTip;
2288                x : CHAR;
2289                VAR ok : BOOLEAN);
2290 BEGIN
2291   WITH s DO
2292     IF Top = Maxstack THEN
2293       ok := FALSE
2294     ELSE
2295       ok := TRUE;
2296       INC(Top);
2297       Element[Top] := x
2298     END
2299   END
2300 END Push;
2301 END Stek.
2302
2303 MODULE wcw;
2304 (* Da li rec pripada gramatici wcw+. *)
2305 FROM Stek IMPORT StekTip, MakeNull, Empty,
2306                  Top, Pop, Push;
2307 FROM InOut IMPORT Read, Write, WriteString, EOL;
2308 TYPE
2309   slova = SET OF CHAR;
2310 VAR
2311   S : StekTip;
2312   Ch, C : CHAR;
2313   ok : BOOLEAN;
2314 BEGIN
2315   MakeNull(S);
2316   Read(Ch);
2317   ok := TRUE;
2318   WHILE ok AND (Ch IN slova{'a', 'b'}) DO
2319     Push(S, Ch, ok);
2320     Read(Ch);
2321   END;
2322   IF NOT ok THEN
2323     WriteString('Greska - mali stek')
2324   ELSIF Ch # 'c' THEN
2325     WriteString('Pogresan string')
2326   ELSE
2327     Read(Ch);
2328     WHILE ok AND (Ch # EOL) DO
2329       Top(S, C, ok);
2330       ok := ok AND (C = Ch);
2331       IF ok THEN
2332         Pop(S, ok);
2333         Read(Ch);
2334       END
2335     END;
2336     IF NOT (ok AND Empty(S)) THEN
2337       WriteString('Pogresan string')
2338     ELSE
2339       WriteString('String pripada jeziku L')
2340     END
2341   END
2342 END wcw.
2343 \end{lstlisting}
2344
2345 \subsection{Zadatak: Kalkulator za izračunavanje postfiksnih izraza}
2346
2347
2348 Napraviti kalkulator za izračunavanje postfiksnih izraza. Svi brojevi
2349 koji figurišu u izrazu su jednocifreni.
2350
2351 \begin{lstlisting}[style=codeblock]
2352 MODULE PostFix;
2353
2354 FROM StekI IMPORT StekTip, MakeNull, Empty, Top, Pop, Push;
2355 FROM InOut IMPORT Read, Write, WriteInt, EOL;
2356 TYPE
2357   slova = SET OF CHAR;
2358 VAR
2359   S : StekTip;
2360   Ch : CHAR;
2361   Op1, Op2 : INTEGER;
2362   ok : BOOLEAN;
2363 PROCEDURE Conv(Ch : CHAR) : INTEGER;
2364 BEGIN
2365   RETURN  ORD(Ch) - ORD('0')
2366 END Conv;
2367
2368 BEGIN
2369   MakeNull(S);
2370   Read(Ch);
2371   WHILE Ch # EOL DO
2372     IF Ch IN slova{'+', '-', '/', '*', '%'} THEN
2373       Top(S, Op2, ok);
2374       Pop(S, ok);
2375       Top(S, Op1, ok);
2376       Pop(S, ok);
2377       CASE Ch OF
2378         '+' : Op1 := Op1 + Op2 |
2379         '-' : Op1 := Op1 - Op2 |
2380         '*' : Op1 := Op1 * Op2 |
2381         '/' : Op1 := Op1 DIV Op2 |
2382         '%' : Op1 := Op1 MOD Op2
2383       END;
2384       Push(S, Op1, ok)
2385     ELSE
2386       Push(S, Conv(Ch), ok)
2387     END;
2388     Read(Ch);
2389   END;
2390   Top(S, Op1, ok);
2391   Write('=');
2392   WriteInt(Op1,5)
2393 END PostFix.
2394 \end{lstlisting}
2395
2396
2397 \section{Simulacija rekurzije}
2398
2399
2400 Na početku označiti sve rekurzivne pozive u originalnoj proceduri
2401 adresama (npr. 1,2,3... ili konstante nabrojivog tipa podataka).
2402
2403 Na steku se čuvaju lokalne promenljive, parametri procedure i adresa
2404 mesta poziva, a u skladu sa tim se kreira InfoTip.
2405
2406 Trivijalnim pozivom se smatra onaj koji se izračunava bez dodatnih
2407 rekurzivnih poziva.
2408
2409 U kodu ispod, \kod{treba\_rekurzija} znači da je poziv netrivijalan,
2410 odnosno treba naći uslove pod kojima se sigurno dešavaju rekurzivni
2411 pozivi.
2412
2413 \begin{lstlisting}
2414 MakeNull(S);
2415 REPEAT
2416   WHILE treba_rekurzija DO
2417     -prepisati sve od pocetka originalne
2418      procedure do prvog rekurzivnog poziva
2419     -staviti na stek potrebne
2420      lokalne promenljive, parametre procedure i
2421      adresu mesta poziva
2422     -podesiti vrednosti parametara da budu
2423      kao u rekurzivnom pozivu procedure
2424   END;
2425   trivijalan poziv
2426   umesto RETURN x pisati rez := x
2427   jos := TRUE;
2428   WHILE jos AND NOT Empty(S) DO
2429     Top(S, el, ok);
2430     Pop(S, ok);
2431     -restauriramo vrednosti sa steka
2432     -u zavisnosti od adrese poziva nastavimo
2433      prepisivanje originalne procedure sa
2434      tog mesta
2435     -ako se dodje do novog rek. poziva tada:
2436        -sacuvati na steku vrednosti
2437        -podesiti vrednosti parametara da budu
2438         kao u rekurzivnom pozivu procedure
2439        -ici na pocetak koda
2440         (ovo se postize sa jos := FALSE)
2441     -inace
2442        ako se naidje na RETURN x pisati rez := x
2443   END
2444 UNTIL Empty(S);
2445 \end{lstlisting}
2446
2447 Ako je procedura funkcijska tada se na kraj dodaje \kod{RETURN rez}.
2448
2449 \subsection*{ZADACI}
2450
2451 Simulirati ponašanje sledećih rekurzivnih procedura (funkcija) upotrebom steka:
2452
2453 \subsection{Primer 1 -- faktorijel}
2454
2455
2456 \begin{lstlisting}[style=codeblock]
2457 MODULE Fakto;
2458 (* InfoTip = CARDINAL; *)
2459
2460 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2461 FROM StekC IMPORT StekTip, MakeNull, Empty,
2462                   Top, Pop, Push;
2463 VAR
2464   n : CARDINAL;
2465 PROCEDURE RFakto(n : CARDINAL) : CARDINAL;
2466 BEGIN
2467   IF n <= 1 THEN
2468     RETURN 1
2469   ELSE
2470     RETURN n * RFakto(n-1)
2471   END
2472 END RFakto;
2473
2474
2475 PROCEDURE SFakto(n : CARDINAL) : CARDINAL;
2476 VAR
2477   s : StekTip;
2478   rez : CARDINAL;
2479   OK : BOOLEAN;
2480 BEGIN
2481   MakeNull(s);
2482   WHILE n > 1 DO
2483     Push(s,n,OK);
2484     DEC(n)
2485   END;
2486   rez := 1;
2487   WHILE NOT Empty(s) DO
2488     Top(s, n, OK);
2489     Pop(s, OK);
2490     rez := n * rez
2491   END;
2492   RETURN rez
2493 END SFakto;
2494
2495 BEGIN
2496   WrStr('n = ');
2497   n := RdCard();
2498   WrLn
2499   WrStr('n! = ');
2500   WrCard(RFakto(n), 1);
2501   WrStr(' = ');
2502   WrCard(SFakto(n), 1)
2503 END Fakto.
2504 \end{lstlisting}
2505
2506 \manbreakJK
2507
2508 \subsection{Primer 2 -- stepenovanje}
2509
2510 \begin{lstlisting}[style=codeblock]
2511 MODULE Step;
2512 (* InfoTip = RECORD
2513                 x : REAL;
2514                 n : CARDINAL;
2515                 adr : (par, nepar)
2516              END;
2517 *)
2518 FROM IO IMPORT WrStr, WrLn, WrReal,
2519         RdReal, RdCard;
2520 FROM StekStep IMPORT StekTip, MakeNull, Empty,
2521              Top, Pop, Push, InfoTip, AdrTip;
2522 VAR
2523   n : CARDINAL;
2524   x : REAL;
2525
2526 PROCEDURE Sqr(y : REAL) : REAL;
2527 BEGIN
2528   RETURN y * y
2529 END Sqr;
2530
2531 PROCEDURE RStep(x : REAL;
2532                 n : CARDINAL) : REAL;
2533 BEGIN
2534   IF n = 0 THEN
2535     RETURN 1.
2536   ELSIF ODD(n) THEN
2537     RETURN x * Sqr( RStep(x, n DIV 2) )
2538   ELSE
2539     RETURN Sqr( RStep(x, n DIV 2) )
2540   END
2541 END RStep;
2542
2543 PROCEDURE SStep(x : REAL;
2544                 n : CARDINAL ) : REAL;
2545 VAR
2546   s : StekTip;
2547   OK : BOOLEAN;
2548   rez : REAL;
2549   el : InfoTip;
2550 BEGIN
2551   MakeNull(s);
2552   WHILE n > 0 DO
2553     el.x := x;
2554     el.n := n;
2555     IF ODD(n) THEN
2556       el.adr := nepar;
2557     ELSE
2558       el.adr := par
2559     END;
2560     Push(s,el,OK);
2561     n := n DIV 2
2562   END;
2563   rez := 1.;
2564   WHILE NOT Empty(s) DO
2565     Top(s, el, OK);
2566     Pop(s, OK);
2567     x := el.x;
2568     n := el.n;
2569     IF el.adr = nepar THEN
2570       rez := x * Sqr(rez)
2571     ELSE
2572       rez := Sqr(rez)
2573     END
2574   END;
2575   RETURN rez
2576 END SStep;
2577
2578 BEGIN
2579   WrStr('x =? ');
2580   x := RdReal();
2581   WrLn;
2582   WrStr('n =? ');
2583   n := RdCard();
2584   WrStr('x^n = ');
2585   WrReal(RStep(x, n), 10, 1);
2586   WrStr(' = ');
2587   WrReal(SStep(x, n), 10, 1)
2588 END Step.
2589 \end{lstlisting}
2590
2591 \subsection{Primer 3 -- Fibonači}
2592
2593 \begin{lstlisting}[style=codeblock]
2594 MODULE Fib;
2595 (* InfoTip = RECORD
2596                 n : CARDINAL;
2597                 PrviSab : CARDINAL;
2598                 adr : (prvi, drugi)
2599              END;
2600 *)
2601
2602 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2603 FROM StekFib IMPORT StekTip, MakeNull, Empty,
2604        Top, Pop, Push, InfoTip, AdrTip;
2605 VAR
2606   n : CARDINAL;
2607
2608 PROCEDURE RFib(n : CARDINAL) : CARDINAL;
2609 BEGIN
2610   IF n <= 1 THEN
2611     RETURN n
2612   ELSE
2613     RETURN RFib(n-1) + RFib(n-2)
2614   END
2615 END RFib;
2616
2617 PROCEDURE SFib(n : CARDINAL ) : CARDINAL;
2618 VAR
2619   s : StekTip;
2620   OK, jos : BOOLEAN;
2621   rez, PrviSab : CARDINAL;
2622   el : InfoTip;
2623 BEGIN
2624   MakeNull(s);
2625   REPEAT
2626     WHILE n > 1 DO
2627       el.n := n;
2628       el.adr := prvi;
2629       Push(s,el,OK);
2630       DEC(n)
2631     END;
2632     rez := (n);
2633     jos := TRUE;
2634     WHILE (NOT Empty(s)) AND jos DO
2635       Top(s, el, OK);
2636       Pop(s, OK);
2637       n := el.n;
2638       IF el.adr = prvi THEN
2639         PrviSab := rez;
2640         el.n := n;
2641         el.adr := drugi;
2642         el.PrviSab := PrviSab;
2643         Push(s, el, OK);
2644         DEC(n, 2);
2645         jos := FALSE
2646       ELSE
2647         PrviSab := el.PrviSab;
2648         rez := PrviSab + rez
2649       END
2650     END
2651   UNTIL Empty(s);
2652   RETURN rez
2653 END SFib;
2654
2655 BEGIN
2656   WrStr('n =? ');
2657   n := RdCard();
2658   WrStr('F(n) = ');
2659   WrCard(RFib(n), 1);
2660   WrStr(' = ');
2661   WrCard(SFib(n), 1)
2662 END Fib.
2663 \end{lstlisting}
2664
2665 \subsection{Primer 4 -- faktorijel 2}
2666
2667
2668 \begin{lstlisting}[style=codeblock]
2669 MODULE Faktor;
2670 (* InfoTip = CARDINAL; *)
2671 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2672 FROM StekC IMPORT StekTip, MakeNull, Empty,
2673                   Top, Pop, Push;
2674 VAR
2675   n,rez : CARDINAL;
2676
2677 PROCEDURE RFakto(n : CARDINAL;
2678                  VAR rez : CARDINAL);
2679 BEGIN
2680   IF n = 0 THEN
2681     rez := 1
2682   ELSE
2683     RFakto(n-1, rez);
2684     rez := n * rez
2685   END
2686 END RFakto;
2687
2688 PROCEDURE SFakto(n : CARDINAL;
2689                  VAR rez : CARDINAL);
2690 VAR
2691   s : StekTip;
2692   OK : BOOLEAN;
2693 BEGIN
2694   MakeNull(s);
2695   WHILE n > 0 DO
2696     Push(s,n,OK);
2697     DEC(n)
2698   END;
2699   rez := 1;
2700   WHILE NOT Empty(s) DO
2701     Top(s, n, OK);
2702     Pop(s, OK);
2703     rez := n * rez
2704   END
2705 END SFakto;
2706
2707 BEGIN
2708   WrStr('n =? ');
2709   n := RdCard();
2710   WrLn;
2711   WrStr('n! = ');
2712   RFakto(n, rez);
2713   WrCard(rez, 1);
2714   WrStr(' = ');
2715   SFakto(n, rez);
2716   WrCard(rez, 1)
2717 END Faktor.
2718 \end{lstlisting}
2719
2720 \subsection{Primer 5 (ispitni)}
2721
2722
2723 \begin{lstlisting}[style=codeblock]
2724 MODULE Rek1;
2725 (* InfoTip = RECORD
2726                 d, g, m1, m2 : INTEGER;
2727                 adr : (prvi, drugi)
2728              END;
2729 *)
2730 FROM Stek1 IMPORT StekTip, adresa, InfoTip,
2731          MakeNull, Empty, Top, Pop, Push;
2732 IMPORT IO;
2733 VAR
2734   X : ARRAY [1..20] OF INTEGER;
2735
2736 PROCEDURE Max(d, g: INTEGER) : INTEGER;
2737 VAR
2738   m1, m2 : INTEGER;
2739 BEGIN
2740   IF d>g THEN
2741     RETURN MIN(INTEGER)
2742   ELSIF d=g THEN
2743     RETURN X[d]
2744   ELSE
2745     m1 := Max(d, (d+g) DIV 2);
2746     m2 := Max((d+g) DIV 2 +1, g);
2747     IF m1 > m2 THEN
2748       RETURN m1
2749     ELSE
2750       RETURN m2
2751     END
2752   END
2753 END Max;
2754
2755 PROCEDURE SMax(d, g: INTEGER) : INTEGER;
2756 VAR
2757   S : StekTip;
2758   el : InfoTip;
2759   ok, jos : BOOLEAN;
2760   m1, m2, rez : INTEGER;
2761 BEGIN
2762   MakeNull(S);
2763   REPEAT
2764     WHILE d<g DO
2765       el.d := d;
2766       el.g := g;
2767       el.adr := prvi;
2768       Push(S, el, ok);
2769       g := (d+g) DIV 2
2770     END;
2771     IF d>g THEN
2772       rez := MIN(INTEGER)
2773     ELSE (* d=g *)
2774       rez := X[d]
2775     END;
2776     jos := TRUE;
2777     WHILE jos AND NOT Empty(S) DO
2778       Top(S, el, ok);
2779       Pop(S, ok);
2780       d := el.d;
2781       g := el.g;
2782       m1 := el.m1;
2783       IF el.adr = prvi THEN
2784         m1 := rez;
2785         el.m1 := m1;
2786         el.adr := drugi;
2787         Push(S, el, ok);
2788         d := (d+g) DIV 2 + 1;
2789         jos := FALSE
2790       ELSE (*el.adr = drugi*)
2791         m2 := rez;
2792         IF m1 > m2 THEN
2793           rez := m1
2794         ELSE
2795           rez := m2
2796         END
2797       END
2798     END
2799   UNTIL Empty(S);
2800   RETURN rez
2801 END SMax;
2802
2803 BEGIN (* glavni program *)
2804   X[1] := 3;
2805   X[2] := 2;
2806   X[3] := 5;
2807   X[4] := -7;
2808   X[5] := 0;
2809   IO.WrCard(Max(1, 5), 3);
2810   IO.WrLn;
2811   IO.WrCard(SMax(1, 5), 3);
2812   IO.WrLn
2813 END Rek1.
2814 \end{lstlisting}
2815
2816 \subsection{Primer 6 (ispitni)}
2817
2818
2819 \begin{lstlisting}[style=codeblock]
2820 MODULE Rek2;
2821 (* InfoTip = RECORD
2822                 x, y, n : CARDINAL;
2823                 adr : (prvi, drugi, treci, cetvrti)
2824              END;
2825 *)
2826 FROM Stek2 IMPORT StekTip, adresa, InfoTip,
2827            MakeNull, Empty, Top, Pop, Push;
2828 IMPORT IO;
2829
2830 PROCEDURE g(x : CARDINAL; y : CARDINAL;
2831             n : CARDINAL) : CARDINAL;
2832 BEGIN
2833   IF n < 3 THEN
2834     RETURN x + y
2835   ELSIF ODD(n) THEN
2836     RETURN g(g(x+1, y, n-2), y, n-3)
2837   ELSE
2838     RETURN g(x, g(x, y+1, n-2), n-3)
2839   END
2840 END g;
2841
2842 PROCEDURE Sg(x : CARDINAL; y : CARDINAL;
2843              n : CARDINAL) : CARDINAL;
2844 VAR
2845   S : StekTip;
2846   el : InfoTip;
2847   ok, jos : BOOLEAN;
2848   rez : CARDINAL;
2849 BEGIN
2850   MakeNull(S);
2851   REPEAT
2852     WHILE n >= 3 DO
2853       IF ODD(n) THEN
2854         el.x := x;
2855         el.y := y;
2856         el.n := n;
2857         el.adr := prvi;
2858         Push(S, el, ok);
2859         INC(x);
2860         DEC(n, 2)
2861       ELSE
2862         el.x := x;
2863         el.y := y;
2864         el.n := n;
2865         el.adr := treci;
2866         Push(S, el, ok);
2867         INC(y);
2868         DEC(n, 2)
2869       END
2870     END;
2871     rez := x+y;
2872     jos := TRUE;
2873     WHILE jos AND NOT Empty(S) DO
2874       Top(S, el, ok);
2875       Pop(S, ok);
2876       x := el.x;
2877       y := el.y;
2878       n := el.n;
2879       IF el.adr = prvi THEN
2880         el.adr := drugi;
2881         Push(S, el, ok);
2882         x := rez;
2883         DEC(n, 3);
2884         jos := FALSE
2885       ELSIF el.adr = treci THEN
2886         el.adr := cetvrti;
2887         Push(S, el, ok);
2888         y := rez;
2889         DEC(n, 3);
2890         jos := FALSE
2891       END
2892     END
2893   UNTIL Empty(S);
2894   RETURN rez
2895 END Sg;
2896
2897 BEGIN (* glavni program *)
2898   IO.WrCard(g(2, 3, 10), 3);
2899   IO.WrCard(Sg(2, 3, 10), 3);
2900 END Rek2.
2901 \end{lstlisting}
2902
2903 %\columnbreak
2904
2905 \appendix
2906
2907 \section{Native XDS Modula 2 -- kratko uputstvo}
2908
2909
2910 Ovo uputstvo ukratko pokriva kako se može nabaviti XDS Modula 2 za Windows
2911 sistem, njenu instalaciju, te kako napraviti i pokretnuti jednostavan program.
2912
2913 \subsection*{Dobavljanje instalacije}
2914
2915
2916 Native XDS Modula 2 se može besplatno skinuti sa sajta proizvođača,
2917 \url{http://www.excelsior-usa.com/}, tačnije na adresi:
2918
2919 \url{http://www.excelsior-usa.com/xdsdl.html}
2920
2921 Prvo se prikazuje ugovor o korišćenju koji na dnu treba potvrditi da ste
2922 razumeli i da ćete ga se pridržavati.
2923
2924 Na stranici koja se potom otvara je potrebno odabrati ``XDS 2.6 beta 2
2925 for Windows'' i snimiti je na računar.
2926
2927 \subsection*{Instalacija okruženja}
2928
2929 Osnovno okruženje (xds-x86...) se instalira pokretanjem prethodno pomenute
2930  instalacione arhive.
2931
2932 \emph{Korisnicima Windows-a 7 preporučujemo da pokrenu instalacione
2933   pakete pomoću opcije ``Run as administrator'' do koje se stiže desnim
2934   klikom miša.}
2935
2936 Pretpostavićemo u daljem tekstu da je program instaliran u
2937 \kod{C:/XDS/}
2938
2939 \subsection*{Pokretanje okruženja}
2940
2941 Po uspešnoj instalaciji bi trebalo da postoji ikonica na desktopu, kao
2942 i grupa sa programom u start meniju.
2943
2944 Ukoliko iz bilo kakvog razloga ne postoje odgovarajuće prečice,
2945 okruženje se može pokrenuti uz pomoć izvršnog fajla
2946 \kod{C:/XDS/BIN/xds.exe} (ako je instalirano na podrazumevanoj
2947 lokaciji).
2948
2949 \subsection*{Prvi projekat}
2950
2951 Da bismo mogli da pišemo i pokrećemo svoj program, potrebno je prvo
2952 napraviti projekat za njega, što se radi na sledeći način:
2953
2954 \begin{itemize}
2955
2956 \item
2957  Iz menija se odabere Project->New.
2958 \item U dijalogu se klikne na gornje dugme ``Browse'', odabere se putanja gde
2959   će se kreirati projekat i ukuca se ime novog projekta.
2960
2961 \item U drugom polju ``Template'' ne treba da piše ništa. Ukoliko
2962   postoji neki tekst, obrisati ga.
2963
2964 \item Kliknuti na ``OK''
2965
2966 \item Iskočiće dijalog na kome piše da ne postoji fajl za editovanje,
2967   kliknuti na ``OK'' da se on napravi.
2968
2969 \item Pojavljuje se forma za kucanje programa, ukucati (na primer):
2970
2971 \begin{minipage}{\columnwidth}
2972 \begin{lstlisting}[style=codeblock]
2973   MODULE Hello;
2974   FROM InOut IMPORT WriteString,WriteLn;
2975   BEGIN
2976     WriteString("Hello World");
2977     WriteLn;
2978   END Hello.
2979 \end{lstlisting}
2980 \end{minipage}
2981
2982 \item Program se može pokrenuti na različite načine, pri čemu se
2983   automatski prevodi:
2984
2985   \begin{itemize}
2986
2987   \item Klik na ``Run'' ikonicu u toolbaru (plavi čovečuljak koji trči)
2988
2989   \item Meni Debug->Run
2990
2991   \item Prečica Ctrl+F9 na tastaturi
2992
2993   \end{itemize}
2994
2995 \item Ako je sve u redu sa programom, treba da se pojavi novi terminal
2996   u kome se ispisuje rezultat izvršavanja programa, u našem slučaju
2997   jednostavna pozdravna poruka.
2998 \end{itemize}
2999
3000 Naravno moguće je i samo prevesti (kompajlirati) program, tako da se
3001 samo prikažu greške (ako ih ima) i bez pokretanja programa:
3002 \begin{itemize}
3003 \item Klik na ``Compile'' ikonicu u toolbaru
3004 \item Meni Tools->Compile
3005 \item Prečica F9 na tastaturi
3006 \end{itemize}
3007
3008 Ukoliko u programu postoje greške, on neće biti pokrenut, već će se
3009 dobiti lista grešaka u donjem delu prozora. Na primer ako obrišemo ``S''
3010 u četvrtom redu i probamo da pokrenemo program, taj red će biti
3011 označen svetlo plavom bojom i dobićemo poruku:
3012
3013 \kod{- Error in pro1.mod [4:5]: Undeclared identifier "Writeting"}
3014
3015 Što znači da u četvrtom redu, kod petog karatkera postoji problem, da
3016 identifikator nije deklarisan, što najčešće znači da ga nismo uvezli,
3017 ili, kao u našem slučaju, da smo napravili grešku u kucanju.
3018
3019 Stvar na koju isto treba obratiti pažnju je da se nekad greška
3020 prijavljue nešto kasnije u tekstu nego što je napravljena. Na primer,
3021 ako obrišemo ``;'' na kraju četvrtog reda i probamo da pokrenemo
3022 program, peti red će biti označen svetlo plavom bojom i dobićemo
3023 poruku:
3024
3025 \kod{- Error in pro1.mod [5:5]: Expected symbol ";" }
3026
3027 Ovo se desilo jer nedostaje tačka zarez na kraju četvrtog reda, ali će
3028 kompajler probati da je traži i dalje, pa će tek na početku petog reda
3029 prijaviti grešku.
3030
3031 U spisku se takođe pojavljuje i upozorenje (Warning) o tome da se
3032 uvezena komanda WriteString ne koristi nigde u programu. Često se
3033 upozorenja mogu ignorisati, a pažnju uglavnom treba obraćati na
3034 greške, odnosno poruke koje počinju sa ``Error''.
3035
3036 Takođe se često dešava da su druge prijavljene greške posledica prve,
3037 te je poželjno ponovo kompajlirati (ili pokretati) program posle svake
3038 ispravljene greške.
3039
3040 \paragraph{Napomena o template-ovima pri kreiranju projekta:}
3041 Moguće je namestiti da u dijalogu za novi projekat drugo polje ``Template''
3042  uvek bude prazno. Potrebno je u tom istom dijalogu kliknuti na
3043  ``Configure'', a potom isprazniti polje ``default template''.
3044
3045 \subsection{Mogući problemi}
3046
3047 \subsubsection*{Nedostajući sistemski moduli}
3048
3049 Verzije pre 2.6 nisu imale uključene u glavni paket sve module koji se
3050 koriste u okviru kursa, i bilo je neophodno da se dodatno instalira i
3051 ``Top Speed Compatibility Pack'' (tscp-x86...). Bez njega je kompajler
3052 prijavljivao da ne postoje neki moduli - najčešće je problem bio da
3053 nedostaje \kod{FIO} modul.
3054
3055 \subsubsection*{Problemi u pokretanju - nemoguće naći exe}
3056
3057 Ako pri pokušaju kompajliranja/pokretanja programa kompajler prijavi
3058 da ne može da nađe exe i pri tome prijavljuje kraću putanju od one
3059 koja je stvarno u pitanju, obično se radi o tome da je postojao razmak
3060 u okviru putanje do modula. Npr ``C:\textbackslash Moj prvi program''
3061 će prouzrokovati probleme, a kompajler će prijaviti da ne može da nađe
3062 ``C:\textbackslash Moj''.
3063
3064 Ovo je nažalost problem okruženja i dok se ne ispravi u nekoj budućoj
3065 verziji ne može se zaobići, tako da je jedino rešenje premestiti
3066 fajlove, odnosno ako je moguće preimenovati problematične foldere.
3067
3068 \mainend
3069
3070