Podatkovna struktura

Osnovne podatkovne strukture

Polje

Najpreprostejša vrsta podatkovne strukture je linearno polje. Znana je tudi kot enodimenzionalno polje. V polju je shranjenih več vrednosti iste vrste (celoštevilsko, plavajoče, vrstno itd.). Dostop do elementov v polju je zelo hiter. Polje ima običajno fiksno velikost. Ko je velikost polja določena na začetku, morda ne bo mogoče povečati velikosti polja, ne da bi ustvarili novo večje polje in kopirali vse vrednosti v novo polje. V računalništvu je podatkovna struktura polja ali preprosto polje podatkovna struktura, sestavljena iz zbirke elementov (vrednosti ali spremenljivk), od katerih je vsak označen z vsaj enim indeksom ali ključem polja. Polje je shranjeno tako, da je mogoče položaj vsakega elementa izračunati iz njegovega indeksa s pomočjo matematične formule.

Na primer, polje 10 celoštevilskih spremenljivk z indeksi od 0 do 9 je lahko shranjeno kot 10 besed na pomnilniških naslovih 2000, 2004, 2008, 2036, tako da ima element z indeksom i naslov 2000 + 4 × i.

Ker je matematični koncept matrike mogoče predstaviti kot dvodimenzionalno mrežo, se dvodimenzionalnim poljem včasih reče tudi matrike. V nekaterih primerih se v računalništvu za matriko uporablja izraz "vektor", čeprav so matematično pravilnejši ekvivalent tuple in ne vektorji. Polja se pogosto uporabljajo za implementacijo tabel, zlasti pregledovalnih tabel; beseda tabela se včasih uporablja kot sopomenka za polje.

Matrike so med najstarejšimi in najpomembnejšimi podatkovnimi strukturami in jih uporablja skoraj vsak program. Uporabljamo jih lahko tudi za implementacijo številnih drugih podatkovnih struktur, kot so seznami in nizi. Učinkovito izkoriščajo logiko naslavljanja računalnikov. V večini sodobnih računalnikov in številnih zunanjih pomnilniških napravah je pomnilnik enodimenzionalno polje besed, katerih indeksi so njihovi naslovi. Procesorji, zlasti vektorski, so pogosto optimizirani za operacije z matrikami.

Matrike so uporabne, ker lahko indekse elementov izračunamo med izvajanjem. Ta lastnost med drugim omogoča, da se z eno iterativno izjavo obdela poljubno veliko elementov polja. Zato morajo biti elementi podatkovne strukture polja enako veliki in morajo uporabljati enako predstavitev podatkov. Nabor veljavnih indeksnih kretnic in naslovi elementov (ter s tem formula za naslavljanje elementov) so običajno, vendar ne vedno, med uporabo polja fiksni.

Izraz array se pogosto uporablja za podatkovni tip array, vrsto podatkovnega tipa, ki ga ponuja večina visokozmogljivih programskih jezikov in je sestavljen iz zbirke vrednosti ali spremenljivk, ki jih je mogoče izbrati z enim ali več indeksi, izračunanimi med izvajanjem. Tipi polj so pogosto izvedeni s strukturami polj, v nekaterih jezikih pa so lahko izvedeni s hash tabelami, povezanimi seznami, iskalnimi drevesi ali drugimi podatkovnimi strukturami.

Povezani seznam

Povezana podatkovna struktura je niz informacij/podatkov, ki so med seboj povezani z referencami. Podatki se pogosto imenujejo vozlišča. Reference se pogosto imenujejo povezave ali kazalci. Od tu naprej bomo za ta pojma uporabljali besedi vozlišče in kazalec.

V povezanih podatkovnih strukturah se kazalci le sklicujejo ali primerjajo za enakost. Tako se povezane podatkovne strukture razlikujejo od matrik, ki zahtevajo dodajanje in odvzemanje kazalnikov.

Povezani seznami, iskalna drevesa in izrazna drevesa so povezane podatkovne strukture. Pomembne so tudi v algoritmih, kot sta topološko razvrščanje in iskanje zvez množic.

Stack

Sklad je osnovna podatkovna struktura, ki jo lahko logično razumemo kot linearno strukturo, ki jo predstavlja dejanski fizični sklad ali kup, struktura, v kateri vstavljanje in brisanje elementov poteka na enem koncu, imenovanem vrh sklada. Osnovni koncept lahko ponazorimo tako, da si svoj nabor podatkov predstavljamo kot kup krožnikov ali knjig, pri čemer lahko s kupa vzamemo le zgornji element, da bi z njega odstranili stvari. Ta struktura se uporablja v celotnem programiranju.

Osnovna izvedba sklada se imenuje tudi struktura "Last In First Out", vendar obstajajo različne različice izvedb sklada.

Na kupih je mogoče izvesti tri operacije. To so:

• vstavljanje ("potiskanje") elementa v kup
• brisanje ("izskočitev") elementa s kupa.
• prikazovanje vsebine zgornjega elementa na kupu ("pokukanje").

Vrstni red

Vrstni red je abstraktni podatkovni tip ali linearna podatkovna struktura, v katero se prvi element vstavi z enega konca ("rep"), brisanje obstoječega elementa pa poteka z drugega konca ("glava"). Vrstni red je struktura "prvi noter, prvi ven". "First In First Out" pomeni, da bodo elementi, ki so v čakalno vrsto vstavljeni prvi, iz nje prišli prvi, elementi, ki so v čakalno vrsto vstavljeni zadnji, pa bodo iz nje prišli zadnji. Primer čakalne vrste so vrste čakajočih ljudi. Prva oseba v vrsti gre prva, zadnja oseba v vrsti pa zadnja.

Postopek dodajanja elementa v čakalno vrsto se imenuje "vpisovanje", postopek odstranjevanja elementa iz čakalne vrste pa "odstranjevanje".

Graf

Graf je abstraktni podatkovni tip, ki je namenjen izvajanju konceptov grafov in hipergrafov iz matematike.

Podatkovno strukturo grafa sestavlja končna (in po možnosti spremenljiva) množica urejenih parov, imenovanih robovi ali loki, določenih entitet, imenovanih vozlišča ali vrhovi. Kot v matematiki se za rob (x,y) reče, da kaže ali gre od x do y. Vozlišča so lahko del grafne strukture ali pa so zunanje entitete, ki jih predstavljajo celoštevilski indeksi ali reference. Podatkovna struktura grafa lahko vsakemu robu pripiše tudi neko vrednost roba, na primer simbolno oznako ali številčni atribut.

Drevo

Drevo je ena najmočnejših naprednih podatkovnih struktur. Pogosto se pojavlja pri naprednih predmetih, kot sta umetna inteligenca in oblikovanje. Presenetljivo pa je drevo pomembno tudi pri veliko bolj osnovni uporabi - vodenju učinkovitega indeksa.

Pri uporabi drevesa je velika verjetnost, da je uporabljen indeks. Najpreprostejša vrsta indeksa je razvrščen seznam ključnih polj. Drevo ima običajno določeno strukturo. V primeru binarnega drevesa lahko z binarnim iskanjem poiščete katero koli postavko, ne da bi morali pregledati vsako postavko.

Podatkovni tip drevo je vrsta grafa, kar pomeni, da številni algoritmi za premikanje po grafu delujejo tudi z drevesom, vendar so lahko algoritmi zelo podobni in morajo imeti namensko začetno vozlišče, tj. vozlišče, ki nima drugih vozlišč, ki bi se nanj povezovala.

Težava z enostavnim urejenim seznamom nastane, ko začnete dodajati nove elemente in morate poskrbeti, da je seznam razvrščen - to lahko storite dokaj učinkovito, vendar je potrebnih nekaj sprememb. Poleg tega linearnega indeksa ni enostavno deliti, saj je treba celoten indeks "zakleniti", ko ga en uporabnik ureja, medtem ko je mogoče zakleniti eno "vejo" drevesa, pri čemer ostale veje lahko urejajo drugi uporabniki (saj nanje ni mogoče vplivati).

Tabela Hash

Hash tabela je polje, v katerem vsak indeks kaže na povezan seznam, ki temelji na vrednosti hash. Vrednost hash je vrednost, določena s funkcijo hash. Funkcija hash določi edinstveno vrednost na podlagi podatkov, ki jih shranjuje. To omogoča dostop do podatkov v konstantnem času, saj računalnik vedno ve, kje naj jih išče.

Vsako vozlišče kaže na drugo vozlišče.