[Music kucheza] 

Rob BOWDEN: Hi. Mimi nina Rob. Na hebu ufumbuzi huu nje. Hivyo hapa tunakwenda kutekeleza ujumla meza. Tunaona kwamba struct node wetu meza ni kwenda kuangalia kama hii. Hivyo ni kwenda kuwa na neno char safu ya ukubwa LENGTH + 1. Usisahau + 1, tangu kiwango cha juu neno katika kamusi ni 45 wahusika. Na kisha sisi ni kwenda haja ya moja ya ziada tabia kwa backslash sifuri. 

Na kisha hashtable wetu katika kila ndoo ni kwenda kuhifadhi wanaohusishwa orodha ya nodes. Sisi si kufanya linear uchunguzi hapa. Na hivyo katika ili kuendana na ijayo hiki katika ndoo, tunahitaji struct nodi * ijayo. OK. Hivyo kwamba ni nini node inaonekana kama. 

Sasa hapa ni tamko ya hashtable yetu. Ni kwenda na 16,834 ndoo. Lakini idadi hiyo haina kweli jambo. Na hatimaye, tunakwenda na kimataifa variable hashtable kawaida, ambayo ni kwenda kuanza mbali kama zero. Na itakuja kwa kuweka wimbo wa jinsi maneno mengi ni katika kamusi yetu. 

Hivyo basi tuangalie mzigo. Taarifa mzigo, kuirudisha bool. Kurudi kweli kama ni mafanikio kubeba, na uongo vinginevyo. Na inachukua const char * dictionary, ambayo ni kamusi kwamba tunataka kufungua. Ili jambo la kwanza tunakwenda kufanya. 

Tunakwenda fopen kamusi ajili ya kusoma. Na tunakwenda kufanya kuhakikisha kwamba wamefanikiwa. Hivyo kama ni kurudi NULL, basi hatukuwa mafanikio kufungua dictionary. Na sisi haja ya kurudi uongo. Lakini kuchukua kwamba alifanya mafanikio wazi, basi tunataka kusoma dictionary. Hivyo kuweka wanaoendesha mpaka sisi kupata baadhi ya sababu ya kuvunja nje ya kitanzi hii, ambayo tutaweza kuona. Hivyo kuweka wanaoendesha. 

Na sasa tunakwenda malloc node moja. Na bila shaka tunahitaji hewa kuangalia tena. Hivyo kama mallocing hakuwa na kufanikiwa, basi tunataka kupakua node yoyote kwamba sisi kilichotokea kwa malloc kabla ya, karibu na kamusi na kurudi uongo. Lakini kupuuza kwamba, kuchukua sisi ilifanikiwa, kisha tunataka kutumia fscanf kusoma neno moja kutoka wetu kamusi ndani ya node yetu. Ili kukumbuka kwamba kuingia> neno ni char neno buffer ya ukubwa LENGHTH + 1 kwamba sisi ni kwenda kuhifadhi neno in 

Hivyo fscanf ni kwenda na kurudi 1, kwa muda mrefu kama alikuwa na uwezo wa mafanikio kusoma neno kutoka faili. Kama ama makosa kinachotokea, au sisi kufikia mwisho wa faili, ni si kurudi 1. Katika kesi ambayo haina kurudi 1, sisi ni hatimaye kwenda kuvunja nje ya kitanzi hii wakati. Hivyo tunaona kwamba mara moja sisi kuwa na mafanikio kusoma neno katika kuingia> neno, kisha tunakwenda kwamba neno kwa kutumia hash kazi yetu. 

Hebu tuangalie hash kazi. Hivyo si kweli wanahitaji kuelewa hili. Na kwa kweli sisi tu vunjwa hash hii kazi kutoka katika mtandao. Kitu tu unahitaji kutambua ni kwamba hii inahitaji const * Char neno. Hivyo ni kuchukua kamba kama pembejeo, na kurudi unsigned int kama pato. Ili wote hash kazi ni, ni inachukua katika pembejeo na anatoa index katika hashtable. 

Taarifa kwamba sisi ni moding na NUM_BUCKETS, hivyo thamani kwamba akarudi kweli ni index katika hashtable na haina index zaidi ya mipaka ya safu. Hivyo kutokana na kazi hiyo, tunakwenda kwa hash neno kwamba sisi kusoma dictionary. Na kisha tunakwenda kutumia kwamba hash kuingiza kuingia katika hashtable. 

Sasa hashtable hash ni sasa wanaohusishwa katika orodha ya meza. Na inawezekana sana kwamba ni tu null. Tunataka kuingiza kuingia yetu mwanzo wa orodha hii wanaohusishwa. Na hivyo tunakwenda na wetu wa sasa hatua ya kuingia kwa nini hashtable sasa anazungumzia. Na kisha tunakwenda kuhifadhi, katika hashtable katika hash, kuingia sasa. Hivyo mistari hizi mbili mafanikio kuingiza kuingia katika mwanzo wa wanaohusishwa orodha ya kwamba index katika hashtable. 

Mara baada ya sisi ni kosa na kwamba, tunajua kwamba sisi kupatikana neno lingine katika kamusi, na sisi nyongeza tena. Kwa hiyo sisi kuendelea kufanya kwamba mpaka fscanf hatimaye alirejea kitu mashirika yasiyo ya 1 katika ambayo uhakika kukumbuka kwamba tunahitaji kuingia bure. Hivyo hapa sisi malloced kuingia. Na sisi walijaribu kusoma kitu kutoka kamusi. Na sisi hakuwa mafanikio kusoma kitu kutoka kamusi, katika kesi ambayo tunahitaji kuingia bure kuwa sisi kamwe kweli kuweka katika hashtable, na hatimaye kuvunja. 

Mara baada ya sisi kuvunja nje tunahitaji kuona, vizuri, Je, sisi kuvunja nje kwa sababu kuna ilikuwa makosa kusoma kutoka faili? Au je, sisi kuvunja nje kwa sababu sisi kufikiwa mwisho wa file? Kama kulikuwa na makosa, kisha tunataka kurudi uongo. Kwa sababu mzigo hakuwa na kufanikiwa. Na katika mchakato tunataka kupakua maneno hayo yote sisi kusoma katika, na karibu faili dictionary. 

Kutokana hatukuwa kufanikiwa, kisha sisi tu bado haja ya karibu kamusi faili, na hatimaye kurudi kweli tangu sisi mafanikio kubeba dictionary. Na kwamba ni kwa ajili ya shehena. Hivyo sasa kuangalia, kutokana na hashtable kubeba, ni kwenda kuangalia kama hii. Ili kuangalia, kuirudisha bool, ambayo ni kwenda kuonyesha kama kupita katika char * neno, kama kupita katika string ni katika kamusi yetu. Hivyo kama ni katika kamusi, kama ni katika hashtable yetu, sisi kurudi kweli. Na kama si, sisi kurudi uongo. 

Kutokana na suala hili kupita katika neno, sisi ni kwenda hash neno. Sasa jambo muhimu kutambua ni kwamba katika mzigo sisi alijua kwamba yote ya maneno tunakwenda kuwa na kesi ya chini. Lakini hapa tuko na uhakika sana. Kama sisi kuangalia hash yetu kufanya kazi, hash kazi yetu kweli ni chini casing kila tabia neno la Mungu. Hivyo bila kujali mtaji wa neno, hash yetu kufanya kazi ni kurudi sawa index kwa chochote mtaji ni, kama ingekuwa kurejea kwa ajili ya kabisa lowercase toleo la neno. Alright. Hiyo ni orodha yetu ni ndani ya hashtable kwa neno hili. 

Sasa hii kwa kitanzi ni kwenda iterate juu ya orodha wanaohusishwa kwamba ilikuwa ni saa index. Hivyo taarifa sisi ni initializing kuingia kwa uhakika na kwamba index. Sisi ni kwenda kuendelea wakati kuingia! = null. Na kukumbuka kwamba kuhuisha pointer katika orodha yetu wanaohusishwa kuingia = kuingia> ijayo. Hivyo kuwa na kuingia hatua wetu wa sasa na bidhaa ijayo katika orodha wanaohusishwa. 

Kwa hiyo kwa kila kuingia katika orodha wanaohusishwa, sisi ni kwenda kutumia strcasecmp. Siyo strcomp. Kwa sababu mara nyingine tena, tunataka kufanya mambo kesi insensitively. Hivyo sisi kutumia strcasecmp kulinganisha neno kwamba ilipitishwa kwa njia hii kazi kinyume na neno kwamba ni katika kuingia hii. Kama kuirudisha zero, hiyo ina maana kulikuwa na mechi, katika kesi ambayo tunataka kurudi kweli. Sisi mafanikio kupatikana neno katika hashtable yetu. 

Kama kulikuwa na si mechi, basi sisi ni kwenda kwa kitanzi tena na kuangalia kuingia ijayo. Na tutaweza kuendelea looping wakati kuna ni entries katika orodha hii wanaohusishwa. Kile kinachotokea kama sisi kuvunja nje ya hii kwa kitanzi? Hiyo ina maana sisi hawakuona kuingia kwamba kuendana neno hili, katika kesi ambayo sisi kurudi uongo zinaonyesha kwamba yetu hashtable hakuwa vyenye neno hili. Na kwamba ni kuangalia. 

Hivyo basi tuangalie kawaida. Sasa ukubwa ni kwenda kuwa pretty rahisi. Tangu kumbuka katika mzigo, kwa kila neno sisi kupatikana, sisi incremented kimataifa variable hashtable kawaida. Hivyo ukubwa kazi ni kwenda tu kurudi variable kimataifa. Na hiyo ni yake. 

Sasa hatimaye, tunahitaji kupakua kamusi mara moja kila kitu kosa. Hivyo ni jinsi sisi ni kwenda kufanya hivyo? Haki hapa sisi ni wanaoendesha juu ya ndoo yote ya meza yetu. Hivyo kuna NUM_BUCKETS ndoo. Na kwa kila orodha wanaohusishwa katika yetu hashtable, tunakwenda kitanzi juu ya ukamilifu wa orodha wanaohusishwa, kumkomboa kila kipengele. 

Sasa tunahitaji kuwa makini. Kwa hiyo hapa tuna variable muda hiyo hifadhi ya pointer ijayo hiki katika orodha wanaohusishwa. Na kisha tunakwenda bure hiki sasa. Tunahitaji kuwa na uhakika sisi kufanya hivyo tangu sisi huwezi bure hiki sasa na kisha kujaribu kupata pointer ya pili, tangu mara moja tumekuwa huru yake, kumbukumbu inakuwa batili. 

Kwa hiyo, tunahitaji kuweka karibu pointer kwa hiki ijayo, basi tunaweza bure hiki sasa, na kisha tunaweza kuboresha hiki wetu wa sasa kwa uhakika na hiki ijayo. Tutaweza kitanzi wakati kuna mambo katika orodha hii wanaohusishwa. Tutaweza kufanya hivyo kwa wote wanaohusishwa orodha katika hashtable. Na mara moja sisi ni kosa na kwamba, tumekuwa kabisa unloaded hashtable, na sisi ni kosa. Hivyo ni vigumu kwa ipakuliwe kwa milele kurudi uongo. Na wakati sisi ni kosa, sisi tu kurudi kweli. 

Hebu kutoa ufumbuzi huu kujaribu. Hivyo basi tuangalie nini yetu struct node kuangalia kama. Hapa tunaona tunakwenda na bool neno na struct nodi * watoto bracket ALPHABET. Hivyo jambo la kwanza unaweza kuwa na wanashangaa, kwa nini ni ALPHABET ed hufafanuliwa kama 27? Vizuri, kumbuka kwamba sisi ni kwenda haja ya kwa kuwa utunzaji apostrophe. Ili kwenda kuwa fulani ya kesi maalum katika mpango huu. 

Sasa kumbuka jinsi trie kweli kazi. Hebu sema sisi ni Indexing neno "Paka." Kisha kutoka mizizi ya trie, sisi ni kwenda kuangalia watoto safu, na sisi ni kwenda kuangalia index kwamba sambamba na barua C. Kwa hiyo itakuwa indexed 2. Hivyo kutokana na kwamba, mapenzi yake ya kwamba kutupa node mpya. Na kisha tutaweza kazi na kwamba nodi. 

Hivyo kutokana na kwamba node, tuko kwa mara nyingine tena kwenda kuangalia watoto safu. Na sisi ni kwenda kuangalia index zero yanahusiana na A katika paka. Hivyo basi sisi ni kwenda kwa kuwa node, na kutokana na kwamba node tunakwenda kuangalia mwisho wake ni sambamba kwa T. Na kuhamia kwenye kwamba node, hatimaye, tuna kabisa inaonekana kupitia neno yetu "paka." Na sasa bool neno zinatakiwa kuonyesha kama neno hili kutokana na ni kweli neno. 

Hivyo kwa nini tunahitaji kuwa kesi maalum? Vizuri gani ya neno "janga" ni katika kamusi yetu, lakini neno "cat" ni si? Hivyo na kuangalia ili kuona kama neno "cat" ni katika kamusi yetu, sisi ni kwenda kwa mafanikio kuangalia njia fahirisi C-A-T katika mkoa wa nodi. Lakini hiyo ni kwa sababu tu janga kilichotokea kwa kujenga nodes juu ya njia kutoka C-A-T, njia yote ya mwisho wa neno. Hivyo neno bool hutumika kuonyesha kama eneo hili hasa kweli inaonyesha neno. 

Sawa. Hivyo sasa kwamba sisi kujua trie ni nini kwenda kuangalia kama, hebu tuangalie mzigo kazi. Hivyo mzigo ni kwenda na kurudi bool kwa kama sisi mafanikio au bila mafanikio kubeba dictionary. Na hii ni kwenda kuwa kamusi kwamba tunataka kupakia. 

Kitu hivyo kwanza sisi ni kufanya ni wazi juu kwamba kamusi ajili ya kusoma. Na sisi kuhakikisha sisi hakuwa na kushindwa. Hivyo kama kamusi hakuwa mafanikio kufunguliwa, itakuwa kurudi null, katika kesi ambayo tuko kwenda na kurudi uongo. Lakini kuchukua kwamba ni mafanikio kufunguliwa, basi tunaweza kweli kusoma kupitia dictionary. 

Kitu hivyo kwanza tunakwenda wanataka kufanya ni sisi na hii kimataifa variable mizizi. Sasa mzizi ni kwenda kuwa node *. Ni juu ya trie yetu kwamba sisi ni kwenda kuwa iterating kupitia. Hivyo jambo la kwanza kwamba sisi ni kwenda wanataka kufanya ni kutenga kumbukumbu kwa ajili ya mizizi yetu. Taarifa kwamba sisi ni kutumia calloc kazi, ambayo ni sawa kimsingi kama malloc kazi, ila ni uhakika wa kurudi kitu ambacho ni kabisa alizungumzia zaidi hali ilivyo nje. Hivyo kama sisi kutumika malloc, tunataka haja ya kwenda kwa njia zote za kuyatumia katika maisha yetu node, na kuhakikisha kwamba wao uko wote null. Hivyo calloc kufanya kwetu hilo. 

Sasa tu kama malloc, sisi haja ya kufanya kuhakikisha kwamba mgao kwa kweli mafanikio. Kama hii akarudi null, kisha sisi haja ya karibu au kamusi faili na kurudi uongo. Hivyo kuchukua mgao kwamba alikuwa mafanikio, sisi ni kwenda kutumia nodi * mshale iterate kupitia trie yetu. Hivyo mizizi yetu kamwe kwenda na mabadiliko, lakini sisi ni kwenda kutumia mshale kweli kwenda na nodi ya nodi. 

Hivyo katika hii kwa kitanzi sisi ni kusoma kwenye faili dictionary. Na sisi ni kutumia fgetc. Fgetc ni kwenda kunyakua moja tabia kutoka file. Sisi ni kwenda kuendelea grabbing wahusika wakati sisi si kufikia mwisho wa faili. 

Kuna mambo mawili sisi haja ya kushughulikia. kwanza, kama tabia hakuwa line mpya. Hivyo sisi kujua kama ilikuwa mstari wa mwezi, kisha sisi ni juu ya kuendelea na neno jipya. Lakini kuchukua haikuwa line mpya, kisha hapa tunataka kufikiri index tunakwenda index katika kwa watoto safu kwamba sisi inaonekana katika kabla ya. 

Hivyo, kama nilivyosema hapo kabla, tunahitaji kesi maalum apostrophe. Taarifa sisi ni kutumia ternary operator hapa. Hivyo sisi ni kwenda kusoma hii kama, kama tabia ya sisi kusoma katika mara apostrophe, basi sisi ni kwenda kuweka index = "ALPHABET" -1, ambayo itakuwa kuwa index 26. 

Mwingine, kama siyo apostrophe, kuna tunakwenda kuweka index sawa na c -. Basi kumbuka nyuma kutoka hapo awali p-sets, c - a ni kwenda kutupa nafasi herufi ya C. Hivyo kama C ni barua A, hii itakuwa kutupa index sifuri. Kwa barua B, itakuwa kutoa sisi index 1, na kadhalika. 

Hivyo hii inatupa index katika watoto safu kwamba tunataka. Sasa kama ripoti hii kwa sasa ni null katika watoto, hiyo ina maana kwamba node haina sasa zipo kutoka kwa njia ya hiyo. Kwa hiyo, tunahitaji kutenga node kwa njia hiyo. Hiyo ni nini tutaweza kufanya hapa. 

Hivyo sisi ni kwenda tena kutumia calloc kazi, ili sisi hawana sifuri nje kuyatumia wote. Na sisi tena haja ya kuangalia kwamba calloc hakuwa na kushindwa. Kama calloc hakuwa kushindwa, basi tunahitaji ipakuliwe kila kitu, karibu yetu kamusi, na kurudi uongo. Hivyo kudhani kuwa hakuwa na kushindwa, kisha itajenga mtoto mpya kwa ajili yetu. Na kisha tutakwenda kwa mtoto. Mshale yetu iterate chini ya kwamba mtoto. 

Sasa kama hii ilikuwa si null kwa kuanzia, kisha mshale unaweza tu iterate chini ya kwamba mtoto bila ya kweli ya kuwa na kutenga kitu chochote. Hii ni kesi ambapo sisi kwanza kilichotokea kutenga neno "paka." Na hiyo ina maana wakati sisi kwenda kutenga "Janga," hatuna haja ya kuunda nodes kwa C-A-T tena. Wao tayari zipo. 

Ni mambo gani haya mwingine? Hii ni hali ambapo c mara backslash n, ambapo c alikuwa mstari mpya. Hii ina maana kwamba sisi kuwa na mafanikio kukamilika neno. Sasa nini tunataka kufanya wakati sisi mafanikio ya kumaliza neno? Tunakwenda kutumia uwanja hii neno ndani ya struct yetu nodi. Tunataka kuweka kwamba kwa kweli. Hivyo kwamba inaonyesha kwamba node hii inaonyesha mafanikio neno, neno halisi. 

Sasa kuweka kwamba kwa kweli. Tunataka upya mshale yetu kwa uhakika mwanzo wa trie tena. Na hatimaye, nyongeza kamusi yetu kawaida, tangu sisi kupatikana kazi nyingine. Hivyo sisi ni kwenda kuweka kufanya hivyo, kusoma katika tabia na tabia, ujenzi wa nodes mpya katika trie yetu na kwa kila neno katika kamusi, mpaka sisi hatimaye kufikia C! = EOF, ambayo kesi sisi kuvunja nje ya faili. 

Sasa kuna mambo mawili chini ya ambayo sisi tupate kuwa hit EOF. kwanza ni kama kulikuwa na makosa kusoma kutoka file. Hivyo kama kulikuwa na makosa, sisi haja ya kufanya kawaida. Kupakua kila kitu, karibu file, kurudi uongo. Kutokana kulikuwa na si kosa, kwamba tu ina maana sisi kweli hit mwisho wa file, katika kesi ambayo, sisi karibu faili na kurudi kweli tangu sisi mafanikio kubeba kamusi ndani ya trie yetu. 

Hivyo sasa hebu angalia nje kuangalia. Kuangalia kazi ya kuangalia, tunaona kuangalia kwamba ni kwenda na kurudi bool. Ni anarudi kweli kama neno hili ni kupitishwa ni katika trie yetu. Ni anarudi uongo vinginevyo. Hivyo ni jinsi gani kuamua kama neno hili ni katika trie yetu? 

Tunaona hapa kwamba, kama kabla, tunakwenda kutumia mshale iterate kupitia trie yetu. Sasa hapa tunakwenda iterate juu ya neno yetu yote. Hivyo iterating juu ya neno sisi ni siku za nyuma, tunakwenda kuamua index ndani ya watoto safu kwamba sambamba na neno bracket I. Hivyo hii ni kwenda kuangalia hasa kama mzigo, ambapo kama neno [i] ni apostrophe, basi tunataka kutumia index "ALPHABET" - 1. Kwa sababu sisi kuamua kwamba ni wapi tunakwenda kuhifadhi apostrophes. 

Mwingine tunakwenda kutumia neno mbili chini bracket I. Basi kumbuka neno ambayo inaweza na mtaji holela. Na hivyo tunataka kuhakikisha kwamba sisi ni kutumia toleo lowercase ya mambo. Na kisha Ondoa na kwamba 'kwa mara nyingine tena kutupa herufi nafasi ya kwamba tabia. Ili kwenda kuwa orodha yetu ndani ya watoto safu. 

Na sasa kama kwamba index ndani ya watoto safu ni null, hiyo ina maana sisi haiwezi kuendelea iterating chini trie yetu. Kama hiyo kesi, neno hili hawawezi uwezekano wa kuwa katika trie yetu. Tangu kama ilivyokuwa, kwamba ingekuwa maana kutakuwa na njia chini ya neno hilo. Na wewe kamwe kukutana null. Hivyo kukutana null, sisi kurudi uongo. neno ni si katika kamusi. Kama si null, basi sisi ni kwenda kuendelea iterating. 

Hivyo sisi ni kwenda huko nje mshale kwa uhakika na kwamba hasa node wakati huo index. Sisi kuendelea kufanya hivyo katika neno nzima, kuchukua sisi kamwe hit null. Hiyo ina maana tulikuwa na uwezo wa kupata njia neno nzima na kupata node katika kujaribu yetu. Lakini sisi siyo kabisa kufanyika bado. 

Hatutaki tu kurudi kweli. Tunataka kurudi mshale> neno. Tangu kumbuka tena, ni "cat" si katika kamusi yetu, na "janga" ni, basi sisi mafanikio sisi kupata kupitia neno "paka." Lakini mshale neno kuwa uongo na si kweli. Hivyo sisi kurudi mshale neno zinaonyesha kama node hii ni kweli neno. Na kwamba ni kwa ajili ya kuangalia. 

Hivyo hebu angalia nje ukubwa. Hivyo ukubwa ni kwenda kuwa pretty rahisi tangu, kumbuka katika mzigo, sisi ni incrementing kamusi kawaida kwa ajili ya kila neno kwamba sisi kukutana. Hivyo ukubwa ni kwenda tu kurudi kamusi kawaida. Na hiyo ni yake. 

Hivyo Mwisho tuna ipakuliwe. Hivyo ipakuliwe, sisi ni kwenda kutumia kazi kujirudia kwa kweli kufanya yote ya kazi kwa ajili yetu. Hivyo kazi yetu ni kwenda kuitwa juu ya mpakuzi. Je, ni mpakuzi kwenda kufanya nini? Tunaona hapa kwamba mpakuzi ni kwenda iterate juu ya yote ya watoto katika node fulani. Na kama node mtoto ni si null, kisha tunakwenda kupakua node mtoto. 

Hivyo hii ni wewe recursively kupakua watoto wetu wote. Mara baada ya sisi ni kuhakikisha kwamba watoto wetu wote wamekuwa unloaded, basi sisi inaweza bure sisi wenyewe, ili kupakua wenyewe. Hii kazi recursively kupakua trie nzima. Na kisha mara moja hiyo ni kufanyika, tunaweza tu kurudi kweli. Ipakuliwe hawezi kushindwa. Tuko tu kumkomboa mambo. Hivyo mara moja sisi ni kosa kumkomboa kila kitu, kurudi kweli. Na hiyo ni yake. Jina langu ni Rob. Na hii ilikuwa Speller. 

[Music kucheza]