>> ROB BOWDEN: Hi.
Olen Rob ja olgem hash seda lahendust.
Nii et siin me läheme rakendada üldine hash tabel.
Me näeme, et struct tipp meie hash tabel läheb välja nägema selline.
Nii et see saab olema char sõna massiivi suurus pikkus pluss 1.
Ärge unustage, 1 kuna maksimaalne sõna sõnastikus on 45
märki ja siis me läheme pead ühe pildi hieroglüüf
kurakriips 0.
>> Ja siis meie hash tabelit iga kopp läheb salvestada
seotud nimekirja sõlmed.
Me ei tee lineaarse katsetamine siin.
Ja nii, et siduda järgmise element ämbrisse, peame
struct tipp * järgmine.
Nii see on, mida sõlme välja näeb.
Nüüd, siin on avaldus meie hash tabel.
See saab olema 16384 kopad, kuid et number ei ole tegelikult küsimus.
Ja lõpuks, me ei kavatse olla globaalse muutuja hashtable_size, mis
läheb alustad kui 0, ja see on kavatse jälgida, kui palju sõnu
olid meie sõnastik.
Hea küll.
>> Võtame pilk koormus.
Nii teate, et koormus, ta naaseb bool.
Sa tagasi true, kui see oli edukalt koormatud ja vale teisiti.
Ja see võtab const char * tärniga sõnastik, mis on sõnastik
et tahame avada.
Nii et esimene asi, me teeme.
Me läheme fopen sõnastik lugemine, ja me ei kavatse olla
veenduda, et see õnnestus, nii et kui see tagastatakse NULL, siis me ei
edukalt avada sõnastik ja me peame tagasi false.
>> Kuid kui eeldada, et ta seda tegi edukalt avatud, siis tahame, et lugeda
sõnastik.
Nii et hoidke silmusega kuni leiame mõned põhjus välja murda see
loop, mida me näeme.
Nii et hoidke silmusega ja nüüd me läheme et malloc ühe sõlme.
Ja loomulikult peame viga näha jälle nii kui mallocing ei õnnestunud
ja me tahame lossida ühtegi sõlme, et me juhtus malloc enne, sulgege
sõnastik ja tagastab false.
>> Aga tähelepanuta asjaolu, eeldades, et me õnnestunud, siis tahame kasutada fscanf
loe sõnagi meie sõnastik meie sõlme.
Seega pidage meeles, et entry-> sõna on char sõna puhverala suurus pikkus pluss
üks, et me läheme hoidke sõna sisse
Nii fscanf läheb tagasi 1 niikaua kui see oli võimalik edukalt lugeda
sõna failist.
>> Kui üks viga juhtub või jõuame Faili lõpus, siis ei
tagastab 1, kus juhul, kui see ei ole tagasi 1, lõpuks ometi oleme murda
sellest samas silmus.
Nii me näeme, et kui meil on edukalt loe sõna võtta
entry-> sõna, siis me läheme hash et sõna meie hash funktsiooni.
Võtame pilk hash funktsiooni.
>> Nii et sa tõesti ei pea sellest aru saama.
Ja tegelikult, me lihtsalt tõmmatakse see räsifunktsiooni internetist.
Ainuke asi, sa pead tunnistama, on et see võtab const char * sõna,
nii see võtab stringi sisendiks ja tagastamise allkirjastamata int toodanguna.
Nii et kõik on hash funktsiooni, on see võtab sisend, see annab sulle
indeks hash tabel.
Pange tähele, et me oleme modding poolt NUM_BUCKETS nii räsi tagasi
tegelikult on indeks hash tabel ja ei indeks üle
piire massiiv.
>> Seega, arvestades, et hash funktsiooni, me hash sõna, et me lugeda
sõnaraamatust ja siis me läheme kasutada, mis on sisestada
sisenemise hash tabel.
Nüüd Hashtable hash on praegune seotud nimekirja hash tabelit ja
On väga võimalik, et on lihtsalt NULL.
Me tahame, et lisada oma sisenemise alguses see seotud nimekirja, ja nii
me lähed on meie praegune kanne juhtida sellele, mida hash tabel praegu
võrra ja siis me lähme salvestada räsi tabeli hash
Praegune kirje.
>> Nii et need kaks rida edukalt sisestada kande alguses
seotud nimekirja sel indeks aastal hash tabel.
Kui me teinud, et me teame et me leidsime teise sõna
sõnastik ja me juurdekasvu uuesti.
Nii me edasi teha kuni fscanf lõpuks tagasi midagi mitte 1 juures
mis punkt meeles pidada, et me peame sissepääs tasuta, nii et siin on meil malloced
sisenemise ja üritasime midagi lugeda sõnaraamatust.
Ja me ei ole suutnud lugeda midagi sõnaraamatust, kus
juhul me peame vabastama kanne, et me tegelikult kunagi pannakse hash tabel
ja lõpuks murda.
>> Kui me välja murda, peame vaatama, noh, me välja murda, sest seal
oli viga lugemisel failist, või me välja murda, sest me jõudsime
Faili lõpus?
Kui seal oli viga, siis me tahame tagasi false sest koormus ei
õnnestub, ja selles protsessis me tahame lossimiseks kõik sõnad, et me loeme
ja sulgege sõnastik faili.
Eeldades, et me ei õnnestu, siis me lihtsalt ikka on vaja sulgeda sõnastik
fail ning lõpuks tagasi true alates oleme edukalt laaditud
sõnastik.
Ja see on see koormus.
>> Nüüd vaadake, arvestades koormatud hash tabel, läheb välja nägema selline.
Nii et vaadata, tagastatakse tõeväärtus, mis läheb, et näidata, kas
edasi-in char * sõna, kas edasi-in string on meie sõnastik.
Nii et kui see on sõnastikus olemas, kui see on meie hash tabel, me tagasi
tõsi, ja kui see ei ole, me tagasi vale.
Arvestades seda edasi-sõnaga, me oleme läheb räsi sõna.
>> Nüüd tähtsam tunnustada on et koormus, me teadsime, et kõik
sõnad, saab olema väiketähti kuid siin me ei ole nii kindel.
Kui me võtame pilk meie räsifunktsiooni, meie räsifunktsiooni tegelikult
on lowercasing iga märk sõna.
Seega sõltumata kapitaliseerimine Ühesõnaga, meie räsifunktsiooni läheb
tagasi sama indeksit mingil kapitalisatsioon on see oleks
tagastatud täielikult väiketähti versioon sõna.
Hea küll.
>> Nii et meie kataloogi.
See on hash tabel selle sõna.
Nüüd on see loop läheb et üle seotud nimekirja
mis oli sel indeks.
Nii märkate oleme algväärtustamisel kanne osutada, et indeks.
Me jätkata samas kirje ei ei võrdu NULL, ja pidage meeles, et
ajakohastamine pointer meie seotud nimekirja kanne võrdub entry-> kõrval, nii on
meie praegune lähtepunkt Järgmine punkt on seotud nimekirja.
Hea küll.
>> Nii iga kande seotud nimekirja, Me ei kavatse kasutada strcasecmp.
See ei strcmp sest taas oleme tahan teha asju, juhul hoolimatult.
Nii et me kasutame strcasecmp võrrelda sõna mis võeti vastu, et see funktsioon
vastu sõna, mis on see kanne.
Kui ta naaseb 0, mis tähendab, et seal oli mängu, mille puhul me tahame
tagasi true.
Oleme edukalt leitud sõna meie hash tabel.
>> Kui ei sobi, siis me oleme läheb loop uuesti ja vaadata
järgmine kanne.
Ja me jätkame silmukoiminen samas on sissekanded Selle seotud nimekirja.
Mis juhtub, kui me murda sellest loop?
See tähendab, et me ei leia kirje, sobitada see sõna, mille puhul
me tagasi false näitab, et meie hash tabel ei sisalda seda sõna.
Ja see on seda kontrollida.
Hea küll.
>> Võtame pilk suurus.
Nüüd suurus saab olema üsna lihtne sest mäletan koormus, iga sõna
leidsime me suurendatakse globaalset muutuja hashtable_size.
Nii suuruse funktsioon on lihtsalt läheb tagasi, et globaalne
muutuja, ja see on kõik.
>> Nüüd lõpuks on meil vaja maha laadida sõnastik Kui kõik on tehtud.
Niisiis, kuidas me saame seda teha?
Siinsamas, me silmusega üle kõik ämbrid meie hash tabel.
Seega on NUM_BUCKETS ämbrid.
Ja iga seotud nimekirja meie hash tabel, me silmus üle
kogu seotud nimekirja vabastades iga element.
Nüüd me peame olema ettevaatlikud, et siin me on ajutine muutuja, mis on
hoidmiseks kursor järgmisele element, mis on seotud nimekirja.
Ja siis me tasuta praegune element.
>> Me peame olema kindlad, et me teeme seda, sest me ei saa lihtsalt vaba praegune element
ja seejärel üritada pääsu järgmise pointer sest kui me vabastas ta
mälu muutub kehtetuks.
Seega on meil vaja, et hoida umbes viit Järgmine element, siis saab tasuta
praegune element, ja siis saame uuendada meie praegune element osutada
Järgmine element.
>> Me loop kui ilmnevad asjaolud, Selles seotud nimekirja.
Me teeme, et kõik, mis on seotud loendite hash tabelis ja kui me oleme valmis
koos, et me oleme täielikult maha laadida hash tabelit ja me oleme valmis.
Nii et see on võimatu, et selle tühjendab kunagi tagasi false, ja kui me teinud oleme
lihtsalt tagasi tõsi.