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

2
00:00:00,530 --> 00:00:03,070
>> SPEAKER 1: Lad os give
denne løsning en chance.

3
00:00:03,070 --> 00:00:07,130
Så lad os tage et kig på, hvad vores
Struct node vil se ud.

4
00:00:07,130 --> 00:00:11,040
Her ser vi, at vi kommer til at have en
Bool Word og en Struct node stjerne

5
00:00:11,040 --> 00:00:12,990
Børn bracketing alfabet.

6
00:00:12,990 --> 00:00:18,720
Så første ting du måske være undrende,
hvorfor er alfabet hash defineres som 27?

7
00:00:18,720 --> 00:00:22,540
Nå, huske, at vi får brug for
at håndtering apostrof, så

8
00:00:22,540 --> 00:00:25,610
der kommer til at være noget af en speciel
tilfældet i dette program.

9
00:00:25,610 --> 00:00:28,780
>> OK, nu huske, hvordan en
Trie rent faktisk virker.

10
00:00:28,780 --> 00:00:33,420
Lad os sige, at vi indeksering ordet katte
derefter fra roden af ​​vores Trie,

11
00:00:33,420 --> 00:00:36,670
vi kommer til at se på børn
array, og vi kommer til at se på

12
00:00:36,670 --> 00:00:42,250
indeks, der svarer til det bogstav
C. Så det ville være indeks to.

13
00:00:42,250 --> 00:00:46,400
Så da vil det give os
en ny knude, og så vil vi

14
00:00:46,400 --> 00:00:47,880
arbejde fra dette knudepunkt.

15
00:00:47,880 --> 00:00:51,830
>> Så da knude, vi igen
kommer til at se på array Children,

16
00:00:51,830 --> 00:00:56,170
og vi kommer til at se på indeks nul
at svare til A i kat.

17
00:00:56,170 --> 00:01:01,240
Så vi kommer til at gå til denne node,
og eftersom knude, vi kommer

18
00:01:01,240 --> 00:01:05,170
at se på det indeks, der svarer
T. Og går videre til denne node,

19
00:01:05,170 --> 00:01:09,590
Endelig har vi helt kigget
gennem vores ord Cat, og nu Bool

20
00:01:09,590 --> 00:01:15,020
Word er meningen at angive, om
dette givne ord er faktisk et ord.

21
00:01:15,020 --> 00:01:17,530
>> Så hvorfor har vi brug for, at særlige tilfælde?

22
00:01:17,530 --> 00:01:21,680
Nå, hvad hvis ordet katastrofe
er i vores ordbog, men

23
00:01:21,680 --> 00:01:24,120
Ordet kat er ikke?

24
00:01:24,120 --> 00:01:29,030
Så i at kigge for at se, om ordet kat er
i vores ordbog, vi kommer til

25
00:01:29,030 --> 00:01:34,880
held se gennem indeksene
C-A-T og nå frem til en node, men det er

26
00:01:34,880 --> 00:01:39,760
kun fordi katastrofe skete med
skabe knudepunkter på vejen fra C-A-T alle

27
00:01:39,760 --> 00:01:41,250
vejen til slutningen af ​​ordet.

28
00:01:41,250 --> 00:01:46,520
Så Bool Word bruges angive, om
netop dette sted faktisk

29
00:01:46,520 --> 00:01:48,370
angiver et ord.

30
00:01:48,370 --> 00:01:52,920
>> Okay, så nu, at vi ved, hvad en
Trie kommer til at se ud, så lad os se

31
00:01:52,920 --> 00:01:54,800
på Load-funktionen.

32
00:01:54,800 --> 00:01:58,670
Så Load kommer til at returnere en Bool
for, om vi med succes eller

33
00:01:58,670 --> 00:02:03,020
held loaded ordbog og
dette vil være ordbogen

34
00:02:03,020 --> 00:02:04,520
at vi ønsker at indlæse.

35
00:02:04,520 --> 00:02:08,310
Så første ting, vi vil gøre er at åbne
op at ordbogen for læsning.

36
00:02:08,310 --> 00:02:12,060
Vi er nødt til at sørge for, vi ikke svigte,
så hvis ordbogen ikke var

37
00:02:12,060 --> 00:02:15,280
succes åbnet, vil den vende tilbage
Nej, i hvilket tilfælde vi vil

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

39
00:02:16,340 --> 00:02:21,290
Men at antage, at det er lykkedes
åbnet, så kan vi rent faktisk læst

40
00:02:21,290 --> 00:02:22,310
gennem ordbogen.

41
00:02:22,310 --> 00:02:24,940
>> Så første ting, vi kommer til at
ønsker at gøre, er at vi har denne

42
00:02:24,940 --> 00:02:26,560
global variabel rod.

43
00:02:26,560 --> 00:02:30,250
Nu rod bliver en node stjerne.

44
00:02:30,250 --> 00:02:33,830
Det er toppen af ​​vores Trie, at vi er
vil blive iteration igennem.

45
00:02:33,830 --> 00:02:38,200
Så første ting, vi kommer til at ønsker at
gøre, er at tildele hukommelse til vores rod.

46
00:02:38,200 --> 00:02:42,040
>> Bemærk, at vi bruger den calloc
funktion, som er stort set den samme

47
00:02:42,040 --> 00:02:45,560
som allokere funktion, medmindre det er
garanteret til at returnere noget, der er

48
00:02:45,560 --> 00:02:47,240
helt nulstillet.

49
00:02:47,240 --> 00:02:51,350
Så hvis vi brugte malloc, ville vi nødt til at
gå igennem alle de pejlemærker i vores

50
00:02:51,350 --> 00:02:54,220
node og sørg for, at
de er alle nul.

51
00:02:54,220 --> 00:02:56,780
Så calloc vil gøre det for os.

52
00:02:56,780 --> 00:03:00,390
>> Nu, ligesom malloc, er vi nødt til at gøre
sikker på, at fordelingen er faktisk

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

54
00:03:01,580 --> 00:03:04,060
Hvis det returnerede null, så vi
nødt til at lukke vores ordbog

55
00:03:04,060 --> 00:03:06,170
fil og returnere False.

56
00:03:06,170 --> 00:03:11,040
Så under forudsætning af bevillingen blev
succes, vi kommer til at bruge en node

57
00:03:11,040 --> 00:03:14,340
stjerne Cursor til at gentage
gennem vores Trie.

58
00:03:14,340 --> 00:03:17,950
Så vores rod er aldrig vil ændre sig,
men vi kommer til at bruge markør til

59
00:03:17,950 --> 00:03:20,770
faktisk gå fra knudepunkt til knudepunkt.

60
00:03:20,770 --> 00:03:25,000
>> Okay, så i dette For loop, er vi
læsning gennem ordbogen fil,

61
00:03:25,000 --> 00:03:26,965
og vi bruger på fgetc.

62
00:03:26,965 --> 00:03:30,360
Så fgetc kommer til at få fat i en enkelt
tegn fra filen.

63
00:03:30,360 --> 00:03:33,430
Vi kommer til at fortsætte med at snuppe
tegn, mens vi ikke nå

64
00:03:33,430 --> 00:03:37,540
slutningen af ​​filen, så der er
to sager, vi skal håndtere.

65
00:03:37,540 --> 00:03:41,640
Den første, hvis karakter ikke er en
ny linje, så vi ved, om det var en ny

66
00:03:41,640 --> 00:03:44,480
linje, så vi er ved at
gå videre til et nyt ord.

67
00:03:44,480 --> 00:03:49,300
Men forudsat det ikke var en ny linje, så
her, vi ønsker at finde ud af

68
00:03:49,300 --> 00:03:52,440
indeks vil vi indekset i
i array Børn som

69
00:03:52,440 --> 00:03:53,890
vi kiggede på før.

70
00:03:53,890 --> 00:03:57,950
>> Så som jeg sagde før, er vi nødt til at
særligt tilfælde apostrof.

71
00:03:57,950 --> 00:04:01,040
Bemærk vi bruger den ternære operatør
her, så vi kommer til at læse

72
00:04:01,040 --> 00:04:05,500
dette, som om det tegn, vi læser i var
en apostrof, så vi kommer til at

73
00:04:05,500 --> 00:04:11,740
sæt indeks svarende til alfabet minus
1, som vil blive indeks 26.

74
00:04:11,740 --> 00:04:15,190
Else, hvis det ikke var en apostrof,
så vi kommer til at indstille indekset

75
00:04:15,190 --> 00:04:17,820
lig med C minus en.

76
00:04:17,820 --> 00:04:23,090
Så husk tilbage fra tidligere p-apparater,
c minus en kommer til at give os

77
00:04:23,090 --> 00:04:27,470
alfabetisk position c, så hvis
c er bogstavet A, vil dette

78
00:04:27,470 --> 00:04:28,770
give os indekset nul.

79
00:04:28,770 --> 00:04:32,180
For bogstavet B, ville det give
os indeks 1, og så videre.

80
00:04:32,180 --> 00:04:37,070
>> Så det giver os indekset i
Børn array, vi ønsker.

81
00:04:37,070 --> 00:04:42,540
Nu, hvis dette indeks er i øjeblikket null i
array Børn, der betyder, at

82
00:04:42,540 --> 00:04:47,470
en node findes ikke i øjeblikket fra
denne sti, så vi er nødt til at afsætte en

83
00:04:47,470 --> 00:04:49,220
node for denne vej.

84
00:04:49,220 --> 00:04:50,610
Det er, hvad vi gør her.

85
00:04:50,610 --> 00:04:54,650
Så vi kommer til, igen bruge calloc
funktion, så vi ikke har

86
00:04:54,650 --> 00:05:00,130
til nul ud af alle de pejlemærker, og vi,
igen, er nødt til at kontrollere, at calloc

87
00:05:00,130 --> 00:05:01,300
svigtede ikke.

88
00:05:01,300 --> 00:05:04,760
Hvis calloc undlod, så har vi brug
at losse alt, lukke vores

89
00:05:04,760 --> 00:05:06,880
ordbog, og returnere False.

90
00:05:06,880 --> 00:05:14,110
>> Så under forudsætning af, at det ikke mislykkes, da
dette vil skabe et nyt barn for os,

91
00:05:14,110 --> 00:05:16,000
og så vil vi gå til det pågældende barn.

92
00:05:16,000 --> 00:05:19,030
Vores markør gentage
ned til barnet.

93
00:05:19,030 --> 00:05:23,390
Nu, hvis dette ikke var nul at begynde med,
så markøren kan bare gentage

94
00:05:23,390 --> 00:05:26,650
ned til det barn uden egentlig
skulle afsætte noget.

95
00:05:26,650 --> 00:05:30,790
Dette er tilfældet, når vi først skete
at tildele ordet kat, og

96
00:05:30,790 --> 00:05:34,390
det betyder, når vi går til at afsætte
katastrofe, behøver vi ikke at skabe

97
00:05:34,390 --> 00:05:35,720
knudepunkter for C-A-T igen.

98
00:05:35,720 --> 00:05:37,620
De findes allerede.

99
00:05:37,620 --> 00:05:40,140
>> OK, så hvad er det andet?

100
00:05:40,140 --> 00:05:44,600
Det er den tilstand, hvor c var
backslash n, hvor c var en ny linje.

101
00:05:44,600 --> 00:05:47,780
Det betyder, at vi har succes
afsluttet et ord.

102
00:05:47,780 --> 00:05:51,020
Nu, hvad vi ønsker at gøre, når vi
gennemført et ord?

103
00:05:51,020 --> 00:05:55,250
Vi kommer til at bruge dette ord felt
inde i vores Struct node.

104
00:05:55,250 --> 00:06:00,570
>> Vi ønsker at sætte det til True, så
angiver, at dette knudepunkt indikerer en

105
00:06:00,570 --> 00:06:03,320
vellykket ord et virkeligt ord.

106
00:06:03,320 --> 00:06:05,050
Nu indstilles det til True.

107
00:06:05,050 --> 00:06:09,210
Vi ønsker at nulstille vores markøren til punkt
til begyndelsen af ​​Trie igen.

108
00:06:09,210 --> 00:06:13,510
Og endelig, forøge vores ordbog
størrelse, da vi fandt et andet ord.

109
00:06:13,510 --> 00:06:16,450
>> Okay, så vi kommer til at holde gør
at læsning i karakter ved at

110
00:06:16,450 --> 00:06:21,960
karakter, bygge nye knudepunkter i
vores Trie og for hvert ord i

111
00:06:21,960 --> 00:06:26,810
ordbog, indtil vi endelig nå c
lig EOF, i hvilket tilfælde, vi bryder

112
00:06:26,810 --> 00:06:28,100
ud af filen.

113
00:06:28,100 --> 00:06:31,110
Nu er der to tilfælde under
som vi måske har EOF ramt.

114
00:06:31,110 --> 00:06:35,680
Den første er, hvis der var en fejl
læsning fra filen, så hvis der var

115
00:06:35,680 --> 00:06:39,280
en fejl, er vi nødt til at gøre det typiske
losse alt, lukke filen,

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

117
00:06:40,520 --> 00:06:43,870
Hvis man antager, at der ikke var en fejl, at
betyder bare, at vi faktisk ramt slutningen af

118
00:06:43,870 --> 00:06:47,820
filen, i hvilket tilfælde vi lukker
fil og returnere sandt, da vi

119
00:06:47,820 --> 00:06:51,010
har indlæst ordbogen
ind i vores Trie.

120
00:06:51,010 --> 00:06:54,240
>> Okay, så lad os nu
tjek Check.

121
00:06:54,240 --> 00:06:58,780
Ser man på Check-funktionen, ser vi
at Check kommer til at returnere en Bool.

122
00:06:58,780 --> 00:07:03,740
Det giver True hvis dette ord, at det er
væltes er i vores Trie.

123
00:07:03,740 --> 00:07:06,170
Den returnerer False andet.

124
00:07:06,170 --> 00:07:10,110
>> Så hvordan skal vi afgøre, om
dette ord er i vores Trie?

125
00:07:10,110 --> 00:07:14,270
Vi ser her, at, ligesom før,
vi kommer til at bruge markøren til at gentage

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

127
00:07:16,010 --> 00:07:20,650
Nu, her, vi kommer til at gentage
over vores hele ordet.

128
00:07:20,650 --> 00:07:24,680
Så iteration over ordet vi
passeret, vi kommer til at bestemme

129
00:07:24,680 --> 00:07:29,280
indekset i array barn, der
svarer til word beslag jeg.

130
00:07:29,280 --> 00:07:34,150
Så det kommer til at se ud nøjagtig som
Belastning, hvor hvis ordet beslag i er et

131
00:07:34,150 --> 00:07:38,110
apostrof, så vi ønsker at bruge indeks
alfabet minus 1, fordi vi bestemt

132
00:07:38,110 --> 00:07:41,160
der er, hvor vi skal hen
at gemme apostrof.

133
00:07:41,160 --> 00:07:44,440
>> Else vi kommer til at bruge tolower
ord beslag dvs.

134
00:07:44,440 --> 00:07:48,270
Så husk, at ord kan have vilkårlig
kapitalisering, og så vi

135
00:07:48,270 --> 00:07:51,590
ønsker at sikre, at vi bruger
et lille version af tingene.

136
00:07:51,590 --> 00:07:55,300
Og så trække fra, at små bogstaver
en til endnu en gang, give os

137
00:07:55,300 --> 00:07:57,940
alfabetisk position
af denne karakter.

138
00:07:57,940 --> 00:08:01,740
Så det kommer til at være vores indeks
i array Children.

139
00:08:01,740 --> 00:08:06,480
>> Og nu, hvis dette indeks i Barnet
array er null, det betyder at vi

140
00:08:06,480 --> 00:08:09,050
ikke længere kan fortsætte iteration
ned vores Trie.

141
00:08:09,050 --> 00:08:13,320
Hvis det er tilfældet, kan dette ord ikke
muligvis være i vores Trie, da hvis det

142
00:08:13,320 --> 00:08:18,000
var, ville det betyde, at der ville være en
sti ned til det ord, og du ville

143
00:08:18,000 --> 00:08:19,350
aldrig støder null.

144
00:08:19,350 --> 00:08:21,910
Så støder null, vi vender tilbage False.

145
00:08:21,910 --> 00:08:23,810
Ordet ikke er i ordbogen.

146
00:08:23,810 --> 00:08:28,200
Hvis det ikke var null, så vi kommer til at
fortsætte iteration, så vi vil

147
00:08:28,200 --> 00:08:33,150
til at opdatere vores markøren til at pege på, at
bestemt node på dette indeks.

148
00:08:33,150 --> 00:08:36,659
>> Så vi holder gør det hele
hele ordet.

149
00:08:36,659 --> 00:08:40,630
Hvis man antager, vi aldrig ramt null, at midler
vi var i stand til at komme igennem hele

150
00:08:40,630 --> 00:08:44,840
verden og finde en node i vores Trie,
men vi er ikke helt færdig endnu.

151
00:08:44,840 --> 00:08:46,350
Vi ønsker ikke bare at returnere sandt.

152
00:08:46,350 --> 00:08:51,400
Vi ønsker at vende tilbage cursor fejl ord
siden, så husk igen, hvis katten er ikke

153
00:08:51,400 --> 00:08:55,140
i vores ordbog og katastrofe er,
så vil vi med held komme igennem

154
00:08:55,140 --> 00:08:59,810
Ordet kat, men markøren ord
vil være False og ikke sandt.

155
00:08:59,810 --> 00:09:04,990
Så vender vi tilbage markøren ord for at angive
hvorvidt denne node er faktisk et ord,

156
00:09:04,990 --> 00:09:06,530
og det er det for check.

157
00:09:06,530 --> 00:09:08,310
>> Så lad os se størrelse.

158
00:09:08,310 --> 00:09:11,410
Så Størrelse kommer til at være temmelig nemt
siden, så husk i Load, er vi

159
00:09:11,410 --> 00:09:15,480
forøgelse ordbog størrelse for
hvert ord, som vi støder på.

160
00:09:15,480 --> 00:09:20,820
Så Størrelse er bare at vende tilbage
ordbog størrelse, og det er det.

161
00:09:20,820 --> 00:09:24,650
>> Okay, så endelig har vi Unload.

162
00:09:24,650 --> 00:09:29,050
Så Unload, vi kommer til at bruge en
rekursiv funktion til rent faktisk at gøre alt

163
00:09:29,050 --> 00:09:33,390
af arbejdet for os, så vores funktion
kommer til at hedde aflæsser.

164
00:09:33,390 --> 00:09:35,830
Hvad aflæsser gøre?

165
00:09:35,830 --> 00:09:40,640
Vi ser her, at Unloader kommer til at
gentage over alle børnene på

166
00:09:40,640 --> 00:09:45,810
dette knudepunkt, og hvis barnet
node ikke er nul, så vi kommer til at

167
00:09:45,810 --> 00:09:47,760
losse barneknudepunktet.

168
00:09:47,760 --> 00:09:52,070
>> Så det kommer til at rekursivt
losse alle vores børn.

169
00:09:52,070 --> 00:09:55,140
Når vi er sikre på, at alle vores børn
er blevet losset, så vi

170
00:09:55,140 --> 00:09:58,830
kan frigøre os selv, så losse selv.

171
00:09:58,830 --> 00:10:04,550
Så dette vil rekursivt losse
Hele Trie, og derefter en gang det er

172
00:10:04,550 --> 00:10:06,910
gjort, kan vi bare returnere sandt.

173
00:10:06,910 --> 00:10:09,770
Unload kan ikke undgå, men vi er
bare frigøre ting.

174
00:10:09,770 --> 00:10:12,985
Så når vi er færdig frigør
alt, returnere sandt.

175
00:10:12,985 --> 00:10:14,380
Og det er det.

176
00:10:14,380 --> 00:10:16,792
Mit navn er Rob, og dette
var [uhørligt].

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