1
00:00:00,000 --> 00:00:12,350
>> [MUSIC Playing]

2
00:00:12,350 --> 00:00:13,050
>> Rob Bowden: Hi.

3
00:00:13,050 --> 00:00:13,640
Unë jam Rob.

4
00:00:13,640 --> 00:00:16,210
Dhe'S le këtë zgjidhje jashtë.

5
00:00:16,210 --> 00:00:20,070
Pra, këtu ne jemi duke shkuar për të zbatuar
një tabelë të përgjithshme.

6
00:00:20,070 --> 00:00:24,090
Ne e shohim se nyja struct e tona
tabela do të duket si ky.

7
00:00:24,090 --> 00:00:28,710
Pra, kjo do të ketë një fjalë char
array e madhësisë gjatësi + 1.

8
00:00:28,710 --> 00:00:32,259
Mos harroni + 1, pasi maksimale
fjalë në fjalor është 45

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

10
00:00:33,130 --> 00:00:37,070
Dhe pastaj ne do të duhet një shtesë
karakter për zero backslash.

11
00:00:37,070 --> 00:00:40,870
>> Dhe pastaj hashtable tonë në çdo
kovë është duke shkuar për të ruajtur një

12
00:00:40,870 --> 00:00:42,320
listë e lidhur e nyjeve.

13
00:00:42,320 --> 00:00:44,420
Ne nuk jemi duke bërë lineare probing këtu.

14
00:00:44,420 --> 00:00:48,430
Dhe kështu që në mënyrë për të lidhur për të ardhshëm
element në kovë, ne kemi nevojë për një

15
00:00:48,430 --> 00:00:50,390
nyje struct * ardhshme.

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

17
00:00:51,110 --> 00:00:53,090
Pra, kjo është ajo që një nyje duket si.

18
00:00:53,090 --> 00:00:56,180
>> Tani këtu është deklarata
e hashtable tonë.

19
00:00:56,180 --> 00:00:59,640
Ajo do të ketë 16.834 kova.

20
00:00:59,640 --> 00:01:01,910
Por ai numër nuk ka rëndësi.

21
00:01:01,910 --> 00:01:05,450
Dhe në fund, ne do të kemi
Madhësia e globale ndryshueshme hashtable, e cila

22
00:01:05,450 --> 00:01:07,000
do të nisem si zero.

23
00:01:07,000 --> 00:01:10,760
Dhe ajo do të mbajnë gjurmët e sa
shumë fjalë janë në fjalorin tonë.

24
00:01:10,760 --> 00:01:13,710
>> Pra, le të marrin një vështrim në ngarkesë.

25
00:01:13,710 --> 00:01:16,390
Vini re se ngarkesës, ajo kthen një bool.

26
00:01:16,390 --> 00:01:20,530
Ju kthim i vërtetë në qoftë se ajo ishte sukses
ngarkuar, dhe të rreme ndryshe.

27
00:01:20,530 --> 00:01:23,990
Dhe ajo merr një const char * dictionary,
që është fjalor

28
00:01:23,990 --> 00:01:25,280
që ne duam të hapur.

29
00:01:25,280 --> 00:01:27,170
Pra, kjo është gjëja e parë
ne jemi duke shkuar për të bërë.

30
00:01:27,170 --> 00:01:29,500
>> Ne jemi duke shkuar për fopen
fjalor për lexim.

31
00:01:29,500 --> 00:01:31,680
Dhe ne do të kemi për të bërë
të sigurt se ajo pati sukses.

32
00:01:31,680 --> 00:01:35,920
Pra, në qoftë se ajo u kthye NULL, atëherë ne nuk e bëri
me sukses të hapur fjalorin.

33
00:01:35,920 --> 00:01:37,440
Dhe ne duhet të kthimit të rreme.

34
00:01:37,440 --> 00:01:41,580
Por, duke supozuar se ajo e bëri me sukses
hapur, atëherë ne duam të lexuar

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

36
00:01:42,400 --> 00:01:46,450
Pra, të mbajtur looping deri sa të gjejmë disa
arsye për të thyer nga ky lak,

37
00:01:46,450 --> 00:01:47,570
të cilat ne do të shohim.

38
00:01:47,570 --> 00:01:48,920
Pra mbani looping.

39
00:01:48,920 --> 00:01:51,780
>> Dhe tani ne jemi duke shkuar për
malloc një nyje të vetme.

40
00:01:51,780 --> 00:01:54,020
Dhe sigurisht ne kemi nevojë
të ajrit kontrolloni sërish.

41
00:01:54,020 --> 00:01:58,680
Pra, nëse mallocing nuk pati sukses, atëherë
ne duam të shkarkoj ndonjë nyje që ne

42
00:01:58,680 --> 00:02:02,590
ndodhur me malloc para, të mbyllur
fjalor dhe kthimit të rreme.

43
00:02:02,590 --> 00:02:06,830
Por duke injoruar se, duke supozuar ne
pati sukses, atëherë ne duam të përdorim fscanf

44
00:02:06,830 --> 00:02:12,400
për të lexuar një fjalë të vetme nga tonë
dictionary në nyje tonë.

45
00:02:12,400 --> 00:02:17,940
Pra, mos harroni se hyrjes> fjalë është char
tampon fjala e madhësisë LENGHTH + 1

46
00:02:17,940 --> 00:02:20,300
që ne jemi duke shkuar për të ruajtur fjalën in

47
00:02:20,300 --> 00:02:25,070
>> Pra fscanf do të kthehen me 1, për sa kohë
si ajo ishte në gjendje që me sukses

48
00:02:25,070 --> 00:02:26,750
lexuar një fjalë nga file.

49
00:02:26,750 --> 00:02:30,460
Nëse një nga një gabim ndodh, ose ne
arritur në fund të skedarit, ajo

50
00:02:30,460 --> 00:02:31,950
nuk do të kthehen 1.

51
00:02:31,950 --> 00:02:35,180
Në të cilin rast nuk ka kthim 1,
ne jemi më në fund duke shkuar për të thyer nga

52
00:02:35,180 --> 00:02:37,280
kjo loop ndërsa.

53
00:02:37,280 --> 00:02:42,770
Pra, ne shohim se një herë ne kemi sukses
lexoni një fjalë në

54
00:02:42,770 --> 00:02:48,270
entry> fjalë, atëherë ne jemi duke shkuar për të cilat
Fjala përdorur funksionin tonë të hash.

55
00:02:48,270 --> 00:02:49,580
>> Le të bëjmë një vështrim në
funksion hash.

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

57
00:02:52,430 --> 00:02:55,610
Pra, ju nuk duhet të vërtetë
për të kuptuar këtë.

58
00:02:55,610 --> 00:02:59,460
Dhe në të vërtetë ne vetëm nxorrën këtë hash
funksionojnë nga interneti.

59
00:02:59,460 --> 00:03:04,010
E vetmja gjë që ju duhet për të njohur është
se kjo merr një const char * fjalën.

60
00:03:04,010 --> 00:03:08,960
Pra, ajo është duke marrë një varg si input, dhe
kthyer një int unsigned si prodhim.

61
00:03:08,960 --> 00:03:12,360
Pra, kjo është e gjitha një funksion hash është, është ajo
merr në një input dhe ju jep një

62
00:03:12,360 --> 00:03:14,490
Indeksi në hashtable.

63
00:03:14,490 --> 00:03:18,530
>> Vini re që ne jemi moding nga NUM_BUCKETS,
në mënyrë që vlera e kthyer

64
00:03:18,530 --> 00:03:21,730
në të vërtetë është një indeks në hashtable
dhe nuk indeksi përtej

65
00:03:21,730 --> 00:03:24,320
caqeve të array.

66
00:03:24,320 --> 00:03:28,060
Pra, duke pasur parasysh se funksioni, ne jemi duke shkuar
te bej hash fjalën se ne të lexuar

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

68
00:03:29,390 --> 00:03:31,700
Dhe atëherë ne jemi duke shkuar për të përdorur
që hash për të futur

69
00:03:31,700 --> 00:03:33,750
hyrja në hashtable.

70
00:03:33,750 --> 00:03:38,520
>> Hash Tani hashtable është aktual
lidhur listë në tabelë.

71
00:03:38,520 --> 00:03:41,410
Dhe kjo është shumë e mundur
se kjo është vetëm NULL.

72
00:03:41,410 --> 00:03:44,960
Ne duam të futur hyrjen tonë në
fillimi i këtij listën e lidhur.

73
00:03:44,960 --> 00:03:48,600
Dhe kështu që ne do të kemi aktuale tonë
pikë hyrëse në çfarë hashtable

74
00:03:48,600 --> 00:03:50,380
aktualisht tregon.

75
00:03:50,380 --> 00:03:53,310
Dhe atëherë ne jemi duke shkuar për të ruajtur,
në hashtable në

76
00:03:53,310 --> 00:03:55,350
hash, hyrja aktuale.

77
00:03:55,350 --> 00:03:59,320
Pra, këto dy linja sukses futur
hyrja në fillim të

78
00:03:59,320 --> 00:04:02,260
lista e lidhur në atë indeks
në hashtable.

79
00:04:02,260 --> 00:04:04,900
>> Pasi ne jemi duke bërë me këtë, ne e dimë
se kemi gjetur një tjetër fjalë në

80
00:04:04,900 --> 00:04:07,790
fjalor, dhe ne rritje përsëri.

81
00:04:07,790 --> 00:04:13,960
Pra, ne vazhdojmë të bëjmë që deri fscanf
më në fund u kthye diçka jo-1 në

82
00:04:13,960 --> 00:04:16,950
e cila pikë mos harroni se
ne kemi nevojë për hyrjen e lirë.

83
00:04:16,950 --> 00:04:19,459
Pra, deri këtu kemi malloced një hyrje.

84
00:04:19,459 --> 00:04:21,329
Dhe ne u përpoq për të lexuar diçka
nga fjalori.

85
00:04:21,329 --> 00:04:23,910
Dhe ne nuk e ka lexuar me sukses
diçka nga fjalori, në

86
00:04:23,910 --> 00:04:26,650
këtë rast ne kemi nevojë për të liruar hyrjen
që kurrë nuk e kemi vënë në të vërtetë në

87
00:04:26,650 --> 00:04:29,140
hashtable, dhe më në fund thyejnë.

88
00:04:29,140 --> 00:04:32,750
>> Pasi ne shpërthen ne duhet të shohim, mirë,
nuk e kemi shpërthen për shkak se ka

89
00:04:32,750 --> 00:04:34,360
u lexuar një gabim nga fotografi?

90
00:04:34,360 --> 00:04:37,120
Apo nuk e kemi thyer jashtë, sepse ne
arritur në fund të dosjes?

91
00:04:37,120 --> 00:04:39,480
Nëse ka pasur një gabim, atëherë
ne duam të kthimit të rreme.

92
00:04:39,480 --> 00:04:40,930
Për shkak të ngarkesës nuk pati sukses.

93
00:04:40,930 --> 00:04:43,890
Dhe në këtë proces ne duam të shkarkoj
të gjitha fjalët që kemi lexuar në, dhe

94
00:04:43,890 --> 00:04:45,670
mbyllur fjalor file.

95
00:04:45,670 --> 00:04:48,740
>> Duke supozuar që pati sukses, atëherë ne vetëm
ende nevojë për të mbyllur fjalorin

96
00:04:48,740 --> 00:04:53,040
paraqesë, dhe më në fund kthehet e vërtetë që kemi
ngarkuar me sukses fjalor.

97
00:04:53,040 --> 00:04:54,420
Dhe kjo është ajo për të ngarkesës.

98
00:04:54,420 --> 00:04:59,020
Deri tani të kontrolluar, duke pasur parasysh një hashtable ngarkuar,
do të duket si ky.

99
00:04:59,020 --> 00:05:03,140
Pra shikoni, ajo kthen një bool, e cila është
duke shkuar për të treguar se kaluar

100
00:05:03,140 --> 00:05:07,530
në char * fjalë, nëse kaluar
në string është në fjalorin tonë.

101
00:05:07,530 --> 00:05:09,890
Pra, në qoftë se ajo është në fjalor,
në qoftë se ajo është në hashtable tonë,

102
00:05:09,890 --> 00:05:11,170
ne do të kthehet e vërtetë.

103
00:05:11,170 --> 00:05:13,380
Dhe në qoftë se kjo nuk është, ne do të kthimit të rreme.

104
00:05:13,380 --> 00:05:17,740
>> Duke pasur parasysh këtë kaloi në fjalë, ne jemi
do të hash fjalën.

105
00:05:17,740 --> 00:05:22,110
Tani një gjë e rëndësishme për të njohur është
se në ngarkesës ne e dinim se të gjithë

106
00:05:22,110 --> 00:05:23,820
fjalë ne do të jetë rasti më i ulët.

107
00:05:23,820 --> 00:05:25,820
Por këtu ne nuk jemi aq të sigurt.

108
00:05:25,820 --> 00:05:29,510
Nëse do të bëjmë një vështrim në funksion tonë të hash,
funksion ynë hash në të vërtetë

109
00:05:29,510 --> 00:05:32,700
është shtresë e jashtme e ulët çdo karakter
të fjalës.

110
00:05:32,700 --> 00:05:37,940
Pra, pavarësisht nga kapitalizimin e
fjalë, funksioni ynë hash është kthimi

111
00:05:37,940 --> 00:05:42,270
të njëjtën gjë indeksi për çfarëdo
kapitalizimi është, pasi do të ketë

112
00:05:42,270 --> 00:05:45,280
kthyer për një krejtësisht të vogla
Versioni i fjalës.

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

114
00:05:46,600 --> 00:05:49,790
Kjo është indeksi jonë është në
hashtable për këtë fjalë.

115
00:05:49,790 --> 00:05:52,940
>> Tani kjo për lak do të
iterate mbi listën e lidhur

116
00:05:52,940 --> 00:05:55,000
që ishte në atë indeks.

117
00:05:55,000 --> 00:05:59,610
Pra, vini re, ne jemi të fillimit të hyrjes
për pikë në këtë indeks.

118
00:05:59,610 --> 00:06:02,750
Ne jemi duke shkuar për të vazhduar
ndërsa hyrja! = NULL.

119
00:06:02,750 --> 00:06:07,770
Dhe mos harroni se përditësimin në treguesin
në hyrjen tonë lidhur list = entry> ardhshëm.

120
00:06:07,770 --> 00:06:14,400
Pra kemi pikën tonë të tanishëm e hyrjes në
Pika tjetër në listën e lidhur.

121
00:06:14,400 --> 00:06:19,250
>> Kështu që për çdo hyrje në listën e lidhur,
ne jemi duke shkuar për të përdorur strcasecmp.

122
00:06:19,250 --> 00:06:20,330
Kjo nuk është strcomp.

123
00:06:20,330 --> 00:06:23,780
Sepse edhe një herë, ne duam të
bëjë gjëra rast insensitively.

124
00:06:23,780 --> 00:06:27,870
Pra, ne i përdorim strcasecmp për të krahasuar
fjalë që u miratua me këtë

125
00:06:27,870 --> 00:06:31,860
Funksioni kundër fjalës
që është në këtë term.

126
00:06:31,860 --> 00:06:35,570
Nëse ai kthehet zero, që do të thotë ka pasur
një ndeshje, në të cilin rast ne duam të

127
00:06:35,570 --> 00:06:36,630
kthim i vërtetë.

128
00:06:36,630 --> 00:06:39,590
Ne me sukses gjetur
Fjala në hashtable tonë.

129
00:06:39,590 --> 00:06:43,040
>> Nëse ka nuk ishte një ndeshje, atëherë ne jemi
do të lak përsëri dhe të kërkoni në

130
00:06:43,040 --> 00:06:43,990
hyrje tjetër.

131
00:06:43,990 --> 00:06:47,640
Dhe ne do të vazhdojmë looping ndërsa ka
janë të hyra në këtë listën e lidhur.

132
00:06:47,640 --> 00:06:50,160
Çfarë ndodh nëse ne pushim
nga kjo për lak?

133
00:06:50,160 --> 00:06:55,110
Kjo do të thotë ne nuk kemi gjetur një hyrje që
përputhet këtë fjalë, në të cilin rast

134
00:06:55,110 --> 00:07:00,220
ne kthimit të rreme për të treguar se tonë
hashtable nuk e përmbajnë këtë fjalë.

135
00:07:00,220 --> 00:07:02,540
Dhe kjo është një kontroll.

136
00:07:02,540 --> 00:07:04,790
>> Pra, le të marrin një vështrim në madhësi.

137
00:07:04,790 --> 00:07:06,970
Tani madhësia do të jetë shumë e thjeshtë.

138
00:07:06,970 --> 00:07:11,080
Që kujtohet në ngarkesë, për çdo fjalë
kemi gjetur, ne incremented një globale

139
00:07:11,080 --> 00:07:12,880
Madhësia hashtable ndryshueshme.

140
00:07:12,880 --> 00:07:16,480
Pra, funksioni madhësia është vetëm do
të kthehen ndryshore globale.

141
00:07:16,480 --> 00:07:18,150
Dhe kjo është ajo.

142
00:07:18,150 --> 00:07:22,300
>> Tani së fundi, ne kemi nevojë për të shkarkoj
fjalor herë është bërë çdo gjë.

143
00:07:22,300 --> 00:07:25,340
Pra, si do të shkojmë për të bërë këtë?

144
00:07:25,340 --> 00:07:30,440
Këtu ne jemi looping mbi
të gjitha kova e tryezën tonë.

145
00:07:30,440 --> 00:07:33,240
Pra, ka NUM_BUCKETS kova.

146
00:07:33,240 --> 00:07:37,410
Dhe për çdo listën e lidhur në tonë
hashtable, ne jemi duke shkuar për lak mbi

147
00:07:37,410 --> 00:07:41,070
tërësia e listës lidhur,
liruar çdo element.

148
00:07:41,070 --> 00:07:42,900
>> Tani ne duhet të jenë të kujdesshëm.

149
00:07:42,900 --> 00:07:47,910
Pra, këtu kemi një ndryshore të përkohshme
që është ruajtjen kursorin për të ardhshëm

150
00:07:47,910 --> 00:07:49,730
element në lista lidhur.

151
00:07:49,730 --> 00:07:52,140
Dhe atëherë ne jemi duke shkuar për të lirë
element tanishme.

152
00:07:52,140 --> 00:07:55,990
Ne duhet të jetë i sigurt që ne e bëjmë këtë që nga viti ne
nuk mund vetëm të lirë elementin e tanishëm të

153
00:07:55,990 --> 00:07:59,180
dhe pastaj të përpiqet për të hyrë në treguesin e ardhshëm,
që nga një herë ne kemi liruar atë,

154
00:07:59,180 --> 00:08:00,870
kujtesës bëhet e pavlefshme.

155
00:08:00,870 --> 00:08:04,990
>> Pra, ne kemi nevojë për të mbajtur rreth një tregues për
element tjetër, atëherë ne mund të lirë

156
00:08:04,990 --> 00:08:08,360
element aktuale, dhe pastaj ne mund të rinovuar
element tonë aktuale për pikë për të

157
00:08:08,360 --> 00:08:09,550
element tjetër.

158
00:08:09,550 --> 00:08:12,800
Ne do të loop ndërsa ka elemente
në këtë listë e lidhur.

159
00:08:12,800 --> 00:08:15,620
Ne do të bëjmë që për të gjithë të lidhur
listat në hashtable.

160
00:08:15,620 --> 00:08:19,460
Dhe një herë ne jemi duke bërë me këtë, ne kemi
shkarkuar plotësisht hashtable, dhe

161
00:08:19,460 --> 00:08:20,190
ne jemi duke bërë.

162
00:08:20,190 --> 00:08:23,200
Kështu që është e pamundur për të shkarkimit
për të ndonjëherë kthimit të rreme.

163
00:08:23,200 --> 00:08:26,470
Dhe kur ne jemi bërë, ne
vetëm kthim i vërtetë.

164
00:08:26,470 --> 00:08:29,000
>> Le të japim këtë zgjidhje një provoni.

165
00:08:29,000 --> 00:08:33,070
Pra, le të marrin një vështrim në atë tona
nyje struct do të duket si.

166
00:08:33,070 --> 00:08:36,220
Këtu ne shohim ne do të kemi një bool
Fjala dhe një nyje struct * fëmijët

167
00:08:36,220 --> 00:08:37,470
alfabetit kllapa.

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

169
00:08:38,929 --> 00:08:42,020
Pra, gjëja e parë që ju mund të jetë
pyesin, pse është e alfabetit

170
00:08:42,020 --> 00:08:44,660
ed përcaktuar si 27?

171
00:08:44,660 --> 00:08:47,900
E pra, mos harroni se ne do të duhet
për të trajtimin e apostrof.

172
00:08:47,900 --> 00:08:51,910
Kështu që do të jetë disi e një
rast i veçantë gjatë këtij programi.

173
00:08:51,910 --> 00:08:54,710
>> Tani mos harroni se si një Trie
në të vërtetë punon.

174
00:08:54,710 --> 00:08:59,380
Le të thonë se ne jemi duke indeksimin fjalën
"Cats". Pastaj nga rrënja e Trie,

175
00:08:59,380 --> 00:09:02,610
ne jemi duke shkuar për të parë fëmijët
array, dhe ne do të shohim në

176
00:09:02,610 --> 00:09:08,090
Indeksi që korrespondon me letrën
C. Kështu që do të indeksuar 2.

177
00:09:08,090 --> 00:09:11,530
Pra duke pasur parasysh se, se vullneti
na japin një nyje të re.

178
00:09:11,530 --> 00:09:13,820
Dhe pastaj ne do të punojmë nga ajo nyje.

179
00:09:13,820 --> 00:09:17,770
>> Pra, duke pasur parasysh se nyjen, ne jemi edhe një herë
duke shkuar për të parë në grup fëmijëve.

180
00:09:17,770 --> 00:09:22,110
Dhe ne jemi duke shkuar për të parë në indeksin zero
të korrespondojnë me A në mace.

181
00:09:22,110 --> 00:09:27,170
Pra, atëherë ne jemi duke shkuar për të shkuar në atë nyje,
dhe duke pasur parasysh se nyja ne jemi duke shkuar

182
00:09:27,170 --> 00:09:31,090
për të parë në fund është një korrespondon
të T. Dhe të lëvizin për në atë nyje,

183
00:09:31,090 --> 00:09:35,530
më në fund, ne kemi shikuar plotësisht
nëpërmjet fjala jonë "cat". Dhe tani bool

184
00:09:35,530 --> 00:09:40,960
Fjala është menduar për të treguar nëse
kjo fjalë e dhënë është në të vërtetë një fjalë.

185
00:09:40,960 --> 00:09:43,470
>> Pra, pse nuk kemi nevojë për këtë rast të veçantë?

186
00:09:43,470 --> 00:09:47,700
E pra çfarë i fjalës "katastrofë"
është në fjalorin tonë, por

187
00:09:47,700 --> 00:09:50,150
Fjala "cat" nuk është?

188
00:09:50,150 --> 00:09:54,580
Pra, dhe duke kërkuar për të parë nëse fjala "cat"
është në fjalorin tonë, ne jemi

189
00:09:54,580 --> 00:09:59,970
do të me sukses të parë përmes
indekset C-A-T në nyje rajon.

190
00:09:59,970 --> 00:10:04,290
Por kjo është vetëm për shkak katastrofë
ndodhur për të krijuar nyjet në rrugë

191
00:10:04,290 --> 00:10:07,190
nga C-A-T, gjitha mënyra për të
fundi i fjalës.

192
00:10:07,190 --> 00:10:12,020
Pra bool fjalë është përdorur për të treguar nëse
këtë vend të veçantë

193
00:10:12,020 --> 00:10:14,310
në të vërtetë tregon një fjalë.

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

195
00:10:15,140 --> 00:10:19,310
Pra, tani që ne e dimë se çfarë është e Trie
do të duken si, le të shohim në

196
00:10:19,310 --> 00:10:20,730
ngarkesës funksion.

197
00:10:20,730 --> 00:10:24,610
Pra ngarkesës do të kthejë një bool
Sepse ne sukses apo

198
00:10:24,610 --> 00:10:26,720
pa sukses ngarkuar fjalor.

199
00:10:26,720 --> 00:10:30,460
Dhe kjo do të jetë fjalor
që ne duam të ngarkesës.

200
00:10:30,460 --> 00:10:33,930
>> Pra gjëja e parë që ne jemi të bëni është e hapur
up këtë fjalor për lexim.

201
00:10:33,930 --> 00:10:36,160
Dhe ne duhet të sigurohemi
ne nuk dështojnë.

202
00:10:36,160 --> 00:10:39,580
Pra, nëse fjalor nuk ishte
u hap me sukses, ajo do të kthehet

203
00:10:39,580 --> 00:10:42,400
null, rast në të cilin ne jemi
do të kthimit të rreme.

204
00:10:42,400 --> 00:10:47,230
Por, duke supozuar se ajo me sukses
hapur, atëherë ne në fakt mund të lexoni

205
00:10:47,230 --> 00:10:48,220
përmes fjalorit.

206
00:10:48,220 --> 00:10:50,880
>> Pra gjëja e parë që ne jemi duke shkuar për
doni të bëni është të kemi këtë

207
00:10:50,880 --> 00:10:52,500
rrënjë globale ndryshueshme.

208
00:10:52,500 --> 00:10:56,190
Tani rrënjë do të jetë një nyje *.

209
00:10:56,190 --> 00:10:59,760
Është maja e Trie sonë se ne jemi
do të iterating përmes.

210
00:10:59,760 --> 00:11:02,660
Pra, gjëja e parë që ne jemi duke shkuar
të doni të bëni është të ndajë

211
00:11:02,660 --> 00:11:04,140
kujtesës për rrënjë tonë.

212
00:11:04,140 --> 00:11:07,980
Vini re se ne jemi duke përdorur calloc
funksion, e cila është në thelb njëjtë

213
00:11:07,980 --> 00:11:11,500
si funksion malloc, përveç se është
garantuara për të kthyer diçka që është

214
00:11:11,500 --> 00:11:13,180
zeroed krejtësisht jashtë.

215
00:11:13,180 --> 00:11:17,290
Pra, nëse kemi përdorur malloc, ne do të duhet të
kalojnë nëpër të gjitha pointers në tonë

216
00:11:17,290 --> 00:11:20,160
nyje, dhe të sigurohemi që
ata janë të gjithë null.

217
00:11:20,160 --> 00:11:22,710
Pra calloc do të bëjë atë për ne.

218
00:11:22,710 --> 00:11:26,330
>> Tani ashtu si malloc, ne kemi nevojë për të bërë
i sigurt se ndarja ishte në të vërtetë

219
00:11:26,330 --> 00:11:27,520
suksesshëm.

220
00:11:27,520 --> 00:11:29,990
Nëse kjo kthye null, atëherë ne
nevojë për të mbyllur ose dictionary

221
00:11:29,990 --> 00:11:32,100
paraqesë dhe të kthimit të rreme.

222
00:11:32,100 --> 00:11:36,835
Pra, duke supozuar se alokimin u
suksesshme, ne jemi duke shkuar për të përdorur një nyje *

223
00:11:36,835 --> 00:11:40,270
kursorin për të iterate përmes Trie tonë.

224
00:11:40,270 --> 00:11:43,890
Pra, rrënjët tona kurrë nuk do të ndryshojë,
por ne jemi duke shkuar për të përdorur kursorin për të

225
00:11:43,890 --> 00:11:47,875
në fakt shkojnë nga nyje në nyje.

226
00:11:47,875 --> 00:11:50,940
>> Pra, në këtë lak për ne duke e lexuar
përmes fjalorit file.

227
00:11:50,940 --> 00:11:53,670
Dhe ne jemi duke përdorur fgetc.

228
00:11:53,670 --> 00:11:56,290
Fgetc do të kap një të vetme
karakter nga file.

229
00:11:56,290 --> 00:11:59,370
Ne jemi duke shkuar për të vazhduar grabbing
karaktere ndërsa ne nuk e arrijnë

230
00:11:59,370 --> 00:12:01,570
fund të file.

231
00:12:01,570 --> 00:12:03,480
>> Ka dy raste ne kemi nevojë për të trajtuar.

232
00:12:03,480 --> 00:12:06,610
E para, nëse karakteri
nuk ishte një linjë e re.

233
00:12:06,610 --> 00:12:10,450
Pra, ne e dimë nëse kjo ishte një linjë e re, atëherë
ne jemi gati për të lëvizur në një fjalë të re.

234
00:12:10,450 --> 00:12:15,240
Por duke supozuar se nuk ishte një linjë e re, atëherë
këtu ne duam të kuptoj se

235
00:12:15,240 --> 00:12:18,380
Indeksi ne do të indeksit në
në rrjet fëmijëve që

236
00:12:18,380 --> 00:12:19,810
kemi shikuar në para.

237
00:12:19,810 --> 00:12:23,880
>> Pra, si kam thënë më parë, ne kemi nevojë për të
rast i veçantë apostrof.

238
00:12:23,880 --> 00:12:26,220
Vini re që ne jemi duke përdorur tresh
Operatori këtu.

239
00:12:26,220 --> 00:12:29,580
Pra, ne jemi duke shkuar për të lexuar këtë si, në qoftë se
karakteri ne lexojmë në ishte një

240
00:12:29,580 --> 00:12:35,330
apostrof, atëherë ne jemi duke shkuar për të vendosur
Indeksi = "alfabetit" -1, i cili do të

241
00:12:35,330 --> 00:12:37,680
të jetë indeksi 26.

242
00:12:37,680 --> 00:12:41,130
>> Tjetër, në qoftë se ajo nuk ishte një apostrof, ka
ne jemi duke shkuar për të vendosur indeksin

243
00:12:41,130 --> 00:12:43,760
barabartë me C - a.

244
00:12:43,760 --> 00:12:49,030
Pra mbani mend, dikur prapa nga p-vë,
c - a do të na japë

245
00:12:49,030 --> 00:12:53,410
Pozita alfabetike e C. Pra, nëse
C është shkronja A, kjo do të

246
00:12:53,410 --> 00:12:54,700
na japin indeksin zero.

247
00:12:54,700 --> 00:12:58,120
Për të letrës B, ajo do të japë
na indeksi 1, dhe kështu me radhë.

248
00:12:58,120 --> 00:13:03,010
>> Pra, kjo na jep indeksin në
Fëmijët array që ne duam.

249
00:13:03,010 --> 00:13:08,890
Tani në qoftë se ky indeks është aktualisht null në
fëmijët, që do të thotë se një nyje

250
00:13:08,890 --> 00:13:11,830
nuk ekziston aktualisht
nga ajo rrugë.

251
00:13:11,830 --> 00:13:15,160
Pra, ne duhet të ndajë
një nyje për atë rrugë.

252
00:13:15,160 --> 00:13:16,550
Kjo është ajo që ne do të bëjmë këtu.

253
00:13:16,550 --> 00:13:20,690
>> Pra, ne jemi duke shkuar për të përdorur përsëri calloc
funksion, në mënyrë që ne nuk duhet të

254
00:13:20,690 --> 00:13:22,880
zero të gjitha pointers.

255
00:13:22,880 --> 00:13:27,240
Dhe ne përsëri duhet të kontrolloni
se calloc nuk dështojnë.

256
00:13:27,240 --> 00:13:30,700
Nëse calloc ka dështojnë, atëherë ne kemi nevojë
për të shkarkuar çdo gjë, të mbyllur tonë

257
00:13:30,700 --> 00:13:32,820
fjalor, dhe kthimit të rreme.

258
00:13:32,820 --> 00:13:40,050
Pra, duke supozuar se ajo nuk dështojnë, atëherë
kjo do të krijojë një fëmijë të ri për ne.

259
00:13:40,050 --> 00:13:41,930
Dhe ne do të shkojmë në atë fëmijë.

260
00:13:41,930 --> 00:13:44,960
Kursori ynë do të iterate
poshtë për atë fëmijë.

261
00:13:44,960 --> 00:13:49,330
>> Tani në qoftë se kjo nuk ishte null për të filluar me,
pastaj kursori mund vetëm të iterate

262
00:13:49,330 --> 00:13:52,590
poshtë për këtë fëmijë të vërtetë pa
pasur nevojë të ndajë asgjë.

263
00:13:52,590 --> 00:13:56,730
Ky është rasti ku ne ka ndodhur e parë
ndajë fjalën "cat." Dhe

264
00:13:56,730 --> 00:14:00,330
që do të thotë kur të shkojmë për të alokuar
"Katastrofë," ne nuk kanë nevojë për të krijuar

265
00:14:00,330 --> 00:14:01,680
nyje për C-A-T përsëri.

266
00:14:01,680 --> 00:14:04,830
Ata tashmë ekzistojnë.

267
00:14:04,830 --> 00:14:06,080
>> Çfarë është kjo tjetër?

268
00:14:06,080 --> 00:14:10,480
Kjo është gjendja ku c është
backslash n, ku c është një linjë e re.

269
00:14:10,480 --> 00:14:13,710
Kjo do të thotë se ne kemi sukses
përfunduar një fjalë.

270
00:14:13,710 --> 00:14:16,860
Tani çfarë ne duam të bëjmë kur ne
përfunduar me sukses një fjalë?

271
00:14:16,860 --> 00:14:21,100
Ne jemi duke shkuar për të përdorur këtë fushë fjalën
brenda nyjeve tonë struct.

272
00:14:21,100 --> 00:14:23,390
Ne duam të vendosur që për të vërtetë.

273
00:14:23,390 --> 00:14:27,150
Pra kjo tregon se kjo nyje
tregon një suksesshëm

274
00:14:27,150 --> 00:14:29,250
fjalë, një fjalë e vërtetë.

275
00:14:29,250 --> 00:14:30,940
>> Tani vendosur që për të vërtetë.

276
00:14:30,940 --> 00:14:35,150
Ne duam të rivendosur kursorin tonë për pikë
në fillim të Trie perseri.

277
00:14:35,150 --> 00:14:40,160
Dhe së fundi, rritje fjalorin tonë
madhësia, pasi kemi gjetur një tjetër punë.

278
00:14:40,160 --> 00:14:43,230
Pra, ne do të vazhdojmë të bëjmë atë,
lexuar në karakter me karakter,

279
00:14:43,230 --> 00:14:49,150
ndërtimin nyje të reja në Trie tonë dhe
për çdo fjalë në fjalor, deri

280
00:14:49,150 --> 00:14:54,020
ne fund arrijnë C! = EOF, në të cilën
rast kemi të thyer nga file.

281
00:14:54,020 --> 00:14:57,050
>> Tani ka dy raste nën
të cilat ne mund të ketë goditur EOF.

282
00:14:57,050 --> 00:15:00,980
E para është nëse ka pasur një gabim
leximi nga file.

283
00:15:00,980 --> 00:15:03,470
Pra, nëse ka pasur një gabim, ne
duhet të bëni tipike.

284
00:15:03,470 --> 00:15:06,460
Shkarkoj çdo gjë, në afërsi
fotografi, kthimit të rreme.

285
00:15:06,460 --> 00:15:09,810
Duke supozuar se nuk ishte një gabim, që
thjesht do të thotë që ne të vërtetë goditi në fund të

286
00:15:09,810 --> 00:15:13,750
fotografi, në të cilin rast, ne mbyllim
paraqesë dhe të kthehet e vërtetë që kemi

287
00:15:13,750 --> 00:15:17,330
ngarkuar me sukses fjalor
në Trie tonë.

288
00:15:17,330 --> 00:15:20,170
>> Pra, tani le të shikoni kontroll.

289
00:15:20,170 --> 00:15:25,156
Duke parë në funksionin e kontrollit, ne shohim
kontrolloni se do të kthehet një bool.

290
00:15:25,156 --> 00:15:29,680
Ajo jep true nëse këtë fjalë që është e
duke u kaluar është në Trie tonë.

291
00:15:29,680 --> 00:15:32,110
Ajo kthen false ndryshe.

292
00:15:32,110 --> 00:15:36,050
Pra, si jeni përcaktuar nëse
kjo fjalë është në Trie tonë?

293
00:15:36,050 --> 00:15:40,190
>> Ne shohim këtu se, ashtu si më parë,
ne jemi duke shkuar për të përdorur kursorin për të iterate

294
00:15:40,190 --> 00:15:41,970
përmes Trie tonë.

295
00:15:41,970 --> 00:15:46,600
Tani këtu ne do të iterate
mbi gjithë fjalën tonë.

296
00:15:46,600 --> 00:15:50,620
Pra iterating fjalën ne jemi e kaluara,
ne jemi duke shkuar për të përcaktuar

297
00:15:50,620 --> 00:15:56,400
Indeksi në grup fëmijëve që
korrespondon fjalës kllapa I. Pra, kjo

298
00:15:56,400 --> 00:15:59,670
do të duken tamam si
ngarkesës, ku në qoftë se fjala [i]

299
00:15:59,670 --> 00:16:03,310
është një apostrof, atëherë ne duam
për të përdorur tregues "alfabetin" - 1.

300
00:16:03,310 --> 00:16:05,350
Sepse ne kemi vendosur se cilat
është ajo ku ne jemi duke shkuar për të ruajtur

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

302
00:16:07,100 --> 00:16:11,780
>> Tjetër ne do të përdorim dy fjalë më të ulët
kllapa I. Pra, mos harroni se fjala mund të

303
00:16:11,780 --> 00:16:13,920
kanë kapitalizim arbitrare.

304
00:16:13,920 --> 00:16:17,540
Dhe kështu që ne duam të sigurohemi që ne jemi
duke përdorur një version vogle të gjërave.

305
00:16:17,540 --> 00:16:21,920
Dhe pastaj të zbriten nga ajo 'një' për herë
përsëri na jepni alfabetik

306
00:16:21,920 --> 00:16:23,880
Pozicioni i atij karakteri.

307
00:16:23,880 --> 00:16:27,680
Kështu që do të jetë indeksi tonë
në array fëmijëve.

308
00:16:27,680 --> 00:16:32,420
>> Dhe tani në rast se indeksi në fëmijët
array është null, që do të thotë ne

309
00:16:32,420 --> 00:16:34,990
mund të vazhdojë më iterating
poshtë Trie tonë.

310
00:16:34,990 --> 00:16:38,870
Në qoftë se është e rastit, kjo fjalë nuk mund të
të jetë ndoshta në Trie tonë.

311
00:16:38,870 --> 00:16:42,340
Që po të ishte, që do të
do të thotë se do të jetë një rrugë e

312
00:16:42,340 --> 00:16:43,510
poshtë për atë fjalë.

313
00:16:43,510 --> 00:16:45,290
Dhe ju nuk do të hasni null.

314
00:16:45,290 --> 00:16:47,850
Pra ndeshi null, ne kthimit të rreme.

315
00:16:47,850 --> 00:16:49,840
Fjala nuk është në fjalor.

316
00:16:49,840 --> 00:16:53,660
Po të mos ishte i pavlefshëm, atëherë ne jemi
do të vazhdojë iterating.

317
00:16:53,660 --> 00:16:57,220
>> Pra, ne jemi duke shkuar nga atje kursorin
të tregojnë për atë të veçantë

318
00:16:57,220 --> 00:16:59,760
nyjë në atë indeks.

319
00:16:59,760 --> 00:17:03,150
Ne vazhdojmë të bëjmë që të gjithë
e gjithë fjala, duke supozuar

320
00:17:03,150 --> 00:17:03,950
ne kurrë nuk goditi null.

321
00:17:03,950 --> 00:17:07,220
Kjo do të thotë që ne ishim në gjendje për të marrë me
e gjithë fjala dhe për të gjetur

322
00:17:07,220 --> 00:17:08,920
një nyje në përpjekje tonë.

323
00:17:08,920 --> 00:17:10,770
Por ne nuk jemi bërë mjaft ende.

324
00:17:10,770 --> 00:17:12,290
>> Ne nuk duam të kthehen vetëm e vërtetë.

325
00:17:12,290 --> 00:17:14,770
Ne duam të kthehen kursorit> fjalë.

326
00:17:14,770 --> 00:17:18,980
Që mos harroni përsëri, është "mace" nuk është
në fjalorin tonë, dhe "katastrofë"

327
00:17:18,980 --> 00:17:22,935
është, atëherë ne do të kemi sukses
nëpërmjet fjala "cat". Por, kursorit

328
00:17:22,935 --> 00:17:25,760
fjalë do të jetë e rreme dhe nuk është e vërtetë.

329
00:17:25,760 --> 00:17:30,930
Pra, ne kthehemi fjalë kursorin për të treguar
nëse kjo nyje është në të vërtetë një fjalë.

330
00:17:30,930 --> 00:17:32,470
Dhe kjo është ajo për kontroll.

331
00:17:32,470 --> 00:17:34,250
>> Pra, le të shikoni madhësinë.

332
00:17:34,250 --> 00:17:37,350
Pra, madhësia do të jetë goxha e lehtë
që, mos harroni në ngarkesës, ne jemi

333
00:17:37,350 --> 00:17:41,430
bën rritjen madhësinë fjalor për
çdo fjalë që hasim.

334
00:17:41,430 --> 00:17:45,350
Pra, madhësia është vetëm do të
kthehen madhësinë dictionary.

335
00:17:45,350 --> 00:17:47,390
Dhe kjo është ajo.

336
00:17:47,390 --> 00:17:50,590
>> Pra, së fundi ne kemi shkarkoj.

337
00:17:50,590 --> 00:17:55,100
Pra shkarkoj, ne do të përdorë
funksion recursive të bëjë në fakt të gjithë

338
00:17:55,100 --> 00:17:56,530
e punës për ne.

339
00:17:56,530 --> 00:17:59,340
Pra, funksioni ynë do të
të thirret në unloader.

340
00:17:59,340 --> 00:18:01,650
Çfarë është unloader do të bëni?

341
00:18:01,650 --> 00:18:06,580
Ne shohim këtu se unloader do të
iterate mbi të gjithë fëmijët në

342
00:18:06,580 --> 00:18:08,410
kjo nyje të veçantë.

343
00:18:08,410 --> 00:18:11,750
Dhe në qoftë se fëmija nuk është nyja
null, atëherë ne do të

344
00:18:11,750 --> 00:18:13,730
shkarkoj nyjen e fëmijëve.

345
00:18:13,730 --> 00:18:18,010
>> Pra, kjo është që ju Recursively shkarkoj
të gjithë fëmijët tanë.

346
00:18:18,010 --> 00:18:21,080
Pasi ne jemi të sigurt që të gjithë fëmijët tanë
janë shkarkuar, atëherë ne

347
00:18:21,080 --> 00:18:25,210
mund të lirë veten, kështu që
shkarkoj veten.

348
00:18:25,210 --> 00:18:29,460
Kjo do të punojë Recursively
shkarkoj gjithë Trie.

349
00:18:29,460 --> 00:18:32,850
Dhe pastaj një herë që është bërë,
ne vetëm mund të kthehet e vërtetë.

350
00:18:32,850 --> 00:18:34,210
Shkarkoj nuk mund të dështojë.

351
00:18:34,210 --> 00:18:35,710
Ne jemi vetëm liruar gjëra.

352
00:18:35,710 --> 00:18:38,870
Pra, një herë ne jemi duke bërë liruar
gjithçka, kthim i vërtetë.

353
00:18:38,870 --> 00:18:40,320
Dhe kjo është ajo.

354
00:18:40,320 --> 00:18:41,080
Emri im është Rob.

355
00:18:41,080 --> 00:18:42,426
Dhe kjo ishte speller.

356
00:18:42,426 --> 00:18:47,830
>> [MUSIC Playing]