1 00:00:00,000 --> 00:00:11,460 2 00:00:11,460 --> 00:00:12,250 >> DAVID MALAN: Très bien. 3 00:00:12,250 --> 00:00:13,860 Bienvenue à CS50. 4 00:00:13,860 --> 00:00:16,190 C'est le début de la semaine 8. 5 00:00:16,190 --> 00:00:21,320 Et rappelons que problème posé 5 terminée avec un peu d'un défi. 6 00:00:21,320 --> 00:00:25,210 Donc, en supposant que vous avez récupéré tout votre Les boursiers de l'enseignement et des photographies de CA 7 00:00:25,210 --> 00:00:30,480 dans le fichier card.raw, vous êtes admissible maintenant trouver tous ces gens, et 8 00:00:30,480 --> 00:00:34,510 Un heureux gagnant marcher jusqu'à la maison avec une de ces choses, le mouvement de saut 9 00:00:34,510 --> 00:00:37,450 appareil que vous pouvez utiliser pour finale projets, par exemple. 10 00:00:37,450 --> 00:00:39,860 >> Ceci, chaque année, conduit à un peu de frayeurs. 11 00:00:39,860 --> 00:00:43,480 Et donc ce que je pensais faire est de partager avec vous quelques-unes des notes qui ont 12 00:00:43,480 --> 00:00:47,370 allé en arrière sur la liste du personnel de la fin. 13 00:00:47,370 --> 00:00:51,110 Par exemple, hier soir, citation unquote, à partir de l'un des employés 14 00:00:51,110 --> 00:00:55,000 membres: «Je viens d'avoir un coup d'étudiant à ma porte pour prendre une photo avec moi. 15 00:00:55,000 --> 00:00:59,020 Stalkers, je vous dis. "Commencé assez descriptive et puis nous avons déménagé 16 00:00:59,020 --> 00:01:02,830 à une heure ou deux plus tard: «J'ai eu une étudiant qui m'attendait après l'article 17 00:01:02,830 --> 00:01:06,080 et il avait tous nos noms et photos sur quelques feuilles de papier. "Très bien. 18 00:01:06,080 --> 00:01:09,230 Alors organisé, mais pas tout ce qui pourtant rampant. 19 00:01:09,230 --> 00:01:12,520 >> Puis: «J'étais hors de la ville ce week-end, et quand je suis rentré, il y en avait un dans 20 00:01:12,520 --> 00:01:12,630 ma 21 00:01:12,630 --> 00:01:16,740 chambre à coucher. "[rires] 22 00:01:16,740 --> 00:01:20,410 DAVID MALAN: citation suivante d'un personnel membre », un étudiant est venu à ma maison à 23 00:01:20,410 --> 00:01:25,330 Somerville à 4 heures ce matin. "Next personnel, "je suis arrivé à mon hôtel à San 24 00:01:25,330 --> 00:01:30,016 Francisco et un étudiant attendait me dans le hall avec trois reflex numériques ". 25 00:01:30,016 --> 00:01:31,510 Type d'appareil. 26 00:01:31,510 --> 00:01:34,980 «Je ne suis même pas sur le personnel de ce semestre, mais un étudiant fait irruption dans ma maison ce 27 00:01:34,980 --> 00:01:40,480 matin et enregistré le tout avec Google Glass. "Et puis enfin, 28 00:01:40,480 --> 00:01:43,650 "Au moins 12 personnes ont été avidement en attendant pour moi quand je suis sorti de mon 29 00:01:43,650 --> 00:01:44,800 limousine, puis je 30 00:01:44,800 --> 00:01:46,970 réveillé. "Très bien. 31 00:01:46,970 --> 00:01:57,690 Donc, parmi les photographies, comme vous pouvez rappelons-le, sont cet homme là, qui vous 32 00:01:57,690 --> 00:02:01,850 pourrait savoir que Milo Banana, qui vit avec Lauren Carvalho, notre tête 33 00:02:01,850 --> 00:02:02,905 enseignement Fellow. 34 00:02:02,905 --> 00:02:05,170 Milo, Milo, viens ici garçon. 35 00:02:05,170 --> 00:02:06,320 Milo. 36 00:02:06,320 --> 00:02:08,650 Milo. 37 00:02:08,650 --> 00:02:12,230 Rappelez-vous, il porte en verre Google, de sorte nous allons vous montrer tout cela après. 38 00:02:12,230 --> 00:02:16,190 Donc, c'est Milo si vous souhaitez prendre une photo avec lui par la suite. 39 00:02:16,190 --> 00:02:18,240 Si vous souhaitez regarder dehors au public y. 40 00:02:18,240 --> 00:02:19,430 OK. 41 00:02:19,430 --> 00:02:20,200 C'est une bonne séquence. 42 00:02:20,200 --> 00:02:22,556 Eh bien, Milo Banana. 43 00:02:22,556 --> 00:02:23,941 Oh, ne fais pas ça. 44 00:02:23,941 --> 00:02:29,020 >> [Rires] 45 00:02:29,020 --> 00:02:29,470 >> OK. 46 00:02:29,470 --> 00:02:34,550 Ainsi, un mot alors sur ce qui nous attend, parce que nous commençons à la transition, 47 00:02:34,550 --> 00:02:38,410 cette semaine précisément, à partir de C dans un environnement de ligne de commande pour PHP et 48 00:02:38,410 --> 00:02:42,720 JavaScript et SQL et HTML et CSS dans un environnement basé sur le Web, nous serons 49 00:02:42,720 --> 00:02:44,490 vous équiper avec tout le plus de connaissances pour 50 00:02:44,490 --> 00:02:46,010 projets finaux potentiels. 51 00:02:46,010 --> 00:02:49,240 À cette fin, le cours a un tradition d'organiser des séminaires qui 52 00:02:49,240 --> 00:02:50,950 portent sur des sujets tangentiels au cours. 53 00:02:50,950 --> 00:02:54,330 Très liée à la programmation et à le développement d'applications et ainsi de suite, mais 54 00:02:54,330 --> 00:02:57,010 pas nécessairement exploré par propre syllabus du cours. 55 00:02:57,010 --> 00:03:00,250 >> Donc, si vous pourriez être intéressé par un ou plus des séminaires de cette année, 56 00:03:00,250 --> 00:03:02,530 s'inscrire à cs50.net/seminar. 57 00:03:02,530 --> 00:03:06,170 Il ya des séminaires âgées à cs50.net/seminars. 58 00:03:06,170 --> 00:03:10,620 Et sur la liste à ce jour pour cette année sont des applications Web étonnants avec Ruby on 59 00:03:10,620 --> 00:03:13,580 Rails, qui est une alternative langue de PHP. 60 00:03:13,580 --> 00:03:14,900 Computational Linguistics. 61 00:03:14,900 --> 00:03:18,710 Introduction à iOS, qui est le plate-forme qui est utilisée pour l'iPhone et l' 62 00:03:18,710 --> 00:03:19,850 développement iPad. 63 00:03:19,850 --> 00:03:22,890 JavaScript pour les applications Web, nous couvrirons , mais à ce séminaire, vous irez 64 00:03:22,890 --> 00:03:24,070 plus en détail. 65 00:03:24,070 --> 00:03:27,390 >> Leap mouvement, donc nous allons effectivement avoir une certaine de nos amis de Leap Motion 66 00:03:27,390 --> 00:03:29,160 l'entreprise elle-même, rejoignez-nous. 67 00:03:29,160 --> 00:03:31,800 Demain, en effet, de fournir un séminaire pratique, si 68 00:03:31,800 --> 00:03:33,320 de vous intéresser. 69 00:03:33,320 --> 00:03:38,770 Meteor.js, une technique alternative pour l'utilisation de JavaScript n'est pas dans un navigateur, 70 00:03:38,770 --> 00:03:39,970 mais sur un serveur. 71 00:03:39,970 --> 00:03:42,110 Node.js, ce qui est beaucoup Dans cette veine ainsi. 72 00:03:42,110 --> 00:03:43,650 Design élégant Android. 73 00:03:43,650 --> 00:03:46,990 Android est une alternative très populaire pour iOS et Windows Phone 74 00:03:46,990 --> 00:03:48,790 et d'autres plates-formes mobiles. 75 00:03:48,790 --> 00:03:51,180 And Web Security Active Defense. 76 00:03:51,180 --> 00:03:54,590 >> Donc en fait, si vous souhaitez à s'engager dans ce domaine, laissez-moi 77 00:03:54,590 --> 00:03:55,840 prendre note de cela. 78 00:03:55,840 --> 00:03:57,790 Nous sommes très heureux de dire que nos amis de Leap 79 00:03:57,790 --> 00:03:59,140 Mouvement, qui est une startup - 80 00:03:59,140 --> 00:04:01,300 cet appareil vraiment juste venu il ya quelques mois - 81 00:04:01,300 --> 00:04:05,960 a gracieusement fait don de 30 de ces appareils à la classe pour que de nombreux étudiants, si 82 00:04:05,960 --> 00:04:08,670 que vous souhaitez emprunter du matériel vers la fin de semestre et l'utiliser pour 83 00:04:08,670 --> 00:04:10,390 un projet final réel. 84 00:04:10,390 --> 00:04:11,890 Ils soutiennent un certain nombre de langues. 85 00:04:11,890 --> 00:04:16,040 Aucun d'entre eux C, aucun d'entre eux PHP, réaliser une ou plusieurs de ces séminaires 86 00:04:16,040 --> 00:04:16,899 pourraient être d'intérêt. 87 00:04:16,899 --> 00:04:19,730 Et chacun d'entre eux sera tourné en Si vous n'êtes pas en mesure 88 00:04:19,730 --> 00:04:21,380 y assister en personne. 89 00:04:21,380 --> 00:04:25,000 Le calendrier sera annoncé via e-mail que nous renforçons chambres. 90 00:04:25,000 --> 00:04:28,460 >> Et enfin, si vous allez à projects.cs.50.net, il s'agit d'un site web 91 00:04:28,460 --> 00:04:31,450 nous maintenons chaque année que nous invitons les gens de la communauté, les professeurs, 92 00:04:31,450 --> 00:04:36,420 départements, le personnel et les à l'extérieur du CS50 à 93 00:04:36,420 --> 00:04:37,730 proposer des idées de projets. 94 00:04:37,730 --> 00:04:39,050 Choses d'intérêt à des groupes d'étudiants. 95 00:04:39,050 --> 00:04:40,600 Choses d'intérêt pour les ministères. 96 00:04:40,600 --> 00:04:43,990 Donc, ne mettez-y si vous êtes en difficulté l'incertitude quant à ce que vous 97 00:04:43,990 --> 00:04:46,700 vous aimeraient aborder. 98 00:04:46,700 --> 00:04:51,760 >> Donc, la dernière fois, nous avons introduit un doute structure de données plus complexes que nous avions 99 00:04:51,760 --> 00:04:53,300 vu ces dernières semaines. 100 00:04:53,300 --> 00:04:56,550 Nous avions été en utilisant des tableaux assez heureusement comme utile si 101 00:04:56,550 --> 00:04:58,160 structure de données simpliste. 102 00:04:58,160 --> 00:05:00,570 Ensuite, nous avons introduit ces derniers, qui sont bien sûr liés listes. 103 00:05:00,570 --> 00:05:05,470 Et ce qui était l'une des motivations pour l'introduction de cette structure de données? 104 00:05:05,470 --> 00:05:06,930 Ouais? 105 00:05:06,930 --> 00:05:07,250 Qu'est-ce que c'est? 106 00:05:07,250 --> 00:05:08,080 >> AUDIENCE: taille dynamique. 107 00:05:08,080 --> 00:05:09,040 >> DAVID MALAN: taille dynamique. 108 00:05:09,040 --> 00:05:11,890 Ainsi, alors que dans le tableau, vous devez connaître sa taille à l'avance quand 109 00:05:11,890 --> 00:05:12,740 vous allouez il. 110 00:05:12,740 --> 00:05:14,380 Dans la liste liée, vous n'avez pas avoir le savoir. 111 00:05:14,380 --> 00:05:17,610 Vous pouvez juste malloc, ou plus généralement, allouer un montant supplémentaire 112 00:05:17,610 --> 00:05:20,720 noeud, pour ainsi dire, à tout moment vous voulez insérer d'autres données. 113 00:05:20,720 --> 00:05:22,670 Et le noeud n'a pas de sens prédéterminé. 114 00:05:22,670 --> 00:05:25,580 C'est juste un terme générique décrivant une sorte de conteneur que nous sommes 115 00:05:25,580 --> 00:05:29,610 à l'aide de notre structure de données pour stocker quelque élément d'intérêt, qui, dans ce 116 00:05:29,610 --> 00:05:31,750 cas se trouvent être des entiers. 117 00:05:31,750 --> 00:05:33,160 >> Mais il ya toujours un compromis. 118 00:05:33,160 --> 00:05:38,070 Ainsi nous obtenons tailles dynamiques des données structure, mais à quel prix payons-nous? 119 00:05:38,070 --> 00:05:40,040 Quel est l'inconvénient des listes chaînées? 120 00:05:40,040 --> 00:05:41,006 Ouais? 121 00:05:41,006 --> 00:05:41,980 >> AUDIENCE: nécessite plus de mémoire. 122 00:05:41,980 --> 00:05:44,240 >> DAVID MALAN: Il faut plus de mémoire, comment exactement? 123 00:05:44,240 --> 00:05:46,440 >> AUDIENCE: [inaudible]. 124 00:05:46,440 --> 00:05:47,050 >> DAVID MALAN: Exactement. 125 00:05:47,050 --> 00:05:50,460 Alors maintenant, nous avons pointeurs prenant mémoire supplémentaire que nous avons précédemment 126 00:05:50,460 --> 00:05:53,040 n'avait pas besoin, parce que l'avantage d'un tableau, bien sûr, est que 127 00:05:53,040 --> 00:05:54,860 tout est contigu, dos à dos à dos, ce qui 128 00:05:54,860 --> 00:05:56,380 vous donne accès aléatoire. 129 00:05:56,380 --> 00:06:00,710 Parce que, tout en utilisant des crochets notation, ou plus techniquement pointeur 130 00:06:00,710 --> 00:06:03,580 arithmétique, addition très simple, vous pouvez accéder à n'importe quel 131 00:06:03,580 --> 00:06:05,700 éléments en temps constant. 132 00:06:05,700 --> 00:06:08,975 Et en fait, c'est le genre d'allusion à un autre prix que nous payons avec un 133 00:06:08,975 --> 00:06:09,760 liste chaînée. 134 00:06:09,760 --> 00:06:13,890 >> Qu'advient-il de la durée de fonctionnement de quelque chose comme la recherche, si je veux 135 00:06:13,890 --> 00:06:17,270 trouver une certaine valeur et à l'intérieur d'une liste chaînée? 136 00:06:17,270 --> 00:06:20,290 Qu'est-ce que mon temps à courir devenir? 137 00:06:20,290 --> 00:06:21,560 Big O n. 138 00:06:21,560 --> 00:06:24,060 Si c'est réglé pour? 139 00:06:24,060 --> 00:06:25,440 Que faire si la structure de données est triée? 140 00:06:25,440 --> 00:06:28,640 Puis-je faire mieux que grand O n pour la recherche? 141 00:06:28,640 --> 00:06:31,700 Non, parce que dans le pire des cas, il peut très bien être triés, mais le nombre 142 00:06:31,700 --> 00:06:32,950 vous cherchez peut-être grand. 143 00:06:32,950 --> 00:06:35,370 Il pourrait être le numéro 100, qui pourrait arriver à être tout 144 00:06:35,370 --> 00:06:36,410 le moyen à la fin. 145 00:06:36,410 --> 00:06:39,950 Et parce que vous ne pouvez accéder à un linked liste dans cette mise en œuvre par 146 00:06:39,950 --> 00:06:42,690 chemin de son premier noeud, vous êtes encore un peu de chance. 147 00:06:42,690 --> 00:06:47,450 Vous devez traverser toute chose du premier au dernier afin de trouver 148 00:06:47,450 --> 00:06:49,150 cette grande valeur comme 100. 149 00:06:49,150 --> 00:06:51,350 Ou pour déterminer s'il s'agit d' même pas là. 150 00:06:51,350 --> 00:06:55,960 >> Donc, nous ne pouvons pas faire ce que l'algorithme dans un ensemble de données structure qui ressemble à ceci? 151 00:06:55,960 --> 00:06:59,460 Nous ne pouvons pas faire de recherche binaire, parce que recherche binaire nécessaire que nous avions 152 00:06:59,460 --> 00:07:00,740 accès aléatoire. 153 00:07:00,740 --> 00:07:04,500 Nous pourrions simplement sauter d'un endroit à emplacement sans avoir à suivre 154 00:07:04,500 --> 00:07:07,080 ces miettes de pain dans la forme l'ensemble de ces pointeurs. 155 00:07:07,080 --> 00:07:08,300 >> Maintenant, comment at-on en œuvre? 156 00:07:08,300 --> 00:07:12,830 Eh bien, si nous allons à l'écran ici, si nous pouvons ré-écrire rapidement ces données 157 00:07:12,830 --> 00:07:13,440 Structure - 158 00:07:13,440 --> 00:07:15,670 mon écriture n'est pas si grand ici, mais nous allons essayer. 159 00:07:15,670 --> 00:07:22,030 Alors struct typedef, et qu'ai-je voulez appeler cette chose ici? 160 00:07:22,030 --> 00:07:22,960 Node. 161 00:07:22,960 --> 00:07:24,580 Donc, je vais nous avons commencé. 162 00:07:24,580 --> 00:07:27,860 Et maintenant, ce qui doit être à l'intérieur de la structure de données pour que seuls 163 00:07:27,860 --> 00:07:28,430 liste chaînée? 164 00:07:28,430 --> 00:07:29,950 Combien de champs? 165 00:07:29,950 --> 00:07:30,450 >> Donc deux. 166 00:07:30,450 --> 00:07:31,570 L'un est assez facile. 167 00:07:31,570 --> 00:07:33,050 Alors int n. 168 00:07:33,050 --> 00:07:35,930 Et nous pourrions appeler n ce que nous voulons, mais il devrait être un int si nous sommes 169 00:07:35,930 --> 00:07:37,660 mettre en œuvre une liste chaînée pour ints. 170 00:07:37,660 --> 00:07:41,920 Et maintenant, qu'est-ce que la seconde domaine en être ainsi? 171 00:07:41,920 --> 00:07:43,460 Struct noeud *. 172 00:07:43,460 --> 00:07:50,570 Donc, si je fais noeud struct *, puis je peut appeler cela aussi que je veux, 173 00:07:50,570 --> 00:07:53,510 mais juste pour être clair, je vais appeler à côté, comme nous l'avons fait. 174 00:07:53,510 --> 00:07:55,270 Et puis je vais fermer mes accolades. 175 00:07:55,270 --> 00:08:00,700 >> Et maintenant, que la dernière fois, Je mets noeud ici. 176 00:08:00,700 --> 00:08:03,830 Mais si je suis en déclarant ceci est aussi un noeud, pourquoi ai-je pris la peine d'être si 177 00:08:03,830 --> 00:08:07,320 verbose ici en déclarant struct * noeud suivant, par opposition 178 00:08:07,320 --> 00:08:09,210 à juste noeud * à côté? 179 00:08:09,210 --> 00:08:09,904 Ouais? 180 00:08:09,904 --> 00:08:12,810 >> AUDIENCE: [inaudible]. 181 00:08:12,810 --> 00:08:14,050 >> DAVID MALAN: Exactement. 182 00:08:14,050 --> 00:08:14,530 Exactement. 183 00:08:14,530 --> 00:08:18,320 Parce que C vous prend vraiment littéralement et ne voit que la définition de noeud 184 00:08:18,320 --> 00:08:21,230 chemin ici-bas, vous ne pouvez pas référer ici. 185 00:08:21,230 --> 00:08:24,760 Donc, nous avons ce genre de préemption déclaration ici, qui est certes 186 00:08:24,760 --> 00:08:25,390 plus bavard. 187 00:08:25,390 --> 00:08:27,810 Struct noeud, ce qui signifie nous pouvons maintenant y accéder 188 00:08:27,810 --> 00:08:29,760 à l'intérieur de la structure de données. 189 00:08:29,760 --> 00:08:33,370 >> Et en passant, parce que c'est devenir un peu plus subjective maintenant, 190 00:08:33,370 --> 00:08:36,230 l'étoile ne peut techniquement faire ici, il peut aller ici, il peut 191 00:08:36,230 --> 00:08:37,179 même aller dans le milieu. 192 00:08:37,179 --> 00:08:39,890 Nous avons adopté, dans le guide de style pour cours, la convention de mise 193 00:08:39,890 --> 00:08:42,299 l'étoile juste à côté des données type, qui, dans ce cas, 194 00:08:42,299 --> 00:08:43,460 serait nœud de structure. 195 00:08:43,460 --> 00:08:46,620 Mais réaliser dans un grand nombre de manuels et références en ligne, vous pourriez effectivement 196 00:08:46,620 --> 00:08:48,450 voir de l'autre côté. 197 00:08:48,450 --> 00:08:52,200 Mais juste se rendre compte que les deux seront effectivement travaillez et vous devez simplement être 198 00:08:52,200 --> 00:08:52,970 cohérente. 199 00:08:52,970 --> 00:08:53,580 >> Très bien. 200 00:08:53,580 --> 00:08:55,630 C'était donc notre déclaration du nœud de structure. 201 00:08:55,630 --> 00:08:59,430 Mais ensuite nous avons commencé à faire plus choses sophistiquées. 202 00:08:59,430 --> 00:09:03,410 Par exemple, nous avons décidé d'introduire quelque chose comme une table de hachage. 203 00:09:03,410 --> 00:09:08,160 Donc, voici une table de hachage de taille n, indexé à partir de 0 en haut à gauche de n 204 00:09:08,160 --> 00:09:09,690 moins 1 en bas à gauche. 205 00:09:09,690 --> 00:09:11,640 Cela pourrait être un hash table pour rien. 206 00:09:11,640 --> 00:09:15,340 Mais ce genre de choses ne nous parlons sur l'utilisation d'une table de hachage pour? 207 00:09:15,340 --> 00:09:18,370 Stockage quoi? 208 00:09:18,370 --> 00:09:18,800 >> Noms. 209 00:09:18,800 --> 00:09:20,870 Nous pourrions faire des noms comme nous avons fait la dernière fois. 210 00:09:20,870 --> 00:09:22,200 Et vraiment, vous pouvez stocker n'importe quoi. 211 00:09:22,200 --> 00:09:24,640 Et nous verrons ce message dans PHP et JavaScript. 212 00:09:24,640 --> 00:09:28,550 Une table de hachage est une belle sorte de Suisse Couteau qui vous permet de stocker 213 00:09:28,550 --> 00:09:33,690 à peu près tout ce que vous voulez à l'intérieur de il en associant des touches avec des valeurs. 214 00:09:33,690 --> 00:09:34,770 Touches de valeurs. 215 00:09:34,770 --> 00:09:37,800 >> Or, dans ce cas simple, notre touches sont que des chiffres. 216 00:09:37,800 --> 00:09:40,380 Nous mettons en place une table de hachage tableau comme un tableau. 217 00:09:40,380 --> 00:09:43,500 Et si les touches sont 0, 1, 2, et ainsi de suite. 218 00:09:43,500 --> 00:09:47,200 Et nous, en tant qu'êtres humains, a décidé dernier semaine que vous savez quoi, si nous sommes 219 00:09:47,200 --> 00:09:50,410 aller à des noms de magasins, disons simplement arbitrairement, mais assez raisonnablement, 220 00:09:50,410 --> 00:09:54,680 supposons que Alice, une un nom, va juste être indexé dans 0. 221 00:09:54,680 --> 00:09:58,030 Et Bob, un nom B, sera indexé en 1, et ainsi de suite. 222 00:09:58,030 --> 00:10:02,490 Donc, nous avons eu une correspondance entre les entrées, qui sont des chaînes, et le hachage 223 00:10:02,490 --> 00:10:04,560 endroits, qui sont des nombres. 224 00:10:04,560 --> 00:10:07,740 >> Donc, ce processus est généralement connu comme une fonction de hachage, et vous pouvez vraiment 225 00:10:07,740 --> 00:10:09,130 mettre en œuvre dans le code. 226 00:10:09,130 --> 00:10:12,080 Si je voulais mettre en œuvre une fonction de hachage qui fait exactement ce que nous 227 00:10:12,080 --> 00:10:17,070 vient d'être décrit de la dernière fois, je pourrais déclarer une fonction qui prend comme 228 00:10:17,070 --> 00:10:18,330 entrée par exemple - 229 00:10:18,330 --> 00:10:22,190 et nous allons le faire sur cette écran ici. 230 00:10:22,190 --> 00:10:26,180 Si je voulais mettre en place une table de hachage fonction, je pourrais dire 231 00:10:26,180 --> 00:10:27,410 quelque chose comme ça. 232 00:10:27,410 --> 00:10:29,030 >> Il va retourner un int. 233 00:10:29,030 --> 00:10:33,600 Ça va être appelé hash, et c'est va accepter comme argument une 234 00:10:33,600 --> 00:10:38,920 chaîne, ou nous pouvons être plus appropriée maintenant, et dire char *, nous l'appellerons s. 235 00:10:38,920 --> 00:10:43,840 Et puis tout cette fonction a à faire, en fin de compte, est de retour int. 236 00:10:43,840 --> 00:10:45,990 Maintenant, comment il le fait qui pourrait ne pas être si évident. 237 00:10:45,990 --> 00:10:49,510 Je vais mettre en œuvre ce sans aucune forme de contrôle d'erreur pour le moment. 238 00:10:49,510 --> 00:10:55,740 Je vais juste dire aveuglément, le retour tout ce qui est à l support 0, moins, 239 00:10:55,740 --> 00:10:58,850 disons, capitale un point-virgule. 240 00:10:58,850 --> 00:10:59,960 >> Totalement rompu. 241 00:10:59,960 --> 00:11:02,620 Ce n'est pas parfait parce que un, si s est nul? 242 00:11:02,620 --> 00:11:04,000 Les mauvaises choses vont se passer. 243 00:11:04,000 --> 00:11:07,940 Deux, si la première lettre de cette nom n'est pas une majuscule? 244 00:11:07,940 --> 00:11:09,860 Cela ne va pas tourner bien fonctionné non plus. 245 00:11:09,860 --> 00:11:11,970 Il pourrait être une lettre minuscule ou non une lettre du tout. 246 00:11:11,970 --> 00:11:15,520 Donc totalement marge d'amélioration ici, mais c'est l'idée de base. 247 00:11:15,520 --> 00:11:19,010 >> Qu'est-ce que nous avons décrit la semaine dernière verbalement seulement un processus de mappage pour Alice 248 00:11:19,010 --> 00:11:23,360 0 à 1 et Bob peuvent être exprimés certainement plus formulaically comme C 249 00:11:23,360 --> 00:11:24,320 fonctionner ici. 250 00:11:24,320 --> 00:11:28,630 Appelé à nouveau hash, prend une chaîne comme entrée, puis en quelque sorte fait quelque chose 251 00:11:28,630 --> 00:11:31,020 avec cette entrée pour produire un signal de sortie. 252 00:11:31,020 --> 00:11:34,130 Non contrairement à notre description de la boîte noire que nous avons longtemps fait. 253 00:11:34,130 --> 00:11:36,550 Je ne sais pas comment cela pourrait être travailler sous la hotte. 254 00:11:36,550 --> 00:11:40,120 >> Pour le jeu de problème 6, l'un des défis c'est à vous de décider ce que 255 00:11:40,120 --> 00:11:41,920 sera votre fonction de hachage être? 256 00:11:41,920 --> 00:11:45,760 Que se passe-être à l'intérieur de ce noir boîte, et sans doute, ce sera un 257 00:11:45,760 --> 00:11:50,380 peu plus intéressant que cela, et nettement plus sujettes à l'erreur 258 00:11:50,380 --> 00:11:53,180 vérifier que ce particulier mise en oeuvre. 259 00:11:53,180 --> 00:11:54,580 >> Mais des problèmes peuvent survenir, non? 260 00:11:54,580 --> 00:11:57,760 Si nous avons une structure de données telle que cette une, c'est quoi l'un des problèmes 261 00:11:57,760 --> 00:12:01,600 vous pouvez exécuter dans le temps que vous insérez de plus en plus des noms dans l' 262 00:12:01,600 --> 00:12:02,880 table de hachage? 263 00:12:02,880 --> 00:12:04,630 Vous obtenez collisions, non? 264 00:12:04,630 --> 00:12:07,560 Que faire si vous avez Alice et Aaron, deux personnes dont les noms arrivé 265 00:12:07,560 --> 00:12:08,190 à commencer par A? 266 00:12:08,190 --> 00:12:11,660 Cela soulève la question, où vous mettre le second un tel nom? 267 00:12:11,660 --> 00:12:15,050 >> Eh bien, vous pourriez naïvement il suffit de mettre où Bob appartient, mais Bob est 268 00:12:15,050 --> 00:12:17,300 genre de vissé si vous essayez d' insérer son nom à côté et 269 00:12:17,300 --> 00:12:18,240 il n'y a pas de place pour lui. 270 00:12:18,240 --> 00:12:21,400 Donc, vous pourriez mettre Bob où Charlie est, et vous pouvez imaginer ce très rapidement 271 00:12:21,400 --> 00:12:23,020 sombrer dans un peu de désordre. 272 00:12:23,020 --> 00:12:25,600 Quelque chose de linéaire à la fin, où vous suffit de rechercher le tout 273 00:12:25,600 --> 00:12:28,190 à la recherche d'Alice ou de Bob ou Aaron ou Charlie. 274 00:12:28,190 --> 00:12:33,230 >> Ainsi, au lieu que nous avons proposé, au lieu de simplement linéairement sondage pour les espaces ouverts 275 00:12:33,230 --> 00:12:36,450 et plopping les noms là-bas, nous proposé une approche plus fantaisistes. 276 00:12:36,450 --> 00:12:41,740 Une table de hachage en œuvre encore avec un tableau d'index, mais le type de données 277 00:12:41,740 --> 00:12:44,500 ces indices étaient maintenant des pointeurs. 278 00:12:44,500 --> 00:12:47,360 Pointeurs vers quoi? 279 00:12:47,360 --> 00:12:48,730 Les pointeurs vers des listes chaînées. 280 00:12:48,730 --> 00:12:53,330 >> Parce que le rappel d'une liste liée est vraiment juste un pointeur vers un noeud, et 281 00:12:53,330 --> 00:12:57,110 le noeud possède un champ à côté, et que le noeud présente une zone suivante, et ainsi de suite. 282 00:12:57,110 --> 00:13:00,690 Ainsi, vous pouvez maintenant penser à ce tableau sur le côté gauche d'une table de hachage en tant que 283 00:13:00,690 --> 00:13:01,820 conduisant à une liste liée. 284 00:13:01,820 --> 00:13:07,000 L'avantage de ce qui est si vous obtenez un collision entre Alice et Aaron, 285 00:13:07,000 --> 00:13:09,300 que faites-vous avec le deuxième telle personne? 286 00:13:09,300 --> 00:13:14,150 Vous attachez simplement lui à l' extrémité, ou même le début 287 00:13:14,150 --> 00:13:15,490 de cette liste liée. 288 00:13:15,490 --> 00:13:17,340 >> Et en fait, disons simplement nouilles à travers que pour une seconde. 289 00:13:17,340 --> 00:13:18,640 Où serait le plus logique? 290 00:13:18,640 --> 00:13:22,060 Si j'insère Alice et elle finit à le premier emplacement, puis j'essaie de 291 00:13:22,060 --> 00:13:25,310 insérer le nom d'Aaron, et il ya évidemment une collision, devrais-je mettre 292 00:13:25,310 --> 00:13:27,400 lui au début de la liste liée? 293 00:13:27,400 --> 00:13:30,944 C'est à ce premier emplacement, ou à la fin? 294 00:13:30,944 --> 00:13:31,440 >> AUDIENCE: [inaudible]. 295 00:13:31,440 --> 00:13:31,990 >> DAVID MALAN: OK. 296 00:13:31,990 --> 00:13:32,490 J'ai entendu commencer. 297 00:13:32,490 --> 00:13:33,903 Pourquoi au début? 298 00:13:33,903 --> 00:13:34,750 >> AUDIENCE: [inaudible]. 299 00:13:34,750 --> 00:13:34,940 >> DAVID MALAN: OK. 300 00:13:34,940 --> 00:13:36,520 C'est alphabétique, donc c'est bien. 301 00:13:36,520 --> 00:13:37,330 C'est un bon établissement. 302 00:13:37,330 --> 00:13:39,335 Il va me faire gagner du temps potentiellement. 303 00:13:39,335 --> 00:13:43,290 Il ne sera pas me laisser faire une recherche binaire, mais je pourrait au moins être en mesure de sortir 304 00:13:43,290 --> 00:13:47,340 d'une boucle si je me rends compte, eh bien, je suis bien passé étaient Aaron serait dans ce 305 00:13:47,340 --> 00:13:48,310 triés liste chaînée. 306 00:13:48,310 --> 00:13:50,360 Je n'ai pas à perdre mon temps à regarder tout le chemin vers la fin. 307 00:13:50,360 --> 00:13:51,530 Donc, c'est raisonnable. 308 00:13:51,530 --> 00:13:54,710 Sinon, pourquoi auriez-vous besoin d'insérer le nom de la collision à l' 309 00:13:54,710 --> 00:13:56,660 au début de la liste? 310 00:13:56,660 --> 00:13:57,397 Qu'est-ce que c'est? 311 00:13:57,397 --> 00:13:58,680 >> AUDIENCE: [inaudible]. 312 00:13:58,680 --> 00:14:00,820 >> DAVID MALAN: Il pourrait prendre un certain temps pour obtenir à la fin de la liste. 313 00:14:00,820 --> 00:14:02,490 Et en fait, plus longtemps et plus longtemps. 314 00:14:02,490 --> 00:14:04,920 Les autres noms que vous insérez A commencer par le plus que 315 00:14:04,920 --> 00:14:06,280 chaîne va se faire. 316 00:14:06,280 --> 00:14:07,890 Le plus qui reliait liste va se faire. 317 00:14:07,890 --> 00:14:09,420 Donc, vous êtes vraiment juste perdre votre temps. 318 00:14:09,420 --> 00:14:14,070 Peut-être que vous êtes mieux maintenant temps d'insertion constant, grand O 1, 319 00:14:14,070 --> 00:14:18,470 en mettant toujours le nom à entrer en collision le début de la liste liée, 320 00:14:18,470 --> 00:14:21,230 et ne pas se soucier autant sur le tri. 321 00:14:21,230 --> 00:14:22,600 >> Quelle est la meilleure solution? 322 00:14:22,600 --> 00:14:23,320 On ne sait pas. 323 00:14:23,320 --> 00:14:26,140 Il genre de dépend de ce que l' distribution, ce que le modèle est 324 00:14:26,140 --> 00:14:27,850 des noms que vous avez inséré. 325 00:14:27,850 --> 00:14:29,430 Ce n'est pas nécessairement une réponse évidente. 326 00:14:29,430 --> 00:14:33,100 Mais ici, encore une fois, est une occasion de conception. 327 00:14:33,100 --> 00:14:37,220 >> Alors nous avons regardé cette chose, qui est vraiment l'autre grande opportunité 328 00:14:37,220 --> 00:14:38,180 P-set 6. 329 00:14:38,180 --> 00:14:41,770 Et de réaliser, si vous n'avez pas déjà, Zamyla plonge dans ces deux hachage, 330 00:14:41,770 --> 00:14:43,260 tables et essaie, plus en détail. 331 00:14:43,260 --> 00:14:45,630 Et la présentation vidéo est intégré dans le p-ensemble spec. 332 00:14:45,630 --> 00:14:46,590 Ce fut un trie - 333 00:14:46,590 --> 00:14:51,670 T-R-I-E. Et ce qui est intéressant à propos de ce n'était que le temps d'exécution 334 00:14:51,670 --> 00:14:59,510 de recherche d'un nom, comme Maxwell dernière fois, était grand O de quoi? 335 00:14:59,510 --> 00:15:01,040 Qu'est-ce que c'est? 336 00:15:01,040 --> 00:15:01,920 >> AUDIENCE: Le nombre de lettres. 337 00:15:01,920 --> 00:15:02,550 >> DAVID MALAN: Nombre de lettres. 338 00:15:02,550 --> 00:15:03,210 J'ai entendu deux choses. 339 00:15:03,210 --> 00:15:04,630 Nombre de lettres et de constante de temps. 340 00:15:04,630 --> 00:15:05,540 Allons donc à cette première. 341 00:15:05,540 --> 00:15:06,410 Le nombre de lettres. 342 00:15:06,410 --> 00:15:10,195 Eh bien, cette structure de données, le rappel est Comme un arbre, un arbre de la famille, chacun des 343 00:15:10,195 --> 00:15:12,860 nœuds dont sont constitués de tableaux. 344 00:15:12,860 --> 00:15:16,300 Et ces tableaux sont des pointeurs vers d'autres tels noeuds, ou d'autres comme 345 00:15:16,300 --> 00:15:17,670 les tableaux dans l'arbre. 346 00:15:17,670 --> 00:15:22,890 >> Donc, si nous voulions déterminer ensuite si Maxwell est ici, je pourrais aller 347 00:15:22,890 --> 00:15:26,890 à la première rangée, au sommet de l'arbre, le soi-disant racine, haut de 348 00:15:26,890 --> 00:15:30,521 le trie, puis suivez le pointeur m, puis l'un pointeur, alors x, 349 00:15:30,521 --> 00:15:31,710 w, e, l, l. 350 00:15:31,710 --> 00:15:34,910 Et puis, quand je vois un symbole spécial, désigné ici comme un triangle. 351 00:15:34,910 --> 00:15:38,480 Dans le code, vous verrez que nous vous proposons implémenté comme un bool, juste dire oui 352 00:15:38,480 --> 00:15:40,540 ou non, un mot s'arrête ici. 353 00:15:40,540 --> 00:15:45,270 >> Eh bien, une fois que nous sommes allés à M-A-X-W-E-L-L, qui ressemble à sept, peut-être 354 00:15:45,270 --> 00:15:48,910 huit si nous allons un passé il, huit étapes pour trouver Maxwell. 355 00:15:48,910 --> 00:15:53,050 Ou appelons-le K. Mais rappelons dernier temps, j'ai fait valoir que s'il ya 356 00:15:53,050 --> 00:15:57,540 réaliste une longueur maximale d'un mot, comme des personnages quelque 40 impairs, une 357 00:15:57,540 --> 00:16:00,810 longueur maximale implique une valeur constante. 358 00:16:00,810 --> 00:16:05,770 Alors, vraiment, oui, c'est techniquement grand O de 8 ou 7, ou vraiment grand O de K. Mais 359 00:16:05,770 --> 00:16:09,420 si il ya un bouchon fini sur ce K pourrait être, c'est une constante. 360 00:16:09,420 --> 00:16:12,080 Et il est donc grand O de 1 à la fin de la journée. 361 00:16:12,080 --> 00:16:13,040 >> Pas dans le monde réel. 362 00:16:13,040 --> 00:16:15,960 Pas quand vous avez réellement commencer à regarder votre horloge comme le fonctionnement de votre programme. 363 00:16:15,960 --> 00:16:20,690 Il est absolument va être un peu plus lent que vraiment constant 364 00:16:20,690 --> 00:16:21,840 le temps avec une seule étape. 365 00:16:21,840 --> 00:16:25,540 Il va y avoir sept ou huit étapes, mais c'est beaucoup, beaucoup mieux 366 00:16:25,540 --> 00:16:30,080 qu'un algorithme comme Big O n que dépend de la taille de ce qui est dans l' 367 00:16:30,080 --> 00:16:31,220 la structure de données. 368 00:16:31,220 --> 00:16:34,970 >> Remarquez la hausse ici est que nous pouvons insérer plus d'un million de noms dans cette 369 00:16:34,970 --> 00:16:38,170 structure de données, mais combien d'autres mesures est ce que ça va nous prendre pour trouver 370 00:16:38,170 --> 00:16:40,480 Maxwell dans ce cas? 371 00:16:40,480 --> 00:16:40,780 Aucun. 372 00:16:40,780 --> 00:16:41,820 Il n'est pas affecté. 373 00:16:41,820 --> 00:16:45,480 Et à ce jour, je ne pense pas que nous avons vu un exemple d'une structure de données ou un 374 00:16:45,480 --> 00:16:48,560 algorithme qui a été complètement affectée par externe 375 00:16:48,560 --> 00:16:50,040 comportements comme ça. 376 00:16:50,040 --> 00:16:51,160 Mais cela ne peut pas être étonnant. 377 00:16:51,160 --> 00:16:52,900 Cela ne peut pas être la seule solution pour le p-ensemble 378 00:16:52,900 --> 00:16:53,570 >> Et ce n'est pas le cas. 379 00:16:53,570 --> 00:16:55,980 Ce n'est pas nécessairement les données la structure devrait graviter autour de vous, 380 00:16:55,980 --> 00:16:58,220 parce que, comme les tables de hachage, faire des compromis. 381 00:16:58,220 --> 00:17:00,500 Quel est le prix que vous payez ici? 382 00:17:00,500 --> 00:17:00,940 Mémoire. 383 00:17:00,940 --> 00:17:02,890 Je veux dire, c'est une atroce quantité de mémoire. 384 00:17:02,890 --> 00:17:05,569 Et vous ne pouvez pas tout voir ici parce que L'auteur de cette image 385 00:17:05,569 --> 00:17:09,420 évidemment tronqué tous les tableaux, et nous ne voyons pas beaucoup de A et 386 00:17:09,420 --> 00:17:12,700 B et C et Q et Y de et Z de ces matrices. 387 00:17:12,700 --> 00:17:13,630 Mais ils sont là. 388 00:17:13,630 --> 00:17:17,660 >> Chacun de ces nœuds est un tableau entier d'environ 26 octets ou plus, chacun de 389 00:17:17,660 --> 00:17:19,170 qui représente une lettre. 390 00:17:19,170 --> 00:17:22,920 27 dans notre cas, de sorte que nous pouvons soutenir apostrophes dans l'ensemble du problème. 391 00:17:22,920 --> 00:17:27,030 Donc, cette structure de données est vraiment, vraiment dense et large. 392 00:17:27,030 --> 00:17:30,880 Et cela seul pourrait finir par ralentir les choses, ou au moins vous coûter une 393 00:17:30,880 --> 00:17:32,240 beaucoup plus d'espace. 394 00:17:32,240 --> 00:17:34,020 Mais encore une fois, nous pouvons tirer comparaisons ici. 395 00:17:34,020 --> 00:17:39,190 >> Rappelons ya quelque temps, nous avons réalisé beaucoup temps d'exécution plus excitant dans le tri 396 00:17:39,190 --> 00:17:42,880 lorsque nous utilisons le tri par fusion, mais le prix nous avons payé pour atteindre n log n pour fusion 397 00:17:42,880 --> 00:17:46,930 Trier nécessaire que nous dépensons plus quelle ressource? 398 00:17:46,930 --> 00:17:47,690 Plus d'espace. 399 00:17:47,690 --> 00:17:50,530 Nous avions besoin d'un réseau secondaire de copier les gens dans, tout comme 400 00:17:50,530 --> 00:17:51,620 nous avons fait ici sur scène. 401 00:17:51,620 --> 00:17:55,880 Encore une fois, pas de gagnants, mais juste conception subjective 402 00:17:55,880 --> 00:17:57,710 décisions à prendre. 403 00:17:57,710 --> 00:17:58,060 >> Très bien. 404 00:17:58,060 --> 00:17:59,130 Alors, comment à ce sujet? 405 00:17:59,130 --> 00:18:02,050 Toute personne qui reconnaît D-Hall? 406 00:18:02,050 --> 00:18:02,440 OK. 407 00:18:02,440 --> 00:18:03,170 Donc, trois d'entre nous. 408 00:18:03,170 --> 00:18:03,750 Mather House. 409 00:18:03,750 --> 00:18:05,070 Il s'agit donc pour la salle de Mather. 410 00:18:05,070 --> 00:18:09,650 Je parie que toutes les salles à manger ont piles de plateaux comme celui-ci. 411 00:18:09,650 --> 00:18:11,950 Et c'est réellement représentatives de quelque chose que nous avons 412 00:18:11,950 --> 00:18:13,050 évidemment déjà vu. 413 00:18:13,050 --> 00:18:14,850 Nous l'avons appelé littéralement une pile. 414 00:18:14,850 --> 00:18:18,970 Et la pile, en fonction de votre la mémoire de l'ordinateur, est l'endroit où les données va 415 00:18:18,970 --> 00:18:20,460 tandis que les fonctions sont appelées. 416 00:18:20,460 --> 00:18:23,410 >> Par exemple, quels types de choses vont sur la pile par rapport à l' 417 00:18:23,410 --> 00:18:27,420 disposition de la mémoire, nous avons discuté ces dernières semaines? 418 00:18:27,420 --> 00:18:28,736 Qu'est-ce que c'est? 419 00:18:28,736 --> 00:18:29,670 >> AUDIENCE: appels à des fonctions. 420 00:18:29,670 --> 00:18:30,260 >> DAVID MALAN: Je suis désolé. 421 00:18:30,260 --> 00:18:31,210 >> AUDIENCE: appels à des fonctions. 422 00:18:31,210 --> 00:18:33,590 >> DAVID MALAN: appels à des fonctions, mais Plus précisément, ce qui est à l'intérieur de chacune des 423 00:18:33,590 --> 00:18:35,340 ces cadres? 424 00:18:35,340 --> 00:18:37,220 Quel genre de choses? 425 00:18:37,220 --> 00:18:37,460 Ouais. 426 00:18:37,460 --> 00:18:38,500 Donc, les variables locales. 427 00:18:38,500 --> 00:18:43,080 Chaque fois que nous avions besoin d'un espace de stockage local, comme un argument, ou int I, ou int 428 00:18:43,080 --> 00:18:45,940 temp, ou quelle que soit la locale variable, nous avons été 429 00:18:45,940 --> 00:18:47,210 mettre que dans la pile. 430 00:18:47,210 --> 00:18:49,610 Et nous appelons cela une pile parce que de cette idée de superposition. 431 00:18:49,610 --> 00:18:52,940 Tout genre de matchs avec la réalité, le concept de ceux-ci. 432 00:18:52,940 --> 00:18:56,650 >> Mais il s'avère que la pile peut également être considéré comme une structure de données, un 433 00:18:56,650 --> 00:19:00,110 alternative à un tableau, une alternative d'une liste chaînée. 434 00:19:00,110 --> 00:19:02,770 Quelque chose conceptuellement plus intéressant qui peut être encore 435 00:19:02,770 --> 00:19:06,030 implémenté en utilisant soit des personnes choses, mais c'est un autre type de 436 00:19:06,030 --> 00:19:09,140 structure de données à l'appui, vraiment, seules deux opérations. 437 00:19:09,140 --> 00:19:11,000 Mais vous pouvez ajouter le colombophile fonctionnalités que celles-ci. 438 00:19:11,000 --> 00:19:12,180 Mais ce sont les bases - 439 00:19:12,180 --> 00:19:13,510 push et pop. 440 00:19:13,510 --> 00:19:19,240 >> Et l'idée d'une pile est que si je avoir ici, avec ou sans Annenberg 441 00:19:19,240 --> 00:19:22,880 savoir, un plateau d'à côté par le chiffre 9 sur elle. 442 00:19:22,880 --> 00:19:23,870 Il suffit donc un int. 443 00:19:23,870 --> 00:19:26,990 Et je tiens à pousser ce sur les données structure, qui est actuellement vide. 444 00:19:26,990 --> 00:19:28,790 Considérons ce bas de la pile. 445 00:19:28,790 --> 00:19:33,150 Je voudrais pousser ce numéro 9 sur le pile, et maintenant il est juste là. 446 00:19:33,150 --> 00:19:36,040 >> Mais la chose intéressante à propos d'une pile c'est que si je veux maintenant pousser 447 00:19:36,040 --> 00:19:40,210 une autre valeur, comme 17, et je pousse ce sur la pile, je vais le faire 448 00:19:40,210 --> 00:19:43,290 la seule chose intuitive, je vais juste pour le mettre là où nous les humains 449 00:19:43,290 --> 00:19:45,180 serait enclin à le mettre, sur le dessus. 450 00:19:45,180 --> 00:19:48,850 Mais ce qui est intéressant maintenant est, comment puis-je obtenir à 9? 451 00:19:48,850 --> 00:19:50,670 Vous savez, je ne suis pas sans un certain effort. 452 00:19:50,670 --> 00:19:54,070 >> Donc ce qui est intéressant à propos de une pile, c'est que de par leur conception, 453 00:19:54,070 --> 00:19:56,330 c'est une structure de données LIFO. 454 00:19:56,330 --> 00:19:59,680 Façon idiote de décrire dernier entré, premier sorti. 455 00:19:59,680 --> 00:20:03,280 Donc, le dernier numéro de à cette époque était de 17. 456 00:20:03,280 --> 00:20:07,540 Donc, si je veux quelque chose de pop off de la pile, il ne peut être que 17. 457 00:20:07,540 --> 00:20:11,890 Donc, il ya une ordonnance de opérations ici, où le dernier élément 458 00:20:11,890 --> 00:20:14,260 en doit être le premier à sortir. 459 00:20:14,260 --> 00:20:16,440 D'où l'acronyme, LIFO. 460 00:20:16,440 --> 00:20:19,160 >> Alors pourquoi cela pourrait-il être utile? 461 00:20:19,160 --> 00:20:22,690 Sont leurs contextes dans lesquels vous feriez vouloir une structure de données comme ça? 462 00:20:22,690 --> 00:20:24,810 Eh bien, il a certainement été utile à l'intérieur d'un ordinateur. 463 00:20:24,810 --> 00:20:29,050 Alors systèmes d'exploitation utilisent clairement cette type de structure de données pour les cheminées. 464 00:20:29,050 --> 00:20:32,800 Nous verrons aussi la même idée quand il s'agit de pages Web. 465 00:20:32,800 --> 00:20:35,890 Donc, cette semaine et la semaine prochaine et au-delà, et que vous commencez à mettre en œuvre web 466 00:20:35,890 --> 00:20:39,490 pages dans un langage appelé HTML, vous pouvez en fait utiliser une structure de données comme 467 00:20:39,490 --> 00:20:42,690 ce afin de déterminer si la page est correctement formaté. 468 00:20:42,690 --> 00:20:47,170 Parce que nous allons voir toutes les pages Web suivent une sorte de hiérarchie, une échancrure 469 00:20:47,170 --> 00:20:52,030 qui, à la fin de la journée, une structure d'arbre sous la hotte. 470 00:20:52,030 --> 00:20:53,620 Donc, plus que dans un peu. 471 00:20:53,620 --> 00:20:56,560 >> Mais pour l'instant, nous allons proposer pour un moment, comment pourrions-nous nous y prendre 472 00:20:56,560 --> 00:20:58,830 représentant ce que la pile est? 473 00:20:58,830 --> 00:21:03,370 Permettez-moi de proposer que nous mettons en œuvre une pile avec du code comme ceci. 474 00:21:03,370 --> 00:21:07,990 Ainsi, une pile va avoir à l'intérieur de celui-ci deux choses, un tableau, appelés plateaux, 475 00:21:07,990 --> 00:21:09,510 juste pour être compatibles avec la démo. 476 00:21:09,510 --> 00:21:12,660 Et chacun des éléments de cette matrice va être un type int. 477 00:21:12,660 --> 00:21:14,740 Et la capacité est sans doute quoi? 478 00:21:14,740 --> 00:21:18,796 Parce que je n'ai pas écrit l' définition complète ici. 479 00:21:18,796 --> 00:21:21,535 >> C'est probablement le maximum taille du tableau. 480 00:21:21,535 --> 00:21:25,150 Et c'est probablement déclarée comme un dièse définir dans la partie supérieure du dossier, un certain 481 00:21:25,150 --> 00:21:28,450 sorte de constante comme le laisse entendre la seule capitalisation. 482 00:21:28,450 --> 00:21:32,250 Donc quelque part la capacité est définie que la taille maximale possible. 483 00:21:32,250 --> 00:21:35,590 Pendant ce temps, à l'intérieur de la structure de données connue comme une pile, il y aura 484 00:21:35,590 --> 00:21:38,630 être un entier vient de connaître simplement que la taille. 485 00:21:38,630 --> 00:21:43,400 >> Donc, si je devais représenter ce moment imagée, supposons que cette 486 00:21:43,400 --> 00:21:48,070 ensemble boîte noire représente ma pile. 487 00:21:48,070 --> 00:21:50,070 A l'intérieur de celui-ci est deux variables. 488 00:21:50,070 --> 00:21:54,780 Donc, je vais attirer l' premier comme taille. 489 00:21:54,780 --> 00:21:57,420 Et le second, je vais pour dessiner comme un tableau. 490 00:21:57,420 --> 00:22:01,060 >> Mais juste pour garder les choses ordonnée, Normalement, je devrais dessiner un tableau comme 491 00:22:01,060 --> 00:22:04,910 , mais c'est le genre de belle si nous comparons la réalité, ou 492 00:22:04,910 --> 00:22:06,230 correspondre au modèle mental. 493 00:22:06,230 --> 00:22:12,880 Alors laissez-moi plutôt dessine le tableau verticalement, ce qui est juste, encore une fois, 494 00:22:12,880 --> 00:22:13,840 L'interprétation de l'artiste. 495 00:22:13,840 --> 00:22:16,610 Ça n'a pas vraiment d'importance ce que est sous la hotte. 496 00:22:16,610 --> 00:22:20,350 Et nous dirons que, par défaut, capacité va être trois. 497 00:22:20,350 --> 00:22:23,480 Ce sera donc l'emplacement 0, ce sera emplacement 1, ce 498 00:22:23,480 --> 00:22:25,740 sera emplacement 2. 499 00:22:25,740 --> 00:22:29,330 >> Si je soudoyer avec une boule de stress, serait Quelqu'un comme pour se lever et courir le 500 00:22:29,330 --> 00:22:30,870 embarquer ici juste un instant? 501 00:22:30,870 --> 00:22:31,960 OK, vu votre première main. 502 00:22:31,960 --> 00:22:33,950 Venez sur place. 503 00:22:33,950 --> 00:22:36,500 Très bien. 504 00:22:36,500 --> 00:22:38,760 Donc, je crois que c'est Steven. 505 00:22:38,760 --> 00:22:40,035 Venez sur place. 506 00:22:40,035 --> 00:22:40,770 Très bien. 507 00:22:40,770 --> 00:22:46,760 >> Mais supposons maintenant nous revenir en arrière pour la première état du monde où je 508 00:22:46,760 --> 00:22:52,180 venez de déclarer une pile, et c'est va avoir une capacité trois. 509 00:22:52,180 --> 00:22:54,470 Mais la taille n'a pas encore été déterminée. 510 00:22:54,470 --> 00:22:56,100 Plateaux n'a pas encore été déterminée. 511 00:22:56,100 --> 00:22:57,300 Alors, quelques questions d'abord. 512 00:22:57,300 --> 00:23:01,310 Et permettez-moi de vous donner micro afin que vous puissiez participer plus activement. 513 00:23:01,310 --> 00:23:05,190 >> Alors, quelle est à l'intérieur de la taille en ce moment dans le temps si tout ce que j'ai fait, c'est 514 00:23:05,190 --> 00:23:09,340 déclaré une pile à une ligne de code? 515 00:23:09,340 --> 00:23:10,100 >> STEVEN: Pas beaucoup. 516 00:23:10,100 --> 00:23:12,080 >> DAVID MALAN: OK, pas beaucoup. 517 00:23:12,080 --> 00:23:14,410 Savons-nous ce qu'il ya à l'intérieur de la taille, savons-nous ce qu'il ya dedans 518 00:23:14,410 --> 00:23:16,330 de ce tableau ici? 519 00:23:16,330 --> 00:23:18,630 >> STEVEN: Juste code aléatoire, non? 520 00:23:18,630 --> 00:23:20,220 Just - 521 00:23:20,220 --> 00:23:23,230 >> DAVID MALAN: Ouais, je vais appeler le code, mais aléatoire - 522 00:23:23,230 --> 00:23:23,820 >> STEVEN: Things. 523 00:23:23,820 --> 00:23:28,290 >> DAVID MALAN: Des choses comme aléatoire 524 00:23:28,290 --> 00:23:28,870 >> STEVEN: Bits. 525 00:23:28,870 --> 00:23:29,530 >> DAVID MALAN: Bits, pas vrai? 526 00:23:29,530 --> 00:23:31,190 Donc, les valeurs d'ordures, non? 527 00:23:31,190 --> 00:23:33,470 Alors permutations de 0 et de 1. 528 00:23:33,470 --> 00:23:35,920 Les restes d'usages antérieurs de cette mémoire. 529 00:23:35,920 --> 00:23:38,150 Et nous ne savons pas vraiment ce que les valeurs sommes, si nous attirons généralement les 530 00:23:38,150 --> 00:23:38,930 des points d'interrogation. 531 00:23:38,930 --> 00:23:41,990 >> Donc la première chose que nous sommes probablement va vouloir faire ici - 532 00:23:41,990 --> 00:23:46,630 et permettez-moi de vous donner ce domaine à l'intérieur de là un nom - plateaux. 533 00:23:46,630 --> 00:23:49,540 Que devrions-nous initialiser vraisemblablement taille si nous voulons 534 00:23:49,540 --> 00:23:51,040 commencer à utiliser cette pile? 535 00:23:51,040 --> 00:23:53,070 >> STEVEN: Plateau est sous 3. 536 00:23:53,070 --> 00:23:53,910 >> DAVID MALAN: Donc, OK. 537 00:23:53,910 --> 00:23:56,710 Pour être clair, la capacité est déclarée ailleurs que trois. 538 00:23:56,710 --> 00:23:58,570 Et c'est ce que j'ai utilisé à allouer le tableau. 539 00:23:58,570 --> 00:24:03,535 Taille va se référer à combien de les plateaux sont actuellement sur la pile. 540 00:24:03,535 --> 00:24:03,880 >> STEVEN: Zéro. 541 00:24:03,880 --> 00:24:04,460 >> DAVID MALAN: Donc, il devrait être de zéro. 542 00:24:04,460 --> 00:24:07,760 Alors allez-y, et avec un doigt, dessiner une taille zéro. 543 00:24:07,760 --> 00:24:08,440 Très bien. 544 00:24:08,440 --> 00:24:10,920 Alors maintenant, ce qui est à l'intérieur de cette ici, nous ne savons pas. 545 00:24:10,920 --> 00:24:12,160 Ce sont vraiment juste des valeurs d'ordures. 546 00:24:12,160 --> 00:24:14,800 Donc, nous pourrions tirer des points d'interrogation, mais gardons la planche propre pour l'instant 547 00:24:14,800 --> 00:24:16,300 parce que ce n'est pas grave ce qui est là. 548 00:24:16,300 --> 00:24:19,130 Nous n'avons pas besoin d'initialiser le tableau à rien, parce que si nous savons que 549 00:24:19,130 --> 00:24:23,100 la taille de la pile est égale à zéro, eh bien, nous ne devrait pas être regardant quelque chose dans 550 00:24:23,100 --> 00:24:25,590 ce tableau de toute façon à ce point dans le temps. 551 00:24:25,590 --> 00:24:29,970 >> Supposez maintenant que je pousse le n ° 9 dans la pile. 552 00:24:29,970 --> 00:24:33,750 Comment devrions-nous mettre à jour la structure de données à l'intérieur de cette boîte noire? 553 00:24:33,750 --> 00:24:35,540 Quelles valeurs faut-il changer? 554 00:24:35,540 --> 00:24:36,200 >> STEVEN: Within - 555 00:24:36,200 --> 00:24:37,400 la taille? 556 00:24:37,400 --> 00:24:37,650 >> DAVID MALAN: OK. 557 00:24:37,650 --> 00:24:38,770 Taille devrait devenir quoi? 558 00:24:38,770 --> 00:24:39,580 >> STEVEN: Taille serait un. 559 00:24:39,580 --> 00:24:39,870 >> DAVID MALAN: OK. 560 00:24:39,870 --> 00:24:41,110 Taille devrait donc devenir un. 561 00:24:41,110 --> 00:24:42,540 Ainsi, vous pouvez le faire en deux manières. 562 00:24:42,540 --> 00:24:46,920 Permettez-moi de vous donner, dès maintenant votre le doigt est une gomme. 563 00:24:46,920 --> 00:24:47,260 Très bien. 564 00:24:47,260 --> 00:24:49,960 Alors maintenant votre doigt est une brosse. 565 00:24:49,960 --> 00:24:50,330 Très bien. 566 00:24:50,330 --> 00:24:52,820 Et maintenant, qu'est-ce qui doit changer, évidemment, dans la structure de données? 567 00:24:52,820 --> 00:24:57,060 >> STEVEN: Nous allons partir bas jusqu'à 9. 568 00:24:57,060 --> 00:24:57,760 >> DAVID MALAN: 9. 569 00:24:57,760 --> 00:24:58,420 OK, c'est bon. 570 00:24:58,420 --> 00:25:01,550 Donc, ne reste pas d'importance ce qui est en lieu une ou deux parce qu'ils sont 571 00:25:01,550 --> 00:25:04,520 valeurs d'ordures, mais il ne faut pas déranger là, à regarder parce que la taille est 572 00:25:04,520 --> 00:25:07,540 nous dire que seul le premier élément est en fait légitime. 573 00:25:07,540 --> 00:25:10,400 Alors maintenant, je pousse 17 sur la liste. 574 00:25:10,400 --> 00:25:11,830 Qu'advient-il de cette image? 575 00:25:11,830 --> 00:25:14,720 >> STEVEN: Donc la taille va aller à deux. 576 00:25:14,720 --> 00:25:15,300 >> DAVID MALAN: OK. 577 00:25:15,300 --> 00:25:16,070 Vous êtes gomme - 578 00:25:16,070 --> 00:25:16,810 oops. 579 00:25:16,810 --> 00:25:18,026 Vous êtes une gomme. 580 00:25:18,026 --> 00:25:18,840 >> STEVEN: Eraser. 581 00:25:18,840 --> 00:25:19,720 >> DAVID MALAN: Vous êtes un pinceau. 582 00:25:19,720 --> 00:25:20,560 >> STEVEN: Brush. 583 00:25:20,560 --> 00:25:20,920 >> DAVID MALAN: OK. 584 00:25:20,920 --> 00:25:21,600 Et quoi d'autre? 585 00:25:21,600 --> 00:25:22,600 >> STEVEN: Et puis nous - 586 00:25:22,600 --> 00:25:22,915 >> DAVID MALAN: Nous avons poussé 17. 587 00:25:22,915 --> 00:25:24,760 >> STEVEN: Nous collons 17 au-dessus, donc - 588 00:25:24,760 --> 00:25:25,710 >> DAVID MALAN: OK, c'est bon. 589 00:25:25,710 --> 00:25:27,040 >> STEVEN: - faire tomber. 590 00:25:27,040 --> 00:25:27,530 >> DAVID MALAN: Très bien. 591 00:25:27,530 --> 00:25:27,940 Il devient facile. 592 00:25:27,940 --> 00:25:29,300 Je ne vais pas vous aider à ce moment. 593 00:25:29,300 --> 00:25:30,510 Poussez 22. 594 00:25:30,510 --> 00:25:31,720 >> STEVEN: Terminé. 595 00:25:31,720 --> 00:25:34,870 Devenir une gomme. 596 00:25:34,870 --> 00:25:37,340 Je deviens un pinceau. 597 00:25:37,340 --> 00:25:39,340 Et puis je mets 22. 598 00:25:39,340 --> 00:25:40,100 >> DAVID MALAN: 22. 599 00:25:40,100 --> 00:25:40,620 Excellente. 600 00:25:40,620 --> 00:25:41,380 Donc, une fois de plus. 601 00:25:41,380 --> 00:25:44,280 Je vais maintenant pousser dans la pile 26. 602 00:25:44,280 --> 00:25:46,350 >> STEVEN: Ooh. 603 00:25:46,350 --> 00:25:50,278 Oh mon dieu. 604 00:25:50,278 --> 00:25:52,520 Vous m'avez vraiment pris au dépourvu. 605 00:25:52,520 --> 00:25:53,703 >> DAVID MALAN: Vous ne l'avez pas vu venir? 606 00:25:53,703 --> 00:25:55,930 >> STEVEN: Je n'ai pas vu venir. 607 00:25:55,930 --> 00:25:58,756 Pourrions-nous la capacité re-départ? 608 00:25:58,756 --> 00:25:59,790 >> DAVID MALAN: C'est une bonne question. 609 00:25:59,790 --> 00:26:02,360 Donc, nous avons sorte de nous peignons dans un coin ici. 610 00:26:02,360 --> 00:26:06,740 Il n'y a vraiment rien de bon sur pour Steven parce que nous avons prévu ce tableau 611 00:26:06,740 --> 00:26:09,130 statiquement, pour ainsi dire, à l'intérieur de la structure de données. 612 00:26:09,130 --> 00:26:12,170 Et nous avons essentiellement codé en dur qu'il soit de taille trois. 613 00:26:12,170 --> 00:26:14,170 Donc, nous ne pouvons pas vraiment le réaffecter. 614 00:26:14,170 --> 00:26:20,020 >> Nous pourrions si nous allions revenir, nous redéfinis plateaux d'être un pointeur qui 615 00:26:20,020 --> 00:26:22,300 Nous utilisons ensuite malloc à la mémoire de main. 616 00:26:22,300 --> 00:26:25,050 Parce que si nous avons la mémoire de le tas via malloc, nous 617 00:26:25,050 --> 00:26:26,430 pourrait alors libérer. 618 00:26:26,430 --> 00:26:29,630 Mais avant de le libérer, nous pourrions réaffecter un plus gros morceau de la mémoire, 619 00:26:29,630 --> 00:26:31,330 mettre à jour le pointeur, et ainsi de suite. 620 00:26:31,330 --> 00:26:33,500 Mais pour l'instant, c'est vraiment Le mieux qu'on puisse faire. 621 00:26:33,500 --> 00:26:36,360 Push et pop sont probablement va d'avoir à signaler une erreur. 622 00:26:36,360 --> 00:26:40,270 >> Ainsi, par exemple, notre mise en œuvre de poussée pourrait retourner un booléen qui 623 00:26:40,270 --> 00:26:42,390 précédemment retourné vrai, vrai, vrai. 624 00:26:42,390 --> 00:26:48,390 Mais la quatrième fois, il va falloir pour revenir faux, par exemple. 625 00:26:48,390 --> 00:26:48,540 Très bien. 626 00:26:48,540 --> 00:26:49,540 Très bien fait. 627 00:26:49,540 --> 00:26:50,060 Félicitations. 628 00:26:50,060 --> 00:26:52,160 Vous avez gagné votre boule de stress aujourd'hui. 629 00:26:52,160 --> 00:26:53,110 >> [Applaudissements] 630 00:26:53,110 --> 00:26:54,382 >> STEVEN: Je vous remercie. 631 00:26:54,382 --> 00:26:55,680 >> DAVID MALAN: Merci. 632 00:26:55,680 --> 00:26:59,740 OK, donc ce ne semble pas être beaucoup d'un pas en avant, non? 633 00:26:59,740 --> 00:27:01,410 Nous avons décrit cette structure de données. 634 00:27:01,410 --> 00:27:02,320 Il a été convaincant, non? 635 00:27:02,320 --> 00:27:03,200 Systèmes d'exploitation comme cela. 636 00:27:03,200 --> 00:27:06,360 Apparemment, le web peut faire usage de cela, et d'autres applications encore. 637 00:27:06,360 --> 00:27:10,870 Mais quelle limitation stupide que nous sommes sauvegarder pour trier de la semaine deux limites 638 00:27:10,870 --> 00:27:12,880 où nous avons fixé des tableaux de taille. 639 00:27:12,880 --> 00:27:15,010 >> Donc, il ya effectivement un couple de façons nous pourrions résoudre ce problème. 640 00:27:15,010 --> 00:27:18,750 Nous pourrions allouer dynamiquement le tableau, pas de coder en dur comme je l'ai 641 00:27:18,750 --> 00:27:22,600 fait ici, mais au lieu de re-déclarer ce, juste pour être clair, comme 642 00:27:22,600 --> 00:27:23,830 quelque chose comme ça. 643 00:27:23,830 --> 00:27:29,040 Int * plateaux, ne pas décider sur encore une capacité. 644 00:27:29,040 --> 00:27:35,460 Mais quand je déclare la pile ailleurs dans mon code, je pourrais alors appeler malloc, 645 00:27:35,460 --> 00:27:38,250 obtenir l'adresse d'un morceau de mémoire, et je ne pouvais assigner 646 00:27:38,250 --> 00:27:39,980 cette adresse à plateaux. 647 00:27:39,980 --> 00:27:43,340 >> Et puis, parce que c'est juste un morceau de mémoire, je pourrais continuer à utiliser carré 648 00:27:43,340 --> 00:27:45,450 Unité de support de la manière habituelle. 649 00:27:45,450 --> 00:27:49,020 Parce qu'encore une fois, il ya une sorte de ce équivalent fonctionnel de tableaux et 650 00:27:49,020 --> 00:27:50,820 morceaux de mémoire qui viennent retour de malloc. 651 00:27:50,820 --> 00:27:53,090 Nous pouvons traiter un comme l'autre en utilisant l'arithmétique de pointeur ou 652 00:27:53,090 --> 00:27:54,440 notation entre crochets. 653 00:27:54,440 --> 00:27:55,660 Donc, c'est une approche. 654 00:27:55,660 --> 00:28:00,120 >> Mais comment pourrions-nous mettre en œuvre cette même structure de données, potentiellement? 655 00:28:00,120 --> 00:28:00,280 Droite? 656 00:28:00,280 --> 00:28:04,530 Je me sens comme nous venons de régler cette problème comme il ya une semaine. 657 00:28:04,530 --> 00:28:08,860 Quelle était la solution à ce problème que Steven a couru en? 658 00:28:08,860 --> 00:28:10,370 Alors listes liées, à droite. 659 00:28:10,370 --> 00:28:13,410 >> Si le problème est que nous sommes en peinture nous dans un coin en allouant 660 00:28:13,410 --> 00:28:17,580 à l'avance trop peu de mémoire que nous puis avoir à traiter avec quelque sorte, eh bien, 661 00:28:17,580 --> 00:28:19,880 pourquoi ne pas simplement éviter que question tout à fait? 662 00:28:19,880 --> 00:28:26,170 Pourquoi ne pas simplement déclarer plateaux d'être un pointeur vers un noeud, ergo une liste chaînée, 663 00:28:26,170 --> 00:28:30,740 et puis tout simplement attribuer de nouveaux nœuds chaque fois que Steven nécessaire pour s'adapter à un 664 00:28:30,740 --> 00:28:32,400 nombre dans la structure de données. 665 00:28:32,400 --> 00:28:34,200 >> Donc, l'image aurait à changer. 666 00:28:34,200 --> 00:28:38,220 Ça ne va pas être aussi propre et aussi simple que un tableau de trois entiers. 667 00:28:38,220 --> 00:28:42,970 Maintenant, il va y avoir un pointeur vers une struct, et que struct va 668 00:28:42,970 --> 00:28:44,830 avoir un int et un pointeur prochaine. 669 00:28:44,830 --> 00:28:47,670 Il va conduire via ce pointeur à une autre structure d' 670 00:28:47,670 --> 00:28:48,600 une autre telle structure. 671 00:28:48,600 --> 00:28:50,560 Donc, l'image serait effectivement obtenir un peu malpropre. 672 00:28:50,560 --> 00:28:52,950 Et nous aurions flèches attachant tout ensemble. 673 00:28:52,950 --> 00:28:55,280 >> Mais c'est bien, non, parce que nous avons vu comment faire cela. 674 00:28:55,280 --> 00:28:58,180 Et une fois que vous obtenez à l'aise quelque chose comme une mise en œuvre liée 675 00:28:58,180 --> 00:29:01,450 liste, que vous avez à faire si vous choisir d'appliquer une table de hachage avec 676 00:29:01,450 --> 00:29:05,120 chaînage séparé pour p-set 6, vous pouvez utiliser en tant que bloc de construction, ou une 677 00:29:05,120 --> 00:29:08,870 ingrédient, ou dans Scratch parler, un procédure, quelque chose que vous mettez, vous 678 00:29:08,870 --> 00:29:12,560 créé votre propre morceau de puzzle que vous pourrez ensuite réutiliser. 679 00:29:12,560 --> 00:29:17,090 Compromis ainsi, mais les solutions possibles que nous avons effectivement vu auparavant. 680 00:29:17,090 --> 00:29:20,560 >> Donc, très souvent, vous voyez cela tous an ou deux, lorsque les rejets d'Apple 681 00:29:20,560 --> 00:29:23,060 quelque chose de nouveau, et tous les gens fous line up à l'extérieur de la Pomme 682 00:29:23,060 --> 00:29:27,050 Store pour acheter leur marginal moderniser le matériel. 683 00:29:27,050 --> 00:29:30,420 Je dis cela, c'est OK, parce que Je suis une de ces personnes. 684 00:29:30,420 --> 00:29:35,140 Alors, quel genre de structure de données pourrait représenter cette réalité? 685 00:29:35,140 --> 00:29:36,980 >> Eh bien, appelons-le une file d'attente, une ligne. 686 00:29:36,980 --> 00:29:40,270 So British dirais que c'est typiquement une file d'attente de toute façon, c'est un joli nom. 687 00:29:40,270 --> 00:29:44,960 Et les deux opérations qu'une file d'attente prendra en charge que nous appellerons une enqueue 688 00:29:44,960 --> 00:29:48,900 opération et une opération dequeue, qui sont similaires dans 689 00:29:48,900 --> 00:29:50,120 esprit de push et pop. 690 00:29:50,120 --> 00:29:54,060 C'est juste une sorte de différent dans convention, ce que nous appelons ces derniers. 691 00:29:54,060 --> 00:29:57,680 Mais pour en file d'attente signifie quelque chose à ajouter ou insérer dans la structure de données. 692 00:29:57,680 --> 00:29:59,570 Pour dequeue signifie pour le supprimer. 693 00:29:59,570 --> 00:30:05,170 Mais alors que la pile était une des données LIFO la structure, une file d'attente est dans une première, 694 00:30:05,170 --> 00:30:06,740 d'abord sur la structure de données. 695 00:30:06,740 --> 00:30:10,050 >> Si vous êtes la première personne en ligne, vous serez la première personne à obtenir 696 00:30:10,050 --> 00:30:12,420 hors de la ligne et acheter votre nouvel appareil. 697 00:30:12,420 --> 00:30:18,070 Imaginez comment bouleversé ces personnes seraient si Apple a plutôt utilisé une pile, pour 698 00:30:18,070 --> 00:30:21,250 Ainsi, pour mettre en œuvre la cueillette de votre nouveau jouet. 699 00:30:21,250 --> 00:30:24,310 Donc, les files d'attente de sens, certes, et nous pouvons penser à toutes sortes de 700 00:30:24,310 --> 00:30:27,480 applications, sans doute, des files d'attente, surtout quand vous voulez l'équité. 701 00:30:27,480 --> 00:30:30,040 Alors, comment pouvons-nous mettre en œuvre ces en tant que structure de données? 702 00:30:30,040 --> 00:30:33,680 >> Eh bien, je propose que nous pourrions besoin de le faire de cette façon. 703 00:30:33,680 --> 00:30:35,225 Donc, je vais devoir maintenant nombres. 704 00:30:35,225 --> 00:30:38,190 Donc, nous allons rester simple et ne parler nécessairement en termes de plateaux. 705 00:30:38,190 --> 00:30:40,220 Seulement des chiffres que les gens de acquis. 706 00:30:40,220 --> 00:30:43,760 Capacité va, encore une fois, fixer le nombre total de personnes qui peuvent être en 707 00:30:43,760 --> 00:30:46,900 cette ligne, comme trois ou toute autre valeur. 708 00:30:46,900 --> 00:30:50,760 >> Mais je propose que j'ai besoin de garder une trace non seulement de la taille de l' 709 00:30:50,760 --> 00:30:52,370 file d'attente, combien de choses sont en elle. 710 00:30:52,370 --> 00:30:56,310 Donc, la taille est la taille actuelle, la capacité est la taille maximale. 711 00:30:56,310 --> 00:30:58,540 Juste encore une fois, nomenclature par convention. 712 00:30:58,540 --> 00:31:03,680 Pourquoi ai-je besoin d'un int supplémentaire à l'intérieur d'une file d'attente pour garder trace de qui est dans 713 00:31:03,680 --> 00:31:05,365 avant de la ligne? 714 00:31:05,365 --> 00:31:07,930 715 00:31:07,930 --> 00:31:10,910 Pourquoi dois-je faire dans ce cas? 716 00:31:10,910 --> 00:31:14,750 717 00:31:14,750 --> 00:31:16,190 >> Eh bien, comment est cette image va changer? 718 00:31:16,190 --> 00:31:19,280 Je peux probablement réutiliser plus de cette image. 719 00:31:19,280 --> 00:31:21,480 Permettez-moi d'aller de l'avant et d'effacer ce qu'il ya ici. 720 00:31:21,480 --> 00:31:24,580 Nous allons donner à cette légèrement nom différent ici. 721 00:31:24,580 --> 00:31:28,930 Débarrassons-nous du 17 Débarrassons du 9, débarrassons-nous de la 3. 722 00:31:28,930 --> 00:31:30,410 Et nous allons ajouter une autre chose. 723 00:31:30,410 --> 00:31:34,710 Je propose que j'ai besoin de garder une trace de l'avant de la liste, ce qui est juste 724 00:31:34,710 --> 00:31:35,570 va être un int ainsi. 725 00:31:35,570 --> 00:31:36,550 Et nous allons garder les choses simples. 726 00:31:36,550 --> 00:31:37,740 Aucune liste liée pour l'instant. 727 00:31:37,740 --> 00:31:40,900 >> Nous admettons que nous allons heurter à cette limite. 728 00:31:40,900 --> 00:31:43,720 Mais qu'est-ce que je veux voir se passer cette fois? 729 00:31:43,720 --> 00:31:47,240 Donc je suppose aller de l'avant et le premier personne vient en ligne, et 730 00:31:47,240 --> 00:31:48,560 c'est le numéro 9. 731 00:31:48,560 --> 00:31:49,680 Nous avons balles anti-stress. 732 00:31:49,680 --> 00:31:51,330 Puis-je voler, disons, deux ou trois personnes? 733 00:31:51,330 --> 00:31:52,690 Un, deux, trois? 734 00:31:52,690 --> 00:31:53,120 Venez sur place. 735 00:31:53,120 --> 00:31:56,022 Dès l'avant, parce que nous ferons celui-rapide. 736 00:31:56,022 --> 00:31:59,415 >> Chacun d'entre vous va maintenant être un garçon de ventilateur en ligne chez Apple. 737 00:31:59,415 --> 00:32:03,970 738 00:32:03,970 --> 00:32:06,210 Vous ne recevrez pas de matériel Apple à la fin de ce bien. 739 00:32:06,210 --> 00:32:06,500 Très bien. 740 00:32:06,500 --> 00:32:09,430 Donc, vous êtes numéro 9, vous êtes numéro 17, numéro 22. 741 00:32:09,430 --> 00:32:12,130 Ces chiffres sont arbitraires, comme ID étudiant ou autres joyeusetés. 742 00:32:12,130 --> 00:32:14,550 Et dans quelques instants, nous allons commencer pour commencer à ajouter des choses. 743 00:32:14,550 --> 00:32:16,000 Et je vais courir le conseil ici ce temps. 744 00:32:16,000 --> 00:32:19,570 >> Donc dans ce cas, j'ai initialisé l'avant pour être - 745 00:32:19,570 --> 00:32:22,380 En fait, je ne m'inquiète pas vraiment ce que l' avant est, en raison de la taille est égale à zéro. 746 00:32:22,380 --> 00:32:24,480 Donc, cela pourrait tout aussi bien être un point d'interrogation. 747 00:32:24,480 --> 00:32:26,170 Ce sont tous des points d'interrogation. 748 00:32:26,170 --> 00:32:29,880 Alors maintenant, nous allons commencer à réellement voir personnes faisaient la queue à la boutique. 749 00:32:29,880 --> 00:32:33,320 >> Donc, si le numéro 9, vous êtes le premier là à 5 heures, aller de l'avant et la queue, 750 00:32:33,320 --> 00:32:34,210 ou la veille. 751 00:32:34,210 --> 00:32:34,580 OK. 752 00:32:34,580 --> 00:32:35,940 Alors maintenant 9 est ici. 753 00:32:35,940 --> 00:32:37,940 Ainsi, la figure 9 est à l'avant de la liste. 754 00:32:37,940 --> 00:32:41,440 Donc, je vais aller de l'avant et mettre à jour la taille de ces données actuelles 755 00:32:41,440 --> 00:32:44,740 Structure de ne pas être plus 0, mais pour être 1. 756 00:32:44,740 --> 00:32:47,630 Je vais mettre 9 à l' début de la liste. 757 00:32:47,630 --> 00:32:51,020 Permettez-moi d'aller de l'avant et basculer l'écran afin que nous puissions voir devant nous ici. 758 00:32:51,020 --> 00:32:53,220 >> Et maintenant, qu'est-ce que je veux de mettre à l'avant? 759 00:32:53,220 --> 00:32:56,240 Je vais garder la trace que l' avant de la file d'attente en ce moment 760 00:32:56,240 --> 00:32:58,570 est à l'emplacement 0. 761 00:32:58,570 --> 00:33:00,510 Parce que ce qui est à côté va se passer? 762 00:33:00,510 --> 00:33:03,000 Eh bien, maintenant, je suppose ENQUEUE 17 aussi. 763 00:33:03,000 --> 00:33:04,510 Embarquez en ligne là-bas. 764 00:33:04,510 --> 00:33:07,060 Et encore, le type de porte à l' magasin va être ici. 765 00:33:07,060 --> 00:33:08,700 Alors maintenant, j'ai ajouté 17. 766 00:33:08,700 --> 00:33:10,810 Et même si ces gars-là sont de blocage l'écran, c'est OK, 767 00:33:10,810 --> 00:33:12,300 parce que nous pouvons le voir ici. 768 00:33:12,300 --> 00:33:12,910 Désolé. 769 00:33:12,910 --> 00:33:13,810 >> PUBLIC: Nous pouvons passer - 770 00:33:13,810 --> 00:33:14,660 >> DAVID MALAN: Non, ce n'est pas grave. 771 00:33:14,660 --> 00:33:16,000 C'est énorme là-haut. 772 00:33:16,000 --> 00:33:18,580 Donc 17 est maintenant à l'intérieur de la file d'attente. 773 00:33:18,580 --> 00:33:21,332 J'ai besoin de mettre à jour qui domaines maintenant bien? 774 00:33:21,332 --> 00:33:23,210 OK, certainement taille. 775 00:33:23,210 --> 00:33:26,430 Et que diriez-vous avant? 776 00:33:26,430 --> 00:33:27,040 OK, no. 777 00:33:27,040 --> 00:33:30,200 Avant ne doit pas changer, parce que Contrairement à une pile, nous 778 00:33:30,200 --> 00:33:31,370 vouloir maintenir l'équité. 779 00:33:31,370 --> 00:33:35,150 Donc, si 9 est venu en premier, nous voulons 9 d'être le premier sur la ligne 780 00:33:35,150 --> 00:33:36,420 et dans le magasin. 781 00:33:36,420 --> 00:33:37,220 >> En fait, nous allons voir cela. 782 00:33:37,220 --> 00:33:42,235 Avant de nous insérons 22, nous allons aller de l'avant et dequeue 9. 783 00:33:42,235 --> 00:33:42,970 Quel est votre nom? 784 00:33:42,970 --> 00:33:43,680 >> AUDIENCE: Jake. 785 00:33:43,680 --> 00:33:45,440 >> DAVID MALAN: Jake va être retirés lors maintenant. 786 00:33:45,440 --> 00:33:48,050 Ainsi, vous obtenez de marcher dans le magasin. 787 00:33:48,050 --> 00:33:49,880 Et prétendre que le magasin est là-bas. 788 00:33:49,880 --> 00:33:51,970 Alors maintenant, ce qu'il faut - dit-dit-dit! 789 00:33:51,970 --> 00:33:53,400 Que faut-il maintenant? 790 00:33:53,400 --> 00:33:54,490 décision de conception. 791 00:33:54,490 --> 00:33:56,825 Donc pas un mauvais instinct, mais - quel est votre nom? 792 00:33:56,825 --> 00:33:57,090 >> AUDIENCE: David. 793 00:33:57,090 --> 00:33:57,500 >> DAVID MALAN: David. 794 00:33:57,500 --> 00:33:58,810 Alors, que fait David? 795 00:33:58,810 --> 00:34:02,590 Il essayait de tri de fixer les données structure et déménagement de son emplacement 796 00:34:02,590 --> 00:34:04,100 dans l'ancien emplacement de Jake. 797 00:34:04,100 --> 00:34:06,740 Et c'est très bien si nous sommes prêts à accepter cela comme une 798 00:34:06,740 --> 00:34:08,199 détail d'implémentation. 799 00:34:08,199 --> 00:34:11,100 Mais d'abord, nous allons mettre à jour les données Structure avant de faire cela. 800 00:34:11,100 --> 00:34:14,139 Parce que je ne suis pas aimer l'idée de tout les gens passer dans cette ligne. 801 00:34:14,139 --> 00:34:17,360 >> Ce n'est pas un gros problème si David fait avec une étape, mais encore une fois, pensez à 802 00:34:17,360 --> 00:34:20,360 lorsque nous avons eu huit volontaires sur le stade et nous avons fait comme insertion 803 00:34:20,360 --> 00:34:22,600 Trier, où nous devions commencer déplacer tout le monde autour. 804 00:34:22,600 --> 00:34:23,790 Cela m'a cher, non? 805 00:34:23,790 --> 00:34:28,330 Cela me fait grincer des dents sur grand O de N, O grand carré de n fois. 806 00:34:28,330 --> 00:34:30,650 Il ne se sent pas comme un résultat idéal. 807 00:34:30,650 --> 00:34:32,080 >> Donc, nous allons simplement mettre à jour ce sujet. 808 00:34:32,080 --> 00:34:35,120 Ainsi, la taille de la file d'attente n'est plus 2. 809 00:34:35,120 --> 00:34:37,090 C'est maintenant simplement 1. 810 00:34:37,090 --> 00:34:40,360 Mais je peux maintenant mettre à jour quelque chose Je n'ai pas mis à jour avant le 811 00:34:40,360 --> 00:34:41,130 début de la liste. 812 00:34:41,130 --> 00:34:45,420 Je ne pouvais tout simplement dire, c'est que 1 emplacement? 813 00:34:45,420 --> 00:34:49,770 Nous avons donc maintenant la valeur des ordures ici, valeur des ordures ici, et David dans le 814 00:34:49,770 --> 00:34:51,469 milieu de ces ordures. 815 00:34:51,469 --> 00:34:54,980 Mais la structure de données est encore intacte. 816 00:34:54,980 --> 00:34:58,540 >> Et en fait, je n'ai même pas besoin d' changer ancien numéro de Jake 817 00:34:58,540 --> 00:35:00,460 9, car qui se soucie. 818 00:35:00,460 --> 00:35:04,470 J'ai maintenant suffisamment d'informations dans le taille que je sais qu'il ya une personne dans 819 00:35:04,470 --> 00:35:05,030 cette file d'attente. 820 00:35:05,030 --> 00:35:08,340 Et je sais que cette personne est à l'emplacement 1, et non 0. 821 00:35:08,340 --> 00:35:09,760 Je ne compte pas. 822 00:35:09,760 --> 00:35:11,300 Donc 1 ainsi. 823 00:35:11,300 --> 00:35:13,410 Ainsi, la structure de données est toujours OK. 824 00:35:13,410 --> 00:35:14,330 >> Eh bien, qu'est-ce qui se passe ensuite? 825 00:35:14,330 --> 00:35:15,010 Le enqueue Let - 826 00:35:15,010 --> 00:35:15,370 Quel est votre nom? 827 00:35:15,370 --> 00:35:16,160 >> AUDIENCE: Callen. 828 00:35:16,160 --> 00:35:16,580 >> DAVID MALAN: Callen. 829 00:35:16,580 --> 00:35:20,770 Allons ENQUEUE un Callen, et 22 est maintenant dans la file d'attente. 830 00:35:20,770 --> 00:35:22,300 Alors maintenant, ce qui doit changer ici? 831 00:35:22,300 --> 00:35:24,380 Avant ne va pas changer, évidemment. 832 00:35:24,380 --> 00:35:27,160 Taille va changer à 2 fois. 833 00:35:27,160 --> 00:35:31,590 Et 22 finit ici, 9 est toujours présent, mais c'est effectivement un 834 00:35:31,590 --> 00:35:32,600 valeur des ordures maintenant. 835 00:35:32,600 --> 00:35:35,910 C'est juste un vestige de Jake passé. 836 00:35:35,910 --> 00:35:39,200 >> Alors maintenant ce qui se passe si Je DEQUEUE David? 837 00:35:39,200 --> 00:35:41,560 Une dernière opération, dequeue David. 838 00:35:41,560 --> 00:35:46,070 Nous pourrions passer, mais je proposer LET'S faire le moins de travail possible. 839 00:35:46,070 --> 00:35:50,280 Maintenant, ma structure de données va sauvegarder la taille varie de 2 à 1. 840 00:35:50,280 --> 00:35:53,730 Mais l'avant de la file d'attente devient maintenant 2. 841 00:35:53,730 --> 00:35:56,640 Je n'ai pas besoin de modifier ces numéros pour l'instant, parce qu'ils sont 842 00:35:56,640 --> 00:35:58,230 seulement des valeurs parasites. 843 00:35:58,230 --> 00:35:59,720 >> Mais maintenant ce qui se passe? 844 00:35:59,720 --> 00:36:03,280 Supposons que je me ENQUEUE, 26? 845 00:36:03,280 --> 00:36:05,890 Je me sens chez moi ici. 846 00:36:05,890 --> 00:36:06,890 Je suis donc d'être en file d'attente. 847 00:36:06,890 --> 00:36:08,760 Donc je sorte de ma place ici. 848 00:36:08,760 --> 00:36:11,300 Et même si vous n'avez pas tout à fait apprécier cette visuellement sur la scène, 849 00:36:11,300 --> 00:36:15,075 parce que nous avons beaucoup de place, je devrais pas être ici, pourquoi? 850 00:36:15,075 --> 00:36:16,290 >> AUDIENCE: Vous êtes hors des limites. 851 00:36:16,290 --> 00:36:16,370 >> DAVID MALAN: C'est vrai. 852 00:36:16,370 --> 00:36:16,940 Je suis hors des limites. 853 00:36:16,940 --> 00:36:19,330 J'ai indexés au-delà de la des bornes de ce tableau. 854 00:36:19,330 --> 00:36:23,420 Je devrais être dans l'un des trois emplacements possibles. 855 00:36:23,420 --> 00:36:25,150 Maintenant, où est plus naturel d'aller? 856 00:36:25,150 --> 00:36:27,760 Je propose que nous à effet de levier une semaine un tour. 857 00:36:27,760 --> 00:36:30,150 L'opérateur mod, pourcentage. 858 00:36:30,150 --> 00:36:36,850 Parce que je suis techniquement debout à emplacement 3, mais je ne 3 capacité de mod, 859 00:36:36,850 --> 00:36:40,250 SO 3, un signe pour cent, 3 - 860 00:36:40,250 --> 00:36:40,970 capacité est 3. 861 00:36:40,970 --> 00:36:41,720 Qu'est-ce que c'est? 862 00:36:41,720 --> 00:36:43,700 Quel est le reste quand vous divisez 3 par 3? 863 00:36:43,700 --> 00:36:44,070 0. 864 00:36:44,070 --> 00:36:48,140 >> Alors, qui me met été Jake était, ce qui est réellement bon. 865 00:36:48,140 --> 00:36:50,370 Alors maintenant, la mise en œuvre de cette chose va 866 00:36:50,370 --> 00:36:51,250 être un peu mal à la tête. 867 00:36:51,250 --> 00:36:53,740 C'est vraiment juste une ligne des maux de tête, de code. 868 00:36:53,740 --> 00:36:56,580 Mais au moins, maintenant, il ya des ordures valeur ici, mais il ya deux 869 00:36:56,580 --> 00:36:57,910 ints légitimes ici. 870 00:36:57,910 --> 00:37:04,160 Et je prétends que, maintenant que nous avons fait exactement ce que nous devons faire, aussi longtemps que 871 00:37:04,160 --> 00:37:08,600 nous changeons ce que Jake valeur était à 26. 872 00:37:08,600 --> 00:37:12,110 >> Nous avons maintenant suffisamment d'informations encore pour maintenir l'intégrité 873 00:37:12,110 --> 00:37:13,060 de cette structure de données. 874 00:37:13,060 --> 00:37:17,160 Nous sommes encore un peu de chance lorsque nous vouloir insérer quatre ou plus totale 875 00:37:17,160 --> 00:37:20,740 éléments, mais je peux au moins faire assez utilisation efficace de cette constante 876 00:37:20,740 --> 00:37:21,740 temps, en fait. 877 00:37:21,740 --> 00:37:27,150 Je n'ai pas à vous soucier de déplacement tout le monde, comme l'inclinaison de David était. 878 00:37:27,150 --> 00:37:30,816 >> Toutes les questions sur piles, ou cette file d'attente? 879 00:37:30,816 --> 00:37:32,184 >> AUDIENCE: Est-ce la raison pour laquelle vous avez besoin de taille afin que vous sachiez 880 00:37:32,184 --> 00:37:34,010 où d'avoir une personne? 881 00:37:34,010 --> 00:37:34,770 >> DAVID MALAN: Exactement. 882 00:37:34,770 --> 00:37:38,230 J'ai besoin de connaître la taille du tableau parce que j'ai besoin de savoir exactement comment 883 00:37:38,230 --> 00:37:41,940 nombre de ces valeurs sont légitimes, et pour que je puisse trouver où mettre 884 00:37:41,940 --> 00:37:42,800 la personne suivante. 885 00:37:42,800 --> 00:37:43,300 Exactement. 886 00:37:43,300 --> 00:37:44,580 La taille est - 887 00:37:44,580 --> 00:37:46,360 en fait, nous n'avons pas à jour ce moment. 888 00:37:46,360 --> 00:37:48,380 J'ai ajouté à 26. 889 00:37:48,380 --> 00:37:51,760 La taille est maintenant, pas 1, mais 2. 890 00:37:51,760 --> 00:37:57,780 Alors maintenant, c'est bien m'aide à trouver l' tête de la liste, qui n'est pas 0, pas 891 00:37:57,780 --> 00:37:59,250 1, mais est égal à 2. 892 00:37:59,250 --> 00:38:01,665 La façade de la liste est en effet le numéro 22. 893 00:38:01,665 --> 00:38:05,120 Parce qu'il est venu en premier, alors il devrait être autorisés à entrer dans le magasin avant moi, 894 00:38:05,120 --> 00:38:08,780 même si visuellement je suis debout plus près du magasin. 895 00:38:08,780 --> 00:38:09,220 >> Tout va bien? 896 00:38:09,220 --> 00:38:12,410 Une salve d'applaudissements pour ces gars-là et nous allons leur faire sortir de là. 897 00:38:12,410 --> 00:38:17,090 >> [Applaudissements] 898 00:38:17,090 --> 00:38:18,150 >> DAVID MALAN: Je pourrais laisser vous gardez le plateau. 899 00:38:18,150 --> 00:38:20,760 Nous avons pu voir ce qui se passe si vous voulez, mais peut-être pas. 900 00:38:20,760 --> 00:38:21,590 Très bien. 901 00:38:21,590 --> 00:38:25,380 Alors quoi cela nous mène? 902 00:38:25,380 --> 00:38:28,900 Eh bien, permettez-moi de proposer qu'il y ait une Quelques autres structures de données que nous pourrions 903 00:38:28,900 --> 00:38:33,810 commencer à ajouter à notre trousse d'outils qui seront effectivement être tout à fait, tout à fait pertinent que 904 00:38:33,810 --> 00:38:35,270 nous plongeons dans des trucs web. 905 00:38:35,270 --> 00:38:38,150 Qui encore une fois, a une sorte de connexion d'arbres dans la forme de 906 00:38:38,150 --> 00:38:40,550 quelque chose qui s'appelle DOM, un document modèle d'objet. 907 00:38:40,550 --> 00:38:42,370 Mais nous verrons plus de que d'ici peu. 908 00:38:42,370 --> 00:38:46,260 >> Permettez-moi de proposer par définition que nous appeler arbre maintenant ce que vous savez peut-être que 909 00:38:46,260 --> 00:38:48,820 plus d'un arbre de la famille, où vous avoir un ancêtre à l' 910 00:38:48,820 --> 00:38:49,790 racines de l'arbre. 911 00:38:49,790 --> 00:38:54,480 Une matriarche patriarcale ou au Tout en haut de l'arbre. 912 00:38:54,480 --> 00:38:56,700 Sans leur conjoint, dans ce cas. 913 00:38:56,700 --> 00:39:00,940 Mais nous avons maintenant ce que nous appellerons enfants, qui sont les nœuds qui pendent 914 00:39:00,940 --> 00:39:05,480 hors l'enfant vers la gauche ou la droite enfant, flèches comme représenté ici. 915 00:39:05,480 --> 00:39:10,490 >> En d'autres termes, dans une structure de données d'arbre en informatique, un arbre a zéro 916 00:39:10,490 --> 00:39:11,480 ou plusieurs nœuds. 917 00:39:11,480 --> 00:39:13,500 Si elle a au moins un noeud, C'est ce qu'on appelle la racine. 918 00:39:13,500 --> 00:39:15,700 Ce sont les choses visuellement que nous tirons vers le haut. 919 00:39:15,700 --> 00:39:20,280 Et ce nœud, comme n'importe quel autre nœud, peut avoir zéro, un, ou deux, ou trois, 920 00:39:20,280 --> 00:39:23,600 Cependant beaucoup d'enfants ou le Structure de données prend en charge. 921 00:39:23,600 --> 00:39:29,150 Dans ce cas, la racine, stockant l' une valeur, a deux enfants, 2 et 3, 922 00:39:29,150 --> 00:39:33,020 de sorte que nous appelons généralement 2 à gauche enfant et le droit de l'enfant 3. 923 00:39:33,020 --> 00:39:36,940 >> Et puis, quand nous nous attelons à 5, 6, et 7, 6 pourrait appeler l'enfant du milieu. 924 00:39:36,940 --> 00:39:38,940 Si vous avez quatre enfants, il devient confus. 925 00:39:38,940 --> 00:39:42,260 Donc, nous cessons d'utiliser ce genre de raccourci verbalement. 926 00:39:42,260 --> 00:39:44,580 Mais c'est vraiment juste un arbre généalogique. 927 00:39:44,580 --> 00:39:48,880 Et les feuilles sont ici les nœuds eux-mêmes n'ont pas d'enfants. 928 00:39:48,880 --> 00:39:52,540 Ils pendent vers le bas de l'arbre. 929 00:39:52,540 --> 00:39:56,940 >> Alors, comment pouvons-nous mettre en œuvre un arbre a seulement deux enfants au maximum? 930 00:39:56,940 --> 00:39:58,410 Nous appelons cela un arbre binaire. 931 00:39:58,410 --> 00:40:00,960 Bi à nouveau deux sens, en ce cas, comme avec binaire. 932 00:40:00,960 --> 00:40:04,830 Et donc il peut avoir zéro, un, ou deux enfants au maximum. 933 00:40:04,830 --> 00:40:08,650 >> Je propose que nous mettons en œuvre le noeud pour cette structure avec un int n, 934 00:40:08,650 --> 00:40:11,910 puis deux pointeurs, l'un appelé à gauche, l'un appelé droit. 935 00:40:11,910 --> 00:40:14,830 Mais ce sont juste agréable conventions arbitraires. 936 00:40:14,830 --> 00:40:18,170 Et ce qui est bien maintenant, surtout si vous sorte de se débattait avec conceptuellement 937 00:40:18,170 --> 00:40:21,300 récursivité, ou pensait que ce n'était pas vraiment une solution à quoi que ce soit, 938 00:40:21,300 --> 00:40:23,120 surtout si vous pouviez à court de mémoire. 939 00:40:23,120 --> 00:40:26,600 Maintenant que nous parlons de données des structures et des algorithmes qui permettent 940 00:40:26,600 --> 00:40:31,030 nous traversons et les manipuler, s'avère que la récursivité revient dans 941 00:40:31,030 --> 00:40:34,240 beaucoup plus convaincant si elle n'est pas belle façon. 942 00:40:34,240 --> 00:40:38,670 >> Donc, ce que je propose est la mise en œuvre d'une fonction de recherche. 943 00:40:38,670 --> 00:40:39,870 Étant donné deux entrées - 944 00:40:39,870 --> 00:40:41,570 Alors, pensez à cela comme une boîte noire. 945 00:40:41,570 --> 00:40:46,560 Étant donné deux entrées, n, un int, et un pointeur sur un arbre, un pointeur vers une 946 00:40:46,560 --> 00:40:50,020 noeud, ou vraiment la racine d'un arbre, je prétendent que cette fonction peut renvoyer 947 00:40:50,020 --> 00:40:53,530 vrai ou faux, cette valeur n est à l'intérieur de cet arbre. 948 00:40:53,530 --> 00:40:55,210 >> À l'intérieur de cette boîte noire? 949 00:40:55,210 --> 00:40:57,440 Eh bien, quatre branches. 950 00:40:57,440 --> 00:40:58,385 La première vient des chèques. 951 00:40:58,385 --> 00:41:00,490 Si l'arbre est nulle, il suffit de retourner faux. 952 00:41:00,490 --> 00:41:04,580 S'il n'y a pas de noeud, il n'ya pas de n, il n'y a pas de numéro, juste return false. 953 00:41:04,580 --> 00:41:12,330 Si bien que, n, la valeur que vous cherchez pour, est inférieure à arbre flèche n, et 954 00:41:12,330 --> 00:41:15,180 juste pour être clair, qu'est-ce que cela veut dire quand J'écris arbre, puis sur la flèche 955 00:41:15,180 --> 00:41:18,150 notation, n? 956 00:41:18,150 --> 00:41:18,690 Exactement. 957 00:41:18,690 --> 00:41:21,970 Cela signifie que déréférencer pointeur appelé arbre. 958 00:41:21,970 --> 00:41:26,750 Allez-y, puis pénétrer à l'intérieur de cette nœud et obtenir son champ appelé n. 959 00:41:26,750 --> 00:41:30,810 Et puis comparer le n réel qui a été passé dans Recherche contre elle. 960 00:41:30,810 --> 00:41:35,390 >> Donc, si n est inférieur à la valeur n dans le nœud de l'arbre lui-même, eh bien, 961 00:41:35,390 --> 00:41:36,720 ça veut dire quoi? 962 00:41:36,720 --> 00:41:40,690 Cela ne veut rien dire à première vue. 963 00:41:40,690 --> 00:41:40,900 Droite? 964 00:41:40,900 --> 00:41:45,560 Tout comme lorsque vous avez un tableau d' valeurs, vous aimerez certainement appliquer binaire 965 00:41:45,560 --> 00:41:48,290 rechercher une forme de fracture et conquérir. 966 00:41:48,290 --> 00:41:51,790 Mais ce postulat avons-nous besoin de faire pour la recherche binaire de travailler à tous 967 00:41:51,790 --> 00:41:54,510 dans le livre de téléphone et exemples précédents? 968 00:41:54,510 --> 00:41:55,530 >> Comment faire pour être triés. 969 00:41:55,530 --> 00:41:59,490 Donc, nous allons préciser la définition de l'arbre ici pas être juste un arbre, ce qui peut 970 00:41:59,490 --> 00:42:00,880 avoir n'importe quel nombre d'enfants. 971 00:42:00,880 --> 00:42:04,700 Pas seulement un arbre binaire, qui peut a 0, 1 ou 2 au maximum. 972 00:42:04,700 --> 00:42:09,700 Mais, comme un arbre binaire de recherche, ou BST, qui est juste une façon élégante de dire une 973 00:42:09,700 --> 00:42:15,430 arbre binaire de telle sorte que chaque noeud de enfant gauche, s'il est présent, est 974 00:42:15,430 --> 00:42:16,830 inférieur au noeud. 975 00:42:16,830 --> 00:42:20,170 Et chaque enfant le droit de nœud, s'il est présent, est supérieure 976 00:42:20,170 --> 00:42:21,740 que le nœud lui-même. 977 00:42:21,740 --> 00:42:25,200 >> Donc, en d'autres termes, si vous deviez dessiner l'arbre out, tous les numéros sont 978 00:42:25,200 --> 00:42:30,620 soigneusement équilibré comme celui-ci de sorte que si vous avez 55 comme la racine, 33 peut aller 979 00:42:30,620 --> 00:42:33,090 à sa gauche parce que c'est moins de 55 ans. 980 00:42:33,090 --> 00:42:36,430 77 peut aller à son droit parce que elle est supérieure à 55. 981 00:42:36,430 --> 00:42:40,750 Mais remarquez maintenant, la même définition, c'est une définition récursive verbalement, 982 00:42:40,750 --> 00:42:42,600 doit demander 33. 983 00:42:42,600 --> 00:42:47,610 Enfant de gauche de 33 doit être inférieure à lui, et à droite enfant de 33, 44, doit être 984 00:42:47,610 --> 00:42:48,580 plus grande que lui. 985 00:42:48,580 --> 00:42:51,670 >> Donc, c'est un arbre binaire de recherche, et Je propose, en utilisant un peu de 986 00:42:51,670 --> 00:42:53,910 récursivité, nous pouvons maintenant trouver n. 987 00:42:53,910 --> 00:42:59,160 Donc, si n est inférieur à la valeur n qui est noeud courant, je vais aller 988 00:42:59,160 --> 00:43:04,090 avant et plate, pour ainsi dire, et juste retourner quelle que soit la réponse est 989 00:43:04,090 --> 00:43:08,470 recherche de n sur le enfant de gauche de l'arbre. 990 00:43:08,470 --> 00:43:11,370 Notez à nouveau, cette fonction seulement s'attend à une étoile nœud, un 991 00:43:11,370 --> 00:43:12,780 pointeur à un noeud. 992 00:43:12,780 --> 00:43:17,360 Alors certes, je peux juste faire arbre flèche gauche, ce qui conduira 993 00:43:17,360 --> 00:43:18,400 moi vers un autre nœud. 994 00:43:18,400 --> 00:43:19,480 Mais quel est ce nœud? 995 00:43:19,480 --> 00:43:22,820 >> Eh bien, selon cette déclaration, gauche est juste un pointeur, de telle sorte que juste 996 00:43:22,820 --> 00:43:27,090 veut dire que je suis de passage à la fonction de recherche un pointeur différent, à savoir 997 00:43:27,090 --> 00:43:30,750 celui qui représente l'arbre de mon fils gauche. 998 00:43:30,750 --> 00:43:36,040 Donc dans ce cas, le pointeur à 33, si c'est notre échantillon d'entrée attendant, si 999 00:43:36,040 --> 00:43:40,740 n est supérieur à la valeur de n à l' nœud actuel dans l'arborescence, puis je suis 1000 00:43:40,740 --> 00:43:43,370 aller de l'avant et botté de dégagement dans l'autre direction et juste dire, je n'aime pas 1001 00:43:43,370 --> 00:43:47,280 savoir si cette valeur n est compris dans l'arbre, mais je sais pas si c'est le cas, c'est en bas de mon 1002 00:43:47,280 --> 00:43:49,090 branche droite, pour ainsi dire. 1003 00:43:49,090 --> 00:43:53,120 Alors permettez-moi j'appelle effectuer des recherches récursives, le passage d'un n fois, mais en passant dans un 1004 00:43:53,120 --> 00:43:54,580 pointeur à mon enfant droite. 1005 00:43:54,580 --> 00:44:00,020 >> En d'autres termes, si je suis actuellement à 55 et je suis à la recherche de 99, je sais que 99 1006 00:44:00,020 --> 00:44:04,270 est supérieur à 55, donc comme j'ai déchiré Il ya le téléphone semaines de livres et nous 1007 00:44:04,270 --> 00:44:07,140 s'est bien passé, même sommes-nous va aller ici. 1008 00:44:07,140 --> 00:44:11,960 Et je ne sais pas si c'est à ma droite enfant, et ce n'est pas, 77 est là, mais 1009 00:44:11,960 --> 00:44:13,210 Je sais que c'est dans cette direction. 1010 00:44:13,210 --> 00:44:18,770 J'appelle donc la recherche de mon enfant droite, 77, et laisser chiffre de recherche à partir 1011 00:44:18,770 --> 00:44:24,950 il si 99 dans ce arbitraire exemple est vraiment là. 1012 00:44:24,950 --> 00:44:26,900 >> Sinon, ce qui est le cas final? 1013 00:44:26,900 --> 00:44:28,620 Si l'arbre est nulle est un cas. 1014 00:44:28,620 --> 00:44:31,890 Si n est inférieur au noeud de courant de valeur est une autre affaire. 1015 00:44:31,890 --> 00:44:35,120 Si n est supérieur à l'actuel La valeur de noeud est un troisième cas. 1016 00:44:35,120 --> 00:44:38,250 Quel est le quatrième et dernier cas? 1017 00:44:38,250 --> 00:44:39,480 Je pense que nous sommes hors des cas, non? 1018 00:44:39,480 --> 00:44:44,690 Il faut que n est dans l' noeud courant que je suis sur. 1019 00:44:44,690 --> 00:44:49,640 >> Donc, si je suis à la recherche de 55 à ce stade dans l'histoire, cette branche de l' 1020 00:44:49,640 --> 00:44:51,780 arbre reviendrait vrai. 1021 00:44:51,780 --> 00:44:55,380 Donc ce qui est intéressant ici, c'est que nous en fait, à la différence semaines passées, nous avons nature 1022 00:44:55,380 --> 00:44:56,740 d'avoir deux cas de base. 1023 00:44:56,740 --> 00:44:58,300 Et ils n'ont pas à être tout en haut. 1024 00:44:58,300 --> 00:45:01,390 Le dessus est un cas de base, parce que si l' arbre est nul, il n'y a rien à faire. 1025 00:45:01,390 --> 00:45:03,410 Il suffit de retourner un disque codé la valeur false. 1026 00:45:03,410 --> 00:45:07,400 >> La branche inférieure est en quelque sorte le défaut, selon laquelle, si nous avons vérifié 1027 00:45:07,400 --> 00:45:11,550 null, nous avons vérifié si elle doit être à gauche, mais il ne devrait pas être, nous avons 1028 00:45:11,550 --> 00:45:14,640 vérifié si elle doit être juste, mais il ne devrait pas être, clairement, il doit être 1029 00:45:14,640 --> 00:45:15,870 là où nous sommes. 1030 00:45:15,870 --> 00:45:16,780 C'est un cas de base. 1031 00:45:16,780 --> 00:45:19,920 Donc, il ya deux cas récursifs il pris en sandwich au milieu. 1032 00:45:19,920 --> 00:45:21,630 Mais j'aurais pu écrire ce dans n'importe quel ordre. 1033 00:45:21,630 --> 00:45:24,520 Je pensais que ça sorte de feutre naturel vérifier d'abord d'une erreur possible, 1034 00:45:24,520 --> 00:45:28,340 puis vérifiez gauche, puis cochez à droite, puis supposons que vous êtes au niveau du noeud 1035 00:45:28,340 --> 00:45:30,630 vous êtes réellement à la recherche d'. 1036 00:45:30,630 --> 00:45:36,240 >> Alors pourquoi cela pourrait-il être utile? 1037 00:45:36,240 --> 00:45:37,910 Ainsi, il s'avère - 1038 00:45:37,910 --> 00:45:42,110 et permettez-moi de passer à un teaser ici c'est sur le web. 1039 00:45:42,110 --> 00:45:44,920 Nous allons commencer à l'utiliser pas une langage de programmation au début, mais une 1040 00:45:44,920 --> 00:45:46,030 langage de balisage. 1041 00:45:46,030 --> 00:45:48,740 Un langage de balisage étant celui qui est dans le même esprit à la programmation 1042 00:45:48,740 --> 00:45:51,715 langue, mais il ne vous donne pas l' capacité à vous exprimer logiquement. 1043 00:45:51,715 --> 00:45:55,070 Il vous donne seulement la possibilité d' exprimez-vous structurellement. 1044 00:45:55,070 --> 00:45:57,960 >> Où voulez-vous mettre quelque chose sur la page, la page Web? 1045 00:45:57,960 --> 00:45:59,200 De quelle couleur voulez-vous faire? 1046 00:45:59,200 --> 00:46:00,950 Quelle est la taille de la police voulez-vous faire? 1047 00:46:00,950 --> 00:46:02,970 Quels mots vous font réellement voulez sur la page web? 1048 00:46:02,970 --> 00:46:04,060 C'est donc un langage de balisage. 1049 00:46:04,060 --> 00:46:07,690 Mais ensuite, nous allons présenter très rapidement JavaScript, qui est un à part entière 1050 00:46:07,690 --> 00:46:08,560 le langage de programmation. 1051 00:46:08,560 --> 00:46:12,530 Très similaire en apparence syntaxiquement à C, mais il va falloir un certain 1052 00:46:12,530 --> 00:46:15,200 beau, plus puissant, plus fonctions conviviales. 1053 00:46:15,200 --> 00:46:18,050 >> Et l'une des frustrations à cet point dans le semestre, c'est que nous allons 1054 00:46:18,050 --> 00:46:22,065 Dès la mise en œuvre Speller en beaucoup moins lignes de code en utilisant d'autres langues 1055 00:46:22,065 --> 00:46:25,580 C que lui-même permet, mais pour des raisons de nous allons bientôt comprendre. 1056 00:46:25,580 --> 00:46:27,750 Ce sera le premier de ces page web. 1057 00:46:27,750 --> 00:46:30,120 Il sera complètement décevante, le premier que nous faisons. 1058 00:46:30,120 --> 00:46:31,400 Il sera tout simplement dire bonjour monde. 1059 00:46:31,400 --> 00:46:34,010 Mais si vous ne l'avez jamais vu avant, c'est HTML, 1060 00:46:34,010 --> 00:46:35,670 HyperText Markup Language. 1061 00:46:35,670 --> 00:46:39,310 >> Si vous allez à une certaine option de menu en la plupart de n'importe quel navigateur, sur n'importe quelle page web sur 1062 00:46:39,310 --> 00:46:43,160 l'Internet, vous pouvez voir le HTML que certaines personnes ont écrit à 1063 00:46:43,160 --> 00:46:44,400 créer cette page web. 1064 00:46:44,400 --> 00:46:47,850 Et il n'a probablement pas aussi bref ou aussi nette que cela. 1065 00:46:47,850 --> 00:46:51,400 Mais il suivra le modèle de ceux-ci parenthèses ouvertes et les barres obliques et 1066 00:46:51,400 --> 00:46:53,660 lettres et potentiellement chiffres. 1067 00:46:53,660 --> 00:46:56,770 >> Je pensais que je vous donne un teaser de ce que vous serez en mesure de faire 1068 00:46:56,770 --> 00:46:57,950 après avoir pris CS50. 1069 00:46:57,950 --> 00:47:02,620 Permettez-moi de passer à cs.harvard.edu / rob, la page de notre propre Rob Bowden. 1070 00:47:02,620 --> 00:47:06,080 Il a fait cela pour nous. 1071 00:47:06,080 --> 00:47:07,490 Ainsi, vous serez bientôt en mesure de le faire. 1072 00:47:07,490 --> 00:47:10,660 Et aussi, ce que vous avez entendu ce matin - 1073 00:47:10,660 --> 00:47:12,480 ce que vous avez entendu ce matin - 1074 00:47:12,480 --> 00:47:13,780 >> [HAMSTER DANCE MUSIC] 1075 00:47:13,780 --> 00:47:15,702 >> - Vous aurez être capable de faire cela. 1076 00:47:15,702 --> 00:47:16,790 Qui nous attend mercredi. 1077 00:47:16,790 --> 00:47:17,791 Nous vous verrons ensuite. 1078 00:47:17,791 --> 00:47:22,950 >> [HAMSTER DANCE MUSIC] 1079 00:47:22,950 --> 00:47:24,300 DAVID MALAN: À la prochaine CS50 - 1080 00:47:24,300 --> 00:47:31,670