1
00:00:00,000 --> 00:00:12,350
>> [Speel van musiek]

2
00:00:12,350 --> 00:00:13,050
>> ROB BOWDEN: Hi.

3
00:00:13,050 --> 00:00:13,640
Ek is Rob.

4
00:00:13,640 --> 00:00:16,210
En laat ons hierdie oplossing uit.

5
00:00:16,210 --> 00:00:20,070
So hier gaan ons te implementeer
'n algemene tafel.

6
00:00:20,070 --> 00:00:24,090
Ons sien dat die struct knoop van ons
tafel gaan lyk soos hierdie.

7
00:00:24,090 --> 00:00:28,710
So dit gaan 'n kar woord te hê
verskeidenheid van grootte lengte + 1.

8
00:00:28,710 --> 00:00:32,259
Moenie vergeet om die + 1, aangesien die maksimum
woord in die woordeboek is 45

9
00:00:32,259 --> 00:00:33,130
karakters.

10
00:00:33,130 --> 00:00:37,070
En dan gaan ons moet 'n ekstra
karakter vir die backslash nul.

11
00:00:37,070 --> 00:00:40,870
>> En dan is ons hashtable in elke
emmer gaan slaan 'n

12
00:00:40,870 --> 00:00:42,320
gekoppel lys van nodes.

13
00:00:42,320 --> 00:00:44,420
Ons doen nie lineêre indringende hier.

14
00:00:44,420 --> 00:00:48,430
En so in orde om te skakel na die volgende
element in die emmer, moet ons 'n

15
00:00:48,430 --> 00:00:50,390
struct knoop * volgende.

16
00:00:50,390 --> 00:00:51,110
OK.

17
00:00:51,110 --> 00:00:53,090
So dit is wat 'n knoop lyk.

18
00:00:53,090 --> 00:00:56,180
>> Nou hier is die verklaring
van ons hashtable.

19
00:00:56,180 --> 00:00:59,640
Dit gaan 16834 emmers te hê.

20
00:00:59,640 --> 00:01:01,910
Maar dat die getal nie regtig saak nie.

21
00:01:01,910 --> 00:01:05,450
En ten slotte, gaan ons die
globale veranderlike hashtable grootte, wat

22
00:01:05,450 --> 00:01:07,000
gaan begin af as nul.

23
00:01:07,000 --> 00:01:10,760
En dit gaan die spoor van hoe om te hou
baie woorde in ons woordeboek.

24
00:01:10,760 --> 00:01:13,710
>> So kom ons neem 'n blik op las.

25
00:01:13,710 --> 00:01:16,390
Let daarop dat die las is dit gee 'n Bool.

26
00:01:16,390 --> 00:01:20,530
Jy terugkeer waar as dit was suksesvol
gelaai en valse anders.

27
00:01:20,530 --> 00:01:23,990
En dit neem 'n konst kar * woordeboek,
wat is die woordeboek

28
00:01:23,990 --> 00:01:25,280
dat ons wil oopmaak.

29
00:01:25,280 --> 00:01:27,170
So wat is die eerste ding wat
ons gaan doen.

30
00:01:27,170 --> 00:01:29,500
>> Ons gaan fopen die
woordeboek vir lees.

31
00:01:29,500 --> 00:01:31,680
En ons gaan hê om te maak
seker te maak dat dit daarin geslaag.

32
00:01:31,680 --> 00:01:35,920
So as dit terug NULL, dan is ons het nie
die woordeboek suksesvol oop te maak.

33
00:01:35,920 --> 00:01:37,440
En ons moet valse om terug te keer.

34
00:01:37,440 --> 00:01:41,580
Maar die veronderstelling dat dit suksesvol gedoen
oop, dan wil ons om te lees die

35
00:01:41,580 --> 00:01:42,400
woordeboek.

36
00:01:42,400 --> 00:01:46,450
So hou herhaling totdat ons 'n paar
rede om te breek uit hierdie lus,

37
00:01:46,450 --> 00:01:47,570
wat ons sal sien.

38
00:01:47,570 --> 00:01:48,920
So hou herhaling.

39
00:01:48,920 --> 00:01:51,780
>> En nou is ons gaan
malloc 'n enkele nodus.

40
00:01:51,780 --> 00:01:54,020
En natuurlik moet ons
te lug weer na te gaan.

41
00:01:54,020 --> 00:01:58,680
So as mallocing nie slaag nie, dan
Ons wil 'n knoop wat ons af te laai

42
00:01:58,680 --> 00:02:02,590
gebeur malloc voor, sluit die
woordeboek en terugkeer onwaar.

43
00:02:02,590 --> 00:02:06,830
Maar ignoreer dat die aanvaarding van ons
geslaag het, dan wil ons gebruik fscanf

44
00:02:06,830 --> 00:02:12,400
'n enkele woord uit te lees ons
woordeboek in ons node.

45
00:02:12,400 --> 00:02:17,940
So onthou dat inskrywing> woord is die kar
woord buffer grootte LENGHTH + 1

46
00:02:17,940 --> 00:02:20,300
dat ons gaan om die woord te stoor in

47
00:02:20,300 --> 00:02:25,070
>> So fscanf gaan terug 1, solank
soos dit was in staat om suksesvol te

48
00:02:25,070 --> 00:02:26,750
lees 'n woord van die lêer.

49
00:02:26,750 --> 00:02:30,460
As óf 'n fout gebeur, of ons
bereik die einde van die lêer, is dit

50
00:02:30,460 --> 00:02:31,950
sal nie terugkeer 1.

51
00:02:31,950 --> 00:02:35,180
In welke geval dit nie terug 1,
ons uiteindelik gaan om te breek uit

52
00:02:35,180 --> 00:02:37,280
dit terwyl loop.

53
00:02:37,280 --> 00:02:42,770
So sien ons dat wanneer ons suksesvol
lees 'n woord in

54
00:02:42,770 --> 00:02:48,270
inskrywing> woord, dan gaan ons wat
woord met behulp van ons hash funksie.

55
00:02:48,270 --> 00:02:49,580
>> Kom ons neem 'n blik op
die hash funksie.

56
00:02:49,580 --> 00:02:52,430

57
00:02:52,430 --> 00:02:55,610
Sodat jy nie regtig nodig het nie
om dit te verstaan.

58
00:02:55,610 --> 00:02:59,460
En eintlik het ons net hierdie hash getrek
funksioneer van die internet.

59
00:02:59,460 --> 00:03:04,010
Die enigste ding wat jy nodig het om te erken, is
dat dit neem om 'n konst kar * woord.

60
00:03:04,010 --> 00:03:08,960
So dit is wat 'n string as invoer, en
terugkeer van 'n unsigned int as uitset.

61
00:03:08,960 --> 00:03:12,360
So dit is al wat 'n hash funksie is, is dit
neem in 'n invoer en gee jou 'n

62
00:03:12,360 --> 00:03:14,490
indeks in die hashtable.

63
00:03:14,490 --> 00:03:18,530
>> Let daarop dat ons moding deur NUM_BUCKETS,
sodat waarde wat

64
00:03:18,530 --> 00:03:21,730
eintlik is 'n indeks in die hashtable
en nie verder as die indeks

65
00:03:21,730 --> 00:03:24,320
grense van die skikking.

66
00:03:24,320 --> 00:03:28,060
So gegee dat funksie, ons gaan
die woord wat ons lees te hash die

67
00:03:28,060 --> 00:03:29,390
woordeboek.

68
00:03:29,390 --> 00:03:31,700
En dan gaan ons om te gebruik
dat hash te voeg die

69
00:03:31,700 --> 00:03:33,750
toetrede tot die hashtable.

70
00:03:33,750 --> 00:03:38,520
>> Nou hashtable hash is die huidige
geskakelde lys in die tabel.

71
00:03:38,520 --> 00:03:41,410
En dit is baie moontlik
dat dit net 'NULL.

72
00:03:41,410 --> 00:03:44,960
Ons wil ons inskrywing aan die te voeg
begin van hierdie geskakelde lys.

73
00:03:44,960 --> 00:03:48,600
En so gaan ons ons huidige te hê
inskrywing punt wat die hashtable

74
00:03:48,600 --> 00:03:50,380
tans dui op.

75
00:03:50,380 --> 00:03:53,310
En dan gaan ons te slaan,
in die hashtable by die

76
00:03:53,310 --> 00:03:55,350
hash, die huidige inskrywing.

77
00:03:55,350 --> 00:03:59,320
So het hierdie twee lyne suksesvol voeg
die inskrywing aan die begin van die

78
00:03:59,320 --> 00:04:02,260
gekoppel lys op daardie indeks
in die hashtable.

79
00:04:02,260 --> 00:04:04,900
>> Sodra ons klaar is met dit, ons weet
dat ons het 'n ander woord in die

80
00:04:04,900 --> 00:04:07,790
woordeboek, en ons inkrementeer weer.

81
00:04:07,790 --> 00:04:13,960
So ons hou om dit te doen totdat fscanf
uiteindelik terug iets nie-1 by

82
00:04:13,960 --> 00:04:16,950
watter punt onthou dat
Ons moet toegang te bevry.

83
00:04:16,950 --> 00:04:19,459
So hier is ons malloced 'n inskrywing.

84
00:04:19,459 --> 00:04:21,329
En ons probeer om iets te lees
van die woordeboek.

85
00:04:21,329 --> 00:04:23,910
En ons het nie suksesvol gelees
iets uit die woordeboek, in

86
00:04:23,910 --> 00:04:26,650
welke geval ons moet die inskrywing te bevry
dat ons nooit eintlik sit in die

87
00:04:26,650 --> 00:04:29,140
hashtable, en uiteindelik breek.

88
00:04:29,140 --> 00:04:32,750
>> Sodra ons breek ons ​​nodig het om te sien, wel,
het ons breek, want daar

89
00:04:32,750 --> 00:04:34,360
is 'n fout met die lees van die lêer?

90
00:04:34,360 --> 00:04:37,120
Of het ons breek, want ons
bereik die einde van die lêer?

91
00:04:37,120 --> 00:04:39,480
As daar 'n fout is, dan
ons wil vals om terug te keer.

92
00:04:39,480 --> 00:04:40,930
Omdat vrag nie slaag nie.

93
00:04:40,930 --> 00:04:43,890
En in die proses het ons wil om af te laai
al die woorde wat ons lees in, en

94
00:04:43,890 --> 00:04:45,670
sluit die woordeboek lêer.

95
00:04:45,670 --> 00:04:48,740
>> Veronderstelling ons het daarin slaag, dan het ons net
nog steeds nodig om die woordeboek te sluit

96
00:04:48,740 --> 00:04:53,040
dien, en uiteindelik terug te keer waar nie, aangesien ons
die woordeboek suksesvol gelaai.

97
00:04:53,040 --> 00:04:54,420
En dit is dit vir vrag.

98
00:04:54,420 --> 00:04:59,020
So nou gaan, gegee 'n gelaaide hashtable,
gaan om te kyk soos hierdie.

99
00:04:59,020 --> 00:05:03,140
So gaan, dit gee 'n Bool, wat
gaan om aan te dui of die geslaag

100
00:05:03,140 --> 00:05:07,530
in kar * woord, of die geslaag
in string is in ons woordeboek.

101
00:05:07,530 --> 00:05:09,890
So indien dit in die woordeboek,
As dit is in ons hashtable,

102
00:05:09,890 --> 00:05:11,170
Ons sal terugkeer waar.

103
00:05:11,170 --> 00:05:13,380
En as dit is nie, sal ons terugkeer onwaar.

104
00:05:13,380 --> 00:05:17,740
>> Gegee in woord hierdie geslaag het, is ons
gaan om die woord te hash.

105
00:05:17,740 --> 00:05:22,110
Nou 'n belangrike ding om te besef is
wat in die las ons het geweet dat al die

106
00:05:22,110 --> 00:05:23,820
woorde ons gaan laer geval te wees.

107
00:05:23,820 --> 00:05:25,820
Maar hier is ons nie so seker nie.

108
00:05:25,820 --> 00:05:29,510
As ons neem 'n blik op ons hash funksie,
ons hash funksie eintlik

109
00:05:29,510 --> 00:05:32,700
laer omhulsel elke karakter
van die woord.

110
00:05:32,700 --> 00:05:37,940
So, ongeag van die kapitalisasie van
woord, ons hash funksie is om die opbrengs

111
00:05:37,940 --> 00:05:42,270
dieselfde indeks vir wat ook al die
kapitalisasie is, as dit sou hê

112
00:05:42,270 --> 00:05:45,280
terug vir 'n heeltemal klein
weergawe van die woord.

113
00:05:45,280 --> 00:05:46,600
Goed.

114
00:05:46,600 --> 00:05:49,790
Dit is die indeks is in die
hashtable vir hierdie woord.

115
00:05:49,790 --> 00:05:52,940
>> Nou is dit vir lus gaan
Itereer oor die geskakelde lys

116
00:05:52,940 --> 00:05:55,000
Dit was op daardie indeks.

117
00:05:55,000 --> 00:05:59,610
So sien ons initializing inskrywing
om aan te dui dat die indeks.

118
00:05:59,610 --> 00:06:02,750
Ons gaan om voort te gaan
terwyl inskrywing! = NULL.

119
00:06:02,750 --> 00:06:07,770
En onthou dat die opdatering van die wyser
in ons gekoppel lys entry = entry> volgende.

120
00:06:07,770 --> 00:06:14,400
So het ons huidige inskrywing punt te
die volgende item in die geskakelde lys.

121
00:06:14,400 --> 00:06:19,250
>> So vir elke inskrywing in die geskakelde lys,
ons gaan strcasecmp te gebruik.

122
00:06:19,250 --> 00:06:20,330
Dit is nie strcomp.

123
00:06:20,330 --> 00:06:23,780
Omdat weer, ons wil
doen dinge geval insensitively.

124
00:06:23,780 --> 00:06:27,870
So gebruik ons ​​strcasecmp te vergelyk
woord wat deur middel van hierdie geslaag is

125
00:06:27,870 --> 00:06:31,860
funksie teen die woord
Dit is in hierdie inskrywing.

126
00:06:31,860 --> 00:06:35,570
As dit terugkeer nul, wat beteken dat daar
'n wedstryd, in welke geval ons wil

127
00:06:35,570 --> 00:06:36,630
terug waar.

128
00:06:36,630 --> 00:06:39,590
Ons het met sukses het die
woord in ons hashtable.

129
00:06:39,590 --> 00:06:43,040
>> As daar nie 'n wedstryd, dan is ons
gaan loop weer en kyk na die

130
00:06:43,040 --> 00:06:43,990
volgende inskrywing.

131
00:06:43,990 --> 00:06:47,640
En ons sal voortgaan om herhaling terwyl daar
is inskrywings in hierdie verband lys.

132
00:06:47,640 --> 00:06:50,160
Wat gebeur as ons breek
uit hierdie lus?

133
00:06:50,160 --> 00:06:55,110
Dit beteken dat ons nie 'n inskrywing te vind dat
ooreenstem met hierdie woord, in welke geval

134
00:06:55,110 --> 00:07:00,220
ons terugkeer valse aan te dui dat ons
hashtable het nie hierdie woord bevat.

135
00:07:00,220 --> 00:07:02,540
En dit is 'n tjek.

136
00:07:02,540 --> 00:07:04,790
>> So kom ons neem 'n blik op die grootte.

137
00:07:04,790 --> 00:07:06,970
Nou grootte gaan wees eenvoudig.

138
00:07:06,970 --> 00:07:11,080
Sedert onthou in las, vir elke woord
ons gevind het, het ons geinkrementeer 'n globale

139
00:07:11,080 --> 00:07:12,880
veranderlike hashtable grootte.

140
00:07:12,880 --> 00:07:16,480
So het die grootte funksie is net gaan
globale veranderlike om terug te keer.

141
00:07:16,480 --> 00:07:18,150
En dit is dit.

142
00:07:18,150 --> 00:07:22,300
>> Nou uiteindelik, moet ons los die
woordeboek sodra alles is gedoen.

143
00:07:22,300 --> 00:07:25,340
So hoe gaan ons dit doen?

144
00:07:25,340 --> 00:07:30,440
Right hier is ons herhaling oor
al emmers ons tafel.

145
00:07:30,440 --> 00:07:33,240
So is daar NUM_BUCKETS emmers.

146
00:07:33,240 --> 00:07:37,410
En vir elke gekoppel lys in ons
hashtable, gaan ons lus oor

147
00:07:37,410 --> 00:07:41,070
die geheel van die geskakelde lys,
bevry elke element.

148
00:07:41,070 --> 00:07:42,900
>> Nou moet ons versigtig wees.

149
00:07:42,900 --> 00:07:47,910
So hier het ons 'n tydelike veranderlike
dit is die stoor van die wyser na die volgende

150
00:07:47,910 --> 00:07:49,730
element in die geskakelde lys.

151
00:07:49,730 --> 00:07:52,140
En dan gaan ons vry
Die huidige element.

152
00:07:52,140 --> 00:07:55,990
Ons moet seker maak ons ​​doen dit omdat ons wees
kan nie net vry om die huidige element

153
00:07:55,990 --> 00:07:59,180
en probeer dan die volgende wyser om toegang te verkry,
sedert wanneer het ons bevry het,

154
00:07:59,180 --> 00:08:00,870
die geheue ongeldig.

155
00:08:00,870 --> 00:08:04,990
>> Dus moet ons om 'n wyser te hou
die volgende element, dan kan ons bevry van die

156
00:08:04,990 --> 00:08:08,360
huidige element, en dan kan ons werk
ons huidige element om aan te dui

157
00:08:08,360 --> 00:08:09,550
die volgende element.

158
00:08:09,550 --> 00:08:12,800
Ons sal loop, terwyl daar is elemente
in hierdie verband lys.

159
00:08:12,800 --> 00:08:15,620
Ons sal doen wat vir alle gekoppelde
lyste in die hashtable.

160
00:08:15,620 --> 00:08:19,460
En sodra ons klaar is met wat ons het
heeltemal gelaai is die hashtable, en

161
00:08:19,460 --> 00:08:20,190
ons gedoen het.

162
00:08:20,190 --> 00:08:23,200
Dus is dit onmoontlik vir, aflaai
ooit vals terugkeer.

163
00:08:23,200 --> 00:08:26,470
En wanneer ons klaar is, het ons
net terug waar.

164
00:08:26,470 --> 00:08:29,000
>> Kom ons gee hierdie oplossing 'n drie.

165
00:08:29,000 --> 00:08:33,070
So laat ons 'n blik op wat ons
struct knoop sal lyk.

166
00:08:33,070 --> 00:08:36,220
Hier sien ons ons gaan 'n Bool te hê
woord en 'n struct knoop * kinders

167
00:08:36,220 --> 00:08:37,470
bracket alfabet is.

168
00:08:37,470 --> 00:08:38,929

169
00:08:38,929 --> 00:08:42,020
Dus is die eerste ding wat jy kan wees
wonder, hoekom is ALPHABET

170
00:08:42,020 --> 00:08:44,660
ed gedefinieer as 27?

171
00:08:44,660 --> 00:08:47,900
Wel, onthou dat ons gaan nodig
word die hantering van die toespraak.

172
00:08:47,900 --> 00:08:51,910
So wat gaan 'n bietjie van 'n
spesiale geval in hierdie program.

173
00:08:51,910 --> 00:08:54,710
>> Onthou nou hoe 'n tydstip waarop
eintlik werk.

174
00:08:54,710 --> 00:08:59,380
Kom ons sê dat ons die woord is kruip
"Katte." Dan uit die wortel van die Trie,

175
00:08:59,380 --> 00:09:02,610
ons gaan om te kyk na die kinders
skikking, en ons gaan om te kyk na die

176
00:09:02,610 --> 00:09:08,090
indeks wat ooreenstem met die letter
C. So wat geïndekseer sal word 2.

177
00:09:08,090 --> 00:09:11,530
So gegee dat, dit sal
gee ons 'n nuwe knoop.

178
00:09:11,530 --> 00:09:13,820
En dan sal ons die werk van die knoop.

179
00:09:13,820 --> 00:09:17,770
>> So gegee dat knoop, ons is weer
gaan om te kyk na die kinders skikking.

180
00:09:17,770 --> 00:09:22,110
En ons gaan om te kyk na indeks nul
ooreenstem met die A in kat.

181
00:09:22,110 --> 00:09:27,170
So dan gaan ons na daardie knoop,
en gegee dat node ons gaan

182
00:09:27,170 --> 00:09:31,090
om te kyk na die ou end is dit 'n ooreenstem
T. en beweeg na die knoop,

183
00:09:31,090 --> 00:09:35,530
Ten slotte, ons het heeltemal gelyk
deur middel van ons woord "kat." En nou Bool

184
00:09:35,530 --> 00:09:40,960
woord is veronderstel om aan te dui of
hierdie gegewe woord is eintlik 'n woord.

185
00:09:40,960 --> 00:09:43,470
>> So hoekom moet ons daardie spesiale geval?

186
00:09:43,470 --> 00:09:47,700
Wel, wat van die woord "katastrofe"
is in ons woordeboek, maar die

187
00:09:47,700 --> 00:09:50,150
woord "kat" is nie?

188
00:09:50,150 --> 00:09:54,580
So en soek om te sien of die woord "kat"
is in ons woordeboek, ons is

189
00:09:54,580 --> 00:09:59,970
gaan om suksesvol te kyk deur
die indekse C-A-T in streek-knoop.

190
00:09:59,970 --> 00:10:04,290
Maar dit is net omdat katastrofe
gebeur nodes op die pad te skep

191
00:10:04,290 --> 00:10:07,190
van C-A-T, al die pad na
die einde van die woord.

192
00:10:07,190 --> 00:10:12,020
So Bool woord word gebruik om aan te dui of
hierdie spesifieke plek

193
00:10:12,020 --> 00:10:14,310
eintlik dui op 'n woord.

194
00:10:14,310 --> 00:10:15,140
>> Alle regte.

195
00:10:15,140 --> 00:10:19,310
So nou dat ons weet wat dit is Trie
gaan lyk, laat ons kyk na die

196
00:10:19,310 --> 00:10:20,730
laai funksie.

197
00:10:20,730 --> 00:10:24,610
So vrag gaan 'n Bool om terug te keer
Want as ons suksesvol of

198
00:10:24,610 --> 00:10:26,720
onsuksesvol gelaai die woordeboek.

199
00:10:26,720 --> 00:10:30,460
En dit gaan die woordeboek te wees
wat ons wil om te laai.

200
00:10:30,460 --> 00:10:33,930
>> So die eerste ding wat ons moet doen, is om oop
up dat woordeboek vir lees.

201
00:10:33,930 --> 00:10:36,160
En ons het om seker te maak
ons het nie misluk nie.

202
00:10:36,160 --> 00:10:39,580
So as die woordeboek was nie
suksesvol oopgemaak word, sal dit terugkeer

203
00:10:39,580 --> 00:10:42,400
nul, in welke geval ons is
gaan valse om terug te keer.

204
00:10:42,400 --> 00:10:47,230
Maar die veronderstelling dat dit suksesvol
oopgemaak het, dan kan ons eintlik lees

205
00:10:47,230 --> 00:10:48,220
deur die woordeboek.

206
00:10:48,220 --> 00:10:50,880
>> So die eerste ding wat ons gaan
wil doen, is ons hierdie

207
00:10:50,880 --> 00:10:52,500
globale veranderlike wortel.

208
00:10:52,500 --> 00:10:56,190
Nou wortel gaan 'n knoop te wees *.

209
00:10:56,190 --> 00:10:59,760
Dit is die top van ons Trie dat ons
gaan word iterating deur.

210
00:10:59,760 --> 00:11:02,660
Dus is die eerste ding wat ons gaan
te wil doen, is die toekenning

211
00:11:02,660 --> 00:11:04,140
geheue vir ons wortel.

212
00:11:04,140 --> 00:11:07,980
Let daarop dat ons met behulp van die calloc
funksie, wat is basies dieselfde

213
00:11:07,980 --> 00:11:11,500
as die malloc funksie nie, behalwe dit is
gewaarborg iets wat om terug te keer

214
00:11:11,500 --> 00:11:13,180
heeltemal zeroed uit.

215
00:11:13,180 --> 00:11:17,290
So as ons gebruik malloc, sou ons nodig het om te
gaan deur al die verwysings in ons

216
00:11:17,290 --> 00:11:20,160
knoop, en maak seker dat
hulle is almal null.

217
00:11:20,160 --> 00:11:22,710
So calloc sal dit doen vir ons.

218
00:11:22,710 --> 00:11:26,330
>> Nou net soos malloc, het ons nodig het om te maak
seker te maak dat die toekenning was eintlik

219
00:11:26,330 --> 00:11:27,520
suksesvol.

220
00:11:27,520 --> 00:11:29,990
As dit teruggekeer null, dan het ons
nodig het om te sluit of 'n woordeboek

221
00:11:29,990 --> 00:11:32,100
lêer en terugkeer onwaar.

222
00:11:32,100 --> 00:11:36,835
So die veronderstelling dat die toekenning is
suksesvol is, gaan ons 'n knoop te gebruik *

223
00:11:36,835 --> 00:11:40,270
wyser na Itereer deur ons Trie.

224
00:11:40,270 --> 00:11:43,890
So ons wortels gaan nooit verander nie,
maar ons gaan wyser te gebruik om te

225
00:11:43,890 --> 00:11:47,875
eintlik gaan van knoop tot knoop.

226
00:11:47,875 --> 00:11:50,940
>> So in hierdie lus vir ons lees
deur die woordeboek lêer.

227
00:11:50,940 --> 00:11:53,670
En ons gebruik fgetc.

228
00:11:53,670 --> 00:11:56,290
Fgetc gaan 'n enkele te gryp
karakter van die lêer.

229
00:11:56,290 --> 00:11:59,370
Ons gaan om voort te gaan gryp
karakters terwyl ons bereik nie die

230
00:11:59,370 --> 00:12:01,570
einde van die lêer.

231
00:12:01,570 --> 00:12:03,480
>> Daar is twee gevalle het ons nodig het om te hanteer.

232
00:12:03,480 --> 00:12:06,610
Die eerste, as die karakter
was nie 'n nuwe reël.

233
00:12:06,610 --> 00:12:10,450
So ons weet of dit 'n nuwe lyn, dan
ons is oor te skuif na 'n nuwe woord.

234
00:12:10,450 --> 00:12:15,240
Maar die veronderstelling dat dit was nie 'n nuwe lyn, dan
Hier wil ons om uit te vind die

235
00:12:15,240 --> 00:12:18,380
indeks gaan ons na die indeks in
in die kinders skikking wat

236
00:12:18,380 --> 00:12:19,810
Ons kyk na voor.

237
00:12:19,810 --> 00:12:23,880
>> So, soos ek gesê het, moet ons
spesiale geval die toespraak.

238
00:12:23,880 --> 00:12:26,220
Let ons die gebruik van die drieledige
operateur hier.

239
00:12:26,220 --> 00:12:29,580
So ons gaan om dit te lees as, indien
die karakter lees ons in was 'n

240
00:12:29,580 --> 00:12:35,330
toespraak, dan gaan ons te stel
indeks = "ALPHABET" -1, wat sal

241
00:12:35,330 --> 00:12:37,680
wees om die indeks 26.

242
00:12:37,680 --> 00:12:41,130
>> Anders, as dit nie was 'n toespraak, is daar
ons gaan die indeks op te stel

243
00:12:41,130 --> 00:12:43,760
gelyk aan c - a.

244
00:12:43,760 --> 00:12:49,030
So onthou terug uit voorheen p-stelle,
c - a gaan ons die te gee

245
00:12:49,030 --> 00:12:53,410
alfabetiese posisie van C. So as
C is die letter A, dit sal

246
00:12:53,410 --> 00:12:54,700
gee ons indeks nul.

247
00:12:54,700 --> 00:12:58,120
Vir die letter B, sal dit gee
ons die indeks 1, en so aan.

248
00:12:58,120 --> 00:13:03,010
>> So dit gee ons die indeks in die
kinders skikking wat ons wil hê.

249
00:13:03,010 --> 00:13:08,890
Nou as die indeks is tans nul in
die kinders, wat beteken dat 'n knoop

250
00:13:08,890 --> 00:13:11,830
nie tans bestaan
uit daardie pad.

251
00:13:11,830 --> 00:13:15,160
So het ons nodig het om te ken
'n knoop vir die pad.

252
00:13:15,160 --> 00:13:16,550
Dit is wat ons hier sal doen.

253
00:13:16,550 --> 00:13:20,690
>> So ons gaan weer die calloc
funksie, sodat ons nie hoef te

254
00:13:20,690 --> 00:13:22,880
nul al die wysers.

255
00:13:22,880 --> 00:13:27,240
En ons weer moet kyk
dat calloc het nie misluk nie.

256
00:13:27,240 --> 00:13:30,700
As calloc het misluk, dan moet ons
om alles te los, sluit ons

257
00:13:30,700 --> 00:13:32,820
woordeboek, en terug onwaar.

258
00:13:32,820 --> 00:13:40,050
So die veronderstelling dat dit nie slaag nie, dan
dit sal 'n nuwe kind skep vir ons.

259
00:13:40,050 --> 00:13:41,930
En dan gaan ons na die kind.

260
00:13:41,930 --> 00:13:44,960
Ons wyser sal Itereer
af aan daardie kind.

261
00:13:44,960 --> 00:13:49,330
>> Nou as dit was nie null met om te begin,
dan die wyser kan net Itereer

262
00:13:49,330 --> 00:13:52,590
af aan daardie kind sonder om werklik
om iets te ken.

263
00:13:52,590 --> 00:13:56,730
Dit is die geval waar ons die eerste keer gebeur het
ken die woord "kat." En

264
00:13:56,730 --> 00:14:00,330
Dit beteken dat wanneer ons gaan te ken
"Katastrofe," het ons nie nodig om te skep

265
00:14:00,330 --> 00:14:01,680
nodes vir C-A-T weer.

266
00:14:01,680 --> 00:14:04,830
Hulle het reeds bestaan.

267
00:14:04,830 --> 00:14:06,080
>> Wat is dit anders?

268
00:14:06,080 --> 00:14:10,480
Dit is die toestand waar c was
backslash n, waar c 'n nuwe lyn.

269
00:14:10,480 --> 00:14:13,710
Dit beteken dat ons suksesvol
voltooi 'n woord.

270
00:14:13,710 --> 00:14:16,860
Nou wat wil ons doen wanneer ons
'n woord suksesvol voltooi?

271
00:14:16,860 --> 00:14:21,100
Ons gaan hierdie woord veld te gebruik
binnekant van ons struct knoop.

272
00:14:21,100 --> 00:14:23,390
Ons wil om dit te stel waar.

273
00:14:23,390 --> 00:14:27,150
So wat daarop dui dat hierdie knoop
dui op 'n suksesvolle

274
00:14:27,150 --> 00:14:29,250
woord, 'n werklike woord.

275
00:14:29,250 --> 00:14:30,940
>> Stel nou dat waar.

276
00:14:30,940 --> 00:14:35,150
Ons wil ons wyser te herstel na punt
aan die begin van die Trie weer.

277
00:14:35,150 --> 00:14:40,160
En uiteindelik, inkrementeer ons woordeboek
grootte, aangesien ons het 'n ander werk.

278
00:14:40,160 --> 00:14:43,230
So ons gaan hou om dit te doen,
lees in karakter deur karakter,

279
00:14:43,230 --> 00:14:49,150
die bou van nuwe nodes in ons Trie en
vir elke woord in die woordeboek, totdat

280
00:14:49,150 --> 00:14:54,020
het ons uiteindelik bereik C! = EOF, waarin
geval ons breek van die lêer.

281
00:14:54,020 --> 00:14:57,050
>> Nou is daar twee gevalle onder
wat ons kan EOF getref het.

282
00:14:57,050 --> 00:15:00,980
Die eerste is as daar 'n fout
die lees van die lêer.

283
00:15:00,980 --> 00:15:03,470
So as daar was 'n fout, ons
moet die tipiese te doen.

284
00:15:03,470 --> 00:15:06,460
Los alles, naby
die lêer, terugkeer onwaar.

285
00:15:06,460 --> 00:15:09,810
Veronderstelling daar was nie 'n fout, wat
beteken net ons eintlik getref die einde van

286
00:15:09,810 --> 00:15:13,750
die lêer, in watter geval, ons sluit die
lêer en terugkeer waar nie, aangesien ons

287
00:15:13,750 --> 00:15:17,330
suksesvol gelaai woordeboek
in ons Trie.

288
00:15:17,330 --> 00:15:20,170
>> So nou, laat ons gaan uit check.

289
00:15:20,170 --> 00:15:25,156
Kyk na die tjek funksie, sien ons
daardie tjek gaan 'n Bool om terug te keer.

290
00:15:25,156 --> 00:15:29,680
Dit gee waar as hierdie woord wat dit is
oorgedra is in ons Trie.

291
00:15:29,680 --> 00:15:32,110
Dit gee valse anders.

292
00:15:32,110 --> 00:15:36,050
So hoe gaan jy bepaal of
hierdie woord is in ons Trie?

293
00:15:36,050 --> 00:15:40,190
>> Ons sien hier dat, net soos tevore,
ons gaan wyser te gebruik om Itereer

294
00:15:40,190 --> 00:15:41,970
deur ons Trie.

295
00:15:41,970 --> 00:15:46,600
Nou hier gaan ons Itereer
oor ons hele woord.

296
00:15:46,600 --> 00:15:50,620
So iterating oor die woord wat ons is verby,
ons gaan om te bepaal die

297
00:15:50,620 --> 00:15:56,400
indeks in die kinders skikking wat
ooreenstem met woord bracket I. So hierdie

298
00:15:56,400 --> 00:15:59,670
gaan lyk presies soos
vrag, waar as woord [i]

299
00:15:59,670 --> 00:16:03,310
is 'n toespraak, dan wil ons
indeks "ALPHABET" te gebruik - 1.

300
00:16:03,310 --> 00:16:05,350
Omdat ons bepaal dat
is waar ons gaan te stoor

301
00:16:05,350 --> 00:16:07,100
apostrofes.

302
00:16:07,100 --> 00:16:11,780
>> Anders gaan ons twee onderste woord te gebruik
bracket I. So onthou dat die woord kan

303
00:16:11,780 --> 00:16:13,920
het arbitrêre kapitalisasie.

304
00:16:13,920 --> 00:16:17,540
En so het ons wil om seker te maak dat ons maak
gebruik van 'n klein weergawe van die dinge.

305
00:16:17,540 --> 00:16:21,920
En dan trek uit daardie 'n "een keer
weer gee ons die alfabetiese

306
00:16:21,920 --> 00:16:23,880
posisie van die karakter.

307
00:16:23,880 --> 00:16:27,680
So wat gaan ons indeks te wees
in die kinders skikking.

308
00:16:27,680 --> 00:16:32,420
>> En nou, as die indeks in die kinders
skikking is nul, wat beteken dat ons

309
00:16:32,420 --> 00:16:34,990
kan nie meer voortgaan iterating
down ons Trie.

310
00:16:34,990 --> 00:16:38,870
As dit die geval is, is hierdie woord kan nie
moontlik wees in ons Trie.

311
00:16:38,870 --> 00:16:42,340
Want as dit was, sou dit
beteken dat daar 'n pad wees

312
00:16:42,340 --> 00:16:43,510
af te wat die woord.

313
00:16:43,510 --> 00:16:45,290
En jy sal nooit ontmoet null.

314
00:16:45,290 --> 00:16:47,850
So stuit nul, keer ons terug onwaar.

315
00:16:47,850 --> 00:16:49,840
Die woord is nie in die woordeboek.

316
00:16:49,840 --> 00:16:53,660
As dit nie was nul, dan is ons
gaan iterating om voort te gaan.

317
00:16:53,660 --> 00:16:57,220
>> So ons gaan daar wyser
om te wys op die besondere

318
00:16:57,220 --> 00:16:59,760
knoop op die indeks.

319
00:16:59,760 --> 00:17:03,150
Ons hou doen wat dwarsdeur
die hele woord, in die veronderstelling

320
00:17:03,150 --> 00:17:03,950
ons nooit getref null.

321
00:17:03,950 --> 00:17:07,220
Dit beteken dat ons in staat was om deur te kom
die hele woord en kry

322
00:17:07,220 --> 00:17:08,920
'n knoop in ons probeer.

323
00:17:08,920 --> 00:17:10,770
Maar ons is nog nie heeltemal klaar nie.

324
00:17:10,770 --> 00:17:12,290
>> Ons wil nie net terug waar.

325
00:17:12,290 --> 00:17:14,770
Ons wil wyser> woord om terug te keer.

326
00:17:14,770 --> 00:17:18,980
Sedert onthou weer, is "kat" is nie
in ons woordeboek, en "katastrofe"

327
00:17:18,980 --> 00:17:22,935
is, sal ons suksesvol ons
deur die woord "kat." Maar wyser

328
00:17:22,935 --> 00:17:25,760
woord sal vals en nie waar wees nie.

329
00:17:25,760 --> 00:17:30,930
So ons terugkeer wyser woord aan te dui
of hierdie knoop is eintlik 'n woord.

330
00:17:30,930 --> 00:17:32,470
En dit is dit vir check.

331
00:17:32,470 --> 00:17:34,250
>> So laat ons kyk na die grootte.

332
00:17:34,250 --> 00:17:37,350
So grootte gaan wees redelik maklik
sedert, onthou in vrag, ons is

333
00:17:37,350 --> 00:17:41,430
die verhoog woordeboek grootte vir
elke woord wat ons teëkom.

334
00:17:41,430 --> 00:17:45,350
So grootte is net gaan om te
terug woordeboek grootte.

335
00:17:45,350 --> 00:17:47,390
En dit is dit.

336
00:17:47,390 --> 00:17:50,590
>> So laastens ons los.

337
00:17:50,590 --> 00:17:55,100
So los, gaan ons gebruik om 'n
rekursiewe funksie te eintlik al

338
00:17:55,100 --> 00:17:56,530
van die werk vir ons.

339
00:17:56,530 --> 00:17:59,340
So ons funksie gaan
word 'n beroep op losser.

340
00:17:59,340 --> 00:18:01,650
Wat is losser gaan doen?

341
00:18:01,650 --> 00:18:06,580
Ons sien hier dat losser gaan
Itereer oor al die kinders wat by

342
00:18:06,580 --> 00:18:08,410
hierdie spesifieke knoop.

343
00:18:08,410 --> 00:18:11,750
En as die kind knoop is nie
nul, dan gaan ons

344
00:18:11,750 --> 00:18:13,730
los die kind knoop.

345
00:18:13,730 --> 00:18:18,010
>> So dit is wat jy herhaaldelik los
almal van ons kinders.

346
00:18:18,010 --> 00:18:21,080
Sodra ons is seker dat al ons kinders
is afgelaai het, dan het ons

347
00:18:21,080 --> 00:18:25,210
kan bevry onsself, so
los onsself.

348
00:18:25,210 --> 00:18:29,460
Dit sal rekursief te werk
los die hele Trie.

349
00:18:29,460 --> 00:18:32,850
En dan sodra dit gedoen is,
ons kan net terug waar.

350
00:18:32,850 --> 00:18:34,210
Los nie kan misluk nie.

351
00:18:34,210 --> 00:18:35,710
Ons is net bevry dinge.

352
00:18:35,710 --> 00:18:38,870
So wanneer ons klaar is bevry
alles terug waar.

353
00:18:38,870 --> 00:18:40,320
En dit is dit.

354
00:18:40,320 --> 00:18:41,080
My naam is Rob.

355
00:18:41,080 --> 00:18:42,426
En dit was speller.

356
00:18:42,426 --> 00:18:47,830
>> [Speel van musiek]