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

2
00:00:00,530 --> 00:00:03,070
>> GARSIAKALBIS 1: Duokime
šis sprendimas pabandyti.

3
00:00:03,070 --> 00:00:07,130
Taigi galime pažvelgti, kas mūsų išvaizdą
Struct mazgas atrodys.

4
00:00:07,130 --> 00:00:11,040
Čia mes matome, mes ketiname turėti
Bool Žodis ir struct mazgas žvaigždė

5
00:00:11,040 --> 00:00:12,990
Vaikai laikiklis abėcėlę.

6
00:00:12,990 --> 00:00:18,720
Taigi pirmas dalykas, jums gali būti įdomu,
kodėl abėcėlė maišos apibrėžiamas kaip 27?

7
00:00:18,720 --> 00:00:22,540
Na, nepamirškite, kad mes ketiname reikia
reikia tvarkyti kabutes, todėl

8
00:00:22,540 --> 00:00:25,610
tai bus šiek tiek ypatingą
atveju visoje šioje programoje.

9
00:00:25,610 --> 00:00:28,780
>> Gerai, dabar prisimenu, kaip
Trie iš tiesų veikia.

10
00:00:28,780 --> 00:00:33,420
Tarkime, mes indeksavimo žodį kačių,
tada iš mūsų TRIE šaknis,

11
00:00:33,420 --> 00:00:36,670
mes ketiname pažvelgti į vaikų
masyvas, ir mes ketiname pažvelgti į

12
00:00:36,670 --> 00:00:42,250
indeksas, kuris atitinka raide
C. Taigi, kad būtų du indeksas.

13
00:00:42,250 --> 00:00:46,400
Taigi, atsižvelgiant į tai, kad duos mums
naujas mazgas, ir tada mes

14
00:00:46,400 --> 00:00:47,880
dirbti nuo tos mazgas.

15
00:00:47,880 --> 00:00:51,830
>> Taigi, atsižvelgiant į tai, mazgas, mes dar kartą
ketiname pažvelgti į vaikų masyvas,

16
00:00:51,830 --> 00:00:56,170
ir mes ketiname pažvelgti į nulinę indekso
atitikti kačių A.

17
00:00:56,170 --> 00:01:01,240
Taigi mes ketiname eiti į tą mazgą,
ir atsižvelgiant į tai, kad mazgas, mes ketiname

18
00:01:01,240 --> 00:01:05,170
pažvelgti į indeksą, kuris atitinka
į T. juda į tą mazgą,

19
00:01:05,170 --> 00:01:09,590
pagaliau, mes turime visiškai atrodė
mūsų žodis katė, o dabar bool

20
00:01:09,590 --> 00:01:15,020
Žodis turėtų nurodyti, ar
turint mintyje tai žodis iš tikrųjų žodis.

21
00:01:15,020 --> 00:01:17,530
>> Tad kodėl mes turime tą ypatingą bylą?

22
00:01:17,530 --> 00:01:21,680
Na, ką daryti, jei žodis katastrofa
yra mūsų žodyne, tačiau

23
00:01:21,680 --> 00:01:24,120
žodis katė yra ne?

24
00:01:24,120 --> 00:01:29,030
Taigi, pažiūrėkite, jei žodis katė
mūsų žodyną, mes ketiname

25
00:01:29,030 --> 00:01:34,880
sėkmingai ieškoti per indeksus
C-T ir pasiekti viršūnę, bet tai

26
00:01:34,880 --> 00:01:39,760
tik todėl, kad katastrofa atsitiko
sukurti mazgų kelyje iš C-A-T visi

27
00:01:39,760 --> 00:01:41,250
Kelias į žodžio pabaigą.

28
00:01:41,250 --> 00:01:46,520
Taigi loginis žodis yra naudojamas nurodyti, ar
tai pirma vieta tikrai

29
00:01:46,520 --> 00:01:48,370
nurodo žodį.

30
00:01:48,370 --> 00:01:52,920
>> Gerai, kad dabar, kad mes žinome, ką
Trie ketina atrodyti, pažvelkime

31
00:01:52,920 --> 00:01:54,800
esant apkrovai funkcija.

32
00:01:54,800 --> 00:01:58,670
Taigi keliamoji ketina grįžti bool
Dėl klausimo, ar mes sėkmingai arba

33
00:01:58,670 --> 00:02:03,020
nesėkmingai pakrautas žodynas ir
tai bus žodynas

34
00:02:03,020 --> 00:02:04,520
kad mes norime įkelti.

35
00:02:04,520 --> 00:02:08,310
Taigi pirmas dalykas, kurį mes ketiname padaryti, tai atidaryti
iki to žodyne svarstymą.

36
00:02:08,310 --> 00:02:12,060
Mes turime įsitikinti, kad mes nepamiršo,
todėl, jei žodynas nebuvo

37
00:02:12,060 --> 00:02:15,280
sėkmingai atidarytas, jis sugrįš
Ne, tokiu atveju mes ketiname

38
00:02:15,280 --> 00:02:16,340
return false.

39
00:02:16,340 --> 00:02:21,290
Tačiau darant prielaidą, kad jis sėkmingai
atidarytas, tada mes iš tiesų gali skaityti

40
00:02:21,290 --> 00:02:22,310
per žodyną.

41
00:02:22,310 --> 00:02:24,940
>> Taigi pirmas dalykas, kurį mes ketiname
norite padaryti, tai turime tai

42
00:02:24,940 --> 00:02:26,560
pasaulinį kintamąjį šaknis.

43
00:02:26,560 --> 00:02:30,250
Dabar šaknis bus mazgas žvaigždė.

44
00:02:30,250 --> 00:02:33,830
Tai mūsų TRIE viršų, kad mes
bus iteravimu per.

45
00:02:33,830 --> 00:02:38,200
Taigi pirmas dalykas, kurį mes ketiname norite
padaryti yra paskirstyti atmintį mūsų šaknis.

46
00:02:38,200 --> 00:02:42,040
>> Atkreipkite dėmesį, kad mes naudojame Calloc
funkcija, kuri yra iš esmės tas pats

47
00:02:42,040 --> 00:02:45,560
kaip malloc funkcijos, išskyrus tai
garantuoja, kad grįžti kažką, kad yra

48
00:02:45,560 --> 00:02:47,240
visiškai nulis iš.

49
00:02:47,240 --> 00:02:51,350
Taigi, jei mes naudojome malloc, mums reikia
eiti per visus iš rodyklės mūsų

50
00:02:51,350 --> 00:02:54,220
mazgas ir įsitikinkite, kad
jie visi null.

51
00:02:54,220 --> 00:02:56,780
Taigi Calloc bus tai padaryti už mus.

52
00:02:56,780 --> 00:03:00,390
>> Dabar, kaip malloc, mes turime padaryti
įsitikinkite, kad paskirstymas iš tikrųjų

53
00:03:00,390 --> 00:03:01,580
sėkmingas.

54
00:03:01,580 --> 00:03:04,060
Jei tai grąžinami null, tada mes
reikia uždaryti savo žodyną

55
00:03:04,060 --> 00:03:06,170
failą ir grąžina false.

56
00:03:06,170 --> 00:03:11,040
Taigi, darant prielaidą, kad asignavimai buvo
sėkmingas, mes ketiname naudoti mazgas

57
00:03:11,040 --> 00:03:14,340
star žymeklį į Iterate
per mūsų TRIE.

58
00:03:14,340 --> 00:03:17,950
Taigi, mūsų šaknis niekada nesiruošia keisti,
bet mes ketiname naudoti žymeklį į

59
00:03:17,950 --> 00:03:20,770
faktiškai eiti iš mazgo į mazgą.

60
00:03:20,770 --> 00:03:25,000
>> Viskas gerai, todėl tai už linijos, mes
Skaitydami žodyno failą,

61
00:03:25,000 --> 00:03:26,965
ir mes naudojame ne fgetc.

62
00:03:26,965 --> 00:03:30,360
Taigi fgetc ketina patraukti vieną
simbolį iš failo.

63
00:03:30,360 --> 00:03:33,430
Mes ketiname tęsti greiferiniai
ženklai, o mes nepasiekia

64
00:03:33,430 --> 00:03:37,540
failo pabaiga, todėl yra
Dviem atvejais mes turime elgtis.

65
00:03:37,540 --> 00:03:41,640
Pirma, jei personažas nebuvo
nauja linija, todėl mes žinome, jeigu tai buvo nauja

66
00:03:41,640 --> 00:03:44,480
linija, tada mes apie
pereiti į naują žodį.

67
00:03:44,480 --> 00:03:49,300
Tačiau darant prielaidą, kad tai buvo ne nauja eilutė, tada
čia mes norime išsiaiškinti,

68
00:03:49,300 --> 00:03:52,440
rodiklis mes ketiname indeksą į
į vaikų matrica,

69
00:03:52,440 --> 00:03:53,890
mes pažvelgė anksčiau.

70
00:03:53,890 --> 00:03:57,950
>> Taigi, kaip ir minėjau anksčiau, mes turime
Ypatingas atvejis kabutes.

71
00:03:57,950 --> 00:04:01,040
Atkreipkite dėmesį, mes naudojame trijų komponentų operatorių
čia, todėl mes ketiname skaityti

72
00:04:01,040 --> 00:04:05,500
tai tarsi simbolis skaitome buvo
Apostrofa, tada mes ketiname

73
00:04:05,500 --> 00:04:11,740
nustatytas indeksas yra abėcėlės minus
1, kuris bus 26 indeksas.

74
00:04:11,740 --> 00:04:15,190
Kitur, jei tai buvo ne Apostrofa,
tada mes ketiname sukurti indeksą

75
00:04:15,190 --> 00:04:17,820
lygi c minus.

76
00:04:17,820 --> 00:04:23,090
Taigi nepamirškite grįžti iš ankstesnių p rinkinių,
c atėmus ketina duoti mums

77
00:04:23,090 --> 00:04:27,470
Abėcėlinis pozicija c, todėl, jei
c yra raidė, tai bus

78
00:04:27,470 --> 00:04:28,770
mums nulinį indeksą.

79
00:04:28,770 --> 00:04:32,180
Dėl raide B, jis duos
mums indeksas 1, ir pan.

80
00:04:32,180 --> 00:04:37,070
>> Taigi, tai suteikia mums rodyklę į
Vaikai masyvas, kad mes norime.

81
00:04:37,070 --> 00:04:42,540
Dabar, jei šis rodiklis šiuo metu yra niekinis ir
Vaikai masyvas, tai reiškia, kad

82
00:04:42,540 --> 00:04:47,470
mazgas šiuo metu nėra iš
tas kelias, todėl reikia skirti

83
00:04:47,470 --> 00:04:49,220
mazgas šiuo keliu.

84
00:04:49,220 --> 00:04:50,610
Štai ką mes čia.

85
00:04:50,610 --> 00:04:54,650
Taigi, mes ketiname vėl naudoti Calloc
funkcija, kad mes neturime

86
00:04:54,650 --> 00:05:00,130
iki nulio iš visų patarimų, o mes,
vėl, reikia patikrinti, kad Calloc

87
00:05:00,130 --> 00:05:01,300
nepamiršo.

88
00:05:01,300 --> 00:05:04,760
Jei Calloc dar nepavyksta, tada mes turime
iškrauti viską, užmerkti

89
00:05:04,760 --> 00:05:06,880
žodyną, ir return false.

90
00:05:06,880 --> 00:05:14,110
>> Taigi, darant prielaidą, kad jis nepavyktų, tada
tai sukurs naują vaiką už mus,

91
00:05:14,110 --> 00:05:16,000
ir tada mes galėsime eiti į tą vaiką.

92
00:05:16,000 --> 00:05:19,030
Mūsų žymeklis bus pakartoti
iki to vaiko.

93
00:05:19,030 --> 00:05:23,390
Dabar, jei tai buvo ne null prasideda,
tada žymeklį galite tiesiog kartoti

94
00:05:23,390 --> 00:05:26,650
žemyn į tą vaiką faktiškai
turintys skirti nieko.

95
00:05:26,650 --> 00:05:30,790
Tai atvejis, kai mes pirmą kartą atsitiko
skirti žodis katė, ir

96
00:05:30,790 --> 00:05:34,390
tai reiškia, kad, kai mes einame skirti
katastrofa, mums nereikia kurti

97
00:05:34,390 --> 00:05:35,720
mazgai C-A-T dar kartą.

98
00:05:35,720 --> 00:05:37,620
Jie jau egzistuoja.

99
00:05:37,620 --> 00:05:40,140
>> Gerai, kad kas tai yra kita?

100
00:05:40,140 --> 00:05:44,600
Tai būklė, kai c buvo
Backslash n, kur c buvo nauja linija.

101
00:05:44,600 --> 00:05:47,780
Tai reiškia, kad mes sėkmingai
baigė žodį.

102
00:05:47,780 --> 00:05:51,020
Dabar, ką mes norime daryti, kai mes
sėkmingai baigė žodį?

103
00:05:51,020 --> 00:05:55,250
Mes ketiname naudoti šį žodį lauką
viduje mūsų struct mazgas.

104
00:05:55,250 --> 00:06:00,570
>> Mes norime nustatyti, kad "True, kad
rodo, kad šis mazgas rodo

105
00:06:00,570 --> 00:06:03,320
sėkmingas žodis tikrasis žodis.

106
00:06:03,320 --> 00:06:05,050
Dabar nustatyta, kad True.

107
00:06:05,050 --> 00:06:09,210
Mes norime, kad naujo mūsų žymeklį į tašką
į TRIE pradžioje dar kartą.

108
00:06:09,210 --> 00:06:13,510
Ir, pagaliau, prieaugio mūsų žodyną
dydis, nes mes rasti kitą žodį.

109
00:06:13,510 --> 00:06:16,450
>> Gerai, kad mes ketiname toliau daryti
kad skaitymo pobūdį,

110
00:06:16,450 --> 00:06:21,960
pobūdžio, statant naujus mazgų
mūsų Trie ir kiekvieno žodžio

111
00:06:21,960 --> 00:06:26,810
žodynas, kol mes pagaliau pasieks c
Lygu EOF, tokiu atveju, mes pertraukos

112
00:06:26,810 --> 00:06:28,100
iš failo.

113
00:06:28,100 --> 00:06:31,110
Dabar yra du atvejai, pagal
kurios mes galime nukentėjo EOF.

114
00:06:31,110 --> 00:06:35,680
Pirma, jei ten buvo klaida
skaitant iš failo, todėl, jei ten buvo

115
00:06:35,680 --> 00:06:39,280
klaida, mes turime padaryti, tipiškas
iškrauti viską, uždarykite failą,

116
00:06:39,280 --> 00:06:40,520
return false.

117
00:06:40,520 --> 00:06:43,870
Darant prielaidą, kad nebuvo klaida, kad
tiesiog reiškia, kad mes iš tikrųjų pateko į pabaigą

118
00:06:43,870 --> 00:06:47,820
failas, tokiu atveju, mes uždaryti
failą ir grąžina true, nes mes

119
00:06:47,820 --> 00:06:51,010
sėkmingai įkeltas žodyną
į mūsų TRIE.

120
00:06:51,010 --> 00:06:54,240
>> Viskas gerai, todėl dabar tegul
patikrinti tikrinimas.

121
00:06:54,240 --> 00:06:58,780
Pažvelgus Check funkcija, matome
Tokį patikrinimą ketina grįžti bool.

122
00:06:58,780 --> 00:07:03,740
Ji grąžina True, jei šis žodis, kad tai
bus perduotas yra mūsų TRIE.

123
00:07:03,740 --> 00:07:06,170
Tai False kitaip.

124
00:07:06,170 --> 00:07:10,110
>> Taigi, kaip mes ketiname nustatyti, ar
šis žodis yra mūsų TRIE?

125
00:07:10,110 --> 00:07:14,270
Čia mes matome, kad, kaip ir anksčiau,
mes ketiname naudoti žymeklį pakartoti

126
00:07:14,270 --> 00:07:16,010
per mūsų TRIE.

127
00:07:16,010 --> 00:07:20,650
Dabar, čia mes ketiname pakartoti
per visą mūsų žodį.

128
00:07:20,650 --> 00:07:24,680
Taigi Iteracja virš žodžio mes
praėjo, mes ketiname nustatyti

129
00:07:24,680 --> 00:07:29,280
rodyklė į vaikų matrica,
atitinka žodžio kronšteino i.

130
00:07:29,280 --> 00:07:34,150
Taigi, tai bus atrodo kaip
Apkrova, kur, jei žodis laikiklis i

131
00:07:34,150 --> 00:07:38,110
Apostrofa, tada mes norite naudoti indeksas
abėcėlė minus 1, nes mes nustatėme

132
00:07:38,110 --> 00:07:41,160
tai kur mes einame
laikyti kabutes.

133
00:07:41,160 --> 00:07:44,440
>> Dar mes ketiname naudoti tolower
Žodis laikiklis i.

134
00:07:44,440 --> 00:07:48,270
Taigi nepamirškite, kad žodis gali būti savavališkas
kapitalizacija, ir todėl mes

135
00:07:48,270 --> 00:07:51,590
norite įsitikinti, kad mes naudojame
mažosiomis portalo dalykų.

136
00:07:51,590 --> 00:07:55,300
Ir tada atimti iš tos mažosios
kad dar kartą suteiktų mums

137
00:07:55,300 --> 00:07:57,940
abėcėlės tvarka
Šio pobūdžio.

138
00:07:57,940 --> 00:08:01,740
Taigi, tai bus mūsų puslapis
į vaikų masyvo.

139
00:08:01,740 --> 00:08:06,480
>> Ir dabar, jei tai puslapis į vaikų
masyvas yra tuščias, tai reiškia, kad mes

140
00:08:06,480 --> 00:08:09,050
nebegali Iteracja
žemyn mūsų TRIE.

141
00:08:09,050 --> 00:08:13,320
Jei tai toks atvejis, šis žodis negali
galbūt bus mūsų TRIE, nes jei ji

142
00:08:13,320 --> 00:08:18,000
buvo, tai reikštų, kad būtų
Kelias iki šio žodžio, ir jūs

143
00:08:18,000 --> 00:08:19,350
niekada susidurti null.

144
00:08:19,350 --> 00:08:21,910
Taigi iškyla null mes return false.

145
00:08:21,910 --> 00:08:23,810
Žodžio nėra žodyne.

146
00:08:23,810 --> 00:08:28,200
Jei tai buvo ne nulis, tada mes ketiname
toliau Iteracja, todėl mes ketiname

147
00:08:28,200 --> 00:08:33,150
atnaujinti savo žymeklį, kad rodytų į tai
ypač mazgas tuo indeksu.

148
00:08:33,150 --> 00:08:36,659
>> Taigi, mes nuolat tai daryti, kad per
visą žodį.

149
00:08:36,659 --> 00:08:40,630
Darant prielaidą, kad mes niekada hit null, tai reiškia,
mes galėjome gauti visą

150
00:08:40,630 --> 00:08:44,840
pasaulio ir rasti mūsų TRIE mazgas,
bet mes ne visai padaryta dar.

151
00:08:44,840 --> 00:08:46,350
Mes nenorime, tiesiog grįžti Tiesa.

152
00:08:46,350 --> 00:08:51,400
Mes norime grįžti žymeklį klaidos žodį
kadangi, nepamirškite vėl, jei katė nėra

153
00:08:51,400 --> 00:08:55,140
į mūsų žodyną ir katastrofa,
tada mes sėkmingai gauti per

154
00:08:55,140 --> 00:08:59,810
žodis katė, bet žymeklis žodis
bus False, o ne tiesa.

155
00:08:59,810 --> 00:09:04,990
Taigi, mes grįžtame žymeklio žodį rodo
ar šis mazgas yra iš tikrųjų žodis

156
00:09:04,990 --> 00:09:06,530
ir viskas registruotis.

157
00:09:06,530 --> 00:09:08,310
>> Taigi galime patikrinti dydis.

158
00:09:08,310 --> 00:09:11,410
Taigi dydis bus gana lengva
nes prisiminti, Load, mes

159
00:09:11,410 --> 00:09:15,480
incrementing žodyno dydį
kiekvienas žodis, kad mes susiduriame.

160
00:09:15,480 --> 00:09:20,820
Taigi Dydis tik ketina grįžti
žodynas dydis, ir viskas.

161
00:09:20,820 --> 00:09:24,650
>> Viskas gerai, taip galiausiai, turime iškrauti.

162
00:09:24,650 --> 00:09:29,050
Taigi Iškelti, mes ketiname naudoti
grįžtamojo funkcija iš tiesų visi

163
00:09:29,050 --> 00:09:33,390
iš mums, tiek mūsų funkcija darbo
bus vadinama unloader.

164
00:09:33,390 --> 00:09:35,830
Kas yra Kėlimo ketinate daryti?

165
00:09:35,830 --> 00:09:40,640
Čia mes matome, kad Kėlimo ketina
kartoti per visas vaikams

166
00:09:40,640 --> 00:09:45,810
tai ypač mazgas, ir jei vaikas
mazgas nėra lygus nuliui, tada mes ketiname

167
00:09:45,810 --> 00:09:47,760
iškrauti vaikų mazgas.

168
00:09:47,760 --> 00:09:52,070
>> Taigi, tai bus rekursyviai
iškrauti visus mūsų vaikus.

169
00:09:52,070 --> 00:09:55,140
Kai mes esame tikri, kad visi mūsų vaikai
buvo iškrauti, tada mes

170
00:09:55,140 --> 00:09:58,830
gali išsivaduoti, todėl iškrauti Save.

171
00:09:58,830 --> 00:10:04,550
Taigi, tai bus rekursyviai iškrauti
Visa Trie, ir tada, kai tai

172
00:10:04,550 --> 00:10:06,910
padaryta, mes galime tiesiog grąžina true.

173
00:10:06,910 --> 00:10:09,770
Iškelti negali žlugti, mes
tiesiog išlaisvina dalykų.

174
00:10:09,770 --> 00:10:12,985
Taigi, kai mes baigsime išlaisvinant
viskas, grąžina true.

175
00:10:12,985 --> 00:10:14,380
Štai ir viskas.

176
00:10:14,380 --> 00:10:16,792
Mano vardas yra Rob, o tai
buvo [nesigirdi].

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