>> HÖGTALARE 1: Låt oss ge denna lösning ett försök.
Så låt oss ta en titt på vad vår Struct node kommer att se ut.
Här ser vi att vi kommer att ha en Bool Word och en Struct nod stjärna
Barn bracket alfabetet.
Så första du kanske undrar, varför är alfabetet hash definieras som 27?
Tja, kom ihåg att vi kommer att behöva att hantera apostrof, så
det kommer att bli något av en speciell fall under hela programmet.
>> OK, nu, minns hur en Trie fungerar faktiskt.
Låt oss säga att vi indexera ordet katter, sedan från roten av vår Trie,
vi kommer att titta på Barnens samling, och vi kommer att titta på
index som motsvarar den bokstav C. Så det vore index två.
Så med tanke på att, kommer att ge oss en ny nod, och sedan kommer vi
arbeta från den noden.
>> Så med tanke på den noden, vi är återigen kommer att titta på barnen arrayen,
och vi kommer att titta på index noll att motsvara A i katt.
Så då ska vi gå till den noden, och med tanke på att nod, vi ska
att titta på det index som motsvarar till T. Och går vidare till den noden,
Slutligen har vi helt tittat genom våra ord Cat, och nu Bool
Ordet är tänkt att indikera om Detta givet ord är faktiskt ett ord.
>> Så varför behöver vi den där speciella fall?
Tja, tänk om ordet katastrof är i vår ordlista, men
ordet katt är inte?
Så ser för att se om ordet katten är i vår ordlista, kommer vi att
framgångsrikt titta igenom indexen C-A-T och nå en nod, men det är
bara för att katastrofen hände skapa noder på vägen från C-A-T alla
vägen till slutet av ordet.
Så Bool Word används indikerar huruvida denna plats faktiskt
indikerar ett ord.
>> Okej, så nu när vi vet vad en Trie kommer att se ut, låt oss titta
på Load-funktionen.
Så Load kommer att returnera en Bool för om vi lyckas eller
utan framgång laddade ordbok och detta kommer att bli ordlistan
att vi vill läsa.
Så första vi ska göra är att öppna up som lexikon för läsning.
Vi måste se till att vi inte misslyckas, så om ordlistan var inte
öppnat, återgår Nej, i vilket fall vi kommer att
returnera False.
Men om man antar att det framgångsrikt öppnas, då kan vi faktiskt läsa
genom ordboken.
>> Så första vi tänker vill göra är att vi har den här
globala variabeln rot.
Nu, root kommer att bli en nod stjärna.
Det är högst upp på vår Trie att vi är kommer att iterera igenom.
Så första vi kommer att vilja göra är att allokera minne för vår rot.
>> Lägg märke till att vi använder calloc funktion, vilket är i stort sett samma
som Malloc funktion, förutom att det är garanterat att återvända något som är
helt nollställd ut.
Så om vi använde Malloc, skulle vi behöva gå igenom alla tips i vår
nod och se till att de är alla null.
Så calloc kommer att göra det åt oss.
>> Nu, precis som Malloc, vi måste göra Se till att fördelningen är faktiskt
framgångsrik.
Om detta återvände null, då vi måste stänga vår ordlista
filen och returnera False.
Så antar fördelningen var framgångsrik, vi kommer att använda en nod
stjärniga Markör att iterera genom vårt Trie.
Så vår rot kommer aldrig att förändras, men vi kommer att använda markören till
faktiskt gå från nod till nod.
>> Okej, så i detta för en slinga, är vi läsa igenom ordlistan filen,
och vi använder vid fgetc.
Så fgetc kommer att ta en enda tecken från filen.
Vi kommer att fortsätta att ta tag tecken när vi inte når
slutet av filen, så det finns två fall som vi behöver för att hantera.
Den första, om karaktären var inte en ny rad, så vi vet om det var en ny
linje, då är vi på väg att gå vidare till ett nytt ord.
Men om det nu inte var en ny linje, då Här vill vi ta reda på
index vi ska index i i Barn array som
vi tittat på tidigare.
>> Så som jag sa tidigare, vi måste specialfall apostrof.
Lägg märke till att vi använder den ternära operatören här, så vi kommer att läsa
detta som om det tecken vi läser in var en apostrof, då vi kommer att
ställa index lika med alfabetet minus 1, som kommer att vara indexet 26.
Annars, om det inte var en apostrof, då ska vi ställa in index
lika med c minus en.
Så minns tillbaka från tidigare p-apparater, c minus en kommer att ge oss
alfabetisk position c, så om c är bokstaven A, detta kommer
ge oss index noll.
För bokstaven B, skulle det ge oss index 1, och så vidare.
>> Så detta ger oss indexet i Barn array som vi vill ha.
Nu, om detta index är närvarande null Barnen arrayen, innebär att det
finns idag inte en nod från den vägen, så vi måste avsätta en
nod för den vägen.
Det är vad vi gör här.
Så vi kommer att, återigen, använd calloc funktion så att vi inte har
att noll alla pekare, och vi, igen, måste kontrollera att calloc
inte misslyckas.
Om calloc gjorde misslyckas, då behöver vi att lasta av allt, stänga vår
lexikon, och returnera False.
>> Så antar att det inte misslyckas, då detta kommer att skapa ett nytt barn för oss,
och då kommer vi att gå till det barnet.
Vår Markören iterera ner till det barnet.
Nu, om detta inte var noll till att börja med, sedan markören kan bara iterera
ner till barnet utan att behöva fördela någonting.
Detta är fallet när vi först hände att fördela ordet katt, och
det betyder när vi går för att fördela katastrof, vi inte behöver skapa
noder för C-A-T igen.
De finns redan.
>> OK, så vad är det annat?
Detta är det tillstånd där c var snedstreck n, där c var en ny rad.
Det innebär att vi har lyckats avslutade ett ord.
Nu, vad vi vill göra när vi framgångsrikt slutfört ett ord?
Vi kommer att använda detta ord fält insidan av vår Struct nod.
>> Vi vill ställa den till True, så att indikerar att denna nod indikerar en
framgångsrik ord en verklig ord.
Nu ställer det till True.
Vi vill återställa vår markören till punkt till början av Trie igen.
Och slutligen, öka vår ordlista storlek eftersom vi hittat ett annat ord.
>> Okej, så vi kommer att fortsätta göra att läsa in tecknet genom
karaktär, bygga nya noder i vår Trie och för varje ord i
ordbok, tills vi slutligen når c lika EOF, i vilket fall, vi bryter
ur filen.
Nu finns det två ärenden som som vi kanske har drabbat EOF.
Den första är om det fanns ett fel läsa från filen, så om det fanns
ett fel, vi måste göra den typiska lasta av allt, stänga filen,
returnera False.
Förutsatt att det inte var ett misstag, att bara innebär att vi faktiskt träffade i slutet av
filen, i vilket fall, vi stänger filen och returnera sant eftersom vi
lästs in i ordlistan in i vår Trie.
>> Okej, så nu ska vi kolla Check.
Om man tittar på Check-funktionen, ser vi att Check kommer att returnera en Bool.
Den returnerar True om detta ord att det är överförs är i vår Trie.
Den returnerar False annars.
>> Så hur ska vi avgöra om detta ord är i vår Trie?
Vi ser här att, precis som tidigare, vi kommer att använda markören för att iterera
genom vårt Trie.
Nu, här kommer vi att iterera över hela vårt ord.
Så iteration över ordet vi är gått, vi kommer att bestämma
index i Children array som motsvarar ordet fäste i..
Så detta kommer att se ut exakt som Belastning, där om ordet fäste i är ett
apostrof, då vill vi använda index alfabetet minus 1 eftersom vi fastställt
det är där vi ska att lagra apostrofer.
>> Annars ska vi använda tolower Ordet Bracket I.
Så kom ihåg att ord kan ha godtycklig kapitalisering, och så vi
vill se till att vi använder ett gement version av saker.
Och sedan subtrahera från den gemena en att återigen ge oss
alfabetisk ståndpunkt av denna karaktär.
Så det kommer att bli vårt index i barn arrayen.
>> Och nu, om det index till barnen matris är noll, innebär att vi
inte längre kan fortsätta iteration ner vår Trie.
Om så är fallet, detta ord kan inte möjligen vara i vår Trie, eftersom om det
var, skulle det innebära att det skulle finnas en stig ner till det ordet, och du skulle
aldrig stöter på null.
Så möter null, återvänder vi False.
Ordet finns inte i ordlistan.
Om det inte var noll, då vi kommer att fortsätta iteration, så vi ska
att uppdatera vår markören för att peka på att speciell nod vid detta index.
>> Så vi fortsätter att göra det hela hela ordet.
Förutsatt att vi aldrig träffade noll, det betyder vi kunde få igenom hela
världen och hitta en nod i vår Trie, men vi är inte riktigt klar ännu.
Vi vill inte bara return true.
Vi vill återvända markören fel ord sedan, minns igen, om katten inte är
i vår ordlista och katastrof är, då kommer vi lyckas få igenom
ordet katt, men markören ord blir False och inte sant.
Så vi återvänder markören ord för att indikera huruvida denna nod är faktiskt ett ord,
och det är den för kontroll.
>> Så låt oss kolla storlek.
Så storlek kommer att bli ganska lätt sedan, minns i Load, vi är
uppräkning ordbok storlek för varje ord som vi stöter på.
Så storlek är bara att återvända dictionary storlek, och det är det.
>> Okej, så slutligen har vi Unload.
Så Unload, kommer vi att använda en rekursiv funktion för att verkligen göra allt
av arbetet åt oss, så att vår funktion kommer att kallas Avlastnings.
Vad Avlastnings göra?
Vi ser här att Avlastnings kommer att iterera över alla barnen på
just denna nod, och om barnet nod inte är null, så ska vi
lossa barnet oden.
>> Så detta kommer att rekursivt lasta alla våra barn.
När vi är säkra på att alla våra barn har lossats, då vi
kan frigöra oss, så lasta av oss själva.
Så det här kommer rekursivt lasta av Hela Trie, och sedan en gång det är
gjort, kan vi bara return true.
Lasta kan inte misslyckas, vi är bara frigöra saker.
Så när vi är klara frigöra allt, return true.
Och det är det.
Mitt namn är Rob, och detta var [OHÖRBAR].