Programovanie (2) v Jave
1-INF-166, letný semester 2023/24
Prednáška 22: Rozdiel medzi revíziami
(→Oznamy) |
|||
(47 medziľahlých úprav od 2 ďalších používateľov nie je zobrazených) | |||
Riadok 1: | Riadok 1: | ||
== Oznamy == | == Oznamy == | ||
− | |||
− | |||
− | |||
− | |||
− | + | Plán prednášok a cvičení na zvyšok semestra: | |
+ | * Dnes informácie k skúške a posledná ukážka stromov | ||
+ | * V piatok nepovinné cvičenia | ||
+ | * V pondelok 11.12. nepovinná prednáška o nepreberaných črtách jazykov C a C++ (táto nepovinná časť učiva nebude vyžadovaná na skúške, ale môžete ju použiť). | ||
+ | * V utorok 12.12. v rámci cvičení tréning na skúšku. | ||
+ | ** Na testovači už sú tréningové príklady na skúšku, jeden pribudne dnes týkajúci sa dnešného učiva. Za niektoré budete môcť získať bonusový bod, ak ich vyriešite do 11.1. (ako tréning sa dajú riešiť aj neskôr). V utorok na cvičeniach pribudne ešte jeden tréningový príklad za 4 body. Ak prídete na cvičenia a odovzdáte na konci aspoň rozumne rozrobenú verziu programu, získate jeden bonusový bod, aj keď ho nestihnete dokončiť. | ||
+ | * V stredu 13.12. 18:10 [[Zimný semester, semestrálny test|semestrálny test]] | ||
+ | * V piatok 15.12. od 13:10 predtermín skúšky, doplnkové cvičenia nebudú | ||
+ | == Prefixové stromy == | ||
− | + | [[Image:trie2.png|thumb|right|Prefixový strom reprezentujúci množinu reťazcov <tt>a, aj, ale, aleba, alebo, cez, na, nad</tt>.]] | |
− | [[Image: | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | ''Prefixové stromy'' (niekde tiež ''lexikografické stromy''; angl. ''trie'' zo slova ''retrieval'') sú dátová štruktúra na uchovávanie ''množiny reťazcov''. Ide o stromy, ktoré nemusia byť binárne: | |
− | + | * Uzol prefixového stromu má najviac toľko detí, koľko je znakov v uvažovanej abecede. Každé dieťa je označené iným znakom abecedy. Graficky si môžeme predstaviť tento znak prislúchajúci k hrane spájajúcej rodiča a dieťa. | |
− | + | * Koreň prefixového stromu zodpovedá prázdnemu reťazcu. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | * | ||
− | * Koreň | ||
* Uzol v hĺbke ''k'' zodpovedá reťazcu dĺžky ''k'', ktorý dostaneme prečítaním písmen na ceste z koreňa do daného uzla. | * Uzol v hĺbke ''k'' zodpovedá reťazcu dĺžky ''k'', ktorý dostaneme prečítaním písmen na ceste z koreňa do daného uzla. | ||
− | * Každý uzol | + | * Každý uzol prefixového stromu obsahuje logickú hodnotu vyjadrujúcu, či k nemu prislúchajúci reťazec patrí do množiny reprezentovanej týmto prefixovým stromom. |
− | * V korektnom | + | * V korektnom prefixovom strome všetky listy zodpovedajú reťazcom z reprezentovanej množiny. |
+ | * Vnútorné vrcholy môžu zodpovedať reťazcu z množiny alebo iba prefixu jedného alebo viacerých takých reťazcov. | ||
− | + | Uzly prefixového stromu budeme reprezentovať štruktúrou <tt>node</tt> | |
+ | * Uzol obsahuje obsahuje booleovskú premennú <tt>isWord</tt>, v ktorej je uložená informácia o tom, či reťazec prislúchajúci k danému uzlu patrí alebo nepatrí do reprezentovanej množiny a pole <tt>children</tt> smerníkov na jednotlivé deti daného uzla. | ||
+ | * Veľkosť <tt>alphSize</tt> tohto poľa je rovná veľkosti uvažovanej abecedy. | ||
+ | * V ukážkovom programe uvažujeme abecedu 'a'..'z'. | ||
− | |||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
Riadok 258: | Riadok 32: | ||
struct node { | struct node { | ||
− | node *children[alphSize]; | + | // pole smernikov na deti |
− | + | node *children[alphSize]; | |
− | + | // udava, ci uzol prislucha k slovu z reprezentovanej mnoziny | |
+ | bool isWord; | ||
}; | }; | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | Samotný | + | Samotný prefixový strom je potom daný iba smerníkom na svoj koreň: |
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
struct trie { | struct trie { | ||
Riadok 271: | Riadok 46: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | === Inicializácia | + | === Inicializácia a likvidácia prefixového stromu === |
− | Nasledujúca funkcia inicializuje prázdny | + | Nasledujúca funkcia inicializuje prázdny prefixový strom <tt>t</tt>: |
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
− | void | + | void init(trie &t) { |
t.root = NULL; | t.root = NULL; | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | + | Uvoľnenie pamäte alokovanej pre podstrom zakorenený v uzle <tt>root</tt> realizujeme obdobne ako pri binárnych vyhľadávacích stromoch. Jediný rozdiel spočíva v potenciálne väčšom počte detí uzla <tt>root</tt>. | |
− | |||
− | Uvoľnenie pamäte alokovanej pre podstrom zakorenený v uzle <tt>root</tt> realizujeme obdobne ako pri binárnych vyhľadávacích stromoch. Jediný rozdiel spočíva v potenciálne väčšom počte | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
void destroySubtree(node *root) { | void destroySubtree(node *root) { | ||
if (root != NULL) { | if (root != NULL) { | ||
− | for (int i = 0; i < | + | for (int i = 0; i < alphSize; i++) { |
destroySubtree(root->children[i]); | destroySubtree(root->children[i]); | ||
} | } | ||
Riadok 296: | Riadok 69: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | Nasledujúca funkcia potom zlikviduje celý | + | Nasledujúca funkcia potom zlikviduje celý prefixový strom <tt>t</tt>: |
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
− | void | + | void destroy(trie &t) { |
destroySubtree(t.root); | destroySubtree(t.root); | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | === | + | === Hľadanie v prefixovom strome === |
− | Pri vkladaní reťazca do množiny | + | Funkcia <tt>contains</tt> pre daný prefixový strom <tt>t</tt> a reťazec <tt>word</tt> zistí, či slovo <tt>word</tt> patrí do množiny reprezentovanej stromom <tt>t</tt>. |
+ | * Postupuje po písmenách reťazca <tt>word</tt>. Kým nedôjde na koniec slova, snaží sa ísť po hranách, ktoré zodpovedajú jednotlivým písmenám. | ||
+ | * V prípade, že v niektorom bode narazí na <tt>NULL</tt>, slovo <tt>word</tt> sa v strome nenachádza. | ||
+ | * V opačnom prípade toto slovo dočíta v nejakom uzle <tt>v</tt>. V takom prípade slovo <tt>word</tt> patrí do reprezentovanej množiny práve vtedy, keď <tt>v->isWord</tt> má hodnotu <tt>true</tt>. | ||
+ | |||
+ | <syntaxhighlight lang="C++"> | ||
+ | bool contains(trie &t, const char *word) { | ||
+ | node *v = t.root; | ||
+ | if (v == NULL) { | ||
+ | return false; | ||
+ | } | ||
+ | for (int i = 0; word[i] != 0; i++) { | ||
+ | int c = word[i] - 'a'; | ||
+ | assert(c >= 0 && c < alphSize); | ||
+ | v = v->children[c]; | ||
+ | if (v == NULL) { | ||
+ | return false; | ||
+ | } | ||
+ | } | ||
+ | return v->isWord; | ||
+ | } | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | === Vkladanie do prefixového stromu === | ||
+ | |||
+ | Pri vkladaní reťazca do množiny reprezentovanej prefixovým stromom potrebujeme vytvárať nové uzly. Túto podúlohu realizuje funkcia <tt>createNode</tt>, ktorá vytvorí nový uzol s hodnotou <tt>isWord</tt> danou jej argumentom a so všetkými smerníkmi na deti nastavenými na <tt>NULL</tt>. | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
node *createNode(bool isWord) { | node *createNode(bool isWord) { | ||
node *v = new node; | node *v = new node; | ||
− | for (int i = 0; i < | + | for (int i = 0; i < alphSize; i++) { |
v->children[i] = NULL; | v->children[i] = NULL; | ||
} | } | ||
Riadok 319: | Riadok 117: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | Vloženie reťazca <tt>word</tt> do | + | Vloženie reťazca <tt>word</tt> do prefixového stromu <tt>t</tt> vykoná funkcia <tt>add</tt>, ktorá pracuje nasledovne: |
* Začne v koreni stromu, odkiaľ postupuje nižšie smerom k listom. | * Začne v koreni stromu, odkiaľ postupuje nižšie smerom k listom. | ||
− | * V každom uzle sa pozrie na ďalšie písmeno slova <tt>word</tt>. Ak danému uzlu chýba | + | * V každom uzle sa pozrie na ďalšie písmeno slova <tt>word</tt>. Ak danému uzlu chýba dieťa pre toto písmeno, vytvorí ho pomocou funkcie <tt>createNode</tt>. Následne sa presunie do tohto dieťaťa. |
− | * | + | * Keď v nejakom uzle <tt>v</tt> príde na koniec slova <tt>word</tt>, nastaví hodnotu <tt>v->isWord</tt> na <tt>true</tt>. |
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
− | void | + | void add(trie &t, const char *word) { |
if (t.root == NULL) { | if (t.root == NULL) { | ||
t.root = createNode(false); | t.root = createNode(false); | ||
Riadok 332: | Riadok 130: | ||
for (int i = 0; word[i] != 0; i++) { | for (int i = 0; word[i] != 0; i++) { | ||
int c = word[i] - 'a'; | int c = word[i] - 'a'; | ||
+ | assert(c >= 0 && c < alphSize); | ||
if (v->children[c] == NULL) { | if (v->children[c] == NULL) { | ||
v->children[c] = createNode(false); | v->children[c] = createNode(false); | ||
Riadok 341: | Riadok 140: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | === | + | === Vymazanie slova z prefixového stromu === |
− | + | Vymazávanie slov z množiny reprezentovanej prefixovým stromom budeme realizovať prostredníctvom pomocnej rekurzívnej funkcie <tt>removeFromSubtree</tt>. | |
− | + | * Funkcia z podstromu zakorenenom v uzle <tt>root</tt> vymaže sufix reťazca <tt>word</tt> začínajúci na pozícii <tt>index</tt>. | |
− | + | * Funkcia vráti booleovskú hodnotu podľa toho, či sa pri tomto vymazaní sufixu z daného podstromu vymazal jeho koreň <tt>root</tt>. | |
− | + | * Ak sa slovo <tt>word</tt> v reprezentovanej množine nenachádza, funkcia <tt>removeFromSubtree</tt> vyhlási chybu pomocou funkcie <tt>assert</tt>. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | Vymazávanie slov z množiny reprezentovanej | ||
− | |||
− | Ak sa slovo <tt>word</tt> v reprezentovanej množine nenachádza, funkcia <tt>removeFromSubtree</tt> vyhlási chybu pomocou funkcie <tt>assert</tt>. | ||
Funkcia <tt>removeFromSubtree</tt> pracuje nasledovne: | Funkcia <tt>removeFromSubtree</tt> pracuje nasledovne: | ||
* Ak je sufix reťazca <tt>word</tt> začínajúci na indexe <tt>index</tt> prázdny, nastaví hodnotu <tt>root->isWord</tt> na <tt>false</tt>. | * Ak je sufix reťazca <tt>word</tt> začínajúci na indexe <tt>index</tt> prázdny, nastaví hodnotu <tt>root->isWord</tt> na <tt>false</tt>. | ||
− | * V opačnom prípade funkcia <tt>removeFromSubtree</tt> zavolá rekurzívne samú seba pre | + | * V opačnom prípade funkcia <tt>removeFromSubtree</tt> zavolá rekurzívne samú seba pre dieťa zodpovedajúce písmenu na pozícii <tt>index</tt> reťazca <tt>word</tt>. Ak toto volanie dané dieťa zmaže, prestaví smerník na toto dieťa na <tt>NULL</tt>. |
− | * V prípade, že po vykonaní jednej z predchádzajúcich dvoch operácií nemá uzol <tt>root</tt> | + | * V prípade, že po vykonaní jednej z predchádzajúcich dvoch operácií nemá uzol <tt>root</tt> žiadne dieťa a súčasne má <tt>root->isWord</tt> hodnotu <tt>false</tt>, uvoľní pamäť alokovanú pre uzol <tt>root</tt> a informáciu o jeho zmazaní vráti na výstupe. |
+ | |||
+ | Cvičenie: hoci mazanie neprehľadáva celý strom, iba jednu cestu z koreňa smerom dolu, naprogramovali sme ju rekurzívne. Na aký problén by sme narazili, ak by sme ju chceli naprogramovať cyklom? Pomohli by nám smerníky na rodiča v uzloch stromu? | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
Riadok 386: | Riadok 168: | ||
} | } | ||
int numChildren = 0; | int numChildren = 0; | ||
− | for (int i = 0; i < | + | for (int i = 0; i < alphSize; i++) { |
if (root->children[i] != NULL) { | if (root->children[i] != NULL) { | ||
numChildren++; | numChildren++; | ||
Riadok 394: | Riadok 176: | ||
delete root; | delete root; | ||
return true; | return true; | ||
+ | } else { | ||
+ | return false; | ||
} | } | ||
− | |||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | Samotné odstránenie reťazca <tt>word</tt> z množiny reprezentovanej stromom <tt>t</tt> potom realizuje | + | Samotné odstránenie reťazca <tt>word</tt> z množiny reprezentovanej stromom <tt>t</tt> potom realizuje funkcia <tt>remove</tt>. |
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
− | void | + | void remove(trie &t, const char *word) { |
+ | // zavolame rekurziu pre koren stromu | ||
bool rootRemoved = removeFromSubtree(t.root, word, 0); | bool rootRemoved = removeFromSubtree(t.root, word, 0); | ||
+ | // ak bol koren odstraneny, nastavime t.root na NULL | ||
if (rootRemoved) { | if (rootRemoved) { | ||
t.root = NULL; | t.root = NULL; | ||
Riadok 410: | Riadok 195: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | === Výška | + | === Výška prefixového stromu === |
− | Nasledujúca funkcia vypočíta výšku podstromu zakoreneného v uzle <tt> | + | Nasledujúca funkcia vypočíta výšku podstromu zakoreneného v uzle <tt>root</tt>: |
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
Riadok 420: | Riadok 205: | ||
} | } | ||
int maxHeight = -1; | int maxHeight = -1; | ||
− | for (int i = 0; i < | + | for (int i = 0; i < alphSize; i++) { |
int height = subtreeHeight(root->children[i]); | int height = subtreeHeight(root->children[i]); | ||
if (height > maxHeight) { | if (height > maxHeight) { | ||
Riadok 430: | Riadok 215: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | Výšku samotného | + | Výšku samotného prefixového stromu <tt>t</tt> potom spočíta nasledujúca funkcia: |
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
− | int | + | int height(trie &t) { |
return subtreeHeight(t.root); | return subtreeHeight(t.root); | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | === Vypisovanie slov reprezentovaných | + | === Vypisovanie slov reprezentovaných prefixovým stromom === |
− | Nasledujúca funkcia <tt>printSubtree</tt> prehľadáva podstrom zakorenený v uzle <tt> | + | Nasledujúca funkcia <tt>printSubtree</tt> prehľadáva podstrom zakorenený v uzle <tt>root</tt> a v reťazci <tt>str</tt> postupne generuje všetky slová z reprezentovanej množiny, ktoré zároveň vypisuje na konzolu. V parametri <tt>index</tt> dostane hĺbku aktuálneho vrcholu, t.j. pozíciu v reťazci, na ktorú pridáme ďalší znak. |
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
− | void printSubtree(node *root, char * | + | void printSubtree(node *root, char *str, int index) { |
if (root == NULL) { | if (root == NULL) { | ||
return; | return; | ||
} | } | ||
if (root->isWord) { | if (root->isWord) { | ||
− | + | str[index] = 0; // ukoncenie retazca pred vypisom | |
− | printf("%s\n", | + | printf("%s\n", str); |
} | } | ||
− | for (int i = 0; i < | + | for (int i = 0; i < alphSize; i++) { |
− | + | str[index] = 'a' + i; | |
− | printSubtree(root->children[i], | + | printSubtree(root->children[i], str, index + 1); |
} | } | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | Funkcia <tt> | + | Funkcia <tt>printAll</tt> vypisujúca všetky slová v množine reprezentovanej prefixovým stromom <tt>t</tt> najprv spočíta výšku stromu <tt>t</tt>, ktorá je rovná dĺžke najdlšieho reťazca tejto množiny. Následne dynamicky alokuje reťazec dostatočnej dĺžky na uchovanie každého slova množiny a zavolá funkciu <tt>printSubtree</tt> pre koreň stromu <tt>t</tt>. |
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
− | void | + | void printAll(trie &t) { |
− | int height = | + | int height = height(t); |
if (height >= 0) { | if (height >= 0) { | ||
− | char * | + | char *str = new char[height + 1]; |
− | printSubtree(t.root, | + | printSubtree(t.root, str, 0); |
− | delete[] | + | delete[] str; |
} | } | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | === | + | V akom poradí budú slová vypísané? |
+ | |||
+ | ==Ukážka programu s prefixovým stromom, ADT slovník== | ||
+ | |||
+ | Na vstupe máme text pozostávajúci zo slov s malými písmenami a pre každé slovo v texte chceme spočítať, koľkokrát sa tam nachádza. | ||
+ | * Jednotlivé slová uložíme pomocou prefixového stromu a v každom uzle si pamätáme namiesto hodnoty <tt>isWord</tt> počítadlo <tt>count</tt>, ktoré udáva, koľkokrát sme príslušné slovo videli na vstupe. | ||
+ | * Počítadlo má hodnotu nula pre prefixy vstupných slov, ktoré samé zatiaľ ako slovo na vstupe neboli. | ||
+ | * Namiesto funkcie <tt>treeInsert</tt> máme funkciu <tt>treeIncrement</tt>, ktorá dostane slovo a zvýši jeho počítadlo, pričom ak slovo zatiaľ v strome nebolo, tak ho pridá. | ||
+ | * Podobne by sme na tento účel vedeli upraviť aj implementáciu množiny pomocou binárneho vyhľadávacieho stromu, hašovacej tabuľky, poľa alebo zoznamu. | ||
+ | ** Pozor, ak sú kľúče reťazce, na ich porovnanie musíme v týchto implementáciách použiť <tt>strcmp</tt>, nie <tt>==</tt>, <tt><</tt> a pod. | ||
+ | |||
+ | Abstraktný dátový typ, ktorý si okrem množiny kľúčov ku každému kľúču pamätá aj ďalšie dáta, sa zvykne nazývať '''slovník''' (angl. dictionary, map). | ||
+ | * Tu boli kľúče slová a ďalšie dáta počet výskytov. | ||
+ | * Iný príklad je zoznam kontaktov, kde kľúčom je meno osoby a pre dané meno chceme vrátiť kontaktné údaje danej osoby (emailová adresa, telefón a pod.) | ||
− | |||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
Riadok 481: | Riadok 278: | ||
using namespace std; | using namespace std; | ||
+ | const int alphSize = 'z' - 'a' + 1; | ||
+ | |||
+ | // uzol prefixoveho stromu | ||
+ | struct node { | ||
+ | // pole smernikov na deti | ||
+ | node *children[alphSize]; | ||
+ | // pocet vyskytov slova prisluchajuceho uzlu | ||
+ | int count; | ||
+ | }; | ||
+ | |||
+ | // cely prefixovy strom | ||
+ | struct trie { | ||
+ | node *root; | ||
+ | }; | ||
− | |||
+ | // inicializacia prazdneho stormu | ||
+ | void init(trie &t) { | ||
+ | t.root = NULL; | ||
+ | } | ||
− | + | // mazanie podstromu s korenom root | |
− | + | void destroySubtree(node *root) { | |
− | + | if (root != NULL) { | |
− | + | for (int i = 0; i < alphSize; i++) { | |
− | + | destroySubtree(root->children[i]); | |
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | + | delete root; | |
− | + | } | |
− | + | } | |
− | + | ||
− | + | // uvolnenie pamate celeho stromu | |
− | + | void destroy(trie &t) { | |
− | + | destroySubtree(t.root); | |
− | + | } | |
+ | |||
+ | // vytvorenie noveo uzlu bez deti a s nula vyskytmi | ||
+ | node *createNode() { | ||
+ | node *v = new node; | ||
+ | for (int i = 0; i < alphSize; i++) { | ||
+ | v->children[i] = NULL; | ||
+ | } | ||
+ | v->count = 0; | ||
+ | return v; | ||
+ | } | ||
+ | |||
+ | // zvysenie pocitadla pre slovo word | ||
+ | // ak slovo este nie je v strome, je pridane | ||
+ | void increment(trie &t, const char *word) { | ||
+ | if (t.root == NULL) { | ||
+ | t.root = createNode(); | ||
+ | } | ||
+ | node *v = t.root; | ||
+ | for (int i = 0; word[i] != 0; i++) { | ||
+ | int c = word[i] - 'a'; | ||
+ | assert(c >= 0 && c < alphSize); | ||
+ | if (v->children[c] == NULL) { | ||
+ | v->children[c] = createNode(); | ||
} | } | ||
− | if ( | + | v = v->children[c]; |
− | + | } | |
− | + | v->count++; | |
+ | } | ||
+ | |||
+ | // vyska podstromu s korenom root | ||
+ | int subtreeHeight(node *root) { | ||
+ | if (root == NULL) { | ||
+ | return -1; | ||
+ | } | ||
+ | int maxHeight = -1; | ||
+ | for (int i = 0; i < alphSize; i++) { | ||
+ | int height = subtreeHeight(root->children[i]); | ||
+ | if (height > maxHeight) { | ||
+ | maxHeight = height; | ||
} | } | ||
− | + | } | |
− | + | return maxHeight + 1; | |
− | + | } | |
− | + | ||
− | + | // vyska stromu. t.j. dlzka najdlsieho slova | |
− | } | + | int height(trie &t) { |
− | + | return subtreeHeight(t.root); | |
+ | } | ||
+ | |||
+ | // vypisanie slov v podstrome prefixoveho stromu | ||
+ | void printSubtree(node *root, char *str, int index) { | ||
+ | if (root == NULL) { | ||
+ | return; | ||
+ | } | ||
+ | if (root->count > 0) { | ||
+ | str[index] = 0; // ukoncenie retazca pred vypisom | ||
+ | printf("%s %d\n", str, root->count); | ||
+ | } | ||
+ | for (int i = 0; i < alphSize; i++) { | ||
+ | str[index] = 'a' + i; | ||
+ | printSubtree(root->children[i], str, index + 1); | ||
+ | } | ||
+ | } | ||
+ | |||
+ | // vypisanie slov prefixoveho stromu | ||
+ | void printAll(trie &t) { | ||
+ | int height = height(t); | ||
+ | if (height >= 0) { | ||
+ | char *str = new char[height + 1]; | ||
+ | printSubtree(t.root, str, 0); | ||
+ | delete[] str; | ||
+ | } | ||
+ | } | ||
+ | |||
+ | int main() { | ||
+ | // inicializacia stromu | ||
+ | trie t; | ||
+ | init(t); | ||
+ | // postupne nacitavanie slov | ||
+ | char word[100]; | ||
+ | while (true) { | ||
+ | int count = scanf("%99s", word); | ||
+ | if (count < 1) { // koniec vstupu | ||
break; | break; | ||
} | } | ||
+ | // pridanie slova resp. zvysenie pocitadla | ||
+ | increment(t, word); | ||
} | } | ||
− | + | // vypis a uvolnenie pamate | |
− | + | printAll(t); | |
+ | destroy(t); | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | |||
== Sylaby predmetu == | == Sylaby predmetu == | ||
Riadok 533: | Riadok 415: | ||
* funkcie (a parametre funkcií - odovzdávanie hodnotou, referenciou, smerníkom) | * funkcie (a parametre funkcií - odovzdávanie hodnotou, referenciou, smerníkom) | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
− | void f1(int x){} | + | void f1(int x){} //hodnotou |
− | void f2(int &x){} | + | void f2(int &x){} //referenciou |
− | void f3(int* x){} | + | void f3(int* x){} //smerníkom |
− | void f(int a[], int n){} | + | void f(int a[], int n){} //polia bez & (ostanú zmeny) |
− | void kresli(Turtle &t){} | + | void kresli(Turtle &t){} //korytnačky, SVGdraw a pod. s & |
</syntaxhighlight> | </syntaxhighlight> | ||
Riadok 576: | Riadok 458: | ||
int *b = a; // a,b su teraz takmer rovnocenne premenne | int *b = a; // a,b su teraz takmer rovnocenne premenne | ||
− | int * | + | int *a = new int[n]; // alokovanie 1D pola danej dlzky |
.. | .. | ||
− | delete[] | + | delete[] a; |
int **a; // alokovanie 2D matice | int **a; // alokovanie 2D matice | ||
Riadok 594: | Riadok 476: | ||
Abstraktný dátový typ '''dynamická množina''' (set) | Abstraktný dátový typ '''dynamická množina''' (set) | ||
− | * operácie init, | + | * operácie init, contains, add, remove |
* implementácie pomocou | * implementácie pomocou | ||
** neutriedeného poľa | ** neutriedeného poľa | ||
** utriedeného poľa | ** utriedeného poľa | ||
** spájaných zoznamov | ** spájaných zoznamov | ||
+ | ** hašovacej tabuľky | ||
** binárnych vyhľadávacích stromov | ** binárnych vyhľadávacích stromov | ||
− | ** | + | ** prefixového stromu (ak kľúč je reťazec) |
− | |||
Abstraktné dátové typy '''rad a zásobník''' | Abstraktné dátové typy '''rad a zásobník''' | ||
Riadok 609: | Riadok 491: | ||
* využitie: ukladanie dát na spracovanie, odstránenie rekurzie | * využitie: ukladanie dát na spracovanie, odstránenie rekurzie | ||
* kontrola zátvoriek a vyhodnocovanie výrazov pomocou zásobníka | * kontrola zátvoriek a vyhodnocovanie výrazov pomocou zásobníka | ||
− | |||
=== Dátové štruktúry === | === Dátové štruktúry === | ||
Riadok 616: | Riadok 497: | ||
struct node { | struct node { | ||
int data; | int data; | ||
− | + | node* next; | |
}; | }; | ||
struct linkedList { | struct linkedList { | ||
− | + | node* first; | |
}; | }; | ||
void insertFirst(linkedList &z, int d){ | void insertFirst(linkedList &z, int d){ | ||
/* do zoznamu z vlozi na zaciatok novy prvok s datami d */ | /* do zoznamu z vlozi na zaciatok novy prvok s datami d */ | ||
− | + | node* p = new node; // vytvoríme nový prvok | |
p->data = d; // naplníme dáta | p->data = d; // naplníme dáta | ||
− | p->next = z.first; // | + | p->next = z.first; // uzol ukazuje na doterajší začiatok |
z.first = p; // tento prvok je novým začiatkom | z.first = p; // tento prvok je novým začiatkom | ||
} | } | ||
Riadok 635: | Riadok 516: | ||
/* vrchol stromu */ | /* vrchol stromu */ | ||
dataType data; | dataType data; | ||
− | node * left; /* | + | node * left; /* lave dieta */ |
− | node * right; /* | + | node * right; /* prave dieta */ |
}; | }; | ||
Riadok 650: | Riadok 531: | ||
* použitie na uloženie aritmetických výrazov | * použitie na uloženie aritmetických výrazov | ||
− | [[Image:P22-BST.png|200px|right]]'''Binárne vyhľadávacie stromy''' | + | [[Image:P22-BST.png|thumb|200px|right]]'''Binárne vyhľadávacie stromy''' |
* vrcholy vľavo od koreňa menší kľúč, vpravo od koreňa väčší | * vrcholy vľavo od koreňa menší kľúč, vpravo od koreňa väčší | ||
* insert, find, remove v čase závisiacom od hĺbky stromu | * insert, find, remove v čase závisiacom od hĺbky stromu | ||
− | [[Image: | + | [[Image:trie2.png|thumb|right|Prefixový strom reprezentujúci množinu reťazcov <tt>a, aj, ale, aleba, alebo, cez, na, nad</tt>.]]'''Prefixové stromy''' |
* ukladajú množinu reťazcov | * ukladajú množinu reťazcov | ||
− | * nie sú binárne: vrchol môže mať veľa | + | * nie sú binárne: vrchol môže mať veľa detí |
* insert, find, remove v čase závisiacom od dĺžky kľúča, ale nie od počtu kľúčov, ktoré už sú v strome | * insert, find, remove v čase závisiacom od dĺžky kľúča, ale nie od počtu kľúčov, ktoré už sú v strome | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
− | struct node { | + | struct node { // uzol prefixoveho stromu |
− | + | bool isWord; // je tento uzol koncom slova? | |
− | |||
− | bool isWord; // je tento | ||
node* next[Abeceda]; // pole smernikov na deti | node* next[Abeceda]; // pole smernikov na deti | ||
}; | }; | ||
Riadok 679: | Riadok 558: | ||
} | } | ||
struct node { | struct node { | ||
− | int | + | int data; |
node* next; | node* next; | ||
}; | }; |
Aktuálna revízia z 15:50, 5. december 2023
Obsah
Oznamy
Plán prednášok a cvičení na zvyšok semestra:
- Dnes informácie k skúške a posledná ukážka stromov
- V piatok nepovinné cvičenia
- V pondelok 11.12. nepovinná prednáška o nepreberaných črtách jazykov C a C++ (táto nepovinná časť učiva nebude vyžadovaná na skúške, ale môžete ju použiť).
- V utorok 12.12. v rámci cvičení tréning na skúšku.
- Na testovači už sú tréningové príklady na skúšku, jeden pribudne dnes týkajúci sa dnešného učiva. Za niektoré budete môcť získať bonusový bod, ak ich vyriešite do 11.1. (ako tréning sa dajú riešiť aj neskôr). V utorok na cvičeniach pribudne ešte jeden tréningový príklad za 4 body. Ak prídete na cvičenia a odovzdáte na konci aspoň rozumne rozrobenú verziu programu, získate jeden bonusový bod, aj keď ho nestihnete dokončiť.
- V stredu 13.12. 18:10 semestrálny test
- V piatok 15.12. od 13:10 predtermín skúšky, doplnkové cvičenia nebudú
Prefixové stromy
Prefixové stromy (niekde tiež lexikografické stromy; angl. trie zo slova retrieval) sú dátová štruktúra na uchovávanie množiny reťazcov. Ide o stromy, ktoré nemusia byť binárne:
- Uzol prefixového stromu má najviac toľko detí, koľko je znakov v uvažovanej abecede. Každé dieťa je označené iným znakom abecedy. Graficky si môžeme predstaviť tento znak prislúchajúci k hrane spájajúcej rodiča a dieťa.
- Koreň prefixového stromu zodpovedá prázdnemu reťazcu.
- Uzol v hĺbke k zodpovedá reťazcu dĺžky k, ktorý dostaneme prečítaním písmen na ceste z koreňa do daného uzla.
- Každý uzol prefixového stromu obsahuje logickú hodnotu vyjadrujúcu, či k nemu prislúchajúci reťazec patrí do množiny reprezentovanej týmto prefixovým stromom.
- V korektnom prefixovom strome všetky listy zodpovedajú reťazcom z reprezentovanej množiny.
- Vnútorné vrcholy môžu zodpovedať reťazcu z množiny alebo iba prefixu jedného alebo viacerých takých reťazcov.
Uzly prefixového stromu budeme reprezentovať štruktúrou node
- Uzol obsahuje obsahuje booleovskú premennú isWord, v ktorej je uložená informácia o tom, či reťazec prislúchajúci k danému uzlu patrí alebo nepatrí do reprezentovanej množiny a pole children smerníkov na jednotlivé deti daného uzla.
- Veľkosť alphSize tohto poľa je rovná veľkosti uvažovanej abecedy.
- V ukážkovom programe uvažujeme abecedu 'a'..'z'.
const int alphSize = 'z' - 'a' + 1;
struct node {
// pole smernikov na deti
node *children[alphSize];
// udava, ci uzol prislucha k slovu z reprezentovanej mnoziny
bool isWord;
};
Samotný prefixový strom je potom daný iba smerníkom na svoj koreň:
struct trie {
node *root;
};
Inicializácia a likvidácia prefixového stromu
Nasledujúca funkcia inicializuje prázdny prefixový strom t:
void init(trie &t) {
t.root = NULL;
}
Uvoľnenie pamäte alokovanej pre podstrom zakorenený v uzle root realizujeme obdobne ako pri binárnych vyhľadávacích stromoch. Jediný rozdiel spočíva v potenciálne väčšom počte detí uzla root.
void destroySubtree(node *root) {
if (root != NULL) {
for (int i = 0; i < alphSize; i++) {
destroySubtree(root->children[i]);
}
delete root;
}
}
Nasledujúca funkcia potom zlikviduje celý prefixový strom t:
void destroy(trie &t) {
destroySubtree(t.root);
}
Hľadanie v prefixovom strome
Funkcia contains pre daný prefixový strom t a reťazec word zistí, či slovo word patrí do množiny reprezentovanej stromom t.
- Postupuje po písmenách reťazca word. Kým nedôjde na koniec slova, snaží sa ísť po hranách, ktoré zodpovedajú jednotlivým písmenám.
- V prípade, že v niektorom bode narazí na NULL, slovo word sa v strome nenachádza.
- V opačnom prípade toto slovo dočíta v nejakom uzle v. V takom prípade slovo word patrí do reprezentovanej množiny práve vtedy, keď v->isWord má hodnotu true.
bool contains(trie &t, const char *word) {
node *v = t.root;
if (v == NULL) {
return false;
}
for (int i = 0; word[i] != 0; i++) {
int c = word[i] - 'a';
assert(c >= 0 && c < alphSize);
v = v->children[c];
if (v == NULL) {
return false;
}
}
return v->isWord;
}
Vkladanie do prefixového stromu
Pri vkladaní reťazca do množiny reprezentovanej prefixovým stromom potrebujeme vytvárať nové uzly. Túto podúlohu realizuje funkcia createNode, ktorá vytvorí nový uzol s hodnotou isWord danou jej argumentom a so všetkými smerníkmi na deti nastavenými na NULL.
node *createNode(bool isWord) {
node *v = new node;
for (int i = 0; i < alphSize; i++) {
v->children[i] = NULL;
}
v->isWord = isWord;
return v;
}
Vloženie reťazca word do prefixového stromu t vykoná funkcia add, ktorá pracuje nasledovne:
- Začne v koreni stromu, odkiaľ postupuje nižšie smerom k listom.
- V každom uzle sa pozrie na ďalšie písmeno slova word. Ak danému uzlu chýba dieťa pre toto písmeno, vytvorí ho pomocou funkcie createNode. Následne sa presunie do tohto dieťaťa.
- Keď v nejakom uzle v príde na koniec slova word, nastaví hodnotu v->isWord na true.
void add(trie &t, const char *word) {
if (t.root == NULL) {
t.root = createNode(false);
}
node *v = t.root;
for (int i = 0; word[i] != 0; i++) {
int c = word[i] - 'a';
assert(c >= 0 && c < alphSize);
if (v->children[c] == NULL) {
v->children[c] = createNode(false);
}
v = v->children[c];
}
v->isWord = true;
}
Vymazanie slova z prefixového stromu
Vymazávanie slov z množiny reprezentovanej prefixovým stromom budeme realizovať prostredníctvom pomocnej rekurzívnej funkcie removeFromSubtree.
- Funkcia z podstromu zakorenenom v uzle root vymaže sufix reťazca word začínajúci na pozícii index.
- Funkcia vráti booleovskú hodnotu podľa toho, či sa pri tomto vymazaní sufixu z daného podstromu vymazal jeho koreň root.
- Ak sa slovo word v reprezentovanej množine nenachádza, funkcia removeFromSubtree vyhlási chybu pomocou funkcie assert.
Funkcia removeFromSubtree pracuje nasledovne:
- Ak je sufix reťazca word začínajúci na indexe index prázdny, nastaví hodnotu root->isWord na false.
- V opačnom prípade funkcia removeFromSubtree zavolá rekurzívne samú seba pre dieťa zodpovedajúce písmenu na pozícii index reťazca word. Ak toto volanie dané dieťa zmaže, prestaví smerník na toto dieťa na NULL.
- V prípade, že po vykonaní jednej z predchádzajúcich dvoch operácií nemá uzol root žiadne dieťa a súčasne má root->isWord hodnotu false, uvoľní pamäť alokovanú pre uzol root a informáciu o jeho zmazaní vráti na výstupe.
Cvičenie: hoci mazanie neprehľadáva celý strom, iba jednu cestu z koreňa smerom dolu, naprogramovali sme ju rekurzívne. Na aký problén by sme narazili, ak by sme ju chceli naprogramovať cyklom? Pomohli by nám smerníky na rodiča v uzloch stromu?
bool removeFromSubtree(node *root, const char *word, int index) {
assert(root != NULL);
if (word[index] == 0) {
assert(root->isWord);
root->isWord = false;
} else {
int c = word[index] - 'a';
bool deleted = removeFromSubtree(root->children[c], word, index + 1);
if (deleted) {
root->children[c] = NULL;
}
}
int numChildren = 0;
for (int i = 0; i < alphSize; i++) {
if (root->children[i] != NULL) {
numChildren++;
}
}
if (numChildren == 0 && !root->isWord) {
delete root;
return true;
} else {
return false;
}
}
Samotné odstránenie reťazca word z množiny reprezentovanej stromom t potom realizuje funkcia remove.
void remove(trie &t, const char *word) {
// zavolame rekurziu pre koren stromu
bool rootRemoved = removeFromSubtree(t.root, word, 0);
// ak bol koren odstraneny, nastavime t.root na NULL
if (rootRemoved) {
t.root = NULL;
}
}
Výška prefixového stromu
Nasledujúca funkcia vypočíta výšku podstromu zakoreneného v uzle root:
int subtreeHeight(node *root) {
if (root == NULL) {
return -1;
}
int maxHeight = -1;
for (int i = 0; i < alphSize; i++) {
int height = subtreeHeight(root->children[i]);
if (height > maxHeight) {
maxHeight = height;
}
}
return maxHeight + 1;
}
Výšku samotného prefixového stromu t potom spočíta nasledujúca funkcia:
int height(trie &t) {
return subtreeHeight(t.root);
}
Vypisovanie slov reprezentovaných prefixovým stromom
Nasledujúca funkcia printSubtree prehľadáva podstrom zakorenený v uzle root a v reťazci str postupne generuje všetky slová z reprezentovanej množiny, ktoré zároveň vypisuje na konzolu. V parametri index dostane hĺbku aktuálneho vrcholu, t.j. pozíciu v reťazci, na ktorú pridáme ďalší znak.
void printSubtree(node *root, char *str, int index) {
if (root == NULL) {
return;
}
if (root->isWord) {
str[index] = 0; // ukoncenie retazca pred vypisom
printf("%s\n", str);
}
for (int i = 0; i < alphSize; i++) {
str[index] = 'a' + i;
printSubtree(root->children[i], str, index + 1);
}
}
Funkcia printAll vypisujúca všetky slová v množine reprezentovanej prefixovým stromom t najprv spočíta výšku stromu t, ktorá je rovná dĺžke najdlšieho reťazca tejto množiny. Následne dynamicky alokuje reťazec dostatočnej dĺžky na uchovanie každého slova množiny a zavolá funkciu printSubtree pre koreň stromu t.
void printAll(trie &t) {
int height = height(t);
if (height >= 0) {
char *str = new char[height + 1];
printSubtree(t.root, str, 0);
delete[] str;
}
}
V akom poradí budú slová vypísané?
Ukážka programu s prefixovým stromom, ADT slovník
Na vstupe máme text pozostávajúci zo slov s malými písmenami a pre každé slovo v texte chceme spočítať, koľkokrát sa tam nachádza.
- Jednotlivé slová uložíme pomocou prefixového stromu a v každom uzle si pamätáme namiesto hodnoty isWord počítadlo count, ktoré udáva, koľkokrát sme príslušné slovo videli na vstupe.
- Počítadlo má hodnotu nula pre prefixy vstupných slov, ktoré samé zatiaľ ako slovo na vstupe neboli.
- Namiesto funkcie treeInsert máme funkciu treeIncrement, ktorá dostane slovo a zvýši jeho počítadlo, pričom ak slovo zatiaľ v strome nebolo, tak ho pridá.
- Podobne by sme na tento účel vedeli upraviť aj implementáciu množiny pomocou binárneho vyhľadávacieho stromu, hašovacej tabuľky, poľa alebo zoznamu.
- Pozor, ak sú kľúče reťazce, na ich porovnanie musíme v týchto implementáciách použiť strcmp, nie ==, < a pod.
Abstraktný dátový typ, ktorý si okrem množiny kľúčov ku každému kľúču pamätá aj ďalšie dáta, sa zvykne nazývať slovník (angl. dictionary, map).
- Tu boli kľúče slová a ďalšie dáta počet výskytov.
- Iný príklad je zoznam kontaktov, kde kľúčom je meno osoby a pre dané meno chceme vrátiť kontaktné údaje danej osoby (emailová adresa, telefón a pod.)
#include <cstdio>
#include <cassert>
#include <cstring>
using namespace std;
const int alphSize = 'z' - 'a' + 1;
// uzol prefixoveho stromu
struct node {
// pole smernikov na deti
node *children[alphSize];
// pocet vyskytov slova prisluchajuceho uzlu
int count;
};
// cely prefixovy strom
struct trie {
node *root;
};
// inicializacia prazdneho stormu
void init(trie &t) {
t.root = NULL;
}
// mazanie podstromu s korenom root
void destroySubtree(node *root) {
if (root != NULL) {
for (int i = 0; i < alphSize; i++) {
destroySubtree(root->children[i]);
}
delete root;
}
}
// uvolnenie pamate celeho stromu
void destroy(trie &t) {
destroySubtree(t.root);
}
// vytvorenie noveo uzlu bez deti a s nula vyskytmi
node *createNode() {
node *v = new node;
for (int i = 0; i < alphSize; i++) {
v->children[i] = NULL;
}
v->count = 0;
return v;
}
// zvysenie pocitadla pre slovo word
// ak slovo este nie je v strome, je pridane
void increment(trie &t, const char *word) {
if (t.root == NULL) {
t.root = createNode();
}
node *v = t.root;
for (int i = 0; word[i] != 0; i++) {
int c = word[i] - 'a';
assert(c >= 0 && c < alphSize);
if (v->children[c] == NULL) {
v->children[c] = createNode();
}
v = v->children[c];
}
v->count++;
}
// vyska podstromu s korenom root
int subtreeHeight(node *root) {
if (root == NULL) {
return -1;
}
int maxHeight = -1;
for (int i = 0; i < alphSize; i++) {
int height = subtreeHeight(root->children[i]);
if (height > maxHeight) {
maxHeight = height;
}
}
return maxHeight + 1;
}
// vyska stromu. t.j. dlzka najdlsieho slova
int height(trie &t) {
return subtreeHeight(t.root);
}
// vypisanie slov v podstrome prefixoveho stromu
void printSubtree(node *root, char *str, int index) {
if (root == NULL) {
return;
}
if (root->count > 0) {
str[index] = 0; // ukoncenie retazca pred vypisom
printf("%s %d\n", str, root->count);
}
for (int i = 0; i < alphSize; i++) {
str[index] = 'a' + i;
printSubtree(root->children[i], str, index + 1);
}
}
// vypisanie slov prefixoveho stromu
void printAll(trie &t) {
int height = height(t);
if (height >= 0) {
char *str = new char[height + 1];
printSubtree(t.root, str, 0);
delete[] str;
}
}
int main() {
// inicializacia stromu
trie t;
init(t);
// postupne nacitavanie slov
char word[100];
while (true) {
int count = scanf("%99s", word);
if (count < 1) { // koniec vstupu
break;
}
// pridanie slova resp. zvysenie pocitadla
increment(t, word);
}
// vypis a uvolnenie pamate
printAll(t);
destroy(t);
}
Sylaby predmetu
Základy
Konštrukcie jazyka C
- premenné typov int, double, char, bool, konverzie medzi nimi
- podmienky (if, else, switch), cykly (for, while)
- funkcie (a parametre funkcií - odovzdávanie hodnotou, referenciou, smerníkom)
void f1(int x){} //hodnotou
void f2(int &x){} //referenciou
void f3(int* x){} //smerníkom
void f(int a[], int n){} //polia bez & (ostanú zmeny)
void kresli(Turtle &t){} //korytnačky, SVGdraw a pod. s &
Polia, reťazce (char[])
int A[4]={3, 6, 8, 10};
int B[4];
B[0]=3; B[1]=6; B[2]=8; B[3]=10;
char C[100] = "pes";
char D[100] = {'p', 'e', 's', 0};
- funkcie strlen, strcpy, strcmp, strcat
Súbory, spracovanie vstupu
- cin, cout alebo printf, scanf
- fopen, fclose, feof
- fprintf, fscanf
- getc, putc, ungetc, fgets, fputs
- spracovanie súboru po znakoch, po riadkoch, po číslach alebo slovách
Smerníky, dynamicky alokovaná pamäť, dvojrozmerné polia
int i; // „klasická“ celočíselná premenná
int *p; // ukazovateľ na celočíselnú premennú
p = &i; // spravne
p = &(i + 3); // zle i+3 nie je premenna
p = &15; // zle konstanta nema adresu
i = *p; // spravne ak p bol inicializovany
int * cislo = new int; // alokovanie jednej premennej
*cislo = 50;
..
delete cislo;
int a[4];
int *b = a; // a,b su teraz takmer rovnocenne premenne
int *a = new int[n]; // alokovanie 1D pola danej dlzky
..
delete[] a;
int **a; // alokovanie 2D matice
a = new int *[n];
for (int i = 0; i < n; i++) a[i] = new int[m];
..
for (int i = 0; i < n; i++) delete[] a[i];
delete[] a;
Abstraktné dátové typy
Abstraktný dátový typ dynamické pole (rastúce pole)
- operácie init, add, get, set, length
Abstraktný dátový typ dynamická množina (set)
- operácie init, contains, add, remove
- implementácie pomocou
- neutriedeného poľa
- utriedeného poľa
- spájaných zoznamov
- hašovacej tabuľky
- binárnych vyhľadávacích stromov
- prefixového stromu (ak kľúč je reťazec)
Abstraktné dátové typy rad a zásobník
- operácie pre rad (frontu, queue): init, isEmpty, enqueue, dequeue, peek
- operácie pre zásobník (stack): init, isEmpty, push, pop
- implementácie: v poli alebo v spájanom zozname
- využitie: ukladanie dát na spracovanie, odstránenie rekurzie
- kontrola zátvoriek a vyhodnocovanie výrazov pomocou zásobníka
Dátové štruktúry
Spájané zoznamy
struct node {
int data;
node* next;
};
struct linkedList {
node* first;
};
void insertFirst(linkedList &z, int d){
/* do zoznamu z vlozi na zaciatok novy prvok s datami d */
node* p = new node; // vytvoríme nový prvok
p->data = d; // naplníme dáta
p->next = z.first; // uzol ukazuje na doterajší začiatok
z.first = p; // tento prvok je novým začiatkom
}
Binárne stromy
struct node {
/* vrchol stromu */
dataType data;
node * left; /* lave dieta */
node * right; /* prave dieta */
};
node * createNode(dataType data, node *left, node *right) {
node *v = new node;
v->data = data;
v->left = left;
v->right = right;
return v;
}
- prehľadávanie inorder, preorder, postorder
- použitie na uloženie aritmetických výrazov
Binárne vyhľadávacie stromy
- vrcholy vľavo od koreňa menší kľúč, vpravo od koreňa väčší
- insert, find, remove v čase závisiacom od hĺbky stromu
Prefixové stromy
- ukladajú množinu reťazcov
- nie sú binárne: vrchol môže mať veľa detí
- insert, find, remove v čase závisiacom od dĺžky kľúča, ale nie od počtu kľúčov, ktoré už sú v strome
struct node { // uzol prefixoveho stromu
bool isWord; // je tento uzol koncom slova?
node* next[Abeceda]; // pole smernikov na deti
};
Hašovanie
- hašovacia tabuľka veľkosti m
- kľúč k premietneme nejakou funkciou na index v poli (0,...,m-1}
- každé políčko hašovacej tabuľky spájaný zoznam prvkov, ktoré sa tam zahašovali
- v ideálnom prípade sa prvky rozhodia pomerne rovnomerne, zoznamy krátke, rýchle hľadanie, vkladenie, mazanie
- v najhoršom prípade všetky prvky v jednom zozname, pomalé hľadanie a mazanie
int hash(int k, int m){ // veľmi jednoduchá hašovacia funkcia, v praxi väčšinou zložitejšie
return abs(k) % m;
}
struct node {
int data;
node* next;
};
struct set {
node** data;
int m;
};
Algoritmy
Rekurzia
- Rekurzívne funkcie
- Vykresľovanie fraktálov
- Prehľadávanie s návratom (backtracking)
- Vyfarbovanie
- Prehľadávanie stromov
Triedenia
- nerekurzívne: Bubblesort, Selectionsort, Insertsort
- rekurzívne: Mergesort, Quicksort
- súvisiace algoritmy: binárne vyhľadávanie
Matematické úlohy
- Euklidov algoritmus, Eratostenovo sito
- Práca s aritmetickými výrazmi: vyhodnocovanie postfixovej formy, prevod z infixovej do postfixovej, reprezentácia vo forme stromu