1 00:00:00,000 --> 00:00:08,250 2 00:00:08,250 --> 00:00:12,680 >> JASON HIRSCHHORN: Bienvenidos a todos a la Sección Siete. 3 00:00:12,680 --> 00:00:15,040 Estamos en la séptima semana del curso. 4 00:00:15,040 --> 00:00:18,440 Y este próximo Jueves es Halloween, así que estoy 5 00:00:18,440 --> 00:00:21,420 vestido como una calabaza. 6 00:00:21,420 --> 00:00:23,460 Yo no podía agacharse y poner en mis zapatos, así que es por eso que estoy 7 00:00:23,460 --> 00:00:25,660 sólo el uso de calcetines. 8 00:00:25,660 --> 00:00:29,220 Asimismo, no llevo nada debajo esto, así que no puedo quitarlo si es 9 00:00:29,220 --> 00:00:29,950 distraer a usted. 10 00:00:29,950 --> 00:00:31,860 Me disculpo de antemano por ello. 11 00:00:31,860 --> 00:00:33,170 No es necesario imaginar ¿qué está pasando. 12 00:00:33,170 --> 00:00:34,240 Yo llevo calzoncillos. 13 00:00:34,240 --> 00:00:36,170 Así que está todo bien. 14 00:00:36,170 --> 00:00:41,120 >> Tengo una historia más larga de por qué estoy vestido como una calabaza, pero yo voy a 15 00:00:41,120 --> 00:00:45,110 guardar para más adelante en esta sección porque yo quiero empezar. 16 00:00:45,110 --> 00:00:47,720 Tenemos un montón de cosas interesantes para repasar esta semana. 17 00:00:47,720 --> 00:00:51,810 La mayoría de ellos se refieren directamente a este conjunto de problemas de la semana, las faltas de ortografía. 18 00:00:51,810 --> 00:00:54,680 Vamos a ir sobre ligado listas y tablas hash 19 00:00:54,680 --> 00:00:57,160 para toda la sección. 20 00:00:57,160 --> 00:01:02,490 Pongo esta lista cada semana, una lista de recursos para usted para ayudarle con 21 00:01:02,490 --> 00:01:04,120 el material de este curso. 22 00:01:04,120 --> 00:01:07,600 Si en una pérdida o si busca alguna obtener más información, echa un vistazo a uno de 23 00:01:07,600 --> 00:01:09,930 estos recursos. 24 00:01:09,930 --> 00:01:14,530 >> Una vez más, es pset6 faltas de ortografía, conjunto de procesadores de esta semana. 25 00:01:14,530 --> 00:01:17,690 Y también te anima, y ​​yo animaros, utilizar algún otro 26 00:01:17,690 --> 00:01:20,320 recursos específicamente para este conjunto de procesadores. 27 00:01:20,320 --> 00:01:23,390 En particular, los tres que he enumerado en la pantalla - 28 00:01:23,390 --> 00:01:27,160 gdb, que hemos estado familiarizados con y estado utilizando desde hace un tiempo, es 29 00:01:27,160 --> 00:01:29,270 va a ser de mucha ayuda esta semana. 30 00:01:29,270 --> 00:01:30,190 Así que puse que hasta aquí. 31 00:01:30,190 --> 00:01:32,910 Pero cada vez que se trabaja con C, siempre se debe utilizar gdb para 32 00:01:32,910 --> 00:01:34,430 depurar los programas. 33 00:01:34,430 --> 00:01:36,660 Esta semana también valgrind. 34 00:01:36,660 --> 00:01:38,535 ¿Alguien sabe lo que valgrind hace? 35 00:01:38,535 --> 00:01:42,184 36 00:01:42,184 --> 00:01:43,890 >> AUDIENCIA: Comprueba si hay fugas de memoria? 37 00:01:43,890 --> 00:01:45,950 >> JASON HIRSCHHORN: Valgrind cheques para las pérdidas de memoria. 38 00:01:45,950 --> 00:01:49,970 Así que si algo malloc en su programa, estás pidiendo memoria. 39 00:01:49,970 --> 00:01:52,920 Al final de su programa, usted tiene para escribir libre de todo lo que has 40 00:01:52,920 --> 00:01:54,800 malloced para dar la memoria. 41 00:01:54,800 --> 00:01:58,420 Si no escribes libre al final y su programa llega a una conclusión, 42 00:01:58,420 --> 00:02:00,000 todo automáticamente ser liberado. 43 00:02:00,000 --> 00:02:02,340 Y para los pequeños programas, que es No es gran cosa. 44 00:02:02,340 --> 00:02:05,250 Pero si usted está escribiendo un rodaje más largo programa que no se cierra, 45 00:02:05,250 --> 00:02:09,180 necesariamente, en un par de minutos o un par de segundos, a continuación, pérdidas de memoria 46 00:02:09,180 --> 00:02:10,710 puede convertirse en un gran negocio. 47 00:02:10,710 --> 00:02:14,940 >> Así que para pset6, la expectativa es que usted tendrá pérdidas de memoria cero con 48 00:02:14,940 --> 00:02:15,910 su programa. 49 00:02:15,910 --> 00:02:18,690 Para comprobar si hay fugas de memoria, valgrind ejecutar y te voy a dar algunas buenas 50 00:02:18,690 --> 00:02:21,190 salida que le permite saber si o no todo era gratis. 51 00:02:21,190 --> 00:02:23,940 Practicaremos con él más adelante hoy, con suerte. 52 00:02:23,940 --> 00:02:25,790 >> Por último, el comando diff. 53 00:02:25,790 --> 00:02:28,900 Ha utilizado algo similar a ella en pset5 con la herramienta vistazo. 54 00:02:28,900 --> 00:02:30,780 Le ha permitido observar el interior. 55 00:02:30,780 --> 00:02:33,400 También usaste diff, también, por el problema establece especificaciones. 56 00:02:33,400 --> 00:02:35,950 Pero en que permite comparar dos archivos. 57 00:02:35,950 --> 00:02:39,180 Se podría comparar el archivo de mapa de bits y info encabezados de una solución personal y 58 00:02:39,180 --> 00:02:42,200 su solución en pset5 si opta por utilizarlo. 59 00:02:42,200 --> 00:02:44,030 Dif. le permitirá hacer eso, también. 60 00:02:44,030 --> 00:02:48,620 Puede comparar la respuesta correcta para El problema de esta semana establece en su respuesta 61 00:02:48,620 --> 00:02:52,210 y ver si se alinee o ver dónde están los errores. 62 00:02:52,210 --> 00:02:55,870 >> Así que estos son tres buenas herramientas que usted debe utilizar para esta semana, y 63 00:02:55,870 --> 00:02:58,130 Definitivamente revisar su programa de con estas tres herramientas 64 00:02:58,130 --> 00:03:00,520 antes de dar vuelta pulg 65 00:03:00,520 --> 00:03:04,650 Una vez más, como ya he mencionado todas las semanas, si tiene alguna reacción para mí - tanto 66 00:03:04,650 --> 00:03:06,470 positiva y constructiva - 67 00:03:06,470 --> 00:03:09,930 no dude en dirigirse a la página web en la parte inferior de esta diapositiva 68 00:03:09,930 --> 00:03:11,270 y la entrada allí. 69 00:03:11,270 --> 00:03:13,440 Realmente aprecio cualquier y todos los comentarios. 70 00:03:13,440 --> 00:03:17,360 Y si me das las cosas específicas que Que puedo hacer para mejorar o que soy 71 00:03:17,360 --> 00:03:21,350 haciendo así que me gustaría Continúo, me tomo muy a pecho y 72 00:03:21,350 --> 00:03:24,040 realmente se esfuerzan para escuchar para su regeneración. 73 00:03:24,040 --> 00:03:27,720 No puedo prometer que voy a hacer todo, sin embargo, como llevar una 74 00:03:27,720 --> 00:03:30,700 calabaza disfraz cada semana. 75 00:03:30,700 --> 00:03:34,020 >> Así que vamos a pasar la mayor parte de sección, como ya he dicho, hablando de 76 00:03:34,020 --> 00:03:37,240 listas enlazadas y tablas hash, que será directamente aplicable a la 77 00:03:37,240 --> 00:03:38,780 problema establecido esta semana. 78 00:03:38,780 --> 00:03:42,580 Las listas enlazadas vamos a repasar relativamente rápidamente, porque hemos pasado un poco justo 79 00:03:42,580 --> 00:03:44,930 de tiempo de ir sobre ella en la sección. 80 00:03:44,930 --> 00:03:48,680 Y así vamos a llegar directamente a la problemas de codificación para listas enlazadas. 81 00:03:48,680 --> 00:03:52,740 Y luego, al final vamos a hablar de tablas hash y cómo se aplican a este 82 00:03:52,740 --> 00:03:55,280 Problema de la semana. 83 00:03:55,280 --> 00:03:57,560 >> Usted ha visto este código antes. 84 00:03:57,560 --> 00:04:02,730 Esta es una estructura, y que está definiendo algo nuevo llamado nodo. 85 00:04:02,730 --> 00:04:10,660 Y dentro de un nodo no es un entero aquí y allá es un puntero a 86 00:04:10,660 --> 00:04:11,830 otro nodo. 87 00:04:11,830 --> 00:04:12,790 Hemos visto esto antes. 88 00:04:12,790 --> 00:04:14,830 Esto ha estado subiendo de un par de semanas ahora. 89 00:04:14,830 --> 00:04:18,680 Combina los punteros, que hemos estado trabajar con, y estructuras, que permiten 90 00:04:18,680 --> 00:04:22,079 nos permite combinar dos diferentes cosas en un solo tipo de datos. 91 00:04:22,079 --> 00:04:24,830 92 00:04:24,830 --> 00:04:26,490 >> Hay mucho que hacer en la pantalla. 93 00:04:26,490 --> 00:04:30,220 Pero todo esto debe ser relativamente familiarizado con usted. 94 00:04:30,220 --> 00:04:33,810 En la primera línea, que declarar un nuevo nodo. 95 00:04:33,810 --> 00:04:41,650 Y luego, dentro de ese nuevo nodo, me puse el número entero en ese nodo a uno. 96 00:04:41,650 --> 00:04:44,950 Vemos en la siguiente línea que estoy haciendo un printf comando, pero he atenuados 97 00:04:44,950 --> 00:04:48,080 el comando printf porque la verdad parte importante es esta línea aquí - 98 00:04:48,080 --> 00:04:50,020 new_node.n. 99 00:04:50,020 --> 00:04:51,270 ¿Qué significa el punto? 100 00:04:51,270 --> 00:04:53,810 101 00:04:53,810 --> 00:04:57,240 >> AUDIENCIA: Vaya al nodo y evaluar el valor de n para ello. 102 00:04:57,240 --> 00:04:58,370 >> JASON HIRSCHHORN: Eso es exactamente correcto. 103 00:04:58,370 --> 00:05:03,300 Dot significa acceder a la parte n de este nuevo nodo. 104 00:05:03,300 --> 00:05:05,690 Esta línea siguiente hace qué? 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 >> AUDIENCIA: Se crea otro nodo que se apunte al nuevo nodo. 108 00:05:21,910 --> 00:05:24,870 >> JASON HIRSCHHORN: Así que no hace crear un nuevo nodo. 109 00:05:24,870 --> 00:05:26,120 Se crea un qué? 110 00:05:26,120 --> 00:05:28,300 111 00:05:28,300 --> 00:05:29,300 >> AUDIENCIA: Un puntero. 112 00:05:29,300 --> 00:05:33,460 >> JASON HIRSCHHORN: Un puntero a un nodo, según lo indicado por este nodo * aquí. 113 00:05:33,460 --> 00:05:34,800 Por lo tanto, crea un puntero a un nodo. 114 00:05:34,800 --> 00:05:37,490 Y qué nodo se lo apunta a, Michael? 115 00:05:37,490 --> 00:05:38,440 >> AUDIENCIA: Nuevo nodo? 116 00:05:38,440 --> 00:05:39,240 >> JASON HIRSCHHORN: Nuevo nodo. 117 00:05:39,240 --> 00:05:43,020 Y está apuntando allí porque hemos dado que la dirección del nuevo nodo. 118 00:05:43,020 --> 00:05:45,820 Y ahora en esta línea vemos dos maneras diferentes de 119 00:05:45,820 --> 00:05:46,910 expresar la misma cosa. 120 00:05:46,910 --> 00:05:49,650 Y yo quería señalar cómo estos dos cosas son lo mismo. 121 00:05:49,650 --> 00:05:54,740 En la primera línea, que eliminar la referencia el puntero. 122 00:05:54,740 --> 00:05:55,830 Así que vamos al nodo. 123 00:05:55,830 --> 00:05:56,830 Eso es lo que significa esta estrella. 124 00:05:56,830 --> 00:05:57,930 Hemos visto que antes con los punteros. 125 00:05:57,930 --> 00:05:59,280 Ir a ese nodo. 126 00:05:59,280 --> 00:06:00,370 Eso está en paréntesis. 127 00:06:00,370 --> 00:06:04,610 Y a continuación, acceder a través del operador de punto el elemento n de ese nodo. 128 00:06:04,610 --> 00:06:08,430 >> Así que eso tomar la sintaxis vimos aquí y ahora 129 00:06:08,430 --> 00:06:09,670 usarla con un puntero. 130 00:06:09,670 --> 00:06:13,730 Por supuesto, se pone un poco ocupado si usted está escribiendo esos paréntesis - 131 00:06:13,730 --> 00:06:14,940 esa estrella y ese punto. 132 00:06:14,940 --> 00:06:16,220 Se pone un poco ocupado. 133 00:06:16,220 --> 00:06:18,500 Así que tenemos un poco de azúcar sintáctica. 134 00:06:18,500 --> 00:06:19,920 Y esta línea aquí - 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 Que hace exactamente lo mismo. 138 00:06:28,000 --> 00:06:30,840 Así que esas dos líneas de código son equivalente y lo hará 139 00:06:30,840 --> 00:06:31,650 exactamente lo mismo. 140 00:06:31,650 --> 00:06:34,210 >> Pero yo quería señalar los antes de ir más lejos para que usted entienda 141 00:06:34,210 --> 00:06:39,000 que realmente esta cosa aquí es sólo el azúcar sintáctica para eliminación de referencias 142 00:06:39,000 --> 00:06:44,200 el puntero y luego ir a la parte n de esa estructura. 143 00:06:44,200 --> 00:06:45,525 ¿Una pregunta sobre esta diapositiva? 144 00:06:45,525 --> 00:06:53,020 145 00:06:53,020 --> 00:06:54,390 Aceptar. 146 00:06:54,390 --> 00:06:58,510 >> Así que vamos a ir a través de un par de las operaciones que se pueden hacer en 147 00:06:58,510 --> 00:06:59,730 listas enlazadas. 148 00:06:59,730 --> 00:07:05,770 Una lista enlazada, el recuerdo, es una serie de nodos que apuntan el uno al otro. 149 00:07:05,770 --> 00:07:12,470 Y por lo general, comenzamos con un puntero llamado la cabeza, por lo general, que apunta a 150 00:07:12,470 --> 00:07:14,040 lo primero en la lista. 151 00:07:14,040 --> 00:07:18,900 Así que en la primera línea aquí, tener primero el original L. 152 00:07:18,900 --> 00:07:21,370 Así que esa cosa que se pueda imaginar - esto texto aquí se puede pensar en como 153 00:07:21,370 --> 00:07:23,560 sólo el puntero hemos almacenado en alguna parte que los puntos 154 00:07:23,560 --> 00:07:24,670 para el primer elemento. 155 00:07:24,670 --> 00:07:27,500 Y en esta lista enlazada tenemos cuatro nodos. 156 00:07:27,500 --> 00:07:29,530 Cada nodo es una caja grande. 157 00:07:29,530 --> 00:07:33,430 La caja más grande dentro de la gran caja es la parte entera. 158 00:07:33,430 --> 00:07:37,400 Y luego tenemos una parte puntero. 159 00:07:37,400 --> 00:07:39,630 >> Estas cajas no están dibujados a escala debido a lo grande que es 160 00:07:39,630 --> 00:07:42,320 un entero en bytes? 161 00:07:42,320 --> 00:07:43,290 ¿Qué tan grande ahora? 162 00:07:43,290 --> 00:07:43,710 Cuatro. 163 00:07:43,710 --> 00:07:45,470 Y qué tan grande es un puntero? 164 00:07:45,470 --> 00:07:45,940 Cuatro. 165 00:07:45,940 --> 00:07:48,180 Así que en realidad, si tuviéramos que dibujar esto es a escala ambas cajas 166 00:07:48,180 --> 00:07:49,690 sería el mismo tamaño. 167 00:07:49,690 --> 00:07:52,870 En este caso, queremos insertar algo a la lista enlazada. 168 00:07:52,870 --> 00:07:57,190 Así que usted puede ver aquí abajo estamos insertando cinco Atravesamos a través de la 169 00:07:57,190 --> 00:08:01,310 lista enlazada, donde encontrará cinco va, y luego insertarlo. 170 00:08:01,310 --> 00:08:03,560 >> Vamos a romper eso y van un poco más lentamente. 171 00:08:03,560 --> 00:08:05,510 Voy a señalar a la junta. 172 00:08:05,510 --> 00:08:09,930 Así que tenemos nuestro nodo cinco que hemos creado en mallocs. 173 00:08:09,930 --> 00:08:11,190 ¿Por qué se está riendo de todo el mundo? 174 00:08:11,190 --> 00:08:12,130 Es broma. 175 00:08:12,130 --> 00:08:13,310 Aceptar. 176 00:08:13,310 --> 00:08:14,820 Así que hemos malloced cinco. 177 00:08:14,820 --> 00:08:16,310 Hemos creado este nodo en otro lugar. 178 00:08:16,310 --> 00:08:17,740 Nosotros lo tenemos listo para ir. 179 00:08:17,740 --> 00:08:20,130 Empezamos en la parte frontal de nuestra lista con dos. 180 00:08:20,130 --> 00:08:22,380 Y queremos insertar de una manera ordenada. 181 00:08:22,380 --> 00:08:27,550 >> Así que si vemos a dos y queremos poner en cinco, ¿qué hacemos cuando vemos 182 00:08:27,550 --> 00:08:28,800 algo menos que nosotros? 183 00:08:28,800 --> 00:08:31,850 184 00:08:31,850 --> 00:08:33,520 ¿Qué? 185 00:08:33,520 --> 00:08:36,750 Queremos insertar cinco en este lista enlazada, manteniéndolo ordenado. 186 00:08:36,750 --> 00:08:37,520 Vemos el número dos. 187 00:08:37,520 --> 00:08:38,769 Entonces, ¿qué hacemos? 188 00:08:38,769 --> 00:08:39,179 Marcus? 189 00:08:39,179 --> 00:08:40,679 >> AUDIENCIA: Llame al puntero al siguiente nodo. 190 00:08:40,679 --> 00:08:42,530 >> JASON HIRSCHHORN: ¿Y por qué nos vamos a la siguiente? 191 00:08:42,530 --> 00:08:45,970 >> AUDIENCIA: Porque es la siguiente nodo de la lista. 192 00:08:45,970 --> 00:08:48,310 Y sólo se sabe que otra ubicación. 193 00:08:48,310 --> 00:08:50,410 >> JASON HIRSCHHORN: Y cinco es mayor de dos, en particular. 194 00:08:50,410 --> 00:08:51,600 Porque queremos mantenerla ordenada. 195 00:08:51,600 --> 00:08:52,730 Así cinco es mayor que dos. 196 00:08:52,730 --> 00:08:54,460 Así que pasamos a la siguiente. 197 00:08:54,460 --> 00:08:55,240 Y ahora llegamos a cuatro. 198 00:08:55,240 --> 00:08:56,490 ¿Y qué pasa cuando lleguemos a cuatro? 199 00:08:56,490 --> 00:08:58,920 200 00:08:58,920 --> 00:09:00,310 >> El cinco es mayor que cuatro. 201 00:09:00,310 --> 00:09:01,460 Así que seguimos adelante. 202 00:09:01,460 --> 00:09:03,110 Y ahora estamos a las seis. 203 00:09:03,110 --> 00:09:04,360 ¿Y qué es lo que vemos a las seis? 204 00:09:04,360 --> 00:09:08,672 205 00:09:08,672 --> 00:09:09,608 Sí, Carlos? 206 00:09:09,608 --> 00:09:10,544 >> AUDIENCIA: Six es mayor que cinco. 207 00:09:10,544 --> 00:09:11,480 >> JASON HIRSCHHORN: Six es mayor que cinco. 208 00:09:11,480 --> 00:09:13,660 Así que ahí es donde queremos para insertar cinco. 209 00:09:13,660 --> 00:09:17,320 Sin embargo, tenga en cuenta que si nos sólo tienen un puntero aquí - 210 00:09:17,320 --> 00:09:19,840 este es nuestro puntero extra que es atravesando por la lista. 211 00:09:19,840 --> 00:09:21,860 Y estamos apuntando a seis. 212 00:09:21,860 --> 00:09:25,010 Hemos perdido la pista de lo viene antes de las seis. 213 00:09:25,010 --> 00:09:29,130 Así que si queremos insertar algo en esta lista mantenerla ordenada, que 214 00:09:29,130 --> 00:09:31,630 probablemente necesitará el número de punteros? 215 00:09:31,630 --> 00:09:32,280 >> AUDIENCIA: Dos. 216 00:09:32,280 --> 00:09:32,920 >> JASON Hirschhorn: Dos. 217 00:09:32,920 --> 00:09:35,720 Uno para realizar un seguimiento de la corriente uno y uno para realizar un seguimiento de 218 00:09:35,720 --> 00:09:37,050 la anterior. 219 00:09:37,050 --> 00:09:38,450 Esta es sólo una lista vinculada individualmente. 220 00:09:38,450 --> 00:09:39,670 Sólo va en una dirección. 221 00:09:39,670 --> 00:09:43,220 Si tuviéramos una lista doblemente enlazada, donde todo apuntaba a la cosa 222 00:09:43,220 --> 00:09:46,240 después de ella y la cosa antes de que, a continuación, no tendríamos necesidad de hacer eso. 223 00:09:46,240 --> 00:09:49,350 Pero en este caso no queremos perder un seguimiento de lo que hubo antes de nosotros en caso de 224 00:09:49,350 --> 00:09:53,350 tenemos que insertar cinco en alguna parte en el medio. 225 00:09:53,350 --> 00:09:55,610 Digamos que Insertamos nueve. 226 00:09:55,610 --> 00:09:57,260 ¿Qué pasaría cuando llegamos a las ocho? 227 00:09:57,260 --> 00:10:01,860 228 00:10:01,860 --> 00:10:04,880 >> AUDIENCIA: Usted tendría que conseguir que el punto nulo. 229 00:10:04,880 --> 00:10:07,820 En lugar de tener punto nulo tendrías para agregar un elemento y luego tener 230 00:10:07,820 --> 00:10:09,216 que apunte a nueve. 231 00:10:09,216 --> 00:10:09,700 >> JASON Hirschhorn: Exactamente. 232 00:10:09,700 --> 00:10:10,600 Así que tenemos ocho. 233 00:10:10,600 --> 00:10:13,140 Llegamos al final de la lista debido a esto apunta a null. 234 00:10:13,140 --> 00:10:16,330 Y ahora, en lugar de tener que apunte a nula tenemos que apunte a nuestro nuevo nodo. 235 00:10:16,330 --> 00:10:19,870 Y ponemos el puntero en nuestro nuevo nodo en null. 236 00:10:19,870 --> 00:10:21,445 ¿Alguien tiene alguna pregunta acerca de la inserción? 237 00:10:21,445 --> 00:10:25,620 238 00:10:25,620 --> 00:10:28,100 ¿Qué pasa si no se preocupan por mantener la lista ordenada? 239 00:10:28,100 --> 00:10:31,701 240 00:10:31,701 --> 00:10:34,350 >> AUDIENCIA: Stick it en el principio o al final. 241 00:10:34,350 --> 00:10:35,510 >> JASON Hirschhorn: Pegúela en al principio o al final. 242 00:10:35,510 --> 00:10:37,276 ¿Cuál debemos hacer? 243 00:10:37,276 --> 00:10:38,770 Bobby? 244 00:10:38,770 --> 00:10:41,020 ¿Por qué al final? 245 00:10:41,020 --> 00:10:43,250 >> AUDIENCIA: Debido a que el principio ya está lleno. 246 00:10:43,250 --> 00:10:43,575 >> JASON Hirschhorn: OK. 247 00:10:43,575 --> 00:10:44,360 El comienzo ya está lleno. 248 00:10:44,360 --> 00:10:46,090 ¿Quién quiere argumentar en contra de Bobby. 249 00:10:46,090 --> 00:10:47,290 Marcus. 250 00:10:47,290 --> 00:10:48,910 >> AUDIENCIA: Bueno, usted probablemente querrá pegarlo al principio porque 251 00:10:48,910 --> 00:10:50,140 de lo contrario si usted lo pone en final que tendría que 252 00:10:50,140 --> 00:10:51,835 recorrer toda la lista. 253 00:10:51,835 --> 00:10:52,990 >> JASON Hirschhorn: Exactamente. 254 00:10:52,990 --> 00:10:57,970 Así que si estamos pensando en el tiempo de ejecución, la tiempo de ejecución de la inserción en el extremo 255 00:10:57,970 --> 00:11:00,110 sería n, el tamaño de este. 256 00:11:00,110 --> 00:11:03,080 ¿Cuál es el tiempo de ejecución de O de inserción por el principio? 257 00:11:03,080 --> 00:11:04,170 Constante de tiempo. 258 00:11:04,170 --> 00:11:07,075 Así que si usted no se preocupan por mantener algo ordenada, mucho mejor que sólo 259 00:11:07,075 --> 00:11:08,420 insertar al principio de esta lista. 260 00:11:08,420 --> 00:11:10,320 Y eso se puede hacer en tiempo constante. 261 00:11:10,320 --> 00:11:13,900 262 00:11:13,900 --> 00:11:14,690 >> Aceptar. 263 00:11:14,690 --> 00:11:18,870 Operación siguiente se encontró que otros - hemos redactaron del búsqueda. 264 00:11:18,870 --> 00:11:22,470 Pero vamos a mirar a través de la lista enlazada por algún objeto. 265 00:11:22,470 --> 00:11:26,000 Ustedes han visto el código de buscar antes en la conferencia. 266 00:11:26,000 --> 00:11:29,490 Pero que tipo de sólo hicimos con insertar, o al menos la inserción 267 00:11:29,490 --> 00:11:30,580 algo ordenada. 268 00:11:30,580 --> 00:11:36,350 Te ves a través, pasando por el nodo nodo, hasta que encuentre el número que usted está 269 00:11:36,350 --> 00:11:37,780 buscando. 270 00:11:37,780 --> 00:11:39,670 ¿Qué sucede si usted llega a el final de la lista? 271 00:11:39,670 --> 00:11:43,020 Digamos que yo estoy buscando a las nueve y me llegar al final de la lista. 272 00:11:43,020 --> 00:11:44,270 ¿Qué hacemos? 273 00:11:44,270 --> 00:11:47,147 274 00:11:47,147 --> 00:11:48,110 >> AUDIENCIA: Volver falso? 275 00:11:48,110 --> 00:11:48,690 >> JASON Hirschhorn: Regresa falso. 276 00:11:48,690 --> 00:11:49,960 No nos encontrará. 277 00:11:49,960 --> 00:11:52,010 Si llega al final de la lista y que no encontró el número al que está 278 00:11:52,010 --> 00:11:54,170 buscando, no está allí. 279 00:11:54,170 --> 00:11:55,420 ¿Una pregunta sobre encontrar? 280 00:11:55,420 --> 00:11:59,530 281 00:11:59,530 --> 00:12:04,615 Si se trataba de una lista ordenada, lo que haría ser diferente para nuestra búsqueda? 282 00:12:04,615 --> 00:12:07,370 283 00:12:07,370 --> 00:12:08,103 Sí. 284 00:12:08,103 --> 00:12:10,600 >> AUDIENCIA: Se encontraría el primer valor es mayor que el 285 00:12:10,600 --> 00:12:12,390 usted está buscando y a continuación, devolver false. 286 00:12:12,390 --> 00:12:13,190 >> JASON Hirschhorn: Exactamente. 287 00:12:13,190 --> 00:12:17,310 Así que si se trata de una lista ordenada, si llegamos a algo que es más grande que lo 288 00:12:17,310 --> 00:12:20,180 que estamos buscando, nosotros no necesitamos seguir adelante hasta el final de la lista. 289 00:12:20,180 --> 00:12:24,060 Podemos en ese punto return false porque no vamos a encontrar. 290 00:12:24,060 --> 00:12:27,340 La pregunta es ahora, hemos hablado de mantener listas enlazadas ordenados, 291 00:12:27,340 --> 00:12:28,180 manteniéndolos sin clasificar. 292 00:12:28,180 --> 00:12:30,050 Eso va a ser algo que te probablemente va a tener que pensar en 293 00:12:30,050 --> 00:12:34,240 cuando un problema de codificación establecido cinco si elegir una tabla hash con separada 294 00:12:34,240 --> 00:12:36,360 enfoque de encadenamiento, que hablaremos más tarde. 295 00:12:36,360 --> 00:12:41,400 >> Pero ¿vale la pena mantener la lista ordenada y luego ser capaz de tener tal vez 296 00:12:41,400 --> 00:12:42,310 Búsquedas más rápidas? 297 00:12:42,310 --> 00:12:47,220 ¿O es mejor para insertar rápidamente algo en tiempo de ejecución constante, pero luego 298 00:12:47,220 --> 00:12:48,430 tener más tiempo buscando? 299 00:12:48,430 --> 00:12:52,250 Eso es un compromiso justo ahí que llegar a decidir qué es lo más apropiado 300 00:12:52,250 --> 00:12:53,590 para su problema específico. 301 00:12:53,590 --> 00:12:56,680 Y no es necesariamente una respuesta toda la razón. 302 00:12:56,680 --> 00:12:59,520 Pero sin duda es una decisión que usted obtiene de hacer, y probablemente bueno para defender 303 00:12:59,520 --> 00:13:05,270 que en, digamos, un comentario o dos por qué que eligió una sobre la otra. 304 00:13:05,270 --> 00:13:06,490 >> Por último, la eliminación. 305 00:13:06,490 --> 00:13:08,100 Hemos visto borrar. 306 00:13:08,100 --> 00:13:09,180 Es similar a la búsqueda. 307 00:13:09,180 --> 00:13:11,020 Buscamos el elemento. 308 00:13:11,020 --> 00:13:12,390 Digamos que estamos tratando de eliminar seis. 309 00:13:12,390 --> 00:13:14,450 Así nos encontramos con seis aquí. 310 00:13:14,450 --> 00:13:18,860 Lo que tenemos que asegurarnos de que hacer es que todo lo que está apuntando a 311 00:13:18,860 --> 00:13:21,220 seis - como vemos en el paso dos aquí abajo - 312 00:13:21,220 --> 00:13:26,500 lo que sea que apunta a seis necesidades a saltar seis ahora y cambiar para 313 00:13:26,500 --> 00:13:28,160 cualquiera que sea seis está apuntando. 314 00:13:28,160 --> 00:13:31,410 No queremos dejar huérfano vez el resto de nuestra lista por el olvido para establecer que 315 00:13:31,410 --> 00:13:32,960 puntero anterior. 316 00:13:32,960 --> 00:13:35,960 Y a continuación, a veces, dependiendo en el programa, ellos sólo 317 00:13:35,960 --> 00:13:37,380 eliminar este nodo completo. 318 00:13:37,380 --> 00:13:40,135 A veces usted querrá volver el valor que está en este nodo. 319 00:13:40,135 --> 00:13:42,490 Así es como la supresión de las obras. 320 00:13:42,490 --> 00:13:44,610 ¿Tiene preguntas sobre eliminar? 321 00:13:44,610 --> 00:13:51,280 322 00:13:51,280 --> 00:13:53,850 >> AUDIENCIA: Así que si usted va a borrar él, sería simplemente usar gratis porque 323 00:13:53,850 --> 00:13:55,655 presumiblemente se malloced? 324 00:13:55,655 --> 00:13:57,976 >> JASON Hirschhorn: Si desea liberar algo que es exactamente correcto y usted 325 00:13:57,976 --> 00:13:58,540 malloced ella. 326 00:13:58,540 --> 00:14:00,410 Digamos que queríamos volver a este valor. 327 00:14:00,410 --> 00:14:04,010 Podríamos volver seis y luego libre este nodo y conexión de llamadas en él. 328 00:14:04,010 --> 00:14:06,180 O es probable que llamaríamos libre primero y luego regresar seis. 329 00:14:06,180 --> 00:14:11,210 330 00:14:11,210 --> 00:14:11,580 >> Aceptar. 331 00:14:11,580 --> 00:14:14,010 Así que vamos a pasar a la práctica de codificación. 332 00:14:14,010 --> 00:14:16,090 Vamos a codificar tres funciones. 333 00:14:16,090 --> 00:14:18,260 La primera se llama insert_node. 334 00:14:18,260 --> 00:14:22,170 Así que tienes el código que te envié, y si estás viendo esto más adelante 335 00:14:22,170 --> 00:14:28,020 se puede acceder al código en linked.c en el sitio web CS50. 336 00:14:28,020 --> 00:14:30,880 Pero en linked.c, hay algo de código esqueleto que ya está 337 00:14:30,880 --> 00:14:32,280 ha escrito para usted. 338 00:14:32,280 --> 00:14:34,560 Y luego hay un par de funciones que necesita para escribir. 339 00:14:34,560 --> 00:14:36,380 >> En primer lugar vamos a escribir insert_node. 340 00:14:36,380 --> 00:14:39,800 ¿Y qué hace insert_node es decir inserta un entero. 341 00:14:39,800 --> 00:14:42,440 Y usted está dando el número entero en una lista enlazada. 342 00:14:42,440 --> 00:14:45,470 Y, en particular, es necesario para mantener la lista ordenada 343 00:14:45,470 --> 00:14:47,650 desde el más pequeño al más grande. 344 00:14:47,650 --> 00:14:51,360 Además, usted no quiere inserte los duplicados. 345 00:14:51,360 --> 00:14:54,600 Por último, como se puede ver insert_node devuelve un bool. 346 00:14:54,600 --> 00:14:57,140 Así que se supone que debes saber al usuario si o no el inserto era 347 00:14:57,140 --> 00:15:00,800 éxito devolviendo verdadero o falso. 348 00:15:00,800 --> 00:15:02,580 Al final de este programa - 349 00:15:02,580 --> 00:15:05,750 y para esta etapa no es necesario que preocuparse por la liberación de cualquier cosa. 350 00:15:05,750 --> 00:15:11,790 Así que todo lo que estamos haciendo es tomando un entero e insertándolo en una lista. 351 00:15:11,790 --> 00:15:13,890 >> Eso es lo que te estoy pidiendo que hagas ahora. 352 00:15:13,890 --> 00:15:17,620 Una vez más, en el linked.c, que se todos tienen, es el código de esqueleto. 353 00:15:17,620 --> 00:15:20,980 Y hay que ver hacia el fondo la declaración de la función de la muestra. 354 00:15:20,980 --> 00:15:27,390 Sin embargo, antes de entrar en la codificación que en C, yo le animo a ir 355 00:15:27,390 --> 00:15:29,330 a través de los pasos que hemos estado la práctica de cada semana. 356 00:15:29,330 --> 00:15:31,100 Nosotros ya hemos pasado por una foto de esto. 357 00:15:31,100 --> 00:15:33,380 Así que usted debe tener algún conocimiento de cómo funciona esto. 358 00:15:33,380 --> 00:15:36,590 Pero me animo a escribir algunos pseudocódigo antes de sumergirse pulg 359 00:15:36,590 --> 00:15:38,640 Y vamos a repasar pseudocódigo como un grupo. 360 00:15:38,640 --> 00:15:41,470 Y una vez que has escrito tu pseudocódigo, y una vez que hemos escrito nuestra 361 00:15:41,470 --> 00:15:45,850 pseudocódigo como grupo, puede entrar en la codificación en C. 362 00:15:45,850 --> 00:15:49,980 >> Como un mano a mano, la función insert_node es probablemente el más difícil de 363 00:15:49,980 --> 00:15:53,550 los tres que vamos a escribir porque añadido algunas restricciones adicionales para 364 00:15:53,550 --> 00:15:57,190 su programación, en particular, que no vas a insertar cualquier 365 00:15:57,190 --> 00:15:59,880 duplicados y que la lista debe permanecer ordenado. 366 00:15:59,880 --> 00:16:02,660 Así que este es un programa no trivial que usted necesita para codificar. 367 00:16:02,660 --> 00:16:06,470 ¿Y por qué no te llevas seis y cincuenta y cinco minutos, para simplemente trabajar en el 368 00:16:06,470 --> 00:16:07,640 pseudocódigo y el código. 369 00:16:07,640 --> 00:16:09,460 Y luego vamos a empezar ir como un grupo. 370 00:16:09,460 --> 00:16:11,680 Una vez más, si usted tiene alguna pregunta sólo levantar la mano y voy a entrar en razón. 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 >> Nosotros también, en general hacemos estos - 375 00:18:30,120 --> 00:18:32,070 o yo no te digo explícitamente puede trabajar con la gente. 376 00:18:32,070 --> 00:18:36,500 Pero, obviamente, yo le animo, si tiene preguntas, pedir al 377 00:18:36,500 --> 00:18:39,840 vecino sentado a tu lado o incluso trabajar con alguien 378 00:18:39,840 --> 00:18:40,510 más si quieres. 379 00:18:40,510 --> 00:18:42,600 Este no tiene que ser un individuo actividad silenciosa. 380 00:18:42,600 --> 00:20:11,770 381 00:20:11,770 --> 00:20:16,330 >> Vamos a empezar con la escritura de algunos pseudocódigo en el tablero. 382 00:20:16,330 --> 00:20:19,395 ¿Quién me puede dar la primera línea de pseudocódigo para este programa? 383 00:20:19,395 --> 00:20:22,240 384 00:20:22,240 --> 00:20:23,640 Para esta función, en lugar - 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 >> AUDIENCIA: Así que lo primero que hice fue crear un nuevo puntero al nodo y yo 388 00:20:36,560 --> 00:20:41,320 inicializa lo que apunta a la misma cosa que la lista está señalando. 389 00:20:41,320 --> 00:20:41,550 >> JASON Hirschhorn: OK. 390 00:20:41,550 --> 00:20:45,190 Así que va a crear un nuevo puntero a la lista, no para el nodo. 391 00:20:45,190 --> 00:20:45,420 >> AUDIENCIA: Así es. 392 00:20:45,420 --> 00:20:46,150 Sí. 393 00:20:46,150 --> 00:20:46,540 >> JASON Hirschhorn: OK. 394 00:20:46,540 --> 00:20:48,221 Y entonces, ¿qué es lo que queremos hacer? 395 00:20:48,221 --> 00:20:49,163 ¿Qué hay después de eso? 396 00:20:49,163 --> 00:20:50,105 ¿Qué pasa con el nodo? 397 00:20:50,105 --> 00:20:51,050 No tenemos un nodo. 398 00:20:51,050 --> 00:20:52,300 Sólo tenemos un valor. 399 00:20:52,300 --> 00:20:55,918 400 00:20:55,918 --> 00:20:58,890 Si queremos insertar un nodo, lo que hace que necesita hacer primero antes de que podamos siquiera 401 00:20:58,890 --> 00:20:59,980 pensar insertarlo? 402 00:20:59,980 --> 00:21:00,820 >> AUDIENCIA: Oh, lo siento. 403 00:21:00,820 --> 00:21:02,160 tenemos que malloc espacio para un nodo. 404 00:21:02,160 --> 00:21:02,455 >> JASON Hirschhorn: Excelente. 405 00:21:02,455 --> 00:21:03,210 Vamos a hacer - 406 00:21:03,210 --> 00:21:04,628 Aceptar. 407 00:21:04,628 --> 00:21:06,065 No se puede llegar tan alto. 408 00:21:06,065 --> 00:21:08,939 409 00:21:08,939 --> 00:21:09,897 Aceptar. 410 00:21:09,897 --> 00:21:13,236 Vamos a ir hacia abajo, y luego estamos usando dos columnas. 411 00:21:13,236 --> 00:21:13,732 No puedo ir a que - 412 00:21:13,732 --> 00:21:14,982 Aceptar. 413 00:21:14,982 --> 00:21:23,660 414 00:21:23,660 --> 00:21:25,130 Crear un nuevo nodo. 415 00:21:25,130 --> 00:21:29,380 Puede crear otro puntero a la lista o simplemente puede utilizar la lista, tal como existe. 416 00:21:29,380 --> 00:21:30,720 Usted realmente no necesita hacer eso. 417 00:21:30,720 --> 00:21:31,750 >> Así que creamos un nuevo nodo. 418 00:21:31,750 --> 00:21:32,010 Grande. 419 00:21:32,010 --> 00:21:32,840 Eso es lo que hacemos en primer lugar. 420 00:21:32,840 --> 00:21:34,870 ¿Qué sigue? 421 00:21:34,870 --> 00:21:35,080 >> AUDIENCIA: Espere. 422 00:21:35,080 --> 00:21:38,330 ¿Hay que crear un nuevo nodo ahora o debemos esperar para asegurarse de que 423 00:21:38,330 --> 00:21:42,260 no hay duplicados del nodo en la lista antes de que nos lo creamos? 424 00:21:42,260 --> 00:21:43,100 >> JASON Hirschhorn: Buena pregunta. 425 00:21:43,100 --> 00:21:47,770 Vamos a sostener que para más adelante porque el mayor parte del tiempo estaremos creando 426 00:21:47,770 --> 00:21:48,220 un nuevo nodo. 427 00:21:48,220 --> 00:21:49,110 Así que vamos a seguir eso aquí. 428 00:21:49,110 --> 00:21:51,006 Pero esa es una buena pregunta. 429 00:21:51,006 --> 00:21:53,250 Si creamos y nos encontramos un duplicado, lo que debe 430 00:21:53,250 --> 00:21:54,490 que hacemos antes de regresar? 431 00:21:54,490 --> 00:21:55,190 >> AUDIENCIA: liberarlo. 432 00:21:55,190 --> 00:21:55,470 >> JASON Hirschhorn: Si. 433 00:21:55,470 --> 00:21:56,500 Probablemente liberarlo. 434 00:21:56,500 --> 00:21:56,760 Aceptar. 435 00:21:56,760 --> 00:21:59,850 ¿Qué hacemos después de que crear un nuevo nodo? 436 00:21:59,850 --> 00:22:02,260 Annie? 437 00:22:02,260 --> 00:22:04,780 >> AUDIENCIA: Ponemos la número en el nodo? 438 00:22:04,780 --> 00:22:05,140 >> JASON Hirschhorn: Exactamente. 439 00:22:05,140 --> 00:22:07,190 Ponemos el número - que malloc espacio. 440 00:22:07,190 --> 00:22:08,160 Voy a dejar que todo en una sola línea. 441 00:22:08,160 --> 00:22:08,720 Pero tienes razón. 442 00:22:08,720 --> 00:22:10,305 Nos malloc espacio, y luego ponemos el número pulg 443 00:22:10,305 --> 00:22:12,585 Incluso podemos establecer el puntero parte de ella en null. 444 00:22:12,585 --> 00:22:13,720 Eso es exactamente correcto. 445 00:22:13,720 --> 00:22:17,400 Y entonces ¿qué pasa después de eso? 446 00:22:17,400 --> 00:22:18,490 Dibujamos la imagen en el tablero. 447 00:22:18,490 --> 00:22:21,190 Entonces, ¿qué hacemos? 448 00:22:21,190 --> 00:22:22,680 >> AUDIENCIA: Vamos a través de la lista. 449 00:22:22,680 --> 00:22:23,930 >> JASON Hirschhorn: Ir a través de la lista. 450 00:22:23,930 --> 00:22:30,620 451 00:22:30,620 --> 00:22:31,100 Aceptar. 452 00:22:31,100 --> 00:22:34,280 ¿Y qué vamos a comprobar en cada nodo. 453 00:22:34,280 --> 00:22:35,955 Kurt, ¿qué es lo comprobamos para en cada nodo? 454 00:22:35,955 --> 00:22:41,640 >> AUDIENCIA: Ver si el valor de n de ese nodo es mayor que el valor de n 455 00:22:41,640 --> 00:22:43,070 de nuestro nodo. 456 00:22:43,070 --> 00:22:43,340 >> JASON Hirschhorn: OK. 457 00:22:43,340 --> 00:22:44,280 Yo voy a hacer - 458 00:22:44,280 --> 00:22:45,855 Sí, está bien. 459 00:22:45,855 --> 00:22:48,160 Así que es n - 460 00:22:48,160 --> 00:22:59,040 Yo voy a decir si el valor es mayor de este nodo, entonces, ¿qué hacemos? 461 00:22:59,040 --> 00:23:07,290 >> AUDIENCIA: Bueno, entonces nos insertamos lo correcto antes de eso. 462 00:23:07,290 --> 00:23:07,970 >> JASON Hirschhorn: OK. 463 00:23:07,970 --> 00:23:09,410 Así que si es mayor que este, entonces queremos insertar. 464 00:23:09,410 --> 00:23:14,010 Pero queremos insertar justo antes de porque nosotros también necesitamos ser 465 00:23:14,010 --> 00:23:16,070 hacer el seguimiento y, a continuación, de lo que era antes. 466 00:23:16,070 --> 00:23:22,690 Así que insertar antes. 467 00:23:22,690 --> 00:23:25,120 Así que es probable que perdimos algo anteriormente. 468 00:23:25,120 --> 00:23:27,770 Probablemente necesitemos estar manteniendo un seguimiento de lo que está pasando. 469 00:23:27,770 --> 00:23:28,460 Pero vamos a llegar allí. 470 00:23:28,460 --> 00:23:30,160 Entonces, ¿qué valor es inferior? 471 00:23:30,160 --> 00:23:38,030 472 00:23:38,030 --> 00:23:39,710 Kurt, ¿qué hacemos si valor es menor que? 473 00:23:39,710 --> 00:23:43,000 >> AUDIENCIA: A continuación, sólo seguir adelante a menos que sea el último. 474 00:23:43,000 --> 00:23:43,550 >> JASON Hirschhorn: eso me gusta. 475 00:23:43,550 --> 00:23:44,800 Así que ir al siguiente nodo. 476 00:23:44,800 --> 00:23:47,410 477 00:23:47,410 --> 00:23:48,930 A menos que sea el último - 478 00:23:48,930 --> 00:23:51,100 es probable que estamos comprobando que en los términos de una condición. 479 00:23:51,100 --> 00:23:54,870 Pero sí, el próximo nodo. 480 00:23:54,870 --> 00:23:58,680 Y eso no baje mucho, así que vamos a pasar por aquí. 481 00:23:58,680 --> 00:24:02,030 Pero si - 482 00:24:02,030 --> 00:24:03,280 ¿Todos pueden ver esto? 483 00:24:03,280 --> 00:24:07,230 484 00:24:07,230 --> 00:24:11,610 Si somos iguales, ¿qué hacemos? 485 00:24:11,610 --> 00:24:15,740 Si el valor que estamos tratando de insertar es igual al valor de este nodo? 486 00:24:15,740 --> 00:24:16,320 ¿Sí? 487 00:24:16,320 --> 00:24:18,400 >> AUDIENCIA: [inaudible]. 488 00:24:18,400 --> 00:24:18,850 >> JASON Hirschhorn: Si. 489 00:24:18,850 --> 00:24:19,290 Dada esta - 490 00:24:19,290 --> 00:24:20,090 Marcus tiene razón. 491 00:24:20,090 --> 00:24:21,330 Podríamos haber hecho tal vez algo diferente. 492 00:24:21,330 --> 00:24:25,360 Pero teniendo en cuenta que hemos creado, aquí debemos liberar y luego regresar. 493 00:24:25,360 --> 00:24:26,774 Oh boy. 494 00:24:26,774 --> 00:24:30,080 ¿Así está mejor? 495 00:24:30,080 --> 00:24:31,850 ¿Cómo es eso? 496 00:24:31,850 --> 00:24:33,100 Aceptar. 497 00:24:33,100 --> 00:24:35,360 498 00:24:35,360 --> 00:24:37,640 Gratis y entonces, ¿qué hacemos nosotros devolver, [inaudible]? 499 00:24:37,640 --> 00:24:41,330 500 00:24:41,330 --> 00:24:44,110 Aceptar. 501 00:24:44,110 --> 00:24:45,360 ¿Nos estamos perdiendo algo? 502 00:24:45,360 --> 00:24:53,500 503 00:24:53,500 --> 00:24:59,650 Entonces, ¿dónde hacer el seguimiento del nodo antes? 504 00:24:59,650 --> 00:25:02,370 >> AUDIENCIA: Creo que sería ir después de crear un nuevo nodo. 505 00:25:02,370 --> 00:25:02,600 >> JASON Hirschhorn: OK. 506 00:25:02,600 --> 00:25:03,940 Así que al principio probablemente vamos - 507 00:25:03,940 --> 00:25:07,175 sí, podemos crear un puntero a una nueva nodo, como un puntero de nodo anterior y 508 00:25:07,175 --> 00:25:09,600 un puntero nodo actual. 509 00:25:09,600 --> 00:25:12,640 Así que vamos a insertar eso aquí. 510 00:25:12,640 --> 00:25:15,610 511 00:25:15,610 --> 00:25:26,900 Crear actual y anterior punteros a los nodos. 512 00:25:26,900 --> 00:25:28,955 Pero ¿cuándo nos ajustamos los punteros? 513 00:25:28,955 --> 00:25:30,205 ¿Dónde lo hacemos en el código? 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 >> AUDIENCIA: - condiciones de valor? 517 00:25:35,170 --> 00:25:36,420 >> JASON Hirschhorn: ¿Qué uno en particular? 518 00:25:36,420 --> 00:25:39,862 519 00:25:39,862 --> 00:25:40,720 >> AUDIENCIA: Estoy confundido. 520 00:25:40,720 --> 00:25:44,200 Si el valor es superior a este nodo, ¿eso no significa que usted quiere ir 521 00:25:44,200 --> 00:25:45,320 al siguiente nodo? 522 00:25:45,320 --> 00:25:49,515 >> JASON HIRSCHHORN: Así que si nuestro valor es mayor que el valor de este nodo. 523 00:25:49,515 --> 00:25:52,130 >> AUDIENCIA: Sí, entonces lo que quiere ir más abajo de la línea, ¿no? 524 00:25:52,130 --> 00:25:52,590 >> JASON HIRSCHHORN: Así es. 525 00:25:52,590 --> 00:25:53,840 Así que no insertamos aquí. 526 00:25:53,840 --> 00:25:58,430 527 00:25:58,430 --> 00:26:03,240 Si el valor es inferior a este nodo, a continuación, vamos al siguiente nodo - o entonces 528 00:26:03,240 --> 00:26:03,835 insertar antes. 529 00:26:03,835 --> 00:26:05,966 >> AUDIENCIA: Espera, que es este nodo y que es el valor? 530 00:26:05,966 --> 00:26:08,510 531 00:26:08,510 --> 00:26:09,280 >> JASON HIRSCHHORN: Buena pregunta. 532 00:26:09,280 --> 00:26:13,260 Valor por esta definición de función es lo que se nos da. 533 00:26:13,260 --> 00:26:16,910 Así que el valor es el número que se nos da. 534 00:26:16,910 --> 00:26:21,120 Así que si el valor es menor que este nodo, necesitamos tiempo para insertar. 535 00:26:21,120 --> 00:26:24,575 Si el valor es superior a este nodo, vamos al siguiente nodo. 536 00:26:24,575 --> 00:26:26,790 Y volviendo a la pregunta original, sin embargo, donde - 537 00:26:26,790 --> 00:26:29,060 >> AUDIENCIA: Si el valor es mayor de este nodo. 538 00:26:29,060 --> 00:26:30,310 >> JASON HIRSCHHORN: Y así ¿qué hacemos aquí? 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 Eso es correcto. 542 00:26:38,860 --> 00:26:41,370 Yo sólo voy a escribir punteros de actualización. 543 00:26:41,370 --> 00:26:44,010 Pero eso sí, con la actual usted desea actualizar a 544 00:26:44,010 --> 00:26:46,080 apuntar a la siguiente. 545 00:26:46,080 --> 00:26:47,330 Cualquier otra cosa que se está perdiendo? 546 00:26:47,330 --> 00:26:52,710 547 00:26:52,710 --> 00:26:54,940 Así que voy a escribir esto código en gedit. 548 00:26:54,940 --> 00:26:58,375 Y mientras hago esto, usted puede tener una par de minutos más para trabajar en la codificación 549 00:26:58,375 --> 00:28:19,240 esta en C. 550 00:28:19,240 --> 00:28:20,940 >> Así que tengo que ingresar el pseudocódigo. 551 00:28:20,940 --> 00:28:22,940 Una nota rápida antes de empezar. 552 00:28:22,940 --> 00:28:25,560 Puede que no seamos capaces de completamente terminar esto en todo 553 00:28:25,560 --> 00:28:27,300 tres de estas funciones. 554 00:28:27,300 --> 00:28:30,630 Hay soluciones correctas a los que voy a enviar por correo electrónico a ustedes 555 00:28:30,630 --> 00:28:33,730 después de la sección, y lo hará se publicarán en CS50.net. 556 00:28:33,730 --> 00:28:35,640 Así que no os animo a ir a buscar en las secciones. 557 00:28:35,640 --> 00:28:40,550 Te animo a que intente resolverlo usted poseer, y luego usar el la práctica 558 00:28:40,550 --> 00:28:41,760 problemas para comprobar sus respuestas. 559 00:28:41,760 --> 00:28:47,070 Todas ellas han sido diseñadas para cerca relacionarse y cumplir con lo 560 00:28:47,070 --> 00:28:48,400 lo que tienes que hacer en el conjunto de problemas. 561 00:28:48,400 --> 00:28:53,820 Así que te animo a practicar este por su cuenta y luego usar el código para 562 00:28:53,820 --> 00:28:54,660 compruebe sus respuestas. 563 00:28:54,660 --> 00:28:57,060 Porque quiero seguir adelante para discutir mesas en algún punto de la sección. 564 00:28:57,060 --> 00:28:58,150 Así que podríamos no conseguir en todo momento. 565 00:28:58,150 --> 00:28:59,960 Pero vamos a hacer lo más que podamos ahora. 566 00:28:59,960 --> 00:29:00,370 >> Aceptar. 567 00:29:00,370 --> 00:29:01,960 Comencemos. 568 00:29:01,960 --> 00:29:04,770 Asam, ¿cómo creamos un nuevo nodo? 569 00:29:04,770 --> 00:29:06,810 >> AUDIENCIA: Usted struct *. 570 00:29:06,810 --> 00:29:09,640 >> JASON HIRSCHHORN: Así que tener que hasta aquí. 571 00:29:09,640 --> 00:29:10,040 Oh, lo siento. 572 00:29:10,040 --> 00:29:13,530 ¿Decías struct *. 573 00:29:13,530 --> 00:29:17,260 >> AUDIENCIA: Y luego [? tipo?] nodo o nodo c. 574 00:29:17,260 --> 00:29:17,780 >> JASON HIRSCHHORN: OK. 575 00:29:17,780 --> 00:29:19,740 Voy a llamarlo new_node para que podamos permanecer constante. 576 00:29:19,740 --> 00:29:22,646 577 00:29:22,646 --> 00:29:33,180 >> AUDIENCIA: Y usted desea establecer que a la cabeza, el primer nodo. 578 00:29:33,180 --> 00:29:33,580 >> JASON HIRSCHHORN: OK. 579 00:29:33,580 --> 00:29:37,290 Así que ahora esta apuntando a - por lo que este no ha creado un nuevo nodo aún. 580 00:29:37,290 --> 00:29:41,380 Esto es sólo apunta a la primer nodo en la lista. 581 00:29:41,380 --> 00:29:42,630 ¿Cómo se crea un nuevo nodo? 582 00:29:42,630 --> 00:29:45,490 583 00:29:45,490 --> 00:29:48,070 Si necesito espacio para crear un nuevo nodo. 584 00:29:48,070 --> 00:29:49,230 Malloc. 585 00:29:49,230 --> 00:29:51,710 Y qué tan grande? 586 00:29:51,710 --> 00:30:00,390 >> AUDIENCIA: El tamaño de la estructura. 587 00:30:00,390 --> 00:30:01,150 >> JASON HIRSCHHORN: El tamaño de la estructura. 588 00:30:01,150 --> 00:30:02,400 Y ¿cuál es la estructura llamada? 589 00:30:02,400 --> 00:30:09,670 590 00:30:09,670 --> 00:30:09,840 >> AUDIENCIA: Nodo? 591 00:30:09,840 --> 00:30:11,640 >> JASON HIRSCHHORN: Nodo. 592 00:30:11,640 --> 00:30:17,640 Así malloc (sizeof (nodo)); nos da el espacio. 593 00:30:17,640 --> 00:30:19,740 Y es esta línea - 594 00:30:19,740 --> 00:30:21,740 una cosa es incorrecto en esta línea. 595 00:30:21,740 --> 00:30:24,430 Es new_node un puntero a una estructura? 596 00:30:24,430 --> 00:30:25,650 Es un nombre genérico. 597 00:30:25,650 --> 00:30:26,520 Qué es - 598 00:30:26,520 --> 00:30:27,450 nodo, exactamente. 599 00:30:27,450 --> 00:30:29,340 Es un nodo *. 600 00:30:29,340 --> 00:30:33,010 Y, ¿qué hacemos después que malloc algo, Asan? 601 00:30:33,010 --> 00:30:34,476 ¿Qué es lo primero que vamos a hacer? 602 00:30:34,476 --> 00:30:38,850 603 00:30:38,850 --> 00:30:40,320 ¿Qué pasa si no funciona? 604 00:30:40,320 --> 00:30:42,430 >> AUDIENCIA: Oh, compruebe si apunta al nodo? 605 00:30:42,430 --> 00:30:43,310 >> JASON HIRSCHHORN: Exactamente. 606 00:30:43,310 --> 00:30:46,750 Así que si usted new_node iguales iguales nulo, ¿qué hacemos? 607 00:30:46,750 --> 00:30:51,650 608 00:30:51,650 --> 00:30:54,820 Esto devuelve un bool, esta función. 609 00:30:54,820 --> 00:30:57,760 Exactamente. 610 00:30:57,760 --> 00:30:58,450 Se ve bien. 611 00:30:58,450 --> 00:30:59,680 Cualquier cosa para agregar ahí? 612 00:30:59,680 --> 00:31:00,670 Vamos a añadir cosas al final. 613 00:31:00,670 --> 00:31:03,160 Pero que hasta el momento se ve bien. 614 00:31:03,160 --> 00:31:06,170 Crear indicadores actuales y anteriores. 615 00:31:06,170 --> 00:31:08,650 Michael, ¿cómo puedo hacer esto? 616 00:31:08,650 --> 00:31:12,810 >> AUDIENCIA: Usted tendría hacer un nodo *. 617 00:31:12,810 --> 00:31:21,800 618 00:31:21,800 --> 00:31:25,502 Tendrías que lo hace a uno para new_node pero para la 619 00:31:25,502 --> 00:31:26,905 nodos que ya tienen. 620 00:31:26,905 --> 00:31:27,230 >> JASON HIRSCHHORN: OK. 621 00:31:27,230 --> 00:31:29,255 Así que el nodo actual estamos en. 622 00:31:29,255 --> 00:31:30,505 Voy a llamar a ese curr. 623 00:31:30,505 --> 00:31:39,650 624 00:31:39,650 --> 00:31:39,770 Está bien. 625 00:31:39,770 --> 00:31:41,620 Hemos decidido que queremos mantener dos, porque tenemos que saber 626 00:31:41,620 --> 00:31:42,870 lo que hay antes de ella. 627 00:31:42,870 --> 00:31:45,770 628 00:31:45,770 --> 00:31:47,020 ¿Qué son inicializadas a? 629 00:31:47,020 --> 00:31:49,874 630 00:31:49,874 --> 00:31:54,180 >> AUDIENCIA: Su valor en nuestra lista. 631 00:31:54,180 --> 00:31:58,090 >> JASON HIRSCHHORN: Entonces, ¿cuál es el Lo primero en nuestra lista? 632 00:31:58,090 --> 00:32:04,050 O, ¿cómo sabemos que el a partir de nuestra lista es? 633 00:32:04,050 --> 00:32:08,015 >> AUDIENCIA: ¿No se aprobó en la función de? 634 00:32:08,015 --> 00:32:08,466 >> JASON HIRSCHHORN: Así es. 635 00:32:08,466 --> 00:32:09,716 Se aprobó en aquí. 636 00:32:09,716 --> 00:32:15,910 637 00:32:15,910 --> 00:32:18,980 Así que si se pasa a la función, la inicio de la lista, ¿qué debemos 638 00:32:18,980 --> 00:32:21,270 establecer corriente igual a? 639 00:32:21,270 --> 00:32:22,110 >> AUDIENCIA: Lista. 640 00:32:22,110 --> 00:32:22,900 >> JASON HIRSCHHORN: Lista. 641 00:32:22,900 --> 00:32:24,090 Eso es exactamente correcto. 642 00:32:24,090 --> 00:32:26,290 Ahora que tiene la dirección de el principio de nuestra lista. 643 00:32:26,290 --> 00:32:28,450 Y ¿qué pasa con previa? 644 00:32:28,450 --> 00:32:31,920 >> AUDIENCIA: Lista menos uno? 645 00:32:31,920 --> 00:32:32,690 >> JASON HIRSCHHORN: No nada antes de ella. 646 00:32:32,690 --> 00:32:34,580 Entonces, ¿qué podemos hacer para significar nada? 647 00:32:34,580 --> 00:32:35,050 >> AUDIENCIA: Nulo. 648 00:32:35,050 --> 00:32:35,450 >> JASON HIRSCHHORN: Si. 649 00:32:35,450 --> 00:32:37,950 Eso suena como una buena idea. 650 00:32:37,950 --> 00:32:38,360 Perfect. 651 00:32:38,360 --> 00:32:39,630 Gracias. 652 00:32:39,630 --> 00:32:42,850 Ir a través de la lista. 653 00:32:42,850 --> 00:32:45,490 Constantino, ¿cuánto tiempo vamos que pasar por la lista? 654 00:32:45,490 --> 00:32:49,010 >> AUDIENCIA: hasta llegar a nulo. 655 00:32:49,010 --> 00:32:49,390 >> JASON HIRSCHHORN: OK. 656 00:32:49,390 --> 00:32:50,430 Así que si, mientras que, para el bucle. 657 00:32:50,430 --> 00:32:52,200 ¿Qué estamos haciendo? 658 00:32:52,200 --> 00:32:53,320 >> AUDIENCIA: Tal vez un bucle? 659 00:32:53,320 --> 00:32:53,910 >> JASON HIRSCHHORN: Vamos a hacer un bucle for. 660 00:32:53,910 --> 00:32:55,870 Aceptar. 661 00:32:55,870 --> 00:33:02,465 >> AUDIENCIA: Y decimos por - 662 00:33:02,465 --> 00:33:09,764 663 00:33:09,764 --> 00:33:13,390 hasta que el puntero actual no es igual a nulo. 664 00:33:13,390 --> 00:33:19,160 >> JASON HIRSCHHORN: Así que si conocemos la condiciones, ¿cómo podemos escribir un bucle 665 00:33:19,160 --> 00:33:21,740 con sede fuera esa condición. 666 00:33:21,740 --> 00:33:24,380 ¿Qué clase de un bucle debemos utilizar? 667 00:33:24,380 --> 00:33:25,260 >> AUDIENCIA: While. 668 00:33:25,260 --> 00:33:25,590 >> JASON HIRSCHHORN: Si. 669 00:33:25,590 --> 00:33:27,130 Eso tiene más sentido con base fuera de lo que dijiste. 670 00:33:27,130 --> 00:33:29,430 Si sólo queremos ir a que lo haría sólo sé que cosa, tendría 671 00:33:29,430 --> 00:33:31,680 sentido hacer un bucle while. 672 00:33:31,680 --> 00:33:39,880 Mientras que la corriente no es igual a null, si el valor es inferior a este nodo. 673 00:33:39,880 --> 00:33:41,650 Akshar, dame de esa línea. 674 00:33:41,650 --> 00:33:48,810 675 00:33:48,810 --> 00:33:56,955 >> AUDIENCIA: Si current-> n n menos de su valor. 676 00:33:56,955 --> 00:34:00,170 677 00:34:00,170 --> 00:34:03,260 O revertir eso. 678 00:34:03,260 --> 00:34:06,140 Cambie esa franja. 679 00:34:06,140 --> 00:34:06,620 >> JASON HIRSCHHORN: Lo siento. 680 00:34:06,620 --> 00:34:08,760 >> AUDIENCIA: Cambie el soporte. 681 00:34:08,760 --> 00:34:10,914 >> JASON HIRSCHHORN: Así que si es mayor que el valor. 682 00:34:10,914 --> 00:34:18,719 683 00:34:18,719 --> 00:34:22,120 Porque eso es confuso con la comente anteriormente, voy a hacer eso. 684 00:34:22,120 --> 00:34:22,480 Pero sí. 685 00:34:22,480 --> 00:34:25,125 Si nuestro valor es menor que este nodo, ¿qué hacemos? 686 00:34:25,125 --> 00:34:25,540 Oh. 687 00:34:25,540 --> 00:34:26,710 Lo tengo aquí mismo. 688 00:34:26,710 --> 00:34:27,960 Insertar antes. 689 00:34:27,960 --> 00:34:32,080 690 00:34:32,080 --> 00:34:32,370 Aceptar. 691 00:34:32,370 --> 00:34:33,933 ¿Cómo hacemos eso? 692 00:34:33,933 --> 00:34:34,900 >> AUDIENCIA: ¿Sigue siendo mi? 693 00:34:34,900 --> 00:34:36,150 >> JASON HIRSCHHORN: Si. 694 00:34:36,150 --> 00:34:38,520 695 00:34:38,520 --> 00:34:39,770 >> AUDIENCIA: Usted - 696 00:34:39,770 --> 00:34:42,909 697 00:34:42,909 --> 00:34:44,159 new_node-> siguiente. 698 00:34:44,159 --> 00:34:46,770 699 00:34:46,770 --> 00:34:50,163 >> JASON HIRSCHHORN: Entonces, ¿qué que va a ser igual? 700 00:34:50,163 --> 00:34:52,070 >> AUDIENCIA: Va a la misma corriente. 701 00:34:52,070 --> 00:34:53,889 >> JASON HIRSCHHORN: Exactamente. 702 00:34:53,889 --> 00:34:55,730 Y así, el otro - 703 00:34:55,730 --> 00:34:56,730 lo que más necesitamos para actualizar? 704 00:34:56,730 --> 00:34:59,982 >> AUDIENCIA: Compruebe si el pasado es igual a nulo. 705 00:34:59,982 --> 00:35:01,870 >> JASON HIRSCHHORN: Si prev - 706 00:35:01,870 --> 00:35:03,730 por lo que si es igual prev nulo. 707 00:35:03,730 --> 00:35:05,990 >> AUDIENCIA: Eso significa que va para convertirse en la cabeza. 708 00:35:05,990 --> 00:35:06,780 >> JASON HIRSCHHORN: Eso significa se ha convertido en la cabeza. 709 00:35:06,780 --> 00:35:07,620 Entonces, ¿qué hacemos? 710 00:35:07,620 --> 00:35:12,510 >> AUDIENCIA: Hacemos la cabeza es igual new_node. 711 00:35:12,510 --> 00:35:16,690 >> JASON HIRSCHHORN: Head iguales new_node. 712 00:35:16,690 --> 00:35:20,540 ¿Y por qué la cabeza aquí, no lista? 713 00:35:20,540 --> 00:35:24,940 >> AUDIENCIA: Debido a que la cabeza es un mundial variable, que es el punto de partida. 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 Aceptar. 717 00:35:34,170 --> 00:35:36,150 Y - 718 00:35:36,150 --> 00:35:53,796 >> AUDIENCIA: Entonces, ¿los demás prev-> siguiente es igual new_node. 719 00:35:53,796 --> 00:35:55,080 Y luego puede volver realidad. 720 00:35:55,080 --> 00:35:59,560 721 00:35:59,560 --> 00:36:02,700 >> JASON HIRSCHHORN: ¿Dónde nos pusimos fin new_node? 722 00:36:02,700 --> 00:36:04,850 >> AUDIENCIA: yo - 723 00:36:04,850 --> 00:36:06,180 Me puse de que al comienzo. 724 00:36:06,180 --> 00:36:07,430 >> JASON HIRSCHHORN: Entonces, ¿qué línea? 725 00:36:07,430 --> 00:36:10,000 726 00:36:10,000 --> 00:36:12,598 >> AUDIENCIA: Después de la sentencia if comprobar si se sabe. 727 00:36:12,598 --> 00:36:13,057 >> JASON HIRSCHHORN: ¿Aquí mismo? 728 00:36:13,057 --> 00:36:18,335 >> AUDIENCIA: Haría new_node-> n igual valor. 729 00:36:18,335 --> 00:36:19,585 >> JASON HIRSCHHORN: Suena bien. 730 00:36:19,585 --> 00:36:21,740 731 00:36:21,740 --> 00:36:25,090 Probablemente tiene sentido - no lo hacemos necesita saber lo que la lista que estamos en 732 00:36:25,090 --> 00:36:26,280 porque sólo estamos tratando con una sola lista. 733 00:36:26,280 --> 00:36:29,560 Por lo tanto una mejor declaración de la función de esto es sólo para deshacerse de este 734 00:36:29,560 --> 00:36:34,360 por completo y sólo tiene que insertar un valor en la cabeza. 735 00:36:34,360 --> 00:36:35,930 Ni siquiera necesitamos saber lo lista que estamos metidos 736 00:36:35,930 --> 00:36:39,140 Pero voy a mantener todo por ahora y luego cambiar a la actualización 737 00:36:39,140 --> 00:36:42,590 las diapositivas y código. 738 00:36:42,590 --> 00:36:44,980 Así que se ve bien, por ahora. 739 00:36:44,980 --> 00:36:46,560 Si el valor - que puede hacer esta línea? 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 ¿qué hacemos aquí, Noah. 743 00:36:53,840 --> 00:36:57,890 744 00:36:57,890 --> 00:37:07,100 >> AUDIENCIA: Si el valor es mayor de curr-> n - 745 00:37:07,100 --> 00:37:16,830 746 00:37:16,830 --> 00:37:18,240 >> JASON HIRSCHHORN: ¿Cómo vamos al siguiente nodo? 747 00:37:18,240 --> 00:37:27,760 748 00:37:27,760 --> 00:37:30,530 >> AUDIENCIA: Curr-> n es igual a new_node. 749 00:37:30,530 --> 00:37:37,630 750 00:37:37,630 --> 00:37:39,195 >> JASON HIRSCHHORN: Entonces n es qué parte de la estructura? 751 00:37:39,195 --> 00:37:43,065 752 00:37:43,065 --> 00:37:46,020 El número entero. 753 00:37:46,020 --> 00:37:50,420 Y new_node es un puntero a un nodo. 754 00:37:50,420 --> 00:37:51,880 Entonces, ¿qué parte de curr debemos actualizar? 755 00:37:51,880 --> 00:38:03,900 756 00:38:03,900 --> 00:38:05,400 Si no es n, entonces ¿cuál es la otra parte? 757 00:38:05,400 --> 00:38:21,680 758 00:38:21,680 --> 00:38:22,810 Noé, ¿cuál es la otra parte. 759 00:38:22,810 --> 00:38:23,570 >> AUDIENCIA: Oh, la próxima. 760 00:38:23,570 --> 00:38:25,645 >> JASON HIRSCHHORN: A continuación, exactamente. 761 00:38:25,645 --> 00:38:26,410 Exactamente. 762 00:38:26,410 --> 00:38:28,770 Siguiente es la correcta. 763 00:38:28,770 --> 00:38:31,540 Y lo que más necesitamos actualizar, Noah? 764 00:38:31,540 --> 00:38:32,840 >> AUDIENCIA: Los punteros. 765 00:38:32,840 --> 00:38:34,840 >> JASON HIRSCHHORN: Así actualizamos actual. 766 00:38:34,840 --> 00:38:36,090 >> AUDIENCIA: Anterior-> siguiente. 767 00:38:36,090 --> 00:38:48,160 768 00:38:48,160 --> 00:38:49,410 >> JASON HIRSCHHORN: Si. 769 00:38:49,410 --> 00:38:57,465 770 00:38:57,465 --> 00:38:58,370 Bien, vamos a hacer una pausa. 771 00:38:58,370 --> 00:39:02,200 ¿Quién nos puede ayudar? 772 00:39:02,200 --> 00:39:03,385 Manu, ¿qué debemos hacer? 773 00:39:03,385 --> 00:39:05,615 >> AUDIENCIA: Hay que establecer es igual a curr-> siguiente. 774 00:39:05,615 --> 00:39:09,110 775 00:39:09,110 --> 00:39:11,630 Pero hacer eso antes de la línea anterior. 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 ¿Algo más? 779 00:39:18,260 --> 00:39:19,170 Akshar. 780 00:39:19,170 --> 00:39:22,680 >> AUDIENCIA: Creo que no estás la intención de cambiar curr-> siguiente. 781 00:39:22,680 --> 00:39:29,270 Creo que estás destinado a hacer iguales curr curr-> siguiente para ir al siguiente nodo. 782 00:39:29,270 --> 00:39:30,500 >> JASON HIRSCHHORN: Lo siento, ¿dónde? 783 00:39:30,500 --> 00:39:32,680 ¿En qué línea? 784 00:39:32,680 --> 00:39:33,420 Esta línea? 785 00:39:33,420 --> 00:39:33,750 >> AUDIENCIA: Si. 786 00:39:33,750 --> 00:39:35,745 Hacer curr equivale curr-> siguiente. 787 00:39:35,745 --> 00:39:39,690 788 00:39:39,690 --> 00:39:43,360 >> JASON HIRSCHHORN: Así que eso es correcto porque la corriente es una 789 00:39:43,360 --> 00:39:45,220 puntero a un nodo. 790 00:39:45,220 --> 00:39:48,550 Y queremos que apunte a la siguiente nodo de lo que está recibiendo en la actualidad 791 00:39:48,550 --> 00:39:49,930 señalado. 792 00:39:49,930 --> 00:39:54,410 Curr en sí tiene un siguiente. 793 00:39:54,410 --> 00:39:58,620 Pero si tuviéramos que actualizar curr.next, nos sería la actualización de la nota real 794 00:39:58,620 --> 00:40:01,430 en sí, no donde esta puntero señalaba. 795 00:40:01,430 --> 00:40:02,680 ¿Qué pasa con esta línea, sin embargo. 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 >> AUDIENCIA: Anterior-> siguiente es igual curr. 799 00:40:09,590 --> 00:40:12,500 800 00:40:12,500 --> 00:40:19,440 >> JASON HIRSCHHORN: Así que de nuevo, en caso anterior es un puntero a un nodo, anterior-> siguiente es la 801 00:40:19,440 --> 00:40:23,020 puntero actual en el nodo. 802 00:40:23,020 --> 00:40:27,190 Así que esta sería la actualización de una puntero en un nodo para curr. 803 00:40:27,190 --> 00:40:28,570 No queremos poner al día un puntero en un nodo. 804 00:40:28,570 --> 00:40:30,570 Queremos poner al día anterior. 805 00:40:30,570 --> 00:40:31,850 Entonces, ¿cómo hacemos eso? 806 00:40:31,850 --> 00:40:34,250 >> AUDIENCIA: Sólo se prev. 807 00:40:34,250 --> 00:40:34,565 >> JASON HIRSCHHORN: Así es. 808 00:40:34,565 --> 00:40:35,560 Anterior es un puntero a un nodo. 809 00:40:35,560 --> 00:40:38,750 Ahora vamos a cambiar a un nuevo puntero a un nodo. 810 00:40:38,750 --> 00:40:40,830 Aceptar Movámonos hacia abajo. 811 00:40:40,830 --> 00:40:41,940 Finalmente, esta última condición. 812 00:40:41,940 --> 00:40:44,896 Jeff, ¿qué hacemos aquí? 813 00:40:44,896 --> 00:40:47,515 >> AUDIENCIA: Si el valor es igual a curr-> n. 814 00:40:47,515 --> 00:40:51,030 815 00:40:51,030 --> 00:40:51,300 >> JASON HIRSCHHORN: Lo siento. 816 00:40:51,300 --> 00:40:52,372 ¡Oh Dios mío. 817 00:40:52,372 --> 00:40:54,330 ¿Qué? 818 00:40:54,330 --> 00:40:55,580 Valor == curr-> n. 819 00:40:55,580 --> 00:41:01,050 820 00:41:01,050 --> 00:41:02,300 ¿Qué hacemos? 821 00:41:02,300 --> 00:41:04,760 822 00:41:04,760 --> 00:41:10,950 >> AUDIENCIA: Usted sería liberar a nuestros new_node, y luego te volverías falsa. 823 00:41:10,950 --> 00:41:21,410 824 00:41:21,410 --> 00:41:23,460 >> JASON HIRSCHHORN: Esto es lo que que hemos escrito hasta ahora. 825 00:41:23,460 --> 00:41:25,710 ¿Alguien tiene algo añadir antes de que hagamos? 826 00:41:25,710 --> 00:41:35,460 827 00:41:35,460 --> 00:41:35,710 Aceptar. 828 00:41:35,710 --> 00:41:36,960 Vamos a intentarlo. 829 00:41:36,960 --> 00:41:44,180 830 00:41:44,180 --> 00:41:46,110 El control puede llegar a la final de una función no nula. 831 00:41:46,110 --> 00:41:48,310 Avi, ¿qué está pasando? 832 00:41:48,310 --> 00:41:51,380 >> AUDIENCIA: ¿Se supone que poner de retorno cierto fuera del bucle while? 833 00:41:51,380 --> 00:41:53,900 834 00:41:53,900 --> 00:41:54,400 >> JASON HIRSCHHORN: No sé. 835 00:41:54,400 --> 00:41:54,780 ¿Me quieres? 836 00:41:54,780 --> 00:41:55,520 >> AUDIENCIA: No importa. 837 00:41:55,520 --> 00:41:56,350 No. 838 00:41:56,350 --> 00:41:57,180 >> JASON HIRSCHHORN: Akshar? 839 00:41:57,180 --> 00:41:59,460 >> AUDIENCIA: Creo que la intención de poner return false al final 840 00:41:59,460 --> 00:42:02,230 del bucle while. 841 00:42:02,230 --> 00:42:03,270 >> JASON HIRSCHHORN: Entonces, ¿dónde Qué quieres que vaya? 842 00:42:03,270 --> 00:42:05,270 >> AUDIENCIA: Al igual que fuera del bucle while. 843 00:42:05,270 --> 00:42:08,800 Así que si sale del bucle while que los medios que ha llegado al final y 844 00:42:08,800 --> 00:42:09,980 no ha pasado nada. 845 00:42:09,980 --> 00:42:10,410 >> JASON HIRSCHHORN: OK. 846 00:42:10,410 --> 00:42:12,340 Así que, ¿qué hacemos aquí? 847 00:42:12,340 --> 00:42:13,702 >> AUDIENCIA: Usted vuelve falsa allí también. 848 00:42:13,702 --> 00:42:15,040 >> JASON HIRSCHHORN: Oh, hacerlo en ambos lugares? 849 00:42:15,040 --> 00:42:15,650 >> AUDIENCIA: Si. 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 ¿Hay que ir? 853 00:42:26,160 --> 00:42:26,980 ¡Oh Dios mío. 854 00:42:26,980 --> 00:42:27,290 Lo siento. 855 00:42:27,290 --> 00:42:28,480 Pido disculpas por la pantalla. 856 00:42:28,480 --> 00:42:30,530 Es un poco flipando en nosotros. 857 00:42:30,530 --> 00:42:31,520 Así que debes elegir una opción. 858 00:42:31,520 --> 00:42:35,260 Cero, por el código, se cierra el programa. 859 00:42:35,260 --> 00:42:36,700 Uno inserta algo. 860 00:42:36,700 --> 00:42:37,990 Vamos a insertar tres. 861 00:42:37,990 --> 00:42:42,900 862 00:42:42,900 --> 00:42:45,380 El inserto no tuvo éxito. 863 00:42:45,380 --> 00:42:46,500 Voy a imprimir. 864 00:42:46,500 --> 00:42:48,050 Yo no tengo nada. 865 00:42:48,050 --> 00:42:48,450 Aceptar. 866 00:42:48,450 --> 00:42:50,250 Tal vez eso era sólo una casualidad. 867 00:42:50,250 --> 00:42:52,810 Inserte uno. 868 00:42:52,810 --> 00:42:55,770 No éxito. 869 00:42:55,770 --> 00:42:57,470 Aceptar. 870 00:42:57,470 --> 00:43:02,400 Vamos a ejecutar a través de GDB muy rápido para comprobar lo que está pasando. 871 00:43:02,400 --> 00:43:06,055 >> Recuerde gdb. / El nombre de su programa nos mete en el BGF. 872 00:43:06,055 --> 00:43:07,610 ¿Es que una gran cantidad de manejar? 873 00:43:07,610 --> 00:43:08,560 El intermitente? 874 00:43:08,560 --> 00:43:10,400 Probablemente. 875 00:43:10,400 --> 00:43:12,760 Cierra los ojos y tomar un poco de profundidad respiraciones si te cansas 876 00:43:12,760 --> 00:43:13,580 de ver las cosas. 877 00:43:13,580 --> 00:43:14,200 Estoy en el BGF. 878 00:43:14,200 --> 00:43:15,830 ¿Qué es lo primero que hago en GDB? 879 00:43:15,830 --> 00:43:17,050 Tenemos que averiguar ¿qué está pasando aquí. 880 00:43:17,050 --> 00:43:17,310 Vamos a ver. 881 00:43:17,310 --> 00:43:21,650 Tenemos seis minutos de la figura lo que está pasando. 882 00:43:21,650 --> 00:43:22,900 Romper principal. 883 00:43:22,900 --> 00:43:25,950 884 00:43:25,950 --> 00:43:28,130 Y entonces, ¿qué hago? 885 00:43:28,130 --> 00:43:29,180 Carlos? 886 00:43:29,180 --> 00:43:31,060 Ejecutar. 887 00:43:31,060 --> 00:43:32,250 Aceptar. 888 00:43:32,250 --> 00:43:34,160 Vamos a escoger una opción. 889 00:43:34,160 --> 00:43:36,330 ¿Y qué tiene N hacer? 890 00:43:36,330 --> 00:43:38,480 Siguiente. 891 00:43:38,480 --> 00:43:38,950 Sí. 892 00:43:38,950 --> 00:43:39,740 >> AUDIENCIA: ¿No lo dices - 893 00:43:39,740 --> 00:43:45,230 qué no me dijiste que la cabeza, que era inicializa en null al principio. 894 00:43:45,230 --> 00:43:47,140 Pero pensé que habías dicho que estaba bien. 895 00:43:47,140 --> 00:43:50,040 896 00:43:50,040 --> 00:43:52,640 >> JASON HIRSCHHORN: Vamos - vamos a ver en GDB, y luego vamos a volver. 897 00:43:52,640 --> 00:43:54,910 Pero parece que usted ya tiene algunas ideas sobre lo que está pasando. 898 00:43:54,910 --> 00:43:58,340 Así que queremos insertar algo. 899 00:43:58,340 --> 00:43:59,390 Aceptar. 900 00:43:59,390 --> 00:44:00,150 Hemos insertar. 901 00:44:00,150 --> 00:44:00,770 Por favor ingrese un int. 902 00:44:00,770 --> 00:44:01,990 Nosotros insertaremos tres. 903 00:44:01,990 --> 00:44:03,000 Y entonces estoy en esta línea. 904 00:44:03,000 --> 00:44:07,030 ¿Cómo hago para iniciar la depuración la inserción de la función conocida? 905 00:44:07,030 --> 00:44:08,280 ¡Oh Dios mío. 906 00:44:08,280 --> 00:44:10,990 907 00:44:10,990 --> 00:44:12,240 Eso es un montón. 908 00:44:12,240 --> 00:44:14,372 909 00:44:14,372 --> 00:44:16,445 ¿Eso enloqueciendo mucho? 910 00:44:16,445 --> 00:44:19,696 911 00:44:19,696 --> 00:44:21,680 >> AUDIENCIA: Oh, murió. 912 00:44:21,680 --> 00:44:22,930 >> JASON HIRSCHHORN: Acabo lo sacó. 913 00:44:22,930 --> 00:44:27,364 914 00:44:27,364 --> 00:44:28,310 Aceptar. 915 00:44:28,310 --> 00:44:29,560 >> AUDIENCIA: Tal vez sea el otro extremo del cable. 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 Así que la conclusión - 919 00:44:42,330 --> 00:44:43,470 ¿qué le dijiste? 920 00:44:43,470 --> 00:44:46,040 >> AUDIENCIA: Dije que la ironía de la técnica dificultades en esta clase. 921 00:44:46,040 --> 00:44:46,410 >> JASON HIRSCHHORN: Lo sé. 922 00:44:46,410 --> 00:44:48,660 Si tan sólo tuviera el control sobre esa parte. 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 Eso suena muy bien. 926 00:44:55,400 --> 00:44:58,680 ¿Por qué no empezar a pensar en los chicos lo que podríamos haber hecho mal, 927 00:44:58,680 --> 00:45:01,140 y vamos a estar de vuelta en 90 segundos. 928 00:45:01,140 --> 00:46:18,160 929 00:46:18,160 --> 00:46:23,010 >> Avica, voy a preguntarle cómo ir insert_node interior para depurarlo. 930 00:46:23,010 --> 00:46:28,940 931 00:46:28,940 --> 00:46:31,460 Así que aquí es donde nos dejó la última vez. 932 00:46:31,460 --> 00:46:35,110 ¿Cómo me voy adentro insert_node, Avica, examinar lo que está pasando? 933 00:46:35,110 --> 00:46:36,360 ¿Qué comando GDB? 934 00:46:36,360 --> 00:46:41,050 935 00:46:41,050 --> 00:46:42,390 Pausa no me llevaría en su interior. 936 00:46:42,390 --> 00:46:46,200 937 00:46:46,200 --> 00:46:47,130 ¿Lo sabe Marquise? 938 00:46:47,130 --> 00:46:48,240 >> AUDIENCIA: ¿Qué? 939 00:46:48,240 --> 00:46:51,780 >> JASON HIRSCHHORN: ¿Qué comando GDB Yo uso para ir dentro de esta función? 940 00:46:51,780 --> 00:46:52,070 >> AUDIENCIA: Step? 941 00:46:52,070 --> 00:46:55,140 >> JASON HIRSCHHORN: Paso a través de S. Eso me lleva dentro. 942 00:46:55,140 --> 00:46:55,476 Aceptar. 943 00:46:55,476 --> 00:46:58,040 New_node mallocing algo de espacio. 944 00:46:58,040 --> 00:46:59,120 Todo eso parece que va. 945 00:46:59,120 --> 00:47:00,370 Vamos a examinar new_node. 946 00:47:00,370 --> 00:47:03,270 947 00:47:03,270 --> 00:47:05,410 Se puso un poco de dirección de memoria. 948 00:47:05,410 --> 00:47:07,440 Vamos a ver - 949 00:47:07,440 --> 00:47:08,500 eso es todo lo correcto. 950 00:47:08,500 --> 00:47:12,220 Así que todo lo que aquí parece estar funcionando correctamente. 951 00:47:12,220 --> 00:47:14,530 >> AUDIENCIA: ¿Cuál es la diferencia entre P y la pantalla? 952 00:47:14,530 --> 00:47:16,160 >> JASON HIRSCHHORN: P corresponde a la impresión. 953 00:47:16,160 --> 00:47:19,310 Y por lo que se está preguntando cuál es la diferencia entre eso y esto? 954 00:47:19,310 --> 00:47:22,330 En este caso, nada. 955 00:47:22,330 --> 00:47:26,960 Pero generalmente hay algunas diferencias. 956 00:47:26,960 --> 00:47:28,220 Y usted debe buscar en el manual de GDB. 957 00:47:28,220 --> 00:47:29,560 Pero en este caso, nada. 958 00:47:29,560 --> 00:47:31,460 Tenemos la tendencia a utilizar la impresión, sin embargo, porque nosotros no tenemos que hacer mucho más que 959 00:47:31,460 --> 00:47:33,960 imprimir un solo valor. 960 00:47:33,960 --> 00:47:34,640 >> Aceptar. 961 00:47:34,640 --> 00:47:40,300 Así que estamos en la línea 80 de nuestro código, estableciendo nodo * curr igual a lista. 962 00:47:40,300 --> 00:47:42,500 Vamos a imprimimos curr. 963 00:47:42,500 --> 00:47:45,260 964 00:47:45,260 --> 00:47:46,840 Es igual a la lista. 965 00:47:46,840 --> 00:47:48,850 Sweet. 966 00:47:48,850 --> 00:47:49,340 Espere. 967 00:47:49,340 --> 00:47:50,590 Es igual a algo. 968 00:47:50,590 --> 00:47:53,680 969 00:47:53,680 --> 00:47:56,190 Eso no me parece correcto. 970 00:47:56,190 --> 00:47:56,840 Eso es. 971 00:47:56,840 --> 00:47:59,470 Es porque en GDB, bien, si que es la línea que está en él 972 00:47:59,470 --> 00:48:00,330 aún no se ha ejecutado. 973 00:48:00,330 --> 00:48:03,100 Así que hay que escribir en realidad siguiente para ejecutar la línea de 974 00:48:03,100 --> 00:48:05,230 antes de ver sus resultados. 975 00:48:05,230 --> 00:48:06,680 Así que aquí estamos. 976 00:48:06,680 --> 00:48:09,490 Simplemente ejecuta esta línea, anterior equivale a nula. 977 00:48:09,490 --> 00:48:13,590 Así que de nuevo, si imprimimos anterior no vamos a ver nada raro. 978 00:48:13,590 --> 00:48:18,680 Pero si realmente ejecutan a que línea, entonces veremos 979 00:48:18,680 --> 00:48:20,380 que esa línea funcionó. 980 00:48:20,380 --> 00:48:21,060 >> Así que tenemos curr. 981 00:48:21,060 --> 00:48:23,180 Esos son los dos buenos. 982 00:48:23,180 --> 00:48:24,010 ¿Cierto? 983 00:48:24,010 --> 00:48:28,130 Ahora estamos en esta línea aquí. 984 00:48:28,130 --> 00:48:29,310 Mientras curr no es igual a nulo. 985 00:48:29,310 --> 00:48:31,110 Bueno, lo que hace curr iguales? 986 00:48:31,110 --> 00:48:32,450 Acabamos de ver que igualó nulo. 987 00:48:32,450 --> 00:48:33,210 Imprimimos a cabo. 988 00:48:33,210 --> 00:48:35,110 Voy a imprimir hacia fuera otra vez. 989 00:48:35,110 --> 00:48:36,720 Así es que mientras que bucle va a ejecutar? 990 00:48:36,720 --> 00:48:37,270 >> AUDIENCIA: No. 991 00:48:37,270 --> 00:48:39,790 >> JASON HIRSCHHORN: Así que cuando he escrito que línea, verá que saltó todo el camino 992 00:48:39,790 --> 00:48:41,390 hasta la parte inferior, devolverá false. 993 00:48:41,390 --> 00:48:44,520 Y luego vamos a devolver false y volver a nuestro programa y 994 00:48:44,520 --> 00:48:48,020 finalmente, imprimir, como vimos, el inserto no tuvo éxito. 995 00:48:48,020 --> 00:48:51,010 Por lo tanto, nadie tiene alguna idea sobre lo que que tenemos que hacer para arreglar esto? 996 00:48:51,010 --> 00:48:54,200 997 00:48:54,200 --> 00:48:57,570 Voy a esperar hasta que vea un par de manos suben. 998 00:48:57,570 --> 00:48:58,830 No ejecutamos esto. 999 00:48:58,830 --> 00:49:01,660 Tenga en cuenta que esta fue la primera Lo que estábamos haciendo. 1000 00:49:01,660 --> 00:49:02,430 Yo no voy a hacer un par. 1001 00:49:02,430 --> 00:49:03,670 Voy a hacer algunos. 1002 00:49:03,670 --> 00:49:04,830 Debido a que un par significa dos. 1003 00:49:04,830 --> 00:49:07,620 Voy a esperar por más de dos. 1004 00:49:07,620 --> 00:49:10,690 >> La primera inserción, corr, por defecto es igual a nulo. 1005 00:49:10,690 --> 00:49:14,050 Y este ciclo sólo se ejecuta si curr no es nulo. 1006 00:49:14,050 --> 00:49:18,740 Entonces, ¿cómo puedo solucionar esto? 1007 00:49:18,740 --> 00:49:19,990 Veo tres manos. 1008 00:49:19,990 --> 00:49:28,490 1009 00:49:28,490 --> 00:49:29,780 Voy a esperar por más de tres. 1010 00:49:29,780 --> 00:49:33,460 1011 00:49:33,460 --> 00:49:35,940 Marcus, ¿qué te parece? 1012 00:49:35,940 --> 00:49:37,730 >> AUDIENCIA: Bueno, si usted lo necesita ejecutar más de una vez, sólo 1013 00:49:37,730 --> 00:49:39,948 cambiarlo a un bucle do-while. 1014 00:49:39,948 --> 00:49:41,250 >> JASON HIRSCHHORN: OK. 1015 00:49:41,250 --> 00:49:44,240 ¿Será que resolver nuestro problema, sin embargo? 1016 00:49:44,240 --> 00:49:47,750 >> AUDIENCIA: En este caso no, porque de el hecho de que la lista está vacía. 1017 00:49:47,750 --> 00:49:52,150 Así que es probable que sólo necesita añadir una declaración de que si se sale del bucle 1018 00:49:52,150 --> 00:49:55,312 entonces usted tiene que estar al final de la la lista, momento en el que usted 1019 00:49:55,312 --> 00:49:56,562 sólo puede insertarlo. 1020 00:49:56,562 --> 00:49:58,920 1021 00:49:58,920 --> 00:49:59,680 >> JASON HIRSCHHORN: eso me gusta. 1022 00:49:59,680 --> 00:50:00,500 Eso tiene sentido. 1023 00:50:00,500 --> 00:50:03,390 Si se sale del bucle - 1024 00:50:03,390 --> 00:50:04,800 porque va a devolver false aquí. 1025 00:50:04,800 --> 00:50:08,220 Así que si se sale del bucle, entonces estamos en Al final de la lista, o tal vez el 1026 00:50:08,220 --> 00:50:10,690 inicio de una lista si no hay nada en , lo que es lo mismo que el final. 1027 00:50:10,690 --> 00:50:12,770 Así que ahora queremos insertar algo aquí. 1028 00:50:12,770 --> 00:50:17,380 Entonces, ¿cómo ese código mira, Marcus? 1029 00:50:17,380 --> 00:50:21,600 >> AUDIENCIA: Si ya tienes el nodo malloced, usted podría decir 1030 00:50:21,600 --> 00:50:25,400 new_node-> siguiente es igual a nula porque tiene que ser al final. 1031 00:50:25,400 --> 00:50:27,510 O new_node-> siguiente es igual a nulo. 1032 00:50:27,510 --> 00:50:27,765 >> JASON HIRSCHHORN: OK. 1033 00:50:27,765 --> 00:50:28,190 Lo siento. 1034 00:50:28,190 --> 00:50:35,760 New_node-> siguiente es igual a nula porque estamos en el final. 1035 00:50:35,760 --> 00:50:36,460 Eso no lo puso pulg 1036 00:50:36,460 --> 00:50:37,710 ¿Cómo nos ponemos en la lista? 1037 00:50:37,710 --> 00:50:46,130 1038 00:50:46,130 --> 00:50:46,460 Derecha. 1039 00:50:46,460 --> 00:50:47,750 Eso es sólo la creación es igual a. 1040 00:50:47,750 --> 00:50:50,940 No, ¿cómo en realidad lo puso en la lista? 1041 00:50:50,940 --> 00:50:54,170 Lo que apunta a la final de la lista? 1042 00:50:54,170 --> 00:50:56,090 >> AUDIENCIA: Head. 1043 00:50:56,090 --> 00:50:57,566 >> JASON HIRSCHHORN: ¿Lo sientes? 1044 00:50:57,566 --> 00:50:59,440 >> AUDIENCIA: Head está apuntando al final de la lista. 1045 00:50:59,440 --> 00:51:01,480 >> JASON HIRSCHHORN: Si no hay nada en la lista, la cabeza está apuntando a la 1046 00:51:01,480 --> 00:51:04,170 final de la lista. 1047 00:51:04,170 --> 00:51:06,920 Así que eso funcionará para la primera inserción. 1048 00:51:06,920 --> 00:51:09,810 ¿Qué pasa si hay un par las cosas en la lista? 1049 00:51:09,810 --> 00:51:12,470 Que no queremos establecer cabeza igual a new_node. 1050 00:51:12,470 --> 00:51:13,790 ¿Qué es lo que queremos hacer allí? 1051 00:51:13,790 --> 00:51:15,610 ¿Sí? 1052 00:51:15,610 --> 00:51:16,860 Probablemente anterior. 1053 00:51:16,860 --> 00:51:23,560 1054 00:51:23,560 --> 00:51:24,810 ¿Funcionará? 1055 00:51:24,810 --> 00:51:28,950 1056 00:51:28,950 --> 00:51:33,050 Recordemos que anterior es sólo un puntero a un nodo. 1057 00:51:33,050 --> 00:51:34,770 Y anterior es una variable local. 1058 00:51:34,770 --> 00:51:38,080 Así que esta línea creará una variable local, anterior, igual o 1059 00:51:38,080 --> 00:51:39,380 señalando a este nuevo nodo. 1060 00:51:39,380 --> 00:51:41,500 Eso no va a poner realmente se en la lista, sin embargo. 1061 00:51:41,500 --> 00:51:44,330 ¿Cómo nos ponemos en nuestra lista? 1062 00:51:44,330 --> 00:51:45,620 Akchar? 1063 00:51:45,620 --> 00:51:46,870 >> AUDIENCIA: Creo que hacer actual-> siguiente. 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-> siguiente. 1067 00:51:54,010 --> 00:51:58,768 Así que de nuevo, la única razón por la que estamos abajo aquí es lo que hace de corriente igual? 1068 00:51:58,768 --> 00:51:59,760 >> AUDIENCIA: igual a nulo. 1069 00:51:59,760 --> 00:52:01,790 >> JASON HIRSCHHORN: Y así lo que pasa si lo hacemos nula-> next? 1070 00:52:01,790 --> 00:52:02,810 ¿Qué va a conseguir? 1071 00:52:02,810 --> 00:52:04,060 Conseguiremos un fallo de segmentación. 1072 00:52:04,060 --> 00:52:06,600 1073 00:52:06,600 --> 00:52:08,880 >> AUDIENCIA: Do curr equivale a nula. 1074 00:52:08,880 --> 00:52:10,760 >> JASON HIRSCHHORN: Eso es lo mismo como anterior, sin embargo, porque no hay 1075 00:52:10,760 --> 00:52:12,820 una variable local que estamos estableciendo igual a este nuevo nodo. 1076 00:52:12,820 --> 00:52:16,680 1077 00:52:16,680 --> 00:52:20,920 Volvamos a nuestra imagen de insertar algo. 1078 00:52:20,920 --> 00:52:25,500 Digamos que estamos insertando al final de la lista, por lo que aquí. 1079 00:52:25,500 --> 00:52:30,010 Tenemos un puntero actual que es apuntando a null y un punto anterior 1080 00:52:30,010 --> 00:52:32,800 eso apunta a 8. 1081 00:52:32,800 --> 00:52:35,330 Entonces, ¿qué tenemos que actualizar, Avi? 1082 00:52:35,330 --> 00:52:36,680 >> AUDIENCIA: Anterior-> siguiente? 1083 00:52:36,680 --> 00:52:41,980 >> JASON HIRSCHHORN: Anterior-> siguiente es lo que queremos poner al día a causa de que 1084 00:52:41,980 --> 00:52:44,960 en realidad se inserta en el final de la lista. 1085 00:52:44,960 --> 00:52:47,220 Todavía tenemos un bicho, sin embargo, que vamos a ejecutar en. 1086 00:52:47,220 --> 00:52:50,090 ¿Qué es ese bicho? 1087 00:52:50,090 --> 00:52:50,790 ¿Sí? 1088 00:52:50,790 --> 00:52:53,860 >> AUDIENCIA: Se va a volver falsa en este caso? 1089 00:52:53,860 --> 00:52:56,380 >> JASON HIRSCHHORN: Oh, es que se va a devolver false. 1090 00:52:56,380 --> 00:52:57,430 Pero hay otro bug. 1091 00:52:57,430 --> 00:52:58,930 Así que tendremos que poner a cambio verdadero. 1092 00:52:58,930 --> 00:53:01,370 >> AUDIENCIA: Lo anterior sigue igual nulo en la parte superior de la lista? 1093 00:53:01,370 --> 00:53:03,645 >> JASON HIRSCHHORN: Todavía Así anterior es igual a nulo desde el principio. 1094 00:53:03,645 --> 00:53:07,480 1095 00:53:07,480 --> 00:53:10,440 Entonces, ¿cómo podemos superar eso? 1096 00:53:10,440 --> 00:53:10,950 ¿Sí? 1097 00:53:10,950 --> 00:53:15,280 >> AUDIENCIA: Creo que se puede hacer una verificación antes de que el bucle while para ver si es 1098 00:53:15,280 --> 00:53:16,610 una lista vacía. 1099 00:53:16,610 --> 00:53:17,000 >> JASON HIRSCHHORN: OK. 1100 00:53:17,000 --> 00:53:17,710 Así que vamos a ir aquí. 1101 00:53:17,710 --> 00:53:18,530 Haga una revisión. 1102 00:53:18,530 --> 00:53:19,380 Si - 1103 00:53:19,380 --> 00:53:20,770 >> AUDIENCIA: Así que si la cabeza es igual a es igual a nulo. 1104 00:53:20,770 --> 00:53:24,300 1105 00:53:24,300 --> 00:53:26,320 >> JASON HIRSCHHORN: Si la cabeza es igual a es igual a nula - 1106 00:53:26,320 --> 00:53:27,790 que nos dirá si se trata de una lista vacía. 1107 00:53:27,790 --> 00:53:31,090 >> AUDIENCIA: Y entonces usted hacer la cabeza es igual a nuevo. 1108 00:53:31,090 --> 00:53:34,740 >> JASON HIRSCHHORN: Head iguales new_node? 1109 00:53:34,740 --> 00:53:35,730 Y ¿qué más tenemos que hacer? 1110 00:53:35,730 --> 00:53:37,020 >> AUDIENCIA: Y luego puede volver realidad. 1111 00:53:37,020 --> 00:53:37,535 >> JASON HIRSCHHORN: No del todo. 1112 00:53:37,535 --> 00:53:38,785 Nos falta un paso. 1113 00:53:38,785 --> 00:53:41,590 1114 00:53:41,590 --> 00:53:43,710 >> AUDIENCIA: New_node siguiente tiene que apuntar a null. 1115 00:53:43,710 --> 00:53:44,570 >> JASON HIRSCHHORN: Exactamente, Alden. 1116 00:53:44,570 --> 00:53:46,600 Y entonces podemos devolver true. 1117 00:53:46,600 --> 00:53:47,560 Aceptar. 1118 00:53:47,560 --> 00:53:51,630 Pero sigue siendo una buena idea de hacer las cosas al final de la lista, ¿no? 1119 00:53:51,630 --> 00:53:51,950 Está bien. 1120 00:53:51,950 --> 00:53:54,450 Todavía podríamos conseguir realmente al final de la lista. 1121 00:53:54,450 --> 00:53:57,870 Así es este código bien si estamos en el final de la lista y hay algunos 1122 00:53:57,870 --> 00:53:59,120 las cosas en la lista? 1123 00:53:59,120 --> 00:54:01,830 1124 00:54:01,830 --> 00:54:02,040 ¿Cierto? 1125 00:54:02,040 --> 00:54:03,540 Debido a que todavía tenemos idea de Marcus. 1126 00:54:03,540 --> 00:54:06,870 Podemos salir de este bucle, porque estamos en el final de la lista. 1127 00:54:06,870 --> 00:54:09,308 Entonces, ¿todavía queremos este código aquí abajo? 1128 00:54:09,308 --> 00:54:10,520 >> AUDIENCIA: Si. 1129 00:54:10,520 --> 00:54:11,000 >> JASON HIRSCHHORN: Si. 1130 00:54:11,000 --> 00:54:14,190 Y ¿qué es lo que tenemos que cambiar esto? 1131 00:54:14,190 --> 00:54:15,440 Verdadero. 1132 00:54:15,440 --> 00:54:19,580 1133 00:54:19,580 --> 00:54:21,640 ¿Suena bien a todo el mundo hasta el momento? 1134 00:54:21,640 --> 00:54:22,420 ¿Alguien tiene alguna - 1135 00:54:22,420 --> 00:54:23,480 Avi, ¿tienes algo que añadir? 1136 00:54:23,480 --> 00:54:23,920 >> AUDIENCIA: No. 1137 00:54:23,920 --> 00:54:25,276 >> JASON HIRSCHHORN: OK. 1138 00:54:25,276 --> 00:54:27,010 Así que hemos hecho un par de cambios. 1139 00:54:27,010 --> 00:54:29,540 Hemos hecho esta comprobación antes de que fuimos para una lista vacía. 1140 00:54:29,540 --> 00:54:31,790 Así que nos hemos ocupado de una lista vacía. 1141 00:54:31,790 --> 00:54:35,500 Y aquí nos ocupamos de la inserción algo al final de la lista. 1142 00:54:35,500 --> 00:54:38,930 Así que parece que esta toma de bucle while cuidado de las cosas en el medio, 1143 00:54:38,930 --> 00:54:41,920 en algún lugar de la lista si hay son las cosas en la lista. 1144 00:54:41,920 --> 00:54:42,280 >> Aceptar. 1145 00:54:42,280 --> 00:54:44,310 Corramos este programa de nuevo. 1146 00:54:44,310 --> 00:54:50,170 1147 00:54:50,170 --> 00:54:50,755 No éxito. 1148 00:54:50,755 --> 00:54:52,190 >> AUDIENCIA: Usted no lo hacen. 1149 00:54:52,190 --> 00:54:53,940 >> JASON HIRSCHHORN: Oh, Yo no lo hice. 1150 00:54:53,940 --> 00:54:56,250 Buen punto, Michael. 1151 00:54:56,250 --> 00:54:57,500 Vamos a añadir una marca vinculada. 1152 00:54:57,500 --> 00:55:01,590 1153 00:55:01,590 --> 00:55:04,830 Línea 87 hay un error. 1154 00:55:04,830 --> 00:55:05,420 Línea 87. 1155 00:55:05,420 --> 00:55:06,600 Alden, esta fue la línea que me diste. 1156 00:55:06,600 --> 00:55:08,962 ¿Qué pasa? 1157 00:55:08,962 --> 00:55:10,710 >> AUDIENCIA: Tiene que ser null. 1158 00:55:10,710 --> 00:55:11,000 >> JASON HIRSCHHORN: Excelente. 1159 00:55:11,000 --> 00:55:11,630 Exactamente derecha. 1160 00:55:11,630 --> 00:55:13,290 Debe ser nulo. 1161 00:55:13,290 --> 00:55:15,210 Vamos a hacer de nuevo. 1162 00:55:15,210 --> 00:55:17,220 Compilar. 1163 00:55:17,220 --> 00:55:17,890 Aceptar. 1164 00:55:17,890 --> 00:55:19,400 Vamos a insertar tres. 1165 00:55:19,400 --> 00:55:20,570 El inserto fue exitosa. 1166 00:55:20,570 --> 00:55:21,660 Vamos a imprimir hacia fuera. 1167 00:55:21,660 --> 00:55:23,590 Oh, si tan sólo pudiéramos comprobar. 1168 00:55:23,590 --> 00:55:25,500 Pero no hemos hecho lo imprimir función todavía. 1169 00:55:25,500 --> 00:55:27,840 Nos adentraremos en otra cosa. 1170 00:55:27,840 --> 00:55:29,090 ¿Qué debemos entrar? 1171 00:55:29,090 --> 00:55:31,120 1172 00:55:31,120 --> 00:55:31,940 >> AUDIENCIA: Siete. 1173 00:55:31,940 --> 00:55:33,340 >> JASON HIRSCHHORN: Seven? 1174 00:55:33,340 --> 00:55:34,590 >> AUDIENCIA: Si. 1175 00:55:34,590 --> 00:55:38,680 1176 00:55:38,680 --> 00:55:39,780 >> JASON HIRSCHHORN: Tenemos una falla seg. 1177 00:55:39,780 --> 00:55:43,760 Así que nos dieron una, pero claramente no puede conseguir dos. 1178 00:55:43,760 --> 00:55:45,690 Es 05:07. 1179 00:55:45,690 --> 00:55:48,370 Así que podemos depurar este durante tres minutos. 1180 00:55:48,370 --> 00:55:51,240 Pero yo voy a dejarnos aquí y pasar a tablas hash. 1181 00:55:51,240 --> 00:55:54,290 Pero, de nuevo, las respuestas de este código Voy a enviar por correo electrónico a usted en un momento. 1182 00:55:54,290 --> 00:55:55,440 Estamos muy cerca de ella. 1183 00:55:55,440 --> 00:55:58,300 Yo le animo a descubrir ¿qué está pasando aquí y arreglarlo. 1184 00:55:58,300 --> 00:56:02,400 Así que voy a por correo electrónico este código como así más la solución - 1185 00:56:02,400 --> 00:56:03,670 probablemente la solución más adelante. 1186 00:56:03,670 --> 00:56:05,110 En primer lugar este código. 1187 00:56:05,110 --> 00:56:08,290 >> La otra cosa que quiero hacer antes de que final es que no hemos liberado a nada. 1188 00:56:08,290 --> 00:56:10,370 Así que quiero que le muestre lo valgrind parece. 1189 00:56:10,370 --> 00:56:14,310 Si corremos límites valgrind en nuestro programa. / enlazado. 1190 00:56:14,310 --> 00:56:22,540 Una vez más, de acuerdo con esta diapositiva, nos debe ejecutar valgrind con algún tipo de 1191 00:56:22,540 --> 00:56:26,410 opción, en este caso - Fuga-check = full. 1192 00:56:26,410 --> 00:56:27,660 Así que vamos a escribir valgrind - Fuga-check = full. 1193 00:56:27,660 --> 00:56:31,910 1194 00:56:31,910 --> 00:56:35,080 Así que esto va a funcionar valgrind en nuestro programa. 1195 00:56:35,080 --> 00:56:37,000 Y ahora el programa realmente funciona. 1196 00:56:37,000 --> 00:56:40,190 Así que vamos a ejecutarlo como antes, poner algo pulg 1197 00:56:40,190 --> 00:56:40,830 Me voy a poner en tres. 1198 00:56:40,830 --> 00:56:41,790 Eso funciona. 1199 00:56:41,790 --> 00:56:43,202 No voy a tratar de poner en algo más porque vamos a 1200 00:56:43,202 --> 00:56:44,710 conseguir un falso seg en ese caso. 1201 00:56:44,710 --> 00:56:46,700 Así que sólo voy a dejar de fumar. 1202 00:56:46,700 --> 00:56:50,160 >> Y ahora que se ve aquí abajo fugas y resumen montón. 1203 00:56:50,160 --> 00:56:52,310 Estas son las cosas buenas que desea revisar. 1204 00:56:52,310 --> 00:56:56,780 Así que el resumen del montón - dice, en uso en la salida - ocho bytes en un bloque. 1205 00:56:56,780 --> 00:56:58,370 Ese bloque es el nodo que malloced. 1206 00:56:58,370 --> 00:57:02,230 Michael, dijo antes de un nodo es de ocho picaduras porque tiene el número entero 1207 00:57:02,230 --> 00:57:02,680 y el puntero. 1208 00:57:02,680 --> 00:57:04,550 Así que ese es nuestro nodo. 1209 00:57:04,550 --> 00:57:08,170 Y luego dice que usamos malloc siete veces y nos liberamos 1210 00:57:08,170 --> 00:57:08,940 algo en seis ocasiones. 1211 00:57:08,940 --> 00:57:13,680 Pero nunca se llama libre, así que no tengo idea de lo que está hablando. 1212 00:57:13,680 --> 00:57:18,490 >> Pero baste decir que cuando su programa se ejecuta, malloc se está llamando 1213 00:57:18,490 --> 00:57:20,330 en algunos otros lugares que no es necesario preocuparse. 1214 00:57:20,330 --> 00:57:22,460 Así malloc probablemente fue llamado en algunos lugares. 1215 00:57:22,460 --> 00:57:24,480 Nosotros no tenemos que preocuparnos dónde. 1216 00:57:24,480 --> 00:57:26,240 Pero esto es realmente nosotros. 1217 00:57:26,240 --> 00:57:27,380 Esta primera línea es nosotros. 1218 00:57:27,380 --> 00:57:28,320 Salimos de ese bloque. 1219 00:57:28,320 --> 00:57:30,330 Y se puede ver que aquí en el resumen de fugas. 1220 00:57:30,330 --> 00:57:31,950 Aún alcanzable - 1221 00:57:31,950 --> 00:57:32,930 ocho bytes en un bloque. 1222 00:57:32,930 --> 00:57:34,100 Eso significa que la memoria - 1223 00:57:34,100 --> 00:57:35,730 hemos escapado ese recuerdo. 1224 00:57:35,730 --> 00:57:37,570 Definitivamente perdido - 1225 00:57:37,570 --> 00:57:38,770 algo se pierde para siempre. 1226 00:57:38,770 --> 00:57:40,590 En general, no lo harás ver nada allí. 1227 00:57:40,590 --> 00:57:44,780 Todavía puede llegar es generalmente donde verás las cosas, donde querrá 1228 00:57:44,780 --> 00:57:48,900 que mirar para ver qué código debe usted se han liberado pero se olvidó de liberar. 1229 00:57:48,900 --> 00:57:53,170 >> Y luego, si este no era el caso, si lo hiciéramos todo gratis, 1230 00:57:53,170 --> 00:57:54,360 podemos comprobar eso. 1231 00:57:54,360 --> 00:57:57,330 Vamos a ejecutar el programa no poner en cualquier cosa. 1232 00:57:57,330 --> 00:57:59,800 Usted verá aquí en uso en la salida - 1233 00:57:59,800 --> 00:58:01,310 cero bytes en cero bloques. 1234 00:58:01,310 --> 00:58:06,310 Eso significa que ya no tenía nada cuando este programa se cierra. 1235 00:58:06,310 --> 00:58:12,090 Así que antes de dar vuelta en pset6, valgrind ejecutar y asegúrese de que usted no tiene 1236 00:58:12,090 --> 00:58:15,310 cualquier pérdidas de memoria en su programa. 1237 00:58:15,310 --> 00:58:17,910 Si usted tiene alguna pregunta con valgrind, no dude en acercarse. 1238 00:58:17,910 --> 00:58:18,700 Pero esto es cómo lo usa. 1239 00:58:18,700 --> 00:58:20,890 Muy sencillo - si usted tener en uso en la salida - 1240 00:58:20,890 --> 00:58:22,270 cualquier byte en cualquier bloque. 1241 00:58:22,270 --> 00:58:27,890 1242 00:58:27,890 --> 00:58:29,580 >> Así que estábamos trabajando en el nodo de inserción. 1243 00:58:29,580 --> 00:58:33,840 Tenía otras dos funciones aquí - imprimir los nodos y los nodos libres. 1244 00:58:33,840 --> 00:58:37,780 Una vez más, se trata de funciones que son va a ser bueno para que practiques 1245 00:58:37,780 --> 00:58:40,990 ya que le ayudará no sólo con estos ejercicios de muestra, sino también 1246 00:58:40,990 --> 00:58:42,180 en el conjunto de problemas. 1247 00:58:42,180 --> 00:58:44,230 Se corresponden en muy de cerca a las cosas usted va a tener que hacer en el 1248 00:58:44,230 --> 00:58:45,010 establece problema. 1249 00:58:45,010 --> 00:58:47,640 Pero yo quiero estar seguro Tocamos todo. 1250 00:58:47,640 --> 00:58:50,400 Y las tablas hash también son cruciales para lo que estamos haciendo en la sección de este 1251 00:58:50,400 --> 00:58:51,980 semana - o en el conjunto de problemas. 1252 00:58:51,980 --> 00:58:55,200 >> Así que vamos a terminar la sección hablando de las tablas hash. 1253 00:58:55,200 --> 00:58:58,140 Si usted nota que hice una pequeña tabla hash. 1254 00:58:58,140 --> 00:59:00,020 Eso no es lo que estamos hablando sobre, sin embargo. 1255 00:59:00,020 --> 00:59:03,540 Estamos hablando de un diferente tipo de tablas hash. 1256 00:59:03,540 --> 00:59:07,300 Y en el fondo, una tabla hash no es más que una 1257 00:59:07,300 --> 00:59:08,860 gama más una función hash. 1258 00:59:08,860 --> 00:59:11,150 Vamos a hablar un poco sólo para asegúrese de que todo el mundo entiende lo que es un 1259 00:59:11,150 --> 00:59:12,110 función hash es. 1260 00:59:12,110 --> 00:59:15,420 Y te estoy diciendo ahora que es nada más que dos cosas - 1261 00:59:15,420 --> 00:59:18,590 una matriz y una función hash. 1262 00:59:18,590 --> 00:59:20,716 Y estos son los pasos a través de que esta opera. 1263 00:59:20,716 --> 00:59:31,560 1264 00:59:31,560 --> 00:59:32,810 >> Ahí está nuestra matriz. 1265 00:59:32,810 --> 00:59:38,460 1266 00:59:38,460 --> 00:59:39,460 Ahí está nuestra función. 1267 00:59:39,460 --> 00:59:43,180 En particular, las funciones de hash necesitan hacer un par de cosas con esto. 1268 00:59:43,180 --> 00:59:45,040 Voy a hablar específicamente acerca establece este problema. 1269 00:59:45,040 --> 00:59:46,450 Probablemente va a tomar en una cadena. 1270 00:59:46,450 --> 00:59:50,570 1271 00:59:50,570 --> 00:59:51,770 Y ¿qué va a volver? 1272 00:59:51,770 --> 00:59:52,640 ¿Qué tipo de datos? 1273 00:59:52,640 --> 00:59:54,260 Alden? 1274 00:59:54,260 --> 00:59:55,760 Devuelva su función hash? 1275 00:59:55,760 --> 00:59:58,760 Un entero. 1276 00:59:58,760 --> 01:00:01,700 Así que esto es lo que el hash tabla consta de - 1277 01:00:01,700 --> 01:00:05,430 una mesa en forma de matriz y una función de hash. 1278 01:00:05,430 --> 01:00:06,010 ¿Cómo funciona? 1279 01:00:06,010 --> 01:00:07,300 Funciona en tres pasos. 1280 01:00:07,300 --> 01:00:08,740 Le damos una clave. 1281 01:00:08,740 --> 01:00:11,470 En este caso, vamos a darle una cadena. 1282 01:00:11,470 --> 01:00:18,140 Llamamos a la función hash por el paso uno en la llave y obtenemos un valor. 1283 01:00:18,140 --> 01:00:20,310 >> En concreto, vamos a decir obtenemos un número entero. 1284 01:00:20,310 --> 01:00:25,630 Ese número entero, no son muy específicos límites a lo que puede ser entero. 1285 01:00:25,630 --> 01:00:28,880 En este ejemplo, nuestra matriz es de tamaño tres. 1286 01:00:28,880 --> 01:00:32,330 Entonces, ¿qué números puede ser ese entero. 1287 01:00:32,330 --> 01:00:35,970 ¿Cuál es el rango de valores válidos para ese entero, el tipo de retorno de esta 1288 01:00:35,970 --> 01:00:37,220 función hash? 1289 01:00:37,220 --> 01:00:40,440 1290 01:00:40,440 --> 01:00:42,110 Cero, uno y dos. 1291 01:00:42,110 --> 01:00:46,060 El punto de la función hash es averiguar el lugar de la matriz 1292 01:00:46,060 --> 01:00:47,790 donde la llave va. 1293 01:00:47,790 --> 01:00:51,290 Sólo hay tres posibles lugares aquí - 1294 01:00:51,290 --> 01:00:52,130 cero, uno, o dos. 1295 01:00:52,130 --> 01:00:55,360 Así que esta función mejor retorno cero, uno, o dos. 1296 01:00:55,360 --> 01:00:58,740 Algunos indice válida en este array. 1297 01:00:58,740 --> 01:01:02,770 >> Y a continuación, dependiendo de donde vuelve, se puede ver que hay antena abierta 1298 01:01:02,770 --> 01:01:03,730 entre paréntesis el valor. 1299 01:01:03,730 --> 01:01:05,800 Ahí es donde ponemos la clave. 1300 01:01:05,800 --> 01:01:11,280 Así que tiramos a la calabaza, salgamos cero. 1301 01:01:11,280 --> 01:01:15,540 En conjunto soporte 0, ponemos calabaza. 1302 01:01:15,540 --> 01:01:21,070 Nos tiramos en los gatos, tenemos a uno. 1303 01:01:21,070 --> 01:01:24,110 Ponemos en un gato. 1304 01:01:24,110 --> 01:01:25,480 Ponemos en araña. 1305 01:01:25,480 --> 01:01:26,710 Salimos dos. 1306 01:01:26,710 --> 01:01:30,200 Ponemos araña en conjunto soporte de dos. 1307 01:01:30,200 --> 01:01:32,300 Sería muy bueno si funcionó de esa manera. 1308 01:01:32,300 --> 01:01:35,570 Pero, por desgracia, como veremos, que es un poco más complicado. 1309 01:01:35,570 --> 01:01:37,570 >> Antes de llegar allí, cualquier pregunta sobre este básico 1310 01:01:37,570 --> 01:01:38,820 puesta a punto de una tabla hash? 1311 01:01:38,820 --> 01:01:49,050 1312 01:01:49,050 --> 01:01:51,940 Esta es una imagen de exactamente lo que dibujamos en el tablero. 1313 01:01:51,940 --> 01:01:55,420 Pero ya lo dibujamos en el tablero, me No voy a entrar en ella aún más. 1314 01:01:55,420 --> 01:02:00,430 Esencialmente, las llaves, el cuadro negro de magia - o en este caso, la caja verde azulado - de un 1315 01:02:00,430 --> 01:02:02,410 función hash los pone en cubos. 1316 01:02:02,410 --> 01:02:04,690 Y en este ejemplo estamos no poner el nombre. 1317 01:02:04,690 --> 01:02:07,880 Estamos poniendo el teléfono asociado número del nombre en el cubo. 1318 01:02:07,880 --> 01:02:10,430 Pero muy bien podría simplemente poner el nombre en el cubo. 1319 01:02:10,430 --> 01:02:12,950 >> Esto es sólo una imagen de lo que dibujamos en el tablero. 1320 01:02:12,950 --> 01:02:14,460 Tenemos dificultades potenciales, sin embargo. 1321 01:02:14,460 --> 01:02:17,470 Y hay dos en particular Las diapositivas que quiero ir. 1322 01:02:17,470 --> 01:02:20,230 La primera de ellas es de aproximadamente una función hash. 1323 01:02:20,230 --> 01:02:22,620 Así que hice la pregunta, ¿qué hace una buena función hash? 1324 01:02:22,620 --> 01:02:24,220 Le doy dos respuestas. 1325 01:02:24,220 --> 01:02:26,630 La primera es que es determinista. 1326 01:02:26,630 --> 01:02:29,660 En el contexto de las funciones de hash, ¿qué significa esto? 1327 01:02:29,660 --> 01:02:37,840 1328 01:02:37,840 --> 01:02:39,282 ¿Sí? 1329 01:02:39,282 --> 01:02:42,850 >> AUDIENCIA: Puede encontrar el índice constante de tiempo? 1330 01:02:42,850 --> 01:02:43,810 >> JASON HIRSCHHORN: Que no es lo que significa. 1331 01:02:43,810 --> 01:02:44,725 Pero eso es una buena suposición. 1332 01:02:44,725 --> 01:02:46,100 ¿Alguien más tiene una conjetura a lo que esto significa? 1333 01:02:46,100 --> 01:02:47,780 Que una buena función hash es determinista? 1334 01:02:47,780 --> 01:02:48,280 Annie? 1335 01:02:48,280 --> 01:02:51,680 >> AUDIENCIA: Que una tecla sólo se puede asignar a un lugar en la tabla hash. 1336 01:02:51,680 --> 01:02:53,070 >> JASON HIRSCHHORN: Eso es exactamente correcto. 1337 01:02:53,070 --> 01:02:57,430 Cada vez que usted pone en la calabaza, siempre devuelve cero. 1338 01:02:57,430 --> 01:03:01,660 Si usted pone en la calabaza y el hachís la función devuelve cero, pero tiene un 1339 01:03:01,660 --> 01:03:06,060 probabilidad de volver algo más mayor que cero - 1340 01:03:06,060 --> 01:03:09,280 así que tal vez puede devolver uno a veces o otras dos veces - 1341 01:03:09,280 --> 01:03:11,100 eso no es una buena función hash. 1342 01:03:11,100 --> 01:03:11,800 Tienes toda la razón. 1343 01:03:11,800 --> 01:03:15,680 Su función hash debe devolver el mismo número entero exacto, en este caso, por 1344 01:03:15,680 --> 01:03:17,780 la misma cadena exacta. 1345 01:03:17,780 --> 01:03:22,210 >> Tal vez devuelve el mismo número entero exacto para la misma cadena exacta 1346 01:03:22,210 --> 01:03:24,430 independientemente de la capitalización. 1347 01:03:24,430 --> 01:03:27,980 Pero en ese caso es todavía determinista porque varias cosas 1348 01:03:27,980 --> 01:03:29,350 se asignan en el mismo valor. 1349 01:03:29,350 --> 01:03:30,170 Eso está bien. 1350 01:03:30,170 --> 01:03:32,615 Mientras que sólo hay una de salida para una entrada dada. 1351 01:03:32,615 --> 01:03:35,630 1352 01:03:35,630 --> 01:03:36,350 >> Aceptar. 1353 01:03:36,350 --> 01:03:38,340 La segunda cosa es que devuelve índices válidos. 1354 01:03:38,340 --> 01:03:40,220 Trajimos hasta que antes. 1355 01:03:40,220 --> 01:03:41,860 Esta función hash - 1356 01:03:41,860 --> 01:03:43,710 oh boy - 1357 01:03:43,710 --> 01:03:46,840 una función hash debe volver índices válidos. 1358 01:03:46,840 --> 01:03:47,740 Así lo dicen - 1359 01:03:47,740 --> 01:03:48,990 vamos a volver a este ejemplo. 1360 01:03:48,990 --> 01:03:52,580 1361 01:03:52,580 --> 01:03:57,540 Mi función hash cuenta hasta las letras de la palabra. 1362 01:03:57,540 --> 01:03:58,380 Esa es la función hash. 1363 01:03:58,380 --> 01:03:59,740 Y vuelve ese entero. 1364 01:03:59,740 --> 01:04:04,280 Así que si tengo la palabra A, es va a devolver uno. 1365 01:04:04,280 --> 01:04:06,900 Y se va a poner una aquí. 1366 01:04:06,900 --> 01:04:09,430 ¿Qué pasa si me pongo en la palabra murciélago? 1367 01:04:09,430 --> 01:04:11,310 Se va a devolver tres. 1368 01:04:11,310 --> 01:04:12,560 ¿A dónde va murciélago? 1369 01:04:12,560 --> 01:04:18,730 1370 01:04:18,730 --> 01:04:19,750 >> No encaja. 1371 01:04:19,750 --> 01:04:21,000 Pero tiene que ir a alguna parte. 1372 01:04:21,000 --> 01:04:23,340 Este es mi tabla hash después de todo, y todo tiene que ir a alguna parte. 1373 01:04:23,340 --> 01:04:24,590 Entonces, ¿dónde debe ir murciélago? 1374 01:04:24,590 --> 01:04:28,020 1375 01:04:28,020 --> 01:04:28,710 ¿Alguna idea? 1376 01:04:28,710 --> 01:04:29,450 Conjeturas? 1377 01:04:29,450 --> 01:04:30,280 Las buenas conjeturas? 1378 01:04:30,280 --> 01:04:31,220 >> AUDIENCIA: Zero. 1379 01:04:31,220 --> 01:04:32,120 >> JASON HIRSCHHORN: ¿Por qué cero? 1380 01:04:32,120 --> 01:04:35,990 >> AUDIENCIA: Porque tres modulo tres es igual a cero? 1381 01:04:35,990 --> 01:04:38,620 >> JASON HIRSCHHORN: Triple módulo de tres es cero. 1382 01:04:38,620 --> 01:04:40,810 Esa es una gran suposición, y eso es correcto. 1383 01:04:40,810 --> 01:04:43,870 Así que en este caso se debe Probablemente vaya a cero. 1384 01:04:43,870 --> 01:04:51,080 Así que una buena manera de asegurarse de que este hash función sólo devuelve índices válidos se 1385 01:04:51,080 --> 01:04:54,580 al modulo que por el tamaño de la tabla. 1386 01:04:54,580 --> 01:04:57,360 Si Modulo Sea lo vuelve por tres, siempre se va a conseguir 1387 01:04:57,360 --> 01:05:00,930 algo entre cero, uno y dos. 1388 01:05:00,930 --> 01:05:05,160 Y si esto siempre devuelve siete, y siempre Modulo por tres, eres 1389 01:05:05,160 --> 01:05:06,030 siempre va a conseguir lo mismo. 1390 01:05:06,030 --> 01:05:09,270 >> Por lo que es aún determinista si MODULO. 1391 01:05:09,270 --> 01:05:11,420 Pero eso va a asegurar que usted nunca conseguir algo - 1392 01:05:11,420 --> 01:05:12,940 una industria no válido. 1393 01:05:12,940 --> 01:05:16,840 Generalmente, módulo que debería ocurrir dentro de su función de hash. 1394 01:05:16,840 --> 01:05:18,240 Así que usted no tiene que preocuparse por esto. 1395 01:05:18,240 --> 01:05:20,555 Sólo puede asegurarse de que este es un indice válida. 1396 01:05:20,555 --> 01:05:23,700 1397 01:05:23,700 --> 01:05:26,700 ¿Tiene preguntas sobre este potencial escollo? 1398 01:05:26,700 --> 01:05:36,590 1399 01:05:36,590 --> 01:05:39,060 >> Aceptar. 1400 01:05:39,060 --> 01:05:40,290 Y ahí vamos. 1401 01:05:40,290 --> 01:05:42,890 Siguiente error potencial y esta es la grande. 1402 01:05:42,890 --> 01:05:46,880 ¿Qué pasa si dos claves mapa en el mismo valor? 1403 01:05:46,880 --> 01:05:49,350 Así que hay dos maneras de manejar esto. 1404 01:05:49,350 --> 01:05:53,140 1405 01:05:53,140 --> 01:05:56,020 La primera se llama lineal sondeo, que estoy 1406 01:05:56,020 --> 01:05:57,300 No voy a ir otra vez. 1407 01:05:57,300 --> 01:06:01,120 Pero usted debe estar familiarizado con la forma que funciona y lo que es eso. 1408 01:06:01,120 --> 01:06:05,610 >> El segundo, voy a ir más ya que es el que muchos 1409 01:06:05,610 --> 01:06:08,290 la gente probablemente va a terminar de decidir para usar en su conjunto de problemas. 1410 01:06:08,290 --> 01:06:09,820 Por supuesto, usted no tiene que hacerlo. 1411 01:06:09,820 --> 01:06:15,280 Sin embargo, para el conjunto de problemas, muchas personas tienden a optar por crear una tabla hash 1412 01:06:15,280 --> 01:06:17,950 con encadenamiento separado para implementar su diccionario. 1413 01:06:17,950 --> 01:06:21,390 Así que vamos a ir más de lo que significa para crear una tabla hash con 1414 01:06:21,390 --> 01:06:23,890 encadenamiento separado. 1415 01:06:23,890 --> 01:06:26,260 >> Así que me puse en calabaza. 1416 01:06:26,260 --> 01:06:29,560 Devuelve cero. 1417 01:06:29,560 --> 01:06:31,410 Y puse calabaza aquí. 1418 01:06:31,410 --> 01:06:35,880 1419 01:06:35,880 --> 01:06:37,930 Entonces me puse en - 1420 01:06:37,930 --> 01:06:39,922 lo que es otra cosa con temas de Halloween? 1421 01:06:39,922 --> 01:06:42,200 >> AUDIENCIA: Candy. 1422 01:06:42,200 --> 01:06:42,770 >> JASON HIRSCHHORN: caramelo! 1423 01:06:42,770 --> 01:06:43,910 Eso es un gran uno. 1424 01:06:43,910 --> 01:06:47,760 Puse en los dulces y caramelos También me da cero. 1425 01:06:47,760 --> 01:06:49,350 ¿Qué hago? 1426 01:06:49,350 --> 01:06:51,940 ¿Alguna idea? 1427 01:06:51,940 --> 01:06:53,940 Debido a que toda la clase de sabe lo encadenamiento separado es. 1428 01:06:53,940 --> 01:06:55,190 Así que cualquier idea de qué hacer? 1429 01:06:55,190 --> 01:06:58,170 1430 01:06:58,170 --> 01:06:59,110 Sí. 1431 01:06:59,110 --> 01:07:03,810 >> AUDIENCIA: Poner la cadena realidad en la tabla hash. 1432 01:07:03,810 --> 01:07:08,910 >> JASON HIRSCHHORN: Así que vamos a dibujar la buena idea aquí. 1433 01:07:08,910 --> 01:07:09,340 Aceptar. 1434 01:07:09,340 --> 01:07:12,290 >> AUDIENCIA: Tener la tabla hash [Inaudible] 1435 01:07:12,290 --> 01:07:16,640 el puntero que apunta a el principio de una lista. 1436 01:07:16,640 --> 01:07:20,930 Y luego han calabaza ser el primer valor en esa lista y dulces vinculado ser 1437 01:07:20,930 --> 01:07:22,800 el segundo valor en esa lista enlazada. 1438 01:07:22,800 --> 01:07:23,420 >> JASON HIRSCHHORN: OK. 1439 01:07:23,420 --> 01:07:24,670 Marcus, que era excepcional. 1440 01:07:24,670 --> 01:07:26,160 Voy a romper eso. 1441 01:07:26,160 --> 01:07:28,890 Marcus está diciendo que no sobrescribir calabaza. 1442 01:07:28,890 --> 01:07:30,660 Eso sería malo. 1443 01:07:30,660 --> 01:07:33,640 No poner el caramelo en otro lugar. 1444 01:07:33,640 --> 01:07:35,390 Vamos a poner a ambos en cero. 1445 01:07:35,390 --> 01:07:37,770 Pero vamos a hacer frente a poniéndolos a cero 1446 01:07:37,770 --> 01:07:39,395 la creación de una lista en cero. 1447 01:07:39,395 --> 01:07:42,430 Y vamos a crear una lista de todo lo que se asigna a cero. 1448 01:07:42,430 --> 01:07:47,960 Y la mejor manera que hemos aprendido para crear una lista que puede crecer y encoger 1449 01:07:47,960 --> 01:07:49,840 dinámica no está dentro otra matriz. 1450 01:07:49,840 --> 01:07:51,510 Así que no es una matriz multi-dimensional. 1451 01:07:51,510 --> 01:07:54,080 Pero basta con crear una lista enlazada. 1452 01:07:54,080 --> 01:07:55,330 >> Así que lo que él propuso - 1453 01:07:55,330 --> 01:07:57,950 1454 01:07:57,950 --> 01:07:59,200 Voy a conseguir un nuevo - 1455 01:07:59,200 --> 01:08:15,380 1456 01:08:15,380 --> 01:08:19,689 es crear una matriz con punteros, una matriz de punteros. 1457 01:08:19,689 --> 01:08:20,580 Aceptar. 1458 01:08:20,580 --> 01:08:24,180 Cualquier idea o sugerencia de lo que el tipo de de estos indicadores debería ser? 1459 01:08:24,180 --> 01:08:26,290 Marcus? 1460 01:08:26,290 --> 01:08:27,250 >> AUDIENCIA: Punteros a - 1461 01:08:27,250 --> 01:08:28,609 >> JASON HIRSCHHORN: Debido a que usted dijo una lista enlazada, así - 1462 01:08:28,609 --> 01:08:29,520 >> AUDIENCIA: punteros de nodo? 1463 01:08:29,520 --> 01:08:30,670 >> JASON HIRSCHHORN: Punteros de nodo. 1464 01:08:30,670 --> 01:08:32,830 Si las cosas en nuestra vinculados lista de nodos son entonces 1465 01:08:32,830 --> 01:08:34,370 debe ser punteros de nodo. 1466 01:08:34,370 --> 01:08:35,939 ¿Y qué es lo que equivalen a un principio? 1467 01:08:35,939 --> 01:08:36,990 >> AUDIENCIA: Nulo. 1468 01:08:36,990 --> 01:08:38,240 >> JASON HIRSCHHORN: Nulo. 1469 01:08:38,240 --> 01:08:44,540 1470 01:08:44,540 --> 01:08:46,080 Así que no es lo nuestro vacío. 1471 01:08:46,080 --> 01:08:47,170 Vuelve calabaza cero. 1472 01:08:47,170 --> 01:08:48,569 ¿Qué hacemos? 1473 01:08:48,569 --> 01:08:49,609 Camina conmigo a través de él? 1474 01:08:49,609 --> 01:08:50,810 En realidad, Marcus ya me dio. 1475 01:08:50,810 --> 01:08:52,439 Alguien más me caminar a través de él. 1476 01:08:52,439 --> 01:08:54,760 ¿Qué hacemos cuando - 1477 01:08:54,760 --> 01:08:56,609 esto se ve muy similar a lo que estábamos haciendo. 1478 01:08:56,609 --> 01:08:57,396 Avi. 1479 01:08:57,396 --> 01:08:59,090 >> AUDIENCIA: Me voy a tomar una conjetura. 1480 01:08:59,090 --> 01:09:01,250 Así que cuando usted consigue el caramelo. 1481 01:09:01,250 --> 01:09:01,640 >> JASON HIRSCHHORN: Si. 1482 01:09:01,640 --> 01:09:03,120 Bueno, tenemos calabaza. 1483 01:09:03,120 --> 01:09:03,870 Vamos a nuestra primera. 1484 01:09:03,870 --> 01:09:04,324 Tenemos calabaza. 1485 01:09:04,324 --> 01:09:04,779 >> AUDIENCIA: OK. 1486 01:09:04,779 --> 01:09:05,880 Vuelve calabaza cero. 1487 01:09:05,880 --> 01:09:08,770 Así lo pones en eso. 1488 01:09:08,770 --> 01:09:10,810 O en realidad, lo pones en la lista enlazada. 1489 01:09:10,810 --> 01:09:13,550 >> JASON HIRSCHHORN: ¿Cómo lo puso en la lista enlazada? 1490 01:09:13,550 --> 01:09:15,479 >> AUDIENCIA: ¡Oh, la sintaxis actual? 1491 01:09:15,479 --> 01:09:16,240 >> JASON HIRSCHHORN: Sólo hay que pasar - 1492 01:09:16,240 --> 01:09:16,740 decir más. 1493 01:09:16,740 --> 01:09:19,310 ¿Qué hacemos? 1494 01:09:19,310 --> 01:09:22,100 >> AUDIENCIA: Sólo hay que insertar como el primer nodo. 1495 01:09:22,100 --> 01:09:22,675 >> JASON HIRSCHHORN: OK. 1496 01:09:22,675 --> 01:09:29,069 Así que tenemos nuestro nodo, calabaza. 1497 01:09:29,069 --> 01:09:31,560 Y ahora ¿cómo lo introduzco? 1498 01:09:31,560 --> 01:09:34,590 1499 01:09:34,590 --> 01:09:37,090 >> AUDIENCIA: Usted asigna en el puntero. 1500 01:09:37,090 --> 01:09:37,970 >> JASON HIRSCHHORN: ¿Qué puntero? 1501 01:09:37,970 --> 01:09:39,620 >> AUDIENCIA: El indicador en cero. 1502 01:09:39,620 --> 01:09:41,420 >> JASON HIRSCHHORN: Entonces, ¿dónde hace este punto? 1503 01:09:41,420 --> 01:09:42,810 >> AUDIENCIA: Para nulo en estos momentos. 1504 01:09:42,810 --> 01:09:43,529 >> JASON HIRSCHHORN: Bueno, está apuntando a null. 1505 01:09:43,529 --> 01:09:44,499 Pero me voy a poner en la calabaza. 1506 01:09:44,499 --> 01:09:46,053 Entonces, ¿dónde debería apuntar? 1507 01:09:46,053 --> 01:09:46,880 >> AUDIENCIA: Para calabaza. 1508 01:09:46,880 --> 01:09:47,399 >> JASON HIRSCHHORN: Para calabaza. 1509 01:09:47,399 --> 01:09:48,760 Exactamente. 1510 01:09:48,760 --> 01:09:50,010 Así que esto apunta a la calabaza. 1511 01:09:50,010 --> 01:09:52,500 1512 01:09:52,500 --> 01:09:54,250 Y ¿de dónde viene este puntero en el punto de calabaza? 1513 01:09:54,250 --> 01:09:57,986 1514 01:09:57,986 --> 01:09:58,340 A 1515 01:09:58,340 --> 01:09:58,590 >> AUDIENCIA: Nulo. 1516 01:09:58,590 --> 01:09:59,210 >> JASON HIRSCHHORN: null. 1517 01:09:59,210 --> 01:10:00,460 Exactamente. 1518 01:10:00,460 --> 01:10:03,570 1519 01:10:03,570 --> 01:10:05,140 Así que sólo nos insertamos algo a la lista enlazada. 1520 01:10:05,140 --> 01:10:07,210 Acabamos de escribir el código para hacer esto. 1521 01:10:07,210 --> 01:10:09,520 Casi casi nos lo completamente agrietado. 1522 01:10:09,520 --> 01:10:10,790 Ahora insertamos el caramelo. 1523 01:10:10,790 --> 01:10:13,480 Nuestro dulces también tiende a cero. 1524 01:10:13,480 --> 01:10:16,100 Entonces, ¿qué hacemos con los dulces? 1525 01:10:16,100 --> 01:10:18,790 >> AUDIENCIA: Depende de si No estamos tratando de resolverlo. 1526 01:10:18,790 --> 01:10:19,640 >> JASON HIRSCHHORN: Eso es exactamente correcto. 1527 01:10:19,640 --> 01:10:21,070 Depende de si es o no que estamos tratando de solucionar el problema. 1528 01:10:21,070 --> 01:10:22,660 Vamos a suponer que no estamos va a solucionar el problema. 1529 01:10:22,660 --> 01:10:24,880 >> AUDIENCIA: Pues bien, como hemos comentado antes, es más sencillo sólo para ponerlo 1530 01:10:24,880 --> 01:10:28,590 desde el principio por lo que el puntero de cero puntos a los dulces. 1531 01:10:28,590 --> 01:10:29,020 >> JASON HIRSCHHORN: OK. 1532 01:10:29,020 --> 01:10:29,380 Espera. 1533 01:10:29,380 --> 01:10:30,630 Déjame crear dulces aquí. 1534 01:10:30,630 --> 01:10:34,030 1535 01:10:34,030 --> 01:10:35,150 Así que este puntero - 1536 01:10:35,150 --> 01:10:37,590 >> AUDIENCIA: Sí, ahora debe apuntar a los dulces. 1537 01:10:37,590 --> 01:10:40,580 Luego que el puntero de punto de caramelo para la calabaza. 1538 01:10:40,580 --> 01:10:43,140 1539 01:10:43,140 --> 01:10:44,560 >> JASON HIRSCHHORN: ¿Así? 1540 01:10:44,560 --> 01:10:47,380 Y decimos que tenemos otra cosa para asignar a cero? 1541 01:10:47,380 --> 01:10:48,660 >> AUDIENCIA: Bueno, usted acaba de hacer lo mismo? 1542 01:10:48,660 --> 01:10:50,290 >> JASON HIRSCHHORN: Hacer lo mismo. 1543 01:10:50,290 --> 01:10:53,700 Así que en este caso, si no lo hacemos quieren mantener lo resuelto que 1544 01:10:53,700 --> 01:10:55,270 Suena bastante simple. 1545 01:10:55,270 --> 01:10:59,920 Tomamos el puntero en el indice dada por nuestra función hash. 1546 01:10:59,920 --> 01:11:03,830 Tenemos que apuntan a nuestro nuevo nodo. 1547 01:11:03,830 --> 01:11:07,830 Y entonces lo que estaba señalando previamente - 1548 01:11:07,830 --> 01:11:10,620 en este caso nulo, en el segundo caso calabaza - 1549 01:11:10,620 --> 01:11:15,310 que, sea lo que está señalando anteriormente, se añade en el siguiente de 1550 01:11:15,310 --> 01:11:17,810 nuestro nuevo nodo. 1551 01:11:17,810 --> 01:11:19,650 Estamos insertando algo en el comienzo. 1552 01:11:19,650 --> 01:11:22,900 De hecho, esto es mucho más simple que tratando de mantener la lista ordenada. 1553 01:11:22,900 --> 01:11:25,340 Pero, de nuevo, la búsqueda será más complicado aquí. 1554 01:11:25,340 --> 01:11:28,300 Siempre tendremos que ir hasta el final. 1555 01:11:28,300 --> 01:11:29,650 >> Aceptar. 1556 01:11:29,650 --> 01:11:32,750 ¿Una pregunta sobre encadenamiento separado? 1557 01:11:32,750 --> 01:11:34,690 ¿Cómo funciona? 1558 01:11:34,690 --> 01:11:35,820 Por favor, pregunte ahora. 1559 01:11:35,820 --> 01:11:39,260 Tengo muchas ganas de asegurarse de que todos los entender esto antes de que nos dirigimos. 1560 01:11:39,260 --> 01:11:48,410 1561 01:11:48,410 --> 01:11:52,060 >> AUDIENCIA: ¿Por qué te pones de calabaza y los dulces en el mismo 1562 01:11:52,060 --> 01:11:54,108 parte de la tabla hash? 1563 01:11:54,108 --> 01:11:55,860 >> JASON HIRSCHHORN: Buena pregunta. 1564 01:11:55,860 --> 01:11:59,140 ¿Por qué los ponemos en la misma parte de la tabla hash? 1565 01:11:59,140 --> 01:12:03,200 Bueno, en este caso nuestra función hash devuelve cero para los dos. 1566 01:12:03,200 --> 01:12:05,310 Así que tienen que ir en cero indice porque ahí es donde vamos a 1567 01:12:05,310 --> 01:12:07,420 buscarlos si alguna vez querer mirar para arriba. 1568 01:12:07,420 --> 01:12:11,750 Una vez más, con un enfoque de sondeo lineal nosotros no pondríamos a los dos al cero. 1569 01:12:11,750 --> 01:12:13,900 Pero en el enfoque de la cadena independiente, nos vamos a poner a ambos en cero 1570 01:12:13,900 --> 01:12:16,620 a continuación, crear una lista de cero. 1571 01:12:16,620 --> 01:12:20,140 >> Y no queremos sobrescribir calabaza simplemente por eso, porque entonces vamos a 1572 01:12:20,140 --> 01:12:21,860 asumir que la calabaza era nunca insertado. 1573 01:12:21,860 --> 01:12:25,230 Si acabamos de tener una cosa en la ubicación que sería malo. 1574 01:12:25,230 --> 01:12:28,590 Entonces no habría oportunidad de nosotros - 1575 01:12:28,590 --> 01:12:31,660 si hemos tenido un duplicado, entonces sería simplemente borrar nuestro valor inicial. 1576 01:12:31,660 --> 01:12:34,090 Así que por eso hacemos este enfoque. 1577 01:12:34,090 --> 01:12:36,580 ¿O es por eso que elegimos - pero de nuevo, eligió el enfoque de encadenamiento separado, 1578 01:12:36,580 --> 01:12:39,670 que hay muchos otros enfoques uno puede elegir. 1579 01:12:39,670 --> 01:12:41,185 ¿Responde esto a su pregunta? 1580 01:12:41,185 --> 01:12:41,660 >> Aceptar. 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 Sondeo lineal implicaría - 1584 01:12:47,720 --> 01:12:51,913 si encontramos una colisión a cero, se vería en el punto siguiente para ver si 1585 01:12:51,913 --> 01:12:54,310 que estaba abierto y lo puso allí. 1586 01:12:54,310 --> 01:12:57,320 Y entonces nos miramos en el siguiente deporte y ver si estaba abierto y lo puso allí. 1587 01:12:57,320 --> 01:12:59,780 Así nos encontramos con la siguiente disposición lugar abierto y lo puso allí. 1588 01:12:59,780 --> 01:13:02,580 1589 01:13:02,580 --> 01:13:03,890 ¿Alguna otra pregunta? 1590 01:13:03,890 --> 01:13:05,370 Sí, Avi. 1591 01:13:05,370 --> 01:13:07,490 >> AUDIENCIA: Como seguimiento a eso, ¿qué quiere decir el próximo acto? 1592 01:13:07,490 --> 01:13:10,250 En la tabla hash o en una lista enlazada. 1593 01:13:10,250 --> 01:13:12,100 >> JASON HIRSCHHORN: Para lineal programación, no hay listas enlazadas. 1594 01:13:12,100 --> 01:13:13,400 El siguiente punto en la tabla hash. 1595 01:13:13,400 --> 01:13:13,820 >> AUDIENCIA: OK. 1596 01:13:13,820 --> 01:13:17,570 Así que la tabla hash sería inicializado al tamaño - 1597 01:13:17,570 --> 01:13:19,560 como el número de cadenas que estuviera insertando? 1598 01:13:19,560 --> 01:13:22,170 >> JASON HIRSCHHORN: Lo harías quiero que sea muy grande. 1599 01:13:22,170 --> 01:13:23,910 Sí. 1600 01:13:23,910 --> 01:13:27,900 Aquí está una foto de lo que acaba de dibujar en el tablero. 1601 01:13:27,900 --> 01:13:29,470 Una vez más, tenemos una colisión aquí. 1602 01:13:29,470 --> 01:13:30,710 en 152. 1603 01:13:30,710 --> 01:13:33,570 Y verás que hemos creado una lista enlazada fuera de ella. 1604 01:13:33,570 --> 01:13:38,200 1605 01:13:38,200 --> 01:13:41,850 Una vez más, la tabla hash encadenamiento separado enfoque no es el que usted 1606 01:13:41,850 --> 01:13:45,590 tienen que tomar para establecer los problemas seis, pero es una que mucha 1607 01:13:45,590 --> 01:13:47,100 los estudiantes tienden a tomar. 1608 01:13:47,100 --> 01:13:51,140 Así que en ese sentido, vamos a hablar brevemente antes de que nos dirigimos a cabo sobre el problema de las seis, 1609 01:13:51,140 --> 01:13:52,160 y luego voy a compartir con ustedes una historia. 1610 01:13:52,160 --> 01:13:55,120 Tenemos tres minutos. 1611 01:13:55,120 --> 01:13:55,750 >> Problema seis set. 1612 01:13:55,750 --> 01:13:57,790 Usted tiene cuatro funciones - 1613 01:13:57,790 --> 01:14:02,430 carga, comprobar, el tamaño y descarga. 1614 01:14:02,430 --> 01:14:03,380 Load - 1615 01:14:03,380 --> 01:14:07,120 bueno, hemos estado yendo sobre carga en este momento. 1616 01:14:07,120 --> 01:14:09,330 Dibujamos la carga en el tablero. 1617 01:14:09,330 --> 01:14:13,230 E incluso nos empezamos a codificar una gran cantidad de insertar en una lista enlazada. 1618 01:14:13,230 --> 01:14:18,020 Así que la carga no es mucho más que lo que hemos estado haciendo. 1619 01:14:18,020 --> 01:14:21,070 >> Descubre que es una vez que haya algo cargado. 1620 01:14:21,070 --> 01:14:22,580 Es el mismo proceso que este. 1621 01:14:22,580 --> 01:14:26,845 Las mismas dos primeras partes donde usted lanza algo dentro de la función hash 1622 01:14:26,845 --> 01:14:29,190 y obtener su valor. 1623 01:14:29,190 --> 01:14:30,700 Pero ahora no estamos de insertarlo. 1624 01:14:30,700 --> 01:14:33,350 Ahora estamos buscando. 1625 01:14:33,350 --> 01:14:37,130 He escrito el código de ejemplo para encontrar algo en una lista enlazada. 1626 01:14:37,130 --> 01:14:38,250 Os animo a practicar eso. 1627 01:14:38,250 --> 01:14:43,000 Pero intuitivamente encontrar algo que se bastante similar a la inserción de algo. 1628 01:14:43,000 --> 01:14:46,540 De hecho, nos hizo un dibujo de la búsqueda algo en una lista enlazada, moviéndose 1629 01:14:46,540 --> 01:14:48,910 a través hasta que llegamos a la final. 1630 01:14:48,910 --> 01:14:52,430 Y si llegamos a la final y no podía encuentra, entonces no está allí. 1631 01:14:52,430 --> 01:14:55,400 Así que eso es cheque, esencialmente. 1632 01:14:55,400 --> 01:14:57,030 >> Siguiente es el tamaño. 1633 01:14:57,030 --> 01:14:57,910 Vamos a saltar tamaño. 1634 01:14:57,910 --> 01:15:00,040 Finalmente has descargar. 1635 01:15:00,040 --> 01:15:02,890 Unload es que no hemos elaborado en la pizarra o aún codificada. 1636 01:15:02,890 --> 01:15:05,990 Pero me animo a probar a programarlo en nuestra muestra ejemplo de lista enlazada. 1637 01:15:05,990 --> 01:15:11,440 Pero descargar intuitiva es similar a la libre - 1638 01:15:11,440 --> 01:15:14,010 o que quiero decir es similar a comprobar. 1639 01:15:14,010 --> 01:15:17,350 Excepto por el momento cada vez que usted va a través, no estas seleccionando a 1640 01:15:17,350 --> 01:15:19,090 ver si usted tiene su valor allí. 1641 01:15:19,090 --> 01:15:22,490 Pero usted está tomando ese nodo y liberándola, esencialmente. 1642 01:15:22,490 --> 01:15:23,610 Eso es lo que descarga te pide que hagas. 1643 01:15:23,610 --> 01:15:24,670 Todo lo libre que ha malloced. 1644 01:15:24,670 --> 01:15:27,480 Así que vas a través de toda la lista de nuevo, pasando por todo el hash 1645 01:15:27,480 --> 01:15:27,760 mesa de nuevo. 1646 01:15:27,760 --> 01:15:29,240 Esta vez no marca para ver lo que hay allí. 1647 01:15:29,240 --> 01:15:31,080 Sólo liberar lo que hay. 1648 01:15:31,080 --> 01:15:33,260 >> Y finalmente tamaño. 1649 01:15:33,260 --> 01:15:34,350 Tamaño debe ser implementado. 1650 01:15:34,350 --> 01:15:35,590 Si no se implementa el tamaño - 1651 01:15:35,590 --> 01:15:36,250 Voy a decirlo de esta manera. 1652 01:15:36,250 --> 01:15:39,740 Si no se implementa tamaño exactamente una línea de código que incluye el 1653 01:15:39,740 --> 01:15:43,760 volver declaración, usted es haciendo tamaño incorrectamente. 1654 01:15:43,760 --> 01:15:47,170 Así que asegúrese de que el tamaño, para el diseño completo puntos, lo estás haciendo exactamente en un 1655 01:15:47,170 --> 01:15:49,970 línea de código, incluyendo la sentencia return. 1656 01:15:49,970 --> 01:15:52,450 >> Y no las maletas, sin embargo, 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 Quería dar las gracias chicos por venir a la sección. 1660 01:16:01,300 --> 01:16:02,550 Tenga un feliz Halloween. 1661 01:16:02,550 --> 01:16:05,300 1662 01:16:05,300 --> 01:16:05,960 Este es mi disfraz. 1663 01:16:05,960 --> 01:16:08,850 Llevaré este jueves si te veo en horario de oficina. 1664 01:16:08,850 --> 01:16:14,640 Y si eres curioso acerca un poco más fondo para este traje, se sienten 1665 01:16:14,640 --> 01:16:19,135 libre de visitar la sección 2011 para una historia sobre por qué estoy 1666 01:16:19,135 --> 01:16:20,900 vistiendo el traje de calabaza. 1667 01:16:20,900 --> 01:16:23,680 Y es una historia triste. 1668 01:16:23,680 --> 01:16:27,050 Así que asegúrese de que tiene algunos tejidos cercanos. 1669 01:16:27,050 --> 01:16:28,680 Pero en eso, si usted tiene cualquier preguntas que me quedaré por aquí 1670 01:16:28,680 --> 01:16:29,960 fuera después de la sección. 1671 01:16:29,960 --> 01:16:31,510 Buena suerte en problema seises. 1672 01:16:31,510 --> 01:16:33,540 Y como siempre, si tiene alguna preguntas, que me haga saber. 1673 01:16:33,540 --> 01:16:35,584