6 datu struktūras, kas jāzina katram programmētājam

Ceļš uz lietpratīgu un veiksmīgu programmētāju ir grūts, taču tas noteikti ir sasniedzams. Datu struktūras ir galvenā sastāvdaļa, kas jāapgūst katram programmēšanas studentam, un, iespējams, jūs jau esat apguvis vai strādājis ar dažām pamata datu struktūrām, piemēram, masīviem vai sarakstiem.

Intervētāji mēdz uzdot jautājumus, kas saistīti ar datu struktūrām, tādēļ, ja gatavojaties darba intervijai, jums būs jāpapildina savas zināšanas par datu struktūrām. Lasiet tālāk, kamēr mēs uzskaitām svarīgākās datu struktūras programmētājiem un darba intervijām.

Saistītie saraksti ir viena no visvienkāršākajām datu struktūrām un bieži vien ir sākumpunkts studentiem lielākajā daļā datu struktūru kursu. Saistītie saraksti ir lineāras datu struktūras, kas nodrošina secīgu piekļuvi datiem.

Saistītā saraksta elementi tiek glabāti atsevišķos mezglos, kas ir savienoti (saistīti), izmantojot norādes. Saistītu sarakstu var uzskatīt par mezglu ķēdi, kas savienoti viens ar otru, izmantojot dažādus rādītājus.

Saistīts: Ievads saistīto sarakstu izmantošanā Java

Pirms iedziļināties dažādu veidu saistīto sarakstu specifikā, ir ļoti svarīgi izprast atsevišķā mezgla struktūru un ieviešanu. Katram saistītā saraksta mezglam ir vismaz viens rādītājs (divkārši saistītiem saraksta mezgliem ir divi rādītāji), kas savieno to ar nākamo saraksta mezglu un pašu datu vienumu.

Katram saistītajam sarakstam ir galvas un astes mezgls. Vienam piesaistītiem saraksta mezgliem ir tikai viens rādītājs, kas norāda uz nākamo ķēdes mezglu. Papildus nākamajam rādītājam divkārši saistītiem saraksta mezgliem ir vēl viens rādītājs, kas norāda uz iepriekšējo ķēdes mezglu.

Intervijas jautājumi, kas saistīti ar saistītajiem sarakstiem, parasti ir saistīti ar konkrēta elementa ievietošanu, meklēšanu vai dzēšanu. Ievietošana saistītajā sarakstā aizņem O(1) laiku, bet dzēšana un meklēšana var aizņemt O(n) laiku sliktākajā gadījumā. Tāpēc saistītie saraksti nav ideāli.

2. Binārais koks

Binārie koki ir vispopulārākā koku saimes datu struktūras apakškopa; binārā koka elementi ir sakārtoti hierarhijā. Pie citiem koku veidiem pieder AVL, sarkanmelnie, B koki utt. Binārā koka mezglos ir datu elements un divi norādes uz katru pakārtoto mezglu.

Katram binārā koka vecākmezglam var būt ne vairāk kā divi pakārtotie mezgli, un katrs pakārtots mezgls savukārt var būt divu mezglu vecākais mezgls.

Saistīts: Bināro koku ceļvedis iesācējiem

Binārais meklēšanas koks (BST) saglabā datus sakārtotā secībā, kur elementi, kuru atslēgas vērtība ir mazāka par vecāku mezgls tiek glabāti kreisajā pusē, un elementi, kuru atslēgas vērtība ir lielāka par vecākmezglu, tiek glabāti taisnība.

Intervijās parasti uzdod jautājumus par binārajiem kokiem, tādēļ, ja gatavojaties intervijai, jums jāzina, kā saplacināt bināro koku, meklēt konkrētu elementu un veikt citas darbības.

3. Hash tabula

Jaukšanas tabulas vai jaucējkartes ir ļoti efektīva datu struktūra, kas glabā datus masīva formātā. Katram datu elementam ir piešķirta unikāla indeksa vērtība hash tabulā, kas ļauj efektīvi meklēt un dzēst.

Atslēgu piešķiršanas vai kartēšanas procesu jaukšanas kartē sauc par jaukšanu. Jo efektīvāka ir jaucējfunkcija, jo labāka ir pašas jaucēj tabulas efektivitāte.

Katra jaucēja tabula saglabā datu elementus vērtības indeksa pārī.

Kur vērtība ir saglabājamie dati, bet indekss ir unikāls vesels skaitlis, ko izmanto elementa kartēšanai tabulā. Jaucējfunkcijas var būt ļoti sarežģītas vai ļoti vienkāršas atkarībā no jaucēj tabulas nepieciešamās efektivitātes un tā, kā jūs atrisināsiet sadursmes.

Sadursmes bieži rodas, ja jaucējfunkcija rada vienu un to pašu kartējumu dažādiem elementiem; jaucējkartes sadursmes var atrisināt dažādos veidos, izmantojot atvērto adresāciju vai ķēdi.

Jaucējtabulām vai jaucējkartēm ir dažādas lietojumprogrammas, tostarp kriptogrāfija. Tie ir pirmās izvēles datu struktūra, kad ir nepieciešama ievietošana vai meklēšana nemainīgā O(1) laikā.

4. Stacks

Stacks ir viena no vienkāršākajām datu struktūrām, un tās ir diezgan viegli apgūt. Stacks datu struktūra būtībā ir jebkura reāla steks (domājiet par kastīšu vai plākšņu kaudzi) un darbojas LIFO (Last In First Out) veidā.

Stacks LIFO rekvizīts nozīmē, ka pirmais tiks piekļūts pēdējam ievietotajam elementam. Jūs nevarat piekļūt elementiem, kas atrodas zem augšējā elementa stekā, ja netiek parādīti elementi virs tā.

Stackiem ir divas galvenās darbības — push un pop. Push izmanto, lai ievietotu elementu kaudzē, un pop noņem augšējo elementu no kaudzītes.

Viņiem ir arī daudz noderīgu lietojumprogrammu, tāpēc intervētāji ļoti bieži uzdod jautājumus, kas saistīti ar kaudzēm. Ir ļoti svarīgi zināt, kā apgriezt skursteni un novērtēt izteiksmes.

5. Rindas

Rindas ir līdzīgas kaudzēm, taču tās darbojas FIFO (First In First Out) veidā, kas nozīmē, ka varat piekļūt iepriekš ievietotajiem elementiem. Rindas datu struktūru var vizualizēt kā jebkuru reālās dzīves rindu, kurā cilvēki tiek novietoti, pamatojoties uz viņu ierašanās secību.

Rindas ievietošanas darbību sauc par rindu, un elementa dzēšana/noņemšana no rindas sākuma tiek saukta par rindas noņemšanu.

Saistīts: Rokasgrāmata iesācējiem, lai izprastu rindas un prioritārās rindas

Prioritārās rindas ir neatņemama rindu lietojumprogramma daudzās svarīgās lietojumprogrammās, piemēram, CPU plānošanā. Prioritātes rindā elementi tiek sakārtoti pēc to prioritātes, nevis pēc ierašanās secības.

6. Kaudzītes

Kaudzes ir bināra koka veids, kurā mezgli ir sakārtoti augošā vai dilstošā secībā. Minimālajā kaudzītē galvenā pamatvērtība ir vienāda ar vai mazāka par tās atvasināto vērtību, un saknes mezglā ir visas kaudzes minimālā vērtība.

Līdzīgi Max Heap saknes mezglā ir ietverta kaudzes maksimālā atslēgas vērtība; jums ir jāsaglabā min/max kaudzes rekvizīts visā kaudzītē.

Saistīts: Kaudzes vs. Stacks: kas tos atšķir?

Kaudzēm ir daudz pielietojumu to ļoti efektīvā rakstura dēļ; Pirmkārt, prioritārās rindas bieži tiek ieviestas, izmantojot kaudzes. Tie ir arī galvenā sastāvdaļa kaudzes kārtošanas algoritmos.

Uzziniet datu struktūras

Datu struktūras sākotnēji var šķist mokošas, taču tām ir jāvelta pietiekami daudz laika, un tās būs vienkāršas.

Tie ir būtiska programmēšanas sastāvdaļa, un gandrīz katrā projektā tie būs jāizmanto. Ir ļoti svarīgi zināt, kāda datu struktūra ir ideāla konkrētajam scenārijam.

7 algoritmi, kas jāzina katram programmētājam

Šie algoritmi ir būtiski katra programmētāja darbplūsmā.

Lasiet Tālāk

Par autoru