Od sada programiramo u C-u: TURBO C 860300465X, 9788603004656 [PDF]

Zitiervorschau

Urednik

B R A NI MIR A VALIĆ Recenzenti

Mr. ZLATA TRUPČ:EVIĆ DUŠAN TRBOJEVIĆ Grafički urednici Ž ELJKO PRODANOVIĆ

ŽELJKA SAMBOLEK

Omot opremio

F E D O R LIČINA Lektor

MIROSLAV MALEZ

CIP - Katalogizacija

u

publikaciji

Nacionalna i sveučilišna biblioteka, Zagreb UDK 519.682 C ( 035 )

VULIN, Rajko Od sada programiramo II C-u: Turbo e

Vulin. - Zagreb: Školska knjiga, 1991. str. : ilustr. ; 24 cm. Kazalo.

ISBN 86-o3-00465-X

910725051

Slog i prijelom na r aču nal u

T & S - Zag re b

Tisak: "AUGUST ŠENOA"

-

Zagreb

-

/

Rajko

VIII, 336

Rajko

Vulin

OD SADA PROGRAMIRAMO U C-u Turbo C

ŠKOLSKA KNJIGA ZAGREB 1991

Predgovor

Knjiga Od sada }ll'ogramiramo II C-u nastala je \I težnji da se nadoknadi stalni ne dostata k knj i ga (na našem jezik u ) iz p o d r u čja programiranja i p r og ramsk ih jez i ka . K nji ga je konri p iran a tako da čitaora postupno uvodi u programsk i j ezik C. Kao p odl oga za učenje iskorišten je TURBO e Ver. 2.0. T U RB O C je inte­ gri ra n i pa ket ko j i sadrži p o t. punu i m plementa ci ju ANSI e s t. a nda rd a , omoguć uj e urectivanje, pre vo (le nj e i iz vrš a vanj e p r og rama II jedinstvenom radnom okruženju, što je vrlo p ogo dno u fazi u če nja . K nj i ga se sastoji od jed a n aes t p ogla v lja i jednog do d at ka. Na p o četk u s va ko g p ogla v lj a nalazi se u v o d, II koj emu je ukratko iznesena p rob l em atika poglavlja koje slijedi. Prvo

i p os ljednje p oglav lje , te

dod ata k odnose se na

p r ogra msk i p aket TURBO

C. Prema tome, ako čitalac ne upotreblj ava TURBO C nego neku drugu implemen­ tariju C-a, ta poglavlja može p reskoč iti . Drugo pog l a v lj e sadrži osnove e-a. Cilj tog p o gla vlj a je u p oz nava nje osnovnih jezika, počevši od gracte programa, deklaracije vari j abli , defi n ic.i je fu n krij a, p oziva fu n kr ija , pr i jenosa parametara, sintakse osnovnih naredbi i sl. U njemu se ne ulazi u p oje d i n osti pojedinih p ro b l ema , nego se nastoji u suženom opsegu prikazati moguć nost p rogr am skog j ez ika C, te ukazati na osnovne p roblem e koji će se z aseb n o obra(livati u narednim p oglav ljima. karakteristika

U os t a lim poglavljima (od tre ć ega do jedanaestoga) mnogo se detal jn ije ras­ p ra v lja o mogu ćnostima p rog r ams kog jezika C. U svim p ogl av ljima izraelena je nekolicina primje ra koji p otk re p lju ju opisanu problematiku. Primjeri su odabrani tako da se već i njih ovo m analizom može shvatiti bit p rob lema . U p o glav ljim a koja ob r a (luj u složeniju problematiku, na primj e r p ok azi v a či , složeniji tipovi po­ dataka i sl., postoje potpoglavlja koj a dodatno obra(luju najčešće grei;ke te uzroke i p os lj e d ice n asta n ka g re šaka.

Knjiga Od sada }ll'ogramil'amo u C-u n a m i j e n jena je i poslužit ć.e sv ima koji žele ste ći solidno z nan je o m ogućnostima p ro g ram s k og jezika C, odnosno pro­ gr amskog p a keta TURBO e Ver. 2.0. U knjizi se nast.ojalo u mjest o udomaćeni h eng lesk i h iskoristit.i što više naših odgovaraj u ćih riječi. Većini čit.alaca, k o j i se služe u gla v nom stranom literaturom, to će p oma lo i smetati. Me(lutim, ovim se na n eki način želi p otak nuti s t va ranj e standardnog informatič.kog rj e č ni ka . U prilog ovome

m ože se navesti primjer koje se do

prije

N adam

se

da je ovo prvo

rije

či računalo, koja se uveliko upotrebljava, a

nekoliko godina upotrebljavala isključivo

riječ

umjesto

kompjutor.

će knjiga naići na dobar prijem kod učenika i studenata. Buclllć.i izdanje, svi prijed lozi i sugest.ije II cilju daljnjeg poboljšanja knjige

da

dobro su došli. Zahvaljujem svima koji su mi pomogli

u

stvaranju ove knjige.

hvaljujem kolegama koji su mi svojim sugestijama ukloniti nejasnoće

u

tekstu te poduzeću

nesebično ustupilo računarsku opremu.

Zagreb,

u

srpnju

1991.

u

Posebno za­

fazi pisanja knjige pomogli

Mraz Elcktronik

iz

Zagreba, koje mi je

Autor

Sadržaj

Uvod, 1.

1.1.

1 . 2. 1.3. 1.4.

1.5.

3.

1

OPERATORI I IZRAZI, 51

OSN OVNE KAR AKTERISTIKE TURBO C-a, 5

3.1.

Sadržaj programskog paketa TURBO e, 6 Instalacija, 6 Pokretanje TURBO e-a, 8 Osnovni izbor, 9 Prozor za urec1ivanje programa,

3.2.

15 1.6. 1.7.

1.8. 1.9. 1.10.

2.

Prozor za ispis poruka, Mogućnost korištenja dvostrukog zaslona, 16 Pomoć (Help), 16 Vruće tipke (Hot ke y s), l! rec1ivač teksta (TURBO e EDITOR),

15

2.6.

2.9.

Argumenti

funkcij e

-

- Call by Value, 43 2.10. 2.11. 2.12.

Polja, 44 Globalne varijable, Sažetak, 49

3.6.

KONTROLA TOKA PROGRAMA, 75

4.1.

Naredbe i blokovi naredbi, 76 Jednost.ruka uvjetna grananja, 76 Višestruka uvjetna grananja, 78 Naredba switeh-ease, 81 Programske petlje , 86 Naredba break, 94 Naretlba continue, 95 Naredba goto, 96

4.2.

4.3. 4.4. 4.5.

32

4.6. 4.7. 4.8 . 5.

5.1. 5.2. 5.:3. 5.4. 5.5.

5.6. 5.7.

47

logičk i operatori, 65 Operator pridruživanja vrijednosti i izrazi, 68 Pretvorba tipova podataka, 69 Najčešće greške, 72

4.

19

Funkcije, 41

2.5.

64 Relacijski i

:3.5.

17

2.8.

2 . 3.

2.4.

3.8.

3.4.

3.10.

2.7.

2.2.

3.7.

3.3.

3.9.

OSN OVE PROGRAMSKOG JEZIKA C, 29

Identifikatori, 52

Ključne ri j eči, 52 Osnovni tipovi podataka, 54 Deklaracija varijabli, 57 Konstante, 59 Aritmetički operatori, 63 Operatori inkrement i dekrement,

3.11.

Kako početi, 30 Struktura e programa, 31 Analiza TUR B O e programa, Prevo'(1enje i izvršavanje . TURBO e programa, 35 Pronalaženje i ispravljanje grešaka, 37 Programska petlja for, 39 Simboličke konstante, 40

2.1.

OSN OVNI TIPOVI P ODATAKA,

5.8. 5.9.

99 Poziv funkcije u e-u, 100 Defi ni c ija funkcije, 100 Na re db a return, 103 Tipovi funkcija, 105 A rgume nt i funkcije, 106 Lokalne varijable, 111 Memorijske klase, 112 FUNKCIJE,

Rekurzija, 122 Prototip funkcije, 128

5.lD. 5.11.

Preprocesorske naredbe, 130 Ostale preprocesorske naredbe,

9.2.

sizeof operator, 255

9. 3.

135

9.4.

Uvjetni? operator, Zarez operator, 257 Pregled i prioritet operatora e-a, 258

9. 5.

6.

POLJA, 137

6.1.

6.5.

Jednodimenzionalno p olje, 138 Niz znakova, 141 Višedimenzionalno polje, 142 Polje niza znakova, 144 Inicijalizacija polja, 146

7.

POKAZIVAČI, 149

7.1.

Pojam pokazivača, 150 Deklaracija i inicijalizacija pokazivača, 151 Pokazivači kao argumenti fu n kci ja , 155 Aritmetika pokazivača, 156 Polja i pokazivači, 159 Pokazivači i niz znakova, 164 Polja pokazivača, 166 Pokazivači na pokazivače, 171 Problemi s pokazivačima, 172 Pokazivač tipa void, 175 Pokazivači i funk c ij e, 176 Pokazivači na fun k cije , 177 Argumenti fun kcije main O, 182

6.2. 6.3. 6.4.

7.2. 7.3. 7 .4. 7.5. 7.6. 7.7. 7.8. 7.9. 7.10. 7.11. 7.12. 7.13. 8.

8.1. 8.2.

8.4.

SLOŽENI JI TI POVI PODATAKA, 187

Struk ture, 188

Dinamičke strukture podataka,

8.5. 8.6. 8.7.

9.

9.1.

Polja bitova, 234 Unije, 237 Enumerirani tipovi podataka, Definiranje vlastitih tipova podataka, 241 Pretvaranje tipova podataka (casting), 242

239

DODATNI SKUP OPERAT ORA, 249

Operatori orijentirani na rad s bitovima, 250

ULAZ I IZLAZ, 259

10.1. Pristup standardnoj

ulazno/izlaznoj biblioteci,

10. 2. Meclusp remnički sistem

260

datoteka, 260

216 8.3.

10.

256

TC i pritisnuti tipku ENTER. Nakon t og a će se na zaslonu p ojavi ti tzv. osn ovni zaslon

(main menu screen), slika

File

Edit

Run

Comp ile

1 .2.

Project

Options

Debug

Break/watch

�-------= Edit -----��----=---� Line 1

Col 1

Insert Indent Tab Fill Un indent * C:IOIAME.C

1------ Message -------1

Ft-Help

FS-Zoom

F6-Switch

Slika 1.2.

F7-Trace

F8 -St ep

F9-Make

FtO-Menu

Osnovni zaslon (main menu screen)

Osnov ni zaslon sas toji se od četiri dijela: osnovni izbor prozor za urectivanje teksta i st atus linija prozor za poruke prevodioca

lUK

1.4.

Osnovni izbor

- kratki pregled zn ačenja vrućih t i p k i

9

(hot keys).

Opcije osnovnog izbora aktiviraju se istovremenim pri t iskom n a tipku ALT i t i p ku p očetnog slova osnovnog izbora. Veličina prozora za ure(tivanje teksta i prozora z a poruke prevodioca mijenja se pritiskom n a funkcijsku tipk u F5. Za izl az iz objedinjenog radnog okruženja po t rebno je i s t ov r em e n o pri­ t i snu ti tipku ALT i t ipk u X (ALT-X).

1.4. Osnovni izbor

Osnovni zaslon koji se pojav i n akon p okretanj a TURBO e-a je potvrda da se n alazimo u obje dinj enom radnom okruženju. U tom okru ženju prak­ tički nema potrebe za funkcijama operati vn og sistema. Naime, sve što je n eophodno za pisanje, prevo(tenje, izvođenje i ispravke programa dostupno je iz samog okruženja. (�ak i ka da je potrebno izvršiti funkcije koje su dos tupn e j('dino iz op e ra t i v nog sist em a, n a pr i mje r formatiranje diskete ili sL, nije potrebno napu štati radno ok ruženj e . Dovoljno je pozvati komandni pro ce s o r , i zvrši t i želj enu akc ij u i nakon toga se, n aredbom exit, ponovno vratiti u rad n o okruženje. Odabir pojedinih akcija osn ovnog izbora može se učiniti na d va nači na. Prvi se sastoji od aktiviranj a osnovnog izhora funkcijskom tipkom FlO, a zatim se s t reli c ama lijevo - desilo lzabere željena opcija. Drugi način dobi­ vanja željene opcije je da se istovremeno pritisnu t ipka ALT i tipka prvog slova opcije izbora. Na primjer, istovremenim pritiskom na tipku ALT i tipku E, pok reće se program �a ure(ti vanj e teksta (EDITOR). Značenja po­ jedinih opcija osnovnog izb ora d an a su u tablici Ll. U n as t av k u će se u kratkim cr t am a opisati sve o pcije osnovnog i do­ datnih izbora. Budući je praksa pokaz al a da se svi dovoljno brzo u p ozn aju sa m ogu ćnostima i funkcijam a pojedinih izb ora, neće s e posvećivati mnogo prostora d a bi se objasni1e s ve m ogu ćnosti pojedinih izb ora.

Postavljanje optimalnog o kru že nj a, prema veliči ni i za1ltjevu programa, opisano je II dodatku A. Promje n a radnog okruženja, posebno dijelova koji se odnose na memorijs ke modele i sl. preporuča se sam o poznavaocima značenja pojed ini h opcija, odnosno poznavaocima paketa TURBO C. Za p očet ak je sasvim dovoljno stand ardno radno okru ženje.

10

Osnovne karakteristike TURBO G- a

Izbor

Značenje

File

Učitavanje i pohranjivanje datoteka, rukovanje direktoriji m a, pozivanje komandnog procesora i izl azak iz TURBO Cokruženja

Edit

Pozivanje programa za uređivanje programa (TURBO CEDITOR)

Run

P revo(tenje i izvršavanje program a iz radnog okru ženja Prevođenje programa koji se n alazi.u radnom okru ženju

Compile Project

Aktiviranje i . deaktiviranje programa čiji se izvorni kod n alazi u više datoteka

Make

Stvaranje izvršne verzije programa čiji je izvorni kod u više datoteka opCIJa

prevodioca

i

Options

Postavljanje različitih povezivača (LINK ER)

Dehug

Postavljenje različitih opcija program a za pronalaženje i ispravljenje grešaka (DEBUGER)

Break/Watch

Postavljenje prekidnih izvršavanja programa

točaka

u

procesu

Tablica 1.1. Pregled i značenje opcija osnovnog izbora

File Izhorom opcije File otvara se prozor s dodatnim izborom za rad s da­ totekama i direktorijima, slika 1.3. Pojedine opcije, kao i II svim ostalim dodatnim izborima, biraju se korištenjem strelica gore - dolje. Opcija Load omoguć.uje u č.itavanje datoteka. Pretpostavlja se u čitavanje datoteka koje imaju dodatak (exten.'1ion) .C. Međutim , navo(tenjem punog pu t a (path) i imena datoteke može se učitati sadržaj bilo koje datoteke iz bilo kojeg di­ rektorija. Opcija Pick prikazuje listu od osam zadnje u čitavanih d atoteka. Izbor, odnosno u č. i tavanje datoteke obavlja se pomicanjem inverzno osvijet­ ljene linije i pritiskom n a tipku ENTER Izborom opcije New počinje se :

LI. Osnovni izbor File

11 Run

Edit

Compile

Pro j ect

Load Pick

. · F3 Alt-F3

Col l

Options

Debug

Break/watch

Edit -------....., Insert Indent Tab

Fill

Unindent * D: I DlAKE . C

lew Save

F3

Write to Directory Change

dir

Quit

Alt-X

OS shell

1----Fl-Help

FS-Zoom

F6-Switch

Message

F7-Trace

-------j

FS-Step

F9-Make

FlO-Menu

IUM

Slika 1.3. Dodatni izbor osnovnog izbora File

stvarati nova (l atoteka. Opcij o m Save se trenutni s adr žaj datoteke pohra­ njuj e u t eku ći direktorij, odnosno di sk . Opcija Write to om ogu ćuj e pohra­ nj ivanje trenutnog sadržaja u čitane datoteke pod nekim drugim imenom. Directory prikazuje sadržaj - t ek u ćeg direktorija. Change dir mij enj a t ek u ći direk t or ij . Op cij a OS s hell pokreće DOS-ov komandni procesor. Pokretan j em kom an d n og procesora mogu se izvršiti sve funkcije DOS ope­ rati vnog s i stem a . Prillljetit� d a se izb orom ove funkcije i d alj e nalazite u TURBO e o kru ž enj u . Naredba EXIT vraća stanje kakvo je hilo prije p ozi­ va komandnog p ro ces o r a . I na kr aj u , op cij a Quit predst avlja izlaz odnosno kraj rad a sa TURBO e-om . Najčešće korištenim opcij ama dod atnih i zb or a prid ruž ene su funkcijske tipke. Na pr i m je r , p r i tis k om na funkcij sku tipk u F2, u bilo kojem t renutku

u re (ti vanja programa, i z vrš ava se o pcij a Save, dok je za pokret anje ko­ m and n og procesora n eo ph odno prvo pozvati izbor File, a zatim izahrati opc ij u OS shell. Pritiskom na tipku izbor.

ESC,

II

bil o k oj em trenu tku, vraća se u osnovni

12

Osnovne karakteristike TURBO G-a

Run

i Compile

Odabiranjem opcij e Run osnovnog izbora po k reće se prevođenje, povezi­ se trenutno ure

Al t-F

Aktivira izbor < File>

Alt-O

Aktivira izbor < Options >

Alt- P

Aktivira izbor < Project >

Alt- R

Aktivira izbor < Run >

Alt-X

Izlaz iz TURBO C okruženja

Ctrl- F 1 Ctrl- F2

Uklju čuje pomoć (značka mora biti postavljena na ključnu riječ) - vrijedi samo za ure(uvač teksta Prekid izvršavanja programa - korak po korak način izvršavanja programa ( trace mode)

Ctrl- F:l

Prikaz stanja stoga (stack)

Ctr1-F4

Promjena vrijednosti zadane varijable ili člana polja (vrijedi za izvršavanje programa u modu korak po korak)

Ctrl- F7

Dodavanje nove varijable za praćenje promjene vrijednosti

Ctrl- F8

Postavljanje/uklanjanje prekidne točke

Ctl'l- F9

Stvaranje izvršne verzije i izvođenje programa iz T U RBO C okru ženja

Tablic.a 1 .2. Pregled

j

značenje vrućih tipki TURBO C-a

1. 10. Ureilivač teksta

(TURBO e EDITOR)

1 . 1 0 . Uređivač teksta

19

(TURBO

e

EDITOR)

Tu rbo e u r E'Ct i va č. t ek s t a pr i 1 ago (ten je p i s anj u s t r u k t u r i r an ih p ro gr am a . U ređi vač. radi au tom atsko u vlačenje teksta (auto-indentation) . To z n a č i d a

ć e s e n akon p ri t iska n a t i pk u E N T E R ( nova lin ij a ) zn a č ka pos t av i t i n a i s t u

kolon u n a

kojoj

p o č i nj e tekst p r e t h od n o g

u v l a če n j a d obije se tekst kao u

slj ede ćem

reda. Korištenjem

au to m a ts ko g

p rimjeru

Ovo j e p r imj er


< Poz ic i j a značke nakon prvog prit i ska na t ipku Pozic i j a zna�ke nakon drugog p r it i ska na t ipku < BackSpac e >

N aredbe z a b ri s anj e t e k st a ,

u č i t avanj e i pohranji vanje blokova

u č i t a van j e i poh ranj i vanj e d a t ot e ka i sl . pot p u n o su j e d n ake

tekst a ,

naredbam a ko j e

koristi tekst p ro cesor Wo rd star ili u služni p rogram S i cleKick . Prem a tome,

ako s t e u p oz n a t i s n ared ham a i mogućnos t i m a n avede n o g t eks t pro ces o r a ili u s l u ž n og program a sloh o d n o možete preskočiti ovaj dio p ogl av lj a . Ako II bilo kom t ren u t ku

ni s t e

s i g ur n i II stečeno zn anj e pri t i s kom n a

e u r e (ii vač. t eks ta možete veom a b r z o nau či t i i koriš tenjem pomoći . Zbog toga u ovom pogl avlj u nije n ačinjen d e t alj an opis svih mogućnosti T U RB O e uređivača teksta. tipku F l p oz ov i t e p om o ć . D akle, T U RB O

jed n os t av n o i

1 . 1 0 . 1 . Unos , izmj ena

i p ohranj ivanj e t e ks t a

Po k r e t an j em T U R B O e-a au t o m a ts ki se ak t i v i r a o s n o v n i i z b o r . Prij e n ego počnemo unos ili i zmjenu teksta pot re h n o j e aktivirati ure(ii vač tek­ s t a . Urc(iivač t eks t a može se ak ti v ir a t i na dva n ačina. P rvim se n ačinom u i zb o r u File od abere op cij a New. Drugi n a č i n jest d a se izahere op cij a osnov n og izbora Edit . U klju čivanjem uremjesec. rodjendan->godina); 1* poziv funkcije definirane u prethodnom primjeru *1 1* varijabla rodjendan deklarirana je kao *1 1* pokazivac i adresni operator &: nije potreban *1 korekcija (rodjendan);

printf ("\n

Podaci

poslije korekcije => %d. %d. %d.". rodjendan->dan. rodjendan->mjesec, rodjendan->godina);

} Rezultat

izvršavanja programa. je:

8.1. Strukture

207

Unesi podatke o datumu rodjenja :: ------------------------------------------------------------------Dan 30 4 Mjesec Godina 1964

Podaci pr1Je korekcije

=

>

Podaci poslije korekcije

=

30. 4. 1964. > 1. 5. 1964.

Pokazivač na s tr u k t u ru koji funkcija vraća naredbom

return

mora odgo­

varati tipu definirane funkcije. To znači da se strukturna varijabla

u

funkciji

uci taj _podatkeO ,

rodj endan

mom deklarirati kao pokazivač na strukturu

tipa datum. Gornji primjer može se riješiti i na drugi naCln, funkcija koja vraća

struct datum

{

strukturu. Preure(teni

tako

da se definira

program glasi:

ucitaj_podatke C)

static struct

datum

rodjendan;

prinU (II\n Unesi podatke o datumu rodjenja : : "); print! (II\n ==================================" ) ; print! (II\n Dan : ); scan! ("%d". rodjendan.dan); II ) ; scanf ("%d". rodjendan.mjesec); print! (" Mjesec "

print! (" Godina

"); scanf ("%d". rodjendan.godina);

return (rodjendan);

} main ()

{

void

korekcija (struct datum *);

struct datum

rodjendan;

struct datum

ucitaj_podatke (void);

1* podaci o rOdjendanu *1 rodjendan

=

ucitaj_podatke ();

printf (II\n Podaci prije korekcije

=

> %d. %d. %d.".

rodjendan.dan. rodjendan.mjesec. rodjendan.godina);

208

Složeniji tipovi podataka

/* varijabla nije deklarirana kao po k az ivac */ */ /* adresni operator t neophodan

korekcija {trodjendan):

}

8.1.7.

printf ("\n Podaci poslije korekcije = > Y.d. Y.d. Y.d.", rodjendan . dan. rodjendan.mjesec, rodjendan.godina) i

Pokazivač kao član strukture

Budući da član strukt ure može biti hilo koji definirani ti p , nema razloga kao član strukture ne pojavi pokazivač. S pokazivačem kao čl anom strukture post u p a se potpuno isto kao i sa samostalnim p okaz iv a či ma . To znači da se pokazivaču prije korištenja mora pridružiti adresa.

da

se

Strukturu datum iz p r ethodnih primje ra deklarirat ć em o tako da su članovi strukture pokazivači na cjelobrojne vrijednosti: struct

datum

{ int

int int

*dan; *mjesec; *godina;

};

Budući da su varijahle d an, mjesec, godina čl anov i strukture, za pristu p pojedinoj varijahli Ulora se koristiti točka op e rat or . Funkcija za unos po­ dataka iz prethodnog primjera koja koristi deklariranu strukturu glasi: / * funkcija za unos podataka spredeklariranom /* strukturom datum

*/ */

unos_podataka O

{ struct datum rodjendan: int

d,

m.

g;

printf ("\n Unesi dan, mjesec i gOdinu rodjenja : : II); printf ("\n :;:;:;:;:;:;================================" ) ;

209

B.l. Strukture print! (lI\n Dan printf ("\n Mjesec printf ("\n Godina

If); scan! ("%d". td); II); scan! ( "% d ". tm); tl); scanf ("%d" , tg);

1* pridruzi adrese *1 rodjendan.dan = td; rodjendan.mjesec = tm; rOdjendan.godina = tg;

}

Naredbama rodjendan.dan = td; rodjendan.mjesec = tm; rodjendan.godina = tg;

članovima strukture pridružuju se adrese varijabli d, m, g.

Prikaz strukturne var ijable rodj endan u memoriji može se prikazati kao

rodjendan

dan mjesec godina - -

I

30

d

4

m

1964

g

Korištenjem unarnog op erator a * može se pristupiti sadržaju memorije na koj u p o kazuj u pokazivači unutar strukture. Izraz day

=

*(rodjendan.dan);

pridružuje varij abli day sadržaj s a d re se na koju pokazuje čJan strukturne varijable dan. Budući da točka op erator ima veći prioritet od * operatora zagrade sc mogu izostat1žti. Veoma je bitno razlučiti razliku između pokazivača kao člana s trukt ure i člana st7'ukturc na koju pokazuje pokazivač. Izrazom

210

Slože.niji tipovi podataka

(*rodjendan).dan

pristupa se članu strukturne varijahle

što

se

može prikazat i kao

n a koju pokazuje pokazivač rodjendan,

rodjendan . dan mjesec.

operator . ima veći priori tet od operatora *, zagrade neophodne. Ako se zagrade izostave i nap i š e izraz

Budući da

slučaju

su ovom

*rodjendan.dan

tada

vrijed nosti na koju pokazuje pokazivač *dan koji je član varijahle rodj endan, što se može prikazati kao

se pristupa

strli kturne

rodjendan

:;n

:

--��------------r---- - -e-s-e-c--

340_

__________

�

�

____

Adresa (,·.lana strukture na kOjH pokazuje pokazivač *rodjendan je adresa_elana

=

�rodjendan->dan;

dok je adresa na koju pokazuje član strukture rodj end an

211

8.1. Strukture 8.1.8. Samoreferentne strukture

Pod pojmom samoreJC1'cntna st7'uktura podrazumijevamo strukturu koj a sadrži član ili ('lanove koj i su pokazivači na strukture istog tipa kao deklari­ rana struktura, Samoreferentne strukture često se na zivaj u i rekurzivne strukture. Za razliku od var ij abli i polja za k oja se au t o m a t sk i zauzima m em o ri ja , samoreferentnI' strukture najčešće zahtijevaju posebne fu nk cije za zauzi m anje odnosno oslobadan, xl.s1jedeci->mjesec, xl.s1jedeci->godina);

1* treci element liste *1

printt ("\n Treci element liste: Y.d Y.d Y.d", xl.s1jedeci->sljedeci->dan, xl.

sIj edeci->sljedeci->mj esec ,

xl.s1jedeci->sljedeci->godina);

} Organizacija povezane liste iz danog primjera može se slikovito prikazati kao na slici 8.1. Bud lIć.i da postoji veza između elemenata liste, vrijednostima pojedinih članova elemenata može se pristupiti preko prethodnih elemenata liste. Tako se vrijednostima članova zadnjeg elemen ta II listi može pristupiti na više načina:

x2. dan

ili

8.1. Strukture x3.s1jedeci->dan x1.sljedeci->sljedeci->dan

dan

mjesec godina

30 4

215

ili

Xl

1 96 4

29 X3

dan

4

mjesec

1964

godi na 1

X2

5

1964 NULL

-h

Slika 8.1.

Izraz x3.sljedeci->dan;

z n ač i : P ro čit aj vrijednost č.lana strukture dan na koju pokaz uje pokazivač sIjedeci j"z p r et h odne strukture. Prema tome , rezultat izvršavanja navedeuog programa je: Prvi element liste Drugi element liste Treci element liste

30 4 1964 29 4 1964 1 5 1964

Za razliku o d polja, el e m e nti liste nisu i

memoriji sekvencijalno.

ne

moraju biti zapisani u

Veličina m e m orij e koju zauzima povezaua lista iz prethoduog primjera. o drectena je b roj em elemena.ta u listi. Buduć.i da su elementi liste statičke

216

Složeniji tipovi podataka

stru ktu re, m em orija se z auzi m a definicijom struk turnih varijabli. Broj ele­ me n at a u lis ti ograničen je b roje m definiranih strukturnih varijahli. Iz toga proi zl azi da se broj elemenata u listi mora o dre dit i u n a prijed . U slučaju da se za zapi s p o d ata ka ne iskoriste sve definirane varijabl e , dio memorije zau ze t d e fi nic ijo m strukturnih var ijabli ost aj e n eiskorišten . Da bi se izbjegl e takve situacije koriste se dinam ičke st rukt ure po­ d at aka. One omogućuju z auzi m anj e i oslobađanje m em orij skog prostora ovisno o b ro j u p o dat aka koji se zapisuju u memorij u . Dinamičke stru kture gl avlj u.

8.2.

Dinamičke

pod at aka

obra(tene su

det alj nij e

u n a redn o m po­

strukture podataka

R asp ol oži v i me morij s ki prostor veoma je važan resurs, p ogo t ov o

u v i še­ sustav i ma . P rogrami koji o periraj u s velikim b roj em p o d ataka zauz imaj u m em ori ju i samim tim onemogu ćuj u p okre­ tanj e drugih pr ogram a i procesa. Di namički m zau zim anjem i oslohađanjem memorije d aj e se mogućnost efika.'inog iskorištenja memorije. Veli čina za­ uzetog prostora u tom sl učaju ovisi o stvarn o m, a ne o pred viđenom broju podataka. Osim efikasnog kori štenj a m em orij skog prostora dinamičke strukture podataka kao i pokazivači imaju i d ru ge prednosti, kao što su hrzina pri stupa p o d aci ma, jednostavno proširivanje b roja p o d at aka i sl. Me(111tim, nepažlji vo rukovanje dinamičkim strukturama može prouzroč.iti nepredvi(tene zav rš etke programa.

procesorskilll'i višekorisničkim

dinamičkih struktura p o dataka objasnit će se na p r i mjer i m a lista i binarnih stabala. Tako đer će bit i objašnjene i funkcije zauzima (malloc O), odnosno osloba(1a (free O) memorijski

Stvaranje

povezanih kojima

prostor.

8.2.1.

se

Funkcije mallocO, reallocO

i

free{)

Zauzimanje mem orij e pri li kom definicije globalne varijahle ili prilikom .deklaracije polja, je stvar ko j u obavlja prevod ilac. Z auz i m anje mem or ije za dinamičke strukture pod a t aka lllora obaviti sam progr am er . M em or ija se u C-u zauzima pozivom fun k cij e mallocO. Opći oblik fun kcije mallocO

Je:

8.2. Dinamičke strukture podalaka

217

void *lllalloc(veličil1s)j

Funkcija

vraća pokaz i v ač tipa void, što

znač i

da se može pridružiti bilo

kojem tipu pokazivača. Na primjer, naredbom i

=

(int

.

) malloc(sizeof(int»i

za.uzima

se m emor i ja po t rebn a za zapis cj elobro jne

dovolj no

memorije fu nk cija

uzete mem orije

pridružuje

vrijednosti i

adresa za­

se poka.zivačkoj varijabli i. Veličina zauzete memorije ov is i o ti pu podatka. Operator sizeof v raća veličinu memorije potrebnu za zapis hilo kojeg defin i rang tipa podatka. U sl u čaj u da nema

mallocO vraća NULL pokaz i vač .

U sl u č aj u da v eličina zauze te memorije nije dovol j na za s mje štaj svih podat aka , može se izvrši t i dodatn o zauzim a nje r as položive memorije. Ono se hitn o razlikuje od ponovnog z au z i m a nj a memorije. N ai me , novim zauzi­ maujem memor ij e svi podaci, z api s an i u pre t ho dno zauzetom dijel u memo­ rije, su iz gu bljen i . Dodatni m zauzim anjem ra spol ožive memorije svi podaci os t aju sahlvani. Funkcija koja omogu ć uje dodatno zau zim anje rasp olo žive memorije u C-ll je reallocO. Opći ohlik funkcije je: void *l"calloc(pokazivac, velieina); A rg u m ent pokazivac

odre(tuje za koji p o d atak se obavlja dodatno zauzi­ memorije, dok se arglllllentom velieina određuje koliko se dodatne m e m orije z ah tij eva. Svakako da se funkci j om reallocO može i sm anji ti veličin a z au zete m emorije . U tom slučaju programer je sam o dgovoran za gu bit ak odre(lenih podataka. manje

Neprestanim zauzimanjem. mem orije , bez o bzira na njezinu veličinu, raspoloživa mem orij a bi se veoma brzo i scr pil a . Zbog toga se memo rija koja je zauze t a nepotrebnim podacima, osloha(la. O slob ađanje dijela zauzete memorije obavlja se pozivom funkcije freeO. Opći obli k funkcije freeO je void free(void *pokazivac);

A rgum e nt funkcije pokazivac sadrži adresu bloka memorije koji se oslobađa. Argument fu n k cije je t ipa void, što zn a č i da funkcija prih va ća pokazivač na

bilo

koji

tip podataka. Pri tome je

dobro eksplicite zadati o kojem se t i pu

pokazivača radi (korištenjem cast o pera t or a

zauze t e memorije

iz

O).

Na primjer, oslobadan = d; novi_ el ement->mj e s ec = m; n o v i_ e l ement->godina = g; n o v i_ e l ement-> slj edeci = KRAJ_L ISTE;

1* da li j e nov i_element prv i u li s t i *1 if (p oc etak_ l i s t e == KRAJ _L I STE) poc etak_l i s t e = kraj_li s t e = n o v i _ el ement; else

{ 1* zadnj i elem ent li s t e pokazuj e na novi e l em ent *1 kraj_Ii s t e-> sl j edeci = novi _ elemen t ;

1* novi el ement postaj e zadnji kraj_li s t e

=

u lis ti *1 n ovi _ element ;

} printf ("\n Unos novih p odataka (d/nL_" ) ; ch = g etche( ) ; } 1* kraj uno sa vrati pokazivac na prvi element u li sti *1 r eturn (poc etak_lis te ) ;

}

Funkcija kreiraj _listu O

stvara povezanu listu i vraća pokazivač na Bitno je uo čiti da se pri dod avanju novog elementa prvo moraju riješiti pokazivači. To znači da se zadnje m elementu u listi prvo mora pridružiti pokazivač na novi element liste, a zatim taj element liste proglasiti zadnjim II listi. Stvaranje i dodavanje novih elemenata u listu se

početak liste.

221

B.e. Dinamičke slr1tkture podataka može

prikazati

kao:

pocetak...liste I

novLelement -

I I I I

-L

Ispis sadržaja liste Funkcija

ispis_sadrzaja O

ispisuje

sadržaj li st e. U fu nkciju je dovoljno element II li st i odrNten je

prenijeti pokazivač na. prvi el em ent liste. Z a.d nji pokazivačem KRAJ_LISTE. 1*

i s pi s sadrzaja li s t e *1

void i spi s_sadrzaj a_l is te (struct

d atum *poc etak_li s t e )

{ struct datum int i;

*i spi s:

1* i s pitaj d a li l i sta uopc e postoji *1 if (poc etak_ l i s t e == KRAJ_L ISTE )

{ print! ("\nLi s t a ne postoji ili greska m em orije " ) ; return:

} 1* i s p i s une s enih podataka *1 printf (" \n Sadrzaj l i s t e : : "); printf ("\n============================" ) ; i = O; for (i s p i s = poc etak_l ist e: ispi s != KRAJ_L ISTE; i spi s = i spi s-> slj edeci )

{

i++: pr intf ( " \n Datum rodj enj a Y.d. o s ob e : Y.d. Y.d. Y.d.".i. i s p i s->dan.

222

Složen iji tipovi podataka

i s p i s->mj e s e c, i s pis->godina ) ;

} pr intf ("\n\n Kraj l i s t e .....

"

);

}

Dodavanje novih elemenata u listu

Dodavanje novih elemenata prikazano je funkcijom unos_novog_elementaO. Elementi se dodaju na kraj liste, premda se funkcija može preoblikovati tako da se elementi uhacuju iza ili ispred zadano� elemenata. Postupak za ubaci­ vanje elementa iza zadanog elementa u listi je 1.

zauzmi memoriju za novi element

2.

učitaj podatke za novi element

3. pronacti

element(test) iza kojeg se ubacuje novi element

4. riješi pokazivač.e: nov i_ e lement->sl j edeci = t est-> s lj edec i ; t e s t-> slj edeci = nov i _ e l ement;

što se može prikazati kao

pocetak�iste I

test ,--+

L -

-

,, , , , , , J

J-

novLelement Ako

funkdji.

je zadani

element

zadnji

u

listi, postupak je

isti

kao

II

prikazanoj

8.2. Dinamičke strukture podataka 1* dodavanje novog elementa na kraj liste *1 v o id uno s_novog_ el ementa (struct datum *pocetak) { s truct datum *novi_ el em en t, *kraj_list e: int d, m, g ; nov i_el ement= ( struct datum *) malloc ( sizeof ( struct datum»; if (novi_element == IULL) { pr intf ( " \n lema dovoljno memor ije .... . II); return : }

1* unos vrijedno sti novog e l ementa l is t e *1 printf pr intf printf printf printf

( " \n Un es i t e podatke o datumu rodjenja: " ) : ( " \n = = = ===== = = = = = = = = = = = = = = = = = = = = = = = = = = " ) : ( " \n\n Dan II): s canf ("Y.d " ,lcd ) : ( " Mjesec II ) : s canf ("Y.d " ,Icm ) : ( " God ina : lt ) : scanf ("Y.d " ,lcg ) ;

novi_ el ement->dan = d ; nov i_el ement->mjese c = m ; nov i_el ement->godina = g : nov i_ e l ement-> s lj ed e c i = K RA J_L I STE ;

1* pronadji kraj l ist e *1 for (kraj_l i st e = poc·etak ; kraj_ l i s t e->slj ede c i != KRAJ_LISTE; kraj_ l i st e = kraj_ l i s t e->slj ed e c i ) : 1* zadnji el ement p� kazuje na nov oun eseni el ement *1 kraj_l ist e-> s ljed e c i = nov i_ e lement; 1* novouneseni el ement zadnji u l ist i *1 kraj_l i s t e = novi_element ; }

Pretraživanje liste Lista se pretražuje usporedhom zadanih podataka s podacima svakog ele­ menta liste. Budući da je jednostruko povezana lista sekvencijaIna, u funkciju

se mora prenijeti pokazivač. na prvi element liste.

224

Složeniji tipovi podataka

1* pretrazivanje liste *1 void pretrazivanje_Iiste(struct

datum

*pocetak)

{ struct datum *testi int d . m. gi

pr int f printf pr intf pr intf printf pr inU

("\n Pretrazivanj e liste : ")j ("\n = = =========== = ======== =")j ( " \n Unesite podatke o datumu rodj enj a " ) ; ")j s e anf (" Y.d" . td); (" \n\nDan ")j scanf ("Y.d" . b)i ("Mjesec ( " Godina " ) i scani (·�Y.d" . tg) i

1* pret raz i vanje liste *1 for (test = pocetakj test != KRAJ_LISTEj test = t e s t - >slj edeci)

{ if (test->dan

{

--

printf ( "\n return;

d II test->mjesec == m II te st->go dina == g) Podat ak je u

} } pr inU ("\n Podatak nije

II

l ist i

");

listi");

} Brisanje elemenata liste

pojedi n og elt'llIenta

listi zahtijeva dvije operacije. Prva je pro­ nalaženje zadanog element a II list i, a druga oslobađanje memorije koju je> zauzimao ohrisani element. Brisanje odnosno izhacivanje, elementa iz liste znači da će prethodni elelllt'nt pokazivati n a n aredni element liste koji slijedi iza izbačenog elementa. N akon toga nema ni jednog elementa II listi koji hi pokazivao na iz b a čeni element. Prema tome, o n nije više d o s t u pan program ll. Zbog toga je dio memorije koji on zauzim a d ob ro osloboditi. Da Brisanje

II

m ora se deklarirati privremeni pokazivač hriše. U navedenoj funkciji to je pokazivač temp. Situacija je uešto drukčija kada se hriše prvi element 11 listi.

hi se memorija mogl a osloboditi, na element Uste koji se

1* brisanje elementa iz liste *1 void brisanje_elementa_iz_liste(struct datum *pocetak) {

225

8. 2. Din a mičke strukture poda t aka struct int printf pr intf printf printf printf p r intf

datum * t e s t , *t emp ; d , m , g , redn i _broj

=

O;

( " \n Br i s anj e el emenata l i s t e : " ) ; ( " \n============================ " ) ; ( " \n Podac i struktur e ko j a s e izbacuj e : " ) j ( " \n\nDan ) ; s canf ( " %d" , a: d) i ( " Mj e s e c " ) ; s canf ( " %d " . a:m) ; tl ) ; s canf ( " %d " • .tg) ; ( " Godina "

1* pronadj i zadan i el ement *1 for ( t est = p o c et ak ; t e st ! = KRA J_LI STE ; t e s t = t e st->slj ed e c i )

{ r edni_broj ++ ; 1* t emp pokazuj e na j edan e l ement i spred t e s t *1 t emp = t e st->slj edec i ; 1* da l i j e to prv i e l ement u l i s t i *1 if ( t e s t ->dan == d tt t e st ->mj e s ec = = m ta: t e s t->godina == g ta: r edn i_broj == 1 )

{ 1* promij en i pokaz ivac prvog e l ement a l i s t e s t art = t emp ;

*1

1* o s lobodi memor i j u e l ement a koj i s e br i s e *1 fr e e « s truct datum * ) t e s t ) ; return ;

} if ( t emp->dan == d tt t emp- >mj e s e c == m tt t emp->godina = = g )

{ 1* pronasađ zadani el ement *1 t es t - > s l j ed e c i = t e s t - > s lj e d e c i - > s l j edec i ; 1* o s lobodi m emor i j u obr i s anog el ement a *1 free « struct datum * ) t emp ) i return ;

}

}

}

B risanje el em en t a li ste može se prikazati kao

226

Slože n iji t ipovi poda taka

p o c et alel i st e t e st

�

-

-

t emp

-

-

-

-

I

l

free ( )

o slobodi dio memorij e ovđg el ementa N an·dni primjer daje prikaz osnovnih operacija n ad jednostruko poveza­ nim listam a. Primjer koristi navedene funkcije. Operacija se bira II funk ciji menu e ) . 1* o s n o vn e opera c ij e nad j ednos t ruko pov ezanom l i s t om * 1

int menu ( v o i d ) { i zbo r ; i nt 1 * obr i s i zaslon * 1

clrs cr O ;

* * tt ) ; - - - - - - - -- - - - - - - - - - , ) ; 1 . ) S t v aranj e l i s t e " ) ; ; Ispis s adrzaj a l i s t e " ) 2. ) 3 . ) Unos novog e l ement a " ) ; 4 . ) Pretraz ivanj e l i s t e , , ) ; S. ) B r i s anj e e l ement a l i s t e " ) ; 6 . ) Kra j rada __ " ) ;

pr intf ( " . . pr intf ( " \ n printf ( " \n pr intf ( " \n p r int f ( " \n pr inU ( " \n prinU ( " \n pr i n t f ( " \n

OSNOVNE OPERA C I J E

.

s c anf ( "Y.d" .tizbor) ; return ( izbor) ; •

}

void main ( v o id ) { 1* pr o t ot ip o v i f unkc i j a *1 struct datum *kr e i ra j _ l i stu ( v o i d ) ; void ispis_ sadrzaj a_l i ste ( struct d at um * ) ; void uno s _novog_elementa ( struct datum * ) ;

8. 2. Dinamičke s trukture pod a t aka

227

v o id pretrazivanje_l iste (struct datum * ) ; v o id brisanje_elementa_iz_ liste (struct datum * ) ; int menu (vo id) ;

int izbor_operacije ; int kreirana = O ; char ch ; do

{

switch ( izbor_operacij e

{

=

menu ( »

case 1 : if (kre irana -- 1 )

{

}

pr intf ( "\n L ista vec stvorena ! ! " ) ; pr intf ( "\n Zel ite n ovu l istu ? (d/n L_ ") ; ch = getche O i if (ch = = ' n ' I I ch = = ' N ' ) break ;

printf ( " \n * * STVARAN JE NOVE LI STE ** ") ; /* p okazivac na pocetak liste */ start = kre iraj _listu ( ) i kre irana = 1 ; br eak ; case 2 : printf ( "\n * * I S P I S SADRZ A J A LISTE ** " ) ; i s p is _sadrzaja_liste (start) ; printf ( " Za nastavak prit isnuti b i l o koj u t ipku"); getch O ; break ; case 3 : ; pr intf ( " \n * * UNOS NOVOG ELEMENTA * * I I ) unos_novog_elementa (start) ; break ; case 4 : pr intf ( "\n * * PRETRAZ I VANJE LISTE * * " ) i pretrazivanje_ l iste (start) ; pr intf ( " Za nastavak pritisnuti b il o koja t ipku ") ; getch O ; break ; case 5 : printf ( "\n * * BRISANJE ELEMENATA L I STE * * ") ; brisanj e_elementa_ iz_l iste ( start) ; break ; case 6 : pr intf ( "\n\n . . . . k r a j . . . . . . . " ) ; •

228

Složeniji tipovi podataka break ;

default : printf ( " \n Pogresan izbor ! ") ; pr intf ( " Za nast avak pr it i snut i bilo ko j a t ipku" ) ; get ch O ; break ;

}

} } while ( izbor_operac i j e

!=

6) ;

Rezu1tat izvršavanja programa je: ** OSHOVHE OPERACI J E * *

1. ) 2. ) 3.) 4. ) 5. ) 6.)

Stvaranj e l i s t e I sp i s s adrzaj a l i s t e Un os novog el ementa Pretrazivan j e l i s t e Brisanj e el ementa l i s t e Kraj rada __ 1

* * STVARANJ E HOVE LISTE *. Un e s i t e podatke o datumu rodj enj a :

= ====== === ===== == ===== == === === = = = = Dan 1 Mj e s e c 1 1990 God ina Uno s nov ih podataka {d/n ) __d

Dan Mj e s e c

Godina

2 2 1990

Unos nov ih podat aka ( d/n) __n .* I S P I S SADRZA JA LISTE .*

Sadrzaj l i s t e :

-------- ------Datum r odj enj a 1 .

osobe

Datum rodj enj a 2 .

os ob e

Kraj l iste . . . . .

1. 1. 1990 . 1 990 .

2. 2.

8. 2. Dinamičke strukture podataka **

UNOS IOVOG ELEMEITA

229

**

Unes i t e podatke o datumu rodjenj a : = = = ======================= = ====== = Dan 4 Mj esec 4 Godina 1 990

**

I S P I S SADRZAJl LISTE

••

S adrzaj liste : - - - - - - - -- - - - - - - - -----------

Datum rodjenj a 1 . osobe Datum rodj enja 2 . osobe Datum rodjenja 3 . osobe

1 . 1 . 1 990 . 2 . 1 990 . 4 . 4 . 1 990 . 2.

Kraj l i ste . . . . .

••

PRETRAZ IVlij E LISTE

••

Pretrazivanje liste : === = === = ============ Unesit e podatke o datumu rodjenja : Dan Mjesec Godina

2 2

1 990

Podatak j e u listi

**

BRISAXJE ELEMElATA LISTE • • =========== = ======= == =====

P odaci st rukture koja se izbacuje : Dan Mjesec Godina **

2 2

1 990

ISPIS SADRZA J! LISTE

••

Sadrzaj list e : - - - - - - - -- - - - - --------- -----

Datum rodjenja 1 . osobe

. . 1.

1.

1 990 .

Složeniji tipovi podataka Datum rodjenja 2 . osobe

4.

4.

1 990 .

Kraj liste . . . . .

Fu n kc ij a za

ispis sadržaj a p ove z a ne lis t e može se

riješiti i rekurzijom :

1* funkcija za ispis sadrzaja liste * 1 rekurz ivna metoda *1 1* vo id ispis_sadrzaj a_liste (st ruct { struct datum * ispis ;

}

datum * pocetak_liste)

ispis = pocetak_liste ; printf ( "\n Datum rodjenja osobe : Y.d . Y.d . 'lod . " , ispis->dan , ispis->mjesec, ispis->godina) ; if « ispis = pocetak_liste->sljedeci) 1 - KRA J_LISTE) ispis_sadrzaja_liste ( ispis) ;

8. 2 . 3 . B i narna stabla

povez anih lista dinamička stru k t ura podataka može obliku binarnog stabla. Oblik bi n arn o g s t abla m o ž e s e

O s i m jed n o s t ruko

se

o rgan i z i ra t i i

II

slikovito prikazati kao

P rije nego kff'nemo na ohj ašnjenje strukt ure i k reiranj a binarnog s t abla pot r('bno je u s voj i ti o d re cten u terminologiju vezanu za binarna stabla.

8. 2. Din am ičke strukture poda t aka

mora imati dva pokaz i vača. Jedan k o j i lijev i cleme n t i jedan ko ji p okaz uje na des n i element. Element stabl a koji se nal azi na n ajvišoj razini n aziva sc kor ijen (root ) . Preko ko r i­ jena s t abl a pri s t u pa sc ostalim el e m e n t i m a koji sc nalaze na nižim razinam a. L ijevi i d e sn i elem enti pred s t avlj aju lij e vo i d esno podstablo . S vaki elem e n t bin arnog stabl a

pokazuje

na

Za prikaz din amičkih struktura po d a t aka organiziranih u obliku bin a­ n og stabla , riješit ćemo j e dan jednostavan zadatak . Cj el o b r ojne vrijed nosti po(l at aka, koje se u n ose s tastature, treba organizirati u obliku bin arnog s t abla prem a slij ed ećem pravilu : S v i podaci k o j i su m anji od p rethodn o un­ e s e nog smje š t aju se 11 lijevo podst ablo, a p o d aci veći ili jednaki od prethodno r

u nesenog smje š t aj u se II desno

podstablo. Za

rj ešenje n avedenog zadatka

potrebno je p ravilno d eklarirati odgovarajući element, odnosno samorefer­

entn u s t r uk t u rn . Deklaracija elem enta bin ar nog stabla glasi : s h'uet

{

iut

};

eLh i u -.S t vl'ijl�(lllos t j

s h'uet

eLbiu ...s t

*lijevij

s trud

eLhiu ...s t

*deSllij

što se može p r i kazati kao v r ijed n ost d es n i

lije v i

Stvaranje binarnog stabla ' Za s t varanje b i nar n og stabla

pogodno je koristiti metod u rekurzije. Funk­ kreiraj _ stab l o ( ) v raća p o kaz i va č na korijen binarnog stabla. Argu­ men t i funkcije S11 p okaziva č n a čvor stabla više razine i te v rij e d nost elem enta koj i se trcha i n tegri rat i II b i n arn o stablo, Program sko rješenje n avedenog cij a

zad atka

je:

1* stvaranje binarnog stabla *1 struct

el_bin_st

*kre iraj_stablo (priv, v ) struct el_bin_st *priv;

Složeniji tipovi poda taka

232 {

v I·

int

1* naj n iza raz ina ? *1 if ( p r i v == NULL)

{

}

1* pokaz ivac na nov i e l ement *1 pr i v = ( s truct el_bin_st * ) malloc ( s iz e o f ( stru ct el_bin_st » ; priv->vrij ednost = v ; priv-> l i j ev i = pr iv->d e s n i = NULL ;

e l s e if (v < pr iv->vr i j edno st ) 1* lijevo podstablo pr iv->l i j e v i = kre iraj _st ablp ( priv-> l i j e v i , v ) ; else 1* desilo pods tablo priv->d e s n i = kre iraj _stablo (priv->de s n i , v ) ;

}

*1

*1

r eturn (priv ) ;

Kom pletan program za s t var anj e n aved enim kriterijima glasi: 1 * program

ispis sadržaja binarnog stabla, prema

binarno s t abl o

*1

# include < s t d i o . h> # inelude #def ine

NULPTR *kor i j en ;

main ( )

{

ehar

ch

int

v;

korj en

=

'd' ;

:;

NULPTR ;

whi l e ( ch ! = ' n '

{

eh

!=

'N')

print:! ( " \n Un e s i t e vr ij edno st : " ) ; s eani ( ":!.d " , .v ) ; kre iraj _stablo ( korij en , v ) ; pr int! ( " Dalj e ( din) II ) ; ch get che O ; kor i J en

}

II

=

=

8. 2. Dinamičke strukture podataka

233

print _ s t ablo (kori j en) ;

}

Ispis sadržaja binarnog stabla Za ispis sadržaja b i n ar n o g s t abla koris t i t ćemo rekurzijl1 . Rekurzi vni n ačin ispisa p o d ataka hinarnog stabla je n ajjednostavniji i n ajprirodniji n ač.in i s pi sa Prvo se ispi suje s ad r ž aj lijevog podstabJa, zatim sad ržaj č v or a i .

potom sadržaj desnog }lodstabl a.

/ * i s p i s sadrzaj a b inarnog stabla */ vo id pr int_stablo ( struct el_bin_st *root ) { if ( root ! = NULPTR) { print_stablo ( root->l ij ev i ) ; printf ( " \n Vr ij edno st = Y.d" . root->vr ij ednost ) ; pr int_stablo ( root->desni ) ; } }

Rezul tat i z v r š avanja program a je:

Un e s i t e vrij edno st : Dalj e ( d/n) d Une s it e vrij ednost : ' Dalj e ( d/n) d Une s i t e vrij ednost : D al j e ( d/n ) d Une s i t e vrij edno st : Dalj e ( d/n ) d Une s i t e vrij edno st : Dalj e (d/n) d Une s i t e vrij edno s t : Dalj e ( d/n) d Unes i t e vrij ednost : Dalj e (d/n) n

20 10 5

12 30 25

32

B i n arno s t ablo n akon u n osa podataka izgled a ovako:

234

Složen iji t ipo vi poda t a k a

20

Ispis

s ad rž aj a b i n arn og stabl a prema go ;e navedenom pravilu je

Vr ij ednost Vrijednost Vrijednost Vr ijednost Vrij ednos t Vr ijednost Vrij edno s t

=

5

=

10

= = = = =

12 20 25 30 32

nad line arnim list ama j es t kraće vri­ s t ab l a vrijeme obilaska proporcion aln o je logari t m u b r o j a č vorova, do k je kod linearni h list a proporcionalno broj u G l avn a pred n o s t b i n arnog stabl a

jeme ob ilas ka .

K o d b i n arnog

el emcn at a li s t e . Postoj i

nekoliko na č i n a obilaska binarnog st abl a :

inorder, postorder

i p reorder.

Detaljnije ob j aš nj e nj e ope r a c ij a

n ad

dinami č.kim strukturam a p o d at aka

z all zel o hi d o s t a pros tora, š t o prelazi o k v i re ove knjige. Ako vas i nt er esi r a ova probl ematika, detaljnije o tome m o ž e t e p ro č i t a t i u knjizi "A lgorit hms + D ata S t ruct ures = P rograms" čij i je au tor N iklaus Wirt h .

8.3.

Polj a bitova

P rogramski jczik e i m a m ogućn ost pristu pa pojed i n o m h i t u ili gru p i P rem d a s e u većini programskih jezika kombin acijom odre(tenih vrijed nosti ( fi l t e r ) i logi čkih operatora može pročit at i v rij ed nost s vakog b i t a , bitova.

8. 3. II

e

Polja bitova

235

se m ože ne samo proč i t a t i vrijednos t pojedinog b i t a ,

v rijed n os t p o j e d i n o m

nego i zad a t i

h i t u ili gru pi bitova.

Pos toj i n ekoli ko razloga z a pristu p

pojedinim hitovima

unu t ar riječi .

N a primjer, ako je m em orijski p r o s t o r ogranič,en , može sc zapi sati nekoliko l ogi čk i h varij ahli u ll u t ar j e d no g haj t a , pristu p i t i od re(tenom s t at u su u ređaj a

čije stanje je

zapisano u n u t a r

hajta, pris t u pi t i

koja se či t a s nestan d ard n og u l a z a i sl .

određenom dijel u i n form acije

Kori št enjem p olj a h i t ova često se

m ože p ove ć at i efikasn ost i pregled n ost program a. D eklaracij a p olja h i tova sli čn a je deklaraciji strukture . O p ći oblik d e­

kl aracije

polj a h i t o va j e :

s h'uet

{

illW _:Polja

t ip

illleO : b roj_hitova;

tip

illleN : broj _hitova;

}; S vakom čl anu st r u k t u r e p ri d ru žuje se o d re mnoz enje s 2 pr intf ( " \n x « 1 = %d Binarno :: ", x ) ; prikaz i_b inarno ( x ) ; « 3; x = 1* pomak ul ijevo => mnozenje s 8 *1 pr intf ("\n x « 3 = %d B inarno :: ", x ) ; prikaz i_b inarno ( x ) ;

x = x « 2; pr intf ("\n x « 2 = %d pr ikaz i_b inarno ( x ) ;

"

B inarno

x);

x = x » 1; 1* pomak ud esno => dij eljenje s 2 *1 pr intf ("\n x » 1 = %d Binarno : : " , x); pr ikaz i_b inarno ( x ) ; x = x » 2; pr intf ( " \n x » 2 = %d pr ikaz i_b inarno ( x ) ;

", x ) ;

Binarno

} void pr ikaz i_b inarno ( int x ) { int t, •

for ( t = 128; t > O; t = t/2 ) { if ( x lc t ) pr intf ( "1 ) ; els e pr intf ("O " ) ; } pr intf ( " \n"); II

}

Rezultat izvršavanja programa je:

x = 7 x « 1 3 x « x

« x » x »

2 1 2

=

= =

= =

96

B inarno B inarno Binarno Binarno Binarno

24

Binarno

14 112 192

, ,

O O O 1 O O

O O 1 1 1 O

O O 1 O 1 O

O O 1 O O 1

O 1 O O O 1

1 1 O O O O

1 1 O O O O

1 O O O O O

9. J. Operatori orijentirani na rad 9.1.2.

biiovima

s

Logičke operacije

Logii:'kc operacije A ND , OR, 'XOR i NOT koje se odnose na rad s hit ovima imaju iste t ablice istinitost i kao i logi čke operacije AND, OR,XOR i NOT koje se pri mjenjuju na logi čke varijable. Razli ka je u tome da logičke operacije koje se odnose na rad s hi tovima kao logičke vrijednost i (O il )

uzimaju vrijednost svakog pojedinog bita za d ane varijable, a ne logi čku vrijednos t varijable. Na p rimjer, varijable x i y d eklariran e kao

ehar

ullsiglled

Yi

x,

sadrže vrijed nosti x=10 i y=20. o

O

O

O

O

O

O

Prikaz varijabli u memoriji je

1

O

1

o

varijabla x

O

1

O

O

varijahla y

��__�__-L__�__�__L-���

L-�__�__-L__-L__�__L-�__�

Varijab li

e

koja je ist og t ipa kao i varijable x l y pri druž uje se rezultat

izvršavanja spomenutih logi čkih operacija.

& Yi

e = x

Nakon

zadane

I

naredbe varijahla

O

I

O

I

O

I

O

I

e

O

prikazana

I

O

I

O

I

Dakle, decimalna vrijednost �arijahJe je O.

je O

u memoriji kao

I

varijabl a

e

Da je na varijable x, y hio

primijenjen logički operator AND (&&), varijabla

vrijednost 1, jer s u logičke vrijedn o s t i varijabli x

e

bi poprimila logičku

i y 1.

Logi čka operacija

AND (&) naj češće se kori s t i kod m askiranja o d ređenih bitova riječi ili bajta. Na p ri mj er, u programu koji prima niz z nakova sa serijskog p or t a

o s m i hit

je hit pariteta. Bit

pariteta s luži kao potvrd a pravilnog prijen osa

pojedinog zn aka, a komhi nacija o s t alih sedam bi tova pred stavlja preneseni znak . Zbog t oga se bit pariteta mor a post avi t i na O. Da bi osmi bit bio

pos t avljen na O potreb n o ga je maskirati. Dakle, ako je primljeni niz bit ova sa serijskog p ort a zapisan u varijahli x, koja je deklarirana kao ullsiglled

ebar

Xj

Dodatni skup operatora

254 tada

se ASCII vr ijed no s t prenesenog bajta dobije kao (x &

121);

Ostali logi čki operato r i koji se odnose na rad s bitovima su isklj učivo ILI (XOR - ) i n egac ija (NOT -). Tablica ist in i tosti logičke operacije XOR prikazana je tablicom 9.2. Logi čk i operator - (NOT) m ij e nj a O u 1, i p

q

p - q

O

O

O

1

O

1

O

1

1

1

1

O

•

Tablica 9.2. TahIica istinitosti logičke operacije XOR obrnuto.

Na primjer, va r ij a b li x p r i d r u žen a

je decimalna vrijednost 10 i

p r ikaza n a je 11 m e m oriji kao

x=00001010 N akon naredbe x

=

-x, varijabla x

p ri ka z a n a je u

m e m o r i ji kao

x=11110101. NOT često se koristi u aritmetici d vojnog komplementa.

Logički operator

Bitno je zapamtiti ela relacijski i logički ope ratori kao rezultat d aju logički O ili logič.ki 1. Logički operatori koji se o d nose na r ad s hitovima kao rezultat daj u bilo koju vrijednost koja ovi si o s tanj u va rijabli i logičkom

operatoru primijenjenom na zadane va rija ble . Usporedba logičkih operatora

i logičkih op er ator a koji se odnose na rad s bitovima može se prikazati ovim primjerom:

unsigned x

Y

= =

char

O 1 1 O 1 O 1 1

x&. y = 43; I y ;:;;; 251;

x

1 O 1 O

x,

1

Yi

1 (binarno)

1 1

(binarno) x x

&&. Y

II

y =

=

= =

1;

107 187 1;

9.2. sizeof

9.2.

255

operator

sizeof operator

Operator sizeof često je korišten u p reth od n im primjerima i ako ste pojedine primjere d e t a l j n ije analizirali mogli ste shvatiti njegovo značenje. Sizeof op e ra t o r je tlllarni op erator i kao rezultat vraća veličinu memorije i z ra ž e n u brojem h aj t o va, koju zadana varijabla zauzima. Operator sizeof zadaje se kao:

sizeof (tip-I>odatka)

i može se pojaviti

ato r

II

s vim ti povim a izraza.

Tip_podatka može biti bilo koji definirani tip. U TURBO e-u, oper­ sizeof primijenjen na osnovne ti p ov e podataka daje sljedeće rezultate:

sizeof sizeof sizeof sizeof

(char) (int) (float)

(douhle)

Ako je

= =

tip_podatka

1;

2;

4',

8;

struktura, tada o p erat o r

broj hajtova koji struktura zauzima

II

sizeof

ra ču n a ukupan

memoriji. Na primjer, ako se struk­

tura deklarira kao:

stl'uet pokus

{ }

iut

fl oat

X; y;

tada je vrijednost koj u vraća op erat o r

sizeof (struet pokus)

=

6.

Budući da prikaz različ.itih tipova podataka u različitim i m pl em ent aci­

jama ne zah tije va uvije k istu veličinu memorije, korištenjem tora u izrazima može povećati prenosivost programa.

sizeof op era­

256

Dodatni skup operatora

9.3. Uvjetni? operator Uvj e t ni operator 7 je ternarni operator, što znači da zahtijeva tri o p er an ela. Opći ohlik konstrukcije u kojoj se primjenjuje uvjetni operator 7

je: izrazI 7 izraz2 : izraz3; gdje izrazI, izraz2 i izraz3 predstavljaju aritmetičke i logičke izraze. Navedena konstrukcija koristi se za zamjenu niza n aredbi

if (izraz!) izraz2; dSl�

izraz3; Načili djelovanja y

=

x

operatora može se prikazati primjerom:

> 9 ? 10

:

20;

Varijahli y prid ružit će se vrijednos t 10, ako je ispunjen u vjet x > 9. U pro ti v n o m varijabli y pri d ružuje se vrijedn os t 20. Gornja naredba, koja je napisana u p o treh o m operatora 7, može se napisati kao if

Cx

>

else y

=

y

U mjesto

=

9) 10; 20;

izra,za izraz2 i izraz3 mogu

stajati i

/* primjena uvjetnog operatora main O

{

void void int

fl f2 X·,

(int);

(void);

printt ("\n Unesite broj scanf ("Yod", tx);

"

);

?

poz ivi */

funkcija.

257

9.4- Zarez operator 1* i s p i s poruke o ? fl(x) : 120;

n esenom broju *1

u

x

}

vo id fl ( int

{

a)

printf ( "\n Uneseni broj razli ci t od O");

}

void f2 (vo id)

{

}

printf ( "\n Unes en i broj j edn ak O");

Ako je uneseni broj različit od nule, tada je u vjet ispunjen i izvršava se prvi dio izraza, tj . funkcija fi O, II suprotnom izvršava se fllnkcija f20. Zbog jednostavnost i i kratke forme zapisa uvjetni operator? najčešće se koristi u m akro-definicijama.

Zarez operator

9.4.

Zarez operator povezuje nekoliko izraza. Izraz na lijevoj strani zarez operatora uvijek je tipa void, što znači da rezultat izraza povezanih zarez operatorom ovisi o vrijednosti koja se d obije izvršavanjem svih izraza s desne strane operatora. Na primjer, n ared bom x

=

( y = 20 , y/4);

varijahli y prvo se pridru ži vrijednost 20, zatim se izračuna izraz y / 4 i izračunata vrijednost pridruži varijabli x. Kako operator pridruživanja ima veći prioritet od zarez operatora, zagrad e su neophodne. Izostavljanjem zagrada varijahli x će se pridr užiti vrijednost 20. Gornja naredba je zamjena za niz naredbi: y

=

x

=

20 ; y I 4;

Dodatni skup operatora

258

9.5. Pregled i prioritet operatora e-a Vrijednost izraza u kojem se nalazi nekoliko operatora ovisi o prioritetu izvršavanja pojedinih operatora. Prioriteti pojedinih operatora obrađivani su kroz primjere u prethodnim poglavljima. Zbog toga se u ovom poglavlju neće ponavljati značenja pojedinih operatora, već će se jednostavno navesti svi operatori i njihovi prioriteti. Tablica 9.3. daje prikaz svih operatora programskog jezika e po prioritetima.

Prioritet Najviši

Operatori ( ) ! * «

< --

->

[ ] ++

-

/

(type)

--

*

ct

sizeof

'!. »

>=

!=

ct -

I .tet

II ? >=

Najniži

+=

-=

*=

/=

J

Tablica 9.3. Lista prioriteta operatora programskog jezika e

10. ULAZ I IZLAZ

Programski jezik e nema llgrađene ulazno/izlazne (U/I) naredbe. Ulaz i izlaz podataka u e-u oba\rlja se preko funkcija. Funkcije se nalaze u stan dardnoj ulazno/izlaznoj biblioteci i definirane su ANSI standardom. Funkcije standardne ulazno/izlazne biblioteke kompatibilne su u svim imple­ mentacijama e-a. Prema tome, prijenos izvornog koda programa s j ednog sistema na drugi ne zahtijeva nikakve izmjene. Osim standardnih U/I funkcija kori snik može definirati i vlastite funkcije koje su prilagođene za­ htjevima programa. U ovom poglavlju bit će opisane osnovne U/I funkcije i načini prijenosa podataka i zmeđu programa i ulazno/izlaznih uređaja, datoteka. Poglavlje je podijeljeno u dva dijela. U prvom dijelu obrađene su funkcije za u čitavanje podataka sa standardnog ulaza i funkcije za ispis podataka na standardni i zlaz . U drugom dijelu je opisan rad s datotekama podataka.

Ulaz i izlaz

260

10.1.

Pristup standardnoj ulazno/izlaznoj biblioteci

Programi koji koriste standardne ulazno/izlazne funkcije moraju sadr­ žavati liniju #include

koja se obično nalazi na početk u programa.

•

U datoteci stdio.h sadržani su prototipovi svih ulazno/izlazllih funkcija i definirane su sve simbolič.ke kon st ante i makro naredbe koje se koriste II p ozivima U/I funkcija. U stdio.h je također deklarirana i kon trolna struk­ tura FILE. Za sada ćemo reći da kon trolna struktura tipa FILE sadrži sve podatke potrebne za izvršavanje ulazn o/izlaznih operacija. Ako je si stem datoteka (file system) organiziran t ako da se d atoteka stdio.h ne nalazi u standardnim direktorijima, kod TURBO C-a je to direktorij \tc\indude, a na UNIX sistemima, /usr/include, tada se ime datoteke u n aredbi #in­ dude mora nalaziti između zn akova navoda ""

#include

"stdio.h"

U slučaju kad se datoteka ne n alazi u tekućem direktoriju, imena datoteke mora navesti i put (path):

#illclude "c:\ lteaders\

10.2.

tada

se ispre d

stdio.h"

Međuspremnički sistem datoteka

Postoje dva načina prijenosa podataka izme(tu programa i vanjskih ure . Nared hom type ime_datoteke, u opera t i v n om sis t emu D O S , sadržaj d atoteke ime_datoteke isp i s u je se na zaslon račun ala. Pre­ u s m j eravan j em s e s ad r žaj d atoteke ime_datoteke m ože u p isa t i u b ilo koj u datoteku . Treb a imati n a umu d a je preusmjeravanje ( r e d ir ekcij a ) ka­ rak teristika pojedinih operat i v nih s i s t em a , i d a preusmjeravanje obavlj a sam operati vni sistem . Me(tu t i m , koriš tenjem među spremui čkog si s t em a datoteka preu smjeravanje ulaz/izlaz iz e-a postaje vrlo jednos t av n o . Za

PreusmjeratJanje ulaz/izlaz

1 0.10.

295

prikaz n aveden og n apišimo program ispisi koji sadržaj datoteke, čije se ime zad aje pokretanjem programa ( command line argument) , ispisuje na zaslon računala ili na štampač. Program ispisi ekvivalent an je naredbi type ope­ rativnog sistem a D O S . preusmj eravanj e ulazi izlaz 1 * program ispisi poz i v a programa : i s p i s i ime_dat o t eke 1* ( i s p i s na zaslon) 1* ispis ime_dat o t eke > lpt l 1* ( i s p i s na stampac ) 1*

*1 *1 *1 *1 *1

# include < s t d i o . h> # include < s t r ing . h>

DA NE

#def ine #d ef ine v o id main ( int

{

FILE int char

1 O argv . char

* argc [] )

*fp ; i s p i s _na_stampac ; ch ;

if ( argv < 2 )

{

put s ( " \n Program se kor i s t i kao : i s p i s i ime_dat => i s p i s na zaslon" ) ; put s ( " \n Opcionalno i s p i s i ime_dat > lpt l => i sp i s na s t ampac " ) ; exit ( 1 ) ;

}. 1* otvori datot eku * 1 if « fp = f open ( argc [ l ] . "rb " »

{

= = Hl)LL)

print! ( " Gr e ska otvaranj a datot eka y.s " . arg c [1 ] ) ; exit ( 1 ) ;

}

if « strcmp ( arg c [2] . " > " ) == O) tt ( strcmp ( arg c [3] . " lpt 1 " ) -- O »

296

Ulaz i izlaz

wh i l e « ch

{

}

}

Izvo(tenjem

=

g et e ( f p ) ) ! = EOF)

if ( i s p i s_na_ stampae ) put e ( eh , stdprn) j else put e ( ch , stdout ) j

1 * i s p i s na s t ampae * 1 1* i s p i s na zaslon *1

p r ogra m a sadržaj z ad an e d atoteke i s p i s at

će se n a z as l on računa­ vj e žb u p oku šajt e prošir i t i p rogram tako da se sadržaj ' datot ek e m ože u p i s a ti u bilo koju datoteku (št am p ač , d ruga dat oteka na disku , zasl on i sli čno) .

la ili na š t am p ač . Za

,

1 1 . D O DATNE M O G U C N O S TI TURB O C-a

U prethodnim poglavljima objašnjene su osnovne kar ak teri st ike i mo­ gu ćnosti program skog Jezika C. S ve što je n apisano odgovara ANSI e stan­ d ard u . Prema tome, kod programa koji ste napisali i koji radi korek tno možete bez velikih teškoća prenijeti i izvršavati u bilo kojoj verziji e prevo­ dioca, naravno uz uvjet d a podržava A NSI e standard .

Prolazeći prethodnim pogl avljim a stekli ste sasvim dovoljno isk u st va i znanja d a va.m ovo pogl avlje ne bi trebalo stvarati poteškoće. Informacije sadržane II ovom pogl avlju karakteristične su za T U R B O C . One će vam pomoći da kodiranje bud u ćih program a u T U R B O e-u bude brže i efikas n ije . Naravno d a po re d onoga što će biti opisano, TURB O C i m a i niz drugih mogućnosti. Međutim, opis svih mogućnosti T U RB O C-a p r el az i okvire ove knjige.

Doda t n e m ogućn osti TUR B O G- a

298

11.1.

Razbijanje izvornog koda programa datoteka

II

više

P ro g r am i sad ržani u p ret h o d nim p ogl avlj i m a i oni k o j e s t e p i s ali u čeći p rogram s ki jezik e n i s u ni pribli ž n o složeni kao p r ogr ami koji rješavaju konkret n e p rogram ske zad atke. Rj eš av anj e m konkretnih program skih za­ d at aka i z vorni k o d je čes to pu t a mnogo v e ć i i sl oženij i . P ron al aženje i otk­ la nj anj e sin t ak snih i logi čkih g r ešaka u t ak v i m p r og r ami m a, čiji b i se i z vo r n i kod n alazio u j ed n o j d a t o t eci , bilo b i veoma teško . K ao ol ak š i cu T U R B O e d aj e m ogućno s t r azh ij an ja i z vor n og koda program a u više d at o t eka.

R az b ijanje i z vo rn og ko d a p ro g r am a II više d at o t e ka i m a n e koli k o pre d nos t i . P rije svega, ure