>> SPEAKER 1: Să-i dăm această soluție o încercare.
Deci, haideți să aruncăm o privire la ceea ce noi Struct nod va arata.
Aici, vom vedea vom avea o Bool Word și o stea nod Struct
Copiii bracketing alfabet.
Deci, primul lucru pe care ar putea fi mirat, de ce este hash alfabet definit ca 27?
Ei bine, amintiți-vă că vom avea nevoie de să fie de manipulare apostrof, astfel
care va fi oarecum de un special cazul în care pe parcursul acestui program.
>> OK, acum, amintiți-vă cum o Trie de fapt de lucrări.
Să presupunem că suntem indexarea pisicile cuvânt, apoi de la rădăcina de Trie noastre,
ne vom uita la copii matrice, și ne vom uita la
indice care corespunde literei C. Deci, care ar fi indicele de doi.
Deci, având în vedere că, care ne va da un nou nod, și apoi ne vom
de lucru de la acel nod.
>> Deci, având în vedere că nod, suntem încă o dată gând să se uite la matrice pentru copii,
și ne vom uita la index zero, să corespundă A de pisică.
Deci, atunci vom merge la acel nod, și având în vedere că nod, vom
să se uite la indicele care corespunde la T. Și de a trece la acel nod,
în cele din urmă, ne-am uitat complet prin intermediul Cat nostru cuvânt, iar acum Bool
Cuvânt ar trebui să indice dacă acest cuvânt dat este de fapt un cuvânt.
>> Deci, de ce avem nevoie de acest caz special?
Ei bine, ceea ce în cazul în care cuvântul catastrofă este în dicționarul nostru, dar
pisica cuvânt nu este?
Deci, în căutarea pentru a vedea dacă pisica cuvânt este în dicționarul nostru, vom
uite cu succes prin intermediul indicilor C-A-T și să ajungă la un nod, dar asta e
doar pentru că sa întâmplat la catastrofă crea noduri pe drumul de la C-A-T toate
drumul până la sfârșitul cuvântului.
Astfel Bool Word este utilizat indică dacă această locație special de fapt
indică un cuvânt.
>> Bine, deci acum că știm ce o Trie se va arăta, să ne uităm
la funcția de încărcare.
Deci, de încărcare este de gând să se întoarcă un Bool pentru dacă noi cu succes sau
dicționar încărcate fără succes și acest lucru va fi în dicționar
pe care vrem să se încarce.
Deci, primul lucru pe care am de gând să faceți este să deschideți up care dicționar pentru lectură.
Trebuie să ne asigurăm că nu a eșuat, așa că, dacă dicționarul nu a fost
deschis cu succes, se va reveni Nu, în cazul în care vom
return false.
Dar presupunând că aceasta cu succes a deschis, atunci se poate citi de fapt
prin dicționar.
>> Deci, primul lucru pe care am de gând să Vreau să faceți este să avem această
rădăcină variabilă globală.
Acum, radacina va fi o stea nod.
Este partea de sus a Trie nostru că suntem va fi iterarea prin intermediul.
Deci, primul lucru pe care am de gând să doriți să face este aloca memorie pentru radacina noastra.
>> Observați că suntem folosind calloc funcție, care este în esență același
ca funcția malloc, cu excepția e garantat pentru a reveni ceva care este
complet adus la zero.
Deci, dacă am folosit malloc, ne-ar trebui să du-te prin toate indicii în nostru
nod și asigurați-vă că toate acestea sunt nule.
Astfel calloc va face asta pentru noi.
>> Acum, la fel ca malloc, avem nevoie pentru a face sigur că alocarea este de fapt
succes.
În cazul în care acest lucru sa întors null, atunci ne-am nevoie pentru a închide dicționarul nostru
fișier și a reveni Fals.
Deci, presupunând că alocarea a fost de succes, vom folosi un nod
stea Cursor de a repeta prin Trie nostru.
Deci, radacina noastra nu se va schimba, dar am de gând să folosească Cursor pentru
de fapt, du-te de la nod la nod.
>> În regulă, deci în această buclă, noi suntem citit prin fișierul dicționar,
și folosim la fgetc.
Astfel fgetc este de gând să apuca un singur personaj din dosar.
Vom continua hapsân caractere în timp ce noi nu ajung la
capăt de dosar, astfel încât există două cazuri pe care trebuie să se ocupe.
Primul, dacă nu a fost un caracter Noua linie, așa că știu dacă a fost un nou
linie, atunci suntem pe cale să trece la un nou cuvânt.
Dar presupunând că nu a fost o linie nouă, apoi aici, vrem să dau seama de
index vom index în în matrice copii care
ne-am uitat la mai înainte.
>> Așa cum am spus mai înainte, trebuie să ne caz special apostrof.
Observați suntem folosind operatorul ternar aici, așa că vom citi
acest lucru ca în cazul în care personajul citim în era un apostrof, atunci vom
setat index egal cu alfabet minus 1, care va fi indexul 26.
Altfel, în cazul în care acesta nu a fost un apostrof, apoi vom stabili indicele
egal cu C minus o.
Deci, amintiți-vă înapoi de la seturi p anterioare, c minus o este de gând să ne dea
Poziția alfabetică de c, așa că, dacă c este litera A, acest lucru va
ne da index zero.
Pentru litera B, s-ar da ne indicele 1, și așa mai departe.
>> Deci, acest lucru ne dă indicele în Matrice de copii pe care ne-o dorim.
Acum, în cazul în care acest indicator este în prezent nul în matrice pentru copii, ceea ce înseamnă că
un nod nu există în prezent din această cale, așa că trebuie să aloce o
nod pentru această cale.
Asta e ceea ce facem noi aici.
Așa că am de gând să, din nou, utilizați calloc funcție, astfel că nu avem
la zero, tot din indicii, și noi, din nou, trebuie să verificați că calloc
nu a eșuat.
Dacă calloc a eșua, atunci avem nevoie de pentru a descărca totul, închideți nostru
dicționar, și întoarce False.
>> Deci, presupunând că nu reușesc, atunci acest lucru va crea un nou copil pentru noi,
iar apoi vom merge la acel copil.
Cursor nostru va repeta până la acel copil.
Acum, în cazul în care acest lucru nu a fost nul pentru a începe cu, atunci cursorul se poate repeta doar
până la care copilul fără de fapt, a trebui să aloce nimic.
Acesta este cazul în care ne-am sa întâmplat în primul rând să aloce pisica cuvânt, și
asta înseamnă că, atunci când vom merge să aloce catastrofă, nu avem nevoie pentru a crea
noduri pentru C-A-T din nou.
Acestea există deja.
>> OK, deci ce este asta altceva?
Aceasta este condiția în care c este backslash n, unde c este o noua linie.
Acest lucru înseamnă că avem succes finalizat un cuvânt.
Acum, ce vrem să facem atunci când ne-am finalizat cu succes un cuvânt?
Vom folosi acest domeniu cuvânt interiorul nod noastre Struct.
>> Vrem să se stabilească faptul că la True, astfel încât indică faptul că acest nod indică o
cuvânt cu succes un cuvânt real.
Acum, stabilit că la Adevărat.
Vrem să resetați cursorul nostru la punct la începutul trie din nou.
Și, în sfârșit, incrementa dicționarul nostru dimensiune de când am găsit un alt cuvânt.
>> În regulă, așa că vom continua să faci că, citind în caracter de
caracter, construirea de noi noduri în Trie noastră și pentru fiecare cuvânt în
dicționar, până când vom ajunge în cele din urmă c este egal cu EOF, caz în care, ne rupe
din dosar.
Acum, există două cazuri în pe care ne-am fi lovit EOF.
Primul este dacă a existat o eroare citirea de la dosar, așa că, dacă nu a fost
o eroare, trebuie să facem tipic descărca totul, închideți fișierul,
return false.
Presupunând că nu a fost o eroare, care înseamnă doar ne-am lovit de fapt la sfârșitul anului
dosar, în care caz, am închide fișier și a reveni adevărat din moment ce
încărcate cu succes în dicționar în Trie nostru.
>> Bine, deci acum hai a verifica afară Verificare.
Privind la funcția Verificare, vom vedea că Check este de gând să se întoarcă un Bool.
Se întoarce True dacă acest cuvânt care este fiind trecut este în Trie nostru.
Se întoarce FALSE în caz contrar.
>> Deci, cum vom determina dacă acest cuvânt este în Trie nostru?
Vedem aici că, la fel ca înainte, vom folosi cursorul pentru a repeta
prin Trie nostru.
Acum, aici, vom repeta peste întreaga noastră cuvânt.
Astfel iterarea peste cuvântul suntem a trecut, vom determina
index în matrice copii care corespunde cuvânt suport i.
Deci, acest lucru se întâmplă pentru a arata exact ca Sarcină, în cazul în care în cazul în care suportul cuvânt i este o
apostrof, atunci vrem sa folosim index alfabet minus 1 pentru că ne-am stabilit
că este în cazul în care vom merge pentru a stoca apostrofuri.
>> Altfel vom folosi tolower Suport de cuvânt i.
Deci, amintiți-vă că cuvânt poate avea arbitrară capitalizare, și așa ne-am
doriți să vă asigurați că suntem folosind o versiune cu litere mici de lucruri.
Și apoi scade din care minuscule o să, încă o dată, ne da
poziție alfabetică din acel caracter.
Astfel că va fi indexul nostru în matrice pentru copii.
>> Și acum, în cazul în care indicele în Copiilor matrice este nulă, înseamnă că ne-am
nu mai poate continua iterarea jos Trie nostru.
Dacă acesta este cazul, acest cuvânt nu poate fi, eventual, în Trie noastră, deoarece în cazul în care
au fost, că ar însemna că ar fi o cale până la acest cuvânt, și v-ar
nu se confruntă null.
Așa se confruntă cu null, ne vom întoarce False.
În care cuvântul nu este în dicționar.
În cazul în care nu au fost nule, atunci vom continuă iterarea, așa că vom
pentru a actualiza cursorul noastră să indice că nod special la acel index.
>> Așa că am continua să faci asta de-a lungul întregul cuvânt.
Presupunând că nu am lovit nulă, care înseamnă noi am fost capabil de a obține prin întregul
lume și de a găsi un nod în Trie nostru, dar nu suntem destul de terminat încă.
Noi nu vrem să se întoarcă doar Adevărat.
Vrem să se întoarcă cursorul eroare cuvânt din moment ce, amintiți-vă din nou, în cazul în care pisica nu este
în dicționar și catastrofă noastră este, atunci vom obține cu succes prin
pisica cuvânt, dar cursorul cuvânt va fi fals și nu este adevărat.
Deci, ne întoarcem cuvânt cursor pentru a indica dacă acest nod este de fapt un cuvânt,
și asta este pentru verificare.
>> Deci, haideți să verificați Size.
Deci, Size va fi destul de ușor din moment ce, amintiți-vă în sarcină, suntem
incrementarea dimensiune dicționar pentru fiecare cuvânt pe care le întâlnim.
Deci, Dimensiunea este doar de gând să se întoarcă Dimensiunea dicționar, și asta e tot.
>> În regulă, așa că în cele din urmă, ne-am Unload.
Deci Unload, vom folosi un Funcția recursive a face de fapt tot
de lucru pentru noi, așa că funcția noastră va fi numit Unloader.
Ce se Unloader de gând să faci?
Vedem aici că Unloader se va itera peste toți copiii la
acest nod special, și dacă copilul nod nu este nul, atunci vom
descărca nodul copil.
>> Deci, acest lucru se întâmplă pentru a recursiv descărca toate de copiii noștri.
Odată ce suntem siguri că toți copiii noștri au fost descărcate, apoi ne-am
ne putem elibera, așa descărca noi înșine.
Deci, aceasta va descărca recursiv întreaga Trie, și apoi o dată că este
face, ne putem întoarce doar Adevărat.
În gol nu poate da greș, suntem doar eliberarea lucrurile.
Deci, odată ce am terminat eliberarea totul, intoarce Adevărat.
Și asta e tot.
Numele meu este Rob, și acest lucru a fost [neauzit].