>> ROB BOWDEN: Hæ.
Ég er Rob, og kjötkássa skulum Þessi lausn út.
Svo hér erum við að fara að innleiða almennt kjötkássa borð.
Við sjáum að strúktúr hnút hash okkar Taflan er að fara að líta svona út.
Svo það er að fara að hafa bleikju orð Fylki af stærðinni lengd auk 1.
Ekki gleyma 1 síðan hámarki orð í orðabókinni er 45
stafir, og þá erum við að fara að þarf einn auka staf fyrir hið
sviga 0.
>> Og þá kjötkássa borð okkar í hvert fötu er að fara að geyma
tengda listanum hnúta.
Við erum ekki að línuleg leit hér.
Og svo í röð til að tengja við næsta þáttur í fötu, þurfum við að
struct node * næst.
Svo er það sem hnúturinn lítur út.
Nú, hér er yfirlýsing af kjötkássa borð okkar.
Það er að fara að hafa 16.384 fötunum, en þessi tala skiptir ekki máli.
Og að lokum, við erum að fara að hafa Global breyta hashtable_size, sem
er að fara að byrja á eins og 0, og það er fara að halda utan um hversu mörg orð
voru í orðabók okkar.
Allt í lagi.
>> Þannig að við skulum taka a líta á hleðslu.
Svo taka eftir því að hlaða, það skilar bool.
Þú skilar true ef það var með góðum árangri hlaðinn og ósönn annars.
Og það tekur const char * stjörnu orðabók, sem er orðabók
að við viljum að opna.
Svo er það fyrsta sem við erum að fara að gera.
Við erum að fara að fopen orðabók fyrir lestur, og við erum að fara að hafa
að ganga úr skugga um að það tókst þannig að ef það skilaði NULL, þá erum við did ekki
tókst að opna orðabókina og við þurfum að skila falskur.
>> En miðað við að það gerði með góðum árangri opinn, þá viljum við að lesa
orðabók.
Svo halda lykkja þar til við að finna nokkrar ástæða til að brjótast út úr þessu
lykkja sem við munum sjá.
Svo halda lykkja, og nú erum við að fara að malloc einum hnút.
Og auðvitað þurfum við að villutékk aftur svo ef mallocing ekki tekist
og við viljum að afferma allir hnút sem við gerðist að malloc áður, loka
orðabók og aftur ósatt.
>> En hunsa það, miðað við tekist, þá viljum við nota fscanf
til að lesa eitt orð frá okkar orðabók í hnút okkar.
Svo muna að innganga-> orð er bleikjan orð biðminni stærð lengd auk
sá sem við erum að fara að geyma orð inn
Svo fscanf er að fara að skila 1 svo lengi eins og það var fær til giftusamlega lesa
orð úr skrá.
>> Ef annað hvort villa kemur eða við náum í lok skrá, það vilja ekki
skila 1 í þeim tilvikum ef það virkar ekki skila 1, við erum loksins að fara að brjóta
út úr þessu while lykkju.
Svo við sjáum að þegar við höfum tekist lesa orð í
innganga-> orð, þá erum við að fara að kjötkássa þessi orð með kjötkássa virka okkar.
Láta 'taka a líta á kjötkássa virka.
>> Svo þú þarft ekki raunverulega þörf að skilja þetta.
Og í raun, dró við bara þetta kjötkássa virka af internetinu.
Það eina sem þú þarft að viðurkenna er að þetta tekur const char * orð,
svo það tekur streng sem inntak og aftur óundirritaður INT sem framleiðsla.
Svo er það allt a kjötkássa virka er, er það tekur í inntak, gefur það þér
Vísitala inn kjötkássa töflunni.
Takið eftir að við erum modding við NUM_BUCKETS svo kjötkássa gildi aftur
reyndar er vísitölu í kjötkássa töflunni og ekki vísitölu handan
mörk í fylkinu.
>> Svo í ljósi þess kjötkássa virka, við erum að fara til kjötkássa orð sem við lesum
úr orðabókinni og þá erum við að fara að nota sem hefur að settu
Gildistaka kjötkássa töflunni.
Nú, Hashtable kjötkássa er núverandi tengda listanum í kjötkássa töflunni, og
það er mjög líklegt að er bara NÚLL.
Við viljum setja færslu okkar á upphafi þessa tengda listanum og svo
við erum að fara að hafa núverandi færslu okkar benda á það sem kjötkássa borð eins og er
stig til og þá erum við að fara að geyma í kjötkássa töflunni í hökkun
núverandi færslu.
>> Svo þessar tvær línur tókst setja færslunnar í upphafi að
tengda listanum á vísitölunni í kjötkássa töflunni.
Þegar við erum búin með það, við vitum að við fundum annað orð í
orðabók og við stighækkun aftur.
Svo við höldum að gera það fyrr en fscanf loksins skilar eitthvað sem ekki 1 á
sem lið muna að við þurfum að Aðgangur er ókeypis og svo upp hér, malloced við að
færslu og við reyndum að lesa eitthvað úr orðabókinni.
Og við fengum ekki tekist að lesa eitthvað úr orðabókinni sem
ef við þurfum að losa færsluna sem við aldrei raunverulega setja inn kjötkássa töflunni
og að lokum brjóta.
>> Þegar við brjótast út, þurfum við að sjá, vel, höfum vér brjótast út vegna þess að það
var að villa við lestur úr skránni, eða höfum vér brjótast út vegna þess að við náð
í lok skrárinnar?
Ef það kom upp villa, þá viljum við return false því hlaða gerði ekki
ná árangri, og í því ferli, við viljum afferma öll þau orð sem við lesum
í og loka orðabók skrá.
Miðað við hafi tekist, þá erum við bara enn þurft að loka orðabók
skrá, og að lokum aftur satt þar við höfum tekist hlaðinn á
orðabók.
Og það er það að hlaða.
>> Svo nú athugað, í ljósi hlaðinn kjötkássa borð, er að fara að líta svona út.
Svo stöðva það skilar bool, sem er að fara að kynna hvort
samþykkt í char * orði, hvort framhjá-í band er í orðabók okkar.
Þannig að ef það er í orðabókinni, ef það er í kjötkássa töflunni okkar, munum við aftur
satt, og ef það er ekki, munum við aftur ósatt.
Í ljósi þessa samþykkt í orð, við erum fara að kjötkássa orðið.
>> Nú, mikilvægur hlutur til að viðurkenna er að í álagi, vissum við að allar
orðin voru að fara að vera lágstöfum, en hér erum við ekki svo viss.
Ef við lítum á kjötkássa virka okkar, kjötkássa virka okkar í raun
er lowercasing hvern staf orðsins.
Svo óháð fjármögnun orð, kjötkássa virka okkar er að fara að
skila sömu vísitölu hvað sem fjármögnun er eins og það myndi hafa
aftur fyrir alveg lágstafir útgáfa af orðinu.
Allt í lagi.
>> Svo er það vísitalan okkar.
Það er kjötkássa borð fyrir þessu orði.
Nú, þetta for lykkju er að fara til yfir tengda listanum
sem var á vísitölunni.
Svo taka við erum Frumstilli færslu til að benda á vísitölunni.
Við ætlum að halda áfram á meðan innganga er ekki jöfn NULL, og muna að
uppfæra músina í tengda listanum okkar færsla jafngildir innganga-> næsta, svo hafa
núverandi innganga okkar benda til næsta atriði í tengda listanum.
Allt í lagi.
>> Svo fyrir hverja færslu í tengda listanum, við erum að fara að nota strcasecmp.
Það er ekki strcmp því aftur, við vilja til að gera hlutina mál insensitively.
Svo við notum strcasecmp að bera orð sem var samþykkt við aðgerðina
gegn orði, sem er í þessari færslu.
Ef það skilar 0, sem þýðir að það var leik, en í því tilviki sem við viljum
return true.
Við fundum tókst að orð í kjötkássa töflunni okkar.
>> Ef það var ekki passa, þá erum við fara að lykkja aftur og líta á
Next Entry.
Og við munum halda áfram að lykkja á meðan það eru færslur í þessum tengda listanum.
Hvað gerist ef við brjóta út af þessu fyrir lykkju?
Það þýðir að við vildum ekki fundið færslu sem samþykkt þetta orð, en í því tilviki
við aftur ósatt að benda að okkar kjötkássa borð ekki innihalda þetta orð.
Og það er það að athuga.
Allt í lagi.
>> Þannig að við skulum taka a líta á stærð.
Nú, stærð er að fara að vera frekar einfalt síðan man í álag, fyrir hvert orð
við fundum að við hækkaða alþjóðlegt breytilegum hashtable_size.
Svo er stærð virka bara fara að skila að alþjóðlegum
breytu, og það er það.
>> Nú loksins, þurfum við að afferma orðabók þegar allt er gert.
Svo hvernig eigum við að fara að gera það?
Hérna erum við lykkja yfir alla fötunum kjötkássa borð okkar.
Þannig að það eru NUM_BUCKETS fötunum.
Og fyrir hvert tengda listanum í hash okkar borð, við erum að fara að lykkja yfir á
heild á tengda listanum frjáls hvert frumefni.
Nú þurfum við að fara varlega, svo hér við hafa tímabundna breytu sem er
geyma músina til næsta þáttur í tengda listanum.
Og þá erum við að fara að losa núverandi þáttur.
>> Við þurfum að vera viss um að við gerum þetta því vér getur ekki bara losa Opin ELEMENT
og reyna svo að sjá næsta músina síðan þegar við leysti það á
minni verður öryrki.
Þannig að við þurfum að halda í kring bendi á næsta þátt, þá getum við frjálsari
núverandi þáttur, og þá getum við uppfært Núverandi þáttur okkar til að benda á
næsta þátt.
>> Við munum lykkja en það eru þættir í þessu tengda listanum.
Við munum gera það fyrir alla tengda listum í kjötkássa borð, og þegar við erum búin
við það, höfum við alveg skipað kjötkássa borð, og við erum búin.
Svo það er ómögulegt fyrir yfirgefur við alltaf return false, og þegar við erum búin, við
bara aftur satt.