skripta-spa1.tex

   1 % skripta-spa1.tex
   2 % Skripta za predmet Strukture podataka i algoritmi 1, DMI, PMF, NS
   3
   4 \documentclass[a4paper,twoside]{article}
   5 \usepackage[T1]{fontenc}
   6 \usepackage[utf8]{inputenc}%definišemo da je ulaz utf-8 fajl
   7
   8 % osnovne informacije koje ce se prikazati na naslovnoj strani,
   9 % kao i u informacijama u generisanom pdfu
  10 \newcommand{\autor}{Vladimir Kurbalija, Milos Radovanovic, Doni Pracner}
  11 \newcommand{\naslov}{Skripta za vezbe iz predmeta "Strukture podataka
  12   i algoritmi 1"}
  13 \newcommand{\datum}{Februar 2013, Novi Sad}
  14 \newcommand{\verzija}{ver 13a-jk}
  15 %jk=jedna kolona, dk=dve kolone
  16
  17 \newcommand{\mainstart}{
  18 %\begin{multicols}{2}
  19 }
  20
  21 \newcommand{\mainend}{
  22 %\end{multicols}
  23 }
  24
  25 \usepackage[serbian]{babel}
  26 \usepackage{fancyhdr}
  27 \pagestyle{fancy}
  28
  29 \title{\naslov -- \verzija}
  30 \author{\autor}
  31 \date{\datum}
  32
  33 %change the default font
  34 \usepackage{lmodern}
  35 \usepackage{beramono}
  36 \renewcommand{\familydefault}{\sfdefault}
  37
  38 \usepackage{pifont}
  39
  40 %podesavanja outputa za pdf verzije
  41 \usepackage[bookmarks,pdffitwindow=false,unicode=true,%
  42 pdftitle={\naslov -- \verzija},%
  43 pdfauthor={\autor}%
  44 ]{hyperref}
  45
  46 \usepackage{graphicx}
  47 \usepackage{listings}
  48 \usepackage{amsthm}
  49 \usepackage{amsmath}
  50 \usepackage{latexsym}
  51 \usepackage{multicol}
  52
  53 %margine
  54 %experiment
  55 %\usepackage[top=2.5cm, bottom=1.5cm, left=3cm, right=2cm]{geometry}
  56 %staro:
  57 \usepackage[top=1.5cm, bottom=1cm, left=2cm, right=1cm]{geometry}
  58
  59 \begin{document}
  60
  61 %customize the itemize environments
  62
  63 \let\olditemize=\itemize
  64 \def\itemize{
  65 \olditemize
  66   \setlength{\itemsep}{1pt}
  67   \setlength{\parskip}{0pt}
  68   \setlength{\parsep}{0pt}
  69   \setlength{\topsep}{-1cm}
  70   \setlength{\partopsep}{1pt}
  71 }
  72
  73 %% ovi redovi daju header i footer
  74
  75 \renewcommand{\sectionmark}[1]{\markright{\thesection\ #1}}
  76 \fancyhf{} % delete current setting for header and footer
  77 %\fancyfoot[C]{\thepage}
  78 \fancyhead[LO]{\bfseries\rightmark}
  79 \fancyhead[RO]{\thepage}
  80 \fancyhead[RE]{Strukture podataka i algoritmi 1 -- skripta}
  81 \fancyhead[LE]{\thepage}
  82 \renewcommand{\headrulewidth}{0.5pt}
  83 \renewcommand{\headwidth}{\textwidth}
  84 %\renewcommand{\footrulewidth}{0.5pt}
  85 %\addtolength{\headheight}{0.5pt} % make space for the rule
  86 \fancypagestyle{plain}{%
  87 \fancyhead{} % get rid of headers on plain pages
  88 \fancyfoot{}
  89 \renewcommand{\headrulewidth}{0pt} % and the line
  90 \renewcommand{\footrulewidth}{0pt} % and the line
  91 }
  92 \renewcommand{\headheight}{15pt}
  93
  94 %promene u marginama:
  95 %\setlength{\marginparwidth}{32pt}
  96 %\setlength{\textwidth}{620pt}
  97 %\setlength{\textheight}{620pt}
  98
  99
 100 %% specijalni blokovi koji služe kao podsetnici u radu ili napomene
 101 \newcommand{\skica}[1]{
 102     \noindent \framebox{\parbox[c]{0.9\textwidth}{  {\small** \textit{#1}  }}
 103     \newline }
 104 }
 105
 106 \newcommand{\skicas}[1]{
 107     \framebox{* \textit{#1} *}
 108 }
 109
 110 %boldovane skice visokog prioriteta
 111 \newcommand{\skicab}[1]{
 112   \noindent \framebox{\parbox[c]{0.9\textwidth}{ {\small***
 113         \textbf{#1} }} \newline } }
 114
 115 \newcommand{\kod}[1]{{\small\texttt{#1}}}
 116
 117 % ako je sledeci red odkomentarisan nista od skica nece biti ispisano
 118 % u finalni dokument
 119
 120 % \renewcommand{\skica}[1]{}
 121
 122 % title u skladu sa uobičajenim na Departmanu
 123 \newcommand{\makemytitle}{
 124   \begin{center}
 125         \makebox{%
 126         \includegraphics[width=2cm]{grbPMF}
 127         \parbox[b]{65ex}{\centering
 128                 Univerzitet u Novom Sadu\\
 129                 Prirodno-matematički fakultet\\
 130                 Departman za matematiku i informatiku}
 131         \includegraphics[width=2cm]{grbUNS}
 132         }
 133         \vspace{10ex}
 134
 135         \parbox[b]{\textwidth}{{\Large {\bf
 136               Vladimir Kurbalija, \href{mailto:kurba@dmi.rs}{kurba@dmi.rs}\\
 137               Miloš Radovanović, \href{mailto:radacha@dmi.rs}{radacha@dmi.rs}\\
 138               Doni Pracner, \href{mailto:doni.pracner@dmi.rs}{doni.pracner@dmi.rs}}}}
 139         \vspace{5ex}
 140
 141         {\Large {\bf Skripta za vežbe iz predmeta }}
 142
 143         {\Huge {\bf
 144             \setlength{\baselineskip}{1.5\baselineskip}Strukture
 145               podataka i algoritmi 1}}
 146
 147         \vspace{5ex}
 148         %\vfill
 149
 150         \verzija \ -- \datum
 151
 152         \end{center}
 153         \thispagestyle{plain}
 154 %       \newpage
 155 }
 156
 157 \makemytitle
 158
 159 % theorems, definition etc.
 160 %''''''''''''''''''''''''''
 161
 162 \theoremstyle{definition}
 163 \newtheorem{def1}{Definicija}
 164 \theoremstyle{plain}
 165 \newtheorem{theo}{Teorema}
 166 \newtheorem{lema}{Lema}
 167
 168 \lstloadlanguages{Modula-2}
 169
 170 \lstset{
 171         basicstyle=\footnotesize\ttfamily,
 172         showstringspaces=false,
 173         breaklines=true
 174 }
 175
 176 \lstdefinestyle{codeblock}{
 177         basicstyle=\footnotesize\ttfamily,
 178         keywordstyle=\textbf,
 179         columns=[l]fixed,
 180         breakatwhitespace=true,
 181 %        prebreak=\P,
 182 %        postbreak=\ding{229}\space,
 183         language=Modula-2
 184 }
 185
 186 \lstdefinestyle{numcodeblock}{
 187   style=codeblock,
 188   numbers=left
 189 }
 190
 191 \lstnewenvironment{codeblock}{\lstset{style=codeblock}}{}
 192
 193
 194 % ----------------==================--------------------------------------
 195 %                 Pravi pocetak rada
 196
 197
 198 Programi u ovoj skripti su testirani sa kompajlerom 'Native XDS Modula
 199 2'. Za verzije pre 2.60 je neophodno dodatno instalirati i TSCP (Top
 200 Speed Compatibility Pack), pošto je potreban za neke od modula koji se
 201 ne nalaze u ISO standardu Module 2. U novijim verzijama su i ovi
 202 moduli uključeni u standardnu instalaciju.
 203
 204 Sav sadržaj se može koristiti u skladu sa {\ttfamily CC-BY-NC-SA} licencom. \url{http://creativecommons.org/licenses/by-nc-sa/3.0/}
 205
 206 \tableofcontents
 207
 208 \newpage
 209
 210 \mainstart
 211
 212 \section{Ilustracija efikasnosti algoritma}
 213
 214 \subsection{Zadatak: Pronaći sve pitagorine
 215 trojke do zadate granice}
 216
 217 Pitagorina trojka su tri broja $a,b,c$ za koje važi $a^2 + b^2 = c^2\\$
 218
 219 \begin{lstlisting}[style=codeblock]
 220 MODULE Trojke1;
 221 (* Pitagorine trojke koriscenjem "Brute-force" *)
 222 FROM InOut IMPORT WriteString, WriteLn, WriteCard;
 223 CONST
 224   Gr = 100;
 225 VAR
 226   a, b, c : [1 .. Gr];
 227 BEGIN
 228   FOR a := 1 TO Gr DO
 229     FOR b := 1 TO Gr DO
 230       FOR c := 1 TO Gr DO
 231         IF a*a + b*b = c*c THEN
 232           WriteLn;
 233           WriteString('a = ');
 234           WriteCard(a,2);
 235           WriteString(', b = ');
 236           WriteCard(b,2);
 237           WriteString(', c = ');
 238           WriteCard(c,2)
 239         END
 240       END
 241     END
 242   END
 243 END Trojke1.
 244 \end{lstlisting}
 245
 246 \begin{codeblock}
 247 MODULE Trojke2;
 248 (*Pitagorine trojke koriscenjem zaokrugljivanja*)
 249 FROM InOut IMPORT WriteString, WriteLn, WriteCard;
 250 FROM MathLib0 IMPORT sqrt;
 251 CONST
 252   Gr = 100;
 253 VAR
 254   a, b, c : CARDINAL;
 255   creal : REAL;
 256 BEGIN
 257   FOR a := 1 TO Gr DO
 258     FOR b := 1 TO Gr DO
 259       creal := FLOAT(a*a) + FLOAT(b*b);
 260       creal := sqrt(creal);
 261       c := TRUNC(creal);
 262       IF creal = FLOAT(c) THEN
 263         WriteLn;
 264         WriteString(' a = ');
 265         WriteCard(a,2);
 266         WriteString(', b = ');
 267         WriteCard(b,2);
 268         WriteString(', c = ');
 269         WriteCard(c,2)
 270       END
 271     END
 272   END
 273 END Trojke2.
 274 \end{codeblock}
 275
 276 Sledeći primer koristi Euklidovu teoremu i malo drugačiji pristup.
 277 Ako uzmemo neka dva prirodna broja $m$ i $n$, tada se iz njih može
 278 izvesti jedna Pitagorina trojka koja lako zadovoljava potrebne uslove:
 279 \[
 280 \begin{array}{l}
 281 a = 2mn\\
 282 b = m^2 - n^2\\
 283 c = m^2 + n^2
 284 \end{array}
 285 \]
 286 Odnosno kad probamo da proverimo da li je ovo
 287 Pitagorina trojka dobijamo:
 288 \[
 289 \begin{array}{r@=l}
 290 a^2 + b^2 & c^2\\
 291 (2mn)^2 + (m^2 - n^2)^2 & (m^2 + n^2)^2
 292 \end{array}
 293 \]
 294
 295 \begin{codeblock}
 296 MODULE Trojke3;
 297 (* Pitagorine trojke koriscenjem teoreme *)
 298 FROM InOut IMPORT WriteString, WriteLn, WriteCard;
 299 CONST
 300   Gr = 10;
 301 VAR
 302   a, b, c, m, n : CARDINAL;
 303 BEGIN
 304   FOR m := 1 TO Gr DO
 305     FOR n := 1 TO m-1 DO
 306       a := 2*m*n;
 307       b := m*m - n*n;
 308       c := m*m + n*n;
 309       WriteLn;
 310       WriteString('a = ');
 311       WriteCard(a,2);
 312       WriteString(', b = ');
 313       WriteCard(b,2);
 314       WriteString(', c = ');
 315       WriteCard(c,2)
 316     END
 317   END
 318 END Trojke3.
 319 \end{codeblock}
 320
 321 Sledeća dva metoda traže trojke sa nekim specifičnim osobinama.
 322
 323 \begin{codeblock}
 324 MODULE Trojke4;
 325 (* Pitagorine trojke kod kojih je razlika
 326    izmedju katete i hipotenuze tacno 1 *)
 327 FROM InOut IMPORT WriteString, WriteLn, WriteCard;
 328 CONST
 329   Gr = 10;
 330 VAR
 331   a, b, c, m, n : CARDINAL;
 332 BEGIN
 333   FOR m := 2 TO Gr DO
 334     n := m - 1;
 335     a := 2*m*n;
 336     b := m*m - n*n;
 337     c := m*m + n*n;
 338     WriteLn;
 339     WriteString('a = ');
 340     WriteCard(a,2);
 341     WriteString(', b = ');
 342     WriteCard(b,2);
 343     WriteString(', c = ');
 344     WriteCard(c,2)
 345   END
 346 END Trojke4.
 347 \end{codeblock}
 348
 349 \begin{lstlisting}[style=codeblock]
 350 MODULE Trojke5;
 351 (* Pitagorine trojke kod kojih je razlika
 352    izmedju kateta jedan *)
 353 FROM InOut IMPORT WriteString, WriteLn, WriteCard;
 354 CONST
 355   Gr = 7;
 356 VAR
 357   a, b, c, m, n, w, i, temp : CARDINAL;
 358 BEGIN
 359   w := 1;
 360   n := 0;
 361   FOR i := 1 TO Gr DO
 362     m := n + w;
 363     a := 2*m*n;
 364     b := m*m - n*n;
 365     c := m*m + n*n;
 366     WriteLn;
 367     WriteString('a = ');
 368     WriteCard(a,2);
 369     WriteString(', b = ');
 370     WriteCard(b,2);
 371     WriteString(', c = ');
 372     WriteCard(c,2);
 373     temp := w;
 374     w := 3*w + 4*n;
 375     n := 2*temp + 3*n
 376   END
 377 END Trojke5.
 378 \end{lstlisting}
 379
 380
 381 \subsection[Zadatak: Maksimalna suma susednih elemenata u
 382 nizu]{Zadatak: Maksimalna suma proizvoljnog broja susednih elemenata u
 383   nizu celih brojeva}
 384
 385 \begin{lstlisting}[style=codeblock]
 386 MODULE MaxNiza1;
 387 (* Prvo resenje. Brute Force: O(n^3)  *)
 388 FROM InOut IMPORT WriteString,ReadInt,
 389            WriteInt,WriteCard,WriteLn;
 390 CONST
 391   N = 10;
 392 TYPE
 393   Interval = [1..N];
 394 VAR
 395   Max, Suma : INTEGER;
 396   d,g,i,Ood,Doo : Interval;
 397   X : ARRAY Interval OF INTEGER;
 398 BEGIN
 399   WriteString(' Unesite niz X ');
 400   WriteLn;
 401   FOR i := 1 TO N DO
 402     ReadInt(X[i]);
 403     WriteLn
 404   END;
 405   Max := 0;
 406   FOR d := 1 TO N DO
 407     FOR g := 1 TO N DO
 408       Suma := 0;
 409       FOR i := d TO g DO
 410         Suma := Suma + X[i]
 411       END;
 412       IF Suma > Max THEN
 413         Max := Suma;
 414         Ood := d;
 415         Doo := g
 416       END
 417     END
 418   END;
 419   WriteLn;
 420   WriteString(' Maksimum je ');
 421   WriteInt(Max,3);
 422   WriteString(' u intervalu od ');
 423   WriteCard(Ood,3);
 424   WriteString(' do ');
 425   WriteCard(Doo,3)
 426 END MaxNiza1.
 427
 428 MODULE MaxNiza2;
 429 (* Drugo resenje: O(n^2).
 430    Koristi se cinjenica da je suma X[d..g]
 431    izracunljiva iz X[d..g-1].  *)
 432 FROM InOut IMPORT WriteString,ReadInt,
 433            WriteInt,WriteCard,WriteLn;
 434 CONST
 435   N = 10;
 436 TYPE
 437   Interval = [1..N];
 438 VAR
 439   Max, Suma : INTEGER;
 440   d,g,i,Ood,Doo : Interval;
 441   X : ARRAY Interval OF INTEGER;
 442 BEGIN
 443   WriteString(' Unesite niz X ');
 444   WriteLn;
 445   FOR i := 1 TO N DO
 446     ReadInt(X[i]);
 447     WriteLn
 448   END;
 449   Max := 0;
 450   FOR d := 1 TO N DO
 451     Suma := 0;
 452     FOR g := d TO N DO
 453       Suma := Suma + X[g];
 454       IF Suma > Max THEN
 455         Max := Suma;
 456         Ood := d;
 457         Doo := g
 458       END
 459     END
 460   END;
 461   WriteLn;
 462   WriteString(' Maksimum je ');
 463   WriteInt(Max,3);
 464   WriteString(' u intervalu od ');
 465   WriteCard(Ood,3);
 466   WriteString(' do ');
 467   WriteCard(Doo,3)
 468 END MaxNiza2.
 469 \end{lstlisting}
 470
 471 \begin{codeblock}
 472 MODULE MaxNiza3;
 473 (* Trece resenje: O(n^2).
 474    Koristi pomocni niz u kome je na i-tom mestu
 475    suma podniza x[1..i] *)
 476 FROM InOut IMPORT WriteString,ReadInt,
 477            WriteInt,WriteCard,WriteLn;
 478 CONST
 479   N = 10;
 480 TYPE
 481   Interval = [1..N];
 482 VAR
 483   Max, Suma : INTEGER;
 484   d,g,i,Ood,Doo : Interval;
 485   X : ARRAY Interval OF INTEGER;
 486   Pom : ARRAY [0..N] OF INTEGER;
 487 BEGIN
 488   WriteString(' Unesite niz X ');
 489   WriteLn;
 490   FOR i := 1 TO N DO
 491     ReadInt(X[i]);
 492     WriteLn
 493   END;
 494   Pom[0] := 0;
 495   FOR i := 1 TO N DO
 496     Pom[i] := Pom[i-1] + X[i]
 497   END;
 498   Max := 0;
 499   FOR d := 1 TO N DO
 500     FOR g := d TO N DO
 501       Suma := Pom[g] - Pom[d-1];
 502       IF Suma > Max THEN
 503         Max := Suma;
 504         Ood := d;
 505         Doo := g
 506       END
 507     END
 508   END;
 509   WriteLn;
 510   WriteString(' Maksimum je ');
 511   WriteInt(Max,3);
 512   WriteString(' u intervalu od ');
 513   WriteCard(Ood,3);
 514   WriteString(' do ');
 515   WriteCard(Doo,3)
 516 END MaxNiza3.
 517 \end{codeblock}
 518
 519 \begin{codeblock}
 520 MODULE MaxNiza4;
 521 (* Cetvrto resenje. Najbolje moguce: O(n)  *)
 522 FROM InOut IMPORT WriteString,ReadInt,
 523            WriteInt,WriteCard,WriteLn;
 524 CONST
 525   N = 10;
 526 TYPE
 527   Interval = [1..N];
 528 VAR
 529   Max, MaxDovde : INTEGER;
 530   i,d,Ood,Doo : Interval;
 531   X : ARRAY Interval OF INTEGER;
 532 BEGIN
 533   WriteString(' Unesite niz X ');
 534   WriteLn;
 535   FOR i := 1 TO N DO
 536     ReadInt(X[i]);
 537     WriteLn
 538   END;
 539   Max := 0;
 540   MaxDovde := 0;
 541   FOR i := 1 TO N DO
 542     IF MaxDovde = 0 THEN
 543       d := i
 544     END;
 545     MaxDovde := MaxDovde + X[i];
 546     IF MaxDovde < 0 THEN
 547       MaxDovde := 0
 548     END;
 549     IF MaxDovde > Max THEN
 550       Ood := d;
 551       Doo := i;
 552       Max := MaxDovde
 553     END
 554   END;
 555   WriteLn;
 556   WriteString(' Maksimum je ');
 557   WriteInt(Max,3);
 558   WriteString(' u intervalu od ');
 559   WriteCard(Ood,3);
 560   WriteString(' do ');
 561   WriteCard(Doo,3)
 562 END MaxNiza4.
 563 \end{codeblock}
 564
 565 \section{Stringovi}
 566
 567
 568 Stringovi -- odnosno nizovi znakova -- ne postoje kao ugrađeni tip u
 569 jeziku Modula 2. Ovo daje slobodu da se niz znakova definiše na dužinu
 570 najadekvatniju za konkretnu primenu. U opštem slučaju definišemo npr:
 571 \begin{codeblock}
 572   TYPE
 573      String = ARRAY [1..30] OF CHAR;
 574 \end{codeblock}
 575
 576 Operacije nad stringovima se najčešće uvoze iz modula \kod{Str}. One
 577 sve prihvataju \emph{otvorene nizove znakova} (strukture definisane sa
 578 \kod{ARRAY OF CHAR}), tako da im se može proslediti niz proizvoljne
 579 dužine.
 580
 581 Određivanje stvarne dužine stringa (tj koliko od maksimalnog
 582 kapaciteta niza je zapravo zauzeto sadržajem) se može izvesti na
 583 sledeći način:
 584 \begin{codeblock}
 585      duzina := Length(str)
 586 \end{codeblock}
 587
 588 Leksikografsko poređenje dva stringa se ne može vršiti standardnim
 589 operatorima kao što su \kod{< > =}. Ovo je delom zato što se radi o
 590 nizovima, a delom i zato što se ne vidi direktno koji deo niza je
 591 popunjen stvarnim sadržajem. Za ovo se koristi komanda \kod{Compare},
 592 koja prihvata dva stringa kao parametre, a vraća broj koji predstavlja
 593 njihov odnos. Taj broj će biti 0 ako su stringovi jednaki, veći
 594 od nule ako je prvi string ``veći'', i manji od nule ako je prvi
 595 string ``manji''. Ovo se lako pamti kad primetimo da je odnos
 596 između \kod{Compare} i 0 isti kao i između prvog i drugog stringa.
 597
 598 \begin{codeblock}
 599   IF    Compare(str1, str2) > 0 THEN
 600      WriteString("Prvi string je veci");
 601   ELSIF Compare(str1, str2) < 0 THEN
 602      WriteString("Prvi string je manji");
 603   ELSE (* moraju biti jednaki *)
 604      WriteString("Jednaki su");
 605   END;
 606 \end{codeblock}
 607
 608 Postoji i modul \kod{Strings} koji ima nešto drugačije definisane
 609 procedure, no na njih se sada nećemo fokusirati.
 610
 611 \section{Rad sa fajlovima}
 612
 613 \subsection{Modul FIO}
 614
 615 U ovom modulu je definisan tip \kod{File}, koji predstavlja jedan fajl
 616 sa kojim radimo. Da bi ga koristili moramo ga uvesti u program (isto
 617 kao što uvozimo i komande).
 618
 619 \begin{quote}U primerima se pretpostavlja da je ``f'' tipa \kod{File}, ``str'' niz
 620 znakova, ``i'' tipa \kod{INTEGER}, ``c'' tipa \kod{CARDINAL} i ``ch''
 621 tipa \kod{CHAR}. Dodatna promenljiva ``n'' tipa \kod{INTEGER} služi za
 622 formatiranje slično kao u modulu \kod{InOut}.
 623 \end{quote}
 624
 625 Promenljiva tipa \kod{File} se mora vezati za neki fajl
 626 jednom od sledećih komandi:
 627 \begin{itemize}
 628 \item \kod{f := Open(str);} -- otvara se postojeci fajl za čitanje\\
 629 \item \kod{f := Create(str);} -- kreira se fajl za pisanje\\
 630 \item \kod{f := Append(str);} -- otvara se postojeći fajl za
 631   dopisivanje na kraj
 632 \end{itemize}
 633
 634 Po završetku rada fajl se mora zatvoriti, u našem primeru to bi bilo
 635 \kod{Close(f);}
 636
 637 Procedure za čitanje i pisanje su vrlo slične onima iz modula
 638 \kod{IO}, osim što imaju dodatni parametar „\kod{f}“ koji označava
 639 fajl sa kojim se radi.
 640 \begin{itemize}
 641 \item \kod{RdStr(f,str)} -- učitava ceo red u string str\\
 642 \item   \kod{RdItem(f,str)} -- učitava jednu reč u string str (učitava znakove iz fajla dok ne naiđe na separator)\\
 643 \item   \kod{i:= RdInt(f); c:= RdCard(f)} -- učitava broj, koji se dobija kao rezultat procedure\\
 644 \item   \kod{ch:= RdChar(f)} -- vraća jedan znak iz fajla
 645 \end{itemize}
 646
 647 Analogne su i procedure za pisanje različitih tipova u fajl:
 648 \begin{itemize}
 649 \item \kod{WrStr(f,str); WrInt(f,i,n);}\ \kod{WrCard(f,c,n);}\
 650   \kod{WrChar(f,ch);}
 651 \end{itemize}
 652
 653
 654 Prelom reda se eksplicitno upisuje u fajl komandom \kod{WrLn(f);}.
 655
 656 Da bi odredili da li smo stigli do kraja fajla možemo koristiti
 657 \kod{EOF}. U pitanju je logička promenljiva koja se uvozi iz modula
 658 FIO kao bilo kakva normalna komanda. Ona označava da li smo poslednjom
 659 operacijom čitanja stigli do kraja fajla.  Ne menja joj se vrednost
 660 pri operacijama otvaranja i zatvaranja fajlova, odnosno neće se pri
 661 tome resetovati na \kod{FALSE}, pa na ovo treba obratiti pažnju pri
 662 radu.
 663
 664 \subsection{Zadatak: ispis sadržaja fajla na ekran}
 665
 666 Potrebno je sve redove iz fajla učitati i ispisati ih na ekran.
 667
 668 \begin{lstlisting}[style=codeblock]
 669 MODULE ispis;
 670 FROM FIO IMPORT File, Open, Close, EOF, RdStr;
 671 FROM InOut IMPORT WriteString, WriteLn, ReadString;
 672
 673 PROCEDURE ispisF(ime: ARRAY OF CHAR);
 674 VAR
 675   f:File;
 676   s : ARRAY[1..100] OF CHAR;
 677 BEGIN
 678   f:=Open(ime);
 679   EOF := FALSE;
 680   WHILE NOT EOF DO
 681       RdStr(f,s);
 682       WriteString(s);
 683       WriteLn;
 684   END;
 685   Close(f);
 686 END ispisF;
 687
 688 VAR
 689   ime: ARRAY[1..100] OF CHAR;
 690 BEGIN
 691   WriteString("unesite ime fajla:");
 692   ReadString(ime);
 693   ispisF(ime);
 694 END ispis.
 695 \end{lstlisting}
 696
 697 \subsection{Zadatak: spisak studenata}
 698
 699 Napraviti program koji iz fajla učitava podatke o studentima, dodaje
 700 novog studenta u spisak i snima fajl.  U fajlu se u svakom redu nalazi
 701 podatak o jednom studentu, redom prezime, ime i godina rođenja,
 702 razdvojeni razmacima.
 703
 704 \begin{lstlisting}[style=codeblock]
 705 MODULE nizslog;
 706 FROM InOut IMPORT WriteString, WriteLn,
 707      WriteCard, ReadCard, ReadString;
 708 FROM FIO IMPORT File, Open, Create, Close, EOF,
 709     RdItem, RdCard, WrStr, WrCard, WrLn;
 710 FROM Str IMPORT Compare;
 711
 712 CONST
 713     MaxStud = 100;
 714 TYPE
 715     String = ARRAY[1..30] OF CHAR;
 716     Student = RECORD
 717         ime, prez: String;
 718         god: CARDINAL;
 719     END;
 720     Studenti = ARRAY[1..MaxStud] OF Student;
 721
 722 PROCEDURE UcitajF(fajl:String;
 723           VAR spisak: Studenti; VAR n:CARDINAL);
 724 VAR
 725     f:File;
 726 BEGIN
 727     n:=0;
 728     f:= Open(fajl);
 729     EOF := FALSE;
 730     WHILE NOT EOF DO
 731         INC(n);
 732         RdItem(f, spisak[n].prez);
 733         RdItem(f, spisak[n].ime);
 734         spisak[n].god := RdCard(f);
 735     END;
 736     Close(f);
 737 END UcitajF;
 738
 739 PROCEDURE Ispisi(spisak:Studenti; n:CARDINAL);
 740 VAR
 741     i: CARDINAL;
 742 BEGIN
 743     FOR i:=1 TO n DO
 744         WriteString(spisak[i].prez);
 745         WriteString(" ");
 746         WriteString(spisak[i].ime);
 747         WriteString(" ");
 748         WriteCard(spisak[i].god,1);
 749         WriteLn;
 750     END;
 751 END Ispisi;
 752
 753 PROCEDURE IspisiF(fajl:String;
 754           spisak:Studenti; n:CARDINAL);
 755 VAR
 756     f:File;
 757     i: CARDINAL;
 758 BEGIN
 759     IF (n>0) AND (n<=MaxStud) THEN
 760         f:=Create(fajl);
 761         (* pravimo takav fajl da ne
 762            postoji zadnji prazan red *)
 763         FOR i:=1 TO n-1 DO
 764             WrStr(f,spisak[i].prez);
 765             WrStr(f," ");
 766             WrStr(f,spisak[i].ime);
 767             WrStr(f," ");
 768             WrCard(f,spisak[i].god,1);
 769             WrLn(f);
 770         END;
 771         WrStr(f,spisak[n].prez);
 772         WrStr(f," ");
 773         WrStr(f,spisak[n].ime);
 774         WrStr(f," ");
 775         WrCard(f,spisak[n].god,1);
 776         Close(f);
 777     END;
 778 END IspisiF;
 779
 780 PROCEDURE NoviStudent(VAR spisak:Studenti;
 781                       VAR n:CARDINAL);
 782 VAR
 783     stud,temp:Student;
 784     i:CARDINAL;
 785     dodaj:BOOLEAN;
 786 BEGIN
 787     IF n<MaxStud THEN
 788         WriteString("Prezime novog studenta?");
 789         ReadString(stud.prez);
 790         WriteString("Ime novog studenta?");
 791         ReadString(stud.ime);
 792         WriteString("Godina rodjenja");
 793         WriteString("novog studenta?");
 794         ReadCard(stud.god);
 795         (* proverimo da li vec postoji *)
 796         i:=1;
 797         dodaj := TRUE;
 798         WHILE (i<=n) AND dodaj DO
 799             temp := spisak[i];
 800             IF (temp.god = stud.god) &
 801               (Compare(temp.prez,stud.prez)=0) &
 802               (Compare(temp.ime,stud.ime)=0) THEN
 803                 dodaj:=FALSE;
 804             END;
 805             INC(i);
 806         END;
 807         IF dodaj THEN
 808             INC(n);
 809             spisak[n]:=stud;
 810         ELSE
 811             WriteString("podaci vec postoje!");
 812         END;
 813     ELSE
 814         WriteString("popunjen kapacitet!");
 815     END;
 816 END NoviStudent;
 817
 818 VAR
 819     spisak : Studenti;
 820     fajl:String;
 821     n:CARDINAL;
 822 BEGIN
 823     fajl:="studenti.txt";
 824     UcitajF(fajl, spisak, n);
 825     Ispisi(spisak, n);
 826     NoviStudent(spisak,n);
 827     IspisiF(fajl, spisak, n);
 828 END nizslog.
 829 \end{lstlisting}
 830
 831 \section{Liste i pokazivači}
 832
 833 Za rad sa pokazivačima je potrebno iz modula \kod{Storage} uvesti procedure
 834 \kod{ALLOCATE} i \kod{DEALLOCATE}. U kodu se tada mogu koristiti i njihovi
 835 skraćeni oblici \kod{NEW} i \kod{DISPOSE}.
 836
 837 \subsection{Zadatak: Formiranje, štampanje i brisanje listi}
 838
 839
 840 \begin{lstlisting}[style=codeblock]
 841 MODULE liste;
 842 FROM InOut IMPORT WriteString, WriteLn, WriteInt,
 843         ReadInt, ReadCard;
 844 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
 845 TYPE
 846   brojevi = POINTER TO brojSlog;
 847   brojSlog = RECORD
 848       info:INTEGER;
 849       veza:brojevi;
 850   END;
 851 VAR
 852   n,i:CARDINAL;
 853   lista : brojevi;
 854   br:INTEGER;
 855
 856 PROCEDURE DodajPoc(VAR lista:brojevi; br:INTEGER);
 857 (* dodaje broj br na pocetak liste *)
 858 VAR
 859   temp:brojevi;
 860 BEGIN
 861   NEW(temp);
 862   temp^.info := br;
 863   temp^.veza := lista;
 864   lista := temp;
 865 END DodajPoc;
 866
 867 PROCEDURE Stampaj(lista:brojevi);
 868 VAR
 869   temp:brojevi;
 870 BEGIN
 871   temp:=lista;
 872   WHILE temp # NIL DO
 873       WriteInt(temp^.info,0);
 874       WriteLn;
 875       temp := temp^.veza;
 876   END;
 877 END Stampaj;
 878
 879 PROCEDURE Unisti(VAR lista:brojevi);
 880 VAR
 881   temp:brojevi;
 882 BEGIN
 883   temp:=lista;
 884   WHILE temp # NIL DO
 885         lista:=lista^.veza;
 886         DISPOSE(temp);
 887         temp:=lista;
 888   END;
 889 END Unisti;
 890
 891 BEGIN
 892   lista := NIL;
 893   WriteString('unesite n (broj brojeva): ');
 894   ReadCard(n);
 895   WriteString('unesite brojeve: ');
 896   WriteLn;
 897   FOR i:= 1 TO n DO
 898       ReadInt(br);
 899       DodajPoc(lista,br);
 900   END;
 901   WriteString('sadrzaj liste:');
 902   WriteLn;
 903   Stampaj(lista);
 904   Unisti(lista);
 905   WriteString('memorija je oslobodjena');
 906   WriteLn;
 907 END liste.
 908 \end{lstlisting}
 909
 910 Alternativno je poziv \kod{DodajPoc} moguće zameniti pozivom jedne od
 911 sledeće dve procedure čime se dobija dodavanje elementa na kraj liste,
 912 ili kreiranje sortirane liste:
 913
 914 \begin{lstlisting}[style=codeblock]
 915 PROCEDURE DodajKraj(VAR lista:brojevi; br:INTEGER);
 916 (* dodaje element na kraj liste *)
 917 VAR
 918   tekuci, temp :brojevi;
 919 BEGIN
 920   NEW(temp);
 921   temp^.info := br;
 922   temp^.veza := NIL;
 923   IF lista = NIL THEN
 924      (* prazna lista *)
 925      lista:=temp;
 926   ELSE
 927      tekuci := lista;
 928      WHILE tekuci^.veza#NIL DO
 929         tekuci:=tekuci^.veza;
 930      END;
 931      tekuci^.veza := temp;
 932   END;
 933 END DodajKraj;
 934
 935 PROCEDURE DodajSort(VAR lista:brojevi; br:CARDINAL);
 936 (* dodaje broj tako da lista ostane sortirana
 937    (podrazumeva se da je vec sortirana) *)
 938 VAR
 939   temp, tekuci : brojevi;
 940 BEGIN
 941   NEW(temp);
 942   temp^.info:=br;
 943   temp^.veza:=NIL;
 944   IF (lista = NIL) OR (lista^.info>=br) THEN
 945   (*prazna lista ili na pocetak*)
 946     temp^.veza:=lista;
 947     lista := temp;
 948   ELSE
 949   (*negde u listi*)
 950     tekuci:= lista;
 951     WHILE (tekuci^.veza # NIL) AND
 952           (tekuci^.veza^.info<=br) DO
 953       tekuci:=tekuci^.veza;
 954     END;
 955     temp^.veza := tekuci^.veza;
 956     tekuci^.veza:=temp;
 957   END;
 958 END DodajSort;
 959 \end{lstlisting}
 960
 961 \subsection{Zadatak: Prikaz osnovih operacija nad listama}
 962
 963 \begin{lstlisting}[style=codeblock]
 964 MODULE liste2;
 965 FROM InOut IMPORT WriteString, WriteLn,
 966            WriteCard, ReadCard;
 967 FROM IO IMPORT RdKey;
 968 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
 969 TYPE
 970   skupZn = SET OF CHAR;
 971   brojevi = POINTER TO brojSlog;
 972   brojSlog = RECORD
 973       info:CARDINAL;
 974       veza:brojevi;
 975   END;
 976 VAR
 977   lista : brojevi;
 978   menu,prazno:CHAR;
 979
 980 PROCEDURE DodajPoc(VAR lista:brojevi; br:INTEGER);
 981 (* dodaje broj pom na pocetak liste *)
 982 VAR
 983   temp:brojevi;
 984 BEGIN
 985   (* kreiramo novi element *)
 986   NEW(temp);
 987   temp^.info := br;
 988   (* treba da pokazuje na ostatak liste *)
 989   temp^.veza := lista;
 990   (* pocetak liste je novi element *)
 991   lista := temp;
 992 END DodajPoc;
 993
 994 PROCEDURE Unos(VAR lista:brojevi);
 995 (* dodaje n brojeva u listu *)
 996 VAR
 997   n,i,br:CARDINAL;
 998 BEGIN
 999   WriteString('unesite n (broj brojeva): ');
1000   ReadCard(n);
1001   FOR i:= 1 TO n DO
1002       WriteString("unesite broj ");
1003       WriteCard(i,0);
1004       WriteString(": ");
1005       ReadCard(br);
1006       DodajPoc(lista,br);
1007   END;
1008 END Unos;
1009
1010 (* -- procedure za stampu -- *)
1011
1012 PROCEDURE Stampaj(lista:brojevi);
1013 (* stampa sadrzaj liste na ekran *)
1014 VAR
1015   temp:brojevi;
1016 BEGIN
1017   WriteLn;
1018   WriteString("Sadrzaj liste:");
1019   WriteLn;
1020   temp:=lista;
1021   WHILE temp # NIL DO
1022       WriteCard(temp^.info,0);
1023       WriteLn;
1024       temp := temp^.veza;
1025   END;
1026 END Stampaj;
1027
1028 PROCEDURE StampajK(VAR lista:brojevi);
1029 (* stampa k-ti element (k unosi korisnik) *)
1030 VAR
1031   temp:brojevi;
1032   k,brojac:CARDINAL;
1033 BEGIN
1034   WriteString("unesite redni broj elementa:");
1035   ReadCard(k);
1036   temp:=lista;
1037   brojac := 1;
1038   WHILE (temp# NIL) AND (k>brojac) DO
1039     temp:=temp^.veza;
1040     INC(brojac);
1041   END;
1042   IF (temp#NIL) THEN
1043     WriteCard(temp^.info,2);
1044   ELSE
1045     WriteString("greska! - ne postoji element");
1046     WriteString(" u listi sa rednim brojem ");
1047     WriteCard(k,2);
1048   END;
1049   WriteLn();
1050 END StampajK;
1051
1052 PROCEDURE StampajMinimum(VAR lista:brojevi);
1053 (* nalazi i stampa minimalni element liste *)
1054 VAR
1055   temp:brojevi;
1056   min:CARDINAL;
1057 BEGIN
1058   IF (lista=NIL) THEN
1059     WriteString("prazna lista!");
1060   ELSE
1061     min:=lista^.info;
1062     temp:=lista^.veza;
1063     WHILE temp # NIL DO
1064       IF temp^.info < min THEN
1065         min := temp^.info;
1066       END;
1067       temp := temp^.veza;
1068     END;
1069     WriteString("Minimalni element liste je ");
1070     WriteCard(min,0);
1071   END;
1072   WriteLn;
1073 END StampajMinimum;
1074
1075 (* -- pomocne procedure, bez ispisa  -- *)
1076
1077 PROCEDURE UListi(lista:brojevi;
1078                  br: CARDINAL):BOOLEAN;
1079 (* vraca da li se 'br' nalazi u listi 'lista' *)
1080 VAR
1081   temp:brojevi;
1082 BEGIN
1083   temp:=lista;
1084   WHILE (temp # NIL) AND (temp^.info # br) DO
1085     (* dok ne dodjemo do kraja liste
1086        ili ne nadjemo broj *)
1087       temp := temp^.veza;
1088   END;
1089   IF temp#NIL THEN
1090     (* znaci da nismo na kraju liste,
1091        tj da je nadjen broj *)
1092     RETURN TRUE;
1093   ELSE (* temp = NIL *)
1094     RETURN FALSE;
1095   END;
1096 END UListi;
1097
1098 PROCEDURE IzbaciIzListe(VAR lista:brojevi;
1099                         br: CARDINAL):BOOLEAN;
1100 (* izbacuje broj 'br' iz liste, naravno ako
1101    postoji i vraca da li je operacija uspesno
1102    obavljena *)
1103 VAR
1104   temp,prethodni:brojevi;
1105 BEGIN
1106   (* proverimo da li je prvi element *)
1107   IF (lista # NIL) AND (lista^.info = br) THEN
1108     temp:=lista;
1109     lista :=lista^.veza;
1110     DISPOSE(temp);
1111     RETURN TRUE;
1112   ELSE
1113   (* trazimo u ostatku liste *)
1114     temp:=lista;
1115     prethodni:=NIL;
1116     WHILE (temp # NIL) AND (temp^.info # br) DO
1117         (* dok ne dodjemo do kraja liste
1118            ili ne nadjemo broj *)
1119         prethodni:=temp;
1120         temp := temp^.veza;
1121     END;
1122     IF temp#NIL THEN
1123       (* znaci da nismo na kraju liste,
1124          odnosno da smo nasli broj *)
1125       (* prevezemo listu oko elementa *)
1126       prethodni^.veza:=temp^.veza;
1127       DISPOSE(temp);
1128       RETURN TRUE;
1129     ELSE
1130       RETURN FALSE;
1131     END;
1132   END;
1133 END IzbaciIzListe;
1134
1135 (* - procedure sa interakcijom sa korisnikom - *)
1136
1137 PROCEDURE IzbacivanjeEl(VAR lista:brojevi);
1138 (* izbacuje uneti broj iz liste koristeci proceduru IzbaciIzListe *)
1139 VAR
1140   br:CARDINAL;
1141 BEGIN
1142   WriteString("unesite broj za izbacivanje: ");
1143   ReadCard(br);
1144   IF IzbaciIzListe(lista,br) THEN
1145     WriteString("broj je izbacen iz liste");
1146   ELSE
1147     WriteString("greska! - broj ne postoji");
1148   END;
1149   WriteLn;
1150 END IzbacivanjeEl;
1151
1152 PROCEDURE IzbacivanjeK(VAR lista:brojevi);
1153 (* izbacuje k-ti element iz liste *)
1154 VAR
1155   temp,tekuci:brojevi;
1156   k,brojac:CARDINAL;
1157 BEGIN
1158   IF lista=NIL THEN
1159     WriteString("lista je prazna, nema ");
1160     WriteString("elemenata za izbacivanje");
1161   ELSE
1162     WriteString("unesite redni broj elementa");
1163     WriteString(" koji zelite izbaciti:");
1164     ReadCard(k);
1165     IF k=1 THEN (*izbacivanje prvog *)
1166       temp:=lista;
1167       lista := lista^.veza;
1168       DISPOSE(temp);
1169     ELSE
1170       tekuci := lista;
1171       brojac := 2; (*gledamo jedan unapred*)
1172       WHILE (tekuci^.veza# NIL) AND (k>brojac) DO
1173         (* idemo kroz listu do k-tog el *)
1174         tekuci:=tekuci^.veza;
1175         INC(brojac);
1176       END;
1177       IF (tekuci^.veza#NIL) THEN
1178          (* pamtimo element za brisanje *)
1179          temp:=tekuci^.veza;
1180          (* prevezujemo listu oko njega*)
1181          tekuci^.veza:=tekuci^.veza^.veza;
1182          DISPOSE(temp);
1183       ELSE
1184         WriteString("greska! - ne postoji el ");
1185         WriteString("u listi sa rednim brojem ");
1186         WriteCard(k,2);
1187       END;
1188       WriteLn();
1189     END;
1190   END;
1191 END IzbacivanjeK;
1192
1193 PROCEDURE Pretraga(lista:brojevi);
1194 (* provera da li se uneti broj nalazi u listi *)
1195 VAR
1196   br:CARDINAL;
1197 BEGIN
1198   WriteString("unesite trazeni broj");
1199   ReadCard(br);
1200   IF UListi(lista,br) THEN
1201     WriteString("broj postoji u listi");
1202   ELSE
1203     WriteString("broj ne postoji u listi");
1204   END;
1205   WriteLn;
1206 END Pretraga;
1207
1208 (* -- oslobadjanje memorije -- *)
1209
1210 PROCEDURE Unisti(VAR lista:brojevi);
1211 VAR
1212   temp:brojevi;
1213 BEGIN
1214   temp:=lista;
1215   WHILE temp # NIL DO
1216         lista:=lista^.veza;
1217         DISPOSE(temp);
1218         temp:=lista;
1219   END;
1220 END Unisti;
1221
1222 BEGIN
1223   (* pocinjemo od prazne liste *)
1224   lista := NIL;
1225   REPEAT
1226      WriteLn;
1227      WriteString("Ilustracija rada sa");
1228      WriteString(" listama brojeva");
1229      WriteLn;
1230      WriteString("=============================");
1231      WriteLn;
1232      WriteString("s - stampa");WriteLn;
1233      WriteString("u - unos");WriteLn;
1234      WriteString("i - izbacivanje br iz liste");
1235      WriteLn;
1236      WriteString("e - izbacivanje k-tog el.");
1237      WriteLn;
1238      WriteString("k - stampanje k-tog elementa");
1239      WriteLn;
1240      WriteString("m - minimalni broj u listi");
1241      WriteLn;
1242      WriteString("p - pretraga el. u listi");
1243      WriteLn;
1244      WriteLn;
1245      WriteString("q - kraj rada (quit)");WriteLn;
1246       REPEAT
1247         menu := CAP(RdKey());
1248       UNTIL menu IN skupZn{'S','U','E','I',
1249                            'M','K','P','Q'};
1250       IF menu#'Q' THEN
1251         CASE menu OF
1252          'S' : Stampaj(lista);|
1253          'U' : Unos(lista);|
1254          'I' : IzbacivanjeEl(lista);|
1255          'E' : IzbacivanjeK(lista);|
1256          'K' : StampajK(lista); |
1257          'M' : StampajMinimum(lista); |
1258          'P' : Pretraga(lista);|
1259         END;
1260         WriteLn;
1261         WriteString("--- pritisnite bilo koji ");
1262         WriteString("taster za povratak u meni");
1263         prazno:=RdKey();
1264       ELSE
1265         WriteString("Kraj rada")
1266       END;
1267       WriteLn;
1268   UNTIL menu='Q';
1269   Unisti(lista);
1270 END liste2.
1271 \end{lstlisting}
1272
1273
1274 \subsection{Zadatak: Prikaz operacija nad listama sa jedinstvenim ključem}
1275
1276 \begin{lstlisting}[style=codeblock]
1277 MODULE Radnici;
1278
1279 FROM InOut IMPORT WriteString, ReadString,
1280            WriteLn, WriteCard, ReadCard, Done;
1281 FROM IO IMPORT RdKey;
1282 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1283
1284 TYPE
1285   skupZn = SET OF CHAR;
1286   str = ARRAY [1..20] OF CHAR;
1287   radnici = POINTER TO slog;
1288   slog = RECORD
1289            ime, prez : str;
1290            broj : CARDINAL;
1291            sled : radnici
1292          END;
1293 VAR
1294   meni, pom : CHAR;
1295   rad : radnici;
1296
1297   PROCEDURE Clear();
1298   VAR
1299     br: CARDINAL;
1300   BEGIN
1301     FOR br:=1 TO 100 DO
1302       WriteLn;
1303     END;
1304   END Clear;
1305
1306   PROCEDURE Spisak(rad : radnici);
1307   BEGIN
1308     WHILE rad # NIL DO
1309       WriteString(rad^.ime);
1310       WriteString(' ');
1311       WriteString(rad^.prez);
1312       WriteCard(rad^.broj, 8);
1313       WriteLn;
1314       rad := rad^.sled
1315     END
1316   END Spisak;
1317
1318   PROCEDURE Zaposli(VAR rad : radnici);
1319   VAR
1320     novi, tek : radnici;
1321     nadjen : BOOLEAN;
1322   BEGIN
1323     NEW(novi);
1324     REPEAT
1325       WriteString('Ime, prezime i jedinstveni');
1326       WriteString(' broj novog radnika: ');
1327       WriteLn;
1328       ReadString(novi^.ime);
1329       ReadString(novi^.prez);
1330       ReadCard(novi^.broj);
1331       nadjen := FALSE;
1332       tek := rad;
1333       WHILE NOT nadjen AND (tek # NIL) AND
1334             (tek^.broj <= novi^.broj) DO
1335         IF novi^.broj = tek^.broj THEN
1336           nadjen := TRUE
1337         ELSE
1338           tek := tek^.sled
1339         END
1340       END
1341     UNTIL Done AND NOT nadjen;
1342     IF (rad = NIL) OR (novi^.broj<rad^.broj) THEN
1343       novi^.sled := rad;
1344       rad := novi
1345     ELSE
1346       tek := rad;
1347       WHILE (tek^.sled # NIL) AND
1348             (tek^.sled^.broj < novi^.broj) DO
1349         tek := tek^.sled
1350       END;
1351       novi^.sled := tek^.sled;
1352       tek^.sled := novi
1353     END
1354   END Zaposli;
1355
1356   PROCEDURE Otpusti(VAR rad : radnici);
1357   VAR
1358     tek, pom : radnici;
1359     br : CARDINAL;
1360   BEGIN
1361     REPEAT
1362       WriteLn;
1363       WriteString('Unesite redni broj radnika:');
1364       ReadCard(br)
1365     UNTIL Done;
1366     WriteLn;
1367     IF rad = NIL THEN
1368       WriteString('Greska.')
1369     ELSIF br = rad^.broj THEN
1370       pom := rad;
1371       rad := rad^.sled;
1372       DISPOSE(pom)
1373     ELSE
1374       tek := rad;
1375       WHILE (tek^.sled # NIL) AND
1376             (tek^.sled^.broj < br) DO
1377         tek := tek^.sled
1378       END;
1379       IF (tek^.sled = NIL) OR
1380          (tek^.sled^.broj > br) THEN
1381         WriteString('Greska.')
1382       ELSE
1383         pom := tek^.sled;
1384         tek^.sled := tek^.sled^.sled;
1385         DISPOSE(pom)
1386       END
1387     END
1388   END Otpusti;
1389
1390   PROCEDURE Inform(rad : radnici);
1391   VAR
1392     br : CARDINAL;
1393   BEGIN
1394     REPEAT
1395       WriteLn;
1396       WriteString('Unesite redni broj radnika:');
1397       ReadCard(br)
1398     UNTIL Done;
1399     WriteLn;
1400     WHILE (rad # NIL) AND (rad^.broj < br) DO
1401       rad := rad^.sled
1402     END;
1403     IF (rad = NIL) OR (rad^.broj # br) THEN
1404       WriteString('Greska.')
1405     ELSE
1406       WriteString(rad^.ime);
1407       WriteString(' ');
1408       WriteString(rad^.prez)
1409     END
1410   END Inform;
1411
1412   PROCEDURE Bankrot(VAR rad : radnici);
1413   VAR
1414     pom : radnici;
1415   BEGIN
1416     WHILE rad # NIL DO
1417       pom := rad;
1418       rad := rad^.sled;
1419       DISPOSE(pom)
1420     END
1421   END Bankrot;
1422
1423 BEGIN
1424   rad := NIL;
1425   REPEAT
1426     Clear;
1427     WriteString('s - spisak svih zaposlenih');
1428     WriteLn;
1429     WriteString('z - zaposljavanje radnika');
1430     WriteLn;
1431     WriteString('o - otpustanje radnika');
1432     WriteLn;
1433     WriteString('i - informacije o radniku');
1434     WriteLn;
1435     WriteString('b - bankrot firme');
1436     WriteLn;
1437     WriteString('k - kraj rada');
1438     WriteLn;
1439     REPEAT
1440       meni := RdKey();
1441     UNTIL CAP(meni) IN skupZn{'S', 'Z', 'O',
1442                               'I', 'B', 'K'};
1443     Clear;
1444     IF CAP(meni) # 'K' THEN
1445       CASE CAP(meni) OF
1446         'S' : Spisak(rad)|
1447         'Z' : Zaposli(rad)|
1448         'O' : Otpusti(rad)|
1449         'I' : Inform(rad)|
1450         'B' : Bankrot(rad)
1451       END;
1452       WriteLn;
1453       WriteString('-- pritisnite bilo koji ');
1454       WriteString('taster za nastavak --');
1455       pom := RdKey()
1456     END
1457   UNTIL CAP(meni) = 'K'
1458 END Radnici.
1459 \end{lstlisting}
1460
1461 Procedura \kod{Spisak} se može realizovati i u rekurzivnoj verziji:
1462
1463 \begin{lstlisting}[style=codeblock]
1464   PROCEDURE Spisak(rad : radnici);
1465   BEGIN
1466     IF rad # NIL THEN
1467       WriteString(rad^.ime);
1468       WriteString(' ');
1469       WriteString(rad^.prez);
1470       WriteCard(rad^.broj, 8);
1471       WriteLn;
1472       Spisak(rad^.sled)
1473     END
1474   END Spisak;
1475 \end{lstlisting}
1476
1477 \subsection[Zadatak: Dve liste osoba sa istim sadržajem]{Zadatak: Dve
1478   liste osoba koje dele sadržaj, jedna sortirana po visini, druga po
1479   težini}
1480
1481 Sa tastature učitavati po dva broja koji opisuju osobu (visina i
1482 težina) i smeštati ih u povezane listu, tako da postoji neopadajuće
1483 uređenje i po visini i po težini.
1484
1485 \begin{lstlisting}[style=codeblock]
1486 MODULE VisTez;
1487 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1488 FROM IO IMPORT WrLn, WrStr, RdCard, WrCard;
1489 FROM SYSTEM IMPORT TSIZE;
1490 TYPE
1491   pok = POINTER TO element;
1492   element = RECORD
1493               visina, tezina : CARDINAL;
1494               Vveza, Tveza : pok
1495             END;
1496 VAR
1497   pocV, pocT : pok;
1498   vis, tez : CARDINAL;
1499 PROCEDURE Ispisi(pocV, pocT : pok);
1500 VAR
1501   tek : pok;
1502 BEGIN
1503   tek := pocV;
1504   WrStr('Po visini:');
1505   WrLn;
1506   WHILE tek # NIL DO
1507     WrCard(tek^.visina, 6);
1508     tek := tek^.Vveza
1509   END;
1510   WrLn;
1511   tek := pocT;
1512   WrStr('Po tezini:');
1513   WrLn;
1514   WHILE tek # NIL DO
1515     WrCard(tek^.tezina,6);
1516     tek := tek^.Tveza
1517   END
1518 END Ispisi;
1519
1520 PROCEDURE Ubaci(VAR pocV, pocT : pok;
1521                 vis, tez : CARDINAL);
1522 VAR
1523   novi, tek, iza : pok;
1524   nadjen : BOOLEAN;
1525 BEGIN
1526   IF pocV = NIL THEN
1527     ALLOCATE(pocV, TSIZE(element));
1528     pocV^.visina := vis;
1529     pocV^.tezina := tez;
1530     pocV^.Vveza := NIL;
1531     pocV^.Tveza := NIL;
1532     pocT := pocV
1533   ELSE
1534     ALLOCATE(novi, TSIZE(element));
1535     novi^.visina := vis;
1536     novi^.tezina := tez;
1537     tek := pocV;
1538     nadjen := FALSE;
1539     WHILE (tek # NIL) AND NOT nadjen DO
1540       nadjen := vis <= tek^.visina;
1541       IF NOT nadjen THEN
1542         iza := tek;
1543         tek := tek^.Vveza
1544       END
1545     END;
1546     novi^.Vveza := tek;
1547     IF tek = pocV THEN
1548       pocV := novi
1549     ELSE
1550       iza^.Vveza := novi
1551     END;
1552     tek := pocT;
1553     nadjen := FALSE;
1554     WHILE (tek # NIL) AND NOT nadjen DO
1555       nadjen := tez <= tek^.tezina;
1556       IF NOT nadjen THEN
1557         iza := tek;
1558         tek := tek^.Tveza
1559       END
1560     END;
1561     novi^.Tveza := tek;
1562     IF tek = pocT THEN
1563       pocT := novi
1564     ELSE
1565       iza^.Tveza := novi
1566     END
1567   END
1568 END Ubaci;
1569
1570 BEGIN
1571   pocV := NIL;
1572   pocT := NIL;
1573   WrStr('Unesite visinu ---- ');
1574   vis := RdCard();
1575   WHILE vis > 0 DO
1576     WrStr('Unesite tezinu ---- ');
1577     tez := RdCard();
1578     Ubaci(pocV, pocT, vis, tez);
1579     WrLn;
1580     WrStr('Unesite visinu ---- ');
1581     vis := RdCard()
1582   END;
1583   WrLn;
1584   Ispisi(pocV, pocT)
1585 END VisTez.
1586 \end{lstlisting}
1587
1588 \section{Polinomi preko listi}
1589
1590 \subsection{Moduli}
1591
1592 Polinomi su predstavljeni pomoću pokazivača. Apstraktni tip podataka
1593 \kod{Polinom} je definisan u globalnom modulu.
1594
1595 \paragraph{PolinomL.DEF} \
1596
1597 \begin{lstlisting}[style=codeblock]
1598 DEFINITION MODULE PolinomL;
1599 TYPE
1600   Polinom = POINTER TO Monom;
1601   Monom = RECORD
1602             k : REAL;
1603             st : CARDINAL;
1604             veza : Polinom
1605           END;
1606
1607 PROCEDURE Anuliraj(VAR p: Polinom);
1608 PROCEDURE Unos(VAR p: Polinom);
1609 PROCEDURE Stampaj(p: Polinom; d: CARDINAL);
1610 PROCEDURE Kopiraj(p: Polinom;
1611                   VAR kopija: Polinom);
1612 PROCEDURE UbaciMonom(mon:Polinom;
1613                      VAR p: Polinom);
1614 PROCEDURE PromeniZnak(VAR p: Polinom);
1615 PROCEDURE Saberi(p1, p2: Polinom;
1616                  VAR zbir: Polinom);
1617 PROCEDURE SaberiNa(p: Polinom; VAR rez: Polinom);
1618 PROCEDURE Oduzmi(p1,p2: Polinom;
1619                  VAR razlika: Polinom);
1620 PROCEDURE MonomPuta(p, mon: Polinom;
1621                     VAR mp : Polinom);
1622 PROCEDURE Puta(p1, p2: Polinom; VAR pr: Polinom);
1623 PROCEDURE Kolicnik(p1, p2: Polinom;
1624                    VAR kol, ost: Polinom;
1625                    VAR ok : BOOLEAN);
1626 PROCEDURE PolinomNaN(p: Polinom; n: CARDINAL;
1627                      VAR rez: Polinom);
1628 PROCEDURE DisposePolinom(VAR p: Polinom);
1629
1630 END PolinomL.
1631 \end{lstlisting}
1632
1633 \paragraph{PolinomL.MOD} \
1634
1635 \begin{codeblock}
1636 (* Modul za rad sa polinomima preko listi
1637    verzija 2012, rev 1 *)
1638 IMPLEMENTATION MODULE PolinomL;
1639 FROM InOut IMPORT Write, WriteString, WriteLn,
1640            WriteCard, ReadCard, Done;
1641 FROM RealInOut IMPORT WriteReal, ReadReal;
1642 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1643
1644 PROCEDURE Anuliraj(VAR p: Polinom);
1645 BEGIN
1646   p := NIL;
1647 END Anuliraj;
1648
1649 PROCEDURE Kopiraj(p: Polinom; VAR kopija: Polinom);
1650 VAR
1651   pomocni: Polinom;
1652 BEGIN
1653   IF p = NIL THEN
1654     kopija := NIL
1655   ELSE
1656     NEW(kopija);
1657     kopija^ := p^;
1658     p := p^.veza;
1659     pomocni := kopija;
1660     WHILE p <> NIL DO
1661       NEW(pomocni^.veza);
1662       pomocni := pomocni^.veza;
1663       pomocni^ := p^;
1664       p := p^.veza
1665     END
1666   END
1667 END Kopiraj;
1668
1669 PROCEDURE Stampaj(p: Polinom; d: CARDINAL);
1670
1671   PROCEDURE StampajMonom(m : Polinom);
1672   BEGIN
1673     WITH m^ DO
1674       IF st <> 0 THEN
1675         IF ABS(k) <> 1.0 THEN
1676           WriteReal(ABS(k), d)
1677         END;
1678         Write('x');
1679         IF st <> 1 THEN
1680           Write('^');
1681           WriteCard(st, 1)
1682         END
1683       ELSE
1684         WriteReal(ABS(k), d)
1685       END
1686     END
1687   END StampajMonom;
1688
1689 BEGIN
1690   IF p = NIL THEN
1691     WriteReal(0., d)
1692   ELSE
1693     IF p^.k < 0.0 THEN
1694       WriteString(' - ')
1695     END;
1696     StampajMonom(p);
1697     p := p^.veza;
1698     WHILE p <> NIL DO
1699       IF p^.k > 0.0 THEN
1700         WriteString(' + ')
1701       ELSE
1702         WriteString(' - ')
1703       END;
1704       StampajMonom(p);
1705       p := p^.veza
1706     END
1707   END
1708 END Stampaj;
1709
1710 PROCEDURE UbaciMonom(mon:Polinom; VAR p: Polinom);
1711 VAR
1712   stari, tekuci, kopija: Polinom;
1713 BEGIN
1714   IF mon # NIL THEN
1715     NEW(kopija);
1716     kopija^ := mon^;
1717     tekuci := p;
1718         stari := NIL;
1719     WHILE (tekuci#NIL) AND (tekuci^.st>kopija^.st) DO
1720       stari := tekuci;
1721       tekuci := tekuci^.veza
1722     END;
1723     kopija^.veza := tekuci;
1724     IF tekuci = p THEN
1725       p := kopija
1726     ELSE
1727       stari^.veza := kopija
1728     END;
1729     IF (tekuci#NIL) AND (kopija^.st = tekuci^.st) THEN
1730       kopija^.k := kopija^.k + tekuci^.k;
1731       kopija^.veza := tekuci^.veza;
1732       DISPOSE(tekuci);
1733       IF kopija^.k = 0.0 THEN
1734         IF p = kopija THEN
1735           p := kopija^.veza
1736         ELSE
1737           stari^.veza := kopija^.veza
1738         END;
1739         DISPOSE(kopija)
1740       END
1741     END
1742   END
1743 END UbaciMonom;
1744
1745 PROCEDURE Unos(VAR p : Polinom);
1746 VAR
1747   i, n: CARDINAL;
1748   novi: Polinom;
1749 BEGIN
1750   Anuliraj(p);
1751   REPEAT
1752     WriteLn;
1753     WriteString('Unesite broj monoma n (n>=0) ');
1754     ReadCard(n);
1755   UNTIL Done;
1756   WriteLn;
1757   FOR i := 1 TO n DO
1758     NEW(novi);
1759     WITH novi^ DO
1760       REPEAT
1761         WriteString('Unesite koeficijent monoma br.');
1762         WriteCard(i, 1);
1763         WriteString(' (<> 0) ');
1764         ReadReal(k);
1765         WriteLn
1766       UNTIL k <> 0.0;
1767       REPEAT
1768         WriteLn;
1769         WriteString('Unesite eksponent monoma br.');
1770         WriteCard(i, 1);
1771         WriteString(' (>=0) ');
1772         ReadCard(st);
1773       UNTIL Done;
1774       WriteLn;
1775     END;
1776     UbaciMonom(novi, p);
1777     DISPOSE(novi);
1778   END
1779 END Unos;
1780
1781 PROCEDURE Saberi(p1, p2: Polinom; VAR zbir: Polinom);
1782 BEGIN
1783   Kopiraj(p1, zbir);
1784   WHILE p2 <> NIL DO
1785     UbaciMonom(p2, zbir);
1786     p2 := p2^.veza
1787   END
1788 END Saberi;
1789
1790 PROCEDURE SaberiNa(p: Polinom; VAR rez: Polinom);
1791 BEGIN
1792   WHILE p <> NIL DO
1793     UbaciMonom(p,rez);
1794     p := p^.veza;
1795   END;
1796 END SaberiNa;
1797
1798 PROCEDURE PromeniZnak(VAR p: Polinom);
1799 VAR
1800   t: Polinom;
1801 BEGIN
1802   t := p;
1803   WHILE t <> NIL DO
1804     t^.k := - t^.k;
1805     t := t^.veza
1806   END
1807 END PromeniZnak;
1808
1809 PROCEDURE Oduzmi(p1,p2: Polinom; VAR razlika: Polinom);
1810 BEGIN
1811   Kopiraj(p2, razlika);
1812   PromeniZnak(razlika);
1813   WHILE p1 <> NIL DO
1814     UbaciMonom(p1, razlika);
1815     p1 := p1^.veza
1816   END
1817 END Oduzmi;
1818
1819 PROCEDURE MonomPuta(p, mon: Polinom; VAR mp: Polinom);
1820 VAR
1821   tekuci: Polinom;
1822 BEGIN
1823   Anuliraj(mp);
1824   IF (mon <> NIL) AND (p <> NIL) THEN
1825     NEW(mp);
1826     mp^.k := p^.k * mon^.k;
1827     mp^.st := p^.st + mon^.st;
1828     p := p^.veza;
1829     tekuci := mp;
1830     WHILE p <> NIL DO
1831       NEW(tekuci^.veza);
1832       tekuci := tekuci^.veza;
1833       tekuci^.k := p^.k * mon^.k;
1834       tekuci^.st := p^.st + mon^.st;
1835       p := p^.veza
1836     END;
1837     tekuci^.veza := NIL
1838   END
1839 END MonomPuta;
1840
1841 PROCEDURE Puta(p1, p2: Polinom; VAR pr: Polinom);
1842 VAR
1843   pomocni: Polinom;
1844 BEGIN
1845   Anuliraj(pr);
1846   IF (p1 <> NIL) AND (p2 <> NIL) THEN
1847     MonomPuta(p1, p2, pr);
1848     p2 := p2^.veza;
1849     WHILE p2 <> NIL DO
1850       MonomPuta(p1, p2, pomocni);
1851       REPEAT
1852         UbaciMonom(pomocni, pr);
1853         pomocni := pomocni^.veza
1854       UNTIL pomocni = NIL;
1855       p2 := p2^.veza
1856     END
1857   END
1858 END Puta;
1859
1860 PROCEDURE Kolicnik(p1, p2: Polinom; VAR kol, ost: Polinom; VAR ok: BOOLEAN);
1861
1862   PROCEDURE Deli(VAR kol, ost: Polinom);
1863   VAR
1864     novi, pomocni: Polinom;
1865   BEGIN
1866     IF ost <> NIL THEN
1867       IF ost^.st >= p2^.st THEN
1868         NEW(novi);
1869         novi^.k := - ost^.k / p2^.k;
1870         novi^.st := ost^.st - p2^.st;
1871         MonomPuta(p2, novi, pomocni);
1872         Saberi(ost, pomocni, ost);
1873         novi^.k := - novi^.k;
1874         UbaciMonom(novi, kol);
1875         DISPOSE(novi);
1876         Deli(kol, ost)
1877       END
1878     END
1879   END Deli;
1880
1881 BEGIN (* Kolicnik *)
1882   ok := TRUE;
1883   Anuliraj(kol);
1884   IF p2 = NIL THEN
1885     ok := FALSE
1886   ELSE
1887     Kopiraj(p1, ost);
1888     Deli(kol, ost)
1889   END
1890 END Kolicnik;
1891
1892 PROCEDURE PolinomNaN(p: Polinom; n: CARDINAL;
1893                      VAR rez: Polinom);
1894 VAR
1895   i: CARDINAL;
1896 BEGIN
1897   IF n = 0 THEN
1898     NEW(rez);
1899     rez^.k := 1.0;
1900     rez^.st := 0;
1901     rez^.veza := NIL;
1902   ELSIF n = 1 THEN
1903         Kopiraj( p, rez );
1904   ELSE
1905     rez := p;
1906     FOR i := 2 TO n DO
1907       Puta(rez, p, rez)
1908     END
1909   END;
1910 END PolinomNaN;
1911
1912 PROCEDURE DisposePolinom(VAR p: Polinom);
1913 VAR
1914   pomocni: Polinom;
1915 BEGIN
1916   pomocni := p;
1917   WHILE pomocni # NIL DO
1918     p := p^.veza;
1919     DISPOSE(pomocni);
1920     pomocni := p
1921   END
1922 END DisposePolinom;
1923
1924 END PolinomL.
1925 \end{codeblock}
1926
1927
1928 \subsection{Zadatak: Sabiranje sa unapred određenim polinomom}
1929
1930 Želimo da ispišemo uneti polinom uvećan za\\ $x^5 - 3x^4 + 4x + 7$.
1931
1932 \begin{lstlisting}[style=codeblock]
1933 MODULE polinom;
1934 FROM PolinomL IMPORT Polinom, Stampaj, Anuliraj, DisposePolinom, UbaciMonom, Unos, Saberi;
1935 FROM InOut IMPORT WriteString, WriteLn;
1936 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1937
1938 VAR
1939   p,q,rez,pom : Polinom;
1940
1941 BEGIN
1942   (* korisnik unosi prvi polinom *)
1943   WriteString("Unesite polinom:");
1944   WriteLn;
1945   Unos(p);
1946   (* drugi polinom kreiramo mi,
1947      monom po monom *)
1948   Anuliraj(q); (* isto sto i q:=NIL; *)
1949   (* formiramo monom x^5 *)
1950   NEW(pom);
1951   pom^.st:=5;
1952   pom^.k:=1.0;
1953   (* dodajemo ga u polinom *)
1954   UbaciMonom(pom,q);
1955   DISPOSE(pom);
1956   (* -3 x^4 *)
1957   NEW(pom);
1958   pom^.st := 4;
1959   pom^.k := -3.0;
1960   UbaciMonom(pom,q);
1961   DISPOSE(pom);
1962   (* 4 x *)
1963   NEW(pom);
1964   pom^.st := 1;
1965   pom^.k := 4.0;
1966   UbaciMonom(pom,q);
1967   DISPOSE(pom);
1968   (* 7 (x^0) *)
1969   NEW(pom);
1970   pom^.st := 0;
1971   pom^.k := 7.0;
1972   UbaciMonom(pom,q);
1973   DISPOSE(pom);
1974   (* saberemo polinome *)
1975   Saberi(p, q, rez);
1976   (* odstampamo rezultat *)
1977   Stampaj(rez,0);
1978   WriteLn;
1979   (* oslobadjanje zauzete memorije *)
1980   DisposePolinom(p);
1981   DisposePolinom(q);
1982   DisposePolinom(rez);
1983 END polinom.
1984 \end{lstlisting}
1985
1986 \subsection{Zadatak: Suma k polinoma}
1987
1988 Napisati program koji ucitava broj k (1<=k<=50) i k polinoma, a nakon
1989 toga izracunava njihovu sumu
1990
1991 \begin{lstlisting}[style=codeblock]
1992 MODULE PolSuma;
1993
1994 FROM PolinomL IMPORT Polinom, Anuliraj, DisposePolinom, Unos, Stampaj, SaberiNa;
1995 FROM InOut IMPORT WriteLn, WriteString, ReadCard, WriteCard;
1996 CONST
1997   maxk = 50;
1998 TYPE
1999   nizPol = ARRAY [1..maxk] OF Polinom;
2000 VAR
2001   i, k: CARDINAL;
2002   suma : Polinom;
2003   p : nizPol;
2004 BEGIN
2005   REPEAT
2006     WriteString('Unesite broj k (1 <= k <= ');
2007     WriteCard(maxk, 1);
2008     WriteString(') ');
2009     ReadCard(k);
2010     WriteLn;
2011   UNTIL (1 <= k) AND (k <= maxk);
2012   FOR i := 1 TO k DO
2013     WriteLn;
2014     WriteString('Unos ');
2015     WriteCard(i, 1);
2016     WriteString('. polinoma.');
2017     WriteLn;
2018     Unos(p[i])
2019   END;
2020   Anuliraj(suma);
2021   FOR i := 1 TO k DO
2022     SaberiNa(suma, p[i])
2023   END;
2024   WriteLn;
2025   WriteString('Njihova suma je:');
2026   WriteLn;
2027   Stampaj(suma, 4);
2028   DisposePolinom(suma);
2029   FOR i := 1 TO k DO
2030     DisposePolinom(p[i]);
2031   END;
2032 END PolSuma.
2033 \end{lstlisting}
2034
2035 \section{Stek i red opsluživanja}
2036
2037 \subsection{Zadatak: Ilustracija pisanja u fajl uz pomoć bafera}
2038
2039 \begin{lstlisting}[style=codeblock]
2040 DEFINITION MODULE QueueInfo;
2041 CONST
2042   Maxqueue = 100;
2043 TYPE
2044   InfoTip = CHAR;
2045
2046 END QueueInfo.
2047
2048 IMPLEMENTATION MODULE QueueInfo;
2049 END QueueInfo.
2050
2051 DEFINITION MODULE RedOpsl1;
2052 FROM QueueInfo IMPORT InfoTip,Maxqueue;
2053 TYPE
2054   Niz = ARRAY[1..Maxqueue] OF InfoTip;
2055   RedOpslTip = RECORD
2056         Prvi, Zadnji : CARDINAL;
2057         Element : Niz
2058   END;
2059
2060 PROCEDURE MakeNull(VAR q : RedOpslTip);
2061 PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
2062 PROCEDURE First(VAR q : RedOpslTip;
2063                 VAR x : InfoTip;
2064                 VAR ok : BOOLEAN);
2065 PROCEDURE PopFirst(VAR q : RedOpslTip;
2066                    VAR ok : BOOLEAN);
2067 PROCEDURE AddRear(VAR q : RedOpslTip;
2068                   x : InfoTip;
2069                   VAR ok : BOOLEAN);
2070
2071 END RedOpsl1.
2072
2073 IMPLEMENTATION MODULE RedOpsl1;
2074 FROM QueueInfo IMPORT Maxqueue,InfoTip;
2075
2076 PROCEDURE MakeNull(VAR q : RedOpslTip);
2077 BEGIN
2078   WITH q DO
2079     Prvi := 0;
2080     Zadnji := 0
2081   END
2082 END MakeNull;
2083
2084 PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
2085 BEGIN
2086   RETURN q.Zadnji = 0
2087 END Empty;
2088
2089
2090 PROCEDURE First(VAR q : RedOpslTip;
2091                 VAR x : InfoTip;
2092                 VAR ok : BOOLEAN);
2093 BEGIN
2094   IF Empty(q) THEN
2095     ok := FALSE
2096   ELSE
2097     ok := TRUE;
2098     WITH q DO
2099       x := Element[Prvi]
2100     END
2101   END
2102 END First;
2103
2104 PROCEDURE AddOne(i : CARDINAL) : CARDINAL;
2105 BEGIN
2106   IF i = Maxqueue THEN
2107     RETURN 1
2108   ELSE
2109     RETURN i+1
2110   END
2111 END AddOne;
2112
2113 PROCEDURE PopFirst(VAR q : RedOpslTip;
2114                    VAR ok : BOOLEAN);
2115 BEGIN
2116   IF Empty(q) THEN
2117     ok := FALSE
2118   ELSE
2119     ok := TRUE;
2120     WITH q DO
2121       IF Prvi = Zadnji THEN
2122         MakeNull(q)
2123       ELSE
2124         Prvi := AddOne(Prvi)
2125       END
2126     END
2127   END
2128 END PopFirst;
2129
2130 PROCEDURE AddRear(VAR q : RedOpslTip;
2131                   x : InfoTip;
2132                   VAR ok : BOOLEAN);
2133 BEGIN
2134   WITH q DO
2135     IF AddOne(Zadnji) = Prvi THEN
2136       ok := FALSE
2137     ELSE
2138       ok := TRUE;
2139       IF Empty(q) THEN
2140         Prvi := 1;
2141         Zadnji := 1
2142       ELSE
2143         Zadnji := AddOne(Zadnji)
2144       END;
2145       Element[Zadnji] := x
2146     END
2147   END
2148 END AddRear;
2149
2150 END RedOpsl1.
2151
2152 MODULE Bafer;
2153 FROM RedOpsl1 IMPORT RedOpslTip, MakeNull, Empty, First, PopFirst, AddRear;
2154 FROM FIO IMPORT File,WrChar, Create, Close;
2155 IMPORT IO;
2156
2157 CONST
2158   ImeIzlaza = 'izlaz.txt';
2159
2160 VAR
2161   izlaz : File;
2162   znak : CHAR;
2163   buffer : RedOpslTip;
2164
2165 PROCEDURE IsprazniBafer(VAR dat : File;
2166                         VAR buf : RedOpslTip);
2167 VAR
2168   znak : CHAR;
2169   ok : BOOLEAN;
2170 BEGIN
2171   WHILE NOT Empty(buf) DO
2172     First(buf, znak, ok);
2173     PopFirst(buf, ok);
2174     WrChar(dat, znak)
2175   END
2176 END IsprazniBafer;
2177
2178 PROCEDURE BaferWrite(VAR dat : File;
2179                      VAR buf : RedOpslTip;
2180                      znak : CHAR);
2181 VAR
2182   ok : BOOLEAN;
2183 BEGIN
2184   AddRear(buf, znak, ok);
2185   IF NOT ok THEN
2186     IsprazniBafer(dat, buf);
2187     AddRear(buf, znak, ok)
2188   END
2189 END BaferWrite;
2190
2191 BEGIN
2192   izlaz := Create(ImeIzlaza);
2193   MakeNull(buffer);
2194   IO.WrStr('Unesite tekst, koji treba da se unese u datoteku ');
2195   IO.WrStr(ImeIzlaza);
2196   IO.WrChar('.');
2197   IO.WrLn;
2198   IO.WrStr('Unos zavrsite tackom.');
2199   IO.WrLn;
2200   znak := IO.RdChar();
2201   WHILE znak # '.' DO
2202     BaferWrite(izlaz, buffer, znak);
2203     znak := IO.RdChar();
2204   END;
2205   IsprazniBafer(izlaz, buffer);
2206   Close(izlaz)
2207 END Bafer.
2208 \end{lstlisting}
2209
2210 \subsection%
2211 {Zadatak: Ispitivanje da li reč pripada gramatici wcw$^+$}
2212
2213 Reč pripada ovoj gramatici ako joj se prvi deo (w) sastoji samo od
2214 slova 'a' i 'b', sledi slovo 'c' a nakon njega obrnuta reč reči w.
2215
2216 \begin{lstlisting}[style=codeblock]
2217 DEFINITION MODULE Stek;
2218 CONST
2219   Maxstack = 100;
2220 TYPE
2221   Niz = ARRAY [1..Maxstack] OF CHAR;
2222   StekTip = RECORD
2223             Top : CARDINAL;
2224             Element : Niz
2225           END;
2226 PROCEDURE MakeNull(VAR s : StekTip);
2227 PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
2228
2229 PROCEDURE Top(VAR s : StekTip;
2230               VAR x : CHAR;
2231               VAR ok : BOOLEAN);
2232 PROCEDURE Pop(VAR s : StekTip;
2233               VAR ok : BOOLEAN);
2234 PROCEDURE Push(VAR s : StekTip;
2235                x : CHAR;
2236                VAR ok : BOOLEAN);
2237 END Stek.
2238
2239
2240 IMPLEMENTATION MODULE Stek;
2241
2242 PROCEDURE MakeNull(VAR s : StekTip);
2243 BEGIN
2244   s.Top := 0
2245 END MakeNull;
2246
2247 PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
2248 BEGIN
2249   RETURN s.Top = 0
2250 END Empty;
2251
2252 PROCEDURE Top(VAR s : StekTip;
2253               VAR x : CHAR;
2254               VAR ok : BOOLEAN);
2255 BEGIN
2256   IF Empty(s) THEN
2257     ok := FALSE
2258   ELSE
2259     ok := TRUE;
2260     WITH s DO
2261       x := Element[Top]
2262     END
2263   END
2264 END Top;
2265
2266 PROCEDURE Pop(VAR s : StekTip;
2267               VAR ok : BOOLEAN);
2268 BEGIN
2269   IF Empty(s) THEN
2270     ok := FALSE
2271   ELSE
2272     ok := TRUE;
2273     DEC(s.Top)
2274   END
2275 END Pop;
2276
2277 PROCEDURE Push(VAR s : StekTip;
2278                x : CHAR;
2279                VAR ok : BOOLEAN);
2280 BEGIN
2281   WITH s DO
2282     IF Top = Maxstack THEN
2283       ok := FALSE
2284     ELSE
2285       ok := TRUE;
2286       INC(Top);
2287       Element[Top] := x
2288     END
2289   END
2290 END Push;
2291 END Stek.
2292
2293 MODULE wcw;
2294 (* Da li rec pripada gramatici wcw+. *)
2295 FROM Stek IMPORT StekTip, MakeNull, Empty,
2296                  Top, Pop, Push;
2297 FROM InOut IMPORT Read, Write, WriteString, EOL;
2298 TYPE
2299   slova = SET OF CHAR;
2300 VAR
2301   S : StekTip;
2302   Ch, C : CHAR;
2303   ok : BOOLEAN;
2304 BEGIN
2305   MakeNull(S);
2306   Read(Ch);
2307   ok := TRUE;
2308   WHILE ok AND (Ch IN slova{'a', 'b'}) DO
2309     Push(S, Ch, ok);
2310     Read(Ch);
2311   END;
2312   IF NOT ok THEN
2313     WriteString('Greska - mali stek')
2314   ELSIF Ch # 'c' THEN
2315     WriteString('Pogresan string')
2316   ELSE
2317     Read(Ch);
2318     WHILE ok AND (Ch # EOL) DO
2319       Top(S, C, ok);
2320       ok := ok AND (C = Ch);
2321       IF ok THEN
2322         Pop(S, ok);
2323         Read(Ch);
2324       END
2325     END;
2326     IF NOT (ok AND Empty(S)) THEN
2327       WriteString('Pogresan string')
2328     ELSE
2329       WriteString('String pripada jeziku L')
2330     END
2331   END
2332 END wcw.
2333 \end{lstlisting}
2334
2335 \subsection{Zadatak: Kalkulator za izračunavanje postfiksnih izraza}
2336
2337
2338 Napraviti kalkulator za izračunavanje postfiksnih izraza. Svi brojevi
2339 koji figurišu u izrazu su jednocifreni.
2340
2341 \begin{lstlisting}[style=codeblock]
2342 MODULE PostFix;
2343
2344 FROM StekI IMPORT StekTip, MakeNull, Empty, Top, Pop, Push;
2345 FROM InOut IMPORT Read, Write, WriteInt, EOL;
2346 TYPE
2347   slova = SET OF CHAR;
2348 VAR
2349   S : StekTip;
2350   Ch : CHAR;
2351   Op1, Op2 : INTEGER;
2352   ok : BOOLEAN;
2353 PROCEDURE Conv(Ch : CHAR) : INTEGER;
2354 BEGIN
2355   RETURN  ORD(Ch) - ORD('0')
2356 END Conv;
2357
2358 BEGIN
2359   MakeNull(S);
2360   Read(Ch);
2361   WHILE Ch # EOL DO
2362     IF Ch IN slova{'+', '-', '/', '*', '%'} THEN
2363       Top(S, Op2, ok);
2364       Pop(S, ok);
2365       Top(S, Op1, ok);
2366       Pop(S, ok);
2367       CASE Ch OF
2368         '+' : Op1 := Op1 + Op2 |
2369         '-' : Op1 := Op1 - Op2 |
2370         '*' : Op1 := Op1 * Op2 |
2371         '/' : Op1 := Op1 DIV Op2 |
2372         '%' : Op1 := Op1 MOD Op2
2373       END;
2374       Push(S, Op1, ok)
2375     ELSE
2376       Push(S, Conv(Ch), ok)
2377     END;
2378     Read(Ch);
2379   END;
2380   Top(S, Op1, ok);
2381   Write('=');
2382   WriteInt(Op1,5)
2383 END PostFix.
2384 \end{lstlisting}
2385
2386
2387 \section{Simulacija rekurzije}
2388
2389
2390 Na početku označiti sve rekurzivne pozive u originalnoj proceduri
2391 adresama (npr. 1,2,3... ili konstante nabrojivog tipa podataka).
2392
2393 Na steku se čuvaju lokalne promenljive, parametri procedure i adresa
2394 mesta poziva, a u skladu sa tim se kreira InfoTip.
2395
2396 Trivijalnim pozivom se smatra onaj koji se izračunava bez dodatnih
2397 rekurzivnih poziva.
2398
2399 U kodu ispod, \kod{treba\_rekurzija} znači da je poziv netrivijalan,
2400 odnosno treba naći uslove pod kojima se sigurno dešavaju rekurzivni
2401 pozivi.
2402
2403 \begin{lstlisting}
2404 MakeNull(S);
2405 REPEAT
2406   WHILE treba_rekurzija DO
2407     -prepisati sve od pocetka originalne
2408      procedure do prvog rekurzivnog poziva
2409     -staviti na stek potrebne
2410      lokalne promenljive, parametre procedure i
2411      adresu mesta poziva
2412     -podesiti vrednosti parametara da budu
2413      kao u rekurzivnom pozivu procedure
2414   END;
2415   trivijalan poziv
2416   umesto RETURN x pisati rez := x
2417   jos := TRUE;
2418   WHILE jos AND NOT Empty(S) DO
2419     Top(S, el, ok);
2420     Pop(S, ok);
2421     -restauriramo vrednosti sa steka
2422     -u zavisnosti od adrese poziva nastavimo
2423      prepisivanje originalne procedure sa
2424      tog mesta
2425     -ako se dodje do novog rek. poziva tada:
2426        -sacuvati na steku vrednosti
2427        -podesiti vrednosti parametara da budu
2428         kao u rekurzivnom pozivu procedure
2429        -ici na pocetak koda
2430         (ovo se postize sa jos := FALSE)
2431     -inace
2432        ako se naidje na RETURN x pisati rez := x
2433   END
2434 UNTIL Empty(S);
2435 \end{lstlisting}
2436
2437 Ako je procedura funkcijska tada se na kraj dodaje \kod{RETURN rez}.
2438
2439 \subsection*{ZADACI}
2440
2441 Simulirati ponašanje sledećih rekurzivnih procedura (funkcija) upotrebom steka:
2442
2443 \subsection{Primer 1 -- faktorijel}
2444
2445
2446 \begin{lstlisting}[style=codeblock]
2447 MODULE Fakto;
2448 (* InfoTip = CARDINAL; *)
2449
2450 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2451 FROM StekC IMPORT StekTip, MakeNull, Empty,
2452                   Top, Pop, Push;
2453 VAR
2454   n : CARDINAL;
2455 PROCEDURE RFakto(n : CARDINAL) : CARDINAL;
2456 BEGIN
2457   IF n <= 1 THEN
2458     RETURN 1
2459   ELSE
2460     RETURN n * RFakto(n-1)
2461   END
2462 END RFakto;
2463
2464
2465 PROCEDURE SFakto(n : CARDINAL) : CARDINAL;
2466 VAR
2467   s : StekTip;
2468   rez : CARDINAL;
2469   OK : BOOLEAN;
2470 BEGIN
2471   MakeNull(s);
2472   WHILE n > 1 DO
2473     Push(s,n,OK);
2474     DEC(n)
2475   END;
2476   rez := 1;
2477   WHILE NOT Empty(s) DO
2478     Top(s, n, OK);
2479     Pop(s, OK);
2480     rez := n * rez
2481   END;
2482   RETURN rez
2483 END SFakto;
2484
2485 BEGIN
2486   WrStr('n = ');
2487   n := RdCard();
2488   WrLn
2489   WrStr('n! = ');
2490   WrCard(RFakto(n), 1);
2491   WrStr(' = ');
2492   WrCard(SFakto(n), 1)
2493 END Fakto.
2494 \end{lstlisting}
2495
2496 \subsection{Primer 2 -- stepenovanje}
2497
2498 \begin{lstlisting}[style=codeblock]
2499 MODULE Step;
2500 (* InfoTip = RECORD
2501                 x : REAL;
2502                 n : CARDINAL;
2503                 adr : (par, nepar)
2504              END;
2505 *)
2506
2507 FROM IO IMPORT WrStr, WrLn, WrReal,
2508         RdReal, RdCard;
2509 FROM StekStep IMPORT StekTip, MakeNull, Empty,
2510              Top, Pop, Push, InfoTip, AdrTip;
2511
2512 VAR
2513   n : CARDINAL;
2514   x : REAL;
2515
2516 PROCEDURE Sqr(y : REAL) : REAL;
2517 BEGIN
2518   RETURN y * y
2519 END Sqr;
2520
2521 PROCEDURE RStep(x : REAL;
2522                 n : CARDINAL) : REAL;
2523 BEGIN
2524   IF n = 0 THEN
2525     RETURN 1.
2526   ELSIF ODD(n) THEN
2527     RETURN x * Sqr( RStep(x, n DIV 2) )
2528   ELSE
2529     RETURN Sqr( RStep(x, n DIV 2) )
2530   END
2531 END RStep;
2532
2533 PROCEDURE SStep(x : REAL;
2534                 n : CARDINAL ) : REAL;
2535 VAR
2536   s : StekTip;
2537   OK : BOOLEAN;
2538   rez : REAL;
2539   el : InfoTip;
2540 BEGIN
2541   MakeNull(s);
2542   WHILE n > 0 DO
2543     el.x := x;
2544     el.n := n;
2545     IF ODD(n) THEN
2546       el.adr := nepar;
2547     ELSE
2548       el.adr := par
2549     END;
2550     Push(s,el,OK);
2551     n := n DIV 2
2552   END;
2553   rez := 1.;
2554   WHILE NOT Empty(s) DO
2555     Top(s, el, OK);
2556     Pop(s, OK);
2557     x := el.x;
2558     n := el.n;
2559     IF el.adr = nepar THEN
2560       rez := x * Sqr(rez)
2561     ELSE
2562       rez := Sqr(rez)
2563     END
2564   END;
2565   RETURN rez
2566 END SStep;
2567
2568 BEGIN
2569   WrStr('x =? ');
2570   x := RdReal();
2571   WrLn;
2572   WrStr('n =? ');
2573   n := RdCard();
2574   WrStr('x^n = ');
2575   WrReal(RStep(x, n), 10, 1);
2576   WrStr(' = ');
2577   WrReal(SStep(x, n), 10, 1)
2578 END Step.
2579 \end{lstlisting}
2580
2581 \subsection{Primer 3 -- Fibonači}
2582
2583 \begin{lstlisting}[style=codeblock]
2584 MODULE Fib;
2585 (* InfoTip = RECORD
2586                 n : CARDINAL;
2587                 PrviSab : CARDINAL;
2588                 adr : (prvi, drugi)
2589              END;
2590 *)
2591
2592 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2593 FROM StekFib IMPORT StekTip, MakeNull, Empty,
2594        Top, Pop, Push, InfoTip, AdrTip;
2595 VAR
2596   n : CARDINAL;
2597
2598 PROCEDURE RFib(n : CARDINAL) : CARDINAL;
2599 BEGIN
2600   IF n <= 1 THEN
2601     RETURN n
2602   ELSE
2603     RETURN RFib(n-1) + RFib(n-2)
2604   END
2605 END RFib;
2606
2607 PROCEDURE SFib(n : CARDINAL ) : CARDINAL;
2608 VAR
2609   s : StekTip;
2610   OK, jos : BOOLEAN;
2611   rez, PrviSab : CARDINAL;
2612   el : InfoTip;
2613 BEGIN
2614   MakeNull(s);
2615   REPEAT
2616     WHILE n > 1 DO
2617       el.n := n;
2618       el.adr := prvi;
2619       Push(s,el,OK);
2620       DEC(n)
2621     END;
2622     rez := (n);
2623     jos := TRUE;
2624     WHILE (NOT Empty(s)) AND jos DO
2625       Top(s, el, OK);
2626       Pop(s, OK);
2627       n := el.n;
2628       IF el.adr = prvi THEN
2629         PrviSab := rez;
2630         el.n := n;
2631         el.adr := drugi;
2632         el.PrviSab := PrviSab;
2633         Push(s, el, OK);
2634         DEC(n, 2);
2635         jos := FALSE
2636       ELSE
2637         PrviSab := el.PrviSab;
2638         rez := PrviSab + rez
2639       END
2640     END
2641   UNTIL Empty(s);
2642   RETURN rez
2643 END SFib;
2644
2645 BEGIN
2646   WrStr('n =? ');
2647   n := RdCard();
2648   WrStr('F(n) = ');
2649   WrCard(RFib(n), 1);
2650   WrStr(' = ');
2651   WrCard(SFib(n), 1)
2652 END Fib.
2653 \end{lstlisting}
2654
2655 \subsection{Primer 4 -- faktorijel 2}
2656
2657
2658 \begin{lstlisting}[style=codeblock]
2659 MODULE Faktor;
2660 (* InfoTip = CARDINAL; *)
2661 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2662 FROM StekC IMPORT StekTip, MakeNull, Empty,
2663                   Top, Pop, Push;
2664
2665 VAR
2666   n,rez : CARDINAL;
2667
2668 PROCEDURE RFakto(n : CARDINAL;
2669                  VAR rez : CARDINAL);
2670 BEGIN
2671   IF n = 0 THEN
2672     rez := 1
2673   ELSE
2674     RFakto(n-1, rez);
2675     rez := n * rez
2676   END
2677 END RFakto;
2678
2679 PROCEDURE SFakto(n : CARDINAL;
2680                  VAR rez : CARDINAL);
2681 VAR
2682   s : StekTip;
2683   OK : BOOLEAN;
2684 BEGIN
2685   MakeNull(s);
2686   WHILE n > 0 DO
2687     Push(s,n,OK);
2688     DEC(n)
2689   END;
2690   rez := 1;
2691   WHILE NOT Empty(s) DO
2692     Top(s, n, OK);
2693     Pop(s, OK);
2694     rez := n * rez
2695   END
2696 END SFakto;
2697
2698 BEGIN
2699   WrStr('n =? ');
2700   n := RdCard();
2701   WrLn;
2702   WrStr('n! = ');
2703   RFakto(n, rez);
2704   WrCard(rez, 1);
2705   WrStr(' = ');
2706   SFakto(n, rez);
2707   WrCard(rez, 1)
2708 END Faktor.
2709 \end{lstlisting}
2710
2711 \subsection{Primer 5 (ispitni)}
2712
2713
2714 \begin{lstlisting}[style=codeblock]
2715 MODULE Rek1;
2716 (* InfoTip = RECORD
2717                 d, g, m1, m2 : INTEGER;
2718                 adr : (prvi, drugi)
2719              END;
2720 *)
2721 FROM Stek1 IMPORT StekTip, adresa, InfoTip,
2722          MakeNull, Empty, Top, Pop, Push;
2723 IMPORT IO;
2724 VAR
2725   X : ARRAY [1..20] OF INTEGER;
2726
2727 PROCEDURE Max(d, g: INTEGER) : INTEGER;
2728 VAR
2729   m1, m2 : INTEGER;
2730 BEGIN
2731   IF d>g THEN
2732     RETURN MIN(INTEGER)
2733   ELSIF d=g THEN
2734     RETURN X[d]
2735   ELSE
2736     m1 := Max(d, (d+g) DIV 2);
2737     m2 := Max((d+g) DIV 2 +1, g);
2738     IF m1 > m2 THEN
2739       RETURN m1
2740     ELSE
2741       RETURN m2
2742     END
2743   END
2744 END Max;
2745
2746 PROCEDURE SMax(d, g: INTEGER) : INTEGER;
2747 VAR
2748   S : StekTip;
2749   el : InfoTip;
2750   ok, jos : BOOLEAN;
2751   m1, m2, rez : INTEGER;
2752 BEGIN
2753   MakeNull(S);
2754   REPEAT
2755     WHILE d<g DO
2756       el.d := d;
2757       el.g := g;
2758       el.adr := prvi;
2759       Push(S, el, ok);
2760       g := (d+g) DIV 2
2761     END;
2762     IF d>g THEN
2763       rez := MIN(INTEGER)
2764     ELSE (* d=g *)
2765       rez := X[d]
2766     END;
2767     jos := TRUE;
2768     WHILE jos AND NOT Empty(S) DO
2769       Top(S, el, ok);
2770       Pop(S, ok);
2771       d := el.d;
2772       g := el.g;
2773       m1 := el.m1;
2774       IF el.adr = prvi THEN
2775         m1 := rez;
2776         el.m1 := m1;
2777         el.adr := drugi;
2778         Push(S, el, ok);
2779         d := (d+g) DIV 2 + 1;
2780         jos := FALSE
2781       ELSE (*el.adr = drugi*)
2782         m2 := rez;
2783         IF m1 > m2 THEN
2784           rez := m1
2785         ELSE
2786           rez := m2
2787         END
2788       END
2789     END
2790   UNTIL Empty(S);
2791   RETURN rez
2792 END SMax;
2793
2794 BEGIN (* glavni program *)
2795   X[1] := 3;
2796   X[2] := 2;
2797   X[3] := 5;
2798   X[4] := -7;
2799   X[5] := 0;
2800   IO.WrCard(Max(1, 5), 3);
2801   IO.WrLn;
2802   IO.WrCard(SMax(1, 5), 3);
2803   IO.WrLn
2804 END Rek1.
2805 \end{lstlisting}
2806
2807 \subsection{Primer 6 (ispitni)}
2808
2809
2810 \begin{lstlisting}[style=codeblock]
2811 MODULE Rek2;
2812 (* InfoTip = RECORD
2813                 x, y, n : CARDINAL;
2814                 adr : (prvi, drugi, treci, cetvrti)
2815              END;
2816 *)
2817 FROM Stek2 IMPORT StekTip, adresa, InfoTip,
2818            MakeNull, Empty, Top, Pop, Push;
2819 IMPORT IO;
2820
2821 PROCEDURE g(x : CARDINAL; y : CARDINAL;
2822             n : CARDINAL) : CARDINAL;
2823 BEGIN
2824   IF n < 3 THEN
2825     RETURN x + y
2826   ELSIF ODD(n) THEN
2827     RETURN g(g(x+1, y, n-2), y, n-3)
2828   ELSE
2829     RETURN g(x, g(x, y+1, n-2), n-3)
2830   END
2831 END g;
2832
2833 PROCEDURE Sg(x : CARDINAL; y : CARDINAL;
2834              n : CARDINAL) : CARDINAL;
2835 VAR
2836   S : StekTip;
2837   el : InfoTip;
2838   ok, jos : BOOLEAN;
2839   rez : CARDINAL;
2840 BEGIN
2841   MakeNull(S);
2842   REPEAT
2843     WHILE n >= 3 DO
2844       IF ODD(n) THEN
2845         el.x := x;
2846         el.y := y;
2847         el.n := n;
2848         el.adr := prvi;
2849         Push(S, el, ok);
2850         INC(x);
2851         DEC(n, 2)
2852       ELSE
2853         el.x := x;
2854         el.y := y;
2855         el.n := n;
2856         el.adr := treci;
2857         Push(S, el, ok);
2858         INC(y);
2859         DEC(n, 2)
2860       END
2861     END;
2862     rez := x+y;
2863     jos := TRUE;
2864     WHILE jos AND NOT Empty(S) DO
2865       Top(S, el, ok);
2866       Pop(S, ok);
2867       x := el.x;
2868       y := el.y;
2869       n := el.n;
2870       IF el.adr = prvi THEN
2871         el.adr := drugi;
2872         Push(S, el, ok);
2873         x := rez;
2874         DEC(n, 3);
2875         jos := FALSE
2876       ELSIF el.adr = treci THEN
2877         el.adr := cetvrti;
2878         Push(S, el, ok);
2879         y := rez;
2880         DEC(n, 3);
2881         jos := FALSE
2882       END
2883     END
2884   UNTIL Empty(S);
2885   RETURN rez
2886 END Sg;
2887
2888 BEGIN (* glavni program *)
2889   IO.WrCard(g(2, 3, 10), 3);
2890   IO.WrCard(Sg(2, 3, 10), 3);
2891 END Rek2.
2892 \end{lstlisting}
2893
2894 %\columnbreak
2895
2896 \appendix
2897
2898 \section{Native XDS Modula 2 -- kratko uputstvo}
2899
2900
2901 Ovo uputstvo ukratko pokriva kako se može nabaviti XDS Modula 2 za Windows
2902 sistem, njenu instalaciju, te kako napraviti i pokretnuti jednostavan program.
2903
2904 \subsection*{Dobavljanje instalacije}
2905
2906
2907 Native XDS Modula 2 se može besplatno skinuti sa sajta proizvođača,
2908 \url{http://www.excelsior-usa.com/}, tačnije na adresi:
2909
2910 \url{http://www.excelsior-usa.com/xdsdl.html}
2911
2912 Prvo se prikazuje ugovor o korišćenju koji na dnu treba potvrditi da ste
2913 razumeli i da ćete ga se pridržavati.
2914
2915 Na stranici koja se potom otvara je potrebno odabrati ``XDS 2.6 beta 2
2916 for Windows'' i snimiti je na računar.
2917
2918 \subsection*{Instalacija okruženja}
2919
2920 Osnovno okruženje (xds-x86...) se instalira pokretanjem prethodno pomenute
2921  instalacione arhive.
2922
2923 \emph{Korisnicima Windows-a 7 preporučujemo da pokrenu instalacione
2924   pakete pomoću opcije ``Run as administrator'' do koje se stiže desnim
2925   klikom miša.}
2926
2927 Pretpostavićemo u daljem tekstu da je program instaliran u
2928 \kod{C:/XDS/}
2929
2930 \subsection*{Pokretanje okruženja}
2931
2932 Po uspešnoj instalaciji bi trebalo da postoji ikonica na desktopu, kao
2933 i grupa sa programom u start meniju.
2934
2935 Ukoliko iz bilo kakvog razloga ne postoje odgovarajuće prečice,
2936 okruženje se može pokrenuti uz pomoć izvršnog fajla
2937 \kod{C:/XDS/BIN/xds.exe} (ako je instalirano na podrazumevanoj
2938 lokaciji).
2939
2940 \subsection*{Prvi projekat}
2941
2942 Da bismo mogli da pišemo i pokrećemo svoj program, potrebno je prvo
2943 napraviti projekat za njega, što se radi na sledeći način:
2944
2945 \begin{itemize}
2946
2947 \item
2948  Iz menija se odabere Project->New.
2949 \item U dijalogu se klikne na gornje dugme ``Browse'', odabere se putanja gde
2950   će se kreirati projekat i ukuca se ime novog projekta.
2951
2952 \item U drugom polju ``Template'' ne treba da piše ništa. Ukoliko
2953   postoji neki tekst, obrisati ga.
2954
2955 \item Kliknuti na ``OK''
2956
2957 \item Iskočiće dijalog na kome piše da ne postoji fajl za editovanje,
2958   kliknuti na ``OK'' da se on napravi.
2959
2960 \item Pojavljuje se forma za kucanje programa, ukucati (na primer):
2961
2962 \begin{minipage}{\columnwidth}
2963 \begin{lstlisting}[style=codeblock]
2964   MODULE Hello;
2965   FROM InOut IMPORT WriteString,WriteLn;
2966   BEGIN
2967     WriteString("Hello World");
2968     WriteLn;
2969   END Hello.
2970 \end{lstlisting}
2971 \end{minipage}
2972
2973 \item Program se može pokrenuti na različite načine, pri čemu se
2974   automatski prevodi:
2975
2976   \begin{itemize}
2977
2978   \item Klik na ``Run'' ikonicu u toolbaru (plavi čovečuljak koji trči)
2979
2980   \item Meni Debug->Run
2981
2982   \item Prečica Ctrl+F9 na tastaturi
2983
2984   \end{itemize}
2985
2986 \item Ako je sve u redu sa programom, treba da se pojavi novi terminal
2987   u kome se ispisuje rezultat izvršavanja programa, u našem slučaju
2988   jednostavna pozdravna poruka.
2989 \end{itemize}
2990
2991 Naravno moguće je i samo prevesti (kompajlirati) program, tako da se
2992 samo prikažu greške (ako ih ima) i bez pokretanja programa:
2993 \begin{itemize}
2994 \item Klik na ``Compile'' ikonicu u toolbaru
2995 \item Meni Tools->Compile
2996 \item Prečica F9 na tastaturi
2997 \end{itemize}
2998
2999 Ukoliko u programu postoje greške, on neće biti pokrenut, već će se
3000 dobiti lista grešaka u donjem delu prozora. Na primer ako obrišemo ``S''
3001 u četvrtom redu i probamo da pokrenemo program, taj red će biti
3002 označen svetlo plavom bojom i dobićemo poruku:
3003
3004 \kod{- Error in pro1.mod [4:5]: Undeclared identifier "Writeting"}
3005
3006 Što znači da u četvrtom redu, kod petog karatkera postoji problem, da
3007 identifikator nije deklarisan, što najčešće znači da ga nismo uvezli,
3008 ili, kao u našem slučaju, da smo napravili grešku u kucanju.
3009
3010 Stvar na koju isto treba obratiti pažnju je da se nekad greška
3011 prijavljue nešto kasnije u tekstu nego što je napravljena. Na primer,
3012 ako obrišemo ``;'' na kraju četvrtog reda i probamo da pokrenemo
3013 program, peti red će biti označen svetlo plavom bojom i dobićemo
3014 poruku:
3015
3016 \kod{- Error in pro1.mod [5:5]: Expected symbol ";" }
3017
3018 Ovo se desilo jer nedostaje tačka zarez na kraju četvrtog reda, ali će
3019 kompajler probati da je traži i dalje, pa će tek na početku petog reda
3020 prijaviti grešku.
3021
3022 U spisku se takođe pojavljuje i upozorenje (Warning) o tome da se
3023 uvezena komanda WriteString ne koristi nigde u programu. Često se
3024 upozorenja mogu ignorisati, a pažnju uglavnom treba obraćati na
3025 greške, odnosno poruke koje počinju sa ``Error''.
3026
3027 Takođe se često dešava da su druge prijavljene greške posledica prve,
3028 te je poželjno ponovo kompajlirati (ili pokretati) program posle svake
3029 ispravljene greške.
3030
3031 \paragraph{Napomena o template-ovima pri kreiranju projekta:}
3032 Moguće je namestiti da u dijalogu za novi projekat drugo polje ``Template''
3033  uvek bude prazno. Potrebno je u tom istom dijalogu kliknuti na
3034  ``Configure'', a potom isprazniti polje ``default template''.
3035
3036 \subsection{Mogući problemi}
3037
3038 \subsubsection*{Nedostajući sistemski moduli}
3039
3040 Verzije pre 2.6 nisu imale uključene u glavni paket sve module koji se
3041 koriste u okviru kursa, i bilo je neophodno da se dodatno instalira i
3042 ``Top Speed Compatibility Pack'' (tscp-x86...). Bez njega je kompajler
3043 prijavljivao da ne postoje neki moduli - najčešće je problem bio da
3044 nedostaje \kod{FIO} modul.
3045
3046 \subsubsection*{Problemi u pokretanju - nemoguće naći exe}
3047
3048 Ako pri pokušaju kompajliranja/pokretanja programa kompajler prijavi
3049 da ne može da nađe exe i pri tome prijavljuje kraću putanju od one
3050 koja je stvarno u pitanju, obično se radi o tome da je postojao razmak
3051 u okviru putanje do modula. Npr ``C:\textbackslash Moj prvi program''
3052 će prouzrokovati probleme, a kompajler će prijaviti da ne može da nađe
3053 ``C:\textbackslash Moj''.
3054
3055 Ovo je nažalost problem okruženja i dok se ne ispravi u nekoj budućoj
3056 verziji ne može se zaobići, tako da je jedino rešenje premestiti
3057 fajlove, odnosno ako je moguće preimenovati problematične foldere.
3058
3059 \mainend
3060
3061 \end{document}