[Lecture de musique] DAVID Malan: Ceci est CS50. Et cela est à la fois le début et la end-- comme literally-- presque la fin de la sixième semaine. 

Je pensais que je partagerais un peu d'un fait amusant. Je l'ai tiré ce à partir d'un Les données de semestre passé fixés. Vous vous souviendrez que nous vous demandons à chaque p forme de jeu si vous avez regardé en ligne ou si vous avez assisté en personne. Et voici les données. Donc, aujourd'hui, était très prévisible. Mais nous voulions passer un peu de temps avec vous même. Quelqu'un voudrait-il conjecturer pourquoi cette graphique est tellement dentelée, haut bas, haut bas, de manière aussi systématique? Qu'est-ce que chacun des pics et les creux représentent? 

PUBLIC: [Inaudible] DAVID Malan: En effet. Et plus amusante, à Dieu ne plaise, nous détenons une conférence le vendredi au début du semestre, Voilà ce que nous voyons se produire. Donc, aujourd'hui, nous participons à un peu plus sur des structures de données. Et pour vous donner plus d'un solide modèle mental de problèmes à cinq, qui vient de sortir. Fautes d'orthographe, dans laquelle, nous allons vous remettre un fichier texte quelque 100.000 plus de mots anglais, et vous allez avoir de comprendre comment charger habilement les dans la mémoire, dans la mémoire vive, en utilisant des données la structure de votre choix. 

Maintenant une telle structure de données pourrait être, mais ne devrait probablement pas être, la liste chaînée assez simpliste, laquelle nous avons introduit la dernière fois. Et une liste chaînée avait au moins un avantage sur un tableau. Qu'est-ce un avantage de une liste chaînée sans doute? 

PUBLIC: Insertion. 

DAVID Malan: Insertion. Que voulez-vous dire par là? 

Public: tout le long la liste [inaudible]. 

DAVID Malan: Bon. Ainsi, vous pouvez insérer un élément où vous voulez dans le milieu de la liste sans avoir à mélanger tout, lequel nous avons conclu, dans notre tri discussions, est pas nécessairement une bonne chose, car il faut du temps pour se déplacer réellement tous ces humains gauche ou la droite. Et avec une liste chaînée, vous pouvez juste allouer avec malloc, un nouveau noeud, et ensuite mettre à jour un couple de pointers-- deux, trois opérations max-- et nous sommes en mesure de fente quelqu'un dans n'importe où dans une liste. 

Qu'y avait avantageux sur une liste chaînée? Ouais? 

PUBLIC: [Inaudible] DAVID Malan: Parfait. Parfait. Il est vraiment dynamique. Et que vous n'êtes pas commettre, à l'avance, dans une certaine taille fixe bloc de mémoire, comme vous auriez à avec un tableau, la hausse de qui est que vous pouvez allouer nœuds seulement sur demande l'aide ainsi que la quantité de l'espace que vous avez réellement besoin. Contrairement à un tableau, vous pourriez allouer accidentellement trop peu. Et puis il va juste être une douleur dans le cou de réaffecter un nouveau grand tableau, copier tout sur, libérer l'ancien tableau, et de passer ensuite sur votre entreprise. Ou pire, vous pourriez allouer façon plus de mémoire que vous avez réellement besoin, et si vous allez avoir une très tableau peu peuplée, pour ainsi dire. 

Ainsi, une liste chaînée vous donne ces avantages de dynamisme et de flexibilité avec des insertions et des suppressions. Mais sûrement il doit y avoir un prix à payer. En fait, l'un des thèmes exploré sur questionnaire zéro était un couple de compromis nous avons vu jusqu'à présent. Alors, quel est le prix à payer ou une la baisse d'une liste chaînée? Ouais. 

PUBLIC: Pas d'accès aléatoire. 

DAVID Malan: Pas d'accès aléatoire. Mais qui se soucie? Accès aléatoire ne semble pas convaincante. 

PUBLIC: [Inaudible] DAVID Malan: Exactement. Si vous voulez avoir un certain algorithm-- et permettez-moi de réellement propose recherche binaire en particulier, qui est un que nous avons utilisé tout un bit-- Si vous ne disposez pas d'accès aléatoire, vous ne pouvez pas faire ce que l'arithmétique simple de trouver comme l'élément central et le saut droit. Vous avez la place pour commencer à la première élément linéaire et rechercher de gauche à droite si vous voulez trouver le milieu ou tout autre élément. 

PUBLIC: Il faut probablement plus de mémoire. 

DAVID Malan: Prend plus de mémoire. Où est ce supplémentaire coût en provenance de la mémoire? 

PUBLIC: [Inaudible] DAVID Malan: Exactement. Dans ce cas là, nous avions une liste chaînée pour les entiers, et pourtant, nous avons doublé la quantité de mémoire nous devons en stockant également ces pointeurs. Maintenant, moins d'un gros problème, vos struct grossissent et vous stockez pas un numéro, mais peut-être un étudiant ou un autre objet. Mais la question reste certainement. Et si un certain nombre des opérations sur les listes chaînées ont été appelés étaient grandes O de linéaire n-. Des choses comme l'insertion ou la recherche ou la suppression dans le cas où un élément se trouvait à la fin de la liste si elle est triée ou non. 

Parfois, vous pourriez avoir de la chance et en les limites inférieures de sorte à ces opérations, pourrait aussi être constante de temps si vous êtes toujours à la recherche du premier élément, par exemple. Mais en fin de compte, nous avons promis pour atteindre le Saint Graal des structures de données, ou certains de ceux-ci d'approximation, à titre de constante de temps. Pouvons-nous trouver des éléments ou ajouter des éléments ou supprimer des éléments d'une liste? Nous verrons assez rapidement. Et il se trouve que l'on des mécanismes que nous sommes va commencer à utiliser aujourd'hui, utilisation annuelle p fixé cinq, est en fait assez familier. Par exemple, si ce groupe est un des ouvrages d'examen, chacun d'entre eux a un étudiant de première Prénom et nom dessus, et je les ramasse de à la fin d'un examen, et ils sont tous assez beaucoup dans un ordre aléatoire, et nous voulons aller sur le tri ces examens de sorte qu'une fois classés il est juste beaucoup plus facile et plus rapide de les restituer à aux étudiants par ordre alphabétique. Quelles seraient vos instincts être pour un tas d'examens de ce genre? 

Eh bien, si vous êtes comme moi, vous peut voir que cela est m, Je vais donc en quelque sorte de mettre cela en, si cela est ma table ou mon étage où Je suis la diffusion de choses out-- ou mon tableau really-- Je pourrais mettre tout le Mme là. Oh. Voici un A. Donc, je pourrais Comme mettre les ici. Oh. Voici un autre R. Je vais à mettre que sur ici. Voici un Z. Voici un autre M. Et Je pourrais commencer à faire des piles de ce genre. Et puis peut-être que je vais en plus tard et une sorte de très nitpicky-ly sorte les piles individuelles. Mais le fait est que je chercherais à l'entrée que je suis solitaire et je voudrais faire quelques calculé décision fondée sur cette entrée. Si elle commence par A, le mettre là-bas. Si elle commence par Z, le mettre sur là, et tout le reste. 

Donc, ceci est une technique qui est généralement connu sous le nom hashing-- H-A-S-H- ce qui signifie en général que la prise entrée et en utilisant cette entrée à calculer une valeur, généralement un numéro, et que nombre est l'indice dans une mémoire récipient, comme un tableau. En d'autres termes, je pourrais avoir une fonction de hachage, comme je le fais dans ma tête, que si je vois quelqu'un est nom qui commence par A, Je vais la carte que à zéro dans ma tête. Et si je vois quelqu'un avec Z, je suis aller à la carte que 25 dans ma tête et puis mettre cela en la dernière pile plus. 

Maintenant, si vous pensez pas mon cerveau mais un programme C, ce qui pourrait numéros vous comptez sur pour atteindre le même résultat? En d'autres termes, si vous avait le caractère ASCII A, comment déterminez-vous ce seau à mettre en? Vous ne voulez probablement pas à mettre dans un seau de 65 ans, qui serait comme là-bas sans raison valable. Où voulez-vous mettre un en termes de sa valeur ASCII? Où voulez-vous faire pour son ASCII valeur à venir avec un seau intelligent à mettre en? 

PUBLIC: Minus A. 

DAVID Malan: Ouais. Donc moins A ou moins spécifiquement 65 si elle est un grand A. Ou 98 si il est un minuscule un. Et si cela nous permettra de très simplement et très arithmétiquement, mettre quelque chose dans un seau comme ça. Donc, il se trouve que nous faisons réellement ce ainsi même avec les jeux-questionnaires. 

Donc, vous pourriez rappeler que vous avez encerclé votre le nom de l'enseignement compatriote sur la couverture. Et les noms du TF ont été organisées dans ces colonnes par ordre alphabétique, Eh bien, croyez-le ou non, quand tout 80 plus de nous se sont réunis l'autre soir au grade, la dernière étape de notre processus de classement est à hacher les quiz dans un grand espace de parole à la [inaudible] et de jeter les quiz de tout le monde exactement dans l'ordre de leur TF de noms sur la couverture, parce que alors il est beaucoup plus facile pour nous à parcourir que l'utilisation linéaire recherche ou une sorte d'intelligence pour un TF de trouver son ou Les quiz de ses élèves. 

Donc cette idée de hachage que vous verrez est très puissant est en fait assez banal et très intuitive, tout comme peut-être diviser et conquête était en semaine zéro. Je avance rapide au hackathon Il ya une couple d'années. Ce fut Zamyla et un couple de d'autres étudiants personnel de vœux comme ils sont entrés. Et nous avons eu tout un tas de pliage tables là-bas avec des étiquettes de nom. Et nous avions les tags de nom organisé avec comme les plus Comme il et ZS là-bas. Et si l'un des facteurs de transcription très habilement écrit ce que les instructions pour la journée. Et dans la semaine 12 du semestre ce tout fait sens et tout le monde parfait savait quoi faire. Mais quand vous avez la file d'attente de la même façon, vous êtes mise en œuvre de la même notion de hachage. Donc, nous allons formaliser un peu. Voici un tableau. Il est établi à un peu large juste pour illustrer, visuellement, que nous pourrions mettre les chaînes dans quelque chose comme ça. Et ce tableau est clairement de la taille 26 au total. Et la chose est appelé tableau arbitrairement. Mais cette interprétation est juste d'un artiste de ce qu'est une table de hachage peut être. 

Ainsi, une table de hachage maintenant va une structure de données de niveau supérieur. A la fin de la journée, nous sommes sur le point de voir que vous peut mettre en œuvre une table de hachage, qui est un peu comme l'enregistrement en ligne à un hackathon un peu comme ce tableau utilisé pour le tri des livres d'examen. Mais une table de hachage est sorte de ce haut niveau concept qui pourrait utiliser un tableau sous le capot de la mettre en œuvre, ou il pourrait utiliser une liste de longueur, ou même peut-être d'autres structures de données. Et maintenant que la prise est theme-- certains de ces ingrédients fondamentaux comme un tableau et ce bâtiment bloquer maintenant d'une liste de longueur et voir ce que nous pouvons construire au-dessus de ceux qui, comme ingrédients dans une recette, ce qui rend de plus en plus résultats finaux intéressantes et utiles. 

Donc, avec la table de hachage nous pourrions mettre en œuvre dans la mémoire imagée comme ça, mais comment peut-il réellement être codé en place? Eh bien, peut-être est que tout simplement cela. Si la capacité en majuscules, est juste certains constant-- par exemple 26, pour 26 lettres de l'alphabet-- Je pourrais appeler ma table de variables, et je pourrais prétendre que je vais mettre étoiles omble là-dedans, ou une chaîne. Donc, il est aussi simple que cela si vous vouloir mettre en place une table de hachage. Et pourtant, cela est vraiment juste un tableau. Mais encore une fois, une table de hachage table est maintenant ce que nous allons appeler un type de données abstrait qui est juste une sorte de superposition conceptuelle sur le dessus de quelque chose de plus terre à terre voudrais maintenant un tableau. 

Maintenant, comment allons-nous sur la résolution de problèmes? Eh bien, plus tôt je eu le luxe d'avoir suffisamment d'espace de table ici de sorte que je pouvais mettre la quiz n'importe où je voulais. Donc, comme on aurait pu aller ici. Zs peuvent aller ici. Mme pourrait aller ici. Et puis je devais un peu d'espace supplémentaire. Mais cela est un peu d'un droit triche maintenant, parce que ce tableau, si je vraiment pensé comme un tableau, est juste va être d'une certaine taille fixe. 

Donc, techniquement, si je tire jusqu'à quiz d'un autre élève et voir, oh, cette personne de nom commence par un A trop, Je veux sorte de l'y mettre. Mais dès que je l'ai mis là, si ce tableau représente en effet un tableau, Je vais être remplaçant ou démolir quiconque quiz de cet élève est. Droit? Si cela est un tableau, une seule chose peut aller à chacune de ces cellules ou d'éléments. Et si je dois genre de à choisir. 

Maintenant, plus tôt je sorte de triché et a fait ceci ou je juste un peu empilés les uns sur les autres. Mais cela ne va pas à voler dans le code. Alors, où puis-je mettre la deuxième élève dont le nom est un si tout ce que je devais est ce l'espace disponible de la table? Et je l'ai utilisé trois fentes et il On dirait qu'il ya quelques autres. Que pourriez-vous faire? PUBLIC: [Inaudible] DAVID Malan: Ouais. Peut-être que nous allons juste garder les choses simples. Droit? Il ne correspond pas où je veux le mettre. Je vais donc le mettre techniquement où un B irait. Maintenant, bien sûr, je commence de me peindre dans un coin. Si je reçois un étudiant dont le nom est en fait B, maintenant B va être déplacé un peu avant, comme cela peut arriver, oui, si cela est un B, maintenant il doit aller ici. 

Et ce très rapidement pourrait devenir problématique, mais il est une technique qui fait est dénommé linéaire de palpage, où vous considérez juste votre tableau à la ligne. Et vous venez de type de sonde ou inspecter chaque élément disponible la recherche d'une place disponible. Et dès que vous trouvez un, vous le déposez là. 

Maintenant, le prix à payer maintenant pour cette solution est quoi? Nous avons un tableau de taille fixe, et quand je insérer des noms en elle, au moins au début, ce qui est le temps d'exécution de l'insertion pour mettre les élèves » quiz dans les bons seaux? Big O de quoi? 

PUBLIC: n. DAVID Malan: je entendu grand O de n. Pas vrai. Mais nous allons démêler pourquoi dans un instant. Que pourrait-il être? 

PUBLIC: [Inaudible] DAVID Malan: Et permettez-moi de le faire visuellement. Supposons donc que ceci est la lettre S. 

PUBLIC: Il est un. DAVID Malan: Il est un. Droit? Ceci est un tableau, qui signifie que nous avons accès aléatoire. Et si nous pensons de cette comme zéro et ce comme 25, et nous nous rendons compte que, oh, voici mon entrée S, Je peux certainement convertir S, un caractère ASCII, pour un nombre correspondant entre zéro et 25 et puis tout de suite mettre où il appartient. 

Mais bien sûr, dès que je reçois à la deuxième personne dont le nom est A ou B ou C finalement, si je l'ai utilisé la sondage linéaire que ma solution, le temps d'exécution de insertion dans le pire des cas qui se passe réellement à se transformer en quoi? Et je ne l'entends ici correctement dès le début. PUBLIC: [Inaudible] DAVID Malan: Donc, il est en effet n fois vous avez un assez grand nombre de données. Ainsi, d'une part, si votre tableau est assez grand et vos données sont assez rares, vous obtenir ce beau temps constant. Mais dès que vous commencez devient de plus en plus d'éléments, et juste statistiquement vous obtenez plus de gens avec la lettre A comme leur nom ou la lettre B, il pourrait potentiellement se transformer en quelque chose de plus linéaire. Donc, pas tout à fait parfait. Ainsi pourrions-nous faire mieux? 

Eh bien, ce qui était notre solution avant lorsque nous voulez avoir plus de dynamisme que quelque chose comme un tableau permis? PUBLIC: [Inaudible] DAVID Malan: Qu'avons-nous introduisons? Ouais. Ainsi, une liste chaînée. Eh bien, voyons ce que la liaison des liste pourrait faire pour nous à la place. Eh bien, je vous propose que nous dessiner l'image comme suit. Maintenant, cela est une autre photo d'un exemple à partir d'un texte différent, en fait, que est fait en utilisant un tableau de taille 31. Et cet auteur simplement décidé de hachage cordes ne repose pas sur les noms de la personne, mais en fonction de leurs dates de naissance. Quel que soit le mois, ils ont pensé si vous êtes né le premier du mois ou le 31 d'un mois, l'auteur sera hachage basé sur cette valeur, de façon à répartir les noms un peu plus que 26 points pourraient permettre. Et peut-être qu'il est un peu plus uniforme que d'aller avec des lettres, parce que bien sûr il ya probablement plus de personnes dans le monde avec des noms que commencer avec un de certainement d'autres lettres de l'alphabet. Alors peut-être cela est un peu plus uniforme, en supposant une distribution uniforme des bébés sur un mois. 

Mais, bien sûr, cela est encore imparfait. Droit? Nous allons avoir des collisions. Plusieurs personnes dans cette structure de données sont encore ayant la même date de naissance au moins vous êtes indépendamment de mois. Mais ce qui a fait l'auteur? Eh bien, il semble que nous ayons un tableau sur le côté gauche tiré verticalement, mais qui est tout simplement l'interprétation d'un artiste. Il n'a pas d'importance quelle direction vous dessiner un tableau, il est toujours un tableau. Quel est ce un tableau de apparemment? 

PUBLIC: liste chaînée. 

DAVID Malan: Ouais. Il semble que ce soit un tableau de liste chaînée. Encore une fois, à ce point de sorte de l'utilisation de ces structures de données maintenant comme ingrédients de plus des solutions intéressantes, vous ne pouvez absolument prendre un fondamental, comme un tableau, et puis prendre quelque chose de plus intéressant comme une liste chaînée et même les combiner dans un même Structure de données plus intéressant. Et en effet, ce serait trop être appelé une table de hachage, de sorte que le tableau est vraiment la table de hachage, mais que la table de hachage a chaînes, pour ainsi dire, qui peut augmenter ou diminuer en fonction de la nombre d'éléments que vous souhaitez insérer. 

Maintenant, en conséquence, ce qui est le temps d'exécution maintenant? Si je veux insérer quelqu'un dont l'anniversaire est le 31 Octobre, Où va-il ou elle? Bien. Tout en bas, où il est dit 31. Et qui est parfait. Ce fut un temps constant. Mais que faire si nous trouvons quelqu'un d'autre dont l'anniversaire est, voyons, Octobre, Novembre 31 Décembre? Où est-il ou elle va aller? Même chose. Deux étapes bien. Voilà constante mais est-ce pas? Bien. Au moment où il est. Mais dans le cas général, plus les gens nous ajouter, probabiliste, nous allons pour obtenir de plus en plus de collisions. 

Maintenant, cela est un peu mieux parce que techniquement, maintenant mes chaînes pourraient être en le pire des cas combien de temps? Si je l'insère n personnes dans cette plus structure de données sophistiqué, n personnes, dans le pire des cas, il va être n. Pourquoi? 

PUBLIC: Parce que si tout le monde a la même date d'anniversaire, ils vont être une seule ligne. DAVID Malan: Parfait. Il pourrait être un peu artificiel, mais vraiment dans le pire des cas, si tout le monde a la même date d'anniversaire, étant donné les entrées que vous avez, vous allez avoir un massivement à longue chaîne. Et oui, vous pourriez appeler un la table de hachage, mais en réalité il est juste une liste massive liée à beaucoup d'espace perdu. Mais, en général, si l'on suppose que au moins les anniversaires sont uniform-- et il est probablement pas. Je fais cela. Mais si nous supposons, pour l'intérêt de la discussion qu'ils sont donc en théorie, si ce est la représentation verticale du tableau, eh bien nous espérons que vous êtes allez obtenir des chaînes qui sont, vous le savez, à peu près la même longueur, où chacun des ceux-ci représente un jour du mois. 

Maintenant, si il ya 31 jours dans le mois, cela signifie que mon temps de marche vraiment est grand O de n plus de 31, qui se sent mieux que linéaire. Mais ce qui était un de nos engagements quelques semaines il ya chaque fois qu'il est venu à exprimer le temps d'exécution d'un algorithme? Il suffit de regarder seulement le terme d'ordre élevé. Droit? 31 est certainement utile. Mais cela est encore grand O de n. Mais l'un des thèmes de problème mis cinq va être à absolument reconnaître que, asymptotiquement, théoriquement cette structure de données est pas mieux que de simplement une liste massive liée. Et en effet, dans le pire des cas, cette table de hachage des pourrait dégénérer en cela. 

Mais dans le monde réel, avec nous, les humains que les propres Mac ou PC ou autre et sont en cours d'exécution monde réel logiciel sur des données du monde réel, l'algorithme allez-vous préférer? Celui qui prend des mesures de fin ou la celui qui prend n divisé par 31 étapes de trouver un morceau de données ou pour rechercher des informations? Je veux dire, absolument les 31 marques une différence dans le monde réel. Il est 31 fois plus rapide. Et nous, les humains sont certainement aller à apprécier cela. 

Donc réaliser la dichotomie il entre en fait parler de choses théoriquement et asymptotiquement qui certainement a une valeur comme nous l'avons vu, mais dans le monde réel, si vous vous souciez de simplement faire la heureux humain pour les entrées générales, vous pourriez très bien vouloir accepter du fait que, oui, cela est linéaire, mais il est 31 fois plus rapide que linéaire pourrait être. Et mieux encore, nous ne devons juste faire quelque chose d'arbitraire comme une date de naissance, nous pourrions passer un peu plus de temps et l'intelligence et de réfléchir à ce que nous pourrions faire, prénom d'une personne et peut-être leur date de naissance de combiner ceux ingrédients pour comprendre quelque chose ce qui est vraiment plus uniforme et moins dentelée, pour ainsi dire que cette image suggère actuellement, il pourrait être. Comment pourrions-nous mettre en œuvre dans votre code? Eh bien, je vous propose que nous juste emprunter une syntaxe que nous avons utilisé une ou deux fois jusqu'à présent. Et je vais définir un noeud, qui à nouveau est un terme générique pour quelques-uns Récipient pour une structure de données. Je vais proposer que une chaîne va là-dedans. Mais nous allons commencer à prendre ceux formation roues de maintenant. 

Plus de librairies CS50 vraiment, sauf si vous voulez à utiliser pour votre finale projet, ce qui est bien, mais maintenant nous allons retirer la rideau et dire qu'il est juste une étoile char. Ainsi, le mot il va être le nom de la personne en question. Et maintenant, je dois un lien ici au noeud suivant de sorte que ceux-ci représentent chacun des noeuds dans la chaîne, éventuellement, d'une liste chaînée. 

Et maintenant, comment puis-je déclare la table de hachage elle-même? Comment dois-je déclarer toute cette structure? Eh bien, vraiment, un peu comme je utilisé un pointeur pour que le premier élément de la liste avant, de même que je peux dire seulement Je dois juste un tas de pointeurs de mettre en œuvre toute cette table de hachage. Je vais avoir un tableau appelé table pour table de hachage. Ça va être la capacité de taille. Voilà combien d'éléments peuvent tenir dans ce. Et chacun de ces éléments dans cette tableau va être une star du nœud. Pourquoi? Eh bien, par cette image, ce que je suis mise en œuvre de la table de hachage comme effectivement au début est juste ce tableau que nous avons tracé verticalement, dont chacun des carrés représente un pointeur. Ce ceux qui ont des barres obliques à travers eux sont tout simplement nulle. Et ceux qui ont flèches allant vers la droite réels sont des pointeurs vers des noeuds réels, ergo le début d'une liste chaînée. 

Donc ici, alors, est de savoir comment nous pourrions mettre en œuvre une table de hachage met en œuvre le chaînage séparé. Maintenant, pouvons-nous faire mieux? Très bien, je promis la dernière fois que nous pourrions atteindre la constante de temps. Et je vous ai donné de genre constante de temps ici, mais alors dit pas vraiment constante de temps, car il est toujours dépendant de la somme nombre d'éléments vous êtes saisie en la structure de données. Mais supposons que nous avons fait cela. Permettez-moi de revenir à l'écran ici. Permettez-moi de ce projet a également ici, clair l'écran, et suppose que je l'ai fait. Supposons que je voulais insérer le nom Daven dans dans ma structure de données. 

Je tiens donc à insérer une chaîne Daven dans la structure de données. Que faire si je ne l'utilise une la table de hachage, mais je l'utilise quelque chose qui est plus arborescente comme un arbre de la famille, où vous avez un peu de racine à la nœuds et les feuilles du haut, puis qui vont vers le bas et vers l'extérieur. Supposons donc que je vouloir insérer Daven de dans ce qui est actuellement une liste vide. Je vais faire ce qui suit: Je suis va créer un noeud dans cette famille arbre-comme la structure de données qui ressemble un peu comme ça, chacun d'entre eux rectangles a, disons, pour le moment 26 éléments en elle. Et chacune des cellules dans ce tableau se passe pour représenter la lettre d'un alphabet. 

Plus précisément, je vais traiter ce est A, puis B, puis C, puis D, celui-ci ici. Donc, cela va effectivement représenter la lettre D. Mais à insérer tous Daven de nom, je dois faire un peu plus. Donc, je vais d'abord hachage, pour ainsi dire. Je vais regarder à la première lettre dans Daven de ce qui est évidemment un D, et je vais allouer un noeud qui ressemble comme this-- un grand rectangle grand suffisante pour répondre à tout l'alphabet. 

Maintenant D est fait. Maintenant A. D-A-V-E-N est le but. Alors maintenant, ce que je vais faire est ce. Dès que je commençais avis D il n'y a pas là pointeur. Il est des valeurs parasites pour le moment, ou je pourrais initialiser à null. Mais permettez-moi de continuer avec cette idée de construire un arbre. Permettez-moi d'en créer une autre de ces nœuds qui dispose de 26 éléments en elle. 

Et vous savez quoi? Si ceci est seulement un noeud dans la mémoire que Je créé avec malloc, en utilisant une structure comme nous le verrons bientôt, Je vais faire this-- Je vais tirer une flèche à partir de la chose qui a représenté D vers le bas à ce nouveau noeud. Et maintenant, le prochain premier lettre au nom de Daven, V-- D-A-V-- je vais aller de l'avant et d'en tirer un autre nœud de ce genre, moyennant quoi, les éléments de V qui, ici, nous tirerons de whoops instance--. Nous ne serons pas tirer là. Il va aller ici. 

Ensuite, nous allons la considèrent comme V. Et puis ici, nous allons à l'index vers le bas de V dans ce que nous allons examiner E. Et puis à partir de là, nous allons aller prendre un de ces nœuds ici. Et maintenant, nous avons une question à répondre. Je dois en quelque sorte indiquer que nous sommes à la fin de la chaîne Daven. Donc, je ne pouvais laisser nulle. 

Mais que faire si nous avons Daven de nom complet aussi, qui est, comme nous l'avons dit, Davenport? Alors que faire si Daven est en fait une sous-chaîne, un préfixe d'une chaîne beaucoup plus longue? Nous ne pouvons pas en permanence dire rien ne va d'y aller, parce que nous avons pu jamais insérer un mot comme Davenport dans cette structure de données 

Donc, ce que nous pourrions faire à la place est traiter chacun de ces éléments comme peut-être avoir deux éléments à l'intérieur d'eux. L'un est un pointeur, en effet, comme je l'ai fait. Donc, chacun de ces boîtes est non seulement une cellule. Mais que faire si le haut One-- de celle du bas va être nul, car il est juste pas encore de Davenport. Que faire si le haut une est une valeur particulière? Et ça va être un peu difficile de dessiner cette taille. Mais supposons qu'il est juste une coche. Vérifiez. D-A-V-E-N est une chaîne dans cette structure de données. 

Pendant ce temps, si je devais plus d'espace ici, je pourrais faire P-O-R-T, et je pourrais mettre chèque dans le noeud qui comporte la lettre T à la fin. Donc ceci est un massivement complexe d'aspect structure de données. Et mon écriture certainement ne pas aider. Mais si je voulais insérer quelque chose autre, considérons ce que nous ferions. Si nous voulions mettre David en, nous aimerions suivre la même logique, D-A-V, mais maintenant je voudrais signaler à la prochaine élément pas de E, mais de I à D. Donc, il va y avoir plusieurs noeuds dans cet arbre. Nous allons avoir appel malloc plus. Mais je ne veux pas faire un désordre complet de cette image. Donc, nous allons plutôt regarder un qui a été pré-formulés comme ça avec pas dot, dot, points, mais seulement des tableaux abrégés. Mais chacun des noeuds dans cet arbre ici représente le même chose-- un tableau de taille Ray 26. 

Ou si nous voulons être vraiment bon maintenant, ce si le nom de quelqu'un que une apostrophe, nous allons supposer que chaque noeud a fait comme 27 index en elle, non seulement 26. Donc ce maintenant va être une des données structure appelée trie-- T-R-I-E. Un trie, qui est censé être historiquement un nom intelligent pour un arbre qui est optimisé pour l'extraction, ce qui bien sûr, est écrit avec un I-E il est donc trie. Mais qui est l'histoire de la Trie. 

Donc un trie sont ces données arborescente structure comme un arbre généalogique qui se comporte finalement comme ça. Et ici est juste un autre exemple de tas ensemble des noms d'autres personnes. Mais la question maintenant à portée de main est ce que ont nous avons gagné en introduisant sans doute un plus la structure de données complexe, et une, franchement, qui utilise beaucoup de mémoire. 

Parce que même si, pour le moment, je suis seulement à l'aide de D'pointeur et A et V et Es et Ns, Je perds un diable de beaucoup de mémoire. Mais là où je passe une ressource, Je tends à ne regagner un autre. Donc, si je passe plus d'espace, ce qui est probablement l'espoir? Que je suis en dépensant moins quoi? PUBLIC: Moins de temps. DAVID Malan: le temps. Maintenant, pourquoi pourrait-il être? Eh bien, ce qui est l'insertion temps, en termes de grand O maintenant, d'un nom comme Daven ou Davenport ou David? Eh bien, Daven était cinq étapes. Davenport serait neuf étapes, il serait donc un peu plus d'étapes. David serait cinq étapes ainsi. Donc, ce sont en béton chiffres, mais il ya sûrement une limite supérieure de la longueur du nom de quelqu'un. Et en effet, dans le problème cinq ensembles de spécification, nous allons proposer qu'il est quelque chose qui est de 40 caractères certains impairs. 

En réalité, personne n'a un nom infiniment long, ce qui veut dire que la longueur d'un nom ou la longueur d'une chaîne nous pourrions avoir certain de l'état de la structure est sans doute ce que? Il est constant. Droit? Il pourrait être une grande constante comme 40 quelque chose, mais il est constant. Et il n'a pas de dépendance sur le nombre de d'autres noms sont dans cette structure de données. En d'autres termes, si je voulu insérer maintenant Colton ou Gabriel ou Rob ou Zamyla ou Alison ou Belinda ou d'autres noms du personnel dans ces données la structure, est le temps d'exécution d'insérer d'autres noms va être tout un impact par combien d'autres éléments sont dans la structure de données déjà? Ce ne est pas. Droit? Parce que nous sommes effectivement en utilisant cette table de hachage multi-couche. Et le temps d'exécution de l'une de ces opérations dépend pas du nombre de les éléments qui se trouvent dans la structure de données ou qui vont éventuellement comme dans la structure de données, mais sur la longueur de ce particulier? 

La chaîne étant inséré, qui ne fait cette asymptotiquement constant Big O time-- d'un. Et franchement, tout en le monde réel, cette signifie inscrivant le nom de Daven prend comme cinq étapes, ou Davenport neuf étapes, ou David cinq étapes. Voilà sacrément petits temps de fonctionnement. Et, en effet, que est une très bonne chose, surtout quand il est indépendant de la totale nombre d'éléments de là. Alors, comment pouvons-nous mettre en œuvre ce type de structure dans le code? Il est un peu plus complexe, mais encore il est juste une demande de blocs de construction de base. Je vais à redéfinir nœud nous comme suit: bool appelé word-- et ce l'on pourrait appeler quelque chose. Mais le bool représente ce que je dessinais comme une coche. Oui. Ceci est la fin d'une chaîne dans cette structure de données. 

Et, bien sûr, la star de noeud il se réfère à des enfants. Et, en effet, comme Just un arbre généalogique, vous examinerait les nœuds qui pendait du fond d'un parent élément d'être des enfants. Et si les enfants va être un tableau de 27, 27 un juste pour être apostrophe. Nous allons trier de cas particulier que. Ainsi, vous pouvez avoir certains noms avec des apostrophes. Peut-être même trait d'union devrait aller là-bas, mais vous allez voir en p 5 ensemble nous de soins seulement les lettres et les apostrophes. 

Et puis, comment voulez-vous représentez la structure elle-même de données? Comment représentez-vous la racine de ce trie, pour ainsi dire? Eh bien, tout comme avec une liste chaînée, vous besoin d'un pointeur sur le premier élément. Avec un trie vous avez juste besoin d'un pointeur vers la racine de cette trie. Et à partir de là, vous pouvez hacher votre chemin vers le bas profond et plus profond pour chaque autre noeud dans la structure. Donc, tout simplement avec cette boîte nous représentons que struct. 

Maintenant Meanwhile-- Oh, question. 

Public: Quel est le mot de bool? 

DAVID Malan: mot de Bool est juste cette incarnation C de ce que je décrivais dans cette boîte ici, quand Je commencé à diviser chacune des Les éléments de tableau en deux morceaux. L'un est un pointeur vers le noeud suivant. L'autre doit être quelque chose comme une case à cocher de dire oui, il ya une Daven mot qui se termine ici, parce que nous ne voulons pas, pour le moment, Dave. 

Même si Dave va être un mot légitime, il est pas dans le trie encore. Et D est pas un mot. Et D-A est pas un mot ou un nom. Donc le coche indique seulement une fois que vous frappé ce nœud est la la trajectoire précédente de caractères fait une chaîne que vous avez inséré. Voilà donc tout le bool il est fait pour nous. 

D'autres questions sur essais? Ouais. 

Public: Quel est le chevauchement? Que faire si vous avez un Dave et Daven? DAVID Malan: Parfait. Que faire si vous avez un Dave et Daven? Donc, si nous insérons, dire un surnom, pour David-- Dave-- D-A-V-E? Ceci est en fait super simple. Donc, nous allons seulement prendre quatre mesures. D-A-V-E. Et qu'est-ce que je dois faire une fois que je frappe quatrième nœud? Tout va vérifier. Nous sommes déjà à partir. Terminé. Quatre étapes. Constante de temps asymptotiquement. Et maintenant, nous avons indiqué que les deux Dave et Daven sont des chaînes dans la structure. Donc, pas de problème. Et remarquez comment la présence Daven de ne pas faire prendre plus de temps ou moins temps pour Dave et vice versa. 

Alors, que pouvons-nous faire maintenant? Nous avons utilisé cette métaphore avant de plateaux représenter quelque chose. Mais il se trouve que pile de plateaux est en fait démonstratif d'un autre données abstrait bien-- une structure de données de niveau supérieur qu'à la fin de la journée est juste comme un tableau ou une liste chaînée ou quelque chose de plus banal. Mais il est un plus intéressant concept conceptuel. Une pile, comme ces plateaux ici à Mather, sont généralement appelés that-- juste une pile. 

Et dans ce type de structure de données vous avez deux operations-- vous avez un appelé poussée pour ajouter quelque chose à la pile, comme mettre un autre bac dos sur le dessus de la pile. Et puis pop, qui signifie que vous prendre la plus haute plateau éteint. Mais ce qui est essentiel sur une pile est que il a cette curieuse particularité. Comme le personnel de la salle de la salle sont réorganisant les plateaux pour le prochain repas, ce qui va être vrai sur la façon dont les étudiants interagir avec cette structure de données? PUBLIC: Ils vont à la pop un arrêt. DAVID Malan: Ils vont un pop off, nous espérons que le haut. Sinon, il est juste un peu stupide aller tout le chemin vers le bas. Droit? La structure de données ne permet pas vraiment vous prenez le plateau inférieur d'au moins facilement. Il ya donc ce curieux propriété à une pile que le dernier élément est va être le premier à sortir. Et les informaticiens appellent ce LIFO-- dernier entré, premier sorti. Et il n'a fait applications intéressantes. Il est pas nécessairement aussi évident que certains d'autres, mais il peut, en effet, être utile, et il peut, en effet, être mis en œuvre dans un couple de différentes manières. 

Donc un, et effectivement, laisser moi de ne pas plonger dans cela. Faisons-le à la place. Regardons un qui est presque la même idée, mais il est un peu plus juste. Droit? Si vous êtes l'un de ces garçons de ventilateur ou les filles qui aime vraiment les produits Apple et vous vous êtes réveillé à 3h00 faire la queue devant certains magasins pour obtenir la toute dernière iPhone, vous aurait fait la queue comme ça. 

Maintenant, une file d'attente est très délibérément nommé. Il ya une ligne parce qu'il ya une certaine équité à elle. Droit? Il genre de sucer si vous avez il a obtenu la première sur l'Apple Store mais vous êtes effectivement la plus basse plateau parce que les employés d'Apple puis pop de la dernière personne qui effectivement obtenu en ligne. Donc, les piles et les files d'attente, même si fonctionnellement ils sont un genre de la same-- il est juste cette collection des ressources qui est va croître et il ya shrink-- cet aspect de l'équité à elle, au moins dans le monde réel, où les opérations que vous exercer sont fondamentalement différentes. Un stack-- une file d'attente rather-- est dit avoir deux opérations: n files d'attente et d file d'attente. Ou vous pouvez les appeler un certain nombre de choses. Mais vous voulez juste saisir l'idée que l'on est d'ajouter et on est en fin de compte la soustraction. 

Maintenant, sous le capot, à la fois la pile et une file d'attente pourrait être mise en œuvre, comment? Nous ne rentrerons pas dans le code de parce que le niveau supérieur idée est une sorte de plus évident. Je veux dire, ce que font les humains? Si je suis la première personne à Apple Stocker et ceci est la porte d'entrée, vous savez, je vais rester ici. Et de l'autre personne va rester ici. Et de l'autre personne va rester ici. Alors quelle est la structure de données se prête à une file d'attente? 

PUBLIC: Une file d'attente. DAVID Malan: Eh bien, une file d'attente. Bien sûr. Quoi d'autre? 

PUBLIC: Une liste chaînée. 

DAVID Malan: A liée la liste que vous pourriez mettre en œuvre. Et une liste chaînée est agréable car alors il peut atteindre une longueur arbitraire, par opposition à avoir un certain nombre fixe de personnes dans le magasin. Mais peut-être un nombre fixe des lieux est légitime. Parce que si ils ont seulement comme 20 iPhones le premier jour, peut-être ils ont seulement besoin d'un tableau de taille 20 pour représenter cette file d'attente, qui est seulement de dire maintenant une fois que nous commençons à parler au sujet de ces problèmes de plus haut niveau, vous pouvez mettre en œuvre dans un certain nombre de façons. Et il est probablement juste aller à être un compromis dans l'espace et le temps ou tout simplement dans votre propre complexité du code. 

Qu'en est-il une pile? Eh bien, une pile, nous avons vu trop peuvent être tout simplement ces plateaux. Et vous pourriez mettre en œuvre ce un tableau. Mais à un moment donné si vous utilisez un tableau, ce qui va se passer pour les plateaux vous essayez de mettre bas? Bien. Vous allez seulement être capable d'aller si haut. Et je pense que dans Mather ils sont en fait en retrait dans cette ouverture. Donc, en effet, il est presque comme Mather utilise une matrice de taille fixe, parce que vous ne pouvez adapter tant de plateaux dans cette ouverture en le mur en bas des genoux des gens. Et que peut-être dit être un tableau, mais nous pourrions certainement mettre en œuvre que plus généralement avec une liste chaînée. 

Eh bien, qu'en est-il une autre structure de données? Permettez-moi de tirer vers le haut un autre visuel ici. Quelque chose comme diriez-vous celui-là? Pourquoi serait-il utile d'avoir pas quelque chose d'aussi chic que un trie, qui nous avons vu ces avions nœuds très larges, chacun d'eux est dans un tableau? Mais si nous faisons quelque chose de plus simplement, comme un vieil arbre de la famille de l'école, dont chacun des nœuds ici est juste stocker un nombre. Au lieu d'un nom ou d'un descendant est juste stocker un certain nombre de ce genre. 

Eh bien, le jargon que nous utilisons dans structures de données est à la fois essais et les arbres, où un trie, de nouveau, est juste un dont les noeuds sont des tableaux, est toujours ce que vous pourriez utiliser de l'école primaire quand vous avez fait une famille feuilles tree-- et la racine de l'arbre et les enfants de la mère et leurs frères et sœurs. Et nous pourrions mettre en place un arbre, par exemple, le plus simplement ce produit. Un arbre, si ce noeud en tant que l'un des ces cercles qui a un certain nombre, il ne va pas avoir un pointeur, mais deux. Et dès que vous ajoutez un second pointeur, vous peut effectivement maintenant prendre de la sorte de données à deux dimensions structures de mémoire. Tout comme un bidimensionnelle tableau, vous pouvez avoir de genre en deux dimensions listes liées, mais les qui suivent un motif où il n'y a pas de cycles. Il est vraiment un arbre avec un façon grand-parent ici et ensuite certains parents et enfants et petits-enfants et arrières petits-enfants. et ainsi de suite. 

Mais ce qui est vraiment bien à ce sujet aussi, juste pour vous taquiner avec un peu de code, rappel de la récursivité quelque temps en arrière, où vous écrivez une fonction qui se dit. Ceci est une belle occasion à mettre en oeuvre quelque chose comme la récursivité, car en tenir compte. 

Ceci est un arbre. Et je suis un peu anal avec la façon dont Je mets les nombres entiers dans la rue. Tant et si bien qu'il a un spécial name-- un arbre binaire de recherche. Maintenant, nous avons entendu parler de binaire recherche, mais pouvez-vous travailler à rebours à partir du nom de cette chose? Quel est le modèle de la façon dont je inséré les entiers dans cet arbre? Il est pas arbitraire. Il ya un certain modèle. Ouais. 

PUBLIC: Les plus petits sur la gauche. 

DAVID Malan: Ouais. Les plus petits sont sur la gauche. Les plus grands sont sur la droite. De telle sorte qu'une véritable déclaration est un parent est supérieure à sa fille gauche, mais moins que son enfant droit. Et que seul est même un définition verbale récursive parce que vous pouvez appliquer cette même à chaque noeud logique et il ne fond sur un scénario de base si vous volonté, lorsque vous appuyez sur l'un des les feuilles, pour ainsi dire, où un congé a plus aucun enfant. 

Maintenant, comment pouvez-vous trouver le numéro 44? Vous voulez commencer à la racine et dire, hm. 55 est donc 44 pas ce que je veux aller droit ou ce que je veux aller à gauche? Eh bien, évidemment, vous voulez aller à gauche. Et il est juste comme le téléphone livre par exemple à la recherche binaire plus généralement. Mais nous mettons en œuvre ce maintenant un peu plus dynamique qu'un tableau pourrait permettre. Et en fait, si vous voulez regarder au code, au premier coup d'œil sûr. Il ressemble à un tas de lignes. Mais il est magnifiquement simple. Si vous souhaitez mettre en place une fonction recherche appelé dont le but dans la vie est de rechercher une valeur comme n, un entier, et vous êtes passé dans un un pointer-- un pointeur vers le noeud de la racine, plutôt, de cet arbre à partir de laquelle vous pouvez accéder à tout le reste, remarquez comment carrément vous pouvez mettre en œuvre la logique. Si l'arbre est nulle, il est évidemment pas là. Disons simplement return false. Droit? Si vous le remettez rien, il n'y a rien. 

Sinon, si n est inférieur à arbre flèche, flèche n- maintenant n, rappelons nous avons introduit de super brièvement l'autre jour, et cela signifie simplement de référence du pointeur et examinez le champ appelé n. Donc, cela signifie qu'il va et regarder le champ appelé n. Donc, si n, la valeur que vous avez donné, est moins que la valeur du nombre entier d'arbres, où voulez-vous aller? À gauche. 

Donc remarquer la récursivité. Je returning-- pas vrai. Pas faux. Je retourne quelle que soit la réponse est par un appel à moi-même, en passant un n nouveau, ce qui est redondant, mais ce qui est légèrement différent maintenant? Comment vais-je faire le plus petit problème? Je suis de passage dans le deuxième l'argument, pas la racine de l'arbre, mais l'enfant gauche dans ce cas. Donc, je suis de passage à l'enfant gauche. 

Pendant ce temps, si n est plus grand que le noeud je suis en train de regarder, Je cherche le côté droit. Sinon, si l'arbre est non nulle, et si l'élément est pas à gauche et il ne veut pas le droit, ce qui est merveilleusement le cas? Nous avons effectivement trouvé le nœud question, et si nous revenons vrai. 

Donc, nous avons juste effleuré la surface maintenant une partie de ces structures de données. En problème réglé cinq vous aurez explorer ces encore plus loin, et vous recevrez votre conception choix de la façon d'aller à ce sujet. Ce que je voudrais conclure sur est juste un deuxième teaser de 30 de ce qui attend la semaine prochaine et au-delà. 

Comme nous begin-- heureusement que vous pourriez think-- notre transition lentement à partir de l'univers de C et inférieure les détails d'implémentation de niveau, à un monde dans lequel nous pouvons prendre pour acquis que quelqu'un d'autre a finalement mise en œuvre de ces données structures pour nous, et nous allons commencer à comprendre la signifie monde réel de la mise en œuvre programmes basés sur le Web et plus généralement sites et aussi la sécurité très implications que nous avons seulement commencé à gratter la surface de. Voici ce qui nous attend dans les jours à venir. 

[VIDEO LECTURE] 

-Il Est venu avec un message, avec un protocole qui lui est propre. Il est venu à un monde cruel pare-feu, routeurs indifférents, et les dangers bien pires que la mort. Il est rapide. Il est fort. Il est TCP / IP, et il a votre adresse. "Warriors of the Net". [FIN LECTURE VIDÉO] DAVID Malan: La semaine prochaine. Nous vous verrons ensuite. [VIDEO LECTURE] -Et Maintenant, "pensées profondes" par Daven Farnham. -David Commence toujours conférences avec, "Très bien." Pourquoi pas: «Voici la solution de problème de jeu "de cette semaine ou "Nous donnons tous un A?" [Rire] [FIN LECTURE VIDÉO]