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

2
00:00:00,530 --> 00:00:03,070
>> SPEAKER 1: Dejme
toto řešení vyzkoušet.

3
00:00:03,070 --> 00:00:07,130
Takže pojďme se podívat na to, co naše
Struct uzel bude vypadat.

4
00:00:07,130 --> 00:00:11,040
Zde vidíme, že budeme mít
Bool Word a struct uzel hvězda

5
00:00:11,040 --> 00:00:12,990
Děti bracketing abecedu.

6
00:00:12,990 --> 00:00:18,720
Takže první věc, kterou byste mohli být zvědaví,
Proto je abeceda hash definována jako 27?

7
00:00:18,720 --> 00:00:22,540
No, pamatujte, že budeme potřebovat
se manipulace apostrof, tak

8
00:00:22,540 --> 00:00:25,610
že to bude poněkud zvláštní
pouzdro na celém tomto programu.

9
00:00:25,610 --> 00:00:28,780
>> OK, teď si vzpomenout, jak
Trie skutečně funguje.

10
00:00:28,780 --> 00:00:33,420
Řekněme, že jsme indexování slovo kočky,
pak z kořene naší Trie,

11
00:00:33,420 --> 00:00:36,670
jdeme se podívat na děti
pole, a budeme se dívat na

12
00:00:36,670 --> 00:00:42,250
index, který odpovídá na dopis
C. Tak že by index dva.

13
00:00:42,250 --> 00:00:46,400
Takže vzhledem k tomu, že se nám
nový uzel, a pak budeme

14
00:00:46,400 --> 00:00:47,880
práce z tohoto uzlu.

15
00:00:47,880 --> 00:00:51,830
>> Takže za předpokladu, že uzel, jsme opět
se podíváme na poli děti,

16
00:00:51,830 --> 00:00:56,170
a jdeme se podívat na indexu nula
tak, aby odpovídal A v kočky.

17
00:00:56,170 --> 00:01:01,240
Takže jsme jít do tohoto uzlu,
a vzhledem k tomu, že uzel, jedeme

18
00:01:01,240 --> 00:01:05,170
se podívat na index, který odpovídá
na T. a pohybuje se na tomto uzlu,

19
00:01:05,170 --> 00:01:09,590
Nakonec jsme zcela podíval
prostřednictvím naší slovo kočka, a teď Bool

20
00:01:09,590 --> 00:01:15,020
Slovo má ukázat, zda
to dané slovo je vlastně slovo.

21
00:01:15,020 --> 00:01:17,530
>> Tak proč potřebujeme ten zvláštní případ?

22
00:01:17,530 --> 00:01:21,680
No, co když slovo katastrofa
je v našem slovníku, ale

23
00:01:21,680 --> 00:01:24,120
slovo kočka není?

24
00:01:24,120 --> 00:01:29,030
Takže v pohledu, zda je slovo kočka
v našem slovníku, budeme

25
00:01:29,030 --> 00:01:34,880
úspěšně prohlédnout indexů
C-A-T a dosáhnout uzel, ale to je

26
00:01:34,880 --> 00:01:39,760
jen proto, že katastrofa se stalo
vytvářet uzly na cestě z C-A-T všechny

27
00:01:39,760 --> 00:01:41,250
způsob, jak se na konci slova.

28
00:01:41,250 --> 00:01:46,520
Takže Bool Word se používá uveďte, zda
Tento konkrétní místo skutečně

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

30
00:01:48,370 --> 00:01:52,920
>> Dobře, tak teď, když víme, co
Trie bude vypadat, pojďme se podívat

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

32
00:01:54,800 --> 00:01:58,670
Takže zatížení se chystá vrátit Bool
na tom, zda se nám podařilo nebo

33
00:01:58,670 --> 00:02:03,020
neúspěšně načíst slovník a
to bude slovník

34
00:02:03,020 --> 00:02:04,520
které chceme načíst.

35
00:02:04,520 --> 00:02:08,310
Takže první věc, kterou se chystáte udělat, je otevřít
do tohoto slovníku pro čtení.

36
00:02:08,310 --> 00:02:12,060
Musíme se ujistit, že nezklamal,
takže pokud slovník nebyl

37
00:02:12,060 --> 00:02:15,280
úspěšně otevřen, vrátí
No, v tom případě budeme

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

39
00:02:16,340 --> 00:02:21,290
Avšak za předpokladu, že se úspěšně
otevřel, pak můžeme skutečně číst

40
00:02:21,290 --> 00:02:22,310
pomocí slovníku.

41
00:02:22,310 --> 00:02:24,940
>> Takže první věc, kterou budeme
chcete udělat, je, že jsme si to

42
00:02:24,940 --> 00:02:26,560
globální proměnná kořen.

43
00:02:26,560 --> 00:02:30,250
Nyní, kořen se bude uzel hvězda.

44
00:02:30,250 --> 00:02:33,830
Je to vrchol naší Trie, že jsme
bude iterace.

45
00:02:33,830 --> 00:02:38,200
Takže první věc, kterou budeme chtít
udělat, je alokovat paměť pro náš kořen.

46
00:02:38,200 --> 00:02:42,040
>> Všimněte si, že jsme pomocí calloc
funkce, která je v podstatě stejná

47
00:02:42,040 --> 00:02:45,560
jako funkce malloc, kromě toho, že je
zaručeno, že vrátí něco, co je

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

49
00:02:47,240 --> 00:02:51,350
Takže pokud jsme použili malloc, potřebovali bychom, aby
projít všechny ukazatele v naší

50
00:02:51,350 --> 00:02:54,220
uzel a ujistěte se, že
všichni jsou null.

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

52
00:02:56,780 --> 00:03:00,390
>> Nyní, stejně jako malloc, je třeba, aby
Ujistěte se, že rozdělení je ve skutečnosti

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

54
00:03:01,580 --> 00:03:04,060
Pokud to vrátil null, pak
je třeba uzavřít naši slovník

55
00:03:04,060 --> 00:03:06,170
souboru a vrátí False.

56
00:03:06,170 --> 00:03:11,040
Takže za předpokladu, že rozdělení bylo
úspěšná, budeme používat uzel

57
00:03:11,040 --> 00:03:14,340
hvězda kurzor na iteraci
prostřednictvím naší Trie.

58
00:03:14,340 --> 00:03:17,950
Takže naše kořen se nikdy nezmění,
ale budeme používat kurzor na

59
00:03:17,950 --> 00:03:20,770
skutečně jít z uzlu do uzlu.

60
00:03:20,770 --> 00:03:25,000
>> Dobře, takže v tomto pro smyčce, jsme
přečtení souboru slovníku,

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

62
00:03:26,965 --> 00:03:30,360
Takže fgetc se chystá chytit jeden
znak ze souboru.

63
00:03:30,360 --> 00:03:33,430
Budeme pokračovat v popadat
znaky, zatímco my nedosahují

64
00:03:33,430 --> 00:03:37,540
konec souboru, takže jsou
dvě případů musíme zvládnout.

65
00:03:37,540 --> 00:03:41,640
První z nich, v případě, že znak nebyl
nová linka, takže víme, že kdyby to byl nový

66
00:03:41,640 --> 00:03:44,480
linka, pak se chystáme
přejít na nové slovo.

67
00:03:44,480 --> 00:03:49,300
Ale za předpokladu, že nebyl nový řádek, pak
tady, chceme zjistit,

68
00:03:49,300 --> 00:03:52,440
index jedeme do indexu do
v poli Děti, které

69
00:03:52,440 --> 00:03:53,890
jsme se podívali na před.

70
00:03:53,890 --> 00:03:57,950
>> Takže jak jsem řekl dříve, je třeba, aby
Zvláštním případem apostrof.

71
00:03:57,950 --> 00:04:01,040
Všimněte si, jsme pomocí ternární operátor
tady, tak budeme číst

72
00:04:01,040 --> 00:04:05,500
to, jako kdyby postava čteme v to
apostrof, pak budeme

73
00:04:05,500 --> 00:04:11,740
nastavit index se rovná abecedy minus
1, který bude index 26..

74
00:04:11,740 --> 00:04:15,190
Jinak, pokud to není apostrof,
pak budeme nastavit index

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

76
00:04:17,820 --> 00:04:23,090
Takže pamatujte zpět z dřívějších p sad,
c minus se chystá dát nám

77
00:04:23,090 --> 00:04:27,470
abecední pozice c, takže pokud
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
Pro písmeno B, bylo by to dát
nám index 1, a tak dále.

80
00:04:32,180 --> 00:04:37,070
>> Tak to nám dává index do
Děti pole, které chceme.

81
00:04:37,070 --> 00:04:42,540
Nyní, v případě, že index je v současné době v null
Děti pole, to znamená, že

82
00:04:42,540 --> 00:04:47,470
uzel nemá v současné době neexistuje z
, že cesta, takže musíme přidělit

83
00:04:47,470 --> 00:04:49,220
uzel pro tuto cestu.

84
00:04:49,220 --> 00:04:50,610
To je to, co děláme tady.

85
00:04:50,610 --> 00:04:54,650
Takže budeme opět používat calloc
funkce, takže nemáme

86
00:04:54,650 --> 00:05:00,130
k vynulování všech ukazatelů, a my,
znovu, je třeba zkontrolovat, že calloc

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

88
00:05:01,300 --> 00:05:04,760
Pokud calloc to nepodaří, pak musíme
vyložit všechno, zavřeme

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

90
00:05:06,880 --> 00:05:14,110
>> Takže za předpokladu, že to nebylo selhání, pak
to bude vytvořit novou dítě pro nás,

91
00:05:14,110 --> 00:05:16,000
a pak půjdeme na to dítě.

92
00:05:16,000 --> 00:05:19,030
Naše kurzor bude přecházet
se k tomuto dítěti.

93
00:05:19,030 --> 00:05:23,390
Nyní, pokud to není null začít s,
pak se kurzor může pouze iterovat

94
00:05:23,390 --> 00:05:26,650
se k tomuto dítěti, aniž by ve skutečnosti
museli přidělit nic.

95
00:05:26,650 --> 00:05:30,790
To je případ, kdy jsme se poprvé stalo
přidělit slovo kočka, a

96
00:05:30,790 --> 00:05:34,390
to znamená, že když jdeme na přidělení
katastrofa, nepotřebujeme vytvářet

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

98
00:05:35,720 --> 00:05:37,620
Již existují.

99
00:05:37,620 --> 00:05:40,140
>> OK, takže to, co je to jiný?

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

101
00:05:44,600 --> 00:05:47,780
To znamená, že se nám podařilo mít
dokončil slovo.

102
00:05:47,780 --> 00:05:51,020
A teď, co chceme dělat, když jsme
úspěšně dokončil slovo?

103
00:05:51,020 --> 00:05:55,250
Budeme používat toto slovo pole
v naší struct uzel.

104
00:05:55,250 --> 00:06:00,570
>> Chceme nastavit, aby se na True, aby
znamená, že tento uzel označuje

105
00:06:00,570 --> 00:06:03,320
úspěšný slovo skutečné slovo.

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

107
00:06:05,050 --> 00:06:09,210
Chceme obnovit naše kurzor na místo
na začátku Trie znovu.

108
00:06:09,210 --> 00:06:13,510
A konečně, zvýšit náš slovník
velikost, protože jsme našli další slovo.

109
00:06:13,510 --> 00:06:16,450
>> Dobře, takže budeme pokračovat v tom
, že čtení v znaku

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

111
00:06:21,960 --> 00:06:26,810
slovník, až jsme konečně dosáhnout c
rovná EOF, v tomto případě jsme se zlomit

112
00:06:26,810 --> 00:06:28,100
ze souboru.

113
00:06:28,100 --> 00:06:31,110
Nyní máme k dispozici dva případy podle
které jsme mohli zasáhnout EOF.

114
00:06:31,110 --> 00:06:35,680
První z nich je, zda došlo k chybě
čtení ze souboru, takže v případě, že byl

115
00:06:35,680 --> 00:06:39,280
chyba, kterou musíme udělat, typické
vyložit vše, zavřete soubor,

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

117
00:06:40,520 --> 00:06:43,870
Za předpokladu, že není chyba, která
jen znamená, že jsme vlastně hit na konec

118
00:06:43,870 --> 00:06:47,820
soubor, v tom případě, zavřeme
soubor a vrátit True, protože jsme

119
00:06:47,820 --> 00:06:51,010
úspěšně načten slovníku
do našeho Trie.

120
00:06:51,010 --> 00:06:54,240
>> Dobře, tak teď pojďme
podívejte se na kontrolu.

121
00:06:54,240 --> 00:06:58,780
Při pohledu na Zkontrolujte funkci, vidíme,
která Kontrola se chystá vrátit Bool.

122
00:06:58,780 --> 00:07:03,740
Vrací TRUE, pokud to slovo, které je
byly přeneseny, je v našem Trie.

123
00:07:03,740 --> 00:07:06,170
Vrací False jinak.

124
00:07:06,170 --> 00:07:10,110
>> Tak jak se budeme k určení, zda
toto slovo je v našem Trie?

125
00:07:10,110 --> 00:07:14,270
Vidíme zde, že stejně jako předtím,
budeme používat kurzor na iteraci

126
00:07:14,270 --> 00:07:16,010
prostřednictvím naší Trie.

127
00:07:16,010 --> 00:07:20,650
Teď, tady, jedeme na iteraci
v celém našem slova.

128
00:07:20,650 --> 00:07:24,680
Takže iterace přes slovo jsme
prošel, jdeme zjistit,

129
00:07:24,680 --> 00:07:29,280
index do pole dětí, které
odpovídá slovo konzole i.

130
00:07:29,280 --> 00:07:34,150
Takže to bude vypadat přesně jako
Zatížení, kde pokud slovo držák i je

131
00:07:34,150 --> 00:07:38,110
apostrof, pak chceme použít index
abeceda minus 1, protože jsme zjistili,

132
00:07:38,110 --> 00:07:41,160
že je místo, kde budeme
uložit apostrofy.

133
00:07:41,160 --> 00:07:44,440
>> Jinak budeme používat tolower
Slovo držák i.

134
00:07:44,440 --> 00:07:48,270
Takže nezapomeňte, že slovo může mít libovolný
kapitalizace, a tak jsme

135
00:07:48,270 --> 00:07:51,590
chcete, aby se ujistil, že jsme pomocí
malá verze věcí.

136
00:07:51,590 --> 00:07:55,300
A pak odečíst od té malými písmeny
na, opět nám

137
00:07:55,300 --> 00:07:57,940
abecední pozice
tohoto charakteru.

138
00:07:57,940 --> 00:08:01,740
Tak, že to bude náš index
do pole děti.

139
00:08:01,740 --> 00:08:06,480
>> A teď, jestli je to index do dětí
pole je null, to znamená, že

140
00:08:06,480 --> 00:08:09,050
již nemůže pokračovat iterace
se naší Trie.

141
00:08:09,050 --> 00:08:13,320
Pokud je tomu tak, nemůže toto slovo není
mohlo být v našem Trie, protože v případě, že

142
00:08:13,320 --> 00:08:18,000
se, že by to znamenalo, že by se
Cesta dolů do tohoto slova, a vy by

143
00:08:18,000 --> 00:08:19,350
nikdy setkat null.

144
00:08:19,350 --> 00:08:21,910
Takže setkání null, vrátíme False.

145
00:08:21,910 --> 00:08:23,810
Slovo není ve slovníku.

146
00:08:23,810 --> 00:08:28,200
Pokud by tomu tak nebylo null, pak budeme
pokračovat iterace, takže jdeme

147
00:08:28,200 --> 00:08:33,150
aktualizovat naše kurzor poukázat na to
zejména uzel v daném indexu.

148
00:08:33,150 --> 00:08:36,659
>> Tak jsme se pokračovat v tom, že po celou dobu
celé slovo.

149
00:08:36,659 --> 00:08:40,630
Za předpokladu, že jsme se nikdy hit null, že prostředky
jsme byli schopni se dostat přes celé

150
00:08:40,630 --> 00:08:44,840
svět a najít uzel v našem Trie,
ale my nejsme úplně neskončil.

151
00:08:44,840 --> 00:08:46,350
Nechceme se jen vrátit true.

152
00:08:46,350 --> 00:08:51,400
Chceme se vrátit kurzor chybovou slovo
protože pamatovat znovu, pokud není kočka

153
00:08:51,400 --> 00:08:55,140
v našem slovníku a katastrofa je,
pak budeme úspěšně projít

154
00:08:55,140 --> 00:08:59,810
slovo kočka, ale kurzor slovo
bude False a není pravda.

155
00:08:59,810 --> 00:09:04,990
Takže se vrátíme kurzoru slovo pro označení
zda tento uzel je vlastně slovo,

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

157
00:09:06,530 --> 00:09:08,310
>> Takže pojďme se podívat na velikost.

158
00:09:08,310 --> 00:09:11,410
Takže velikost bude docela snadné
protože, pamatujte na zatížení, jsme

159
00:09:11,410 --> 00:09:15,480
zvyšování velikost slovníku pro
každé slovo, že se setkáváme.

160
00:09:15,480 --> 00:09:20,820
Takže Velikost se právě chystá k návratu
slovník velikosti, a to je vše.

161
00:09:20,820 --> 00:09:24,650
>> Dobře, takže nakonec máme Uvolnit.

162
00:09:24,650 --> 00:09:29,050
Takže uvolnit, budeme používat
rekurzivní funkce, která vlastně dělat vše

163
00:09:29,050 --> 00:09:33,390
práce pro nás, tak naše funkce
se bude nazýván Unloader.

164
00:09:33,390 --> 00:09:35,830
Co je Unloader dělat?

165
00:09:35,830 --> 00:09:40,640
Vidíme zde, že Unloader se chystá
iterovat přes všechny děti na

166
00:09:40,640 --> 00:09:45,810
Tento konkrétní uzel, a v případě, že dítě
uzel není null, pak budeme

167
00:09:45,810 --> 00:09:47,760
vyložit podřízený uzel.

168
00:09:47,760 --> 00:09:52,070
>> Takže to bude rekurzivně
vyložit všechny naše děti.

169
00:09:52,070 --> 00:09:55,140
Poté, co jsme si jisti, že všechny naše děti
byly vyloženy, a pak jsme

170
00:09:55,140 --> 00:09:58,830
může osvobodit, tak vyložit sami.

171
00:09:58,830 --> 00:10:04,550
Takže to bude rekurzivně uvolnit
Celý Trie, a pak ještě jednou, že je

172
00:10:04,550 --> 00:10:06,910
hotovo, můžeme jen vrátit true.

173
00:10:06,910 --> 00:10:09,770
Uvolnit nemůže selhat, že jsme
jen uvolnění věci.

174
00:10:09,770 --> 00:10:12,985
Takže jakmile jsme hotovi uvolnění
vše, vrátí hodnotu true.

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

176
00:10:14,380 --> 00:10:16,792
Jmenuji se Rob, a to
byl [neslyšitelný].

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