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

2
00:00:00,530 --> 00:00:03,070
>> SPEAKER 1: Dajme
toto riešenie vyskúšať.

3
00:00:03,070 --> 00:00:07,130
Takže poďme sa pozrieť na to, čo naše
Struct uzol bude vyzerať.

4
00:00:07,130 --> 00:00:11,040
Tu vidíme, že budeme mať
Bool Word a struct uzol hviezda

5
00:00:11,040 --> 00:00:12,990
Deti bracketing abecedu.

6
00:00:12,990 --> 00:00:18,720
Takže prvá vec, ktorú by ste mohli byť zvedaví,
Preto je abeceda hash definovaná ako 27?

7
00:00:18,720 --> 00:00:22,540
No, pamätajte, že budeme potrebovať
sa manipulácia apostrof, tak

8
00:00:22,540 --> 00:00:25,610
že to bude trochu zvláštne
puzdro na celom tomto programe.

9
00:00:25,610 --> 00:00:28,780
>> OK, teraz si spomenúť, ako
Trie skutočne funguje.

10
00:00:28,780 --> 00:00:33,420
Povedzme, že sme indexovanie slovo mačky,
potom z koreňa našej Trie,

11
00:00:33,420 --> 00:00:36,670
ideme sa pozrieť na deti
pole, a budeme sa pozerať na

12
00:00:36,670 --> 00:00:42,250
index, ktorý odpovedá na list
C. Tak že by index dva.

13
00:00:42,250 --> 00:00:46,400
Takže vzhľadom k tomu, že sa nám
nový uzol, a potom budeme

14
00:00:46,400 --> 00:00:47,880
práce z tohto uzla.

15
00:00:47,880 --> 00:00:51,830
>> Takže za predpokladu, že uzol, sme opäť
sa pozrieme na poli deti,

16
00:00:51,830 --> 00:00:56,170
a ideme sa pozrieť na indexe nula
tak, aby zodpovedal A v mačky.

17
00:00:56,170 --> 00:01:01,240
Takže sme ísť do tohto uzla,
a vzhľadom k tomu, že uzol, ideme

18
00:01:01,240 --> 00:01:05,170
sa pozrieť na index, ktorý zodpovedá
na T. a pohybuje sa na tomto uzle,

19
00:01:05,170 --> 00:01:09,590
Nakoniec sme úplne pozrel
prostredníctvom našej slovo mačka, a teraz Bool

20
00:01:09,590 --> 00:01:15,020
Slovo má ukázať, či
to dané slovo je vlastne slovo.

21
00:01:15,020 --> 00:01:17,530
>> Tak prečo potrebujeme ten zvláštny prípad?

22
00:01:17,530 --> 00:01:21,680
No, čo keď slovo katastrofa
je v našom slovníku, ale

23
00:01:21,680 --> 00:01:24,120
slovo mačka nie je?

24
00:01:24,120 --> 00:01:29,030
Takže v pohľade, či je slovo mačka
v našom slovníku, budeme

25
00:01:29,030 --> 00:01:34,880
úspešne prezrieť indexov
C-A-T a dosiahnuť uzol, ale to je

26
00:01:34,880 --> 00:01:39,760
len preto, že katastrofa sa stalo
vytvárať uzly na ceste z C-A-T všetky

27
00:01:39,760 --> 00:01:41,250
spôsob, ako sa na konci slova.

28
00:01:41,250 --> 00:01:46,520
Takže Bool Word sa používa uveďte, či
Tento konkrétny miesto skutočne

29
00:01:46,520 --> 00:01:48,370
označuje slovo.

30
00:01:48,370 --> 00:01:52,920
>> Dobre, tak teraz, keď vieme, čo
Trie bude vyzerať, poďme sa pozrieť

31
00:01:52,920 --> 00:01:54,800
na funkciu Load.

32
00:01:54,800 --> 00:01:58,670
Takže zaťaženie sa chystá vrátiť Bool
na tom, či sa nám podarilo alebo

33
00:01:58,670 --> 00:02:03,020
neúspešne načítať slovník a
to bude slovník

34
00:02:03,020 --> 00:02:04,520
ktoré chceme načítať.

35
00:02:04,520 --> 00:02:08,310
Takže prvá vec, ktorú sa chystáte urobiť, je otvoriť
do tohto slovníka pre čítanie.

36
00:02:08,310 --> 00:02:12,060
Musíme sa uistiť, že nesklamal,
takže ak slovník nebol

37
00:02:12,060 --> 00:02:15,280
úspešne otvorený, vráti
No, v tom prípade budeme

38
00:02:15,280 --> 00:02:16,340
vráti False.

39
00:02:16,340 --> 00:02:21,290
Avšak za predpokladu, že sa úspešne
otvoril, potom môžeme skutočne čítať

40
00:02:21,290 --> 00:02:22,310
pomocou slovníka.

41
00:02:22,310 --> 00:02:24,940
>> Takže prvá vec, ktorú budeme
chcete urobiť, je, že sme si to

42
00:02:24,940 --> 00:02:26,560
globálna premenná koreň.

43
00:02:26,560 --> 00:02:30,250
Teraz, koreň sa bude uzol hviezda.

44
00:02:30,250 --> 00:02:33,830
Je to vrchol našej Trie, že sme
bude iterácie.

45
00:02:33,830 --> 00:02:38,200
Takže prvá vec, ktorú budeme chcieť
urobiť, je alokovať pamäť pre náš koreň.

46
00:02:38,200 --> 00:02:42,040
>> Všimnite si, že sme pomocou calloc
funkcia, ktorá je v podstate rovnaká

47
00:02:42,040 --> 00:02:45,560
ako funkcia malloc, okrem toho, že je
zaručené, že vráti niečo, čo je

48
00:02:45,560 --> 00:02:47,240
úplne vynuluje.

49
00:02:47,240 --> 00:02:51,350
Takže ak sme použili malloc, potrebovali by sme, aby
prejsť všetky ukazovatele v našej

50
00:02:51,350 --> 00:02:54,220
uzol a uistite sa, že
všetci sú null.

51
00:02:54,220 --> 00:02:56,780
Takže calloc to urobí za nás.

52
00:02:56,780 --> 00:03:00,390
>> Teraz, rovnako ako malloc, je potrebné, aby
Uistite sa, že rozdelenie je v skutočnosti

53
00:03:00,390 --> 00:03:01,580
úspešný.

54
00:03:01,580 --> 00:03:04,060
Ak to vrátil null, potom
je potrebné uzavrieť našu slovník

55
00:03:04,060 --> 00:03:06,170
súboru a vráti False.

56
00:03:06,170 --> 00:03:11,040
Takže za predpokladu, že rozdelenie bolo
úspešná, budeme používať uzol

57
00:03:11,040 --> 00:03:14,340
hviezda kurzor na iteráciu
prostredníctvom našej Trie.

58
00:03:14,340 --> 00:03:17,950
Takže naše koreň sa nikdy nezmení,
ale budeme používať kurzor na

59
00:03:17,950 --> 00:03:20,770
skutočne ísť z uzla do uzla.

60
00:03:20,770 --> 00:03:25,000
>> Dobre, takže v tomto pre sláčiky, sme
prečítaní súboru slovníka,

61
00:03:25,000 --> 00:03:26,965
a budeme používať na fgetc.

62
00:03:26,965 --> 00:03:30,360
Takže fgetc sa chystá chytiť jeden
znak zo súboru.

63
00:03:30,360 --> 00:03:33,430
Budeme pokračovať v popada
znaky, zatiaľ čo my nedosahujú

64
00:03:33,430 --> 00:03:37,540
koniec súboru, takže sú
dve prípadov musíme zvládnuť.

65
00:03:37,540 --> 00:03:41,640
Prvý z nich, v prípade, že znak nebol
nová linka, takže vieme, že keby to bol nový

66
00:03:41,640 --> 00:03:44,480
linka, potom sa chystáme
prejsť na nové slovo.

67
00:03:44,480 --> 00:03:49,300
Ale za predpokladu, že nebol nový riadok, potom
tu, chceme zistiť,

68
00:03:49,300 --> 00:03:52,440
index ideme do indexu do
v poli Deti, ktoré

69
00:03:52,440 --> 00:03:53,890
sme sa pozreli na pred.

70
00:03:53,890 --> 00:03:57,950
>> Takže ako som povedal predtým, je potrebné, aby
Zvláštnym prípadom apostrof.

71
00:03:57,950 --> 00:04:01,040
Všimnite si, sme pomocou ternárnu operátor
tu, tak budeme čítať

72
00:04:01,040 --> 00:04:05,500
to, ako keby postava čítame v to
apostrof, potom budeme

73
00:04:05,500 --> 00:04:11,740
nastaviť index sa rovná abecedy mínus
1, ktorý bude index 26..

74
00:04:11,740 --> 00:04:15,190
Inak, ak to nie je apostrof,
potom budeme nastaviť index

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

76
00:04:17,820 --> 00:04:23,090
Takže pamätajte späť z predchádzajúcich p sád,
c mínus sa chystá dať nám

77
00:04:23,090 --> 00:04:27,470
abecedný pozície c, takže ak
c je písmeno, to bude

78
00:04:27,470 --> 00:04:28,770
nám index nula.

79
00:04:28,770 --> 00:04:32,180
Pre bod B, bolo by to dať
nám index 1, a tak ďalej.

80
00:04:32,180 --> 00:04:37,070
>> Tak to nám dáva index do
Deti pole, ktoré chceme.

81
00:04:37,070 --> 00:04:42,540
Teraz, v prípade, že index je v súčasnej dobe v null
Deti poľa, to znamená, že

82
00:04:42,540 --> 00:04:47,470
uzol nemá v súčasnej dobe neexistuje z
, Že cesta, takže musíme prideliť

83
00:04:47,470 --> 00:04:49,220
uzol pre túto cestu.

84
00:04:49,220 --> 00:04:50,610
To je to, čo robíme tu.

85
00:04:50,610 --> 00:04:54,650
Takže budeme opäť používať calloc
funkcie, takže nemáme

86
00:04:54,650 --> 00:05:00,130
k vynulovanie všetkých ukazovateľov, a my,
znovu, je potrebné skontrolovať, že calloc

87
00:05:00,130 --> 00:05:01,300
nesklamal.

88
00:05:01,300 --> 00:05:04,760
Ak calloc to nepodarí, potom musíme
vyložiť všetko, zatvoríme

89
00:05:04,760 --> 00:05:06,880
slovník, a vráti False.

90
00:05:06,880 --> 00:05:14,110
>> Takže za predpokladu, že to nebolo zlyhanie, potom
to bude vytvoriť novú dieťa pre nás,

91
00:05:14,110 --> 00:05:16,000
a potom pôjdeme na to dieťa.

92
00:05:16,000 --> 00:05:19,030
Naše kurzor bude prechádzať
sa k tomuto dieťaťu.

93
00:05:19,030 --> 00:05:23,390
Teraz, ak to nie je null začať s,
potom sa kurzor môže iba iterovat

94
00:05:23,390 --> 00:05:26,650
sa k tomuto dieťaťu, bez toho by v skutočnosti
museli prideliť nič.

95
00:05:26,650 --> 00:05:30,790
To je prípad, kedy sme sa prvýkrát stalo
prideliť slovo mačka, a

96
00:05:30,790 --> 00:05:34,390
to znamená, že keď ideme na pridelenie
katastrofa, nepotrebujeme vytvárať

97
00:05:34,390 --> 00:05:35,720
uzly pre C-A-T znova.

98
00:05:35,720 --> 00:05:37,620
Už existujú.

99
00:05:37,620 --> 00:05:40,140
>> OK, takže to, čo je to iný?

100
00:05:40,140 --> 00:05:44,600
To je stav, kedy c je
spätné lomítko n, kde c je nová linka.

101
00:05:44,600 --> 00:05:47,780
To znamená, že sa nám podarilo mať
dokončil slovo.

102
00:05:47,780 --> 00:05:51,020
A teraz, čo chceme robiť, keď sme
úspešne dokončil slovo?

103
00:05:51,020 --> 00:05:55,250
Budeme používať toto slovo pole
v našej struct uzol.

104
00:05:55,250 --> 00:06:00,570
>> Chceme nastaviť, aby sa na True, aby
znamená, že tento uzol označuje

105
00:06:00,570 --> 00:06:03,320
úspešný slovo skutočné slovo.

106
00:06:03,320 --> 00:06:05,050
Teraz nastavte, že na hodnotu TRUE.

107
00:06:05,050 --> 00:06:09,210
Chceme obnoviť naše kurzor na miesto
na začiatku Trie znova.

108
00:06:09,210 --> 00:06:13,510
A konečne, zvýšiť náš slovník
veľkosť, pretože sme našli ďalšie slovo.

109
00:06:13,510 --> 00:06:16,450
>> Dobre, takže budeme pokračovať v tom
, Že čítanie v znaku

110
00:06:16,450 --> 00:06:21,960
charakter, výstavbu nových uzlov v
naše Trie a pre každé slovo v

111
00:06:21,960 --> 00:06:26,810
slovník, až sme konečne dosiahnuť c
rovná EOF, v tomto prípade sme sa zlomiť

112
00:06:26,810 --> 00:06:28,100
zo súboru.

113
00:06:28,100 --> 00:06:31,110
Teraz máme k dispozícii dva prípady podľa
ktoré sme mohli zasiahnuť EOF.

114
00:06:31,110 --> 00:06:35,680
Prvý z nich je, či došlo k chybe
čítanie zo súboru, takže v prípade, že bol

115
00:06:35,680 --> 00:06:39,280
chyba, ktorú musíme urobiť, typické
vyložiť všetko, zatvorte súbor,

116
00:06:39,280 --> 00:06:40,520
vráti False.

117
00:06:40,520 --> 00:06:43,870
Za predpokladu, že nie je chyba, ktorá
len znamená, že sme vlastne hit na koniec

118
00:06:43,870 --> 00:06:47,820
súbor, v tom prípade, zatvoríme
súbor a vrátiť True, pretože sme

119
00:06:47,820 --> 00:06:51,010
úspešne načítaný slovníka
do nášho Trie.

120
00:06:51,010 --> 00:06:54,240
>> Dobre, tak teraz poďme
pozrite sa na kontrolu.

121
00:06:54,240 --> 00:06:58,780
Pri pohľade na Skontrolujte funkciu, vidíme,
ktorá Kontrola sa chystá vrátiť Bool.

122
00:06:58,780 --> 00:07:03,740
Vracia TRUE, ak to slovo, ktoré je
boli prenesené, je v našom Trie.

123
00:07:03,740 --> 00:07:06,170
Vracia False inak.

124
00:07:06,170 --> 00:07:10,110
>> Tak ako sa budeme na určenie, či
toto slovo je v našom Trie?

125
00:07:10,110 --> 00:07:14,270
Vidíme tu, že rovnako ako predtým,
budeme používať kurzor na iteráciu

126
00:07:14,270 --> 00:07:16,010
prostredníctvom našej Trie.

127
00:07:16,010 --> 00:07:20,650
Teraz, tu, ideme na iteráciu
v celom našom slova.

128
00:07:20,650 --> 00:07:24,680
Takže iterácia cez slovo sme
prešiel, ideme zistiť,

129
00:07:24,680 --> 00:07:29,280
index do poľa detí, ktoré
zodpovedá slovo konzola i

130
00:07:29,280 --> 00:07:34,150
Takže to bude vyzerať presne ako
Zaťaženie, kde ak slovo držiak aj je

131
00:07:34,150 --> 00:07:38,110
apostrof, potom chceme použiť index
abeceda mínus 1, pretože sme zistili,

132
00:07:38,110 --> 00:07:41,160
že je miesto, kde budeme
uložiť apostrofy.

133
00:07:41,160 --> 00:07:44,440
>> Inak budeme používať tolower
Slovo držiak i

134
00:07:44,440 --> 00:07:48,270
Takže nezabudnite, že slovo môže mať ľubovoľný
kapitalizácie, a tak sme

135
00:07:48,270 --> 00:07:51,590
chcete, aby sa ubezpečil, že sme pomocou
malá verzia vecí.

136
00:07:51,590 --> 00:07:55,300
A potom odpočítať od tej malými písmenami
na, opäť nám

137
00:07:55,300 --> 00:07:57,940
abecedný pozície
tohto charakteru.

138
00:07:57,940 --> 00:08:01,740
Tak, že to bude náš index
do poľa deti.

139
00:08:01,740 --> 00:08:06,480
>> A teraz, či je to index do detí
pole je null, to znamená, že

140
00:08:06,480 --> 00:08:09,050
už nemôže pokračovať iterácie
sa našej Trie.

141
00:08:09,050 --> 00:08:13,320
Ak je tomu tak, nemôže toto slovo nie je
mohlo byť v našom Trie, pretože v prípade, že

142
00:08:13,320 --> 00:08:18,000
sa, že by to znamenalo, že by sa
Cesta dole do tohto slova, a vy by

143
00:08:18,000 --> 00:08:19,350
nikdy stretnúť null.

144
00:08:19,350 --> 00:08:21,910
Takže stretnutie null, vrátime False.

145
00:08:21,910 --> 00:08:23,810
Slovo nie je v slovníku.

146
00:08:23,810 --> 00:08:28,200
Ak by tomu tak nebolo null, potom budeme
pokračovať iterácie, takže ideme

147
00:08:28,200 --> 00:08:33,150
aktualizovať naše kurzor poukázať na to
najmä uzol v danom indexe.

148
00:08:33,150 --> 00:08:36,659
>> Tak sme sa pokračovať v tom, že po celú dobu
celé slovo.

149
00:08:36,659 --> 00:08:40,630
Za predpokladu, že sme sa nikdy hit null, že prostriedky
sme boli schopní sa dostať cez celé

150
00:08:40,630 --> 00:08:44,840
svet a nájsť uzol v našom Trie,
ale my nie sme úplne neskončil.

151
00:08:44,840 --> 00:08:46,350
Nechceme sa len vrátiť true.

152
00:08:46,350 --> 00:08:51,400
Chceme sa vrátiť kurzor chybovú slovo
pretože pamätať znovu, pokiaľ nie je mačka

153
00:08:51,400 --> 00:08:55,140
v našom slovníku a katastrofa je,
potom budeme úspešne prejsť

154
00:08:55,140 --> 00:08:59,810
slovo mačka, ale kurzor slovo
bude False a nie je pravda.

155
00:08:59,810 --> 00:09:04,990
Takže sa vrátime kurzora slovo pre označenie
či tento uzol je vlastne slovo,

156
00:09:04,990 --> 00:09:06,530
a je to pre kontrolu.

157
00:09:06,530 --> 00:09:08,310
>> Takže poďme sa pozrieť na veľkosť.

158
00:09:08,310 --> 00:09:11,410
Takže veľkosť bude celkom jednoduché
pretože, pamätajte na zaťaženie, sme

159
00:09:11,410 --> 00:09:15,480
zvyšovanie veľkosť slovníka pre
každé slovo, že sa stretávame.

160
00:09:15,480 --> 00:09:20,820
Takže Veľkosť sa práve chystá k návratu
slovník veľkosti, a to je všetko.

161
00:09:20,820 --> 00:09:24,650
>> Dobre, takže nakoniec máme Uvoľniť.

162
00:09:24,650 --> 00:09:29,050
Takže uvoľniť, budeme používať
rekurzívne funkcie, ktorá vlastne robiť všetko

163
00:09:29,050 --> 00:09:33,390
práca pre nás, tak naše funkcie
sa bude nazývaný Unloader.

164
00:09:33,390 --> 00:09:35,830
Čo je Unloader robiť?

165
00:09:35,830 --> 00:09:40,640
Vidíme tu, že Unloader sa chystá
iterovat cez všetky deti na

166
00:09:40,640 --> 00:09:45,810
Tento konkrétny uzol, a v prípade, že dieťa
uzol nie je null, potom budeme

167
00:09:45,810 --> 00:09:47,760
vyložiť podriadený uzol.

168
00:09:47,760 --> 00:09:52,070
>> Takže to bude rekurzívne
vyložiť všetky naše deti.

169
00:09:52,070 --> 00:09:55,140
Potom, čo sme si istí, že všetky naše deti
boli vyložené, a potom sme

170
00:09:55,140 --> 00:09:58,830
môže oslobodiť, tak vyložiť sami.

171
00:09:58,830 --> 00:10:04,550
Takže to bude rekurzívne uvoľniť
Celý Trie, a potom ešte raz, že je

172
00:10:04,550 --> 00:10:06,910
hotovo, môžeme len vrátiť true.

173
00:10:06,910 --> 00:10:09,770
Uvoľniť nemôže zlyhať, že sme
len uvoľnenie veci.

174
00:10:09,770 --> 00:10:12,985
Takže akonáhle sme hotoví uvoľnenie
všetko, vráti hodnotu true.

175
00:10:12,985 --> 00:10:14,380
A to je všetko.

176
00:10:14,380 --> 00:10:16,792
Volám sa Rob, a to
bol [nepočuteľný].

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