[MUSIQUE JEU] 

ROB BOWDEN: Salut. Je suis Rob. Et de laisser cette solution sur. Donc, ici, nous allons mettre en œuvre un tableau général. Nous voyons que le noeud de structure de notre table va ressembler à ceci. Donc ça va avoir un mot char tableau de taille LONGUEUR + 1. Ne pas oublier le + 1, puisque le maximum mot dans le dictionnaire est de 45 caractères. Et puis nous allons avoir besoin d'un supplément caractère pour le zéro de barre oblique inverse. 

Et puis notre table de hachage dans chaque seau va stocker une liste chaînée de noeuds. Nous ne faisons pas linéaire sondage ici. Et afin de relier à l'autre élément dans le seau, nous avons besoin d'une noeud de struct * prochaine. OK. C'est ce que un nœud ressemble. 

Maintenant, voici la déclaration de notre table de hachage. Il va avoir 16 834 seaux. Mais ce nombre n'a pas vraiment d'importance. Et enfin, nous allons avoir l' taille de la table de hachage variable globale, qui va commencer à zéro. Et il va garder une trace de la façon dont beaucoup de mots sont dans notre dictionnaire. 

Donc, nous allons jeter un oeil à charge. Notez que la charge, elle retourne un bool. Vous revenez vrai si c'était avec succès chargé, et faux sinon. Et il prend un char * const dictionnaire, qui est le dictionnaire que nous voulons ouvrir. Donc, c'est la première chose nous allons faire. 

Nous allons fopen l' dictionnaire pour la lecture. Et nous allons avoir à faire vous que c'est réussi. Donc, si il est retourné NULL, alors nous n'avons pas réussir à ouvrir le dictionnaire. Et nous devons retourner false. Mais en supposant qu'il a fait avec succès ouvert, alors que nous voulons lire le dictionnaire. Donc tourne en boucle jusqu'à ce qu'on trouve une certaine raison de sortir de cette boucle, que nous allons voir. Donc, tourne en boucle. 

Et maintenant, nous allons malloc un seul nœud. Et bien sûr, nous avons besoin pour aérer vérifier de nouveau. Donc, si allouer de ne pas réussir, alors nous voulons décharger un nœud que nous arrivé à malloc avant, fermer la dictionnaire et retourner false. Mais en ignorant que, en supposant que nous réussi, alors nous voulons utiliser fscanf de lire un seul mot de notre par dictionnaire dans notre nœud. Alors, n'oubliez pas que l'entrée> mot est l'omble mot tampon de taille Lenghth + 1 que nous allons stocker le mot po 

Donc fscanf va revenir 1, aussi longtemps comme il a pu avec succès lire un mot à partir du fichier. Si une erreur se produit, soit, ou nous atteindre la fin du fichier, il ne reviendra pas 1. Dans ce cas, il ne revient pas 1, nous allons enfin sortir de cette boucle while. Ainsi, nous voyons qu'une fois que nous avons réussi à lire un mot en entrée> mot, puis nous allons à cette mot en utilisant notre fonction de hachage. 

Jetons un coup d'œil à la fonction de hachage. Donc, vous n'avez pas vraiment besoin pour comprendre cela. Et en fait, nous sommes arrivés juste ce hachage fonctionner à partir d'Internet. La seule chose que vous devez reconnaître, c'est que cela prend un char * mot const. Il s'agit donc de prendre une chaîne en entrée, et retour d'un unsigned int en sortie. Donc, c'est tout une fonction de hachage est, est-il prend en entrée et vous donne une index dans la table de hachage. 

Notez que nous n'avons moding par num_buckets, de sorte que la valeur retournée est en fait un index dans la table de hachage et n'indexe pas au-delà de la limites du tableau. Donc, étant donné que la fonction, nous allons pour hacher le mot que nous lisons l' dictionnaire. Et puis nous allons utiliser ce hachage pour insérer le entrée dans la table de hachage. 

Hachage Maintenant table de hachage est le courant liste chaînée dans le tableau. Et il est très possible que c'est juste NULL. Nous voulons insérer notre entrée à l' à partir de cette liste chaînée. Et donc nous allons avoir notre courant le point à ce que la table de hachage d'entrée des points actuellement. Et puis nous allons stocker, dans la table de hachage à l' hachage, l'entrée actuelle. Donc, ces deux lignes insérer avec succès l'entrée au début de l' liste liée à l'index dans la table de hachage. 

Une fois que nous en avons terminé avec cela, nous savons que nous avons trouvé un autre mot dans la dictionnaire, et on incrémente à nouveau. Donc, nous continuons à faire que jusqu'à fscanf enfin de retour quelque chose de non-1 à quel point rappeler que nous devons libérer entrée. Donc, ici nous malloced une entrée. Et nous avons essayé de lire quelque chose du dictionnaire. Et nous n'avons pas lu avec succès quelque chose à partir du dictionnaire, dans auquel cas nous devons libérer l'entrée que nous n'avons jamais mis dans le table de hachage, et enfin briser. 

Une fois que nous échappons, nous devons voir, eh bien, n'avons nous rompons parce qu'il n'y a été une erreur de lecture du fichier? Ou avons-nous rompons parce que nous atteint la fin du fichier? S'il y avait une erreur, nous voulons retourner faux. Parce que la charge n'a pas réussi. Et dans le processus, nous voulons décharger tous les mots que nous lisons dans et fermer le fichier du dictionnaire. 

En supposant que nous avons réussi, alors que nous venons de encore besoin de fermer le dictionnaire déposer, et revenir enfin vrai puisque nous chargé le dictionnaire. Et c'est tout pour la charge. Alors maintenant, vérifier, étant donné une table de hachage chargé, va ressembler à ceci. Afin de vérifier, il retourne un bool, ce qui est va indiquer si le passé en char * mot, si le passé dans la chaîne est dans notre dictionnaire. Donc, si elle est dans le dictionnaire, si c'est dans notre table de hachage, nous reviendrons vrai. Et si ce n'est pas, nous reviendrons faux. 

Étant donné ce passé dans le mot, nous sommes va hacher le mot. Maintenant une chose importante à reconnaître est que la charge que nous savions que tous les mots que nous allons être en minuscules. Mais ici, nous ne sommes pas si sûr. Si nous prenons un coup d'oeil à notre fonction de hachage, notre fonction de hachage fait boîtier inférieur est chaque caractère du mot. Donc, quelle que soit la capitalisation des mot, notre fonction de hachage est le retour le même indice pour quelle que soit la la capitalisation est, comme il aurait retourné pour un tout minuscule version du mot. Très bien. C'est notre indice est dans le Hashtable pour ce mot. 

Or, cette boucle va parcourir la liste chaînée que c'était à cet index. Donc, nous remarquons l'initialisation entrée pour pointer vers cet index. Nous allons continuer tandis que l'entrée! = NULL. Et rappelez-vous que la mise à jour du pointeur dans notre entrée de liste liée = entrée> prochaine. Alors que notre point d'entrée actuel à l'élément suivant dans la liste chaînée. 

Ainsi, pour chaque entrée dans la liste liée, nous allons utiliser strcasecmp. Ce n'est pas StrComp. Car encore une fois, nous voulons faire des choses sensible à la casse. Nous utilisons donc strcasecmp de comparer la mot qui a été adoptée par cette fonction contre le mot c'est dans cette entrée. Si elle retourne zéro, cela signifie qu'il a été un match, dans ce cas, nous voulons return true. Nous avons trouvé le succès mot dans notre table de hachage. 

S'il n'y avait pas un match, alors nous sommes aller à boucle encore et regarder la entrée suivante. Et nous allons continuer boucle alors qu'il sont entrées dans cette liste chaînée. Qu'advient-il si nous rompons sortir de cette boucle? Cela signifie que nous n'avons pas trouvé une entrée qui identifié ce mot, dans ce cas, nous retournons false pour indiquer que notre ne contient pas de table de hachage ce mot. Et c'est un chèque. 

Donc, nous allons jeter un oeil à la taille. Maintenant taille va être assez simple. Depuis souvenir en charge, pour chaque mot nous avons trouvé, nous incrémentons un mondial taille de la table de hachage variable. Ainsi, la fonction de la taille va juste pour revenir variable globale. Et c'est tout. 

Maintenant, enfin, nous avons besoin de décharger le dictionnaire une fois que tout est fait. Alors, comment allons-nous faire? Ici, nous sommes en boucle sur tous les godets de notre table. Donc, il ya num_buckets seaux. Et pour chaque liste liée dans notre table de hachage, nous allons faire une boucle sur la totalité de la liste chaînée, libérer chaque élément. 

Maintenant, nous devons être prudents. Nous avons donc ici une variable temporaire C'est stocker le pointeur à l'autre élément dans la liste chaînée. Et puis nous allons à la libre l'élément courant. Nous devons être sûrs que nous faisons depuis que nous avons ne peut pas simplement libérer l'élément courant puis essayer d'accéder au pointeur suivant, car une fois que nous avons libéré il, la mémoire devient invalide. 

Nous devons donc garder autour d'un pointeur vers l'élément suivant, alors nous pouvons libérer l' élément courant, et alors nous pouvons mettre à jour notre élément courant jusqu'au point de l'élément suivant. Nous allons boucle alors qu'il ya des éléments dans cette liste chaînée. Nous le ferons pour tous liés listes dans la table de hachage. Et une fois que nous en avons terminé avec cela, nous avons complètement déchargé la table de hachage, et nous aurons terminé. Il est donc impossible pour le déchargement à jamais retourner false. Et quand nous aurons terminé, nous il suffit de retourner vrai. 

Donnons cette solution un essai. Donc, nous allons jeter un oeil à ce que notre noeud de structure ressemblera. Ici, nous voyons que nous allons avoir un bool mot et un noeud de struct * pour enfants support alphabet. Donc, la première chose que vous seriez peut-être demander, pourquoi est ALPHABET ed définie comme 27? Eh bien, rappelez-vous que nous allons avoir besoin de à la manipulation de l'apostrophe. Donc cela va être un peu un cas particulier tout au long de ce programme. 

Maintenant rappeler comment un trie fonctionne réellement. Disons que nous sommes indexer le mot «chats». Puis à partir de la racine de Trie, nous allons regarder les enfants tableau, et nous allons regarder la indice qui correspond à la lettre C. Alors qui sera indexé 2. Donc, étant donné que, cette volonté nous donner un nouveau nœud. Et 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 étant donné que nous allons noeud à regarder à la fin c'est un correspond T. Et de passer à ce nœud, enfin, nous avons complètement regardé grâce à notre mot «chat». Et maintenant bool mot est censé indiquer si cette parole donnée est en fait un mot. 

Alors pourquoi avons-nous besoin ce cas particulier? Eh bien ce que le mot «catastrophe» est dans notre dictionnaire, mais la mot «chat» n'est pas? Ainsi et afin de voir si le mot "chat" est dans notre dictionnaire, nous sommes va regarder avec succès par les indices C-A-T en noeud de la région. Mais c'est seulement parce que la catastrophe arrivé à créer des nœuds sur le chemin à partir de C-A-T, tout le chemin pour la fin du mot. Donc bool mot est utilisé pour indiquer si cet endroit particulier indique en fait un mot. 

Très bien. Alors, maintenant que nous savons ce qu'il trie est va ressembler, regardons l' charger la fonction. Donc, la charge va revenir un bool pour que nous succès ou en vain chargé le dictionnaire. Et ce sera le dictionnaire que nous voulons charger. 

Donc la première chose que nous sommes à faire est d'ouvrir jusqu'à ce dictionnaire pour la lecture. Et nous devons faire en sorte nous n'avons pas manqué. Donc, si le dictionnaire n'a pas été ouvert avec succès, il sera de retour null, auquel cas nous sommes va 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 un 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 d'allouer 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 noeud, et assurez-vous que ils sont tous nuls. Donc calloc le fera pour nous. 

Maintenant comme malloc, nous devons faire s'assurer que la répartition était effectivement réussie. Si cette retourné null, alors nous besoin de fermer ou de dictionnaire déposer et retourner false. Supposant donc que l'allocation a été succès, nous allons utiliser un noeud * curseur pour parcourir notre trie. Ainsi, nos racines ne changera jamais, mais nous allons utiliser le curseur à effectivement aller de noeud à noeud. 

Ainsi, dans cette boucle que nous lisons dans le fichier de dictionnaire. Et nous utilisons fgetc. 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. 

Il ya deux cas, nous devons gérer. La première, si le caractère n'était pas une nouvelle ligne. Nous savons donc s'il s'agissait d'une nouvelle ligne, puis 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 enfants nous avons regardé avant. 

Donc, comme je l'ai dit avant, nous devons cas particulier de l'apostrophe. Notez que nous utilisons le ternaire opérateur ici. Nous allons donc lire ce que, si le caractère que nous lisons dans était un apostrophe, alors nous allons mettre en index = "alphabet" -1, ce qui sera être l'indice 26. 

Sinon, si ce n'était pas une apostrophe, il nous allons définir l'index égale à c - a. Alors, n'oubliez pas de retour de précédemment p-ensembles, c - une va nous le donner la position alphabétique de C. Donc, si C est la lettre A, ce sera nous donner l'indice zéro. Pour la lettre B, il donnera nous l'index 1, et ainsi de suite. 

Cela nous donne l'index dans le enfants ensemble que nous voulons. Maintenant, si cet indice est actuellement nulle dans les enfants, ce qui signifie que le nœud n'existe pas actuellement à partir de cette voie. Nous avons donc besoin d'allouer un noeud de ce chemin. C'est ce que nous allons faire ici. 

Donc, nous allons à nouveau utiliser le calloc fonction, de sorte que nous n'avons pas à zéro sur tous les pointeurs. Et nous avons encore besoin de vérifier que calloc n'a 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. Et 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é allouer 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à. 

Quel est ce monde? 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. Ainsi, cela indique que ce noeud indique un succès mot, un mot réel. 

Réglez maintenant que de vrai. Nous voulons rétablir notre curseur sur le point au début de la trie à nouveau. Et enfin, augmenter notre dictionnaire taille, puisque nous avons trouvé un autre travail. Donc, nous allons continuer à le faire, 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 arrivons enfin C! = EOF, dans lequel cas nous sortir du fichier. 

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. Donc, si il y avait une erreur, nous besoin de faire la typique. Décharger tout, près le fichier, return 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 que nous dictionnaire chargé avec succès dans notre trie. 

Alors maintenant, nous allons vérifier chèque. En regardant la fonction de contrôle, nous voyons que l'enregistrement va revenir un bool. Elle retourne true si ce mot que c'est étant passé est dans notre trie. Il retourne false sinon. Alors, comment allez-vous 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. 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 des enfants correspond à mot support I. Donc, ce va ressembler exactement charge, où si le mot [i] est une apostrophe, alors nous voulons à utiliser l'index "alphabet" - 1. Parce que nous avons déterminé que ce C'est là que nous allons stocker apostrophes. 

Sinon nous allons utiliser deux mots inférieure support I. Alors, n'oubliez pas que ce mot peut ont capitalisation arbitraire. Et si nous voulons nous assurer que nous sommes en utilisant une version en minuscules des choses. Et puis soustraire de ce «a» à la fois nous redonner la alphabétique la position de ce caractère. Alors que va être notre index dans le tableau des 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. Etant donné que s'il s'agissait d', qui serait cela signifie qu'il y aurait un trajet jusqu'à ce mot. Et vous ne rencontrerez jamais nulle. Donc rencontrer nulle, nous revenons faux. Le mot n'est pas dans le dictionnaire. Si ce n'était pas nulle, alors nous sommes va continuer itération. 

Donc, nous allons là-bas curseur au point à ce particulier nœud à l'index. Nous continuons à faire que tout au long le mot entier, en supposant nous n'avons jamais touché nulle. Cela signifie que nous avons pu passer à travers le mot entier et de trouver un noeud dans notre essai. Mais nous ne sommes pas encore tout à fait terminé. 

Nous ne voulons pas simplement retourner vrai. Nous voulons retourner curseur> mot. Depuis n'oubliez pas nouveau, est «chat» n'est pas dans notre dictionnaire, et "catastrophe" est, alors nous réussirons à nous obtenons par le mot "chat". Mais curseur mot sera 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 la taille. Donc, la taille va être assez facile car, rappelez-vous en charge, nous sommes incrémenter taille du dictionnaire pour chaque mot que nous rencontrons. Donc, la taille va juste retourner la taille du dictionnaire. Et c'est tout. 

Donc, nous avons enfin décharger. Donc, décharger, nous allons utiliser une fonction récursive pour réellement faire tout du travail pour nous. Donc notre fonction va être appelé sur déchargeur. Quel est déchargeur va faire? Nous voyons ici que déchargeur va itérer sur tous les enfants à ce nœud particulier. Et si le nœud de l'enfant n'est pas nul, alors nous allons décharger le nœud enfant. 

Donc, c'est vous déchargez de manière récursive 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, de sorte nous décharger. Cela fonctionnera de manière récursive décharger la totalité de trie. Et puis une fois que c'est fait, nous ne pouvons retourner true. Décharger ne peut pas échouer. Nous sommes en train de libérer des choses. Donc, une fois que nous aurons fini de libérer tout, retourne true. Et c'est tout. Mon nom est Rob. Et ce fut correcteur orthographique. 

[MUSIQUE JEU]