X-Git-Url: http://svarog.pmf.uns.ac.rs/gitweb/?a=blobdiff_plain;f=skripta-spa1-sadrzaj.tex;h=61350f0fa566f6a23d7bfd135da1b874ae4a949d;hb=5e0787dfd5359ffe9a205a791d5f86e9cf7e6e94;hp=68dacce7f13bebf45312b03138dc55d0c5fc71dd;hpb=3a61709b99b7f56048e0cdf6422ad84882f42b1e;p=spa1skripta-public.git diff --git a/skripta-spa1-sadrzaj.tex b/skripta-spa1-sadrzaj.tex index 68dacce..61350f0 100644 --- a/skripta-spa1-sadrzaj.tex +++ b/skripta-spa1-sadrzaj.tex @@ -10,7 +10,7 @@ \newcommand{\naslov}{Skripta za vezbe iz predmeta "Strukture podataka i algoritmi 1"} \newcommand{\datum}{Februar 2013, Novi Sad} -\newcommand{\verzija}{ver 13a-\varijacija} +\newcommand{\verzija}{ver 14a-\varijacija} %varijacija je definisana u fajlu koji ukljucuje ovaj \title{\naslov -- \verzija} @@ -90,7 +90,7 @@ pdfauthor={\autor}% 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 }} @@ -148,6 +148,7 @@ pdfauthor={\autor}% % ----------------==================-------------------------------------- % 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 @@ -155,14 +156,17 @@ 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/} +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 @@ -246,6 +250,7 @@ a^2 + b^2 & c^2\\ \end{array} \] +\manbreakJK \begin{codeblock} MODULE Trojke3; (* Pitagorine trojke koriscenjem teoreme *) @@ -331,8 +336,6 @@ BEGIN END Trojke5. \end{lstlisting} -\manbreakJK - \subsection[Zadatak: Maksimalna suma susednih elemenata u nizu]{Zadatak: Maksimalna suma proizvoljnog broja susednih elemenata u nizu celih brojeva} @@ -517,6 +520,7 @@ BEGIN END MaxNiza4. \end{codeblock} +\sectionbreak \section{Stringovi} @@ -563,6 +567,7 @@ 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} @@ -783,6 +788,7 @@ BEGIN END nizslog. \end{lstlisting} +\sectionbreak \section{Liste i pokazivači} Za rad sa pokazivačima je potrebno iz modula \kod{Storage} uvesti procedure @@ -1595,6 +1601,7 @@ BEGIN END VisTez. \end{lstlisting} +\sectionbreak \section{Polinomi preko listi} \subsection{Moduli} @@ -1604,446 +1611,32 @@ Polinomi su predstavljeni pomoću pokazivača. Apstraktni tip podataka \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] @@ -2272,7 +1865,9 @@ BEGIN END END END Top; +\end{lstlisting} +\begin{codeblock} PROCEDURE Pop(VAR s : StekTip; VAR ok : BOOLEAN); BEGIN @@ -2340,7 +1935,9 @@ BEGIN END END END wcw. -\end{lstlisting} +\end{codeblock} + +\manbreakJK \subsection{Zadatak: Kalkulator za izračunavanje postfiksnih izraza} @@ -2393,7 +1990,7 @@ BEGIN END PostFix. \end{lstlisting} - +\sectionbreak \section{Simulacija rekurzije} @@ -2503,8 +2100,6 @@ BEGIN END Fakto. \end{lstlisting} -\manbreakJK - \subsection{Primer 2 -- stepenovanje} \begin{lstlisting}[style=codeblock] @@ -2904,6 +2499,7 @@ END Rek2. \appendix +\sectionbreak \section{Native XDS Modula 2 -- kratko uputstvo}