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{Rad sa fajlovima}
 566
 567 \subsection{Modul FIO}
 568
 569 U ovom modulu je definisan tip \kod{File}, koji predstavlja jedan fajl
 570 sa kojim radimo. Da bi ga koristili moramo ga uvesti u program (isto
 571 kao što uvozimo i komande).
 572
 573 \begin{quote}U primerima se pretpostavlja da je ``f'' tipa \kod{File}, ``str'' niz
 574 znakova, ``i'' tipa \kod{INTEGER}, ``c'' tipa \kod{CARDINAL} i ``ch''
 575 tipa \kod{CHAR}. Dodatna promenljiva ``n'' tipa \kod{INTEGER} služi za
 576 formatiranje slično kao u modulu \kod{InOut}.
 577 \end{quote}
 578
 579 Promenljiva tipa \kod{File} se mora vezati za neki fajl
 580 jednom od sledećih komandi:
 581 \begin{itemize}
 582 \item \kod{f := Open(str);} -- otvara se postojeci fajl za čitanje\\
 583 \item \kod{f := Create(str);} -- kreira se fajl za pisanje\\
 584 \item \kod{f := Append(str);} -- otvara se postojeći fajl za
 585   dopisivanje na kraj
 586 \end{itemize}
 587
 588 Po završetku rada fajl se mora zatvoriti, u našem primeru to bi bilo
 589 \kod{Close(f);}
 590
 591 Procedure za čitanje i pisanje su vrlo slične onima iz modula
 592 \kod{IO}, osim što imaju dodatni parametar „\kod{f}“ koji označava
 593 fajl sa kojim se radi.
 594 \begin{itemize}
 595 \item \kod{RdStr(f,str)} -- učitava ceo red u string str\\
 596 \item   \kod{RdItem(f,str)} -- učitava jednu reč u string str (učitava znakove iz fajla dok ne naiđe na separator)\\
 597 \item   \kod{i:= RdInt(f); c:= RdCard(f)} -- učitava broj, koji se dobija kao rezultat procedure\\
 598 \item   \kod{ch:= RdChar(f)} -- vraća jedan znak iz fajla
 599 \end{itemize}
 600
 601 Analogne su i procedure za pisanje različitih tipova u fajl:
 602 \begin{itemize}
 603 \item \kod{WrStr(f,str); WrInt(f,i,n);}\ \kod{WrCard(f,c,n);}\
 604   \kod{WrChar(f,ch);}
 605 \end{itemize}
 606
 607
 608 Prelom reda se eksplicitno upisuje u fajl komandom \kod{WrLn(f);}.
 609
 610 Da bi odredili da li smo stigli do kraja fajla možemo koristiti
 611 \kod{EOF}. U pitanju je logička promenljiva koja se uvozi iz modula
 612 FIO kao bilo kakva normalna komanda. Ona označava da li smo poslednjom
 613 operacijom čitanja stigli do kraja fajla.  Ne menja joj se vrednost
 614 pri operacijama otvaranja i zatvaranja fajlova, odnosno neće se pri
 615 tome resetovati na \kod{FALSE}, pa na ovo treba obratiti pažnju pri
 616 radu.
 617
 618 \subsection{Zadatak: ispis sadržaja fajla na ekran}
 619
 620 Potrebno je sve redove iz fajla učitati i ispisati ih na ekran.
 621
 622 \begin{lstlisting}[style=codeblock]
 623 MODULE ispis;
 624 FROM FIO IMPORT File, Open, Close, EOF, RdStr;
 625 FROM InOut IMPORT WriteString, WriteLn, ReadString;
 626
 627 PROCEDURE ispisF(ime: ARRAY OF CHAR);
 628 VAR
 629   f:File;
 630   s : ARRAY[1..100] OF CHAR;
 631 BEGIN
 632   f:=Open(ime);
 633   EOF := FALSE;
 634   WHILE NOT EOF DO
 635       RdStr(f,s);
 636       WriteString(s);
 637       WriteLn;
 638   END;
 639   Close(f);
 640 END ispisF;
 641
 642 VAR
 643   ime: ARRAY[1..100] OF CHAR;
 644 BEGIN
 645   WriteString("unesite ime fajla:");
 646   ReadString(ime);
 647   ispisF(ime);
 648 END ispis.
 649 \end{lstlisting}
 650
 651 \subsection{Zadatak: spisak studenata}
 652
 653 Napraviti program koji iz fajla učitava podatke o studentima, dodaje
 654 novog studenta u spisak i snima fajl.  U fajlu se u svakom redu nalazi
 655 podatak o jednom studentu, redom prezime, ime i godina rođenja,
 656 razdvojeni razmacima.
 657
 658 \begin{lstlisting}[style=codeblock]
 659 MODULE nizslog;
 660 FROM InOut IMPORT WriteString, WriteLn,
 661      WriteCard, ReadCard, ReadString;
 662 FROM FIO IMPORT File, Open, Create, Close, EOF,
 663     RdItem, RdCard, WrStr, WrCard, WrLn;
 664 FROM Str IMPORT Compare;
 665
 666 CONST
 667     MaxStud = 100;
 668 TYPE
 669     String = ARRAY[1..30] OF CHAR;
 670     Student = RECORD
 671         ime, prez: String;
 672         god: CARDINAL;
 673     END;
 674     Studenti = ARRAY[1..MaxStud] OF Student;
 675
 676 PROCEDURE UcitajF(fajl:String;
 677           VAR spisak: Studenti; VAR n:CARDINAL);
 678 VAR
 679     f:File;
 680 BEGIN
 681     n:=0;
 682     f:= Open(fajl);
 683     EOF := FALSE;
 684     WHILE NOT EOF DO
 685         INC(n);
 686         RdItem(f, spisak[n].prez);
 687         RdItem(f, spisak[n].ime);
 688         spisak[n].god := RdCard(f);
 689     END;
 690     Close(f);
 691 END UcitajF;
 692
 693 PROCEDURE Ispisi(spisak:Studenti; n:CARDINAL);
 694 VAR
 695     i: CARDINAL;
 696 BEGIN
 697     FOR i:=1 TO n DO
 698         WriteString(spisak[i].prez);
 699         WriteString(" ");
 700         WriteString(spisak[i].ime);
 701         WriteString(" ");
 702         WriteCard(spisak[i].god,1);
 703         WriteLn;
 704     END;
 705 END Ispisi;
 706
 707 PROCEDURE IspisiF(fajl:String;
 708           spisak:Studenti; n:CARDINAL);
 709 VAR
 710     f:File;
 711     i: CARDINAL;
 712 BEGIN
 713     IF (n>0) AND (n<=MaxStud) THEN
 714         f:=Create(fajl);
 715         (* pravimo takav fajl da ne
 716            postoji zadnji prazan red *)
 717         FOR i:=1 TO n-1 DO
 718             WrStr(f,spisak[i].prez);
 719             WrStr(f," ");
 720             WrStr(f,spisak[i].ime);
 721             WrStr(f," ");
 722             WrCard(f,spisak[i].god,1);
 723             WrLn(f);
 724         END;
 725         WrStr(f,spisak[n].prez);
 726         WrStr(f," ");
 727         WrStr(f,spisak[n].ime);
 728         WrStr(f," ");
 729         WrCard(f,spisak[n].god,1);
 730         Close(f);
 731     END;
 732 END IspisiF;
 733
 734 PROCEDURE NoviStudent(VAR spisak:Studenti;
 735                       VAR n:CARDINAL);
 736 VAR
 737     stud,temp:Student;
 738     i:CARDINAL;
 739     dodaj:BOOLEAN;
 740 BEGIN
 741     IF n<MaxStud THEN
 742         WriteString("Prezime novog studenta?");
 743         ReadString(stud.prez);
 744         WriteString("Ime novog studenta?");
 745         ReadString(stud.ime);
 746         WriteString("Godina rodjenja");
 747         WriteString("novog studenta?");
 748         ReadCard(stud.god);
 749         (* proverimo da li vec postoji *)
 750         i:=1;
 751         dodaj := TRUE;
 752         WHILE (i<=n) AND dodaj DO
 753             temp := spisak[i];
 754             IF (temp.god = stud.god) &
 755               (Compare(temp.prez,stud.prez)=0) &
 756               (Compare(temp.ime,stud.ime)=0) THEN
 757                 dodaj:=FALSE;
 758             END;
 759             INC(i);
 760         END;
 761         IF dodaj THEN
 762             INC(n);
 763             spisak[n]:=stud;
 764         ELSE
 765             WriteString("podaci vec postoje!");
 766         END;
 767     ELSE
 768         WriteString("popunjen kapacitet!");
 769     END;
 770 END NoviStudent;
 771
 772 VAR
 773     spisak : Studenti;
 774     fajl:String;
 775     n:CARDINAL;
 776 BEGIN
 777     fajl:="studenti.txt";
 778     UcitajF(fajl, spisak, n);
 779     Ispisi(spisak, n);
 780     NoviStudent(spisak,n);
 781     IspisiF(fajl, spisak, n);
 782 END nizslog.
 783 \end{lstlisting}
 784
 785 \section{Liste i pokazivači}
 786
 787 Za rad sa pokazivačima je potrebno iz modula \kod{Storage} uvesti procedure
 788 \kod{ALLOCATE} i \kod{DEALLOCATE}. U kodu se tada mogu koristiti i njihovi
 789 skraćeni oblici \kod{NEW} i \kod{DISPOSE}.
 790
 791 \subsection{Zadatak: Formiranje, štampanje i brisanje listi}
 792
 793
 794 \begin{lstlisting}[style=codeblock]
 795 MODULE liste;
 796 FROM InOut IMPORT WriteString, WriteLn, WriteInt,
 797         ReadInt, ReadCard;
 798 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
 799 TYPE
 800   brojevi = POINTER TO brojSlog;
 801   brojSlog = RECORD
 802       info:INTEGER;
 803       veza:brojevi;
 804   END;
 805 VAR
 806   n,i:CARDINAL;
 807   lista : brojevi;
 808   br:INTEGER;
 809
 810 PROCEDURE DodajPoc(VAR lista:brojevi; br:INTEGER);
 811 (* dodaje broj br na pocetak liste *)
 812 VAR
 813   temp:brojevi;
 814 BEGIN
 815   NEW(temp);
 816   temp^.info := br;
 817   temp^.veza := lista;
 818   lista := temp;
 819 END DodajPoc;
 820
 821 PROCEDURE Stampaj(lista:brojevi);
 822 VAR
 823   temp:brojevi;
 824 BEGIN
 825   temp:=lista;
 826   WHILE temp # NIL DO
 827       WriteInt(temp^.info,0);
 828       WriteLn;
 829       temp := temp^.veza;
 830   END;
 831 END Stampaj;
 832
 833 PROCEDURE Unisti(VAR lista:brojevi);
 834 VAR
 835   temp:brojevi;
 836 BEGIN
 837   temp:=lista;
 838   WHILE temp # NIL DO
 839         lista:=lista^.veza;
 840         DISPOSE(temp);
 841         temp:=lista;
 842   END;
 843 END Unisti;
 844
 845 BEGIN
 846   lista := NIL;
 847   WriteString('unesite n (broj brojeva): ');
 848   ReadCard(n);
 849   WriteString('unesite brojeve: ');
 850   WriteLn;
 851   FOR i:= 1 TO n DO
 852       ReadInt(br);
 853       DodajPoc(lista,br);
 854   END;
 855   WriteString('sadrzaj liste:');
 856   WriteLn;
 857   Stampaj(lista);
 858   Unisti(lista);
 859   WriteString('memorija je oslobodjena');
 860   WriteLn;
 861 END liste.
 862 \end{lstlisting}
 863
 864 Alternativno je poziv \kod{DodajPoc} moguće zameniti pozivom jedne od
 865 sledeće dve procedure čime se dobija dodavanje elementa na kraj liste,
 866 ili kreiranje sortirane liste:
 867
 868 \begin{lstlisting}[style=codeblock]
 869 PROCEDURE DodajKraj(VAR lista:brojevi; br:INTEGER);
 870 (* dodaje element na kraj liste *)
 871 VAR
 872   tekuci, temp :brojevi;
 873 BEGIN
 874   NEW(temp);
 875   temp^.info := br;
 876   temp^.veza := NIL;
 877   IF lista = NIL THEN
 878      (* prazna lista *)
 879      lista:=temp;
 880   ELSE
 881      tekuci := lista;
 882      WHILE tekuci^.veza#NIL DO
 883         tekuci:=tekuci^.veza;
 884      END;
 885      tekuci^.veza := temp;
 886   END;
 887 END DodajKraj;
 888
 889 PROCEDURE DodajSort(VAR lista:brojevi; br:CARDINAL);
 890 (* dodaje broj tako da lista ostane sortirana
 891    (podrazumeva se da je vec sortirana) *)
 892 VAR
 893   temp, tekuci : brojevi;
 894 BEGIN
 895   NEW(temp);
 896   temp^.info:=br;
 897   temp^.veza:=NIL;
 898   IF (lista = NIL) OR (lista^.info>=br) THEN
 899   (*prazna lista ili na pocetak*)
 900     temp^.veza:=lista;
 901     lista := temp;
 902   ELSE
 903   (*negde u listi*)
 904     tekuci:= lista;
 905     WHILE (tekuci^.veza # NIL) AND
 906           (tekuci^.veza^.info<=br) DO
 907       tekuci:=tekuci^.veza;
 908     END;
 909     temp^.veza := tekuci^.veza;
 910     tekuci^.veza:=temp;
 911   END;
 912 END DodajSort;
 913 \end{lstlisting}
 914
 915 \subsection{Zadatak: Prikaz osnovih operacija nad listama}
 916
 917 \begin{lstlisting}[style=codeblock]
 918 MODULE liste2;
 919 FROM InOut IMPORT WriteString, WriteLn,
 920            WriteCard, ReadCard;
 921 FROM IO IMPORT RdKey;
 922 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
 923 TYPE
 924   skupZn = SET OF CHAR;
 925   brojevi = POINTER TO brojSlog;
 926   brojSlog = RECORD
 927       info:CARDINAL;
 928       veza:brojevi;
 929   END;
 930 VAR
 931   lista : brojevi;
 932   menu,prazno:CHAR;
 933
 934 PROCEDURE DodajPoc(VAR lista:brojevi; br:INTEGER);
 935 (* dodaje broj pom na pocetak liste *)
 936 VAR
 937   temp:brojevi;
 938 BEGIN
 939   (* kreiramo novi element *)
 940   NEW(temp);
 941   temp^.info := br;
 942   (* treba da pokazuje na ostatak liste *)
 943   temp^.veza := lista;
 944   (* pocetak liste je novi element *)
 945   lista := temp;
 946 END DodajPoc;
 947
 948 PROCEDURE Unos(VAR lista:brojevi);
 949 (* dodaje n brojeva u listu *)
 950 VAR
 951   n,i,br:CARDINAL;
 952 BEGIN
 953   WriteString('unesite n (broj brojeva): ');
 954   ReadCard(n);
 955   FOR i:= 1 TO n DO
 956       WriteString("unesite broj ");
 957       WriteCard(i,0);
 958       WriteString(": ");
 959       ReadCard(br);
 960       DodajPoc(lista,br);
 961   END;
 962 END Unos;
 963
 964 (* -- procedure za stampu -- *)
 965
 966 PROCEDURE Stampaj(lista:brojevi);
 967 (* stampa sadrzaj liste na ekran *)
 968 VAR
 969   temp:brojevi;
 970 BEGIN
 971   WriteLn;
 972   WriteString("Sadrzaj liste:");
 973   WriteLn;
 974   temp:=lista;
 975   WHILE temp # NIL DO
 976       WriteCard(temp^.info,0);
 977       WriteLn;
 978       temp := temp^.veza;
 979   END;
 980 END Stampaj;
 981
 982 PROCEDURE StampajK(VAR lista:brojevi);
 983 (* stampa k-ti element (k unosi korisnik) *)
 984 VAR
 985   temp:brojevi;
 986   k,brojac:CARDINAL;
 987 BEGIN
 988   WriteString("unesite redni broj elementa:");
 989   ReadCard(k);
 990   temp:=lista;
 991   brojac := 1;
 992   WHILE (temp# NIL) AND (k>brojac) DO
 993     temp:=temp^.veza;
 994     INC(brojac);
 995   END;
 996   IF (temp#NIL) THEN
 997     WriteCard(temp^.info,2);
 998   ELSE
 999     WriteString("greska! - ne postoji element");
1000     WriteString(" u listi sa rednim brojem ");
1001     WriteCard(k,2);
1002   END;
1003   WriteLn();
1004 END StampajK;
1005
1006 PROCEDURE StampajMinimum(VAR lista:brojevi);
1007 (* nalazi i stampa minimalni element liste *)
1008 VAR
1009   temp:brojevi;
1010   min:CARDINAL;
1011 BEGIN
1012   IF (lista=NIL) THEN
1013     WriteString("prazna lista!");
1014   ELSE
1015     min:=lista^.info;
1016     temp:=lista^.veza;
1017     WHILE temp # NIL DO
1018       IF temp^.info < min THEN
1019         min := temp^.info;
1020       END;
1021       temp := temp^.veza;
1022     END;
1023     WriteString("Minimalni element liste je ");
1024     WriteCard(min,0);
1025   END;
1026   WriteLn;
1027 END StampajMinimum;
1028
1029 (* -- pomocne procedure, bez ispisa  -- *)
1030
1031 PROCEDURE UListi(lista:brojevi;
1032                  br: CARDINAL):BOOLEAN;
1033 (* vraca da li se 'br' nalazi u listi 'lista' *)
1034 VAR
1035   temp:brojevi;
1036 BEGIN
1037   temp:=lista;
1038   WHILE (temp # NIL) AND (temp^.info # br) DO
1039     (* dok ne dodjemo do kraja liste
1040        ili ne nadjemo broj *)
1041       temp := temp^.veza;
1042   END;
1043   IF temp#NIL THEN
1044     (* znaci da nismo na kraju liste,
1045        tj da je nadjen broj *)
1046     RETURN TRUE;
1047   ELSE (* temp = NIL *)
1048     RETURN FALSE;
1049   END;
1050 END UListi;
1051
1052 PROCEDURE IzbaciIzListe(VAR lista:brojevi;
1053                         br: CARDINAL):BOOLEAN;
1054 (* izbacuje broj 'br' iz liste, naravno ako
1055    postoji i vraca da li je operacija uspesno
1056    obavljena *)
1057 VAR
1058   temp,prethodni:brojevi;
1059 BEGIN
1060   (* proverimo da li je prvi element *)
1061   IF (lista # NIL) AND (lista^.info = br) THEN
1062     temp:=lista;
1063     lista :=lista^.veza;
1064     DISPOSE(temp);
1065     RETURN TRUE;
1066   ELSE
1067   (* trazimo u ostatku liste *)
1068     temp:=lista;
1069     prethodni:=NIL;
1070     WHILE (temp # NIL) AND (temp^.info # br) DO
1071         (* dok ne dodjemo do kraja liste
1072            ili ne nadjemo broj *)
1073         prethodni:=temp;
1074         temp := temp^.veza;
1075     END;
1076     IF temp#NIL THEN
1077       (* znaci da nismo na kraju liste,
1078          odnosno da smo nasli broj *)
1079       (* prevezemo listu oko elementa *)
1080       prethodni^.veza:=temp^.veza;
1081       DISPOSE(temp);
1082       RETURN TRUE;
1083     ELSE
1084       RETURN FALSE;
1085     END;
1086   END;
1087 END IzbaciIzListe;
1088
1089 (* - procedure sa interakcijom sa korisnikom - *)
1090
1091 PROCEDURE IzbacivanjeEl(VAR lista:brojevi);
1092 (* izbacuje uneti broj iz liste koristeci proceduru IzbaciIzListe *)
1093 VAR
1094   br:CARDINAL;
1095 BEGIN
1096   WriteString("unesite broj za izbacivanje: ");
1097   ReadCard(br);
1098   IF IzbaciIzListe(lista,br) THEN
1099     WriteString("broj je izbacen iz liste");
1100   ELSE
1101     WriteString("greska! - broj ne postoji");
1102   END;
1103   WriteLn;
1104 END IzbacivanjeEl;
1105
1106 PROCEDURE IzbacivanjeK(VAR lista:brojevi);
1107 (* izbacuje k-ti element iz liste *)
1108 VAR
1109   temp,tekuci:brojevi;
1110   k,brojac:CARDINAL;
1111 BEGIN
1112   IF lista=NIL THEN
1113     WriteString("lista je prazna, nema ");
1114     WriteString("elemenata za izbacivanje");
1115   ELSE
1116     WriteString("unesite redni broj elementa");
1117     WriteString(" koji zelite izbaciti:");
1118     ReadCard(k);
1119     IF k=1 THEN (*izbacivanje prvog *)
1120       temp:=lista;
1121       lista := lista^.veza;
1122       DISPOSE(temp);
1123     ELSE
1124       tekuci := lista;
1125       brojac := 2; (*gledamo jedan unapred*)
1126       WHILE (tekuci^.veza# NIL) AND (k>brojac) DO
1127         (* idemo kroz listu do k-tog el *)
1128         tekuci:=tekuci^.veza;
1129         INC(brojac);
1130       END;
1131       IF (tekuci^.veza#NIL) THEN
1132          (* pamtimo element za brisanje *)
1133          temp:=tekuci^.veza;
1134          (* prevezujemo listu oko njega*)
1135          tekuci^.veza:=tekuci^.veza^.veza;
1136          DISPOSE(temp);
1137       ELSE
1138         WriteString("greska! - ne postoji el ");
1139         WriteString("u listi sa rednim brojem ");
1140         WriteCard(k,2);
1141       END;
1142       WriteLn();
1143     END;
1144   END;
1145 END IzbacivanjeK;
1146
1147 PROCEDURE Pretraga(lista:brojevi);
1148 (* provera da li se uneti broj nalazi u listi *)
1149 VAR
1150   br:CARDINAL;
1151 BEGIN
1152   WriteString("unesite trazeni broj");
1153   ReadCard(br);
1154   IF UListi(lista,br) THEN
1155     WriteString("broj postoji u listi");
1156   ELSE
1157     WriteString("broj ne postoji u listi");
1158   END;
1159   WriteLn;
1160 END Pretraga;
1161
1162 (* -- oslobadjanje memorije -- *)
1163
1164 PROCEDURE Unisti(VAR lista:brojevi);
1165 VAR
1166   temp:brojevi;
1167 BEGIN
1168   temp:=lista;
1169   WHILE temp # NIL DO
1170         lista:=lista^.veza;
1171         DISPOSE(temp);
1172         temp:=lista;
1173   END;
1174 END Unisti;
1175
1176 BEGIN
1177   (* pocinjemo od prazne liste *)
1178   lista := NIL;
1179   REPEAT
1180      WriteLn;
1181      WriteString("Ilustracija rada sa");
1182      WriteString(" listama brojeva");
1183      WriteLn;
1184      WriteString("=============================");
1185      WriteLn;
1186      WriteString("s - stampa");WriteLn;
1187      WriteString("u - unos");WriteLn;
1188      WriteString("i - izbacivanje br iz liste");
1189      WriteLn;
1190      WriteString("e - izbacivanje k-tog el.");
1191      WriteLn;
1192      WriteString("k - stampanje k-tog elementa");
1193      WriteLn;
1194      WriteString("m - minimalni broj u listi");
1195      WriteLn;
1196      WriteString("p - pretraga el. u listi");
1197      WriteLn;
1198      WriteLn;
1199      WriteString("q - kraj rada (quit)");WriteLn;
1200       REPEAT
1201         menu := CAP(RdKey());
1202       UNTIL menu IN skupZn{'S','U','E','I',
1203                            'M','K','P','Q'};
1204       IF menu#'Q' THEN
1205         CASE menu OF
1206          'S' : Stampaj(lista);|
1207          'U' : Unos(lista);|
1208          'I' : IzbacivanjeEl(lista);|
1209          'E' : IzbacivanjeK(lista);|
1210          'K' : StampajK(lista); |
1211          'M' : StampajMinimum(lista); |
1212          'P' : Pretraga(lista);|
1213         END;
1214         WriteLn;
1215         WriteString("--- pritisnite bilo koji ");
1216         WriteString("taster za povratak u meni");
1217         prazno:=RdKey();
1218       ELSE
1219         WriteString("Kraj rada")
1220       END;
1221       WriteLn;
1222   UNTIL menu='Q';
1223   Unisti(lista);
1224 END liste2.
1225 \end{lstlisting}
1226
1227
1228 \subsection{Zadatak: Prikaz operacija nad listama sa jedinstvenim ključem}
1229
1230 \begin{lstlisting}[style=codeblock]
1231 MODULE Radnici;
1232
1233 FROM InOut IMPORT WriteString, ReadString,
1234            WriteLn, WriteCard, ReadCard, Done;
1235 FROM IO IMPORT RdKey;
1236 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1237
1238 TYPE
1239   skupZn = SET OF CHAR;
1240   str = ARRAY [1..20] OF CHAR;
1241   radnici = POINTER TO slog;
1242   slog = RECORD
1243            ime, prez : str;
1244            broj : CARDINAL;
1245            sled : radnici
1246          END;
1247 VAR
1248   meni, pom : CHAR;
1249   rad : radnici;
1250
1251   PROCEDURE Clear();
1252   VAR
1253     br: CARDINAL;
1254   BEGIN
1255     FOR br:=1 TO 100 DO
1256       WriteLn;
1257     END;
1258   END Clear;
1259
1260   PROCEDURE Spisak(rad : radnici);
1261   BEGIN
1262     WHILE rad # NIL DO
1263       WriteString(rad^.ime);
1264       WriteString(' ');
1265       WriteString(rad^.prez);
1266       WriteCard(rad^.broj, 8);
1267       WriteLn;
1268       rad := rad^.sled
1269     END
1270   END Spisak;
1271
1272   PROCEDURE Zaposli(VAR rad : radnici);
1273   VAR
1274     novi, tek : radnici;
1275     nadjen : BOOLEAN;
1276   BEGIN
1277     NEW(novi);
1278     REPEAT
1279       WriteString('Ime, prezime i jedinstveni');
1280       WriteString(' broj novog radnika: ');
1281       WriteLn;
1282       ReadString(novi^.ime);
1283       ReadString(novi^.prez);
1284       ReadCard(novi^.broj);
1285       nadjen := FALSE;
1286       tek := rad;
1287       WHILE NOT nadjen AND (tek # NIL) AND
1288             (tek^.broj <= novi^.broj) DO
1289         IF novi^.broj = tek^.broj THEN
1290           nadjen := TRUE
1291         ELSE
1292           tek := tek^.sled
1293         END
1294       END
1295     UNTIL Done AND NOT nadjen;
1296     IF (rad = NIL) OR (novi^.broj<rad^.broj) THEN
1297       novi^.sled := rad;
1298       rad := novi
1299     ELSE
1300       tek := rad;
1301       WHILE (tek^.sled # NIL) AND
1302             (tek^.sled^.broj < novi^.broj) DO
1303         tek := tek^.sled
1304       END;
1305       novi^.sled := tek^.sled;
1306       tek^.sled := novi
1307     END
1308   END Zaposli;
1309
1310   PROCEDURE Otpusti(VAR rad : radnici);
1311   VAR
1312     tek, pom : radnici;
1313     br : CARDINAL;
1314   BEGIN
1315     REPEAT
1316       WriteLn;
1317       WriteString('Unesite redni broj radnika:');
1318       ReadCard(br)
1319     UNTIL Done;
1320     WriteLn;
1321     IF rad = NIL THEN
1322       WriteString('Greska.')
1323     ELSIF br = rad^.broj THEN
1324       pom := rad;
1325       rad := rad^.sled;
1326       DISPOSE(pom)
1327     ELSE
1328       tek := rad;
1329       WHILE (tek^.sled # NIL) AND
1330             (tek^.sled^.broj < br) DO
1331         tek := tek^.sled
1332       END;
1333       IF (tek^.sled = NIL) OR
1334          (tek^.sled^.broj > br) THEN
1335         WriteString('Greska.')
1336       ELSE
1337         pom := tek^.sled;
1338         tek^.sled := tek^.sled^.sled;
1339         DISPOSE(pom)
1340       END
1341     END
1342   END Otpusti;
1343
1344   PROCEDURE Inform(rad : radnici);
1345   VAR
1346     br : CARDINAL;
1347   BEGIN
1348     REPEAT
1349       WriteLn;
1350       WriteString('Unesite redni broj radnika:');
1351       ReadCard(br)
1352     UNTIL Done;
1353     WriteLn;
1354     WHILE (rad # NIL) AND (rad^.broj < br) DO
1355       rad := rad^.sled
1356     END;
1357     IF (rad = NIL) OR (rad^.broj # br) THEN
1358       WriteString('Greska.')
1359     ELSE
1360       WriteString(rad^.ime);
1361       WriteString(' ');
1362       WriteString(rad^.prez)
1363     END
1364   END Inform;
1365
1366   PROCEDURE Bankrot(VAR rad : radnici);
1367   VAR
1368     pom : radnici;
1369   BEGIN
1370     WHILE rad # NIL DO
1371       pom := rad;
1372       rad := rad^.sled;
1373       DISPOSE(pom)
1374     END
1375   END Bankrot;
1376
1377 BEGIN
1378   rad := NIL;
1379   REPEAT
1380     Clear;
1381     WriteString('s - spisak svih zaposlenih');
1382     WriteLn;
1383     WriteString('z - zaposljavanje radnika');
1384     WriteLn;
1385     WriteString('o - otpustanje radnika');
1386     WriteLn;
1387     WriteString('i - informacije o radniku');
1388     WriteLn;
1389     WriteString('b - bankrot firme');
1390     WriteLn;
1391     WriteString('k - kraj rada');
1392     WriteLn;
1393     REPEAT
1394       meni := RdKey();
1395     UNTIL CAP(meni) IN skupZn{'S', 'Z', 'O',
1396                               'I', 'B', 'K'};
1397     Clear;
1398     IF CAP(meni) # 'K' THEN
1399       CASE CAP(meni) OF
1400         'S' : Spisak(rad)|
1401         'Z' : Zaposli(rad)|
1402         'O' : Otpusti(rad)|
1403         'I' : Inform(rad)|
1404         'B' : Bankrot(rad)
1405       END;
1406       WriteLn;
1407       WriteString('-- pritisnite bilo koji ');
1408       WriteString('taster za nastavak --');
1409       pom := RdKey()
1410     END
1411   UNTIL CAP(meni) = 'K'
1412 END Radnici.
1413 \end{lstlisting}
1414
1415 Procedura \kod{Spisak} se može realizovati i u rekurzivnoj verziji:
1416
1417 \begin{lstlisting}[style=codeblock]
1418   PROCEDURE Spisak(rad : radnici);
1419   BEGIN
1420     IF rad # NIL THEN
1421       WriteString(rad^.ime);
1422       WriteString(' ');
1423       WriteString(rad^.prez);
1424       WriteCard(rad^.broj, 8);
1425       WriteLn;
1426       Spisak(rad^.sled)
1427     END
1428   END Spisak;
1429 \end{lstlisting}
1430
1431 \subsection[Zadatak: Dve liste osoba sa istim sadržajem]{Zadatak: Dve
1432   liste osoba koje dele sadržaj, jedna sortirana po visini, druga po
1433   težini}
1434
1435 Sa tastature učitavati po dva broja koji opisuju osobu (visina i
1436 težina) i smeštati ih u povezane listu, tako da postoji neopadajuće
1437 uređenje i po visini i po težini.
1438
1439 \begin{lstlisting}[style=codeblock]
1440 MODULE VisTez;
1441 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1442 FROM IO IMPORT WrLn, WrStr, RdCard, WrCard;
1443 FROM SYSTEM IMPORT TSIZE;
1444 TYPE
1445   pok = POINTER TO element;
1446   element = RECORD
1447               visina, tezina : CARDINAL;
1448               Vveza, Tveza : pok
1449             END;
1450 VAR
1451   pocV, pocT : pok;
1452   vis, tez : CARDINAL;
1453 PROCEDURE Ispisi(pocV, pocT : pok);
1454 VAR
1455   tek : pok;
1456 BEGIN
1457   tek := pocV;
1458   WrStr('Po visini:');
1459   WrLn;
1460   WHILE tek # NIL DO
1461     WrCard(tek^.visina, 6);
1462     tek := tek^.Vveza
1463   END;
1464   WrLn;
1465   tek := pocT;
1466   WrStr('Po tezini:');
1467   WrLn;
1468   WHILE tek # NIL DO
1469     WrCard(tek^.tezina,6);
1470     tek := tek^.Tveza
1471   END
1472 END Ispisi;
1473
1474 PROCEDURE Ubaci(VAR pocV, pocT : pok;
1475                 vis, tez : CARDINAL);
1476 VAR
1477   novi, tek, iza : pok;
1478   nadjen : BOOLEAN;
1479 BEGIN
1480   IF pocV = NIL THEN
1481     ALLOCATE(pocV, TSIZE(element));
1482     pocV^.visina := vis;
1483     pocV^.tezina := tez;
1484     pocV^.Vveza := NIL;
1485     pocV^.Tveza := NIL;
1486     pocT := pocV
1487   ELSE
1488     ALLOCATE(novi, TSIZE(element));
1489     novi^.visina := vis;
1490     novi^.tezina := tez;
1491     tek := pocV;
1492     nadjen := FALSE;
1493     WHILE (tek # NIL) AND NOT nadjen DO
1494       nadjen := vis <= tek^.visina;
1495       IF NOT nadjen THEN
1496         iza := tek;
1497         tek := tek^.Vveza
1498       END
1499     END;
1500     novi^.Vveza := tek;
1501     IF tek = pocV THEN
1502       pocV := novi
1503     ELSE
1504       iza^.Vveza := novi
1505     END;
1506     tek := pocT;
1507     nadjen := FALSE;
1508     WHILE (tek # NIL) AND NOT nadjen DO
1509       nadjen := tez <= tek^.tezina;
1510       IF NOT nadjen THEN
1511         iza := tek;
1512         tek := tek^.Tveza
1513       END
1514     END;
1515     novi^.Tveza := tek;
1516     IF tek = pocT THEN
1517       pocT := novi
1518     ELSE
1519       iza^.Tveza := novi
1520     END
1521   END
1522 END Ubaci;
1523
1524 BEGIN
1525   pocV := NIL;
1526   pocT := NIL;
1527   WrStr('Unesite visinu ---- ');
1528   vis := RdCard();
1529   WHILE vis > 0 DO
1530     WrStr('Unesite tezinu ---- ');
1531     tez := RdCard();
1532     Ubaci(pocV, pocT, vis, tez);
1533     WrLn;
1534     WrStr('Unesite visinu ---- ');
1535     vis := RdCard()
1536   END;
1537   WrLn;
1538   Ispisi(pocV, pocT)
1539 END VisTez.
1540 \end{lstlisting}
1541
1542 \section{Polinomi preko listi}
1543
1544 \subsection{Moduli}
1545
1546 Polinomi su predstavljeni pomoću pokazivača. Apstraktni tip podataka
1547 \kod{Polinom} je definisan u globalnom modulu.
1548
1549 \paragraph{PolinomL.DEF} \
1550
1551 \begin{lstlisting}[style=codeblock]
1552 DEFINITION MODULE PolinomL;
1553 TYPE
1554   Polinom = POINTER TO Monom;
1555   Monom = RECORD
1556             k : REAL;
1557             st : CARDINAL;
1558             veza : Polinom
1559           END;
1560
1561 PROCEDURE Anuliraj(VAR p: Polinom);
1562 PROCEDURE Unos(VAR p: Polinom);
1563 PROCEDURE Stampaj(p: Polinom; d: CARDINAL);
1564 PROCEDURE Kopiraj(p: Polinom;
1565                   VAR kopija: Polinom);
1566 PROCEDURE UbaciMonom(mon:Polinom;
1567                      VAR p: Polinom);
1568 PROCEDURE PromeniZnak(VAR p: Polinom);
1569 PROCEDURE Saberi(p1, p2: Polinom;
1570                  VAR zbir: Polinom);
1571 PROCEDURE SaberiNa(p: Polinom; VAR rez: Polinom);
1572 PROCEDURE Oduzmi(p1,p2: Polinom;
1573                  VAR razlika: Polinom);
1574 PROCEDURE MonomPuta(p, mon: Polinom;
1575                     VAR mp : Polinom);
1576 PROCEDURE Puta(p1, p2: Polinom; VAR pr: Polinom);
1577 PROCEDURE Kolicnik(p1, p2: Polinom;
1578                    VAR kol, ost: Polinom;
1579                    VAR ok : BOOLEAN);
1580 PROCEDURE PolinomNaN(p: Polinom; n: CARDINAL;
1581                      VAR rez: Polinom);
1582 PROCEDURE DisposePolinom(VAR p: Polinom);
1583
1584 END PolinomL.
1585 \end{lstlisting}
1586
1587 \paragraph{PolinomL.MOD} \
1588
1589 \begin{codeblock}
1590 (* Modul za rad sa polinomima preko listi
1591    verzija 2012, rev 1 *)
1592 IMPLEMENTATION MODULE PolinomL;
1593 FROM InOut IMPORT Write, WriteString, WriteLn,
1594            WriteCard, ReadCard, Done;
1595 FROM RealInOut IMPORT WriteReal, ReadReal;
1596 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1597
1598 PROCEDURE Anuliraj(VAR p: Polinom);
1599 BEGIN
1600   p := NIL;
1601 END Anuliraj;
1602
1603 PROCEDURE Kopiraj(p: Polinom; VAR kopija: Polinom);
1604 VAR
1605   pomocni: Polinom;
1606 BEGIN
1607   IF p = NIL THEN
1608     kopija := NIL
1609   ELSE
1610     NEW(kopija);
1611     kopija^ := p^;
1612     p := p^.veza;
1613     pomocni := kopija;
1614     WHILE p <> NIL DO
1615       NEW(pomocni^.veza);
1616       pomocni := pomocni^.veza;
1617       pomocni^ := p^;
1618       p := p^.veza
1619     END
1620   END
1621 END Kopiraj;
1622
1623 PROCEDURE Stampaj(p: Polinom; d: CARDINAL);
1624
1625   PROCEDURE StampajMonom(m : Polinom);
1626   BEGIN
1627     WITH m^ DO
1628       IF st <> 0 THEN
1629         IF ABS(k) <> 1.0 THEN
1630           WriteReal(ABS(k), d)
1631         END;
1632         Write('x');
1633         IF st <> 1 THEN
1634           Write('^');
1635           WriteCard(st, 1)
1636         END
1637       ELSE
1638         WriteReal(ABS(k), d)
1639       END
1640     END
1641   END StampajMonom;
1642
1643 BEGIN
1644   IF p = NIL THEN
1645     WriteReal(0., d)
1646   ELSE
1647     IF p^.k < 0.0 THEN
1648       WriteString(' - ')
1649     END;
1650     StampajMonom(p);
1651     p := p^.veza;
1652     WHILE p <> NIL DO
1653       IF p^.k > 0.0 THEN
1654         WriteString(' + ')
1655       ELSE
1656         WriteString(' - ')
1657       END;
1658       StampajMonom(p);
1659       p := p^.veza
1660     END
1661   END
1662 END Stampaj;
1663
1664 PROCEDURE UbaciMonom(mon:Polinom; VAR p: Polinom);
1665 VAR
1666   stari, tekuci, kopija: Polinom;
1667 BEGIN
1668   IF mon # NIL THEN
1669     NEW(kopija);
1670     kopija^ := mon^;
1671     tekuci := p;
1672         stari := NIL;
1673     WHILE (tekuci#NIL) AND (tekuci^.st>kopija^.st) DO
1674       stari := tekuci;
1675       tekuci := tekuci^.veza
1676     END;
1677     kopija^.veza := tekuci;
1678     IF tekuci = p THEN
1679       p := kopija
1680     ELSE
1681       stari^.veza := kopija
1682     END;
1683     IF (tekuci#NIL) AND (kopija^.st = tekuci^.st) THEN
1684       kopija^.k := kopija^.k + tekuci^.k;
1685       kopija^.veza := tekuci^.veza;
1686       DISPOSE(tekuci);
1687       IF kopija^.k = 0.0 THEN
1688         IF p = kopija THEN
1689           p := kopija^.veza
1690         ELSE
1691           stari^.veza := kopija^.veza
1692         END;
1693         DISPOSE(kopija)
1694       END
1695     END
1696   END
1697 END UbaciMonom;
1698
1699 PROCEDURE Unos(VAR p : Polinom);
1700 VAR
1701   i, n: CARDINAL;
1702   novi: Polinom;
1703 BEGIN
1704   Anuliraj(p);
1705   REPEAT
1706     WriteLn;
1707     WriteString('Unesite broj monoma n (n>=0) ');
1708     ReadCard(n);
1709   UNTIL Done;
1710   WriteLn;
1711   FOR i := 1 TO n DO
1712     NEW(novi);
1713     WITH novi^ DO
1714       REPEAT
1715         WriteString('Unesite koeficijent monoma br.');
1716         WriteCard(i, 1);
1717         WriteString(' (<> 0) ');
1718         ReadReal(k);
1719         WriteLn
1720       UNTIL k <> 0.0;
1721       REPEAT
1722         WriteLn;
1723         WriteString('Unesite eksponent monoma br.');
1724         WriteCard(i, 1);
1725         WriteString(' (>=0) ');
1726         ReadCard(st);
1727       UNTIL Done;
1728       WriteLn;
1729     END;
1730     UbaciMonom(novi, p);
1731     DISPOSE(novi);
1732   END
1733 END Unos;
1734
1735 PROCEDURE Saberi(p1, p2: Polinom; VAR zbir: Polinom);
1736 BEGIN
1737   Kopiraj(p1, zbir);
1738   WHILE p2 <> NIL DO
1739     UbaciMonom(p2, zbir);
1740     p2 := p2^.veza
1741   END
1742 END Saberi;
1743
1744 PROCEDURE SaberiNa(p: Polinom; VAR rez: Polinom);
1745 BEGIN
1746   WHILE p <> NIL DO
1747     UbaciMonom(p,rez);
1748     p := p^.veza;
1749   END;
1750 END SaberiNa;
1751
1752 PROCEDURE PromeniZnak(VAR p: Polinom);
1753 VAR
1754   t: Polinom;
1755 BEGIN
1756   t := p;
1757   WHILE t <> NIL DO
1758     t^.k := - t^.k;
1759     t := t^.veza
1760   END
1761 END PromeniZnak;
1762
1763 PROCEDURE Oduzmi(p1,p2: Polinom; VAR razlika: Polinom);
1764 BEGIN
1765   Kopiraj(p2, razlika);
1766   PromeniZnak(razlika);
1767   WHILE p1 <> NIL DO
1768     UbaciMonom(p1, razlika);
1769     p1 := p1^.veza
1770   END
1771 END Oduzmi;
1772
1773 PROCEDURE MonomPuta(p, mon: Polinom; VAR mp: Polinom);
1774 VAR
1775   tekuci: Polinom;
1776 BEGIN
1777   Anuliraj(mp);
1778   IF (mon <> NIL) AND (p <> NIL) THEN
1779     NEW(mp);
1780     mp^.k := p^.k * mon^.k;
1781     mp^.st := p^.st + mon^.st;
1782     p := p^.veza;
1783     tekuci := mp;
1784     WHILE p <> NIL DO
1785       NEW(tekuci^.veza);
1786       tekuci := tekuci^.veza;
1787       tekuci^.k := p^.k * mon^.k;
1788       tekuci^.st := p^.st + mon^.st;
1789       p := p^.veza
1790     END;
1791     tekuci^.veza := NIL
1792   END
1793 END MonomPuta;
1794
1795 PROCEDURE Puta(p1, p2: Polinom; VAR pr: Polinom);
1796 VAR
1797   pomocni: Polinom;
1798 BEGIN
1799   Anuliraj(pr);
1800   IF (p1 <> NIL) AND (p2 <> NIL) THEN
1801     MonomPuta(p1, p2, pr);
1802     p2 := p2^.veza;
1803     WHILE p2 <> NIL DO
1804       MonomPuta(p1, p2, pomocni);
1805       REPEAT
1806         UbaciMonom(pomocni, pr);
1807         pomocni := pomocni^.veza
1808       UNTIL pomocni = NIL;
1809       p2 := p2^.veza
1810     END
1811   END
1812 END Puta;
1813
1814 PROCEDURE Kolicnik(p1, p2: Polinom; VAR kol, ost: Polinom; VAR ok: BOOLEAN);
1815
1816   PROCEDURE Deli(VAR kol, ost: Polinom);
1817   VAR
1818     novi, pomocni: Polinom;
1819   BEGIN
1820     IF ost <> NIL THEN
1821       IF ost^.st >= p2^.st THEN
1822         NEW(novi);
1823         novi^.k := - ost^.k / p2^.k;
1824         novi^.st := ost^.st - p2^.st;
1825         MonomPuta(p2, novi, pomocni);
1826         Saberi(ost, pomocni, ost);
1827         novi^.k := - novi^.k;
1828         UbaciMonom(novi, kol);
1829         DISPOSE(novi);
1830         Deli(kol, ost)
1831       END
1832     END
1833   END Deli;
1834
1835 BEGIN (* Kolicnik *)
1836   ok := TRUE;
1837   Anuliraj(kol);
1838   IF p2 = NIL THEN
1839     ok := FALSE
1840   ELSE
1841     Kopiraj(p1, ost);
1842     Deli(kol, ost)
1843   END
1844 END Kolicnik;
1845
1846 PROCEDURE PolinomNaN(p: Polinom; n: CARDINAL;
1847                      VAR rez: Polinom);
1848 VAR
1849   i: CARDINAL;
1850 BEGIN
1851   IF n = 0 THEN
1852     NEW(rez);
1853     rez^.k := 1.0;
1854     rez^.st := 0;
1855     rez^.veza := NIL;
1856   ELSIF n = 1 THEN
1857         Kopiraj( p, rez );
1858   ELSE
1859     rez := p;
1860     FOR i := 2 TO n DO
1861       Puta(rez, p, rez)
1862     END
1863   END;
1864 END PolinomNaN;
1865
1866 PROCEDURE DisposePolinom(VAR p: Polinom);
1867 VAR
1868   pomocni: Polinom;
1869 BEGIN
1870   pomocni := p;
1871   WHILE pomocni # NIL DO
1872     p := p^.veza;
1873     DISPOSE(pomocni);
1874     pomocni := p
1875   END
1876 END DisposePolinom;
1877
1878 END PolinomL.
1879 \end{codeblock}
1880
1881
1882 \subsection{Zadatak: Sabiranje sa unapred određenim polinomom}
1883
1884 Želimo da ispišemo uneti polinom uvećan za\\ $x^5 - 3x^4 + 4x + 7$.
1885
1886 \begin{lstlisting}[style=codeblock]
1887 MODULE polinom;
1888 FROM PolinomL IMPORT Polinom, Stampaj, Anuliraj, DisposePolinom, UbaciMonom, Unos, Saberi;
1889 FROM InOut IMPORT WriteString, WriteLn;
1890 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1891
1892 VAR
1893   p,q,rez,pom : Polinom;
1894
1895 BEGIN
1896   (* korisnik unosi prvi polinom *)
1897   WriteString("Unesite polinom:");
1898   WriteLn;
1899   Unos(p);
1900   (* drugi polinom kreiramo mi,
1901      monom po monom *)
1902   Anuliraj(q); (* isto sto i q:=NIL; *)
1903   (* formiramo monom x^5 *)
1904   NEW(pom);
1905   pom^.st:=5;
1906   pom^.k:=1.0;
1907   (* dodajemo ga u polinom *)
1908   UbaciMonom(pom,q);
1909   DISPOSE(pom);
1910   (* -3 x^4 *)
1911   NEW(pom);
1912   pom^.st := 4;
1913   pom^.k := -3.0;
1914   UbaciMonom(pom,q);
1915   DISPOSE(pom);
1916   (* 4 x *)
1917   NEW(pom);
1918   pom^.st := 1;
1919   pom^.k := 4.0;
1920   UbaciMonom(pom,q);
1921   DISPOSE(pom);
1922   (* 7 (x^0) *)
1923   NEW(pom);
1924   pom^.st := 0;
1925   pom^.k := 7.0;
1926   UbaciMonom(pom,q);
1927   DISPOSE(pom);
1928   (* saberemo polinome *)
1929   Saberi(p, q, rez);
1930   (* odstampamo rezultat *)
1931   Stampaj(rez,0);
1932   WriteLn;
1933   (* oslobadjanje zauzete memorije *)
1934   DisposePolinom(p);
1935   DisposePolinom(q);
1936   DisposePolinom(rez);
1937 END polinom.
1938 \end{lstlisting}
1939
1940 \subsection{Zadatak: Suma k polinoma}
1941
1942 Napisati program koji ucitava broj k (1<=k<=50) i k polinoma, a nakon
1943 toga izracunava njihovu sumu
1944
1945 \begin{lstlisting}[style=codeblock]
1946 MODULE PolSuma;
1947
1948 FROM PolinomL IMPORT Polinom, Anuliraj, DisposePolinom, Unos, Stampaj, SaberiNa;
1949 FROM InOut IMPORT WriteLn, WriteString, ReadCard, WriteCard;
1950 CONST
1951   maxk = 50;
1952 TYPE
1953   nizPol = ARRAY [1..maxk] OF Polinom;
1954 VAR
1955   i, k: CARDINAL;
1956   suma : Polinom;
1957   p : nizPol;
1958 BEGIN
1959   REPEAT
1960     WriteString('Unesite broj k (1 <= k <= ');
1961     WriteCard(maxk, 1);
1962     WriteString(') ');
1963     ReadCard(k);
1964     WriteLn;
1965   UNTIL (1 <= k) AND (k <= maxk);
1966   FOR i := 1 TO k DO
1967     WriteLn;
1968     WriteString('Unos ');
1969     WriteCard(i, 1);
1970     WriteString('. polinoma.');
1971     WriteLn;
1972     Unos(p[i])
1973   END;
1974   Anuliraj(suma);
1975   FOR i := 1 TO k DO
1976     SaberiNa(suma, p[i])
1977   END;
1978   WriteLn;
1979   WriteString('Njihova suma je:');
1980   WriteLn;
1981   Stampaj(suma, 4);
1982   DisposePolinom(suma);
1983   FOR i := 1 TO k DO
1984     DisposePolinom(p[i]);
1985   END;
1986 END PolSuma.
1987 \end{lstlisting}
1988
1989 \section{Stek i red opsluživanja}
1990
1991 \subsection{Zadatak: Ilustracija pisanja u fajl uz pomoć bafera}
1992
1993 \begin{lstlisting}[style=codeblock]
1994 DEFINITION MODULE QueueInfo;
1995 CONST
1996   Maxqueue = 100;
1997 TYPE
1998   InfoTip = CHAR;
1999
2000 END QueueInfo.
2001
2002 IMPLEMENTATION MODULE QueueInfo;
2003 END QueueInfo.
2004
2005 DEFINITION MODULE RedOpsl1;
2006 FROM QueueInfo IMPORT InfoTip,Maxqueue;
2007 TYPE
2008   Niz = ARRAY[1..Maxqueue] OF InfoTip;
2009   RedOpslTip = RECORD
2010         Prvi, Zadnji : CARDINAL;
2011         Element : Niz
2012   END;
2013
2014 PROCEDURE MakeNull(VAR q : RedOpslTip);
2015 PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
2016 PROCEDURE First(VAR q : RedOpslTip;
2017                 VAR x : InfoTip;
2018                 VAR ok : BOOLEAN);
2019 PROCEDURE PopFirst(VAR q : RedOpslTip;
2020                    VAR ok : BOOLEAN);
2021 PROCEDURE AddRear(VAR q : RedOpslTip;
2022                   x : InfoTip;
2023                   VAR ok : BOOLEAN);
2024
2025 END RedOpsl1.
2026
2027 IMPLEMENTATION MODULE RedOpsl1;
2028 FROM QueueInfo IMPORT Maxqueue,InfoTip;
2029
2030 PROCEDURE MakeNull(VAR q : RedOpslTip);
2031 BEGIN
2032   WITH q DO
2033     Prvi := 0;
2034     Zadnji := 0
2035   END
2036 END MakeNull;
2037
2038 PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
2039 BEGIN
2040   RETURN q.Zadnji = 0
2041 END Empty;
2042
2043
2044 PROCEDURE First(VAR q : RedOpslTip;
2045                 VAR x : InfoTip;
2046                 VAR ok : BOOLEAN);
2047 BEGIN
2048   IF Empty(q) THEN
2049     ok := FALSE
2050   ELSE
2051     ok := TRUE;
2052     WITH q DO
2053       x := Element[Prvi]
2054     END
2055   END
2056 END First;
2057
2058 PROCEDURE AddOne(i : CARDINAL) : CARDINAL;
2059 BEGIN
2060   IF i = Maxqueue THEN
2061     RETURN 1
2062   ELSE
2063     RETURN i+1
2064   END
2065 END AddOne;
2066
2067 PROCEDURE PopFirst(VAR q : RedOpslTip;
2068                    VAR ok : BOOLEAN);
2069 BEGIN
2070   IF Empty(q) THEN
2071     ok := FALSE
2072   ELSE
2073     ok := TRUE;
2074     WITH q DO
2075       IF Prvi = Zadnji THEN
2076         MakeNull(q)
2077       ELSE
2078         Prvi := AddOne(Prvi)
2079       END
2080     END
2081   END
2082 END PopFirst;
2083
2084 PROCEDURE AddRear(VAR q : RedOpslTip;
2085                   x : InfoTip;
2086                   VAR ok : BOOLEAN);
2087 BEGIN
2088   WITH q DO
2089     IF AddOne(Zadnji) = Prvi THEN
2090       ok := FALSE
2091     ELSE
2092       ok := TRUE;
2093       IF Empty(q) THEN
2094         Prvi := 1;
2095         Zadnji := 1
2096       ELSE
2097         Zadnji := AddOne(Zadnji)
2098       END;
2099       Element[Zadnji] := x
2100     END
2101   END
2102 END AddRear;
2103
2104 END RedOpsl1.
2105
2106 MODULE Bafer;
2107 FROM RedOpsl1 IMPORT RedOpslTip, MakeNull, Empty, First, PopFirst, AddRear;
2108 FROM FIO IMPORT File,WrChar, Create, Close;
2109 IMPORT IO;
2110
2111 CONST
2112   ImeIzlaza = 'izlaz.txt';
2113
2114 VAR
2115   izlaz : File;
2116   znak : CHAR;
2117   buffer : RedOpslTip;
2118
2119 PROCEDURE IsprazniBafer(VAR dat : File;
2120                         VAR buf : RedOpslTip);
2121 VAR
2122   znak : CHAR;
2123   ok : BOOLEAN;
2124 BEGIN
2125   WHILE NOT Empty(buf) DO
2126     First(buf, znak, ok);
2127     PopFirst(buf, ok);
2128     WrChar(dat, znak)
2129   END
2130 END IsprazniBafer;
2131
2132 PROCEDURE BaferWrite(VAR dat : File;
2133                      VAR buf : RedOpslTip;
2134                      znak : CHAR);
2135 VAR
2136   ok : BOOLEAN;
2137 BEGIN
2138   AddRear(buf, znak, ok);
2139   IF NOT ok THEN
2140     IsprazniBafer(dat, buf);
2141     AddRear(buf, znak, ok)
2142   END
2143 END BaferWrite;
2144
2145 BEGIN
2146   izlaz := Create(ImeIzlaza);
2147   MakeNull(buffer);
2148   IO.WrStr('Unesite tekst, koji treba da se unese u datoteku ');
2149   IO.WrStr(ImeIzlaza);
2150   IO.WrChar('.');
2151   IO.WrLn;
2152   IO.WrStr('Unos zavrsite tackom.');
2153   IO.WrLn;
2154   znak := IO.RdChar();
2155   WHILE znak # '.' DO
2156     BaferWrite(izlaz, buffer, znak);
2157     znak := IO.RdChar();
2158   END;
2159   IsprazniBafer(izlaz, buffer);
2160   Close(izlaz)
2161 END Bafer.
2162 \end{lstlisting}
2163
2164 \subsection%
2165 {Zadatak: Ispitivanje da li reč pripada gramatici wcw$^+$}
2166
2167 Reč pripada ovoj gramatici ako joj se prvi deo (w) sastoji samo od
2168 slova 'a' i 'b', sledi slovo 'c' a nakon njega obrnuta reč reči w.
2169
2170 \begin{lstlisting}[style=codeblock]
2171 DEFINITION MODULE Stek;
2172 CONST
2173   Maxstack = 100;
2174 TYPE
2175   Niz = ARRAY [1..Maxstack] OF CHAR;
2176   StekTip = RECORD
2177             Top : CARDINAL;
2178             Element : Niz
2179           END;
2180 PROCEDURE MakeNull(VAR s : StekTip);
2181 PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
2182
2183 PROCEDURE Top(VAR s : StekTip;
2184               VAR x : CHAR;
2185               VAR ok : BOOLEAN);
2186 PROCEDURE Pop(VAR s : StekTip;
2187               VAR ok : BOOLEAN);
2188 PROCEDURE Push(VAR s : StekTip;
2189                x : CHAR;
2190                VAR ok : BOOLEAN);
2191 END Stek.
2192
2193
2194 IMPLEMENTATION MODULE Stek;
2195
2196 PROCEDURE MakeNull(VAR s : StekTip);
2197 BEGIN
2198   s.Top := 0
2199 END MakeNull;
2200
2201 PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
2202 BEGIN
2203   RETURN s.Top = 0
2204 END Empty;
2205
2206 PROCEDURE Top(VAR s : StekTip;
2207               VAR x : CHAR;
2208               VAR ok : BOOLEAN);
2209 BEGIN
2210   IF Empty(s) THEN
2211     ok := FALSE
2212   ELSE
2213     ok := TRUE;
2214     WITH s DO
2215       x := Element[Top]
2216     END
2217   END
2218 END Top;
2219
2220 PROCEDURE Pop(VAR s : StekTip;
2221               VAR ok : BOOLEAN);
2222 BEGIN
2223   IF Empty(s) THEN
2224     ok := FALSE
2225   ELSE
2226     ok := TRUE;
2227     DEC(s.Top)
2228   END
2229 END Pop;
2230
2231 PROCEDURE Push(VAR s : StekTip;
2232                x : CHAR;
2233                VAR ok : BOOLEAN);
2234 BEGIN
2235   WITH s DO
2236     IF Top = Maxstack THEN
2237       ok := FALSE
2238     ELSE
2239       ok := TRUE;
2240       INC(Top);
2241       Element[Top] := x
2242     END
2243   END
2244 END Push;
2245 END Stek.
2246
2247 MODULE wcw;
2248 (* Da li rec pripada gramatici wcw+. *)
2249 FROM Stek IMPORT StekTip, MakeNull, Empty,
2250                  Top, Pop, Push;
2251 FROM InOut IMPORT Read, Write, WriteString, EOL;
2252 TYPE
2253   slova = SET OF CHAR;
2254 VAR
2255   S : StekTip;
2256   Ch, C : CHAR;
2257   ok : BOOLEAN;
2258 BEGIN
2259   MakeNull(S);
2260   Read(Ch);
2261   ok := TRUE;
2262   WHILE ok AND (Ch IN slova{'a', 'b'}) DO
2263     Push(S, Ch, ok);
2264     Read(Ch);
2265   END;
2266   IF NOT ok THEN
2267     WriteString('Greska - mali stek')
2268   ELSIF Ch # 'c' THEN
2269     WriteString('Pogresan string')
2270   ELSE
2271     Read(Ch);
2272     WHILE ok AND (Ch # EOL) DO
2273       Top(S, C, ok);
2274       ok := ok AND (C = Ch);
2275       IF ok THEN
2276         Pop(S, ok);
2277         Read(Ch);
2278       END
2279     END;
2280     IF NOT (ok AND Empty(S)) THEN
2281       WriteString('Pogresan string')
2282     ELSE
2283       WriteString('String pripada jeziku L')
2284     END
2285   END
2286 END wcw.
2287 \end{lstlisting}
2288
2289 \subsection{Zadatak: Kalkulator za izračunavanje postfiksnih izraza}
2290
2291
2292 Napraviti kalkulator za izračunavanje postfiksnih izraza. Svi brojevi
2293 koji figurišu u izrazu su jednocifreni.
2294
2295 \begin{lstlisting}[style=codeblock]
2296 MODULE PostFix;
2297
2298 FROM StekI IMPORT StekTip, MakeNull, Empty, Top, Pop, Push;
2299 FROM InOut IMPORT Read, Write, WriteInt, EOL;
2300 TYPE
2301   slova = SET OF CHAR;
2302 VAR
2303   S : StekTip;
2304   Ch : CHAR;
2305   Op1, Op2 : INTEGER;
2306   ok : BOOLEAN;
2307 PROCEDURE Conv(Ch : CHAR) : INTEGER;
2308 BEGIN
2309   RETURN  ORD(Ch) - ORD('0')
2310 END Conv;
2311
2312 BEGIN
2313   MakeNull(S);
2314   Read(Ch);
2315   WHILE Ch # EOL DO
2316     IF Ch IN slova{'+', '-', '/', '*', '%'} THEN
2317       Top(S, Op2, ok);
2318       Pop(S, ok);
2319       Top(S, Op1, ok);
2320       Pop(S, ok);
2321       CASE Ch OF
2322         '+' : Op1 := Op1 + Op2 |
2323         '-' : Op1 := Op1 - Op2 |
2324         '*' : Op1 := Op1 * Op2 |
2325         '/' : Op1 := Op1 DIV Op2 |
2326         '%' : Op1 := Op1 MOD Op2
2327       END;
2328       Push(S, Op1, ok)
2329     ELSE
2330       Push(S, Conv(Ch), ok)
2331     END;
2332     Read(Ch);
2333   END;
2334   Top(S, Op1, ok);
2335   Write('=');
2336   WriteInt(Op1,5)
2337 END PostFix.
2338 \end{lstlisting}
2339
2340
2341 \section{Simulacija rekurzije}
2342
2343
2344 Na početku označiti sve rekurzivne pozive u originalnoj proceduri
2345 adresama (npr. 1,2,3... ili konstante nabrojivog tipa podataka).
2346
2347 Na steku se čuvaju lokalne promenljive, parametri procedure i adresa
2348 mesta poziva, a u skladu sa tim se kreira InfoTip.
2349
2350 Trivijalnim pozivom se smatra onaj koji se izračunava bez dodatnih
2351 rekurzivnih poziva.
2352
2353 U kodu ispod, \kod{treba\_rekurzija} znači da je poziv netrivijalan,
2354 odnosno treba naći uslove pod kojima se sigurno dešavaju rekurzivni
2355 pozivi.
2356
2357 \begin{lstlisting}
2358 MakeNull(S);
2359 REPEAT
2360   WHILE treba_rekurzija DO
2361     -prepisati sve od pocetka originalne
2362      procedure do prvog rekurzivnog poziva
2363     -staviti na stek potrebne
2364      lokalne promenljive, parametre procedure i
2365      adresu mesta poziva
2366     -podesiti vrednosti parametara da budu
2367      kao u rekurzivnom pozivu procedure
2368   END;
2369   trivijalan poziv
2370   umesto RETURN x pisati rez := x
2371   jos := TRUE;
2372   WHILE jos AND NOT Empty(S) DO
2373     Top(S, el, ok);
2374     Pop(S, ok);
2375     -restauriramo vrednosti sa steka
2376     -u zavisnosti od adrese poziva nastavimo
2377      prepisivanje originalne procedure sa
2378      tog mesta
2379     -ako se dodje do novog rek. poziva tada:
2380        -sacuvati na steku vrednosti
2381        -podesiti vrednosti parametara da budu
2382         kao u rekurzivnom pozivu procedure
2383        -ici na pocetak koda
2384         (ovo se postize sa jos := FALSE)
2385     -inace
2386        ako se naidje na RETURN x pisati rez := x
2387   END
2388 UNTIL Empty(S);
2389 \end{lstlisting}
2390
2391 Ako je procedura funkcijska tada se na kraj dodaje \kod{RETURN rez}.
2392
2393 \subsection*{ZADACI}
2394
2395 Simulirati ponašanje sledećih rekurzivnih procedura (funkcija) upotrebom steka:
2396
2397 \subsection{Primer 1 -- faktorijel}
2398
2399
2400 \begin{lstlisting}[style=codeblock]
2401 MODULE Fakto;
2402 (* InfoTip = CARDINAL; *)
2403
2404 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2405 FROM StekC IMPORT StekTip, MakeNull, Empty,
2406                   Top, Pop, Push;
2407 VAR
2408   n : CARDINAL;
2409 PROCEDURE RFakto(n : CARDINAL) : CARDINAL;
2410 BEGIN
2411   IF n <= 1 THEN
2412     RETURN 1
2413   ELSE
2414     RETURN n * RFakto(n-1)
2415   END
2416 END RFakto;
2417
2418
2419 PROCEDURE SFakto(n : CARDINAL) : CARDINAL;
2420 VAR
2421   s : StekTip;
2422   rez : CARDINAL;
2423   OK : BOOLEAN;
2424 BEGIN
2425   MakeNull(s);
2426   WHILE n > 1 DO
2427     Push(s,n,OK);
2428     DEC(n)
2429   END;
2430   rez := 1;
2431   WHILE NOT Empty(s) DO
2432     Top(s, n, OK);
2433     Pop(s, OK);
2434     rez := n * rez
2435   END;
2436   RETURN rez
2437 END SFakto;
2438
2439 BEGIN
2440   WrStr('n = ');
2441   n := RdCard();
2442   WrLn
2443   WrStr('n! = ');
2444   WrCard(RFakto(n), 1);
2445   WrStr(' = ');
2446   WrCard(SFakto(n), 1)
2447 END Fakto.
2448 \end{lstlisting}
2449
2450 \subsection{Primer 2 -- stepenovanje}
2451
2452 \begin{lstlisting}[style=codeblock]
2453 MODULE Step;
2454 (* InfoTip = RECORD
2455                 x : REAL;
2456                 n : CARDINAL;
2457                 adr : (par, nepar)
2458              END;
2459 *)
2460
2461 FROM IO IMPORT WrStr, WrLn, WrReal,
2462         RdReal, RdCard;
2463 FROM StekStep IMPORT StekTip, MakeNull, Empty,
2464              Top, Pop, Push, InfoTip, AdrTip;
2465
2466 VAR
2467   n : CARDINAL;
2468   x : REAL;
2469
2470 PROCEDURE Sqr(y : REAL) : REAL;
2471 BEGIN
2472   RETURN y * y
2473 END Sqr;
2474
2475 PROCEDURE RStep(x : REAL;
2476                 n : CARDINAL) : REAL;
2477 BEGIN
2478   IF n = 0 THEN
2479     RETURN 1.
2480   ELSIF ODD(n) THEN
2481     RETURN x * Sqr( RStep(x, n DIV 2) )
2482   ELSE
2483     RETURN Sqr( RStep(x, n DIV 2) )
2484   END
2485 END RStep;
2486
2487 PROCEDURE SStep(x : REAL;
2488                 n : CARDINAL ) : REAL;
2489 VAR
2490   s : StekTip;
2491   OK : BOOLEAN;
2492   rez : REAL;
2493   el : InfoTip;
2494 BEGIN
2495   MakeNull(s);
2496   WHILE n > 0 DO
2497     el.x := x;
2498     el.n := n;
2499     IF ODD(n) THEN
2500       el.adr := nepar;
2501     ELSE
2502       el.adr := par
2503     END;
2504     Push(s,el,OK);
2505     n := n DIV 2
2506   END;
2507   rez := 1.;
2508   WHILE NOT Empty(s) DO
2509     Top(s, el, OK);
2510     Pop(s, OK);
2511     x := el.x;
2512     n := el.n;
2513     IF el.adr = nepar THEN
2514       rez := x * Sqr(rez)
2515     ELSE
2516       rez := Sqr(rez)
2517     END
2518   END;
2519   RETURN rez
2520 END SStep;
2521
2522 BEGIN
2523   WrStr('x =? ');
2524   x := RdReal();
2525   WrLn;
2526   WrStr('n =? ');
2527   n := RdCard();
2528   WrStr('x^n = ');
2529   WrReal(RStep(x, n), 10, 1);
2530   WrStr(' = ');
2531   WrReal(SStep(x, n), 10, 1)
2532 END Step.
2533 \end{lstlisting}
2534
2535 \subsection{Primer 3 -- Fibonači}
2536
2537 \begin{lstlisting}[style=codeblock]
2538 MODULE Fib;
2539 (* InfoTip = RECORD
2540                 n : CARDINAL;
2541                 PrviSab : CARDINAL;
2542                 adr : (prvi, drugi)
2543              END;
2544 *)
2545
2546 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2547 FROM StekFib IMPORT StekTip, MakeNull, Empty,
2548        Top, Pop, Push, InfoTip, AdrTip;
2549 VAR
2550   n : CARDINAL;
2551
2552 PROCEDURE RFib(n : CARDINAL) : CARDINAL;
2553 BEGIN
2554   IF n <= 1 THEN
2555     RETURN n
2556   ELSE
2557     RETURN RFib(n-1) + RFib(n-2)
2558   END
2559 END RFib;
2560
2561 PROCEDURE SFib(n : CARDINAL ) : CARDINAL;
2562 VAR
2563   s : StekTip;
2564   OK, jos : BOOLEAN;
2565   rez, PrviSab : CARDINAL;
2566   el : InfoTip;
2567 BEGIN
2568   MakeNull(s);
2569   REPEAT
2570     WHILE n > 1 DO
2571       el.n := n;
2572       el.adr := prvi;
2573       Push(s,el,OK);
2574       DEC(n)
2575     END;
2576     rez := (n);
2577     jos := TRUE;
2578     WHILE (NOT Empty(s)) AND jos DO
2579       Top(s, el, OK);
2580       Pop(s, OK);
2581       n := el.n;
2582       IF el.adr = prvi THEN
2583         PrviSab := rez;
2584         el.n := n;
2585         el.adr := drugi;
2586         el.PrviSab := PrviSab;
2587         Push(s, el, OK);
2588         DEC(n, 2);
2589         jos := FALSE
2590       ELSE
2591         PrviSab := el.PrviSab;
2592         rez := PrviSab + rez
2593       END
2594     END
2595   UNTIL Empty(s);
2596   RETURN rez
2597 END SFib;
2598
2599 BEGIN
2600   WrStr('n =? ');
2601   n := RdCard();
2602   WrStr('F(n) = ');
2603   WrCard(RFib(n), 1);
2604   WrStr(' = ');
2605   WrCard(SFib(n), 1)
2606 END Fib.
2607 \end{lstlisting}
2608
2609 \subsection{Primer 4 -- faktorijel 2}
2610
2611
2612 \begin{lstlisting}[style=codeblock]
2613 MODULE Faktor;
2614 (* InfoTip = CARDINAL; *)
2615 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2616 FROM StekC IMPORT StekTip, MakeNull, Empty,
2617                   Top, Pop, Push;
2618
2619 VAR
2620   n,rez : CARDINAL;
2621
2622 PROCEDURE RFakto(n : CARDINAL;
2623                  VAR rez : CARDINAL);
2624 BEGIN
2625   IF n = 0 THEN
2626     rez := 1
2627   ELSE
2628     RFakto(n-1, rez);
2629     rez := n * rez
2630   END
2631 END RFakto;
2632
2633 PROCEDURE SFakto(n : CARDINAL;
2634                  VAR rez : CARDINAL);
2635 VAR
2636   s : StekTip;
2637   OK : BOOLEAN;
2638 BEGIN
2639   MakeNull(s);
2640   WHILE n > 0 DO
2641     Push(s,n,OK);
2642     DEC(n)
2643   END;
2644   rez := 1;
2645   WHILE NOT Empty(s) DO
2646     Top(s, n, OK);
2647     Pop(s, OK);
2648     rez := n * rez
2649   END
2650 END SFakto;
2651
2652 BEGIN
2653   WrStr('n =? ');
2654   n := RdCard();
2655   WrLn;
2656   WrStr('n! = ');
2657   RFakto(n, rez);
2658   WrCard(rez, 1);
2659   WrStr(' = ');
2660   SFakto(n, rez);
2661   WrCard(rez, 1)
2662 END Faktor.
2663 \end{lstlisting}
2664
2665 \subsection{Primer 5 (ispitni)}
2666
2667
2668 \begin{lstlisting}[style=codeblock]
2669 MODULE Rek1;
2670 (* InfoTip = RECORD
2671                 d, g, m1, m2 : INTEGER;
2672                 adr : (prvi, drugi)
2673              END;
2674 *)
2675 FROM Stek1 IMPORT StekTip, adresa, InfoTip,
2676          MakeNull, Empty, Top, Pop, Push;
2677 IMPORT IO;
2678 VAR
2679   X : ARRAY [1..20] OF INTEGER;
2680
2681 PROCEDURE Max(d, g: INTEGER) : INTEGER;
2682 VAR
2683   m1, m2 : INTEGER;
2684 BEGIN
2685   IF d>g THEN
2686     RETURN MIN(INTEGER)
2687   ELSIF d=g THEN
2688     RETURN X[d]
2689   ELSE
2690     m1 := Max(d, (d+g) DIV 2);
2691     m2 := Max((d+g) DIV 2 +1, g);
2692     IF m1 > m2 THEN
2693       RETURN m1
2694     ELSE
2695       RETURN m2
2696     END
2697   END
2698 END Max;
2699
2700 PROCEDURE SMax(d, g: INTEGER) : INTEGER;
2701 VAR
2702   S : StekTip;
2703   el : InfoTip;
2704   ok, jos : BOOLEAN;
2705   m1, m2, rez : INTEGER;
2706 BEGIN
2707   MakeNull(S);
2708   REPEAT
2709     WHILE d<g DO
2710       el.d := d;
2711       el.g := g;
2712       el.adr := prvi;
2713       Push(S, el, ok);
2714       g := (d+g) DIV 2
2715     END;
2716     IF d>g THEN
2717       rez := MIN(INTEGER)
2718     ELSE (* d=g *)
2719       rez := X[d]
2720     END;
2721     jos := TRUE;
2722     WHILE jos AND NOT Empty(S) DO
2723       Top(S, el, ok);
2724       Pop(S, ok);
2725       d := el.d;
2726       g := el.g;
2727       m1 := el.m1;
2728       IF el.adr = prvi THEN
2729         m1 := rez;
2730         el.m1 := m1;
2731         el.adr := drugi;
2732         Push(S, el, ok);
2733         d := (d+g) DIV 2 + 1;
2734         jos := FALSE
2735       ELSE (*el.adr = drugi*)
2736         m2 := rez;
2737         IF m1 > m2 THEN
2738           rez := m1
2739         ELSE
2740           rez := m2
2741         END
2742       END
2743     END
2744   UNTIL Empty(S);
2745   RETURN rez
2746 END SMax;
2747
2748 BEGIN (* glavni program *)
2749   X[1] := 3;
2750   X[2] := 2;
2751   X[3] := 5;
2752   X[4] := -7;
2753   X[5] := 0;
2754   IO.WrCard(Max(1, 5), 3);
2755   IO.WrLn;
2756   IO.WrCard(SMax(1, 5), 3);
2757   IO.WrLn
2758 END Rek1.
2759 \end{lstlisting}
2760
2761 \subsection{Primer 6 (ispitni)}
2762
2763
2764 \begin{lstlisting}[style=codeblock]
2765 MODULE Rek2;
2766 (* InfoTip = RECORD
2767                 x, y, n : CARDINAL;
2768                 adr : (prvi, drugi, treci, cetvrti)
2769              END;
2770 *)
2771 FROM Stek2 IMPORT StekTip, adresa, InfoTip,
2772            MakeNull, Empty, Top, Pop, Push;
2773 IMPORT IO;
2774
2775 PROCEDURE g(x : CARDINAL; y : CARDINAL;
2776             n : CARDINAL) : CARDINAL;
2777 BEGIN
2778   IF n < 3 THEN
2779     RETURN x + y
2780   ELSIF ODD(n) THEN
2781     RETURN g(g(x+1, y, n-2), y, n-3)
2782   ELSE
2783     RETURN g(x, g(x, y+1, n-2), n-3)
2784   END
2785 END g;
2786
2787 PROCEDURE Sg(x : CARDINAL; y : CARDINAL;
2788              n : CARDINAL) : CARDINAL;
2789 VAR
2790   S : StekTip;
2791   el : InfoTip;
2792   ok, jos : BOOLEAN;
2793   rez : CARDINAL;
2794 BEGIN
2795   MakeNull(S);
2796   REPEAT
2797     WHILE n >= 3 DO
2798       IF ODD(n) THEN
2799         el.x := x;
2800         el.y := y;
2801         el.n := n;
2802         el.adr := prvi;
2803         Push(S, el, ok);
2804         INC(x);
2805         DEC(n, 2)
2806       ELSE
2807         el.x := x;
2808         el.y := y;
2809         el.n := n;
2810         el.adr := treci;
2811         Push(S, el, ok);
2812         INC(y);
2813         DEC(n, 2)
2814       END
2815     END;
2816     rez := x+y;
2817     jos := TRUE;
2818     WHILE jos AND NOT Empty(S) DO
2819       Top(S, el, ok);
2820       Pop(S, ok);
2821       x := el.x;
2822       y := el.y;
2823       n := el.n;
2824       IF el.adr = prvi THEN
2825         el.adr := drugi;
2826         Push(S, el, ok);
2827         x := rez;
2828         DEC(n, 3);
2829         jos := FALSE
2830       ELSIF el.adr = treci THEN
2831         el.adr := cetvrti;
2832         Push(S, el, ok);
2833         y := rez;
2834         DEC(n, 3);
2835         jos := FALSE
2836       END
2837     END
2838   UNTIL Empty(S);
2839   RETURN rez
2840 END Sg;
2841
2842 BEGIN (* glavni program *)
2843   IO.WrCard(g(2, 3, 10), 3);
2844   IO.WrCard(Sg(2, 3, 10), 3);
2845 END Rek2.
2846 \end{lstlisting}
2847
2848 %\columnbreak
2849
2850 \appendix
2851
2852 \section{Native XDS Modula 2 -- kratko uputstvo}
2853
2854
2855 Ovo uputstvo ukratko pokriva kako se može nabaviti XDS Modula 2 za Windows
2856 sistem, njenu instalaciju, te kako napraviti i pokretnuti jednostavan program.
2857
2858 \subsection*{Dobavljanje instalacije}
2859
2860
2861 Native XDS Modula 2 se može besplatno skinuti sa sajta proizvođača,
2862 \url{http://www.excelsior-usa.com/}, tačnije na adresi:
2863
2864 \url{http://www.excelsior-usa.com/xdsdl.html}
2865
2866 Prvo se prikazuje ugovor o korišćenju koji na dnu treba potvrditi da ste
2867 razumeli i da ćete ga se pridržavati.
2868
2869 Na stranici koja se potom otvara je potrebno odabrati ``XDS 2.6 beta 2
2870 for Windows'' i snimiti je na računar.
2871
2872 \subsection*{Instalacija okruženja}
2873
2874 Osnovno okruženje (xds-x86...) se instalira pokretanjem prethodno pomenute
2875  instalacione arhive.
2876
2877 \emph{Korisnicima Windows-a 7 preporučujemo da pokrenu instalacione
2878   pakete pomoću opcije ``Run as administrator'' do koje se stiže desnim
2879   klikom miša.}
2880
2881 Pretpostavićemo u daljem tekstu da je program instaliran u
2882 \kod{C:/XDS/}
2883
2884 \subsection*{Pokretanje okruženja}
2885
2886 Po uspešnoj instalaciji bi trebalo da postoji ikonica na desktopu, kao
2887 i grupa sa programom u start meniju.
2888
2889 Ukoliko iz bilo kakvog razloga ne postoje odgovarajuće prečice,
2890 okruženje se može pokrenuti uz pomoć izvršnog fajla
2891 \kod{C:/XDS/BIN/xds.exe} (ako je instalirano na podrazumevanoj
2892 lokaciji).
2893
2894 \subsection*{Prvi projekat}
2895
2896 Da bismo mogli da pišemo i pokrećemo svoj program, potrebno je prvo
2897 napraviti projekat za njega, što se radi na sledeći način:
2898
2899 \begin{itemize}
2900
2901 \item
2902  Iz menija se odabere Project->New.
2903 \item U dijalogu se klikne na gornje dugme ``Browse'', odabere se putanja gde
2904   će se kreirati projekat i ukuca se ime novog projekta.
2905
2906 \item U drugom polju ``Template'' ne treba da piše ništa. Ukoliko
2907   postoji neki tekst, obrisati ga.
2908
2909 \item Kliknuti na ``OK''
2910
2911 \item Iskočiće dijalog na kome piše da ne postoji fajl za editovanje,
2912   kliknuti na ``OK'' da se on napravi.
2913
2914 \item Pojavljuje se forma za kucanje programa, ukucati (na primer):
2915
2916 \begin{minipage}{\columnwidth}
2917 \begin{lstlisting}[style=codeblock]
2918   MODULE Hello;
2919   FROM InOut IMPORT WriteString,WriteLn;
2920   BEGIN
2921     WriteString("Hello World");
2922     WriteLn;
2923   END Hello.
2924 \end{lstlisting}
2925 \end{minipage}
2926
2927 \item Program se može pokrenuti na različite načine, pri čemu se
2928   automatski prevodi:
2929
2930   \begin{itemize}
2931
2932   \item Klik na ``Run'' ikonicu u toolbaru (plavi čovečuljak koji trči)
2933
2934   \item Meni Debug->Run
2935
2936   \item Prečica Ctrl+F9 na tastaturi
2937
2938   \end{itemize}
2939
2940 \item Ako je sve u redu sa programom, treba da se pojavi novi terminal
2941   u kome se ispisuje rezultat izvršavanja programa, u našem slučaju
2942   jednostavna pozdravna poruka.
2943 \end{itemize}
2944
2945 Naravno moguće je i samo prevesti (kompajlirati) program, tako da se
2946 samo prikažu greške (ako ih ima) i bez pokretanja programa:
2947 \begin{itemize}
2948 \item Klik na ``Compile'' ikonicu u toolbaru
2949 \item Meni Tools->Compile
2950 \item Prečica F9 na tastaturi
2951 \end{itemize}
2952
2953 Ukoliko u programu postoje greške, on neće biti pokrenut, već će se
2954 dobiti lista grešaka u donjem delu prozora. Na primer ako obrišemo ``S''
2955 u četvrtom redu i probamo da pokrenemo program, taj red će biti
2956 označen svetlo plavom bojom i dobićemo poruku:
2957
2958 \kod{- Error in pro1.mod [4:5]: Undeclared identifier "Writeting"}
2959
2960 Što znači da u četvrtom redu, kod petog karatkera postoji problem, da
2961 identifikator nije deklarisan, što najčešće znači da ga nismo uvezli,
2962 ili, kao u našem slučaju, da smo napravili grešku u kucanju.
2963
2964 Stvar na koju isto treba obratiti pažnju je da se nekad greška
2965 prijavljue nešto kasnije u tekstu nego što je napravljena. Na primer,
2966 ako obrišemo ``;'' na kraju četvrtog reda i probamo da pokrenemo
2967 program, peti red će biti označen svetlo plavom bojom i dobićemo
2968 poruku:
2969
2970 \kod{- Error in pro1.mod [5:5]: Expected symbol ";" }
2971
2972 Ovo se desilo jer nedostaje tačka zarez na kraju četvrtog reda, ali će
2973 kompajler probati da je traži i dalje, pa će tek na početku petog reda
2974 prijaviti grešku.
2975
2976 U spisku se takođe pojavljuje i upozorenje (Warning) o tome da se
2977 uvezena komanda WriteString ne koristi nigde u programu. Često se
2978 upozorenja mogu ignorisati, a pažnju uglavnom treba obraćati na
2979 greške, odnosno poruke koje počinju sa ``Error''.
2980
2981 Takođe se često dešava da su druge prijavljene greške posledica prve,
2982 te je poželjno ponovo kompajlirati (ili pokretati) program posle svake
2983 ispravljene greške.
2984
2985 \paragraph{Napomena o template-ovima pri kreiranju projekta:}
2986 Moguće je namestiti da u dijalogu za novi projekat drugo polje ``Template''
2987  uvek bude prazno. Potrebno je u tom istom dijalogu kliknuti na
2988  ``Configure'', a potom isprazniti polje ``default template''.
2989
2990 \subsection{Mogući problemi}
2991
2992 \subsubsection*{Nedostajući sistemski moduli}
2993
2994 Verzije pre 2.6 nisu imale uključene u glavni paket sve module koji se
2995 koriste u okviru kursa, i bilo je neophodno da se dodatno instalira i
2996 ``Top Speed Compatibility Pack'' (tscp-x86...). Bez njega je kompajler
2997 prijavljivao da ne postoje neki moduli - najčešće je problem bio da
2998 nedostaje \kod{FIO} modul.
2999
3000 \subsubsection*{Problemi u pokretanju - nemoguće naći exe}
3001
3002 Ako pri pokušaju kompajliranja/pokretanja programa kompajler prijavi
3003 da ne može da nađe exe i pri tome prijavljuje kraću putanju od one
3004 koja je stvarno u pitanju, obično se radi o tome da je postojao razmak
3005 u okviru putanje do modula. Npr ``C:\textbackslash Moj prvi program''
3006 će prouzrokovati probleme, a kompajler će prijaviti da ne može da nađe
3007 ``C:\textbackslash Moj''.
3008
3009 Ovo je nažalost problem okruženja i dok se ne ispravi u nekoj budućoj
3010 verziji ne može se zaobići, tako da je jedino rešenje premestiti
3011 fajlove, odnosno ako je moguće preimenovati problematične foldere.
3012
3013 \mainend
3014
3015 \end{document}