[MUSIC Playing] 

Rob Bowden: Hi. Unë jam Rob. Dhe'S le këtë zgjidhje jashtë. Pra, këtu ne jemi duke shkuar për të zbatuar një tabelë të përgjithshme. Ne e shohim se nyja struct e tona tabela do të duket si ky. Pra, kjo do të ketë një fjalë char array e madhësisë gjatësi + 1. Mos harroni + 1, pasi maksimale fjalë në fjalor është 45 karaktere. Dhe pastaj ne do të duhet një shtesë karakter për zero backslash. 

Dhe pastaj hashtable tonë në çdo kovë është duke shkuar për të ruajtur një listë e lidhur e nyjeve. Ne nuk jemi duke bërë lineare probing këtu. Dhe kështu që në mënyrë për të lidhur për të ardhshëm element në kovë, ne kemi nevojë për një nyje struct * ardhshme. OK. Pra, kjo është ajo që një nyje duket si. 

Tani këtu është deklarata e hashtable tonë. Ajo do të ketë 16.834 kova. Por ai numër nuk ka rëndësi. Dhe në fund, ne do të kemi Madhësia e globale ndryshueshme hashtable, e cila do të nisem si zero. Dhe ajo do të mbajnë gjurmët e sa shumë fjalë janë në fjalorin tonë. 

Pra, le të marrin një vështrim në ngarkesë. Vini re se ngarkesës, ajo kthen një bool. Ju kthim i vërtetë në qoftë se ajo ishte sukses ngarkuar, dhe të rreme ndryshe. Dhe ajo merr një const char * dictionary, që është fjalor që ne duam të hapur. Pra, kjo është gjëja e parë ne jemi duke shkuar për të bërë. 

Ne jemi duke shkuar për fopen fjalor për lexim. Dhe ne do të kemi për të bërë të sigurt se ajo pati sukses. Pra, në qoftë se ajo u kthye NULL, atëherë ne nuk e bëri me sukses të hapur fjalorin. Dhe ne duhet të kthimit të rreme. Por, duke supozuar se ajo e bëri me sukses hapur, atëherë ne duam të lexuar fjalor. Pra, të mbajtur looping deri sa të gjejmë disa arsye për të thyer nga ky lak, të cilat ne do të shohim. Pra mbani looping. 

Dhe tani ne jemi duke shkuar për malloc një nyje të vetme. Dhe sigurisht ne kemi nevojë të ajrit kontrolloni sërish. Pra, nëse mallocing nuk pati sukses, atëherë ne duam të shkarkoj ndonjë nyje që ne ndodhur me malloc para, të mbyllur fjalor dhe kthimit të rreme. Por duke injoruar se, duke supozuar ne pati sukses, atëherë ne duam të përdorim fscanf për të lexuar një fjalë të vetme nga tonë dictionary në nyje tonë. Pra, mos harroni se hyrjes> fjalë është char tampon fjala e madhësisë LENGHTH + 1 që ne jemi duke shkuar për të ruajtur fjalën in 

Pra fscanf do të kthehen me 1, për sa kohë si ajo ishte në gjendje që me sukses lexuar një fjalë nga file. Nëse një nga një gabim ndodh, ose ne arritur në fund të skedarit, ajo nuk do të kthehen 1. Në të cilin rast nuk ka kthim 1, ne jemi më në fund duke shkuar për të thyer nga kjo loop ndërsa. Pra, ne shohim se një herë ne kemi sukses lexoni një fjalë në entry> fjalë, atëherë ne jemi duke shkuar për të cilat Fjala përdorur funksionin tonë të hash. 

Le të bëjmë një vështrim në funksion hash. Pra, ju nuk duhet të vërtetë për të kuptuar këtë. Dhe në të vërtetë ne vetëm nxorrën këtë hash funksionojnë nga interneti. E vetmja gjë që ju duhet për të njohur është se kjo merr një const char * fjalën. Pra, ajo është duke marrë një varg si input, dhe kthyer një int unsigned si prodhim. Pra, kjo është e gjitha një funksion hash është, është ajo merr në një input dhe ju jep një Indeksi në hashtable. 

Vini re që ne jemi moding nga NUM_BUCKETS, në mënyrë që vlera e kthyer në të vërtetë është një indeks në hashtable dhe nuk indeksi përtej caqeve të array. Pra, duke pasur parasysh se funksioni, ne jemi duke shkuar te bej hash fjalën se ne të lexuar fjalor. Dhe atëherë ne jemi duke shkuar për të përdorur që hash për të futur hyrja në hashtable. 

Hash Tani hashtable është aktual lidhur listë në tabelë. Dhe kjo është shumë e mundur se kjo është vetëm NULL. Ne duam të futur hyrjen tonë në fillimi i këtij listën e lidhur. Dhe kështu që ne do të kemi aktuale tonë pikë hyrëse në çfarë hashtable aktualisht tregon. Dhe atëherë ne jemi duke shkuar për të ruajtur, në hashtable në hash, hyrja aktuale. Pra, këto dy linja sukses futur hyrja në fillim të lista e lidhur në atë indeks në hashtable. 

Pasi ne jemi duke bërë me këtë, ne e dimë se kemi gjetur një tjetër fjalë në fjalor, dhe ne rritje përsëri. Pra, ne vazhdojmë të bëjmë që deri fscanf më në fund u kthye diçka jo-1 në e cila pikë mos harroni se ne kemi nevojë për hyrjen e lirë. Pra, deri këtu kemi malloced një hyrje. Dhe ne u përpoq për të lexuar diçka nga fjalori. Dhe ne nuk e ka lexuar me sukses diçka nga fjalori, në këtë rast ne kemi nevojë për të liruar hyrjen që kurrë nuk e kemi vënë në të vërtetë në hashtable, dhe më në fund thyejnë. 

Pasi ne shpërthen ne duhet të shohim, mirë, nuk e kemi shpërthen për shkak se ka u lexuar një gabim nga fotografi? Apo nuk e kemi thyer jashtë, sepse ne arritur në fund të dosjes? Nëse ka pasur një gabim, atëherë ne duam të kthimit të rreme. Për shkak të ngarkesës nuk pati sukses. Dhe në këtë proces ne duam të shkarkoj të gjitha fjalët që kemi lexuar në, dhe mbyllur fjalor file. 

Duke supozuar që pati sukses, atëherë ne vetëm ende nevojë për të mbyllur fjalorin paraqesë, dhe më në fund kthehet e vërtetë që kemi ngarkuar me sukses fjalor. Dhe kjo është ajo për të ngarkesës. Deri tani të kontrolluar, duke pasur parasysh një hashtable ngarkuar, do të duket si ky. Pra shikoni, ajo kthen një bool, e cila është duke shkuar për të treguar se kaluar në char * fjalë, nëse kaluar në string është në fjalorin tonë. Pra, në qoftë se ajo është në fjalor, në qoftë se ajo është në hashtable tonë, ne do të kthehet e vërtetë. Dhe në qoftë se kjo nuk është, ne do të kthimit të rreme. 

Duke pasur parasysh këtë kaloi në fjalë, ne jemi do të hash fjalën. Tani një gjë e rëndësishme për të njohur është se në ngarkesës ne e dinim se të gjithë fjalë ne do të jetë rasti më i ulët. Por këtu ne nuk jemi aq të sigurt. Nëse do të bëjmë një vështrim në funksion tonë të hash, funksion ynë hash në të vërtetë është shtresë e jashtme e ulët çdo karakter të fjalës. Pra, pavarësisht nga kapitalizimin e fjalë, funksioni ynë hash është kthimi të njëjtën gjë indeksi për çfarëdo kapitalizimi është, pasi do të ketë kthyer për një krejtësisht të vogla Versioni i fjalës. Mirë. Kjo është indeksi jonë është në hashtable për këtë fjalë. 

Tani kjo për lak do të iterate mbi listën e lidhur që ishte në atë indeks. Pra, vini re, ne jemi të fillimit të hyrjes për pikë në këtë indeks. Ne jemi duke shkuar për të vazhduar ndërsa hyrja! = NULL. Dhe mos harroni se përditësimin në treguesin në hyrjen tonë lidhur list = entry> ardhshëm. Pra kemi pikën tonë të tanishëm e hyrjes në Pika tjetër në listën e lidhur. 

Kështu që për çdo hyrje në listën e lidhur, ne jemi duke shkuar për të përdorur strcasecmp. Kjo nuk është strcomp. Sepse edhe një herë, ne duam të bëjë gjëra rast insensitively. Pra, ne i përdorim strcasecmp për të krahasuar fjalë që u miratua me këtë Funksioni kundër fjalës që është në këtë term. Nëse ai kthehet zero, që do të thotë ka pasur një ndeshje, në të cilin rast ne duam të kthim i vërtetë. Ne me sukses gjetur Fjala në hashtable tonë. 

Nëse ka nuk ishte një ndeshje, atëherë ne jemi do të lak përsëri dhe të kërkoni në hyrje tjetër. Dhe ne do të vazhdojmë looping ndërsa ka janë të hyra në këtë listën e lidhur. Çfarë ndodh nëse ne pushim nga kjo për lak? Kjo do të thotë ne nuk kemi gjetur një hyrje që përputhet këtë fjalë, në të cilin rast ne kthimit të rreme për të treguar se tonë hashtable nuk e përmbajnë këtë fjalë. Dhe kjo është një kontroll. 

Pra, le të marrin një vështrim në madhësi. Tani madhësia do të jetë shumë e thjeshtë. Që kujtohet në ngarkesë, për çdo fjalë kemi gjetur, ne incremented një globale Madhësia hashtable ndryshueshme. Pra, funksioni madhësia është vetëm do të kthehen ndryshore globale. Dhe kjo është ajo. 

Tani së fundi, ne kemi nevojë për të shkarkoj fjalor herë është bërë çdo gjë. Pra, si do të shkojmë për të bërë këtë? Këtu ne jemi looping mbi të gjitha kova e tryezën tonë. Pra, ka NUM_BUCKETS kova. Dhe për çdo listën e lidhur në tonë hashtable, ne jemi duke shkuar për lak mbi tërësia e listës lidhur, liruar çdo element. 

Tani ne duhet të jenë të kujdesshëm. Pra, këtu kemi një ndryshore të përkohshme që është ruajtjen kursorin për të ardhshëm element në lista lidhur. Dhe atëherë ne jemi duke shkuar për të lirë element tanishme. Ne duhet të jetë i sigurt që ne e bëjmë këtë që nga viti ne nuk mund vetëm të lirë elementin e tanishëm të dhe pastaj të përpiqet për të hyrë në treguesin e ardhshëm, që nga një herë ne kemi liruar atë, kujtesës bëhet e pavlefshme. 

Pra, ne kemi nevojë për të mbajtur rreth një tregues për element tjetër, atëherë ne mund të lirë element aktuale, dhe pastaj ne mund të rinovuar element tonë aktuale për pikë për të element tjetër. Ne do të loop ndërsa ka elemente në këtë listë e lidhur. Ne do të bëjmë që për të gjithë të lidhur listat në hashtable. Dhe një herë ne jemi duke bërë me këtë, ne kemi shkarkuar plotësisht hashtable, dhe ne jemi duke bërë. Kështu që është e pamundur për të shkarkimit për të ndonjëherë kthimit të rreme. Dhe kur ne jemi bërë, ne vetëm kthim i vërtetë. 

Le të japim këtë zgjidhje një provoni. Pra, le të marrin një vështrim në atë tona nyje struct do të duket si. Këtu ne shohim ne do të kemi një bool Fjala dhe një nyje struct * fëmijët alfabetit kllapa. Pra, gjëja e parë që ju mund të jetë pyesin, pse është e alfabetit ed përcaktuar si 27? E pra, mos harroni se ne do të duhet për të trajtimin e apostrof. Kështu që do të jetë disi e një rast i veçantë gjatë këtij programi. 

Tani mos harroni se si një Trie në të vërtetë punon. Le të thonë se ne jemi duke indeksimin fjalën "Cats". Pastaj nga rrënja e Trie, ne jemi duke shkuar për të parë fëmijët array, dhe ne do të shohim në Indeksi që korrespondon me letrën C. Kështu që do të indeksuar 2. Pra duke pasur parasysh se, se vullneti na japin një nyje të re. Dhe pastaj ne do të punojmë nga ajo nyje. 

Pra, duke pasur parasysh se nyjen, ne jemi edhe një herë duke shkuar për të parë në grup fëmijëve. Dhe ne jemi duke shkuar për të parë në indeksin zero të korrespondojnë me A në mace. Pra, atëherë ne jemi duke shkuar për të shkuar në atë nyje, dhe duke pasur parasysh se nyja ne jemi duke shkuar për të parë në fund është një korrespondon të T. Dhe të lëvizin për në atë nyje, më në fund, ne kemi shikuar plotësisht nëpërmjet fjala jonë "cat". Dhe tani bool Fjala është menduar për të treguar nëse kjo fjalë e dhënë është në të vërtetë një fjalë. 

Pra, pse nuk kemi nevojë për këtë rast të veçantë? E pra çfarë i fjalës "katastrofë" është në fjalorin tonë, por Fjala "cat" nuk është? Pra, dhe duke kërkuar për të parë nëse fjala "cat" është në fjalorin tonë, ne jemi do të me sukses të parë përmes indekset C-A-T në nyje rajon. Por kjo është vetëm për shkak katastrofë ndodhur për të krijuar nyjet në rrugë nga C-A-T, gjitha mënyra për të fundi i fjalës. Pra bool fjalë është përdorur për të treguar nëse këtë vend të veçantë në të vërtetë tregon një fjalë. 

Dakord. Pra, tani që ne e dimë se çfarë është e Trie do të duken si, le të shohim në ngarkesës funksion. Pra ngarkesës do të kthejë një bool Sepse ne sukses apo pa sukses ngarkuar fjalor. Dhe kjo do të jetë fjalor që ne duam të ngarkesës. 

Pra gjëja e parë që ne jemi të bëni është e hapur up këtë fjalor për lexim. Dhe ne duhet të sigurohemi ne nuk dështojnë. Pra, nëse fjalor nuk ishte u hap me sukses, ajo do të kthehet null, rast në të cilin ne jemi do të kthimit të rreme. Por, duke supozuar se ajo me sukses hapur, atëherë ne në fakt mund të lexoni përmes fjalorit. 

Pra gjëja e parë që ne jemi duke shkuar për doni të bëni është të kemi këtë rrënjë globale ndryshueshme. Tani rrënjë do të jetë një nyje *. Është maja e Trie sonë se ne jemi do të iterating përmes. Pra, gjëja e parë që ne jemi duke shkuar të doni të bëni është të ndajë kujtesës për rrënjë tonë. Vini re se ne jemi duke përdorur calloc funksion, e cila është në thelb njëjtë si funksion malloc, përveç se është garantuara për të kthyer diçka që është zeroed krejtësisht jashtë. Pra, nëse kemi përdorur malloc, ne do të duhet të kalojnë nëpër të gjitha pointers në tonë nyje, dhe të sigurohemi që ata janë të gjithë null. Pra calloc do të bëjë atë për ne. 

Tani ashtu si malloc, ne kemi nevojë për të bërë i sigurt se ndarja ishte në të vërtetë suksesshëm. Nëse kjo kthye null, atëherë ne nevojë për të mbyllur ose dictionary paraqesë dhe të kthimit të rreme. Pra, duke supozuar se alokimin u suksesshme, ne jemi duke shkuar për të përdorur një nyje * kursorin për të iterate përmes Trie tonë. Pra, rrënjët tona kurrë nuk do të ndryshojë, por ne jemi duke shkuar për të përdorur kursorin për të në fakt shkojnë nga nyje në nyje. 

Pra, në këtë lak për ne duke e lexuar përmes fjalorit file. Dhe ne jemi duke përdorur fgetc. Fgetc do të kap një të vetme karakter nga file. Ne jemi duke shkuar për të vazhduar grabbing karaktere ndërsa ne nuk e arrijnë fund të file. 

Ka dy raste ne kemi nevojë për të trajtuar. E para, nëse karakteri nuk ishte një linjë e re. Pra, ne e dimë nëse kjo ishte një linjë e re, atëherë ne jemi gati për të lëvizur në një fjalë të re. Por duke supozuar se nuk ishte një linjë e re, atëherë këtu ne duam të kuptoj se Indeksi ne do të indeksit në në rrjet fëmijëve që kemi shikuar në para. 

Pra, si kam thënë më parë, ne kemi nevojë për të rast i veçantë apostrof. Vini re që ne jemi duke përdorur tresh Operatori këtu. Pra, ne jemi duke shkuar për të lexuar këtë si, në qoftë se karakteri ne lexojmë në ishte një apostrof, atëherë ne jemi duke shkuar për të vendosur Indeksi = "alfabetit" -1, i cili do të të jetë indeksi 26. 

Tjetër, në qoftë se ajo nuk ishte një apostrof, ka ne jemi duke shkuar për të vendosur indeksin barabartë me C - a. Pra mbani mend, dikur prapa nga p-vë, c - a do të na japë Pozita alfabetike e C. Pra, nëse C është shkronja A, kjo do të na japin indeksin zero. Për të letrës B, ajo do të japë na indeksi 1, dhe kështu me radhë. 

Pra, kjo na jep indeksin në Fëmijët array që ne duam. Tani në qoftë se ky indeks është aktualisht null në fëmijët, që do të thotë se një nyje nuk ekziston aktualisht nga ajo rrugë. Pra, ne duhet të ndajë një nyje për atë rrugë. Kjo është ajo që ne do të bëjmë këtu. 

Pra, ne jemi duke shkuar për të përdorur përsëri calloc funksion, në mënyrë që ne nuk duhet të zero të gjitha pointers. Dhe ne përsëri duhet të kontrolloni se calloc nuk dështojnë. Nëse calloc ka dështojnë, atëherë ne kemi nevojë për të shkarkuar çdo gjë, të mbyllur tonë fjalor, dhe kthimit të rreme. Pra, duke supozuar se ajo nuk dështojnë, atëherë kjo do të krijojë një fëmijë të ri për ne. Dhe ne do të shkojmë në atë fëmijë. Kursori ynë do të iterate poshtë për atë fëmijë. 

Tani në qoftë se kjo nuk ishte null për të filluar me, pastaj kursori mund vetëm të iterate poshtë për këtë fëmijë të vërtetë pa pasur nevojë të ndajë asgjë. Ky është rasti ku ne ka ndodhur e parë ndajë fjalën "cat." Dhe që do të thotë kur të shkojmë për të alokuar "Katastrofë," ne nuk kanë nevojë për të krijuar nyje për C-A-T përsëri. Ata tashmë ekzistojnë. 

Çfarë është kjo tjetër? Kjo është gjendja ku c është backslash n, ku c është një linjë e re. Kjo do të thotë se ne kemi sukses përfunduar një fjalë. Tani çfarë ne duam të bëjmë kur ne përfunduar me sukses një fjalë? Ne jemi duke shkuar për të përdorur këtë fushë fjalën brenda nyjeve tonë struct. Ne duam të vendosur që për të vërtetë. Pra kjo tregon se kjo nyje tregon një suksesshëm fjalë, një fjalë e vërtetë. 

Tani vendosur që për të vërtetë. Ne duam të rivendosur kursorin tonë për pikë në fillim të Trie perseri. Dhe së fundi, rritje fjalorin tonë madhësia, pasi kemi gjetur një tjetër punë. Pra, ne do të vazhdojmë të bëjmë atë, lexuar në karakter me karakter, ndërtimin nyje të reja në Trie tonë dhe për çdo fjalë në fjalor, deri ne fund arrijnë C! = EOF, në të cilën rast kemi të thyer nga file. 

Tani ka dy raste nën të cilat ne mund të ketë goditur EOF. E para është nëse ka pasur një gabim leximi nga file. Pra, nëse ka pasur një gabim, ne duhet të bëni tipike. Shkarkoj çdo gjë, në afërsi fotografi, kthimit të rreme. Duke supozuar se nuk ishte një gabim, që thjesht do të thotë që ne të vërtetë goditi në fund të fotografi, në të cilin rast, ne mbyllim paraqesë dhe të kthehet e vërtetë që kemi ngarkuar me sukses fjalor në Trie tonë. 

Pra, tani le të shikoni kontroll. Duke parë në funksionin e kontrollit, ne shohim kontrolloni se do të kthehet një bool. Ajo jep true nëse këtë fjalë që është e duke u kaluar është në Trie tonë. Ajo kthen false ndryshe. Pra, si jeni përcaktuar nëse kjo fjalë është në Trie tonë? 

Ne shohim këtu se, ashtu si më parë, ne jemi duke shkuar për të përdorur kursorin për të iterate përmes Trie tonë. Tani këtu ne do të iterate mbi gjithë fjalën tonë. Pra iterating fjalën ne jemi e kaluara, ne jemi duke shkuar për të përcaktuar Indeksi në grup fëmijëve që korrespondon fjalës kllapa I. Pra, kjo do të duken tamam si ngarkesës, ku në qoftë se fjala [i] është një apostrof, atëherë ne duam për të përdorur tregues "alfabetin" - 1. Sepse ne kemi vendosur se cilat është ajo ku ne jemi duke shkuar për të ruajtur apostrofat. 

Tjetër ne do të përdorim dy fjalë më të ulët kllapa I. Pra, mos harroni se fjala mund të kanë kapitalizim arbitrare. Dhe kështu që ne duam të sigurohemi që ne jemi duke përdorur një version vogle të gjërave. Dhe pastaj të zbriten nga ajo 'një' për herë përsëri na jepni alfabetik Pozicioni i atij karakteri. Kështu që do të jetë indeksi tonë në array fëmijëve. 

Dhe tani në rast se indeksi në fëmijët array është null, që do të thotë ne mund të vazhdojë më iterating poshtë Trie tonë. Në qoftë se është e rastit, kjo fjalë nuk mund të të jetë ndoshta në Trie tonë. Që po të ishte, që do të do të thotë se do të jetë një rrugë e poshtë për atë fjalë. Dhe ju nuk do të hasni null. Pra ndeshi null, ne kthimit të rreme. Fjala nuk është në fjalor. Po të mos ishte i pavlefshëm, atëherë ne jemi do të vazhdojë iterating. 

Pra, ne jemi duke shkuar nga atje kursorin të tregojnë për atë të veçantë nyjë në atë indeks. Ne vazhdojmë të bëjmë që të gjithë e gjithë fjala, duke supozuar ne kurrë nuk goditi null. Kjo do të thotë që ne ishim në gjendje për të marrë me e gjithë fjala dhe për të gjetur një nyje në përpjekje tonë. Por ne nuk jemi bërë mjaft ende. 

Ne nuk duam të kthehen vetëm e vërtetë. Ne duam të kthehen kursorit> fjalë. Që mos harroni përsëri, është "mace" nuk është në fjalorin tonë, dhe "katastrofë" është, atëherë ne do të kemi sukses nëpërmjet fjala "cat". Por, kursorit fjalë do të jetë e rreme dhe nuk është e vërtetë. Pra, ne kthehemi fjalë kursorin për të treguar nëse kjo nyje është në të vërtetë një fjalë. Dhe kjo është ajo për kontroll. 

Pra, le të shikoni madhësinë. Pra, madhësia do të jetë goxha e lehtë që, mos harroni në ngarkesës, ne jemi bën rritjen madhësinë fjalor për çdo fjalë që hasim. Pra, madhësia është vetëm do të kthehen madhësinë dictionary. Dhe kjo është ajo. 

Pra, së fundi ne kemi shkarkoj. Pra shkarkoj, ne do të përdorë funksion recursive të bëjë në fakt të gjithë e punës për ne. Pra, funksioni ynë do të të thirret në unloader. Çfarë është unloader do të bëni? Ne shohim këtu se unloader do të iterate mbi të gjithë fëmijët në kjo nyje të veçantë. Dhe në qoftë se fëmija nuk është nyja null, atëherë ne do të shkarkoj nyjen e fëmijëve. 

Pra, kjo është që ju Recursively shkarkoj të gjithë fëmijët tanë. Pasi ne jemi të sigurt që të gjithë fëmijët tanë janë shkarkuar, atëherë ne mund të lirë veten, kështu që shkarkoj veten. Kjo do të punojë Recursively shkarkoj gjithë Trie. Dhe pastaj një herë që është bërë, ne vetëm mund të kthehet e vërtetë. Shkarkoj nuk mund të dështojë. Ne jemi vetëm liruar gjëra. Pra, një herë ne jemi duke bërë liruar gjithçka, kthim i vërtetë. Dhe kjo është ajo. Emri im është Rob. Dhe kjo ishte speller. 

[MUSIC Playing]