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 (sabiranje, množenje, itd.), koji su ograničeni u svojim mogućnostima, programer može koristiti procedure za kreiranje sopstveni operateri i primijeniti ih na operande različitih tipova, 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 linija koda, a znamo gdje se ti redovi nalaze.
Definicija apstraktnog tipa podaci
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.
Dva karakteristike procedure - generalizacija i inkapsulacija - o kojima je bilo reči gore, savršeno karakterišu 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 ADT implementaciju, 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, van 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 podataka na apstraktnom tipu podataka LIST (list 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 sljedeća stavka br.
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 ovise o tome kako je tip implementiran - za to su odgovorne procedure koje implementiraju operatore za ovaj tip podataka.
Nazad na apstraktni tip GRAFSKI podaci(Grafikon). Objekti ovog tipa zahtijevaju operatore koji izvode sljedeće radnje.
1. Odabran 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. Razne strukture podaci koji podržavaju ovaj tip podataka biće razmatrani u temama 6 i 7.
Treba naglasiti da broj operatora koji se primjenjuju 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. Termin implementacija ADT 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, jedan od moguće implementacije varijabla 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čite vrste... Ovaj sinopsis pokriva samo neke od glavnih matematički modeli, kao što su teorija skupova i teorija grafova, ali za različite implementacije na osnovu ovih modela biće izgrađeni određeni ADT-ovi različiti 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. Sa ove tačke gledišta, jezik Pascal nije baš pogodan jezik za implementaciju raznih ADT-ova, ali, s druge strane, teško je naći drugi programski jezik u kojem bi bilo moguće direktno deklarisati ADT-ove. Dodatne informacije za takve programske jezike pogledajte bibliografske napomene na kraju teme.
Tip podataka opisuje mnoge objekte sa sličnim svojstvima. Svi tradicionalni programski jezici koriste skup osnovnih tipova podataka (stvarni, cijeli broj, string, 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 pozivanjem na imena polja. Operacije kao što su WRITE, READ, DELETE, UPDATE se mogu izvesti 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 implementirani su 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 bilo koji osnovni tip, ili drugi 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 klase, i kada se odnose na skup instanci objekta - ključna riječ klasa. 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 Razne 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 na današnjem tržištu baza podataka.
Apstraktni tip podataka Podaci Općenito apstraktni tip podataka opšte odredbe specifikacija, prezentacija, implementacija 1
Šta su podaci? Set različitih informacionih objekata nad kojima određene radnje izvode programski operatori nazivaju se podacima. Podaci su neophodan atribut svakog programa. Mogu biti: - zasebni bitovi; - niz nezavisnih bitova; -brojevi u različitim oblicima prezentacije; -bajtovi i grupe nezavisnih bajtova; -nizovi brojeva; -povezane liste; - odvojeni fajlovi i sistemima datoteka. 2
Univerzalna reprezentacija ove raznolikosti podataka je teška i nepraktična. Preporučljivo je podijeliti ih na tipove 3
Šta je tip podataka? Tip podataka je određen: - formatom reprezentacije u memoriji računara prema određenim konvencijama algoritamskog jezika, ali bez potrebe za proračunima; - Mnogo prihvatljive vrijednosti koju varijabla ili konstanta koja pripada odabranom tipu može uzeti; - Skup važećih operacija primjenjivih na ovu vrstu. 4
Primjeri tipova podataka Integer tipovi Realni tip Boolean tip Tip karaktera Nabrojani tip Tip intervala Pokazivači 5
Cjelobrojni tipovi Postoji pet unaprijed definiranih tipova cijelih brojeva: 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 cjelobrojni tip kačenjem. 6
Realni tip Realni tip je podskup brojeva predstavljenih u formatu s pomičnim zarezom s fiksnim brojem cifara. Pisanje vrijednosti 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 cijeli brojevi u stvarnom rasponu. Ove vrijednosti m i e dalje definiraju raspon reprezentacije i preciznost realnog tipa. Primjer: 0,143 E + 22, gdje je m - 0,143; b = 2 (podrazumevano), e = 22. Postoji pet tipova pravi tipovi: pravi (Real), sa jednostrukom preciznošću (Single), sa dvostrukom preciznošću (Double), sa povećanom preciznošću (Extended) i složenim (Comp). 7
Boolean tip Postoje 4 predefinirana logička tipa: Boolean, Byte. Bool, Word. Bool i Long. Bool. Booleove vrijednosti su označene ugrađenim konstantnim identifikatorima False i True. Booleove varijable se mogu koristiti za pohranjivanje rezultata bilo kojeg logičkog proračuna. Za logičke varijable dozvoljene su samo 2 operacije poređenja "=" (jednako) i "" (nije jednako). osam
Tip znakova Skup vrijednosti ovog tipa su znakovi poredani prema proširenom ASCII skupu znakova. Ovo su slova ["A". ... ... "Z", "a". ... ... "z"], cifre ["0". ... ... "9"], znakovi interpunkcije i specijalni znakovi. Varijabla ovog tipa zauzima jedan bajt u memoriji. devet
Nabrojani tip Nabrojani tipovi definiraju uređene skupove vrijednosti nabrajanjem identifikatora koji predstavljaju te vrijednosti. Redoslijed skupova se vrši prema redoslijedu u kojem su navedeni identifikatori. Tip Sedmica = (ponedeljak, utorak, srijeda, četvrtak, petak, subota, nedjelja); deset
Tip intervala Tip intervala je raspon vrijednosti od ordinalnog tipa. Definicija tipa intervala uključuje najmanji i najveća vrijednost u podopseg. Interval tipa = 0.. ... 1000; Ova deklaracija tipa govori kompajleru da su samo brojevi u navedenom rasponu važeći za varijable ovog tipa. Dakle, program može automatski organizirati provjere ispravnosti operacija dodjeljivanja za ove 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 obim i složenost prezentacije informacija povećava, javlja se potreba za pogodnim oblicima njihovog predstavljanja, skladištenja i obrade. 12
Definicija apstraktnog tipa podataka (ADT ili apstraktni tip podataka, ili ADT) je skup apstraktnih objekata koji predstavljaju elemente podataka, i definiranih na njemu skupova operacija koje se mogu izvesti nad elementima ovog skupa. 13
ADT - generalizacija tipova podataka Apstraktni tipovi podataka (ADT) se mogu smatrati sredstvom za proširenje programskih jezika. Hajde da uporedimo apstraktni tip podataka sa tako poznatim konceptom kao što je procedura. Procedura se može posmatrati kao generalizovani koncept operatora. Dvije karakteristične karakteristike procedura, generalizacija i enkapsulacija, savršeno karakteriziraju apstraktne tipove podataka. ADT se može posmatrati kao generalizacija jednostavnih tipova podataka (celobrojni, realni, itd.), kao što je procedura generalizacija jednostavnih operatora (+, -, itd.) 14
Prednosti ATD Abstract strukture podataka su za zgodno skladištenje i pristup informacijama. Oni pružaju korisničko sučelje za uobičajene operacije na pohranjenim objektima, skrivajući detalje implementacije od korisnika. Naravno, ovo je vrlo zgodno i omogućava vam da postignete veću modularnost programa. 15
Primjer za automatizovano upravljanje temperature u raznim prostorijama velike zgrade, koristan ATD bi bio TERMOSTAT. Program može sadržavati mnogo varijable tipa TERMOSTAT koji odgovara stvarnim termostatima u različitim prostorijama zgrade. ADT se može opisati svojim imenom, skupom vrijednosti i važećim operacijama kao i svaki drugi tip podataka. Opis tipa TERMOSTATA: - Tip podataka: TERMOSTAT - Raspon vrijednosti: temperatura se može mijenjati u rasponu od 0 do 50 stepeni (Celzijusa). - Operacije: Više, Donje, Postavi, Provjera, Alarm. (Možete se sjetiti mnogih korisnih operacija, ali previše njih degradira apstrakciju) 16
Nivoi apstrakcije Nivoi apstrakcije su poput slojeva softver... Viši nivoi apstrakcije odražavaju ideju korisnika o rješavanju problema. Niži nivoi apstrakcije - mogućnosti programskog jezika. 17
Primjer apstrakcije na nivou korisnika Arhitekta predstavlja kuću kao zidove, podove, prozore, vrata itd. U ovom slučaju, tip podataka je Crtež. Vrata bi mogla biti dobar apstraktni tip. Tip podataka: Slika. Rad vrata: Draw. Obriši vrata. Door Draw. Dvostruko. Vrata ……. Crtanje. Vrata su apstrakcija visoki nivo odražavajući korisnikov pogled na problem 18
Primjer apstrakcije na nivou programera Programer može predložiti drugi nivo apstrakcije za ove objekte, kao što je pravougaonik. Tip podataka: Pravougaonik Operacije: Crtanje. Rectangle Erase. Rectangle Divide. Pravougaonik. On. Dijelovi ……. Pravougaonik - više apstrakcije nizak nivo jer je bliže implementaciji. 19
ADT konstruktori Svaki ADT mora sadržavati operacije za konstruiranje vrijednosti vlastitog tipa. Takve operacije se nazivaju konstruktori. Trebalo bi da postoji dovoljno konstruktora za generiranje cijelog skupa vrijednosti ovog tipa... ADT koji zadovoljava ovo svojstvo naziva se kompletan. Nepotpuni ADT je greška u dizajnu. dvadeset
Preporuke za izbor operacija apstraktnog tipa podataka Preporučljivo je uključiti sljedeće operacije: - operacije konstruktora, - operacije provjere, - operacije konverzije tipa, - I/O operacije, - operacije kopiranja, - operacije selektora. Pokušajte da broj operacija bude što manji. Jednostavan ADT je lakši za razumevanje. Održavajte povezanost operacija s odabranom apstrakcijom tipa. 21
Operacije primarnog konstruktora koje kreiraju nove ADT vrijednosti bez obzira na njihovu prethodnu vrijednost nazivaju se primarnim konstruktorima. Svaki ADT uključuje najmanje jedan primarni konstruktor: bez njega je nemoguće generirati početnu vrijednost. 22
Korištenje skrivenih tipova Apstraktne tipove podataka najbolje je deklarirati kao skrivene tipove. Ovo vam omogućava da premestite opis strukture podataka u modul implementacije, gde se primarno koristi. Oni takođe pružaju mogućnost prevencije direktan pristup tipskim komponentama sa strane uvoznika. Budući da se skriveni tip uvijek implementira pomoću pokazivača, tri operacije moraju biti uključene u ADT. - Kreiraj - operacija koja kreira čvor odgovarajuće strukture. - Destroy - operacija oslobađanja memorije čvora skriveni tip... - Assign — operacija kopiranja polja dinamičke strukture čvora skrivenog tipa. 23
Šta je specifikacija i implementacija apstraktnog tipa podataka Apstraktni tip podataka je način definisanja određenog koncepta u obliku klase objekata sa nekim svojstvima i operacijama. U programskom jeziku, takva definicija je formalizirana kao posebna sintaktička konstrukcija koja se zove in različitim jezicima kapsula, modul, klaster, klasa, paket, obrazac, itd. Ova konstrukcija u svom najnaprednijem obliku sadrži: specifikaciju tipa podataka, uključujući opis interfejsa (naziv definisanog tipa, nazive operacija sa naznakom njihovih profili) i apstraktni opis operacija i objekata sa kojima rade, nekim sredstvima specifikacije; implementacija tipa podataka koja uključuje specifičan opis istih operacija i objekata. 24
Klasifikacija tipova podataka po načinu opisa i zaštite je upakovana, ako je opis tipa podataka sakupljen na jednom mestu (u jednom paketu), odnosno, njegovi objekti i operacije su kombinovani u jedan koncept; ima definiciju, koja, međutim, može sadržati samo njegovu implementaciju; enkapsulirano, ako je tip podataka upakovan, njegova definicija sadrži opis interfejsa i implementaciju, a takođe je obezbeđena inkapsulacija implementacije; apstraktno ako je tip podataka enkapsuliran i njegova specifikacija uključuje apstraktni opis. 25
Komponente specifikacije Programiranje, kao proces, počinje konstatacijom problema (njegova definicija), odnosno specifikacijom problema. Nadalje, u cijelom tekstu se koriste specifikacije koje se sastoje od šest komponenti: - Naziv - naziv problema koji se rješava; - Opis - nekoliko rečenica koje opisuju suštinu zadatka; - ulaz - Detaljan opis očekivani oblik ulaznih podataka; - Izlaz - detaljan opis očekivanog oblika izlaznih podataka; - Greške - detaljna lista situacije koje proizlaze iz netač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 je u nju moguće "staviti" neki element i iz njega "odabrati" element koji je tu postavljen nedavno. Sintaksički dio STEK specifikacije tipa podataka ima tip pogleda STACK specifikacija je CREATE: funkcija () return (@); INSERT: funkcija (cijeli broj; @) povratak (@); DELETE: funkcija (@) povratak (@); TOP: funkcija (@) povratak (cijeli broj); EMPTY: funkcija (@) povratak (boolean); krajnja specifikacija; Ovdje operacija CREATE daje prazan stek kao rezultat, INSERT - stek čiji je element dodat na "vrh", DELETE - stek sa uklonjenim "top" elementom, TOP - vrijednost elementa "top" steka , PRAZNO - znak praznog steka. Ovdje samo cijeli brojevi mogu biti elementi steka. 27
IMPLEMENTACIJA APSTRAKTNOG TIPA PODATAKA Implementaciju je pogodnije uraditi korišćenjem objektno orijentisanih programskih jezika, kao što su C++ ili Java, u kojima su apstraktni tipovi podataka podržani korišćenjem klasa. ADT implementacija uključuje konkretan opis objekata tipa koji se koristi definisana i implementacija operacija tog tipa. To znači da se objekti opisuju kao jednostavni tipovi podataka, ili kao nizovi, zapisi ili unije. Osim toga, koriste se unaprijed definirani tipovi podataka ili ADT-ovi definirani ranije. Implementacija operacija se sastoji u opisu potprograma koji se izvode neophodne radnje sa navedenim objektima. Na primjer, operacije +, *, =. ... i tako dalje, ali je u isto vrijeme skrivena sama implementacija ovih operacija. 28
Razvijanje apstraktnih modela za podatke i način obrade tih podataka je bitna komponenta u procesu rješavanja problema pomoću 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.
Sve računarski sistemi na osnovu nivoa apstrakcije: određena fizička svojstva silicijuma i drugih materijala omogućavaju usvajanje apstraktnog modela bita, koji može imati binarne vrijednosti 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 pogodni su za rješavanje problema u brojnim područjima primjene, kao i za stvaranje apstraktnih mehanizama višeg nivoa koji koriste ove osnovne konstrukcije. Apstraktni tipovi podataka nam pružaju beskonačno proširiv skup alati 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 strojna uputstva; 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 odnose i 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 kreiranje 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 ni na 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 sa pokretnim zarezom, označenih sa x i y. Ova upotreba tipova podataka je uobičajena u veliki sistemi softver: razvijamo skup konvencija o prezentaciji podataka (kao i definiramo brojne povezane operacije) i činimo ta pravila dostupnima preko sučelja tako da ih mogu koristiti klijentski programi uključeni u veliki sistem... Tip podataka osigurava da su svi dijelovi sistema konzistentni s 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 preć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 napišemo definiciju kao što je int i u programu, kažemo sistemu da rezerviše memorijsku oblast za podatke (inline) tipa int kojoj može pristupiti i. U jeziku C++ postoji termin objekat 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 kada 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 funkcije članice mu 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 i 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, gde se ne kombinuju samo podaci, već se definišu i operacije sa 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.
