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 (* Modul za rad sa polinomima preko listi
1588    verzija 2012, rev 1 *)
1589 IMPLEMENTATION MODULE PolinomL;
1590 FROM InOut IMPORT Write, WriteString, WriteLn,
1591            WriteCard, ReadCard, Done;
1592 FROM RealInOut IMPORT WriteReal, ReadReal;
1593 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1594
1595 PROCEDURE Anuliraj(VAR p: Polinom);
1596 BEGIN
1597   p := NIL;
1598 END Anuliraj;
1599
1600 PROCEDURE Kopiraj(p: Polinom; VAR kopija: Polinom);
1601 VAR
1602   pomocni: Polinom;
1603 BEGIN
1604   IF p = NIL THEN
1605     kopija := NIL
1606   ELSE
1607     NEW(kopija);
1608     kopija^ := p^;
1609     p := p^.veza;
1610     pomocni := kopija;
1611     WHILE p <> NIL DO
1612       NEW(pomocni^.veza);
1613       pomocni := pomocni^.veza;
1614       pomocni^ := p^;
1615       p := p^.veza
1616     END
1617   END
1618 END Kopiraj;
1619
1620 PROCEDURE Stampaj(p: Polinom; d: CARDINAL);
1621
1622   PROCEDURE StampajMonom(m : Polinom);
1623   BEGIN
1624     WITH m^ DO
1625       IF st <> 0 THEN
1626         IF ABS(k) <> 1.0 THEN
1627           WriteReal(ABS(k), d)
1628         END;
1629         Write('x');
1630         IF st <> 1 THEN
1631           Write('^');
1632           WriteCard(st, 1)
1633         END
1634       ELSE
1635         WriteReal(ABS(k), d)
1636       END
1637     END
1638   END StampajMonom;
1639
1640 BEGIN
1641   IF p = NIL THEN
1642     WriteReal(0., d)
1643   ELSE
1644     IF p^.k < 0.0 THEN
1645       WriteString(' - ')
1646     END;
1647     StampajMonom(p);
1648     p := p^.veza;
1649     WHILE p <> NIL DO
1650       IF p^.k > 0.0 THEN
1651         WriteString(' + ')
1652       ELSE
1653         WriteString(' - ')
1654       END;
1655       StampajMonom(p);
1656       p := p^.veza
1657     END
1658   END
1659 END Stampaj;
1660
1661 PROCEDURE UbaciMonom(mon:Polinom; VAR p: Polinom);
1662 VAR
1663   stari, tekuci, kopija: Polinom;
1664 BEGIN
1665   IF mon # NIL THEN
1666     NEW(kopija);
1667     kopija^ := mon^;
1668     tekuci := p;
1669         stari := NIL;
1670     WHILE (tekuci#NIL) AND (tekuci^.st>kopija^.st) DO
1671       stari := tekuci;
1672       tekuci := tekuci^.veza
1673     END;
1674     kopija^.veza := tekuci;
1675     IF tekuci = p THEN
1676       p := kopija
1677     ELSE
1678       stari^.veza := kopija
1679     END;
1680     IF (tekuci#NIL) AND (kopija^.st = tekuci^.st) THEN
1681       kopija^.k := kopija^.k + tekuci^.k;
1682       kopija^.veza := tekuci^.veza;
1683       DISPOSE(tekuci);
1684       IF kopija^.k = 0.0 THEN
1685         IF p = kopija THEN
1686           p := kopija^.veza
1687         ELSE
1688           stari^.veza := kopija^.veza
1689         END;
1690         DISPOSE(kopija)
1691       END
1692     END
1693   END
1694 END UbaciMonom;
1695
1696 PROCEDURE Unos(VAR p : Polinom);
1697 VAR
1698   i, n: CARDINAL;
1699   novi: Polinom;
1700 BEGIN
1701   Anuliraj(p);
1702   REPEAT
1703     WriteLn;
1704     WriteString('Unesite broj monoma n (n>=0) ');
1705     ReadCard(n);
1706   UNTIL Done;
1707   WriteLn;
1708   FOR i := 1 TO n DO
1709     NEW(novi);
1710     WITH novi^ DO
1711       REPEAT
1712         WriteString('Unesite koeficijent monoma br.');
1713         WriteCard(i, 1);
1714         WriteString(' (<> 0) ');
1715         ReadReal(k);
1716         WriteLn
1717       UNTIL k <> 0.0;
1718       REPEAT
1719         WriteLn;
1720         WriteString('Unesite eksponent monoma br.');
1721         WriteCard(i, 1);
1722         WriteString(' (>=0) ');
1723         ReadCard(st);
1724       UNTIL Done;
1725       WriteLn;
1726     END;
1727     UbaciMonom(novi, p);
1728     DISPOSE(novi);
1729   END
1730 END Unos;
1731
1732 PROCEDURE Saberi(p1, p2: Polinom; VAR zbir: Polinom);
1733 BEGIN
1734   Kopiraj(p1, zbir);
1735   WHILE p2 <> NIL DO
1736     UbaciMonom(p2, zbir);
1737     p2 := p2^.veza
1738   END
1739 END Saberi;
1740
1741 PROCEDURE SaberiNa(p: Polinom; VAR rez: Polinom);
1742 BEGIN
1743   WHILE p <> NIL DO
1744     UbaciMonom(p,rez);
1745     p := p^.veza;
1746   END;
1747 END SaberiNa;
1748
1749 PROCEDURE PromeniZnak(VAR p: Polinom);
1750 VAR
1751   t: Polinom;
1752 BEGIN
1753   t := p;
1754   WHILE t <> NIL DO
1755     t^.k := - t^.k;
1756     t := t^.veza
1757   END
1758 END PromeniZnak;
1759
1760 PROCEDURE Oduzmi(p1,p2: Polinom; VAR razlika: Polinom);
1761 BEGIN
1762   Kopiraj(p2, razlika);
1763   PromeniZnak(razlika);
1764   WHILE p1 <> NIL DO
1765     UbaciMonom(p1, razlika);
1766     p1 := p1^.veza
1767   END
1768 END Oduzmi;
1769
1770 PROCEDURE MonomPuta(p, mon: Polinom; VAR mp: Polinom);
1771 VAR
1772   tekuci: Polinom;
1773 BEGIN
1774   Anuliraj(mp);
1775   IF (mon <> NIL) AND (p <> NIL) THEN
1776     NEW(mp);
1777     mp^.k := p^.k * mon^.k;
1778     mp^.st := p^.st + mon^.st;
1779     p := p^.veza;
1780     tekuci := mp;
1781     WHILE p <> NIL DO
1782       NEW(tekuci^.veza);
1783       tekuci := tekuci^.veza;
1784       tekuci^.k := p^.k * mon^.k;
1785       tekuci^.st := p^.st + mon^.st;
1786       p := p^.veza
1787     END;
1788     tekuci^.veza := NIL
1789   END
1790 END MonomPuta;
1791
1792 PROCEDURE Puta(p1, p2: Polinom; VAR pr: Polinom);
1793 VAR
1794   pomocni: Polinom;
1795 BEGIN
1796   Anuliraj(pr);
1797   IF (p1 <> NIL) AND (p2 <> NIL) THEN
1798     MonomPuta(p1, p2, pr);
1799     p2 := p2^.veza;
1800     WHILE p2 <> NIL DO
1801       MonomPuta(p1, p2, pomocni);
1802       REPEAT
1803         UbaciMonom(pomocni, pr);
1804         pomocni := pomocni^.veza
1805       UNTIL pomocni = NIL;
1806       p2 := p2^.veza
1807     END
1808   END
1809 END Puta;
1810
1811 PROCEDURE Kolicnik(p1, p2: Polinom; VAR kol, ost: Polinom; VAR ok: BOOLEAN);
1812
1813   PROCEDURE Deli(VAR kol, ost: Polinom);
1814   VAR
1815     novi, pomocni: Polinom;
1816   BEGIN
1817     IF ost <> NIL THEN
1818       IF ost^.st >= p2^.st THEN
1819         NEW(novi);
1820         novi^.k := - ost^.k / p2^.k;
1821         novi^.st := ost^.st - p2^.st;
1822         MonomPuta(p2, novi, pomocni);
1823         Saberi(ost, pomocni, ost);
1824         novi^.k := - novi^.k;
1825         UbaciMonom(novi, kol);
1826         DISPOSE(novi);
1827         Deli(kol, ost)
1828       END
1829     END
1830   END Deli;
1831
1832 BEGIN (* Kolicnik *)
1833   ok := TRUE;
1834   Anuliraj(kol);
1835   IF p2 = NIL THEN
1836     ok := FALSE
1837   ELSE
1838     Kopiraj(p1, ost);
1839     Deli(kol, ost)
1840   END
1841 END Kolicnik;
1842
1843 PROCEDURE PolinomNaN(p: Polinom; n: CARDINAL;
1844                      VAR rez: Polinom);
1845 VAR
1846   i: CARDINAL;
1847 BEGIN
1848   IF n = 0 THEN
1849     NEW(rez);
1850     rez^.k := 1.0;
1851     rez^.st := 0;
1852     rez^.veza := NIL;
1853   ELSIF n = 1 THEN
1854         Kopiraj( p, rez );
1855   ELSE
1856     rez := p;
1857     FOR i := 2 TO n DO
1858       Puta(rez, p, rez)
1859     END
1860   END;
1861 END PolinomNaN;
1862
1863 PROCEDURE DisposePolinom(VAR p: Polinom);
1864 VAR
1865   pomocni: Polinom;
1866 BEGIN
1867   pomocni := p;
1868   WHILE pomocni # NIL DO
1869     p := p^.veza;
1870     DISPOSE(pomocni);
1871     pomocni := p
1872   END
1873 END DisposePolinom;
1874
1875 END PolinomL.
1876 \end{codeblock}
1877
1878
1879 \subsection{Zadatak: Sabiranje sa unapred određenim polinomom}
1880
1881 Želimo da ispišemo uneti polinom uvećan za\\ $x^5 - 3x^4 + 4x + 7$.
1882
1883 \begin{lstlisting}[style=codeblock]
1884 MODULE polinom;
1885 FROM PolinomL IMPORT Polinom, Stampaj, Anuliraj, DisposePolinom, UbaciMonom, Unos, Saberi;
1886 FROM InOut IMPORT WriteString, WriteLn;
1887 FROM Storage IMPORT ALLOCATE, DEALLOCATE;
1888
1889 VAR
1890   p,q,rez,pom : Polinom;
1891
1892 BEGIN
1893   (* korisnik unosi prvi polinom *)
1894   WriteString("Unesite polinom:");
1895   WriteLn;
1896   Unos(p);
1897   (* drugi polinom kreiramo mi,
1898      monom po monom *)
1899   Anuliraj(q); (* isto sto i q:=NIL; *)
1900   (* formiramo monom x^5 *)
1901   NEW(pom);
1902   pom^.st:=5;
1903   pom^.k:=1.0;
1904   (* dodajemo ga u polinom *)
1905   UbaciMonom(pom,q);
1906   DISPOSE(pom);
1907   (* -3 x^4 *)
1908   NEW(pom);
1909   pom^.st := 4;
1910   pom^.k := -3.0;
1911   UbaciMonom(pom,q);
1912   DISPOSE(pom);
1913   (* 4 x *)
1914   NEW(pom);
1915   pom^.st := 1;
1916   pom^.k := 4.0;
1917   UbaciMonom(pom,q);
1918   DISPOSE(pom);
1919   (* 7 (x^0) *)
1920   NEW(pom);
1921   pom^.st := 0;
1922   pom^.k := 7.0;
1923   UbaciMonom(pom,q);
1924   DISPOSE(pom);
1925   (* saberemo polinome *)
1926   Saberi(p, q, rez);
1927   (* odstampamo rezultat *)
1928   Stampaj(rez,0);
1929   WriteLn;
1930   (* oslobadjanje zauzete memorije *)
1931   DisposePolinom(p);
1932   DisposePolinom(q);
1933   DisposePolinom(rez);
1934 END polinom.
1935 \end{lstlisting}
1936
1937 \subsection{Zadatak: Suma k polinoma}
1938
1939 Napisati program koji ucitava broj k (1<=k<=50) i k polinoma, a nakon
1940 toga izracunava njihovu sumu
1941
1942 \begin{lstlisting}[style=codeblock]
1943 MODULE PolSuma;
1944
1945 FROM PolinomL IMPORT Polinom, Anuliraj, DisposePolinom, Unos, Stampaj, SaberiNa;
1946 FROM InOut IMPORT WriteLn, WriteString, ReadCard, WriteCard;
1947 CONST
1948   maxk = 50;
1949 TYPE
1950   nizPol = ARRAY [1..maxk] OF Polinom;
1951 VAR
1952   i, k: CARDINAL;
1953   suma : Polinom;
1954   p : nizPol;
1955 BEGIN
1956   REPEAT
1957     WriteString('Unesite broj k (1 <= k <= ');
1958     WriteCard(maxk, 1);
1959     WriteString(') ');
1960     ReadCard(k);
1961     WriteLn;
1962   UNTIL (1 <= k) AND (k <= maxk);
1963   FOR i := 1 TO k DO
1964     WriteLn;
1965     WriteString('Unos ');
1966     WriteCard(i, 1);
1967     WriteString('. polinoma.');
1968     WriteLn;
1969     Unos(p[i])
1970   END;
1971   Anuliraj(suma);
1972   FOR i := 1 TO k DO
1973     SaberiNa(suma, p[i])
1974   END;
1975   WriteLn;
1976   WriteString('Njihova suma je:');
1977   WriteLn;
1978   Stampaj(suma, 4);
1979   DisposePolinom(suma);
1980   FOR i := 1 TO k DO
1981     DisposePolinom(p[i]);
1982   END;
1983 END PolSuma.
1984 \end{lstlisting}
1985
1986 \section{Stek i red opsluživanja}
1987
1988 \subsection{Zadatak: Ilustracija pisanja u fajl uz pomoć bafera}
1989
1990 \begin{lstlisting}[style=codeblock]
1991 DEFINITION MODULE QueueInfo;
1992 CONST
1993   Maxqueue = 100;
1994 TYPE
1995   InfoTip = CHAR;
1996
1997 END QueueInfo.
1998
1999 IMPLEMENTATION MODULE QueueInfo;
2000 END QueueInfo.
2001
2002 DEFINITION MODULE RedOpsl1;
2003 FROM QueueInfo IMPORT InfoTip,Maxqueue;
2004 TYPE
2005   Niz = ARRAY[1..Maxqueue] OF InfoTip;
2006   RedOpslTip = RECORD
2007         Prvi, Zadnji : CARDINAL;
2008         Element : Niz
2009   END;
2010
2011 PROCEDURE MakeNull(VAR q : RedOpslTip);
2012 PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
2013 PROCEDURE First(VAR q : RedOpslTip;
2014                 VAR x : InfoTip;
2015                 VAR ok : BOOLEAN);
2016 PROCEDURE PopFirst(VAR q : RedOpslTip;
2017                    VAR ok : BOOLEAN);
2018 PROCEDURE AddRear(VAR q : RedOpslTip;
2019                   x : InfoTip;
2020                   VAR ok : BOOLEAN);
2021
2022 END RedOpsl1.
2023
2024 IMPLEMENTATION MODULE RedOpsl1;
2025 FROM QueueInfo IMPORT Maxqueue,InfoTip;
2026
2027 PROCEDURE MakeNull(VAR q : RedOpslTip);
2028 BEGIN
2029   WITH q DO
2030     Prvi := 0;
2031     Zadnji := 0
2032   END
2033 END MakeNull;
2034
2035 PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
2036 BEGIN
2037   RETURN q.Zadnji = 0
2038 END Empty;
2039
2040
2041 PROCEDURE First(VAR q : RedOpslTip;
2042                 VAR x : InfoTip;
2043                 VAR ok : BOOLEAN);
2044 BEGIN
2045   IF Empty(q) THEN
2046     ok := FALSE
2047   ELSE
2048     ok := TRUE;
2049     WITH q DO
2050       x := Element[Prvi]
2051     END
2052   END
2053 END First;
2054
2055 PROCEDURE AddOne(i : CARDINAL) : CARDINAL;
2056 BEGIN
2057   IF i = Maxqueue THEN
2058     RETURN 1
2059   ELSE
2060     RETURN i+1
2061   END
2062 END AddOne;
2063
2064 PROCEDURE PopFirst(VAR q : RedOpslTip;
2065                    VAR ok : BOOLEAN);
2066 BEGIN
2067   IF Empty(q) THEN
2068     ok := FALSE
2069   ELSE
2070     ok := TRUE;
2071     WITH q DO
2072       IF Prvi = Zadnji THEN
2073         MakeNull(q)
2074       ELSE
2075         Prvi := AddOne(Prvi)
2076       END
2077     END
2078   END
2079 END PopFirst;
2080
2081 PROCEDURE AddRear(VAR q : RedOpslTip;
2082                   x : InfoTip;
2083                   VAR ok : BOOLEAN);
2084 BEGIN
2085   WITH q DO
2086     IF AddOne(Zadnji) = Prvi THEN
2087       ok := FALSE
2088     ELSE
2089       ok := TRUE;
2090       IF Empty(q) THEN
2091         Prvi := 1;
2092         Zadnji := 1
2093       ELSE
2094         Zadnji := AddOne(Zadnji)
2095       END;
2096       Element[Zadnji] := x
2097     END
2098   END
2099 END AddRear;
2100
2101 END RedOpsl1.
2102
2103 MODULE Bafer;
2104 FROM RedOpsl1 IMPORT RedOpslTip, MakeNull, Empty, First, PopFirst, AddRear;
2105 FROM FIO IMPORT File,WrChar, Create, Close;
2106 IMPORT IO;
2107
2108 CONST
2109   ImeIzlaza = 'izlaz.txt';
2110
2111 VAR
2112   izlaz : File;
2113   znak : CHAR;
2114   buffer : RedOpslTip;
2115
2116 PROCEDURE IsprazniBafer(VAR dat : File;
2117                         VAR buf : RedOpslTip);
2118 VAR
2119   znak : CHAR;
2120   ok : BOOLEAN;
2121 BEGIN
2122   WHILE NOT Empty(buf) DO
2123     First(buf, znak, ok);
2124     PopFirst(buf, ok);
2125     WrChar(dat, znak)
2126   END
2127 END IsprazniBafer;
2128
2129 PROCEDURE BaferWrite(VAR dat : File;
2130                      VAR buf : RedOpslTip;
2131                      znak : CHAR);
2132 VAR
2133   ok : BOOLEAN;
2134 BEGIN
2135   AddRear(buf, znak, ok);
2136   IF NOT ok THEN
2137     IsprazniBafer(dat, buf);
2138     AddRear(buf, znak, ok)
2139   END
2140 END BaferWrite;
2141
2142 BEGIN
2143   izlaz := Create(ImeIzlaza);
2144   MakeNull(buffer);
2145   IO.WrStr('Unesite tekst, koji treba da se unese u datoteku ');
2146   IO.WrStr(ImeIzlaza);
2147   IO.WrChar('.');
2148   IO.WrLn;
2149   IO.WrStr('Unos zavrsite tackom.');
2150   IO.WrLn;
2151   znak := IO.RdChar();
2152   WHILE znak # '.' DO
2153     BaferWrite(izlaz, buffer, znak);
2154     znak := IO.RdChar();
2155   END;
2156   IsprazniBafer(izlaz, buffer);
2157   Close(izlaz)
2158 END Bafer.
2159 \end{lstlisting}
2160
2161 \subsection%
2162 {Zadatak: Ispitivanje da li reč pripada gramatici wcw$^+$}
2163
2164 Reč pripada ovoj gramatici ako joj se prvi deo (w) sastoji samo od
2165 slova 'a' i 'b', sledi slovo 'c' a nakon njega obrnuta reč reči w.
2166
2167 \begin{lstlisting}[style=codeblock]
2168 DEFINITION MODULE Stek;
2169 CONST
2170   Maxstack = 100;
2171 TYPE
2172   Niz = ARRAY [1..Maxstack] OF CHAR;
2173   StekTip = RECORD
2174             Top : CARDINAL;
2175             Element : Niz
2176           END;
2177 PROCEDURE MakeNull(VAR s : StekTip);
2178 PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
2179
2180 PROCEDURE Top(VAR s : StekTip;
2181               VAR x : CHAR;
2182               VAR ok : BOOLEAN);
2183 PROCEDURE Pop(VAR s : StekTip;
2184               VAR ok : BOOLEAN);
2185 PROCEDURE Push(VAR s : StekTip;
2186                x : CHAR;
2187                VAR ok : BOOLEAN);
2188 END Stek.
2189
2190
2191 IMPLEMENTATION MODULE Stek;
2192
2193 PROCEDURE MakeNull(VAR s : StekTip);
2194 BEGIN
2195   s.Top := 0
2196 END MakeNull;
2197
2198 PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
2199 BEGIN
2200   RETURN s.Top = 0
2201 END Empty;
2202
2203 PROCEDURE Top(VAR s : StekTip;
2204               VAR x : CHAR;
2205               VAR ok : BOOLEAN);
2206 BEGIN
2207   IF Empty(s) THEN
2208     ok := FALSE
2209   ELSE
2210     ok := TRUE;
2211     WITH s DO
2212       x := Element[Top]
2213     END
2214   END
2215 END Top;
2216
2217 PROCEDURE Pop(VAR s : StekTip;
2218               VAR ok : BOOLEAN);
2219 BEGIN
2220   IF Empty(s) THEN
2221     ok := FALSE
2222   ELSE
2223     ok := TRUE;
2224     DEC(s.Top)
2225   END
2226 END Pop;
2227
2228 PROCEDURE Push(VAR s : StekTip;
2229                x : CHAR;
2230                VAR ok : BOOLEAN);
2231 BEGIN
2232   WITH s DO
2233     IF Top = Maxstack THEN
2234       ok := FALSE
2235     ELSE
2236       ok := TRUE;
2237       INC(Top);
2238       Element[Top] := x
2239     END
2240   END
2241 END Push;
2242 END Stek.
2243
2244 MODULE wcw;
2245 (* Da li rec pripada gramatici wcw+. *)
2246 FROM Stek IMPORT StekTip, MakeNull, Empty,
2247                  Top, Pop, Push;
2248 FROM InOut IMPORT Read, Write, WriteString, EOL;
2249 TYPE
2250   slova = SET OF CHAR;
2251 VAR
2252   S : StekTip;
2253   Ch, C : CHAR;
2254   ok : BOOLEAN;
2255 BEGIN
2256   MakeNull(S);
2257   Read(Ch);
2258   ok := TRUE;
2259   WHILE ok AND (Ch IN slova{'a', 'b'}) DO
2260     Push(S, Ch, ok);
2261     Read(Ch);
2262   END;
2263   IF NOT ok THEN
2264     WriteString('Greska - mali stek')
2265   ELSIF Ch # 'c' THEN
2266     WriteString('Pogresan string')
2267   ELSE
2268     Read(Ch);
2269     WHILE ok AND (Ch # EOL) DO
2270       Top(S, C, ok);
2271       ok := ok AND (C = Ch);
2272       IF ok THEN
2273         Pop(S, ok);
2274         Read(Ch);
2275       END
2276     END;
2277     IF NOT (ok AND Empty(S)) THEN
2278       WriteString('Pogresan string')
2279     ELSE
2280       WriteString('String pripada jeziku L')
2281     END
2282   END
2283 END wcw.
2284 \end{lstlisting}
2285
2286 \subsection{Zadatak: Kalkulator za izračunavanje postfiksnih izraza}
2287
2288
2289 Napraviti kalkulator za izračunavanje postfiksnih izraza. Svi brojevi
2290 koji figurišu u izrazu su jednocifreni.
2291
2292 \begin{lstlisting}[style=codeblock]
2293 MODULE PostFix;
2294
2295 FROM StekI IMPORT StekTip, MakeNull, Empty, Top, Pop, Push;
2296 FROM InOut IMPORT Read, Write, WriteInt, EOL;
2297 TYPE
2298   slova = SET OF CHAR;
2299 VAR
2300   S : StekTip;
2301   Ch : CHAR;
2302   Op1, Op2 : INTEGER;
2303   ok : BOOLEAN;
2304 PROCEDURE Conv(Ch : CHAR) : INTEGER;
2305 BEGIN
2306   RETURN  ORD(Ch) - ORD('0')
2307 END Conv;
2308
2309 BEGIN
2310   MakeNull(S);
2311   Read(Ch);
2312   WHILE Ch # EOL DO
2313     IF Ch IN slova{'+', '-', '/', '*', '%'} THEN
2314       Top(S, Op2, ok);
2315       Pop(S, ok);
2316       Top(S, Op1, ok);
2317       Pop(S, ok);
2318       CASE Ch OF
2319         '+' : Op1 := Op1 + Op2 |
2320         '-' : Op1 := Op1 - Op2 |
2321         '*' : Op1 := Op1 * Op2 |
2322         '/' : Op1 := Op1 DIV Op2 |
2323         '%' : Op1 := Op1 MOD Op2
2324       END;
2325       Push(S, Op1, ok)
2326     ELSE
2327       Push(S, Conv(Ch), ok)
2328     END;
2329     Read(Ch);
2330   END;
2331   Top(S, Op1, ok);
2332   Write('=');
2333   WriteInt(Op1,5)
2334 END PostFix.
2335 \end{lstlisting}
2336
2337
2338 \section{Simulacija rekurzije}
2339
2340
2341 Na početku označiti sve rekurzivne pozive u originalnoj proceduri
2342 adresama (npr. 1,2,3... ili konstante nabrojivog tipa podataka).
2343
2344 Na steku se čuvaju lokalne promenljive, parametri procedure i adresa
2345 mesta poziva, a u skladu sa tim se kreira InfoTip.
2346
2347 Trivijalnim pozivom se smatra onaj koji se izračunava bez dodatnih
2348 rekurzivnih poziva.
2349
2350 U kodu ispod, \kod{treba\_rekurzija} znači da je poziv netrivijalan,
2351 odnosno treba naći uslove pod kojima se sigurno dešavaju rekurzivni
2352 pozivi.
2353
2354 \begin{lstlisting}
2355 MakeNull(S);
2356 REPEAT
2357   WHILE treba_rekurzija DO
2358     -prepisati sve od pocetka originalne
2359      procedure do prvog rekurzivnog poziva
2360     -staviti na stek potrebne
2361      lokalne promenljive, parametre procedure i
2362      adresu mesta poziva
2363     -podesiti vrednosti parametara da budu
2364      kao u rekurzivnom pozivu procedure
2365   END;
2366   trivijalan poziv
2367   umesto RETURN x pisati rez := x
2368   jos := TRUE;
2369   WHILE jos AND NOT Empty(S) DO
2370     Top(S, el, ok);
2371     Pop(S, ok);
2372     -restauriramo vrednosti sa steka
2373     -u zavisnosti od adrese poziva nastavimo
2374      prepisivanje originalne procedure sa
2375      tog mesta
2376     -ako se dodje do novog rek. poziva tada:
2377        -sacuvati na steku vrednosti
2378        -podesiti vrednosti parametara da budu
2379         kao u rekurzivnom pozivu procedure
2380        -ici na pocetak koda
2381         (ovo se postize sa jos := FALSE)
2382     -inace
2383        ako se naidje na RETURN x pisati rez := x
2384   END
2385 UNTIL Empty(S);
2386 \end{lstlisting}
2387
2388 Ako je procedura funkcijska tada se na kraj dodaje \kod{RETURN rez}.
2389
2390 \subsection*{ZADACI}
2391
2392 Simulirati ponašanje sledećih rekurzivnih procedura (funkcija) upotrebom steka:
2393
2394 \subsection{Primer 1 -- faktorijel}
2395
2396
2397 \begin{lstlisting}[style=codeblock]
2398 MODULE Fakto;
2399 (* InfoTip = CARDINAL; *)
2400
2401 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2402 FROM StekC IMPORT StekTip, MakeNull, Empty,
2403                   Top, Pop, Push;
2404 VAR
2405   n : CARDINAL;
2406 PROCEDURE RFakto(n : CARDINAL) : CARDINAL;
2407 BEGIN
2408   IF n <= 1 THEN
2409     RETURN 1
2410   ELSE
2411     RETURN n * RFakto(n-1)
2412   END
2413 END RFakto;
2414
2415
2416 PROCEDURE SFakto(n : CARDINAL) : CARDINAL;
2417 VAR
2418   s : StekTip;
2419   rez : CARDINAL;
2420   OK : BOOLEAN;
2421 BEGIN
2422   MakeNull(s);
2423   WHILE n > 1 DO
2424     Push(s,n,OK);
2425     DEC(n)
2426   END;
2427   rez := 1;
2428   WHILE NOT Empty(s) DO
2429     Top(s, n, OK);
2430     Pop(s, OK);
2431     rez := n * rez
2432   END;
2433   RETURN rez
2434 END SFakto;
2435
2436 BEGIN
2437   WrStr('n = ');
2438   n := RdCard();
2439   WrLn
2440   WrStr('n! = ');
2441   WrCard(RFakto(n), 1);
2442   WrStr(' = ');
2443   WrCard(SFakto(n), 1)
2444 END Fakto.
2445 \end{lstlisting}
2446
2447 \subsection{Primer 2 -- stepenovanje}
2448
2449 \begin{lstlisting}[style=codeblock]
2450 MODULE Step;
2451 (* InfoTip = RECORD
2452                 x : REAL;
2453                 n : CARDINAL;
2454                 adr : (par, nepar)
2455              END;
2456 *)
2457
2458 FROM IO IMPORT WrStr, WrLn, WrReal,
2459         RdReal, RdCard;
2460 FROM StekStep IMPORT StekTip, MakeNull, Empty,
2461              Top, Pop, Push, InfoTip, AdrTip;
2462
2463 VAR
2464   n : CARDINAL;
2465   x : REAL;
2466
2467 PROCEDURE Sqr(y : REAL) : REAL;
2468 BEGIN
2469   RETURN y * y
2470 END Sqr;
2471
2472 PROCEDURE RStep(x : REAL;
2473                 n : CARDINAL) : REAL;
2474 BEGIN
2475   IF n = 0 THEN
2476     RETURN 1.
2477   ELSIF ODD(n) THEN
2478     RETURN x * Sqr( RStep(x, n DIV 2) )
2479   ELSE
2480     RETURN Sqr( RStep(x, n DIV 2) )
2481   END
2482 END RStep;
2483
2484 PROCEDURE SStep(x : REAL;
2485                 n : CARDINAL ) : REAL;
2486 VAR
2487   s : StekTip;
2488   OK : BOOLEAN;
2489   rez : REAL;
2490   el : InfoTip;
2491 BEGIN
2492   MakeNull(s);
2493   WHILE n > 0 DO
2494     el.x := x;
2495     el.n := n;
2496     IF ODD(n) THEN
2497       el.adr := nepar;
2498     ELSE
2499       el.adr := par
2500     END;
2501     Push(s,el,OK);
2502     n := n DIV 2
2503   END;
2504   rez := 1.;
2505   WHILE NOT Empty(s) DO
2506     Top(s, el, OK);
2507     Pop(s, OK);
2508     x := el.x;
2509     n := el.n;
2510     IF el.adr = nepar THEN
2511       rez := x * Sqr(rez)
2512     ELSE
2513       rez := Sqr(rez)
2514     END
2515   END;
2516   RETURN rez
2517 END SStep;
2518
2519 BEGIN
2520   WrStr('x =? ');
2521   x := RdReal();
2522   WrLn;
2523   WrStr('n =? ');
2524   n := RdCard();
2525   WrStr('x^n = ');
2526   WrReal(RStep(x, n), 10, 1);
2527   WrStr(' = ');
2528   WrReal(SStep(x, n), 10, 1)
2529 END Step.
2530 \end{lstlisting}
2531
2532 \subsection{Primer 3 -- Fibonači}
2533
2534 \begin{lstlisting}[style=codeblock]
2535 MODULE Fib;
2536 (* InfoTip = RECORD
2537                 n : CARDINAL;
2538                 PrviSab : CARDINAL;
2539                 adr : (prvi, drugi)
2540              END;
2541 *)
2542
2543 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2544 FROM StekFib IMPORT StekTip, MakeNull, Empty,
2545        Top, Pop, Push, InfoTip, AdrTip;
2546 VAR
2547   n : CARDINAL;
2548
2549 PROCEDURE RFib(n : CARDINAL) : CARDINAL;
2550 BEGIN
2551   IF n <= 1 THEN
2552     RETURN n
2553   ELSE
2554     RETURN RFib(n-1) + RFib(n-2)
2555   END
2556 END RFib;
2557
2558 PROCEDURE SFib(n : CARDINAL ) : CARDINAL;
2559 VAR
2560   s : StekTip;
2561   OK, jos : BOOLEAN;
2562   rez, PrviSab : CARDINAL;
2563   el : InfoTip;
2564 BEGIN
2565   MakeNull(s);
2566   REPEAT
2567     WHILE n > 1 DO
2568       el.n := n;
2569       el.adr := prvi;
2570       Push(s,el,OK);
2571       DEC(n)
2572     END;
2573     rez := (n);
2574     jos := TRUE;
2575     WHILE (NOT Empty(s)) AND jos DO
2576       Top(s, el, OK);
2577       Pop(s, OK);
2578       n := el.n;
2579       IF el.adr = prvi THEN
2580         PrviSab := rez;
2581         el.n := n;
2582         el.adr := drugi;
2583         el.PrviSab := PrviSab;
2584         Push(s, el, OK);
2585         DEC(n, 2);
2586         jos := FALSE
2587       ELSE
2588         PrviSab := el.PrviSab;
2589         rez := PrviSab + rez
2590       END
2591     END
2592   UNTIL Empty(s);
2593   RETURN rez
2594 END SFib;
2595
2596 BEGIN
2597   WrStr('n =? ');
2598   n := RdCard();
2599   WrStr('F(n) = ');
2600   WrCard(RFib(n), 1);
2601   WrStr(' = ');
2602   WrCard(SFib(n), 1)
2603 END Fib.
2604 \end{lstlisting}
2605
2606 \subsection{Primer 4 -- faktorijel 2}
2607
2608
2609 \begin{lstlisting}[style=codeblock]
2610 MODULE Faktor;
2611 (* InfoTip = CARDINAL; *)
2612 FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
2613 FROM StekC IMPORT StekTip, MakeNull, Empty,
2614                   Top, Pop, Push;
2615
2616 VAR
2617   n,rez : CARDINAL;
2618
2619 PROCEDURE RFakto(n : CARDINAL;
2620                  VAR rez : CARDINAL);
2621 BEGIN
2622   IF n = 0 THEN
2623     rez := 1
2624   ELSE
2625     RFakto(n-1, rez);
2626     rez := n * rez
2627   END
2628 END RFakto;
2629
2630 PROCEDURE SFakto(n : CARDINAL;
2631                  VAR rez : CARDINAL);
2632 VAR
2633   s : StekTip;
2634   OK : BOOLEAN;
2635 BEGIN
2636   MakeNull(s);
2637   WHILE n > 0 DO
2638     Push(s,n,OK);
2639     DEC(n)
2640   END;
2641   rez := 1;
2642   WHILE NOT Empty(s) DO
2643     Top(s, n, OK);
2644     Pop(s, OK);
2645     rez := n * rez
2646   END
2647 END SFakto;
2648
2649 BEGIN
2650   WrStr('n =? ');
2651   n := RdCard();
2652   WrLn;
2653   WrStr('n! = ');
2654   RFakto(n, rez);
2655   WrCard(rez, 1);
2656   WrStr(' = ');
2657   SFakto(n, rez);
2658   WrCard(rez, 1)
2659 END Faktor.
2660 \end{lstlisting}
2661
2662 \subsection{Primer 5 (ispitni)}
2663
2664
2665 \begin{lstlisting}[style=codeblock]
2666 MODULE Rek1;
2667 (* InfoTip = RECORD
2668                 d, g, m1, m2 : INTEGER;
2669                 adr : (prvi, drugi)
2670              END;
2671 *)
2672 FROM Stek1 IMPORT StekTip, adresa, InfoTip,
2673          MakeNull, Empty, Top, Pop, Push;
2674 IMPORT IO;
2675 VAR
2676   X : ARRAY [1..20] OF INTEGER;
2677
2678 PROCEDURE Max(d, g: INTEGER) : INTEGER;
2679 VAR
2680   m1, m2 : INTEGER;
2681 BEGIN
2682   IF d>g THEN
2683     RETURN MIN(INTEGER)
2684   ELSIF d=g THEN
2685     RETURN X[d]
2686   ELSE
2687     m1 := Max(d, (d+g) DIV 2);
2688     m2 := Max((d+g) DIV 2 +1, g);
2689     IF m1 > m2 THEN
2690       RETURN m1
2691     ELSE
2692       RETURN m2
2693     END
2694   END
2695 END Max;
2696
2697 PROCEDURE SMax(d, g: INTEGER) : INTEGER;
2698 VAR
2699   S : StekTip;
2700   el : InfoTip;
2701   ok, jos : BOOLEAN;
2702   m1, m2, rez : INTEGER;
2703 BEGIN
2704   MakeNull(S);
2705   REPEAT
2706     WHILE d<g DO
2707       el.d := d;
2708       el.g := g;
2709       el.adr := prvi;
2710       Push(S, el, ok);
2711       g := (d+g) DIV 2
2712     END;
2713     IF d>g THEN
2714       rez := MIN(INTEGER)
2715     ELSE (* d=g *)
2716       rez := X[d]
2717     END;
2718     jos := TRUE;
2719     WHILE jos AND NOT Empty(S) DO
2720       Top(S, el, ok);
2721       Pop(S, ok);
2722       d := el.d;
2723       g := el.g;
2724       m1 := el.m1;
2725       IF el.adr = prvi THEN
2726         m1 := rez;
2727         el.m1 := m1;
2728         el.adr := drugi;
2729         Push(S, el, ok);
2730         d := (d+g) DIV 2 + 1;
2731         jos := FALSE
2732       ELSE (*el.adr = drugi*)
2733         m2 := rez;
2734         IF m1 > m2 THEN
2735           rez := m1
2736         ELSE
2737           rez := m2
2738         END
2739       END
2740     END
2741   UNTIL Empty(S);
2742   RETURN rez
2743 END SMax;
2744
2745 BEGIN (* glavni program *)
2746   X[1] := 3;
2747   X[2] := 2;
2748   X[3] := 5;
2749   X[4] := -7;
2750   X[5] := 0;
2751   IO.WrCard(Max(1, 5), 3);
2752   IO.WrLn;
2753   IO.WrCard(SMax(1, 5), 3);
2754   IO.WrLn
2755 END Rek1.
2756 \end{lstlisting}
2757
2758 \subsection{Primer 6 (ispitni)}
2759
2760
2761 \begin{lstlisting}[style=codeblock]
2762 MODULE Rek2;
2763 (* InfoTip = RECORD
2764                 x, y, n : CARDINAL;
2765                 adr : (prvi, drugi, treci, cetvrti)
2766              END;
2767 *)
2768 FROM Stek2 IMPORT StekTip, adresa, InfoTip,
2769            MakeNull, Empty, Top, Pop, Push;
2770 IMPORT IO;
2771
2772 PROCEDURE g(x : CARDINAL; y : CARDINAL;
2773             n : CARDINAL) : CARDINAL;
2774 BEGIN
2775   IF n < 3 THEN
2776     RETURN x + y
2777   ELSIF ODD(n) THEN
2778     RETURN g(g(x+1, y, n-2), y, n-3)
2779   ELSE
2780     RETURN g(x, g(x, y+1, n-2), n-3)
2781   END
2782 END g;
2783
2784 PROCEDURE Sg(x : CARDINAL; y : CARDINAL;
2785              n : CARDINAL) : CARDINAL;
2786 VAR
2787   S : StekTip;
2788   el : InfoTip;
2789   ok, jos : BOOLEAN;
2790   rez : CARDINAL;
2791 BEGIN
2792   MakeNull(S);
2793   REPEAT
2794     WHILE n >= 3 DO
2795       IF ODD(n) THEN
2796         el.x := x;
2797         el.y := y;
2798         el.n := n;
2799         el.adr := prvi;
2800         Push(S, el, ok);
2801         INC(x);
2802         DEC(n, 2)
2803       ELSE
2804         el.x := x;
2805         el.y := y;
2806         el.n := n;
2807         el.adr := treci;
2808         Push(S, el, ok);
2809         INC(y);
2810         DEC(n, 2)
2811       END
2812     END;
2813     rez := x+y;
2814     jos := TRUE;
2815     WHILE jos AND NOT Empty(S) DO
2816       Top(S, el, ok);
2817       Pop(S, ok);
2818       x := el.x;
2819       y := el.y;
2820       n := el.n;
2821       IF el.adr = prvi THEN
2822         el.adr := drugi;
2823         Push(S, el, ok);
2824         x := rez;
2825         DEC(n, 3);
2826         jos := FALSE
2827       ELSIF el.adr = treci THEN
2828         el.adr := cetvrti;
2829         Push(S, el, ok);
2830         y := rez;
2831         DEC(n, 3);
2832         jos := FALSE
2833       END
2834     END
2835   UNTIL Empty(S);
2836   RETURN rez
2837 END Sg;
2838
2839 BEGIN (* glavni program *)
2840   IO.WrCard(g(2, 3, 10), 3);
2841   IO.WrCard(Sg(2, 3, 10), 3);
2842 END Rek2.
2843 \end{lstlisting}
2844
2845 %\columnbreak
2846
2847 \appendix
2848
2849 \section{Native XDS Modula 2 -- kratko uputstvo}
2850
2851
2852 Ovo uputstvo ukratko pokriva kako se može nabaviti XDS Modula 2 za Windows
2853 sistem, njenu instalaciju, te kako napraviti i pokretnuti jednostavan program.
2854
2855 \subsection*{Dobavljanje instalacije}
2856
2857
2858 Native XDS Modula 2 se može besplatno skinuti sa sajta proizvođača,
2859 \url{http://www.excelsior-usa.com/}, tačnije na adresi:
2860
2861 \url{http://www.excelsior-usa.com/xdsdl.html}
2862
2863 Prvo se prikazuje ugovor o korišćenju koji na dnu treba potvrditi da ste
2864 razumeli i da ćete ga se pridržavati.
2865
2866 Na stranici koja se potom otvara je potrebno odabrati sledeće pakete za
2867 download:
2868
2869 * Native XDS-x86 2.51 for Windows (6.5MB)
2870 \url{http://www.excelsior-usa.com/download/xds25x/xds-x86-251-enduser-win32.exe}
2871
2872 * TSCP add-on (2.4MB)
2873 \url{http://www.excelsior-usa.com/download/xds25x/tscp-x86-251-enduser-win32.exe}
2874
2875 \subsection*{Instalacija okruženja}
2876
2877 Prvo treba instalirati osnovno okruženje (xds-x86...), a potom i Top
2878 Speed Compatibility Pack (tscp-x86...), koji je potreban za neke
2879 module koji se koriste.
2880
2881 \emph{Korisnicima Windows-a 7 preporučujemo da pokrenu instalacione
2882   pakete pomoću opcije ``Run as administrator'' do koje se stiže desnim
2883   klikom miša.}
2884
2885 Pretpostavićemo u daljem tekstu da je program instaliran u
2886 \kod{C:/XDS/}
2887
2888 \subsection*{Pokretanje okruženja}
2889
2890 Po uspešnoj instalaciji bi trebalo da postoji ikonica na desktopu, kao
2891 i grupa sa programom u start meniju.
2892
2893 Ukoliko iz bilo kakvog razloga ne postoje odgovarajuće prečice,
2894 okruženje se može pokrenuti uz pomoć izvršnog fajla
2895 \kod{C:/XDS/BIN/xds.exe} (ako je instalirano na podrazumevanoj
2896 lokaciji).
2897
2898 \subsection*{Prvi projekat}
2899
2900 Da bismo mogli da pišemo i pokrećemo svoj program, potrebno je prvo
2901 napraviti projekat za njega, što se radi na sledeći način:
2902
2903 \begin{itemize}
2904
2905 \item
2906  Iz menija se odabere Project->New.
2907 \item U dijalogu se klikne na gornje dugme ``Browse'', odabere se putanja gde
2908   će se kreirati projekat i ukuca se ime novog projekta.
2909
2910 \item U drugom polju ``Template'' ne treba da piše ništa. Ukoliko
2911   postoji neki tekst, obrisati ga.
2912
2913 \item Kliknuti na ``OK''
2914
2915 \item Iskočiće dijalog na kome piše da ne postoji fajl za editovanje,
2916   kliknuti na ``OK'' da se on napravi.
2917
2918 \item Pojavljuje se forma za kucanje programa, ukucati (na primer):
2919
2920 \begin{minipage}{\columnwidth}
2921 \begin{lstlisting}[style=codeblock]
2922   MODULE Hello;
2923   FROM InOut IMPORT WriteString,WriteLn;
2924   BEGIN
2925     WriteString("Hello World");
2926     WriteLn;
2927   END Hello.
2928 \end{lstlisting}
2929 \end{minipage}
2930
2931 \item Program se može pokrenuti na različite načine, pri čemu se
2932   automatski prevodi:
2933
2934   \begin{itemize}
2935
2936   \item Klik na ``Run'' ikonicu u toolbaru (plavi čovečuljak koji trči)
2937
2938   \item Meni Debug->Run
2939
2940   \item Prečica Ctrl+F9 na tastaturi
2941
2942   \end{itemize}
2943
2944 \item Ako je sve u redu sa programom, treba da se pojavi novi terminal
2945   u kome se ispisuje rezultat izvršavanja programa, u našem slučaju
2946   jednostavna pozdravna poruka.
2947 \end{itemize}
2948
2949 Naravno moguće je i samo prevesti (kompajlirati) program, tako da se
2950 samo prikažu greške (ako ih ima) i bez pokretanja programa:
2951 \begin{itemize}
2952 \item Klik na ``Compile'' ikonicu u toolbaru
2953 \item Meni Tools->Compile
2954 \item Prečica F9 na tastaturi
2955 \end{itemize}
2956
2957 Ukoliko u programu postoje greške, on neće biti pokrenut, već će se
2958 dobiti lista grešaka u donjem delu prozora. Na primer ako obrišemo ``S''
2959 u četvrtom redu i probamo da pokrenemo program, taj red će biti
2960 označen svetlo plavom bojom i dobićemo poruku:
2961
2962 \kod{- Error in pro1.mod [4:5]: Undeclared identifier "Writeting"}
2963
2964 Što znači da u četvrtom redu, kod petog karatkera postoji problem, da
2965 identifikator nije deklarisan, što najčešće znači da ga nismo uvezli,
2966 ili, kao u našem slučaju, da smo napravili grešku u kucanju.
2967
2968 Stvar na koju isto treba obratiti pažnju je da se nekad greška
2969 prijavljue nešto kasnije u tekstu nego što je napravljena. Na primer,
2970 ako obrišemo ``;'' na kraju četvrtog reda i probamo da pokrenemo
2971 program, peti red će biti označen svetlo plavom bojom i dobićemo
2972 poruku:
2973
2974 \kod{- Error in pro1.mod [5:5]: Expected symbol ";" }
2975
2976 Ovo se desilo jer nedostaje tačka zarez na kraju četvrtog reda, ali će
2977 kompajler probati da je traži i dalje, pa će tek na početku petog reda
2978 prijaviti grešku.
2979
2980 U spisku se takođe pojavljuje i upozorenje (Warning) o tome da se
2981 uvezena komanda WriteString ne koristi nigde u programu. Često se
2982 upozorenja mogu ignorisati, a pažnju uglavnom treba obraćati na
2983 greške, odnosno poruke koje počinju sa ``Error''.
2984
2985 Takođe se često dešava da su druge prijavljene greške posledica prve,
2986 te je poželjno ponovo kompajlirati (ili pokretati) program posle svake
2987 ispravljene greške.
2988
2989 \paragraph{Napomena o template-ovima pri kreiranju projekta:}
2990 Moguće je namestiti da u dijalogu za novi projekat drugo polje ``Template''
2991  uvek bude prazno. Potrebno je u tom istom dijalogu kliknuti na
2992  ``Configure'', a potom isprazniti polje ``default template''.
2993
2994
2995 \mainend
2996
2997 \end{document}