1.2. Apstraktni tipovi podataka
Većina koncepata predstavljenih u prethodnom odjeljku obično se podučava u uvodnom tečaju programiranja i trebali bi vam biti poznati. Samo apstraktni tipovi podataka mogu biti novi, pa prvo razmotrimo njihovu ulogu u procesu razvoja softvera. Prvo, usporedimo apstraktni tip podataka s poznatim konceptom procedure.
Postupak, bitan programski alat, može se smatrati generaliziranim konceptom operatora. Za razliku od ugrađenih operatora programskog jezika, koji su ograničeni u svojim mogućnostima (zbrajanje, množenje, itd.), pomoću procedura programer može kreirati vlastitih operatera i primijeniti ih na operande različitih tipova, ne samo na osnovne. Primjer takvog operatora procedure je standardni potprogram množenja matrice.
Još jedna prednost procedura (osim mogućnosti stvaranja novih izraza) je da se na njih može koristiti inkapsulacija dijelove algoritma stavljanjem u poseban dio programa svih operatora odgovornih za određeni aspekt funkcioniranja programa. Primjer enkapsulacije: korištenje jedne procedure za čitanje unosa bilo koje vrste i provjeru valjanosti. Prednost enkapsulacije je u tome što znamo koje inkapsulirane izraze treba promijeniti u slučaju problema u radu programa. Primjerice, ako je potrebno organizirati provjeru ulaznih podataka na pozitivne vrijednosti, potrebno je promijeniti samo nekoliko redaka koda, a točno znamo gdje se ti redovi nalaze.
Definicija apstraktnog tipa podaci
mi definiramo apstraktni tip podataka(ATD) kao matematički model sa skupom operatora definiranim unutar ovog modela. Jednostavan primjer ADT-a bili bi skupovi cijelih brojeva s operatorima unije, sjecišta i razlika skupova. U ADT modelu, operatori mogu imati kao operande ne samo podatke definirane ADT-om, već i podatke drugih tipova: standardne tipove programskog jezika ili one definirane u drugim ADT-ovima. Rezultat operacije operatora također može biti različitog tipa od onih definiranih u danom ADT modelu. Ali pretpostavljamo da barem jedan operand ili rezultat bilo kojeg operatora ima tip podataka definiran u dotičnom ADT modelu.
Dva karakteristike procedure - generalizacija i enkapsulacija - o kojima smo gore govorili, savršeno karakteriziraju apstraktne tipove podataka. ADT se može smatrati generalizacijom jednostavnih tipova podataka (cijeli brojevi, realni brojevi, itd.), kao što je postupak generalizacija jednostavni operatori(+, - itd.). ADT enkapsulira tipove podataka u smislu da su definicija tipa i svi operatori koji se mogu izvesti nad podacima tog tipa smješteni u jedan dio programa. Ako je potrebno promijeniti implementaciju ADT-a, znamo gdje pronaći i što promijeniti u jednom malom dijelu programa, a možemo biti sigurni da to neće dovesti do grešaka nigdje u programu pri radu s tim podacima tip. Štoviše, izvan odjeljka o definiranju ADT operatora, ADT tipove možemo smatrati primarnim tipovima, budući da deklaracije tipa nisu formalno povezane s njihovom implementacijom. Ali u ovom slučaju mogu nastati komplikacije, budući da se neke izjave mogu pokrenuti za više od jednog ADT-a, a reference na te izjave moraju biti u odjeljcima nekoliko ADT-ova.
Kako bismo ilustrirali osnovne ideje koje dovode do stvaranja ADT-a, razmotrimo proceduru pohlepnu iz prethodnog odjeljka (listing 1.3), koja koristi jednostavne operatore za podatke apstraktnog tipa podataka LIST (popis cijelih brojeva). Ovi operatori moraju izvršiti sljedeće radnje na varijablu newclr tipa LIST.
1. Neka popis bude prazan.
2. Odaberite prvi element popisa i, ako je popis prazan, vratite vrijednost null.
3. Odaberite sljedeći element popisa i vratite vrijednost nula, ako sljedeći element Ne.
4. Umetnite cijeli broj u popis.
Moguće je koristiti različite strukture podataka s kojima možete učinkovito izvoditi opisane radnje. (Detaljno ćemo raspravljati o strukturama podataka u temi 2.) Ako u Listu 1.3 zamijenimo odgovarajuće operatore izrazima
MAKENULL(newcJr);
w:= PRVI(novicJr);
w:= NEXT(newcfr);
INSERT(v, newclr);
tada će biti jasan 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 ovise o tome kako je tip implementiran - za to su odgovorne procedure koje implementiraju operatore za ovaj tip podataka.
Natrag na apstraktni tip GRAFSKI podaci(Grafikon). Objekti ovog tipa zahtijevaju operatore koji izvode sljedeće radnje.
1. Odaberite prvi neobojeni vrh.
2. Provjerite postoji li rub između dva vrha.
3. Označite vrh bojom.
4. Odaberite sljedeći nepopunjeni vrh.
Očito, drugi operatori, kao što je umetanje vrhova i bridova u graf ili označavanje svih vrhova grafa kao nepopunjenih, ostaju izvan dosega pohlepne procedure. Razne strukture tipovi podataka koji podržavaju ovu vrstu podataka bit će obrađeni u temama 6 i 7.
Treba naglasiti da broj operatora koji se primjenjuju na objekte ovog matematičkog modela nije ograničen. Svaki skup iskaza definira zaseban ADT. Ovdje su primjeri operatora koji se mogu definirati za apstraktni tip podataka SET (Set).
1. MAKENULL(A), Ovaj postupak čini skup A praznim skupom.
2. UNIJA (A, B, C). Ovaj postupak uzima dva "ulazna" argumenta, skupove A i B, i dodjeljuje uniju ovih skupova svom "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: prijevod u programski jezik izjave deklaracija koje definiraju varijable ovog apstraktnog tipa podataka, plus procedure za svaku naredbu izvedenu na ADT objektima. Provedba ovisi o strukture podataka, predstavlja ATD. Svaka struktura podataka izgrađena je na temelju osnovnih tipova podataka korištenog programskog jezika, korištenjem alata za strukturiranje podataka dostupnih u ovom jeziku. Strukture niza i zapisa dva su važna načina strukturiranja podataka mogućih u Pascalu. Na primjer, jedan od moguće implementacije varijabla S tipa SET može biti niz koji sadrži elemente skupa S.
Jedan od glavnih razloga za definiranje dva različita ADT-a unutar istog modela je taj što se na objektima tih ADT-a moraju izvesti različite radnje, t.j. definirati operatore različiti tipovi. Ovaj sažetak pokriva samo neke od glavnih matematički modeli, kao što su teorija skupova i teorija grafova, ali uz različite implementacije, određeni ADT će biti izgrađeni na temelju ovih modela razni setovi operateri.
U idealnom slučaju, poželjno je pisati programe na jeziku čiji su osnovni tipovi podataka i operatori dovoljni za implementaciju ADT-a. S ove toč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 deklarirati ADT na tako izravan način. . Dodatne informacije za takve programske jezike pogledajte bibliografske bilješke na kraju teme.
Tip podataka opisuje skup objekata sa sličnim svojstvima. Svi tradicionalni programski jezici koriste skup osnovnih tipova podataka (stvarni, cijeli broj, niz, karakter). Osnovni tipovi podataka podliježu unaprijed definiranom skupu operacija. Na primjer, osnovna vrsta podataka cijeli broj omogućuje vam izvođenje operacija kao što su zbrajanje, oduzimanje, množenje i dijeljenje.
Tradicionalni programski jezici uključuju konstruktore tipa, od kojih je najčešći konstruktor zapisa. Na primjer, za zapis tipa CUSTOMER možete definirati podatkovna polja. Unos KUPCA bit će novi tip strukturi podataka, koja će pohraniti informacije o klijentu, možete izravno pristupiti ovoj strukturi podataka pozivanjem na nazive polja. Na zapisu možete izvoditi operacije kao što su WRITE, READ, DELETE, UPDATE. Ne možete definirati nove operacije za osnovne vrste podataka.
Poput osnovnih tipova podataka, apstraktni tipovi podataka (ATD) opisuju mnoge slične objekte. Postoje razlike između ATD i tradicionalni tip podaci:
· operacije pod ATD definira korisnik;
· ATD-ovi ne dopuštaju izravan pristup internom prikazu podataka i implementaciji metoda.
U nekim OO sustavima (na primjer, Smalltalk), osnovni tipovi podataka implementirani su kao apstraktni.
Da biste stvorili apstraktnu vrstu podataka, morate osigurati:
naziv vrste;
Reprezentacija podataka ili varijabli instance objekta u vlasništvu ATD-a; svaka varijabla instance ima tip podataka, koji može biti bilo koji bazni tip, ili neki drugi ATD;
· ATD operacije i ograničenja provode se korištenjem metoda.
ATD definicija obnavlja definiciju klase. U nekim OO sustavima, ključna riječ type koristi se za razlikovanje između klasa i tipova kada se odnosi na strukture podataka i metode klase, i kada se odnosi na skup instanci objekta, ključna riječ razreda. Tip (tip) je više statični koncept, a klasa se uglavnom odnosi na vrijeme izvođenja. Razlika između OO klase i OO tipa može se ilustrirati primjerom. Pretpostavimo da postoji predložak za konstruktor. Predložak je popraćen opisom njegove strukture, kao i uputama za njegovu uporabu. Ovaj predložak je definicija tipa. Skup stvarnih proizvoda izrađenih pomoću predloška, od kojih svaki ima jedinstveni broj (ili OID), čini klasu (klasu).
ATD, zajedno s nasljeđivanjem, omogućuje stvaranje složenih objekata. Složeni objekt nastaje spajanjem drugih objekata koji su međusobno u složenim odnosima. Primjer složeni objekt mogu se naći u sigurnosnim sustavima koji koriste različiti tipovi podaci:
1. standardni (tablični) podaci o zaposleniku (ime i prezime, tab. br. i sl.);
2. bitmapa za pohranu fotografija zaposlenika;
Mogućnost rada s tako složenim podatkovnim okruženjem s relativnom lakoćom povećava važnost OO sustava na današnjem tržištu baza podataka.
Apstraktni tip podataka Opći tipovi podataka Apstraktni tip podataka općim odredbama specifikacija, reprezentacija, implementacija 1
Što su podaci? Set raznih informacijski objekti, na kojem određene radnje izvode programski operateri, nazivaju se podacima. Podaci su neizostavan atribut svakog programa. Mogu biti: - pojedinačni bitovi; - slijed neovisnih bitova; -brojevi u različitim oblicima predstavljanja; -bajtovi i grupe neovisnih bajtova; - nizovi brojeva; - povezane liste; - zasebne datoteke i datotečnim sustavima. 2
Univerzalni prikaz ove raznolikosti podataka je težak i nepraktičan. Preporučljivo je podijeliti ih u vrste 3
Što je tip podataka? Vrsta podataka određena je: – formatom prikaza u memoriji računala prema određenim konvencijama algoritamskog jezika, ali bez potrebe za izračunima; - Puno dopuštene vrijednosti, koju varijabla ili konstanta koja pripada odabranom tipu može uzeti; – Skup valjanih operacija primjenjivih na ovu vrstu. 4
Primjeri tipova podataka Integer Types Real Type boolean tip Vrsta znaka Nabrojani tip Vrsta raspona Pokazivači 5
Cjelobrojni tipovi Postoji pet unaprijed definiranih cjelobrojnih vrsta: Shortint, Integer, Longint, Byte i Word. Svaki tip označava određeni podskup cijelih brojeva. Vrijednost jednog cjelobrojnog tipa može se eksplicitno pretvoriti u drugi integralni tip pomoću cast. 6
Realni tip Realni tip odnosi se na podskup brojeva predstavljenih u formatu s pomičnim zarezom s fiksnim brojem znamenki. Vrijednost s pomičnim zarezom obično uključuje tri vrijednosti - m, b i e - takve da je m * b ^ e = n, gdje je b uvijek 2, a m i e su cjelobrojne vrijednosti u rasponu stvarnog tipa . Ove vrijednosti m i e dalje definiraju raspon reprezentacije i preciznost stvarnog tipa. Primjer: 0,143 E+22, gdje je m 0,143; b=2 (podrazumijevano), e=22. Postoji pet vrsta pravi tipovi: pravi (Real), s jednostrukom preciznošću (Single), s dvostrukom preciznošću (Double), s povećanom preciznošću (Extended) i složenim (Comp). 7
Boolean tip Postoje 4 unaprijed definirana Booleova tipa: Boolean, Byte. Bool, Word. bool i dugo. Bool. Booleove vrijednosti su označene ugrađenim konstantnim identifikatorima False i True. Booleove varijable mogu se koristiti za pohranjivanje rezultata bilo kojeg logičkog izračuna. Za booleove varijable dopuštene su samo 2 operacije usporedbe "="(jednako) i ""(nije jednako). 8
Vrsta znakova Skup vrijednosti ove vrste su znakovi poredani prema proširenom skupu znakova ASCII. Ovo su slova ["A". . . "Z", "a". . . "z"], znamenke ["0". . . "9"], interpunkcijski znakovi i posebni znakovi. Varijabla ovog tipa zauzima jedan bajt u memoriji. devet
Nabrojani tip Nabrojani tipovi definiraju uređene skupove vrijednosti kroz nabrajanje identifikatora koji označavaju te vrijednosti. Skupovi su poredani prema redoslijedu kojim su navedeni identifikatori. Vrsta Tjedan = (ponedjeljak, utorak, srijeda, četvrtak, petak, subota, nedjelja); 10
Tip intervala Tip intervala je raspon vrijednosti od ordinalnog tipa. Definicija tipa intervala uključuje najmanji i najviša vrijednost u podrasponu. Interval tipa = 0. . . 1000; Takva deklaracija tipa govori prevoditelju da su samo brojevi unutar navedenog raspona dopušteni za varijable tog tipa. Dakle, program može automatski organizirati provjere ispravnosti operacija dodjeljivanja za te varijable. jedanaest
Zajedničko za tipove podataka Svaki od tipova podataka odgovara skupu jednostavne operacije. INTEGER-operacije +, -, *, div, mod REAL - operacije + , -, *, / BOOLEAN- operacije - konjunkcija (i), disjunkcija V (ili), negacija (ne) CHAR-operacija ORD (c) -N : (C u ASCII), CHR (I) I-ti znak u ASCII-u Kako se povećava volumen i složenost prezentacije informacija, javlja se potreba za prikladnim oblicima njihovog prikaza, pohranjivanja i obrade. 12
Definicija apstraktnog tipa podataka (ATD ili apstraktni tip podataka, ili ADT) je skup apstraktnih objekata koji predstavljaju elemente podataka i skup operacija definiranih na njemu koje se mogu izvesti nad elementima ovog skupa. 13
ADT – generalizacija tipova podataka Apstraktni tipovi podataka (ATD) mogu se smatrati sredstvom za proširenje programskih jezika. Usporedimo apstraktni tip podataka s poznatim konceptom procedure. Postupak se može promatrati kao generalizirani pojam operatora. Dvije karakteristične značajke procedura - generalizacija i enkapsulacija - savršeno karakteriziraju apstraktne tipove podataka. ADT se može smatrati generalizacijom jednostavnih tipova podataka (cijeli brojevi, realni, itd.), kao što je postupak generalizacija jednostavnih operatora (+, -, itd.)
Prednosti ATD sažetak strukture podataka su za prikladno skladištenje i pristup informacijama. Oni pružaju user-friendly sučelje za tipične operacije pohranjenih objekata, skrivajući detalje implementacije od korisnika. Naravno, to je vrlo zgodno i omogućuje vam postizanje veće modularnosti programa. 15
Primjer za automatizirano upravljanje temperature u raznim prostorijama velike zgrade, TERMOSTAT bi bio koristan ATD. Program može imati mnogo varijable tipa TERMOSTAT koji odgovara pravim termostatima u raznim prostorijama zgrade. ADT se može opisati svojim imenom, skupom vrijednosti i dopuštenim operacijama baš kao i svaki drugi tip podataka. Opis tipa TERMOSTATA: – Vrsta podataka: TERMOSTAT – Raspon vrijednosti: Temperatura može varirati između 0 i 50 stupnjeva (Celzija). – Operacije: Gore, Dolje, Postavi, Provjera, Alarm. (Može se smisliti mnogo korisnih operacija, ali previše njih degradira apstrakciju) 16
Slojevi apstrakcije Slojevi apstrakcije su poput slojeva softver. Najviše razine apstrakcije odražavaju ideju korisnika o rješavanju problema. niže razine apstrakcije su mogućnosti programskog jezika. 17
Primjer apstrakcije na korisničkoj razini Arhitekt predstavlja kuću u smislu zidova, podova, prozora, vrata itd. U ovom slučaju, tip podataka je Slika. Vrata bi mogla biti dobar apstraktni tip. Vrsta podataka: Crtež. Rad na vratima: crtanje. Brisanje vrata. Izvlačenje vrata. Dvostruko. Vrata ……. Slika. Vrata su apstraktna visoka razina, odražavajući korisnikov pogled na problem 18
Primjer apstrakcije na razini programera Programer može predložiti drugu razinu apstrakcije za ove objekte, kao što je pravokutnik. Vrsta podataka: Pravokutnik Operacije: Crtanje. Izbriši pravokutnik. Podjela pravokutnika. Pravokutnik. Na Dijelovi……. Pravokutnik je apstrakcija niska razina, budući da je bliže implementaciji. 19
ADT konstruktori Svaki ADT mora sadržavati operacije za konstruiranje vrijednosti svog tipa. Takve operacije nazivaju se konstruktori. Konstruktori bi trebali biti dovoljni za generiranje cijelog skupa vrijednosti ovog tipa. ADT koji zadovoljava ovo svojstvo naziva se potpun. Nepotpuni ADT je greška u dizajnu. dvadeset
Preporuke za odabir operacija apstraktnog tipa podataka Preporučljivo je uključiti sljedeće operacije: – operacije konstruktora, – operacije provjere, – operacije pretvorbe tipa, – I/O operacije, – operacije kopiranja, – operacije selektora. Pokušajte svesti broj transakcija na minimum. Jednostavan ADT je lakše razumjeti. Zadržite operacije povezane s apstrakcijom tipa po vašem izboru. 21
Operacije primarnog konstruktora koje stvaraju nove vrijednosti za ADT bez obzira na njegovu prethodnu vrijednost nazivaju se primarnim konstruktorima. Svaki ADT uključuje barem jedan primarni konstruktor: bez njega je nemoguće formirati početnu vrijednost. 22
Korištenje skrivenih tipova Apstraktne tipove podataka najbolje je deklarirati kao skrivene tipove. To omogućuje premještanje opisa strukture podataka u implementacijsku jedinicu, gdje se ona pretežno koristi. Oni također pružaju priliku za prevenciju Direktni pristup tipskim komponentama na strani uvoznika. Budući da se skriveni tip uvijek implementira s pokazivačem, postoje tri operacije koje moraju biti uključene u ADT. – Create - operacija koja stvara čvor odgovarajuće strukture. – Destroy – operacija oslobađanja memorije čvora skriveni tip. – Assign - operacija kopiranja polja dinamičke strukture čvora skrivenog tipa. 23
Što je specifikacija i implementacija apstraktnog tipa podataka Apstraktni tip podataka je način definiranja koncepta kao klase objekata s nekim svojstvima i operacijama. U programskom jeziku takva je definicija formalizirana kao posebna sintaktička konstrukcija koja se poziva različiti jezici kapsula, modul, klaster, klasa, paket, obrazac itd. Ova konstrukcija u svom najnaprednijem obliku sadrži: specifikaciju tipa podataka, koja uključuje opis sučelja (naziv tipa koji se definira, nazivi operacija s naznakom njihovih profila) i apstraktni opis operacija i objekata s kojima rade, neka sredstva specifikacije; implementacija tipa podataka koja uključuje specifičan opis istih operacija i objekata. 24
Klasifikacija tipova podataka prema načinu opisa i upakiranoj zaštiti, ako je opis vrste podataka prikupljen na jednom mjestu (u jednom paketu), odnosno njegovi objekti i operacije su spojeni u jedan koncept; ima definiciju, koja može sadržavati, međutim, samo njegovu provedbu; enkapsulirano, ako je tip podataka pakiran, njegova definicija sadrži opis sučelja i implementaciju, a također je osigurana inkapsulacija implementacije; apstraktno ako je tip podataka enkapsuliran i njegova specifikacija uključuje apstraktnu deklaraciju. 25
Komponente specifikacije Programiranje, kao proces, počinje iskazom problema (njegova definicija), odnosno specifikacijom problema. U nastavku teksta koriste se specifikacije koje se sastoje od šest komponenti: – Naslov – naziv problema koji se rješava; – Opis – nekoliko rečenica koje opisuju bit zadatka; - ulaz - Detaljan opis predviđeni oblik ulaznih podataka; – Izlaz – detaljan opis predviđenog oblika izlaznih podataka; – Greške – detaljan popis situacije koje proizlaze iz netočnih ulaznih podataka; – Primjer – primjer izvođenja u smislu input-output. 26
Primjer specifikacije Apstraktni tip podataka STEK koji implementira dobro poznatu strukturu podataka koju karakterizira činjenica da u nju možete "staviti" neki element i iz njega "odabrati" element koji je tamo nedavno postavljen. Sintaktički dio specifikacije tipa podataka STACK je tip STACK specifikacija je CREATE: funkcija () return (@); INSERT: funkcija (cijeli broj; @) povratak (@); DELETE: funkcija (@) povratak (@); TOP: funkcija (@) povratak (cijeli broj); PRAZNO: funkcija (@) return(boolean); krajnja specifikacija; Ovdje operacija CREATE kao rezultat proizvodi prazan stog, INSERT - stog čiji je element dodan na "vrh", DELETE - stog s uklonjenim "top" elementom, TOP - vrijednost "top" elementa stog, PRAZAN - znak praznine hrpe. Elementi stoga ovdje mogu biti samo cijeli brojevi. 27
IMPLEMENTACIJA APSTRAKTNE VRSTE PODATAKA Implementacija se prikladnije provodi korištenjem objektno orijentiranih programskih jezika kao što su C++ ili Java, gdje su apstraktni tipovi podataka podržani od strane klasa. Implementacija ADT-a uključuje specifičan opis objekata vrste koja se koristi definirana i provedba operacija tog tipa. To znači da se objekti opisuju ili kao podaci primitivnih tipova, ili kao nizovi, zapisi ili unije. Štoviše, koriste se unaprijed definirani tipovi podataka ili ADT-ovi definirani ranije. Implementacija operacija sastoji se u opisu potprograma koji se izvode potrebne radnje sa navedenim objektima. Na primjer operacije +, *, =. . itd. ali se pritom skriva sama provedba tih operacija. 28
Razvoj apstraktnih modela podataka i načina obrade tih podataka je bitna komponenta u procesu rješavanja problema pomoću računala. Vidimo primjere toga i na niskoj razini u svakodnevnom programiranju (na primjer, kada se koriste nizovi i povezane liste, o kojima se raspravlja u), i na visokoj razini pri rješavanju primijenjeni zadaci(kao kod rješavanja problema povezivanja korištenjem šume pretraživanja pridruživanja u "Uvodu"). Ovo predavanje govori o apstraktnim tipovima podataka (apstraktni tip podataka, u daljnjem tekstu ADT), koji vam omogućuju stvaranje programa pomoću apstrakcija visoke razine. Apstraktni tipovi podataka omogućuju vam da odvojite apstraktne (konceptualne) transformacije koje programi izvode na podacima od bilo kojeg određenog prikaza strukture podataka i bilo koje određene implementacije algoritma.
Sve računalni sustavi na temelju razina apstrakcije: određena fizička svojstva silicija i drugih materijala omogućuju usvajanje apstraktnog modela bita, koji može poprimiti binarne vrijednosti 0-1; zatim se apstraktni model stroja gradi na dinamičkim svojstvima vrijednosti određenog skupa bitova; nadalje, na temelju principa rada stroja pod kontrolom programa na strojni jezik izgrađuje se apstraktni model programskog jezika; i, konačno, konstruira se apstraktni koncept algoritma koji se implementira kao C++ program. Apstraktni tipovi podataka omogućuju daljnji nastavak ovog procesa i razvoj apstraktnih mehanizama za određene računske zadatke na višoj razini nego što je to predviđeno sustavom C++, razvoj apstraktnih mehanizama usmjerenih na specifične aplikacije i pogodan za rješavanje problema u brojnim područjima primjene, kao i za stvaranje apstraktnih mehanizama više razine koji koriste ove osnovne konstrukcije. Apstraktni tipovi podataka pružaju nam beskonačno proširiv skup alata rješavati sve više novih problema.
S jedne strane, korištenje apstraktnih konstrukcija oslobađa od brige oko njihove detaljne implementacije; s druge strane, kada izvođenje program je važan, morate 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; implementirati druge apstrakcije u softver; i koristiti dodatne apstrakcije koje pruža prethodno napisani softver sustava. Apstraktne konstrukcije visoke razine često se temelje na više jednostavni dizajni. Na svim razinama vrijedi isti osnovni princip: trebate pronaći najviše važne operacije u programima i većina važne karakteristike podatke, a zatim i precizno definirati oboje na apstraktnoj razini i razviti učinkovite konkretne mehanizme za njihovu provedbu. U ovom ćemo predavanju pogledati mnoge primjere primjene ovog principa.
Razvijanje nove razine apstrakcije zahtijevat će (1) definiranje apstraktnih objekata kojima će se manipulirati i operacija koje će se nad njima izvoditi; (2) predstavljaju podatke u nekoj strukturi podataka i implementiraju operacije; (3) i (što je najvažnije) osigurati da su ti objekti prikladni za korištenje za rješavanje primijenjenih problema. Ove točke također se odnose na jednostavni tipovi podataka, tako da se osnovni mehanizmi za podršku tipovima podataka, o kojima je bilo riječi u "Elementarnim strukturama podataka", mogu prilagoditi za naše potrebe. Međutim, jezik C++ nudi važno proširenje mehanizam struktura, nazvan klasa (class). Klase su iznimno korisne u stvaranju razina apstrakcije i stoga se tretiraju kao glavni alat koji se koristi u tu svrhu u ostatku knjige.
Definicija 4.1. Apstraktni tip podataka (ATD) je tip podataka (skup vrijednosti i skup operacija nad tim vrijednostima) kojem se pristupa samo preko sučelja. Program koji koristi ADT zvati će se klijent, a program koji sadrži specifikaciju ovog tipa podataka zvati će se implementacija.
Riječ je koja samo čini vrstu podataka apstraktnom: u slučaju ADT-a, klijentski programi nemaju pristup vrijednostima podataka ni na koji drugi način osim operacijama opisanim u sučelju. Reprezentacija ovih podataka i funkcije koje implementiraju ove operacije su u implementaciji i potpuno su odvojene sučeljem od klijenta. Kažemo da je sučelje neprozirno: klijent ne može vidjeti implementaciju kroz sučelje.
U C++ programima ova je razlika obično malo jasnija, budući da je najlakše stvoriti sučelje uključivanjem prikaz podataka, ali navodeći da klijentskim programima nije dopušten izravan pristup podacima. Drugim riječima, programeri klijenata možda znaju prikaz podataka, ali ga ni na koji način ne mogu koristiti.
Kao primjer, razmotrite sučelje tipa podataka za točke (Program 3.3) iz odjeljka 3.1 "Elementarne strukture podataka". Ovo sučelje eksplicitno izjavljuje da su točke predstavljene kao strukture koje se sastoje od para brojeva s pomičnim zarezom, označenih s x i y. Ova upotreba tipova podataka uobičajena je u veliki sustavi softver: razvijamo skup konvencija o predstavljanju podataka (kao i definiramo skup povezanih operacija) i činimo ta pravila dostupnima putem sučelja kako bi ih mogli koristiti klijentski programi uključeni u veliki sustav. Tip podataka osigurava da su svi dijelovi sustava u skladu s prikazom temeljnih struktura podataka na razini cijelog sustava. Koliko god ova strategija bila dobra, ona ima jedan nedostatak: ako je potrebno promijeniti prikaz podataka, morat ćete promijeniti sve klijentske programe. Program 3.3 opet nam daje jednostavan primjer: jedan od razloga za razvoj ovog tipa podataka je pogodnost klijentskih programa koji rade s točkama, te očekujemo da će klijenti imati pristup pojedinačnim koordinatama točke ako je potrebno. Ali ne možemo se promijeniti na drugačiji prikaz podataka (recimo, polarne koordinate, ili 3D koordinate, ili čak druge vrste 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 u Programu 3.3, ali koristi klasu jezika C++ koja istovremeno definira i podatke i pridružene operacije. Program 4.2 je klijentski program A koji radi s ovom vrstom podataka. Ova dva programa izvode iste izračune kao programi 3.3 i 3.8. Oni ilustriraju niz glavnih svojstava klasa koje ćemo sada razmotriti.
Kada u programu napišemo definiciju poput int i, kažemo sustavu da rezervira memorijsko područje za podatke (ugrađeno) upišite int, kojemu se može pristupiti imenom i. Jezik C++ ima pojam objekt za takve entitete. Kada se definicija kao što je POINT p napiše u programu, kaže se da je stvoren objekt klase POINT, na koji se može pozvati ime p. U našem primjeru, svaki objekt sadrži dva elementa podataka, nazvana x i y. Kao i kod struktura, na njih se može pozivati imenima poput p.y.
Podatkovni članovi x i y nazivaju se podatkovnim članovima klase. Klasa također može definirati funkcije člana koje implementiraju operacije povezane s ovim tipom podataka. Na primjer, klasa definirana u Programu 4.1 ima dvije funkcije člana pod nazivom TOČKA i udaljenost.
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 sadržanih u nekoj strukturi. Na primjer, izraz p.distance(q) izračunava udaljenost između točaka p i q (istu udaljenost treba vratiti pozivanjem q.distance(p)). Funkcija POINT(), prva funkcija u Programu 4.1, posebna je funkcija člana nazvana konstruktor: ima isto ime kao klasa i poziva se kada je potrebno kreirati objekt te klase.
Program 4.1. Implementacija klase POINT (točka)
Ova klasa definira tip podataka koji se sastoji od skupa vrijednosti koje su "parovi brojeva s plutajućim zarezom" (pod pretpostavkom da se tumače kao točke u kartezijskoj ravnini), kao i dvije funkcije člana definirane za sve instance POINT klasa: funkcija POINT() , koja je konstruktor koji inicijalizira koordinate sa slučajnim vrijednostima od 0 do 1, i funkcija distance(POINT) koja izračunava udaljenost do druge točke. Prikaz podataka je privatan i samo mu funkcije članice mogu pristupiti ili ga mijenjati. Same funkcije članova su javne (javne) i dostupne svakom klijentu. Kod se može spremiti, na primjer, u datoteku pod nazivom POINT .cxx.
#uključiti
Program 4.2. Klijentski program za klasu POINT (pronalaženje najbliže točke)
Ova verzija programa 3.8 je klijent koji koristi POINT ADT definiran u programu 4.3. Operacija nova stvara niz POINT objekata (pozivanjem konstruktora POINT() za inicijalizaciju svakog objekta s nasumičnim vrijednostima koordinata). Izraz a[i].distance(a[j]) poziva funkciju člana distance na objektu a[i] s argumentom a[j] .
#uključiti
Definiranje TOČKE p u klijentskom programu rezultira dodjeljivanjem memorijskog područja za novi objekt, a zatim (koristeći funkciju POINT()) dodjeljivanjem svakom od njegova dva podatkovna elementa slučajne 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 kombiniraju samo podaci, već se definiraju operacije nad tim podacima. Može postojati mnogo različitih objekata koji pripadaju istoj klasi, ali su svi slični po tome što njihovi članovi podataka mogu poprimiti isti skup vrijednosti, a isti skup operacija može se izvesti nad tim članovima podataka - općenito, oni su instance istog tipa podataka. U objektno orijentiranom programiranju, objekti su dizajnirani za obradu svojih članova podataka (za razliku od korištenja neovisnih funkcija za obradu podataka pohranjenih u objektima).
Gledamo gore opisani primjer male klase samo da bismo se upoznali s osnovnim značajkama klasa; pa je daleko od potpunog. U stvarnom kodu za klasu točaka imat ćemo mnogo više operacija. Na primjer, u programu 4.1 ne postoje čak ni operacije koje vam omogućuju da saznate vrijednosti koordinata x i y. Kao što ćemo vidjeti, dodavanje ovih i drugih operacija prilično je jednostavan zadatak. U 5. dijelu pobliže ćemo pogledati klase za točke i druge geometrijske apstrakcije kao što su linije i poligoni.
U C++ (ali ne u 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.
