2020 - Týždeň 8

Zhrnutie prednášky

Prednáška nadväzuje na minulotýždňové jednosmerné spájané zoznamy, ktoré odstránili obmedzenie pevnej veľkosti poľa, no zachovali lineárnu zložitosť operácií. Predstavuje obojsmerný spájaný zoznam, kde každý uzol odkazuje na predchádzajúci aj nasledujúci prvok, a kruhový zoznam, v ktorom je posledný prvok prepojený s prvým. Použitie ilustruje na prehrávaní multimédií a doskových či kartových hrách (Monopoly, UNO). Na záver naznačuje, že pri usporiadaných prvkoch možno zložitosť vyhľadávania znížiť, ak každý uzol má ľavé rameno s menšími a pravé s väčšími hodnotami, čo vedie k binárnemu vyhľadávaciemu stromu. Druhou témou dňa sú uniony v jazyku C.

• - Spájaný zoznam odstránil obmedzenie veľkosti poľa, ale zložitosť operácií ostala lineárna.
• - Obojsmerný zoznam má v uzle odkaz na predchádzajúci aj nasledujúci prvok, čo uľahčuje prechod oboma smermi.
• - Obojsmerný zoznam sa využíva napríklad pri prehrávaní videa alebo zvuku dopredu aj dozadu.
• - Kruhový zoznam prepája posledný prvok s prvým, takže z ktoréhokoľvek uzla sa dá prejsť na ostatné.
• - Kruhové zoznamy zodpovedajú hrám ako Monopoly alebo striedaniu hráčov, pri UNO s možnou zmenou smeru.
• - Pri usporiadaných údajoch s ľavým (menším) a pravým (väčším) ramenom uzla vzniká binárny vyhľadávací strom.
• - V druhej časti prednášky sa preberajú uniony v jazyku C.

Zhrnutie pripravené s pomocou AI z prepisu videa.