Svi ugrađeni tipovi podataka su apstraktni, iako se retko tako nazivaju.
Koncept apstrakcije
Apstrakcija je sud ili reprezentacija o objektu koji sadrži samo svojstva koja su bitna u datom kontekstu. Apstrakcija vam omogućava da kombinujete instance objekata u grupe, unutar kojih opšta svojstva objekti se mogu zanemariti, tj. apstraktno od njih. Apstrakcija je efikasan alat protiv složenosti programiranja, omogućavajući programeru da se fokusira na bitna svojstva objekata. Vrste apstrakcija: apstrakcija procesa i apstrakcija podataka.
Apstrakcija procesa. Sve potprograme su apstrakcije procesa, one definišu način na koji program određuje da neki proces treba da se obavi, bez specificiranja detalja o tome kako to tačno uraditi. Sposobnost apstrahovanja mnogih detalja algoritma koji pokreće potprogram omogućava vam da kreirate, čitate i razumete velike programe. Svaka apstrakcija podataka su operacije, definirane kao procesne apstrakcije.
Apstrakcija podataka. Apstraktni tip podataka je enkapsulacija koja sadrži samo reprezentacije podataka jednog određenog tipa i rutine koje izvode operacije nad podacima tog tipa. Uz kontrolu pristupa, mogu se sakriti nebitni detalji opisa tipa eksterni moduli koji koriste ovu vrstu. Programski moduli koji koriste apstraktni tip podataka mogu deklarirati varijable tog tipa iako je stvarni prikaz tipa skriven od njih. Instance apstraktnog tipa podaci se nazivaju objektom.
Razlog za kreiranje apstrakcije tipa podataka i apstrakcije procesa je lijek protiv složenosti, način da se napravi velika i/ili složeni programi upravljivije.
Enkapsulacija
Podjela programa na sintaktičke kontejnere koji sadrže grupe logički povezanih rutina i podataka. Ovi sintaktički kontejneri se nazivaju moduli, a proces razvoja je modularizacija.
Sastavljanje programa od skupova rutina i podataka, od kojih se svaki može kompajlirati zasebno, bez ponovnog kompajliranja ostatka programa. Ovaj skup se naziva jedinica za kompilaciju.
Enkapsulacija je način integracije rutina i podataka koje obrađuju u koherentnu cjelinu. Enkapsulacija, koja se sastavlja ili zasebno ili nezavisno, je osnova apstraktnog sistema i logičke organizacije skupa povezanih proračuna.
Apstraktni korisnički definirani tipovi podataka
Apstraktni korisnički definirani tipovi podataka moraju imati sljedeća svojstva:
1) definicija tipa, koja dozvoljava programskim modulima da deklarišu varijable ovog tipa, dok kreiraju stvarnu reprezentaciju ovih varijabli u memoriji.
2) skup operacija za manipulaciju objektima ovog tipa.
Formalna definicija apstraktnog tipa podataka u kontekstu korisnički definiranih tipova: Apstraktni tip podataka je tip podataka koji zadovoljava sljedeća dva uvjeta.
Reprezentacija (definicija tipa) i operacije nad objektima ovog tipa sadržane su u jednoj sintaksičkoj jedinici, varijable ovog tipa mogu se kreirati u drugim modulima.
Predstavljanje objekata ovog tipa je skriveno od softverski moduli koristeći ovaj tip, možete izvoditi operacije na objektima koji su direktno navedeni u definiciji tipa.
Pakovanje prikaza tipa i operacija u zasebnu sintaksičku jedinicu omogućava vam da organizujete svoj program kao logičke jedinice koje se mogu zasebno kompajlirati. Drugo, postaje moguće modificirati reprezentacije objekata određenog tipa ili operacija s njima u posebnom dijelu programa. Postoje prednosti skrivanja detalja prezentacije tipa. Klijenti ne mogu "vidjeti" detalje pogleda objekta, a njihov kod je nezavisan od tog pogleda. Na ovaj način, reprezentacije objekata mogu se promijeniti u bilo koje vrijeme bez potrebe za promjenama koda klijenta. Još jedna očigledna i važna prednost skrivanja informacija je povećana pouzdanost. Klijenti ne mogu direktno promijeniti osnovne reprezentacije objekata, bilo namjerno ili slučajno, stoga se povećava integritet takvih objekata. Objekti se mogu mijenjati samo korištenjem operacija predviđenih za to.
Problemi sa dizajnom tipa
Trebalo bi biti moguće učiniti ime tipa i zaglavlja potprograma vidljivim u klijentima apstrakcije. Ovo omogućava klijentima da deklarišu varijable apstraktnog tipa i manipulišu njihovim vrednostima. Iako ime tipa mora biti vidljivo izvana, njegova definicija mora biti skrivena.
Postoji vrlo malo općih ugrađenih operacija koje se mogu izvesti na objektima apstraktnih tipova, za razliku od onih koje daje definicija tipa. Takve operacije uključuju zadatke i testove jednakosti i nejednakosti. Ako jezik ne dozvoljava korisnicima da preopterećuju operator dodjeljivanja, onda bi trebao biti inline. Provjere jednakosti i nejednakosti moraju biti unaprijed definirane u nekim slučajevima, au drugim ne. Dizajner tipa mora sam definirati operacije za većinu apstraktnih tipova podataka.
Smalltalk, C++ i Java direktno podržavaju apstraktne tipove podataka.
Apstraktni tipovi podataka u C++
Ada i Modula-2 jezici pružaju enkapsulaciju koja se može koristiti za modeliranje apstraktnih tipova podataka, dok C ++ uvodi koncept klase koja direktno podržava apstraktne tipove podataka. U C ++, klase su tipovi, ali Ada paketi i Modula-2 moduli nisu tipovi. Paketi i moduli se uvoze, omogućavajući uvoznoj programskoj jedinici da deklarira varijable bilo kojeg tipa definiranog u paketu ili modulu. U C++ programu, varijable su deklarisane kao entiteti tipa ove klase. Stoga su klase mnogo više poput ugrađenih tipova nego paketa ili modula. Programska jedinica koja vidi paket na jeziku Ada ili modul na jeziku Modula-2 ima pristup svim otvorenim entitetima samo po njihovom imenu. C++ programska jedinica koja deklarira instancu klase također ima pristup svim javnim entitetima u toj klasi, ali samo preko instance te klase.
Tip podataka opisuje mnoge objekte sa sličnim svojstvima. Svi tradicionalni programski jezici koriste set osnovne vrste podaci (stvarni, cijeli broj, niz, karakter). Osnovni tipovi podataka podliježu unaprijed definiranom skupu operacija. Na primjer, osnovni tip podataka cijeli broj omogućava vam da izvodite operacije kao što su zbrajanje, oduzimanje, množenje, dijeljenje.
Tradicionalni programski jezici uključuju konstruktore tipova, od kojih je najčešći konstruktor zapisa. Na primjer, za zapis tipa CUSTOMER, možete definirati polja podataka. Zapis CUSTOMER će biti novi tip podataka, koji će pohraniti informacije o klijentima, možete direktno pristupiti ovoj strukturi podataka pozivajući se na imena polja. Operacije kao što su WRITE, READ, DELETE, UPDATE mogu se izvršiti na zapisu. Ne možete definirati nove operacije za osnovne tipove podataka.
Kao i osnovni tipovi podataka, apstraktni tipovi podataka (ATD) opisuju mnoge slične objekte. Postoje razlike između ATD i tradicionalnog tipa podaci:
· Operacije pod ATD definira korisnik;
· ATD ne dozvoljavaju direktan pristup internom predstavljanju podataka i implementaciji metoda.
U nekim OO sistemima (na primjer, Smalltalk), osnovni tipovi podataka se implementiraju kao apstraktni.
Da biste kreirali apstraktni tip podataka, morate osigurati:
· Ime tipa;
· Prikaz podataka ili varijable instance objekta koji pripada ATD-u; svaka varijabla instance ima tip podataka koji može biti ili osnovni tip ili različit ATD;
· ATD operacije i ograničenja se implementiraju korištenjem metoda.
ATD definicija ponovo gradi definiciju klase. Neki OO sistemi koriste ključnu riječ type za razlikovanje između klasa i tipova kada se odnose na strukture podataka i metode klasa, i ključnu riječ class kada se odnose na skup instanci objekta. Tip je statičniji koncept, dok se klasa uglavnom odnosi na vrijeme izvođenja. Razlika između OO klase i OO tipa može se ilustrirati primjerom. Pretpostavimo da imate šablon za konstruktor. Šablon prati opis njegove strukture, kao i uputstva za njegovu upotrebu. Ovaj šablon je definicija tipa. Skup stvarnih proizvoda napravljenih pomoću šablona, od kojih svaki ima jedinstveni broj (ili OID), čini klasu (klasu).
ATD, zajedno sa nasljeđivanjem, omogućava kreiranje složenih objekata. Složeni objekat nastaje kombinovanjem drugih objekata koji su međusobno u složenim odnosima. Primjer složeni objekat mogu se naći u sigurnosnim sistemima gdje različite vrste podaci:
1. standardni (tabelarni) podaci o zaposlenom (ime i prezime, tab. br. itd.);
2. bitmap za čuvanje fotografije zaposlenog;
Sposobnost da se relativno lako rukuje tako složenim okruženjem podataka povećava vrijednost OO sistema moderno tržište baze podataka.
Jezik C ++ vam omogućava da kreirate tipove podataka koji se ponašaju slično osnovnim tipovima jezika C. Ove vrste se obično nazivaju apstraktni tipovi podataka(ATD).
Za implementaciju ADT-a u jeziku C, koriste se strukture. Ali korištenje podataka strukturni tip značajno ograničen u odnosu na korištenje osnovnih tipova podataka. Na primjer, strukturirani podaci se ne mogu koristiti kao operandi u raznim operacijama (sabiranje, oduzimanje). Da biste manipulirali takvim podacima, morate napisati skup funkcija koje izvršavaju razne akcije, i pozovite ove funkcije umjesto operacija.
Osim toga, elementi konstrukcije nisu ni na koji način zaštićeni od slučajnih modifikacija. Odnosno, bilo koja funkcija (čak ni iz skupa alata za manipulaciju strukturalnim podacima) može se odnositi na element strukture. Ovo je u suprotnosti s jednim od osnovnih principa objektno orijentiranog programiranja - enkapsulacijom podataka: nema drugih funkcija osim posebne funkcije manipulacije s ovim tipom podataka ne bi trebale moći pristupiti stavkama podataka.
Razmotrite implementaciju koncepta datuma koristeći strukturu kako biste definirali datum predstavljanja datuma i niz funkcija za rad s varijablama ovog tipa:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include
datum strukture
{
int mjesec; // mjesec
int dan; // dan
int godina; // god
};
void set_date (datum * f, int d, int m, int y)
{
f-> dan = d;
f-> mjesec = m;
f-> godina = y;
}
void print_date (datum * f)
{
printf ("% d.% d.% d", f-> dan, f-> mjesec, f-> godina);
}
int main ()
{
datum danas;
set_date (& danas, 2, 4, 2014);
print_date (& danas);
getchar ();
return 0;
}
Rezultat izvršenja
Ne postoji eksplicitna veza između funkcija i tipa podataka u ovom primjeru. Da biste pozvali bilo koju od opisanih funkcija, morate proslijediti pokazivač na instancu strukture kao argument.
Ovaj odnos se može uspostaviti opisivanjem funkcija kao članova strukture. Ove funkcije mogu djelovati na podatke sadržane u samoj strukturi.
Po defaultu, kada se deklarira struktura, njeni podaci i funkcije se dijele, odnosno objekti strukture tipa nemaju ni enkapsulaciju ni zaštitu podataka:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include
datum strukture
{
int mjesec; // mjesec
int dan; // dan
int godina; // god
void set_date (int d, int m, int y)
{
dan = d; mjesec = m; godina = y;
}
void print_date (void);
};
nevažeći datum :: print_date (void)
{
printf ("% d.% d.% d", dan, mjesec, godina);
}
int main ()
{
datum danas;
today.set_date (2, 4, 2014);
today.print_date ();
getchar ();
return 0;
}
Funkcije članova i članovi podataka
Funkcije opisane u tijelu apstraktnog tipa podataka su funkcije ili metode i mogu se pozvati samo na posebnoj varijabli odgovarajućeg tipa koristeći standardnu sintaksu za pristup članovima podataka ili poljima strukture.
Definicija funkcija članova može se izvršiti na dva načina:
- opis funkcije direktno na opisu strukture;
- opis funkcije izvan strukture.
Članske funkcije koje su definirane unutar strukture su implicitno umetnute ( ). Tipično, samo kratke, često korištene funkcije člana trebaju biti definirane unutar strukture: prazni skup (int m, int d, int y) (mjesec = m; dan = d; godina = y;);
Ukoliko različite strukture može imati funkcije člana sa ista imena, kada definirate funkciju člana, morate navesti ime strukture, spajajući ih pomoću operatora za razrješenje konteksta (dupla dvotočka) ::
Vrsta ADT :: naziv (list argumenata) (
tijelo funkcije člana; )
- tip- tip povratka funkcije člana
- ATD- naziv apstraktnog tipa podataka (ime strukture ili klase)
- ime- naziv funkcije člana
nevažeći datum :: print_date (void)
(printf ("% d.% d.% d", dan, mjesec, godina);)
U funkciji člana, imena članova mogu se koristiti bez eksplicitne reference objekta. U ovom slučaju, ime se odnosi na člana objekta na kojem je funkcija pozvana.
Funkcije članova iste strukture mogu biti polimorfne, odnosno preopterećene.
Prava pristupa
Koncept strukture u C ++ (za razliku od C) omogućava da članovi strukture budu javni, privatni ili zaštićeni:
- javno - opšte;
- privatno - privatno;
- zaštićen - zaštićen.
Upotreba ključna riječ zaštićeno je povezano s konceptom nasljeđivanja.
Upotreba privatne ključne riječi ograničava pristup članovima koji slijede ovu konstrukciju. Privatne članove može koristiti samo nekoliko kategorija funkcija, čije privilegije uključuju pristup tim članovima. To su u osnovi funkcije članova iste strukture.
Javna ključna riječ formira sučelje za objekt strukture.
Standard je da se u njega smjesti član podataka privatni prostor(privatni), a dijelovi funkcija članova nalaze se u javnom dijelu apstraktnog tipa podataka. U ovom slučaju, privatni dio definira podatke o objektu i servisne funkcije, a funkcije članice općeg dijela implementiraju metode za rad s objektom.
Promijenimo strukturu datuma da sakrijemo prikaz podataka (enkapsulacija podataka):
1
2
3
4
5
6
7
8
datum strukture
{
privatno:
int mjesec, dan, godina;
javno:
void skup (int, int, int);
void print ();
};
Razvijanje apstraktnih modela za podatke i način obrade tih podataka je bitna komponenta u procesu rješavanja problema korištenjem računara. Vidimo primjere ovoga i na niskom nivou u svakodnevnom programiranju (na primjer, kada se koriste nizovi i povezane liste o kojima se govori u), i na visokom nivou prilikom rješavanja primijenjeni zadaci(kao kod rješavanja problema povezivanja korištenjem šume pretraživanja pridruživanja u "Uvodu"). Ovo predavanje govori o apstraktnim tipovima podataka (u daljem tekstu ADT), koji vam omogućavaju da kreirate programe koristeći apstrakcije visokog nivoa. Apstraktni tipovi podataka vam omogućavaju da odvojite apstraktne (konceptualne) transformacije koje programi izvode na podacima od bilo kojeg određenog prikaza strukture podataka ili bilo koje posebne implementacije algoritma.
Svi računarski sistemi su zasnovani na nivoima apstrakcije: određena fizička svojstva silicijuma i drugih materijala omogućavaju usvajanje apstraktnog modela bita, koji može imati binarne vrednosti 0-1; tada se apstraktni model stroja gradi na dinamičkim svojstvima vrijednosti određenog skupa bitova; dalje, na osnovu principa rada mašine pod kontrolom programa na mašinski jezik gradi se apstraktni model programskog jezika; i, konačno, konstruiše se apstraktni koncept algoritma koji se implementira kao program u jeziku C++. Apstraktni tipovi podataka omogućavaju nastavak ovog procesa dalje i razvoj apstraktnih mehanizama za određene računske zadatke na višem nivou od onog koji pruža C++ sistem, razvoj apstraktnih mehanizama fokusiranih na specifične aplikacije i pogodan za rješavanje problema u brojnim područjima primjene, kao i stvaranje apstraktnih mehanizama više visoki nivo koji koriste ove osnovne konstrukcije. Apstraktni tipovi podataka nam pružaju beskonačno proširiv skup alata rješavati sve više novih problema.
S jedne strane, upotreba apstraktnih konstrukcija oslobađa vas brige oko njihove detaljne implementacije; s druge strane kada performanse Program je važan, potrebno je znati troškove izvođenja osnovnih operacija. Koristimo mnogo osnovnih apstrakcija ugrađenih u hardver Računalo i služi kao osnova za strojne upute; implementiramo druge apstrakcije u softver; i koristiti dodatne apstrakcije koje obezbjeđuje prethodno napisani sistemski softver. Apstraktne konstrukcije visokog nivoa često se kreiraju na osnovu više jednostavni dizajni... Na svim nivoima vrijedi isti osnovni princip: potrebno je pronaći najviše važne operacije u programima i većina važne karakteristike podatke, a zatim precizno definirati oba na apstraktnom nivou i razviti efikasne konkretne mehanizme za njihovu implementaciju. U ovom predavanju ćemo pogledati mnoge primjere primjene ovog principa.
Da biste razvili novi nivo apstrakcije, moraćete da (1) definišete apstraktne objekte kojima treba manipulisati i operacije koje treba izvršiti na njima; (2) predstavljaju podatke u nekoj strukturi podataka i implementiraju operacije; (3) i (što je najvažnije) osigurati da su ovi objekti pogodni za korištenje za rješavanje primijenjenih problema. Ove tačke se takođe odnose na jednostavni tipovi podataka, tako da se osnovni mehanizmi za podršku tipovima podataka koji su razmatrani u "Atomskim strukturama podataka" mogu prilagoditi za naše potrebe. Međutim, jezik C++ sugeriše važno proširenje mehanizam strukture koji se zove klasa. Klase su izuzetno korisne za stvaranje nivoa apstrakcije i stoga se smatraju primarnim alatom koji se koristi u tu svrhu u ostatku ove knjige.
Definicija 4.1. Apstraktni tip podataka (ADT) je tip podataka (skup vrijednosti i skup operacija za te vrijednosti) kojem se pristupa samo preko sučelja. Program koji koristi ADT će se zvati klijent, a program koji sadrži specifikaciju ovog tipa podataka naziva se implementacija.
To je riječ koja samo čini tip podataka apstraktnim: u slučaju ADT-a, klijentski programi nemaju pristup vrijednostima podataka na bilo koji drugi način, osim operacijama opisanim u sučelju. Prezentacija ovih podataka i funkcije koje implementiraju ove operacije su u implementaciji i potpuno su odvojene interfejsom od klijenta. Kažemo da je interfejs neproziran: klijent ne može da vidi implementaciju kroz interfejs.
U C ++ programima ova razlika je obično malo jasnija, jer je najlakši način za kreiranje sučelja uključiti prezentacija podataka ali navodeći da klijentskim programima nije dozvoljen direktan pristup podacima. Drugim riječima, programeri klijentskog softvera mogu znati prezentacija podataka ali ne mogu ga koristiti ni na koji način.
Kao primjer, razmotrite interfejs tipa podataka za tačke (Program 3.3) iz Odjeljka 3.1 "Elementarne strukture podataka". Ovaj interfejs eksplicitno izjavljuje da su tačke predstavljene kao strukture koje se sastoje od para brojeva s pokretnim zarezom, označenih kao x i y. Ova upotreba tipova podataka je uobičajena u veliki sistemi softvera: razvijamo skup konvencija za prezentaciju podataka (kao i definiramo niz povezanih operacija) i činimo ta pravila dostupnima kroz sučelje tako da ih mogu koristiti klijentski programi uključeni u veliki sistem... Tip podataka osigurava da su svi dijelovi sistema konzistentni sa reprezentacijom temeljnih struktura podataka u cijelom sistemu. Koliko god ova strategija bila dobra, ona ima jednu manu: ako treba da se promenite prezentacija podataka, tada će se svi klijentski programi morati promijeniti. Program 3.3 nam opet daje jednostavan primjer: jedan od razloga za razvoj ove vrste podataka je pogodnost klijentskih programa sa tačkama, te očekujemo da klijenti imaju pristup pojedinačnim koordinatama tačaka kada je to potrebno. Ali ne možemo prijeći na drugačiji prikaz podataka (recimo polarne koordinate, ili 3D koordinate, ili čak različite tipove podataka za pojedinačne koordinate) bez promjene svih klijentskih programa.
Nasuprot tome, Program 4.1 sadrži implementaciju apstraktnog tipa podataka koji odgovara tipu podataka Programa 3.3, ali koristeći C++ klasu koja odmah definira i podatke i pridružene operacije. Program 4.2 je klijentski program rad sa ovim tipom podataka. Ova dva programa izvode iste proračune kao programi 3.3 i 3.8. One ilustruju neka od osnovnih svojstava klasa koje ćemo sada pogledati.
Kada u programu napišemo definiciju kao što je int i, kažemo sistemu da rezerviše memorijsku oblast za podatke (inline) tipa int kojoj se može pristupiti putem i. U jeziku C++ postoji termin objekt za takve entitete. Kada napišete definiciju kao što je POINT p u programu, kaže se da kreirate objekat klase POINT, kojem se može pristupiti po imenu p. U našem primjeru, svaki objekt sadrži dvije stavke podataka, nazvane x i y. Kao i kod struktura, na njih se može pozvati imena poput p.y.
Članovi podataka x i y nazivaju se članovima podataka klase. Klasa također može definirati funkcije člana koje implementiraju operacije povezane s tim tipom podataka. Na primjer, klasa definirana u Programu 4.1 ima dvije funkcije člana pod nazivom POINT i distance.
Klijentski programi, kao što je Program 4.2, mogu pozvati funkcije člana povezane s objektom, specificirajući njihova imena na isti način kao i imena podataka pronađenih u nekoj strukturi. Na primjer, izraz p.distance (q) izračunava rastojanje između tačaka p i q (istu udaljenost treba vratiti pozivanjem q.distance (p)). Funkcija POINT (), prva u Programu 4.1, je posebna funkcija člana koja se zove konstruktor: ima isto ime kao klasa i poziva se kad god je potrebno kreirati objekat te klase.
Program 4.1. Implementacija klase POINT (tačka)
Ova klasa definira tip podataka koji se sastoji od skupa vrijednosti koje su "parovi s plutajućim zarezima" (pretpostavlja se da se tumače kao tačke na kartezijanskoj ravni) i dvije funkcije članice definirane za sve instance klase POINT: funkcija POINT (), koji je konstruktor koji inicijalizira koordinate na slučajne vrijednosti od 0 do 1, i funkcija udaljenosti (POINT) koja izračunava udaljenost do druge točke. Prezentacija podataka je privatan i samo mu funkcije mogu pristupiti ili ga modificirati. Same funkcije članova su javne i dostupne svakom klijentu. Kod se može sačuvati, na primjer, u datoteci pod nazivom POINT .cxx.
#include
Program 4.2. Klijentski program za klasu POINT (pronalaženje najbliže tačke)
Ova verzija programa 3.8 je klijent koji koristi POINT ADT definiran u programu 4.3. Nova operacija kreira niz POINT objekata (pozivanjem konstruktora POINT () za inicijalizaciju svakog objekta sa nasumične koordinate). Izraz a [i] .distance (a [j]) poziva na objektu a [i] funkciju člana udaljenosti s argumentom a [j].
#include
Definiranje POINT p u klijentskom programu rezultira dodjeljivanjem memorijskog područja za novi objekt, a zatim (koristeći funkciju POINT ()) dodjeljivanjem svakoj od njegove dvije stavke podataka nasumične vrijednosti u rasponu od 0 do 1.
Ovaj stil programiranja, koji se ponekad naziva objektno orijentirano programiranje, u potpunosti je podržan konstrukcijom klase C ++. Klasa se može smatrati proširenjem koncepta strukture, gdje se ne kombinuju samo podaci, već se definiraju i operacije s tim podacima. Može postojati mnogo različitih objekata koji pripadaju istoj klasi, ali svi su slični po tome što njihovi podaci o članovima mogu uzeti isti skup vrijednosti, a isti skup operacija se može izvesti nad tim podacima o članovima - općenito, oni su instance istog tipa podataka. U objektno orijentiranom programiranju, objekti su dizajnirani da obrađuju svoje podatke o članovima (za razliku od korištenja nezavisnih funkcija za obradu podataka pohranjenih u objektima).
Gledamo gore opisani primjer male klase samo da bismo se upoznali sa osnovnim karakteristikama klasa; stoga je daleko od potpunog. U stvarnom kodu za klasu tačke, imaćemo mnogo više operacija. Na primjer, Program 4.1 čak nema operacije koje vam omogućavaju da saznate vrijednosti x i y koordinata. Kao što ćemo vidjeti, dodavanje ovih i drugih operacija je prilično jednostavan zadatak. U petom dijelu ćemo detaljnije pogledati klase za tačke i druge geometrijske apstrakcije kao što su linije i poligoni.
U C ++ (ali ne i C), strukture također mogu imati funkcije povezane s njima. Ključna razlika između klasa i struktura odnosi se na pristup informacijama, koji karakteriziraju ključne riječi.
1.2. Apstraktni tipovi podataka
Većina koncepata predstavljenih u prethodnom odjeljku obično se uvode u početni kurs programiranja i trebali bi vam biti poznati. Samo apstraktni tipovi podataka mogu biti novi, pa hajde da prvo razmotrimo njihovu ulogu u procesu razvoja programa. Prije svega, uporedimo apstraktni tip podataka sa tako poznatim konceptom kao što je procedura.
Procedura, integralni programski alat, može se posmatrati kao generički koncept operatora. Za razliku od ugrađenih operatora programskog jezika (sabiranja, množenja, itd.), koji su ograničeni u svojim mogućnostima, programer može koristiti procedure za kreiranje vlastitih operatora i njihovu primjenu na operande različitih tipova, a ne samo na osnovne. Primjer takve procedure operatora je standardna rutina množenja matrice.
Još jedna prednost procedura (osim mogućnosti kreiranja novih operatora) je mogućnost njihove upotrebe za inkapsulacija dijelove algoritma tako što će u poseban dio programa smjestiti sve operatore odgovorne za određeni aspekt funkcionisanja programa. Primjer enkapsulacije: korištenje jedne procedure za čitanje ulaznih podataka bilo kojeg tipa i provjeru njihove ispravnosti. Prednost enkapsulacije je u tome što znamo koje inkapsulirane izjave treba promijeniti u slučaju problema u funkcionisanju programa. Na primjer, ako je potrebno organizirati provjeru ulaznih podataka za pozitivne vrijednosti, potrebno je promijeniti samo nekoliko redova koda, a znamo gdje se ti redovi nalaze.
Definicija apstraktnog tipa podataka
Mi definišemo apstraktni tip podataka(ADT) kao matematički model sa skupom operatora definisanim u okviru ovog modela. Jednostavan primjer ADT-a je skup cijelih brojeva s operatorima unije, presjeka i razlike skupova. U ADT modelu, operatori mogu imati kao operande ne samo podatke definisane ADT-om, već i podatke drugih tipova: standardni tipovi programskog jezika ili definisani u drugim ADT-ovima. Rezultat operacije operatora također može biti različitog tipa od onih definiranih u ovom ADT modelu. Ali pretpostavljamo da barem jedan operand ili rezultat bilo kojeg operatora ima tip podataka definiran u razmatranom ADT modelu.
Dve karakteristične karakteristike procedura — generalizacija i inkapsulacija — o kojima se raspravljalo iznad su odlične za apstraktne tipove podataka. ADT se može smatrati generalizacijom jednostavnih tipova podataka (cijeli brojevi, realni brojevi, itd.), baš kao što je procedura generalizacija jednostavnih operatora (+, -, itd.). ADT inkapsulira tipove podataka u smislu da se definicija tipa i svi izrazi izvedeni na podacima tog tipa nalaze u jednom dijelu programa. Ako je potrebno promijeniti implementaciju ADT-a, znamo gdje pronaći i šta promijeniti u jednom malom dijelu programa i možemo biti sigurni da to neće dovesti do grešaka nigdje u programu pri radu sa ovim tipom podataka. Štaviše, izvan odeljka o definiciji ADT operatora, ADT tipove možemo smatrati primarnim tipovima, pošto deklaracija tipova nije formalno povezana sa njihovom implementacijom. Ali u ovom slučaju mogu nastati poteškoće, budući da se neki operatori mogu pokrenuti za više od jednog ADT-a i reference na te operatore moraju biti u odjeljcima nekoliko ADT-ova.
Da biste ilustrovali osnovne ideje iza kreiranja ADT-a, razmotrite pohlepnu rutinu iz prethodnog odeljka (Listing 1.3), koja koristi jednostavne operatore na apstraktnom tipu podataka LIST (lista celih brojeva). Ovi operatori moraju izvršiti sljedeće akcije na varijablu newclr tipa LIST.
1. Neka lista bude prazna.
2. Odaberite prvi element liste i, ako je lista prazna, vratite vrijednost null.
3. Odaberite sljedeću stavku na listi i vratite vrijednost null, ako nema sljedeće stavke.
4. Umetnite cijeli broj u listu.
Moguće je koristiti različite strukture podataka pomoću kojih možete efikasno izvoditi opisane radnje. (Strukture podataka će biti detaljno razmotrene u Temi 2.) Ako u Listingu 1.3 zamijenite odgovarajuće operatore izrazima
MAKENULL (newcJr);
w: = PRVI (newcJr);
w: = NEXT (newcfr);
INSERT (v, newclr);
tada će se razumjeti jedan od glavnih aspekata (i prednosti) apstraktnih tipova podataka. Tip podataka možete implementirati na bilo koji način, a programi koji koriste objekte ovog tipa ne zavise od toga kako je tip implementiran - za to su odgovorne procedure koje implementiraju operatore za ovaj tip podataka.
Vratimo se apstraktnom tipu podataka GRAPH (Graf). Objekti ovog tipa zahtijevaju operatore koji izvode sljedeće radnje.
1. Izabran je prvi neobojeni vrh.
2. Provjerite postoji li ivica između dva vrha.
3. Označite vrh bojom.
4. Odaberite sljedeći neobojeni vrh.
Očigledno, drugi operatori ostaju izvan vidokruga pohlepne procedure, kao što je umetanje vrhova i ivica u graf ili označavanje svih vrhova grafa kao otvorenih. Različite strukture podataka koje podržavaju ovaj tip podataka bit će pokrivene u temama 6 i 7.
Treba naglasiti da broj operatora primijenjenih na objekte ovog matematičkog modela nije ograničen. Svaki skup operatora definira poseban ADT. Evo primjera operatora koje možete definirati za SET (Set) apstraktni tip podataka.
1. MAKENULL (A), Ova procedura čini skup A praznim.
2. UNIJA (A, B, C). Ova procedura ima dva "ulazna" argumenta, skupove A i B, i dodeljuje uniju ovih skupova "izlaznom" argumentu, skupu C.
3. VELIČINA (A). Ova funkcija ima argument skupa A i vraća objekt cjelobrojnog tipa jednak broju elemenata skupa A. Izraz ADT implementacija podrazumijeva sljedeće: prevođenje deklaracija koje definiraju varijable ovog apstraktnog tipa podataka u izjave programskog jezika, plus procedure za svaki operator koji se izvršava na ADT objektima. Implementacija zavisi od strukture podataka, predstavlja ADT. Svaka struktura podataka je izgrađena na osnovu osnovnih tipova podataka programskog jezika koji se koristi pomoću alata za strukturiranje podataka dostupnih u ovom jeziku. Strukture niza i zapisa su dva važna alata za strukturiranje podataka dostupna u Pascalu. Na primjer, jedna od mogućih implementacija varijable S tipa SET može biti niz koji sadrži elemente skupa S.
Jedan od glavnih razloga za definisanje dva različita ADT-a u okviru istog modela je taj što se na objektima ovih ADT-a moraju izvršiti različite akcije, tj. definirati operatore različitih tipova. U ovom sažetku razmatra se samo nekoliko osnovnih matematičkih modela, kao što su teorija skupova i teorija grafova, ali za različite implementacije, različiti skupovi operatora će biti izgrađeni na osnovu ovih modela određenih ADT-ova.
U idealnom slučaju, poželjno je pisati programe na jeziku čiji su osnovni tipovi podataka i operatori dovoljni za implementaciju ADT-a. Sa ove tačke gledišta, jezik Pascal nije baš prikladan jezik za implementaciju raznih ADT-ova, ali, s druge strane, teško je pronaći drugi programski jezik u kojem bi bilo moguće direktno deklarisati ADT-ove. Za više informacija o takvim programskim jezicima, pogledajte bibliografske napomene na kraju teme.
