>> SPEAKER 1: Dejme toto řešení vyzkoušet.
Takže pojďme se podívat na to, co naše Struct uzel bude vypadat.
Zde vidíme, že budeme mít Bool Word a struct uzel hvězda
Děti bracketing abecedu.
Takže první věc, kterou byste mohli být zvědaví, Proto je abeceda hash definována jako 27?
No, pamatujte, že budeme potřebovat se manipulace apostrof, tak
že to bude poněkud zvláštní pouzdro na celém tomto programu.
>> OK, teď si vzpomenout, jak Trie skutečně funguje.
Řekněme, že jsme indexování slovo kočky, pak z kořene naší Trie,
jdeme se podívat na děti pole, a budeme se dívat na
index, který odpovídá na dopis C. Tak že by index dva.
Takže vzhledem k tomu, že se nám nový uzel, a pak budeme
práce z tohoto uzlu.
>> Takže za předpokladu, že uzel, jsme opět se podíváme na poli děti,
a jdeme se podívat na indexu nula tak, aby odpovídal A v kočky.
Takže jsme jít do tohoto uzlu, a vzhledem k tomu, že uzel, jedeme
se podívat na index, který odpovídá na T. a pohybuje se na tomto uzlu,
Nakonec jsme zcela podíval prostřednictvím naší slovo kočka, a teď Bool
Slovo má ukázat, zda to dané slovo je vlastně slovo.
>> Tak proč potřebujeme ten zvláštní případ?
No, co když slovo katastrofa je v našem slovníku, ale
slovo kočka není?
Takže v pohledu, zda je slovo kočka v našem slovníku, budeme
úspěšně prohlédnout indexů C-A-T a dosáhnout uzel, ale to je
jen proto, že katastrofa se stalo vytvářet uzly na cestě z C-A-T všechny
způsob, jak se na konci slova.
Takže Bool Word se používá uveďte, zda Tento konkrétní místo skutečně
označuje slovo.
>> Dobře, tak teď, když víme, co Trie bude vypadat, pojďme se podívat
na funkci Load.
Takže zatížení se chystá vrátit Bool na tom, zda se nám podařilo nebo
neúspěšně načíst slovník a to bude slovník
které chceme načíst.
Takže první věc, kterou se chystáte udělat, je otevřít do tohoto slovníku pro čtení.
Musíme se ujistit, že nezklamal, takže pokud slovník nebyl
úspěšně otevřen, vrátí No, v tom případě budeme
vrátí False.
Avšak za předpokladu, že se úspěšně otevřel, pak můžeme skutečně číst
pomocí slovníku.
>> Takže první věc, kterou budeme chcete udělat, je, že jsme si to
globální proměnná kořen.
Nyní, kořen se bude uzel hvězda.
Je to vrchol naší Trie, že jsme bude iterace.
Takže první věc, kterou budeme chtít udělat, je alokovat paměť pro náš kořen.
>> Všimněte si, že jsme pomocí calloc funkce, která je v podstatě stejná
jako funkce malloc, kromě toho, že je zaručeno, že vrátí něco, co je
zcela vynuluje.
Takže pokud jsme použili malloc, potřebovali bychom, aby projít všechny ukazatele v naší
uzel a ujistěte se, že všichni jsou null.
Takže calloc to udělá za nás.
>> Nyní, stejně jako malloc, je třeba, aby Ujistěte se, že rozdělení je ve skutečnosti
úspěšný.
Pokud to vrátil null, pak je třeba uzavřít naši slovník
souboru a vrátí False.
Takže za předpokladu, že rozdělení bylo úspěšná, budeme používat uzel
hvězda kurzor na iteraci prostřednictvím naší Trie.
Takže naše kořen se nikdy nezmění, ale budeme používat kurzor na
skutečně jít z uzlu do uzlu.
>> Dobře, takže v tomto pro smyčce, jsme přečtení souboru slovníku,
a budeme používat na fgetc.
Takže fgetc se chystá chytit jeden znak ze souboru.
Budeme pokračovat v popadat znaky, zatímco my nedosahují
konec souboru, takže jsou dvě případů musíme zvládnout.
První z nich, v případě, že znak nebyl nová linka, takže víme, že kdyby to byl nový
linka, pak se chystáme přejít na nové slovo.
Ale za předpokladu, že nebyl nový řádek, pak tady, chceme zjistit,
index jedeme do indexu do v poli Děti, které
jsme se podívali na před.
>> Takže jak jsem řekl dříve, je třeba, aby Zvláštním případem apostrof.
Všimněte si, jsme pomocí ternární operátor tady, tak budeme číst
to, jako kdyby postava čteme v to apostrof, pak budeme
nastavit index se rovná abecedy minus 1, který bude index 26..
Jinak, pokud to není apostrof, pak budeme nastavit index
rovna c mínus.
Takže pamatujte zpět z dřívějších p sad, c minus se chystá dát nám
abecední pozice c, takže pokud c je písmeno, to bude
nám index nula.
Pro písmeno B, bylo by to dát nám index 1, a tak dále.
>> Tak to nám dává index do Děti pole, které chceme.
Nyní, v případě, že index je v současné době v null Děti pole, to znamená, že
uzel nemá v současné době neexistuje z , že cesta, takže musíme přidělit
uzel pro tuto cestu.
To je to, co děláme tady.
Takže budeme opět používat calloc funkce, takže nemáme
k vynulování všech ukazatelů, a my, znovu, je třeba zkontrolovat, že calloc
nezklamal.
Pokud calloc to nepodaří, pak musíme vyložit všechno, zavřeme
slovník, a vrátí False.
>> Takže za předpokladu, že to nebylo selhání, pak to bude vytvořit novou dítě pro nás,
a pak půjdeme na to dítě.
Naše kurzor bude přecházet se k tomuto dítěti.
Nyní, pokud to není null začít s, pak se kurzor může pouze iterovat
se k tomuto dítěti, aniž by ve skutečnosti museli přidělit nic.
To je případ, kdy jsme se poprvé stalo přidělit slovo kočka, a
to znamená, že když jdeme na přidělení katastrofa, nepotřebujeme vytvářet
uzly pro C-A-T znovu.
Již existují.
>> OK, takže to, co je to jiný?
To je stav, kdy c je zpětné lomítko n, kde c je nová linka.
To znamená, že se nám podařilo mít dokončil slovo.
A teď, co chceme dělat, když jsme úspěšně dokončil slovo?
Budeme používat toto slovo pole v naší struct uzel.
>> Chceme nastavit, aby se na True, aby znamená, že tento uzel označuje
úspěšný slovo skutečné slovo.
Nyní nastavte, že na hodnotu TRUE.
Chceme obnovit naše kurzor na místo na začátku Trie znovu.
A konečně, zvýšit náš slovník velikost, protože jsme našli další slovo.
>> Dobře, takže budeme pokračovat v tom , že čtení v znaku
charakter, výstavbu nových uzlů v naše Trie a pro každé slovo v
slovník, až jsme konečně dosáhnout c rovná EOF, v tomto případě jsme se zlomit
ze souboru.
Nyní máme k dispozici dva případy podle které jsme mohli zasáhnout EOF.
První z nich je, zda došlo k chybě čtení ze souboru, takže v případě, že byl
chyba, kterou musíme udělat, typické vyložit vše, zavřete soubor,
vrátí False.
Za předpokladu, že není chyba, která jen znamená, že jsme vlastně hit na konec
soubor, v tom případě, zavřeme soubor a vrátit True, protože jsme
úspěšně načten slovníku do našeho Trie.
>> Dobře, tak teď pojďme podívejte se na kontrolu.
Při pohledu na Zkontrolujte funkci, vidíme, která Kontrola se chystá vrátit Bool.
Vrací TRUE, pokud to slovo, které je byly přeneseny, je v našem Trie.
Vrací False jinak.
>> Tak jak se budeme k určení, zda toto slovo je v našem Trie?
Vidíme zde, že stejně jako předtím, budeme používat kurzor na iteraci
prostřednictvím naší Trie.
Teď, tady, jedeme na iteraci v celém našem slova.
Takže iterace přes slovo jsme prošel, jdeme zjistit,
index do pole dětí, které odpovídá slovo konzole i.
Takže to bude vypadat přesně jako Zatížení, kde pokud slovo držák i je
apostrof, pak chceme použít index abeceda minus 1, protože jsme zjistili,
že je místo, kde budeme uložit apostrofy.
>> Jinak budeme používat tolower Slovo držák i.
Takže nezapomeňte, že slovo může mít libovolný kapitalizace, a tak jsme
chcete, aby se ujistil, že jsme pomocí malá verze věcí.
A pak odečíst od té malými písmeny na, opět nám
abecední pozice tohoto charakteru.
Tak, že to bude náš index do pole děti.
>> A teď, jestli je to index do dětí pole je null, to znamená, že
již nemůže pokračovat iterace se naší Trie.
Pokud je tomu tak, nemůže toto slovo není mohlo být v našem Trie, protože v případě, že
se, že by to znamenalo, že by se Cesta dolů do tohoto slova, a vy by
nikdy setkat null.
Takže setkání null, vrátíme False.
Slovo není ve slovníku.
Pokud by tomu tak nebylo null, pak budeme pokračovat iterace, takže jdeme
aktualizovat naše kurzor poukázat na to zejména uzel v daném indexu.
>> Tak jsme se pokračovat v tom, že po celou dobu celé slovo.
Za předpokladu, že jsme se nikdy hit null, že prostředky jsme byli schopni se dostat přes celé
svět a najít uzel v našem Trie, ale my nejsme úplně neskončil.
Nechceme se jen vrátit true.
Chceme se vrátit kurzor chybovou slovo protože pamatovat znovu, pokud není kočka
v našem slovníku a katastrofa je, pak budeme úspěšně projít
slovo kočka, ale kurzor slovo bude False a není pravda.
Takže se vrátíme kurzoru slovo pro označení zda tento uzel je vlastně slovo,
a je to pro kontrolu.
>> Takže pojďme se podívat na velikost.
Takže velikost bude docela snadné protože, pamatujte na zatížení, jsme
zvyšování velikost slovníku pro každé slovo, že se setkáváme.
Takže Velikost se právě chystá k návratu slovník velikosti, a to je vše.
>> Dobře, takže nakonec máme Uvolnit.
Takže uvolnit, budeme používat rekurzivní funkce, která vlastně dělat vše
práce pro nás, tak naše funkce se bude nazýván Unloader.
Co je Unloader dělat?
Vidíme zde, že Unloader se chystá iterovat přes všechny děti na
Tento konkrétní uzel, a v případě, že dítě uzel není null, pak budeme
vyložit podřízený uzel.
>> Takže to bude rekurzivně vyložit všechny naše děti.
Poté, co jsme si jisti, že všechny naše děti byly vyloženy, a pak jsme
může osvobodit, tak vyložit sami.
Takže to bude rekurzivně uvolnit Celý Trie, a pak ještě jednou, že je
hotovo, můžeme jen vrátit true.
Uvolnit nemůže selhat, že jsme jen uvolnění věci.
Takže jakmile jsme hotovi uvolnění vše, vrátí hodnotu true.
A to je vše.
Jmenuji se Rob, a to byl [neslyšitelný].