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