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=50655d0b7b895274d8d75526f62d0705823c2fd9;hb=HEAD;hpb=5032b8ef31be8b199297901b7fe1ec2c6dccea37 diff --git a/skripta-spa1-sadrzaj.tex b/skripta-spa1-sadrzaj.tex index 50655d0..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 @@ -532,10 +536,19 @@ najadekvatniju za konkretnu primenu. U opštem slučaju definišemo npr: 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 @@ -546,13 +559,12 @@ sledeći način: 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 @@ -564,12 +576,72 @@ između \kod{Compare} i 0 isti kao i između prvog i drugog stringa. 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 @@ -644,6 +716,34 @@ pri operacijama otvaranja i zatvaranja fajlova, odnosno neće se pri 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} @@ -663,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} @@ -765,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 @@ -791,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] @@ -1479,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} \ @@ -1688,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; @@ -1737,9 +1871,7 @@ BEGIN END END END Top; -\end{lstlisting} -\begin{codeblock} PROCEDURE Pop(VAR s : StekTip; VAR ok : BOOLEAN); BEGIN @@ -2375,6 +2507,9 @@ END Rek2. \pagenumbering{Roman} \input{xds-uputstvo} +\sectionbreak +\input{xds-komandna-linija} + \mainend