1 00:00:00,000 --> 00:00:08,250 2 00:00:08,250 --> 00:00:12,680 >> JASON HIRSCHHORN: Bienvenue à tous à la Section Seven. 3 00:00:12,680 --> 00:00:15,040 Nous sommes dans la semaine de sept de cours. 4 00:00:15,040 --> 00:00:18,440 Et ce prochain jeudi C'est Halloween donc je suis 5 00:00:18,440 --> 00:00:21,420 habillé comme une citrouille. 6 00:00:21,420 --> 00:00:23,460 Je ne pouvais pas plier et mettre sur mes chaussures, et c'est pourquoi je suis 7 00:00:23,460 --> 00:00:25,660 juste porter des chaussettes. 8 00:00:25,660 --> 00:00:29,220 Je suis également rien porter sous cela, je ne peux pas l'enlever si c'est 9 00:00:29,220 --> 00:00:29,950 distraire de vous. 10 00:00:29,950 --> 00:00:31,860 Je m'excuse d'avance pour cela. 11 00:00:31,860 --> 00:00:33,170 Vous n'avez pas besoin d'imaginer ce qui se passe. 12 00:00:33,170 --> 00:00:34,240 Je porte des boxeurs. 13 00:00:34,240 --> 00:00:36,170 Il est donc tout bon. 14 00:00:36,170 --> 00:00:41,120 >> J'ai une histoire plus pourquoi je suis habillé comme une citrouille, mais je vais 15 00:00:41,120 --> 00:00:45,110 sauf que pour plus tard dans cette section parce que je ne veux pour commencer. 16 00:00:45,110 --> 00:00:47,720 Nous avons beaucoup de choses passionnantes d'aller au cours de cette semaine. 17 00:00:47,720 --> 00:00:51,810 La plupart d'entre eux sont directement liés à ce l'ensemble des problèmes de la semaine, les fautes d'orthographe. 18 00:00:51,810 --> 00:00:54,680 Nous allons aller plus liée listes et les tables de hachage 19 00:00:54,680 --> 00:00:57,160 pour l'ensemble de la section. 20 00:00:57,160 --> 00:01:02,490 Je mets cette liste chaque semaine, une liste de ressources pour vous pour vous aider à 21 00:01:02,490 --> 00:01:04,120 le matériel sur ce cours. 22 00:01:04,120 --> 00:01:07,600 Si, à une perte ou si la recherche d'une plus d'informations, consultez l'un des 23 00:01:07,600 --> 00:01:09,930 ces ressources. 24 00:01:09,930 --> 00:01:14,530 >> Encore une fois, pset6 est des fautes d'orthographe, l'ensemble de processeurs de cette semaine. 25 00:01:14,530 --> 00:01:17,690 Et il vous encourage aussi, et je vous encourager, d'utiliser un autre 26 00:01:17,690 --> 00:01:20,320 ressources spécifiquement pour ce jeu de processeurs. 27 00:01:20,320 --> 00:01:23,390 En particulier, les trois que j'ai figurant sur l'écran - 28 00:01:23,390 --> 00:01:27,160 gdb, que nous avons été familiarisés avec et utilisent depuis un certain temps maintenant, est 29 00:01:27,160 --> 00:01:29,270 va être très utile cette semaine. 30 00:01:29,270 --> 00:01:30,190 Alors, j'ai mis que ici. 31 00:01:30,190 --> 00:01:32,910 Mais chaque fois que vous travaillez avec C, vous devriez toujours utiliser gdb pour 32 00:01:32,910 --> 00:01:34,430 déboguer vos programmes. 33 00:01:34,430 --> 00:01:36,660 Cette semaine Valgrind aussi. 34 00:01:36,660 --> 00:01:38,535 Est-ce que quelqu'un sait ce que valgrind t-il? 35 00:01:38,535 --> 00:01:42,184 36 00:01:42,184 --> 00:01:43,890 >> PUBLIC: Il vérifie les fuites de mémoire? 37 00:01:43,890 --> 00:01:45,950 >> JASON HIRSCHHORN: Valgrind Détecter les fuites de mémoire. 38 00:01:45,950 --> 00:01:49,970 Donc, si vous quelque chose dans votre malloc programme, vous demandez de la mémoire. 39 00:01:49,970 --> 00:01:52,920 A la fin de votre programme, vous avez d'écrire gratuitement sur tout ce que vous avez 40 00:01:52,920 --> 00:01:54,800 malloced pour donner la mémoire de retour. 41 00:01:54,800 --> 00:01:58,420 Si vous n'écrivez pas libre à la fin et votre programme arrive à une conclusion, 42 00:01:58,420 --> 00:02:00,000 tout va automatiquement être libéré. 43 00:02:00,000 --> 00:02:02,340 Et pour les petits programmes, il est pas un gros problème. 44 00:02:02,340 --> 00:02:05,250 Mais si vous écrivez un long fonctionnement programme qui ne quitte pas, 45 00:02:05,250 --> 00:02:09,180 nécessairement, en quelques minutes ou un quelques secondes, puis des fuites de mémoire 46 00:02:09,180 --> 00:02:10,710 peut devenir une affaire énorme. 47 00:02:10,710 --> 00:02:14,940 >> Donc, pour pset6, on s'attend à ce que vous aurez zéro fuites de mémoire avec 48 00:02:14,940 --> 00:02:15,910 votre programme. 49 00:02:15,910 --> 00:02:18,690 Pour vérifier s'il ya des fuites de mémoire, valgrind exécuter et il vous donnera quelques belles 50 00:02:18,690 --> 00:02:21,190 sortie vous permettant de savoir si ou tout n'était pas libre. 51 00:02:21,190 --> 00:02:23,940 Nous pratiquons avec elle plus tard aujourd'hui, je l'espère. 52 00:02:23,940 --> 00:02:25,790 >> Enfin, la commande diff. 53 00:02:25,790 --> 00:02:28,900 Vous avez utilisé quelque chose de semblable à ce dans pset5 avec l'outil coup d'oeil. 54 00:02:28,900 --> 00:02:30,780 Vous a permis de regarder à l'intérieur. 55 00:02:30,780 --> 00:02:33,400 Vous avez également utilisé diff, aussi, par le problème réglé spec. 56 00:02:33,400 --> 00:02:35,950 Mais en vous autorisé à comparer deux fichiers. 57 00:02:35,950 --> 00:02:39,180 Vous pouvez comparer le fichier bitmap et d'info-têtes d'une solution de personnel et 58 00:02:39,180 --> 00:02:42,200 votre solution en pset5 si vous avez choisi d'utiliser. 59 00:02:42,200 --> 00:02:44,030 Diff vous permettra de faire ainsi. 60 00:02:44,030 --> 00:02:48,620 Vous pouvez comparer la réponse correcte pour Le problème de cette semaine mis à votre réponse 61 00:02:48,620 --> 00:02:52,210 et voir si elle s'aligne ou voir où les erreurs sont. 62 00:02:52,210 --> 00:02:55,870 >> Donc, ce sont trois bons outils vous devez utiliser pour cette semaine, et 63 00:02:55,870 --> 00:02:58,130 vérifier définitivement votre programme avec ces trois outils 64 00:02:58,130 --> 00:03:00,520 avant de se tourner po 65 00:03:00,520 --> 00:03:04,650 Encore une fois, comme je l'ai dit chaque semaine, si vous avez des commentaires pour moi - à la fois 66 00:03:04,650 --> 00:03:06,470 positive et constructive - 67 00:03:06,470 --> 00:03:09,930 n'hésitez pas à diriger sur le site au bas de cette diapositive 68 00:03:09,930 --> 00:03:11,270 et entrée là. 69 00:03:11,270 --> 00:03:13,440 J'apprécie vraiment tout et tous les commentaires. 70 00:03:13,440 --> 00:03:17,360 Et si vous me donnez des choses spécifiques que Je peux faire pour améliorer ou que je suis 71 00:03:17,360 --> 00:03:21,350 faisant ainsi que vous voudriez que je continue, je prends cela à coeur et 72 00:03:21,350 --> 00:03:24,040 vraiment essayer dur à écouter à vos commentaires. 73 00:03:24,040 --> 00:03:27,720 Je ne peux pas promettre que je vais faire tout, même si, comme le port d'un 74 00:03:27,720 --> 00:03:30,700 citrouille costume chaque semaine. 75 00:03:30,700 --> 00:03:34,020 >> Donc, nous allons passer la majeure partie de article, comme je l'ai mentionné, en parlant de 76 00:03:34,020 --> 00:03:37,240 listes chaînées et les tables de hachage, qui sera directement applicable à la 77 00:03:37,240 --> 00:03:38,780 problème réglé cette semaine. 78 00:03:38,780 --> 00:03:42,580 Les listes chaînées, nous allons passer en revue relativement rapidement, car nous avons passé un peu juste 79 00:03:42,580 --> 00:03:44,930 du temps qui passe au-dessus de l'article. 80 00:03:44,930 --> 00:03:48,680 Et donc nous allons aller droit dans le problèmes de codage pour les listes chaînées. 81 00:03:48,680 --> 00:03:52,740 Et puis à la fin, nous allons parler hash tables et comment ils s'appliquent à ce 82 00:03:52,740 --> 00:03:55,280 Le problème de la semaine défini. 83 00:03:55,280 --> 00:03:57,560 >> Vous avez vu ce code avant. 84 00:03:57,560 --> 00:04:02,730 Il s'agit d'une structure, et elle consiste à définir quelque chose de nouveau appelé un nœud. 85 00:04:02,730 --> 00:04:10,660 Et à l'intérieur d'un noeud y est un nombre entier ici et là est un pointeur vers 86 00:04:10,660 --> 00:04:11,830 un autre noeud. 87 00:04:11,830 --> 00:04:12,790 Nous avons vu cela avant. 88 00:04:12,790 --> 00:04:14,830 Cela a été à venir pour un couple de semaines maintenant. 89 00:04:14,830 --> 00:04:18,680 Il combine des pointeurs, qui nous avons été travailler avec, et les structures qui permettent 90 00:04:18,680 --> 00:04:22,079 nous combinons deux différents choses dans un type de données. 91 00:04:22,079 --> 00:04:24,830 92 00:04:24,830 --> 00:04:26,490 >> Il ya beaucoup de choses à l'écran. 93 00:04:26,490 --> 00:04:30,220 Mais tout cela devrait être relativement familier avec vous. 94 00:04:30,220 --> 00:04:33,810 Sur la première ligne, nous déclarer un nouveau nœud. 95 00:04:33,810 --> 00:04:41,650 Et puis à l'intérieur que le nouveau noeud, j'ai mis en ce que l'entier le noeud à une. 96 00:04:41,650 --> 00:04:44,950 Nous voyons sur la ligne suivante, je fais un printf, mais j'ai grisé 97 00:04:44,950 --> 00:04:48,080 la commande printf parce que la très partie importante est cette ligne ici - 98 00:04:48,080 --> 00:04:50,020 new_node.n. 99 00:04:50,020 --> 00:04:51,270 Qu'est-ce que le point signifie? 100 00:04:51,270 --> 00:04:53,810 101 00:04:53,810 --> 00:04:57,240 >> PUBLIC: Ouvrez le nœud et évaluer la valeur de n pour cela. 102 00:04:57,240 --> 00:04:58,370 >> JASON HIRSCHHORN: C'est tout à fait exact. 103 00:04:58,370 --> 00:05:03,300 Point signifie accéder à la partie n de ce nouveau noeud. 104 00:05:03,300 --> 00:05:05,690 Cette ligne suivante fait quoi? 105 00:05:05,690 --> 00:05:16,140 106 00:05:16,140 --> 00:05:17,050 Michael. 107 00:05:17,050 --> 00:05:21,910 >> PUBLIC: Il crée un autre noeud qui va pointer vers le nouveau nœud. 108 00:05:21,910 --> 00:05:24,870 >> JASON HIRSCHHORN: Donc, ce n'est pas créer un nouveau nœud. 109 00:05:24,870 --> 00:05:26,120 Il crée un quoi? 110 00:05:26,120 --> 00:05:28,300 111 00:05:28,300 --> 00:05:29,300 >> PUBLIC: Un pointeur. 112 00:05:29,300 --> 00:05:33,460 >> JASON HIRSCHHORN: Un pointeur vers un noeud, comme indiqué par ce noeud * ici. 113 00:05:33,460 --> 00:05:34,800 Donc il crée un pointeur vers un noeud. 114 00:05:34,800 --> 00:05:37,490 Et qui est-ce nœud pointe à, Michael? 115 00:05:37,490 --> 00:05:38,440 >> PUBLIC: New noeud? 116 00:05:38,440 --> 00:05:39,240 >> JASON HIRSCHHORN: New noeud. 117 00:05:39,240 --> 00:05:43,020 Et c'est pointant là parce que nous avons donné l'adresse du nouveau noeud. 118 00:05:43,020 --> 00:05:45,820 Et maintenant, dans cette ligne, nous voyons deux manières différentes de 119 00:05:45,820 --> 00:05:46,910 exprimer la même chose. 120 00:05:46,910 --> 00:05:49,650 Et je tenais à souligner la façon dont ces deux choses sont les mêmes. 121 00:05:49,650 --> 00:05:54,740 Dans la première ligne, nous déréférencer le pointeur. 122 00:05:54,740 --> 00:05:55,830 Donc, nous allons vers le noeud. 123 00:05:55,830 --> 00:05:56,830 C'est ce que signifie cette étoile. 124 00:05:56,830 --> 00:05:57,930 Nous avons déjà vu cela avec des pointeurs. 125 00:05:57,930 --> 00:05:59,280 Allez à ce nœud. 126 00:05:59,280 --> 00:06:00,370 C'est entre parenthèses. 127 00:06:00,370 --> 00:06:04,610 Et alors accéder via l'opérateur point l'élément n de ce noeud. 128 00:06:04,610 --> 00:06:08,430 >> Donc, c'est prendre la syntaxe nous avons vu ici et maintenant 129 00:06:08,430 --> 00:06:09,670 utiliser avec un pointeur. 130 00:06:09,670 --> 00:06:13,730 Bien sûr, il obtient le genre d'occupation si vous écrivez ces parenthèses - 131 00:06:13,730 --> 00:06:14,940 cette étoile et point. 132 00:06:14,940 --> 00:06:16,220 Il est un peu occupé. 133 00:06:16,220 --> 00:06:18,500 Donc, nous avons un peu de sucre syntaxique. 134 00:06:18,500 --> 00:06:19,920 Et cette ligne ici - 135 00:06:19,920 --> 00:06:21,170 ptr_node-> n. 136 00:06:21,170 --> 00:06:25,400 137 00:06:25,400 --> 00:06:28,000 Cela ne exactement la même chose. 138 00:06:28,000 --> 00:06:30,840 Donc, ces deux lignes de code équivalent et fera 139 00:06:30,840 --> 00:06:31,650 exactement la même chose. 140 00:06:31,650 --> 00:06:34,210 >> Mais je tenais à ceux avant d'aller plus loin pour que vous compreniez 141 00:06:34,210 --> 00:06:39,000 que vraiment cette chose ici est juste du sucre syntaxique pour le déréférencement 142 00:06:39,000 --> 00:06:44,200 le pointeur et puis aller à n partie de cette structure. 143 00:06:44,200 --> 00:06:45,525 Une question sur ce toboggan? 144 00:06:45,525 --> 00:06:53,020 145 00:06:53,020 --> 00:06:54,390 OK. 146 00:06:54,390 --> 00:06:58,510 >> Nous allons donc passer par un couple des opérations que vous pouvez faire sur 147 00:06:58,510 --> 00:06:59,730 listes chaînées. 148 00:06:59,730 --> 00:07:05,770 Une liste chaînée, rappel, est une série de nœuds qui pointent vers une autre. 149 00:07:05,770 --> 00:07:12,470 Et nous commençons généralement avec un pointeur appelé la tête, en général, qui pointe vers 150 00:07:12,470 --> 00:07:14,040 la première chose dans la liste. 151 00:07:14,040 --> 00:07:18,900 Ainsi, sur la première ligne, ici, nous ont d'abord notre origine L. 152 00:07:18,900 --> 00:07:21,370 Donc, cette chose que vous pouvez penser - ce texte ici vous pouvez penser que 153 00:07:21,370 --> 00:07:23,560 juste le pointeur nous avons stocké que quelque part les points 154 00:07:23,560 --> 00:07:24,670 au premier élément. 155 00:07:24,670 --> 00:07:27,500 Et dans cette liste chaînée nous avons quatre nœuds. 156 00:07:27,500 --> 00:07:29,530 Chaque noeud est une grosse boîte. 157 00:07:29,530 --> 00:07:33,430 La grande boîte à l'intérieur du grand boîte est la partie entière. 158 00:07:33,430 --> 00:07:37,400 Et puis nous avons une partie de pointeur. 159 00:07:37,400 --> 00:07:39,630 >> Ces boîtes ne sont pas à échelle, car la taille est 160 00:07:39,630 --> 00:07:42,320 un nombre entier, en octets? 161 00:07:42,320 --> 00:07:43,290 Quelle maintenant? 162 00:07:43,290 --> 00:07:43,710 Quatre. 163 00:07:43,710 --> 00:07:45,470 Et la taille est un pointeur? 164 00:07:45,470 --> 00:07:45,940 Quatre. 165 00:07:45,940 --> 00:07:48,180 Alors, vraiment, si nous devions dessiner ce à l'échelle les deux cases 166 00:07:48,180 --> 00:07:49,690 serait de la même taille. 167 00:07:49,690 --> 00:07:52,870 Dans ce cas, nous voulons insérer quelque chose dans la liste chaînée. 168 00:07:52,870 --> 00:07:57,190 Vous pouvez donc voir ici nous insertion cinq Nous traversons par la 169 00:07:57,190 --> 00:08:01,310 liste chaînée, trouver où cinq va, et puis insérez-le. 170 00:08:01,310 --> 00:08:03,560 >> Brisons que vers le bas et aller un peu plus lentement. 171 00:08:03,560 --> 00:08:05,510 Je vais rappeler à la carte. 172 00:08:05,510 --> 00:08:09,930 Donc, nous avons notre nœud cinq qui nous avons créé dans mallocs. 173 00:08:09,930 --> 00:08:11,190 Pourquoi tout le monde rit? 174 00:08:11,190 --> 00:08:12,130 Je plaisante. 175 00:08:12,130 --> 00:08:13,310 OK. 176 00:08:13,310 --> 00:08:14,820 Nous avons donc malloced cinq. 177 00:08:14,820 --> 00:08:16,310 Nous avons créé ce noeud ailleurs. 178 00:08:16,310 --> 00:08:17,740 Nous l'avons prêt à aller. 179 00:08:17,740 --> 00:08:20,130 Nous commençons à l'avant de notre liste à deux. 180 00:08:20,130 --> 00:08:22,380 Et nous voulons insérer dans un mode de tri. 181 00:08:22,380 --> 00:08:27,550 >> Donc, si nous voyons deux et nous voulons mettre dans cinq ans, que faisons-nous lorsque nous voyons 182 00:08:27,550 --> 00:08:28,800 quelque chose de moins que nous? 183 00:08:28,800 --> 00:08:31,850 184 00:08:31,850 --> 00:08:33,520 Qu'est-ce? 185 00:08:33,520 --> 00:08:36,750 Nous voulons insérer cinq dans ce liste chaînée, mettant triée. 186 00:08:36,750 --> 00:08:37,520 Nous voyons le numéro deux. 187 00:08:37,520 --> 00:08:38,769 Alors, que faisons-nous? 188 00:08:38,769 --> 00:08:39,179 Marcus? 189 00:08:39,179 --> 00:08:40,679 >> PUBLIC: Appelez le pointeur au noeud suivant. 190 00:08:40,679 --> 00:08:42,530 >> JASON HIRSCHHORN: Et pourquoi faire nous allons à la prochaine? 191 00:08:42,530 --> 00:08:45,970 >> PUBLIC: Parce que c'est la noeud suivant dans la liste. 192 00:08:45,970 --> 00:08:48,310 Et nous savons que cet autre emplacement. 193 00:08:48,310 --> 00:08:50,410 >> JASON HIRSCHHORN: Et cinq est supérieur supérieur à deux, en particulier. 194 00:08:50,410 --> 00:08:51,600 Parce que nous voulons garder triée. 195 00:08:51,600 --> 00:08:52,730 Ainsi cinq est supérieur à deux. 196 00:08:52,730 --> 00:08:54,460 Donc, nous passons à la suivante. 197 00:08:54,460 --> 00:08:55,240 Et maintenant, nous arrivons à quatre. 198 00:08:55,240 --> 00:08:56,490 Et ce qui se passe quand nous arrivons à quatre? 199 00:08:56,490 --> 00:08:58,920 200 00:08:58,920 --> 00:09:00,310 >> Cinq est supérieur à quatre. 201 00:09:00,310 --> 00:09:01,460 Donc, nous continuons. 202 00:09:01,460 --> 00:09:03,110 Et maintenant, nous sommes à six. 203 00:09:03,110 --> 00:09:04,360 Et que voyons-nous à six? 204 00:09:04,360 --> 00:09:08,672 205 00:09:08,672 --> 00:09:09,608 Oui, Carlos? 206 00:09:09,608 --> 00:09:10,544 >> PUBLIC: Six est supérieur à cinq. 207 00:09:10,544 --> 00:09:11,480 >> JASON HIRSCHHORN: Six est supérieur à cinq. 208 00:09:11,480 --> 00:09:13,660 C'est donc là que nous voulons pour insérer cinq. 209 00:09:13,660 --> 00:09:17,320 Cependant, gardez à l'esprit que si nous avoir un seul pointeur ici - 210 00:09:17,320 --> 00:09:19,840 c'est notre pointeur supplémentaire qui est traversant la liste. 211 00:09:19,840 --> 00:09:21,860 Et nous pointant à six. 212 00:09:21,860 --> 00:09:25,010 Nous avons perdu la trace de ce vient avant six. 213 00:09:25,010 --> 00:09:29,130 Donc, si nous voulons insérer quelque chose dans cette liste mettant triée, nous 214 00:09:29,130 --> 00:09:31,630 probablement besoin de combien de pointeurs? 215 00:09:31,630 --> 00:09:32,280 >> PUBLIC: Deux. 216 00:09:32,280 --> 00:09:32,920 >> JASON Hirschhorn: Deux. 217 00:09:32,920 --> 00:09:35,720 Un pour garder une trace de l'actuel un et un pour garder une trace de 218 00:09:35,720 --> 00:09:37,050 la précédente. 219 00:09:37,050 --> 00:09:38,450 Il ne s'agit que d'une liste chaînée. 220 00:09:38,450 --> 00:09:39,670 Il va de seulement une direction. 221 00:09:39,670 --> 00:09:43,220 Si nous avions une liste doublement chaînée, où tout pointait à la chose 222 00:09:43,220 --> 00:09:46,240 après et la chose avant, puis nous n'aurions pas besoin de le faire. 223 00:09:46,240 --> 00:09:49,350 Mais dans ce cas, nous ne voulons pas perdre trace de ce qui est venu avant nous dans le cas 224 00:09:49,350 --> 00:09:53,350 nous avons besoin d'insérer quelque part cinq dans le milieu. 225 00:09:53,350 --> 00:09:55,610 Disons que nous avons insérons neuf. 226 00:09:55,610 --> 00:09:57,260 Qu'est-ce qui se passerait quand nous sommes arrivés à huit? 227 00:09:57,260 --> 00:10:01,860 228 00:10:01,860 --> 00:10:04,880 >> PUBLIC: Vous auriez à obtenir ce point zéro. 229 00:10:04,880 --> 00:10:07,820 Au lieu d'avoir point zéro vous auriez pour ajouter un élément et ensuite 230 00:10:07,820 --> 00:10:09,216 pointer à neuf. 231 00:10:09,216 --> 00:10:09,700 >> JASON Hirschhorn: Exactement. 232 00:10:09,700 --> 00:10:10,600 Donc, nous obtenons huit. 233 00:10:10,600 --> 00:10:13,140 Nous arrivons à la fin de la liste, car cette pointe sur null. 234 00:10:13,140 --> 00:10:16,330 Et maintenant, au lieu d'avoir à pointer null pointer nous avons à notre nouveau nœud. 235 00:10:16,330 --> 00:10:19,870 Et nous avons mis le pointeur dans notre nouveau nœud à null. 236 00:10:19,870 --> 00:10:21,445 Quelqu'un at-il des questions sur l'insertion? 237 00:10:21,445 --> 00:10:25,620 238 00:10:25,620 --> 00:10:28,100 Que faire si je ne me soucie pas en gardant la liste triée? 239 00:10:28,100 --> 00:10:31,701 240 00:10:31,701 --> 00:10:34,350 >> PUBLIC: Collez à l' début ou la fin. 241 00:10:34,350 --> 00:10:35,510 >> JASON Hirschhorn: Collez à le début ou la fin. 242 00:10:35,510 --> 00:10:37,276 Lequel faut-il faire? 243 00:10:37,276 --> 00:10:38,770 Bobby? 244 00:10:38,770 --> 00:10:41,020 Pourquoi la fin? 245 00:10:41,020 --> 00:10:43,250 >> PUBLIC: Parce que le début est déjà rempli. 246 00:10:43,250 --> 00:10:43,575 >> JASON Hirschhorn: OK. 247 00:10:43,575 --> 00:10:44,360 Le début est déjà rempli. 248 00:10:44,360 --> 00:10:46,090 Qui veut plaider contre Bobby. 249 00:10:46,090 --> 00:10:47,290 Marcus. 250 00:10:47,290 --> 00:10:48,910 >> PUBLIC: Eh bien, vous voulez probablement coller au début parce 251 00:10:48,910 --> 00:10:50,140 sinon, si vous mettez à la fin, vous auriez à 252 00:10:50,140 --> 00:10:51,835 parcourir la liste entière. 253 00:10:51,835 --> 00:10:52,990 >> JASON Hirschhorn: Exactement. 254 00:10:52,990 --> 00:10:57,970 Donc, si nous pensons à l'exécution, le l'exécution de l'insertion à la fin 255 00:10:57,970 --> 00:11:00,110 serait n, la taille de ce produit. 256 00:11:00,110 --> 00:11:03,080 Quelle est la grande exécution de O de l'insertion au début? 257 00:11:03,080 --> 00:11:04,170 Constante de temps. 258 00:11:04,170 --> 00:11:07,075 Donc, si vous ne vous souciez pas de garder quelque chose triée, beaucoup mieux à juste 259 00:11:07,075 --> 00:11:08,420 insérer au début de cette liste. 260 00:11:08,420 --> 00:11:10,320 Et cela peut être fait en temps constant. 261 00:11:10,320 --> 00:11:13,900 262 00:11:13,900 --> 00:11:14,690 >> OK. 263 00:11:14,690 --> 00:11:18,870 Opération suivante est de trouver qui d'autre - nous avons formulé ce que la recherche. 264 00:11:18,870 --> 00:11:22,470 Mais nous allons regarder à travers le liste chaînée pour un objet. 265 00:11:22,470 --> 00:11:26,000 Les gars, vous avez vu le code de rechercher avant en cours. 266 00:11:26,000 --> 00:11:29,490 Mais nous sorte de juste fait avec insérer, ou au moins l'insertion, 267 00:11:29,490 --> 00:11:30,580 quelque chose triée. 268 00:11:30,580 --> 00:11:36,350 Vous regardez à travers, le noeud va par noeud, jusqu'à ce que vous trouviez le numéro que vous êtes 269 00:11:36,350 --> 00:11:37,780 cherchez. 270 00:11:37,780 --> 00:11:39,670 Qu'advient-il si vous atteignez la fin de la liste? 271 00:11:39,670 --> 00:11:43,020 Disons que je suis à la recherche de neuf et je atteindre la fin de la liste. 272 00:11:43,020 --> 00:11:44,270 Que faisons-nous? 273 00:11:44,270 --> 00:11:47,147 274 00:11:47,147 --> 00:11:48,110 >> PUBLIC: Retour faux? 275 00:11:48,110 --> 00:11:48,690 >> JASON Hirschhorn: Retour faux. 276 00:11:48,690 --> 00:11:49,960 Nous n'avons pas trouvé. 277 00:11:49,960 --> 00:11:52,010 Si vous arrivez à la fin de la liste et vous n'avez pas trouvé le numéro que vous êtes 278 00:11:52,010 --> 00:11:54,170 cherchez, il n'est pas là. 279 00:11:54,170 --> 00:11:55,420 Une question sur trouver? 280 00:11:55,420 --> 00:11:59,530 281 00:11:59,530 --> 00:12:04,615 S'il s'agissait d'une liste triée, ce qui serait être différent pour notre recherche? 282 00:12:04,615 --> 00:12:07,370 283 00:12:07,370 --> 00:12:08,103 Ouais. 284 00:12:08,103 --> 00:12:10,600 >> PUBLIC: Il serait trouver la première valeur C'est plus grand que celui 285 00:12:10,600 --> 00:12:12,390 vous cherchez et puis retourner false. 286 00:12:12,390 --> 00:12:13,190 >> JASON Hirschhorn: Exactement. 287 00:12:13,190 --> 00:12:17,310 Donc, si c'est une liste triée, si nous arrivons à quelque chose qui est plus grand que ce 288 00:12:17,310 --> 00:12:20,180 nous recherchons, nous n'avons pas besoin de continuer à aller à la fin de la liste. 289 00:12:20,180 --> 00:12:24,060 Nous pouvons à ce moment return false parce que nous n'allons pas trouver. 290 00:12:24,060 --> 00:12:27,340 La question est maintenant, nous avons parlé garder les listes chaînées triés, 291 00:12:27,340 --> 00:12:28,180 les garder non triés. 292 00:12:28,180 --> 00:12:30,050 Ça va être quelque chose que vous êtes probablement avoir à penser 293 00:12:30,050 --> 00:12:34,240 quand le problème de codage fixé cinq si vous choisir une table de hachage avec distinct 294 00:12:34,240 --> 00:12:36,360 approche chaînage, qui nous en parlerons plus tard. 295 00:12:36,360 --> 00:12:41,400 >> Mais est-il utile de garder la liste trié et ensuite être capable d'avoir peut-être 296 00:12:41,400 --> 00:12:42,310 des recherches plus rapides? 297 00:12:42,310 --> 00:12:47,220 Ou vaut-il mieux insérer rapidement quelque chose dans l'exécution constante mais 298 00:12:47,220 --> 00:12:48,430 avoir plus de recherche? 299 00:12:48,430 --> 00:12:52,250 C'est un compromis là que vous arriver à décider ce qui est plus approprié 300 00:12:52,250 --> 00:12:53,590 pour votre problème spécifique. 301 00:12:53,590 --> 00:12:56,680 Et il n'y a pas nécessairement un réponse tout à fait raison. 302 00:12:56,680 --> 00:12:59,520 Mais c'est certainement une décision que vous obtenez à faire, et probablement bon pour défendre 303 00:12:59,520 --> 00:13:05,270 que, disons, un commentaire ou deux pourquoi vous avez choisi un sur l'autre. 304 00:13:05,270 --> 00:13:06,490 >> Enfin, la suppression. 305 00:13:06,490 --> 00:13:08,100 Nous avons vu la suppression. 306 00:13:08,100 --> 00:13:09,180 Il est similaire à la recherche. 307 00:13:09,180 --> 00:13:11,020 Nous attendons de l'élément. 308 00:13:11,020 --> 00:13:12,390 Disons que nous essayons de supprimer six. 309 00:13:12,390 --> 00:13:14,450 Donc, nous trouvons six ici. 310 00:13:14,450 --> 00:13:18,860 La seule chose que nous devons nous assurer que nous faire, c'est que tout ce que pointe vers 311 00:13:18,860 --> 00:13:21,220 six - comme nous le voyons dans l'étape deux ici - 312 00:13:21,220 --> 00:13:26,500 tout ce qui se pointant à six besoins à sauter six maintenant et être changé à 313 00:13:26,500 --> 00:13:28,160 quelle que soit six pointe. 314 00:13:28,160 --> 00:13:31,410 Nous ne voulons pas toujours orphelin le reste de notre liste en oubliant de mettre cette 315 00:13:31,410 --> 00:13:32,960 pointeur précédente. 316 00:13:32,960 --> 00:13:35,960 Et puis parfois, selon sur le programme, ils vont juste 317 00:13:35,960 --> 00:13:37,380 supprimer ce noeud tout. 318 00:13:37,380 --> 00:13:40,135 Parfois, vous aurez envie de revenir la valeur qui se trouve dans ce nœud. 319 00:13:40,135 --> 00:13:42,490 C'est comme ça que la suppression de travaux. 320 00:13:42,490 --> 00:13:44,610 Toutes les questions sur supprimer? 321 00:13:44,610 --> 00:13:51,280 322 00:13:51,280 --> 00:13:53,850 >> PUBLIC: Donc, si vous allez à supprimer il, voulez-vous juste utiliser gratuitement parce 323 00:13:53,850 --> 00:13:55,655 on peut supposer qu'il a été malloced? 324 00:13:55,655 --> 00:13:57,976 >> JASON Hirschhorn: Si vous voulez libérer quelque chose qui est tout à fait exact et vous 325 00:13:57,976 --> 00:13:58,540 malloced elle. 326 00:13:58,540 --> 00:14:00,410 Disons que nous voulions y retourner cette valeur. 327 00:14:00,410 --> 00:14:04,010 Nous pourrions revenir six et gratuit ce nœud et appel gratuit sur elle. 328 00:14:04,010 --> 00:14:06,180 Ou nous aurions probablement appelons libre d'abord et puis revenir six. 329 00:14:06,180 --> 00:14:11,210 330 00:14:11,210 --> 00:14:11,580 >> OK. 331 00:14:11,580 --> 00:14:14,010 Passons donc à la pratique de codage. 332 00:14:14,010 --> 00:14:16,090 Nous allons coder trois fonctions. 333 00:14:16,090 --> 00:14:18,260 Le premier est appelé insert_node. 334 00:14:18,260 --> 00:14:22,170 Ainsi, vous avez le code que je vous ai envoyé, et si vous regardez cela plus tard 335 00:14:22,170 --> 00:14:28,020 vous pouvez accéder au code linked.c sur le site Web de CS50. 336 00:14:28,020 --> 00:14:30,880 Mais dans linked.c, il ya quelques le squelette du code qui est déjà 337 00:14:30,880 --> 00:14:32,280 été écrit pour vous. 338 00:14:32,280 --> 00:14:34,560 Et puis il ya quelques fonctions vous devez écrire. 339 00:14:34,560 --> 00:14:36,380 >> Nous allons d'abord écrire insert_node. 340 00:14:36,380 --> 00:14:39,800 Et ce ne insert_node c'est insère un nombre entier. 341 00:14:39,800 --> 00:14:42,440 Et vous donner l'entier dans une liste chaînée. 342 00:14:42,440 --> 00:14:45,470 Et en particulier, vous devez pour maintenir la liste triée 343 00:14:45,470 --> 00:14:47,650 du plus petit au plus grand. 344 00:14:47,650 --> 00:14:51,360 En outre, vous ne voulez pas insérer les doublons. 345 00:14:51,360 --> 00:14:54,600 Enfin, comme vous pouvez le voir insert_node retourne un bool. 346 00:14:54,600 --> 00:14:57,140 Donc, vous êtes censé informer l'utilisateur si l'insert a été ou non 347 00:14:57,140 --> 00:15:00,800 succès en retournant true ou false. 348 00:15:00,800 --> 00:15:02,580 A la fin de ce programme - 349 00:15:02,580 --> 00:15:05,750 et pour ce stade, vous n'avez pas besoin à vous soucier de quoi que ce soit libérer. 350 00:15:05,750 --> 00:15:11,790 Donc, tout ce que vous faites, c'est de prendre un nombre entier et l'insérer dans une liste. 351 00:15:11,790 --> 00:15:13,890 >> C'est ce que je vous demande de faire maintenant. 352 00:15:13,890 --> 00:15:17,620 Encore une fois, dans le linked.c, qui vous ont tous, est le code de squelette. 353 00:15:17,620 --> 00:15:20,980 Et vous devriez voir vers le bas la déclaration de la fonction de l'échantillon. 354 00:15:20,980 --> 00:15:27,390 Toutefois, avant d'entrer dans le coder en C, je vous encourage fortement à aller 355 00:15:27,390 --> 00:15:29,330 à travers les étapes que nous avons été pratiquer chaque semaine. 356 00:15:29,330 --> 00:15:31,100 Nous avons déjà traversé une photo de ce. 357 00:15:31,100 --> 00:15:33,380 Donc, vous devriez avoir une certaine compréhension de la façon dont cela fonctionne. 358 00:15:33,380 --> 00:15:36,590 Mais je voudrais vous encourager à écrire certains pseudo avant de plonger po 359 00:15:36,590 --> 00:15:38,640 Et nous allons passer en revue pseudocode en tant que groupe. 360 00:15:38,640 --> 00:15:41,470 Et puis une fois que vous avez écrit votre pseudo, et une fois que nous avons écrit notre 361 00:15:41,470 --> 00:15:45,850 pseudo en tant que groupe, vous pouvez aller dans le codage en C 362 00:15:45,850 --> 00:15:49,980 >> Comme un heads-up, la fonction de insert_node est probablement la plus délicate de 363 00:15:49,980 --> 00:15:53,550 les trois nous allons écrire parce que je ajouter des contraintes supplémentaires à 364 00:15:53,550 --> 00:15:57,190 la programmation, en particulier, que vous n'allez pas à insérer une 365 00:15:57,190 --> 00:15:59,880 doublons et que la liste devrait rester triée. 366 00:15:59,880 --> 00:16:02,660 Donc, c'est un programme non trivial que vous avez besoin de coder. 367 00:16:02,660 --> 00:16:06,470 Et pourquoi ne pas vous prendre de cinq à sept minutes pour se mettre au travail sur le 368 00:16:06,470 --> 00:16:07,640 pseudo et le code. 369 00:16:07,640 --> 00:16:09,460 Et puis nous allons commencer part en groupe. 370 00:16:09,460 --> 00:16:11,680 Encore une fois, si vous avez des questions juste levez la main et je viendrai autour. 371 00:16:11,680 --> 00:16:15,258 372 00:16:15,258 --> 00:16:16,508 . 373 00:16:16,508 --> 00:18:28,370 374 00:18:28,370 --> 00:18:30,120 >> Nous faisons aussi généralement ceux-ci - 375 00:18:30,120 --> 00:18:32,070 ou je ne vous dis pas explicitement peut travailler avec les gens. 376 00:18:32,070 --> 00:18:36,500 Mais évidemment, je vous encourage fortement, si vous avez des questions, de demander à la 377 00:18:36,500 --> 00:18:39,840 voisin assis à côté de vous ou même travailler avec quelqu'un 378 00:18:39,840 --> 00:18:40,510 d'autre si vous voulez. 379 00:18:40,510 --> 00:18:42,600 Cela ne doit pas nécessairement être un individu activité silencieuse. 380 00:18:42,600 --> 00:20:11,770 381 00:20:11,770 --> 00:20:16,330 >> Commençons par écrit un certain pseudo sur la carte. 382 00:20:16,330 --> 00:20:19,395 Qui peut me donner la première ligne de pseudo pour ce programme? 383 00:20:19,395 --> 00:20:22,240 384 00:20:22,240 --> 00:20:23,640 Pour cette fonction, plutôt - insert_node. 385 00:20:23,640 --> 00:20:29,960 386 00:20:29,960 --> 00:20:31,830 Alden? 387 00:20:31,830 --> 00:20:36,560 >> PUBLIC: Donc, la première chose que j'ai faite a été créer un nouveau pointeur vers le noeud et je 388 00:20:36,560 --> 00:20:41,320 initialisé il pointant vers le même chose qui liste pointe. 389 00:20:41,320 --> 00:20:41,550 >> JASON Hirschhorn: OK. 390 00:20:41,550 --> 00:20:45,190 Donc, vous créez un nouveau pointeur à la liste, de ne pas le noeud. 391 00:20:45,190 --> 00:20:45,420 >> PUBLIC: Droit. 392 00:20:45,420 --> 00:20:46,150 Ouais. 393 00:20:46,150 --> 00:20:46,540 >> JASON Hirschhorn: OK. 394 00:20:46,540 --> 00:20:48,221 Et puis qu'est-ce que nous voulons faire? 395 00:20:48,221 --> 00:20:49,163 Quoi de suite? 396 00:20:49,163 --> 00:20:50,105 Qu'est-ce que sur le nœud? 397 00:20:50,105 --> 00:20:51,050 Nous n'avons pas de nœud. 398 00:20:51,050 --> 00:20:52,300 Nous avons juste valeur. 399 00:20:52,300 --> 00:20:55,918 400 00:20:55,918 --> 00:20:58,890 Si nous voulons insérer un noeud, qu'est-ce que nous besoin de faire avant que nous puissions même 401 00:20:58,890 --> 00:20:59,980 penser l'insérer? 402 00:20:59,980 --> 00:21:00,820 >> PUBLIC: Oh, désolé. 403 00:21:00,820 --> 00:21:02,160 nous avons besoin de malloc espace pour un nœud. 404 00:21:02,160 --> 00:21:02,455 >> JASON Hirschhorn: Excellent. 405 00:21:02,455 --> 00:21:03,210 Faisons - 406 00:21:03,210 --> 00:21:04,628 OK. 407 00:21:04,628 --> 00:21:06,065 Vous ne pouvez pas atteindre cette haute. 408 00:21:06,065 --> 00:21:08,939 409 00:21:08,939 --> 00:21:09,897 OK. 410 00:21:09,897 --> 00:21:13,236 Nous allons descendre, puis nous utilisons deux colonnes. 411 00:21:13,236 --> 00:21:13,732 Je ne peux pas aller aussi - 412 00:21:13,732 --> 00:21:14,982 OK. 413 00:21:14,982 --> 00:21:23,660 414 00:21:23,660 --> 00:21:25,130 Créez un nouveau nœud. 415 00:21:25,130 --> 00:21:29,380 Vous pouvez créer un autre pointeur à la liste ou vous pouvez simplement utiliser la liste telle qu'elle existe. 416 00:21:29,380 --> 00:21:30,720 Vous n'avez pas vraiment besoin de le faire. 417 00:21:30,720 --> 00:21:31,750 >> Donc, nous créons un nouveau nœud. 418 00:21:31,750 --> 00:21:32,010 Grand. 419 00:21:32,010 --> 00:21:32,840 C'est ce que nous faisons d'abord. 420 00:21:32,840 --> 00:21:34,870 Quelle est la prochaine? 421 00:21:34,870 --> 00:21:35,080 >> PUBLIC: Attendez. 422 00:21:35,080 --> 00:21:38,330 Faut-il créer un nouveau nœud maintenant ou devrions nous attendre à faire en sorte que 423 00:21:38,330 --> 00:21:42,260 il n'ya pas de doublons de noeud sur la liste avant que nous créons? 424 00:21:42,260 --> 00:21:43,100 >> JASON Hirschhorn: Bonne question. 425 00:21:43,100 --> 00:21:47,770 Tenons pour plus tard parce que la majorité du temps, nous allons créer 426 00:21:47,770 --> 00:21:48,220 un nouveau noeud. 427 00:21:48,220 --> 00:21:49,110 Donc, nous allons garder ici. 428 00:21:49,110 --> 00:21:51,006 Mais c'est une bonne question. 429 00:21:51,006 --> 00:21:53,250 Si nous créons et nous trouvons un double, ce qui devrait 430 00:21:53,250 --> 00:21:54,490 nous faisons avant de revenir? 431 00:21:54,490 --> 00:21:55,190 >> PUBLIC: libérer. 432 00:21:55,190 --> 00:21:55,470 >> JASON Hirschhorn: Ouais. 433 00:21:55,470 --> 00:21:56,500 Probablement le libérer. 434 00:21:56,500 --> 00:21:56,760 OK. 435 00:21:56,760 --> 00:21:59,850 Que faisons-nous après nous créer un nouveau nœud? 436 00:21:59,850 --> 00:22:02,260 Annie? 437 00:22:02,260 --> 00:22:04,780 >> PUBLIC: Nous mettons l' nombre dans le noeud? 438 00:22:04,780 --> 00:22:05,140 >> JASON Hirschhorn: Exactement. 439 00:22:05,140 --> 00:22:07,190 Nous mettons le nombre - nous malloc espace. 440 00:22:07,190 --> 00:22:08,160 Je vais laisser cette tout comme une ligne. 441 00:22:08,160 --> 00:22:08,720 Mais vous avez raison. 442 00:22:08,720 --> 00:22:10,305 Nous malloc espace, puis nous mettons le nombre po 443 00:22:10,305 --> 00:22:12,585 Nous pouvons même mettre le pointeur partie à null. 444 00:22:12,585 --> 00:22:13,720 C'est exactement ça. 445 00:22:13,720 --> 00:22:17,400 Et puis que dire de la suite? 446 00:22:17,400 --> 00:22:18,490 Nous avons tiré cette image sur la carte. 447 00:22:18,490 --> 00:22:21,190 Alors, que faisons-nous? 448 00:22:21,190 --> 00:22:22,680 >> PUBLIC: Nous allons dans la liste. 449 00:22:22,680 --> 00:22:23,930 >> JASON Hirschhorn: Aller dans la liste. 450 00:22:23,930 --> 00:22:30,620 451 00:22:30,620 --> 00:22:31,100 OK. 452 00:22:31,100 --> 00:22:34,280 Et qu'est-ce que nous vérifions à chaque noeud. 453 00:22:34,280 --> 00:22:35,955 Kurt, qu'est-ce que nous vérifions pour chaque noeud? 454 00:22:35,955 --> 00:22:41,640 >> PUBLIC: Voir si la valeur de n de ce noeud est supérieure à la valeur de n 455 00:22:41,640 --> 00:22:43,070 de notre noeud. 456 00:22:43,070 --> 00:22:43,340 >> JASON Hirschhorn: OK. 457 00:22:43,340 --> 00:22:44,280 Je vais faire - 458 00:22:44,280 --> 00:22:45,855 ouais, OK. 459 00:22:45,855 --> 00:22:48,160 C'est donc n - 460 00:22:48,160 --> 00:22:59,040 Je vais dire si la valeur est supérieure que ce nœud, alors que faisons-nous? 461 00:22:59,040 --> 00:23:07,290 >> PUBLIC: Eh bien, nous insérons la chose juste avant que. 462 00:23:07,290 --> 00:23:07,970 >> JASON Hirschhorn: OK. 463 00:23:07,970 --> 00:23:09,410 Donc, si c'est plus que cela, alors nous voulons insérer. 464 00:23:09,410 --> 00:23:14,010 Mais nous voulons insérer juste avant parce que nous devons aussi être 465 00:23:14,010 --> 00:23:16,070 garder la trace, alors, de ce qui était avant. 466 00:23:16,070 --> 00:23:22,690 Donc insérer avant. 467 00:23:22,690 --> 00:23:25,120 Nous avons probablement manqué quelque chose donc plus tôt. 468 00:23:25,120 --> 00:23:27,770 Nous avons probablement besoin d'être maintenant une trace de ce qui se passe. 469 00:23:27,770 --> 00:23:28,460 Mais nous reviendrons là-bas. 470 00:23:28,460 --> 00:23:30,160 Donc, quelle est la valeur est inférieure à? 471 00:23:30,160 --> 00:23:38,030 472 00:23:38,030 --> 00:23:39,710 Kurt, que faisons-nous si valeur est inférieure à? 473 00:23:39,710 --> 00:23:43,000 >> PUBLIC: Ensuite, vous continuez à aller sauf si c'est la dernière. 474 00:23:43,000 --> 00:23:43,550 >> JASON Hirschhorn: j'aime ça. 475 00:23:43,550 --> 00:23:44,800 Alors, allez au nœud suivant. 476 00:23:44,800 --> 00:23:47,410 477 00:23:47,410 --> 00:23:48,930 Sauf si c'est le dernier - 478 00:23:48,930 --> 00:23:51,100 nous allons probablement vérifiant que dans les termes d'une condition. 479 00:23:51,100 --> 00:23:54,870 Mais oui, noeud suivant. 480 00:23:54,870 --> 00:23:58,680 Et cela devient trop faible, donc nous allons passer ici. 481 00:23:58,680 --> 00:24:02,030 Mais si - 482 00:24:02,030 --> 00:24:03,280 peut tous voir cela? 483 00:24:03,280 --> 00:24:07,230 484 00:24:07,230 --> 00:24:11,610 Si nous sommes égaux que faisons-nous? 485 00:24:11,610 --> 00:24:15,740 Si la valeur que nous essayons d'insérer est égale à la valeur de ce noeud? 486 00:24:15,740 --> 00:24:16,320 Ouais? 487 00:24:16,320 --> 00:24:18,400 >> PUBLIC: [inaudible]. 488 00:24:18,400 --> 00:24:18,850 >> JASON Hirschhorn: Ouais. 489 00:24:18,850 --> 00:24:19,290 Compte tenu de cette - 490 00:24:19,290 --> 00:24:20,090 Marcus est juste. 491 00:24:20,090 --> 00:24:21,330 Nous aurions pu peut-être fait quelque chose de différent. 492 00:24:21,330 --> 00:24:25,360 Mais étant donné que nous l'avons créé, ici nous devons libérer et revenir ensuite. 493 00:24:25,360 --> 00:24:26,774 Oh boy. 494 00:24:26,774 --> 00:24:30,080 Est-ce mieux? 495 00:24:30,080 --> 00:24:31,850 Comment ça? 496 00:24:31,850 --> 00:24:33,100 OK. 497 00:24:33,100 --> 00:24:35,360 498 00:24:35,360 --> 00:24:37,640 Gratuit et que faisons-nous revenir, [inaudible]? 499 00:24:37,640 --> 00:24:41,330 500 00:24:41,330 --> 00:24:44,110 OK. 501 00:24:44,110 --> 00:24:45,360 Avons-nous oublié quelque chose? 502 00:24:45,360 --> 00:24:53,500 503 00:24:53,500 --> 00:24:59,650 Alors, où allons-nous garder la trace du noeud avant? 504 00:24:59,650 --> 00:25:02,370 >> PUBLIC: Je pense que ce serait aller après créer un nouveau nœud. 505 00:25:02,370 --> 00:25:02,600 >> JASON Hirschhorn: OK. 506 00:25:02,600 --> 00:25:03,940 Donc, au début nous allons probablement - 507 00:25:03,940 --> 00:25:07,175 oui, nous pouvons créer un pointeur vers une nouvelle nœud, comme un pointeur de noeud précédent et 508 00:25:07,175 --> 00:25:09,600 un pointeur de nœud actuel. 509 00:25:09,600 --> 00:25:12,640 Donc, nous allons insérer ici. 510 00:25:12,640 --> 00:25:15,610 511 00:25:15,610 --> 00:25:26,900 Créer actuelle et précédente des pointeurs vers des noeuds. 512 00:25:26,900 --> 00:25:28,955 Mais quand avons-nous ajustons ces pointeurs? 513 00:25:28,955 --> 00:25:30,205 Où pouvons-nous faire dans le code? 514 00:25:30,205 --> 00:25:33,830 515 00:25:33,830 --> 00:25:34,160 Jeff? 516 00:25:34,160 --> 00:25:35,170 >> PUBLIC: - des conditions de valeur? 517 00:25:35,170 --> 00:25:36,420 >> JASON Hirschhorn: Quels un en particulier? 518 00:25:36,420 --> 00:25:39,862 519 00:25:39,862 --> 00:25:40,720 >> PUBLIC: Je suis juste confondu. 520 00:25:40,720 --> 00:25:44,200 Si la valeur est supérieure à ce noeud, ce que cela signifie pas que vous voulez aller 521 00:25:44,200 --> 00:25:45,320 au noeud suivant? 522 00:25:45,320 --> 00:25:49,515 >> JASON HIRSCHHORN: Donc, si notre valeur est supérieure à la valeur de ce nœud. 523 00:25:49,515 --> 00:25:52,130 >> PUBLIC: Oui, alors vous voudriez aller plus loin dans la ligne, non? 524 00:25:52,130 --> 00:25:52,590 >> JASON HIRSCHHORN: Droit. 525 00:25:52,590 --> 00:25:53,840 Donc, nous n'avons pas l'insérer ici. 526 00:25:53,840 --> 00:25:58,430 527 00:25:58,430 --> 00:26:03,240 Si la valeur est inférieure à ce nœud, puis nous allons à la prochaine nœud - ou alors nous 528 00:26:03,240 --> 00:26:03,835 insérer avant. 529 00:26:03,835 --> 00:26:05,966 >> PUBLIC: Attendez, qui est ce noeud et qui est la valeur? 530 00:26:05,966 --> 00:26:08,510 531 00:26:08,510 --> 00:26:09,280 >> JASON HIRSCHHORN: Bonne question. 532 00:26:09,280 --> 00:26:13,260 Valeur par cette définition de fonction c'est ce que l'on nous donne. 533 00:26:13,260 --> 00:26:16,910 Donc, la valeur est le nombre qu'on nous donne. 534 00:26:16,910 --> 00:26:21,120 Donc, si la valeur est inférieure à cette nœud, nous avons besoin de temps pour insérer. 535 00:26:21,120 --> 00:26:24,575 Si la valeur est supérieure à ce noeud, nous allons vers le noeud suivant. 536 00:26:24,575 --> 00:26:26,790 Et revenir à la question initiale, cependant, où - 537 00:26:26,790 --> 00:26:29,060 >> PUBLIC: Si la valeur est supérieure que ce nœud. 538 00:26:29,060 --> 00:26:30,310 >> JASON HIRSCHHORN: Et si que faisons-nous ici? 539 00:26:30,310 --> 00:26:36,790 540 00:26:36,790 --> 00:26:38,160 Sweet. 541 00:26:38,160 --> 00:26:38,860 C'est exact. 542 00:26:38,860 --> 00:26:41,370 Je vais juste écrire mise à jour des pointeurs. 543 00:26:41,370 --> 00:26:44,010 Mais oui, avec l'actuel vous mettre à jour à 544 00:26:44,010 --> 00:26:46,080 pointer vers la suivante. 545 00:26:46,080 --> 00:26:47,330 Autre chose qui nous manque? 546 00:26:47,330 --> 00:26:52,710 547 00:26:52,710 --> 00:26:54,940 Je vais donc saisir cette coder dans gedit. 548 00:26:54,940 --> 00:26:58,375 Et tandis que je fais cela, vous pouvez avoir un quelques minutes de plus pour travailler sur le codage 549 00:26:58,375 --> 00:28:19,240 dans cette C. 550 00:28:19,240 --> 00:28:20,940 >> J'ai donc entrée du pseudo. 551 00:28:20,940 --> 00:28:22,940 Une note rapide avant que nous commencions. 552 00:28:22,940 --> 00:28:25,560 Nous pourrions ne pas être en mesure de complètement terminer ce dans tous les 553 00:28:25,560 --> 00:28:27,300 trois de ces fonctions. 554 00:28:27,300 --> 00:28:30,630 Il est des solutions correctes pour eux que je vais envoyer sur vous les gars 555 00:28:30,630 --> 00:28:33,730 après l'article, et il sera être affiché sur CS50.net. 556 00:28:33,730 --> 00:28:35,640 Donc, je ne vous encourage pas à aller voir les sections. 557 00:28:35,640 --> 00:28:40,550 Je vous encourage à essayer ces sur votre posséder, puis utiliser la pratique 558 00:28:40,550 --> 00:28:41,760 problèmes pour vérifier vos réponses. 559 00:28:41,760 --> 00:28:47,070 Ceux-ci ont tous été conçus pour près s'identifier et adhérer à ce 560 00:28:47,070 --> 00:28:48,400 vous avez à faire sur l'ensemble des problèmes. 561 00:28:48,400 --> 00:28:53,820 Donc, je ne vous encourage à pratiquer cette sur votre propre et utiliser le code de 562 00:28:53,820 --> 00:28:54,660 vérifiez vos réponses. 563 00:28:54,660 --> 00:28:57,060 Parce que je ne veux passer à hacher tables à un certain moment dans la section. 564 00:28:57,060 --> 00:28:58,150 Donc, nous ne pourrions pas passer à travers tout cela. 565 00:28:58,150 --> 00:28:59,960 Mais nous ferons aussi bien que nous pouvons maintenant. 566 00:28:59,960 --> 00:29:00,370 >> OK. 567 00:29:00,370 --> 00:29:01,960 Commençons. 568 00:29:01,960 --> 00:29:04,770 Asam, comment pouvons-nous créer un nouveau nœud? 569 00:29:04,770 --> 00:29:06,810 >> PUBLIC: Vous n'avez struct *. 570 00:29:06,810 --> 00:29:09,640 >> JASON HIRSCHHORN: Donc, nous avoir que ici. 571 00:29:09,640 --> 00:29:10,040 Oh, désolé. 572 00:29:10,040 --> 00:29:13,530 Vous disiez struct *. 573 00:29:13,530 --> 00:29:17,260 >> PUBLIC: Et puis [? genre?] nœud ou un nœud de c. 574 00:29:17,260 --> 00:29:17,780 >> JASON HIRSCHHORN: OK. 575 00:29:17,780 --> 00:29:19,740 Je vais l'appeler new_node afin que nous puissions rester cohérent. 576 00:29:19,740 --> 00:29:22,646 577 00:29:22,646 --> 00:29:33,180 >> PUBLIC: Et vous voulez définir ce que à la tête, le premier noeud. 578 00:29:33,180 --> 00:29:33,580 >> JASON HIRSCHHORN: OK. 579 00:29:33,580 --> 00:29:37,290 Alors maintenant, ce pointage à - si ce n'a pas encore créé un nouveau nœud. 580 00:29:37,290 --> 00:29:41,380 Ceci est juste pointe vers le premier noeud dans la liste. 581 00:29:41,380 --> 00:29:42,630 Comment puis-je créer un nouveau nœud? 582 00:29:42,630 --> 00:29:45,490 583 00:29:45,490 --> 00:29:48,070 Si j'ai besoin d'espace pour créer un nouveau nœud. 584 00:29:48,070 --> 00:29:49,230 Malloc. 585 00:29:49,230 --> 00:29:51,710 Et comment grand? 586 00:29:51,710 --> 00:30:00,390 >> PUBLIC: La taille de la structure. 587 00:30:00,390 --> 00:30:01,150 >> JASON HIRSCHHORN: L' taille de la structure. 588 00:30:01,150 --> 00:30:02,400 Et quelle est la structure appelée? 589 00:30:02,400 --> 00:30:09,670 590 00:30:09,670 --> 00:30:09,840 >> PUBLIC: Noeud? 591 00:30:09,840 --> 00:30:11,640 >> JASON HIRSCHHORN: Node. 592 00:30:11,640 --> 00:30:17,640 Donc malloc (sizeof (noeud)); nous donne l'espace. 593 00:30:17,640 --> 00:30:19,740 Et cette ligne - 594 00:30:19,740 --> 00:30:21,740 une chose est incorrecte sur cette ligne. 595 00:30:21,740 --> 00:30:24,430 Est new_node un pointeur vers une structure? 596 00:30:24,430 --> 00:30:25,650 C'est un nom générique. 597 00:30:25,650 --> 00:30:26,520 Qu'est ce que c'est - 598 00:30:26,520 --> 00:30:27,450 noeud, exactement. 599 00:30:27,450 --> 00:30:29,340 C'est un noeud *. 600 00:30:29,340 --> 00:30:33,010 Et que faisons-nous tout de suite après nous malloc quelque chose, Asan? 601 00:30:33,010 --> 00:30:34,476 Quelle est la première chose que nous faisons? 602 00:30:34,476 --> 00:30:38,850 603 00:30:38,850 --> 00:30:40,320 Et si ça ne marche pas? 604 00:30:40,320 --> 00:30:42,430 >> PUBLIC: Oh, vérifier si elle des points au noeud? 605 00:30:42,430 --> 00:30:43,310 >> JASON HIRSCHHORN: Exactement. 606 00:30:43,310 --> 00:30:46,750 Donc, si vous new_node égaux égaux null, que faisons-nous? 607 00:30:46,750 --> 00:30:51,650 608 00:30:51,650 --> 00:30:54,820 Cela renvoie un bool, cette fonction. 609 00:30:54,820 --> 00:30:57,760 Exactement. 610 00:30:57,760 --> 00:30:58,450 On dirait bien. 611 00:30:58,450 --> 00:30:59,680 Quelque chose à ajouter? 612 00:30:59,680 --> 00:31:00,670 Nous allons ajouter des choses à la fin. 613 00:31:00,670 --> 00:31:03,160 Mais que regarde jusqu'ici bon. 614 00:31:03,160 --> 00:31:06,170 Créer pointeurs actuels et antérieurs. 615 00:31:06,170 --> 00:31:08,650 Michael, comment puis-je faire cela? 616 00:31:08,650 --> 00:31:12,810 >> PUBLIC: Vous auriez faire un noeud *. 617 00:31:12,810 --> 00:31:21,800 618 00:31:21,800 --> 00:31:25,502 Vous auriez à faire un pas pour new_node mais pour l' 619 00:31:25,502 --> 00:31:26,905 noeuds nous ont déjà. 620 00:31:26,905 --> 00:31:27,230 >> JASON HIRSCHHORN: OK. 621 00:31:27,230 --> 00:31:29,255 Ainsi, le nœud actuel nous sommes sur. 622 00:31:29,255 --> 00:31:30,505 Je vais appeler que Curr. 623 00:31:30,505 --> 00:31:39,650 624 00:31:39,650 --> 00:31:39,770 Très bien. 625 00:31:39,770 --> 00:31:41,620 Nous avons décidé que nous voulons garder deux, parce que nous devons savoir 626 00:31:41,620 --> 00:31:42,870 ce qui est devant lui. 627 00:31:42,870 --> 00:31:45,770 628 00:31:45,770 --> 00:31:47,020 Que font-ils initialisés à? 629 00:31:47,020 --> 00:31:49,874 630 00:31:49,874 --> 00:31:54,180 >> PUBLIC: Leur valeur dans notre liste. 631 00:31:54,180 --> 00:31:58,090 >> JASON HIRSCHHORN: Alors, quelle est la première chose sur notre liste? 632 00:31:58,090 --> 00:32:04,050 Ou comment savons-nous où l' à partir de notre liste est? 633 00:32:04,050 --> 00:32:08,015 >> PUBLIC: N'est-il pas passé dans la fonction? 634 00:32:08,015 --> 00:32:08,466 >> JASON HIRSCHHORN: Droit. 635 00:32:08,466 --> 00:32:09,716 Elle a été adoptée en droit ici. 636 00:32:09,716 --> 00:32:15,910 637 00:32:15,910 --> 00:32:18,980 Donc, si il est passé à la fonction, la début de la liste, ce qui devrait nous 638 00:32:18,980 --> 00:32:21,270 définir courant égal à? 639 00:32:21,270 --> 00:32:22,110 >> PUBLIC: Liste. 640 00:32:22,110 --> 00:32:22,900 >> JASON HIRSCHHORN: Liste. 641 00:32:22,900 --> 00:32:24,090 C'est exactement ça. 642 00:32:24,090 --> 00:32:26,290 Maintenant, il a l'adresse de le début de notre liste. 643 00:32:26,290 --> 00:32:28,450 Et que dire précédente? 644 00:32:28,450 --> 00:32:31,920 >> PUBLIC: Liste moins un? 645 00:32:31,920 --> 00:32:32,690 >> JASON HIRSCHHORN: Il ya rien devant elle. 646 00:32:32,690 --> 00:32:34,580 Alors, que pouvons-nous faire pour rien signifier? 647 00:32:34,580 --> 00:32:35,050 >> PUBLIC: Null. 648 00:32:35,050 --> 00:32:35,450 >> JASON HIRSCHHORN: Ouais. 649 00:32:35,450 --> 00:32:37,950 Cela sonne comme une bonne idée. 650 00:32:37,950 --> 00:32:38,360 Parfait. 651 00:32:38,360 --> 00:32:39,630 Merci. 652 00:32:39,630 --> 00:32:42,850 Parcourez la liste. 653 00:32:42,850 --> 00:32:45,490 Constantine, combien de temps allons-nous de passer par la liste? 654 00:32:45,490 --> 00:32:49,010 >> PUBLIC: jusqu'à arriver nulle. 655 00:32:49,010 --> 00:32:49,390 >> JASON HIRSCHHORN: OK. 656 00:32:49,390 --> 00:32:50,430 Donc, si, tandis que, pour la boucle. 657 00:32:50,430 --> 00:32:52,200 Que faisons-nous? 658 00:32:52,200 --> 00:32:53,320 >> PUBLIC: Peut-être une boucle? 659 00:32:53,320 --> 00:32:53,910 >> JASON HIRSCHHORN: Faisons une boucle for. 660 00:32:53,910 --> 00:32:55,870 OK. 661 00:32:55,870 --> 00:33:02,465 >> PUBLIC: Et nous disons pour - 662 00:33:02,465 --> 00:33:09,764 663 00:33:09,764 --> 00:33:13,390 jusqu'à ce que le pointeur courant n'est pas égal à zéro. 664 00:33:13,390 --> 00:33:19,160 >> JASON HIRSCHHORN: Donc, si nous savons l' état, comment pouvons-nous écrire une boucle 665 00:33:19,160 --> 00:33:21,740 sur la base de cette condition. 666 00:33:21,740 --> 00:33:24,380 Quel genre de boucle devrions-nous utiliser? 667 00:33:24,380 --> 00:33:25,260 >> PUBLIC: Bien. 668 00:33:25,260 --> 00:33:25,590 >> JASON HIRSCHHORN: Ouais. 669 00:33:25,590 --> 00:33:27,130 Cela fait plus de sens en fonction hors de ce que vous dites. 670 00:33:27,130 --> 00:33:29,430 Si nous voulons juste aller en nous, il serait il suffit de savoir que cette chose, il serait 671 00:33:29,430 --> 00:33:31,680 sens de faire une boucle while. 672 00:33:31,680 --> 00:33:39,880 Alors que le courant n'est pas égal à zéro, si la valeur est inférieure à ce noeud. 673 00:33:39,880 --> 00:33:41,650 Akshar, donne-moi cette ligne. 674 00:33:41,650 --> 00:33:48,810 675 00:33:48,810 --> 00:33:56,955 >> PUBLIC: Si le courant-> n n moins de valeur. 676 00:33:56,955 --> 00:34:00,170 677 00:34:00,170 --> 00:34:03,260 Ou renverser cette tendance. 678 00:34:03,260 --> 00:34:06,140 Mettez cette tranche. 679 00:34:06,140 --> 00:34:06,620 >> JASON HIRSCHHORN: Désolé. 680 00:34:06,620 --> 00:34:08,760 >> PUBLIC: Changer le support. 681 00:34:08,760 --> 00:34:10,914 >> JASON HIRSCHHORN: Donc, si c'est supérieure à la valeur. 682 00:34:10,914 --> 00:34:18,719 683 00:34:18,719 --> 00:34:22,120 Parce que c'est la confusion avec la commentaire ci-dessus, je vais le faire. 684 00:34:22,120 --> 00:34:22,480 Mais oui. 685 00:34:22,480 --> 00:34:25,125 Si notre valeur est inférieure à cette noeud, que faisons-nous? 686 00:34:25,125 --> 00:34:25,540 Oh. 687 00:34:25,540 --> 00:34:26,710 Je l'ai juste ici. 688 00:34:26,710 --> 00:34:27,960 Insérer avant. 689 00:34:27,960 --> 00:34:32,080 690 00:34:32,080 --> 00:34:32,370 OK. 691 00:34:32,370 --> 00:34:33,933 Comment faisons-nous cela? 692 00:34:33,933 --> 00:34:34,900 >> PUBLIC: Est-il encore de moi? 693 00:34:34,900 --> 00:34:36,150 >> JASON HIRSCHHORN: Ouais. 694 00:34:36,150 --> 00:34:38,520 695 00:34:38,520 --> 00:34:39,770 >> PUBLIC: Vous - 696 00:34:39,770 --> 00:34:42,909 697 00:34:42,909 --> 00:34:44,159 new_node-> next. 698 00:34:44,159 --> 00:34:46,770 699 00:34:46,770 --> 00:34:50,163 >> JASON HIRSCHHORN: Alors, quel est qui va égaler? 700 00:34:50,163 --> 00:34:52,070 >> PUBLIC: Il va courant égal. 701 00:34:52,070 --> 00:34:53,889 >> JASON HIRSCHHORN: Exactement. 702 00:34:53,889 --> 00:34:55,730 Et si l'autre - 703 00:34:55,730 --> 00:34:56,730 quoi d'autre avons-nous besoin de mettre à jour? 704 00:34:56,730 --> 00:34:59,982 >> PUBLIC: Vérifier si le passé est égal à zéro. 705 00:34:59,982 --> 00:35:01,870 >> JASON HIRSCHHORN: Si prev - 706 00:35:01,870 --> 00:35:03,730 si prev égal nulle. 707 00:35:03,730 --> 00:35:05,990 >> PUBLIC: Cela signifie qu'il va pour devenir le chef. 708 00:35:05,990 --> 00:35:06,780 >> JASON HIRSCHHORN: Cela signifie que il est devenu la tête. 709 00:35:06,780 --> 00:35:07,620 Alors que faisons-nous? 710 00:35:07,620 --> 00:35:12,510 >> PUBLIC: Nous faisons face est de new_node. 711 00:35:12,510 --> 00:35:16,690 >> JASON HIRSCHHORN: Head égaux new_node. 712 00:35:16,690 --> 00:35:20,540 Et pourquoi la tête ici, pas la liste? 713 00:35:20,540 --> 00:35:24,940 >> PUBLIC: Parce que la tête est une entreprise mondiale variable, qui est le lieu de départ. 714 00:35:24,940 --> 00:35:26,190 >> JASON HIRSCHHORN: Sweet. 715 00:35:26,190 --> 00:35:33,750 716 00:35:33,750 --> 00:35:34,170 OK. 717 00:35:34,170 --> 00:35:36,150 Et - 718 00:35:36,150 --> 00:35:53,796 >> PUBLIC: Ensuite, vous n'avez d'autre prev-> égale prochaine new_node. 719 00:35:53,796 --> 00:35:55,080 Et puis vous revenez vrai. 720 00:35:55,080 --> 00:35:59,560 721 00:35:59,560 --> 00:36:02,700 >> JASON HIRSCHHORN: Où faire nous avons mis fin à new_node? 722 00:36:02,700 --> 00:36:04,850 >> PUBLIC: Je voudrais - 723 00:36:04,850 --> 00:36:06,180 J'ai mis qu'au début. 724 00:36:06,180 --> 00:36:07,430 >> JASON HIRSCHHORN: Alors quelle ligne? 725 00:36:07,430 --> 00:36:10,000 726 00:36:10,000 --> 00:36:12,598 >> PUBLIC: Après l'instruction if vérifier si elle est connue. 727 00:36:12,598 --> 00:36:13,057 >> JASON HIRSCHHORN: Juste ici? 728 00:36:13,057 --> 00:36:18,335 >> PUBLIC: je ferais new_node-> n est égale valeur. 729 00:36:18,335 --> 00:36:19,585 >> JASON HIRSCHHORN: Ça sonne bien. 730 00:36:19,585 --> 00:36:21,740 731 00:36:21,740 --> 00:36:25,090 Probablement il est logique - nous ne faisons pas besoin de savoir ce que nous sommes sur la liste 732 00:36:25,090 --> 00:36:26,280 parce que nous ne traitons avec une seule liste. 733 00:36:26,280 --> 00:36:29,560 Donc une meilleure déclaration de fonction pour c'est juste pour se débarrasser de cette 734 00:36:29,560 --> 00:36:34,360 entièrement et il suffit d'insérer une valeur dans la tête. 735 00:36:34,360 --> 00:36:35,930 Nous n'avons même pas besoin de savoir quelle liste nous sommes po 736 00:36:35,930 --> 00:36:39,140 Mais je vais le garder pour le moment et puis changer à la mise à jour 737 00:36:39,140 --> 00:36:42,590 les diapositives et le code. 738 00:36:42,590 --> 00:36:44,980 Alors qu'il est bon pour le moment. 739 00:36:44,980 --> 00:36:46,560 Si la valeur - qui peut le faire en ligne? 740 00:36:46,560 --> 00:36:47,810 Si - 741 00:36:47,810 --> 00:36:52,240 742 00:36:52,240 --> 00:36:53,840 que faisons-nous ici, Noah. 743 00:36:53,840 --> 00:36:57,890 744 00:36:57,890 --> 00:37:07,100 >> PUBLIC: Si la valeur est supérieure que curr-> n - 745 00:37:07,100 --> 00:37:16,830 746 00:37:16,830 --> 00:37:18,240 >> JASON HIRSCHHORN: Comment faire nous allons vers le noeud suivant? 747 00:37:18,240 --> 00:37:27,760 748 00:37:27,760 --> 00:37:30,530 >> PUBLIC: Curr-> n est égal à new_node. 749 00:37:30,530 --> 00:37:37,630 750 00:37:37,630 --> 00:37:39,195 >> JASON HIRSCHHORN: Donc n est quelle partie de la structure? 751 00:37:39,195 --> 00:37:43,065 752 00:37:43,065 --> 00:37:46,020 L'entier. 753 00:37:46,020 --> 00:37:50,420 Et new_node est un pointeur sur un noeud. 754 00:37:50,420 --> 00:37:51,880 Alors quelle partie de Curr devrions nous mettre à jour? 755 00:37:51,880 --> 00:38:03,900 756 00:38:03,900 --> 00:38:05,400 Si ce n'est pas n, alors quel est l'autre partie? 757 00:38:05,400 --> 00:38:21,680 758 00:38:21,680 --> 00:38:22,810 Noé, ce qui est l'autre partie. 759 00:38:22,810 --> 00:38:23,570 >> PUBLIC: Oh, la prochaine. 760 00:38:23,570 --> 00:38:25,645 >> JASON HIRSCHHORN: Ensuite, exactement. 761 00:38:25,645 --> 00:38:26,410 Exactement. 762 00:38:26,410 --> 00:38:28,770 Suivant est la bonne. 763 00:38:28,770 --> 00:38:31,540 Et quoi d'autre avons-nous besoin de mettre à jour, Noah? 764 00:38:31,540 --> 00:38:32,840 >> PUBLIC: Les pointeurs. 765 00:38:32,840 --> 00:38:34,840 >> JASON HIRSCHHORN: Donc, nous courant mis à jour. 766 00:38:34,840 --> 00:38:36,090 >> PUBLIC: Précédent-> next. 767 00:38:36,090 --> 00:38:48,160 768 00:38:48,160 --> 00:38:49,410 >> JASON HIRSCHHORN: Ouais. 769 00:38:49,410 --> 00:38:57,465 770 00:38:57,465 --> 00:38:58,370 OK, nous ferons une pause. 771 00:38:58,370 --> 00:39:02,200 Qui peut nous aider ici? 772 00:39:02,200 --> 00:39:03,385 Manu, que devons-nous faire? 773 00:39:03,385 --> 00:39:05,615 >> PUBLIC: Vous avez à définir il égale à curr-> suivant. 774 00:39:05,615 --> 00:39:09,110 775 00:39:09,110 --> 00:39:11,630 Mais le faire avant la ligne précédente. 776 00:39:11,630 --> 00:39:12,880 >> JASON HIRSCHHORN: OK. 777 00:39:12,880 --> 00:39:16,590 778 00:39:16,590 --> 00:39:18,260 Autre chose? 779 00:39:18,260 --> 00:39:19,170 Akshar. 780 00:39:19,170 --> 00:39:22,680 >> PUBLIC: Je ne pense pas que vous êtes destiné à changer curr-> suivant. 781 00:39:22,680 --> 00:39:29,270 Je pense que vous êtes censé faire égaux curr curr-> next pour aller au noeud suivant. 782 00:39:29,270 --> 00:39:30,500 >> JASON HIRSCHHORN: Donc désolé, où? 783 00:39:30,500 --> 00:39:32,680 Sur quelle ligne? 784 00:39:32,680 --> 00:39:33,420 Cette ligne? 785 00:39:33,420 --> 00:39:33,750 >> PUBLIC: Ouais. 786 00:39:33,750 --> 00:39:35,745 Assurez-Curr égale curr-> suivant. 787 00:39:35,745 --> 00:39:39,690 788 00:39:39,690 --> 00:39:43,360 >> JASON HIRSCHHORN: C'est correct parce que le courant est un 789 00:39:43,360 --> 00:39:45,220 pointeur vers un noeud. 790 00:39:45,220 --> 00:39:48,550 Et nous voulons qu'il pointe vers la prochaine nœud de ce qui se actuellement 791 00:39:48,550 --> 00:39:49,930 souligné. 792 00:39:49,930 --> 00:39:54,410 Curr lui-même a un côté. 793 00:39:54,410 --> 00:39:58,620 Mais si nous devions mettre à jour curr.next, nous serait mise à jour de la note réelle 794 00:39:58,620 --> 00:40:01,430 lui-même, pas où ce pointeur pointait. 795 00:40:01,430 --> 00:40:02,680 Qu'en est-il de cette ligne, si. 796 00:40:02,680 --> 00:40:05,160 797 00:40:05,160 --> 00:40:07,330 Avi? 798 00:40:07,330 --> 00:40:09,590 >> PUBLIC: Précédent-> égaux prochaine Curr. 799 00:40:09,590 --> 00:40:12,500 800 00:40:12,500 --> 00:40:19,440 >> JASON HIRSCHHORN: Encore une fois, si prev est un pointeur vers un noeud, prev-> se trouve à côté de la 801 00:40:19,440 --> 00:40:23,020 réelle pointeur dans le noeud. 802 00:40:23,020 --> 00:40:27,190 Donc, ce serait une mise à jour pointeur dans un noeud à Curr. 803 00:40:27,190 --> 00:40:28,570 Nous ne voulons pas de mettre à jour un pointeur dans un noeud. 804 00:40:28,570 --> 00:40:30,570 Nous voulons mettre à jour précédente. 805 00:40:30,570 --> 00:40:31,850 Alors, comment faisons-nous cela? 806 00:40:31,850 --> 00:40:34,250 >> PUBLIC: Il serait juste préc. 807 00:40:34,250 --> 00:40:34,565 >> JASON HIRSCHHORN: Droit. 808 00:40:34,565 --> 00:40:35,560 Précédent est un pointeur vers un noeud. 809 00:40:35,560 --> 00:40:38,750 Maintenant, nous sommes changeant à un nouveau pointeur vers un noeud. 810 00:40:38,750 --> 00:40:40,830 OK Passons bas. 811 00:40:40,830 --> 00:40:41,940 Enfin, cette dernière condition. 812 00:40:41,940 --> 00:40:44,896 Jeff, que faisons-nous ici? 813 00:40:44,896 --> 00:40:47,515 >> PUBLIC: Si la valeur est égal à curr-> n. 814 00:40:47,515 --> 00:40:51,030 815 00:40:51,030 --> 00:40:51,300 >> JASON HIRSCHHORN: Désolé. 816 00:40:51,300 --> 00:40:52,372 Oh mon Dieu. 817 00:40:52,372 --> 00:40:54,330 Qu'est-ce? 818 00:40:54,330 --> 00:40:55,580 Valeur == curr-> n. 819 00:40:55,580 --> 00:41:01,050 820 00:41:01,050 --> 00:41:02,300 Que faisons-nous? 821 00:41:02,300 --> 00:41:04,760 822 00:41:04,760 --> 00:41:10,950 >> PUBLIC: Vous souhaitez libérer notre new_node, et alors vous revenez faux. 823 00:41:10,950 --> 00:41:21,410 824 00:41:21,410 --> 00:41:23,460 >> JASON HIRSCHHORN: C'est ce que nous avons écrit jusqu'ici. 825 00:41:23,460 --> 00:41:25,710 Quelqu'un at-il quoi que ce soit à ajouter avant que nous fassions? 826 00:41:25,710 --> 00:41:35,460 827 00:41:35,460 --> 00:41:35,710 OK. 828 00:41:35,710 --> 00:41:36,960 Essayons. 829 00:41:36,960 --> 00:41:44,180 830 00:41:44,180 --> 00:41:46,110 Le contrôle peut arriver à la fin d'une fonction non-nulle. 831 00:41:46,110 --> 00:41:48,310 Avi, ce qui se passe? 832 00:41:48,310 --> 00:41:51,380 >> PUBLIC: Êtes-vous censé mettre retour vrai à l'extérieur de la boucle while? 833 00:41:51,380 --> 00:41:53,900 834 00:41:53,900 --> 00:41:54,400 >> JASON HIRSCHHORN: Je ne sais pas. 835 00:41:54,400 --> 00:41:54,780 Vous me voulez? 836 00:41:54,780 --> 00:41:55,520 >> PUBLIC: Peu importe. 837 00:41:55,520 --> 00:41:56,350 Non. 838 00:41:56,350 --> 00:41:57,180 >> JASON HIRSCHHORN: Akshar? 839 00:41:57,180 --> 00:41:59,460 >> PUBLIC: Je pense que vous vouliez mettre retour faux à la fin 840 00:41:59,460 --> 00:42:02,230 de la boucle while. 841 00:42:02,230 --> 00:42:03,270 >> JASON HIRSCHHORN: Alors, où voulez-vous aller? 842 00:42:03,270 --> 00:42:05,270 >> PUBLIC: Comme l'extérieur de la boucle while. 843 00:42:05,270 --> 00:42:08,800 Donc, si vous quittez la boucle while que des moyens que vous avez atteint la fin et 844 00:42:08,800 --> 00:42:09,980 ne s'est rien passé. 845 00:42:09,980 --> 00:42:10,410 >> JASON HIRSCHHORN: OK. 846 00:42:10,410 --> 00:42:12,340 Alors, que faisons-nous ici? 847 00:42:12,340 --> 00:42:13,702 >> PUBLIC: Vous revenez faux là aussi. 848 00:42:13,702 --> 00:42:15,040 >> JASON HIRSCHHORN: Oh, nous faire dans les deux endroits? 849 00:42:15,040 --> 00:42:15,650 >> PUBLIC: Ouais. 850 00:42:15,650 --> 00:42:16,900 >> JASON HIRSCHHORN: OK. 851 00:42:16,900 --> 00:42:24,840 852 00:42:24,840 --> 00:42:26,160 Faut-il aller? 853 00:42:26,160 --> 00:42:26,980 Oh mon Dieu. 854 00:42:26,980 --> 00:42:27,290 Je suis désolé. 855 00:42:27,290 --> 00:42:28,480 Je m'excuse pour l'écran. 856 00:42:28,480 --> 00:42:30,530 C'est une sorte de flipper sur nous. 857 00:42:30,530 --> 00:42:31,520 Alors, choisissez une option. 858 00:42:31,520 --> 00:42:35,260 Zéro, par le code, quitte le programme. 859 00:42:35,260 --> 00:42:36,700 On insère quelque chose. 860 00:42:36,700 --> 00:42:37,990 Insérons trois. 861 00:42:37,990 --> 00:42:42,900 862 00:42:42,900 --> 00:42:45,380 L'insert a échoué. 863 00:42:45,380 --> 00:42:46,500 Je vais imprimer. 864 00:42:46,500 --> 00:42:48,050 Je n'ai rien. 865 00:42:48,050 --> 00:42:48,450 OK. 866 00:42:48,450 --> 00:42:50,250 Peut-être que c'était juste un coup de chance. 867 00:42:50,250 --> 00:42:52,810 Insérez un. 868 00:42:52,810 --> 00:42:55,770 Pas réussi. 869 00:42:55,770 --> 00:42:57,470 OK. 870 00:42:57,470 --> 00:43:02,400 Lançons par GDB très rapidement de vérifier ce qui se passe. 871 00:43:02,400 --> 00:43:06,055 >> Rappelez-vous gdb. / Le nom de votre programme nous met dans GDB. 872 00:43:06,055 --> 00:43:07,610 Est-ce beaucoup à gérer? 873 00:43:07,610 --> 00:43:08,560 Le clignotant? 874 00:43:08,560 --> 00:43:10,400 Probablement. 875 00:43:10,400 --> 00:43:12,760 Fermez vos yeux et prendre un peu de profondeur respirations si vous êtes fatigués 876 00:43:12,760 --> 00:43:13,580 de voir les choses. 877 00:43:13,580 --> 00:43:14,200 Je suis dans GDB. 878 00:43:14,200 --> 00:43:15,830 Quelle est la première chose que je fais dans GDB? 879 00:43:15,830 --> 00:43:17,050 Nous devons comprendre ce qui se passe ici. 880 00:43:17,050 --> 00:43:17,310 Voyons. 881 00:43:17,310 --> 00:43:21,650 Nous avons six minutes pour comprendre ce qui se passe. 882 00:43:21,650 --> 00:43:22,900 Cassez principale. 883 00:43:22,900 --> 00:43:25,950 884 00:43:25,950 --> 00:43:28,130 Et puis ce que je fais? 885 00:43:28,130 --> 00:43:29,180 Carlos? 886 00:43:29,180 --> 00:43:31,060 Exécutez. 887 00:43:31,060 --> 00:43:32,250 OK. 888 00:43:32,250 --> 00:43:34,160 Choisissons une option. 889 00:43:34,160 --> 00:43:36,330 Et ce ne N faire? 890 00:43:36,330 --> 00:43:38,480 Suivant. 891 00:43:38,480 --> 00:43:38,950 Ouais. 892 00:43:38,950 --> 00:43:39,740 >> PUBLIC: Vous n'avez pas mentionné - 893 00:43:39,740 --> 00:43:45,230 vous n'avez pas dit que la tête, il était initialisée à null au début. 894 00:43:45,230 --> 00:43:47,140 Mais je pensais que vous avez dit que c'était OK. 895 00:43:47,140 --> 00:43:50,040 896 00:43:50,040 --> 00:43:52,640 >> JASON HIRSCHHORN: Allons - regardons dans GDB, et puis nous allons revenir. 897 00:43:52,640 --> 00:43:54,910 Mais il semble que vous avez déjà quelques idées sur ce qui se passe. 898 00:43:54,910 --> 00:43:58,340 Donc, nous voulons insérer quelque chose. 899 00:43:58,340 --> 00:43:59,390 OK. 900 00:43:59,390 --> 00:44:00,150 Nous avons insérer. 901 00:44:00,150 --> 00:44:00,770 S'il vous plaît entrer un entier. 902 00:44:00,770 --> 00:44:01,990 Nous allons insérer trois. 903 00:44:01,990 --> 00:44:03,000 Et puis je suis sur cette ligne. 904 00:44:03,000 --> 00:44:07,030 Comment puis-je démarrer le débogage l'insert fonction connue? 905 00:44:07,030 --> 00:44:08,280 Oh mon Dieu. 906 00:44:08,280 --> 00:44:10,990 907 00:44:10,990 --> 00:44:12,240 C'est beaucoup. 908 00:44:12,240 --> 00:44:14,372 909 00:44:14,372 --> 00:44:16,445 Est-ce que paniquer beaucoup? 910 00:44:16,445 --> 00:44:19,696 911 00:44:19,696 --> 00:44:21,680 >> PUBLIC: Oh, il est mort. 912 00:44:21,680 --> 00:44:22,930 >> JASON HIRSCHHORN: Je ai sorti. 913 00:44:22,930 --> 00:44:27,364 914 00:44:27,364 --> 00:44:28,310 OK. 915 00:44:28,310 --> 00:44:29,560 >> PUBLIC: C'est peut-être la l'autre extrémité du fil. 916 00:44:29,560 --> 00:44:37,000 917 00:44:37,000 --> 00:44:39,470 >> JASON HIRSCHHORN: Wow. 918 00:44:39,470 --> 00:44:42,330 Ainsi, la ligne de fond - 919 00:44:42,330 --> 00:44:43,470 qu'avez-vous dit? 920 00:44:43,470 --> 00:44:46,040 >> PUBLIC: je l'ai dit l'ironie de la technique difficultés dans cette classe. 921 00:44:46,040 --> 00:44:46,410 >> JASON HIRSCHHORN: Je sais. 922 00:44:46,410 --> 00:44:48,660 Si seulement j'avais le contrôle de la partie. 923 00:44:48,660 --> 00:44:49,910 [Inaudible] 924 00:44:49,910 --> 00:44:54,430 925 00:44:54,430 --> 00:44:55,400 Cela sonne bien. 926 00:44:55,400 --> 00:44:58,680 Pourquoi avez-vous les gars commencent pas à penser à ce que nous aurions pu faire de mal, 927 00:44:58,680 --> 00:45:01,140 et nous serons de retour en 90 secondes. 928 00:45:01,140 --> 00:46:18,160 929 00:46:18,160 --> 00:46:23,010 >> Avica, je vais vous demander comment aller insert_node intérieur pour déboguer. 930 00:46:23,010 --> 00:46:28,940 931 00:46:28,940 --> 00:46:31,460 C'est donc là que nous nous sommes quittés. 932 00:46:31,460 --> 00:46:35,110 Comment dois-je aller à l'intérieur insert_node, Avica, d'examiner ce qui se passe? 933 00:46:35,110 --> 00:46:36,360 Quelle commande GDB? 934 00:46:36,360 --> 00:46:41,050 935 00:46:41,050 --> 00:46:42,390 Pause ne me prendrait pas à l'intérieur. 936 00:46:42,390 --> 00:46:46,200 937 00:46:46,200 --> 00:46:47,130 Ne marquise sait? 938 00:46:47,130 --> 00:46:48,240 >> PUBLIC: Quoi? 939 00:46:48,240 --> 00:46:51,780 >> JASON HIRSCHHORN: Quelle commande GDB Que j'utilise pour aller à l'intérieur de cette fonction? 940 00:46:51,780 --> 00:46:52,070 >> PUBLIC: étape? 941 00:46:52,070 --> 00:46:55,140 >> JASON HIRSCHHORN: étape par S. Cela me prend à l'intérieur. 942 00:46:55,140 --> 00:46:55,476 OK. 943 00:46:55,476 --> 00:46:58,040 New_node allouer de l'espace. 944 00:46:58,040 --> 00:46:59,120 C'est tout ressemble à sa va. 945 00:46:59,120 --> 00:47:00,370 Examinons new_node. 946 00:47:00,370 --> 00:47:03,270 947 00:47:03,270 --> 00:47:05,410 Il a obtenu une adresse mémoire. 948 00:47:05,410 --> 00:47:07,440 Voyons - 949 00:47:07,440 --> 00:47:08,500 c'est tout bon. 950 00:47:08,500 --> 00:47:12,220 Donc, tout ici semble travailler correctement. 951 00:47:12,220 --> 00:47:14,530 >> PUBLIC: Quelle est la différence entre P et l'affichage? 952 00:47:14,530 --> 00:47:16,160 >> JASON HIRSCHHORN: P pour imprimer. 953 00:47:16,160 --> 00:47:19,310 Et si vous vous demandez quelle est la différence entre cela et ce? 954 00:47:19,310 --> 00:47:22,330 Dans ce cas, rien. 955 00:47:22,330 --> 00:47:26,960 Mais en général, il ya certaines différences. 956 00:47:26,960 --> 00:47:28,220 Et vous devriez regarder dans le manuel GDB. 957 00:47:28,220 --> 00:47:29,560 Mais dans ce cas, rien. 958 00:47:29,560 --> 00:47:31,460 Nous avons tendance à utiliser l'impression, cependant, parce que nous n'avons pas besoin de faire beaucoup plus que 959 00:47:31,460 --> 00:47:33,960 imprimer une seule valeur. 960 00:47:33,960 --> 00:47:34,640 >> OK. 961 00:47:34,640 --> 00:47:40,300 Donc, nous sommes sur la ligne 80 de notre code, mettant le noeud * curr égale à la liste. 962 00:47:40,300 --> 00:47:42,500 Laissez-nous imprimons Curr. 963 00:47:42,500 --> 00:47:45,260 964 00:47:45,260 --> 00:47:46,840 Elle est égale à la liste. 965 00:47:46,840 --> 00:47:48,850 Sweet. 966 00:47:48,850 --> 00:47:49,340 Attendez. 967 00:47:49,340 --> 00:47:50,590 Elle est égale à quelque chose. 968 00:47:50,590 --> 00:47:53,680 969 00:47:53,680 --> 00:47:56,190 Cela ne semble pas juste. 970 00:47:56,190 --> 00:47:56,840 Nous y voilà. 971 00:47:56,840 --> 00:47:59,470 C'est parce que dans GDB, à droite, si c'est la ligne que vous êtes dessus 972 00:47:59,470 --> 00:48:00,330 n'a pas encore exécuté. 973 00:48:00,330 --> 00:48:03,100 Donc, vous devez taper effectivement prochaine pour exécuter la ligne 974 00:48:03,100 --> 00:48:05,230 avant de voir ses résultats. 975 00:48:05,230 --> 00:48:06,680 Donc nous sommes ici. 976 00:48:06,680 --> 00:48:09,490 Nous venons exécuté cette ligne, précédente est égal à zéro. 977 00:48:09,490 --> 00:48:13,590 Encore une fois, si nous imprimons précédente nous ne verrons pas quelque chose de bizarre. 978 00:48:13,590 --> 00:48:18,680 Mais si nous exécutons fait que ligne, puis nous verrons 979 00:48:18,680 --> 00:48:20,380 que cette ligne a travaillé. 980 00:48:20,380 --> 00:48:21,060 >> Nous avons donc Curr. 981 00:48:21,060 --> 00:48:23,180 Ce sont deux très bons. 982 00:48:23,180 --> 00:48:24,010 Droite? 983 00:48:24,010 --> 00:48:28,130 Maintenant, nous sommes sur cette ligne ici. 984 00:48:28,130 --> 00:48:29,310 Alors que curr n'est pas égal à zéro. 985 00:48:29,310 --> 00:48:31,110 Eh bien, qu'est-ce que curr égal? 986 00:48:31,110 --> 00:48:32,450 Nous venons de voir qu'il a égalé nulle. 987 00:48:32,450 --> 00:48:33,210 Nous avons imprimé le. 988 00:48:33,210 --> 00:48:35,110 Je vais l'imprimer à nouveau. 989 00:48:35,110 --> 00:48:36,720 Alors est ce que la boucle while va exécuter? 990 00:48:36,720 --> 00:48:37,270 >> PUBLIC: Non 991 00:48:37,270 --> 00:48:39,790 >> JASON HIRSCHHORN: Alors, quand j'ai tapé que ligne, vous voyez, nous avons sauté tout le chemin 992 00:48:39,790 --> 00:48:41,390 vers le bas, retourner false. 993 00:48:41,390 --> 00:48:44,520 Et puis nous allons revenir faux et revenir à notre programme et 994 00:48:44,520 --> 00:48:48,020 éventuellement imprimer, comme nous l'avons vu, l'insert n'a pas réussi. 995 00:48:48,020 --> 00:48:51,010 Donc, quelqu'un a des idées sur ce que nous devons faire pour résoudre ce problème? 996 00:48:51,010 --> 00:48:54,200 997 00:48:54,200 --> 00:48:57,570 Je vais attendre jusqu'à ce que je vois un couple de mains se lèvent. 998 00:48:57,570 --> 00:48:58,830 Nous n'avons pas exécuter cette. 999 00:48:58,830 --> 00:49:01,660 Gardez à l'esprit, c'était la première chose que nous faisions. 1000 00:49:01,660 --> 00:49:02,430 Je ne vais pas faire un couple. 1001 00:49:02,430 --> 00:49:03,670 Je vais faire un peu. 1002 00:49:03,670 --> 00:49:04,830 Parce que un couple deux moyens. 1003 00:49:04,830 --> 00:49:07,620 Je vais attendre plus de deux. 1004 00:49:07,620 --> 00:49:10,690 >> La première insertion, Curr, par défaut est égale à zéro. 1005 00:49:10,690 --> 00:49:14,050 Et cette boucle ne s'exécute que si curr n'est pas nulle. 1006 00:49:14,050 --> 00:49:18,740 Alors, comment puis-je contourner ce? 1007 00:49:18,740 --> 00:49:19,990 Je vois trois mains. 1008 00:49:19,990 --> 00:49:28,490 1009 00:49:28,490 --> 00:49:29,780 Je vais attendre plus de trois. 1010 00:49:29,780 --> 00:49:33,460 1011 00:49:33,460 --> 00:49:35,940 Marcus, que pensez-vous? 1012 00:49:35,940 --> 00:49:37,730 >> PUBLIC: Eh bien, si vous en avez besoin exécuter plus d'une fois, vous venez 1013 00:49:37,730 --> 00:49:39,948 changer pour une boucle do-while. 1014 00:49:39,948 --> 00:49:41,250 >> JASON HIRSCHHORN: OK. 1015 00:49:41,250 --> 00:49:44,240 Est-ce que résoudre notre problème, si? 1016 00:49:44,240 --> 00:49:47,750 >> PUBLIC: Dans ce cas, aucune raison de le fait que la liste est vide. 1017 00:49:47,750 --> 00:49:52,150 Alors vous avez probablement juste besoin d'ajouter une déclaration que si la boucle s'arrête 1018 00:49:52,150 --> 00:49:55,312 alors vous devez être à la fin de la liste, à laquelle vous pointez 1019 00:49:55,312 --> 00:49:56,562 peut simplement insérer. 1020 00:49:56,562 --> 00:49:58,920 1021 00:49:58,920 --> 00:49:59,680 >> JASON HIRSCHHORN: j'aime ça. 1022 00:49:59,680 --> 00:50:00,500 C'est logique. 1023 00:50:00,500 --> 00:50:03,390 Si la boucle sort - 1024 00:50:03,390 --> 00:50:04,800 parce que ça va revenir faux ici. 1025 00:50:04,800 --> 00:50:08,220 Donc, si la boucle s'arrête, alors nous sommes à la fin de la liste, ou peut-être l' 1026 00:50:08,220 --> 00:50:10,690 le début d'une liste si il n'y a rien dans , ce qui est la même que la fin. 1027 00:50:10,690 --> 00:50:12,770 Alors maintenant, nous voulons insérer quelque chose ici. 1028 00:50:12,770 --> 00:50:17,380 Alors, comment est-ce que le code regardez, Marcus? 1029 00:50:17,380 --> 00:50:21,600 >> AUDIENCE: Si vous avez déjà eu le nœud malloced, vous pouvez simplement dire 1030 00:50:21,600 --> 00:50:25,400 new_node-> égaux prochain nulle car il doit être à la fin. 1031 00:50:25,400 --> 00:50:27,510 Ou new_node-> égale prochain nulle. 1032 00:50:27,510 --> 00:50:27,765 >> JASON HIRSCHHORN: OK. 1033 00:50:27,765 --> 00:50:28,190 Désolé. 1034 00:50:28,190 --> 00:50:35,760 New_node-> égaux prochaine null parce que nous sommes à la fin. 1035 00:50:35,760 --> 00:50:36,460 Cela ne met pas po 1036 00:50:36,460 --> 00:50:37,710 Comment pouvons-nous mettre dans la liste? 1037 00:50:37,710 --> 00:50:46,130 1038 00:50:46,130 --> 00:50:46,460 Droite. 1039 00:50:46,460 --> 00:50:47,750 C'est juste le mettre à égalité. 1040 00:50:47,750 --> 00:50:50,940 Non, comment pouvons-nous réellement mettre dans la liste? 1041 00:50:50,940 --> 00:50:54,170 Qu'est-ce qui pointant vers le fin de la liste? 1042 00:50:54,170 --> 00:50:56,090 >> PUBLIC: Head. 1043 00:50:56,090 --> 00:50:57,566 >> JASON HIRSCHHORN: Désolé? 1044 00:50:57,566 --> 00:50:59,440 >> PUBLIC: Chef pointe à la fin de la liste. 1045 00:50:59,440 --> 00:51:01,480 >> JASON HIRSCHHORN: S'il n'y a rien dans la liste, la tête est orientée vers la 1046 00:51:01,480 --> 00:51:04,170 fin de la liste. 1047 00:51:04,170 --> 00:51:06,920 Alors qui va travailler pour la la première insertion. 1048 00:51:06,920 --> 00:51:09,810 Qu'en est-il si il ya un couple choses dans la liste? 1049 00:51:09,810 --> 00:51:12,470 Que nous ne voulons pas mettre en diriger égale à new_node. 1050 00:51:12,470 --> 00:51:13,790 Que voulons-nous y faire? 1051 00:51:13,790 --> 00:51:15,610 Ouais? 1052 00:51:15,610 --> 00:51:16,860 Probablement précédente. 1053 00:51:16,860 --> 00:51:23,560 1054 00:51:23,560 --> 00:51:24,810 Est-ce que travailler? 1055 00:51:24,810 --> 00:51:28,950 1056 00:51:28,950 --> 00:51:33,050 Rappelons que précédente est juste un pointeur vers un noeud. 1057 00:51:33,050 --> 00:51:34,770 Et précédente est une variable locale. 1058 00:51:34,770 --> 00:51:38,080 Donc, cette ligne sera de définir une variable locale, précédente, égale ou 1059 00:51:38,080 --> 00:51:39,380 pointant vers ce nouveau nœud. 1060 00:51:39,380 --> 00:51:41,500 Ce ne sera pas fait mettre dans notre liste, si. 1061 00:51:41,500 --> 00:51:44,330 Comment pouvons-nous mettre dans notre liste? 1062 00:51:44,330 --> 00:51:45,620 Akchar? 1063 00:51:45,620 --> 00:51:46,870 >> PUBLIC: Je pense que vous faire current-> suivant. 1064 00:51:46,870 --> 00:51:50,186 1065 00:51:50,186 --> 00:51:52,550 >> JASON HIRSCHHORN: OK. 1066 00:51:52,550 --> 00:51:54,010 curr-> suivant. 1067 00:51:54,010 --> 00:51:58,768 Encore une fois, la seule raison pour laquelle nous en sommes ici, c'est ce que fait courant égal? 1068 00:51:58,768 --> 00:51:59,760 >> PUBLIC: Equals nulle. 1069 00:51:59,760 --> 00:52:01,790 >> JASON HIRSCHHORN: Et qu'est-ce qui se passe si nous faisons null-> next? 1070 00:52:01,790 --> 00:52:02,810 Qu'est-ce qu'on va faire? 1071 00:52:02,810 --> 00:52:04,060 Nous aurons une erreur de segmentation. 1072 00:52:04,060 --> 00:52:06,600 1073 00:52:06,600 --> 00:52:08,880 >> PUBLIC: Do curr vaut NULL. 1074 00:52:08,880 --> 00:52:10,760 >> JASON HIRSCHHORN: C'est la même chose comme précédent, cependant, car il ya 1075 00:52:10,760 --> 00:52:12,820 une variable locale, nous mettons en place égal à ce nouveau noeud. 1076 00:52:12,820 --> 00:52:16,680 1077 00:52:16,680 --> 00:52:20,920 Revenons à notre image l'insertion de quelque chose. 1078 00:52:20,920 --> 00:52:25,500 Disons que nous sommes l'insertion à la fin de la liste, de sorte ici. 1079 00:52:25,500 --> 00:52:30,010 Nous avons un pointeur courant qui est pointant à null et un point précédent 1080 00:52:30,010 --> 00:52:32,800 C'est pointant à 8. 1081 00:52:32,800 --> 00:52:35,330 Alors que devons-nous pour mettre à jour, Avi? 1082 00:52:35,330 --> 00:52:36,680 >> PUBLIC: Précédent-> next? 1083 00:52:36,680 --> 00:52:41,980 >> JASON HIRSCHHORN: Précédent-> est ce que la prochaine nous voulons mettre à jour parce que 1084 00:52:41,980 --> 00:52:44,960 seront effectivement insérer à la fin de la liste. 1085 00:52:44,960 --> 00:52:47,220 Nous avons encore un bug, si, que nous allons rencontrer. 1086 00:52:47,220 --> 00:52:50,090 Quel est ce bug? 1087 00:52:50,090 --> 00:52:50,790 Ouais? 1088 00:52:50,790 --> 00:52:53,860 >> PUBLIC: Il va revenir faux dans ce cas? 1089 00:52:53,860 --> 00:52:56,380 >> JASON HIRSCHHORN: Oh, est est va retourner false. 1090 00:52:56,380 --> 00:52:57,430 Mais il ya un autre bug. 1091 00:52:57,430 --> 00:52:58,930 Nous devons donc mettre en return true. 1092 00:52:58,930 --> 00:53:01,370 >> PUBLIC: Ne précédente toujours à égalité nulle en haut de la liste? 1093 00:53:01,370 --> 00:53:03,645 >> JASON HIRSCHHORN: encore Donc précédente est égal à zéro au début. 1094 00:53:03,645 --> 00:53:07,480 1095 00:53:07,480 --> 00:53:10,440 Alors, comment pouvons-nous obtenir plus de cela? 1096 00:53:10,440 --> 00:53:10,950 Ouais? 1097 00:53:10,950 --> 00:53:15,280 >> PUBLIC: Je pense que vous pouvez faire un chèque avant la boucle while pour voir si c'est 1098 00:53:15,280 --> 00:53:16,610 une liste vide. 1099 00:53:16,610 --> 00:53:17,000 >> JASON HIRSCHHORN: OK. 1100 00:53:17,000 --> 00:53:17,710 Allons donc ici. 1101 00:53:17,710 --> 00:53:18,530 Faites une vérification. 1102 00:53:18,530 --> 00:53:19,380 Si - 1103 00:53:19,380 --> 00:53:20,770 >> PUBLIC: Donc, si la tête est égal à égal nulle. 1104 00:53:20,770 --> 00:53:24,300 1105 00:53:24,300 --> 00:53:26,320 >> JASON HIRSCHHORN: Si la tête est égal à égal nulle - 1106 00:53:26,320 --> 00:53:27,790 qui nous dira si c'est une liste vide. 1107 00:53:27,790 --> 00:53:31,090 >> PUBLIC: Et puis vous faire face est de nouveau. 1108 00:53:31,090 --> 00:53:34,740 >> JASON HIRSCHHORN: Head égaux new_node? 1109 00:53:34,740 --> 00:53:35,730 Et quoi d'autre avons-nous besoin de le faire? 1110 00:53:35,730 --> 00:53:37,020 >> PUBLIC: Et puis vous revenez vrai. 1111 00:53:37,020 --> 00:53:37,535 >> JASON HIRSCHHORN: Pas tout à fait. 1112 00:53:37,535 --> 00:53:38,785 Il nous manque une étape. 1113 00:53:38,785 --> 00:53:41,590 1114 00:53:41,590 --> 00:53:43,710 >> PUBLIC: New_node prochaine doit indiquer la valeur null. 1115 00:53:43,710 --> 00:53:44,570 >> JASON HIRSCHHORN: Exactement, Alden. 1116 00:53:44,570 --> 00:53:46,600 Et puis nous pouvons retourner true. 1117 00:53:46,600 --> 00:53:47,560 OK. 1118 00:53:47,560 --> 00:53:51,630 Mais c'est toujours une bonne idée de faire des choses à la fin de la liste, non? 1119 00:53:51,630 --> 00:53:51,950 Très bien. 1120 00:53:51,950 --> 00:53:54,450 Nous pourrions encore réellement obtenir à la fin de la liste. 1121 00:53:54,450 --> 00:53:57,870 Alors est ce code bien si nous sommes à la fin de la liste et il ya quelques 1122 00:53:57,870 --> 00:53:59,120 choses dans la liste? 1123 00:53:59,120 --> 00:54:01,830 1124 00:54:01,830 --> 00:54:02,040 Droite? 1125 00:54:02,040 --> 00:54:03,540 Parce que nous avons toujours l'idée de Marcus. 1126 00:54:03,540 --> 00:54:06,870 Nous pourrions sortir de cette boucle, car nous sommes à la fin de la liste. 1127 00:54:06,870 --> 00:54:09,308 Ainsi voulons-nous toujours ce coder ici? 1128 00:54:09,308 --> 00:54:10,520 >> PUBLIC: Oui. 1129 00:54:10,520 --> 00:54:11,000 >> JASON HIRSCHHORN: Ouais. 1130 00:54:11,000 --> 00:54:14,190 Et que devons-nous changer cela? 1131 00:54:14,190 --> 00:54:15,440 Vrai. 1132 00:54:15,440 --> 00:54:19,580 1133 00:54:19,580 --> 00:54:21,640 Est-ce que bon son à tout le monde à ce jour? 1134 00:54:21,640 --> 00:54:22,420 Quelqu'un a une - 1135 00:54:22,420 --> 00:54:23,480 Avi, avez-vous quelque chose à ajouter? 1136 00:54:23,480 --> 00:54:23,920 >> PUBLIC: Non 1137 00:54:23,920 --> 00:54:25,276 >> JASON HIRSCHHORN: OK. 1138 00:54:25,276 --> 00:54:27,010 Nous avons donc fait quelques changements. 1139 00:54:27,010 --> 00:54:29,540 Nous avons fait cette vérification avant est allé dans une liste vide. 1140 00:54:29,540 --> 00:54:31,790 Donc, nous avons pris soin d'une liste vide. 1141 00:54:31,790 --> 00:54:35,500 Et ici nous avons pris soin d'insérer quelque chose à la fin de la liste. 1142 00:54:35,500 --> 00:54:38,930 Il semble donc que cette prise de boucle while soin des choses entre les deux, 1143 00:54:38,930 --> 00:54:41,920 quelque part dans la liste si ya des choses dans la liste. 1144 00:54:41,920 --> 00:54:42,280 >> OK. 1145 00:54:42,280 --> 00:54:44,310 Courons de nouveau ce programme. 1146 00:54:44,310 --> 00:54:50,170 1147 00:54:50,170 --> 00:54:50,755 Pas réussi. 1148 00:54:50,755 --> 00:54:52,190 >> PUBLIC: Vous n'avez pas faites. 1149 00:54:52,190 --> 00:54:53,940 >> JASON HIRSCHHORN: Oh, Je n'ai pas réussi. 1150 00:54:53,940 --> 00:54:56,250 Bon point, Michael. 1151 00:54:56,250 --> 00:54:57,500 Ajoutons une marque liée. 1152 00:54:57,500 --> 00:55:01,590 1153 00:55:01,590 --> 00:55:04,830 Ligne 87 il ya une erreur. 1154 00:55:04,830 --> 00:55:05,420 Ligne 87. 1155 00:55:05,420 --> 00:55:06,600 Alden, c'est la ligne que vous m'avez donné. 1156 00:55:06,600 --> 00:55:08,962 Quel est le problème? 1157 00:55:08,962 --> 00:55:10,710 >> PUBLIC: Il doit être à null. 1158 00:55:10,710 --> 00:55:11,000 >> JASON HIRSCHHORN: Excellent. 1159 00:55:11,000 --> 00:55:11,630 Exactement. 1160 00:55:11,630 --> 00:55:13,290 Il devrait être nulle. 1161 00:55:13,290 --> 00:55:15,210 Faisons à nouveau. 1162 00:55:15,210 --> 00:55:17,220 Compiler. 1163 00:55:17,220 --> 00:55:17,890 OK. 1164 00:55:17,890 --> 00:55:19,400 Insérons trois. 1165 00:55:19,400 --> 00:55:20,570 L'insert a été réussie. 1166 00:55:20,570 --> 00:55:21,660 Disons imprimer. 1167 00:55:21,660 --> 00:55:23,590 Oh, si seulement nous pouvions vérifier. 1168 00:55:23,590 --> 00:55:25,500 Mais nous n'avons pas fait la imprimer encore la fonction. 1169 00:55:25,500 --> 00:55:27,840 Entrons autre chose. 1170 00:55:27,840 --> 00:55:29,090 Que devons-nous conclure? 1171 00:55:29,090 --> 00:55:31,120 1172 00:55:31,120 --> 00:55:31,940 >> PUBLIC: Seven. 1173 00:55:31,940 --> 00:55:33,340 >> JASON HIRSCHHORN: Seven? 1174 00:55:33,340 --> 00:55:34,590 >> PUBLIC: Oui. 1175 00:55:34,590 --> 00:55:38,680 1176 00:55:38,680 --> 00:55:39,780 >> JASON HIRSCHHORN: Nous avons une erreur de segmentation. 1177 00:55:39,780 --> 00:55:43,760 Donc, nous avons eu un, mais nous avons clairement ne peut pas avoir deux. 1178 00:55:43,760 --> 00:55:45,690 Il est 05h07. 1179 00:55:45,690 --> 00:55:48,370 Donc, nous pourrions déboguer ce pendant trois minutes. 1180 00:55:48,370 --> 00:55:51,240 Mais je vais nous laisser ici et de passer aux différentes tables. 1181 00:55:51,240 --> 00:55:54,290 Mais encore une fois, les réponses à ce code Je vais te l'envoyer dans un peu. 1182 00:55:54,290 --> 00:55:55,440 Nous sommes très près de lui. 1183 00:55:55,440 --> 00:55:58,300 Je vous encourage fortement à comprendre ce qui se passe ici et de le corriger. 1184 00:55:58,300 --> 00:56:02,400 Donc, je vais vous envoyer ce code bien plus de la solution - 1185 00:56:02,400 --> 00:56:03,670 probablement la solution par la suite. 1186 00:56:03,670 --> 00:56:05,110 Première ce code. 1187 00:56:05,110 --> 00:56:08,290 >> L'autre chose que je veux faire avant de nous finition est que nous n'avons pas libéré rien. 1188 00:56:08,290 --> 00:56:10,370 Je tiens donc à vous montrer ce que valgrind ressemble. 1189 00:56:10,370 --> 00:56:14,310 Si nous courons limites de valgrind sur notre programme. / lié. 1190 00:56:14,310 --> 00:56:22,540 Encore une fois, selon cette diapositive, nous devrait fonctionner valgrind avec un certain type de 1191 00:56:22,540 --> 00:56:26,410 possibilité, dans ce cas, - Fuite chèque = plein. 1192 00:56:26,410 --> 00:56:27,660 Donc, nous allons écrire valgrind - Fuite chèque = plein. 1193 00:56:27,660 --> 00:56:31,910 1194 00:56:31,910 --> 00:56:35,080 Donc, ce sera exécuter valgrind sur notre programme. 1195 00:56:35,080 --> 00:56:37,000 Et maintenant, le programme fonctionne réellement. 1196 00:56:37,000 --> 00:56:40,190 Donc, nous allons le faire fonctionner comme avant, mettre quelque chose po 1197 00:56:40,190 --> 00:56:40,830 Je vais mettre trois. 1198 00:56:40,830 --> 00:56:41,790 Cela fonctionne. 1199 00:56:41,790 --> 00:56:43,202 Je ne vais pas essayer de mettre quelque chose d'autre parce que nous allons 1200 00:56:43,202 --> 00:56:44,710 obtenir un faux segment dans ce cas. 1201 00:56:44,710 --> 00:56:46,700 Donc, je vais juste arrêter de fumer. 1202 00:56:46,700 --> 00:56:50,160 >> Et maintenant vous voyez ici fuir et résumé du tas. 1203 00:56:50,160 --> 00:56:52,310 Ce sont les bonnes choses que vous voulez vérifier. 1204 00:56:52,310 --> 00:56:56,780 Ainsi, le résumé de tas - il dit, en utilisation à la sortie - huit octets dans un bloc. 1205 00:56:56,780 --> 00:56:58,370 C'est un bloc est l' nœud nous malloced. 1206 00:56:58,370 --> 00:57:02,230 Michael, vous avez dit avant un nœud est de huit morsures, car il a l'entier 1207 00:57:02,230 --> 00:57:02,680 et le pointeur. 1208 00:57:02,680 --> 00:57:04,550 C'est donc notre nœud. 1209 00:57:04,550 --> 00:57:08,170 Et puis il dit que nous avons utilisé malloc sept fois et nous avons libéré 1210 00:57:08,170 --> 00:57:08,940 quelque chose de six fois. 1211 00:57:08,940 --> 00:57:13,680 Mais nous n'avons jamais dit libre, donc je n'ai pas idée de ce que parle. 1212 00:57:13,680 --> 00:57:18,490 >> Mais il suffit de dire que lorsque votre programme s'exécute, malloc est appelé 1213 00:57:18,490 --> 00:57:20,330 dans d'autres endroits que nous n'ont pas besoin de s'inquiéter. 1214 00:57:20,330 --> 00:57:22,460 Donc malloc a probablement été appelé dans certains endroits. 1215 00:57:22,460 --> 00:57:24,480 Nous n'avons pas besoin de s'inquiéter où. 1216 00:57:24,480 --> 00:57:26,240 Mais c'est vraiment nous. 1217 00:57:26,240 --> 00:57:27,380 Cette première ligne, c'est nous. 1218 00:57:27,380 --> 00:57:28,320 Nous avons quitté ce bloc. 1219 00:57:28,320 --> 00:57:30,330 Et vous pouvez voir que ici dans le résumé de fuite. 1220 00:57:30,330 --> 00:57:31,950 Toujours accessible - 1221 00:57:31,950 --> 00:57:32,930 huit octets dans un bloc. 1222 00:57:32,930 --> 00:57:34,100 Cela signifie que la mémoire - 1223 00:57:34,100 --> 00:57:35,730 nous avons fui cette mémoire. 1224 00:57:35,730 --> 00:57:37,570 Définitivement perdu - 1225 00:57:37,570 --> 00:57:38,770 quelque chose est perdu pour de bon. 1226 00:57:38,770 --> 00:57:40,590 En général, vous ne serez pas voir du tout. 1227 00:57:40,590 --> 00:57:44,780 Toujours est généralement accessible où vous voyez les choses, où vous voulez 1228 00:57:44,780 --> 00:57:48,900 à regarder pour voir ce code devrait ont libéré mais vous avez oublié de libérer. 1229 00:57:48,900 --> 00:57:53,170 >> Et puis, si ce n'était pas le cas, si nous avons fait tout gratuit, 1230 00:57:53,170 --> 00:57:54,360 nous pouvons vérifier cela. 1231 00:57:54,360 --> 00:57:57,330 Disons simplement exécuter le programme ne pas mettre en quoi que ce soit. 1232 00:57:57,330 --> 00:57:59,800 Vous verrez ici en usage à la sortie - 1233 00:57:59,800 --> 00:58:01,310 de zéro octets blocs nuls. 1234 00:58:01,310 --> 00:58:06,310 Cela signifie que nous n'avions plus rien lorsque ce programme est sorti. 1235 00:58:06,310 --> 00:58:12,090 Donc, avant de tourner dans pset6, valgrind exécuter et assurez-vous que vous n'avez pas 1236 00:58:12,090 --> 00:58:15,310 tout fuites de mémoire dans votre programme. 1237 00:58:15,310 --> 00:58:17,910 Si vous avez des questions valgrind, n'hésitez pas à atteindre. 1238 00:58:17,910 --> 00:58:18,700 Mais c'est la façon dont vous l'utilisez. 1239 00:58:18,700 --> 00:58:20,890 Très simple - voir si vous ont utilisé à la sortie - 1240 00:58:20,890 --> 00:58:22,270 les octets de tous les blocs. 1241 00:58:22,270 --> 00:58:27,890 1242 00:58:27,890 --> 00:58:29,580 >> Donc, nous avons travaillé sur le noeud d'insertion. 1243 00:58:29,580 --> 00:58:33,840 J'ai eu deux autres fonctions ici - imprimer noeuds et noeuds libres. 1244 00:58:33,840 --> 00:58:37,780 Là encore, ce sont des fonctions qui sont va être bon pour vous de pratiquer 1245 00:58:37,780 --> 00:58:40,990 car ils vous aideront non seulement avec ces exemples d'exercices, mais aussi 1246 00:58:40,990 --> 00:58:42,180 sur le problème posé. 1247 00:58:42,180 --> 00:58:44,230 Ils carte sur d'assez près aux choses vous allez avoir à faire dans le 1248 00:58:44,230 --> 00:58:45,010 problème réglé. 1249 00:58:45,010 --> 00:58:47,640 Mais je ne veux m'assurer nous touchons à tout. 1250 00:58:47,640 --> 00:58:50,400 Et les tables de hachage sont également cruciales pour ce que nous faisons dans la section de ce 1251 00:58:50,400 --> 00:58:51,980 semaines - ou dans le jeu de problème. 1252 00:58:51,980 --> 00:58:55,200 >> Donc, nous allons terminer la section parler de tables de hachage. 1253 00:58:55,200 --> 00:58:58,140 Si vous remarquez, j'ai fait une petite table de hachage. 1254 00:58:58,140 --> 00:59:00,020 Ce n'est pas ce dont nous parlons sur, cependant. 1255 00:59:00,020 --> 00:59:03,540 Nous parlons d'un autre type de tables de hachage. 1256 00:59:03,540 --> 00:59:07,300 Et à sa base, une table de hachage n'est rien de plus qu'un 1257 00:59:07,300 --> 00:59:08,860 tableau plus une fonction de hachage. 1258 00:59:08,860 --> 00:59:11,150 Nous allons parler un peu juste assurez-vous que tout le monde comprend ce qu'est un 1259 00:59:11,150 --> 00:59:12,110 fonction de hachage est. 1260 00:59:12,110 --> 00:59:15,420 Et je vous dis maintenant qu'il est rien de plus que deux choses - 1261 00:59:15,420 --> 00:59:18,590 une matrice et une fonction de hachage. 1262 00:59:18,590 --> 00:59:20,716 Et voici les étapes à ce qui fonctionne. 1263 00:59:20,716 --> 00:59:31,560 1264 00:59:31,560 --> 00:59:32,810 >> Voilà notre tableau. 1265 00:59:32,810 --> 00:59:38,460 1266 00:59:38,460 --> 00:59:39,460 Il ya notre fonction. 1267 00:59:39,460 --> 00:59:43,180 En particulier, les fonctions de hachage doivent faire une ou deux choses à ce sujet. 1268 00:59:43,180 --> 00:59:45,040 Je vais parler spécifiquement sur ce problème réglé. 1269 00:59:45,040 --> 00:59:46,450 Il va probablement prendre dans une chaîne. 1270 00:59:46,450 --> 00:59:50,570 1271 00:59:50,570 --> 00:59:51,770 Et qu'est-ce que ça va revenir? 1272 00:59:51,770 --> 00:59:52,640 Quel type de données? 1273 00:59:52,640 --> 00:59:54,260 Alden? 1274 00:59:54,260 --> 00:59:55,760 Votre fonction de hachage revenir? 1275 00:59:55,760 --> 00:59:58,760 Un entier. 1276 00:59:58,760 --> 01:00:01,700 Donc, c'est ce que le hachage table se compose de - 1277 01:00:01,700 --> 01:00:05,430 une table sous forme de tableau et une fonction de hachage. 1278 01:00:05,430 --> 01:00:06,010 Comment ça marche? 1279 01:00:06,010 --> 01:00:07,300 Il fonctionne en trois étapes. 1280 01:00:07,300 --> 01:00:08,740 Nous lui donnons une clé. 1281 01:00:08,740 --> 01:00:11,470 Dans ce cas, nous lui donnons une chaîne. 1282 01:00:11,470 --> 01:00:18,140 Nous appelons la fonction de hachage pour la première étape sur la touche et nous obtenons une valeur. 1283 01:00:18,140 --> 01:00:20,310 >> Plus précisément, nous dirons nous obtenons un nombre entier. 1284 01:00:20,310 --> 01:00:25,630 Cela entier, il ya très spécifique des limites à ce que peut être entier. 1285 01:00:25,630 --> 01:00:28,880 Dans cet exemple, notre matrice est de taille trois. 1286 01:00:28,880 --> 01:00:32,330 Donc, ce nombre peut être entier que. 1287 01:00:32,330 --> 01:00:35,970 Quelle est la plage de valeurs valides pour ce nombre entier, le type de ce retour 1288 01:00:35,970 --> 01:00:37,220 fonction de hachage? 1289 01:00:37,220 --> 01:00:40,440 1290 01:00:40,440 --> 01:00:42,110 Zéro, un et deux. 1291 01:00:42,110 --> 01:00:46,060 Le point de la fonction de hachage est de comprendre la place dans le tableau 1292 01:00:46,060 --> 01:00:47,790 où notre clé va. 1293 01:00:47,790 --> 01:00:51,290 Il n'y a que trois possibilités endroits ici - 1294 01:00:51,290 --> 01:00:52,130 zéro, un ou deux. 1295 01:00:52,130 --> 01:00:55,360 Donc, cette fonction meilleur rendement zéro, un ou deux. 1296 01:00:55,360 --> 01:00:58,740 Certains indice valable dans ce tableau. 1297 01:00:58,740 --> 01:01:02,770 >> Et puis en fonction de l'endroit où il retourne, vous pouvez y voir tableau ouvert 1298 01:01:02,770 --> 01:01:03,730 entourer la valeur. 1299 01:01:03,730 --> 01:01:05,800 C'est là que nous avons mis sur la touche. 1300 01:01:05,800 --> 01:01:11,280 Alors que nous jetons dans la citrouille, nous sortons zéro. 1301 01:01:11,280 --> 01:01:15,540 Au tableau support 0, nous avons mis la citrouille. 1302 01:01:15,540 --> 01:01:21,070 Nous jetons les chats, nous sortons un. 1303 01:01:21,070 --> 01:01:24,110 Nous mettons chat à un. 1304 01:01:24,110 --> 01:01:25,480 Nous avons mis en araignée. 1305 01:01:25,480 --> 01:01:26,710 Nous sortons deux. 1306 01:01:26,710 --> 01:01:30,200 Nous mettons araignée au tableau support deux. 1307 01:01:30,200 --> 01:01:32,300 Ce serait tellement bien si il a travaillé comme ça. 1308 01:01:32,300 --> 01:01:35,570 Mais malheureusement, comme nous le verrons, c'est un peu plus compliqué. 1309 01:01:35,570 --> 01:01:37,570 >> Avant d'y arriver, des questions de cette base 1310 01:01:37,570 --> 01:01:38,820 mise en place d'une table de hachage? 1311 01:01:38,820 --> 01:01:49,050 1312 01:01:49,050 --> 01:01:51,940 C'est une image d'exactement ce qui nous nous sommes inspirés du conseil. 1313 01:01:51,940 --> 01:01:55,420 Mais puisque nous avons tiré sur le bord, je je ne vais pas aller dans davantage. 1314 01:01:55,420 --> 01:02:00,430 Essentiellement touches, la boîte noire magique - ou dans ce cas, la boîte de sarcelle d'hiver - d'un 1315 01:02:00,430 --> 01:02:02,410 fonction de hachage les met dans des seaux. 1316 01:02:02,410 --> 01:02:04,690 Et dans cet exemple, nous sommes ne pas mettre le nom. 1317 01:02:04,690 --> 01:02:07,880 Nous mettons le téléphone associé nombre de son nom dans le seau. 1318 01:02:07,880 --> 01:02:10,430 Mais vous pourriez très bien juste mettre le nom dans le seau. 1319 01:02:10,430 --> 01:02:12,950 >> C'est juste une image de ce nous avons dessiné sur la carte. 1320 01:02:12,950 --> 01:02:14,460 Nous avons pièges potentiels, cependant. 1321 01:02:14,460 --> 01:02:17,470 Et il ya deux en particulier diapositives que je veux y aller. 1322 01:02:17,470 --> 01:02:20,230 La première est d'environ une fonction de hachage. 1323 01:02:20,230 --> 01:02:22,620 J'ai donc posé la question, ce qui fait une bonne fonction de hachage? 1324 01:02:22,620 --> 01:02:24,220 Je donne deux réponses. 1325 01:02:24,220 --> 01:02:26,630 La première, c'est qu'il est déterministe. 1326 01:02:26,630 --> 01:02:29,660 Dans le cadre de fonctions de hachage, qu'est-ce que cela signifie? 1327 01:02:29,660 --> 01:02:37,840 1328 01:02:37,840 --> 01:02:39,282 Oui? 1329 01:02:39,282 --> 01:02:42,850 >> PUBLIC: On peut trouver le indice en temps constant? 1330 01:02:42,850 --> 01:02:43,810 >> JASON HIRSCHHORN: C'est n'est pas ce que cela signifie. 1331 01:02:43,810 --> 01:02:44,725 Mais c'est une bonne proposition. 1332 01:02:44,725 --> 01:02:46,100 Quelqu'un d'autre a une proposition ce que cela signifie? 1333 01:02:46,100 --> 01:02:47,780 C'est une bonne fonction de hachage est déterministe? 1334 01:02:47,780 --> 01:02:48,280 Annie? 1335 01:02:48,280 --> 01:02:51,680 >> PUBLIC: C'est une clé ne peut être mappé à un seul endroit dans la table de hachage. 1336 01:02:51,680 --> 01:02:53,070 >> JASON HIRSCHHORN: C'est tout à fait exact. 1337 01:02:53,070 --> 01:02:57,430 Chaque fois que vous mettez dans la citrouille, elle retourne toujours zéro. 1338 01:02:57,430 --> 01:03:01,660 Si vous mettez dans votre citrouille et hachage la fonction renvoie zéro mais a une 1339 01:03:01,660 --> 01:03:06,060 probabilité de retourner quelque chose d'autre supérieur à zéro - 1340 01:03:06,060 --> 01:03:09,280 alors peut-être il peut renvoyer l'un, parfois ou deux autres fois - 1341 01:03:09,280 --> 01:03:11,100 ce n'est pas une bonne fonction de hachage. 1342 01:03:11,100 --> 01:03:11,800 Vous avez parfaitement raison. 1343 01:03:11,800 --> 01:03:15,680 Votre fonction de hachage doit retourner le même nombre entier exact, dans ce cas, pour 1344 01:03:15,680 --> 01:03:17,780 la même chaîne exacte. 1345 01:03:17,780 --> 01:03:22,210 >> Peut-être que renvoie le même nombre entier exact pour la même chaîne exacte 1346 01:03:22,210 --> 01:03:24,430 indépendamment de la capitalisation. 1347 01:03:24,430 --> 01:03:27,980 Mais dans ce cas, il est encore déterministe car plusieurs choses 1348 01:03:27,980 --> 01:03:29,350 sont mappés sur la même valeur. 1349 01:03:29,350 --> 01:03:30,170 C'est très bien. 1350 01:03:30,170 --> 01:03:32,615 Tant qu'il n'y a qu'un seul sortie pour une entrée donnée. 1351 01:03:32,615 --> 01:03:35,630 1352 01:03:35,630 --> 01:03:36,350 >> OK. 1353 01:03:36,350 --> 01:03:38,340 La deuxième chose est qu'il retourne indices valides. 1354 01:03:38,340 --> 01:03:40,220 Nous avons apporté jusqu'à l'heure. 1355 01:03:40,220 --> 01:03:41,860 Cette fonction de hachage - 1356 01:03:41,860 --> 01:03:43,710 oh boy - 1357 01:03:43,710 --> 01:03:46,840 une fonction de hachage devrait retourner indices valides. 1358 01:03:46,840 --> 01:03:47,740 Donc dire - 1359 01:03:47,740 --> 01:03:48,990 Revenons à notre exemple. 1360 01:03:48,990 --> 01:03:52,580 1361 01:03:52,580 --> 01:03:57,540 Ma fonction de hachage compte jusqu'à les lettres du mot. 1362 01:03:57,540 --> 01:03:58,380 C'est la fonction de hachage. 1363 01:03:58,380 --> 01:03:59,740 Et renvoie cet entier. 1364 01:03:59,740 --> 01:04:04,280 Donc, si j'ai le mot A, il est va revenir un. 1365 01:04:04,280 --> 01:04:06,900 Et il va mettre un ici. 1366 01:04:06,900 --> 01:04:09,430 Qu'est-ce que si je mets le mot chauve-souris? 1367 01:04:09,430 --> 01:04:11,310 Il va revenir trois. 1368 01:04:11,310 --> 01:04:12,560 Où aller chauve-souris? 1369 01:04:12,560 --> 01:04:18,730 1370 01:04:18,730 --> 01:04:19,750 >> Il ne convient pas. 1371 01:04:19,750 --> 01:04:21,000 Mais il a besoin d'aller quelque part. 1372 01:04:21,000 --> 01:04:23,340 C'est ma table de hachage après tout, et tout doit aller quelque part. 1373 01:04:23,340 --> 01:04:24,590 Alors, où devrait aller chauve-souris? 1374 01:04:24,590 --> 01:04:28,020 1375 01:04:28,020 --> 01:04:28,710 Des pensées? 1376 01:04:28,710 --> 01:04:29,450 Devine? 1377 01:04:29,450 --> 01:04:30,280 Bonnes suppositions? 1378 01:04:30,280 --> 01:04:31,220 >> PUBLIC: zéro. 1379 01:04:31,220 --> 01:04:32,120 >> JASON HIRSCHHORN: Pourquoi zéro? 1380 01:04:32,120 --> 01:04:35,990 >> PUBLIC: Parce que trois modulo trois est égal à zéro? 1381 01:04:35,990 --> 01:04:38,620 >> JASON HIRSCHHORN: Trois modulo trois est égal à zéro. 1382 01:04:38,620 --> 01:04:40,810 C'est une grande proposition, et c'est exact. 1383 01:04:40,810 --> 01:04:43,870 Donc, dans ce cas, il devrait probablement aller à zéro. 1384 01:04:43,870 --> 01:04:51,080 Donc, une bonne façon de s'assurer que ce hachage fonction ne retourne indices valides est 1385 01:04:51,080 --> 01:04:54,580 modulo par la taille de la table. 1386 01:04:54,580 --> 01:04:57,360 Si vous modulo quel que soit ce rendement par trois, vous allez toujours obtenir 1387 01:04:57,360 --> 01:05:00,930 quelque chose entre zéro, un, et deux. 1388 01:05:00,930 --> 01:05:05,160 Et si cela retourne toujours sept, et vous avez toujours modulo par trois, vous êtes 1389 01:05:05,160 --> 01:05:06,030 allant toujours à obtenir la même chose. 1390 01:05:06,030 --> 01:05:09,270 >> Donc, il est toujours déterministe si vous modulo. 1391 01:05:09,270 --> 01:05:11,420 Mais cela ne vous assurer que vous jamais obtenir quelque chose - 1392 01:05:11,420 --> 01:05:12,940 un secteur valide. 1393 01:05:12,940 --> 01:05:16,840 En règle générale, qui doit se faire modulo l'intérieur de votre fonction de hachage. 1394 01:05:16,840 --> 01:05:18,240 Donc, vous n'avez pas besoin de s'inquiéter à ce sujet. 1395 01:05:18,240 --> 01:05:20,555 Vous ne pouvez faire en sorte que il s'agit d'un indice valable. 1396 01:05:20,555 --> 01:05:23,700 1397 01:05:23,700 --> 01:05:26,700 Toutes les questions sur ce écueil? 1398 01:05:26,700 --> 01:05:36,590 1399 01:05:36,590 --> 01:05:39,060 >> OK. 1400 01:05:39,060 --> 01:05:40,290 Et là nous allons. 1401 01:05:40,290 --> 01:05:42,890 Suivant potentiel écueil, et c'est le grand. 1402 01:05:42,890 --> 01:05:46,880 Que faire si deux touches carte à la même valeur? 1403 01:05:46,880 --> 01:05:49,350 Donc, il ya deux façons de gérer cela. 1404 01:05:49,350 --> 01:05:53,140 1405 01:05:53,140 --> 01:05:56,020 Le premier est appelé linéaire sondage, qui je suis 1406 01:05:56,020 --> 01:05:57,300 ne vais pas y aller. 1407 01:05:57,300 --> 01:06:01,120 Mais vous devez être familier avec la façon qui fonctionne et ce que c'est. 1408 01:06:01,120 --> 01:06:05,610 >> La seconde, je vais aller sur parce que c'est celui qui a beaucoup 1409 01:06:05,610 --> 01:06:08,290 les gens vont probablement finir par décider à utiliser dans leur ensemble de problème. 1410 01:06:08,290 --> 01:06:09,820 Bien sûr, vous n'avez pas à. 1411 01:06:09,820 --> 01:06:15,280 Mais, pour l'ensemble des problèmes, beaucoup de gens ont tendance à choisir de créer une table de hachage 1412 01:06:15,280 --> 01:06:17,950 avec chaînage séparé pour mettre en œuvre leur dictionnaire. 1413 01:06:17,950 --> 01:06:21,390 Donc, nous allons revenir sur ce que cela signifie pour créer une table de hachage avec 1414 01:06:21,390 --> 01:06:23,890 chaînage séparé. 1415 01:06:23,890 --> 01:06:26,260 >> Alors, j'ai mis en citrouille. 1416 01:06:26,260 --> 01:06:29,560 Il renvoie zéro. 1417 01:06:29,560 --> 01:06:31,410 Et je mets citrouille ici. 1418 01:06:31,410 --> 01:06:35,880 1419 01:06:35,880 --> 01:06:37,930 Puis-je mettre dans - 1420 01:06:37,930 --> 01:06:39,922 ce qui est une autre chose de Halloween sur le thème? 1421 01:06:39,922 --> 01:06:42,200 >> PUBLIC: Candy. 1422 01:06:42,200 --> 01:06:42,770 >> JASON HIRSCHHORN: Candy! 1423 01:06:42,770 --> 01:06:43,910 C'est un grand. 1424 01:06:43,910 --> 01:06:47,760 Je mets dans les bonbons, et des bonbons me donne aussi zéro. 1425 01:06:47,760 --> 01:06:49,350 Que dois-je faire? 1426 01:06:49,350 --> 01:06:51,940 Des idées? 1427 01:06:51,940 --> 01:06:53,940 Parce que vous savez toutes sortes de ce chaînage séparé est. 1428 01:06:53,940 --> 01:06:55,190 Donc, toutes les idées que faire? 1429 01:06:55,190 --> 01:06:58,170 1430 01:06:58,170 --> 01:06:59,110 Ouais. 1431 01:06:59,110 --> 01:07:03,810 >> PUBLIC: Mettre la chaîne en fait dans la table de hachage. 1432 01:07:03,810 --> 01:07:08,910 >> JASON HIRSCHHORN: Donc, nous allons attirer la bonne idée ici. 1433 01:07:08,910 --> 01:07:09,340 OK. 1434 01:07:09,340 --> 01:07:12,290 >> PUBLIC: Vous avez la table de hachage [Inaudible] 1435 01:07:12,290 --> 01:07:16,640 le pointeur qui pointe vers le début d'une liste. 1436 01:07:16,640 --> 01:07:20,930 Et puis ont citrouille être la première valeur dans cette liste, et les bonbons être 1437 01:07:20,930 --> 01:07:22,800 la deuxième valeur de cette liste chaînée. 1438 01:07:22,800 --> 01:07:23,420 >> JASON HIRSCHHORN: OK. 1439 01:07:23,420 --> 01:07:24,670 Marcus, qui était exceptionnel. 1440 01:07:24,670 --> 01:07:26,160 Je vais faire une ventilation. 1441 01:07:26,160 --> 01:07:28,890 Marcus dit ne le font pas remplacer la citrouille. 1442 01:07:28,890 --> 01:07:30,660 Ce serait mauvais. 1443 01:07:30,660 --> 01:07:33,640 Ne pas mettre des bonbons ailleurs. 1444 01:07:33,640 --> 01:07:35,390 Nous allons les mettre à la fois à zéro. 1445 01:07:35,390 --> 01:07:37,770 Mais nous allons faire face à les mettre à zéro par 1446 01:07:37,770 --> 01:07:39,395 création d'une liste à zéro. 1447 01:07:39,395 --> 01:07:42,430 Et nous allons créer une liste de tout ce qui mappée à zéro. 1448 01:07:42,430 --> 01:07:47,960 Et la meilleure façon que nous avons appris à créer une liste qui peut croître et se rétrécir 1449 01:07:47,960 --> 01:07:49,840 est dynamiquement pas à l'intérieur de un autre tableau. 1450 01:07:49,840 --> 01:07:51,510 Donc, pas un tableau multi-dimensionnel. 1451 01:07:51,510 --> 01:07:54,080 Mais il suffit de créer une liste chaînée. 1452 01:07:54,080 --> 01:07:55,330 >> Donc, ce qu'il a proposé - 1453 01:07:55,330 --> 01:07:57,950 1454 01:07:57,950 --> 01:07:59,200 Je vais me faire un nouveau - 1455 01:07:59,200 --> 01:08:15,380 1456 01:08:15,380 --> 01:08:19,689 est de créer un tableau avec des pointeurs, un tableau de pointeurs. 1457 01:08:19,689 --> 01:08:20,580 OK. 1458 01:08:20,580 --> 01:08:24,180 Toute idée ou soupçon que soit le type de cette pointeurs devrait être? 1459 01:08:24,180 --> 01:08:26,290 Marcus? 1460 01:08:26,290 --> 01:08:27,250 >> PUBLIC: Les pointeurs vers - 1461 01:08:27,250 --> 01:08:28,609 >> JASON HIRSCHHORN: Parce que vous dit une liste chaînée, si - 1462 01:08:28,609 --> 01:08:29,520 >> PUBLIC: pointeurs de noeuds? 1463 01:08:29,520 --> 01:08:30,670 >> JASON HIRSCHHORN: pointeurs de noeuds. 1464 01:08:30,670 --> 01:08:32,830 Si les choses dans notre liée liste sont des nœuds, puis ils 1465 01:08:32,830 --> 01:08:34,370 devraient être des pointeurs de noeuds. 1466 01:08:34,370 --> 01:08:35,939 Et que font-ils égaux d'abord? 1467 01:08:35,939 --> 01:08:36,990 >> PUBLIC: Null. 1468 01:08:36,990 --> 01:08:38,240 >> JASON HIRSCHHORN: Null. 1469 01:08:38,240 --> 01:08:44,540 1470 01:08:44,540 --> 01:08:46,080 Donc, il ya notre truc vide. 1471 01:08:46,080 --> 01:08:47,170 rendements de citrouille zéro. 1472 01:08:47,170 --> 01:08:48,569 Que faisons-nous? 1473 01:08:48,569 --> 01:08:49,609 Me promener à travers elle? 1474 01:08:49,609 --> 01:08:50,810 En fait, Marcus m'a déjà donné. 1475 01:08:50,810 --> 01:08:52,439 Quelqu'un d'autre me promener à travers elle. 1476 01:08:52,439 --> 01:08:54,760 Ce que nous faisons lorsque nous - 1477 01:08:54,760 --> 01:08:56,609 cela semble très similaire à ce que nous ne faisions. 1478 01:08:56,609 --> 01:08:57,396 Avi. 1479 01:08:57,396 --> 01:08:59,090 >> PUBLIC: Je vais faire une supposition. 1480 01:08:59,090 --> 01:09:01,250 Ainsi, lorsque vous obtenez des bonbons. 1481 01:09:01,250 --> 01:09:01,640 >> JASON HIRSCHHORN: Ouais. 1482 01:09:01,640 --> 01:09:03,120 Eh bien, nous avons eu la citrouille. 1483 01:09:03,120 --> 01:09:03,870 Soyons de notre premier. 1484 01:09:03,870 --> 01:09:04,324 Nous avons eu la citrouille. 1485 01:09:04,324 --> 01:09:04,779 >> PUBLIC: OK. 1486 01:09:04,779 --> 01:09:05,880 rendements de citrouille zéro. 1487 01:09:05,880 --> 01:09:08,770 Donc, vous le mettez dans cela. 1488 01:09:08,770 --> 01:09:10,810 Ou fait, vous le mettez dans la liste chaînée. 1489 01:09:10,810 --> 01:09:13,550 >> JASON HIRSCHHORN: Comment pouvons-nous mettre dans la liste chaînée? 1490 01:09:13,550 --> 01:09:15,479 >> PUBLIC: Oh, la syntaxe réelle? 1491 01:09:15,479 --> 01:09:16,240 >> JASON HIRSCHHORN: Il suffit de marcher - 1492 01:09:16,240 --> 01:09:16,740 dire plus. 1493 01:09:16,740 --> 01:09:19,310 Que faisons-nous? 1494 01:09:19,310 --> 01:09:22,100 >> PUBLIC: Il suffit d'insérer comme le premier noeud. 1495 01:09:22,100 --> 01:09:22,675 >> JASON HIRSCHHORN: OK. 1496 01:09:22,675 --> 01:09:29,069 Donc, nous avons notre noeud, potiron. 1497 01:09:29,069 --> 01:09:31,560 Et maintenant, comment puis-je l'insérer? 1498 01:09:31,560 --> 01:09:34,590 1499 01:09:34,590 --> 01:09:37,090 >> PUBLIC: Vous affectez au pointeur. 1500 01:09:37,090 --> 01:09:37,970 >> JASON HIRSCHHORN: Quels pointeur? 1501 01:09:37,970 --> 01:09:39,620 >> AUDIENCE: Le pointeur à zéro. 1502 01:09:39,620 --> 01:09:41,420 >> JASON HIRSCHHORN: Alors, où fait ce point? 1503 01:09:41,420 --> 01:09:42,810 >> PUBLIC: Pour null dès maintenant. 1504 01:09:42,810 --> 01:09:43,529 >> JASON HIRSCHHORN: Eh bien, il pointe vers null. 1505 01:09:43,529 --> 01:09:44,499 Mais je suis en train de la citrouille. 1506 01:09:44,499 --> 01:09:46,053 Alors, où faut-il signaler? 1507 01:09:46,053 --> 01:09:46,880 >> PUBLIC: Pour potiron. 1508 01:09:46,880 --> 01:09:47,399 >> JASON HIRSCHHORN: Pour potiron. 1509 01:09:47,399 --> 01:09:48,760 Exactement. 1510 01:09:48,760 --> 01:09:50,010 Donc, cela souligne la citrouille. 1511 01:09:50,010 --> 01:09:52,500 1512 01:09:52,500 --> 01:09:54,250 Et d'où vient ce pointeur au point de citrouille? 1513 01:09:54,250 --> 01:09:57,986 1514 01:09:57,986 --> 01:09:58,340 À 1515 01:09:58,340 --> 01:09:58,590 >> PUBLIC: Null. 1516 01:09:58,590 --> 01:09:59,210 >> JASON HIRSCHHORN: Pour null. 1517 01:09:59,210 --> 01:10:00,460 Exactement. 1518 01:10:00,460 --> 01:10:03,570 1519 01:10:03,570 --> 01:10:05,140 Donc, nous venons d'insérer quelque chose dans la liste chaînée. 1520 01:10:05,140 --> 01:10:07,210 Nous venons d'écrire le code pour ce faire. 1521 01:10:07,210 --> 01:10:09,520 Près de nous, il a presque réussi complètement craqué. 1522 01:10:09,520 --> 01:10:10,790 Maintenant, nous insérons des bonbons. 1523 01:10:10,790 --> 01:10:13,480 Notre bonbons va également à zéro. 1524 01:10:13,480 --> 01:10:16,100 Alors, que faisons-nous avec des bonbons? 1525 01:10:16,100 --> 01:10:18,790 >> PUBLIC: Cela dépend de si oui ou pas que nous essayons de faire le tri. 1526 01:10:18,790 --> 01:10:19,640 >> JASON HIRSCHHORN: C'est tout à fait exact. 1527 01:10:19,640 --> 01:10:21,070 Cela dépend de si oui ou non nous essayons de faire le tri. 1528 01:10:21,070 --> 01:10:22,660 Supposons que nous ne sommes pas va faire le tri. 1529 01:10:22,660 --> 01:10:24,880 >> PUBLIC: Eh bien, comme nous l'avons avant, le plus simple est juste de le mettre 1530 01:10:24,880 --> 01:10:28,590 dès le début de sorte que le pointeur de points zéro à bonbons. 1531 01:10:28,590 --> 01:10:29,020 >> JASON HIRSCHHORN: OK. 1532 01:10:29,020 --> 01:10:29,380 Attendez. 1533 01:10:29,380 --> 01:10:30,630 Permettez-moi de créer des bonbons ici. 1534 01:10:30,630 --> 01:10:34,030 1535 01:10:34,030 --> 01:10:35,150 Donc, ce pointeur - 1536 01:10:35,150 --> 01:10:37,590 >> PUBLIC: Ouais, doit maintenant pointer à bonbons. 1537 01:10:37,590 --> 01:10:40,580 Avoir le pointeur de Point de potiron de sucrerie. 1538 01:10:40,580 --> 01:10:43,140 1539 01:10:43,140 --> 01:10:44,560 >> JASON HIRSCHHORN: Comme ça? 1540 01:10:44,560 --> 01:10:47,380 Et dire que nous avons un autre chose à la carte à zéro? 1541 01:10:47,380 --> 01:10:48,660 >> PUBLIC: Eh bien, vous venez de faire la même chose? 1542 01:10:48,660 --> 01:10:50,290 >> JASON HIRSCHHORN: Faites la même chose. 1543 01:10:50,290 --> 01:10:53,700 Donc dans ce cas, si nous ne faisons pas vouloir garder triée il 1544 01:10:53,700 --> 01:10:55,270 sons assez simple. 1545 01:10:55,270 --> 01:10:59,920 Nous prenons le pointeur dans la indice donné par notre fonction de hachage. 1546 01:10:59,920 --> 01:11:03,830 Nous avons ce point à notre nouveau nœud. 1547 01:11:03,830 --> 01:11:07,830 Et puis tout ce qu'il pointait précédemment - 1548 01:11:07,830 --> 01:11:10,620 dans ce cas, nul, dans le second cas citrouille - 1549 01:11:10,620 --> 01:11:15,310 que, quel que soit son pointant vers précédemment, nous ajoutons dans le prochain de 1550 01:11:15,310 --> 01:11:17,810 notre nouveau noeud. 1551 01:11:17,810 --> 01:11:19,650 Nous insertion quelque chose au début. 1552 01:11:19,650 --> 01:11:22,900 En fait, c'est beaucoup plus simple que en essayant de garder la liste triée. 1553 01:11:22,900 --> 01:11:25,340 Mais encore une fois, la recherche sera plus compliqué ici. 1554 01:11:25,340 --> 01:11:28,300 Nous aurons toujours à aller jusqu'au bout. 1555 01:11:28,300 --> 01:11:29,650 >> OK. 1556 01:11:29,650 --> 01:11:32,750 Une question sur le chaînage séparé? 1557 01:11:32,750 --> 01:11:34,690 Comment cela fonctionne? 1558 01:11:34,690 --> 01:11:35,820 S'il vous plaît demandez-leur maintenant. 1559 01:11:35,820 --> 01:11:39,260 Je veux vraiment vous assurer que vous tous comprendre cela avant, nous nous dirigeons. 1560 01:11:39,260 --> 01:11:48,410 1561 01:11:48,410 --> 01:11:52,060 >> PUBLIC: Pourquoi mettez-vous la citrouille et des bonbons dans la même 1562 01:11:52,060 --> 01:11:54,108 partie de la table de hachage? 1563 01:11:54,108 --> 01:11:55,860 >> JASON HIRSCHHORN: Bonne question. 1564 01:11:55,860 --> 01:11:59,140 Pourquoi avons-nous les mettons dans le même partie de la table de hachage? 1565 01:11:59,140 --> 01:12:03,200 Eh bien, dans ce cas, notre fonction de hachage retourne zéro pour chacun d'eux. 1566 01:12:03,200 --> 01:12:05,310 Donc, ils ont besoin d'aller à indice zéro parce que c'est là que nous allons 1567 01:12:05,310 --> 01:12:07,420 les chercher si jamais nous vouloir les regarder. 1568 01:12:07,420 --> 01:12:11,750 Encore une fois, avec une approche linéaire sondage nous ne serions pas les mettre tous deux à zéro. 1569 01:12:11,750 --> 01:12:13,900 Mais dans l'approche de la chaîne séparée, nous allons les mettre à la fois à zéro 1570 01:12:13,900 --> 01:12:16,620 et puis créer une liste de zéro. 1571 01:12:16,620 --> 01:12:20,140 >> Et nous ne voulons pas remplacer la citrouille simplement parce que alors nous allons 1572 01:12:20,140 --> 01:12:21,860 supposons que la citrouille était jamais inséré. 1573 01:12:21,860 --> 01:12:25,230 Si nous gardons juste une chose dans le emplacement qui serait mauvais. 1574 01:12:25,230 --> 01:12:28,590 Ensuite, il n'y aurait pas chance de nous jamais - 1575 01:12:28,590 --> 01:12:31,660 si jamais nous avions un double, puis nous serait tout simplement effacer notre valeur initiale. 1576 01:12:31,660 --> 01:12:34,090 Voilà pourquoi nous faisons cette démarche. 1577 01:12:34,090 --> 01:12:36,580 Ou c'est pourquoi nous avons choisi - mais encore une fois, nous a choisi l'approche de chaînage séparé, 1578 01:12:36,580 --> 01:12:39,670 dont il existe de nombreuses autres approches on pourrait choisir. 1579 01:12:39,670 --> 01:12:41,185 Est-ce que cela répond à votre question? 1580 01:12:41,185 --> 01:12:41,660 >> OK. 1581 01:12:41,660 --> 01:12:42,910 Carlos. 1582 01:12:42,910 --> 01:12:46,130 1583 01:12:46,130 --> 01:12:47,720 Linéaire sondage impliquerait - 1584 01:12:47,720 --> 01:12:51,913 si nous avons trouvé une collision à zéro, nous regarderait en place prochaine pour voir si 1585 01:12:51,913 --> 01:12:54,310 elle était ouverte et l'a mis là. 1586 01:12:54,310 --> 01:12:57,320 Et puis nous sommes dans le prochain sport et voir si c'était ouvert et le mettre là. 1587 01:12:57,320 --> 01:12:59,780 Donc, nous trouvons la prochaine disponible endroit ouvert et le mettre là. 1588 01:12:59,780 --> 01:13:02,580 1589 01:13:02,580 --> 01:13:03,890 D'autres questions? 1590 01:13:03,890 --> 01:13:05,370 Ouais, Avi. 1591 01:13:05,370 --> 01:13:07,490 >> PUBLIC: Comme un suivi à cela, Qu'entendez-vous par spot suivant? 1592 01:13:07,490 --> 01:13:10,250 Dans la table de hachage ou dans une liste chaînée. 1593 01:13:10,250 --> 01:13:12,100 >> JASON HIRSCHHORN: Pour linéaire programmation, pas de listes chaînées. 1594 01:13:12,100 --> 01:13:13,400 Le prochain point sur la table de hachage. 1595 01:13:13,400 --> 01:13:13,820 >> PUBLIC: OK. 1596 01:13:13,820 --> 01:13:17,570 Ainsi, la table de hachage serait initialisé à la taille - 1597 01:13:17,570 --> 01:13:19,560 comme le nombre de chaînes que vous insérez? 1598 01:13:19,560 --> 01:13:22,170 >> JASON HIRSCHHORN: Vous feriez voulez qu'il soit vraiment grand. 1599 01:13:22,170 --> 01:13:23,910 Oui. 1600 01:13:23,910 --> 01:13:27,900 Voici une photo de ce que nous juste a attiré sur la carte. 1601 01:13:27,900 --> 01:13:29,470 Encore une fois, nous avons une collision ici. 1602 01:13:29,470 --> 01:13:30,710 à 152. 1603 01:13:30,710 --> 01:13:33,570 Et vous verrez que nous avons créé une liste chaînée hors de lui. 1604 01:13:33,570 --> 01:13:38,200 1605 01:13:38,200 --> 01:13:41,850 Encore une fois, la table de hachage chaînage séparé approche n'est pas celle que vous 1606 01:13:41,850 --> 01:13:45,590 prendre les problèmes mis en six, mais est un que beaucoup de 1607 01:13:45,590 --> 01:13:47,100 les étudiants ont tendance à prendre. 1608 01:13:47,100 --> 01:13:51,140 Donc, sur cette note, parlons brièvement avant, nous nous dirigeons sur six problème, 1609 01:13:51,140 --> 01:13:52,160 et puis je vais partager une histoire avec vous. 1610 01:13:52,160 --> 01:13:55,120 Nous avons trois minutes. 1611 01:13:55,120 --> 01:13:55,750 >> Problème réglé six. 1612 01:13:55,750 --> 01:13:57,790 Vous disposez de quatre fonctions - 1613 01:13:57,790 --> 01:14:02,430 charge, vérifier la taille et le déchargement. 1614 01:14:02,430 --> 01:14:03,380 Charge - 1615 01:14:03,380 --> 01:14:07,120 bien, nous y allons plus de charge en ce moment. 1616 01:14:07,120 --> 01:14:09,330 Nous avons tiré la charge sur le plateau. 1617 01:14:09,330 --> 01:14:13,230 Et nous avons même commencé à coder un grand nombre de insérer dans une liste chaînée. 1618 01:14:13,230 --> 01:14:18,020 Donc, la charge n'est pas beaucoup plus que ce que nous venons de faire. 1619 01:14:18,020 --> 01:14:21,070 >> Arrivée est une fois que vous avez quelque chose chargé. 1620 01:14:21,070 --> 01:14:22,580 C'est le même processus que cela. 1621 01:14:22,580 --> 01:14:26,845 Les mêmes deux premières parties où vous jetez quelque chose dans la fonction de hachage 1622 01:14:26,845 --> 01:14:29,190 et obtenir sa valeur. 1623 01:14:29,190 --> 01:14:30,700 Mais maintenant, nous ne sommes pas l'insérer. 1624 01:14:30,700 --> 01:14:33,350 Maintenant, nous sommes à la recherche d'elle. 1625 01:14:33,350 --> 01:14:37,130 J'ai des exemples de code écrit pour trouver quelque chose dans une liste chaînée. 1626 01:14:37,130 --> 01:14:38,250 Je vous encourage à pratiquer cela. 1627 01:14:38,250 --> 01:14:43,000 Mais trouver intuitivement que quelque chose assez similaire à l'insertion de quelque chose. 1628 01:14:43,000 --> 01:14:46,540 En effet, nous avons établi une image de la recherche quelque chose dans une liste chaînée, déplacer 1629 01:14:46,540 --> 01:14:48,910 par jusqu'à ce que vous avez à la fin. 1630 01:14:48,910 --> 01:14:52,430 Et si vous avez obtenu à la fin et ne pouvait pas trouver, alors il n'est pas là. 1631 01:14:52,430 --> 01:14:55,400 C'est donc chèque, essentiellement. 1632 01:14:55,400 --> 01:14:57,030 >> Suivant est la taille. 1633 01:14:57,030 --> 01:14:57,910 Passons taille. 1634 01:14:57,910 --> 01:15:00,040 Enfin, vous avez décharger. 1635 01:15:00,040 --> 01:15:02,890 Décharger est celui que nous n'avons pas tiré sur la carte ou encore codé. 1636 01:15:02,890 --> 01:15:05,990 Mais je vous encourage à essayer coder dans notre échantillon exemple de liste chaînée. 1637 01:15:05,990 --> 01:15:11,440 Mais décharger intuitivement est similaire à la libre - 1638 01:15:11,440 --> 01:15:14,010 ou je veux dire, c'est même à vérifier. 1639 01:15:14,010 --> 01:15:17,350 Sauf pour l'instant à chaque fois que vous allez à travers, vous n'êtes pas simplement de vérifier à 1640 01:15:17,350 --> 01:15:19,090 voir si vous avez votre valeur il. 1641 01:15:19,090 --> 01:15:22,490 Mais vous prenez ce nœud et le libérant, essentiellement. 1642 01:15:22,490 --> 01:15:23,610 C'est ce déchargement vous demande de faire. 1643 01:15:23,610 --> 01:15:24,670 Tout gratuit vous avez malloced. 1644 01:15:24,670 --> 01:15:27,480 Donc, vous allez toute la liste nouveau, en passant par l'ensemble hachage 1645 01:15:27,480 --> 01:15:27,760 table. 1646 01:15:27,760 --> 01:15:29,240 Cette fois-ci ne vérifie pas pour voir ce qui est là. 1647 01:15:29,240 --> 01:15:31,080 Juste libérer ce qui est là. 1648 01:15:31,080 --> 01:15:33,260 >> Et enfin la taille. 1649 01:15:33,260 --> 01:15:34,350 Taille devrait être mis en œuvre. 1650 01:15:34,350 --> 01:15:35,590 Si vous ne mettez pas en œuvre la taille - 1651 01:15:35,590 --> 01:15:36,250 Je vais dire comme ça. 1652 01:15:36,250 --> 01:15:39,740 Si vous ne mettez pas en œuvre la taille exactement une ligne de code, y compris la 1653 01:15:39,740 --> 01:15:43,760 déclaration de retour, vous êtes faire la taille correctement. 1654 01:15:43,760 --> 01:15:47,170 Donc, assurez-vous que le format, pour la conception complète points, vous le faites dans exactement un 1655 01:15:47,170 --> 01:15:49,970 ligne de code, y compris l'instruction de retour. 1656 01:15:49,970 --> 01:15:52,450 >> Et ne pas emballer encore, Akchar. 1657 01:15:52,450 --> 01:15:53,700 Eager Beaver. 1658 01:15:53,700 --> 01:15:55,820 1659 01:15:55,820 --> 01:16:01,300 Je voulais vous dire merci les gars pour venir à l'article. 1660 01:16:01,300 --> 01:16:02,550 Ayez un Halloween heureux. 1661 01:16:02,550 --> 01:16:05,300 1662 01:16:05,300 --> 01:16:05,960 C'est mon costume. 1663 01:16:05,960 --> 01:16:08,850 Je vais porter ce jeudi si je vous vois à des heures de bureau. 1664 01:16:08,850 --> 01:16:14,640 Et si vous êtes curieux de savoir un peu plus fond à ce costume, se sentir 1665 01:16:14,640 --> 01:16:19,135 n'hésitez pas à consulter la section 2011 pour un article sur pourquoi je suis 1666 01:16:19,135 --> 01:16:20,900 portant le costume de citrouille. 1667 01:16:20,900 --> 01:16:23,680 Et c'est une histoire triste. 1668 01:16:23,680 --> 01:16:27,050 Donc, assurez-vous que vous avez certains tissus voisins. 1669 01:16:27,050 --> 01:16:28,680 Mais sur ce point, si vous avez une questions que je vais rester 1670 01:16:28,680 --> 01:16:29,960 l'extérieur, après l'article. 1671 01:16:29,960 --> 01:16:31,510 Bonne chance problème réglé six. 1672 01:16:31,510 --> 01:16:33,540 Et comme toujours, si vous avez une questions, laissez-moi savoir. 1673 01:16:33,540 --> 01:16:35,584