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