1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:03,340 [Lecture de musique] 3 00:00:03,340 --> 00:00:11,020 4 00:00:11,020 --> 00:00:14,010 >> DAVID Malan: Ceci est CS50. 5 00:00:14,010 --> 00:00:18,090 Et cela est à la fois le début et la end-- comme literally-- presque la fin 6 00:00:18,090 --> 00:00:18,825 de la sixième semaine. 7 00:00:18,825 --> 00:00:20,030 8 00:00:20,030 --> 00:00:22,640 >> Je pensais que je partagerais un peu d'un fait amusant. 9 00:00:22,640 --> 00:00:25,370 Je l'ai tiré ce à partir d'un Les données de semestre passé fixés. 10 00:00:25,370 --> 00:00:29,710 Vous vous souviendrez que nous vous demandons à chaque p forme de jeu si vous avez regardé en ligne 11 00:00:29,710 --> 00:00:31,580 ou si vous avez assisté en personne. 12 00:00:31,580 --> 00:00:33,020 Et voici les données. 13 00:00:33,020 --> 00:00:34,710 Donc, aujourd'hui, était très prévisible. 14 00:00:34,710 --> 00:00:37,126 Mais nous voulions passer un peu de temps avec vous même. 15 00:00:37,126 --> 00:00:40,599 Quelqu'un voudrait-il conjecturer pourquoi cette graphique est tellement dentelée, haut bas, haut bas, 16 00:00:40,599 --> 00:00:41,265 de manière aussi systématique? 17 00:00:41,265 --> 00:00:42,980 18 00:00:42,980 --> 00:00:45,130 Qu'est-ce que chacun des pics et les creux représentent? 19 00:00:45,130 --> 00:00:46,005 >> PUBLIC: [Inaudible] 20 00:00:46,005 --> 00:00:47,002 21 00:00:47,002 --> 00:00:47,835 DAVID Malan: En effet. 22 00:00:47,835 --> 00:00:50,900 23 00:00:50,900 --> 00:00:55,480 Et plus amusante, à Dieu ne plaise, nous détenons une conférence le vendredi 24 00:00:55,480 --> 00:00:58,960 au début du semestre, Voilà ce que nous voyons se produire. 25 00:00:58,960 --> 00:01:03,430 Donc, aujourd'hui, nous participons à un peu plus sur des structures de données. 26 00:01:03,430 --> 00:01:06,660 Et pour vous donner plus d'un solide modèle mental de problèmes à cinq, 27 00:01:06,660 --> 00:01:07,450 qui vient de sortir. 28 00:01:07,450 --> 00:01:10,817 Fautes d'orthographe, dans laquelle, nous allons vous remettre un fichier texte quelque 100.000 29 00:01:10,817 --> 00:01:12,650 plus de mots anglais, et vous allez avoir 30 00:01:12,650 --> 00:01:17,770 de comprendre comment charger habilement les dans la mémoire, dans la mémoire vive, en utilisant des données 31 00:01:17,770 --> 00:01:19,330 la structure de votre choix. 32 00:01:19,330 --> 00:01:22,470 >> Maintenant une telle structure de données pourrait être, mais ne devrait probablement pas être, 33 00:01:22,470 --> 00:01:25,630 la liste chaînée assez simpliste, laquelle nous avons introduit la dernière fois. 34 00:01:25,630 --> 00:01:29,220 Et une liste chaînée avait au moins un avantage sur un tableau. 35 00:01:29,220 --> 00:01:32,096 Qu'est-ce un avantage de une liste chaînée sans doute? 36 00:01:32,096 --> 00:01:32,950 >> PUBLIC: Insertion. 37 00:01:32,950 --> 00:01:33,908 >> DAVID Malan: Insertion. 38 00:01:33,908 --> 00:01:34,155 39 00:01:34,155 --> 00:01:35,196 Que voulez-vous dire par là? 40 00:01:35,196 --> 00:01:37,872 >> Public: tout le long la liste [inaudible]. 41 00:01:37,872 --> 00:01:38,770 >> DAVID Malan: Bon. 42 00:01:38,770 --> 00:01:42,090 Ainsi, vous pouvez insérer un élément où vous voulez dans le milieu de la liste 43 00:01:42,090 --> 00:01:45,490 sans avoir à mélanger tout, lequel nous avons conclu, dans notre tri 44 00:01:45,490 --> 00:01:47,630 discussions, est pas nécessairement une bonne chose, 45 00:01:47,630 --> 00:01:51,200 car il faut du temps pour se déplacer réellement tous ces humains gauche ou la droite. 46 00:01:51,200 --> 00:01:55,540 Et avec une liste chaînée, vous pouvez juste allouer avec malloc, un nouveau noeud, 47 00:01:55,540 --> 00:01:58,385 et ensuite mettre à jour un couple de pointers-- deux, trois opérations max-- 48 00:01:58,385 --> 00:02:01,480 et nous sommes en mesure de fente quelqu'un dans n'importe où dans une liste. 49 00:02:01,480 --> 00:02:03,550 >> Qu'y avait avantageux sur une liste chaînée? 50 00:02:03,550 --> 00:02:04,980 51 00:02:04,980 --> 00:02:05,659 Ouais? 52 00:02:05,659 --> 00:02:06,534 >> PUBLIC: [Inaudible] 53 00:02:06,534 --> 00:02:07,538 54 00:02:07,538 --> 00:02:08,413 DAVID Malan: Parfait. 55 00:02:08,413 --> 00:02:10,590 56 00:02:10,590 --> 00:02:11,090 Parfait. 57 00:02:11,090 --> 00:02:12,070 Il est vraiment dynamique. 58 00:02:12,070 --> 00:02:15,100 Et que vous n'êtes pas commettre, à l'avance, dans une certaine taille fixe 59 00:02:15,100 --> 00:02:18,750 bloc de mémoire, comme vous auriez à avec un tableau, la hausse de qui 60 00:02:18,750 --> 00:02:22,455 est que vous pouvez allouer nœuds seulement sur demande l'aide ainsi que la quantité de l'espace 61 00:02:22,455 --> 00:02:23,330 que vous avez réellement besoin. 62 00:02:23,330 --> 00:02:26,830 Contrairement à un tableau, vous pourriez allouer accidentellement trop peu. 63 00:02:26,830 --> 00:02:28,871 Et puis il va juste être une douleur dans le cou 64 00:02:28,871 --> 00:02:32,440 de réaffecter un nouveau grand tableau, copier tout sur, libérer l'ancien tableau, 65 00:02:32,440 --> 00:02:33,990 et de passer ensuite sur votre entreprise. 66 00:02:33,990 --> 00:02:37,479 Ou pire, vous pourriez allouer façon plus de mémoire que vous avez réellement besoin, 67 00:02:37,479 --> 00:02:40,520 et si vous allez avoir une très tableau peu peuplée, pour ainsi dire. 68 00:02:40,520 --> 00:02:44,350 >> Ainsi, une liste chaînée vous donne ces avantages de dynamisme et de flexibilité 69 00:02:44,350 --> 00:02:46,080 avec des insertions et des suppressions. 70 00:02:46,080 --> 00:02:48,000 Mais sûrement il doit y avoir un prix à payer. 71 00:02:48,000 --> 00:02:50,000 En fait, l'un des thèmes exploré sur questionnaire zéro 72 00:02:50,000 --> 00:02:52,430 était un couple de compromis nous avons vu jusqu'à présent. 73 00:02:52,430 --> 00:02:56,161 Alors, quel est le prix à payer ou une la baisse d'une liste chaînée? 74 00:02:56,161 --> 00:02:56,660 Ouais. 75 00:02:56,660 --> 00:02:57,560 >> PUBLIC: Pas d'accès aléatoire. 76 00:02:57,560 --> 00:02:58,809 >> DAVID Malan: Pas d'accès aléatoire. 77 00:02:58,809 --> 00:02:59,540 Mais qui se soucie? 78 00:02:59,540 --> 00:03:01,546 Accès aléatoire ne semble pas convaincante. 79 00:03:01,546 --> 00:03:02,421 >> PUBLIC: [Inaudible] 80 00:03:02,421 --> 00:03:04,865 81 00:03:04,865 --> 00:03:05,740 DAVID Malan: Exactement. 82 00:03:05,740 --> 00:03:07,580 Si vous voulez avoir un certain algorithm-- 83 00:03:07,580 --> 00:03:10,170 et permettez-moi de réellement propose recherche binaire en particulier, qui 84 00:03:10,170 --> 00:03:12,600 est un que nous avons utilisé tout un bit-- Si vous ne disposez pas d'accès aléatoire, 85 00:03:12,600 --> 00:03:15,516 vous ne pouvez pas faire ce que l'arithmétique simple de trouver comme l'élément central 86 00:03:15,516 --> 00:03:16,530 et le saut droit. 87 00:03:16,530 --> 00:03:20,239 Vous avez la place pour commencer à la première élément linéaire et rechercher de gauche 88 00:03:20,239 --> 00:03:22,780 à droite si vous voulez trouver le milieu ou tout autre élément. 89 00:03:22,780 --> 00:03:24,410 >> PUBLIC: Il faut probablement plus de mémoire. 90 00:03:24,410 --> 00:03:25,040 >> DAVID Malan: Prend plus de mémoire. 91 00:03:25,040 --> 00:03:27,464 Où est ce supplémentaire coût en provenance de la mémoire? 92 00:03:27,464 --> 00:03:28,339 >> PUBLIC: [Inaudible] 93 00:03:28,339 --> 00:03:32,566 94 00:03:32,566 --> 00:03:33,440 DAVID Malan: Exactement. 95 00:03:33,440 --> 00:03:35,679 Dans ce cas là, nous avions une liste chaînée pour les entiers, 96 00:03:35,679 --> 00:03:37,470 et pourtant, nous avons doublé la quantité de mémoire 97 00:03:37,470 --> 00:03:39,680 nous devons en stockant également ces pointeurs. 98 00:03:39,680 --> 00:03:42,090 Maintenant, moins d'un gros problème, vos struct grossissent 99 00:03:42,090 --> 00:03:45,320 et vous stockez pas un numéro, mais peut-être un étudiant ou un autre objet. 100 00:03:45,320 --> 00:03:46,880 Mais la question reste certainement. 101 00:03:46,880 --> 00:03:49,421 Et si un certain nombre des opérations sur les listes chaînées ont été appelés 102 00:03:49,421 --> 00:03:50,570 étaient grandes O de linéaire n-. 103 00:03:50,570 --> 00:03:54,730 Des choses comme l'insertion ou la recherche ou la suppression dans le cas où un élément 104 00:03:54,730 --> 00:03:57,720 se trouvait à la fin de la liste si elle est triée ou non. 105 00:03:57,720 --> 00:04:01,167 >> Parfois, vous pourriez avoir de la chance et en les limites inférieures de sorte à ces opérations, 106 00:04:01,167 --> 00:04:04,250 pourrait aussi être constante de temps si vous êtes toujours à la recherche du premier élément, 107 00:04:04,250 --> 00:04:05,070 par exemple. 108 00:04:05,070 --> 00:04:09,360 Mais en fin de compte, nous avons promis pour atteindre le Saint Graal 109 00:04:09,360 --> 00:04:12,630 des structures de données, ou certains de ceux-ci d'approximation, 110 00:04:12,630 --> 00:04:14,290 à titre de constante de temps. 111 00:04:14,290 --> 00:04:17,579 Pouvons-nous trouver des éléments ou ajouter des éléments ou supprimer des éléments d'une liste? 112 00:04:17,579 --> 00:04:19,059 Nous verrons assez rapidement. 113 00:04:19,059 --> 00:04:21,100 Et il se trouve que l'on des mécanismes que nous sommes 114 00:04:21,100 --> 00:04:23,464 va commencer à utiliser aujourd'hui, utilisation annuelle p fixé cinq, 115 00:04:23,464 --> 00:04:24,630 est en fait assez familier. 116 00:04:24,630 --> 00:04:27,430 Par exemple, si ce groupe est un des ouvrages d'examen, chacun d'entre eux 117 00:04:27,430 --> 00:04:29,660 a un étudiant de première Prénom et nom dessus, 118 00:04:29,660 --> 00:04:31,820 et je les ramasse de à la fin d'un examen, 119 00:04:31,820 --> 00:04:33,746 et ils sont tous assez beaucoup dans un ordre aléatoire, 120 00:04:33,746 --> 00:04:36,370 et nous voulons aller sur le tri ces examens de sorte qu'une fois classés 121 00:04:36,370 --> 00:04:38,661 il est juste beaucoup plus facile et plus rapide de les restituer à 122 00:04:38,661 --> 00:04:40,030 aux étudiants par ordre alphabétique. 123 00:04:40,030 --> 00:04:42,770 Quelles seraient vos instincts être pour un tas d'examens de ce genre? 124 00:04:42,770 --> 00:04:45,019 >> Eh bien, si vous êtes comme moi, vous peut voir que cela est m, 125 00:04:45,019 --> 00:04:48,505 Je vais donc en quelque sorte de mettre cela en, si cela est ma table ou mon étage où 126 00:04:48,505 --> 00:04:50,650 Je suis la diffusion de choses out-- ou mon tableau really-- 127 00:04:50,650 --> 00:04:52,210 Je pourrais mettre tout le Mme là. 128 00:04:52,210 --> 00:04:52,710 Oh. 129 00:04:52,710 --> 00:04:55,020 Voici un A. Donc, je pourrais Comme mettre les ici. 130 00:04:55,020 --> 00:04:55,520 Oh. 131 00:04:55,520 --> 00:04:57,980 Voici un autre R. Je vais à mettre que sur ici. 132 00:04:57,980 --> 00:05:02,490 Voici un Z. Voici un autre M. Et Je pourrais commencer à faire des piles de ce genre. 133 00:05:02,490 --> 00:05:06,620 Et puis peut-être que je vais en plus tard et une sorte de très nitpicky-ly sorte 134 00:05:06,620 --> 00:05:07,710 les piles individuelles. 135 00:05:07,710 --> 00:05:11,300 Mais le fait est que je chercherais à l'entrée que je suis solitaire 136 00:05:11,300 --> 00:05:14,016 et je voudrais faire quelques calculé décision fondée sur cette entrée. 137 00:05:14,016 --> 00:05:15,640 Si elle commence par A, le mettre là-bas. 138 00:05:15,640 --> 00:05:18,980 Si elle commence par Z, le mettre sur là, et tout le reste. 139 00:05:18,980 --> 00:05:22,730 >> Donc, ceci est une technique qui est généralement connu sous le nom hashing-- H-A-S-H- 140 00:05:22,730 --> 00:05:26,550 ce qui signifie en général que la prise entrée et en utilisant cette entrée à calculer 141 00:05:26,550 --> 00:05:30,940 une valeur, généralement un numéro, et que nombre est l'indice dans une mémoire 142 00:05:30,940 --> 00:05:32,260 récipient, comme un tableau. 143 00:05:32,260 --> 00:05:35,490 En d'autres termes, je pourrais avoir une fonction de hachage, comme je le fais dans ma tête, 144 00:05:35,490 --> 00:05:37,940 que si je vois quelqu'un est nom qui commence par A, 145 00:05:37,940 --> 00:05:40,190 Je vais la carte que à zéro dans ma tête. 146 00:05:40,190 --> 00:05:44,160 Et si je vois quelqu'un avec Z, je suis aller à la carte que 25 dans ma tête 147 00:05:44,160 --> 00:05:46,220 et puis mettre cela en la dernière pile plus. 148 00:05:46,220 --> 00:05:50,990 >> Maintenant, si vous pensez pas mon cerveau mais un programme C, ce qui pourrait numéros 149 00:05:50,990 --> 00:05:53,170 vous comptez sur pour atteindre le même résultat? 150 00:05:53,170 --> 00:05:55,594 En d'autres termes, si vous avait le caractère ASCII A, 151 00:05:55,594 --> 00:05:57,510 comment déterminez-vous ce seau à mettre en? 152 00:05:57,510 --> 00:05:59,801 Vous ne voulez probablement pas à mettre dans un seau de 65 ans, qui 153 00:05:59,801 --> 00:06:01,840 serait comme là-bas sans raison valable. 154 00:06:01,840 --> 00:06:04,320 Où voulez-vous mettre un en termes de sa valeur ASCII? 155 00:06:04,320 --> 00:06:05,600 156 00:06:05,600 --> 00:06:08,920 Où voulez-vous faire pour son ASCII valeur à venir avec un seau intelligent 157 00:06:08,920 --> 00:06:09,480 à mettre en? 158 00:06:09,480 --> 00:06:10,206 >> PUBLIC: Minus A. 159 00:06:10,206 --> 00:06:10,956 >> DAVID Malan: Ouais. 160 00:06:10,956 --> 00:06:13,190 Donc moins A ou moins spécifiquement 65 si elle est 161 00:06:13,190 --> 00:06:18,240 un grand A. Ou 98 si il est un minuscule un. 162 00:06:18,240 --> 00:06:21,300 Et si cela nous permettra de très simplement et très arithmétiquement, 163 00:06:21,300 --> 00:06:23,260 mettre quelque chose dans un seau comme ça. 164 00:06:23,260 --> 00:06:26,010 Donc, il se trouve que nous faisons réellement ce ainsi même avec les jeux-questionnaires. 165 00:06:26,010 --> 00:06:29,051 >> Donc, vous pourriez rappeler que vous avez encerclé votre le nom de l'enseignement compatriote sur la couverture. 166 00:06:29,051 --> 00:06:32,270 Et les noms du TF ont été organisées dans ces colonnes par ordre alphabétique, 167 00:06:32,270 --> 00:06:34,400 Eh bien, croyez-le ou non, quand tout 80 plus de nous 168 00:06:34,400 --> 00:06:37,800 se sont réunis l'autre soir au grade, la dernière étape de notre processus de classement 169 00:06:37,800 --> 00:06:41,830 est à hacher les quiz dans un grand espace de parole à la [inaudible] 170 00:06:41,830 --> 00:06:45,110 et de jeter les quiz de tout le monde exactement dans l'ordre de leur TF de 171 00:06:45,110 --> 00:06:47,700 noms sur la couverture, parce que alors il est beaucoup plus facile pour nous 172 00:06:47,700 --> 00:06:51,290 à parcourir que l'utilisation linéaire recherche ou une sorte d'intelligence 173 00:06:51,290 --> 00:06:54,050 pour un TF de trouver son ou Les quiz de ses élèves. 174 00:06:54,050 --> 00:06:56,060 >> Donc cette idée de hachage que vous verrez est 175 00:06:56,060 --> 00:07:00,520 très puissant est en fait assez banal et très intuitive, 176 00:07:00,520 --> 00:07:03,000 tout comme peut-être diviser et conquête était en semaine zéro. 177 00:07:03,000 --> 00:07:05,250 Je avance rapide au hackathon Il ya une couple d'années. 178 00:07:05,250 --> 00:07:08,040 Ce fut Zamyla et un couple de d'autres étudiants personnel de vœux 179 00:07:08,040 --> 00:07:09,030 comme ils sont entrés. 180 00:07:09,030 --> 00:07:12,680 Et nous avons eu tout un tas de pliage tables là-bas avec des étiquettes de nom. 181 00:07:12,680 --> 00:07:15,380 Et nous avions les tags de nom organisé avec comme les plus Comme il 182 00:07:15,380 --> 00:07:16,690 et ZS là-bas. 183 00:07:16,690 --> 00:07:20,350 Et si l'un des facteurs de transcription très habilement écrit ce que les instructions 184 00:07:20,350 --> 00:07:21,030 pour la journée. 185 00:07:21,030 --> 00:07:24,480 Et dans la semaine 12 du semestre ce tout fait sens et tout le monde parfait 186 00:07:24,480 --> 00:07:25,310 savait quoi faire. 187 00:07:25,310 --> 00:07:27,900 Mais quand vous avez la file d'attente de la même façon, 188 00:07:27,900 --> 00:07:30,272 vous êtes mise en œuvre de la même notion de hachage. 189 00:07:30,272 --> 00:07:31,730 Donc, nous allons formaliser un peu. 190 00:07:31,730 --> 00:07:32,890 Voici un tableau. 191 00:07:32,890 --> 00:07:36,820 Il est établi à un peu large juste pour illustrer, visuellement, 192 00:07:36,820 --> 00:07:38,920 que nous pourrions mettre les chaînes dans quelque chose comme ça. 193 00:07:38,920 --> 00:07:41,970 Et ce tableau est clairement de la taille 26 au total. 194 00:07:41,970 --> 00:07:43,935 Et la chose est appelé tableau arbitrairement. 195 00:07:43,935 --> 00:07:48,930 Mais cette interprétation est juste d'un artiste de ce qu'est une table de hachage peut être. 196 00:07:48,930 --> 00:07:52,799 >> Ainsi, une table de hachage maintenant va une structure de données de niveau supérieur. 197 00:07:52,799 --> 00:07:54,840 A la fin de la journée, nous sommes sur le point de voir que vous 198 00:07:54,840 --> 00:07:58,700 peut mettre en œuvre une table de hachage, qui est un peu comme l'enregistrement en ligne 199 00:07:58,700 --> 00:08:02,059 à un hackathon un peu comme ce tableau utilisé pour le tri des livres d'examen. 200 00:08:02,059 --> 00:08:03,850 Mais une table de hachage est sorte de ce haut niveau 201 00:08:03,850 --> 00:08:08,250 concept qui pourrait utiliser un tableau sous le capot de la mettre en œuvre, 202 00:08:08,250 --> 00:08:11,890 ou il pourrait utiliser une liste de longueur, ou même peut-être d'autres structures de données. 203 00:08:11,890 --> 00:08:15,590 Et maintenant que la prise est theme-- certains de ces ingrédients fondamentaux 204 00:08:15,590 --> 00:08:18,310 comme un tableau et ce bâtiment bloquer maintenant d'une liste de longueur 205 00:08:18,310 --> 00:08:21,740 et voir ce que nous pouvons construire au-dessus de ceux qui, comme ingrédients 206 00:08:21,740 --> 00:08:26,550 dans une recette, ce qui rend de plus en plus résultats finaux intéressantes et utiles. 207 00:08:26,550 --> 00:08:28,680 >> Donc, avec la table de hachage nous pourrions mettre en œuvre 208 00:08:28,680 --> 00:08:32,540 dans la mémoire imagée comme ça, mais comment peut-il réellement être codé en place? 209 00:08:32,540 --> 00:08:33,789 Eh bien, peut-être est que tout simplement cela. 210 00:08:33,789 --> 00:08:38,270 Si la capacité en majuscules, est juste certains constant-- par exemple 26, 211 00:08:38,270 --> 00:08:42,030 pour 26 lettres de l'alphabet-- Je pourrais appeler ma table de variables, 212 00:08:42,030 --> 00:08:45,630 et je pourrais prétendre que je vais mettre étoiles omble là-dedans, ou une chaîne. 213 00:08:45,630 --> 00:08:49,880 Donc, il est aussi simple que cela si vous vouloir mettre en place une table de hachage. 214 00:08:49,880 --> 00:08:51,490 Et pourtant, cela est vraiment juste un tableau. 215 00:08:51,490 --> 00:08:53,198 Mais encore une fois, une table de hachage table est maintenant ce que nous allons 216 00:08:53,198 --> 00:08:57,470 appeler un type de données abstrait qui est juste une sorte de superposition conceptuelle sur le dessus 217 00:08:57,470 --> 00:09:00,780 de quelque chose de plus terre à terre voudrais maintenant un tableau. 218 00:09:00,780 --> 00:09:02,960 >> Maintenant, comment allons-nous sur la résolution de problèmes? 219 00:09:02,960 --> 00:09:06,980 Eh bien, plus tôt je eu le luxe d'avoir suffisamment d'espace de table ici 220 00:09:06,980 --> 00:09:09,460 de sorte que je pouvais mettre la quiz n'importe où je voulais. 221 00:09:09,460 --> 00:09:10,620 Donc, comme on aurait pu aller ici. 222 00:09:10,620 --> 00:09:12,100 Zs peuvent aller ici. 223 00:09:12,100 --> 00:09:13,230 Mme pourrait aller ici. 224 00:09:13,230 --> 00:09:14,740 Et puis je devais un peu d'espace supplémentaire. 225 00:09:14,740 --> 00:09:18,740 Mais cela est un peu d'un droit triche maintenant, parce que ce tableau, si je vraiment 226 00:09:18,740 --> 00:09:22,720 pensé comme un tableau, est juste va être d'une certaine taille fixe. 227 00:09:22,720 --> 00:09:25,380 >> Donc, techniquement, si je tire jusqu'à quiz d'un autre élève 228 00:09:25,380 --> 00:09:28,490 et voir, oh, cette personne de nom commence par un A trop, 229 00:09:28,490 --> 00:09:30,980 Je veux sorte de l'y mettre. 230 00:09:30,980 --> 00:09:34,740 Mais dès que je l'ai mis là, si ce tableau représente en effet un tableau, 231 00:09:34,740 --> 00:09:37,840 Je vais être remplaçant ou démolir quiconque quiz de cet élève est. 232 00:09:37,840 --> 00:09:38,340 Droit? 233 00:09:38,340 --> 00:09:41,972 Si cela est un tableau, une seule chose peut aller à chacune de ces cellules ou d'éléments. 234 00:09:41,972 --> 00:09:43,680 Et si je dois genre de à choisir. 235 00:09:43,680 --> 00:09:45,735 >> Maintenant, plus tôt je sorte de triché et a fait ceci ou je 236 00:09:45,735 --> 00:09:47,526 juste un peu empilés les uns sur les autres. 237 00:09:47,526 --> 00:09:49,170 Mais cela ne va pas à voler dans le code. 238 00:09:49,170 --> 00:09:52,260 Alors, où puis-je mettre la deuxième élève dont le nom 239 00:09:52,260 --> 00:09:54,964 est un si tout ce que je devais est ce l'espace disponible de la table? 240 00:09:54,964 --> 00:09:57,880 Et je l'ai utilisé trois fentes et il On dirait qu'il ya quelques autres. 241 00:09:57,880 --> 00:09:58,959 Que pourriez-vous faire? 242 00:09:58,959 --> 00:09:59,834 PUBLIC: [Inaudible] 243 00:09:59,834 --> 00:10:00,565 244 00:10:00,565 --> 00:10:01,315 DAVID Malan: Ouais. 245 00:10:01,315 --> 00:10:02,370 Peut-être que nous allons juste garder les choses simples. 246 00:10:02,370 --> 00:10:02,660 Droit? 247 00:10:02,660 --> 00:10:04,243 Il ne correspond pas où je veux le mettre. 248 00:10:04,243 --> 00:10:07,450 Je vais donc le mettre techniquement où un B irait. 249 00:10:07,450 --> 00:10:09,932 Maintenant, bien sûr, je commence de me peindre dans un coin. 250 00:10:09,932 --> 00:10:11,890 Si je reçois un étudiant dont le nom est en fait B, 251 00:10:11,890 --> 00:10:14,840 maintenant B va être déplacé un peu avant, comme cela peut arriver, oui, 252 00:10:14,840 --> 00:10:17,530 si cela est un B, maintenant il doit aller ici. 253 00:10:17,530 --> 00:10:20,180 >> Et ce très rapidement pourrait devenir problématique, 254 00:10:20,180 --> 00:10:23,850 mais il est une technique qui fait est dénommé linéaire de palpage, 255 00:10:23,850 --> 00:10:26,650 où vous considérez juste votre tableau à la ligne. 256 00:10:26,650 --> 00:10:29,680 Et vous venez de type de sonde ou inspecter chaque élément disponible 257 00:10:29,680 --> 00:10:31,360 la recherche d'une place disponible. 258 00:10:31,360 --> 00:10:34,010 Et dès que vous trouvez un, vous le déposez là. 259 00:10:34,010 --> 00:10:38,390 >> Maintenant, le prix à payer maintenant pour cette solution est quoi? 260 00:10:38,390 --> 00:10:41,300 Nous avons un tableau de taille fixe, et quand je insérer des noms 261 00:10:41,300 --> 00:10:44,059 en elle, au moins au début, ce qui est le temps d'exécution de l'insertion 262 00:10:44,059 --> 00:10:46,350 pour mettre les élèves » quiz dans les bons seaux? 263 00:10:46,350 --> 00:10:48,710 264 00:10:48,710 --> 00:10:50,002 Big O de quoi? 265 00:10:50,002 --> 00:10:51,147 >> PUBLIC: n. 266 00:10:51,147 --> 00:10:52,480 DAVID Malan: je entendu grand O de n. 267 00:10:52,480 --> 00:10:53,530 268 00:10:53,530 --> 00:10:54,300 Pas vrai. 269 00:10:54,300 --> 00:10:56,490 Mais nous allons démêler pourquoi dans un instant. 270 00:10:56,490 --> 00:10:57,702 Que pourrait-il être? 271 00:10:57,702 --> 00:10:58,755 >> PUBLIC: [Inaudible] 272 00:10:58,755 --> 00:11:00,380 DAVID Malan: Et permettez-moi de le faire visuellement. 273 00:11:00,380 --> 00:11:04,720 Supposons donc que ceci est la lettre S. 274 00:11:04,720 --> 00:11:05,604 >> PUBLIC: Il est un. 275 00:11:05,604 --> 00:11:06,520 DAVID Malan: Il est un. 276 00:11:06,520 --> 00:11:06,710 Droit? 277 00:11:06,710 --> 00:11:08,950 Ceci est un tableau, qui signifie que nous avons accès aléatoire. 278 00:11:08,950 --> 00:11:11,790 Et si nous pensons de cette comme zéro et ce comme 25, 279 00:11:11,790 --> 00:11:13,800 et nous nous rendons compte que, oh, voici mon entrée S, 280 00:11:13,800 --> 00:11:16,350 Je peux certainement convertir S, un caractère ASCII, 281 00:11:16,350 --> 00:11:18,540 pour un nombre correspondant entre zéro et 25 282 00:11:18,540 --> 00:11:20,910 et puis tout de suite mettre où il appartient. 283 00:11:20,910 --> 00:11:26,120 >> Mais bien sûr, dès que je reçois à la deuxième personne dont le nom est A ou B ou C 284 00:11:26,120 --> 00:11:29,300 finalement, si je l'ai utilisé la sondage linéaire que ma solution, 285 00:11:29,300 --> 00:11:31,360 le temps d'exécution de insertion dans le pire des cas 286 00:11:31,360 --> 00:11:33,120 qui se passe réellement à se transformer en quoi? 287 00:11:33,120 --> 00:11:34,270 288 00:11:34,270 --> 00:11:36,045 Et je ne l'entends ici correctement dès le début. 289 00:11:36,045 --> 00:11:36,920 PUBLIC: [Inaudible] 290 00:11:36,920 --> 00:11:41,620 DAVID Malan: Donc, il est en effet n fois vous avez un assez grand nombre de données. 291 00:11:41,620 --> 00:11:44,410 Ainsi, d'une part, si votre tableau est assez grand 292 00:11:44,410 --> 00:11:48,287 et vos données sont assez rares, vous obtenir ce beau temps constant. 293 00:11:48,287 --> 00:11:50,620 Mais dès que vous commencez devient de plus en plus d'éléments, 294 00:11:50,620 --> 00:11:53,200 et juste statistiquement vous obtenez plus de gens avec la lettre 295 00:11:53,200 --> 00:11:56,030 A comme leur nom ou la lettre B, il pourrait potentiellement 296 00:11:56,030 --> 00:11:57,900 se transformer en quelque chose de plus linéaire. 297 00:11:57,900 --> 00:11:59,640 Donc, pas tout à fait parfait. 298 00:11:59,640 --> 00:12:00,690 Ainsi pourrions-nous faire mieux? 299 00:12:00,690 --> 00:12:03,210 >> Eh bien, ce qui était notre solution avant lorsque nous 300 00:12:03,210 --> 00:12:06,820 voulez avoir plus de dynamisme que quelque chose comme un tableau permis? 301 00:12:06,820 --> 00:12:08,085 302 00:12:08,085 --> 00:12:08,960 PUBLIC: [Inaudible] 303 00:12:08,960 --> 00:12:10,030 DAVID Malan: Qu'avons-nous introduisons? 304 00:12:10,030 --> 00:12:10,530 Ouais. 305 00:12:10,530 --> 00:12:11,430 Ainsi, une liste chaînée. 306 00:12:11,430 --> 00:12:14,430 Eh bien, voyons ce que la liaison des liste pourrait faire pour nous à la place. 307 00:12:14,430 --> 00:12:17,630 Eh bien, je vous propose que nous dessiner l'image comme suit. 308 00:12:17,630 --> 00:12:19,620 Maintenant, cela est une autre photo d'un exemple 309 00:12:19,620 --> 00:12:24,750 à partir d'un texte différent, en fait, que est fait en utilisant un tableau de taille 31. 310 00:12:24,750 --> 00:12:28,220 Et cet auteur simplement décidé de hachage cordes 311 00:12:28,220 --> 00:12:32,430 ne repose pas sur les noms de la personne, mais en fonction de leurs dates de naissance. 312 00:12:32,430 --> 00:12:35,680 Quel que soit le mois, ils ont pensé si vous êtes né le premier du mois 313 00:12:35,680 --> 00:12:39,580 ou le 31 d'un mois, l'auteur sera hachage basé sur cette valeur, 314 00:12:39,580 --> 00:12:44,154 de façon à répartir les noms un peu plus que 26 points pourraient permettre. 315 00:12:44,154 --> 00:12:47,320 Et peut-être qu'il est un peu plus uniforme que d'aller avec des lettres, 316 00:12:47,320 --> 00:12:50,236 parce que bien sûr il ya probablement plus de personnes dans le monde avec des noms 317 00:12:50,236 --> 00:12:54,020 que commencer avec un de certainement d'autres lettres de l'alphabet. 318 00:12:54,020 --> 00:12:56,380 Alors peut-être cela est un peu plus uniforme, en supposant 319 00:12:56,380 --> 00:12:58,640 une distribution uniforme des bébés sur un mois. 320 00:12:58,640 --> 00:12:59,990 >> Mais, bien sûr, cela est encore imparfait. 321 00:12:59,990 --> 00:13:00,370 Droit? 322 00:13:00,370 --> 00:13:01,370 Nous allons avoir des collisions. 323 00:13:01,370 --> 00:13:04,680 Plusieurs personnes dans cette structure de données sont encore 324 00:13:04,680 --> 00:13:08,432 ayant la même date de naissance au moins vous êtes indépendamment de mois. 325 00:13:08,432 --> 00:13:09,640 Mais ce qui a fait l'auteur? 326 00:13:09,640 --> 00:13:13,427 Eh bien, il semble que nous ayons un tableau sur le côté gauche tiré verticalement, 327 00:13:13,427 --> 00:13:15,010 mais qui est tout simplement l'interprétation d'un artiste. 328 00:13:15,010 --> 00:13:18,009 Il n'a pas d'importance quelle direction vous dessiner un tableau, il est toujours un tableau. 329 00:13:18,009 --> 00:13:20,225 Quel est ce un tableau de apparemment? 330 00:13:20,225 --> 00:13:21,500 >> PUBLIC: liste chaînée. 331 00:13:21,500 --> 00:13:21,650 >> DAVID Malan: Ouais. 332 00:13:21,650 --> 00:13:23,490 Il semble que ce soit un tableau de liste chaînée. 333 00:13:23,490 --> 00:13:26,490 Encore une fois, à ce point de sorte de l'utilisation de ces structures de données maintenant 334 00:13:26,490 --> 00:13:28,550 comme ingrédients de plus des solutions intéressantes, 335 00:13:28,550 --> 00:13:30,862 vous ne pouvez absolument prendre un fondamental, comme un tableau, 336 00:13:30,862 --> 00:13:33,320 et puis prendre quelque chose de plus intéressant comme une liste chaînée 337 00:13:33,320 --> 00:13:36,660 et même les combiner dans un même Structure de données plus intéressant. 338 00:13:36,660 --> 00:13:39,630 Et en effet, ce serait trop être appelé une table de hachage, 339 00:13:39,630 --> 00:13:42,610 de sorte que le tableau est vraiment la table de hachage, 340 00:13:42,610 --> 00:13:45,600 mais que la table de hachage a chaînes, pour ainsi dire, 341 00:13:45,600 --> 00:13:50,220 qui peut augmenter ou diminuer en fonction de la nombre d'éléments que vous souhaitez insérer. 342 00:13:50,220 --> 00:13:52,990 >> Maintenant, en conséquence, ce qui est le temps d'exécution maintenant? 343 00:13:52,990 --> 00:13:58,030 Si je veux insérer quelqu'un dont l'anniversaire est le 31 Octobre, 344 00:13:58,030 --> 00:13:59,040 Où va-il ou elle? 345 00:13:59,040 --> 00:14:00,530 346 00:14:00,530 --> 00:14:01,030 Bien. 347 00:14:01,030 --> 00:14:02,819 Tout en bas, où il est dit 31. 348 00:14:02,819 --> 00:14:03,610 Et qui est parfait. 349 00:14:03,610 --> 00:14:05,060 Ce fut un temps constant. 350 00:14:05,060 --> 00:14:08,760 Mais que faire si nous trouvons quelqu'un d'autre dont l'anniversaire est, voyons, 351 00:14:08,760 --> 00:14:10,950 Octobre, Novembre 31 Décembre? 352 00:14:10,950 --> 00:14:12,790 Où est-il ou elle va aller? 353 00:14:12,790 --> 00:14:13,290 Même chose. 354 00:14:13,290 --> 00:14:13,970 Deux étapes bien. 355 00:14:13,970 --> 00:14:15,303 Voilà constante mais est-ce pas? 356 00:14:15,303 --> 00:14:16,360 357 00:14:16,360 --> 00:14:16,860 Bien. 358 00:14:16,860 --> 00:14:17,840 Au moment où il est. 359 00:14:17,840 --> 00:14:20,570 Mais dans le cas général, plus les gens nous ajouter, 360 00:14:20,570 --> 00:14:23,790 probabiliste, nous allons pour obtenir de plus en plus de collisions. 361 00:14:23,790 --> 00:14:26,820 >> Maintenant, cela est un peu mieux parce que techniquement, 362 00:14:26,820 --> 00:14:34,580 maintenant mes chaînes pourraient être en le pire des cas combien de temps? 363 00:14:34,580 --> 00:14:38,890 Si je l'insère n personnes dans cette plus structure de données sophistiqué, n personnes, 364 00:14:38,890 --> 00:14:41,080 dans le pire des cas, il va être n. 365 00:14:41,080 --> 00:14:41,815 Pourquoi? 366 00:14:41,815 --> 00:14:43,332 >> PUBLIC: Parce que si tout le monde a la même date d'anniversaire, 367 00:14:43,332 --> 00:14:44,545 ils vont être une seule ligne. 368 00:14:44,545 --> 00:14:45,420 DAVID Malan: Parfait. 369 00:14:45,420 --> 00:14:47,480 Il pourrait être un peu artificiel, mais vraiment dans le pire des cas, 370 00:14:47,480 --> 00:14:50,117 si tout le monde a la même date d'anniversaire, étant donné les entrées que vous avez, 371 00:14:50,117 --> 00:14:51,950 vous allez avoir un massivement à longue chaîne. 372 00:14:51,950 --> 00:14:54,241 Et oui, vous pourriez appeler un la table de hachage, mais en réalité il est 373 00:14:54,241 --> 00:14:56,810 juste une liste massive liée à beaucoup d'espace perdu. 374 00:14:56,810 --> 00:15:00,460 Mais, en général, si l'on suppose que au moins les anniversaires sont uniform-- 375 00:15:00,460 --> 00:15:01,750 et il est probablement pas. 376 00:15:01,750 --> 00:15:02,587 Je fais cela. 377 00:15:02,587 --> 00:15:04,420 Mais si nous supposons, pour l'intérêt de la discussion 378 00:15:04,420 --> 00:15:07,717 qu'ils sont donc en théorie, si ce est la représentation verticale 379 00:15:07,717 --> 00:15:11,050 du tableau, eh bien nous espérons que vous êtes allez obtenir des chaînes qui sont, vous le savez, 380 00:15:11,050 --> 00:15:15,880 à peu près la même longueur, où chacun des ceux-ci représente un jour du mois. 381 00:15:15,880 --> 00:15:19,930 >> Maintenant, si il ya 31 jours dans le mois, cela signifie que mon temps de marche vraiment 382 00:15:19,930 --> 00:15:25,230 est grand O de n plus de 31, qui se sent mieux que linéaire. 383 00:15:25,230 --> 00:15:27,950 Mais ce qui était un de nos engagements quelques semaines 384 00:15:27,950 --> 00:15:31,145 il ya chaque fois qu'il est venu à exprimer le temps d'exécution d'un algorithme? 385 00:15:31,145 --> 00:15:33,450 386 00:15:33,450 --> 00:15:35,190 Il suffit de regarder seulement le terme d'ordre élevé. 387 00:15:35,190 --> 00:15:35,690 Droit? 388 00:15:35,690 --> 00:15:37,400 31 est certainement utile. 389 00:15:37,400 --> 00:15:39,610 Mais cela est encore grand O de n. 390 00:15:39,610 --> 00:15:41,730 Mais l'un des thèmes de problème mis cinq 391 00:15:41,730 --> 00:15:43,950 va être à absolument reconnaître que, 392 00:15:43,950 --> 00:15:47,320 asymptotiquement, théoriquement cette structure de données 393 00:15:47,320 --> 00:15:50,470 est pas mieux que de simplement une liste massive liée. 394 00:15:50,470 --> 00:15:53,550 Et en effet, dans le pire des cas, cette table de hachage des pourrait dégénérer en cela. 395 00:15:53,550 --> 00:15:57,620 >> Mais dans le monde réel, avec nous, les humains que les propres Mac ou PC ou autre 396 00:15:57,620 --> 00:16:01,240 et sont en cours d'exécution monde réel logiciel sur des données du monde réel, 397 00:16:01,240 --> 00:16:03,260 l'algorithme allez-vous préférer? 398 00:16:03,260 --> 00:16:09,180 Celui qui prend des mesures de fin ou la celui qui prend n divisé par 31 étapes 399 00:16:09,180 --> 00:16:12,900 de trouver un morceau de données ou pour rechercher des informations? 400 00:16:12,900 --> 00:16:16,580 Je veux dire, absolument les 31 marques une différence dans le monde réel. 401 00:16:16,580 --> 00:16:18,540 Il est 31 fois plus rapide. 402 00:16:18,540 --> 00:16:20,880 Et nous, les humains sont certainement aller à apprécier cela. 403 00:16:20,880 --> 00:16:23,004 >> Donc réaliser la dichotomie il entre en fait 404 00:16:23,004 --> 00:16:25,920 parler de choses théoriquement et asymptotiquement qui certainement 405 00:16:25,920 --> 00:16:28,760 a une valeur comme nous l'avons vu, mais dans le monde réel, 406 00:16:28,760 --> 00:16:32,930 si vous vous souciez de simplement faire la heureux humain pour les entrées générales, 407 00:16:32,930 --> 00:16:36,010 vous pourriez très bien vouloir accepter du fait que, oui, cela est linéaire, 408 00:16:36,010 --> 00:16:38,360 mais il est 31 fois plus rapide que linéaire pourrait être. 409 00:16:38,360 --> 00:16:41,610 Et mieux encore, nous ne devons juste faire quelque chose d'arbitraire comme une date de naissance, 410 00:16:41,610 --> 00:16:44,030 nous pourrions passer un peu plus de temps et l'intelligence 411 00:16:44,030 --> 00:16:47,140 et de réfléchir à ce que nous pourrions faire, prénom d'une personne et peut-être 412 00:16:47,140 --> 00:16:50,130 leur date de naissance de combiner ceux ingrédients pour comprendre quelque chose 413 00:16:50,130 --> 00:16:52,720 ce qui est vraiment plus uniforme et moins dentelée, 414 00:16:52,720 --> 00:16:56,250 pour ainsi dire que cette image suggère actuellement, il pourrait être. 415 00:16:56,250 --> 00:16:57,750 Comment pourrions-nous mettre en œuvre dans votre code? 416 00:16:57,750 --> 00:17:00,280 Eh bien, je vous propose que nous juste emprunter une syntaxe que nous avons 417 00:17:00,280 --> 00:17:01,799 utilisé une ou deux fois jusqu'à présent. 418 00:17:01,799 --> 00:17:03,590 Et je vais définir un noeud, qui à nouveau 419 00:17:03,590 --> 00:17:06,812 est un terme générique pour quelques-uns Récipient pour une structure de données. 420 00:17:06,812 --> 00:17:09,020 Je vais proposer que une chaîne va là-dedans. 421 00:17:09,020 --> 00:17:11,369 Mais nous allons commencer à prendre ceux formation roues de maintenant. 422 00:17:11,369 --> 00:17:13,230 >> Plus de librairies CS50 vraiment, sauf si vous voulez 423 00:17:13,230 --> 00:17:15,230 à utiliser pour votre finale projet, ce qui est bien, 424 00:17:15,230 --> 00:17:18,569 mais maintenant nous allons retirer la rideau et dire qu'il est juste une étoile char. 425 00:17:18,569 --> 00:17:22,069 Ainsi, le mot il va être le nom de la personne en question. 426 00:17:22,069 --> 00:17:25,079 Et maintenant, je dois un lien ici au noeud suivant 427 00:17:25,079 --> 00:17:28,170 de sorte que ceux-ci représentent chacun des noeuds 428 00:17:28,170 --> 00:17:30,950 dans la chaîne, éventuellement, d'une liste chaînée. 429 00:17:30,950 --> 00:17:34,090 >> Et maintenant, comment puis-je déclare la table de hachage elle-même? 430 00:17:34,090 --> 00:17:36,660 Comment dois-je déclarer toute cette structure? 431 00:17:36,660 --> 00:17:40,960 Eh bien, vraiment, un peu comme je utilisé un pointeur pour que le premier élément de la liste 432 00:17:40,960 --> 00:17:44,510 avant, de même que je peux dire seulement Je dois juste un tas de pointeurs 433 00:17:44,510 --> 00:17:46,270 de mettre en œuvre toute cette table de hachage. 434 00:17:46,270 --> 00:17:49,484 Je vais avoir un tableau appelé table pour table de hachage. 435 00:17:49,484 --> 00:17:50,900 Ça va être la capacité de taille. 436 00:17:50,900 --> 00:17:52,525 Voilà combien d'éléments peuvent tenir dans ce. 437 00:17:52,525 --> 00:17:56,180 Et chacun de ces éléments dans cette tableau va être une star du nœud. 438 00:17:56,180 --> 00:17:56,810 Pourquoi? 439 00:17:56,810 --> 00:18:00,160 Eh bien, par cette image, ce que je suis mise en œuvre de la table de hachage comme 440 00:18:00,160 --> 00:18:04,330 effectivement au début est juste ce tableau que nous avons tracé verticalement, 441 00:18:04,330 --> 00:18:06,820 dont chacun des carrés représente un pointeur. 442 00:18:06,820 --> 00:18:09,170 Ce ceux qui ont des barres obliques à travers eux sont tout simplement nulle. 443 00:18:09,170 --> 00:18:11,410 Et ceux qui ont flèches allant vers la droite 444 00:18:11,410 --> 00:18:16,140 réels sont des pointeurs vers des noeuds réels, ergo le début d'une liste chaînée. 445 00:18:16,140 --> 00:18:19,050 >> Donc ici, alors, est de savoir comment nous pourrions mettre en œuvre une table de hachage 446 00:18:19,050 --> 00:18:21,580 met en œuvre le chaînage séparé. 447 00:18:21,580 --> 00:18:22,840 Maintenant, pouvons-nous faire mieux? 448 00:18:22,840 --> 00:18:25,632 Très bien, je promis la dernière fois que nous pourrions atteindre la constante de temps. 449 00:18:25,632 --> 00:18:27,381 Et je vous ai donné de genre constante de temps ici, 450 00:18:27,381 --> 00:18:29,850 mais alors dit pas vraiment constante de temps, car il est toujours 451 00:18:29,850 --> 00:18:31,890 dépendant de la somme nombre d'éléments 452 00:18:31,890 --> 00:18:34,500 vous êtes saisie en la structure de données. 453 00:18:34,500 --> 00:18:35,980 Mais supposons que nous avons fait cela. 454 00:18:35,980 --> 00:18:39,550 Permettez-moi de revenir à l'écran ici. 455 00:18:39,550 --> 00:18:44,520 Permettez-moi de ce projet a également ici, clair l'écran, et suppose que je l'ai fait. 456 00:18:44,520 --> 00:18:49,300 Supposons que je voulais insérer le nom Daven dans dans ma structure de données. 457 00:18:49,300 --> 00:18:52,100 >> Je tiens donc à insérer une chaîne Daven dans la structure de données. 458 00:18:52,100 --> 00:18:54,370 Que faire si je ne l'utilise une la table de hachage, mais je l'utilise 459 00:18:54,370 --> 00:18:56,980 quelque chose qui est plus arborescente comme un arbre de la famille, où 460 00:18:56,980 --> 00:18:59,670 vous avez un peu de racine à la nœuds et les feuilles du haut, puis 461 00:18:59,670 --> 00:19:01,440 qui vont vers le bas et vers l'extérieur. 462 00:19:01,440 --> 00:19:04,450 Supposons donc que je vouloir insérer Daven de 463 00:19:04,450 --> 00:19:06,430 dans ce qui est actuellement une liste vide. 464 00:19:06,430 --> 00:19:09,780 Je vais faire ce qui suit: Je suis va créer un noeud dans cette famille 465 00:19:09,780 --> 00:19:15,170 arbre-comme la structure de données qui ressemble un peu comme ça, chacun d'entre eux 466 00:19:15,170 --> 00:19:19,640 rectangles a, disons, pour le moment 26 éléments en elle. 467 00:19:19,640 --> 00:19:21,650 Et chacune des cellules dans ce tableau se passe 468 00:19:21,650 --> 00:19:23,470 pour représenter la lettre d'un alphabet. 469 00:19:23,470 --> 00:19:28,190 >> Plus précisément, je vais traiter ce est A, puis B, puis C, puis D, 470 00:19:28,190 --> 00:19:29,310 celui-ci ici. 471 00:19:29,310 --> 00:19:32,940 Donc, cela va effectivement représenter la lettre D. 472 00:19:32,940 --> 00:19:36,040 Mais à insérer tous Daven de nom, je dois faire un peu plus. 473 00:19:36,040 --> 00:19:37,840 Donc, je vais d'abord hachage, pour ainsi dire. 474 00:19:37,840 --> 00:19:41,049 Je vais regarder à la première lettre dans Daven de ce qui est évidemment un D, 475 00:19:41,049 --> 00:19:42,840 et je vais allouer un noeud qui ressemble 476 00:19:42,840 --> 00:19:45,570 comme this-- un grand rectangle grand suffisante pour répondre à tout l'alphabet. 477 00:19:45,570 --> 00:19:47,140 >> Maintenant D est fait. 478 00:19:47,140 --> 00:19:49,720 Maintenant A. D-A-V-E-N est le but. 479 00:19:49,720 --> 00:19:51,220 Alors maintenant, ce que je vais faire est ce. 480 00:19:51,220 --> 00:19:54,027 Dès que je commençais avis D il n'y a pas là pointeur. 481 00:19:54,027 --> 00:19:56,860 Il est des valeurs parasites pour le moment, ou je pourrais initialiser à null. 482 00:19:56,860 --> 00:19:59,630 Mais permettez-moi de continuer avec cette idée de construire un arbre. 483 00:19:59,630 --> 00:20:04,260 Permettez-moi d'en créer une autre de ces nœuds qui dispose de 26 éléments en elle. 484 00:20:04,260 --> 00:20:05,150 >> Et vous savez quoi? 485 00:20:05,150 --> 00:20:09,130 Si ceci est seulement un noeud dans la mémoire que Je créé avec malloc, en utilisant une structure 486 00:20:09,130 --> 00:20:11,240 comme nous le verrons bientôt, Je vais faire this-- 487 00:20:11,240 --> 00:20:14,450 Je vais tirer une flèche à partir de la chose qui a représenté D vers le bas 488 00:20:14,450 --> 00:20:15,860 à ce nouveau noeud. 489 00:20:15,860 --> 00:20:19,240 Et maintenant, le prochain premier lettre au nom de Daven, 490 00:20:19,240 --> 00:20:24,150 V-- D-A-V-- je vais aller de l'avant et d'en tirer un autre nœud de ce genre, 491 00:20:24,150 --> 00:20:30,150 moyennant quoi, les éléments de V qui, ici, nous tirerons de whoops instance--. 492 00:20:30,150 --> 00:20:31,020 Nous ne serons pas tirer là. 493 00:20:31,020 --> 00:20:31,936 Il va aller ici. 494 00:20:31,936 --> 00:20:32,890 495 00:20:32,890 --> 00:20:35,712 >> Ensuite, nous allons la considèrent comme V. 496 00:20:35,712 --> 00:20:44,920 Et puis ici, nous allons à l'index vers le bas de V dans ce que nous allons examiner E. 497 00:20:44,920 --> 00:20:50,100 Et puis à partir de là, nous allons aller prendre un de ces nœuds ici. 498 00:20:50,100 --> 00:20:52,930 Et maintenant, nous avons une question à répondre. 499 00:20:52,930 --> 00:20:57,840 Je dois en quelque sorte indiquer que nous sommes à la fin de la chaîne Daven. 500 00:20:57,840 --> 00:20:59,490 Donc, je ne pouvais laisser nulle. 501 00:20:59,490 --> 00:21:02,670 >> Mais que faire si nous avons Daven de nom complet aussi, qui 502 00:21:02,670 --> 00:21:04,280 est, comme nous l'avons dit, Davenport? 503 00:21:04,280 --> 00:21:06,970 Alors que faire si Daven est en fait une sous-chaîne, 504 00:21:06,970 --> 00:21:08,960 un préfixe d'une chaîne beaucoup plus longue? 505 00:21:08,960 --> 00:21:11,450 Nous ne pouvons pas en permanence dire rien ne va 506 00:21:11,450 --> 00:21:14,410 d'y aller, parce que nous avons pu jamais insérer un mot comme Davenport 507 00:21:14,410 --> 00:21:15,840 dans cette structure de données 508 00:21:15,840 --> 00:21:19,560 >> Donc, ce que nous pourrions faire à la place est traiter chacun de ces éléments 509 00:21:19,560 --> 00:21:22,170 comme peut-être avoir deux éléments à l'intérieur d'eux. 510 00:21:22,170 --> 00:21:24,810 L'un est un pointeur, en effet, comme je l'ai fait. 511 00:21:24,810 --> 00:21:27,100 Donc, chacun de ces boîtes est non seulement une cellule. 512 00:21:27,100 --> 00:21:29,855 Mais que faire si le haut One-- de celle du bas 513 00:21:29,855 --> 00:21:32,230 va être nul, car il est juste pas encore de Davenport. 514 00:21:32,230 --> 00:21:34,197 Que faire si le haut une est une valeur particulière? 515 00:21:34,197 --> 00:21:36,530 Et ça va être un peu difficile de dessiner cette taille. 516 00:21:36,530 --> 00:21:38,130 Mais supposons qu'il est juste une coche. 517 00:21:38,130 --> 00:21:38,920 Vérifiez. 518 00:21:38,920 --> 00:21:44,230 D-A-V-E-N est une chaîne dans cette structure de données. 519 00:21:44,230 --> 00:21:48,350 >> Pendant ce temps, si je devais plus d'espace ici, je pourrais faire P-O-R-T, 520 00:21:48,350 --> 00:21:52,650 et je pourrais mettre chèque dans le noeud qui comporte la lettre T à la fin. 521 00:21:52,650 --> 00:21:55,460 Donc ceci est un massivement complexe d'aspect structure de données. 522 00:21:55,460 --> 00:21:57,210 Et mon écriture certainement ne pas aider. 523 00:21:57,210 --> 00:22:00,043 Mais si je voulais insérer quelque chose autre, considérons ce que nous ferions. 524 00:22:00,043 --> 00:22:03,370 Si nous voulions mettre David en, nous aimerions suivre la même logique, D-A-V, 525 00:22:03,370 --> 00:22:08,802 mais maintenant je voudrais signaler à la prochaine élément pas de E, mais de I à D. 526 00:22:08,802 --> 00:22:10,760 Donc, il va y avoir plusieurs noeuds dans cet arbre. 527 00:22:10,760 --> 00:22:12,325 Nous allons avoir appel malloc plus. 528 00:22:12,325 --> 00:22:14,700 Mais je ne veux pas faire un désordre complet de cette image. 529 00:22:14,700 --> 00:22:17,710 Donc, nous allons plutôt regarder un qui a été pré-formulés 530 00:22:17,710 --> 00:22:21,810 comme ça avec pas dot, dot, points, mais seulement des tableaux abrégés. 531 00:22:21,810 --> 00:22:23,950 Mais chacun des noeuds dans cet arbre ici 532 00:22:23,950 --> 00:22:26,700 représente le même chose-- un tableau de taille Ray 26. 533 00:22:26,700 --> 00:22:28,860 >> Ou si nous voulons être vraiment bon maintenant, ce 534 00:22:28,860 --> 00:22:30,790 si le nom de quelqu'un que une apostrophe, nous allons 535 00:22:30,790 --> 00:22:35,560 supposer que chaque noeud a fait comme 27 index en elle, non seulement 26. 536 00:22:35,560 --> 00:22:42,020 Donc ce maintenant va être une des données structure appelée trie-- T-R-I-E. 537 00:22:42,020 --> 00:22:46,120 Un trie, qui est censé être historiquement un nom intelligent pour un arbre 538 00:22:46,120 --> 00:22:49,040 qui est optimisé pour l'extraction, ce qui bien sûr, 539 00:22:49,040 --> 00:22:50,870 est écrit avec un I-E il est donc trie. 540 00:22:50,870 --> 00:22:52,710 Mais qui est l'histoire de la Trie. 541 00:22:52,710 --> 00:22:55,860 >> Donc un trie sont ces données arborescente structure comme un arbre généalogique 542 00:22:55,860 --> 00:22:57,510 qui se comporte finalement comme ça. 543 00:22:57,510 --> 00:23:00,890 Et ici est juste un autre exemple de tas ensemble des noms d'autres personnes. 544 00:23:00,890 --> 00:23:03,540 Mais la question maintenant à portée de main est ce que ont 545 00:23:03,540 --> 00:23:08,070 nous avons gagné en introduisant sans doute un plus la structure de données complexe, et une, 546 00:23:08,070 --> 00:23:09,870 franchement, qui utilise beaucoup de mémoire. 547 00:23:09,870 --> 00:23:11,703 >> Parce que même si, pour le moment, je suis seulement 548 00:23:11,703 --> 00:23:15,050 à l'aide de D'pointeur et A et V et Es et Ns, 549 00:23:15,050 --> 00:23:16,700 Je perds un diable de beaucoup de mémoire. 550 00:23:16,700 --> 00:23:18,030 551 00:23:18,030 --> 00:23:22,660 Mais là où je passe une ressource, Je tends à ne regagner un autre. 552 00:23:22,660 --> 00:23:26,020 Donc, si je passe plus d'espace, ce qui est probablement l'espoir? 553 00:23:26,020 --> 00:23:27,407 Que je suis en dépensant moins quoi? 554 00:23:27,407 --> 00:23:28,240 PUBLIC: Moins de temps. 555 00:23:28,240 --> 00:23:28,990 DAVID Malan: le temps. 556 00:23:28,990 --> 00:23:30,320 Maintenant, pourquoi pourrait-il être? 557 00:23:30,320 --> 00:23:33,880 Eh bien, ce qui est l'insertion temps, en termes de grand O maintenant, 558 00:23:33,880 --> 00:23:37,660 d'un nom comme Daven ou Davenport ou David? 559 00:23:37,660 --> 00:23:39,340 Eh bien, Daven était cinq étapes. 560 00:23:39,340 --> 00:23:42,350 Davenport serait neuf étapes, il serait donc un peu plus d'étapes. 561 00:23:42,350 --> 00:23:44,250 David serait cinq étapes ainsi. 562 00:23:44,250 --> 00:23:47,230 Donc, ce sont en béton chiffres, mais il ya sûrement 563 00:23:47,230 --> 00:23:49,550 une limite supérieure de la longueur du nom de quelqu'un. 564 00:23:49,550 --> 00:23:52,240 Et en effet, dans le problème cinq ensembles de spécification, 565 00:23:52,240 --> 00:23:54,050 nous allons proposer qu'il est quelque chose 566 00:23:54,050 --> 00:23:55,470 qui est de 40 caractères certains impairs. 567 00:23:55,470 --> 00:23:58,180 >> En réalité, personne n'a un nom infiniment long, 568 00:23:58,180 --> 00:24:01,542 ce qui veut dire que la longueur d'un nom ou la longueur d'une chaîne nous pourrions 569 00:24:01,542 --> 00:24:03,750 avoir certain de l'état de la structure est sans doute ce que? 570 00:24:03,750 --> 00:24:05,550 571 00:24:05,550 --> 00:24:06,250 Il est constant. 572 00:24:06,250 --> 00:24:06,430 Droit? 573 00:24:06,430 --> 00:24:09,310 Il pourrait être une grande constante comme 40 quelque chose, mais il est constant. 574 00:24:09,310 --> 00:24:13,752 Et il n'a pas de dépendance sur le nombre de d'autres noms sont dans cette structure de données. 575 00:24:13,752 --> 00:24:15,460 En d'autres termes, si je voulu insérer maintenant 576 00:24:15,460 --> 00:24:20,540 Colton ou Gabriel ou Rob ou Zamyla ou Alison ou Belinda ou d'autres noms 577 00:24:20,540 --> 00:24:23,940 du personnel dans ces données la structure, est le temps d'exécution 578 00:24:23,940 --> 00:24:26,750 d'insérer d'autres noms va être tout un impact 579 00:24:26,750 --> 00:24:30,220 par combien d'autres éléments sont dans la structure de données déjà? 580 00:24:30,220 --> 00:24:31,040 Ce ne est pas. 581 00:24:31,040 --> 00:24:31,540 Droit? 582 00:24:31,540 --> 00:24:36,150 Parce que nous sommes effectivement en utilisant cette table de hachage multi-couche. 583 00:24:36,150 --> 00:24:38,280 Et le temps d'exécution de l'une de ces opérations 584 00:24:38,280 --> 00:24:41,510 dépend pas du nombre de les éléments qui se trouvent dans la structure de données 585 00:24:41,510 --> 00:24:43,090 ou qui vont éventuellement comme dans la structure de données, 586 00:24:43,090 --> 00:24:44,714 mais sur la longueur de ce particulier? 587 00:24:44,714 --> 00:24:46,500 588 00:24:46,500 --> 00:24:49,200 >> La chaîne étant inséré, qui ne fait 589 00:24:49,200 --> 00:24:52,580 cette asymptotiquement constant Big O time-- d'un. 590 00:24:52,580 --> 00:24:54,720 Et franchement, tout en le monde réel, cette 591 00:24:54,720 --> 00:24:58,380 signifie inscrivant le nom de Daven prend comme cinq étapes, ou Davenport neuf 592 00:24:58,380 --> 00:25:00,100 étapes, ou David cinq étapes. 593 00:25:00,100 --> 00:25:03,071 Voilà sacrément petits temps de fonctionnement. 594 00:25:03,071 --> 00:25:05,320 Et, en effet, que est une très bonne chose, surtout quand 595 00:25:05,320 --> 00:25:08,126 il est indépendant de la totale nombre d'éléments de là. 596 00:25:08,126 --> 00:25:10,500 Alors, comment pouvons-nous mettre en œuvre ce type de structure dans le code? 597 00:25:10,500 --> 00:25:12,900 Il est un peu plus complexe, mais encore il est 598 00:25:12,900 --> 00:25:15,050 juste une demande de blocs de construction de base. 599 00:25:15,050 --> 00:25:17,830 Je vais à redéfinir nœud nous comme suit: 600 00:25:17,830 --> 00:25:21,100 bool appelé word-- et ce l'on pourrait appeler quelque chose. 601 00:25:21,100 --> 00:25:23,970 Mais le bool représente ce que je dessinais comme une coche. 602 00:25:23,970 --> 00:25:24,490 Oui. 603 00:25:24,490 --> 00:25:26,720 Ceci est la fin d'une chaîne dans cette structure de données. 604 00:25:26,720 --> 00:25:30,702 >> Et, bien sûr, la star de noeud il se réfère à des enfants. 605 00:25:30,702 --> 00:25:32,410 Et, en effet, comme Just un arbre généalogique, vous 606 00:25:32,410 --> 00:25:34,370 examinerait les nœuds qui pendait 607 00:25:34,370 --> 00:25:36,920 du fond d'un parent élément d'être des enfants. 608 00:25:36,920 --> 00:25:40,510 Et si les enfants va être un tableau de 27, 27 un 609 00:25:40,510 --> 00:25:41,680 juste pour être apostrophe. 610 00:25:41,680 --> 00:25:43,390 Nous allons trier de cas particulier que. 611 00:25:43,390 --> 00:25:45,400 Ainsi, vous pouvez avoir certains noms avec des apostrophes. 612 00:25:45,400 --> 00:25:47,399 Peut-être même trait d'union devrait aller là-bas, mais vous allez 613 00:25:47,399 --> 00:25:50,330 voir en p 5 ensemble nous de soins seulement les lettres et les apostrophes. 614 00:25:50,330 --> 00:25:52,990 >> Et puis, comment voulez-vous représentez la structure elle-même de données? 615 00:25:52,990 --> 00:25:56,454 Comment représentez-vous la racine de ce trie, pour ainsi dire? 616 00:25:56,454 --> 00:25:59,620 Eh bien, tout comme avec une liste chaînée, vous besoin d'un pointeur sur le premier élément. 617 00:25:59,620 --> 00:26:04,270 Avec un trie vous avez juste besoin d'un pointeur vers la racine de cette trie. 618 00:26:04,270 --> 00:26:07,290 Et à partir de là, vous pouvez hacher votre chemin vers le bas profond et plus profond 619 00:26:07,290 --> 00:26:10,460 pour chaque autre noeud dans la structure. 620 00:26:10,460 --> 00:26:13,440 Donc, tout simplement avec cette boîte nous représentons que struct. 621 00:26:13,440 --> 00:26:15,877 >> Maintenant Meanwhile-- Oh, question. 622 00:26:15,877 --> 00:26:17,220 >> Public: Quel est le mot de bool? 623 00:26:17,220 --> 00:26:20,490 >> DAVID Malan: mot de Bool est juste cette incarnation C 624 00:26:20,490 --> 00:26:22,920 de ce que je décrivais dans cette boîte ici, quand 625 00:26:22,920 --> 00:26:26,000 Je commencé à diviser chacune des Les éléments de tableau en deux morceaux. 626 00:26:26,000 --> 00:26:27,600 L'un est un pointeur vers le noeud suivant. 627 00:26:27,600 --> 00:26:30,280 L'autre doit être quelque chose comme une case à cocher 628 00:26:30,280 --> 00:26:33,770 de dire oui, il ya une Daven mot qui se termine ici, 629 00:26:33,770 --> 00:26:35,610 parce que nous ne voulons pas, pour le moment, Dave. 630 00:26:35,610 --> 00:26:39,320 >> Même si Dave va être un mot légitime, il est pas dans le trie 631 00:26:39,320 --> 00:26:39,830 encore. 632 00:26:39,830 --> 00:26:40,950 Et D est pas un mot. 633 00:26:40,950 --> 00:26:42,770 Et D-A est pas un mot ou un nom. 634 00:26:42,770 --> 00:26:45,020 Donc le coche indique seulement une fois que vous 635 00:26:45,020 --> 00:26:48,190 frappé ce nœud est la la trajectoire précédente de caractères 636 00:26:48,190 --> 00:26:50,700 fait une chaîne que vous avez inséré. 637 00:26:50,700 --> 00:26:53,660 Voilà donc tout le bool il est fait pour nous. 638 00:26:53,660 --> 00:26:55,500 >> D'autres questions sur essais? 639 00:26:55,500 --> 00:26:56,215 Ouais. 640 00:26:56,215 --> 00:26:58,035 >> Public: Quel est le chevauchement? 641 00:26:58,035 --> 00:26:59,945 Que faire si vous avez un Dave et Daven? 642 00:26:59,945 --> 00:27:00,820 DAVID Malan: Parfait. 643 00:27:00,820 --> 00:27:02,580 Que faire si vous avez un Dave et Daven? 644 00:27:02,580 --> 00:27:06,240 Donc, si nous insérons, dire un surnom, pour David-- Dave-- D-A-V-E? 645 00:27:06,240 --> 00:27:07,370 646 00:27:07,370 --> 00:27:08,700 Ceci est en fait super simple. 647 00:27:08,700 --> 00:27:10,325 Donc, nous allons seulement prendre quatre mesures. 648 00:27:10,325 --> 00:27:11,042 649 00:27:11,042 --> 00:27:15,847 D-A-V-E. Et qu'est-ce que je dois faire une fois que je frappe quatrième nœud? 650 00:27:15,847 --> 00:27:16,680 Tout va vérifier. 651 00:27:16,680 --> 00:27:18,000 Nous sommes déjà à partir. 652 00:27:18,000 --> 00:27:18,840 Terminé. 653 00:27:18,840 --> 00:27:19,750 Quatre étapes. 654 00:27:19,750 --> 00:27:21,590 Constante de temps asymptotiquement. 655 00:27:21,590 --> 00:27:26,300 Et maintenant, nous avons indiqué que les deux Dave et Daven sont des chaînes dans la structure. 656 00:27:26,300 --> 00:27:27,710 Donc, pas de problème. 657 00:27:27,710 --> 00:27:30,200 Et remarquez comment la présence Daven de ne pas faire 658 00:27:30,200 --> 00:27:34,750 prendre plus de temps ou moins temps pour Dave et vice versa. 659 00:27:34,750 --> 00:27:36,000 >> Alors, que pouvons-nous faire maintenant? 660 00:27:36,000 --> 00:27:40,680 Nous avons utilisé cette métaphore avant de plateaux représenter quelque chose. 661 00:27:40,680 --> 00:27:43,380 Mais il se trouve que pile de plateaux est en fait 662 00:27:43,380 --> 00:27:47,187 démonstratif d'un autre données abstrait bien-- une structure de données de niveau supérieur 663 00:27:47,187 --> 00:27:49,770 qu'à la fin de la journée est juste comme un tableau ou une liste chaînée 664 00:27:49,770 --> 00:27:50,970 ou quelque chose de plus banal. 665 00:27:50,970 --> 00:27:53,270 Mais il est un plus intéressant concept conceptuel. 666 00:27:53,270 --> 00:27:56,440 Une pile, comme ces plateaux ici à Mather, 667 00:27:56,440 --> 00:27:58,750 sont généralement appelés that-- juste une pile. 668 00:27:58,750 --> 00:28:02,540 >> Et dans ce type de structure de données vous avez deux operations-- 669 00:28:02,540 --> 00:28:05,880 vous avez un appelé poussée pour ajouter quelque chose à la pile, 670 00:28:05,880 --> 00:28:08,320 comme mettre un autre bac dos sur le dessus de la pile. 671 00:28:08,320 --> 00:28:11,350 Et puis pop, qui signifie que vous prendre la plus haute plateau éteint. 672 00:28:11,350 --> 00:28:16,210 Mais ce qui est essentiel sur une pile est que il a cette curieuse particularité. 673 00:28:16,210 --> 00:28:19,560 Comme le personnel de la salle de la salle sont réorganisant les plateaux pour le prochain repas, 674 00:28:19,560 --> 00:28:21,380 ce qui va être vrai sur la façon dont les étudiants 675 00:28:21,380 --> 00:28:22,856 interagir avec cette structure de données? 676 00:28:22,856 --> 00:28:24,480 PUBLIC: Ils vont à la pop un arrêt. 677 00:28:24,480 --> 00:28:26,550 DAVID Malan: Ils vont un pop off, nous espérons que le haut. 678 00:28:26,550 --> 00:28:28,910 Sinon, il est juste un peu stupide aller tout le chemin vers le bas. 679 00:28:28,910 --> 00:28:29,070 Droit? 680 00:28:29,070 --> 00:28:31,620 La structure de données ne permet pas vraiment vous prenez le plateau inférieur d'au moins 681 00:28:31,620 --> 00:28:32,520 facilement. 682 00:28:32,520 --> 00:28:35,040 Il ya donc ce curieux propriété à une pile 683 00:28:35,040 --> 00:28:39,730 que le dernier élément est va être le premier à sortir. 684 00:28:39,730 --> 00:28:43,400 Et les informaticiens appellent ce LIFO-- dernier entré, premier sorti. 685 00:28:43,400 --> 00:28:45,540 Et il n'a fait applications intéressantes. 686 00:28:45,540 --> 00:28:50,090 Il est pas nécessairement aussi évident que certains d'autres, mais il peut, en effet, être utile, 687 00:28:50,090 --> 00:28:54,040 et il peut, en effet, être mis en œuvre dans un couple de différentes manières. 688 00:28:54,040 --> 00:28:58,550 >> Donc un, et effectivement, laisser moi de ne pas plonger dans cela. 689 00:28:58,550 --> 00:28:59,860 Faisons-le à la place. 690 00:28:59,860 --> 00:29:03,700 Regardons un qui est presque la même idée, mais il est un peu plus juste. 691 00:29:03,700 --> 00:29:04,200 Droit? 692 00:29:04,200 --> 00:29:07,560 Si vous êtes l'un de ces garçons de ventilateur ou les filles qui aime vraiment les produits Apple 693 00:29:07,560 --> 00:29:10,130 et vous vous êtes réveillé à 3h00 faire la queue devant certains magasins 694 00:29:10,130 --> 00:29:14,150 pour obtenir la toute dernière iPhone, vous aurait fait la queue comme ça. 695 00:29:14,150 --> 00:29:15,800 >> Maintenant, une file d'attente est très délibérément nommé. 696 00:29:15,800 --> 00:29:18,190 Il ya une ligne parce qu'il ya une certaine équité à elle. 697 00:29:18,190 --> 00:29:18,690 Droit? 698 00:29:18,690 --> 00:29:21,690 Il genre de sucer si vous avez il a obtenu la première sur l'Apple Store 699 00:29:21,690 --> 00:29:25,700 mais vous êtes effectivement la plus basse plateau parce que les employés d'Apple puis 700 00:29:25,700 --> 00:29:28,189 pop de la dernière personne qui effectivement obtenu en ligne. 701 00:29:28,189 --> 00:29:31,230 Donc, les piles et les files d'attente, même si fonctionnellement ils sont un genre de la same-- 702 00:29:31,230 --> 00:29:33,105 il est juste cette collection des ressources qui est 703 00:29:33,105 --> 00:29:36,210 va croître et il ya shrink-- cet aspect de l'équité à elle, 704 00:29:36,210 --> 00:29:39,634 au moins dans le monde réel, où les opérations que vous exercer 705 00:29:39,634 --> 00:29:40,800 sont fondamentalement différentes. 706 00:29:40,800 --> 00:29:43,360 Un stack-- une file d'attente rather-- est dit avoir 707 00:29:43,360 --> 00:29:45,320 deux opérations: n files d'attente et d file d'attente. 708 00:29:45,320 --> 00:29:46,341 709 00:29:46,341 --> 00:29:48,090 Ou vous pouvez les appeler un certain nombre de choses. 710 00:29:48,090 --> 00:29:50,770 Mais vous voulez juste saisir l'idée que l'on est d'ajouter 711 00:29:50,770 --> 00:29:53,230 et on est en fin de compte la soustraction. 712 00:29:53,230 --> 00:29:58,840 >> Maintenant, sous le capot, à la fois la pile et une file d'attente pourrait être mise en œuvre, comment? 713 00:29:58,840 --> 00:30:01,390 Nous ne rentrerons pas dans le code de parce que le niveau supérieur 714 00:30:01,390 --> 00:30:03,387 idée est une sorte de plus évident. 715 00:30:03,387 --> 00:30:04,470 Je veux dire, ce que font les humains? 716 00:30:04,470 --> 00:30:07,030 Si je suis la première personne à Apple Stocker et ceci est la porte d'entrée, 717 00:30:07,030 --> 00:30:08,130 vous savez, je vais rester ici. 718 00:30:08,130 --> 00:30:09,750 Et de l'autre personne va rester ici. 719 00:30:09,750 --> 00:30:11,500 Et de l'autre personne va rester ici. 720 00:30:11,500 --> 00:30:13,792 Alors quelle est la structure de données se prête à une file d'attente? 721 00:30:13,792 --> 00:30:14,542 >> PUBLIC: Une file d'attente. 722 00:30:14,542 --> 00:30:15,667 DAVID Malan: Eh bien, une file d'attente. 723 00:30:15,667 --> 00:30:16,390 Bien sûr. 724 00:30:16,390 --> 00:30:16,920 Quoi d'autre? 725 00:30:16,920 --> 00:30:17,600 >> PUBLIC: Une liste chaînée. 726 00:30:17,600 --> 00:30:18,990 >> DAVID Malan: A liée la liste que vous pourriez mettre en œuvre. 727 00:30:18,990 --> 00:30:22,500 Et une liste chaînée est agréable car alors il peut atteindre une longueur arbitraire, par opposition 728 00:30:22,500 --> 00:30:24,880 à avoir un certain nombre fixe de personnes dans le magasin. 729 00:30:24,880 --> 00:30:27,030 Mais peut-être un nombre fixe des lieux est légitime. 730 00:30:27,030 --> 00:30:30,350 Parce que si ils ont seulement comme 20 iPhones le premier jour, peut-être 731 00:30:30,350 --> 00:30:33,930 ils ont seulement besoin d'un tableau de taille 20 pour représenter cette file d'attente, qui 732 00:30:33,930 --> 00:30:37,070 est seulement de dire maintenant une fois que nous commençons à parler au sujet de ces problèmes de plus haut niveau, 733 00:30:37,070 --> 00:30:38,890 vous pouvez mettre en œuvre dans un certain nombre de façons. 734 00:30:38,890 --> 00:30:42,030 Et il est probablement juste aller à être un compromis dans l'espace et le temps 735 00:30:42,030 --> 00:30:43,950 ou tout simplement dans votre propre complexité du code. 736 00:30:43,950 --> 00:30:45,380 >> Qu'en est-il une pile? 737 00:30:45,380 --> 00:30:48,190 Eh bien, une pile, nous avons vu trop peuvent être tout simplement ces plateaux. 738 00:30:48,190 --> 00:30:50,007 Et vous pourriez mettre en œuvre ce un tableau. 739 00:30:50,007 --> 00:30:53,090 Mais à un moment donné si vous utilisez un tableau, ce qui va se passer pour les plateaux 740 00:30:53,090 --> 00:30:54,173 vous essayez de mettre bas? 741 00:30:54,173 --> 00:30:55,170 742 00:30:55,170 --> 00:30:55,670 Bien. 743 00:30:55,670 --> 00:30:57,490 Vous allez seulement être capable d'aller si haut. 744 00:30:57,490 --> 00:31:00,156 Et je pense que dans Mather ils sont en fait en retrait dans cette ouverture. 745 00:31:00,156 --> 00:31:01,950 Donc, en effet, il est presque comme Mather utilise 746 00:31:01,950 --> 00:31:03,783 une matrice de taille fixe, parce que vous ne pouvez 747 00:31:03,783 --> 00:31:08,302 adapter tant de plateaux dans cette ouverture en le mur en bas des genoux des gens. 748 00:31:08,302 --> 00:31:10,010 Et que peut-être dit être un tableau, 749 00:31:10,010 --> 00:31:14,300 mais nous pourrions certainement mettre en œuvre que plus généralement avec une liste chaînée. 750 00:31:14,300 --> 00:31:16,390 >> Eh bien, qu'en est-il une autre structure de données? 751 00:31:16,390 --> 00:31:18,760 Permettez-moi de tirer vers le haut un autre visuel ici. 752 00:31:18,760 --> 00:31:24,710 Quelque chose comme diriez-vous celui-là? 753 00:31:24,710 --> 00:31:28,920 Pourquoi serait-il utile d'avoir pas quelque chose d'aussi chic que un trie, qui 754 00:31:28,920 --> 00:31:32,370 nous avons vu ces avions nœuds très larges, chacun d'eux est dans un tableau? 755 00:31:32,370 --> 00:31:35,740 Mais si nous faisons quelque chose de plus simplement, comme un vieil arbre de la famille de l'école, 756 00:31:35,740 --> 00:31:38,110 dont chacun des nœuds ici est juste stocker un nombre. 757 00:31:38,110 --> 00:31:42,180 Au lieu d'un nom ou d'un descendant est juste stocker un certain nombre de ce genre. 758 00:31:42,180 --> 00:31:45,250 >> Eh bien, le jargon que nous utilisons dans structures de données est à la fois essais 759 00:31:45,250 --> 00:31:49,510 et les arbres, où un trie, de nouveau, est juste un dont les noeuds sont des tableaux, 760 00:31:49,510 --> 00:31:51,680 est toujours ce que vous pourriez utiliser de l'école primaire 761 00:31:51,680 --> 00:31:53,860 quand vous avez fait une famille feuilles tree-- et la racine 762 00:31:53,860 --> 00:31:57,250 de l'arbre et les enfants de la mère et leurs frères et sœurs. 763 00:31:57,250 --> 00:32:03,670 Et nous pourrions mettre en place un arbre, par exemple, le plus simplement ce produit. 764 00:32:03,670 --> 00:32:07,420 Un arbre, si ce noeud en tant que l'un des ces cercles qui a un certain nombre, 765 00:32:07,420 --> 00:32:09,947 il ne va pas avoir un pointeur, mais deux. 766 00:32:09,947 --> 00:32:11,780 Et dès que vous ajoutez un second pointeur, vous 767 00:32:11,780 --> 00:32:13,905 peut effectivement maintenant prendre de la sorte de données à deux dimensions 768 00:32:13,905 --> 00:32:14,780 structures de mémoire. 769 00:32:14,780 --> 00:32:16,660 Tout comme un bidimensionnelle tableau, vous pouvez 770 00:32:16,660 --> 00:32:18,904 avoir de genre en deux dimensions listes liées, mais les 771 00:32:18,904 --> 00:32:20,820 qui suivent un motif où il n'y a pas de cycles. 772 00:32:20,820 --> 00:32:24,487 Il est vraiment un arbre avec un façon grand-parent ici et ensuite 773 00:32:24,487 --> 00:32:27,320 certains parents et enfants et petits-enfants et arrières petits-enfants. 774 00:32:27,320 --> 00:32:28,370 et ainsi de suite. 775 00:32:28,370 --> 00:32:32,390 >> Mais ce qui est vraiment bien à ce sujet aussi, juste pour vous taquiner avec un peu de code, 776 00:32:32,390 --> 00:32:35,370 rappel de la récursivité quelque temps en arrière, où 777 00:32:35,370 --> 00:32:38,220 vous écrivez une fonction qui se dit. 778 00:32:38,220 --> 00:32:41,140 Ceci est une belle occasion à mettre en oeuvre quelque chose 779 00:32:41,140 --> 00:32:42,920 comme la récursivité, car en tenir compte. 780 00:32:42,920 --> 00:32:43,860 >> Ceci est un arbre. 781 00:32:43,860 --> 00:32:48,040 Et je suis un peu anal avec la façon dont Je mets les nombres entiers dans la rue. 782 00:32:48,040 --> 00:32:51,020 Tant et si bien qu'il a un spécial name-- un arbre binaire de recherche. 783 00:32:51,020 --> 00:32:53,460 Maintenant, nous avons entendu parler de binaire recherche, mais pouvez-vous 784 00:32:53,460 --> 00:32:55,180 travailler à rebours à partir du nom de cette chose? 785 00:32:55,180 --> 00:32:59,280 Quel est le modèle de la façon dont je inséré les entiers dans cet arbre? 786 00:32:59,280 --> 00:33:00,696 Il est pas arbitraire. 787 00:33:00,696 --> 00:33:01,570 Il ya un certain modèle. 788 00:33:01,570 --> 00:33:02,090 Ouais. 789 00:33:02,090 --> 00:33:03,370 >> PUBLIC: Les plus petits sur la gauche. 790 00:33:03,370 --> 00:33:03,690 >> DAVID Malan: Ouais. 791 00:33:03,690 --> 00:33:05,062 Les plus petits sont sur la gauche. 792 00:33:05,062 --> 00:33:06,270 Les plus grands sont sur la droite. 793 00:33:06,270 --> 00:33:12,940 De telle sorte qu'une véritable déclaration est un parent est supérieure à sa fille gauche, 794 00:33:12,940 --> 00:33:14,850 mais moins que son enfant droit. 795 00:33:14,850 --> 00:33:17,750 Et que seul est même un définition verbale récursive 796 00:33:17,750 --> 00:33:20,500 parce que vous pouvez appliquer cette même à chaque noeud logique 797 00:33:20,500 --> 00:33:23,080 et il ne fond sur un scénario de base si vous 798 00:33:23,080 --> 00:33:25,740 volonté, lorsque vous appuyez sur l'un des les feuilles, pour ainsi dire, 799 00:33:25,740 --> 00:33:28,580 où un congé a plus aucun enfant. 800 00:33:28,580 --> 00:33:30,614 >> Maintenant, comment pouvez-vous trouver le numéro 44? 801 00:33:30,614 --> 00:33:32,280 Vous voulez commencer à la racine et dire, hm. 802 00:33:32,280 --> 00:33:35,690 55 est donc 44 pas ce que je veux aller droit ou ce que je veux aller à gauche? 803 00:33:35,690 --> 00:33:37,190 Eh bien, évidemment, vous voulez aller à gauche. 804 00:33:37,190 --> 00:33:40,060 Et il est juste comme le téléphone livre par exemple à la recherche binaire 805 00:33:40,060 --> 00:33:41,099 plus généralement. 806 00:33:41,099 --> 00:33:43,390 Mais nous mettons en œuvre ce maintenant un peu plus dynamique 807 00:33:43,390 --> 00:33:45,339 qu'un tableau pourrait permettre. 808 00:33:45,339 --> 00:33:48,130 Et en fait, si vous voulez regarder au code, au premier coup d'œil sûr. 809 00:33:48,130 --> 00:33:49,671 Il ressemble à un tas de lignes. 810 00:33:49,671 --> 00:33:51,220 Mais il est magnifiquement simple. 811 00:33:51,220 --> 00:33:54,490 Si vous souhaitez mettre en place une fonction recherche appelé dont le but dans la vie 812 00:33:54,490 --> 00:33:57,290 est de rechercher une valeur comme n, un entier, 813 00:33:57,290 --> 00:34:01,756 et vous êtes passé dans un un pointer-- un pointeur vers le noeud de la racine, 814 00:34:01,756 --> 00:34:04,380 plutôt, de cet arbre à partir de laquelle vous pouvez accéder à tout le reste, 815 00:34:04,380 --> 00:34:08,850 remarquez comment carrément vous pouvez mettre en œuvre la logique. 816 00:34:08,850 --> 00:34:10,880 Si l'arbre est nulle, il est évidemment pas là. 817 00:34:10,880 --> 00:34:11,880 Disons simplement return false. 818 00:34:11,880 --> 00:34:12,000 Droit? 819 00:34:12,000 --> 00:34:14,040 Si vous le remettez rien, il n'y a rien. 820 00:34:14,040 --> 00:34:17,900 >> Sinon, si n est inférieur à arbre flèche, flèche n- maintenant n, 821 00:34:17,900 --> 00:34:20,670 rappelons nous avons introduit de super brièvement l'autre jour, 822 00:34:20,670 --> 00:34:25,100 et cela signifie simplement de référence du pointeur et examinez le champ appelé n. 823 00:34:25,100 --> 00:34:27,690 Donc, cela signifie qu'il va et regarder le champ appelé n. 824 00:34:27,690 --> 00:34:33,810 Donc, si n, la valeur que vous avez donné, est moins que la valeur du nombre entier d'arbres, 825 00:34:33,810 --> 00:34:35,449 où voulez-vous aller? 826 00:34:35,449 --> 00:34:36,389 À gauche. 827 00:34:36,389 --> 00:34:37,780 >> Donc remarquer la récursivité. 828 00:34:37,780 --> 00:34:39,860 Je returning-- pas vrai. 829 00:34:39,860 --> 00:34:40,989 Pas faux. 830 00:34:40,989 --> 00:34:45,670 Je retourne quelle que soit la réponse est par un appel à moi-même, en passant 831 00:34:45,670 --> 00:34:50,100 un n nouveau, ce qui est redondant, mais ce qui est légèrement différent maintenant? 832 00:34:50,100 --> 00:34:51,989 Comment vais-je faire le plus petit problème? 833 00:34:51,989 --> 00:34:54,920 Je suis de passage dans le deuxième l'argument, pas la racine de l'arbre, 834 00:34:54,920 --> 00:34:59,616 mais l'enfant gauche dans ce cas. 835 00:34:59,616 --> 00:35:00,990 Donc, je suis de passage à l'enfant gauche. 836 00:35:00,990 --> 00:35:04,720 >> Pendant ce temps, si n est plus grand que le noeud je suis en train de regarder, 837 00:35:04,720 --> 00:35:06,690 Je cherche le côté droit. 838 00:35:06,690 --> 00:35:10,880 Sinon, si l'arbre est non nulle, et si l'élément est pas à gauche 839 00:35:10,880 --> 00:35:13,240 et il ne veut pas le droit, ce qui est merveilleusement le cas? 840 00:35:13,240 --> 00:35:14,630 841 00:35:14,630 --> 00:35:18,440 Nous avons effectivement trouvé le nœud question, et si nous revenons vrai. 842 00:35:18,440 --> 00:35:21,490 >> Donc, nous avons juste effleuré la surface maintenant une partie de ces structures de données. 843 00:35:21,490 --> 00:35:24,370 En problème réglé cinq vous aurez explorer ces encore plus loin, 844 00:35:24,370 --> 00:35:27,250 et vous recevrez votre conception choix de la façon d'aller à ce sujet. 845 00:35:27,250 --> 00:35:30,250 Ce que je voudrais conclure sur est juste un deuxième teaser de 30 846 00:35:30,250 --> 00:35:32,080 de ce qui attend la semaine prochaine et au-delà. 847 00:35:32,080 --> 00:35:35,390 >> Comme nous begin-- heureusement que vous pourriez think-- notre transition lentement 848 00:35:35,390 --> 00:35:38,680 à partir de l'univers de C et inférieure les détails d'implémentation de niveau, 849 00:35:38,680 --> 00:35:42,090 à un monde dans lequel nous pouvons prendre pour acquis que quelqu'un d'autre a finalement 850 00:35:42,090 --> 00:35:44,010 mise en œuvre de ces données structures pour nous, 851 00:35:44,010 --> 00:35:47,570 et nous allons commencer à comprendre la signifie monde réel de la mise en œuvre 852 00:35:47,570 --> 00:35:50,560 programmes basés sur le Web et plus généralement sites 853 00:35:50,560 --> 00:35:52,910 et aussi la sécurité très implications que nous avons seulement 854 00:35:52,910 --> 00:35:54,850 commencé à gratter la surface de. 855 00:35:54,850 --> 00:35:57,320 Voici ce qui nous attend dans les jours à venir. 856 00:35:57,320 --> 00:36:00,480 >> [VIDEO LECTURE] 857 00:36:00,480 --> 00:36:03,432 858 00:36:03,432 --> 00:36:12,780 >> -Il Est venu avec un message, avec un protocole qui lui est propre. 859 00:36:12,780 --> 00:36:26,110 860 00:36:26,110 --> 00:36:30,894 Il est venu à un monde cruel pare-feu, routeurs indifférents, 861 00:36:30,894 --> 00:36:33,368 et les dangers bien pires que la mort. 862 00:36:33,368 --> 00:36:35,280 863 00:36:35,280 --> 00:36:36,236 Il est rapide. 864 00:36:36,236 --> 00:36:37,980 Il est fort. 865 00:36:37,980 --> 00:36:42,830 Il est TCP / IP, et il a votre adresse. 866 00:36:42,830 --> 00:36:45,290 867 00:36:45,290 --> 00:36:48,074 "Warriors of the Net". 868 00:36:48,074 --> 00:36:49,660 [FIN LECTURE VIDÉO] 869 00:36:49,660 --> 00:36:50,910 DAVID Malan: La semaine prochaine. 870 00:36:50,910 --> 00:36:51,880 Nous vous verrons ensuite. 871 00:36:51,880 --> 00:36:54,615 872 00:36:54,615 --> 00:36:56,060 [VIDEO LECTURE] 873 00:36:56,060 --> 00:36:59,240 -Et Maintenant, "pensées profondes" par Daven Farnham. 874 00:36:59,240 --> 00:37:02,030 875 00:37:02,030 --> 00:37:05,820 -David Commence toujours conférences avec, "Très bien." 876 00:37:05,820 --> 00:37:08,750 Pourquoi pas: «Voici la solution de problème de jeu "de cette semaine 877 00:37:08,750 --> 00:37:12,180 ou "Nous donnons tous un A?" 878 00:37:12,180 --> 00:37:13,380 [Rire] 879 00:37:13,380 --> 00:37:15,530 [FIN LECTURE VIDÉO]