Tímto úkolem začíná série úkolů, během níž budete implementovat jednoduchou variantu prefixového stromu (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.
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í zde.
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.
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é.
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 <string> #include <iostream> int main() { std::string s = "Hello world"; const char* sptr = s.c_str(); while (*sptr) { std::cout << *sptr << '\n'; sptr++; } }
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ý.
Pro tento úkol žádné hlavičky ze standardní knihovny nedoporučujeme.