Strukture podataka i algoritmi
2.1 Objekti i apstraktni tipovi podataka

U ovom predmetu, necemo ulaziti u pravu teoriju objektno-orijentisanog dizajna. Umesto toga, koncentrisacemo se na pretecu OO dizajna: apstraktne tipove podataka. Teorija objektno-orijentisanog pristupa se lako gradi na idejama apstraktnih tipova podataka.

Apstraktni tip podataka je struktura podataka i skup funkcija ili procedura koje operisu na strukturi podataka.

Da bi se priblizili OO pristupu, funkcije i procedure cemo zvati metodima, a strukturu podataka i njene metode klasom, tj. nase apstraktne tipove podataka cemo zvati klase. Medjutim, nase klase nemaju sve mogucnosti koje imaju klase u OO programiranju. Instanca klase se zove objekat. Objekti predstavljaju realne objekte i u programima se pojavljuju kao promenljive tipa definisanog klasom. Ovi pojmovi imaju isto znacenje i u OO dizajnu, ali oni tamo imaju i dodatne osobine kao sto je nasledjivanje klasa, sto ovde necemo razmatrati.

Vazno je primetiti da je objektna orijentisanost metodologija programiranja. Kao posledica, moguce je pisati OO programe koristeci jezike kao sto su C, Ada i Pascal. Tzv. OO jezici, kao sto su C++ i Eiffel jednostavno pruzaju odredjenu kompajlersku podrsku za OO dizajn: u ne-OO jezicima ovu podrsku programer mora sam da pruzi.

2.2 Primer: skupovi

Programi cesto barataju sa skupovima objekata. Ovi skupovi mogu biti organizovani na mnogo nacina i mogu se koristiti razlicite programske strukture za njihovo predstavljanje, ali ipak, sa apstraktne tacke gledista, postoji nekoliko zajednickih operacija za bilo koji skup. One mogu biti:

create Kreiranje novog skupa
add Dodavanja objekta skupu
delete Brisanje objekta iz skupa
find Trazenje objekta koji zadovoljava odredjeni uslov u skupu
destroy Brisanje skupa

2.2.1 Konstruktori i destruktori

Metodi create i destroy - cesto zvani konstruktori i destruktori - obicno se implementiraju za sve apstraktne tipove podataka. S vremena na vreme, uslovi koriscenja ili semantika tipa podataka su takvi da postoji samo jedan objekat tog tipa u programu. U tom slucaju, moguce je sakriti od korisnika cak i referencu na objekat. Medjutim, cak i u ovim slucajevima, konstruktor i destruktor metodi se cesto navode.

Naravno, specificne primene mogu zahtevati dodatne metode, npr. mozda ce nam trebati unija dva skupa - ili nam mozda nece trebati svi ovi metodi.

Jedan od ciljeva dobrog programiranja je da omoguci da se dodatni zahtevi lako resavaju.

2.2.2 Struktura podataka

Da bi konstruisali apstraktni softverski model skupa, pocinjemo sa navodjenjem formalne specifikacije. Prva komponenta ovakve specifikacije je ime tipa podataka - ovo je tip objekata koji pripadaju klasi collection (skup). U C-u, koristimo typedef da bi definisali novi tip koji je pointer na strukturu:

typedef struct collection_struct *collection;

Primetimo da smo definisali samo pointer na strukturu; nismo specificirali detalji atributa strukture. Ovo smo namerno odlozili - detalji implementacije su nebitni u ovom trenutku. Nas interesuje jedino apstraktno ponasanje skupa. U stvari, zelimo da budemo u mogucnosti da imamo razlicite strukture podataka za stvarnu implementaciju skupa, u zavisnosti od nasih potreba.

typedef deklaracija nam daje C tip (klasu u OO terminologiji) collection. Mozemo deklarisati objekte tipa collection gde god nam je potrebno. Iako nas C prisiljava da otkrijemo da je referenca na objekat klase u stvari pointer, bolje je drzati se apstraktnog gledista: promenljive tipa collection posmatracemo kao reference na same objekte klase i prosto zaboraviti da su promenljive u stvari C pointeri.

2.2.3 Metodi

Sada nam je potrebno da definisemo metode:

collection ConsCollection( int max_items, int item_size );
void AddToCollection( collection c, void *item );
void DeleteFromCollection( collection c, void *item );
void *FindInCollection( collection c, void *key );

Primetimo da ovde koristimo dosta C "hack-ova". C - cak i u ANSI standardu - nije bas najbezbedniji programski jezik u smislu podrske koju pruza za konstruisanje kvalitetnog softvera. Medjutim, njegova prenosivost i ekstremna popularnost znace da je on praktican izbor cak i za velike projekte u softverskom inzinjerstvu. Na zalost, C++, s obzirom da je baziran na C-u, nije mnogo bolji. Java, poslednja moda u softverskoj industriji, dokazuje da su njeni kreatori nesto naucili iz iskustva (ili cak i procitali nesto od literature iz istrazivanja programskih jezika!) i eliminisali neke od opasnijih osobina C-a.

Bas kao sto smo definisali objekat skupa kao pointer na strukturu, tako cemo pretpostaviti i da je objekat, koji pripada skupu, takodje pointer na strukturu podataka. Stoga u AddToCollection, za item pisemo void *. U ANSI C-u, void * ce odgovarati bilo kom pointeru - pa AddToCollection moze da se koristi za dodavanje bilo kog objekta u nas skup. Slicno, za key u FindInCollection je takodje navedeno void *, posto kljucni izraz koji se koristi da pronadjemo neki objekat moze sam za sebe da predstavlja neki drugi objekat. FindInCollection vraca pointer na objekat u skupu koji odgovara kljucnom izrazu, pa on takodje ima tip void *. Koriscenje void * ovde naglasava neke nedostatke u C-u: on ne omogucava kreiranje opstih objekata, kao sto su mogucnost definisanja opstih paketa u Adi ili sablona (templates) u C++.

Naravno, postoje razni drugi "hack-ovi" za prevazilazenje C-ovih ogranicenja u ovoj oblasti. Jedan od njih koristi preprocesor. Mozda biste mogli da nadjete alternativni pristup i probate da ubedite svog profesora da je vas pristup bolji od onog koji je ovde predlozen!

2.2.4 Pre- i post-uslovi

Nijedna formalna specifikacija nije kompletna bez pre- i post-uslova. Koristan nacin za njihovo predstavljanje je sklapanje ugovora izmedju objekta i njegovog korisnika. Pre-uslovi definisu stanje programa koje korisnik garantuje da obezbedi pre pozivanja bilo kog metoda, dok post-uslovi definisu stanje programa koje metodi objekta garantuju da generisu po svom izvrsenju.

Opet, C (za razliku od Eiffel-a, na primer) ne obezbedjuje formalnu podrsku za pre- i post-uslove. Standard ipak definise makro assert koja se moze (i treba!) da koristi za proveru ispunjenosti pre- i post-uslova [standardan Unix opis za assert makro]. Videcemo kako se ovaj makro koristi kada budemo razmatrali implementaciju naseg skupa. Prema tome, pre- i post-uslovi bi trebalo da budu navedeni kao komentari nakon definicije metoda.

Dodavanje pre- i post-uslova u objekat collection bi dalo:
Ucitaj collection.h

Sa strane

Kako bi u ovom trenutku diskusija ostala sto jednostavnija, definicije koje su ovde koriscene prouzrokuju veoma opstu specifikaciju skupa. U praksi bismo cesto ogranicili nasu specifikaciju na razne nacine: na primer, ne dozvoljavajuci da se u skupu nadju duplikati (objekti sa istim kljucem). Kod takvog skupa, pre- i post-uslovi mogu biti jos formalniji:
Ucitaj ucollection.h

Primetimo kako pre- i post-uslovi sada koriste funkciju FindInUCollection za preciznije definisanje stanja objekta pre i nakon sto je metod pozvan. Takvi formalni pre- i post-uslovi su ocigledno mnogo korisniji nego raniji neformalni. Njih je takodje i lakse prevesti u odgovarajuce "assert" tvrdjenja, kao sto ce se videti kada se budemo bavili implementacijom.

2.2.5 C konvencije

Ovakvu specifikaciju - koju korisnik objekta treba da vidi (njega ne interesuju detalji implementacije) - normalno bi trebalo staviti u datoteku sa nastavkom .h (h = header, zaglavlje). Za skup, specifikacije bismo stavili u datoteke collection.h, odnosno Ucollection.h, i koristili C-ovu #include direktivu za njihovo ucitavanje u programe koji treba da ih koriste. Sama implementacija klase se stavlja u datoteku sa nastavkom .c.

Literatura

Dodatni izvori informacija o objektnoj orijentisanosti:

Kljucni pojmovi

Apstraktni tip podataka (ADT)
Struktura podataka i skup operacija koji se na njoj mogu izvrsiti. Klasa u objektno-orijentisano programiranju je apstraktni tip podataka. Medjtuim, klase imaju dodatna svojstva (nasledjivanje i polimorfizam) koje se obicno ne razmatraju kod apstraktnih tipova podataka.

Dalje na Manipulisanje greskama
Dalje na Nizove
Nazad na Sadrzaj
© John Morris, 1998. Prevod sa engleskog, Dragan Stevanovic, 2002.