Andmestruktuur

Põhilised andmestruktuurid

Array

Lihtsaim andmestruktuuri tüüp on lineaarne massiivi. Tuntud ka kui ühemõõtmeline massiivi. Massiivis hoitakse mitut sama tüüpi väärtust (täisarv, ujukesed, string jne). Juurdepääs elementidele massiivi sees on väga kiire. Massiiv on tavaliselt fikseeritud suurusega. Pärast seda, kui massiivi suurus on alguses kindlaks määratud, ei pruugi olla võimalik massiivi suurust suurendada ilma uue suurema massiivi loomiseta ja kõigi väärtuste kopeerimiseta uude massiivi. Arvutiteaduses on massiivi andmestruktuur või lihtsalt massiiv andmestruktuur, mis koosneb elementide (väärtuste või muutujate) kogumist, millest igaüht identifitseerib vähemalt üks massiivi indeks või võti. Massiiv salvestatakse nii, et iga elemendi positsiooni saab arvutada selle indeksitupli põhjal matemaatilise valemi abil.

Näiteks 10 täisarvulise muutuja massiivi, mille indeksid on 0 kuni 9, võib salvestada 10 sõnana mäluaadressidel 2000, 2004, 2008, 2036, nii et indeksiga i elemendi aadressiks on 2000 + 4 × i.

Kuna maatriksi matemaatilist mõistet saab esitada kahemõõtmelise ruudustikuna, nimetatakse kahemõõtmelisi massiive mõnikord maatriksiteks. Mõnel juhul kasutatakse arvutustehnikas massiivi tähistamiseks terminit "vektor", kuigi matemaatiliselt on korrektsem ekvivalent pigem tuplid kui vektorid. Massiivide abil rakendatakse sageli tabeleid, eriti otsingutabeleid; sõna tabel kasutatakse mõnikord massiivide sünonüümina.

Massiivid on üks vanimaid ja tähtsamaid andmestruktuure, mida kasutatakse peaaegu igas programmis. Neid saab kasutada ka paljude teiste andmestruktuuride, näiteks loetelude ja stringide rakendamiseks. Nad kasutavad tõhusalt ära arvutite adresseerimisloogikat. Enamikus kaasaegsetes arvutites ja paljudes välismäluseadmetes on mälu ühemõõtmeline sõnade massiivi, mille indeksid on nende aadressid. Protsessorid, eriti vektorprotsessorid, on sageli optimeeritud massiivioperatsioonideks.

Massiivid on kasulikud, sest elementide indeksid saab arvutada töö ajal. Muu hulgas võimaldab see omadus ühe iteratiivse avaldusega töödelda suvaliselt palju massiivi elemente. Sel põhjusel peavad massiivi andmestruktuuri elemendid olema ühesuurused ja kasutama ühesugust andmeesitust. Kehtivate indeksituplite hulk ja elementide aadressid (ja seega ka elementide adresseerimisvalem) on tavaliselt, kuid mitte alati, massiivi kasutamise ajal fikseeritud.

Mõiste massiivi all mõistetakse sageli massiivi andmetüüpi, mis on enamikus kõrgetasemelistes programmeerimiskeeltes pakutav andmetüüp, mis koosneb väärtuste või muutujate kogumist, mida saab valida ühe või mitme indeksi abil, mis arvutatakse töö ajal. Massiivi tüüpe rakendatakse sageli massiivi struktuuride abil; mõnes keeles võib neid siiski rakendada ka hash-tabelite, lingitud loendite, otsingupuude või muude andmestruktuuride abil.

Seotud nimekiri

Seotud andmestruktuur on teabe/andmete kogum, mis on omavahel seotud viidetega. Andmeid nimetatakse sageli sõlmedeks. Viiteid nimetatakse sageli linkideks või osutajateks. Edaspidi kasutatakse nende mõistete kohta sõnu sõlme ja osuti.

Seotud andmestruktuurides tuletatakse osutajaid ainult või võrreldakse neid võrdsuse suhtes. Seega erinevad seotud andmestruktuurid massiividest, mis nõuavad osutajate liitmist ja lahutamist.

Seotud loetelud, otsingupuud ja väljendipuud on kõik seotud andmestruktuurid. Need on olulised ka sellistes algoritmides nagu topoloogiline sorteerimine ja kogumiühenduste leidmine.

Stack

Korstnat on põhiline andmestruktuur, mida saab loogiliselt mõelda lineaarse struktuurina, mida kujutab endast reaalne füüsiline korstnat või virna, struktuur, mille ühes otsas, mida nimetatakse korstna tipuks, toimub elementide sisestamine ja kustutamine. Põhimõistet saab illustreerida, kui mõelda oma andmekogumile kui taldrikute või raamatute virnale, kust saab eemaldada asju ainult virnast ülemise elemendi. Seda struktuuri kasutatakse kogu programmeerimisel.

Korstna põhilist rakendust nimetatakse ka "Last In First Out" struktuuriks; siiski on olemas erinevaid variante korstna rakendustest.

Põhimõtteliselt on kolm operatsiooni, mida saab teha virnadega. Need on järgmised:

• elemendi sisestamine ("lükkamine") virna
• elemendi kustutamine ("popping") virnast.
• virna ülemise elemendi sisu kuvamine ("piilumine")

Järjekord

Järjekord on abstraktne andmetüüp või lineaarne andmestruktuur, kus esimene element sisestatakse ühest otsast ("saba") ja olemasoleva elemendi kustutamine toimub teisest otsast ("pea"). Järjekord on "First In First Out" struktuur. "First In First Out" tähendab, et elemendid, mis pannakse järjekorda esimesena, tulevad esimesena välja ja elemendid, mis pannakse järjekorda viimasena, tulevad viimasena välja. Järjekorra näide on järjekorrad, kus inimesed ootavad. Esimene inimene järjekorras läheb esimesena ja viimane inimene järjekorras viimasena.

Elemendi lisamist järjekorda nimetatakse "järjekorda seadmiseks" ja elemendi eemaldamist järjekorrast nimetatakse "järjekorrast eemaldamiseks".

Graafik

Graaf on abstraktne andmetüüp, mis on mõeldud matemaatikast pärit graafi ja hüpergraafi mõistete rakendamiseks.

Graafi andmestruktuur koosneb piiratud (ja võimalik, et muutuv) hulk järjestatud paaridest, mida nimetatakse servadeks või kaaredeks, ja teatud üksustest, mida nimetatakse sõlmedeks või tipudeks. Nagu matemaatikas, öeldakse, et serv (x,y) näitab või läheb x-st y-sse. Sõlmed võivad olla osa graafistruktuurist või olla välised üksused, mida esindavad täisarvulised indeksid või viited. Graafi andmestruktuur võib seostada igale servale ka mingi serva väärtuse, näiteks sümboolse märgistuse või numbrilise atribuudi.

Puu

Puu on üks võimsamaid arenenud andmestruktuure. See esineb sageli arenenud teemades, nagu tehisintellekt (AI) ja disain. Üllataval kombel on puu oluline ka palju lihtsamas rakenduses - tõhusa indeksi pidamisel.

Puu kasutamisel on suur tõenäosus, et kasutatakse indeksit. Lihtsaim indeksitüüp on võtmeväljade sorteeritud loetelu. Puu on tavaliselt kindla struktuuriga. Binaarse puu puhul saab kasutada binaarset otsingut, et leida mis tahes element, ilma et oleks vaja vaadata iga elementi.

Puu andmetüüp on graafi tüüp, mis tähendab, et paljud algoritmid, mis on tehtud graafi läbimiseks, töötavad ka puu abil, kuid algoritmid võivad olla palju sarnased ja neil peab olema spetsiaalne algussõlm, st sõlme, millel ei ole teisi sõlmi, mis seda ühendavad.

Lihtsa järjestatud loendi probleem tekib siis, kui hakkate uusi elemente lisama ja peate loendit sorteerituna hoidma - seda saab teha küllaltki tõhusalt, kuid see nõuab mõningaid muudatusi. Lisaks ei ole lineaarset indeksit lihtne jagada, sest kogu indeks tuleb "lukustada", kui üks kasutaja seda redigeerib, samas kui puu ühe "haru" saab lukustada, jättes teised harud teistele kasutajatele redigeeritavaks (kuna neid ei saa mõjutada).

Hash tabel

Räsitabel on massiiv, kus iga indeks osutab räsiväärtusel põhinevale lingitud loendile. Hash-väärtus on väärtus, mis on määratud hash-funktsiooni abil. Hash-funktsioon määrab unikaalse väärtuse salvestatavate andmete põhjal. See võimaldab juurdepääsu andmetele konstantse ajaga, sest arvuti teab alati, kust otsida.

Iga sõlm osutab teisele sõlmpunktile.