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