Week 7

úvod do dynamických údajových typov, spojkový zoznam, CRUD

Záznam z prednášky

Oznamy

  • Namakaný deň 2019
    • pomoc

Motivácia

Polia

  • (slide)

  • Polia sú užitočné, pretože je možné do nich ukladať typovo rovnaké údaje, pričom v pamäti sú uložené súvislo za sebou.

  • S takto uloženými a reprezentovanými údajmi vie pracovať aj mnoho knižničných funkcií, napr. funkcie z knižnice string.h vedia pracovať s jednorozmernými poliami znakov (reťazcami), funkcie bsearch() a qsort() dokážu vyhľadávať alebo triediť takto uložené údaje, a iné.

  • Jednou z nevýhod polí je však ich fixná veľkosť (zoznam študentov môžem vytvoriť až vtedy, keď viem, koľko študentov sa v ňom bude nachádzať). Ak mi veľkosť poľa nestačí, ako do neho vložím ďalší prvok?

  • Ďalšou, podstatne väčšou nevýhodou je fakt, že základné CRUD operácie (Create Retrieve Update Delete) nie sú jednoduché a obyčajne sú tieto operácie aj veľmi drahé (O(n)).

  • S niektorými operáciami ste sa priamo stretli počas riešenia zadania K - ako ste postupovali, keď ste potrebovali vložiť prvok na správne miesto v zozname Hall of Fame?

File System

  • (slide)

  • Pozrime sa na to, ako je organizovaná štruktúra súborového systému na disku. Súbory sú uložené do blokov fixnej dĺžky, pričom jeden súbor môže na disku zaberať niekoľko takýchto blokov. Na základe príkladu na slajde má blok veľkosť 6B. Ak teda chceme uložiť reťazec “Hello, world!” do súboru, bude uložený do 3 takýchto blokov.

  • Tento spôsob ukladania údajov je veľmi výhodný, nakoľko pomocou neho je možn�� uložiť akékoľvek množstvo údajov (teoreticky súbor o akejkoľvek dĺžke). Stačí len vstupné údaje “rozbiť” do potrebného množstva týchto blokov a v uvedenej (poprepájanej) podobe ich uložiť.

  • Podobný spôsob sa napríklad používa aj pri prenose údajov v sieti, kde sa údaje rozbijú do menších celkov nazvaných pakety. Ak sa jeden stratí alebo sa prenesie poškodený, prijímateľ si ho vyžiada znova na základe čísla chýbajúceho paketu, pričom odosielateľ nemá problém požadovaný paket s údajmi zostaviť opätovným vyseknutím potrebných údajov a preposlať ho.

  • Ako je možné takýto prístup reprezentovať v jazyku C?

  • Dnes budeme hovoriť o dynamických údajových typoch (slide).

Linked Lists

  • Spôsob reprezentácie súboru v súborovom systéme, kedy je tento uložený ako istá postupnosť blokov, je známy ako Spojkový zoznam alebo Spájaný zoznam (slide).

  • Ak by sme chceli reprezentovať v jazyku C jeden jeho blok, vyzeral by takto (slide):

  • Táto štruktúra sa však nevolá block ale node, pretože vychádzame z definície, že (slide):

    linked list is a data structure consisting of a group of nodes which together represent a sequence (Wikipedia)

    Rovnako je možné takýto zoznam reprezentovať planárnym grafom, kde sa slovo uzol (node) bežne používa.

  • Ukážka takéhoto riešenia sa nachádza v súbore filesystem.c.

CRUD

  • Nad takouto štruktúrou nás bude zaujímať niekoľko operácií (slide) a to konkrétne:
    • volženie/vytvorenie nového uzla
    • získanie/vyhľadanie existujúceho uzla
    • aktualizovanie/úprava existujúceho uzla
    • odstránenie existujúceho uzla zo zoznamu
  • Naše snaženie budeme skúšať nad zoznamom čísiel a budeme sa ho snažiť udržiavať usporiadaný (slide):

    7 12 19 23 37 52

Štruktúrovaný údajový typ struct node

Funkcia traverse()

Funkcia insert()

Funkcia delete()

Other dynamic data types

  • (slide)
  • stromy
  • hash tabuľky (mapy)

Further Reading