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}{April 2014, Novi Sad}
  13 \newcommand{\verzija}{ver 14c-\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:INTEGER);
 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 Kod svih procedura se mogu primeniti i rekurzivne varijante. Sledi
 903 primer za kreiranje sortirane liste.
 904
 905 \begin{codeblock}
 906 PROCEDURE DodajSortRek(VAR lista:brojevi; br:INTEGER);
 907 (* Koristi se cinjenica da prosledjujemo pokazivac
 908 po referenci, tj. da ga mozemo menjati unutar procedure *)
 909 VAR
 910   temp : brojevi;
 911 BEGIN
 912   IF (lista = NIL) OR (lista^.info>=br) THEN
 913     (* Izlaz iz rekurzije. Ubacivanje u praznu listu,
 914     na kraj liste ili na odgovarajuce mesto *)
 915     NEW(temp);
 916     temp^.info:=br;
 917     temp^.veza:=lista;
 918     lista:=temp;
 919   ELSE
 920     DodajSortRek(lista^.veza, br);
 921   END;
 922 END DodajSortRek;
 923 \end{codeblock}
 924
 925 \manbreakJK
 926
 927 \subsection{Zadatak: Prikaz osnovih operacija nad listama}
 928
 929 \begin{lstlisting}[style=codeblock]
 930 MODULE liste2;
 931 FROM InOut IMPORT WriteString, WriteLn,
 932            WriteCard, ReadCard;
 933 FROM IO IMPORT RdKey;
 934 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
 935 TYPE
 936   skupZn = SET OF CHAR;
 937   brojevi = POINTER TO brojSlog;
 938   brojSlog = RECORD
 939       info:CARDINAL;
 940       veza:brojevi;
 941   END;
 942 VAR
 943   lista : brojevi;
 944   menu,prazno:CHAR;
 945
 946 PROCEDURE DodajPoc(VAR lista:brojevi; br:INTEGER);
 947 (* dodaje broj pom na pocetak liste *)
 948 VAR
 949   temp:brojevi;
 950 BEGIN
 951   (* kreiramo novi element *)
 952   NEW(temp);
 953   temp^.info := br;
 954   (* treba da pokazuje na ostatak liste *)
 955   temp^.veza := lista;
 956   (* pocetak liste je novi element *)
 957   lista := temp;
 958 END DodajPoc;
 959
 960 PROCEDURE Unos(VAR lista:brojevi);
 961 (* dodaje n brojeva u listu *)
 962 VAR
 963   n,i,br:CARDINAL;
 964 BEGIN
 965   WriteString('unesite n (broj brojeva): ');
 966   ReadCard(n);
 967   FOR i:= 1 TO n DO
 968       WriteString("unesite broj ");
 969       WriteCard(i,0);
 970       WriteString(": ");
 971       ReadCard(br);
 972       DodajPoc(lista,br);
 973   END;
 974 END Unos;
 975
 976 (* -- procedure za stampu -- *)
 977
 978 PROCEDURE Stampaj(lista:brojevi);
 979 (* stampa sadrzaj liste na ekran *)
 980 VAR
 981   temp:brojevi;
 982 BEGIN
 983   WriteLn;
 984   WriteString("Sadrzaj liste:");
 985   WriteLn;
 986   temp:=lista;
 987   WHILE temp # NIL DO
 988       WriteCard(temp^.info,0);
 989       WriteLn;
 990       temp := temp^.veza;
 991   END;
 992 END Stampaj;
 993
 994 PROCEDURE StampajK(VAR lista:brojevi);
 995 (* stampa k-ti element (k unosi korisnik) *)
 996 VAR
 997   temp:brojevi;
 998   k,brojac:CARDINAL;
 999 BEGIN
1000   WriteString("unesite redni broj elementa:");
1001   ReadCard(k);
1002   temp:=lista;
1003   brojac := 1;
1004   WHILE (temp# NIL) AND (k>brojac) DO
1005     temp:=temp^.veza;
1006     INC(brojac);
1007   END;
1008   IF (temp#NIL) THEN
1009     WriteCard(temp^.info,2);
1010   ELSE
1011     WriteString("greska! - ne postoji element");
1012     WriteString(" u listi sa rednim brojem ");
1013     WriteCard(k,2);
1014   END;
1015   WriteLn();
1016 END StampajK;
1017
1018 PROCEDURE StampajMinimum(VAR lista:brojevi);
1019 (* nalazi i stampa minimalni element liste *)
1020 VAR
1021   temp:brojevi;
1022   min:CARDINAL;
1023 BEGIN
1024   IF (lista=NIL) THEN
1025     WriteString("prazna lista!");
1026   ELSE
1027     min:=lista^.info;
1028     temp:=lista^.veza;
1029     WHILE temp # NIL DO
1030       IF temp^.info < min THEN
1031         min := temp^.info;
1032       END;
1033       temp := temp^.veza;
1034     END;
1035     WriteString("Minimalni element liste je ");
1036     WriteCard(min,0);
1037   END;
1038   WriteLn;
1039 END StampajMinimum;
1040
1041 (* -- pomocne procedure, bez ispisa  -- *)
1042
1043 PROCEDURE UListi(lista:brojevi;
1044                  br: CARDINAL):BOOLEAN;
1045 (* vraca da li se 'br' nalazi u listi 'lista' *)
1046 VAR
1047   temp:brojevi;
1048 BEGIN
1049   temp:=lista;
1050   WHILE (temp # NIL) AND (temp^.info # br) DO
1051     (* dok ne dodjemo do kraja liste
1052        ili ne nadjemo broj *)
1053       temp := temp^.veza;
1054   END;
1055   IF temp#NIL THEN
1056     (* znaci da nismo na kraju liste,
1057        tj da je nadjen broj *)
1058     RETURN TRUE;
1059   ELSE (* temp = NIL *)
1060     RETURN FALSE;
1061   END;
1062 END UListi;
1063
1064 PROCEDURE IzbaciIzListe(VAR lista:brojevi;
1065                         br: CARDINAL):BOOLEAN;
1066 (* izbacuje broj 'br' iz liste, naravno ako
1067    postoji i vraca da li je operacija uspesno
1068    obavljena *)
1069 VAR
1070   temp,prethodni:brojevi;
1071 BEGIN
1072   (* proverimo da li je prvi element *)
1073   IF (lista # NIL) AND (lista^.info = br) THEN
1074     temp:=lista;
1075     lista :=lista^.veza;
1076     DISPOSE(temp);
1077     RETURN TRUE;
1078   ELSE
1079   (* trazimo u ostatku liste *)
1080     temp:=lista;
1081     prethodni:=NIL;
1082     WHILE (temp # NIL) AND (temp^.info # br) DO
1083         (* dok ne dodjemo do kraja liste
1084            ili ne nadjemo broj *)
1085         prethodni:=temp;
1086         temp := temp^.veza;
1087     END;
1088     IF temp#NIL THEN
1089       (* znaci da nismo na kraju liste,
1090          odnosno da smo nasli broj *)
1091       (* prevezemo listu oko elementa *)
1092       prethodni^.veza:=temp^.veza;
1093       DISPOSE(temp);
1094       RETURN TRUE;
1095     ELSE
1096       RETURN FALSE;
1097     END;
1098   END;
1099 END IzbaciIzListe;
1100
1101 PROCEDURE IzbaciIzListeSve(VAR lista:brojevi;
1102                         br: CARDINAL):CARDINAL;
1103 (* izbacuje sve brojeve 'br' iz liste, naravno ako
1104    postoje i vraca koliko ih je bilo *)
1105 VAR
1106   temp,prethodni:brojevi;
1107   brojac : CARDINAL;
1108 BEGIN
1109   brojac := 0;
1110   (* uklanjamo sa pocetka koliko je potrebno *)
1111   WHILE (lista # NIL) AND (lista^.info = br) DO
1112     temp:=lista;
1113     lista :=lista^.veza;
1114     DISPOSE(temp);
1115     INC(brojac);
1116   END;
1117   (* trazimo u ostatku liste *)
1118   IF (lista # NIL) THEN
1119     temp:=lista;
1120     WHILE (temp^.veza # NIL)  DO
1121         (* idemo do poslednjeg elementa liste *)
1122         prethodni:=temp;
1123         temp := temp^.veza;
1124         IF temp^.info = br THEN
1125           (* prevezemo listu oko elementa *)
1126           prethodni^.veza:=temp^.veza;
1127           DISPOSE(temp);
1128           INC(brojac);
1129           (* vracamo se jedan korak da bi
1130           u novom krugu proverili i ovaj element *)
1131           temp := prethodni;
1132         END;
1133     END;
1134   END;
1135   RETURN brojac;
1136 END IzbaciIzListeSve;
1137
1138 (* - procedure sa interakcijom sa korisnikom - *)
1139
1140 PROCEDURE IzbacivanjeEl(VAR lista:brojevi);
1141 (* izbacuje uneti broj iz liste koristeci proceduru IzbaciIzListe *)
1142 VAR
1143   br:CARDINAL;
1144 BEGIN
1145   WriteString("unesite broj za izbacivanje: ");
1146   ReadCard(br);
1147   IF IzbaciIzListe(lista,br) THEN
1148     WriteString("broj je izbacen iz liste");
1149   ELSE
1150     WriteString("greska! - broj ne postoji");
1151   END;
1152   WriteLn;
1153 END IzbacivanjeEl;
1154
1155 PROCEDURE IzbacivanjeElSvi(VAR lista:brojevi);
1156 (* izbacuje sve primeke unetog broj iz liste
1157    koristeci proceduru IzbaciIzListeSve *)
1158 VAR
1159   br, ukupno:CARDINAL;
1160 BEGIN
1161   WriteString("unesite broj za izbacivanje: ");
1162   ReadCard(br);
1163   ukupno := IzbaciIzListeSve(lista,br);
1164   WriteString("Iz liste je izbaceno ");
1165   WriteCard(ukupno,3);
1166   WriteString(" el.");
1167   WriteLn;
1168 END IzbacivanjeElSvi;
1169
1170 PROCEDURE IzbacivanjeK(VAR lista:brojevi);
1171 (* izbacuje k-ti element iz liste *)
1172 VAR
1173   temp,tekuci:brojevi;
1174   k,brojac:CARDINAL;
1175 BEGIN
1176   IF lista=NIL THEN
1177     WriteString("lista je prazna, nema ");
1178     WriteString("elemenata za izbacivanje");
1179   ELSE
1180     WriteString("unesite redni broj elementa");
1181     WriteString(" koji zelite izbaciti:");
1182     ReadCard(k);
1183     IF k=1 THEN (*izbacivanje prvog *)
1184       temp:=lista;
1185       lista := lista^.veza;
1186       DISPOSE(temp);
1187     ELSE
1188       tekuci := lista;
1189       brojac := 2; (*gledamo jedan unapred*)
1190       WHILE (tekuci^.veza# NIL) AND (k>brojac) DO
1191         (* idemo kroz listu do k-tog el *)
1192         tekuci:=tekuci^.veza;
1193         INC(brojac);
1194       END;
1195       IF (tekuci^.veza#NIL) THEN
1196          (* pamtimo element za brisanje *)
1197          temp:=tekuci^.veza;
1198          (* prevezujemo listu oko njega*)
1199          tekuci^.veza:=tekuci^.veza^.veza;
1200          DISPOSE(temp);
1201       ELSE
1202         WriteString("greska! - ne postoji el ");
1203         WriteString("u listi sa rednim brojem ");
1204         WriteCard(k,2);
1205       END;
1206       WriteLn();
1207     END;
1208   END;
1209 END IzbacivanjeK;
1210
1211 PROCEDURE Pretraga(lista:brojevi);
1212 (* provera da li se uneti broj nalazi u listi *)
1213 VAR
1214   br:CARDINAL;
1215 BEGIN
1216   WriteString("unesite trazeni broj");
1217   ReadCard(br);
1218   IF UListi(lista,br) THEN
1219     WriteString("broj postoji u listi");
1220   ELSE
1221     WriteString("broj ne postoji u listi");
1222   END;
1223   WriteLn;
1224 END Pretraga;
1225
1226 (* -- oslobadjanje memorije -- *)
1227
1228 PROCEDURE Unisti(VAR lista:brojevi);
1229 VAR
1230   temp:brojevi;
1231 BEGIN
1232   temp:=lista;
1233   WHILE temp # NIL DO
1234         lista:=lista^.veza;
1235         DISPOSE(temp);
1236         temp:=lista;
1237   END;
1238 END Unisti;
1239
1240 BEGIN
1241   (* pocinjemo od prazne liste *)
1242   lista := NIL;
1243   REPEAT
1244      WriteLn;
1245      WriteString("Ilustracija rada sa");
1246      WriteString(" listama brojeva");
1247      WriteLn;
1248      WriteString("=============================");
1249      WriteLn;
1250      WriteString("s - Stampa");WriteLn;
1251      WriteString("u - Unos");WriteLn;
1252      WriteString("i - Izbacivanje br iz liste");
1253      WriteLn;
1254      WriteString("v - izbacivanje svih br iz liste");
1255      WriteLn;
1256      WriteString("e - izbacivanje k-tog El.");
1257      WriteLn;
1258      WriteString("k - stampanje k-tog elementa");
1259      WriteLn;
1260      WriteString("m - Minimalni broj u listi");
1261      WriteLn;
1262      WriteString("p - Pretraga el. u listi");
1263      WriteLn;
1264      WriteLn;
1265      WriteString("q - kraj rada (Quit)");WriteLn;
1266       REPEAT
1267         menu := CAP(RdKey());
1268       UNTIL menu IN skupZn{'S','U','E','I','V',
1269                            'M','K','P','Q'};
1270       IF menu#'Q' THEN
1271         CASE menu OF
1272          'S' : Stampaj(lista);|
1273          'U' : Unos(lista);|
1274          'I' : IzbacivanjeEl(lista);|
1275          'V' : IzbacivanjeElSvi(lista);|
1276          'E' : IzbacivanjeK(lista);|
1277          'K' : StampajK(lista); |
1278          'M' : StampajMinimum(lista); |
1279          'P' : Pretraga(lista);|
1280         END;
1281         WriteLn;
1282         WriteString("--- pritisnite bilo koji ");
1283         WriteString("taster za povratak u meni");
1284         prazno:=RdKey();
1285       ELSE
1286         WriteString("Kraj rada")
1287       END;
1288       WriteLn;
1289   UNTIL menu='Q';
1290   Unisti(lista);
1291 END liste2.
1292 \end{lstlisting}
1293
1294
1295 \subsection{Zadatak: Prikaz operacija nad listama sa jedinstvenim ključem}
1296
1297 \begin{lstlisting}[style=codeblock]
1298 MODULE Radnici;
1299
1300 FROM InOut IMPORT WriteString, ReadString,
1301            WriteLn, WriteCard, ReadCard, Done;
1302 FROM IO IMPORT RdKey;
1303 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1304
1305 TYPE
1306   skupZn = SET OF CHAR;
1307   str = ARRAY [1..20] OF CHAR;
1308   radnici = POINTER TO slog;
1309   slog = RECORD
1310            ime, prez : str;
1311            broj : CARDINAL;
1312            sled : radnici
1313          END;
1314 VAR
1315   meni, pom : CHAR;
1316   rad : radnici;
1317
1318   PROCEDURE Clear();
1319   VAR
1320     br: CARDINAL;
1321   BEGIN
1322     FOR br:=1 TO 100 DO
1323       WriteLn;
1324     END;
1325   END Clear;
1326
1327   PROCEDURE Spisak(rad : radnici);
1328   BEGIN
1329     WHILE rad # NIL DO
1330       WriteString(rad^.ime);
1331       WriteString(' ');
1332       WriteString(rad^.prez);
1333       WriteCard(rad^.broj, 8);
1334       WriteLn;
1335       rad := rad^.sled
1336     END
1337   END Spisak;
1338
1339   PROCEDURE Zaposli(VAR rad : radnici);
1340   VAR
1341     novi, tek : radnici;
1342     nadjen : BOOLEAN;
1343   BEGIN
1344     NEW(novi);
1345     REPEAT
1346       WriteString('Ime, prezime i jedinstveni');
1347       WriteString(' broj novog radnika: ');
1348       WriteLn;
1349       ReadString(novi^.ime);
1350       ReadString(novi^.prez);
1351       ReadCard(novi^.broj);
1352       nadjen := FALSE;
1353       tek := rad;
1354       WHILE NOT nadjen AND (tek # NIL) AND
1355             (tek^.broj <= novi^.broj) DO
1356         IF novi^.broj = tek^.broj THEN
1357           nadjen := TRUE
1358         ELSE
1359           tek := tek^.sled
1360         END
1361       END
1362     UNTIL Done AND NOT nadjen;
1363     IF (rad = NIL) OR (novi^.broj<rad^.broj) THEN
1364       novi^.sled := rad;
1365       rad := novi
1366     ELSE
1367       tek := rad;
1368       WHILE (tek^.sled # NIL) AND
1369             (tek^.sled^.broj < novi^.broj) DO
1370         tek := tek^.sled
1371       END;
1372       novi^.sled := tek^.sled;
1373       tek^.sled := novi
1374     END
1375   END Zaposli;
1376
1377   PROCEDURE Otpusti(VAR rad : radnici);
1378   VAR
1379     tek, pom : radnici;
1380     br : CARDINAL;
1381   BEGIN
1382     REPEAT
1383       WriteLn;
1384       WriteString('Unesite redni broj radnika:');
1385       ReadCard(br)
1386     UNTIL Done;
1387     WriteLn;
1388     IF rad = NIL THEN
1389       WriteString('Greska.')
1390     ELSIF br = rad^.broj THEN
1391       pom := rad;
1392       rad := rad^.sled;
1393       DISPOSE(pom)
1394     ELSE
1395       tek := rad;
1396       WHILE (tek^.sled # NIL) AND
1397             (tek^.sled^.broj < br) DO
1398         tek := tek^.sled
1399       END;
1400       IF (tek^.sled = NIL) OR
1401          (tek^.sled^.broj > br) THEN
1402         WriteString('Greska.')
1403       ELSE
1404         pom := tek^.sled;
1405         tek^.sled := tek^.sled^.sled;
1406         DISPOSE(pom)
1407       END
1408     END
1409   END Otpusti;
1410
1411   PROCEDURE Inform(rad : radnici);
1412   VAR
1413     br : CARDINAL;
1414   BEGIN
1415     REPEAT
1416       WriteLn;
1417       WriteString('Unesite redni broj radnika:');
1418       ReadCard(br)
1419     UNTIL Done;
1420     WriteLn;
1421     WHILE (rad # NIL) AND (rad^.broj < br) DO
1422       rad := rad^.sled
1423     END;
1424     IF (rad = NIL) OR (rad^.broj # br) THEN
1425       WriteString('Greska.')
1426     ELSE
1427       WriteString(rad^.ime);
1428       WriteString(' ');
1429       WriteString(rad^.prez)
1430     END
1431   END Inform;
1432
1433   PROCEDURE Bankrot(VAR rad : radnici);
1434   VAR
1435     pom : radnici;
1436   BEGIN
1437     WHILE rad # NIL DO
1438       pom := rad;
1439       rad := rad^.sled;
1440       DISPOSE(pom)
1441     END
1442   END Bankrot;
1443
1444 BEGIN
1445   rad := NIL;
1446   REPEAT
1447     Clear;
1448     WriteString('s - spisak svih zaposlenih');
1449     WriteLn;
1450     WriteString('z - zaposljavanje radnika');
1451     WriteLn;
1452     WriteString('o - otpustanje radnika');
1453     WriteLn;
1454     WriteString('i - informacije o radniku');
1455     WriteLn;
1456     WriteString('b - bankrot firme');
1457     WriteLn;
1458     WriteString('k - kraj rada');
1459     WriteLn;
1460     REPEAT
1461       meni := RdKey();
1462     UNTIL CAP(meni) IN skupZn{'S', 'Z', 'O',
1463                               'I', 'B', 'K'};
1464     Clear;
1465     IF CAP(meni) # 'K' THEN
1466       CASE CAP(meni) OF
1467         'S' : Spisak(rad)|
1468         'Z' : Zaposli(rad)|
1469         'O' : Otpusti(rad)|
1470         'I' : Inform(rad)|
1471         'B' : Bankrot(rad)
1472       END;
1473       WriteLn;
1474       WriteString('-- pritisnite bilo koji ');
1475       WriteString('taster za nastavak --');
1476       pom := RdKey()
1477     END
1478   UNTIL CAP(meni) = 'K'
1479 END Radnici.
1480 \end{lstlisting}
1481
1482 Procedura \kod{Spisak} se može realizovati i u rekurzivnoj verziji:
1483
1484 \begin{lstlisting}[style=codeblock]
1485   PROCEDURE Spisak(rad : radnici);
1486   BEGIN
1487     IF rad # NIL THEN
1488       WriteString(rad^.ime);
1489       WriteString(' ');
1490       WriteString(rad^.prez);
1491       WriteCard(rad^.broj, 8);
1492       WriteLn;
1493       Spisak(rad^.sled)
1494     END
1495   END Spisak;
1496 \end{lstlisting}
1497
1498 \subsection[Zadatak: Dve liste osoba sa istim sadržajem]{Zadatak: Dve
1499   liste osoba koje dele sadržaj, jedna sortirana po visini, druga po
1500   težini}
1501
1502 Sa tastature učitavati po dva broja koji opisuju osobu (visina i
1503 težina) i smeštati ih u povezane listu, tako da postoji neopadajuće
1504 uređenje i po visini i po težini.
1505
1506 \begin{lstlisting}[style=codeblock]
1507 MODULE VisTez;
1508 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1509 FROM IO IMPORT WrLn, WrStr, RdCard, WrCard;
1510 FROM SYSTEM IMPORT TSIZE;
1511 TYPE
1512   pok = POINTER TO element;
1513   element = RECORD
1514               visina, tezina : CARDINAL;
1515               Vveza, Tveza : pok
1516             END;
1517 VAR
1518   pocV, pocT : pok;
1519   vis, tez : CARDINAL;
1520 PROCEDURE Ispisi(pocV, pocT : pok);
1521 VAR
1522   tek : pok;
1523 BEGIN
1524   tek := pocV;
1525   WrStr('Po visini:');
1526   WrLn;
1527   WHILE tek # NIL DO
1528     WrCard(tek^.visina, 6);
1529     tek := tek^.Vveza
1530   END;
1531   WrLn;
1532   tek := pocT;
1533   WrStr('Po tezini:');
1534   WrLn;
1535   WHILE tek # NIL DO
1536     WrCard(tek^.tezina,6);
1537     tek := tek^.Tveza
1538   END
1539 END Ispisi;
1540
1541 PROCEDURE Ubaci(VAR pocV, pocT : pok;
1542                 vis, tez : CARDINAL);
1543 VAR
1544   novi, tek, iza : pok;
1545   nadjen : BOOLEAN;
1546 BEGIN
1547   IF pocV = NIL THEN
1548     ALLOCATE(pocV, TSIZE(element));
1549     pocV^.visina := vis;
1550     pocV^.tezina := tez;
1551     pocV^.Vveza := NIL;
1552     pocV^.Tveza := NIL;
1553     pocT := pocV
1554   ELSE
1555     ALLOCATE(novi, TSIZE(element));
1556     novi^.visina := vis;
1557     novi^.tezina := tez;
1558     tek := pocV;
1559     nadjen := FALSE;
1560     WHILE (tek # NIL) AND NOT nadjen DO
1561       nadjen := vis <= tek^.visina;
1562       IF NOT nadjen THEN
1563         iza := tek;
1564         tek := tek^.Vveza
1565       END
1566     END;
1567     novi^.Vveza := tek;
1568     IF tek = pocV THEN
1569       pocV := novi
1570     ELSE
1571       iza^.Vveza := novi
1572     END;
1573     tek := pocT;
1574     nadjen := FALSE;
1575     WHILE (tek # NIL) AND NOT nadjen DO
1576       nadjen := tez <= tek^.tezina;
1577       IF NOT nadjen THEN
1578         iza := tek;
1579         tek := tek^.Tveza
1580       END
1581     END;
1582     novi^.Tveza := tek;
1583     IF tek = pocT THEN
1584       pocT := novi
1585     ELSE
1586       iza^.Tveza := novi
1587     END
1588   END
1589 END Ubaci;
1590
1591 BEGIN
1592   pocV := NIL;
1593   pocT := NIL;
1594   WrStr('Unesite visinu ---- ');
1595   vis := RdCard();
1596   WHILE vis > 0 DO
1597     WrStr('Unesite tezinu ---- ');
1598     tez := RdCard();
1599     Ubaci(pocV, pocT, vis, tez);
1600     WrLn;
1601     WrStr('Unesite visinu ---- ');
1602     vis := RdCard()
1603   END;
1604   WrLn;
1605   Ispisi(pocV, pocT)
1606 END VisTez.
1607 \end{lstlisting}
1608
1609 \sectionbreak
1610 \section{Polinomi preko listi}
1611
1612 \subsection{Moduli}
1613
1614 Polinomi su predstavljeni pomoću pokazivača. Apstraktni tip podataka
1615 \kod{Polinom} je definisan u globalnom modulu. Redosled parametara kod
1616 svih procedura je takav da varijabilni parametri dolaze na kraju.
1617
1618 \paragraph{PolinomL.DEF} \
1619
1620 \lstinputlisting[style=codeblock]{kodovi/polinomi/POLINOML.DEF}
1621
1622 \paragraph{PolinomL.MOD} \
1623
1624 \lstinputlisting[style=codeblock]{kodovi/polinomi/POLINOML.MOD}
1625
1626 \subsection{Zadatak: Sabiranje sa unapred određenim polinomom}
1627
1628 Želimo da ispišemo uneti polinom uvećan za\\ $x^5 - 3x^4 + 4x + 7$.
1629
1630 \lstinputlisting[style=codeblock]{kodovi/polinomi/polinom.MOD}
1631
1632 \subsection{Zadatak: Suma k polinoma}
1633
1634 Napisati program koji ucitava broj k (1<=k<=50) i k polinoma, a nakon
1635 toga izracunava njihovu sumu
1636
1637 \lstinputlisting[style=codeblock]{kodovi/polinomi/PolSuma.MOD}
1638
1639 \sectionbreak
1640 \section{Stek i red opsluživanja}
1641
1642 \subsection{Primer: osnovno korišćenje steka i reda opsluživanja}
1643
1644 \lstinputlisting[style=codeblock]{kodovi/stek-redopsl/stekred.mod}
1645
1646 \subsection{Zadatak: Ilustracija pisanja u fajl uz pomoć bafera}
1647
1648 \begin{lstlisting}[style=codeblock]
1649 DEFINITION MODULE QueueInfo;
1650 CONST
1651   Maxqueue = 100;
1652 TYPE
1653   InfoTip = CHAR;
1654
1655 END QueueInfo.
1656
1657 IMPLEMENTATION MODULE QueueInfo;
1658 END QueueInfo.
1659
1660 DEFINITION MODULE RedOpsl1;
1661 FROM QueueInfo IMPORT InfoTip,Maxqueue;
1662 TYPE
1663   Niz = ARRAY[1..Maxqueue] OF InfoTip;
1664   RedOpslTip = RECORD
1665         Prvi, Zadnji : CARDINAL;
1666         Element : Niz
1667   END;
1668
1669 PROCEDURE MakeNull(VAR q : RedOpslTip);
1670 PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
1671 PROCEDURE First(VAR q : RedOpslTip;
1672                 VAR x : InfoTip;
1673                 VAR ok : BOOLEAN);
1674 PROCEDURE PopFirst(VAR q : RedOpslTip;
1675                    VAR ok : BOOLEAN);
1676 PROCEDURE AddRear(VAR q : RedOpslTip;
1677                   x : InfoTip;
1678                   VAR ok : BOOLEAN);
1679
1680 END RedOpsl1.
1681
1682 IMPLEMENTATION MODULE RedOpsl1;
1683 FROM QueueInfo IMPORT Maxqueue,InfoTip;
1684
1685 PROCEDURE MakeNull(VAR q : RedOpslTip);
1686 BEGIN
1687   WITH q DO
1688     Prvi := 0;
1689     Zadnji := 0
1690   END
1691 END MakeNull;
1692
1693 PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
1694 BEGIN
1695   RETURN q.Zadnji = 0
1696 END Empty;
1697
1698
1699 PROCEDURE First(VAR q : RedOpslTip;
1700                 VAR x : InfoTip;
1701                 VAR ok : BOOLEAN);
1702 BEGIN
1703   IF Empty(q) THEN
1704     ok := FALSE
1705   ELSE
1706     ok := TRUE;
1707     WITH q DO
1708       x := Element[Prvi]
1709     END
1710   END
1711 END First;
1712
1713 PROCEDURE AddOne(i : CARDINAL) : CARDINAL;
1714 BEGIN
1715   IF i = Maxqueue THEN
1716     RETURN 1
1717   ELSE
1718     RETURN i+1
1719   END
1720 END AddOne;
1721
1722 PROCEDURE PopFirst(VAR q : RedOpslTip;
1723                    VAR ok : BOOLEAN);
1724 BEGIN
1725   IF Empty(q) THEN
1726     ok := FALSE
1727   ELSE
1728     ok := TRUE;
1729     WITH q DO
1730       IF Prvi = Zadnji THEN
1731         MakeNull(q)
1732       ELSE
1733         Prvi := AddOne(Prvi)
1734       END
1735     END
1736   END
1737 END PopFirst;
1738
1739 PROCEDURE AddRear(VAR q : RedOpslTip;
1740                   x : InfoTip;
1741                   VAR ok : BOOLEAN);
1742 BEGIN
1743   WITH q DO
1744     IF AddOne(Zadnji) = Prvi THEN
1745       ok := FALSE
1746     ELSE
1747       ok := TRUE;
1748       IF Empty(q) THEN
1749         Prvi := 1;
1750         Zadnji := 1
1751       ELSE
1752         Zadnji := AddOne(Zadnji)
1753       END;
1754       Element[Zadnji] := x
1755     END
1756   END
1757 END AddRear;
1758
1759 END RedOpsl1.
1760
1761 MODULE Bafer;
1762 FROM RedOpsl1 IMPORT RedOpslTip, MakeNull, Empty, First, PopFirst, AddRear;
1763 FROM FIO IMPORT File,WrChar, Create, Close;
1764 IMPORT IO;
1765
1766 CONST
1767   ImeIzlaza = 'izlaz.txt';
1768
1769 VAR
1770   izlaz : File;
1771   znak : CHAR;
1772   buffer : RedOpslTip;
1773
1774 PROCEDURE IsprazniBafer(VAR dat : File;
1775                         VAR buf : RedOpslTip);
1776 VAR
1777   znak : CHAR;
1778   ok : BOOLEAN;
1779 BEGIN
1780   WHILE NOT Empty(buf) DO
1781     First(buf, znak, ok);
1782     PopFirst(buf, ok);
1783     WrChar(dat, znak)
1784   END
1785 END IsprazniBafer;
1786
1787 PROCEDURE BaferWrite(VAR dat : File;
1788                      VAR buf : RedOpslTip;
1789                      znak : CHAR);
1790 VAR
1791   ok : BOOLEAN;
1792 BEGIN
1793   AddRear(buf, znak, ok);
1794   IF NOT ok THEN
1795     IsprazniBafer(dat, buf);
1796     AddRear(buf, znak, ok)
1797   END
1798 END BaferWrite;
1799
1800 BEGIN
1801   izlaz := Create(ImeIzlaza);
1802   MakeNull(buffer);
1803   IO.WrStr('Unesite tekst, koji treba da se unese u datoteku ');
1804   IO.WrStr(ImeIzlaza);
1805   IO.WrChar('.');
1806   IO.WrLn;
1807   IO.WrStr('Unos zavrsite tackom.');
1808   IO.WrLn;
1809   znak := IO.RdChar();
1810   WHILE znak # '.' DO
1811     BaferWrite(izlaz, buffer, znak);
1812     znak := IO.RdChar();
1813   END;
1814   IsprazniBafer(izlaz, buffer);
1815   Close(izlaz)
1816 END Bafer.
1817 \end{lstlisting}
1818
1819 \subsection%
1820 {Zadatak: Ispitivanje da li reč pripada gramatici wcw$^+$}
1821
1822 Reč pripada ovoj gramatici ako joj se prvi deo (w) sastoji samo od
1823 slova 'a' i 'b', sledi slovo 'c' a nakon njega obrnuta reč reči w.
1824
1825 \begin{codeblock}
1826 DEFINITION MODULE Stek;
1827 CONST
1828   Maxstack = 100;
1829 TYPE
1830   Niz = ARRAY [1..Maxstack] OF CHAR;
1831   StekTip = RECORD
1832             Top : CARDINAL;
1833             Element : Niz
1834           END;
1835 PROCEDURE MakeNull(VAR s : StekTip);
1836 PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
1837
1838 PROCEDURE Top(VAR s : StekTip;
1839               VAR x : CHAR;
1840               VAR ok : BOOLEAN);
1841 PROCEDURE Pop(VAR s : StekTip;
1842               VAR ok : BOOLEAN);
1843 PROCEDURE Push(VAR s : StekTip;
1844                x : CHAR;
1845                VAR ok : BOOLEAN);
1846 END Stek.
1847
1848
1849 IMPLEMENTATION MODULE Stek;
1850
1851 PROCEDURE MakeNull(VAR s : StekTip);
1852 BEGIN
1853   s.Top := 0
1854 END MakeNull;
1855
1856 PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
1857 BEGIN
1858   RETURN s.Top = 0
1859 END Empty;
1860
1861 PROCEDURE Top(VAR s : StekTip;
1862               VAR x : CHAR;
1863               VAR ok : BOOLEAN);
1864 BEGIN
1865   IF Empty(s) THEN
1866     ok := FALSE
1867   ELSE
1868     ok := TRUE;
1869     WITH s DO
1870       x := Element[Top]
1871     END
1872   END
1873 END Top;
1874
1875 PROCEDURE Pop(VAR s : StekTip;
1876               VAR ok : BOOLEAN);
1877 BEGIN
1878   IF Empty(s) THEN
1879     ok := FALSE
1880   ELSE
1881     ok := TRUE;
1882     DEC(s.Top)
1883   END
1884 END Pop;
1885
1886 PROCEDURE Push(VAR s : StekTip;
1887                x : CHAR;
1888                VAR ok : BOOLEAN);
1889 BEGIN
1890   WITH s DO
1891     IF Top = Maxstack THEN
1892       ok := FALSE
1893     ELSE
1894       ok := TRUE;
1895       INC(Top);
1896       Element[Top] := x
1897     END
1898   END
1899 END Push;
1900 END Stek.
1901
1902 MODULE wcw;
1903 (* Da li rec pripada gramatici wcw+. *)
1904 FROM Stek IMPORT StekTip, MakeNull, Empty,
1905                  Top, Pop, Push;
1906 FROM InOut IMPORT Read, Write, WriteString, EOL;
1907 TYPE
1908   slova = SET OF CHAR;
1909 VAR
1910   S : StekTip;
1911   Ch, C : CHAR;
1912   ok : BOOLEAN;
1913 BEGIN
1914   MakeNull(S);
1915   Read(Ch);
1916   ok := TRUE;
1917   WHILE ok AND (Ch IN slova{'a', 'b'}) DO
1918     Push(S, Ch, ok);
1919     Read(Ch);
1920   END;
1921   IF NOT ok THEN
1922     WriteString('Greska - mali stek')
1923   ELSIF Ch # 'c' THEN
1924     WriteString('Pogresan string')
1925   ELSE
1926     Read(Ch);
1927     WHILE ok AND (Ch # EOL) DO
1928       Top(S, C, ok);
1929       ok := ok AND (C = Ch);
1930       IF ok THEN
1931         Pop(S, ok);
1932         Read(Ch);
1933       END
1934     END;
1935     IF NOT (ok AND Empty(S)) THEN
1936       WriteString('Pogresan string')
1937     ELSE
1938       WriteString('String pripada jeziku L')
1939     END
1940   END
1941 END wcw.
1942 \end{codeblock}
1943
1944 \manbreakJK
1945
1946 \subsection{Zadatak: Kalkulator za izračunavanje postfiksnih izraza}
1947
1948
1949 Napraviti kalkulator za izračunavanje postfiksnih izraza. Svi brojevi
1950 koji figurišu u izrazu su jednocifreni.
1951
1952 \begin{lstlisting}[style=codeblock]
1953 MODULE PostFix;
1954
1955 FROM StekI IMPORT StekTip, MakeNull, Empty, Top, Pop, Push;
1956 FROM InOut IMPORT Read, Write, WriteInt, EOL;
1957 TYPE
1958   slova = SET OF CHAR;
1959 VAR
1960   S : StekTip;
1961   Ch : CHAR;
1962   Op1, Op2 : INTEGER;
1963   ok : BOOLEAN;
1964 PROCEDURE Conv(Ch : CHAR) : INTEGER;
1965 BEGIN
1966   RETURN  ORD(Ch) - ORD('0')
1967 END Conv;
1968
1969 BEGIN
1970   MakeNull(S);
1971   Read(Ch);
1972   WHILE Ch # EOL DO
1973     IF Ch IN slova{'+', '-', '/', '*', '%'} THEN
1974       Top(S, Op2, ok);
1975       Pop(S, ok);
1976       Top(S, Op1, ok);
1977       Pop(S, ok);
1978       CASE Ch OF
1979         '+' : Op1 := Op1 + Op2 |
1980         '-' : Op1 := Op1 - Op2 |
1981         '*' : Op1 := Op1 * Op2 |
1982         '/' : Op1 := Op1 DIV Op2 |
1983         '%' : Op1 := Op1 MOD Op2
1984       END;
1985       Push(S, Op1, ok)
1986     ELSE
1987       Push(S, Conv(Ch), ok)
1988     END;
1989     Read(Ch);
1990   END;
1991   Top(S, Op1, ok);
1992   Write('=');
1993   WriteInt(Op1,5)
1994 END PostFix.
1995 \end{lstlisting}
1996
1997 \sectionbreak
1998 \section{Simulacija rekurzije}
1999
2000
2001 Na početku označiti sve rekurzivne pozive u originalnoj proceduri
2002 adresama (npr. 1,2,3... ili konstante nabrojivog tipa podataka).
2003
2004 Na steku se čuvaju lokalne promenljive, parametri procedure i adresa
2005 mesta poziva, a u skladu sa tim se kreira InfoTip.
2006
2007 Trivijalnim pozivom se smatra onaj koji se izračunava bez dodatnih
2008 rekurzivnih poziva.
2009
2010 U kodu ispod, \kod{treba\_rekurzija} znači da je poziv netrivijalan,
2011 odnosno treba naći uslove pod kojima se sigurno dešavaju rekurzivni
2012 pozivi.
2013
2014 \begin{lstlisting}
2015 MakeNull(S);
2016 REPEAT
2017   WHILE treba_rekurzija DO
2018     -prepisati sve od pocetka originalne
2019      procedure do prvog rekurzivnog poziva
2020     -staviti na stek potrebne
2021      lokalne promenljive, parametre procedure i
2022      adresu mesta poziva
2023     -podesiti vrednosti parametara da budu
2024      kao u rekurzivnom pozivu procedure
2025   END;
2026   trivijalan poziv
2027   umesto RETURN x pisati rez := x
2028   jos := TRUE;
2029   WHILE jos AND NOT Empty(S) DO
2030     Top(S, el, ok);
2031     Pop(S, ok);
2032     -restauriramo vrednosti sa steka
2033     -u zavisnosti od adrese poziva nastavimo
2034      prepisivanje originalne procedure sa
2035      tog mesta
2036     -ako se dodje do novog rek. poziva tada:
2037        -sacuvati na steku vrednosti
2038        -podesiti vrednosti parametara da budu
2039         kao u rekurzivnom pozivu procedure
2040        -ici na pocetak koda
2041         (ovo se postize sa jos := FALSE)
2042     -inace
2043        ako se naidje na RETURN x pisati rez := x
2044   END
2045 UNTIL Empty(S);
2046 \end{lstlisting}
2047
2048 Ako je procedura funkcijska tada se na kraj dodaje \kod{RETURN rez}.
2049
2050 \subsection*{ZADACI}
2051
2052 Simulirati ponašanje sledećih rekurzivnih procedura (funkcija) upotrebom steka:
2053
2054 \subsection{Primer 1 -- faktorijel}
2055
2056
2057 \begin{lstlisting}[style=codeblock]
2058 MODULE Fakto;
2059 (* InfoTip = CARDINAL; *)
2060
2061 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2062 FROM StekC IMPORT StekTip, MakeNull, Empty,
2063                   Top, Pop, Push;
2064 VAR
2065   n : CARDINAL;
2066 PROCEDURE RFakto(n : CARDINAL) : CARDINAL;
2067 BEGIN
2068   IF n <= 1 THEN
2069     RETURN 1
2070   ELSE
2071     RETURN n * RFakto(n-1)
2072   END
2073 END RFakto;
2074
2075
2076 PROCEDURE SFakto(n : CARDINAL) : CARDINAL;
2077 VAR
2078   s : StekTip;
2079   rez : CARDINAL;
2080   OK : BOOLEAN;
2081 BEGIN
2082   MakeNull(s);
2083   WHILE n > 1 DO
2084     Push(s,n,OK);
2085     DEC(n)
2086   END;
2087   rez := 1;
2088   WHILE NOT Empty(s) DO
2089     Top(s, n, OK);
2090     Pop(s, OK);
2091     rez := n * rez
2092   END;
2093   RETURN rez
2094 END SFakto;
2095
2096 BEGIN
2097   WrStr('n = ');
2098   n := RdCard();
2099   WrLn
2100   WrStr('n! = ');
2101   WrCard(RFakto(n), 1);
2102   WrStr(' = ');
2103   WrCard(SFakto(n), 1)
2104 END Fakto.
2105 \end{lstlisting}
2106
2107 \subsection{Primer 2 -- stepenovanje}
2108
2109 \begin{lstlisting}[style=codeblock]
2110 MODULE Step;
2111 (* InfoTip = RECORD
2112                 x : REAL;
2113                 n : CARDINAL;
2114                 adr : (par, nepar)
2115              END;
2116 *)
2117 FROM IO IMPORT WrStr, WrLn, WrReal,
2118         RdReal, RdCard;
2119 FROM StekStep IMPORT StekTip, MakeNull, Empty,
2120              Top, Pop, Push, InfoTip, AdrTip;
2121 VAR
2122   n : CARDINAL;
2123   x : REAL;
2124
2125 PROCEDURE Sqr(y : REAL) : REAL;
2126 BEGIN
2127   RETURN y * y
2128 END Sqr;
2129
2130 PROCEDURE RStep(x : REAL;
2131                 n : CARDINAL) : REAL;
2132 BEGIN
2133   IF n = 0 THEN
2134     RETURN 1.
2135   ELSIF ODD(n) THEN
2136     RETURN x * Sqr( RStep(x, n DIV 2) )
2137   ELSE
2138     RETURN Sqr( RStep(x, n DIV 2) )
2139   END
2140 END RStep;
2141
2142 PROCEDURE SStep(x : REAL;
2143                 n : CARDINAL ) : REAL;
2144 VAR
2145   s : StekTip;
2146   OK : BOOLEAN;
2147   rez : REAL;
2148   el : InfoTip;
2149 BEGIN
2150   MakeNull(s);
2151   WHILE n > 0 DO
2152     el.x := x;
2153     el.n := n;
2154     IF ODD(n) THEN
2155       el.adr := nepar;
2156     ELSE
2157       el.adr := par
2158     END;
2159     Push(s,el,OK);
2160     n := n DIV 2
2161   END;
2162   rez := 1.;
2163   WHILE NOT Empty(s) DO
2164     Top(s, el, OK);
2165     Pop(s, OK);
2166     x := el.x;
2167     n := el.n;
2168     IF el.adr = nepar THEN
2169       rez := x * Sqr(rez)
2170     ELSE
2171       rez := Sqr(rez)
2172     END
2173   END;
2174   RETURN rez
2175 END SStep;
2176
2177 BEGIN
2178   WrStr('x =? ');
2179   x := RdReal();
2180   WrLn;
2181   WrStr('n =? ');
2182   n := RdCard();
2183   WrStr('x^n = ');
2184   WrReal(RStep(x, n), 10, 1);
2185   WrStr(' = ');
2186   WrReal(SStep(x, n), 10, 1)
2187 END Step.
2188 \end{lstlisting}
2189
2190 \subsection{Primer 3 -- Fibonači}
2191
2192 \begin{lstlisting}[style=codeblock]
2193 MODULE Fib;
2194 (* InfoTip = RECORD
2195                 n : CARDINAL;
2196                 PrviSab : CARDINAL;
2197                 adr : (prvi, drugi)
2198              END;
2199 *)
2200
2201 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2202 FROM StekFib IMPORT StekTip, MakeNull, Empty,
2203        Top, Pop, Push, InfoTip, AdrTip;
2204 VAR
2205   n : CARDINAL;
2206
2207 PROCEDURE RFib(n : CARDINAL) : CARDINAL;
2208 BEGIN
2209   IF n <= 1 THEN
2210     RETURN n
2211   ELSE
2212     RETURN RFib(n-1) + RFib(n-2)
2213   END
2214 END RFib;
2215
2216 PROCEDURE SFib(n : CARDINAL ) : CARDINAL;
2217 VAR
2218   s : StekTip;
2219   OK, jos : BOOLEAN;
2220   rez, PrviSab : CARDINAL;
2221   el : InfoTip;
2222 BEGIN
2223   MakeNull(s);
2224   REPEAT
2225     WHILE n > 1 DO
2226       el.n := n;
2227       el.adr := prvi;
2228       Push(s,el,OK);
2229       DEC(n)
2230     END;
2231     rez := (n);
2232     jos := TRUE;
2233     WHILE (NOT Empty(s)) AND jos DO
2234       Top(s, el, OK);
2235       Pop(s, OK);
2236       n := el.n;
2237       IF el.adr = prvi THEN
2238         PrviSab := rez;
2239         el.n := n;
2240         el.adr := drugi;
2241         el.PrviSab := PrviSab;
2242         Push(s, el, OK);
2243         DEC(n, 2);
2244         jos := FALSE
2245       ELSE
2246         PrviSab := el.PrviSab;
2247         rez := PrviSab + rez
2248       END
2249     END
2250   UNTIL Empty(s);
2251   RETURN rez
2252 END SFib;
2253
2254 BEGIN
2255   WrStr('n =? ');
2256   n := RdCard();
2257   WrStr('F(n) = ');
2258   WrCard(RFib(n), 1);
2259   WrStr(' = ');
2260   WrCard(SFib(n), 1)
2261 END Fib.
2262 \end{lstlisting}
2263
2264 \subsection{Primer 4 -- faktorijel 2}
2265
2266
2267 \begin{lstlisting}[style=codeblock]
2268 MODULE Faktor;
2269 (* InfoTip = CARDINAL; *)
2270 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2271 FROM StekC IMPORT StekTip, MakeNull, Empty,
2272                   Top, Pop, Push;
2273 VAR
2274   n,rez : CARDINAL;
2275
2276 PROCEDURE RFakto(n : CARDINAL;
2277                  VAR rez : CARDINAL);
2278 BEGIN
2279   IF n = 0 THEN
2280     rez := 1
2281   ELSE
2282     RFakto(n-1, rez);
2283     rez := n * rez
2284   END
2285 END RFakto;
2286
2287 PROCEDURE SFakto(n : CARDINAL;
2288                  VAR rez : CARDINAL);
2289 VAR
2290   s : StekTip;
2291   OK : BOOLEAN;
2292 BEGIN
2293   MakeNull(s);
2294   WHILE n > 0 DO
2295     Push(s,n,OK);
2296     DEC(n)
2297   END;
2298   rez := 1;
2299   WHILE NOT Empty(s) DO
2300     Top(s, n, OK);
2301     Pop(s, OK);
2302     rez := n * rez
2303   END
2304 END SFakto;
2305
2306 BEGIN
2307   WrStr('n =? ');
2308   n := RdCard();
2309   WrLn;
2310   WrStr('n! = ');
2311   RFakto(n, rez);
2312   WrCard(rez, 1);
2313   WrStr(' = ');
2314   SFakto(n, rez);
2315   WrCard(rez, 1)
2316 END Faktor.
2317 \end{lstlisting}
2318
2319 \subsection{Primer 5 (ispitni)}
2320
2321
2322 \begin{lstlisting}[style=codeblock]
2323 MODULE Rek1;
2324 (* InfoTip = RECORD
2325                 d, g, m1, m2 : INTEGER;
2326                 adr : (prvi, drugi)
2327              END;
2328 *)
2329 FROM Stek1 IMPORT StekTip, adresa, InfoTip,
2330          MakeNull, Empty, Top, Pop, Push;
2331 IMPORT IO;
2332 VAR
2333   X : ARRAY [1..20] OF INTEGER;
2334
2335 PROCEDURE Max(d, g: INTEGER) : INTEGER;
2336 VAR
2337   m1, m2 : INTEGER;
2338 BEGIN
2339   IF d>g THEN
2340     RETURN MIN(INTEGER)
2341   ELSIF d=g THEN
2342     RETURN X[d]
2343   ELSE
2344     m1 := Max(d, (d+g) DIV 2);
2345     m2 := Max((d+g) DIV 2 +1, g);
2346     IF m1 > m2 THEN
2347       RETURN m1
2348     ELSE
2349       RETURN m2
2350     END
2351   END
2352 END Max;
2353
2354 PROCEDURE SMax(d, g: INTEGER) : INTEGER;
2355 VAR
2356   S : StekTip;
2357   el : InfoTip;
2358   ok, jos : BOOLEAN;
2359   m1, m2, rez : INTEGER;
2360 BEGIN
2361   MakeNull(S);
2362   REPEAT
2363     WHILE d<g DO
2364       el.d := d;
2365       el.g := g;
2366       el.adr := prvi;
2367       Push(S, el, ok);
2368       g := (d+g) DIV 2
2369     END;
2370     IF d>g THEN
2371       rez := MIN(INTEGER)
2372     ELSE (* d=g *)
2373       rez := X[d]
2374     END;
2375     jos := TRUE;
2376     WHILE jos AND NOT Empty(S) DO
2377       Top(S, el, ok);
2378       Pop(S, ok);
2379       d := el.d;
2380       g := el.g;
2381       m1 := el.m1;
2382       IF el.adr = prvi THEN
2383         m1 := rez;
2384         el.m1 := m1;
2385         el.adr := drugi;
2386         Push(S, el, ok);
2387         d := (d+g) DIV 2 + 1;
2388         jos := FALSE
2389       ELSE (*el.adr = drugi*)
2390         m2 := rez;
2391         IF m1 > m2 THEN
2392           rez := m1
2393         ELSE
2394           rez := m2
2395         END
2396       END
2397     END
2398   UNTIL Empty(S);
2399   RETURN rez
2400 END SMax;
2401
2402 BEGIN (* glavni program *)
2403   X[1] := 3;
2404   X[2] := 2;
2405   X[3] := 5;
2406   X[4] := -7;
2407   X[5] := 0;
2408   IO.WrCard(Max(1, 5), 3);
2409   IO.WrLn;
2410   IO.WrCard(SMax(1, 5), 3);
2411   IO.WrLn
2412 END Rek1.
2413 \end{lstlisting}
2414
2415 \subsection{Primer 6 (ispitni)}
2416
2417
2418 \begin{lstlisting}[style=codeblock]
2419 MODULE Rek2;
2420 (* InfoTip = RECORD
2421                 x, y, n : CARDINAL;
2422                 adr : (prvi, drugi, treci, cetvrti)
2423              END;
2424 *)
2425 FROM Stek2 IMPORT StekTip, adresa, InfoTip,
2426            MakeNull, Empty, Top, Pop, Push;
2427 IMPORT IO;
2428
2429 PROCEDURE g(x : CARDINAL; y : CARDINAL;
2430             n : CARDINAL) : CARDINAL;
2431 BEGIN
2432   IF n < 3 THEN
2433     RETURN x + y
2434   ELSIF ODD(n) THEN
2435     RETURN g(g(x+1, y, n-2), y, n-3)
2436   ELSE
2437     RETURN g(x, g(x, y+1, n-2), n-3)
2438   END
2439 END g;
2440
2441 PROCEDURE Sg(x : CARDINAL; y : CARDINAL;
2442              n : CARDINAL) : CARDINAL;
2443 VAR
2444   S : StekTip;
2445   el : InfoTip;
2446   ok, jos : BOOLEAN;
2447   rez : CARDINAL;
2448 BEGIN
2449   MakeNull(S);
2450   REPEAT
2451     WHILE n >= 3 DO
2452       IF ODD(n) THEN
2453         el.x := x;
2454         el.y := y;
2455         el.n := n;
2456         el.adr := prvi;
2457         Push(S, el, ok);
2458         INC(x);
2459         DEC(n, 2)
2460       ELSE
2461         el.x := x;
2462         el.y := y;
2463         el.n := n;
2464         el.adr := treci;
2465         Push(S, el, ok);
2466         INC(y);
2467         DEC(n, 2)
2468       END
2469     END;
2470     rez := x+y;
2471     jos := TRUE;
2472     WHILE jos AND NOT Empty(S) DO
2473       Top(S, el, ok);
2474       Pop(S, ok);
2475       x := el.x;
2476       y := el.y;
2477       n := el.n;
2478       IF el.adr = prvi THEN
2479         el.adr := drugi;
2480         Push(S, el, ok);
2481         x := rez;
2482         DEC(n, 3);
2483         jos := FALSE
2484       ELSIF el.adr = treci THEN
2485         el.adr := cetvrti;
2486         Push(S, el, ok);
2487         y := rez;
2488         DEC(n, 3);
2489         jos := FALSE
2490       END
2491     END
2492   UNTIL Empty(S);
2493   RETURN rez
2494 END Sg;
2495
2496 BEGIN (* glavni program *)
2497   IO.WrCard(g(2, 3, 10), 3);
2498   IO.WrCard(Sg(2, 3, 10), 3);
2499 END Rek2.
2500 \end{lstlisting}
2501
2502 %\columnbreak
2503
2504 \appendix
2505
2506 \sectionbreak
2507 \pagenumbering{Roman}
2508 \input{xds-uputstvo}
2509
2510 \sectionbreak
2511 \input{xds-komandna-linija}
2512
2513 \mainend
2514
2515
2516
2517 %%% Local Variables:
2518 %%% mode: latex
2519 %%% TeX-master: "skripta-spa1-jk"
2520 %%% End: