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

2
00:00:00,530 --> 00:00:03,070
>> LUIDSPREKER 1: Laten we
deze oplossing proberen.

3
00:00:03,070 --> 00:00:07,130
Dus laten we eens kijken naar wat onze
Struct knooppunt eruit zal zien.

4
00:00:07,130 --> 00:00:11,040
Hier zien we we gaan een
Bool Word en een Struct knooppunt ster

5
00:00:11,040 --> 00:00:12,990
Kinderen beugel alfabet.

6
00:00:12,990 --> 00:00:18,720
Dus eerste wat je misschien af,
waarom is alfabet hash gedefinieerd als 27?

7
00:00:18,720 --> 00:00:22,540
Nou, vergeet niet dat we gaan nodig hebben
te hanteren van de apostrof, dus

8
00:00:22,540 --> 00:00:25,610
dat gaat wat te zijn van een bijzondere
geval in dit programma.

9
00:00:25,610 --> 00:00:28,780
>> OK, nu, herinner me hoe een
Trie eigenlijk werkt.

10
00:00:28,780 --> 00:00:33,420
Laten we zeggen dat we het indexeren van het woord katten,
vervolgens uit de wortel van onze Trie,

11
00:00:33,420 --> 00:00:36,670
we gaan kijken naar de kinderen
array, en we gaan kijken naar de

12
00:00:36,670 --> 00:00:42,250
index die overeenkomt met de letter
C. Dat zou indexeren twee.

13
00:00:42,250 --> 00:00:46,400
Zo bepaalde, zal dat ons
een nieuw knooppunt, en dan gaan we

14
00:00:46,400 --> 00:00:47,880
werken vanuit dat knooppunt.

15
00:00:47,880 --> 00:00:51,830
>> Zo bepaalde knooppunt, we zijn weer
gaan kijken naar de kinderen array,

16
00:00:51,830 --> 00:00:56,170
en we gaan kijken naar index nul
overeenkomen met de A cat.

17
00:00:56,170 --> 00:01:01,240
Dus dan gaan we naar dat knooppunt,
en gezien het feit dat knooppunt, we gaan

18
00:01:01,240 --> 00:01:05,170
te kijken naar de index die overeenkomt
T. En de overgang naar dat knooppunt,

19
00:01:05,170 --> 00:01:09,590
Tenslotte hebben we volledig gekeken
door ons woord kat, en nu Bool

20
00:01:09,590 --> 00:01:15,020
Woord wordt verondersteld te geven of
dit gegeven woord is eigenlijk een woord.

21
00:01:15,020 --> 00:01:17,530
>> Dus waarom doen we dat speciaal geval nodig?

22
00:01:17,530 --> 00:01:21,680
Nou, wat als het woord catastrofe
in ons woordenboek, maar

23
00:01:21,680 --> 00:01:24,120
het woord kat is niet?

24
00:01:24,120 --> 00:01:29,030
Dus op zoek om te zien of het woord kat
in ons woordenboek, gaan we

25
00:01:29,030 --> 00:01:34,880
succes kijken via de indices
C-A-T en bereiken een knooppunt, maar dat is

26
00:01:34,880 --> 00:01:39,760
alleen omdat ramp gebeurd met
creëren knooppunten op de weg van C-A-T Alle

27
00:01:39,760 --> 00:01:41,250
tot aan het einde van het woord.

28
00:01:41,250 --> 00:01:46,520
Dus Bool Word wordt gebruikt aangeven of
deze bijzondere locatie daadwerkelijk

29
00:01:46,520 --> 00:01:48,370
duidt op een woord.

30
00:01:48,370 --> 00:01:52,920
>> Oke, dus nu dat we weten wat een
Trie gaat uitzien, laten we eens kijken

31
00:01:52,920 --> 00:01:54,800
op de Load functie.

32
00:01:54,800 --> 00:01:58,670
Dus Load gaat een Bool terug
voor de vraag of we met succes of

33
00:01:58,670 --> 00:02:03,020
tevergeefs geladen woordenboek en
dit gaat om het woordenboek te zijn

34
00:02:03,020 --> 00:02:04,520
dat we willen laden.

35
00:02:04,520 --> 00:02:08,310
Dus eerste wat we gaan doen is het openen
up die woordenboek voor het lezen.

36
00:02:08,310 --> 00:02:12,060
We moeten ervoor zorgen dat we niet falen,
dus als het woordenboek niet

37
00:02:12,060 --> 00:02:15,280
succesvol geopend is, zal het terug
Nee, in dat geval gaan we

38
00:02:15,280 --> 00:02:16,340
return false.

39
00:02:16,340 --> 00:02:21,290
Maar ervan uitgaande dat het met succes
geopend, dan kunnen we echt gelezen

40
00:02:21,290 --> 00:02:22,310
door het woordenboek.

41
00:02:22,310 --> 00:02:24,940
>> Dus eerste wat we gaan
wilt doen is hebben we dit

42
00:02:24,940 --> 00:02:26,560
globale variabele root.

43
00:02:26,560 --> 00:02:30,250
Nu, wortel gaat een knooppunt ster.

44
00:02:30,250 --> 00:02:33,830
Het is de top van onze Trie dat we
zal worden itereren door.

45
00:02:33,830 --> 00:02:38,200
Dus eerste wat we gaan willen
doen is geheugen toewijzen voor onze root.

46
00:02:38,200 --> 00:02:42,040
>> Merk op dat we met behulp van de calloc
functie, die is in principe hetzelfde

47
00:02:42,040 --> 00:02:45,560
als Malloc functie, behalve dat het
gegarandeerd iets dat terug

48
00:02:45,560 --> 00:02:47,240
volledig op nul gezet.

49
00:02:47,240 --> 00:02:51,350
Dus als we gebruikt Malloc, zouden we moeten
gaan door alle van de wijzers in onze

50
00:02:51,350 --> 00:02:54,220
knooppunt en zorg ervoor dat
ze zijn allemaal null.

51
00:02:54,220 --> 00:02:56,780
Dus calloc doet dat voor ons.

52
00:02:56,780 --> 00:03:00,390
>> Nu, net als Malloc, moeten we ervoor
ervoor dat de toewijzing is eigenlijk

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

54
00:03:01,580 --> 00:03:04,060
Als dit terug null, dan kunnen we
moeten ons woordenboek sluiten

55
00:03:04,060 --> 00:03:06,170
file en terug False.

56
00:03:06,170 --> 00:03:11,040
Dus uitgaande van de toewijzing werd
succesvol is, gaan we een knooppunt gebruiken

57
00:03:11,040 --> 00:03:14,340
ster Cursor te herhalen
via onze Trie.

58
00:03:14,340 --> 00:03:17,950
Dus onze wortel gaat nooit veranderen,
maar we gaan Cursor gebruiken om

59
00:03:17,950 --> 00:03:20,770
daadwerkelijk te gaan van knooppunt naar knooppunt.

60
00:03:20,770 --> 00:03:25,000
>> Oke, dus in dit For-lus, we zijn
lezen door het woordenboek bestand,

61
00:03:25,000 --> 00:03:26,965
en we gebruiken bij fgetc.

62
00:03:26,965 --> 00:03:30,360
Dus fgetc gaat een pak
karakter van het bestand.

63
00:03:30,360 --> 00:03:33,430
We gaan blijven grijpen
personages terwijl we niet bereikt de

64
00:03:33,430 --> 00:03:37,540
einde van het bestand, dus er zijn
twee gevallen moeten we hanteren.

65
00:03:37,540 --> 00:03:41,640
De eerste, indien het teken niet een
nieuwe lijn, dus we weten of het een nieuwe

66
00:03:41,640 --> 00:03:44,480
lijn, dan zijn we op het punt om
gaan naar een nieuw woord.

67
00:03:44,480 --> 00:03:49,300
Maar ervan uitgaande dat het was niet een nieuwe regel, dan
hier willen we achterhalen van de

68
00:03:49,300 --> 00:03:52,440
index gaan we index in
in the Children array die

69
00:03:52,440 --> 00:03:53,890
we gekeken naar eerder.

70
00:03:53,890 --> 00:03:57,950
>> Dus zoals ik al eerder zei, we moeten
speciaal geval de apostrof.

71
00:03:57,950 --> 00:04:01,040
Let op dat we met behulp van de ternaire operator
hier, dus we gaan om te lezen

72
00:04:01,040 --> 00:04:05,500
dit alsof het personage lezen we in was
een apostrof, dan gaan we naar

73
00:04:05,500 --> 00:04:11,740
ingesteld index gelijk aan alfabet minus
1, die de index 26 is.

74
00:04:11,740 --> 00:04:15,190
Anders, als het niet een apostrof,
dan gaan we naar de index-set

75
00:04:15,190 --> 00:04:17,820
c gelijk aan minus een.

76
00:04:17,820 --> 00:04:23,090
Dus vergeet niet terug van eerdere p sets,
c minus een gaat ons het geven

77
00:04:23,090 --> 00:04:27,470
alfabetische positie van c, dus als
c is de letter A, dit wil

78
00:04:27,470 --> 00:04:28,770
geven ons index nul.

79
00:04:28,770 --> 00:04:32,180
Voor de letter B, zou het geven
ons de index 1, en ga zo maar door.

80
00:04:32,180 --> 00:04:37,070
>> Dus dit geeft ons de index in de
Kinderen array die we willen.

81
00:04:37,070 --> 00:04:42,540
Nu, als deze index is momenteel null in
the Children array, dat betekent dat

82
00:04:42,540 --> 00:04:47,470
een knooppunt nog niet bestaat uit
dat pad, dus we moeten kennen een

83
00:04:47,470 --> 00:04:49,220
knooppunt voor dat pad.

84
00:04:49,220 --> 00:04:50,610
Dat is wat we hier doen.

85
00:04:50,610 --> 00:04:54,650
Dus we gaan, nogmaals, gebruik de calloc
functie zodat we niet hoeven

86
00:04:54,650 --> 00:05:00,130
tot nul uit alle van de pointers, en wij,
weer, moet dat calloc controleren

87
00:05:00,130 --> 00:05:01,300
faalde niet.

88
00:05:01,300 --> 00:05:04,760
Als calloc deed mislukken, dan moeten we
om alles uit te laden, sluit onze

89
00:05:04,760 --> 00:05:06,880
woordenboek, en terug False.

90
00:05:06,880 --> 00:05:14,110
>> Dus de veronderstelling dat het niet mislukt, dan
dit zal een nieuw kind voor ons te creëren,

91
00:05:14,110 --> 00:05:16,000
en dan gaan we naar dat kind.

92
00:05:16,000 --> 00:05:19,030
Onze cursor zal herhalen
neer aan dat kind.

93
00:05:19,030 --> 00:05:23,390
Nu, als dit niet nul te beginnen,
vervolgens de cursor kan slechts herhalen

94
00:05:23,390 --> 00:05:26,650
neer dat kind zonder daadwerkelijk
iets te hoeven toe te wijzen.

95
00:05:26,650 --> 00:05:30,790
Dit is het geval wanneer we eerst gebeurd
om het woord kat toewijzen en

96
00:05:30,790 --> 00:05:34,390
dat betekent dat wanneer we naar toe te wijzen
catastrofe, hoeven we niet te maken

97
00:05:34,390 --> 00:05:35,720
knooppunten C-A-T weer.

98
00:05:35,720 --> 00:05:37,620
Ze bestaan ​​reeds.

99
00:05:37,620 --> 00:05:40,140
>> OK, dus wat is dit anders?

100
00:05:40,140 --> 00:05:44,600
Dit is de toestand waarin c was
backslash n, waarbij c was een nieuwe regel.

101
00:05:44,600 --> 00:05:47,780
Dit betekent dat we met succes hebben
voltooide een woord.

102
00:05:47,780 --> 00:05:51,020
Nu, wat willen we doen als we
een woord met succes afgerond?

103
00:05:51,020 --> 00:05:55,250
We gaan dit woord veld gebruiken
binnenkant van ons Struct knooppunt.

104
00:05:55,250 --> 00:06:00,570
>> We willen instellen die op True, zodat
geeft aan dat knooppunt aangeeft een

105
00:06:00,570 --> 00:06:03,320
succesvolle woord een echte woord.

106
00:06:03,320 --> 00:06:05,050
Nu, stel dat op True.

107
00:06:05,050 --> 00:06:09,210
We willen onze cursor terug te zetten naar punt
aan het begin van de Trie weer.

108
00:06:09,210 --> 00:06:13,510
En tenslotte, verhogen ons woordenboek
maat omdat we vonden een ander woord.

109
00:06:13,510 --> 00:06:16,450
>> Oke, dus we gaan blijven doen
dat het lezen van karakter door

110
00:06:16,450 --> 00:06:21,960
karakter, de aanleg van nieuwe knooppunten in
onze Trie en voor elk woord in de

111
00:06:21,960 --> 00:06:26,810
woordenboek, tot we uiteindelijk c bereiken
gelijk EOF, in welk geval we breken

112
00:06:26,810 --> 00:06:28,100
uit het bestand.

113
00:06:28,100 --> 00:06:31,110
Nu zijn er twee gevallen onder
die wij EOF zou hebben geraakt.

114
00:06:31,110 --> 00:06:35,680
De eerste is of er een fout
het lezen van het bestand, dus als er

115
00:06:35,680 --> 00:06:39,280
een fout, moeten we de typische doen
lossen alles, sluit u het bestand

116
00:06:39,280 --> 00:06:40,520
return false.

117
00:06:40,520 --> 00:06:43,870
Ervan uitgaande dat er was geen fout, dat
betekent gewoon dat we eigenlijk raakte eind

118
00:06:43,870 --> 00:06:47,820
het bestand, waarbij sluiten we de
file en terug True aangezien we

119
00:06:47,820 --> 00:06:51,010
met succes geladen het woordenboek
in onze Trie.

120
00:06:51,010 --> 00:06:54,240
>> Oke, dus nu laten we
check out Check.

121
00:06:54,240 --> 00:06:58,780
Kijkend naar de Check-functie, zien we
Controleer dat gaat een Bool terugkeren.

122
00:06:58,780 --> 00:07:03,740
Het geeft Waar als dit woord dat het
wordt doorgegeven is in onze Trie.

123
00:07:03,740 --> 00:07:06,170
Het geeft Onwaar anders.

124
00:07:06,170 --> 00:07:10,110
>> Dus hoe gaan we om te bepalen of
dit woord is in onze Trie?

125
00:07:10,110 --> 00:07:14,270
We zien hier dat, net als vroeger,
we gaan cursor gebruiken om te schakelen

126
00:07:14,270 --> 00:07:16,010
via onze Trie.

127
00:07:16,010 --> 00:07:20,650
Nu, hier, we gaan herhalen
meer dan onze hele woord.

128
00:07:20,650 --> 00:07:24,680
Dus itereren over het woord dat we zijn
gepasseerd, gaan we bepalen de

129
00:07:24,680 --> 00:07:29,280
index in de Kinderen array die
komt overeen met woord beugel i.

130
00:07:29,280 --> 00:07:34,150
Dus dit gaat precies hetzelfde uitzien als
Belasting, waar als woord beugel i een

131
00:07:34,150 --> 00:07:38,110
apostrof, dan willen we index te gebruiken
alfabet minus 1 omdat we bepaald

132
00:07:38,110 --> 00:07:41,160
dat is waar we heen gaan
apostrofs slaan.

133
00:07:41,160 --> 00:07:44,440
>> Anders gaan we gebruiken tolower
woord beugel i.

134
00:07:44,440 --> 00:07:48,270
Dus onthoud dat woord kan hebben willekeurige
kapitalisatie, en dus hebben we

135
00:07:48,270 --> 00:07:51,590
willen ervoor zorgen dat we gebruiken
een kleine versie van de dingen.

136
00:07:51,590 --> 00:07:55,300
En dan aftrekken van die kleine letters
a. opnieuw ons het

137
00:07:55,300 --> 00:07:57,940
alfabetische positie
van dat personage.

138
00:07:57,940 --> 00:08:01,740
Dus dat gaat onze index zijn
in de Kinderen array.

139
00:08:01,740 --> 00:08:06,480
>> En nu, als die index in de Kinderen
array is null, dat betekent dat we

140
00:08:06,480 --> 00:08:09,050
kan niet langer blijven itereren
beneden onze Trie.

141
00:08:09,050 --> 00:08:13,320
Als dat het geval is, dit woord kan niet
eventueel in onze Trie, want als het

142
00:08:13,320 --> 00:08:18,000
werden, dat zou betekenen dat er zou een zijn
pad naar dat woord, en je zou

143
00:08:18,000 --> 00:08:19,350
nooit null tegenkomen.

144
00:08:19,350 --> 00:08:21,910
Dus ontmoeten null, we terugkeren False.

145
00:08:21,910 --> 00:08:23,810
Het woord niet in het woordenboek.

146
00:08:23,810 --> 00:08:28,200
Als het niet null is, dan gaan we naar
blijven itereren, dus we gaan

147
00:08:28,200 --> 00:08:33,150
onze cursor updaten naar wijzen dat
bepaald knooppunt op die index.

148
00:08:33,150 --> 00:08:36,659
>> Dus houden we dat overal doen
het hele woord.

149
00:08:36,659 --> 00:08:40,630
Ervan uitgaande dat we nooit geraakt null, dat betekent
we waren in staat om door het hele te krijgen

150
00:08:40,630 --> 00:08:44,840
wereld en het vinden van een knooppunt in onze Trie,
maar we zijn nog niet klaar.

151
00:08:44,840 --> 00:08:46,350
We willen niet gewoon terug True.

152
00:08:46,350 --> 00:08:51,400
We willen cursor fout woord terug
sinds, herinner nogmaals, als kat is niet

153
00:08:51,400 --> 00:08:55,140
in ons woordenboek en catastrofe is,
dan zullen we met succes doorheen

154
00:08:55,140 --> 00:08:59,810
het woord kat, maar cursor woord
Valse en niet True zal zijn.

155
00:08:59,810 --> 00:09:04,990
Dus keren we cursor woord om aan te geven
of dit knooppunt is eigenlijk een woord,

156
00:09:04,990 --> 00:09:06,530
en dat is het voor controle.

157
00:09:06,530 --> 00:09:08,310
>> Dus laten we eens kijken Grootte.

158
00:09:08,310 --> 00:09:11,410
Dus Grootte gaat vrij gemakkelijk te zijn
sinds, gedenken in Load, we zijn

159
00:09:11,410 --> 00:09:15,480
incrementing woordenboek maat voor
elk woord dat we tegenkomen.

160
00:09:15,480 --> 00:09:20,820
Dus maat is gewoon om terug te keren
woordenboekgrootte, en dat is het.

161
00:09:20,820 --> 00:09:24,650
>> Oke, ten slotte, hebben wij Unload.

162
00:09:24,650 --> 00:09:29,050
Dus Unload, gaan we gebruik maken van een
recursieve functie om daadwerkelijk alles te doen

163
00:09:29,050 --> 00:09:33,390
van het werk voor ons, zodat onze functie
is gaan heten Unloader.

164
00:09:33,390 --> 00:09:35,830
Wat is Unloader gaan doen?

165
00:09:35,830 --> 00:09:40,640
We zien hier dat Unloader gaat
itereren over alle kinderen op

166
00:09:40,640 --> 00:09:45,810
dit knooppunt en het kind
knooppunt is niet nul, dan gaan we naar

167
00:09:45,810 --> 00:09:47,760
lossen de onderliggende node.

168
00:09:47,760 --> 00:09:52,070
>> Dus dit gaat recursief
lossen al onze kinderen.

169
00:09:52,070 --> 00:09:55,140
Zodra we zeker weten dat al onze kinderen
zijn gelost, dan kunnen we

170
00:09:55,140 --> 00:09:58,830
kunnen onszelf bevrijden, zo lossen onszelf.

171
00:09:58,830 --> 00:10:04,550
Dus dit zal recursief lossen van de
hele Trie, en dan een keer is dat

172
00:10:04,550 --> 00:10:06,910
gedaan, kunnen we gewoon terug True.

173
00:10:06,910 --> 00:10:09,770
Lossen kan niet falen, we zijn
net bevrijden dingen.

174
00:10:09,770 --> 00:10:12,985
Dus zodra we klaar bevrijden
alles, return true.

175
00:10:12,985 --> 00:10:14,380
En dat is het.

176
00:10:14,380 --> 00:10:16,792
Mijn naam is Rob, en dit
was [onverstaanbaar].

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