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

2
00:00:09,700 --> 00:00:12,140
>> ZAMYLA CHAN: Naredimo
črkovalnik.

3
00:00:12,140 --> 00:00:16,900
Če odprete speller.c, potem boste videli
da je večina Funkcionalnost

4
00:00:16,900 --> 00:00:20,810
preverjanje besedilno datoteko proti
Slovar je že za vami.

5
00:00:20,810 --> 00:00:26,330
. / Speller, ki poteka v slovarju besedilu
datoteko in nato še besedilna datoteka,

6
00:00:26,330 --> 00:00:28,960
bo preveril, ali besedilno datoteko
proti slovarju.

7
00:00:28,960 --> 00:00:34,160
>> Zdaj bo slovarja besedilne datoteke vsebujejo
veljavnih besede, enega v vsako vrstico.

8
00:00:34,160 --> 00:00:37,910
Potem speller.c bo poklical Load
v slovarju besedilno datoteko.

9
00:00:37,910 --> 00:00:43,650
To bom poklical funkcijo imenovano Preveri
vsaka beseda v vnesenega besedilno datoteko,

10
00:00:43,650 --> 00:00:46,460
tiskanje vseh napačno črkovane besede.

11
00:00:46,460 --> 00:00:50,030
>> Speller.c bo tudi pokličete na velikost
določitev števila besed

12
00:00:50,030 --> 00:00:53,500
slovar in pokličite raztovoriti
da sprostite pomnilnik.

13
00:00:53,500 --> 00:00:57,600
speller.c bodo tudi spremljali, kako
koliko časa se uporablja za izvajanje teh

14
00:00:57,600 --> 00:01:00,560
procesi, vendar bomo
to kasneje.

15
00:01:00,560 --> 00:01:02,440
>> Torej, kaj moramo storiti?

16
00:01:02,440 --> 00:01:05,110
Moramo izpolniti dictionary.c.

17
00:01:05,110 --> 00:01:09,940
V dictionary.c, imamo pomočnika
Funkcija Load, ki naloži

18
00:01:09,940 --> 00:01:10,855
Slovar.

19
00:01:10,855 --> 00:01:15,490
Preverite delovanje, ki preveri, če
dana beseda v slovarju.

20
00:01:15,490 --> 00:01:19,150
Funkcija Velikost vrne število
besed v slovarju.

21
00:01:19,150 --> 00:01:24,870
In končno, smo raztovoriti, ki
osvobodi slovar iz spomina.

22
00:01:24,870 --> 00:01:27,070
>> Torej, najprej, kaj je reševanje breme.

23
00:01:27,070 --> 00:01:32,110
Za vsako besedo v slovarju besedilu
Datoteka bo Load shranite te besede v

24
00:01:32,110 --> 00:01:34,860
slovar struktura podatkov
po vaši izbiri, bodisi

25
00:01:34,860 --> 00:01:36,750
hash tabelo ali Trsta.

26
00:01:36,750 --> 00:01:39,440
Jaz bom šel čez, tako v
ta sprehod skozi.

27
00:01:39,440 --> 00:01:43,150
>> Najprej pogovoriva o hash tabel.

28
00:01:43,150 --> 00:01:47,050
Povejte, da ste imeli 10 biljard krogle in
si želel, da jih shranite.

29
00:01:47,050 --> 00:01:50,420
Vi bi jih lahko dal vse v vedro,
in ko boste potrebovali specifično

30
00:01:50,420 --> 00:01:54,010
oštevilčene žogo, ki ste jo vzeli eno
iz vedra hkrati

31
00:01:54,010 --> 00:01:55,880
je videti, da za žogo.

32
00:01:55,880 --> 00:01:59,370
In s samo 10 žog, bi morali biti
možnost, da bi našli svojo žogico v razumnem

33
00:01:59,370 --> 00:02:01,160
časa.

34
00:02:01,160 --> 00:02:03,180
>> Toda kaj, če si imel 20 jajc?

35
00:02:03,180 --> 00:02:05,480
To lahko traja malo dlje zdaj.

36
00:02:05,480 --> 00:02:06,180
Kaj pa 100?

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

38
00:02:07,880 --> 00:02:11,590
Zdaj, bi bilo veliko lažje, če
boste imeli več vedra.

39
00:02:11,590 --> 00:02:15,890
Mogoče eno vedro žogic za oštevilčene nič
skozi devet, drugi vedro za

40
00:02:15,890 --> 00:02:18,800
kroglice oštevilčene 10 skozi
19, in tako naprej.

41
00:02:18,800 --> 00:02:22,330
>> Zdaj, ko je potrebno poiskati specifične
žoga, bi lahko samodejno

42
00:02:22,330 --> 00:02:26,320
pojdite na eno posebno vedro in
iskanje po tisto vedro.

43
00:02:26,320 --> 00:02:29,840
In če ima vsaka žlica približno 10
žoge, potem lahko enostavno iskanje

44
00:02:29,840 --> 00:02:31,790
skozenj.

45
00:02:31,790 --> 00:02:34,960
>> Zdaj, ker imamo opravka z
slovarji, ena žlica za

46
00:02:34,960 --> 00:02:41,970
vse besede v slovarju bo
Verjetno je veliko premalo vedra.

47
00:02:41,970 --> 00:02:44,370
Tako da je lahko pogled na hash tabel.

48
00:02:44,370 --> 00:02:46,940
>> Think of it kot niz vedrih.

49
00:02:46,940 --> 00:02:50,370
In v tem primeru, vedra
so naši povezani seznam.

50
00:02:50,370 --> 00:02:54,770
In bomo razdelili vseh naših besed
med temi več povezanih sezname

51
00:02:54,770 --> 00:02:58,940
organiziran način s funkcijo razpršitve,
ki nam bo povedal,

52
00:02:58,940 --> 00:03:03,720
vedro določen ključ, saj
beseda pripada.

53
00:03:03,720 --> 00:03:05,960
>> Oglejmo predstavljajo to shematično.

54
00:03:05,960 --> 00:03:11,320
Modre škatle tu vsebuje vrednosti in
rdeče škatle na drugo točko vrednosti

55
00:03:11,320 --> 00:03:12,280
kazalec par.

56
00:03:12,280 --> 00:03:14,800
Poklicali bomo teh parov vozlišč.

57
00:03:14,800 --> 00:03:18,260
Zdaj, vsak vedro, kot sem rekel,
prej, je povezani seznam.

58
00:03:18,260 --> 00:03:21,820
V povezanih seznamov, vsako vozlišče ima svojo vrednost,
kot tudi kazalec

59
00:03:21,820 --> 00:03:23,170
Naslednji vrednost.

60
00:03:23,170 --> 00:03:26,150
>> Zdaj, ki se ukvarjajo s povezanimi sezname
to je zelo pomembno, da

61
00:03:26,150 --> 00:03:28,120
ne izgubijo nobenih povezav.

62
00:03:28,120 --> 00:03:32,250
In še dejstvo, da se spomnimo, da
zadnje vozlišče, če ne kažejo na

63
00:03:32,250 --> 00:03:35,120
drugo vozlišče, kaže na null.

64
00:03:35,120 --> 00:03:37,970
>> Torej, kako bomo to predstavljajo v C?

65
00:03:37,970 --> 00:03:40,540
Definiramo našo zgradimo tukaj.

66
00:03:40,540 --> 00:03:44,850
In vrednost je v tem primeru
char array dolžine.

67
00:03:44,850 --> 00:03:48,880
Dolžina plus 1, kjer je dolžina
Največja dolžina katerokoli besedo, plus 1 za

68
00:03:48,880 --> 00:03:50,380
null terminator.

69
00:03:50,380 --> 00:03:54,210
In potem imamo kazalec
drugo vozlišče se imenuje Naprej.

70
00:03:54,210 --> 00:03:56,730
>> Torej, dajmo narediti majhen povezani seznam.

71
00:03:56,730 --> 00:04:00,390
Najprej boste želeli malloc svoje vozlišče,
ki ustvarjajo prostor v pomnilniku

72
00:04:00,390 --> 00:04:04,010
velikost vašega tipa vozlišča.

73
00:04:04,010 --> 00:04:06,100
In da drugo vozlišče,
spet mallocing.

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

75
00:04:09,370 --> 00:04:14,340
>> Zdaj, če želite dodeliti vrednost
beseda, potem bi lahko rekli, node1 puščico

76
00:04:14,340 --> 00:04:18,820
Beseda je enako "Hello". Ta puščica operater
dereferences kazalec in

77
00:04:18,820 --> 00:04:20,620
dostopi spremenljivke struct je.

78
00:04:20,620 --> 00:04:24,330
Na ta način ne bomo morali uporabiti oboje
dot in operater zvezda.

79
00:04:24,330 --> 00:04:30,100
>> Torej imam Node2 arrow beseda je enaka
»Svet«. In tam, da so vrednosti

80
00:04:30,100 --> 00:04:33,110
poseljena v mojih vozlišč.

81
00:04:33,110 --> 00:04:38,780
Če želite, da povezave, bom mimo v node1
puščico, dostop do vozlišča zvezdo,

82
00:04:38,780 --> 00:04:44,160
da vozlišče kazalec, enaka Node2,
kaže node1 za Node2 dva.

83
00:04:44,160 --> 00:04:46,360
In tam imamo povezan seznam.

84
00:04:46,360 --> 00:04:51,480
>> Tako da je bila le ena povezani seznam, vendar
hash tabela je cela paleta

85
00:04:51,480 --> 00:04:52,520
povezani seznam.

86
00:04:52,520 --> 00:04:55,920
No, bomo imeli enako vozlišče
strukturirati kot prej.

87
00:04:55,920 --> 00:05:00,140
Ampak, če bi želeli dejansko razpršene tabele,
potem bomo lahko le, da vozlišča kazalec

88
00:05:00,140 --> 00:05:01,330
matrika tukaj.

89
00:05:01,330 --> 00:05:04,940
Na primer, velikost 500.

90
00:05:04,940 --> 00:05:08,910
>> Zdaj obvestilo, da se bo trgovanje
off med velikostjo vašega

91
00:05:08,910 --> 00:05:11,280
hash table in velikost
vaših povezanih seznamov.

92
00:05:11,280 --> 00:05:15,640
Če imate res veliko število
vedra, si predstavlja, da bi morali teči nazaj

93
00:05:15,640 --> 00:05:18,230
in tja v skladu z
našli vedro.

94
00:05:18,230 --> 00:05:21,530
Ampak tudi vi ne želite majhno število
žlic, ker potem smo nazaj

95
00:05:21,530 --> 00:05:26,850
prvotna problem, kako ob
Preveč žog v naši vedro.

96
00:05:26,850 --> 00:05:30,480
>> OK, ampak kje pa je naša žoga šla?

97
00:05:30,480 --> 00:05:33,150
No, moramo najprej
imajo žogo, kajne?

98
00:05:33,150 --> 00:05:39,130
Torej, kaj je malloc vozlišče za vsako
Nova beseda, ki jo imamo.

99
00:05:39,130 --> 00:05:42,900
vozlišče * new_node Rezult
malloc (sizeof (vozlišče)).

100
00:05:42,900 --> 00:05:46,760
>> Sedaj, ko imamo to strukturo, smo
Lahko skeniranje, s funkcijo

101
00:05:46,760 --> 00:05:51,850
fscanf, niz iz naše dokumentacije, če
to je slovar datoteka, v

102
00:05:51,850 --> 00:05:55,780
new_node arrow beseda, kjer new_node
arrow beseda je naša

103
00:05:55,780 --> 00:05:58,110
cilj te besede.

104
00:05:58,110 --> 00:06:01,900
>> Naprej bomo želeli, da hash
Beseda uporabo funkcijo razpršitve.

105
00:06:01,900 --> 00:06:05,860
Hash funkcijo prevzame niz
in vrne indeks.

106
00:06:05,860 --> 00:06:09,760
V tem primeru je indeks mora
manj od števila

107
00:06:09,760 --> 00:06:11,440
žlice, ki jih imate.

108
00:06:11,440 --> 00:06:14,600
>> Zdaj, zgoščevalne funkcije, ko poskušate
da bi našli enega, in ustvarili enega

109
00:06:14,600 --> 00:06:17,890
svoje, ne pozabite, da so
biti deterministična.

110
00:06:17,890 --> 00:06:22,420
To pomeni, da ista vrednost mora
preslika v žlico vsakič

111
00:06:22,420 --> 00:06:23,800
da jo hash.

112
00:06:23,800 --> 00:06:25,300
>> To je nekako tako kot v knjižnici.

113
00:06:25,300 --> 00:06:28,560
Ko boste vzeli knjigo, ki temelji na
avtor, veste, kateri polici bi morala

114
00:06:28,560 --> 00:06:31,890
pojdi na to, ali je to število polica
en, dva ali tri.

115
00:06:31,890 --> 00:06:36,280
In da bo knjiga vedno spadajo na
bodisi polica enega, dva ali tri.

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

117
00:06:39,460 --> 00:06:43,810
>> Torej, če new_node arrow ima beseda
Beseda iz svojega slovarja, potem

118
00:06:43,810 --> 00:06:47,770
hašiš new_node arrow Beseda bo
nam dajejo indeks

119
00:06:47,770 --> 00:06:49,370
vedro razpršene tabele.

120
00:06:49,370 --> 00:06:54,040
In potem bomo vstaviti, da v to
specifično povezani seznam z navedeno

121
00:06:54,040 --> 00:06:56,060
vrne vrednost našega hash funkcijo.

122
00:06:56,060 --> 00:06:59,070
>> Oglejmo si primer
vstavimo vozlišče v

123
00:06:59,070 --> 00:07:01,750
začetek povezanega seznama.

124
00:07:01,750 --> 00:07:06,930
Če glava je kazalec vozlišče, ki označuje
začetek povezan

125
00:07:06,930 --> 00:07:12,420
Seznam in new_node označuje novo
vozlišče, ki ga želite vnesti v, samo

126
00:07:12,420 --> 00:07:17,340
dodeljevanje glavo new_node bi izgubili
Povezava na preostanek seznama.

127
00:07:17,340 --> 00:07:19,330
Tako da ne želimo, da to storijo.

128
00:07:19,330 --> 00:07:22,160
>> Namesto tega želimo zagotoviti
da imamo na vsaki

129
00:07:22,160 --> 00:07:23,550
single vozlišče v našem programu.

130
00:07:23,550 --> 00:07:29,560
Torej teče new_node puščico Rezult
glava in nato vodja enaka new_node

131
00:07:29,560 --> 00:07:34,470
bodo ohranili vse
povezave in ne izgubijo.

132
00:07:34,470 --> 00:07:39,330
>> Toda kaj, če želite, da vaš seznam, ki bo
razporejene, ker ima razporejene povezan

133
00:07:39,330 --> 00:07:42,910
Seznam bi bilo lažje za
ga iščejo kasneje?

134
00:07:42,910 --> 00:07:46,020
No, za to, boste morali vedeti,
kako za prečkanje povezanih seznamov.

135
00:07:46,020 --> 00:07:51,210
>> Prečkanje povezan seznam, imejmo
kazalec vozlišče, vozlišče *, da deluje kot

136
00:07:51,210 --> 00:07:54,120
kazalec, ki označuje ki
vozlišče ste na, začenši

137
00:07:54,120 --> 00:07:55,460
na prvem elementu.

138
00:07:55,460 --> 00:08:01,070
Zanka, dokler kazalec je nična, ne moremo
izvajati določene procese in nato

139
00:08:01,070 --> 00:08:04,330
napredovanje kazalec, ko moramo
S pomočjo smernih arrow vrednost.

140
00:08:04,330 --> 00:08:08,820
>> Ne pozabite, da je to ista stvar kot
rekoč zvezda kazalec, Dereferenciranje

141
00:08:08,820 --> 00:08:13,480
kurzor, nato pa z uporabo
dot vrednost operater.

142
00:08:13,480 --> 00:08:19,000
Torej posodobitev kazalec se z dodelitvijo
kazalec na kazalec puščico.

143
00:08:19,000 --> 00:08:24,960
>> Povejte, da ste ugotovili, da je D postane v
med C in E. Če želite vstaviti vozlišče,

144
00:08:24,960 --> 00:08:30,030
imajo new_node D pokažite
vozlišče E, ki je kazalec dostavo.

145
00:08:30,030 --> 00:08:36,409
In potem C, kazalec, lahko pokažite
do D. Na ta način vzdržuje seznam.

146
00:08:36,409 --> 00:08:41,080
Bodite previdni, da ne bi izgubili svoje povezave, ki jih
premikanje kurzorja puščico D

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

148
00:08:43,929 --> 00:08:44,620
>> Vse je v redu.

149
00:08:44,620 --> 00:08:48,920
Torej, to je, kako si lahko vstavite vozlišč,
jih naložite, nalaganje besed na tiste,

150
00:08:48,920 --> 00:08:51,600
vozlišč, in jih vstavite
v vašem razpršene tabele.

151
00:08:51,600 --> 00:08:53,580
Sedaj si oglejmo poskusih.

152
00:08:53,580 --> 00:08:58,540
>> V Trsta, bo vsako vozlišče vsebuje
matrika vozlišč kazalcev, enega za vsak

153
00:08:58,540 --> 00:09:02,260
črka v abecedi
plus opuščaj.

154
00:09:02,260 --> 00:09:06,150
In vsak element v matriki
bo opozorila na drugo vozlišče.

155
00:09:06,150 --> 00:09:10,130
Če je to vozlišče je nična, potem to pismo
se ne bo naslednja črka

156
00:09:10,130 --> 00:09:15,690
vsaka beseda v zaporedju, ker vsak
Beseda označuje, ali je to zadnji

157
00:09:15,690 --> 00:09:18,160
značaj besedo ali ne.

158
00:09:18,160 --> 00:09:19,750
>> Oglejmo shemo.

159
00:09:19,750 --> 00:09:22,260
Upajmo, da se bodo stvari
biti malo bolj jasno.

160
00:09:22,260 --> 00:09:27,210
V tem diagramu vidimo, da le
nekatere črke in nekatere podrejene

161
00:09:27,210 --> 00:09:28,190
se navedeni ven.

162
00:09:28,190 --> 00:09:32,500
Tako da lahko sledijo določenim poti, in
vse te poti vas bo vodil do

163
00:09:32,500 --> 00:09:34,020
različne besede.

164
00:09:34,020 --> 00:09:37,630
>> Torej, kako bomo to predstavljajo v C?

165
00:09:37,630 --> 00:09:41,910
No, vsako vozlišče sedaj se dogaja, da imajo
Logična vrednost, ki pove, ali

166
00:09:41,910 --> 00:09:46,580
da vozlišče konec
dana beseda ali ne.

167
00:09:46,580 --> 00:09:50,690
In potem bomo imeli tudi niz
vozlišče kazalci se imenujejo otroci in

168
00:09:50,690 --> 00:09:53,440
tam se bo 27 od njih.

169
00:09:53,440 --> 00:09:56,510
In ne pozabite, da boste prav tako želeli
slediti vaš prvi vozlišče.

170
00:09:56,510 --> 00:09:59,830
Gremo na klic, da korenine.

171
00:09:59,830 --> 00:10:01,690
>> Tako da je struktura Trsta.

172
00:10:01,690 --> 00:10:05,630
Kako bomo to predstavljajo
kot slovar?

173
00:10:05,630 --> 00:10:09,890
No, preračunavanja besede v, za vsak
slovar besedo, boste želeli

174
00:10:09,890 --> 00:10:11,960
za ponovitev prek Trsta.

175
00:10:11,960 --> 00:10:16,170
In vsak element pri otrocih
ustreza drugačen pisma.

176
00:10:16,170 --> 00:10:21,660
>> Torej, da preverja vrednost pri otrocih
indeks i, kjer je i predstavlja

177
00:10:21,660 --> 00:10:24,840
specifični indeks pismu, ki
poskušate vstaviti.

178
00:10:24,840 --> 00:10:28,980
No, če je nična, potem boste želeli, da
malloc novo vozlišče in imeti otroke

179
00:10:28,980 --> 00:10:31,110
i kažejo na to vozlišče.

180
00:10:31,110 --> 00:10:35,630
>> Če ni nič, potem to pomeni, da
da glede na podružnico, da je glede

181
00:10:35,630 --> 00:10:37,350
podniz, že obstaja.

182
00:10:37,350 --> 00:10:40,160
Torej boste le, da se premaknete na
novo vozlišče in naprej.

183
00:10:40,160 --> 00:10:43,220
Če ste na koncu besede, ki
skušate naložiti v

184
00:10:43,220 --> 00:10:48,120
slovar, potem lahko nastavite, da
Sedanji vozlišče, da ste na true.

185
00:10:48,120 --> 00:10:51,550
>> Zato si oglejmo primer vstavljanja
Beseda "lisica" v našem

186
00:10:51,550 --> 00:10:53,070
Slovar.

187
00:10:53,070 --> 00:10:56,110
Pretvarjaj se, da začnemo z
prazen slovar.

188
00:10:56,110 --> 00:11:01,610
Prva črka F, ki se nahajata
V indeksu otrok pet od korenin

189
00:11:01,610 --> 00:11:03,700
otroci matrika.

190
00:11:03,700 --> 00:11:05,430
Tako smo, da vstavite noter

191
00:11:05,430 --> 00:11:14,610
>> Črka O bo nato pri otrocih
indeks 15, po tem F. In potem X

192
00:11:14,610 --> 00:11:20,180
bo še nižja, razvejane
off otrok na Ö je.

193
00:11:20,180 --> 00:11:24,120
In zato, ker potem X je zadnja črka
besede "lisice", potem bom

194
00:11:24,120 --> 00:11:27,210
zeleno barvo, ki kaže, da
to je konec besedi.

195
00:11:27,210 --> 00:11:32,880
V C, da bo nastavitev je
Beseda boolean vrednosti prave.

196
00:11:32,880 --> 00:11:36,780
>> Zdaj, kaj če Naslednja beseda, ki ste
vložite v je beseda "foo"?

197
00:11:36,780 --> 00:11:41,490
No, vam ni treba malloc več
Prostor za F ali O, saj

198
00:11:41,490 --> 00:11:42,990
tistih, ki že obstajajo.

199
00:11:42,990 --> 00:11:45,910
Toda zadnja O v foo?

200
00:11:45,910 --> 00:11:47,320
Tista, boste morali malloc.

201
00:11:47,320 --> 00:11:52,390
Naredite novo vozlišče za to, v katerem
Word Boolean, da res.

202
00:11:52,390 --> 00:11:57,340
>> Torej, zdaj pa doda "psa." Pes bo
začeti z indeksom treh korenin

203
00:11:57,340 --> 00:12:00,520
otroci, ker je D ne
še ni bila ustvarjena.

204
00:12:00,520 --> 00:12:04,990
In bomo sledili podoben proces kot
pred oblikovanjem podniz psa,

205
00:12:04,990 --> 00:12:10,400
kjer je G zelene barve, saj
to je konec besedi.

206
00:12:10,400 --> 00:12:13,160
>> Zdaj, kaj, če želimo vstaviti "ne"?

207
00:12:13,160 --> 00:12:17,150
No, to je podniz psa, tako da
nam ni treba več malloc.

208
00:12:17,150 --> 00:12:20,800
Vendar pa je treba navesti, kje smo že
dosegel konec te besede.

209
00:12:20,800 --> 00:12:24,020
Torej bo O zelene barve.

210
00:12:24,020 --> 00:12:27,810
Nadaljevanje tega procesa za vsak
beseda v vašem slovarju, ki ste jih

211
00:12:27,810 --> 00:12:32,120
jih v naloženi v obeh vašem
hash tabelo ali vaše Trsta.

212
00:12:32,120 --> 00:12:37,530
>> speller.c bo minilo v kito za
dictionary.c za njihovo preverjanje.

213
00:12:37,530 --> 00:12:41,140
Zdaj Preverite delovanje mora delovati
v skladu s sodno neobčutljivosti.

214
00:12:41,140 --> 00:12:45,980
To pomeni, da tiskane črke in
male črke in mešanica obojega

215
00:12:45,980 --> 00:12:50,670
bi morali vsi enačijo true če sploh
kombinacija, ki je v

216
00:12:50,670 --> 00:12:51,880
Slovar.

217
00:12:51,880 --> 00:12:55,580
Prav tako lahko sklepamo, da so strune
samo še vsebuje abecedni

218
00:12:55,580 --> 00:12:58,200
znakov ali opuščaj.

219
00:12:58,200 --> 00:13:02,490
>> Zato si oglejmo, kako lahko preverite,
s strukturo hash tabele.

220
00:13:02,490 --> 00:13:07,330
Torej, če obstaja beseda, potem
je mogoče najti v razpršene tabele.

221
00:13:07,330 --> 00:13:12,240
Torej, potem lahko poskusite najti, da
beseda v ustreznem vedru.

222
00:13:12,240 --> 00:13:14,480
>> Torej, ki bucket bi ta beseda v?

223
00:13:14,480 --> 00:13:20,060
No, boš dobil številko, da indeks
vedra, s hašiš to besedo

224
00:13:20,060 --> 00:13:23,690
in nato iskati v tem povezan seznam,
prehaja skozi celoten

225
00:13:23,690 --> 00:13:28,060
povezani seznam, s pomočjo String
Funkcijo primerjavo.

226
00:13:28,060 --> 00:13:31,940
>> Če konec povezani seznam je
dosegel, kar pomeni, da je vaš kazalec

227
00:13:31,940 --> 00:13:36,030
doseže nič, potem beseda ni
lahko najdemo v slovarju.

228
00:13:36,030 --> 00:13:39,090
To ne bo v katerikoli drugi vedru.

229
00:13:39,090 --> 00:13:43,020
Torej tu lahko vidite, kako bi lahko obstajal
je kompromis med tem, ali

230
00:13:43,020 --> 00:13:46,280
razvrščena povezani seznami ali nesortirane tisti.

231
00:13:46,280 --> 00:13:51,180
Bodisi bo potrebno več časa med
naložiti ali več časa med preverjanjem.

232
00:13:51,180 --> 00:13:53,560
>> Kako bi lahko prijavijo
Trie struktura?

233
00:13:53,560 --> 00:13:56,370
Gremo navzdol potovati
v Trsta.

234
00:13:56,370 --> 00:14:00,390
Za vsako črko v besedi vnesenega
da smo kontrolo, bomo šli na to

235
00:14:00,390 --> 00:14:03,280
ustreza element pri otrocih.

236
00:14:03,280 --> 00:14:07,770
>> Če ta element je nična, potem to pomeni,
da ni nukleotidov

237
00:14:07,770 --> 00:14:11,110
vsebuje našo vhodno besedo, tako da
beseda napačno črkovana.

238
00:14:11,110 --> 00:14:15,140
Če to ni nič, lahko gremo na
naslednja črka besede, da smo

239
00:14:15,140 --> 00:14:18,850
preverjanje in nadaljevati ta proces
dokler ne pridete do konca

240
00:14:18,850 --> 00:14:20,350
vhodne besede.

241
00:14:20,350 --> 00:14:23,330
In potem bomo lahko preverite
Če je Beseda je res.

242
00:14:23,330 --> 00:14:24,610
Če je, potem super.

243
00:14:24,610 --> 00:14:25,590
Beseda je pravilno.

244
00:14:25,590 --> 00:14:30,890
Če pa ne, čeprav se ta podniz
obstaja v Trsta, beseda

245
00:14:30,890 --> 00:14:32,250
napačno.

246
00:14:32,250 --> 00:14:36,590
>> Ko je funkcija Velikost imenuje, velikost
mora vrniti število besed, ki

247
00:14:36,590 --> 00:14:39,110
so v danem slovar
struktura podatkov.

248
00:14:39,110 --> 00:14:42,780
Torej, če ste z uporabo hash tabelo,
lahko bodisi iti skozi vsak

249
00:14:42,780 --> 00:14:45,860
povezani seznam v vsak
bucket štetjem

250
00:14:45,860 --> 00:14:47,130
besed so tam.

251
00:14:47,130 --> 00:14:49,940
Če boste uporabljali Trsta, lahko
iti skozi vse prepovedi null

252
00:14:49,940 --> 00:14:52,030
Pot v vašem Trsta.

253
00:14:52,030 --> 00:14:56,420
Ali pa, ko ste nalaganju slovar
leta, morda lahko spremljate, kako

254
00:14:56,420 --> 00:14:58,760
veliko besed ste loading prijavite

255
00:14:58,760 --> 00:15:03,180
>> Ko speller.c konča preverjanje
besedilna datoteka, proti slovarju, potem

256
00:15:03,180 --> 00:15:08,010
to je storil, in zato poziva, razkladanje, kjer
vaša naloga je, da osvobodi vse

257
00:15:08,010 --> 00:15:09,500
da ste malloced.

258
00:15:09,500 --> 00:15:14,420
Torej, če uporabljate razpršene tabele, nato pa
morajo biti še posebej previdni, da se prepreči

259
00:15:14,420 --> 00:15:18,830
pomnilniške uhajanje ne osvoboditev ničesar
prezgodaj in držite vsak

260
00:15:18,830 --> 00:15:20,780
enojna vez, preden brezplačno.

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

262
00:15:24,680 --> 00:15:30,100
>> Torej za vsak element v razpršene tabele
in za vsako vozlišče v povezanem seznamu,

263
00:15:30,100 --> 00:15:32,370
boste želeli sprostiti, da vozlišče.

264
00:15:32,370 --> 00:15:34,970
Kako greste o sproščanju
povezani seznam?

265
00:15:34,970 --> 00:15:38,570
Nastavitev vozlišča kazalec kazalec
glava, do začetka

266
00:15:38,570 --> 00:15:43,100
povezani seznam, potem ko je vaš kazalec
ni nič, lahko nastavite začasno

267
00:15:43,100 --> 00:15:45,610
vozlišče kazalec kazalca.

268
00:15:45,610 --> 00:15:48,370
Potem vnaprej kazalec.

269
00:15:48,370 --> 00:15:52,950
In potem se lahko sprostite, da se začasna
vrednost, medtem ko še vedno držite na

270
00:15:52,950 --> 00:15:55,650
vse kasneje.

271
00:15:55,650 --> 00:15:57,800
>> Kaj pa, če boste uporabljali Trsta?

272
00:15:57,800 --> 00:16:00,410
Potem je najboljši način za to
je za raztovarjanje iz zelo

273
00:16:00,410 --> 00:16:02,290
spodaj navzgor.

274
00:16:02,290 --> 00:16:06,920
S potovanjem na najnižjo možno
vozlišče, lahko osvobodi vse napotke v

275
00:16:06,920 --> 00:16:11,430
da otroci in nato Vrniti
navzgor, sprostitev vse elemente v vseh

276
00:16:11,430 --> 00:16:15,610
otrok nizi, dokler
si se udaril v top korenskega vozlišča.

277
00:16:15,610 --> 00:16:18,920
Tu Rekurzija
bo prišel prav.

278
00:16:18,920 --> 00:16:22,780
>> Se prepričajte, da ste verjetno osvobodil
vse, kar ste malloced,

279
00:16:22,780 --> 00:16:24,400
lahko uporabite Valgrind.

280
00:16:24,400 --> 00:16:28,640
Tek Valgrind bo potekal svoj program
Računam, koliko bajtov pomnilnika

281
00:16:28,640 --> 00:16:32,440
ki ga uporabljate, in pazite, da ste
Vse jih osvobodil, ti

282
00:16:32,440 --> 00:16:34,530
, kjer boste morda morali
pozabili brezplačno.

283
00:16:34,530 --> 00:16:38,390
Tako, da teče in ko Valgrind vam pove
in vam gredo naprej, nato pa

284
00:16:38,390 --> 00:16:41,160
ste končali razkladanje.

285
00:16:41,160 --> 00:16:44,420
>> Zdaj, nekaj nasvetov, preden greste
off in začeti izvajati svoj

286
00:16:44,420 --> 00:16:46,260
Slovar.

287
00:16:46,260 --> 00:16:49,650
Želel priporočamo, da prenese v manjši
slovar, ko ste poskušali preizkusiti

288
00:16:49,650 --> 00:16:52,620
stvari in razhroščevanje z BDP.

289
00:16:52,620 --> 00:16:58,550
Uporaba speller je. / Speller,
neobvezno slovar, nato pa besedilo.

290
00:16:58,550 --> 00:17:01,550
>> Privzeto je, da se naloži v
Velik slovar.

291
00:17:01,550 --> 00:17:06,670
Tako da boste morda želeli, da prenese v majhno
slovar, ali morda celo vaše

292
00:17:06,670 --> 00:17:11,819
lastno, prilagajanje vaše slovar
in vaše besedilne datoteke.

293
00:17:11,819 --> 00:17:15,950
>> In potem končno, Jaz bi tudi priporočamo
vzeti svinčnik in papir in sestaviti

294
00:17:15,950 --> 00:17:20,490
Stvari pred, med in po
Saj si napisal vse svoje kode.

295
00:17:20,490 --> 00:17:24,170
Samo poskrbite, da ste dobili
ti kazalci ravno prav.

296
00:17:24,170 --> 00:17:26,480
>> Želim vam veliko sreče.

297
00:17:26,480 --> 00:17:29,690
In ko ste končali, če želite
za izpodbijanje veliko desko in

298
00:17:29,690 --> 00:17:34,390
videli, kako hitro se vaš program v primerjavi s
sošolci, nato pa spodbujam

299
00:17:34,390 --> 00:17:35,960
vam, da preverite to.

300
00:17:35,960 --> 00:17:39,220
>> S tem, ko ste končali
speller PSet.

301
00:17:39,220 --> 00:17:41,800
Ime je Zamyla, in to je CS50.

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