ROB BOWDEN: Hi. Jien Rob, u hash ejja din is-soluzzjoni out. Allura hawnhekk aħna qed tmur biex jimplimentaw tabella hash ġenerali. Naraw li l-node Struct ta 'hash tagħna tabella hija ser teżamina bħal dan. Allura li għaddej biex ikollhom kelma char firxa ta 'tul daqs plus 1. Tinsiex l-1 sa l-massimu kelma fid-dizzjunarju huwa 45 karattri, u allura aħna qed tmur biex bżonn karattru wieħed żejda għall- backslash 0. 

U mbagħad tabella hash tagħna f'kull barmil se taħżen lista marbuta ta 'nodes. Aħna mhux qed tagħmel lineari probing hawn. U dan sabiex link għall-ieħor element fil-barmil, għandna bżonn node Struct * jmiss. Allura dan huwa dak node Dehra. Issa, hawnhekk huwa d-dikjarazzjoni ta 'tabella hash tagħna. Huwa ser ikollhom 16384 bramel, iżda dak in-numru ma verament kwistjoni. U fl-aħħarnett, aħna qed tmur biex ikollhom l- hashtable_size varjabbli globali, li se jibda off bħala 0, u huwa se jżommu rekord ta 'kemm kliem kienu dizzjunarju tagħna. Kull dritt. 

Mela ejja tagħti ħarsa lejn tagħbija. Allura 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 const char * star dizzjunarju, 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-dizzjunarju għal qari, u aħna qed tmur biex ikollhom biex tiżgura li hija rnexxielha hekk 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 għall malloc node wieħed. U naturalment, għandna bżonn ta 'żball verifika darb'oħra hekk jekk mallocing ma rnexxilhomx u rridu 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 word-dħul> hija l-char buffer kelma ta 'tul daqs plus wieħed li aħna qed tmur biex jaħżnu l-kelma pulzieri Allura fscanf se jirritorna 1 sakemm kif kien kapaċi b'suċċess jaqra kelma mill-fajl. 

Jekk la l-iżball iseħħ jew nilħqu l-aħħar tal-fajl, mhux se ritorn 1 f'liema każ jekk ma ritorn 1, aħna qed finalment se break minn dan loop waqt. Allura naraw li ladarba aħna rnexxielna aqra kelma in dħul-> kelma, allura aħna qed tmur biex issir hash din il-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 funzjoni 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 fl input, li tagħtik indiċi fit-tabella hash. Avviż li aħna qed modding mill NUM_BUCKETS hekk il-valur hash lura attwalment huwa indiċi fit-tabella hash u ma indiċi lil hinn mill- limiti ta 'l-array. 

Allura peress li funzjoni hash, aħna qed tmur biex hash-kelma li naqraw mill-dizzjunarju u allura aħna qed tmur għall-użu li għandha tiddaħħal l- dħul fis-tabella hash. Issa, hash hashtable hija l-kurrent lista marbuta fit-tabella hash, 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 għalhekk aħna qed tmur biex ikollhom dħul attwali tagħna punt li dak l-tabella hash bħalissa punti li u allura aħna qed tmur biex jaħżnu fit-tabella hash fil-hash id-dħul attwali. 

Allura dawn iż-żewġ linji b'suċċess daħħal id-dħul fil-bidu tal- lista marbuta f'dak l-indiċi fit-tabella hash. 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 jirritorna xi ħaġa non 1 fi li punt ftakar li għandna bżonn li dħul mingħajr, so up here, aħna malloced l 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 li fih każ għandna bżonn li ħielsa l-entrata li aħna qatt effettivament imqiegħda fiċ-tabella hash 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 aħna ma break out għaliex aħna laħaq l-aħħar tal-fajl? Jekk kien hemm żball, allura irridu ritorn foloz minħabba tagħbija ma tirnexxi, u fil-proċess, irridu jħottu l-kliem kollha li naqraw fi u tagħ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 ritorn vera peress konna mgħobbija b'suċċess il- dizzjunarju. U li hu għal tagħbija. 

Allura issa jiċċekkjaw, minħabba tabella hash mgħobbija, se teżamina bħal dan. Sabiex jiċċekkjaw, huwa jirritorna bool, li se jindikaw jekk l- 'għadda fil char * kelma, jekk il- għaddew fil-sekwenza huwa dizzjunarju tagħna. Hekk jekk huwa fl-dizzjunarju, jekk huwa fit-tabella hash tagħna, aħna se terġa 'lura vera, u jekk mhuwiex, aħna se terġa 'lura falza. Minħabba din il-kelma għadda-in, aħna qed ser hash-kelma. 

Issa, ħaġa importanti li jirrikonoxxu hija li fl-tagħbija, aħna kien jaf li kollha ta ' il-kliem kienu ser ikunu minuskuli, iżda hawnhekk, aħna mhux qed hekk żgur. Jekk nieħdu ħarsa lejn funzjoni hash tagħna, funzjoni hash tagħna attwalment huwa lowercasing kull karattru tal-kelma. Allura irrispettivament mill-kapitalizzazzjoni ta ' kelma, funzjoni hash tagħna se jirritorna l-istess indiċi għal kwalunkwe l- kapitalizzazzjoni huwa kif kien ikun lura għal kollox lowercase verżjoni tal-kelma. Kull dritt. 

Allura dak indiċi tagħna. Hu l-tabella hash għal din il-kelma. Issa, dan għal loop va għal aktar minn l-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 ikomplu filwaqt li dħul ma mhux NULL ugwali, u ftakar li taġġorna l-pointer fil-lista marbuta tagħna dħul ugwali dħul-> jmiss, sabiex ikollhom punt tagħna dħul kurrenti għall- punt li jmiss fil-lista marbuta. Kull dritt. 

Allura għal kull entrata fil-lista marbuta, aħna qed tmur għall-użu strcasecmp. Mhuwiex strcmp għaliex għal darb'oħra, aħna tixtieq li tagħmel affarijiet każ insensitively. Allura aħna nużaw strcasecmp biex iqabblu l-kelma li kien mgħoddi lill din il-funzjoni kontra l-kelma li huwa f'din l-entrata. Jekk dan jirritorna 0, dan ifisser li kien hemm taqbila, f'liema każ rridu ritorn vera. Aħna b'suċċess sabet il- kelma fit-tabella hash 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 tabella hash ma kinitx tinkludi din il-kelma. U li huwa għal kontroll. Kull dritt. 

Mela ejja tagħti ħarsa lejn id-daqs. Issa, id-daqs se tkun pjuttost sempliċi peress li tiftakar fit-tagħbija, għal kull kelma sibna aħna jiżdied globali hashtable_size varjabbli. Allura l-funzjoni daqs huwa biss ser jirritorna dik globali varjabbli, 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 kollha bramel ta 'tabella hash tagħna. Allura hemm bramel NUM_BUCKETS. U għal kull lista marbuta hash tagħna mejda, aħna qed tmur biex loop madwar id- intier tal-lista marbuta ħelsien kull element. Issa, għandna bżonn li tkun attenta, so here we jkollhom varjabbli temporanja li l- ħażna tal-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 aħna meħlusa dan l- 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-listi kollha marbuta b'mod -tabella hash, u ladarba aħna qed isir ma 'dan, konna kompletament maħtuta -tabella hash, u aħna qed isir. Allura huwa impossibbli għall tħott li qatt ritorn foloz, u meta aħna qed isir, aħna biss ritorn vera.