>> Rob BOWDEN: Hi.
Ako Rob, at hash let ni solusyon na ito out.
Kaya dito kami ay pagpunta sa ipatupad isang pangkalahatang hash table.
Nakita namin na ang struct node ng aming hash talahanayan ay pagpunta sa ganito ang hitsura.
Kaya ito ay pagpunta sa magkaroon ng isang pansamantalang trabaho salita array ng haba laki ng plus 1.
Huwag kalimutan ang 1 dahil ang maximum salita sa diksyunaryo ay 45
mga character, at pagkatapos kami ay pagpunta sa kailangan isa dagdag ng character para sa mga
backslash 0.
>> At pagkatapos ay aming hash talahanayan sa bawat bucket ay pagpunta sa mag-imbak ng
naka-link na listahan ng mga node.
Hindi namin ginagawa linear probing dito.
At kaya upang mai-link sa susunod sangkap sa mga bucket, kailangan namin ng isang
struct node * susunod.
Kaya na kung ano ang hitsura ng isang node tulad.
Ngayon, dito ay ang deklarasyon ng aming hash table.
Ito ay pagpunta sa may 16,384 mga bucket, ngunit numerong iyon ay hindi talagang mahalaga.
At sa wakas, kami ay pagpunta sa may global variable hashtable_size, na
Pupunta upang simulan off bilang 0, at ito ay pagpunta sa masubaybayan kung gaano karaming mga salita
ay nasa aming diksyunaryo.
Ayos lang.
>> Kaya ipaalam sa tumagal ng isang pagtingin sa pag-load.
Kaya mapapansin na ang pag-load, Ibinabalik nito ang isang bool.
Ikaw nagbabalik ng tunay na kung matagumpay na ito ay na-load at hindi totoo kung hindi man.
At ito ay tumatagal ng isang const pansamantalang trabaho * star diksyonaryo, kung saan ay ang diksyunaryo
na nais naming buksan.
Kaya iyon ang unang bagay kami ay pagpunta sa gawin.
Kami ay pagpunta sa fopen sa diksyunaryo para sa pagbabasa, at kami ay pagpunta sa may
upang matiyak na ito Nagtagumpay kaya kung ibinalik na ito null, pagkatapos kami ay hindi
Matagumpay na buksan ang diksyunaryo at kailangan namin upang bumalik hindi totoo.
>> Ngunit sa pag-aakala na matagumpay na ginawa ito bukas, pagkatapos ay nais naming basahin ang
diksiyunaryo.
Kaya panatilihin looping hanggang sa mahanap namin ang ilang dahilan upang masira out ng ito
loop na kung saan ipapakita namin makita.
Kaya panatilihin looping, at ngayon kami ay pagpunta sa malloc isang solong node.
At siyempre, kailangan naming i-check error muli kaya kung mallocing hindi nagtagumpay
at gusto naming mag-ibis anumang node na namin nangyari bago sa malloc, isara ang
diksyunaryo at bumalik hindi totoo.
>> Ngunit hindi papansin ang na, sa pag-aakala namin nagtagumpay, pagkatapos ay nais naming gamitin fscanf
basahin ang isang solong salita mula sa aming diksyunaryo sa aming mga node.
Kaya tandaan na ang entry-> salita ay ang pansamantalang trabaho salita buffer ng haba laki ng plus
isa na kami ng pagpunta sa mag-imbak ang salitang in
Kaya fscanf ay pagpunta upang bumalik 1 hangga't dahil ito ay matagumpay na mai-basahin ang isang
salita mula sa file.
>> Kung nangyari ang alinman sa isang error o maabot namin sa dulo ng file, ito ay hindi
bumalik 1 sa kasong ito kung hindi bumalik 1, sa wakas kami ay pagpunta sa masira
out ng ito habang loop.
Kaya nakikita natin na sa sandaling matagumpay na mayroon kami basahin ang isang salita sa
entry-> salita, pagkatapos kami ay pagpunta sa hash ang salitang iyon gamit ang aming hash.
Hayaan ang kumuha ng isang pagtingin sa ang hash.
>> Kaya huwag talagang kailangan mo upang maunawaan ito.
At talagang, na nakuha namin ito lamang hash mula sa internet.
Ang tanging bagay na kailangan mo upang makilala ang na ito ay tumatagal ng isang const pansamantalang trabaho * salita,
kaya tumatagal string na ito bilang input at bumabalik isang wala pang kontratang int bilang output.
Kaya iyon ang lahat ng hash function na ay, ay ito tumatagal sa isang input, nagbibigay ito sa iyo ng isang
index sa hash table.
Pansinin na aming Modding sa pamamagitan ng NUM_BUCKETS kaya ibinalik ang halaga ng hash
talaga ay isang index sa hash talahanayan at hindi ini-index nang higit sa
hanggahan ng array.
>> Kaya ibinigay na hash, ipinapadala namin ng pagpunta sa hash ang salita na aming basahin
mula sa diksyunaryo at pagkatapos kami ay pagpunta gamitin na may upang ipasok ang
entry sa hash table.
Ngayon, hashtable hash ay ang kasalukuyang naka-link na listahan sa hash talahanayan, at
ito ay napaka posible na lamang null.
Gusto naming upang ipasok ang aming entry sa simula ng ito na naka-link listahan, at sa gayon
kami ay pagpunta sa may aming kasalukuyang entry tumuturo sa kung ano ang hash talahanayan sa kasalukuyan
mga punto upang at pagkatapos kami ay pagpunta upang mag-imbak sa hash talahanayan sa hash
ang kasalukuyang entry.
>> Kaya matagumpay na ipasok ang dalawang mga linya ang entry sa simula ng
naka-link na listahan sa index na sa hash table.
Sa sandaling tapos na kami doon, alam namin nakakita kami ng isa pang salita sa
diksyunaryo at kami dinagdagan muli.
Kaya panatilihin namin ang paggawa na hanggang fscanf sa wakas ay nagbabalik ng isang bagay na hindi pang 1 sa
na kung saang tandaan na kailangan namin upang libreng entry, kaya hanggang dito, malloced kami ng isang
entry at sinubukan naming basahin ang isang bagay mula sa diksyunaryo.
At kami ay hindi matagumpay na basahin isang bagay mula sa diksyunaryo kung saan
sakaling kailangan namin upang palayain ang entry na kami hindi kailanman talagang ilagay sa hash talahanayan
at sa wakas ay masira.
>> Sa sandaling magsimula namin, kailangan naming makita, mahusay, ay masira kami out dahil mayroong
ay isang error sa pagbabasa mula sa file, o ay masira kami out dahil naabot namin
sa dulo ng file?
Kung nagkaroon ng error, pagkatapos ay nais naming bumalik hindi totoo dahil ang hindi pagkarga
magtagumpay, at sa proseso, nais naming alisan ng bala lahat ng mga salita na aming basahin
sa at isara ang file na diksiyunaryo.
Sa pag-aakala namin ginawa magtagumpay, pagkatapos namin lamang kailangan pa rin upang isara ang diksyunaryo
maghain, at sa wakas ay nagbabalik ng tunay na mula noong matagumpay naming na-load ang
diksiyunaryo.
At na ito para sa pag-load.
>> Kaya ngayon suriin, bibigyan ng load hash talahanayan, ay pagpunta sa ganito ang hitsura.
Kaya tingnan, nagbabalik ito ng isang bool, na Pupunta upang ipahiwatig kung ang
pumasang-in pansamantalang trabaho * salita, kung ang pumasang-in string ay nasa aming diksyunaryo.
Kaya kung ito ay nasa sa diksyunaryo, kung ito ay sa aming hash talahanayan, magkakaroon kami bumalik
totoo, at kung hindi, ay namin bumalik false.
Given na ito ang pumasa sa-sa salita, kami ay pagpunta sa hash ang salita.
>> Ngayon, ang isang mahalagang bagay upang makilala ang na sa pag-load, alam namin na ang lahat ng
ang mga salita ay pagpunta sa maging mas mababa kaso, ngunit dito, hindi kami kaya sigurado.
Kung tumagal kami ng isang tumingin sa aming hash, ang aming hash talaga
ay lowercasing bawat karakter ng salita.
Kaya anuman ang capitalization ng salita, ang aming hash ay pagpunta sa
ibalik ang parehong index para sa anumang mga capitalization ay gaya ng ang mga ito ay may
ibinalik para sa isang ganap na lowercase bersyon ng salita.
Ayos lang.
>> Kaya iyon ang aming index.
Ito ay ang talahanayan ng hash para sa salitang ito.
Ngayon, ito para sa loop ay pagpunta sa ibabaw ng naka-link na listahan
na noon ay sa index iyon.
Kaya't mapapansin ay Sinisimulan namin entry upang tumuro sa index iyon.
Kami ay pagpunta upang magpatuloy habang entry gumagana hindi katumbas null, at tandaan na
ina-update ang pointer sa aming listahan na naka-link entry ay katumbas ng entry-> susunod, kaya may
aming kasalukuyang entry point sa susunod na item sa naka-link na listahan.
Ayos lang.
>> Kaya para sa bawat entry sa naka-link na listahan, kami ay pagpunta sa gamitin strcasecmp.
Hindi ito strcmp dahil sa sandaling muli, namin gusto gawin kaso bagay insensitively.
Kaya ginagamit namin strcasecmp upang ihambing ang salitang na pumasa sa mga ito sa function na
laban sa mga salita na ay nasa ang entry na ito.
Kung nagbabalik ito 0, ibig sabihin nagkaroon isang tugma, kung saan nais naming
nagbabalik ng tunay.
Kami matagumpay nahanap ang salita sa aming hash table.
>> Kung nagkaroon hindi isang tugma, pagkatapos kami ay pagpunta sa loop muli at tumingin sa
susunod na entry.
At patuloy kaming looping habang doon mga entry sa naka-link na ito listahan.
Ano ang mangyayari kung masira namin out na ito para sa loop?
Nangangahulugan iyon na hindi kami nakahanap ng isang entry na tugmang salita na ito, kung saan
bumalik kami huwad upang ipahiwatig na ang aming hash talahanayan ay hindi naglalaman ng salitang ito.
At na ito para sa check.
Ayos lang.
>> Kaya ipaalam sa tumagal ng isang pagtingin sa laki.
Ngayon, laki ay magiging kaakit-akit na simple dahil tandaan sa pag-load, para sa bawat salita
nakita namin incremented kami ng isang global variable hashtable_size.
Kaya ang function ng laki ay lamang pagpunta sa bumalik na global
variable, at iyon ito.
>> Ngayon sa wakas, kailangan naming mag-ibis ang diksyunaryo-sabay ang lahat ng bagay tapos na.
Kaya paano kami makapupunta sa gawin iyon?
Kanan dito, kami ay looping sa ibabaw ng lahat mga bucket ng aming hash table.
Kaya may mga NUM_BUCKETS bucket.
At para sa bawat naka-link na listahan sa aming hash talahanayan, kami ay pagpunta sa loop sa ibabaw ng
kabuuan ng naka-link na listahan pagbabakante bawat elemento.
Ngayon, kailangan naming maging maingat, kaya dito kami magkaroon ng isang pansamantalang variable na
pag-iimbak ang pointer sa susunod elemento sa naka-link na listahan.
At pagkatapos ay kami ay pagpunta sa libreng ang kasalukuyang elemento.
>> Kailangan naming siguruhin ang ginagawa namin ito dahil kami Hindi maaaring lamang palayain ang kasalukuyang elemento
at pagkatapos ay subukang i-access ang susunod na pointer dahil sa sandaling napalaya namin ito ng
nagiging di-wastong memorya.
Kaya kailangan namin upang panatilihin sa paligid ng isang pointer upang sa susunod na elemento, pagkatapos ay maaari naming palayain ang
kasalukuyang elemento, at pagkatapos ay maaari naming i-update aming kasalukuyang elemento upang tumuro sa
sa susunod na elemento.
>> Kami na magugustuhan loop habang mayroong mga elemento sa naka-link na listahan.
Gagawin namin ang na para sa lahat ng naka-link na mga listahan sa ang hash talahanayan, at sa sandaling tapos na kami
may iyon, ganap namin deskargado na ang hash talahanayan, at tapos na kami.
Kaya imposibleng para sa unloads sa kailanman bumalik false, at kapag tapos na kami, namin
bumalik lang totoo.