1
00:00:00,000 --> 00:00:12,350
>> [MUSIK SPELA]

2
00:00:12,350 --> 00:00:13,050
>> ROB BOWDEN: Hej.

3
00:00:13,050 --> 00:00:13,640
Jag är Rob.

4
00:00:13,640 --> 00:00:16,210
Och låt oss denna lösning ut.

5
00:00:16,210 --> 00:00:20,070
Så här är vi kommer att genomföra
en allmän tabell.

6
00:00:20,070 --> 00:00:24,090
Vi ser att struct nod i vår
tabellen kommer att se ut så här.

7
00:00:24,090 --> 00:00:28,710
Så det kommer att ha en char ord
matris med storlek LÄNGD + 1.

8
00:00:28,710 --> 00:00:32,259
Glöm inte + 1, eftersom den maximala
ord i ordlistan är 45

9
00:00:32,259 --> 00:00:33,130
tecken.

10
00:00:33,130 --> 00:00:37,070
Och sedan ska vi behöva en extra
tecknet för backslash noll.

11
00:00:37,070 --> 00:00:40,870
>> Och sedan vår Hashtable i varje
skopan kommer att lagra en

12
00:00:40,870 --> 00:00:42,320
länkad lista av noder.

13
00:00:42,320 --> 00:00:44,420
Vi gör inte linjär sondering här.

14
00:00:44,420 --> 00:00:48,430
Och så för att länka till nästa
inslag i hinken, vi behöver en

15
00:00:48,430 --> 00:00:50,390
struct node * nästa.

16
00:00:50,390 --> 00:00:51,110
OK.

17
00:00:51,110 --> 00:00:53,090
Så det är vad en nod ser ut.

18
00:00:53,090 --> 00:00:56,180
>> Nu här är förklaringen
av vår hashtable.

19
00:00:56,180 --> 00:00:59,640
Det kommer att ha 16.834 hinkar.

20
00:00:59,640 --> 00:01:01,910
Men den siffran spelar egentligen ingen roll.

21
00:01:01,910 --> 00:01:05,450
Och slutligen, kommer vi att ha
globala variabeln hashtable storlek, vilket

22
00:01:05,450 --> 00:01:07,000
kommer att börja som noll.

23
00:01:07,000 --> 00:01:10,760
Och det kommer att hålla reda på hur
många ord i vår ordlista.

24
00:01:10,760 --> 00:01:13,710
>> Så låt oss ta en titt på last.

25
00:01:13,710 --> 00:01:16,390
Lägg märke till att lasten, returneras en bool.

26
00:01:16,390 --> 00:01:20,530
Du return true om det var lyckat
laddad, och i annat fall false.

27
00:01:20,530 --> 00:01:23,990
Och det tar en const char * ordbok,
vilket är ordboken

28
00:01:23,990 --> 00:01:25,280
att vi vill öppna.

29
00:01:25,280 --> 00:01:27,170
Så det är det första
vi ska göra.

30
00:01:27,170 --> 00:01:29,500
>> Vi ska fopen den
ordlista för läsning.

31
00:01:29,500 --> 00:01:31,680
Och vi kommer att behöva göra
Se till att det lyckades.

32
00:01:31,680 --> 00:01:35,920
Så om det returneras NULL, sedan gjorde vi inte
framgångsrikt öppna ordlistan.

33
00:01:35,920 --> 00:01:37,440
Och vi måste returnera false.

34
00:01:37,440 --> 00:01:41,580
Men om man antar att den gjorde med framgång
öppen, då vill vi att läsa

35
00:01:41,580 --> 00:01:42,400
ordboken.

36
00:01:42,400 --> 00:01:46,450
Så håll looping tills vi hittar några
anledning att bryta sig ut ur denna slinga,

37
00:01:46,450 --> 00:01:47,570
som vi får se.

38
00:01:47,570 --> 00:01:48,920
Så håll looping.

39
00:01:48,920 --> 00:01:51,780
>> Och nu ska vi
malloc en enda nod.

40
00:01:51,780 --> 00:01:54,020
Och naturligtvis behöver vi
till luft kontrollera igen.

41
00:01:54,020 --> 00:01:58,680
Så om mallocing inte lyckades, sedan
vi önskar att lasta av någon nod som vi

42
00:01:58,680 --> 00:02:02,590
hänt med malloc innan, stänger
ordbok och returnera false.

43
00:02:02,590 --> 00:02:06,830
Men ignorera det, förutsatt att vi
lyckats, då vill vi använda fscanf

44
00:02:06,830 --> 00:02:12,400
att läsa ett enda ord från vår
dictionary i vårt nod.

45
00:02:12,400 --> 00:02:17,940
Så kom ihåg att posten> Ordet är rödingen
ordet buffert av storlek lenghth + 1

46
00:02:17,940 --> 00:02:20,300
att vi kommer att lagra ord i.

47
00:02:20,300 --> 00:02:25,070
>> Så fscanf kommer att återvända 1, så länge
eftersom det kunde framgångsrikt

48
00:02:25,070 --> 00:02:26,750
läsa ett ord från filen.

49
00:02:26,750 --> 00:02:30,460
Om antingen ett fel inträffar, eller vi
når slutet av filen, det

50
00:02:30,460 --> 00:02:31,950
kommer inte tillbaka 1.

51
00:02:31,950 --> 00:02:35,180
I vilket fall är det inte återvänder 1,
vi äntligen kommer att bryta sig ur

52
00:02:35,180 --> 00:02:37,280
detta medan slinga.

53
00:02:37,280 --> 00:02:42,770
Så vi ser att när vi har lyckats
läsa ett ord i

54
00:02:42,770 --> 00:02:48,270
entry> ord, då vi ska det
ordet med vår hashfunktion.

55
00:02:48,270 --> 00:02:49,580
>> Låt oss ta en titt på
hashfunktionen.

56
00:02:49,580 --> 00:02:52,430

57
00:02:52,430 --> 00:02:55,610
Så du behöver egentligen inte
att förstå detta.

58
00:02:55,610 --> 00:02:59,460
Och faktiskt vi bara drog denna hash
fungera från Internet.

59
00:02:59,460 --> 00:03:04,010
Det enda du behöver för att känna igen är
att det tar en const char * ord.

60
00:03:04,010 --> 00:03:08,960
Så det tar en sträng som indata, och
returnera en unsigned int som produktion.

61
00:03:08,960 --> 00:03:12,360
Så det är allt en hash-funktion, är det
tar i en ingång och ger dig en

62
00:03:12,360 --> 00:03:14,490
index i hashtable.

63
00:03:14,490 --> 00:03:18,530
>> Lägg märke till att vi Moding av NUM_BUCKETS,
så att värdet som returneras

64
00:03:18,530 --> 00:03:21,730
faktiskt är ett index in i hashtable
och inte index bortom

65
00:03:21,730 --> 00:03:24,320
gränserna för arrayen.

66
00:03:24,320 --> 00:03:28,060
Så med tanke på att funktionen ska vi
att hash det ord som vi läser

67
00:03:28,060 --> 00:03:29,390
ordboken.

68
00:03:29,390 --> 00:03:31,700
Och sedan ska vi använda
som hash att infoga

69
00:03:31,700 --> 00:03:33,750
inträde i hashtable.

70
00:03:33,750 --> 00:03:38,520
>> Nu hashtable hash är den aktuella
lista länkad i tabellen.

71
00:03:38,520 --> 00:03:41,410
Och det är mycket möjligt
att det bara är NULL.

72
00:03:41,410 --> 00:03:44,960
Vi vill sätta in vårt inträde på
början av denna länkade lista.

73
00:03:44,960 --> 00:03:48,600
Och så ska vi ha vår nuvarande
inkörsport till vad hashtable

74
00:03:48,600 --> 00:03:50,380
för närvarande pekar på.

75
00:03:50,380 --> 00:03:53,310
Och då kommer vi att lagra,
i hashtable vid

76
00:03:53,310 --> 00:03:55,350
hash, den aktuella posten.

77
00:03:55,350 --> 00:03:59,320
Så dessa två linjer framgångsrikt sätt in
posten i början av

78
00:03:59,320 --> 00:04:02,260
länkade listan vid detta index
i hashtable.

79
00:04:02,260 --> 00:04:04,900
>> När vi är klara med det, vi vet
att vi hittat ett annat ord i

80
00:04:04,900 --> 00:04:07,790
lexikon, och vi öka igen.

81
00:04:07,790 --> 00:04:13,960
Så vi fortsätter att göra det tills fscanf
äntligen tillbaka något icke-1 vid

82
00:04:13,960 --> 00:04:16,950
vilken punkt ihåg att
Vi måste frigöra posten.

83
00:04:16,950 --> 00:04:19,459
Så här uppe malloced vi en post.

84
00:04:19,459 --> 00:04:21,329
Och vi försökte läsa något
från ordlistan.

85
00:04:21,329 --> 00:04:23,910
Och vi har inte lyckats läsa
något från ordlistan, i

86
00:04:23,910 --> 00:04:26,650
då vi måste frigöra posten
att vi aldrig tas i

87
00:04:26,650 --> 00:04:29,140
hashtable, och slutligen gå av.

88
00:04:29,140 --> 00:04:32,750
>> När vi bryter ut måste vi se, ja,
vi bryta ut eftersom det

89
00:04:32,750 --> 00:04:34,360
var ett fel vid läsning från filen?

90
00:04:34,360 --> 00:04:37,120
Eller har vi bryta ut, eftersom vi
nått slutet av filen?

91
00:04:37,120 --> 00:04:39,480
Om det fanns ett fel, då
Vi vill returnera false.

92
00:04:39,480 --> 00:04:40,930
Eftersom lasten inte lyckades.

93
00:04:40,930 --> 00:04:43,890
Och i processen vi vill lasta
alla de ord som vi läser in och

94
00:04:43,890 --> 00:04:45,670
stäng ordlistefilen.

95
00:04:45,670 --> 00:04:48,740
>> Förutsatt att vi lyckades, då vi bara
ändå måste stänga i ordlistan

96
00:04:48,740 --> 00:04:53,040
fil, och slutligen återvänder sant eftersom vi
lästs in i ordlistan.

97
00:04:53,040 --> 00:04:54,420
Och det är det för last.

98
00:04:54,420 --> 00:04:59,020
Så nu kontrollera, med tanke på en laddad hashtable,
kommer att se ut så här.

99
00:04:59,020 --> 00:05:03,140
Så kolla, den returnerar en bool, som är
kommer att ange om det gått

100
00:05:03,140 --> 00:05:07,530
i char * ord, om det gått
i strängen är i vår ordlista.

101
00:05:07,530 --> 00:05:09,890
Så om det är i ordlistan,
om det är i vår hashtable,

102
00:05:09,890 --> 00:05:11,170
vi återkommer sant.

103
00:05:11,170 --> 00:05:13,380
Och om det inte är, kommer vi att returnera false.

104
00:05:13,380 --> 00:05:17,740
>> Med tanke på detta gick i ord, vi är
kommer att hash ordet.

105
00:05:17,740 --> 00:05:22,110
Nu en viktig sak att inse är
att vi i lasten visste, att alla av

106
00:05:22,110 --> 00:05:23,820
ord vi kommer att vara gemener.

107
00:05:23,820 --> 00:05:25,820
Men här är vi inte så säker.

108
00:05:25,820 --> 00:05:29,510
Om vi ​​tar en titt på hash-funktion,
vår hashfunktion faktiskt

109
00:05:29,510 --> 00:05:32,700
är lägre hölje varje tecken
av ordet.

110
00:05:32,700 --> 00:05:37,940
Så oavsett kapitalisering av
ord, är vår hashfunktion retur

111
00:05:37,940 --> 00:05:42,270
samma index för oavsett den
aktivering är, eftersom det skulle ha

112
00:05:42,270 --> 00:05:45,280
returneras för en helt gement
version av ordet.

113
00:05:45,280 --> 00:05:46,600
Alright.

114
00:05:46,600 --> 00:05:49,790
Det är vårt index är i
Hashtable för detta ord.

115
00:05:49,790 --> 00:05:52,940
>> Nu är detta för slinga kommer att
iterera över den länkade listan

116
00:05:52,940 --> 00:05:55,000
Det var vid detta index.

117
00:05:55,000 --> 00:05:59,610
Så märker vi att initiera inresa
att peka på detta index.

118
00:05:59,610 --> 00:06:02,750
Vi kommer att fortsätta
medan posten! = NULL.

119
00:06:02,750 --> 00:06:07,770
Och kom ihåg att uppdatera pekaren
i vår länkad lista posten = entry> nästa.

120
00:06:07,770 --> 00:06:14,400
Så har vår nuvarande ingång till
nästa objekt i den länkade listan.

121
00:06:14,400 --> 00:06:19,250
>> Så för varje post i den länkade listan,
vi kommer att använda strcasecmp.

122
00:06:19,250 --> 00:06:20,330
Det är inte strcomp.

123
00:06:20,330 --> 00:06:23,780
Därför att en gång, vill vi
göra saker fallet okänsligt.

124
00:06:23,780 --> 00:06:27,870
Så vi använder strcasecmp att jämföra
ord som fick passera genom denna

125
00:06:27,870 --> 00:06:31,860
funktion mot ordet
det är i denna post.

126
00:06:31,860 --> 00:06:35,570
Om den returnerar noll, betyder att det inte var
en match, i vilket fall vi vill

127
00:06:35,570 --> 00:06:36,630
return true.

128
00:06:36,630 --> 00:06:39,590
Vi fann framgångsrikt
ordet i vår hashtable.

129
00:06:39,590 --> 00:06:43,040
>> Om det fanns inte en match, då är vi
gå till loop igen och titta på

130
00:06:43,040 --> 00:06:43,990
nästa post.

131
00:06:43,990 --> 00:06:47,640
Och vi kommer att fortsätta looping medan det
är poster i detta länkad lista.

132
00:06:47,640 --> 00:06:50,160
Vad händer om vi bryter
ur detta för loop?

133
00:06:50,160 --> 00:06:55,110
Det betyder att vi inte hittade en post som
matchas detta ord, i vilket fall

134
00:06:55,110 --> 00:07:00,220
vi returnera false för att ange att vår
hashtable inte innehöll detta ord.

135
00:07:00,220 --> 00:07:02,540
Och det är en check.

136
00:07:02,540 --> 00:07:04,790
>> Så låt oss ta en titt på storlek.

137
00:07:04,790 --> 00:07:06,970
Nu storlek kommer att vara ganska enkelt.

138
00:07:06,970 --> 00:07:11,080
Sedan minns i lasten, för varje ord
vi hittade, vi ökas en global

139
00:07:11,080 --> 00:07:12,880
variabel hashtable storlek.

140
00:07:12,880 --> 00:07:16,480
Så storleksfunktionen är bara att gå
att återvända globala variabeln.

141
00:07:16,480 --> 00:07:18,150
Och det är det.

142
00:07:18,150 --> 00:07:22,300
>> Nu äntligen, måste vi lasta av
dictionary när allt är gjort.

143
00:07:22,300 --> 00:07:25,340
Så hur ska vi göra det?

144
00:07:25,340 --> 00:07:30,440
Just här vi looping över
alla segment av vårt bord.

145
00:07:30,440 --> 00:07:33,240
Så det finns NUM_BUCKETS hinkar.

146
00:07:33,240 --> 00:07:37,410
Och för varje länkad lista i vår
hashtable, vi ska slinga över

147
00:07:37,410 --> 00:07:41,070
helheten av den länkade listan,
frigöra varje element.

148
00:07:41,070 --> 00:07:42,900
>> Nu måste vi vara försiktiga.

149
00:07:42,900 --> 00:07:47,910
Så här har vi en temporär variabel
som är lagra pekaren till nästa

150
00:07:47,910 --> 00:07:49,730
elementet i den länkade listan.

151
00:07:49,730 --> 00:07:52,140
Och sedan ska vi gratis
det aktuella elementet.

152
00:07:52,140 --> 00:07:55,990
Vi måste vara säkra på att vi gör detta eftersom vi
kan inte bara befria det aktuella elementet

153
00:07:55,990 --> 00:07:59,180
och sedan försöka komma till nästa pekare,
sedan när vi har befriat det,

154
00:07:59,180 --> 00:08:00,870
minnet blir ogiltig.

155
00:08:00,870 --> 00:08:04,990
>> Så vi måste hålla runt en pekare till
nästa element, då vi kan frigöra

156
00:08:04,990 --> 00:08:08,360
aktuellt element, och då kan vi uppdatera
vår nuvarande elementet att peka på

157
00:08:08,360 --> 00:08:09,550
nästa element.

158
00:08:09,550 --> 00:08:12,800
Vi ska slinga medan det finns inslag
i detta länkad lista.

159
00:08:12,800 --> 00:08:15,620
Vi ska göra det för alla länkade
listor i hashtable.

160
00:08:15,620 --> 00:08:19,460
Och när vi är klara med det, vi har
helt lossas hashtable, och

161
00:08:19,460 --> 00:08:20,190
vi är klara.

162
00:08:20,190 --> 00:08:23,200
Så det är omöjligt att lossa
att någonsin returnera false.

163
00:08:23,200 --> 00:08:26,470
Och när vi är klara, vi
bara return true.

164
00:08:26,470 --> 00:08:29,000
>> Låt oss ge denna lösning ett försök.

165
00:08:29,000 --> 00:08:33,070
Så låt oss ta en titt på vad vår
struct node kommer att se ut.

166
00:08:33,070 --> 00:08:36,220
Här ser vi att vi kommer att ha en bool
ord och en struct node * barn

167
00:08:36,220 --> 00:08:37,470
fäste alfabetet.

168
00:08:37,470 --> 00:08:38,929

169
00:08:38,929 --> 00:08:42,020
Så det första du kan vara
undrar, varför är ALFABETET

170
00:08:42,020 --> 00:08:44,660
ed definierad som 27?

171
00:08:44,660 --> 00:08:47,900
Tja, kom ihåg att vi kommer att behöva
att hantera apostrof.

172
00:08:47,900 --> 00:08:51,910
Så det kommer att bli något av en
specialfall under hela detta program.

173
00:08:51,910 --> 00:08:54,710
>> Nu minns hur en trie
faktiskt fungerar.

174
00:08:54,710 --> 00:08:59,380
Låt oss säga att vi indexera ordet
"katter". Sedan från roten av trie,

175
00:08:59,380 --> 00:09:02,610
vi kommer att titta på barnen
samling, och vi kommer att titta på

176
00:09:02,610 --> 00:09:08,090
index som motsvarar den bokstav
C. Så det kommer att indexeras 2.

177
00:09:08,090 --> 00:09:11,530
Så med tanke på att, som kommer
ge oss en ny nod.

178
00:09:11,530 --> 00:09:13,820
Och så kommer vi arbeta utifrån den noden.

179
00:09:13,820 --> 00:09:17,770
>> Så med tanke på den noden, vi är återigen
kommer att titta på barnen arrayen.

180
00:09:17,770 --> 00:09:22,110
Och vi kommer att titta på index noll
att motsvara A i katt.

181
00:09:22,110 --> 00:09:27,170
Så då ska vi gå till den noden,
och med tanke på att noden ska vi

182
00:09:27,170 --> 00:09:31,090
att titta på slutet är det en motsvarar
till T. Och går vidare till den noden,

183
00:09:31,090 --> 00:09:35,530
Slutligen har vi helt tittat
genom vårt ord "cat". Och nu bool

184
00:09:35,530 --> 00:09:40,960
Ordet är tänkt att indikera om
Detta givet ord är faktiskt ett ord.

185
00:09:40,960 --> 00:09:43,470
>> Så varför behöver vi den där speciella fall?

186
00:09:43,470 --> 00:09:47,700
Väl vad ordet "katastrof"
är enligt vår ordbok, men den

187
00:09:47,700 --> 00:09:50,150
ordet "katt" är inte?

188
00:09:50,150 --> 00:09:54,580
Så och titta för att se om ordet "katt"
är i vår ordlista, vi är

189
00:09:54,580 --> 00:09:59,970
kommer att lyckas titta igenom
indexen C-A-T i regionen nod.

190
00:09:59,970 --> 00:10:04,290
Men det är bara för katastrof
råkade skapa noder på vägen

191
00:10:04,290 --> 00:10:07,190
från C-A-T, hela vägen till
i slutet av ordet.

192
00:10:07,190 --> 00:10:12,020
Så bool ordet används för att indikera huruvida
denna särskilda plats

193
00:10:12,020 --> 00:10:14,310
faktiskt visar ett ord.

194
00:10:14,310 --> 00:10:15,140
>> Okej.

195
00:10:15,140 --> 00:10:19,310
Så nu när vi vet vad det trie är
kommer att se ut, låt oss titta på det

196
00:10:19,310 --> 00:10:20,730
ladda funktion.

197
00:10:20,730 --> 00:10:24,610
Så belastningen kommer att returnera en bool
för om vi lyckas eller

198
00:10:24,610 --> 00:10:26,720
utan framgång laddat ordlistan.

199
00:10:26,720 --> 00:10:30,460
Och det kommer att bli i ordlistan
att vi vill läsa.

200
00:10:30,460 --> 00:10:33,930
>> Så första vi ska göra är att öppna
up som lexikon för läsning.

201
00:10:33,930 --> 00:10:36,160
Och vi måste se till
vi inte misslyckas.

202
00:10:36,160 --> 00:10:39,580
Så om ordlistan var inte
öppnat, återgår

203
00:10:39,580 --> 00:10:42,400
null, i vilket fall vi är
kommer att returnera false.

204
00:10:42,400 --> 00:10:47,230
Men om man antar att det framgångsrikt
öppnas, då kan vi faktiskt läsa

205
00:10:47,230 --> 00:10:48,220
genom ordboken.

206
00:10:48,220 --> 00:10:50,880
>> Så första vi tänker
vill göra är att vi har den här

207
00:10:50,880 --> 00:10:52,500
globala variabeln rot.

208
00:10:52,500 --> 00:10:56,190
Nu root kommer att bli en nod *.

209
00:10:56,190 --> 00:10:59,760
Det är högst upp på vår trie att vi är
kommer att iterera igenom.

210
00:10:59,760 --> 00:11:02,660
Så det första som vi ska
att vilja göra är att fördela

211
00:11:02,660 --> 00:11:04,140
minne för vår rot.

212
00:11:04,140 --> 00:11:07,980
Lägg märke till att vi använder calloc
funktion, vilket är i stort sett samma

213
00:11:07,980 --> 00:11:11,500
som malloc funktion, förutom att det är
garanterat att återvända något som är

214
00:11:11,500 --> 00:11:13,180
helt nollställd ut.

215
00:11:13,180 --> 00:11:17,290
Så om vi använt malloc, skulle vi behöva
gå igenom alla tips i vår

216
00:11:17,290 --> 00:11:20,160
nod, och se till att
de är alla null.

217
00:11:20,160 --> 00:11:22,710
Så calloc kommer att göra det åt oss.

218
00:11:22,710 --> 00:11:26,330
>> Nu precis som malloc, vi måste göra
Se till att tilldelningen var faktiskt

219
00:11:26,330 --> 00:11:27,520
framgångsrik.

220
00:11:27,520 --> 00:11:29,990
Om detta återvände null, då vi
behöva stänga eller ordbok

221
00:11:29,990 --> 00:11:32,100
filen och returnera false.

222
00:11:32,100 --> 00:11:36,835
Så antar att fördelningen var
framgångsrik, vi kommer att använda en nod *

223
00:11:36,835 --> 00:11:40,270
markören för att iterera genom vår trie.

224
00:11:40,270 --> 00:11:43,890
Så våra rötter aldrig kommer att förändras,
men vi kommer att använda markören till

225
00:11:43,890 --> 00:11:47,875
faktiskt gå från nod till nod.

226
00:11:47,875 --> 00:11:50,940
>> Så i detta för slinga vi läser
genom ordlistefilen.

227
00:11:50,940 --> 00:11:53,670
Och vi använder fgetc.

228
00:11:53,670 --> 00:11:56,290
Fgetc kommer att ta en enda
tecken från filen.

229
00:11:56,290 --> 00:11:59,370
Vi kommer att fortsätta att ta tag
tecken när vi inte når

230
00:11:59,370 --> 00:12:01,570
slutet av filen.

231
00:12:01,570 --> 00:12:03,480
>> Det finns två fall som vi måste hantera.

232
00:12:03,480 --> 00:12:06,610
Den första, om karaktären
var inte en ny rad.

233
00:12:06,610 --> 00:12:10,450
Så vi vet om det var en ny linje, då
vi håller på att gå vidare till ett nytt ord.

234
00:12:10,450 --> 00:12:15,240
Men om det nu inte var en ny linje, då
Här vill vi ta reda på

235
00:12:15,240 --> 00:12:18,380
index vi ska index i
i barn array som

236
00:12:18,380 --> 00:12:19,810
vi tittat på tidigare.

237
00:12:19,810 --> 00:12:23,880
>> Så, som jag sa tidigare, vi måste
specialfall apostrof.

238
00:12:23,880 --> 00:12:26,220
Lägg märke till att vi med hjälp av ternära
operatör här.

239
00:12:26,220 --> 00:12:29,580
Så vi kommer att läsa detta som, om
karaktären läser vi i var en

240
00:12:29,580 --> 00:12:35,330
apostrof, då ska vi ställa
index = "Alfabet" -1, vilket kommer

241
00:12:35,330 --> 00:12:37,680
vara indexet 26.

242
00:12:37,680 --> 00:12:41,130
>> Annars, om det inte var en apostrof, finns
vi ska ställa in index

243
00:12:41,130 --> 00:12:43,760
lika med c - en.

244
00:12:43,760 --> 00:12:49,030
Så minns tillbaka från tidigare p-apparater,
c - a kommer att ge oss

245
00:12:49,030 --> 00:12:53,410
alfabetisk position C. Så om
C är bokstaven A, detta kommer

246
00:12:53,410 --> 00:12:54,700
ge oss index noll.

247
00:12:54,700 --> 00:12:58,120
För bokstaven B, kommer det att ge
oss index 1, och så vidare.

248
00:12:58,120 --> 00:13:03,010
>> Så detta ger oss indexet i
barn array som vi vill ha.

249
00:13:03,010 --> 00:13:08,890
Nu, om detta index är närvarande null
barnen, det betyder att en nod

250
00:13:08,890 --> 00:13:11,830
för närvarande inte finns
från den vägen.

251
00:13:11,830 --> 00:13:15,160
Så vi måste avsätta
en nod för den vägen.

252
00:13:15,160 --> 00:13:16,550
Det är vad vi gör här.

253
00:13:16,550 --> 00:13:20,690
>> Så vi kommer att åter använda calloc
funktion, så att vi inte behöver

254
00:13:20,690 --> 00:13:22,880
nollställa alla pekare.

255
00:13:22,880 --> 00:13:27,240
Och vi återigen måste kontrollera
att calloc inte misslyckas.

256
00:13:27,240 --> 00:13:30,700
Om calloc gjorde misslyckas, då behöver vi
att lasta av allt, stänga vår

257
00:13:30,700 --> 00:13:32,820
lexikon, och returnera false.

258
00:13:32,820 --> 00:13:40,050
Så antar att det inte misslyckas, då
detta kommer att skapa ett nytt barn för oss.

259
00:13:40,050 --> 00:13:41,930
Och då kommer vi till det barnet.

260
00:13:41,930 --> 00:13:44,960
Vår Markören iterera
ner till det barnet.

261
00:13:44,960 --> 00:13:49,330
>> Nu, om detta inte var noll till att börja med,
sedan markören kan bara iterera

262
00:13:49,330 --> 00:13:52,590
ner till barnet utan att
behöva fördela någonting.

263
00:13:52,590 --> 00:13:56,730
Detta är fallet när vi först hände
fördela ordet "katt". Och

264
00:13:56,730 --> 00:14:00,330
det betyder när vi går för att fördela
"Katastrof" vi inte behöver skapa

265
00:14:00,330 --> 00:14:01,680
noder för C-A-T igen.

266
00:14:01,680 --> 00:14:04,830
De finns redan.

267
00:14:04,830 --> 00:14:06,080
>> Vad är det annars?

268
00:14:06,080 --> 00:14:10,480
Detta är det tillstånd där c var
snedstreck n, där c var en ny rad.

269
00:14:10,480 --> 00:14:13,710
Det innebär att vi har lyckats
avslutade ett ord.

270
00:14:13,710 --> 00:14:16,860
Nu vad vi vill göra när vi
framgångsrikt slutfört ett ord?

271
00:14:16,860 --> 00:14:21,100
Vi kommer att använda detta ord fält
insidan av vår struct nod.

272
00:14:21,100 --> 00:14:23,390
Vi vill ställa den till true.

273
00:14:23,390 --> 00:14:27,150
Så som tyder på att denna nod
indikerar en framgångsrik

274
00:14:27,150 --> 00:14:29,250
ord, en verklig ord.

275
00:14:29,250 --> 00:14:30,940
>> Nu satt det till true.

276
00:14:30,940 --> 00:14:35,150
Vi vill återställa vår markören till punkt
till början av trie igen.

277
00:14:35,150 --> 00:14:40,160
Och slutligen, öka vår ordlista
storlek, eftersom vi hittat ett annat arbete.

278
00:14:40,160 --> 00:14:43,230
Så vi kommer att fortsätta göra det,
läsa in tecken för tecken,

279
00:14:43,230 --> 00:14:49,150
bygga nya noder i vår trie och
för varje ord i ordlistan, tills

280
00:14:49,150 --> 00:14:54,020
vi äntligen når C! = EOF, där
fall bryter vi ut filen.

281
00:14:54,020 --> 00:14:57,050
>> Nu finns det två ärenden enligt
som vi kanske har drabbat EOF.

282
00:14:57,050 --> 00:15:00,980
Den första är om det fanns ett fel
läsning från filen.

283
00:15:00,980 --> 00:15:03,470
Så om det var ett misstag, vi
måste göra den typiska.

284
00:15:03,470 --> 00:15:06,460
Lasta allt, nära
filen, returnera false.

285
00:15:06,460 --> 00:15:09,810
Förutsatt att det inte var ett misstag, att
bara innebär att vi faktiskt träffade i slutet av

286
00:15:09,810 --> 00:15:13,750
filen, i vilket fall, vi stänger
filen och returnera sant eftersom vi

287
00:15:13,750 --> 00:15:17,330
laddats lexikon
in i vår trie.

288
00:15:17,330 --> 00:15:20,170
>> Så nu ska vi kolla check.

289
00:15:20,170 --> 00:15:25,156
Om man tittar på funktionskontrollen, ser vi
att kontrollen kommer att returnera en bool.

290
00:15:25,156 --> 00:15:29,680
Den returnerar sant om detta ord att det är
överförs är i vår trie.

291
00:15:29,680 --> 00:15:32,110
Den returnerar false annars.

292
00:15:32,110 --> 00:15:36,050
Så hur ska du avgöra om
detta ord är i vår trie?

293
00:15:36,050 --> 00:15:40,190
>> Vi ser här att, precis som tidigare,
vi kommer att använda markören för att iterera

294
00:15:40,190 --> 00:15:41,970
genom vår trie.

295
00:15:41,970 --> 00:15:46,600
Nu här vi kommer att iterera
över hela vårt ord.

296
00:15:46,600 --> 00:15:50,620
Så iteration över ordet vi är förbi,
vi kommer att bestämma

297
00:15:50,620 --> 00:15:56,400
index till barn array som
motsvarar ordet fäste I. Så detta

298
00:15:56,400 --> 00:15:59,670
kommer att se ut exakt som
belastning, där om ord [i]

299
00:15:59,670 --> 00:16:03,310
är en apostrof, då vi vill ha
att använda index "ALPHABET" - 1.

300
00:16:03,310 --> 00:16:05,350
Eftersom vi fastställt att det
är där vi kommer att lagra

301
00:16:05,350 --> 00:16:07,100
apostrofer.

302
00:16:07,100 --> 00:16:11,780
>> Annars ska vi använda två nedre ord
fäste I. Så kom ihåg det ordet kan

303
00:16:11,780 --> 00:16:13,920
ha godtycklig kapitalisering.

304
00:16:13,920 --> 00:16:17,540
Och så vill vi se till att vi är
med hjälp av en gemen version av saker.

305
00:16:17,540 --> 00:16:21,920
Och sedan dra ifrån att "en" att en gång
återigen ge oss den alfabetiska

306
00:16:21,920 --> 00:16:23,880
ställning av denna karaktär.

307
00:16:23,880 --> 00:16:27,680
Så det kommer att bli vårt index
till barn array.

308
00:16:27,680 --> 00:16:32,420
>> Och nu om detta index till barnen
matris är noll, innebär att vi

309
00:16:32,420 --> 00:16:34,990
inte längre kan fortsätta iteration
ner vår trie.

310
00:16:34,990 --> 00:16:38,870
Om så är fallet, detta ord kan inte
möjligen vara i vår trie.

311
00:16:38,870 --> 00:16:42,340
Sedan om det var, skulle det
innebära att det skulle finnas en bana

312
00:16:42,340 --> 00:16:43,510
ner till det ordet.

313
00:16:43,510 --> 00:16:45,290
Och du skulle aldrig stöta på null.

314
00:16:45,290 --> 00:16:47,850
Så möter null, återvänder vi falskt.

315
00:16:47,850 --> 00:16:49,840
Ordet finns inte i ordlistan.

316
00:16:49,840 --> 00:16:53,660
Om det inte var noll, då är vi
kommer att fortsätta iteration.

317
00:16:53,660 --> 00:16:57,220
>> Så vi ska ut där markören
för att peka på den särskilda

318
00:16:57,220 --> 00:16:59,760
nod vid detta index.

319
00:16:59,760 --> 00:17:03,150
Vi fortsätter att göra det hela
hela ordet, förutsatt

320
00:17:03,150 --> 00:17:03,950
Vi slog aldrig noll.

321
00:17:03,950 --> 00:17:07,220
Det betyder att vi skulle kunna få igenom
hela ordet och hitta

322
00:17:07,220 --> 00:17:08,920
en nod i våra försök.

323
00:17:08,920 --> 00:17:10,770
Men vi är inte riktigt klar ännu.

324
00:17:10,770 --> 00:17:12,290
>> Vi vill inte bara return true.

325
00:17:12,290 --> 00:17:14,770
Vi vill återvända markören> ord.

326
00:17:14,770 --> 00:17:18,980
Sedan minns igen, är "katten" är inte
i vår ordlista och "katastrof"

327
00:17:18,980 --> 00:17:22,935
är, då kommer vi att lyckas får vi
genom ordet "katt". Men markören

328
00:17:22,935 --> 00:17:25,760
Ordet är falsk och inte sant.

329
00:17:25,760 --> 00:17:30,930
Så vi återvänder markören ord för att indikera
huruvida denna nod är faktiskt ett ord.

330
00:17:30,930 --> 00:17:32,470
Och det är den för kontroll.

331
00:17:32,470 --> 00:17:34,250
>> Så låt oss kolla storlek.

332
00:17:34,250 --> 00:17:37,350
Så storlek kommer att bli ganska lätt
sedan, minns i lasten, vi är

333
00:17:37,350 --> 00:17:41,430
uppräkning ordbok storlek för
varje ord som vi stöter på.

334
00:17:41,430 --> 00:17:45,350
Så storleken är bara att
tillbaka ordboken storlek.

335
00:17:45,350 --> 00:17:47,390
Och det är det.

336
00:17:47,390 --> 00:17:50,590
>> Så slutligen har vi lasta.

337
00:17:50,590 --> 00:17:55,100
Så lasta, kommer vi att använda en
rekursiv funktion för att verkligen göra allt

338
00:17:55,100 --> 00:17:56,530
av arbetet åt oss.

339
00:17:56,530 --> 00:17:59,340
Så vår funktion kommer att
kallas på avlastnings.

340
00:17:59,340 --> 00:18:01,650
Vad avlastnings göra?

341
00:18:01,650 --> 00:18:06,580
Vi ser här att avlastnings kommer att
iterera över alla barnen på

342
00:18:06,580 --> 00:18:08,410
just denna nod.

343
00:18:08,410 --> 00:18:11,750
Och om barnet noden inte
null, då vi kommer att

344
00:18:11,750 --> 00:18:13,730
lossa barnet oden.

345
00:18:13,730 --> 00:18:18,010
>> Så det här är du rekursivt lasta
alla våra barn.

346
00:18:18,010 --> 00:18:21,080
När vi är säkra på att alla våra barn
har lossats, då vi

347
00:18:21,080 --> 00:18:25,210
kan frigöra oss, så
lasta av oss själva.

348
00:18:25,210 --> 00:18:29,460
Detta fungerar rekursivt
lasta hela trie.

349
00:18:29,460 --> 00:18:32,850
Och när det är gjort,
Vi kan bara return true.

350
00:18:32,850 --> 00:18:34,210
Lasta kan inte misslyckas.

351
00:18:34,210 --> 00:18:35,710
Vi bara frigöra saker.

352
00:18:35,710 --> 00:18:38,870
Så när vi är klara frigöra
allt, return true.

353
00:18:38,870 --> 00:18:40,320
Och det är det.

354
00:18:40,320 --> 00:18:41,080
Mitt namn är Rob.

355
00:18:41,080 --> 00:18:42,426
Och detta var speller.

356
00:18:42,426 --> 00:18:47,830
>> [MUSIK SPELA]