>> ROB BOWDEN: Hei.
Jeg er Rob, og la oss hash denne løsningen ut.
Så her kommer vi til å implementere en generell hash table.
Vi ser at struct node av vår hash tabellen kommer til å se slik ut.
Så det kommer til å ha en char ord matrise av størrelse lengde pluss en.
Ikke glem en siden den maksimale ord i ordlisten er 45
tegn, og da vi kommer til å trenger en ekstra karakter for den
backslash 0.
>> Og da er vår hash table i hvert bøtte kommer til å lagre en
lenket liste av noder.
Vi gjør ikke lineær sondering her.
Og så for å koble til den neste element i bøtta, trenger vi en
struct node * neste.
Så det er hva en node ser ut.
Nå, her er erklæringen av vår hash table.
Det kommer til å ha 16 384 bøtter, men at antall spiller egentlig ingen rolle.
Og til slutt, kommer vi til å ha den global variabel hashtable_size, som
kommer til å starte som 0, og det er kommer til å holde styr på hvor mange ord
var i vår ordbok.
OK.
>> Så la oss ta en titt på lasten.
Så merker at lasten, den returnerer en bool.
Du return true hvis det var vellykket lastet og falsk ellers.
Og det tar en const char * stjerners ordboken, som er ordboken
at vi ønsker å åpne.
Så det er den første tingen vi kommer til å gjøre.
Vi kommer til å FÅpne ordboken for lesing, og vi kommer til å ha
å sørge for at det lyktes så hvis det returneres NULL, så vi gjorde ikke
hell åpne ordboken og vi trenger å returnere false.
>> Men forutsatt at det gjorde med hell åpen, så vi ønsker å lese
ordbok.
Så hold looping til vi finner noen Grunnen til å bryte ut av denne
løkke som vi får se.
Så hold looping, og nå skal vi til malloc en enkelt node.
Og selvfølgelig, må vi feil sjekk igjen så hvis mallocing ikke lykkes
og vi ønsker å losse noen node som vi skjedde med malloc før, lukker
ordbok og return false.
>> Men ignorerer det, forutsatt at vi lyktes, da vi ønsker å bruke fscanf
å lese et eneste ord fra vår ordlisten, i vår node.
Så husk at entry-> Ordet er røye Ordet buffer størrelse lengde pluss
en som vi kommer til å lagre ordet i.
Så fscanf kommer til å returnere en så lang som det var i stand til å lese en
ord fra filen.
>> Hvis enten en feil skjer eller vi nå slutten av filen, vil det ikke
returnere en i hvilket tilfelle dersom det ikke skjer returnere en, vi endelig kommer til å bryte
ut av denne, mens sløyfen.
Så vi ser at når vi har lykkes lese inn et ord i
entry-> ord, så vi kommer til hasj at ordet med vår hash-funksjon.
La oss ta en titt på hash-funksjon.
>> Så du ikke virkelig trenger å forstå dette.
Og faktisk, vi bare trakk dette hash-funksjon fra internett.
Det eneste du trenger å anerkjenne er at dette tar en const char * ord,
så det tar en streng som input og returnere en usignert int som utgang.
Så det er alt en hash-funksjon er, er det tar i en inngang, det gir deg en
indeks inn i nøkkeltabell.
Legg merke til at vi er modding av NUM_BUCKETS så hash-verdi returneres
faktisk er en indeks inn i hash table og indekserer ikke utover
matrisegrensen.
>> Så gitt at hash-funksjon, skal vi til hasj ordet som vi leser
fra ordboken og så skal vi å bruke som har å sette inn
inntreden i hash table.
Nå er hashtabellen hash gjeldende lenket liste i hash table, og
det er meget mulig det er bare NULL.
Vi ønsker å sette vår inntreden på I begynnelsen av dette lenket liste, og så
vi kommer til å ha vår nåværende oppføring peke på hva hash tabellen for øyeblikket
poeng til og vi kommer til å lagre i hash table på hash
den gjeldende oppføringen.
>> Så disse to linjene med hell sette trer ved begynnelsen av
lenket liste ved at indeksen i hash tabellen.
Når vi er ferdig med det, vi vet at vi fant et annet ord i
ordbok og vi øke igjen.
Så vi fortsette med det inntil fscanf endelig returnerer noe ikke en på
hvilket punkt husk at vi trenger å gratis inngang, så her oppe, vi malloced en
oppføring og vi prøvde å lese noe fra ordboken.
Og om vi ikke lykkes lese noe fra ordboken der
tilfelle vi trenger å frigjøre oppføringen som vi aldri faktisk satt i hash table
og til slutt bryte.
>> Når vi bryter ut, trenger vi å se, vel, gjorde vi bryte ut fordi det
ble en feil ved lesing fra filen, eller gjorde vi bryte ut fordi vi nådd
slutten av filen?
Hvis det var en feil, så vi ønsker å return false fordi belastningen ikke
lykkes, og i prosessen, ønsker vi å losse alle ordene som vi leser
inn og lukke ordlistefilen.
Antar vi lykkes, så vi bare fortsatt trenger å lukke ordlisten
fil, og til slutt returnere sant siden vi har lastet inn
ordbok.
Og det er det for last.
>> Så nå sjekke, gitt en ladd hash table, kommer til å se slik ut.
Så sjekk, den returnerer en bool, som kommer til å indikere hvorvidt
gått-i char * ord, om gått-i strengen er i vår ordbok.
Så hvis det er i ordboken, hvis det er i vår hash table, vil vi komme tilbake
sant, og hvis det ikke er det, vi vil returnere false.
Gitt dette gått-i ord, er vi kommer til hasj ordet.
>> Nå, er en viktig ting å gjenkjenne at i lasten, vi visste at alle
ordene skulle skrives med små bokstaver, men her er vi ikke så sikker.
Hvis vi tar en titt på vår hash-funksjon, vår hash-funksjon faktisk
er lowercasing hvert tegn av ordet.
Så uavhengig av kapitalisering av ord, er vår hash-funksjon kommer til å
returnere den samme indeksen for uansett kapitalisering er som det ville ha
returneres for et helt små bokstaver versjon av ordet.
OK.
>> Så det er vår indeks.
Det er hash table for dette ordet.
Nå, dette for loop kommer til over lenkeliste
som var på den indeksen.
Så oppdager vi initialisering oppføring å peke på at indeksen.
Vi kommer til å fortsette mens entry gjør ikke lik NULL, og husk at
oppdatere pekeren i vår lenket liste entry tilsvarer entry-> neste, så har
vår nåværende inngangspunkt til neste element i lenket liste.
OK.
>> Så for hver oppføring i lenket liste, vi kommer til å bruke strcasecmp.
Det er ikke StrCmp fordi en gang, vi ønsker å gjøre ting saken insensitively.
Så vi bruker strcasecmp å sammenligne ordet som ble sendt til denne funksjonen
mot ordet som er i dette innlegget.
Hvis den gir 0, betyr at det ikke var en kamp, ​​og da ønsker vi å
returnere true.
Vi vellykket funnet ord i vår hash table.
>> Hvis det ikke var en kamp, ​​så vi er kommer til å sløyfe igjen og se på
neste oppføring.
Og vi vil fortsette looping mens det er oppføringer i denne lenket liste.
Hva skjer hvis vi bryter ut av dette for løkke?
Det betyr at vi ikke finner en oppføring som matchet dette ordet, i så fall
vi return false for å vise at vår hash table inneholdt ikke dette ordet.
Og det er det for sjekk.
OK.
>> Så la oss ta en titt på størrelse.
Nå er størrelsen kommer til å være ganske enkel siden husker i lasten, for hvert ord
vi fant vi økes en global variable hashtable_size.
Så størrelsen funksjon er rett kommer til å returnere den globale
variabel, og det er det.
>> Nå endelig, trenger vi å losse ordbok når alt er ferdig.
Så hvordan skal vi gjøre det?
Akkurat her er vi looping over alt bøtter med vår hash table.
Så det er NUM_BUCKETS bøtter.
Og for hver lenket liste i vår hash bordet, kommer vi til å sløyfe over
Helheten av lenket liste frigjør hvert element.
Nå må vi være forsiktige, så her er vi har en midlertidig variabel som er
lagring av pekeren til den neste element i lenket liste.
Og så skal vi gratis det aktuelle elementet.
>> Vi må være sikker på at vi gjør dette fordi vi kan ikke bare frigjøre det aktuelle elementet
og deretter prøve å få tilgang til neste pekeren siden når vi frigjort det
minnet blir ugyldig.
Så vi trenger å holde rundt en peker til neste element, så vi kan frigjøre
gjeldende element, og da kan vi oppdatere vår nåværende element for å peke på
det neste element.
>> Vi vil sløyfe mens det er elementer i dette lenket liste.
Vi vil gjøre det for alle lenkede lister i hash tabellen, og når vi er ferdige
med det, har vi helt losset hash tabellen, og vi er ferdige.
Så det er umulig for fjerninger å noensinne return false, og når vi er ferdige, vi
bare returnere true.