1
00:00:00,000 --> 00:00:12,350
>> [MUSIQUE JEU]

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

3
00:00:13,050 --> 00:00:13,640
Je suis Rob.

4
00:00:13,640 --> 00:00:16,210
Et de laisser cette solution sur.

5
00:00:16,210 --> 00:00:20,070
Donc, ici, nous allons mettre en œuvre
un tableau général.

6
00:00:20,070 --> 00:00:24,090
Nous voyons que le noeud de structure de notre
table va ressembler à ceci.

7
00:00:24,090 --> 00:00:28,710
Donc ça va avoir un mot char
tableau de taille LONGUEUR + 1.

8
00:00:28,710 --> 00:00:32,259
Ne pas oublier le + 1, puisque le maximum
mot dans le dictionnaire est de 45

9
00:00:32,259 --> 00:00:33,130
caractères.

10
00:00:33,130 --> 00:00:37,070
Et puis nous allons avoir besoin d'un supplément
caractère pour le zéro de barre oblique inverse.

11
00:00:37,070 --> 00:00:40,870
>> Et puis notre table de hachage dans chaque
seau va stocker une

12
00:00:40,870 --> 00:00:42,320
liste chaînée de noeuds.

13
00:00:42,320 --> 00:00:44,420
Nous ne faisons pas linéaire sondage ici.

14
00:00:44,420 --> 00:00:48,430
Et afin de relier à l'autre
élément dans le seau, nous avons besoin d'une

15
00:00:48,430 --> 00:00:50,390
noeud de struct * prochaine.

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

17
00:00:51,110 --> 00:00:53,090
C'est ce que un nœud ressemble.

18
00:00:53,090 --> 00:00:56,180
>> Maintenant, voici la déclaration
de notre table de hachage.

19
00:00:56,180 --> 00:00:59,640
Il va avoir 16 834 seaux.

20
00:00:59,640 --> 00:01:01,910
Mais ce nombre n'a pas vraiment d'importance.

21
00:01:01,910 --> 00:01:05,450
Et enfin, nous allons avoir l'
taille de la table de hachage variable globale, qui

22
00:01:05,450 --> 00:01:07,000
va commencer à zéro.

23
00:01:07,000 --> 00:01:10,760
Et il va garder une trace de la façon dont
beaucoup de mots sont dans notre dictionnaire.

24
00:01:10,760 --> 00:01:13,710
>> Donc, nous allons jeter un oeil à charge.

25
00:01:13,710 --> 00:01:16,390
Notez que la charge, elle retourne un bool.

26
00:01:16,390 --> 00:01:20,530
Vous revenez vrai si c'était avec succès
chargé, et faux sinon.

27
00:01:20,530 --> 00:01:23,990
Et il prend un char * const dictionnaire,
qui est le dictionnaire

28
00:01:23,990 --> 00:01:25,280
que nous voulons ouvrir.

29
00:01:25,280 --> 00:01:27,170
Donc, c'est la première chose
nous allons faire.

30
00:01:27,170 --> 00:01:29,500
>> Nous allons fopen l'
dictionnaire pour la lecture.

31
00:01:29,500 --> 00:01:31,680
Et nous allons avoir à faire
vous que c'est réussi.

32
00:01:31,680 --> 00:01:35,920
Donc, si il est retourné NULL, alors nous n'avons pas
réussir à ouvrir le dictionnaire.

33
00:01:35,920 --> 00:01:37,440
Et nous devons retourner false.

34
00:01:37,440 --> 00:01:41,580
Mais en supposant qu'il a fait avec succès
ouvert, alors que nous voulons lire le

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

36
00:01:42,400 --> 00:01:46,450
Donc tourne en boucle jusqu'à ce qu'on trouve une certaine
raison de sortir de cette boucle,

37
00:01:46,450 --> 00:01:47,570
que nous allons voir.

38
00:01:47,570 --> 00:01:48,920
Donc, tourne en boucle.

39
00:01:48,920 --> 00:01:51,780
>> Et maintenant, nous allons
malloc un seul nœud.

40
00:01:51,780 --> 00:01:54,020
Et bien sûr, nous avons besoin
pour aérer vérifier de nouveau.

41
00:01:54,020 --> 00:01:58,680
Donc, si allouer de ne pas réussir, alors
nous voulons décharger un nœud que nous

42
00:01:58,680 --> 00:02:02,590
arrivé à malloc avant, fermer la
dictionnaire et retourner false.

43
00:02:02,590 --> 00:02:06,830
Mais en ignorant que, en supposant que nous
réussi, alors nous voulons utiliser fscanf

44
00:02:06,830 --> 00:02:12,400
de lire un seul mot de notre
par dictionnaire dans notre nœud.

45
00:02:12,400 --> 00:02:17,940
Alors, n'oubliez pas que l'entrée> mot est l'omble
mot tampon de taille Lenghth + 1

46
00:02:17,940 --> 00:02:20,300
que nous allons stocker le mot po

47
00:02:20,300 --> 00:02:25,070
>> Donc fscanf va revenir 1, aussi longtemps
comme il a pu avec succès

48
00:02:25,070 --> 00:02:26,750
lire un mot à partir du fichier.

49
00:02:26,750 --> 00:02:30,460
Si une erreur se produit, soit, ou nous
atteindre la fin du fichier, il

50
00:02:30,460 --> 00:02:31,950
ne reviendra pas 1.

51
00:02:31,950 --> 00:02:35,180
Dans ce cas, il ne revient pas 1,
nous allons enfin sortir de

52
00:02:35,180 --> 00:02:37,280
cette boucle while.

53
00:02:37,280 --> 00:02:42,770
Ainsi, nous voyons qu'une fois que nous avons réussi à
lire un mot en

54
00:02:42,770 --> 00:02:48,270
entrée> mot, puis nous allons à cette
mot en utilisant notre fonction de hachage.

55
00:02:48,270 --> 00:02:49,580
>> Jetons un coup d'œil à
la fonction de hachage.

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

57
00:02:52,430 --> 00:02:55,610
Donc, vous n'avez pas vraiment besoin
pour comprendre cela.

58
00:02:55,610 --> 00:02:59,460
Et en fait, nous sommes arrivés juste ce hachage
fonctionner à partir d'Internet.

59
00:02:59,460 --> 00:03:04,010
La seule chose que vous devez reconnaître, c'est
que cela prend un char * mot const.

60
00:03:04,010 --> 00:03:08,960
Il s'agit donc de prendre une chaîne en entrée, et
retour d'un unsigned int en sortie.

61
00:03:08,960 --> 00:03:12,360
Donc, c'est tout une fonction de hachage est, est-il
prend en entrée et vous donne une

62
00:03:12,360 --> 00:03:14,490
index dans la table de hachage.

63
00:03:14,490 --> 00:03:18,530
>> Notez que nous n'avons moding par num_buckets,
de sorte que la valeur retournée

64
00:03:18,530 --> 00:03:21,730
est en fait un index dans la table de hachage
et n'indexe pas au-delà de la

65
00:03:21,730 --> 00:03:24,320
limites du tableau.

66
00:03:24,320 --> 00:03:28,060
Donc, étant donné que la fonction, nous allons
pour hacher le mot que nous lisons l'

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

68
00:03:29,390 --> 00:03:31,700
Et puis nous allons utiliser
ce hachage pour insérer le

69
00:03:31,700 --> 00:03:33,750
entrée dans la table de hachage.

70
00:03:33,750 --> 00:03:38,520
>> Hachage Maintenant table de hachage est le courant
liste chaînée dans le tableau.

71
00:03:38,520 --> 00:03:41,410
Et il est très possible
que c'est juste NULL.

72
00:03:41,410 --> 00:03:44,960
Nous voulons insérer notre entrée à l'
à partir de cette liste chaînée.

73
00:03:44,960 --> 00:03:48,600
Et donc nous allons avoir notre courant
le point à ce que la table de hachage d'entrée

74
00:03:48,600 --> 00:03:50,380
des points actuellement.

75
00:03:50,380 --> 00:03:53,310
Et puis nous allons stocker,
dans la table de hachage à l'

76
00:03:53,310 --> 00:03:55,350
hachage, l'entrée actuelle.

77
00:03:55,350 --> 00:03:59,320
Donc, ces deux lignes insérer avec succès
l'entrée au début de l'

78
00:03:59,320 --> 00:04:02,260
liste liée à l'index
dans la table de hachage.

79
00:04:02,260 --> 00:04:04,900
>> Une fois que nous en avons terminé avec cela, nous savons
que nous avons trouvé un autre mot dans la

80
00:04:04,900 --> 00:04:07,790
dictionnaire, et on incrémente à nouveau.

81
00:04:07,790 --> 00:04:13,960
Donc, nous continuons à faire que jusqu'à fscanf
enfin de retour quelque chose de non-1 à

82
00:04:13,960 --> 00:04:16,950
quel point rappeler que
nous devons libérer entrée.

83
00:04:16,950 --> 00:04:19,459
Donc, ici nous malloced une entrée.

84
00:04:19,459 --> 00:04:21,329
Et nous avons essayé de lire quelque chose
du dictionnaire.

85
00:04:21,329 --> 00:04:23,910
Et nous n'avons pas lu avec succès
quelque chose à partir du dictionnaire, dans

86
00:04:23,910 --> 00:04:26,650
auquel cas nous devons libérer l'entrée
que nous n'avons jamais mis dans le

87
00:04:26,650 --> 00:04:29,140
table de hachage, et enfin briser.

88
00:04:29,140 --> 00:04:32,750
>> Une fois que nous échappons, nous devons voir, eh bien,
n'avons nous rompons parce qu'il n'y

89
00:04:32,750 --> 00:04:34,360
a été une erreur de lecture du fichier?

90
00:04:34,360 --> 00:04:37,120
Ou avons-nous rompons parce que nous
atteint la fin du fichier?

91
00:04:37,120 --> 00:04:39,480
S'il y avait une erreur,
nous voulons retourner faux.

92
00:04:39,480 --> 00:04:40,930
Parce que la charge n'a pas réussi.

93
00:04:40,930 --> 00:04:43,890
Et dans le processus, nous voulons décharger
tous les mots que nous lisons dans et

94
00:04:43,890 --> 00:04:45,670
fermer le fichier du dictionnaire.

95
00:04:45,670 --> 00:04:48,740
>> En supposant que nous avons réussi, alors que nous venons de
encore besoin de fermer le dictionnaire

96
00:04:48,740 --> 00:04:53,040
déposer, et revenir enfin vrai puisque nous
chargé le dictionnaire.

97
00:04:53,040 --> 00:04:54,420
Et c'est tout pour la charge.

98
00:04:54,420 --> 00:04:59,020
Alors maintenant, vérifier, étant donné une table de hachage chargé,
va ressembler à ceci.

99
00:04:59,020 --> 00:05:03,140
Afin de vérifier, il retourne un bool, ce qui est
va indiquer si le passé

100
00:05:03,140 --> 00:05:07,530
en char * mot, si le passé
dans la chaîne est dans notre dictionnaire.

101
00:05:07,530 --> 00:05:09,890
Donc, si elle est dans le dictionnaire,
si c'est dans notre table de hachage,

102
00:05:09,890 --> 00:05:11,170
nous reviendrons vrai.

103
00:05:11,170 --> 00:05:13,380
Et si ce n'est pas, nous reviendrons faux.

104
00:05:13,380 --> 00:05:17,740
>> Étant donné ce passé dans le mot, nous sommes
va hacher le mot.

105
00:05:17,740 --> 00:05:22,110
Maintenant une chose importante à reconnaître est
que la charge que nous savions que tous les

106
00:05:22,110 --> 00:05:23,820
mots que nous allons être en minuscules.

107
00:05:23,820 --> 00:05:25,820
Mais ici, nous ne sommes pas si sûr.

108
00:05:25,820 --> 00:05:29,510
Si nous prenons un coup d'oeil à notre fonction de hachage,
notre fonction de hachage fait

109
00:05:29,510 --> 00:05:32,700
boîtier inférieur est chaque caractère
du mot.

110
00:05:32,700 --> 00:05:37,940
Donc, quelle que soit la capitalisation des
mot, notre fonction de hachage est le retour

111
00:05:37,940 --> 00:05:42,270
le même indice pour quelle que soit la
la capitalisation est, comme il aurait

112
00:05:42,270 --> 00:05:45,280
retourné pour un tout minuscule
version du mot.

113
00:05:45,280 --> 00:05:46,600
Très bien.

114
00:05:46,600 --> 00:05:49,790
C'est notre indice est dans le
Hashtable pour ce mot.

115
00:05:49,790 --> 00:05:52,940
>> Or, cette boucle va
parcourir la liste chaînée

116
00:05:52,940 --> 00:05:55,000
que c'était à cet index.

117
00:05:55,000 --> 00:05:59,610
Donc, nous remarquons l'initialisation entrée
pour pointer vers cet index.

118
00:05:59,610 --> 00:06:02,750
Nous allons continuer
tandis que l'entrée! = NULL.

119
00:06:02,750 --> 00:06:07,770
Et rappelez-vous que la mise à jour du pointeur
dans notre entrée de liste liée = entrée> prochaine.

120
00:06:07,770 --> 00:06:14,400
Alors que notre point d'entrée actuel à
l'élément suivant dans la liste chaînée.

121
00:06:14,400 --> 00:06:19,250
>> Ainsi, pour chaque entrée dans la liste liée,
nous allons utiliser strcasecmp.

122
00:06:19,250 --> 00:06:20,330
Ce n'est pas StrComp.

123
00:06:20,330 --> 00:06:23,780
Car encore une fois, nous voulons
faire des choses sensible à la casse.

124
00:06:23,780 --> 00:06:27,870
Nous utilisons donc strcasecmp de comparer la
mot qui a été adoptée par cette

125
00:06:27,870 --> 00:06:31,860
fonction contre le mot
c'est dans cette entrée.

126
00:06:31,860 --> 00:06:35,570
Si elle retourne zéro, cela signifie qu'il a été
un match, dans ce cas, nous voulons

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

128
00:06:36,630 --> 00:06:39,590
Nous avons trouvé le succès
mot dans notre table de hachage.

129
00:06:39,590 --> 00:06:43,040
>> S'il n'y avait pas un match, alors nous sommes
aller à boucle encore et regarder la

130
00:06:43,040 --> 00:06:43,990
entrée suivante.

131
00:06:43,990 --> 00:06:47,640
Et nous allons continuer boucle alors qu'il
sont entrées dans cette liste chaînée.

132
00:06:47,640 --> 00:06:50,160
Qu'advient-il si nous rompons
sortir de cette boucle?

133
00:06:50,160 --> 00:06:55,110
Cela signifie que nous n'avons pas trouvé une entrée qui
identifié ce mot, dans ce cas,

134
00:06:55,110 --> 00:07:00,220
nous retournons false pour indiquer que notre
ne contient pas de table de hachage ce mot.

135
00:07:00,220 --> 00:07:02,540
Et c'est un chèque.

136
00:07:02,540 --> 00:07:04,790
>> Donc, nous allons jeter un oeil à la taille.

137
00:07:04,790 --> 00:07:06,970
Maintenant taille va être assez simple.

138
00:07:06,970 --> 00:07:11,080
Depuis souvenir en charge, pour chaque mot
nous avons trouvé, nous incrémentons un mondial

139
00:07:11,080 --> 00:07:12,880
taille de la table de hachage variable.

140
00:07:12,880 --> 00:07:16,480
Ainsi, la fonction de la taille va juste
pour revenir variable globale.

141
00:07:16,480 --> 00:07:18,150
Et c'est tout.

142
00:07:18,150 --> 00:07:22,300
>> Maintenant, enfin, nous avons besoin de décharger le
dictionnaire une fois que tout est fait.

143
00:07:22,300 --> 00:07:25,340
Alors, comment allons-nous faire?

144
00:07:25,340 --> 00:07:30,440
Ici, nous sommes en boucle sur
tous les godets de notre table.

145
00:07:30,440 --> 00:07:33,240
Donc, il ya num_buckets seaux.

146
00:07:33,240 --> 00:07:37,410
Et pour chaque liste liée dans notre
table de hachage, nous allons faire une boucle sur

147
00:07:37,410 --> 00:07:41,070
la totalité de la liste chaînée,
libérer chaque élément.

148
00:07:41,070 --> 00:07:42,900
>> Maintenant, nous devons être prudents.

149
00:07:42,900 --> 00:07:47,910
Nous avons donc ici une variable temporaire
C'est stocker le pointeur à l'autre

150
00:07:47,910 --> 00:07:49,730
élément dans la liste chaînée.

151
00:07:49,730 --> 00:07:52,140
Et puis nous allons à la libre
l'élément courant.

152
00:07:52,140 --> 00:07:55,990
Nous devons être sûrs que nous faisons depuis que nous avons
ne peut pas simplement libérer l'élément courant

153
00:07:55,990 --> 00:07:59,180
puis essayer d'accéder au pointeur suivant,
car une fois que nous avons libéré il,

154
00:07:59,180 --> 00:08:00,870
la mémoire devient invalide.

155
00:08:00,870 --> 00:08:04,990
>> Nous devons donc garder autour d'un pointeur vers
l'élément suivant, alors nous pouvons libérer l'

156
00:08:04,990 --> 00:08:08,360
élément courant, et alors nous pouvons mettre à jour
notre élément courant jusqu'au point de

157
00:08:08,360 --> 00:08:09,550
l'élément suivant.

158
00:08:09,550 --> 00:08:12,800
Nous allons boucle alors qu'il ya des éléments
dans cette liste chaînée.

159
00:08:12,800 --> 00:08:15,620
Nous le ferons pour tous liés
listes dans la table de hachage.

160
00:08:15,620 --> 00:08:19,460
Et une fois que nous en avons terminé avec cela, nous avons
complètement déchargé la table de hachage, et

161
00:08:19,460 --> 00:08:20,190
nous aurons terminé.

162
00:08:20,190 --> 00:08:23,200
Il est donc impossible pour le déchargement
à jamais retourner false.

163
00:08:23,200 --> 00:08:26,470
Et quand nous aurons terminé, nous
il suffit de retourner vrai.

164
00:08:26,470 --> 00:08:29,000
>> Donnons cette solution un essai.

165
00:08:29,000 --> 00:08:33,070
Donc, nous allons jeter un oeil à ce que notre
noeud de structure ressemblera.

166
00:08:33,070 --> 00:08:36,220
Ici, nous voyons que nous allons avoir un bool
mot et un noeud de struct * pour enfants

167
00:08:36,220 --> 00:08:37,470
support alphabet.

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

169
00:08:38,929 --> 00:08:42,020
Donc, la première chose que vous seriez peut-être
demander, pourquoi est ALPHABET

170
00:08:42,020 --> 00:08:44,660
ed définie comme 27?

171
00:08:44,660 --> 00:08:47,900
Eh bien, rappelez-vous que nous allons avoir besoin de
à la manipulation de l'apostrophe.

172
00:08:47,900 --> 00:08:51,910
Donc cela va être un peu un
cas particulier tout au long de ce programme.

173
00:08:51,910 --> 00:08:54,710
>> Maintenant rappeler comment un trie
fonctionne réellement.

174
00:08:54,710 --> 00:08:59,380
Disons que nous sommes indexer le mot
«chats». Puis à partir de la racine de Trie,

175
00:08:59,380 --> 00:09:02,610
nous allons regarder les enfants
tableau, et nous allons regarder la

176
00:09:02,610 --> 00:09:08,090
indice qui correspond à la lettre
C. Alors qui sera indexé 2.

177
00:09:08,090 --> 00:09:11,530
Donc, étant donné que, cette volonté
nous donner un nouveau nœud.

178
00:09:11,530 --> 00:09:13,820
Et puis nous allons travailler à partir de ce nœud.

179
00:09:13,820 --> 00:09:17,770
>> Donc, étant donné que le noeud, nous sommes une fois de plus
va regarder le tableau des enfants.

180
00:09:17,770 --> 00:09:22,110
Et nous allons voir à l'index zéro
pour correspondre à l'un de cat.

181
00:09:22,110 --> 00:09:27,170
Alors nous allons aller à ce nœud,
et étant donné que nous allons noeud

182
00:09:27,170 --> 00:09:31,090
à regarder à la fin c'est un correspond
T. Et de passer à ce nœud,

183
00:09:31,090 --> 00:09:35,530
enfin, nous avons complètement regardé
grâce à notre mot «chat». Et maintenant bool

184
00:09:35,530 --> 00:09:40,960
mot est censé indiquer si
cette parole donnée est en fait un mot.

185
00:09:40,960 --> 00:09:43,470
>> Alors pourquoi avons-nous besoin ce cas particulier?

186
00:09:43,470 --> 00:09:47,700
Eh bien ce que le mot «catastrophe»
est dans notre dictionnaire, mais la

187
00:09:47,700 --> 00:09:50,150
mot «chat» n'est pas?

188
00:09:50,150 --> 00:09:54,580
Ainsi et afin de voir si le mot "chat"
est dans notre dictionnaire, nous sommes

189
00:09:54,580 --> 00:09:59,970
va regarder avec succès par
les indices C-A-T en noeud de la région.

190
00:09:59,970 --> 00:10:04,290
Mais c'est seulement parce que la catastrophe
arrivé à créer des nœuds sur le chemin

191
00:10:04,290 --> 00:10:07,190
à partir de C-A-T, tout le chemin pour
la fin du mot.

192
00:10:07,190 --> 00:10:12,020
Donc bool mot est utilisé pour indiquer si
cet endroit particulier

193
00:10:12,020 --> 00:10:14,310
indique en fait un mot.

194
00:10:14,310 --> 00:10:15,140
>> Très bien.

195
00:10:15,140 --> 00:10:19,310
Alors, maintenant que nous savons ce qu'il trie est
va ressembler, regardons l'

196
00:10:19,310 --> 00:10:20,730
charger la fonction.

197
00:10:20,730 --> 00:10:24,610
Donc, la charge va revenir un bool
pour que nous succès ou

198
00:10:24,610 --> 00:10:26,720
en vain chargé le dictionnaire.

199
00:10:26,720 --> 00:10:30,460
Et ce sera le dictionnaire
que nous voulons charger.

200
00:10:30,460 --> 00:10:33,930
>> Donc la première chose que nous sommes à faire est d'ouvrir
jusqu'à ce dictionnaire pour la lecture.

201
00:10:33,930 --> 00:10:36,160
Et nous devons faire en sorte
nous n'avons pas manqué.

202
00:10:36,160 --> 00:10:39,580
Donc, si le dictionnaire n'a pas été
ouvert avec succès, il sera de retour

203
00:10:39,580 --> 00:10:42,400
null, auquel cas nous sommes
va retourner false.

204
00:10:42,400 --> 00:10:47,230
Mais en supposant qu'il succès
ouvert, alors nous pouvons lire

205
00:10:47,230 --> 00:10:48,220
par le dictionnaire.

206
00:10:48,220 --> 00:10:50,880
>> Donc la première chose que nous allons
voulons faire, c'est ce que nous avons

207
00:10:50,880 --> 00:10:52,500
racine variable globale.

208
00:10:52,500 --> 00:10:56,190
Maintenant racine va être un noeud *.

209
00:10:56,190 --> 00:10:59,760
C'est le sommet de notre trie que nous sommes
va être itérer.

210
00:10:59,760 --> 00:11:02,660
Donc la première chose que nous allons
à vouloir faire est d'allouer

211
00:11:02,660 --> 00:11:04,140
mémoire pour notre racine.

212
00:11:04,140 --> 00:11:07,980
Notez que nous utilisons le calloc
fonction, qui est essentiellement le même

213
00:11:07,980 --> 00:11:11,500
que la fonction malloc, sauf que c'est
garantie de renvoyer quelque chose qui est

214
00:11:11,500 --> 00:11:13,180
complètement remis à zéro.

215
00:11:13,180 --> 00:11:17,290
Donc, si nous avons utilisé malloc, nous aurions besoin de
passer en revue tous les pointeurs dans notre

216
00:11:17,290 --> 00:11:20,160
noeud, et assurez-vous que
ils sont tous nuls.

217
00:11:20,160 --> 00:11:22,710
Donc calloc le fera pour nous.

218
00:11:22,710 --> 00:11:26,330
>> Maintenant comme malloc, nous devons faire
s'assurer que la répartition était effectivement

219
00:11:26,330 --> 00:11:27,520
réussie.

220
00:11:27,520 --> 00:11:29,990
Si cette retourné null, alors nous
besoin de fermer ou de dictionnaire

221
00:11:29,990 --> 00:11:32,100
déposer et retourner false.

222
00:11:32,100 --> 00:11:36,835
Supposant donc que l'allocation a été
succès, nous allons utiliser un noeud *

223
00:11:36,835 --> 00:11:40,270
curseur pour parcourir notre trie.

224
00:11:40,270 --> 00:11:43,890
Ainsi, nos racines ne changera jamais,
mais nous allons utiliser le curseur à

225
00:11:43,890 --> 00:11:47,875
effectivement aller de noeud à noeud.

226
00:11:47,875 --> 00:11:50,940
>> Ainsi, dans cette boucle que nous lisons
dans le fichier de dictionnaire.

227
00:11:50,940 --> 00:11:53,670
Et nous utilisons fgetc.

228
00:11:53,670 --> 00:11:56,290
Fgetc va prendre un seul
caractère du fichier.

229
00:11:56,290 --> 00:11:59,370
Nous allons continuer à saisir
caractères alors que nous ne parvenons pas à la

230
00:11:59,370 --> 00:12:01,570
fin du fichier.

231
00:12:01,570 --> 00:12:03,480
>> Il ya deux cas, nous devons gérer.

232
00:12:03,480 --> 00:12:06,610
La première, si le caractère
n'était pas une nouvelle ligne.

233
00:12:06,610 --> 00:12:10,450
Nous savons donc s'il s'agissait d'une nouvelle ligne, puis
nous sommes sur le point de passer à un nouveau mot.

234
00:12:10,450 --> 00:12:15,240
Mais à supposer que ce n'était pas une nouvelle ligne, puis
ici nous voulons comprendre la

235
00:12:15,240 --> 00:12:18,380
indice que nous allons à l'index dans
dans le tableau enfants

236
00:12:18,380 --> 00:12:19,810
nous avons regardé avant.

237
00:12:19,810 --> 00:12:23,880
>> Donc, comme je l'ai dit avant, nous devons
cas particulier de l'apostrophe.

238
00:12:23,880 --> 00:12:26,220
Notez que nous utilisons le ternaire
opérateur ici.

239
00:12:26,220 --> 00:12:29,580
Nous allons donc lire ce que, si
le caractère que nous lisons dans était un

240
00:12:29,580 --> 00:12:35,330
apostrophe, alors nous allons mettre en
index = "alphabet" -1, ce qui sera

241
00:12:35,330 --> 00:12:37,680
être l'indice 26.

242
00:12:37,680 --> 00:12:41,130
>> Sinon, si ce n'était pas une apostrophe, il
nous allons définir l'index

243
00:12:41,130 --> 00:12:43,760
égale à c - a.

244
00:12:43,760 --> 00:12:49,030
Alors, n'oubliez pas de retour de précédemment p-ensembles,
c - une va nous le donner

245
00:12:49,030 --> 00:12:53,410
la position alphabétique de C. Donc, si
C est la lettre A, ce sera

246
00:12:53,410 --> 00:12:54,700
nous donner l'indice zéro.

247
00:12:54,700 --> 00:12:58,120
Pour la lettre B, il donnera
nous l'index 1, et ainsi de suite.

248
00:12:58,120 --> 00:13:03,010
>> Cela nous donne l'index dans le
enfants ensemble que nous voulons.

249
00:13:03,010 --> 00:13:08,890
Maintenant, si cet indice est actuellement nulle dans
les enfants, ce qui signifie que le nœud

250
00:13:08,890 --> 00:13:11,830
n'existe pas actuellement
à partir de cette voie.

251
00:13:11,830 --> 00:13:15,160
Nous avons donc besoin d'allouer
un noeud de ce chemin.

252
00:13:15,160 --> 00:13:16,550
C'est ce que nous allons faire ici.

253
00:13:16,550 --> 00:13:20,690
>> Donc, nous allons à nouveau utiliser le calloc
fonction, de sorte que nous n'avons pas à

254
00:13:20,690 --> 00:13:22,880
zéro sur tous les pointeurs.

255
00:13:22,880 --> 00:13:27,240
Et nous avons encore besoin de vérifier
que calloc n'a pas manqué.

256
00:13:27,240 --> 00:13:30,700
Si calloc n'at-il pas, alors nous devons
pour décharger tout, fermer notre

257
00:13:30,700 --> 00:13:32,820
dictionnaire, et retourner false.

258
00:13:32,820 --> 00:13:40,050
Donc, en supposant qu'il n'a pas manqué, alors
cela va créer un nouvel enfant pour nous.

259
00:13:40,050 --> 00:13:41,930
Et puis nous irons à l'enfant.

260
00:13:41,930 --> 00:13:44,960
Notre curseur va parcourir
jusqu'à ce que l'enfant.

261
00:13:44,960 --> 00:13:49,330
>> Maintenant, si ce n'était pas nul pour commencer,
alors le curseur peut seulement parcourir

262
00:13:49,330 --> 00:13:52,590
jusqu'à ce que l'enfant sans réellement
avoir à allouer rien.

263
00:13:52,590 --> 00:13:56,730
C'est le cas où nous avons d'abord arrivé
allouer le mot «chat». Et

264
00:13:56,730 --> 00:14:00,330
Cela signifie que lorsque nous allons à allouer
"Catastrophe", nous n'avons pas besoin de créer

265
00:14:00,330 --> 00:14:01,680
noeuds pour C-A-T nouveau.

266
00:14:01,680 --> 00:14:04,830
Ils existent déjà.

267
00:14:04,830 --> 00:14:06,080
>> Quel est ce monde?

268
00:14:06,080 --> 00:14:10,480
C'est la condition où c était
barre oblique inverse n, c était une nouvelle ligne.

269
00:14:10,480 --> 00:14:13,710
Cela signifie que nous avons réussi à
complété un mot.

270
00:14:13,710 --> 00:14:16,860
Maintenant que voulons-nous faire quand nous
terminé avec succès un mot?

271
00:14:16,860 --> 00:14:21,100
Nous allons utiliser ce champ de texte
à l'intérieur de notre noeud de structure.

272
00:14:21,100 --> 00:14:23,390
Nous voulons mettre que de vrai.

273
00:14:23,390 --> 00:14:27,150
Ainsi, cela indique que ce noeud
indique un succès

274
00:14:27,150 --> 00:14:29,250
mot, un mot réel.

275
00:14:29,250 --> 00:14:30,940
>> Réglez maintenant que de vrai.

276
00:14:30,940 --> 00:14:35,150
Nous voulons rétablir notre curseur sur le point
au début de la trie à nouveau.

277
00:14:35,150 --> 00:14:40,160
Et enfin, augmenter notre dictionnaire
taille, puisque nous avons trouvé un autre travail.

278
00:14:40,160 --> 00:14:43,230
Donc, nous allons continuer à le faire,
lecture caractère par caractère,

279
00:14:43,230 --> 00:14:49,150
la construction de nouveaux nœuds dans notre trie et
pour chaque mot dans le dictionnaire, jusqu'à ce que

280
00:14:49,150 --> 00:14:54,020
nous arrivons enfin C! = EOF, dans lequel
cas nous sortir du fichier.

281
00:14:54,020 --> 00:14:57,050
>> Maintenant il ya deux cas sous
que nous aurions pu frapper EOF.

282
00:14:57,050 --> 00:15:00,980
La première est de savoir si il y avait une erreur
la lecture du fichier.

283
00:15:00,980 --> 00:15:03,470
Donc, si il y avait une erreur, nous
besoin de faire la typique.

284
00:15:03,470 --> 00:15:06,460
Décharger tout, près
le fichier, return false.

285
00:15:06,460 --> 00:15:09,810
En supposant qu'il n'y a pas d'erreur, que
signifie simplement que nous effectivement touché la fin de

286
00:15:09,810 --> 00:15:13,750
le fichier, dans ce cas, nous fermons l'
déposer et revenir vrai que nous

287
00:15:13,750 --> 00:15:17,330
dictionnaire chargé avec succès
dans notre trie.

288
00:15:17,330 --> 00:15:20,170
>> Alors maintenant, nous allons vérifier chèque.

289
00:15:20,170 --> 00:15:25,156
En regardant la fonction de contrôle, nous voyons
que l'enregistrement va revenir un bool.

290
00:15:25,156 --> 00:15:29,680
Elle retourne true si ce mot que c'est
étant passé est dans notre trie.

291
00:15:29,680 --> 00:15:32,110
Il retourne false sinon.

292
00:15:32,110 --> 00:15:36,050
Alors, comment allez-vous déterminer si
ce mot est dans notre trie?

293
00:15:36,050 --> 00:15:40,190
>> Nous voyons ici que, comme avant,
nous allons utiliser le curseur pour parcourir

294
00:15:40,190 --> 00:15:41,970
grâce à notre trie.

295
00:15:41,970 --> 00:15:46,600
Ici nous allons parcourir
sur l'ensemble de notre parole.

296
00:15:46,600 --> 00:15:50,620
Donc itération sur le mot que nous sommes passé,
nous allons déterminer la

297
00:15:50,620 --> 00:15:56,400
index dans le tableau des enfants
correspond à mot support I. Donc, ce

298
00:15:56,400 --> 00:15:59,670
va ressembler exactement
charge, où si le mot [i]

299
00:15:59,670 --> 00:16:03,310
est une apostrophe, alors nous voulons
à utiliser l'index "alphabet" - 1.

300
00:16:03,310 --> 00:16:05,350
Parce que nous avons déterminé que ce
C'est là que nous allons stocker

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

302
00:16:07,100 --> 00:16:11,780
>> Sinon nous allons utiliser deux mots inférieure
support I. Alors, n'oubliez pas que ce mot peut

303
00:16:11,780 --> 00:16:13,920
ont capitalisation arbitraire.

304
00:16:13,920 --> 00:16:17,540
Et si nous voulons nous assurer que nous sommes
en utilisant une version en minuscules des choses.

305
00:16:17,540 --> 00:16:21,920
Et puis soustraire de ce «a» à la fois
nous redonner la alphabétique

306
00:16:21,920 --> 00:16:23,880
la position de ce caractère.

307
00:16:23,880 --> 00:16:27,680
Alors que va être notre index
dans le tableau des enfants.

308
00:16:27,680 --> 00:16:32,420
>> Et maintenant, si cet indice dans les enfants
tableau est nulle, cela signifie que nous

309
00:16:32,420 --> 00:16:34,990
ne peut plus continuer itération
en bas de notre trie.

310
00:16:34,990 --> 00:16:38,870
Si c'est le cas, ce mot ne peut pas
éventuellement dans notre trie.

311
00:16:38,870 --> 00:16:42,340
Etant donné que s'il s'agissait d', qui serait
cela signifie qu'il y aurait un trajet

312
00:16:42,340 --> 00:16:43,510
jusqu'à ce mot.

313
00:16:43,510 --> 00:16:45,290
Et vous ne rencontrerez jamais nulle.

314
00:16:45,290 --> 00:16:47,850
Donc rencontrer nulle, nous revenons faux.

315
00:16:47,850 --> 00:16:49,840
Le mot n'est pas dans le dictionnaire.

316
00:16:49,840 --> 00:16:53,660
Si ce n'était pas nulle, alors nous sommes
va continuer itération.

317
00:16:53,660 --> 00:16:57,220
>> Donc, nous allons là-bas curseur
au point à ce particulier

318
00:16:57,220 --> 00:16:59,760
nœud à l'index.

319
00:16:59,760 --> 00:17:03,150
Nous continuons à faire que tout au long
le mot entier, en supposant

320
00:17:03,150 --> 00:17:03,950
nous n'avons jamais touché nulle.

321
00:17:03,950 --> 00:17:07,220
Cela signifie que nous avons pu passer à travers
le mot entier et de trouver

322
00:17:07,220 --> 00:17:08,920
un noeud dans notre essai.

323
00:17:08,920 --> 00:17:10,770
Mais nous ne sommes pas encore tout à fait terminé.

324
00:17:10,770 --> 00:17:12,290
>> Nous ne voulons pas simplement retourner vrai.

325
00:17:12,290 --> 00:17:14,770
Nous voulons retourner curseur> mot.

326
00:17:14,770 --> 00:17:18,980
Depuis n'oubliez pas nouveau, est «chat» n'est pas
dans notre dictionnaire, et "catastrophe"

327
00:17:18,980 --> 00:17:22,935
est, alors nous réussirons à nous obtenons
par le mot "chat". Mais curseur

328
00:17:22,935 --> 00:17:25,760
mot sera faux et pas vrai.

329
00:17:25,760 --> 00:17:30,930
Donc, nous revenons mot de curseur pour indiquer
si ce nœud est en fait un mot.

330
00:17:30,930 --> 00:17:32,470
Et c'est tout pour l'enregistrement.

331
00:17:32,470 --> 00:17:34,250
>> Donc, nous allons vérifier la taille.

332
00:17:34,250 --> 00:17:37,350
Donc, la taille va être assez facile
car, rappelez-vous en charge, nous sommes

333
00:17:37,350 --> 00:17:41,430
incrémenter taille du dictionnaire pour
chaque mot que nous rencontrons.

334
00:17:41,430 --> 00:17:45,350
Donc, la taille va juste
retourner la taille du dictionnaire.

335
00:17:45,350 --> 00:17:47,390
Et c'est tout.

336
00:17:47,390 --> 00:17:50,590
>> Donc, nous avons enfin décharger.

337
00:17:50,590 --> 00:17:55,100
Donc, décharger, nous allons utiliser une
fonction récursive pour réellement faire tout

338
00:17:55,100 --> 00:17:56,530
du travail pour nous.

339
00:17:56,530 --> 00:17:59,340
Donc notre fonction va
être appelé sur déchargeur.

340
00:17:59,340 --> 00:18:01,650
Quel est déchargeur va faire?

341
00:18:01,650 --> 00:18:06,580
Nous voyons ici que déchargeur va
itérer sur tous les enfants à

342
00:18:06,580 --> 00:18:08,410
ce nœud particulier.

343
00:18:08,410 --> 00:18:11,750
Et si le nœud de l'enfant n'est pas
nul, alors nous allons

344
00:18:11,750 --> 00:18:13,730
décharger le nœud enfant.

345
00:18:13,730 --> 00:18:18,010
>> Donc, c'est vous déchargez de manière récursive
tous nos enfants.

346
00:18:18,010 --> 00:18:21,080
Une fois que nous sommes sûrs que tous nos enfants
ont été déchargés, puis nous

347
00:18:21,080 --> 00:18:25,210
peut nous libérer, de sorte
nous décharger.

348
00:18:25,210 --> 00:18:29,460
Cela fonctionnera de manière récursive
décharger la totalité de trie.

349
00:18:29,460 --> 00:18:32,850
Et puis une fois que c'est fait,
nous ne pouvons retourner true.

350
00:18:32,850 --> 00:18:34,210
Décharger ne peut pas échouer.

351
00:18:34,210 --> 00:18:35,710
Nous sommes en train de libérer des choses.

352
00:18:35,710 --> 00:18:38,870
Donc, une fois que nous aurons fini de libérer
tout, retourne true.

353
00:18:38,870 --> 00:18:40,320
Et c'est tout.

354
00:18:40,320 --> 00:18:41,080
Mon nom est Rob.

355
00:18:41,080 --> 00:18:42,426
Et ce fut correcteur orthographique.

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