>> 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.