1 00:00:00,000 --> 00:00:11,460 2 00:00:11,460 --> 00:00:12,250 >> DAVID MALAN: Muy bien. 3 00:00:12,250 --> 00:00:13,860 Bienvenido de nuevo a CS50. 4 00:00:13,860 --> 00:00:16,190 Este es el comienzo de la semana 8. 5 00:00:16,190 --> 00:00:21,320 Y recordemos que problemas 5 terminado con un poco de un desafío. 6 00:00:21,320 --> 00:00:25,210 Así que asumiendo que usted ha recuperado la totalidad de su Teaching Fellows y fotografías de CA 7 00:00:25,210 --> 00:00:30,480 en el archivo card.raw, usted es elegible que ahora se encuentran todas esas personas, y 8 00:00:30,480 --> 00:00:34,510 un afortunado ganador será regresar a casa con una de estas cosas, el movimiento de salto 9 00:00:34,510 --> 00:00:37,450 dispositivo que se puede utilizar para la final de proyectos, por ejemplo. 10 00:00:37,450 --> 00:00:39,860 >> Este, cada año, lleva a un poco de creepiness. 11 00:00:39,860 --> 00:00:43,480 Y así lo que yo pensé que iba a hacer es compartir con ustedes algunas de las notas que tienen 12 00:00:43,480 --> 00:00:47,370 ido adelante y atrás sobre la lista de personal en los últimos tiempos. 13 00:00:47,370 --> 00:00:51,110 Por ejemplo, anoche, cita fin de la cita, de uno de los del personal 14 00:00:51,110 --> 00:00:55,000 miembros, "Acabo de tener un golpe estudiante a mi puerta para hacer una foto conmigo. 15 00:00:55,000 --> 00:00:59,020 Los acosadores, les digo. "Empezó, bastante descriptivo y luego nos mudamos 16 00:00:59,020 --> 00:01:02,830 a, una hora más tarde, "Yo tenía un estudiante me espera después de la sección 17 00:01:02,830 --> 00:01:06,080 y tenía todos nuestros nombres y fotos en algunas hojas de papel. "Muy bien. 18 00:01:06,080 --> 00:01:09,230 Así organizada, pero no todo lo que todavía espeluznante. 19 00:01:09,230 --> 00:01:12,520 >> Entonces, "Yo estaba fuera de la ciudad este fin de semana, y cuando volví, había uno en 20 00:01:12,520 --> 00:01:12,630 mi 21 00:01:12,630 --> 00:01:16,740 dormitorio ". [Risas] 22 00:01:16,740 --> 00:01:20,410 DAVID MALAN: Próxima cita de un personal miembro ", un estudiante vino a mi casa a las 23 00:01:20,410 --> 00:01:25,330 Somerville a las 4 am de esta mañana. "Next personal: "Yo llegué a mi hotel en San 24 00:01:25,330 --> 00:01:30,016 Francisco y un estudiante estaba esperando mí en el hall de entrada con tres cámaras réflex digitales. " 25 00:01:30,016 --> 00:01:31,510 Tipo de cámara. 26 00:01:31,510 --> 00:01:34,980 "Ni siquiera estoy en el personal de este semestre, pero un estudiante entró a mi casa esta 27 00:01:34,980 --> 00:01:40,480 mañana y registrado todo el asunto con Google Glass. "Y luego, por último, 28 00:01:40,480 --> 00:01:43,650 "Por lo menos 12 personas fueron ávidamente esperando por mí cuando salí de mi 29 00:01:43,650 --> 00:01:44,800 limo, y luego me 30 00:01:44,800 --> 00:01:46,970 despertó. "Muy bien. 31 00:01:46,970 --> 00:01:57,690 Así que entre las fotografías, ya que puede recordar, es este hombre aquí, que os 32 00:01:57,690 --> 00:02:01,850 podría saber como Milo Banana, que vive con Lauren Carvalho, nuestra cabeza 33 00:02:01,850 --> 00:02:02,905 Teaching Fellow. 34 00:02:02,905 --> 00:02:05,170 Milo, Milo, ven aquí chico. 35 00:02:05,170 --> 00:02:06,320 Milo. 36 00:02:06,320 --> 00:02:08,650 Milo. 37 00:02:08,650 --> 00:02:12,230 Eso sí, él está usando Google Glass, por lo le mostraremos todo esto después. 38 00:02:12,230 --> 00:02:16,190 Así que esto es Milo si usted desea tomar una fotografía con él después. 39 00:02:16,190 --> 00:02:18,240 Si desea buscar a la audiencia allí. 40 00:02:18,240 --> 00:02:19,430 Aceptar. 41 00:02:19,430 --> 00:02:20,200 Eso es bueno metraje. 42 00:02:20,200 --> 00:02:22,556 Bueno, Milo plátano. 43 00:02:22,556 --> 00:02:23,941 Oh, no hagas eso. 44 00:02:23,941 --> 00:02:29,020 >> [Risas] 45 00:02:29,020 --> 00:02:29,470 >> Aceptar. 46 00:02:29,470 --> 00:02:34,550 Así que una palabra a continuación, en lo que se avecina, porque a medida que empezamos a la transición, 47 00:02:34,550 --> 00:02:38,410 esta semana específicamente, de C en un entorno de línea de comandos para PHP y 48 00:02:38,410 --> 00:02:42,720 JavaScript y SQL y HTML y CSS en un entorno basado en web, estaremos 49 00:02:42,720 --> 00:02:44,490 y te equipa con todo el más conocimiento para 50 00:02:44,490 --> 00:02:46,010 potenciales proyectos finales. 51 00:02:46,010 --> 00:02:49,240 Con ese fin, el curso tiene una tradición de la celebración de seminarios que 52 00:02:49,240 --> 00:02:50,950 son sobre temas tangenciales al curso. 53 00:02:50,950 --> 00:02:54,330 Muy relacionado con la programación y para desarrollo de aplicaciones y así sucesivamente, pero 54 00:02:54,330 --> 00:02:57,010 no explorado necesariamente por propio plan de estudios del curso. 55 00:02:57,010 --> 00:03:00,250 >> Así que si usted podría estar interesado en una o más de los seminarios de este año, 56 00:03:00,250 --> 00:03:02,530 registrarse en cs50.net/seminar. 57 00:03:02,530 --> 00:03:06,170 Hay seminarios mayores en cs50.net/seminars. 58 00:03:06,170 --> 00:03:10,620 Y en la lista hasta el momento para este año Web Apps son increíbles con Ruby on 59 00:03:10,620 --> 00:03:13,580 Rails, que es una alternativa lenguaje PHP. 60 00:03:13,580 --> 00:03:14,900 Lingüística Computacional. 61 00:03:14,900 --> 00:03:18,710 Introducción a la IOS, que es el plataforma que se utiliza para el iPhone y el 62 00:03:18,710 --> 00:03:19,850 desarrollo iPad. 63 00:03:19,850 --> 00:03:22,890 JavaScript para Aplicaciones Web, vamos a cubrir eso, sino que en este seminario, que irá 64 00:03:22,890 --> 00:03:24,070 en más detalles. 65 00:03:24,070 --> 00:03:27,390 >> Salto de movimiento, así que en realidad va a tener un poco de de nuestros amigos de Salto Movimiento, 66 00:03:27,390 --> 00:03:29,160 la propia empresa, se unan a nosotros. 67 00:03:29,160 --> 00:03:31,800 Mañana, de hecho, para proporcionar un seminario práctico, si 68 00:03:31,800 --> 00:03:33,320 de interés para usted. 69 00:03:33,320 --> 00:03:38,770 Meteor.js, una técnica alternativa para usando JavaScript no en un navegador, 70 00:03:38,770 --> 00:03:39,970 pero en un servidor. 71 00:03:39,970 --> 00:03:42,110 Node.js, que es en gran medida en ese sentido también. 72 00:03:42,110 --> 00:03:43,650 Diseño elegante Android. 73 00:03:43,650 --> 00:03:46,990 Siendo Android una alternativa muy popular para iOS y Windows Phone 74 00:03:46,990 --> 00:03:48,790 y otras plataformas móviles. 75 00:03:48,790 --> 00:03:51,180 Y Seguridad Active Web Defensa. 76 00:03:51,180 --> 00:03:54,590 >> Así que de hecho, si usted desea a participar en esto, déjame 77 00:03:54,590 --> 00:03:55,840 tome nota de esto. 78 00:03:55,840 --> 00:03:57,790 Estamos muy felices de decir que nuestros amigos de Salto 79 00:03:57,790 --> 00:03:59,140 Movimiento, que es un inicio - 80 00:03:59,140 --> 00:04:01,300 este dispositivo realmente acaba de llegar hace unos meses - 81 00:04:01,300 --> 00:04:05,960 ha donado graciosamente 30 de estos dispositivos a la clase por tantos estudiantes, si 82 00:04:05,960 --> 00:04:08,670 desea pedir prestado el hardware hacia el final del semestre y utilizarlo para 83 00:04:08,670 --> 00:04:10,390 un proyecto final real. 84 00:04:10,390 --> 00:04:11,890 Apoyan a varios idiomas. 85 00:04:11,890 --> 00:04:16,040 Ninguno de ellos C, ninguno de ellos PHP, así realizar uno o más de estos seminarios 86 00:04:16,040 --> 00:04:16,899 podría resultar de interés. 87 00:04:16,899 --> 00:04:19,730 Y todos ellos será filmado en el caso de que usted no es capaz 88 00:04:19,730 --> 00:04:21,380 asistir en persona. 89 00:04:21,380 --> 00:04:25,000 El horario será anunciado a través de correo electrónico a medida que consolidamos habitaciones. 90 00:04:25,000 --> 00:04:28,460 >> Y por último, si usted va a projects.cs.50.net, este es un sitio web 91 00:04:28,460 --> 00:04:31,450 mantenemos cada año que invitemos gente de la comunidad, profesores, 92 00:04:31,450 --> 00:04:36,420 departamentos, personal, y tanto en el exterior del CS50 a 93 00:04:36,420 --> 00:04:37,730 proponer ideas de proyectos. 94 00:04:37,730 --> 00:04:39,050 Actividades de interés para los grupos de estudiantes. 95 00:04:39,050 --> 00:04:40,600 Actividades de interés para los departamentos. 96 00:04:40,600 --> 00:04:43,990 Así que vuelta allí si usted está luchando la incertidumbre en cuanto a lo que 97 00:04:43,990 --> 00:04:46,700 usted le gustaría abordar. 98 00:04:46,700 --> 00:04:51,760 >> Así que la última vez que presentamos una duda estructura de datos más compleja de lo que habíamos 99 00:04:51,760 --> 00:04:53,300 visto en semanas pasado. 100 00:04:53,300 --> 00:04:56,550 Habíamos estado usando arrays bastante felizmente como un útil si 101 00:04:56,550 --> 00:04:58,160 estructura de datos simplista. 102 00:04:58,160 --> 00:05:00,570 Entonces introdujimos estos, que por supuesto están vinculados listas. 103 00:05:00,570 --> 00:05:05,470 Y lo que fue una de las motivaciones para la introducción de esta estructura de datos? 104 00:05:05,470 --> 00:05:06,930 ¿Sí? 105 00:05:06,930 --> 00:05:07,250 ¿Qué es eso? 106 00:05:07,250 --> 00:05:08,080 >> AUDIENCIA: Dynamic tamaño. 107 00:05:08,080 --> 00:05:09,040 >> DAVID MALAN: Dynamic tamaño. 108 00:05:09,040 --> 00:05:11,890 Así, mientras que en la matriz, lo que tiene que conocer su tamaño con anticipación cuándo 109 00:05:11,890 --> 00:05:12,740 asigna él. 110 00:05:12,740 --> 00:05:14,380 En lista enlazada, no lo sabes tiene que saber eso. 111 00:05:14,380 --> 00:05:17,610 Usted puede simplemente malloc, o más en general, asignar otros 112 00:05:17,610 --> 00:05:20,720 nodo, por así decirlo, cada vez que desee insertar más datos. 113 00:05:20,720 --> 00:05:22,670 Y nodo no ha predeterminado significado. 114 00:05:22,670 --> 00:05:25,580 Es sólo un término genérico que describe algún tipo de contenedor que estamos 115 00:05:25,580 --> 00:05:29,610 utilizando en nuestra estructura de datos para almacenar algún artículo de interés, que en este 116 00:05:29,610 --> 00:05:31,750 caso resultan ser números enteros. 117 00:05:31,750 --> 00:05:33,160 >> Pero siempre hay una solución de compromiso. 118 00:05:33,160 --> 00:05:38,070 Así que llegamos tamaños dinámicos de los datos estructura, pero qué precio pagamos? 119 00:05:38,070 --> 00:05:40,040 ¿Cuál es el lado negativo de las listas enlazadas? 120 00:05:40,040 --> 00:05:41,006 ¿Sí? 121 00:05:41,006 --> 00:05:41,980 >> AUDIENCIA: Requiere más memoria. 122 00:05:41,980 --> 00:05:44,240 >> DAVID MALAN: Requiere más memoria, ¿cómo exactamente? 123 00:05:44,240 --> 00:05:46,440 >> AUDIENCIA: [inaudible]. 124 00:05:46,440 --> 00:05:47,050 >> DAVID MALAN: Exactamente. 125 00:05:47,050 --> 00:05:50,460 Así que ahora que hemos punteros ocupar memoria adicional que previamente 126 00:05:50,460 --> 00:05:53,040 no era necesario, porque la ventaja de una matriz, por supuesto, es que 127 00:05:53,040 --> 00:05:54,860 todo está contigua, de vuelta de espalda con espalda, lo que 128 00:05:54,860 --> 00:05:56,380 le da acceso aleatorio. 129 00:05:56,380 --> 00:06:00,710 Porque sólo mediante el uso de corchetes notación, o más técnicamente puntero 130 00:06:00,710 --> 00:06:03,580 aritmética, adición muy simple, se puede acceder a cualquier 131 00:06:03,580 --> 00:06:05,700 elementos en tiempo constante. 132 00:06:05,700 --> 00:06:08,975 Y de hecho, eso es un poco haciendo alusión a otro precio que estamos pagando con un 133 00:06:08,975 --> 00:06:09,760 lista enlazada. 134 00:06:09,760 --> 00:06:13,890 >> ¿Qué sucede con el tiempo de ejecución de algo así como la búsqueda, si quiero 135 00:06:13,890 --> 00:06:17,270 encontrar algo de valor y en el interior de una lista enlazada? 136 00:06:17,270 --> 00:06:20,290 Lo que se convierte en mi tiempo de ejecución? 137 00:06:20,290 --> 00:06:21,560 Big O de n. 138 00:06:21,560 --> 00:06:24,060 Si se ordena a? 139 00:06:24,060 --> 00:06:25,440 ¿Qué pasa si ordenado de la estructura de datos? 140 00:06:25,440 --> 00:06:28,640 ¿Puedo hacer algo mejor que grande O de n para la búsqueda? 141 00:06:28,640 --> 00:06:31,700 No, porque en el peor de los casos podría muy bien ser ordenados, pero el número 142 00:06:31,700 --> 00:06:32,950 usted está buscando podría ser grande. 143 00:06:32,950 --> 00:06:35,370 Puede ser que sea el número 100, que que podría pasar a ser todo 144 00:06:35,370 --> 00:06:36,410 la forma en el extremo. 145 00:06:36,410 --> 00:06:39,950 Y debido a que sólo se puede acceder a una ligada lista de esta aplicación por 146 00:06:39,950 --> 00:06:42,690 camino de su primer nodo, eres todavía un poco fuera de suerte. 147 00:06:42,690 --> 00:06:47,450 Usted tiene que atravesar todo el asunto de principio a fin con el fin de encontrar 148 00:06:47,450 --> 00:06:49,150 ese gran valor, como 100. 149 00:06:49,150 --> 00:06:51,350 O, para determinar si es ni siquiera existe. 150 00:06:51,350 --> 00:06:55,960 >> Así que no podemos hacer lo que en un algoritmo de datos estructura que se parece a esto? 151 00:06:55,960 --> 00:06:59,460 No podemos hacer la búsqueda binaria, porque búsqueda binaria requiere que teníamos 152 00:06:59,460 --> 00:07:00,740 de acceso aleatorio. 153 00:07:00,740 --> 00:07:04,500 Podríamos saltar de un lugar a ubicación sin tener que seguir 154 00:07:04,500 --> 00:07:07,080 estas migas de pan en forma de todos estos indicadores. 155 00:07:07,080 --> 00:07:08,300 >> Ahora, ¿cómo implementamos esto? 156 00:07:08,300 --> 00:07:12,830 Bueno, si vamos a la pantalla de aquí, si podemos volver a implementar rápidamente estos datos 157 00:07:12,830 --> 00:07:13,440 estructura - 158 00:07:13,440 --> 00:07:15,670 mi escritura no es tan muy bien aquí, pero lo intentaremos. 159 00:07:15,670 --> 00:07:22,030 Así struct typedef, y lo que hizo que quiere llamar a esta cosa aquí? 160 00:07:22,030 --> 00:07:22,960 Nodo. 161 00:07:22,960 --> 00:07:24,580 Así que voy a que podamos empezar. 162 00:07:24,580 --> 00:07:27,860 Y ahora, ¿qué tiene que estar dentro del la estructura de datos para que individualmente 163 00:07:27,860 --> 00:07:28,430 lista enlazada? 164 00:07:28,430 --> 00:07:29,950 ¿Cuántos campos? 165 00:07:29,950 --> 00:07:30,450 >> Así que dos. 166 00:07:30,450 --> 00:07:31,570 Uno de ellos es bastante fácil. 167 00:07:31,570 --> 00:07:33,050 Así int n. 168 00:07:33,050 --> 00:07:35,930 Y podríamos llamar n todo lo que queramos, pero debe ser un int si estamos 169 00:07:35,930 --> 00:07:37,660 la implementación de una lista enlazada para ints. 170 00:07:37,660 --> 00:07:41,920 Y ahora lo que hace el segundo campo tiene que ser? 171 00:07:41,920 --> 00:07:43,460 Struct nodo *. 172 00:07:43,460 --> 00:07:50,570 Así que si lo hago struct nodo *, y luego me puede llamar a esto también lo que yo quiera, 173 00:07:50,570 --> 00:07:53,510 pero para que quede claro que llamaré lo siguiente, ya que hemos estado haciendo. 174 00:07:53,510 --> 00:07:55,270 Y luego voy a cerrar mis llaves. 175 00:07:55,270 --> 00:08:00,700 >> Y ahora, como la última vez, Puse nodo aquí abajo. 176 00:08:00,700 --> 00:08:03,830 Pero si estoy declarando esto es como un nodo, ¿por qué me molesto estar tan 177 00:08:03,830 --> 00:08:07,320 verbose aquí en declarar struct nodo * siguiente, en contraposición 178 00:08:07,320 --> 00:08:09,210 al nodo sólo * siguiente? 179 00:08:09,210 --> 00:08:09,904 ¿Sí? 180 00:08:09,904 --> 00:08:12,810 >> AUDIENCIA: [inaudible]. 181 00:08:12,810 --> 00:08:14,050 >> DAVID MALAN: Exactamente. 182 00:08:14,050 --> 00:08:14,530 Exactamente. 183 00:08:14,530 --> 00:08:18,320 Debido C realmente te lleva literalmente y sólo ve la definición de nodo 184 00:08:18,320 --> 00:08:21,230 hasta aquí, no se puede referirse a ella aquí. 185 00:08:21,230 --> 00:08:24,760 Así que tenemos esta clase de preventivo declaración aquí, que es reconocidamente 186 00:08:24,760 --> 00:08:25,390 más detallado. 187 00:08:25,390 --> 00:08:27,810 Nodo de estructura, que los medios ahora podemos acceder a ella 188 00:08:27,810 --> 00:08:29,760 en el interior de la estructura de datos. 189 00:08:29,760 --> 00:08:33,370 >> Y en un aparte, porque se trata de cada vez un poco más subjetiva ahora, 190 00:08:33,370 --> 00:08:36,230 la estrella técnicamente puede ir aquí, puede ir aquí, puede 191 00:08:36,230 --> 00:08:37,179 incluso ir en el medio. 192 00:08:37,179 --> 00:08:39,890 Hemos adoptado, en la guía de estilo para el curso, la convención de poner 193 00:08:39,890 --> 00:08:42,299 la estrella junto a los datos escriba, que en este caso, 194 00:08:42,299 --> 00:08:43,460 sería nodo de estructura. 195 00:08:43,460 --> 00:08:46,620 Pero darse cuenta de una gran cantidad de libros de texto y referencias en línea, es posible que de hecho 196 00:08:46,620 --> 00:08:48,450 ver que en el otro lado. 197 00:08:48,450 --> 00:08:52,200 Pero sólo se dan cuenta de que tanto en realidad trabaja y debe ser simplemente 198 00:08:52,200 --> 00:08:52,970 consistente. 199 00:08:52,970 --> 00:08:53,580 >> Está bien. 200 00:08:53,580 --> 00:08:55,630 Así que esa fue nuestra declaración del nodo de estructura. 201 00:08:55,630 --> 00:08:59,430 Pero luego empezamos a hacer más cosas sofisticadas. 202 00:08:59,430 --> 00:09:03,410 Por ejemplo, decidimos introducir algo así como una tabla hash. 203 00:09:03,410 --> 00:09:08,160 Así que aquí es una tabla hash de tamaño n, indexada desde 0 en la parte superior izquierda de n 204 00:09:08,160 --> 00:09:09,690 menos 1 en la parte inferior izquierda. 205 00:09:09,690 --> 00:09:11,640 Esto podría ser un hash mesa para nada. 206 00:09:11,640 --> 00:09:15,340 Pero, ¿qué tipo de cosas qué hablamos sobre el uso de una tabla hash para? 207 00:09:15,340 --> 00:09:18,370 Almacenamiento de qué? 208 00:09:18,370 --> 00:09:18,800 >> Nombres. 209 00:09:18,800 --> 00:09:20,870 Podríamos hacer nombres como hicimos la última vez. 210 00:09:20,870 --> 00:09:22,200 Y realmente, puede almacenar cualquier cosa. 211 00:09:22,200 --> 00:09:24,640 Y vamos a ver esto de nuevo en PHP y JavaScript. 212 00:09:24,640 --> 00:09:28,550 Una tabla hash es una buena especie de Suiza Navaja que le permite almacenar 213 00:09:28,550 --> 00:09:33,690 casi todo lo que quieras dentro de que mediante la asociación de teclas con los valores. 214 00:09:33,690 --> 00:09:34,770 Teclas con valores. 215 00:09:34,770 --> 00:09:37,800 >> Ahora en este caso sencillo, nuestra claves son sólo números. 216 00:09:37,800 --> 00:09:40,380 Estamos implementando un hash tabla como una matriz. 217 00:09:40,380 --> 00:09:43,500 Y así las claves son 0, 1, 2, y así sucesivamente. 218 00:09:43,500 --> 00:09:47,200 Y así, nosotros, como seres humanos, decidió el pasado semana que usted sabe qué, si estamos 219 00:09:47,200 --> 00:09:50,410 va a almacenar nombres, vamos a arbitrariamente, pero bastante razonable, 220 00:09:50,410 --> 00:09:54,680 asumir que Alice, un nombre de A, se acaba de ser indexados en 0. 221 00:09:54,680 --> 00:09:58,030 Y Bob, un nombre de B, se indexará en 1, y así sucesivamente. 222 00:09:58,030 --> 00:10:02,490 Así que tuvimos una correspondencia entre las entradas, que son cadenas, y el hash 223 00:10:02,490 --> 00:10:04,560 lugares, que son números. 224 00:10:04,560 --> 00:10:07,740 >> Por lo tanto ese proceso se conoce generalmente como una función de hash, y usted realmente puede 225 00:10:07,740 --> 00:10:09,130 implementarlo en el código. 226 00:10:09,130 --> 00:10:12,080 Si quisiera aplicar una función hash que hace exactamente lo que 227 00:10:12,080 --> 00:10:17,070 se acaba de describir de la última vez, yo podría declarar una función que toma como 228 00:10:17,070 --> 00:10:18,330 de entrada, por ejemplo - 229 00:10:18,330 --> 00:10:22,190 y vamos a hacer esto en este pantalla aquí. 230 00:10:22,190 --> 00:10:26,180 Si quisiera aplicar un hash función, yo podría decir 231 00:10:26,180 --> 00:10:27,410 algo como esto. 232 00:10:27,410 --> 00:10:29,030 >> Se va a devolver un int. 233 00:10:29,030 --> 00:10:33,600 Va a ser llamado hash, y es va a aceptar como argumento una 234 00:10:33,600 --> 00:10:38,920 cadena, o podemos ser más apropiado ahora, y decir char *, que llamaremos s. 235 00:10:38,920 --> 00:10:43,840 Y entonces todo esta función tiene que ver, en última instancia, es devolver un int. 236 00:10:43,840 --> 00:10:45,990 Ahora, cómo lo hace que el poder no ser tan clara. 237 00:10:45,990 --> 00:10:49,510 Voy a poner en práctica esto sin ninguna forma de comprobación de errores en estos momentos. 238 00:10:49,510 --> 00:10:55,740 Yo sólo voy a decir a ciegas, el retorno lo que esté a escuadra s 0, menos, 239 00:10:55,740 --> 00:10:58,850 digamos, la capital un punto y coma. 240 00:10:58,850 --> 00:10:59,960 >> Totalmente roto. 241 00:10:59,960 --> 00:11:02,620 No es perfecto, porque uno, lo que si s es nulo? 242 00:11:02,620 --> 00:11:04,000 Las cosas malas van a suceder. 243 00:11:04,000 --> 00:11:07,940 Dos, ¿y si la primera letra en este nombre no es una letra mayúscula? 244 00:11:07,940 --> 00:11:09,860 Eso no va a girar bien tampoco. 245 00:11:09,860 --> 00:11:11,970 Puede ser que sea una letra minúscula o no una carta a todos. 246 00:11:11,970 --> 00:11:15,520 Así que totalmente margen de mejora, pero esta es la idea básica. 247 00:11:15,520 --> 00:11:19,010 >> Lo que describimos la semana pasada verbalmente como sólo un proceso de asignación de Alice a 248 00:11:19,010 --> 00:11:23,360 0 y Bob a 1 se puede expresar ciertamente más formulaically como C 249 00:11:23,360 --> 00:11:24,320 funcionar aquí. 250 00:11:24,320 --> 00:11:28,630 Llamé de nuevo hash, toma una cadena como de entrada, y entonces de alguna manera hace algo 251 00:11:28,630 --> 00:11:31,020 con esa entrada para producir una salida. 252 00:11:31,020 --> 00:11:34,130 No muy diferente de nuestra descripción cuadro negro lo que hemos hecho siempre. 253 00:11:34,130 --> 00:11:36,550 No sé cómo podría ser trabajo debajo de la capucha. 254 00:11:36,550 --> 00:11:40,120 >> Para problemas 6, uno de los retos es para que usted decida qué 255 00:11:40,120 --> 00:11:41,920 Será su función hash? 256 00:11:41,920 --> 00:11:45,760 ¿Qué va a estar dentro de ese negro caja, y, presumiblemente, va a ser un 257 00:11:45,760 --> 00:11:50,380 poco más interesante que esto, y definitivamente más propenso a errores 258 00:11:50,380 --> 00:11:53,180 comprobar que este particular, aplicación. 259 00:11:53,180 --> 00:11:54,580 >> Pero pueden surgir problemas, ¿verdad? 260 00:11:54,580 --> 00:11:57,760 Si tenemos una estructura de datos como este uno, lo que es uno de los problemas 261 00:11:57,760 --> 00:12:01,600 se puede ejecutar en el transcurso del tiempo a medida que inserta más y más nombres en la 262 00:12:01,600 --> 00:12:02,880 la tabla de hash? 263 00:12:02,880 --> 00:12:04,630 Usted consigue colisiones, ¿verdad? 264 00:12:04,630 --> 00:12:07,560 ¿Qué pasa si usted tiene Alice y Aarón, dos personas cuyos nombres sucedido 265 00:12:07,560 --> 00:12:08,190 comenzar con A? 266 00:12:08,190 --> 00:12:11,660 Esto plantea la pregunta, en la que poner la segunda como un nombre? 267 00:12:11,660 --> 00:12:15,050 >> Bueno, tal vez ingenuamente, sólo hay que poner donde Bob pertenece, pero Bob es 268 00:12:15,050 --> 00:12:17,300 tipo de atornillado si intenta inserte su nombre al lado y 269 00:12:17,300 --> 00:12:18,240 no hay sitio para él. 270 00:12:18,240 --> 00:12:21,400 Así que se podría poner Bob dónde está Charlie, y se puede imaginar esto muy rápidamente 271 00:12:21,400 --> 00:12:23,020 delegar en un poco de un desastre. 272 00:12:23,020 --> 00:12:25,600 Algo lineal en el final, donde se sólo hay que buscar todo el asunto 273 00:12:25,600 --> 00:12:28,190 en busca de Alice o Bob o Aaron o Charlie. 274 00:12:28,190 --> 00:12:33,230 >> Así que en lugar hemos propuesto, en lugar de linealmente el sondeo de espacios abiertos 275 00:12:33,230 --> 00:12:36,450 y dejándose los nombres allí, propuesto un enfoque más elegante. 276 00:12:36,450 --> 00:12:41,740 Una tabla hash implementado todavía con un array de índices, pero el tipo de datos de 277 00:12:41,740 --> 00:12:44,500 esos índices ya eran punteros. 278 00:12:44,500 --> 00:12:47,360 Punteros a qué? 279 00:12:47,360 --> 00:12:48,730 Punteros a las listas enlazadas. 280 00:12:48,730 --> 00:12:53,330 >> Porque recordemos que una lista enlazada es en realidad sólo un puntero a un nodo, y 281 00:12:53,330 --> 00:12:57,110 el nodo tiene un campo siguiente, y que el nodo tiene un campo siguiente, y así sucesivamente. 282 00:12:57,110 --> 00:13:00,690 Así que ahora puede pensar en este conjunto de el lado de la mano izquierda de una tabla hash como 283 00:13:00,690 --> 00:13:01,820 que conduce a una lista enlazada. 284 00:13:01,820 --> 00:13:07,000 La ventaja de que es si usted consigue un colisión entre Alice y Aarón, 285 00:13:07,000 --> 00:13:09,300 ¿qué hacer con el segunda de estas personas? 286 00:13:09,300 --> 00:13:14,150 Sólo le conceden a la final, o incluso el principio 287 00:13:14,150 --> 00:13:15,490 de esa lista enlazada. 288 00:13:15,490 --> 00:13:17,340 >> Y, de hecho, vamos a través de fideos que por sólo un segundo. 289 00:13:17,340 --> 00:13:18,640 ¿Dónde tendría la mayoría del sentido? 290 00:13:18,640 --> 00:13:22,060 Si inserto Alice y ella termina en el primer lugar, entonces yo trato de 291 00:13:22,060 --> 00:13:25,310 inserte el nombre de Aarón, y no hay obviamente una colisión, debo poner 292 00:13:25,310 --> 00:13:27,400 él al principio de la lista enlazada? 293 00:13:27,400 --> 00:13:30,944 Eso es por lo que la primera ubicación, o al final? 294 00:13:30,944 --> 00:13:31,440 >> AUDIENCIA: [inaudible]. 295 00:13:31,440 --> 00:13:31,990 >> DAVID MALAN: OK. 296 00:13:31,990 --> 00:13:32,490 He oído que comienza. 297 00:13:32,490 --> 00:13:33,903 ¿Por qué al principio? 298 00:13:33,903 --> 00:13:34,750 >> AUDIENCIA: [inaudible]. 299 00:13:34,750 --> 00:13:34,940 >> DAVID MALAN: OK. 300 00:13:34,940 --> 00:13:36,520 Es alfabético, por lo que es bueno. 301 00:13:36,520 --> 00:13:37,330 Esa es una buena propiedad. 302 00:13:37,330 --> 00:13:39,335 Se me va a ahorrar un poco de tiempo potencialmente. 303 00:13:39,335 --> 00:13:43,290 No me deja hacer búsqueda binaria, pero podrían al menos ser capaz de romper 304 00:13:43,290 --> 00:13:47,340 de un bucle si me doy cuenta, bueno, estoy camino pasado fueron Aarón sería en este 305 00:13:47,340 --> 00:13:48,310 ordenados lista enlazada. 306 00:13:48,310 --> 00:13:50,360 Yo no tengo que perder el tiempo buscando todo el camino hasta el final. 307 00:13:50,360 --> 00:13:51,530 Así que eso es razonable. 308 00:13:51,530 --> 00:13:54,710 ¿Por qué más podría querer insertar el nombre de chocar en la 309 00:13:54,710 --> 00:13:56,660 principio de la lista? 310 00:13:56,660 --> 00:13:57,397 ¿Qué es eso? 311 00:13:57,397 --> 00:13:58,680 >> AUDIENCIA: [inaudible]. 312 00:13:58,680 --> 00:14:00,820 >> DAVID MALAN: Podría tomar mucho tiempo para llegar a la final de la lista. 313 00:14:00,820 --> 00:14:02,490 Y, de hecho, más y más. 314 00:14:02,490 --> 00:14:04,920 Cuantos más nombres que se insertan comenzar con A, el más largo que 315 00:14:04,920 --> 00:14:06,280 la cadena se va a poner. 316 00:14:06,280 --> 00:14:07,890 Cuanto más tiempo que enlazada lista se va a conseguir. 317 00:14:07,890 --> 00:14:09,420 Así que usted es realmente justo perdiendo el tiempo. 318 00:14:09,420 --> 00:14:14,070 Tal vez usted es mejor de mantener tiempo de inserción constante, gran O de 1, 319 00:14:14,070 --> 00:14:18,470 poniendo siempre el nombre de chocar en el principio de la lista enlazada, 320 00:14:18,470 --> 00:14:21,230 y no preocuparse tanto acerca de la ordenación. 321 00:14:21,230 --> 00:14:22,600 >> ¿Cuál es la mejor respuesta? 322 00:14:22,600 --> 00:14:23,320 No está claro. 323 00:14:23,320 --> 00:14:26,140 Es algo que depende de lo que el distribución es, cuál es el patrón 324 00:14:26,140 --> 00:14:27,850 de los nombres que va a insertar. 325 00:14:27,850 --> 00:14:29,430 No es necesariamente una respuesta obvia. 326 00:14:29,430 --> 00:14:33,100 Pero aquí, de nuevo, es una oportunidad de diseño. 327 00:14:33,100 --> 00:14:37,220 >> Así que a continuación analizamos esta cosa, que es realmente la otra gran oportunidad 328 00:14:37,220 --> 00:14:38,180 de p-set 6. 329 00:14:38,180 --> 00:14:41,770 Y me di cuenta, si no lo ha hecho, Zamyla sumerge en ambos, el hash 330 00:14:41,770 --> 00:14:43,260 mesas y países, en más detalle. 331 00:14:43,260 --> 00:14:45,630 Y el video guía se incrustado en p-establecer especificaciones. 332 00:14:45,630 --> 00:14:46,590 Este era un trie - 333 00:14:46,590 --> 00:14:51,670 T-R-I-E. Y lo que era interesante de esto fue que el tiempo de ejecución 334 00:14:51,670 --> 00:14:59,510 de la búsqueda de un nombre, como Maxwell la última vez, era gran O de qué? 335 00:14:59,510 --> 00:15:01,040 ¿Qué es eso? 336 00:15:01,040 --> 00:15:01,920 >> AUDIENCIA: El número de letras. 337 00:15:01,920 --> 00:15:02,550 >> DAVID MALAN: Número de letras. 338 00:15:02,550 --> 00:15:03,210 Escuché dos cosas. 339 00:15:03,210 --> 00:15:04,630 Número de letras y constante de tiempo. 340 00:15:04,630 --> 00:15:05,540 Así que vamos a ir con eso primero. 341 00:15:05,540 --> 00:15:06,410 El número de letras. 342 00:15:06,410 --> 00:15:10,195 Pues bien, esta estructura de datos, recuperación, es como un árbol, un árbol de la familia, cada uno de 343 00:15:10,195 --> 00:15:12,860 cuyos nodos se componen de matrices. 344 00:15:12,860 --> 00:15:16,300 Y esos arreglos son apuntadores a otros tales nodos u otros tales 345 00:15:16,300 --> 00:15:17,670 matrices en el árbol. 346 00:15:17,670 --> 00:15:22,890 >> Así que si queríamos luego determinar si Maxwell está aquí dentro, yo podría ir 347 00:15:22,890 --> 00:15:26,890 a la primera serie, en la parte superior de el árbol, la raíz de la llamada, la parte superior de 348 00:15:26,890 --> 00:15:30,521 trie y, a continuación, siga el puntero del m, entonces el un puntero, entonces x, 349 00:15:30,521 --> 00:15:31,710 w, e, l, l. 350 00:15:31,710 --> 00:15:34,910 Y entonces, cuando veo algún símbolo especial, denotada aquí como un triángulo. 351 00:15:34,910 --> 00:15:38,480 En el código verás que proponemos que implementado como un bool, sólo decir que sí 352 00:15:38,480 --> 00:15:40,540 o no, una palabra se detiene aquí. 353 00:15:40,540 --> 00:15:45,270 >> Bueno, una vez que hemos ido a la M-A-X-W-E-L-L, se siente como siete, tal vez 354 00:15:45,270 --> 00:15:48,910 ocho si vamos un pasado, ocho pasos para encontrar Maxwell. 355 00:15:48,910 --> 00:15:53,050 ¿O vamos a llamarlo K. Pero recuerdan el pasado tiempo, sostuve que si hay 356 00:15:53,050 --> 00:15:57,540 realista una longitud máxima en un palabra, como 40 y tantos y tantos personajes, un 357 00:15:57,540 --> 00:16:00,810 longitud máxima implica un valor constante. 358 00:16:00,810 --> 00:16:05,770 Así que en realidad, sí, es técnicamente gran O de 8 o 7, o en realidad gran O de K. Pero 359 00:16:05,770 --> 00:16:09,420 si hay una tapa finito en lo K podría ser, es una constante. 360 00:16:09,420 --> 00:16:12,080 Y lo que es gran O de 1 a el final del día. 361 00:16:12,080 --> 00:16:13,040 >> No en el mundo real. 362 00:16:13,040 --> 00:16:15,960 No cuando usted realmente empezar a ver el reloj como correr de su programa. 363 00:16:15,960 --> 00:16:20,690 Está absolutamente va a ser un poco más lento que verdaderamente constante 364 00:16:20,690 --> 00:16:21,840 tiempo con un solo paso. 365 00:16:21,840 --> 00:16:25,540 Va a ser siete u ocho pasos, pero eso es mucho, mucho mejor 366 00:16:25,540 --> 00:16:30,080 de un algoritmo como el gran O de n que depende del tamaño de lo que hay en el 367 00:16:30,080 --> 00:16:31,220 estructura de datos. 368 00:16:31,220 --> 00:16:34,970 >> Observe el alza aquí es que podemos insertar un millón más nombres en esta 369 00:16:34,970 --> 00:16:38,170 estructura de datos, pero la cantidad de pasos más es que va a llevarnos a encontrar 370 00:16:38,170 --> 00:16:40,480 Maxwell, en ese caso? 371 00:16:40,480 --> 00:16:40,780 Ninguno. 372 00:16:40,780 --> 00:16:41,820 Es afectado. 373 00:16:41,820 --> 00:16:45,480 Y hasta la fecha, no creo que hemos visto un ejemplo de una estructura de datos o un 374 00:16:45,480 --> 00:16:48,560 algoritmo que era completamente afectado por externa 375 00:16:48,560 --> 00:16:50,040 conductas como esas. 376 00:16:50,040 --> 00:16:51,160 Pero esto no puede ser increíble. 377 00:16:51,160 --> 00:16:52,900 Esto no puede ser la única solución para el p-set 378 00:16:52,900 --> 00:16:53,570 >> Y no lo es. 379 00:16:53,570 --> 00:16:55,980 Esto no es necesariamente los datos estructura que debe gravitar hacia, 380 00:16:55,980 --> 00:16:58,220 porque las tablas hash como, equilibrio. 381 00:16:58,220 --> 00:17:00,500 ¿Cuál es el precio que se paga aquí? 382 00:17:00,500 --> 00:17:00,940 Memoria. 383 00:17:00,940 --> 00:17:02,890 Quiero decir, este es un atroz cantidad de memoria. 384 00:17:02,890 --> 00:17:05,569 Y no se puede ver bien aquí porque el autor de esta imagen 385 00:17:05,569 --> 00:17:09,420 obviamente truncado todos los arrays, y no estamos viendo un montón de doctores y 386 00:17:09,420 --> 00:17:12,700 B y C de Q y de e Y de y de Z en estas matrices. 387 00:17:12,700 --> 00:17:13,630 Pero están ahí. 388 00:17:13,630 --> 00:17:17,660 >> Cada uno de estos nodos es toda una serie de algunos 26 o más bytes, cada uno de 389 00:17:17,660 --> 00:17:19,170 lo que representa una letra. 390 00:17:19,170 --> 00:17:22,920 27 en nuestro caso, por lo que podemos apoyar apóstrofes en el problema establecido. 391 00:17:22,920 --> 00:17:27,030 Así que esta estructura de datos es realmente, muy densa y amplia. 392 00:17:27,030 --> 00:17:30,880 Y eso solo podría terminar la desaceleración las cosas, o al menos le cuesta un 393 00:17:30,880 --> 00:17:32,240 mucho más espacio. 394 00:17:32,240 --> 00:17:34,020 Pero una vez más, podemos sacar comparaciones aquí. 395 00:17:34,020 --> 00:17:39,190 >> Recordemos hace un tiempo, hemos logrado mucho más emocionante tiempo de funcionamiento en la clasificación 396 00:17:39,190 --> 00:17:42,880 cuando usamos la combinación de estilo, pero el precio que pagamos para lograr n log n de fusión 397 00:17:42,880 --> 00:17:46,930 especie requiere que pasemos más lo que los recursos? 398 00:17:46,930 --> 00:17:47,690 Más espacio. 399 00:17:47,690 --> 00:17:50,530 Necesitábamos una matriz secundaria a copiar a la gente a, al igual que 400 00:17:50,530 --> 00:17:51,620 que hicimos aquí en el escenario. 401 00:17:51,620 --> 00:17:55,880 Así que de nuevo, no hay claros ganadores, pero sólo el diseño subjetiva 402 00:17:55,880 --> 00:17:57,710 decisiones que tomar. 403 00:17:57,710 --> 00:17:58,060 >> Está bien. 404 00:17:58,060 --> 00:17:59,130 Así que ¿qué tal esto? 405 00:17:59,130 --> 00:18:02,050 Cualquier persona reconoce que D-Hall? 406 00:18:02,050 --> 00:18:02,440 Aceptar. 407 00:18:02,440 --> 00:18:03,170 Así que tres de nosotros lo hacemos. 408 00:18:03,170 --> 00:18:03,750 Mather House. 409 00:18:03,750 --> 00:18:05,070 Así que esto es para una cena de Mather. 410 00:18:05,070 --> 00:18:09,650 Apuesto a todos los comedores tienen pilas de bandejas les gusta esto. 411 00:18:09,650 --> 00:18:11,950 Y esto es realmente representativa de algo que hemos 412 00:18:11,950 --> 00:18:13,050 obviamente ya visto. 413 00:18:13,050 --> 00:18:14,850 Lo llamamos literalmente una pila. 414 00:18:14,850 --> 00:18:18,970 Y la pila, en términos de su la memoria de la computadora, es que los datos se 415 00:18:18,970 --> 00:18:20,460 mientras que las funciones están siendo llamados. 416 00:18:20,460 --> 00:18:23,410 >> Por ejemplo, ¿qué tipo de cosas van en la pila con respecto a la 417 00:18:23,410 --> 00:18:27,420 diseño de la memoria que hemos discutido en semana pasado? 418 00:18:27,420 --> 00:18:28,736 ¿Qué es eso? 419 00:18:28,736 --> 00:18:29,670 >> AUDIENCIA: Las llamadas a funciones. 420 00:18:29,670 --> 00:18:30,260 >> DAVID MALAN: lo siento. 421 00:18:30,260 --> 00:18:31,210 >> AUDIENCIA: Las llamadas a funciones. 422 00:18:31,210 --> 00:18:33,590 >> DAVID MALAN: Las llamadas a funciones, pero en concreto, lo que hay dentro de cada uno de 423 00:18:33,590 --> 00:18:35,340 esos cuadros? 424 00:18:35,340 --> 00:18:37,220 ¿Qué tipo de cosas? 425 00:18:37,220 --> 00:18:37,460 Sí. 426 00:18:37,460 --> 00:18:38,500 Por lo tanto las variables locales. 427 00:18:38,500 --> 00:18:43,080 Cada vez que necesitábamos algo de almacenamiento local, como un argumento, o int i, o int 428 00:18:43,080 --> 00:18:45,940 temp, o lo que sea lo local variable es, hemos estado 429 00:18:45,940 --> 00:18:47,210 poner que en la pila. 430 00:18:47,210 --> 00:18:49,610 Y lo llamamos una pila porque de esa idea de estratificación. 431 00:18:49,610 --> 00:18:52,940 Sólo tipo de partidos con la realidad, el concepto de los mismos. 432 00:18:52,940 --> 00:18:56,650 >> Pero resulta que una pila puede también ser visto como una estructura de datos, una 433 00:18:56,650 --> 00:19:00,110 alternativa a una matriz, una alternativa a una lista enlazada. 434 00:19:00,110 --> 00:19:02,770 Algo conceptualmente más interesante que todavía puede haber 435 00:19:02,770 --> 00:19:06,030 implementado utilizando cualquiera de los cosas, pero es un tipo diferente de 436 00:19:06,030 --> 00:19:09,140 estructura de datos de apoyo, de verdad, sólo dos operaciones. 437 00:19:09,140 --> 00:19:11,000 Pero puedes agregar más de lujo características que éstos. 438 00:19:11,000 --> 00:19:12,180 Pero estos son los fundamentos - 439 00:19:12,180 --> 00:19:13,510 insertar y extraer. 440 00:19:13,510 --> 00:19:19,240 >> Y la idea con una pila es que si yo tenemos aquí, con o sin Annenberg 441 00:19:19,240 --> 00:19:22,880 saber, una bandeja de al lado con el número 9 en él. 442 00:19:22,880 --> 00:19:23,870 Así que sólo un int. 443 00:19:23,870 --> 00:19:26,990 Y quiero llevar este a los datos estructura, que actualmente está vacía. 444 00:19:26,990 --> 00:19:28,790 Considere esto la parte inferior de la pila. 445 00:19:28,790 --> 00:19:33,150 Me gustaría llevar este número 9 en el pila, y ahora es justo ahí. 446 00:19:33,150 --> 00:19:36,040 >> Pero lo interesante de una pila es que si ahora quiero empujar 447 00:19:36,040 --> 00:19:40,210 algún otro valor, como 17, y me empujan esta en la pila, yo voy a hacer 448 00:19:40,210 --> 00:19:43,290 la única cosa intuitiva, sólo voy para ponerlo justo donde nosotros los humanos 449 00:19:43,290 --> 00:19:45,180 se inclina a poner, en la parte superior. 450 00:19:45,180 --> 00:19:48,850 Pero lo que es interesante ahora es, ¿cómo puedo conseguir a las 9? 451 00:19:48,850 --> 00:19:50,670 Usted sabe, yo no lo hago sin algún esfuerzo. 452 00:19:50,670 --> 00:19:54,070 >> Así que lo interesante de una pila es que por diseño, 453 00:19:54,070 --> 00:19:56,330 que es una estructura de datos LIFO. 454 00:19:56,330 --> 00:19:59,680 Manera tonta de describir último en entrar, primero en salir. 455 00:19:59,680 --> 00:20:03,280 Así que el último número de en este momento tenía 17 años. 456 00:20:03,280 --> 00:20:07,540 Así que si quiero hacer estallar algo fuera de la pila, sólo puede ser 17. 457 00:20:07,540 --> 00:20:11,890 Así que hay una orden obligatoria de operaciones aquí, donde el último elemento 458 00:20:11,890 --> 00:20:14,260 en tiene que ser la primera en salir. 459 00:20:14,260 --> 00:20:16,440 De ahí el acrónimo, LIFO. 460 00:20:16,440 --> 00:20:19,160 >> Entonces ¿por qué podría ser esto útil? 461 00:20:19,160 --> 00:20:22,690 ¿Son sus contextos en los que había quieren una estructura de datos como este? 462 00:20:22,690 --> 00:20:24,810 Bueno, ha sido sin duda útil interior de una computadora. 463 00:20:24,810 --> 00:20:29,050 Así que los sistemas operativos utilizan claramente esta tipo de estructura de datos para las pilas. 464 00:20:29,050 --> 00:20:32,800 También veremos la misma idea cuando se trata de páginas web. 465 00:20:32,800 --> 00:20:35,890 Así que esta semana y la próxima semana y más allá, y como iniciar la aplicación de web 466 00:20:35,890 --> 00:20:39,490 páginas en un lenguaje llamado HTML, puede realmente utilizar una estructura de datos como 467 00:20:39,490 --> 00:20:42,690 esto para determinar si la página tiene el formato correcto. 468 00:20:42,690 --> 00:20:47,170 Porque vamos a ver todas las páginas web siguen una especie de jerarquía, una escotadura 469 00:20:47,170 --> 00:20:52,030 que la voluntad, al final del día, ser un estructura de árbol debajo de la capucha. 470 00:20:52,030 --> 00:20:53,620 Así que más de eso en sólo un poco. 471 00:20:53,620 --> 00:20:56,560 >> Pero por ahora, vamos a proponer una momento, ¿cómo podemos ir sobre 472 00:20:56,560 --> 00:20:58,830 representa lo que una pila es? 473 00:20:58,830 --> 00:21:03,370 Permítanme proponer que implementamos una pila con código como este. 474 00:21:03,370 --> 00:21:07,990 Así que una pila va a tener dentro de ella dos cosas, una matriz, llamada bandejas, 475 00:21:07,990 --> 00:21:09,510 sólo para estar en consonancia con la demo. 476 00:21:09,510 --> 00:21:12,660 Y cada uno de los elementos de la matriz va a ser un tipo int. 477 00:21:12,660 --> 00:21:14,740 Y la capacidad es de suponer qué? 478 00:21:14,740 --> 00:21:18,796 Porque yo no he escrito el definición completa aquí. 479 00:21:18,796 --> 00:21:21,535 >> Es probablemente la máxima tamaño de la matriz. 480 00:21:21,535 --> 00:21:25,150 Y probablemente declarada como una fuerte definir en la parte superior del archivo, algunos 481 00:21:25,150 --> 00:21:28,450 tipo de constante como lo implica la mera capitalización. 482 00:21:28,450 --> 00:21:32,250 Así que en alguna parte de la capacidad se define como el tamaño máximo posible. 483 00:21:32,250 --> 00:21:35,590 Mientras tanto, en el interior de la estructura de datos conocido como una pila habrá 484 00:21:35,590 --> 00:21:38,630 ser un entero sólo conocido simplemente como tamaño. 485 00:21:38,630 --> 00:21:43,400 >> Así que si yo fuera a representar esta empresa pictóricamente, vamos a suponer que esta 486 00:21:43,400 --> 00:21:48,070 cuadro negro entero representa mi stack. 487 00:21:48,070 --> 00:21:50,070 En el interior de la misma es de dos variables. 488 00:21:50,070 --> 00:21:54,780 Así que voy a señalar a la uno primero como el tamaño. 489 00:21:54,780 --> 00:21:57,420 Y el segundo me voy dibujar como una matriz. 490 00:21:57,420 --> 00:22:01,060 >> Pero sólo para mantener las cosas ordenadas, Normalmente me gustaría llamar una matriz como 491 00:22:01,060 --> 00:22:04,910 esto, pero es un poco agradable si hacemos coincidir la realidad, o 492 00:22:04,910 --> 00:22:06,230 que coincida con el modelo mental. 493 00:22:06,230 --> 00:22:12,880 Así que déjame en vez dibujar la matriz verticalmente, lo que es justo, de nuevo, 494 00:22:12,880 --> 00:22:13,840 interpretación del artista. 495 00:22:13,840 --> 00:22:16,610 Realmente no importa lo que hay debajo del capó. 496 00:22:16,610 --> 00:22:20,350 Y vamos a decir que, por defecto, capacidad va a ser tres. 497 00:22:20,350 --> 00:22:23,480 Así que esta será la posición 0, este será ubicación 1, este 498 00:22:23,480 --> 00:22:25,740 será ubicación 2. 499 00:22:25,740 --> 00:22:29,330 >> Si me soborne con una bola de la tensión, lo haría alguien como para llegar y ejecutar el 500 00:22:29,330 --> 00:22:30,870 abordar aquí por un momento? 501 00:22:30,870 --> 00:22:31,960 Aceptar, vio primero la mano. 502 00:22:31,960 --> 00:22:33,950 Vamos arriba. 503 00:22:33,950 --> 00:22:36,500 Está bien. 504 00:22:36,500 --> 00:22:38,760 Así que creo que es Steven. 505 00:22:38,760 --> 00:22:40,035 Vamos arriba. 506 00:22:40,035 --> 00:22:40,770 Está bien. 507 00:22:40,770 --> 00:22:46,760 >> Pero supongamos ahora que rebobinar hasta el inicial estado del mundo en el que 508 00:22:46,760 --> 00:22:52,180 se acaba de declarar una pila, y es va a tener una capacidad de tres. 509 00:22:52,180 --> 00:22:54,470 Pero el tamaño todavía no se ha determinado. 510 00:22:54,470 --> 00:22:56,100 Bandejas aún no ha sido determinada. 511 00:22:56,100 --> 00:22:57,300 Así que un par de preguntas primero. 512 00:22:57,300 --> 00:23:01,310 Y te voy a dar usted micrófono a lo que puede participar más activamente en esto. 513 00:23:01,310 --> 00:23:05,190 >> Así que lo que está dentro de su tamaño en este momento a tiempo si todo lo que he hecho es 514 00:23:05,190 --> 00:23:09,340 declarado una pila con una línea de código? 515 00:23:09,340 --> 00:23:10,100 >> STEVEN: No mucho. 516 00:23:10,100 --> 00:23:12,080 >> DAVID MALAN: OK, no mucho. 517 00:23:12,080 --> 00:23:14,410 ¿Sabemos lo que hay dentro de su tamaño, Cómo podemos saber lo que hay dentro 518 00:23:14,410 --> 00:23:16,330 de esta variedad aquí? 519 00:23:16,330 --> 00:23:18,630 >> STEVEN: Just código aleatorio, ¿verdad? 520 00:23:18,630 --> 00:23:20,220 Just - 521 00:23:20,220 --> 00:23:23,230 >> DAVID MALAN: Sí, voy a llamarlo código, pero al azar - 522 00:23:23,230 --> 00:23:23,820 >> STEVEN: Cosas. 523 00:23:23,820 --> 00:23:28,290 >> DAVID MALAN: Cosas como aleatorio 524 00:23:28,290 --> 00:23:28,870 >> STEVEN: Bits. 525 00:23:28,870 --> 00:23:29,530 >> DAVID MALAN: Bits, ¿verdad? 526 00:23:29,530 --> 00:23:31,190 Así que los valores de la basura, ¿verdad? 527 00:23:31,190 --> 00:23:33,470 Así permutaciones de 0 de y 1. 528 00:23:33,470 --> 00:23:35,920 Los restos de usos anteriores de esta memoria. 529 00:23:35,920 --> 00:23:38,150 Y no se sabe muy bien cuáles son los valores somos, por lo que normalmente los alejaremos 530 00:23:38,150 --> 00:23:38,930 como signos de interrogación. 531 00:23:38,930 --> 00:23:41,990 >> Así que lo primero que estamos presumiblemente va a querer hacer aquí - 532 00:23:41,990 --> 00:23:46,630 y te voy a dar este campo en el interior de ahí el nombre - bandejas. 533 00:23:46,630 --> 00:23:49,540 ¿Qué debemos de suponer inicializar tamaño a si queremos 534 00:23:49,540 --> 00:23:51,040 empezar a utilizar esta pila? 535 00:23:51,040 --> 00:23:53,070 >> STEVEN: Bandeja está SUB 3. 536 00:23:53,070 --> 00:23:53,910 >> DAVID MALAN: Entonces, OK. 537 00:23:53,910 --> 00:23:56,710 Para que quede claro, se declara la capacidad en otros lugares como tres. 538 00:23:56,710 --> 00:23:58,570 Y eso es lo que he usado para asignar la matriz. 539 00:23:58,570 --> 00:24:03,535 El tamaño se va a hacer referencia a la cantidad de bandejas están actualmente en la pila. 540 00:24:03,535 --> 00:24:03,880 >> STEVEN: Zero. 541 00:24:03,880 --> 00:24:04,460 >> DAVID MALAN: Por lo tanto, debe ser cero. 542 00:24:04,460 --> 00:24:07,760 Así que adelante, y con cualquier dedo, dibujar un cero en tamaño. 543 00:24:07,760 --> 00:24:08,440 Está bien. 544 00:24:08,440 --> 00:24:10,920 Así que ahora, lo que hay dentro de este aquí, no sabemos. 545 00:24:10,920 --> 00:24:12,160 Estos son en realidad los valores de basura. 546 00:24:12,160 --> 00:24:14,800 Así que podríamos dibujar signos de interrogación, pero vamos a mantener el tablero limpio por ahora 547 00:24:14,800 --> 00:24:16,300 porque no importa lo que hay. 548 00:24:16,300 --> 00:24:19,130 No necesitamos para inicializar la matriz para nada, porque si sabemos que 549 00:24:19,130 --> 00:24:23,100 el tamaño de la pila es cero, bueno, no se debe mirar nada en 550 00:24:23,100 --> 00:24:25,590 esta matriz de todos modos en este punto en el tiempo. 551 00:24:25,590 --> 00:24:29,970 >> Así que ahora supongo que empujo la número 9 en la pila. 552 00:24:29,970 --> 00:24:33,750 ¿Cómo debemos actualizar la estructura de datos dentro de este recuadro negro? 553 00:24:33,750 --> 00:24:35,540 ¿Qué valores tienen que cambiar? 554 00:24:35,540 --> 00:24:36,200 >> STEVEN: Within - 555 00:24:36,200 --> 00:24:37,400 el tamaño? 556 00:24:37,400 --> 00:24:37,650 >> DAVID MALAN: OK. 557 00:24:37,650 --> 00:24:38,770 Tamaño Debe convertirse en lo que? 558 00:24:38,770 --> 00:24:39,580 >> STEVEN: Tamaño sería uno. 559 00:24:39,580 --> 00:24:39,870 >> DAVID MALAN: OK. 560 00:24:39,870 --> 00:24:41,110 Así que el tamaño debe ser uno. 561 00:24:41,110 --> 00:24:42,540 Así que usted puede hacer esto en un par de maneras. 562 00:24:42,540 --> 00:24:46,920 Te voy a dar, ya que su el dedo es una goma de borrar. 563 00:24:46,920 --> 00:24:47,260 Está bien. 564 00:24:47,260 --> 00:24:49,960 Entonces ahora el dedo es un pincel. 565 00:24:49,960 --> 00:24:50,330 Está bien. 566 00:24:50,330 --> 00:24:52,820 Y ahora ¿qué otra cosa tiene que cambiar, obviamente, en la estructura de datos? 567 00:24:52,820 --> 00:24:57,060 >> STEVEN: Estamos pasando de de abajo hacia arriba a 9. 568 00:24:57,060 --> 00:24:57,760 >> DAVID MALAN: 9. 569 00:24:57,760 --> 00:24:58,420 Bueno, bueno. 570 00:24:58,420 --> 00:25:01,550 Así que todavía no importa lo que está en ubicación de uno o dos, porque son 571 00:25:01,550 --> 00:25:04,520 valores de basura, pero no hay que molestarse buscando allí porque el tamaño es 572 00:25:04,520 --> 00:25:07,540 que nos dice que sólo el primer elemento en realidad es legítima. 573 00:25:07,540 --> 00:25:10,400 Así que ahora me empuje 17 en la lista. 574 00:25:10,400 --> 00:25:11,830 ¿Qué pasa con esta imagen? 575 00:25:11,830 --> 00:25:14,720 >> STEVEN: Tamaño Así que va a ir a dos. 576 00:25:14,720 --> 00:25:15,300 >> DAVID MALAN: OK. 577 00:25:15,300 --> 00:25:16,070 Eres eraser - 578 00:25:16,070 --> 00:25:16,810 ¡Uy. 579 00:25:16,810 --> 00:25:18,026 Usted es una goma de borrar. 580 00:25:18,026 --> 00:25:18,840 >> STEVEN: Borrador. 581 00:25:18,840 --> 00:25:19,720 >> DAVID MALAN: Eres un cepillo. 582 00:25:19,720 --> 00:25:20,560 >> STEVEN: Brush. 583 00:25:20,560 --> 00:25:20,920 >> DAVID MALAN: OK. 584 00:25:20,920 --> 00:25:21,600 ¿Y qué más? 585 00:25:21,600 --> 00:25:22,600 >> STEVEN: Y entonces - 586 00:25:22,600 --> 00:25:22,915 >> DAVID MALAN: Nos empujó 17. 587 00:25:22,915 --> 00:25:24,760 >> STEVEN: Nos pegamos 17 en la parte superior, por lo que - 588 00:25:24,760 --> 00:25:25,710 >> DAVID MALAN: OK, bueno. 589 00:25:25,710 --> 00:25:27,040 >> STEVEN: - caída hacia abajo. 590 00:25:27,040 --> 00:25:27,530 >> DAVID MALAN: Muy bien. 591 00:25:27,530 --> 00:25:27,940 Se está poniendo fácil. 592 00:25:27,940 --> 00:25:29,300 Yo no voy a ayudarle a este momento. 593 00:25:29,300 --> 00:25:30,510 Empuje 22. 594 00:25:30,510 --> 00:25:31,720 >> STEVEN: Hecho. 595 00:25:31,720 --> 00:25:34,870 Convertirse en una goma de borrar. 596 00:25:34,870 --> 00:25:37,340 Me estoy convirtiendo en un cepillo. 597 00:25:37,340 --> 00:25:39,340 Y entonces me estoy poniendo 22. 598 00:25:39,340 --> 00:25:40,100 >> DAVID MALAN: 22. 599 00:25:40,100 --> 00:25:40,620 Excelente. 600 00:25:40,620 --> 00:25:41,380 Así que una vez más. 601 00:25:41,380 --> 00:25:44,280 Ahora voy a empujar en la pila 26. 602 00:25:44,280 --> 00:25:46,350 >> STEVEN: Ooh. 603 00:25:46,350 --> 00:25:50,278 Oh Dios mío. 604 00:25:50,278 --> 00:25:52,520 Realmente me tomó por sorpresa. 605 00:25:52,520 --> 00:25:53,703 >> DAVID MALAN: No lo hiciste ver venir esto? 606 00:25:53,703 --> 00:25:55,930 >> STEVEN: No vi venir esto. 607 00:25:55,930 --> 00:25:58,756 ¿Podríamos volver a inicial de la capacidad? 608 00:25:58,756 --> 00:25:59,790 >> DAVID MALAN: Esa es una buena pregunta. 609 00:25:59,790 --> 00:26:02,360 Así que hemos tipo de nosotros mismos pintamos en una esquina aquí. 610 00:26:02,360 --> 00:26:06,740 Realmente no hay ninguna buena por Steven porque hemos asignado este array 611 00:26:06,740 --> 00:26:09,130 estáticamente, por así decirlo, el interior de la estructura de datos. 612 00:26:09,130 --> 00:26:12,170 Y hemos esencialmente codificamos que sea del tamaño de tres. 613 00:26:12,170 --> 00:26:14,170 Así que en realidad no podemos reasignarlo. 614 00:26:14,170 --> 00:26:20,020 >> Podríamos Si regresamos, nos bandejas redefinidos para ser un puntero que 615 00:26:20,020 --> 00:26:22,300 entonces usamos malloc para memoria de la mano de. 616 00:26:22,300 --> 00:26:25,050 Porque si tenemos la memoria de la pila a través de malloc, que 617 00:26:25,050 --> 00:26:26,430 podría entonces liberarlo. 618 00:26:26,430 --> 00:26:29,630 Pero antes de liberarla, podríamos reasignar un pedazo más grande de la memoria, 619 00:26:29,630 --> 00:26:31,330 actualizar el puntero, y así sucesivamente. 620 00:26:31,330 --> 00:26:33,500 Pero por ahora, esto es realmente lo mejor que podemos hacer. 621 00:26:33,500 --> 00:26:36,360 Empuje y pop son presumiblemente van a tener que señalar alguna de error. 622 00:26:36,360 --> 00:26:40,270 >> Así, por ejemplo, nuestra implementación de empuje podría devolver un bool que 623 00:26:40,270 --> 00:26:42,390 previamente devuelto cierto, cierto, cierto. 624 00:26:42,390 --> 00:26:48,390 Pero la cuarta vez, va a tener devuelva false, por ejemplo. 625 00:26:48,390 --> 00:26:48,540 Está bien. 626 00:26:48,540 --> 00:26:49,540 Muy bien hecho. 627 00:26:49,540 --> 00:26:50,060 Felicitaciones. 628 00:26:50,060 --> 00:26:52,160 Te has ganado tu bola de la tensión actual. 629 00:26:52,160 --> 00:26:53,110 >> [Aplausos] 630 00:26:53,110 --> 00:26:54,382 >> STEVEN: Gracias. 631 00:26:54,382 --> 00:26:55,680 >> DAVID MALAN: Gracias. 632 00:26:55,680 --> 00:26:59,740 OK, así que esto parece ser no mucho de un paso adelante, ¿no? 633 00:26:59,740 --> 00:27:01,410 Hemos descrito esta estructura de datos. 634 00:27:01,410 --> 00:27:02,320 Ha sido convincente, ¿no? 635 00:27:02,320 --> 00:27:03,200 Los sistemas operativos gusta. 636 00:27:03,200 --> 00:27:06,360 Al parecer, la web puede hacer uso de este, y otras aplicaciones fijas. 637 00:27:06,360 --> 00:27:10,870 Pero lo que una limitación estúpidos que somos de vuelta a clase de semana dos límites 638 00:27:10,870 --> 00:27:12,880 donde hemos fijado arrays de tamaño. 639 00:27:12,880 --> 00:27:15,010 >> Así que de hecho hay un par de maneras en que podríamos solucionar esto. 640 00:27:15,010 --> 00:27:18,750 Podríamos asignar dinámicamente la matriz, no por la fuerza de codificación como he 641 00:27:18,750 --> 00:27:22,600 hecho aquí, sino que vuelva a declarar esto, para ser claros, como 642 00:27:22,600 --> 00:27:23,830 algo como esto. 643 00:27:23,830 --> 00:27:29,040 Int * bandejas, no decidir en una capacidad todavía. 644 00:27:29,040 --> 00:27:35,460 Pero cuando yo declaro la pila en otros lugares en mi código, podría entonces llamar a malloc, 645 00:27:35,460 --> 00:27:38,250 obtener la dirección de un trozo de memoria, y podría asignar 646 00:27:38,250 --> 00:27:39,980 esa dirección a bandejas. 647 00:27:39,980 --> 00:27:43,340 >> Y luego, porque es sólo un trozo de memoria, podría seguir utilizando cuadrado 648 00:27:43,340 --> 00:27:45,450 notación de corchetes de la manera habitual. 649 00:27:45,450 --> 00:27:49,020 Porque una vez más, hay una especie de este equivalente funcional de matrices y 650 00:27:49,020 --> 00:27:50,820 trozos de memoria que vienen de vuelta de malloc. 651 00:27:50,820 --> 00:27:53,090 Podemos tratar a uno como el otro utilizando la aritmética de punteros o 652 00:27:53,090 --> 00:27:54,440 notación de corchetes. 653 00:27:54,440 --> 00:27:55,660 Así que ese es uno de los enfoques. 654 00:27:55,660 --> 00:28:00,120 >> Pero, ¿cómo más podemos implementar esta misma estructura de datos, potencialmente? 655 00:28:00,120 --> 00:28:00,280 ¿Cierto? 656 00:28:00,280 --> 00:28:04,530 Me siento como que acabamos de resolver este problema como hace una semana. 657 00:28:04,530 --> 00:28:08,860 ¿Cuál fue la solución a este problema que se encontró con Steven? 658 00:28:08,860 --> 00:28:10,370 Así que las listas enlazadas, derecha. 659 00:28:10,370 --> 00:28:13,410 >> Si el problema es que estamos pintando a nosotros mismos en una esquina por la asignación de 660 00:28:13,410 --> 00:28:17,580 en avance muy poca memoria que a continuación, tener que lidiar de alguna manera con, bueno, 661 00:28:17,580 --> 00:28:19,880 ¿por qué no evitar que emitir en total? 662 00:28:19,880 --> 00:28:26,170 ¿Por qué no declaran bandejas para ser un puntero a un nodo, ergo una lista enlazada, 663 00:28:26,170 --> 00:28:30,740 y luego simplemente asignar nuevos nodos cada vez que Steven tenía que adaptarse a una 664 00:28:30,740 --> 00:28:32,400 número en la estructura de datos. 665 00:28:32,400 --> 00:28:34,200 >> Así que la imagen tendría que cambiar. 666 00:28:34,200 --> 00:28:38,220 No va a ser tan limpio y tan simple como una matriz de tres enteros. 667 00:28:38,220 --> 00:28:42,970 Ahora que va a ser un puntero a una estructura, y que estructura se va a 668 00:28:42,970 --> 00:28:44,830 tener un entero y un puntero siguiente. 669 00:28:44,830 --> 00:28:47,670 Se va a llevar a través de ese puntero a otro tal estructura a 670 00:28:47,670 --> 00:28:48,600 otro ejemplo de estructura. 671 00:28:48,600 --> 00:28:50,560 Así que el panorama sería realmente ser un poco más desordenado. 672 00:28:50,560 --> 00:28:52,950 Y tendríamos flechas atar todo junto. 673 00:28:52,950 --> 00:28:55,280 >> Pero eso está bien, correcto, porque hemos visto cómo hacer esto. 674 00:28:55,280 --> 00:28:58,180 Y una vez que usted se sienta cómodo implementar algo así como un archivo vinculado 675 00:28:58,180 --> 00:29:01,450 lista, que tendrá que hacer si elegir implementar una tabla hash con 676 00:29:01,450 --> 00:29:05,120 encadenamiento separado para p-set 6, se puede utilizarlo como un bloque de construcción, o un 677 00:29:05,120 --> 00:29:08,870 ingrediente, o arañazos hablar, un procedimiento, algo que se pone, que 678 00:29:08,870 --> 00:29:12,560 creado su propia pieza del rompecabezas que se puede reusar. 679 00:29:12,560 --> 00:29:17,090 Así compensaciones, sino las posibles soluciones que en realidad hemos visto antes. 680 00:29:17,090 --> 00:29:20,560 >> Así que muy a menudo, se ve esto todos los año o dos cuando Apple lanza 681 00:29:20,560 --> 00:29:23,060 algo nuevo, y todos los locos fila afuera de la Manzana 682 00:29:23,060 --> 00:29:27,050 tienda a comprar su marginal actualizar el hardware. 683 00:29:27,050 --> 00:29:30,420 Digo esto, está bien, porque Yo soy una de esas personas. 684 00:29:30,420 --> 00:29:35,140 Entonces, ¿qué tipo de estructura de datos podría representar esta realidad? 685 00:29:35,140 --> 00:29:36,980 >> Bueno, vamos a llamarlo una cola, una línea. 686 00:29:36,980 --> 00:29:40,270 So British diría que es típicamente un cola de todos modos, así que es un nombre bonito. 687 00:29:40,270 --> 00:29:44,960 Y las dos operaciones que una cola apoyará llamaremos un enqueue 688 00:29:44,960 --> 00:29:48,900 funcionamiento y una operación de quitar de la cola, que son similares en 689 00:29:48,900 --> 00:29:50,120 espíritu para insertar y extraer. 690 00:29:50,120 --> 00:29:54,060 Es sólo una especie de diferente en convención, lo que estamos llamando a estos. 691 00:29:54,060 --> 00:29:57,680 Pero para poner en cola algo significa añadir o insertarlo en la estructura de datos. 692 00:29:57,680 --> 00:29:59,570 Para quitar de la cola medios para eliminarlo. 693 00:29:59,570 --> 00:30:05,170 Pero mientras que una pila era un dato LIFO estructura, una cola es una primicia en, 694 00:30:05,170 --> 00:30:06,740 primero en salir estructura de datos. 695 00:30:06,740 --> 00:30:10,050 >> Si usted es la primera persona de la fila, usted será la primera persona en llegar 696 00:30:10,050 --> 00:30:12,420 fuera de la línea y comprar su nuevo dispositivo. 697 00:30:12,420 --> 00:30:18,070 Imagínate lo mal que serían estas personas si Apple en cambio utiliza una pila, para 698 00:30:18,070 --> 00:30:21,250 ejemplo, para implementar la recolección en marcha de su nuevo juguete. 699 00:30:21,250 --> 00:30:24,310 Así que las colas tienen sentido, sin duda, y podemos pensar en todo tipo de 700 00:30:24,310 --> 00:30:27,480 aplicaciones, presumiblemente, para las colas, especialmente cuando se quiere justicia. 701 00:30:27,480 --> 00:30:30,040 Entonces, ¿cómo podríamos aplicar estos como una estructura de datos? 702 00:30:30,040 --> 00:30:33,680 >> Bueno, yo propongo que podría tenga que hacerlo de esta manera. 703 00:30:33,680 --> 00:30:35,225 Así que voy a tener ahora los números. 704 00:30:35,225 --> 00:30:38,190 Así que vamos a mantenerlo simple y no necesariamente hablar en términos de bandejas. 705 00:30:38,190 --> 00:30:40,220 A sólo números que la gente de habidas. 706 00:30:40,220 --> 00:30:43,760 La capacidad se va a, de nuevo, fijar el número total de personas que pueden estar en 707 00:30:43,760 --> 00:30:46,900 esta línea, ya que tres o cualquier otro valor. 708 00:30:46,900 --> 00:30:50,760 >> Pero propongo que necesito para realizar un seguimiento no sólo del tamaño de la 709 00:30:50,760 --> 00:30:52,370 cola, ¿cuántas cosas hay en él. 710 00:30:52,370 --> 00:30:56,310 Así que el tamaño es el tamaño actual, la capacidad de es el tamaño máximo. 711 00:30:56,310 --> 00:30:58,540 Sólo una vez más, la nomenclatura por convención. 712 00:30:58,540 --> 00:31:03,680 ¿Por qué necesito un int adicional dentro de una cola para realizar un seguimiento de quién está en 713 00:31:03,680 --> 00:31:05,365 delante de la línea? 714 00:31:05,365 --> 00:31:07,930 715 00:31:07,930 --> 00:31:10,910 ¿Por qué tengo que hacer eso en este caso? 716 00:31:10,910 --> 00:31:14,750 717 00:31:14,750 --> 00:31:16,190 >> Bueno, ¿cómo es esta imagen va a cambiar? 718 00:31:16,190 --> 00:31:19,280 Es probable que pueda volver a utilizar más de esta imagen. 719 00:31:19,280 --> 00:31:21,480 Déjame ir adelante y borrar lo que hay aquí. 720 00:31:21,480 --> 00:31:24,580 Vamos a dar esto un poco nombre diferente aquí. 721 00:31:24,580 --> 00:31:28,930 Vamos a deshacernos de los 17, vamos a deshacernos del 9, vamos a deshacernos de los 3. 722 00:31:28,930 --> 00:31:30,410 Y vamos a añadir una cosa más. 723 00:31:30,410 --> 00:31:34,710 Propongo que tengo que hacer un seguimiento de al frente de la lista, que es sólo 724 00:31:34,710 --> 00:31:35,570 va a ser un int también. 725 00:31:35,570 --> 00:31:36,550 Y vamos a mantenerlo simple. 726 00:31:36,550 --> 00:31:37,740 Lista de No vinculado por ahora. 727 00:31:37,740 --> 00:31:40,900 >> Vamos a admitir que vamos a se topan con este límite. 728 00:31:40,900 --> 00:31:43,720 Pero, ¿qué es lo que quiero ver sucederá esta vez? 729 00:31:43,720 --> 00:31:47,240 Así que supongo que sigo adelante y la primera persona aparece en la fila, y 730 00:31:47,240 --> 00:31:48,560 es el número 9. 731 00:31:48,560 --> 00:31:49,680 Tenemos bolas de la tensión. 732 00:31:49,680 --> 00:31:51,330 ¿Puedo robar, por ejemplo, dos o tres personas? 733 00:31:51,330 --> 00:31:52,690 Uno, dos, tres? 734 00:31:52,690 --> 00:31:53,120 Vamos arriba. 735 00:31:53,120 --> 00:31:56,022 Desde el frente, porque vamos a hacer esta labor más rápida. 736 00:31:56,022 --> 00:31:59,415 >> Cada uno de ustedes está ahora va a ser un chico de ventilador en línea de Apple. 737 00:31:59,415 --> 00:32:03,970 738 00:32:03,970 --> 00:32:06,210 Usted no va a recibir los equipos de Apple al final de esto, sin embargo. 739 00:32:06,210 --> 00:32:06,500 Está bien. 740 00:32:06,500 --> 00:32:09,430 Así que usted es el número 9, que está número 17, número 22. 741 00:32:09,430 --> 00:32:12,130 Estos son números arbitrarios, como identificaciones estudiantiles o lo que sea. 742 00:32:12,130 --> 00:32:14,550 Y en un momento, vamos a empezar para empezar a añadir cosas. 743 00:32:14,550 --> 00:32:16,000 Y voy a correr el tablero aquí esta vez. 744 00:32:16,000 --> 00:32:19,570 >> Así que en este caso, he inicializa la frente a ser - 745 00:32:19,570 --> 00:32:22,380 En realidad no me importa lo que la delante es, porque el tamaño es cero. 746 00:32:22,380 --> 00:32:24,480 Así que esto puede ser que también acaba de ser un signo de interrogación. 747 00:32:24,480 --> 00:32:26,170 Todos estos son signos de interrogación. 748 00:32:26,170 --> 00:32:29,880 Así que ahora vamos a empezar a ver realmente algunos gente haciendo cola en la tienda. 749 00:32:29,880 --> 00:32:33,320 >> Así que si el número 9, que es el primero a las 5 de la mañana, a seguir adelante y se alinean, 750 00:32:33,320 --> 00:32:34,210 o la noche antes. 751 00:32:34,210 --> 00:32:34,580 Aceptar. 752 00:32:34,580 --> 00:32:35,940 Así que ahora 9 está aquí. 753 00:32:35,940 --> 00:32:37,940 Así es 9 en la parte frontal de la lista. 754 00:32:37,940 --> 00:32:41,440 Así que voy a seguir adelante y actualizar el tamaño de estos datos actual 755 00:32:41,440 --> 00:32:44,740 estructura a no ser 0 más, pero para ser 1. 756 00:32:44,740 --> 00:32:47,630 Me voy a poner 9 en el frente de la lista. 757 00:32:47,630 --> 00:32:51,020 Déjame ir adelante y alternar la pantalla para que podamos ver más allá de nosotros aquí. 758 00:32:51,020 --> 00:32:53,220 >> Y ahora, ¿qué es lo que quiero poner al frente? 759 00:32:53,220 --> 00:32:56,240 Voy a llevar la cuenta de que la frente de la cola en este momento 760 00:32:56,240 --> 00:32:58,570 está en la posición 0. 761 00:32:58,570 --> 00:33:00,510 Porque lo que está al lado va a pasar? 762 00:33:00,510 --> 00:33:03,000 Bueno, supongo que ahora me Enqueue 17 también. 763 00:33:03,000 --> 00:33:04,510 Así que saltar en línea allí. 764 00:33:04,510 --> 00:33:07,060 Y de nuevo, el tipo de puerta a la tienda va a estar aquí. 765 00:33:07,060 --> 00:33:08,700 Así que ahora he añadido 17. 766 00:33:08,700 --> 00:33:10,810 Y a pesar de que estos chicos están bloqueando la pantalla, eso está bien, 767 00:33:10,810 --> 00:33:12,300 porque podemos verlo aquí. 768 00:33:12,300 --> 00:33:12,910 Lo siento. 769 00:33:12,910 --> 00:33:13,810 >> AUDIENCIA: Podemos mover - 770 00:33:13,810 --> 00:33:14,660 >> DAVID MALAN: No, eso está bien. 771 00:33:14,660 --> 00:33:16,000 Es enorme allí. 772 00:33:16,000 --> 00:33:18,580 Así 17 está ahora dentro de la cola. 773 00:33:18,580 --> 00:33:21,332 Necesito actualizar el que campos, aunque ahora? 774 00:33:21,332 --> 00:33:23,210 Bueno, definitivamente tamaño. 775 00:33:23,210 --> 00:33:26,430 ¿Y qué hay delante? 776 00:33:26,430 --> 00:33:27,040 Bueno, no. 777 00:33:27,040 --> 00:33:30,200 Frente no debe cambiar, porque a diferencia de una pila, que 778 00:33:30,200 --> 00:33:31,370 quiere mantener la equidad. 779 00:33:31,370 --> 00:33:35,150 Así que si 9 se produjo en primer lugar, queremos 9 para ser el primero en salir de la línea de 780 00:33:35,150 --> 00:33:36,420 y dentro de la tienda. 781 00:33:36,420 --> 00:33:37,220 >> De hecho, vamos a ver eso. 782 00:33:37,220 --> 00:33:42,235 Antes de que nos insertamos 22, vamos a seguir adelante y sacar de la cola 9. 783 00:33:42,235 --> 00:33:42,970 ¿Cuál es tu nombre? 784 00:33:42,970 --> 00:33:43,680 >> AUDIENCIA: Jake. 785 00:33:43,680 --> 00:33:45,440 >> DAVID MALAN: Jake va para ser quitado de la cola ahora. 786 00:33:45,440 --> 00:33:48,050 Así que tienes que caminar a la tienda. 787 00:33:48,050 --> 00:33:49,880 Y pretender que la tienda es por allí. 788 00:33:49,880 --> 00:33:51,970 Así que ahora lo que hay - dit-dit-dit! 789 00:33:51,970 --> 00:33:53,400 ¿Qué debe ocurrir ahora? 790 00:33:53,400 --> 00:33:54,490 Decisión de diseño. 791 00:33:54,490 --> 00:33:56,825 Así que no es un mal instinto, pero - ¿cuál es tu nombre? 792 00:33:56,825 --> 00:33:57,090 >> AUDIENCIA: David. 793 00:33:57,090 --> 00:33:57,500 >> DAVID MALAN: David. 794 00:33:57,500 --> 00:33:58,810 Entonces, ¿qué hizo David? 795 00:33:58,810 --> 00:34:02,590 Él estaba tratando de arreglar especie de los datos estructura y el movimiento de su ubicación 796 00:34:02,590 --> 00:34:04,100 en antigua ubicación de Jake. 797 00:34:04,100 --> 00:34:06,740 Y eso está bien si estamos dispuestos a aceptar que como una 798 00:34:06,740 --> 00:34:08,199 detalle de implementación. 799 00:34:08,199 --> 00:34:11,100 Pero primero, vamos a actualizar los datos estructura antes de hacer eso. 800 00:34:11,100 --> 00:34:14,139 Porque yo no me está gustando la idea de todo el pueblo el cambio en esta línea. 801 00:34:14,139 --> 00:34:17,360 >> No es gran cosa si David lo hace con un paso, pero una vez más, pensar en volver a 802 00:34:17,360 --> 00:34:20,360 cuando hemos tenido ocho voluntarios en el escenario y lo que hemos hecho, como la inserción 803 00:34:20,360 --> 00:34:22,600 especie, donde tuvimos que empezar mover todos a su alrededor. 804 00:34:22,600 --> 00:34:23,790 Eso hizo caro, ¿no? 805 00:34:23,790 --> 00:34:28,330 Eso me hace temblar sobre Big O de n, gran O de n al cuadrado de nuevo. 806 00:34:28,330 --> 00:34:30,650 No se siente como un resultado ideal. 807 00:34:30,650 --> 00:34:32,080 >> Así que vamos a actualizar esto. 808 00:34:32,080 --> 00:34:35,120 Así que el tamaño de la cola ya no es 2. 809 00:34:35,120 --> 00:34:37,090 Ahora es simplemente 1. 810 00:34:37,090 --> 00:34:40,360 Pero ahora puedo actualizar algo No me actualizo antes, la 811 00:34:40,360 --> 00:34:41,130 frente de la lista. 812 00:34:41,130 --> 00:34:45,420 Yo sólo puedo decir, es que la ubicación 1? 813 00:34:45,420 --> 00:34:49,770 Así que ahora tenemos el valor de basura aquí, valor de la basura aquí, y David en el 814 00:34:49,770 --> 00:34:51,469 medio de esta basura. 815 00:34:51,469 --> 00:34:54,980 Pero la estructura de datos sigue intacta. 816 00:34:54,980 --> 00:34:58,540 >> Y de hecho, yo ni siquiera necesito cambiar ex número de Jake 817 00:34:58,540 --> 00:35:00,460 9, porque a quién le importa. 818 00:35:00,460 --> 00:35:04,470 Tengo suficiente información ahora en el tamaño que sé que hay una persona en 819 00:35:04,470 --> 00:35:05,030 esta cola. 820 00:35:05,030 --> 00:35:08,340 Y sé que esa persona está en la posición 1, no 0. 821 00:35:08,340 --> 00:35:09,760 No estoy contando. 822 00:35:09,760 --> 00:35:11,300 Así 1 también. 823 00:35:11,300 --> 00:35:13,410 De modo que la estructura de datos es aún así está bien. 824 00:35:13,410 --> 00:35:14,330 >> Bueno, ¿qué pasa después? 825 00:35:14,330 --> 00:35:15,010 Vamos a poner en cola - 826 00:35:15,010 --> 00:35:15,370 ¿cuál es tu nombre? 827 00:35:15,370 --> 00:35:16,160 >> AUDIENCIA: Callen. 828 00:35:16,160 --> 00:35:16,580 >> DAVID MALAN: Callen. 829 00:35:16,580 --> 00:35:20,770 Vamos a poner en cola un Callen, y 22 se encuentra ahora en la cola. 830 00:35:20,770 --> 00:35:22,300 Así que ahora lo que tiene que cambiar aquí? 831 00:35:22,300 --> 00:35:24,380 Frente no va a cambiar, obviamente. 832 00:35:24,380 --> 00:35:27,160 Tamaño va a cambiar para ser 2 de nuevo. 833 00:35:27,160 --> 00:35:31,590 Y 22 termina aquí, 9 es todavía presente, pero es efectivamente un 834 00:35:31,590 --> 00:35:32,600 valor de la basura ahora. 835 00:35:32,600 --> 00:35:35,910 Es sólo un remanente de Jake pasado. 836 00:35:35,910 --> 00:35:39,200 >> ¿Y ahora qué pasa si Me Dequeue David? 837 00:35:39,200 --> 00:35:41,560 Una última operación, dequeue David. 838 00:35:41,560 --> 00:35:46,070 Podríamos cambiar, pero propongo establezcamos las hacer el menor trabajo posible. 839 00:35:46,070 --> 00:35:50,280 Ahora mi estructura de datos se de nuevo en tamaño de 2 a 1. 840 00:35:50,280 --> 00:35:53,730 Pero la parte delantera de la cola ahora se convierte en 2. 841 00:35:53,730 --> 00:35:56,640 Yo no necesito cambiar estos números por el momento, porque son 842 00:35:56,640 --> 00:35:58,230 sólo los valores de basura. 843 00:35:58,230 --> 00:35:59,720 >> Pero ahora ¿qué pasa? 844 00:35:59,720 --> 00:36:03,280 Supongamos que yo Enqueue mí mismo, 26? 845 00:36:03,280 --> 00:36:05,890 Siento que pertenezco aquí. 846 00:36:05,890 --> 00:36:06,890 Así que estoy siendo en cola. 847 00:36:06,890 --> 00:36:08,760 Así que tipo de pertenezco aquí. 848 00:36:08,760 --> 00:36:11,300 Y aunque no lo hace bastante apreciar esta visualmente en el escenario, 849 00:36:11,300 --> 00:36:15,075 porque tenemos un montón de espacio, lo que debería No estar de pie aquí, ¿por qué? 850 00:36:15,075 --> 00:36:16,290 >> AUDIENCIA: Usted está fuera de los límites. 851 00:36:16,290 --> 00:36:16,370 >> DAVID MALAN: Así es. 852 00:36:16,370 --> 00:36:16,940 Estoy fuera de los límites. 853 00:36:16,940 --> 00:36:19,330 He indexan más allá de la límites de este arreglo. 854 00:36:19,330 --> 00:36:23,420 Realmente debería estar en uno de los tres posibles ubicaciones. 855 00:36:23,420 --> 00:36:25,150 Ahora, ¿dónde está más natural que ir? 856 00:36:25,150 --> 00:36:27,760 Propongo aprovechamos a la semana de un solo truco. 857 00:36:27,760 --> 00:36:30,150 El operador mod, porcentaje. 858 00:36:30,150 --> 00:36:36,850 Porque estoy técnicamente pie en localización 3, pero tengo 3 capacidad mod, 859 00:36:36,850 --> 00:36:40,250 so 3, un signo de porcentaje, 3 - 860 00:36:40,250 --> 00:36:40,970 de capacidad 3. 861 00:36:40,970 --> 00:36:41,720 ¿Qué es eso? 862 00:36:41,720 --> 00:36:43,700 ¿Qué es lo que queda cuando dividir 3 por 3? 863 00:36:43,700 --> 00:36:44,070 0. 864 00:36:44,070 --> 00:36:48,140 >> Así que eso pone a mí eran Jake era, que en realidad es bueno. 865 00:36:48,140 --> 00:36:50,370 Así que ahora la aplicación de esta cosa va a 866 00:36:50,370 --> 00:36:51,250 ser un poco de dolor de cabeza. 867 00:36:51,250 --> 00:36:53,740 Es realmente una sola línea de dolor de cabeza, de código. 868 00:36:53,740 --> 00:36:56,580 Pero al menos ahora hay basura valoran aquí, pero hay dos 869 00:36:56,580 --> 00:36:57,910 ints legítimos aquí. 870 00:36:57,910 --> 00:37:04,160 Y afirmo que ahora que hemos hecho exactamente lo que tenemos que hacer, siempre y cuando 871 00:37:04,160 --> 00:37:08,600 cambiamos lo de Jake valor iba a ser 26. 872 00:37:08,600 --> 00:37:12,110 >> Ahora tenemos suficiente información todavía para mantener la integridad 873 00:37:12,110 --> 00:37:13,060 de esta estructura de datos. 874 00:37:13,060 --> 00:37:17,160 Todavía estamos un poco fuera de suerte cuando nos desee insertar cuatro o más totales 875 00:37:17,160 --> 00:37:20,740 elementos, pero al menos puedo hacer bastante uso eficiente de esta constante 876 00:37:20,740 --> 00:37:21,740 tiempo, de hecho. 877 00:37:21,740 --> 00:37:27,150 Yo no tengo que preocuparme por el cambio todos, como la inclinación de David era. 878 00:37:27,150 --> 00:37:30,816 >> ¿Tiene preguntas sobre pilas, o esta cola? 879 00:37:30,816 --> 00:37:32,184 >> AUDIENCIA: ¿Es la razón por la cual usted necesita tamaño para que usted sepa 880 00:37:32,184 --> 00:37:34,010 dónde tener a una persona? 881 00:37:34,010 --> 00:37:34,770 >> DAVID MALAN: Exactamente. 882 00:37:34,770 --> 00:37:38,230 Necesito saber el tamaño de la matriz porque tengo que saber exactamente cómo 883 00:37:38,230 --> 00:37:41,940 muchos de estos valores son legítimos, y para que yo pueda encontrar dónde poner 884 00:37:41,940 --> 00:37:42,800 la siguiente persona. 885 00:37:42,800 --> 00:37:43,300 Exactamente. 886 00:37:43,300 --> 00:37:44,580 El tamaño es - 887 00:37:44,580 --> 00:37:46,360 en realidad, no nos actualizamos esto todavía. 888 00:37:46,360 --> 00:37:48,380 Me sumé a 26. 889 00:37:48,380 --> 00:37:51,760 El tamaño es ahora, no 1, sino 2. 890 00:37:51,760 --> 00:37:57,780 Así que ahora esta de hecho me ayuda a encontrar el cabeza de la lista, que no es 0, no 891 00:37:57,780 --> 00:37:59,250 1, pero es 2. 892 00:37:59,250 --> 00:38:01,665 El frente de la lista es de hecho el número 22. 893 00:38:01,665 --> 00:38:05,120 Debido a que llegó en primer lugar, por lo que debería ser admitidos en la tienda antes de mí, 894 00:38:05,120 --> 00:38:08,780 a pesar de que visualmente estoy parado más cerca de la tienda. 895 00:38:08,780 --> 00:38:09,220 >> ¿De acuerdo? 896 00:38:09,220 --> 00:38:12,410 Un aplauso para estos chicos y dejaremos que sacarlos de allí. 897 00:38:12,410 --> 00:38:17,090 >> [Aplausos] 898 00:38:17,090 --> 00:38:18,150 >> DAVID MALAN: podía dejar que a mantener la bandeja. 899 00:38:18,150 --> 00:38:20,760 Pudimos ver lo que ocurre si que quiera, pero tal vez no. 900 00:38:20,760 --> 00:38:21,590 Está bien. 901 00:38:21,590 --> 00:38:25,380 ¿Y ahora qué nos deja eso? 902 00:38:25,380 --> 00:38:28,900 Bueno, permítanme proponer que hay un algunas otras estructuras de datos que pudimos 903 00:38:28,900 --> 00:38:33,810 empezar a añadir a nuestro conjunto de herramientas que se en realidad ser muy, muy relevante como 904 00:38:33,810 --> 00:38:35,270 nos sumergimos en materia web. 905 00:38:35,270 --> 00:38:38,150 Que a su vez, tiene algún tipo de conexión a los árboles en la forma de 906 00:38:38,150 --> 00:38:40,550 algo que se llama DOM, documento modelo de objetos. 907 00:38:40,550 --> 00:38:42,370 Pero vamos a ver más de que en poco tiempo. 908 00:38:42,370 --> 00:38:46,260 >> Permítanme proponer por definición que Árbol de llamadas ahora lo que puede ser que sepa como 909 00:38:46,260 --> 00:38:48,820 más de un árbol de la familia, en la que tener algún antepasado en el 910 00:38:48,820 --> 00:38:49,790 raíces del árbol. 911 00:38:49,790 --> 00:38:54,480 A patriarcal o una matriarca en la parte más alta del árbol. 912 00:38:54,480 --> 00:38:56,700 Sin su cónyuge, en este caso. 913 00:38:56,700 --> 00:39:00,940 Pero ahora tenemos lo que llamamos los niños, que son los nodos que cuelgan 914 00:39:00,940 --> 00:39:05,480 fuera el hijo izquierdo o derecho del niño, flechas como se representa aquí. 915 00:39:05,480 --> 00:39:10,490 >> En otras palabras, en una estructura de datos en árbol en el ordenador, un árbol tiene cero 916 00:39:10,490 --> 00:39:11,480 o más nodos. 917 00:39:11,480 --> 00:39:13,500 Si tiene al menos un nodo, eso se llama la raíz. 918 00:39:13,500 --> 00:39:15,700 Son las cosas visualmente que nos basamos en la parte superior. 919 00:39:15,700 --> 00:39:20,280 Y ese nodo, como cualquier otro nodo, puede tener cero, uno, o dos, o tres, 920 00:39:20,280 --> 00:39:23,600 o sin embargo muchos niños la estructura de datos compatible. 921 00:39:23,600 --> 00:39:29,150 En este caso, la raíz, el almacenamiento de la valorar uno, tiene dos hijos, de 2 y 3, 922 00:39:29,150 --> 00:39:33,020 por lo que generalmente llamamos 2 la izquierda infantil y 3 el hijo derecho. 923 00:39:33,020 --> 00:39:36,940 >> Y luego, cuando nos ponemos manos a la 5, 6, y 7, 6 podría ser llamado el hijo del medio. 924 00:39:36,940 --> 00:39:38,940 Si usted tiene cuatro hijos, se vuelve confuso. 925 00:39:38,940 --> 00:39:42,260 Así que dejamos de usar ese tipo de atajo verbal. 926 00:39:42,260 --> 00:39:44,580 Pero no deja de ser un árbol genealógico. 927 00:39:44,580 --> 00:39:48,880 Y las hojas que aquí están los nodos que ellos no tienen hijos. 928 00:39:48,880 --> 00:39:52,540 Se cuelgan de la parte inferior del árbol. 929 00:39:52,540 --> 00:39:56,940 >> Entonces, ¿cómo podríamos implementar un árbol que tiene sólo dos hijos al máximo? 930 00:39:56,940 --> 00:39:58,410 Lo llamaremos un árbol binario. 931 00:39:58,410 --> 00:40:00,960 Bi de nuevo lo que significa dos, en este caso, al igual que con el binario. 932 00:40:00,960 --> 00:40:04,830 Y por lo que puede tener cero, uno, o dos niños como máximo. 933 00:40:04,830 --> 00:40:08,650 >> Yo propongo que implementamos el nodo para esa estructura con un int n, 934 00:40:08,650 --> 00:40:11,910 y luego dos punteros, uno llamado a la izquierda, uno llamado derecha. 935 00:40:11,910 --> 00:40:14,830 Pero esos son sólo agradable convenciones arbitrarias. 936 00:40:14,830 --> 00:40:18,170 Y lo que es bueno ahora, sobre todo si clase de batallado conceptualmente con 937 00:40:18,170 --> 00:40:21,300 recursividad, o pensó que no era realmente una solución a nada, 938 00:40:21,300 --> 00:40:23,120 especialmente si pudiera quedarse sin memoria. 939 00:40:23,120 --> 00:40:26,600 Ahora que estamos hablando de datos estructuras y algoritmos que permiten 940 00:40:26,600 --> 00:40:31,030 nosotros atravesamos y manipularlos, Resulta que la recursividad regresa en 941 00:40:31,030 --> 00:40:34,240 una forma mucho más convincente si no es bello camino. 942 00:40:34,240 --> 00:40:38,670 >> Así que esto que propongo es la implementación de una función de búsqueda. 943 00:40:38,670 --> 00:40:39,870 Dadas dos entradas - 944 00:40:39,870 --> 00:40:41,570 por lo que pensar en esto como un cuadro negro. 945 00:40:41,570 --> 00:40:46,560 Dadas dos entradas, n, un entero, y un puntero a un árbol, un puntero a una 946 00:40:46,560 --> 00:40:50,020 nodo, o realmente la raíz de un árbol, afirman que esta función puede devolver 947 00:40:50,020 --> 00:40:53,530 verdadera o falsa, de que el valor n que está dentro de este árbol. 948 00:40:53,530 --> 00:40:55,210 >> ¿Qué hay dentro de esta caja de negro? 949 00:40:55,210 --> 00:40:57,440 Bueno, cuatro ramas. 950 00:40:57,440 --> 00:40:58,385 El primero sólo comprueba. 951 00:40:58,385 --> 00:41:00,490 Si el árbol es nulo, apenas vuelva falsa. 952 00:41:00,490 --> 00:41:04,580 Si no hay un nodo, no hay n, no hay un número, simplemente return false. 953 00:41:04,580 --> 00:41:12,330 Si, sin embargo, n, el valor que usted está buscando para, es menos de árbol de la flecha N, y 954 00:41:12,330 --> 00:41:15,180 sólo para que quede claro, lo que quiere decir cuando Escribo árbol y luego la flecha 955 00:41:15,180 --> 00:41:18,150 notación, n? 956 00:41:18,150 --> 00:41:18,690 Exactamente. 957 00:41:18,690 --> 00:41:21,970 Significa eliminar la referencia que puntero llama árbol. 958 00:41:21,970 --> 00:41:26,750 Ir allí, y luego entrar de esa nodo y conseguir su campo llamado n. 959 00:41:26,750 --> 00:41:30,810 Y a continuación, comparar el n real que fue pasado a la búsqueda en contra de ella. 960 00:41:30,810 --> 00:41:35,390 >> Así que si n es menor que, el valor de n en el nodo de árbol en sí, bueno, 961 00:41:35,390 --> 00:41:36,720 ¿Qué significa eso? 962 00:41:36,720 --> 00:41:40,690 Eso no significa nada a primera vista. 963 00:41:40,690 --> 00:41:40,900 ¿Cierto? 964 00:41:40,900 --> 00:41:45,560 Al igual que cuando usted tiene una gran variedad de valores, que te pueden gustar aplicar binario 965 00:41:45,560 --> 00:41:48,290 buscar como una forma de división y conquistar. 966 00:41:48,290 --> 00:41:51,790 Pero, ¿qué hipótesis nos tenemos que hacer de búsqueda binaria para trabajar en absoluto 967 00:41:51,790 --> 00:41:54,510 en la guía telefónica y ejemplos anteriores? 968 00:41:54,510 --> 00:41:55,530 >> Cómo ordenar. 969 00:41:55,530 --> 00:41:59,490 Así que vamos a refinar la definición de árbol aquí no para ser sólo un árbol, lo que puede 970 00:41:59,490 --> 00:42:00,880 tener cualquier número de hijos. 971 00:42:00,880 --> 00:42:04,700 No es sólo un árbol binario, lo que puede tener 0, 1, o 2 como máximo. 972 00:42:04,700 --> 00:42:09,700 Pero, como un árbol de búsqueda binaria, o BST, que es sólo una forma elegante de decir una 973 00:42:09,700 --> 00:42:15,430 árbol binario de tal manera que de cada nodo hijo izquierdo, si está presente, es 974 00:42:15,430 --> 00:42:16,830 menor que el nodo. 975 00:42:16,830 --> 00:42:20,170 Y los niños el derecho de cada nodo, si está presente, es mayor 976 00:42:20,170 --> 00:42:21,740 que el propio nodo. 977 00:42:21,740 --> 00:42:25,200 >> Así que en otras palabras, si usted fuera a dibujar el árbol de salida, todos los números son 978 00:42:25,200 --> 00:42:30,620 cuidadosamente equilibrada como esto para que si usted tiene 55 como la raíz, 33 pueden ir 979 00:42:30,620 --> 00:42:33,090 a su izquierda, ya que es menos de 55. 980 00:42:33,090 --> 00:42:36,430 77 se puede ir a la derecha, porque que es mayor que 55. 981 00:42:36,430 --> 00:42:40,750 Pero ahora fíjense, la misma definición, es una definición recursiva verbalmente, 982 00:42:40,750 --> 00:42:42,600 tiene que solicitar 33. 983 00:42:42,600 --> 00:42:47,610 Hijo izquierdo de 33 debe ser menor que ella, y el derecho del niño de 33 años, de 44 años, debe ser 984 00:42:47,610 --> 00:42:48,580 más grande que él. 985 00:42:48,580 --> 00:42:51,670 >> Así que este es un árbol de búsqueda binaria, y Propongo, con un poco de 986 00:42:51,670 --> 00:42:53,910 recursividad, ahora podemos encontrar n. 987 00:42:53,910 --> 00:42:59,160 Así que si n es menor que el valor de n que es nodo actual, voy a ir 988 00:42:59,160 --> 00:43:04,090 adelante y batea, por así decirlo, y sólo regreso sea cual sea la respuesta es de 989 00:43:04,090 --> 00:43:08,470 la búsqueda de n en el hijo izquierdo del árbol. 990 00:43:08,470 --> 00:43:11,370 Note otra vez, esta función sólo espera una estrella nodo, una 991 00:43:11,370 --> 00:43:12,780 puntero a un nodo. 992 00:43:12,780 --> 00:43:17,360 Así que he aquí yo sólo puedo hacer árbol flecha izquierda, lo que conducirá 993 00:43:17,360 --> 00:43:18,400 me a otro nodo. 994 00:43:18,400 --> 00:43:19,480 Pero, ¿qué es ese nodo? 995 00:43:19,480 --> 00:43:22,820 >> Bueno, de acuerdo con esta declaración, izquierda es sólo un puntero, por lo que sólo 996 00:43:22,820 --> 00:43:27,090 significa que estoy pasando a la función de búsqueda un puntero diferente, a saber 997 00:43:27,090 --> 00:43:30,750 el que representa el árbol de mi hijo izquierdo. 998 00:43:30,750 --> 00:43:36,040 Así pues, en este caso, el puntero a 33, si esta es nuestra entrada de la muestra Mientras tanto, si 999 00:43:36,040 --> 00:43:40,740 n es mayor que el valor de n en la nodo actual en el árbol, entonces estoy 1000 00:43:40,740 --> 00:43:43,370 va a seguir adelante y en batea en la otra dirección y simplemente decir, no lo sé 1001 00:43:43,370 --> 00:43:47,280 saber si este valor de n está en el árbol, pero sé que si lo es, es por mi 1002 00:43:47,280 --> 00:43:49,090 rama derecha, por así decirlo. 1003 00:43:49,090 --> 00:43:53,120 Así que déjame llamar recursivamente buscar, pasar una n otra vez, pero que pasa en un 1004 00:43:53,120 --> 00:43:54,580 Puntero a mi hijo derecho. 1005 00:43:54,580 --> 00:44:00,020 >> En otras palabras, si estoy en la actualidad a 55 y estoy en busca de 99, yo sé que el 99 1006 00:44:00,020 --> 00:44:04,270 es mayor que 55, por lo que al igual que yo arranqué hace las semanas de la guía telefónica y nos 1007 00:44:04,270 --> 00:44:07,140 que salió bien, del mismo modo somos va a ir a la derecha aquí. 1008 00:44:07,140 --> 00:44:11,960 Y yo no sé si es a mi derecha niño, y no lo es, 77 es allí, pero 1009 00:44:11,960 --> 00:44:13,210 Sé que es en esa dirección. 1010 00:44:13,210 --> 00:44:18,770 Así que llamar a buscar a mi hijo derecho, 77, y dejar que figura búsqueda hacia fuera de 1011 00:44:18,770 --> 00:44:24,950 Si hay 99 en este arbitraria ejemplo es realmente allí. 1012 00:44:24,950 --> 00:44:26,900 >> Si no, ¿cuál es el último caso? 1013 00:44:26,900 --> 00:44:28,620 Si el árbol es nula es uno de los casos. 1014 00:44:28,620 --> 00:44:31,890 Si n es menor que la corriente del nodo valor es otro caso. 1015 00:44:31,890 --> 00:44:35,120 Si n es mayor que la corriente valor del nodo es un tercer caso. 1016 00:44:35,120 --> 00:44:38,250 ¿Cuál es la cuarta y última caso? 1017 00:44:38,250 --> 00:44:39,480 Creo que estamos fuera de los casos, ¿no? 1018 00:44:39,480 --> 00:44:44,690 Debe ser que n está en el nodo actual que estoy en. 1019 00:44:44,690 --> 00:44:49,640 >> Así que si yo estoy buscando 55 en este punto en la historia, esa rama de la 1020 00:44:49,640 --> 00:44:51,780 árbol volvería realidad. 1021 00:44:51,780 --> 00:44:55,380 Así que lo que es interesante aquí es que En realidad, a diferencia de semana pasado, que tipo 1022 00:44:55,380 --> 00:44:56,740 de tener dos casos base. 1023 00:44:56,740 --> 00:44:58,300 Y no tienen que es todo en la parte superior. 1024 00:44:58,300 --> 00:45:01,390 La parte superior es un caso base, porque si el árbol es nulo, no hay nada que hacer. 1025 00:45:01,390 --> 00:45:03,410 Simplemente envíe un duro Coded valor false. 1026 00:45:03,410 --> 00:45:07,400 >> La rama inferior es una especie de De forma predeterminada, por lo que si hemos comprobado para 1027 00:45:07,400 --> 00:45:11,550 null, hemos comprobado si debe ser a la izquierda, pero no debe ser, tenemos 1028 00:45:11,550 --> 00:45:14,640 comprobar si se debe estar en lo cierto, pero no debe ser, claramente, tiene que ser 1029 00:45:14,640 --> 00:45:15,870 justo donde estamos. 1030 00:45:15,870 --> 00:45:16,780 Ese es un caso base. 1031 00:45:16,780 --> 00:45:19,920 Así que hay dos casos recursivos intercalado en el medio. 1032 00:45:19,920 --> 00:45:21,630 Pero yo podría haber escrito esto en cualquier orden. 1033 00:45:21,630 --> 00:45:24,520 Acabo de pensar que tipo de sentía natural comprobar primero para un posible error, 1034 00:45:24,520 --> 00:45:28,340 a continuación, compruebe la izquierda, a continuación, compruebe la derecha, luego asumir que usted está en el nodo 1035 00:45:28,340 --> 00:45:30,630 en realidad estás buscando. 1036 00:45:30,630 --> 00:45:36,240 >> Entonces ¿por qué podría ser esto útil? 1037 00:45:36,240 --> 00:45:37,910 Así que resulta - 1038 00:45:37,910 --> 00:45:42,110 y que me haga saltar de un teaser aquí lo que está en la web. 1039 00:45:42,110 --> 00:45:44,920 Vamos a empezar no es un uso de lenguaje de programación al principio, pero una 1040 00:45:44,920 --> 00:45:46,030 lenguaje de marcas. 1041 00:45:46,030 --> 00:45:48,740 Un lenguaje de marcado de ser uno que sea similares en espíritu a la programación 1042 00:45:48,740 --> 00:45:51,715 lenguaje, pero no te la dan capacidad de expresarse con lógica. 1043 00:45:51,715 --> 00:45:55,070 Sólo le da la capacidad de expresarse estructuralmente. 1044 00:45:55,070 --> 00:45:57,960 >> ¿Dónde quieres poner algo en la página, la página web? 1045 00:45:57,960 --> 00:45:59,200 ¿De qué color es lo que quieres que sea? 1046 00:45:59,200 --> 00:46:00,950 ¿Qué tamaño de la fuente es lo que quieres que sea? 1047 00:46:00,950 --> 00:46:02,970 ¿Qué palabras en realidad quiera en la página web? 1048 00:46:02,970 --> 00:46:04,060 Así que eso es un lenguaje de marcas. 1049 00:46:04,060 --> 00:46:07,690 Pero entonces vamos a introducir muy rápidamente JavaScript, lo que es un hecho y derecho 1050 00:46:07,690 --> 00:46:08,560 lenguaje de programación. 1051 00:46:08,560 --> 00:46:12,530 Sintácticamente muy similares en apariencia a C, pero va a tener algún 1052 00:46:12,530 --> 00:46:15,200 agradable, más poderoso, más características de uso fácil. 1053 00:46:15,200 --> 00:46:18,050 >> Y una de las frustraciones en este punto en el semestre es que vamos a 1054 00:46:18,050 --> 00:46:22,065 pronto aplicar corrector ortográfico en un número mucho menor líneas de código que utilizan otros idiomas 1055 00:46:22,065 --> 00:46:25,580 que la propia C permite, pero por razón de pronto vamos a entender. 1056 00:46:25,580 --> 00:46:27,750 Esta será la primera de esas páginas web. 1057 00:46:27,750 --> 00:46:30,120 Será completamente decepcionante, el primero que hacemos. 1058 00:46:30,120 --> 00:46:31,400 Simplemente va a decir hola mundo. 1059 00:46:31,400 --> 00:46:34,010 Pero si nunca has visto antes, este es HTML, 1060 00:46:34,010 --> 00:46:35,670 HyperText Markup Language. 1061 00:46:35,670 --> 00:46:39,310 >> Si usted va a una opción de menú determinado en la mayoría de cualquier navegador, en cualquier página web en 1062 00:46:39,310 --> 00:46:43,160 el Internet, usted puede ver el código HTML que algunas personas escribieron a 1063 00:46:43,160 --> 00:46:44,400 crear esa página web. 1064 00:46:44,400 --> 00:46:47,850 Y probablemente no se ve tan breve o tan limpio como este. 1065 00:46:47,850 --> 00:46:51,400 Pero va a seguir el patrón de estos soportes y barras abiertas y 1066 00:46:51,400 --> 00:46:53,660 letras y potencialmente números. 1067 00:46:53,660 --> 00:46:56,770 >> Pensé que te daría un teaser de lo que será capaz de hacer 1068 00:46:56,770 --> 00:46:57,950 después de tomar CS50. 1069 00:46:57,950 --> 00:47:02,620 Déjame ir a cs.harvard.edu / rob, nuestra propia página de Rob Bowden. 1070 00:47:02,620 --> 00:47:06,080 Él hizo esto por nosotros. 1071 00:47:06,080 --> 00:47:07,490 Así que pronto será capaz de hacer eso. 1072 00:47:07,490 --> 00:47:10,660 Y también, lo que has oído esta mañana - 1073 00:47:10,660 --> 00:47:12,480 lo que has oído esta mañana - 1074 00:47:12,480 --> 00:47:13,780 >> [MÚSICA Hamster Dance] 1075 00:47:13,780 --> 00:47:15,702 >> - Usted será capaz de hacer esto. 1076 00:47:15,702 --> 00:47:16,790 Que nos espera el miércoles. 1077 00:47:16,790 --> 00:47:17,791 Nos vemos entonces. 1078 00:47:17,791 --> 00:47:22,950 >> [MÚSICA Hamster Dance] 1079 00:47:22,950 --> 00:47:24,300 DAVID MALAN: En la próxima CS50 - 1080 00:47:24,300 --> 00:47:31,670