% skripta-spa1-sadrzaj.tex
% Skripta za predmet Strukture podataka i algoritmi 1, DMI, PMF, NS
% ovaj fajl sadrzi glavni sadrzaj skripte koji se ukljucuje u jedan
% od pomocnih fajlova koji ce primeniti adekvatna formatiranja,
% npr za jednu ili dve kolone

% 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}{Februar 2014, Novi Sad}
\newcommand{\verzija}{ver 14a-\varijacija}
%varijacija je definisana u fajlu koji ukljucuje ovaj

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

%change the default font
\usepackage{lmodern}
\usepackage{beramono}
\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}

\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}
}

%% 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{15ex}
	
        {\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\ttfamily,
        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

\vfill

Programi u ovoj skripti su testirani sa kompajlerom 'Native XDS Modula
2'. Za verzije pre 2.60 je neophodno dodatno instalirati i TSCP (Top
Speed Compatibility Pack), pošto je potreban za neke od modula koji se
ne nalaze u ISO standardu Module 2. U novijim verzijama su i ovi
moduli uključeni u standardnu instalaciju.

Sav sadržaj se može koristiti u skladu sa {\ttfamily CC-BY-NC-SA} licencom. \\
\url{http://creativecommons.org/licenses/by-nc-sa/3.0/}

\newpage

\tableofcontents

\mainstart

\sectionbreak

\section{Ilustracija efikasnosti algoritma}

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

Pitagorina trojka su tri broja $a,b,c$ za koje važi $a^2 + b^2 = c^2\\$

\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}

Sledeći primer koristi Euklidovu teoremu i malo drugačiji pristup.
Ako uzmemo neka dva prirodna broja $m$ i $n$, tada se iz njih može
izvesti jedna Pitagorina trojka koja lako zadovoljava potrebne uslove:
\[
\begin{array}{l}
a = 2mn\\
b = m^2 - n^2\\
c = m^2 + n^2
\end{array}
\]
Odnosno kad probamo da proverimo da li je ovo
Pitagorina trojka dobijamo:
\[
\begin{array}{r@=l}
a^2 + b^2 & c^2\\
(2mn)^2 + (m^2 - n^2)^2 & (m^2 + n^2)^2
\end{array}
\]

\manbreakJK
\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}

Sledeća dva metoda traže trojke sa nekim specifičnim osobinama.

\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}

\sectionbreak
\section{Stringovi}


Stringovi -- odnosno nizovi znakova -- ne postoje kao ugrađeni tip u
jeziku Modula 2. Ovo daje slobodu da se niz znakova definiše na dužinu
najadekvatniju za konkretnu primenu. U opštem slučaju definišemo npr:
\begin{codeblock}
  TYPE
     String = ARRAY [1..30] OF CHAR;
\end{codeblock}

Budući da Modula 2 definiše mogućnost korišćenja \emph{otvorenih
  nizova}, lako je moguće definisati procedure koje kao parametre
primaju bilo koji tip koji je definisan kao niz znakova.

\begin{codeblock}
   PROCEDURE ObradaStringa(str: ARRAY OF CHAR);
\end{codeblock}

Konkretne promenljive u programu moraju biti definisane dužine.

Operacije nad stringovima se najčešće uvoze iz modula \kod{Str} i one
su sve definisane da prihvataju \emph{otvorene nizove znakova} kao što
je malopre objašnjeno.

Određivanje stvarne dužine stringa (tj koliko od maksimalnog
kapaciteta niza je zapravo zauzeto sadržajem) se može izvesti na
sledeći način:
\begin{codeblock}
     duzina := Length(str)
\end{codeblock}
    
Leksikografsko poređenje dva stringa se ne može vršiti standardnim
operatorima kao što su \kod{< > =}. Ovo je delom zato što se radi o
nizovima, ali značajnije i zato što se ne vidi direktno koji deo niza
je popunjen ``stvarnim'' sadržajem. Za ovo se koristi komanda
\kod{Compare}, koja prihvata dva stringa kao parametre, a vraća broj
koji predstavlja njihov odnos. Taj broj će biti 0 ako su stringovi
jednaki, veći od nule ako je prvi string ``veći'', i manji od nule ako
je prvi string ``manji''.

\begin{codeblock}
  IF    Compare(str1, str2) > 0 THEN
     WriteString("Prvi string je veci");
  ELSIF Compare(str1, str2) < 0 THEN
     WriteString("Prvi string je manji");
  ELSE (* moraju biti jednaki *)
     WriteString("Jednaki su");
  END;
\end{codeblock}

Ovo se lako pamti kad primetimo da je odnos između \kod{Compare} i 0
isti kao i između prvog i drugog stringa.

Postoji i modul \kod{Strings} koji ima nešto drugačije definisane
procedure, no na njih se sada nećemo fokusirati.

\sectionbreak
\section{Rad sa fajlovima}

\subsection{Modul FIO}

U ovom modulu je definisan tip \kod{File}, koji predstavlja jedan fajl
sa kojim radimo. Da bi ga koristili moramo ga uvesti u program (isto
kao što uvozimo i komande).

\emph{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}, odnosno za ispis će biti zauzeto bar ``n'' znakova.}


Ako otvaramo već postojeći fajl, poželjno je prvo proveriti da li on
postoji -- u suprotnom naš program će se srušiti pri izvršavanju.
Funkcija \kod{Exists(str)} vraća da li fajl postoji.

Promenljiva tipa \kod{File} se mora vezati za neki fajl
jednom od sledećih komandi:
\begin{itemize}
\item \kod{f := Open(str);} -- otvara se postojeci fajl za čitanje
\item \kod{f := Create(str);} -- kreira se fajl za pisanje; ako je već
  postojao, biće zamenjen
\item \kod{f := Append(str);} -- otvara se postojeći fajl za
  dopisivanje na kraj
\end{itemize}

Po završetku rada fajl se mora zatvoriti, u našem primeru to bi bilo:
\begin{itemize}
\item \kod{Close(f);}
\end{itemize}

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

Bitno je obratiti pažnju na specifičnost da postoje dve komande za
čitanje stringova iz fajla i da se one ponašaju različito.  Budući da
razmak spada u separatore to znači da se korišćenjem \kod{RdItem} ne
može učitati string koji ima u sebi razmake.

Analogne su i procedure za pisanje različitih tipova u fajl:
\begin{itemize}
\item \kod{WrStr(f,str);}
\item \kod{WrInt(f,i,n);}
\item \kod{WrCard(f,c,n);}
\item \kod{WrChar(f,ch);}
\end{itemize}

Treba primetiti da ne postoje dve komande za ispis stringa u fajl --
potpuno je svejedno da li on ima razmake u sebi ili ne.

Prelom reda se eksplicitno upisuje u fajl komandom
\begin{itemize}
\item \kod{WrLn(f);}.
\end{itemize}


Da bi odredili da li smo stigli do kraja fajla možemo koristiti
\kod{EOF}. U pitanju je logička promenljiva koja se uvozi iz modula
FIO kao bilo kakva normalna komanda. Ona 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}, pa na ovo treba obratiti pažnju pri
radu.

\subsubsection*{Mogući problemi}

U ovoj glavi će biti navedeni neki česti problemi koji se mogu desiti
pri korišćenju FIO modula, a koji su vezani za konkretnu
implementaciju u XDS distribuciji kompajlera.

\paragraph{\kod{RdStr} i drugi pozivi} Prilikom čitanja iz fajlova
može doći do neobičnih rezultata ako se kombinuju pozivi \kod{RdStr}
sa drugima. Problem je u različitom tretiranju separatora. Komanda
\kod{RdStr} uvek čita do kraja reda i pri tome premesti poziciju za
čitanje odmah iza znaka za razdvajanje redova. Ostale komande prvo
preskaču separatore i čitaju sadržaj dok ne naiđu na novi separator
(što može biti novi red, a može biti i razmak, tabulator i neki drugi
znaci) i staju sa čitanjem \emph{pre} tog separatora. Kombinaovanje
ova dva pristupa može dovesti do toga da \kod{RdStr} nakon neke druge
komande učita samo kraj trenutnog reda, a ne sledeći red kao što bi
bilo očekivano.

\paragraph{EOF i prazan red na kraju fajla} Svako čitanje iz fajla
postavlja \kod{EOF} u skladu sa tim da li je komanda stigla do kraja
fajla ili ne. Nažalost kod svih komandi za čitanje (osim \kod{RdStr})
postoji problem ukoliko je na kraju prazan red ili neki dodatni
separator. Tada učitavanje poslednjeg elementa nije zapravo došlo do
kraja fajla. Ako se nakon toga proba još jedno učitavanje sa takvom
komandom ona će probati da preskoči separator i da učita neki sadržaj,
ali će se zaglaviti jer ne može da ga nađe. Ovo ponašanje je greška u
implementaciji FIO modula u okviru XDS distribucije.


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

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

\lstinputlisting[style=codeblock]{kodovi/fajlovi/ispis.mod}

\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.

\lstinputlisting[style=codeblock]{kodovi/fajlovi/nizslog.MOD}

\sectionbreak
\section{Liste i pokazivači}

Za rad sa pokazivačima je potrebno iz modula \kod{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 IzbaciIzListeSve(VAR lista:brojevi; 
                        br: CARDINAL):CARDINAL;
(* izbacuje sve brojeve 'br' iz liste, naravno ako 
   postoje i vraca koliko ih je bilo *)
VAR
  temp,prethodni:brojevi;
  brojac : CARDINAL;
BEGIN
  brojac := 0;
  (* uklanjamo sa pocetka koliko je potrebno *)
  WHILE (lista # NIL) AND (lista^.info = br) DO
    temp:=lista;
    lista :=lista^.veza;
    DISPOSE(temp);
    INC(brojac);
  END;
  (* trazimo u ostatku liste *)
  IF (lista # NIL) THEN
    temp:=lista;
    WHILE (temp^.veza # NIL)  DO
        (* idemo do poslednjeg elementa liste *)
        prethodni:=temp;
        temp := temp^.veza;
        IF temp^.info = br THEN
          (* prevezemo listu oko elementa *)
          prethodni^.veza:=temp^.veza;
          DISPOSE(temp);
          INC(brojac);
          (* vracamo se jedan korak da bi 
          u novom krugu proverili i ovaj element *)
          temp := prethodni;
        END;
    END;
  END;
  RETURN brojac;
END IzbaciIzListeSve;

(* - 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 IzbacivanjeElSvi(VAR lista:brojevi);
(* izbacuje sve primeke unetog broj iz liste 
   koristeci proceduru IzbaciIzListeSve *)
VAR
  br, ukupno:CARDINAL;
BEGIN
  WriteString("unesite broj za izbacivanje: ");
  ReadCard(br);
  ukupno := IzbaciIzListeSve(lista,br);
  WriteString("Iz liste je izbaceno ");
  WriteCard(ukupno,3);
  WriteString(" el.");
  WriteLn;
END IzbacivanjeElSvi;

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("v - izbacivanje svih 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','V',
                           'M','K','P','Q'};
      IF menu#'Q' THEN
        CASE menu OF
         'S' : Stampaj(lista);|
         'U' : Unos(lista);|
         'I' : IzbacivanjeEl(lista);|
         'V' : IzbacivanjeElSvi(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 učitavati po dva broja koji opisuju osobu (visina i
težina) i smeštati ih u povezane listu, tako da postoji neopadajuće
uređenje i po visini i po težini.

\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}

\sectionbreak
\section{Polinomi preko listi}

\subsection{Moduli}

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

\paragraph{PolinomL.DEF} \ 

\lstinputlisting[style=codeblock]{kodovi/polinomi/POLINOML.DEF}

\paragraph{PolinomL.MOD} \ 

\lstinputlisting[style=codeblock]{kodovi/polinomi/POLINOML.MOD}

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

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

\lstinputlisting[style=codeblock]{kodovi/polinomi/polinom.MOD}

\subsection{Zadatak: Suma k polinoma}

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

\lstinputlisting[style=codeblock]{kodovi/polinomi/PolSuma.MOD}

\sectionbreak
\section{Stek i red opsluživanja}

\subsection{Primer: osnovno korišćenje steka i reda opsluživanja}

\lstinputlisting[style=codeblock]{kodovi/stek-redopsl/stekred.mod}

\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;
\end{lstlisting}

\begin{codeblock}
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{codeblock}

\manbreakJK

\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}

\sectionbreak
\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

\sectionbreak
\pagenumbering{Roman}
\input{xds-uputstvo}

\mainend



%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "skripta-spa1-jk"
%%% End: 
