Dátové štruktúry sú základným stavebným prvkom programovania. Predstavujú rôzne spôsoby reprezentácie dát. Opíšeme si najzákladnejšie dátové štruktúry a rozdiely medzi nimi. Keďže sme sa o dátových štruktúrach celkom rozkecali, tak algoritmy spomínať nebudeme, to až v ďalšej epizóde.
Stiahnuť
https://wp.streetofcode.sk/wp-content/uploads/2020/09/StreetOfCode-Ep46.mp3
(02:35 – 05:58) – Čo su dátové štruktúry?
(05:59 – 12:38) – Pole (Arrayy)
(12:39 – 19:45) – Zreťazený zoznam (Linked list)
(19:46 – 27:43) – Hash set
(27:44 – 32:33) – Hash map / Dictionary
(32:34 – 35:16) – Zásobník (Stack)
(35:17 – 37:25) – Rada (Queue)
(37:26 – 43:06) – Graf
(43:07 – 44:58) – Strom
(44:59 – 46:46) – Nečakaná zmena plánov
Pole (Array)
Skupina prvkov (väčšinou toho istého typu)Ku prvkom pristupujeme podľa indexov (indexy väčšinou začínajú od 0)Statická / Nemeniteľná veľkosťLIST
To isté ako pole, ale veľkosť je dynamickáZreťazený zoznam (Linked List)
Reprezentuje sekvenciu uzlov (nodes)Každý node obsahuje svoju hodnotu (môže byť čokoľvek) a referenciu na ďalší nodeReferenciu môže obsahovať aj na predošlí node, vtedy je zoznam obojsmerný (inak jednosmerný)Konštantná O(1) zložitosť vkladania/odstraňovania prvkov.Hash Mapa / Dictionary
Mapuje kľúče na hodnotyPoužíva hashovaciu funkciu na kľúčeKonštantná O(1) zložitosť prístupu k prvkom podľa keyZásobník (stack)
LIFO (last-in first-out)Vieme si to predstaviť ako taniere – posledný vložený na kopu bude použitý ako prvýObsahuje funkcie:pop() – odstráni prvok na vrcholepush(item) – pridá prvok na vrcholpeek() – vráti prvok na vrchole (neodstraňuje)isEmpty()Rad (Queue)
FIFO (first-in first-out)Vieme si to predstaviť ako rad v obchode- prvý čo sa postaví do radu bude aj prvý obslúženýObsahuje funkcie:remove() – odstráni prvok na vrcholeadd(item) – pridá prvok na koniecpeek() – vráti prvok na vrchole (neodstraňuje)isEmpty()Graf
Má vrcholy a hrany. Hranami sa spájajú jednotlivé vrcholyPomocou tejto dátovej štruktúry sa rieši mnoho problémov z reálneho života (napr. Google maps, Sociálne siete)Susedia vrcholu (alebo nazývame aj node) A, sú všetky vrcholy, ktoré majú s vrcholom A spojenieSpojenia/Hrany môzu byť orientované alebo neorientovanéMôže obsahovať cykly, vtedy je graf cyklický (inak acyklický)Strom
Stromy sú typy grafovKaždý strom ma root node (prvý node na vrchole stromu)Každý node ma 0 alebo N detí (child nodes)Binárny strom je typ stromu, v ktorom každý node ma 0 až 2 detíBinárny vyhľadávací strom je taký, v ktorom platí usporiadané také, že pre každý node platí, že naľavo od tohto node sú prvky menšie a napravo väčšieThe post Ep. 46 – Dátové štruktúry appeared first on Street of Code.