1
00:00:00,000 --> 00:00:12,350
>> [Muziek]

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

3
00:00:13,050 --> 00:00:13,640
Ik ben Rob.

4
00:00:13,640 --> 00:00:16,210
En laten we deze oplossing uit.

5
00:00:16,210 --> 00:00:20,070
Dus hier gaan we implementeren
een algemene tabel.

6
00:00:20,070 --> 00:00:24,090
We zien dat de structuur knooppunt van onze
tafel gaat uitzien.

7
00:00:24,090 --> 00:00:28,710
Dus het gaat om een ​​char woord hebben
matrix van grootte LENGTE + 1.

8
00:00:28,710 --> 00:00:32,259
Vergeet niet de + 1, omdat de maximale
woord in het woordenboek is 45

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

10
00:00:33,130 --> 00:00:37,070
En dan gaan we een extra nodig
karakter voor de backslash nul.

11
00:00:37,070 --> 00:00:40,870
>> En dan is onze hash in elke
emmer gaat slaan een

12
00:00:40,870 --> 00:00:42,320
gelinkte lijst van knooppunten.

13
00:00:42,320 --> 00:00:44,420
We zijn niet lineair hier indringende doen.

14
00:00:44,420 --> 00:00:48,430
En dus om te linken naar het volgende
element in de emmer, hebben we een

15
00:00:48,430 --> 00:00:50,390
struct knoop * volgende.

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

17
00:00:51,110 --> 00:00:53,090
Dus dat is wat een knooppunt eruit ziet.

18
00:00:53,090 --> 00:00:56,180
>> Nu hier is de verklaring
van onze hash.

19
00:00:56,180 --> 00:00:59,640
Het gaat om 16.834 bakken hebben.

20
00:00:59,640 --> 00:01:01,910
Maar dat aantal maakt niet echt uit.

21
00:01:01,910 --> 00:01:05,450
En tot slot, we gaan de
globale variabele hash grootte, die

22
00:01:05,450 --> 00:01:07,000
gaat beginnen als nul.

23
00:01:07,000 --> 00:01:10,760
En het gaat bij te houden hoe houden
veel woorden zijn in ons woordenboek.

24
00:01:10,760 --> 00:01:13,710
>> Dus laten we eens een kijkje nemen op belasting.

25
00:01:13,710 --> 00:01:16,390
Merk op dat de belasting, retourneert een bool.

26
00:01:16,390 --> 00:01:20,530
U return true als het succesvol was
geladen, anders false.

27
00:01:20,530 --> 00:01:23,990
En het duurt een const char * woordenboek,
die het woordenboek

28
00:01:23,990 --> 00:01:25,280
dat we willen openen.

29
00:01:25,280 --> 00:01:27,170
Dus dat is het eerste wat
we gaan doen.

30
00:01:27,170 --> 00:01:29,500
>> We gaan fopen de
woordenboek voor het lezen.

31
00:01:29,500 --> 00:01:31,680
En we zullen moeten maken
zeker van dat het is gelukt.

32
00:01:31,680 --> 00:01:35,920
Dus als het terug NULL, dan hebben we niet
succes opent het woordenboek.

33
00:01:35,920 --> 00:01:37,440
En we moeten return false.

34
00:01:37,440 --> 00:01:41,580
Maar ervan uitgaande dat het met succes gedaan
geopend, dan willen we lezen de

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

36
00:01:42,400 --> 00:01:46,450
Dus houd looping tot we enkele
reden om uit te breken van deze lus,

37
00:01:46,450 --> 00:01:47,570
die we zullen zien.

38
00:01:47,570 --> 00:01:48,920
Dus houd looping.

39
00:01:48,920 --> 00:01:51,780
>> En nu gaan we naar
malloc een enkel knooppunt.

40
00:01:51,780 --> 00:01:54,020
En natuurlijk moeten we
aan de lucht probeert u het opnieuw.

41
00:01:54,020 --> 00:01:58,680
Dus als mallocing niet gelukt, dan
we willen elke node die wij lossen

42
00:01:58,680 --> 00:02:02,590
gebeurd met malloc voor, sluit de
woordenboek en return false.

43
00:02:02,590 --> 00:02:06,830
Maar negeren dat, uitgaande we
gelukt, dan willen we fscanf gebruiken

44
00:02:06,830 --> 00:02:12,400
om een ​​enkel woord lezen uit onze
woordenboek in onze knooppunt.

45
00:02:12,400 --> 00:02:17,940
Dus onthoud dat entry> woord is de char
woord buffer van omvang lenghth + 1

46
00:02:17,940 --> 00:02:20,300
dat we gaan om het woord op te slaan in

47
00:02:20,300 --> 00:02:25,070
>> Dus fscanf gaat terug 1, zolang
zoals het was in staat om succesvol

48
00:02:25,070 --> 00:02:26,750
lees een woord uit het bestand.

49
00:02:26,750 --> 00:02:30,460
Als een van beide een fout gebeurt, of we
bereiken het einde van het bestand,

50
00:02:30,460 --> 00:02:31,950
zal niet terugkeren 1.

51
00:02:31,950 --> 00:02:35,180
In dat geval niet terugkeert 1,
we eindelijk te doorbreken

52
00:02:35,180 --> 00:02:37,280
dit terwijl lus.

53
00:02:37,280 --> 00:02:42,770
Zo zien we dat als we succes hebben
lees een woord in

54
00:02:42,770 --> 00:02:48,270
entry> woord, dan gaan we dat
woord met behulp van onze hash-functie.

55
00:02:48,270 --> 00:02:49,580
>> Laten we eens een kijkje nemen op
de hash-functie.

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

57
00:02:52,430 --> 00:02:55,610
Zodat je niet echt nodig hebt
om dit te begrijpen.

58
00:02:55,610 --> 00:02:59,460
En eigenlijk zijn we net trok deze hash
functioneren van het internet.

59
00:02:59,460 --> 00:03:04,010
Het enige wat je moet erkennen is
dat dit duurt een const char * woord.

60
00:03:04,010 --> 00:03:08,960
Dus het duurt een string als input, en
retourneren van een unsigned int als output.

61
00:03:08,960 --> 00:03:12,360
Dus dat is al een hash-functie is, is het
neemt in een input en geeft u een

62
00:03:12,360 --> 00:03:14,490
index in de hash.

63
00:03:14,490 --> 00:03:18,530
>> Merk op dat we moding door NUM_BUCKETS,
zodat de waarde terug

64
00:03:18,530 --> 00:03:21,730
eigenlijk is een index in de hash
en niet geïndexeerd dan de

65
00:03:21,730 --> 00:03:24,320
grenzen van de array.

66
00:03:24,320 --> 00:03:28,060
Zo bepaalde functie, we gaan
aan het woord die we lezen hash de

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

68
00:03:29,390 --> 00:03:31,700
En dan gaan we gebruiken
dat hash te voegen de

69
00:03:31,700 --> 00:03:33,750
binnenkomst in de hash.

70
00:03:33,750 --> 00:03:38,520
>> Nu hash hash is de huidige
gekoppelde lijst in de tabel.

71
00:03:38,520 --> 00:03:41,410
En het is heel goed mogelijk
dat het gewoon NULL.

72
00:03:41,410 --> 00:03:44,960
We willen onze toegang aan de voegen
begin van deze gelinkte lijst.

73
00:03:44,960 --> 00:03:48,600
En dus gaan we onze huidige hebben
toegangspoort tot wat de hash

74
00:03:48,600 --> 00:03:50,380
nog wijst.

75
00:03:50,380 --> 00:03:53,310
En dan gaan we op te slaan,
in de hash op de

76
00:03:53,310 --> 00:03:55,350
hash, de huidige vermelding.

77
00:03:55,350 --> 00:03:59,320
Dus deze twee lijnen met succes te voegen
de ingang aan het begin van de

78
00:03:59,320 --> 00:04:02,260
gelinkte lijst op die index
in de hash.

79
00:04:02,260 --> 00:04:04,900
>> Zodra we klaar zijn met dat, we weten
dat vonden we een ander woord in de

80
00:04:04,900 --> 00:04:07,790
woordenboek, en we verhogen opnieuw.

81
00:04:07,790 --> 00:04:13,960
Dus houden we dat doen totdat fscanf
teruggegaan iets non-1 bij

82
00:04:13,960 --> 00:04:16,950
welk punt herinneren dat
we moeten gratis toegang.

83
00:04:16,950 --> 00:04:19,459
Dus hier malloced we een vermelding.

84
00:04:19,459 --> 00:04:21,329
En we hebben geprobeerd om iets te lezen
uit het woordenboek.

85
00:04:21,329 --> 00:04:23,910
En we hebben niet met succes gelezen
iets uit het woordenboek, in

86
00:04:23,910 --> 00:04:26,650
dat geval moeten we de toegang gratis
dat we nooit daadwerkelijk in de zetten

87
00:04:26,650 --> 00:04:29,140
hash, en uiteindelijk breken.

88
00:04:29,140 --> 00:04:32,750
>> Zodra we breken we moeten zien, nou ja,
hebben we breken omdat er

89
00:04:32,750 --> 00:04:34,360
was een fout bij het lezen van het dossier?

90
00:04:34,360 --> 00:04:37,120
Of hebben we breken omdat we
aan het einde van het bestand?

91
00:04:37,120 --> 00:04:39,480
Als er een fout, waarna
we willen valse terugkeren.

92
00:04:39,480 --> 00:04:40,930
Omdat de lading niet gelukt.

93
00:04:40,930 --> 00:04:43,890
En in het proces dat we willen lossen
alle woorden die we lezen in, en

94
00:04:43,890 --> 00:04:45,670
sluit het woordenboek bestand.

95
00:04:45,670 --> 00:04:48,740
>> Ervan uitgaande dat we niet slagen, dan kunnen we gewoon
nog steeds nodig om het woordenboek te sluiten

96
00:04:48,740 --> 00:04:53,040
bestand, en tenslotte return true omdat we
met succes geladen het woordenboek.

97
00:04:53,040 --> 00:04:54,420
En dat is het voor de belasting.

98
00:04:54,420 --> 00:04:59,020
Dus nu controleren, gegeven een geladen hash,
gaat er zo uitzien.

99
00:04:59,020 --> 00:05:03,140
Dus check, het een bool terug, dat is
zal aangeven of de verstreken

100
00:05:03,140 --> 00:05:07,530
in char * woord, of de doorgegeven
in string is in ons woordenboek.

101
00:05:07,530 --> 00:05:09,890
Dus als het in het woordenboek
als het in onze hash,

102
00:05:09,890 --> 00:05:11,170
we zullen terugkeren waar.

103
00:05:11,170 --> 00:05:13,380
En als het niet, we zullen valse terugkeren.

104
00:05:13,380 --> 00:05:17,740
>> Gezien deze gepasseerd in woord, we zijn
gaan naar het woord hash.

105
00:05:17,740 --> 00:05:22,110
Nu een belangrijk ding te herkennen is
dat in de belasting we wisten dat alle

106
00:05:22,110 --> 00:05:23,820
woorden we gaan naar kleine letters.

107
00:05:23,820 --> 00:05:25,820
Maar hier zijn we niet zo zeker van.

108
00:05:25,820 --> 00:05:29,510
Als we een kijkje nemen op onze hash-functie,
onze hash-functie eigenlijk

109
00:05:29,510 --> 00:05:32,700
lager behuizing elk karakter
van het woord.

110
00:05:32,700 --> 00:05:37,940
Dus ongeacht de kapitalisatie van
woord, onze hash-functie is de terugkeer

111
00:05:37,940 --> 00:05:42,270
dezelfde index om welke
activering, zoals zou

112
00:05:42,270 --> 00:05:45,280
terug voor een volledig kleine
versie van het woord.

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

114
00:05:46,600 --> 00:05:49,790
Dat is onze index moet in de
hash voor dit woord.

115
00:05:49,790 --> 00:05:52,940
>> Nu is deze lus gaat
itereren over de gelinkte lijst

116
00:05:52,940 --> 00:05:55,000
dat was die index.

117
00:05:55,000 --> 00:05:59,610
Zo merken we initialiseren binnenkomst
te wijzen die index.

118
00:05:59,610 --> 00:06:02,750
We gaan blijven
terwijl entry! = NULL.

119
00:06:02,750 --> 00:06:07,770
En vergeet niet dat het bijwerken van de aanwijzer
in onze gelinkte lijst entry = entry> volgende.

120
00:06:07,770 --> 00:06:14,400
Dus hebben onze huidige toegangspoort tot
het volgende item in de gelinkte lijst.

121
00:06:14,400 --> 00:06:19,250
>> Dus voor elk item in de gelinkte lijst,
we gaan strcasecmp gebruiken.

122
00:06:19,250 --> 00:06:20,330
Het is niet StrComp.

123
00:06:20,330 --> 00:06:23,780
Want nogmaals, we willen
dingen doen geval ongevoelig.

124
00:06:23,780 --> 00:06:27,870
We gebruiken dus strcasecmp te vergelijken
woord, dat door dit

125
00:06:27,870 --> 00:06:31,860
functie tegen het woord
dat in deze ingang.

126
00:06:31,860 --> 00:06:35,570
Als deze nul terugkeert, dat betekent dat er
een wedstrijd, waarbij we willen

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

128
00:06:36,630 --> 00:06:39,590
Wij hebben met succes vonden de
woord in onze hash.

129
00:06:39,590 --> 00:06:43,040
>> Als er geen match, dan zijn we
gaat lus opnieuw en kijk naar de

130
00:06:43,040 --> 00:06:43,990
volgende item.

131
00:06:43,990 --> 00:06:47,640
En we gaan terwijl er verder looping
zijn items in deze gelinkte lijst.

132
00:06:47,640 --> 00:06:50,160
Wat gebeurt er als we breken
uit deze lus?

133
00:06:50,160 --> 00:06:55,110
Dat betekent dat we een ingang niet vinden dat
paste dit woord, in welk geval

134
00:06:55,110 --> 00:07:00,220
we return false aangeven dat onze
hashtable heeft dit woord niet bevatten.

135
00:07:00,220 --> 00:07:02,540
En dat is een cheque.

136
00:07:02,540 --> 00:07:04,790
>> Dus laten we eens een kijkje nemen op grootte.

137
00:07:04,790 --> 00:07:06,970
Nu grootte gaat vrij eenvoudig te zijn.

138
00:07:06,970 --> 00:07:11,080
Sinds herinneren in de belasting, voor elk woord
we vonden, we schuiven een globale

139
00:07:11,080 --> 00:07:12,880
variabele grootte hash.

140
00:07:12,880 --> 00:07:16,480
Zodat de grootte functie wordt gewoon
om globale variabele terug te keren.

141
00:07:16,480 --> 00:07:18,150
En dat is het.

142
00:07:18,150 --> 00:07:22,300
>> Nu eindelijk, moeten we lossen het
woordenboek als alles klaar is.

143
00:07:22,300 --> 00:07:25,340
Dus hoe gaan we dat doen?

144
00:07:25,340 --> 00:07:30,440
Hier zijn we looping boven
alle emmers van onze tafel.

145
00:07:30,440 --> 00:07:33,240
Dus er zijn NUM_BUCKETS emmers.

146
00:07:33,240 --> 00:07:37,410
En voor elke gekoppelde lijst in onze
hash, gaan we lus over

147
00:07:37,410 --> 00:07:41,070
het geheel van de gekoppelde lijst,
vrijmaken van elk element.

148
00:07:41,070 --> 00:07:42,900
>> Nu moeten we voorzichtig zijn.

149
00:07:42,900 --> 00:07:47,910
Dus hier hebben we een tijdelijke variabele
dat is het opslaan van de pointer naar de volgende

150
00:07:47,910 --> 00:07:49,730
element in de gelinkte lijst.

151
00:07:49,730 --> 00:07:52,140
En dan gaan we gratis
het huidige element.

152
00:07:52,140 --> 00:07:55,990
We moeten zorgen dat we dit doen omdat we
kan niet alleen gratis de huidige element

153
00:07:55,990 --> 00:07:59,180
en dan proberen om naar de volgende wijzer,
want zodra we het hebben bevrijd,

154
00:07:59,180 --> 00:08:00,870
het geheugen wordt ongeldig.

155
00:08:00,870 --> 00:08:04,990
>> Dus moeten we houden rond een pointer naar
het volgende element, dan kunnen we gratis de

156
00:08:04,990 --> 00:08:08,360
huidige element, en dan kunnen we updaten
het actuele element wijzen

157
00:08:08,360 --> 00:08:09,550
het volgende element.

158
00:08:09,550 --> 00:08:12,800
We zullen lus terwijl er elementen
in deze gelinkte lijst.

159
00:08:12,800 --> 00:08:15,620
We zullen dat doen voor alle gekoppelde
lijsten in de hash.

160
00:08:15,620 --> 00:08:19,460
En als we klaar zijn met dat, we hebben
volledig gelost de hash, en

161
00:08:19,460 --> 00:08:20,190
we klaar zijn.

162
00:08:20,190 --> 00:08:23,200
Dus het is onmogelijk voor lossen
ooit return false.

163
00:08:23,200 --> 00:08:26,470
En als we klaar zijn, we
gewoon terug waar.

164
00:08:26,470 --> 00:08:29,000
>> Laten we deze oplossing proberen.

165
00:08:29,000 --> 00:08:33,070
Dus laten we eens kijken naar wat onze
struct knoop eruit zal zien.

166
00:08:33,070 --> 00:08:36,220
Hier zien we dat we gaan een bool hebben
woord en een struct knoop * kinderen

167
00:08:36,220 --> 00:08:37,470
beugel alfabet.

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

169
00:08:38,929 --> 00:08:42,020
Dus het eerste wat je zou kunnen zijn
afvragen, waarom is ALFABET

170
00:08:42,020 --> 00:08:44,660
ed gedefinieerd als 27?

171
00:08:44,660 --> 00:08:47,900
Nou, vergeet niet dat we gaan nodig hebben
te hanteren van de apostrof.

172
00:08:47,900 --> 00:08:51,910
Dus dat gaat iets van een
speciaal geval in dit programma.

173
00:08:51,910 --> 00:08:54,710
>> Nu herinneren hoe een Trie
eigenlijk werkt.

174
00:08:54,710 --> 00:08:59,380
Laten we zeggen dat we het indexeren van het woord
"Katten." Dan wordt uit de wortel van Trie,

175
00:08:59,380 --> 00:09:02,610
we gaan kijken naar de kinderen
array, en we gaan kijken naar de

176
00:09:02,610 --> 00:09:08,090
index die overeenkomt met de letter
C. Dus die zullen worden geïndexeerd 2.

177
00:09:08,090 --> 00:09:11,530
Zo bepaalde, dat wil
geven ons een nieuw knooppunt.

178
00:09:11,530 --> 00:09:13,820
En dan zullen we werken vanuit dat knooppunt.

179
00:09:13,820 --> 00:09:17,770
>> Zo bepaalde knooppunt, we zijn weer
gaan kijken naar de kinderen array.

180
00:09:17,770 --> 00:09:22,110
En we gaan kijken naar index nul
overeenkomen met de A cat.

181
00:09:22,110 --> 00:09:27,170
Dus dan gaan we naar dat knooppunt,
en gezien het feit dat knooppunt we gaan

182
00:09:27,170 --> 00:09:31,090
om te kijken naar het einde is het een overeen
T. En de overgang naar dat knooppunt,

183
00:09:31,090 --> 00:09:35,530
Tenslotte hebben we volledig gekeken
door ons woord "cat". En nu bool

184
00:09:35,530 --> 00:09:40,960
woord moet geven of
dit gegeven woord is eigenlijk een woord.

185
00:09:40,960 --> 00:09:43,470
>> Dus waarom doen we dat speciaal geval nodig?

186
00:09:43,470 --> 00:09:47,700
Tja, wat van het woord "catastrofe"
in ons woordenboek, maar de

187
00:09:47,700 --> 00:09:50,150
woord "cat" is niet?

188
00:09:50,150 --> 00:09:54,580
Zo en op zoek om te zien of het woord "kat"
wordt in ons woordenboek, we zijn

189
00:09:54,580 --> 00:09:59,970
gaan om succesvol te kijken door
de indices C-A-T in regio node.

190
00:09:59,970 --> 00:10:04,290
Maar dat is alleen omdat catastrofe
gebeurd met knooppunten op de weg te creëren

191
00:10:04,290 --> 00:10:07,190
van C-A-T, helemaal naar
het einde van het woord.

192
00:10:07,190 --> 00:10:12,020
Dus bool woord wordt gebruikt om aan te geven of
deze bijzondere locatie

193
00:10:12,020 --> 00:10:14,310
eigenlijk wijst op een woord.

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

195
00:10:15,140 --> 00:10:19,310
Dus nu dat we weten wat het trie is
eruit komt te zien, laten we eens kijken naar de

196
00:10:19,310 --> 00:10:20,730
laden functie.

197
00:10:20,730 --> 00:10:24,610
Dus belasting gaat een bool terug
voor de vraag of we met succes of

198
00:10:24,610 --> 00:10:26,720
tevergeefs geladen het woordenboek.

199
00:10:26,720 --> 00:10:30,460
En dit gaat om het woordenboek te zijn
dat we willen laden.

200
00:10:30,460 --> 00:10:33,930
>> Dus eerste wat we doen is geopend
up die woordenboek voor het lezen.

201
00:10:33,930 --> 00:10:36,160
En we moeten ervoor zorgen
we niet falen.

202
00:10:36,160 --> 00:10:39,580
Als het woordenboek niet
succesvol geopend is, zal het terug

203
00:10:39,580 --> 00:10:42,400
null, in welk geval we
gaan return false.

204
00:10:42,400 --> 00:10:47,230
Maar ervan uitgaande dat het met succes
geopend, dan kunnen we echt gelezen

205
00:10:47,230 --> 00:10:48,220
door het woordenboek.

206
00:10:48,220 --> 00:10:50,880
>> Dus eerste wat we gaan
wilt doen is hebben we dit

207
00:10:50,880 --> 00:10:52,500
globale variabele root.

208
00:10:52,500 --> 00:10:56,190
Nu wortel gaat om een ​​knooppunt te zijn *.

209
00:10:56,190 --> 00:10:59,760
Het is de top van onze trie dat we
zal worden itereren door.

210
00:10:59,760 --> 00:11:02,660
Dus het eerste wat we gaan
te willen doen is toe te wijzen

211
00:11:02,660 --> 00:11:04,140
geheugen voor onze root.

212
00:11:04,140 --> 00:11:07,980
Merk op dat we met behulp van de calloc
functie, die is in principe hetzelfde

213
00:11:07,980 --> 00:11:11,500
als malloc-functie, behalve dat het
gegarandeerd iets dat terug

214
00:11:11,500 --> 00:11:13,180
volledig op nul gezet.

215
00:11:13,180 --> 00:11:17,290
Dus als we gebruikt malloc, zouden we moeten
gaan door alle van de wijzers in onze

216
00:11:17,290 --> 00:11:20,160
knooppunt, en zorg ervoor dat
ze zijn allemaal null.

217
00:11:20,160 --> 00:11:22,710
Dus calloc doet dat voor ons.

218
00:11:22,710 --> 00:11:26,330
>> Nu net als malloc, moeten we ervoor
ervoor dat de toewijzing was eigenlijk

219
00:11:26,330 --> 00:11:27,520
succesvol.

220
00:11:27,520 --> 00:11:29,990
Als dit terug null, dan kunnen we
moeten woordenboek sluiten of

221
00:11:29,990 --> 00:11:32,100
bestand en return false.

222
00:11:32,100 --> 00:11:36,835
Dus de veronderstelling dat de toewijzing werd
succesvol is, gaan we een knooppunt te gebruiken *

223
00:11:36,835 --> 00:11:40,270
cursor naar doorloopt onze trie.

224
00:11:40,270 --> 00:11:43,890
Dus onze roots nooit veranderen,
maar we gaan cursor om

225
00:11:43,890 --> 00:11:47,875
daadwerkelijk te gaan van knooppunt naar knooppunt.

226
00:11:47,875 --> 00:11:50,940
>> Dus in deze lus we lezen
door het woordenboek bestand.

227
00:11:50,940 --> 00:11:53,670
En we gebruiken fgetc.

228
00:11:53,670 --> 00:11:56,290
Fgetc gaat om een ​​enkel te grijpen
karakter van het bestand.

229
00:11:56,290 --> 00:11:59,370
We gaan blijven grijpen
personages terwijl we niet bereikt de

230
00:11:59,370 --> 00:12:01,570
einde van het bestand.

231
00:12:01,570 --> 00:12:03,480
>> Er zijn twee gevallen moeten we hanteren.

232
00:12:03,480 --> 00:12:06,610
De eerste, indien het teken
was niet een nieuwe regel.

233
00:12:06,610 --> 00:12:10,450
Dus we weten of het een nieuwe regel, dan
we staan ​​op het punt om over te gaan naar een nieuw woord.

234
00:12:10,450 --> 00:12:15,240
Maar ervan uitgaande dat het was niet een nieuwe regel, dan
hier willen we achterhalen van de

235
00:12:15,240 --> 00:12:18,380
index gaan we index in
in de kinderen array

236
00:12:18,380 --> 00:12:19,810
we gekeken naar eerder.

237
00:12:19,810 --> 00:12:23,880
>> Dus, zoals ik al eerder zei, we moeten
speciaal geval de apostrof.

238
00:12:23,880 --> 00:12:26,220
Merken we gebruiken het ternaire
operator hier.

239
00:12:26,220 --> 00:12:29,580
Dus we gaan om dit te lezen als, indien
het karakter lezen we in was een

240
00:12:29,580 --> 00:12:35,330
apostrof, dan gaan we in te stellen
index = "alphabet" -1, die zal

241
00:12:35,330 --> 00:12:37,680
als index 26.

242
00:12:37,680 --> 00:12:41,130
>> Anders, als het niet een apostrof, er
we gaan naar de index-set

243
00:12:41,130 --> 00:12:43,760
gelijk aan c - een.

244
00:12:43,760 --> 00:12:49,030
Dus vergeet niet terug van eerder p-sets,
c - een gaat ons het geven

245
00:12:49,030 --> 00:12:53,410
alfabetische positie van C. Dus als
C de letter A, zal dit

246
00:12:53,410 --> 00:12:54,700
geven ons index nul.

247
00:12:54,700 --> 00:12:58,120
Voor de letter B, zal het geven
ons de index 1, en ga zo maar door.

248
00:12:58,120 --> 00:13:03,010
>> Dus dit geeft ons de index in de
kinderen array die we willen.

249
00:13:03,010 --> 00:13:08,890
Nu, als deze index is momenteel null in
kinderen, dat betekent dat een knooppunt

250
00:13:08,890 --> 00:13:11,830
nog niet bestaat
van dat pad.

251
00:13:11,830 --> 00:13:15,160
Dus we moeten wijzen
een knooppunt voor dat pad.

252
00:13:15,160 --> 00:13:16,550
Dat is wat we hier gaan doen.

253
00:13:16,550 --> 00:13:20,690
>> Dus we gaan weer gebruik maken van de calloc
functie, zodat we niet hoeven te

254
00:13:20,690 --> 00:13:22,880
nul uit alle pointers.

255
00:13:22,880 --> 00:13:27,240
En we weer moeten controleren
dat calloc faalde niet.

256
00:13:27,240 --> 00:13:30,700
Als calloc deed mislukken, dan moeten we
om alles uit te laden, sluit onze

257
00:13:30,700 --> 00:13:32,820
woordenboek, en return false.

258
00:13:32,820 --> 00:13:40,050
Dus de veronderstelling dat het niet mislukt, dan
dit zal een nieuw kind te maken voor ons.

259
00:13:40,050 --> 00:13:41,930
En dan gaan we naar dat kind.

260
00:13:41,930 --> 00:13:44,960
Onze cursor zal herhalen
neer aan dat kind.

261
00:13:44,960 --> 00:13:49,330
>> Nu als dit niet nul te beginnen met,
vervolgens de cursor kan slechts herhalen

262
00:13:49,330 --> 00:13:52,590
neer dat kind zonder daadwerkelijk
iets te hoeven toe te wijzen.

263
00:13:52,590 --> 00:13:56,730
Dit is het geval wanneer we eerst gebeurd
wijzen het woord "kat." En

264
00:13:56,730 --> 00:14:00,330
dat betekent dat wanneer we naar toe te wijzen
"Catastrofe," we hoeven niet te maken

265
00:14:00,330 --> 00:14:01,680
knooppunten C-A-T weer.

266
00:14:01,680 --> 00:14:04,830
Ze bestaan ​​reeds.

267
00:14:04,830 --> 00:14:06,080
>> Wat is dit anders?

268
00:14:06,080 --> 00:14:10,480
Dit is de toestand waarin c was
backslash n, waarbij c was een nieuwe regel.

269
00:14:10,480 --> 00:14:13,710
Dit betekent dat we met succes hebben
voltooide een woord.

270
00:14:13,710 --> 00:14:16,860
Nu, wat willen we doen als we
een woord met succes afgerond?

271
00:14:16,860 --> 00:14:21,100
We gaan dit woord veld gebruiken
binnenkant van ons struct knooppunt.

272
00:14:21,100 --> 00:14:23,390
We willen stellen dat dit waar.

273
00:14:23,390 --> 00:14:27,150
Dat geeft aan dat knooppunt
wijst op een succesvolle

274
00:14:27,150 --> 00:14:29,250
woord, een echte woord.

275
00:14:29,250 --> 00:14:30,940
>> Stellen nu dat dit waar.

276
00:14:30,940 --> 00:14:35,150
We willen onze cursor terug te zetten naar punt
aan het begin van de Trie weer.

277
00:14:35,150 --> 00:14:40,160
En tenslotte, verhogen ons woordenboek
grootte, omdat we vonden een ander werk.

278
00:14:40,160 --> 00:14:43,230
Dus gaan we dat blijven doen,
lezen in het teken voor teken,

279
00:14:43,230 --> 00:14:49,150
de aanleg van nieuwe knooppunten in onze trie en
voor elk woord in de woordenlijst, tot

280
00:14:49,150 --> 00:14:54,020
we eindelijk bereiken C! = EOF, waarin
geval breken we uit het bestand.

281
00:14:54,020 --> 00:14:57,050
>> Nu zijn er twee gevallen onder
die wij EOF zou hebben geraakt.

282
00:14:57,050 --> 00:15:00,980
De eerste is of er een fout
het lezen van het bestand.

283
00:15:00,980 --> 00:15:03,470
Dus als er een fout, we
moeten de typische doen.

284
00:15:03,470 --> 00:15:06,460
Lossen alles, dicht
het bestand, return false.

285
00:15:06,460 --> 00:15:09,810
Ervan uitgaande dat er was geen fout, dat
betekent gewoon dat we eigenlijk raakte eind

286
00:15:09,810 --> 00:15:13,750
het bestand, waarbij sluiten we de
bestand en return true omdat we

287
00:15:13,750 --> 00:15:17,330
succes geladen woordenboek
in onze trie.

288
00:15:17,330 --> 00:15:20,170
>> Dus nu laten we eens kijken check.

289
00:15:20,170 --> 00:15:25,156
Kijkend naar de check-functie, zien we
Het inchecken gaat een bool terug.

290
00:15:25,156 --> 00:15:29,680
Het geeft true als dit woord dat het
wordt doorgegeven is in onze trie.

291
00:15:29,680 --> 00:15:32,110
Het geeft anders false.

292
00:15:32,110 --> 00:15:36,050
Dus hoe ga je bepalen of
dit woord is in onze trie?

293
00:15:36,050 --> 00:15:40,190
>> We zien hier dat, net als vroeger,
we gaan cursor gebruiken om te schakelen

294
00:15:40,190 --> 00:15:41,970
via onze trie.

295
00:15:41,970 --> 00:15:46,600
Nu hier gaan we herhalen
meer dan onze hele woord.

296
00:15:46,600 --> 00:15:50,620
Dus itereren over het woord dat we zijn verleden,
we gaan bepalen

297
00:15:50,620 --> 00:15:56,400
index in de array kinderen
komt overeen met woord beugel I. Dus dit

298
00:15:56,400 --> 00:15:59,670
gaat precies hetzelfde uitzien als
belasting, waar als woord [i]

299
00:15:59,670 --> 00:16:03,310
is een apostrof, dan willen we
naar index "alphabet" gebruiken - 1.

300
00:16:03,310 --> 00:16:05,350
Omdat we vastgesteld dat
is waar we heen gaan om op te slaan

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

302
00:16:07,100 --> 00:16:11,780
>> Anders gaan we twee onderste woord te gebruiken
beugel I. Dus onthoud dat woord kan

303
00:16:11,780 --> 00:16:13,920
hebben willekeurige kapitalisatie.

304
00:16:13,920 --> 00:16:17,540
En dus we willen ervoor zorgen dat we
met behulp van een kleine versie van de dingen.

305
00:16:17,540 --> 00:16:21,920
En dan aftrekken van dat 'a' om een ​​keer
weer geven ons de alfabetische

306
00:16:21,920 --> 00:16:23,880
positie van dat personage.

307
00:16:23,880 --> 00:16:27,680
Dus dat gaat onze index zijn
in de kinderen array.

308
00:16:27,680 --> 00:16:32,420
>> En nu als die index in de kinderen
array is null, dat betekent dat we

309
00:16:32,420 --> 00:16:34,990
kan niet langer blijven itereren
beneden onze trie.

310
00:16:34,990 --> 00:16:38,870
Als dat het geval is, dit woord kan niet
eventueel in onze trie.

311
00:16:38,870 --> 00:16:42,340
Want als het ware, dat zou
betekenen dat er zou een pad zijn

312
00:16:42,340 --> 00:16:43,510
neer aan dat woord.

313
00:16:43,510 --> 00:16:45,290
En je zou nooit null tegenkomen.

314
00:16:45,290 --> 00:16:47,850
Dus ontmoeten null, we return false.

315
00:16:47,850 --> 00:16:49,840
Het woord niet in het woordenboek.

316
00:16:49,840 --> 00:16:53,660
Als het niet null is, dan zijn we
zal itereren gaan.

317
00:16:53,660 --> 00:16:57,220
>> Dus we gaan er cursor
te wijzen dat specifieke

318
00:16:57,220 --> 00:16:59,760
knooppunt op die index.

319
00:16:59,760 --> 00:17:03,150
We houden dat in heel het doen
het hele woord, in de veronderstelling

320
00:17:03,150 --> 00:17:03,950
we nooit geraakt null.

321
00:17:03,950 --> 00:17:07,220
Dat betekent dat we in staat waren om door te komen
het hele woord en vind

322
00:17:07,220 --> 00:17:08,920
een knooppunt in onze poging.

323
00:17:08,920 --> 00:17:10,770
Maar we zijn nog niet klaar.

324
00:17:10,770 --> 00:17:12,290
>> We willen niet alleen return true.

325
00:17:12,290 --> 00:17:14,770
We willen cursor> woord terug.

326
00:17:14,770 --> 00:17:18,980
Ondertussen weer herinner, is "cat" is niet
in ons woordenboek, en "catastrofe"

327
00:17:18,980 --> 00:17:22,935
wordt, dan zullen we met succes krijgen we
door het woord "cat". Maar cursor

328
00:17:22,935 --> 00:17:25,760
woord zal vals en niet waar zijn.

329
00:17:25,760 --> 00:17:30,930
Dus keren we cursor woord om aan te geven
of dit knooppunt is eigenlijk een woord.

330
00:17:30,930 --> 00:17:32,470
En dat is het voor controle.

331
00:17:32,470 --> 00:17:34,250
>> Dus laten we eens kijken grootte.

332
00:17:34,250 --> 00:17:37,350
Dus maat gaat vrij gemakkelijk te zijn
sinds, gedenken in belasting, we zijn

333
00:17:37,350 --> 00:17:41,430
incrementing woordenboek maat voor
elk woord dat we tegenkomen.

334
00:17:41,430 --> 00:17:45,350
Dus maat is gewoon gaan
terug woordenboekgrootte.

335
00:17:45,350 --> 00:17:47,390
En dat is het.

336
00:17:47,390 --> 00:17:50,590
>> Dus slotte hebben uitladen.

337
00:17:50,590 --> 00:17:55,100
Dus lossen, gaan we gebruik maken van een
recursieve functie om daadwerkelijk alles te doen

338
00:17:55,100 --> 00:17:56,530
van het werk voor ons.

339
00:17:56,530 --> 00:17:59,340
Dus onze functie gaat
worden opgeroepen losser.

340
00:17:59,340 --> 00:18:01,650
Wat is losser gaan doen?

341
00:18:01,650 --> 00:18:06,580
We zien hier dat losser gaat
itereren over alle kinderen op

342
00:18:06,580 --> 00:18:08,410
dit knooppunt.

343
00:18:08,410 --> 00:18:11,750
En als het kind knooppunt is niet
null, dan gaan we naar

344
00:18:11,750 --> 00:18:13,730
lossen de onderliggende node.

345
00:18:13,730 --> 00:18:18,010
>> Dus dit is je recursief lossen
al onze kinderen.

346
00:18:18,010 --> 00:18:21,080
Zodra we zeker weten dat al onze kinderen
zijn gelost, dan kunnen we

347
00:18:21,080 --> 00:18:25,210
kunnen onszelf bevrijden, zodat
onszelf lossen.

348
00:18:25,210 --> 00:18:29,460
Dit recursief werken
lossen de hele trie.

349
00:18:29,460 --> 00:18:32,850
En dan zodra dat is gedaan,
kunnen we gewoon return true.

350
00:18:32,850 --> 00:18:34,210
Lossen kan niet falen.

351
00:18:34,210 --> 00:18:35,710
We zijn net bevrijden dingen.

352
00:18:35,710 --> 00:18:38,870
Dus zodra we klaar bevrijden
alles, return true.

353
00:18:38,870 --> 00:18:40,320
En dat is het.

354
00:18:40,320 --> 00:18:41,080
Mijn naam is Rob.

355
00:18:41,080 --> 00:18:42,426
En dit was speller.

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