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

2
00:00:00,530 --> 00:00:03,070
>> Spreker 1: Kom ons gee
hierdie oplossing 'n drie.

3
00:00:03,070 --> 00:00:07,130
So laat ons 'n blik op wat ons
Struct knoop sal lyk.

4
00:00:07,130 --> 00:00:11,040
Hier sien ons wat ons gaan hê om 'n
Bool Woord en 'n struct knoop ster

5
00:00:11,040 --> 00:00:12,990
Kinders in hakies alfabet.

6
00:00:12,990 --> 00:00:18,720
So die eerste ding wat jy dalk wonder,
Hoekom is alfabet hash gedefinieer as 27?

7
00:00:18,720 --> 00:00:22,540
Wel, onthou dat ons gaan nodig
word die hantering van die toespraak, so

8
00:00:22,540 --> 00:00:25,610
wat gaan om 'n bietjie te wees van 'n spesiale
geval in hierdie program.

9
00:00:25,610 --> 00:00:28,780
>> OK, nou, onthou hoe 'n
Trie eintlik werk.

10
00:00:28,780 --> 00:00:33,420
Kom ons sê ons kruip die woord katte,
dan van die wortel van ons Trie,

11
00:00:33,420 --> 00:00:36,670
ons gaan om te kyk na die kinders
skikking, en ons gaan om te kyk na die

12
00:00:36,670 --> 00:00:42,250
indeks wat ooreenstem met die letter
C. So wat sou indeks twee.

13
00:00:42,250 --> 00:00:46,400
So gegee dat, wat ons sal gee
'n nuwe knoop, en dan sal ons

14
00:00:46,400 --> 00:00:47,880
werk van daardie knoop.

15
00:00:47,880 --> 00:00:51,830
>> So gegee dat knoop, ons is weer
gaan om te kyk na die kinders skikking,

16
00:00:51,830 --> 00:00:56,170
en ons gaan om te kyk na indeks nul
ooreenstem met die A in kat.

17
00:00:56,170 --> 00:01:01,240
So dan gaan ons na daardie knoop,
en gegee dat knoop, gaan ons

18
00:01:01,240 --> 00:01:05,170
om te kyk na die indeks wat ooreenstem
T. en beweeg na die knoop,

19
00:01:05,170 --> 00:01:09,590
Ten slotte, ons het heeltemal gelyk
deur ons woord Cat, en nou Bool

20
00:01:09,590 --> 00:01:15,020
Woord is veronderstel om aan te dui of
hierdie gegewe woord is eintlik 'n woord.

21
00:01:15,020 --> 00:01:17,530
>> So hoekom moet ons daardie spesiale geval?

22
00:01:17,530 --> 00:01:21,680
Wel, wat as die woord ramp
is in ons woordeboek, maar

23
00:01:21,680 --> 00:01:24,120
die woord kat is nie?

24
00:01:24,120 --> 00:01:29,030
So in soek om te sien of die woord kat is
in ons woordeboek, gaan ons

25
00:01:29,030 --> 00:01:34,880
suksesvol te kyk deur die indekse
C-A-T en bereik 'n knoop, maar dit is

26
00:01:34,880 --> 00:01:39,760
net omdat katastrofe gebeur
skep nodes op die pad van C-A-T al

27
00:01:39,760 --> 00:01:41,250
die pad na die einde van die woord.

28
00:01:41,250 --> 00:01:46,520
So Bool woord gebruik word aan te dui of
hierdie spesifieke plek eintlik

29
00:01:46,520 --> 00:01:48,370
dui op 'n woord.

30
00:01:48,370 --> 00:01:52,920
>> Alle reg, nou dat ons weet wat 'n
Trie gaan lyk, laat ons kyk

31
00:01:52,920 --> 00:01:54,800
by die las funksie.

32
00:01:54,800 --> 00:01:58,670
So vrag is gaan 'n Bool om terug te keer
Want as ons suksesvol of

33
00:01:58,670 --> 00:02:03,020
onsuksesvol gelaai woordeboek
Dit gaan die woordeboek te wees

34
00:02:03,020 --> 00:02:04,520
wat ons wil om te laai.

35
00:02:04,520 --> 00:02:08,310
So die eerste ding wat ons gaan doen is oop
up dat woordeboek vir lees.

36
00:02:08,310 --> 00:02:12,060
Ons moet seker maak ons ​​het nie versuim om,
So as die woordeboek was nie

37
00:02:12,060 --> 00:02:15,280
suksesvol oopgemaak word, sal dit terugkeer
Nee, in welke geval ons gaan

38
00:02:15,280 --> 00:02:16,340
terug Vals.

39
00:02:16,340 --> 00:02:21,290
Maar die veronderstelling dat dit suksesvol
oopgemaak het, dan kan ons eintlik lees

40
00:02:21,290 --> 00:02:22,310
deur die woordeboek.

41
00:02:22,310 --> 00:02:24,940
>> So die eerste ding wat ons gaan
wil doen, is ons hierdie

42
00:02:24,940 --> 00:02:26,560
globale veranderlike wortel.

43
00:02:26,560 --> 00:02:30,250
Nou, is die wortel gaan 'n knoop-ster te wees.

44
00:02:30,250 --> 00:02:33,830
Dit is die top van ons Trie dat ons
gaan word iterating deur.

45
00:02:33,830 --> 00:02:38,200
So die eerste ding wat ons gaan om te wil
doen, is om toeken geheue vir ons wortel.

46
00:02:38,200 --> 00:02:42,040
>> Let daarop dat ons met behulp van die Calloc
funksie, wat is basies dieselfde

47
00:02:42,040 --> 00:02:45,560
as die malloc funksie nie, behalwe dit is
gewaarborg iets wat om terug te keer

48
00:02:45,560 --> 00:02:47,240
heeltemal zeroed uit.

49
00:02:47,240 --> 00:02:51,350
So as ons gebruik malloc, sou ons nodig het om te
gaan deur al die verwysings in ons

50
00:02:51,350 --> 00:02:54,220
knoop en maak seker dat
hulle is almal null.

51
00:02:54,220 --> 00:02:56,780
So Calloc sal dit doen vir ons.

52
00:02:56,780 --> 00:03:00,390
>> Nou, net soos malloc, het ons nodig het om te maak
seker te maak dat die toekenning is eintlik

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

54
00:03:01,580 --> 00:03:04,060
As dit teruggekeer null, dan het ons
moet ons woordeboek te sluit

55
00:03:04,060 --> 00:03:06,170
lêer en terug Vals.

56
00:03:06,170 --> 00:03:11,040
So die aanvaarding van die toekenning is
suksesvol is, gaan ons 'n knoop te gebruik

57
00:03:11,040 --> 00:03:14,340
ster wyser te Itereer
deur ons Trie.

58
00:03:14,340 --> 00:03:17,950
So ons wortel gaan nooit verander nie,
maar ons gaan wyser te gebruik om te

59
00:03:17,950 --> 00:03:20,770
eintlik gaan van knoop tot knoop.

60
00:03:20,770 --> 00:03:25,000
>> Alle reg, so in hierdie For-lus, ons is
lees deur die woordeboek lêer,

61
00:03:25,000 --> 00:03:26,965
en ons gebruik by fgetc.

62
00:03:26,965 --> 00:03:30,360
So fgetc gaan 'n enkele te gryp
karakter van die lêer.

63
00:03:30,360 --> 00:03:33,430
Ons gaan om voort te gaan gryp
karakters terwyl ons bereik nie die

64
00:03:33,430 --> 00:03:37,540
einde van die lêer, sodat daar
twee gevalle het ons nodig het om te hanteer.

65
00:03:37,540 --> 00:03:41,640
Die eerste, as die karakter was nie 'n
nuwe lyn, sodat ons weet of dit 'n nuwe

66
00:03:41,640 --> 00:03:44,480
lyn, dan is ons oor te
beweeg na 'n nuwe woord.

67
00:03:44,480 --> 00:03:49,300
Maar die veronderstelling dat dit was nie 'n nuwe lyn, dan
Hier wil ons om uit te vind die

68
00:03:49,300 --> 00:03:52,440
indeks gaan ons na die indeks in
in die kinders skikking wat

69
00:03:52,440 --> 00:03:53,890
Ons kyk na voor.

70
00:03:53,890 --> 00:03:57,950
>> Dus, net soos ek gesê het, moet ons
spesiale geval die toespraak.

71
00:03:57,950 --> 00:04:01,040
Let ons die gebruik van die drieledige operateur
hier, so ons gaan om te lees

72
00:04:01,040 --> 00:04:05,500
hierdie asof die karakter wat ons gelees het, was
'n toespraak, dan gaan ons

73
00:04:05,500 --> 00:04:11,740
stel indeks gelyk aan alfabet minus
1, wat sal die indeks 26 wees.

74
00:04:11,740 --> 00:04:15,190
Anders, as dit nie was 'n toespraak,
dan gaan ons die indeks op te stel

75
00:04:15,190 --> 00:04:17,820
gelyk aan c minus a.

76
00:04:17,820 --> 00:04:23,090
So onthou terug van die vorige p stelle,
c minus 'n gaan ons die te gee

77
00:04:23,090 --> 00:04:27,470
alfabetiese posisie van c, so as
c is die letter A, word dit

78
00:04:27,470 --> 00:04:28,770
gee ons indeks nul.

79
00:04:28,770 --> 00:04:32,180
Vir die letter B, sou dit gee
ons die indeks 1, en so aan.

80
00:04:32,180 --> 00:04:37,070
>> So dit gee ons die indeks in die
Kinders skikking wat ons wil hê.

81
00:04:37,070 --> 00:04:42,540
Nou, as die indeks is tans nul in
die kinders skikking, wat beteken dat

82
00:04:42,540 --> 00:04:47,470
'n knoop op die oomblik nie bestaan ​​uit
dat die pad, sodat ons nodig het om te wys 'n

83
00:04:47,470 --> 00:04:49,220
knoop vir die pad.

84
00:04:49,220 --> 00:04:50,610
Dit is wat ons hier doen.

85
00:04:50,610 --> 00:04:54,650
So gaan ons weer, gebruik die Calloc
funksie sodat ons nie

86
00:04:54,650 --> 00:05:00,130
nul uit al die wysers, en ons,
weer, moet daardie Calloc om seker te maak

87
00:05:00,130 --> 00:05:01,300
het nie misluk nie.

88
00:05:01,300 --> 00:05:04,760
As Calloc het misluk, dan moet ons
om alles te los, sluit ons

89
00:05:04,760 --> 00:05:06,880
woordeboek, en terug Vals.

90
00:05:06,880 --> 00:05:14,110
>> So die veronderstelling dat dit nie slaag nie, dan
dit sal 'n nuwe kind vir ons skep,

91
00:05:14,110 --> 00:05:16,000
en dan sal ons na daardie kind.

92
00:05:16,000 --> 00:05:19,030
Ons wyser sal Itereer
af aan daardie kind.

93
00:05:19,030 --> 00:05:23,390
Nou, as dit nie nul te begin,
dan die wyser kan net Itereer

94
00:05:23,390 --> 00:05:26,650
af aan daardie kind sonder om werklik
om iets te ken.

95
00:05:26,650 --> 00:05:30,790
Dit is die geval waar ons die eerste keer gebeur het
die woord kat te ken, en

96
00:05:30,790 --> 00:05:34,390
Dit beteken dat wanneer ons gaan te ken
ramp, het ons nie nodig om te skep

97
00:05:34,390 --> 00:05:35,720
nodes vir C-A-T weer.

98
00:05:35,720 --> 00:05:37,620
Hulle het reeds bestaan.

99
00:05:37,620 --> 00:05:40,140
>> OK, so wat is hierdie Anders?

100
00:05:40,140 --> 00:05:44,600
Dit is die toestand waar c was
backslash n, waar c 'n nuwe lyn.

101
00:05:44,600 --> 00:05:47,780
Dit beteken dat ons suksesvol
voltooi 'n woord.

102
00:05:47,780 --> 00:05:51,020
Nou, wat wil ons doen wanneer ons
'n woord suksesvol voltooi?

103
00:05:51,020 --> 00:05:55,250
Ons gaan hierdie woord veld te gebruik
binnekant van ons struct knoop.

104
00:05:55,250 --> 00:06:00,570
>> Ons wil dit waar, sodat
dui aan dat hierdie knoop dui op 'n

105
00:06:00,570 --> 00:06:03,320
suksesvolle woord 'n werklike woord.

106
00:06:03,320 --> 00:06:05,050
Nou, stel wat aan True.

107
00:06:05,050 --> 00:06:09,210
Ons wil ons wyser te herstel na punt
aan die begin van die Trie weer.

108
00:06:09,210 --> 00:06:13,510
En uiteindelik, inkrementeer ons woordeboek
grootte, aangesien ons het nog 'n woord.

109
00:06:13,510 --> 00:06:16,450
>> Alle reg, so ons gaan aanhou doen
dat lees in karakter deur

110
00:06:16,450 --> 00:06:21,960
karakter, die bou van nuwe nodes in
ons Trie en vir elke woord in die

111
00:06:21,960 --> 00:06:26,810
woordeboek, totdat ons uiteindelik bereik c
gelyk EOF, in watter geval, ons breek

112
00:06:26,810 --> 00:06:28,100
uit die lêer.

113
00:06:28,100 --> 00:06:31,110
Nou is daar twee gevalle onder
wat ons kan EOF getref het.

114
00:06:31,110 --> 00:06:35,680
Die eerste is as daar 'n fout
die lees van die lêer, sodat as daar

115
00:06:35,680 --> 00:06:39,280
'n fout, ons moet die tipiese te doen
los alles, maak die lêer,

116
00:06:39,280 --> 00:06:40,520
terug Vals.

117
00:06:40,520 --> 00:06:43,870
Veronderstelling daar was nie 'n fout, wat
beteken net ons eintlik getref die einde van

118
00:06:43,870 --> 00:06:47,820
die lêer, in watter geval, ons sluit die
lêer en terugkeer waar nie, aangesien ons

119
00:06:47,820 --> 00:06:51,010
die woordeboek suksesvol gelaai
in ons Trie.

120
00:06:51,010 --> 00:06:54,240
>> Alle reg, so laat ons nou
check Check.

121
00:06:54,240 --> 00:06:58,780
Kyk na die Check funksie, sien ons
daardie tjek gaan 'n Bool om terug te keer.

122
00:06:58,780 --> 00:07:03,740
Dit gee Waar indien hierdie woord wat dit is
oorgedra is in ons Trie.

123
00:07:03,740 --> 00:07:06,170
Dit gee Vals anders.

124
00:07:06,170 --> 00:07:10,110
>> So hoe gaan ons om te bepaal of
hierdie woord is in ons Trie?

125
00:07:10,110 --> 00:07:14,270
Ons sien hier dat, net soos tevore,
ons gaan wyser te gebruik om Itereer

126
00:07:14,270 --> 00:07:16,010
deur ons Trie.

127
00:07:16,010 --> 00:07:20,650
Nou, hier gaan ons te Itereer
oor ons hele woord.

128
00:07:20,650 --> 00:07:24,680
So iterating oor die woord wat ons is
geslaag het, gaan ons om te bepaal die

129
00:07:24,680 --> 00:07:29,280
indeks vir die kinders skikking wat
ooreenstem met woord bracket i.

130
00:07:29,280 --> 00:07:34,150
So dit gaan lyk presies soos
Vrag, waar as woord bracket ek is 'n

131
00:07:34,150 --> 00:07:38,110
toespraak, dan wil ons indeks te gebruik
alfabet minus 1 omdat ons bepaal

132
00:07:38,110 --> 00:07:41,160
dit is waar ons gaan
apostrofes te stoor.

133
00:07:41,160 --> 00:07:44,440
>> Anders gaan ons tolower te gebruik
woord bracket i.

134
00:07:44,440 --> 00:07:48,270
So onthou dat die woord kan arbitrêre
kapitalisasie, en so het ons

135
00:07:48,270 --> 00:07:51,590
wil seker maak dat ons gebruik maak
'n klein weergawe van die dinge.

136
00:07:51,590 --> 00:07:55,300
En dan trek uit daardie klein
'n te weer, gee ons die

137
00:07:55,300 --> 00:07:57,940
alfabetiese posisie
van die karakter.

138
00:07:57,940 --> 00:08:01,740
So wat gaan ons indeks te wees
in die kinders skikking.

139
00:08:01,740 --> 00:08:06,480
>> En nou, as die indeks vir die kinders
skikking is nul, wat beteken dat ons

140
00:08:06,480 --> 00:08:09,050
kan nie meer voortgaan iterating
down ons Trie.

141
00:08:09,050 --> 00:08:13,320
As dit die geval is, is hierdie woord kan nie
moontlik wees in ons Trie, want as dit

142
00:08:13,320 --> 00:08:18,000
was, sou dit beteken dat daar 'n wees
pad af na die woord, en jy sou

143
00:08:18,000 --> 00:08:19,350
nooit ontmoet null.

144
00:08:19,350 --> 00:08:21,910
So stuit nul, keer ons terug Vals.

145
00:08:21,910 --> 00:08:23,810
Die woord is nie in die woordeboek.

146
00:08:23,810 --> 00:08:28,200
As dit nie was nul, dan gaan ons
voortgaan iterating, so ons gaan

147
00:08:28,200 --> 00:08:33,150
ons wyser te werk aan te dui dat
spesifieke knoop op die indeks.

148
00:08:33,150 --> 00:08:36,659
>> So ons hou doen wat dwarsdeur
die hele woord.

149
00:08:36,659 --> 00:08:40,630
Veronderstelling ons nooit getref nul, wat beteken dat
ons in staat was om te kry deur die hele

150
00:08:40,630 --> 00:08:44,840
wêreld en vind 'n knoop in ons Trie,
maar ons is nog nie heeltemal klaar nie.

151
00:08:44,840 --> 00:08:46,350
Ons wil nie net terug Waar.

152
00:08:46,350 --> 00:08:51,400
Ons wil wyser fout woord om terug te keer
sedert, onthou weer, as die kat is nie

153
00:08:51,400 --> 00:08:55,140
in ons woordeboek en ramp is,
dan sal ons suksesvol kry deur

154
00:08:55,140 --> 00:08:59,810
die woord kat, maar wyser woord
sal Vals en nie waar wees nie.

155
00:08:59,810 --> 00:09:04,990
So ons terugkeer wyser woord aan te dui
of hierdie knoop is eintlik 'n woord,

156
00:09:04,990 --> 00:09:06,530
en dit is dit vir check.

157
00:09:06,530 --> 00:09:08,310
>> So laat ons kyk na grootte.

158
00:09:08,310 --> 00:09:11,410
So grootte gaan wees redelik maklik
sedert, onthou in Vrag, ons is

159
00:09:11,410 --> 00:09:15,480
die verhoog woordeboek grootte vir
elke woord wat ons teëkom.

160
00:09:15,480 --> 00:09:20,820
So grootte is net gaan om terug te keer
woordeboek grootte, en dit is dit.

161
00:09:20,820 --> 00:09:24,650
>> Alle reg, sodat laastens, ons het los.

162
00:09:24,650 --> 00:09:29,050
So los, ons gaan gebruik om 'n
rekursiewe funksie te eintlik al

163
00:09:29,050 --> 00:09:33,390
van die werk vir ons, sodat ons funksie
gaan genoem word losser.

164
00:09:33,390 --> 00:09:35,830
Wat is losser gaan doen?

165
00:09:35,830 --> 00:09:40,640
Ons sien hier dat losser gaan
Itereer oor al die kinders wat by

166
00:09:40,640 --> 00:09:45,810
hierdie spesifieke knoop, en indien die kind
knoop is nie nul is, dan gaan ons

167
00:09:45,810 --> 00:09:47,760
los die kind knoop.

168
00:09:47,760 --> 00:09:52,070
>> So dit gaan rekursief
los almal van ons kinders.

169
00:09:52,070 --> 00:09:55,140
Sodra ons is seker dat al ons kinders
is afgelaai het, dan het ons

170
00:09:55,140 --> 00:09:58,830
kan bevry onsself, so los onsself.

171
00:09:58,830 --> 00:10:04,550
So dit sal rekursief los die
hele Trie, en dan weer dit is

172
00:10:04,550 --> 00:10:06,910
gedoen het, kan ons net terug Waar.

173
00:10:06,910 --> 00:10:09,770
Los nie kan misluk nie, ons is
net bevry dinge.

174
00:10:09,770 --> 00:10:12,985
So wanneer ons klaar is bevry
alles terug Waar.

175
00:10:12,985 --> 00:10:14,380
En dit is dit.

176
00:10:14,380 --> 00:10:16,792
My naam is Rob, en hierdie
was [onhoorbaar].

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