1
00:00:00,000 --> 00:00:12,350
>> [Tónlist spila]

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

3
00:00:13,050 --> 00:00:13,640
Ég er Rob.

4
00:00:13,640 --> 00:00:16,210
Og við skulum þessa lausn út.

5
00:00:16,210 --> 00:00:20,070
Svo hér erum við að fara að innleiða
almenn borð.

6
00:00:20,070 --> 00:00:24,090
Við sjáum að strúktúr hnút af okkar
Taflan er að fara að líta svona út.

7
00:00:24,090 --> 00:00:28,710
Svo það er að fara að hafa bleikju orð
Fylki af stærðinni LENGD + 1.

8
00:00:28,710 --> 00:00:32,259
Ekki gleyma + 1, þar sem hámark
orð í orðabókinni er 45

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

10
00:00:33,130 --> 00:00:37,070
Og þá erum við að fara að þurfa einn auka
eðli fyrir sviga núll.

11
00:00:37,070 --> 00:00:40,870
>> Og þá Hashtable okkar í hvert
fötu er að fara að geyma

12
00:00:40,870 --> 00:00:42,320
tengda listanum hnúta.

13
00:00:42,320 --> 00:00:44,420
Við erum ekki að gera línuleg leit hér.

14
00:00:44,420 --> 00:00:48,430
Og svo í röð til að tengja við næsta
þáttur í fötu, þurfum við að

15
00:00:48,430 --> 00:00:50,390
struct node * næst.

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

17
00:00:51,110 --> 00:00:53,090
Svo er það sem hnúturinn lítur út.

18
00:00:53,090 --> 00:00:56,180
>> Nú er hér yfirlýsingin
af Hashtable okkar.

19
00:00:56,180 --> 00:00:59,640
Það er að fara að hafa 16.834 fötunum.

20
00:00:59,640 --> 00:01:01,910
En þessi tala er í raun ekki máli.

21
00:01:01,910 --> 00:01:05,450
Og að lokum, við erum að fara að hafa
Global breyta Hashtable stærð, sem

22
00:01:05,450 --> 00:01:07,000
er að fara að byrja á núll.

23
00:01:07,000 --> 00:01:10,760
Og það er að fara að halda utan um hvernig
mörg orð eru í orðabók okkar.

24
00:01:10,760 --> 00:01:13,710
>> Þannig að við skulum taka a líta á hleðslu.

25
00:01:13,710 --> 00:01:16,390
Taka eftir því að hlaða, skilar það sér bool.

26
00:01:16,390 --> 00:01:20,530
Þú skilar true ef það var með góðum árangri
hlaðinn og ósönn annars.

27
00:01:20,530 --> 00:01:23,990
Og það tekur const char * orðabók,
sem er orðabókinni

28
00:01:23,990 --> 00:01:25,280
að við viljum að opna.

29
00:01:25,280 --> 00:01:27,170
Svo er það fyrsta sem
við erum að fara að gera.

30
00:01:27,170 --> 00:01:29,500
>> Við erum að fara að fopen á
orðabók fyrir lestur.

31
00:01:29,500 --> 00:01:31,680
Og við erum að fara til verða að gera
viss um að það tókst.

32
00:01:31,680 --> 00:01:35,920
Þannig að ef það skilaði engu, svo við gerðum ekki
tókst að opna orðabók.

33
00:01:35,920 --> 00:01:37,440
Og við þurfum að skila falskur.

34
00:01:37,440 --> 00:01:41,580
En miðað við að það gerði með góðum árangri
opinn, þá viljum við að lesa

35
00:01:41,580 --> 00:01:42,400
orðabók.

36
00:01:42,400 --> 00:01:46,450
Svo halda lykkja þar til við að finna nokkrar
ástæða til að brjótast út úr þessu lykkju,

37
00:01:46,450 --> 00:01:47,570
sem við munum sjá.

38
00:01:47,570 --> 00:01:48,920
Svo halda lykkja.

39
00:01:48,920 --> 00:01:51,780
>> Og nú erum við að fara að
malloc einum hnút.

40
00:01:51,780 --> 00:01:54,020
Og auðvitað þurfum við
að loft athuga aftur.

41
00:01:54,020 --> 00:01:58,680
Svo ef mallocing ekki tekist, þá
við viljum að afferma allir hnút sem við

42
00:01:58,680 --> 00:02:02,590
gerðist að malloc áður, loka
orðabók og aftur ósatt.

43
00:02:02,590 --> 00:02:06,830
En hunsa það, miðað við
tekist, þá viljum við nota fscanf

44
00:02:06,830 --> 00:02:12,400
til að lesa eitt orð frá okkar
orðabók í hnút okkar.

45
00:02:12,400 --> 00:02:17,940
Svo muna að Entry> orð er bleikjan
orð biðminni stærð LENGHTH + 1

46
00:02:17,940 --> 00:02:20,300
að við erum að fara að geyma orð inn

47
00:02:20,300 --> 00:02:25,070
>> Svo fscanf er að fara að skila 1, svo lengi
eins og það var fær til giftusamlega

48
00:02:25,070 --> 00:02:26,750
lesa orð úr skrá.

49
00:02:26,750 --> 00:02:30,460
Ef annað hvort villa kemur, eða við
ná sambandi við lok skrárinnar, það

50
00:02:30,460 --> 00:02:31,950
mun ekki skila 1.

51
00:02:31,950 --> 00:02:35,180
Í því tilviki er það ekki aftur 1,
við erum loksins að fara að brjótast út úr

52
00:02:35,180 --> 00:02:37,280
þetta á meðan lykkja.

53
00:02:37,280 --> 00:02:42,770
Svo við sjáum að þegar við höfum tekist
lesa orð í

54
00:02:42,770 --> 00:02:48,270
innganga> orð, þá erum við að fara að því
orð með kjötkássa virka okkar.

55
00:02:48,270 --> 00:02:49,580
>> Láta 'taka a líta á
kjötkássa virka.

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

57
00:02:52,430 --> 00:02:55,610
Svo þú þarft ekki raunverulega þörf
að skilja þetta.

58
00:02:55,610 --> 00:02:59,460
Og reyndar við dregið bara þessa hass
virka af internetinu.

59
00:02:59,460 --> 00:03:04,010
Það eina sem þú þarft að viðurkenna er
að þetta tekur const char * orð.

60
00:03:04,010 --> 00:03:08,960
Svo það tekur a band sem inntak, og
aftur óundirritaður INT sem framleiðsla.

61
00:03:08,960 --> 00:03:12,360
Svo er það allt a kjötkássa virka er, er það
tekur í inntak og gefur þér

62
00:03:12,360 --> 00:03:14,490
Vísitala inn Hashtable.

63
00:03:14,490 --> 00:03:18,530
>> Takið eftir að við erum moding með NUM_BUCKETS,
þannig að gildi aftur

64
00:03:18,530 --> 00:03:21,730
reyndar er vísitölu í Hashtable
og ekki vísitölu handan

65
00:03:21,730 --> 00:03:24,320
mörk í fylkinu.

66
00:03:24,320 --> 00:03:28,060
Svo í ljósi þess virka, við erum að fara
til kjötkássa orð sem við lesum

67
00:03:28,060 --> 00:03:29,390
orðabók.

68
00:03:29,390 --> 00:03:31,700
Og þá erum við að fara að nota
sem kjötkássa að settu

69
00:03:31,700 --> 00:03:33,750
Gildistaka Hashtable.

70
00:03:33,750 --> 00:03:38,520
>> Nú Hashtable kjötkássa er núverandi
tengda listanum í töflunni.

71
00:03:38,520 --> 00:03:41,410
Og það er mjög líklegt
að það er bara NÚLL.

72
00:03:41,410 --> 00:03:44,960
Við viljum setja færslu okkar á
byrjun þessa tengda listanum.

73
00:03:44,960 --> 00:03:48,600
Og svo við erum að fara að hafa núverandi okkar
innganga benda á það sem Hashtable

74
00:03:48,600 --> 00:03:50,380
nú bendir til.

75
00:03:50,380 --> 00:03:53,310
Og þá erum við að fara að geyma,
í Hashtable á að

76
00:03:53,310 --> 00:03:55,350
hass, núverandi færslu.

77
00:03:55,350 --> 00:03:59,320
Svo þessar tvær línur tókst setja
færslunnar í upphafi að

78
00:03:59,320 --> 00:04:02,260
tengda listanum á vísitölunni
í Hashtable.

79
00:04:02,260 --> 00:04:04,900
>> Þegar við erum búin með það, við vitum
að við fundum annað orð í

80
00:04:04,900 --> 00:04:07,790
orðabók, og við stighækkun aftur.

81
00:04:07,790 --> 00:04:13,960
Svo við höldum að gera það fyrr en fscanf
að lokum skilað eitthvað non-1 á

82
00:04:13,960 --> 00:04:16,950
sem lið muna að
við þurfum að losa færslu.

83
00:04:16,950 --> 00:04:19,459
Svo upp hér við malloced færslu.

84
00:04:19,459 --> 00:04:21,329
Og við reyndum að lesa eitthvað
úr orðabókinni.

85
00:04:21,329 --> 00:04:23,910
Og við fengum ekki tekist að lesa
eitthvað úr orðabókinni, í

86
00:04:23,910 --> 00:04:26,650
en þá þurfum við að losa færslu
sem við aldrei raunverulega setja inn í

87
00:04:26,650 --> 00:04:29,140
Hashtable, og að lokum brjóta.

88
00:04:29,140 --> 00:04:32,750
>> Þegar við brjótast út við þurfum að sjá, vel,
höfum vér brjótast út vegna þess að það

89
00:04:32,750 --> 00:04:34,360
var að villa við lestur úr skránni?

90
00:04:34,360 --> 00:04:37,120
Eða höfum vér brjótast út vegna þess að við
náð í lok skrárinnar?

91
00:04:37,120 --> 00:04:39,480
Ef það kom upp villa, þá
við viljum return false.

92
00:04:39,480 --> 00:04:40,930
Vegna hlaða tókst ekki.

93
00:04:40,930 --> 00:04:43,890
Og í því ferli sem við viljum að afferma
öll þau orð, sem við lesum í, og

94
00:04:43,890 --> 00:04:45,670
loka orðabók skrá.

95
00:04:45,670 --> 00:04:48,740
>> Miðað við hafi tekist, þá erum við bara
enn þurft að loka orðabók

96
00:04:48,740 --> 00:04:53,040
skrá, og að lokum aftur satt þar sem við
Það tókst að hlaða orðabókinni.

97
00:04:53,040 --> 00:04:54,420
Og það er það að hlaða.

98
00:04:54,420 --> 00:04:59,020
Svo nú athugað, í ljósi hlaðinn Hashtable,
er að fara að líta svona út.

99
00:04:59,020 --> 00:05:03,140
Svo stöðva það skilar bool, sem er
fara til kynna hvort liðið

100
00:05:03,140 --> 00:05:07,530
í char * orði, hvort liðin
í band er í orðabók okkar.

101
00:05:07,530 --> 00:05:09,890
Þannig að ef það er í orðabókinni,
ef það er í Hashtable okkar,

102
00:05:09,890 --> 00:05:11,170
við munum fara aftur satt.

103
00:05:11,170 --> 00:05:13,380
Og ef það er ekki, munum við aftur ósatt.

104
00:05:13,380 --> 00:05:17,740
>> Í ljósi þessa samþykkt í orði, við erum
fara að kjötkássa orðið.

105
00:05:17,740 --> 00:05:22,110
Nú er mikilvægt að viðurkenna
að í álagi við vissum að allir sem

106
00:05:22,110 --> 00:05:23,820
orð sem við ætlum að vera lágstöfum.

107
00:05:23,820 --> 00:05:25,820
En hér erum við ekki svo viss.

108
00:05:25,820 --> 00:05:29,510
Ef við lítum á kjötkássa virka okkar,
kjötkássa virka okkar í raun

109
00:05:29,510 --> 00:05:32,700
er lægra hlíf hvert eðli
orðsins.

110
00:05:32,700 --> 00:05:37,940
Svo óháð fjármögnun
orð, kjötkássa virka okkar er aftur

111
00:05:37,940 --> 00:05:42,270
sama vísitölu hvað sem
hástafanotkun er, eins og það myndi hafa

112
00:05:42,270 --> 00:05:45,280
aftur fyrir alveg lágstafir
útgáfa af orðinu.

113
00:05:45,280 --> 00:05:46,600
Allt í lagi.

114
00:05:46,600 --> 00:05:49,790
Það er vísitala okkar er inn í
Hashtable fyrir þetta orð.

115
00:05:49,790 --> 00:05:52,940
>> Nú þetta fyrir lykkja er að fara að
iterate yfir tengda listanum

116
00:05:52,940 --> 00:05:55,000
sem var á vísitölunni.

117
00:05:55,000 --> 00:05:59,610
Svo taka við erum Frumstilli færslu
til að benda á vísitölunni.

118
00:05:59,610 --> 00:06:02,750
Við erum að fara að halda áfram
en innganga = null.

119
00:06:02,750 --> 00:06:07,770
Og muna að uppfæra músina
í tengda listanum innganga okkar = færsla> næst.

120
00:06:07,770 --> 00:06:14,400
Svo hafa núverandi innganga okkar benda til
Í næsta atriði í tengda listanum.

121
00:06:14,400 --> 00:06:19,250
>> Svo fyrir hverja færslu í tengda listanum,
við erum að fara að nota strcasecmp.

122
00:06:19,250 --> 00:06:20,330
Það er ekki strcomp.

123
00:06:20,330 --> 00:06:23,780
Því enn og aftur, við viljum
gera hlutina mál insensitively.

124
00:06:23,780 --> 00:06:27,870
Svo við notum strcasecmp að bera saman
Orðið sem var samþykkt í gegnum þetta

125
00:06:27,870 --> 00:06:31,860
virka gegn orði
sem er í þessari færslu.

126
00:06:31,860 --> 00:06:35,570
Ef það skilar núll, sem þýðir að það var
leik, en í því tilviki sem við viljum

127
00:06:35,570 --> 00:06:36,630
return true.

128
00:06:36,630 --> 00:06:39,590
Við fundum tókst að
orð í Hashtable okkar.

129
00:06:39,590 --> 00:06:43,040
>> Ef það var ekki passa, þá erum við
fara að lykkja aftur og líta á

130
00:06:43,040 --> 00:06:43,990
Next Entry.

131
00:06:43,990 --> 00:06:47,640
Og við munum halda áfram að lykkja á meðan það
eru færslur í þessum tengda listanum.

132
00:06:47,640 --> 00:06:50,160
Hvað gerist ef við brjóta
út af þessu fyrir lykkju?

133
00:06:50,160 --> 00:06:55,110
Það þýðir að við vildum ekki fundið færslu sem
samþykkt þetta orð, en í því tilviki

134
00:06:55,110 --> 00:07:00,220
við aftur ósatt að benda að okkar
Hashtable ekki innihalda þetta orð.

135
00:07:00,220 --> 00:07:02,540
Og það er ávísun.

136
00:07:02,540 --> 00:07:04,790
>> Þannig að við skulum taka a líta á stærð.

137
00:07:04,790 --> 00:07:06,970
Nú stærð er að fara að vera nokkuð einfalt.

138
00:07:06,970 --> 00:07:11,080
Þar muna í álag, fyrir hvert orð
við fundum, við hækkaða alþjóðlegt

139
00:07:11,080 --> 00:07:12,880
breytu Hashtable stærð.

140
00:07:12,880 --> 00:07:16,480
Þannig að stærð virka er bara að fara
til að fara aftur alþjóðlegum breytu.

141
00:07:16,480 --> 00:07:18,150
Og það er það.

142
00:07:18,150 --> 00:07:22,300
>> Nú loksins, þurfum við að afferma
orðabók þegar allt er gert.

143
00:07:22,300 --> 00:07:25,340
Svo hvernig eigum við að fara að gera það?

144
00:07:25,340 --> 00:07:30,440
Hérna erum við lykkja yfir
allar fötunum borðinu okkar.

145
00:07:30,440 --> 00:07:33,240
Þannig að það eru NUM_BUCKETS fötunum.

146
00:07:33,240 --> 00:07:37,410
Og fyrir hvert tengda listanum í okkar
Hashtable, þá ætlum við að lykkja yfir

147
00:07:37,410 --> 00:07:41,070
heild á tengda listanum,
frjáls hvert frumefni.

148
00:07:41,070 --> 00:07:42,900
>> Nú þurfum við að fara varlega.

149
00:07:42,900 --> 00:07:47,910
Svo hér höfum við tímabundna breytu
sem er að geyma músina til næsta

150
00:07:47,910 --> 00:07:49,730
þáttur í tengda listanum.

151
00:07:49,730 --> 00:07:52,140
Og þá erum við að fara að losa
núverandi þáttur.

152
00:07:52,140 --> 00:07:55,990
Við þurfum að vera viss um að við gerum þetta því vér
getur ekki bara losa Opin ELEMENT

153
00:07:55,990 --> 00:07:59,180
og reyna svo að sjá næsta músina,
síðan þegar við höfum frelsi það,

154
00:07:59,180 --> 00:08:00,870
minni verður öryrki.

155
00:08:00,870 --> 00:08:04,990
>> Þannig að við þurfum að halda í kring bendi á
næsta þátt, þá getum við frjálsari

156
00:08:04,990 --> 00:08:08,360
núverandi þáttur, og þá getum við uppfært
Núverandi þáttur okkar til að benda á

157
00:08:08,360 --> 00:08:09,550
næsta þátt.

158
00:08:09,550 --> 00:08:12,800
Við munum lykkja en það eru þættir
í þessu tengda listanum.

159
00:08:12,800 --> 00:08:15,620
Við munum gera það fyrir alla tengda
listum Hashtable.

160
00:08:15,620 --> 00:08:19,460
Og þegar við erum búin með það, höfum við
alveg skipað Hashtable og

161
00:08:19,460 --> 00:08:20,190
við erum búin.

162
00:08:20,190 --> 00:08:23,200
Svo það er ómögulegt fyrir afferma
að alltaf return false.

163
00:08:23,200 --> 00:08:26,470
Og þegar við erum búin, við
bara aftur satt.

164
00:08:26,470 --> 00:08:29,000
>> Við skulum gefa þessa lausn a reyna.

165
00:08:29,000 --> 00:08:33,070
Þannig að við skulum taka a líta á það sem okkar
struct hnút mun líta út.

166
00:08:33,070 --> 00:08:36,220
Hér sjáum við að við erum að fara að hafa bool
orð og strúktúr node * börn

167
00:08:36,220 --> 00:08:37,470
krappi stafrófinu.

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

169
00:08:38,929 --> 00:08:42,020
Svo það fyrsta sem þú gætir verið
spá, hvers vegna er ALPHABET

170
00:08:42,020 --> 00:08:44,660
Ed skilgreint sem 27?

171
00:08:44,660 --> 00:08:47,900
Jæja, muna að við erum að fara að þurfa
að vera meðhöndlun úrfellingarmerki.

172
00:08:47,900 --> 00:08:51,910
Svo það er að fara að vera nokkuð
sérstakt tilfelli í þessari áætlun.

173
00:08:51,910 --> 00:08:54,710
>> Nú man hvernig trie
í raun virkar.

174
00:08:54,710 --> 00:08:59,380
Segjum að við erum flokkun orð
"kettir." Þá frá rót trie,

175
00:08:59,380 --> 00:09:02,610
við erum að fara að horfa á börnin
array, og við erum að fara að líta á

176
00:09:02,610 --> 00:09:08,090
Vísitala sem svarar til bréf
C. Svo að verða verðtryggð 2.

177
00:09:08,090 --> 00:09:11,530
Svo í ljósi þess, sem mun
gefa okkur nýja hnút.

178
00:09:11,530 --> 00:09:13,820
Og þá munum við vinna úr þeim hnút.

179
00:09:13,820 --> 00:09:17,770
>> Svo í ljósi þess hnút, erum við enn og aftur
fara að horfa á börnin fylkisins.

180
00:09:17,770 --> 00:09:22,110
Og við erum að fara að horfa á vísitölu núll
að vinna í samræmi við A í cat.

181
00:09:22,110 --> 00:09:27,170
Svo þá erum við að fara að fara til hnút,
og í ljósi þess að hnúturinn við erum að fara

182
00:09:27,170 --> 00:09:31,090
að líta á the endir það er sem a
til T. og færa til þess hnút,

183
00:09:31,090 --> 00:09:35,530
Að lokum, höfum við alveg leit
gegnum orð okkar "köttur." Og nú bool

184
00:09:35,530 --> 00:09:40,960
Orðið er ætlað að gefa til kynna hvort
þetta gefið orð er í raun orð.

185
00:09:40,960 --> 00:09:43,470
>> Svo hvers vegna þurfum við að sérstakt tilfelli?

186
00:09:43,470 --> 00:09:47,700
Jæja hvað um orðið "stórslys"
er í orðabók okkar, en

187
00:09:47,700 --> 00:09:50,150
Orðið "köttur" er það ekki?

188
00:09:50,150 --> 00:09:54,580
Svo og að leita að sjá hvort orðið "köttur"
er í orðabók okkar, við erum

189
00:09:54,580 --> 00:09:59,970
fara að tókst að líta í gegnum
Vísitölurnar C-A-T í svæðinu hnút.

190
00:09:59,970 --> 00:10:04,290
En það er einungis vegna þess að stórslys
gerðist að búa hnútar á leiðinni

191
00:10:04,290 --> 00:10:07,190
úr C-A-T, alla leið til
enda orðsins.

192
00:10:07,190 --> 00:10:12,020
Svo bool orðið er notað til að gefa til kynna hvort
þetta tiltekna staðsetningu

193
00:10:12,020 --> 00:10:14,310
reyndar táknar orð.

194
00:10:14,310 --> 00:10:15,140
>> Allt í lagi.

195
00:10:15,140 --> 00:10:19,310
Svo nú er að við vitum hvað það trie er
að fara að líta út eins og, við skulum líta á

196
00:10:19,310 --> 00:10:20,730
hlaða virka.

197
00:10:20,730 --> 00:10:24,610
Svo álag er að fara að skila bool
fyrir hvort við góðum árangri eða

198
00:10:24,610 --> 00:10:26,720
árangurslaust hlaðinn orðabókin.

199
00:10:26,720 --> 00:10:30,460
Og þetta er að fara til vera the orðabók
að við viljum að hlaða.

200
00:10:30,460 --> 00:10:33,930
>> Svo fyrsta sem við erum að gera er opinn
upp þessi orðabók fyrir lestur.

201
00:10:33,930 --> 00:10:36,160
Og við verðum að ganga úr skugga um
við gerðum ekki mistakast.

202
00:10:36,160 --> 00:10:39,580
Þannig að ef orðabók væri ekki
tókst opnaði, það mun skila

203
00:10:39,580 --> 00:10:42,400
null, í því tilviki sem við erum
fara að skila falskur.

204
00:10:42,400 --> 00:10:47,230
En miðað við að það tókst
opnaði, þá getum við í raun lesið

205
00:10:47,230 --> 00:10:48,220
gegnum orðabókina.

206
00:10:48,220 --> 00:10:50,880
>> Svo fyrsta sem við erum að fara að
vilja til að gera er að við höfum þetta

207
00:10:50,880 --> 00:10:52,500
Global breyta rót.

208
00:10:52,500 --> 00:10:56,190
Nú rót er að fara til vera a node *.

209
00:10:56,190 --> 00:10:59,760
Það er efst á trie okkar sem við erum
að fara að iterating gegnum.

210
00:10:59,760 --> 00:11:02,660
Svo the fyrstur hlutur sem við erum að fara
til að vilja gera er að úthluta

211
00:11:02,660 --> 00:11:04,140
minni rót okkar.

212
00:11:04,140 --> 00:11:07,980
Takið eftir að við erum að nota calloc
virka, sem er í grundvallaratriðum það sama

213
00:11:07,980 --> 00:11:11,500
sem malloc virka, nema það er
tryggingu til að fara aftur eitthvað sem er

214
00:11:11,500 --> 00:11:13,180
alveg zeroed út.

215
00:11:13,180 --> 00:11:17,290
Þannig að ef við notuðum malloc, vildi að við þurfum að
fara í gegnum öll ábendingum í okkar

216
00:11:17,290 --> 00:11:20,160
hnút, og ganga úr skugga um að
þeir eru allir null.

217
00:11:20,160 --> 00:11:22,710
Svo calloc mun gera það fyrir okkur.

218
00:11:22,710 --> 00:11:26,330
>> Nú bara eins malloc, þurfum við að gera
úr skugga um að úthlutun var í raun

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

220
00:11:27,520 --> 00:11:29,990
Ef þetta aftur null, þá erum við
þurft að loka eða orðabók

221
00:11:29,990 --> 00:11:32,100
skrá og aftur ósatt.

222
00:11:32,100 --> 00:11:36,835
Svo miðað við að úthlutun var
vel, við erum að fara að nota hnút *

223
00:11:36,835 --> 00:11:40,270
bendilinn iterate gegnum trie okkar.

224
00:11:40,270 --> 00:11:43,890
Svo rætur okkar aldrei að fara að breyta,
en við erum að fara að nota bendilinn til

225
00:11:43,890 --> 00:11:47,875
reyndar fara frá hnút í hnút.

226
00:11:47,875 --> 00:11:50,940
>> Svo í þetta fyrir lykkju við erum að lesa
gegnum orðabók skrá.

227
00:11:50,940 --> 00:11:53,670
Og við erum að nota fgetc.

228
00:11:53,670 --> 00:11:56,290
Fgetc er að fara að grípa einn
eðli úr skrá.

229
00:11:56,290 --> 00:11:59,370
Við erum að fara að halda áfram grabbing
stafir á meðan við ná ekki

230
00:11:59,370 --> 00:12:01,570
lok skrárinnar.

231
00:12:01,570 --> 00:12:03,480
>> Það eru tvö tilvik sem við þurfum að sinna.

232
00:12:03,480 --> 00:12:06,610
Fyrsta, ef eðli
var ekki ný lína.

233
00:12:06,610 --> 00:12:10,450
Þannig að við vitum ef það væri ný lína, þá
við erum að fara að hreyfa á til nýtt orð.

234
00:12:10,450 --> 00:12:15,240
En miðað við það var ekki ný línu, þá
Hér viljum við að reikna út

235
00:12:15,240 --> 00:12:18,380
vísitölu sem við erum að fara að kemba í
í börnin fylkingu sem

236
00:12:18,380 --> 00:12:19,810
við skoðuðum áður.

237
00:12:19,810 --> 00:12:23,880
>> Svo, eins og ég sagði áður, þurfum við að
sérstakt tilfelli úrfellingarmerki.

238
00:12:23,880 --> 00:12:26,220
Taka við erum með ternary
Rekstraraðili hér.

239
00:12:26,220 --> 00:12:29,580
Þannig að við erum að fara að lesa þetta eins og, ef
eðli sem við lesum í var

240
00:12:29,580 --> 00:12:35,330
úrfellingarmerki, þá erum við að fara að setja
Vísitala = "ALPHABET" -1, sem mun

241
00:12:35,330 --> 00:12:37,680
vera vísitala 26.

242
00:12:37,680 --> 00:12:41,130
>> Annars, ef það var ekki úrfellingarmerki, þar
við erum að fara að setja vísitölu

243
00:12:41,130 --> 00:12:43,760
jöfn c - a.

244
00:12:43,760 --> 00:12:49,030
Svo man aftur frá áður p-setur,
c - a er að fara að gefa okkur

245
00:12:49,030 --> 00:12:53,410
stafrófsröð stöðu C. Svo ef
C er bókstafurinn A, þetta verður

246
00:12:53,410 --> 00:12:54,700
gefa okkur vísitölu núll.

247
00:12:54,700 --> 00:12:58,120
Fyrir stafinn B, mun það gefa
okkur vísitalan 1, og svo framvegis.

248
00:12:58,120 --> 00:13:03,010
>> Svo það gefur okkur vísitölu inn í
börn array sem við viljum.

249
00:13:03,010 --> 00:13:08,890
Nú ef þessi vísitala er nú null í
börnin, sem þýðir að hnúturinn

250
00:13:08,890 --> 00:13:11,830
ekki fyrir hendi
frá þeirri braut.

251
00:13:11,830 --> 00:13:15,160
Þannig að við þurfum að úthluta
hnút í þeirri braut.

252
00:13:15,160 --> 00:13:16,550
Það er það sem við munum gera hér.

253
00:13:16,550 --> 00:13:20,690
>> Þannig að við erum að fara að aftur nota calloc
virka, þannig að við þurfum ekki að

254
00:13:20,690 --> 00:13:22,880
núll út allar ábendingar.

255
00:13:22,880 --> 00:13:27,240
Og við þurfum aftur að athuga
að calloc ekki mistakast.

256
00:13:27,240 --> 00:13:30,700
Ef calloc gerði ekki, þá þurfum við
að afferma allt, loka okkar

257
00:13:30,700 --> 00:13:32,820
orðabók, og return false.

258
00:13:32,820 --> 00:13:40,050
Svo miðað við að það var ekki mistakast, þá
þetta mun búa til nýtt barn fyrir okkur.

259
00:13:40,050 --> 00:13:41,930
Og þá munum við fara til barnsins.

260
00:13:41,930 --> 00:13:44,960
Bendillinn okkar mun kunnugt er
niður til að barnið.

261
00:13:44,960 --> 00:13:49,330
>> Nú ef þetta var ekki null til að byrja með,
þá bendillinn getur bara iterate

262
00:13:49,330 --> 00:13:52,590
niður til að barnið án þess að raunverulega
að þurfa að úthluta neitt.

263
00:13:52,590 --> 00:13:56,730
Þetta er raunin þar sem við gerðist fyrst
úthluta orðið "köttur". Og

264
00:13:56,730 --> 00:14:00,330
sem þýðir að þegar við förum að úthluta
"Stórslys," við þurfum ekki að búa til

265
00:14:00,330 --> 00:14:01,680
hnúta fyrir C-A-T aftur.

266
00:14:01,680 --> 00:14:04,830
Þeir eru fyrir hendi nú þegar.

267
00:14:04,830 --> 00:14:06,080
>> Hvað er þetta annað?

268
00:14:06,080 --> 00:14:10,480
Þetta er ástand þar sem C, var
sviga n, þar sem C, var nýja línu.

269
00:14:10,480 --> 00:14:13,710
Þetta þýðir að við höfum tekist
lokið orð.

270
00:14:13,710 --> 00:14:16,860
Nú hvað við viljum gera þegar við
lokið orð?

271
00:14:16,860 --> 00:14:21,100
Við erum að fara að nota þetta orð reit
inni strúktúr hnút okkar.

272
00:14:21,100 --> 00:14:23,390
Við viljum að setja það satt.

273
00:14:23,390 --> 00:14:27,150
Svo gefur til kynna að þessi hnútur
sýnir vel

274
00:14:27,150 --> 00:14:29,250
orð, í raun orðið.

275
00:14:29,250 --> 00:14:30,940
>> Nú setja það satt.

276
00:14:30,940 --> 00:14:35,150
Við viljum að endurstilla bendilinn okkar lið
að upphafi trie aftur.

277
00:14:35,150 --> 00:14:40,160
Og að lokum, vöxtur orðabók okkar
stærð, þar sem við fundið aðra vinnu.

278
00:14:40,160 --> 00:14:43,230
Þannig að við erum að fara að halda að gera það,
lestur í staf með staf,

279
00:14:43,230 --> 00:14:49,150
byggja nýja hnúta í trie okkar og
fyrir hvert orð í orðabók, þar

280
00:14:49,150 --> 00:14:54,020
við náum loks C! = EOF, þar sem
ræða við brjótast út úr skránni.

281
00:14:54,020 --> 00:14:57,050
>> Nú eru tvö tilvik undir
sem við gætum hafa högg EOF.

282
00:14:57,050 --> 00:15:00,980
Fyrsta er ef það var villa
lesa úr skrá.

283
00:15:00,980 --> 00:15:03,470
Þannig að ef það var villa, við
þarft að gera dæmigerð.

284
00:15:03,470 --> 00:15:06,460
Afferma allt, nærri
skráin, return false.

285
00:15:06,460 --> 00:15:09,810
Miðað við að það var ekki villa, að
bara þýðir að við högg í raun enda

286
00:15:09,810 --> 00:15:13,750
skráin, í því tilviki, nálægt við á
skrá og skila satt þar sem við

287
00:15:13,750 --> 00:15:17,330
tókst hlaðinn orðabók
í trie okkar.

288
00:15:17,330 --> 00:15:20,170
>> Svo nú skulum kíkja stöðva.

289
00:15:20,170 --> 00:15:25,156
Útlit á the stöðva virka, sjáum við
að stöðva er að fara að skila bool.

290
00:15:25,156 --> 00:15:29,680
Það skilar satt ef þetta orð að það er
berist er í trie okkar.

291
00:15:29,680 --> 00:15:32,110
Það skilar ósönn annars.

292
00:15:32,110 --> 00:15:36,050
Svo hvernig ætlar þú að ákveða hvort
þetta orð er í trie okkar?

293
00:15:36,050 --> 00:15:40,190
>> Við sjáum hér að, rétt eins og áður,
við erum að fara að nota bendilinn til iterate

294
00:15:40,190 --> 00:15:41,970
gegnum trie okkar.

295
00:15:41,970 --> 00:15:46,600
Nú hér erum við að fara að iterate
yfir öllu orð okkar.

296
00:15:46,600 --> 00:15:50,620
Svo iterating yfir orð sem við erum fortíð,
við erum að fara að ákveða

297
00:15:50,620 --> 00:15:56,400
Vísitala í börnin fylkingu sem
samsvarar orðinu krappi I. Þannig að þetta

298
00:15:56,400 --> 00:15:59,670
er að fara að líta nákvæmlega eins og
álag, þar sem ef orð [i]

299
00:15:59,670 --> 00:16:03,310
er úrfellingarmerki, þá viljum við
að nota vísitölu "stafrófi" - 1.

300
00:16:03,310 --> 00:16:05,350
Vegna þess að við ákveðið að það
er þar sem við erum að fara að geyma

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

302
00:16:07,100 --> 00:16:11,780
>> Annað sem við erum að fara að nota tvær minni orð
krappi I. Svo muna að orð getur

303
00:16:11,780 --> 00:16:13,920
hafa handahófi fjármögnun.

304
00:16:13,920 --> 00:16:17,540
Og svo við viljum tryggja að við erum
nota lágstafir útgáfa af hlutum.

305
00:16:17,540 --> 00:16:21,920
Og þá draga úr því að 'a' til einu sinni
aftur gefa okkur í stafrófsröð

306
00:16:21,920 --> 00:16:23,880
stöðu að eðli.

307
00:16:23,880 --> 00:16:27,680
Svo það er að fara að vera vísitölu okkar
í Börnin fylkisins.

308
00:16:27,680 --> 00:16:32,420
>> Og nú ef að vísitalan í börnin
array er núll, sem þýðir að við

309
00:16:32,420 --> 00:16:34,990
getur ekki lengur haldið áfram iterating
niður trie okkar.

310
00:16:34,990 --> 00:16:38,870
Ef það er málið, þetta orð er ekki hægt
hugsanlega verið í trie okkar.

311
00:16:38,870 --> 00:16:42,340
Síðan ef það væri, sem myndi
meina það væri leið

312
00:16:42,340 --> 00:16:43,510
niður að því orði.

313
00:16:43,510 --> 00:16:45,290
Og þú myndi aldrei lenda null.

314
00:16:45,290 --> 00:16:47,850
Svo hitta null aftur við rangar.

315
00:16:47,850 --> 00:16:49,840
Er orðið ekki í orðabókinni.

316
00:16:49,840 --> 00:16:53,660
Ef það væri ekki null, þá erum við
fara að halda áfram iterating.

317
00:16:53,660 --> 00:16:57,220
>> Þannig að við erum að fara út þar bendilinn
til að benda á að einkum

318
00:16:57,220 --> 00:16:59,760
hnút á vísitölunni.

319
00:16:59,760 --> 00:17:03,150
Við halda að gera það í gegn
allt orðið, miðað

320
00:17:03,150 --> 00:17:03,950
við aldrei högg null.

321
00:17:03,950 --> 00:17:07,220
Það þýðir að við gátum til að komast í gegnum
allt orð og finna

322
00:17:07,220 --> 00:17:08,920
hnút í okkar reyna.

323
00:17:08,920 --> 00:17:10,770
En við erum ekki alveg búin ennþá.

324
00:17:10,770 --> 00:17:12,290
>> Við viljum ekki bara koma aftur satt.

325
00:17:12,290 --> 00:17:14,770
Við viljum skila bendilinn> Word.

326
00:17:14,770 --> 00:17:18,980
Þar sem man aftur, er "köttur" er ekki
í orðabók okkar, og "stórslys"

327
00:17:18,980 --> 00:17:22,935
er, þá munum við vel okkur fá
gegnum orðið "köttur". En bendillinn

328
00:17:22,935 --> 00:17:25,760
orð mun vera rangar og ekki satt.

329
00:17:25,760 --> 00:17:30,930
Þannig að við aftur bendilinn orð til að sýna
hvort þetta hnútur er í raun orð.

330
00:17:30,930 --> 00:17:32,470
Og það er það að athuga.

331
00:17:32,470 --> 00:17:34,250
>> Þannig að við skulum kíkja stærð.

332
00:17:34,250 --> 00:17:37,350
Svo stærð er að fara að vera nokkuð auðvelt
síðan, man í álag, við erum

333
00:17:37,350 --> 00:17:41,430
incrementing orðabók stærð fyrir
hvert orð sem við lendum.

334
00:17:41,430 --> 00:17:45,350
Svo stærð er bara að fara að
aftur orðabók stærð.

335
00:17:45,350 --> 00:17:47,390
Og það er það.

336
00:17:47,390 --> 00:17:50,590
>> Svo loksins við höfum afferma.

337
00:17:50,590 --> 00:17:55,100
Svo afferma, við erum að fara að nota
endurkvæma virka til raunverulega gera allt

338
00:17:55,100 --> 00:17:56,530
af vinnu fyrir okkur.

339
00:17:56,530 --> 00:17:59,340
Svo virka okkar er að fara að
kallað á Unloader.

340
00:17:59,340 --> 00:18:01,650
Hvað er Unloader að fara að gera?

341
00:18:01,650 --> 00:18:06,580
Við sjáum hér að Unloader er að fara að
iterate yfir öll börn á

342
00:18:06,580 --> 00:18:08,410
Þetta tiltekna hnút.

343
00:18:08,410 --> 00:18:11,750
Og ef barnið hnút er ekki
null, þá erum við að fara að

344
00:18:11,750 --> 00:18:13,730
afferma barn hnút.

345
00:18:13,730 --> 00:18:18,010
>> Svo er þetta sem þú afferma endurkvæmt
öll börnin okkar.

346
00:18:18,010 --> 00:18:21,080
Þegar við erum viss um að öll börn okkar
hafa verið skipað, þá erum við

347
00:18:21,080 --> 00:18:25,210
geta losa okkur, svo
afferma okkur.

348
00:18:25,210 --> 00:18:29,460
Þetta mun vinna endurkvæmt
afferma alla trie.

349
00:18:29,460 --> 00:18:32,850
Og síðan einu sinni það er gert,
getum við bara aftur satt.

350
00:18:32,850 --> 00:18:34,210
Afferma getur ekki mistekist.

351
00:18:34,210 --> 00:18:35,710
Við erum bara frjáls hluti.

352
00:18:35,710 --> 00:18:38,870
Svo þegar við erum búin frjáls
allt aftur satt.

353
00:18:38,870 --> 00:18:40,320
Og það er það.

354
00:18:40,320 --> 00:18:41,080
Mitt nafn er Rob.

355
00:18:41,080 --> 00:18:42,426
Og þetta var Speller.

356
00:18:42,426 --> 00:18:47,830
>> [Tónlist spila]