Të gjitha llojet e të dhënave të integruara janë abstrakte, megjithëse rrallë quhen kështu.
Koncepti i abstraksionit
Një abstraksion është një gjykim ose paraqitje për një objekt që përmban vetëm vetitë që janë të rëndësishme në kontekstin e dhënë. Abstraksioni ju lejon të kombinoni instancat e objekteve në grupe, brenda të cilave vetitë e përgjithshme objektet mund të injorohen, d.m.th. abstrakt prej tyre. Abstraksioni është një ilaç efektiv kundër kompleksitetit të programimit, duke i lejuar programuesit të fokusohet në vetitë thelbësore të objekteve. Llojet e abstraksioneve: procesi i abstraksionit dhe abstragimi i të dhënave.
Abstraksioni i procesit. Të gjitha nënproceset janë abstraksione të proceseve; ato përcaktojnë mënyrën në të cilën një program përcakton që një proces duhet të kryhet, pa specifikuar detajet se si duhet bërë saktësisht. Aftësia për të hequr shumë detaje të algoritmit që ekzekuton një nënprogram bën të mundur shkrimin, leximin dhe kuptimin e programeve të mëdha. Çdo abstraksion i të dhënave janë operacione, të përcaktuara si abstraksione të procesit.
Abstragimi i të dhënave. Një lloj abstrakt i të dhënave është një kapsulim që përmban vetëm paraqitje të të dhënave të një lloji të veçantë dhe rutina që kryejnë operacione në të dhënat e atij lloji. Me kontrollin e aksesit, mund të fshihen detaje jo thelbësore të një përshkrimi të llojit modulet e jashtme që përdorin këtë lloj. Modulet e programit që përdorin një lloj të dhënash abstrakte mund të deklarojnë variabla të atij lloji, edhe pse përfaqësimi aktual i llojit është i fshehur prej tyre. shembull lloji abstrakt të dhënat quhet objekt.
Arsyeja për krijimin e një abstraksioni të tipit të të dhënave dhe një abstraksioni të procesit është një ilaç kundër kompleksitetit, një mënyrë për të bërë të mëdha dhe/ose programe komplekse më të menaxhueshme.
Kapsulimi
Ndarja e një programi në kontejnerë sintaksorë që përmbajnë grupe rutinash dhe të dhënash të lidhura logjikisht. Këto kontejnerë sintaksorë quhen module, dhe procesi i zhvillimit të tyre quhet modularizim.
Kompozimi i një programi nga grupe rutinash dhe të dhënash, secila prej të cilave mund të kompilohet veçmas pa rikompiluar pjesën tjetër të programit. Një grup i tillë quhet njësi përpilimi.
Enkapsulimi është një mënyrë për të kombinuar nënprogramet dhe të dhënat që ato përpunojnë në një tërësi të vetme. Kapsulimi, i cili përpilohet veçmas ose në mënyrë të pavarur, është baza e një sistemi abstrakt dhe organizimi logjik i një grupi llogaritjesh përkatëse.
Llojet abstrakte të të dhënave të përcaktuara nga përdoruesi
Llojet e të dhënave abstrakte të përcaktuara nga përdoruesi duhet të kenë vetitë e mëposhtme:
1) përcaktimi i tipit, i cili lejon modulet e programit të deklarojnë variabla të këtij lloji, duke krijuar një paraqitje reale të këtyre variablave në memorie.
2) një grup operacionesh për manipulimin e objekteve të këtij lloji.
Një përkufizim formal i një lloji abstrakt të të dhënave në kontekstin e llojeve të përcaktuara nga përdoruesi: Një lloj i të dhënave abstrakte është një lloj i të dhënave që plotëson dy kushtet e mëposhtme.
Përfaqësimi (përcaktimi i tipit) dhe operacionet në objekte të një lloji të caktuar përmbahen në një njësi sintaksore, variablat e këtij lloji mund të krijohen edhe në module të tjera.
Përfaqësimi i objekteve të këtij lloji është i fshehur nga modulet e softuerit që përdorin këtë lloj, është e mundur të kryhen operacione në objekte që parashikohen drejtpërdrejt në përkufizimin e tipit.
Paketimi i paraqitjes së tipit dhe operacioneve në një njësi të vetme sintaksore lejon që programi të organizohet në njësi logjike që mund të kompilohen veçmas. Së dyti, bëhet e mundur modifikimi i paraqitjeve të objekteve të një lloji të caktuar ose operacioneve me to në një pjesë të veçantë të programit. Ka avantazhe për të fshehur detajet e paraqitjes së tipit. Klientët nuk mund të "shohin" detajet e përfaqësimit të një objekti dhe kodi i tyre nuk varet nga ai përfaqësim. Kështu, paraqitjet e objekteve mund të ndryshohen në çdo kohë pa kërkuar ndryshime në kodin e klientit. Një përfitim tjetër i dukshëm dhe i rëndësishëm i fshehjes së informacionit është rritja e besueshmërisë. Klientët nuk mund të modifikojnë drejtpërdrejt paraqitjet themelore të objekteve, qoftë qëllimisht apo aksidentalisht, duke rritur kështu integritetin e objekteve të tilla. Objektet mund të modifikohen vetëm duke përdorur operacionet e parashikuara për këtë.
Çështjet e projektimit të tipit
Duhet të jetë e mundur që emri i tipit dhe titujt e nënrutinës të jenë të dukshëm në klientët e abstraksionit. Kjo i lejon klientët të deklarojnë variabla të një lloji abstrakt dhe të manipulojnë vlerat e tyre. Megjithëse emri i tipit duhet të jetë i dukshëm nga jashtë, përkufizimi i tij duhet të jetë i fshehur.
Ka shumë pak operacione të përgjithshme të integruara që mund të kryhen në objekte të llojeve abstrakte, përveç atyre të parashikuara nga përkufizimi i tipit. Këto operacione përfshijnë detyra, si dhe teste të barazisë dhe pabarazisë. Nëse gjuha nuk i lejon përdoruesit të mbingarkojnë operatorin e caktimit, atëherë ai duhet të jetë në linjë. Testet e barazisë dhe pabarazisë duhet të paracaktohen në disa raste dhe jo në të tjera. Projektuesi i tipit duhet të përcaktojë vetë operacionet për shumicën e llojeve abstrakte të të dhënave.
Gjuhët Smalltalk, C++ dhe Java mbështesin drejtpërdrejt llojet abstrakte të të dhënave.
Llojet abstrakte të të dhënave në C++
Ada dhe Modula-2 ofrojnë përmbledhje që mund të përdoret për të modeluar lloje abstrakte të të dhënave, C++ prezanton konceptin e një klase që mbështet drejtpërdrejt llojet e të dhënave abstrakte. Në C++, klasat janë lloje, por paketat Ada dhe modulet Modula-2 nuk janë lloje. Paketat dhe modulet importohen, duke lejuar njësinë e softuerit importues të deklarojë variabla të çdo lloji të përcaktuar në paketë ose modul. Në një program C++, variablat deklarohen si entitete që kanë llojin e klasës së dhënë. Kështu, klasat janë shumë më tepër si lloje të integruara sesa paketa ose module. Një njësi softuerike që sheh një paketë Ada ose një modul Modula-2 ka akses në çdo njësi publike thjesht me emrat e tyre. Një njësi C++ që deklaron një shembull të një klase ka gjithashtu akses në çdo njësi publike në atë klasë, por vetëm përmes shembullit të asaj klase.
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 llojet e bazës të dhëna (reale, numër i plotë, varg, 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ë hyni drejtpërdrejt në këtë strukturë të të dhënave duke iu referuar emrave të fushave. Ju mund të kryeni veprime 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 sipas 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 shembull ka një lloj të dhënash, i cili mund të jetë ose një lloj bazë ose një tjetër ATD;
· Operacionet dhe kufizimet ATD zbatohen duke përdorur metoda.
Përkufizimi ATD rindërton përkufizimin e klasës. Disa sisteme OO përdorin fjalën kyçe të tipit për të dalluar klasat dhe llojet kur iu referohen strukturave të të dhënave dhe metodave të një klase, dhe fjalën kyçe të klasës kur i referohen një grupi instancash objektesh. 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ë.
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.
Gjuha C++ ju lejon të krijoni lloje të dhënash që sillen në mënyrë të ngjashme me llojet bazë të gjuhëve C. Këto lloje zakonisht quhen Llojet abstrakte të të dhënave(ATD).
Strukturat përdoren për të zbatuar ADT në gjuhën C. Por përdorimi i të dhënave lloji strukturor i kufizuar dukshëm në krahasim me përdorimin e llojeve bazë të të dhënave. Për shembull, të dhënat strukturore nuk mund të përdoren si operandë në operacione të ndryshme (mbledhje, zbritje). Për të manipuluar të dhëna të tilla, duhet të shkruani një grup funksionesh që kryejnë aktivitete të ndryshme, dhe thirrni këto funksione në vend të operacioneve.
Për më tepër, elementët e strukturës nuk mbrohen në asnjë mënyrë nga modifikimi aksidental. Kjo do të thotë, çdo funksion (madje edhe jo nga grupi i mjeteve për manipulimin e të dhënave strukturore) mund t'i referohet një elementi strukture. Kjo është në kundërshtim me një nga parimet kryesore të programimit të orientuar nga objekti - kapsulimi i të dhënave: asnjë funksion tjetër përveç funksione të veçanta manipulimet e këtij lloji të të dhënave nuk duhet të kenë akses te anëtarët e të dhënave.
Le të shqyrtojmë zbatimin e konceptit të datës duke përdorur struct për të përcaktuar paraqitjen e datës së datës dhe një grup funksionesh për të punuar me variabla të këtij lloji:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#përfshi
data e strukturës
{
muaji int; // muaj
ditë int; // ditë
viti int; // vit
};
datë_caktimi i pavlefshëm(data* f, int d, int m, int y)
{
f->ditë = d;
f->muaj = m;
f->vit = y;
}
data_printimi i pavlefshëm (data*f)
{
printf("%d.%d.%d" , f->ditë, f->muaj, f->vit);
}
int main()
{
data sot;
data_caktimi (&sot, 2, 4, 2014);
data_printimi (&sot);
getchar ();
kthimi 0;
}
Rezultati i ekzekutimit
Nuk ka asnjë lidhje të qartë midis funksioneve dhe llojit të të dhënave në këtë shembull. Për të thirrur ndonjë nga funksionet e përshkruara, ju duhet të kaloni një tregues në një shembull të strukturës si argument.
Një marrëdhënie e tillë mund të krijohet duke përshkruar funksionet si anëtarë të një strukture. Këto funksione mund të veprojnë në të dhënat e përfshira në vetë strukturën.
Si parazgjedhje, kur një strukturë deklarohet, të dhënat dhe funksionet e saj ndahen, që do të thotë se objektet e llojit të strukturës nuk kanë as kapsulim dhe as mbrojtje të të dhënave:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#përfshi
data e strukturës
{
muaji int; // muaj
ditë int; // ditë
viti int; // vit
data_caktimi i pavlefshëm (int d, int m, int y)
{
ditë=d; muaj=m; vit=y;
}
void print_data(void);
};
data e pavlefshme::print_date(void )
{
printf("%d.%d.%d" , dita, muaji, viti);
}
int main()
{
data sot;
sot.data_vendosje(2, 4, 2014);
sot.data_printimit();
getchar ();
kthimi 0;
}
Funksionet e anëtarëve dhe anëtarët e të dhënave
Funksionet e deklaruara në trupin e një lloji abstrakt të të dhënave janë funksione ose metoda anëtare dhe mund të thirren vetëm në një variabël të veçantë të llojit përkatës duke përdorur sintaksën standarde për të aksesuar anëtarët e të dhënave ose fushat e një strukture.
Funksionet e anëtarëve mund të përcaktohen në dy mënyra:
- përshkrimi i funksionit drejtpërdrejt në përshkrimin e strukturës;
- përshkrimi i funksionit jashtë strukturës.
Funksionet e anëtarëve që përcaktohen brenda një strukture janë në mënyrë implicite në linjë ( ). Si rregull i përgjithshëm, vetëm funksionet e anëtarëve të shkurtër dhe të përdorur shpesh duhet të përcaktohen brenda një strukture: grup i pavlefshëm(int m, int d, int y) (muaj = m; ditë = d; viti = y;);
Për aq sa struktura të ndryshme mund të ketë funksione anëtare me të njëjtët emra, kur përcaktoni një funksion anëtar, duhet të specifikoni emrin e strukturës duke i lidhur ato me operatorin e zgjidhjes së kontekstit (dy pika):
Lloji ATD:: emri (lista e argumenteve) (
organi i funksionit anëtar; )
- një llojështë lloji i kthimit të funksionit anëtar
- ATD— emri i llojit të të dhënave abstrakte (emri i strukturës ose klasës)
- emri- emri i funksionit të anëtarit
data e pavlefshme::print_date(void )
( printf("%d.%d.%d" ,ditë, muaj, vit);)
Në një funksion anëtar, emrat e anëtarëve mund të përdoren pa një referencë të qartë të objektit. Në këtë rast, emri i referohet anëtarit të objektit në të cilin është thirrur funksioni.
Funksionet e anëtarëve të së njëjtës strukturë mund të jenë polimorfike, domethënë të mbingarkuara.
Të drejtat e aksesit
Koncepti i një strukture në C++ (ndryshe nga C) lejon që anëtarët e një strukture të jenë publike, private ose të mbrojtura:
- publik - i përgjithshëm;
- private - private;
- i mbrojtur - i mbrojtur.
Përdorimi fjalë kyçe i mbrojtur lidhet me konceptin e trashëgimisë.
Përdorimi i fjalës kyçe private kufizon aksesin për anëtarët që ndjekin këtë konstrukt. Anëtarët privatë mund të përdoren vetëm nga disa kategori funksionesh që kanë privilegje për t'iu qasur atyre anëtarëve. Ato janë në thelb funksione anëtare të së njëjtës strukturë.
Fjala kyçe publike formon një ndërfaqe me një objekt strukture.
Është standarde të vendosen të dhënat e anëtarëve zonë private(private ) dhe pjesët e funksionit anëtar në pjesën publike (publike) të tipit abstrakt të të dhënave. Në këtë rast, pjesa private (private) përcakton të dhënat e objektit dhe funksionet e dobishme, dhe funksionet anëtare të pjesës publike zbatojnë metoda për të punuar me objektin.
Le të ndryshojmë strukturën e datës për të fshehur paraqitjen e të dhënave (inkapsulimi i të dhënave):
1
2
3
4
5
6
7
8
data e strukturës
{
private:
në muajin, ditën, vitin;
publike:
grup void (int, int, int);
voidprint();
};
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 i të dhënave abstrakte, 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.
Të gjitha sistemet kompjuterike bazohen në nivelet e abstraksionit: disa veti fizike të silikonit dhe materialeve të tjera lejojnë adoptimin e një modeli abstrakt të një biti, 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 niveleve 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ë përfaqësimi 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ë përfaqësimi 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 pika (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 software: 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 ndërfaqes 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 përfaqësimi 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ë punon 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 funksionet 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), dhe dy funksione anëtare të përcaktuara për të gjitha rastet e klasës POINT: 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 të qenit i plotë. 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.
1.2. Llojet abstrakte të të dhënave
Shumica e koncepteve të prezantuara në pjesën e mëparshme 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. Ndryshe nga operatorët e integruar të një gjuhe programimi, të cilët janë të kufizuar në aftësitë e tyre (mbledhje, shumëzim, etj.), me ndihmën e procedurave, një programues mund të krijojë operatorët e tij dhe t'i zbatojë ato në operandë të llojeve të ndryshme, jo vetëm ato themelore. Një shembull i një operatori 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ërcaktimi i një lloji abstrakt të të dhënave
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 tiparet kryesore të procedurave, përgjithësimi dhe kapsulimi, të diskutuara më sipër, janë përshkrime të shkëlqyera të llojeve abstrakte të të dhënave. Një ADT mund të konsiderohet si një përgjithësim i llojeve të thjeshta të të dhënave (numra të plotë, numra realë, etj.), ashtu si një procedurë është një përgjithësim i operatorëve 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 nuk ka element tjetër.
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ë.
Le të kthehemi te lloji abstrakt i të dhënave GRAPH (Graph). 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ë paplotësuar.
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 implementim 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 implementimet e mundshme të një ndryshoreje S të 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ë llojeve të ndryshme. Ky përmbledhje mbulon vetëm disa modele themelore matematikore, të tilla si teoria e grupeve dhe teoria e grafikëve, por zbatime të ndryshme do të ndërtojnë grupe të ndryshme operatorësh bazuar në këto modele të ADT-ve të caktuara.
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 Pascal nuk është 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ë. . Për më shumë informacion rreth këtyre gjuhëve programuese, shihni shënimet bibliografike në fund të temës.
