>> INTERLOCUTEUR 1: Donnons cette solution un essai.
Donc, nous allons jeter un oeil à ce que notre noeud de Struct va ressembler.
Ici, nous voyons que nous allons avoir un Bool Word et un noeud étoiles Struct
Enfants encadrent alphabet.
Donc la première chose que vous demandez peut-être, pourquoi hachage alphabet défini comme 27?
Eh bien, rappelez-vous que nous allons avoir besoin de à la manipulation de l'apostrophe, alors
que ça va être un peu un spécial cas tout au long de ce programme.
>> OK, maintenant, rappelez-vous comment un Trie fonctionne réellement.
Disons que nous sommes l'indexation des mots chats, puis à partir de la racine de notre Trie,
nous allons regarder les enfants tableau, et nous allons regarder la
indice qui correspond à la lettre C. Donc, ce serait deux index.
Donc, étant donné que, cela nous donnera un nouveau noeud, puis nous allons
travailler à partir de ce nœud.
>> Donc, étant donné que le noeud, nous sommes une fois de plus va regarder le tableau des enfants,
et nous allons voir à l'index zéro pour correspondre à l'un de cat.
Alors nous allons aller à ce nœud, et compte tenu de ce nœud, nous allons
à regarder l'indice qui correspond T. Et de passer à ce nœud,
enfin, nous avons complètement regardé grâce à notre mot chat, et maintenant Bool
Word est censé indiquer si cette parole donnée est en fait un mot.
>> Alors pourquoi avons-nous besoin ce cas particulier?
Eh bien, si le mot catastrophe est dans notre dictionnaire, mais
le mot chat n'est pas?
Donc, en cherchant à voir si le mot chat est dans notre dictionnaire, nous allons
regarder avec succès à travers les indices C-A-T et d'atteindre un nœud, mais c'est
seulement parce que la catastrophe qui s'est passé à créer des nœuds sur le chemin de C-A-T tout
le chemin de la fin du mot.
Donc Bool Word est utilisé indiquer si cet emplacement particulier fait
indique un mot.
>> Bon, maintenant que nous savons ce qu'est un Trie va ressembler, regardons
à la fonction de charge.
Donc, la charge va revenir un Bool pour que nous succès ou
dictionnaire vain chargé et cela va être le dictionnaire
que nous voulons charger.
Donc la première chose que nous allons faire est d'ouvrir jusqu'à ce dictionnaire pour la lecture.
Nous devons nous assurer que nous n'avons pas manqué, donc si le dictionnaire n'a pas été
ouvert avec succès, il sera de retour Non, dans ce cas, nous allons
retourner False.
Mais en supposant qu'il succès ouvert, alors nous pouvons lire
par le dictionnaire.
>> Donc la première chose que nous allons voulons faire, c'est ce que nous avons
racine variable globale.
Maintenant, racine va être une star de noeud.
C'est le sommet de notre Trie que nous sommes va être itérer.
Donc la première chose que nous allons vouloir faire est allouer de la mémoire pour notre racine.
>> Notez que nous utilisons le calloc fonction, qui est essentiellement le même
que la fonction malloc, sauf que c'est garantie de renvoyer quelque chose qui est
complètement remis à zéro.
Donc, si nous avons utilisé Malloc, nous aurions besoin de passer en revue tous les pointeurs dans notre
nœud et assurez-vous que ils sont tous nuls.
Donc calloc le fera pour nous.
>> Maintenant, tout comme Malloc, nous devons faire s'assurer que la répartition est en fait
réussie.
Si cette retourné null, alors nous besoin de fermer notre dictionnaire
déposer et revenir Faux.
Supposant donc l'allocation a été succès, nous allons utiliser un noeud
étoile curseur pour parcourir grâce à notre Trie.
Donc, notre racine ne va jamais changer, mais nous allons utiliser le curseur à
effectivement aller de noeud à noeud.
>> Très bien, alors dans ce boucle For, nous sommes la lecture à travers le fichier de dictionnaire,
et nous utilisons à fgetc.
Donc fgetc va prendre un seul caractère du fichier.
Nous allons continuer à saisir caractères alors que nous ne parvenons pas à la
fin du fichier, donc il ya deux cas, nous devons gérer.
La première, si le caractère n'est pas un nouvelle ligne, afin que nous sachions s'il s'agissait d'un nouveau
ligne, alors nous sommes sur le point de passer à un nouveau mot.
Mais à supposer que ce n'était pas une nouvelle ligne, puis ici, nous voulons comprendre la
indice que nous allons à l'index dans dans le tableau des enfants qui
nous avons regardé avant.
>> Donc, comme je l'ai dit avant, nous devons cas particulier de l'apostrophe.
Notez que nous utilisons l'opérateur ternaire ici, nous allons lire
ce comme si le personnage était lisons-nous dans une apostrophe, alors nous allons
définir indice égal à alphabet moins 1, qui sera l'index 26.
Sinon, si ce n'était pas une apostrophe, alors nous allons définir l'index
égale à c moins un.
Alors, n'oubliez pas de retour de p ensembles précédents, c moins un va nous le donner
la position alphabétique de c, si c est la lettre A, cette volonté
nous donner l'indice zéro.
Par la lettre B, cela donnerait nous l'index 1, et ainsi de suite.
>> Cela nous donne l'index dans le Enfants tableau que nous voulons.
Maintenant, si cet indice est actuellement nulle dans la matrice des enfants, ce qui signifie que
n'existe pas actuellement un nœud de ce chemin, nous avons donc besoin d'allouer une
noeud pour cette voie.
C'est ce que nous faisons ici.
Nous allons donc, encore une fois, utiliser le calloc fonction de sorte que nous n'avons pas
mettre à zéro tous les pointeurs, et nous, nouveau, besoin de vérifier que calloc
n'ont pas manqué.
Si calloc n'at-il pas, alors nous devons pour décharger tout, fermer notre
dictionnaire, et retourner False.
>> Donc, en supposant qu'il n'a pas manqué, alors cela va créer un nouvel enfant pour nous,
puis nous irons à l'enfant.
Notre curseur va parcourir jusqu'à ce que l'enfant.
Maintenant, si ce n'était pas nul pour commencer, alors le curseur peut seulement parcourir
jusqu'à ce que l'enfant sans réellement avoir à allouer rien.
C'est le cas où nous avons d'abord arrivé d'attribuer le mot chat, et
Cela signifie que lorsque nous allons à allouer catastrophe, nous n'avons pas besoin de créer
noeuds pour C-A-T nouveau.
Ils existent déjà.
>> OK, alors qu'est-ce autre chose?
C'est la condition où c était barre oblique inverse n, c était une nouvelle ligne.
Cela signifie que nous avons réussi à complété un mot.
Maintenant, que voulons-nous faire quand nous terminé avec succès un mot?
Nous allons utiliser ce champ de texte à l'intérieur de notre noeud de structure.
>> Nous voulons mettre que de vrai, de sorte que indique que ce noeud indique un
mot succès un mot réel.
Maintenant, définir cette valeur True.
Nous voulons rétablir notre curseur sur le point au début de la Trie nouveau.
Et enfin, augmenter notre dictionnaire taille car nous avons trouvé un autre mot.
>> Très bien, nous allons donc continuer à faire que, à la lecture caractère par
caractère, la construction de nouveaux nœuds dans notre Trie et pour chaque mot dans le
dictionnaire, jusqu'à ce que nous atteignons finalement c est égal à EOF, dans ce cas, nous rompons
hors de l'image.
Maintenant, il ya deux cas sous que nous aurions pu frapper EOF.
La première est de savoir si il y avait une erreur la lecture du fichier, si il y avait
une erreur, nous devons faire le type décharger tout, fermez le fichier,
retourner False.
En supposant qu'il n'y a pas d'erreur, que signifie simplement que nous effectivement touché la fin de
le fichier, dans ce cas, nous fermons l' déposer et revenir vrai puisque nous
chargé avec succès le dictionnaire dans notre Trie.
>> Très bien, alors maintenant nous allons Départ Arrivée.
En regardant la fonction de contrôle, nous voyons Vérifier que va revenir un Bool.
Il retourne True si ce mot que c'est étant passé est dans notre Trie.
Elle renvoie Faux sinon.
>> Alors, comment allons-nous déterminer si ce mot est dans notre Trie?
Nous voyons ici que, comme avant, nous allons utiliser le curseur pour parcourir
grâce à notre Trie.
Maintenant, ici, nous allons parcourir sur l'ensemble de notre parole.
Donc itération sur le mot que nous sommes passé, nous allons déterminer la
index dans le tableau que les enfants correspond à mot i support.
Donc, cela va ressembler exactement Charge, où si le mot support i est un
apostrophe, alors nous voulons utiliser l'index alphabet moins 1 car nous avons déterminé
c'est là que nous allons pour stocker des apostrophes.
>> Sinon nous allons utiliser tolower mot support i.
Alors, n'oubliez pas que ce mot peut avoir arbitraire capitalisation, et nous
voulez vous assurer que nous utilisons une version en minuscules des choses.
Et puis soustraire de ce minuscule une, encore une fois, nous le donner
la position alphabétique de ce personnage.
Alors que va être notre index dans le tableau enfants.
>> Et maintenant, si cet indice dans les enfants tableau est nulle, cela signifie que nous
ne peut plus continuer itération en bas de notre Trie.
Si c'est le cas, ce mot ne peut pas éventuellement dans notre Trie, car si elle
ont été, cela voudrait dire qu'il y aurait une chemin vers le bas à ce mot, et vous le feriez
jamais rencontrer nulle.
Donc rencontrer nulle, nous revenons Faux.
Le mot n'est pas dans le dictionnaire.
Si ce n'était pas nul, alors nous allons poursuivre l'itération, nous allons
mettre à jour notre curseur pour pointer vers qui noeud particulier à cet index.
>> Donc, nous continuons à faire ce que tout au long de le mot entier.
En supposant que nous n'avons jamais touché nulle, que des moyens nous avons réussi à passer à travers l'ensemble du
monde et de trouver un noeud dans notre Trie, mais nous ne sommes pas encore tout à fait terminé.
Nous ne voulons pas simplement renvoyer True.
Nous voulons retourner curseur mot d'erreur car, rappelez-vous de nouveau, si le chat n'est pas
dans notre dictionnaire et la catastrophe est, alors nous allons passer avec succès
le mot chat, mais le mot de curseur seront faux et pas vrai.
Donc, nous revenons mot de curseur pour indiquer si ce nœud est en fait un mot,
et c'est tout pour l'enregistrement.
>> Donc, nous allons vérifier Taille.
Ainsi la Taille va être assez facile car, rappelez-vous en charge, nous sommes
incrémenter taille du dictionnaire pour chaque mot que nous rencontrons.
Ainsi la Taille va juste revenir taille de dictionnaire, et c'est tout.
>> Très bien, alors, enfin, nous avons Unload.
Donc Décharger, nous allons utiliser un fonction récursive pour réellement faire tout
du travail pour nous, de sorte que notre fonction va être appelé délestage.
Quel est Unloader va faire?
Nous voyons ici que la vidange est va itérer sur tous les enfants à
ce nœud particulier, et si l'enfant noeud n'est pas nul, alors nous allons
décharger le nœud enfant.
>> Donc, cela va de façon récursive décharger tous nos enfants.
Une fois que nous sommes sûrs que tous nos enfants ont été déchargés, puis nous
peut nous libérer, afin de décharger soi-même.
Donc, ce sera de manière récursive décharger le Trie ensemble, et puis une fois que c'est
fait, nous ne pouvons retourner vrai.
Décharger ne peut pas échouer, nous sommes juste libérant les choses.
Donc, une fois que nous aurons fini de libérer tout, revenir vrai.
Et c'est tout.
Mon nom est Rob, et ce était [inaudible].