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 IzbaciIzListeSve(VAR lista:brojevi;
1136                         br: CARDINAL):CARDINAL;
1137 (* izbacuje sve brojeve 'br' iz liste, naravno ako
1138    postoje i vraca koliko ih je bilo *)
1139 VAR
1140   temp,prethodni:brojevi;
1141   brojac : CARDINAL;
1142 BEGIN
1143   brojac := 0;
1144   (* uklanjamo sa pocetka koliko je potrebno *)
1145   WHILE (lista # NIL) AND (lista^.info = br) DO
1146     temp:=lista;
1147     lista :=lista^.veza;
1148     DISPOSE(temp);
1149     INC(brojac);
1150   END;
1151   (* trazimo u ostatku liste *)
1152   IF (lista # NIL) THEN
1153     temp:=lista;
1154     WHILE (temp^.veza # NIL)  DO
1155         (* idemo do poslednjeg elementa liste *)
1156         prethodni:=temp;
1157         temp := temp^.veza;
1158         IF temp^.info = br THEN
1159           (* prevezemo listu oko elementa *)
1160           prethodni^.veza:=temp^.veza;
1161           DISPOSE(temp);
1162           INC(brojac);
1163           (* vracamo se jedan korak da bi
1164           u novom krugu proverili i ovaj element *)
1165           temp := prethodni;
1166         END;
1167     END;
1168   END;
1169   RETURN brojac;
1170 END IzbaciIzListeSve;
1171
1172 (* - procedure sa interakcijom sa korisnikom - *)
1173
1174 PROCEDURE IzbacivanjeEl(VAR lista:brojevi);
1175 (* izbacuje uneti broj iz liste koristeci proceduru IzbaciIzListe *)
1176 VAR
1177   br:CARDINAL;
1178 BEGIN
1179   WriteString("unesite broj za izbacivanje: ");
1180   ReadCard(br);
1181   IF IzbaciIzListe(lista,br) THEN
1182     WriteString("broj je izbacen iz liste");
1183   ELSE
1184     WriteString("greska! - broj ne postoji");
1185   END;
1186   WriteLn;
1187 END IzbacivanjeEl;
1188
1189 PROCEDURE IzbacivanjeElSvi(VAR lista:brojevi);
1190 (* izbacuje sve primeke unetog broj iz liste
1191    koristeci proceduru IzbaciIzListeSve *)
1192 VAR
1193   br, ukupno:CARDINAL;
1194 BEGIN
1195   WriteString("unesite broj za izbacivanje: ");
1196   ReadCard(br);
1197   ukupno := IzbaciIzListeSve(lista,br);
1198   WriteString("Iz liste je izbaceno ");
1199   WriteCard(ukupno,3);
1200   WriteString(" el.");
1201   WriteLn;
1202 END IzbacivanjeElSvi;
1203
1204 PROCEDURE IzbacivanjeK(VAR lista:brojevi);
1205 (* izbacuje k-ti element iz liste *)
1206 VAR
1207   temp,tekuci:brojevi;
1208   k,brojac:CARDINAL;
1209 BEGIN
1210   IF lista=NIL THEN
1211     WriteString("lista je prazna, nema ");
1212     WriteString("elemenata za izbacivanje");
1213   ELSE
1214     WriteString("unesite redni broj elementa");
1215     WriteString(" koji zelite izbaciti:");
1216     ReadCard(k);
1217     IF k=1 THEN (*izbacivanje prvog *)
1218       temp:=lista;
1219       lista := lista^.veza;
1220       DISPOSE(temp);
1221     ELSE
1222       tekuci := lista;
1223       brojac := 2; (*gledamo jedan unapred*)
1224       WHILE (tekuci^.veza# NIL) AND (k>brojac) DO
1225         (* idemo kroz listu do k-tog el *)
1226         tekuci:=tekuci^.veza;
1227         INC(brojac);
1228       END;
1229       IF (tekuci^.veza#NIL) THEN
1230          (* pamtimo element za brisanje *)
1231          temp:=tekuci^.veza;
1232          (* prevezujemo listu oko njega*)
1233          tekuci^.veza:=tekuci^.veza^.veza;
1234          DISPOSE(temp);
1235       ELSE
1236         WriteString("greska! - ne postoji el ");
1237         WriteString("u listi sa rednim brojem ");
1238         WriteCard(k,2);
1239       END;
1240       WriteLn();
1241     END;
1242   END;
1243 END IzbacivanjeK;
1244
1245 PROCEDURE Pretraga(lista:brojevi);
1246 (* provera da li se uneti broj nalazi u listi *)
1247 VAR
1248   br:CARDINAL;
1249 BEGIN
1250   WriteString("unesite trazeni broj");
1251   ReadCard(br);
1252   IF UListi(lista,br) THEN
1253     WriteString("broj postoji u listi");
1254   ELSE
1255     WriteString("broj ne postoji u listi");
1256   END;
1257   WriteLn;
1258 END Pretraga;
1259
1260 (* -- oslobadjanje memorije -- *)
1261
1262 PROCEDURE Unisti(VAR lista:brojevi);
1263 VAR
1264   temp:brojevi;
1265 BEGIN
1266   temp:=lista;
1267   WHILE temp # NIL DO
1268         lista:=lista^.veza;
1269         DISPOSE(temp);
1270         temp:=lista;
1271   END;
1272 END Unisti;
1273
1274 BEGIN
1275   (* pocinjemo od prazne liste *)
1276   lista := NIL;
1277   REPEAT
1278      WriteLn;
1279      WriteString("Ilustracija rada sa");
1280      WriteString(" listama brojeva");
1281      WriteLn;
1282      WriteString("=============================");
1283      WriteLn;
1284      WriteString("s - Stampa");WriteLn;
1285      WriteString("u - Unos");WriteLn;
1286      WriteString("i - Izbacivanje br iz liste");
1287      WriteLn;
1288      WriteString("v - izbacivanje svih br iz liste");
1289      WriteLn;
1290      WriteString("e - izbacivanje k-tog El.");
1291      WriteLn;
1292      WriteString("k - stampanje k-tog elementa");
1293      WriteLn;
1294      WriteString("m - Minimalni broj u listi");
1295      WriteLn;
1296      WriteString("p - Pretraga el. u listi");
1297      WriteLn;
1298      WriteLn;
1299      WriteString("q - kraj rada (Quit)");WriteLn;
1300       REPEAT
1301         menu := CAP(RdKey());
1302       UNTIL menu IN skupZn{'S','U','E','I','V',
1303                            'M','K','P','Q'};
1304       IF menu#'Q' THEN
1305         CASE menu OF
1306          'S' : Stampaj(lista);|
1307          'U' : Unos(lista);|
1308          'I' : IzbacivanjeEl(lista);|
1309          'V' : IzbacivanjeElSvi(lista);|
1310          'E' : IzbacivanjeK(lista);|
1311          'K' : StampajK(lista); |
1312          'M' : StampajMinimum(lista); |
1313          'P' : Pretraga(lista);|
1314         END;
1315         WriteLn;
1316         WriteString("--- pritisnite bilo koji ");
1317         WriteString("taster za povratak u meni");
1318         prazno:=RdKey();
1319       ELSE
1320         WriteString("Kraj rada")
1321       END;
1322       WriteLn;
1323   UNTIL menu='Q';
1324   Unisti(lista);
1325 END liste2.
1326 \end{lstlisting}
1327
1328
1329 \subsection{Zadatak: Prikaz operacija nad listama sa jedinstvenim ključem}
1330
1331 \begin{lstlisting}[style=codeblock]
1332 MODULE Radnici;
1333
1334 FROM InOut IMPORT WriteString, ReadString,
1335            WriteLn, WriteCard, ReadCard, Done;
1336 FROM IO IMPORT RdKey;
1337 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1338
1339 TYPE
1340   skupZn = SET OF CHAR;
1341   str = ARRAY [1..20] OF CHAR;
1342   radnici = POINTER TO slog;
1343   slog = RECORD
1344            ime, prez : str;
1345            broj : CARDINAL;
1346            sled : radnici
1347          END;
1348 VAR
1349   meni, pom : CHAR;
1350   rad : radnici;
1351
1352   PROCEDURE Clear();
1353   VAR
1354     br: CARDINAL;
1355   BEGIN
1356     FOR br:=1 TO 100 DO
1357       WriteLn;
1358     END;
1359   END Clear;
1360
1361   PROCEDURE Spisak(rad : radnici);
1362   BEGIN
1363     WHILE rad # NIL DO
1364       WriteString(rad^.ime);
1365       WriteString(' ');
1366       WriteString(rad^.prez);
1367       WriteCard(rad^.broj, 8);
1368       WriteLn;
1369       rad := rad^.sled
1370     END
1371   END Spisak;
1372
1373   PROCEDURE Zaposli(VAR rad : radnici);
1374   VAR
1375     novi, tek : radnici;
1376     nadjen : BOOLEAN;
1377   BEGIN
1378     NEW(novi);
1379     REPEAT
1380       WriteString('Ime, prezime i jedinstveni');
1381       WriteString(' broj novog radnika: ');
1382       WriteLn;
1383       ReadString(novi^.ime);
1384       ReadString(novi^.prez);
1385       ReadCard(novi^.broj);
1386       nadjen := FALSE;
1387       tek := rad;
1388       WHILE NOT nadjen AND (tek # NIL) AND
1389             (tek^.broj <= novi^.broj) DO
1390         IF novi^.broj = tek^.broj THEN
1391           nadjen := TRUE
1392         ELSE
1393           tek := tek^.sled
1394         END
1395       END
1396     UNTIL Done AND NOT nadjen;
1397     IF (rad = NIL) OR (novi^.broj<rad^.broj) THEN
1398       novi^.sled := rad;
1399       rad := novi
1400     ELSE
1401       tek := rad;
1402       WHILE (tek^.sled # NIL) AND
1403             (tek^.sled^.broj < novi^.broj) DO
1404         tek := tek^.sled
1405       END;
1406       novi^.sled := tek^.sled;
1407       tek^.sled := novi
1408     END
1409   END Zaposli;
1410
1411   PROCEDURE Otpusti(VAR rad : radnici);
1412   VAR
1413     tek, pom : radnici;
1414     br : CARDINAL;
1415   BEGIN
1416     REPEAT
1417       WriteLn;
1418       WriteString('Unesite redni broj radnika:');
1419       ReadCard(br)
1420     UNTIL Done;
1421     WriteLn;
1422     IF rad = NIL THEN
1423       WriteString('Greska.')
1424     ELSIF br = rad^.broj THEN
1425       pom := rad;
1426       rad := rad^.sled;
1427       DISPOSE(pom)
1428     ELSE
1429       tek := rad;
1430       WHILE (tek^.sled # NIL) AND
1431             (tek^.sled^.broj < br) DO
1432         tek := tek^.sled
1433       END;
1434       IF (tek^.sled = NIL) OR
1435          (tek^.sled^.broj > br) THEN
1436         WriteString('Greska.')
1437       ELSE
1438         pom := tek^.sled;
1439         tek^.sled := tek^.sled^.sled;
1440         DISPOSE(pom)
1441       END
1442     END
1443   END Otpusti;
1444
1445   PROCEDURE Inform(rad : radnici);
1446   VAR
1447     br : CARDINAL;
1448   BEGIN
1449     REPEAT
1450       WriteLn;
1451       WriteString('Unesite redni broj radnika:');
1452       ReadCard(br)
1453     UNTIL Done;
1454     WriteLn;
1455     WHILE (rad # NIL) AND (rad^.broj < br) DO
1456       rad := rad^.sled
1457     END;
1458     IF (rad = NIL) OR (rad^.broj # br) THEN
1459       WriteString('Greska.')
1460     ELSE
1461       WriteString(rad^.ime);
1462       WriteString(' ');
1463       WriteString(rad^.prez)
1464     END
1465   END Inform;
1466
1467   PROCEDURE Bankrot(VAR rad : radnici);
1468   VAR
1469     pom : radnici;
1470   BEGIN
1471     WHILE rad # NIL DO
1472       pom := rad;
1473       rad := rad^.sled;
1474       DISPOSE(pom)
1475     END
1476   END Bankrot;
1477
1478 BEGIN
1479   rad := NIL;
1480   REPEAT
1481     Clear;
1482     WriteString('s - spisak svih zaposlenih');
1483     WriteLn;
1484     WriteString('z - zaposljavanje radnika');
1485     WriteLn;
1486     WriteString('o - otpustanje radnika');
1487     WriteLn;
1488     WriteString('i - informacije o radniku');
1489     WriteLn;
1490     WriteString('b - bankrot firme');
1491     WriteLn;
1492     WriteString('k - kraj rada');
1493     WriteLn;
1494     REPEAT
1495       meni := RdKey();
1496     UNTIL CAP(meni) IN skupZn{'S', 'Z', 'O',
1497                               'I', 'B', 'K'};
1498     Clear;
1499     IF CAP(meni) # 'K' THEN
1500       CASE CAP(meni) OF
1501         'S' : Spisak(rad)|
1502         'Z' : Zaposli(rad)|
1503         'O' : Otpusti(rad)|
1504         'I' : Inform(rad)|
1505         'B' : Bankrot(rad)
1506       END;
1507       WriteLn;
1508       WriteString('-- pritisnite bilo koji ');
1509       WriteString('taster za nastavak --');
1510       pom := RdKey()
1511     END
1512   UNTIL CAP(meni) = 'K'
1513 END Radnici.
1514 \end{lstlisting}
1515
1516 Procedura \kod{Spisak} se može realizovati i u rekurzivnoj verziji:
1517
1518 \begin{lstlisting}[style=codeblock]
1519   PROCEDURE Spisak(rad : radnici);
1520   BEGIN
1521     IF rad # NIL THEN
1522       WriteString(rad^.ime);
1523       WriteString(' ');
1524       WriteString(rad^.prez);
1525       WriteCard(rad^.broj, 8);
1526       WriteLn;
1527       Spisak(rad^.sled)
1528     END
1529   END Spisak;
1530 \end{lstlisting}
1531
1532 \subsection[Zadatak: Dve liste osoba sa istim sadržajem]{Zadatak: Dve
1533   liste osoba koje dele sadržaj, jedna sortirana po visini, druga po
1534   težini}
1535
1536 Sa tastature učitavati po dva broja koji opisuju osobu (visina i
1537 težina) i smeštati ih u povezane listu, tako da postoji neopadajuće
1538 uređenje i po visini i po težini.
1539
1540 \begin{lstlisting}[style=codeblock]
1541 MODULE VisTez;
1542 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1543 FROM IO IMPORT WrLn, WrStr, RdCard, WrCard;
1544 FROM SYSTEM IMPORT TSIZE;
1545 TYPE
1546   pok = POINTER TO element;
1547   element = RECORD
1548               visina, tezina : CARDINAL;
1549               Vveza, Tveza : pok
1550             END;
1551 VAR
1552   pocV, pocT : pok;
1553   vis, tez : CARDINAL;
1554 PROCEDURE Ispisi(pocV, pocT : pok);
1555 VAR
1556   tek : pok;
1557 BEGIN
1558   tek := pocV;
1559   WrStr('Po visini:');
1560   WrLn;
1561   WHILE tek # NIL DO
1562     WrCard(tek^.visina, 6);
1563     tek := tek^.Vveza
1564   END;
1565   WrLn;
1566   tek := pocT;
1567   WrStr('Po tezini:');
1568   WrLn;
1569   WHILE tek # NIL DO
1570     WrCard(tek^.tezina,6);
1571     tek := tek^.Tveza
1572   END
1573 END Ispisi;
1574
1575 PROCEDURE Ubaci(VAR pocV, pocT : pok;
1576                 vis, tez : CARDINAL);
1577 VAR
1578   novi, tek, iza : pok;
1579   nadjen : BOOLEAN;
1580 BEGIN
1581   IF pocV = NIL THEN
1582     ALLOCATE(pocV, TSIZE(element));
1583     pocV^.visina := vis;
1584     pocV^.tezina := tez;
1585     pocV^.Vveza := NIL;
1586     pocV^.Tveza := NIL;
1587     pocT := pocV
1588   ELSE
1589     ALLOCATE(novi, TSIZE(element));
1590     novi^.visina := vis;
1591     novi^.tezina := tez;
1592     tek := pocV;
1593     nadjen := FALSE;
1594     WHILE (tek # NIL) AND NOT nadjen DO
1595       nadjen := vis <= tek^.visina;
1596       IF NOT nadjen THEN
1597         iza := tek;
1598         tek := tek^.Vveza
1599       END
1600     END;
1601     novi^.Vveza := tek;
1602     IF tek = pocV THEN
1603       pocV := novi
1604     ELSE
1605       iza^.Vveza := novi
1606     END;
1607     tek := pocT;
1608     nadjen := FALSE;
1609     WHILE (tek # NIL) AND NOT nadjen DO
1610       nadjen := tez <= tek^.tezina;
1611       IF NOT nadjen THEN
1612         iza := tek;
1613         tek := tek^.Tveza
1614       END
1615     END;
1616     novi^.Tveza := tek;
1617     IF tek = pocT THEN
1618       pocT := novi
1619     ELSE
1620       iza^.Tveza := novi
1621     END
1622   END
1623 END Ubaci;
1624
1625 BEGIN
1626   pocV := NIL;
1627   pocT := NIL;
1628   WrStr('Unesite visinu ---- ');
1629   vis := RdCard();
1630   WHILE vis > 0 DO
1631     WrStr('Unesite tezinu ---- ');
1632     tez := RdCard();
1633     Ubaci(pocV, pocT, vis, tez);
1634     WrLn;
1635     WrStr('Unesite visinu ---- ');
1636     vis := RdCard()
1637   END;
1638   WrLn;
1639   Ispisi(pocV, pocT)
1640 END VisTez.
1641 \end{lstlisting}
1642
1643 \section{Polinomi preko listi}
1644
1645 \subsection{Moduli}
1646
1647 Polinomi su predstavljeni pomoću pokazivača. Apstraktni tip podataka
1648 \kod{Polinom} je definisan u globalnom modulu.
1649
1650 \paragraph{PolinomL.DEF} \
1651
1652 \begin{lstlisting}[style=codeblock]
1653 DEFINITION MODULE PolinomL;
1654 TYPE
1655   Polinom = POINTER TO Monom;
1656   Monom = RECORD
1657             k : REAL;
1658             st : CARDINAL;
1659             veza : Polinom
1660           END;
1661
1662 PROCEDURE Anuliraj(VAR p: Polinom);
1663 PROCEDURE Unos(VAR p: Polinom);
1664 PROCEDURE Stampaj(p: Polinom; d: CARDINAL);
1665 PROCEDURE Kopiraj(p: Polinom;
1666                   VAR kopija: Polinom);
1667 PROCEDURE UbaciMonom(mon:Polinom;
1668                      VAR p: Polinom);
1669 PROCEDURE PromeniZnak(VAR p: Polinom);
1670 PROCEDURE Saberi(p1, p2: Polinom;
1671                  VAR zbir: Polinom);
1672 PROCEDURE SaberiNa(p: Polinom; VAR rez: Polinom);
1673 PROCEDURE Oduzmi(p1,p2: Polinom;
1674                  VAR razlika: Polinom);
1675 PROCEDURE MonomPuta(p, mon: Polinom;
1676                     VAR mp : Polinom);
1677 PROCEDURE Puta(p1, p2: Polinom; VAR pr: Polinom);
1678 PROCEDURE Kolicnik(p1, p2: Polinom;
1679                    VAR kol, ost: Polinom;
1680                    VAR ok : BOOLEAN);
1681 PROCEDURE PolinomNaN(p: Polinom; n: CARDINAL;
1682                      VAR rez: Polinom);
1683 PROCEDURE DisposePolinom(VAR p: Polinom);
1684
1685 END PolinomL.
1686 \end{lstlisting}
1687
1688 \paragraph{PolinomL.MOD} \
1689
1690 \begin{codeblock}
1691 (* Modul za rad sa polinomima preko listi
1692    verzija 2012, rev 1 *)
1693 IMPLEMENTATION MODULE PolinomL;
1694 FROM InOut IMPORT Write, WriteString, WriteLn,
1695            WriteCard, ReadCard, Done;
1696 FROM RealInOut IMPORT WriteReal, ReadReal;
1697 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1698
1699 PROCEDURE Anuliraj(VAR p: Polinom);
1700 BEGIN
1701   p := NIL;
1702 END Anuliraj;
1703
1704 PROCEDURE Kopiraj(p: Polinom; VAR kopija: Polinom);
1705 VAR
1706   pomocni: Polinom;
1707 BEGIN
1708   IF p = NIL THEN
1709     kopija := NIL
1710   ELSE
1711     NEW(kopija);
1712     kopija^ := p^;
1713     p := p^.veza;
1714     pomocni := kopija;
1715     WHILE p <> NIL DO
1716       NEW(pomocni^.veza);
1717       pomocni := pomocni^.veza;
1718       pomocni^ := p^;
1719       p := p^.veza
1720     END
1721   END
1722 END Kopiraj;
1723
1724 PROCEDURE Stampaj(p: Polinom; d: CARDINAL);
1725
1726   PROCEDURE StampajMonom(m : Polinom);
1727   BEGIN
1728     WITH m^ DO
1729       IF st <> 0 THEN
1730         IF ABS(k) <> 1.0 THEN
1731           WriteReal(ABS(k), d)
1732         END;
1733         Write('x');
1734         IF st <> 1 THEN
1735           Write('^');
1736           WriteCard(st, 1)
1737         END
1738       ELSE
1739         WriteReal(ABS(k), d)
1740       END
1741     END
1742   END StampajMonom;
1743
1744 BEGIN
1745   IF p = NIL THEN
1746     WriteReal(0., d)
1747   ELSE
1748     IF p^.k < 0.0 THEN
1749       WriteString(' - ')
1750     END;
1751     StampajMonom(p);
1752     p := p^.veza;
1753     WHILE p <> NIL DO
1754       IF p^.k > 0.0 THEN
1755         WriteString(' + ')
1756       ELSE
1757         WriteString(' - ')
1758       END;
1759       StampajMonom(p);
1760       p := p^.veza
1761     END
1762   END
1763 END Stampaj;
1764
1765 PROCEDURE UbaciMonom(mon:Polinom; VAR p: Polinom);
1766 VAR
1767   stari, tekuci, kopija: Polinom;
1768 BEGIN
1769   IF mon # NIL THEN
1770     NEW(kopija);
1771     kopija^ := mon^;
1772     tekuci := p;
1773         stari := NIL;
1774     WHILE (tekuci#NIL) AND (tekuci^.st>kopija^.st) DO
1775       stari := tekuci;
1776       tekuci := tekuci^.veza
1777     END;
1778     kopija^.veza := tekuci;
1779     IF tekuci = p THEN
1780       p := kopija
1781     ELSE
1782       stari^.veza := kopija
1783     END;
1784     IF (tekuci#NIL) AND (kopija^.st = tekuci^.st) THEN
1785       kopija^.k := kopija^.k + tekuci^.k;
1786       kopija^.veza := tekuci^.veza;
1787       DISPOSE(tekuci);
1788       IF kopija^.k = 0.0 THEN
1789         IF p = kopija THEN
1790           p := kopija^.veza
1791         ELSE
1792           stari^.veza := kopija^.veza
1793         END;
1794         DISPOSE(kopija)
1795       END
1796     END
1797   END
1798 END UbaciMonom;
1799
1800 PROCEDURE Unos(VAR p : Polinom);
1801 VAR
1802   i, n: CARDINAL;
1803   novi: Polinom;
1804 BEGIN
1805   Anuliraj(p);
1806   REPEAT
1807     WriteLn;
1808     WriteString('Unesite broj monoma n (n>=0) ');
1809     ReadCard(n);
1810   UNTIL Done;
1811   WriteLn;
1812   FOR i := 1 TO n DO
1813     NEW(novi);
1814     WITH novi^ DO
1815       REPEAT
1816         WriteString('Unesite koeficijent monoma br.');
1817         WriteCard(i, 1);
1818         WriteString(' (<> 0) ');
1819         ReadReal(k);
1820         WriteLn
1821       UNTIL k <> 0.0;
1822       REPEAT
1823         WriteLn;
1824         WriteString('Unesite eksponent monoma br.');
1825         WriteCard(i, 1);
1826         WriteString(' (>=0) ');
1827         ReadCard(st);
1828       UNTIL Done;
1829       WriteLn;
1830     END;
1831     UbaciMonom(novi, p);
1832     DISPOSE(novi);
1833   END
1834 END Unos;
1835
1836 PROCEDURE Saberi(p1, p2: Polinom; VAR zbir: Polinom);
1837 BEGIN
1838   Kopiraj(p1, zbir);
1839   WHILE p2 <> NIL DO
1840     UbaciMonom(p2, zbir);
1841     p2 := p2^.veza
1842   END
1843 END Saberi;
1844
1845 PROCEDURE SaberiNa(p: Polinom; VAR rez: Polinom);
1846 BEGIN
1847   WHILE p <> NIL DO
1848     UbaciMonom(p,rez);
1849     p := p^.veza;
1850   END;
1851 END SaberiNa;
1852
1853 PROCEDURE PromeniZnak(VAR p: Polinom);
1854 VAR
1855   t: Polinom;
1856 BEGIN
1857   t := p;
1858   WHILE t <> NIL DO
1859     t^.k := - t^.k;
1860     t := t^.veza
1861   END
1862 END PromeniZnak;
1863
1864 PROCEDURE Oduzmi(p1,p2: Polinom; VAR razlika: Polinom);
1865 BEGIN
1866   Kopiraj(p2, razlika);
1867   PromeniZnak(razlika);
1868   WHILE p1 <> NIL DO
1869     UbaciMonom(p1, razlika);
1870     p1 := p1^.veza
1871   END
1872 END Oduzmi;
1873
1874 PROCEDURE MonomPuta(p, mon: Polinom; VAR mp: Polinom);
1875 VAR
1876   tekuci: Polinom;
1877 BEGIN
1878   Anuliraj(mp);
1879   IF (mon <> NIL) AND (p <> NIL) THEN
1880     NEW(mp);
1881     mp^.k := p^.k * mon^.k;
1882     mp^.st := p^.st + mon^.st;
1883     p := p^.veza;
1884     tekuci := mp;
1885     WHILE p <> NIL DO
1886       NEW(tekuci^.veza);
1887       tekuci := tekuci^.veza;
1888       tekuci^.k := p^.k * mon^.k;
1889       tekuci^.st := p^.st + mon^.st;
1890       p := p^.veza
1891     END;
1892     tekuci^.veza := NIL
1893   END
1894 END MonomPuta;
1895
1896 PROCEDURE Puta(p1, p2: Polinom; VAR pr: Polinom);
1897 VAR
1898   pomocni: Polinom;
1899 BEGIN
1900   Anuliraj(pr);
1901   IF (p1 <> NIL) AND (p2 <> NIL) THEN
1902     MonomPuta(p1, p2, pr);
1903     p2 := p2^.veza;
1904     WHILE p2 <> NIL DO
1905       MonomPuta(p1, p2, pomocni);
1906       REPEAT
1907         UbaciMonom(pomocni, pr);
1908         pomocni := pomocni^.veza
1909       UNTIL pomocni = NIL;
1910       p2 := p2^.veza
1911     END
1912   END
1913 END Puta;
1914
1915 PROCEDURE Kolicnik(p1, p2: Polinom; VAR kol, ost: Polinom; VAR ok: BOOLEAN);
1916
1917   PROCEDURE Deli(VAR kol, ost: Polinom);
1918   VAR
1919     novi, pomocni: Polinom;
1920   BEGIN
1921     IF ost <> NIL THEN
1922       IF ost^.st >= p2^.st THEN
1923         NEW(novi);
1924         novi^.k := - ost^.k / p2^.k;
1925         novi^.st := ost^.st - p2^.st;
1926         MonomPuta(p2, novi, pomocni);
1927         Saberi(ost, pomocni, ost);
1928         novi^.k := - novi^.k;
1929         UbaciMonom(novi, kol);
1930         DISPOSE(novi);
1931         Deli(kol, ost)
1932       END
1933     END
1934   END Deli;
1935
1936 BEGIN (* Kolicnik *)
1937   ok := TRUE;
1938   Anuliraj(kol);
1939   IF p2 = NIL THEN
1940     ok := FALSE
1941   ELSE
1942     Kopiraj(p1, ost);
1943     Deli(kol, ost)
1944   END
1945 END Kolicnik;
1946
1947 PROCEDURE PolinomNaN(p: Polinom; n: CARDINAL;
1948                      VAR rez: Polinom);
1949 VAR
1950   i: CARDINAL;
1951 BEGIN
1952   IF n = 0 THEN
1953     NEW(rez);
1954     rez^.k := 1.0;
1955     rez^.st := 0;
1956     rez^.veza := NIL;
1957   ELSIF n = 1 THEN
1958         Kopiraj( p, rez );
1959   ELSE
1960     rez := p;
1961     FOR i := 2 TO n DO
1962       Puta(rez, p, rez)
1963     END
1964   END;
1965 END PolinomNaN;
1966
1967 PROCEDURE DisposePolinom(VAR p: Polinom);
1968 VAR
1969   pomocni: Polinom;
1970 BEGIN
1971   pomocni := p;
1972   WHILE pomocni # NIL DO
1973     p := p^.veza;
1974     DISPOSE(pomocni);
1975     pomocni := p
1976   END
1977 END DisposePolinom;
1978
1979 END PolinomL.
1980 \end{codeblock}
1981
1982
1983 \subsection{Zadatak: Sabiranje sa unapred određenim polinomom}
1984
1985 Želimo da ispišemo uneti polinom uvećan za\\ $x^5 - 3x^4 + 4x + 7$.
1986
1987 \begin{lstlisting}[style=codeblock]
1988 MODULE polinom;
1989 FROM PolinomL IMPORT Polinom, Stampaj, Anuliraj, DisposePolinom, UbaciMonom, Unos, Saberi;
1990 FROM InOut IMPORT WriteString, WriteLn;
1991 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1992
1993 VAR
1994   p,q,rez,pom : Polinom;
1995
1996 BEGIN
1997   (* korisnik unosi prvi polinom *)
1998   WriteString("Unesite polinom:");
1999   WriteLn;
2000   Unos(p);
2001   (* drugi polinom kreiramo mi,
2002      monom po monom *)
2003   Anuliraj(q); (* isto sto i q:=NIL; *)
2004   (* formiramo monom x^5 *)
2005   NEW(pom);
2006   pom^.st:=5;
2007   pom^.k:=1.0;
2008   (* dodajemo ga u polinom *)
2009   UbaciMonom(pom,q);
2010   DISPOSE(pom);
2011   (* -3 x^4 *)
2012   NEW(pom);
2013   pom^.st := 4;
2014   pom^.k := -3.0;
2015   UbaciMonom(pom,q);
2016   DISPOSE(pom);
2017   (* 4 x *)
2018   NEW(pom);
2019   pom^.st := 1;
2020   pom^.k := 4.0;
2021   UbaciMonom(pom,q);
2022   DISPOSE(pom);
2023   (* 7 (x^0) *)
2024   NEW(pom);
2025   pom^.st := 0;
2026   pom^.k := 7.0;
2027   UbaciMonom(pom,q);
2028   DISPOSE(pom);
2029   (* saberemo polinome *)
2030   Saberi(p, q, rez);
2031   (* odstampamo rezultat *)
2032   Stampaj(rez,0);
2033   WriteLn;
2034   (* oslobadjanje zauzete memorije *)
2035   DisposePolinom(p);
2036   DisposePolinom(q);
2037   DisposePolinom(rez);
2038 END polinom.
2039 \end{lstlisting}
2040
2041 \subsection{Zadatak: Suma k polinoma}
2042
2043 Napisati program koji ucitava broj k (1<=k<=50) i k polinoma, a nakon
2044 toga izracunava njihovu sumu
2045
2046 \begin{lstlisting}[style=codeblock]
2047 MODULE PolSuma;
2048
2049 FROM PolinomL IMPORT Polinom, Anuliraj, DisposePolinom, Unos, Stampaj, SaberiNa;
2050 FROM InOut IMPORT WriteLn, WriteString, ReadCard, WriteCard;
2051 CONST
2052   maxk = 50;
2053 TYPE
2054   nizPol = ARRAY [1..maxk] OF Polinom;
2055 VAR
2056   i, k: CARDINAL;
2057   suma : Polinom;
2058   p : nizPol;
2059 BEGIN
2060   REPEAT
2061     WriteString('Unesite broj k (1 <= k <= ');
2062     WriteCard(maxk, 1);
2063     WriteString(') ');
2064     ReadCard(k);
2065     WriteLn;
2066   UNTIL (1 <= k) AND (k <= maxk);
2067   FOR i := 1 TO k DO
2068     WriteLn;
2069     WriteString('Unos ');
2070     WriteCard(i, 1);
2071     WriteString('. polinoma.');
2072     WriteLn;
2073     Unos(p[i])
2074   END;
2075   Anuliraj(suma);
2076   FOR i := 1 TO k DO
2077     SaberiNa(suma, p[i])
2078   END;
2079   WriteLn;
2080   WriteString('Njihova suma je:');
2081   WriteLn;
2082   Stampaj(suma, 4);
2083   DisposePolinom(suma);
2084   FOR i := 1 TO k DO
2085     DisposePolinom(p[i]);
2086   END;
2087 END PolSuma.
2088 \end{lstlisting}
2089
2090 \section{Stek i red opsluživanja}
2091
2092 \subsection{Zadatak: Ilustracija pisanja u fajl uz pomoć bafera}
2093
2094 \begin{lstlisting}[style=codeblock]
2095 DEFINITION MODULE QueueInfo;
2096 CONST
2097   Maxqueue = 100;
2098 TYPE
2099   InfoTip = CHAR;
2100
2101 END QueueInfo.
2102
2103 IMPLEMENTATION MODULE QueueInfo;
2104 END QueueInfo.
2105
2106 DEFINITION MODULE RedOpsl1;
2107 FROM QueueInfo IMPORT InfoTip,Maxqueue;
2108 TYPE
2109   Niz = ARRAY[1..Maxqueue] OF InfoTip;
2110   RedOpslTip = RECORD
2111         Prvi, Zadnji : CARDINAL;
2112         Element : Niz
2113   END;
2114
2115 PROCEDURE MakeNull(VAR q : RedOpslTip);
2116 PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
2117 PROCEDURE First(VAR q : RedOpslTip;
2118                 VAR x : InfoTip;
2119                 VAR ok : BOOLEAN);
2120 PROCEDURE PopFirst(VAR q : RedOpslTip;
2121                    VAR ok : BOOLEAN);
2122 PROCEDURE AddRear(VAR q : RedOpslTip;
2123                   x : InfoTip;
2124                   VAR ok : BOOLEAN);
2125
2126 END RedOpsl1.
2127
2128 IMPLEMENTATION MODULE RedOpsl1;
2129 FROM QueueInfo IMPORT Maxqueue,InfoTip;
2130
2131 PROCEDURE MakeNull(VAR q : RedOpslTip);
2132 BEGIN
2133   WITH q DO
2134     Prvi := 0;
2135     Zadnji := 0
2136   END
2137 END MakeNull;
2138
2139 PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
2140 BEGIN
2141   RETURN q.Zadnji = 0
2142 END Empty;
2143
2144
2145 PROCEDURE First(VAR q : RedOpslTip;
2146                 VAR x : InfoTip;
2147                 VAR ok : BOOLEAN);
2148 BEGIN
2149   IF Empty(q) THEN
2150     ok := FALSE
2151   ELSE
2152     ok := TRUE;
2153     WITH q DO
2154       x := Element[Prvi]
2155     END
2156   END
2157 END First;
2158
2159 PROCEDURE AddOne(i : CARDINAL) : CARDINAL;
2160 BEGIN
2161   IF i = Maxqueue THEN
2162     RETURN 1
2163   ELSE
2164     RETURN i+1
2165   END
2166 END AddOne;
2167
2168 PROCEDURE PopFirst(VAR q : RedOpslTip;
2169                    VAR ok : BOOLEAN);
2170 BEGIN
2171   IF Empty(q) THEN
2172     ok := FALSE
2173   ELSE
2174     ok := TRUE;
2175     WITH q DO
2176       IF Prvi = Zadnji THEN
2177         MakeNull(q)
2178       ELSE
2179         Prvi := AddOne(Prvi)
2180       END
2181     END
2182   END
2183 END PopFirst;
2184
2185 PROCEDURE AddRear(VAR q : RedOpslTip;
2186                   x : InfoTip;
2187                   VAR ok : BOOLEAN);
2188 BEGIN
2189   WITH q DO
2190     IF AddOne(Zadnji) = Prvi THEN
2191       ok := FALSE
2192     ELSE
2193       ok := TRUE;
2194       IF Empty(q) THEN
2195         Prvi := 1;
2196         Zadnji := 1
2197       ELSE
2198         Zadnji := AddOne(Zadnji)
2199       END;
2200       Element[Zadnji] := x
2201     END
2202   END
2203 END AddRear;
2204
2205 END RedOpsl1.
2206
2207 MODULE Bafer;
2208 FROM RedOpsl1 IMPORT RedOpslTip, MakeNull, Empty, First, PopFirst, AddRear;
2209 FROM FIO IMPORT File,WrChar, Create, Close;
2210 IMPORT IO;
2211
2212 CONST
2213   ImeIzlaza = 'izlaz.txt';
2214
2215 VAR
2216   izlaz : File;
2217   znak : CHAR;
2218   buffer : RedOpslTip;
2219
2220 PROCEDURE IsprazniBafer(VAR dat : File;
2221                         VAR buf : RedOpslTip);
2222 VAR
2223   znak : CHAR;
2224   ok : BOOLEAN;
2225 BEGIN
2226   WHILE NOT Empty(buf) DO
2227     First(buf, znak, ok);
2228     PopFirst(buf, ok);
2229     WrChar(dat, znak)
2230   END
2231 END IsprazniBafer;
2232
2233 PROCEDURE BaferWrite(VAR dat : File;
2234                      VAR buf : RedOpslTip;
2235                      znak : CHAR);
2236 VAR
2237   ok : BOOLEAN;
2238 BEGIN
2239   AddRear(buf, znak, ok);
2240   IF NOT ok THEN
2241     IsprazniBafer(dat, buf);
2242     AddRear(buf, znak, ok)
2243   END
2244 END BaferWrite;
2245
2246 BEGIN
2247   izlaz := Create(ImeIzlaza);
2248   MakeNull(buffer);
2249   IO.WrStr('Unesite tekst, koji treba da se unese u datoteku ');
2250   IO.WrStr(ImeIzlaza);
2251   IO.WrChar('.');
2252   IO.WrLn;
2253   IO.WrStr('Unos zavrsite tackom.');
2254   IO.WrLn;
2255   znak := IO.RdChar();
2256   WHILE znak # '.' DO
2257     BaferWrite(izlaz, buffer, znak);
2258     znak := IO.RdChar();
2259   END;
2260   IsprazniBafer(izlaz, buffer);
2261   Close(izlaz)
2262 END Bafer.
2263 \end{lstlisting}
2264
2265 \subsection%
2266 {Zadatak: Ispitivanje da li reč pripada gramatici wcw$^+$}
2267
2268 Reč pripada ovoj gramatici ako joj se prvi deo (w) sastoji samo od
2269 slova 'a' i 'b', sledi slovo 'c' a nakon njega obrnuta reč reči w.
2270
2271 \begin{lstlisting}[style=codeblock]
2272 DEFINITION MODULE Stek;
2273 CONST
2274   Maxstack = 100;
2275 TYPE
2276   Niz = ARRAY [1..Maxstack] OF CHAR;
2277   StekTip = RECORD
2278             Top : CARDINAL;
2279             Element : Niz
2280           END;
2281 PROCEDURE MakeNull(VAR s : StekTip);
2282 PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
2283
2284 PROCEDURE Top(VAR s : StekTip;
2285               VAR x : CHAR;
2286               VAR ok : BOOLEAN);
2287 PROCEDURE Pop(VAR s : StekTip;
2288               VAR ok : BOOLEAN);
2289 PROCEDURE Push(VAR s : StekTip;
2290                x : CHAR;
2291                VAR ok : BOOLEAN);
2292 END Stek.
2293
2294
2295 IMPLEMENTATION MODULE Stek;
2296
2297 PROCEDURE MakeNull(VAR s : StekTip);
2298 BEGIN
2299   s.Top := 0
2300 END MakeNull;
2301
2302 PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
2303 BEGIN
2304   RETURN s.Top = 0
2305 END Empty;
2306
2307 PROCEDURE Top(VAR s : StekTip;
2308               VAR x : CHAR;
2309               VAR ok : BOOLEAN);
2310 BEGIN
2311   IF Empty(s) THEN
2312     ok := FALSE
2313   ELSE
2314     ok := TRUE;
2315     WITH s DO
2316       x := Element[Top]
2317     END
2318   END
2319 END Top;
2320
2321 PROCEDURE Pop(VAR s : StekTip;
2322               VAR ok : BOOLEAN);
2323 BEGIN
2324   IF Empty(s) THEN
2325     ok := FALSE
2326   ELSE
2327     ok := TRUE;
2328     DEC(s.Top)
2329   END
2330 END Pop;
2331
2332 PROCEDURE Push(VAR s : StekTip;
2333                x : CHAR;
2334                VAR ok : BOOLEAN);
2335 BEGIN
2336   WITH s DO
2337     IF Top = Maxstack THEN
2338       ok := FALSE
2339     ELSE
2340       ok := TRUE;
2341       INC(Top);
2342       Element[Top] := x
2343     END
2344   END
2345 END Push;
2346 END Stek.
2347
2348 MODULE wcw;
2349 (* Da li rec pripada gramatici wcw+. *)
2350 FROM Stek IMPORT StekTip, MakeNull, Empty,
2351                  Top, Pop, Push;
2352 FROM InOut IMPORT Read, Write, WriteString, EOL;
2353 TYPE
2354   slova = SET OF CHAR;
2355 VAR
2356   S : StekTip;
2357   Ch, C : CHAR;
2358   ok : BOOLEAN;
2359 BEGIN
2360   MakeNull(S);
2361   Read(Ch);
2362   ok := TRUE;
2363   WHILE ok AND (Ch IN slova{'a', 'b'}) DO
2364     Push(S, Ch, ok);
2365     Read(Ch);
2366   END;
2367   IF NOT ok THEN
2368     WriteString('Greska - mali stek')
2369   ELSIF Ch # 'c' THEN
2370     WriteString('Pogresan string')
2371   ELSE
2372     Read(Ch);
2373     WHILE ok AND (Ch # EOL) DO
2374       Top(S, C, ok);
2375       ok := ok AND (C = Ch);
2376       IF ok THEN
2377         Pop(S, ok);
2378         Read(Ch);
2379       END
2380     END;
2381     IF NOT (ok AND Empty(S)) THEN
2382       WriteString('Pogresan string')
2383     ELSE
2384       WriteString('String pripada jeziku L')
2385     END
2386   END
2387 END wcw.
2388 \end{lstlisting}
2389
2390 \subsection{Zadatak: Kalkulator za izračunavanje postfiksnih izraza}
2391
2392
2393 Napraviti kalkulator za izračunavanje postfiksnih izraza. Svi brojevi
2394 koji figurišu u izrazu su jednocifreni.
2395
2396 \begin{lstlisting}[style=codeblock]
2397 MODULE PostFix;
2398
2399 FROM StekI IMPORT StekTip, MakeNull, Empty, Top, Pop, Push;
2400 FROM InOut IMPORT Read, Write, WriteInt, EOL;
2401 TYPE
2402   slova = SET OF CHAR;
2403 VAR
2404   S : StekTip;
2405   Ch : CHAR;
2406   Op1, Op2 : INTEGER;
2407   ok : BOOLEAN;
2408 PROCEDURE Conv(Ch : CHAR) : INTEGER;
2409 BEGIN
2410   RETURN  ORD(Ch) - ORD('0')
2411 END Conv;
2412
2413 BEGIN
2414   MakeNull(S);
2415   Read(Ch);
2416   WHILE Ch # EOL DO
2417     IF Ch IN slova{'+', '-', '/', '*', '%'} THEN
2418       Top(S, Op2, ok);
2419       Pop(S, ok);
2420       Top(S, Op1, ok);
2421       Pop(S, ok);
2422       CASE Ch OF
2423         '+' : Op1 := Op1 + Op2 |
2424         '-' : Op1 := Op1 - Op2 |
2425         '*' : Op1 := Op1 * Op2 |
2426         '/' : Op1 := Op1 DIV Op2 |
2427         '%' : Op1 := Op1 MOD Op2
2428       END;
2429       Push(S, Op1, ok)
2430     ELSE
2431       Push(S, Conv(Ch), ok)
2432     END;
2433     Read(Ch);
2434   END;
2435   Top(S, Op1, ok);
2436   Write('=');
2437   WriteInt(Op1,5)
2438 END PostFix.
2439 \end{lstlisting}
2440
2441
2442 \section{Simulacija rekurzije}
2443
2444
2445 Na početku označiti sve rekurzivne pozive u originalnoj proceduri
2446 adresama (npr. 1,2,3... ili konstante nabrojivog tipa podataka).
2447
2448 Na steku se čuvaju lokalne promenljive, parametri procedure i adresa
2449 mesta poziva, a u skladu sa tim se kreira InfoTip.
2450
2451 Trivijalnim pozivom se smatra onaj koji se izračunava bez dodatnih
2452 rekurzivnih poziva.
2453
2454 U kodu ispod, \kod{treba\_rekurzija} znači da je poziv netrivijalan,
2455 odnosno treba naći uslove pod kojima se sigurno dešavaju rekurzivni
2456 pozivi.
2457
2458 \begin{lstlisting}
2459 MakeNull(S);
2460 REPEAT
2461   WHILE treba_rekurzija DO
2462     -prepisati sve od pocetka originalne
2463      procedure do prvog rekurzivnog poziva
2464     -staviti na stek potrebne
2465      lokalne promenljive, parametre procedure i
2466      adresu mesta poziva
2467     -podesiti vrednosti parametara da budu
2468      kao u rekurzivnom pozivu procedure
2469   END;
2470   trivijalan poziv
2471   umesto RETURN x pisati rez := x
2472   jos := TRUE;
2473   WHILE jos AND NOT Empty(S) DO
2474     Top(S, el, ok);
2475     Pop(S, ok);
2476     -restauriramo vrednosti sa steka
2477     -u zavisnosti od adrese poziva nastavimo
2478      prepisivanje originalne procedure sa
2479      tog mesta
2480     -ako se dodje do novog rek. poziva tada:
2481        -sacuvati na steku vrednosti
2482        -podesiti vrednosti parametara da budu
2483         kao u rekurzivnom pozivu procedure
2484        -ici na pocetak koda
2485         (ovo se postize sa jos := FALSE)
2486     -inace
2487        ako se naidje na RETURN x pisati rez := x
2488   END
2489 UNTIL Empty(S);
2490 \end{lstlisting}
2491
2492 Ako je procedura funkcijska tada se na kraj dodaje \kod{RETURN rez}.
2493
2494 \subsection*{ZADACI}
2495
2496 Simulirati ponašanje sledećih rekurzivnih procedura (funkcija) upotrebom steka:
2497
2498 \subsection{Primer 1 -- faktorijel}
2499
2500
2501 \begin{lstlisting}[style=codeblock]
2502 MODULE Fakto;
2503 (* InfoTip = CARDINAL; *)
2504
2505 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2506 FROM StekC IMPORT StekTip, MakeNull, Empty,
2507                   Top, Pop, Push;
2508 VAR
2509   n : CARDINAL;
2510 PROCEDURE RFakto(n : CARDINAL) : CARDINAL;
2511 BEGIN
2512   IF n <= 1 THEN
2513     RETURN 1
2514   ELSE
2515     RETURN n * RFakto(n-1)
2516   END
2517 END RFakto;
2518
2519
2520 PROCEDURE SFakto(n : CARDINAL) : CARDINAL;
2521 VAR
2522   s : StekTip;
2523   rez : CARDINAL;
2524   OK : BOOLEAN;
2525 BEGIN
2526   MakeNull(s);
2527   WHILE n > 1 DO
2528     Push(s,n,OK);
2529     DEC(n)
2530   END;
2531   rez := 1;
2532   WHILE NOT Empty(s) DO
2533     Top(s, n, OK);
2534     Pop(s, OK);
2535     rez := n * rez
2536   END;
2537   RETURN rez
2538 END SFakto;
2539
2540 BEGIN
2541   WrStr('n = ');
2542   n := RdCard();
2543   WrLn
2544   WrStr('n! = ');
2545   WrCard(RFakto(n), 1);
2546   WrStr(' = ');
2547   WrCard(SFakto(n), 1)
2548 END Fakto.
2549 \end{lstlisting}
2550
2551 \subsection{Primer 2 -- stepenovanje}
2552
2553 \begin{lstlisting}[style=codeblock]
2554 MODULE Step;
2555 (* InfoTip = RECORD
2556                 x : REAL;
2557                 n : CARDINAL;
2558                 adr : (par, nepar)
2559              END;
2560 *)
2561
2562 FROM IO IMPORT WrStr, WrLn, WrReal,
2563         RdReal, RdCard;
2564 FROM StekStep IMPORT StekTip, MakeNull, Empty,
2565              Top, Pop, Push, InfoTip, AdrTip;
2566
2567 VAR
2568   n : CARDINAL;
2569   x : REAL;
2570
2571 PROCEDURE Sqr(y : REAL) : REAL;
2572 BEGIN
2573   RETURN y * y
2574 END Sqr;
2575
2576 PROCEDURE RStep(x : REAL;
2577                 n : CARDINAL) : REAL;
2578 BEGIN
2579   IF n = 0 THEN
2580     RETURN 1.
2581   ELSIF ODD(n) THEN
2582     RETURN x * Sqr( RStep(x, n DIV 2) )
2583   ELSE
2584     RETURN Sqr( RStep(x, n DIV 2) )
2585   END
2586 END RStep;
2587
2588 PROCEDURE SStep(x : REAL;
2589                 n : CARDINAL ) : REAL;
2590 VAR
2591   s : StekTip;
2592   OK : BOOLEAN;
2593   rez : REAL;
2594   el : InfoTip;
2595 BEGIN
2596   MakeNull(s);
2597   WHILE n > 0 DO
2598     el.x := x;
2599     el.n := n;
2600     IF ODD(n) THEN
2601       el.adr := nepar;
2602     ELSE
2603       el.adr := par
2604     END;
2605     Push(s,el,OK);
2606     n := n DIV 2
2607   END;
2608   rez := 1.;
2609   WHILE NOT Empty(s) DO
2610     Top(s, el, OK);
2611     Pop(s, OK);
2612     x := el.x;
2613     n := el.n;
2614     IF el.adr = nepar THEN
2615       rez := x * Sqr(rez)
2616     ELSE
2617       rez := Sqr(rez)
2618     END
2619   END;
2620   RETURN rez
2621 END SStep;
2622
2623 BEGIN
2624   WrStr('x =? ');
2625   x := RdReal();
2626   WrLn;
2627   WrStr('n =? ');
2628   n := RdCard();
2629   WrStr('x^n = ');
2630   WrReal(RStep(x, n), 10, 1);
2631   WrStr(' = ');
2632   WrReal(SStep(x, n), 10, 1)
2633 END Step.
2634 \end{lstlisting}
2635
2636 \subsection{Primer 3 -- Fibonači}
2637
2638 \begin{lstlisting}[style=codeblock]
2639 MODULE Fib;
2640 (* InfoTip = RECORD
2641                 n : CARDINAL;
2642                 PrviSab : CARDINAL;
2643                 adr : (prvi, drugi)
2644              END;
2645 *)
2646
2647 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2648 FROM StekFib IMPORT StekTip, MakeNull, Empty,
2649        Top, Pop, Push, InfoTip, AdrTip;
2650 VAR
2651   n : CARDINAL;
2652
2653 PROCEDURE RFib(n : CARDINAL) : CARDINAL;
2654 BEGIN
2655   IF n <= 1 THEN
2656     RETURN n
2657   ELSE
2658     RETURN RFib(n-1) + RFib(n-2)
2659   END
2660 END RFib;
2661
2662 PROCEDURE SFib(n : CARDINAL ) : CARDINAL;
2663 VAR
2664   s : StekTip;
2665   OK, jos : BOOLEAN;
2666   rez, PrviSab : CARDINAL;
2667   el : InfoTip;
2668 BEGIN
2669   MakeNull(s);
2670   REPEAT
2671     WHILE n > 1 DO
2672       el.n := n;
2673       el.adr := prvi;
2674       Push(s,el,OK);
2675       DEC(n)
2676     END;
2677     rez := (n);
2678     jos := TRUE;
2679     WHILE (NOT Empty(s)) AND jos DO
2680       Top(s, el, OK);
2681       Pop(s, OK);
2682       n := el.n;
2683       IF el.adr = prvi THEN
2684         PrviSab := rez;
2685         el.n := n;
2686         el.adr := drugi;
2687         el.PrviSab := PrviSab;
2688         Push(s, el, OK);
2689         DEC(n, 2);
2690         jos := FALSE
2691       ELSE
2692         PrviSab := el.PrviSab;
2693         rez := PrviSab + rez
2694       END
2695     END
2696   UNTIL Empty(s);
2697   RETURN rez
2698 END SFib;
2699
2700 BEGIN
2701   WrStr('n =? ');
2702   n := RdCard();
2703   WrStr('F(n) = ');
2704   WrCard(RFib(n), 1);
2705   WrStr(' = ');
2706   WrCard(SFib(n), 1)
2707 END Fib.
2708 \end{lstlisting}
2709
2710 \subsection{Primer 4 -- faktorijel 2}
2711
2712
2713 \begin{lstlisting}[style=codeblock]
2714 MODULE Faktor;
2715 (* InfoTip = CARDINAL; *)
2716 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2717 FROM StekC IMPORT StekTip, MakeNull, Empty,
2718                   Top, Pop, Push;
2719
2720 VAR
2721   n,rez : CARDINAL;
2722
2723 PROCEDURE RFakto(n : CARDINAL;
2724                  VAR rez : CARDINAL);
2725 BEGIN
2726   IF n = 0 THEN
2727     rez := 1
2728   ELSE
2729     RFakto(n-1, rez);
2730     rez := n * rez
2731   END
2732 END RFakto;
2733
2734 PROCEDURE SFakto(n : CARDINAL;
2735                  VAR rez : CARDINAL);
2736 VAR
2737   s : StekTip;
2738   OK : BOOLEAN;
2739 BEGIN
2740   MakeNull(s);
2741   WHILE n > 0 DO
2742     Push(s,n,OK);
2743     DEC(n)
2744   END;
2745   rez := 1;
2746   WHILE NOT Empty(s) DO
2747     Top(s, n, OK);
2748     Pop(s, OK);
2749     rez := n * rez
2750   END
2751 END SFakto;
2752
2753 BEGIN
2754   WrStr('n =? ');
2755   n := RdCard();
2756   WrLn;
2757   WrStr('n! = ');
2758   RFakto(n, rez);
2759   WrCard(rez, 1);
2760   WrStr(' = ');
2761   SFakto(n, rez);
2762   WrCard(rez, 1)
2763 END Faktor.
2764 \end{lstlisting}
2765
2766 \subsection{Primer 5 (ispitni)}
2767
2768
2769 \begin{lstlisting}[style=codeblock]
2770 MODULE Rek1;
2771 (* InfoTip = RECORD
2772                 d, g, m1, m2 : INTEGER;
2773                 adr : (prvi, drugi)
2774              END;
2775 *)
2776 FROM Stek1 IMPORT StekTip, adresa, InfoTip,
2777          MakeNull, Empty, Top, Pop, Push;
2778 IMPORT IO;
2779 VAR
2780   X : ARRAY [1..20] OF INTEGER;
2781
2782 PROCEDURE Max(d, g: INTEGER) : INTEGER;
2783 VAR
2784   m1, m2 : INTEGER;
2785 BEGIN
2786   IF d>g THEN
2787     RETURN MIN(INTEGER)
2788   ELSIF d=g THEN
2789     RETURN X[d]
2790   ELSE
2791     m1 := Max(d, (d+g) DIV 2);
2792     m2 := Max((d+g) DIV 2 +1, g);
2793     IF m1 > m2 THEN
2794       RETURN m1
2795     ELSE
2796       RETURN m2
2797     END
2798   END
2799 END Max;
2800
2801 PROCEDURE SMax(d, g: INTEGER) : INTEGER;
2802 VAR
2803   S : StekTip;
2804   el : InfoTip;
2805   ok, jos : BOOLEAN;
2806   m1, m2, rez : INTEGER;
2807 BEGIN
2808   MakeNull(S);
2809   REPEAT
2810     WHILE d<g DO
2811       el.d := d;
2812       el.g := g;
2813       el.adr := prvi;
2814       Push(S, el, ok);
2815       g := (d+g) DIV 2
2816     END;
2817     IF d>g THEN
2818       rez := MIN(INTEGER)
2819     ELSE (* d=g *)
2820       rez := X[d]
2821     END;
2822     jos := TRUE;
2823     WHILE jos AND NOT Empty(S) DO
2824       Top(S, el, ok);
2825       Pop(S, ok);
2826       d := el.d;
2827       g := el.g;
2828       m1 := el.m1;
2829       IF el.adr = prvi THEN
2830         m1 := rez;
2831         el.m1 := m1;
2832         el.adr := drugi;
2833         Push(S, el, ok);
2834         d := (d+g) DIV 2 + 1;
2835         jos := FALSE
2836       ELSE (*el.adr = drugi*)
2837         m2 := rez;
2838         IF m1 > m2 THEN
2839           rez := m1
2840         ELSE
2841           rez := m2
2842         END
2843       END
2844     END
2845   UNTIL Empty(S);
2846   RETURN rez
2847 END SMax;
2848
2849 BEGIN (* glavni program *)
2850   X[1] := 3;
2851   X[2] := 2;
2852   X[3] := 5;
2853   X[4] := -7;
2854   X[5] := 0;
2855   IO.WrCard(Max(1, 5), 3);
2856   IO.WrLn;
2857   IO.WrCard(SMax(1, 5), 3);
2858   IO.WrLn
2859 END Rek1.
2860 \end{lstlisting}
2861
2862 \subsection{Primer 6 (ispitni)}
2863
2864
2865 \begin{lstlisting}[style=codeblock]
2866 MODULE Rek2;
2867 (* InfoTip = RECORD
2868                 x, y, n : CARDINAL;
2869                 adr : (prvi, drugi, treci, cetvrti)
2870              END;
2871 *)
2872 FROM Stek2 IMPORT StekTip, adresa, InfoTip,
2873            MakeNull, Empty, Top, Pop, Push;
2874 IMPORT IO;
2875
2876 PROCEDURE g(x : CARDINAL; y : CARDINAL;
2877             n : CARDINAL) : CARDINAL;
2878 BEGIN
2879   IF n < 3 THEN
2880     RETURN x + y
2881   ELSIF ODD(n) THEN
2882     RETURN g(g(x+1, y, n-2), y, n-3)
2883   ELSE
2884     RETURN g(x, g(x, y+1, n-2), n-3)
2885   END
2886 END g;
2887
2888 PROCEDURE Sg(x : CARDINAL; y : CARDINAL;
2889              n : CARDINAL) : CARDINAL;
2890 VAR
2891   S : StekTip;
2892   el : InfoTip;
2893   ok, jos : BOOLEAN;
2894   rez : CARDINAL;
2895 BEGIN
2896   MakeNull(S);
2897   REPEAT
2898     WHILE n >= 3 DO
2899       IF ODD(n) THEN
2900         el.x := x;
2901         el.y := y;
2902         el.n := n;
2903         el.adr := prvi;
2904         Push(S, el, ok);
2905         INC(x);
2906         DEC(n, 2)
2907       ELSE
2908         el.x := x;
2909         el.y := y;
2910         el.n := n;
2911         el.adr := treci;
2912         Push(S, el, ok);
2913         INC(y);
2914         DEC(n, 2)
2915       END
2916     END;
2917     rez := x+y;
2918     jos := TRUE;
2919     WHILE jos AND NOT Empty(S) DO
2920       Top(S, el, ok);
2921       Pop(S, ok);
2922       x := el.x;
2923       y := el.y;
2924       n := el.n;
2925       IF el.adr = prvi THEN
2926         el.adr := drugi;
2927         Push(S, el, ok);
2928         x := rez;
2929         DEC(n, 3);
2930         jos := FALSE
2931       ELSIF el.adr = treci THEN
2932         el.adr := cetvrti;
2933         Push(S, el, ok);
2934         y := rez;
2935         DEC(n, 3);
2936         jos := FALSE
2937       END
2938     END
2939   UNTIL Empty(S);
2940   RETURN rez
2941 END Sg;
2942
2943 BEGIN (* glavni program *)
2944   IO.WrCard(g(2, 3, 10), 3);
2945   IO.WrCard(Sg(2, 3, 10), 3);
2946 END Rek2.
2947 \end{lstlisting}
2948
2949 %\columnbreak
2950
2951 \appendix
2952
2953 \section{Native XDS Modula 2 -- kratko uputstvo}
2954
2955
2956 Ovo uputstvo ukratko pokriva kako se može nabaviti XDS Modula 2 za Windows
2957 sistem, njenu instalaciju, te kako napraviti i pokretnuti jednostavan program.
2958
2959 \subsection*{Dobavljanje instalacije}
2960
2961
2962 Native XDS Modula 2 se može besplatno skinuti sa sajta proizvođača,
2963 \url{http://www.excelsior-usa.com/}, tačnije na adresi:
2964
2965 \url{http://www.excelsior-usa.com/xdsdl.html}
2966
2967 Prvo se prikazuje ugovor o korišćenju koji na dnu treba potvrditi da ste
2968 razumeli i da ćete ga se pridržavati.
2969
2970 Na stranici koja se potom otvara je potrebno odabrati ``XDS 2.6 beta 2
2971 for Windows'' i snimiti je na računar.
2972
2973 \subsection*{Instalacija okruženja}
2974
2975 Osnovno okruženje (xds-x86...) se instalira pokretanjem prethodno pomenute
2976  instalacione arhive.
2977
2978 \emph{Korisnicima Windows-a 7 preporučujemo da pokrenu instalacione
2979   pakete pomoću opcije ``Run as administrator'' do koje se stiže desnim
2980   klikom miša.}
2981
2982 Pretpostavićemo u daljem tekstu da je program instaliran u
2983 \kod{C:/XDS/}
2984
2985 \subsection*{Pokretanje okruženja}
2986
2987 Po uspešnoj instalaciji bi trebalo da postoji ikonica na desktopu, kao
2988 i grupa sa programom u start meniju.
2989
2990 Ukoliko iz bilo kakvog razloga ne postoje odgovarajuće prečice,
2991 okruženje se može pokrenuti uz pomoć izvršnog fajla
2992 \kod{C:/XDS/BIN/xds.exe} (ako je instalirano na podrazumevanoj
2993 lokaciji).
2994
2995 \subsection*{Prvi projekat}
2996
2997 Da bismo mogli da pišemo i pokrećemo svoj program, potrebno je prvo
2998 napraviti projekat za njega, što se radi na sledeći način:
2999
3000 \begin{itemize}
3001
3002 \item
3003  Iz menija se odabere Project->New.
3004 \item U dijalogu se klikne na gornje dugme ``Browse'', odabere se putanja gde
3005   će se kreirati projekat i ukuca se ime novog projekta.
3006
3007 \item U drugom polju ``Template'' ne treba da piše ništa. Ukoliko
3008   postoji neki tekst, obrisati ga.
3009
3010 \item Kliknuti na ``OK''
3011
3012 \item Iskočiće dijalog na kome piše da ne postoji fajl za editovanje,
3013   kliknuti na ``OK'' da se on napravi.
3014
3015 \item Pojavljuje se forma za kucanje programa, ukucati (na primer):
3016
3017 \begin{minipage}{\columnwidth}
3018 \begin{lstlisting}[style=codeblock]
3019   MODULE Hello;
3020   FROM InOut IMPORT WriteString,WriteLn;
3021   BEGIN
3022     WriteString("Hello World");
3023     WriteLn;
3024   END Hello.
3025 \end{lstlisting}
3026 \end{minipage}
3027
3028 \item Program se može pokrenuti na različite načine, pri čemu se
3029   automatski prevodi:
3030
3031   \begin{itemize}
3032
3033   \item Klik na ``Run'' ikonicu u toolbaru (plavi čovečuljak koji trči)
3034
3035   \item Meni Debug->Run
3036
3037   \item Prečica Ctrl+F9 na tastaturi
3038
3039   \end{itemize}
3040
3041 \item Ako je sve u redu sa programom, treba da se pojavi novi terminal
3042   u kome se ispisuje rezultat izvršavanja programa, u našem slučaju
3043   jednostavna pozdravna poruka.
3044 \end{itemize}
3045
3046 Naravno moguće je i samo prevesti (kompajlirati) program, tako da se
3047 samo prikažu greške (ako ih ima) i bez pokretanja programa:
3048 \begin{itemize}
3049 \item Klik na ``Compile'' ikonicu u toolbaru
3050 \item Meni Tools->Compile
3051 \item Prečica F9 na tastaturi
3052 \end{itemize}
3053
3054 Ukoliko u programu postoje greške, on neće biti pokrenut, već će se
3055 dobiti lista grešaka u donjem delu prozora. Na primer ako obrišemo ``S''
3056 u četvrtom redu i probamo da pokrenemo program, taj red će biti
3057 označen svetlo plavom bojom i dobićemo poruku:
3058
3059 \kod{- Error in pro1.mod [4:5]: Undeclared identifier "Writeting"}
3060
3061 Što znači da u četvrtom redu, kod petog karatkera postoji problem, da
3062 identifikator nije deklarisan, što najčešće znači da ga nismo uvezli,
3063 ili, kao u našem slučaju, da smo napravili grešku u kucanju.
3064
3065 Stvar na koju isto treba obratiti pažnju je da se nekad greška
3066 prijavljue nešto kasnije u tekstu nego što je napravljena. Na primer,
3067 ako obrišemo ``;'' na kraju četvrtog reda i probamo da pokrenemo
3068 program, peti red će biti označen svetlo plavom bojom i dobićemo
3069 poruku:
3070
3071 \kod{- Error in pro1.mod [5:5]: Expected symbol ";" }
3072
3073 Ovo se desilo jer nedostaje tačka zarez na kraju četvrtog reda, ali će
3074 kompajler probati da je traži i dalje, pa će tek na početku petog reda
3075 prijaviti grešku.
3076
3077 U spisku se takođe pojavljuje i upozorenje (Warning) o tome da se
3078 uvezena komanda WriteString ne koristi nigde u programu. Često se
3079 upozorenja mogu ignorisati, a pažnju uglavnom treba obraćati na
3080 greške, odnosno poruke koje počinju sa ``Error''.
3081
3082 Takođe se često dešava da su druge prijavljene greške posledica prve,
3083 te je poželjno ponovo kompajlirati (ili pokretati) program posle svake
3084 ispravljene greške.
3085
3086 \paragraph{Napomena o template-ovima pri kreiranju projekta:}
3087 Moguće je namestiti da u dijalogu za novi projekat drugo polje ``Template''
3088  uvek bude prazno. Potrebno je u tom istom dijalogu kliknuti na
3089  ``Configure'', a potom isprazniti polje ``default template''.
3090
3091 \subsection{Mogući problemi}
3092
3093 \subsubsection*{Nedostajući sistemski moduli}
3094
3095 Verzije pre 2.6 nisu imale uključene u glavni paket sve module koji se
3096 koriste u okviru kursa, i bilo je neophodno da se dodatno instalira i
3097 ``Top Speed Compatibility Pack'' (tscp-x86...). Bez njega je kompajler
3098 prijavljivao da ne postoje neki moduli - najčešće je problem bio da
3099 nedostaje \kod{FIO} modul.
3100
3101 \subsubsection*{Problemi u pokretanju - nemoguće naći exe}
3102
3103 Ako pri pokušaju kompajliranja/pokretanja programa kompajler prijavi
3104 da ne može da nađe exe i pri tome prijavljuje kraću putanju od one
3105 koja je stvarno u pitanju, obično se radi o tome da je postojao razmak
3106 u okviru putanje do modula. Npr ``C:\textbackslash Moj prvi program''
3107 će prouzrokovati probleme, a kompajler će prijaviti da ne može da nađe
3108 ``C:\textbackslash Moj''.
3109
3110 Ovo je nažalost problem okruženja i dok se ne ispravi u nekoj budućoj
3111 verziji ne može se zaobići, tako da je jedino rešenje premestiti
3112 fajlove, odnosno ako je moguće preimenovati problematične foldere.
3113
3114 \mainend
3115
3116 \end{document}