>> Spreker 1: Kom ons gee hierdie oplossing 'n drie.
So laat ons 'n blik op wat ons Struct knoop sal lyk.
Hier sien ons wat ons gaan hê om 'n Bool Woord en 'n struct knoop ster
Kinders in hakies alfabet.
So die eerste ding wat jy dalk wonder, Hoekom is alfabet hash gedefinieer as 27?
Wel, onthou dat ons gaan nodig word die hantering van die toespraak, so
wat gaan om 'n bietjie te wees van 'n spesiale geval in hierdie program.
>> OK, nou, onthou hoe 'n Trie eintlik werk.
Kom ons sê ons kruip die woord katte, dan van die wortel van ons Trie,
ons gaan om te kyk na die kinders skikking, en ons gaan om te kyk na die
indeks wat ooreenstem met die letter C. So wat sou indeks twee.
So gegee dat, wat ons sal gee 'n nuwe knoop, en dan sal ons
werk van daardie knoop.
>> So gegee dat knoop, ons is weer gaan om te kyk na die kinders skikking,
en ons gaan om te kyk na indeks nul ooreenstem met die A in kat.
So dan gaan ons na daardie knoop, en gegee dat knoop, gaan ons
om te kyk na die indeks wat ooreenstem T. en beweeg na die knoop,
Ten slotte, ons het heeltemal gelyk deur ons woord Cat, en nou Bool
Woord is veronderstel om aan te dui of hierdie gegewe woord is eintlik 'n woord.
>> So hoekom moet ons daardie spesiale geval?
Wel, wat as die woord ramp is in ons woordeboek, maar
die woord kat is nie?
So in soek om te sien of die woord kat is in ons woordeboek, gaan ons
suksesvol te kyk deur die indekse C-A-T en bereik 'n knoop, maar dit is
net omdat katastrofe gebeur skep nodes op die pad van C-A-T al
die pad na die einde van die woord.
So Bool woord gebruik word aan te dui of hierdie spesifieke plek eintlik
dui op 'n woord.
>> Alle reg, nou dat ons weet wat 'n Trie gaan lyk, laat ons kyk
by die las funksie.
So vrag is gaan 'n Bool om terug te keer Want as ons suksesvol of
onsuksesvol gelaai woordeboek Dit gaan die woordeboek te wees
wat ons wil om te laai.
So die eerste ding wat ons gaan doen is oop up dat woordeboek vir lees.
Ons moet seker maak ons ​​het nie versuim om, So as die woordeboek was nie
suksesvol oopgemaak word, sal dit terugkeer Nee, in welke geval ons gaan
terug Vals.
Maar die veronderstelling dat dit suksesvol oopgemaak het, dan kan ons eintlik lees
deur die woordeboek.
>> So die eerste ding wat ons gaan wil doen, is ons hierdie
globale veranderlike wortel.
Nou, is die wortel gaan 'n knoop-ster te wees.
Dit is die top van ons Trie dat ons gaan word iterating deur.
So die eerste ding wat ons gaan om te wil doen, is om toeken geheue vir ons wortel.
>> Let daarop dat ons met behulp van die Calloc funksie, wat is basies dieselfde
as die malloc funksie nie, behalwe dit is gewaarborg iets wat om terug te keer
heeltemal zeroed uit.
So as ons gebruik malloc, sou ons nodig het om te gaan deur al die verwysings in ons
knoop en maak seker dat hulle is almal null.
So Calloc sal dit doen vir ons.
>> Nou, net soos malloc, het ons nodig het om te maak seker te maak dat die toekenning is eintlik
suksesvol.
As dit teruggekeer null, dan het ons moet ons woordeboek te sluit
lêer en terug Vals.
So die aanvaarding van die toekenning is suksesvol is, gaan ons 'n knoop te gebruik
ster wyser te Itereer deur ons Trie.
So ons wortel gaan nooit verander nie, maar ons gaan wyser te gebruik om te
eintlik gaan van knoop tot knoop.
>> Alle reg, so in hierdie For-lus, ons is lees deur die woordeboek lêer,
en ons gebruik by fgetc.
So fgetc gaan 'n enkele te gryp karakter van die lêer.
Ons gaan om voort te gaan gryp karakters terwyl ons bereik nie die
einde van die lêer, sodat daar twee gevalle het ons nodig het om te hanteer.
Die eerste, as die karakter was nie 'n nuwe lyn, sodat ons weet of dit 'n nuwe
lyn, dan is ons oor te beweeg na 'n nuwe woord.
Maar die veronderstelling dat dit was nie 'n nuwe lyn, dan Hier wil ons om uit te vind die
indeks gaan ons na die indeks in in die kinders skikking wat
Ons kyk na voor.
>> Dus, net soos ek gesê het, moet ons spesiale geval die toespraak.
Let ons die gebruik van die drieledige operateur hier, so ons gaan om te lees
hierdie asof die karakter wat ons gelees het, was 'n toespraak, dan gaan ons
stel indeks gelyk aan alfabet minus 1, wat sal die indeks 26 wees.
Anders, as dit nie was 'n toespraak, dan gaan ons die indeks op te stel
gelyk aan c minus a.
So onthou terug van die vorige p stelle, c minus 'n gaan ons die te gee
alfabetiese posisie van c, so as c is die letter A, word dit
gee ons indeks nul.
Vir die letter B, sou dit gee ons die indeks 1, en so aan.
>> So dit gee ons die indeks in die Kinders skikking wat ons wil hê.
Nou, as die indeks is tans nul in die kinders skikking, wat beteken dat
'n knoop op die oomblik nie bestaan ​​uit dat die pad, sodat ons nodig het om te wys 'n
knoop vir die pad.
Dit is wat ons hier doen.
So gaan ons weer, gebruik die Calloc funksie sodat ons nie
nul uit al die wysers, en ons, weer, moet daardie Calloc om seker te maak
het nie misluk nie.
As Calloc het misluk, dan moet ons om alles te los, sluit ons
woordeboek, en terug Vals.
>> So die veronderstelling dat dit nie slaag nie, dan dit sal 'n nuwe kind vir ons skep,
en dan sal ons na daardie kind.
Ons wyser sal Itereer af aan daardie kind.
Nou, as dit nie nul te begin, dan die wyser kan net Itereer
af aan daardie kind sonder om werklik om iets te ken.
Dit is die geval waar ons die eerste keer gebeur het die woord kat te ken, en
Dit beteken dat wanneer ons gaan te ken ramp, het ons nie nodig om te skep
nodes vir C-A-T weer.
Hulle het reeds bestaan.
>> OK, so wat is hierdie Anders?
Dit is die toestand waar c was backslash n, waar c 'n nuwe lyn.
Dit beteken dat ons suksesvol voltooi 'n woord.
Nou, wat wil ons doen wanneer ons 'n woord suksesvol voltooi?
Ons gaan hierdie woord veld te gebruik binnekant van ons struct knoop.
>> Ons wil dit waar, sodat dui aan dat hierdie knoop dui op 'n
suksesvolle woord 'n werklike woord.
Nou, stel wat aan True.
Ons wil ons wyser te herstel na punt aan die begin van die Trie weer.
En uiteindelik, inkrementeer ons woordeboek grootte, aangesien ons het nog 'n woord.
>> Alle reg, so ons gaan aanhou doen dat lees in karakter deur
karakter, die bou van nuwe nodes in ons Trie en vir elke woord in die
woordeboek, totdat ons uiteindelik bereik c gelyk EOF, in watter geval, ons breek
uit die lêer.
Nou is daar twee gevalle onder wat ons kan EOF getref het.
Die eerste is as daar 'n fout die lees van die lêer, sodat as daar
'n fout, ons moet die tipiese te doen los alles, maak die lêer,
terug Vals.
Veronderstelling daar was nie 'n fout, wat beteken net ons eintlik getref die einde van
die lêer, in watter geval, ons sluit die lêer en terugkeer waar nie, aangesien ons
die woordeboek suksesvol gelaai in ons Trie.
>> Alle reg, so laat ons nou check Check.
Kyk na die Check funksie, sien ons daardie tjek gaan 'n Bool om terug te keer.
Dit gee Waar indien hierdie woord wat dit is oorgedra is in ons Trie.
Dit gee Vals anders.
>> So hoe gaan ons om te bepaal of hierdie woord is in ons Trie?
Ons sien hier dat, net soos tevore, ons gaan wyser te gebruik om Itereer
deur ons Trie.
Nou, hier gaan ons te Itereer oor ons hele woord.
So iterating oor die woord wat ons is geslaag het, gaan ons om te bepaal die
indeks vir die kinders skikking wat ooreenstem met woord bracket i.
So dit gaan lyk presies soos Vrag, waar as woord bracket ek is 'n
toespraak, dan wil ons indeks te gebruik alfabet minus 1 omdat ons bepaal
dit is waar ons gaan apostrofes te stoor.
>> Anders gaan ons tolower te gebruik woord bracket i.
So onthou dat die woord kan arbitrêre kapitalisasie, en so het ons
wil seker maak dat ons gebruik maak 'n klein weergawe van die dinge.
En dan trek uit daardie klein 'n te weer, gee ons die
alfabetiese posisie van die karakter.
So wat gaan ons indeks te wees in die kinders skikking.
>> En nou, as die indeks vir die kinders skikking is nul, wat beteken dat ons
kan nie meer voortgaan iterating down ons Trie.
As dit die geval is, is hierdie woord kan nie moontlik wees in ons Trie, want as dit
was, sou dit beteken dat daar 'n wees pad af na die woord, en jy sou
nooit ontmoet null.
So stuit nul, keer ons terug Vals.
Die woord is nie in die woordeboek.
As dit nie was nul, dan gaan ons voortgaan iterating, so ons gaan
ons wyser te werk aan te dui dat spesifieke knoop op die indeks.
>> So ons hou doen wat dwarsdeur die hele woord.
Veronderstelling ons nooit getref nul, wat beteken dat ons in staat was om te kry deur die hele
wêreld en vind 'n knoop in ons Trie, maar ons is nog nie heeltemal klaar nie.
Ons wil nie net terug Waar.
Ons wil wyser fout woord om terug te keer sedert, onthou weer, as die kat is nie
in ons woordeboek en ramp is, dan sal ons suksesvol kry deur
die woord kat, maar wyser woord sal Vals en nie waar wees nie.
So ons terugkeer wyser woord aan te dui of hierdie knoop is eintlik 'n woord,
en dit is dit vir check.
>> So laat ons kyk na grootte.
So grootte gaan wees redelik maklik sedert, onthou in Vrag, ons is
die verhoog woordeboek grootte vir elke woord wat ons teëkom.
So grootte is net gaan om terug te keer woordeboek grootte, en dit is dit.
>> Alle reg, sodat laastens, ons het los.
So los, ons gaan gebruik om 'n rekursiewe funksie te eintlik al
van die werk vir ons, sodat ons funksie gaan genoem word losser.
Wat is losser gaan doen?
Ons sien hier dat losser gaan Itereer oor al die kinders wat by
hierdie spesifieke knoop, en indien die kind knoop is nie nul is, dan gaan ons
los die kind knoop.
>> So dit gaan rekursief los almal van ons kinders.
Sodra ons is seker dat al ons kinders is afgelaai het, dan het ons
kan bevry onsself, so los onsself.
So dit sal rekursief los die hele Trie, en dan weer dit is
gedoen het, kan ons net terug Waar.
Los nie kan misluk nie, ons is net bevry dinge.
So wanneer ons klaar is bevry alles terug Waar.
En dit is dit.
My naam is Rob, en hierdie was [onhoorbaar].