[MUSIC PŘEHRÁVÁNÍ] 

ROB BOWDEN: Ahoj. Jsem Rob. A ať je to řešení ven. Takže tady budeme realizovat obecné tabulky. Vidíme, že struct uzel naší tabulka bude vypadat takto. Takže to bude mít char slovo Pole Velikost Délka + 1. Nezapomeňte + 1, protože maximální slovo ve slovníku je 45 znaky. A pak budeme potřebovat jeden navíc znak pro zpětné lomítko nulu. 

A pak naše Hashtable v každém kbelík se bude ukládat spojový seznam uzlů. Neděláme lineární snímací zde. A tak, aby odkazy na další prvek v kbelíku, musíme struct uzel * další. OK. Takže to je to, co uzel vypadá. 

Nyní je zde prohlášení naší Hashtable. Bude to mít 16.834 kbelíky. Ale to číslo nezáleží. A konečně budeme mít globální proměnná velikost Hashtable, které se chystá začít jako nula. A to bude mít přehled o tom, jak mnoho slov jsou v našem slovníku. 

Takže pojďme se podívat na zatížení. Všimněte si, že zátěž, vrací bool. Můžete se vrátit true, pokud bylo úspěšné naloženo, a v opačném případě false. A to trvá const char * slovníku, což je slovník který chceme otevřít. Takže to je první věc, budeme dělat. 

Jedeme do fopen slovník pro čtení. A budeme muset udělat Ujistěte se, že se jí podařilo. Takže pokud to vrátil NULL, pak ne úspěšně otevřít slovník. A my se musíme vrátit false. Ale za předpokladu, že to úspěšně udělal otevřené, pak chceme přečíst slovník. Takže mějte opakování, dokud nenajdeme nějaký důvod, aby se vymanily z této smyčky, které uvidíme. Takže mějte opakování. 

A teď jdeme na malloc jeden uzel. A samozřejmě musíme vysílat znovu zkontrolujte. Takže pokud mallocing neuspěl, pak chceme vyložit libovolný uzel, který my stalo malloc před zavřete slovník a vrátí false. Ale ignorovat, že za předpokladu, že se podařilo, pak chceme použít fscanf přečíst jediné slovo z naší slovník do našeho uzlu. Takže pamatujte, že vstupní slovo> je char Slovo vyrovnávací paměť o velikosti LENGHTH + 1 že budeme ukládat slovo palců 

Takže fscanf bude vrátit 1, pokud jak to bylo schopné úspěšně číst slovo ze souboru. Pokud to buď chyba se stane, nebo se dostat se na konec souboru, nevrátí 1.. V takovém případě nevrací 1, jsme se konečně chystá vypuknout Tento cyklus while. Takže vidíme, že jednou se nám podařilo mít číst slovo do entry> slovo, pak jdeme na to Slovo pomocí našeho hash funkce. 

Pojďme se podívat na funkce hash. Takže nemáte opravdu potřebujete to pochopit. A vlastně jsme právě vytáhl tento hash funkce z internetu. Jediná věc, kterou je třeba si uvědomit, je že to trvá const char * slovo. Tak to trvá řetězec jako vstup, a vrácením unsigned int jako výstup. Tak to je vše, funkce hash je, je to bere na vstup a dá vám index do Hashtable. 

Všimněte si, že jsme moding by NUM_BUCKETS, tak, že vrácená hodnota ve skutečnosti je index do Hashtable a není index za meze pole. Takže za předpokladu, že funkce, jedeme hash slovo, které čteme slovník. A pak budeme používat že hashovací vložit vstup do Hashtable. 

Nyní Hashtable hash je aktuální spojené seznamu v tabulce. A to je velmi možné, že je to jen NULL. Chceme vložit náš vstup na začátku tohoto propojeného seznamu. A tak budeme mít naši aktuální vstupní bod do jaké Hashtable V současné době poukazuje na. A pak budeme ukládat, v Hashtable na hash, aktuální záznam. Takže tyto dva řádky úspěšně vložit Vstup na začátku spojový seznam v tomto indexu v Hashtable. 

Jakmile jsme hotovi s tím, víme, že jsme našli další slovo slovník, a my jsme opět zvyšovat. Tak jsme to dělat, dokud fscanf nakonec se vrátil něco non-1 na který bod si uvědomit, že musíme vstup zdarma. Tak tady jsme malloced položku. A my jsme se snažili něco přečíst ze slovníku. A my jsme neměli úspěšně číst něco ze slovníku, v takovém případě musíme uvolnit vstup že jsme vlastně nikdy dát do Hashtable, a konečně zlomit. 

Poté, co jsme vypukne musíme vidět, dobře, jsme se zlomit, protože tam byla chyba při čtení ze souboru? Nebo jsme se zlomit, protože jsme došli na konec souboru? Pokud došlo k chybě, pak Chceme se vrátit false. Vzhledem k tomu, zatížení neuspěl. A v tomto procesu chceme vyložit všechna slova, která čteme v, a zavřete soubor slovníku. 

Za předpokladu, že jsme se to podaří, pak jsme jen Stále je třeba zavřít slovník soubor, a nakonec se vrátit true, protože jsme úspěšně načten slovníku. A to je pro zatížení. Takže teď zjistit, vzhledem k tomu naložené Hashtable, bude vypadat takto. Tak se podívejte, vrací bool, který je bude uvádět, zda prošel v char * slovo, ať už prošel v řetězci je v našem slovníku. Takže, je-li ve slovníku, v případě, že je v našem Hashtable, budeme vrátí hodnotu true. A pokud to tak není, vrátíme false. 

Vzhledem k tomu, to prošel ve slově, my jsme bude hash slovo. Nyní důležité si uvědomit, je že v zátěži věděli jsme, že všechny slova, že budeme mít malá písmena. Ale tady nejsme tak jistí. Pokud se podíváme na náš hash funkce, naše hash funkce vlastně je nižší plášť každý znak slova. Takže bez ohledu na kapitalizace Slovo, náš hash funkce je návrat stejný index na cokoliv kapitalizace je, jak to bude mít se vrátil k úplně malá verze slova. Dobře. To je náš index je do HashTable pro toto slovo. 

Teď to pro smyčce bude iteraci spojového seznamu která byla v daném indexu. Takže všimnete jsme inicializaci vstup poukázat na daném indexu. Budeme pokračovat zatímco vstup! = NULL. A nezapomeňte, že aktualizace ukazatel v našem souvisí položka v seznamu = entry> další. Takže máme aktuální vstupní bod do Dalším bodem v propojeném seznamu. 

Takže pro každou položku v propojeném seznamu, budeme používat strcasecmp. Není to StrComp. Protože jednou, chceme dělat věci případ necitlivě. Tak jsme se použít strcasecmp k porovnání Slovo, které bylo prošel tento funkce proti slovu že je v této položce. Pokud se vrátí nulu, to znamená, že je Zápas, ve kterém případě chceme, aby return true. Úspěšně jsme našli Slovo v našem Hashtable. 

V případě, že nebyl zápas, pak jsme jít na smyčku znovu a podívat se na další záznam. A budeme pokračovat smyčkování zatímco jsou položky v této aplikaci v seznamu. Co se stane, když se rozejdeme z toho pro smyčce? To znamená, že jsme neměli najít položku, která uzavřeno toto slovo, v tom případě vrátíme false což znamená, že naše Hashtable neobsahoval slovo. A to je kontrola. 

Takže pojďme se podívat na velikosti. Nyní velikost bude velmi jednoduchý. Vzhledem k tomu, pamatujte na zatížení, pro každé slovo jsme zjistili, jsme se zvyšuje globální variabilní velikost Hashtable. Takže funkce velikost je právě děje vrátit globální proměnné. A to je vše. 

Nyní konečně, musíme uvolnit slovník jednou všechno hotovo. Tak jak budeme dělat, že? Právě zde jsme smyčkování přes všechny kbelíky našeho stolu. Takže tam jsou NUM_BUCKETS kbelíky. A pro každou aplikaci v seznamu v naší Hashtable, jedeme do smyčky přes celistvost propojeného seznamu, uvolní každý prvek. 

Nyní musíme být opatrní. Takže tady máme dočasnou proměnnou to je ukládání ukazatel na další prvek v propojeném seznamu. A pak budeme zdarma aktuální prvek. Musíme si být jisti, že jsme to udělat, protože my nemůže jen tak uvolnit aktuálního prvku a pak zkuste přejděte na další ukazatel, protože jakmile jsme osvobodil jej, paměť se stává neplatnou. 

Takže musíme držet kolem ukazatel na Další prvek, pak se můžeme osvobodit aktuální prvek, a pak se můžeme aktualizovat Naše aktuální prvek poukázat na další prvek. Budeme smyčky, zatímco tam jsou prvky, v tomto propojeném seznamu. Uděláme to pro všechny spojeny Seznamy v Hashtable. A jakmile jsme skončili s tím, máme zcela vyloženo Hashtable a jsme hotovi. Tak to je nemožné pro odlehčení někdy vrátí false. A když jsme hotovi, můžeme jen vrátit true. 

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 slovo a struct uzel * děti držák abecedu. Takže první věc, kterou by mohlo být přemýšlel, proč je abecedu ed definována jako 27? No, pamatujte, že budeme potřebovat se zpracování apostrof. Tak, že to bude poněkud Zvláštní případ v celém programu. 

Nyní si vzpomenout, jak trie skutečně funguje. Řekněme, že jsme indexování slovo "kočky". Pak z kořene trie, jdeme se podívat na děti pole, a budeme se dívat na index, který odpovídá na dopis C. Tak, že budou indexovány 2. Takže vzhledem k tomu, že bude nám nový uzel. A pak budeme pracovat od tohoto uzlu. 

Takže za předpokladu, že uzel, jsme opět se podíváme na dětském pole. A budeme se dí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 dívat se na konci to je a odpovídá na T. a pohybuje se na tomto uzlu, Nakonec jsme zcela podíval přes naše 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 slovo "katastrofa" je v našem slovníku, ale slovo "kočka" je ne? Tak a chtějí zjistit, zda slovo "kočka" je v našem slovníku, jsme bude úspěšně prohlédnout Indexy C-A-T v oblasti uzlu. Ale to je jen proto, že katastrofa se stalo vytvoření uzlů na cestě z C-A-T, až do konec slova. Takže bool slovo se používá k označení, zda Tento konkrétní místo vlastně označuje slovo. 

Dobrá. Takže teď, když víme, co to trie je bude vypadat, pojďme se podívat na načíst funkci. 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 se bude slovník které chceme načíst. 

Takže první věc, kterou máme udělat, je otevřít do tohoto slovníku pro čtení. A musíme se ujistit, jsme nepropadli. Takže v případě, že nebyla slovník úspěšně otevřen, vrátí null, v tomto případě jsme chystá se vrátit 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 bude uzel *. Je to vrchol naší trie, že jsme bude iterace. Takže první věc, kterou budeme chtít udělat, je rozdělit 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, potřebujeme, aby se Ujistěte se, že rozdělení bylo ve skutečnosti úspěšný. Pokud to vrátil null, pak je třeba uzavřít nebo slovník souboru a vrátí false. Takže za předpokladu, že rozdělení bylo úspěšná, budeme používat uzel * kurzor iterovat naší trie. Takže naše kořeny nikdy nezmění, ale budeme používat kurzor skutečně jít z uzlu do uzlu. 

Takže v tomto cyklu for jsme čtení prostřednictvím souboru slovníku. A my jsme pomocí fgetc. Fgetc se chystá chytit jeden znak ze souboru. Budeme pokračovat v popadat znaky, zatímco my nedosahují konec souboru. 

Existují dva případy, které musíme zvládnout. První z nich, v případě, že znak nebyl nový řádek. Takže víme, že kdyby to byla nová linka, pak chystáme se přejít na nové slovo. Ale za předpokladu, že nebyl nový řádek, pak zde chceme zjistit, index jedeme do indexu do v dětském pole, které jsme se podívali na před. 

Takže, jak už jsem řekl, musíme Zvláštním případem apostrof. Všimněte si, jsme pomocí ternární Zde operátor. Takže budeme číst to jako, pokud charakter čteme v byl apostrof, pak jedeme do nastavení index = "abecedu" -1, která bude být index 26. 

Jinak, pokud to není apostrof, že budeme nastavit index rovná c -. Takže pamatujte zpět z již p-sad, c - bude nám abecední pozice C. Takže pokud C je písmeno, to bude nám index nula. Pro písmeno B, dá nám index 1, a tak dále. 

Tak to nám dává index do děti pole, které chceme. Nyní, pokud tento index je v současné době v null děti, to znamená, že uzel v současné době neexistuje z této cesty. Takže musíme přidělit uzel pro tuto cestu. To je to, co budeme dělat. 

Takže budeme znovu použít calloc funkce, takže jsme se nemuseli nula se všechny ukazatele. A opět 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ě na nás. A pak půjdeme k tomuto dítěti. 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í. 

Co je to jinde? 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 hodnotu true. Tak, že znamená, že tento uzel označuje úspěšné Slovo, aktuální 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 jinou práci. Takže budeme pokračovat v tom, že, čtení v znak po znaku, výstavbu nových uzlů v našem trie a pro každé slovo ve slovníku, dokud jsme se konečně dostat C! = EOF, ve kterém Případ se vymanit ze souboru. 

Nyní existují dva případy projednávané před které jsme mohli zasáhnout EOF. První z nich je, zda došlo k chybě čtení ze souboru. Takže v případě, že byla chyba, budeme musíte udělat typický. Vyložit všechno, v blízkosti 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. 

Takže teď pojďme podívat na kontrolu. Podíváme-li se na funkci kontroly, vidíme, že kontrola bude vracet hodnotu typu bool. Vrací true, pokud to slovo, které je byly přeneseny, je v našem trie. Vrací false jinak. Tak jak se vám zjistit, 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. A teď budeme iterovat v celém našem slova. Takže iterace nad slovem jsme v minulosti, jdeme zjistit, index do pole, které děti odpovídá slovo držák I. Tak tohle bude vypadat přesně jako zatížení, kde pokud slovo [i] je apostrof, pak chceme použít index "Abeceda" - 1. Protože jsme zjistili, že je místo, kde budeme ukládat apostrofy. 

Jinak budeme používat dva nižší slovo Držák I. Takže nezapomeňte, že slovo může mít libovolnou velikost písmen. A tak chceme, aby se ujistil, že jsme používat malá písmena verzi věcí. A pak odečíst od "" jednou znovu nám v abecedním Postavení tohoto charakteru. Tak, že to bude náš index do dětského pole. 

A teď, pokud tento 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. Vzhledem k tomu, pokud by bylo, že by se znamenat, že by cesta se k tomuto slovu. A vy byste nikdy setkat null. Takže setkání null, vrátíme false. Slovo není ve slovníku. Pokud by tomu tak nebylo null, pak jsme bude pokračovat iterace. 

Takže jdeme tam kurzor poukázat na to zejména uzel v daném indexu. Držíme tom, že po celé slovo, za předpokladu, že nikdy hit null. To znamená, že jsme byli schopni dostat se přes celé slovo a najít uzel v našem pokusu. Ale my nejsme úplně neskončil. 

Nechceme se jen vrátit true. Chceme se vrátit kurzor> slovo. Vzhledem k tomu, nezapomeňte znovu, je "kočka" není v našem slovníku, a "katastrofa" je, pak budeme úspěšně dostaneme přes 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 ve skutečnosti slovo. A to je 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 je jen tak návrat slovníku velikost. A to je vše. 

Takže nakonec jsme se uvolnit. Takže vyložit, budeme používat rekurzivní funkce, která vlastně dělat vše práce pro nás. Takže naše funkce bude být vyzvána, vykladače. Co je vykladač dělat? Vidíme zde, že vykladač 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 to jste vy 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. To bude fungovat rekurzivně vyložit celý trie. A pak ještě jednou, že to udělal, můžeme jen vrátit true. Uvolnit nemůže selhat. 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 pravopisu. 

[MUSIC PŘEHRÁVÁNÍ]