DOUG LLOYD: Donc, en CS50, nous avons couvert un grand nombre de différentes structures de données, droit? Nous avons vu des tableaux, et Linked les listes et les tables de hachage, et tente, piles et files d'attente. On y apprend aussi un peu des arbres et des tas, mais vraiment ces tout simplement finir par être variations sur un thème. Il ya vraiment ces type de quatre idées de base que tout le monde peut se résumer à. Tableaux, listes chaînées, Les tables de hachage, et tente. Et comme je l'ai dit, il y sont des variations sur eux, mais cela est assez de choses pour résumer tout ce que nous allons parler dans cette catégorie en termes de C. Mais comment ces toutes les mesures en place, non? Nous avons parlé des avantages et des inconvénients de chaque dans les vidéos distinctes sur eux, mais il ya beaucoup de chiffres se jeter autour. Il ya beaucoup de général pensées se jeter autour. Essayons et consolider en un seul endroit. Disons peser les avantages contre les inconvénients, et considèrent laquelle structure de données pourrait être le droit des données la structure de votre situation particulière, quel que soit le type de données que vous stockez. Vous n'êtes pas nécessairement toujours besoin de utiliser l'insertion super rapide, la suppression, et recherche d'un trie si vous avez vraiment ne se soucient pas insertion et de suppression trop. Si vous avez juste besoin rapidement aléatoire l'accès, peut-être un tableau est mieux. Alors disons que distiller. Parlons de chacun des quatre grands types de structures de données que nous avons parlé, et voir juste au moment où ils pourraient être bon, et quand ils pourraient ne pas être si bon. Commençons donc avec les tableaux. Donc, l'insertion, que ce genre de mauvais. 

Insertion à la fin d'un tableau est OK, si nous construisons un tableau que nous allons. Mais si nous avons besoin d'insérer éléments dans le milieu, penser à l'insertion Trier, il ya beaucoup de passage à adapter un élément là-dedans. Et donc si nous allons insérer partout, mais la fin d'un tableau, qui est sans doute pas si grand. 

De même, la suppression, à moins que nous sommes la suppression à partir de la fin d'un tableau, est probablement aussi pas si grand, si nous ne voulons pas laisser des espaces vides à, qui habituellement nous ne faisons pas. Nous voulons supprimer un élément, et puis sorte de rendre à nouveau serré. Et donc des éléments de suppression un tableau, aussi pas si grande. 

Lookup, cependant, est grande. Nous avons accès aléatoire, recherche constante de temps. Nous disons seulement sept, et nous allons au tableau relocalisation sept. Nous disons 20, au rendez-vous à tableau réinstallation 20. Nous ne disposons pas d'itérer à travers. Cela est assez bon. 

Les tableaux sont aussi relativement facile à trier. Chaque fois que nous avons parlé d'un tri algorithme, comme la sélection sorte, tri par insertion, bulle tri, de fusion Trier, nous avons toujours utilisé des tableaux de le faire, car les tableaux sont assez faciles à trier, par rapport aux structures de données nous avons vu jusqu'à présent. 

Ils sont aussi relativement faible. Il n'y a pas beaucoup d'espace supplémentaire. Vous venez de mettre de côté exactement autant que vous avez besoin pour stocker vos données, et voilà à peu près tout. Donc, ils sont assez petite et efficace en ce sens. Mais un autre inconvénient, cependant, est qu'ils sont fixés à la taille. Nous devons déclarer exactement comment Nous voulons que notre grand tableau à être, et nous obtenons un seul coup à elle. Nous ne pouvons pas grandir et rétrécir. 

Si nous avons besoin de grandir ou rétrécir, nous besoin de déclarer un tableau tout à fait nouveau, copier tous les éléments de la premier tableau dans la deuxième rangée. Et si nous mal calculé que temps, nous avons besoin de le faire à nouveau. Pas si bien. Donc tableaux ne nous donnent pas la flexibilité d'avoir un nombre variable d'éléments. 

Avec une liste chaînée, insertion est assez facile. Nous louvoyons juste sur le devant. La suppression est également assez facile. Nous devons trouver les éléments. Qui impliquent quelques recherches. 

Mais une fois que vous avez trouvé l'élément vous cherchez, tout ce que vous devez faire est de changer un pointeur, peut-être deux si vous avez un lié films-- un doublement liste chaînée, rather-- et puis vous pouvez simplement libérer le noeud. Vous ne devez pas passer tout autour. Vous venez de changer deux pointeurs, de sorte que est assez rapide. 

Lookup est mauvais, non? Pour que nous puissions trouver une élément dans une liste chaînée, si une ou deux fois lié, nous devons linéaire fouiller. Nous devons commencer au début et déplacer la fin, ou commencer à l'initiative de la fin au début. Nous ne avons plus accès aléatoire. Donc, si nous faisons un beaucoup de recherche, peut-être une liste chaînée est pas tout à fait aussi bon pour nous. 

Ils sont également très difficiles à trier, à droite? La seule façon que vous pouvez vraiment trier une liste chaînée est de faire le tri comme vous le construire. Mais si vous triez comme vous construire, vous n'êtes plus des insertions rapides plus. Vous n'êtes pas seulement vireur les choses sur le devant. Vous devez trouver le place juste pour la mettre, puis votre insertion devient à peu près aussi mauvais que l'insertion dans un tableau. Donc, les listes chaînées ne sont pas si grand pour le tri des données. 

Ils sont aussi assez petit, de la taille d'une montre. Doublement liste chaînée légèrement plus grand que les listes simplement liées, qui sont légèrement plus grand que les tableaux, mais il est pas une énorme quantité d'espace perdu. Donc, si l'espace est à une prime, mais pas une prime vraiment intense, ce pourrait être la bonne façon de faire. 

Les tables de hachage. Insertion dans une table de hachage est assez simple. Il est un processus en deux étapes. Premièrement, nous devons exécuter nos données à travers une fonction de hachage pour obtenir un code de hachage, puis on insère l'élément dans le table de hachage des à cet endroit de code de hachage. 

Suppression, semblable à la liste chaînée, est facile une fois que vous trouvez l'élément. Vous devez trouver le premier, mais alors quand vous le supprimez, vous avez juste besoin d'échanger un couple de pointeurs, si vous utilisez le chaînage séparé. Si vous utilisez de sondage, ou si vous n'êtes pas utilisant chaînage du tout dans votre table de hachage, suppression est effectivement très facile. Tout ce que vous devez faire est de hacher la données, puis aller à cet endroit. Et en supposant que vous ne faites pas Pour toute collision, vous serez en mesure de supprimer très rapidement. 

Maintenant, consultation est où les choses obtenir un peu plus compliqué. Il est en moyenne meilleure que les listes chaînées. Si vous utilisez le chaînage, vous avez encore une liste chaînée, ce qui signifie que vous avez toujours la recherche désavantage du une liste chaînée. Mais parce que vous prenez votre liés liste et le diviser plus de 100 ou 1000 ou n éléments dans votre table de hachage, vous êtes listes chaînées sont tous un nième la taille. Ils sont tous sensiblement plus petite. Vous avez n liée listes place d'une liste liée de taille n. 

Et donc ce monde réel constant facteur, que nous avons généralement ne pas parler de la complexité du temps, il ne fait effectivement une différence ici. Donc recherche est toujours linéaire rechercher si vous utilisez le chaînage, mais la longueur de la liste vous êtes à la recherche par le biais est très, très courte en comparaison. Encore une fois, si le tri est votre but ici, la table de hachage probablement pas la bonne voie à suivre. Il suffit d'utiliser un tableau si le tri est vraiment important pour vous. 

Et ils peuvent exécuter toute la gamme de la taille. Il est difficile de dire si une Table hachage est petite ou grande, parce que cela dépend vraiment de la taille de votre table de hachage est. Si vous allez seulement à stocker cinq éléments dans votre table de hachage, et vous avez une table de hachage avec 10.000 éléments en elle, vous êtes probablement perdre beaucoup d'espace. Contraste Vous être peut également avoir des tables de hachage très compactes, mais le plus petit de votre table de hachage obtient, le plus chacune de ces listes chaînées Gets. Et donc il n'y a vraiment aucun moyen de définir exactement de la taille d'une table de hachage, mais il est probablement sûr à-dire il est généralement va être plus grand qu'un liée Liste stocker les mêmes données, mais inférieure à une trie. 

Et tente sont la quatrième de ces structures que nous avons parlé. Insertion dans un trie est complexe. Il ya beaucoup de dynamique allocation de mémoire, en particulier au début, que vous commencez à construire. Mais il est temps constant. Il est seulement l'élément humain ici qui le rend délicat. Avoir à rencontrer pointeur NULL, malloc espace, allez-y, l'espace éventuellement malloc à partir de là à nouveau. Le genre de facteur d'intimidation de pointeurs dans allocation dynamique de mémoire est l'obstacle à franchir. Mais une fois que vous avez terminé il, insertion vient en fait assez simple, et il est certainement temps constant. 

La suppression est facile. Tout ce que vous devez faire est de descendre d'un couple de pointeurs et gratuitement le noeud, de sorte que est assez bon. Lookup est également assez rapide. Il est seulement basé sur la longueur de vos données. Donc, si toutes vos données est cinq chaînes de caractères, par exemple, que vous stockez de cinq chaînes de caractères dans votre trie, il ne faut que cinq étapes à trouver ce que vous cherchez. Cinq est juste un facteur constant, de sorte de plus, l'insertion, la suppression et recherche Voici les temps constant, efficace. 

Une autre chose est que votre Trie est fait assez déjà trié, non? En vertu de la façon dont nous sommes insérer des éléments, par lettre allant par lettre du clé, chiffre par chiffre ou de la clé, habituellement, votre trie finit par être sorte de tri que vous construisez. Il n'a pas fait vraiment sens de penser sur le tri de la même manière que nous pensons à propos avec des tableaux ou des listes liées, ou tables de hachage. Mais dans un certain sens, votre Trie est triée comme vous allez. 

L'inconvénient, bien sûr, est que un trie devient rapidement énorme. De tous les points de jonction, vous pourriez have-- si votre clé est constitué de chiffres, vous avez 10 autres endroits où vous pouvez aller, qui signifie que chaque nœud contient des informations sur les données que vous souhaitez stocker à ce noeud, plus 10 pointeurs. Qui, sur CS50 IDE, est de 80 octets. Donc, il est au moins 80 octets pour chaque nœud que vous créez, et cela est même pas des données de comptage. Et si vos nœuds sont lettres au lieu de chiffres, maintenant vous avez 26 pointeurs de chaque emplacement. Et 26 fois 8 est probablement 200 octets, ou quelque chose comme ça. Et vous avez des capitaux et vous peut lowercase-- voir où je vais avec cela, non? Vos nœuds peuvent être vraiment grande, et donc le trie lui-même, dans l'ensemble, peut devenir vraiment grand, trop. Donc, si l'espace est à un niveau élevé prime sur votre système, un trie pourrait ne pas être la bonne façon de aller, même si ses autres avantages entrer en jeu. Je suis Doug Lloyd. Ceci est CS50.