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 one osnovne. Primjer takve procedure operatora je standardna rutina množenja matrice.
Još jedna prednost procedura (osim mogućnosti kreiranja novih operatora) je mogućnost njihove upotrebe za inkapsulacija dijelove algoritma tako što će u poseban dio programa smjestiti sve operatore odgovorne za određeni aspekt funkcionisanja programa. Primjer enkapsulacije: korištenje jedne procedure za čitanje ulaznih podataka bilo kojeg tipa i provjeru njihove ispravnosti. Prednost enkapsulacije je u tome što znamo koje inkapsulirane izjave treba promijeniti u slučaju problema u funkcionisanju programa. Na primjer, ako je potrebno organizirati provjeru ulaznih podataka za pozitivne vrijednosti, potrebno je promijeniti samo nekoliko redova koda, a znamo gdje se ti redovi nalaze.
Definicija apstraktnog tipa 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 jednostavni operatori(+, - itd.). ADT inkapsulira tipove podataka u smislu da se definicija tipa i svi izrazi izvedeni na podacima tog tipa nalaze u jednom dijelu programa. Ako je potrebno promijeniti implementaciju ADT-a, znamo gdje pronaći i šta promijeniti u jednom malom dijelu programa i možemo biti sigurni da to neće dovesti do grešaka nigdje u programu pri radu sa ovim tipom podataka. Štaviše, izvan odeljka o definiciji ADT operatora, ADT tipove možemo smatrati primarnim tipovima, pošto deklaracija tipova nije formalno povezana sa njihovom implementacijom. Ali u ovom slučaju mogu nastati poteškoće, budući da se neki operatori mogu pokrenuti za više od jednog ADT-a i reference na te operatore moraju biti u odjeljcima nekoliko ADT-ova.
Da biste ilustrovali osnovne ideje iza kreiranja ADT-a, razmotrite pohlepnu rutinu iz prethodnog odeljka (Listing 1.3), koja koristi jednostavne operatore na apstraktnom tipu podataka LIST (lista celih brojeva). Ovi operatori moraju izvršiti sljedeće akcije na varijablu newclr tipa LIST.
1. Neka lista bude prazna.
2. Odaberite prvi element liste i, ako je lista prazna, vratite vrijednost null.
3. Odaberite sljedeću stavku na listi i vratite vrijednost null, ako 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 zavise od toga 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. Izabran je prvi neobojeni vrh.
2. Provjerite postoji li ivica između dva vrha.
3. Označite vrh bojom.
4. Odaberite sljedeći neobojeni vrh.
Očigledno, drugi operatori ostaju izvan vidokruga pohlepne procedure, kao što je umetanje vrhova i ivica u graf ili označavanje svih vrhova grafa kao otvorenih. Različite strukture podataka koje podržavaju ovaj tip podataka bit će pokrivene u temama 6 i 7.
Treba naglasiti da broj operatora primijenjenih na objekte ovog matematičkog modela nije ograničen. Svaki skup operatora definira poseban ADT. Evo primjera operatora koje možete definirati za SET (Set) apstraktni tip podataka.
1. MAKENULL (A), Ova procedura čini skup A praznim.
2. UNIJA (A, B, C). Ova procedura ima dva "ulazna" argumenta, skupove A i B, i dodeljuje uniju ovih skupova "izlaznom" argumentu, skupu C.
3. VELIČINA (A). Ova funkcija ima argument skupa A i vraća objekt cjelobrojnog tipa jednak broju elemenata skupa A. Izraz ADT implementacija podrazumijeva sljedeće: prevođenje deklaracija koje definiraju varijable ovog apstraktnog tipa podataka u izjave programskog jezika, plus procedure za svaki operator koji se izvršava na ADT objektima. Implementacija zavisi od strukture podataka, predstavlja ADT. Svaka struktura podataka je izgrađena na osnovu osnovnih tipova podataka programskog jezika koji se koristi pomoću alata za strukturiranje podataka dostupnih u ovom jeziku. Strukture niza i zapisa su dva važna alata za strukturiranje podataka dostupna u Pascalu. Na primjer, 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 će za različite implementacije na osnovu ovih modela biti 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 Pascal jezik 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 tako direktno deklarirati 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 pozivajući se na imena polja. Operacije kao što su WRITE, READ, DELETE, UPDATE mogu se izvršiti na zapisu. Ne možete definirati nove operacije za osnovne tipove podataka.
Kao i osnovni tipovi podataka, apstraktni tipovi podataka (ATD) opisuju mnoge slične objekte. Postoje razlike između ATD i tradicionalnog tipa podaci:
· Operacije pod ATD definira korisnik;
· ATD ne dozvoljavaju direktan pristup internom predstavljanju podataka i implementaciji metoda.
U nekim OO sistemima (na primjer, Smalltalk), osnovni tipovi podataka se implementiraju kao apstraktni.
Da biste kreirali apstraktni tip podataka, morate osigurati:
· Ime tipa;
· Prikaz podataka ili varijable instance objekta koji pripada ATD-u; svaka varijabla instance ima tip podataka koji može biti 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 različite vrste podaci:
1. standardni (tabelarni) podaci o zaposlenom (ime i prezime, tab. br. itd.);
2. bitmap za čuvanje fotografije zaposlenog;
Sposobnost da se relativno lako rukuje tako složenim okruženjem podataka povećava vrijednost OO sistema moderno tržište baze podataka.
Uobičajeno je da se apstraktnim tipom naziva tip podataka koji nije eksplicitno dostupan u programskom jeziku; u tom smislu, ovaj koncept je relativan - tip podataka koji je odsutan u jednom programskom jeziku može biti prisutan u drugom.
Apstraktni tip podataka (ADT) se određuje bez obzira na to kako se implementira:
mnoštvo moguće vrijednosti ovaj tip,
i skup operacija nad vrijednostima ovog tipa.
Upotreba ADT-a može se ograničiti na fazu razvoja softvera, ali za njegovu eksplicitnu upotrebu u programu, morate imati njegovu implementaciju zasnovanu na postojećim (i prethodno implementiranim) tipovima podataka u programskom jeziku:
način predstavljanja vrijednosti ove vrste,
i implementaciju operacija nad vrijednostima ovog tipa.
ADT nije predefinisan u programskom jeziku, a čak i više od toga, operacije za konstruisanje takvih tipova, unapred definisane u jeziku, pomeraju pitanje kako predstaviti vrednosti ovog tipa i kako implementirati operacije sa vrednostima ovaj tip na programer-programer. Stoga se za takve tipove podataka postavlja pitanje izbora definicija i metoda implementacije operacija oblika konstruktor (vrijednosti i skladišta podataka) ovog tipa, selektor i modifikator komponente (vrijednosti i skladišta podataka) ovog tipa odgovornost su programera-programera.
U konceptu ADT-a, sljedeći koncepti imaju poseban status: interfejs otvoren za korisnika, i realizacija skriveno od njega. Posebna uloga ovih koncepata u konceptu ADT-a povezana je sa temeljnom odredbom o nezavisnosti koncepta ADT-a od načina njegove implementacije.
U modernim "praktičnim programskim jezicima", operacija konstrukcije unaprijed definiranog tipa obično se koristi za konstruiranje ADT-ova klasa , koji programeru-programeru daje ne samo sredstva za grupisanje podataka i operacija (sa ovim podacima) u jedinstvenu cjelinu, već i sredstva inkapsulacije, nasljeđivanja i polimorfizma za kontrolu načina konstruisanja i pristupa takvim podacima. Imajte na umu da klasa opisuje jednu moguću implementaciju ADT-a, mapiranje klase u ADT je izraženo 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 ". Zaista, na primjer, "Stak" ADT ne ovisi o tipu elemenata steka, ali je nemoguće implementirati ovaj ADT upućivanjem na "elemente istog tipa". U programskom jeziku Ada prvobitno su uključena odgovarajuća sredstva za konstruisanje parametrizovanih tipova podataka, au modernim „praktičnim programskim jezicima“ ta sredstva su se pojavila tek od pojave razvoja STL biblioteke. Danas koncept "generičkog programiranja" zauzima značajno mjesto u praktičnom programiranju zbog uključivanja u "praktične programske jezike" sredstva za konstruisanje parametrizovanih tipova podataka (šabloni, šablon , generički) .
Sve navedeno znači da je sa metodološkog i teorijskog gledišta potrebna detaljnija i preciznija definicija pojma „apstraktni tip podataka“. U teoriji, koncept "apstraktnog tipa podataka" se obično definira kao višestruko sortirani (višebazni) algebarski sistem , u kojem su, pored skupa mogućih vrijednosti (nosač) i skupa operacija nad takvim vrijednostima, istaknuti sljedeći koncepti:
Sortiranje i potpis - ovi koncepti vam omogućavaju da klasifikujete i elemente nosača i operacije s njima prema njihovim tipovima (za operacije, prema tipovima njihovih argumenata i povratnoj vrijednosti).
Predikati su odnosi na elementima nosioca. Ovo omogućava određivanje raspona mogućih vrijednosti nametanjem ograničenja (zahtjeva). dozvoljene vrijednosti, kao i u prirodnoj interpretaciji za rad sa proizvoljnim logičkih izraza bez prisiljavanja da ih se tumači kao funkcije članstva za skupove ili kao operacije sa više vrijednosti.
Na osnovu toga, moguće je razmatrati apstraktne tipove podataka sa jedinstvenog integralnog logičko-algebarskog stanovišta, uključujući pitanja o konstruktorima (tipovima i vrijednostima), selektorima i modifikatorima svojstava za objekte ovog tipa.
Koncepti "strukture podataka" i "apstraktnog tipa podataka" su donekle slični. Možete, naravno, smatrati da su ovi koncepti samo dva pogleda na istu stvar. Način predstavljanja ADT vrijednosti uvijek se temelji na nekoj strukturi podataka, manje ili više složenoj, a implementacija operacija sa takvim vrijednostima prirodno ovisi o ovoj odabranoj strukturi podataka. S druge strane, ako želimo, uvijek možemo dizajnirati strukturu podataka koja nas kao ADT zanima.
Ali ipak ćemo razlikovati ova dva koncepta, s obzirom na:
Apstraktni tip podataka - podrazumijeva određeni nivo apstrakcije kako bi se popravio primijenjeni (specifičan za domen) tip podataka, bez obzira na to kako je implementiran, a moguće je uključiti ovaj tip podataka u biblioteku aplikacije, pa, barem za specifičan razvoj softverski sistem... ADT može imati nekoliko alternativnih implementacija zasnovanih na različitim strukturama podataka.
Struktura podataka je prije neka vrsta sheme organizacije podataka i upravljanje njima, što pretpostavlja odgovarajuću konkretizaciju pri upotrebi u konkretnim situacijama pri rješavanju konkretnih problema.
Prije svega, matematički osnovni algebarski sistemi - nizovi, skupovi, relacije i preslikavanja (funkcionalni odnosi, funkcije) - prirodno pripadaju apstraktnim tipovima podataka. Ali u programiranju, u prvom planu nije istraživanje opšta svojstva ovih matematičkih koncepata, te mogućnosti njihove upotrebe u razvoju modela za rješavanje problema predmetne oblasti, algoritama za rješavanje ovih problema i efektivne implementacije razvijenih algoritama. Stoga se u programiranju, u obliku ADT-a, s jedne strane formiraju ograničene verzije ovih osnovnih algebarskih sistema, as druge strane, oni se proširuju specijalizovanim skupovima operacija koje su sa stanovišta pragmatičnog interesa. oblasti primene.
Razvijanje apstraktnih modela za podatke i način obrade tih podataka je bitna komponenta u procesu rješavanja problema korištenjem računara. Vidimo primjere ovoga i na niskom nivou u svakodnevnom programiranju (na primjer, kada se koriste nizovi i povezane liste o kojima se govori u), i na visokom nivou prilikom rješavanja primijenjeni zadaci(kao kod rješavanja problema povezivanja korištenjem šume pretraživanja pridruživanja u "Uvodu"). Ovo predavanje govori o apstraktnim tipovima podataka (u daljem tekstu ADT), koji vam omogućavaju da kreirate programe koristeći apstrakcije visokog nivoa. Apstraktni tipovi podataka vam omogućavaju da odvojite apstraktne (konceptualne) transformacije koje programi izvode na podacima od bilo kojeg određenog prikaza strukture podataka ili bilo koje posebne implementacije algoritma.
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 pogodan za rješavanje problema u brojnim područjima primjene, kao i stvaranje apstraktnih mehanizama više visoki nivo koji koriste ove osnovne konstrukcije. Apstraktni tipovi podataka nam pružaju beskonačno proširiv skup alata rješavati sve više novih problema.
S jedne strane, upotreba apstraktnih konstrukcija oslobađa vas brige oko njihove detaljne implementacije; s druge strane kada performanse Program je važan, potrebno je znati troškove izvođenja osnovnih operacija. Koristimo mnogo osnovnih apstrakcija ugrađenih u hardver Računalo i služi kao osnova za strojne upute; implementiramo druge apstrakcije u softver; i koristiti dodatne apstrakcije koje obezbjeđuje prethodno napisani sistemski softver. Apstraktne konstrukcije visokog nivoa često se kreiraju na osnovu više jednostavni dizajni... Na svim nivoima vrijedi isti osnovni princip: potrebno je pronaći najviše važne operacije u programima i većina važne karakteristike podatke, a zatim precizno definirati oba na apstraktnom nivou i razviti efikasne konkretne mehanizme za njihovu implementaciju. U ovom predavanju ćemo pogledati mnoge primjere primjene ovog principa.
Da biste razvili novi nivo apstrakcije, moraćete da (1) definišete apstraktne objekte kojima treba manipulisati i operacije koje treba izvršiti na njima; (2) predstavljaju podatke u nekoj strukturi podataka i implementiraju operacije; (3) i (što je najvažnije) osigurati da su ovi objekti pogodni za korištenje za rješavanje primijenjenih problema. Ove tačke se takođe odnose na jednostavni tipovi podataka, tako da se osnovni mehanizmi za podršku tipovima podataka koji su razmatrani u "Atomskim strukturama podataka" mogu prilagoditi za naše potrebe. Međutim, jezik C++ sugeriše važno proširenje mehanizam strukture koji se zove klasa. Klase su izuzetno korisne za stvaranje nivoa apstrakcije i stoga se smatraju primarnim alatom koji se koristi u tu svrhu u ostatku ove knjige.
Definicija 4.1. Apstraktni tip podataka (ADT) je tip podataka (skup vrijednosti i skup operacija za te vrijednosti) kojem se pristupa samo preko sučelja. Program koji koristi ADT će se zvati klijent, a program koji sadrži specifikaciju ovog tipa podataka naziva se implementacija.
To je riječ koja samo čini tip podataka apstraktnim: u slučaju ADT-a, klijentski programi nemaju pristup vrijednostima podataka na bilo koji drugi način, osim operacijama opisanim u sučelju. Prezentacija ovih podataka i funkcije koje implementiraju ove operacije su u implementaciji i potpuno su odvojene interfejsom od klijenta. Kažemo da je interfejs neproziran: klijent ne može da vidi implementaciju kroz interfejs.
U C ++ programima ova razlika je obično malo jasnija, jer je najlakši način za kreiranje sučelja uključiti prezentacija podataka ali navodeći da klijentskim programima nije dozvoljen direktan pristup podacima. Drugim riječima, programeri klijentskog softvera mogu znati prezentacija podataka ali ne mogu ga koristiti ni na koji način.
Kao primjer, razmotrite interfejs tipa podataka za tačke (Program 3.3) iz Odjeljka 3.1 "Elementarne strukture podataka". Ovaj interfejs eksplicitno izjavljuje da su tačke predstavljene kao strukture koje se sastoje od para brojeva s pokretnim zarezom, označenih kao x i y. Ova upotreba tipova podataka je uobičajena u veliki sistemi softver: razvijamo skup konvencija za prezentaciju podataka (kao i definiramo niz povezanih operacija) 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 sa reprezentacijom temeljnih struktura podataka u cijelom sistemu. Koliko god ova strategija bila dobra, ona ima jednu manu: ako treba da se promenite prezentacija podataka, tada će se svi klijentski programi morati promijeniti. Program 3.3 nam opet daje jednostavan primjer: jedan od razloga za razvoj ove vrste podataka je pogodnost klijentskih programa sa tačkama, te očekujemo da klijenti imaju pristup pojedinačnim koordinatama tačaka kada je to potrebno. Ali ne možemo prijeći na drugačiji prikaz podataka (recimo polarne koordinate, ili 3D koordinate, ili čak različite tipove podataka za pojedinačne koordinate) bez promjene svih klijentskih programa.
Nasuprot tome, Program 4.1 sadrži implementaciju apstraktnog tipa podataka koji odgovara tipu podataka Programa 3.3, ali koristeći C++ klasu koja odmah definira i podatke i pridružene operacije. Program 4.2 je klijentski program rad sa ovim tipom podataka. Ova dva programa izvode iste proračune kao programi 3.3 i 3.8. One ilustruju neka od osnovnih svojstava klasa koje ćemo sada pogledati.
Kada u programu napišemo definiciju kao što je int i, kažemo sistemu da rezerviše memorijsku oblast za podatke (inline) tipa int kojoj se može pristupiti putem i. U jeziku C++ postoji termin objekt za takve entitete. Kada napišete definiciju kao što je POINT p u programu, kaže se da kreirate objekat klase POINT, kojem se može pristupiti po imenu p. U našem primjeru, svaki objekt sadrži dvije stavke podataka, nazvane x i y. Kao i kod struktura, na njih se može pozvati imena poput p.y.
Članovi podataka x i y nazivaju se članovima podataka klase. Klasa također može definirati funkcije člana koje implementiraju operacije povezane s tim tipom podataka. Na primjer, klasa definirana u Programu 4.1 ima dvije funkcije člana pod nazivom POINT i distance.
Klijentski programi, kao što je Program 4.2, mogu pozvati funkcije člana povezane s objektom, specificirajući njihova imena na isti način kao i imena podataka pronađenih u nekoj strukturi. Na primjer, izraz p.distance (q) izračunava rastojanje između tačaka p i q (istu udaljenost treba vratiti pozivanjem q.distance (p)). Funkcija POINT (), prva u Programu 4.1, je posebna funkcija člana koja se zove konstruktor: ima isto ime kao klasa i poziva se kad god je potrebno kreirati objekat te klase.
Program 4.1. Implementacija klase POINT (tačka)
Ova klasa definira tip podataka koji se sastoji od skupa vrijednosti koje su "parovi s plutajućim zarezima" (pretpostavlja se da se tumače kao tačke na kartezijanskoj ravni) i dvije funkcije članice definirane za sve instance klase POINT: funkcija POINT (), koji je konstruktor koji inicijalizira koordinate na slučajne vrijednosti od 0 do 1, i funkcija udaljenosti (POINT) koja izračunava udaljenost do druge točke. Prezentacija podataka je privatan i samo mu funkcije mogu pristupiti ili ga modificirati. Same funkcije članova su javne i dostupne svakom klijentu. Kod se može sačuvati, na primjer, u datoteci pod nazivom POINT .cxx.
#include
Program 4.2. Klijentski program za klasu POINT (pronalaženje najbliže tačke)
Ova verzija programa 3.8 je klijent koji koristi POINT ADT definiran u programu 4.3. Nova operacija kreira niz POINT objekata (pozivanjem konstruktora POINT () za inicijalizaciju svakog objekta sa nasumične koordinate). Izraz a [i] .distance (a [j]) poziva na objektu a [i] funkciju člana udaljenosti s argumentom a [j].
#include
Definiranje POINT p u klijentskom programu rezultira dodjeljivanjem memorijskog područja za novi objekt, a zatim (koristeći funkciju POINT ()) dodjeljivanjem svakoj od njegove dvije stavke podataka nasumične vrijednosti u rasponu od 0 do 1.
Ovaj stil programiranja, koji se ponekad naziva objektno orijentirano programiranje, u potpunosti je podržan konstrukcijom klase C ++. Klasa se može smatrati proširenjem koncepta strukture, gdje se ne kombinuju samo podaci, već se definiraju i operacije s tim podacima. Može postojati mnogo različitih objekata koji pripadaju istoj klasi, ali svi su slični po tome što njihovi podaci o članovima mogu uzeti isti skup vrijednosti, a isti skup operacija se može izvesti nad tim podacima o članovima - općenito, oni su instance istog tipa podataka. U objektno orijentiranom programiranju, objekti su dizajnirani da obrađuju svoje podatke o članovima (za razliku od korištenja nezavisnih funkcija za obradu podataka pohranjenih u objektima).
Gledamo gore opisani primjer male klase samo da bismo se upoznali sa osnovnim karakteristikama klasa; stoga je daleko od potpunog. U stvarnom kodu za klasu tačke, imaćemo mnogo više operacija. Na primjer, Program 4.1 čak nema operacije koje vam omogućavaju da saznate vrijednosti x i y koordinata. Kao što ćemo vidjeti, dodavanje ovih i drugih operacija je prilično jednostavan zadatak. U petom dijelu ćemo detaljnije pogledati klase za tačke i druge geometrijske apstrakcije kao što su linije i poligoni.
U C ++ (ali ne i C), strukture također mogu imati funkcije povezane s njima. Ključna razlika između klasa i struktura odnosi se na pristup informacijama, koji karakteriziraju ključne riječi.
Dobar dan, stanovnici Khabrava!
Sljedeći post je sažetak mojih misli o prirodi nastave i ADT-a. Ova razmišljanja su dopunjena zanimljivim citatima iz knjiga gurua razvoja softvera.
Uvod
Počnimo tako što ćemo glatko pristupiti definiciji ADT-a. ADT je prvenstveno tip podataka, što znači sljedeće: prisustvo određenih dostupnih operacija na elementima ove vrste;
kao i podatke na kojima se te operacije izvode (opseg vrijednosti).
Šta znači riječ "apstraktno"? Prije svega, pojam "apstraktnosti" znači fokusiranje na nešto važno, a istovremeno se trebamo odvratiti od nevažnih, trenutno, detalja. Definicija apstraktnosti je dobro obrađena u knjizi Gradyja Boocha. Definicija zvuči ovako:
Apstrakcija je odabir i prenošenje skupa objekata sa zajedničkim svojstvima koja definiraju njihove konceptualne granice i razlikuju ih od svih drugih tipova objekata.
Drugim riječima, apstrakcija nam omogućava da “rasvijetlimo” podatke o objektima koji su nam potrebni i da istovremeno “zasjenimo” one podatke koji nam nisu važni.
Dakle, šta se dešava ako spojite koncepte "tip podataka" i "apstrakcija" zajedno? Dobit ćemo tip podataka koji nam pruža skup operacija koje osiguravaju ponašanje objekata ovog tipa podataka, a ovaj tip podataka će također sakriti podatke s kojima je ovo ponašanje implementirano. Dakle, dolazimo do koncepta ADT-a:
ADT je tip podataka koji skriva svoju internu implementaciju od klijenata.
Iznenađujuće, korišćenjem apstrakcije, ADT nam omogućava da ne razmišljamo o detaljima implementacije na niskom nivou, već da radimo sa entitetom visokog nivoa stvarnog sveta (Steve McConnell).
Vjerujem da kada razvijate ADT, prvo morate definirati sučelje, jer sučelje ne bi trebalo ovisiti o internom prikazu podataka u ADT-u. Nakon definiranja operacija koje čine sučelje, morate se fokusirati na podatke koji će implementirati specificirano ponašanje ADT-a. Kao rezultat toga, dobit ćemo neku vrstu strukture podataka - mehanizam koji vam omogućava pohranjivanje i obradu podataka. Istovremeno, ljepota ADT-a je da ako želimo promijeniti internu reprezentaciju podataka, onda ne moramo lutati kroz cijeli program i mijenjati svaki red koda koji ovisi o podacima koje želimo promijeniti. ADT inkapsulira ove podatke, što vam omogućava da promijenite ponašanje objekata ovog tipa, a ne cijelog programa.
Prednosti ATD-a
Upotreba ADT-a ima mnogo prednosti (sve opisane prednosti možete pronaći u knjizi Stevea McConnell-a "Savršen kod"):
- Enkapsulacija detalja implementacije.
To znači da kada obuhvatimo detalje o tome kako ADT radi, pružamo klijentu sučelje preko kojeg može komunicirati sa ADT-om. Promjenom detalja implementacije, percepcija korisnika ADT-a se neće promijeniti.
- Smanjena složenost.
Apstrahujući od detalja implementacije, fokusiramo se na interfejs, što je ono što ADT može da uradi, a ne kako se radi. Štaviše, ADT nam omogućava da radimo sa suštinom stvarnog svijeta.
- Ograničavanje obima upotrebe podataka.
Koristeći ADT, možemo biti sigurni da podaci koji predstavljaju internu strukturu ADT-a neće ovisiti o drugim dijelovima koda. Istovremeno se ostvaruje „nezavisnost“ ADT-a.
- Visok informativni sadržaj interfejsa.
ADT vam omogućava da predstavite čitav interfejs u smislu entiteta domena, što, vidite, povećava čitljivost i informativni sadržaj interfejsa.
Steve McConnell preporučuje predstavljanje tipova podataka niskog nivoa kao što su stog ili lista kao ADT. Zapitajte se koja je lista. Ako predstavlja listu zaposlenih u banci, onda smatrajte ATD spiskom zaposlenih u banci.
Dakle, shvatili smo šta je ADT i naveli prednosti njegove upotrebe. Sada je vrijedno napomenuti da kada razvijate klase u OOP-u, trebate prvenstveno misliti na ADT. Istovremeno, kako je rekao Steve McConnell, ne programirate na jeziku, već uz pomoć jezika. To jest, vi ćete programirati izvan jezika, ne ograničavajući se na misli u smislu nizova ili jednostavnih tipova podataka. Umjesto toga, razmišljat ćete na visokom nivou apstrakcije (na primjer, u smislu proračunskih tabela ili lista zaposlenih). Klasa nije ništa drugo do dodatak i način da se implementira ADT koncept. Možemo čak predstaviti klasu kao formulu:
Klasa = ADT + nasljeđivanje + polimorfizam.
Dakle, zašto bi se razmišljalo o ADT-ima prilikom dizajniranja klasa. Jer, prvo, moramo odlučiti koje će operacije činiti interfejs buduće klase, koje podatke sakriti, a kojima omogućiti javni pristup. Moramo razmisliti o tome da interfejs učinimo visoko informativnim, lakim za optimizaciju i validaciju koda i kako možemo pružiti ispravnu apstrakciju tako da možemo razmišljati o entitetima iz stvarnog svijeta, a ne o detaljima implementacije niskog nivoa. Vjerujem da bi nakon definicije ADT-a trebalo razmišljati o pitanjima nasljeđivanja i polimorfizma.
Vrijedi napomenuti da je koncept ADT-a našao široku primjenu u OOP-u, jer upravo ovaj koncept nadopunjuje OOP i omogućava vam da smanjite složenost programa u svijetu softverskih zahtjeva koji se brzo mijenja.
Ovaj članak sam napisao kako bih skrenuo pažnju programera na ADT u cilju poboljšanja kvaliteta rada i razvoja softvera.
Korišteni izvori:
Steve McConnell - Code Perfect;
Robert Sedgwick - "Algoritmi u Javi".
