Please enable JavaScript.

Coggle requires JavaScript to display documents.

16. Základní datové struktury (Základní abstraktní datové struktury…

- - - - pomocí pole a proměnné
        
        první prvek - dno
        
        proměnná - index vrcholu
      - pomocí lineárně spoj. seznamu (ukazatelé)
        
        1směrný seznam
        
        první prvek - vrchol --> použiju operaci tail
    - - odebrání O(1)
      - ověření prázdnosti O(1)
      - přidání O(1)
      - prvek na vrcholu zás. O(1)
      - vytvoření prázdného O(1)
  - - - seznam, udpořádán podle priorit (ne příchodu)
      - reprez. seznamem méně efekt. --> bin. halda
      - využití: řazení - heapsort, Dijkstr, Jarník
    - - pole + 2 proměnné
        
        časté vkládání a odebírání - zvyš. indexů - řešení
        
        posun, pokud nutné (pak celé)
        
        kruhové pole (slož.)
        
        posouvat prvku o 1 níže (neefektivní)
        
        vhodná - 3. prom. - počet prvků
        
        pokud známe max. možnou délku
        
        proměnné - index prvního a posledního prvku
      - lineárně spoj. seznam
        
        1směrný - začátek fronty na začátku a konec na konci
        
        každý uzel - ukazatel na následníka
    - - obousměrná (odebírat/vkládat na obou koncích)
      - prioritní
    - - ověření práznosti O(1)
      - přidání prvku na konec O(1)
      - vytvoření O(1)
      - fronta bez 1. prvku O(1)
      - první prvek O(1)
  - - - pomocí hašovací tabulky
        
        téměř konstantní přístup k prvkům - vhodné pro časté vkládání
        
        př.: Java
      - pomocí vyhledávacího stromu
        
        vhodné pro setřízené množiny
      - pomocí seznamu
        
        neefektivní (vyhledávání - projít celou)
        
        nejjednoduší
        
        ignoruje pořadí a při vkládání se kontroluje přítomnost stejného prvku
    - - dotaz na prvek x
      - je množina prázdná
      - přidání/odebrání prvku
      - počet prvků (...)
      - vytvoření
  - - - pomocí lineárního (1stranného) spoj. seznamu
        
        základ - záznam obsahující uloženou hodnotu + ukazatel na následující prvek
        
        ukazatel posledního prvku je prázdný
        
        pokud navážeme konec na začátek - kruhový
        
        pokud neznáme dopředu velikost
        
        data na začátek
      - pomocí oboustranného spoj. seznamu
        
        ukazatelé prvního a poslendího prvku jsou prázdné
        
        procházení oběma směry - v paměti ale 2krát tolik ukazatelů
        
        navíc ukazatel na předchozí prvek
        
        pokud navážeme konec na začátek - kruhový (sentiel - hlídka - první i poslední prvek)
      - pomocí dynam. pole
        
        nemusíme znát předem počet prvků
        
        + rychlý přístup k prvkům O(1) - náhodný přístup na index i
        
        v případě potřeby se pole realokuje na dvojnásebek
        
        - pomalé odebírání a vkládání doprostřed/na začátek - O(n)
    - - přidání prvku
      - smazání k-tého prvku
      - vytvoření prázdného O(1)
      - vložení před/za k-tý prvek
      - setřízení seznamu
      - vyhledávání v seznamu
      - test, zda je seznam prázdný O(1)
      - první prvek - head O(1)
      - seznam bez prvního prvku - tail (...)
    - - časová slož. - vkládání/mazání uprostřed - O(n) - lineární vyhledávání
      - neumožňuje náhodný přístup
  - - - při pokusu uložení více objektů na = adresu
      - haš. fce nezaručuje jinou adresu pro jiné obj.
      - řešení
        
        zřetězením
        
        hodnoty do spoj. seznamů (kolize - na konec)
        
        velké zaplnění - degradace výkonu
        
        otevřenou adresací
        
        hodnoty do pole
        
        vyhledávání
        
        obvykle
        
        kolize
        
        lineární zkoušení
        
        obsazená - o 1 místo dál
        
        nevýhoda - shlukování - nutné sekvenčně procházet
        
        spočítáme adresu
        
        mazání - nutné nahradit volná místa hlídkami
        
        druhotné hašování
        
        dvojce hašov. fcí
        
        inic. adresa
        
        pokud obsazeno - vypočte posun - opět posun...
    - - odstranění O(n)
      - vložení O(n)
      - vyhledávání prvku O(n), prům. O(1)
    - - konzistentně vrací pro stejné objekty stejné adresy
      - nezaručuje vrácení různé adresy pro různé objekty
      - celý prostor adres se stejnou prstí
      - výpočet adresy - rychle
      - modulární aritmetika
      - využití - rychlé hledání položky v poli/jiném homogennímt typu
      - pro získání hodnoty z klíče - adresace