KEVIN SCHMID: Parfois, lors de la construction d'un programme, vous voudrez peut-être utiliser un structure de données appelée un dictionnaire. A Plans Dictionnaire touches, qui sont généralement des chaînes, des valeurs, ints, caractères, un pointeur vers un objet, ce que nous voulons. C'est comme les dictionnaires ordinaires que la carte par le biais de mots définitions. 

Dictionnaires nous donnent l' capacité à stocker des informations associé à quelque chose et le regarder plus tard. Alors, comment pouvons-nous mettre en oeuvre effectivement un dictionnaire, disons, le code C que nous pouvons utiliser dans un de nos programmes? Eh bien, il ya beaucoup de façons que nous pourrions mettre en œuvre un dictionnaire. 

D'une part, nous pourrions utiliser un tableau qui nous redimensionner dynamiquement ou nous pourrions utiliser une liste chaînée, table de hachage ou d'un arbre binaire. Mais ce que nous choisissons, nous devrions être conscient de l'efficacité et le rendement de la mise en œuvre. Nous devrions penser à l'algorithme utilisé à insérer et rechercher des éléments dans notre structure de données. 

Pour l'instant, supposons que nous vouloir utiliser des chaînes comme clés. Parlons une possibilité, une structure de données appelée un trie. Alors, voici une représentation visuelle d'une structure arborescente. 

Comme l'image l'indique, un trie est une structure de données d'arbre avec noeuds reliés entre eux. Nous voyons qu'il ya clairement une racine noeud avec quelques liens s'étendant à d'autres noeuds. Mais qu'est-ce que chaque nœud consiste? Si nous supposons que nous sommes le stockage de clés avec seulement des caractères alphabétiques, et nous ne nous soucions pas de la capitalisation, voici une définition d'un noeud suffira. 

Un objet dont le type est struct noeud comporte deux parties appelé données et des enfants. Nous avons laissé la partie de données comme un commentaire pour être remplacé par un composant déclaration lorsque le noeud de structure est incorporé dans un programme C. La partie de données d'un nœud peut être un Valeur booléenne pour indiquer si pas le nœud représente l'achèvement d'une clé de dictionnaire ou il pourrait être un chaîne représentant la définition d'un mot dans le dictionnaire. 

Nous utiliserons un visage souriant pour indiquer lorsque des données sont présentes dans un noeud. Il ya 26 éléments dans notre tableau pour enfants, un indice par caractère alphabétique. Nous verrons l'importance de cette bientôt. 

Soyons un peu plus près du noeud racine dans notre schéma, qui n'a pas de données qui lui est associée, comme indiqué par l' absence du visage souriant dans la partie de données. Les flèches s'étendant à partir des parties d' les enfants représentent matrice non-noeud des pointeurs vers d'autres noeuds. Par exemple, la flèche s'étendant à partir de le deuxième élément d'enfants représente la lettre B dans un dictionnaire clé. Et dans le diagramme plus grande nous marquer avec un B. 

On notera que dans le diagramme plus grande, lorsque nous tirer un pointeur vers un autre nœud, il n'a pas d'importance où la flèche répond l'autre nœud. Notre échantillon dictionnaire trie contient deux mots, que et zoom. Passons en revue un exemple de la recherche de données d'une clé. 

Supposons que nous voulions voir le La valeur correspondante pour le bain clé. Nous allons commencer notre regard vers le haut au niveau du noeud de racine. Ensuite, nous allons prendre la première lettre de notre clé, B, et trouver le correspondant repérer dans notre tableau des enfants. Notez qu'il ya exactement 26 points dans le tableau, une pour chaque lettre de l'alphabet. Et nous aurons les points représentent la lettres de l'alphabet dans l'ordre. 

Nous allons examiner le second indice alors, une indice, par B. D'une manière générale, si l'on avoir un caractère alphabétique C nous pourrait déterminer l'endroit correspondant dans le tableau en utilisant les enfants un calcul de ce genre. Nous aurions pu utiliser un plus grand enfants tableau si nous voulions offrir regard d' touches avec un large éventail de personnages, tel que l'ensemble de Jeu de caractères ASCII. 

Dans ce cas, le pointeur dans notre tableau les enfants à index-ci n'est pas nulle. Nous continuerons donc à la recherche le bain de clé. Si jamais nous avons rencontré un pointeur null au bon endroit chez les enfants tableau tandis que nous traversions les nœuds, alors nous devons dire que nous ne pouvait pas trouver quelque chose pour cette clé. 

Maintenant, nous allons prendre la seconde lettre de notre clé, A, et continuer à suivre pointeurs de cette façon jusqu'à ce que nous arriver à la fin de notre clé. Si nous arrivons à la fin de la clé sans heurter les impasses, les pointeurs NULL, comme c'est le cas ici, alors nous ne avoir à vérifier une chose. Est-ce réellement la clé dans le dictionnaire? 

Si c'est le cas, nous devrions trouver une valeur, ainsi un smiley icône de visage dans notre schéma où le mot se termine. Si il ya quelque chose d'autre stockée avec les données, alors nous pouvons retourner. Par exemple, le zoo clé n'est pas dans la dictionnaire, même si nous aurions pu atteint la fin de cette touche, sans jamais frapper un pointeur NULL, alors que nous parcourir la trie. 

Si nous avons essayé de voir la salle de bain clé, la deuxième à l'indice de tableau de dernier nœud, correspondant à la lettre H, serait ont tenu un pointeur NULL. Ainsi, le bain n'est pas dans le dictionnaire. Et si un trie est unique en ce que les touches ne sont jamais explicitement stockés dans la structure de données. Alors, comment pouvons-nous insérer quelque chose dans un trie? 

Insérons la touche zoo dans notre trie. Rappelez-vous que un visage souriant à un noeud pourrait correspondre dans le code à une simple Valeur booléenne pour indiquer que zoo est dans le dictionnaire ou il pourrait correspondent à plus d'informations que nous souhaitez associer à la touche zoo, comme la définition de l' mot ou quelque chose d'autre. À certains égards, le processus pour insérer quelque chose dans un trie est similaire à regardant quelque chose dans un trie. 

Nous allons commencer avec le nœud racine de nouveau, pointeurs suivants correspondant à les lettres de notre clé. Heureusement, nous avons pu suivre les pointeurs tout le chemin jusqu'à ce que nous ayons atteint l'extrémité de la clé. Depuis zoo est un préfixe du mot zoom, qui est un membre de l' dictionnaire, nous n'avons pas besoin de allouer de nouveaux nœuds. 

Nous pouvons modifier le nœud pour indiquer que le chemin de personnages principaux à il représente un élément clé dans notre dictionnaire. Maintenant, nous allons essayer d'insérer le BAIN clé dans la structure arborescente. Nous allons commencer à le nœud racine et suivre à nouveau les pointeurs. Mais dans cette situation, nous avons touché un mort fin avant que nous soyons en mesure d'obtenir à l' extrémité de la clé. Maintenant, nous avons besoin d'allouer une nouvelle nœuds devront allouer un nouveau pour chaque nœud restant lettre de notre clé. 

Dans ce cas, nous avons juste besoin d'allouer un nouveau nœud. Ensuite, nous devons faire l'indice de H référence à ce nouveau nœud. Une fois de plus, nous pouvons modifier le nœud de indiquer que la trajectoire de caractères menant à elle représente un clé dans notre dictionnaire. Disons raisonner sur l'asymptotique complexité de nos procédures pour les deux opérations. 

Nous remarquons que dans les deux cas, le nombre des étapes de notre algorithme a pris a été proportionnel au nombre de lettres dans le mot-clé. C'est vrai. Si vous souhaitez rechercher un mot dans un trie vous suffit pour parcourir les lettres une par une jusqu'à ce que vous arriver à la fin du mot ou dans une impasse dans le trie. 

Et lorsque vous souhaitez insérer une clé valeur paire dans un trie à l'aide du procédure, nous avons discuté, le pire des cas vous fera l'attribution d'un nouveau noeud pour chaque lettre. Et nous supposons que la répartition est une constante de temps de fonctionnement. Donc, si nous supposons que la longueur de la clé est délimitée par une constante fixe, à la fois insertion et voir sont constants opérations de temps pour un trie. 

Si nous ne faisons pas cette hypothèse que la longueur de la clé est délimitée par une partie fixe constante, insertion et regarder en haut, dans le pire des cas, sont linéaires dans la longueur de la clé. Notez que le nombre d'éléments stockés dans le trie ne pas affecter l'apparence des ou le temps d'insertion. Il est seulement affecté par la longueur de la clé. 

En revanche, l'ajout d'entrées à, disons, une table de hachage tend à faire perspectives d'avenir plus lentement. Même si cela peut paraître séduisante au premier abord, nous devrions garder à l'esprit que complexité asymptotique favorable ne dire que dans la pratique les données structure est nécessairement au-delà de tout reproche. Nous devons aussi considérer que pour stocker une mot dans un trie, nous devons, dans le pire des cas, un certain nombre de noeuds proportionnel à la longueur du mot lui-même. 

Essais ont tendance à utiliser beaucoup d'espace. C'est en revanche à une table de hachage, où nous avons seulement besoin d'un nouveau nœud à stocker des paires de valeur de la clé. Maintenant, toujours en théorie, un grand espace la consommation ne semble pas être un grand traiter, d'autant plus que moderne ordinateurs ont gigaoctets et gigaoctets de mémoire. Mais il s'avère que nous avons encore à vous soucier de l'utilisation de la mémoire et organisation pour le bien de performance, puisque les ordinateurs modernes avoir des mécanismes en place dans le cadre du capot pour accélérer l'accès mémoire. 

Mais ces mécanismes fonctionnent mieux lorsque accès à la mémoire sont expédiées dans les compact régions ou zones. Et les noeuds d'un trie pourraient résider n'importe où dans ce tas. Mais ce sont des compromis que nous devons considérer. 

Rappelez-vous que, lorsque vous choisissez une des données la structure pour une certaine tâche, nous devraient penser à ce genre de opérations de la structure de données doit support et quel rendement de chacun de ces opérations des questions à nous. Ces opérations peuvent même étendre au-delà de base regard et l'insertion. Supposons que nous voulions mettre en place une sorte de la fonctionnalité de saisie semi-automatique, beaucoup comme moteur de recherche Google ne. C'est, retournez toutes les clés et potentiellement valeurs qui avoir un préfixe donné. 

Un trie est particulièrement utile pour cette opération. C'est simple pour parcourir le trie pour chaque caractère de le préfixe. Tout comme une opération rechercher, nous pourrions suivre des pointeurs caractère par caractère. Puis, quand nous arrivons à la fin de la préfixe, nous pourrions parcourir la la partie restante de la structure de données étant donné que l'une des touches au-delà de ce point ont le préfixe. 

Il est également facile d'obtenir cette annonce dans l'ordre alphabétique depuis le éléments de la matrice pour enfants sont classées par ordre alphabétique. Donc, j'espère que vous envisagerez dons tente un essai. Je suis Kevin Schmid, et c'est CS50. 

Ah, c'est le début de la baisse. Je suis désolé. Désolé. Désolé. Désolé. 

Frappez quatre. Je suis sorti. Désolé. Désolé. Désolé. Désolé pour la fabrication de la personne qui doit modifier ce fou. 

Désolé. Désolé. Désolé. Désolé. 

INTERLOCUTEUR 1: Bravo. Cela a été très bien fait.