>> ROB BOWDEN: Hej.
Jeg er Rob, og lad os hash denne løsning.
Så her vi kommer til at gennemføre en generel hash tabel.
Vi ser, at struct node i vores hash Tabellen kommer til at se sådan ud.
Så det kommer til at have en char ord vifte af størrelse længde plus 1.
Glem ikke 1, da den maksimale ord i ordbogen er 45
tegn, og så vil vi har brug for en ekstra karakter for
backslash 0.
>> Og så er vores hash tabel i hver spand vil gemme en
forbundet nodeliste.
Vi laver ikke lineær probing her.
Og så for at linke til den næste element i spanden, vi har brug for en
struct node * næste.
Så det er hvad en knude ser ud.
Nu, her er den erklæring vores hash tabellen.
Det kommer til at have 16.384 spande, men dette nummer er faktisk ligegyldigt.
Og endelig, vi kommer til at have den global variabel hashtable_size, som
kommer til at starte som 0, og det er kommer til at holde styr på, hvor mange ord
var i vores ordbog.
Ok.
>> Så lad os tage et kig på belastning.
Så bemærke, at last, den returnerer en bool.
Du vender tilbage sandt, hvis det var lykkedes lastet og falsk ellers.
Og det tager en const char * stjerne ordbog, som ordbogen
at vi ønsker at åbne.
Så det er den første ting vi kommer til at gøre.
Vi kommer til at fopen ordbogen for læsning, og vi er nødt til
at sørge for, at det lykkedes så hvis det returnerede NULL, så vi ikke gjorde
held åbne ordbogen og vi er nødt til at returnere falsk.
>> Men det antages, at den gjorde med succes åben, så vi ønsker at læse
ordbogen.
Så hold looping indtil vi finder nogle grund til at bryde ud af denne
løkke, som vi vil se.
Så holde looping, og nu skal vi at allokere en enkelt node.
Og selvfølgelig er vi nødt til fejl kontrol igen, så hvis mallocing ikke lykkedes
og vi ønsker at losse enhver knude, som vi sket med malloc før, lukke
ordbog og returnere falsk.
>> Men at ignorere det, antager vi lykkedes, så vi ønsker at bruge fscanf
at læse et enkelt ord fra vores ordbogen til vores knude.
Så husk, at entry-> Ordet er char ord buffer størrelse længde plus
en, som vi kommer til at gemme ord i.
Så fscanf kommer til at returnere 1, så længe som det var i stand til at læse en
ord fra filen.
>> Hvis enten en fejl sker, eller vi nå slutningen af ​​filen, vil det ikke
returnere 1, i hvilket tilfælde, hvis den ikke gør det returnere 1, vi endelig kommer til at bryde
ud af dette, mens løkken.
Så vi kan se, at når vi har med succes læse et ord i
entry-> ord, så vi kommer til at hash at ordet ved hjælp af vores hash funktion.
Lad os tage et kig på hash-funktionen.
>> Så du behøver ikke virkelig har brug for at forstå dette.
Og faktisk, vi bare trak dette hash funktion fra internettet.
Det eneste, du skal erkende, er at det tager en const char * ord,
så det tager en streng som input og returnere en usigneret int som output.
Så det hele er en hash-funktion er, er det tager i et input, det giver dig en
indekset i hash tabellen.
Bemærk, at vi er modding af NUM_BUCKETS så den hash værdi, der returneres
faktisk er et indeks i hash tabellen og indekserer ikke ud over
grænserne for array.
>> Så da hash funktion, vi kommer at hash det ord, vi læser
fra ordbogen og så vil vi at bruge, der har at indsætte
indrejse i hash tabellen.
Nu Hashtable hash er den aktuelle linkede liste i hash tabellen, og
det er meget muligt, at er bare NULL.
Vi ønsker at indsætte vores indtræden på det begyndelsen af ​​denne linkede liste, og så
vi vil have vores aktuelle post pege på, hvad hash tabellen i øjeblikket
point til og så vi kommer til at gemme i hash tabellen på hash
den aktuelle indtastning.
>> Så disse to linjer held indsætte posten i begyndelsen af
forbundet listen på det pågældende indeks i hash tabellen.
Når vi er færdig med det, vi kender at vi fandt et andet ord i
ordbog og vi tilvækst igen.
Så vi holde gør, at indtil fscanf Endelig returnerer noget ikke 1 ved
hvilket punkt huske, at vi er nødt til gratis adgang, så op her, vi malloced en
indrejse og vi forsøgte at læse noget fra ordbogen.
Og vi havde ikke held læst noget fra ordbogen, hvor
tilfælde har vi brug for at frigøre den post, vi faktisk aldrig sat i hash tabellen
og endelig at bryde.
>> Når vi bryder ud, er vi nødt til at se, ja, vi bryde ud, fordi der
var en fejl ved læsning fra filen, eller vi bryder ud, fordi vi nåede
slutningen af ​​fil?
Hvis der var en fejl, da vi ønsker at return false fordi belastningen ikke
lykkes, og i den proces, vi ønsker at losse alle de ord, som vi læser
ind og lukke ordbogen fil.
Hvis man antager, vi lykkes, så vi bare stadig nødt til at lukke ordbogen
fil, og endelig returnere sandt, da vi har indlæst
ordbogen.
Og det er det for belastning.
>> Så nu kontrollere, givet en ladt hash tabel, kommer til at se sådan ud.
Så tjek det returnerer en bool, der kommer til at angive, om
passerede-in char * ord, hvorvidt den passerede-i streng er i vores ordbog.
Så hvis det er i ordbogen, hvis det er i vores hash tabel, vi vil vende tilbage
sandt, og hvis det ikke er, vi vil vende tilbage falsk.
I betragtning af denne passerede-i ord, er vi kommer til hash ordet.
>> Nu, en vigtig ting at erkende, er at i lasten, vidste vi, at alle
de ord, skulle være lavere fald men her er vi ikke så sikker.
Hvis vi tager et kig på vores hash funktion, vores hash-funktionen faktisk
er lowercasing hver karakter af ordet.
Så uanset kapitalisering af ord, er vores hash funktion, der går til
returnere det samme indeks for uanset kapitalisering er som det ville have
vendt tilbage til en helt små bogstaver version af ord.
Ok.
>> Så det er vores indeks.
Det er hash tabellen for dette ord.
Nu, dette for-løkke går til over den linkede liste
der var på dette indeks.
Så opdager vi initialiseres indgang at pege på dette indeks.
Vi kommer til at fortsætte, mens indgang gør ikke lig NULL, og husk, at
opdatering af markøren i vores linkede liste entry lig entry-> næste, så har
vores nuværende indgang til Næste punkt på linkede liste.
Ok.
>> Så for hver post i den linkede liste, vi kommer til at bruge strcasecmp.
Det er ikke strcmp fordi vi endnu en gang ønsker at gøre tingene tilfælde ufølsomt.
Så vi bruger strcasecmp at sammenligne ordet som blev overført til denne funktion
imod det ord, er i denne post.
Hvis den returnerer 0, som betyder, at der var en kamp, ​​i hvilket tilfælde vil vi
returnere sandt.
Vi har med held fundet ord i vores hash tabel.
>> Hvis der ikke var en kamp, ​​så er vi gå til loop igen og se på
næste post.
Og vi vil fortsætte looping mens der er poster i denne linkede liste.
Hvad sker der, hvis vi bryder ud af denne for-løkke?
Det betyder, at vi ikke finde en post, der matches dette ord, i hvilket tilfælde
vi vender tilbage falsk for at angive, at vores hash tabel ikke indeholder dette ord.
Og det er det for check.
Ok.
>> Så lad os tage et kig på størrelse.
Nu størrelse kommer til at være temmelig simpel da huske i belastning, for hvert ord
vi fandt vi øges en global variabel hashtable_size.
Så størrelsen funktion er kun vil vende tilbage, at den globale
variabel, og det er det.
>> Nu endelig er vi nødt til at losse ordbog når alt er gjort.
Så hvordan skal vi gøre det?
Lige her, vi springer over alle spande af vores hash tabel.
Så der er NUM_BUCKETS spande.
Og for hver linkede liste i vores hash tabel, vi kommer til at sløjfe over
hele den linkede liste frigøre hvert element.
Nu er vi nødt til at være forsigtig, så her vi have en midlertidig variabel, der er
lagring markøren til den næste element i den linkede liste.
Og så vil vi fri det aktuelle element.
>> Vi er nødt til at være sikker på, vi gør dette, da vi kan ikke bare frigøre det aktuelle element
og derefter prøve at gå til det næste pointer siden når vi befriede det
hukommelse bliver ugyldig.
Så vi nødt til at holde omkring en pegepind til det næste element, så vi kan frigøre
aktuelle element, og så vi kan opdatere vores aktuelle element til at pege på
det næste element.
>> Vi vil sløjfe, mens der er elementer i denne linkede liste.
Vi vil gøre det for alle sammenkædede lister hash tabellen, og når vi er færdig
med det, har vi helt losses hash tabellen, og vi er færdige.
Så det er umuligt for losser til nogensinde returnere falsk, og når vi er færdige, vi
bare returnere sandt.