Ep. 46 – Dátové štruktúry

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ť

(00:00 – 02:34) – Úvod
(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
(46:47 – 47:24) – Záver

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ší node
  • Referenciu 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 hodnoty
  • Používa hashovaciu funkciu na kľúče
  • Konštantná O(1) zložitosť prístupu k prvkom podľa key

Zá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 vrchole
    • push(item) – pridá prvok na vrchol
    • peek() – 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 vrchole
    • add(item) – pridá prvok na koniec
    • peek() – vráti prvok na vrchole (neodstraňuje)
    • isEmpty()

Graf

  • Má vrcholy a hrany. Hranami sa spájajú jednotlivé vrcholy
  • Pomocou 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 spojenie
  • Spojenia/Hrany môzu byť orientované alebo neorientované
  • Môže obsahovať cykly, vtedy je graf cyklický (inak acyklický)

Strom

  • Stromy sú typy grafov
  • Kaž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äčšie

Pridaj komentár

Vaša e-mailová adresa nebude zverejnená.