[MUSIC PLAYBACK] 

ROB BOWDEN: Ahoj. Som Rob. A nech je to riešenie von. Takže tu budeme realizovať všeobecné tabuľky. Vidíme, že struct uzol našej tabuľka bude vyzerať takto. Takže to bude mať char slovo Pole Veľkosť Dĺžka + 1. Nezabudnite + 1, pretože maximálna slovo v slovníku je 45 znaky. A potom budeme potrebovať jeden navyše znak pre spätné lomítko nulu. 

A potom naše Hashtable v každom vedro sa bude ukladať spájať zoznam uzlov. Nerobíme lineárne snímacie tu. A tak, aby odkazy na ďalšie prvok v vedre, musíme struct uzol * ďalšie. OK. Takže to je to, čo uzol vyzerá. 

Teraz je tu vyhlásenie našej Hashtable. Bude to mať 16.834 vedierka. Ale to číslo nezáleží. A konečne budeme mať globálna premenná veľkosť Hashtable, ktoré sa chystá začať ako nula. A to bude mať prehľad o tom, ako veľa slov sú v našom slovníku. 

Takže poďme sa pozrieť na zaťaženie. Všimnite si, že záťaž, vracia bool. Môžete sa vrátiť true, ak bolo úspešné naložené, a v opačnom prípade false. A to trvá const char * slovníka, čo je slovník ktorý chceme otvoriť. Takže to je prvá vec, budeme robiť. 

Ideme do fopen slovník čítanie. A budeme musieť urobiť Uistite sa, že sa jej podarilo. Takže ak to vrátil NULL, potom nie úspešne otvoriť slovník. A my sa musíme vrátiť false. Ale za predpokladu, že to úspešne urobil otvorené, potom chceme prečítať slovník. Takže majte opakovanie, kým nenájdeme nejaký dôvod, aby sa vymanili z tejto slučky, ktoré uvidíme. Takže majte opakovanie. 

A teraz ideme na malloc jeden uzol. A samozrejme musíme vysielať znovu skontrolujte. Takže ak mallocing neuspel, potom chceme vyložiť ľubovoľný uzol, ktorý my stalo malloc pred zavrite slovník a vráti false. Ale ignorovať, že za predpokladu, že sa podarilo, potom chceme použiť fscanf prečítať jediné slovo z našej slovník do nášho uzla. Takže pamätajte, že vstupné slovo> je char Slovo vyrovnávaciu pamäť o veľkosti lenghth + 1 že budeme ukladať slovo palcov 

Takže fscanf bude vrátiť 1, ak ako to bolo schopné úspešne čítať slovo zo súboru. Pokiaľ to buď chyba sa stane, alebo sa dostať sa na koniec súboru, nevráti 1.. V takomto prípade nevracia 1, sme sa konečne chystá vypuknúť Tento cyklus while. Takže vidíme, že raz sa nám podarilo mať čítať slovo do entry> slovo, potom ideme na to Slovo pomocou nášho hash funkcie. 

Poďme sa pozrieť na funkcia hash. Takže nemáte naozaj potrebujete to pochopiť. A vlastne sme práve vytiahol tento hash funkcie z internetu. Jediná vec, ktorú je potrebné si uvedomiť, je že to trvá const char * slovo. Tak to trvá reťazec ako vstup, a vrátením unsigned int ako výstup. Tak to je všetko, funkcia hash je, je to berie na vstup a dá vám index do Hashtable. 

Všimnite si, že sme moding by NUM_BUCKETS, tak, že vrátená hodnota v skutočnosti je index do Hashtable a nie je index za medze poľa. Takže za predpokladu, že funkcie, ideme hash slovo, ktoré čítame slovník. A potom budeme používať že hashovacie vložiť vstup do Hashtable. 

Teraz Hashtable hash je aktuálne spojené zoznamu v tabuľke. A to je veľmi možné, že je to len NULL. Chceme vložiť náš vstup na začiatku tohto prepojeného zoznamu. A tak budeme mať našu aktuálnu vstupný bod do akej Hashtable V súčasnej dobe poukazuje na. A potom budeme ukladať, v Hashtable na hash, aktuálny záznam. Takže tieto dva riadky úspešne vložiť Vstup na začiatku spájať zoznam v tomto indexe v Hashtable. 

Akonáhle sme hotoví s tým, vieme, že sme našli ďalšie slovo slovník, a my sme opäť zvyšovať. Tak sme to robiť, kým fscanf nakoniec sa vrátil niečo non-1 na ktorý bod si uvedomiť, že musíme vstup zadarmo. Tak tu sme malloced položku. A my sme sa snažili niečo prečítať zo slovníka. A my sme nemali úspešne čítať niečo zo slovníka, v takomto prípade musíme uvoľniť vstup že sme vlastne nikdy dať do Hashtable, a konečne zlomiť. 

Potom, čo sme vypukne musíme vidieť, dobre, sme sa zlomiť, pretože tam bola chyba pri čítaní zo súboru? Alebo sme sa zlomiť, pretože sme došli na koniec súboru? Ak došlo k chybe, potom Chceme sa vrátiť false. Vzhľadom k tomu, zaťaženie neuspel. A v tomto procese chceme vyložiť všetky slová, ktoré čítame v, a zatvorte súbor slovníka. 

Za predpokladu, že sme sa to podarí, potom sme len Stále je potrebné zavrieť slovník súbor, a nakoniec sa vrátiť true, pretože sme úspešne načítaný slovníka. A to je pre zaťaženie. Takže teraz zistiť, vzhľadom k tomu naložené Hashtable, bude vyzerať takto. Tak sa pozrite, vracia bool, ktorý je bude uvádzať, či prešiel v char * slovo, či už prešiel v reťazci je v našom slovníku. Takže, ak je v slovníku, v prípade, že je v našom Hashtable, budeme vráti hodnotu true. A ak to tak nie je, vrátime false. 

Vzhľadom k tomu, to prešiel v slove, my sme bude hash slovo. Teraz dôležité si uvedomiť, je že v záťaži vedeli sme, že všetky slová, že budeme mať malé písmená. Ale tu nie sme tak istí. Ak sa pozrieme na náš hash funkcie, naše hash funkcia vlastne je nižšia plášť každý znak slová. Takže bez ohľadu na kapitalizácie Slovo, náš hash funkcia je návrat rovnaký index na čokoľvek kapitalizácie je, ako to bude mať sa vrátil k úplne malá verzie slová. Dobre. To je náš index je do Hashtable pre toto slovo. 

Teraz to pre sláčiky bude iterácii spojovaceho zoznamu ktorá bola v danom indexe. Takže všimnete sme inicializácii vstup poukázať na danom indexe. Budeme pokračovať zatiaľ čo vstup! = NULL. A nezabudnite, že aktualizácia ukazovateľ v našom súvisí položka v zozname = entry> ďalšie. Takže máme aktuálne vstupný bod do Ďalším bodom v prepojenom zozname. 

Takže pre každú položku v prepojenom zoznamu, budeme používať strcasecmp. Nie je to StrComp. Pretože raz, chceme robiť veci prípad necitlivo. Tak sme sa použiť strcasecmp k porovnání Slovo, ktoré bolo prešiel tento funkcia proti slovu že je v tejto položke. Ak sa vráti nulu, to znamená, že je Zápas, v ktorom prípade chceme, aby return true. Úspešne sme našli Slovo v našom Hashtable. 

V prípade, že nebol zápas, potom sme ísť na slučku znova a pozrieť sa na ďalší záznam. A budeme pokračovať smyčkování zatiaľ čo sú položky v tejto aplikácii v zozname. Čo sa stane, keď sa rozídeme z toho pre sláčiky? To znamená, že sme nemali nájsť položku, ktorá uzavreté toto slovo, v tom prípade vrátime false čo znamená, že naše Hashtable neobsahuje slovo. A to je kontrola. 

Takže poďme sa pozrieť na veľkosti. Teraz veľkosť bude veľmi jednoduchý. Vzhľadom k tomu, pamätajte na zaťaženie, pre každé slovo sme zistili, sme sa zvyšuje globálny variabilná veľkosť Hashtable. Takže funkcia veľkosť je práve deje vrátiť globálne premenné. A to je všetko. 

Teraz konečne, musíme uvoľniť slovník raz všetko hotové. Tak ako budeme robiť, že? Práve tu sme smyčkování cez všetky vedierka nášho stola. Takže tam sú NUM_BUCKETS vedierka. A pre každú aplikáciu v zozname v našej Hashtable, ideme do slučky cez celistvosť prepojeného zoznamu, uvoľní každý prvok. 

Teraz musíme byť opatrní. Takže tu máme dočasnú premennú to je ukladanie ukazovateľ na ďalšie prvok v prepojenom zozname. A potom budeme zadarmo aktuálny prvok. Musíme si byť istí, že sme to urobiť, pretože my nemôže len tak uvoľniť aktuálneho prvku a potom skúste prejdite na ďalší ukazovateľ, pretože akonáhle sme oslobodil ho, pamäť sa stáva neplatnou. 

Takže musíme držať okolo ukazovateľ na Ďalší prvok, potom sa môžeme oslobodiť aktuálny prvok, a potom sa môžeme aktualizovať Naše aktuálne prvok poukázať na ďalší prvok. Budeme slučky, zatiaľ čo tam sú prvky, v tomto prepojenom zozname. Urobíme to pre všetky spojené Zoznamy v Hashtable. A akonáhle sme skončili s tým, máme úplne vyložený Hashtable a sme hotoví. Tak to je nemožné pre odľahčenie niekedy vráti false. A keď sme hotoví, môžeme len vrátiť true. 

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 slovo a struct uzol * deti držiak abecedu. Takže prvá vec, ktorú by mohlo byť premýšľal, prečo je abecedu ed definovaná ako 27? No, pamätajte, že budeme potrebovať sa spracovanie apostrof. Tak, že to bude trochu Osobitný prípad v celom programe. 

Teraz si spomenúť, ako trie skutočne funguje. Povedzme, že sme indexovanie slovo "Mačky". Potom z koreňa trie, ideme sa pozrieť na deti pole, a budeme sa pozerať na index, ktorý odpovedá na list C. Tak, že budú indexované 2. Takže vzhľadom k tomu, že bude nám nový uzol. A potom budeme pracovať od tohto uzla. 

Takže za predpokladu, že uzol, sme opäť sa pozrieme na detskom poľa. A budeme sa pozerať 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 pozerať sa na konci to je a zodpovedá na T. a pohybuje sa na tomto uzle, Nakoniec sme úplne pozrel cez naše 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 slovo "katastrofa" je v našom slovníku, ale slovo "mačka" je nie? Tak a chcú zistiť, či slovo "mačka" je v našom slovníku, sme bude úspešne prezrieť Indexy C-A-T v oblasti uzla. Ale to je len preto, že katastrofa sa stalo vytvorenie uzlov na ceste z C-A-T, až do koniec slova. Takže bool slovo sa používa na označenie, či Tento konkrétny miesto vlastne označuje slovo. 

Dobrá. Takže teraz, keď vieme, čo to trie je bude vyzerať, poďme sa pozrieť na načítať funkciu. 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 sa bude slovník ktoré chceme načítať. 

Takže prvá vec, ktorú máme urobiť, je otvoriť do tohto slovníka pre čítanie. A musíme sa uistiť, sme neprepadli. Takže v prípade, že nebola slovník úspešne otvorený, vráti null, v tomto prípade sme chystá sa 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ň bude uzol *. Je to vrchol našej trie, že sme bude iterácie. Takže prvá vec, ktorú budeme chcieť urobiť, je rozdeliť 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, potrebujeme, aby sa Uistite sa, že rozdelenie bolo v skutočnosti úspešný. Ak to vrátil null, potom je potrebné uzavrieť alebo slovník súboru a vráti false. Takže za predpokladu, že rozdelenie bolo úspešná, budeme používať uzol * kurzor iterovat našej trie. Takže naše korene nikdy nezmení, ale budeme používať kurzor skutočne ísť z uzla do uzla. 

Takže v tomto cykle for sme čítanie prostredníctvom súboru slovníka. A my sme pomocou fgetc. Fgetc sa chystá chytiť jeden znak zo súboru. Budeme pokračovať v popada znaky, zatiaľ čo my nedosahujú koniec súboru. 

Existujú dva prípady, ktoré musíme zvládnuť. Prvý z nich, v prípade, že znak nebol nový riadok. Takže vieme, že keby to bola nová linka, potom chystáme sa prejsť na nové slovo. Ale za predpokladu, že nebol nový riadok, potom tu chceme zistiť, index ideme do indexu do v detskom pole, ktoré sme sa pozreli na pred. 

Takže, ako som už povedal, musíme Zvláštnym prípadom apostrof. Všimnite si, sme pomocou ternárnu Tu operátor. Takže budeme čítať to ako, ak charakter čítame v bol apostrof, potom ideme do nastavenia index = "abecedu" -1, ktorá bude byť index 26. 

Inak, ak to nie je apostrof, že budeme nastaviť index rovná c -. Takže pamätajte späť z už p-sad, c - bude nám abecedný pozície C. Takže ak C je písmeno, to bude nám index nula. Pre bod B, dá nám index 1, a tak ďalej. 

Tak to nám dáva index do deti polia, ktoré chceme. Teraz, ak tento index je v súčasnej dobe v null deti, to znamená, že uzol v súčasnej dobe neexistuje z tejto cesty. Takže musíme prideliť uzol pre túto cestu. To je to, čo budeme robiť. 

Takže budeme znovu použiť calloc funkcie, takže sme sa nemuseli nula sa všetky ukazovatele. A opäť 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 na nás. A potom pôjdeme k tomuto dieťaťu. 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ú. 

Čo je to inde? 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 hodnotu true. Tak, že znamená, že tento uzol označuje úspešné Slovo, aktuálne 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 inú prácu. Takže budeme pokračovať v tom, že, čítanie v znak po znaku, výstavbu nových uzlov v našom trie a pre každé slovo v slovníku, kým sme sa konečne dostať C! = EOF, v ktorom Prípad sa vymaniť zo súboru. 

Teraz existujú dva prípady prejednávanej pred ktoré sme mohli zasiahnuť EOF. Prvý z nich je, či došlo k chybe čítanie zo súboru. Takže v prípade, že bola chyba, budeme musíte urobiť typický. Vyložiť všetko, v blízkosti 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. 

Takže teraz poďme pozrieť na kontrolu. Ak sa pozrieme na funkciu kontroly, vidíme, že kontrola bude vracať hodnotu typu bool. Vracia true, ak to slovo, ktoré je boli prenesené, je v našom trie. Vracia false inak. Tak ako sa vám zistiť, č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. A teraz budeme iterovat v celom našom slova. Takže iterácia nad slovom sme v minulosti, ideme zistiť, index do poľa, ktoré deti zodpovedá slovo držiak I. Tak toto bude vyzerať presne ako zaťaženie, kde ak slovo [i] je apostrof, potom chceme použiť index "Abeceda" - 1. Pretože sme zistili, že je miesto, kde budeme ukladať apostrofy. 

Inak budeme používať dva nižšiu slovo Držiak I. Takže nezabudnite, že slovo môže mať ľubovoľnú veľkosť písmen. A tak chceme, aby sa ubezpečil, že sme používať malé písmená verzii vecí. A potom odpočítať od "" raz znovu nám v abecednom Postavenie tohto charakteru. Tak, že to bude náš index do detského poľa. 

A teraz, ak tento 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. Vzhľadom k tomu, ak by bolo, že by sa znamenať, že by cesta sa k tomuto slovu. A vy by ste nikdy stretnúť null. Takže stretnutie null, vrátime false. Slovo nie je v slovníku. Ak by tomu tak nebolo null, potom sme bude pokračovať iterácie. 

Takže ideme tam kurzor poukázať na to najmä uzol v danom indexe. Držíme tom, že po celé slovo, za predpokladu, že nikdy hit null. To znamená, že sme boli schopní dostať sa cez celé slovo a nájsť uzol v našom pokuse. Ale my nie sme úplne neskončil. 

Nechceme sa len vrátiť true. Chceme sa vrátiť kurzor> slovo. Vzhľadom k tomu, nezabudnite znovu, je "mačka" nie je v našom slovníku, a "katastrofa" je, potom budeme úspešne dostaneme cez 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 v skutočnosti slovo. A to je 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ť je len tak návrat slovníka veľkosť. A to je všetko. 

Takže nakoniec sme sa uvoľniť. Takže vyložiť, budeme používať rekurzívne funkcie, ktorá vlastne robiť všetko práce pre nás. Takže naša funkcia bude byť vyzvaná, vykladača. Čo je vykladač robiť? Vidíme tu, že vykladač 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 to ste vy 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. To bude fungovať rekurzívne vyložiť celý trie. A potom ešte raz, že to urobil, môžeme len vrátiť true. Uvoľniť nemôže zlyhať. 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 pravopisu. 

[MUSIC PLAYBACK]