Univerzitet u Novom Sadu
Prirodno-matematički fakultet
Departman za matematiku i informatiku
Vladimir Kurbalija, [email protected]
Miloš Radovanović, [email protected]
Doni Pracner, [email protected]
Skripta za vežbe iz predmeta
Strukture podataka i algoritmi 1
ver 14c-jk – April 2014, Novi Sad
Programi u ovoj skripti su testirani sa kompajlerom ’Native XDS Modula 2’. Za verzije pre 2.60 je
neophodno dodatno instalirati i TSCP (Top Speed Compatibility Pack), pošto je potreban za neke od
modula koji se ne nalaze u ISO standardu Module 2. U novijim verzijama su i ovi moduli uključeni u
standardnu instalaciju.
Sav sadržaj se može koristiti u skladu sa CC-BY-NC-SA licencom.
http://creativecommons.org/licenses/by-nc-sa/3.0/
2
Strukture podataka i algoritmi 1 – skripta
Sadržaj
1 Ilustracija efikasnosti algoritma
1.1 Zadatak: Pronaći sve pitagorine trojke do zadate granice . . . . . . . . . . . . . . . .
1.2 Zadatak: Maksimalna suma susednih elemenata u nizu . . . . . . . . . . . . . . . . .
3
3
5
2 Stringovi
8
3 Rad
3.1
3.2
3.3
sa fajlovima
Modul FIO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Zadatak: ispis sadržaja fajla na ekran . . . . . . . . . . . . . . . . . . . . . . . . . .
Zadatak: spisak studenata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4 Liste i pokazivači
4.1 Zadatak: Formiranje, štampanje i brisanje listi . . . . . . . . .
4.2 Zadatak: Prikaz osnovih operacija nad listama . . . . . . . . .
4.3 Zadatak: Prikaz operacija nad listama sa jedinstvenim ključem
4.4 Zadatak: Dve liste osoba sa istim sadržajem . . . . . . . . . .
9
9
10
11
.
.
.
.
13
13
15
19
22
5 Polinomi preko listi
5.1 Moduli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Zadatak: Sabiranje sa unapred određenim polinomom . . . . . . . . . . . . . . . . . .
5.3 Zadatak: Suma k polinoma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
24
29
30
6 Stek i red opsluživanja
6.1 Primer: osnovno korišćenje steka i reda opsluživanja . .
6.2 Zadatak: Ilustracija pisanja u fajl uz pomoć bafera . .
6.3 Zadatak: Ispitivanje da li reč pripada gramatici wcw+ .
6.4 Zadatak: Kalkulator za izračunavanje postfiksnih izraza
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
31
31
31
34
36
7 Simulacija rekurzije
7.1 Primer 1 – faktorijel . . .
7.2 Primer 2 – stepenovanje .
7.3 Primer 3 – Fibonači . . .
7.4 Primer 4 – faktorijel 2 . .
7.5 Primer 5 (ispitni) . . . .
7.6 Primer 6 (ispitni) . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
37
37
38
39
40
41
42
A Native XDS Modula 2 – kratko uputstvo
A.1 Mogući problemi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
I
II
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
B XDS modula 2 - rad iz komandne linije
B.1 Prednosti (ili “Zašto ovo raditi?”) . . . . . . . . . . . . . . . . .
B.2 Podešavanje sistemske putanje (ili "OK, odakle početi?") . . . . .
B.3 Kompajliranje programa . . . . . . . . . . . . . . . . . . . . . . .
B.4 Linux i drugi slobodni sistemi (ili "Who needs windows anyway?")
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
III
III
III
III
III
1 Ilustracija efikasnosti algoritma
1
3
Ilustracija efikasnosti algoritma
1.1
Zadatak: Pronaći sve pitagorine trojke do zadate granice
Pitagorina trojka su tri broja a, b, c za koje važi a2 + b2 = c2
MODULE Trojke1;
(* Pitagorine trojke koriscenjem "Brute-force" *)
FROM InOut IMPORT WriteString, WriteLn, WriteCard;
CONST
Gr = 100;
VAR
a, b, c : [1 .. Gr];
BEGIN
FOR a := 1 TO Gr DO
FOR b := 1 TO Gr DO
FOR c := 1 TO Gr DO
IF a*a + b*b = c*c THEN
WriteLn;
WriteString(’a = ’);
WriteCard(a,2);
WriteString(’, b = ’);
WriteCard(b,2);
WriteString(’, c = ’);
WriteCard(c,2)
END
END
END
END
END Trojke1.
MODULE Trojke2;
(*Pitagorine trojke koriscenjem zaokrugljivanja*)
FROM InOut IMPORT WriteString, WriteLn, WriteCard;
FROM MathLib0 IMPORT sqrt;
CONST
Gr = 100;
VAR
a, b, c : CARDINAL;
creal : REAL;
BEGIN
FOR a := 1 TO Gr DO
FOR b := 1 TO Gr DO
creal := FLOAT(a*a) + FLOAT(b*b);
creal := sqrt(creal);
c := TRUNC(creal);
IF creal = FLOAT(c) THEN
WriteLn;
WriteString(’ a = ’);
WriteCard(a,2);
WriteString(’, b = ’);
WriteCard(b,2);
WriteString(’, c = ’);
WriteCard(c,2)
END
END
END
END Trojke2.
Sledeći primer koristi Euklidovu teoremu i malo drugačiji pristup. Ako uzmemo neka dva prirodna
broja m i n, tada se iz njih može izvesti jedna Pitagorina trojka koja lako zadovoljava potrebne uslove:
a = 2mn
b = m 2 − n2
c = m2 + n2
Odnosno kad probamo da proverimo da li je ovo Pitagorina trojka dobijamo:
a2 + b2 =c2
(2mn) + (m − n2 )2 =(m2 + n2 )2
2
2
4
Strukture podataka i algoritmi 1 – skripta
MODULE Trojke3;
(* Pitagorine trojke koriscenjem teoreme *)
FROM InOut IMPORT WriteString, WriteLn, WriteCard;
CONST
Gr = 10;
VAR
a, b, c, m, n : CARDINAL;
BEGIN
FOR m := 1 TO Gr DO
FOR n := 1 TO m-1 DO
a := 2*m*n;
b := m*m - n*n;
c := m*m + n*n;
WriteLn;
WriteString(’a = ’);
WriteCard(a,2);
WriteString(’, b = ’);
WriteCard(b,2);
WriteString(’, c = ’);
WriteCard(c,2)
END
END
END Trojke3.
Sledeća dva metoda traže trojke sa nekim specifičnim osobinama.
MODULE Trojke4;
(* Pitagorine trojke kod kojih je razlika
izmedju katete i hipotenuze tacno 1 *)
FROM InOut IMPORT WriteString, WriteLn, WriteCard;
CONST
Gr = 10;
VAR
a, b, c, m, n : CARDINAL;
BEGIN
FOR m := 2 TO Gr DO
n := m - 1;
a := 2*m*n;
b := m*m - n*n;
c := m*m + n*n;
WriteLn;
WriteString(’a = ’);
WriteCard(a,2);
WriteString(’, b = ’);
WriteCard(b,2);
WriteString(’, c = ’);
WriteCard(c,2)
END
END Trojke4.
MODULE Trojke5;
(* Pitagorine trojke kod kojih je razlika
izmedju kateta jedan *)
FROM InOut IMPORT WriteString, WriteLn, WriteCard;
CONST
Gr = 7;
VAR
a, b, c, m, n, w, i, temp : CARDINAL;
BEGIN
w := 1;
n := 0;
FOR i := 1 TO Gr DO
m := n + w;
a := 2*m*n;
b := m*m - n*n;
c := m*m + n*n;
WriteLn;
WriteString(’a = ’);
WriteCard(a,2);
WriteString(’, b = ’);
WriteCard(b,2);
WriteString(’, c = ’);
WriteCard(c,2);
temp := w;
w := 3*w + 4*n;
n := 2*temp + 3*n
END
1.2
Zadatak: Maksimalna suma susednih elemenata u nizu
5
END Trojke5.
1.2
Zadatak: Maksimalna suma proizvoljnog broja susednih elemenata u nizu
celih brojeva
MODULE MaxNiza1;
(* Prvo resenje. Brute Force: O(n^3) *)
FROM InOut IMPORT WriteString,ReadInt,
WriteInt,WriteCard,WriteLn;
CONST
N = 10;
TYPE
Interval = [1..N];
VAR
Max, Suma : INTEGER;
d,g,i,Ood,Doo : Interval;
X : ARRAY Interval OF INTEGER;
BEGIN
WriteString(’ Unesite niz X ’);
WriteLn;
FOR i := 1 TO N DO
ReadInt(X[i]);
WriteLn
END;
Max := 0;
FOR d := 1 TO N DO
FOR g := 1 TO N DO
Suma := 0;
FOR i := d TO g DO
Suma := Suma + X[i]
END;
IF Suma > Max THEN
Max := Suma;
Ood := d;
Doo := g
END
END
END;
WriteLn;
WriteString(’ Maksimum je ’);
WriteInt(Max,3);
WriteString(’ u intervalu od ’);
WriteCard(Ood,3);
WriteString(’ do ’);
WriteCard(Doo,3)
END MaxNiza1.
MODULE MaxNiza2;
(* Drugo resenje: O(n^2).
Koristi se cinjenica da je suma X[d..g]
izracunljiva iz X[d..g-1]. *)
FROM InOut IMPORT WriteString,ReadInt,
WriteInt,WriteCard,WriteLn;
CONST
N = 10;
TYPE
Interval = [1..N];
VAR
Max, Suma : INTEGER;
d,g,i,Ood,Doo : Interval;
X : ARRAY Interval OF INTEGER;
BEGIN
WriteString(’ Unesite niz X ’);
WriteLn;
FOR i := 1 TO N DO
ReadInt(X[i]);
WriteLn
END;
Max := 0;
FOR d := 1 TO N DO
Suma := 0;
FOR g := d TO N DO
Suma := Suma + X[g];
IF Suma > Max THEN
6
Strukture podataka i algoritmi 1 – skripta
Max := Suma;
Ood := d;
Doo := g
END
END
END;
WriteLn;
WriteString(’ Maksimum je ’);
WriteInt(Max,3);
WriteString(’ u intervalu od ’);
WriteCard(Ood,3);
WriteString(’ do ’);
WriteCard(Doo,3)
END MaxNiza2.
MODULE MaxNiza3;
(* Trece resenje: O(n^2).
Koristi pomocni niz u kome je na i-tom mestu
suma podniza x[1..i] *)
FROM InOut IMPORT WriteString,ReadInt,
WriteInt,WriteCard,WriteLn;
CONST
N = 10;
TYPE
Interval = [1..N];
VAR
Max, Suma : INTEGER;
d,g,i,Ood,Doo : Interval;
X : ARRAY Interval OF INTEGER;
Pom : ARRAY [0..N] OF INTEGER;
BEGIN
WriteString(’ Unesite niz X ’);
WriteLn;
FOR i := 1 TO N DO
ReadInt(X[i]);
WriteLn
END;
Pom[0] := 0;
FOR i := 1 TO N DO
Pom[i] := Pom[i-1] + X[i]
END;
Max := 0;
FOR d := 1 TO N DO
FOR g := d TO N DO
Suma := Pom[g] - Pom[d-1];
IF Suma > Max THEN
Max := Suma;
Ood := d;
Doo := g
END
END
END;
WriteLn;
WriteString(’ Maksimum je ’);
WriteInt(Max,3);
WriteString(’ u intervalu od ’);
WriteCard(Ood,3);
WriteString(’ do ’);
WriteCard(Doo,3)
END MaxNiza3.
MODULE MaxNiza4;
(* Cetvrto resenje. Najbolje moguce: O(n)
FROM InOut IMPORT WriteString,ReadInt,
WriteInt,WriteCard,WriteLn;
CONST
N = 10;
TYPE
Interval = [1..N];
VAR
Max, MaxDovde : INTEGER;
i,d,Ood,Doo : Interval;
X : ARRAY Interval OF INTEGER;
BEGIN
WriteString(’ Unesite niz X ’);
WriteLn;
*)
1.2
Zadatak: Maksimalna suma susednih elemenata u nizu
FOR i := 1 TO N DO
ReadInt(X[i]);
WriteLn
END;
Max := 0;
MaxDovde := 0;
FOR i := 1 TO N DO
IF MaxDovde = 0 THEN
d := i
END;
MaxDovde := MaxDovde + X[i];
IF MaxDovde < 0 THEN
MaxDovde := 0
END;
IF MaxDovde > Max THEN
Ood := d;
Doo := i;
Max := MaxDovde
END
END;
WriteLn;
WriteString(’ Maksimum je ’);
WriteInt(Max,3);
WriteString(’ u intervalu od ’);
WriteCard(Ood,3);
WriteString(’ do ’);
WriteCard(Doo,3)
END MaxNiza4.
7
8
Strukture podataka i algoritmi 1 – skripta
2
Stringovi
Stringovi – odnosno nizovi znakova – ne postoje kao ugrađeni tip u jeziku Modula 2. Ovo daje
slobodu da se niz znakova definiše na dužinu najadekvatniju za konkretnu primenu. U opštem slučaju
definišemo npr:
TYPE
String = ARRAY [1..30] OF CHAR;
Budući da Modula 2 definiše mogućnost korišćenja otvorenih nizova, lako je moguće definisati
procedure koje kao parametre primaju bilo koji tip koji je definisan kao niz znakova.
PROCEDURE ObradaStringa(str: ARRAY OF CHAR);
Konkretne promenljive u programu moraju biti definisane dužine.
Operacije nad stringovima se najčešće uvoze iz modula Str i one su sve definisane da prihvataju
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 sledeći način:
duzina := Length(str)
Leksikografsko poređenje dva stringa se ne može vršiti standardnim operatorima kao što su < > =.
Ovo je delom zato što se radi o nizovima, ali značajnije i zato što se ne vidi direktno koji deo niza je
popunjen “stvarnim” sadržajem. Za ovo se koristi komanda 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”.
Compare(str1, str2) > 0 THEN
WriteString("Prvi string je veci");
ELSIF Compare(str1, str2) < 0 THEN
WriteString("Prvi string je manji");
ELSE (* moraju biti jednaki *)
WriteString("Jednaki su");
END;
IF
Ovo se lako pamti kad primetimo da je odnos između Compare i 0 isti kao i između prvog i drugog
stringa.
Postoji i modul Strings koji ima nešto drugačije definisane procedure, no na njih se sada nećemo
fokusirati.
3 Rad sa fajlovima
3
9
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:
• Kod 10 – Line feed – red dole na štampaču
• Kod 13 – Carriage return – povratak na početak reda
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 LF,
dok je Apple definisao da je sam 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.
V
R
e
d
1
LF CR
2
...
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.
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.
3.1
Modul FIO
U ovom modulu je definisan tip File, koji predstavlja jedan fajl sa kojim radimo. Da bi ga koristili
moramo ga uvesti u program (isto kao što uvozimo i komande).
U primerima se pretpostavlja da je “f” tipa File, “str” niz znakova, “i” tipa INTEGER, “c” tipa
CARDINAL i “ch” tipa CHAR. Dodatna promenljiva “n” tipa INTEGER služi za formatiranje slično kao u
modulu 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 Exists(str) vraća da li fajl postoji.
Promenljiva tipa File se mora vezati za neki fajl jednom od sledećih komandi:
• f := Open(str); – otvara se postojeci fajl za čitanje
• f := Create(str); – kreira se fajl za pisanje; ako je već postojao, biće zamenjen
• f := Append(str); – otvara se postojeći fajl za dopisivanje na kraj
Po završetku rada fajl se mora zatvoriti, u našem primeru to bi bilo:
• Close(f);
Procedure za čitanje i pisanje su vrlo slične onima iz modula IO, osim što imaju dodatni parametar
„f“ koji označava fajl sa kojim se radi.
• RdStr(f,str) – učitava ceo red u string str
• RdItem(f,str) – učitava jednu reč u string str (učitava znakove iz fajla dok ne naiđe na
separator)
• i:= RdInt(f); c:= RdCard(f) – učitava broj, koji se dobija kao rezultat procedure
• ch:= RdChar(f) – vraća jedan znak iz fajla
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 RdItem ne
može učitati string koji ima u sebi razmake.
Analogne su i procedure za pisanje različitih tipova u fajl:
•
•
•
•
WrStr(f,str);
WrInt(f,i,n);
WrCard(f,c,n);
WrChar(f,ch);
10
Strukture podataka i algoritmi 1 – skripta
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
• WrLn(f);.
Da bi odredili da li smo stigli do kraja fajla možemo koristiti EOF. U pitanju je logička promenljiva
koja se uvozi iz modula FIO kao bilo kakva normalna komanda. Ona označava da li smo poslednjom
operacijom čitanja stigli do kraja fajla. Ne menja joj se vrednost pri operacijama otvaranja i zatvaranja
fajlova, odnosno neće se pri tome resetovati na FALSE, pa na ovo treba obratiti pažnju pri radu.
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.
RdStr i drugi pozivi Prilikom čitanja iz fajlova može doći do neobičnih rezultata ako se kombinuju
pozivi RdStr sa drugima. Problem je u različitom tretiranju separatora. Komanda 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 pre tog separatora. Kombinovanje
ova dva pristupa može dovesti do toga da RdStr nakon neke druge komande učita samo kraj trenutnog
reda, a ne sledeći red kao što bi bilo očekivano.
EOF i prazan red na kraju fajla Svako čitanje iz fajla postavlja EOF u skladu sa tim da li je komanda
stigla do kraja fajla ili ne. Nažalost kod svih komandi za čitanje (osim 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.
3.2
Zadatak: ispis sadržaja fajla na ekran
Potrebno je sve redove iz fajla učitati i ispisati ih na ekran.
MODULE ispis;
FROM FIO IMPORT File, Exists, Open, Close, EOF, RdStr;
FROM InOut IMPORT WriteString, WriteLn, ReadString;
PROCEDURE ispisF(ime: ARRAY OF CHAR);
VAR
f:File;
s : ARRAY[1..100] OF CHAR;
BEGIN
IF Exists(ime) THEN
f:=Open(ime);
EOF := FALSE;
WHILE NOT EOF DO
RdStr(f,s);
WriteString(s);
WriteLn;
END;
Close(f);
ELSE
WriteString("-- fajl ne postoji --");
WriteLn;
END;
END ispisF;
VAR
ime: ARRAY[1..100] OF CHAR;
BEGIN
WriteString("unesite ime fajla:");
ReadString(ime);
ispisF(ime);
END ispis.
3.3
3.3
Zadatak: spisak studenata
11
Zadatak: spisak studenata
Napraviti program koji iz fajla učitava podatke o studentima, dodaje 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.
MODULE nizslog;
FROM InOut IMPORT WriteString, WriteLn, WriteCard,
ReadCard, ReadString;
FROM FIO IMPORT File, Exists, Open, Create, Close, EOF,
RdItem, RdCard, WrStr, WrCard, WrLn;
FROM Str IMPORT Compare;
CONST
MaxStud = 100;
radnifajl = "studenti.txt";
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;
IF Exists(fajl) THEN
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;
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," ");
12
Strukture podataka i algoritmi 1 – skripta
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("God. rodj. 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;
n:CARDINAL;
BEGIN
UcitajF(radnifajl, spisak, n);
Ispisi(spisak, n);
NoviStudent(spisak,n);
IspisiF(radnifajl, spisak, n);
END nizslog.
4 Liste i pokazivači
4
13
Liste i pokazivači
Za rad sa pokazivačima je potrebno iz modula Storage uvesti procedure za dinamičko zauzimanje
i oslobađanje memorije ALLOCATE i DEALLOCATE.
U kodu se mogu koristiti i skraćeni oblici NEW i DISPOSE koji se direktno prevode u prethodno
pomenute procedure.
ALLOCATE(point, SIZE(point));
(* isto kao NEW(point)
*)
DEALLOCATE(point, SIZE(point)); (* isto kao DISPOSE(point) *)
4.1
Zadatak: Formiranje, štampanje i brisanje listi
MODULE liste;
FROM InOut IMPORT WriteString, WriteLn, WriteInt,
ReadInt, ReadCard;
FROM Storage IMPORT ALLOCATE, DEALLOCATE;
TYPE
brojevi = POINTER TO brojSlog;
brojSlog = RECORD
info:INTEGER;
veza:brojevi;
END;
VAR
n,i:CARDINAL;
lista : brojevi;
br:INTEGER;
PROCEDURE DodajPoc(VAR lista:brojevi; br:INTEGER);
(* dodaje broj br na pocetak liste *)
VAR
temp:brojevi;
BEGIN
NEW(temp);
temp^.info := br;
temp^.veza := lista;
lista := temp;
END DodajPoc;
PROCEDURE Stampaj(lista:brojevi);
VAR
temp:brojevi;
BEGIN
temp:=lista;
WHILE temp # NIL DO
WriteInt(temp^.info,0);
WriteLn;
temp := temp^.veza;
END;
END Stampaj;
PROCEDURE Unisti(VAR lista:brojevi);
VAR
temp:brojevi;
BEGIN
temp:=lista;
WHILE temp # NIL DO
lista:=lista^.veza;
DISPOSE(temp);
temp:=lista;
END;
END Unisti;
BEGIN
lista := NIL;
WriteString(’unesite n (broj brojeva): ’);
ReadCard(n);
WriteString(’unesite brojeve: ’);
WriteLn;
FOR i:= 1 TO n DO
ReadInt(br);
DodajPoc(lista,br);
END;
WriteString(’sadrzaj liste:’);
WriteLn;
14
Strukture podataka i algoritmi 1 – skripta
Stampaj(lista);
Unisti(lista);
WriteString(’memorija je oslobodjena’);
WriteLn;
END liste.
Alternativno je poziv DodajPoc moguće zameniti pozivom jedne od sledeće dve procedure čime se
dobija dodavanje elementa na kraj liste, ili kreiranje sortirane liste:
PROCEDURE DodajKraj(VAR lista:brojevi; br:INTEGER);
(* dodaje element na kraj liste *)
VAR
tekuci, temp :brojevi;
BEGIN
NEW(temp);
temp^.info := br;
temp^.veza := NIL;
IF lista = NIL THEN
(* prazna lista *)
lista:=temp;
ELSE
tekuci := lista;
WHILE tekuci^.veza#NIL DO
tekuci:=tekuci^.veza;
END;
tekuci^.veza := temp;
END;
END DodajKraj;
PROCEDURE DodajSort(VAR lista:brojevi; br:INTEGER);
(* dodaje broj tako da lista ostane sortirana
(podrazumeva se da je vec sortirana) *)
VAR
temp, tekuci : brojevi;
BEGIN
NEW(temp);
temp^.info:=br;
temp^.veza:=NIL;
IF (lista = NIL) OR (lista^.info>=br) THEN
(*prazna lista ili na pocetak*)
temp^.veza:=lista;
lista := temp;
ELSE
(*negde u listi*)
tekuci:= lista;
WHILE (tekuci^.veza # NIL) AND
(tekuci^.veza^.info<=br) DO
tekuci:=tekuci^.veza;
END;
temp^.veza := tekuci^.veza;
tekuci^.veza:=temp;
END;
END DodajSort;
Kod svih procedura se mogu primeniti i rekurzivne varijante. Sledi primer za kreiranje sortirane liste.
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;
4.2
4.2
Zadatak: Prikaz osnovih operacija nad listama
Zadatak: Prikaz osnovih operacija nad listama
MODULE liste2;
FROM InOut IMPORT WriteString, WriteLn,
WriteCard, ReadCard;
FROM IO IMPORT RdKey;
FROM Storage IMPORT ALLOCATE, DEALLOCATE;
TYPE
skupZn = SET OF CHAR;
brojevi = POINTER TO brojSlog;
brojSlog = RECORD
info:CARDINAL;
veza:brojevi;
END;
VAR
lista : brojevi;
menu,prazno:CHAR;
PROCEDURE DodajPoc(VAR lista:brojevi; br:INTEGER);
(* dodaje broj pom na pocetak liste *)
VAR
temp:brojevi;
BEGIN
(* kreiramo novi element *)
NEW(temp);
temp^.info := br;
(* treba da pokazuje na ostatak liste *)
temp^.veza := lista;
(* pocetak liste je novi element *)
lista := temp;
END DodajPoc;
PROCEDURE Unos(VAR lista:brojevi);
(* dodaje n brojeva u listu *)
VAR
n,i,br:CARDINAL;
BEGIN
WriteString(’unesite n (broj brojeva): ’);
ReadCard(n);
FOR i:= 1 TO n DO
WriteString("unesite broj ");
WriteCard(i,0);
WriteString(": ");
ReadCard(br);
DodajPoc(lista,br);
END;
END Unos;
(* -- procedure za stampu -- *)
PROCEDURE Stampaj(lista:brojevi);
(* stampa sadrzaj liste na ekran *)
VAR
temp:brojevi;
BEGIN
WriteLn;
WriteString("Sadrzaj liste:");
WriteLn;
temp:=lista;
WHILE temp # NIL DO
WriteCard(temp^.info,0);
WriteLn;
temp := temp^.veza;
END;
END Stampaj;
PROCEDURE StampajK(VAR lista:brojevi);
(* stampa k-ti element (k unosi korisnik) *)
VAR
temp:brojevi;
k,brojac:CARDINAL;
BEGIN
WriteString("unesite redni broj elementa:");
ReadCard(k);
temp:=lista;
brojac := 1;
15
16
Strukture podataka i algoritmi 1 – skripta
WHILE (temp# NIL) AND (k>brojac) DO
temp:=temp^.veza;
INC(brojac);
END;
IF (temp#NIL) THEN
WriteCard(temp^.info,2);
ELSE
WriteString("greska! - ne postoji element");
WriteString(" u listi sa rednim brojem ");
WriteCard(k,2);
END;
WriteLn();
END StampajK;
PROCEDURE StampajMinimum(VAR lista:brojevi);
(* nalazi i stampa minimalni element liste *)
VAR
temp:brojevi;
min:CARDINAL;
BEGIN
IF (lista=NIL) THEN
WriteString("prazna lista!");
ELSE
min:=lista^.info;
temp:=lista^.veza;
WHILE temp # NIL DO
IF temp^.info < min THEN
min := temp^.info;
END;
temp := temp^.veza;
END;
WriteString("Minimalni element liste je ");
WriteCard(min,0);
END;
WriteLn;
END StampajMinimum;
(* -- pomocne procedure, bez ispisa
-- *)
PROCEDURE UListi(lista:brojevi;
br: CARDINAL):BOOLEAN;
(* vraca da li se ’br’ nalazi u listi ’lista’ *)
VAR
temp:brojevi;
BEGIN
temp:=lista;
WHILE (temp # NIL) AND (temp^.info # br) DO
(* dok ne dodjemo do kraja liste
ili ne nadjemo broj *)
temp := temp^.veza;
END;
IF temp#NIL THEN
(* znaci da nismo na kraju liste,
tj da je nadjen broj *)
RETURN TRUE;
ELSE (* temp = NIL *)
RETURN FALSE;
END;
END UListi;
PROCEDURE IzbaciIzListe(VAR lista:brojevi;
br: CARDINAL):BOOLEAN;
(* izbacuje broj ’br’ iz liste, naravno ako
postoji i vraca da li je operacija uspesno
obavljena *)
VAR
temp,prethodni:brojevi;
BEGIN
(* proverimo da li je prvi element *)
IF (lista # NIL) AND (lista^.info = br) THEN
temp:=lista;
lista :=lista^.veza;
DISPOSE(temp);
RETURN TRUE;
ELSE
(* trazimo u ostatku liste *)
4.2
Zadatak: Prikaz osnovih operacija nad listama
temp:=lista;
prethodni:=NIL;
WHILE (temp # NIL) AND (temp^.info # br) DO
(* dok ne dodjemo do kraja liste
ili ne nadjemo broj *)
prethodni:=temp;
temp := temp^.veza;
END;
IF temp#NIL THEN
(* znaci da nismo na kraju liste,
odnosno da smo nasli broj *)
(* prevezemo listu oko elementa *)
prethodni^.veza:=temp^.veza;
DISPOSE(temp);
RETURN TRUE;
ELSE
RETURN FALSE;
END;
END;
END IzbaciIzListe;
PROCEDURE IzbaciIzListeSve(VAR lista:brojevi;
br: CARDINAL):CARDINAL;
(* izbacuje sve brojeve ’br’ iz liste, naravno ako
postoje i vraca koliko ih je bilo *)
VAR
temp,prethodni:brojevi;
brojac : CARDINAL;
BEGIN
brojac := 0;
(* uklanjamo sa pocetka koliko je potrebno *)
WHILE (lista # NIL) AND (lista^.info = br) DO
temp:=lista;
lista :=lista^.veza;
DISPOSE(temp);
INC(brojac);
END;
(* trazimo u ostatku liste *)
IF (lista # NIL) THEN
temp:=lista;
WHILE (temp^.veza # NIL) DO
(* idemo do poslednjeg elementa liste *)
prethodni:=temp;
temp := temp^.veza;
IF temp^.info = br THEN
(* prevezemo listu oko elementa *)
prethodni^.veza:=temp^.veza;
DISPOSE(temp);
INC(brojac);
(* vracamo se jedan korak da bi
u novom krugu proverili i ovaj element *)
temp := prethodni;
END;
END;
END;
RETURN brojac;
END IzbaciIzListeSve;
(* - procedure sa interakcijom sa korisnikom - *)
PROCEDURE IzbacivanjeEl(VAR lista:brojevi);
(* izbacuje uneti broj iz liste koristeci proceduru IzbaciIzListe *)
VAR
br:CARDINAL;
BEGIN
WriteString("unesite broj za izbacivanje: ");
ReadCard(br);
IF IzbaciIzListe(lista,br) THEN
WriteString("broj je izbacen iz liste");
ELSE
WriteString("greska! - broj ne postoji");
END;
WriteLn;
END IzbacivanjeEl;
PROCEDURE IzbacivanjeElSvi(VAR lista:brojevi);
17
18
(* izbacuje sve primeke unetog broj iz liste
koristeci proceduru IzbaciIzListeSve *)
VAR
br, ukupno:CARDINAL;
BEGIN
WriteString("unesite broj za izbacivanje: ");
ReadCard(br);
ukupno := IzbaciIzListeSve(lista,br);
WriteString("Iz liste je izbaceno ");
WriteCard(ukupno,3);
WriteString(" el.");
WriteLn;
END IzbacivanjeElSvi;
PROCEDURE IzbacivanjeK(VAR lista:brojevi);
(* izbacuje k-ti element iz liste *)
VAR
temp,tekuci:brojevi;
k,brojac:CARDINAL;
BEGIN
IF lista=NIL THEN
WriteString("lista je prazna, nema ");
WriteString("elemenata za izbacivanje");
ELSE
WriteString("unesite redni broj elementa");
WriteString(" koji zelite izbaciti:");
ReadCard(k);
IF k=1 THEN (*izbacivanje prvog *)
temp:=lista;
lista := lista^.veza;
DISPOSE(temp);
ELSE
tekuci := lista;
brojac := 2; (*gledamo jedan unapred*)
WHILE (tekuci^.veza# NIL) AND (k>brojac) DO
(* idemo kroz listu do k-tog el *)
tekuci:=tekuci^.veza;
INC(brojac);
END;
IF (tekuci^.veza#NIL) THEN
(* pamtimo element za brisanje *)
temp:=tekuci^.veza;
(* prevezujemo listu oko njega*)
tekuci^.veza:=tekuci^.veza^.veza;
DISPOSE(temp);
ELSE
WriteString("greska! - ne postoji el ");
WriteString("u listi sa rednim brojem ");
WriteCard(k,2);
END;
WriteLn();
END;
END;
END IzbacivanjeK;
PROCEDURE Pretraga(lista:brojevi);
(* provera da li se uneti broj nalazi u listi *)
VAR
br:CARDINAL;
BEGIN
WriteString("unesite trazeni broj");
ReadCard(br);
IF UListi(lista,br) THEN
WriteString("broj postoji u listi");
ELSE
WriteString("broj ne postoji u listi");
END;
WriteLn;
END Pretraga;
(* -- oslobadjanje memorije -- *)
PROCEDURE Unisti(VAR lista:brojevi);
VAR
temp:brojevi;
BEGIN
Strukture podataka i algoritmi 1 – skripta
4.3
Zadatak: Prikaz operacija nad listama sa jedinstvenim ključem
temp:=lista;
WHILE temp # NIL DO
lista:=lista^.veza;
DISPOSE(temp);
temp:=lista;
END;
END Unisti;
BEGIN
(* pocinjemo od prazne liste *)
lista := NIL;
REPEAT
WriteLn;
WriteString("Ilustracija rada sa");
WriteString(" listama brojeva");
WriteLn;
WriteString("=============================");
WriteLn;
WriteString("s - Stampa");WriteLn;
WriteString("u - Unos");WriteLn;
WriteString("i - Izbacivanje br iz liste");
WriteLn;
WriteString("v - izbacivanje svih br iz liste");
WriteLn;
WriteString("e - izbacivanje k-tog El.");
WriteLn;
WriteString("k - stampanje k-tog elementa");
WriteLn;
WriteString("m - Minimalni broj u listi");
WriteLn;
WriteString("p - Pretraga el. u listi");
WriteLn;
WriteLn;
WriteString("q - kraj rada (Quit)");WriteLn;
REPEAT
menu := CAP(RdKey());
UNTIL menu IN skupZn{’S’,’U’,’E’,’I’,’V’,
’M’,’K’,’P’,’Q’};
IF menu#’Q’ THEN
CASE menu OF
’S’ : Stampaj(lista);|
’U’ : Unos(lista);|
’I’ : IzbacivanjeEl(lista);|
’V’ : IzbacivanjeElSvi(lista);|
’E’ : IzbacivanjeK(lista);|
’K’ : StampajK(lista); |
’M’ : StampajMinimum(lista); |
’P’ : Pretraga(lista);|
END;
WriteLn;
WriteString("--- pritisnite bilo koji ");
WriteString("taster za povratak u meni");
prazno:=RdKey();
ELSE
WriteString("Kraj rada")
END;
WriteLn;
UNTIL menu=’Q’;
Unisti(lista);
END liste2.
4.3
Zadatak: Prikaz operacija nad listama sa jedinstvenim ključem
MODULE Radnici;
FROM InOut IMPORT WriteString, ReadString,
WriteLn, WriteCard, ReadCard, Done;
FROM IO IMPORT RdKey;
FROM Storage IMPORT ALLOCATE, DEALLOCATE;
TYPE
skupZn = SET OF CHAR;
str = ARRAY [1..20] OF CHAR;
radnici = POINTER TO slog;
slog = RECORD
ime, prez : str;
19
20
Strukture podataka i algoritmi 1 – skripta
broj : CARDINAL;
sled : radnici
END;
VAR
meni, pom : CHAR;
rad : radnici;
PROCEDURE Clear();
VAR
br: CARDINAL;
BEGIN
FOR br:=1 TO 100 DO
WriteLn;
END;
END Clear;
PROCEDURE Spisak(rad : radnici);
BEGIN
WHILE rad # NIL DO
WriteString(rad^.ime);
WriteString(’ ’);
WriteString(rad^.prez);
WriteCard(rad^.broj, 8);
WriteLn;
rad := rad^.sled
END
END Spisak;
PROCEDURE Zaposli(VAR rad : radnici);
VAR
novi, tek : radnici;
nadjen : BOOLEAN;
BEGIN
NEW(novi);
REPEAT
WriteString(’Ime, prezime i jedinstveni’);
WriteString(’ broj novog radnika: ’);
WriteLn;
ReadString(novi^.ime);
ReadString(novi^.prez);
ReadCard(novi^.broj);
nadjen := FALSE;
tek := rad;
WHILE NOT nadjen AND (tek # NIL) AND
(tek^.broj <= novi^.broj) DO
IF novi^.broj = tek^.broj THEN
nadjen := TRUE
ELSE
tek := tek^.sled
END
END
UNTIL Done AND NOT nadjen;
IF (rad = NIL) OR (novi^.broj<rad^.broj) THEN
novi^.sled := rad;
rad := novi
ELSE
tek := rad;
WHILE (tek^.sled # NIL) AND
(tek^.sled^.broj < novi^.broj) DO
tek := tek^.sled
END;
novi^.sled := tek^.sled;
tek^.sled := novi
END
END Zaposli;
PROCEDURE Otpusti(VAR rad : radnici);
VAR
tek, pom : radnici;
br : CARDINAL;
BEGIN
REPEAT
WriteLn;
WriteString(’Unesite redni broj radnika:’);
ReadCard(br)
UNTIL Done;
4.3
Zadatak: Prikaz operacija nad listama sa jedinstvenim ključem
WriteLn;
IF rad = NIL THEN
WriteString(’Greska.’)
ELSIF br = rad^.broj THEN
pom := rad;
rad := rad^.sled;
DISPOSE(pom)
ELSE
tek := rad;
WHILE (tek^.sled # NIL) AND
(tek^.sled^.broj < br) DO
tek := tek^.sled
END;
IF (tek^.sled = NIL) OR
(tek^.sled^.broj > br) THEN
WriteString(’Greska.’)
ELSE
pom := tek^.sled;
tek^.sled := tek^.sled^.sled;
DISPOSE(pom)
END
END
END Otpusti;
PROCEDURE Inform(rad : radnici);
VAR
br : CARDINAL;
BEGIN
REPEAT
WriteLn;
WriteString(’Unesite redni broj radnika:’);
ReadCard(br)
UNTIL Done;
WriteLn;
WHILE (rad # NIL) AND (rad^.broj < br) DO
rad := rad^.sled
END;
IF (rad = NIL) OR (rad^.broj # br) THEN
WriteString(’Greska.’)
ELSE
WriteString(rad^.ime);
WriteString(’ ’);
WriteString(rad^.prez)
END
END Inform;
PROCEDURE Bankrot(VAR rad : radnici);
VAR
pom : radnici;
BEGIN
WHILE rad # NIL DO
pom := rad;
rad := rad^.sled;
DISPOSE(pom)
END
END Bankrot;
BEGIN
rad := NIL;
REPEAT
Clear;
WriteString(’s - spisak svih zaposlenih’);
WriteLn;
WriteString(’z - zaposljavanje radnika’);
WriteLn;
WriteString(’o - otpustanje radnika’);
WriteLn;
WriteString(’i - informacije o radniku’);
WriteLn;
WriteString(’b - bankrot firme’);
WriteLn;
WriteString(’k - kraj rada’);
WriteLn;
REPEAT
meni := RdKey();
UNTIL CAP(meni) IN skupZn{’S’, ’Z’, ’O’,
21
22
Strukture podataka i algoritmi 1 – skripta
’I’, ’B’, ’K’};
Clear;
IF CAP(meni) # ’K’ THEN
CASE CAP(meni) OF
’S’ : Spisak(rad)|
’Z’ : Zaposli(rad)|
’O’ : Otpusti(rad)|
’I’ : Inform(rad)|
’B’ : Bankrot(rad)
END;
WriteLn;
WriteString(’-- pritisnite bilo koji ’);
WriteString(’taster za nastavak --’);
pom := RdKey()
END
UNTIL CAP(meni) = ’K’
END Radnici.
Procedura Spisak se može realizovati i u rekurzivnoj verziji:
PROCEDURE Spisak(rad : radnici);
BEGIN
IF rad # NIL THEN
WriteString(rad^.ime);
WriteString(’ ’);
WriteString(rad^.prez);
WriteCard(rad^.broj, 8);
WriteLn;
Spisak(rad^.sled)
END
END Spisak;
4.4
Zadatak: Dve liste osoba koje dele sadržaj, jedna sortirana po visini,
druga po težini
Sa tastature učitavati po dva broja koji opisuju osobu (visina i težina) i smeštati ih u povezane listu,
tako da postoji neopadajuće uređenje i po visini i po težini.
MODULE VisTez;
FROM Storage IMPORT ALLOCATE, DEALLOCATE;
FROM IO IMPORT WrLn, WrStr, RdCard, WrCard;
FROM SYSTEM IMPORT TSIZE;
TYPE
pok = POINTER TO element;
element = RECORD
visina, tezina : CARDINAL;
Vveza, Tveza : pok
END;
VAR
pocV, pocT : pok;
vis, tez : CARDINAL;
PROCEDURE Ispisi(pocV, pocT : pok);
VAR
tek : pok;
BEGIN
tek := pocV;
WrStr(’Po visini:’);
WrLn;
WHILE tek # NIL DO
WrCard(tek^.visina, 6);
tek := tek^.Vveza
END;
WrLn;
tek := pocT;
WrStr(’Po tezini:’);
WrLn;
WHILE tek # NIL DO
WrCard(tek^.tezina,6);
tek := tek^.Tveza
END
END Ispisi;
PROCEDURE Ubaci(VAR pocV, pocT : pok;
vis, tez : CARDINAL);
VAR
novi, tek, iza : pok;
nadjen : BOOLEAN;
4.4
Zadatak: Dve liste osoba sa istim sadržajem
BEGIN
IF pocV = NIL THEN
ALLOCATE(pocV, TSIZE(element));
pocV^.visina := vis;
pocV^.tezina := tez;
pocV^.Vveza := NIL;
pocV^.Tveza := NIL;
pocT := pocV
ELSE
ALLOCATE(novi, TSIZE(element));
novi^.visina := vis;
novi^.tezina := tez;
tek := pocV;
nadjen := FALSE;
WHILE (tek # NIL) AND NOT nadjen DO
nadjen := vis <= tek^.visina;
IF NOT nadjen THEN
iza := tek;
tek := tek^.Vveza
END
END;
novi^.Vveza := tek;
IF tek = pocV THEN
pocV := novi
ELSE
iza^.Vveza := novi
END;
tek := pocT;
nadjen := FALSE;
WHILE (tek # NIL) AND NOT nadjen DO
nadjen := tez <= tek^.tezina;
IF NOT nadjen THEN
iza := tek;
tek := tek^.Tveza
END
END;
novi^.Tveza := tek;
IF tek = pocT THEN
pocT := novi
ELSE
iza^.Tveza := novi
END
END
END Ubaci;
BEGIN
pocV := NIL;
pocT := NIL;
WrStr(’Unesite visinu ---- ’);
vis := RdCard();
WHILE vis > 0 DO
WrStr(’Unesite tezinu ---- ’);
tez := RdCard();
Ubaci(pocV, pocT, vis, tez);
WrLn;
WrStr(’Unesite visinu ---- ’);
vis := RdCard()
END;
WrLn;
Ispisi(pocV, pocT)
END VisTez.
23
24
5
5.1
Strukture podataka i algoritmi 1 – skripta
Polinomi preko listi
Moduli
Polinomi su predstavljeni pomoću pokazivača. Apstraktni tip podataka Polinom je definisan u
globalnom modulu. Redosled parametara kod svih procedura je takav da varijabilni parametri dolaze
na kraju.
PolinomL.DEF
(* Modul za rad sa polinomima preko listi
verzija 2014; rev 1 *)
DEFINITION MODULE PolinomL;
TYPE
Polinom = POINTER TO Monom;
Monom = RECORD
k : REAL;
st : CARDINAL;
veza : Polinom
END;
PROCEDURE
PROCEDURE
PROCEDURE
PROCEDURE
PROCEDURE
PROCEDURE
PROCEDURE
PROCEDURE
PROCEDURE
PROCEDURE
PROCEDURE
PROCEDURE
PROCEDURE
PROCEDURE
PROCEDURE
PROCEDURE
PROCEDURE
Anuliraj(VAR p: Polinom);
Unos(VAR p: Polinom);
Stampaj(p: Polinom; d: CARDINAL);
Kopiraj(p: Polinom;
VAR kopija: Polinom);
PostaviClan(k: REAL; st:CARDINAL;
VAR p:Polinom);
KoeficijentUz(p:Polinom; st:CARDINAL):REAL;
MaksimalniStepen(p:Polinom):CARDINAL;
UbaciMonom(mon:Polinom;
VAR p: Polinom);
PromeniZnak(VAR p: Polinom);
Saberi(p1, p2: Polinom;
VAR zbir: Polinom);
SaberiNa(p: Polinom; VAR rez: Polinom);
Oduzmi(p1,p2: Polinom;
VAR razlika: Polinom);
MonomPuta(p, mon: Polinom;
VAR mp : Polinom);
Puta(p1, p2: Polinom; VAR pr: Polinom);
Kolicnik(p1, p2: Polinom;
VAR kol, ost: Polinom;
VAR ok : BOOLEAN);
PolinomNaN(p: Polinom; n: CARDINAL;
VAR rez: Polinom);
DisposePolinom(VAR p: Polinom);
END PolinomL.
PolinomL.MOD
(* Modul za rad sa polinomima preko listi
verzija 2014; rev 1 *)
IMPLEMENTATION MODULE PolinomL;
FROM InOut IMPORT Write, WriteString, WriteLn,
WriteCard, ReadCard, Done;
FROM RealInOut IMPORT WriteReal, ReadReal;
FROM Storage IMPORT ALLOCATE, DEALLOCATE;
PROCEDURE Anuliraj(VAR p: Polinom);
BEGIN
p := NIL;
END Anuliraj;
PROCEDURE Kopiraj(p: Polinom; VAR kopija: Polinom);
VAR
pomocni: Polinom;
BEGIN
IF p = NIL THEN
kopija := NIL
ELSE
NEW(kopija);
kopija^ := p^;
5.1
Moduli
p := p^.veza;
pomocni := kopija;
WHILE p <> NIL DO
NEW(pomocni^.veza);
pomocni := pomocni^.veza;
pomocni^ := p^;
p := p^.veza
END
END
END Kopiraj;
PROCEDURE Stampaj(p: Polinom; d: CARDINAL);
PROCEDURE StampajMonom(m : Polinom);
BEGIN
WITH m^ DO
IF st <> 0 THEN
IF ABS(k) <> 1.0 THEN
WriteReal(ABS(k), d)
END;
Write(’x’);
IF st <> 1 THEN
Write(’^’);
WriteCard(st, 1)
END
ELSE
WriteReal(ABS(k), d)
END
END
END StampajMonom;
BEGIN
IF p = NIL THEN
WriteReal(0., d)
ELSE
IF p^.k < 0.0 THEN
WriteString(’ - ’)
END;
StampajMonom(p);
p := p^.veza;
WHILE p <> NIL DO
IF p^.k > 0.0 THEN
WriteString(’ + ’)
ELSE
WriteString(’ - ’)
END;
StampajMonom(p);
p := p^.veza
END
END
END Stampaj;
PROCEDURE PostaviClan(k:REAL; st:CARDINAL;
VAR p:Polinom);
VAR
cilj, prethodni : Polinom;
BEGIN
cilj := p;
prethodni := NIL;
WHILE (cilj # NIL) AND (cilj^.st>st) DO
prethodni := cilj;
cilj := cilj^.veza;
END;
(* da li upisujemo vrednost ili sklanjamo clan *)
IF k#0.0 THEN
(* da li menjamo clan ili pravimo novi *)
IF (cilj # NIL) AND (cilj^.st = st) THEN
cilj^.k:=k;
ELSE
NEW(cilj);
cilj^.k := k;
cilj^.st := st;
cilj^.veza := NIL;
IF prethodni = NIL THEN
(* ili je prazan polinom, ili dodajemo na pocetak *)
cilj^.veza := p;
25
26
Strukture podataka i algoritmi 1 – skripta
p := cilj;
ELSE
cilj^.veza := prethodni^.veza;
prethodni^.veza := cilj;
END;
END;
ELSE
(* da li postoji ovakav clan *)
IF (cilj # NIL) AND (cilj^.st = st) THEN
IF p = cilj THEN
p := p^.veza;
ELSE
prethodni^.veza:= prethodni^.veza^.veza;
END;
DISPOSE(cilj);
END;
END;
END PostaviClan;
PROCEDURE KoeficijentUz(p:Polinom; st:CARDINAL):REAL;
VAR
tekuci : Polinom;
BEGIN
tekuci := p;
WHILE (tekuci#NIL) AND (tekuci^.st > st) DO
tekuci := tekuci^.veza;
END;
IF (tekuci # NIL) AND (tekuci^.st = st) THEN
RETURN tekuci^.k;
ELSE
RETURN 0.0;
END;
END KoeficijentUz;
PROCEDURE MaksimalniStepen(p:Polinom):CARDINAL;
BEGIN
IF p#NIL THEN
RETURN p^.st;
ELSE
RETURN 0;
END;
END MaksimalniStepen;
PROCEDURE UbaciMonom(mon:Polinom; VAR p: Polinom);
VAR
stari, tekuci, kopija: Polinom;
BEGIN
IF mon # NIL THEN
NEW(kopija);
kopija^ := mon^;
tekuci := p;
stari := NIL;
WHILE (tekuci#NIL) AND (tekuci^.st>kopija^.st) DO
stari := tekuci;
tekuci := tekuci^.veza
END;
kopija^.veza := tekuci;
IF tekuci = p THEN
p := kopija
ELSE
stari^.veza := kopija
END;
IF (tekuci#NIL) AND (kopija^.st = tekuci^.st) THEN
kopija^.k := kopija^.k + tekuci^.k;
kopija^.veza := tekuci^.veza;
DISPOSE(tekuci);
IF kopija^.k = 0.0 THEN
IF p = kopija THEN
p := kopija^.veza
ELSE
stari^.veza := kopija^.veza
END;
DISPOSE(kopija)
END
END
END
5.1
Moduli
END UbaciMonom;
PROCEDURE Unos(VAR p : Polinom);
VAR
i, n: CARDINAL;
novi: Polinom;
BEGIN
Anuliraj(p);
REPEAT
WriteLn;
WriteString(’Unesite broj monoma n (n>=0) ’);
ReadCard(n);
UNTIL Done;
WriteLn;
FOR i := 1 TO n DO
NEW(novi);
WITH novi^ DO
REPEAT
WriteString(’Unesite koeficijent monoma br.’);
WriteCard(i, 1);
WriteString(’ (<> 0) ’);
ReadReal(k);
WriteLn
UNTIL k <> 0.0;
REPEAT
WriteLn;
WriteString(’Unesite eksponent monoma br.’);
WriteCard(i, 1);
WriteString(’ (>=0) ’);
ReadCard(st);
UNTIL Done;
WriteLn;
END;
UbaciMonom(novi, p);
DISPOSE(novi);
END
END Unos;
PROCEDURE Saberi(p1, p2: Polinom; VAR zbir: Polinom);
BEGIN
Kopiraj(p1, zbir);
WHILE p2 <> NIL DO
UbaciMonom(p2, zbir);
p2 := p2^.veza
END
END Saberi;
PROCEDURE SaberiNa(p: Polinom; VAR rez: Polinom);
BEGIN
WHILE p <> NIL DO
UbaciMonom(p,rez);
p := p^.veza;
END;
END SaberiNa;
PROCEDURE PromeniZnak(VAR p: Polinom);
VAR
t: Polinom;
BEGIN
t := p;
WHILE t <> NIL DO
t^.k := - t^.k;
t := t^.veza
END
END PromeniZnak;
PROCEDURE Oduzmi(p1,p2: Polinom; VAR razlika: Polinom);
BEGIN
Kopiraj(p2, razlika);
PromeniZnak(razlika);
WHILE p1 <> NIL DO
UbaciMonom(p1, razlika);
p1 := p1^.veza
END
END Oduzmi;
27
28
Strukture podataka i algoritmi 1 – skripta
PROCEDURE MonomPuta(p, mon: Polinom; VAR mp: Polinom);
VAR
tekuci: Polinom;
BEGIN
Anuliraj(mp);
IF (mon <> NIL) AND (p <> NIL) THEN
NEW(mp);
mp^.k := p^.k * mon^.k;
mp^.st := p^.st + mon^.st;
p := p^.veza;
tekuci := mp;
WHILE p <> NIL DO
NEW(tekuci^.veza);
tekuci := tekuci^.veza;
tekuci^.k := p^.k * mon^.k;
tekuci^.st := p^.st + mon^.st;
p := p^.veza
END;
tekuci^.veza := NIL
END
END MonomPuta;
PROCEDURE Puta(p1, p2: Polinom; VAR pr: Polinom);
VAR
pomocni, brisi: Polinom;
BEGIN
Anuliraj(pr);
IF (p1 <> NIL) AND (p2 <> NIL) THEN
MonomPuta(p1, p2, pr);
p2 := p2^.veza;
WHILE p2 <> NIL DO
MonomPuta(p1, p2, pomocni);
REPEAT
UbaciMonom(pomocni, pr);
brisi := pomocni;
pomocni := pomocni^.veza;
DISPOSE(brisi);
UNTIL pomocni = NIL;
p2 := p2^.veza
END
END
END Puta;
PROCEDURE Kolicnik(p1, p2: Polinom; VAR kol, ost: Polinom; VAR ok: BOOLEAN);
PROCEDURE Deli(VAR kol, ost: Polinom);
VAR
novi, pomocni: Polinom;
BEGIN
IF ost <> NIL THEN
IF ost^.st >= p2^.st THEN
NEW(novi);
novi^.k := - ost^.k / p2^.k;
novi^.st := ost^.st - p2^.st;
MonomPuta(p2, novi, pomocni);
SaberiNa(pomocni, ost);
DisposePolinom(pomocni);
novi^.k := - novi^.k;
UbaciMonom(novi, kol);
DISPOSE(novi);
Deli(kol, ost)
END
END
END Deli;
BEGIN (* Kolicnik *)
ok := TRUE;
Anuliraj(kol);
IF p2 = NIL THEN
ok := FALSE
ELSE
Kopiraj(p1, ost);
Deli(kol, ost)
END
END Kolicnik;
5.2
Zadatak: Sabiranje sa unapred određenim polinomom
PROCEDURE PolinomNaN(p: Polinom; n: CARDINAL;
VAR rez: Polinom);
VAR
i: CARDINAL;
pret : Polinom;
BEGIN
IF n = 0 THEN
NEW(rez);
rez^.k := 1.0;
rez^.st := 0;
rez^.veza := NIL;
ELSE
Kopiraj( p, rez );
FOR i := 2 TO n DO
pret := rez;
Puta(pret, p, rez);
DisposePolinom(pret);
END
END;
END PolinomNaN;
PROCEDURE DisposePolinom(VAR p: Polinom);
VAR
pomocni: Polinom;
BEGIN
pomocni := p;
WHILE pomocni # NIL DO
p := p^.veza;
DISPOSE(pomocni);
pomocni := p
END
END DisposePolinom;
END PolinomL.
5.2
Zadatak: Sabiranje sa unapred određenim polinomom
Želimo da ispišemo uneti polinom uvećan za
x5 − 3x4 + 4x + 7.
MODULE polinom;
FROM PolinomL IMPORT Polinom, Stampaj, Anuliraj,
DisposePolinom, PostaviClan, Unos, Saberi;
FROM InOut IMPORT WriteString, WriteLn;
VAR
p,q,rez : Polinom;
BEGIN
(* korisnik unosi prvi polinom *)
WriteString("Unesite polinom:");
WriteLn;
Unos(p);
(* drugi polinom kreiramo mi,
monom po monom *)
Anuliraj(q); (* isto sto i q:=NIL; *)
(* postavimo clan x^5 *)
PostaviClan(1.0,5,q);
(* -3 x^4 *)
PostaviClan(-3.0,4,q);
(* 4 x *)
PostaviClan(4.0,1,q);
(* 7 (x^0) *)
PostaviClan(7.0,0,q);
(* saberemo polinome *)
Saberi(p, q, rez);
(* odstampamo rezultat i polinome *)
WriteString("p: ");
Stampaj(p,0);
WriteLn;
WriteString("q: ");
Stampaj(q,0);
WriteLn;
WriteString("rez: ");
Stampaj(rez,0);
29
30
Strukture podataka i algoritmi 1 – skripta
WriteLn;
DisposePolinom(p);
DisposePolinom(q);
DisposePolinom(rez);
END polinom.
5.3
Zadatak: Suma k polinoma
Napisati program koji ucitava broj k (1<=k<=50) i k polinoma, a nakon toga izracunava njihovu
sumu
MODULE PolSuma;
(* Napisati program koji ucitava broj k (1 <= k <= 50) i k polinoma, a nakon toga
izracunava njihovu sumu *)
FROM PolinomL IMPORT Polinom, Anuliraj, DisposePolinom,
Unos, Stampaj, SaberiNa;
FROM InOut IMPORT WriteLn, WriteString, ReadCard, WriteCard;
CONST
maxk = 50;
TYPE
nizPol = ARRAY [1..maxk] OF Polinom;
VAR
i, k: CARDINAL;
suma : Polinom;
p : nizPol;
BEGIN
REPEAT
WriteString(’Unesite broj k (1 <= k <= ’);
WriteCard(maxk, 1);
WriteString(’) ’);
ReadCard(k);
WriteLn;
UNTIL (1 <= k) AND (k <= maxk);
FOR i := 1 TO k DO
WriteLn;
WriteString(’Unos ’);
WriteCard(i, 1);
WriteString(’. polinoma.’);
WriteLn;
Unos(p[i])
END;
Anuliraj(suma);
FOR i := 1 TO k DO
SaberiNa(p[i], suma)
END;
WriteLn;
WriteString(’Njihova suma je:’);
WriteLn;
Stampaj(suma, 4);
DisposePolinom(suma);
FOR i := 1 TO k DO
DisposePolinom(p[i]);
END;
END PolSuma.
6 Stek i red opsluživanja
6
6.1
Stek i red opsluživanja
Primer: osnovno korišćenje steka i reda opsluživanja
MODULE stekred;
(* prvo importujemo cele module, da bi mogli da koristimo istoimene
procedure (kao MakeNull) iz oba modula *)
IMPORT RedOpsl;
IMPORT Stek;
(* nakon toga importujemo i sve raznoimene delove, da ne bi morali
da kucamo puna imena modula svaki put i kad ne moramo *)
FROM Stek IMPORT StekTip, Top, Pop, Push;
FROM RedOpsl IMPORT RedOpslTip, First, PopFirst, AddRear;
FROM InOut IMPORT ReadString,WriteString,Write,WriteLn;
FROM Strings IMPORT Length;
VAR
str : ARRAY[1..256] OF CHAR;
q :RedOpslTip;
s :StekTip;
i : CARDINAL;
ok,palin : BOOLEAN;
c,c1 : CHAR;
BEGIN
WriteString("unesite string: ");
ReadString(str);
(* inicijalizujemo strukture *)
Stek.MakeNull(s);
RedOpsl.MakeNull(q);
(* ubacujemo elemente u stek *)
FOR i:=1 TO Length(str) DO
Push(s, str[i], ok);
END;
(* ubacujemo elemente u red opsl *)
FOR i:=1 TO Length(str) DO
AddRear(q, str[i], ok);
END;
WriteLn;
WriteString("sadrzaj steka");
WriteLn;
WHILE NOT Stek.Empty(s) DO
Top(s,c,ok);
Pop(s,ok);
Write(c);
END;
WriteLn;
WriteString("sadrzaj reda opsl.");
WriteLn;
WHILE NOT RedOpsl.Empty(q) DO
First(q,c,ok);
PopFirst(q,ok);
Write(c);
END;
WriteLn;
END stekred.
6.2
Zadatak: Ilustracija pisanja u fajl uz pomoć bafera
DEFINITION MODULE QueueInfo;
CONST
Maxqueue = 100;
TYPE
InfoTip = CHAR;
END QueueInfo.
IMPLEMENTATION MODULE QueueInfo;
END QueueInfo.
DEFINITION MODULE RedOpsl1;
FROM QueueInfo IMPORT InfoTip,Maxqueue;
TYPE
Niz = ARRAY[1..Maxqueue] OF InfoTip;
RedOpslTip = RECORD
31
32
Strukture podataka i algoritmi 1 – skripta
Prvi, Zadnji : CARDINAL;
Element : Niz
END;
PROCEDURE MakeNull(VAR q : RedOpslTip);
PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
PROCEDURE First(VAR q : RedOpslTip;
VAR x : InfoTip;
VAR ok : BOOLEAN);
PROCEDURE PopFirst(VAR q : RedOpslTip;
VAR ok : BOOLEAN);
PROCEDURE AddRear(VAR q : RedOpslTip;
x : InfoTip;
VAR ok : BOOLEAN);
END RedOpsl1.
IMPLEMENTATION MODULE RedOpsl1;
FROM QueueInfo IMPORT Maxqueue,InfoTip;
PROCEDURE MakeNull(VAR q : RedOpslTip);
BEGIN
WITH q DO
Prvi := 0;
Zadnji := 0
END
END MakeNull;
PROCEDURE Empty(VAR q : RedOpslTip) : BOOLEAN;
BEGIN
RETURN q.Zadnji = 0
END Empty;
PROCEDURE First(VAR q : RedOpslTip;
VAR x : InfoTip;
VAR ok : BOOLEAN);
BEGIN
IF Empty(q) THEN
ok := FALSE
ELSE
ok := TRUE;
WITH q DO
x := Element[Prvi]
END
END
END First;
PROCEDURE AddOne(i : CARDINAL) : CARDINAL;
BEGIN
IF i = Maxqueue THEN
RETURN 1
ELSE
RETURN i+1
END
END AddOne;
PROCEDURE PopFirst(VAR q : RedOpslTip;
VAR ok : BOOLEAN);
BEGIN
IF Empty(q) THEN
ok := FALSE
ELSE
ok := TRUE;
WITH q DO
IF Prvi = Zadnji THEN
MakeNull(q)
ELSE
Prvi := AddOne(Prvi)
END
END
END
END PopFirst;
PROCEDURE AddRear(VAR q : RedOpslTip;
x : InfoTip;
6.2
Zadatak: Ilustracija pisanja u fajl uz pomoć bafera
VAR ok : BOOLEAN);
BEGIN
WITH q DO
IF AddOne(Zadnji) = Prvi THEN
ok := FALSE
ELSE
ok := TRUE;
IF Empty(q) THEN
Prvi := 1;
Zadnji := 1
ELSE
Zadnji := AddOne(Zadnji)
END;
Element[Zadnji] := x
END
END
END AddRear;
END RedOpsl1.
MODULE Bafer;
FROM RedOpsl1 IMPORT RedOpslTip, MakeNull, Empty, First, PopFirst, AddRear;
FROM FIO IMPORT File,WrChar, Create, Close;
IMPORT IO;
CONST
ImeIzlaza = ’izlaz.txt’;
VAR
izlaz : File;
znak : CHAR;
buffer : RedOpslTip;
PROCEDURE IsprazniBafer(VAR dat : File;
VAR buf : RedOpslTip);
VAR
znak : CHAR;
ok : BOOLEAN;
BEGIN
WHILE NOT Empty(buf) DO
First(buf, znak, ok);
PopFirst(buf, ok);
WrChar(dat, znak)
END
END IsprazniBafer;
PROCEDURE BaferWrite(VAR dat : File;
VAR buf : RedOpslTip;
znak : CHAR);
VAR
ok : BOOLEAN;
BEGIN
AddRear(buf, znak, ok);
IF NOT ok THEN
IsprazniBafer(dat, buf);
AddRear(buf, znak, ok)
END
END BaferWrite;
BEGIN
izlaz := Create(ImeIzlaza);
MakeNull(buffer);
IO.WrStr(’Unesite tekst, koji treba da se unese u datoteku ’);
IO.WrStr(ImeIzlaza);
IO.WrChar(’.’);
IO.WrLn;
IO.WrStr(’Unos zavrsite tackom.’);
IO.WrLn;
znak := IO.RdChar();
WHILE znak # ’.’ DO
BaferWrite(izlaz, buffer, znak);
znak := IO.RdChar();
END;
IsprazniBafer(izlaz, buffer);
Close(izlaz)
END Bafer.
33
34
6.3
Strukture podataka i algoritmi 1 – skripta
Zadatak: Ispitivanje da li reč pripada gramatici wcw+
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.
DEFINITION MODULE Stek;
CONST
Maxstack = 100;
TYPE
Niz = ARRAY [1..Maxstack] OF CHAR;
StekTip = RECORD
Top : CARDINAL;
Element : Niz
END;
PROCEDURE MakeNull(VAR s : StekTip);
PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
PROCEDURE Top(VAR s : StekTip;
VAR x : CHAR;
VAR ok : BOOLEAN);
PROCEDURE Pop(VAR s : StekTip;
VAR ok : BOOLEAN);
PROCEDURE Push(VAR s : StekTip;
x : CHAR;
VAR ok : BOOLEAN);
END Stek.
IMPLEMENTATION MODULE Stek;
PROCEDURE MakeNull(VAR s : StekTip);
BEGIN
s.Top := 0
END MakeNull;
PROCEDURE Empty(VAR s : StekTip) : BOOLEAN;
BEGIN
RETURN s.Top = 0
END Empty;
PROCEDURE Top(VAR s : StekTip;
VAR x : CHAR;
VAR ok : BOOLEAN);
BEGIN
IF Empty(s) THEN
ok := FALSE
ELSE
ok := TRUE;
WITH s DO
x := Element[Top]
END
END
END Top;
PROCEDURE Pop(VAR s : StekTip;
VAR ok : BOOLEAN);
BEGIN
IF Empty(s) THEN
ok := FALSE
ELSE
ok := TRUE;
DEC(s.Top)
END
END Pop;
PROCEDURE Push(VAR s : StekTip;
x : CHAR;
VAR ok : BOOLEAN);
BEGIN
WITH s DO
IF Top = Maxstack THEN
ok := FALSE
ELSE
ok := TRUE;
INC(Top);
Element[Top] := x
END
6.3
Zadatak: Ispitivanje da li reč pripada gramatici wcw+
END
END Push;
END Stek.
MODULE wcw;
(* Da li rec pripada gramatici wcw+. *)
FROM Stek IMPORT StekTip, MakeNull, Empty,
Top, Pop, Push;
FROM InOut IMPORT Read, Write, WriteString, EOL;
TYPE
slova = SET OF CHAR;
VAR
S : StekTip;
Ch, C : CHAR;
ok : BOOLEAN;
BEGIN
MakeNull(S);
Read(Ch);
ok := TRUE;
WHILE ok AND (Ch IN slova{’a’, ’b’}) DO
Push(S, Ch, ok);
Read(Ch);
END;
IF NOT ok THEN
WriteString(’Greska - mali stek’)
ELSIF Ch # ’c’ THEN
WriteString(’Pogresan string’)
ELSE
Read(Ch);
WHILE ok AND (Ch # EOL) DO
Top(S, C, ok);
ok := ok AND (C = Ch);
IF ok THEN
Pop(S, ok);
Read(Ch);
END
END;
IF NOT (ok AND Empty(S)) THEN
WriteString(’Pogresan string’)
ELSE
WriteString(’String pripada jeziku L’)
END
END
END wcw.
35
36
6.4
Strukture podataka i algoritmi 1 – skripta
Zadatak: Kalkulator za izračunavanje postfiksnih izraza
Napraviti kalkulator za izračunavanje postfiksnih izraza. Svi brojevi koji figurišu u izrazu su jednocifreni.
MODULE PostFix;
FROM StekI IMPORT StekTip, MakeNull, Empty, Top, Pop, Push;
FROM InOut IMPORT Read, Write, WriteInt, EOL;
TYPE
slova = SET OF CHAR;
VAR
S : StekTip;
Ch : CHAR;
Op1, Op2 : INTEGER;
ok : BOOLEAN;
PROCEDURE Conv(Ch : CHAR) : INTEGER;
BEGIN
RETURN ORD(Ch) - ORD(’0’)
END Conv;
BEGIN
MakeNull(S);
Read(Ch);
WHILE Ch # EOL DO
IF Ch IN slova{’+’, ’-’, ’/’, ’*’, ’%’} THEN
Top(S, Op2, ok);
Pop(S, ok);
Top(S, Op1, ok);
Pop(S, ok);
CASE Ch OF
’+’ : Op1 := Op1 + Op2 |
’-’ : Op1 := Op1 - Op2 |
’*’ : Op1 := Op1 * Op2 |
’/’ : Op1 := Op1 DIV Op2 |
’%’ : Op1 := Op1 MOD Op2
END;
Push(S, Op1, ok)
ELSE
Push(S, Conv(Ch), ok)
END;
Read(Ch);
END;
Top(S, Op1, ok);
Write(’=’);
WriteInt(Op1,5)
END PostFix.
7 Simulacija rekurzije
7
37
Simulacija rekurzije
Na početku označiti sve rekurzivne pozive u originalnoj proceduri adresama (npr. 1,2,3... ili konstante nabrojivog tipa podataka).
Na steku se čuvaju lokalne promenljive, parametri procedure i adresa mesta poziva, a u skladu sa
tim se kreira InfoTip.
Trivijalnim pozivom se smatra onaj koji se izračunava bez dodatnih rekurzivnih poziva.
U kodu ispod, treba_rekurzija znači da je poziv netrivijalan, odnosno treba naći uslove pod
kojima se sigurno dešavaju rekurzivni pozivi.
MakeNull(S);
REPEAT
WHILE treba_rekurzija DO
-prepisati sve od pocetka originalne
procedure do prvog rekurzivnog poziva
-staviti na stek potrebne
lokalne promenljive, parametre procedure i
adresu mesta poziva
-podesiti vrednosti parametara da budu
kao u rekurzivnom pozivu procedure
END;
trivijalan poziv
umesto RETURN x pisati rez := x
jos := TRUE;
WHILE jos AND NOT Empty(S) DO
Top(S, el, ok);
Pop(S, ok);
-restauriramo vrednosti sa steka
-u zavisnosti od adrese poziva nastavimo
prepisivanje originalne procedure sa
tog mesta
-ako se dodje do novog rek. poziva tada:
-sacuvati na steku vrednosti
-podesiti vrednosti parametara da budu
kao u rekurzivnom pozivu procedure
-ici na pocetak koda
(ovo se postize sa jos := FALSE)
-inace
ako se naidje na RETURN x pisati rez := x
END
UNTIL Empty(S);
Ako je procedura funkcijska tada se na kraj dodaje RETURN rez.
ZADACI
Simulirati ponašanje sledećih rekurzivnih procedura (funkcija) upotrebom steka:
7.1
Primer 1 – faktorijel
MODULE Fakto;
(* InfoTip = CARDINAL; *)
FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
FROM StekC IMPORT StekTip, MakeNull, Empty,
Top, Pop, Push;
VAR
n : CARDINAL;
PROCEDURE RFakto(n : CARDINAL) : CARDINAL;
BEGIN
IF n <= 1 THEN
RETURN 1
ELSE
RETURN n * RFakto(n-1)
END
END RFakto;
PROCEDURE SFakto(n : CARDINAL) : CARDINAL;
VAR
s : StekTip;
rez : CARDINAL;
OK : BOOLEAN;
38
Strukture podataka i algoritmi 1 – skripta
BEGIN
MakeNull(s);
WHILE n > 1 DO
Push(s,n,OK);
DEC(n)
END;
rez := 1;
WHILE NOT Empty(s) DO
Top(s, n, OK);
Pop(s, OK);
rez := n * rez
END;
RETURN rez
END SFakto;
BEGIN
WrStr(’n = ’);
n := RdCard();
WrLn
WrStr(’n! = ’);
WrCard(RFakto(n), 1);
WrStr(’ = ’);
WrCard(SFakto(n), 1)
END Fakto.
7.2
Primer 2 – stepenovanje
MODULE Step;
(* InfoTip = RECORD
x : REAL;
n : CARDINAL;
adr : (par, nepar)
END;
*)
FROM IO IMPORT WrStr, WrLn, WrReal,
RdReal, RdCard;
FROM StekStep IMPORT StekTip, MakeNull, Empty,
Top, Pop, Push, InfoTip, AdrTip;
VAR
n : CARDINAL;
x : REAL;
PROCEDURE Sqr(y : REAL) : REAL;
BEGIN
RETURN y * y
END Sqr;
PROCEDURE RStep(x : REAL;
n : CARDINAL) : REAL;
BEGIN
IF n = 0 THEN
RETURN 1.
ELSIF ODD(n) THEN
RETURN x * Sqr( RStep(x, n DIV 2) )
ELSE
RETURN Sqr( RStep(x, n DIV 2) )
END
END RStep;
PROCEDURE SStep(x : REAL;
n : CARDINAL ) : REAL;
VAR
s : StekTip;
OK : BOOLEAN;
rez : REAL;
el : InfoTip;
BEGIN
MakeNull(s);
WHILE n > 0 DO
el.x := x;
el.n := n;
IF ODD(n) THEN
el.adr := nepar;
ELSE
el.adr := par
END;
7.3
Primer 3 – Fibonači
Push(s,el,OK);
n := n DIV 2
END;
rez := 1.;
WHILE NOT Empty(s) DO
Top(s, el, OK);
Pop(s, OK);
x := el.x;
n := el.n;
IF el.adr = nepar THEN
rez := x * Sqr(rez)
ELSE
rez := Sqr(rez)
END
END;
RETURN rez
END SStep;
BEGIN
WrStr(’x =? ’);
x := RdReal();
WrLn;
WrStr(’n =? ’);
n := RdCard();
WrStr(’x^n = ’);
WrReal(RStep(x, n), 10, 1);
WrStr(’ = ’);
WrReal(SStep(x, n), 10, 1)
END Step.
7.3
Primer 3 – Fibonači
MODULE Fib;
(* InfoTip = RECORD
n : CARDINAL;
PrviSab : CARDINAL;
adr : (prvi, drugi)
END;
*)
FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
FROM StekFib IMPORT StekTip, MakeNull, Empty,
Top, Pop, Push, InfoTip, AdrTip;
VAR
n : CARDINAL;
PROCEDURE RFib(n : CARDINAL) : CARDINAL;
BEGIN
IF n <= 1 THEN
RETURN n
ELSE
RETURN RFib(n-1) + RFib(n-2)
END
END RFib;
PROCEDURE SFib(n : CARDINAL ) : CARDINAL;
VAR
s : StekTip;
OK, jos : BOOLEAN;
rez, PrviSab : CARDINAL;
el : InfoTip;
BEGIN
MakeNull(s);
REPEAT
WHILE n > 1 DO
el.n := n;
el.adr := prvi;
Push(s,el,OK);
DEC(n)
END;
rez := (n);
jos := TRUE;
WHILE (NOT Empty(s)) AND jos DO
Top(s, el, OK);
Pop(s, OK);
n := el.n;
39
40
Strukture podataka i algoritmi 1 – skripta
IF el.adr = prvi THEN
PrviSab := rez;
el.n := n;
el.adr := drugi;
el.PrviSab := PrviSab;
Push(s, el, OK);
DEC(n, 2);
jos := FALSE
ELSE
PrviSab := el.PrviSab;
rez := PrviSab + rez
END
END
UNTIL Empty(s);
RETURN rez
END SFib;
BEGIN
WrStr(’n =? ’);
n := RdCard();
WrStr(’F(n) = ’);
WrCard(RFib(n), 1);
WrStr(’ = ’);
WrCard(SFib(n), 1)
END Fib.
7.4
Primer 4 – faktorijel 2
MODULE Faktor;
(* InfoTip = CARDINAL; *)
FROM IO IMPORT WrStr, WrLn, WrCard, RdCard;
FROM StekC IMPORT StekTip, MakeNull, Empty,
Top, Pop, Push;
VAR
n,rez : CARDINAL;
PROCEDURE RFakto(n : CARDINAL;
VAR rez : CARDINAL);
BEGIN
IF n = 0 THEN
rez := 1
ELSE
RFakto(n-1, rez);
rez := n * rez
END
END RFakto;
PROCEDURE SFakto(n : CARDINAL;
VAR rez : CARDINAL);
VAR
s : StekTip;
OK : BOOLEAN;
BEGIN
MakeNull(s);
WHILE n > 0 DO
Push(s,n,OK);
DEC(n)
END;
rez := 1;
WHILE NOT Empty(s) DO
Top(s, n, OK);
Pop(s, OK);
rez := n * rez
END
END SFakto;
BEGIN
WrStr(’n =? ’);
n := RdCard();
WrLn;
WrStr(’n! = ’);
RFakto(n, rez);
WrCard(rez, 1);
WrStr(’ = ’);
SFakto(n, rez);
WrCard(rez, 1)
7.5
Primer 5 (ispitni)
END Faktor.
7.5
Primer 5 (ispitni)
MODULE Rek1;
(* InfoTip = RECORD
d, g, m1, m2 : INTEGER;
adr : (prvi, drugi)
END;
*)
FROM Stek1 IMPORT StekTip, adresa, InfoTip,
MakeNull, Empty, Top, Pop, Push;
IMPORT IO;
VAR
X : ARRAY [1..20] OF INTEGER;
PROCEDURE Max(d, g: INTEGER) : INTEGER;
VAR
m1, m2 : INTEGER;
BEGIN
IF d>g THEN
RETURN MIN(INTEGER)
ELSIF d=g THEN
RETURN X[d]
ELSE
m1 := Max(d, (d+g) DIV 2);
m2 := Max((d+g) DIV 2 +1, g);
IF m1 > m2 THEN
RETURN m1
ELSE
RETURN m2
END
END
END Max;
PROCEDURE SMax(d, g: INTEGER) : INTEGER;
VAR
S : StekTip;
el : InfoTip;
ok, jos : BOOLEAN;
m1, m2, rez : INTEGER;
BEGIN
MakeNull(S);
REPEAT
WHILE d<g DO
el.d := d;
el.g := g;
el.adr := prvi;
Push(S, el, ok);
g := (d+g) DIV 2
END;
IF d>g THEN
rez := MIN(INTEGER)
ELSE (* d=g *)
rez := X[d]
END;
jos := TRUE;
WHILE jos AND NOT Empty(S) DO
Top(S, el, ok);
Pop(S, ok);
d := el.d;
g := el.g;
m1 := el.m1;
IF el.adr = prvi THEN
m1 := rez;
el.m1 := m1;
el.adr := drugi;
Push(S, el, ok);
d := (d+g) DIV 2 + 1;
jos := FALSE
ELSE (*el.adr = drugi*)
m2 := rez;
IF m1 > m2 THEN
rez := m1
ELSE
rez := m2
41
42
Strukture podataka i algoritmi 1 – skripta
END
END
END
UNTIL Empty(S);
RETURN rez
END SMax;
BEGIN (* glavni program *)
X[1] := 3;
X[2] := 2;
X[3] := 5;
X[4] := -7;
X[5] := 0;
IO.WrCard(Max(1, 5), 3);
IO.WrLn;
IO.WrCard(SMax(1, 5), 3);
IO.WrLn
END Rek1.
7.6
Primer 6 (ispitni)
MODULE Rek2;
(* InfoTip = RECORD
x, y, n : CARDINAL;
adr : (prvi, drugi, treci, cetvrti)
END;
*)
FROM Stek2 IMPORT StekTip, adresa, InfoTip,
MakeNull, Empty, Top, Pop, Push;
IMPORT IO;
PROCEDURE g(x : CARDINAL; y : CARDINAL;
n : CARDINAL) : CARDINAL;
BEGIN
IF n < 3 THEN
RETURN x + y
ELSIF ODD(n) THEN
RETURN g(g(x+1, y, n-2), y, n-3)
ELSE
RETURN g(x, g(x, y+1, n-2), n-3)
END
END g;
PROCEDURE Sg(x : CARDINAL; y : CARDINAL;
n : CARDINAL) : CARDINAL;
VAR
S : StekTip;
el : InfoTip;
ok, jos : BOOLEAN;
rez : CARDINAL;
BEGIN
MakeNull(S);
REPEAT
WHILE n >= 3 DO
IF ODD(n) THEN
el.x := x;
el.y := y;
el.n := n;
el.adr := prvi;
Push(S, el, ok);
INC(x);
DEC(n, 2)
ELSE
el.x := x;
el.y := y;
el.n := n;
el.adr := treci;
Push(S, el, ok);
INC(y);
DEC(n, 2)
END
END;
rez := x+y;
jos := TRUE;
WHILE jos AND NOT Empty(S) DO
Top(S, el, ok);
7.6
Primer 6 (ispitni)
Pop(S, ok);
x := el.x;
y := el.y;
n := el.n;
IF el.adr = prvi THEN
el.adr := drugi;
Push(S, el, ok);
x := rez;
DEC(n, 3);
jos := FALSE
ELSIF el.adr = treci THEN
el.adr := cetvrti;
Push(S, el, ok);
y := rez;
DEC(n, 3);
jos := FALSE
END
END
UNTIL Empty(S);
RETURN rez
END Sg;
BEGIN (* glavni program *)
IO.WrCard(g(2, 3, 10), 3);
IO.WrCard(Sg(2, 3, 10), 3);
END Rek2.
43
A Native XDS Modula 2 – kratko uputstvo
A
I
Native XDS Modula 2 – kratko uputstvo
Ovo uputstvo ukratko pokriva kako se može nabaviti XDS Modula 2 za Windows sistem, njenu
instalaciju, te kako napraviti i pokretnuti jednostavan program.
Dobavljanje instalacije
Native XDS Modula 2 se može besplatno skinuti sa sajta proizvođača, tačnije na adresi:
http://www.excelsior-usa.com/xdsdl.html
Prvo se prikazuje ugovor o korišćenju koji na dnu treba potvrditi da ste razumeli i da ćete ga se
pridržavati.
Na stranici koja se potom otvara je potrebno odabrati “XDS 2.6 beta 2 for Windows” i snimiti je
na računar.
Instalacija okruženja
Osnovno okruženje (xds-x86...) se instalira pokretanjem prethodno pomenute instalacione arhive.
Korisnicima Windows-a 7 preporučujemo da pokrenu instalacione pakete pomoću opcije “Run as
administrator” do koje se stiže desnim klikom miša.
Pretpostavićemo u daljem tekstu da je program instaliran u C:/XDS/
Pokretanje okruženja
Po uspešnoj instalaciji bi trebalo da postoji ikonica na desktopu, kao i grupa sa programom u start
meniju.
Ukoliko iz bilo kakvog razloga ne postoje odgovarajuće prečice, okruženje se može pokrenuti uz
pomoć izvršnog fajla C:/XDS/BIN/xds.exe (ako je instalirano na podrazumevanoj lokaciji).
Prvi projekat
Da bismo mogli da pišemo i pokrećemo svoj program, potrebno je prvo napraviti projekat za njega,
što se radi na sledeći način:
• Iz menija se odabere Project->New.
• U dijalogu se klikne na gornje dugme “Browse”, odabere se putanja gde će se kreirati projekat i
ukuca se ime novog projekta.
• U drugom polju “Template” ne treba da piše ništa. Ukoliko postoji neki tekst, obrisati ga.
• Kliknuti na “OK”
• Iskočiće dijalog na kome piše da ne postoji fajl za editovanje, kliknuti na “OK” da se on napravi.
• Pojavljuje se forma za kucanje programa, ukucati (na primer):
MODULE Hello;
FROM InOut IMPORT WriteString,WriteLn;
BEGIN
WriteString("Hello World");
WriteLn;
END Hello.
• Program se može pokrenuti na različite načine, pri čemu se automatski prevodi:
– Klik na “Run” ikonicu u toolbaru (plavi čovečuljak koji trči)
– Meni Debug->Run
– Prečica Ctrl+F9 na tastaturi
• Ako je sve u redu sa programom, treba da se pojavi novi terminal u kome se ispisuje rezultat
izvršavanja programa, u našem slučaju jednostavna pozdravna poruka.
Naravno moguće je i samo prevesti (kompajlirati) program, tako da se samo prikažu greške (ako ih
ima) i bez pokretanja programa:
• Klik na “Compile” ikonicu u toolbaru
• Meni Tools->Compile
• Prečica F9 na tastaturi
II
Strukture podataka i algoritmi 1 – skripta
Ukoliko u programu postoje greške, on neće biti pokrenut, već će se dobiti lista grešaka u donjem
delu prozora. Na primer ako obrišemo “S” u četvrtom redu i probamo da pokrenemo program, taj red
će biti označen svetlo plavom bojom i dobićemo poruku:
- Error in pro1.mod [4:5]:
Undeclared identifier "Writeting"
Što znači da u četvrtom redu, kod petog karatkera postoji problem, da identifikator nije deklarisan,
što najčešće znači da ga nismo uvezli, ili, kao u našem slučaju, da smo napravili grešku u kucanju.
Stvar na koju isto treba obratiti pažnju je da se nekad greška prijavljue nešto kasnije u tekstu
nego što je napravljena. Na primer, ako obrišemo “;” na kraju četvrtog reda i probamo da pokrenemo
program, peti red će biti označen svetlo plavom bojom i dobićemo poruku:
- Error in pro1.mod [5:5]:
Expected symbol ";"
Ovo se desilo jer nedostaje tačka zarez na kraju četvrtog reda, ali će kompajler probati da je traži i
dalje, pa će tek na početku petog reda prijaviti grešku.
U spisku se takođe pojavljuje i upozorenje (Warning) o tome da se uvezena komanda WriteString
ne koristi nigde u programu. Često se upozorenja mogu ignorisati, a pažnju uglavnom treba obraćati
na greške, odnosno poruke koje počinju sa “Error”.
Takođe se često dešava da su druge prijavljene greške posledica prve, te je poželjno ponovo kompajlirati (ili pokretati) program posle svake ispravljene greške.
Napomena o template-ovima pri kreiranju projekta: Moguće je namestiti da u dijalogu za novi
projekat drugo polje “Template” uvek bude prazno. Potrebno je u tom istom dijalogu kliknuti na
“Configure”, a potom isprazniti polje “default template”.
A.1
Mogući problemi
Nedostajući sistemski moduli
Verzije pre 2.6 nisu imale uključene u glavni paket sve module koji se koriste u okviru kursa, i bilo
je neophodno da se dodatno instalira i “Top Speed Compatibility Pack” (tscp-x86...). Bez njega je
kompajler prijavljivao da ne postoje neki moduli - najčešće je problem bio da nedostaje FIO modul.
Problemi u pokretanju - nemoguće naći exe
Ako pri pokušaju kompajliranja/pokretanja programa kompajler prijavi da ne može da nađe exe
i pri tome prijavljuje kraću putanju od one koja je stvarno u pitanju, obično se radi o tome da je
postojao razmak u okviru putanje do modula. Npr “C:\Moj prvi program” će prouzrokovati probleme,
a kompajler će prijaviti da ne može da nađe “C:\Moj”.
Ovo je nažalost problem okruženja i dok se ne ispravi u nekoj budućoj verziji ne može se zaobići,
tako da je jedino rešenje premestiti fajlove, odnosno ako je moguće preimenovati problematične foldere.
B XDS modula 2 - rad iz komandne linije
B
III
XDS modula 2 - rad iz komandne linije
Ovo uputstvu ukratko pokriva kako se XDS kompajler može podesiti da se koristi iz komandne linije,
na Windows, ali i *nix sistemima.
Predpostavlja se da je XDS Modula 2 već instalirana (konsultovati odvojeno uputstvo ako nije).
Takođe će se predpostavljati da je instalirana na podrazumevanu lokaciju “c:/xds/”. Ako to nije slučaj,
potrebno je zameniti putanje iz upustva sa stvarnom putanjom.
B.1
Prednosti (ili “Zašto ovo raditi?”)
Skoro svaki jezik se može kompajlirati iz komandne linije, i onda se rad sa različitim jezicima svodi
na rad u svom omiljenom editoru teksta (npr Notepad++, jEdit, joe, emacs...), koji je prilagođen
sopstvenim zahtevima i pozivanjem odgovarajućeg kompajlera iz komandne linije.
U konkretnom slučaju XDS kompajlera, ovim se takođe oslobađa potrebe kreiranja projekata koji
su neophodni kad se koristi XDS windows okruženje - bilo koji pojedinačni modul se može direktno
kompajlirati, fajlovi se mogu premeštati po folderima, menjati imena foldera i tako dalje.
Još jedna prednost za studente PMF-a koji polažu ispite u okruženju Svetovid je što u njemu dobijaju
potpuno iste poruke od kompajlera kao što se dobijaju izvršavanjem kompajliranja iz komandne linije.
B.2
Podešavanje sistemske putanje (ili "OK, odakle početi?")
Da bi kompajler mogao da se poziva iz bilo kog foldera na računaru, a ne samo iz “C:/xds/bin”,
potrebno je dodati folder kompajlera u sistemsku putanju (tj spisak foldera koji se pretražuju kada
korisnik pokuša da pokrene neku komandu). Na Windows sistemima se ova promenljiva naziva “PATH”,
a trenutnom sadržaju se može pristupiti preko %PATH%.
Putanja se može dodati privremeno komandom:
path = %PATH%;c:/xds/bin
ovim se proširuje spisak putanja u trenutom komandom prozoru, odnosno važiće samo u trenutno
otvorenom cmd promptu i to dok se isti ne zatvori.
Putanja se može i trajno dodati na nekoliko načina. Na win xp, Vista i 7 sistemima se to može uraditi
na sledeći način: otvori se “computer properties” (desni klik na "My Computer"), odabere se jezičak
"advanced", klikne na dugme "Environment variables", u prozoru koji se otvori odabere se “PATH” i
klikne na dugme "edit", nakon čega se na postojeću vrednost doda “c:\xds\bin”. Bitno je da se ne
obriše postojeća vrednost, kao i da se novi dodatak odvoji sa “;” od postojećih.
B.3
Kompajliranje programa
Nakon što je podešena sistemska putanja, kompajleru se pristupa komandom "xc". Poziv bez
parametara će dati ispis mogućnosti. Tipična upotreba za kreiranje izvršne verzije programa sadržanu
u fajlu "ime.MOD":
xc =make =all ime
Ovim pozivom će se rekompajlirati i svi ostali potrebni moduli koji se koriste u okviru programa.
Ako postoje greške u programu izvršna verzija neće biti kreirana. Ako već postoji exe napravljen
nekim prethodnim kompajliranjem, on NEĆE biti obrisan.
Kompajler greške prijavljuje u sledećem formatu:
* [zad.mod 125.12 E020] * undeclared identifier "RStr" IO.$RStr(ime);
Odnosno ime fajla, red greške i kolona razdvojeni tačkom i kod greške koji počinje sa “E”. Sam kod
greške nije previše bitan, pošto u sledećem redu sledi objašnjenje. Ono što jeste bitno je da se u istom
formatu prikazuju i upozorenja kompajlera čiji kodovi počinu sa “W” i po ovome se najlakše razlikuju.
Takođe treba obratiti pažnju na to da nakon objašnjenja greške sledi i ispis samog reda u kome je
greška u koji je dodatno ubačen karakter “$” koji označava tačno nesto greške. Ako se on nalazi na
početku reda često je u pitanju greška iz prethodnog reda (npr nedostaje “;”). Konkretna prikazana
greška je pogrešno napisano “RdStr”.
B.4
Linux i drugi slobodni sistemi (ili "Who needs windows anyway?")
Korisnici Linux (i srodnih) sistema takođe mogu koristiti XDS Modulu 2, i to i okruženje i kompajler
iz komandne linije.
IV
Strukture podataka i algoritmi 1 – skripta
Prvo rešenje je korišćenje Linux verzije XDS kompajlera. Međutim ona se ponaša malo drugačije,
nema vizuelno okruženje i, što je najznačajnije za studente PMFa, nema Top Speed Compatibility Pack
koji se koristi na vežbama.
Ono što je najbolje rešenje u ovoj situaciji je koriščenje sloja za emuliranje Windowsa - "Wine".
Potrebno je pokrenuti instalaciju XDS paketa, isto kao i pod windowsom (ili alternativno preuziti
strukturu foldera iz windowsa i prekopirati u Wine-ov “C” disk).
Ovako instaliran XDS se može koristiti i kao normalno programsko okruženje koje se koristi pod
Windowsom.
Ono što je inače bila poenta ovog uputsva u celini je bilo korišćenje iz komandne linije.
Da bi kompajler radio u bilo kom folderu, potrebno je namestiti PATH pod Wine-om. Treba obratiti
pažnju da to NIJE ista PATH variabla kao ona od Linux sistema. Ovo se može uraditi na sledeći način1 :
• Otvori se regedit pod wine-om (wine regedit)
• nađe se ključ HKEY_CURRENT_USER/Environment
• promeni se polje “path” tako da uključuje i xds bin folder. obratiti pažnju da je potrebno ubaciti
dodatni "\", pa će krajnja vrednost izgledati ovako nekako:
c:\\windows;c:\\windows\\system;c:\\xds\\bin
Nakon ovoga se u bilo kom folderu može vršiti poziv
wine xc =make =all zad
predpostavljajući naravno da u folderu postoji “zad.mod” i da je u pitanju ispravan programski
modul, biće kreiran “zad.exe” koji se onda može pokrenuti sa
wine zad
Jednostavni programi koji rade sa tekstualnim ulazom i izlazom će najčešće raditi bez problema.
U zavisnosti od verzija programa nekad se dešava da kada ovako pokrenut program čeka na unos sa
tastature pravi veliko zauzeće procesora.
Postoji i opcija da se otvori novi terminal prozor koji vrši kompletnu emulaciju komandnog promta
operativnog sistema DOS 6. Npr:
wineconsole zad
Ovako pokrenut program će se ponašati identično kao na Windowsu i neće nepotrebno povećavati
zauzeće procesora. Međutim odmah nakon završetka rada pokrenute komande (tj programa zad u
primeru) novi prozor će se zatvoriti, što je problem ako je trebalo pročitati izlaz programa. Rešenje za
ovo je otvaranje terminala u kome se izvrašava cmd, tj klasični dos promt:
wineconsole cmd
U ovako otvorenom promtu se mogu naravno izvršavati sve komande, iako će interakcija biti nešto
drugačija od naviknute u modernim konzolama (tipa ispisivanja čudnih kodova umesto kretanja okolo
kad se pritiskaju strelice).
1 Link: uputstvo za sistemske promenljive na zvaničnom sajtu softvera Wine:
http://www.winehq.org/docs/wineusr-guide/environment-variables
Download

"normalna" verzija - jedna kolona