>> [Musikgengivelse]
>> ROB BOWDEN: Hej.
Jeg er Rob.
Og lad os denne løsning.
Så her vi kommer til at gennemføre en generel tabel.
Vi ser, at struct node i vores Tabellen kommer til at se sådan ud.
Så det kommer til at have en char ord vifte af størrelse længde + 1.
Glem ikke + 1, da den maksimale ord i ordbogen er 45
tegn.
Og så vil vi brug for en ekstra karakter for backslash nul.
>> Og så er vores Hashtabelsamling i hver spand vil gemme en
forbundet nodeliste.
Vi gør 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.
OK.
Så det er hvad en knude ser ud.
>> Nu her er den erklæring af vores Hashtabelsamling.
Det kommer til at have 16.834 spande.
Men dette tal er faktisk ligegyldigt.
Og endelig, vi kommer til at have den global variabel hashtabelsamling størrelse, hvilket
kommer til at starte som nul.
Og det kommer til at holde styr på hvor mange ord der er i vores ordbog.
>> Så lad os tage et kig på belastning.
Bemærk, at belastning, den returnerer en bool.
Du vender tilbage sandt, hvis det var lykkedes indlæst, og falsk ellers.
Og det tager en const char * ordbog, som er ordbogen
at vi ønsker at åbne.
Så det er den første ting vi kommer til at gøre.
>> Vi kommer til at fopen den ordbog til læsning.
Og vi er nødt til at gøre sikker på, at det lykkedes.
Så hvis det returnerede NULL, så vi ikke gjorde held åbne ordbogen.
Og vi har brug for at vende tilbage 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 sløjfe,
som vi vil se.
Så hold looping.
>> Og nu vil vi allokere en enkelt node.
Og selvfølgelig har vi brug for at lufte kontrollere igen.
Så hvis mallocing ikke lykkes, så 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 post> Ordet er char ord buffer størrelse LENGHTH + 1
at vi kommer til at gemme ord i.
>> Så fscanf vil returnere 1, så længe som det var i stand til at
læse et ord fra filen.
Hvis der sker enten en fejl, eller vi nå enden af ​​filen, det
vil ikke vende tilbage 1..
I så fald er det ikke returnere 1, vi endelig kommer til at bryde ud af
dette, mens løkke.
Så vi kan se, at når vi har med succes læse et ord i
post> ord, så vi skal til 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 denne hash fungere 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 og giver dig en
indekset i Hashtable.
>> Bemærk, at vi moding ved NUM_BUCKETS, så returnerede værdi
faktisk er et indeks i Hashtable og indekserer ikke ud over
grænserne for array.
Så eftersom funktion, vi kommer at hash det ord, vi læser
ordbogen.
Og så vil vi bruge at hash for at indsætte
indrejse i Hashtable.
>> Nu Hashtable hash er den aktuelle forbundet liste i tabellen.
Og det er meget muligt at det er bare NULL.
Vi ønsker at indsætte vores indtræden på det begyndelsen af ​​denne linkede liste.
Og så vil vi have vores nuværende indgang til hvad Hashtable
øjeblikket peger på.
Og så vil vi gemme, i Hashtable på
hash, det aktuelle opslag.
Så disse to linjer held indsætte posten i begyndelsen af
forbundet listen på det pågældende indeks i Hashtable.
>> 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 returneres noget ikke-1 ved
hvilket punkt huske, at vi nødt til at frigøre post.
Så heroppe vi malloced en post.
Og vi har forsøgt at læse noget fra ordbogen.
Og vi havde ikke held læst noget fra ordbogen, i
hvilket tilfælde vi har brug for at frigøre posten at vi faktisk aldrig sat ind i
hashtabelsamling, og endelig at bryde.
>> Når vi bryde ud, vi har brug for at se, ja, vi bryde ud, fordi der
var en fejl ved læsning fra filen?
Eller gjorde vi bryde ud, fordi vi nået til slutningen af ​​filen?
Hvis der var en fejl, vi ønsker at vende tilbage falsk.
Fordi belastning ikke lykkedes.
Og i den proces, vi ønsker at losse alle de ord, som vi læser i, 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 Hashtabelsamling, kommer til at se sådan ud.
Så tjek det returnerer en bool, der er kommer til at angive, om den passerede
i char * ord, uanset om det passerede i strengen er i vores ordbog.
Så hvis det er i ordbogen, hvis det er i vores Hashtabelsamling,
vi vil vende tilbage sandt.
Og hvis det ikke er, vil vi returnere falsk.
>> I betragtning af dette gik i ord, er vi kommer til hash ordet.
Nu er en vigtig ting at erkende, er at vi belastning vidste, at alle
ord, vi kommer til at være lavere sag.
Men her er vi ikke så sikker på.
Hvis vi tager et kig på vores hash funktion, vores hash-funktionen faktisk
er underdelen hver karakter af ordet.
Så uanset kapitalisering af ord, vores hash funktion er afkastet
det samme indeks for uanset kapitalisering er, som det ville have
vendt tilbage til en helt små bogstaver version af ord.
Okay.
Det er vores indeks er i Hashtabelsamling for dette ord.
>> Nu er dette for løkke kommer til gentage 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 post! = NULL.
Og husk at opdatere markøren i vores linkede liste entry = post> næste.
Så har vores nuværende indgang til det næste element i den linkede liste.
>> Så for hver post i den linkede liste, vi kommer til at bruge strcasecmp.
Det er ikke strcomp.
Fordi igen, vi ønsker at gøre tingene tilfælde ufølsomt.
Så vi bruger strcasecmp at sammenligne ord, der blev passeret gennem denne
funktion mod ordet der er i denne post.
Hvis det returneres nul, betyder det, der var en kamp, ​​i hvilket tilfælde vil vi
returnere sandt.
Vi har med held fundet ord i vores hashtabelsamling.
>> 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 Hashtabelsamling ikke indeholder dette ord.
Og det er en check.
>> Så lad os tage et kig på størrelse.
Nu størrelse kommer til at være temmelig simpel.
Siden huske belastning, for hvert ord vi fundet, vi øges en global
variabel Hashtabelsamling størrelse.
Så størrelsen funktionen er bare at returnere global 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 er vi looping løbet alle spande vores bord.
Så der er NUM_BUCKETS spande.
Og for hver linkede liste i vores Hashtabelsamling, vi kommer til løkken over
hele den linkede liste, frigøre hvert element.
>> Nu er vi nødt til at være forsigtig.
Så her har vi en midlertidig variabel der er lagre 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, da når vi har befriet det,
hukommelsen 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 forbundet lister i hashtabelsamling.
Og når vi er færdige med det, vi har helt losset Hashtable, og
vi er færdige.
Så det er umuligt for unload til nogensinde vender tilbage falsk.
Og når vi er færdige, vi bare returnere sandt.
>> Lad os give denne løsning en chance.
Så lad os tage et kig på, hvad vores struct node vil se ud.
Her ser vi, at vi kommer til at have en bool ord og et struct node * børn
beslag alfabet.
Så den første ting du måske være gad vide, hvorfor er ALPHABET
ed defineret som 27?
Nå, huske, at vi får brug for at håndtering apostrof.
Så det kommer til at blive noget af en særligt tilfældet i hele dette program.
>> Nu huske, hvordan en trie rent faktisk virker.
Lad os sige, at vi indeksering ordet "katte". Så fra roden af ​​trie,
vi kommer til at se på børnene array, og vi kommer til at se på
indeks, der svarer til det bogstav C. Så det vil blive indekseret 2.
Så i betragtning af at, der vil give os en ny node.
Og så vil vi arbejde ud fra denne node.
>> Så da knude, vi igen kommer til at se på børn array.
Og vi kommer til at se på indeks nul at svare til A i kat.
Så vi kommer til at gå til denne node, og eftersom knude vi kommer
til at se på i slutningen, det er A svarer T. Og går videre til denne node,
Endelig har vi helt kigget gennem vores ord "kat". Og nu bool
ord er meningen at angive, om dette givne ord er faktisk et ord.
>> Så hvorfor har vi brug for, at særlige tilfælde?
Nå hvad ordet "katastrofe" er i vores ordbog, men den
Ordet "kat" er ikke?
Så og søger at se, hvis ordet "kat" er i vores ordbog, er vi
vil held se gennem indeksene C-A-T i regionen node.
Men det er kun fordi katastrofe sket for at skabe knudepunkter på vej
fra C-A-T, hele vejen til slutningen af ​​ordet.
Så bool ord bruges til at angive, om dette særlige sted
faktisk angiver et ord.
>> Ok.
Så nu, at vi ved, hvad det trie er kommer til at se ud, lad os se på det
indlæse funktion.
Så belastning kommer til at returnere en bool for, om vi med succes eller
forgæves indlæst ordbogen.
Og det kommer til at være ordbogen at vi ønsker at indlæse.
>> Så første ting vi skal gøre er at åbne op at ordbogen for læsning.
Og vi er nødt til at sørge vi ikke svigte.
Så hvis ordbogen ikke var succes åbnet, vil den vende tilbage
null, i hvilket tilfælde vi kommer til at vende tilbage falsk.
Men at antage, at det er lykkedes åbnet, så kan vi rent faktisk læst
gennem ordbogen.
>> Så første ting, vi kommer til at ønsker at gøre, er at vi har denne
global variabel rod.
Nu rod bliver en node *.
Det er toppen af ​​vores trie, at vi er vil blive iteration igennem.
Så den første ting, vi vil ønsker at gøre, er at tildele
hukommelse for vores rod.
Bemærk, at vi bruger den calloc funktion, som er stort set den samme
som allokere funktion, medmindre det er garanteret til at returnere noget, der er
helt nulstillet.
Så hvis vi brugte malloc, ville vi nødt til at gå igennem alle de pejlemærker i vores
node, og sørg for, at de er alle nul.
Så calloc vil gøre det for os.
>> Nu ligesom malloc, er vi nødt til at gøre sikker på, at tildelingen var faktisk
succes.
Hvis det returnerede null, så vi nødt til at lukke eller ordbog
fil og returnere falsk.
Så under forudsætning af, at tildelingen var succes, vi kommer til at bruge en node *
markøren til gentage gennem vores trie.
Så vores rødder aldrig kommer til at ændre, men vi kommer til at bruge markøren til
faktisk gå fra knudepunkt til knudepunkt.
>> Så i denne for-løkke, vi læser gennem ordbogen fil.
Og vi bruger fgetc.
Fgetc kommer til at få fat i en enkelt tegn fra filen.
Vi kommer til at fortsætte med at snuppe tegn, mens vi ikke nå
slutningen af ​​filen.
>> Der er to sager, vi har brug for at håndtere.
Den første, hvis karakter var ikke en ny linje.
Så vi ved, om det var en ny linje, så vi er ved at gå videre til et nyt ord.
Men forudsat det ikke var en ny linje, så her vi ønsker at finde ud af
indeks vil vi indekset i i børn array,
vi kiggede på før.
>> Så som jeg sagde før, er vi nødt til særligt tilfælde apostrof.
Bemærk vi bruger den ternære operatør her.
Så vi kommer til at læse dette som, hvis karakter vi læser i var en
apostrof, så vi kommer til at sætte index = "alfabet" -1, hvilket vil
være indekset 26.
>> Else, hvis det ikke var en apostrof, der vi kommer til at indstille indekset
svarende til c - a.
Så husk tilbage fra tidligere p-sæt, c - a kommer til at give os
alfabetisk position C. Så hvis C er bogstavet A, vil dette
give os indekset nul.
For bogstavet B, vil det give os indeks 1, og så videre.
>> Så det giver os indekset i børn array, vi ønsker.
Nu, hvis dette indeks er i øjeblikket null i børnene, der betyder, at en knude
findes ikke i øjeblikket fra denne vej.
Så vi er nødt til at afsætte en knude til den vej.
Det er, hvad vi vil gøre her.
>> Så vi kommer til igen at bruge calloc funktion, så vi ikke behøver at
nul ud af alle pointere.
Og vi igen nødt til at tjekke at calloc svigtede ikke.
Hvis calloc undlod, så har vi brug at losse alt, lukke vores
ordbog, og returnere falsk.
Så under forudsætning af, at det ikke mislykkes, da dette vil skabe et nyt barn for os.
Og så vil vi gå til det pågældende barn.
Vores markør gentage ned til barnet.
>> Nu, hvis dette ikke var nul at begynde med, så markøren kan bare gentage
ned til det barn uden egentlig skulle afsætte noget.
Dette er tilfældet, når vi først skete tildele ordet "kat". Og
det betyder, når vi går til at afsætte "Katastrofe", behøver vi ikke at skabe
knudepunkter for C-A-T igen.
De findes allerede.
>> Hvad er det andet?
Det er den tilstand, hvor c var backslash n, hvor c var en ny linje.
Det betyder, at vi har succes afsluttet et ord.
Hvad gør vi nu vil gøre, når vi gennemført et ord?
Vi kommer til at bruge dette ord felt inde i vores struct node.
Vi ønsker at sætte det til sand.
Så det tyder på, at dette knudepunkt indikerer en vellykket
ord, en faktiske ord.
>> Sæt nu, at til sand.
Vi ønsker at nulstille vores markøren til punkt til begyndelsen af ​​trie igen.
Og endelig, forøge vores ordbog størrelse, da vi fandt et andet værk.
Så vi kommer til at holde gør det, læsning i tegn for tegn,
konstruere nye noder i vores trie og for hvert ord i ordbogen, indtil
vi endelig nå C! = EOF, hvor tilfælde vi bryde ud af filen.
>> Nu er der to sager under som vi måske har EOF ramt.
Den første er, hvis der var en fejl læsning fra filen.
Så hvis der var en fejl, vi nødt til at gøre det typiske.
Unload alting tæt filen, returnerer falsk.
Hvis man antager, at der ikke var en fejl, at betyder bare, at vi faktisk ramt slutningen af
filen, i hvilket tilfælde vi lukker fil og returnere sandt, da vi
indlæst ordbog ind i vores trie.
>> Så lad os nu tjekke check.
Ser ved check funktionen, ser vi at kontrollen kommer til at returnere en bool.
Den returnerer sand, hvis dette ord, at det er væltes er i vores trie.
Den returnerer falsk ellers.
Så hvordan er du bestemme, om dette ord er i vores trie?
>> Vi ser her, at, ligesom før, vi kommer til at bruge markøren til at gentage
gennem vores trie.
Nu her vi kommer til at gentage over vores hele ordet.
Så iteration over ord, vi er forbi, vi kommer til at bestemme
indeks i børn array, svarer til ordet beslag I. Så dette
kommer til at se ud nøjagtig som belastning, hvor hvis ordet [i]
er en apostrof, så vi vil at bruge index "alfabet" - 1.
Fordi vi besluttet, at der er, hvor vi kommer til at gemme
apostroffer.
>> Else vi kommer til at bruge to lavere ord beslag I. Så husk at ord kan
have vilkårlige bogstaver.
Og så ønsker vi at sikre, at vi er ved hjælp af et lille version af ting.
Og så trække fra, at 'a' til en gang igen give os alfabetisk
position af denne karakter.
Så det kommer til at være vores indeks i børn array.
>> Og nu, hvis dette indeks i børnene array er null, det betyder at vi
ikke længere kan fortsætte iteration ned vores trie.
Hvis det er tilfældet, kan dette ord ikke muligvis være i vores trie.
Da var det, der ville betyde, at der ville være en sti
ned til det ord.
Og du vil aldrig støde null.
Så støder null, vi vender tilbage falsk.
Ordet ikke er i ordbogen.
Hvis det ikke var null, så er vi vil fortsætte iteration.
>> Så vi vil derud markøren til at pege på det særlige
knude på dette indeks.
Vi holde gør det hele hele ordet, under forudsætning af
vi aldrig ramt null.
Det betyder, at vi var i stand til at komme igennem hele ordet og finde
en knude i vores prøve.
Men vi er ikke helt færdig endnu.
>> Vi ønsker ikke bare at returnere sandt.
Vi ønsker at vende tilbage cursoren> ord.
Siden huske igen, er "kat" er ikke i vores ordbog, og "katastrofe"
er, så vil vi med held får vi gennem ordet "kat". Men cursor
ord vil være falsk og ikke sandt.
Så vender vi tilbage markøren ord for at angive hvorvidt denne node er faktisk et ord.
Og det er det for check.
>> Så lad os se størrelse.
Så størrelse kommer til at være temmelig nemt siden, husker i lasten, er vi
forøgelse ordbog størrelse for hvert ord, som vi støder på.
Så størrelse er bare at returnere ordbog størrelse.
Og det er det.
>> Så endelig har vi losse.
Så losse, vi kommer til at bruge en rekursiv funktion til rent faktisk at gøre alt
af arbejdet for os.
Så vores funktion vil blive kaldt på aflæsser.
Hvad aflæsser gøre?
Vi ser her, at aflæsser kommer til at gentage over alle børnene på
dette knudepunkt.
Og hvis barneknudepunktet er ikke null, så vi kommer til at
losse barneknudepunktet.
>> Så det er dig rekursivt losse alle vores børn.
Når vi er sikre på, at alle vores børn er blevet losset, så vi
kan frigøre os selv, så losse os selv.
Dette vil arbejde rekursivt losse hele trie.
Og derefter en gang det er gjort, vi kan bare returnere sandt.
Unload kan ikke fejle.
Vi er bare frigøre ting.
Så når vi er færdig frigør alt, returnere sandt.
Og det er det.
Mit navn er Rob.
Og dette var stave.
>> [Musikgengivelse]