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 Budući da Modula 2 definiše mogućnost korišćenja \emph{otvorenih
 536   nizova}, lako je moguće definisati procedure koje kao parametre
 537 primaju bilo koji tip koji je definisan kao niz znakova.
 538
 539 \begin{codeblock}
 540    PROCEDURE ObradaStringa(str: ARRAY OF CHAR);
 541 \end{codeblock}
 542
 543 Konkretne promenljive u programu moraju biti definisane dužine.
 544
 545 Operacije nad stringovima se najčešće uvoze iz modula \kod{Str} i one
 546 su sve definisane da prihvataju \emph{otvorene nizove znakova} kao što
 547 je malopre objašnjeno.
 548
 549 Određivanje stvarne dužine stringa (tj koliko od maksimalnog
 550 kapaciteta niza je zapravo zauzeto sadržajem) se može izvesti na
 551 sledeći način:
 552 \begin{codeblock}
 553      duzina := Length(str)
 554 \end{codeblock}
 555
 556 Leksikografsko poređenje dva stringa se ne može vršiti standardnim
 557 operatorima kao što su \kod{< > =}. Ovo je delom zato što se radi o
 558 nizovima, ali značajnije i zato što se ne vidi direktno koji deo niza
 559 je popunjen ``stvarnim'' sadržajem. Za ovo se koristi komanda
 560 \kod{Compare}, koja prihvata dva stringa kao parametre, a vraća broj
 561 koji predstavlja njihov odnos. Taj broj će biti 0 ako su stringovi
 562 jednaki, veći od nule ako je prvi string ``veći'', i manji od nule ako
 563 je prvi string ``manji''.
 564
 565 \begin{codeblock}
 566   IF    Compare(str1, str2) > 0 THEN
 567      WriteString("Prvi string je veci");
 568   ELSIF Compare(str1, str2) < 0 THEN
 569      WriteString("Prvi string je manji");
 570   ELSE (* moraju biti jednaki *)
 571      WriteString("Jednaki su");
 572   END;
 573 \end{codeblock}
 574
 575 Ovo se lako pamti kad primetimo da je odnos između \kod{Compare} i 0
 576 isti kao i između prvog i drugog stringa.
 577
 578 Postoji i modul \kod{Strings} koji ima nešto drugačije definisane
 579 procedure, no na njih se sada nećemo fokusirati.
 580
 581 \sectionbreak
 582 \section{Rad sa fajlovima}
 583
 584 \subsection{Modul FIO}
 585
 586 U ovom modulu je definisan tip \kod{File}, koji predstavlja jedan fajl
 587 sa kojim radimo. Da bi ga koristili moramo ga uvesti u program (isto
 588 kao što uvozimo i komande).
 589
 590 \emph{U primerima se pretpostavlja da je ``f'' tipa \kod{File},
 591   ``str'' niz znakova, ``i'' tipa \kod{INTEGER}, ``c'' tipa
 592   \kod{CARDINAL} i ``ch'' tipa \kod{CHAR}. Dodatna promenljiva ``n''
 593   tipa \kod{INTEGER} služi za formatiranje slično kao u modulu
 594   \kod{InOut}, odnosno za ispis će biti zauzeto bar ``n'' znakova.}
 595
 596
 597 Ako otvaramo već postojeći fajl, poželjno je prvo proveriti da li on
 598 postoji -- u suprotnom naš program će se srušiti pri izvršavanju.
 599 Funkcija \kod{Exists(str)} vraća da li fajl postoji.
 600
 601 Promenljiva tipa \kod{File} se mora vezati za neki fajl
 602 jednom od sledećih komandi:
 603 \begin{itemize}
 604 \item \kod{f := Open(str);} -- otvara se postojeci fajl za čitanje
 605 \item \kod{f := Create(str);} -- kreira se fajl za pisanje; ako je već
 606   postojao, biće zamenjen
 607 \item \kod{f := Append(str);} -- otvara se postojeći fajl za
 608   dopisivanje na kraj
 609 \end{itemize}
 610
 611 Po završetku rada fajl se mora zatvoriti, u našem primeru to bi bilo:
 612 \begin{itemize}
 613 \item \kod{Close(f);}
 614 \end{itemize}
 615
 616 Procedure za čitanje i pisanje su vrlo slične onima iz modula
 617 \kod{IO}, osim što imaju dodatni parametar „\kod{f}“ koji označava
 618 fajl sa kojim se radi.
 619 \begin{itemize}
 620 \item \kod{RdStr(f,str)} -- učitava ceo red u string str
 621 \item \kod{RdItem(f,str)} -- učitava jednu reč u string str (učitava
 622   znakove iz fajla dok ne naiđe na separator)
 623 \item \kod{i:= RdInt(f); c:= RdCard(f)} -- učitava broj, koji se
 624   dobija kao rezultat procedure
 625 \item   \kod{ch:= RdChar(f)} -- vraća jedan znak iz fajla
 626 \end{itemize}
 627
 628 Bitno je obratiti pažnju na specifičnost da postoje dve komande za
 629 čitanje stringova iz fajla i da se one ponašaju različito.  Budući da
 630 razmak spada u separatore to znači da se korišćenjem \kod{RdItem} ne
 631 može učitati string koji ima u sebi razmake.
 632
 633 Analogne su i procedure za pisanje različitih tipova u fajl:
 634 \begin{itemize}
 635 \item \kod{WrStr(f,str);}
 636 \item \kod{WrInt(f,i,n);}
 637 \item \kod{WrCard(f,c,n);}
 638 \item \kod{WrChar(f,ch);}
 639 \end{itemize}
 640
 641 Treba primetiti da ne postoje dve komande za ispis stringa u fajl --
 642 potpuno je svejedno da li on ima razmake u sebi ili ne.
 643
 644 Prelom reda se eksplicitno upisuje u fajl komandom
 645 \begin{itemize}
 646 \item \kod{WrLn(f);}.
 647 \end{itemize}
 648
 649
 650 Da bi odredili da li smo stigli do kraja fajla možemo koristiti
 651 \kod{EOF}. U pitanju je logička promenljiva koja se uvozi iz modula
 652 FIO kao bilo kakva normalna komanda. Ona označava da li smo poslednjom
 653 operacijom čitanja stigli do kraja fajla.  Ne menja joj se vrednost
 654 pri operacijama otvaranja i zatvaranja fajlova, odnosno neće se pri
 655 tome resetovati na \kod{FALSE}, pa na ovo treba obratiti pažnju pri
 656 radu.
 657
 658 \subsubsection*{Mogući problemi}
 659
 660 U ovoj glavi će biti navedeni neki česti problemi koji se mogu desiti
 661 pri korišćenju FIO modula, a koji su vezani za konkretnu
 662 implementaciju u XDS distribuciji kompajlera.
 663
 664 \paragraph{\kod{RdStr} i drugi pozivi} Prilikom čitanja iz fajlova
 665 može doći do neobičnih rezultata ako se kombinuju pozivi \kod{RdStr}
 666 sa drugima. Problem je u različitom tretiranju separatora. Komanda
 667 \kod{RdStr} uvek čita do kraja reda i pri tome premesti poziciju za
 668 čitanje odmah iza znaka za razdvajanje redova. Ostale komande prvo
 669 preskaču separatore i čitaju sadržaj dok ne naiđu na novi separator
 670 (što može biti novi red, a može biti i razmak, tabulator i neki drugi
 671 znaci) i staju sa čitanjem \emph{pre} tog separatora. Kombinaovanje
 672 ova dva pristupa može dovesti do toga da \kod{RdStr} nakon neke druge
 673 komande učita samo kraj trenutnog reda, a ne sledeći red kao što bi
 674 bilo očekivano.
 675
 676 \paragraph{EOF i prazan red na kraju fajla} Svako čitanje iz fajla
 677 postavlja \kod{EOF} u skladu sa tim da li je komanda stigla do kraja
 678 fajla ili ne. Nažalost kod svih komandi za čitanje (osim \kod{RdStr})
 679 postoji problem ukoliko je na kraju prazan red ili neki dodatni
 680 separator. Tada učitavanje poslednjeg elementa nije zapravo došlo do
 681 kraja fajla. Ako se nakon toga proba još jedno učitavanje sa takvom
 682 komandom ona će probati da preskoči separator i da učita neki sadržaj,
 683 ali će se zaglaviti jer ne može da ga nađe. Ovo ponašanje je greška u
 684 implementaciji FIO modula u okviru XDS distribucije.
 685
 686
 687 \subsection{Zadatak: ispis sadržaja fajla na ekran}
 688
 689 Potrebno je sve redove iz fajla učitati i ispisati ih na ekran.
 690
 691 \lstinputlisting[style=codeblock]{kodovi/fajlovi/ispis.mod}
 692
 693 \subsection{Zadatak: spisak studenata}
 694
 695 Napraviti program koji iz fajla učitava podatke o studentima, dodaje
 696 novog studenta u spisak i snima fajl.  U fajlu se u svakom redu nalazi
 697 podatak o jednom studentu, redom prezime, ime i godina rođenja,
 698 razdvojeni razmacima.
 699
 700 \lstinputlisting[style=codeblock]{kodovi/fajlovi/nizslog.MOD}
 701
 702 \sectionbreak
 703 \section{Liste i pokazivači}
 704
 705 Za rad sa pokazivačima je potrebno iz modula \kod{Storage} uvesti
 706 procedure za dinamičko zauzimanje i oslobađanje
 707 memorije \kod{ALLOCATE} i \kod{DEALLOCATE}.
 708
 709 U kodu se mogu koristiti i skraćeni oblici \kod{NEW} i \kod{DISPOSE}
 710 koji se direktno prevode u prethodno pomenute procedure.
 711
 712 \begin{codeblock}
 713 ALLOCATE(point, SIZE(point));   (* isto kao NEW(point)     *)
 714 DEALLOCATE(point, SIZE(point)); (* isto kao DISPOSE(point) *)
 715 \end{codeblock}
 716
 717 \subsection{Zadatak: Formiranje, štampanje i brisanje listi}
 718
 719
 720 \begin{lstlisting}[style=codeblock]
 721 MODULE liste;
 722 FROM InOut IMPORT WriteString, WriteLn, WriteInt,
 723         ReadInt, ReadCard;
 724 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
 725 TYPE
 726   brojevi = POINTER TO brojSlog;
 727   brojSlog = RECORD
 728       info:INTEGER;
 729       veza:brojevi;
 730   END;
 731 VAR
 732   n,i:CARDINAL;
 733   lista : brojevi;
 734   br:INTEGER;
 735
 736 PROCEDURE DodajPoc(VAR lista:brojevi; br:INTEGER);
 737 (* dodaje broj br na pocetak liste *)
 738 VAR
 739   temp:brojevi;
 740 BEGIN
 741   NEW(temp);
 742   temp^.info := br;
 743   temp^.veza := lista;
 744   lista := temp;
 745 END DodajPoc;
 746
 747 PROCEDURE Stampaj(lista:brojevi);
 748 VAR
 749   temp:brojevi;
 750 BEGIN
 751   temp:=lista;
 752   WHILE temp # NIL DO
 753       WriteInt(temp^.info,0);
 754       WriteLn;
 755       temp := temp^.veza;
 756   END;
 757 END Stampaj;
 758
 759 PROCEDURE Unisti(VAR lista:brojevi);
 760 VAR
 761   temp:brojevi;
 762 BEGIN
 763   temp:=lista;
 764   WHILE temp # NIL DO
 765         lista:=lista^.veza;
 766         DISPOSE(temp);
 767         temp:=lista;
 768   END;
 769 END Unisti;
 770
 771 BEGIN
 772   lista := NIL;
 773   WriteString('unesite n (broj brojeva): ');
 774   ReadCard(n);
 775   WriteString('unesite brojeve: ');
 776   WriteLn;
 777   FOR i:= 1 TO n DO
 778       ReadInt(br);
 779       DodajPoc(lista,br);
 780   END;
 781   WriteString('sadrzaj liste:');
 782   WriteLn;
 783   Stampaj(lista);
 784   Unisti(lista);
 785   WriteString('memorija je oslobodjena');
 786   WriteLn;
 787 END liste.
 788 \end{lstlisting}
 789
 790 Alternativno je poziv \kod{DodajPoc} moguće zameniti pozivom jedne od
 791 sledeće dve procedure čime se dobija dodavanje elementa na kraj liste,
 792 ili kreiranje sortirane liste:
 793
 794 \begin{lstlisting}[style=codeblock]
 795 PROCEDURE DodajKraj(VAR lista:brojevi; br:INTEGER);
 796 (* dodaje element na kraj liste *)
 797 VAR
 798   tekuci, temp :brojevi;
 799 BEGIN
 800   NEW(temp);
 801   temp^.info := br;
 802   temp^.veza := NIL;
 803   IF lista = NIL THEN
 804      (* prazna lista *)
 805      lista:=temp;
 806   ELSE
 807      tekuci := lista;
 808      WHILE tekuci^.veza#NIL DO
 809         tekuci:=tekuci^.veza;
 810      END;
 811      tekuci^.veza := temp;
 812   END;
 813 END DodajKraj;
 814
 815 PROCEDURE DodajSort(VAR lista:brojevi; br:CARDINAL);
 816 (* dodaje broj tako da lista ostane sortirana
 817    (podrazumeva se da je vec sortirana) *)
 818 VAR
 819   temp, tekuci : brojevi;
 820 BEGIN
 821   NEW(temp);
 822   temp^.info:=br;
 823   temp^.veza:=NIL;
 824   IF (lista = NIL) OR (lista^.info>=br) THEN
 825   (*prazna lista ili na pocetak*)
 826     temp^.veza:=lista;
 827     lista := temp;
 828   ELSE
 829   (*negde u listi*)
 830     tekuci:= lista;
 831     WHILE (tekuci^.veza # NIL) AND
 832           (tekuci^.veza^.info<=br) DO
 833       tekuci:=tekuci^.veza;
 834     END;
 835     temp^.veza := tekuci^.veza;
 836     tekuci^.veza:=temp;
 837   END;
 838 END DodajSort;
 839 \end{lstlisting}
 840
 841 \subsection{Zadatak: Prikaz osnovih operacija nad listama}
 842
 843 \begin{lstlisting}[style=codeblock]
 844 MODULE liste2;
 845 FROM InOut IMPORT WriteString, WriteLn,
 846            WriteCard, ReadCard;
 847 FROM IO IMPORT RdKey;
 848 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
 849 TYPE
 850   skupZn = SET OF CHAR;
 851   brojevi = POINTER TO brojSlog;
 852   brojSlog = RECORD
 853       info:CARDINAL;
 854       veza:brojevi;
 855   END;
 856 VAR
 857   lista : brojevi;
 858   menu,prazno:CHAR;
 859
 860 PROCEDURE DodajPoc(VAR lista:brojevi; br:INTEGER);
 861 (* dodaje broj pom na pocetak liste *)
 862 VAR
 863   temp:brojevi;
 864 BEGIN
 865   (* kreiramo novi element *)
 866   NEW(temp);
 867   temp^.info := br;
 868   (* treba da pokazuje na ostatak liste *)
 869   temp^.veza := lista;
 870   (* pocetak liste je novi element *)
 871   lista := temp;
 872 END DodajPoc;
 873
 874 PROCEDURE Unos(VAR lista:brojevi);
 875 (* dodaje n brojeva u listu *)
 876 VAR
 877   n,i,br:CARDINAL;
 878 BEGIN
 879   WriteString('unesite n (broj brojeva): ');
 880   ReadCard(n);
 881   FOR i:= 1 TO n DO
 882       WriteString("unesite broj ");
 883       WriteCard(i,0);
 884       WriteString(": ");
 885       ReadCard(br);
 886       DodajPoc(lista,br);
 887   END;
 888 END Unos;
 889
 890 (* -- procedure za stampu -- *)
 891
 892 PROCEDURE Stampaj(lista:brojevi);
 893 (* stampa sadrzaj liste na ekran *)
 894 VAR
 895   temp:brojevi;
 896 BEGIN
 897   WriteLn;
 898   WriteString("Sadrzaj liste:");
 899   WriteLn;
 900   temp:=lista;
 901   WHILE temp # NIL DO
 902       WriteCard(temp^.info,0);
 903       WriteLn;
 904       temp := temp^.veza;
 905   END;
 906 END Stampaj;
 907
 908 PROCEDURE StampajK(VAR lista:brojevi);
 909 (* stampa k-ti element (k unosi korisnik) *)
 910 VAR
 911   temp:brojevi;
 912   k,brojac:CARDINAL;
 913 BEGIN
 914   WriteString("unesite redni broj elementa:");
 915   ReadCard(k);
 916   temp:=lista;
 917   brojac := 1;
 918   WHILE (temp# NIL) AND (k>brojac) DO
 919     temp:=temp^.veza;
 920     INC(brojac);
 921   END;
 922   IF (temp#NIL) THEN
 923     WriteCard(temp^.info,2);
 924   ELSE
 925     WriteString("greska! - ne postoji element");
 926     WriteString(" u listi sa rednim brojem ");
 927     WriteCard(k,2);
 928   END;
 929   WriteLn();
 930 END StampajK;
 931
 932 PROCEDURE StampajMinimum(VAR lista:brojevi);
 933 (* nalazi i stampa minimalni element liste *)
 934 VAR
 935   temp:brojevi;
 936   min:CARDINAL;
 937 BEGIN
 938   IF (lista=NIL) THEN
 939     WriteString("prazna lista!");
 940   ELSE
 941     min:=lista^.info;
 942     temp:=lista^.veza;
 943     WHILE temp # NIL DO
 944       IF temp^.info < min THEN
 945         min := temp^.info;
 946       END;
 947       temp := temp^.veza;
 948     END;
 949     WriteString("Minimalni element liste je ");
 950     WriteCard(min,0);
 951   END;
 952   WriteLn;
 953 END StampajMinimum;
 954
 955 (* -- pomocne procedure, bez ispisa  -- *)
 956
 957 PROCEDURE UListi(lista:brojevi;
 958                  br: CARDINAL):BOOLEAN;
 959 (* vraca da li se 'br' nalazi u listi 'lista' *)
 960 VAR
 961   temp:brojevi;
 962 BEGIN
 963   temp:=lista;
 964   WHILE (temp # NIL) AND (temp^.info # br) DO
 965     (* dok ne dodjemo do kraja liste
 966        ili ne nadjemo broj *)
 967       temp := temp^.veza;
 968   END;
 969   IF temp#NIL THEN
 970     (* znaci da nismo na kraju liste,
 971        tj da je nadjen broj *)
 972     RETURN TRUE;
 973   ELSE (* temp = NIL *)
 974     RETURN FALSE;
 975   END;
 976 END UListi;
 977
 978 PROCEDURE IzbaciIzListe(VAR lista:brojevi;
 979                         br: CARDINAL):BOOLEAN;
 980 (* izbacuje broj 'br' iz liste, naravno ako
 981    postoji i vraca da li je operacija uspesno
 982    obavljena *)
 983 VAR
 984   temp,prethodni:brojevi;
 985 BEGIN
 986   (* proverimo da li je prvi element *)
 987   IF (lista # NIL) AND (lista^.info = br) THEN
 988     temp:=lista;
 989     lista :=lista^.veza;
 990     DISPOSE(temp);
 991     RETURN TRUE;
 992   ELSE
 993   (* trazimo u ostatku liste *)
 994     temp:=lista;
 995     prethodni:=NIL;
 996     WHILE (temp # NIL) AND (temp^.info # br) DO
 997         (* dok ne dodjemo do kraja liste
 998            ili ne nadjemo broj *)
 999         prethodni:=temp;
1000         temp := temp^.veza;
1001     END;
1002     IF temp#NIL THEN
1003       (* znaci da nismo na kraju liste,
1004          odnosno da smo nasli broj *)
1005       (* prevezemo listu oko elementa *)
1006       prethodni^.veza:=temp^.veza;
1007       DISPOSE(temp);
1008       RETURN TRUE;
1009     ELSE
1010       RETURN FALSE;
1011     END;
1012   END;
1013 END IzbaciIzListe;
1014
1015 PROCEDURE IzbaciIzListeSve(VAR lista:brojevi;
1016                         br: CARDINAL):CARDINAL;
1017 (* izbacuje sve brojeve 'br' iz liste, naravno ako
1018    postoje i vraca koliko ih je bilo *)
1019 VAR
1020   temp,prethodni:brojevi;
1021   brojac : CARDINAL;
1022 BEGIN
1023   brojac := 0;
1024   (* uklanjamo sa pocetka koliko je potrebno *)
1025   WHILE (lista # NIL) AND (lista^.info = br) DO
1026     temp:=lista;
1027     lista :=lista^.veza;
1028     DISPOSE(temp);
1029     INC(brojac);
1030   END;
1031   (* trazimo u ostatku liste *)
1032   IF (lista # NIL) THEN
1033     temp:=lista;
1034     WHILE (temp^.veza # NIL)  DO
1035         (* idemo do poslednjeg elementa liste *)
1036         prethodni:=temp;
1037         temp := temp^.veza;
1038         IF temp^.info = br THEN
1039           (* prevezemo listu oko elementa *)
1040           prethodni^.veza:=temp^.veza;
1041           DISPOSE(temp);
1042           INC(brojac);
1043           (* vracamo se jedan korak da bi
1044           u novom krugu proverili i ovaj element *)
1045           temp := prethodni;
1046         END;
1047     END;
1048   END;
1049   RETURN brojac;
1050 END IzbaciIzListeSve;
1051
1052 (* - procedure sa interakcijom sa korisnikom - *)
1053
1054 PROCEDURE IzbacivanjeEl(VAR lista:brojevi);
1055 (* izbacuje uneti broj iz liste koristeci proceduru IzbaciIzListe *)
1056 VAR
1057   br:CARDINAL;
1058 BEGIN
1059   WriteString("unesite broj za izbacivanje: ");
1060   ReadCard(br);
1061   IF IzbaciIzListe(lista,br) THEN
1062     WriteString("broj je izbacen iz liste");
1063   ELSE
1064     WriteString("greska! - broj ne postoji");
1065   END;
1066   WriteLn;
1067 END IzbacivanjeEl;
1068
1069 PROCEDURE IzbacivanjeElSvi(VAR lista:brojevi);
1070 (* izbacuje sve primeke unetog broj iz liste
1071    koristeci proceduru IzbaciIzListeSve *)
1072 VAR
1073   br, ukupno:CARDINAL;
1074 BEGIN
1075   WriteString("unesite broj za izbacivanje: ");
1076   ReadCard(br);
1077   ukupno := IzbaciIzListeSve(lista,br);
1078   WriteString("Iz liste je izbaceno ");
1079   WriteCard(ukupno,3);
1080   WriteString(" el.");
1081   WriteLn;
1082 END IzbacivanjeElSvi;
1083
1084 PROCEDURE IzbacivanjeK(VAR lista:brojevi);
1085 (* izbacuje k-ti element iz liste *)
1086 VAR
1087   temp,tekuci:brojevi;
1088   k,brojac:CARDINAL;
1089 BEGIN
1090   IF lista=NIL THEN
1091     WriteString("lista je prazna, nema ");
1092     WriteString("elemenata za izbacivanje");
1093   ELSE
1094     WriteString("unesite redni broj elementa");
1095     WriteString(" koji zelite izbaciti:");
1096     ReadCard(k);
1097     IF k=1 THEN (*izbacivanje prvog *)
1098       temp:=lista;
1099       lista := lista^.veza;
1100       DISPOSE(temp);
1101     ELSE
1102       tekuci := lista;
1103       brojac := 2; (*gledamo jedan unapred*)
1104       WHILE (tekuci^.veza# NIL) AND (k>brojac) DO
1105         (* idemo kroz listu do k-tog el *)
1106         tekuci:=tekuci^.veza;
1107         INC(brojac);
1108       END;
1109       IF (tekuci^.veza#NIL) THEN
1110          (* pamtimo element za brisanje *)
1111          temp:=tekuci^.veza;
1112          (* prevezujemo listu oko njega*)
1113          tekuci^.veza:=tekuci^.veza^.veza;
1114          DISPOSE(temp);
1115       ELSE
1116         WriteString("greska! - ne postoji el ");
1117         WriteString("u listi sa rednim brojem ");
1118         WriteCard(k,2);
1119       END;
1120       WriteLn();
1121     END;
1122   END;
1123 END IzbacivanjeK;
1124
1125 PROCEDURE Pretraga(lista:brojevi);
1126 (* provera da li se uneti broj nalazi u listi *)
1127 VAR
1128   br:CARDINAL;
1129 BEGIN
1130   WriteString("unesite trazeni broj");
1131   ReadCard(br);
1132   IF UListi(lista,br) THEN
1133     WriteString("broj postoji u listi");
1134   ELSE
1135     WriteString("broj ne postoji u listi");
1136   END;
1137   WriteLn;
1138 END Pretraga;
1139
1140 (* -- oslobadjanje memorije -- *)
1141
1142 PROCEDURE Unisti(VAR lista:brojevi);
1143 VAR
1144   temp:brojevi;
1145 BEGIN
1146   temp:=lista;
1147   WHILE temp # NIL DO
1148         lista:=lista^.veza;
1149         DISPOSE(temp);
1150         temp:=lista;
1151   END;
1152 END Unisti;
1153
1154 BEGIN
1155   (* pocinjemo od prazne liste *)
1156   lista := NIL;
1157   REPEAT
1158      WriteLn;
1159      WriteString("Ilustracija rada sa");
1160      WriteString(" listama brojeva");
1161      WriteLn;
1162      WriteString("=============================");
1163      WriteLn;
1164      WriteString("s - Stampa");WriteLn;
1165      WriteString("u - Unos");WriteLn;
1166      WriteString("i - Izbacivanje br iz liste");
1167      WriteLn;
1168      WriteString("v - izbacivanje svih br iz liste");
1169      WriteLn;
1170      WriteString("e - izbacivanje k-tog El.");
1171      WriteLn;
1172      WriteString("k - stampanje k-tog elementa");
1173      WriteLn;
1174      WriteString("m - Minimalni broj u listi");
1175      WriteLn;
1176      WriteString("p - Pretraga el. u listi");
1177      WriteLn;
1178      WriteLn;
1179      WriteString("q - kraj rada (Quit)");WriteLn;
1180       REPEAT
1181         menu := CAP(RdKey());
1182       UNTIL menu IN skupZn{'S','U','E','I','V',
1183                            'M','K','P','Q'};
1184       IF menu#'Q' THEN
1185         CASE menu OF
1186          'S' : Stampaj(lista);|
1187          'U' : Unos(lista);|
1188          'I' : IzbacivanjeEl(lista);|
1189          'V' : IzbacivanjeElSvi(lista);|
1190          'E' : IzbacivanjeK(lista);|
1191          'K' : StampajK(lista); |
1192          'M' : StampajMinimum(lista); |
1193          'P' : Pretraga(lista);|
1194         END;
1195         WriteLn;
1196         WriteString("--- pritisnite bilo koji ");
1197         WriteString("taster za povratak u meni");
1198         prazno:=RdKey();
1199       ELSE
1200         WriteString("Kraj rada")
1201       END;
1202       WriteLn;
1203   UNTIL menu='Q';
1204   Unisti(lista);
1205 END liste2.
1206 \end{lstlisting}
1207
1208
1209 \subsection{Zadatak: Prikaz operacija nad listama sa jedinstvenim ključem}
1210
1211 \begin{lstlisting}[style=codeblock]
1212 MODULE Radnici;
1213
1214 FROM InOut IMPORT WriteString, ReadString,
1215            WriteLn, WriteCard, ReadCard, Done;
1216 FROM IO IMPORT RdKey;
1217 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1218
1219 TYPE
1220   skupZn = SET OF CHAR;
1221   str = ARRAY [1..20] OF CHAR;
1222   radnici = POINTER TO slog;
1223   slog = RECORD
1224            ime, prez : str;
1225            broj : CARDINAL;
1226            sled : radnici
1227          END;
1228 VAR
1229   meni, pom : CHAR;
1230   rad : radnici;
1231
1232   PROCEDURE Clear();
1233   VAR
1234     br: CARDINAL;
1235   BEGIN
1236     FOR br:=1 TO 100 DO
1237       WriteLn;
1238     END;
1239   END Clear;
1240
1241   PROCEDURE Spisak(rad : radnici);
1242   BEGIN
1243     WHILE rad # NIL DO
1244       WriteString(rad^.ime);
1245       WriteString(' ');
1246       WriteString(rad^.prez);
1247       WriteCard(rad^.broj, 8);
1248       WriteLn;
1249       rad := rad^.sled
1250     END
1251   END Spisak;
1252
1253   PROCEDURE Zaposli(VAR rad : radnici);
1254   VAR
1255     novi, tek : radnici;
1256     nadjen : BOOLEAN;
1257   BEGIN
1258     NEW(novi);
1259     REPEAT
1260       WriteString('Ime, prezime i jedinstveni');
1261       WriteString(' broj novog radnika: ');
1262       WriteLn;
1263       ReadString(novi^.ime);
1264       ReadString(novi^.prez);
1265       ReadCard(novi^.broj);
1266       nadjen := FALSE;
1267       tek := rad;
1268       WHILE NOT nadjen AND (tek # NIL) AND
1269             (tek^.broj <= novi^.broj) DO
1270         IF novi^.broj = tek^.broj THEN
1271           nadjen := TRUE
1272         ELSE
1273           tek := tek^.sled
1274         END
1275       END
1276     UNTIL Done AND NOT nadjen;
1277     IF (rad = NIL) OR (novi^.broj<rad^.broj) THEN
1278       novi^.sled := rad;
1279       rad := novi
1280     ELSE
1281       tek := rad;
1282       WHILE (tek^.sled # NIL) AND
1283             (tek^.sled^.broj < novi^.broj) DO
1284         tek := tek^.sled
1285       END;
1286       novi^.sled := tek^.sled;
1287       tek^.sled := novi
1288     END
1289   END Zaposli;
1290
1291   PROCEDURE Otpusti(VAR rad : radnici);
1292   VAR
1293     tek, pom : radnici;
1294     br : CARDINAL;
1295   BEGIN
1296     REPEAT
1297       WriteLn;
1298       WriteString('Unesite redni broj radnika:');
1299       ReadCard(br)
1300     UNTIL Done;
1301     WriteLn;
1302     IF rad = NIL THEN
1303       WriteString('Greska.')
1304     ELSIF br = rad^.broj THEN
1305       pom := rad;
1306       rad := rad^.sled;
1307       DISPOSE(pom)
1308     ELSE
1309       tek := rad;
1310       WHILE (tek^.sled # NIL) AND
1311             (tek^.sled^.broj < br) DO
1312         tek := tek^.sled
1313       END;
1314       IF (tek^.sled = NIL) OR
1315          (tek^.sled^.broj > br) THEN
1316         WriteString('Greska.')
1317       ELSE
1318         pom := tek^.sled;
1319         tek^.sled := tek^.sled^.sled;
1320         DISPOSE(pom)
1321       END
1322     END
1323   END Otpusti;
1324
1325   PROCEDURE Inform(rad : radnici);
1326   VAR
1327     br : CARDINAL;
1328   BEGIN
1329     REPEAT
1330       WriteLn;
1331       WriteString('Unesite redni broj radnika:');
1332       ReadCard(br)
1333     UNTIL Done;
1334     WriteLn;
1335     WHILE (rad # NIL) AND (rad^.broj < br) DO
1336       rad := rad^.sled
1337     END;
1338     IF (rad = NIL) OR (rad^.broj # br) THEN
1339       WriteString('Greska.')
1340     ELSE
1341       WriteString(rad^.ime);
1342       WriteString(' ');
1343       WriteString(rad^.prez)
1344     END
1345   END Inform;
1346
1347   PROCEDURE Bankrot(VAR rad : radnici);
1348   VAR
1349     pom : radnici;
1350   BEGIN
1351     WHILE rad # NIL DO
1352       pom := rad;
1353       rad := rad^.sled;
1354       DISPOSE(pom)
1355     END
1356   END Bankrot;
1357
1358 BEGIN
1359   rad := NIL;
1360   REPEAT
1361     Clear;
1362     WriteString('s - spisak svih zaposlenih');
1363     WriteLn;
1364     WriteString('z - zaposljavanje radnika');
1365     WriteLn;
1366     WriteString('o - otpustanje radnika');
1367     WriteLn;
1368     WriteString('i - informacije o radniku');
1369     WriteLn;
1370     WriteString('b - bankrot firme');
1371     WriteLn;
1372     WriteString('k - kraj rada');
1373     WriteLn;
1374     REPEAT
1375       meni := RdKey();
1376     UNTIL CAP(meni) IN skupZn{'S', 'Z', 'O',
1377                               'I', 'B', 'K'};
1378     Clear;
1379     IF CAP(meni) # 'K' THEN
1380       CASE CAP(meni) OF
1381         'S' : Spisak(rad)|
1382         'Z' : Zaposli(rad)|
1383         'O' : Otpusti(rad)|
1384         'I' : Inform(rad)|
1385         'B' : Bankrot(rad)
1386       END;
1387       WriteLn;
1388       WriteString('-- pritisnite bilo koji ');
1389       WriteString('taster za nastavak --');
1390       pom := RdKey()
1391     END
1392   UNTIL CAP(meni) = 'K'
1393 END Radnici.
1394 \end{lstlisting}
1395
1396 Procedura \kod{Spisak} se može realizovati i u rekurzivnoj verziji:
1397
1398 \begin{lstlisting}[style=codeblock]
1399   PROCEDURE Spisak(rad : radnici);
1400   BEGIN
1401     IF rad # NIL THEN
1402       WriteString(rad^.ime);
1403       WriteString(' ');
1404       WriteString(rad^.prez);
1405       WriteCard(rad^.broj, 8);
1406       WriteLn;
1407       Spisak(rad^.sled)
1408     END
1409   END Spisak;
1410 \end{lstlisting}
1411
1412 \subsection[Zadatak: Dve liste osoba sa istim sadržajem]{Zadatak: Dve
1413   liste osoba koje dele sadržaj, jedna sortirana po visini, druga po
1414   težini}
1415
1416 Sa tastature učitavati po dva broja koji opisuju osobu (visina i
1417 težina) i smeštati ih u povezane listu, tako da postoji neopadajuće
1418 uređenje i po visini i po težini.
1419
1420 \begin{lstlisting}[style=codeblock]
1421 MODULE VisTez;
1422 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1423 FROM IO IMPORT WrLn, WrStr, RdCard, WrCard;
1424 FROM SYSTEM IMPORT TSIZE;
1425 TYPE
1426   pok = POINTER TO element;
1427   element = RECORD
1428               visina, tezina : CARDINAL;
1429               Vveza, Tveza : pok
1430             END;
1431 VAR
1432   pocV, pocT : pok;
1433   vis, tez : CARDINAL;
1434 PROCEDURE Ispisi(pocV, pocT : pok);
1435 VAR
1436   tek : pok;
1437 BEGIN
1438   tek := pocV;
1439   WrStr('Po visini:');
1440   WrLn;
1441   WHILE tek # NIL DO
1442     WrCard(tek^.visina, 6);
1443     tek := tek^.Vveza
1444   END;
1445   WrLn;
1446   tek := pocT;
1447   WrStr('Po tezini:');
1448   WrLn;
1449   WHILE tek # NIL DO
1450     WrCard(tek^.tezina,6);
1451     tek := tek^.Tveza
1452   END
1453 END Ispisi;
1454
1455 PROCEDURE Ubaci(VAR pocV, pocT : pok;
1456                 vis, tez : CARDINAL);
1457 VAR
1458   novi, tek, iza : pok;
1459   nadjen : BOOLEAN;
1460 BEGIN
1461   IF pocV = NIL THEN
1462     ALLOCATE(pocV, TSIZE(element));
1463     pocV^.visina := vis;
1464     pocV^.tezina := tez;
1465     pocV^.Vveza := NIL;
1466     pocV^.Tveza := NIL;
1467     pocT := pocV
1468   ELSE
1469     ALLOCATE(novi, TSIZE(element));
1470     novi^.visina := vis;
1471     novi^.tezina := tez;
1472     tek := pocV;
1473     nadjen := FALSE;
1474     WHILE (tek # NIL) AND NOT nadjen DO
1475       nadjen := vis <= tek^.visina;
1476       IF NOT nadjen THEN
1477         iza := tek;
1478         tek := tek^.Vveza
1479       END
1480     END;
1481     novi^.Vveza := tek;
1482     IF tek = pocV THEN
1483       pocV := novi
1484     ELSE
1485       iza^.Vveza := novi
1486     END;
1487     tek := pocT;
1488     nadjen := FALSE;
1489     WHILE (tek # NIL) AND NOT nadjen DO
1490       nadjen := tez <= tek^.tezina;
1491       IF NOT nadjen THEN
1492         iza := tek;
1493         tek := tek^.Tveza
1494       END
1495     END;
1496     novi^.Tveza := tek;
1497     IF tek = pocT THEN
1498       pocT := novi
1499     ELSE
1500       iza^.Tveza := novi
1501     END
1502   END
1503 END Ubaci;
1504
1505 BEGIN
1506   pocV := NIL;
1507   pocT := NIL;
1508   WrStr('Unesite visinu ---- ');
1509   vis := RdCard();
1510   WHILE vis > 0 DO
1511     WrStr('Unesite tezinu ---- ');
1512     tez := RdCard();
1513     Ubaci(pocV, pocT, vis, tez);
1514     WrLn;
1515     WrStr('Unesite visinu ---- ');
1516     vis := RdCard()
1517   END;
1518   WrLn;
1519   Ispisi(pocV, pocT)
1520 END VisTez.
1521 \end{lstlisting}
1522
1523 \sectionbreak
1524 \section{Polinomi preko listi}
1525
1526 \subsection{Moduli}
1527
1528 Polinomi su predstavljeni pomoću pokazivača. Apstraktni tip podataka
1529 \kod{Polinom} je definisan u globalnom modulu. Redosled parametara kod
1530 svih procedura je takav da varijabilni parametri dolaze na kraju.
1531
1532 \paragraph{PolinomL.DEF} \
1533
1534 \lstinputlisting[style=codeblock]{kodovi/polinomi/POLINOML.DEF}
1535
1536 \paragraph{PolinomL.MOD} \
1537
1538 \lstinputlisting[style=codeblock]{kodovi/polinomi/POLINOML.MOD}
1539
1540 \subsection{Zadatak: Sabiranje sa unapred određenim polinomom}
1541
1542 Želimo da ispišemo uneti polinom uvećan za\\ $x^5 - 3x^4 + 4x + 7$.
1543
1544 \lstinputlisting[style=codeblock]{kodovi/polinomi/polinom.MOD}
1545
1546 \subsection{Zadatak: Suma k polinoma}
1547
1548 Napisati program koji ucitava broj k (1<=k<=50) i k polinoma, a nakon
1549 toga izracunava njihovu sumu
1550
1551 \lstinputlisting[style=codeblock]{kodovi/polinomi/PolSuma.MOD}
1552
1553 \sectionbreak
1554 \section{Stek i red opsluživanja}
1555
1556 \subsection{Primer: osnovno korišćenje steka i reda opsluživanja}
1557
1558 \lstinputlisting[style=codeblock]{kodovi/stek-redopsl/stekred.mod}
1559
1560 \subsection{Zadatak: Ilustracija pisanja u fajl uz pomoć bafera}
1561
1562 \begin{lstlisting}[style=codeblock]
1563 DEFINITION MODULE QueueInfo;
1564 CONST
1565   Maxqueue = 100;
1566 TYPE
1567   InfoTip = CHAR;
1568
1569 END QueueInfo.
1570
1571 IMPLEMENTATION MODULE QueueInfo;
1572 END QueueInfo.
1573
1574 DEFINITION MODULE RedOpsl1;
1575 FROM QueueInfo IMPORT InfoTip,Maxqueue;
1576 TYPE
1577   Niz = ARRAY[1..Maxqueue] OF InfoTip;
1578   RedOpslTip = RECORD
1579         Prvi, Zadnji : CARDINAL;
1580         Element : Niz
1581   END;
1582
1583 PROCEDURE MakeNull(VAR q : RedOpslTip);
1584 PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
1585 PROCEDURE First(VAR q : RedOpslTip;
1586                 VAR x : InfoTip;
1587                 VAR ok : BOOLEAN);
1588 PROCEDURE PopFirst(VAR q : RedOpslTip;
1589                    VAR ok : BOOLEAN);
1590 PROCEDURE AddRear(VAR q : RedOpslTip;
1591                   x : InfoTip;
1592                   VAR ok : BOOLEAN);
1593
1594 END RedOpsl1.
1595
1596 IMPLEMENTATION MODULE RedOpsl1;
1597 FROM QueueInfo IMPORT Maxqueue,InfoTip;
1598
1599 PROCEDURE MakeNull(VAR q : RedOpslTip);
1600 BEGIN
1601   WITH q DO
1602     Prvi := 0;
1603     Zadnji := 0
1604   END
1605 END MakeNull;
1606
1607 PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
1608 BEGIN
1609   RETURN q.Zadnji = 0
1610 END Empty;
1611
1612
1613 PROCEDURE First(VAR q : RedOpslTip;
1614                 VAR x : InfoTip;
1615                 VAR ok : BOOLEAN);
1616 BEGIN
1617   IF Empty(q) THEN
1618     ok := FALSE
1619   ELSE
1620     ok := TRUE;
1621     WITH q DO
1622       x := Element[Prvi]
1623     END
1624   END
1625 END First;
1626
1627 PROCEDURE AddOne(i : CARDINAL) : CARDINAL;
1628 BEGIN
1629   IF i = Maxqueue THEN
1630     RETURN 1
1631   ELSE
1632     RETURN i+1
1633   END
1634 END AddOne;
1635
1636 PROCEDURE PopFirst(VAR q : RedOpslTip;
1637                    VAR ok : BOOLEAN);
1638 BEGIN
1639   IF Empty(q) THEN
1640     ok := FALSE
1641   ELSE
1642     ok := TRUE;
1643     WITH q DO
1644       IF Prvi = Zadnji THEN
1645         MakeNull(q)
1646       ELSE
1647         Prvi := AddOne(Prvi)
1648       END
1649     END
1650   END
1651 END PopFirst;
1652
1653 PROCEDURE AddRear(VAR q : RedOpslTip;
1654                   x : InfoTip;
1655                   VAR ok : BOOLEAN);
1656 BEGIN
1657   WITH q DO
1658     IF AddOne(Zadnji) = Prvi THEN
1659       ok := FALSE
1660     ELSE
1661       ok := TRUE;
1662       IF Empty(q) THEN
1663         Prvi := 1;
1664         Zadnji := 1
1665       ELSE
1666         Zadnji := AddOne(Zadnji)
1667       END;
1668       Element[Zadnji] := x
1669     END
1670   END
1671 END AddRear;
1672
1673 END RedOpsl1.
1674
1675 MODULE Bafer;
1676 FROM RedOpsl1 IMPORT RedOpslTip, MakeNull, Empty, First, PopFirst, AddRear;
1677 FROM FIO IMPORT File,WrChar, Create, Close;
1678 IMPORT IO;
1679
1680 CONST
1681   ImeIzlaza = 'izlaz.txt';
1682
1683 VAR
1684   izlaz : File;
1685   znak : CHAR;
1686   buffer : RedOpslTip;
1687
1688 PROCEDURE IsprazniBafer(VAR dat : File;
1689                         VAR buf : RedOpslTip);
1690 VAR
1691   znak : CHAR;
1692   ok : BOOLEAN;
1693 BEGIN
1694   WHILE NOT Empty(buf) DO
1695     First(buf, znak, ok);
1696     PopFirst(buf, ok);
1697     WrChar(dat, znak)
1698   END
1699 END IsprazniBafer;
1700
1701 PROCEDURE BaferWrite(VAR dat : File;
1702                      VAR buf : RedOpslTip;
1703                      znak : CHAR);
1704 VAR
1705   ok : BOOLEAN;
1706 BEGIN
1707   AddRear(buf, znak, ok);
1708   IF NOT ok THEN
1709     IsprazniBafer(dat, buf);
1710     AddRear(buf, znak, ok)
1711   END
1712 END BaferWrite;
1713
1714 BEGIN
1715   izlaz := Create(ImeIzlaza);
1716   MakeNull(buffer);
1717   IO.WrStr('Unesite tekst, koji treba da se unese u datoteku ');
1718   IO.WrStr(ImeIzlaza);
1719   IO.WrChar('.');
1720   IO.WrLn;
1721   IO.WrStr('Unos zavrsite tackom.');
1722   IO.WrLn;
1723   znak := IO.RdChar();
1724   WHILE znak # '.' DO
1725     BaferWrite(izlaz, buffer, znak);
1726     znak := IO.RdChar();
1727   END;
1728   IsprazniBafer(izlaz, buffer);
1729   Close(izlaz)
1730 END Bafer.
1731 \end{lstlisting}
1732
1733 \subsection%
1734 {Zadatak: Ispitivanje da li reč pripada gramatici wcw$^+$}
1735
1736 Reč pripada ovoj gramatici ako joj se prvi deo (w) sastoji samo od
1737 slova 'a' i 'b', sledi slovo 'c' a nakon njega obrnuta reč reči w.
1738
1739 \begin{lstlisting}[style=codeblock]
1740 DEFINITION MODULE Stek;
1741 CONST
1742   Maxstack = 100;
1743 TYPE
1744   Niz = ARRAY [1..Maxstack] OF CHAR;
1745   StekTip = RECORD
1746             Top : CARDINAL;
1747             Element : Niz
1748           END;
1749 PROCEDURE MakeNull(VAR s : StekTip);
1750 PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
1751
1752 PROCEDURE Top(VAR s : StekTip;
1753               VAR x : CHAR;
1754               VAR ok : BOOLEAN);
1755 PROCEDURE Pop(VAR s : StekTip;
1756               VAR ok : BOOLEAN);
1757 PROCEDURE Push(VAR s : StekTip;
1758                x : CHAR;
1759                VAR ok : BOOLEAN);
1760 END Stek.
1761
1762
1763 IMPLEMENTATION MODULE Stek;
1764
1765 PROCEDURE MakeNull(VAR s : StekTip);
1766 BEGIN
1767   s.Top := 0
1768 END MakeNull;
1769
1770 PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
1771 BEGIN
1772   RETURN s.Top = 0
1773 END Empty;
1774
1775 PROCEDURE Top(VAR s : StekTip;
1776               VAR x : CHAR;
1777               VAR ok : BOOLEAN);
1778 BEGIN
1779   IF Empty(s) THEN
1780     ok := FALSE
1781   ELSE
1782     ok := TRUE;
1783     WITH s DO
1784       x := Element[Top]
1785     END
1786   END
1787 END Top;
1788 \end{lstlisting}
1789
1790 \begin{codeblock}
1791 PROCEDURE Pop(VAR s : StekTip;
1792               VAR ok : BOOLEAN);
1793 BEGIN
1794   IF Empty(s) THEN
1795     ok := FALSE
1796   ELSE
1797     ok := TRUE;
1798     DEC(s.Top)
1799   END
1800 END Pop;
1801
1802 PROCEDURE Push(VAR s : StekTip;
1803                x : CHAR;
1804                VAR ok : BOOLEAN);
1805 BEGIN
1806   WITH s DO
1807     IF Top = Maxstack THEN
1808       ok := FALSE
1809     ELSE
1810       ok := TRUE;
1811       INC(Top);
1812       Element[Top] := x
1813     END
1814   END
1815 END Push;
1816 END Stek.
1817
1818 MODULE wcw;
1819 (* Da li rec pripada gramatici wcw+. *)
1820 FROM Stek IMPORT StekTip, MakeNull, Empty,
1821                  Top, Pop, Push;
1822 FROM InOut IMPORT Read, Write, WriteString, EOL;
1823 TYPE
1824   slova = SET OF CHAR;
1825 VAR
1826   S : StekTip;
1827   Ch, C : CHAR;
1828   ok : BOOLEAN;
1829 BEGIN
1830   MakeNull(S);
1831   Read(Ch);
1832   ok := TRUE;
1833   WHILE ok AND (Ch IN slova{'a', 'b'}) DO
1834     Push(S, Ch, ok);
1835     Read(Ch);
1836   END;
1837   IF NOT ok THEN
1838     WriteString('Greska - mali stek')
1839   ELSIF Ch # 'c' THEN
1840     WriteString('Pogresan string')
1841   ELSE
1842     Read(Ch);
1843     WHILE ok AND (Ch # EOL) DO
1844       Top(S, C, ok);
1845       ok := ok AND (C = Ch);
1846       IF ok THEN
1847         Pop(S, ok);
1848         Read(Ch);
1849       END
1850     END;
1851     IF NOT (ok AND Empty(S)) THEN
1852       WriteString('Pogresan string')
1853     ELSE
1854       WriteString('String pripada jeziku L')
1855     END
1856   END
1857 END wcw.
1858 \end{codeblock}
1859
1860 \manbreakJK
1861
1862 \subsection{Zadatak: Kalkulator za izračunavanje postfiksnih izraza}
1863
1864
1865 Napraviti kalkulator za izračunavanje postfiksnih izraza. Svi brojevi
1866 koji figurišu u izrazu su jednocifreni.
1867
1868 \begin{lstlisting}[style=codeblock]
1869 MODULE PostFix;
1870
1871 FROM StekI IMPORT StekTip, MakeNull, Empty, Top, Pop, Push;
1872 FROM InOut IMPORT Read, Write, WriteInt, EOL;
1873 TYPE
1874   slova = SET OF CHAR;
1875 VAR
1876   S : StekTip;
1877   Ch : CHAR;
1878   Op1, Op2 : INTEGER;
1879   ok : BOOLEAN;
1880 PROCEDURE Conv(Ch : CHAR) : INTEGER;
1881 BEGIN
1882   RETURN  ORD(Ch) - ORD('0')
1883 END Conv;
1884
1885 BEGIN
1886   MakeNull(S);
1887   Read(Ch);
1888   WHILE Ch # EOL DO
1889     IF Ch IN slova{'+', '-', '/', '*', '%'} THEN
1890       Top(S, Op2, ok);
1891       Pop(S, ok);
1892       Top(S, Op1, ok);
1893       Pop(S, ok);
1894       CASE Ch OF
1895         '+' : Op1 := Op1 + Op2 |
1896         '-' : Op1 := Op1 - Op2 |
1897         '*' : Op1 := Op1 * Op2 |
1898         '/' : Op1 := Op1 DIV Op2 |
1899         '%' : Op1 := Op1 MOD Op2
1900       END;
1901       Push(S, Op1, ok)
1902     ELSE
1903       Push(S, Conv(Ch), ok)
1904     END;
1905     Read(Ch);
1906   END;
1907   Top(S, Op1, ok);
1908   Write('=');
1909   WriteInt(Op1,5)
1910 END PostFix.
1911 \end{lstlisting}
1912
1913 \sectionbreak
1914 \section{Simulacija rekurzije}
1915
1916
1917 Na početku označiti sve rekurzivne pozive u originalnoj proceduri
1918 adresama (npr. 1,2,3... ili konstante nabrojivog tipa podataka).
1919
1920 Na steku se čuvaju lokalne promenljive, parametri procedure i adresa
1921 mesta poziva, a u skladu sa tim se kreira InfoTip.
1922
1923 Trivijalnim pozivom se smatra onaj koji se izračunava bez dodatnih
1924 rekurzivnih poziva.
1925
1926 U kodu ispod, \kod{treba\_rekurzija} znači da je poziv netrivijalan,
1927 odnosno treba naći uslove pod kojima se sigurno dešavaju rekurzivni
1928 pozivi.
1929
1930 \begin{lstlisting}
1931 MakeNull(S);
1932 REPEAT
1933   WHILE treba_rekurzija DO
1934     -prepisati sve od pocetka originalne
1935      procedure do prvog rekurzivnog poziva
1936     -staviti na stek potrebne
1937      lokalne promenljive, parametre procedure i
1938      adresu mesta poziva
1939     -podesiti vrednosti parametara da budu
1940      kao u rekurzivnom pozivu procedure
1941   END;
1942   trivijalan poziv
1943   umesto RETURN x pisati rez := x
1944   jos := TRUE;
1945   WHILE jos AND NOT Empty(S) DO
1946     Top(S, el, ok);
1947     Pop(S, ok);
1948     -restauriramo vrednosti sa steka
1949     -u zavisnosti od adrese poziva nastavimo
1950      prepisivanje originalne procedure sa
1951      tog mesta
1952     -ako se dodje do novog rek. poziva tada:
1953        -sacuvati na steku vrednosti
1954        -podesiti vrednosti parametara da budu
1955         kao u rekurzivnom pozivu procedure
1956        -ici na pocetak koda
1957         (ovo se postize sa jos := FALSE)
1958     -inace
1959        ako se naidje na RETURN x pisati rez := x
1960   END
1961 UNTIL Empty(S);
1962 \end{lstlisting}
1963
1964 Ako je procedura funkcijska tada se na kraj dodaje \kod{RETURN rez}.
1965
1966 \subsection*{ZADACI}
1967
1968 Simulirati ponašanje sledećih rekurzivnih procedura (funkcija) upotrebom steka:
1969
1970 \subsection{Primer 1 -- faktorijel}
1971
1972
1973 \begin{lstlisting}[style=codeblock]
1974 MODULE Fakto;
1975 (* InfoTip = CARDINAL; *)
1976
1977 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
1978 FROM StekC IMPORT StekTip, MakeNull, Empty,
1979                   Top, Pop, Push;
1980 VAR
1981   n : CARDINAL;
1982 PROCEDURE RFakto(n : CARDINAL) : CARDINAL;
1983 BEGIN
1984   IF n <= 1 THEN
1985     RETURN 1
1986   ELSE
1987     RETURN n * RFakto(n-1)
1988   END
1989 END RFakto;
1990
1991
1992 PROCEDURE SFakto(n : CARDINAL) : CARDINAL;
1993 VAR
1994   s : StekTip;
1995   rez : CARDINAL;
1996   OK : BOOLEAN;
1997 BEGIN
1998   MakeNull(s);
1999   WHILE n > 1 DO
2000     Push(s,n,OK);
2001     DEC(n)
2002   END;
2003   rez := 1;
2004   WHILE NOT Empty(s) DO
2005     Top(s, n, OK);
2006     Pop(s, OK);
2007     rez := n * rez
2008   END;
2009   RETURN rez
2010 END SFakto;
2011
2012 BEGIN
2013   WrStr('n = ');
2014   n := RdCard();
2015   WrLn
2016   WrStr('n! = ');
2017   WrCard(RFakto(n), 1);
2018   WrStr(' = ');
2019   WrCard(SFakto(n), 1)
2020 END Fakto.
2021 \end{lstlisting}
2022
2023 \subsection{Primer 2 -- stepenovanje}
2024
2025 \begin{lstlisting}[style=codeblock]
2026 MODULE Step;
2027 (* InfoTip = RECORD
2028                 x : REAL;
2029                 n : CARDINAL;
2030                 adr : (par, nepar)
2031              END;
2032 *)
2033 FROM IO IMPORT WrStr, WrLn, WrReal,
2034         RdReal, RdCard;
2035 FROM StekStep IMPORT StekTip, MakeNull, Empty,
2036              Top, Pop, Push, InfoTip, AdrTip;
2037 VAR
2038   n : CARDINAL;
2039   x : REAL;
2040
2041 PROCEDURE Sqr(y : REAL) : REAL;
2042 BEGIN
2043   RETURN y * y
2044 END Sqr;
2045
2046 PROCEDURE RStep(x : REAL;
2047                 n : CARDINAL) : REAL;
2048 BEGIN
2049   IF n = 0 THEN
2050     RETURN 1.
2051   ELSIF ODD(n) THEN
2052     RETURN x * Sqr( RStep(x, n DIV 2) )
2053   ELSE
2054     RETURN Sqr( RStep(x, n DIV 2) )
2055   END
2056 END RStep;
2057
2058 PROCEDURE SStep(x : REAL;
2059                 n : CARDINAL ) : REAL;
2060 VAR
2061   s : StekTip;
2062   OK : BOOLEAN;
2063   rez : REAL;
2064   el : InfoTip;
2065 BEGIN
2066   MakeNull(s);
2067   WHILE n > 0 DO
2068     el.x := x;
2069     el.n := n;
2070     IF ODD(n) THEN
2071       el.adr := nepar;
2072     ELSE
2073       el.adr := par
2074     END;
2075     Push(s,el,OK);
2076     n := n DIV 2
2077   END;
2078   rez := 1.;
2079   WHILE NOT Empty(s) DO
2080     Top(s, el, OK);
2081     Pop(s, OK);
2082     x := el.x;
2083     n := el.n;
2084     IF el.adr = nepar THEN
2085       rez := x * Sqr(rez)
2086     ELSE
2087       rez := Sqr(rez)
2088     END
2089   END;
2090   RETURN rez
2091 END SStep;
2092
2093 BEGIN
2094   WrStr('x =? ');
2095   x := RdReal();
2096   WrLn;
2097   WrStr('n =? ');
2098   n := RdCard();
2099   WrStr('x^n = ');
2100   WrReal(RStep(x, n), 10, 1);
2101   WrStr(' = ');
2102   WrReal(SStep(x, n), 10, 1)
2103 END Step.
2104 \end{lstlisting}
2105
2106 \subsection{Primer 3 -- Fibonači}
2107
2108 \begin{lstlisting}[style=codeblock]
2109 MODULE Fib;
2110 (* InfoTip = RECORD
2111                 n : CARDINAL;
2112                 PrviSab : CARDINAL;
2113                 adr : (prvi, drugi)
2114              END;
2115 *)
2116
2117 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2118 FROM StekFib IMPORT StekTip, MakeNull, Empty,
2119        Top, Pop, Push, InfoTip, AdrTip;
2120 VAR
2121   n : CARDINAL;
2122
2123 PROCEDURE RFib(n : CARDINAL) : CARDINAL;
2124 BEGIN
2125   IF n <= 1 THEN
2126     RETURN n
2127   ELSE
2128     RETURN RFib(n-1) + RFib(n-2)
2129   END
2130 END RFib;
2131
2132 PROCEDURE SFib(n : CARDINAL ) : CARDINAL;
2133 VAR
2134   s : StekTip;
2135   OK, jos : BOOLEAN;
2136   rez, PrviSab : CARDINAL;
2137   el : InfoTip;
2138 BEGIN
2139   MakeNull(s);
2140   REPEAT
2141     WHILE n > 1 DO
2142       el.n := n;
2143       el.adr := prvi;
2144       Push(s,el,OK);
2145       DEC(n)
2146     END;
2147     rez := (n);
2148     jos := TRUE;
2149     WHILE (NOT Empty(s)) AND jos DO
2150       Top(s, el, OK);
2151       Pop(s, OK);
2152       n := el.n;
2153       IF el.adr = prvi THEN
2154         PrviSab := rez;
2155         el.n := n;
2156         el.adr := drugi;
2157         el.PrviSab := PrviSab;
2158         Push(s, el, OK);
2159         DEC(n, 2);
2160         jos := FALSE
2161       ELSE
2162         PrviSab := el.PrviSab;
2163         rez := PrviSab + rez
2164       END
2165     END
2166   UNTIL Empty(s);
2167   RETURN rez
2168 END SFib;
2169
2170 BEGIN
2171   WrStr('n =? ');
2172   n := RdCard();
2173   WrStr('F(n) = ');
2174   WrCard(RFib(n), 1);
2175   WrStr(' = ');
2176   WrCard(SFib(n), 1)
2177 END Fib.
2178 \end{lstlisting}
2179
2180 \subsection{Primer 4 -- faktorijel 2}
2181
2182
2183 \begin{lstlisting}[style=codeblock]
2184 MODULE Faktor;
2185 (* InfoTip = CARDINAL; *)
2186 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2187 FROM StekC IMPORT StekTip, MakeNull, Empty,
2188                   Top, Pop, Push;
2189 VAR
2190   n,rez : CARDINAL;
2191
2192 PROCEDURE RFakto(n : CARDINAL;
2193                  VAR rez : CARDINAL);
2194 BEGIN
2195   IF n = 0 THEN
2196     rez := 1
2197   ELSE
2198     RFakto(n-1, rez);
2199     rez := n * rez
2200   END
2201 END RFakto;
2202
2203 PROCEDURE SFakto(n : CARDINAL;
2204                  VAR rez : CARDINAL);
2205 VAR
2206   s : StekTip;
2207   OK : BOOLEAN;
2208 BEGIN
2209   MakeNull(s);
2210   WHILE n > 0 DO
2211     Push(s,n,OK);
2212     DEC(n)
2213   END;
2214   rez := 1;
2215   WHILE NOT Empty(s) DO
2216     Top(s, n, OK);
2217     Pop(s, OK);
2218     rez := n * rez
2219   END
2220 END SFakto;
2221
2222 BEGIN
2223   WrStr('n =? ');
2224   n := RdCard();
2225   WrLn;
2226   WrStr('n! = ');
2227   RFakto(n, rez);
2228   WrCard(rez, 1);
2229   WrStr(' = ');
2230   SFakto(n, rez);
2231   WrCard(rez, 1)
2232 END Faktor.
2233 \end{lstlisting}
2234
2235 \subsection{Primer 5 (ispitni)}
2236
2237
2238 \begin{lstlisting}[style=codeblock]
2239 MODULE Rek1;
2240 (* InfoTip = RECORD
2241                 d, g, m1, m2 : INTEGER;
2242                 adr : (prvi, drugi)
2243              END;
2244 *)
2245 FROM Stek1 IMPORT StekTip, adresa, InfoTip,
2246          MakeNull, Empty, Top, Pop, Push;
2247 IMPORT IO;
2248 VAR
2249   X : ARRAY [1..20] OF INTEGER;
2250
2251 PROCEDURE Max(d, g: INTEGER) : INTEGER;
2252 VAR
2253   m1, m2 : INTEGER;
2254 BEGIN
2255   IF d>g THEN
2256     RETURN MIN(INTEGER)
2257   ELSIF d=g THEN
2258     RETURN X[d]
2259   ELSE
2260     m1 := Max(d, (d+g) DIV 2);
2261     m2 := Max((d+g) DIV 2 +1, g);
2262     IF m1 > m2 THEN
2263       RETURN m1
2264     ELSE
2265       RETURN m2
2266     END
2267   END
2268 END Max;
2269
2270 PROCEDURE SMax(d, g: INTEGER) : INTEGER;
2271 VAR
2272   S : StekTip;
2273   el : InfoTip;
2274   ok, jos : BOOLEAN;
2275   m1, m2, rez : INTEGER;
2276 BEGIN
2277   MakeNull(S);
2278   REPEAT
2279     WHILE d<g DO
2280       el.d := d;
2281       el.g := g;
2282       el.adr := prvi;
2283       Push(S, el, ok);
2284       g := (d+g) DIV 2
2285     END;
2286     IF d>g THEN
2287       rez := MIN(INTEGER)
2288     ELSE (* d=g *)
2289       rez := X[d]
2290     END;
2291     jos := TRUE;
2292     WHILE jos AND NOT Empty(S) DO
2293       Top(S, el, ok);
2294       Pop(S, ok);
2295       d := el.d;
2296       g := el.g;
2297       m1 := el.m1;
2298       IF el.adr = prvi THEN
2299         m1 := rez;
2300         el.m1 := m1;
2301         el.adr := drugi;
2302         Push(S, el, ok);
2303         d := (d+g) DIV 2 + 1;
2304         jos := FALSE
2305       ELSE (*el.adr = drugi*)
2306         m2 := rez;
2307         IF m1 > m2 THEN
2308           rez := m1
2309         ELSE
2310           rez := m2
2311         END
2312       END
2313     END
2314   UNTIL Empty(S);
2315   RETURN rez
2316 END SMax;
2317
2318 BEGIN (* glavni program *)
2319   X[1] := 3;
2320   X[2] := 2;
2321   X[3] := 5;
2322   X[4] := -7;
2323   X[5] := 0;
2324   IO.WrCard(Max(1, 5), 3);
2325   IO.WrLn;
2326   IO.WrCard(SMax(1, 5), 3);
2327   IO.WrLn
2328 END Rek1.
2329 \end{lstlisting}
2330
2331 \subsection{Primer 6 (ispitni)}
2332
2333
2334 \begin{lstlisting}[style=codeblock]
2335 MODULE Rek2;
2336 (* InfoTip = RECORD
2337                 x, y, n : CARDINAL;
2338                 adr : (prvi, drugi, treci, cetvrti)
2339              END;
2340 *)
2341 FROM Stek2 IMPORT StekTip, adresa, InfoTip,
2342            MakeNull, Empty, Top, Pop, Push;
2343 IMPORT IO;
2344
2345 PROCEDURE g(x : CARDINAL; y : CARDINAL;
2346             n : CARDINAL) : CARDINAL;
2347 BEGIN
2348   IF n < 3 THEN
2349     RETURN x + y
2350   ELSIF ODD(n) THEN
2351     RETURN g(g(x+1, y, n-2), y, n-3)
2352   ELSE
2353     RETURN g(x, g(x, y+1, n-2), n-3)
2354   END
2355 END g;
2356
2357 PROCEDURE Sg(x : CARDINAL; y : CARDINAL;
2358              n : CARDINAL) : CARDINAL;
2359 VAR
2360   S : StekTip;
2361   el : InfoTip;
2362   ok, jos : BOOLEAN;
2363   rez : CARDINAL;
2364 BEGIN
2365   MakeNull(S);
2366   REPEAT
2367     WHILE n >= 3 DO
2368       IF ODD(n) THEN
2369         el.x := x;
2370         el.y := y;
2371         el.n := n;
2372         el.adr := prvi;
2373         Push(S, el, ok);
2374         INC(x);
2375         DEC(n, 2)
2376       ELSE
2377         el.x := x;
2378         el.y := y;
2379         el.n := n;
2380         el.adr := treci;
2381         Push(S, el, ok);
2382         INC(y);
2383         DEC(n, 2)
2384       END
2385     END;
2386     rez := x+y;
2387     jos := TRUE;
2388     WHILE jos AND NOT Empty(S) DO
2389       Top(S, el, ok);
2390       Pop(S, ok);
2391       x := el.x;
2392       y := el.y;
2393       n := el.n;
2394       IF el.adr = prvi THEN
2395         el.adr := drugi;
2396         Push(S, el, ok);
2397         x := rez;
2398         DEC(n, 3);
2399         jos := FALSE
2400       ELSIF el.adr = treci THEN
2401         el.adr := cetvrti;
2402         Push(S, el, ok);
2403         y := rez;
2404         DEC(n, 3);
2405         jos := FALSE
2406       END
2407     END
2408   UNTIL Empty(S);
2409   RETURN rez
2410 END Sg;
2411
2412 BEGIN (* glavni program *)
2413   IO.WrCard(g(2, 3, 10), 3);
2414   IO.WrCard(Sg(2, 3, 10), 3);
2415 END Rek2.
2416 \end{lstlisting}
2417
2418 %\columnbreak
2419
2420 \appendix
2421
2422 \sectionbreak
2423 \pagenumbering{Roman}
2424 \input{xds-uputstvo}
2425
2426 \mainend
2427
2428
2429
2430 %%% Local Variables:
2431 %%% mode: latex
2432 %%% TeX-master: "skripta-spa1-jk"
2433 %%% End: