2017 - Týždeň 2

Zhrnutie prednášky

Prednáška nadväzuje na vyhľadávanie v poliach štruktúr a pripomína lineárne vyhľadávanie so zložitosťou N a binárne vyhľadávanie so zložitosťou log N, ktoré vyžaduje zoradené pole. Zdôrazňuje inžiniersky princíp nevymýšľať už hotové a overené riešenia, preto sa využívajú funkcie qsort a bsearch zo štandardnej knižnice stdlib. Podrobne rozoberá deklaráciu qsort: adresu začiatku poľa (base), počet prvkov a veľkosť jedného prvku v bajtoch, ktorú funkcia potrebuje na posun medzi prvkami cez ukazovateľ void*. Vysvetľuje potrebu vlastnej porovnávacej funkcie pre štruktúrovaný typ person, ktorá vracia nulu pri zhode, zápornú hodnotu pri správnom poradí a kladnú pri potrebe výmeny, podobne ako strcmp. Na záver sa začína implementácia tejto funkcie cmp.

• - Lineárne vyhľadávanie má zložitosť N, binárne log N a vyžaduje zoradené pole.
• - Namiesto vlastných implementácií sa oplatí použiť overené funkcie knižnice stdlib: qsort a bsearch.
• - qsort dostáva adresu prvého prvku poľa, počet prvkov a veľkosť jedného prvku v bajtoch.
• - Veľkosť štruktúry sa určuje súčtom jej členov, napríklad 30 + 40 + 1 + 4 = 75 bajtov pre person.
• - Ukazovateľ void* nenesie informáciu o type, preto qsort potrebuje veľkosť prvku na posun v pamäti.
• - Porovnávacia funkcia určuje, podľa ktorého kritéria sa štruktúry triedia (priezvisko, meno, výška a pod.).
• - Návratová hodnota porovnávacej funkcie funguje ako strcmp: nula je zhoda, záporné číslo správne poradie, kladné znamená výmenu.

Zhrnutie pripravené s pomocou AI z prepisu videa.