10 bendrų duomenų struktūrų, paaiškintų naudojant vaizdo įrašus + pratimus

„Blogi programuotojai nerimauja dėl kodo. Geri programuotojai nerimauja dėl duomenų struktūrų ir jų ryšių. “- Linus Torvalds,„ Linux “kūrėjas
** Atnaujinti ** Dabar mano video kursas apie algoritmus yra tiesiogiai transliuojamas! Peržiūrėkite judesio algoritmus iš „Manning Publications“. Pasinaudokite kodu „39carnes“ 39% nuo mano kurso! Arba galite gauti 50% nuolaidą mano „Deep Learning in Motion“ kursui su kodu „vlcarnes2“.

Duomenų struktūros yra kritinė programinės įrangos kūrimo dalis ir viena iš dažniausiai pasitaikančių kūrėjo darbo pokalbio klausimų.

Geros žinios yra tai, kad jie iš esmės yra tik specializuoti duomenų tvarkymo ir saugojimo formatai.

Aš išmokysiu jus 10 labiausiai paplitusių duomenų struktūrų - čia, šiame trumpame straipsnyje.

Aš įdėjau vaizdo įrašus, kuriuos sukūriau kiekvienai iš šių duomenų struktūrų. Aš taip pat susiejau su kiekvieno iš jų kodų pavyzdžiais, kurie parodo, kaip juos įdiegti „JavaScript“.

Siekdamas suteikti jums praktikos, susiejau su „freeCodeCamp“ mokymo programos iššūkiais.

Atminkite, kad kai kurios iš šių duomenų struktūrų laiko „Big O“ žymėjimu yra sudėtingos. Tai neįeina į visus juos, nes laiko sudėtingumas kartais priklauso nuo to, kaip jis įgyvendinamas. Jei norite sužinoti daugiau apie „Big O Notation“, peržiūrėkite mano straipsnį apie tai arba šį Briana Marie vaizdo įrašą.

Taip pat atkreipkite dėmesį, kad nors ir parodau, kaip šias duomenų struktūras įgyvendinti „JavaScript“, daugumai jų niekada nereikės jų diegti patiems, nebent jūs vartotumėte žemo lygio kalbą, tokią kaip C.

„JavaScript“ (kaip ir dauguma aukšto lygio kalbų) turi daugelio šių duomenų struktūrų įdiegimus.

Vis dėlto žinodami, kaip įdiegti šias duomenų struktūras, gausite didžiulį pranašumą ieškant kūrėjo darbo ir tai gali būti naudinga bandant rašyti didelio našumo kodus.

Susieti sąrašai

Susietas sąrašas yra viena iš elementariausių duomenų struktūrų. Jis dažnai lyginamas su masyvu, nes daugybė kitų duomenų struktūrų gali būti įgyvendintos naudojant masyvą arba susietą sąrašą. Jie visi turi privalumų ir trūkumų.

Susieto sąrašo pateikimas

Susietą sąrašą sudaro mazgų grupė, kurie kartu žymi seką. Kiekviename mazge yra du dalykai: faktiniai saugomi duomenys (kurie iš esmės gali būti bet kokio tipo duomenys) ir rodyklė (arba nuoroda) į kitą mazgą iš eilės. Taip pat yra dvigubai susieti sąrašai, kur kiekvienas mazgas turi rodyklę tiek į kitą, tiek į ankstesnį sąrašo elementą.

Pagrindinės susieto sąrašo operacijos yra elemento įtraukimas į sąrašą, elemento išbraukimas iš sąrašo ir elemento paieška sąraše.

Susieto sąrašo kodą „JavaScript“ rasite čia.

Susietas sąrašo laiko sudėtingumas
╔═══════════╦═════════╦════════════╗
║ Algoritmas ║ Vidutinis ║ Blogiausias atvejis ║
╠═══════════╬═════════╬════════════╣
║ Tarpas ║ O (n) ║ O (n) ║
║ Paieška ║ O (n) ║ O (n) ║
Įdėkite ║ O (1) ║ O (1) ║
║ Ištrinti ║ O (1) ║ O (1) ║
╚═══════════╩═════════╩════════════╝

„freeCodeCamp“ iššūkiai

  • Darbas su mazgais susietame sąraše
  • Sukurkite susieto sąrašo klasę
  • Pašalinkite elementus iš susieto sąrašo
  • Paieška susietų sąraše
  • Pašalinkite elementus iš susieto sąrašo pagal rodyklę
  • Pridėti elementus tam tikrame indekse susietų sąraše
  • Sukurkite dvigubai susietų sąrašą
  • Grąžinkite dvigubai susietą sąrašą

Kaminai

Rietuvė yra pagrindinė duomenų struktūra, kurioje galite įterpti arba ištrinti elementus tik krūvos viršuje. Tai panašu į krūvą knygų. Jei norite pažvelgti į knygą krūvos viduryje, pirmiausia turite išimti visas virš jos esančias knygas.

Rinkinys laikomas LIFO (paskutinis iš pradžių) - tai reiškia, kad paskutinis daiktas, kurį įdėjote į krūvą, yra pirmasis elementas, kuris išeina iš krūvos

Stack atstovavimas

Yra trys pagrindinės operacijos, kurias galima atlikti su krūvomis: įterpti elementą į krūvą (vadinamą „stumti“), ištrinti elementą iš krūvos (vadinamą „pop“) ir parodyti krūvos turinį (kartais vadinamą „pip“) ').

Čia rasite „JavaScript“ krūvos kodą.

Stack laiko sudėtingumas
╔═══════════╦═════════╦════════════╗
║ Algoritmas ║ Vidutinis ║ Blogiausias atvejis ║
╠═══════════╬═════════╬════════════╣
║ Tarpas ║ O (n) ║ O (n) ║
║ Paieška ║ O (n) ║ O (n) ║
Įdėkite ║ O (1) ║ O (1) ║
║ Ištrinti ║ O (1) ║ O (1) ║
╚═══════════╩═════════╩════════════╝

„freeCodeCamp“ iššūkiai

  • Sužinokite, kaip veikia krūva
  • Sukurkite „Stack Class“

Eilės

Galite įsivaizduoti eilę kaip žmonių eilę maisto prekių parduotuvėje. Pirmasis eilutėje yra pirmasis, kuris turi būti įteiktas. Visai kaip eilė.

Eilutės atvaizdavimas

Laikoma, kad eilė yra FIFO („First In First Out“), siekiant parodyti, kaip ji pasiekia duomenis. Tai reiškia, kad pridėjus naują elementą, visi nauji elementai, kurie buvo pridėti anksčiau, turi būti pašalinti, kad būtų galima pašalinti.

Eilėje yra tik dvi pagrindinės operacijos: užkoduoti ir nurašyti. „Enqueque“ reiškia daikto įterpimą į eilės galinę dalį, o „dequeque“ reiškia priekinio daikto pašalinimą.

Eilės kodą „JavaScript“ žiūrėkite čia.

Eilės laiko sudėtingumas
╔═══════════╦═════════╦════════════╗
║ Algoritmas ║ Vidutinis ║ Blogiausias atvejis ║
╠═══════════╬═════════╬════════════╣
║ Tarpas ║ O (n) ║ O (n) ║
║ Paieška ║ O (n) ║ O (n) ║
Įdėkite ║ O (1) ║ O (1) ║
║ Ištrinti ║ O (1) ║ O (1) ║
╚═══════════╩═════════╩════════════╝

„freeCodeCamp“ iššūkiai

  • Sukurkite eilės klasę
  • Sukurkite prioritetinių eilių klasę
  • Sukurkite apskritą eilę

Rinkiniai

Nustatykite reprezentaciją

Rinkinio duomenų struktūra saugo reikšmes be jokios konkrečios tvarkos ir be pakartotinių verčių. Be to, kad rinkinyje galima pridėti ir pašalinti elementus, yra ir keletas kitų svarbių rinkinio funkcijų, kurios veikia kartu su dviem rinkiniais.

  • „Union“ - tai sujungia visus elementus iš dviejų skirtingų rinkinių ir grąžina tai kaip naują rinkinį (be kopijų).
  • Sankryža - atsižvelgiant į du rinkinius, ši funkcija grąžina kitą rinkinį, kuriame yra visi elementai, kurie yra abiejų rinkinių dalis.
  • Skirtumas - grąžinamas elementų, kurie yra viename rinkinyje, bet NE kitame rinkinyje, sąrašas.
  • Pogrupis - grąžina loginę reikšmę, parodančią, ar visi vieno rinkinio elementai yra įtraukti į kitą rinkinį.

Peržiūrėkite kodą, kad įdiegtumėte rinkinį „JavaScript“ čia.

„freeCodeCamp“ iššūkiai

  • Sukurkite rinkinio klasę
  • Pašalinti iš rinkinio
  • Rinkinio dydis
  • Sudarykite dviejų rinkinių sąjungą
  • Atlikite dviejų duomenų rinkinių sankirtą
  • Atlikite dviejų duomenų rinkinių skirtumą
  • Atlikite dviejų duomenų rinkinių pogrupio patikrinimą
  • Sukurkite ir pridėkite prie rinkinių ES6
  • Pašalinkite elementus iš rinkinio „ES6“
  • ES6 rinkinyje naudokite .has ir .size
  • ES5 rinkinio () integravimui naudokite sklaidą ir pastabas

Žemėlapiai

Žemėlapis yra duomenų struktūra, kurioje duomenys saugomi raktų / reikšmių poromis, kur kiekvienas raktas yra unikalus. Žemėlapis kartais vadinamas asociatyviu masyvu arba žodynu. Jis dažnai naudojamas greitam duomenų paieškai. Žemėlapiuose galima atlikti šiuos dalykus:

Žemėlapio vaizdavimas
  • poros papildymas kolekcija
  • poros pašalinimas iš kolekcijos
  • esamos poros modifikacija
  • vertės, susijusios su konkrečiu raktu, paieška

Norėdami pamatyti žemėlapį „JavaScript“, žiūrėkite kodą čia.

„freeCodeCamp“ iššūkiai

  • Sukurkite žemėlapio duomenų struktūrą
  • Sukurkite „ES6 JavaScript“ žemėlapį

Maišymo stalai

Maišymo lentelės ir maišos funkcijų vaizdavimas

Maišos lentelė yra žemėlapio duomenų struktūra, kurioje yra raktų / reikšmių poros. Jis naudoja maišos funkciją, norėdamas apskaičiuoti indeksą į segmentų ar laiko tarpsnių masyvą, iš kurio galima rasti norimą vertę.

Maišos funkcija paprastai įveda eilutę kaip įvestį ir išveda skaitinę vertę. Maišos funkcija visada turėtų suteikti tą patį išvesties numerį tam pačiam įėjimui. Kai du įėjimai maišo tą patį skaitmeninį išėjimą, tai vadinama susidūrimu. Tikslas yra, kad būtų nedaug susidūrimų.

Taigi, kai raktų / reikšmių porą įvedate į maišos lentelę, raktas paleidžiamas naudojant maišos funkciją ir paverčiamas skaičiumi. Tada ši skaitinė reikšmė naudojama kaip tikrasis raktas, kurį vertė saugo. Bandydami dar kartą pasiekti tą patį klavišą, maišos funkcija apdoros klavišą ir grįš tas pats skaitinis rezultatas. Skaičius bus naudojamas ieškant susijusios vertės. Tai vidutiniškai suteikia labai efektyvų O (1) paieškos laiką.

Čia galite pamatyti maišos lentelės kodą.

Maišymo stalo laiko sudėtingumas
╔═══════════╦═════════╦════════════╗
║ Algoritmas ║ Vidutinis ║ Blogiausias atvejis ║
╠═══════════╬═════════╬════════════╣
║ Tarpas ║ O (n) ║ O (n) ║
║ Paieška ║ O (1) ║ O (n) ║
Įdėkite ║ O (1) ║ O (n) ║
║ Ištrinti ║ O (1) ║ O (n) ║
╚═══════════╩═════════╩════════════╝

„freeCodeCamp“ iššūkiai

  • Sukurkite maišos lentelę

Dvejetainis paieškos medis

Dvejetainė paieškos medis

Medis yra duomenų struktūra, sudaryta iš mazgų. Jis turi šias savybes:

  1. Kiekvienas medis turi šaknies mazgą (viršuje).
  2. Šaknies mazge yra nulis ar daugiau vaiko mazgų.
  3. Kiekviename vaiko mazge yra nulis ar daugiau vaiko mazgų ir pan.

Dvejetainis paieškos medis prideda šias dvi savybes:

  1. Kiekviename mazgelyje yra iki dviejų vaikų.
  2. Kiekvieno mazgo kairieji palikuonys yra mažesni nei dabartinis mazgas, tai yra mažiau nei dešinieji palikuonys.

Dvejetainiai paieškos medžiai leidžia greitai ieškoti, pridėti ir pašalinti elementus. Tai, kaip jie nustatomi, reiškia, kad vidutiniškai kiekvienas palyginimas leidžia praleisti maždaug pusę medžio, taigi kiekvienas peržvalgos, įterpimo ar ištrynimo laikas užtrunka proporcingai medyje saugomų elementų skaičiaus logaritmui.

Dvejetainės paieškos medžio kodą „JavaScript“ žiūrėkite čia.

Dvejetainės paieškos laiko sudėtingumas
╔═══════════╦══════════╦════════════╗
║ Algoritmas ║ Vidutinis ║ Blogiausias atvejis ║
╠═══════════╬══════════╬════════════╣
║ Tarpas ║ O (n) ║ O (n) ║
║ Paieška ║ O (log n) ║ O (n) ║
║ Įdėkite ║ O (log n) ║ O (n) ║
║ Ištrinti ║ O (log n) ║ O (n) ║
╚═══════════╩══════════╩════════════╝

„freeCodeCamp“ iššūkiai

  • Dvejetainėje paieškos medyje raskite mažiausią ir maksimalią vertę
  • Pridėti dvejetainės paieškos medį naują elementą
  • Patikrinkite, ar dvejetainėje paieškos medyje yra elementas
  • Raskite mažiausią ir maksimalų dvejetainės paieškos medžio aukštį
  • Naudokite pirmąją gylio paiešką dvejetainėje paieškos medyje
  • Dvejetainėje paieškos medyje naudokite pirmą pločio paiešką
  • Ištrinkite lapų mazgą dvejetainėje paieškos medyje
  • Ištrinkite mazgą su vienu vaiku dvejetainėje paieškos medyje
  • Ištrinkite mazgą su dviem vaikais iš dvejetainės paieškos medžio
  • Apverskite dvejetainį medį

Trie

Trie (tariama „pabandyti“) arba priešdėlis medis yra tam tikras paieškos medis. Trie saugo duomenis etapais, kur kiekvienas žingsnis yra mazgas. Bandymai dažnai naudojami norint greitai išsaugoti žodžius, pvz., Žodžio automatinio užbaigimo funkciją.

Tries reprezentacija

Kiekviename kalbos trie mazge yra viena žodžio raidė. Sekdami trio šakomis šaukite žodį, vieną raidę vienu metu. Žingsniai pradedami atšakoti, kai raidžių tvarka skiriasi nuo kitų trie žodžių arba kai baigiasi žodis. Kiekviename mazge yra raidė (duomenys) ir boolean, nurodantys, ar mazgas yra paskutinis žodžio mazgas.

Pažvelkite į atvaizdą ir galėsite formuoti žodžius. Visada pradėkite nuo šaknies mazgo viršuje ir dirbkite žemyn. Čia parodytoje trijoje yra žodis rutulys, šikšnosparnis, lėlė, do, dorkas, bendrabutis, siųsti, prasmė.

Trijos kodą „JavaScript“ žiūrėkite čia.

„freeCodeCamp“ iššūkiai

  • Sukurkite „Trie“ paieškos medį

Dvejetainė krūva

Dvejetainė krūva yra dar viena medžio duomenų struktūros rūšis. Kiekvienas mazgas turi ne daugiau kaip du vaikus. Be to, tai yra pilnas medis. Tai reiškia, kad visi lygiai yra visiškai užpildyti iki paskutinio lygio, o paskutinis lygis užpildomas iš kairės į dešinę.

Min ir max krūvos reprezentacijos

Dvejetainis krūvas gali būti tiek mažiausias, tiek didžiausias. Esant maksimaliam krūviui, tėvų mazgų raktai visada yra didesni arba lygūs vaikų klavišams. Minimaliame krūve tėvų mazgų raktai yra mažesni arba lygūs vaikų klavišams.

Tvarka tarp lygių yra svarbi, tačiau to paties lygio mazgų tvarka nėra svarbi. Paveikslėlyje galite pamatyti, kad trečiasis minų krūvos lygis yra 10, 6 ir 12. Šie skaičiai nėra tinkami.

Čia galite peržiūrėti krūvos kodą „JavaScript“.

Dvejetainis krūvos laiko sudėtingumas
╔═══════════╦══════════╦════════════╗
║ Algoritmas ║ Vidutinis ║ Blogiausias atvejis ║
╠═══════════╬══════════╬════════════╣
║ Tarpas ║ O (n) ║ O (n) ║
║ Paieška ║ O (n) ║ O (n) ║
║ Įdėkite ║ O (1) ║ O (log n) ║
║ Ištrinti ║ O (log n) ║ O (log n) ║
║ Žvilgsnis ║ O (1) ║ O (1) ║
╚═══════════╩══════════╩════════════╝

„freeCodeCamp“ iššūkiai

  • Įdėkite elementą į maksimalią krūvą
  • Pašalinkite elementą iš didžiosios krūvos
  • Įdėkite krūvą Rūšiuokite su maža krūva

Grafikas

Grafikai yra mazgų (dar vadinamų viršūnėmis) ir jų jungčių (vadinamų briaunomis) rinkiniai. Grafikai taip pat žinomi kaip tinklai.

Vienas grafikų pavyzdys yra socialinis tinklas. Mazgai yra žmonės, o kraštai - draugystė.

Yra du pagrindiniai grafikų tipai: nukreipti ir netaikomi. Nukreipti grafikai yra grafikai be jokios krypties briaunose tarp mazgų. Kryptingi grafikai, priešingai, yra grafikai, kurių kraštinė yra kryptis.

Du paplitę būdai, kaip pavaizduoti grafiką, yra gretimybių sąrašas ir gretimybių matrica.

Gretimos matricos grafikas

Gretimybių sąrašą galima pavaizduoti kaip sąrašą, kuriame kairioji pusė yra mazgas, o dešinėje - visi kiti mazgai, prie kurių jis yra prijungtas.

Gretimybių matrica yra skaičių tinklelis, kuriame kiekviena eilutė arba stulpelis žymi skirtingą diagramos mazgą. Eilutės ir stulpelio sankirtoje yra skaičius, nurodantis ryšį. Nuliai reiškia, kad nėra krašto ar santykių. Oni reiškia, kad yra santykiai. Skaičiai, didesni už vieną, gali būti naudojami norint parodyti skirtingus svorius.

Traversal algoritmai yra algoritmai, skirti diagramos takams aplankyti ar aplankyti. Pagrindiniai traversinių algoritmų tipai yra pirmo pločio paieška ir pirmo gylio paieška. Vienas iš būdų yra nustatyti, kiek arti mazgai yra šaknies mazgui. Žemiau pateiktame vaizdo įraše skaitykite, kaip „Java“ paieškoje įdiegti pirmą plotį.

Pirmiausia ieškokite kodo, esančio gretimybių matricos diagramoje „JavaScript“.

Gretimybių sąrašo (grafiko) laiko sudėtingumas
╔═══════════════╦════════════╗
║ Algoritmas ║ Laikas ║
╠═══════════════╬════════════╣
║ Sandėliavimas ║ O (| V | + | E |) ║
║ Pridėti „Vertex“ ║ O (1) ║
║ Pridėti kraštą ║ O (1) ║
║ Pašalinkite Vertex ║ O (| V | + | E |) ║
║ Pašalinkite kraštą ║ O (| E |) ║
║ Užklausa ║ O (| V |) ║
╚═══════════════╩════════════╝

„freeCodeCamp“ iššūkiai

  • Gretimybių sąrašas
  • Blakių matrica
  • Sergamumo matrica
  • Pirma paieška
  • Pirmasis gylis

Daugiau

Knyga „Grokking Algorithms“ yra geriausia knyga šia tema, jei dar nesinaudojote duomenų struktūromis / algoritmais ir neturite informatikos pagrindų. Tam, kad paaiškintų kai kurias duomenų struktūras, aprašytas šiame straipsnyje, naudojami lengvai suprantami paaiškinimai ir linksmos, rankomis iliustruotos iliustracijos (autoriaus, kuris yra pagrindinis „Etsy“ kūrėjas).

Arba galite peržiūrėti mano vaizdo įrašo kursą pagal tą knygą: Algoritmai judant iš „Manning Publications“. Pasinaudokite kodu „39carnes“ 39% nuo mano kurso!