>> [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Í]