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

2
00:00:00,530 --> 00:00:03,070
>> SPEAKER 1: La oss gi
denne løsningen en prøve.

3
00:00:03,070 --> 00:00:07,130
Så la oss ta en titt på hva våre
Struct node vil se ut.

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

5
00:00:11,040 --> 00:00:12,990
Barn brakett alfabetet.

6
00:00:12,990 --> 00:00:18,720
Så første du kanskje lurer på,
hvorfor er alfabetet hash definert som 27?

7
00:00:18,720 --> 00:00:22,540
Vel, husk at vi kommer til å trenge
å være håndtering av apostrof, så

8
00:00:22,540 --> 00:00:25,610
som kommer til å være litt av en spesiell
tilfelle i hele dette programmet.

9
00:00:25,610 --> 00:00:28,780
>> OK, nå, husker hvordan en
Trie faktisk fungerer.

10
00:00:28,780 --> 00:00:33,420
La oss si at vi indekserer ordet katter,
deretter fra roten av vårt Trie,

11
00:00:33,420 --> 00:00:36,670
vi kommer til å se på barne
matrise, og vi kommer til å se på

12
00:00:36,670 --> 00:00:42,250
indeks som tilsvarer bokstaven
C. Så som ville være index to.

13
00:00:42,250 --> 00:00:46,400
Så gitt at, vil det gi oss
en ny node, og så får vi

14
00:00:46,400 --> 00:00:47,880
arbeide fra den noden.

15
00:00:47,880 --> 00:00:51,830
>> Så gitt at node, er vi nok en gang
kommer til å se på Barne-array,

16
00:00:51,830 --> 00:00:56,170
og vi kommer til å se på indeksen null
for å svare til en på katten.

17
00:00:56,170 --> 00:01:01,240
Så da skal vi gå til den noden,
og gitt at node, skal vi

18
00:01:01,240 --> 00:01:05,170
å se på indeksen som tilsvarer
til T. Og går videre til den noden,

19
00:01:05,170 --> 00:01:09,590
endelig, har vi helt sett
gjennom vårt ord Cat, og nå Bool

20
00:01:09,590 --> 00:01:15,020
Word er ment å indikere om
dette gitt ord er faktisk et ord.

21
00:01:15,020 --> 00:01:17,530
>> Så hvorfor trenger vi den spesielle saken?

22
00:01:17,530 --> 00:01:21,680
Vel, hva om ordet katastrofe
er i vår ordbok, men

23
00:01:21,680 --> 00:01:24,120
ordet katt er ikke?

24
00:01:24,120 --> 00:01:29,030
Så i jakt for å se om ordet katt er
i vår ordbok, kommer vi til å

25
00:01:29,030 --> 00:01:34,880
hell ser gjennom indeksene
C-A-T og nå en node, men det er

26
00:01:34,880 --> 00:01:39,760
bare fordi katastrofen skjedde med
lage noder på vei fra C-A-T all

27
00:01:39,760 --> 00:01:41,250
helt til slutten av ordet.

28
00:01:41,250 --> 00:01:46,520
Så Bool Word brukes indikere om
denne spesielle beliggenheten faktisk

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

30
00:01:48,370 --> 00:01:52,920
>> Ok, så nå som vi vet hva en
Trie kommer til å se ut, la oss se

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

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

33
00:01:58,670 --> 00:02:03,020
uten hell lastet ordbok og
dette kommer til å være ordlisten

34
00:02:03,020 --> 00:02:04,520
at vi ønsker å laste.

35
00:02:04,520 --> 00:02:08,310
Så det første vi kommer til å gjøre er å åpne
opp at ordboken for lesing.

36
00:02:08,310 --> 00:02:12,060
Vi må sørge for at vi ikke mislykkes,
slik at hvis det ikke var ordboken

37
00:02:12,060 --> 00:02:15,280
hell åpnet, vil den returnere
Nei, i så fall vi kommer til å

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

39
00:02:16,340 --> 00:02:21,290
Men forutsatt at det med hell
åpnet, så kan vi faktisk lese

40
00:02:21,290 --> 00:02:22,310
gjennom ordlisten.

41
00:02:22,310 --> 00:02:24,940
>> Så det første vi kommer til å
ønsker å gjøre er vi har dette

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

43
00:02:26,560 --> 00:02:30,250
Nå er roten kommer til å være en node stjerne.

44
00:02:30,250 --> 00:02:33,830
Det er toppen av vår Trie at vi er
kommer til å bli itera gjennom.

45
00:02:33,830 --> 00:02:38,200
Så det første vi kommer til å ønske å
gjøre er å allokere minne for vår rot.

46
00:02:38,200 --> 00:02:42,040
>> Legg merke til at vi bruker den Calloc
funksjon, som er utgangspunktet det samme

47
00:02:42,040 --> 00:02:45,560
som malloc funksjon, bortsett fra det er
garantert å returnere noe som er

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

49
00:02:47,240 --> 00:02:51,350
Så hvis vi brukte malloc, ville vi trenger å
gå gjennom alle pekere i vår

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

51
00:02:54,220 --> 00:02:56,780
Så Calloc vil gjøre det for oss.

52
00:02:56,780 --> 00:03:00,390
>> Nå, akkurat som malloc, trenger vi å gjøre
sikker på at tildeling er faktisk

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

54
00:03:01,580 --> 00:03:04,060
Hvis dette returneres null, så vi
må lukke vår ordbok

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

56
00:03:06,170 --> 00:03:11,040
Så forutsatt at tildelingen ble
vellykket, kommer vi til å bruke en node

57
00:03:11,040 --> 00:03:14,340
stjerners Cursor å iterere
gjennom vår Trie.

58
00:03:14,340 --> 00:03:17,950
Så vår root kommer aldri til å forandre seg,
men vi kommer til å bruke markøren til

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

60
00:03:20,770 --> 00:03:25,000
>> Greit, så i dette For loop, er vi
lese gjennom ordlistefilen,

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

62
00:03:26,965 --> 00:03:30,360
Så fgetc kommer til å ta en enkelt
karakter fra filen.

63
00:03:30,360 --> 00:03:33,430
Vi kommer til å fortsette å gripe
tegn, mens vi ikke når

64
00:03:33,430 --> 00:03:37,540
slutten av filen, slik at det er
to tilfeller vi trenger for å håndtere.

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

66
00:03:41,640 --> 00:03:44,480
linje, så vi er i ferd med å
gå videre til et nytt ord.

67
00:03:44,480 --> 00:03:49,300
Men forutsatt at det ikke var en ny linje, deretter
her, ønsker vi å finne ut av

68
00:03:49,300 --> 00:03:52,440
indeksen vi kommer til å indeksere inn
i Barn array som

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

70
00:03:53,890 --> 00:03:57,950
>> Så som jeg sa før, må vi
spesielt tilfelle apostrof.

71
00:03:57,950 --> 00:04:01,040
Legg merke til at vi bruker den trefoldig operatøren
her, så vi kommer til å lese

72
00:04:01,040 --> 00:04:05,500
dette som om karakteren vi leste i var
en apostrof, så vi kommer til å

73
00:04:05,500 --> 00:04:11,740
satt indeks lik alfabetet minus
1, som vil være indeksen 26..

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

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

76
00:04:17,820 --> 00:04:23,090
Så husker tilbake fra forrige p-apparater,
c minus en kommer til å gi oss

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

78
00:04:27,470 --> 00:04:28,770
gi oss indeks null.

79
00:04:28,770 --> 00:04:32,180
For bokstaven B, vil det gi
oss indeksen 1, og så videre.

80
00:04:32,180 --> 00:04:37,070
>> Så dette gir oss indeksen inn i
Barn array som vi ønsker.

81
00:04:37,070 --> 00:04:42,540
Nå, hvis denne indeksen er for tiden null i
Barna array, betyr det at

82
00:04:42,540 --> 00:04:47,470
en node for øyeblikket ikke eksisterer fra
den veien, så vi trenger å tildele en

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

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

85
00:04:50,610 --> 00:04:54,650
Så vi kommer til, igjen, bruker Calloc
funksjon slik at vi ikke har

86
00:04:54,650 --> 00:05:00,130
til null ut alle tips, og vi,
igjen, må du sjekke at Calloc

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

88
00:05:01,300 --> 00:05:04,760
Hvis Calloc gjorde mislykkes, så vi trenger
å lesse alt, lukke våre

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

90
00:05:06,880 --> 00:05:14,110
>> Så forutsatt at det ikke mislykkes, da
Dette vil skape et nytt barn for oss,

91
00:05:14,110 --> 00:05:16,000
og da vil vi gå til det barnet.

92
00:05:16,000 --> 00:05:19,030
Vår markøren vil iterere
ned til at barnet.

93
00:05:19,030 --> 00:05:23,390
Nå, hvis dette ikke var null til å begynne med,
deretter markøren kan bare iterere

94
00:05:23,390 --> 00:05:26,650
ned til at barnet uten å faktisk
å måtte fordele noe.

95
00:05:26,650 --> 00:05:30,790
Dette er tilfelle hvor vi først skjedd
å fordele ordet katt, og

96
00:05:30,790 --> 00:05:34,390
det betyr at når vi går å tildele
katastrofe, trenger vi ikke å skape

97
00:05:34,390 --> 00:05:35,720
noder for C-A-T på nytt.

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

99
00:05:37,620 --> 00:05:40,140
>> OK, så hva er dette Else?

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

101
00:05:44,600 --> 00:05:47,780
Dette betyr at vi har lykkes
gjennomført et ord.

102
00:05:47,780 --> 00:05:51,020
Nå, hva vi ønsker å gjøre når vi
fullført et ord?

103
00:05:51,020 --> 00:05:55,250
Vi kommer til å bruke dette ordet feltet
innsiden av våre Struct node.

104
00:05:55,250 --> 00:06:00,570
>> Vi ønsker å sette det til True, slik at
indikerer at denne noden indikerer en

105
00:06:00,570 --> 00:06:03,320
vellykket ord en faktisk ord.

106
00:06:03,320 --> 00:06:05,050
Nå satt det til True.

107
00:06:05,050 --> 00:06:09,210
Vi ønsker å tilbakestille vår markøren til punkt
til begynnelsen av den Trie nytt.

108
00:06:09,210 --> 00:06:13,510
Og til slutt, øke vår ordbok
størrelse siden vi fant et annet ord.

109
00:06:13,510 --> 00:06:16,450
>> Greit, så vi kommer til å fortsette å gjøre
at lesing i karakter etter

110
00:06:16,450 --> 00:06:21,960
karakter, bygging av nye noder i
vår Trie og for hvert ord i

111
00:06:21,960 --> 00:06:26,810
ordbok, før vi endelig nå c
tilsvarer EOF, i så fall, vi bryte

112
00:06:26,810 --> 00:06:28,100
ut av filen.

113
00:06:28,100 --> 00:06:31,110
Nå er det to tilfeller i henhold
som vi kan ha truffet EOF.

114
00:06:31,110 --> 00:06:35,680
Den første er om det var en feil
lesing fra filen, så hvis det var

115
00:06:35,680 --> 00:06:39,280
en feil, må vi gjøre den 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
Antar det ikke var en feil, at
betyr bare at vi faktisk traff slutten av

118
00:06:43,870 --> 00:06:47,820
filen, og i så fall, vi lukker
fil og returnere sant siden vi

119
00:06:47,820 --> 00:06:51,010
lastet ordlisten
inn i vår Trie.

120
00:06:51,010 --> 00:06:54,240
>> Greit, så la oss nå
sjekk ut Check.

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

122
00:06:58,780 --> 00:07:03,740
Den returnerer Sann hvis dette ordet at det er
blir vedtatt er i vår Trie.

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

124
00:07:06,170 --> 00:07:10,110
>> Så hvordan skal vi finne ut om
dette ordet er i vår Trie?

125
00:07:10,110 --> 00:07:14,270
Vi ser her at, akkurat som før,
vi kommer til å bruke markøren til å reagere

126
00:07:14,270 --> 00:07:16,010
gjennom vår Trie.

127
00:07:16,010 --> 00:07:20,650
Nå, her kommer vi til å reagere
over vår hele ord.

128
00:07:20,650 --> 00:07:24,680
Så itera over ordet vi er
passert, kommer vi til å bestemme

129
00:07:24,680 --> 00:07:29,280
indeksen inn Barna array som
tilsvarer ordet brakett jeg.

130
00:07:29,280 --> 00:07:34,150
Så dette kommer til å se ut akkurat som
Load, der hvis ordet brakett jeg er en

131
00:07:34,150 --> 00:07:38,110
apostrof, da vi ønsker å bruke indeksen
alfabetet minus ett fordi vi bestemt

132
00:07:38,110 --> 00:07:41,160
det er der vi skal
til å lagre apostrofer.

133
00:07:41,160 --> 00:07:44,440
>> Else vi kommer til å bruke tolower
Ordet brakett jeg.

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

135
00:07:48,270 --> 00:07:51,590
ønsker å sørge for at vi bruker
inn en liten versjon av ting.

136
00:07:51,590 --> 00:07:55,300
Og så trekke fra det med små bokstaver
en til, nok en gang, gi oss

137
00:07:55,300 --> 00:07:57,940
alfabetisk stilling
av det tegnet.

138
00:07:57,940 --> 00:08:01,740
Så det kommer til å bli vår hovedside
inn i Children array.

139
00:08:01,740 --> 00:08:06,480
>> Og nå, hvis at indeksen inn Barna
matrise er null, betyr det at vi

140
00:08:06,480 --> 00:08:09,050
kan ikke lenger fortsette itera
ned vår Trie.

141
00:08:09,050 --> 00:08:13,320
Hvis det er tilfelle, dette ordet kan ikke
muligens være i vår Trie, siden hvis det

142
00:08:13,320 --> 00:08:18,000
ble, som ville bety at det ville være en
sti ned til det ordet, og du ville

143
00:08:18,000 --> 00:08:19,350
aldri støter på null.

144
00:08:19,350 --> 00:08:21,910
Så møter null, returnerer vi False.

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

146
00:08:23,810 --> 00:08:28,200
Hvis det ikke var null, så vi kommer til å
fortsetter itera, så vi kommer

147
00:08:28,200 --> 00:08:33,150
å oppdatere vår markøren til å peke på at
spesiell knute på at indeksen.

148
00:08:33,150 --> 00:08:36,659
>> Så vi fortsette med det hele
hele ordet.

149
00:08:36,659 --> 00:08:40,630
Antar vi aldri treffer null, det betyr
vi var i stand til å komme gjennom hele

150
00:08:40,630 --> 00:08:44,840
verden og finne en node i vår Trie,
men vi er ikke helt ferdig ennå.

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

152
00:08:46,350 --> 00:08:51,400
Vi ønsker å returnere markøren feil ord
siden, husker igjen, hvis katten er ikke

153
00:08:51,400 --> 00:08:55,140
i vår ordbok og katastrofe er,
da vil vi lykkes å komme gjennom

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

155
00:08:59,810 --> 00:09:04,990
Så vi tilbake markøren ord for å indikere
vidt denne noden er faktisk et ord,

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

157
00:09:06,530 --> 00:09:08,310
>> Så la oss sjekke ut størrelse.

158
00:09:08,310 --> 00:09:11,410
Så størrelse kommer til å være ganske lett
siden, husker i Load, er vi

159
00:09:11,410 --> 00:09:15,480
økes ordbok størrelse for
hvert ord som vi møter.

160
00:09:15,480 --> 00:09:20,820
Så størrelse er bare kommer til å returnere
ordbok størrelse, og det er det.

161
00:09:20,820 --> 00:09:24,650
>> Greit, så til slutt, har vi losse.

162
00:09:24,650 --> 00:09:29,050
Så losse, kommer vi til å bruke en
rekursiv funksjon å faktisk gjøre alt

163
00:09:29,050 --> 00:09:33,390
av arbeidet for oss, så vår funksjon
kommer til å bli kalt losser.

164
00:09:33,390 --> 00:09:35,830
Hva er losser kommer til å gjøre?

165
00:09:35,830 --> 00:09:40,640
Vi ser her at losser kommer til å
iterere over alle barna på

166
00:09:40,640 --> 00:09:45,810
denne spesielle noden, og dersom barnet
Noden er ikke null, så vi kommer til å

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

168
00:09:47,760 --> 00:09:52,070
>> Så dette kommer til å rekursivt
losse alle våre barn.

169
00:09:52,070 --> 00:09:55,140
Når vi er sikker på at alle våre barn
har blitt losset, så vi

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

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

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

173
00:10:06,910 --> 00:10:09,770
Losse kan ikke mislykkes, vi er
bare frigjøre ting.

174
00:10:09,770 --> 00:10:12,985
Så når vi er ferdig å frigjøre
alt, returnere true.

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

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

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