>> ROB BOWDEN: Hej.
Jag är Rob, och låt oss hash denna lösning ut.
Så här är vi kommer att genomföra en allmän hashtabell.
Vi ser att struct nod i vår hash tabellen kommer att se ut så här.
Så det kommer att ha en char ord matris av storlek längd plus ett.
Glöm inte 1 eftersom den maximala ord i ordlistan är 45
tecken, och sedan ska vi behöver en extra karaktär för
snedstreck 0.
>> Och då vår hashtabell i varje skopan kommer att lagra en
länkad lista av noder.
Vi gör inte linjär sondering här.
Och så för att länka till nästa inslag i hinken, vi behöver en
struct node * nästa.
Så det är vad en nod ser ut.
Nu, här är förklaringen av vår hashtabell.
Det kommer att ha 16,384 hinkar, men den siffran spelar egentligen ingen roll.
Och slutligen, kommer vi att ha globala variabeln hashtable_size, vilket
kommer att börja som 0, och det är kommer att hålla reda på hur många ord
var i vår ordlista.
Okej.
>> Så låt oss ta en titt på last.
Så märker att lasten, den returnerar en bool.
Du return true om det var lyckat laddad och falskt annars.
Och det tar en const char * stjärna lexikon, som är ordboken
att vi vill öppna.
Så det är det första vi ska göra.
Vi ska fopen ordlistan för läsning, och vi kommer att ha
att se till att det lyckades så om det tillbaka NULL, sedan gjorde vi inte
framgångsrikt öppna ordlistan och vi måste returnera false.
>> Men om man antar att den gjorde med framgång öppen, då vill vi att läsa
ordboken.
Så håll looping tills vi hittar några anledning att bryta sig ut ur detta
slinga som vi får se.
Så håll looping, och nu ska vi att malloc en enda nod.
Och naturligtvis måste vi felkontroll igen så om mallocing inte lyckades
och vi vill lasta någon nod som vi hänt med malloc innan, stänger
ordbok och returnera false.
>> Men ignorera det, förutsatt att vi lyckats, då vill vi använda fscanf
att läsa ett enda ord från vår dictionary i vårt nod.
Så kom ihåg att posten-> Ordet är rödingen ordet buffert av storlek längd plus
en som vi kommer att lagra ord i.
Så fscanf kommer att återvända 1 så länge eftersom det kunde framgångsrikt läsa en
ord från filen.
>> Om antingen ett fel inträffar eller vi når slutet på filen, kommer den inte
returnera ett i vilket fall, om den inte gör det tillbaka 1, vi äntligen bryta
ur denna while-slinga.
Så vi ser att när vi har lyckats läsa ett ord i
post-> ord, då vi kommer att hash det ordet med hjälp av vår hashfunktion.
Låt oss ta en titt på hashfunktionen.
>> Så du behöver egentligen inte att förstå detta.
Och faktiskt, bara drog vi detta hash funktion från internet.
Det enda du behöver för att känna igen är att det tar en const char * ord,
så det tar en sträng som indata och returnera en unsigned int som produktion.
Så det är allt en hash-funktion, är det tar på en ingång, det ger dig en
index i hash-tabellen.
Lägg märke till att vi modding av NUM_BUCKETS så det hashvärde return
faktiskt är ett index in i hashtabell och inte index bortom
gränserna för arrayen.
>> Så med tanke på att hashfunktion, vi ska att hash ordet som vi läser
från ordlistan och sedan ska vi att använda som har att sätta in
inträde i hash-tabell.
Nu är hashtable hash den aktuella länkad lista i hash-tabellen, och
det är mycket möjligt det är bara NULL.
Vi vill sätta in vårt inträde på början av denna länkade lista och så
vi kommer att ha vår nuvarande posten peka på vad hash tabellen för tillfället
pekar på och sedan ska vi lagra i hash-tabellen i hash
den aktuella posten.
>> Så dessa två linjer framgångsrikt sätt in posten i början av
länkade listan vid detta index i hash-tabellen.
När vi är klara med det, vi vet att vi hittat ett annat ord i
ordlista och vi öka igen.
Så vi fortsätter att göra det tills fscanf slutligen återvänder något icke en vid
vilken punkt kommer ihåg att vi måste fri entré, så här uppe, malloced vi en
inresa och vi försökte läsa något från ordlistan.
Och vi har inte lyckats läsa något från ordlistan i vilken
fall måste vi befria den post som vi aldrig tas i hash-tabellen
och slutligen brytas.
>> När vi bryter ut, måste vi se, ja, vi bryta ut eftersom det
var ett fel vid läsning från filen, eller vi bryta ut eftersom vi nådde
i slutet av filen?
Om det fanns ett fel, då vill vi att returnera false eftersom lasten inte
lyckas, och i processen, vill vi lasta av alla de ord som vi läser
i och stäng ordlistefilen.
Förutsatt att vi lyckades, då vi bara ändå måste stänga i ordlistan
fil, och slutligen återvänder sant eftersom Vi har laddats i
ordboken.
Och det är det för last.
>> Så nu kontrollera, med tanke på en laddad hash-tabell, kommer att se ut så här.
Så kolla, den returnerar en bool, som kommer att indikera om
passerade-in char * ord, om passerade-in sträng är i vår ordlista.
Så om det är i ordlistan, om det är i vårt hashtabell, kommer vi tillbaka
sant, och om det inte är, vi kommer att returnera false.
Med tanke på detta passerade-in ord, vi är kommer att hash ordet.
>> Nu är en viktig sak att känna igen att i lasten, vi visste att alla
orden skulle bli små bokstäver, men här är vi inte så säker.
Om vi ​​tar en titt på hash-funktion, vår hashfunktion faktiskt
är lowercasing varje tecken av ordet.
Så oavsett kapitalisering av ord, är vår hashfunktion går till
tillbaka samma index för oavsett aktivering är som det skulle ha
returneras för en helt gement version av ordet.
Okej.
>> Så det är vårt index.
Det är hashtabell för detta ord.
Nu, detta för slinga går till över den länkade listan
Det var vid detta index.
Så märker vi att initiera inresa att peka på detta index.
Vi kommer att fortsätta medan posten gör inte lika NULL, och kom ihåg att
uppdaterar pekaren i vår länkad lista posten är lika med posten-> nästa, så har
vår nuvarande ingång till Nästa objekt i länkad lista.
Okej.
>> Så för varje post i den länkade listan, vi kommer att använda strcasecmp.
Det är inte StrCmp eftersom ännu en gång, vi vill göra saker fallet okänsligt.
Så vi använder strcasecmp jämföra ordet som skickades till denna funktion
mot det ord som är i denna post.
Om den returnerar 0, betyder att det inte var en match, i vilket fall vi vill
return true.
Vi fann framgångsrikt ord i vårt hashtabell.
>> Om det fanns inte en match, då är vi gå till loop igen och titta på
nästa post.
Och vi kommer att fortsätta looping medan det är poster i detta länkad lista.
Vad händer om vi bryter ur detta för loop?
Det betyder att vi inte hittade en post som matchas detta ord, i vilket fall
vi returnera false för att ange att vår hashtabell inte innehöll detta ord.
Och det är den för kontroll.
Okej.
>> Så låt oss ta en titt på storlek.
Nu, storlek kommer att vara ganska enkelt sedan minns i lasten, för varje ord
vi hittade vi ökas en global variabel hashtable_size.
Så storleken funktion är bara kommer att returnera det globala
variabel, och det är det.
>> Nu äntligen, måste vi lasta av dictionary när allt är gjort.
Så hur ska vi göra det?
Just här, vi loopa över alla hinkar med vår hashtabell.
Så det finns NUM_BUCKETS hinkar.
Och för varje länkad lista i vår hash bord, vi ska slinga över
helheten av den länkade listan frigöra varje element.
Nu måste vi vara försiktiga, så här är vi har en temporär variabel som är
lagra pekare till nästa elementet i den länkade listan.
Och sedan ska vi gratis det aktuella elementet.
>> Vi måste vara säkra på att vi gör detta eftersom vi kan inte bara befria det aktuella elementet
och sedan försöka komma till nästa pekaren sedan när vi befriade det
minnet blir ogiltig.
Så vi måste hålla runt en pekare till nästa element, då vi kan frigöra
aktuellt element, och då kan vi uppdatera vår nuvarande elementet att peka på
nästa element.
>> Vi ska slinga medan det finns inslag i detta länkad lista.
Vi kommer att göra det för alla länkade listor i hash tabellen, och när vi är klara
med det har vi helt lossas hash tabellen, och vi är klara.
Så det är omöjligt för lastar någonsin returnera false, och när vi är klara, vi
bara return true.