LOGO
“ Add your company slogan ”
Uvod u programiranje
Glava 5 – Strukturirani tipovi podataka
Zimski semestar 2013 v0.5
PMF Novi Sad
Departman za matematiku i informatiku
Slajd 2 od 100
Slajd 3 od 100
Ø Prosti tipovi podataka najčešće nisu dovoljni da bi se rešili svi (čak i neki
jednostavniji) problemi u programiranju.
Ø Drugu značajnu grupu tipova u Moduli-2 čine strukturirani tipovi podataka
– oni određuju strukturirane (komponovane, složene) vrednosti.
Ø Vrednosti strukturiranih tipova podataka se sastoje od komponenti, koje
mogu biti prostog ili (ponovo) strukturiranog tipa podataka, zavisno od
konkretnih pravila za građenje strukturiranih vrednosti.
Ø Za sve strukturirane tipove podataka zajedničko je da je skup dozvoljenih
operacija za rad sa njihovim vrednostima mali: obično su to operacije
pristupanja pojedinim komponentama strukture, operacije poređenja
(ne)jednakosti strukture i operacije dodeljivanja jedne strukture drugoj.
Ø Strukturirani tipovi su tako samo pogodan način za „pakovanje“ vrednosti
drugih tipova podataka u logičke celine.
Slajd 4 od 100
Ø U Moduli-2 je od strukturiranih tipova podataka moguće koristiti: nizove,
slogove (ili „zapise“), standardne skupove i skupove.
Ø Od ovih tipova podataka, jedino su standardni skupovi ugrađeni tip
podataka, dok su svi ostali uvedeni (korisnički).
Ø Uvedeni tipovi podataka definišu se u odgovarajućim delovima Modula-2
programa.
Ø Ako se definiše imenovani strukturirani tip (eksplicitna definicija tipa), on
se mora definisati u delu za definiciju tipova.
Ø Ako se u programu koristi neki strukturirani tip koji ne mora da bude
posebno imenovan (implicitna definicija tipa), njegova neimenovana
definicija se navodi u delu za deklaraciju promenljivih.
Slajd 5 od 100
Slajd 6 od 100
Ø Niz je tip podataka koji se sastoji od fiksnog broja komponenti istog tipa.
Ø Svakoj komponenti niza odgovara jedinstveni indeks komponente.
Ø Svakoj komponenti niza se, dakle, može pristupiti navođenjem imena
promenljive nizovnog tipa i indeksa, koji predstavlja poziciju komponente u
nizu.
Ø Tip indeksa mora biti redni tip, a tip komponente niza je proizvoljan tip.
Ø U daljem tekstu ćemo pojmom nizovni tip (podataka) označavati tip
podataka niz.
Ø Pod pojmom niz obično podrazumevamo promenljivu koja je (nekog)
nizovnog tipa.
Slajd 7 od 100
Ø Nizovni tip podataka je određen svojom veličinom (brojem komponenti),
tipom indeksa i tipom svojih komponenti.
Ø Da bi dva niza bila istog tipa, neophodno je da imaju: iste veličine, iste
tipove indeksa i iste tipove komponenti.
Ø Navedeni uslovi su potrebni (ali ne i dovoljni) da bi dva nizovna tipa bila
ista.
Ø O tome šta je zapravo potrebno da bi dva nizovna tipa (i uopšte tipa)
podataka u Moduli-2 bila ista, biće nešto više reči u poslednjem odeljku
ovog poglavlja.
Slajd 8 od 100
Ø U Moduli-2 dozvoljene su sledeće operacije sa nizovima (zbog stroge
tipiziranosti jezika, nizovi koji učestvuju u prve dve navedene operacije
moraju biti istog (nizovnog) tipa):
dodela vrednosti jednog niza drugom nizu (naredbom dodele),
poređenje jednakosti i nejednakosti dva niza (relacionim operatorima =
i <> (#)),
pristupanje jednoj komponenti niza.
Ø Pored toga, niz može biti prosleđivan procedurama i može biti rezultat
(funkcijskih) procedura.
Ø Nad komponentama niza mogu se primenjivati operacije koje su dozvoljene
za tip podataka komponente.
Slajd 9 od 100
5.1.1 Definicija nizovnog tipa podataka
Ø U opštem slučaju, nizovni tip podataka Niz i promenljiva tipa Niz definišu
se na sledeći način:
TYPE Niz = ARRAY TipIndeksa OF TipKomponente;
VAR nizA : Niz;
Ø Ukoliko nema potrebe da se nizovni tip podataka imenuje (implicitna
definicija tipa), tada se promenljiva nizA deklariše na sledeći način:
VAR nizA : ARRAY TipIndeksa OF TipKomponente;
Ø Definicija nizovnog tipa započinje rezervisanom rečju ARRAY, a sastoji se
od definicije tipa indeksa i definicije tipa komponenti.
Ø Kako tip podataka indeksa mora biti redni tip (što znači i da mu je skup
vrednosti konačne veličine), to je podatak o veličini niza implicitno sadržan
u definiciji tipa TipIndeksa.
Slajd 10 od 100
5.1.1 Definicija nizovnog tipa podataka
Ø Niz ima onoliko komponenti koliko skup vrednosti tipa TipIndeksa ima
elemenata.
Ø Tip TipKomponente je proizvoljan tip podataka.
Ø Bitno je napomenuti da tip indeksa definiše maksimalnu veličinu niza, te da
tokom rada programa niz može imati manje korisnih komponenti.
Ø Memorijski prostor je, međutim, zauzet za maksimalnu veličinu niza i ne
zavisi od toga koliko se komponenti niza u stvari koristi.
Ø Zbog toga se treba truditi da se definiše niz koji odgovara potrebama.
Slajd 11 od 100
5.1.1 Definicija nizovnog tipa podataka
Ø Upoznajmo se na kraju i sa jednom konvencijom (o kojoj će biti više reči u
odeljku 5.1.4): ukoliko je tip komponenti nekog niza (ponovo) nizovni tip,
tada je definiciju takvog niza moguće napisati i na drugačiji, kraći način.
Ø Sledeće dve definicije nizovnog tipa podataka su ekvivalentne:
ARRAY T1 OF ARRAY T2 OF ... ARRAY Tn OF Tk;
ARRAY T1, T2, ..., Tn OF Tk;
ARRAY
RedniTip
OF
Tip
,
5.1 Niz
Slajd 12 od 100
5.1.2 Nizovne konstante
Ø Konstante nizovnog tipa podataka mogu se zadati navođenjem vrednosti
svih komponenti niza.
Ø Moraju se navesti vrednosti za sve komponente niza, redom.
Ø Opšti oblik nizovne konstante je:
Tip(v1, v2, ..., vn)
pri čemu je Tip ime (već definisanog) nizovnog tipa podataka, v1, ..., vn
su, redom, konstantne vrednosti komponenata niza, dok je n ukupan broj
komponenti niza.
Slajd 13 od 100
5.1.2 Nizovne konstante
Primer.
TYPE Brojevi = ARRAY [-5..4] OF CARDINAL;
CONST Jedinice = Brojevi(1, 1, 1, 1, 1, 1, 1, 1, 1, 1);
VAR x, y : Brojevi;
BEGIN
x := Jedinice;
y := Brojevi(10, 20, 30, 10, 20, 30, 1, 1, 1, 1);
Posle navedenih dodeljivanja, (na primer) fizički prva komponenta niza y (odgovara
indeksu -5) je 10, a fizički peta komponenta (odgovara indeksu -1) je 20.
ØZbog načina na koji se definišu nizovne konstante, jasno je da se ne mogu
definisati konstante neimenovanih nizovnih tipova podataka.
Po Virtu, u Moduli-2 se ne mogu definisati konstantni nizovi. Po standardu, međutim,
mogu, na način sličan ovde opisanom. Razlika je što se umesto zagrada ( i )
upotrebljavaju zagrade { i }.
Slajd 14 od 100
5.1.3 Jednodimenzionalni nizovi
Ø Niz je jednodimenzionalan ako tip njegovih komponenti nije (ponovo) niz.
Ø To znači da se komponentama niza pristupa pomoću samo jednog indeksa.
Ø Komponenti (jednodimenzionalnog) niza a, kojoj odgovara vrednost i
indeksa, pristupa se izrazom a[i].
Ø Namerno ne kažemo i-toj komponenti niza, jer to asocira na fizički i-tu
komponentu niza.
Ø Komponenta na poziciji i ne mora, međutim, biti fizički na i-toj poziciji.
Ø Na primer, u nizu definisanom kao ARRAY [-2..2] OF REAL,
komponenta koja odgovara indeksu 1 u stvari je fizički četvrta komponenta.
-2 -1 0
1
2
Slajd 15 od 100
5.1.3 Jednodimenzionalni nizovi
Primer. Neki primeri jednodimenzionalnih nizova.
TYPE
Red = ARRAY [1..80] OF CHAR;
(* Niz znakova maksimalne duzine 80. Svakom elementu se pristupa pomocu
indeksa koji se krece u opsegu od 1 do 80 *)
Vektor = ARRAY [1..3] OF REAL;
Dani = (pon, uto, sre, cet, pet, sub, ned);
Meseci = (jan, feb, mar, apr, maj, jun, jul, avg, sep, okt, nov, dec);
VAR
ime : Red; (* promenljiva ciji je tip niz od 80 znakova *)
xKoor, yKoor : Vektor;
sati : ARRAY [pon..pet] OF REAL;
(* Promenljiva sati je promenljiva neimenovanog nizovnog tipa, koji predstavlja niz
realnih vrednosti za radne dane u nedelji. Indeks niza je podoblasnog tipa *)
pozitivniBr : ARRAY INTEGER OF CHAR;
(* Niz od 65536 znakova (odnosno onoliko koliko skup vrednosti tipa INTEGER
ima elemenata) *)
brojDana : ARRAY Meseci OF [1..31];
(* Svakom mesecu je pridruzen broj dana *)
Slajd 16 od 100
5.1.3 Jednodimenzionalni nizovi
Primer.
Napisati program koji određuje najmanji element u nizu brojeva. Obratimo pažnju da broj aktuelnih
(važečih) elemenata u niza ne mora biti jednak maksimalnom (deklarisanom) broju elemenata u nizu. U sledećem
primeru se broj aktuelnih elemenata u nizu nalazi u promenljivoj brojeva.
MODULE Min;
FROM InOut IMPORT ReadInt, WriteInt, WriteString, WriteLn;
CONST maxBrojeva = 100;
TYPE DijapazonVel = [1..maxBrojeva];
VAR
i, brojeva, min : INTEGER;
nizBr : ARRAY DijapazonVel OF INTEGER;
BEGIN
WriteString(‘Unesite broj ulaznih brojeva: ’); ReadInt(brojeva);
WriteString(‘Unesite ulazne brojeve: ’);
FOR i := 1 TO brojeva DO
ReadInt(nizBr[i]); WriteLn
END;
min := nizBr[1]; (* nizBr[1] daje vrednost pocetnog elementa niza *)
FOR i := 2 TO brojeva DO
IF nizBr[i] < min THEN
min := nizBr[i] (* novi minimum *)
END
END; (* FOR *)
WriteString(‘Minimalna vrednost u nizu je: ’); WriteInt(min, 6)
END Min.
Slajd 17 od 100
5.1.3 Jednodimenzionalni nizovi
Ø Za obradu svih komponenti niza najčešće se koristi FOR naredba.
Ø Međutim, postoje slučajevi u kojima je zgodnije i efikasnije koristiti neku
drugu naredbu ponavljanja.
Ø U sledećem primeru se vidi da upotreba WHILE naredbe skraćuje broj
izvršavanja ciklusa, jer nije neophodno pretraživati sve elemente niza.
Slajd 18 od 100
Primer. Program koji proverava da li se učitani element nalazi u nizu. U ovom primeru (zbog
jednostavnosti) podrazumevamo da je aktuelan broj elemenata u nizu jednak deklarisanom.
MODULE Sadrzan;
FROM InOut IMPORT ReadCard, WriteCard, WriteString, WriteLn, Done;
CONST duzina = 10;
VAR brojevi : ARRAY [1..duzina] OF CARDINAL;
i, broj : CARDINAL;
BEGIN
WriteString(‘Unesite elemente niza: ’); WriteLn;
FOR i := 1 TO duzina DO
ReadCard(brojevi[i]); WriteLn
END;
WriteString(‘Unesite broj: ’); ReadCard(broj);
WHILE Done DO
i := 1;
WHILE (i <= duzina) AND (brojevi[i] <> broj) DO
INC(i)
END;
IF (i <= duzina) THEN
WriteString(‘Broj je sadrzan u nizu’)
ELSE
WriteString(‘Broj nije sadrzan u nizu’)
END;
ReadCard(broj)
END
END Sadrzan.
Slajd 19 od 100
Primer. Program koji za učitani niz znakova utvrđuje da li je palindrom ili ne. Palindrom je niz
znakova koji se isto čita i sa leva u desno i sa desna u levo.
MODULE Palindrom;
FROM InOut IMPORT Read, Write, WriteString, WriteLn;
CONST maxDuz = 200;
TYPE Rec = ARRAY [1..maxDuz] OF CHAR;
VAR pali : Rec; ch : CHAR; poc, kraj : CARDINAL;
BEGIN
kraj := 0;
WriteString(‘Unesite niz znakova: ’); Read(ch);
WHILE ch <> ‘.’ DO
ch := CAP(ch);
IF (ch >= ‘A’) AND (ch <= ‘Z’) THEN
INC(kraj); pali[kraj] := ch
END;
Read(ch)
END;
poc := 1;
WHILE (poc < kraj) AND (pali[kraj] = pali[poc]) DO
DEC(kraj); INC(poc)
END;
WriteString(‘Uneta recenica ’);
IF poc >= kraj THEN
WriteString(‘je palindrom’)
ELSE
WriteString(‘nije palindrom’)
END
END Palindrom.
Slajd 20 od 100
5.1.4 Višedimenzionalni nizovi
Ø Komponente niza mogu biti takođe nizovi.
Ø Ova činjenica nam omogućava definisanje višedimenzionalnih nizova
(dvodimenzionalnih, trodimenzionalnih, itd.).
Ø Višedimenzionalni niz može se definisati na sledeći način:
TYPE ViseDim = ARRAY T1 OF ARRAY T2 OF ... ARRAY Tn OF Tk;
VAR vMatrica : ViseDim;
Ø Tip podataka ViseDim predstavlja višedimenzionalni niz, čiji su indeksi
tipa T1, T2, ..., Tn, a tip komponente je Tk.
Slajd 21 od 100
5.1.4 Višedimenzionalni nizovi
Ø Prethodna definicija može se zapisati i na sledeći način (uvođenjem
imenovanih tipova).
TYPE
Nti = ARRAY Tn OF Tk;
NMinus1 = ARRAY Tn-1 OF Nti;
...
Drugi = ARRAY T2 OF Treci;
ViseDim = ARRAY T1 OF Drugi;
VAR
vMatrica : ViseDim;
Slajd 22 od 100
5.1.4 Višedimenzionalni nizovi
Primer. Posmatrajmo ove mogućnosti definisanja na slučaju dvodimenzionalnih nizova.
TYPE Matrica = ARRAY [1..20] OF ARRAY [1..100] OF REAL;
VAR mat : Matrica;
Ekvivalentan način definisanja bi mogao biti
TYPE Red = ARRAY [1..100] OF REAL;
Matrica = ARRAY [1..20] OF Red;
VAR mat : Matrica;
mat je dvodimenzionalni niz koji se sastoji od 20 jednodimenzionalnih nizova.
Svaki od tih 20 nizova je jednodimenzionalni niz od po 100 realnih brojeva.
1
...
2
1
100
1
...
2
2
100
...
1
2
...
100
20
Slajd 23 od 100
5.1.4 Višedimenzionalni nizovi
Ø Komponenti višedimenzionalnog niza koji je definisan na opisani način se
pristupa izrazom: vMatrica[I1][I2]...[In], gde su I1, I2, ..., In
izrazi čije vrednosti određuju indekse pojedinih dimenzija.
Ø Ove veličine moraju biti u opsegu koje definišu odgovarajući tipovi.
Ø Tako za slučaj dvodimenzionalnog niza, mat[1][20] daje dvadesetu
komponentu prvog elementa (reda) matrice mat.
Ø Navedeni način definisanja višedimenzionalnih nizova je glomazan i
nečitak, pogotovo ako se definišu nizovi dimenzije veće od 2.
Ø Stoga postoji i jednostavniji način definisanja i pristupanja elementima
višedimenzionalnih nizova.
Slajd 24 od 100
5.1.4 Višedimenzionalni nizovi
Ø Višedimenzionalni nizovi mogu se definisati na sledeći način:
TYPE ViseDim = ARRAY T1, T2, ..., Tn OF Tk;
Primer. Tako se dvodimenzionalni niz Matrica može definisati i na sledeći način:
TYPE Matrica = ARRAY [1..20], [1..100] OF REAL;
VAR mat : Matrica;
a njenim elementima se može pristupiti na sledeći način:
mat[i,j] (* gde je i indeks vrste elementa, a j indeks kolone elementa *)
Primer. Pretpostavimo da se za svaki sat u toku dana, za različite temperature (variraju
između -60 i 45 stepeni Celzijusa), vrše merenja čiji je rezultat realan broj. Podaci
merenja mogli bi se smeštati u matricu sledećeg tipa.
TYPE Merenje = ARRAY [1..24], [-60..45] OF REAL;
Prvi indeks ([1..24]) je podoblasni tip osnovnog tipa CARDINAL, dok je drugi indeks
([-60..45]) podoblasni tip osnovnog tipa INTEGER.
Slajd 25 od 100
MODULE SabiranjeMat;
FROM InOut IMPORT ReadInt, WriteInt, WriteString, WriteLn;
CONST
dim = 50;
TYPE
Matrica = ARRAY [1..dim], [1..dim] OF INTEGER;
VAR
i, j, d : INTEGER;
mat1, mat2, mat3 : Matrica;
BEGIN
WriteString('Unesite dimenziju matrica: ');
ReadInt(d); WriteLn;
WriteString('Unesite prvu matricu po vrstama: ');
WriteLn;
(* Unos 1. matrice *)
FOR i := 1 TO d DO
FOR j := 1 TO d DO
ReadInt(mat1[i,j])
END;
WriteLn
END;
WriteString('Unesite drugu matricu po vrstama: ');
Slajd 26 od 100
5.1.5 Stringovi (niske)
Ø String je posebna vrsta niza.
Ø To je jednodimenzionalni niz čije su komponente znaci (tipa CHAR), a
indeks je bilo kog rednog tipa podataka.
Po Virtu, indeks stringa mora biti podintervalni tip prirodnih brojeva.
Ø Sa stringovskim konstantama sreli smo se u odeljku 2.1.3 (niz znakova
ograđen jednostrukim ili dvostrukim navodnicima).
Ø Napominjemo da navodnici nisu deo stringa – oni su samo pomoćni
mehanizam za zapisivanje konstanti.
Slajd 27 od 100
5.1.5 Stringovi (niske)
Primer.
TYPE
String10 = ARRAY [0..9] OF CHAR;
String2 = ARRAY BOOLEAN OF CHAR;
VAR
ime1, ime2 : String10;
skr : String2;
...
ime1 := ‘Konstantin’;
ime2 := ‘Pera’;
skr := ‘AB’;
...
U promenljivoj ime1 nalazi se niz znakova čija je dužina tačno 10 znakova. U
promenljivoj ime2 nalazi se niz znakova čija je dužina 4 znaka.
Slajd 28 od 100
5.1.5 Stringovi (niske)
Ø Prazan string se označava kao ‘’ ili “”.
Ø Prazan string je po tipu podataka string, ali se u izrazima može mešati sa
znacima (tipom podataka CHAR).
Po Virtu, prazan string nije usklađen sa tipom podataka CHAR.
Ø Ako je aktuelni sadržaj stringa kraći od definisane dužine stringa, tada se
kraj aktuelnog sadržaja stringa označava znakom 0C, koji se nalazi na
poziciji iza poslednjeg korisnog znaka u stringu (u slučaju prethodnog
primera, znak 0C se u promenljivoj ime2 nalazi na poziciji 4 – iza znaka a).
Ø Ovaj znak se postavlja automatski iza poslednjeg znaka od strane prevodioca
i o tome najčešće nije potrebno posebno voditi računa osim ako sami,
element po element, ne formiramo neki string.
Slajd 29 od 100
5.1.5 Stringovi (niske)
Ø Ako je čitav string popunjen sadržajem (kao u slučaju promenljive ime1),
string se ne završava znakom 0C.
Po standardu, kraj korisnog sadržaja stringa se ne mora označavati znakom 0C.
Umesto toga, kaže se da se kraj korisnog sadržaja stringa označava praznim stringom
(‘’ ili “”), pri čemu unutrašnja reprezentacija praznog stringa nije bitna i zavisi od
realizacije Module-2.
Ø Nad stringovnim konstantama može se primeniti operacija spajanja
(primenom operatora +).
Ø Rezultat primene operatora + je novi string čiji je sadržaj nastao spajanjem
sadržine oba operanda.
Ø Bitno je napomenuti da operandi operatora + ne mogu biti promenljive tipa
string, ni vrednosti tipa CHAR.
Slajd 30 od 100
5.1.5 Stringovi (niske)
Primer. Sledeći programski fragment ispisaće string ‘Zdravo Pero’ na ekranu.
TYPE String = ARRAY [1..25] OF CHAR;
CONST pozdrav = ‘Zdravo ’;
VAR ime : String;
BEGIN
ime := pozdrav + “Pero”;
WriteString(ime);
Virt ne predviđa mogućnost spajanja stringovnih konstanti.
Ø Operator + je jedini operator koji se može primeniti nad stringovima (uz
standardne nizovne operatore).
Ø Međutim svaka realizacija Module-2 poseduje bar jedan bibliotečki modul
sa procedurama za rad sa stringovima.
Standard predviđa postojanje funkcije LENGTH koja daje dužinu stringa.
Slajd 31 od 100
5.1.5 Stringovi (niske)
Primer. Program koji učitava string, pretvara sva učitana slova u velika i ispisuje rezultat.
MODULE Velika;
FROM InOut IMPORT ReadString, WriteString, WriteLn, Done;
CONST duzina = 99;
TYPE Str100 = ARRAY [0..duzina] OF CHAR;
VAR
ime : Str100;
i : CARDINAL;
BEGIN
WriteString(‘Unesite string za konverziju: ’); WriteLn;
ReadString(ime); WriteLn;
WHILE Done DO
FOR i := 0 TO duzina DO
ime[i] := CAP(ime[i])
END;
WriteString(‘Konvertovani string: ’);
WriteString(ime); WriteLn;
WriteString(‘Unesite string za konverziju: ’); WriteLn;
ReadString(ime); WriteLn;
END
END Velika.
Slajd 32 od 100
Slajd 33 od 100
Ø Niz je, kao što smo videli, strukturirani tip podataka čije su sve komponente
istog tipa.
Ø Međutim, često je potrebno grupisati nekoliko elemenata različitog tipa koji
predstavljaju neku logičku celinu.
Ø Tako je na primer podatke o osobi (ime, prezime, datum rođenja, matični
broj, ...) korisno čuvati grupisano, kako bi im se što lakše i organizovanije
pristupilo.
Ø Slog (ponekad ga zovemo i zapis, engl. record) je tip podataka koji se
sastoji od fiksnog broja polja (komponenti), čiji tipovi podataka mogu biti
međusobno različiti.
Ø Tip polja sloga može biti bilo koji tip podataka.
Slajd 34 od 100
Ø Svako polje sloga ima jedinstveno ime u slogu.
Ø Polju se pristupa navođenjem imena promenljive tipa sloga i imena polja u
tom slogu.
Ø U daljem tekstu pojmom slogovni tip (podataka) označavaćemo tip
podataka slog.
Ø Pod pojmom slog podrazumevaćemo promenljivu koja je (nekog)
slogovnog tipa.
Ø Slogovni tip podataka je određen brojem, redosledom i tipom komponenti.
Ø Da bi dva sloga bila istog tipa, neophodno je: da imaju iste tipove
komponenti i da one budu u istom redosledu.
Slajd 35 od 100
Ø U Moduli-2 su dozvoljene sledeće operacije sa slogovima (zbog stroge
tipiziranosti jezika, slogovi koji učestvuju u prve dve navedene operacije
moraju biti istog (slogovnog) tipa):
dodela vrednosti jednog sloga drugom slogu (naredbom dodele),
poređenje jednakosti i nejednakosti dva sloga (relacionim operatorima
= i <> (#)),
pristupanje jednom polju sloga.
Ø Pored toga, slog može biti prosleđivan procedurama kao parametar i može
biti rezultat (funkcijskih) procedura.
Ø Nad poljem sloga mogu se primenjivati operacije koje su dozvoljene za tip
podataka polja.
Slajd 36 od 100
5.2.1 Definicija slogovnog tipa podatka
Ø U opštem slučaju definicija (fiksnog) slogovnog tipa podataka je oblika:
TYPE
Slog = RECORD
ime1 : T1;
ime2 : T2;
...
imen : Tn
END
pri čemu je Slog ime definisanog slogovnog tipa; RECORD i END
rezervisane reči za definisanje slogovnog tipa podataka; ime1, ..., imen su
međusobno različita imena polja sloga, a T1, ..., Tn tipovi polja sloga.
Ø Ukoliko je više uzastopnih polja istog tipa, tada se njihova imena mogu
navesti jedno iza drugog (odvojeni zarezima) pre definicije njihovog tipa.
Slajd 37 od 100
5.2.1 Definicija slogovnog tipa podatka
Ø Pored fiksnih slogova postoje i promenljivi slogovi (slogovi promenljive
veličine).
Ø Njihova struktura zavisi od vrednosti posebnih selektorskih (težinskih, engl.
tag) polja.
Ø Promenljivi slogovi biće objašnjeni nešto kasnije u ovom poglavlju.
Slajd 38 od 100
5.2.1 Definicija slogovnog tipa podatka
;
RECORD
Lista polja
ListaPolja
END
,
:
Ime
CASE
Ime
:
Varijanta
Tip
KvalIme
|
OF
Varijanta
;
ELSE
..
END
;
,
KonstIzraz
ListaPolja
KonstIzraz
:
ListaPolja
5.4 Slog
Slajd 39 od 100
5.2.1 Definicija slogovnog tipa podatka
Primer. U sledećoj definiciji definišemo novi tip podataka za kompleksni broj.
Kompleksni broj se sastoji od realnog i imaginarnog dela, pri čemu su obe komponente
istog (realnog) tipa podataka. Iako smo se u ovom slučaju mogli opredeliti i za niz, slog
će nam omogućiti pisanje čitljivijih i razumljivijih programa, zato što ćemo se realnoj i
imaginarnoj komponenti obraćati imenima, a ne indeksima:
TYPE Kompleksni = RECORD
Re, Im : REAL
END;
VAR kBr1, kBr2 : Kompleksni;
Gore navedeni primer mogao bi se ekvivalentno definisati korišćenjem neimenovanog
tipa sloga na sledeći način:
VAR
kBr1, kBr2 : RECORD
Re, Im : REAL
END;
Slajd 40 od 100
5.2.1 Definicija slogovnog tipa podatka
Primer. Neki različiti, a ekvivalentni načini definisanja tipova sloga.
TYPE
Datum = RECORD
Dan : [1..31];
Mesec : (jan, feb, mar, apr, maj, jun, jul,
avg, sep, okt, nov, dec);
God : [1900..2200]
END;
VAR dan, petarDan, jovanDan : Datum;
TYPE
Dani = [1..31];
Meseci = (jan, feb, mar, apr, maj, jun, jul,
avg, sep, okt, nov, dec);
Godine = [1900..2200];
Datum = RECORD
Dan : Dani;
Mesec : Meseci;
God : Godine
END;
VAR dan, petarDan, jovanDan : Datum;
Slajd 41 od 100
5.2.1 Definicija slogovnog tipa podatka
Ø Primetimo da je dozvoljeno da promenljive ili neke druge konstrukcije van
sloga imaju ista imena kao polja u slogovima (unutar sloga, međutim, imena
polja moraju biti međusobno različita).
Ø Ovo je moguće jer su imena polja lokalna u odnosu na slog: da bi se
pristupilo nekom polju unutar sloga, navodi se ime sloga i ime polja unutar
sloga na sledeći način: slog.polje, pri čemu je slog ime sloga, polje
ime željenog polja, a . je specijalni znak.
Ø Ako je polje sloga takođe slogovnog tipa podataka, tada se navodi čitava
hijerarhija (redosled slogova) kojom se prolazi da bi se pristupilo željenom
polju.
Ø Svaki nivo (ime polja) u toj hijerarhiji razdovjen je simbolom .
Slajd 42 od 100
5.2.1 Definicija slogovnog tipa podatka
Primer.
dan.Dan := 20;
(* dodela vrednosti polju Dan u okviru promenljive (tipa sloga) dan *)
dan.Mesec := feb;
(* dodela vrednosti polju Mesec u okviru promenljive (tipa sloga) dan *)
dan.God := 2010;
(* slicno kao i za prethodna dva polja *)
Slajd 43 od 100
5.2.2 Slogovne konstante
Ø Konstante slogovnog tipa podataka mogu se zadati navođenjem vrednosti
svih komponenti sloga po redu po kojem se pojavljuju u definiciji slogovnog
tipa.
Ø Moraju se navesti vrednosti za sve komponente sloga.
Ø Opšti oblik slogovne konstante je:
Tip(v1, v2, ..., vn)
pri čemu je Tip ime (već definisanog) slogovnog tipa podataka, a
v1, ..., vn su redom konstantne vrednosti komponenata sloga, gde je n
ukupan broj komponenti sloga.
Slajd 44 od 100
5.2.2 Slogovne konstante
Primer.
TYPE Osoba = RECORD
Ime, Prezime : ARRAY [1..10] OF CHAR;
Godine : [0..120]
END;
CONST pera = Osoba(“Pera”, “Petrovic”, 24);
VAR
x, y : Osoba;
BEGIN
x := pera;
y := Osoba(“Djoka”, “Petrovic”, 38);
Posle navedenih dodeljivanja polja Ime sloga x ima vrednost “Pera”, a polje Godine
sloga y ima vrednost 38.
ØZbog načina na koji se definišu slogovne konstante, jasno je da se ne mogu
definisati konstante neimenovanih slogovnih tipova podataka.
Po Virtu, u Moduli-2 se ne mogu definisati konstantni slogovi. Po standardu mogu, na način sličan
ovde opisanom. Jedina razlika je što se umesto zagrada ( i ) upotrebljavaju zagrade { i }.
Slajd 45 od 100
5.2.3 Fiksni slogovi
Ø Kao što je već rečeno, fiksni slogovi su slogovi nepromenljive strukture i
sastoje se od polja (komponenti), od kojih svako može biti proizvoljnog tipa
podataka.
Ø U ovom odeljku navodimo nekoliko primera upotrebe fiksnih slogova.
Primer. Slog sa osnovnim podacima o studentu.
TYPE
String15 = ARRAY [1..15] OF CHAR;
Student = RECORD
Ime, Prezime : String15;
DatRodj : Datum;
MaticniBr : CARDINAL;
Mesto : String15
END;
...
...
Dan Mesec God
...
Ime
Prezime
DatRodj
MaticniBroj
Mesto
Slajd 46 od 100
5.2.3 Fiksni slogovi
Ø Polja istog tipa podataka ne moraju se navoditi jedno iza drugog.
Ø Raspored polja je proizvoljan i nema uticaja na brzinu pristupa poljima ili
brzinu izvršavanja čitavog programa.
Primer. Komponente strukturiranih tipova podataka mogu biti takođe strukture. To nam
omogućava bolju apstrakciju podataka i čitljivije programe.
VAR odeljenje : ARRAY [1..40] OF Student;
osoba : Student;
Odeljenje je niz od 40 slogova. Svakom studentu iz odeljenja odgovara po
jedan slog. U okviru sloga imamo polja Ime, Prezime i Mesto koja su
nizovi znakova. DatumRodj je tipa sloga, MaticniBr je tipa
CARDINAL.
Slajd 47 od 100
5.2.3 Fiksni slogovi
Primer. Pretpostavimo da je stud (već otvoren) fajl u kom su navedene vrednosti
kompletnih slogova. U tom slučaju dodela vrednosti elementima niza iz prethodnog
primera bi se mogla vršiti na sledeći način:
i := 0;
ucitano := RdBin(stud, osoba, SIZE(Student));
(* iz datoteke stud se cita sadrzaj narednog sloga i smesta u promenljivu osoba *)
WHILE i < 40 DO
INC(i);
odeljenje[i] := osoba;
(* dodela vrednosti sloga osoba, narednom elementu u nizu slogova odeljenje *)
ucitano := RdBin(stud, osoba, SIZE(Student));
IF ucitano <> SIZE(Student) THEN
WriteString(‘Neka greska’)
END
END;
Slajd 48 od 100
5.2.3 Fiksni slogovi
ili korišćenjem naredbe FOR:
FOR i := 1 TO 40 DO
ucitano := RdBin(stud, odeljenje[i], SIZE(odeljenje[i]))
(* moguce je direktno ucitavati slog na odgovarajucu poziciju u nizu,
ne koristeci pomocnu promenljivu osoba *)
END;
Ø Poziv standardne funkcije SIZE(p) daje veličinu promenljive p u
bajtovima.
Slajd 49 od 100
5.2.3 Fiksni slogovi
Primer. U sledećem primeru su ilustrovani slogovi unutar slogova.
VAR
oIme, oPrezime, oMesto : String15;
oDani : Dani; oMeseci : Meseci; oGodine : Godine;
BEGIN
...
FOR i := 1 TO 40 DO
Ucitaj(oIme, oPrezime, oDani, oMeseci, oGodine, oMesto);
(* Ucitaj je neka procedura kojom se ucitavaju navedeni podaci *)
odeljenje[i].Ime := oIme;
odeljenje[i].Prezime := oPrezime;
odeljenje[i].DatRodj.Dan := oDani;
odeljenje[i].DatRodj.Mesec := oMeseci;
odeljenje[i].DatRodj.God := oGodina;
odeljenje[i].Mesto := oMesto;
END;
...
END
Prvom slovu imena i-tog studenta iz odeljenja se pristupa na sledeći način:
odeljenje[i].Ime[1];
Slajd 50 od 100
5.2.3 Fiksni slogovi
Primer.
Program za učitavanje dva kompleksna broja (čiji su realni i imaginarni delovi celi), izvršavanje zadate
operacije nad njima (+ za sabiranje, - za oduzimanje i * za množenje dva kompleksna broja) i štampanje rezultata.
MODULE KompleksniBr;
FROM InOut IMPORT ReadInt, WriteString, WriteLn, WriteInt, Read, Write;
TYPE Kompleksni = RECORD
Re, Im : INTEGER;
END;
VAR br1, br2, rez : Kompleksni; op : CHAR;
BEGIN
WriteString(‘Unesite realni i imaginarni deo 1. broja: ’);
ReadInt(br1.Re); ReadInt(br1.Im); WriteLn;
WriteString(‘Unesite realni i imaginarni deo 2. broja: ’);
ReadInt(br2.Re); ReadInt(br2.Im); WriteLn;
REPEAT
WriteString(‘Unesite znak operacije (+,-,*): ’); Read(op)
UNTIL (op = ‘+’) OR (op = ‘-’) OR (op = ‘*’);
CASE op OF
‘+’: rez.Re := br1.Re + br2.Re; rez.Im := br1.Im + br2.Im |
‘-’: rez.Re := br1.Re – br2.Re; rez.Im := br1.Im – br2.Im
ELSE
(* kako je prilikom ucitavanja operacije vrsena kontrola ispravnosti,
ako operacije nije ‘+’ ili ‘-’ onda sigurno mora biti ‘*’ *)
rez.Re := br1.Re*br2.Re – br1.Im*br2.Im;
rez.Im := br1.Re*br2.Im + br1.Im*br2.Re
END;
WriteString(‘Rezultat: ’); WriteInt(rez.Re,2); Write(‘+’); WriteInt(rez.Im,2); Write(‘i’)
END KompleksniBr.
Slajd 51 od 100
5.2.4 Naredba WITH
Ø U prethodnim primerima mogli smo primetiti da je, ukoliko je struktura
sloga „bogatija“, opis dostizanja pojedinih polja (koja su duboko u
hijerarhiji) sve duži.
Ø Da bi se pojednostavio pristup poljima sloga, te da se izbegne stalno
ponavljanje imena sloga pre imena polja, uvedena je naredba WITH.
Ø Naredbom WITH slog se „raspakuje“ i njegova polja postaju dostupna, bez
obaveze da se ispred svakog od njih navodi ime sloga.
Ø Opšti oblik naredbe WITH je sledeći:
WITH ime DO nizNaredbi END;
pri čemu je ime ime sloga, koje će se u naredbama nizNaredbi
podrazumevati kao prefiks svim imenima polja koja figurišu u naredbama.
Slajd 52 od 100
5.2.4 Naredba WITH
.
Ime
,
KvalIme
WITH
[
Izraz
]
^
DO
NizNaredbi
END
5.6 WITH naredba
Slajd 53 od 100
5.2.4 Naredba WITH
Primer. Korišćenjem polja iz niza odeljenje, uz pomoć WITH naredbi.
FOR i := 1 TO 40 DO
Ucitaj(...);
WITH odeljenje[i] DO (* 1 *)
Ime := oIme;
(* Pristupa se poljima samo navodjenjem njihovih imena.
Podrazumeva se prefiks odeljenje[i]. naveden u naredbi WITH *)
Prezime := oPrezime;
WITH DatRodj DO (* 2 *)
Dan := oDani;
Mesec := oMeseci;
God := oGodine
END; (* 2 *)
Mesto := oMesto
END (* 1 *)
END (* FOR *)
Slajd 54 od 100
Primer.
TYPE
Automobil = RECORD
Marka, Proizvodjac : String15;
GodinaProiz : [1800..2100];
Boja : (bela, crna, crvena, plava, zelena);
Jacina : CARDINAL;
BrVrata : [1..10]
END;
Vlasnik = RECORD
Ime, Prezime, RegBroj : String15;
Auto : Automobil
END;
VAR
vlasnici : ARRAY [1..1000] OF Vlasnik;
Ako želimo da popunjavamo podatke o automobilu nekog vlasnika onda je jednostavnije
koristiti WITH naredbu nego stalno navoditi promenljivu za slog i polja u slogu.
WITH vlasnici[i].Auto DO
Marka := ‘Yugo Koral 55’;
Proizvodjac := ‘Crvena zastava’;
GodinaProiz := 1989;
Jacina := 1000;
BrVrata := 5;
Boja := crvena
END;
Slajd 55 od 100
5.2.4.1 Pristup poljima
Ø Naredba WITH slog DO nizNaredbi END izvršava se na sledeći način:
pristupi se slogu slog;
za svako ime unutar naredbi nizNaredbi ispituje se da li je ime nekog
polja unutar sloga slog;
ako jeste, koristi se to polje;
ako nije, koristi se ime u svom originalnom obliku (bez prefiksa slog.)
Ø Na osnovu gornjeg pravila, jasno je da unutar naredbe WITH imena polja imaju
prvenstvo u odnosu na imena nekih drugih promenljivih.
Slajd 56 od 100
5.2.4.1 Pristup poljima
Primer.
VAR Re : REAL;
TYPE Kompl = RECORD
Re, Im : REAL
END;
...
VAR
k : Kompl;
...
Re := 1.0;
(* 1 *)
WITH k DO
Re := 2.0;
(* 2 *)
k.Re := 3.0; (* 3 *)
END;
k.Re := 4.0;
(* 4 *)
Prva dodela identifikatoru Re odnosi se na realnu promenljivu Re, dok se sve
ostale dodele odnose na dodelu polju Re unutar sloga k.
Slajd 57 od 100
5.2.4.1 Pristup poljima
Ø Po navedenim pravilima, unutar WITH naredbe se može dodeliti i vrednost
čitavom slogu koji je WITH naredbom „raspakovan“ (mada to nije
preporučljivo, niti je odlika lepog stila programiranja).
Primer. U sledećem primeru se čitavom „raspakovanom“ slogu vlasnici[i].Auto
dodeljuje potpuno nova vrednost unutar WITH naredbe.
WITH vlasnici[i].Auto DO
...
IF promena THEN
vlasnici[i].Auto := noviAuto
END;
...
END;
Slajd 58 od 100
5.2.4.2 Efikasnost
Ø Naredba WITH, osim što omogućava skraćeni i jednostavniji zapis pristupanja
poljima sloga, može da utiče i na efikasnost izvršavanja programa.
Ø Upotrebom naredbe WITH slogu se pristupa samo jednom.
Ø Kada su slogovi, na primer, komponente niza, da bi se pristupilo nekom polju,
prvo se mora pristupiti komponenti niza, što znači da se svaki put izračunava
pozicija komponente.
Ø U prethodnom primeru sa automobilima, bez upotrebe naredbe WITH za
svako polje bi se ponovo izračunavala pozicija sloga u nizu i svaki put bi se
iznova pristupalo slogu.
Ø Kada se navede WITH naredba, komponenti se pristupa samo jednom (na
početku naredbe) i nikakva izračunavanja više nisu potrebna – sva polja se
nalaze na „dohvat ruke“.
Slajd 59 od 100
5.2.4.2 Efikasnost
Ø Primer. Program koji iz ulaznog fajla čita trenutnu tabelu fudbalskog prvenstva,
rezultate sa utakmica održanih u poslednjem kolu, pa na osnovu tih rezultata ažurira
stanje u trenutnoj tabeli i štampa novu tabelu. Ulazni podaci nalaze su u fajlu tabela,
a rezultujuća tabela se štampa u fajl nova.
Podaci su u fajlu smešteni u sledećem obliku:
podaci o trenutnoj tabeli (za svaki tim su podaci u jednom redu):
• 20 znakova za ime tima,
• broj odigranih utakmica,
• broj datih golova,
• broj primljenih golova,
• ukupan broj bodova
podaci o odigranim utakmicama (za svaku utakmicu su podacu u jednom redu)
• ime tima domaćina,
• ime tima gosta,
• broj golova koje je dao tim domaćin,
• broj golova koje je dao tim gost.
Bodovi se računaju tako da se za pobedu timu dodaju 2 boda, za nerešen rezultat 1 bod
i za izgubljenu utakmicu 0 bodova.
Slajd 60 od 100
5.2.4.2 Efikasnost
Ø Rešenje. Niz akcija koje će se izvršavati u programu mogu se podeliti na nekoliko
celina koje se globalno mogu prikazati na sledeći način:
1.
2.
3.
4.
5.
6.
7.
učitati tabelu prvenstva,
učitati podatke o ekipama i rezultatima,
izračunati bitne podatke na osnovu rezultata odigranih utakmica,
pronaći u tabeli obe ekipe i ažurirati podatke,
korake 2-4 izvršavati sve dok ima podataka o utakmicama,
sortirati dobijenu tabelu,
zapisati novu tabelu.
Ø Za prikaz podataka u tabeli, tj. za prikaz podataka o jednom timu, koristiće se slog koji
će sadržati odgovarajuća polja za podatke koji se učitavaju o timu.
Slajd 61 od 100
5.2.4.2 Efikasnost
Ø Za sortiranje tabele koristiće se jedna, relativno jednostavna i neefikasna metoda (pošto
se u rešenju ovog zadatka ne insistira na efikasnosti), poznata pod imenom „bubble
sort“ (sortiranje metodom mehura).
Ø Da bi se sortirao niz elemenata, posmatra se prvi još nesortirani element.
Ø Taj element se poredi sa preostalim nesortiranim elementima.
Ø Ako je neki od tih elemenata veći od posmatranog, oni zamene mesta u nizu.
Ø Kada se dođe do kraja niza, na posmatranoj poziciji će biti najveći od još nesortiranih
elemenata.
Ø Postupak se ponavlja za sve elemente počev od prvog do pretposlednjeg.
Ø Dakle, na svaku od pozicija isplivava najveći element od još nesortiranih.
Slajd 62 od 100
5.2.4.2 Efikasnost
Ø U primeni ovog algoritma na fudbalsku tabelu potrebno je odrediti uslov kada je jedan
element, tj. tim, bolji od nekog drugog.
Ø Tim T1 je bolji od tima T2, ako tim T1 ima veći broj bodova ili, kada oba tima imaju
isti broj bodova, bolji je onaj tim koji ima bolju gol razliku.
Ø U nastavku je data jedna jednostavna realizacija programa koji rešava ovaj problem.
Ø Za rad sa datotekama koristimo procedure iz modula FIO.
Ø Pretpostavljamo, takođe. da postoji procedura UNoviRed(f), koja se pozicionira na
prvi znak sledećeg reda u (otvorenom) fajlu f.
Ø U realizaciji procedure se koristimo činjenicom da se svaka linija u fajlu pod
operativnim sistemom DOS završava sa dva specijalna znaka: 15C i 12C.
Slajd 63 od 100
5.2.4.2 Efikasnost
(* Realizacija procedure mogla bi da izgleda ovako:
zn := FIO.RdChar(f);
WHILE zn <> 15C DO
zn := FIO.RdChar(f)
END;
zn := RdChar(f); (* ucitamo jos i 12C *)
(* sledece citanje iz fajla citace sa pocetka novog reda
*)
*)
MODULE Tabela;
IMPORT FIO;
CONST
brojTimova = 18;
duzina = 20;
max = 400;
TYPE
Do400 = [0..max];
BrTim = [1..brojTimova];
Slajd 64 od 100
5.2.5 Promenljivi slog
Ø Promenljivi slog (slog promenljive dužine) se sastoji, u opštem slučaju, od
fiksnog i promenljivog dela (pri čemu fiksni deo može da se sastoji samo od
selektorskog polja).
Ø Struktura
promenljivog dela sloga zavisi od vrednosti posebnog
(selektorskog) polja.
Ø Selektorsko polje mora biti nekog rednog tipa podataka.
Ø Za svaku vrednost selektorskog polja navodi se lista važećih polja sloga za
taj slučaj.
Ø Sva imena polja koja se jave u promenljivom delu sloga moraju biti
međusobno različita, čak i kada se javljaju u različitim varijantama.
Ø Promenljivi deo sloga se može javiti na proizvoljnom mestu u slogu,
proizvoljan broj puta, a može biti i ugnežden.
Slajd 65 od 100
5.2.5 Promenljivi slog
Primer. Neka su u narednom primeru tipovi: Tip0, Tip11, Tip12, Tip13, Tip31 i
Tip32 različiti, već definisani tipovi.
TYPE
Boja = (crvena, zelena, crna);
Objekat = RECORD
x, y : Tip0;
CASE Var1 : Boja OF
crvena : a : Tip11;
b : Tip12;
c : Tip13 |
crna : d : Tip31;
e, f : Tip32
END;
z : Tip0;
CASE : BOOLEAN OF
TRUE : g, h : INTEGER
ELSE
i : CARDINAL
END
END;
VAR ob : Objekat;
Slajd 66 od 100
5.2.5 Promenljivi slog
Ø Primetimo da će se u objektu ob pristupati poljima ob.a, ob.b i ob.c, ako
selektorsko polje ob.Var1 ima vrednost crvena.
Ø U slučaju da je ta vrednost zelena, nema polja u varijabilnom delu, a kada
je vrednost selektorskog polja crna, dostupna su polja ob.d, ob.e i ob.f.
Ø Takođe, sva imena polja a, b, c, d, e i f moraju biti različita jer se javljaju u
istom varijabilnom delu.
Ø Poljima ob.g i ob.h, odnosno ob.i, pristupa se navođenjem njihovih
imena (odgovornost je u potpunosti programerova) jer u tom varijabilnom
delu nema selektorskog polja na osnovu koga se određuje koja polja u
varijabilnom delu su dostupna, a koja ne (sva polja su vidljiva). U pitanju je
slobodna unija, o čemu će biti više reči kasnije.
Slajd 67 od 100
5.2.5 Promenljivi slog
Primer. U sledećem primeru za svaku od 4 površinske figure u slogu Figura predstavljeni su obim,
površina, kao i podaci na osnovu kojih se obim i površina mogu izračunati. U zavisnosti od vrednosti
polja Izbor, za krug i kvadrat je to jedna vrednost (poluprečnik ili dužina stranice), za pravougaonik:
visina i širina figure, a za trougao dužine stranica.
TYPE
Figure = (kvadrat, krug, trougao, pravoug);
Figura = RECORD
Obim, Povrsina : REAL;
CASE Izbor : Figure OF
krug, kvadrat: Duz : REAL |
pravoug: Vis, Sir : REAL
ELSE
St1, St2, St3 : REAL
(* za one slucajeve koji preostaju u rednom tipu, u ovom slucaju: trougao *)
END
END;
VAR
fig1, fig2 : Figura;
...
IF fig1.Izbor = trougao THEN
ReadReal(fig1.St1,5); ReadReal(fig1.St2,5); ReadReal(fig1.St3,5)
ELSIF ...
END;
Slajd 68 od 100
5.2.1 Definicija slogovnog tipa podatka
;
RECORD
Lista polja
ListaPolja
END
,
:
Ime
CASE
Ime
:
Varijanta
Tip
KvalIme
|
OF
Varijanta
;
ELSE
..
END
;
,
KonstIzraz
ListaPolja
KonstIzraz
:
ListaPolja
5.4 Slog
Slajd 69 od 100
TYPE
VrstaOsobe = (domaci, stranac);
BracnoStanje = (sam, ubraku, razveden, udovac);
Drzavljanstvo = (porodjenju, pozivljenju);
Polovi = (musko, zensko);
Osoba = RECORD
Ime, Prezime : String15;
DatumRodj : Datum;
CASE Poreklo : VrstaOsobe OF
domaci: MestoRodj : String15;
CASE Drzavljanin : Drzavljanstvo OF
porodjenju: |
pozivljenju: RegBroj : CARDINAL;
DatDrzavljanstva : Datum
END |
stranac: ZemljaPorekla : String15;
DatumUlaska : Datum;
GranicniPrelaz : String15
END;
CASE Status : BracnoStanje OF
sam: |
ubraku: ImeBracnogDruga : String15;
Slajd 70 od 100
5.2.5.1 Prednosti i mane promenljivih slogova
Ø Postojanjem promenljivog sloga u programskom jeziku moguće je u strukturu
formalno istog tipa podataka smestiti konkretne vrednosti različitih tipova
podataka.
Ø Sličan efekat bi se mogao postići i fiksnim slogom, u kome bi figurisala sva
potrebna polja, a važnost pojedinih polja bi se određivala takođe na osnovu
sadržine nekog „posvećenog“ polja.
Ø Prednost promenljivih slogova je smanjenje zauzetosti memorijskog prostora,
jer se ne zauzima memorijski prostor za sve varijante – zauzima se samo za
najdužu varijantu.
Slajd 71 od 100
5.2.5.1 Prednosti i mane promenljivih slogova
Primer. U sledećem primeru fiksni deo sloga sastoji se samo od selektorskog polja tip, od čije
vrednosti zavisi struktura promenljivog dela sloga. Ako se u polju tip nalazi vrednost ceo, tada se
ostatak sloga sastoji od polja brojC (tipa INTEGER), a inače se sastoji od polja brojR (tipa REAL).
TYPE
TipBroja = (ceo, realni);
Broj = RECORD
CASE tip : TipBroja OF
ceo:
brojC : INTEGER |
realni: brojR : REAL
END
END;
Za potrebe sloga Broj zauzima se
memorijski prostor dovoljan za
smeštanje duže varijante (kada je tip
= realni).
Broj
tip
brojC
brojR
Slajd 72 od 100
5.2.5.1 Prednosti i mane promenljivih slogova
Primer. Niz od pet elemenata tipa Broj tada se definiše na sledeći način:
TYPE
Niz = ARRAY [1..5] OF Broj;
(* cime smo zapravo omogucili stavljanje i celih i realnih brojeva u isti niz.
Alternativna varijanta bez promenljivog sloga: *)
TYPE
Broj1 = RECORD
tip : TipBroja;
brojC : INTEGER;
brojR : REAL
END;
Niz1 = ARRAY [1..5] OF Broj1;
(* moguca je takodje, ali zauzima vise memorijskog prostora. *)
Slajd 73 od 100
5.2.5.1 Prednosti i mane promenljivih slogova
Ø Pored prednosti koje pružaju, promenljivi slogovi imaju i nedostatke.
Ø Prevodilac Module-2 (obično) ne pruža nikakve „usluge“ u radu sa
promenljivim slogovima i bez obzira koja vrednost se nalazi u selektorskom
polju, može se pristupiti svim poljima (iz svih varijanti) promenljivog sloga.
Ø Tako su vrednost selektorskog polja i važeća struktura sloga potpuna
odgovornost programera.
Ø Greške napravljene pristupanjem polju koje trenutno nije važeće se vrlo teško
otkrivaju, jer je sadržina polja u tom trenutku nedefinisana (na primer,
pristupanje polju brojR iz prethodnog primera, ako je u polju tip vrednost
ceo, će dati ono što se u tom trenutku zateklo u memoriji, što može dovesti
do neočekivanih rezultata).
Slajd 74 od 100
5.2.5.2 Slobodne unije
Ø Kao što se vidi iz sintaksnog dijagrama, selektorsko polje nije neophodno
navesti u definiciji promenljivog sloga.
Ø Promenljivi slogovi bez selektorskog polja nazivaju se slobodnim unijama.
Ø Pomoću slobodne unije jednoj vrednosti (ili sekvenci vrednosti) se može
pristupati na više različitih načina (tj. jedna te ista vrednost može se tumačiti
na više različitih načina).
Slajd 75 od 100
5.2.5.2 Slobodne unije
Primer. U sledećem primeru s je definisano kao slobodna unija. Podacima iz slobodne
unije se slobodno i bez ikakvih restrikcija može pristupiti na dva načina: kao znacima ili
broju. Selektorski tip (ovde: BOOLEAN) u slobodnim unijama ima samo ulogu
međusobnog odvajanja različitih načina pristupa.
VAR s : RECORD
CASE : BOOLEAN OF
TRUE: zn1, zn2 : CHAR |
FALSE: broj : CARDINAL
END
END;
Slobodna unija s je definisana tako da
je zn1 znakovna reprezentacija prvog
bajta, a zn2 znakovna reprezentacija
drugog bajta prirodnog broja broj.
s
broj
zn1
zn2
Ø Slobodne unije najčešće nalaze primenu u sistemskom programiranju. Nisu
pogodne za programiranje visokog nivoa, jer je mogućnost greške velika.
Slajd 76 od 100
Slajd 77 od 100
Ø Skup je tip podataka unapred određene veličine, u kom se nalaze elementi
istog tipa podataka.
Ø Za razliku od nizova i slogova, elementima skupa se ne može pristupiti na
osnovu pozicije.
Ø U ovom odeljku upoznaćemo se sa standardnim skupovnim tipom (ili
BITSET) kod kojeg ne možemo menjati tip elemenata skupa.
Ø U sledećem odeljku obradićemo uvedenti tip podataka skup, kod kojeg
možemo (donekle) birati tip vrednosti elemenata skupa.
Slajd 78 od 100
Ø Standardni skupovni tip podataka označava se standardnim imenom BITSET.
Ø Skupu vrednosti tipa BITSET pripadaju svi elementi partitivnog skupa od {0,
1, 2, ..., n–1}, tj. skupovi (uključujući i prazan skup), čiji su elementi prirodni
brojevi od 0 do (n–1).
Ø n je zavisno od računara na kom je jezik realizovan i najčešće je jednako
veličini memorijske reči računara (u slučaju 16-bitnog procesora je 16).
Ø Međutim, u zavisnosti od realizacije Module-2, n može biti i veće, a onda je
obično neki umnožak dužine reči računara.
Primer. Neke od mogućih vrednosti tipa BITSET su sledeći skupovi:
{0}, {1..5}, {0, 1, 3..5}, {1, 3, 5, 7, 9, 11, 13, 15}
Slajd 79 od 100
5.3.1 Konstante BITSET-a
Ø Konstante BITSET-a se navode u vitičastim zagradama i razdvojene su
zarezom.
,
{
Izraz
..
Izraz
}
5.9 BITSET konstanta
Ø Elemente skupa u skupovnoj konstanti možemo navoditi pojedinačno ili
navođenjem prvog i poslednjeg elementa u nekom nizu sukcesivnih
elemenata. U tom slučaju se između njih postavljaju znaci ..
Primer. Primeri konstanti:
{}, {1..12}, {1, 2, 5..10}
Slajd 80 od 100
5.3.2 Skupovne operacije
Ø Nad vrednostima tipa podataka BITSET mogu se primeniti sledeće operacije:
+
(unija skupova),
(razlika skupova),
*
(presek skupova),
/
(simetrična razlika skupova),
i sledeći relacioni operatori:
=
(proverava jednakost skupova),
#
(proverava nejednakost skupova),
<=
(proverava da li je jedan skup podskup drugog skupa),
>=
(proverava da li je jedan skup nadskup drugog skupa),
IN
(određivanje pripadnosti elementa skupu).
Slajd 81 od 100
5.3.2 Skupovne operacije
Primer. Sledeći fragment programa će ispisati Nejednako – sk2 podskup na ekranu.
VAR
sk1, sk2 : BITSET;
BEGIN
sk1 := {1, 2, 3}; sk2 := {1, 2};
IF (sk1 = sk2) THEN WriteString(‘Jednako - ’) END;
IF (sk1 # sk2) THEN WriteString(‘Nejednako - ’); END;
IF (sk1 <= sk2) THEN WriteString(‘sk1 podskup’); END;
IF (sk1 >= sk2) THEN WriteString(‘sk2 podskup’); END;
Slajd 82 od 100
5.3.2 Skupovne operacije
Ø Sledeće standardne procedure mogu se primenjivati nad standardnim
skupovima:
ü EXCL(sk, elem)
Izbacuje element elem iz skupa sk. Element elem mora biti prirodan broj iz
dozvoljenog opsega za tip BITSET.
ü INCL(sk, elem)
Ubacuje element elem u skup sk. Element elem mora biti prirodan broj iz
dozvoljenog opsega za tip BITSET.
Ø Upotreba standardnog skupovnog tipa je zbog male kardinalnosti njegovih
elemenata u svakodnevnom programiranju veoma ograničena.
Ø Primena tipa podataka BITSET mnogo je češća u takozvanom sistemskom
programiranju, gde se skupovne operacije nad vrednošću tipa BITSET
koriste za direktnu manipulaciju bitovima.
Slajd 83 od 100
Slajd 84 od 100
Ø Korisnički skupovni tip podataka definiše se nad nekim baznim tipom koji
mora biti redni tip podataka bez negativnih vrednosti.
Ø Moguće vrednosti skupovnog tipa podataka su elementi partitivnog skupa
podataka baznog skupa, tj. svi podskupovi nad datim baznim tipom: prazan
skup, svi jednočlani skupovi, svi dvočani skupovi, sve do skupa koji sadrži
sve elemente iz baznog tipa.
Po standardu i negativne vrednosti mogu biti elementi skupova.
Ø U daljem tekstu pojmom skupovni tip (podataka) označavaćemo tip
podataka skup.
Ø Pod pojmom skup podrazumevaćemo promenljivu koja je (nekog) skupovnog
tipa.
Ø Skupovni tip podataka je određen jedino svojim baznim tipom.
Slajd 85 od 100
5.4.1 Definicija skupovnog tipa podataka
Ø Opšti oblik definicije skupovnog tipa podataka je sledeći:
TYPE Skup = SET OF TipElementa;
pri čemu je TipElementa tip čiji će podskupovi vrednosti biti elementi
skupa Skup.
ProstTip
KvalIme
SET OF
ProstTip
NabrojiviTip
PodoblasniTip
5.10 Skup
Slajd 86 od 100
5.4.1 Definicija skupovnog tipa podataka
Ø Broj vrednosti tipa elemenata zavisi od realizacije Module-2, a najčešće je to
neki umnožak dužine procesorske reči.
Ø U slučaju TopSpeed prevodioca tip elemenata mora da ima manje od 65536
(216) mogućih vrednosti, u slučaju XDS prevodioca taj broj je 1048576 (220).
Ø Kardinalnost tipa elemenata kod drugih realizacija može biti mnogo manja,
ali obično je dovoljna da se može definisati SET OF CHAR.
Primer. U sledećoj definiciji moguće vrednosti tipa MaliSkup kreću se od praznog skupa,
preko skupova {1}, {2}, ..., {20}, {1, 2}, {1, 3}, pa do skupa svih vrednosti od 1 do 20.
Moguće vrednosti tipa VelikiSkup kreću se do skupa svih vrednosti od 0 do 65535.
TYPE
Celi = [1..20];
MaliSkup = SET OF Celi;
VelikiSkup = SET OF CARDINAL;
Slajd 87 od 100
5.4.2 Skupovne konstante
Ø Elementi skupa se mogu zadati proizvoljnim izrazima, ali je bitno da sve
veličine koje učestvuju u izrazu u trenutku pristupa skupu budu poznate.
Ø Vrednost izraza mora biti istog tipa kao i bazni skup nad kojim se definiše
skup.
Ø Elementi skupa zadaju se pojedinačno ili kao dijapazoni sukcesivnih
vrednosti, međusobno razdvojeni zarezima.
,
KvalIme
{
Izraz
..
Izraz
}
5.11 Skupovna konstanta
Slajd 88 od 100
5.4.2 Skupovne konstante
Primer.
VAR
sk1, sk2 : SkupCeli;
i, j : CARDINAL;
BEGIN
...
sk1 := SkupCeli{i..j};
sk2 := SkupCeli{i, j};
Ako je i=j, u oba slučaja će se sk1 i sk2 tretirati kao skup od jednog
elementa. Ako je i>j, skup sk1 je prazan skup.
ØKod korisničkih skupovnih tipova podataka se i ispred praznog skupa mora
navoditi ime skupovnog tipa.
ØPrazan skup bez imena tipa je prazan skup tipa BITSET.
Slajd 89 od 100
5.4.2 Skupovne konstante
Primer.
TYPE
Skup = SET OF [1..20];
VAR
sk1 : Skup;
sk2 : BITSET;
BEGIN
...
sk1 := Skup{};
sk2 := {};
Slajd 90 od 100
5.4.2 Skupovne konstante
Primer. Primeri nekih skupova.
TYPE
Dani = (pon, uto, sre, cet, pet, sub, ned);
Interval = [0..60];
SkSlova = SET OF CHAR;
RadniDani = SET OF Dani;
SkInt = SET OF Interval;
Znaci = SET OF CHAR;
VAR
sk : SkSlova;
rd : RadniDani;
cifre : Znaci;
vred : SkInt;
BEGIN
...
sk := SkSlova{‘A’..‘Z’, ‘a’..‘z’};
cifre := Znaci{‘0’..‘9’};
vred := SkInt{x, y, x+y, x-y, x*y, x DIV y};
Slajd 91 od 100
5.4.3 Skupovne operacije
Ø Sve operacije koje se mogu primeniti nad skupovima tipa BITSET, mogu se
primeniti i na korisničke skupovne tipove.
MODULE Analiza;
FROM InOut IMPORT WriteString, WriteLn, Read, Write;
TYPE
Slova = SET OF ['A'..'Z'];
Cifre = SET OF ['0'..'9'];
VAR
sviSam, sviSug : Slova;
sveCif : Cifre;
ch : CHAR;
CONST
prazan = Slova{};
samog = Slova{'A', 'E', 'I', 'O', 'U'};
sugl = Slova{'A'..'Z'}-samog;
cif = Cifre{'0'..'9'};
BEGIN
sviSam := prazan; sviSug := prazan; sveCif := Cifre{};
Slajd 92 od 100
5.4.3 Skupovne operacije
(* Primer. Program za pronalazenje prostih brojeva u
intervalu
[2..N] koristeci algoritam Eratostenovog sita.
Algoritam se sastoji u sledecem:
1) prvi element sita (intervala) je prost broj,
2) iskljuciti sve njegove umnoske iz sita,
3) pronaci prvi sledeci broj iz sita,
4) ponavljati korake 1-3 sve dok ima elemenata u
situ.
Resenje. Globalni izgled programa mogao bi se prikazati na
sledeci nacin:
inicijalizacija promenljivih;
REPEAT
pronaci broj kojim sito pocinje;
ukljuciti taj element u skup prostih brojeva;
WHILE umnozak broja <= N DO
iskljuci umnozak broja iz sita;
nadji sledeci umnozak
Slajd 93 od 100
Slajd 94 od 100
Ø U Moduli-2 (i u mnogim drugim jezicima) jednakost tipova zasnovana je na
imenima tipova.
Ø Dakle, dva tipa u Moduli-2 su ista ako imaju isto ime (a ne ako imaju istu
definiciju).
Ø Promenljive su istog tipa podataka ako su istog imenovanog tipa podataka ili
ako su deklarisane u istoj deklaraciji.
Ø Iako će principi utvrđivanja jednakosti tipova biti objašnjeni na nizovnim
tipovima podataka, sve ovde rečeno važi za sve tipove podataka u Moduli-2.
Slajd 95 od 100
Primer. U sledećoj deklaraciji nizovi brA i brB su istog (nizovnog) tipa.
TYPE
Niz = ARRAY [1..100] OF INTEGER;
VAR
brA, brB : Niz;
Primer. U sledećoj deklaraciji, nizovi brA i brB su različitog tipa, jer im se tipovi
različito zovu.
TYPE
Niz = ARRAY [1..100] OF INTEGER;
Niz1 = ARRAY [1..100] OF INTEGER;
VAR
brA : Niz;
brB : Niz1;
Primer. U sledećoj deklaraciji, nizovi brA i brB su istog tipa (jer su deklarisani u istoj
deklaraciji).
VAR
brA, brB : ARRAY [1..100] OF INTEGER;
Slajd 96 od 100
Primer. U sledećoj deklaraciji nizovi brA i brB su različitog tipa, jer su deklarisani u
različitim deklaracijama.
VAR
brA : ARRAY [1..100] OF INTEGER;
brB : ARRAY [1..100] OF INTEGER;
Ø Tipovi podataka koji se različito zovu jesu, međutim, isti ako su samo
preimenovani, a ne iznova definisani pod drugim imenom.
Primer. U sledećoj deklaraciji nizovi brA i brB su istog tipa, jer se ime Niz1 smatra
samo drugim imenom za Niz.
TYPE
Niz : ARRAY [1..100] OF INTEGER;
Niz1 = Niz;
VAR
brA : Niz;
brB : Niz1;
Slajd 97 od 100
Ø Može se učiniti da ovako definisana jednakost tipova u programskom jeziku
nije dobra.
Ø Međutim, ponekad programer želi da u suštini istom skupu vrednosti dodeli
različite uloge u svom programu, te da na njih primenjuje različite operacije.
Ø Na primer, i minuti i sekunde se mogu definisati kao podoblasni tip sa
vrednostima od 0 do 59, ali se vrednosti ova dva tipa ne smeju slobodno
mešati, niti dodeljivati jedni drugima.
Ø U takvim slučajevima je dobro da se tipovi podataka za minute i sekunde
razlikuju, iako im je skup vrednosti (a verovatno i skup operacija nad njima)
isti.
Ø Drugi karakterističan primer je slog od dva realna broja koji može da
predstavlja kompleksni broj i koordinate u ravni – i u tom slučaju programer
ne bi želeo da ova dva tipa podataka budu jednaka niti njihove vrednosti
kompatibilne.
Slajd 98 od 100
5.5.1 Imenovanje tipova podataka
Ø Uvedenom tipu podataka je dobro dati ime (umesto da se definicija direktno
koristi u deklaracijama promenljivih) iz sledećih razloga:
program može biti pregledniji,
kao što smo videli, to je jedini način da na više različitih mesta u
programu deklarišemo promenljive istog (uvedenog) tipa podataka,
formalni parametri u zaglavljima procedura (kao što ćemo tek videti)
moraju biti deklarisani imenima tipova podataka, a ne definicijama
tipova podataka.
Slajd 99 od 100
LOGO
“ Add your company slogan ”
PPTX: Teodor Najdan Trifunov 287/09
PMF Novi Sad
Departman za matematiku i informatiku
Download

Glava 5