{{page>courses:b6b36pjc:styles#common&noheader&nofooter}}
{{page>courses:b6b36pjc:styles#ukoly&noheader&nofooter}}
===== Trie 1 =====
Tímto úkolem začíná série úkolů, během níž budete implementovat jednoduchou
variantu prefixového stromu ([[https://en.wikipedia.org/wiki/Trie|Trie]])
ve stylu standardní knihovny. Varianta, kterou budete implementovat, reprezentuje
každý znak jedním uzlem a má připravené odkazy pro každého možného potomka.
Tato varianta je zbytečně paměťově náročná, ale jednoduchá k implementaci.
/*
Pokud chceme vlastni obrazek, generujici dot:
digraph G {
"" -> "A"
"A" -> "B"
"B"[color=green penwidth=5]
"C" [color=green penwidth=5]
"V" [color=green penwidth=5]
"P" [color=green penwidth=5]
"" -> "P"
"P" -> "J"
"J" -> "C"
"J" -> "V"
}
*/
V tomto úkolu začneme vytvořením struktury ''trie'', která zastřešuje interní
data skládající se z uzlů reprezentovaných ''trie_node''. Jejich popis najdete níže.
// Assume only basic ASCII characters
static const size_t num_chars = 128;
struct trie_node {
trie_node* children[num_chars] = {};
trie_node* parent = nullptr;
char payload = 0;
bool is_terminal = false;
};
struct trie {
trie_node* root = nullptr;
size_t size = 0;
};
* ''trie::root'' je ukazatel na kořenový uzel stromu
* ''trie::size'' je počet unikátních slov, které trie obsahuje
* ''trie_node::children'' je pole ukazatelů na přímé následovníky daného uzlu
* ''trie_node::parent'' je ukazatel na přímého předka daného uzlu
* ''trie_node::payload'' je znak, který tento uzel reprezentuje
* ''trie_node::is_terminal'' označuje, jestli v tomto uzlu končí slovo
Potřebné hlavičkové soubory a testy ke stažení
{{:courses:b6b36pjc:ukoly:trie-1.zip|zde}}.
==== Co odevzdat? ====
Jeden nebo více ''.cpp'' souborů, které implementují funkce deklarované v
souboru ''trie.hpp'' tak, aby testy procházely a neztrácela se paměť. Při práci
na úkolu soubor ''trie.hpp'' neměňte.
===== Rady =====
Testy jsou schválně dělané tak, aby bylo možné se ve stromu pohybovat pomocí
rekurze. Tedy se vám ani při naivní implementaci nestane, že vám dojde místo
na stacku, a doporučujeme tedy při implementaci různých operací přemýšlet
rekurzivně.
Stejně tak doporučujeme implementovat plnění všech dat do uzlů. V tomto úkolu se
bez toho obejdete, ale ty následující je budou využívat a je snadnější to udělat
napoprvé.
==== Rekurzivní průchod std::string ====
Funkce pracující s trií dostávají jako argument ''std::string const&''. Abyste
si nemuseli vždy předávat referenci na ''std::string'' a index, kde zrovna
v průchodu jste, můžete si ze ''std::string'' vzít ukazatel na C-style
řetězec.
Následující kód projde a vypíše celý řetězec ze ''std::string'' bez použití délky.
Podobným způsobem se můžete posouvat v řetězci uvnitř trie.
#include
#include
int main() {
std::string s = "Hello world";
const char* sptr = s.c_str();
while (*sptr) {
std::cout << *sptr << '\n';
sptr++;
}
}
==== Přístup ke smazané paměti ====
Dávejte si pozor na přístup ke smazané paměti, protože jakmile jednou kus paměti
uvolníte, všechna data v ní jsou pro vás ztracena. To znamená, že například při
mazání trie je potřeba každému uzlu nejdříve smazat potomky, a až potom uzel samotný.
==== Užitečné hlavičky ====
Pro tento úkol žádné hlavičky ze standardní knihovny nedoporučujeme.