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

2
00:00:00,530 --> 00:00:03,070
>> HÖGTALARE 1: Låt oss ge
denna lösning ett försök.

3
00:00:03,070 --> 00:00:07,130
Så låt oss ta en titt på vad vår
Struct node kommer att se ut.

4
00:00:07,130 --> 00:00:11,040
Här ser vi att vi kommer att ha en
Bool Word och en Struct nod stjärna

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

6
00:00:12,990 --> 00:00:18,720
Så första du kanske undrar,
varför är alfabetet hash definieras som 27?

7
00:00:18,720 --> 00:00:22,540
Tja, kom ihåg att vi kommer att behöva
att hantera apostrof, så

8
00:00:22,540 --> 00:00:25,610
det kommer att bli något av en speciell
fall under hela programmet.

9
00:00:25,610 --> 00:00:28,780
>> OK, nu, minns hur en
Trie fungerar faktiskt.

10
00:00:28,780 --> 00:00:33,420
Låt oss säga att vi indexera ordet katter,
sedan från roten av vår Trie,

11
00:00:33,420 --> 00:00:36,670
vi kommer att titta på Barnens
samling, och vi kommer att titta på

12
00:00:36,670 --> 00:00:42,250
index som motsvarar den bokstav
C. Så det vore index två.

13
00:00:42,250 --> 00:00:46,400
Så med tanke på att, kommer att ge oss
en ny nod, och sedan kommer vi

14
00:00:46,400 --> 00:00:47,880
arbeta från den noden.

15
00:00:47,880 --> 00:00:51,830
>> Så med tanke på den noden, vi är återigen
kommer att titta på barnen arrayen,

16
00:00:51,830 --> 00:00:56,170
och vi kommer att titta på index noll
att motsvara A i katt.

17
00:00:56,170 --> 00:01:01,240
Så då ska vi gå till den noden,
och med tanke på att nod, vi ska

18
00:01:01,240 --> 00:01:05,170
att titta på det index som motsvarar
till T. Och går vidare till den noden,

19
00:01:05,170 --> 00:01:09,590
Slutligen har vi helt tittat
genom våra ord Cat, och nu Bool

20
00:01:09,590 --> 00:01:15,020
Ordet är tänkt att indikera om
Detta givet ord är faktiskt ett ord.

21
00:01:15,020 --> 00:01:17,530
>> Så varför behöver vi den där speciella fall?

22
00:01:17,530 --> 00:01:21,680
Tja, tänk om ordet katastrof
är i vår ordlista, men

23
00:01:21,680 --> 00:01:24,120
ordet katt är inte?

24
00:01:24,120 --> 00:01:29,030
Så ser för att se om ordet katten är
i vår ordlista, kommer vi att

25
00:01:29,030 --> 00:01:34,880
framgångsrikt titta igenom indexen
C-A-T och nå en nod, men det är

26
00:01:34,880 --> 00:01:39,760
bara för att katastrofen hände
skapa noder på vägen från C-A-T alla

27
00:01:39,760 --> 00:01:41,250
vägen till slutet av ordet.

28
00:01:41,250 --> 00:01:46,520
Så Bool Word används indikerar huruvida
denna plats faktiskt

29
00:01:46,520 --> 00:01:48,370
indikerar ett ord.

30
00:01:48,370 --> 00:01:52,920
>> Okej, så nu när vi vet vad en
Trie kommer att se ut, låt oss titta

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

32
00:01:54,800 --> 00:01:58,670
Så Load kommer att returnera en Bool
för om vi lyckas eller

33
00:01:58,670 --> 00:02:03,020
utan framgång laddade ordbok och
detta kommer att bli ordlistan

34
00:02:03,020 --> 00:02:04,520
att vi vill läsa.

35
00:02:04,520 --> 00:02:08,310
Så första vi ska göra är att öppna
up som lexikon för läsning.

36
00:02:08,310 --> 00:02:12,060
Vi måste se till att vi inte misslyckas,
så om ordlistan var inte

37
00:02:12,060 --> 00:02:15,280
öppnat, återgår
Nej, i vilket fall vi kommer att

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

39
00:02:16,340 --> 00:02:21,290
Men om man antar att det framgångsrikt
öppnas, då kan vi faktiskt läsa

40
00:02:21,290 --> 00:02:22,310
genom ordboken.

41
00:02:22,310 --> 00:02:24,940
>> Så första vi tänker
vill göra är att vi har den här

42
00:02:24,940 --> 00:02:26,560
globala variabeln rot.

43
00:02:26,560 --> 00:02:30,250
Nu, root kommer att bli en nod stjärna.

44
00:02:30,250 --> 00:02:33,830
Det är högst upp på vår Trie att vi är
kommer att iterera igenom.

45
00:02:33,830 --> 00:02:38,200
Så första vi kommer att vilja
göra är att allokera minne för vår rot.

46
00:02:38,200 --> 00:02:42,040
>> Lägg märke till att vi använder calloc
funktion, vilket är i stort sett samma

47
00:02:42,040 --> 00:02:45,560
som Malloc funktion, förutom att det är
garanterat att återvända något som är

48
00:02:45,560 --> 00:02:47,240
helt nollställd ut.

49
00:02:47,240 --> 00:02:51,350
Så om vi använde Malloc, skulle vi behöva
gå igenom alla tips i vår

50
00:02:51,350 --> 00:02:54,220
nod och se till att
de är alla null.

51
00:02:54,220 --> 00:02:56,780
Så calloc kommer att göra det åt oss.

52
00:02:56,780 --> 00:03:00,390
>> Nu, precis som Malloc, vi måste göra
Se till att fördelningen är faktiskt

53
00:03:00,390 --> 00:03:01,580
framgångsrik.

54
00:03:01,580 --> 00:03:04,060
Om detta återvände null, då vi
måste stänga vår ordlista

55
00:03:04,060 --> 00:03:06,170
filen och returnera False.

56
00:03:06,170 --> 00:03:11,040
Så antar fördelningen var
framgångsrik, vi kommer att använda en nod

57
00:03:11,040 --> 00:03:14,340
stjärniga Markör att iterera
genom vårt Trie.

58
00:03:14,340 --> 00:03:17,950
Så vår rot kommer aldrig att förändras,
men vi kommer att använda markören till

59
00:03:17,950 --> 00:03:20,770
faktiskt gå från nod till nod.

60
00:03:20,770 --> 00:03:25,000
>> Okej, så i detta för en slinga, är vi
läsa igenom ordlistan filen,

61
00:03:25,000 --> 00:03:26,965
och vi använder vid fgetc.

62
00:03:26,965 --> 00:03:30,360
Så fgetc kommer att ta en enda
tecken från filen.

63
00:03:30,360 --> 00:03:33,430
Vi kommer att fortsätta att ta tag
tecken när vi inte når

64
00:03:33,430 --> 00:03:37,540
slutet av filen, så det finns
två fall som vi behöver för att hantera.

65
00:03:37,540 --> 00:03:41,640
Den första, om karaktären var inte en
ny rad, så vi vet om det var en ny

66
00:03:41,640 --> 00:03:44,480
linje, då är vi på väg att
gå vidare till ett nytt ord.

67
00:03:44,480 --> 00:03:49,300
Men om det nu inte var en ny linje, då
Här vill vi ta reda på

68
00:03:49,300 --> 00:03:52,440
index vi ska index i
i Barn array som

69
00:03:52,440 --> 00:03:53,890
vi tittat på tidigare.

70
00:03:53,890 --> 00:03:57,950
>> Så som jag sa tidigare, vi måste
specialfall apostrof.

71
00:03:57,950 --> 00:04:01,040
Lägg märke till att vi använder den ternära operatören
här, så vi kommer att läsa

72
00:04:01,040 --> 00:04:05,500
detta som om det tecken vi läser in var
en apostrof, då vi kommer att

73
00:04:05,500 --> 00:04:11,740
ställa index lika med alfabetet minus
1, som kommer att vara indexet 26.

74
00:04:11,740 --> 00:04:15,190
Annars, om det inte var en apostrof,
då ska vi ställa in index

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

76
00:04:17,820 --> 00:04:23,090
Så minns tillbaka från tidigare p-apparater,
c minus en kommer att ge oss

77
00:04:23,090 --> 00:04:27,470
alfabetisk position c, så om
c är bokstaven A, detta kommer

78
00:04:27,470 --> 00:04:28,770
ge oss index noll.

79
00:04:28,770 --> 00:04:32,180
För bokstaven B, skulle det ge
oss index 1, och så vidare.

80
00:04:32,180 --> 00:04:37,070
>> Så detta ger oss indexet i
Barn array som vi vill ha.

81
00:04:37,070 --> 00:04:42,540
Nu, om detta index är närvarande null
Barnen arrayen, innebär att det

82
00:04:42,540 --> 00:04:47,470
finns idag inte en nod från
den vägen, så vi måste avsätta en

83
00:04:47,470 --> 00:04:49,220
nod för den vägen.

84
00:04:49,220 --> 00:04:50,610
Det är vad vi gör här.

85
00:04:50,610 --> 00:04:54,650
Så vi kommer att, återigen, använd calloc
funktion så att vi inte har

86
00:04:54,650 --> 00:05:00,130
att noll alla pekare, och vi,
igen, måste kontrollera att calloc

87
00:05:00,130 --> 00:05:01,300
inte misslyckas.

88
00:05:01,300 --> 00:05:04,760
Om calloc gjorde misslyckas, då behöver vi
att lasta av allt, stänga vår

89
00:05:04,760 --> 00:05:06,880
lexikon, och returnera False.

90
00:05:06,880 --> 00:05:14,110
>> Så antar att det inte misslyckas, då
detta kommer att skapa ett nytt barn för oss,

91
00:05:14,110 --> 00:05:16,000
och då kommer vi att gå till det barnet.

92
00:05:16,000 --> 00:05:19,030
Vår Markören iterera
ner till det barnet.

93
00:05:19,030 --> 00:05:23,390
Nu, om detta inte var noll till att börja med,
sedan markören kan bara iterera

94
00:05:23,390 --> 00:05:26,650
ner till barnet utan att
behöva fördela någonting.

95
00:05:26,650 --> 00:05:30,790
Detta är fallet när vi först hände
att fördela ordet katt, och

96
00:05:30,790 --> 00:05:34,390
det betyder när vi går för att fördela
katastrof, vi inte behöver skapa

97
00:05:34,390 --> 00:05:35,720
noder för C-A-T igen.

98
00:05:35,720 --> 00:05:37,620
De finns redan.

99
00:05:37,620 --> 00:05:40,140
>> OK, så vad är det annat?

100
00:05:40,140 --> 00:05:44,600
Detta är det tillstånd där c var
snedstreck n, där c var en ny rad.

101
00:05:44,600 --> 00:05:47,780
Det innebär att vi har lyckats
avslutade ett ord.

102
00:05:47,780 --> 00:05:51,020
Nu, vad vi vill göra när vi
framgångsrikt slutfört ett ord?

103
00:05:51,020 --> 00:05:55,250
Vi kommer att använda detta ord fält
insidan av vår Struct nod.

104
00:05:55,250 --> 00:06:00,570
>> Vi vill ställa den till True, så att
indikerar att denna nod indikerar en

105
00:06:00,570 --> 00:06:03,320
framgångsrik ord en verklig ord.

106
00:06:03,320 --> 00:06:05,050
Nu ställer det till True.

107
00:06:05,050 --> 00:06:09,210
Vi vill återställa vår markören till punkt
till början av Trie igen.

108
00:06:09,210 --> 00:06:13,510
Och slutligen, öka vår ordlista
storlek eftersom vi hittat ett annat ord.

109
00:06:13,510 --> 00:06:16,450
>> Okej, så vi kommer att fortsätta göra
att läsa in tecknet genom

110
00:06:16,450 --> 00:06:21,960
karaktär, bygga nya noder i
vår Trie och för varje ord i

111
00:06:21,960 --> 00:06:26,810
ordbok, tills vi slutligen når c
lika EOF, i vilket fall, vi bryter

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

113
00:06:28,100 --> 00:06:31,110
Nu finns det två ärenden som
som vi kanske har drabbat EOF.

114
00:06:31,110 --> 00:06:35,680
Den första är om det fanns ett fel
läsa från filen, så om det fanns

115
00:06:35,680 --> 00:06:39,280
ett fel, vi måste göra den typiska
lasta av allt, stänga filen,

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

117
00:06:40,520 --> 00:06:43,870
Förutsatt att det inte var ett misstag, att
bara innebär att vi faktiskt träffade i slutet av

118
00:06:43,870 --> 00:06:47,820
filen, i vilket fall, vi stänger
filen och returnera sant eftersom vi

119
00:06:47,820 --> 00:06:51,010
lästs in i ordlistan
in i vår Trie.

120
00:06:51,010 --> 00:06:54,240
>> Okej, så nu ska vi
kolla Check.

121
00:06:54,240 --> 00:06:58,780
Om man tittar på Check-funktionen, ser vi
att Check kommer att returnera en Bool.

122
00:06:58,780 --> 00:07:03,740
Den returnerar True om detta ord att det är
överförs är i vår Trie.

123
00:07:03,740 --> 00:07:06,170
Den returnerar False annars.

124
00:07:06,170 --> 00:07:10,110
>> Så hur ska vi avgöra om
detta ord är i vår Trie?

125
00:07:10,110 --> 00:07:14,270
Vi ser här att, precis som tidigare,
vi kommer att använda markören för att iterera

126
00:07:14,270 --> 00:07:16,010
genom vårt Trie.

127
00:07:16,010 --> 00:07:20,650
Nu, här kommer vi att iterera
över hela vårt ord.

128
00:07:20,650 --> 00:07:24,680
Så iteration över ordet vi är
gått, vi kommer att bestämma

129
00:07:24,680 --> 00:07:29,280
index i Children array som
motsvarar ordet fäste i..

130
00:07:29,280 --> 00:07:34,150
Så detta kommer att se ut exakt som
Belastning, där om ordet fäste i är ett

131
00:07:34,150 --> 00:07:38,110
apostrof, då vill vi använda index
alfabetet minus 1 eftersom vi fastställt

132
00:07:38,110 --> 00:07:41,160
det är där vi ska
att lagra apostrofer.

133
00:07:41,160 --> 00:07:44,440
>> Annars ska vi använda tolower
Ordet Bracket I.

134
00:07:44,440 --> 00:07:48,270
Så kom ihåg att ord kan ha godtycklig
kapitalisering, och så vi

135
00:07:48,270 --> 00:07:51,590
vill se till att vi använder
ett gement version av saker.

136
00:07:51,590 --> 00:07:55,300
Och sedan subtrahera från den gemena
en att återigen ge oss

137
00:07:55,300 --> 00:07:57,940
alfabetisk ståndpunkt
av denna karaktär.

138
00:07:57,940 --> 00:08:01,740
Så det kommer att bli vårt index
i barn arrayen.

139
00:08:01,740 --> 00:08:06,480
>> Och nu, om det index till barnen
matris är noll, innebär att vi

140
00:08:06,480 --> 00:08:09,050
inte längre kan fortsätta iteration
ner vår Trie.

141
00:08:09,050 --> 00:08:13,320
Om så är fallet, detta ord kan inte
möjligen vara i vår Trie, eftersom om det

142
00:08:13,320 --> 00:08:18,000
var, skulle det innebära att det skulle finnas en
stig ner till det ordet, och du skulle

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

144
00:08:19,350 --> 00:08:21,910
Så möter null, återvänder vi False.

145
00:08:21,910 --> 00:08:23,810
Ordet finns inte i ordlistan.

146
00:08:23,810 --> 00:08:28,200
Om det inte var noll, då vi kommer att
fortsätta iteration, så vi ska

147
00:08:28,200 --> 00:08:33,150
att uppdatera vår markören för att peka på att
speciell nod vid detta index.

148
00:08:33,150 --> 00:08:36,659
>> Så vi fortsätter att göra det hela
hela ordet.

149
00:08:36,659 --> 00:08:40,630
Förutsatt att vi aldrig träffade noll, det betyder
vi kunde få igenom hela

150
00:08:40,630 --> 00:08:44,840
världen och hitta en nod i vår Trie,
men vi är inte riktigt klar ännu.

151
00:08:44,840 --> 00:08:46,350
Vi vill inte bara return true.

152
00:08:46,350 --> 00:08:51,400
Vi vill återvända markören fel ord
sedan, minns igen, om katten inte är

153
00:08:51,400 --> 00:08:55,140
i vår ordlista och katastrof är,
då kommer vi lyckas få igenom

154
00:08:55,140 --> 00:08:59,810
ordet katt, men markören ord
blir False och inte sant.

155
00:08:59,810 --> 00:09:04,990
Så vi återvänder markören ord för att indikera
huruvida denna nod är faktiskt ett ord,

156
00:09:04,990 --> 00:09:06,530
och det är den för kontroll.

157
00:09:06,530 --> 00:09:08,310
>> Så låt oss kolla storlek.

158
00:09:08,310 --> 00:09:11,410
Så storlek kommer att bli ganska lätt
sedan, minns i Load, vi är

159
00:09:11,410 --> 00:09:15,480
uppräkning ordbok storlek för
varje ord som vi stöter på.

160
00:09:15,480 --> 00:09:20,820
Så storlek är bara att återvända
dictionary storlek, och det är det.

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

162
00:09:24,650 --> 00:09:29,050
Så Unload, kommer vi att använda en
rekursiv funktion för att verkligen göra allt

163
00:09:29,050 --> 00:09:33,390
av arbetet åt oss, så att vår funktion
kommer att kallas Avlastnings.

164
00:09:33,390 --> 00:09:35,830
Vad Avlastnings göra?

165
00:09:35,830 --> 00:09:40,640
Vi ser här att Avlastnings kommer att
iterera över alla barnen på

166
00:09:40,640 --> 00:09:45,810
just denna nod, och om barnet
nod inte är null, så ska vi

167
00:09:45,810 --> 00:09:47,760
lossa barnet oden.

168
00:09:47,760 --> 00:09:52,070
>> Så detta kommer att rekursivt
lasta alla våra barn.

169
00:09:52,070 --> 00:09:55,140
När vi är säkra på att alla våra barn
har lossats, då vi

170
00:09:55,140 --> 00:09:58,830
kan frigöra oss, så lasta av oss själva.

171
00:09:58,830 --> 00:10:04,550
Så det här kommer rekursivt lasta av
Hela Trie, och sedan en gång det är

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

173
00:10:06,910 --> 00:10:09,770
Lasta kan inte misslyckas, vi är
bara frigöra saker.

174
00:10:09,770 --> 00:10:12,985
Så när vi är klara frigöra
allt, return true.

175
00:10:12,985 --> 00:10:14,380
Och det är det.

176
00:10:14,380 --> 00:10:16,792
Mitt namn är Rob, och detta
var [OHÖRBAR].

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