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

2
00:00:00,530 --> 00:00:03,070
>> INTERLOCUTEUR 1: Donnons
cette solution un essai.

3
00:00:03,070 --> 00:00:07,130
Donc, nous allons jeter un oeil à ce que notre
noeud de Struct va ressembler.

4
00:00:07,130 --> 00:00:11,040
Ici, nous voyons que nous allons avoir un
Bool Word et un noeud étoiles Struct

5
00:00:11,040 --> 00:00:12,990
Enfants encadrent alphabet.

6
00:00:12,990 --> 00:00:18,720
Donc la première chose que vous demandez peut-être,
pourquoi hachage alphabet défini comme 27?

7
00:00:18,720 --> 00:00:22,540
Eh bien, rappelez-vous que nous allons avoir besoin de
à la manipulation de l'apostrophe, alors

8
00:00:22,540 --> 00:00:25,610
que ça va être un peu un spécial
cas tout au long de ce programme.

9
00:00:25,610 --> 00:00:28,780
>> OK, maintenant, rappelez-vous comment un
Trie fonctionne réellement.

10
00:00:28,780 --> 00:00:33,420
Disons que nous sommes l'indexation des mots chats,
puis à partir de la racine de notre Trie,

11
00:00:33,420 --> 00:00:36,670
nous allons regarder les enfants
tableau, et nous allons regarder la

12
00:00:36,670 --> 00:00:42,250
indice qui correspond à la lettre
C. Donc, ce serait deux index.

13
00:00:42,250 --> 00:00:46,400
Donc, étant donné que, cela nous donnera
un nouveau noeud, puis nous allons

14
00:00:46,400 --> 00:00:47,880
travailler à partir de ce nœud.

15
00:00:47,880 --> 00:00:51,830
>> Donc, étant donné que le noeud, nous sommes une fois de plus
va regarder le tableau des enfants,

16
00:00:51,830 --> 00:00:56,170
et nous allons voir à l'index zéro
pour correspondre à l'un de cat.

17
00:00:56,170 --> 00:01:01,240
Alors nous allons aller à ce nœud,
et compte tenu de ce nœud, nous allons

18
00:01:01,240 --> 00:01:05,170
à regarder l'indice qui correspond
T. Et de passer à ce nœud,

19
00:01:05,170 --> 00:01:09,590
enfin, nous avons complètement regardé
grâce à notre mot chat, et maintenant Bool

20
00:01:09,590 --> 00:01:15,020
Word est censé indiquer si
cette parole donnée est en fait un mot.

21
00:01:15,020 --> 00:01:17,530
>> Alors pourquoi avons-nous besoin ce cas particulier?

22
00:01:17,530 --> 00:01:21,680
Eh bien, si le mot catastrophe
est dans notre dictionnaire, mais

23
00:01:21,680 --> 00:01:24,120
le mot chat n'est pas?

24
00:01:24,120 --> 00:01:29,030
Donc, en cherchant à voir si le mot chat est
dans notre dictionnaire, nous allons

25
00:01:29,030 --> 00:01:34,880
regarder avec succès à travers les indices
C-A-T et d'atteindre un nœud, mais c'est

26
00:01:34,880 --> 00:01:39,760
seulement parce que la catastrophe qui s'est passé à
créer des nœuds sur le chemin de C-A-T tout

27
00:01:39,760 --> 00:01:41,250
le chemin de la fin du mot.

28
00:01:41,250 --> 00:01:46,520
Donc Bool Word est utilisé indiquer si
cet emplacement particulier fait

29
00:01:46,520 --> 00:01:48,370
indique un mot.

30
00:01:48,370 --> 00:01:52,920
>> Bon, maintenant que nous savons ce qu'est un
Trie va ressembler, regardons

31
00:01:52,920 --> 00:01:54,800
à la fonction de charge.

32
00:01:54,800 --> 00:01:58,670
Donc, la charge va revenir un Bool
pour que nous succès ou

33
00:01:58,670 --> 00:02:03,020
dictionnaire vain chargé et
cela va être le dictionnaire

34
00:02:03,020 --> 00:02:04,520
que nous voulons charger.

35
00:02:04,520 --> 00:02:08,310
Donc la première chose que nous allons faire est d'ouvrir
jusqu'à ce dictionnaire pour la lecture.

36
00:02:08,310 --> 00:02:12,060
Nous devons nous assurer que nous n'avons pas manqué,
donc si le dictionnaire n'a pas été

37
00:02:12,060 --> 00:02:15,280
ouvert avec succès, il sera de retour
Non, dans ce cas, nous allons

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

39
00:02:16,340 --> 00:02:21,290
Mais en supposant qu'il succès
ouvert, alors nous pouvons lire

40
00:02:21,290 --> 00:02:22,310
par le dictionnaire.

41
00:02:22,310 --> 00:02:24,940
>> Donc la première chose que nous allons
voulons faire, c'est ce que nous avons

42
00:02:24,940 --> 00:02:26,560
racine variable globale.

43
00:02:26,560 --> 00:02:30,250
Maintenant, racine va être une star de noeud.

44
00:02:30,250 --> 00:02:33,830
C'est le sommet de notre Trie que nous sommes
va être itérer.

45
00:02:33,830 --> 00:02:38,200
Donc la première chose que nous allons vouloir
faire est allouer de la mémoire pour notre racine.

46
00:02:38,200 --> 00:02:42,040
>> Notez que nous utilisons le calloc
fonction, qui est essentiellement le même

47
00:02:42,040 --> 00:02:45,560
que la fonction malloc, sauf que c'est
garantie de renvoyer quelque chose qui est

48
00:02:45,560 --> 00:02:47,240
complètement remis à zéro.

49
00:02:47,240 --> 00:02:51,350
Donc, si nous avons utilisé Malloc, nous aurions besoin de
passer en revue tous les pointeurs dans notre

50
00:02:51,350 --> 00:02:54,220
nœud et assurez-vous que
ils sont tous nuls.

51
00:02:54,220 --> 00:02:56,780
Donc calloc le fera pour nous.

52
00:02:56,780 --> 00:03:00,390
>> Maintenant, tout comme Malloc, nous devons faire
s'assurer que la répartition est en fait

53
00:03:00,390 --> 00:03:01,580
réussie.

54
00:03:01,580 --> 00:03:04,060
Si cette retourné null, alors nous
besoin de fermer notre dictionnaire

55
00:03:04,060 --> 00:03:06,170
déposer et revenir Faux.

56
00:03:06,170 --> 00:03:11,040
Supposant donc l'allocation a été
succès, nous allons utiliser un noeud

57
00:03:11,040 --> 00:03:14,340
étoile curseur pour parcourir
grâce à notre Trie.

58
00:03:14,340 --> 00:03:17,950
Donc, notre racine ne va jamais changer,
mais nous allons utiliser le curseur à

59
00:03:17,950 --> 00:03:20,770
effectivement aller de noeud à noeud.

60
00:03:20,770 --> 00:03:25,000
>> Très bien, alors dans ce boucle For, nous sommes
la lecture à travers le fichier de dictionnaire,

61
00:03:25,000 --> 00:03:26,965
et nous utilisons à fgetc.

62
00:03:26,965 --> 00:03:30,360
Donc fgetc va prendre un seul
caractère du fichier.

63
00:03:30,360 --> 00:03:33,430
Nous allons continuer à saisir
caractères alors que nous ne parvenons pas à la

64
00:03:33,430 --> 00:03:37,540
fin du fichier, donc il ya
deux cas, nous devons gérer.

65
00:03:37,540 --> 00:03:41,640
La première, si le caractère n'est pas un
nouvelle ligne, afin que nous sachions s'il s'agissait d'un nouveau

66
00:03:41,640 --> 00:03:44,480
ligne, alors nous sommes sur le point de
passer à un nouveau mot.

67
00:03:44,480 --> 00:03:49,300
Mais à supposer que ce n'était pas une nouvelle ligne, puis
ici, nous voulons comprendre la

68
00:03:49,300 --> 00:03:52,440
indice que nous allons à l'index dans
dans le tableau des enfants qui

69
00:03:52,440 --> 00:03:53,890
nous avons regardé avant.

70
00:03:53,890 --> 00:03:57,950
>> Donc, comme je l'ai dit avant, nous devons
cas particulier de l'apostrophe.

71
00:03:57,950 --> 00:04:01,040
Notez que nous utilisons l'opérateur ternaire
ici, nous allons lire

72
00:04:01,040 --> 00:04:05,500
ce comme si le personnage était lisons-nous dans
une apostrophe, alors nous allons

73
00:04:05,500 --> 00:04:11,740
définir indice égal à alphabet moins
1, qui sera l'index 26.

74
00:04:11,740 --> 00:04:15,190
Sinon, si ce n'était pas une apostrophe,
alors nous allons définir l'index

75
00:04:15,190 --> 00:04:17,820
égale à c moins un.

76
00:04:17,820 --> 00:04:23,090
Alors, n'oubliez pas de retour de p ensembles précédents,
c moins un va nous le donner

77
00:04:23,090 --> 00:04:27,470
la position alphabétique de c, si
c est la lettre A, cette volonté

78
00:04:27,470 --> 00:04:28,770
nous donner l'indice zéro.

79
00:04:28,770 --> 00:04:32,180
Par la lettre B, cela donnerait
nous l'index 1, et ainsi de suite.

80
00:04:32,180 --> 00:04:37,070
>> Cela nous donne l'index dans le
Enfants tableau que nous voulons.

81
00:04:37,070 --> 00:04:42,540
Maintenant, si cet indice est actuellement nulle dans
la matrice des enfants, ce qui signifie que

82
00:04:42,540 --> 00:04:47,470
n'existe pas actuellement un nœud de
ce chemin, nous avons donc besoin d'allouer une

83
00:04:47,470 --> 00:04:49,220
noeud pour cette voie.

84
00:04:49,220 --> 00:04:50,610
C'est ce que nous faisons ici.

85
00:04:50,610 --> 00:04:54,650
Nous allons donc, encore une fois, utiliser le calloc
fonction de sorte que nous n'avons pas

86
00:04:54,650 --> 00:05:00,130
mettre à zéro tous les pointeurs, et nous,
nouveau, besoin de vérifier que calloc

87
00:05:00,130 --> 00:05:01,300
n'ont pas manqué.

88
00:05:01,300 --> 00:05:04,760
Si calloc n'at-il pas, alors nous devons
pour décharger tout, fermer notre

89
00:05:04,760 --> 00:05:06,880
dictionnaire, et retourner False.

90
00:05:06,880 --> 00:05:14,110
>> Donc, en supposant qu'il n'a pas manqué, alors
cela va créer un nouvel enfant pour nous,

91
00:05:14,110 --> 00:05:16,000
puis nous irons à l'enfant.

92
00:05:16,000 --> 00:05:19,030
Notre curseur va parcourir
jusqu'à ce que l'enfant.

93
00:05:19,030 --> 00:05:23,390
Maintenant, si ce n'était pas nul pour commencer,
alors le curseur peut seulement parcourir

94
00:05:23,390 --> 00:05:26,650
jusqu'à ce que l'enfant sans réellement
avoir à allouer rien.

95
00:05:26,650 --> 00:05:30,790
C'est le cas où nous avons d'abord arrivé
d'attribuer le mot chat, et

96
00:05:30,790 --> 00:05:34,390
Cela signifie que lorsque nous allons à allouer
catastrophe, nous n'avons pas besoin de créer

97
00:05:34,390 --> 00:05:35,720
noeuds pour C-A-T nouveau.

98
00:05:35,720 --> 00:05:37,620
Ils existent déjà.

99
00:05:37,620 --> 00:05:40,140
>> OK, alors qu'est-ce autre chose?

100
00:05:40,140 --> 00:05:44,600
C'est la condition où c était
barre oblique inverse n, c était une nouvelle ligne.

101
00:05:44,600 --> 00:05:47,780
Cela signifie que nous avons réussi à
complété un mot.

102
00:05:47,780 --> 00:05:51,020
Maintenant, que voulons-nous faire quand nous
terminé avec succès un mot?

103
00:05:51,020 --> 00:05:55,250
Nous allons utiliser ce champ de texte
à l'intérieur de notre noeud de structure.

104
00:05:55,250 --> 00:06:00,570
>> Nous voulons mettre que de vrai, de sorte que
indique que ce noeud indique un

105
00:06:00,570 --> 00:06:03,320
mot succès un mot réel.

106
00:06:03,320 --> 00:06:05,050
Maintenant, définir cette valeur True.

107
00:06:05,050 --> 00:06:09,210
Nous voulons rétablir notre curseur sur le point
au début de la Trie nouveau.

108
00:06:09,210 --> 00:06:13,510
Et enfin, augmenter notre dictionnaire
taille car nous avons trouvé un autre mot.

109
00:06:13,510 --> 00:06:16,450
>> Très bien, nous allons donc continuer à faire
que, à la lecture caractère par

110
00:06:16,450 --> 00:06:21,960
caractère, la construction de nouveaux nœuds dans
notre Trie et pour chaque mot dans le

111
00:06:21,960 --> 00:06:26,810
dictionnaire, jusqu'à ce que nous atteignons finalement c
est égal à EOF, dans ce cas, nous rompons

112
00:06:26,810 --> 00:06:28,100
hors de l'image.

113
00:06:28,100 --> 00:06:31,110
Maintenant, il ya deux cas sous
que nous aurions pu frapper EOF.

114
00:06:31,110 --> 00:06:35,680
La première est de savoir si il y avait une erreur
la lecture du fichier, si il y avait

115
00:06:35,680 --> 00:06:39,280
une erreur, nous devons faire le type
décharger tout, fermez le fichier,

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

117
00:06:40,520 --> 00:06:43,870
En supposant qu'il n'y a pas d'erreur, que
signifie simplement que nous effectivement touché la fin de

118
00:06:43,870 --> 00:06:47,820
le fichier, dans ce cas, nous fermons l'
déposer et revenir vrai puisque nous

119
00:06:47,820 --> 00:06:51,010
chargé avec succès le dictionnaire
dans notre Trie.

120
00:06:51,010 --> 00:06:54,240
>> Très bien, alors maintenant nous allons
Départ Arrivée.

121
00:06:54,240 --> 00:06:58,780
En regardant la fonction de contrôle, nous voyons
Vérifier que va revenir un Bool.

122
00:06:58,780 --> 00:07:03,740
Il retourne True si ce mot que c'est
étant passé est dans notre Trie.

123
00:07:03,740 --> 00:07:06,170
Elle renvoie Faux sinon.

124
00:07:06,170 --> 00:07:10,110
>> Alors, comment allons-nous déterminer si
ce mot est dans notre Trie?

125
00:07:10,110 --> 00:07:14,270
Nous voyons ici que, comme avant,
nous allons utiliser le curseur pour parcourir

126
00:07:14,270 --> 00:07:16,010
grâce à notre Trie.

127
00:07:16,010 --> 00:07:20,650
Maintenant, ici, nous allons parcourir
sur l'ensemble de notre parole.

128
00:07:20,650 --> 00:07:24,680
Donc itération sur le mot que nous sommes
passé, nous allons déterminer la

129
00:07:24,680 --> 00:07:29,280
index dans le tableau que les enfants
correspond à mot i support.

130
00:07:29,280 --> 00:07:34,150
Donc, cela va ressembler exactement
Charge, où si le mot support i est un

131
00:07:34,150 --> 00:07:38,110
apostrophe, alors nous voulons utiliser l'index
alphabet moins 1 car nous avons déterminé

132
00:07:38,110 --> 00:07:41,160
c'est là que nous allons
pour stocker des apostrophes.

133
00:07:41,160 --> 00:07:44,440
>> Sinon nous allons utiliser tolower
mot support i.

134
00:07:44,440 --> 00:07:48,270
Alors, n'oubliez pas que ce mot peut avoir arbitraire
capitalisation, et nous

135
00:07:48,270 --> 00:07:51,590
voulez vous assurer que nous utilisons
une version en minuscules des choses.

136
00:07:51,590 --> 00:07:55,300
Et puis soustraire de ce minuscule
une, encore une fois, nous le donner

137
00:07:55,300 --> 00:07:57,940
la position alphabétique
de ce personnage.

138
00:07:57,940 --> 00:08:01,740
Alors que va être notre index
dans le tableau enfants.

139
00:08:01,740 --> 00:08:06,480
>> Et maintenant, si cet indice dans les enfants
tableau est nulle, cela signifie que nous

140
00:08:06,480 --> 00:08:09,050
ne peut plus continuer itération
en bas de notre Trie.

141
00:08:09,050 --> 00:08:13,320
Si c'est le cas, ce mot ne peut pas
éventuellement dans notre Trie, car si elle

142
00:08:13,320 --> 00:08:18,000
ont été, cela voudrait dire qu'il y aurait une
chemin vers le bas à ce mot, et vous le feriez

143
00:08:18,000 --> 00:08:19,350
jamais rencontrer nulle.

144
00:08:19,350 --> 00:08:21,910
Donc rencontrer nulle, nous revenons Faux.

145
00:08:21,910 --> 00:08:23,810
Le mot n'est pas dans le dictionnaire.

146
00:08:23,810 --> 00:08:28,200
Si ce n'était pas nul, alors nous allons
poursuivre l'itération, nous allons

147
00:08:28,200 --> 00:08:33,150
mettre à jour notre curseur pour pointer vers qui
noeud particulier à cet index.

148
00:08:33,150 --> 00:08:36,659
>> Donc, nous continuons à faire ce que tout au long de
le mot entier.

149
00:08:36,659 --> 00:08:40,630
En supposant que nous n'avons jamais touché nulle, que des moyens
nous avons réussi à passer à travers l'ensemble du

150
00:08:40,630 --> 00:08:44,840
monde et de trouver un noeud dans notre Trie,
mais nous ne sommes pas encore tout à fait terminé.

151
00:08:44,840 --> 00:08:46,350
Nous ne voulons pas simplement renvoyer True.

152
00:08:46,350 --> 00:08:51,400
Nous voulons retourner curseur mot d'erreur
car, rappelez-vous de nouveau, si le chat n'est pas

153
00:08:51,400 --> 00:08:55,140
dans notre dictionnaire et la catastrophe est,
alors nous allons passer avec succès

154
00:08:55,140 --> 00:08:59,810
le mot chat, mais le mot de curseur
seront faux et pas vrai.

155
00:08:59,810 --> 00:09:04,990
Donc, nous revenons mot de curseur pour indiquer
si ce nœud est en fait un mot,

156
00:09:04,990 --> 00:09:06,530
et c'est tout pour l'enregistrement.

157
00:09:06,530 --> 00:09:08,310
>> Donc, nous allons vérifier Taille.

158
00:09:08,310 --> 00:09:11,410
Ainsi la Taille va être assez facile
car, rappelez-vous en charge, nous sommes

159
00:09:11,410 --> 00:09:15,480
incrémenter taille du dictionnaire pour
chaque mot que nous rencontrons.

160
00:09:15,480 --> 00:09:20,820
Ainsi la Taille va juste revenir
taille de dictionnaire, et c'est tout.

161
00:09:20,820 --> 00:09:24,650
>> Très bien, alors, enfin, nous avons Unload.

162
00:09:24,650 --> 00:09:29,050
Donc Décharger, nous allons utiliser un
fonction récursive pour réellement faire tout

163
00:09:29,050 --> 00:09:33,390
du travail pour nous, de sorte que notre fonction
va être appelé délestage.

164
00:09:33,390 --> 00:09:35,830
Quel est Unloader va faire?

165
00:09:35,830 --> 00:09:40,640
Nous voyons ici que la vidange est va
itérer sur tous les enfants à

166
00:09:40,640 --> 00:09:45,810
ce nœud particulier, et si l'enfant
noeud n'est pas nul, alors nous allons

167
00:09:45,810 --> 00:09:47,760
décharger le nœud enfant.

168
00:09:47,760 --> 00:09:52,070
>> Donc, cela va de façon récursive
décharger tous nos enfants.

169
00:09:52,070 --> 00:09:55,140
Une fois que nous sommes sûrs que tous nos enfants
ont été déchargés, puis nous

170
00:09:55,140 --> 00:09:58,830
peut nous libérer, afin de décharger soi-même.

171
00:09:58,830 --> 00:10:04,550
Donc, ce sera de manière récursive décharger le
Trie ensemble, et puis une fois que c'est

172
00:10:04,550 --> 00:10:06,910
fait, nous ne pouvons retourner vrai.

173
00:10:06,910 --> 00:10:09,770
Décharger ne peut pas échouer, nous sommes
juste libérant les choses.

174
00:10:09,770 --> 00:10:12,985
Donc, une fois que nous aurons fini de libérer
tout, revenir vrai.

175
00:10:12,985 --> 00:10:14,380
Et c'est tout.

176
00:10:14,380 --> 00:10:16,792
Mon nom est Rob, et ce
était [inaudible].

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