[Daqq tal-mużika] 

ROB BOWDEN: Hi. Jien Rob. U ejja din is-soluzzjoni out. Allura hawnhekk aħna qed tmur biex jimplimentaw tabella ġenerali. Naraw li l-node Istituzzjonjijiet ta 'tagħna tabella hija ser teżamina bħal dan. Allura li għaddej biex ikollhom kelma char firxa ta 'daqs TUL + 1. Tinsiex l + 1, peress li l-massimu kelma fid-dizzjunarju huwa 45 karattri. U allura aħna qed tmur għall-bżonn waħda extra karattru għall-zero backslash. 

U mbagħad hashtable tagħna f'kull barmil se taħżen lista marbuta ta 'nodes. Aħna mhux qed jagħmlu lineari probing hawn. U dan sabiex link għall-ieħor element fil-barmil, għandna bżonn node Struct * jmiss. OK. Allura dan huwa dak node Dehra. 

Issa hawnhekk huwa d-dikjarazzjoni ta hashtable tagħna. Huwa ser ikollhom 16834 bramel. Imma dak in-numru ma verament kwistjoni. U fl-aħħarnett, aħna qed tmur biex ikollhom l- globali daqs hashtable varjabbli, li se jibda off bħala zero. U li għaddej biex iżommu kont ta 'kif ħafna kliem huma fil-dizzjunarju tagħna. 

Mela ejja tagħti ħarsa lejn tagħbija. Avviż li tagħbija, dan jirritorna a bool. Inti tirritorna veru jekk kien b'suċċess mgħobbija, u falza mod ieħor. U li tieħu char dizzjunarju * const, li hija l-dizzjunarju li aħna rridu li tiftaħ. Allura dak hu l-ewwel ħaġa aħna qed tmur biex tagħmel. 

Aħna ser fopen l- dizzjunarju għall-qari. U aħna qed tmur biex ikollhom jagħmlu ċert li hija rnexxielha. Mela jekk huwa lura NULL, allura aħna ma miftuħa b'suċċess-dizzjunarju. U għandna bżonn li jirritornaw falza. Iżda jekk wieħed jassumi li għamlet b'suċċess miftuħa, allura aħna trid taqra l- dizzjunarju. Sabiex iżommu looping sakemm insibu xi raġuni għal break out ta 'dan loop, li aħna ser tara. Sabiex iżommu looping. 

U issa aħna qed tmur biex malloc node wieħed. U ovvjament għandna bżonn għall-arja erġa 'ċċekkja. Mela jekk mallocing ma tirnexxi, allura irridu li jħottu kwalunkwe node li aħna ġara malloc qabel, tagħlaq il- dizzjunarju u r-ritorn foloz. Iżda jinjora li, jekk wieħed jassumi aħna irnexxielu, allura irridu li jużaw fscanf biex jaqraw kelma waħda minn tagħna dizzjunarju fis node tagħna. Mela ftakar li d-dħul> kelma hija l-char buffer kelma ta 'daqs LENGHTH + 1 li aħna qed tmur biex jaħżnu l-kelma pulzieri 

Allura fscanf se jirritorna 1, sakemm kif kien kapaċi b'suċċess aqra kelma mill-fajl. Jekk la l-iżball iseħħ, jew aħna jilħqu t-tmiem tal-file, mhux se terġa 'lura 1. F'liema każ ma ritorn 1, aħna qed finalment se break out ta ' dan loop waqt. Allura naraw li ladarba aħna rnexxielna aqra kelma in dħul> kelma, allura aħna qed tmur biex dak kelma li jużaw funzjoni hash tagħna. 

Ejja tagħti ħarsa lejn il-funzjoni hash. Allura inti ma verament bżonn biex jifhmu dan. U fil-fatt aħna biss jinġibed dan hash jiffunzjonaw mill-internet. L-unika ħaġa li għandek bżonn biex jirrikonoxxu hija li dan jieħu const char * kelma. Allura huwa tieħu string bħala input, u jirritorna int mhux iffirmat bħala output. Hekk li kollox funzjoni hash, huwa jieħu fil input u tagħtik indiċi fil-hashtable. 

Avviż li aħna qed moding mill NUM_BUCKETS, hekk li l-valur lura attwalment huwa indiċi fil-hashtable u ma indiċi lil hinn mill- limiti ta 'l-array. Allura peress li funzjoni, aħna qed tmur biex hash-kelma li naqraw l- dizzjunarju. U allura aħna qed tmur għall-użu li hash li daħħal il- dħul fl-hashtable. 

Hash issa hashtable hija l-kurrent marbuta lista fit-tabella. U huwa ferm possibbli li huwa biss NULL. Aħna rridu li daħħal id-dħul tagħna fl- bidu ta 'din il-lista marbuta. U hekk aħna qed tmur biex ikollhom attwali tagħna punt ta 'dħul għal dak l-hashtable bħalissa punti li. U allura aħna qed tmur biex jaħżnu, fil-hashtable fil- hash, l-entrata attwali. Allura dawn iż-żewġ linji b'suċċess daħħal id-dħul fil-bidu tal- lista marbuta f'dak l-indiċi fil-hashtable. 

Ladarba aħna qed isir ma 'dan, nafu li sibna kelma oħra fil- dizzjunarju, u aħna inkrement darb'oħra. Allura aħna iżommu tagħmel li sakemm fscanf finalment lura xi ħaġa non-1 fi li punt ftakar li għandna bżonn biex ħielsa dħul. Allura up here we malloced dħul. U aħna ppruvaw biex taqra xi ħaġa mill-dizzjunarju. U aħna ma taqra b'suċċess xi ħaġa mill-dizzjunarju, fil- f'liema każ għandna bżonn biex ħielsa-dħul li aħna qatt ma attwalment tqiegħed fil- hashtable, u finalment break. 

Ladarba aħna break out jeħtieġ li naraw, ukoll, aħna ma break out għaliex hemm kien żball qari mill-fajl? Jew ma we break out għaliex aħna laħqu t-tmiem tal-fajl? Jekk kien hemm żball, imbagħad irridu li jirritornaw falza. Minħabba tagħbija ma rnexxilhomx. U fil-proċess irridu li jħottu il-kliem kollha li naqraw fil-, u jagħlaq il-fajl dizzjunarju. 

Jekk wieħed jassumi aħna ma tirnexxi, allura aħna biss xorta jeħtieġ li tagħlaq il-dizzjunarju fajl, u finalment jirritorna veru peress li aħna mgħobbija b'suċċess-dizzjunarju. U li hu għal tagħbija. Allura issa check, mogħtija hashtable mgħobbija, se teżamina bħal dan. Sabiex jiċċekkjaw, huwa jirritorna bool, li hija ser tindika jekk l-għadda fil char * kelma, jekk il għaddiet fil string huwa dizzjunarju tagħna. Hekk jekk huwa fl-dizzjunarju, jekk dan ikun fl hashtable tagħna, aħna se terġa 'lura veru. U jekk mhuwiex, aħna se terġa 'lura falza. 

Minħabba dan għadda fil-kelma, aħna qed ser hash-kelma. Issa ħaġa importanti li jirrikonoxxu hija li fit-tagħbija aħna kien jaf li kollha ta 'l- kliem aħna qed tmur biex tkun żgħira. Imma hawn aħna mhux qed hekk żgur. Jekk nieħdu ħarsa lejn funzjoni hash tagħna, funzjoni hash tagħna attwalment huwa casing inqas kull karattru tal-kelma. Allura irrispettivament mill-kapitalizzazzjoni ta ' kelma, funzjoni hash tagħna huwa r-ritorn l-istess indiċi għal kwalunkwe l- kapitalizzazzjoni huwa, kif kien ikun lura għal kollox lowercase verżjoni tal-kelma. Alright. C'est indiċi tagħna hija fil- hashtable għal din il-kelma. 

Issa dan għal loop se jtenni fuq il-lista marbuta li kienet f'dak l-indiċi. Allura avviż aħna initializing dħul għall-punt li l-indiċi. Aħna ser tkompli filwaqt li dħul! = NULL. U ftakar li taġġorna l-pointer fl-entrata tagħna marbuta lista = dħul> jmiss. Allura jkollhom punt tagħna entrata attwali biex il-punt li jmiss fil-lista marbuta. 

Allura għal kull entrata fil-lista marbuta, aħna qed tmur għall-użu strcasecmp. Mhuwiex strcomp. Minħabba darb'oħra, irridu tagħmel affarijiet każ insensitively. Allura aħna nużaw strcasecmp biex iqabblu l- kelma li kien mgħoddi permezz ta 'dan funzjoni kontra l-kelma li huwa f'din l-entrata. Jekk dan jirritorna żero, dan ifisser li kien hemm taqbila, f'liema każ rridu ritorn vera. Aħna b'suċċess sabet il- kelma hashtable tagħna. 

Jekk ma kienx hemm taqbila, allura aħna qed ser loop darb'oħra u ħarsa lejn il- dħul li jmiss. U aħna ser tkompli looping filwaqt li hemm iskrizzjonijiet f'din il-lista marbuta. X'jiġri jekk aħna break minn dan għal loop? Dan ifisser li aħna ma sabx ta 'dħul li mqabbla din il-kelma, f'liema każ nerġgħu lura falza li tindika li tagħna hashtable ma kinitx tinkludi din il-kelma. U li l-verifika. 

Mela ejja tagħti ħarsa lejn id-daqs. Issa daqs se tkun pjuttost sempliċi. Peress tiftakar fit-tagħbija, għal kull kelma sibna, aħna jiżdied globali daqs hashtable varjabbli. Allura l-funzjoni daqs huwa biss se li jirritornaw varjabbli globali. U thats it. 

Issa finalment, għandna bżonn li jħottu l- dizzjunarju ladarba kollox isir. Allura kif huma aħna se tagħmel dan? Dritt hawn aħna qed looping fuq bramel kollha tal-mejda tagħna. Allura hemm bramel NUM_BUCKETS. U għal kull lista marbuta tagħna hashtable, aħna qed tmur biex jiffurmaw ingassa l-intier tal-lista marbuta, ħelsien kull element. 

Issa għandna bżonn li tkun attenta. Allura hawnhekk għandna varjabbli temporanju thats ħażna l-pointer għall-ieħor element fil-lista marbuta. U allura aħna qed tmur għall-free l-element attwali. Għandna bżonn biex tkun ċert nagħmlu dan peress li aħna tista 'mhux biss ħielsa l-element attwali u mbagħad jippruvaw jaċċessaw l-pointer li jmiss, peress li ladarba konna meħlusa dan, il-memorja ssir invalida. 

Għalhekk għandna bżonn li jżommu madwar pointer biex l-element li jmiss, allura nistgħu ħielsa l- element attwali, u allura nistgħu taġġorna element attwali tagħna għall-punt li l-element li jmiss. Aħna ser loop filwaqt li hemm elementi f'din il-lista marbuta. Aħna ser tagħmel dan għal kulħadd marbuta listi fil-hashtable. U ladarba aħna qed isir ma 'dan, aħna ħadthom kompletament jinħattu l hashtable, u aħna qed isir. Allura huwa impossibbli għall jħottu li qatt ritorn foloz. U meta aħna qed isir, aħna biss ritorn vera. 

Ejjew nagħtu din is-soluzzjoni jipprova. Mela ejja tagħti ħarsa lejn dak tagħna node Struct se look like. Hawnhekk naraw aħna qed tmur biex ikollhom bool kelma u node Istituzzjonjijiet * tfal ALPHABET bracket. Allura l-ewwel ħaġa li inti jista 'jkun mintix, għaliex huwa ALPHABET ed definita bħala 27? Ukoll, ftakar li aħna qed tmur għall-ħtieġa li għandu jittratta l-apostrophe. Allura li għaddej biex tkun kemmxejn ta ' Każ speċjali matul dan il-programm. 

Issa ftakar kif trie attwalment xogħlijiet. Ejja ngħidu aħna qed indiċjar-kelma "qtates." Imbagħad mill-għeruq ta 'trie, aħna qed tmur biex tħares lejn it-tfal array, u aħna qed tmur biex tħares lejn il- indiċi li tikkorrispondi għall-ittra C. Allura li se jiġu indiċjati 2. Allura peress li, li se agħtina node ġdid. U allura aħna ser jaħdmu minn dak node. 

Allura peress li node, aħna qed darb'oħra ser tħares lejn il-firxa tfal. U aħna qed tmur biex tħares lejn indiċi żero li jikkorrispondu għall-A fil-qtates. Mela allura aħna qed tmur biex tmur f'dak node, u minħabba li node aħna qed tmur li tħares lejn l-aħħar huwa tikkorrispondi li T. U jimxu fuq dak node, fl-aħħarnett, aħna għandna kompletament ħarsu permezz ta 'kelma tagħna "qattus." U issa bool kelma suppost jindikaw jekk din il-kelma mogħtija hija attwalment kelma. 

Allura għaliex għandna bżonn li każ speċjali? Ukoll dak tal-kelma "katastrofi" huwa dizzjunarju tagħna, iżda l- kelma "qattus" hija le? Hekk u tfittex biex tara jekk il-kelma "qattus" huwa dizzjunarju tagħna, aħna qed ser tfittex b'suċċess permezz l-indiċi C-A-T fir-reġjun node. Imma dak li biss minħabba katastrofi ġara biex joħolqu lymph fuq il-mod minn C-A-T, it-triq kollha li l-aħħar tal-kelma. Allura bool kelma hija użata biex tindika jekk dan il-post partikolari fil-fatt jindika kelma. 

Kull dritt. Allura issa li nafu dak li trie huwa ser look like, ejja nħarsu lejn l- tagħbija funzjoni. Allura tagħbija se jirritornaw bool għal kemm aħna b'suċċess jew mingħajr suċċess mgħobbija-dizzjunarju. U dan se jkun l-dizzjunarju li rridu tagħbija. 

Allura l-ewwel ħaġa li aħna qed tagħmel huwa miftuħ up li dizzjunarju għall-qari. U rridu niżguraw aħna ma jonqsu. Allura jekk il-dizzjunarju ma kienx miftuħa b'suċċess, din se terġa 'lura null, f'liema każ aħna qed ser jirritornaw falza. Iżda jekk wieħed jassumi li dan b'suċċess miftuħa, allura nistgħu fil-fatt taqra permezz tal-dizzjunarju. 

Allura l-ewwel ħaġa li aħna qed tmur biex trid tagħmel hu li għandna dan root varjabbli globali. Issa għeruq huwa se tkun node *. Hu l-quċċata ta 'trie tagħna li aħna qed ser jiġu mtennija permezz. Allura l-ewwel ħaġa li aħna qed tmur li trid tagħmel hu li jallokaw memorja għall-għeruq tagħna. Avviż li aħna qed tuża l-calloc funzjoni, li huwa bażikament l-istess bħala l-funzjoni malloc, ħlief huwa garantit li jirritornaw xi ħaġa li hija kompletament zeroed out. Allura jekk aħna użati malloc, għandna bżonn biex jmorru kollha permezz ta 'l-pointers fil tagħna node, u kun żgur li dawn qed kollha null. Allura calloc se tagħmel dan għalina. 

Issa bħad malloc, hemm bżonn li nagħmlu żgur li l-allokazzjoni kien effettivament suċċess. Jekk dan lura null, allura aħna bżonn li tagħlaq jew dizzjunarju fajl u r-ritorn foloz. Allura jekk wieħed jassumi li allokazzjoni kienet suċċess, aħna qed tmur biex tuża node * cursor li jtenni permezz trie tagħna. Allura għeruq tagħna qatt se jibdlu, imma aħna qed tmur biex jużaw cursor biex fil-fatt imorru minn node biex node. 

Allura f'dan għat loop aħna qed qari permezz tal-fajl dizzjunarju. U aħna qed tuża fgetc. Fgetc se grab wieħed karattru mill-fajl. Aħna ser tkompli ħtif karattri filwaqt li aħna ma jilħqu l- tmiem tal-file. 

Hemm żewġ każijiet għandna bżonn biex jimmaniġġaw. L-ewwel, jekk il-karattru ma kienx linja ġdida. Hekk nafu jekk kienx linja ġdida, allura aħna qed dwar li jimxu fuq kelma ġdida. Iżda jekk wieħed jassumi li ma kienx linja ġdida, allura hawn irridu insemmu l- indiċi aħna qed tmur għall-indiċi fi fil-firxa tfal li ħarisna lejn qabel. 

Allura, bħal I said qabel, għandna bżonn li każ speċjali tal-apostrophe. Avviż aħna qed tuża l-ternarji operatur hawn. Allura aħna qed tmur biex taqra dan bħala, jekk l-karattru naqraw fil kienet apostrophe, allura aħna qed tmur biex jistabbilixxu indiċi = "ALPHABET" -1, li se jkun l-indiċi 26. 

Else, jekk ma kienx apostrophe, hemm aħna qed tmur biex jistabbilixxu l-indiċi daqs c - a. Mela ftakar lura minn qabel kienu p-settijiet, c - a se tagħtina l- pożizzjoni alfabetika tal C. Mela jekk C hija l-ittra A, dan se agħtina indiċi żero. Għall-ittra B, se tagħti lilna l-indiċi 1, u l-bqija. 

Allura dan jagħtina l-indiċi fil- tfal array li rridu. Issa jekk dan l-indiċi bħalissa null it-tfal, li jfisser li node ma jeżistix bħalissa minn dik it-triq. Għalhekk għandna bżonn li jiġu allokati a node għal dik it-triq. Dak hu li aħna ser nagħmlu hawnhekk. 

Allura aħna qed tmur biex għal darb'oħra tuża l-calloc funzjoni, sabiex inkunu ma jkollhom żero l-pointers. U aħna napprovaw bżonn li jiċċekkja li calloc ma naqasx. Jekk calloc ma jonqsu, allura għandna bżonn li jħottu kollox, qrib tagħna dizzjunarju, u r-ritorn foloz. Allura jekk wieħed jassumi li ma ifallu, din se toħloq tifel ġdid għalina. U allura aħna se jmorru għal dak tat-tfal. Cursor tagħna se jtenni stabbiliti għal dak it-tifel. 

Issa jekk dan ma kienx null biex jibdew, allura l-cursor tista 'biss ittenni stabbiliti għal dak it-tifel mingħajr ma attwalment jkollu jalloka xejn. Dan huwa l-każ fejn aħna l-ewwel li ġara jallokaw il-kelma "qattus." U dan ifisser li meta immorru biex jallokaw "Katastrofi," aħna ma bżonn li jinħoloq nodes għal C-A-T mill-ġdid. Huma diġà jeżistu. 

X'inhu dan ieħor? Din hija l-kundizzjoni fejn c kienet backslash n, fejn c kienet linja ġdida. Dan ifisser li aħna rnexxielna temm kelma. Issa dak li rridu nagħmlu meta aħna temmew kelma? Aħna ser jużaw dan il-qasam kelma ġewwa tal node Struct tagħna. Aħna rridu li jistabbilixxu li biex veru. Allura li jindika li dan node jindika suċċess kelma, kelma attwali. 

Issa stabbilit li biex veru. Irridu reset cursor tagħna għall-punt għall-bidu tal-trie darb'oħra. U fl-aħħarnett, inkrement dizzjunarju tagħna daqs, peress li aħna sabu xogħol ieħor. Allura aħna qed tmur biex iżommu tagħmel dan, qari fil-karattru minn karattru, kostruzzjoni lymph ġodda fil trie tagħna u għal kull kelma fil-dizzjunarju, sakemm aħna finalment jilħqu C! = EOF, li fih każ aħna break out tal-fajl. 

Issa hemm żewġ każijiet taħt li aħna jista 'jkollha hit EOF. L-ewwel huwa jekk kien hemm żball qari mill-fajl. Allura jekk kien hemm żball, aħna bżonn tagħmel l-tipiċi. Jħottu kollox, qrib il-fajl, ritorn foloz. Jekk wieħed jassumi li ma kien hemm żball, dak ifisser biss għandna attwalment laqat il-aħħar ta ' il-fajl, f'liema każ, aħna qrib il- fajl u r-ritorn vera peress li aħna dizzjunarju mgħobbija b'suċċess fis trie tagħna. 

Allura issa ejja check out check. Ħarsa lejn il-funzjoni kontroll, naraw dak il-kontroll se jirritornaw bool. Dan jirritorna minnu jekk din il-kelma li huwa jiġu mgħoddija huwa trie tagħna. Dan jirritorna falza mod ieħor. Allura kif inti jiddeterminaw jekk din il-kelma hija fil trie tagħna? 

Naraw hawnhekk li, bħal qabel, aħna qed tmur biex jużaw cursor biex jtenni permezz trie tagħna. Issa hawnhekk aħna qed tmur biex jtenni fuq kelma tagħna kollu. Allura mtennija fuq il-kelma aħna passat, aħna qed tmur biex tiddetermina l- indiċi fil-firxa tfal li jikkorrispondi għall-kelma bracket I. Allura dan hija ser tfittex eżattament bħal tagħbija, fejn jekk kelma [i] huwa apostrophe, allura irridu tuża indiċi "ALPHABET" - 1. Għaliex aħna determinati li din huwa fejn aħna qed tmur biex jaħżnu apostrophes. 

Else aħna qed tmur biex tuża żewġ kelma t'isfel bracket I. Sabiex tiftakar din il-kelma tista ' jkollhom kapitalizzazzjoni arbitrarja. U hekk irridu niżguraw li aħna qed permezz ta 'verżjoni zghar ta' affarijiet. U mbagħad naqqas minn dak 'a' għal darba darb'oħra tagħtina l alfabetiku pożizzjoni ta 'dan il-karattru. Allura li għaddej biex tkun indiċi tagħna fil-firxa tfal. 

U issa jekk f'dak l-indiċi fil-tfal array huwa null, dan ifisser li aħna m'għadhomx jistgħu jkomplu jiġu mtennija down trie tagħna. Jekk dan huwa l-każ, din il-kelma ma tistax possibbilment fil trie tagħna. Peress li kieku kien, li kieku jfissirx ikun hemm passaġġ stabbiliti għal din il-kelma. U int qatt ser tiltaqa null. Allura jiltaqgħu null, nerġgħu lura falza. Il-kelma mhijiex fid-dizzjunarju. Jekk ma jkunx null, allura aħna qed se tkompli mtennija. 

Allura aħna qed tmur hemmhekk cursor għall-punt li dak partikulari node f'dak l-indiċi. Aħna iżommu tagħmel li matul il-kelma kollu, jekk wieħed jassumi aħna qatt hit null. Dan ifisser li aħna kienu kapaċi jiksbu permezz il-kelma kollu u jsibu a node fl jipprova tagħna. Iżda aħna mhux qed pjuttost isir s'issa. 

Aħna ma jridux biss jirritornaw veru. Aħna rridu li jirritornaw cursor> kelma. Peress li tiftakar darb'oħra, huwa "qattus" ma dizzjunarju tagħna, u "katastrofi" huwa, allura aħna se b'suċċess nikbru permezz tal-kelma "qattus." Iżda cursor kelma se tkun falza u mhux veru. Allura aħna ritorn kelma cursor biex jindikaw jekk dan node huwa attwalment kelma. U li huwa għal kontroll. 

Mela ejja check out daqs. Allura daqs se tkun pjuttost faċli peress li, ftakar fit-tagħbija, aħna qed inkrementazzjoni daqs dizzjunarju għal kull kelma li aħna jiltaqgħu. Allura daqs huwa biss se ritorn daqs dizzjunarju. U thats it. 

Allura fl-aħħar għandna jħottu. Allura jħottu, aħna qed tmur biex tuża funzjoni jirrikorri għall-fatt jagħmlu kollha tax-xogħol għalina. Allura funzjoni tagħna se jiġi msejjaħ unloader. X'inhu unloader se jagħmlu? Naraw hawnhekk li unloader se jtenni fuq kollha tat-tfal fil- dan node partikolari. U jekk il-node wild ma jkunx null, allura aħna qed tmur biex jħottu l-node tfal. 

Allura dan huwa inti recursively jħottu kollha tat-tfal tagħna. Ladarba aħna qed żgur li kollha tat-tfal tagħna ikunu mniżżla, allura aħna jistgħu ħielsa lilna nfusna, hekk jħottu nfusna. Dan se taħdem recursively jħottu l trie kollu. U mbagħad darba li isir, nistgħu biss ritorn vera. Jħottu ma tistax tonqos. Aħna biss ħelsien affarijiet. Allura ladarba aħna qed isir ħelsien kollox, ritorn vera. U thats it. Jisimni Rob. U dan kien speller. 

[Daqq tal-mużika]