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

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

3
00:00:13,050 --> 00:00:13,640
Som Rob.

4
00:00:13,640 --> 00:00:16,210
A nech je to riešenie von.

5
00:00:16,210 --> 00:00:20,070
Takže tu budeme realizovať
všeobecné tabuľky.

6
00:00:20,070 --> 00:00:24,090
Vidíme, že struct uzol našej
tabuľka bude vyzerať takto.

7
00:00:24,090 --> 00:00:28,710
Takže to bude mať char slovo
Pole Veľkosť Dĺžka + 1.

8
00:00:28,710 --> 00:00:32,259
Nezabudnite + 1, pretože maximálna
slovo v slovníku je 45

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

10
00:00:33,130 --> 00:00:37,070
A potom budeme potrebovať jeden navyše
znak pre spätné lomítko nulu.

11
00:00:37,070 --> 00:00:40,870
>> A potom naše Hashtable v každom
vedro sa bude ukladať

12
00:00:40,870 --> 00:00:42,320
spájať zoznam uzlov.

13
00:00:42,320 --> 00:00:44,420
Nerobíme lineárne snímacie tu.

14
00:00:44,420 --> 00:00:48,430
A tak, aby odkazy na ďalšie
prvok v vedre, musíme

15
00:00:48,430 --> 00:00:50,390
struct uzol * ďalšie.

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

17
00:00:51,110 --> 00:00:53,090
Takže to je to, čo uzol vyzerá.

18
00:00:53,090 --> 00:00:56,180
>> Teraz je tu vyhlásenie
našej Hashtable.

19
00:00:56,180 --> 00:00:59,640
Bude to mať 16.834 vedierka.

20
00:00:59,640 --> 00:01:01,910
Ale to číslo nezáleží.

21
00:01:01,910 --> 00:01:05,450
A konečne budeme mať
globálna premenná veľkosť Hashtable, ktoré

22
00:01:05,450 --> 00:01:07,000
sa chystá začať ako nula.

23
00:01:07,000 --> 00:01:10,760
A to bude mať prehľad o tom, ako
veľa slov sú v našom slovníku.

24
00:01:10,760 --> 00:01:13,710
>> Takže poďme sa pozrieť na zaťaženie.

25
00:01:13,710 --> 00:01:16,390
Všimnite si, že záťaž, vracia bool.

26
00:01:16,390 --> 00:01:20,530
Môžete sa vrátiť true, ak bolo úspešné
naložené, a v opačnom prípade false.

27
00:01:20,530 --> 00:01:23,990
A to trvá const char * slovníka,
čo je slovník

28
00:01:23,990 --> 00:01:25,280
ktorý chceme otvoriť.

29
00:01:25,280 --> 00:01:27,170
Takže to je prvá vec,
budeme robiť.

30
00:01:27,170 --> 00:01:29,500
>> Ideme do fopen
slovník čítanie.

31
00:01:29,500 --> 00:01:31,680
A budeme musieť urobiť
Uistite sa, že sa jej podarilo.

32
00:01:31,680 --> 00:01:35,920
Takže ak to vrátil NULL, potom nie
úspešne otvoriť slovník.

33
00:01:35,920 --> 00:01:37,440
A my sa musíme vrátiť false.

34
00:01:37,440 --> 00:01:41,580
Ale za predpokladu, že to úspešne urobil
otvorené, potom chceme prečítať

35
00:01:41,580 --> 00:01:42,400
slovník.

36
00:01:42,400 --> 00:01:46,450
Takže majte opakovanie, kým nenájdeme nejaký
dôvod, aby sa vymanili z tejto slučky,

37
00:01:46,450 --> 00:01:47,570
ktoré uvidíme.

38
00:01:47,570 --> 00:01:48,920
Takže majte opakovanie.

39
00:01:48,920 --> 00:01:51,780
>> A teraz ideme na
malloc jeden uzol.

40
00:01:51,780 --> 00:01:54,020
A samozrejme musíme
vysielať znovu skontrolujte.

41
00:01:54,020 --> 00:01:58,680
Takže ak mallocing neuspel, potom
chceme vyložiť ľubovoľný uzol, ktorý my

42
00:01:58,680 --> 00:02:02,590
stalo malloc pred zavrite
slovník a vráti false.

43
00:02:02,590 --> 00:02:06,830
Ale ignorovať, že za predpokladu, že sa
podarilo, potom chceme použiť fscanf

44
00:02:06,830 --> 00:02:12,400
prečítať jediné slovo z našej
slovník do nášho uzla.

45
00:02:12,400 --> 00:02:17,940
Takže pamätajte, že vstupné slovo> je char
Slovo vyrovnávaciu pamäť o veľkosti lenghth + 1

46
00:02:17,940 --> 00:02:20,300
že budeme ukladať slovo palcov

47
00:02:20,300 --> 00:02:25,070
>> Takže fscanf bude vrátiť 1, ak
ako to bolo schopné úspešne

48
00:02:25,070 --> 00:02:26,750
čítať slovo zo súboru.

49
00:02:26,750 --> 00:02:30,460
Pokiaľ to buď chyba sa stane, alebo sa
dostať sa na koniec súboru,

50
00:02:30,460 --> 00:02:31,950
nevráti 1..

51
00:02:31,950 --> 00:02:35,180
V takomto prípade nevracia 1,
sme sa konečne chystá vypuknúť

52
00:02:35,180 --> 00:02:37,280
Tento cyklus while.

53
00:02:37,280 --> 00:02:42,770
Takže vidíme, že raz sa nám podarilo mať
čítať slovo do

54
00:02:42,770 --> 00:02:48,270
entry> slovo, potom ideme na to
Slovo pomocou nášho hash funkcie.

55
00:02:48,270 --> 00:02:49,580
>> Poďme sa pozrieť na
funkcia hash.

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

57
00:02:52,430 --> 00:02:55,610
Takže nemáte naozaj potrebujete
to pochopiť.

58
00:02:55,610 --> 00:02:59,460
A vlastne sme práve vytiahol tento hash
funkcie z internetu.

59
00:02:59,460 --> 00:03:04,010
Jediná vec, ktorú je potrebné si uvedomiť, je
že to trvá const char * slovo.

60
00:03:04,010 --> 00:03:08,960
Tak to trvá reťazec ako vstup, a
vrátením unsigned int ako výstup.

61
00:03:08,960 --> 00:03:12,360
Tak to je všetko, funkcia hash je, je to
berie na vstup a dá vám

62
00:03:12,360 --> 00:03:14,490
index do Hashtable.

63
00:03:14,490 --> 00:03:18,530
>> Všimnite si, že sme moding by NUM_BUCKETS,
tak, že vrátená hodnota

64
00:03:18,530 --> 00:03:21,730
v skutočnosti je index do Hashtable
a nie je index za

65
00:03:21,730 --> 00:03:24,320
medze poľa.

66
00:03:24,320 --> 00:03:28,060
Takže za predpokladu, že funkcie, ideme
hash slovo, ktoré čítame

67
00:03:28,060 --> 00:03:29,390
slovník.

68
00:03:29,390 --> 00:03:31,700
A potom budeme používať
že hashovacie vložiť

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

70
00:03:33,750 --> 00:03:38,520
>> Teraz Hashtable hash je aktuálne
spojené zoznamu v tabuľke.

71
00:03:38,520 --> 00:03:41,410
A to je veľmi možné,
že je to len NULL.

72
00:03:41,410 --> 00:03:44,960
Chceme vložiť náš vstup na
začiatku tohto prepojeného zoznamu.

73
00:03:44,960 --> 00:03:48,600
A tak budeme mať našu aktuálnu
vstupný bod do akej Hashtable

74
00:03:48,600 --> 00:03:50,380
V súčasnej dobe poukazuje na.

75
00:03:50,380 --> 00:03:53,310
A potom budeme ukladať,
v Hashtable na

76
00:03:53,310 --> 00:03:55,350
hash, aktuálny záznam.

77
00:03:55,350 --> 00:03:59,320
Takže tieto dva riadky úspešne vložiť
Vstup na začiatku

78
00:03:59,320 --> 00:04:02,260
spájať zoznam v tomto indexe
v Hashtable.

79
00:04:02,260 --> 00:04:04,900
>> Akonáhle sme hotoví s tým, vieme,
že sme našli ďalšie slovo

80
00:04:04,900 --> 00:04:07,790
slovník, a my sme opäť zvyšovať.

81
00:04:07,790 --> 00:04:13,960
Tak sme to robiť, kým fscanf
nakoniec sa vrátil niečo non-1 na

82
00:04:13,960 --> 00:04:16,950
ktorý bod si uvedomiť, že
musíme vstup zadarmo.

83
00:04:16,950 --> 00:04:19,459
Tak tu sme malloced položku.

84
00:04:19,459 --> 00:04:21,329
A my sme sa snažili niečo prečítať
zo slovníka.

85
00:04:21,329 --> 00:04:23,910
A my sme nemali úspešne čítať
niečo zo slovníka, v

86
00:04:23,910 --> 00:04:26,650
takomto prípade musíme uvoľniť vstup
že sme vlastne nikdy dať do

87
00:04:26,650 --> 00:04:29,140
Hashtable, a konečne zlomiť.

88
00:04:29,140 --> 00:04:32,750
>> Potom, čo sme vypukne musíme vidieť, dobre,
sme sa zlomiť, pretože tam

89
00:04:32,750 --> 00:04:34,360
bola chyba pri čítaní zo súboru?

90
00:04:34,360 --> 00:04:37,120
Alebo sme sa zlomiť, pretože sme
došli na koniec súboru?

91
00:04:37,120 --> 00:04:39,480
Ak došlo k chybe, potom
Chceme sa vrátiť false.

92
00:04:39,480 --> 00:04:40,930
Vzhľadom k tomu, zaťaženie neuspel.

93
00:04:40,930 --> 00:04:43,890
A v tomto procese chceme vyložiť
všetky slová, ktoré čítame v, a

94
00:04:43,890 --> 00:04:45,670
zatvorte súbor slovníka.

95
00:04:45,670 --> 00:04:48,740
>> Za predpokladu, že sme sa to podarí, potom sme len
Stále je potrebné zavrieť slovník

96
00:04:48,740 --> 00:04:53,040
súbor, a nakoniec sa vrátiť true, pretože sme
úspešne načítaný slovníka.

97
00:04:53,040 --> 00:04:54,420
A to je pre zaťaženie.

98
00:04:54,420 --> 00:04:59,020
Takže teraz zistiť, vzhľadom k tomu naložené Hashtable,
bude vyzerať takto.

99
00:04:59,020 --> 00:05:03,140
Tak sa pozrite, vracia bool, ktorý je
bude uvádzať, či prešiel

100
00:05:03,140 --> 00:05:07,530
v char * slovo, či už prešiel
v reťazci je v našom slovníku.

101
00:05:07,530 --> 00:05:09,890
Takže, ak je v slovníku,
v prípade, že je v našom Hashtable,

102
00:05:09,890 --> 00:05:11,170
budeme vráti hodnotu true.

103
00:05:11,170 --> 00:05:13,380
A ak to tak nie je, vrátime false.

104
00:05:13,380 --> 00:05:17,740
>> Vzhľadom k tomu, to prešiel v slove, my sme
bude hash slovo.

105
00:05:17,740 --> 00:05:22,110
Teraz dôležité si uvedomiť, je
že v záťaži vedeli sme, že všetky

106
00:05:22,110 --> 00:05:23,820
slová, že budeme mať malé písmená.

107
00:05:23,820 --> 00:05:25,820
Ale tu nie sme tak istí.

108
00:05:25,820 --> 00:05:29,510
Ak sa pozrieme na náš hash funkcie,
naše hash funkcia vlastne

109
00:05:29,510 --> 00:05:32,700
je nižšia plášť každý znak
slová.

110
00:05:32,700 --> 00:05:37,940
Takže bez ohľadu na kapitalizácie
Slovo, náš hash funkcia je návrat

111
00:05:37,940 --> 00:05:42,270
rovnaký index na čokoľvek
kapitalizácie je, ako to bude mať

112
00:05:42,270 --> 00:05:45,280
sa vrátil k úplne malá
verzie slová.

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

114
00:05:46,600 --> 00:05:49,790
To je náš index je do
Hashtable pre toto slovo.

115
00:05:49,790 --> 00:05:52,940
>> Teraz to pre sláčiky bude
iterácii spojovaceho zoznamu

116
00:05:52,940 --> 00:05:55,000
ktorá bola v danom indexe.

117
00:05:55,000 --> 00:05:59,610
Takže všimnete sme inicializácii vstup
poukázať na danom indexe.

118
00:05:59,610 --> 00:06:02,750
Budeme pokračovať
zatiaľ čo vstup! = NULL.

119
00:06:02,750 --> 00:06:07,770
A nezabudnite, že aktualizácia ukazovateľ
v našom súvisí položka v zozname = entry> ďalšie.

120
00:06:07,770 --> 00:06:14,400
Takže máme aktuálne vstupný bod do
Ďalším bodom v prepojenom zozname.

121
00:06:14,400 --> 00:06:19,250
>> Takže pre každú položku v prepojenom zoznamu,
budeme používať strcasecmp.

122
00:06:19,250 --> 00:06:20,330
Nie je to StrComp.

123
00:06:20,330 --> 00:06:23,780
Pretože raz, chceme
robiť veci prípad necitlivo.

124
00:06:23,780 --> 00:06:27,870
Tak sme sa použiť strcasecmp k porovnání
Slovo, ktoré bolo prešiel tento

125
00:06:27,870 --> 00:06:31,860
funkcia proti slovu
že je v tejto položke.

126
00:06:31,860 --> 00:06:35,570
Ak sa vráti nulu, to znamená, že je
Zápas, v ktorom prípade chceme, aby

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

128
00:06:36,630 --> 00:06:39,590
Úspešne sme našli
Slovo v našom Hashtable.

129
00:06:39,590 --> 00:06:43,040
>> V prípade, že nebol zápas, potom sme
ísť na slučku znova a pozrieť sa na

130
00:06:43,040 --> 00:06:43,990
ďalší záznam.

131
00:06:43,990 --> 00:06:47,640
A budeme pokračovať smyčkování zatiaľ čo
sú položky v tejto aplikácii v zozname.

132
00:06:47,640 --> 00:06:50,160
Čo sa stane, keď sa rozídeme
z toho pre sláčiky?

133
00:06:50,160 --> 00:06:55,110
To znamená, že sme nemali nájsť položku, ktorá
uzavreté toto slovo, v tom prípade

134
00:06:55,110 --> 00:07:00,220
vrátime false čo znamená, že naše
Hashtable neobsahuje slovo.

135
00:07:00,220 --> 00:07:02,540
A to je kontrola.

136
00:07:02,540 --> 00:07:04,790
>> Takže poďme sa pozrieť na veľkosti.

137
00:07:04,790 --> 00:07:06,970
Teraz veľkosť bude veľmi jednoduchý.

138
00:07:06,970 --> 00:07:11,080
Vzhľadom k tomu, pamätajte na zaťaženie, pre každé slovo
sme zistili, sme sa zvyšuje globálny

139
00:07:11,080 --> 00:07:12,880
variabilná veľkosť Hashtable.

140
00:07:12,880 --> 00:07:16,480
Takže funkcia veľkosť je práve deje
vrátiť globálne premenné.

141
00:07:16,480 --> 00:07:18,150
A to je všetko.

142
00:07:18,150 --> 00:07:22,300
>> Teraz konečne, musíme uvoľniť
slovník raz všetko hotové.

143
00:07:22,300 --> 00:07:25,340
Tak ako budeme robiť, že?

144
00:07:25,340 --> 00:07:30,440
Práve tu sme smyčkování cez
všetky vedierka nášho stola.

145
00:07:30,440 --> 00:07:33,240
Takže tam sú NUM_BUCKETS vedierka.

146
00:07:33,240 --> 00:07:37,410
A pre každú aplikáciu v zozname v našej
Hashtable, ideme do slučky cez

147
00:07:37,410 --> 00:07:41,070
celistvosť prepojeného zoznamu,
uvoľní každý prvok.

148
00:07:41,070 --> 00:07:42,900
>> Teraz musíme byť opatrní.

149
00:07:42,900 --> 00:07:47,910
Takže tu máme dočasnú premennú
to je ukladanie ukazovateľ na ďalšie

150
00:07:47,910 --> 00:07:49,730
prvok v prepojenom zozname.

151
00:07:49,730 --> 00:07:52,140
A potom budeme zadarmo
aktuálny prvok.

152
00:07:52,140 --> 00:07:55,990
Musíme si byť istí, že sme to urobiť, pretože my
nemôže len tak uvoľniť aktuálneho prvku

153
00:07:55,990 --> 00:07:59,180
a potom skúste prejdite na ďalší ukazovateľ,
pretože akonáhle sme oslobodil ho,

154
00:07:59,180 --> 00:08:00,870
pamäť sa stáva neplatnou.

155
00:08:00,870 --> 00:08:04,990
>> Takže musíme držať okolo ukazovateľ na
Ďalší prvok, potom sa môžeme oslobodiť

156
00:08:04,990 --> 00:08:08,360
aktuálny prvok, a potom sa môžeme aktualizovať
Naše aktuálne prvok poukázať na

157
00:08:08,360 --> 00:08:09,550
ďalší prvok.

158
00:08:09,550 --> 00:08:12,800
Budeme slučky, zatiaľ čo tam sú prvky,
v tomto prepojenom zozname.

159
00:08:12,800 --> 00:08:15,620
Urobíme to pre všetky spojené
Zoznamy v Hashtable.

160
00:08:15,620 --> 00:08:19,460
A akonáhle sme skončili s tým, máme
úplne vyložený Hashtable a

161
00:08:19,460 --> 00:08:20,190
sme hotoví.

162
00:08:20,190 --> 00:08:23,200
Tak to je nemožné pre odľahčenie
niekedy vráti false.

163
00:08:23,200 --> 00:08:26,470
A keď sme hotoví, môžeme
len vrátiť true.

164
00:08:26,470 --> 00:08:29,000
>> Dajme toto riešenie vyskúšať.

165
00:08:29,000 --> 00:08:33,070
Takže poďme sa pozrieť na to, čo naše
struct uzol bude vyzerať.

166
00:08:33,070 --> 00:08:36,220
Tu vidíme, že budeme mať bool
slovo a struct uzol * deti

167
00:08:36,220 --> 00:08:37,470
držiak abecedu.

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

169
00:08:38,929 --> 00:08:42,020
Takže prvá vec, ktorú by mohlo byť
premýšľal, prečo je abecedu

170
00:08:42,020 --> 00:08:44,660
ed definovaná ako 27?

171
00:08:44,660 --> 00:08:47,900
No, pamätajte, že budeme potrebovať
sa spracovanie apostrof.

172
00:08:47,900 --> 00:08:51,910
Tak, že to bude trochu
Osobitný prípad v celom programe.

173
00:08:51,910 --> 00:08:54,710
>> Teraz si spomenúť, ako trie
skutočne funguje.

174
00:08:54,710 --> 00:08:59,380
Povedzme, že sme indexovanie slovo
"Mačky". Potom z koreňa trie,

175
00:08:59,380 --> 00:09:02,610
ideme sa pozrieť na deti
pole, a budeme sa pozerať na

176
00:09:02,610 --> 00:09:08,090
index, ktorý odpovedá na list
C. Tak, že budú indexované 2.

177
00:09:08,090 --> 00:09:11,530
Takže vzhľadom k tomu, že bude
nám nový uzol.

178
00:09:11,530 --> 00:09:13,820
A potom budeme pracovať od tohto uzla.

179
00:09:13,820 --> 00:09:17,770
>> Takže za predpokladu, že uzol, sme opäť
sa pozrieme na detskom poľa.

180
00:09:17,770 --> 00:09:22,110
A budeme sa pozerať na indexe nula
tak, aby zodpovedal A v mačky.

181
00:09:22,110 --> 00:09:27,170
Takže sme ísť do tohto uzla,
a vzhľadom k tomu, že uzol ideme

182
00:09:27,170 --> 00:09:31,090
pozerať sa na konci to je a zodpovedá
na T. a pohybuje sa na tomto uzle,

183
00:09:31,090 --> 00:09:35,530
Nakoniec sme úplne pozrel
cez naše slovo "mačka". A teraz bool

184
00:09:35,530 --> 00:09:40,960
Slovo má ukázať, či
to dané slovo je vlastne slovo.

185
00:09:40,960 --> 00:09:43,470
>> Tak prečo potrebujeme ten zvláštny prípad?

186
00:09:43,470 --> 00:09:47,700
No, čo slovo "katastrofa"
je v našom slovníku, ale

187
00:09:47,700 --> 00:09:50,150
slovo "mačka" je nie?

188
00:09:50,150 --> 00:09:54,580
Tak a chcú zistiť, či slovo "mačka"
je v našom slovníku, sme

189
00:09:54,580 --> 00:09:59,970
bude úspešne prezrieť
Indexy C-A-T v oblasti uzla.

190
00:09:59,970 --> 00:10:04,290
Ale to je len preto, že katastrofa
sa stalo vytvorenie uzlov na ceste

191
00:10:04,290 --> 00:10:07,190
z C-A-T, až do
koniec slova.

192
00:10:07,190 --> 00:10:12,020
Takže bool slovo sa používa na označenie, či
Tento konkrétny miesto

193
00:10:12,020 --> 00:10:14,310
vlastne označuje slovo.

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

195
00:10:15,140 --> 00:10:19,310
Takže teraz, keď vieme, čo to trie je
bude vyzerať, poďme sa pozrieť na

196
00:10:19,310 --> 00:10:20,730
načítať funkciu.

197
00:10:20,730 --> 00:10:24,610
Takže zaťaženie sa chystá vrátiť bool
na tom, či sa nám podarilo alebo

198
00:10:24,610 --> 00:10:26,720
neúspešne načítať slovník.

199
00:10:26,720 --> 00:10:30,460
A to sa bude slovník
ktoré chceme načítať.

200
00:10:30,460 --> 00:10:33,930
>> Takže prvá vec, ktorú máme urobiť, je otvoriť
do tohto slovníka pre čítanie.

201
00:10:33,930 --> 00:10:36,160
A musíme sa uistiť,
sme neprepadli.

202
00:10:36,160 --> 00:10:39,580
Takže v prípade, že nebola slovník
úspešne otvorený, vráti

203
00:10:39,580 --> 00:10:42,400
null, v tomto prípade sme
chystá sa vrátiť false.

204
00:10:42,400 --> 00:10:47,230
Avšak za predpokladu, že sa úspešne
otvoril, potom môžeme skutočne čítať

205
00:10:47,230 --> 00:10:48,220
pomocou slovníka.

206
00:10:48,220 --> 00:10:50,880
>> Takže prvá vec, ktorú budeme
chcete urobiť, je, že sme si to

207
00:10:50,880 --> 00:10:52,500
globálna premenná koreň.

208
00:10:52,500 --> 00:10:56,190
Teraz koreň bude uzol *.

209
00:10:56,190 --> 00:10:59,760
Je to vrchol našej trie, že sme
bude iterácie.

210
00:10:59,760 --> 00:11:02,660
Takže prvá vec, ktorú budeme
chcieť urobiť, je rozdeliť

211
00:11:02,660 --> 00:11:04,140
pamäť pre náš koreň.

212
00:11:04,140 --> 00:11:07,980
Všimnite si, že sme pomocou calloc
funkcia, ktorá je v podstate rovnaká

213
00:11:07,980 --> 00:11:11,500
ako funkcia malloc, okrem toho, že je
zaručené, že vráti niečo, čo je

214
00:11:11,500 --> 00:11:13,180
úplne vynuluje.

215
00:11:13,180 --> 00:11:17,290
Takže ak sme použili malloc, potrebovali by sme, aby
prejsť všetky ukazovatele v našej

216
00:11:17,290 --> 00:11:20,160
uzol, a uistite sa, že
všetci sú null.

217
00:11:20,160 --> 00:11:22,710
Takže calloc to urobí za nás.

218
00:11:22,710 --> 00:11:26,330
>> Teraz, rovnako ako malloc, potrebujeme, aby sa
Uistite sa, že rozdelenie bolo v skutočnosti

219
00:11:26,330 --> 00:11:27,520
úspešný.

220
00:11:27,520 --> 00:11:29,990
Ak to vrátil null, potom
je potrebné uzavrieť alebo slovník

221
00:11:29,990 --> 00:11:32,100
súboru a vráti false.

222
00:11:32,100 --> 00:11:36,835
Takže za predpokladu, že rozdelenie bolo
úspešná, budeme používať uzol *

223
00:11:36,835 --> 00:11:40,270
kurzor iterovat našej trie.

224
00:11:40,270 --> 00:11:43,890
Takže naše korene nikdy nezmení,
ale budeme používať kurzor

225
00:11:43,890 --> 00:11:47,875
skutočne ísť z uzla do uzla.

226
00:11:47,875 --> 00:11:50,940
>> Takže v tomto cykle for sme čítanie
prostredníctvom súboru slovníka.

227
00:11:50,940 --> 00:11:53,670
A my sme pomocou fgetc.

228
00:11:53,670 --> 00:11:56,290
Fgetc sa chystá chytiť jeden
znak zo súboru.

229
00:11:56,290 --> 00:11:59,370
Budeme pokračovať v popada
znaky, zatiaľ čo my nedosahujú

230
00:11:59,370 --> 00:12:01,570
koniec súboru.

231
00:12:01,570 --> 00:12:03,480
>> Existujú dva prípady, ktoré musíme zvládnuť.

232
00:12:03,480 --> 00:12:06,610
Prvý z nich, v prípade, že znak
nebol nový riadok.

233
00:12:06,610 --> 00:12:10,450
Takže vieme, že keby to bola nová linka, potom
chystáme sa prejsť na nové slovo.

234
00:12:10,450 --> 00:12:15,240
Ale za predpokladu, že nebol nový riadok, potom
tu chceme zistiť,

235
00:12:15,240 --> 00:12:18,380
index ideme do indexu do
v detskom pole, ktoré

236
00:12:18,380 --> 00:12:19,810
sme sa pozreli na pred.

237
00:12:19,810 --> 00:12:23,880
>> Takže, ako som už povedal, musíme
Zvláštnym prípadom apostrof.

238
00:12:23,880 --> 00:12:26,220
Všimnite si, sme pomocou ternárnu
Tu operátor.

239
00:12:26,220 --> 00:12:29,580
Takže budeme čítať to ako, ak
charakter čítame v bol

240
00:12:29,580 --> 00:12:35,330
apostrof, potom ideme do nastavenia
index = "abecedu" -1, ktorá bude

241
00:12:35,330 --> 00:12:37,680
byť index 26.

242
00:12:37,680 --> 00:12:41,130
>> Inak, ak to nie je apostrof, že
budeme nastaviť index

243
00:12:41,130 --> 00:12:43,760
rovná c -.

244
00:12:43,760 --> 00:12:49,030
Takže pamätajte späť z už p-sad,
c - bude nám

245
00:12:49,030 --> 00:12:53,410
abecedný pozície C. Takže ak
C je písmeno, to bude

246
00:12:53,410 --> 00:12:54,700
nám index nula.

247
00:12:54,700 --> 00:12:58,120
Pre bod B, dá
nám index 1, a tak ďalej.

248
00:12:58,120 --> 00:13:03,010
>> Tak to nám dáva index do
deti polia, ktoré chceme.

249
00:13:03,010 --> 00:13:08,890
Teraz, ak tento index je v súčasnej dobe v null
deti, to znamená, že uzol

250
00:13:08,890 --> 00:13:11,830
v súčasnej dobe neexistuje
z tejto cesty.

251
00:13:11,830 --> 00:13:15,160
Takže musíme prideliť
uzol pre túto cestu.

252
00:13:15,160 --> 00:13:16,550
To je to, čo budeme robiť.

253
00:13:16,550 --> 00:13:20,690
>> Takže budeme znovu použiť calloc
funkcie, takže sme sa nemuseli

254
00:13:20,690 --> 00:13:22,880
nula sa všetky ukazovatele.

255
00:13:22,880 --> 00:13:27,240
A opäť je potrebné skontrolovať
že calloc nesklamal.

256
00:13:27,240 --> 00:13:30,700
Ak calloc to nepodarí, potom musíme
vyložiť všetko, zatvoríme

257
00:13:30,700 --> 00:13:32,820
slovník, a vráti false.

258
00:13:32,820 --> 00:13:40,050
Takže za predpokladu, že to nebolo zlyhanie, potom
to bude vytvoriť novú dieťa na nás.

259
00:13:40,050 --> 00:13:41,930
A potom pôjdeme k tomuto dieťaťu.

260
00:13:41,930 --> 00:13:44,960
Naše kurzor bude prechádzať
sa k tomuto dieťaťu.

261
00:13:44,960 --> 00:13:49,330
>> Teraz, ak to nie je null začať s,
potom sa kurzor môže iba iterovat

262
00:13:49,330 --> 00:13:52,590
sa k tomuto dieťaťu, bez toho by v skutočnosti
museli prideliť nič.

263
00:13:52,590 --> 00:13:56,730
To je prípad, kedy sme sa prvýkrát stalo
prideliť slovo "mačka". A

264
00:13:56,730 --> 00:14:00,330
to znamená, že keď ideme na pridelenie
"Katastrofa", nepotrebujeme vytvárať

265
00:14:00,330 --> 00:14:01,680
uzly pre C-A-T znova.

266
00:14:01,680 --> 00:14:04,830
Už existujú.

267
00:14:04,830 --> 00:14:06,080
>> Čo je to inde?

268
00:14:06,080 --> 00:14:10,480
To je stav, kedy c je
spätné lomítko n, kde c je nová linka.

269
00:14:10,480 --> 00:14:13,710
To znamená, že sa nám podarilo mať
dokončil slovo.

270
00:14:13,710 --> 00:14:16,860
A teraz, čo chceme robiť, keď sme
úspešne dokončil slovo?

271
00:14:16,860 --> 00:14:21,100
Budeme používať toto slovo pole
v našej struct uzol.

272
00:14:21,100 --> 00:14:23,390
Chceme nastaviť, aby sa na hodnotu true.

273
00:14:23,390 --> 00:14:27,150
Tak, že znamená, že tento uzol
označuje úspešné

274
00:14:27,150 --> 00:14:29,250
Slovo, aktuálne slovo.

275
00:14:29,250 --> 00:14:30,940
>> Teraz nastavte, že na hodnotu true.

276
00:14:30,940 --> 00:14:35,150
Chceme obnoviť naše kurzor na miesto
na začiatku trie znova.

277
00:14:35,150 --> 00:14:40,160
A konečne, zvýšiť náš slovník
veľkosť, pretože sme našli inú prácu.

278
00:14:40,160 --> 00:14:43,230
Takže budeme pokračovať v tom, že,
čítanie v znak po znaku,

279
00:14:43,230 --> 00:14:49,150
výstavbu nových uzlov v našom trie a
pre každé slovo v slovníku, kým

280
00:14:49,150 --> 00:14:54,020
sme sa konečne dostať C! = EOF, v ktorom
Prípad sa vymaniť zo súboru.

281
00:14:54,020 --> 00:14:57,050
>> Teraz existujú dva prípady prejednávanej pred
ktoré sme mohli zasiahnuť EOF.

282
00:14:57,050 --> 00:15:00,980
Prvý z nich je, či došlo k chybe
čítanie zo súboru.

283
00:15:00,980 --> 00:15:03,470
Takže v prípade, že bola chyba, budeme
musíte urobiť typický.

284
00:15:03,470 --> 00:15:06,460
Vyložiť všetko, v blízkosti
súbor, vráti false.

285
00:15:06,460 --> 00:15:09,810
Za predpokladu, že nie je chyba, ktorá
len znamená, že sme vlastne hit na koniec

286
00:15:09,810 --> 00:15:13,750
súbor, v tom prípade, zatvoríme
súbor a vrátiť true, pretože sme

287
00:15:13,750 --> 00:15:17,330
úspešne načítaný slovníka
do nášho trie.

288
00:15:17,330 --> 00:15:20,170
>> Takže teraz poďme pozrieť na kontrolu.

289
00:15:20,170 --> 00:15:25,156
Ak sa pozrieme na funkciu kontroly, vidíme,
že kontrola bude vracať hodnotu typu bool.

290
00:15:25,156 --> 00:15:29,680
Vracia true, ak to slovo, ktoré je
boli prenesené, je v našom trie.

291
00:15:29,680 --> 00:15:32,110
Vracia false inak.

292
00:15:32,110 --> 00:15:36,050
Tak ako sa vám zistiť, či
toto slovo je v našom trie?

293
00:15:36,050 --> 00:15:40,190
>> Vidíme tu, že rovnako ako predtým,
budeme používať kurzor na iteráciu

294
00:15:40,190 --> 00:15:41,970
prostredníctvom našej trie.

295
00:15:41,970 --> 00:15:46,600
A teraz budeme iterovat
v celom našom slova.

296
00:15:46,600 --> 00:15:50,620
Takže iterácia nad slovom sme v minulosti,
ideme zistiť,

297
00:15:50,620 --> 00:15:56,400
index do poľa, ktoré deti
zodpovedá slovo držiak I. Tak toto

298
00:15:56,400 --> 00:15:59,670
bude vyzerať presne ako
zaťaženie, kde ak slovo [i]

299
00:15:59,670 --> 00:16:03,310
je apostrof, potom chceme
použiť index "Abeceda" - 1.

300
00:16:03,310 --> 00:16:05,350
Pretože sme zistili, že
je miesto, kde budeme ukladať

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

302
00:16:07,100 --> 00:16:11,780
>> Inak budeme používať dva nižšiu slovo
Držiak I. Takže nezabudnite, že slovo môže

303
00:16:11,780 --> 00:16:13,920
mať ľubovoľnú veľkosť písmen.

304
00:16:13,920 --> 00:16:17,540
A tak chceme, aby sa ubezpečil, že sme
používať malé písmená verzii vecí.

305
00:16:17,540 --> 00:16:21,920
A potom odpočítať od "" raz
znovu nám v abecednom

306
00:16:21,920 --> 00:16:23,880
Postavenie tohto charakteru.

307
00:16:23,880 --> 00:16:27,680
Tak, že to bude náš index
do detského poľa.

308
00:16:27,680 --> 00:16:32,420
>> A teraz, ak tento index do detí
pole je null, to znamená, že

309
00:16:32,420 --> 00:16:34,990
už nemôže pokračovať iterácie
sa našej trie.

310
00:16:34,990 --> 00:16:38,870
Ak je tomu tak, nemôže toto slovo nie je
mohlo byť v našom trie.

311
00:16:38,870 --> 00:16:42,340
Vzhľadom k tomu, ak by bolo, že by sa
znamenať, že by cesta

312
00:16:42,340 --> 00:16:43,510
sa k tomuto slovu.

313
00:16:43,510 --> 00:16:45,290
A vy by ste nikdy stretnúť null.

314
00:16:45,290 --> 00:16:47,850
Takže stretnutie null, vrátime false.

315
00:16:47,850 --> 00:16:49,840
Slovo nie je v slovníku.

316
00:16:49,840 --> 00:16:53,660
Ak by tomu tak nebolo null, potom sme
bude pokračovať iterácie.

317
00:16:53,660 --> 00:16:57,220
>> Takže ideme tam kurzor
poukázať na to najmä

318
00:16:57,220 --> 00:16:59,760
uzol v danom indexe.

319
00:16:59,760 --> 00:17:03,150
Držíme tom, že po
celé slovo, za predpokladu, že

320
00:17:03,150 --> 00:17:03,950
nikdy hit null.

321
00:17:03,950 --> 00:17:07,220
To znamená, že sme boli schopní dostať sa cez
celé slovo a nájsť

322
00:17:07,220 --> 00:17:08,920
uzol v našom pokuse.

323
00:17:08,920 --> 00:17:10,770
Ale my nie sme úplne neskončil.

324
00:17:10,770 --> 00:17:12,290
>> Nechceme sa len vrátiť true.

325
00:17:12,290 --> 00:17:14,770
Chceme sa vrátiť kurzor> slovo.

326
00:17:14,770 --> 00:17:18,980
Vzhľadom k tomu, nezabudnite znovu, je "mačka" nie je
v našom slovníku, a "katastrofa"

327
00:17:18,980 --> 00:17:22,935
je, potom budeme úspešne dostaneme
cez slovo "mačka". Ale kurzor

328
00:17:22,935 --> 00:17:25,760
Slovo bude false, a nie je pravda.

329
00:17:25,760 --> 00:17:30,930
Takže sa vrátime kurzora slovo pre označenie
či tento uzol je v skutočnosti slovo.

330
00:17:30,930 --> 00:17:32,470
A to je pre kontrolu.

331
00:17:32,470 --> 00:17:34,250
>> Takže poďme sa pozrieť na veľkosť.

332
00:17:34,250 --> 00:17:37,350
Takže veľkosť bude celkom jednoduché
pretože, pamätajte na zaťaženie, sme

333
00:17:37,350 --> 00:17:41,430
zvyšovanie veľkosť slovníka pre
každé slovo, že sa stretávame.

334
00:17:41,430 --> 00:17:45,350
Takže veľkosť je len tak
návrat slovníka veľkosť.

335
00:17:45,350 --> 00:17:47,390
A to je všetko.

336
00:17:47,390 --> 00:17:50,590
>> Takže nakoniec sme sa uvoľniť.

337
00:17:50,590 --> 00:17:55,100
Takže vyložiť, budeme používať
rekurzívne funkcie, ktorá vlastne robiť všetko

338
00:17:55,100 --> 00:17:56,530
práce pre nás.

339
00:17:56,530 --> 00:17:59,340
Takže naša funkcia bude
byť vyzvaná, vykladača.

340
00:17:59,340 --> 00:18:01,650
Čo je vykladač robiť?

341
00:18:01,650 --> 00:18:06,580
Vidíme tu, že vykladač sa chystá
iterovat cez všetky deti na

342
00:18:06,580 --> 00:18:08,410
tento konkrétny uzol.

343
00:18:08,410 --> 00:18:11,750
A v prípade, že dieťa uzol nie je
null, potom budeme

344
00:18:11,750 --> 00:18:13,730
vyložiť podriadený uzol.

345
00:18:13,730 --> 00:18:18,010
>> Tak to ste vy rekurzívne vyložiť
všetky naše deti.

346
00:18:18,010 --> 00:18:21,080
Potom, čo sme si istí, že všetky naše deti
boli vyložené, a potom sme

347
00:18:21,080 --> 00:18:25,210
môže oslobodiť, tak
vyložiť sami.

348
00:18:25,210 --> 00:18:29,460
To bude fungovať rekurzívne
vyložiť celý trie.

349
00:18:29,460 --> 00:18:32,850
A potom ešte raz, že to urobil,
môžeme len vrátiť true.

350
00:18:32,850 --> 00:18:34,210
Uvoľniť nemôže zlyhať.

351
00:18:34,210 --> 00:18:35,710
Sme len uvoľnenie veci.

352
00:18:35,710 --> 00:18:38,870
Takže akonáhle sme hotoví uvoľnenie
všetko, vráti hodnotu true.

353
00:18:38,870 --> 00:18:40,320
A to je všetko.

354
00:18:40,320 --> 00:18:41,080
Volám sa Rob.

355
00:18:41,080 --> 00:18:42,426
A to pravopisu.

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