Datu struktūras

Pamatdatu struktūras

Matu masīvs

Vienkāršākais datu struktūras tips ir lineārais masīvs. Zināms arī kā viendimensiju masīvs. Masīvā tiek saglabātas vairākas viena tipa vērtības (vesels skaitlis, peldošais skaitlis, virkne u. c.). Piekļuve elementiem masīvā ir ļoti ātra. Parasti masīvam ir fiksēts izmērs. Pēc tam, kad sākumā ir noteikts masīva lielums, var nebūt iespējams palielināt masīva lielumu, neizveidojot jaunu lielāku masīvu un neiekopējot visas vērtības jaunajā masīvā. Datorzinātnē masīva datu struktūra vai vienkārši masīvs ir datu struktūra, kas sastāv no elementu (vērtību vai mainīgo) kopuma, no kuriem katru identificē ar vismaz vienu masīva indeksu vai atslēgu. Masu glabā tā, lai katra elementa pozīciju varētu aprēķināt no tā indeksa kopas ar matemātisku formulu.

Piemēram, 10 veselu skaitļu mainīgo masīvu ar indeksiem no 0 līdz 9 var saglabāt kā 10 vārdus atmiņas adresēs 2000, 2004, 2008, 2036, lai elementam ar indeksu i būtu adrese 2000 + 4 × i.

Tā kā matricas matemātisko jēdzienu var attēlot kā divdimensiju režģi, divdimensiju masīvus dažkārt sauc arī par matricām. Dažos gadījumos skaitļošanas tehnikā tiek lietots termins "vektors", lai apzīmētu matricu, lai gan matemātiski pareizāk ir lietot tuples, nevis vektorus. Masīvus bieži izmanto, lai ieviestu tabulas, jo īpaši meklēšanas tabulas; vārdu "tabula" dažkārt lieto kā sinonīmu vārdam "masīvs".

Matu masīvi ir viena no senākajām un svarīgākajām datu struktūrām, un tos izmanto gandrīz katra programma. Tos var izmantot arī daudzu citu datu struktūru, piemēram, sarakstu un virkņu, ieviešanai. Tie efektīvi izmanto datoru adresācijas loģiku. Lielākajā daļā mūsdienu datoru un daudzās ārējās atmiņas ierīcēs atmiņa ir viendimensiju vārdu masīvs, kura indeksi ir to adreses. Procesori, īpaši vektoru procesori, bieži ir optimizēti masīvu operācijām.

Māri ir noderīgi, jo elementu indeksus var aprēķināt darbības laikā. Šī īpašība cita starpā ļauj ar vienu iteratīvo izteikumu apstrādāt patvaļīgi daudz masīva elementu. Šā iemesla dēļ masīva datu struktūras elementiem ir jābūt vienāda lieluma, un tiem ir jāizmanto viena un tā pati datu reprezentācija. Derīgo indeksu kopu kopa un elementu adreses (un līdz ar to arī elementu adresēšanas formula) parasti, bet ne vienmēr, ir fiksētas, kamēr masīvs tiek izmantots.

Terminu masīvs bieži lieto, lai apzīmētu masīva datu tipu - datu tipu, ko nodrošina lielākā daļa augsta līmeņa programmēšanas valodu un kas sastāv no vērtību vai mainīgo kopuma, ko var atlasīt pēc viena vai vairākiem izpildes laikā aprēķinātiem indeksiem. Matu tipus bieži īsteno ar masīvu struktūrām, tomēr dažās valodās tos var īstenot ar heš tabulām, saistītiem sarakstiem, meklēšanas kokiem vai citām datu struktūrām.

Saistītais saraksts

Saistīto datu struktūra ir informācijas/datu kopums, kas savstarpēji saistīts ar atsaucēm. Datus bieži sauc par mezgliem. Atsauces bieži sauc par saitēm vai norādēm. Turpmāk šiem jēdzieniem tiks lietoti vārdi mezgls un rādītājs.

Saistītajās datu struktūrās rādītāji tiek tikai atsaukti vai salīdzināti, lai noteiktu vienlīdzību. Tādējādi saistītās datu struktūras atšķiras no masīviem, kuros rādītājus nepieciešams saskaitīt un atņemt.

Saistītie saraksti, meklēšanas koki un izteiksmes koki ir saistītas datu struktūras. Tās ir svarīgas arī tādos algoritmos kā topoloģiskā šķirošana un kopu apvienojumu meklēšana.

Steks

Kaudze ir datu pamatstruktūra, ko loģiski var uzskatīt par lineāru struktūru, ko attēlo reāla fiziska kaudze jeb kaudze, struktūra, kurā elementu ievietošana un dzēšana notiek vienā kaudzes galā, ko sauc par kaudzes virsmu. Šo pamatjēdzienu var ilustrēt, iedomājoties datu kopu kā šķīvju vai grāmatu kaudzi, no kuras var izņemt tikai augšējo elementu, lai no tās izņemtu lietas. Šī struktūra tiek izmantota visā programmēšanas procesā.

Steka pamatrealizācija tiek saukta arī par "Last In First Out" struktūru, tomēr ir dažādi steka implementācijas varianti.

Ar kaudzēm var veikt trīs darbības. Tās ir:

• elementa ievietošana ("iebīdīšana") kaudzē
• elementa izdzēšana ("izņemšana") no kaudzes.
• kaudzes augšējā elementa satura rādīšana ("ieskatīšanās").

Rinda

Rinda ir abstrakts datu tips jeb lineāra datu struktūra, kurā pirmais elements tiek ievietots no viena gala ("astes"), bet esošā elementa dzēšana notiek no otra gala ("galvas"). Rinda ir struktūra, kas darbojas pēc principa "pirmais iekšā, pirmais ārā". "First In First Out" nozīmē, ka elementi, kas rindā ievietoti pirmie, iziet pirmie, bet elementi, kas rindā ievietoti pēdējie, iziet pēdējie. Rindu piemēri ir rindas, kurās gaida cilvēki. Pirmais cilvēks rindā iet pirmais, bet pēdējais rindā - pēdējais.

Elementa pievienošanu rindai sauc par "pievienošanu rindā", bet elementa noņemšanu no rindas - par "noņemšanu no rindas".

Grafiks

Grafs ir abstrakts datu tips, kas paredzēts matemātikas grafiku un hipergrafu jēdzienu īstenošanai.

Grafa datu struktūru veido galīgs (un, iespējams, mainīgs) sakārtotu pāru kopums, ko sauc par malām jeb lokiem, no noteiktām vienībām, ko sauc par mezgliem jeb virsotnēm. Tāpat kā matemātikā, par malu (x,y) saka, ka tā norāda vai iet no x uz y. Mezgli var būt daļa no grafa struktūras vai ārējas vienības, ko attēlo veselu skaitļu indeksi vai atsauces. Grafa datu struktūra var arī saistīt ar katru malu kādu malas vērtību, piemēram, simbolisku marķējumu vai skaitlisku atribūtu.

Koks

Koks ir viena no spēcīgākajām datu struktūrām. Tā bieži parādās tādos progresīvos mācību priekšmetos kā mākslīgais intelekts (AI) un dizains. Pārsteidzoši, ka koks ir svarīgs daudz vienkāršākā lietojumā - efektīva indeksa uzturēšanā.

Ja tiek izmantots koks, pastāv liela iespēja, ka tiek izmantots indekss. Vienkāršākais indeksa veids ir sakārtots atslēgas lauku saraksts. Kokam parasti ir noteikta struktūra. Bināra koka gadījumā var izmantot bināro meklēšanu, lai atrastu jebkuru elementu, neapskatot katru elementu.

Koku datu tips ir grafika tips, kas nozīmē, ka daudzi algoritmi, kas izveidoti, lai šķērsotu grafiku, darbojas arī ar koku, tomēr algoritmi var būt ļoti līdzīgi, un tiem ir jābūt īpašam sākuma mezglam, t. i., mezglam, kuram nav citu mezglu, kas to savieno.

Problēma ar vienkāršu sakārtotu sarakstu rodas tad, kad sākat pievienot jaunus elementus un saraksts ir jāsaglabā sakārtots - to var izdarīt samērā efektīvi, bet ir nepieciešamas dažas modifikācijas. Turklāt lineāro indeksu nav viegli kopīgot, jo, vienam lietotājam to rediģējot, ir "jānofiksē" viss indekss, turpretī vienu koka "zaru" var nofiksēt, atstājot pārējos zarus rediģējamus citiem lietotājiem (jo tos nevar ietekmēt).

Hash tabula

Hešgrāfa tabula ir masīvs, kurā katrs indekss norāda uz saistīto sarakstu, pamatojoties uz heša vērtību. Hašvērtība ir vērtība, ko nosaka ar hašēšanas funkciju. Hēša funkcija nosaka unikālu vērtību, pamatojoties uz datiem, kurus tā glabā. Tas ļauj piekļūt datiem konstantā laikā, jo dators vienmēr zina, kur meklēt.

Katrs mezgls norāda uz citu mezglu.