skripta-spa1-sadrzaj.tex

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