1.2. Apstraktni tipovi podataka
Većina koncepata predstavljenih u prethodnom odjeljku obično se uči na početnom tečaju programiranja i trebali bi vam biti poznati. Samo apstraktni tipovi podataka mogu biti novi, pa raspravimo prvo njihovu ulogu u procesu razvoja programa. Prije svega, usporedimo apstraktni tip podataka s tako poznatim konceptom kao što je procedura.
Procedura, integralni programski alat, može se smatrati generaliziranim konceptom operatora. Za razliku od ugrađenih operatora programskog jezika (zbrajanje, množenje itd.), koji su ograničeni u svojim mogućnostima, koristeći procedure koje programer može kreirati vlastite operatere i primijeniti ih na operande raznih vrsta, ne samo na osnovne. Primjer takve operatorske procedure je standardni potprogram množenja matrica.
Još jedna prednost procedura (osim mogućnosti stvaranja novih iskaza) je da se mogu koristiti za enkapsulacija dijelova algoritma stavljanjem u zasebnu sekciju programa svih operatora odgovornih za određeni aspekt funkcioniranja programa. Primjer enkapsulacije: korištenje jedne procedure za čitanje unosa bilo koje vrste i provjeru njegove valjanosti. Prednost enkapsulacije je što znamo koje enkapsulirane izjave je potrebno promijeniti ako se pojave problemi u radu programa. Na primjer, ako trebamo provjeriti pozitivne vrijednosti ulaznih podataka, trebamo promijeniti samo nekoliko redaka koda, a znamo točno gdje se ti redovi nalaze.
Definicija apstraktni tip podaci
Mi definiramo apstraktni tip podataka(ATD) kao matematički model sa skupom operatora definiranih 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 operande ne samo podataka definiranih ADT-om, već i podataka drugih tipova: standardnih tipova programskog jezika ili definiranih u drugim ADT-ovima. Rezultat radnje operatora također može biti različite vrste 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 postupci - generalizacija i enkapsulacija - o kojima se govori gore, savršeno karakteriziraju 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 enkapsulira tipove podataka u smislu da su definicija tipa i sve izjave izvedene na podacima tog tipa sadržane u jednom odjeljku programa. Ako trebamo promijeniti implementaciju ADT-a, znamo gdje pronaći i što promijeniti u jednom malom odjeljku programa i možemo biti sigurni da to neće dovesti do pogrešaka bilo gdje u programu pri radu s tom vrstom podataka . Štoviše, izvan odjeljka o definiranju ADT operatora, ADT tipove možemo smatrati primarnim tipovima, budući da deklaracija tipova nije formalno povezana s njihovom implementacijom. Ali u ovom slučaju mogu nastati poteškoće, budući da se neki iskazi mogu pokrenuti za više od jednog ADT-a, a reference na te iskaze moraju biti u odjeljcima nekoliko ADT-ova.
Za ilustraciju osnovnih ideja koje vode do stvaranja ADT-a, razmotrite pohlepni postupak iz prethodnog odjeljka (Ispis 1.3), koji koristi jednostavne operatore na podacima apstraktnog tipa podataka LIST (popis cijelih brojeva). Ovi operatori moraju izvršiti sljedeće radnje na newclr varijabli tipa LIST.
1. Neka popis bude prazan.
2. Odaberite prvi element popisa i, ako je popis prazan, vratite vrijednost ništavan.
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. (Strukture podataka će se detaljno raspravljati u temi 2.) Ako u ispisu 1.3 zamijenimo odgovarajuće operatore izrazima
MAKENULL(newcJr);
w:= PRVI(newcJr);
w:= SLJEDEĆI(newcfr);
INSERT(v, newclr);
Ovo će objasniti 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 načinu na koji je tip implementiran - to je odgovornost procedura koje implementiraju operatore za ovaj tip podataka.
Vratimo se apstraktnom tipu GRAPH podaci(Grafikon). Objekti ovog tipa zahtijevaju operatore koji rade sljedeće:
1. Odaberite prvi neobojeni vrh.
2. Provjerite postoji li brid između dva vrha.
3. Označite vrh bojom.
4. Odaberite sljedeći neobojeni vrh.
Očito, drugi operatori ostaju izvan opsega pohlepne procedure, kao što je umetanje vrhova i bridova u graf ili označavanje svih vrhova grafa kao nezasjenjenih. Različite strukture podataka koje podržavaju ovu vrstu podataka bit će pokrivene u temama 6 i 7.
Posebno treba naglasiti da broj operatora koji se primjenjuju na objekte ovog matematičkog modela nije ograničen. Svaki skup iskaza definira zasebni ADT. Evo primjera operatora koji se mogu definirati za apstraktni tip podataka SET (Set).
1. MAKENULL(A), Ova procedura čini skup A praznim skupom.
2. UNIJA(A, B, C). Ova procedura uzima dva "ulazna" argumenta, skupove A i B, i dodjeljuje uniju tih skupova "izlaznom" argumentu, skup C.
3. VELIČINA (A). Ova funkcija uzima argument skupa A i vraća objekt cjelobrojnog tipa jednakog broju elemenata skupa A. Izraz implementacija ADT-a podrazumijeva sljedeće: prevođenje u programski jezik iskaza deklaracija koje definiraju varijable ovog apstraktnog tipa podataka, plus procedure za svaka izjava izvršena na ADT objektima. Implementacija ovisi o strukture podataka, koji 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 tom jeziku. Strukture polja i zapisa dva su 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 definiranje dva različita ADT-a unutar istog modela je taj što se moraju izvršiti različite radnje na objektima tih ADT-a, tj. definirati operatore različiti tipovi. Ovaj sažetak pokriva samo nekoliko osnovnih matematički modeli, kao što su teorija skupova i teorija grafova, ali s različitim implementacijama, određeni ADT-ovi bit će izgrađeni na temelju tih 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 ovog gledišta Pascal jezik nije baš prikladan jezik za implementaciju raznih ADT-ova, ali, s druge strane, teško je pronaći neki drugi programski jezik u kojem bi bilo moguće tako izravno deklarirati ADT. Dodatne informacije Za takve programske jezike pogledajte bibliografske bilješke na kraju teme.
Tip podataka opisuje skup objekata sličnih svojstava. Svi tradicionalni programski jezici koriste skup osnovnih tipova podataka (pravi, cijeli broj, niz, znakovi). Osnovni tipovi podataka podliježu unaprijed definiranom skupu operacija. Na primjer, osnovni tip podataka cijeli broj omogućuje 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 podataka u kojima će biti pohranjeni podaci o kupcima, možete izravno pristupiti ovoj podatkovnoj strukturi pozivajući se na nazive polja. Na zapisu možete izvoditi operacije kao što su WRITE, READ, DELETE, UPDATE. Ne možete definirati nove operacije za osnovne tipove 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 ne dopuštaju izravan pristup internom prikazu podataka i implementaciji metode.
Neki objektno orijentirani sustavi (kao što je Smalltalk) implementiraju osnovne tipove podataka kao apstraktne.
Za izradu apstraktnog tipa podataka morate osigurati:
· naziv tipa;
· prikaz podataka ili varijable instance objekta u vlasništvu ATD-a; Svaka varijabla instance ima tip podataka, koji može biti bilo koji osnovni tip, ili drugi ATD;
· operacije pod ATD i ograničenja provode se metodama.
ATD definicija ponovno gradi definiciju klase. Neki objektno orijentirani sustavi koriste ključnu riječ type za razlikovanje između klasa i tipova kada se pozivaju na podatkovne strukture i metode klase, a kada se referira na skup instanci objekta - ključna riječ razreda. Tip je statičniji koncept, dok se klasa prvenstveno bavi vremenom izvođenja. Razlika između OO klase i OO tipa može se ilustrirati primjerom. Recimo da imamo predložak za konstruktor. Predložak je popraćen opisom strukture, kao i uputama za korištenje. 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.
ATD zajedno s nasljeđivanjem omogućuje stvaranje složenih objekata. Složeni objekt nastaje kombinacijom drugih objekata koji su međusobno u složenim odnosima. Primjer složeni objekt mogu se naći u sigurnosnim sustavima u kojima se koriste Različite vrste podaci:
1. standardni (tabelarni) podaci o zaposleniku (ime i prezime, br. tablice i sl.);
2. bitmapa za pohranjivanje fotografije zaposlenika;
Mogućnost rada s tako složenim podatkovnim okruženjem s relativnom lakoćom povećava vrijednost OO sustava za moderno tržište baze podataka.
Sažetkom se obično naziva tip podataka koji nije eksplicitno prisutan u programskom jeziku; u tom smislu, ovo je relativan koncept - tip podataka koji je odsutan u jednom programskom jeziku može biti prisutan u drugom.
Apstraktni tip podataka (ATD) definira se bez obzira na način njegove provedbe:
puno moguće vrijednosti ovaj tip
i skup operacija s vrijednostima ovog tipa.
Korištenje ADT-a može biti ograničeno na fazu razvoja softver, ali da biste ga eksplicitno koristili u programu, morate imati njegovu implementaciju temeljenu na postojećim (i prethodno implementiranim) tipovima podataka u programskom jeziku:
način predstavljanja vrijednosti ove vrste,
i provedba operacija s vrijednostima ovog tipa.
ADT nije unaprijed definiran u programskom jeziku, čak štoviše, konstrukcijske operacije takvih tipova, unaprijed definiranih u jeziku, prebacuju programeru-programeru pitanje kako predstaviti vrijednosti ove vrste i implementirati operacije s vrijednostima ove vrste. Stoga se za takve tipove podataka postavlja pitanje izbora definicija i metoda za implementaciju operacija obrasca konstruktor (vrijednosti i pohrane podataka) ove vrste, selektor I modifikator komponente (vrijednosti i pohrane podataka) ove vrste ostaju na programeru programera.
U konceptu ADT koncepti imaju poseban status sučelje , otvoren za korisnika i implementacija , skriven od njega. Posebna uloga ovih pojmova u konceptu ADT-a povezana je s temeljnim stavom o neovisnosti koncepta ADT-a o načinu njegove provedbe.
U modernim "praktičnim programskim jezicima", operacija konstrukcije unaprijed definiranog tipa obično se koristi za konstrukciju ADT-a razreda , koji razvijaču-programeru daje ne samo sredstva grupiranja podataka i operacija (s tim podacima) u jedinstvenu cjelinu, već i sredstva enkapsulacije, nasljeđivanja i polimorfizma za kontrolu načina na koji se takvi podaci konstruiraju i kako im se pristupa. Imajte na umu da klasa opisuje jednu moguću implementaciju ADT-a, preslikavanje klase u ADT izraženo je funkcijom apstrakcije, ali inverzna relacija obično nije funkcionalna; može postojati nekoliko implementacija istog ADT-a.
U istraživanju apstraktnih tipova podataka važna je uloga koncepta " parametrizacija tipa " Doista, na primjer, ADT "Stop" ne ovisi o vrsti elemenata steka, ali je nemoguće implementirati ovaj ADT ukazivanjem na "elemente nekog identičnog tipa". U programskom jeziku Ada inicijalno su uključeni odgovarajući alati za konstrukciju parametriziranih tipova podataka, au modernim “praktičnim programskim jezicima” koji su se alati pojavili tek od pojave razvoja pomoću STL biblioteke. Danas koncept "generaliziranog programiranja" zauzima značajno mjesto u praktičnom programiranju zbog svoje uključenosti u "praktične programske jezike" alati za konstrukciju parametriziranih tipova podataka (predlošci, šablona , generički) .
Sve navedeno znači da je s metodološkog i teorijskog gledišta potrebno detaljnije preciznije definiranje pojma „apstraktni tip podataka“. U teoriji se koncept "apstraktnog tipa podataka" obično definira kao multi-sorted (multi-basic) algebarski sustav , u kojem su, osim skupa mogućih vrijednosti (nosač) i skupa operacija na takvim vrijednostima, istaknuti sljedeći pojmovi:
Sortiranje i potpis - ovi vam koncepti omogućuju klasificiranje medijskih elemenata i operacija s njima prema njihovim vrstama (za operacije - prema vrstama njihovih argumenata i povratne vrijednosti).
Predikati su relacije na elementima nositelja. To vam omogućuje određivanje raspona mogućih vrijednosti nametanjem ograničenja (zahtjeva). važeće vrijednosti, a također iu prirodnom tumačenju rad s proizvoljnim logički izrazi, a da ih se ne mora tumačiti kao funkcije pripadnosti skupovima ili kao operacije s više vrijednosti.
Na ovoj osnovi, moguće je razmatrati apstraktne tipove podataka s jednog holističkog logičko-algebarskog gledišta, uključujući pitanja o konstruktorima (tipovi i vrijednosti), selektorima i modifikatorima svojstava za objekte ovog tipa.
Koncepti "struktura podataka" i "apstraktni tip podataka" na neki su način vrlo bliski. Može se, naravno, pretpostaviti da su ti koncepti jednostavno dva pogleda na istu stvar. Način na koji ADT predstavlja vrijednosti uvijek se temelji na nekoj strukturi podataka, manje ili više složenoj, a implementacija operacija na takvim vrijednostima prirodno ovisi o ovoj odabranoj strukturi podataka. S druge strane, ako stvarno želimo, uvijek možemo dizajnirati strukturu podataka koja nas zanima kao ADT.
Ali ipak ćemo razlikovati ova dva koncepta, uzimajući u obzir:
Apstraktni tip podataka - podrazumijeva određenu razinu apstrakcije kako bi se fiksirao primijenjeni (domeno orijentirani) tip podataka, bez obzira na metode njegove implementacije, a moguće je uključiti ovaj tip podataka u aplikacijsku biblioteku, dobro, barem za specifični razvoj specifičnog programski sustav. ADT može imati nekoliko alternativnih implementacija na temelju različitih struktura podataka.
Struktura podataka zapravo je neka shema za organiziranje podataka i upravljanje njima, što pretpostavlja odgovarajuće specifikacije kada se koristi u specifičnim situacijama pri rješavanju specifičnih problema.
Apstraktni tipovi podataka prvenstveno prirodno uključuju matematičke osnovne algebarske sustave - nizove, skupove, relacije i preslikavanja (funkcionalne relacije, funkcije). Ali u programiranju istraživanje nije u prvom planu. opća svojstva te matematičkih koncepata, te mogućnosti njihove upotrebe u razvoju modela za rješavanje problema predmetnog područja, algoritama za rješavanje tih problema i učinkovitu implementaciju razvijenih algoritama. Stoga su u programiranju u obliku ADT-a, s jedne strane, ograničene verzije ovih osnovnih algebarskih sustava obično formalizirane, a s druge strane proširene specijaliziranim skupovima operacija koje su od pragmatičnog interesa sa stajališta polje primjene.
Razvijanje apstraktnih modela za podatke i načine obrade tih podataka je bitna komponenta u procesu rješavanja problema pomoću računala. Vidimo primjere ovoga i na niskoj razini u svakodnevnom programiranju (na primjer, kada se koriste nizovi i povezani popisi, o čemu se raspravlja u), i na visokoj razini kada se rješava primijenjeni problemi(kao kod rješavanja problema povezivanja upotrebom šume pretraživanja pridruživanja u "Uvodu"). Ovo predavanje raspravlja o apstraktnim tipovima podataka (u daljnjem tekstu ADT), koji vam omogućuju izradu programa korištenjem apstrakcija visoke razine. Apstraktni tipovi podataka dopuštaju da se apstraktne (konceptualne) transformacije koje programi izvode na podacima odvoje od bilo koje konkretne reprezentacije strukture podataka i svake konkretne implementacije algoritma.
svi računalni sustavi na temelju razina apstrakcije: određena fizička svojstva silicija i drugih materijala dopuštaju usvajanje apstraktnog modela bita koji može poprimiti binarne vrijednosti 0-1; tada se apstraktni model stroja gradi na dinamičkim svojstvima vrijednosti određenog skupa bitova; dalje, na temelju principa rada stroja pod programskom kontrolom na strojni jezik gradi se apstraktni model programskog jezika; i konačno, konstruiran je apstraktni koncept algoritma, implementiran kao program u C++. Apstraktni tipovi podataka omogućuju daljnji nastavak ovog procesa i razvoj apstraktnih mehanizama za određene računalne zadatke na višoj razini od one koju pruža C++ sustav, razvoj apstraktnih mehanizama usmjerenih na specifične aplikacije i prikladan za rješavanje problema u brojnim područjima primjene, kao i stvaranje apstraktnih mehanizama za više visoka razina, koji koriste ove osnovne dizajne. Apstraktni tipovi podataka pružaju nam beskonačno proširiv skup alata rješavati sve više i više novih problema.
S jedne strane, korištenje apstraktnih konstrukcija oslobađa vas brige oko njihove detaljne implementacije; s druge strane, kada izvođenje Program je važan, morate znati troškove obavljanja osnovnih operacija. Koristimo puno ugrađenih osnovnih apstrakcija 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 sistemski softver. Apstraktne konstrukcije visoke razine često se stvaraju na temelju više jednostavni dizajni. Na svim razinama vrijedi isto osnovno načelo: potrebno je pronaći najviše važne operacije u programima i većini važne karakteristike podatke, a potom i jedno i drugo precizno definirati na apstraktnoj razini i razviti učinkovite konkretne mehanizme za njihovu provedbu. U ovom predavanju ćemo pogledati mnoge primjere primjene ovog principa.
Razvijanje nove razine apstrakcije zahtijevat će (1) definiranje apstraktnih objekata kojima se mora manipulirati i operacija koje se na njima moraju izvoditi; (2) predstaviti podatke u nekoj strukturi podataka i implementirati operacije; (3) i (što je najvažnije) osigurati da su ti objekti prikladni za korištenje za rješavanje primijenjenih problema. Ove se točke također odnose na jednostavne vrste podataka, tako da se osnovni mehanizmi za podršku tipovima podataka koji su razmatrani u "Elementarnim strukturama podataka" mogu prilagoditi za naše potrebe. Međutim, jezik C++ nudi važno proširenje mehanizam struktura, nazvan klasa (klasa). Klase su izuzetno korisne u stvaranju slojeva apstrakcije i stoga se smatraju primarnim alatom korištenim u tu svrhu u ostatku knjige.
Definicija 4.1. Apstraktni tip podataka (ADT) je tip podataka (skup vrijednosti i skup operacija na tim vrijednostima) kojem se može pristupiti samo putem sučelja. Program koji koristi ADT naziva se klijent, a program koji sadrži specifikaciju ovog tipa podataka naziva se implementacija.
To je riječ koja tip podataka samo čini apstraktnim: u slučaju ADT-a, klijentski programi nemaju pristup vrijednostima podataka ni na koji način osim operacija opisanih u sučelju. Reprezentacija ovih podataka i funkcije koje provode 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 prezentacija podataka, ali navodeći da klijentskim programima nije dopušten izravan pristup podacima. Drugim riječima, programeri klijentskih programa mogu znati prezentacija podataka, ali ga ne može koristiti ni na koji način.
Kao primjer, razmotrite sučelje tipa podataka za točke (program 3.3) iz odjeljka 3.1 “Osnovne strukture podataka”. Ovo sučelje izričito izjavljuje da su točke predstavljene kao strukture koje se sastoje od para brojeva s pomičnim zarezom, označenih x i y. Ova upotreba tipova podataka uobičajena je u velikih sustava softver: razvijamo skup konvencija o predstavljanju podataka (i također definiramo niz povezanih operacija) i činimo ta pravila dostupnima putem sučelja tako da ih mogu koristiti klijentski programi uključeni u veliki sustav. Vrsta podataka osigurava da su svi dijelovi sustava dosljedni u predstavljanju temeljnih struktura podataka na razini cijelog sustava. Koliko god ova strategija bila dobra, ima jednu manu: ako se trebate promijeniti prezentacija podataka, tada ćete morati promijeniti sve klijentske programe. Program 3.3 opet nam daje jednostavan primjer: Jedan od razloga za dizajniranje ove vrste podataka je olakšati klijentskim programima rad s točkama, a očekujemo da klijenti imaju pristup koordinatama pojedinačnih toč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 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 C++ jezičnu klasu koja odmah definira i podatke i njima pridružene operacije. Program 4.2 je klijentski program, radeći s ovom vrstom podataka. Ova dva programa izvode iste izračune kao programi 3.3 i 3.8. Oni ilustriraju niz osnovnih svojstava klasa koje ćemo sada pogledati.
Kada u programu napišemo definiciju poput int i, govorimo sustavu da rezervira područje memorije za (ugrađene) podatke. tip int, koji se može osloviti imenom i. U jeziku C++ postoji izraz za takve entitete kao objekt. Kada program napiše definiciju kao što je POINT p, kaže se da stvara objekt klase POINT na koji se može referirati imenom p. U našem primjeru, svaki objekt sadrži dva podatkovna elementa, nazvana x i y. Kao i strukture, mogu se nazivati imenima poput p.y.
Podatkovni članovi x i y nazivaju se podatkovni članovi klase. Klasa također može definirati funkcije članice koje implementiraju operacije povezane s ovim tipom podataka. Na primjer, klasa definirana u programu 4.1 ima dvije funkcije članice pod nazivom POINT i distance.
Klijentski programi, kao što je Program 4.2, mogu pozvati funkcije članice povezane s objektom navodeći njihova imena na isti način kao imena podataka sadržanih u strukturi. Na primjer, izraz p.distance(q) izračunava udaljenost između točaka p i q (ista udaljenost treba biti vraćena pozivom q.distance(p)). Funkcija POINT(), prva funkcija u programu 4.1, posebna je funkcija članica koja se naziva konstruktor: ima isto ime kao klasa i poziva se kada želite stvoriti objekt te klase.
Program 4.1. Implementacija POINT klase
Ova klasa definira tip podataka koji se sastoji od skupa vrijednosti koje su "parovi brojeva s pomičnim zarezom" (za koje se pretpostavlja da se tumače kao točke na kartezijanskoj ravnini), kao i dvije funkcije članice definirane za sve instance POINT klasa: funkcija POINT() , koja je konstruktor koji inicijalizira koordinate sa slučajnim vrijednostima između 0 i 1, i funkcija distance(POINT) , koja izračunava udaljenost do druge točke. Prezentacija podataka je privatan i mogu mu pristupiti samo funkcije članice ili ga mijenjati. Same članske funkcije su javne i dostupne svakom klijentu. Kod se može spremiti, na primjer, u datoteku pod nazivom POINT.cxx.
#uključi
Program 4.2. Klijentski program za POINT klasu (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 POINT() konstruktora za inicijalizaciju svakog objekta nasumičnim vrijednostima koordinata). Izraz a[i].distance(a[j]) poziva funkciju člana udaljenosti na objektu a[i] s argumentom a[j] .
#uključi
Definiranje POINT p u klijentskom programu dodjeljuje područje memorije za novi objekt i zatim (koristeći funkciju POINT()) dodjeljuje svakom od njegova dva elementa podataka slučajnu vrijednost u rasponu od 0 do 1.
Ovaj stil programiranja, koji se ponekad naziva i objektno orijentirano programiranje, u potpunosti podržava C++ konstrukcija klase. Klasa se može smatrati proširenjem koncepta strukture, gdje se ne kombiniraju samo podaci, već su definirane i operacije nad tim podacima. Može postojati mnogo različitih objekata koji pripadaju istoj klasi, ali svi su slični po tome što njihovi podatkovni članovi mogu preuzeti isti skup vrijednosti i isti skup operacija može se izvesti na tim podatkovnim članovima - općenito, to su instance iste vrste podataka. U objektno orijentiranom programiranju, objekti su dizajnirani za obradu podataka svojih članova (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, imat ćemo mnogo više operacija za klasu bodova. Na primjer, u programu 4.1 nema čak ni operacija koje vam omogućuju da saznate vrijednosti x i y koordinata. Kao što ćemo vidjeti, dodavanje ovih i drugih operacija prilično je jednostavan zadatak. U 5. dijelu pobliže ćemo pogledati klase za točku 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
Dobar dan, stanovnici Khabre!
Sljedeći post je sažetak mojih razmišljanja o prirodi nastave i ADT-a. Ova razmišljanja nadopunjuju zanimljivi citati iz knjiga gurua razvoja softvera
Uvod
Započnimo s postupnim približavanjem definiciji ADT-a. ADT je prije svega tip podataka, što znači sljedeće: prisutnost određenih dostupnih operacija na elementima ove vrste;
kao i podatke nad kojima se te operacije izvode (raspon vrijednosti).
Što znači riječ "apstraktno"? Prije svega, pojam "apstraktnosti" znači fokusiranje pažnje na nešto važno, au isto vrijeme moramo skrenuti pažnju s detalja koji su u ovom trenutku nevažni. Definicija apstrakcije dobro je obrađena u knjizi Gradyja Boocha. Definicija glasi ovako:
Apstrakcija je odabir i davanje skupu objekata zajedničkih svojstava koja određuju njihove konceptualne granice i razlikuju ih od svih drugih vrsta objekata.
Drugim riječima, apstrakcija nam omogućuje da „rasvijetlimo“ podatke o objektu koji su nam potrebni i istovremeno „zasjenimo“ podatke koji nam nisu važni.
Dakle, što se događa ako spojite koncepte "vrste podataka" i "apstrakcije" zajedno? Dobit ćemo tip podataka koji nam daje određeni skup operacija koje osiguravaju ponašanje objekata ovog tipa podataka, a ovaj tip podataka će također sakriti podatke uz pomoć kojih se to ponašanje implementira. Dakle, dolazimo do koncepta ADT:
ADT je tip podataka koji svoju internu implementaciju skriva od klijenata.
Nevjerojatna stvar je da nam primjenom apstrakcije ADT omogućuje da ne brinemo o detaljima implementacije niske razine, već da radimo s suštinom stvarnog svijeta visoke razine (Steve McConnell).
Vjerujem da kada razvijate ADT, prvo trebate definirati sučelje, budući da sučelje ne bi trebalo ovisiti o internoj reprezentaciji podataka u ADT-u. Nakon definiranja operacija koje čine sučelje, morate se usredotočiti na podatke koji će implementirati navedeno ponašanje ADT-a. Kao rezultat toga, dobit ćemo određenu strukturu podataka - mehanizam koji nam omogućuje pohranu i obradu podataka. Istovremeno, ljepota ADT-a je u tome što ako želimo promijeniti interni prikaz podataka, ne moramo lutati kroz cijeli program i mijenjati svaki redak koda koji ovisi o podacima koje želimo promijeniti. ADT enkapsulira ove podatke, što vam omogućuje promjenu rada objekata ove vrste, a ne cijelog programa.
Prednosti ATD-a
Korištenje ADT-a ima puno prednosti (sve opisane prednosti mogu se pronaći u knjizi Stevea McConnella "Perfect Code"):
- Enkapsulacija detalja implementacije.
To znači da nakon što smo enkapsulirali detalje implementacije ADT-a, dajemo klijentu sučelje s kojim može komunicirati s ADT-om. Promjenom detalja implementacije neće se promijeniti percepcija klijenata o ADT operaciji.
- Smanjena složenost.
Apstrahirajući se od detalja implementacije, fokusiramo se na sučelje, to jest na ono što ADT može učiniti, a ne na to kako se to radi. Štoviše, ADT nam omogućuje da radimo s esencijom stvarnog svijeta.
- Ograničavanje opsega korištenja podataka.
Korištenjem ADT-a možemo biti sigurni da podaci koji predstavljaju unutarnju strukturu ADT-a neće ovisiti o drugim dijelovima koda. U ovom slučaju ostvarena je "neovisnost" ADT-a.
- Vrlo informativno sučelje.
ADT vam omogućuje da cijelo sučelje predstavite u smislu domenskih entiteta, što, vidite, povećava čitljivost i informativnost sučelja.
Steve McConnell preporučuje predstavljanje tipova podataka niske razine, kao što je hrpa ili lista, kao ADT. Zapitajte se što ovaj popis predstavlja. Ako predstavlja popis zaposlenika banke, onda ATD smatrajte popisom zaposlenika banke.
Dakle, shvatili smo što je ADT i nazvali smo prednosti njegove upotrebe. Sada je vrijedno napomenuti da kada razvijate klase u OOP-u, prije svega trebate razmišljati o ADT-u. U isto vrijeme, kao što je rekao Steve McConnell, programirate ne na jeziku, već uz pomoć jezika. To jest, programirat ćete izvan granica jezika, ne ograničavajući se na razmišljanje u terminima nizova ili jednostavnih tipova podataka. Umjesto toga, razmišljat ćete na visokoj razini apstrakcije (na primjer, u smislu proračunskih tablica ili popisa zaposlenika). Klasa nije ništa drugo nego dodatak i način implementacije ADT koncepta. Čak možemo predstaviti klasu kao formulu:
Klasa = ADT + Nasljeđe + Polimorfizam.
Pa zašto biste trebali razmišljati o ADT-u kada razvijate predavanja? Zato što prvo moramo odlučiti koje će operacije činiti sučelje buduće klase, koje podatke sakriti, a kojima omogućiti javni pristup. Moramo razmišljati o tome da sučelje učinimo visoko informativnim, da kod bude lako optimizirati i testirati, i kako možemo pružiti pravu apstrakciju kako bismo mogli razmišljati o entitetima iz stvarnog svijeta, a ne o detaljima implementacije niske razine. Vjerujem da tek nakon definiranja ADT-a trebamo razmišljati o pitanjima nasljeđivanja i polimorfizma.
Vrijedno je napomenuti da je koncept ADT-a pronašao široku primjenu u OOP-u, budući da upravo ovaj koncept nadopunjuje OOP i omogućuje smanjenje složenosti programa u svijetu softverskih zahtjeva koji se brzo mijenja.
Napisao sam ovaj članak kako bih skrenuo pozornost programera na ADT kako bi poboljšali kvalitetu rada i razvoja softvera.
Korišteni izvori:
Steve McConnell - “Savršen kod”;
Robert Sedgwick - “Algoritmi u Javi.”
