gitweb on Svarog
projekti pod git sistemom za održavanje verzija -- projects under the git version control system--- a/skripta-spa1-sadrzaj.tex
+++ b/skripta-spa1-sadrzaj.tex
\newcommand{\autor}{Vladimir Kurbalija, Milos Radovanovic, Doni Pracner}
\newcommand{\naslov}{Skripta za vezbe iz predmeta "Strukture podataka
i algoritmi 1"}
-\newcommand{\datum}{Februar 2013, Novi Sad}
-\newcommand{\verzija}{ver 13a-\varijacija}
+\newcommand{\datum}{Februar 2014, Novi Sad}
+\newcommand{\verzija}{ver 14a-\varijacija}
%varijacija je definisana u fajlu koji ukljucuje ovaj
\title{\naslov -- \verzija}
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}
+ \vspace{15ex}
{\Large {\bf Skripta za vežbe iz predmeta }}
% ----------------==================--------------------------------------
% 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
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/}
+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/}
-\tableofcontents
+\newpage
-%\newpage
+\tableofcontents
\mainstart
+\sectionbreak
+
\section{Ilustracija efikasnosti algoritma}
\subsection{Zadatak: Pronaći sve pitagorine
\end{array}
\]
+\manbreakJK
\begin{codeblock}
MODULE Trojke3;
(* Pitagorine trojke koriscenjem teoreme *)
END Trojke5.
\end{lstlisting}
-\manbreakJK
-
\subsection[Zadatak: Maksimalna suma susednih elemenata u
nizu]{Zadatak: Maksimalna suma proizvoljnog broja susednih elemenata u
nizu celih brojeva}
END MaxNiza4.
\end{codeblock}
+\sectionbreak
\section{Stringovi}
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}
END nizslog.
\end{lstlisting}
+\sectionbreak
\section{Liste i pokazivači}
Za rad sa pokazivačima je potrebno iz modula \kod{Storage} uvesti procedure
END VisTez.
\end{lstlisting}
+\sectionbreak
\section{Polinomi preko listi}
\subsection{Moduli}
\paragraph{PolinomL.DEF} \
-\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.
-\end{lstlisting}
+\lstinputlisting[style=codeblock]{kodovi/polinomi/POLINOML.DEF}
\paragraph{PolinomL.MOD} \
-\begin{codeblock}
-(* Modul za rad sa polinomima preko listi
- verzija 2012, rev 1 *)
-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
- p := NIL;
-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('Unesite koeficijent monoma br.');
- WriteCard(i, 1);
- WriteString(' (<> 0) ');
- ReadReal(k);
- WriteLn
- UNTIL k <> 0.0;
- REPEAT
- WriteLn;
- WriteString('Unesite 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( p, rez );
- 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{codeblock}
-
+\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$.
-\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}
+\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
-\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}
+\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]
END
END
END Top;
+\end{lstlisting}
+\begin{codeblock}
PROCEDURE Pop(VAR s : StekTip;
VAR ok : BOOLEAN);
BEGIN
END
END
END wcw.
-\end{lstlisting}
+\end{codeblock}
+
+\manbreakJK
\subsection{Zadatak: Kalkulator za izračunavanje postfiksnih izraza}
END PostFix.
\end{lstlisting}
-
+\sectionbreak
\section{Simulacija rekurzije}
END Fakto.
\end{lstlisting}
-\manbreakJK
-
\subsection{Primer 2 -- stepenovanje}
\begin{lstlisting}[style=codeblock]
\appendix
+\sectionbreak
\section{Native XDS Modula 2 -- kratko uputstvo}
@@ -2914,8 +2510,7 @@ sistem, njenu instalaciju, te kako napraviti i pokretnuti jednostavan program.
Native XDS Modula 2 se može besplatno skinuti sa sajta proizvođača,
-\url{http://www.excelsior-usa.com/}, tačnije na adresi:
-
+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