Cvičenie č.11

Ciele
  1. Porozumieť dodanej implementácii ADT hašovacia tabuľka (Hash table).
  2. Doplniť implementáciu podľa pokynov.
  3. Reprezentácia ADT Množina pomocou ADT Binárny vyhľadávací strom (BVS).
  4. Reprezentácia ADT Množina pomocou ADT AVL strom.
  5. Reprezentácia ADT Množina pomocou ADT 2-3 strom.
Úvod
    Reprezentácia ADT Množina.
Postup
  1. Implementácia hašovacej tabuľky.
    Poznámka: Základnú predstavu o činnosti a vlastnostich ADT hašovacia tabuľka je možné získať na tejto stránke.
    Úloha: Pridajte do vytvoreného projektu všetky súbory z pripraveného archívu. Projekt preložte. Výsledný program spustite.

    Pripravený archív obsahuje tieto súbory:

    • hashtable.h - definičný modul hašovacej tabuľky so separátnym reťazením.
    • hashtable.c - implementačný modul algoritmu hašovacej tabuľky so separátnym reťazením.
    • test.c - modul pre testovanie. Obsahuje aj funkciu main.
    Poznámka: Dôkladne preštudujte dodaný kód. V prípade nejasností sa s konkrétnou otázkou obráťte na cvičiaceho.
  2. Doplnenie implementácie hašovacej tabuľky.
    Úloha: Doplňte implementáciu funkcií HTprint a HTdelete podľa nasledujúceho vzoru.
  3. Reprezentácia ADT Množina pomocou ADT Binárny vyhľadávací strom (BVS).
    Úloha: Vytvorte BVS postupným vkladaním prvkov (4, 5, 7, 2, 1, 3, 6).
    Úloha: Odstráňte z uvedeného BVS postupne tieto vrcholy (4, 8, 6, 5, 2, 1, 7).
  4. Reprezentácia ADT Množina pomocou ADT AVL strom.
    Úloha: Vytvorte AVL strom postupným vkladaním prvkov (4, 5, 7, 2, 1, 3, 6).
    Úloha: Odstráňte z uvedeného AVL stromu postupne tieto vrcholy (4, 8, 6, 5, 2, 1, 7).
    Poznámka: Vizualizácia ADT AVL strom.
  5. Reprezentácia ADT Množina pomocou ADT 2-3 strom.
    Úloha: Vytvorte 2-3 strom postupným vkladaním prvkov (1, 5, 8, 3, 6, 9, 7).
    Úloha: Odstráňte z vytvoreného 2-3 stromu postupne tieto vrcholy (8, 5).
Doplňujúce úlohy
    Úloha: Implementujte hašovaciu tabuľku s otvorenou adresáciou (lineárne, kvadratické hašovanie).
comments powered by Disqus