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

2
00:00:00,530 --> 00:00:03,070
>> SPEAKER 1: Annetaan
tämä ratkaisu yrittää.

3
00:00:03,070 --> 00:00:07,130
Joten katsomaan mitä
Struct solmu näyttää.

4
00:00:07,130 --> 00:00:11,040
Täällä näemme aiomme olla
Bool Word ja Struct solmun tähti

5
00:00:11,040 --> 00:00:12,990
Lapset teline aakkoset.

6
00:00:12,990 --> 00:00:18,720
Joten ensimmäinen asia, saatat olla miettimättä,
miksi aakkoset hash määritelty 27?

7
00:00:18,720 --> 00:00:22,540
No, muistaa, että olemme menossa tarvitsevat
voidaan käsittely heittomerkki, joten

8
00:00:22,540 --> 00:00:25,610
että tulee olemaan jokseenkin erityinen
tapauksessa koko tähän ohjelmaan.

9
00:00:25,610 --> 00:00:28,780
>> OK, nyt muistan kuinka
Trie todella toimii.

10
00:00:28,780 --> 00:00:33,420
Sanotaan olemme indeksointi sana kissat,
sitten juuri meidän Trie,

11
00:00:33,420 --> 00:00:36,670
olemme menossa katsomaan lapsia
array, ja olemme menossa katsomaan

12
00:00:36,670 --> 00:00:42,250
indeksi, joka vastaa kirjeen
C. Jotta olisi indeksin kaksi.

13
00:00:42,250 --> 00:00:46,400
Niin sillä, että se antaa meille
uusi solmu, ja sitten me

14
00:00:46,400 --> 00:00:47,880
työskennellä, että solmu.

15
00:00:47,880 --> 00:00:51,830
>> Joten koska solmu, olemme jälleen kerran
menossa katsomaan Children array,

16
00:00:51,830 --> 00:00:56,170
ja olemme menossa katsomaan indeksi nolla
vastaamaan kissan.

17
00:00:56,170 --> 00:01:01,240
Niin sitten me aiomme mennä, että solmu,
ja koska solmu, aiomme

18
00:01:01,240 --> 00:01:05,170
tarkastella indeksi, joka vastaa
T. Ja siirrymme että solmuun,

19
00:01:05,170 --> 00:01:09,590
Lopuksi, olemme täysin huolta
kautta sana kissa, ja nyt Bool

20
00:01:09,590 --> 00:01:15,020
Sana on tarkoitus ilmoittaa, onko
Tämän tiettyä sanaa on oikeastaan ​​sana.

21
00:01:15,020 --> 00:01:17,530
>> Joten miksi me tarvitsemme, että erikoistapaus?

22
00:01:17,530 --> 00:01:21,680
No, mitä jos sana katastrofi
on meidän sanakirja, mutta

23
00:01:21,680 --> 00:01:24,120
sana kissa ei ole?

24
00:01:24,120 --> 00:01:29,030
Joten katsomatta, jos sana kissa on
meidän sanakirja, aiomme

25
00:01:29,030 --> 00:01:34,880
onnistuneesti katsoa läpi indeksit
C--T ja saavuttaa solmu, mutta se on

26
00:01:34,880 --> 00:01:39,760
vain siksi katastrofi tapahtui
luoda solmujen matkalla C-A-T kaikki

27
00:01:39,760 --> 00:01:41,250
tapa sanan loppuun.

28
00:01:41,250 --> 00:01:46,520
Joten Bool sanaa käytetään ilmoittaa, onko
tässä paikassa todella

29
00:01:46,520 --> 00:01:48,370
ilmaisee sana.

30
00:01:48,370 --> 00:01:52,920
>> Okei, joten nyt, että me tiedämme, mitä
Triestä on menossa näyttämään, katsotaanpa

31
00:01:52,920 --> 00:01:54,800
klo Load-toiminto.

32
00:01:54,800 --> 00:01:58,670
Joten Load aikoo palata Bool
Jos me oikein tai

33
00:01:58,670 --> 00:02:03,020
tuloksetta ladattu sanakirja ja
tämä tulee olemaan sanakirja

34
00:02:03,020 --> 00:02:04,520
että haluamme ladata.

35
00:02:04,520 --> 00:02:08,310
Joten ensimmäinen asia aiomme tehdä, on avoin
up, joka sanakirjan lukemiseen.

36
00:02:08,310 --> 00:02:12,060
Meidän täytyy varmistaa, että meillä ei epäonnistunut,
joten jos sanakirjaa ei ollut

37
00:02:12,060 --> 00:02:15,280
onnistuneesti avattu, se palaa
Ei, jolloin aiomme

38
00:02:15,280 --> 00:02:16,340
palata False.

39
00:02:16,340 --> 00:02:21,290
Mutta olettaen, että se onnistui
avattu, niin voimme todella lukea

40
00:02:21,290 --> 00:02:22,310
kautta sanakirja.

41
00:02:22,310 --> 00:02:24,940
>> Joten ensimmäinen asia aiomme
haluat tehdä, on meillä on tämä

42
00:02:24,940 --> 00:02:26,560
globaali muuttuja root.

43
00:02:26,560 --> 00:02:30,250
Nyt, juuri tulee olemaan solmu tähti.

44
00:02:30,250 --> 00:02:33,830
Se kärkeen Trie että olemme
aiotaan iteroimalla läpi.

45
00:02:33,830 --> 00:02:38,200
Joten ensimmäinen asia aiomme haluavat
tehdä, on varata muistia meidän root.

46
00:02:38,200 --> 00:02:42,040
>> Huomaa, että käytämme calloc
toiminto, joka on periaatteessa sama

47
00:02:42,040 --> 00:02:45,560
kuten malloc funktio, paitsi se on
taattu palata jotain, joka on

48
00:02:45,560 --> 00:02:47,240
täysin nollataan.

49
00:02:47,240 --> 00:02:51,350
Jos siis käytetään malloc, meidän olisi
käydä läpi kaikki osoittimet meidän

50
00:02:51,350 --> 00:02:54,220
solmu ja varmista, että
he kaikki null.

51
00:02:54,220 --> 00:02:56,780
Joten calloc tekee sen meille.

52
00:02:56,780 --> 00:03:00,390
>> Nyt, aivan kuten malloc, meidän täytyy tehdä
Varmista, että jako on oikeastaan

53
00:03:00,390 --> 00:03:01,580
onnistunut.

54
00:03:01,580 --> 00:03:04,060
Jos tämä palasi null, meidän
täytyy sulkea sanakirjastamme

55
00:03:04,060 --> 00:03:06,170
tiedostoon ja palauttaa False.

56
00:03:06,170 --> 00:03:11,040
Joten olettaen jako on
onnistunut, aiomme käyttää solmuun

57
00:03:11,040 --> 00:03:14,340
tähden Cursor kerrata
kautta Trie.

58
00:03:14,340 --> 00:03:17,950
Joten meidän root koskaan muutu,
mutta aiomme käyttää kursori

59
00:03:17,950 --> 00:03:20,770
itse mennä solmusta toiseen.

60
00:03:20,770 --> 00:03:25,000
>> Okei, joten tässä käytettäessä loop olemme
käsittelyn kautta sanastotiedostoa,

61
00:03:25,000 --> 00:03:26,965
ja käytämme klo fgetc.

62
00:03:26,965 --> 00:03:30,360
Joten fgetc aikoo napata yhden
hahmo tiedoston.

63
00:03:30,360 --> 00:03:33,430
Aiomme jatkaa tarttumalla
merkkiä vaikka emme pääse

64
00:03:33,430 --> 00:03:37,540
tiedoston loppuun, joten on
Kahdessa tapauksessa meidän täytyy käsitellä.

65
00:03:37,540 --> 00:03:41,640
Ensimmäinen, jos merkki ei ollut
Uusi linja, joten tiedämme, jos se oli uusi

66
00:03:41,640 --> 00:03:44,480
linja, niin aiomme
siirtyä uuden sanan.

67
00:03:44,480 --> 00:03:49,300
Mutta jos se ei ollut uusi linja, niin
täällä, haluamme selvittää

68
00:03:49,300 --> 00:03:52,440
index aiomme indeksinä
in Children array, joka

69
00:03:52,440 --> 00:03:53,890
me katsoimme ennen.

70
00:03:53,890 --> 00:03:57,950
>> Niin kuin aiemmin sanoin, meidän täytyy
erikoistapaus heittomerkki.

71
00:03:57,950 --> 00:04:01,040
Huomaa käytämme kolmen komponentin operaattori
täällä, joten aiomme lukea

72
00:04:01,040 --> 00:04:05,500
Tässä ikään kuin merkki luemme oli
heittomerkki, niin aiomme

73
00:04:05,500 --> 00:04:11,740
asettaa indeksi on aakkoset miinus
1, joka tulee indeksi 26.

74
00:04:11,740 --> 00:04:15,190
Else, jos se ei pilkullisilla
Sitten aiomme asettaa indeksin

75
00:04:15,190 --> 00:04:17,820
yhtä suuri kuin c miinus.

76
00:04:17,820 --> 00:04:23,090
Joten muistakaa takaisin edelliseen p sarjaa,
c miinus aikoo antaa meille

77
00:04:23,090 --> 00:04:27,470
aakkosjärjestyksessä c, joten jos
c on kirjain, se

78
00:04:27,470 --> 00:04:28,770
antaa meille indeksi nolla.

79
00:04:28,770 --> 00:04:32,180
Kirjain B, se antaisi
meille indeksi 1, ja niin edelleen.

80
00:04:32,180 --> 00:04:37,070
>> Joten tämä antaa meille indeksinä
Lapset array että haluamme.

81
00:04:37,070 --> 00:04:42,540
Nyt, jos tämä indeksi on tällä hetkellä null
Lapset array, se tarkoittaa, että

82
00:04:42,540 --> 00:04:47,470
solmu ei tällä hetkellä ole alkaen
että polku, joten meidän on osoitettava

83
00:04:47,470 --> 00:04:49,220
solmu polun.

84
00:04:49,220 --> 00:04:50,610
Sitähän me teemme täällä.

85
00:04:50,610 --> 00:04:54,650
Joten aiomme, uudelleen, käytä calloc
toimii niin, että meillä ei ole

86
00:04:54,650 --> 00:05:00,130
hakeutua pois kaikki osoittimet, ja me,
uudelleen, on tarkistettava, että calloc

87
00:05:00,130 --> 00:05:01,300
ei onnistu.

88
00:05:01,300 --> 00:05:04,760
Jos calloc ei onnistu, meidän
purkaa kaiken, sulkea

89
00:05:04,760 --> 00:05:06,880
sanakirja, ja palauttaa False.

90
00:05:06,880 --> 00:05:14,110
>> Niin olettaen, että se ei ole jättänyt, niin
tämä luo uuden lapsen meille,

91
00:05:14,110 --> 00:05:16,000
ja sitten menemme että lapsi.

92
00:05:16,000 --> 00:05:19,030
Meidän osoitin kerrata
tuolle lapselle.

93
00:05:19,030 --> 00:05:23,390
Nyt, jos tämä ei null aluksi,
Sitten osoitin voi vain kerrata

94
00:05:23,390 --> 00:05:26,650
alas, että lapsi ei itse
ottaa jakaa mitään.

95
00:05:26,650 --> 00:05:30,790
Tämä on tapaus, jossa ensin tapahtui
jakaa sanan kissa, ja

96
00:05:30,790 --> 00:05:34,390
se tarkoittaa, että kun menemme kohdentaa
katastrofi, meidän ei tarvitse luoda

97
00:05:34,390 --> 00:05:35,720
solmut C-A-T uudelleen.

98
00:05:35,720 --> 00:05:37,620
Ne ovat jo olemassa.

99
00:05:37,620 --> 00:05:40,140
>> OK, niin mikä on tämän Else?

100
00:05:40,140 --> 00:05:44,600
Tämä on sairaus, jossa C
kenoviiva n, missä c on uusi rivi.

101
00:05:44,600 --> 00:05:47,780
Tämä tarkoittaa, että olemme onnistuneet
valmistunut sana.

102
00:05:47,780 --> 00:05:51,020
Nyt, mitä haluamme tehdä, kun me
suorittanut sana?

103
00:05:51,020 --> 00:05:55,250
Aiomme käyttää tätä sanaa alalla
sisällä meidän Struct solmun.

104
00:05:55,250 --> 00:06:00,570
>> Haluamme asettaa, että True, jotta
osoittaa, että tämä solmu ilmaisee

105
00:06:00,570 --> 00:06:03,320
menestyvä sana Varsinainen sana.

106
00:06:03,320 --> 00:06:05,050
Nyt asetettu, että True.

107
00:06:05,050 --> 00:06:09,210
Haluamme palauttaa meidän kohdistin pisteeseen
alkuun Trie uudelleen.

108
00:06:09,210 --> 00:06:13,510
Ja lopuksi, kasvattaa meidän sanakirja
koko koska löysimme toisen sanan.

109
00:06:13,510 --> 00:06:16,450
>> Kunnossa, joten aiomme pitää tehdä
että lukeminen merkin

110
00:06:16,450 --> 00:06:21,960
merkki, rakentamalla uusia solmuja
meidän Trie ja jokaisen sanan

111
00:06:21,960 --> 00:06:26,810
sanakirja, kunnes lopulta saavuttaa c
vastaa EOF, jolloin, rikomme

112
00:06:26,810 --> 00:06:28,100
pois tiedoston.

113
00:06:28,100 --> 00:06:31,110
Nyt on kaksi tapausta alle
jotka olisimme osuma EOF.

114
00:06:31,110 --> 00:06:35,680
Ensimmäinen on, jos siellä oli virhe
lukemisen tiedosto, joten jos oli

115
00:06:35,680 --> 00:06:39,280
virhe, meidän täytyy tehdä tyypillinen
purkaa kaiken, sulje tiedosto,

116
00:06:39,280 --> 00:06:40,520
palata False.

117
00:06:40,520 --> 00:06:43,870
Olettaen ei ollut virhe, joka
tarkoittaa vain me itse osui lopussa

118
00:06:43,870 --> 00:06:47,820
tiedosto, jolloin suljemme
tiedostoon ja palauttaa True koska meillä

119
00:06:47,820 --> 00:06:51,010
ladattu onnistuneesti sanakirja
meidän Trie.

120
00:06:51,010 --> 00:06:54,240
>> Okei, joten nyt katsotaanpa
tutustu Tarkista.

121
00:06:54,240 --> 00:06:58,780
Tarkasteltaessa Check-toiminto, näemme
että Tarkista aikoo palata Bool.

122
00:06:58,780 --> 00:07:03,740
Se palauttaa True, jos tämä sana, se on
siirrellään on meidän Trie.

123
00:07:03,740 --> 00:07:06,170
Se palauttaa muuten False.

124
00:07:06,170 --> 00:07:10,110
>> Joten miten aiomme selvittää
tämä sana on meidän Trie?

125
00:07:10,110 --> 00:07:14,270
Näemme tässä, että aivan kuten ennen,
aiomme käyttää kohdistin kerrata

126
00:07:14,270 --> 00:07:16,010
kautta Trie.

127
00:07:16,010 --> 00:07:20,650
Nyt tässä, me aiomme kerrata
yli koko sanan.

128
00:07:20,650 --> 00:07:24,680
Joten iteroimalla yli sana olemme
kulunut, aiomme selvittää

129
00:07:24,680 --> 00:07:29,280
indeksinä Lapset array, joka
vastaa sana kiinnike i.

130
00:07:29,280 --> 00:07:34,150
Joten tämä tulee näyttää täsmälleen samalta kuin
Kuormitus, jossa jos sana kiinnike i on

131
00:07:34,150 --> 00:07:38,110
heittomerkki, niin haluamme käyttää indeksiä
aakkoset miinus 1 koska me määritetty

132
00:07:38,110 --> 00:07:41,160
että on mihin olemme menossa
tallentaa heittomerkit.

133
00:07:41,160 --> 00:07:44,440
>> Else aiomme käyttää tolower
sana kiinnike i.

134
00:07:44,440 --> 00:07:48,270
Niin muista, että sana voi olla mielivaltainen
arvo, ja niin me

135
00:07:48,270 --> 00:07:51,590
haluat varmistaa, että käytämme
pieniä versio asioista.

136
00:07:51,590 --> 00:07:55,300
Ja vähennä siitä pieniä
ja, jälleen kerran, antaa meille

137
00:07:55,300 --> 00:07:57,940
aakkosjärjestyksessä
kyseisen merkin.

138
00:07:57,940 --> 00:08:01,740
Niin, että tulee olemaan meidän indeksi
osaksi Lapset array.

139
00:08:01,740 --> 00:08:06,480
>> Ja nyt, jos se indeksinä Lapset
matriisi on nolla, se tarkoittaa, että me

140
00:08:06,480 --> 00:08:09,050
voi enää jatkaa iteroimalla
alas meidän Trie.

141
00:08:09,050 --> 00:08:13,320
Jos näin on, tämä sana voi
mahdollisesti olla meidän Trie, koska jos se

142
00:08:13,320 --> 00:08:18,000
oli, se merkitsisi olisi
polku alas, että sana, ja olisit

143
00:08:18,000 --> 00:08:19,350
koskaan kohtaat null.

144
00:08:19,350 --> 00:08:21,910
Joten kohtaaminen null, palaamme False.

145
00:08:21,910 --> 00:08:23,810
Sanaa ei ole sanakirjassa.

146
00:08:23,810 --> 00:08:28,200
Jos se ei ole tyhjä, niin aiomme
jatkaa iteroimalla, joten olemme menossa

147
00:08:28,200 --> 00:08:33,150
päivittämään kursorin osoittamaan, että
Erityisesti solmu tuohon indeksi.

148
00:08:33,150 --> 00:08:36,659
>> Joten meidän pitää tehdä, että koko
koko sanan.

149
00:08:36,659 --> 00:08:40,630
Olettaen emme koskaan lyönyt null, että välineet
pystyimme saamaan läpi koko

150
00:08:40,630 --> 00:08:44,840
maailmaa ja löytää solmun meidän Trie,
mutta emme ole aivan vielä valmis.

151
00:08:44,840 --> 00:08:46,350
Emme halua vain palata True.

152
00:08:46,350 --> 00:08:51,400
Haluamme palata kursori virhe sana
koska muistan taas, jos kissa ei ole

153
00:08:51,400 --> 00:08:55,140
meidän sanakirja ja katastrofi on,
niin me onnistuneesti läpi

154
00:08:55,140 --> 00:08:59,810
sana kissa, mutta kursori sana
on väärä ja ei ole totta.

155
00:08:59,810 --> 00:09:04,990
Joten palaamme kursori tarkoittava sana
onko tämä solmu on oikeastaan ​​sana,

156
00:09:04,990 --> 00:09:06,530
ja se on siinä lähtöselvitykseen.

157
00:09:06,530 --> 00:09:08,310
>> Joten tarkistaa koko.

158
00:09:08,310 --> 00:09:11,410
Joten koko tulee olemaan melko helppoa
koska muistaa Load, olemme

159
00:09:11,410 --> 00:09:15,480
monesko sanakirja koko
jokainen sana, että törmäämme.

160
00:09:15,480 --> 00:09:20,820
Joten koko on vain aio palata
sanakirjan koko, ja se on siinä.

161
00:09:20,820 --> 00:09:24,650
>> Okei, joten lopuksi, meillä on Unload.

162
00:09:24,650 --> 00:09:29,050
Joten Unload, aiomme käyttää
rekursiivinen funktio itse tehdä kaikki

163
00:09:29,050 --> 00:09:33,390
työn meille, joten meidän tehtävämme
aiotaan kutsutaan Unloader.

164
00:09:33,390 --> 00:09:35,830
Mitä Unloader aiot tehdä?

165
00:09:35,830 --> 00:09:40,640
Näemme tässä, että Unloader on menossa
kerrata hoitaakseen kaikki lasten

166
00:09:40,640 --> 00:09:45,810
Tässä nimenomaisessa solmu, ja jos lapsi
solmu ei ole nolla, niin aiomme

167
00:09:45,810 --> 00:09:47,760
purkaa lapsi solmu.

168
00:09:47,760 --> 00:09:52,070
>> Joten tämä on menossa rekursiivisesti
purkaa kaikki lapsemme.

169
00:09:52,070 --> 00:09:55,140
Kun olemme varmoja, että kaikki lapsemme
on purettu, niin me

170
00:09:55,140 --> 00:09:58,830
voi vapauttaa itsemme, niin purkaa itsestämme.

171
00:09:58,830 --> 00:10:04,550
Joten tämä rekursiivisesti purkaa
koko Trie, ja sitten kun se on

172
00:10:04,550 --> 00:10:06,910
tehty, voimme vain palata True.

173
00:10:06,910 --> 00:10:09,770
Kevennys ei voi epäonnistua, olemme
vain vapauttaa asioita.

174
00:10:09,770 --> 00:10:12,985
Joten kun olemme tehneet vapauttaa
kaiken, return true.

175
00:10:12,985 --> 00:10:14,380
Ja se on siinä.

176
00:10:14,380 --> 00:10:16,792
Nimeni on Rob, ja tämä
oli [äänetön].

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