Týždeň 4

knižnica stdlib.h, funkcie qsort(), bsort(), binárne súbory, načítavanie a ukladanie štruktúrovaných údajov, serializácia, deserializácia

Záznam z prednášky

Oznamy

  • (slide) hack košice

  • (slide) zadanie č. 1
    • už len necelý týždeň
  • (slide) Namakaný deň 2019
    • v stredu nebude prednáška ani cvičenia, ale ste všetci pozvaní na Namakaný deň

Standard Library

  • V praxi však nebudete vždy nutne potrebovať písať vlastné funkcie pre vyhľadanie prvkov alebo pre zotriedenie zoznamu prvkov. Proste využijete funkcie, ktoré sú už pre tento účel pripravené.

  • (slide) V tomto prípade môžeme napríklad využiť funkciu bsearch() z knižnice stdlib.h, ktorá implementuje tzv. binárne vyhľadávanie. A my už vieme, že v porovnaní s lineárnym vyhľadávaním, ktoré sme použili minulý týždeň, má binárne vyhľadávanie aj lepšiu zložitosť.

  • (slide) Pokúsme sa porovnať vlastnosti oboch algoritmov na vyhľadávanie:

    Lineárne vyhľadávanie Binárne vyhľadávanie
    zložitosť O(n) O(log2(n)
    najlepší prípad prvý prvok prostredný prvok
    najhorší prípad pre n prvkov n-tý prvok vyhľadávanie sa zastaví po log2n
    prerekvizity žiadne zotriedený zoznam
    prístup iteratívny rozdeľ a panuj (divide and conquer)
  • Ak však chceme binárne vyhľadávanie použiť, prvky musia byť už zotriedené. V opačnom prípade fungovať nebude. V štandardnej knižnici sa nachádza implementácia triedenia quick sort, ktorú môžete využiť zavolaním funkcie qsort().

  • Použitie oboch funkcií si ukážeme na nasledujúcich príkladoch.

Sorting list with qsort()

Searching with bsearch()

Data Persistence

  • (slide) Teraz sa pozrime na to, ako zabezpečiť trvácnosť našich údajov. Našim cieľom bude zabezpečiť, aby sa údaje nestratili a nepoškodili ani po vypnutí a opätovnom zapnutí aplikácie. Budeme ich teda ukladať a následne načítavať zo súboru.

  • Základnú prácu so súbormi už ovládate. Viete načítavať a ukladať textové aj binárne súbory.

  • Ak by sme mali tieto údaje ukladať ako textové súbory, pravdepodobne by sme došli ku niektorej schéme, ako napr.
    • (slide) každý údaj by sme uložili na samostatný riadok, alebo
    • (slide) každý jeden záznam by sme uložili na jeden riadok, pričom by sme jeho jednotlivé položky oddeľovali napr. bodkočiarkou. Tento spôsob reprezentácie sa volá CSV súbor (Comma Separated Values súbor).
  • (slide) My sa však nebudeme ukladať údaje textovo, ale binárne

  • (slide) Na čítanie a zápis budeme používať dve funkcie: fread() a fwrite().

  • Obe funkcie vrátia počet prečítaných alebo zapísaných údajov. Koniec súboru je teda možné zistiť z tohto čísla alebo pomocou funkcie feof().

  • Poďme sa teda pozrieť na to, ako uložiť najprv jednu osobu a potom aj všetky osoby na disk.

Saving Binary Data to Disk

Loading Binary Data from Disk

Additional Resources