1
00:00:00,000 --> 00:00:12,350
>> [MUSIC PŘEHRÁVÁNÍ]

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

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

4
00:00:13,640 --> 00:00:16,210
A ať je to řešení ven.

5
00:00:16,210 --> 00:00:20,070
Takže tady budeme realizovat
obecné tabulky.

6
00:00:20,070 --> 00:00:24,090
Vidíme, že struct uzel naší
tabulka bude vypadat takto.

7
00:00:24,090 --> 00:00:28,710
Takže to bude mít char slovo
Pole Velikost Délka + 1.

8
00:00:28,710 --> 00:00:32,259
Nezapomeňte + 1, protože maximální
slovo ve slovníku je 45

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

10
00:00:33,130 --> 00:00:37,070
A pak budeme potřebovat jeden navíc
znak pro zpětné lomítko nulu.

11
00:00:37,070 --> 00:00:40,870
>> A pak naše Hashtable v každém
kbelík se bude ukládat

12
00:00:40,870 --> 00:00:42,320
spojový seznam uzlů.

13
00:00:42,320 --> 00:00:44,420
Neděláme lineární snímací zde.

14
00:00:44,420 --> 00:00:48,430
A tak, aby odkazy na další
prvek v kbelíku, musíme

15
00:00:48,430 --> 00:00:50,390
struct uzel * další.

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

17
00:00:51,110 --> 00:00:53,090
Takže to je to, co uzel vypadá.

18
00:00:53,090 --> 00:00:56,180
>> Nyní je zde prohlášení
naší Hashtable.

19
00:00:56,180 --> 00:00:59,640
Bude to mít 16.834 kbelíky.

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čně budeme mít
globální proměnná velikost Hashtable, které

22
00:01:05,450 --> 00:01:07,000
se chystá začít jako nula.

23
00:01:07,000 --> 00:01:10,760
A to bude mít přehled o tom, jak
mnoho slov jsou v našem slovníku.

24
00:01:10,760 --> 00:01:13,710
>> Takže pojďme se podívat na zatížení.

25
00:01:13,710 --> 00:01:16,390
Všimněte si, že zátěž, vrací bool.

26
00:01:16,390 --> 00:01:20,530
Můžete se vrátit true, pokud bylo úspěšné
naloženo, a v opačném případě false.

27
00:01:20,530 --> 00:01:23,990
A to trvá const char * slovníku,
což je slovník

28
00:01:23,990 --> 00:01:25,280
který chceme otevřít.

29
00:01:25,280 --> 00:01:27,170
Takže to je první věc,
budeme dělat.

30
00:01:27,170 --> 00:01:29,500
>> Jedeme do fopen
slovník pro čtení.

31
00:01:29,500 --> 00:01:31,680
A budeme muset udělat
Ujistěte se, že se jí podařilo.

32
00:01:31,680 --> 00:01:35,920
Takže pokud to vrátil NULL, pak ne
úspěšně otevřít slovník.

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

34
00:01:37,440 --> 00:01:41,580
Ale za předpokladu, že to úspěšně udělal
otevřené, pak chceme přečíst

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

36
00:01:42,400 --> 00:01:46,450
Takže mějte opakování, dokud nenajdeme nějaký
důvod, aby se vymanily z této smyčky,

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

38
00:01:47,570 --> 00:01:48,920
Takže mějte opakování.

39
00:01:48,920 --> 00:01:51,780
>> A teď jdeme na
malloc jeden uzel.

40
00:01:51,780 --> 00:01:54,020
A samozřejmě musíme
vysílat znovu zkontrolujte.

41
00:01:54,020 --> 00:01:58,680
Takže pokud mallocing neuspěl, pak
chceme vyložit libovolný uzel, který my

42
00:01:58,680 --> 00:02:02,590
stalo malloc před zavřete
slovník a vrátí false.

43
00:02:02,590 --> 00:02:06,830
Ale ignorovat, že za předpokladu, že se
podařilo, pak chceme použít fscanf

44
00:02:06,830 --> 00:02:12,400
přečíst jediné slovo z naší
slovník do našeho uzlu.

45
00:02:12,400 --> 00:02:17,940
Takže pamatujte, že vstupní slovo> je char
Slovo vyrovnávací paměť o velikosti LENGHTH + 1

46
00:02:17,940 --> 00:02:20,300
že budeme ukládat slovo palců

47
00:02:20,300 --> 00:02:25,070
>> Takže fscanf bude vrátit 1, pokud
jak to bylo schopné úspěšně

48
00:02:25,070 --> 00:02:26,750
číst slovo ze souboru.

49
00:02:26,750 --> 00:02:30,460
Pokud to buď chyba se stane, nebo se
dostat se na konec souboru,

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

51
00:02:31,950 --> 00:02:35,180
V takovém případě nevrací 1,
jsme se konečně chystá vypuknout

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 jednou se nám podařilo mít
číst slovo do

54
00:02:42,770 --> 00:02:48,270
entry> slovo, pak jdeme na to
Slovo pomocí našeho hash funkce.

55
00:02:48,270 --> 00:02:49,580
>> Pojďme se podívat na
funkce hash.

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

57
00:02:52,430 --> 00:02:55,610
Takže nemáte opravdu potřebujete
to pochopit.

58
00:02:55,610 --> 00:02:59,460
A vlastně jsme právě vytáhl tento hash
funkce z internetu.

59
00:02:59,460 --> 00:03:04,010
Jediná věc, kterou je třeba si uvědomit, je
že to trvá const char * slovo.

60
00:03:04,010 --> 00:03:08,960
Tak to trvá řetězec jako vstup, a
vrácením unsigned int jako výstup.

61
00:03:08,960 --> 00:03:12,360
Tak to je vše, funkce hash je, je to
bere 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šimněte si, že jsme moding by NUM_BUCKETS,
tak, že vrácená hodnota

64
00:03:18,530 --> 00:03:21,730
ve skutečnosti je index do Hashtable
a není index za

65
00:03:21,730 --> 00:03:24,320
meze pole.

66
00:03:24,320 --> 00:03:28,060
Takže za předpokladu, že funkce, jedeme
hash slovo, které čteme

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

68
00:03:29,390 --> 00:03:31,700
A pak budeme používat
že hashovací vložit

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

70
00:03:33,750 --> 00:03:38,520
>> Nyní Hashtable hash je aktuální
spojené seznamu v tabulce.

71
00:03:38,520 --> 00:03:41,410
A to je velmi možné,
že je to jen NULL.

72
00:03:41,410 --> 00:03:44,960
Chceme vložit náš vstup na
začátku tohoto propojeného seznamu.

73
00:03:44,960 --> 00:03:48,600
A tak budeme mít naši aktuální
vstupní bod do jaké Hashtable

74
00:03:48,600 --> 00:03:50,380
V současné době poukazuje na.

75
00:03:50,380 --> 00:03:53,310
A pak budeme ukládat,
v Hashtable na

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

77
00:03:55,350 --> 00:03:59,320
Takže tyto dva řádky úspěšně vložit
Vstup na začátku

78
00:03:59,320 --> 00:04:02,260
spojový seznam v tomto indexu
v Hashtable.

79
00:04:02,260 --> 00:04:04,900
>> Jakmile jsme hotovi s tím, víme,
že jsme našli další slovo

80
00:04:04,900 --> 00:04:07,790
slovník, a my jsme opět zvyšovat.

81
00:04:07,790 --> 00:04:13,960
Tak jsme to dělat, dokud fscanf
nakonec se vrátil něco non-1 na

82
00:04:13,960 --> 00:04:16,950
který bod si uvědomit, že
musíme vstup zdarma.

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

84
00:04:19,459 --> 00:04:21,329
A my jsme se snažili něco přečíst
ze slovníku.

85
00:04:21,329 --> 00:04:23,910
A my jsme neměli úspěšně číst
něco ze slovníku, v

86
00:04:23,910 --> 00:04:26,650
takovém případě musíme uvolnit vstup
že jsme vlastně nikdy dát do

87
00:04:26,650 --> 00:04:29,140
Hashtable, a konečně zlomit.

88
00:04:29,140 --> 00:04:32,750
>> Poté, co jsme vypukne musíme vidět, dobře,
jsme se zlomit, protože tam

89
00:04:32,750 --> 00:04:34,360
byla chyba při čtení ze souboru?

90
00:04:34,360 --> 00:04:37,120
Nebo jsme se zlomit, protože jsme
došli na konec souboru?

91
00:04:37,120 --> 00:04:39,480
Pokud došlo k chybě, pak
Chceme se vrátit false.

92
00:04:39,480 --> 00:04:40,930
Vzhledem k tomu, zatížení neuspěl.

93
00:04:40,930 --> 00:04:43,890
A v tomto procesu chceme vyložit
všechna slova, která čteme v, a

94
00:04:43,890 --> 00:04:45,670
zavřete soubor slovníku.

95
00:04:45,670 --> 00:04:48,740
>> Za předpokladu, že jsme se to podaří, pak jsme jen
Stále je třeba zavřít slovník

96
00:04:48,740 --> 00:04:53,040
soubor, a nakonec se vrátit true, protože jsme
úspěšně načten slovníku.

97
00:04:53,040 --> 00:04:54,420
A to je pro zatížení.

98
00:04:54,420 --> 00:04:59,020
Takže teď zjistit, vzhledem k tomu naložené Hashtable,
bude vypadat takto.

99
00:04:59,020 --> 00:05:03,140
Tak se podívejte, vrací bool, který je
bude uvádět, zda prošel

100
00:05:03,140 --> 00:05:07,530
v char * slovo, ať už prošel
v řetězci je v našem slovníku.

101
00:05:07,530 --> 00:05:09,890
Takže, je-li ve slovníku,
v případě, že je v našem Hashtable,

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

103
00:05:11,170 --> 00:05:13,380
A pokud to tak není, vrátíme false.

104
00:05:13,380 --> 00:05:17,740
>> Vzhledem k tomu, to prošel ve slově, my jsme
bude hash slovo.

105
00:05:17,740 --> 00:05:22,110
Nyní důležité si uvědomit, je
že v zátěži věděli jsme, že všechny

106
00:05:22,110 --> 00:05:23,820
slova, že budeme mít malá písmena.

107
00:05:23,820 --> 00:05:25,820
Ale tady nejsme tak jistí.

108
00:05:25,820 --> 00:05:29,510
Pokud se podíváme na náš hash funkce,
naše hash funkce vlastně

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

110
00:05:32,700 --> 00:05:37,940
Takže bez ohledu na kapitalizace
Slovo, náš hash funkce je návrat

111
00:05:37,940 --> 00:05:42,270
stejný index na cokoliv
kapitalizace je, jak to bude mít

112
00:05:42,270 --> 00:05:45,280
se vrátil k úplně malá
verze slova.

113
00:05:45,280 --> 00:05:46,600
Dobře.

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

115
00:05:49,790 --> 00:05:52,940
>> Teď to pro smyčce bude
iteraci spojového seznamu

116
00:05:52,940 --> 00:05:55,000
která byla v daném indexu.

117
00:05:55,000 --> 00:05:59,610
Takže všimnete jsme inicializaci vstup
poukázat na daném indexu.

118
00:05:59,610 --> 00:06:02,750
Budeme pokračovat
zatímco vstup! = NULL.

119
00:06:02,750 --> 00:06:07,770
A nezapomeňte, že aktualizace ukazatel
v našem souvisí položka v seznamu = entry> další.

120
00:06:07,770 --> 00:06:14,400
Takže máme aktuální vstupní bod do
Dalším bodem v propojeném seznamu.

121
00:06:14,400 --> 00:06:19,250
>> Takže pro každou položku v propojeném seznamu,
budeme používat strcasecmp.

122
00:06:19,250 --> 00:06:20,330
Není to StrComp.

123
00:06:20,330 --> 00:06:23,780
Protože jednou, chceme
dělat věci případ necitlivě.

124
00:06:23,780 --> 00:06:27,870
Tak jsme se použít strcasecmp k porovnání
Slovo, které bylo prošel tento

125
00:06:27,870 --> 00:06:31,860
funkce proti slovu
že je v této položce.

126
00:06:31,860 --> 00:06:35,570
Pokud se vrátí nulu, to znamená, že je
Zápas, ve kterém případě chceme, aby

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

128
00:06:36,630 --> 00:06:39,590
Úspěšně jsme našli
Slovo v našem Hashtable.

129
00:06:39,590 --> 00:06:43,040
>> V případě, že nebyl zápas, pak jsme
jít na smyčku znovu a podívat se na

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

131
00:06:43,990 --> 00:06:47,640
A budeme pokračovat smyčkování zatímco
jsou položky v této aplikaci v seznamu.

132
00:06:47,640 --> 00:06:50,160
Co se stane, když se rozejdeme
z toho pro smyčce?

133
00:06:50,160 --> 00:06:55,110
To znamená, že jsme neměli najít položku, která
uzavřeno toto slovo, v tom případě

134
00:06:55,110 --> 00:07:00,220
vrátíme false což znamená, že naše
Hashtable neobsahoval 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 pojďme se podívat na velikosti.

137
00:07:04,790 --> 00:07:06,970
Nyní velikost bude velmi jednoduchý.

138
00:07:06,970 --> 00:07:11,080
Vzhledem k tomu, pamatujte na zatížení, pro každé slovo
jsme zjistili, jsme se zvyšuje globální

139
00:07:11,080 --> 00:07:12,880
variabilní velikost Hashtable.

140
00:07:12,880 --> 00:07:16,480
Takže funkce velikost je právě děje
vrátit globální proměnné.

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

142
00:07:18,150 --> 00:07:22,300
>> Nyní konečně, musíme uvolnit
slovník jednou všechno hotovo.

143
00:07:22,300 --> 00:07:25,340
Tak jak budeme dělat, že?

144
00:07:25,340 --> 00:07:30,440
Právě zde jsme smyčkování přes
všechny kbelíky našeho stolu.

145
00:07:30,440 --> 00:07:33,240
Takže tam jsou NUM_BUCKETS kbelíky.

146
00:07:33,240 --> 00:07:37,410
A pro každou aplikaci v seznamu v naší
Hashtable, jedeme do smyčky přes

147
00:07:37,410 --> 00:07:41,070
celistvost propojeného seznamu,
uvolní každý prvek.

148
00:07:41,070 --> 00:07:42,900
>> Nyní musíme být opatrní.

149
00:07:42,900 --> 00:07:47,910
Takže tady máme dočasnou proměnnou
to je ukládání ukazatel na další

150
00:07:47,910 --> 00:07:49,730
prvek v propojeném seznamu.

151
00:07:49,730 --> 00:07:52,140
A pak budeme zdarma
aktuální prvek.

152
00:07:52,140 --> 00:07:55,990
Musíme si být jisti, že jsme to udělat, protože my
nemůže jen tak uvolnit aktuálního prvku

153
00:07:55,990 --> 00:07:59,180
a pak zkuste přejděte na další ukazatel,
protože jakmile jsme osvobodil jej,

154
00:07:59,180 --> 00:08:00,870
paměť se stává neplatnou.

155
00:08:00,870 --> 00:08:04,990
>> Takže musíme držet kolem ukazatel na
Další prvek, pak se můžeme osvobodit

156
00:08:04,990 --> 00:08:08,360
aktuální prvek, a pak se můžeme aktualizovat
Naše aktuální prvek poukázat na

157
00:08:08,360 --> 00:08:09,550
další prvek.

158
00:08:09,550 --> 00:08:12,800
Budeme smyčky, zatímco tam jsou prvky,
v tomto propojeném seznamu.

159
00:08:12,800 --> 00:08:15,620
Uděláme to pro všechny spojeny
Seznamy v Hashtable.

160
00:08:15,620 --> 00:08:19,460
A jakmile jsme skončili s tím, máme
zcela vyloženo Hashtable a

161
00:08:19,460 --> 00:08:20,190
jsme hotovi.

162
00:08:20,190 --> 00:08:23,200
Tak to je nemožné pro odlehčení
někdy vrátí false.

163
00:08:23,200 --> 00:08:26,470
A když jsme hotovi, můžeme
jen vrátit true.

164
00:08:26,470 --> 00:08:29,000
>> Dejme toto řešení vyzkoušet.

165
00:08:29,000 --> 00:08:33,070
Takže pojďme se podívat na to, co naše
struct uzel bude vypadat.

166
00:08:33,070 --> 00:08:36,220
Zde vidíme, že budeme mít bool
slovo a struct uzel * děti

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

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

169
00:08:38,929 --> 00:08:42,020
Takže první věc, kterou by mohlo být
přemýšlel, proč je abecedu

170
00:08:42,020 --> 00:08:44,660
ed definována jako 27?

171
00:08:44,660 --> 00:08:47,900
No, pamatujte, že budeme potřebovat
se zpracování apostrof.

172
00:08:47,900 --> 00:08:51,910
Tak, že to bude poněkud
Zvláštní případ v celém programu.

173
00:08:51,910 --> 00:08:54,710
>> Nyní si vzpomenout, jak trie
skutečně funguje.

174
00:08:54,710 --> 00:08:59,380
Řekněme, že jsme indexování slovo
"kočky". Pak z kořene trie,

175
00:08:59,380 --> 00:09:02,610
jdeme se podívat na děti
pole, a budeme se dívat na

176
00:09:02,610 --> 00:09:08,090
index, který odpovídá na dopis
C. Tak, že budou indexovány 2.

177
00:09:08,090 --> 00:09:11,530
Takže vzhledem k tomu, že bude
nám nový uzel.

178
00:09:11,530 --> 00:09:13,820
A pak budeme pracovat od tohoto uzlu.

179
00:09:13,820 --> 00:09:17,770
>> Takže za předpokladu, že uzel, jsme opět
se podíváme na dětském pole.

180
00:09:17,770 --> 00:09:22,110
A budeme se dívat na indexu nula
tak, aby odpovídal A v kočky.

181
00:09:22,110 --> 00:09:27,170
Takže jsme jít do tohoto uzlu,
a vzhledem k tomu, že uzel jedeme

182
00:09:27,170 --> 00:09:31,090
dívat se na konci to je a odpovídá
na T. a pohybuje se na tomto uzlu,

183
00:09:31,090 --> 00:09:35,530
Nakonec jsme zcela podíval
přes naše slovo "kočka". A teď bool

184
00:09:35,530 --> 00:09:40,960
Slovo má ukázat, zda
to dané slovo je vlastně slovo.

185
00:09:40,960 --> 00:09:43,470
>> Tak proč potřebujeme ten zvláštní případ?

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

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

188
00:09:50,150 --> 00:09:54,580
Tak a chtějí zjistit, zda slovo "kočka"
je v našem slovníku, jsme

189
00:09:54,580 --> 00:09:59,970
bude úspěšně prohlédnout
Indexy C-A-T v oblasti uzlu.

190
00:09:59,970 --> 00:10:04,290
Ale to je jen proto, že katastrofa
se stalo vytvoření uzlů na cestě

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

192
00:10:07,190 --> 00:10:12,020
Takže bool slovo se používá k označení, zda
Tento konkrétní místo

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

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

195
00:10:15,140 --> 00:10:19,310
Takže teď, když víme, co to trie je
bude vypadat, pojďme se podívat na

196
00:10:19,310 --> 00:10:20,730
načíst funkci.

197
00:10:20,730 --> 00:10:24,610
Takže zatížení se chystá vrátit bool
na tom, zda se nám podařilo nebo

198
00:10:24,610 --> 00:10:26,720
neúspěšně načíst slovník.

199
00:10:26,720 --> 00:10:30,460
A to se bude slovník
které chceme načíst.

200
00:10:30,460 --> 00:10:33,930
>> Takže první věc, kterou máme udělat, je otevřít
do tohoto slovníku pro čtení.

201
00:10:33,930 --> 00:10:36,160
A musíme se ujistit,
jsme nepropadli.

202
00:10:36,160 --> 00:10:39,580
Takže v případě, že nebyla slovník
úspěšně otevřen, vrátí

203
00:10:39,580 --> 00:10:42,400
null, v tomto případě jsme
chystá se vrátit false.

204
00:10:42,400 --> 00:10:47,230
Avšak za předpokladu, že se úspěšně
otevřel, pak můžeme skutečně číst

205
00:10:47,230 --> 00:10:48,220
pomocí slovníku.

206
00:10:48,220 --> 00:10:50,880
>> Takže první věc, kterou budeme
chcete udělat, je, že jsme si to

207
00:10:50,880 --> 00:10:52,500
globální proměnná kořen.

208
00:10:52,500 --> 00:10:56,190
Nyní kořen bude uzel *.

209
00:10:56,190 --> 00:10:59,760
Je to vrchol naší trie, že jsme
bude iterace.

210
00:10:59,760 --> 00:11:02,660
Takže první věc, kterou budeme
chtít udělat, je rozdělit

211
00:11:02,660 --> 00:11:04,140
paměť pro náš kořen.

212
00:11:04,140 --> 00:11:07,980
Všimněte si, že jsme pomocí calloc
funkce, která je v podstatě stejná

213
00:11:07,980 --> 00:11:11,500
jako funkce malloc, kromě toho, že je
zaručeno, že vrátí něco, co je

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

215
00:11:13,180 --> 00:11:17,290
Takže pokud jsme použili malloc, potřebovali bychom, aby
projít všechny ukazatele v naší

216
00:11:17,290 --> 00:11:20,160
uzel, a ujistěte se, že
všichni jsou null.

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

218
00:11:22,710 --> 00:11:26,330
>> Nyní, stejně jako malloc, potřebujeme, aby se
Ujistěte se, že rozdělení bylo ve skutečnosti

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

220
00:11:27,520 --> 00:11:29,990
Pokud to vrátil null, pak
je třeba uzavřít nebo slovník

221
00:11:29,990 --> 00:11:32,100
souboru a vrátí false.

222
00:11:32,100 --> 00:11:36,835
Takže za předpokladu, že rozdělení bylo
úspěšná, budeme používat uzel *

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

224
00:11:40,270 --> 00:11:43,890
Takže naše kořeny nikdy nezmění,
ale budeme používat kurzor

225
00:11:43,890 --> 00:11:47,875
skutečně jít z uzlu do uzlu.

226
00:11:47,875 --> 00:11:50,940
>> Takže v tomto cyklu for jsme čtení
prostřednictvím souboru slovníku.

227
00:11:50,940 --> 00:11:53,670
A my jsme pomocí fgetc.

228
00:11:53,670 --> 00:11:56,290
Fgetc se chystá chytit jeden
znak ze souboru.

229
00:11:56,290 --> 00:11:59,370
Budeme pokračovat v popadat
znaky, zatímco my nedosahují

230
00:11:59,370 --> 00:12:01,570
konec souboru.

231
00:12:01,570 --> 00:12:03,480
>> Existují dva případy, které musíme zvládnout.

232
00:12:03,480 --> 00:12:06,610
První z nich, v případě, že znak
nebyl nový řádek.

233
00:12:06,610 --> 00:12:10,450
Takže víme, že kdyby to byla nová linka, pak
chystáme se přejít na nové slovo.

234
00:12:10,450 --> 00:12:15,240
Ale za předpokladu, že nebyl nový řádek, pak
zde chceme zjistit,

235
00:12:15,240 --> 00:12:18,380
index jedeme do indexu do
v dětském pole, které

236
00:12:18,380 --> 00:12:19,810
jsme se podívali na před.

237
00:12:19,810 --> 00:12:23,880
>> Takže, jak už jsem řekl, musíme
Zvláštním případem apostrof.

238
00:12:23,880 --> 00:12:26,220
Všimněte si, jsme pomocí ternární
Zde operátor.

239
00:12:26,220 --> 00:12:29,580
Takže budeme číst to jako, pokud
charakter čteme v byl

240
00:12:29,580 --> 00:12:35,330
apostrof, pak jedeme do nastavení
index = "abecedu" -1, která bude

241
00:12:35,330 --> 00:12:37,680
být index 26.

242
00:12:37,680 --> 00:12:41,130
>> Jinak, pokud to není apostrof, že
budeme nastavit index

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

244
00:12:43,760 --> 00:12:49,030
Takže pamatujte zpět z již p-sad,
c - bude nám

245
00:12:49,030 --> 00:12:53,410
abecední pozice C. Takže pokud
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
Pro písmeno B, dá
nám index 1, a tak dále.

248
00:12:58,120 --> 00:13:03,010
>> Tak to nám dává index do
děti pole, které chceme.

249
00:13:03,010 --> 00:13:08,890
Nyní, pokud tento index je v současné době v null
děti, to znamená, že uzel

250
00:13:08,890 --> 00:13:11,830
v současné době neexistuje
z této cesty.

251
00:13:11,830 --> 00:13:15,160
Takže musíme přidělit
uzel pro tuto cestu.

252
00:13:15,160 --> 00:13:16,550
To je to, co budeme dělat.

253
00:13:16,550 --> 00:13:20,690
>> Takže budeme znovu použít calloc
funkce, takže jsme se nemuseli

254
00:13:20,690 --> 00:13:22,880
nula se všechny ukazatele.

255
00:13:22,880 --> 00:13:27,240
A opět je třeba zkontrolovat
že calloc nezklamal.

256
00:13:27,240 --> 00:13:30,700
Pokud calloc to nepodaří, pak musíme
vyložit všechno, zavřeme

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

258
00:13:32,820 --> 00:13:40,050
Takže za předpokladu, že to nebylo selhání, pak
to bude vytvořit novou dítě na nás.

259
00:13:40,050 --> 00:13:41,930
A pak půjdeme k tomuto dítěti.

260
00:13:41,930 --> 00:13:44,960
Naše kurzor bude přecházet
se k tomuto dítěti.

261
00:13:44,960 --> 00:13:49,330
>> Nyní, pokud to není null začít s,
pak se kurzor může pouze iterovat

262
00:13:49,330 --> 00:13:52,590
se k tomuto dítěti, aniž by ve skutečnosti
museli přidělit nic.

263
00:13:52,590 --> 00:13:56,730
To je případ, kdy jsme se poprvé stalo
přidělit slovo "kočka". A

264
00:13:56,730 --> 00:14:00,330
to znamená, že když jdeme na přidělení
"Katastrofa", nepotřebujeme vytvářet

265
00:14:00,330 --> 00:14:01,680
uzly pro C-A-T znovu.

266
00:14:01,680 --> 00:14:04,830
Již existují.

267
00:14:04,830 --> 00:14:06,080
>> Co je to jinde?

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

269
00:14:10,480 --> 00:14:13,710
To znamená, že se nám podařilo mít
dokončil slovo.

270
00:14:13,710 --> 00:14:16,860
A teď, co chceme dělat, když jsme
úspěšně dokončil slovo?

271
00:14:16,860 --> 00:14:21,100
Budeme používat toto slovo pole
v naší struct uzel.

272
00:14:21,100 --> 00:14:23,390
Chceme nastavit, aby se na hodnotu true.

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

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

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

276
00:14:30,940 --> 00:14:35,150
Chceme obnovit naše kurzor na místo
na začátku trie znovu.

277
00:14:35,150 --> 00:14:40,160
A konečně, zvýšit náš slovník
velikost, protože jsme našli jinou práci.

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

279
00:14:43,230 --> 00:14:49,150
výstavbu nových uzlů v našem trie a
pro každé slovo ve slovníku, dokud

280
00:14:49,150 --> 00:14:54,020
jsme se konečně dostat C! = EOF, ve kterém
Případ se vymanit ze souboru.

281
00:14:54,020 --> 00:14:57,050
>> Nyní existují dva případy projednávané před
které jsme mohli zasáhnout EOF.

282
00:14:57,050 --> 00:15:00,980
První z nich je, zda došlo k chybě
čtení ze souboru.

283
00:15:00,980 --> 00:15:03,470
Takže v případě, že byla chyba, budeme
musíte udělat typický.

284
00:15:03,470 --> 00:15:06,460
Vyložit všechno, v blízkosti
soubor, vrátí false.

285
00:15:06,460 --> 00:15:09,810
Za předpokladu, že není chyba, která
jen znamená, že jsme vlastně hit na konec

286
00:15:09,810 --> 00:15:13,750
soubor, v tom případě, zavřeme
soubor a vrátit true, protože jsme

287
00:15:13,750 --> 00:15:17,330
úspěšně načten slovníku
do našeho trie.

288
00:15:17,330 --> 00:15:20,170
>> Takže teď pojďme podívat na kontrolu.

289
00:15:20,170 --> 00:15:25,156
Podíváme-li se na funkci kontroly, vidíme,
že kontrola bude vracet hodnotu typu bool.

290
00:15:25,156 --> 00:15:29,680
Vrací true, pokud to slovo, které je
byly přeneseny, je v našem trie.

291
00:15:29,680 --> 00:15:32,110
Vrací false jinak.

292
00:15:32,110 --> 00:15:36,050
Tak jak se vám zjistit, zda
toto slovo je v našem trie?

293
00:15:36,050 --> 00:15:40,190
>> Vidíme zde, že stejně jako předtím,
budeme používat kurzor na iteraci

294
00:15:40,190 --> 00:15:41,970
prostřednictvím naší trie.

295
00:15:41,970 --> 00:15:46,600
A teď budeme iterovat
v celém našem slova.

296
00:15:46,600 --> 00:15:50,620
Takže iterace nad slovem jsme v minulosti,
jdeme zjistit,

297
00:15:50,620 --> 00:15:56,400
index do pole, které děti
odpovídá slovo držák I. Tak tohle

298
00:15:56,400 --> 00:15:59,670
bude vypadat přesně jako
zatížení, kde pokud slovo [i]

299
00:15:59,670 --> 00:16:03,310
je apostrof, pak chceme
použít index "Abeceda" - 1.

300
00:16:03,310 --> 00:16:05,350
Protože jsme zjistili, že
je místo, kde budeme ukládat

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

302
00:16:07,100 --> 00:16:11,780
>> Jinak budeme používat dva nižší slovo
Držák I. Takže nezapomeňte, že slovo může

303
00:16:11,780 --> 00:16:13,920
mít libovolnou velikost písmen.

304
00:16:13,920 --> 00:16:17,540
A tak chceme, aby se ujistil, že jsme
používat malá písmena verzi věcí.

305
00:16:17,540 --> 00:16:21,920
A pak odečíst od "" jednou
znovu nám v abecedním

306
00:16:21,920 --> 00:16:23,880
Postavení tohoto charakteru.

307
00:16:23,880 --> 00:16:27,680
Tak, že to bude náš index
do dětského pole.

308
00:16:27,680 --> 00:16:32,420
>> A teď, pokud tento index do dětí
pole je null, to znamená, že

309
00:16:32,420 --> 00:16:34,990
již nemůže pokračovat iterace
se naší trie.

310
00:16:34,990 --> 00:16:38,870
Pokud je tomu tak, nemůže toto slovo není
mohlo být v našem trie.

311
00:16:38,870 --> 00:16:42,340
Vzhledem k tomu, pokud by bylo, že by se
znamenat, že by cesta

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

313
00:16:43,510 --> 00:16:45,290
A vy byste nikdy setkat null.

314
00:16:45,290 --> 00:16:47,850
Takže setkání null, vrátíme false.

315
00:16:47,850 --> 00:16:49,840
Slovo není ve slovníku.

316
00:16:49,840 --> 00:16:53,660
Pokud by tomu tak nebylo null, pak jsme
bude pokračovat iterace.

317
00:16:53,660 --> 00:16:57,220
>> Takže jdeme tam kurzor
poukázat na to zejména

318
00:16:57,220 --> 00:16:59,760
uzel v daném indexu.

319
00:16:59,760 --> 00:17:03,150
Držíme tom, že po
celé slovo, za předpokladu, ž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 jsme byli schopni dostat se přes
celé slovo a najít

322
00:17:07,220 --> 00:17:08,920
uzel v našem pokusu.

323
00:17:08,920 --> 00:17:10,770
Ale my nejsme úplně neskončil.

324
00:17:10,770 --> 00:17:12,290
>> Nechceme se jen vrátit true.

325
00:17:12,290 --> 00:17:14,770
Chceme se vrátit kurzor> slovo.

326
00:17:14,770 --> 00:17:18,980
Vzhledem k tomu, nezapomeňte znovu, je "kočka" není
v našem slovníku, a "katastrofa"

327
00:17:18,980 --> 00:17:22,935
je, pak budeme úspěšně dostaneme
přes slovo "kočka". Ale kurzor

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

329
00:17:25,760 --> 00:17:30,930
Takže se vrátíme kurzoru slovo pro označení
zda tento uzel je ve skutečnosti slovo.

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

331
00:17:32,470 --> 00:17:34,250
>> Takže pojďme se podívat na velikost.

332
00:17:34,250 --> 00:17:37,350
Takže velikost bude docela snadné
protože, pamatujte na zatížení, jsme

333
00:17:37,350 --> 00:17:41,430
zvyšování velikost slovníku pro
každé slovo, že se setkáváme.

334
00:17:41,430 --> 00:17:45,350
Takže velikost je jen tak
návrat slovníku velikost.

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

336
00:17:47,390 --> 00:17:50,590
>> Takže nakonec jsme se uvolnit.

337
00:17:50,590 --> 00:17:55,100
Takže vyložit, budeme používat
rekurzivní funkce, která vlastně dělat vše

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

339
00:17:56,530 --> 00:17:59,340
Takže naše funkce bude
být vyzvána, vykladače.

340
00:17:59,340 --> 00:18:01,650
Co je vykladač dělat?

341
00:18:01,650 --> 00:18:06,580
Vidíme zde, že vykladač se chystá
iterovat přes všechny děti na

342
00:18:06,580 --> 00:18:08,410
tento konkrétní uzel.

343
00:18:08,410 --> 00:18:11,750
A v případě, že dítě uzel není
null, pak budeme

344
00:18:11,750 --> 00:18:13,730
vyložit podřízený uzel.

345
00:18:13,730 --> 00:18:18,010
>> Tak to jste vy rekurzivně vyložit
všechny naše děti.

346
00:18:18,010 --> 00:18:21,080
Poté, co jsme si jisti, že všechny naše děti
byly vyloženy, a pak jsme

347
00:18:21,080 --> 00:18:25,210
může osvobodit, tak
vyložit sami.

348
00:18:25,210 --> 00:18:29,460
To bude fungovat rekurzivně
vyložit celý trie.

349
00:18:29,460 --> 00:18:32,850
A pak ještě jednou, že to udělal,
můžeme jen vrátit true.

350
00:18:32,850 --> 00:18:34,210
Uvolnit nemůže selhat.

351
00:18:34,210 --> 00:18:35,710
Jsme jen uvolnění věci.

352
00:18:35,710 --> 00:18:38,870
Takže jakmile jsme hotovi uvolnění
vše, vrátí hodnotu true.

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

354
00:18:40,320 --> 00:18:41,080
Jmenuji se Rob.

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

356
00:18:42,426 --> 00:18:47,830
>> [MUSIC PŘEHRÁVÁNÍ]