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 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}
\usepackage{latexsym}
\usepackage{multicol}
+\usepackage{tikz}
+\usetikzlibrary{chains}
+
+
\begin{document}
%customize the itemize environments
\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
č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.
\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}
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
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]
\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} \
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;
END
END
END Top;
-\end{lstlisting}
-\begin{codeblock}
PROCEDURE Pop(VAR s : StekTip;
VAR ok : BOOLEAN);
BEGIN
\pagenumbering{Roman}
\input{xds-uputstvo}
+\sectionbreak
+\input{xds-komandna-linija}
+
\mainend