Duomenų struktūra

Pagrindinės duomenų struktūros

Masyvas

Paprasčiausia duomenų struktūra yra linijinis masyvas. Dar vadinama vienmatžiu masyvu. Masyve saugomos kelios to paties tipo reikšmės (sveikieji skaičiai, kintamieji, eilutės ir t. t.). Prieiga prie masyvo elementų yra labai greita. Paprastai masyvas yra fiksuoto dydžio. Pradžioje nustačius masyvo dydį, gali būti neįmanoma padidinti masyvo dydžio nesukūrus naujo didesnio masyvo ir nenukopijavus visų reikšmių į naująjį masyvą. Informatikoje masyvo duomenų struktūra arba tiesiog masyvas yra duomenų struktūra, sudaryta iš elementų (verčių arba kintamųjų) rinkinio, kurių kiekvienas identifikuojamas bent vienu masyvo indeksu arba raktu. Masyvas saugomas taip, kad kiekvieno elemento padėtį būtų galima apskaičiuoti pagal jo indekso tuple pagal matematinę formulę.

Pavyzdžiui, 10 sveikųjų skaičių kintamųjų masyvą su indeksais nuo 0 iki 9 galima saugoti kaip 10 žodžių atminties adresais 2000, 2004, 2008, 2036, kad elementas su indeksu i turėtų adresą 2000 + 4 × i.

Kadangi matematinę matricos sąvoką galima pavaizduoti kaip dvimatį tinklelį, dvimatės matricos taip pat kartais vadinamos matricomis. Kai kuriais atvejais skaičiavimuose naudojamas terminas "vektorius", reiškiantis matricą, nors teisingesnis matematinis atitikmuo yra ne vektoriai, o tupliai. Masyvai dažnai naudojami lentelėms, ypač paieškos lentelėms, įgyvendinti; žodis lentelė kartais vartojamas kaip masyvo sinonimas.

Masyvai yra viena iš seniausių ir svarbiausių duomenų struktūrų, kuri naudojama beveik kiekvienoje programoje. Jie taip pat gali būti naudojami daugeliui kitų duomenų struktūrų, pavyzdžiui, sąrašams ir eilutėms, įgyvendinti. Jie veiksmingai išnaudoja kompiuterių adresavimo logiką. Daugumoje šiuolaikinių kompiuterių ir daugelyje išorinių atminties įrenginių atmintis yra vienmatis žodžių masyvas, kurio indeksai yra jų adresai. Procesoriai, ypač vektoriniai procesoriai, dažnai optimizuojami darbui su masyvais.

Masyvai yra naudingi, nes elementų indeksus galima apskaičiuoti paleidimo metu. Be kita ko, ši savybė leidžia vienu iteraciniu teiginiu apdoroti bet kokį skaičių masyvo elementų. Dėl šios priežasties reikalaujama, kad masyvo duomenų struktūros elementai būtų vienodo dydžio ir turėtų naudoti tą patį duomenų atvaizdavimą. Galiojančių indekso taškų rinkinys ir elementų adresai (taigi ir elementų adresavimo formulė) paprastai, bet ne visada, yra fiksuoti, kol masyvas yra naudojamas.

Terminas "masyvas" dažnai vartojamas kalbant apie masyvo duomenų tipą - daugumos aukšto lygio programavimo kalbų duomenų tipą, kurį sudaro reikšmių arba kintamųjų rinkinys, kurį galima pasirinkti pagal vieną ar daugiau indeksų, apskaičiuojamų vykdymo metu. Masyvo tipai dažnai įgyvendinami masyvų struktūromis, tačiau kai kuriose kalbose jie gali būti įgyvendinami hash lentelėmis, susietais sąrašais, paieškos medžiais ar kitomis duomenų struktūromis.

Susietasis sąrašas

Susietoji duomenų struktūra - tai informacijos ir (arba) duomenų rinkinys, susietas nuorodomis. Duomenys dažnai vadinami mazgais. Nuorodos dažnai vadinamos nuorodomis arba rodyklėmis. Toliau šioms sąvokoms įvardyti bus vartojami žodžiai mazgas ir rodyklė.

Susietosiose duomenų struktūrose rodyklės tik iš naujo nurodomos arba lyginamos dėl lygybės. Taigi susietosios duomenų struktūros skiriasi nuo masyvų, kuriuose reikia pridėti ir atimti rodykles.

Susieti sąrašai, paieškos medžiai ir išraiškos medžiai yra susietosios duomenų struktūros. Jos taip pat svarbios tokiuose algoritmuose kaip topologinis rūšiavimas ir aibių sąjungos paieška.

Stack

Stekas yra pagrindinė duomenų struktūra, kurią logiškai galima laikyti linijine struktūra, vaizduojama tikru fiziniu steku arba krūva, struktūra, kurioje elementų įterpimas ir ištrynimas vyksta viename iš steko galų, vadinamame steko viršuje. Pagrindinę sąvoką galima iliustruoti įsivaizduojant savo duomenų rinkinį kaip plokščių ar knygų krūvą, iš kurios galima išimti tik viršutinį elementą, kad būtų galima pašalinti daiktus iš krūvos. Ši struktūra naudojama visame programavime.

Pagrindinė kamino realizacija taip pat vadinama struktūra "paskutinis įeina, pirmas išeina", tačiau yra įvairių kamino realizacijos variantų.

Iš esmės su krūvomis galima atlikti tris operacijas. Tai:

• elemento įterpimas ("stūmimas") į steką
• elemento pašalinimas ("iššokimas") iš krūvos.
• viršutinio krūvos elemento turinio rodymas ("žvilgtelėjimas").

Eilė

Eilė yra abstraktus duomenų tipas arba linijinė duomenų struktūra, į kurią pirmasis elementas įterpiamas iš vieno galo ("uodega"), o esamas elementas ištrinamas iš kito galo ("galva"). Eilė yra struktūra "pirmas įeina, pirmas išeina". "Pirmas įeina, pirmas išeina" reiškia, kad elementai, į eilę įdėti pirmieji, išeina pirmieji, o elementai, į eilę įdėti paskutiniai, išeina paskutiniai. Eilės pavyzdys - laukiančių žmonių eilės. Pirmasis eilėje laukiantis asmuo eina pirmas, o paskutinis - paskutinis.

Elemento įtraukimas į eilę vadinamas įtraukimu į eilę, o elemento pašalinimas iš eilės - pašalinimu iš eilės.

Grafikas

Grafas yra abstraktus duomenų tipas, skirtas matematikos grafų ir hipergrafų sąvokoms įgyvendinti.

Grafo duomenų struktūrą sudaro baigtinė (ir galimai kintanti) tam tikrų esybių, vadinamų mazgais arba viršūnėmis, sutvarkytų porų, vadinamų briaunomis arba alkūnėmis, aibė. Kaip ir matematikoje, sakoma, kad briauna (x,y) rodo arba eina iš x į y. Mazgai gali būti grafo struktūros dalis arba gali būti išorinės esybės, vaizduojamos sveikųjų skaičių indeksais arba nuorodomis. Grafo duomenų struktūroje kiekvienai briaunai taip pat gali būti priskirta tam tikra briaunos vertė, pavyzdžiui, simbolinė etiketė arba skaitinis atributas.

Medis

Medis yra viena iš galingiausių pažangių duomenų struktūrų. Jis dažnai pasitaiko tokiuose pažangiuose dalykuose kaip dirbtinis intelektas (DI) ir dizainas. Keista, bet medis yra svarbus ir daug paprastesniam taikymui - veiksmingam indeksui išlaikyti.

Kai naudojamas medis, yra didelė tikimybė, kad bus naudojamas indeksas. Paprasčiausias indekso tipas yra surūšiuotas pagrindinių laukų sąrašas. Medis paprastai turi apibrėžtą struktūrą. Dvejetainio medžio atveju galima naudoti dvejetainę paiešką, kad surastumėte bet kurį elementą, neperžiūrėdami kiekvieno elemento.

Medžio duomenų tipas yra grafo tipas, o tai reiškia, kad daugelis algoritmų, sukurtų grafui kirsti, taip pat veikia su medžiu, tačiau algoritmai gali būti labai panašūs ir turi turėti specialų pradinį mazgą, t. y. mazgą, su kuriuo nesusiję jokie kiti mazgai.

Paprasto sutvarkyto sąrašo problema kyla tada, kai pradedate pridėti naujų elementų ir turite išlaikyti sąrašo rūšiavimą - tai galima padaryti gana efektyviai, tačiau reikia tam tikrų pakeitimų. Be to, tiesiniu indeksu nelengva dalytis, nes visą indeksą reikia "užrakinti", kai vienas naudotojas jį redaguoja, o medžio "šaką" galima užrakinti, o kitas šakas kiti naudotojai gali redaguoti (nes jos negali būti paveiktos).

"Hash" lentelė

Hešinė lentelė - tai masyvas, kurio kiekvienas indeksas nurodo į susietąjį sąrašą, sudarytą pagal hešo reikšmę. Hašo reikšmė - tai reikšmė, nustatyta hašo funkcija. Hašo funkcija nustato unikalią vertę pagal saugomus duomenis. Tai leidžia pasiekti duomenis per pastovų laiką, nes kompiuteris visada žino, kur ieškoti.

Kiekvienas mazgas nurodo į kitą mazgą.