skripta-spa1-sadrzaj.tex

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