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