>> SPEAKER 1: 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 Word og en Struct node stjerne
Børn bracketing alfabet.
Så første ting du måske være undrende, hvorfor er alfabet hash defineres som 27?
Nå, huske, at vi får brug for at håndtering apostrof, så
der kommer til at være noget af en speciel tilfældet i dette program.
>> OK, nu huske, hvordan en Trie rent faktisk virker.
Lad os sige, at vi indeksering ordet katte derefter fra roden af ​​vores Trie,
vi kommer til at se på børn array, og vi kommer til at se på
indeks, der svarer til det bogstav C. Så det ville være indeks to.
Så da vil det give os en ny knude, og så vil vi
arbejde fra dette knudepunkt.
>> Så da knude, vi igen kommer til at se på array Children,
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
at se på det indeks, der svarer T. Og går videre til denne node,
Endelig har vi helt kigget gennem vores ord Cat, og nu Bool
Word 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 hvis ordet katastrofe er i vores ordbog, men
Ordet kat er ikke?
Så i at kigge for at se, om ordet kat er i vores ordbog, vi kommer til
held se gennem indeksene C-A-T og nå frem til en node, men det er
kun fordi katastrofe skete med skabe knudepunkter på vejen fra C-A-T alle
vejen til slutningen af ​​ordet.
Så Bool Word bruges angive, om netop dette sted faktisk
angiver et ord.
>> Okay, så nu, at vi ved, hvad en Trie kommer til at se ud, så lad os se
på Load-funktionen.
Så Load kommer til at returnere en Bool for, om vi med succes eller
held loaded ordbog og dette vil være ordbogen
at vi ønsker at indlæse.
Så første ting, vi vil gøre er at åbne op at ordbogen for læsning.
Vi er nødt til at sørge for, vi ikke svigte, så hvis ordbogen ikke var
succes åbnet, vil den vende tilbage Nej, i hvilket tilfælde vi vil
returnere False.
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 stjerne.
Det er toppen af ​​vores Trie, at vi er vil blive iteration igennem.
Så første ting, vi kommer til at ønsker at gøre, er at tildele hukommelse til 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 fordelingen er faktisk
succes.
Hvis det returnerede null, så vi nødt til at lukke vores ordbog
fil og returnere False.
Så under forudsætning af bevillingen blev succes, vi kommer til at bruge en node
stjerne Cursor til at gentage gennem vores Trie.
Så vores rod er aldrig vil ændre sig, men vi kommer til at bruge markør til
faktisk gå fra knudepunkt til knudepunkt.
>> Okay, så i dette For loop, er vi læsning gennem ordbogen fil,
og vi bruger på fgetc.
Så 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, så der er to sager, vi skal håndtere.
Den første, hvis karakter ikke er 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 array Børn som
vi kiggede på før.
>> Så som jeg sagde før, er vi nødt til at særligt tilfælde apostrof.
Bemærk vi bruger den ternære operatør her, så vi kommer til at læse
dette, som om det tegn, vi læser i var en apostrof, så vi kommer til at
sæt indeks svarende til alfabet minus 1, som vil blive indeks 26.
Else, hvis det ikke var en apostrof, så vi kommer til at indstille indekset
lig med C minus en.
Så husk tilbage fra tidligere p-apparater, c minus en kommer til at give os
alfabetisk position c, så hvis c er bogstavet A, vil dette
give os indekset nul.
For bogstavet B, ville 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 array Børn, der betyder, at
en node findes ikke i øjeblikket fra denne sti, så vi er nødt til at afsætte en
node for denne vej.
Det er, hvad vi gør her.
Så vi kommer til, igen bruge calloc funktion, så vi ikke har
til nul ud af alle de pejlemærker, og vi, igen, er nødt til at kontrollere, at calloc
svigtede ikke.
Hvis calloc undlod, så har vi brug at losse alt, lukke vores
ordbog, og returnere False.
>> 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 at 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.
>> OK, så 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.
Nu, hvad vi ønsker at 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 True, så angiver, at dette knudepunkt indikerer en
vellykket ord et virkeligt ord.
Nu indstilles det til True.
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 ord.
>> Okay, så vi kommer til at holde gør at læsning i karakter ved at
karakter, bygge nye knudepunkter i vores Trie og for hvert ord i
ordbog, indtil vi endelig nå c lig EOF, i hvilket tilfælde, vi bryder
ud af filen.
Nu er der to tilfælde 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, er vi nødt til at gøre det typiske losse alt, lukke filen,
returnere False.
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
har indlæst ordbogen ind i vores Trie.
>> Okay, så lad os nu tjek Check.
Ser man på Check-funktionen, ser vi at Check kommer til at returnere en Bool.
Det giver True hvis dette ord, at det er væltes er i vores Trie.
Den returnerer False andet.
>> Så hvordan skal vi afgøre, 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 ordet vi passeret, vi kommer til at bestemme
indekset i array barn, der svarer til word beslag jeg.
Så det kommer til at se ud nøjagtig som Belastning, hvor hvis ordet beslag i er et
apostrof, så vi ønsker at bruge indeks alfabet minus 1, fordi vi bestemt
der er, hvor vi skal hen at gemme apostrof.
>> Else vi kommer til at bruge tolower ord beslag dvs.
Så husk, at ord kan have vilkårlig kapitalisering, og så vi
ønsker at sikre, at vi bruger et lille version af tingene.
Og så trække fra, at små bogstaver en til endnu en gang, give os
alfabetisk position af denne karakter.
Så det kommer til at være vores indeks i array Children.
>> Og nu, hvis dette indeks i Barnet 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 hvis det
var, ville det betyde, at der ville være en sti ned til det ord, og du ville
aldrig støder null.
Så støder null, vi vender tilbage False.
Ordet ikke er i ordbogen.
Hvis det ikke var null, så vi kommer til at fortsætte iteration, så vi vil
til at opdatere vores markøren til at pege på, at bestemt node på dette indeks.
>> Så vi holder gør det hele hele ordet.
Hvis man antager, vi aldrig ramt null, at midler vi var i stand til at komme igennem hele
verden og finde en node i vores Trie, men vi er ikke helt færdig endnu.
Vi ønsker ikke bare at returnere sandt.
Vi ønsker at vende tilbage cursor fejl ord siden, så husk igen, hvis katten er ikke
i vores ordbog og katastrofe er, så vil vi med held komme igennem
Ordet kat, men markøren ord vil være False 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, så husk i Load, er vi
forøgelse ordbog størrelse for hvert ord, som vi støder på.
Så Størrelse er bare at vende tilbage ordbog størrelse, og det er det.
>> Okay, så endelig har vi Unload.
Så Unload, vi kommer til at bruge en rekursiv funktion til rent faktisk at gøre alt
af arbejdet for os, så vores funktion kommer til at hedde aflæsser.
Hvad aflæsser gøre?
Vi ser her, at Unloader kommer til at gentage over alle børnene på
dette knudepunkt, og hvis barnet node ikke er nul, så vi kommer til at
losse barneknudepunktet.
>> Så det kommer til at 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 selv.
Så dette vil rekursivt losse Hele Trie, og derefter en gang det er
gjort, kan vi bare returnere sandt.
Unload kan ikke undgå, men 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 [uhørligt].