1
00:00:00,000 --> 00:00:12,350
>> [Musiikki soi]

2
00:00:12,350 --> 00:00:13,050
>> ROB BOWDEN: Hei.

3
00:00:13,050 --> 00:00:13,640
Olen Rob.

4
00:00:13,640 --> 00:00:16,210
Ja nyt tämä ratkaisu ulos.

5
00:00:16,210 --> 00:00:20,070
Joten tässä me aiomme toteuttaa
yleinen pöytä.

6
00:00:20,070 --> 00:00:24,090
Näemme, että struct solmu meidän
taulukossa on menossa näyttää tältä.

7
00:00:24,090 --> 00:00:28,710
Niin se tulee olla char sana
taulukon koko pituus + 1.

8
00:00:28,710 --> 00:00:32,259
Älä unohda + 1, koska suurin
sanan sanakirjasta on 45

9
00:00:32,259 --> 00:00:33,130
merkkiä.

10
00:00:33,130 --> 00:00:37,070
Ja sitten me aiomme tarvitsevat yhden ylimääräisen
merkin kenoviiva nolla.

11
00:00:37,070 --> 00:00:40,870
>> Ja sitten meidän hashtable kussakin
kauha on menossa tallentamaan

12
00:00:40,870 --> 00:00:42,320
linkitetyn listan solmuja.

13
00:00:42,320 --> 00:00:44,420
Emme tee lineaarinen luotaa täällä.

14
00:00:44,420 --> 00:00:48,430
Ja niin, jotta sen yhteys seuraavaan
elementti ämpäri, tarvitsemme

15
00:00:48,430 --> 00:00:50,390
struct solmu * seuraavaksi.

16
00:00:50,390 --> 00:00:51,110
OK.

17
00:00:51,110 --> 00:00:53,090
Niin, että mitä solmu näyttää.

18
00:00:53,090 --> 00:00:56,180
>> Nyt tässä ilmoituksessa
meidän hashtable.

19
00:00:56,180 --> 00:00:59,640
Se tulee olla 16834 kauhat.

20
00:00:59,640 --> 00:01:01,910
Mutta että numero ei ole oikeastaan ​​väliä.

21
00:01:01,910 --> 00:01:05,450
Ja lopuksi, me aiomme olla
globaali muuttuja hashtable koko, joka

22
00:01:05,450 --> 00:01:07,000
aikoo alkajaisiksi kuin nolla.

23
00:01:07,000 --> 00:01:10,760
Ja se tulee seurata, kuinka
monet sanat ovat meidän sanakirja.

24
00:01:10,760 --> 00:01:13,710
>> Joten katsotaanpa katsomaan kuormalla.

25
00:01:13,710 --> 00:01:16,390
Huomaa, että kuorman, se palauttaa bool.

26
00:01:16,390 --> 00:01:20,530
Palaat tosi, jos se onnistui
ladattu ja vääriä toisin.

27
00:01:20,530 --> 00:01:23,990
Ja se vie const char * sanakirja,
joka on sanakirja

28
00:01:23,990 --> 00:01:25,280
että haluamme avata.

29
00:01:25,280 --> 00:01:27,170
Niin, että ensimmäinen asia
aiomme tehdä.

30
00:01:27,170 --> 00:01:29,500
>> Aiomme fopen
sanakirja lukemiseen.

31
00:01:29,500 --> 00:01:31,680
Ja me aiomme pitäisi tehdä
Varmista, että se onnistui.

32
00:01:31,680 --> 00:01:35,920
Joten jos se palautetaan NULL, niin emme
onnistuneesti Avaa sanakirja.

33
00:01:35,920 --> 00:01:37,440
Ja meidän täytyy palata vääriä.

34
00:01:37,440 --> 00:01:41,580
Mutta olettaen, että se teki onnistuneesti
auki, haluamme lukea

35
00:01:41,580 --> 00:01:42,400
sanakirja.

36
00:01:42,400 --> 00:01:46,450
Joten pitää kiehkura kunnes löydämme
syytä murtautua ulos tästä silmukan,

37
00:01:46,450 --> 00:01:47,570
jonka näemme.

38
00:01:47,570 --> 00:01:48,920
Joten pitää kiehkura.

39
00:01:48,920 --> 00:01:51,780
>> Ja nyt me aiomme
malloc yhden solmun.

40
00:01:51,780 --> 00:01:54,020
Ja tietysti me tarvitsemme
tuuletusta tarkista uudelleen.

41
00:01:54,020 --> 00:01:58,680
Joten jos mallocing ei onnistunut, niin
haluamme purkaa tahansa solmuun, että me

42
00:01:58,680 --> 00:02:02,590
tapahtui malloc ennen, sulje
sanakirja ja palauttaa false.

43
00:02:02,590 --> 00:02:06,830
Mutta unohdetaan, että vaikka oletettaisiin me
onnistunut, niin haluamme käyttää fscanf

44
00:02:06,830 --> 00:02:12,400
lukea sanaakaan meidän
sanaston meidän solmuun.

45
00:02:12,400 --> 00:02:17,940
Niin muista, että merkintä> sana on char
sana puskurin koko lenghth + 1

46
00:02:17,940 --> 00:02:20,300
että aiomme säilyttää sanan sisään

47
00:02:20,300 --> 00:02:25,070
>> Joten fscanf tulee palata 1, niin kauan
sillä se kykeni

48
00:02:25,070 --> 00:02:26,750
lukea sana tiedoston.

49
00:02:26,750 --> 00:02:30,460
Jos jompikumpi virhe tapahtuu, tai me
päähän tiedoston, se

50
00:02:30,460 --> 00:02:31,950
ei palaa 1.

51
00:02:31,950 --> 00:02:35,180
Jolloin se ei palaa 1,
olemme vihdoin menossa murtautua ulos

52
00:02:35,180 --> 00:02:37,280
Tässä kun silmukka.

53
00:02:37,280 --> 00:02:42,770
Näemme siis, että kun meillä on onnistuneesti
lukea sanan

54
00:02:42,770 --> 00:02:48,270
entry> sana, niin aiomme että
sana käyttämällä tiivistefunktiota.

55
00:02:48,270 --> 00:02:49,580
>> Katsotaanpa katsomaan
hash-funktio.

56
00:02:49,580 --> 00:02:52,430

57
00:02:52,430 --> 00:02:55,610
Joten sinun ei todellakaan tarvitse
ymmärtää tätä.

58
00:02:55,610 --> 00:02:59,460
Ja oikeastaan ​​me vain veti tämän hash
toimiakseen Internetistä.

59
00:02:59,460 --> 00:03:04,010
Ainoa asia, sinun täytyy tunnustaa, on
että tämä vie const char * sana.

60
00:03:04,010 --> 00:03:08,960
Joten se vie narua tulo, ja
palaamassa unsigned int tuotokseksi.

61
00:03:08,960 --> 00:03:12,360
Niin, että kaikki hash-toiminto on, on se
vie tulo ja antaa sinulle

62
00:03:12,360 --> 00:03:14,490
indeksinä hashtable.

63
00:03:14,490 --> 00:03:18,530
>> Huomaa, että olemme moding by NUM_BUCKETS,
jotta palautettu arvo

64
00:03:18,530 --> 00:03:21,730
itse asiassa on indeksinä hashtable
ja ei indeksoi yli

65
00:03:21,730 --> 00:03:24,320
rajat array.

66
00:03:24,320 --> 00:03:28,060
Joten koska toiminto, aiomme
hash sana, joka luemme

67
00:03:28,060 --> 00:03:29,390
sanakirja.

68
00:03:29,390 --> 00:03:31,700
Ja sitten me aiomme käyttää
että hash lisätä

69
00:03:31,700 --> 00:03:33,750
tuloa hashtable.

70
00:03:33,750 --> 00:03:38,520
>> Nyt hashtable hash on nykyinen
linkitetty lista taulukossa.

71
00:03:38,520 --> 00:03:41,410
Ja se on hyvin mahdollista
että se on vain NULL.

72
00:03:41,410 --> 00:03:44,960
Haluamme lisätä meidän käännyttämiseksi
Alussa tämän linkitetyn listan.

73
00:03:44,960 --> 00:03:48,600
Ja niin me aiomme olla nykyiseen
alkupisteestä mitä hashtable

74
00:03:48,600 --> 00:03:50,380
tällä hetkellä viittaa.

75
00:03:50,380 --> 00:03:53,310
Ja sitten me aiomme säilyttää,
vuonna hashtable osoitteessa

76
00:03:53,310 --> 00:03:55,350
hash, nykyinen tieto.

77
00:03:55,350 --> 00:03:59,320
Joten nämä kaksi riviä onnistuneesti aseta
merkintä alussa

78
00:03:59,320 --> 00:04:02,260
linkitetty lista tuohon hakemisto
vuonna hashtable.

79
00:04:02,260 --> 00:04:04,900
>> Kun olemme tehneet, että me tiedämme
että löysimme toinen sana

80
00:04:04,900 --> 00:04:07,790
sanakirja, ja me kasvattaa uudelleen.

81
00:04:07,790 --> 00:04:13,960
Joten meidän pitää tehdä, että kunnes fscanf
palasi lopulta jotain ei-1

82
00:04:13,960 --> 00:04:16,950
missä vaiheessa muistaa, että
meidän on vapaa pääsy.

83
00:04:16,950 --> 00:04:19,459
Joten täällä me malloced merkintä.

84
00:04:19,459 --> 00:04:21,329
Ja yritimme lukea jotain
sanakirjasta.

85
00:04:21,329 --> 00:04:23,910
Ja emme onnistuttiin lukemaan
jotain sanakirjasta vuonna

86
00:04:23,910 --> 00:04:26,650
joka tapauksessa meidän täytyy vapauttaa merkintä
että emme koskaan oikeastaan ​​panna

87
00:04:26,650 --> 00:04:29,140
hashtable, ja lopulta murtaa.

88
00:04:29,140 --> 00:04:32,750
>> Kun me puhkeaa meidän täytyy nähdä, hyvin,
me puhkeaa, koska siellä

89
00:04:32,750 --> 00:04:34,360
oli virhe luettaessa tiedostoa?

90
00:04:34,360 --> 00:04:37,120
Vai rikomme pois, koska me
lopussa tiedoston?

91
00:04:37,120 --> 00:04:39,480
Jos oli virhe,
haluamme palata vääriä.

92
00:04:39,480 --> 00:04:40,930
Koska kuormitus ei onnistunut.

93
00:04:40,930 --> 00:04:43,890
Ja samalla haluamme purkaa
kaikki sanat, jotka luemme, ja

94
00:04:43,890 --> 00:04:45,670
Sulje sanastotiedostoa.

95
00:04:45,670 --> 00:04:48,740
>> Olettaen emme onnistu, sitten me vain
vielä sulkea sanakirja

96
00:04:48,740 --> 00:04:53,040
tiedostoon, ja lopulta palata totta, sillä me
ladattu onnistuneesti sanakirja.

97
00:04:53,040 --> 00:04:54,420
Ja se on siinä kuorman.

98
00:04:54,420 --> 00:04:59,020
Joten nyt tarkistaa, koska ladattu hashtable,
aikoo näyttää tältä.

99
00:04:59,020 --> 00:05:03,140
Joten tarkista, se palauttaa bool, joka on
menossa osoittamaan, onko kulunut

100
00:05:03,140 --> 00:05:07,530
char * sana, onko kulunut
merkkijono on meidän sanakirja.

101
00:05:07,530 --> 00:05:09,890
Joten jos se on sanakirjassa,
jos se on meidän hashtable,

102
00:05:09,890 --> 00:05:11,170
palaamme totta.

103
00:05:11,170 --> 00:05:13,380
Ja jos se ei ole, palaamme vääriä.

104
00:05:13,380 --> 00:05:17,740
>> Kun otetaan huomioon tämä kulunut sana, olemme
menossa hash sana.

105
00:05:17,740 --> 00:05:22,110
Nyt tärkeintä tunnistaa on
että kuorman tiesimme, että kaikki

106
00:05:22,110 --> 00:05:23,820
sanat aiomme pieniä kirjaimia.

107
00:05:23,820 --> 00:05:25,820
Mutta täällä emme ole niin varma.

108
00:05:25,820 --> 00:05:29,510
Jos me katsomaan meidän hajautusfunktio,
meidän hash-toiminto itse asiassa

109
00:05:29,510 --> 00:05:32,700
on pienempi kotelo kunkin merkin
sanan.

110
00:05:32,700 --> 00:05:37,940
Joten riippumatta arvo
sana, meidän hash funktio on paluu

111
00:05:37,940 --> 00:05:42,270
sama indeksi jostain
-arvo on, koska sillä olisi

112
00:05:42,270 --> 00:05:45,280
palautetaan kokonaan pienillä kirjaimilla
versio sanasta.

113
00:05:45,280 --> 00:05:46,600
Okei.

114
00:05:46,600 --> 00:05:49,790
Se on meidän indeksi on osaksi
Hashtable sanaa.

115
00:05:49,790 --> 00:05:52,940
>> Nyt tämä silmukka on menossa
kerrata yli linkitetty lista

116
00:05:52,940 --> 00:05:55,000
joka oli tuohon indeksi.

117
00:05:55,000 --> 00:05:59,610
Joten huomaat olemme alustetaan merkintä
osoittamaan, että indeksiin.

118
00:05:59,610 --> 00:06:02,750
Aiomme jatkaa
kun pääsy! = NULL.

119
00:06:02,750 --> 00:06:07,770
Ja muista, että päivittäminen osoitin
meidän linkitetty lista entry = entry> seuraavaksi.

120
00:06:07,770 --> 00:06:14,400
Niin on meidän nykyinen yhteys siihen
Esityslistalla on linkitetty lista.

121
00:06:14,400 --> 00:06:19,250
>> Joten jokaisen merkinnän linkitetty lista,
aiomme käyttää strcasecmp.

122
00:06:19,250 --> 00:06:20,330
Se ei ole strcomp.

123
00:06:20,330 --> 00:06:23,780
Koska jälleen kerran, haluamme
tehdä asioita tapauksessa insensitively.

124
00:06:23,780 --> 00:06:27,870
Joten käytämme strcasecmp vertailla
sana, joka on läpäissyt tämän

125
00:06:27,870 --> 00:06:31,860
toiminto sanaa vastaan
joka on tämän merkinnän.

126
00:06:31,860 --> 00:06:35,570
Jos se palaa nolla, se tarkoittaa, että oli
ottelu, jolloin haluamme

127
00:06:35,570 --> 00:06:36,630
return true.

128
00:06:36,630 --> 00:06:39,590
Olemme löytäneet
sana meidän hashtable.

129
00:06:39,590 --> 00:06:43,040
>> Jos ei ole ottelu, niin olemme
menossa silmukka uudelleen ja katsoa

130
00:06:43,040 --> 00:06:43,990
seuraava merkintä.

131
00:06:43,990 --> 00:06:47,640
Ja jatkamme silmukoiminen vaikka
ovat merkintöjä tähän linkitetty lista.

132
00:06:47,640 --> 00:06:50,160
Mitä tapahtuu, jos rikomme
pois tästä silmukan?

133
00:06:50,160 --> 00:06:55,110
Tämä tarkoittaa emme löytäneet merkinnän, joka
Hyväksytty tämä sana, jolloin

134
00:06:55,110 --> 00:07:00,220
palaamme epätosi ilmaisten, että
hashtable ei sisältänyt tätä sanaa.

135
00:07:00,220 --> 00:07:02,540
Ja se tarkistaa.

136
00:07:02,540 --> 00:07:04,790
>> Joten katsotaanpa katsomaan koko.

137
00:07:04,790 --> 00:07:06,970
Nyt koko tulee olemaan melko yksinkertainen.

138
00:07:06,970 --> 00:07:11,080
Koska muistaa kuorman, jokaista sanaa
löysimme meillä kasvatetaan maailmanlaajuisen

139
00:07:11,080 --> 00:07:12,880
muuttuja hashtable koko.

140
00:07:12,880 --> 00:07:16,480
Joten koko toiminto on juuri menossa
palata globaali muuttuja.

141
00:07:16,480 --> 00:07:18,150
Ja se on siinä.

142
00:07:18,150 --> 00:07:22,300
>> Nyt vihdoin, meidän täytyy purkaa
sanakirjassa kerran kaiken tehtyä.

143
00:07:22,300 --> 00:07:25,340
Niin miten me sen teemme?

144
00:07:25,340 --> 00:07:30,440
Täällä olemme silmukoiden yli
kaikki ämpärillistä meidän pöytään.

145
00:07:30,440 --> 00:07:33,240
Joten on NUM_BUCKETS kauhat.

146
00:07:33,240 --> 00:07:37,410
Ja kunkin linkitetyn listan meidän
hashtable, aiomme lenkki

147
00:07:37,410 --> 00:07:41,070
kokonaisuudessaan linkitetty lista,
vapauttaa jokaisen elementin.

148
00:07:41,070 --> 00:07:42,900
>> Nyt meidän on oltava varovaisia.

149
00:07:42,900 --> 00:07:47,910
Joten tässä meillä on väliaikainen muuttuja,
joka tallennetaan osoitin seuraavaan

150
00:07:47,910 --> 00:07:49,730
elementti linkitetty lista.

151
00:07:49,730 --> 00:07:52,140
Ja sitten me aiomme ilmaiseksi
elementin.

152
00:07:52,140 --> 00:07:55,990
Meidän on oltava varmoja teemme tämän, koska meillä
voi vain vapauttaa elementin

153
00:07:55,990 --> 00:07:59,180
ja yritä sitten käyttää seuraavaan osoitin,
koska kerran olemme vapautettu, sitä,

154
00:07:59,180 --> 00:08:00,870
muisti mitätöityy.

155
00:08:00,870 --> 00:08:04,990
>> Joten meidän täytyy pitää noin osoitin
seuraavan osan, voimme vapauttaa

156
00:08:04,990 --> 00:08:08,360
elementin, ja sitten voimme päivittää
nykyinen elementti osoittamaan

157
00:08:08,360 --> 00:08:09,550
seuraavan osan.

158
00:08:09,550 --> 00:08:12,800
Me silmukka, kun on olemassa tekijöitä,
Tässä linkitetty lista.

159
00:08:12,800 --> 00:08:15,620
Teemme että kaikilla yhdistetyillä
luettelot hashtable.

160
00:08:15,620 --> 00:08:19,460
Ja kun olemme tehneet, että olemme
kokonaan purettu hashtable, ja

161
00:08:19,460 --> 00:08:20,190
olemme valmiit.

162
00:08:20,190 --> 00:08:23,200
Joten se on mahdotonta purkaa
koskaan palata vääriä.

163
00:08:23,200 --> 00:08:26,470
Ja kun olemme tehneet, me
vain palata totta.

164
00:08:26,470 --> 00:08:29,000
>> Annetaanpa tämän ratkaisun yrittää.

165
00:08:29,000 --> 00:08:33,070
Joten katsomaan mitä
struct solmu näyttää.

166
00:08:33,070 --> 00:08:36,220
Tässä näemme aiomme olla bool
sana ja struct solmu * lasten

167
00:08:36,220 --> 00:08:37,470
kiinnike aakkosia.

168
00:08:37,470 --> 00:08:38,929

169
00:08:38,929 --> 00:08:42,020
Joten ensimmäinen asia, saatat olla
ihmettelevät, miksi on AAKKOSITTAIN

170
00:08:42,020 --> 00:08:44,660
ed määritelty 27?

171
00:08:44,660 --> 00:08:47,900
No, muistaa, että olemme menossa tarvitsevat
voidaan käsittely heittomerkki.

172
00:08:47,900 --> 00:08:51,910
Niin, että tulee olemaan jokseenkin
erikoistapaus koko tähän ohjelmaan.

173
00:08:51,910 --> 00:08:54,710
>> Nyt muista miten triellä
todella toimii.

174
00:08:54,710 --> 00:08:59,380
Sanotaan olemme indeksointi sana
"Kissat". Sitten juuresta triestä,

175
00:08:59,380 --> 00:09:02,610
olemme menossa katsomaan lapsia
array, ja olemme menossa katsomaan

176
00:09:02,610 --> 00:09:08,090
indeksi, joka vastaa kirjeen
C. Niin että on indeksoitu 2.

177
00:09:08,090 --> 00:09:11,530
Niin sillä, että tahto
antaa meille uuden solmun.

178
00:09:11,530 --> 00:09:13,820
Ja sitten me työskennellä, että solmu.

179
00:09:13,820 --> 00:09:17,770
>> Joten koska solmu, olemme jälleen kerran
menossa katsomaan lapsia array.

180
00:09:17,770 --> 00:09:22,110
Ja aiomme tarkastella indeksi nolla
vastaamaan kissan.

181
00:09:22,110 --> 00:09:27,170
Niin sitten me aiomme mennä, että solmu,
ja koska solmu aiomme

182
00:09:27,170 --> 00:09:31,090
katsomaan lopussa se vastaa
T. Ja siirrymme että solmuun,

183
00:09:31,090 --> 00:09:35,530
Lopuksi, olemme täysin huolta
kautta sana "kissa." Ja nyt bool

184
00:09:35,530 --> 00:09:40,960
sana on tarkoitus ilmoittaa, onko
Tämän tiettyä sanaa on oikeastaan ​​sana.

185
00:09:40,960 --> 00:09:43,470
>> Joten miksi me tarvitsemme, että erikoistapaus?

186
00:09:43,470 --> 00:09:47,700
No mitä sanan "katastrofi"
on meidän sanakirja, mutta

187
00:09:47,700 --> 00:09:50,150
sana "kissa" ei ole?

188
00:09:50,150 --> 00:09:54,580
Niin ja katsomatta, jos sana "kissa"
on meidän sanakirja, olemme

189
00:09:54,580 --> 00:09:59,970
menossa onnistuneesti katsoa läpi
indeksit C--T alueella solmussa.

190
00:09:59,970 --> 00:10:04,290
Mutta se on vain siksi katastrofi
tapahtui luoda solmut matkalla

191
00:10:04,290 --> 00:10:07,190
C-A-T, aina
sanan lopussa.

192
00:10:07,190 --> 00:10:12,020
Joten bool sanaa käytetään osoittamaan, onko
tässä paikassa

193
00:10:12,020 --> 00:10:14,310
todella osoittaa sana.

194
00:10:14,310 --> 00:10:15,140
>> Selvä.

195
00:10:15,140 --> 00:10:19,310
Joten nyt me tiedämme, mitä se triestä on
tulee näyttämään, katsokaamme

196
00:10:19,310 --> 00:10:20,730
kuormafunktio.

197
00:10:20,730 --> 00:10:24,610
Joten kuorma aio palata bool
Jos me oikein tai

198
00:10:24,610 --> 00:10:26,720
tuloksetta ladattu sanakirja.

199
00:10:26,720 --> 00:10:30,460
Ja tämä tulee olemaan sanakirja
että haluamme ladata.

200
00:10:30,460 --> 00:10:33,930
>> Joten ensimmäinen asia, olemme vain avata
up, joka sanakirjan lukemiseen.

201
00:10:33,930 --> 00:10:36,160
Ja meidän täytyy varmistaa,
emme onnistu.

202
00:10:36,160 --> 00:10:39,580
Joten jos sanakirjassa ei ollut
onnistuneesti avattu, se palaa

203
00:10:39,580 --> 00:10:42,400
null, jolloin olemme
aio palata vääriä.

204
00:10:42,400 --> 00:10:47,230
Mutta olettaen, että se onnistui
avattu, niin voimme todella lukea

205
00:10:47,230 --> 00:10:48,220
kautta sanakirja.

206
00:10:48,220 --> 00:10:50,880
>> Joten ensimmäinen asia aiomme
haluat tehdä, on meillä on tämä

207
00:10:50,880 --> 00:10:52,500
globaali muuttuja root.

208
00:10:52,500 --> 00:10:56,190
Nyt root tulee olemaan solmu *.

209
00:10:56,190 --> 00:10:59,760
Se kärkeen triestä että olemme
aiotaan iteroimalla läpi.

210
00:10:59,760 --> 00:11:02,660
Joten ensimmäinen asia, että olemme menossa
halua tehdä, on jakaa

211
00:11:02,660 --> 00:11:04,140
muisti meidän root.

212
00:11:04,140 --> 00:11:07,980
Huomaa, että käytämme calloc
toiminto, joka on periaatteessa sama

213
00:11:07,980 --> 00:11:11,500
kuten malloc funktio, paitsi se on
taattu palata jotain, joka on

214
00:11:11,500 --> 00:11:13,180
täysin nollataan.

215
00:11:13,180 --> 00:11:17,290
Jos siis käytetään malloc, meidän olisi
käydä läpi kaikki osoittimet meidän

216
00:11:17,290 --> 00:11:20,160
solmu, ja varmista, että
he kaikki null.

217
00:11:20,160 --> 00:11:22,710
Joten calloc tekee sen meille.

218
00:11:22,710 --> 00:11:26,330
>> Nyt aivan kuten malloc, meidän täytyy tehdä
Varmista, että jako oli oikeastaan

219
00:11:26,330 --> 00:11:27,520
onnistunut.

220
00:11:27,520 --> 00:11:29,990
Jos tämä palasi null, meidän
täytyy sulkea tai sanakirja

221
00:11:29,990 --> 00:11:32,100
tiedostoon ja palauttaa false.

222
00:11:32,100 --> 00:11:36,835
Joten olettaen että jako on
onnistunut, aiomme käyttää solmuun *

223
00:11:36,835 --> 00:11:40,270
kursorin kerrata kautta triellä.

224
00:11:40,270 --> 00:11:43,890
Joten meidän juuret koskaan muutu,
mutta aiomme käyttää kohdistin

225
00:11:43,890 --> 00:11:47,875
itse mennä solmusta toiseen.

226
00:11:47,875 --> 00:11:50,940
>> Joten tässä silmukan Luemme
kautta sanastotiedostoa.

227
00:11:50,940 --> 00:11:53,670
Ja käytämme fgetc.

228
00:11:53,670 --> 00:11:56,290
Fgetc aikoo napata yhden
hahmo tiedoston.

229
00:11:56,290 --> 00:11:59,370
Aiomme jatkaa tarttumalla
merkkiä vaikka emme pääse

230
00:11:59,370 --> 00:12:01,570
tiedoston loppuun.

231
00:12:01,570 --> 00:12:03,480
>> On olemassa kaksi tapausta meidän täytyy käsitellä.

232
00:12:03,480 --> 00:12:06,610
Ensimmäinen, jos merkki
ei ollut uusi rivi.

233
00:12:06,610 --> 00:12:10,450
Joten me tiedämme, jos se oli uusi linja, niin
aiomme siirtyä uuden sanan.

234
00:12:10,450 --> 00:12:15,240
Mutta jos se ei ollut uusi linja, niin
Tässä haluamme selvittää

235
00:12:15,240 --> 00:12:18,380
index aiomme indeksinä
lapsissa array, joka

236
00:12:18,380 --> 00:12:19,810
me katsoimme ennen.

237
00:12:19,810 --> 00:12:23,880
>> Joten, kuten sanoin aiemmin, meidän täytyy
erikoistapaus heittomerkki.

238
00:12:23,880 --> 00:12:26,220
Huomaa käytämme ternäärisen
operaattori täällä.

239
00:12:26,220 --> 00:12:29,580
Menemme siis lukea tätä, jos
merkki luemme oli

240
00:12:29,580 --> 00:12:35,330
heittomerkki, niin aiomme asettaa
index = "AAKKOSITTAIN" -1, joka

241
00:12:35,330 --> 00:12:37,680
olla indeksi 26.

242
00:12:37,680 --> 00:12:41,130
>> Else, jos se ei ollut heittomerkki, siellä
aiomme asettaa indeksin

243
00:12:41,130 --> 00:12:43,760
yhtä suuri kuin c -.

244
00:12:43,760 --> 00:12:49,030
Joten muistakaa takaisin aiemmin p-sarjaa,
c - ei aio antaa meille

245
00:12:49,030 --> 00:12:53,410
aakkosjärjestyksessä C. Joten jos
C on kirjain, tämä tulee

246
00:12:53,410 --> 00:12:54,700
antaa meille indeksi nolla.

247
00:12:54,700 --> 00:12:58,120
Kirjain B, se antaa
meille indeksi 1, ja niin edelleen.

248
00:12:58,120 --> 00:13:03,010
>> Joten tämä antaa meille indeksinä
lasten array että haluamme.

249
00:13:03,010 --> 00:13:08,890
Nyt jos tämä indeksi on tällä hetkellä null
lapset, se tarkoittaa, että solmu

250
00:13:08,890 --> 00:13:11,830
ei vielä ole
alkaen, että polku.

251
00:13:11,830 --> 00:13:15,160
Joten meidän täytyy kohdentaa
solmun polun.

252
00:13:15,160 --> 00:13:16,550
Sitähän me teemme täällä.

253
00:13:16,550 --> 00:13:20,690
>> Joten aiomme taas käyttää calloc
toiminto, jotta meidän ei tarvitse

254
00:13:20,690 --> 00:13:22,880
nolla pois kaikki osoittimet.

255
00:13:22,880 --> 00:13:27,240
Ja me taas täytyy tarkistaa
että calloc ei epäonnistunut.

256
00:13:27,240 --> 00:13:30,700
Jos calloc ei onnistu, meidän
purkaa kaiken, sulkea

257
00:13:30,700 --> 00:13:32,820
sanakirja, ja palauttaa false.

258
00:13:32,820 --> 00:13:40,050
Niin olettaen, että se ei ole jättänyt, niin
tämä luo uuden lapsen meille.

259
00:13:40,050 --> 00:13:41,930
Ja sitten menemme että lapsi.

260
00:13:41,930 --> 00:13:44,960
Meidän osoitin kerrata
tuolle lapselle.

261
00:13:44,960 --> 00:13:49,330
>> Nyt jos tämä ei null aluksi,
Sitten osoitin voi vain kerrata

262
00:13:49,330 --> 00:13:52,590
alas, että lapsi ei itse
ottaa jakaa mitään.

263
00:13:52,590 --> 00:13:56,730
Tämä on tapaus, jossa ensin tapahtui
jakaa sana "kissa." Ja

264
00:13:56,730 --> 00:14:00,330
se tarkoittaa, että kun menemme kohdentaa
"Katastrofi", meidän ei tarvitse luoda

265
00:14:00,330 --> 00:14:01,680
solmut C-A-T uudelleen.

266
00:14:01,680 --> 00:14:04,830
Ne ovat jo olemassa.

267
00:14:04,830 --> 00:14:06,080
>> Mikä on tämä muuta?

268
00:14:06,080 --> 00:14:10,480
Tämä on sairaus, jossa C
kenoviiva n, missä c on uusi rivi.

269
00:14:10,480 --> 00:14:13,710
Tämä tarkoittaa, että olemme onnistuneet
valmistunut sana.

270
00:14:13,710 --> 00:14:16,860
Nyt mitä haluamme tehdä, kun me
suorittanut sana?

271
00:14:16,860 --> 00:14:21,100
Aiomme käyttää tätä sanaa alalla
sisällä meidän struct solmu.

272
00:14:21,100 --> 00:14:23,390
Haluamme asettaa, että totta.

273
00:14:23,390 --> 00:14:27,150
Niin, joka osoittaa, että tämä solmu
osoittaa onnistuneen

274
00:14:27,150 --> 00:14:29,250
sana, todellinen sana.

275
00:14:29,250 --> 00:14:30,940
>> Nyt asetettu, että totta.

276
00:14:30,940 --> 00:14:35,150
Haluamme palauttaa meidän kohdistin pisteeseen
alkuun trien uudelleen.

277
00:14:35,150 --> 00:14:40,160
Ja lopuksi, kasvattaa meidän sanakirja
koko, koska löysimme toisen teoksen.

278
00:14:40,160 --> 00:14:43,230
Joten aiomme pitää tehdä, että
lukeminen merkki merkiltä,

279
00:14:43,230 --> 00:14:49,150
rakentamalla uusia solmuja meidän triessä ja
jokaisen sanan sanakirjasta, kunnes

280
00:14:49,150 --> 00:14:54,020
me lopulta saavuttaa C! = EOF, jossa
tapauksessa meidän murtautumaan ulos tiedoston.

281
00:14:54,020 --> 00:14:57,050
>> Nyt on kaksi tapausta alle
jotka olisimme osuma EOF.

282
00:14:57,050 --> 00:15:00,980
Ensimmäinen on, jos siellä oli virhe
lukemisen tiedoston.

283
00:15:00,980 --> 00:15:03,470
Joten jos oli virhe, me
täytyy tehdä tyypillinen.

284
00:15:03,470 --> 00:15:06,460
Purkaa kaiken, lähellä
tiedosto, palauttaa false.

285
00:15:06,460 --> 00:15:09,810
Olettaen ei ollut virhe, joka
tarkoittaa vain me itse osui lopussa

286
00:15:09,810 --> 00:15:13,750
tiedosto, jolloin suljemme
tiedostoon ja palauttaa totta, sillä me

287
00:15:13,750 --> 00:15:17,330
ladattu onnistuneesti sanakirja
meidän trie.

288
00:15:17,330 --> 00:15:20,170
>> Joten nyt Katsotaanpa tarkistaa tarkistaa.

289
00:15:20,170 --> 00:15:25,156
Tarkasteltaessa toiminnanvalvonnassa, näemme
että tarkastus aio palata bool.

290
00:15:25,156 --> 00:15:29,680
Se palauttaa true, jos tämä sana, se on
siirrellään on meidän triessä.

291
00:15:29,680 --> 00:15:32,110
Se palauttaa false muuten.

292
00:15:32,110 --> 00:15:36,050
Joten miten voit selvittää,
tämä sana on meidän triestä?

293
00:15:36,050 --> 00:15:40,190
>> Näemme tässä, että aivan kuten ennen,
aiomme käyttää kohdistin kerrata

294
00:15:40,190 --> 00:15:41,970
kautta trie.

295
00:15:41,970 --> 00:15:46,600
Nyt olemme menossa kerrata
yli koko sanan.

296
00:15:46,600 --> 00:15:50,620
Joten iteroimalla yli sana olemme aiemmin,
aiomme selvittää

297
00:15:50,620 --> 00:15:56,400
indeksinä lapset array, joka
vastaa sanaa teline I. Joten tämä

298
00:15:56,400 --> 00:15:59,670
tulee näyttämään täsmälleen samalta kuin
kuormitus, jossa jos sana [i]

299
00:15:59,670 --> 00:16:03,310
on heittomerkki, niin haluamme
käyttää indeksi "AAKKOSITTAIN" - 1.

300
00:16:03,310 --> 00:16:05,350
Koska olemme päättäneet, että että
on, jos aiomme säilyttää

301
00:16:05,350 --> 00:16:07,100
heittomerkit.

302
00:16:07,100 --> 00:16:11,780
>> Else aiomme käyttää kahta alempaa sanaa
kiinnike I. Joten muistakaa, että sana voi

303
00:16:11,780 --> 00:16:13,920
on mielivaltainen arvo.

304
00:16:13,920 --> 00:16:17,540
Ja niin me haluamme varmistaa, että olemme
käyttämällä pieniä versio asioista.

305
00:16:17,540 --> 00:16:21,920
Ja vähennä siitä "" kerran
taas antaa meille aakkosjärjestyksessä

306
00:16:21,920 --> 00:16:23,880
asemaa tämän merkin.

307
00:16:23,880 --> 00:16:27,680
Niin, että tulee olemaan meidän indeksi
osaksi lasten array.

308
00:16:27,680 --> 00:16:32,420
>> Ja nyt jos indeksinä lapsia
matriisi on nolla, se tarkoittaa, että me

309
00:16:32,420 --> 00:16:34,990
voi enää jatkaa iteroimalla
alas meidän trie.

310
00:16:34,990 --> 00:16:38,870
Jos näin on, tämä sana voi
mahdollisesti olla meidän triessä.

311
00:16:38,870 --> 00:16:42,340
Koska jos se olisi, että olisi
tarkoittaa ei olisi polku

312
00:16:42,340 --> 00:16:43,510
alas, että sana.

313
00:16:43,510 --> 00:16:45,290
Ja et koskaan kohdata null.

314
00:16:45,290 --> 00:16:47,850
Joten kohtaaminen null, palaamme vääriä.

315
00:16:47,850 --> 00:16:49,840
Sanaa ei ole sanakirjassa.

316
00:16:49,840 --> 00:16:53,660
Jos se ei ole tyhjä, niin olemme
tulee jatkumaan iteroimalla.

317
00:16:53,660 --> 00:16:57,220
>> Menemme siis siellä kohdistin
huomauttaa, että erityisesti

318
00:16:57,220 --> 00:16:59,760
solmu, että indeksi.

319
00:16:59,760 --> 00:17:03,150
Meidän pitää tehdä, että koko
koko sana, olettaen

320
00:17:03,150 --> 00:17:03,950
emme koskaan lyönyt null.

321
00:17:03,950 --> 00:17:07,220
Se tarkoittaa, että pystyimme saamaan läpi
koko sanan ja löytää

322
00:17:07,220 --> 00:17:08,920
solmu meidän yrittää.

323
00:17:08,920 --> 00:17:10,770
Mutta emme ole aivan vielä valmis.

324
00:17:10,770 --> 00:17:12,290
>> Emme halua vain palata totta.

325
00:17:12,290 --> 00:17:14,770
Haluamme palata kursori> sana.

326
00:17:14,770 --> 00:17:18,980
Koska muistan taas, on "kissa" ei
meidän sanakirja, ja "katastrofi"

327
00:17:18,980 --> 00:17:22,935
on, niin me onnistuneesti saamme
kautta sana "kissa." Mutta osoitin

328
00:17:22,935 --> 00:17:25,760
sana on väärä ja ei ole totta.

329
00:17:25,760 --> 00:17:30,930
Joten palaamme kursori tarkoittava sana
onko tämä solmu on todella sana.

330
00:17:30,930 --> 00:17:32,470
Ja siinä se lähtöselvitykseen.

331
00:17:32,470 --> 00:17:34,250
>> Joten tarkistaa koko.

332
00:17:34,250 --> 00:17:37,350
Joten koko tulee olemaan melko helppoa
koska muistaa kuormitus, olemme

333
00:17:37,350 --> 00:17:41,430
monesko sanakirja koko
jokainen sana, että törmäämme.

334
00:17:41,430 --> 00:17:45,350
Joten koko on juuri menossa
palata sanakirjan koko.

335
00:17:45,350 --> 00:17:47,390
Ja se on siinä.

336
00:17:47,390 --> 00:17:50,590
>> Joten lopuksi olemme purkaa.

337
00:17:50,590 --> 00:17:55,100
Joten purkaa, aiomme käyttää
rekursiivinen funktio itse tehdä kaikki

338
00:17:55,100 --> 00:17:56,530
työn meille.

339
00:17:56,530 --> 00:17:59,340
Joten meidän tehtävämme on menossa
voidaan kutsua unloader.

340
00:17:59,340 --> 00:18:01,650
Mitä unloader aiot tehdä?

341
00:18:01,650 --> 00:18:06,580
Näemme tässä, että purkaimen on menossa
kerrata hoitaakseen kaikki lasten

342
00:18:06,580 --> 00:18:08,410
tässä solmussa.

343
00:18:08,410 --> 00:18:11,750
Ja jos lapsi solmu ei ole
null, niin aiomme

344
00:18:11,750 --> 00:18:13,730
purkaa lapsi solmu.

345
00:18:13,730 --> 00:18:18,010
>> Joten tämä on sinulle rekursiivisesti purkaa
kaikki lapsemme.

346
00:18:18,010 --> 00:18:21,080
Kun olemme varmoja, että kaikki lapsemme
on purettu, niin me

347
00:18:21,080 --> 00:18:25,210
voi vapauttaa itsemme, niin
purkaa itseämme.

348
00:18:25,210 --> 00:18:29,460
Tämä toimii rekursiivisesti
purkaa koko triessä.

349
00:18:29,460 --> 00:18:32,850
Ja sitten kun se on tehty,
voimme vain palata totta.

350
00:18:32,850 --> 00:18:34,210
Kevennys ei voi epäonnistua.

351
00:18:34,210 --> 00:18:35,710
Me vain vapauttaa asioita.

352
00:18:35,710 --> 00:18:38,870
Joten kun olemme tehneet vapauttaa
kaiken, return true.

353
00:18:38,870 --> 00:18:40,320
Ja se on siinä.

354
00:18:40,320 --> 00:18:41,080
Nimeni on Rob.

355
00:18:41,080 --> 00:18:42,426
Ja tämä oli speller.

356
00:18:42,426 --> 00:18:47,830
>> [Musiikki soi]