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 2014, Novi Sad}
  13 \newcommand{\verzija}{ver 14a-\varijacija}
  14 %varijacija je definisana u fajlu koji ukljucuje ovaj
  15
  16 \title{\naslov -- \verzija}
  17 \author{\autor}
  18 \date{\datum}
  19
  20 %change the default font
  21 \usepackage{lmodern}
  22 \usepackage{beramono}
  23 \renewcommand{\familydefault}{\sfdefault}
  24
  25 \usepackage{pifont}
  26
  27 %podesavanja outputa za pdf verzije
  28 \usepackage[bookmarks,pdffitwindow=false,unicode=true,%
  29 pdftitle={\naslov -- \verzija},%
  30 pdfauthor={\autor}%
  31 ]{hyperref}
  32
  33 \usepackage{graphicx}
  34 \usepackage{listings}
  35 \usepackage{amsthm}
  36 \usepackage{amsmath}
  37 \usepackage{latexsym}
  38 \usepackage{multicol}
  39
  40 \begin{document}
  41
  42 %customize the itemize environments
  43
  44 \let\olditemize=\itemize
  45 \def\itemize{
  46 \olditemize
  47   \setlength{\itemsep}{1pt}
  48   \setlength{\parskip}{0pt}
  49   \setlength{\parsep}{0pt}
  50   \setlength{\topsep}{-1cm}
  51   \setlength{\partopsep}{1pt}
  52 }
  53
  54 %% specijalni blokovi koji služe kao podsetnici u radu ili napomene
  55 \newcommand{\skica}[1]{
  56     \noindent \framebox{\parbox[c]{0.9\textwidth}{  {\small** \textit{#1}  }}
  57     \newline }
  58 }
  59
  60 \newcommand{\skicas}[1]{
  61     \framebox{* \textit{#1} *}
  62 }
  63
  64 %boldovane skice visokog prioriteta
  65 \newcommand{\skicab}[1]{
  66   \noindent \framebox{\parbox[c]{0.9\textwidth}{ {\small***
  67         \textbf{#1} }} \newline } }
  68
  69 \newcommand{\kod}[1]{{\small\texttt{#1}}}
  70
  71 % ako je sledeci red odkomentarisan nista od skica nece biti ispisano
  72 % u finalni dokument
  73
  74 % \renewcommand{\skica}[1]{}
  75
  76 % title u skladu sa uobičajenim na Departmanu
  77 \newcommand{\makemytitle}{
  78   \begin{center}
  79         \makebox{%
  80         \includegraphics[width=2cm]{grbPMF}
  81         \parbox[b]{65ex}{\centering
  82                 Univerzitet u Novom Sadu\\
  83                 Prirodno-matematički fakultet\\
  84                 Departman za matematiku i informatiku}
  85         \includegraphics[width=2cm]{grbUNS}
  86         }
  87         \vspace{10ex}
  88
  89         \parbox[b]{\textwidth}{{\Large {\bf
  90               Vladimir Kurbalija, \href{mailto:kurba@dmi.rs}{kurba@dmi.rs}\\
  91               Miloš Radovanović, \href{mailto:radacha@dmi.rs}{radacha@dmi.rs}\\
  92               Doni Pracner, \href{mailto:doni.pracner@dmi.rs}{doni.pracner@dmi.rs}}}}
  93         \vspace{15ex}
  94
  95         {\Large {\bf Skripta za vežbe iz predmeta }}
  96
  97         {\Huge {\bf
  98             \setlength{\baselineskip}{1.5\baselineskip}Strukture
  99               podataka i algoritmi 1}}
 100
 101         \vspace{5ex}
 102         %\vfill
 103
 104         \verzija \ -- \datum
 105
 106         \end{center}
 107         \thispagestyle{plain}
 108 %       \newpage
 109 }
 110
 111 \makemytitle
 112
 113 % theorems, definition etc.
 114 %''''''''''''''''''''''''''
 115
 116 \theoremstyle{definition}
 117 \newtheorem{def1}{Definicija}
 118 \theoremstyle{plain}
 119 \newtheorem{theo}{Teorema}
 120 \newtheorem{lema}{Lema}
 121
 122 \lstloadlanguages{Modula-2}
 123
 124 \lstset{
 125         basicstyle=\footnotesize\ttfamily,
 126         showstringspaces=false,
 127         breaklines=true
 128 }
 129
 130 \lstdefinestyle{codeblock}{
 131         basicstyle=\footnotesize\ttfamily,
 132         keywordstyle=\textbf,
 133         columns=[l]fixed,
 134         breakatwhitespace=true,
 135 %        prebreak=\P,
 136 %        postbreak=\ding{229}\space,
 137         language=Modula-2
 138 }
 139
 140 \lstdefinestyle{numcodeblock}{
 141   style=codeblock,
 142   numbers=left
 143 }
 144
 145 \lstnewenvironment{codeblock}{\lstset{style=codeblock}}{}
 146
 147
 148 % ----------------==================--------------------------------------
 149 %                 Pravi pocetak rada
 150
 151 \vfill
 152
 153 Programi u ovoj skripti su testirani sa kompajlerom 'Native XDS Modula
 154 2'. Za verzije pre 2.60 je neophodno dodatno instalirati i TSCP (Top
 155 Speed Compatibility Pack), pošto je potreban za neke od modula koji se
 156 ne nalaze u ISO standardu Module 2. U novijim verzijama su i ovi
 157 moduli uključeni u standardnu instalaciju.
 158
 159 Sav sadržaj se može koristiti u skladu sa {\ttfamily CC-BY-NC-SA} licencom. \\
 160 \url{http://creativecommons.org/licenses/by-nc-sa/3.0/}
 161
 162 \newpage
 163
 164 \tableofcontents
 165
 166 \mainstart
 167
 168 \sectionbreak
 169
 170 \section{Ilustracija efikasnosti algoritma}
 171
 172 \subsection{Zadatak: Pronaći sve pitagorine
 173 trojke do zadate granice}
 174
 175 Pitagorina trojka su tri broja $a,b,c$ za koje važi $a^2 + b^2 = c^2\\$
 176
 177 \begin{lstlisting}[style=codeblock]
 178 MODULE Trojke1;
 179 (* Pitagorine trojke koriscenjem "Brute-force" *)
 180 FROM InOut IMPORT WriteString, WriteLn, WriteCard;
 181 CONST
 182   Gr = 100;
 183 VAR
 184   a, b, c : [1 .. Gr];
 185 BEGIN
 186   FOR a := 1 TO Gr DO
 187     FOR b := 1 TO Gr DO
 188       FOR c := 1 TO Gr DO
 189         IF a*a + b*b = c*c THEN
 190           WriteLn;
 191           WriteString('a = ');
 192           WriteCard(a,2);
 193           WriteString(', b = ');
 194           WriteCard(b,2);
 195           WriteString(', c = ');
 196           WriteCard(c,2)
 197         END
 198       END
 199     END
 200   END
 201 END Trojke1.
 202 \end{lstlisting}
 203
 204 \begin{codeblock}
 205 MODULE Trojke2;
 206 (*Pitagorine trojke koriscenjem zaokrugljivanja*)
 207 FROM InOut IMPORT WriteString, WriteLn, WriteCard;
 208 FROM MathLib0 IMPORT sqrt;
 209 CONST
 210   Gr = 100;
 211 VAR
 212   a, b, c : CARDINAL;
 213   creal : REAL;
 214 BEGIN
 215   FOR a := 1 TO Gr DO
 216     FOR b := 1 TO Gr DO
 217       creal := FLOAT(a*a) + FLOAT(b*b);
 218       creal := sqrt(creal);
 219       c := TRUNC(creal);
 220       IF creal = FLOAT(c) THEN
 221         WriteLn;
 222         WriteString(' a = ');
 223         WriteCard(a,2);
 224         WriteString(', b = ');
 225         WriteCard(b,2);
 226         WriteString(', c = ');
 227         WriteCard(c,2)
 228       END
 229     END
 230   END
 231 END Trojke2.
 232 \end{codeblock}
 233
 234 Sledeći primer koristi Euklidovu teoremu i malo drugačiji pristup.
 235 Ako uzmemo neka dva prirodna broja $m$ i $n$, tada se iz njih može
 236 izvesti jedna Pitagorina trojka koja lako zadovoljava potrebne uslove:
 237 \[
 238 \begin{array}{l}
 239 a = 2mn\\
 240 b = m^2 - n^2\\
 241 c = m^2 + n^2
 242 \end{array}
 243 \]
 244 Odnosno kad probamo da proverimo da li je ovo
 245 Pitagorina trojka dobijamo:
 246 \[
 247 \begin{array}{r@=l}
 248 a^2 + b^2 & c^2\\
 249 (2mn)^2 + (m^2 - n^2)^2 & (m^2 + n^2)^2
 250 \end{array}
 251 \]
 252
 253 \manbreakJK
 254 \begin{codeblock}
 255 MODULE Trojke3;
 256 (* Pitagorine trojke koriscenjem teoreme *)
 257 FROM InOut IMPORT WriteString, WriteLn, WriteCard;
 258 CONST
 259   Gr = 10;
 260 VAR
 261   a, b, c, m, n : CARDINAL;
 262 BEGIN
 263   FOR m := 1 TO Gr DO
 264     FOR n := 1 TO m-1 DO
 265       a := 2*m*n;
 266       b := m*m - n*n;
 267       c := m*m + n*n;
 268       WriteLn;
 269       WriteString('a = ');
 270       WriteCard(a,2);
 271       WriteString(', b = ');
 272       WriteCard(b,2);
 273       WriteString(', c = ');
 274       WriteCard(c,2)
 275     END
 276   END
 277 END Trojke3.
 278 \end{codeblock}
 279
 280 Sledeća dva metoda traže trojke sa nekim specifičnim osobinama.
 281
 282 \begin{codeblock}
 283 MODULE Trojke4;
 284 (* Pitagorine trojke kod kojih je razlika
 285    izmedju katete i hipotenuze tacno 1 *)
 286 FROM InOut IMPORT WriteString, WriteLn, WriteCard;
 287 CONST
 288   Gr = 10;
 289 VAR
 290   a, b, c, m, n : CARDINAL;
 291 BEGIN
 292   FOR m := 2 TO Gr DO
 293     n := m - 1;
 294     a := 2*m*n;
 295     b := m*m - n*n;
 296     c := m*m + n*n;
 297     WriteLn;
 298     WriteString('a = ');
 299     WriteCard(a,2);
 300     WriteString(', b = ');
 301     WriteCard(b,2);
 302     WriteString(', c = ');
 303     WriteCard(c,2)
 304   END
 305 END Trojke4.
 306 \end{codeblock}
 307
 308 \begin{lstlisting}[style=codeblock]
 309 MODULE Trojke5;
 310 (* Pitagorine trojke kod kojih je razlika
 311    izmedju kateta jedan *)
 312 FROM InOut IMPORT WriteString, WriteLn, WriteCard;
 313 CONST
 314   Gr = 7;
 315 VAR
 316   a, b, c, m, n, w, i, temp : CARDINAL;
 317 BEGIN
 318   w := 1;
 319   n := 0;
 320   FOR i := 1 TO Gr DO
 321     m := n + w;
 322     a := 2*m*n;
 323     b := m*m - n*n;
 324     c := m*m + n*n;
 325     WriteLn;
 326     WriteString('a = ');
 327     WriteCard(a,2);
 328     WriteString(', b = ');
 329     WriteCard(b,2);
 330     WriteString(', c = ');
 331     WriteCard(c,2);
 332     temp := w;
 333     w := 3*w + 4*n;
 334     n := 2*temp + 3*n
 335   END
 336 END Trojke5.
 337 \end{lstlisting}
 338
 339 \subsection[Zadatak: Maksimalna suma susednih elemenata u
 340 nizu]{Zadatak: Maksimalna suma proizvoljnog broja susednih elemenata u
 341   nizu celih brojeva}
 342
 343 \begin{lstlisting}[style=codeblock]
 344 MODULE MaxNiza1;
 345 (* Prvo resenje. Brute Force: O(n^3)  *)
 346 FROM InOut IMPORT WriteString,ReadInt,
 347            WriteInt,WriteCard,WriteLn;
 348 CONST
 349   N = 10;
 350 TYPE
 351   Interval = [1..N];
 352 VAR
 353   Max, Suma : INTEGER;
 354   d,g,i,Ood,Doo : Interval;
 355   X : ARRAY Interval OF INTEGER;
 356 BEGIN
 357   WriteString(' Unesite niz X ');
 358   WriteLn;
 359   FOR i := 1 TO N DO
 360     ReadInt(X[i]);
 361     WriteLn
 362   END;
 363   Max := 0;
 364   FOR d := 1 TO N DO
 365     FOR g := 1 TO N DO
 366       Suma := 0;
 367       FOR i := d TO g DO
 368         Suma := Suma + X[i]
 369       END;
 370       IF Suma > Max THEN
 371         Max := Suma;
 372         Ood := d;
 373         Doo := g
 374       END
 375     END
 376   END;
 377   WriteLn;
 378   WriteString(' Maksimum je ');
 379   WriteInt(Max,3);
 380   WriteString(' u intervalu od ');
 381   WriteCard(Ood,3);
 382   WriteString(' do ');
 383   WriteCard(Doo,3)
 384 END MaxNiza1.
 385
 386 MODULE MaxNiza2;
 387 (* Drugo resenje: O(n^2).
 388    Koristi se cinjenica da je suma X[d..g]
 389    izracunljiva iz X[d..g-1].  *)
 390 FROM InOut IMPORT WriteString,ReadInt,
 391            WriteInt,WriteCard,WriteLn;
 392 CONST
 393   N = 10;
 394 TYPE
 395   Interval = [1..N];
 396 VAR
 397   Max, Suma : INTEGER;
 398   d,g,i,Ood,Doo : Interval;
 399   X : ARRAY Interval OF INTEGER;
 400 BEGIN
 401   WriteString(' Unesite niz X ');
 402   WriteLn;
 403   FOR i := 1 TO N DO
 404     ReadInt(X[i]);
 405     WriteLn
 406   END;
 407   Max := 0;
 408   FOR d := 1 TO N DO
 409     Suma := 0;
 410     FOR g := d TO N DO
 411       Suma := Suma + X[g];
 412       IF Suma > Max THEN
 413         Max := Suma;
 414         Ood := d;
 415         Doo := g
 416       END
 417     END
 418   END;
 419   WriteLn;
 420   WriteString(' Maksimum je ');
 421   WriteInt(Max,3);
 422   WriteString(' u intervalu od ');
 423   WriteCard(Ood,3);
 424   WriteString(' do ');
 425   WriteCard(Doo,3)
 426 END MaxNiza2.
 427 \end{lstlisting}
 428
 429 \begin{codeblock}
 430 MODULE MaxNiza3;
 431 (* Trece resenje: O(n^2).
 432    Koristi pomocni niz u kome je na i-tom mestu
 433    suma podniza x[1..i] *)
 434 FROM InOut IMPORT WriteString,ReadInt,
 435            WriteInt,WriteCard,WriteLn;
 436 CONST
 437   N = 10;
 438 TYPE
 439   Interval = [1..N];
 440 VAR
 441   Max, Suma : INTEGER;
 442   d,g,i,Ood,Doo : Interval;
 443   X : ARRAY Interval OF INTEGER;
 444   Pom : ARRAY [0..N] OF INTEGER;
 445 BEGIN
 446   WriteString(' Unesite niz X ');
 447   WriteLn;
 448   FOR i := 1 TO N DO
 449     ReadInt(X[i]);
 450     WriteLn
 451   END;
 452   Pom[0] := 0;
 453   FOR i := 1 TO N DO
 454     Pom[i] := Pom[i-1] + X[i]
 455   END;
 456   Max := 0;
 457   FOR d := 1 TO N DO
 458     FOR g := d TO N DO
 459       Suma := Pom[g] - Pom[d-1];
 460       IF Suma > Max THEN
 461         Max := Suma;
 462         Ood := d;
 463         Doo := g
 464       END
 465     END
 466   END;
 467   WriteLn;
 468   WriteString(' Maksimum je ');
 469   WriteInt(Max,3);
 470   WriteString(' u intervalu od ');
 471   WriteCard(Ood,3);
 472   WriteString(' do ');
 473   WriteCard(Doo,3)
 474 END MaxNiza3.
 475 \end{codeblock}
 476
 477 \begin{codeblock}
 478 MODULE MaxNiza4;
 479 (* Cetvrto resenje. Najbolje moguce: O(n)  *)
 480 FROM InOut IMPORT WriteString,ReadInt,
 481            WriteInt,WriteCard,WriteLn;
 482 CONST
 483   N = 10;
 484 TYPE
 485   Interval = [1..N];
 486 VAR
 487   Max, MaxDovde : INTEGER;
 488   i,d,Ood,Doo : Interval;
 489   X : ARRAY Interval OF INTEGER;
 490 BEGIN
 491   WriteString(' Unesite niz X ');
 492   WriteLn;
 493   FOR i := 1 TO N DO
 494     ReadInt(X[i]);
 495     WriteLn
 496   END;
 497   Max := 0;
 498   MaxDovde := 0;
 499   FOR i := 1 TO N DO
 500     IF MaxDovde = 0 THEN
 501       d := i
 502     END;
 503     MaxDovde := MaxDovde + X[i];
 504     IF MaxDovde < 0 THEN
 505       MaxDovde := 0
 506     END;
 507     IF MaxDovde > Max THEN
 508       Ood := d;
 509       Doo := i;
 510       Max := MaxDovde
 511     END
 512   END;
 513   WriteLn;
 514   WriteString(' Maksimum je ');
 515   WriteInt(Max,3);
 516   WriteString(' u intervalu od ');
 517   WriteCard(Ood,3);
 518   WriteString(' do ');
 519   WriteCard(Doo,3)
 520 END MaxNiza4.
 521 \end{codeblock}
 522
 523 \sectionbreak
 524 \section{Stringovi}
 525
 526
 527 Stringovi -- odnosno nizovi znakova -- ne postoje kao ugrađeni tip u
 528 jeziku Modula 2. Ovo daje slobodu da se niz znakova definiše na dužinu
 529 najadekvatniju za konkretnu primenu. U opštem slučaju definišemo npr:
 530 \begin{codeblock}
 531   TYPE
 532      String = ARRAY [1..30] OF CHAR;
 533 \end{codeblock}
 534
 535 Operacije nad stringovima se najčešće uvoze iz modula \kod{Str}. One
 536 sve prihvataju \emph{otvorene nizove znakova} (strukture definisane sa
 537 \kod{ARRAY OF CHAR}), tako da im se može proslediti niz proizvoljne
 538 dužine.
 539
 540 Određivanje stvarne dužine stringa (tj koliko od maksimalnog
 541 kapaciteta niza je zapravo zauzeto sadržajem) se može izvesti na
 542 sledeći način:
 543 \begin{codeblock}
 544      duzina := Length(str)
 545 \end{codeblock}
 546
 547 Leksikografsko poređenje dva stringa se ne može vršiti standardnim
 548 operatorima kao što su \kod{< > =}. Ovo je delom zato što se radi o
 549 nizovima, a delom i zato što se ne vidi direktno koji deo niza je
 550 popunjen stvarnim sadržajem. Za ovo se koristi komanda \kod{Compare},
 551 koja prihvata dva stringa kao parametre, a vraća broj koji predstavlja
 552 njihov odnos. Taj broj će biti 0 ako su stringovi jednaki, veći
 553 od nule ako je prvi string ``veći'', i manji od nule ako je prvi
 554 string ``manji''. Ovo se lako pamti kad primetimo da je odnos
 555 između \kod{Compare} i 0 isti kao i između prvog i drugog stringa.
 556
 557 \begin{codeblock}
 558   IF    Compare(str1, str2) > 0 THEN
 559      WriteString("Prvi string je veci");
 560   ELSIF Compare(str1, str2) < 0 THEN
 561      WriteString("Prvi string je manji");
 562   ELSE (* moraju biti jednaki *)
 563      WriteString("Jednaki su");
 564   END;
 565 \end{codeblock}
 566
 567 Postoji i modul \kod{Strings} koji ima nešto drugačije definisane
 568 procedure, no na njih se sada nećemo fokusirati.
 569
 570 \sectionbreak
 571 \section{Rad sa fajlovima}
 572
 573 \subsection{Modul FIO}
 574
 575 U ovom modulu je definisan tip \kod{File}, koji predstavlja jedan fajl
 576 sa kojim radimo. Da bi ga koristili moramo ga uvesti u program (isto
 577 kao što uvozimo i komande).
 578
 579 \emph{U primerima se pretpostavlja da je ``f'' tipa \kod{File},
 580   ``str'' niz znakova, ``i'' tipa \kod{INTEGER}, ``c'' tipa
 581   \kod{CARDINAL} i ``ch'' tipa \kod{CHAR}. Dodatna promenljiva ``n''
 582   tipa \kod{INTEGER} služi za formatiranje slično kao u modulu
 583   \kod{InOut}, odnosno za ispis će biti zauzeto bar ``n'' znakova.}
 584
 585
 586 Ako otvaramo već postojeći fajl, poželjno je prvo proveriti da li on
 587 postoji -- u suprotnom naš program će se srušiti pri izvršavanju.
 588 Funkcija \kod{Exists(str)} vraća da li fajl postoji.
 589
 590 Promenljiva tipa \kod{File} se mora vezati za neki fajl
 591 jednom od sledećih komandi:
 592 \begin{itemize}
 593 \item \kod{f := Open(str);} -- otvara se postojeci fajl za čitanje
 594 \item \kod{f := Create(str);} -- kreira se fajl za pisanje; ako je već
 595   postojao, biće zamenjen
 596 \item \kod{f := Append(str);} -- otvara se postojeći fajl za
 597   dopisivanje na kraj
 598 \end{itemize}
 599
 600 Po završetku rada fajl se mora zatvoriti, u našem primeru to bi bilo:
 601 \begin{itemize}
 602 \item \kod{Close(f);}
 603 \end{itemize}
 604
 605 Procedure za čitanje i pisanje su vrlo slične onima iz modula
 606 \kod{IO}, osim što imaju dodatni parametar „\kod{f}“ koji označava
 607 fajl sa kojim se radi.
 608 \begin{itemize}
 609 \item \kod{RdStr(f,str)} -- učitava ceo red u string str
 610 \item \kod{RdItem(f,str)} -- učitava jednu reč u string str (učitava
 611   znakove iz fajla dok ne naiđe na separator)
 612 \item \kod{i:= RdInt(f); c:= RdCard(f)} -- učitava broj, koji se
 613   dobija kao rezultat procedure
 614 \item   \kod{ch:= RdChar(f)} -- vraća jedan znak iz fajla
 615 \end{itemize}
 616
 617 Bitno je obratiti pažnju na specifičnost da postoje dve komande za
 618 čitanje stringova iz fajla i da se one ponašaju različito.  Budući da
 619 razmak spada u separatore to znači da se korišćenjem \kod{RdItem} ne
 620 može učitati string koji ima u sebi razmake.
 621
 622 Analogne su i procedure za pisanje različitih tipova u fajl:
 623 \begin{itemize}
 624 \item \kod{WrStr(f,str);}
 625 \item \kod{WrInt(f,i,n);}
 626 \item \kod{WrCard(f,c,n);}
 627 \item \kod{WrChar(f,ch);}
 628 \end{itemize}
 629
 630 Treba primetiti da ne postoje dve komande za ispis stringa u fajl --
 631 potpuno je svejedno da li on ima razmake u sebi ili ne.
 632
 633 Prelom reda se eksplicitno upisuje u fajl komandom
 634 \begin{itemize}
 635 \item \kod{WrLn(f);}.
 636 \end{itemize}
 637
 638
 639 Da bi odredili da li smo stigli do kraja fajla možemo koristiti
 640 \kod{EOF}. U pitanju je logička promenljiva koja se uvozi iz modula
 641 FIO kao bilo kakva normalna komanda. Ona označava da li smo poslednjom
 642 operacijom čitanja stigli do kraja fajla.  Ne menja joj se vrednost
 643 pri operacijama otvaranja i zatvaranja fajlova, odnosno neće se pri
 644 tome resetovati na \kod{FALSE}, pa na ovo treba obratiti pažnju pri
 645 radu.
 646
 647
 648 \subsection{Zadatak: ispis sadržaja fajla na ekran}
 649
 650 Potrebno je sve redove iz fajla učitati i ispisati ih na ekran.
 651
 652 \begin{lstlisting}[style=codeblock]
 653 MODULE ispis;
 654 FROM FIO IMPORT File, Open, Close, EOF, RdStr;
 655 FROM InOut IMPORT WriteString, WriteLn, ReadString;
 656
 657 PROCEDURE ispisF(ime: ARRAY OF CHAR);
 658 VAR
 659   f:File;
 660   s : ARRAY[1..100] OF CHAR;
 661 BEGIN
 662   f:=Open(ime);
 663   EOF := FALSE;
 664   WHILE NOT EOF DO
 665       RdStr(f,s);
 666       WriteString(s);
 667       WriteLn;
 668   END;
 669   Close(f);
 670 END ispisF;
 671
 672 VAR
 673   ime: ARRAY[1..100] OF CHAR;
 674 BEGIN
 675   WriteString("unesite ime fajla:");
 676   ReadString(ime);
 677   ispisF(ime);
 678 END ispis.
 679 \end{lstlisting}
 680
 681 \subsection{Zadatak: spisak studenata}
 682
 683 Napraviti program koji iz fajla učitava podatke o studentima, dodaje
 684 novog studenta u spisak i snima fajl.  U fajlu se u svakom redu nalazi
 685 podatak o jednom studentu, redom prezime, ime i godina rođenja,
 686 razdvojeni razmacima.
 687
 688 \begin{lstlisting}[style=codeblock]
 689 MODULE nizslog;
 690 FROM InOut IMPORT WriteString, WriteLn,
 691      WriteCard, ReadCard, ReadString;
 692 FROM FIO IMPORT File, Open, Create, Close, EOF,
 693     RdItem, RdCard, WrStr, WrCard, WrLn;
 694 FROM Str IMPORT Compare;
 695
 696 CONST
 697     MaxStud = 100;
 698 TYPE
 699     String = ARRAY[1..30] OF CHAR;
 700     Student = RECORD
 701         ime, prez: String;
 702         god: CARDINAL;
 703     END;
 704     Studenti = ARRAY[1..MaxStud] OF Student;
 705
 706 PROCEDURE UcitajF(fajl:String;
 707           VAR spisak: Studenti; VAR n:CARDINAL);
 708 VAR
 709     f:File;
 710 BEGIN
 711     n:=0;
 712     f:= Open(fajl);
 713     EOF := FALSE;
 714     WHILE NOT EOF DO
 715         INC(n);
 716         RdItem(f, spisak[n].prez);
 717         RdItem(f, spisak[n].ime);
 718         spisak[n].god := RdCard(f);
 719     END;
 720     Close(f);
 721 END UcitajF;
 722
 723 PROCEDURE Ispisi(spisak:Studenti; n:CARDINAL);
 724 VAR
 725     i: CARDINAL;
 726 BEGIN
 727     FOR i:=1 TO n DO
 728         WriteString(spisak[i].prez);
 729         WriteString(" ");
 730         WriteString(spisak[i].ime);
 731         WriteString(" ");
 732         WriteCard(spisak[i].god,1);
 733         WriteLn;
 734     END;
 735 END Ispisi;
 736
 737 PROCEDURE IspisiF(fajl:String;
 738           spisak:Studenti; n:CARDINAL);
 739 VAR
 740     f:File;
 741     i: CARDINAL;
 742 BEGIN
 743     IF (n>0) AND (n<=MaxStud) THEN
 744         f:=Create(fajl);
 745         (* pravimo takav fajl da ne
 746            postoji zadnji prazan red *)
 747         FOR i:=1 TO n-1 DO
 748             WrStr(f,spisak[i].prez);
 749             WrStr(f," ");
 750             WrStr(f,spisak[i].ime);
 751             WrStr(f," ");
 752             WrCard(f,spisak[i].god,1);
 753             WrLn(f);
 754         END;
 755         WrStr(f,spisak[n].prez);
 756         WrStr(f," ");
 757         WrStr(f,spisak[n].ime);
 758         WrStr(f," ");
 759         WrCard(f,spisak[n].god,1);
 760         Close(f);
 761     END;
 762 END IspisiF;
 763
 764 PROCEDURE NoviStudent(VAR spisak:Studenti;
 765                       VAR n:CARDINAL);
 766 VAR
 767     stud,temp:Student;
 768     i:CARDINAL;
 769     dodaj:BOOLEAN;
 770 BEGIN
 771     IF n<MaxStud THEN
 772         WriteString("Prezime novog studenta?");
 773         ReadString(stud.prez);
 774         WriteString("Ime novog studenta?");
 775         ReadString(stud.ime);
 776         WriteString("Godina rodjenja");
 777         WriteString("novog studenta?");
 778         ReadCard(stud.god);
 779         (* proverimo da li vec postoji *)
 780         i:=1;
 781         dodaj := TRUE;
 782         WHILE (i<=n) AND dodaj DO
 783             temp := spisak[i];
 784             IF (temp.god = stud.god) &
 785               (Compare(temp.prez,stud.prez)=0) &
 786               (Compare(temp.ime,stud.ime)=0) THEN
 787                 dodaj:=FALSE;
 788             END;
 789             INC(i);
 790         END;
 791         IF dodaj THEN
 792             INC(n);
 793             spisak[n]:=stud;
 794         ELSE
 795             WriteString("podaci vec postoje!");
 796         END;
 797     ELSE
 798         WriteString("popunjen kapacitet!");
 799     END;
 800 END NoviStudent;
 801
 802 VAR
 803     spisak : Studenti;
 804     fajl:String;
 805     n:CARDINAL;
 806 BEGIN
 807     fajl:="studenti.txt";
 808     UcitajF(fajl, spisak, n);
 809     Ispisi(spisak, n);
 810     NoviStudent(spisak,n);
 811     IspisiF(fajl, spisak, n);
 812 END nizslog.
 813 \end{lstlisting}
 814
 815 \sectionbreak
 816 \section{Liste i pokazivači}
 817
 818 Za rad sa pokazivačima je potrebno iz modula \kod{Storage} uvesti procedure
 819 \kod{ALLOCATE} i \kod{DEALLOCATE}. U kodu se tada mogu koristiti i njihovi
 820 skraćeni oblici \kod{NEW} i \kod{DISPOSE}.
 821
 822 \subsection{Zadatak: Formiranje, štampanje i brisanje listi}
 823
 824
 825 \begin{lstlisting}[style=codeblock]
 826 MODULE liste;
 827 FROM InOut IMPORT WriteString, WriteLn, WriteInt,
 828         ReadInt, ReadCard;
 829 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
 830 TYPE
 831   brojevi = POINTER TO brojSlog;
 832   brojSlog = RECORD
 833       info:INTEGER;
 834       veza:brojevi;
 835   END;
 836 VAR
 837   n,i:CARDINAL;
 838   lista : brojevi;
 839   br:INTEGER;
 840
 841 PROCEDURE DodajPoc(VAR lista:brojevi; br:INTEGER);
 842 (* dodaje broj br na pocetak liste *)
 843 VAR
 844   temp:brojevi;
 845 BEGIN
 846   NEW(temp);
 847   temp^.info := br;
 848   temp^.veza := lista;
 849   lista := temp;
 850 END DodajPoc;
 851
 852 PROCEDURE Stampaj(lista:brojevi);
 853 VAR
 854   temp:brojevi;
 855 BEGIN
 856   temp:=lista;
 857   WHILE temp # NIL DO
 858       WriteInt(temp^.info,0);
 859       WriteLn;
 860       temp := temp^.veza;
 861   END;
 862 END Stampaj;
 863
 864 PROCEDURE Unisti(VAR lista:brojevi);
 865 VAR
 866   temp:brojevi;
 867 BEGIN
 868   temp:=lista;
 869   WHILE temp # NIL DO
 870         lista:=lista^.veza;
 871         DISPOSE(temp);
 872         temp:=lista;
 873   END;
 874 END Unisti;
 875
 876 BEGIN
 877   lista := NIL;
 878   WriteString('unesite n (broj brojeva): ');
 879   ReadCard(n);
 880   WriteString('unesite brojeve: ');
 881   WriteLn;
 882   FOR i:= 1 TO n DO
 883       ReadInt(br);
 884       DodajPoc(lista,br);
 885   END;
 886   WriteString('sadrzaj liste:');
 887   WriteLn;
 888   Stampaj(lista);
 889   Unisti(lista);
 890   WriteString('memorija je oslobodjena');
 891   WriteLn;
 892 END liste.
 893 \end{lstlisting}
 894
 895 Alternativno je poziv \kod{DodajPoc} moguće zameniti pozivom jedne od
 896 sledeće dve procedure čime se dobija dodavanje elementa na kraj liste,
 897 ili kreiranje sortirane liste:
 898
 899 \begin{lstlisting}[style=codeblock]
 900 PROCEDURE DodajKraj(VAR lista:brojevi; br:INTEGER);
 901 (* dodaje element na kraj liste *)
 902 VAR
 903   tekuci, temp :brojevi;
 904 BEGIN
 905   NEW(temp);
 906   temp^.info := br;
 907   temp^.veza := NIL;
 908   IF lista = NIL THEN
 909      (* prazna lista *)
 910      lista:=temp;
 911   ELSE
 912      tekuci := lista;
 913      WHILE tekuci^.veza#NIL DO
 914         tekuci:=tekuci^.veza;
 915      END;
 916      tekuci^.veza := temp;
 917   END;
 918 END DodajKraj;
 919
 920 PROCEDURE DodajSort(VAR lista:brojevi; br:CARDINAL);
 921 (* dodaje broj tako da lista ostane sortirana
 922    (podrazumeva se da je vec sortirana) *)
 923 VAR
 924   temp, tekuci : brojevi;
 925 BEGIN
 926   NEW(temp);
 927   temp^.info:=br;
 928   temp^.veza:=NIL;
 929   IF (lista = NIL) OR (lista^.info>=br) THEN
 930   (*prazna lista ili na pocetak*)
 931     temp^.veza:=lista;
 932     lista := temp;
 933   ELSE
 934   (*negde u listi*)
 935     tekuci:= lista;
 936     WHILE (tekuci^.veza # NIL) AND
 937           (tekuci^.veza^.info<=br) DO
 938       tekuci:=tekuci^.veza;
 939     END;
 940     temp^.veza := tekuci^.veza;
 941     tekuci^.veza:=temp;
 942   END;
 943 END DodajSort;
 944 \end{lstlisting}
 945
 946 \subsection{Zadatak: Prikaz osnovih operacija nad listama}
 947
 948 \begin{lstlisting}[style=codeblock]
 949 MODULE liste2;
 950 FROM InOut IMPORT WriteString, WriteLn,
 951            WriteCard, ReadCard;
 952 FROM IO IMPORT RdKey;
 953 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
 954 TYPE
 955   skupZn = SET OF CHAR;
 956   brojevi = POINTER TO brojSlog;
 957   brojSlog = RECORD
 958       info:CARDINAL;
 959       veza:brojevi;
 960   END;
 961 VAR
 962   lista : brojevi;
 963   menu,prazno:CHAR;
 964
 965 PROCEDURE DodajPoc(VAR lista:brojevi; br:INTEGER);
 966 (* dodaje broj pom na pocetak liste *)
 967 VAR
 968   temp:brojevi;
 969 BEGIN
 970   (* kreiramo novi element *)
 971   NEW(temp);
 972   temp^.info := br;
 973   (* treba da pokazuje na ostatak liste *)
 974   temp^.veza := lista;
 975   (* pocetak liste je novi element *)
 976   lista := temp;
 977 END DodajPoc;
 978
 979 PROCEDURE Unos(VAR lista:brojevi);
 980 (* dodaje n brojeva u listu *)
 981 VAR
 982   n,i,br:CARDINAL;
 983 BEGIN
 984   WriteString('unesite n (broj brojeva): ');
 985   ReadCard(n);
 986   FOR i:= 1 TO n DO
 987       WriteString("unesite broj ");
 988       WriteCard(i,0);
 989       WriteString(": ");
 990       ReadCard(br);
 991       DodajPoc(lista,br);
 992   END;
 993 END Unos;
 994
 995 (* -- procedure za stampu -- *)
 996
 997 PROCEDURE Stampaj(lista:brojevi);
 998 (* stampa sadrzaj liste na ekran *)
 999 VAR
1000   temp:brojevi;
1001 BEGIN
1002   WriteLn;
1003   WriteString("Sadrzaj liste:");
1004   WriteLn;
1005   temp:=lista;
1006   WHILE temp # NIL DO
1007       WriteCard(temp^.info,0);
1008       WriteLn;
1009       temp := temp^.veza;
1010   END;
1011 END Stampaj;
1012
1013 PROCEDURE StampajK(VAR lista:brojevi);
1014 (* stampa k-ti element (k unosi korisnik) *)
1015 VAR
1016   temp:brojevi;
1017   k,brojac:CARDINAL;
1018 BEGIN
1019   WriteString("unesite redni broj elementa:");
1020   ReadCard(k);
1021   temp:=lista;
1022   brojac := 1;
1023   WHILE (temp# NIL) AND (k>brojac) DO
1024     temp:=temp^.veza;
1025     INC(brojac);
1026   END;
1027   IF (temp#NIL) THEN
1028     WriteCard(temp^.info,2);
1029   ELSE
1030     WriteString("greska! - ne postoji element");
1031     WriteString(" u listi sa rednim brojem ");
1032     WriteCard(k,2);
1033   END;
1034   WriteLn();
1035 END StampajK;
1036
1037 PROCEDURE StampajMinimum(VAR lista:brojevi);
1038 (* nalazi i stampa minimalni element liste *)
1039 VAR
1040   temp:brojevi;
1041   min:CARDINAL;
1042 BEGIN
1043   IF (lista=NIL) THEN
1044     WriteString("prazna lista!");
1045   ELSE
1046     min:=lista^.info;
1047     temp:=lista^.veza;
1048     WHILE temp # NIL DO
1049       IF temp^.info < min THEN
1050         min := temp^.info;
1051       END;
1052       temp := temp^.veza;
1053     END;
1054     WriteString("Minimalni element liste je ");
1055     WriteCard(min,0);
1056   END;
1057   WriteLn;
1058 END StampajMinimum;
1059
1060 (* -- pomocne procedure, bez ispisa  -- *)
1061
1062 PROCEDURE UListi(lista:brojevi;
1063                  br: CARDINAL):BOOLEAN;
1064 (* vraca da li se 'br' nalazi u listi 'lista' *)
1065 VAR
1066   temp:brojevi;
1067 BEGIN
1068   temp:=lista;
1069   WHILE (temp # NIL) AND (temp^.info # br) DO
1070     (* dok ne dodjemo do kraja liste
1071        ili ne nadjemo broj *)
1072       temp := temp^.veza;
1073   END;
1074   IF temp#NIL THEN
1075     (* znaci da nismo na kraju liste,
1076        tj da je nadjen broj *)
1077     RETURN TRUE;
1078   ELSE (* temp = NIL *)
1079     RETURN FALSE;
1080   END;
1081 END UListi;
1082
1083 PROCEDURE IzbaciIzListe(VAR lista:brojevi;
1084                         br: CARDINAL):BOOLEAN;
1085 (* izbacuje broj 'br' iz liste, naravno ako
1086    postoji i vraca da li je operacija uspesno
1087    obavljena *)
1088 VAR
1089   temp,prethodni:brojevi;
1090 BEGIN
1091   (* proverimo da li je prvi element *)
1092   IF (lista # NIL) AND (lista^.info = br) THEN
1093     temp:=lista;
1094     lista :=lista^.veza;
1095     DISPOSE(temp);
1096     RETURN TRUE;
1097   ELSE
1098   (* trazimo u ostatku liste *)
1099     temp:=lista;
1100     prethodni:=NIL;
1101     WHILE (temp # NIL) AND (temp^.info # br) DO
1102         (* dok ne dodjemo do kraja liste
1103            ili ne nadjemo broj *)
1104         prethodni:=temp;
1105         temp := temp^.veza;
1106     END;
1107     IF temp#NIL THEN
1108       (* znaci da nismo na kraju liste,
1109          odnosno da smo nasli broj *)
1110       (* prevezemo listu oko elementa *)
1111       prethodni^.veza:=temp^.veza;
1112       DISPOSE(temp);
1113       RETURN TRUE;
1114     ELSE
1115       RETURN FALSE;
1116     END;
1117   END;
1118 END IzbaciIzListe;
1119
1120 PROCEDURE IzbaciIzListeSve(VAR lista:brojevi;
1121                         br: CARDINAL):CARDINAL;
1122 (* izbacuje sve brojeve 'br' iz liste, naravno ako
1123    postoje i vraca koliko ih je bilo *)
1124 VAR
1125   temp,prethodni:brojevi;
1126   brojac : CARDINAL;
1127 BEGIN
1128   brojac := 0;
1129   (* uklanjamo sa pocetka koliko je potrebno *)
1130   WHILE (lista # NIL) AND (lista^.info = br) DO
1131     temp:=lista;
1132     lista :=lista^.veza;
1133     DISPOSE(temp);
1134     INC(brojac);
1135   END;
1136   (* trazimo u ostatku liste *)
1137   IF (lista # NIL) THEN
1138     temp:=lista;
1139     WHILE (temp^.veza # NIL)  DO
1140         (* idemo do poslednjeg elementa liste *)
1141         prethodni:=temp;
1142         temp := temp^.veza;
1143         IF temp^.info = br THEN
1144           (* prevezemo listu oko elementa *)
1145           prethodni^.veza:=temp^.veza;
1146           DISPOSE(temp);
1147           INC(brojac);
1148           (* vracamo se jedan korak da bi
1149           u novom krugu proverili i ovaj element *)
1150           temp := prethodni;
1151         END;
1152     END;
1153   END;
1154   RETURN brojac;
1155 END IzbaciIzListeSve;
1156
1157 (* - procedure sa interakcijom sa korisnikom - *)
1158
1159 PROCEDURE IzbacivanjeEl(VAR lista:brojevi);
1160 (* izbacuje uneti broj iz liste koristeci proceduru IzbaciIzListe *)
1161 VAR
1162   br:CARDINAL;
1163 BEGIN
1164   WriteString("unesite broj za izbacivanje: ");
1165   ReadCard(br);
1166   IF IzbaciIzListe(lista,br) THEN
1167     WriteString("broj je izbacen iz liste");
1168   ELSE
1169     WriteString("greska! - broj ne postoji");
1170   END;
1171   WriteLn;
1172 END IzbacivanjeEl;
1173
1174 PROCEDURE IzbacivanjeElSvi(VAR lista:brojevi);
1175 (* izbacuje sve primeke unetog broj iz liste
1176    koristeci proceduru IzbaciIzListeSve *)
1177 VAR
1178   br, ukupno:CARDINAL;
1179 BEGIN
1180   WriteString("unesite broj za izbacivanje: ");
1181   ReadCard(br);
1182   ukupno := IzbaciIzListeSve(lista,br);
1183   WriteString("Iz liste je izbaceno ");
1184   WriteCard(ukupno,3);
1185   WriteString(" el.");
1186   WriteLn;
1187 END IzbacivanjeElSvi;
1188
1189 PROCEDURE IzbacivanjeK(VAR lista:brojevi);
1190 (* izbacuje k-ti element iz liste *)
1191 VAR
1192   temp,tekuci:brojevi;
1193   k,brojac:CARDINAL;
1194 BEGIN
1195   IF lista=NIL THEN
1196     WriteString("lista je prazna, nema ");
1197     WriteString("elemenata za izbacivanje");
1198   ELSE
1199     WriteString("unesite redni broj elementa");
1200     WriteString(" koji zelite izbaciti:");
1201     ReadCard(k);
1202     IF k=1 THEN (*izbacivanje prvog *)
1203       temp:=lista;
1204       lista := lista^.veza;
1205       DISPOSE(temp);
1206     ELSE
1207       tekuci := lista;
1208       brojac := 2; (*gledamo jedan unapred*)
1209       WHILE (tekuci^.veza# NIL) AND (k>brojac) DO
1210         (* idemo kroz listu do k-tog el *)
1211         tekuci:=tekuci^.veza;
1212         INC(brojac);
1213       END;
1214       IF (tekuci^.veza#NIL) THEN
1215          (* pamtimo element za brisanje *)
1216          temp:=tekuci^.veza;
1217          (* prevezujemo listu oko njega*)
1218          tekuci^.veza:=tekuci^.veza^.veza;
1219          DISPOSE(temp);
1220       ELSE
1221         WriteString("greska! - ne postoji el ");
1222         WriteString("u listi sa rednim brojem ");
1223         WriteCard(k,2);
1224       END;
1225       WriteLn();
1226     END;
1227   END;
1228 END IzbacivanjeK;
1229
1230 PROCEDURE Pretraga(lista:brojevi);
1231 (* provera da li se uneti broj nalazi u listi *)
1232 VAR
1233   br:CARDINAL;
1234 BEGIN
1235   WriteString("unesite trazeni broj");
1236   ReadCard(br);
1237   IF UListi(lista,br) THEN
1238     WriteString("broj postoji u listi");
1239   ELSE
1240     WriteString("broj ne postoji u listi");
1241   END;
1242   WriteLn;
1243 END Pretraga;
1244
1245 (* -- oslobadjanje memorije -- *)
1246
1247 PROCEDURE Unisti(VAR lista:brojevi);
1248 VAR
1249   temp:brojevi;
1250 BEGIN
1251   temp:=lista;
1252   WHILE temp # NIL DO
1253         lista:=lista^.veza;
1254         DISPOSE(temp);
1255         temp:=lista;
1256   END;
1257 END Unisti;
1258
1259 BEGIN
1260   (* pocinjemo od prazne liste *)
1261   lista := NIL;
1262   REPEAT
1263      WriteLn;
1264      WriteString("Ilustracija rada sa");
1265      WriteString(" listama brojeva");
1266      WriteLn;
1267      WriteString("=============================");
1268      WriteLn;
1269      WriteString("s - Stampa");WriteLn;
1270      WriteString("u - Unos");WriteLn;
1271      WriteString("i - Izbacivanje br iz liste");
1272      WriteLn;
1273      WriteString("v - izbacivanje svih br iz liste");
1274      WriteLn;
1275      WriteString("e - izbacivanje k-tog El.");
1276      WriteLn;
1277      WriteString("k - stampanje k-tog elementa");
1278      WriteLn;
1279      WriteString("m - Minimalni broj u listi");
1280      WriteLn;
1281      WriteString("p - Pretraga el. u listi");
1282      WriteLn;
1283      WriteLn;
1284      WriteString("q - kraj rada (Quit)");WriteLn;
1285       REPEAT
1286         menu := CAP(RdKey());
1287       UNTIL menu IN skupZn{'S','U','E','I','V',
1288                            'M','K','P','Q'};
1289       IF menu#'Q' THEN
1290         CASE menu OF
1291          'S' : Stampaj(lista);|
1292          'U' : Unos(lista);|
1293          'I' : IzbacivanjeEl(lista);|
1294          'V' : IzbacivanjeElSvi(lista);|
1295          'E' : IzbacivanjeK(lista);|
1296          'K' : StampajK(lista); |
1297          'M' : StampajMinimum(lista); |
1298          'P' : Pretraga(lista);|
1299         END;
1300         WriteLn;
1301         WriteString("--- pritisnite bilo koji ");
1302         WriteString("taster za povratak u meni");
1303         prazno:=RdKey();
1304       ELSE
1305         WriteString("Kraj rada")
1306       END;
1307       WriteLn;
1308   UNTIL menu='Q';
1309   Unisti(lista);
1310 END liste2.
1311 \end{lstlisting}
1312
1313
1314 \subsection{Zadatak: Prikaz operacija nad listama sa jedinstvenim ključem}
1315
1316 \begin{lstlisting}[style=codeblock]
1317 MODULE Radnici;
1318
1319 FROM InOut IMPORT WriteString, ReadString,
1320            WriteLn, WriteCard, ReadCard, Done;
1321 FROM IO IMPORT RdKey;
1322 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1323
1324 TYPE
1325   skupZn = SET OF CHAR;
1326   str = ARRAY [1..20] OF CHAR;
1327   radnici = POINTER TO slog;
1328   slog = RECORD
1329            ime, prez : str;
1330            broj : CARDINAL;
1331            sled : radnici
1332          END;
1333 VAR
1334   meni, pom : CHAR;
1335   rad : radnici;
1336
1337   PROCEDURE Clear();
1338   VAR
1339     br: CARDINAL;
1340   BEGIN
1341     FOR br:=1 TO 100 DO
1342       WriteLn;
1343     END;
1344   END Clear;
1345
1346   PROCEDURE Spisak(rad : radnici);
1347   BEGIN
1348     WHILE rad # NIL DO
1349       WriteString(rad^.ime);
1350       WriteString(' ');
1351       WriteString(rad^.prez);
1352       WriteCard(rad^.broj, 8);
1353       WriteLn;
1354       rad := rad^.sled
1355     END
1356   END Spisak;
1357
1358   PROCEDURE Zaposli(VAR rad : radnici);
1359   VAR
1360     novi, tek : radnici;
1361     nadjen : BOOLEAN;
1362   BEGIN
1363     NEW(novi);
1364     REPEAT
1365       WriteString('Ime, prezime i jedinstveni');
1366       WriteString(' broj novog radnika: ');
1367       WriteLn;
1368       ReadString(novi^.ime);
1369       ReadString(novi^.prez);
1370       ReadCard(novi^.broj);
1371       nadjen := FALSE;
1372       tek := rad;
1373       WHILE NOT nadjen AND (tek # NIL) AND
1374             (tek^.broj <= novi^.broj) DO
1375         IF novi^.broj = tek^.broj THEN
1376           nadjen := TRUE
1377         ELSE
1378           tek := tek^.sled
1379         END
1380       END
1381     UNTIL Done AND NOT nadjen;
1382     IF (rad = NIL) OR (novi^.broj<rad^.broj) THEN
1383       novi^.sled := rad;
1384       rad := novi
1385     ELSE
1386       tek := rad;
1387       WHILE (tek^.sled # NIL) AND
1388             (tek^.sled^.broj < novi^.broj) DO
1389         tek := tek^.sled
1390       END;
1391       novi^.sled := tek^.sled;
1392       tek^.sled := novi
1393     END
1394   END Zaposli;
1395
1396   PROCEDURE Otpusti(VAR rad : radnici);
1397   VAR
1398     tek, pom : radnici;
1399     br : CARDINAL;
1400   BEGIN
1401     REPEAT
1402       WriteLn;
1403       WriteString('Unesite redni broj radnika:');
1404       ReadCard(br)
1405     UNTIL Done;
1406     WriteLn;
1407     IF rad = NIL THEN
1408       WriteString('Greska.')
1409     ELSIF br = rad^.broj THEN
1410       pom := rad;
1411       rad := rad^.sled;
1412       DISPOSE(pom)
1413     ELSE
1414       tek := rad;
1415       WHILE (tek^.sled # NIL) AND
1416             (tek^.sled^.broj < br) DO
1417         tek := tek^.sled
1418       END;
1419       IF (tek^.sled = NIL) OR
1420          (tek^.sled^.broj > br) THEN
1421         WriteString('Greska.')
1422       ELSE
1423         pom := tek^.sled;
1424         tek^.sled := tek^.sled^.sled;
1425         DISPOSE(pom)
1426       END
1427     END
1428   END Otpusti;
1429
1430   PROCEDURE Inform(rad : radnici);
1431   VAR
1432     br : CARDINAL;
1433   BEGIN
1434     REPEAT
1435       WriteLn;
1436       WriteString('Unesite redni broj radnika:');
1437       ReadCard(br)
1438     UNTIL Done;
1439     WriteLn;
1440     WHILE (rad # NIL) AND (rad^.broj < br) DO
1441       rad := rad^.sled
1442     END;
1443     IF (rad = NIL) OR (rad^.broj # br) THEN
1444       WriteString('Greska.')
1445     ELSE
1446       WriteString(rad^.ime);
1447       WriteString(' ');
1448       WriteString(rad^.prez)
1449     END
1450   END Inform;
1451
1452   PROCEDURE Bankrot(VAR rad : radnici);
1453   VAR
1454     pom : radnici;
1455   BEGIN
1456     WHILE rad # NIL DO
1457       pom := rad;
1458       rad := rad^.sled;
1459       DISPOSE(pom)
1460     END
1461   END Bankrot;
1462
1463 BEGIN
1464   rad := NIL;
1465   REPEAT
1466     Clear;
1467     WriteString('s - spisak svih zaposlenih');
1468     WriteLn;
1469     WriteString('z - zaposljavanje radnika');
1470     WriteLn;
1471     WriteString('o - otpustanje radnika');
1472     WriteLn;
1473     WriteString('i - informacije o radniku');
1474     WriteLn;
1475     WriteString('b - bankrot firme');
1476     WriteLn;
1477     WriteString('k - kraj rada');
1478     WriteLn;
1479     REPEAT
1480       meni := RdKey();
1481     UNTIL CAP(meni) IN skupZn{'S', 'Z', 'O',
1482                               'I', 'B', 'K'};
1483     Clear;
1484     IF CAP(meni) # 'K' THEN
1485       CASE CAP(meni) OF
1486         'S' : Spisak(rad)|
1487         'Z' : Zaposli(rad)|
1488         'O' : Otpusti(rad)|
1489         'I' : Inform(rad)|
1490         'B' : Bankrot(rad)
1491       END;
1492       WriteLn;
1493       WriteString('-- pritisnite bilo koji ');
1494       WriteString('taster za nastavak --');
1495       pom := RdKey()
1496     END
1497   UNTIL CAP(meni) = 'K'
1498 END Radnici.
1499 \end{lstlisting}
1500
1501 Procedura \kod{Spisak} se može realizovati i u rekurzivnoj verziji:
1502
1503 \begin{lstlisting}[style=codeblock]
1504   PROCEDURE Spisak(rad : radnici);
1505   BEGIN
1506     IF rad # NIL THEN
1507       WriteString(rad^.ime);
1508       WriteString(' ');
1509       WriteString(rad^.prez);
1510       WriteCard(rad^.broj, 8);
1511       WriteLn;
1512       Spisak(rad^.sled)
1513     END
1514   END Spisak;
1515 \end{lstlisting}
1516
1517 \subsection[Zadatak: Dve liste osoba sa istim sadržajem]{Zadatak: Dve
1518   liste osoba koje dele sadržaj, jedna sortirana po visini, druga po
1519   težini}
1520
1521 Sa tastature učitavati po dva broja koji opisuju osobu (visina i
1522 težina) i smeštati ih u povezane listu, tako da postoji neopadajuće
1523 uređenje i po visini i po težini.
1524
1525 \begin{lstlisting}[style=codeblock]
1526 MODULE VisTez;
1527 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1528 FROM IO IMPORT WrLn, WrStr, RdCard, WrCard;
1529 FROM SYSTEM IMPORT TSIZE;
1530 TYPE
1531   pok = POINTER TO element;
1532   element = RECORD
1533               visina, tezina : CARDINAL;
1534               Vveza, Tveza : pok
1535             END;
1536 VAR
1537   pocV, pocT : pok;
1538   vis, tez : CARDINAL;
1539 PROCEDURE Ispisi(pocV, pocT : pok);
1540 VAR
1541   tek : pok;
1542 BEGIN
1543   tek := pocV;
1544   WrStr('Po visini:');
1545   WrLn;
1546   WHILE tek # NIL DO
1547     WrCard(tek^.visina, 6);
1548     tek := tek^.Vveza
1549   END;
1550   WrLn;
1551   tek := pocT;
1552   WrStr('Po tezini:');
1553   WrLn;
1554   WHILE tek # NIL DO
1555     WrCard(tek^.tezina,6);
1556     tek := tek^.Tveza
1557   END
1558 END Ispisi;
1559
1560 PROCEDURE Ubaci(VAR pocV, pocT : pok;
1561                 vis, tez : CARDINAL);
1562 VAR
1563   novi, tek, iza : pok;
1564   nadjen : BOOLEAN;
1565 BEGIN
1566   IF pocV = NIL THEN
1567     ALLOCATE(pocV, TSIZE(element));
1568     pocV^.visina := vis;
1569     pocV^.tezina := tez;
1570     pocV^.Vveza := NIL;
1571     pocV^.Tveza := NIL;
1572     pocT := pocV
1573   ELSE
1574     ALLOCATE(novi, TSIZE(element));
1575     novi^.visina := vis;
1576     novi^.tezina := tez;
1577     tek := pocV;
1578     nadjen := FALSE;
1579     WHILE (tek # NIL) AND NOT nadjen DO
1580       nadjen := vis <= tek^.visina;
1581       IF NOT nadjen THEN
1582         iza := tek;
1583         tek := tek^.Vveza
1584       END
1585     END;
1586     novi^.Vveza := tek;
1587     IF tek = pocV THEN
1588       pocV := novi
1589     ELSE
1590       iza^.Vveza := novi
1591     END;
1592     tek := pocT;
1593     nadjen := FALSE;
1594     WHILE (tek # NIL) AND NOT nadjen DO
1595       nadjen := tez <= tek^.tezina;
1596       IF NOT nadjen THEN
1597         iza := tek;
1598         tek := tek^.Tveza
1599       END
1600     END;
1601     novi^.Tveza := tek;
1602     IF tek = pocT THEN
1603       pocT := novi
1604     ELSE
1605       iza^.Tveza := novi
1606     END
1607   END
1608 END Ubaci;
1609
1610 BEGIN
1611   pocV := NIL;
1612   pocT := NIL;
1613   WrStr('Unesite visinu ---- ');
1614   vis := RdCard();
1615   WHILE vis > 0 DO
1616     WrStr('Unesite tezinu ---- ');
1617     tez := RdCard();
1618     Ubaci(pocV, pocT, vis, tez);
1619     WrLn;
1620     WrStr('Unesite visinu ---- ');
1621     vis := RdCard()
1622   END;
1623   WrLn;
1624   Ispisi(pocV, pocT)
1625 END VisTez.
1626 \end{lstlisting}
1627
1628 \sectionbreak
1629 \section{Polinomi preko listi}
1630
1631 \subsection{Moduli}
1632
1633 Polinomi su predstavljeni pomoću pokazivača. Apstraktni tip podataka
1634 \kod{Polinom} je definisan u globalnom modulu.
1635
1636 \paragraph{PolinomL.DEF} \
1637
1638 \lstinputlisting[style=codeblock]{kodovi/polinomi/POLINOML.DEF}
1639
1640 \paragraph{PolinomL.MOD} \
1641
1642 \lstinputlisting[style=codeblock]{kodovi/polinomi/POLINOML.MOD}
1643
1644 \subsection{Zadatak: Sabiranje sa unapred određenim polinomom}
1645
1646 Želimo da ispišemo uneti polinom uvećan za\\ $x^5 - 3x^4 + 4x + 7$.
1647
1648 \lstinputlisting[style=codeblock]{kodovi/polinomi/polinom.MOD}
1649
1650 \subsection{Zadatak: Suma k polinoma}
1651
1652 Napisati program koji ucitava broj k (1<=k<=50) i k polinoma, a nakon
1653 toga izracunava njihovu sumu
1654
1655 \lstinputlisting[style=codeblock]{kodovi/polinomi/PolSuma.MOD}
1656
1657 \sectionbreak
1658 \section{Stek i red opsluživanja}
1659
1660 \subsection{Primer: osnovno korišćenje steka i reda opsluživanja}
1661
1662 \lstinputlisting[style=codeblock]{kodovi/stek-redopsl/stekred.mod}
1663
1664 \subsection{Zadatak: Ilustracija pisanja u fajl uz pomoć bafera}
1665
1666 \begin{lstlisting}[style=codeblock]
1667 DEFINITION MODULE QueueInfo;
1668 CONST
1669   Maxqueue = 100;
1670 TYPE
1671   InfoTip = CHAR;
1672
1673 END QueueInfo.
1674
1675 IMPLEMENTATION MODULE QueueInfo;
1676 END QueueInfo.
1677
1678 DEFINITION MODULE RedOpsl1;
1679 FROM QueueInfo IMPORT InfoTip,Maxqueue;
1680 TYPE
1681   Niz = ARRAY[1..Maxqueue] OF InfoTip;
1682   RedOpslTip = RECORD
1683         Prvi, Zadnji : CARDINAL;
1684         Element : Niz
1685   END;
1686
1687 PROCEDURE MakeNull(VAR q : RedOpslTip);
1688 PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
1689 PROCEDURE First(VAR q : RedOpslTip;
1690                 VAR x : InfoTip;
1691                 VAR ok : BOOLEAN);
1692 PROCEDURE PopFirst(VAR q : RedOpslTip;
1693                    VAR ok : BOOLEAN);
1694 PROCEDURE AddRear(VAR q : RedOpslTip;
1695                   x : InfoTip;
1696                   VAR ok : BOOLEAN);
1697
1698 END RedOpsl1.
1699
1700 IMPLEMENTATION MODULE RedOpsl1;
1701 FROM QueueInfo IMPORT Maxqueue,InfoTip;
1702
1703 PROCEDURE MakeNull(VAR q : RedOpslTip);
1704 BEGIN
1705   WITH q DO
1706     Prvi := 0;
1707     Zadnji := 0
1708   END
1709 END MakeNull;
1710
1711 PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
1712 BEGIN
1713   RETURN q.Zadnji = 0
1714 END Empty;
1715
1716
1717 PROCEDURE First(VAR q : RedOpslTip;
1718                 VAR x : InfoTip;
1719                 VAR ok : BOOLEAN);
1720 BEGIN
1721   IF Empty(q) THEN
1722     ok := FALSE
1723   ELSE
1724     ok := TRUE;
1725     WITH q DO
1726       x := Element[Prvi]
1727     END
1728   END
1729 END First;
1730
1731 PROCEDURE AddOne(i : CARDINAL) : CARDINAL;
1732 BEGIN
1733   IF i = Maxqueue THEN
1734     RETURN 1
1735   ELSE
1736     RETURN i+1
1737   END
1738 END AddOne;
1739
1740 PROCEDURE PopFirst(VAR q : RedOpslTip;
1741                    VAR ok : BOOLEAN);
1742 BEGIN
1743   IF Empty(q) THEN
1744     ok := FALSE
1745   ELSE
1746     ok := TRUE;
1747     WITH q DO
1748       IF Prvi = Zadnji THEN
1749         MakeNull(q)
1750       ELSE
1751         Prvi := AddOne(Prvi)
1752       END
1753     END
1754   END
1755 END PopFirst;
1756
1757 PROCEDURE AddRear(VAR q : RedOpslTip;
1758                   x : InfoTip;
1759                   VAR ok : BOOLEAN);
1760 BEGIN
1761   WITH q DO
1762     IF AddOne(Zadnji) = Prvi THEN
1763       ok := FALSE
1764     ELSE
1765       ok := TRUE;
1766       IF Empty(q) THEN
1767         Prvi := 1;
1768         Zadnji := 1
1769       ELSE
1770         Zadnji := AddOne(Zadnji)
1771       END;
1772       Element[Zadnji] := x
1773     END
1774   END
1775 END AddRear;
1776
1777 END RedOpsl1.
1778
1779 MODULE Bafer;
1780 FROM RedOpsl1 IMPORT RedOpslTip, MakeNull, Empty, First, PopFirst, AddRear;
1781 FROM FIO IMPORT File,WrChar, Create, Close;
1782 IMPORT IO;
1783
1784 CONST
1785   ImeIzlaza = 'izlaz.txt';
1786
1787 VAR
1788   izlaz : File;
1789   znak : CHAR;
1790   buffer : RedOpslTip;
1791
1792 PROCEDURE IsprazniBafer(VAR dat : File;
1793                         VAR buf : RedOpslTip);
1794 VAR
1795   znak : CHAR;
1796   ok : BOOLEAN;
1797 BEGIN
1798   WHILE NOT Empty(buf) DO
1799     First(buf, znak, ok);
1800     PopFirst(buf, ok);
1801     WrChar(dat, znak)
1802   END
1803 END IsprazniBafer;
1804
1805 PROCEDURE BaferWrite(VAR dat : File;
1806                      VAR buf : RedOpslTip;
1807                      znak : CHAR);
1808 VAR
1809   ok : BOOLEAN;
1810 BEGIN
1811   AddRear(buf, znak, ok);
1812   IF NOT ok THEN
1813     IsprazniBafer(dat, buf);
1814     AddRear(buf, znak, ok)
1815   END
1816 END BaferWrite;
1817
1818 BEGIN
1819   izlaz := Create(ImeIzlaza);
1820   MakeNull(buffer);
1821   IO.WrStr('Unesite tekst, koji treba da se unese u datoteku ');
1822   IO.WrStr(ImeIzlaza);
1823   IO.WrChar('.');
1824   IO.WrLn;
1825   IO.WrStr('Unos zavrsite tackom.');
1826   IO.WrLn;
1827   znak := IO.RdChar();
1828   WHILE znak # '.' DO
1829     BaferWrite(izlaz, buffer, znak);
1830     znak := IO.RdChar();
1831   END;
1832   IsprazniBafer(izlaz, buffer);
1833   Close(izlaz)
1834 END Bafer.
1835 \end{lstlisting}
1836
1837 \subsection%
1838 {Zadatak: Ispitivanje da li reč pripada gramatici wcw$^+$}
1839
1840 Reč pripada ovoj gramatici ako joj se prvi deo (w) sastoji samo od
1841 slova 'a' i 'b', sledi slovo 'c' a nakon njega obrnuta reč reči w.
1842
1843 \begin{lstlisting}[style=codeblock]
1844 DEFINITION MODULE Stek;
1845 CONST
1846   Maxstack = 100;
1847 TYPE
1848   Niz = ARRAY [1..Maxstack] OF CHAR;
1849   StekTip = RECORD
1850             Top : CARDINAL;
1851             Element : Niz
1852           END;
1853 PROCEDURE MakeNull(VAR s : StekTip);
1854 PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
1855
1856 PROCEDURE Top(VAR s : StekTip;
1857               VAR x : CHAR;
1858               VAR ok : BOOLEAN);
1859 PROCEDURE Pop(VAR s : StekTip;
1860               VAR ok : BOOLEAN);
1861 PROCEDURE Push(VAR s : StekTip;
1862                x : CHAR;
1863                VAR ok : BOOLEAN);
1864 END Stek.
1865
1866
1867 IMPLEMENTATION MODULE Stek;
1868
1869 PROCEDURE MakeNull(VAR s : StekTip);
1870 BEGIN
1871   s.Top := 0
1872 END MakeNull;
1873
1874 PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
1875 BEGIN
1876   RETURN s.Top = 0
1877 END Empty;
1878
1879 PROCEDURE Top(VAR s : StekTip;
1880               VAR x : CHAR;
1881               VAR ok : BOOLEAN);
1882 BEGIN
1883   IF Empty(s) THEN
1884     ok := FALSE
1885   ELSE
1886     ok := TRUE;
1887     WITH s DO
1888       x := Element[Top]
1889     END
1890   END
1891 END Top;
1892 \end{lstlisting}
1893
1894 \begin{codeblock}
1895 PROCEDURE Pop(VAR s : StekTip;
1896               VAR ok : BOOLEAN);
1897 BEGIN
1898   IF Empty(s) THEN
1899     ok := FALSE
1900   ELSE
1901     ok := TRUE;
1902     DEC(s.Top)
1903   END
1904 END Pop;
1905
1906 PROCEDURE Push(VAR s : StekTip;
1907                x : CHAR;
1908                VAR ok : BOOLEAN);
1909 BEGIN
1910   WITH s DO
1911     IF Top = Maxstack THEN
1912       ok := FALSE
1913     ELSE
1914       ok := TRUE;
1915       INC(Top);
1916       Element[Top] := x
1917     END
1918   END
1919 END Push;
1920 END Stek.
1921
1922 MODULE wcw;
1923 (* Da li rec pripada gramatici wcw+. *)
1924 FROM Stek IMPORT StekTip, MakeNull, Empty,
1925                  Top, Pop, Push;
1926 FROM InOut IMPORT Read, Write, WriteString, EOL;
1927 TYPE
1928   slova = SET OF CHAR;
1929 VAR
1930   S : StekTip;
1931   Ch, C : CHAR;
1932   ok : BOOLEAN;
1933 BEGIN
1934   MakeNull(S);
1935   Read(Ch);
1936   ok := TRUE;
1937   WHILE ok AND (Ch IN slova{'a', 'b'}) DO
1938     Push(S, Ch, ok);
1939     Read(Ch);
1940   END;
1941   IF NOT ok THEN
1942     WriteString('Greska - mali stek')
1943   ELSIF Ch # 'c' THEN
1944     WriteString('Pogresan string')
1945   ELSE
1946     Read(Ch);
1947     WHILE ok AND (Ch # EOL) DO
1948       Top(S, C, ok);
1949       ok := ok AND (C = Ch);
1950       IF ok THEN
1951         Pop(S, ok);
1952         Read(Ch);
1953       END
1954     END;
1955     IF NOT (ok AND Empty(S)) THEN
1956       WriteString('Pogresan string')
1957     ELSE
1958       WriteString('String pripada jeziku L')
1959     END
1960   END
1961 END wcw.
1962 \end{codeblock}
1963
1964 \manbreakJK
1965
1966 \subsection{Zadatak: Kalkulator za izračunavanje postfiksnih izraza}
1967
1968
1969 Napraviti kalkulator za izračunavanje postfiksnih izraza. Svi brojevi
1970 koji figurišu u izrazu su jednocifreni.
1971
1972 \begin{lstlisting}[style=codeblock]
1973 MODULE PostFix;
1974
1975 FROM StekI IMPORT StekTip, MakeNull, Empty, Top, Pop, Push;
1976 FROM InOut IMPORT Read, Write, WriteInt, EOL;
1977 TYPE
1978   slova = SET OF CHAR;
1979 VAR
1980   S : StekTip;
1981   Ch : CHAR;
1982   Op1, Op2 : INTEGER;
1983   ok : BOOLEAN;
1984 PROCEDURE Conv(Ch : CHAR) : INTEGER;
1985 BEGIN
1986   RETURN  ORD(Ch) - ORD('0')
1987 END Conv;
1988
1989 BEGIN
1990   MakeNull(S);
1991   Read(Ch);
1992   WHILE Ch # EOL DO
1993     IF Ch IN slova{'+', '-', '/', '*', '%'} THEN
1994       Top(S, Op2, ok);
1995       Pop(S, ok);
1996       Top(S, Op1, ok);
1997       Pop(S, ok);
1998       CASE Ch OF
1999         '+' : Op1 := Op1 + Op2 |
2000         '-' : Op1 := Op1 - Op2 |
2001         '*' : Op1 := Op1 * Op2 |
2002         '/' : Op1 := Op1 DIV Op2 |
2003         '%' : Op1 := Op1 MOD Op2
2004       END;
2005       Push(S, Op1, ok)
2006     ELSE
2007       Push(S, Conv(Ch), ok)
2008     END;
2009     Read(Ch);
2010   END;
2011   Top(S, Op1, ok);
2012   Write('=');
2013   WriteInt(Op1,5)
2014 END PostFix.
2015 \end{lstlisting}
2016
2017 \sectionbreak
2018 \section{Simulacija rekurzije}
2019
2020
2021 Na početku označiti sve rekurzivne pozive u originalnoj proceduri
2022 adresama (npr. 1,2,3... ili konstante nabrojivog tipa podataka).
2023
2024 Na steku se čuvaju lokalne promenljive, parametri procedure i adresa
2025 mesta poziva, a u skladu sa tim se kreira InfoTip.
2026
2027 Trivijalnim pozivom se smatra onaj koji se izračunava bez dodatnih
2028 rekurzivnih poziva.
2029
2030 U kodu ispod, \kod{treba\_rekurzija} znači da je poziv netrivijalan,
2031 odnosno treba naći uslove pod kojima se sigurno dešavaju rekurzivni
2032 pozivi.
2033
2034 \begin{lstlisting}
2035 MakeNull(S);
2036 REPEAT
2037   WHILE treba_rekurzija DO
2038     -prepisati sve od pocetka originalne
2039      procedure do prvog rekurzivnog poziva
2040     -staviti na stek potrebne
2041      lokalne promenljive, parametre procedure i
2042      adresu mesta poziva
2043     -podesiti vrednosti parametara da budu
2044      kao u rekurzivnom pozivu procedure
2045   END;
2046   trivijalan poziv
2047   umesto RETURN x pisati rez := x
2048   jos := TRUE;
2049   WHILE jos AND NOT Empty(S) DO
2050     Top(S, el, ok);
2051     Pop(S, ok);
2052     -restauriramo vrednosti sa steka
2053     -u zavisnosti od adrese poziva nastavimo
2054      prepisivanje originalne procedure sa
2055      tog mesta
2056     -ako se dodje do novog rek. poziva tada:
2057        -sacuvati na steku vrednosti
2058        -podesiti vrednosti parametara da budu
2059         kao u rekurzivnom pozivu procedure
2060        -ici na pocetak koda
2061         (ovo se postize sa jos := FALSE)
2062     -inace
2063        ako se naidje na RETURN x pisati rez := x
2064   END
2065 UNTIL Empty(S);
2066 \end{lstlisting}
2067
2068 Ako je procedura funkcijska tada se na kraj dodaje \kod{RETURN rez}.
2069
2070 \subsection*{ZADACI}
2071
2072 Simulirati ponašanje sledećih rekurzivnih procedura (funkcija) upotrebom steka:
2073
2074 \subsection{Primer 1 -- faktorijel}
2075
2076
2077 \begin{lstlisting}[style=codeblock]
2078 MODULE Fakto;
2079 (* InfoTip = CARDINAL; *)
2080
2081 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2082 FROM StekC IMPORT StekTip, MakeNull, Empty,
2083                   Top, Pop, Push;
2084 VAR
2085   n : CARDINAL;
2086 PROCEDURE RFakto(n : CARDINAL) : CARDINAL;
2087 BEGIN
2088   IF n <= 1 THEN
2089     RETURN 1
2090   ELSE
2091     RETURN n * RFakto(n-1)
2092   END
2093 END RFakto;
2094
2095
2096 PROCEDURE SFakto(n : CARDINAL) : CARDINAL;
2097 VAR
2098   s : StekTip;
2099   rez : CARDINAL;
2100   OK : BOOLEAN;
2101 BEGIN
2102   MakeNull(s);
2103   WHILE n > 1 DO
2104     Push(s,n,OK);
2105     DEC(n)
2106   END;
2107   rez := 1;
2108   WHILE NOT Empty(s) DO
2109     Top(s, n, OK);
2110     Pop(s, OK);
2111     rez := n * rez
2112   END;
2113   RETURN rez
2114 END SFakto;
2115
2116 BEGIN
2117   WrStr('n = ');
2118   n := RdCard();
2119   WrLn
2120   WrStr('n! = ');
2121   WrCard(RFakto(n), 1);
2122   WrStr(' = ');
2123   WrCard(SFakto(n), 1)
2124 END Fakto.
2125 \end{lstlisting}
2126
2127 \subsection{Primer 2 -- stepenovanje}
2128
2129 \begin{lstlisting}[style=codeblock]
2130 MODULE Step;
2131 (* InfoTip = RECORD
2132                 x : REAL;
2133                 n : CARDINAL;
2134                 adr : (par, nepar)
2135              END;
2136 *)
2137 FROM IO IMPORT WrStr, WrLn, WrReal,
2138         RdReal, RdCard;
2139 FROM StekStep IMPORT StekTip, MakeNull, Empty,
2140              Top, Pop, Push, InfoTip, AdrTip;
2141 VAR
2142   n : CARDINAL;
2143   x : REAL;
2144
2145 PROCEDURE Sqr(y : REAL) : REAL;
2146 BEGIN
2147   RETURN y * y
2148 END Sqr;
2149
2150 PROCEDURE RStep(x : REAL;
2151                 n : CARDINAL) : REAL;
2152 BEGIN
2153   IF n = 0 THEN
2154     RETURN 1.
2155   ELSIF ODD(n) THEN
2156     RETURN x * Sqr( RStep(x, n DIV 2) )
2157   ELSE
2158     RETURN Sqr( RStep(x, n DIV 2) )
2159   END
2160 END RStep;
2161
2162 PROCEDURE SStep(x : REAL;
2163                 n : CARDINAL ) : REAL;
2164 VAR
2165   s : StekTip;
2166   OK : BOOLEAN;
2167   rez : REAL;
2168   el : InfoTip;
2169 BEGIN
2170   MakeNull(s);
2171   WHILE n > 0 DO
2172     el.x := x;
2173     el.n := n;
2174     IF ODD(n) THEN
2175       el.adr := nepar;
2176     ELSE
2177       el.adr := par
2178     END;
2179     Push(s,el,OK);
2180     n := n DIV 2
2181   END;
2182   rez := 1.;
2183   WHILE NOT Empty(s) DO
2184     Top(s, el, OK);
2185     Pop(s, OK);
2186     x := el.x;
2187     n := el.n;
2188     IF el.adr = nepar THEN
2189       rez := x * Sqr(rez)
2190     ELSE
2191       rez := Sqr(rez)
2192     END
2193   END;
2194   RETURN rez
2195 END SStep;
2196
2197 BEGIN
2198   WrStr('x =? ');
2199   x := RdReal();
2200   WrLn;
2201   WrStr('n =? ');
2202   n := RdCard();
2203   WrStr('x^n = ');
2204   WrReal(RStep(x, n), 10, 1);
2205   WrStr(' = ');
2206   WrReal(SStep(x, n), 10, 1)
2207 END Step.
2208 \end{lstlisting}
2209
2210 \subsection{Primer 3 -- Fibonači}
2211
2212 \begin{lstlisting}[style=codeblock]
2213 MODULE Fib;
2214 (* InfoTip = RECORD
2215                 n : CARDINAL;
2216                 PrviSab : CARDINAL;
2217                 adr : (prvi, drugi)
2218              END;
2219 *)
2220
2221 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2222 FROM StekFib IMPORT StekTip, MakeNull, Empty,
2223        Top, Pop, Push, InfoTip, AdrTip;
2224 VAR
2225   n : CARDINAL;
2226
2227 PROCEDURE RFib(n : CARDINAL) : CARDINAL;
2228 BEGIN
2229   IF n <= 1 THEN
2230     RETURN n
2231   ELSE
2232     RETURN RFib(n-1) + RFib(n-2)
2233   END
2234 END RFib;
2235
2236 PROCEDURE SFib(n : CARDINAL ) : CARDINAL;
2237 VAR
2238   s : StekTip;
2239   OK, jos : BOOLEAN;
2240   rez, PrviSab : CARDINAL;
2241   el : InfoTip;
2242 BEGIN
2243   MakeNull(s);
2244   REPEAT
2245     WHILE n > 1 DO
2246       el.n := n;
2247       el.adr := prvi;
2248       Push(s,el,OK);
2249       DEC(n)
2250     END;
2251     rez := (n);
2252     jos := TRUE;
2253     WHILE (NOT Empty(s)) AND jos DO
2254       Top(s, el, OK);
2255       Pop(s, OK);
2256       n := el.n;
2257       IF el.adr = prvi THEN
2258         PrviSab := rez;
2259         el.n := n;
2260         el.adr := drugi;
2261         el.PrviSab := PrviSab;
2262         Push(s, el, OK);
2263         DEC(n, 2);
2264         jos := FALSE
2265       ELSE
2266         PrviSab := el.PrviSab;
2267         rez := PrviSab + rez
2268       END
2269     END
2270   UNTIL Empty(s);
2271   RETURN rez
2272 END SFib;
2273
2274 BEGIN
2275   WrStr('n =? ');
2276   n := RdCard();
2277   WrStr('F(n) = ');
2278   WrCard(RFib(n), 1);
2279   WrStr(' = ');
2280   WrCard(SFib(n), 1)
2281 END Fib.
2282 \end{lstlisting}
2283
2284 \subsection{Primer 4 -- faktorijel 2}
2285
2286
2287 \begin{lstlisting}[style=codeblock]
2288 MODULE Faktor;
2289 (* InfoTip = CARDINAL; *)
2290 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2291 FROM StekC IMPORT StekTip, MakeNull, Empty,
2292                   Top, Pop, Push;
2293 VAR
2294   n,rez : CARDINAL;
2295
2296 PROCEDURE RFakto(n : CARDINAL;
2297                  VAR rez : CARDINAL);
2298 BEGIN
2299   IF n = 0 THEN
2300     rez := 1
2301   ELSE
2302     RFakto(n-1, rez);
2303     rez := n * rez
2304   END
2305 END RFakto;
2306
2307 PROCEDURE SFakto(n : CARDINAL;
2308                  VAR rez : CARDINAL);
2309 VAR
2310   s : StekTip;
2311   OK : BOOLEAN;
2312 BEGIN
2313   MakeNull(s);
2314   WHILE n > 0 DO
2315     Push(s,n,OK);
2316     DEC(n)
2317   END;
2318   rez := 1;
2319   WHILE NOT Empty(s) DO
2320     Top(s, n, OK);
2321     Pop(s, OK);
2322     rez := n * rez
2323   END
2324 END SFakto;
2325
2326 BEGIN
2327   WrStr('n =? ');
2328   n := RdCard();
2329   WrLn;
2330   WrStr('n! = ');
2331   RFakto(n, rez);
2332   WrCard(rez, 1);
2333   WrStr(' = ');
2334   SFakto(n, rez);
2335   WrCard(rez, 1)
2336 END Faktor.
2337 \end{lstlisting}
2338
2339 \subsection{Primer 5 (ispitni)}
2340
2341
2342 \begin{lstlisting}[style=codeblock]
2343 MODULE Rek1;
2344 (* InfoTip = RECORD
2345                 d, g, m1, m2 : INTEGER;
2346                 adr : (prvi, drugi)
2347              END;
2348 *)
2349 FROM Stek1 IMPORT StekTip, adresa, InfoTip,
2350          MakeNull, Empty, Top, Pop, Push;
2351 IMPORT IO;
2352 VAR
2353   X : ARRAY [1..20] OF INTEGER;
2354
2355 PROCEDURE Max(d, g: INTEGER) : INTEGER;
2356 VAR
2357   m1, m2 : INTEGER;
2358 BEGIN
2359   IF d>g THEN
2360     RETURN MIN(INTEGER)
2361   ELSIF d=g THEN
2362     RETURN X[d]
2363   ELSE
2364     m1 := Max(d, (d+g) DIV 2);
2365     m2 := Max((d+g) DIV 2 +1, g);
2366     IF m1 > m2 THEN
2367       RETURN m1
2368     ELSE
2369       RETURN m2
2370     END
2371   END
2372 END Max;
2373
2374 PROCEDURE SMax(d, g: INTEGER) : INTEGER;
2375 VAR
2376   S : StekTip;
2377   el : InfoTip;
2378   ok, jos : BOOLEAN;
2379   m1, m2, rez : INTEGER;
2380 BEGIN
2381   MakeNull(S);
2382   REPEAT
2383     WHILE d<g DO
2384       el.d := d;
2385       el.g := g;
2386       el.adr := prvi;
2387       Push(S, el, ok);
2388       g := (d+g) DIV 2
2389     END;
2390     IF d>g THEN
2391       rez := MIN(INTEGER)
2392     ELSE (* d=g *)
2393       rez := X[d]
2394     END;
2395     jos := TRUE;
2396     WHILE jos AND NOT Empty(S) DO
2397       Top(S, el, ok);
2398       Pop(S, ok);
2399       d := el.d;
2400       g := el.g;
2401       m1 := el.m1;
2402       IF el.adr = prvi THEN
2403         m1 := rez;
2404         el.m1 := m1;
2405         el.adr := drugi;
2406         Push(S, el, ok);
2407         d := (d+g) DIV 2 + 1;
2408         jos := FALSE
2409       ELSE (*el.adr = drugi*)
2410         m2 := rez;
2411         IF m1 > m2 THEN
2412           rez := m1
2413         ELSE
2414           rez := m2
2415         END
2416       END
2417     END
2418   UNTIL Empty(S);
2419   RETURN rez
2420 END SMax;
2421
2422 BEGIN (* glavni program *)
2423   X[1] := 3;
2424   X[2] := 2;
2425   X[3] := 5;
2426   X[4] := -7;
2427   X[5] := 0;
2428   IO.WrCard(Max(1, 5), 3);
2429   IO.WrLn;
2430   IO.WrCard(SMax(1, 5), 3);
2431   IO.WrLn
2432 END Rek1.
2433 \end{lstlisting}
2434
2435 \subsection{Primer 6 (ispitni)}
2436
2437
2438 \begin{lstlisting}[style=codeblock]
2439 MODULE Rek2;
2440 (* InfoTip = RECORD
2441                 x, y, n : CARDINAL;
2442                 adr : (prvi, drugi, treci, cetvrti)
2443              END;
2444 *)
2445 FROM Stek2 IMPORT StekTip, adresa, InfoTip,
2446            MakeNull, Empty, Top, Pop, Push;
2447 IMPORT IO;
2448
2449 PROCEDURE g(x : CARDINAL; y : CARDINAL;
2450             n : CARDINAL) : CARDINAL;
2451 BEGIN
2452   IF n < 3 THEN
2453     RETURN x + y
2454   ELSIF ODD(n) THEN
2455     RETURN g(g(x+1, y, n-2), y, n-3)
2456   ELSE
2457     RETURN g(x, g(x, y+1, n-2), n-3)
2458   END
2459 END g;
2460
2461 PROCEDURE Sg(x : CARDINAL; y : CARDINAL;
2462              n : CARDINAL) : CARDINAL;
2463 VAR
2464   S : StekTip;
2465   el : InfoTip;
2466   ok, jos : BOOLEAN;
2467   rez : CARDINAL;
2468 BEGIN
2469   MakeNull(S);
2470   REPEAT
2471     WHILE n >= 3 DO
2472       IF ODD(n) THEN
2473         el.x := x;
2474         el.y := y;
2475         el.n := n;
2476         el.adr := prvi;
2477         Push(S, el, ok);
2478         INC(x);
2479         DEC(n, 2)
2480       ELSE
2481         el.x := x;
2482         el.y := y;
2483         el.n := n;
2484         el.adr := treci;
2485         Push(S, el, ok);
2486         INC(y);
2487         DEC(n, 2)
2488       END
2489     END;
2490     rez := x+y;
2491     jos := TRUE;
2492     WHILE jos AND NOT Empty(S) DO
2493       Top(S, el, ok);
2494       Pop(S, ok);
2495       x := el.x;
2496       y := el.y;
2497       n := el.n;
2498       IF el.adr = prvi THEN
2499         el.adr := drugi;
2500         Push(S, el, ok);
2501         x := rez;
2502         DEC(n, 3);
2503         jos := FALSE
2504       ELSIF el.adr = treci THEN
2505         el.adr := cetvrti;
2506         Push(S, el, ok);
2507         y := rez;
2508         DEC(n, 3);
2509         jos := FALSE
2510       END
2511     END
2512   UNTIL Empty(S);
2513   RETURN rez
2514 END Sg;
2515
2516 BEGIN (* glavni program *)
2517   IO.WrCard(g(2, 3, 10), 3);
2518   IO.WrCard(Sg(2, 3, 10), 3);
2519 END Rek2.
2520 \end{lstlisting}
2521
2522 %\columnbreak
2523
2524 \appendix
2525
2526 \sectionbreak
2527 \pagenumbering{Roman}
2528 \input{xds-uputstvo}
2529
2530 \mainend
2531
2532
2533
2534 %%% Local Variables:
2535 %%% mode: latex
2536 %%% TeX-master: "skripta-spa1-jk"
2537 %%% End: