>> SPEAKER 1: Dajme toto riešenie vyskúšať.
Takže poďme sa pozrieť na to, čo naše Struct uzol bude vyzerať.
Tu vidíme, že budeme mať Bool Word a struct uzol hviezda
Deti bracketing abecedu.
Takže prvá vec, ktorú by ste mohli byť zvedaví, Preto je abeceda hash definovaná ako 27?
No, pamätajte, že budeme potrebovať sa manipulácia apostrof, tak
že to bude trochu zvláštne puzdro na celom tomto programe.
>> OK, teraz si spomenúť, ako Trie skutočne funguje.
Povedzme, že sme indexovanie slovo mačky, potom z koreňa našej Trie,
ideme sa pozrieť na deti pole, a budeme sa pozerať na
index, ktorý odpovedá na list C. Tak že by index dva.
Takže vzhľadom k tomu, že sa nám nový uzol, a potom budeme
práce z tohto uzla.
>> Takže za predpokladu, že uzol, sme opäť sa pozrieme na poli deti,
a ideme sa pozrieť na indexe nula tak, aby zodpovedal A v mačky.
Takže sme ísť do tohto uzla, a vzhľadom k tomu, že uzol, ideme
sa pozrieť na index, ktorý zodpovedá na T. a pohybuje sa na tomto uzle,
Nakoniec sme úplne pozrel prostredníctvom našej slovo mačka, a teraz Bool
Slovo má ukázať, či to dané slovo je vlastne slovo.
>> Tak prečo potrebujeme ten zvláštny prípad?
No, čo keď slovo katastrofa je v našom slovníku, ale
slovo mačka nie je?
Takže v pohľade, či je slovo mačka v našom slovníku, budeme
úspešne prezrieť indexov C-A-T a dosiahnuť uzol, ale to je
len preto, že katastrofa sa stalo vytvárať uzly na ceste z C-A-T všetky
spôsob, ako sa na konci slova.
Takže Bool Word sa používa uveďte, či Tento konkrétny miesto skutočne
označuje slovo.
>> Dobre, tak teraz, keď vieme, čo Trie bude vyzerať, poďme sa pozrieť
na funkciu Load.
Takže zaťaženie sa chystá vrátiť Bool na tom, či sa nám podarilo alebo
neúspešne načítať slovník a to bude slovník
ktoré chceme načítať.
Takže prvá vec, ktorú sa chystáte urobiť, je otvoriť do tohto slovníka pre čítanie.
Musíme sa uistiť, že nesklamal, takže ak slovník nebol
úspešne otvorený, vráti No, v tom prípade budeme
vráti False.
Avšak za predpokladu, že sa úspešne otvoril, potom môžeme skutočne čítať
pomocou slovníka.
>> Takže prvá vec, ktorú budeme chcete urobiť, je, že sme si to
globálna premenná koreň.
Teraz, koreň sa bude uzol hviezda.
Je to vrchol našej Trie, že sme bude iterácie.
Takže prvá vec, ktorú budeme chcieť urobiť, je alokovať pamäť pre náš koreň.
>> Všimnite si, že sme pomocou calloc funkcia, ktorá je v podstate rovnaká
ako funkcia malloc, okrem toho, že je zaručené, že vráti niečo, čo je
úplne vynuluje.
Takže ak sme použili malloc, potrebovali by sme, aby prejsť všetky ukazovatele v našej
uzol a uistite sa, že všetci sú null.
Takže calloc to urobí za nás.
>> Teraz, rovnako ako malloc, je potrebné, aby Uistite sa, že rozdelenie je v skutočnosti
úspešný.
Ak to vrátil null, potom je potrebné uzavrieť našu slovník
súboru a vráti False.
Takže za predpokladu, že rozdelenie bolo úspešná, budeme používať uzol
hviezda kurzor na iteráciu prostredníctvom našej Trie.
Takže naše koreň sa nikdy nezmení, ale budeme používať kurzor na
skutočne ísť z uzla do uzla.
>> Dobre, takže v tomto pre sláčiky, sme prečítaní súboru slovníka,
a budeme používať na fgetc.
Takže fgetc sa chystá chytiť jeden znak zo súboru.
Budeme pokračovať v popada znaky, zatiaľ čo my nedosahujú
koniec súboru, takže sú dve prípadov musíme zvládnuť.
Prvý z nich, v prípade, že znak nebol nová linka, takže vieme, že keby to bol nový
linka, potom sa chystáme prejsť na nové slovo.
Ale za predpokladu, že nebol nový riadok, potom tu, chceme zistiť,
index ideme do indexu do v poli Deti, ktoré
sme sa pozreli na pred.
>> Takže ako som povedal predtým, je potrebné, aby Zvláštnym prípadom apostrof.
Všimnite si, sme pomocou ternárnu operátor tu, tak budeme čítať
to, ako keby postava čítame v to apostrof, potom budeme
nastaviť index sa rovná abecedy mínus 1, ktorý bude index 26..
Inak, ak to nie je apostrof, potom budeme nastaviť index
rovná c mínus.
Takže pamätajte späť z predchádzajúcich p sád, c mínus sa chystá dať nám
abecedný pozície c, takže ak c je písmeno, to bude
nám index nula.
Pre bod B, bolo by to dať nám index 1, a tak ďalej.
>> Tak to nám dáva index do Deti pole, ktoré chceme.
Teraz, v prípade, že index je v súčasnej dobe v null Deti poľa, to znamená, že
uzol nemá v súčasnej dobe neexistuje z , Že cesta, takže musíme prideliť
uzol pre túto cestu.
To je to, čo robíme tu.
Takže budeme opäť používať calloc funkcie, takže nemáme
k vynulovanie všetkých ukazovateľov, a my, znovu, je potrebné skontrolovať, že calloc
nesklamal.
Ak calloc to nepodarí, potom musíme vyložiť všetko, zatvoríme
slovník, a vráti False.
>> Takže za predpokladu, že to nebolo zlyhanie, potom to bude vytvoriť novú dieťa pre nás,
a potom pôjdeme na to dieťa.
Naše kurzor bude prechádzať sa k tomuto dieťaťu.
Teraz, ak to nie je null začať s, potom sa kurzor môže iba iterovat
sa k tomuto dieťaťu, bez toho by v skutočnosti museli prideliť nič.
To je prípad, kedy sme sa prvýkrát stalo prideliť slovo mačka, a
to znamená, že keď ideme na pridelenie katastrofa, nepotrebujeme vytvárať
uzly pre C-A-T znova.
Už existujú.
>> OK, takže to, čo je to iný?
To je stav, kedy c je spätné lomítko n, kde c je nová linka.
To znamená, že sa nám podarilo mať dokončil slovo.
A teraz, čo chceme robiť, keď sme úspešne dokončil slovo?
Budeme používať toto slovo pole v našej struct uzol.
>> Chceme nastaviť, aby sa na True, aby znamená, že tento uzol označuje
úspešný slovo skutočné slovo.
Teraz nastavte, že na hodnotu TRUE.
Chceme obnoviť naše kurzor na miesto na začiatku Trie znova.
A konečne, zvýšiť náš slovník veľkosť, pretože sme našli ďalšie slovo.
>> Dobre, takže budeme pokračovať v tom , Že čítanie v znaku
charakter, výstavbu nových uzlov v naše Trie a pre každé slovo v
slovník, až sme konečne dosiahnuť c rovná EOF, v tomto prípade sme sa zlomiť
zo súboru.
Teraz máme k dispozícii dva prípady podľa ktoré sme mohli zasiahnuť EOF.
Prvý z nich je, či došlo k chybe čítanie zo súboru, takže v prípade, že bol
chyba, ktorú musíme urobiť, typické vyložiť všetko, zatvorte súbor,
vráti False.
Za predpokladu, že nie je chyba, ktorá len znamená, že sme vlastne hit na koniec
súbor, v tom prípade, zatvoríme súbor a vrátiť True, pretože sme
úspešne načítaný slovníka do nášho Trie.
>> Dobre, tak teraz poďme pozrite sa na kontrolu.
Pri pohľade na Skontrolujte funkciu, vidíme, ktorá Kontrola sa chystá vrátiť Bool.
Vracia TRUE, ak to slovo, ktoré je boli prenesené, je v našom Trie.
Vracia False inak.
>> Tak ako sa budeme na určenie, či toto slovo je v našom Trie?
Vidíme tu, že rovnako ako predtým, budeme používať kurzor na iteráciu
prostredníctvom našej Trie.
Teraz, tu, ideme na iteráciu v celom našom slova.
Takže iterácia cez slovo sme prešiel, ideme zistiť,
index do poľa detí, ktoré zodpovedá slovo konzola i
Takže to bude vyzerať presne ako Zaťaženie, kde ak slovo držiak aj je
apostrof, potom chceme použiť index abeceda mínus 1, pretože sme zistili,
že je miesto, kde budeme uložiť apostrofy.
>> Inak budeme používať tolower Slovo držiak i
Takže nezabudnite, že slovo môže mať ľubovoľný kapitalizácie, a tak sme
chcete, aby sa ubezpečil, že sme pomocou malá verzia vecí.
A potom odpočítať od tej malými písmenami na, opäť nám
abecedný pozície tohto charakteru.
Tak, že to bude náš index do poľa deti.
>> A teraz, či je to index do detí pole je null, to znamená, že
už nemôže pokračovať iterácie sa našej Trie.
Ak je tomu tak, nemôže toto slovo nie je mohlo byť v našom Trie, pretože v prípade, že
sa, že by to znamenalo, že by sa Cesta dole do tohto slova, a vy by
nikdy stretnúť null.
Takže stretnutie null, vrátime False.
Slovo nie je v slovníku.
Ak by tomu tak nebolo null, potom budeme pokračovať iterácie, takže ideme
aktualizovať naše kurzor poukázať na to najmä uzol v danom indexe.
>> Tak sme sa pokračovať v tom, že po celú dobu celé slovo.
Za predpokladu, že sme sa nikdy hit null, že prostriedky sme boli schopní sa dostať cez celé
svet a nájsť uzol v našom Trie, ale my nie sme úplne neskončil.
Nechceme sa len vrátiť true.
Chceme sa vrátiť kurzor chybovú slovo pretože pamätať znovu, pokiaľ nie je mačka
v našom slovníku a katastrofa je, potom budeme úspešne prejsť
slovo mačka, ale kurzor slovo bude False a nie je pravda.
Takže sa vrátime kurzora slovo pre označenie či tento uzol je vlastne slovo,
a je to pre kontrolu.
>> Takže poďme sa pozrieť na veľkosť.
Takže veľkosť bude celkom jednoduché pretože, pamätajte na zaťaženie, sme
zvyšovanie veľkosť slovníka pre každé slovo, že sa stretávame.
Takže Veľkosť sa práve chystá k návratu slovník veľkosti, a to je všetko.
>> Dobre, takže nakoniec máme Uvoľniť.
Takže uvoľniť, budeme používať rekurzívne funkcie, ktorá vlastne robiť všetko
práca pre nás, tak naše funkcie sa bude nazývaný Unloader.
Čo je Unloader robiť?
Vidíme tu, že Unloader sa chystá iterovat cez všetky deti na
Tento konkrétny uzol, a v prípade, že dieťa uzol nie je null, potom budeme
vyložiť podriadený uzol.
>> Takže to bude rekurzívne vyložiť všetky naše deti.
Potom, čo sme si istí, že všetky naše deti boli vyložené, a potom sme
môže oslobodiť, tak vyložiť sami.
Takže to bude rekurzívne uvoľniť Celý Trie, a potom ešte raz, že je
hotovo, môžeme len vrátiť true.
Uvoľniť nemôže zlyhať, že sme len uvoľnenie veci.
Takže akonáhle sme hotoví uvoľnenie všetko, vráti hodnotu true.
A to je všetko.
Volám sa Rob, a to bol [nepočuteľný].