1
00:00:00,000 --> 00:00:00,530

2
00:00:00,530 --> 00:00:03,070
>> SPEAKER 1: Să-i dăm
această soluție o încercare.

3
00:00:03,070 --> 00:00:07,130
Deci, haideți să aruncăm o privire la ceea ce noi
Struct nod va arata.

4
00:00:07,130 --> 00:00:11,040
Aici, vom vedea vom avea o
Bool Word și o stea nod Struct

5
00:00:11,040 --> 00:00:12,990
Copiii bracketing alfabet.

6
00:00:12,990 --> 00:00:18,720
Deci, primul lucru pe care ar putea fi mirat,
de ce este hash alfabet definit ca 27?

7
00:00:18,720 --> 00:00:22,540
Ei bine, amintiți-vă că vom avea nevoie de
să fie de manipulare apostrof, astfel

8
00:00:22,540 --> 00:00:25,610
care va fi oarecum de un special
cazul în care pe parcursul acestui program.

9
00:00:25,610 --> 00:00:28,780
>> OK, acum, amintiți-vă cum o
Trie de fapt de lucrări.

10
00:00:28,780 --> 00:00:33,420
Să presupunem că suntem indexarea pisicile cuvânt,
apoi de la rădăcina de Trie noastre,

11
00:00:33,420 --> 00:00:36,670
ne vom uita la copii
matrice, și ne vom uita la

12
00:00:36,670 --> 00:00:42,250
indice care corespunde literei
C. Deci, care ar fi indicele de doi.

13
00:00:42,250 --> 00:00:46,400
Deci, având în vedere că, care ne va da
un nou nod, și apoi ne vom

14
00:00:46,400 --> 00:00:47,880
de lucru de la acel nod.

15
00:00:47,880 --> 00:00:51,830
>> Deci, având în vedere că nod, suntem încă o dată
gând să se uite la matrice pentru copii,

16
00:00:51,830 --> 00:00:56,170
și ne vom uita la index zero,
să corespundă A de pisică.

17
00:00:56,170 --> 00:01:01,240
Deci, atunci vom merge la acel nod,
și având în vedere că nod, vom

18
00:01:01,240 --> 00:01:05,170
să se uite la indicele care corespunde
la T. Și de a trece la acel nod,

19
00:01:05,170 --> 00:01:09,590
în cele din urmă, ne-am uitat complet
prin intermediul Cat nostru cuvânt, iar acum Bool

20
00:01:09,590 --> 00:01:15,020
Cuvânt ar trebui să indice dacă
acest cuvânt dat este de fapt un cuvânt.

21
00:01:15,020 --> 00:01:17,530
>> Deci, de ce avem nevoie de acest caz special?

22
00:01:17,530 --> 00:01:21,680
Ei bine, ceea ce în cazul în care cuvântul catastrofă
este în dicționarul nostru, dar

23
00:01:21,680 --> 00:01:24,120
pisica cuvânt nu este?

24
00:01:24,120 --> 00:01:29,030
Deci, în căutarea pentru a vedea dacă pisica cuvânt este
în dicționarul nostru, vom

25
00:01:29,030 --> 00:01:34,880
uite cu succes prin intermediul indicilor
C-A-T și să ajungă la un nod, dar asta e

26
00:01:34,880 --> 00:01:39,760
doar pentru că sa întâmplat la catastrofă
crea noduri pe drumul de la C-A-T toate

27
00:01:39,760 --> 00:01:41,250
drumul până la sfârșitul cuvântului.

28
00:01:41,250 --> 00:01:46,520
Astfel Bool Word este utilizat indică dacă
această locație special de fapt

29
00:01:46,520 --> 00:01:48,370
indică un cuvânt.

30
00:01:48,370 --> 00:01:52,920
>> Bine, deci acum că știm ce o
Trie se va arăta, să ne uităm

31
00:01:52,920 --> 00:01:54,800
la funcția de încărcare.

32
00:01:54,800 --> 00:01:58,670
Deci, de încărcare este de gând să se întoarcă un Bool
pentru dacă noi cu succes sau

33
00:01:58,670 --> 00:02:03,020
dicționar încărcate fără succes și
acest lucru va fi în dicționar

34
00:02:03,020 --> 00:02:04,520
pe care vrem să se încarce.

35
00:02:04,520 --> 00:02:08,310
Deci, primul lucru pe care am de gând să faceți este să deschideți
up care dicționar pentru lectură.

36
00:02:08,310 --> 00:02:12,060
Trebuie să ne asigurăm că nu a eșuat,
așa că, dacă dicționarul nu a fost

37
00:02:12,060 --> 00:02:15,280
deschis cu succes, se va reveni
Nu, în cazul în care vom

38
00:02:15,280 --> 00:02:16,340
return false.

39
00:02:16,340 --> 00:02:21,290
Dar presupunând că aceasta cu succes
a deschis, atunci se poate citi de fapt

40
00:02:21,290 --> 00:02:22,310
prin dicționar.

41
00:02:22,310 --> 00:02:24,940
>> Deci, primul lucru pe care am de gând să
Vreau să faceți este să avem această

42
00:02:24,940 --> 00:02:26,560
rădăcină variabilă globală.

43
00:02:26,560 --> 00:02:30,250
Acum, radacina va fi o stea nod.

44
00:02:30,250 --> 00:02:33,830
Este partea de sus a Trie nostru că suntem
va fi iterarea prin intermediul.

45
00:02:33,830 --> 00:02:38,200
Deci, primul lucru pe care am de gând să doriți să
face este aloca memorie pentru radacina noastra.

46
00:02:38,200 --> 00:02:42,040
>> Observați că suntem folosind calloc
funcție, care este în esență același

47
00:02:42,040 --> 00:02:45,560
ca funcția malloc, cu excepția e
garantat pentru a reveni ceva care este

48
00:02:45,560 --> 00:02:47,240
complet adus la zero.

49
00:02:47,240 --> 00:02:51,350
Deci, dacă am folosit malloc, ne-ar trebui să
du-te prin toate indicii în nostru

50
00:02:51,350 --> 00:02:54,220
nod și asigurați-vă că
toate acestea sunt nule.

51
00:02:54,220 --> 00:02:56,780
Astfel calloc va face asta pentru noi.

52
00:02:56,780 --> 00:03:00,390
>> Acum, la fel ca malloc, avem nevoie pentru a face
sigur că alocarea este de fapt

53
00:03:00,390 --> 00:03:01,580
succes.

54
00:03:01,580 --> 00:03:04,060
În cazul în care acest lucru sa întors null, atunci ne-am
nevoie pentru a închide dicționarul nostru

55
00:03:04,060 --> 00:03:06,170
fișier și a reveni Fals.

56
00:03:06,170 --> 00:03:11,040
Deci, presupunând că alocarea a fost
de succes, vom folosi un nod

57
00:03:11,040 --> 00:03:14,340
stea Cursor de a repeta
prin Trie nostru.

58
00:03:14,340 --> 00:03:17,950
Deci, radacina noastra nu se va schimba,
dar am de gând să folosească Cursor pentru

59
00:03:17,950 --> 00:03:20,770
de fapt, du-te de la nod la nod.

60
00:03:20,770 --> 00:03:25,000
>> În regulă, deci în această buclă, noi suntem
citit prin fișierul dicționar,

61
00:03:25,000 --> 00:03:26,965
și folosim la fgetc.

62
00:03:26,965 --> 00:03:30,360
Astfel fgetc este de gând să apuca un singur
personaj din dosar.

63
00:03:30,360 --> 00:03:33,430
Vom continua hapsân
caractere în timp ce noi nu ajung la

64
00:03:33,430 --> 00:03:37,540
capăt de dosar, astfel încât există
două cazuri pe care trebuie să se ocupe.

65
00:03:37,540 --> 00:03:41,640
Primul, dacă nu a fost un caracter
Noua linie, așa că știu dacă a fost un nou

66
00:03:41,640 --> 00:03:44,480
linie, atunci suntem pe cale să
trece la un nou cuvânt.

67
00:03:44,480 --> 00:03:49,300
Dar presupunând că nu a fost o linie nouă, apoi
aici, vrem să dau seama de

68
00:03:49,300 --> 00:03:52,440
index vom index în
în matrice copii care

69
00:03:52,440 --> 00:03:53,890
ne-am uitat la mai înainte.

70
00:03:53,890 --> 00:03:57,950
>> Așa cum am spus mai înainte, trebuie să ne
caz special apostrof.

71
00:03:57,950 --> 00:04:01,040
Observați suntem folosind operatorul ternar
aici, așa că vom citi

72
00:04:01,040 --> 00:04:05,500
acest lucru ca în cazul în care personajul citim în era
un apostrof, atunci vom

73
00:04:05,500 --> 00:04:11,740
setat index egal cu alfabet minus
1, care va fi indexul 26.

74
00:04:11,740 --> 00:04:15,190
Altfel, în cazul în care acesta nu a fost un apostrof,
apoi vom stabili indicele

75
00:04:15,190 --> 00:04:17,820
egal cu C minus o.

76
00:04:17,820 --> 00:04:23,090
Deci, amintiți-vă înapoi de la seturi p anterioare,
c minus o este de gând să ne dea

77
00:04:23,090 --> 00:04:27,470
Poziția alfabetică de c, așa că, dacă
c este litera A, acest lucru va

78
00:04:27,470 --> 00:04:28,770
ne da index zero.

79
00:04:28,770 --> 00:04:32,180
Pentru litera B, s-ar da
ne indicele 1, și așa mai departe.

80
00:04:32,180 --> 00:04:37,070
>> Deci, acest lucru ne dă indicele în
Matrice de copii pe care ne-o dorim.

81
00:04:37,070 --> 00:04:42,540
Acum, în cazul în care acest indicator este în prezent nul în
matrice pentru copii, ceea ce înseamnă că

82
00:04:42,540 --> 00:04:47,470
un nod nu există în prezent din
această cale, așa că trebuie să aloce o

83
00:04:47,470 --> 00:04:49,220
nod pentru această cale.

84
00:04:49,220 --> 00:04:50,610
Asta e ceea ce facem noi aici.

85
00:04:50,610 --> 00:04:54,650
Așa că am de gând să, din nou, utilizați calloc
funcție, astfel că nu avem

86
00:04:54,650 --> 00:05:00,130
la zero, tot din indicii, și noi,
din nou, trebuie să verificați că calloc

87
00:05:00,130 --> 00:05:01,300
nu a eșuat.

88
00:05:01,300 --> 00:05:04,760
Dacă calloc a eșua, atunci avem nevoie de
pentru a descărca totul, închideți nostru

89
00:05:04,760 --> 00:05:06,880
dicționar, și întoarce False.

90
00:05:06,880 --> 00:05:14,110
>> Deci, presupunând că nu reușesc, atunci
acest lucru va crea un nou copil pentru noi,

91
00:05:14,110 --> 00:05:16,000
iar apoi vom merge la acel copil.

92
00:05:16,000 --> 00:05:19,030
Cursor nostru va repeta
până la acel copil.

93
00:05:19,030 --> 00:05:23,390
Acum, în cazul în care acest lucru nu a fost nul pentru a începe cu,
atunci cursorul se poate repeta doar

94
00:05:23,390 --> 00:05:26,650
până la care copilul fără de fapt,
a trebui să aloce nimic.

95
00:05:26,650 --> 00:05:30,790
Acesta este cazul în care ne-am sa întâmplat în primul rând
să aloce pisica cuvânt, și

96
00:05:30,790 --> 00:05:34,390
asta înseamnă că, atunci când vom merge să aloce
catastrofă, nu avem nevoie pentru a crea

97
00:05:34,390 --> 00:05:35,720
noduri pentru C-A-T din nou.

98
00:05:35,720 --> 00:05:37,620
Acestea există deja.

99
00:05:37,620 --> 00:05:40,140
>> OK, deci ce este asta altceva?

100
00:05:40,140 --> 00:05:44,600
Aceasta este condiția în care c este
backslash n, unde c este o noua linie.

101
00:05:44,600 --> 00:05:47,780
Acest lucru înseamnă că avem succes
finalizat un cuvânt.

102
00:05:47,780 --> 00:05:51,020
Acum, ce vrem să facem atunci când ne-am
finalizat cu succes un cuvânt?

103
00:05:51,020 --> 00:05:55,250
Vom folosi acest domeniu cuvânt
interiorul nod noastre Struct.

104
00:05:55,250 --> 00:06:00,570
>> Vrem să se stabilească faptul că la True, astfel încât
indică faptul că acest nod indică o

105
00:06:00,570 --> 00:06:03,320
cuvânt cu succes un cuvânt real.

106
00:06:03,320 --> 00:06:05,050
Acum, stabilit că la Adevărat.

107
00:06:05,050 --> 00:06:09,210
Vrem să resetați cursorul nostru la punct
la începutul trie din nou.

108
00:06:09,210 --> 00:06:13,510
Și, în sfârșit, incrementa dicționarul nostru
dimensiune de când am găsit un alt cuvânt.

109
00:06:13,510 --> 00:06:16,450
>> În regulă, așa că vom continua să faci
că, citind în caracter de

110
00:06:16,450 --> 00:06:21,960
caracter, construirea de noi noduri în
Trie noastră și pentru fiecare cuvânt în

111
00:06:21,960 --> 00:06:26,810
dicționar, până când vom ajunge în cele din urmă c
este egal cu EOF, caz în care, ne rupe

112
00:06:26,810 --> 00:06:28,100
din dosar.

113
00:06:28,100 --> 00:06:31,110
Acum, există două cazuri în
pe care ne-am fi lovit EOF.

114
00:06:31,110 --> 00:06:35,680
Primul este dacă a existat o eroare
citirea de la dosar, așa că, dacă nu a fost

115
00:06:35,680 --> 00:06:39,280
o eroare, trebuie să facem tipic
descărca totul, închideți fișierul,

116
00:06:39,280 --> 00:06:40,520
return false.

117
00:06:40,520 --> 00:06:43,870
Presupunând că nu a fost o eroare, care
înseamnă doar ne-am lovit de fapt la sfârșitul anului

118
00:06:43,870 --> 00:06:47,820
dosar, în care caz, am închide
fișier și a reveni adevărat din moment ce

119
00:06:47,820 --> 00:06:51,010
încărcate cu succes în dicționar
în Trie nostru.

120
00:06:51,010 --> 00:06:54,240
>> Bine, deci acum hai
a verifica afară Verificare.

121
00:06:54,240 --> 00:06:58,780
Privind la funcția Verificare, vom vedea
că Check este de gând să se întoarcă un Bool.

122
00:06:58,780 --> 00:07:03,740
Se întoarce True dacă acest cuvânt care este
fiind trecut este în Trie nostru.

123
00:07:03,740 --> 00:07:06,170
Se întoarce FALSE în caz contrar.

124
00:07:06,170 --> 00:07:10,110
>> Deci, cum vom determina dacă
acest cuvânt este în Trie nostru?

125
00:07:10,110 --> 00:07:14,270
Vedem aici că, la fel ca înainte,
vom folosi cursorul pentru a repeta

126
00:07:14,270 --> 00:07:16,010
prin Trie nostru.

127
00:07:16,010 --> 00:07:20,650
Acum, aici, vom repeta
peste întreaga noastră cuvânt.

128
00:07:20,650 --> 00:07:24,680
Astfel iterarea peste cuvântul suntem
a trecut, vom determina

129
00:07:24,680 --> 00:07:29,280
index în matrice copii care
corespunde cuvânt suport i.

130
00:07:29,280 --> 00:07:34,150
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

131
00:07:34,150 --> 00:07:38,110
apostrof, atunci vrem sa folosim index
alfabet minus 1 pentru că ne-am stabilit

132
00:07:38,110 --> 00:07:41,160
că este în cazul în care vom merge
pentru a stoca apostrofuri.

133
00:07:41,160 --> 00:07:44,440
>> Altfel vom folosi tolower
Suport de cuvânt i.

134
00:07:44,440 --> 00:07:48,270
Deci, amintiți-vă că cuvânt poate avea arbitrară
capitalizare, și așa ne-am

135
00:07:48,270 --> 00:07:51,590
doriți să vă asigurați că suntem folosind
o versiune cu litere mici de lucruri.

136
00:07:51,590 --> 00:07:55,300
Și apoi scade din care minuscule
o să, încă o dată, ne da

137
00:07:55,300 --> 00:07:57,940
poziție alfabetică
din acel caracter.

138
00:07:57,940 --> 00:08:01,740
Astfel că va fi indexul nostru
în matrice pentru copii.

139
00:08:01,740 --> 00:08:06,480
>> Și acum, în cazul în care indicele în Copiilor
matrice este nulă, înseamnă că ne-am

140
00:08:06,480 --> 00:08:09,050
nu mai poate continua iterarea
jos Trie nostru.

141
00:08:09,050 --> 00:08:13,320
Dacă acesta este cazul, acest cuvânt nu poate
fi, eventual, în Trie noastră, deoarece în cazul în care

142
00:08:13,320 --> 00:08:18,000
au fost, că ar însemna că ar fi o
cale până la acest cuvânt, și v-ar

143
00:08:18,000 --> 00:08:19,350
nu se confruntă null.

144
00:08:19,350 --> 00:08:21,910
Așa se confruntă cu null, ne vom întoarce False.

145
00:08:21,910 --> 00:08:23,810
În care cuvântul nu este în dicționar.

146
00:08:23,810 --> 00:08:28,200
În cazul în care nu au fost nule, atunci vom
continuă iterarea, așa că vom

147
00:08:28,200 --> 00:08:33,150
pentru a actualiza cursorul noastră să indice că
nod special la acel index.

148
00:08:33,150 --> 00:08:36,659
>> Așa că am continua să faci asta de-a lungul
întregul cuvânt.

149
00:08:36,659 --> 00:08:40,630
Presupunând că nu am lovit nulă, care înseamnă
noi am fost capabil de a obține prin întregul

150
00:08:40,630 --> 00:08:44,840
lume și de a găsi un nod în Trie nostru,
dar nu suntem destul de terminat încă.

151
00:08:44,840 --> 00:08:46,350
Noi nu vrem să se întoarcă doar Adevărat.

152
00:08:46,350 --> 00:08:51,400
Vrem să se întoarcă cursorul eroare cuvânt
din moment ce, amintiți-vă din nou, în cazul în care pisica nu este

153
00:08:51,400 --> 00:08:55,140
în dicționar și catastrofă noastră este,
atunci vom obține cu succes prin

154
00:08:55,140 --> 00:08:59,810
pisica cuvânt, dar cursorul cuvânt
va fi fals și nu este adevărat.

155
00:08:59,810 --> 00:09:04,990
Deci, ne întoarcem cuvânt cursor pentru a indica
dacă acest nod este de fapt un cuvânt,

156
00:09:04,990 --> 00:09:06,530
și asta este pentru verificare.

157
00:09:06,530 --> 00:09:08,310
>> Deci, haideți să verificați Size.

158
00:09:08,310 --> 00:09:11,410
Deci, Size va fi destul de ușor
din moment ce, amintiți-vă în sarcină, suntem

159
00:09:11,410 --> 00:09:15,480
incrementarea dimensiune dicționar pentru
fiecare cuvânt pe care le întâlnim.

160
00:09:15,480 --> 00:09:20,820
Deci, Dimensiunea este doar de gând să se întoarcă
Dimensiunea dicționar, și asta e tot.

161
00:09:20,820 --> 00:09:24,650
>> În regulă, așa că în cele din urmă, ne-am Unload.

162
00:09:24,650 --> 00:09:29,050
Deci Unload, vom folosi un
Funcția recursive a face de fapt tot

163
00:09:29,050 --> 00:09:33,390
de lucru pentru noi, așa că funcția noastră
va fi numit Unloader.

164
00:09:33,390 --> 00:09:35,830
Ce se Unloader de gând să faci?

165
00:09:35,830 --> 00:09:40,640
Vedem aici că Unloader se va
itera peste toți copiii la

166
00:09:40,640 --> 00:09:45,810
acest nod special, și dacă copilul
nod nu este nul, atunci vom

167
00:09:45,810 --> 00:09:47,760
descărca nodul copil.

168
00:09:47,760 --> 00:09:52,070
>> Deci, acest lucru se întâmplă pentru a recursiv
descărca toate de copiii noștri.

169
00:09:52,070 --> 00:09:55,140
Odată ce suntem siguri că toți copiii noștri
au fost descărcate, apoi ne-am

170
00:09:55,140 --> 00:09:58,830
ne putem elibera, așa descărca noi înșine.

171
00:09:58,830 --> 00:10:04,550
Deci, aceasta va descărca recursiv
întreaga Trie, și apoi o dată că este

172
00:10:04,550 --> 00:10:06,910
face, ne putem întoarce doar Adevărat.

173
00:10:06,910 --> 00:10:09,770
În gol nu poate da greș, suntem
doar eliberarea lucrurile.

174
00:10:09,770 --> 00:10:12,985
Deci, odată ce am terminat eliberarea
totul, intoarce Adevărat.

175
00:10:12,985 --> 00:10:14,380
Și asta e tot.

176
00:10:14,380 --> 00:10:16,792
Numele meu este Rob, și acest lucru
a fost [neauzit].

177
00:10:16,792 --> 00:10:21,888