1.2. Llojet abstrakte të të dhënave
Shumica e koncepteve të prezantuara në seksionin e mëparshëm zakonisht prezantohen në një kurs programimi fillestar 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ë programit. Para së gjithash, le të krahasojmë një lloj të dhënash abstrakte me një koncept kaq të njohur si një procedurë.
Një procedurë, një mjet programimi integral, mund të shihet si një koncept i përgjithshëm i një operatori. Ndryshe nga operatorët e integruar të gjuhës së programimit (mbledhja, shumëzimi, etj.), të cilët janë të kufizuar në aftësitë e tyre, programuesi mund të përdorë procedura për të krijuar operatorët e vet dhe t'i zbatoni ato në operandë të llojeve të ndryshme, jo vetëm atyre bazë. Një shembull i një procedure të tillë operatori është rutina standarde e shumëzimit të matricës.
Një avantazh tjetër i procedurave (përveç aftësisë për të krijuar operatorë të rinj) është aftësia për t'i përdorur ato 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 për të lexuar të dhënat hyrëse të çdo lloji dhe për të kontrolluar korrektësinë e tyre. Avantazhi i kapsulimit është se ne e dimë se cilat deklarata të kapsuluara duhet të ndryshohen në rast të problemeve në funksionimin e programit. Për shembull, nëse është e nevojshme të organizohet verifikimi i të dhënave hyrëse për vlera pozitive, duhet të ndryshohen 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(ADT) si një model matematikor me një grup operatorësh të përcaktuar brenda këtij modeli. Një shembull i thjeshtë i ADT është një grup numrash të plotë me operatorë të bashkimit, kryqëzimit dhe ndryshimit të 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 programuese ose të përcaktuara në ADT të tjera. Rezultati i veprimit të operatorit mund të jetë gjithashtu i një lloji të ndryshëm nga ato të përcaktuara në këtë model ADT. Por ne supozojmë se të paktën një operand ose rezultat i çdo operatori ka llojin e të dhënave të përcaktuar në modelin ADT të konsideruar.
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 (numra të plotë, numra realë, etj.), ashtu si një procedurë është një përgjithësim operatorë të thjeshtë(+, - etj.). Një ADT përmbledh llojet e të dhënave në kuptimin që përkufizimi i një lloji dhe të gjitha deklaratat e kryera në të dhënat e atij lloji vendosen në një seksion të programit. Nëse është e nevojshme të ndryshojmë zbatimin e ADT, ne e dimë se ku të gjejmë dhe çfarë të ndryshojmë në një seksion 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ëtë lloj të dhënash. Për më tepër, jashtë seksionit për përkufizimin e operatorëve ADT, ne mund t'i konsiderojmë llojet ADT si lloje kryesore, pasi deklarimi i llojeve nuk lidhet zyrtarisht me zbatimin e tyre. Por në këtë rast, mund të shfaqen vështirësi, pasi disa operatorë mund të inicohen për më shumë se një ADT dhe referencat për këta operatorë duhet të jenë në seksione të disa ADT-ve.
Për të ilustruar idetë bazë pas krijimit të një ADT, merrni parasysh rutinën e pangopur nga seksioni i mëparshëm (Lista 1.3), e cila përdor operatorë të thjeshtë në llojin e të dhënave abstrakte 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 artikullin tjetër në listë dhe kthejeni vlerën i pavlefshëm, nëse artikulli tjetër nr.
4. Fusni 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ë diskutohen në detaje në temën 2.) Nëse në Listimin 1.3 zëvendësoni operatorët përkatës me shprehje
MAKENULL (newcJr);
w: = FIRST (newcJr);
w: = NEXT (newcfr);
INSERT (v, newclr);
atëherë do të kuptohet një nga aspektet (dhe avantazhet) kryesore të llojeve abstrakte të të dhënave. 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ës 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. Përzgjidhet kulmi i parë i pa lyer.
2. Kontrolloni nëse ka një skaj midis dy kulmeve.
3. Shënoni kulmin me ngjyrë.
4. Zgjidhni kulmin tjetër të palyer.
Natyrisht, operatorët e tjerë mbeten jashtë vëmendjes së procedurës së babëzitur, të tilla si futja e kulmeve dhe skajeve në grafik ose shënimi i të gjitha kulmeve të grafikut si të hapura. Struktura të ndryshme të dhënat që mbështesin këtë lloj të dhënash do të diskutohen 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 operatorësh përcakton një ADT të veçantë. Këtu janë shembuj të operatorëve që mund të përcaktoni për llojin e të dhënave abstrakte SET (Set).
1. MAKENULL (A), Kjo procedurë e bën të zbrazët grupin A.
2. BASHKIM (A, B, C). Kjo procedurë ka dy argumente "hyrëse", grupet A dhe B, dhe cakton bashkimin e këtyre grupeve me argumentin "output", grup C.
3. MADHËSIA (A). Ky funksion ka një argument të vendosur A dhe kthen një objekt të llojit të plotë të barabartë me numrin e elementeve të grupit A. Termi zbatim i ADT nënkupton sa më poshtë: përkthimi i deklaratave që përcaktojnë variabla të këtij lloji abstrakt të të dhënave në deklaratat e gjuhës programuese, plus procedurat për çdo operator i ekzekutuar në objekte ADT. Zbatimi varet nga strukturat e të dhënave, që përfaqëson ADT. Ç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 të strukturimit të të dhënave të disponueshme 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... Ky përmbledhje mbulon vetëm disa nga kryesoret modele matematikore, si teoria e grupeve dhe teoria e grafikëve, por për zbatime të ndryshme në bazë të këtyre modeleve, do të ndërtohen ADT të caktuara. 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 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ë deklaroheshin drejtpërdrejt ADT-të. Informacion shtese për gjuhë të tilla programimi, shihni shënimet bibliografike në fund të temës.
Lloji i të dhënave përshkruan shumë objekte 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 e të dhënave bazë i binden një grupi të paracaktuar operacionesh. Për shembull, numri i plotë i tipit bazë të të dhënave ju lejon të kryeni veprime të tilla si mbledhje, zbritje, shumëzim, 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. Regjistrimi i KLIENTIT do të jetë lloj i ri të dhënat, të cilat do të ruajnë informacionin e klientit, ju mund të hyni drejtpërdrejt në këtë strukturë të të dhënave duke iu referuar emrave të fushave. Operacione të tilla si WRITE, READ, DELETE, UPDATE mund të kryhen 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ë përfaqësimin e brendshëm të të dhënave dhe zbatimin e metodave.
Në disa sisteme OO (për shembull, Smalltalk), llojet bazë të të dhënave zbatohen si abstrakte.
Për të krijuar një lloj të dhënash abstrakte, duhet të siguroni:
· Shkruani emrin;
· Paraqitja e të dhënave ose variablat e një shembulli të një objekti që i përket ATD; çdo variabël shembull ka një lloj të dhënash që mund të jetë ose lloji i bazës, ose ATD tjetër;
· 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 tip për të dalluar klasat dhe tipat kur iu referohen strukturave të të dhënave dhe metodave të një klase, dhe kur i referohen një grupi shembujsh objektesh - fjalë kyçe klasës. Lloji është një koncept më statik, ndërsa 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 keni 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ë ku 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 fotografisë së punonjësit;
Aftësia për të trajtuar një mjedis të tillë kompleks të të dhënave me lehtësi relative rrit vlerën e sistemeve OO në tregun e sotëm të bazës së të dhënave.
Lloji i të dhënave abstrakte Të dhëna të përgjithshme Abstrakte të tipit të të dhënave dispozitat e përgjithshme specifikim, prezantim, zbatim 1
Çfarë janë të dhënat? Set të ndryshme objektet e informacionit mbi të cilat kryhen veprime të caktuara nga operatorët e programit quhen të dhëna. Të dhënat janë një atribut i domosdoshëm i çdo programi. Ato mund të jenë: - copa të veçanta; - një sekuencë bitesh të pavarur; -numrat në forma të ndryshme të paraqitjes; -bajt dhe grupe bajtësh të pavarur; -vargje numrash; -listat e lidhura; - skedarë të veçantë dhe sistemet e skedarëve. 2
Paraqitja universale e kësaj shumëllojshmërie të dhënash është e vështirë dhe jopraktike. Këshillohet që ato të ndahen në llojet 3.
Çfarë është një tip i të dhënave? Lloji i të dhënave përcaktohet nga: - Formati i paraqitjes në kujtesën e kompjuterit sipas konventave të caktuara të gjuhës algoritmike, por pa pasur nevojë për llogaritje; - Shumë vlerat e pranueshme që mund të marrë një variabël ose konstante që i përket llojit të zgjedhur; - Grupi i operacioneve të vlefshme të zbatueshme për këtë lloj. 4
Shembuj të tipit të të dhënave Llojet e plota Lloji real Lloji Boolean Lloji i karakterit Lloji i numëruar Lloji i intervalit Pointers 5
Llojet e numrave të plotë Ekzistojnë pesë lloje të numrave të plotë të paracaktuar: Shortint, Integer, Longint, Byte dhe Word. Çdo lloj tregon një nëngrup specifik të numrave të plotë. Një vlerë e një lloji të numrit të plotë mund të konvertohet në mënyrë eksplicite në një lloj tjetër të plotë duke hedhur. 6
Lloji real Lloji real është një nëngrup numrash të përfaqësuar në formatin me pikë lundruese me një numër fiks shifrash. Shkrimi i një vlere me pikë lundruese zakonisht përfshin tre vlera - m, b dhe e - të tilla që m * b ^ e = n, ku b është gjithmonë 2 dhe m dhe e janë numra të plotë në intervalin real. Këto vlera m dhe e përcaktojnë më tej gamën e paraqitjes dhe saktësinë e tipit real. Shembull: 0. 143 E + 22, ku m - 0. 143; b = 2 (nënkuptohet), e = 22. Ka pesë lloje lloje reale: real (Real), me saktësi të vetme (Single), me saktësi të dyfishtë (Double), me saktësi të shtuar (Extended) dhe komplekse (Comp). 7
Lloji Boolean Ekzistojnë 4 lloje të Boolean të paracaktuara: Boolean, Byte. Bool, Word. Bool dhe Long. Bool. Vlerat Boolean shënohen me identifikuesit konstant të integruar False dhe True. Variablat Boolean mund të përdoren për të ruajtur rezultatet e çdo llogaritjeje logjike. Për variablat boolean lejohen vetëm 2 operacione krahasimi "=" (barabartë) dhe "" (jo të barabartë). tetë
Lloji i karakterit Grupi i vlerave të këtij lloji janë karaktere të renditura sipas grupit të zgjeruar të karaktereve ASCII. Këto janë shkronjat ["A". ... ... "Z", "a". ... ... "z"], shifra ["0". ... ... "9"], shenjat e pikësimit dhe karakteret speciale. Një variabël i këtij lloji zë një bajt në memorie. 9
Lloji i numëruar Llojet e numëruara përcaktojnë grupe të renditura vlerash duke numëruar identifikuesit që përfaqësojnë ato vlera. Renditja e grupeve kryhet sipas renditjes në të cilën janë renditur identifikuesit. Lloji Java = (e hënë, e martë, e mërkurë, e enjte, e premte, e shtunë, e diel); 10
Lloji i intervalit Një lloj intervali është një varg vlerash nga një lloj rendor. Përkufizimi i një lloji interval përfshin më të voglin dhe vlerën më të madhe në nënvarg. Lloji Interval = 0.. ... 1000; Kjo deklaratë e tipit i tregon kompajlerit se vetëm numrat në diapazonin e specifikuar janë të vlefshëm për variablat e këtij lloji. Kështu, programi mund të organizojë automatikisht kontrolle për korrektësinë e operacioneve të caktimit për këto variabla. njëmbëdhjetë
Të përbashkëta për llojet e të dhënave Secili prej llojeve të të dhënave korrespondon me një grup operacione të thjeshta... Operacionet INTEGER +, -, *, div, mod REAL - operacionet +, -, *, / BOOLEAN- operacionet - lidhja (dhe), disjunksioni V (ose), mohimi (jo) CHAR-operacioni ORD (c) -N : (C në ASCII), CHR (I) Karakteri i I-të në ASCII Ndërsa vëllimi dhe kompleksiteti i paraqitjes së informacionit rritet, lind nevoja për forma të përshtatshme të paraqitjes, ruajtjes dhe përpunimit të tij. 12
Përkufizimi i një lloji abstrakt të të dhënave (ADT ose tipi abstrakt i të dhënave, ose ADT) është një grup objektesh abstrakte që përfaqësojnë elemente të dhënash, dhe të përcaktuara në të grupe operacionesh që mund të kryhen në elementet e këtij grupi. trembëdhjetë
ADT - përgjithësimi i llojeve të të dhënave Llojet abstrakte të të dhënave (ADT) mund të konsiderohen si një mjet për zgjerimin e gjuhëve programuese. Le të krahasojmë një lloj të dhënash abstrakte me një koncept kaq të njohur si një procedurë. Një procedurë mund të shihet si një koncept i përgjithësuar i një operatori. Dy tipare karakteristike të procedurave, përgjithësimi dhe kapsulimi, karakterizojnë në mënyrë të përsosur llojet e të dhënave abstrakte. ADT mund të shihet si një përgjithësim i llojeve të thjeshta të të dhënave (numra të plotë, real, etj.), ashtu si një procedurë është një përgjithësim i operatorëve të thjeshtë (+, -, etj.) 14
Përparësitë Abstrakt ATD strukturat e të dhënave janë për ruajtje e përshtatshme dhe akses në informacion. Ato ofrojnë ndërfaqe miqësore për përdoruesit për operacionet e zakonshme në objektet e ruajtura, duke fshehur detajet e zbatimit nga përdoruesi. Sigurisht, kjo është shumë e përshtatshme dhe ju lejon të arrini modularitet më të madh të programit. 15
Shembull Për kontroll i automatizuar temperatura në dhoma të ndryshme të një ndërtese të madhe, një ATD e dobishme do të ishte një TERMOSTAT. Programi mund të përmbajë shumë variablat e tipit TERMOSTAT që korrespondon me termostatet reale në dhoma të ndryshme të ndërtesës. Një ADT mund të përshkruhet me emrin e tij, grupin e vlerave dhe operacionet e vlefshme ashtu si çdo lloj tjetër i të dhënave. Përshkrimi për llojin TERMOSTAT: - Lloji i të dhënave: TERMOSTAT - Gama e vlerave: temperatura mund të variojë në intervalin nga 0 deri në 50 gradë (Celsius). - Operacionet: më i lartë, i ulët, i caktuar, i kontrollit, i alarmit. (Mund të mendoni për shumë operacione të dobishme, por shumë prej tyre degradojnë abstraksionin) 16
Nivelet e Abstraksionit Nivelet e Abstraksionit janë si shtresa software... Nivelet më të larta të abstraksionit pasqyrojnë idenë e përdoruesit për zgjidhjen e një problemi. Nivelet më të ulëta abstraksionet - aftësitë e gjuhës programuese. 17
Shembull i abstraksionit të nivelit të përdoruesit Një arkitekt paraqet një shtëpi si mure, dysheme, dritare, dyer etj.. Në këtë rast, lloji i të dhënave është Vizatim. Dyert mund të jenë një lloj i mirë abstrakt. Lloji i të dhënave: Figura. Funksionimi i dyerve: Draw. Fshije derën. Vizatimi i derës. Dyfishtë. Dera……. Vizatim. Dyert janë abstraksion nivel të lartë duke pasqyruar pikëpamjen e përdoruesit për problemin 18
Një shembull i abstraksionit në nivelin e programuesit Një programues mund të sugjerojë një nivel tjetër abstraksioni për këto objekte, si për shembull një drejtkëndësh. Lloji i të dhënave: Drejtkëndësh Operacionet: Draw. Fshij drejtkëndëshi. Ndarja drejtkëndëshe. Drejtkëndësh. Në. Pjesë……. Drejtkëndësh - më shumë abstraksion nivel i ulët pasi është më afër zbatimit. nëntëmbëdhjetë
Konstruktorët ADT Çdo ADT duhet të përmbajë operacione për ndërtimin e vlerave të llojit të vet. Operacione të tilla quhen konstruktorë. Duhet të ketë mjaft konstruktorë për të gjeneruar të gjithë grupin e vlerave të këtij lloji... Një ADT që plotëson këtë veti quhet e plotë. ADT jo i plotë është një gabim projektimi. njëzet
Rekomandime për zgjedhjen e operacioneve të tipit abstrakt të të dhënave Këshillohet që të përfshihen operacionet e mëposhtme: - operacionet e konstruktorit, - operacionet e kontrollit, - operacionet e konvertimit të tipit, - Operacionet I/O, - operacionet e kopjimit, - operacionet e përzgjedhësit. Mundohuni të mbani numrin e operacioneve në minimum. Një ADT e thjeshtë është më e lehtë për t'u kuptuar. Ruani lidhjen e operacioneve me abstraksionin e tipit të zgjedhur. 21
Operacionet e Konstruktorit Primar që krijojnë vlera të reja ADT, pavarësisht nga vlera e tyre e mëparshme quhen konstruktorë parësorë. Çdo ADT përfshin të paktën një konstruktor kryesor: pa të, është e pamundur të gjenerohet një vlerë fillestare. 22
Përdorimi i llojeve të fshehura Llojet abstrakte të të dhënave deklarohen më së miri si tipe të fshehura. Kjo ju lejon të zhvendosni përshkrimin e strukturës së të dhënave në modulin e zbatimit, ku përdoret kryesisht. Ato ofrojnë gjithashtu aftësinë për të parandaluar akses direkt tek komponentët e tipit nga ana e importuesit. Meqenëse një tip i fshehur zbatohet gjithmonë duke përdorur një tregues, tre operacione duhet të përfshihen në ADT. - Krijo - një operacion që krijon një nyje të strukturës përkatëse. - Destroy - operacion për të liruar kujtesën e nyjës lloj i fshehur... - Caktimi - funksionimi i kopjimit të fushave të strukturës dinamike të një nyje të tipit të fshehur. 23
Cili është specifikimi dhe zbatimi i një lloji abstrakt të të dhënave Një lloj abstrakt i të dhënave është një mënyrë për të përcaktuar një koncept të caktuar në formën e një klase objektesh me disa veti dhe operacione. Në një gjuhë programimi, një përkufizim i tillë zyrtarizohet si një ndërtim i veçantë sintaksor, i quajtur in gjuhë të ndryshme kapsula, moduli, grupi, klasa, paketa, forma, etj. Ky konstruksion në formën e tij më të avancuar përmban: një specifikim të llojit të të dhënave, duke përfshirë një përshkrim të ndërfaqes (emri i llojit të përcaktuar, emrat e operacioneve me një tregues të tyre profilet) dhe një përshkrim abstrakt të operacioneve dhe objekteve, me të cilat ata punojnë, me disa mjete specifikimi; një zbatim i tipit të të dhënave që përfshin një përshkrim specifik të të njëjtave operacione dhe objekte. 24
Klasifikimi i llojeve të të dhënave sipas mënyrës së përshkrimit dhe mbrojtjes është i paketuar, nëse përshkrimi i llojit të të dhënave është mbledhur në një vend (në një paketë), domethënë, objektet dhe operacionet e tij janë të kombinuara në një koncept; ai ka një përkufizim, i cili megjithatë mund të përmbajë vetëm zbatimin e tij; i kapsuluar, nëse lloji i të dhënave është i paketuar, përkufizimi i tij përmban përshkrimin dhe zbatimin e ndërfaqes, si dhe ofrohet edhe kapsulimi i zbatimit; abstrakt nëse lloji i të dhënave është i kapsuluar dhe specifikimi i tij përfshin një përshkrim abstrakt. 25
Komponentët e specifikimit Programimi, si proces, fillon me deklarimin e problemit (përkufizimin e tij), ose specifikimin e problemit. Më tej, në të gjithë tekstin përdoren specifikimet, të përbërë nga gjashtë komponentë: - Emri - emri i problemit që zgjidhet; - Përshkrimi - disa fjali që përshkruajnë thelbin e detyrës; - Hyrja - pershkrim i detajuar formën e pritur të të dhënave hyrëse; - Outputi - një përshkrim i detajuar i formës së pritur të të dhënave dalëse; - Gabimet - listë të detajuar situatat që lindin nga të dhënat hyrëse të pasakta; - Shembull - një shembull i ekzekutimit në aspektin e hyrje-daljes. 26
Një shembull i specifikimit Lloji abstrakt i të dhënave STEK, i cili zbaton një strukturë të njohur të dhënash, e cila karakterizohet nga fakti se është e mundur të "vendosësh" një element në të dhe të "zgjidhësh" prej tij elementin që është vendosur atje. më së fundmi. Pjesa sintaksore e specifikimit të tipit të të dhënave STEK ka lloji i pamjes Specifikimi i STACK është CREATE: funksioni () return (@); INSERT: funksioni (integer; @) return (@); FSHI: funksioni (@) kthimi (@); TOP: funksioni (@) kthimi (i plotë); EMPTY: funksioni (@) kthimi (boolean); specifikimi i fundit; Këtu operacioni CREATE jep një pirg bosh si rezultat, INSERT - një pirg me elementin e tij të shtuar në "lart", DELETE - një pirg me elementin "lart" të hequr, TOP - vlera e elementit të pirgut "lart". , EMPTY - një shenjë e pirgut bosh. Vetëm numrat e plotë mund të jenë elementë të stivës këtu. 27
ZBATIMI I LLOJIT TË TË DHËNAVE ABSTRAKTE Zbatimi është më i përshtatshëm për t'u bërë duke përdorur gjuhë programimi të orientuara nga objekti, të tilla si C ++ ose Java, në të cilat llojet abstrakte të të dhënave mbështeten duke përdorur klasa. Një zbatim ADT përfshin një përshkrim konkret të objekteve të llojit që të përcaktuara dhe zbatimin e operacioneve të atij lloji. Kjo do të thotë që objektet përshkruhen ose si lloje të thjeshta të dhënash, ose si vargje, regjistrime ose bashkime. Për më tepër, përdoren llojet e paracaktuara të të dhënave ose ADT-të e përcaktuara më parë. Zbatimi i operacioneve konsiston në përshkrimin e nënprogrameve që kryejnë veprimet e nevojshme me objektet e specifikuara. Për shembull, operacionet +, *, =. ... e kështu me radhë, por në të njëjtën kohë fshihet vetë zbatimi i këtyre operacioneve. 28
Zhvillimi i modeleve abstrakte për të dhënat dhe si të përpunohen ato të dhëna ë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 një problem të lidhjes duke përdorur një pyll kërkimi të bashkuar në "Hyrje"). Ky leksion diskuton llojet e të dhënave abstrakte (në tekstin e mëtejmë 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ë shkëputni transformimet abstrakte (konceptuale) që programet kryejnë në të dhëna nga çdo paraqitje e veçantë e një strukture të dhënash ose ndonjë 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ë të adoptohet një model abstrakt i një bit, i cili mund të marrë vlera binare 0-1; atëherë 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 një programi në gjuha e makinerisë po ndërtohet një model abstrakt i gjuhës programuese; dhe, në fund, ndërtohet një koncept abstrakt i një algoritmi, i cili zbatohet si program në gjuhën 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 janë të përshtatshme për zgjidhjen e problemeve në fusha të shumta aplikimi, si dhe për krijimin e mekanizmave abstraktë të nivelit më 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 konstruksioneve abstrakte të çliron 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; ne implementojmë 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 krijohen bazuar në më shumë dizajne të thjeshta... Në të gjitha nivelet, zbatohet i njëjti parim bazë: është e nevojshme të gjesh sa më shumë operacione të rëndësishme në programe dhe shumica karakteristika të rëndësishme të dhënat, dhe më pas të përcaktohen me saktësi 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.
Për të zhvilluar një nivel të ri abstraksioni, do t'ju duhet (1) të përcaktoni objektet abstrakte që duhet të manipulohen dhe operacionet që duhet të kryhen mbi to; (2) përfaqësojnë të dhënat në disa strukturë të dhënash dhe zbatojnë operacione; (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, kështu që mekanizmat bazë për mbështetjen e llojeve të të dhënave që u diskutuan në "Strukturat e të dhënave atomike" mund të përshtaten për qëllimet tona. Sidoqoftë, gjuha C ++ sugjeron shtrirje e rëndësishme një mekanizëm strukturor i quajtur klasë. Klasat janë jashtëzakonisht të dobishme për krijimin e niveleve të abstraksionit dhe për këtë arsye konsiderohen si mjeti kryesor i përdorur për këtë qëllim gjatë pjesës së mbetur të këtij libri.
Përkufizimi 4.1. Një lloj abstrakt i të dhënave (ADT) është një lloj i të dhënave (një grup vlerash dhe një grup operacionesh për ato vlera) që aksesohet vetëm përmes një ndërfaqeje. Një program që përdor një ADT do të quhet klient, dhe një program që përmban një specifikim të këtij lloji të të dhënave quhet një zbatim.
Është fjala që e bën vetëm llojin e të dhënave abstrakte: në rastin e 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 ndërfaqja 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 mënyra më e lehtë për të krijuar një ndërfaqe është përfshirja prezantimi i të dhënave por duke specifikuar që programeve të klientit nuk u lejohet qasja e drejtpërdrejtë në të dhëna. Me fjalë të tjera, zhvilluesit e softuerit të klientit 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ënuara 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 prezantimin e të dhënave (si dhe përcaktojmë një numër 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ë të metë: nëse duhet të ndryshoni prezantimi i të dhënave, atëherë të gjitha programet e klientit do të duhet të ndryshohen. Programi 3.3 përsëri na jep një shembull të thjeshtë: një nga arsyet e dizajnimit të këtij lloji të të dhënave është komoditeti i programeve të klientit me pika, dhe ne presim që klientët të kenë akses në koordinatat individuale të pikave kur ë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ë ndryshme 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 nga Programi 3.3, por duke përdorur një klasë C ++ që përcakton menjëherë të dhënat dhe operacionet e lidhura me të. Programi 4.2 është program klienti duke punuar 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ë disa nga vetitë themelore të klasave që do t'i shikojmë 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 (inline) të tipit int të cilat mund të aksesohen nga i. Në gjuhën C ++, ekziston termi objekt për entitete të tilla. Kur shkruani një përkufizim të tillë si POINT p në një program, thuhet se krijoni një objekt të klasës POINT, i cili mund të aksesohet me emrin p. Në shembullin tonë, çdo objekt përmban dy elementë të të dhënave, të emërtuara 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. Një klasë mund të përcaktojë gjithashtu funksione anëtare që zbatojnë operacionet e lidhura me atë 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 që gjenden në ndonjë strukturë. Për shembull, shprehja p.distance (q) llogarit distancën midis pikave p dhe q (e njëjta distancë duhet të kthehet duke thirrur q.distanca (p)). Funksioni POINT (), i pari në Programin 4.1, është një funksion i veçantë anëtar i quajtur konstruktor: ka të njëjtin emër si një klasë dhe thirret sa herë që duhet të krijohet një objekt i asaj klase.
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 me pika lundruese" (duke supozuar se ato interpretohen si pika në rrafshin 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 në vlera të rastësishme nga 0 në 1, dhe një funksion distancë (POINT) që llogarit distancën në një pikë tjetër. Prezantimi i të dhënaveështë private, dhe vetëm funksionet e anëtarëve mund ta qasen ose modifikojnë atë. Vetë funksionet e anëtarëve janë 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. Operacion i ri krijon një grup objektesh POINT (duke thirrur konstruktorin POINT () për të inicializuar çdo objekt me koordinata të rastësishme). Shprehja a [i] .distanca (a [j]) thërret objektin a [i] funksionin e anëtarit të distancës 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 ()) për t'i caktuar secilit prej dy artikujve të tij të të dhënave një vlerë të rastësishme në rangun nga 0 në 1.
Ky stil programimi, i referuar ndonjëherë si programim i orientuar nga objekti, mbështetet plotësisht nga konstrukti i klasës C ++. Një klasë mund të konsiderohet si një zgjerim i konceptit të strukturës, ku jo vetëm kombinohen të dhënat, por përcaktohen edhe operacionet me këto 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ë shembuj të të njëjtit lloj të dhënash. Në programimin e orientuar nga objekti, objektet janë krijuar për të përpunuar të dhënat e anëtarëve të tyre (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 klasave të vogla të përshkruar më sipër vetëm për t'u njohur me veçoritë themelore të klasave; prandaj është larg nga kompletimi. Në kodin real për klasën e pikëve, do të kemi shumë më tepër operacione. Për shembull, Programi 4.1 nuk ka as operacione që ju lejojnë të zbuloni vlerat e koordinatave x dhe y. Siç do ta 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 pika dhe abstraksione të tjera gjeometrike si vijat dhe poligonet.
Në C ++ (por jo C), strukturat mund të kenë gjithashtu 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.
