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
String = ARRAY [1..30] OF CHAR;
\end{codeblock}
-Operacije nad stringovima se najčešće uvoze iz modula \kod{Str}. One
-sve prihvataju \emph{otvorene nizove znakova} (strukture definisane sa
-\kod{ARRAY OF CHAR}), tako da im se može proslediti niz proizvoljne
-dužine.
+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
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, a delom 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''. Ovo se lako pamti kad primetimo da je odnos
-između \kod{Compare} i 0 isti kao i između prvog i drugog stringa.
+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
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}
+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
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. 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.
+
+\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}
\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