X-Git-Url: http://svarog.pmf.uns.ac.rs/gitweb/?p=spa1skripta-public.git;a=blobdiff_plain;f=skripta-spa1-sadrzaj.tex;h=737cb2a837dd04c5ac731eb0d1d6e6e1d92a806f;hp=2d3146e12cf02a137e41ead823ce04e0742682d5;hb=HEAD;hpb=7b0251c69e779464030fa1b5a23b38e921bb39cf

diff --git a/skripta-spa1-sadrzaj.tex b/skripta-spa1-sadrzaj.tex
index 2d3146e..737cb2a 100644
--- a/skripta-spa1-sadrzaj.tex
+++ b/skripta-spa1-sadrzaj.tex
@@ -9,8 +9,8 @@
 \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}
+\newcommand{\datum}{April 2014, Novi Sad}
+\newcommand{\verzija}{ver 14c-\varijacija}
 %varijacija je definisana u fajlu koji ukljucuje ovaj
 
 \title{\naslov -- \verzija}
@@ -37,6 +37,10 @@ pdfauthor={\autor}%
 \usepackage{latexsym}
 \usepackage{multicol}
 
+\usepackage{tikz}
+\usetikzlibrary{chains}
+
+
 \begin{document}
 
 %customize the itemize environments
@@ -581,6 +585,63 @@ procedure, no na njih se sada nećemo fokusirati.
 \sectionbreak
 \section{Rad sa fajlovima}
 
+Za rad sa fajlovima je bitno razumeti da su oni u suštini niz znakova,
+pri čemu neki imaju posebna značenja. Na primer novi red u tekstualnom
+fajlu ne postoji u istom smislu kao na ekranu ili na papiru, budući da
+svi znakovi dolaze jedan posle drugog u jednom nizu. Umesto toga
+postoje specijalo definisani kodovi u ASCII tabeli znakova koji
+predstavljaju prelome:
+\begin{itemize}
+\item Kod 10 -- \emph{Line feed} -- red dole na štampaču
+\item Kod 13 -- \emph{Carriage return} -- povratak na početak reda
+\end{itemize}
+
+Različiti operativni sistemi koriste različite kombinacije ovih
+znakova da označe prelome redova -- Windows koristi oba jedan za
+drugim, Linux i drugi srodni operativni sistemi tipično koriste samo
+\emph{LF}, dok je Apple definisao da je sam \emph{CR} prelom
+reda. Kvalitetni tekstualni editori uglavnom mogu sami da prepoznaju
+prelom koji je korišćen u fajlu i da se adekvatno prilagode.
+
+Pri radu sa fajlom se on tipično otvara preko neke pomoćne strukture
+koja potom pamti poziciju u fajlu odakle treba nastaviti čitanje ili
+gde će biti nastavljeno pisanje.
+
+\noindent\begin{minipage}{\columnwidth}
+\centering
+\begin{tikzpicture}
+% Delimicno bazirano na http://www.texample.net/tikz/examples/turing-machine-2/
+\tikzstyle{every path}=[very thick]
+
+\edef\sizetape{0.7cm}
+\tikzstyle{tmtape}=[draw,minimum size=\sizetape]
+
+%% Draw TM tape
+\begin{scope}[start chain=1 going right,node distance=-0.15mm]
+    \node [on chain=1,tmtape] {R};
+    \node [on chain=1,tmtape] {e};
+    \node [on chain=1,tmtape] {d};
+    \node [on chain=1,tmtape] { };
+    \node [on chain=1,tmtape] {1};
+    \node [on chain=1,tmtape] (input) {\emph{LF}};
+    \node [on chain=1,tmtape] {\emph{CR}};
+    \node [on chain=1,tmtape] {2};
+    \node [on chain=1,tmtape,draw=none] {$\ldots$};
+\end{scope}
+
+\node [yshift=.3cm] at (input.north) (head) {V};
+
+\end{tikzpicture}
+
+\emph{Primer: tekstualni fajl u kome u prvom redu piše ``Red 1'', a
+  drugi počinje znakom ``2''. Pozicija prikazuje da smo pročitali prvi
+  red.}
+\end{minipage}\\
+
+Bitno je i napomenuti da ukoliko pišemo u postojeći fajl novi sadržaj
+zamenjuje stari -- odnosno biće pisano preko starog teksta. Tipično ne
+postoje opcije da se novi sadržaj umeće u sredinu postojećeg fajla.
+
 \subsection{Modul FIO}
 
 U ovom modulu je definisan tip \kod{File}, koji predstavlja jedan fajl
@@ -668,7 +729,7 @@ sa drugima. Problem je u različitom tretiranju separatora. Komanda
 č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
+znaci) i staju sa čitanjem \emph{pre} tog separatora. Kombinovanje
 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.
@@ -702,9 +763,17 @@ razdvojeni razmacima.
 \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}.
+Za rad sa pokazivačima je potrebno iz modula \kod{Storage} uvesti
+procedure za dinamičko zauzimanje i oslobađanje
+memorije \kod{ALLOCATE} i \kod{DEALLOCATE}. 
+
+U kodu se mogu koristiti i skraćeni oblici \kod{NEW} i \kod{DISPOSE}
+koji se direktno prevode u prethodno pomenute procedure.
+
+\begin{codeblock}
+ALLOCATE(point, SIZE(point));   (* isto kao NEW(point)     *)
+DEALLOCATE(point, SIZE(point)); (* isto kao DISPOSE(point) *)
+\end{codeblock}
 
 \subsection{Zadatak: Formiranje, Å¡tampanje i brisanje listi}
 
@@ -804,7 +873,7 @@ BEGIN
   END;
 END DodajKraj;
 
-PROCEDURE DodajSort(VAR lista:brojevi; br:CARDINAL);
+PROCEDURE DodajSort(VAR lista:brojevi; br:INTEGER);
 (* dodaje broj tako da lista ostane sortirana 
    (podrazumeva se da je vec sortirana) *)
 VAR
@@ -830,6 +899,31 @@ BEGIN
 END DodajSort;
 \end{lstlisting}
 
+Kod svih procedura se mogu primeniti i rekurzivne varijante. Sledi
+primer za kreiranje sortirane liste.
+
+\begin{codeblock}
+PROCEDURE DodajSortRek(VAR lista:brojevi; br:INTEGER);
+(* Koristi se cinjenica da prosledjujemo pokazivac
+po referenci, tj. da ga mozemo menjati unutar procedure *)
+VAR
+  temp : brojevi;
+BEGIN
+  IF (lista = NIL) OR (lista^.info>=br) THEN
+    (* Izlaz iz rekurzije. Ubacivanje u praznu listu,
+    na kraj liste ili na odgovarajuce mesto *)
+    NEW(temp);
+    temp^.info:=br;
+    temp^.veza:=lista;
+    lista:=temp;
+  ELSE
+    DodajSortRek(lista^.veza, br);
+  END;
+END DodajSortRek;
+\end{codeblock}
+
+\manbreakJK
+
 \subsection{Zadatak: Prikaz osnovih operacija nad listama}
 
 \begin{lstlisting}[style=codeblock]
@@ -1518,7 +1612,8 @@ END VisTez.
 \subsection{Moduli}
 
 Polinomi su predstavljeni pomoću pokazivača. Apstraktni tip podataka
-\kod{Polinom} je definisan u globalnom modulu.
+\kod{Polinom} je definisan u globalnom modulu. Redosled parametara kod
+svih procedura je takav da varijabilni parametri dolaze na kraju.
 
 \paragraph{PolinomL.DEF} \ 
 
@@ -1727,7 +1822,7 @@ END Bafer.
 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]
+\begin{codeblock}
 DEFINITION MODULE Stek;
 CONST
   Maxstack = 100;
@@ -1776,9 +1871,7 @@ BEGIN
     END
   END
 END Top;
-\end{lstlisting}
 
-\begin{codeblock}
 PROCEDURE Pop(VAR s : StekTip;
               VAR ok : BOOLEAN);
 BEGIN
@@ -2414,6 +2507,9 @@ END Rek2.
 \pagenumbering{Roman}
 \input{xds-uputstvo}
 
+\sectionbreak
+\input{xds-komandna-linija}
+
 \mainend