1
PROGRAMIRANJE
C JEZIKOM
Nastavni materijal za studente FESB-a.
Split, 2005/2006
Autor: Ivo Mateljan
2
Sadržaj
1 Uvod........................................................................................................................................... 5
2 Matemati
č
ki i elektroni
č
ki temelji ra
č
unarstva ........................................................................ 13
2.1 Izjavna i digitalna logika ................................................................................................... 13
2.2 Brojevni sustavi i ra
č
unska sposobnost ra
č
unala .............................................................. 16
3 Izrada prvog C programa.......................................................................................................... 20
3.1 Strojni, asemblerski i viši programski jezici ..................................................................... 20
3.2 Prvi program u C jeziku .................................................................................................... 21
3.3 Struktura i kompiliranje C programa ................................................................................ 25
3.4 Integrirana razvojna okolina (IDE) ................................................................................... 27
3.5 Usmjeravanje procesa kompiliranja programom nmake................................................... 32
4 Kodiranje i tipovi podataka ...................................................................................................... 33
4.1 Kodiranje i zapis podataka ................................................................................................ 33
4.2 Memorija ........................................................................................................................... 40
4.3 Prosti tipovi podataka........................................................................................................ 42
4.4 Direktiva #define............................................................................................................... 46
4.5 Specifikatori printf funkcije .............................................................................................. 47
4.6 Pristup podacima pomo
ć
u pokaziva
č
a .............................................................................. 49
4.7 Unos podataka u memoriju ra
č
unala................................................................................. 52
4.8 Inicijalizacija varijabli....................................................................................................... 54
5 Uvod u programiranje C jezikom............................................................................................. 55
5.1 Postupak izrade programa ................................................................................................. 55
5.2 Algoritamska struktura C programa? ............................................................................... 57
5.3 Funkcije C jezika............................................................................................................... 63
5.4 Zaklju
č
ak........................................................................................................................... 70
6 Izrazi i sintaksa C jezika........................................................................................................... 71
6.1 Izrazi.................................................................................................................................. 71
6.2 Automatska i explicitna pretvorba tipova ......................................................................... 78
6.3 Definiranje sinonima tipa pomo
ć
u typedef ....................................................................... 81
6.4 Formalni zapis sintakse C-jezika....................................................................................... 81
7 Proste i strukturalne naredbe C jezika...................................................................................... 87
7.1 Proste naredbe ................................................................................................................... 87
7.2 Strukturalne naredbe ......................................................................................................... 89
8 Nizovi..................................................................................................................................... 102
8.1 Jednodimenzionalni nizovi.............................................................................................. 102
8.2 Prijenos nizova u funkciju............................................................................................... 107
8.3 Višedimenzionalni nizovi................................................................................................ 110
9 Blokovi, moduli i dekompozicija programa........................................................................... 112
9.1 Blokovska struktura programa ........................................................................................ 112
9.2 Funkcionalna dekompozicija programa "od vrha prema dolje" ...................................... 120
9.3 Zaklju
č
ak......................................................................................................................... 128
10 Rad s pokaziva
č
ima.............................................................................................................. 129
4
16.1 Koncept apstraktnog dinami
č
kog tipa podataka ........................................................... 210
16.2 Stog i STACK ADT ...................................................................................................... 215
16.3 Primjena stoga za prora
č
un izraza postfiksne notacije.................................................. 218
16.4 Red i QUEUE ADT....................................................................................................... 221
16.5 Zaklju
č
ak....................................................................................................................... 224
17 Rekurzija i složenost algoritama .......................................................................................... 225
17.1 Rekurzivne funkcije ...................................................................................................... 225
17.2 Matemati
č
ka indukcija .................................................................................................. 227
17.3 Kule Hanoja .................................................................................................................. 227
17.4 Metoda - podijeli pa vladaj (Divide and Conquer)........................................................ 230
17.5 Pretvorba rekurzije u iteraciju ....................................................................................... 232
17.6 Standardna bsearch() funkcija....................................................................................... 234
17.7 Složenost algoritama - "Veliki - O" notacija................................................................. 236
17.8 Sortiranje ....................................................................................................................... 239
17.9 Zaklju
č
ak....................................................................................................................... 248
18 Samoreferentne strukture i liste............................................................................................ 249
18.1 Samoreferentne strukture i lista..................................................................................... 249
18.2 Operacije s vezanom listom .......................................................................................... 250
18.3 Što može biti element liste ............................................................................................ 259
18.4 Lista sa sortiranim redoslijedom elemenata .................................................................. 260
18.5 Implementacija ADT STACK pomo
ć
u linearne liste ................................................... 265
18.6 Implementacija ADT QUEUE pomo
ć
u vezane liste..................................................... 267
18.7 Dvostruko vezana lista .................................................................................................. 269
18.8 Generi
č
ki dvostrani red - ADT DEQUEUE.................................................................. 271
18.9 Zaklju
č
ak....................................................................................................................... 280
19 Razgranate strukture - stabla ................................................................................................ 281
19.1 Definicija stabla ............................................................................................................ 281
19.2 Binarno stablo ............................................................................................................... 282
19.3 Interpreter prefiksnih izraza .......................................................................................... 291
19.4 Stabla s proizvoljnim brojem grana .............................................................................. 305
19.5 Prioritetni redovi i hrpe ................................................................................................. 309
19.6 Zaklju
č
ak....................................................................................................................... 316
20 Strukture za brzo traženje podataka .................................................................................... 317
20.1 Tablice simbola i rje
č
nici .............................................................................................. 317
20.2 Hash tablica................................................................................................................... 318
20.3 BST - binarno stablo traženja........................................................................................ 333
20.4 Crveno-crna stabla......................................................................................................... 344
Literatura ................................................................................................................................... 354
Dodatak ..................................................................................................................................... 355
Dodatak A - Elementi dijagrama toka................................................................................... 355
Dodatak B - Gramatika C jezika ........................................................................................... 356
Dodatak C - Standardna biblioteka C jezika ......................................................................... 361
Index.......................................................................................................................................... 392
5
1 Uvod
Naglasci:
•
Što je ra
č
unalo ?
•
Što je program ?
•
Kako se rješavaju problemi pomo
ć
u ra
č
unala?
•
Ra
č
unarski procesi i memorijski objekti
•
Apstrakcija, algoritam, program
Ra
č
unalo
ili
kompjuter
(eng. computer) je naziv za ure
đ
aje koji obavljaju radnje prema
programima koje izra
đ
uje
č
ovjek. Sastavni dijelovi ra
č
unala nazivaju se
hardver
, a programi i
njihova dokumentacija nazivaju se
softver.
Prvotno su ra
č
unala služila za obavljanje numeri
č
kih
prora
č
una, odatle i potje
č
e naziv ra
č
unalo. Danas ra
č
unala služe za obradu razli
č
itih problema.
Korisnike ra
č
unala zanima kako se koristi ra
č
unalo, a one koji izu
č
avaju ra
č
unala zanima:
•
kako se izra
đ
uje ra
č
unalo,
•
kako se izra
đ
uje program i
•
kako se rješavaju problemi pomo
ć
u ra
č
unala.
Ovdje
ć
e biti pokazano kako se izra
đ
uju programi i kako se programiranjem rješavaju
razli
č
iti problemi. Bit
ć
e opisana i unutarnja gra
đ
a ra
č
unala. Za pisanje programa koristit
ć
e se
programski jeziku C i asemblerski jezik.
Što je program?
Program je zapis operacija koje ra
č
unalo treba obaviti. Taj zapis može biti u obliku
izvršnog programa
ili u obliku
izvornog programa
. Izvršni program sadrži kôd operacija koje
izvršava stroj ra
č
unala, pa se naziva i strojni program. Izvorni program se zapisuje simboli
č
kim
jezikom koji se naziva programski jezik. Prevo
đ
enje izvornog programa u strojni program vrši
se pomo
ć
u programa koji se nazivaju kompilatori (ili kompajleri).
Stroj ra
č
unala
Postoje dva tipa elektroni
č
kih ra
č
unala: analogna i digitalna. Analognim ra
č
unalima se
obra
đ
uju kontinuirani elektroni
č
ki signali. Digitalnim ra
č
unalom se obra
đ
uju, prenose i pamte
diskretni elektroni
č
ki signali koji u jednom trenutku mogu imati samo jedno od dva mogu
ć
a
stanja. Ta stanja se ozna
č
avaju znamenkama 0 i 1, odatle i naziv digitalna ra
č
unala (eng. digit
zna
č
i znamenka). Programere i korisnike ne zanimaju elektroni
č
ki signali u ra
č
unalu, ve
ć
poruka koju oni prenose – digitalna informacija.
Brojevni sustav, u kojem postoje samo dvije znamenke, naziva se binarni brojevni sustav.
U tom se sustavu može kodirati razli
č
ite informacije koriste
ć
i više binarnih znamenki.
Znamenka binarnog brojevnog sustava se naziva
bit
(kratica od eng. binary digit), a može imati
samo dvije vrijednosti 0 ili 1. Niz od više bitova predstavlja kodiranu informaciju koja može
7
Razmotrimo skup podataka kiji se kodira s tri bita. Taj skup može imati maksimalno 8
elemenata jer se s tri bita može kodirati maksimalno osam kombinacija: 000, 001, 010, 011,
100, 101, 110, 111. Lako je pokazati da se s
n
-bita može kodirati podatke iz skupa od
maksimalno 2
n
elemenata. Tablica 1.2 pokazuje da se udvostru
č
enjem broja bitova zna
č
ajno
pove
ć
ava skup vrijednosti koje se mogu kodirati u ra
č
unalu.
Operacije se u ra
č
unala nikada ne izvršavaju samo s jednim bitom, ve
ć
se istovremeno
prenosi i obra
đ
uje više bita. Kod svih ra
č
unala usvojeno je da najmanja jedinica digitalne
informacije, koja se kao cjelina prenosi i pamti u ra
č
unalu, sadrži 8 bita, tj. jedan bajt.
Na slici 1.2 prikazani su sastavni dijelovi digitalnog ra
č
unala.
Centralna procesorska
jedinica
(CPU – central processing unit) - kontrolira izvršenje programa i aritmeti
č
ko-logi
č
kih
operacija. CPU je kod mikro i mini ra
č
unala izveden kao jedinstveni integrirani elektroni
č
ki
sklop (
č
ip) i naziva se mikroprocesor. Uobi
č
ajeno je koristiti naziv
procesor
, bilo da se radi o
mikroprocesoru ili o skupini
č
ipova koji obavljaju funkcije CPU, a programe koji se izvršavaju
u ra
č
unalu naziva se
procesima
.
Slika 1.2. Op
ć
i prikaz digitalnog ra
č
unala
Radna memorija
– pamti digitalne informacije za vrijeme dok je ra
č
unalo u operativnom
stanju. U memoriji se nalazi programski kôd i podaci s kojima operira procesor na temelju
naredbi sadržanih u programskom kôdu. Memorija je napravljena od poluvodi
č
kih elemenata u
koje procesor može upisati i iz kojih može
č
itati digitalne informacije. Ta memorija se naziva
RAM (eng. random access memory). Sa programerskog stajališta RAM predstavlja linearno
ure
đ
en prostor u kojem se istovremeno može pristupiti grupi od 8 bita digitalne informacije (1
bajt). Položaj ove temeljne memorijske
ć
elije se ozna
č
ava prirodnim brojem i naziva se
adresa
.
Jedan manji dio memorije je napravljen od poluvodi
č
kih elemenata koji mogu trajno pamtiti
digitalnu informaciju, a naziva se ROM (eng. read-only memory). U ROM-u je upisan program
koji služi pokretanju osnovnih funkcija ra
č
unala. U samom procesoru ugra
đ
eno je nekoliko
manjih memorijskih jedinica koje se nazivaju
registri
. Registri služe za privremeni smještaj
programskog kôda i podataka iz radne memorije, te rezultata aritmeti
č
ko-logi
č
kih operacije koje
se izvršavaju u samom procesoru. Broj bita koji može biti pohranjen u jednom registru naziva se
rije
č
procesora. Kod ve
ć
ine današnjih PC ra
č
unala rije
č
procesora sadrži 32 bita (4 bajta), pa se
kaže da su to 32-bitna ra
č
unala.
Vanjska memorija
- služi za trajnu pohranu podataka. U tu svrhu koriste se magnetski i
opti
č
ki mediji (tvrdi disk, savitljive diskete, magnetske trake, opti
č
ki diskovi,..). Podaci se na
njima pohranjuju u organiziranom i imenovanom skupu podataka koji se nazivaju
datoteka
.
Ulazne jedinice
- služe za unos podataka (tipkovnica, miš, svjetlosna olovka, mikrofon,..).
Standardna ulazna jedinica je tipkovnica.
Izlazne jedinice
- služe za prikaz informacija korisniku ra
č
unala (video-monitor, pisa
č
,
zvu
č
nik,...). Standardna izlazna jedinica je video-monitor.
