% skripta-spa1.tex
% Skripta za predmet Strukture podataka i algoritmi 1, DMI, PMF, NS

\documentclass[a4paper,twoside]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}%definišemo da je ulaz utf-8 fajl

% osnovne informacije koje ce se prikazati na naslovnoj strani,
% kao i u informacijama u generisanom pdfu
\newcommand{\autor}{Vladimir Kurbalija, Milos Radovanovic, Doni Pracner}
\newcommand{\naslov}{Skripta za vezbe iz predmeta strukture podataka
  i algoritmi 1} 
\newcommand{\datum}{April 2012, Novi Sad}
\newcommand{\verzija}{ver 12b}
%sc=single-column
\usepackage[serbian]{babel}
\usepackage{fancyhdr}
\pagestyle{fancy}

\title{\naslov -- \verzija}
\author{\autor}
\date{\datum}

%change the default font
\usepackage{lmodern}
\renewcommand{\familydefault}{\sfdefault}

\usepackage{pifont}

%podesavanja outputa za pdf verzije
\usepackage[bookmarks,pdffitwindow=false,unicode=true,%
pdftitle={\naslov -- \verzija},%
pdfauthor={\autor}%
]{hyperref}

\usepackage{graphicx}
\usepackage{listings}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{multicol}

%margine
%experiment 
%\usepackage[top=2.5cm, bottom=1.5cm, left=3cm, right=2cm]{geometry}
%staro: 
\usepackage[top=1.5cm, bottom=1cm, left=2cm, right=1cm]{geometry}

\begin{document}

%customize the itemize environments

\let\olditemize=\itemize
\def\itemize{
\olditemize
  \setlength{\itemsep}{1pt}
  \setlength{\parskip}{0pt}
  \setlength{\parsep}{0pt}
  \setlength{\topsep}{-1cm}
  \setlength{\partopsep}{1pt}
}

%% ovi redovi daju header i footer

\renewcommand{\sectionmark}[1]{\markright{\thesection\ #1}}
\fancyhf{} % delete current setting for header and footer
%\fancyfoot[C]{\thepage}
\fancyhead[LO]{\bfseries\rightmark}
\fancyhead[RO]{\thepage}
\fancyhead[RE]{Strukture podataka i algoritmi 1 -- skripta}
\fancyhead[LE]{\thepage}
\renewcommand{\headrulewidth}{0.5pt}
\renewcommand{\headwidth}{\textwidth}
%\renewcommand{\footrulewidth}{0.5pt}
%\addtolength{\headheight}{0.5pt} % make space for the rule
\fancypagestyle{plain}{%
\fancyhead{} % get rid of headers on plain pages
\fancyfoot{}
\renewcommand{\headrulewidth}{0pt} % and the line
\renewcommand{\footrulewidth}{0pt} % and the line
}
\renewcommand{\headheight}{15pt}

%promene u marginama:
%\setlength{\marginparwidth}{32pt}
%\setlength{\textwidth}{620pt}
%\setlength{\textheight}{620pt}


%% specijalni blokovi koji služe kao podsetnici u radu ili napomene
\newcommand{\skica}[1]{
    \noindent \framebox{\parbox[c]{0.9\textwidth}{  {\small** \textit{#1}  }}
    \newline }
}

\newcommand{\skicas}[1]{
    \framebox{* \textit{#1} *}
}

%boldovane skice visokog prioriteta
\newcommand{\skicab}[1]{
  \noindent \framebox{\parbox[c]{0.9\textwidth}{ {\small***
        \textbf{#1} }} \newline } }

\newcommand{\kod}[1]{{\small\texttt{#1}}}

% ako je sledeci red odkomentarisan nista od skica nece biti ispisano
% u finalni dokument

% \renewcommand{\skica}[1]{}

% title u skladu sa uobičajenim na Departmanu
\newcommand{\makemytitle}{
  \begin{center}
	\makebox{%
	\includegraphics[width=2cm]{grbPMF} 
	\parbox[b]{65ex}{\centering 
		Univerzitet u Novom Sadu\\
                Prirodno-matematički fakultet\\
                Departman za matematiku i informatiku}
	\includegraphics[width=2cm]{grbUNS}
	}
	\vspace{10ex} 

	\parbox[b]{\textwidth}{{\Large {\bf 
              Vladimir Kurbalija, \href{mailto:kurba@dmi.rs}{kurba@dmi.rs}\\ 
              Miloš Radovanović, \href{mailto:radacha@dmi.rs}{radacha@dmi.rs}\\ 
              Doni Pracner, \href{mailto:doni.pracner@dmi.rs}{doni.pracner@dmi.rs}}}}
	\vspace{5ex}
	
        {\Large {\bf Skripta za vežbe iz predmeta }} 
        
        {\Huge {\bf
            \setlength{\baselineskip}{1.5\baselineskip}Strukture
              podataka i algoritmi 1}}
			
	\vspace{5ex}
	%\vfill

	\verzija \ -- \datum
	
	\end{center}
	\thispagestyle{plain}
%	\newpage
}

\makemytitle

% theorems, definition etc.
%''''''''''''''''''''''''''

\theoremstyle{definition}
\newtheorem{def1}{Definicija}
\theoremstyle{plain}
\newtheorem{theo}{Teorema}
\newtheorem{lema}{Lema}

\lstloadlanguages{Modula-2}

\lstset{
	basicstyle=\footnotesize\ttfamily,
        showstringspaces=false,
	breaklines=true
}

\lstdefinestyle{codeblock}{
	basicstyle=\footnotesize,
        keywordstyle=\textbf,
        columns=[l]fixed,
        breakatwhitespace=true,
%        prebreak=\P,
%        postbreak=\ding{229}\space,
        language=Modula-2
}

\lstdefinestyle{numcodeblock}{
  style=codeblock,
  numbers=left
}

\lstnewenvironment{codeblock}{\lstset{style=codeblock}}{}

% ----------------==================--------------------------------------
%                 Pravi pocetak rada


Programi u ovoj skripti su testirani sa kompajlerom 'Native XDS Modula
2' sa instaliranim dodatnim paketom TSCP (Top Speed Compatibility
Pack), potrebnim za neke od modula koji se ne nalaze u ISO standardu
Module 2.

\tableofcontents

\newpage

\begin{multicols}{2}
\section{Ilustracija efikasnosti algoritma}

\subsection{Zadatak: Pronaći sve pitagorine
trojke do zadate granice}


\begin{lstlisting}[style=codeblock]
MODULE Trojke1;
(* Pitagorine trojke koriscenjem "Brute-force" *)
FROM InOut IMPORT WriteString, WriteLn, WriteCard;
CONST
  Gr = 100;
VAR
  a, b, c : [1 .. Gr];
BEGIN
  FOR a := 1 TO Gr DO
    FOR b := 1 TO Gr DO
      FOR c := 1 TO Gr DO
        IF a*a + b*b = c*c THEN
          WriteLn;
          WriteString('a = ');
          WriteCard(a,2);
          WriteString(', b = ');
          WriteCard(b,2);
          WriteString(', c = ');
          WriteCard(c,2)
        END
      END
    END
  END
END Trojke1.
\end{lstlisting}

\begin{codeblock}
MODULE Trojke2;
(*Pitagorine trojke koriscenjem zaokrugljivanja*)
FROM InOut IMPORT WriteString, WriteLn, WriteCard;
FROM MathLib0 IMPORT sqrt;
CONST
  Gr = 100;
VAR
  a, b, c : CARDINAL;
  creal : REAL;
BEGIN
  FOR a := 1 TO Gr DO
    FOR b := 1 TO Gr DO
      creal := FLOAT(a*a) + FLOAT(b*b);
      creal := sqrt(creal);
      c := TRUNC(creal);
      IF creal = FLOAT(c) THEN
        WriteLn;
        WriteString(' a = ');
        WriteCard(a,2);
        WriteString(', b = ');
        WriteCard(b,2);
        WriteString(', c = ');
        WriteCard(c,2)
      END
    END
  END
END Trojke2.
\end{codeblock}

\begin{codeblock}
MODULE Trojke3;
(* Pitagorine trojke koriscenjem teoreme *)
FROM InOut IMPORT WriteString, WriteLn, WriteCard;
CONST
  Gr = 10;
VAR
  a, b, c, m, n : CARDINAL;
BEGIN
  FOR m := 1 TO Gr DO
    FOR n := 1 TO m-1 DO
      a := 2*m*n;
      b := m*m - n*n;
      c := m*m + n*n;
      WriteLn;
      WriteString('a = ');
      WriteCard(a,2);
      WriteString(', b = ');
      WriteCard(b,2);
      WriteString(', c = ');
      WriteCard(c,2)
    END
  END
END Trojke3.
\end{codeblock}

\begin{codeblock}
MODULE Trojke4;
(* Pitagorine trojke kod kojih je razlika
   izmedju katete i hipotenuze tacno 1 *)
FROM InOut IMPORT WriteString, WriteLn, WriteCard;
CONST
  Gr = 10;
VAR
  a, b, c, m, n : CARDINAL;
BEGIN
  FOR m := 2 TO Gr DO
    n := m - 1;
    a := 2*m*n;
    b := m*m - n*n;
    c := m*m + n*n;
    WriteLn;
    WriteString('a = ');
    WriteCard(a,2);
    WriteString(', b = ');
    WriteCard(b,2);
    WriteString(', c = ');
    WriteCard(c,2)
  END
END Trojke4.
\end{codeblock}

\begin{lstlisting}[style=codeblock]
MODULE Trojke5;
(* Pitagorine trojke kod kojih je razlika 
   izmedju kateta jedan *)
FROM InOut IMPORT WriteString, WriteLn, WriteCard;
CONST
  Gr = 7;
VAR
  a, b, c, m, n, w, i, temp : CARDINAL;
BEGIN
  w := 1;
  n := 0;
  FOR i := 1 TO Gr DO
    m := n + w;
    a := 2*m*n;
    b := m*m - n*n;
    c := m*m + n*n;
    WriteLn;
    WriteString('a = ');
    WriteCard(a,2);
    WriteString(', b = ');
    WriteCard(b,2);
    WriteString(', c = ');
    WriteCard(c,2);
    temp := w;
    w := 3*w + 4*n;
    n := 2*temp + 3*n
  END
END Trojke5.
\end{lstlisting}


\subsection[Zadatak: Maksimalna suma susednih elemenata u
nizu]{Zadatak: Maksimalna suma proizvoljnog broja susednih elemenata u
  nizu celih brojeva}

\begin{lstlisting}[style=codeblock]
MODULE MaxNiza1;
(* Prvo resenje. Brute Force: O(n^3)  *)
FROM InOut IMPORT WriteString,ReadInt,
           WriteInt,WriteCard,WriteLn;
CONST
  N = 10;
TYPE
  Interval = [1..N];
VAR
  Max, Suma : INTEGER;
  d,g,i,Ood,Doo : Interval;
  X : ARRAY Interval OF INTEGER;
BEGIN
  WriteString(' Unesite niz X ');
  WriteLn;
  FOR i := 1 TO N DO
    ReadInt(X[i]);
    WriteLn
  END;
  Max := 0;
  FOR d := 1 TO N DO
    FOR g := 1 TO N DO
      Suma := 0;
      FOR i := d TO g DO
        Suma := Suma + X[i]
      END;
      IF Suma > Max THEN
        Max := Suma;
        Ood := d;
        Doo := g
      END
    END
  END;
  WriteLn;
  WriteString(' Maksimum je ');
  WriteInt(Max,3);
  WriteString(' u intervalu od ');
  WriteCard(Ood,3);
  WriteString(' do ');
  WriteCard(Doo,3)
END MaxNiza1.

MODULE MaxNiza2;
(* Drugo resenje: O(n^2). 
   Koristi se cinjenica da je suma X[d..g]
   izracunljiva iz X[d..g-1].  *)
FROM InOut IMPORT WriteString,ReadInt, 
           WriteInt,WriteCard,WriteLn;
CONST
  N = 10;
TYPE
  Interval = [1..N];
VAR
  Max, Suma : INTEGER;
  d,g,i,Ood,Doo : Interval;
  X : ARRAY Interval OF INTEGER;
BEGIN
  WriteString(' Unesite niz X ');
  WriteLn;
  FOR i := 1 TO N DO
    ReadInt(X[i]);
    WriteLn
  END;
  Max := 0;
  FOR d := 1 TO N DO
    Suma := 0;
    FOR g := d TO N DO
      Suma := Suma + X[g];
      IF Suma > Max THEN
        Max := Suma;
        Ood := d;
        Doo := g
      END
    END
  END;
  WriteLn;
  WriteString(' Maksimum je ');
  WriteInt(Max,3);
  WriteString(' u intervalu od ');
  WriteCard(Ood,3);
  WriteString(' do ');
  WriteCard(Doo,3)
END MaxNiza2.
\end{lstlisting}

\begin{codeblock}
MODULE MaxNiza3;
(* Trece resenje: O(n^2). 
   Koristi pomocni niz u kome je na i-tom mestu
   suma podniza x[1..i] *)
FROM InOut IMPORT WriteString,ReadInt,
           WriteInt,WriteCard,WriteLn;
CONST
  N = 10;
TYPE
  Interval = [1..N];
VAR
  Max, Suma : INTEGER;
  d,g,i,Ood,Doo : Interval;
  X : ARRAY Interval OF INTEGER;
  Pom : ARRAY [0..N] OF INTEGER;
BEGIN
  WriteString(' Unesite niz X ');
  WriteLn;
  FOR i := 1 TO N DO
    ReadInt(X[i]);
    WriteLn
  END;
  Pom[0] := 0;
  FOR i := 1 TO N DO
    Pom[i] := Pom[i-1] + X[i]
  END;
  Max := 0;
  FOR d := 1 TO N DO
    FOR g := d TO N DO
      Suma := Pom[g] - Pom[d-1];
      IF Suma > Max THEN
        Max := Suma;
        Ood := d;
        Doo := g
      END
    END
  END;
  WriteLn;
  WriteString(' Maksimum je ');
  WriteInt(Max,3);
  WriteString(' u intervalu od ');
  WriteCard(Ood,3);
  WriteString(' do ');
  WriteCard(Doo,3)
END MaxNiza3.
\end{codeblock}

\begin{codeblock}
MODULE MaxNiza4;
(* Cetvrto resenje. Najbolje moguce: O(n)  *)
FROM InOut IMPORT WriteString,ReadInt,
           WriteInt,WriteCard,WriteLn;
CONST
  N = 10;
TYPE
  Interval = [1..N];
VAR
  Max, MaxDovde : INTEGER;
  i,d,Ood,Doo : Interval;
  X : ARRAY Interval OF INTEGER;
BEGIN
  WriteString(' Unesite niz X ');
  WriteLn;
  FOR i := 1 TO N DO
    ReadInt(X[i]);
    WriteLn
  END;
  Max := 0;
  MaxDovde := 0;
  FOR i := 1 TO N DO
    IF MaxDovde = 0 THEN
      d := i
    END;
    MaxDovde := MaxDovde + X[i];
    IF MaxDovde < 0 THEN
      MaxDovde := 0
    END;
    IF MaxDovde > Max THEN
      Ood := d;
      Doo := i;
      Max := MaxDovde
    END
  END;
  WriteLn;
  WriteString(' Maksimum je ');
  WriteInt(Max,3);
  WriteString(' u intervalu od ');
  WriteCard(Ood,3);
  WriteString(' do ');
  WriteCard(Doo,3)
END MaxNiza4.
\end{codeblock}

\section{Rad sa fajlovima}

\subsection{Modul FIO}

U ovom modulu je definisan tip \kod{File}, koji predstavlja jedan fajl
sa kojim radimo.

U primerima se pretpostavlja da je „f“ tipa \kod{File}, „str“ niz
znakova, „i“ tipa \kod{INTEGER}, „c“ tipa \kod{CARDINAL} i „ch“ tipa
\kod{CHAR}. Dodatna promenljiva „n“ tipa \kod{INTEGER} služi za
formatiranje slično kao u modulu \kod{InOut}.

Promenljiva tipa \kod{File} se mora vezati za neki fajl
jednom od sledećih komandi:\\
\kod{f := Open(str);} -- otvara se postojeci fajl za čitanje\\
\kod{f := Create(str);} -- kreira se fajl za pisanje\\
\kod{f := Append(str);} -- otvara se postojeći za dopisivanje na kraj

\kod{Close(f);} -- po završetku rada fajl se mora zatvoriti

Procedure za čitanje i pisanje imaju parametar „\kod{f}“ koji označava
 fajl sa kojim se radi.\\
\kod{RdStr(f,str)} -- učitava ceo red u string str\\
\kod{RdItem(f,str)} -- učitava jednu reč u string str (učitava znakove iz fajla dok ne naiđe na separator)\\
\kod{i:= RdInt(f); c:= RdCard(f)} -- učitava broj, koji se dobija kao rezultat procedure\\
\kod{ch:= RdChar(f)} -- vraća jedan znak iz fajla

Procedure za pisanje različitih tipova u fajl:
\kod{WrStr(f,str); WrInt(f,i,n); WrCard(f,c,n);WrChar(f,ch);}

\kod{WrLn(f);} -- upisuje prelom reda u fajl

\kod{EOF} -- logička promenljiva, označava da li smo poslednjom
operacijom čitanja stigli do kraja fajla.  Ne menja joj se vrednost
pri operacijama otvaranja i zatvaranja fajlova, odnosno neće se pri
tome resetovati na \kod{FALSE}.


\subsection{Zadatak: ispis sadržaja fajla na ekran}

Potrebno je sve redove iz fajla učitati i ispisati ih na ekran.

\begin{lstlisting}[style=codeblock]
MODULE ispis;
FROM FIO IMPORT File, Open, Close, EOF, RdStr;
FROM InOut IMPORT WriteString, WriteLn, ReadString;

PROCEDURE ispisF(ime: ARRAY OF CHAR);
VAR
  f:File;
  s : ARRAY[1..100] OF CHAR;
BEGIN
  f:=Open(ime);
  EOF := FALSE;
  WHILE NOT EOF DO
      RdStr(f,s);
      WriteString(s);
      WriteLn;
  END;
  Close(f);
END ispisF;

VAR
  ime: ARRAY[1..100] OF CHAR;
BEGIN
  WriteString("unesite ime fajla:");
  ReadString(ime);
  ispisF(ime);
END ispis.
\end{lstlisting}

\subsection{Zadatak: spisak studenata}

Napraviti program koji iz fajla učitava podatke o studentima, dodaje
novog studenta u spisak i snima fajl.  U fajlu se u svakom redu nalazi
podatak o jednom studentu, redom prezime, ime i godina rođenja,
razdvojeni razmacima.

\begin{lstlisting}[style=codeblock]
MODULE nizslog;
FROM InOut IMPORT WriteString, WriteLn, 
     WriteCard, ReadCard, ReadString;
FROM FIO IMPORT File, Open, Create, Close, EOF,
    RdItem, RdCard, WrStr, WrCard, WrLn;
FROM Str IMPORT Compare;

CONST
    MaxStud = 100;
TYPE
    String = ARRAY[1..30] OF CHAR;
    Student = RECORD
        ime, prez: String;
        god: CARDINAL;
    END;
    Studenti = ARRAY[1..MaxStud] OF Student;

PROCEDURE UcitajF(fajl:String;
          VAR spisak: Studenti; VAR n:CARDINAL);
VAR
    f:File;
BEGIN
    n:=0;
    f:= Open(fajl);
    EOF := FALSE;
    WHILE NOT EOF DO
        INC(n);
        RdItem(f, spisak[n].prez);
        RdItem(f, spisak[n].ime);
        spisak[n].god := RdCard(f);
    END;
    Close(f);
END UcitajF;

PROCEDURE Ispisi(spisak:Studenti; n:CARDINAL);
VAR
    i: CARDINAL;
BEGIN
    FOR i:=1 TO n DO
        WriteString(spisak[i].prez);
        WriteString(" ");
        WriteString(spisak[i].ime);
        WriteString(" ");
        WriteCard(spisak[i].god,1);
        WriteLn;
    END;
END Ispisi;

PROCEDURE IspisiF(fajl:String;
          spisak:Studenti; n:CARDINAL);
VAR
    f:File;
    i: CARDINAL;
BEGIN
    IF (n>0) AND (n<=MaxStud) THEN
        f:=Create(fajl);
        (* pravimo takav fajl da ne
           postoji zadnji prazan red *)
        FOR i:=1 TO n-1 DO
            WrStr(f,spisak[i].prez);
            WrStr(f," ");
            WrStr(f,spisak[i].ime);
            WrStr(f," ");
            WrCard(f,spisak[i].god,1);
            WrLn(f);
        END;
        WrStr(f,spisak[n].prez);
        WrStr(f," ");
        WrStr(f,spisak[n].ime);
        WrStr(f," ");
        WrCard(f,spisak[n].god,1);
        Close(f);
    END;
END IspisiF;

PROCEDURE NoviStudent(VAR spisak:Studenti;
                      VAR n:CARDINAL);
VAR
    stud,temp:Student;
    i:CARDINAL;
    dodaj:BOOLEAN;
BEGIN
    IF n<MaxStud THEN
        WriteString("Prezime novog studenta?");
        ReadString(stud.prez);
        WriteString("Ime novog studenta?");
        ReadString(stud.ime);
        WriteString("Godina rodjenja");
        WriteString("novog studenta?");
        ReadCard(stud.god);
        (* proverimo da li vec postoji *)
        i:=1;
        dodaj := TRUE;
        WHILE (i<=n) AND dodaj DO
            temp := spisak[i];
            IF (temp.god = stud.god) &
              (Compare(temp.prez,stud.prez)=0) &
              (Compare(temp.ime,stud.ime)=0) THEN
                dodaj:=FALSE;
            END;
            INC(i);
        END;
        IF dodaj THEN
            INC(n);
            spisak[n]:=stud;
        ELSE
            WriteString("podaci vec postoje!");
        END;
    ELSE
        WriteString("popunjen kapacitet!");
    END;
END NoviStudent;

VAR
    spisak : Studenti;
    fajl:String;
    n:CARDINAL;
BEGIN
    fajl:="studenti.txt";
    UcitajF(fajl, spisak, n);
    Ispisi(spisak, n);
    NoviStudent(spisak,n);
    IspisiF(fajl, spisak, n);
END nizslog.
\end{lstlisting}

\section{Liste i pokazivači}

Za rad sa pokazivačima je potrebno iz modula Storage uvesti procedure
\kod{ALLOCATE} i \kod{DEALLOCATE}. U kodu se tada mogu koristiti i njihovi
skraćeni oblici \kod{NEW} i \kod{DISPOSE}.

\subsection{Zadatak: Formiranje, štampanje i brisanje listi}


\begin{lstlisting}[style=codeblock]
MODULE liste;
FROM InOut IMPORT WriteString, WriteLn, WriteInt,
	ReadInt, ReadCard;
FROM Storage IMPORT ALLOCATE, DEALLOCATE;
TYPE
  brojevi = POINTER TO brojSlog;
  brojSlog = RECORD
      info:INTEGER;
      veza:brojevi;
  END;
VAR
  n,i:CARDINAL;
  lista : brojevi;
  br:INTEGER;

PROCEDURE DodajPoc(VAR lista:brojevi; br:INTEGER);
(* dodaje broj br na pocetak liste *)
VAR
  temp:brojevi;
BEGIN
  NEW(temp);
  temp^.info := br;
  temp^.veza := lista;
  lista := temp;
END DodajPoc;

PROCEDURE Stampaj(lista:brojevi);
VAR
  temp:brojevi;
BEGIN
  temp:=lista;
  WHILE temp # NIL DO
      WriteInt(temp^.info,0);
      WriteLn;
      temp := temp^.veza;
  END;
END Stampaj;

PROCEDURE Unisti(VAR lista:brojevi);
VAR
  temp:brojevi;
BEGIN
  temp:=lista;
  WHILE temp # NIL DO
        lista:=lista^.veza;
        DISPOSE(temp);
        temp:=lista;
  END;
END Unisti;

BEGIN
  lista := NIL;
  WriteString('unesite n (broj brojeva): ');
  ReadCard(n);
  WriteString('unesite brojeve: ');
  WriteLn;
  FOR i:= 1 TO n DO
      ReadInt(br);
      DodajPoc(lista,br);
  END;
  WriteString('sadrzaj liste:');
  WriteLn;
  Stampaj(lista);
  Unisti(lista);
  WriteString('memorija je oslobodjena');
  WriteLn;
END liste.
\end{lstlisting}

Alternativno je poziv \kod{DodajPoc} moguće zameniti pozivom jedne od
sledeće dve procedure čime se dobija dodavanje elementa na kraj liste,
ili kreiranje sortirane liste:

\begin{lstlisting}[style=codeblock]
PROCEDURE DodajKraj(VAR lista:brojevi; br:INTEGER);
(* dodaje element na kraj liste *)
VAR
  tekuci, temp :brojevi;
BEGIN
  NEW(temp);
  temp^.info := br;
  temp^.veza := NIL;
  IF lista = NIL THEN
     (* prazna lista *)
     lista:=temp;
  ELSE
     tekuci := lista;
     WHILE tekuci^.veza#NIL DO
        tekuci:=tekuci^.veza;
     END;
     tekuci^.veza := temp;
  END;
END DodajKraj;

PROCEDURE DodajSort(VAR lista:brojevi; br:CARDINAL);
(* dodaje broj tako da lista ostane sortirana 
   (podrazumeva se da je vec sortirana) *)
VAR
  temp, tekuci : brojevi;
BEGIN
  NEW(temp);
  temp^.info:=br;
  temp^.veza:=NIL;
  IF (lista = NIL) OR (lista^.info>=br) THEN
  (*prazna lista ili na pocetak*)
    temp^.veza:=lista;
    lista := temp;
  ELSE
  (*negde u listi*)
    tekuci:= lista;
    WHILE (tekuci^.veza # NIL) AND 
          (tekuci^.veza^.info<=br) DO
      tekuci:=tekuci^.veza;
    END;
    temp^.veza := tekuci^.veza;
    tekuci^.veza:=temp;
  END;
END DodajSort;
\end{lstlisting}

\subsection{Zadatak: Prikaz osnovih operacija nad listama}

\begin{lstlisting}[style=codeblock]
MODULE liste2;
FROM InOut IMPORT WriteString, WriteLn,
           WriteCard, ReadCard;
FROM IO IMPORT RdKey;
FROM Storage IMPORT ALLOCATE, DEALLOCATE;
TYPE
  skupZn = SET OF CHAR;
  brojevi = POINTER TO brojSlog;
  brojSlog = RECORD
      info:CARDINAL;
      veza:brojevi;
  END;
VAR
  lista : brojevi;
  menu,prazno:CHAR;

PROCEDURE DodajPoc(VAR lista:brojevi; br:INTEGER);
(* dodaje broj pom na pocetak liste *)
VAR
  temp:brojevi;
BEGIN
  (* kreiramo novi element *)
  NEW(temp);
  temp^.info := br;
  (* treba da pokazuje na ostatak liste *)
  temp^.veza := lista;
  (* pocetak liste je novi element *)
  lista := temp;
END DodajPoc;

PROCEDURE Unos(VAR lista:brojevi);
(* dodaje n brojeva u listu *)
VAR
  n,i,br:CARDINAL;
BEGIN
  WriteString('unesite n (broj brojeva): ');
  ReadCard(n);
  FOR i:= 1 TO n DO
      WriteString("unesite broj ");
      WriteCard(i,0);
      WriteString(": ");
      ReadCard(br);
      DodajPoc(lista,br);
  END;
END Unos;

(* -- procedure za stampu -- *)

PROCEDURE Stampaj(lista:brojevi);
(* stampa sadrzaj liste na ekran *)
VAR
  temp:brojevi;
BEGIN
  WriteLn;
  WriteString("Sadrzaj liste:");
  WriteLn;
  temp:=lista;
  WHILE temp # NIL DO
      WriteCard(temp^.info,0);
      WriteLn;
      temp := temp^.veza;
  END;
END Stampaj;

PROCEDURE StampajK(VAR lista:brojevi);
(* stampa k-ti element (k unosi korisnik) *)
VAR
  temp:brojevi;
  k,brojac:CARDINAL;
BEGIN
  WriteString("unesite redni broj elementa:");
  ReadCard(k);
  temp:=lista;
  brojac := 1;
  WHILE (temp# NIL) AND (k>brojac) DO
    temp:=temp^.veza;
    INC(brojac);
  END;
  IF (temp#NIL) THEN
    WriteCard(temp^.info,2);
  ELSE
    WriteString("greska! - ne postoji element");
    WriteString(" u listi sa rednim brojem ");
    WriteCard(k,2);
  END;
  WriteLn();
END StampajK;

PROCEDURE StampajMinimum(VAR lista:brojevi);
(* nalazi i stampa minimalni element liste *)
VAR
  temp:brojevi;
  min:CARDINAL;
BEGIN
  IF (lista=NIL) THEN
    WriteString("prazna lista!");
  ELSE
    min:=lista^.info;
    temp:=lista^.veza;
    WHILE temp # NIL DO
      IF temp^.info < min THEN
        min := temp^.info;
      END;
      temp := temp^.veza;
    END;
    WriteString("Minimalni element liste je ");
    WriteCard(min,0);
  END;
  WriteLn;
END StampajMinimum;

(* -- pomocne procedure, bez ispisa  -- *)

PROCEDURE UListi(lista:brojevi; 
                 br: CARDINAL):BOOLEAN;
(* vraca da li se 'br' nalazi u listi 'lista' *)
VAR
  temp:brojevi;
BEGIN
  temp:=lista;
  WHILE (temp # NIL) AND (temp^.info # br) DO
    (* dok ne dodjemo do kraja liste 
       ili ne nadjemo broj *)
      temp := temp^.veza;
  END;
  IF temp#NIL THEN
    (* znaci da nismo na kraju liste, 
       tj da je nadjen broj *)
    RETURN TRUE;
  ELSE (* temp = NIL *)
    RETURN FALSE;
  END;
END UListi;

PROCEDURE IzbaciIzListe(VAR lista:brojevi; 
                        br: CARDINAL):BOOLEAN;
(* izbacuje broj 'br' iz liste, naravno ako 
   postoji i vraca da li je operacija uspesno 
   obavljena *)
VAR
  temp,prethodni:brojevi;
BEGIN
  (* proverimo da li je prvi element *)
  IF (lista # NIL) AND (lista^.info = br) THEN
    temp:=lista;
    lista :=lista^.veza;
    DISPOSE(temp);
    RETURN TRUE;
  ELSE
  (* trazimo u ostatku liste *)
    temp:=lista;
    prethodni:=NIL;
    WHILE (temp # NIL) AND (temp^.info # br) DO
        (* dok ne dodjemo do kraja liste 
           ili ne nadjemo broj *)
        prethodni:=temp;
        temp := temp^.veza;
    END;
    IF temp#NIL THEN
      (* znaci da nismo na kraju liste, 
         odnosno da smo nasli broj *)
      (* prevezemo listu oko elementa *)
      prethodni^.veza:=temp^.veza;
      DISPOSE(temp);
      RETURN TRUE;
    ELSE
      RETURN FALSE;
    END;
  END;
END IzbaciIzListe;

(* - procedure sa interakcijom sa korisnikom - *)

PROCEDURE IzbacivanjeEl(VAR lista:brojevi);
(* izbacuje uneti broj iz liste koristeci proceduru IzbaciIzListe *)
VAR
  br:CARDINAL;
BEGIN
  WriteString("unesite broj za izbacivanje: ");
  ReadCard(br);
  IF IzbaciIzListe(lista,br) THEN
    WriteString("broj je izbacen iz liste");
  ELSE
    WriteString("greska! - broj ne postoji");
  END;
  WriteLn;
END IzbacivanjeEl;

PROCEDURE IzbacivanjeK(VAR lista:brojevi);
(* izbacuje k-ti element iz liste *)
VAR
  temp,tekuci:brojevi;
  k,brojac:CARDINAL;
BEGIN
  IF lista=NIL THEN
    WriteString("lista je prazna, nema ");
    WriteString("elemenata za izbacivanje");
  ELSE
    WriteString("unesite redni broj elementa");
    WriteString(" koji zelite izbaciti:");
    ReadCard(k);
    IF k=1 THEN (*izbacivanje prvog *)
      temp:=lista;
      lista := lista^.veza;
      DISPOSE(temp);
    ELSE
      tekuci := lista;
      brojac := 2; (*gledamo jedan unapred*)
      WHILE (tekuci^.veza# NIL) AND (k>brojac) DO
        (* idemo kroz listu do k-tog el *)
        tekuci:=tekuci^.veza;
        INC(brojac);
      END;
      IF (tekuci^.veza#NIL) THEN
         (* pamtimo element za brisanje *)
         temp:=tekuci^.veza;
         (* prevezujemo listu oko njega*)
         tekuci^.veza:=tekuci^.veza^.veza;
         DISPOSE(temp);
      ELSE
        WriteString("greska! - ne postoji el ");
        WriteString("u listi sa rednim brojem ");
        WriteCard(k,2);
      END;
      WriteLn();
    END;
  END;
END IzbacivanjeK;

PROCEDURE Pretraga(lista:brojevi);
(* provera da li se uneti broj nalazi u listi *)
VAR
  br:CARDINAL;
BEGIN
  WriteString("unesite trazeni broj");
  ReadCard(br);
  IF UListi(lista,br) THEN
    WriteString("broj postoji u listi");
  ELSE
    WriteString("broj ne postoji u listi");
  END;
  WriteLn;
END Pretraga;

(* -- oslobadjanje memorije -- *)

PROCEDURE Unisti(VAR lista:brojevi);
VAR
  temp:brojevi;
BEGIN
  temp:=lista;
  WHILE temp # NIL DO
        lista:=lista^.veza;
        DISPOSE(temp);
        temp:=lista;
  END;
END Unisti;

BEGIN
  (* pocinjemo od prazne liste *)
  lista := NIL;
  REPEAT
     WriteLn;
     WriteString("Ilustracija rada sa");
     WriteString(" listama brojeva");
     WriteLn;
     WriteString("=============================");
     WriteLn;
     WriteString("s - stampa");WriteLn;
     WriteString("u - unos");WriteLn;
     WriteString("i - izbacivanje br iz liste");
     WriteLn;
     WriteString("e - izbacivanje k-tog el.");
     WriteLn;
     WriteString("k - stampanje k-tog elementa");
     WriteLn;
     WriteString("m - minimalni broj u listi");
     WriteLn;
     WriteString("p - pretraga el. u listi");
     WriteLn;
     WriteLn;
     WriteString("q - kraj rada (quit)");WriteLn;
      REPEAT
        menu := CAP(RdKey());
      UNTIL menu IN skupZn{'S','U','E','I',
                           'M','K','P','Q'};
      IF menu#'Q' THEN
        CASE menu OF
         'S' : Stampaj(lista);|
         'U' : Unos(lista);|
         'I' : IzbacivanjeEl(lista);|
         'E' : IzbacivanjeK(lista);|
         'K' : StampajK(lista); |
         'M' : StampajMinimum(lista); |
         'P' : Pretraga(lista);|
        END;
        WriteLn;
        WriteString("--- pritisnite bilo koji ");
        WriteString("taster za povratak u meni");
        prazno:=RdKey();
      ELSE
        WriteString("Kraj rada")
      END;
      WriteLn;
  UNTIL menu='Q';
  Unisti(lista);
END liste2.
\end{lstlisting}


\subsection{Zadatak: Prikaz operacija nad listama sa jedinstvenim ključem}

\begin{lstlisting}[style=codeblock]
MODULE Radnici;

FROM InOut IMPORT WriteString, ReadString,
           WriteLn, WriteCard, ReadCard, Done;
FROM IO IMPORT RdKey;
FROM Storage IMPORT ALLOCATE, DEALLOCATE;

TYPE
  skupZn = SET OF CHAR;
  str = ARRAY [1..20] OF CHAR;
  radnici = POINTER TO slog;
  slog = RECORD
           ime, prez : str;
           broj : CARDINAL;
           sled : radnici
         END;
VAR
  meni, pom : CHAR;
  rad : radnici;

  PROCEDURE Clear();
  VAR
    br: CARDINAL;
  BEGIN
    FOR br:=1 TO 100 DO
      WriteLn;
    END;
  END Clear;

  PROCEDURE Spisak(rad : radnici);
  BEGIN
    WHILE rad # NIL DO
      WriteString(rad^.ime);
      WriteString(' ');
      WriteString(rad^.prez);
      WriteCard(rad^.broj, 8);
      WriteLn;
      rad := rad^.sled
    END
  END Spisak;

  PROCEDURE Zaposli(VAR rad : radnici);
  VAR
    novi, tek : radnici;
    nadjen : BOOLEAN;
  BEGIN
    NEW(novi);
    REPEAT
      WriteString('Ime, prezime i jedinstveni');
      WriteString(' broj novog radnika: ');
      WriteLn;
      ReadString(novi^.ime);
      ReadString(novi^.prez);
      ReadCard(novi^.broj);
      nadjen := FALSE;
      tek := rad;
      WHILE NOT nadjen AND (tek # NIL) AND
            (tek^.broj <= novi^.broj) DO
        IF novi^.broj = tek^.broj THEN
          nadjen := TRUE
        ELSE
          tek := tek^.sled
        END
      END
    UNTIL Done AND NOT nadjen;
    IF (rad = NIL) OR (novi^.broj<rad^.broj) THEN
      novi^.sled := rad;
      rad := novi
    ELSE
      tek := rad;
      WHILE (tek^.sled # NIL) AND
            (tek^.sled^.broj < novi^.broj) DO
        tek := tek^.sled
      END;
      novi^.sled := tek^.sled;
      tek^.sled := novi
    END
  END Zaposli;

  PROCEDURE Otpusti(VAR rad : radnici);
  VAR
    tek, pom : radnici;
    br : CARDINAL;
  BEGIN
    REPEAT
      WriteLn;
      WriteString('Unesite redni broj radnika:');
      ReadCard(br)
    UNTIL Done;
    WriteLn;
    IF rad = NIL THEN
      WriteString('Greska.')
    ELSIF br = rad^.broj THEN
      pom := rad;
      rad := rad^.sled;
      DISPOSE(pom)
    ELSE
      tek := rad;
      WHILE (tek^.sled # NIL) AND
            (tek^.sled^.broj < br) DO
        tek := tek^.sled
      END;
      IF (tek^.sled = NIL) OR
         (tek^.sled^.broj > br) THEN
        WriteString('Greska.')
      ELSE
        pom := tek^.sled;
        tek^.sled := tek^.sled^.sled;
        DISPOSE(pom)
      END
    END
  END Otpusti;

  PROCEDURE Inform(rad : radnici);
  VAR
    br : CARDINAL;
  BEGIN
    REPEAT
      WriteLn;
      WriteString('Unesite redni broj radnika:');
      ReadCard(br)
    UNTIL Done;
    WriteLn;
    WHILE (rad # NIL) AND (rad^.broj < br) DO
      rad := rad^.sled
    END;
    IF (rad = NIL) OR (rad^.broj # br) THEN
      WriteString('Greska.')
    ELSE
      WriteString(rad^.ime);
      WriteString(' ');
      WriteString(rad^.prez)
    END
  END Inform;

  PROCEDURE Bankrot(VAR rad : radnici);
  VAR
    pom : radnici;
  BEGIN
    WHILE rad # NIL DO
      pom := rad;
      rad := rad^.sled;
      DISPOSE(pom)
    END
  END Bankrot;

BEGIN
  rad := NIL;
  REPEAT
    Clear;
    WriteString('s - spisak svih zaposlenih');
    WriteLn;
    WriteString('z - zaposljavanje radnika');
    WriteLn;
    WriteString('o - otpustanje radnika');
    WriteLn;
    WriteString('i - informacije o radniku');
    WriteLn;
    WriteString('b - bankrot firme');
    WriteLn;
    WriteString('k - kraj rada');
    WriteLn;
    REPEAT
      meni := RdKey();
    UNTIL CAP(meni) IN skupZn{'S', 'Z', 'O', 
                              'I', 'B', 'K'};
    Clear;
    IF CAP(meni) # 'K' THEN
      CASE CAP(meni) OF
        'S' : Spisak(rad)|
        'Z' : Zaposli(rad)|
        'O' : Otpusti(rad)|
        'I' : Inform(rad)|
        'B' : Bankrot(rad)
      END;
      WriteLn;
      WriteString('-- pritisnite bilo koji ');
      WriteString('taster za nastavak --');
      pom := RdKey()
    END
  UNTIL CAP(meni) = 'K'
END Radnici.
\end{lstlisting}

Procedura \kod{Spisak} se može realizovati i u rekurzivnoj verziji:

\begin{lstlisting}[style=codeblock]
  PROCEDURE Spisak(rad : radnici);
  BEGIN
    IF rad # NIL THEN
      WriteString(rad^.ime);
      WriteString(' ');
      WriteString(rad^.prez);
      WriteCard(rad^.broj, 8);
      WriteLn;
      Spisak(rad^.sled)
    END
  END Spisak;
\end{lstlisting}

\subsection[Zadatak: Dve liste osoba sa istim sadržajem]{Zadatak: Dve
  liste osoba koje dele sadržaj, jedna sortirana po visini, druga po
  težini}

Sa tastature ucitavati po dva broja koji opisiuju osobu (visina i
tezina) i smestati ih u povezane listu, tako da postoji neopadajuce
uredjenje i po visini i po tezini.

\begin{lstlisting}[style=codeblock]
MODULE VisTez;
FROM Storage IMPORT ALLOCATE, DEALLOCATE;
FROM IO IMPORT WrLn, WrStr, RdCard, WrCard;
FROM SYSTEM IMPORT TSIZE;
TYPE
  pok = POINTER TO element;
  element = RECORD
              visina, tezina : CARDINAL;
              Vveza, Tveza : pok
            END;
VAR
  pocV, pocT : pok;
  vis, tez : CARDINAL;
PROCEDURE Ispisi(pocV, pocT : pok);
VAR
  tek : pok;
BEGIN
  tek := pocV;
  WrStr('Po visini:');
  WrLn;
  WHILE tek # NIL DO
    WrCard(tek^.visina, 6);
    tek := tek^.Vveza
  END;
  WrLn;
  tek := pocT;
  WrStr('Po tezini:');
  WrLn;
  WHILE tek # NIL DO
    WrCard(tek^.tezina,6);
    tek := tek^.Tveza
  END
END Ispisi;

PROCEDURE Ubaci(VAR pocV, pocT : pok;
                vis, tez : CARDINAL);
VAR
  novi, tek, iza : pok;
  nadjen : BOOLEAN;
BEGIN
  IF pocV = NIL THEN
    ALLOCATE(pocV, TSIZE(element));
    pocV^.visina := vis;
    pocV^.tezina := tez;
    pocV^.Vveza := NIL;
    pocV^.Tveza := NIL;
    pocT := pocV
  ELSE
    ALLOCATE(novi, TSIZE(element));
    novi^.visina := vis;
    novi^.tezina := tez;
    tek := pocV;
    nadjen := FALSE;
    WHILE (tek # NIL) AND NOT nadjen DO
      nadjen := vis <= tek^.visina;
      IF NOT nadjen THEN
        iza := tek;
        tek := tek^.Vveza
      END
    END;
    novi^.Vveza := tek;
    IF tek = pocV THEN
      pocV := novi
    ELSE
      iza^.Vveza := novi
    END;
    tek := pocT;
    nadjen := FALSE;
    WHILE (tek # NIL) AND NOT nadjen DO
      nadjen := tez <= tek^.tezina;
      IF NOT nadjen THEN
        iza := tek;
        tek := tek^.Tveza
      END
    END;
    novi^.Tveza := tek;
    IF tek = pocT THEN
      pocT := novi
    ELSE
      iza^.Tveza := novi
    END
  END
END Ubaci;

BEGIN
  pocV := NIL;
  pocT := NIL;
  WrStr('Unesite visinu ---- ');
  vis := RdCard();
  WHILE vis > 0 DO
    WrStr('Unesite tezinu ---- ');
    tez := RdCard();
    Ubaci(pocV, pocT, vis, tez);
    WrLn;
    WrStr('Unesite visinu ---- ');
    vis := RdCard()
  END;
  WrLn;
  Ispisi(pocV, pocT)
END VisTez.
\end{lstlisting}

\section{Polinomi preko listi}

\subsection{Moduli}

Polinomi su predstavljeni pomoću pokazivača. Apstraktni tip podataka
\kod{Polinom} je definisan u globalnom modulu.

\begin{lstlisting}[style=codeblock]
DEFINITION MODULE PolinomL;
TYPE
  Polinom = POINTER TO Monom;
  Monom = RECORD
            k : REAL;
            st : CARDINAL;
            veza : Polinom
          END;

PROCEDURE Anuliraj(VAR p: Polinom);
PROCEDURE Unos(VAR p: Polinom);
PROCEDURE Stampaj(p: Polinom; d: CARDINAL);
PROCEDURE Kopiraj(p: Polinom; 
                  VAR kopija: Polinom);
PROCEDURE UbaciMonom(mon:Polinom; 
                     VAR p: Polinom);
PROCEDURE PromeniZnak(VAR p: Polinom);
PROCEDURE Saberi(p1, p2: Polinom; 
                 VAR zbir: Polinom);
PROCEDURE SaberiNa(p: Polinom; VAR rez: Polinom);
PROCEDURE Oduzmi(p1,p2: Polinom; 
                 VAR razlika: Polinom);
PROCEDURE MonomPuta(p, mon: Polinom; 
                    VAR mp : Polinom);
PROCEDURE Puta(p1, p2: Polinom; VAR pr: Polinom);
PROCEDURE Kolicnik(p1, p2: Polinom;
                   VAR kol, ost: Polinom;
                   VAR ok : BOOLEAN);
PROCEDURE PolinomNaN(p: Polinom; n: CARDINAL;
                     VAR rez: Polinom);
PROCEDURE DisposePolinom(VAR p: Polinom);

END PolinomL.
(* --- kraj definicionog modula --- *)

IMPLEMENTATION MODULE PolinomL;
FROM InOut IMPORT Write, WriteString, WriteLn,
           WriteCard, ReadCard, Done;
FROM RealInOut IMPORT WriteReal, ReadReal;
FROM Storage IMPORT ALLOCATE, DEALLOCATE;

PROCEDURE Anuliraj(VAR p: Polinom);
BEGIN
  IF p # NIL THEN
    DisposePolinom(p);
  END;
END Anuliraj;

PROCEDURE Kopiraj(p: Polinom;
                  VAR kopija: Polinom);
VAR
  pomocni: Polinom;
BEGIN
  IF p = NIL THEN
    kopija := NIL
  ELSE
    NEW(kopija);
    kopija^ := p^;
    p := p^.veza;
    pomocni := kopija;
    WHILE p <> NIL DO
      NEW(pomocni^.veza);
      pomocni := pomocni^.veza;
      pomocni^ := p^;
      p := p^.veza
    END
  END
END Kopiraj;

PROCEDURE Stampaj(p: Polinom; d: CARDINAL);

  PROCEDURE StampajMonom(m : Polinom);
  BEGIN
    WITH m^ DO
      IF st <> 0 THEN
        IF ABS(k) <> 1.0 THEN
          WriteReal(ABS(k), d)
        END;
        Write('x');
        IF st <> 1 THEN
          Write('^');
          WriteCard(st, 1)
        END
      ELSE
        WriteReal(ABS(k), d)
      END
    END
  END StampajMonom;

BEGIN
  IF p = NIL THEN
    WriteReal(0., d)
  ELSE
    IF p^.k < 0.0 THEN
      WriteString(' - ')
    END;
    StampajMonom(p);
    p := p^.veza;
    WHILE p <> NIL DO
      IF p^.k > 0.0 THEN
        WriteString(' + ')
      ELSE
        WriteString(' - ')
      END;
      StampajMonom(p);
      p := p^.veza
    END
  END
END Stampaj;

PROCEDURE UbaciMonom(mon :Polinom; 
                     VAR p: Polinom);
VAR
  stari, tekuci, kopija: Polinom;
BEGIN
  IF mon # NIL THEN
    NEW(kopija);
    kopija^ := mon^;
    tekuci := p;
	stari := NIL;
    WHILE (tekuci#NIL) AND (tekuci^.st>kopija^.st) DO
      stari := tekuci;
      tekuci := tekuci^.veza
    END;
    kopija^.veza := tekuci;
    IF tekuci = p THEN
      p := kopija
    ELSE
      stari^.veza := kopija
    END;
    IF (tekuci#NIL) AND 
           (kopija^.st = tekuci^.st) THEN
      kopija^.k := kopija^.k + tekuci^.k;
      kopija^.veza := tekuci^.veza;
      DISPOSE(tekuci);
      IF kopija^.k = 0.0 THEN
        IF p = kopija THEN
          p := kopija^.veza
        ELSE
          stari^.veza := kopija^.veza
        END;
        DISPOSE(kopija)
      END
    END
  END
END UbaciMonom;

PROCEDURE Unos(VAR p : Polinom);
VAR
  i, n: CARDINAL;
  novi: Polinom;
BEGIN
  Anuliraj(p);
  REPEAT
    WriteLn;
    WriteString('Unesite broj monoma n (n>=0) ');
    ReadCard(n);
  UNTIL Done;
  WriteLn;
  FOR i := 1 TO n DO
    NEW(novi);
    WITH novi^ DO
      REPEAT
        WriteString('koeficijent monoma br.');
        WriteCard(i, 1);
        WriteString(' (<> 0):');
        ReadReal(k);
        WriteLn
      UNTIL k <> 0.0;
      REPEAT
        WriteLn;
        WriteString('eksponent monoma br.');
        WriteCard(i, 1);
        WriteString(' (>= 0): ');
        ReadCard(st);
      UNTIL Done;
      WriteLn;
    END;
    UbaciMonom(novi, p);
    DISPOSE(novi);
  END
END Unos;

PROCEDURE Saberi(p1, p2: Polinom; 
                 VAR zbir: Polinom);
BEGIN
  Kopiraj(p1, zbir);
  WHILE p2 <> NIL DO
    UbaciMonom(p2, zbir);
    p2 := p2^.veza
  END
END Saberi;

PROCEDURE SaberiNa(p: Polinom; 
                   VAR rez: Polinom);
BEGIN
  WHILE p <> NIL DO
    UbaciMonom(p,rez);
    p := p^.veza;
  END;
END SaberiNa;

PROCEDURE PromeniZnak(VAR p: Polinom);
VAR
  t: Polinom;
BEGIN
  t := p;
  WHILE t <> NIL DO
    t^.k := - t^.k;
    t := t^.veza
  END
END PromeniZnak;

PROCEDURE Oduzmi(p1,p2: Polinom; 
                 VAR razlika: Polinom);
BEGIN
  Kopiraj(p2, razlika);
  PromeniZnak(razlika);
  WHILE p1 <> NIL DO
    UbaciMonom(p1, razlika);
    p1 := p1^.veza
  END
END Oduzmi;

PROCEDURE MonomPuta(p, mon: Polinom; 
                    VAR mp: Polinom);
VAR
  tekuci: Polinom;
BEGIN
  Anuliraj(mp);
  IF (mon <> NIL) AND (p <> NIL) THEN
    NEW(mp);
    mp^.k := p^.k * mon^.k;
    mp^.st := p^.st + mon^.st;
    p := p^.veza;
    tekuci := mp;
    WHILE p <> NIL DO
      NEW(tekuci^.veza);
      tekuci := tekuci^.veza;
      tekuci^.k := p^.k * mon^.k;
      tekuci^.st := p^.st + mon^.st;
      p := p^.veza
    END;
    tekuci^.veza := NIL
  END
END MonomPuta;

PROCEDURE Puta(p1, p2: Polinom; VAR pr: Polinom);
VAR
  pomocni: Polinom;
BEGIN
  Anuliraj(pr);
  IF (p1 <> NIL) AND (p2 <> NIL) THEN
    MonomPuta(p1, p2, pr);
    p2 := p2^.veza;
    WHILE p2 <> NIL DO
      MonomPuta(p1, p2, pomocni);
      REPEAT
        UbaciMonom(pomocni, pr);
        pomocni := pomocni^.veza
      UNTIL pomocni = NIL;
      p2 := p2^.veza
    END
  END
END Puta;

PROCEDURE Kolicnik(p1, p2: Polinom; 
                   VAR kol, ost: Polinom; 
                   VAR ok: BOOLEAN);

  PROCEDURE Deli(VAR kol, ost: Polinom);
  VAR
    novi, pomocni: Polinom;
  BEGIN
    IF ost <> NIL THEN
      IF ost^.st >= p2^.st THEN
        NEW(novi);
        novi^.k := - ost^.k / p2^.k;
        novi^.st := ost^.st - p2^.st;
        MonomPuta(p2, novi, pomocni);
        Saberi(ost, pomocni, ost);
        novi^.k := - novi^.k;
        UbaciMonom(novi, kol);
        DISPOSE(novi);
        Deli(kol, ost)
      END
    END
  END Deli;

BEGIN (* Kolicnik *)
  ok := TRUE;
  Anuliraj(kol);
  IF p2 = NIL THEN
    ok := FALSE
  ELSE
    Kopiraj(p1, ost);
    Deli(kol, ost)
  END
END Kolicnik;

PROCEDURE PolinomNaN(p: Polinom; n: CARDINAL;
                     VAR rez: Polinom);
VAR
  i: CARDINAL;
BEGIN
  IF n = 0 THEN
    NEW(rez);
    rez^.k := 1.0;
    rez^.st := 0;
    rez^.veza := NIL;
  ELSIF n = 1 THEN
    Kopiraj( rez, p );
  ELSE
    rez := p;
    FOR i := 2 TO n DO
      Puta(rez, p, rez)
    END
  END;
END PolinomNaN;

PROCEDURE DisposePolinom(VAR p: Polinom);
VAR
  pomocni: Polinom;
BEGIN
  pomocni := p;
  WHILE pomocni # NIL DO
    p := p^.veza;
    DISPOSE(pomocni);
    pomocni := p
  END
END DisposePolinom;

END PolinomL.
\end{lstlisting}


\subsection{Zadatak: Sabiranje sa unapred određenim polinomom}

Želimo da ispišemo uneti polinom uvećan za\\ $x^5 - 3x^4 + 4x + 7$.

\begin{lstlisting}[style=codeblock]
MODULE polinom;
FROM PolinomL IMPORT Polinom, Stampaj, Anuliraj, DisposePolinom, UbaciMonom, Unos, Saberi;
FROM InOut IMPORT WriteString, WriteLn;
FROM Storage IMPORT ALLOCATE, DEALLOCATE;

VAR
  p,q,rez,pom : Polinom;

BEGIN
  (* korisnik unosi prvi polinom *)
  WriteString("Unesite polinom:");
  WriteLn;
  Unos(p);
  (* drugi polinom kreiramo mi, 
     monom po monom *)
  Anuliraj(q); (* isto sto i q:=NIL; *)
  (* formiramo monom x^5 *)
  NEW(pom);
  pom^.st:=5;
  pom^.k:=1.0;
  (* dodajemo ga u polinom *)
  UbaciMonom(pom,q);
  DISPOSE(pom);
  (* -3 x^4 *)
  NEW(pom);
  pom^.st := 4;
  pom^.k := -3.0;
  UbaciMonom(pom,q);
  DISPOSE(pom);
  (* 4 x *)
  NEW(pom);
  pom^.st := 1;
  pom^.k := 4.0;
  UbaciMonom(pom,q);
  DISPOSE(pom);
  (* 7 (x^0) *)
  NEW(pom);
  pom^.st := 0;
  pom^.k := 7.0;
  UbaciMonom(pom,q);
  DISPOSE(pom);
  (* saberemo polinome *)
  Saberi(p, q, rez);
  (* odstampamo rezultat *)
  Stampaj(rez,0);
  WriteLn;
  (* oslobadjanje zauzete memorije *)
  DisposePolinom(p);
  DisposePolinom(q);
  DisposePolinom(rez);
END polinom.
\end{lstlisting}

\subsection{Zadatak: Suma k polinoma}

Napisati program koji ucitava broj k (1<=k<=50) i k polinoma, a nakon
toga izracunava njihovu sumu

\begin{lstlisting}[style=codeblock]
MODULE PolSuma;

FROM PolinomL IMPORT Polinom, Anuliraj, DisposePolinom, Unos, Stampaj, SaberiNa;
FROM InOut IMPORT WriteLn, WriteString, ReadCard, WriteCard;
CONST
  maxk = 50;
TYPE
  nizPol = ARRAY [1..maxk] OF Polinom;
VAR
  i, k: CARDINAL;
  suma : Polinom;
  p : nizPol;
BEGIN
  REPEAT
    WriteString('Unesite broj k (1 <= k <= ');
    WriteCard(maxk, 1);
    WriteString(') ');
    ReadCard(k);
    WriteLn;
  UNTIL (1 <= k) AND (k <= maxk);
  FOR i := 1 TO k DO
    WriteLn;
    WriteString('Unos ');
    WriteCard(i, 1);
    WriteString('. polinoma.');
    WriteLn;
    Unos(p[i])
  END;
  Anuliraj(suma);
  FOR i := 1 TO k DO
    SaberiNa(suma, p[i])
  END;
  WriteLn;
  WriteString('Njihova suma je:');
  WriteLn;
  Stampaj(suma, 4);
  DisposePolinom(suma);
  FOR i := 1 TO k DO
    DisposePolinom(p[i]);
  END;
END PolSuma.
\end{lstlisting}

\section{Stek i red opsluživanja}

\subsection{Zadatak: Ilustracija pisanja u fajl uz pomoć bafera}

\begin{lstlisting}[style=codeblock]
DEFINITION MODULE QueueInfo;
CONST
  Maxqueue = 100;
TYPE
  InfoTip = CHAR;

END QueueInfo.

IMPLEMENTATION MODULE QueueInfo;
END QueueInfo.

DEFINITION MODULE RedOpsl1;
FROM QueueInfo IMPORT InfoTip,Maxqueue;
TYPE 
  Niz = ARRAY[1..Maxqueue] OF InfoTip;
  RedOpslTip = RECORD
        Prvi, Zadnji : CARDINAL;
        Element : Niz
  END;

PROCEDURE MakeNull(VAR q : RedOpslTip);
PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
PROCEDURE First(VAR q : RedOpslTip;
                VAR x : InfoTip;
                VAR ok : BOOLEAN);
PROCEDURE PopFirst(VAR q : RedOpslTip;
                   VAR ok : BOOLEAN);
PROCEDURE AddRear(VAR q : RedOpslTip;
                  x : InfoTip;
                  VAR ok : BOOLEAN);

END RedOpsl1.

IMPLEMENTATION MODULE RedOpsl1;
FROM QueueInfo IMPORT Maxqueue,InfoTip;

PROCEDURE MakeNull(VAR q : RedOpslTip);
BEGIN
  WITH q DO
    Prvi := 0;
    Zadnji := 0
  END
END MakeNull;

PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
BEGIN
  RETURN q.Zadnji = 0
END Empty;


PROCEDURE First(VAR q : RedOpslTip;
                VAR x : InfoTip;
                VAR ok : BOOLEAN);
BEGIN
  IF Empty(q) THEN
    ok := FALSE
  ELSE
    ok := TRUE;
    WITH q DO
      x := Element[Prvi]
    END
  END
END First;

PROCEDURE AddOne(i : CARDINAL) : CARDINAL;
BEGIN
  IF i = Maxqueue THEN
    RETURN 1
  ELSE
    RETURN i+1
  END
END AddOne;

PROCEDURE PopFirst(VAR q : RedOpslTip;
                   VAR ok : BOOLEAN);
BEGIN
  IF Empty(q) THEN
    ok := FALSE
  ELSE
    ok := TRUE;
    WITH q DO
      IF Prvi = Zadnji THEN
        MakeNull(q)
      ELSE
        Prvi := AddOne(Prvi)
      END
    END
  END
END PopFirst;

PROCEDURE AddRear(VAR q : RedOpslTip;
                  x : InfoTip;
                  VAR ok : BOOLEAN);
BEGIN
  WITH q DO
    IF AddOne(Zadnji) = Prvi THEN
      ok := FALSE
    ELSE
      ok := TRUE;
      IF Empty(q) THEN
        Prvi := 1;
        Zadnji := 1
      ELSE
        Zadnji := AddOne(Zadnji)
      END;
      Element[Zadnji] := x
    END
  END
END AddRear;

END RedOpsl1.

MODULE Bafer;
FROM RedOpsl1 IMPORT RedOpslTip, MakeNull, Empty, First, PopFirst, AddRear;
FROM FIO IMPORT File,WrChar, Create, Close;
IMPORT IO;

CONST
  ImeIzlaza = 'izlaz.txt';

VAR
  izlaz : File;
  znak : CHAR;
  buffer : RedOpslTip;

PROCEDURE IsprazniBafer(VAR dat : File;
                        VAR buf : RedOpslTip);
VAR
  znak : CHAR;
  ok : BOOLEAN;
BEGIN
  WHILE NOT Empty(buf) DO
    First(buf, znak, ok);
    PopFirst(buf, ok);
    WrChar(dat, znak)
  END
END IsprazniBafer;

PROCEDURE BaferWrite(VAR dat : File;
                     VAR buf : RedOpslTip;
                     znak : CHAR);
VAR
  ok : BOOLEAN;
BEGIN
  AddRear(buf, znak, ok);
  IF NOT ok THEN
    IsprazniBafer(dat, buf);
    AddRear(buf, znak, ok)
  END
END BaferWrite;

BEGIN
  izlaz := Create(ImeIzlaza);
  MakeNull(buffer);
  IO.WrStr('Unesite tekst, koji treba da se unese u datoteku ');
  IO.WrStr(ImeIzlaza);
  IO.WrChar('.');
  IO.WrLn;
  IO.WrStr('Unos zavrsite tackom.');
  IO.WrLn;
  znak := IO.RdChar();
  WHILE znak # '.' DO
    BaferWrite(izlaz, buffer, znak);
    znak := IO.RdChar();
  END;
  IsprazniBafer(izlaz, buffer);
  Close(izlaz)
END Bafer.
\end{lstlisting}

\subsection%
{Zadatak: Ispitivanje da li reč pripada gramatici wcw$^+$}

Reč pripada ovoj gramatici ako joj se prvi deo (w) sastoji samo od
slova 'a' i 'b', sledi slovo 'c' a nakon njega obrnuta reč reči w.

\begin{lstlisting}[style=codeblock]
DEFINITION MODULE Stek;
CONST
  Maxstack = 100;
TYPE
  Niz = ARRAY [1..Maxstack] OF CHAR;
  StekTip = RECORD
            Top : CARDINAL;
            Element : Niz
          END;
PROCEDURE MakeNull(VAR s : StekTip);
PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;

PROCEDURE Top(VAR s : StekTip;
              VAR x : CHAR;
              VAR ok : BOOLEAN);
PROCEDURE Pop(VAR s : StekTip;
              VAR ok : BOOLEAN);
PROCEDURE Push(VAR s : StekTip;
               x : CHAR;
               VAR ok : BOOLEAN);
END Stek.


IMPLEMENTATION MODULE Stek;

PROCEDURE MakeNull(VAR s : StekTip);
BEGIN
  s.Top := 0
END MakeNull;

PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
BEGIN
  RETURN s.Top = 0
END Empty;

PROCEDURE Top(VAR s : StekTip;
              VAR x : CHAR;
              VAR ok : BOOLEAN);
BEGIN
  IF Empty(s) THEN
    ok := FALSE
  ELSE
    ok := TRUE;
    WITH s DO
      x := Element[Top]
    END
  END
END Top;

PROCEDURE Pop(VAR s : StekTip;
              VAR ok : BOOLEAN);
BEGIN
  IF Empty(s) THEN
    ok := FALSE
  ELSE
    ok := TRUE;
    DEC(s.Top)
  END
END Pop;

PROCEDURE Push(VAR s : StekTip;
               x : CHAR;
               VAR ok : BOOLEAN);
BEGIN
  WITH s DO
    IF Top = Maxstack THEN
      ok := FALSE
    ELSE
      ok := TRUE;
      INC(Top);
      Element[Top] := x
    END
  END
END Push;
END Stek.

MODULE wcw;
(* Da li rec pripada gramatici wcw+. *)
FROM Stek IMPORT StekTip, MakeNull, Empty,
                 Top, Pop, Push;
FROM InOut IMPORT Read, Write, WriteString, EOL;
TYPE
  slova = SET OF CHAR;
VAR
  S : StekTip;
  Ch, C : CHAR;
  ok : BOOLEAN;
BEGIN
  MakeNull(S);
  Read(Ch);
  ok := TRUE;
  WHILE ok AND (Ch IN slova{'a', 'b'}) DO
    Push(S, Ch, ok);
    Read(Ch);
  END;
  IF NOT ok THEN
    WriteString('Greska - mali stek')
  ELSIF Ch # 'c' THEN
    WriteString('Pogresan string')
  ELSE
    Read(Ch);
    WHILE ok AND (Ch # EOL) DO
      Top(S, C, ok);
      ok := ok AND (C = Ch);
      IF ok THEN
        Pop(S, ok);
        Read(Ch);
      END
    END;
    IF NOT (ok AND Empty(S)) THEN
      WriteString('Pogresan string')
    ELSE
      WriteString('String pripada jeziku L')
    END
  END
END wcw.
\end{lstlisting}

\subsection{Zadatak: Kalkulator za izračunavanje postfiksnih izraza}


Napraviti kalkulator za izračunavanje postfiksnih izraza. Svi brojevi
koji figurišu u izrazu su jednocifreni.

\begin{lstlisting}[style=codeblock]
MODULE PostFix;

FROM StekI IMPORT StekTip, MakeNull, Empty, Top, Pop, Push;
FROM InOut IMPORT Read, Write, WriteInt, EOL;
TYPE
  slova = SET OF CHAR;
VAR
  S : StekTip;
  Ch : CHAR;
  Op1, Op2 : INTEGER;
  ok : BOOLEAN;
PROCEDURE Conv(Ch : CHAR) : INTEGER;
BEGIN
  RETURN  ORD(Ch) - ORD('0') 
END Conv;

BEGIN
  MakeNull(S);
  Read(Ch);
  WHILE Ch # EOL DO
    IF Ch IN slova{'+', '-', '/', '*', '%'} THEN
      Top(S, Op2, ok);
      Pop(S, ok);
      Top(S, Op1, ok);
      Pop(S, ok);
      CASE Ch OF
        '+' : Op1 := Op1 + Op2 |
        '-' : Op1 := Op1 - Op2 |
        '*' : Op1 := Op1 * Op2 |
        '/' : Op1 := Op1 DIV Op2 |
        '%' : Op1 := Op1 MOD Op2
      END;
      Push(S, Op1, ok)
    ELSE
      Push(S, Conv(Ch), ok)
    END;
    Read(Ch);
  END;
  Top(S, Op1, ok);
  Write('=');
  WriteInt(Op1,5)
END PostFix.
\end{lstlisting}


\section{Simulacija rekurzije}


Na početku označiti sve rekurzivne pozive u originalnoj proceduri
adresama (npr. 1,2,3... ili konstante nabrojivog tipa podataka).  

Na steku se čuvaju lokalne promenljive, parametri procedure i adresa
mesta poziva, a u skladu sa tim se kreira InfoTip.

Trivijalnim pozivom se smatra onaj koji se izračunava bez dodatnih
rekurzivnih poziva.  

U kodu ispod, \kod{treba\_rekurzija} znači da je poziv netrivijalan,
odnosno treba naći uslove pod kojima se sigurno dešavaju rekurzivni
pozivi.

\begin{lstlisting}
MakeNull(S);
REPEAT
  WHILE treba_rekurzija DO
    -prepisati sve od pocetka originalne 
     procedure do prvog rekurzivnog poziva
    -staviti na stek potrebne
     lokalne promenljive, parametre procedure i
     adresu mesta poziva
    -podesiti vrednosti parametara da budu
     kao u rekurzivnom pozivu procedure
  END;
  trivijalan poziv
  umesto RETURN x pisati rez := x 
  jos := TRUE;
  WHILE jos AND NOT Empty(S) DO
    Top(S, el, ok);
    Pop(S, ok);
    -restauriramo vrednosti sa steka
    -u zavisnosti od adrese poziva nastavimo
     prepisivanje originalne procedure sa 
     tog mesta
    -ako se dodje do novog rek. poziva tada: 
       -sacuvati na steku vrednosti
       -podesiti vrednosti parametara da budu 
        kao u rekurzivnom pozivu procedure
       -ici na pocetak koda 
        (ovo se postize sa jos := FALSE)
    -inace
       ako se naidje na RETURN x pisati rez := x
  END
UNTIL Empty(S);
\end{lstlisting}

Ako je procedura funkcijska tada se na kraj dodaje \kod{RETURN rez}.

\subsection*{ZADACI}

Simulirati ponašanje sledećih rekurzivnih procedura (funkcija) upotrebom steka:

\subsection{Primer 1 -- faktorijel}


\begin{lstlisting}[style=codeblock]
MODULE Fakto;
(* InfoTip = CARDINAL; *)

FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
FROM StekC IMPORT StekTip, MakeNull, Empty,
                  Top, Pop, Push;
VAR
  n : CARDINAL;
PROCEDURE RFakto(n : CARDINAL) : CARDINAL;
BEGIN
  IF n <= 1 THEN
    RETURN 1
  ELSE
    RETURN n * RFakto(n-1)
  END
END RFakto;


PROCEDURE SFakto(n : CARDINAL) : CARDINAL;
VAR
  s : StekTip;
  rez : CARDINAL;
  OK : BOOLEAN;
BEGIN
  MakeNull(s);
  WHILE n > 1 DO
    Push(s,n,OK);
    DEC(n)
  END;
  rez := 1;
  WHILE NOT Empty(s) DO
    Top(s, n, OK);
    Pop(s, OK);
    rez := n * rez
  END;
  RETURN rez
END SFakto;

BEGIN
  WrStr('n = ');
  n := RdCard();
  WrLn
  WrStr('n! = ');
  WrCard(RFakto(n), 1);
  WrStr(' = ');
  WrCard(SFakto(n), 1)
END Fakto.
\end{lstlisting}

\subsection{Primer 2 -- stepenovanje}

\begin{lstlisting}[style=codeblock]
MODULE Step;
(* InfoTip = RECORD
                x : REAL;
                n : CARDINAL;
                adr : (par, nepar)
             END;
*)

FROM IO IMPORT WrStr, WrLn, WrReal,
        RdReal, RdCard;
FROM StekStep IMPORT StekTip, MakeNull, Empty,
             Top, Pop, Push, InfoTip, AdrTip;

VAR
  n : CARDINAL;
  x : REAL;

PROCEDURE Sqr(y : REAL) : REAL;
BEGIN
  RETURN y * y
END Sqr;

PROCEDURE RStep(x : REAL;
                n : CARDINAL) : REAL;
BEGIN
  IF n = 0 THEN
    RETURN 1.
  ELSIF ODD(n) THEN
    RETURN x * Sqr( RStep(x, n DIV 2) )
  ELSE
    RETURN Sqr( RStep(x, n DIV 2) )
  END
END RStep;

PROCEDURE SStep(x : REAL;
                n : CARDINAL ) : REAL;
VAR
  s : StekTip;
  OK : BOOLEAN;
  rez : REAL;
  el : InfoTip;
BEGIN
  MakeNull(s);
  WHILE n > 0 DO
    el.x := x;
    el.n := n;
    IF ODD(n) THEN
      el.adr := nepar;
    ELSE
      el.adr := par
    END;
    Push(s,el,OK);
    n := n DIV 2
  END;
  rez := 1.;
  WHILE NOT Empty(s) DO
    Top(s, el, OK);
    Pop(s, OK);
    x := el.x;
    n := el.n;
    IF el.adr = nepar THEN
      rez := x * Sqr(rez)
    ELSE
      rez := Sqr(rez)
    END
  END;
  RETURN rez
END SStep;

BEGIN
  WrStr('x =? ');
  x := RdReal();
  WrLn;
  WrStr('n =? ');
  n := RdCard();
  WrStr('x^n = ');
  WrReal(RStep(x, n), 10, 1);
  WrStr(' = ');
  WrReal(SStep(x, n), 10, 1)
END Step.
\end{lstlisting}

\subsection{Primer 3 -- Fibonači}

\begin{lstlisting}[style=codeblock]
MODULE Fib;
(* InfoTip = RECORD
                n : CARDINAL;
                PrviSab : CARDINAL;
                adr : (prvi, drugi)
             END;
*)

FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
FROM StekFib IMPORT StekTip, MakeNull, Empty,
       Top, Pop, Push, InfoTip, AdrTip;
VAR
  n : CARDINAL;

PROCEDURE RFib(n : CARDINAL) : CARDINAL;
BEGIN
  IF n <= 1 THEN
    RETURN n
  ELSE
    RETURN RFib(n-1) + RFib(n-2)
  END
END RFib;

PROCEDURE SFib(n : CARDINAL ) : CARDINAL;
VAR
  s : StekTip;
  OK, jos : BOOLEAN;
  rez, PrviSab : CARDINAL;
  el : InfoTip;
BEGIN
  MakeNull(s);
  REPEAT
    WHILE n > 1 DO
      el.n := n;
      el.adr := prvi;
      Push(s,el,OK);
      DEC(n)
    END;
    rez := (n);
    jos := TRUE;
    WHILE (NOT Empty(s)) AND jos DO
      Top(s, el, OK);
      Pop(s, OK);
      n := el.n;
      IF el.adr = prvi THEN
        PrviSab := rez;
        el.n := n;
        el.adr := drugi;
        el.PrviSab := PrviSab;
        Push(s, el, OK);
        DEC(n, 2);
        jos := FALSE
      ELSE
        PrviSab := el.PrviSab;
        rez := PrviSab + rez
      END
    END
  UNTIL Empty(s);
  RETURN rez
END SFib;

BEGIN
  WrStr('n =? ');
  n := RdCard();
  WrStr('F(n) = ');
  WrCard(RFib(n), 1);
  WrStr(' = ');
  WrCard(SFib(n), 1)
END Fib.
\end{lstlisting}

\subsection{Primer 4 -- faktorijel 2}


\begin{lstlisting}[style=codeblock]
MODULE Faktor;
(* InfoTip = CARDINAL; *)
FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
FROM StekC IMPORT StekTip, MakeNull, Empty,
                  Top, Pop, Push;

VAR
  n,rez : CARDINAL;

PROCEDURE RFakto(n : CARDINAL;
                 VAR rez : CARDINAL);
BEGIN
  IF n = 0 THEN
    rez := 1
  ELSE
    RFakto(n-1, rez);
    rez := n * rez
  END
END RFakto;

PROCEDURE SFakto(n : CARDINAL;
                 VAR rez : CARDINAL);
VAR
  s : StekTip;
  OK : BOOLEAN;
BEGIN
  MakeNull(s);
  WHILE n > 0 DO
    Push(s,n,OK);
    DEC(n)
  END;
  rez := 1;
  WHILE NOT Empty(s) DO
    Top(s, n, OK);
    Pop(s, OK);
    rez := n * rez
  END
END SFakto;

BEGIN
  WrStr('n =? ');
  n := RdCard();
  WrLn;
  WrStr('n! = ');
  RFakto(n, rez);
  WrCard(rez, 1);
  WrStr(' = ');
  SFakto(n, rez);
  WrCard(rez, 1)
END Faktor.
\end{lstlisting}

\subsection{Primer 5 (ispitni)}


\begin{lstlisting}[style=codeblock]
MODULE Rek1;
(* InfoTip = RECORD
                d, g, m1, m2 : INTEGER; 
                adr : (prvi, drugi)
             END;
*)
FROM Stek1 IMPORT StekTip, adresa, InfoTip,
         MakeNull, Empty, Top, Pop, Push;
IMPORT IO;
VAR
  X : ARRAY [1..20] OF INTEGER;

PROCEDURE Max(d, g: INTEGER) : INTEGER;
VAR
  m1, m2 : INTEGER;
BEGIN
  IF d>g THEN
    RETURN MIN(INTEGER)
  ELSIF d=g THEN
    RETURN X[d]
  ELSE
    m1 := Max(d, (d+g) DIV 2);
    m2 := Max((d+g) DIV 2 +1, g);
    IF m1 > m2 THEN
      RETURN m1
    ELSE
      RETURN m2
    END
  END
END Max;

PROCEDURE SMax(d, g: INTEGER) : INTEGER;
VAR
  S : StekTip;
  el : InfoTip;
  ok, jos : BOOLEAN;
  m1, m2, rez : INTEGER;
BEGIN
  MakeNull(S);
  REPEAT
    WHILE d<g DO
      el.d := d;
      el.g := g;
      el.adr := prvi;
      Push(S, el, ok);
      g := (d+g) DIV 2
    END;
    IF d>g THEN
      rez := MIN(INTEGER)
    ELSE (* d=g *)
      rez := X[d]
    END;
    jos := TRUE;
    WHILE jos AND NOT Empty(S) DO
      Top(S, el, ok);
      Pop(S, ok);
      d := el.d;
      g := el.g;
      m1 := el.m1;
      IF el.adr = prvi THEN
        m1 := rez;
        el.m1 := m1;
        el.adr := drugi;
        Push(S, el, ok);
        d := (d+g) DIV 2 + 1;
        jos := FALSE
      ELSE (*el.adr = drugi*)
        m2 := rez;
        IF m1 > m2 THEN
          rez := m1
        ELSE
          rez := m2
        END
      END
    END
  UNTIL Empty(S);
  RETURN rez
END SMax;

BEGIN (* glavni program *)
  X[1] := 3;
  X[2] := 2;
  X[3] := 5;
  X[4] := -7;
  X[5] := 0;
  IO.WrCard(Max(1, 5), 3);
  IO.WrLn;
  IO.WrCard(SMax(1, 5), 3);
  IO.WrLn
END Rek1.
\end{lstlisting}

\subsection{Primer 6 (ispitni)}


\begin{lstlisting}[style=codeblock]
MODULE Rek2;
(* InfoTip = RECORD
                x, y, n : CARDINAL; 
                adr : (prvi, drugi, treci, cetvrti)
             END;
*)
FROM Stek2 IMPORT StekTip, adresa, InfoTip, 
           MakeNull, Empty, Top, Pop, Push;
IMPORT IO;

PROCEDURE g(x : CARDINAL; y : CARDINAL;
            n : CARDINAL) : CARDINAL;
BEGIN
  IF n < 3 THEN
    RETURN x + y
  ELSIF ODD(n) THEN
    RETURN g(g(x+1, y, n-2), y, n-3)
  ELSE
    RETURN g(x, g(x, y+1, n-2), n-3)
  END
END g;

PROCEDURE Sg(x : CARDINAL; y : CARDINAL;
             n : CARDINAL) : CARDINAL;
VAR
  S : StekTip;
  el : InfoTip;
  ok, jos : BOOLEAN;
  rez : CARDINAL;
BEGIN
  MakeNull(S);
  REPEAT
    WHILE n >= 3 DO
      IF ODD(n) THEN
        el.x := x;
        el.y := y;
        el.n := n;
        el.adr := prvi;
        Push(S, el, ok);
        INC(x);
        DEC(n, 2)
      ELSE
        el.x := x;
        el.y := y;
        el.n := n;
        el.adr := treci;
        Push(S, el, ok);
        INC(y);
        DEC(n, 2)
      END
    END;
    rez := x+y;
    jos := TRUE;
    WHILE jos AND NOT Empty(S) DO
      Top(S, el, ok);
      Pop(S, ok);
      x := el.x;
      y := el.y;
      n := el.n;
      IF el.adr = prvi THEN
        el.adr := drugi;
        Push(S, el, ok);
        x := rez;
        DEC(n, 3);
        jos := FALSE
      ELSIF el.adr = treci THEN
        el.adr := cetvrti;
        Push(S, el, ok);
        y := rez;
        DEC(n, 3);
        jos := FALSE
      END
    END
  UNTIL Empty(S);
  RETURN rez
END Sg;

BEGIN (* glavni program *)
  IO.WrCard(g(2, 3, 10), 3);
  IO.WrCard(Sg(2, 3, 10), 3);
END Rek2.
\end{lstlisting}

%\columnbreak

\appendix

\section{Native XDS Modula 2 -- kratko uputstvo}


Ovo uputstvo ukratko pokriva kako se može nabaviti XDS Modula 2 za Windows
sistem, njenu instalaciju, te kako napraviti i pokretnuti jednostavan program.

\subsection*{Dobavljanje instalacije}


Native XDS Modula 2 se može besplatno skinuti sa sajta proizvođača,
\url{http://www.excelsior-usa.com/}, tačnije na adresi:

\url{http://www.excelsior-usa.com/xdsdl.html}

Prvo se prikazuje ugovor o korišćenju koji na dnu treba potvrditi da ste
razumeli i da ćete ga se pridržavati.

Na stranici koja se potom otvara je potrebno odabrati sledeće pakete za
download:

* Native XDS-x86 2.51 for Windows (6.5MB)
\url{http://www.excelsior-usa.com/download/xds25x/xds-x86-251-enduser-win32.exe}

* TSCP add-on (2.4MB)
\url{http://www.excelsior-usa.com/download/xds25x/tscp-x86-251-enduser-win32.exe}

\subsection*{Instalacija okruženja}

Prvo treba instalirati osnovno okruženje (xds-x86...), a potom i Top
Speed Compatibility Pack (tscp-x86...), koji je potreban za neke
module koji se koriste.

\emph{Korisnicima Windows-a 7 preporučujemo da pokrenu instalacione
  pakete pomoću opcije ``Run as administrator'' do koje se stiže desnim
  klikom miša.}

Pretpostavićemo u daljem tekstu da je program instaliran u
\kod{C:/XDS/}

\subsection*{Pokretanje okruženja}

Po uspešnoj instalaciji bi trebalo da postoji ikonica na desktopu, kao
i grupa sa programom u start meniju.

Ukoliko iz bilo kakvog razloga ne postoje odgovarajuće prečice,
okruženje se može pokrenuti uz pomoć izvršnog fajla
\kod{C:/XDS/BIN/xds.exe} (ako je instalirano na podrazumevanoj
lokaciji).

\subsection*{Prvi projekat}

Da bismo mogli da pišemo i pokrećemo svoj program, potrebno je prvo
napraviti projekat za njega, što se radi na sledeći način:

\begin{itemize}

\item 
 Iz menija se odabere Project->New.
\item U dijalogu se klikne na gornje dugme ``Browse'', odabere se putanja gde
  će se kreirati projekat i ukuca se ime novog projekta.

\item U drugom polju ``Template'' ne treba da piše ništa. Ukoliko
  postoji neki tekst, obrisati ga.

\item Kliknuti na ``OK''

\item Iskočiće dijalog na kome piše da ne postoji fajl za editovanje,
  kliknuti na ``OK'' da se on napravi.

\item Pojavljuje se forma za kucanje programa, ukucati (na primer):

\begin{minipage}{\columnwidth}
\begin{lstlisting}[style=codeblock]
  MODULE Hello;
  FROM InOut IMPORT WriteString,WriteLn;
  BEGIN
    WriteString("Hello World");
    WriteLn;
  END Hello.
\end{lstlisting} 
\end{minipage}

\item Program se može pokrenuti na različite načine, pri čemu se
  automatski prevodi:

  \begin{itemize}

  \item Klik na ``Run'' ikonicu u toolbaru (plavi čovečuljak koji trči)

  \item Meni Debug->Run

  \item Prečica Ctrl+F9 na tastaturi

  \end{itemize}

\item Ako je sve u redu sa programom, treba da se pojavi novi terminal
  u kome se ispisuje rezultat izvršavanja programa, u našem slučaju
  jednostavna pozdravna poruka.
\end{itemize}  

Naravno moguće je i samo prevesti (kompajlirati) program, tako da se
samo prikažu greške (ako ih ima) i bez pokretanja programa:
\begin{itemize}
\item Klik na ``Compile'' ikonicu u toolbaru
\item Meni Tools->Compile
\item Prečica F9 na tastaturi
\end{itemize}

Ukoliko u programu postoje greške, on neće biti pokrenut, već će se
dobiti lista grešaka u donjem delu prozora. Na primer ako obrišemo ``S''
u četvrtom redu i probamo da pokrenemo program, taj red će biti
označen svetlo plavom bojom i dobićemo poruku:
 
\kod{- Error in pro1.mod [4:5]: Undeclared identifier "Writeting"}

Što znači da u četvrtom redu, kod petog karatkera postoji problem, da
identifikator nije deklarisan, što najčešće znači da ga nismo uvezli,
ili, kao u našem slučaju, da smo napravili grešku u kucanju.

Stvar na koju isto treba obratiti pažnju je da se nekad greška
prijavljue nešto kasnije u tekstu nego što je napravljena. Na primer,
ako obrišemo ``;'' na kraju četvrtog reda i probamo da pokrenemo
program, peti red će biti označen svetlo plavom bojom i dobićemo
poruku:

\kod{- Error in pro1.mod [5:5]: Expected symbol ";" }

Ovo se desilo jer nedostaje tačka zarez na kraju četvrtog reda, ali će
kompajler probati da je traži i dalje, pa će tek na početku petog reda
prijaviti grešku.

U spisku se takođe pojavljuje i upozorenje (Warning) o tome da se
uvezena komanda WriteString ne koristi nigde u programu. Često se
upozorenja mogu ignorisati, a pažnju uglavnom treba obraćati na
greške, odnosno poruke koje počinju sa ``Error''.

Takođe se često dešava da su druge prijavljene greške posledica prve,
te je poželjno ponovo kompajlirati (ili pokretati) program posle svake
ispravljene greške.

\paragraph{Napomena o template-ovima pri kreiranju projekta:} 
Moguće je namestiti da u dijalogu za novi projekat drugo polje ``Template''
 uvek bude prazno. Potrebno je u tom istom dijalogu kliknuti na
 ``Configure'', a potom isprazniti polje ``default template''.
\end{multicols}

\end{document}
