1.2. Llojet abstrakte të të dhënave
Shumica e koncepteve të prezantuara në seksionin e mëparshëm zakonisht mësohen në një kurs programimi hyrës dhe duhet të jenë të njohura për ju. Vetëm llojet abstrakte të të dhënave mund të jenë të reja, prandaj le të diskutojmë fillimisht rolin e tyre në procesin e zhvillimit të softuerit. Së pari, le të krahasojmë një lloj të dhënash abstrakte me konceptin e njohur të një procedure.
Një procedurë, një mjet programimi thelbësor, mund të mendohet si një koncept i përgjithësuar i një operatori. Në ndryshim nga operatorët e integruar të një gjuhe programimi, të cilët janë të kufizuar në aftësitë e tyre (mbledhje, shumëzim, etj.), duke përdorur procedura, një programues mund të krijojë operatorët e vet dhe t'i zbatoni ato në operandë të llojeve të ndryshme, jo vetëm atyre bazë. Një shembull i një operacioni të tillë procedurë është nënprogrami standard i shumëzimit të matricës.
Një avantazh tjetër i procedurave (përveç aftësisë për të krijuar deklarata të reja) është se ato mund të përdoren kapsulimi pjesë të algoritmit duke vendosur në një seksion të veçantë të programit të gjithë operatorët përgjegjës për një aspekt të caktuar të funksionimit të programit. Shembull i kapsulimit: Përdorimi i një procedure të vetme për të lexuar hyrjen e çdo lloji dhe për ta vërtetuar atë. Avantazhi i kapsulimit është se ne e dimë se cilat deklarata të kapsuluara duhet të ndryshohen në rast se ka probleme në funksionimin e programit. Për shembull, nëse është e nevojshme të organizojmë një kontroll të të dhënave hyrëse për vlera pozitive, duhet të ndryshojmë vetëm disa rreshta kodi dhe ne e dimë saktësisht se ku ndodhen këto rreshta.
Përkufizimi lloji abstrakt të dhëna
Ne përcaktojmë lloji abstrakt i të dhënave(ATD) si një model matematikor me një grup operatorësh të përcaktuar brenda këtij modeli. Një shembull i thjeshtë i një ADT do të ishin grupet e numrave të plotë me operatorë bashkimi, kryqëzimi dhe ndryshimi i grupeve. Në modelin ADT, operatorët mund të kenë si operandë jo vetëm të dhëna të përcaktuara nga ADT, por edhe të dhëna të llojeve të tjera: tipe standarde të gjuhës së programimit ose ato të përcaktuara në ADT të tjera. Rezultati i një veprimi operatori mund të jetë gjithashtu i një lloji të ndryshëm nga ato të përcaktuara në modelin e dhënë ADT. Por ne supozojmë se të paktën një operand ose rezultat i çdo operatori ka një lloj të dhënash të përcaktuar në modelin ADT në fjalë.
Dy karakteristikat procedurat - përgjithësimi dhe kapsulimi - të cilat u diskutuan më lart, karakterizojnë në mënyrë të përsosur llojet e të dhënave abstrakte. Një ADT mund të konsiderohet si një përgjithësim i llojeve të thjeshta të të dhënave (numrat e plotë, numrat realë, etj.), ashtu si një procedurë është një përgjithësim i operatorë të thjeshtë(+, - etj.). Një ADT përmbledh llojet e të dhënave në kuptimin që përkufizimi i tipit dhe të gjithë operatorët që mund të kryhen në të dhënat e atij lloji vendosen në një seksion të programit. Nëse është e nevojshme të ndryshojmë zbatimin e një ADT, ne e dimë se ku të gjejmë dhe çfarë të ndryshojmë në një pjesë të vogël të programit dhe mund të jemi të sigurt se kjo nuk do të çojë në gabime askund në program kur punojmë me këto të dhëna. lloji. Për më tepër, jashtë seksionit për përcaktimin e operatorëve ADT, ne mund t'i konsiderojmë llojet ADT si lloje kryesore, pasi deklaratat e tipit nuk lidhen zyrtarisht me zbatimin e tyre. Por në këtë rast, mund të shfaqen komplikime, pasi disa deklarata mund të inicohen për më shumë se një ADT, dhe referencat ndaj këtyre deklaratave duhet të jenë në seksione të disa ADT-ve.
Për të ilustruar idetë bazë që çojnë në krijimin e një ADT, konsideroni procedurën lakmitare nga seksioni i mëparshëm (lista 1.3), e cila përdor operatorë të thjeshtë për të dhënat e llojit abstrakt të të dhënave LIST (lista e numrave të plotë). Këta operatorë duhet të kryejnë veprimet e mëposhtme në variablin newclr të tipit LIST.
1. Bëjeni listën bosh.
2. Zgjidhni elementin e parë të listës dhe, nëse lista është bosh, kthejeni vlerën i pavlefshëm.
3. Zgjidhni elementin tjetër të listës dhe ktheni vlerën i pavlefshëm, nëse elementi tjetër nr.
4. Futni një numër të plotë në listë.
Është e mundur të përdoren struktura të ndryshme të dhënash me të cilat mund të kryeni në mënyrë efektive veprimet e përshkruara. (Strukturat e të dhënave do të diskutojmë në detaje në temën 2.) Nëse në Listimin 1.3 zëvendësojmë operatorët përkatës me shprehje
MAKENULL(newcJr);
w:= FIRST(newcJr);
w:= NEXT(newcfr);
INSERT(v, newclr);
atëherë një nga aspektet (dhe avantazhet) kryesore të llojeve abstrakte të të dhënave do të jetë i qartë. Ju mund të zbatoni një lloj të dhënash në çdo mënyrë, dhe programet që përdorin objekte të këtij lloji nuk varen nga mënyra se si zbatohet lloji - procedurat që zbatojnë operatorët për këtë lloj të dhënash janë përgjegjëse për këtë.
Kthehu tek lloji abstrakt Të dhënat GRAPH(Grafiku). Objektet e këtij lloji kërkojnë operatorë që kryejnë veprimet e mëposhtme.
1. Zgjidhni kulmin e parë të palyer.
2. Kontrolloni nëse ka një skaj midis dy kulmeve.
3. Shënoni pjesën e sipërme me një ngjyrë.
4. Zgjidhni kulmin tjetër të palyer.
Natyrisht, operatorë të tjerë, të tillë si futja e kulmeve dhe skajeve në një grafik ose shënimi i të gjitha kulmeve të grafikut si të paplotësuara, mbeten jashtë objektit të procedurës së babëzitur. Struktura të ndryshme të të dhënave që mbështesin këtë lloj të dhënash do të trajtohen në temat 6 dhe 7.
Duhet theksuar se numri i operatorëve të aplikuar për objektet e këtij modeli matematikor nuk është i kufizuar. Çdo grup deklaratash përcakton një ADT të veçantë. Këtu janë shembuj të operatorëve që mund të përcaktohen për llojin abstrakt të të dhënave SET (Set).
1. MAKENULL(A), Kjo procedurë e bën grupin A një grup bosh.
2. BASHKIM (A, B, C). Kjo procedurë merr dy argumente "hyrëse", grupet A dhe B, dhe cakton bashkimin e këtyre grupeve me argumentin "output" të saj, grupin C.
3. SIZE (A). Ky funksion ka një argument të vendosur A dhe kthen një objekt të tipit të plotë të barabartë me numrin e elementeve të grupit A. Termi zbatimi ADT nënkupton sa më poshtë: përkthimi në gjuhën e programimit deklarata të deklaratave që përcaktojnë variabla të këtij lloji abstrakt të të dhënave, plus procedurat për çdo deklaratë të kryer në objektet ADT. Zbatimi varet nga strukturat e të dhënave, që përfaqëson ATD. Çdo strukturë e të dhënave është ndërtuar mbi bazën e llojeve bazë të të dhënave të gjuhës së programimit të përdorur, duke përdorur mjetet e strukturimit të të dhënave të disponueshme në këtë gjuhë. Strukturat e grupeve dhe rekordeve janë dy mjete të rëndësishme për strukturimin e të dhënave të mundshme në Pascal. Për shembull, një nga zbatimet e mundshme ndryshorja S e tipit SET mund të jetë një grup që përmban elementë të grupit S.
Një nga arsyet kryesore për përcaktimin e dy ADT-ve të ndryshme brenda të njëjtit model është se duhet të kryhen veprime të ndryshme në objektet e këtyre ADT-ve, d.m.th. përcaktojnë operatorët tipe te ndryshme. Kjo përmbledhje mbulon vetëm disa nga kryesoret modele matematikore, si teoria e grupeve dhe teoria e grafikëve, por me zbatime të ndryshme, ADT të caktuara do të ndërtohen në bazë të këtyre modeleve. komplete të ndryshme operatorët.
Në mënyrë ideale, është e dëshirueshme të shkruhen programe në një gjuhë, llojet bazë të të dhënave dhe operatorët e së cilës janë të mjaftueshëm për të zbatuar një ADT. Nga ky këndvështrim Gjuha e paskalit jo një gjuhë shumë e përshtatshme për zbatimin e ADT-ve të ndryshme, por, nga ana tjetër, është e vështirë të gjesh një gjuhë tjetër programimi në të cilën do të ishte e mundur të deklarohej një ADT në një mënyrë kaq të drejtpërdrejtë. Informacion shtese për gjuhë të tilla programimi, shihni shënimet bibliografike në fund të temës.
Një lloj i të dhënave përshkruan një grup objektesh me veti të ngjashme. Të gjitha gjuhët tradicionale të programimit përdorin një grup të llojeve bazë të të dhënave (reale, integer, string, karakter). Llojet bazë të të dhënave i nënshtrohen një grupi të paracaktuar operacionesh. Për shembull, numri i plotë i llojit të të dhënave bazë ju lejon të kryeni veprime të tilla si mbledhje, zbritje, shumëzim dhe pjesëtim.
Gjuhët tradicionale të programimit përfshijnë konstruktorët e tipit, më i zakonshmi prej të cilëve është konstruktori i rekordeve. Për shembull, për një regjistrim të tipit CUSTOMER, mund të përcaktoni fushat e të dhënave. Hyrja e KLIENTIT do të jetë lloj i ri struktura e të dhënave, e cila do të ruajë informacione rreth klientit, ju mund të aksesoni drejtpërdrejt këtë strukturë të të dhënave duke iu referuar emrave të fushave. Mund të kryeni operacione të tilla si SHKRUAJ, LEXO, FSHIJE, PËRDITËSIM në një regjistrim. Ju nuk mund të përcaktoni operacione të reja për llojet bazë të të dhënave.
Ashtu si llojet bazë të të dhënave, llojet abstrakte të të dhënave (ATD) përshkruajnë shumë objekte të ngjashme. Ka dallime midis ATD dhe tip tradicional të dhënat:
· Operacionet nën ATD përcaktohen nga përdoruesi;
· ATD-të nuk lejojnë akses të drejtpërdrejtë në paraqitjen e brendshme të të dhënave dhe zbatimin e metodave.
Në disa sisteme OO (për shembull, Smalltalk), llojet bazë të të dhënave zbatohen si ato abstrakte.
Për të krijuar një lloj të dhënash abstrakte, duhet të siguroni:
emri i llojit;
Paraqitja e të dhënave ose variablave të shembullit të një objekti në pronësi të ATD; çdo variabël shembulli ka një lloj të dhënash, i cili mund të jetë ose lloji i bazës, ose një ATD tjetër;
· Operacionet dhe kufizimet ATD zbatohen duke përdorur metoda.
Përkufizimi ATD rindërton përkufizimin e klasës. Në disa sisteme OO, fjala kyçe tip përdoret për të dalluar klasat dhe llojet kur i referohet strukturave të të dhënave dhe metodave të një klase, dhe kur i referohet një grupi instancash objektesh, fjalë kyçe klasës. Lloji (lloji) është një koncept më statik, dhe klasa lidhet kryesisht me kohën e ekzekutimit. Dallimi midis një klase OO dhe një lloji OO mund të ilustrohet me një shembull. Supozoni se ekziston një shabllon për një konstruktor. Shablloni shoqërohet me një përshkrim të strukturës së tij, si dhe me udhëzime për përdorimin e tij. Ky shabllon është përkufizimi i llojit. Një grup produktesh reale të bëra duke përdorur një shabllon, secila prej të cilave ka një numër unik (ose OID), përbën një klasë (klasë).
ATD, së bashku me trashëgiminë, ju lejon të krijoni objekte komplekse. Një objekt kompleks formohet duke kombinuar objekte të tjera që janë në marrëdhënie komplekse me njëri-tjetrin. Shembull objekt kompleks mund të gjenden në sistemet e sigurisë që përdorin tipe te ndryshme të dhënat:
1. Të dhëna standarde (tabelore) për punonjësin (emri i plotë, nr. Tab, etj.);
2. bitmap për ruajtjen e fotografive të punonjësve;
Të jesh në gjendje të punosh me një mjedis të tillë kompleks të të dhënave me lehtësi relative rrit vlerën e sistemeve OO treg modern bazat e të dhënave.
Një lloj i të dhënave abstrakte zakonisht quhet një lloj i të dhënave që nuk është i disponueshëm në mënyrë eksplicite në një gjuhë programimi; në këtë kuptim, ky koncept është relativ - një lloj i të dhënave që mungon në një gjuhë programimi mund të jetë i pranishëm në një tjetër.
Lloji abstrakt i të dhënave (ATD) përcaktohet pavarësisht se si zbatohet:
shumë vlerat e mundshme të këtij lloji
dhe një grup operacionesh mbi vlerat e këtij lloji.
Përdorimi i një ADT mund të kufizohet në fazën e zhvillimit software, por për përdorimin e tij të qartë në program, është e nevojshme që zbatimi i tij të bazohet në llojet e të dhënave ekzistuese (dhe të implementuara më parë) në gjuhën e programimit:
një mënyrë për të paraqitur vlera të këtij lloji,
dhe zbatimin e operacioneve mbi vlerat e atij lloji.
ADT nuk është i paracaktuar në gjuhën e programimit, dhe aq më tepër - operacionet e ndërtimit të llojeve të tilla, të paracaktuara në gjuhë, zhvendosin pyetjen se si të përfaqësohen vlerat e këtij lloji dhe të zbatohen operacione me vlera të këtij lloji. te zhvilluesi-programues. Prandaj, për lloje të tilla të dhënash, çështja e zgjedhjes së përkufizimeve dhe metodave për zbatimin e operacioneve të formularit konstruktor (vlerat dhe depozitat e të dhënave) të këtij lloji, përzgjedhës Dhe modifikues komponentët (vlerat dhe dyqanet e të dhënave) të këtij lloji i caktohen zhvilluesit-programuesit.
Në konceptin e ATD, konceptet ndërfaqe , të ekspozuara ndaj përdoruesit, dhe zbatimi fshehur prej tij. Roli i veçantë i këtyre koncepteve në konceptin e ADT lidhet me propozimin themelor se koncepti i ADT është i pavarur nga metoda e zbatimit të tij.
"Gjuhët e programimit praktik" moderne zakonisht përdorin operacionin e ndërtimit të tipit të paracaktuar për të ndërtuar një ADT. klasës , i cili i jep zhvilluesit-programuesit jo vetëm mjetet e grupimit të të dhënave dhe operacioneve (me këto të dhëna) në një tërësi të vetme, por edhe mjetet e kapsulimit, trashëgimisë dhe polimorfizmit për të kontrolluar se si ndërtohen dhe aksesohen të dhëna të tilla. Vini re se klasa përshkruan një zbatim të mundshëm të ADT, hartëzimi i klasës me ADT shprehet me funksionin e abstraksionit, por marrëdhënia e kundërt zakonisht nuk është funksionale, mund të ketë disa implementime të së njëjtës ADT.
Në kërkimin mbi llojet abstrakte të të dhënave, roli i rëndësishëm i konceptit " parametrizimi i llojit ". Në të vërtetë, për shembull, "Stack" ADT nuk varet nga lloji i elementeve të pirgut, por është e pamundur të zbatohet kjo ADT duke treguar "elemente të një lloji të njëjtë". Mjetet përkatëse për ndërtimin e llojeve të të dhënave të parametrizuara u përfshinë në gjuhën e programimit Ada që nga fillimi, dhe në "gjuhët praktike të programimit" moderne, cilat mjete janë shfaqur vetëm që nga zhvillimi i bibliotekës STL. Sot, koncepti i "programimit të përgjithësuar" zë një pozicion të rëndësishëm në programimin praktik për shkak të përfshirjes së tij në "gjuhët e programimit praktik". mjetet e ndërtimit për llojet e të dhënave të parametrizuara (shabllonet, shabllon , gjenerike) .
Të gjitha sa më sipër do të thotë se nga pikëpamja metodologjike dhe teorike, nevojitet një përkufizim më i detajuar i saktë i konceptit të "llopit abstrakt të të dhënave". Në teori, koncepti i "llopit abstrakt të të dhënave" zakonisht përkufizohet si sistem algjebrik me shumë renditje (me shumë baza). , në të cilën, përveç grupit të vlerave të mundshme (bartës) dhe grupit të operacioneve mbi vlera të tilla, theksohen konceptet e mëposhtme:
Renditja dhe nënshkrimi - këto koncepte bëjnë të mundur klasifikimin e elementeve të transportuesit dhe operacioneve me ta sipas llojeve të tyre (për operacionet - sipas llojeve të argumenteve të tyre dhe vlerës së kthimit).
Kallëzuesit janë marrëdhënie mbi elementet bartëse. Kjo ju lejon të përcaktoni gamën e vlerave të mundshme duke vendosur kufizime (kërkesa). vlerat e lejuara, si dhe në interpretimin natyror për të punuar me arbitrare shprehjet logjike, pa i detyruar ato të interpretohen si funksione anëtarësimi për grupe ose si operacione me shumë vlera.
Mbi këtë bazë, mund të merren në konsideratë llojet abstrakte të të dhënave nga një këndvështrim i vetëm logjik-algjebrik holistik, duke përfshirë pyetjet rreth konstruktorëve (të llojeve dhe vlerave), përzgjedhësve dhe modifikuesve të vetive për objekte të këtij lloji.
Konceptet e "strukturës së të dhënave" dhe "lloji abstrakt i të dhënave" janë disi afër. Ju sigurisht mund të konsideroni se këto koncepte janë vetëm dy pikëpamje për të njëjtën gjë. Mënyra se si përfaqësohen vlerat ADT bazohet gjithmonë në disa strukturë të dhënash, më pak ose më komplekse, dhe zbatimi i operacioneve mbi vlera të tilla varet natyrshëm nga kjo strukturë e zgjedhur e të dhënave. Nga ana tjetër, ne gjithmonë mund të formatojmë strukturën e të dhënave që na intereson si ADT nëse vërtet dëshirojmë.
Por megjithatë, ne do të bëjmë dallimin midis këtyre dy koncepteve, duke pasur parasysh:
Lloji i të dhënave abstrakte - nënkupton një nivel të caktuar abstraksioni për të rregulluar llojin e të dhënave të aplikacionit (të orientuar nga domeni), pavarësisht se si zbatohet, dhe është e mundur të përfshihet ky lloj i të dhënave në bibliotekën e aplikacionit, mirë, të paktën për një zhvillim specifik i një specifike sistemi softuerik. Një ADT mund të ketë disa implementime alternative bazuar në struktura të ndryshme të dhënash.
Struktura e të dhënave është më tepër një lloj skeme organizimi të të dhënave dhe menaxhimin e tyre, që nënkupton konkretizimin e duhur kur përdoret në situata specifike në zgjidhjen e problemeve specifike.
Para së gjithash, sistemet algjebrike themelore matematikore natyrisht i përkasin llojeve abstrakte të të dhënave - sekuencave, grupeve, marrëdhënieve dhe hartave (marrëdhëniet funksionale, funksionet). Por në programim plani i parë nuk është kërkimi vetitë e përbashkëta këto koncepte matematikore dhe mundësinë e përdorimit të tyre në zhvillimin e modeleve për zgjidhjen e problemeve në fushën lëndore, algoritme për zgjidhjen e këtyre problemeve dhe zbatimin efektiv të algoritmeve të zhvilluara. Prandaj, në programimin në formën e një ADT, nga njëra anë, versionet e kufizuara të këtyre sistemeve bazë algjebrike zakonisht formalizohen, dhe nga ana tjetër, ato zgjerohen nga grupe të specializuara operacionesh që janë me interes pragmatik nga pikëpamja e pamje e zonës së aplikimit.
Zhvillimi i modeleve abstrakte për të dhënat dhe mënyrat e përpunimit të këtyre të dhënave është komponent thelbësor në procesin e zgjidhjes së problemeve duke përdorur një kompjuter. Ne shohim shembuj të kësaj si në një nivel të ulët në programimin e përditshëm (për shembull, kur përdoren vargje dhe lista të lidhura, të diskutuara në), dhe në një nivel të lartë kur zgjidhim detyrat e aplikuara(si kur zgjidhni problemin e lidhjes duke përdorur pyllin e kërkimit të bashkimit në "Hyrje"). Ky leksion diskuton llojet abstrakte të të dhënave (lloji abstrakt i të dhënave, më tej ADT), të cilat ju lejojnë të krijoni programe duke përdorur abstraksione të nivelit të lartë. Llojet abstrakte të të dhënave ju lejojnë të ndani transformimet abstrakte (konceptuale) që programet kryejnë në të dhëna nga çdo paraqitje e veçantë e një strukture të dhënash dhe çdo zbatim i veçantë i një algoritmi.
Gjithçka sistemet kompjuterike bazuar në nivelet e abstraksionit: disa veti fizike të silikonit dhe materialeve të tjera lejojnë adoptimin e një modeli abstrakt të bitit, i cili mund të marrë vlerat binare 0-1; më pas, një model abstrakt i makinës është ndërtuar mbi vetitë dinamike të vlerave të një grupi të caktuar bitësh; më tej, bazuar në parimin e funksionimit të makinës nën kontrollin e programit në gjuha e makinerisë ndërtohet një model abstrakt i gjuhës programuese; dhe, në fund, ndërtohet një koncept abstrakt i një algoritmi, i cili zbatohet si një program C++. Llojet abstrakte të të dhënave bëjnë të mundur vazhdimin e mëtejshëm të këtij procesi dhe zhvillimin e mekanizmave abstraktë për detyra të caktuara llogaritëse në një nivel më të lartë sesa ofrohet nga sistemi C ++, zhvillojnë mekanizma abstraktë të fokusuar në aplikacione specifike dhe i përshtatshëm për zgjidhjen e problemeve në fusha të shumta aplikimi, si dhe për të krijuar mekanizma abstraktë për më shumë nivel të lartë që përdorin këto konstruksione bazë. Llojet abstrakte të të dhënave na ofrojnë një grup pafundësisht të zgjerueshëm mjetet për të zgjidhur gjithnjë e më shumë probleme të reja.
Nga njëra anë, përdorimi i konstrukteve abstrakte e çliron njeriun nga shqetësimet për zbatimin e detajuar të tyre; nga ana tjetër, kur performancës programi është i rëndësishëm, ju duhet të dini kostot e kryerjes së operacioneve bazë. Ne përdorim shumë abstraksione bazë të integruara hardware kompjuter dhe shërben si bazë për instruksionet e makinës; të zbatojë abstraksione të tjera në softuer; dhe përdorni abstraksione shtesë të ofruara nga softueri i sistemit të shkruar më parë. Konstruktet abstrakte të nivelit të lartë shpesh bazohen në më shumë dizajne të thjeshta. Në të gjitha nivelet, zbatohet i njëjti parim bazë: ju duhet të gjeni më shumë operacione të rëndësishme në programe dhe shumica karakteristika të rëndësishme të dhëna, dhe më pas të përcaktohen saktësisht të dyja në nivel abstrakt dhe të zhvillohen mekanizma konkretë efektivë për zbatimin e tyre. Në këtë leksion do të shohim shumë shembuj të zbatimit të këtij parimi.
Zhvillimi i një niveli të ri abstraksioni do të kërkojë (1) përcaktimin e objekteve abstrakte që do të manipulohen dhe operacionet që do të kryhen mbi to; (2) përfaqësojnë të dhënat në disa strukturë të dhënash dhe zbatojnë operacionet; (3) dhe (më e rëndësishmja) për të siguruar që këto objekte janë të përshtatshme për t'u përdorur për zgjidhjen e problemeve të aplikuara. Këto pika vlejnë edhe për lloje të thjeshta të dhënat, në mënyrë që mekanizmat bazë për mbështetjen e llojeve të të dhënave, të cilat u diskutuan në "Strukturat elementare të të dhënave", mund të përshtaten për qëllimet tona. Megjithatë, gjuha C++ ofron zgjerim i rëndësishëm mekanizmi i strukturave, i quajtur një klasë ( class ). Klasat janë jashtëzakonisht të dobishme në krijimin e shtresave të abstraksionit dhe për këtë arsye trajtohen si mjeti kryesor i përdorur për këtë qëllim në pjesën e mbetur të librit.
Përkufizimi 4.1. Një lloj i të dhënave abstrakte (ATD) është një lloj i të dhënave (një grup vlerash dhe një grup operacionesh mbi ato vlera) që aksesohet vetëm përmes një ndërfaqeje. Programi që përdor ADT do të quhet klient, dhe programi që përmban specifikimet e këtij lloji të të dhënave do të quhet implementim.
Është fjala që e bën vetëm llojin e të dhënave abstrakte: në rastin e një ADT, programet e klientit nuk kanë akses në vlerat e të dhënave në asnjë mënyrë tjetër përveç operacioneve të përshkruara në ndërfaqe. Paraqitja e këtyre të dhënave dhe funksionet që zbatojnë këto operacione janë në zbatim dhe janë plotësisht të ndara nga një ndërfaqe nga klienti. Themi se ndërfaqja është e errët: klienti nuk mund ta shohë zbatimin përmes ndërfaqes.
Në programet C++, ky dallim zakonisht bëhet pak më i qartë, pasi është më e lehtë të krijosh një ndërfaqe duke përfshirë prezantimi i të dhënave, por duke specifikuar se programet e klientëve nuk lejohen të kenë akses të drejtpërdrejtë në të dhëna. Me fjalë të tjera, zhvilluesit e klientëve mund ta dinë prezantimi i të dhënave, por nuk mund ta përdor në asnjë mënyrë.
Si shembull, merrni parasysh ndërfaqen e tipit të të dhënave për pikat (Programi 3.3) nga seksioni 3.1 "Strukturat elementare të të dhënave". Kjo ndërfaqe deklaron në mënyrë eksplicite se pikat përfaqësohen si struktura që përbëhen nga një çift numrash me pikë lundruese, të shënuar me x dhe y. Ky përdorim i llojeve të të dhënave është i zakonshëm në sisteme të mëdha softuer: ne zhvillojmë një grup konventash për përfaqësimin e të dhënave (si dhe përcaktojmë një grup operacionesh të lidhura) dhe i bëjmë këto rregulla të disponueshme përmes një ndërfaqeje në mënyrë që ato të mund të përdoren nga programet e klientit të përfshirë në sistem i madh. Lloji i të dhënave siguron që të gjitha pjesët e sistemit të jenë në përputhje me paraqitjen e strukturave themelore të të dhënave në të gjithë sistemin. Sado e mirë të jetë kjo strategji, ajo ka një pengesë: nëse është e nevojshme të ndryshohet prezantimi i të dhënave, do t'ju duhet të ndryshoni të gjitha programet e klientit. Programi 3.3 përsëri na jep një shembull të thjeshtë: një nga arsyet për zhvillimin e këtij lloji të të dhënave është komoditeti i programeve të klientëve që punojnë me pikat dhe ne presim që klientët të kenë akses në koordinatat individuale të një pike nëse është e nevojshme. Por ne nuk mund të kalojmë në një paraqitje të ndryshme të të dhënave (të themi, koordinatat polare, ose koordinatat 3D, apo edhe lloje të tjera të dhënash për koordinatat individuale) pa ndryshuar të gjitha programet e klientit.
Në të kundërt, Programi 4.1 përmban një implementim të një lloji abstrakt të të dhënave që korrespondon me llojin e të dhënave në Programin 3.3, por duke përdorur një klasë të gjuhës C++ që përcakton të dhënat dhe operacionet e lidhura me të në të njëjtën kohë. Programi 4.2 është program klienti A që funksionon me këtë lloj të dhënash. Këto dy programe kryejnë të njëjtat llogaritje si programet 3.3 dhe 3.8. Ato ilustrojnë një sërë karakteristikash kryesore të klasave që do t'i shqyrtojmë tani.
Kur shkruajmë një përkufizim si int i në një program, i themi sistemit të rezervojë një zonë memorie për të dhënat (në bord) shkruani int, e cila mund të arrihet me emrin i. Gjuha C++ ka termin objekt për entitete të tilla. Kur një përkufizim i tillë si POINT p shkruhet në një program, thuhet se krijohet një objekt i klasës POINT, i cili mund të referohet me emrin p. Në shembullin tonë, çdo objekt përmban dy elementë të dhënash, të quajtur x dhe y. Ashtu si me strukturat, ato mund të referohen me emra si p.y.
Anëtarët e të dhënave x dhe y quhen anëtarë të të dhënave të klasës. Klasa gjithashtu mund të përcaktojë funksionet anëtare që zbatojnë operacionet e lidhura me këtë lloj të dhënash. Për shembull, klasa e përcaktuar në Programin 4.1 ka dy funksione anëtare të quajtura POINT dhe distancë.
Programet e klientëve, të tillë si programi 4.2, mund të thërrasin funksione anëtare të lidhura me një objekt duke specifikuar emrat e tyre në të njëjtën mënyrë si emrat e të dhënave të përfshira në një strukturë strukture. Për shembull, shprehja p.distance(q) llogarit distancën ndërmjet pikave p dhe q (e njëjta distancë duhet të kthehet duke thirrur q.distance(p) ). Funksioni POINT(), funksioni i parë në Programin 4.1, është një funksion i veçantë anëtar i quajtur konstruktor: ai ka të njëjtin emër si një klasë dhe thirret kur një objekt i asaj klase duhet të krijohet.
Programi 4.1. Zbatimi i klasës POINT (pikë)
Kjo klasë përcakton një lloj të dhënash që përbëhet nga një grup vlerash që janë "çifte numrash me pikë lundruese" (duke supozuar se ato interpretohen si pika në një plan kartezian), si dhe dy funksione anëtare të përcaktuara për të gjitha rastet e POINT. klasa: funksioni POINT() , i cili është një konstruktor që inicializon koordinatat me vlera të rastësishme nga 0 në 1, dhe një funksion distance (POINT) që llogarit distancën në një pikë tjetër. Përfaqësimi i të dhënaveështë private dhe vetëm funksionet e anëtarëve mund ta aksesojnë ose modifikojnë atë. Vetë funksionet e anëtarëve janë publike (publike) dhe të disponueshme për çdo klient. Kodi mund të ruhet, për shembull, në një skedar të quajtur POINT .cxx.
#përfshi
Programi 4.2. Programi i klientit për klasën POINT (gjetja e pikës më të afërt)
Ky version i programit 3.8 është një klient që përdor POINT ADT të përcaktuar në programin 4.3. Operacioni i ri krijon një grup objektesh POINT (duke thirrur konstruktorin POINT() për të inicializuar çdo objekt me vlera të rastësishme të koordinatave). Shprehja a[i].distanca(a[j]) e quan funksionin e anëtarit distancë në objektin a[i] me argumentin a[j] .
#përfshi
Përcaktimi i POINT p në programin e klientit rezulton në ndarjen e një zone memorie për një objekt të ri dhe më pas (duke përdorur funksionin POINT()) duke i caktuar secilit prej dy elementeve të të dhënave të tij një vlerë të rastësishme në intervalin nga 0 në 1.
Ky stil programimi, i quajtur ndonjëherë programim i orientuar nga objekti, mbështetet plotësisht nga konstrukti i klasës C++. Një klasë mund të mendohet si një zgjerim i konceptit të strukturës, ku jo vetëm kombinohen të dhënat, por përcaktohen operacionet mbi ato të dhëna. Mund të ketë shumë objekte të ndryshme që i përkasin të njëjtës klasë, por të gjithë janë të ngjashëm në atë që anëtarët e tyre të të dhënave mund të marrin të njëjtin grup vlerash dhe i njëjti grup operacionesh mund të kryhet në këta anëtarë të të dhënave - në përgjithësi, ato janë raste të të njëjtit lloj të dhënash. Në programimin e orientuar nga objekti, objektet janë krijuar për të përpunuar anëtarët e tyre të të dhënave (në krahasim me përdorimin e funksioneve të pavarura për të përpunuar të dhënat e ruajtura në objekte).
Ne po shikojmë shembullin e një klase të vogël të përshkruar më sipër vetëm për t'u njohur me veçoritë themelore të klasave; kështu që është larg nga kompletimi. Në kodin real për klasën e pikëve, do të kemi shumë operacione të tjera. Për shembull, në programin 4.1, nuk ka as operacione që ju lejojnë të zbuloni vlerat e koordinatave x dhe y. Siç do të shohim, shtimi i këtyre dhe operacioneve të tjera është një detyrë mjaft e thjeshtë. Në Pjesën 5, ne do t'i hedhim një vështrim më të afërt klasave për pikat dhe abstraksione të tjera gjeometrike si vijat dhe poligonet.
Në C++ (por jo në C), strukturat gjithashtu mund të kenë funksione të lidhura me to. Dallimi kryesor midis klasave dhe strukturave ka të bëjë me aksesin në informacion, i cili karakterizohet nga fjalë kyçe.
Mirëdita, habravchane!
Postimi i mëposhtëm është një përmbledhje e mendimeve të mia mbi natyrën e klasave dhe ADT-ve. Këto reflektime plotësohen me citate interesante nga librat e guruve të zhvillimit të softuerit.
Prezantimi
Le të fillojmë me faktin se do t'i qasemi pa probleme përkufizimit të ATD. Një ADT është kryesisht një lloj i të dhënave, që do të thotë si më poshtë: disponueshmëria e disa operacioneve të disponueshme për elementë të këtij lloji;
si dhe të dhënat mbi të cilat kryhen këto operacione (vargu i vlerave).
Çfarë do të thotë fjala "abstrakt"? Para së gjithash, koncepti "abstrakt" nënkupton përqendrimin në diçka të rëndësishme dhe, në të njëjtën kohë, duhet të largohemi nga detajet e parëndësishme, për momentin. Përkufizimi i abstraktit është i mbuluar mirë në librin e Grady Booch. Përkufizimi tingëllon si ky:
Abstraksioni është përzgjedhja dhe dhënia e një grupi objektesh të vetive të përbashkëta që përcaktojnë kufijtë e tyre konceptualë dhe i dallojnë ato nga të gjitha llojet e tjera të objekteve.
Me fjalë të tjera, abstraksioni na lejon të "ndriçojmë dritë" mbi të dhënat e objektit që na duhen dhe, në të njëjtën kohë, të "errësojmë" të dhënat që nuk janë të rëndësishme për ne.
Pra, çfarë do të ndodhë nëse bashkojmë konceptet e "llopit të të dhënave" dhe "abstraksionit" së bashku? Ne do të marrim një lloj të dhënash që na siguron një grup operacionesh që ofrojnë sjelljen e objekteve të këtij lloji të të dhënave, dhe ky lloj i të dhënave do të fshehë gjithashtu të dhënat me të cilat zbatohet kjo sjellje. Nga këtu, ne vijmë te koncepti i ATD:
Një ADT është një lloj i të dhënave që fsheh zbatimin e tij të brendshëm nga klientët.
Gjëja e mahnitshme është se duke aplikuar abstraksionin, ADT na lejon të mos mendojmë për detaje të zbatimit të nivelit të ulët, por të punojmë me një entitet të nivelit të lartë të botës reale (Steve McConnell).
Unë besoj se kur dizajnoni një ADT, së pari duhet të përcaktoni një ndërfaqe, sepse një ndërfaqe nuk duhet të varet nga përfaqësimi i brendshëm i të dhënave në një ADT. Pas përcaktimit të operacioneve që përbëjnë ndërfaqen, duhet të përqendroheni në të dhënat që do të zbatojnë sjelljen e specifikuar të ADT. Si rezultat, ne marrim një strukturë të caktuar të dhënash - një mekanizëm që ju lejon të ruani dhe përpunoni të dhëna. Në të njëjtën kohë, bukuria e ADT është se nëse duam të ndryshojmë paraqitjen e brendshme të të dhënave, atëherë nuk kemi pse të endemi nëpër të gjithë programin dhe të ndryshojmë çdo rresht kodi që varet nga të dhënat që duam të ndryshojmë. ADT përmbledh këto të dhëna, gjë që ju lejon të ndryshoni sjelljen e objekteve të këtij lloji, në vend të të gjithë programit.
Përfitimet e ATD
Ka shumë përparësi për të përdorur një ADT (të gjitha avantazhet e përshkruara mund të gjenden në Kodin Perfect të Steve McConnell):
- Enkapsulimi i detajeve të zbatimit.
Kjo do të thotë që pasi të kemi përmbledhur detajet e zbatimit se si funksionon ADT, ne i ofrojmë klientit një ndërfaqe përmes së cilës ai mund të ndërveprojë me ADT. Duke ndryshuar detajet e zbatimit, pamja e klientit për funksionimin e ADT nuk do të ndryshojë.
- Kompleksiteti i reduktuar.
Duke u larguar nga detajet e zbatimit, ne fokusohemi në ndërfaqen, domethënë në atë që një ADT mund të bëjë, sesa në mënyrën se si bëhet. Për më tepër, ADT na lejon të punojmë me thelbin e botës reale.
- Kufizimi i fushës së përdorimit të të dhënave.
Duke përdorur një ADT, mund të jemi të sigurt se të dhënat që përfaqësojnë strukturën e brendshme të një ADT nuk do të varen nga pjesë të tjera të kodit. Në këtë rast realizohet “pavarësia” e ADT-së.
- Përmbajtja e lartë e informacionit të ndërfaqes.
ATD ju lejon të përfaqësoni të gjithë ndërfaqen për sa i përket entiteteve të fushës së temës, gjë që, siç shihni, rrit lexueshmërinë dhe informativitetin e ndërfaqes.
Steve McConnell rekomandon përfaqësimin e llojeve të të dhënave të nivelit të ulët të tillë si një pirg ose një listë si një ADT. Pyesni veten se cila është kjo listë. Nëse përfaqëson një listë të punonjësve të bankës, atëherë trajtojeni ADT-në si një listë të punonjësve të bankës.
Pra, ne kuptuam se çfarë është ATD dhe i quajtëm avantazhet e përdorimit të tij. Tani vlen të përmendet se kur zhvilloni klasa në OOP, duhet të mendoni, para së gjithash, për ADT. Thënë kjo, siç tha Steve McConnell, ju nuk programoni në një gjuhë, por me një gjuhë. Kjo do të thotë, ju do të programoni përtej gjuhës, duke mos u kufizuar në mendime për sa i përket vargjeve ose llojeve të thjeshta të të dhënave. Në vend të kësaj, ju do të mendoni për një nivel të lartë abstraksioni (p.sh., për sa i përket tabelave ose listave të punonjësve). Një klasë nuk është gjë tjetër veçse një shtesë dhe një mënyrë për të zbatuar konceptin e një ADT. Ne madje mund ta paraqesim klasën si një formulë:
Klasa = ATD + Trashëgimia + Polimorfizmi.
Pra, pse duhet të mendoni për ADT-të kur hartoni klasa. Sepse, së pari ne duhet të vendosim se cilat operacione do të përbëjnë ndërfaqen e klasës së ardhshme, cilat të dhëna të fshihen dhe cilat të ofrojnë akses publik. Ne duhet të mendojmë për ta bërë ndërfaqen shumë informative, për ta bërë kodin të lehtë për t'u optimizuar dhe testuar, dhe si mund të ofrojmë abstraksionin e duhur në mënyrë që të mund të mendojmë për entitetet e botës reale dhe jo për detajet e zbatimit të nivelit të ulët. Besoj se pas përcaktimit të ADT duhet të mendojmë për çështjet e trashëgimisë dhe polimorfizmit.
Vlen të përmendet se koncepti ADT ka gjetur aplikim të gjerë në OOP, sepse është ky koncept që plotëson OOP dhe ju lejon të zvogëloni kompleksitetin e programeve në një botë që ndryshon me shpejtësi kërkesat e softuerit.
E shkrova këtë artikull për të tërhequr vëmendjen e zhvilluesve te ATD për të përmirësuar cilësinë e punës dhe zhvillimin e softuerit.
Burimet e përdorura:
Steve McConnell - "Kodi i përsosur";
Robert Sedgwick - Algoritmet në Java.
