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

2
00:00:00,530 --> 00:00:03,070
>> ALTAVEU 1: Anem a donar-li
aquesta solució una oportunitat.

3
00:00:03,070 --> 00:00:07,130
Així que donem una ullada al nostre
Node d'estructura es veurà així.

4
00:00:07,130 --> 00:00:11,040
Aquí, veiem que tindrem un
Bool Paraula i una estrella node d'estructura

5
00:00:11,040 --> 00:00:12,990
Nens acorchetan alfabet.

6
00:00:12,990 --> 00:00:18,720
Així que el primer que potser es pregunti,
Per què és de hash alfabet defineix com 27?

7
00:00:18,720 --> 00:00:22,540
Bé, recordeu que nosaltres necessitarem
estar manejant l'apòstrof, per

8
00:00:22,540 --> 00:00:25,610
que serà una mena especial
cas a través d'aquest programa.

9
00:00:25,610 --> 00:00:28,780
>> Bé, ara, recordes com 1
Trie realment funciona.

10
00:00:28,780 --> 00:00:33,420
Diguem que estem indexant la paraula gats,
a continuació, a partir de l'arrel de la nostra Trie,

11
00:00:33,420 --> 00:00:36,670
anem a mirar els nens
matriu, i anem a mirar el

12
00:00:36,670 --> 00:00:42,250
índex que correspon a la lletra
C. Així que seria índex de dues.

13
00:00:42,250 --> 00:00:46,400
Així que tenint en compte que, que ens donarà
un nou node, i després anem a

14
00:00:46,400 --> 00:00:47,880
treballar des d'aquest node.

15
00:00:47,880 --> 00:00:51,830
>> Així que tenint en compte que el node, estem un cop més
va a mirar la matriu infantil,

16
00:00:51,830 --> 00:00:56,170
i anem a buscar en l'índex zero
per correspondre a la A en el gat.

17
00:00:56,170 --> 00:01:01,240
Així que anirem a aquest node,
i atès que el node, anem

18
00:01:01,240 --> 00:01:05,170
per buscar en l'índex que correspon
T. I de passar a aquest node,

19
00:01:05,170 --> 00:01:09,590
finalment, ens hem mirat del tot
a través del nostre gat de paraula, i ara Bool

20
00:01:09,590 --> 00:01:15,020
Paraula se suposa que ha d'indicar si
aquesta paraula donada és en realitat una paraula.

21
00:01:15,020 --> 00:01:17,530
>> Llavors, per què necessitem aquest cas especial?

22
00:01:17,530 --> 00:01:21,680
Bé, i si la paraula catàstrofe
és al diccionari, però

23
00:01:21,680 --> 00:01:24,120
la paraula gat no ho és?

24
00:01:24,120 --> 00:01:29,030
Així que en mirar per veure si la paraula gat és
al diccionari, anem a

25
00:01:29,030 --> 00:01:34,880
buscar amb èxit a través dels índexs
C-A-T i arribar a un node, però això és

26
00:01:34,880 --> 00:01:39,760
només perquè la catàstrofe va ocórrer a
crear nodes en el camí de C-A-T tot

27
00:01:39,760 --> 00:01:41,250
el camí fins al final de la paraula.

28
00:01:41,250 --> 00:01:46,520
Així Bool s'utilitza Word indicar si
aquest lloc en particular en realitat

29
00:01:46,520 --> 00:01:48,370
indica una paraula.

30
00:01:48,370 --> 00:01:52,920
>> Molt bé, així que ara que sabem el que és un
Trie es va a semblar, donem una ullada

31
00:01:52,920 --> 00:01:54,800
en la funció de càrrega.

32
00:01:54,800 --> 00:01:58,670
Així que la càrrega es va a tornar un Bool
Perquè si estem amb èxit o

33
00:01:58,670 --> 00:02:03,020
diccionari i carregat, sense èxit,
això serà el diccionari

34
00:02:03,020 --> 00:02:04,520
que volem carregar.

35
00:02:04,520 --> 00:02:08,310
Així que el primer que farem és obrir
fins a aquest diccionari per llegir.

36
00:02:08,310 --> 00:02:12,060
Hem de assegurar-nos que no fracassem,
pel que si el diccionari no era

37
00:02:12,060 --> 00:02:15,280
obert amb èxit, tornarà
No, en aquest cas anem a

38
00:02:15,280 --> 00:02:16,340
tornarà False.

39
00:02:16,340 --> 00:02:21,290
Però suposant que èxit
obert, llavors podem realment llegir

40
00:02:21,290 --> 00:02:22,310
a través del diccionari.

41
00:02:22,310 --> 00:02:24,940
>> Així que el primer que anem a
volem fer és que tenim aquesta

42
00:02:24,940 --> 00:02:26,560
arrel variable global.

43
00:02:26,560 --> 00:02:30,250
Ara, l'arrel serà una estrella de node.

44
00:02:30,250 --> 00:02:33,830
És el cim de la nostra Trie que estem
va a recórrer en iteració.

45
00:02:33,830 --> 00:02:38,200
Així que el primer que anem a voler
fer és assignar memòria per a la nostra arrel.

46
00:02:38,200 --> 00:02:42,040
>> Noteu que estem fent servir la calloc
funció, que és bàsicament la mateixa

47
00:02:42,040 --> 00:02:45,560
com la funció malloc, excepte que és
garantit per tornar una cosa que és

48
00:02:45,560 --> 00:02:47,240
completament portat a zero.

49
00:02:47,240 --> 00:02:51,350
Així que si utilitzem malloc, necessitaríem
passar per tots els punters en la nostra

50
00:02:51,350 --> 00:02:54,220
node i assegureu-vos que
són tots nuls.

51
00:02:54,220 --> 00:02:56,780
Així calloc ho farà per nosaltres.

52
00:02:56,780 --> 00:03:00,390
>> Ara, igual que malloc, hem de fer
Assegureu-vos que l'assignació és en realitat

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

54
00:03:01,580 --> 00:03:04,060
Si això retorna null, llavors
hagi de tancar el nostre diccionari

55
00:03:04,060 --> 00:03:06,170
presentar i tornar Fals.

56
00:03:06,170 --> 00:03:11,040
Així que assumint que l'assignació es
èxit, utilitzarem un node

57
00:03:11,040 --> 00:03:14,340
protagonitzar Cursor per repetir
a través del nostre Trie.

58
00:03:14,340 --> 00:03:17,950
Així que la nostra arrel mai canviarà,
però utilitzarem el cursor per

59
00:03:17,950 --> 00:03:20,770
en realitat anar d'un node a un altre.

60
00:03:20,770 --> 00:03:25,000
>> Molt bé, així que en aquest bucle, estem
llegir el fitxer de diccionari,

61
00:03:25,000 --> 00:03:26,965
i estem utilitzant al fgetc.

62
00:03:26,965 --> 00:03:30,360
Així fgetc va a agafar un sol
caràcter de l'arxiu.

63
00:03:30,360 --> 00:03:33,430
Anem a continuar amb l'acaparament
caràcters, mentre que no arriben fins a la

64
00:03:33,430 --> 00:03:37,540
final de l'arxiu, de manera que cal
2 casos hem de manejar.

65
00:03:37,540 --> 00:03:41,640
El primer, si el personatge no era un
nova línia, de manera que sabia si era un nou

66
00:03:41,640 --> 00:03:44,480
línia, llavors estem a punt de
passar a una nova paraula.

67
00:03:44,480 --> 00:03:49,300
Però suposant que no era una nova línia, a continuació,
aquí, volem esbrinar el

68
00:03:49,300 --> 00:03:52,440
Índex anem a índex en
en la matriu de nens que

69
00:03:52,440 --> 00:03:53,890
miràvem abans.

70
00:03:53,890 --> 00:03:57,950
>> Així que com he dit abans, hem de
cas especial l'apòstrof.

71
00:03:57,950 --> 00:04:01,040
Noteu que estem utilitzant l'operador ternari
aquí, així que llegirem

72
00:04:01,040 --> 00:04:05,500
això com si el personatge es llegeix en era
un apòstrof, a continuació, anem a

73
00:04:05,500 --> 00:04:11,740
setembre índex igual a menys alfabet
1, que serà l'índex de 26.

74
00:04:11,740 --> 00:04:15,190
Si no, si no fos un apòstrof,
a continuació, establirem l'índex

75
00:04:15,190 --> 00:04:17,820
igual a C menys un.

76
00:04:17,820 --> 00:04:23,090
Així que recorda de nou a partir de conjunts p anteriors,
c, menys una que ens donarà la

77
00:04:23,090 --> 00:04:27,470
posició alfabètica de c, de manera que si
c és la lletra A, aquesta voluntat

78
00:04:27,470 --> 00:04:28,770
donar-nos l'índex zero.

79
00:04:28,770 --> 00:04:32,180
Perquè la lletra B, donaria
ens l'índex 1, i així successivament.

80
00:04:32,180 --> 00:04:37,070
>> Així que això ens dóna l'índex a la
Nens matriu que volem.

81
00:04:37,070 --> 00:04:42,540
Ara bé, si aquest índex és actualment nul · la en
la matriu de nens, que significa que

82
00:04:42,540 --> 00:04:47,470
un node no existeix en l'actualitat de
aquest camí, així que hem de assignar una

83
00:04:47,470 --> 00:04:49,220
node per aquest camí.

84
00:04:49,220 --> 00:04:50,610
Això és el que fem aquí.

85
00:04:50,610 --> 00:04:54,650
Així que anem a, de nou, utilitzeu el calloc
funció de manera que no tenim

86
00:04:54,650 --> 00:05:00,130
posar a zero tots els punters, i nosaltres,
de nou, la necessitat de comprovar que calloc

87
00:05:00,130 --> 00:05:01,300
no va fallar.

88
00:05:01,300 --> 00:05:04,760
Si calloc va deixar, llavors necessitem
per descarregar tot, tancar la nostra

89
00:05:04,760 --> 00:05:06,880
diccionari, i tornarà False.

90
00:05:06,880 --> 00:05:14,110
>> Així que suposant que no va fallar, llavors
això crearà un nou fill per a nosaltres,

91
00:05:14,110 --> 00:05:16,000
i després anirem a aquest nen.

92
00:05:16,000 --> 00:05:19,030
El nostre cursor iterará
a aquest nen.

93
00:05:19,030 --> 00:05:23,390
Ara bé, si això no fos nul, per començar,
a continuació, el cursor només es pot repetir

94
00:05:23,390 --> 00:05:26,650
a aquest nen sense arribar a
haver de assignar res.

95
00:05:26,650 --> 00:05:30,790
Aquest és el cas en què primer va passar
per assignar la paraula gat, i

96
00:05:30,790 --> 00:05:34,390
això vol dir que quan anem a assignar
catàstrofe, que no necessitem per crear

97
00:05:34,390 --> 00:05:35,720
nodes per a C-A-T de nou.

98
00:05:35,720 --> 00:05:37,620
Ja existeixen.

99
00:05:37,620 --> 00:05:40,140
>> OK, llavors què és aquesta cosa?

100
00:05:40,140 --> 00:05:44,600
Aquesta és la condició en la que C era
barra invertida n, on c és una línia.

101
00:05:44,600 --> 00:05:47,780
Això vol dir que tenim èxit
completat una paraula.

102
00:05:47,780 --> 00:05:51,020
Ara, què és el que volem fer quan
completat amb èxit una paraula?

103
00:05:51,020 --> 00:05:55,250
Utilitzarem aquest camp la paraula
dins del nostre node d'estructura.

104
00:05:55,250 --> 00:06:00,570
>> Volem establir que en True, de manera que
indica que aquest node indica un

105
00:06:00,570 --> 00:06:03,320
paraula èxit una paraula real.

106
00:06:03,320 --> 00:06:05,050
Ara, ajust que a True.

107
00:06:05,050 --> 00:06:09,210
Volem restablir la nostra cursor fins al punt
al començament de la Trie de nou.

108
00:06:09,210 --> 00:06:13,510
I, finalment, incrementar el nostre diccionari
mida ja que trobem una paraula més.

109
00:06:13,510 --> 00:06:16,450
>> Molt bé, així que seguirem fent
que, en la lectura de caràcter per

110
00:06:16,450 --> 00:06:21,960
caràcter, la construcció de nous nodes en
nostra Trie i per a cada paraula en el

111
00:06:21,960 --> 00:06:26,810
diccionari, fins que finalment arribem c
és igual a EOF, en aquest cas, trenquem

112
00:06:26,810 --> 00:06:28,100
fora de l'arxiu.

113
00:06:28,100 --> 00:06:31,110
Ara, hi ha dos casos en virtut
que podríem haver colpejat EOF.

114
00:06:31,110 --> 00:06:35,680
La primera és si hi va haver un error
llegint l'arxiu, així que si hi havia

115
00:06:35,680 --> 00:06:39,280
un error, hem de fer la típica
descarregar tot, tancar l'arxiu,

116
00:06:39,280 --> 00:06:40,520
tornarà False.

117
00:06:40,520 --> 00:06:43,870
Suposant que no era un error, que
simplement vol dir que realment va colpejar el final de

118
00:06:43,870 --> 00:06:47,820
l'arxiu, en aquest cas, es tanca el
presentar i tornar True, ja que

119
00:06:47,820 --> 00:06:51,010
carregat amb èxit el diccionari
en la nostra Trie.

120
00:06:51,010 --> 00:06:54,240
>> Molt bé, així que ara anem a
Pagament Pagament.

121
00:06:54,240 --> 00:06:58,780
Quant a la funció de comprovació, veiem
Comprovar que es va a tornar un Bool.

122
00:06:58,780 --> 00:07:03,740
Retorna True si aquesta paraula que és
que passa és en la nostra Trie.

123
00:07:03,740 --> 00:07:06,170
Retorna False en cas contrari.

124
00:07:06,170 --> 00:07:10,110
>> Llavors, com anem a determinar si
aquesta paraula és en la nostra Trie?

125
00:07:10,110 --> 00:07:14,270
Veiem aquí que, igual que abans,
farem servir el cursor per iterar

126
00:07:14,270 --> 00:07:16,010
a través del nostre Trie.

127
00:07:16,010 --> 00:07:20,650
Ara, aquí, repetirem
llarg de tota la nostra paraula.

128
00:07:20,650 --> 00:07:24,680
Així iteració en la paraula som
passat, anem a determinar la

129
00:07:24,680 --> 00:07:29,280
índex en la matriu nens que
correspon al suport de la paraula i.

130
00:07:29,280 --> 00:07:34,150
Així que això serà exactament com
Càrrega, en la qual si el suport paraula i és un

131
00:07:34,150 --> 00:07:38,110
apòstrof, llavors volem utilitzar l'índex
alfabet menys 1 perquè vam determinar

132
00:07:38,110 --> 00:07:41,160
aquí és on anem
per emmagatzemar apòstrofs.

133
00:07:41,160 --> 00:07:44,440
>> Else utilitzarem tolower
suport de la paraula i.

134
00:07:44,440 --> 00:07:48,270
Així que recordi que la paraula pot tenir arbitrària
capitalització, per la qual cosa

135
00:07:48,270 --> 00:07:51,590
voldrà assegurar-se que estem utilitzant
una versió en minúscules de les coses.

136
00:07:51,590 --> 00:07:55,300
I després restar d'aquesta minúscula
a per, un cop més, ens la donarà

137
00:07:55,300 --> 00:07:57,940
posició alfabètic
d'aquest caràcter.

138
00:07:57,940 --> 00:08:01,740
Així que serà el nostre índex
en la matriu de la Infància.

139
00:08:01,740 --> 00:08:06,480
>> I ara, si aquest índex en els nens
matriu és nul, això significa que

140
00:08:06,480 --> 00:08:09,050
ja no pot continuar la iteració
baixar la Trie.

141
00:08:09,050 --> 00:08:13,320
Si aquest és el cas, aquesta paraula no pot
possiblement estar en la nostra Trie, ja que si

142
00:08:13,320 --> 00:08:18,000
van ser, això significaria que hi hauria una
ruta d'accés a aquesta paraula, i ho faria

143
00:08:18,000 --> 00:08:19,350
Mai trobada nul.

144
00:08:19,350 --> 00:08:21,910
Així que trobar nul, tornem Fals.

145
00:08:21,910 --> 00:08:23,810
La paraula no és al diccionari.

146
00:08:23,810 --> 00:08:28,200
Si no fos nul, llavors anem a
continuar la iteració, pel que anem

147
00:08:28,200 --> 00:08:33,150
actualitzar el nostre cursor per assenyalar que
en particular node en aquest índex.

148
00:08:33,150 --> 00:08:36,659
>> Així que seguim fent que al llarg
la paraula sencera.

149
00:08:36,659 --> 00:08:40,630
Suposant que mai colpegem nul, que els mitjans
hem estat capaços d'obtenir a través de la totalitat de

150
00:08:40,630 --> 00:08:44,840
món i trobar un node a la nostra Trie,
però no hem acabat encara.

151
00:08:44,840 --> 00:08:46,350
No volem simplement tornar True.

152
00:08:46,350 --> 00:08:51,400
Volem tornar Paraula d'error cursor
des de llavors, recordar de nou, si el gat no és

153
00:08:51,400 --> 00:08:55,140
en el diccionari i la catàstrofe és,
llavors anem a aconseguir amb èxit a través de

154
00:08:55,140 --> 00:08:59,810
la paraula gat, però la paraula cursor
serà falsa i no és cert.

155
00:08:59,810 --> 00:09:04,990
Així que tornem cursor paraula per indicar
si aquest node és en realitat una paraula,

156
00:09:04,990 --> 00:09:06,530
i això és tot per xec.

157
00:09:06,530 --> 00:09:08,310
>> Així que anem a veure Mida.

158
00:09:08,310 --> 00:09:11,410
Així Mida serà bastant fàcil
ja que, recorda, en càrrega, estem

159
00:09:11,410 --> 00:09:15,480
incrementant la mida del diccionari per
cada paraula que ens trobem.

160
00:09:15,480 --> 00:09:20,820
Així Mida és només tornarà
mida del diccionari, i això és tot.

161
00:09:20,820 --> 00:09:24,650
>> Molt bé, així que, finalment, tenim a Baixa.

162
00:09:24,650 --> 00:09:29,050
Així Unload, anem a utilitzar una
funció recursiva per fer realitat tots

163
00:09:29,050 --> 00:09:33,390
part del treball per nosaltres, pel que la nostra funció
es va a cridar Descarregador.

164
00:09:33,390 --> 00:09:35,830
Què està Descarregador farem?

165
00:09:35,830 --> 00:09:40,640
Veiem aquí que Descarregador va a
iterar sobre tots els infants en

166
00:09:40,640 --> 00:09:45,810
aquest node particular, i si el nen
node no és nul, llavors anem a

167
00:09:45,810 --> 00:09:47,760
descarregar el node secundari.

168
00:09:47,760 --> 00:09:52,070
>> Així que això va a forma recursiva
descarregar tots els nostres nens.

169
00:09:52,070 --> 00:09:55,140
Quan estiguem segurs que tots els nostres nens
s'han descarregat, llavors

170
00:09:55,140 --> 00:09:58,830
pot alliberar-nos, per descarregar a nosaltres mateixos.

171
00:09:58,830 --> 00:10:04,550
Així que aquest serà de forma recursiva descarregar el
tota Trie i, a continuació, una vegada que és

172
00:10:04,550 --> 00:10:06,910
fet, només podem tornar True.

173
00:10:06,910 --> 00:10:09,770
Unload no pot fallar, estem
simplement alliberant coses.

174
00:10:09,770 --> 00:10:12,985
Així que un cop haguem acabat alliberant
tot, tornar TRUE.

175
00:10:12,985 --> 00:10:14,380
I això és tot.

176
00:10:14,380 --> 00:10:16,792
El meu nom és Rob, i això
va ser [inaudible].

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