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

2
00:00:09,700 --> 00:00:12,140
>> ZAMYLA Chan: Tehdään
oikeinkirjoituksen tarkistus.

3
00:00:12,140 --> 00:00:16,900
Jos avaat speller.c, niin näet
että useimmat toiminnot

4
00:00:16,900 --> 00:00:20,810
tarkkailun tekstitiedosto vastaan
sanakirja on jo tehty sinulle.

5
00:00:20,810 --> 00:00:26,330
. / Speller, ohimennen sanakirjassa teksti
tiedoston ja sitten toinen tekstitiedosto,

6
00:00:26,330 --> 00:00:28,960
tarkistaa, että tekstitiedoston
vastaan ​​sanakirja.

7
00:00:28,960 --> 00:00:34,160
>> Nyt, sanakirja tekstitiedostoja sisältää
voimassa sanaa, yksi kullekin riville.

8
00:00:34,160 --> 00:00:37,910
Sitten speller.c soittaa Load
on sanakirja tekstitiedosto.

9
00:00:37,910 --> 00:00:43,650
Se soitan toiminto nimeltään tarkastaminen
jokainen sana syötetyn tekstitiedosto,

10
00:00:43,650 --> 00:00:46,460
tulostaa kaikki väärin kirjoitetut sanat.

11
00:00:46,460 --> 00:00:50,030
>> Speller.c myös soittaa koko-
määrittää sanojen määrä

12
00:00:50,030 --> 00:00:53,500
sanakirja ja soita Unload
vapauttaa muistia.

13
00:00:53,500 --> 00:00:57,600
speller.c myös seurata, kuinka
paljon aikaa avulla tehdään näiden

14
00:00:57,600 --> 00:01:00,560
prosesseja, mutta me
päästä siihen myöhemmin.

15
00:01:00,560 --> 00:01:02,440
>> Joten mitä meidän pitää tehdä?

16
00:01:02,440 --> 00:01:05,110
Meidän täytyy täyttää dictionary.c.

17
00:01:05,110 --> 00:01:09,940
Vuonna dictionary.c, meillä on auttaja
toiminto Load, joka lataa

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

19
00:01:10,855 --> 00:01:15,490
Toimintojen tarkistus, joka tarkistaa, jos
tiettyä sanaa on sanakirjassa.

20
00:01:15,490 --> 00:01:19,150
Funktio Koko palauttaa luvun
sanoja sanakirjasta.

21
00:01:19,150 --> 00:01:24,870
Ja lopuksi, olemme Pura, joka
vapauttaa sanakirja muistista.

22
00:01:24,870 --> 00:01:27,070
>> Joten ensin on puuttua Load.

23
00:01:27,070 --> 00:01:32,110
Jokaisen sanan sanakirjasta tekstissä
tiedosto, Load tallentaa näitä sanoja

24
00:01:32,110 --> 00:01:34,860
sanakirjassa tietorakenne
valitsemaltasi joko

25
00:01:34,860 --> 00:01:36,750
hash taulukon tai triellä.

26
00:01:36,750 --> 00:01:39,440
Menen aikana sekä
Tämän kulkea.

27
00:01:39,440 --> 00:01:43,150
>> Katsotaanpa ensin puhua hash taulukoita.

28
00:01:43,150 --> 00:01:47,050
Sano sinä olisit säästänyt 10 biljardi pallot ja
halusit tallentaa ne.

29
00:01:47,050 --> 00:01:50,420
Saatat laittaa ne kaikki ämpäri,
ja kun tarvitaan tietyn

30
00:01:50,420 --> 00:01:54,010
numeroitu pallo, ottaisit yhden
ulos ämpäri kerrallaan

31
00:01:54,010 --> 00:01:55,880
etsivät että pallo.

32
00:01:55,880 --> 00:01:59,370
Ja vain 10 palloa, sinun pitäisi olla
pystyä löytämään pallo kohtuullisen

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

34
00:02:01,160 --> 00:02:03,180
>> Mutta mitä jos sinulla olisi 20 pallot?

35
00:02:03,180 --> 00:02:05,480
Se saattaa kestää hieman kauemmin nyt.

36
00:02:05,480 --> 00:02:06,180
Entä 100?

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

38
00:02:07,880 --> 00:02:11,590
Nyt, se olisi paljon helpompaa, jos
sinulla oli useita kauhat.

39
00:02:11,590 --> 00:02:15,890
Ehkä yksi ämpäri palloja numeroitu nolla
yhdeksään, toinen kauha

40
00:02:15,890 --> 00:02:18,800
numeroitua palloa 10 kautta
19, ja niin edelleen.

41
00:02:18,800 --> 00:02:22,330
>> Nyt kun sinun piti etsiä tiettyjä
pallo, voisit automaattisesti

42
00:02:22,330 --> 00:02:26,320
mene johonkin tiettyyn ämpäri ja
etsiä että ämpäri.

43
00:02:26,320 --> 00:02:29,840
Ja jos jokainen ämpäri on noin 10
pallot, niin voit helposti etsiä

44
00:02:29,840 --> 00:02:31,790
läpi.

45
00:02:31,790 --> 00:02:34,960
>> Nyt, koska olemme tekemisissä
sanakirjoja, yhden kauhan

46
00:02:34,960 --> 00:02:41,970
kaikki sanat sanakirja
todennäköisesti aivan liian vähän kauhat.

47
00:02:41,970 --> 00:02:44,370
Joten katsotaanpa katsomaan hash taulukoita.

48
00:02:44,370 --> 00:02:46,940
>> Ajattele sitä erilaisia ​​kauhoja.

49
00:02:46,940 --> 00:02:50,370
Ja tässä tapauksessa, kauhat
ovat meidän linkitettyjä listoja.

50
00:02:50,370 --> 00:02:54,770
Ja jaamme kaikki sanamme
näiden joukossa useita linkitettyjä luettelot

51
00:02:54,770 --> 00:02:58,940
järjestäytyneesti käyttäen tiivistefunktiota,
joka kertoo meille, mitkä

52
00:02:58,940 --> 00:03:03,720
ämpäri tietyn avaimen, tietyn
sana, kuuluu.

53
00:03:03,720 --> 00:03:05,960
>> Katsotaanpa edustamaan tätä kaavamaisesti.

54
00:03:05,960 --> 00:03:11,320
Siniset laatikot tässä on arvoja, ja
punainen laatikot paikasta toiseen arvoon

55
00:03:11,320 --> 00:03:12,280
osoitin pari.

56
00:03:12,280 --> 00:03:14,800
Me kutsumme näitä paria solmuja.

57
00:03:14,800 --> 00:03:18,260
Nyt jokainen ämpäri, kuten sanoin
aikaisemmin, on linkitetty lista.

58
00:03:18,260 --> 00:03:21,820
Vuonna linkitettyjä listoja, jokainen solmu on arvo,
sekä osoitin

59
00:03:21,820 --> 00:03:23,170
seuraavan arvon.

60
00:03:23,170 --> 00:03:26,150
>> Nyt tekemisissä liittyvät luettelot,
se on erittäin tärkeää, että

61
00:03:26,150 --> 00:03:28,120
älä hävitä linkkejä.

62
00:03:28,120 --> 00:03:32,250
Ja toinen tosiasia on muistaa, että
viime solmu, jos se ei osoita

63
00:03:32,250 --> 00:03:35,120
toisen solmun, viittaa null.

64
00:03:35,120 --> 00:03:37,970
>> Miten siis edustamaan tätä C?

65
00:03:37,970 --> 00:03:40,540
Määrittelemme struct täällä.

66
00:03:40,540 --> 00:03:44,850
Ja arvo on tässä tapauksessa
char array pituuden.

67
00:03:44,850 --> 00:03:48,880
Pituus plus 1, jossa pituus on
Pisin tahansa sana, plus 1

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

69
00:03:50,380 --> 00:03:54,210
Ja sitten meillä on osoitin
toisen solmun nimeltä Next.

70
00:03:54,210 --> 00:03:56,730
>> Joten tehdä pienen linkitetty lista.

71
00:03:56,730 --> 00:04:00,390
Ensinnäkin, sinun kannattaa malloc teidän solmuun,
jotka luovat tilaa muistissa

72
00:04:00,390 --> 00:04:04,010
kokoa solmun tyyppiä.

73
00:04:04,010 --> 00:04:06,100
Ja tee uusi solmu,
jälleen mallocing.

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

75
00:04:09,370 --> 00:04:14,340
>> Nyt jos haluat antaa arvoa
sana, niin voisimme sanoa node1 arrow

76
00:04:14,340 --> 00:04:18,820
sana vastaa "Hei." Tämä nuoli operaattori
dereferences osoitin ja

77
00:04:18,820 --> 00:04:20,620
sisäänkäyntien struct: n muuttujia.

78
00:04:20,620 --> 00:04:24,330
Näin meidän ei tarvitse käyttää molempia
dot ja tähti operaattori.

79
00:04:24,330 --> 00:04:30,100
>> Niin sitten minulla on node2 nuoli sana vastaa
"Maailmassa." Ja siellä, arvot ovat

80
00:04:30,100 --> 00:04:33,110
asutuilla minun solmut.

81
00:04:33,110 --> 00:04:38,780
Jotta linkkejä, minä kulkea node1
nuolta, saatavuuden että solmu tähti,

82
00:04:38,780 --> 00:04:44,160
että solmu osoitin, vastaa node2,
osoittaa node1 to node2 kaksi.

83
00:04:44,160 --> 00:04:46,360
Ja siellä meillä on linkitetty lista.

84
00:04:46,360 --> 00:04:51,480
>> Joten se oli vain yksi linkitetty lista, mutta
tiiviste on koko joukon

85
00:04:51,480 --> 00:04:52,520
linkitettyjä listoja.

86
00:04:52,520 --> 00:04:55,920
No, meillä on sama solmu
rakenne kuin ennen.

87
00:04:55,920 --> 00:05:00,140
Mutta jos halusimme todellinen tiiviste,
voimme vain tehdä solmu osoitin

88
00:05:00,140 --> 00:05:01,330
array täällä.

89
00:05:01,330 --> 00:05:04,940
Esimerkiksi koko 500.

90
00:05:04,940 --> 00:05:08,910
>> Nyt ilmoitusta, siellä tulee olemaan kaupan
pois välillä kokoa

91
00:05:08,910 --> 00:05:11,280
tiiviste ja koko
oman linkitettyjä listoja.

92
00:05:11,280 --> 00:05:15,640
Jos sinulla on todella suuri määrä
kauhat, kuvitellen ottaa juosta takaisin

93
00:05:15,640 --> 00:05:18,230
ja esiin linja
löytää ämpäri.

94
00:05:18,230 --> 00:05:21,530
Mutta et myöskään halua pieni määrä
kauhat, koska silloin olemme takaisin

95
00:05:21,530 --> 00:05:26,850
alkuperäinen ongelma, miten ottaa
liian monta palloa meidän ämpäri.

96
00:05:26,850 --> 00:05:30,480
>> OK, mutta mistä meidän pallo mennä?

97
00:05:30,480 --> 00:05:33,150
No, meidän on ensin
on pallo, eikö?

98
00:05:33,150 --> 00:05:39,130
Joten malloc solmu jokaista
uusi sana, että meillä on.

99
00:05:39,130 --> 00:05:42,900
solmu * new_node tasavertaisina
malloc (sizeof (solmu)).

100
00:05:42,900 --> 00:05:46,760
>> Nyt kun meillä on tämä rakenne, me
voi skannata funktion

101
00:05:46,760 --> 00:05:51,850
fscanf, string meidän tiedoston, jos
se on sanakirja-tiedosto,

102
00:05:51,850 --> 00:05:55,780
new_node nuoli sana, jossa new_node
nuoli sana on meidän

103
00:05:55,780 --> 00:05:58,110
määränpää tämä sana.

104
00:05:58,110 --> 00:06:01,900
>> Seuraavaksi me haluamme hash että
sana käyttämällä hash-funktiota.

105
00:06:01,900 --> 00:06:05,860
Hajautusfunktio vie merkkijonon
ja palauttaa indeksin.

106
00:06:05,860 --> 00:06:09,760
Tässä tapauksessa indeksi on
olla pienempi kuin määrä

107
00:06:09,760 --> 00:06:11,440
kauhat, että sinulla on.

108
00:06:11,440 --> 00:06:14,600
>> Nyt hajautusfunktioita, kun yrität
löytää ja luoda yksi

109
00:06:14,600 --> 00:06:17,890
oman, muista, että ne
täytyy olla deterministinen.

110
00:06:17,890 --> 00:06:22,420
Tämä tarkoittaa, että sama arvo on
kartta samaan ämpäri joka kerta

111
00:06:22,420 --> 00:06:23,800
että olet hash sitä.

112
00:06:23,800 --> 00:06:25,300
>> Se on tavallaan kuin kirjasto.

113
00:06:25,300 --> 00:06:28,560
Kun otat kirjan, joka perustuu
kirjailija, tiedät mikä hylly pitääkin

114
00:06:28,560 --> 00:06:31,890
mennä, onko se hyllynumero
yksi, kaksi tai kolme.

115
00:06:31,890 --> 00:06:36,280
Ja että kirja kuuluvat aina päällä
joko hylly yksi, kaksi tai kolme.

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

117
00:06:39,460 --> 00:06:43,810
>> Joten, jos new_node nuoli sanalla on
sanan sanakirjaa sitten

118
00:06:43,810 --> 00:06:47,770
hajautusta new_node arrow sana
antaa meille indeksi

119
00:06:47,770 --> 00:06:49,370
ämpäri tiiviste.

120
00:06:49,370 --> 00:06:54,040
Ja sitten me lisätä, että tuohon
erityiset linkitetty lista merkitty

121
00:06:54,040 --> 00:06:56,060
palata arvoa meidän hajautusfunktio.

122
00:06:56,060 --> 00:06:59,070
>> Katsotaanpa esimerkki
lisäämällä solmun

123
00:06:59,070 --> 00:07:01,750
alussa linkitetyn listan.

124
00:07:01,750 --> 00:07:06,930
Jos pää on solmu osoitin, joka ilmaisee
alussa linkitetty

125
00:07:06,930 --> 00:07:12,420
luettelosta ja new_node osoittaa uusi
solmu, joka haluat päästä sisälle, vain

126
00:07:12,420 --> 00:07:17,340
osoitetaan pään new_node menettäisi
linkki muuhun luettelosta.

127
00:07:17,340 --> 00:07:19,330
Joten emme halua tehdä tätä.

128
00:07:19,330 --> 00:07:22,160
>> Pikemminkin haluamme varmistaa
että pidämme kiinni jokaiseen

129
00:07:22,160 --> 00:07:23,550
yhden solmun ohjelmaamme.

130
00:07:23,550 --> 00:07:29,560
Joten käynnissä new_node nuolta tasavertaisina
pää ja sitten pää vastaa new_node

131
00:07:29,560 --> 00:07:34,470
säilyttää kaikki
linkkejä ja menetä mitään.

132
00:07:34,470 --> 00:07:39,330
>> Mutta entä jos haluat luettelon olevan
lajiteltu, koska ottaa lajiteltu linkitetty

133
00:07:39,330 --> 00:07:42,910
lista saattaa olla helpompi
etsimällä sen myöhemmin?

134
00:07:42,910 --> 00:07:46,020
No, että sinun täytyy tietää
miten kulkea linkitettyjä listoja.

135
00:07:46,020 --> 00:07:51,210
>> Kulkemaan linkitetty lista, otetaanpa
solmun osoitin, solmu *, toimimaan

136
00:07:51,210 --> 00:07:54,120
kohdistin, mitkä
solmuun olet alkaen

137
00:07:54,120 --> 00:07:55,460
ensimmäisen elementin.

138
00:07:55,460 --> 00:08:01,070
Silmukoiden kunnes kohdistin on null, voimme
suorittaa tiettyjä prosesseja ja sitten

139
00:08:01,070 --> 00:08:04,330
etukäteen kohdistin kun tarvitsemme
käyttäen kursorin nuolen arvoa.

140
00:08:04,330 --> 00:08:08,820
>> Muista, että tämä on sama asia kuin
sanomalla tähden kursori, dereferencing

141
00:08:08,820 --> 00:08:13,480
kohdistin, sitten käyttämällä
dot operaattorin arvo.

142
00:08:13,480 --> 00:08:19,000
Joten päivittäminen kursori on nimeämällä
kohdistin kursorin nuolta.

143
00:08:19,000 --> 00:08:24,960
>> Sano saat selville, että D tulee vuonna
välillä C ja E. Jos haluat lisätä solmun,

144
00:08:24,960 --> 00:08:30,030
on new_node D kohta
solmu E, joka on kursorin vieressä.

145
00:08:30,030 --> 00:08:36,409
Ja sitten C, kursori, voidaan osoittaa
D. Näin voit ylläpitää luetteloa.

146
00:08:36,409 --> 00:08:41,080
Varo menettää linkit
siirtämällä kursorin nuolen vieressä D

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

148
00:08:43,929 --> 00:08:44,620
>> Selvä.

149
00:08:44,620 --> 00:08:48,920
Niin, että miten voit lisätä solmuja,
lataa ne, kuorma sanat noihin

150
00:08:48,920 --> 00:08:51,600
solmut, ja aseta ne
omaan tiiviste.

151
00:08:51,600 --> 00:08:53,580
Joten nyt katsokaamme yrittää.

152
00:08:53,580 --> 00:08:58,540
>> Vuonna trie, jokainen solmu sisältää
joukko solmun osoittimia, yksi jokaista

153
00:08:58,540 --> 00:09:02,260
kirjain aakkosissa
plus heittomerkki.

154
00:09:02,260 --> 00:09:06,150
Ja jokainen alkio
tulee kohta toiseen solmuun.

155
00:09:06,150 --> 00:09:10,130
Jos tämä solmu on null, niin että kirje
ei tule olemaan seuraava kirjeellä

156
00:09:10,130 --> 00:09:15,690
tahansa sana järjestyksessä, koska jokainen
sana osoittaa, mikäli kyseessä on viimeinen

157
00:09:15,690 --> 00:09:18,160
luonnetta sanan tai ei.

158
00:09:18,160 --> 00:09:19,750
>> Katsotaanpa kaavio.

159
00:09:19,750 --> 00:09:22,260
Toivottavasti asiat
olla hieman selkeämpi.

160
00:09:22,260 --> 00:09:27,210
Tässä kaaviossa, näemme, että vain
tiettyjen kirjainten ja tiettyjen osamerkkijonoihin

161
00:09:27,210 --> 00:09:28,190
ollaan lueteltu ulos.

162
00:09:28,190 --> 00:09:32,500
Joten voit seurata tiettyjä polkuja, ja
kaikki nämä polut johtaa sinut

163
00:09:32,500 --> 00:09:34,020
eri sanoja.

164
00:09:34,020 --> 00:09:37,630
>> Miten siis edustamaan tätä C?

165
00:09:37,630 --> 00:09:41,910
No, jokainen solmu nyt joutuu
Boolean ilmaisee, onko

166
00:09:41,910 --> 00:09:46,580
, että solmu on lopussa
tiettyä sanaa vai ei.

167
00:09:46,580 --> 00:09:50,690
Ja niin se tulee myös joukko
solmu viitteitä lapsen nimen, ja

168
00:09:50,690 --> 00:09:53,440
siellä tulevat olemaan 27 heistä.

169
00:09:53,440 --> 00:09:56,510
Ja muista, sinun kannattaa myös
seurata oman ensimmäisen solmun.

170
00:09:56,510 --> 00:09:59,830
Aiomme soittaa että juuri.

171
00:09:59,830 --> 00:10:01,690
>> Niin, että rakenne triellä.

172
00:10:01,690 --> 00:10:05,630
Miten me edustamme tätä
sanakirjana?

173
00:10:05,630 --> 00:10:09,890
No, ladata sanoja, jokaiselle
sanakirja sana, olet menossa haluavat

174
00:10:09,890 --> 00:10:11,960
iteroitava triessä.

175
00:10:11,960 --> 00:10:16,170
Ja jokaisen elementin lapsia
vastaa eri kirjain.

176
00:10:16,170 --> 00:10:21,660
>> Joten tarkistaa arvoa lapsille
indeksin i, missä i edustaa

177
00:10:21,660 --> 00:10:24,840
-indeksi kirjeestä, jonka
yrität lisätä.

178
00:10:24,840 --> 00:10:28,980
No, jos se on nolla, niin sinun kannattaa
malloc uusi solmu ja saada lapsia

179
00:10:28,980 --> 00:10:31,110
Osoitan, että solmu.

180
00:10:31,110 --> 00:10:35,630
>> Jos se ei ole tyhjä, niin se tarkoittaa, että
että koska sivuliikkeen, että annetaan

181
00:10:35,630 --> 00:10:37,350
alimerkkijono, on jo olemassa.

182
00:10:37,350 --> 00:10:40,160
Joten Tulet siirtymällä haluamaasi
uusi solmu ja jatkaa.

183
00:10:40,160 --> 00:10:43,220
Jos olet lopussa sana, joka
yrität ladata vuonna

184
00:10:43,220 --> 00:10:48,120
sanakirja, voit asettaa, että
nykyisen solmun että olet tosi.

185
00:10:48,120 --> 00:10:51,550
>> Joten katsokaamme esimerkki lisäämällä
sana "kettu" meidän

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

187
00:10:53,070 --> 00:10:56,110
Teeskennellä aloitamme
tyhjä sanakirja.

188
00:10:56,110 --> 00:11:01,610
Ensimmäinen kirjain, F, tulee sijaitsemaan
lapsilla indeksi viisi juuret

189
00:11:01,610 --> 00:11:03,700
lasten array.

190
00:11:03,700 --> 00:11:05,430
Niin lisäämme, että sisään

191
00:11:05,430 --> 00:11:14,610
>> O-kirjain on sitten lapsilla
indeksi 15, jonka jälkeen F. Ja sitten X

192
00:11:14,610 --> 00:11:20,180
on jopa alle, että aluevaltaus
pois O lapsia.

193
00:11:20,180 --> 00:11:24,120
Ja sitten, koska X on viimeinen kirjain
sanan "kettu", niin aion

194
00:11:24,120 --> 00:11:27,210
väri, vihreänä,
se on sanan lopussa.

195
00:11:27,210 --> 00:11:32,880
C, että vaihtoehto olisi Is
Sana Boolean arvoon totta.

196
00:11:32,880 --> 00:11:36,780
>> Nyt mitä jos seuraava sana, että olet
lastausta on sana "foo"?

197
00:11:36,780 --> 00:11:41,490
No, sinun ei tarvitse malloc enää
tilaa F tai O, koska

198
00:11:41,490 --> 00:11:42,990
jo olemassa.

199
00:11:42,990 --> 00:11:45,910
Mutta viimeinen O foo?

200
00:11:45,910 --> 00:11:47,320
Että yksi, sinun täytyy malloc.

201
00:11:47,320 --> 00:11:52,390
Tee uusi solmu, että asetus
Onko Word Boolen totta.

202
00:11:52,390 --> 00:11:57,340
>> Joten Nyt lisätä "koira." Koira
aloittaa indeksi kolme juuret

203
00:11:57,340 --> 00:12:00,520
lapsia, koska D ei ole
vielä luotu.

204
00:12:00,520 --> 00:12:04,990
Niin otamme samanlainen prosessi kuin
ennen, luoda osamerkkijonon koira,

205
00:12:04,990 --> 00:12:10,400
Missä G on väriltään vihreä, koska
se on sanan lopussa.

206
00:12:10,400 --> 00:12:13,160
>> Nyt, mitä jos haluamme lisätä "tehdä"?

207
00:12:13,160 --> 00:12:17,150
No, tämä on alimerkkijono koira, joten
meidän ei tarvitse malloc enää.

208
00:12:17,150 --> 00:12:20,800
Mutta meidän on ilmoitettava, missä olemme
lopussa tuo sana.

209
00:12:20,800 --> 00:12:24,020
Joten O on väriltään vihreä.

210
00:12:24,020 --> 00:12:27,810
Jatkuvat että prosessi joka ikinen
sanan sanakirjaa, olet

211
00:12:27,810 --> 00:12:32,120
ladattu ne osaksi joko
hash table tai triellä.

212
00:12:32,120 --> 00:12:37,530
>> speller.c välitän jousille
dictionary.c tarkistaa ne.

213
00:12:37,530 --> 00:12:41,140
Nyt Tarkista toiminto on toimittava
alle tapauksessa välinpitämättömyys.

214
00:12:41,140 --> 00:12:45,980
Tämä tarkoittaa, että isoja kirjaimia ja
pieniä kirjaimia ja sekoitus molempia

215
00:12:45,980 --> 00:12:50,670
kaikkien pitäisi rinnastaa arvoksi true, jos mitään
yhdistelmä, joka on

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

217
00:12:51,880 --> 00:12:55,580
Voit myös olettaa, että kielet ovat
vain menossa sisältää aakkosjärjestyksessä

218
00:12:55,580 --> 00:12:58,200
merkkejä tai heittomerkit.

219
00:12:58,200 --> 00:13:02,490
>> Joten katsotaanpa miten voisit tarkistaa
kanssa hash taulukon rakenne.

220
00:13:02,490 --> 00:13:07,330
No, jos sana on olemassa, niin se
löytyvät tiiviste.

221
00:13:07,330 --> 00:13:12,240
Niin sitten voit yrittää löytää, että
sana asiaa ämpäri.

222
00:13:12,240 --> 00:13:14,480
>> Joten mikä ämpäri olisi, että sana olla?

223
00:13:14,480 --> 00:13:20,060
No, saat luultavasti numero, että indeksi
kauhan, hajautusrakenteissa tämä sana

224
00:13:20,060 --> 00:13:23,690
ja sitten hakuja että linkitetty lista,
liikkumisesta läpi koko

225
00:13:23,690 --> 00:13:28,060
linkitetty lista, käyttäen String
Vertaa toiminto.

226
00:13:28,060 --> 00:13:31,940
>> Jos pää linkitetty lista on
saavutettu, mikä tarkoittaa, että kohdistin

227
00:13:31,940 --> 00:13:36,030
saavuttaa null, niin sana ei ole
joka löytyy sanakirjasta.

228
00:13:36,030 --> 00:13:39,090
Se ei ole missään muussa ämpäri.

229
00:13:39,090 --> 00:13:43,020
Joten tässä, saatat nähdä, miten siellä pitää
olla kompromisseja, joilla on joko

230
00:13:43,020 --> 00:13:46,280
lajiteltu linkitetyt tai lajittelemattoman niistä.

231
00:13:46,280 --> 00:13:51,180
Joko vie enemmän aikaa aikana
lastata tai enemmän aikana tarkistaa.

232
00:13:51,180 --> 00:13:53,560
>> Miten voisit tarkistaa
trie rakenne?

233
00:13:53,560 --> 00:13:56,370
Aiomme matkustaa alaspäin
triessä.

234
00:13:56,370 --> 00:14:00,390
Jokaisen kirjeen syötetty sana
että me tarkastamme, menemme että

235
00:14:00,390 --> 00:14:03,280
vastaava osa lapsia.

236
00:14:03,280 --> 00:14:07,770
>> Jos tämä elementti on tyhjä, niin se tarkoittaa,
että ei ole olemassa merkkijonoa

237
00:14:07,770 --> 00:14:11,110
sisältävät meidän tulosana, joten
sana on kirjoitettu väärin.

238
00:14:11,110 --> 00:14:15,140
Jos se ei ole nolla, voimme siirtyä
seuraava kirjain sanan, että olemme

239
00:14:15,140 --> 00:14:18,850
tarkkailun ja jatkaa tätä prosessia
kunnes pääsemme loppuun

240
00:14:18,850 --> 00:14:20,350
tulo-sana.

241
00:14:20,350 --> 00:14:23,330
Ja sitten voimme tarkistaa
If on Sana on totta.

242
00:14:23,330 --> 00:14:24,610
Jos se on, niin hienoa.

243
00:14:24,610 --> 00:14:25,590
Sana on oikein.

244
00:14:25,590 --> 00:14:30,890
Mutta jos ei, vaikka tämä alimerkkijono
olemassa triessä, sana on

245
00:14:30,890 --> 00:14:32,250
kirjoitettu väärin.

246
00:14:32,250 --> 00:14:36,590
>> Kun toiminto Koko kutsutaan, koko
pitäisi palata sanojen määrästä

247
00:14:36,590 --> 00:14:39,110
ovat teidän annetaan sanakirjassa
tietorakenne.

248
00:14:39,110 --> 00:14:42,780
Joten jos käytät hash-taulukon
voi joko mennä läpi joka ikinen

249
00:14:42,780 --> 00:14:45,860
linkitetty lista jokaisessa
ämpäri laskemalla

250
00:14:45,860 --> 00:14:47,130
sanoista on siellä.

251
00:14:47,130 --> 00:14:49,940
Jos käytät triellä, voit
käytävä läpi ei null

252
00:14:49,940 --> 00:14:52,030
polku teidän triessä.

253
00:14:52,030 --> 00:14:56,420
Tai kun lataat sanakirja
vuonna, ehkä voit seurata, kuinka

254
00:14:56,420 --> 00:14:58,760
monta sanaa lataat sisään

255
00:14:58,760 --> 00:15:03,180
>> Kun speller.c lopettaa tarkkailun
tekstitiedosto vastaan ​​sanakirja, sitten

256
00:15:03,180 --> 00:15:08,010
se on tehty ja niin se vaatii Unload, jossa
sinun tehtäväsi on vapauttaa mitään

257
00:15:08,010 --> 00:15:09,500
että olet malloced.

258
00:15:09,500 --> 00:15:14,420
Joten jos käytät hash table, sinun
täytyy olla erityisen varovainen, jotta vältetään

259
00:15:14,420 --> 00:15:18,830
muisti vuodot eivät vapauttamalla mitään
ennenaikaisesti ja pitää kiinni joka

260
00:15:18,830 --> 00:15:20,780
single link ennen teidät vapaiksi.

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

262
00:15:24,680 --> 00:15:30,100
>> Joten jokaisen elementin tiiviste
ja jokaisen solmun linkitetyn listan,

263
00:15:30,100 --> 00:15:32,370
sinun kannattaa vapauttaa, että solmu.

264
00:15:32,370 --> 00:15:34,970
Miten te sitten vapauttaa
linkitetty lista?

265
00:15:34,970 --> 00:15:38,570
Asettaminen solmu osoittimen kohdistin
pää, alkuun

266
00:15:38,570 --> 00:15:43,100
linkitetty lista, sitten kun kohdistin
ei ole nolla, voit asettaa tilapäisen

267
00:15:43,100 --> 00:15:45,610
solmu osoitin kohdistin.

268
00:15:45,610 --> 00:15:48,370
Siirry sitten kursori.

269
00:15:48,370 --> 00:15:52,950
Ja sitten voit vapauttaa että väliaikainen
arvo samalla tilalla

270
00:15:52,950 --> 00:15:55,650
kaiken jälkeenpäin.

271
00:15:55,650 --> 00:15:57,800
>> Mitä jos käytät triellä?

272
00:15:57,800 --> 00:16:00,410
Niin paras tapa tehdä tämä
on purkaa aivan

273
00:16:00,410 --> 00:16:02,290
alhaalta ylöspäin.

274
00:16:02,290 --> 00:16:06,920
Matkustamalla mahdollisimman
solmu, voit vapaasti kaikkia viitteitä

275
00:16:06,920 --> 00:16:11,430
että lapset ja sitten perääntyä
ylöspäin, vapauttaa kaikki elementit kaikissa

276
00:16:11,430 --> 00:16:15,610
lasten ryhmät, kunnes
osut alkuun juurisolmuun.

277
00:16:15,610 --> 00:16:18,920
Tässä missä Rekursio
tulee kätevä.

278
00:16:18,920 --> 00:16:22,780
>> Varmista, että olet todennäköisesti vapautettu
kaiken, olet malloced,

279
00:16:22,780 --> 00:16:24,400
voit käyttää Valgrind.

280
00:16:24,400 --> 00:16:28,640
Juoksu Valgrind ajaa oman ohjelman
laskemalla, kuinka monta tavua muistia

281
00:16:28,640 --> 00:16:32,440
käytät ja varmistaa, että olet
vapautti heidät kaikki, kerron

282
00:16:32,440 --> 00:16:34,530
jos saatat olla
unohtanut ilmaiseksi.

283
00:16:34,530 --> 00:16:38,390
Niin ajelu että ja kun Valgrind kertoo
ja antaa sinulle mennä eteenpäin, niin

284
00:16:38,390 --> 00:16:41,160
olet valmis purkaa.

285
00:16:41,160 --> 00:16:44,420
>> Nyt, pari vinkkiä ennen lähtöä
pois ja alkaa toteuttaa oman

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

287
00:16:46,260 --> 00:16:49,650
Suosittelen kulkea pienempi
sanakirjassa kun yrität testata

288
00:16:49,650 --> 00:16:52,620
asioita ja testaajat BKT.

289
00:16:52,620 --> 00:16:58,550
Käyttö Speller. / Speller,
valinnainen sanakirja, ja sitten teksti.

290
00:16:58,550 --> 00:17:01,550
>> Oletuksena se lataa vuonna
suuri sanakirja.

291
00:17:01,550 --> 00:17:06,670
Joten kannattaa kulkea pieni
sanakirja, tai ehkä jopa tehdä

292
00:17:06,670 --> 00:17:11,819
oma, muokkaamalla sanakirja
ja tekstitiedosto.

293
00:17:11,819 --> 00:17:15,950
>> Ja lopulta, olisin myös suositella
ottaa kynä ja paperia ja piirrä

294
00:17:15,950 --> 00:17:20,490
asioita ennen, sen aikana ja sen jälkeen
olet kirjoittanut kaikki koodi.

295
00:17:20,490 --> 00:17:24,170
Vain varmista, että sinulla
näitä viitteitä juuri oikea.

296
00:17:24,170 --> 00:17:26,480
>> Toivotan teille onnea.

297
00:17:26,480 --> 00:17:29,690
Ja kun olet valmis, jos haluat
haastaa iso board ja

298
00:17:29,690 --> 00:17:34,390
kuinka nopeasti ohjelman verrataan
luokkatoverit ", niin kehotan

299
00:17:34,390 --> 00:17:35,960
voit tarkistaa, että ulos.

300
00:17:35,960 --> 00:17:39,220
>> Kanssa, että olet lopettanut
speller PSET.

301
00:17:39,220 --> 00:17:41,800
Nimeni on Zamyla, ja tämä on CS50.

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