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 13b-\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{Zadatak: Ilustracija pisanja u fajl uz pomoć bafera}
2058
2059 \begin{lstlisting}[style=codeblock]
2060 DEFINITION MODULE QueueInfo;
2061 CONST
2062   Maxqueue = 100;
2063 TYPE
2064   InfoTip = CHAR;
2065
2066 END QueueInfo.
2067
2068 IMPLEMENTATION MODULE QueueInfo;
2069 END QueueInfo.
2070
2071 DEFINITION MODULE RedOpsl1;
2072 FROM QueueInfo IMPORT InfoTip,Maxqueue;
2073 TYPE
2074   Niz = ARRAY[1..Maxqueue] OF InfoTip;
2075   RedOpslTip = RECORD
2076         Prvi, Zadnji : CARDINAL;
2077         Element : Niz
2078   END;
2079
2080 PROCEDURE MakeNull(VAR q : RedOpslTip);
2081 PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
2082 PROCEDURE First(VAR q : RedOpslTip;
2083                 VAR x : InfoTip;
2084                 VAR ok : BOOLEAN);
2085 PROCEDURE PopFirst(VAR q : RedOpslTip;
2086                    VAR ok : BOOLEAN);
2087 PROCEDURE AddRear(VAR q : RedOpslTip;
2088                   x : InfoTip;
2089                   VAR ok : BOOLEAN);
2090
2091 END RedOpsl1.
2092
2093 IMPLEMENTATION MODULE RedOpsl1;
2094 FROM QueueInfo IMPORT Maxqueue,InfoTip;
2095
2096 PROCEDURE MakeNull(VAR q : RedOpslTip);
2097 BEGIN
2098   WITH q DO
2099     Prvi := 0;
2100     Zadnji := 0
2101   END
2102 END MakeNull;
2103
2104 PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
2105 BEGIN
2106   RETURN q.Zadnji = 0
2107 END Empty;
2108
2109
2110 PROCEDURE First(VAR q : RedOpslTip;
2111                 VAR x : InfoTip;
2112                 VAR ok : BOOLEAN);
2113 BEGIN
2114   IF Empty(q) THEN
2115     ok := FALSE
2116   ELSE
2117     ok := TRUE;
2118     WITH q DO
2119       x := Element[Prvi]
2120     END
2121   END
2122 END First;
2123
2124 PROCEDURE AddOne(i : CARDINAL) : CARDINAL;
2125 BEGIN
2126   IF i = Maxqueue THEN
2127     RETURN 1
2128   ELSE
2129     RETURN i+1
2130   END
2131 END AddOne;
2132
2133 PROCEDURE PopFirst(VAR q : RedOpslTip;
2134                    VAR ok : BOOLEAN);
2135 BEGIN
2136   IF Empty(q) THEN
2137     ok := FALSE
2138   ELSE
2139     ok := TRUE;
2140     WITH q DO
2141       IF Prvi = Zadnji THEN
2142         MakeNull(q)
2143       ELSE
2144         Prvi := AddOne(Prvi)
2145       END
2146     END
2147   END
2148 END PopFirst;
2149
2150 PROCEDURE AddRear(VAR q : RedOpslTip;
2151                   x : InfoTip;
2152                   VAR ok : BOOLEAN);
2153 BEGIN
2154   WITH q DO
2155     IF AddOne(Zadnji) = Prvi THEN
2156       ok := FALSE
2157     ELSE
2158       ok := TRUE;
2159       IF Empty(q) THEN
2160         Prvi := 1;
2161         Zadnji := 1
2162       ELSE
2163         Zadnji := AddOne(Zadnji)
2164       END;
2165       Element[Zadnji] := x
2166     END
2167   END
2168 END AddRear;
2169
2170 END RedOpsl1.
2171
2172 MODULE Bafer;
2173 FROM RedOpsl1 IMPORT RedOpslTip, MakeNull, Empty, First, PopFirst, AddRear;
2174 FROM FIO IMPORT File,WrChar, Create, Close;
2175 IMPORT IO;
2176
2177 CONST
2178   ImeIzlaza = 'izlaz.txt';
2179
2180 VAR
2181   izlaz : File;
2182   znak : CHAR;
2183   buffer : RedOpslTip;
2184
2185 PROCEDURE IsprazniBafer(VAR dat : File;
2186                         VAR buf : RedOpslTip);
2187 VAR
2188   znak : CHAR;
2189   ok : BOOLEAN;
2190 BEGIN
2191   WHILE NOT Empty(buf) DO
2192     First(buf, znak, ok);
2193     PopFirst(buf, ok);
2194     WrChar(dat, znak)
2195   END
2196 END IsprazniBafer;
2197
2198 PROCEDURE BaferWrite(VAR dat : File;
2199                      VAR buf : RedOpslTip;
2200                      znak : CHAR);
2201 VAR
2202   ok : BOOLEAN;
2203 BEGIN
2204   AddRear(buf, znak, ok);
2205   IF NOT ok THEN
2206     IsprazniBafer(dat, buf);
2207     AddRear(buf, znak, ok)
2208   END
2209 END BaferWrite;
2210
2211 BEGIN
2212   izlaz := Create(ImeIzlaza);
2213   MakeNull(buffer);
2214   IO.WrStr('Unesite tekst, koji treba da se unese u datoteku ');
2215   IO.WrStr(ImeIzlaza);
2216   IO.WrChar('.');
2217   IO.WrLn;
2218   IO.WrStr('Unos zavrsite tackom.');
2219   IO.WrLn;
2220   znak := IO.RdChar();
2221   WHILE znak # '.' DO
2222     BaferWrite(izlaz, buffer, znak);
2223     znak := IO.RdChar();
2224   END;
2225   IsprazniBafer(izlaz, buffer);
2226   Close(izlaz)
2227 END Bafer.
2228 \end{lstlisting}
2229
2230 \subsection%
2231 {Zadatak: Ispitivanje da li reč pripada gramatici wcw$^+$}
2232
2233 Reč pripada ovoj gramatici ako joj se prvi deo (w) sastoji samo od
2234 slova 'a' i 'b', sledi slovo 'c' a nakon njega obrnuta reč reči w.
2235
2236 \begin{lstlisting}[style=codeblock]
2237 DEFINITION MODULE Stek;
2238 CONST
2239   Maxstack = 100;
2240 TYPE
2241   Niz = ARRAY [1..Maxstack] OF CHAR;
2242   StekTip = RECORD
2243             Top : CARDINAL;
2244             Element : Niz
2245           END;
2246 PROCEDURE MakeNull(VAR s : StekTip);
2247 PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
2248
2249 PROCEDURE Top(VAR s : StekTip;
2250               VAR x : CHAR;
2251               VAR ok : BOOLEAN);
2252 PROCEDURE Pop(VAR s : StekTip;
2253               VAR ok : BOOLEAN);
2254 PROCEDURE Push(VAR s : StekTip;
2255                x : CHAR;
2256                VAR ok : BOOLEAN);
2257 END Stek.
2258
2259
2260 IMPLEMENTATION MODULE Stek;
2261
2262 PROCEDURE MakeNull(VAR s : StekTip);
2263 BEGIN
2264   s.Top := 0
2265 END MakeNull;
2266
2267 PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
2268 BEGIN
2269   RETURN s.Top = 0
2270 END Empty;
2271
2272 PROCEDURE Top(VAR s : StekTip;
2273               VAR x : CHAR;
2274               VAR ok : BOOLEAN);
2275 BEGIN
2276   IF Empty(s) THEN
2277     ok := FALSE
2278   ELSE
2279     ok := TRUE;
2280     WITH s DO
2281       x := Element[Top]
2282     END
2283   END
2284 END Top;
2285 \end{lstlisting}
2286 \manbreakJK
2287 \begin{codeblock}
2288 PROCEDURE Pop(VAR s : StekTip;
2289               VAR ok : BOOLEAN);
2290 BEGIN
2291   IF Empty(s) THEN
2292     ok := FALSE
2293   ELSE
2294     ok := TRUE;
2295     DEC(s.Top)
2296   END
2297 END Pop;
2298
2299 PROCEDURE Push(VAR s : StekTip;
2300                x : CHAR;
2301                VAR ok : BOOLEAN);
2302 BEGIN
2303   WITH s DO
2304     IF Top = Maxstack THEN
2305       ok := FALSE
2306     ELSE
2307       ok := TRUE;
2308       INC(Top);
2309       Element[Top] := x
2310     END
2311   END
2312 END Push;
2313 END Stek.
2314
2315 MODULE wcw;
2316 (* Da li rec pripada gramatici wcw+. *)
2317 FROM Stek IMPORT StekTip, MakeNull, Empty,
2318                  Top, Pop, Push;
2319 FROM InOut IMPORT Read, Write, WriteString, EOL;
2320 TYPE
2321   slova = SET OF CHAR;
2322 VAR
2323   S : StekTip;
2324   Ch, C : CHAR;
2325   ok : BOOLEAN;
2326 BEGIN
2327   MakeNull(S);
2328   Read(Ch);
2329   ok := TRUE;
2330   WHILE ok AND (Ch IN slova{'a', 'b'}) DO
2331     Push(S, Ch, ok);
2332     Read(Ch);
2333   END;
2334   IF NOT ok THEN
2335     WriteString('Greska - mali stek')
2336   ELSIF Ch # 'c' THEN
2337     WriteString('Pogresan string')
2338   ELSE
2339     Read(Ch);
2340     WHILE ok AND (Ch # EOL) DO
2341       Top(S, C, ok);
2342       ok := ok AND (C = Ch);
2343       IF ok THEN
2344         Pop(S, ok);
2345         Read(Ch);
2346       END
2347     END;
2348     IF NOT (ok AND Empty(S)) THEN
2349       WriteString('Pogresan string')
2350     ELSE
2351       WriteString('String pripada jeziku L')
2352     END
2353   END
2354 END wcw.
2355 \end{codeblock}
2356
2357 \manbreakJK
2358
2359 \subsection{Zadatak: Kalkulator za izračunavanje postfiksnih izraza}
2360
2361
2362 Napraviti kalkulator za izračunavanje postfiksnih izraza. Svi brojevi
2363 koji figurišu u izrazu su jednocifreni.
2364
2365 \begin{lstlisting}[style=codeblock]
2366 MODULE PostFix;
2367
2368 FROM StekI IMPORT StekTip, MakeNull, Empty, Top, Pop, Push;
2369 FROM InOut IMPORT Read, Write, WriteInt, EOL;
2370 TYPE
2371   slova = SET OF CHAR;
2372 VAR
2373   S : StekTip;
2374   Ch : CHAR;
2375   Op1, Op2 : INTEGER;
2376   ok : BOOLEAN;
2377 PROCEDURE Conv(Ch : CHAR) : INTEGER;
2378 BEGIN
2379   RETURN  ORD(Ch) - ORD('0')
2380 END Conv;
2381
2382 BEGIN
2383   MakeNull(S);
2384   Read(Ch);
2385   WHILE Ch # EOL DO
2386     IF Ch IN slova{'+', '-', '/', '*', '%'} THEN
2387       Top(S, Op2, ok);
2388       Pop(S, ok);
2389       Top(S, Op1, ok);
2390       Pop(S, ok);
2391       CASE Ch OF
2392         '+' : Op1 := Op1 + Op2 |
2393         '-' : Op1 := Op1 - Op2 |
2394         '*' : Op1 := Op1 * Op2 |
2395         '/' : Op1 := Op1 DIV Op2 |
2396         '%' : Op1 := Op1 MOD Op2
2397       END;
2398       Push(S, Op1, ok)
2399     ELSE
2400       Push(S, Conv(Ch), ok)
2401     END;
2402     Read(Ch);
2403   END;
2404   Top(S, Op1, ok);
2405   Write('=');
2406   WriteInt(Op1,5)
2407 END PostFix.
2408 \end{lstlisting}
2409
2410 \sectionbreak
2411 \section{Simulacija rekurzije}
2412
2413
2414 Na početku označiti sve rekurzivne pozive u originalnoj proceduri
2415 adresama (npr. 1,2,3... ili konstante nabrojivog tipa podataka).
2416
2417 Na steku se čuvaju lokalne promenljive, parametri procedure i adresa
2418 mesta poziva, a u skladu sa tim se kreira InfoTip.
2419
2420 Trivijalnim pozivom se smatra onaj koji se izračunava bez dodatnih
2421 rekurzivnih poziva.
2422
2423 U kodu ispod, \kod{treba\_rekurzija} znači da je poziv netrivijalan,
2424 odnosno treba naći uslove pod kojima se sigurno dešavaju rekurzivni
2425 pozivi.
2426
2427 \begin{lstlisting}
2428 MakeNull(S);
2429 REPEAT
2430   WHILE treba_rekurzija DO
2431     -prepisati sve od pocetka originalne
2432      procedure do prvog rekurzivnog poziva
2433     -staviti na stek potrebne
2434      lokalne promenljive, parametre procedure i
2435      adresu mesta poziva
2436     -podesiti vrednosti parametara da budu
2437      kao u rekurzivnom pozivu procedure
2438   END;
2439   trivijalan poziv
2440   umesto RETURN x pisati rez := x
2441   jos := TRUE;
2442   WHILE jos AND NOT Empty(S) DO
2443     Top(S, el, ok);
2444     Pop(S, ok);
2445     -restauriramo vrednosti sa steka
2446     -u zavisnosti od adrese poziva nastavimo
2447      prepisivanje originalne procedure sa
2448      tog mesta
2449     -ako se dodje do novog rek. poziva tada:
2450        -sacuvati na steku vrednosti
2451        -podesiti vrednosti parametara da budu
2452         kao u rekurzivnom pozivu procedure
2453        -ici na pocetak koda
2454         (ovo se postize sa jos := FALSE)
2455     -inace
2456        ako se naidje na RETURN x pisati rez := x
2457   END
2458 UNTIL Empty(S);
2459 \end{lstlisting}
2460
2461 Ako je procedura funkcijska tada se na kraj dodaje \kod{RETURN rez}.
2462
2463 \subsection*{ZADACI}
2464
2465 Simulirati ponašanje sledećih rekurzivnih procedura (funkcija) upotrebom steka:
2466
2467 \subsection{Primer 1 -- faktorijel}
2468
2469
2470 \begin{lstlisting}[style=codeblock]
2471 MODULE Fakto;
2472 (* InfoTip = CARDINAL; *)
2473
2474 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2475 FROM StekC IMPORT StekTip, MakeNull, Empty,
2476                   Top, Pop, Push;
2477 VAR
2478   n : CARDINAL;
2479 PROCEDURE RFakto(n : CARDINAL) : CARDINAL;
2480 BEGIN
2481   IF n <= 1 THEN
2482     RETURN 1
2483   ELSE
2484     RETURN n * RFakto(n-1)
2485   END
2486 END RFakto;
2487
2488
2489 PROCEDURE SFakto(n : CARDINAL) : CARDINAL;
2490 VAR
2491   s : StekTip;
2492   rez : CARDINAL;
2493   OK : BOOLEAN;
2494 BEGIN
2495   MakeNull(s);
2496   WHILE n > 1 DO
2497     Push(s,n,OK);
2498     DEC(n)
2499   END;
2500   rez := 1;
2501   WHILE NOT Empty(s) DO
2502     Top(s, n, OK);
2503     Pop(s, OK);
2504     rez := n * rez
2505   END;
2506   RETURN rez
2507 END SFakto;
2508
2509 BEGIN
2510   WrStr('n = ');
2511   n := RdCard();
2512   WrLn
2513   WrStr('n! = ');
2514   WrCard(RFakto(n), 1);
2515   WrStr(' = ');
2516   WrCard(SFakto(n), 1)
2517 END Fakto.
2518 \end{lstlisting}
2519
2520 \subsection{Primer 2 -- stepenovanje}
2521
2522 \begin{lstlisting}[style=codeblock]
2523 MODULE Step;
2524 (* InfoTip = RECORD
2525                 x : REAL;
2526                 n : CARDINAL;
2527                 adr : (par, nepar)
2528              END;
2529 *)
2530 FROM IO IMPORT WrStr, WrLn, WrReal,
2531         RdReal, RdCard;
2532 FROM StekStep IMPORT StekTip, MakeNull, Empty,
2533              Top, Pop, Push, InfoTip, AdrTip;
2534 VAR
2535   n : CARDINAL;
2536   x : REAL;
2537
2538 PROCEDURE Sqr(y : REAL) : REAL;
2539 BEGIN
2540   RETURN y * y
2541 END Sqr;
2542
2543 PROCEDURE RStep(x : REAL;
2544                 n : CARDINAL) : REAL;
2545 BEGIN
2546   IF n = 0 THEN
2547     RETURN 1.
2548   ELSIF ODD(n) THEN
2549     RETURN x * Sqr( RStep(x, n DIV 2) )
2550   ELSE
2551     RETURN Sqr( RStep(x, n DIV 2) )
2552   END
2553 END RStep;
2554
2555 PROCEDURE SStep(x : REAL;
2556                 n : CARDINAL ) : REAL;
2557 VAR
2558   s : StekTip;
2559   OK : BOOLEAN;
2560   rez : REAL;
2561   el : InfoTip;
2562 BEGIN
2563   MakeNull(s);
2564   WHILE n > 0 DO
2565     el.x := x;
2566     el.n := n;
2567     IF ODD(n) THEN
2568       el.adr := nepar;
2569     ELSE
2570       el.adr := par
2571     END;
2572     Push(s,el,OK);
2573     n := n DIV 2
2574   END;
2575   rez := 1.;
2576   WHILE NOT Empty(s) DO
2577     Top(s, el, OK);
2578     Pop(s, OK);
2579     x := el.x;
2580     n := el.n;
2581     IF el.adr = nepar THEN
2582       rez := x * Sqr(rez)
2583     ELSE
2584       rez := Sqr(rez)
2585     END
2586   END;
2587   RETURN rez
2588 END SStep;
2589
2590 BEGIN
2591   WrStr('x =? ');
2592   x := RdReal();
2593   WrLn;
2594   WrStr('n =? ');
2595   n := RdCard();
2596   WrStr('x^n = ');
2597   WrReal(RStep(x, n), 10, 1);
2598   WrStr(' = ');
2599   WrReal(SStep(x, n), 10, 1)
2600 END Step.
2601 \end{lstlisting}
2602
2603 \subsection{Primer 3 -- Fibonači}
2604
2605 \begin{lstlisting}[style=codeblock]
2606 MODULE Fib;
2607 (* InfoTip = RECORD
2608                 n : CARDINAL;
2609                 PrviSab : CARDINAL;
2610                 adr : (prvi, drugi)
2611              END;
2612 *)
2613
2614 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2615 FROM StekFib IMPORT StekTip, MakeNull, Empty,
2616        Top, Pop, Push, InfoTip, AdrTip;
2617 VAR
2618   n : CARDINAL;
2619
2620 PROCEDURE RFib(n : CARDINAL) : CARDINAL;
2621 BEGIN
2622   IF n <= 1 THEN
2623     RETURN n
2624   ELSE
2625     RETURN RFib(n-1) + RFib(n-2)
2626   END
2627 END RFib;
2628
2629 PROCEDURE SFib(n : CARDINAL ) : CARDINAL;
2630 VAR
2631   s : StekTip;
2632   OK, jos : BOOLEAN;
2633   rez, PrviSab : CARDINAL;
2634   el : InfoTip;
2635 BEGIN
2636   MakeNull(s);
2637   REPEAT
2638     WHILE n > 1 DO
2639       el.n := n;
2640       el.adr := prvi;
2641       Push(s,el,OK);
2642       DEC(n)
2643     END;
2644     rez := (n);
2645     jos := TRUE;
2646     WHILE (NOT Empty(s)) AND jos DO
2647       Top(s, el, OK);
2648       Pop(s, OK);
2649       n := el.n;
2650       IF el.adr = prvi THEN
2651         PrviSab := rez;
2652         el.n := n;
2653         el.adr := drugi;
2654         el.PrviSab := PrviSab;
2655         Push(s, el, OK);
2656         DEC(n, 2);
2657         jos := FALSE
2658       ELSE
2659         PrviSab := el.PrviSab;
2660         rez := PrviSab + rez
2661       END
2662     END
2663   UNTIL Empty(s);
2664   RETURN rez
2665 END SFib;
2666
2667 BEGIN
2668   WrStr('n =? ');
2669   n := RdCard();
2670   WrStr('F(n) = ');
2671   WrCard(RFib(n), 1);
2672   WrStr(' = ');
2673   WrCard(SFib(n), 1)
2674 END Fib.
2675 \end{lstlisting}
2676
2677 \subsection{Primer 4 -- faktorijel 2}
2678
2679
2680 \begin{lstlisting}[style=codeblock]
2681 MODULE Faktor;
2682 (* InfoTip = CARDINAL; *)
2683 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2684 FROM StekC IMPORT StekTip, MakeNull, Empty,
2685                   Top, Pop, Push;
2686 VAR
2687   n,rez : CARDINAL;
2688
2689 PROCEDURE RFakto(n : CARDINAL;
2690                  VAR rez : CARDINAL);
2691 BEGIN
2692   IF n = 0 THEN
2693     rez := 1
2694   ELSE
2695     RFakto(n-1, rez);
2696     rez := n * rez
2697   END
2698 END RFakto;
2699
2700 PROCEDURE SFakto(n : CARDINAL;
2701                  VAR rez : CARDINAL);
2702 VAR
2703   s : StekTip;
2704   OK : BOOLEAN;
2705 BEGIN
2706   MakeNull(s);
2707   WHILE n > 0 DO
2708     Push(s,n,OK);
2709     DEC(n)
2710   END;
2711   rez := 1;
2712   WHILE NOT Empty(s) DO
2713     Top(s, n, OK);
2714     Pop(s, OK);
2715     rez := n * rez
2716   END
2717 END SFakto;
2718
2719 BEGIN
2720   WrStr('n =? ');
2721   n := RdCard();
2722   WrLn;
2723   WrStr('n! = ');
2724   RFakto(n, rez);
2725   WrCard(rez, 1);
2726   WrStr(' = ');
2727   SFakto(n, rez);
2728   WrCard(rez, 1)
2729 END Faktor.
2730 \end{lstlisting}
2731
2732 \subsection{Primer 5 (ispitni)}
2733
2734
2735 \begin{lstlisting}[style=codeblock]
2736 MODULE Rek1;
2737 (* InfoTip = RECORD
2738                 d, g, m1, m2 : INTEGER;
2739                 adr : (prvi, drugi)
2740              END;
2741 *)
2742 FROM Stek1 IMPORT StekTip, adresa, InfoTip,
2743          MakeNull, Empty, Top, Pop, Push;
2744 IMPORT IO;
2745 VAR
2746   X : ARRAY [1..20] OF INTEGER;
2747
2748 PROCEDURE Max(d, g: INTEGER) : INTEGER;
2749 VAR
2750   m1, m2 : INTEGER;
2751 BEGIN
2752   IF d>g THEN
2753     RETURN MIN(INTEGER)
2754   ELSIF d=g THEN
2755     RETURN X[d]
2756   ELSE
2757     m1 := Max(d, (d+g) DIV 2);
2758     m2 := Max((d+g) DIV 2 +1, g);
2759     IF m1 > m2 THEN
2760       RETURN m1
2761     ELSE
2762       RETURN m2
2763     END
2764   END
2765 END Max;
2766
2767 PROCEDURE SMax(d, g: INTEGER) : INTEGER;
2768 VAR
2769   S : StekTip;
2770   el : InfoTip;
2771   ok, jos : BOOLEAN;
2772   m1, m2, rez : INTEGER;
2773 BEGIN
2774   MakeNull(S);
2775   REPEAT
2776     WHILE d<g DO
2777       el.d := d;
2778       el.g := g;
2779       el.adr := prvi;
2780       Push(S, el, ok);
2781       g := (d+g) DIV 2
2782     END;
2783     IF d>g THEN
2784       rez := MIN(INTEGER)
2785     ELSE (* d=g *)
2786       rez := X[d]
2787     END;
2788     jos := TRUE;
2789     WHILE jos AND NOT Empty(S) DO
2790       Top(S, el, ok);
2791       Pop(S, ok);
2792       d := el.d;
2793       g := el.g;
2794       m1 := el.m1;
2795       IF el.adr = prvi THEN
2796         m1 := rez;
2797         el.m1 := m1;
2798         el.adr := drugi;
2799         Push(S, el, ok);
2800         d := (d+g) DIV 2 + 1;
2801         jos := FALSE
2802       ELSE (*el.adr = drugi*)
2803         m2 := rez;
2804         IF m1 > m2 THEN
2805           rez := m1
2806         ELSE
2807           rez := m2
2808         END
2809       END
2810     END
2811   UNTIL Empty(S);
2812   RETURN rez
2813 END SMax;
2814
2815 BEGIN (* glavni program *)
2816   X[1] := 3;
2817   X[2] := 2;
2818   X[3] := 5;
2819   X[4] := -7;
2820   X[5] := 0;
2821   IO.WrCard(Max(1, 5), 3);
2822   IO.WrLn;
2823   IO.WrCard(SMax(1, 5), 3);
2824   IO.WrLn
2825 END Rek1.
2826 \end{lstlisting}
2827
2828 \subsection{Primer 6 (ispitni)}
2829
2830
2831 \begin{lstlisting}[style=codeblock]
2832 MODULE Rek2;
2833 (* InfoTip = RECORD
2834                 x, y, n : CARDINAL;
2835                 adr : (prvi, drugi, treci, cetvrti)
2836              END;
2837 *)
2838 FROM Stek2 IMPORT StekTip, adresa, InfoTip,
2839            MakeNull, Empty, Top, Pop, Push;
2840 IMPORT IO;
2841
2842 PROCEDURE g(x : CARDINAL; y : CARDINAL;
2843             n : CARDINAL) : CARDINAL;
2844 BEGIN
2845   IF n < 3 THEN
2846     RETURN x + y
2847   ELSIF ODD(n) THEN
2848     RETURN g(g(x+1, y, n-2), y, n-3)
2849   ELSE
2850     RETURN g(x, g(x, y+1, n-2), n-3)
2851   END
2852 END g;
2853
2854 PROCEDURE Sg(x : CARDINAL; y : CARDINAL;
2855              n : CARDINAL) : CARDINAL;
2856 VAR
2857   S : StekTip;
2858   el : InfoTip;
2859   ok, jos : BOOLEAN;
2860   rez : CARDINAL;
2861 BEGIN
2862   MakeNull(S);
2863   REPEAT
2864     WHILE n >= 3 DO
2865       IF ODD(n) THEN
2866         el.x := x;
2867         el.y := y;
2868         el.n := n;
2869         el.adr := prvi;
2870         Push(S, el, ok);
2871         INC(x);
2872         DEC(n, 2)
2873       ELSE
2874         el.x := x;
2875         el.y := y;
2876         el.n := n;
2877         el.adr := treci;
2878         Push(S, el, ok);
2879         INC(y);
2880         DEC(n, 2)
2881       END
2882     END;
2883     rez := x+y;
2884     jos := TRUE;
2885     WHILE jos AND NOT Empty(S) DO
2886       Top(S, el, ok);
2887       Pop(S, ok);
2888       x := el.x;
2889       y := el.y;
2890       n := el.n;
2891       IF el.adr = prvi THEN
2892         el.adr := drugi;
2893         Push(S, el, ok);
2894         x := rez;
2895         DEC(n, 3);
2896         jos := FALSE
2897       ELSIF el.adr = treci THEN
2898         el.adr := cetvrti;
2899         Push(S, el, ok);
2900         y := rez;
2901         DEC(n, 3);
2902         jos := FALSE
2903       END
2904     END
2905   UNTIL Empty(S);
2906   RETURN rez
2907 END Sg;
2908
2909 BEGIN (* glavni program *)
2910   IO.WrCard(g(2, 3, 10), 3);
2911   IO.WrCard(Sg(2, 3, 10), 3);
2912 END Rek2.
2913 \end{lstlisting}
2914
2915 %\columnbreak
2916
2917 \appendix
2918
2919 \sectionbreak
2920 \section{Native XDS Modula 2 -- kratko uputstvo}
2921
2922
2923 Ovo uputstvo ukratko pokriva kako se može nabaviti XDS Modula 2 za Windows
2924 sistem, njenu instalaciju, te kako napraviti i pokretnuti jednostavan program.
2925
2926 \subsection*{Dobavljanje instalacije}
2927
2928
2929 Native XDS Modula 2 se može besplatno skinuti sa sajta proizvođača,
2930 \url{http://www.excelsior-usa.com/}, tačnije na adresi:
2931
2932 \url{http://www.excelsior-usa.com/xdsdl.html}
2933
2934 Prvo se prikazuje ugovor o korišćenju koji na dnu treba potvrditi da ste
2935 razumeli i da ćete ga se pridržavati.
2936
2937 Na stranici koja se potom otvara je potrebno odabrati ``XDS 2.6 beta 2
2938 for Windows'' i snimiti je na računar.
2939
2940 \subsection*{Instalacija okruženja}
2941
2942 Osnovno okruženje (xds-x86...) se instalira pokretanjem prethodno pomenute
2943  instalacione arhive.
2944
2945 \emph{Korisnicima Windows-a 7 preporučujemo da pokrenu instalacione
2946   pakete pomoću opcije ``Run as administrator'' do koje se stiže desnim
2947   klikom miša.}
2948
2949 Pretpostavićemo u daljem tekstu da je program instaliran u
2950 \kod{C:/XDS/}
2951
2952 \subsection*{Pokretanje okruženja}
2953
2954 Po uspešnoj instalaciji bi trebalo da postoji ikonica na desktopu, kao
2955 i grupa sa programom u start meniju.
2956
2957 Ukoliko iz bilo kakvog razloga ne postoje odgovarajuće prečice,
2958 okruženje se može pokrenuti uz pomoć izvršnog fajla
2959 \kod{C:/XDS/BIN/xds.exe} (ako je instalirano na podrazumevanoj
2960 lokaciji).
2961
2962 \subsection*{Prvi projekat}
2963
2964 Da bismo mogli da pišemo i pokrećemo svoj program, potrebno je prvo
2965 napraviti projekat za njega, što se radi na sledeći način:
2966
2967 \begin{itemize}
2968
2969 \item
2970  Iz menija se odabere Project->New.
2971 \item U dijalogu se klikne na gornje dugme ``Browse'', odabere se putanja gde
2972   će se kreirati projekat i ukuca se ime novog projekta.
2973
2974 \item U drugom polju ``Template'' ne treba da piše ništa. Ukoliko
2975   postoji neki tekst, obrisati ga.
2976
2977 \item Kliknuti na ``OK''
2978
2979 \item Iskočiće dijalog na kome piše da ne postoji fajl za editovanje,
2980   kliknuti na ``OK'' da se on napravi.
2981
2982 \item Pojavljuje se forma za kucanje programa, ukucati (na primer):
2983
2984 \begin{minipage}{\columnwidth}
2985 \begin{lstlisting}[style=codeblock]
2986   MODULE Hello;
2987   FROM InOut IMPORT WriteString,WriteLn;
2988   BEGIN
2989     WriteString("Hello World");
2990     WriteLn;
2991   END Hello.
2992 \end{lstlisting}
2993 \end{minipage}
2994
2995 \item Program se može pokrenuti na različite načine, pri čemu se
2996   automatski prevodi:
2997
2998   \begin{itemize}
2999
3000   \item Klik na ``Run'' ikonicu u toolbaru (plavi čovečuljak koji trči)
3001
3002   \item Meni Debug->Run
3003
3004   \item Prečica Ctrl+F9 na tastaturi
3005
3006   \end{itemize}
3007
3008 \item Ako je sve u redu sa programom, treba da se pojavi novi terminal
3009   u kome se ispisuje rezultat izvršavanja programa, u našem slučaju
3010   jednostavna pozdravna poruka.
3011 \end{itemize}
3012
3013 Naravno moguće je i samo prevesti (kompajlirati) program, tako da se
3014 samo prikažu greške (ako ih ima) i bez pokretanja programa:
3015 \begin{itemize}
3016 \item Klik na ``Compile'' ikonicu u toolbaru
3017 \item Meni Tools->Compile
3018 \item Prečica F9 na tastaturi
3019 \end{itemize}
3020
3021 Ukoliko u programu postoje greške, on neće biti pokrenut, već će se
3022 dobiti lista grešaka u donjem delu prozora. Na primer ako obrišemo ``S''
3023 u četvrtom redu i probamo da pokrenemo program, taj red će biti
3024 označen svetlo plavom bojom i dobićemo poruku:
3025
3026 \kod{- Error in pro1.mod [4:5]: Undeclared identifier "Writeting"}
3027
3028 Što znači da u četvrtom redu, kod petog karatkera postoji problem, da
3029 identifikator nije deklarisan, što najčešće znači da ga nismo uvezli,
3030 ili, kao u našem slučaju, da smo napravili grešku u kucanju.
3031
3032 Stvar na koju isto treba obratiti pažnju je da se nekad greška
3033 prijavljue nešto kasnije u tekstu nego što je napravljena. Na primer,
3034 ako obrišemo ``;'' na kraju četvrtog reda i probamo da pokrenemo
3035 program, peti red će biti označen svetlo plavom bojom i dobićemo
3036 poruku:
3037
3038 \kod{- Error in pro1.mod [5:5]: Expected symbol ";" }
3039
3040 Ovo se desilo jer nedostaje tačka zarez na kraju četvrtog reda, ali će
3041 kompajler probati da je traži i dalje, pa će tek na početku petog reda
3042 prijaviti grešku.
3043
3044 U spisku se takođe pojavljuje i upozorenje (Warning) o tome da se
3045 uvezena komanda WriteString ne koristi nigde u programu. Često se
3046 upozorenja mogu ignorisati, a pažnju uglavnom treba obraćati na
3047 greške, odnosno poruke koje počinju sa ``Error''.
3048
3049 Takođe se često dešava da su druge prijavljene greške posledica prve,
3050 te je poželjno ponovo kompajlirati (ili pokretati) program posle svake
3051 ispravljene greške.
3052
3053 \paragraph{Napomena o template-ovima pri kreiranju projekta:}
3054 Moguće je namestiti da u dijalogu za novi projekat drugo polje ``Template''
3055  uvek bude prazno. Potrebno je u tom istom dijalogu kliknuti na
3056  ``Configure'', a potom isprazniti polje ``default template''.
3057
3058 \subsection{Mogući problemi}
3059
3060 \subsubsection*{Nedostajući sistemski moduli}
3061
3062 Verzije pre 2.6 nisu imale uključene u glavni paket sve module koji se
3063 koriste u okviru kursa, i bilo je neophodno da se dodatno instalira i
3064 ``Top Speed Compatibility Pack'' (tscp-x86...). Bez njega je kompajler
3065 prijavljivao da ne postoje neki moduli - najčešće je problem bio da
3066 nedostaje \kod{FIO} modul.
3067
3068 \subsubsection*{Problemi u pokretanju - nemoguće naći exe}
3069
3070 Ako pri pokušaju kompajliranja/pokretanja programa kompajler prijavi
3071 da ne može da nađe exe i pri tome prijavljuje kraću putanju od one
3072 koja je stvarno u pitanju, obično se radi o tome da je postojao razmak
3073 u okviru putanje do modula. Npr ``C:\textbackslash Moj prvi program''
3074 će prouzrokovati probleme, a kompajler će prijaviti da ne može da nađe
3075 ``C:\textbackslash Moj''.
3076
3077 Ovo je nažalost problem okruženja i dok se ne ispravi u nekoj budućoj
3078 verziji ne može se zaobići, tako da je jedino rešenje premestiti
3079 fajlove, odnosno ako je moguće preimenovati problematične foldere.
3080
3081 \mainend
3082
3083