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

2
00:00:00,530 --> 00:00:03,070
>> Ræðumaður 1: Við skulum gefa
Þessi lausn að reyna.

3
00:00:03,070 --> 00:00:07,130
Þannig að við skulum taka a líta á það sem okkar
Strúktúr hnút mun líta út.

4
00:00:07,130 --> 00:00:11,040
Hér sjáum við að við erum að fara að hafa
Bool Word og Struct hnút stjörnu

5
00:00:11,040 --> 00:00:12,990
Börn krappi stafrófið.

6
00:00:12,990 --> 00:00:18,720
Svo fyrsta sem þú gætir verið að spá,
hvers vegna er stafrófið kjötkássa skilgreind sem 27?

7
00:00:18,720 --> 00:00:22,540
Jæja, muna að við erum að fara að þurfa
að vera meðhöndlun úrfellingarmerki, svo

8
00:00:22,540 --> 00:00:25,610
það er að fara að vera nokkuð sérstakt
allt til þessarar áætlunar.

9
00:00:25,610 --> 00:00:28,780
>> OK, nú, muna hvernig
Trie virkar í raun.

10
00:00:28,780 --> 00:00:33,420
Segjum að við erum flokkun á orð ketti,
þá frá rót Trie okkar,

11
00:00:33,420 --> 00:00:36,670
við erum að fara að horfa á börnin
array, og við erum að fara að líta á

12
00:00:36,670 --> 00:00:42,250
Vísitala sem svarar til bréf
C. Svo það væri Vísitala tvö.

13
00:00:42,250 --> 00:00:46,400
Svo í ljósi þess, sem mun gefa okkur
ný hnút, og þá munum við

14
00:00:46,400 --> 00:00:47,880
vinna úr þeim hnút.

15
00:00:47,880 --> 00:00:51,830
>> Svo í ljósi þess hnút, erum við enn og aftur
fara að horfa á börnin fylking,

16
00:00:51,830 --> 00:00:56,170
og við erum að fara að horfa á vísitölu núll
að vinna í samræmi við A í cat.

17
00:00:56,170 --> 00:01:01,240
Svo þá erum við að fara að fara til hnút,
og í ljósi þess að hnút, við erum að fara

18
00:01:01,240 --> 00:01:05,170
að líta á vísitölu sem svarar
til T. og færa til þess hnút,

19
00:01:05,170 --> 00:01:09,590
Að lokum, höfum við alveg leit
gegnum orð kötturinn okkar, og nú bool

20
00:01:09,590 --> 00:01:15,020
Orðið er ætlað að gefa til kynna hvort
þetta gefið orð er í raun orð.

21
00:01:15,020 --> 00:01:17,530
>> Svo hvers vegna þurfum við að sérstakt tilfelli?

22
00:01:17,530 --> 00:01:21,680
Jæja, hvað ef orðið stórslys
er í orðabók okkar, en

23
00:01:21,680 --> 00:01:24,120
orðið köttur er það ekki?

24
00:01:24,120 --> 00:01:29,030
Svo í að leita að sjá hvort orð kötturinn er
í orðabók okkar, við erum að fara að

25
00:01:29,030 --> 00:01:34,880
tókst að líta í gegnum skránna
C-A-T og ná hnút, en það er

26
00:01:34,880 --> 00:01:39,760
aðeins vegna stórslys gerðist
að búa til hnútar á leiðinni frá C-A-T allan

27
00:01:39,760 --> 00:01:41,250
leið til the endir af the orð.

28
00:01:41,250 --> 00:01:46,520
Svo bool Word er notað til kynna hvort
þetta tiltekna staðsetningu raun

29
00:01:46,520 --> 00:01:48,370
táknar orð.

30
00:01:48,370 --> 00:01:52,920
>> Allt í lagi, svo nú að við vitum hvað
Trie er að fara að líta út eins og, við skulum líta

31
00:01:52,920 --> 00:01:54,800
á álaginu virka.

32
00:01:54,800 --> 00:01:58,670
Svo Load er að fara að skila bool
fyrir hvort við góðum árangri eða

33
00:01:58,670 --> 00:02:03,020
árangurslaust hlaðinn orðabók og
þetta er að fara til vera the orðabók

34
00:02:03,020 --> 00:02:04,520
að við viljum að hlaða.

35
00:02:04,520 --> 00:02:08,310
Svo fyrsta sem við ætlum að gera er að opna
upp þessi orðabók fyrir lestur.

36
00:02:08,310 --> 00:02:12,060
Við verðum að tryggja að við ekki mistakast,
þannig að ef orðabók væri ekki

37
00:02:12,060 --> 00:02:15,280
tókst opnaði, það mun skila
Nei, en í því tilviki sem við erum að fara að

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

39
00:02:16,340 --> 00:02:21,290
En miðað við að það tókst
opnaði, þá getum við í raun lesið

40
00:02:21,290 --> 00:02:22,310
gegnum orðabókina.

41
00:02:22,310 --> 00:02:24,940
>> Svo fyrsta sem við erum að fara að
vilja til að gera er að við höfum þetta

42
00:02:24,940 --> 00:02:26,560
Global breyta rót.

43
00:02:26,560 --> 00:02:30,250
Nú, rót er að fara til vera a hnút stjörnu.

44
00:02:30,250 --> 00:02:33,830
Það er efst á Trie okkar sem við erum
að fara að iterating gegnum.

45
00:02:33,830 --> 00:02:38,200
Svo fyrsta sem við erum að fara til að vilja
gera er að úthluta minni fyrir rót okkar.

46
00:02:38,200 --> 00:02:42,040
>> Takið eftir að við erum að nota Calloc
virka, sem er í grundvallaratriðum það sama

47
00:02:42,040 --> 00:02:45,560
sem Malloc virka, nema það er
tryggingu til að fara aftur eitthvað sem er

48
00:02:45,560 --> 00:02:47,240
alveg zeroed út.

49
00:02:47,240 --> 00:02:51,350
Þannig að ef við notuðum Malloc, vildi að við þurfum að
fara í gegnum öll ábendingum í okkar

50
00:02:51,350 --> 00:02:54,220
hnút og tryggja að
þeir eru allir null.

51
00:02:54,220 --> 00:02:56,780
Svo Calloc mun gera það fyrir okkur.

52
00:02:56,780 --> 00:03:00,390
>> Nú, rétt eins og Malloc, þurfum við að gera
úr skugga um að úthlutun er í raun

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

54
00:03:01,580 --> 00:03:04,060
Ef þetta aftur null, þá erum við
þarf að loka orðabók okkar

55
00:03:04,060 --> 00:03:06,170
skrá og skila False.

56
00:03:06,170 --> 00:03:11,040
Svo miðað við úthlutun var
vel, við erum að fara að nota hnút

57
00:03:11,040 --> 00:03:14,340
stjörnu bendilinn til iterate
gegnum Trie okkar.

58
00:03:14,340 --> 00:03:17,950
Svo rót okkar er aldrei að fara að breytast,
en við erum að fara að nota bendilinn til

59
00:03:17,950 --> 00:03:20,770
reyndar fara frá hnút í hnút.

60
00:03:20,770 --> 00:03:25,000
>> Allt í lagi, svo í þetta fyrir lykkju, við erum
lesa í gegnum orðabók skrá,

61
00:03:25,000 --> 00:03:26,965
og við erum að nota á fgetc.

62
00:03:26,965 --> 00:03:30,360
Svo fgetc er að fara að grípa einn
eðli úr skrá.

63
00:03:30,360 --> 00:03:33,430
Við erum að fara að halda áfram grabbing
stafir á meðan við ná ekki

64
00:03:33,430 --> 00:03:37,540
lok skrárinnar, þannig að það eru
tveimur tilvikum við þurfum að sinna.

65
00:03:37,540 --> 00:03:41,640
Fyrsta, ef eðli var ekki
Ný lína, þannig að við vitum hvort það var ný

66
00:03:41,640 --> 00:03:44,480
lína, þá erum við að fara að
hreyfa á til nýtt orð.

67
00:03:44,480 --> 00:03:49,300
En miðað við það var ekki ný línu, þá
hér, viljum við að reikna út

68
00:03:49,300 --> 00:03:52,440
vísitölu sem við erum að fara að kemba í
í barna fylkingu sem

69
00:03:52,440 --> 00:03:53,890
við skoðuðum áður.

70
00:03:53,890 --> 00:03:57,950
>> Svo eins og ég sagði áður, þurfum við að
sérstakt tilfelli úrfellingarmerki.

71
00:03:57,950 --> 00:04:01,040
Taka við erum með ternary rekstraraðila
hér, þannig að við erum að fara að lesa

72
00:04:01,040 --> 00:04:05,500
þetta eins og ef eðli við lesið í var
úrfellingarmerki, þá erum við að fara að

73
00:04:05,500 --> 00:04:11,740
setja vísitölu jöfn stafrófið mínus
1, sem verður vísitala 26.

74
00:04:11,740 --> 00:04:15,190
Annars, ef það var ekki úrfellingarmerki,
þá erum við að fara að láta vísitölu

75
00:04:15,190 --> 00:04:17,820
jafnt c mínus.

76
00:04:17,820 --> 00:04:23,090
Svo man aftur frá fyrri p setur,
c mínus er að fara að gefa okkur

77
00:04:23,090 --> 00:04:27,470
stafrófsröð staða c, þannig að ef
c er bókstafurinn A, þetta mun

78
00:04:27,470 --> 00:04:28,770
gefa okkur vísitölu núll.

79
00:04:28,770 --> 00:04:32,180
Fyrir stafinn B, það myndi gefa
okkur vísitalan 1, og svo framvegis.

80
00:04:32,180 --> 00:04:37,070
>> Svo það gefur okkur vísitölu inn í
Börn array sem við viljum.

81
00:04:37,070 --> 00:04:42,540
Nú, ef þetta vísitölu er nú null í
the Children array, sem þýðir að

82
00:04:42,540 --> 00:04:47,470
hnút ekki fyrir hendi úr
sem leið, þannig að við þurfum að úthluta

83
00:04:47,470 --> 00:04:49,220
hnút í þeirri braut.

84
00:04:49,220 --> 00:04:50,610
Það er það sem við gerum hér.

85
00:04:50,610 --> 00:04:54,650
Þannig að við ætlum að, aftur, nota Calloc
virka þannig að við höfum ekki

86
00:04:54,650 --> 00:05:00,130
til núll út allar ábendingum, og við,
aftur, þarf að athuga að Calloc

87
00:05:00,130 --> 00:05:01,300
ekki mistakast.

88
00:05:01,300 --> 00:05:04,760
Ef Calloc gerði ekki, þá þurfum við
að afferma allt, loka okkar

89
00:05:04,760 --> 00:05:06,880
orðabók, og return false.

90
00:05:06,880 --> 00:05:14,110
>> Svo miðað við að það var ekki mistakast, þá
þetta mun búa til nýtt barn fyrir okkur,

91
00:05:14,110 --> 00:05:16,000
og þá munum við fara til barnsins.

92
00:05:16,000 --> 00:05:19,030
Bendillinn okkar mun kunnugt er
niður til að barnið.

93
00:05:19,030 --> 00:05:23,390
Nú, ef þetta var ekki null til að byrja með,
þá bendillinn getur bara iterate

94
00:05:23,390 --> 00:05:26,650
niður til að barnið án þess að raunverulega
að þurfa að úthluta neitt.

95
00:05:26,650 --> 00:05:30,790
Þetta er raunin þar sem við gerðist fyrst
að úthluta orðið köttur, og

96
00:05:30,790 --> 00:05:34,390
sem þýðir að þegar við förum að úthluta
stórslys, við þurfum ekki að búa til

97
00:05:34,390 --> 00:05:35,720
hnúta fyrir C-A-T aftur.

98
00:05:35,720 --> 00:05:37,620
Þeir eru fyrir hendi nú þegar.

99
00:05:37,620 --> 00:05:40,140
>> OK, hvað er þetta annað?

100
00:05:40,140 --> 00:05:44,600
Þetta er ástand þar sem C, var
sviga n, þar sem C, var nýja línu.

101
00:05:44,600 --> 00:05:47,780
Þetta þýðir að við höfum tekist
lokið orð.

102
00:05:47,780 --> 00:05:51,020
Nú, hvað við viljum gera þegar við
lokið orð?

103
00:05:51,020 --> 00:05:55,250
Við erum að fara að nota þetta orð reit
inni strúktúr hnút okkar.

104
00:05:55,250 --> 00:06:00,570
>> Við viljum að setja það á True, svo að
gefur til kynna að þetta hnútur táknar

105
00:06:00,570 --> 00:06:03,320
vel orðið raunveruleg orð.

106
00:06:03,320 --> 00:06:05,050
Nú, setja það til True.

107
00:06:05,050 --> 00:06:09,210
Við viljum að endurstilla bendilinn okkar lið
að upphafi Trie aftur.

108
00:06:09,210 --> 00:06:13,510
Og að lokum, vöxtur orðabók okkar
stærð þar sem við fundum annað orð.

109
00:06:13,510 --> 00:06:16,450
>> Allt í lagi, þannig að við erum að fara að halda að gera
að lesa í staf með

110
00:06:16,450 --> 00:06:21,960
eðli, byggingu nýja hnúta í
Trie okkar og fyrir hvert orð í

111
00:06:21,960 --> 00:06:26,810
orðabók, þangað til við komum að lokum c
jafngildir EOF, í því tilviki, brot við

112
00:06:26,810 --> 00:06:28,100
út af skránni.

113
00:06:28,100 --> 00:06:31,110
Nú, það eru tvö tilvik undir
sem við gætum hafa högg EOF.

114
00:06:31,110 --> 00:06:35,680
Fyrsta er ef það var villa
lesa úr skrá, þannig að ef það var

115
00:06:35,680 --> 00:06:39,280
villa, þurfum við að gera dæmigerð
afferma allt, loka skrá,

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

117
00:06:40,520 --> 00:06:43,870
Miðað við að það var ekki villa, að
bara þýðir að við högg í raun enda

118
00:06:43,870 --> 00:06:47,820
skráin, í því tilviki, nálægt við á
skrá og skila satt þar sem við

119
00:06:47,820 --> 00:06:51,010
tókst hlaðinn orðabók
í Trie okkar.

120
00:06:51,010 --> 00:06:54,240
>> Allt í lagi, svo nú skulum
kíkja stöðva.

121
00:06:54,240 --> 00:06:58,780
Þegar litið er á the stöðva virka, sjáum við
að stöðva er að fara að skila bool.

122
00:06:58,780 --> 00:07:03,740
Það skilar True ef þetta orð að það er
berist er í Trie okkar.

123
00:07:03,740 --> 00:07:06,170
False annað.

124
00:07:06,170 --> 00:07:10,110
>> Svo hvernig eigum við að fara að ákveða hvort
þetta orð er í Trie okkar?

125
00:07:10,110 --> 00:07:14,270
Við sjáum hér að, rétt eins og áður,
við erum að fara að nota bendilinn til iterate

126
00:07:14,270 --> 00:07:16,010
gegnum Trie okkar.

127
00:07:16,010 --> 00:07:20,650
Nú, hér erum við að fara að iterate
yfir öllu orð okkar.

128
00:07:20,650 --> 00:07:24,680
Svo iterating yfir orð sem við erum
liðin, við erum að fara að ákveða

129
00:07:24,680 --> 00:07:29,280
Vísitala í börnin fylkingu sem
samsvarar orðinu krappi i.

130
00:07:29,280 --> 00:07:34,150
Þannig að þetta er að fara að líta nákvæmlega eins og
Álag, þar sem ef orð krappi ég er

131
00:07:34,150 --> 00:07:38,110
úrfellingarmerki, þá viljum við nota vísitölu
stafrófið mínus 1 vegna þess að við ákveðin

132
00:07:38,110 --> 00:07:41,160
það er þar sem við erum að fara
að geyma úrfellingarmerki.

133
00:07:41,160 --> 00:07:44,440
>> Annað sem við erum að fara að nota tolower
Orðið krappi i.

134
00:07:44,440 --> 00:07:48,270
Svo muna að orð geta haft handahófskennt
fjármögnun, og svo við

135
00:07:48,270 --> 00:07:51,590
vilja til að ganga úr skugga um að við erum að nota
A lágstafir útgáfa af hlutum.

136
00:07:51,590 --> 00:07:55,300
Og þá draga úr því lágstafir
a til að, enn og aftur, gefa okkur

137
00:07:55,300 --> 00:07:57,940
stafrófsröð staða
þeirrar persónu.

138
00:07:57,940 --> 00:08:01,740
Svo það er að fara að vera vísitölu okkar
í Börnin fylkisins.

139
00:08:01,740 --> 00:08:06,480
>> Og nú, ef að vísitalan í börnin
array er núll, sem þýðir að við

140
00:08:06,480 --> 00:08:09,050
getur ekki lengur haldið áfram iterating
niður Trie okkar.

141
00:08:09,050 --> 00:08:13,320
Ef það er málið, þetta orð er ekki hægt
hugsanlega verið í Trie okkar, því ef það

142
00:08:13,320 --> 00:08:18,000
voru, sem myndi þýða að það væri
Slóðin niður í þessi orð, og þú myndir

143
00:08:18,000 --> 00:08:19,350
aldrei lenda null.

144
00:08:19,350 --> 00:08:21,910
Svo hitta null aftur við False.

145
00:08:21,910 --> 00:08:23,810
Er orðið ekki í orðabókinni.

146
00:08:23,810 --> 00:08:28,200
Ef það væri ekki null, þá erum við að fara að
áfram iterating, þannig að við erum að fara

147
00:08:28,200 --> 00:08:33,150
að uppfæra bendilinn okkar til að benda á að
einkum hnút í vísitölunni.

148
00:08:33,150 --> 00:08:36,659
>> Svo við höldum að gera það í gegn
allt orðið.

149
00:08:36,659 --> 00:08:40,630
Miðað við högg aldrei null, sem þýðir
við gátum til að komast í gegnum allt

150
00:08:40,630 --> 00:08:44,840
heimurinn og finna hnút í Trie okkar,
en við erum ekki alveg búin ennþá.

151
00:08:44,840 --> 00:08:46,350
Við viljum ekki bara koma aftur True.

152
00:08:46,350 --> 00:08:51,400
Við viljum skila bendilinn villa orð
síðan, man aftur, ef kötturinn er ekki

153
00:08:51,400 --> 00:08:55,140
í orðabók okkar og stórslys er,
þá munum við tekist að komast í gegnum

154
00:08:55,140 --> 00:08:59,810
orðið köttur, en bendillinn orð
verður falskur og ekki satt.

155
00:08:59,810 --> 00:09:04,990
Þannig að við aftur bendilinn orð til að sýna
hvort þetta hnútur er í raun orð,

156
00:09:04,990 --> 00:09:06,530
og það er það að athuga.

157
00:09:06,530 --> 00:09:08,310
>> Þannig að við skulum kíkja stærð.

158
00:09:08,310 --> 00:09:11,410
Svo stærð er að fara að vera nokkuð auðvelt
síðan, man í álag, við erum

159
00:09:11,410 --> 00:09:15,480
incrementing orðabók stærð fyrir
hvert orð sem við lendum.

160
00:09:15,480 --> 00:09:20,820
Svo Stærð er bara að fara að fara aftur
orðabók stærð, og það er það.

161
00:09:20,820 --> 00:09:24,650
>> Allt í lagi, svo loksins, höfum við afferma.

162
00:09:24,650 --> 00:09:29,050
Svo afferma, við erum að fara að nota
endurkvæma virka til raunverulega gera allt

163
00:09:29,050 --> 00:09:33,390
af vinnu fyrir okkur, svo virka okkar
er að fara að vera kölluð Unloader.

164
00:09:33,390 --> 00:09:35,830
Hvað er Unloader að fara að gera?

165
00:09:35,830 --> 00:09:40,640
Við sjáum hér að Unloader er að fara að
iterate yfir öll börn á

166
00:09:40,640 --> 00:09:45,810
Þetta tiltekna hnút, og ef barnið
tengipunktur er ekki núll, þá erum við að fara að

167
00:09:45,810 --> 00:09:47,760
afferma barn hnút.

168
00:09:47,760 --> 00:09:52,070
>> Þannig að þetta er að fara til endurkvæmt
afferma öll börnin okkar.

169
00:09:52,070 --> 00:09:55,140
Þegar við erum viss um að öll börn okkar
hafa verið skipað, þá erum við

170
00:09:55,140 --> 00:09:58,830
geta losa okkur, svo afferma okkur sjálf.

171
00:09:58,830 --> 00:10:04,550
Þannig að þetta verður endurkvæmt afferma
Öllu Trie, og þá einu sinni sem er

172
00:10:04,550 --> 00:10:06,910
gert, getum við bara aftur True.

173
00:10:06,910 --> 00:10:09,770
Afferma getur ekki mistekist, við erum
bara frjáls hluti.

174
00:10:09,770 --> 00:10:12,985
Svo þegar við erum búin frjáls
allt aftur True.

175
00:10:12,985 --> 00:10:14,380
Og það er það.

176
00:10:14,380 --> 00:10:16,792
Mitt nafn er Rob, og þetta
var [inaudible].

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