>> SPEAKER 1: Dosim Šis risinājums mēģināt.
Tātad, pieņemsim apskatīt to, kas mūsu Struktūrai mezgls izskatīsies.
Šeit mēs redzam, mēs esam nāksies Bool Word un Struct mezglu zvaigzne
Bērni Bracket alfabētu.
Tātad, pirmā lieta, jūs varētu būt jautājums, kāpēc alfabēts hash definēta kā 27?
Nu, atcerieties, ka mēs ejam uz nepieciešamību kas apstrādes apostrofu, lai
, kas būs nedaudz īpašs lieta visā šajā programmā.
>> Labi, tagad atceros, kā Trie faktiski darbojas.
Pieņemsim, ka mēs esam indeksēšanas vārdu kaķi, tad no saknes mūsu Trie,
mēs ejam apskatīt Bērnu masīvs, un mēs ejam apskatīt
indekss, kas atbilst vēstules C. Lai būtu indekss divi.
Tātad, ņemot vērā, ka tas dos mums jaunu mezglu, un tad mēs
strādā no šī mezgla.
>> Tāpēc, ka mezglā, mēs atkal esam skatīsies uz Bērnu masīvs,
un mēs ejam apskatīt indeksu nulles lai tā atbilstu A kaķu.
Tātad, tad mēs ejam, lai dotos uz šo mezglu, un ņemot vērā, ka mezglā, mēs ejam
aplūkot indekss, kas atbilst ar T. un pārvietojas uz šo mezglu,
Visbeidzot, mēs esam pilnīgi izskatījās caur mūsu vārdu Cat, un tagad Bool
Vārds ir paredzēts, lai norādītu, vai tas dots vārds ir faktiski vārdu.
>> Tātad, kāpēc mums ir nepieciešams, ka īpaša gadījumā?
Nu, ko tad, ja vārds katastrofa ir mūsu vārdnīcā, bet
vārds kaķis ir ne?
Tāpēc vēlas redzēt, ja vārds kaķis mūsu vārdnīcā, mēs ejam
veiksmīgi meklēt, izmantojot indeksu C-T un sasniegt mezglu, bet tas ir
tikai tāpēc, ka katastrofa notika izveidot mezglu ceļā no C-A-T all
veids, beigās vārdu.
Tāpēc Bool Word lieto norādīt, vai šī konkrētā vietā faktiski
norāda vārdu.
>> Labi, tāpēc tagad, ka mēs zinām, kas Trie gatavojas izskatās, aplūkosim
pie slodzes funkciju.
Tāpēc Slodze gatavojas atgriezties bool par to, vai mēs veiksmīgi vai
neveiksmīgi piekrauts vārdnīcu un tas būs vārdnīca
ka mēs gribam, lai slodze.
Tātad pirmā lieta, ko mēs gatavojamies darīt, ir atvērts līdz šim vārdnīcā lasījumā.
Mums ir jāpārliecinās, mums nav neizdoties, tāpēc, ja vārdnīcā nav
veiksmīgi atvērts, tas atgriezīsies Nē, tādā gadījumā mēs spēsim
atgriešanās False.
Bet, pieņemot, ka tā veiksmīgi atvērts, tad mēs faktiski var izlasīt
izmantojot vārdnīcu.
>> Tātad pirmā lieta, ko mēs gatavojamies vēlaties darīt, ir, mums ir šis
globālo mainīgo saknes.
Tagad, saknes būs mezglā zvaigzne.
Tā ir top mūsu Trie, ka mēs esam būs atkārtojot cauri.
Tātad pirmā lieta, ko mēs esam gatavojas vēlaties darīt, ir piešķirt atmiņu mūsu saknes.
>> Ievērojiet, ka mēs esam, izmantojot Calloc funkcija, kas būtībā ir tas pats
jo malloc funkciju, izņemot tā garantēta, lai atgrieztos kaut ko, kas ir
pilnīgi nulli out.
Tātad, ja mēs izmantojām malloc, mums būtu nepieciešams, lai iet cauri visiem norādes mūsu
mezglu un pārliecinieties, ka viņi visi null.
Tāpēc Calloc būs darīt, ka mums.
>> Tagad, tāpat kā malloc, mums ir nepieciešams veikt pārliecināts, ka sadalījums ir faktiski
veiksmīga.
Ja tas atgriezās null, tad mēs nepieciešams slēgt mūsu vārdnīca
failu un atgriešanās False.
Tātad, pieņemot, ka piešķiršanu tika veiksmīga, mēs ejam, lai izmantotu mezglu
star kursoru atkārtot caur mūsu Trie.
Tātad mūsu saknes nekad mainīsies, bet mēs esam gatavojas izmantot kursoru
tiešām iet no mezgla uz mezglu.
>> Labi, tāpēc šis cilpas, mēs esam iepazīšanās ar vārdnīcas failu,
un mēs esam izmantojot pie fgetc.
Tāpēc fgetc gatavojas sagrābt vienotu rakstzīmi no lietas materiāliem.
Mēs turpināsim satveršanas rakstzīmes, kamēr mēs nenonāk
beigām failu, tāpēc ir abas lietas mums ir nepieciešams rīkoties.
Pirmais, ja raksturs nebija Jaunā līnija, tāpēc mēs zinām, ja tas bija jauns
līniju, tad mēs esam par to, lai pāriet uz jaunu vārdu.
Bet pieņemot, ka tas nebija jaunu līniju, tad šeit, mēs gribam, lai noskaidrotu
indekss mēs ejam indeksēt ar bērniem masīvā, ka
mēs paskatījās agrāk.
>> Tā kā es teicu iepriekš, mums ir nepieciešams Īpašs gadījums Apostrofs.
Ievērojiet, mēs izmantot trīskāršo operators šeit, tāpēc mēs ejam, lai lasītu
Tas it kā varonis lasām bija Apostrofs, tad mēs ejam uz
iestatīts indekss ir vienāds alfabēts mīnusu 1, kas būs rādītājs 26.
Cits, ja tas nav Apostrofs, tad mēs ejam, lai uzstādītu indeksu
vienāds ar c mīnus.
Līdz ar to atcerēties atpakaļ no iepriekšējiem p komplekti, c mīnus gatavojas sniegt mums
alfabēta stāvokli c, tāpēc, ja c ir burts, tas
dod mums indekss nulle.
Par vēstules B, tas dotu mums indekss 1, un tā tālāk.
>> Tāpēc tas dod mums indekss spēkā Bērni masīvs, ko mēs gribam.
Tagad, ja šis rādītājs pašlaik Null Bērni masīvs, tas nozīmē, ka
mezglu pašreiz nav no ka ceļš, tāpēc mums ir nepieciešams piešķirt
mezglu, lai šajā ceļā.
Tas ir tas, ko mēs darām šeit.
Tāpēc mēs ejam atkal izmantojiet Calloc funkciju, tā, ka mums nav
līdz nulle visas norādes, un mēs, atkal, ir nepieciešams, lai pārbaudītu, vai Calloc
nav neizdoties.
Ja Calloc tomēr neizdodas, tad mums izkraut viss, aizvērt
vārdnīcu, un atgriešanās False.
>> Tātad, pieņemot, ka tas nav neizdoties, tad Tas radīs jaunu bērnu mums,
un tad mēs dosimies uz šo bērnu.
Mūsu kursors atkārtot uz leju, lai šo bērnu.
Tagad, ja tas nav null, lai sāktu ar, tad kursors var tikai atkārtot
uz leju, lai šo bērnu, bet faktiski kam piešķirt neko.
Šis ir gadījums, kad mēs pirmo reizi notika piešķirt vārdu kaķis, un
tas nozīmē, ka tad, kad mēs ejam, lai sadalītu katastrofa, mums nav nepieciešams, lai izveidotu
mezglu C-A-T vēlreiz.
Viņi jau pastāv.
>> Labi, lai to, kas ir šis cits?
Tas ir stāvoklis, kurā c ir slīpsvītru n, kur c ir jauna līnija.
Tas nozīmē, ka ir veiksmīgi pabeidzis vārdu.
Tagad, ko mēs vēlamies darīt, kad mēs sekmīgi pabeigta vārdu?
Mēs ejam, lai izmantotu šo vārdu lauku iekšpusē mūsu struktūrai mezglā.
>> Mēs gribam, lai noteiktu, ka uz True, lai norāda, ka šis mezgls norāda
veiksmīga vārdu faktisko vārdu.
Tagad, noteikti, ka, lai True.
Mēs vēlamies, lai atjaunotu savu kursoru uz punktu līdz sākumā Trie atkal.
Un visbeidzot, solis mūsu vārdnīca izmērs, jo mēs atradām citu vārdu.
>> Labi, tāpēc mēs ejam, lai saglabātu darot ka, lasot raksturs, ko
raksturs, būvējot jaunas mezglu mūsu Trie un katram vārdu
vārdnīcu, kamēr mēs beidzot sasniedz c vienāds EOF, tādā gadījumā mēs laužam
no lietas materiāliem.
Tagad ar divi gadījumi kas mēs varētu būt hit EOF.
Pirmais ir, ja tur bija kļūda lasot no lietas materiāliem, tāpēc, ja tur bija
kļūda, kas mums jādara, tipisks izkraut viss, slēgt datni,
atgriešanās False.
Pieņemot, ka tur nebija kļūda, ka tikai nozīmē, ka mēs faktiski hit beigām
failu, un tādā gadījumā, mēs cieši failu un atgriezties taisnība, jo mēs
veiksmīgi ielādēta vārdnīcu mūsu Trie.
>> Labi, tāpēc tagad pieņemsim izbraukšana pārbaude.
Raugoties uz pārbaudes funkciju, mēs redzam, ka pārbaude ir gatavojas atgriezties bool.
Tā atgriež True, ja šis vārds, ka tas ir tiek pieņemts, tur ir mūsu Trie.
Tā atgriež False citādi.
>> Tātad, kā mēs gatavojamies, lai noteiktu, vai šis vārds ir mūsu Trie?
Mēs redzam šeit, ka, tāpat kā iepriekš, mēs gatavojamies izmantot kursoru atkārtot
caur mūsu Trie.
Tagad, šeit mēs esam gatavojas atkārtot pār mūsu visu vārdu.
Tātad, atkārtojot visā vārdu mēs esam pagājis, mēs ejam, lai noteiktu
indeksu uz Bērnu masīvu, kas atbilst vārdu stiprinājuma i.
Tāpēc tas ir gatavojas izskatās tieši tāpat kā Slodze, kur, ja vārds kronšteins i ir
Apostrofs, tad mēs vēlamies izmantot indeksu alfabēts mīnus 1, jo mēs noteicām
tas ir, ja mēs ejam uzglabāt apostrofiem.
>> Vēl mēs spēsim izmantot tolower Vārds kronšteins i.
Līdz ar to atcerēties, ka vārds var būt patvaļīgs kapitalizācija, un tāpēc mēs
vēlaties pārliecināties, ka mēs izmantojam mazie versija lietām.
Un tad atņemt no šī mazajiem lai, atkal, dod mums
alfabēta amats par šo personāžu.
Tā, ka būs mūsu indeksu uz bērnu masīvs.
>> Un tagad, ja šis rādītājs uz Bērnu masīvs ir nulle, tas nozīmē, ka mēs
vairs nevar turpināt, atkārtojot leju mūsu Trie.
Ja tas ir gadījumā, šis vārds nevar iespējams, varētu būt mūsu Trie, jo, ja tā
bija, tas nozīmētu, ka varētu būt ceļš uz leju, lai šo vārdu, un jūs,
nekad sastapties null.
Tātad sastopas Null, mēs atgriežamies False.
Vārda nav vārdnīcā.
Ja tas nav null, tad mēs ejam turpinās atkārtojot, tāpēc mēs ejam
lai atjauninātu savu kursoru, lai norādītu, ka īpaši mezglā šajā indeksā.
>> Tāpēc mēs turpinām darām visu visu vārdu.
Pieņemot, ka mēs nekad hit nulle, tas nozīmē mēs varējām dabūt cauri visam
pasaulē un atrast mezglu mūsu Trie, bet mēs neesam gluži izdarīts vēl.
Mēs nevēlamies, lai tikai atgrieztos True.
Mēs vēlamies, lai atgrieztos kursoru kļūdas vārdu jo, atcerieties, atkal, ja kaķis nav
mūsu vārdnīcu un katastrofa ir, tad mēs veiksmīgi tikt cauri
vārdu kaķis, bet kursors vārds būs False un nav taisnība.
Tāpēc mēs atgriežamies kursora vārdu, lai norādītu vai šis mezgls ir patiesībā vārds,
un tas arī viss par pārbaudi.
>> Tāpēc pieņemsim izbraukšana izmērs.
Tā lielums būs diezgan viegli jo atceros, Load, mēs esam
palielināšanai vārdnīca izmēru katrs vārds, ko mēs saskaramies.
Tā lielums ir tikai gatavojas atgriezties vārdnīca izmēru, un tas arī viss.
>> Labi, tāpēc visbeidzot, mēs esam izkraut.
Tātad Izkraut, mēs ejam, lai izmantotu rekursīvas funkcijas, lai faktiski darīt visu
no darba mums, lai mūsu funkcija būs saukt Atslodzes.
Kas ir Atslodzes gatavojas darīt?
Mēs redzam šeit, ka Atslodzes gatavojas atkārtot pār visiem bērniem
Tas īpaši mezglā, un, ja bērns mezgls nav nulle, tad mēs ejam
izkraut bērnu mezglu.
>> Tātad šis būs rekursīvi izkraut visas mūsu bērniem.
Pēc tam, kad mēs esam pārliecināti, ka visi mūsu bērni ir izkrautas, tad mēs
var atbrīvot sevi, lai izkrautu ourself.
Tāpēc tas rekursīvi izkraut Visa Trie, un tad, kad tas ir
izdarīts, mēs varam vienkārši atgriezties True.
Izkraut nevar neizdoties, mēs esam tikai atbrīvojot lietas.
Tātad, kad mēs esam darījuši atbrīvojot viss, atgriešanās True.
Un tas arī viss.
Mans vārds ir Rob, un šī bija [dzirdams].