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=585798d402a33e48497476f025b8dce799505c6c;hb=HEAD;hpb=8ca1fae76b9dc43413cea5aeaad0e735b1c25717

diff --git a/skripta-spa1-sadrzaj.tex b/skripta-spa1-sadrzaj.tex
index 585798d..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,54 +576,137 @@ 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
 sa kojim radimo. Da bi ga koristili moramo ga uvesti u program (isto
 kao Å¡to uvozimo i komande).
 
-\begin{quote}U primerima se pretpostavlja da je ``f'' tipa \kod{File}, ``str'' niz
-znakova, ``i'' tipa \kod{INTEGER}, ``c'' tipa \kod{CARDINAL} i ``ch''
-tipa \kod{CHAR}. Dodatna promenljiva ``n'' tipa \kod{INTEGER} služi za
-formatiranje slično kao u modulu \kod{InOut}.
-\end{quote}
+\emph{U primerima se pretpostavlja da je ``f'' tipa \kod{File},
+  ``str'' niz znakova, ``i'' tipa \kod{INTEGER}, ``c'' tipa
+  \kod{CARDINAL} i ``ch'' tipa \kod{CHAR}. Dodatna promenljiva ``n''
+  tipa \kod{INTEGER} služi za formatiranje slično kao u modulu
+  \kod{InOut}, odnosno za ispis će biti zauzeto bar ``n'' znakova.}
+
+
+Ako otvaramo već postojeći fajl, poželjno je prvo proveriti da li on
+postoji -- u suprotnom naš program će se srušiti pri izvršavanju.
+Funkcija \kod{Exists(str)} vraća da li fajl postoji.
 
 Promenljiva tipa \kod{File} se mora vezati za neki fajl
 jednom od sledećih komandi:
 \begin{itemize}
-\item \kod{f := Open(str);} -- otvara se postojeci fajl za čitanje\\
-\item \kod{f := Create(str);} -- kreira se fajl za pisanje\\
+\item \kod{f := Open(str);} -- otvara se postojeci fajl za čitanje
+\item \kod{f := Create(str);} -- kreira se fajl za pisanje; ako je već
+  postojao, biće zamenjen
 \item \kod{f := Append(str);} -- otvara se postojeći fajl za
   dopisivanje na kraj
 \end{itemize}
 
-Po završetku rada fajl se mora zatvoriti, u našem primeru to bi bilo
-\kod{Close(f);}
+Po završetku rada fajl se mora zatvoriti, u našem primeru to bi bilo:
+\begin{itemize}
+\item \kod{Close(f);}
+\end{itemize}
 
 Procedure za čitanje i pisanje su vrlo slične onima iz modula
 \kod{IO}, osim što imaju dodatni parametar „\kod{f}“ koji označava
 fajl sa kojim se radi.
 \begin{itemize}
-\item \kod{RdStr(f,str)} -- učitava ceo red u string str\\
-\item   \kod{RdItem(f,str)} -- učitava jednu reč u string str (učitava znakove iz fajla dok ne naiđe na separator)\\
-\item   \kod{i:= RdInt(f); c:= RdCard(f)} -- učitava broj, koji se dobija kao rezultat procedure\\
+\item \kod{RdStr(f,str)} -- učitava ceo red u string str
+\item \kod{RdItem(f,str)} -- učitava jednu reč u string str (učitava
+  znakove iz fajla dok ne naiđe na separator)
+\item \kod{i:= RdInt(f); c:= RdCard(f)} -- učitava broj, koji se
+  dobija kao rezultat procedure
 \item   \kod{ch:= RdChar(f)} -- vraća jedan znak iz fajla
 \end{itemize}
 
+Bitno je obratiti pažnju na specifičnost da postoje dve komande za
+čitanje stringova iz fajla i da se one ponašaju različito.  Budući da
+razmak spada u separatore to znači da se korišćenjem \kod{RdItem} ne
+može učitati string koji ima u sebi razmake.
+
 Analogne su i procedure za pisanje različitih tipova u fajl:
 \begin{itemize}
-\item \kod{WrStr(f,str); WrInt(f,i,n);}\ \kod{WrCard(f,c,n);}\
-  \kod{WrChar(f,ch);}
+\item \kod{WrStr(f,str);}
+\item \kod{WrInt(f,i,n);}
+\item \kod{WrCard(f,c,n);}
+\item \kod{WrChar(f,ch);}
 \end{itemize}
 
+Treba primetiti da ne postoje dve komande za ispis stringa u fajl --
+potpuno je svejedno da li on ima razmake u sebi ili ne.
+
+Prelom reda se eksplicitno upisuje u fajl komandom
+\begin{itemize}
+\item \kod{WrLn(f);}.
+\end{itemize}
 
-Prelom reda se eksplicitno upisuje u fajl komandom \kod{WrLn(f);}.
 
 Da bi odredili da li smo stigli do kraja fajla možemo koristiti
 \kod{EOF}. U pitanju je logička promenljiva koja se uvozi iz modula
@@ -621,38 +716,40 @@ 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.
 
-\subsection{Zadatak: ispis sadržaja fajla na ekran}
+\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.
 
-Potrebno je sve redove iz fajla učitati i ispisati ih na ekran.
 
-\begin{lstlisting}[style=codeblock]
-MODULE ispis;
-FROM FIO IMPORT File, Open, Close, EOF, RdStr;
-FROM InOut IMPORT WriteString, WriteLn, ReadString;
+\subsection{Zadatak: ispis sadržaja fajla na ekran}
 
-PROCEDURE ispisF(ime: ARRAY OF CHAR);
-VAR
-  f:File;
-  s : ARRAY[1..100] OF CHAR;
-BEGIN
-  f:=Open(ime);
-  EOF := FALSE;
-  WHILE NOT EOF DO
-      RdStr(f,s);
-      WriteString(s);
-      WriteLn;
-  END;
-  Close(f);
-END ispisF;
+Potrebno je sve redove iz fajla učitati i ispisati ih na ekran.
 
-VAR
-  ime: ARRAY[1..100] OF CHAR;
-BEGIN
-  WriteString("unesite ime fajla:");
-  ReadString(ime);
-  ispisF(ime);
-END ispis.
-\end{lstlisting}
+\lstinputlisting[style=codeblock]{kodovi/fajlovi/ispis.mod}
 
 \subsection{Zadatak: spisak studenata}
 
@@ -661,139 +758,22 @@ novog studenta u spisak i snima fajl.  U fajlu se u svakom redu nalazi
 podatak o jednom studentu, redom prezime, ime i godina rođenja,
 razdvojeni razmacima.
 
-\begin{lstlisting}[style=codeblock]
-MODULE nizslog;
-FROM InOut IMPORT WriteString, WriteLn, 
-     WriteCard, ReadCard, ReadString;
-FROM FIO IMPORT File, Open, Create, Close, EOF,
-    RdItem, RdCard, WrStr, WrCard, WrLn;
-FROM Str IMPORT Compare;
-
-CONST
-    MaxStud = 100;
-TYPE
-    String = ARRAY[1..30] OF CHAR;
-    Student = RECORD
-        ime, prez: String;
-        god: CARDINAL;
-    END;
-    Studenti = ARRAY[1..MaxStud] OF Student;
-
-PROCEDURE UcitajF(fajl:String;
-          VAR spisak: Studenti; VAR n:CARDINAL);
-VAR
-    f:File;
-BEGIN
-    n:=0;
-    f:= Open(fajl);
-    EOF := FALSE;
-    WHILE NOT EOF DO
-        INC(n);
-        RdItem(f, spisak[n].prez);
-        RdItem(f, spisak[n].ime);
-        spisak[n].god := RdCard(f);
-    END;
-    Close(f);
-END UcitajF;
-
-PROCEDURE Ispisi(spisak:Studenti; n:CARDINAL);
-VAR
-    i: CARDINAL;
-BEGIN
-    FOR i:=1 TO n DO
-        WriteString(spisak[i].prez);
-        WriteString(" ");
-        WriteString(spisak[i].ime);
-        WriteString(" ");
-        WriteCard(spisak[i].god,1);
-        WriteLn;
-    END;
-END Ispisi;
-
-PROCEDURE IspisiF(fajl:String;
-          spisak:Studenti; n:CARDINAL);
-VAR
-    f:File;
-    i: CARDINAL;
-BEGIN
-    IF (n>0) AND (n<=MaxStud) THEN
-        f:=Create(fajl);
-        (* pravimo takav fajl da ne
-           postoji zadnji prazan red *)
-        FOR i:=1 TO n-1 DO
-            WrStr(f,spisak[i].prez);
-            WrStr(f," ");
-            WrStr(f,spisak[i].ime);
-            WrStr(f," ");
-            WrCard(f,spisak[i].god,1);
-            WrLn(f);
-        END;
-        WrStr(f,spisak[n].prez);
-        WrStr(f," ");
-        WrStr(f,spisak[n].ime);
-        WrStr(f," ");
-        WrCard(f,spisak[n].god,1);
-        Close(f);
-    END;
-END IspisiF;
-
-PROCEDURE NoviStudent(VAR spisak:Studenti;
-                      VAR n:CARDINAL);
-VAR
-    stud,temp:Student;
-    i:CARDINAL;
-    dodaj:BOOLEAN;
-BEGIN
-    IF n<MaxStud THEN
-        WriteString("Prezime novog studenta?");
-        ReadString(stud.prez);
-        WriteString("Ime novog studenta?");
-        ReadString(stud.ime);
-        WriteString("Godina rodjenja");
-        WriteString("novog studenta?");
-        ReadCard(stud.god);
-        (* proverimo da li vec postoji *)
-        i:=1;
-        dodaj := TRUE;
-        WHILE (i<=n) AND dodaj DO
-            temp := spisak[i];
-            IF (temp.god = stud.god) &
-              (Compare(temp.prez,stud.prez)=0) &
-              (Compare(temp.ime,stud.ime)=0) THEN
-                dodaj:=FALSE;
-            END;
-            INC(i);
-        END;
-        IF dodaj THEN
-            INC(n);
-            spisak[n]:=stud;
-        ELSE
-            WriteString("podaci vec postoje!");
-        END;
-    ELSE
-        WriteString("popunjen kapacitet!");
-    END;
-END NoviStudent;
-
-VAR
-    spisak : Studenti;
-    fajl:String;
-    n:CARDINAL;
-BEGIN
-    fajl:="studenti.txt";
-    UcitajF(fajl, spisak, n);
-    Ispisi(spisak, n);
-    NoviStudent(spisak,n);
-    IspisiF(fajl, spisak, n);
-END nizslog.
-\end{lstlisting}
+\lstinputlisting[style=codeblock]{kodovi/fajlovi/nizslog.MOD}
 
 \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}
 
@@ -893,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
@@ -919,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]
@@ -1607,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} \ 
 
@@ -1816,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;
@@ -1865,9 +1871,7 @@ BEGIN
     END
   END
 END Top;
-\end{lstlisting}
 
-\begin{codeblock}
 PROCEDURE Pop(VAR s : StekTip;
               VAR ok : BOOLEAN);
 BEGIN
@@ -2503,6 +2507,9 @@ END Rek2.
 \pagenumbering{Roman}
 \input{xds-uputstvo}
 
+\sectionbreak
+\input{xds-komandna-linija}
+
 \mainend