6 duomenų struktūros, kurias turėtų žinoti kiekvienas programuotojas

Kelias tapti įgudusiu ir sėkmingu programuotoju yra sunkus, bet tikrai pasiekiamas. Duomenų struktūros yra pagrindinis komponentas, kurį turi įvaldyti kiekvienas programavimo studentas, ir tikėtina, kad jau išmokote arba dirbote su kai kuriomis pagrindinėmis duomenų struktūromis, tokiomis kaip masyvai ar sąrašai.

Interviuotojai dažniausiai teikia pirmenybę klausimų, susijusių su duomenų struktūromis, taigi, jei ruošiatės darbo pokalbiui, turėsite pagyvinti savo žinias apie duomenų struktūras. Skaitykite toliau, kai išvardijame svarbiausias programuotojų ir darbo pokalbių duomenų struktūras.

Susieti sąrašai yra viena iš pagrindinių duomenų struktūrų ir dažnai yra daugelio duomenų struktūrų kursų studentų atspirties taškas. Susieti sąrašai yra linijinės duomenų struktūros, leidžiančios nuosekliai pasiekti duomenis.

Susieto sąrašo elementai saugomi atskiruose mazguose, kurie yra sujungti (susieti) naudojant rodykles. Galite galvoti apie susietą sąrašą kaip mazgų, sujungtų vienas su kitu skirtingais rodyklėmis, grandinę.

Susijęs: Susietų sąrašų naudojimo Java programoje įvadas

Prieš pradedant susipažinti su skirtingų tipų susietų sąrašų specifika, labai svarbu suprasti atskiro mazgo struktūrą ir įgyvendinimą. Kiekvienas susieto sąrašo mazgas turi bent vieną rodyklę (dvigubai susieti sąrašo mazgai turi dvi rodykles), jungiančią jį su kitu sąrašo mazgu ir pačiu duomenų elementu.

Kiekvienas susietas sąrašas turi galvos ir uodegos mazgus. Vienu susietuose sąrašo mazguose yra tik vienas žymeklis, nukreipiantis į kitą grandinės mazgą. Be kito rodyklės, dvigubai susieti sąrašo mazgai turi kitą rodyklę, nukreipiančią į ankstesnį grandinės mazgą.

Interviu klausimai, susiję su susietais sąrašais, paprastai sukasi apie konkretaus elemento įterpimą, paiešką ar ištrynimą. Įterpimas į susietą sąrašą užtrunka O(1) laiko, bet ištrynimas ir paieška gali užtrukti O(n) blogiausiu atveju. Taigi susieti sąrašai nėra idealūs.

2. Dvejetainis medis

Dvejetainiai medžiai yra populiariausias medžių šeimos duomenų struktūros poaibis; dvejetainio medžio elementai yra išdėstyti hierarchija. Kiti medžių tipai yra AVL, raudonai juodi, B medžiai ir kt. Dvejetainio medžio mazguose yra duomenų elementas ir dvi rodyklės į kiekvieną antrinį mazgą.

Kiekvienas dvejetainio medžio pirminis mazgas gali turėti daugiausia du antrinius mazgus, o kiekvienas antrinis mazgas savo ruožtu gali būti dviejų mazgų pirminis mazgas.

Susijęs: Dvejetainių medžių vadovas pradedantiesiems

Dvejetainis paieškos medis (BST) saugo duomenis surūšiuota tvarka, kur elementai, kurių rakto reikšmė mažesnė už pirminį mazgas yra saugomi kairėje, o elementai, kurių rakto reikšmė didesnė nei pirminio mazgo, yra saugomi teisingai.

Dvejetainiai medžiai dažniausiai klausiami interviu metu, taigi, jei ruošiatės pokalbiui, turėtumėte žinoti, kaip išlyginti dvejetainį medį, ieškoti konkretaus elemento ir kt.

3. Maišos lentelė

Maišos lentelės arba maišos žemėlapiai yra labai efektyvi duomenų struktūra, kurioje duomenys saugomi masyvo formatu. Kiekvienam duomenų elementui maišos lentelėje priskiriama unikali indekso reikšmė, kuri leidžia efektyviai ieškoti ir ištrinti.

Raktų priskyrimo arba susiejimo maišos žemėlapyje procesas vadinamas maišos nustatymu. Kuo efektyvesnė maišos funkcija, tuo geresnis pačios maišos lentelės efektyvumas.

Kiekvienoje maišos lentelėje duomenų elementai saugomi vertės ir indekso poroje.

Kur reikšmė yra saugomi duomenys, o indeksas yra unikalus sveikasis skaičius, naudojamas elementui priskirti lentelę. Maišos funkcijos gali būti labai sudėtingos arba labai paprastos, atsižvelgiant į reikiamą maišos lentelės efektyvumą ir tai, kaip išspręsite susidūrimus.

Kolizijos dažnai kyla, kai maišos funkcija sukuria tą patį skirtingų elementų atvaizdavimą; maišos žemėlapio susidūrimus galima išspręsti įvairiais būdais, naudojant atvirą adresavimą arba grandininį.

Maišos lentelės arba maišos žemėlapiai turi daugybę skirtingų programų, įskaitant kriptografiją. Jie yra pirmojo pasirinkimo duomenų struktūra, kai reikia įterpti arba ieškoti pastovaus O (1) laiko.

4. Krūvos

Stacks yra viena iš paprastesnių duomenų struktūrų ir jas gana lengva įsisavinti. Duomenų krūvos struktūra iš esmės yra bet kokia realaus gyvenimo krūva (pagalvokite apie dėžių ar plokščių krūvą) ir veikia LIFO (Last In First Out) būdu.

Stacks LIFO ypatybė reiškia, kad elementas, kurį įterpėte paskutinį kartą, bus pasiekiamas pirmiausia. Negalite pasiekti elementų, esančių žemiau viršutinio elemento krūvoje, nepakeldami elementų virš jo.

Stacks turi dvi pagrindines operacijas – stumti ir pop. „Push“ naudojamas elementui įterpti į krūvą, o „pop“ pašalina aukščiausią elementą iš krūvos.

Jie taip pat turi daug naudingų programų, todėl labai dažnai pašnekovai užduoda klausimus, susijusius su krūvomis. Labai svarbu žinoti, kaip apversti krūvą ir įvertinti išraiškas.

5. Eilės

Eilės yra panašios į krūvas, bet veikia FIFO (pirmas pirmas išeinantis) būdu, o tai reiškia, kad galite pasiekti elementus, kuriuos įterpėte anksčiau. Eilės duomenų struktūra gali būti vizualizuota kaip bet kokia reali eilė, kurioje žmonės yra išdėstyti pagal jų atvykimo tvarką.

Eilės įterpimo operacija vadinama eile, o elemento ištrynimas / pašalinimas iš eilės pradžios vadinamas ištraukimu iš eilės.

Susijęs: Eilių ir prioritetinių eilių supratimo vadovas pradedančiajam

Prioritetinės eilės yra neatsiejama eilių taikymas daugelyje svarbių programų, pvz., CPU planavimo. Prioritetinėje eilėje elementai išdėstomi pagal jų prioritetą, o ne pagal atvykimo tvarką.

6. Krūvos

Krūvos yra dvejetainio medžio tipas, kuriame mazgai yra išdėstyti didėjančia arba mažėjančia tvarka. Minimojoje krūvoje pagrindinė pirminio elemento reikšmė yra lygi arba mažesnė už jos antrinę vertę, o šakniniame mazge yra mažiausia visos krūvos reikšmė.

Panašiai Max Heap šakniniame mazge yra didžiausia krūvos rakto reikšmė; turite išlaikyti min/max krūvos savybę visoje krūvoje.

Susijęs: Krūvos vs. Stacks: kas juos skiria?

Krūvos turi daug pritaikymų dėl labai efektyvaus pobūdžio; pirmiausia prioritetinės eilės dažnai įgyvendinamos per krūvas. Jie taip pat yra pagrindinis krūvos rūšiavimo algoritmų komponentas.

Sužinokite duomenų struktūras

Duomenų struktūros iš pradžių gali atrodyti siaubingos, tačiau skirkite pakankamai laiko, todėl jas rasite kaip pyragą.

Jie yra gyvybiškai svarbi programavimo dalis, ir beveik kiekvienam projektui reikės juos naudoti. Labai svarbu žinoti, kokia duomenų struktūra yra ideali tam tikram scenarijui.

7 algoritmai, kuriuos turėtų žinoti kiekvienas programuotojas

Šie algoritmai yra būtini kiekvieno programuotojo darbo eigai.

Skaitykite toliau

Apie autorių