1
00:00:00,000 --> 00:00:09,700

2
00:00:09,700 --> 00:00:12,140
>> ZAMYLA CHAN: Udělejme
pravopisu.

3
00:00:12,140 --> 00:00:16,900
Pokud otevřete speller.c, pak uvidíte,
že většinu funkcí pro

4
00:00:16,900 --> 00:00:20,810
kontrola textového souboru proti
Slovník je již na vás.

5
00:00:20,810 --> 00:00:26,330
. / Kontrola pravopisu, procházející ve slovníku textu
souboru a pak další textový soubor,

6
00:00:26,330 --> 00:00:28,960
bude kontrolovat, že textový soubor
proti slovníku.

7
00:00:28,960 --> 00:00:34,160
>> Nyní se slovníkem textové soubory obsahují
platí slova, na každý řádek jednu.

8
00:00:34,160 --> 00:00:37,910
Pak speller.c bude volat zatížení
na slovníku textového souboru.

9
00:00:37,910 --> 00:00:43,650
Je to volání funkce s názvem Podívejte se na
každé slovo v zadaném textovém souboru,

10
00:00:43,650 --> 00:00:46,460
tisk všech slov s chybným pravopisem.

11
00:00:46,460 --> 00:00:50,030
>> Speller.c bude také volat Size
určení počtu slov v

12
00:00:50,030 --> 00:00:53,500
slovník a zavolejte Uvolnit
uvolnit paměť.

13
00:00:53,500 --> 00:00:57,600
speller.c bude také sledovat, jak
hodně času se používá k provedení těchto

14
00:00:57,600 --> 00:01:00,560
procesy, ale budeme
se k tomu později.

15
00:01:00,560 --> 00:01:02,440
>> Takže to, co musíme udělat?

16
00:01:02,440 --> 00:01:05,110
Musíme vyplnit dictionary.c.

17
00:01:05,110 --> 00:01:09,940
V dictionary.c, máme pomocníka
Funkce Load, který načte

18
00:01:09,940 --> 00:01:10,855
slovník.

19
00:01:10,855 --> 00:01:15,490
Funkce Kontrola, která zkontroluje, zda
dané slovo je ve slovníku.

20
00:01:15,490 --> 00:01:19,150
Funkce vrací číslo Size
slov ve slovníku.

21
00:01:19,150 --> 00:01:24,870
A nakonec jsme Uvolnit, které
osvobozuje slovník z paměti.

22
00:01:24,870 --> 00:01:27,070
>> Tak za prvé, pojďme řešit zatížení.

23
00:01:27,070 --> 00:01:32,110
Pro každé slovo ve slovníku textu
soubor, zatížení bude ukládat tato slova

24
00:01:32,110 --> 00:01:34,860
slovník datová struktura
dle vašeho výběru, a to buď

25
00:01:34,860 --> 00:01:36,750
hash tabulky nebo trie.

26
00:01:36,750 --> 00:01:39,440
Půjdu na to jak v
to projít.

27
00:01:39,440 --> 00:01:43,150
>> Nejprve pojďme mluvit o hash tabulky.

28
00:01:43,150 --> 00:01:47,050
Řekněme, že máte 10 kulečníkové koule a
byste chtěli, aby jim uložit.

29
00:01:47,050 --> 00:01:50,420
Ty by mohly dát je všechny do kbelíku,
a když si potřeboval specifické

30
00:01:50,420 --> 00:01:54,010
číslované koule, měli byste vzít jednu
z nádoby v době

31
00:01:54,010 --> 00:01:55,880
hledá pro tuto kouli.

32
00:01:55,880 --> 00:01:59,370
A pouze 10 míčů, měli byste být
schopni najít si míč v přiměřené

33
00:01:59,370 --> 00:02:01,160
množství času.

34
00:02:01,160 --> 00:02:03,180
>> Ale co když jste měli 20 koule?

35
00:02:03,180 --> 00:02:05,480
To může trvat trochu déle, teď.

36
00:02:05,480 --> 00:02:06,180
Co je 100?

37
00:02:06,180 --> 00:02:07,880
1000?

38
00:02:07,880 --> 00:02:11,590
Nyní by bylo mnohem jednodušší, pokud
jste měli více kbelíky.

39
00:02:11,590 --> 00:02:15,890
Možná, že jeden kbelík na míčky očíslovány nulu
přes devět, další kbelík pro

40
00:02:15,890 --> 00:02:18,800
koule číslovány 10 až
19, a tak dále.

41
00:02:18,800 --> 00:02:22,330
>> Nyní, když jste potřebovali podívat se na konkrétní
míč, mohl automaticky

42
00:02:22,330 --> 00:02:26,320
jít na jednu konkrétní kbelíku a
hledat prostřednictvím tohoto kbelíku.

43
00:02:26,320 --> 00:02:29,840
A pokud každý kbelík má přibližně 10
koule, pak byste mohli snadno vyhledávat

44
00:02:29,840 --> 00:02:31,790
přes něj.

45
00:02:31,790 --> 00:02:34,960
>> Nyní, protože máme co do činění s
slovníky, jediný kbelík pro

46
00:02:34,960 --> 00:02:41,970
všechna slova ve slovníku bude
pravděpodobně příliš málo kbelíky.

47
00:02:41,970 --> 00:02:44,370
Takže pojďme se podívat na tabulky hash.

48
00:02:44,370 --> 00:02:46,940
>> Ber to jako pole kbelíky.

49
00:02:46,940 --> 00:02:50,370
A v tomto případě, kbelíky
jsou naše spojové seznamy.

50
00:02:50,370 --> 00:02:54,770
A budeme distribuovat všechny naše slova
mezi těmito několika propojených seznamů v

51
00:02:54,770 --> 00:02:58,940
organizovaný způsob, jak pomocí funkce hash,
který nám řekne, které

52
00:02:58,940 --> 00:03:03,720
lžíce daný klíč, vzhledem
slovo, patří.

53
00:03:03,720 --> 00:03:05,960
>> Pojďme představují to schematicky.

54
00:03:05,960 --> 00:03:11,320
Modrá krabice zde obsahují hodnoty a
červené krabičky poukazují na jinou hodnotu

55
00:03:11,320 --> 00:03:12,280
ukazatel pár.

56
00:03:12,280 --> 00:03:14,800
Zavoláme těchto dvojic uzlů.

57
00:03:14,800 --> 00:03:18,260
Nyní, každý kbelík, jak jsem řekl,
dříve, je spojový seznam.

58
00:03:18,260 --> 00:03:21,820
V propojené seznamy, každý uzel má hodnotu,
stejně jako ukazatel

59
00:03:21,820 --> 00:03:23,170
další hodnota.

60
00:03:23,170 --> 00:03:26,150
>> Nyní, zabývající se spojových seznamů,
to je velmi důležité, aby vám

61
00:03:26,150 --> 00:03:28,120
neztrácejí žádné odkazy.

62
00:03:28,120 --> 00:03:32,250
A další je uvědomit si fakt, že
poslední uzel, je-li to neukazuje na

63
00:03:32,250 --> 00:03:35,120
jiný uzel, ukazuje na null.

64
00:03:35,120 --> 00:03:37,970
>> Tak jak jsme se reprezentovat to v C?

65
00:03:37,970 --> 00:03:40,540
Jsme zde definovat naši struct.

66
00:03:40,540 --> 00:03:44,850
A hodnota je v tomto případě
char pole délky.

67
00:03:44,850 --> 00:03:48,880
Délka plus 1, kde délka je
Maximální délka každého slova, plus 1 za

68
00:03:48,880 --> 00:03:50,380
null terminátor.

69
00:03:50,380 --> 00:03:54,210
A pak máme ukazatel na
jiný uzel s názvem Next.

70
00:03:54,210 --> 00:03:56,730
>> Takže pojďme udělat malou propojeného seznamu.

71
00:03:56,730 --> 00:04:00,390
Za prvé, budete chtít, aby malloc váš uzel,
které vytvářejí prostor v paměti

72
00:04:00,390 --> 00:04:04,010
velikost vašeho typu uzlu.

73
00:04:04,010 --> 00:04:06,100
A provést další uzel,
znovu mallocing.

74
00:04:06,100 --> 00:04:09,370

75
00:04:09,370 --> 00:04:14,340
>> Nyní, pokud chcete přiřadit hodnotu
slovo, pak bychom mohli říci, UZEL1 šipku

76
00:04:14,340 --> 00:04:18,820
slovo rovno "Dobrý den." Tento operátor šipka
dereferences ukazatel a

77
00:04:18,820 --> 00:04:20,620
přistupuje proměnné struct je.

78
00:04:20,620 --> 00:04:24,330
Tímto způsobem, nemusíme používat jak
tečka a provozovatel hvězda.

79
00:04:24,330 --> 00:04:30,100
>> Tak jsem si node2 šipka slovo rovno
"Svět." A tam, hodnoty jsou

80
00:04:30,100 --> 00:04:33,110
naplněna v mých uzlů.

81
00:04:33,110 --> 00:04:38,780
Chcete-li odkazy, předám v node1
šipku, přístup uzel hvězdu,

82
00:04:38,780 --> 00:04:44,160
že ukazatel uzel, rovná node2,
ukázal node1 node2 dva.

83
00:04:44,160 --> 00:04:46,360
A tady máme propojeného seznamu.

84
00:04:46,360 --> 00:04:51,480
>> Takže to byl jen jeden spojový seznam, ale
hash tabulka je celá řada

85
00:04:51,480 --> 00:04:52,520
spojové seznamy.

86
00:04:52,520 --> 00:04:55,920
No, budeme mít stejný uzel
strukturu jako předtím.

87
00:04:55,920 --> 00:05:00,140
Ale pokud jsme chtěli skutečnou hash tabulky,
pak můžeme jen aby ukazatel uzlu

88
00:05:00,140 --> 00:05:01,330
array zde.

89
00:05:01,330 --> 00:05:04,940
Například, velikost 500.

90
00:05:04,940 --> 00:05:08,910
>> Nyní oznámení, že to bude obchod
off mezi velikostí svého

91
00:05:08,910 --> 00:05:11,280
hash tabulky a velikost
vaše spojových seznamů.

92
00:05:11,280 --> 00:05:15,640
Pokud máte opravdu velký počet
kbelíky, představoval si museli běžet zpátky

93
00:05:15,640 --> 00:05:18,230
a dále v souladu s
najít svůj kbelík.

94
00:05:18,230 --> 00:05:21,530
Ale také nechci malý počet
lopat, protože pak jsme zpátky

95
00:05:21,530 --> 00:05:26,850
původní problém, jak s
příliš mnoho míčů v naší kbelíku.

96
00:05:26,850 --> 00:05:30,480
>> OK, ale tam, kde se naše míč jít?

97
00:05:30,480 --> 00:05:33,150
No, musíme nejprve
mít míč, ne?

98
00:05:33,150 --> 00:05:39,130
Takže pojďme malloc uzel pro každý
nové slovo, které máme.

99
00:05:39,130 --> 00:05:42,900
uzel * new_node rovná
malloc (sizeof (node)).

100
00:05:42,900 --> 00:05:46,760
>> Nyní, když máme tuto strukturu, jsme
můžete skenovat pomocí funkce

101
00:05:46,760 --> 00:05:51,850
fscanf, řetězec z našeho souboru, pokud
to je soubor slovníku, do

102
00:05:51,850 --> 00:05:55,780
new_node šipka slovo, kde new_node
arrow slovo je naše

103
00:05:55,780 --> 00:05:58,110
cílem tohoto slova.

104
00:05:58,110 --> 00:06:01,900
>> Dále budeme chtít hash, že
Slovo pomocí hash funkce.

105
00:06:01,900 --> 00:06:05,860
Hašovací funkce má řetězec
a vrátí index.

106
00:06:05,860 --> 00:06:09,760
V tomto případě, má index
být menší, než je počet

107
00:06:09,760 --> 00:06:11,440
kbelíky, které máte.

108
00:06:11,440 --> 00:06:14,600
>> Nyní, hashovací funkce, když se snažíte
najít jeden a vytvořit jednu z

109
00:06:14,600 --> 00:06:17,890
vlastní, pamatujte, že
musí být deterministický.

110
00:06:17,890 --> 00:06:22,420
To znamená, že stejná hodnota musí
Pro na stejnou nádobu pokaždé

111
00:06:22,420 --> 00:06:23,800
že jste to hash.

112
00:06:23,800 --> 00:06:25,300
>> Je to něco jako knihovna.

113
00:06:25,300 --> 00:06:28,560
Když budete mít knihu, založenou na
autor, víte, které police by měla

114
00:06:28,560 --> 00:06:31,890
dál, ať už je to číslo police
jeden, dva, nebo tři.

115
00:06:31,890 --> 00:06:36,280
A že kniha bude vždy patřit na
buď police jeden, dva, nebo tři.

116
00:06:36,280 --> 00:06:39,460

117
00:06:39,460 --> 00:06:43,810
>> Takže, pokud new_node šipka Slovo má
Slovo z vašeho slovníku, pak

118
00:06:43,810 --> 00:06:47,770
hash new_node šipka slovo bude
nám index

119
00:06:47,770 --> 00:06:49,370
kbelík tabulky hash.

120
00:06:49,370 --> 00:06:54,040
A pak budeme vkládat, že do toho
specifické spojový seznam indikována

121
00:06:54,040 --> 00:06:56,060
vrátí hodnotu naší hash funkce.

122
00:06:56,060 --> 00:06:59,070
>> Podívejme se na příklad
vložení uzlu do

123
00:06:59,070 --> 00:07:01,750
začátek propojeného seznamu.

124
00:07:01,750 --> 00:07:06,930
Je-li hlava je uzel ukazatel, který naznačuje,
počátek souvisí

125
00:07:06,930 --> 00:07:12,420
seznam, a new_node indikuje nové
uzel, který chcete zadat v, jen

126
00:07:12,420 --> 00:07:17,340
přiřazení hlavu, aby new_node ztratí
odkaz na zbytku seznamu.

127
00:07:17,340 --> 00:07:19,330
Takže nechceme to dělat.

128
00:07:19,330 --> 00:07:22,160
>> Spíše chceme, aby se ujistil,
že máme na každý

129
00:07:22,160 --> 00:07:23,550
jeden uzel v našem programu.

130
00:07:23,550 --> 00:07:29,560
Takže běh new_node šipku vedle rovná
hlava a pak hlava rovná new_node

131
00:07:29,560 --> 00:07:34,470
zachová všechny
odkazy a neztratily nic.

132
00:07:34,470 --> 00:07:39,330
>> Ale co když chcete, aby váš seznam být
dále, protože když řazeny spojené

133
00:07:39,330 --> 00:07:42,910
Seznam by mohl být jednodušší
hledání na později?

134
00:07:42,910 --> 00:07:46,020
No, na to, že budete potřebovat vědět,
jak přejít propojené seznamy.

135
00:07:46,020 --> 00:07:51,210
>> Chcete-li procházet spojový seznam, pojďme se
uzel ukazatel, uzel *, působit jako

136
00:07:51,210 --> 00:07:54,120
kurzor, označující, do kterého
uzlu jste na, počínaje

137
00:07:54,120 --> 00:07:55,460
na první prvek.

138
00:07:55,460 --> 00:08:01,070
Opakování, dokud kurzor je null, můžeme
provádět určité procesy a pak

139
00:08:01,070 --> 00:08:04,330
posuňte kurzor, když potřebujeme
pomocí kurzoru šipky hodnoty.

140
00:08:04,330 --> 00:08:08,820
>> Pamatujte si, že to je totéž jako
říká hvězda kurzor, dereferencing

141
00:08:08,820 --> 00:08:13,480
kurzor, poté pomocí
dot hodnota operátor.

142
00:08:13,480 --> 00:08:19,000
Tak aktualizace kurzor je přiřazením
kurzor na šipku vedle kurzoru.

143
00:08:19,000 --> 00:08:24,960
>> Řekněme, že zjistíte, že D se v
mezi C a E. Pro vložení uzlu,

144
00:08:24,960 --> 00:08:30,030
mají new_node D přejděte na
uzel E, což je další kurzor.

145
00:08:30,030 --> 00:08:36,409
A pak C, kurzor, pak může ukázat
až D. Tímto způsobem můžete udržovat seznam.

146
00:08:36,409 --> 00:08:41,080
Dávejte pozor, abyste neztratili své odkazy podle
pohybem kurzoru šipku vedle D

147
00:08:41,080 --> 00:08:43,929
hned.

148
00:08:43,929 --> 00:08:44,620
>> Dobrá.

149
00:08:44,620 --> 00:08:48,920
Tak to je, jak byste mohli vložit uzly,
vkládejte do, zatížení slova do těch

150
00:08:48,920 --> 00:08:51,600
uzly, a vložte je
do hash tabulky.

151
00:08:51,600 --> 00:08:53,580
Takže teď se pojďme podívat na pokusech.

152
00:08:53,580 --> 00:08:58,540
>> V trie, bude každý uzel obsahovat
pole uzlu ukazatelů, jeden pro každý

153
00:08:58,540 --> 00:09:02,260
písmeno v abecedě
a apostrof.

154
00:09:02,260 --> 00:09:06,150
A každý prvek v poli
bude ukazovat na jiný uzel.

155
00:09:06,150 --> 00:09:10,130
Je-li, že uzel je null, pak ten dopis
se nebude příští dopis

156
00:09:10,130 --> 00:09:15,690
nějaké slovo v pořadí, protože každá
Slovo označuje, zda je to poslední

157
00:09:15,690 --> 00:09:18,160
znak slova, nebo ne.

158
00:09:18,160 --> 00:09:19,750
>> Pojďme se podívat na diagramu.

159
00:09:19,750 --> 00:09:22,260
Doufejme, že to bude
být trochu jasnější.

160
00:09:22,260 --> 00:09:27,210
V tomto diagramu vidíme, že pouze
některé dopisy a některé podřetězce

161
00:09:27,210 --> 00:09:28,190
jsou uvedeny ven.

162
00:09:28,190 --> 00:09:32,500
Takže můžete sledovat určité cesty, a
všech těchto cest vás dovede k

163
00:09:32,500 --> 00:09:34,020
různá slova.

164
00:09:34,020 --> 00:09:37,630
>> Tak jak jsme se reprezentovat to v C?

165
00:09:37,630 --> 00:09:41,910
No, každý uzel je nyní bude mít
Logická hodnota označující, zda

166
00:09:41,910 --> 00:09:46,580
že uzel je konec
dané slovo, nebo ne.

167
00:09:46,580 --> 00:09:50,690
A pak to bude mít také řadu
ukazatele uzlu pojmenovaném děti, a

168
00:09:50,690 --> 00:09:53,440
tam se bude 27 z nich.

169
00:09:53,440 --> 00:09:56,510
A pamatujte, budete také chtít, aby
sledovat svého prvního uzlu.

170
00:09:56,510 --> 00:09:59,830
Budeme říkat, že kořen.

171
00:09:59,830 --> 00:10:01,690
>> Tak to je struktura trie.

172
00:10:01,690 --> 00:10:05,630
Jak můžeme reprezentovat tento
jako slovník?

173
00:10:05,630 --> 00:10:09,890
No, načítání slova, pro každý
slovník slovo, budete chtít

174
00:10:09,890 --> 00:10:11,960
iterovat trie.

175
00:10:11,960 --> 00:10:16,170
A každý prvek u dětí
odpovídá jiné písmeno.

176
00:10:16,170 --> 00:10:21,660
>> Takže kontrola hodnoty na děti
index i, kde i představuje

177
00:10:21,660 --> 00:10:24,840
specifický index dopisu, který
se snažíte vložit.

178
00:10:24,840 --> 00:10:28,980
No, pokud je to null, pak budete chtít
malloc nový uzel a mít děti

179
00:10:28,980 --> 00:10:31,110
i poukazují na tomto uzlu.

180
00:10:31,110 --> 00:10:35,630
>> Pokud to není null, pak to znamená, že
že vzhledem k tomu větev, že vzhledem

181
00:10:35,630 --> 00:10:37,350
podřetězec, již existuje.

182
00:10:37,350 --> 00:10:40,160
Takže pak budete jen přesunout do které
nový uzel a pokračovat.

183
00:10:40,160 --> 00:10:43,220
Pokud jste na konci slova, které
se snažíte načíst do

184
00:10:43,220 --> 00:10:48,120
slovník, pak si můžete nastavit, aby
aktuální uzel, který jste na true.

185
00:10:48,120 --> 00:10:51,550
>> Takže pojďme se podívat na příklad vložení
slovo "fox" do našich

186
00:10:51,550 --> 00:10:53,070
slovník.

187
00:10:53,070 --> 00:10:56,110
Předstírat, že začneme s
prázdný slovník.

188
00:10:56,110 --> 00:11:01,610
První písmeno, F, budou umístěny
u dětí indexu pět z kořenů

189
00:11:01,610 --> 00:11:03,700
děti pole.

190
00:11:03,700 --> 00:11:05,430
Takže vložíme že palců

191
00:11:05,430 --> 00:11:14,610
>> Písmeno O se pak u dětí
index 15, po tomto F. A pak X

192
00:11:14,610 --> 00:11:20,180
bude ještě nižší, větvení
off dětí Õ je.

193
00:11:20,180 --> 00:11:24,120
A pak, protože X je poslední písmeno
slova "liška", pak budu

194
00:11:24,120 --> 00:11:27,210
barva, která zeleně na znamení, že
to je konec slova.

195
00:11:27,210 --> 00:11:32,880
V jazyce C, který by nastavení je
Word Boolean hodnoty skutečné.

196
00:11:32,880 --> 00:11:36,780
>> Teď co když další slovo, které jste
načítá se je slovo "foo"?

197
00:11:36,780 --> 00:11:41,490
No, nemusíte se malloc víc
prostor pro F nebo O, protože

198
00:11:41,490 --> 00:11:42,990
těch, které již existují.

199
00:11:42,990 --> 00:11:45,910
Ale poslední O v foo?

200
00:11:45,910 --> 00:11:47,320
To je jeden, budete muset malloc.

201
00:11:47,320 --> 00:11:52,390
Vytvořte nový uzel pro to, že nastavení
je slovo, Boolean true.

202
00:11:52,390 --> 00:11:57,340
>> Takže teď pojďme vložit "psa." Pes bude
začít s indexem tři z kořenů

203
00:11:57,340 --> 00:12:00,520
děti, protože D nemá
nebyly vytvořeny.

204
00:12:00,520 --> 00:12:04,990
A budeme sledovat podobný proces jako
před, vytváření podřetězec psa,

205
00:12:04,990 --> 00:12:10,400
kde je G je v zelené barvě, protože
to je konec slova.

206
00:12:10,400 --> 00:12:13,160
>> A teď, co když chceme vložit "dělat"?

207
00:12:13,160 --> 00:12:17,150
No, to je podřetězec psa, tak
nepotřebujeme k malloc už.

208
00:12:17,150 --> 00:12:20,800
Ale my potřebujeme ukázat, kde máme
došli na konec tohoto slova.

209
00:12:20,800 --> 00:12:24,020
Takže O bude v zelené barvě.

210
00:12:24,020 --> 00:12:27,810
Pokračování tohoto procesu pro každý
slovo ve slovníku, jste

211
00:12:27,810 --> 00:12:32,120
naložili je do do buď do
hash tabulky nebo na trie.

212
00:12:32,120 --> 00:12:37,530
>> speller.c přejdou v řetězcích pro
dictionary.c pro kontrolu.

213
00:12:37,530 --> 00:12:41,140
Nyní, Kontrola funkce musí pracovat
v případě necitlivosti.

214
00:12:41,140 --> 00:12:45,980
To znamená, že velká písmena a
malá písmena a mix obou

215
00:12:45,980 --> 00:12:50,670
všichni měli rovnat true, pokud některý
Kombinace, které je v

216
00:12:50,670 --> 00:12:51,880
slovník.

217
00:12:51,880 --> 00:12:55,580
Můžete se také předpokládat, že řetězce jsou
jen bude obsahovat abecední

218
00:12:55,580 --> 00:12:58,200
znaky nebo apostrofy.

219
00:12:58,200 --> 00:13:02,490
>> Tak se pojďme podívat na to, jak byste mohli zkontrolovat,
se strukturou hash tabulky.

220
00:13:02,490 --> 00:13:07,330
No, pokud existuje slovo, pak to
jsou uvedeny v tabulce hash.

221
00:13:07,330 --> 00:13:12,240
Takže pak se můžete pokusit zjistit, že
slovo v daném bloku.

222
00:13:12,240 --> 00:13:14,480
>> Tak který kbelík by to slovo bylo v?

223
00:13:14,480 --> 00:13:20,060
No, měli byste dostat číslo, že index
z kbelíku, hešováním toto slovo

224
00:13:20,060 --> 00:13:23,690
a pak vyhledávání v tomto provázaném seznamu,
procházející přes celý

225
00:13:23,690 --> 00:13:28,060
spojový seznam, pomocí String
Porovnání funkci.

226
00:13:28,060 --> 00:13:31,940
>> Pokud konec spojového seznamu je
dosaženo, což znamená, že kurzor

227
00:13:31,940 --> 00:13:36,030
dosáhne null, pak slovo není
lze nalézt ve slovníku.

228
00:13:36,030 --> 00:13:39,090
Nebude to v žádném jiném kbelíku.

229
00:13:39,090 --> 00:13:43,020
Tak tady můžete vidět, jak by mohlo
být kompromis mezi tím, a to buď

230
00:13:43,020 --> 00:13:46,280
seřazeno spojové seznamy nebo ty netříděné.

231
00:13:46,280 --> 00:13:51,180
Buď bude mít více času během
při kontrole zatížení nebo více času.

232
00:13:51,180 --> 00:13:53,560
>> Jak můžete zkontrolovat v
struktura trie?

233
00:13:53,560 --> 00:13:56,370
Budeme se pohybovat směrem dolů
v trie.

234
00:13:56,370 --> 00:14:00,390
Pro každé písmeno v zadaném slově
že budeme kontrolovat, půjdeme na to

235
00:14:00,390 --> 00:14:03,280
odpovídající prvek dětí.

236
00:14:03,280 --> 00:14:07,770
>> Je-li tento prvek je null, pak to znamená,
že neexistují žádné substrings

237
00:14:07,770 --> 00:14:11,110
obsahující naší vstupní slovo, tak
slovo je chybně.

238
00:14:11,110 --> 00:14:15,140
Pokud to není null, můžeme přesunout do
další písmeno slova, které jsme

239
00:14:15,140 --> 00:14:18,850
kontrolu a pokračovat v tomto procesu
až se dostaneme na konec

240
00:14:18,850 --> 00:14:20,350
vstupního slova.

241
00:14:20,350 --> 00:14:23,330
A pak můžeme zkontrolovat
Je-li slovo je pravda.

242
00:14:23,330 --> 00:14:24,610
Pokud ano, pak skvělé.

243
00:14:24,610 --> 00:14:25,590
Slovo je pravda.

244
00:14:25,590 --> 00:14:30,890
Ale i kdyby ne, i přesto, že podřetězec
existuje v trie, slovo je

245
00:14:30,890 --> 00:14:32,250
chybně.

246
00:14:32,250 --> 00:14:36,590
>> Je-li funkce volána velikost, velikost
by měl vrátit počet slov, která

247
00:14:36,590 --> 00:14:39,110
jsou v daném slovníku
datová struktura.

248
00:14:39,110 --> 00:14:42,780
Takže pokud používáte hash tabulky, můžete
Můžete buď projít každý

249
00:14:42,780 --> 00:14:45,860
spojový seznam se každý
kbelík počítání počtu

250
00:14:45,860 --> 00:14:47,130
slov jsou tam.

251
00:14:47,130 --> 00:14:49,940
Pokud používáte trie, můžete
projít všechny non null

252
00:14:49,940 --> 00:14:52,030
Cesta v trie.

253
00:14:52,030 --> 00:14:56,420
Nebo když jste načítání slovníku
v, možná můžete sledovat, jak

254
00:14:56,420 --> 00:14:58,760
mnoho slov jste nahrává palců

255
00:14:58,760 --> 00:15:03,180
>> Jakmile speller.c dokončí kontrolu
textový soubor proti slovníku, pak

256
00:15:03,180 --> 00:15:08,010
to udělat, a tak to volá Uvolnit, kde
Vaším úkolem je osvobodit nic

257
00:15:08,010 --> 00:15:09,500
že jste malloced.

258
00:15:09,500 --> 00:15:14,420
Takže pokud používáte hash tabulku, pak se
musí být obzvláště opatrní, aby se zabránilo

259
00:15:14,420 --> 00:15:18,830
paměťové úniky informací ze strany není uvolnění nic
předčasně a drží na každém

260
00:15:18,830 --> 00:15:20,780
single link Před zdarma.

261
00:15:20,780 --> 00:15:24,680

262
00:15:24,680 --> 00:15:30,100
>> Takže pro každý prvek v tabulce hash
a pro každý uzel v propojeném seznamu

263
00:15:30,100 --> 00:15:32,370
budete chtít osvobodit, aby uzel.

264
00:15:32,370 --> 00:15:34,970
Jak se vám jít o uvolnění
spojový seznam?

265
00:15:34,970 --> 00:15:38,570
Nastavení vašeho uzlu ukazatel myši na
hlavy, na začátku roku

266
00:15:38,570 --> 00:15:43,100
spojový seznam, a pak, když kurzor
není null, můžete nastavit dočasný

267
00:15:43,100 --> 00:15:45,610
uzel ukazatel kurzoru.

268
00:15:45,610 --> 00:15:48,370
Potom posuňte kurzor.

269
00:15:48,370 --> 00:15:52,950
A pak se můžete uvolnit, že dočasný
hodnotu, zatímco stále drží na

270
00:15:52,950 --> 00:15:55,650
vše později.

271
00:15:55,650 --> 00:15:57,800
>> Co když používáte trie?

272
00:15:57,800 --> 00:16:00,410
Pak je nejlepší způsob, jak to udělat
je vyložit z velmi

273
00:16:00,410 --> 00:16:02,290
zdola nahoru.

274
00:16:02,290 --> 00:16:06,920
Tím, že cestuje na nejnižší možné
uzel, můžete uvolnit všechny ukazatele v

275
00:16:06,920 --> 00:16:11,430
že děti a pak s návratem
nahoru, uvolní všechny prvky ve všech

276
00:16:11,430 --> 00:16:15,610
z dětských pole, do
můžete trefit horní kořenový uzel.

277
00:16:15,610 --> 00:16:18,920
Zde je místo, kde Rekurze
přijde vhod.

278
00:16:18,920 --> 00:16:22,780
>> Abyste se ujistili, že jste pravděpodobně uvolněno
vše, co jste malloced,

279
00:16:22,780 --> 00:16:24,400
můžete použít Valgrind.

280
00:16:24,400 --> 00:16:28,640
Spuštění Valgrind poběží program
počítání, kolik bajtů paměti

281
00:16:28,640 --> 00:16:32,440
používáte, a ujistěte se, že jste
osvobodil všechny, říkám

282
00:16:32,440 --> 00:16:34,530
kde byste mohli mít
zapomněli zdarma.

283
00:16:34,530 --> 00:16:38,390
Tak běžte, že i po Valgrind vám řekne,
a dává vám do toho, pak

284
00:16:38,390 --> 00:16:41,160
jste skončil vyložit.

285
00:16:41,160 --> 00:16:44,420
>> Nyní, pár tipů před odjezdem
off a začít provádět svůj

286
00:16:44,420 --> 00:16:46,260
slovník.

287
00:16:46,260 --> 00:16:49,650
Já bych doporučil projít v menší
slovník, když se snažíte testovat

288
00:16:49,650 --> 00:16:52,620
věci a ladění s HDP.

289
00:16:52,620 --> 00:16:58,550
Použití pravopisu je. / Pravopisu,
volitelný slovník, a pak text.

290
00:16:58,550 --> 00:17:01,550
>> Ve výchozím nastavení se nahraje do
velký slovník.

291
00:17:01,550 --> 00:17:06,670
Takže možná budete chtít projít v malých
slovník, nebo dokonce vytvořit svůj

292
00:17:06,670 --> 00:17:11,819
vlastní, přizpůsobení váš slovník
a váš textový soubor.

293
00:17:11,819 --> 00:17:15,950
>> A nakonec bych také doporučit
vzít si tužku a papír a nakreslete

294
00:17:15,950 --> 00:17:20,490
věci před, v průběhu a po
jste napsali všechny vaše kódu.

295
00:17:20,490 --> 00:17:24,170
Jen se ujistěte, že máte
tyto ukazatele akorát.

296
00:17:24,170 --> 00:17:26,480
>> Přeji Vám hodně štěstí.

297
00:17:26,480 --> 00:17:29,690
A jakmile jste hotovi, pokud byste chtěli
napadnout velkou tabuli a

298
00:17:29,690 --> 00:17:34,390
vidět, jak rychle se váš program ve srovnání s
svými spolužáky ", pak doporučuji

299
00:17:34,390 --> 00:17:35,960
zkontrolovat, že ven.

300
00:17:35,960 --> 00:17:39,220
>> Díky, že jsi skončil
pravopisu PSet.

301
00:17:39,220 --> 00:17:41,800
Jmenuji se Zamyla, a to je CS50.

302
00:17:41,800 --> 00:17:49,504