Preden vemo o abstraktnem podatkovnem tipu, bi morali vedeti, kaj je podatkovna struktura.
Kaj je struktura podatkov?
Struktura podatkov je tehnika organiziranja podatkov, tako da jih je mogoče učinkovito uporabiti. Podatkovno strukturo si lahko ogledate na dva načina:
Zakaj struktura podatkov?
Prednosti uporabe podatkovne strukture so naslednje:
- To so bistvene sestavine, ki se uporabljajo za ustvarjanje hitrih in zmogljivih algoritmov.
- Pomagajo nam pri upravljanju in organiziranju podatkov.
- Zaradi podatkovnih struktur je koda čistejša in lažja za razumevanje.
Kaj je abstraktni podatkovni tip?
Abstraktni podatkovni tip je abstrakcija podatkovne strukture, ki zagotavlja le vmesnik, ki se mu mora podatkovna struktura držati. Vmesnik ne daje nobenih posebnih podrobnosti o tem, kaj bi bilo treba implementirati ali v katerem programskem jeziku.
Z drugimi besedami, lahko rečemo, da so abstraktni podatkovni tipi entitete, ki so definicije podatkov in operacij, vendar nimajo podrobnosti izvedbe. V tem primeru poznamo podatke, ki jih shranjujemo, in operacije, ki jih lahko izvajamo s podatki, ne poznamo pa podrobnosti izvedbe. Razlog za pomanjkanje podrobnosti o implementaciji je, da ima na primer vsak programski jezik drugačno strategijo implementacije; podatkovna struktura C je implementirana z uporabo struktur, medtem ko je podatkovna struktura C++ implementirana z uporabo objektov in razredov.
na primer Seznam je abstraktni podatkovni tip, ki je implementiran z uporabo dinamične matrike in povezanega seznama. Čakalna vrsta je implementirana s pomočjo povezane čakalne vrste na podlagi seznama, čakalne vrste na podlagi polja in čakalne vrste na podlagi sklada. Zemljevid je implementiran z uporabo drevesnega zemljevida, zgoščenega zemljevida ali zgoščene tabele.
Model abstraktnega podatkovnega tipa
Preden se seznanimo z modelom abstraktnega podatkovnega tipa, bi morali poznati abstrakcijo in enkapsulacijo.
java dodaj v matriko
Abstrakcija: je tehnika skrivanja notranjih podrobnosti pred uporabnikom in prikaz le potrebnih podrobnosti uporabniku.
Enkapsulacija: To je tehnika združevanja podatkov in članske funkcije v eno samo enoto, znana kot enkapsulacija.
Zgornja slika prikazuje model ADT. V modelu ADT obstajata dve vrsti modelov, tj. javna funkcija in zasebna funkcija. Model ADT vsebuje tudi podatkovne strukture, ki jih uporabljamo v programu. V tem modelu se najprej izvede enkapsulacija, to je, da so vsi podatki oviti v eno samo enoto, to je ADT. Nato se izvede abstrakcija, ki pomeni prikaz operacij, ki jih je mogoče izvajati na podatkovni strukturi in katere so podatkovne strukture, ki jih uporabljamo v programu.
Razumejmo abstraktni podatkovni tip s primerom iz resničnega sveta.
Če upoštevamo pametni telefon. Gledamo visoke specifikacije pametnega telefona, kot so:
- 4 GB RAM-a
- Procesor Snapdragon 2,2 GHz
- 5 inčni LCD zaslon
- Dvojna kamera
- Android 8.0
Zgornje specifikacije pametnega telefona so podatki, na pametnem telefonu pa lahko izvajamo tudi naslednje operacije:
panjska arhitektura
Pametni telefon je subjekt, katerega podatki ali specifikacije in operacije so navedeni zgoraj. Abstraktni/logični pogled in operacije so abstraktni ali logični pogledi pametnega telefona.
Izvedbeni pogled zgornjega abstraktnega/logičnega pogleda je podan spodaj:
class Smartphone { private: int ramSize; string processorName; float screenSize; int cameraCount; string androidVersion; public: void call(); void text(); void photo(); void video(); }
Zgornja koda je implementacija specifikacij in operacij, ki jih je mogoče izvesti na pametnem telefonu. Izvedbeni pogled se lahko razlikuje, ker je sintaksa programskih jezikov drugačna, vendar bi abstrakten/logični pogled na strukturo podatkov ostal enak. Zato lahko rečemo, da je abstrakten/logični pogled neodvisen od izvedbenega pogleda.
Opomba: Poznamo operacije, ki jih je mogoče izvesti na vnaprej določenih tipih podatkov, kot so int, float, char itd., vendar ne poznamo podrobnosti izvedbe podatkovnih tipov. Zato lahko rečemo, da se abstraktni podatkovni tip obravnava kot skrito polje, ki skriva vse notranje podrobnosti podatkovnega tipa.
Primer strukture podatkov
Recimo, da imamo indeksno matriko velikosti 4. Imamo indeksno lokacijo, ki se začne od 0, 1, 2, 3. Matrika je podatkovna struktura, kjer so elementi shranjeni na sosednji lokaciji. Naslov pomnilnika prvega elementa je 1000, drugega elementa 1004, tretjega elementa 1008 in četrtega elementa 1012. Ker je celoštevilskega tipa, bo zasedel 4 bajte in razlika med naslovi vsakega elementa je 4 bajtov. Vrednosti, shranjene v matriki, so 10, 20, 30 in 40. Te vrednosti, položaji indeksov in pomnilniški naslovi so implementacije.
Abstrakten ali logičen pogled na niz celih števil se lahko izrazi kot:
- Shranjuje nabor elementov celoštevilskega tipa.
- Elemente bere po položaju, tj. indeksu.
- Elemente spreminja po indeksu
- Izvaja sortiranje
Izvedbeni pogled matrike celih števil:
a[4] = {10, 20, 30, 40} cout<< a[2] a[3] = 50