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