ALTAVOZ 1: Muy bien, así que estamos de vuelta. Bienvenido a CS50. Este es el final de la séptima semana. Así que recordar que la última vez, empezamos mirando ligeramente más sofisticado estructuras de datos. Dado que hasta ahora, todo lo que teníamos realmente a nuestra disposición era esto, una matriz. Pero antes de descartar la matriz como no todo lo que interesante, que de hecho se realmente es, ¿cuáles son algunas de las ventajas de estos datos sencilla estructurar hasta el momento? ¿Qué es lo bueno? Por lo que hemos visto? ¿Qué tienes? Nada. ESTUDIANTE: [inaudible]. ALTAVOZ 1: ¿Qué es eso? ESTUDIANTE: [inaudible]. ALTAVOZ 1: Tamaño fijo. OK, así que ¿por qué es bueno, aunque de tamaño fijo? ESTUDIANTE: [inaudible]. ALTAVOZ 1: OK, así que es eficiente en la el sentido de que se puede asignar una cantidad fija de espacio, lo cual es de esperar es precisamente tanto espacio que quieras. Así que podría ser absolutamente una ventaja. ¿Cuál es la otra cara de una matriz? ¿Sí? ESTUDIANTE: [inaudible]. ALTAVOZ 1: Todo el - lo siento? ESTUDIANTE: [inaudible]. ALTAVOZ 1: Todos los cuadros en la memoria o uno junto al otro. Y eso es útil - por qué? Eso es muy cierto. Pero ¿cómo podemos aprovechar esa verdad? ESTUDIANTE: [inaudible]. ALTAVOZ 1: Exactamente, podemos mantener un registro de donde todo es sólo saber una dirección, a saber, la dirección de la primer byte de ese trozo de memoria. O en el caso de la cadena, la dirección de la primera charla en esa cadena. Y a partir de ahí, podemos encontrar el final de la cadena. Podemos encontrar el segundo elemento, el tercer elemento, y así sucesivamente. Y así, la manera elegante de describir que característica es que las matrices nos dan de acceso aleatorio. Sólo mediante el uso del corchete notación y un número, puede saltar a un elemento específico de la matriz en tiempo constante, gran O de uno, por así decirlo. Pero ha habido algunos inconvenientes. Lo que un conjunto no lo hacen con mucha facilidad? ¿Qué no hacer bien? ESTUDIANTE: [inaudible]. ALTAVOZ 1: ¿Qué es eso? ESTUDIANTE: [inaudible]. ALTAVOZ 1: Ampliación de tamaño. Así que los aspectos negativos de la matriz son precisamente lo contrario de lo que el Upsides son. Así que una de las desventajas es que es un tamaño fijo. Así que realmente no se puede crecer. Puede reasignar un pedazo más grande de la memoria y, a continuación, mover los elementos antiguos en la nueva matriz. Y luego liberar la matriz de edad, para los ejemplo, mediante el uso de malloc o similar función llamada realloc, que reasigna memoria. Realloc, como un aparte, intenta darle memoria que está al lado de la matriz que ya tiene. Pero podría mover cosas alrededor del todo. Pero en fin, eso es caro, ¿no? Porque si tienes un trozo de memoria de este tamaño, pero realmente quieres uno de este tamaño, y desea conservar los elementos originales, que tienen más o menos un proceso de copia de tiempo lineal eso tiene que suceder de antigua matriz a la nueva. Y la realidad está pidiendo a la operación sistema una y otra vez y de nuevo por grandes trozos de la memoria puede comenzar que le costará algo de tiempo también. Así que es tanto una bendición como una maldición en disfrazar, el hecho de que estas matrices son de tamaño fijo. Pero si introducimos en cambio algo como éste, que hemos denominado una ligado lista, tenemos unas cuantas ventajas y algunas desventajas también aquí. Así que una lista enlazada es simplemente un dato estructura compuesta de C estructuras en esta caso, en que una estructura, el recuerdo, es sólo un contenedor para una o más específica tipos de variables. En este caso, lo que hacen los tipos de datos parecen estar dentro de la estructura que última vez que se llama un nodo? Cada uno de estos rectángulos es un nodo. Y cada uno de los rectángulos más pequeños dentro de ella es un tipo de datos. ¿Qué tipos dijimos estaban el lunes? ¿Sí? ESTUDIANTE: [inaudible]. ALTAVOZ 1: Una variable y un puntero, o más específicamente, un int, para n, y un puntero en la parte inferior. Tanto de los que pasan a ser de 32 bits, por lo menos en un equipo como éste CS50 Appliance y por lo que son dibujado por igual en tamaño. Entonces, ¿qué está utilizando el puntero aunque para parecer? ¿Por qué añadir esta flecha ahora, cuando las matrices fueron tan agradable y limpio y simple? ¿Cuál es el puntero haciendo por nosotros en cada uno de estos nodos? ESTUDIANTE: [inaudible]. ALTAVOZ 1: Exactamente. Le está diciendo a donde el siguiente es. Así que en cierto modo me utilizo la analogía de utilizando un hilo a una especie de enhebrar estos nodos juntos. Y eso es exactamente lo que estamos haciendo con punteros porque cada uno de estos trozos de memoria pueden o no pueden ser contigua, espalda con espalda hacia atrás dentro de la memoria RAM, ya que cada vez que llamada diciendo malloc, dame suficiente bytes para un nuevo nodo, podría estar aquí o podría estar aquí. Podría estar aquí. Podría estar aquí. Usted simplemente no sabe. Pero el uso de punteros en las direcciones de esos nodos, puede coserlos juntos en una manera que parece visualmente como una lista, incluso si estas cosas son todo extendido en todo su ser o su dos o tus cuatro gigabytes de RAM dentro de su propio equipo. De modo que el lado negativo, pues, de una lista enlazada es lo que? ¿Qué es un precio que estamos al parecer, el pago? ESTUDIANTE: [inaudible]. ALTAVOZ 1: Más espacio, ¿no? Hemos, en este caso, duplicamos la cantidad de espacio, porque hemos ido de 32 bits para cada nodo, para cada uno int, por lo que ahora de 64 bits, ya que tiene que mantener en torno a un puntero también. Usted obtiene más eficiencia si su estructura es más grande que esta cosa simple. Si usted realmente tiene un estudiante en el interior de que es un par de cadenas de nombre y la casa, tal vez un número de identificación, tal vez algunos otros campos en total. Así que si usted tiene un gran suficiente estructura, entonces tal vez el costo del puntero es no es una cosa muy importante. Esto es un poco de un caso límite en que estamos almacenando una sencilla primitiva, tales dentro de la lista enlazada. Pero el punto es el mismo. Definitivamente estás gastando más memoria, pero que está recibiendo flexibilidad. Porque ahora si quiero agregar un elemento al principio de esta lista, Tengo que asignar un nuevo nodo. Y tengo que acaba de actualizar los flechas de alguna manera, con sólo mover algunos indicadores alrededor. Si quiero insertar algo en el mitad de la lista, no tiene por qué empujar a todos a un lado como lo hicimos en pasado semanas con nuestros voluntarios que representado una matriz. Yo sólo puedo asignar un nuevo nodo y a continuación, sólo apuntar las flechas en diferentes direcciones, ya que no hace que permanecer en real memoria una verdadera línea como he dibujado aquí en la pantalla. Y luego, por último, si desea insertar algo al final de la lista, es aún más fácil. Esta es una especie de notación arbitraria, pero un triple de 34, tomar una conjetura. ¿Cuál es el valor de su indicador más probablemente dibujado algo así como un viejo antena de escuela allí? ESTUDIANTE: [inaudible]. ALTAVOZ 1: Probablemente es nulo. Y de hecho es uno de los autores de representación de nulo. Y es nula, porque a pesar de todo necesita saber dónde está el final de un vinculado lista es, para que no se mantiene después y siguiendo y siguiendo estas flechas a algún valor de basura. Así nula significará que no es más nodos a la derecha del número 34, en este caso. Así que proponemos que podemos poner en práctica este nodo en el código. Y hemos visto este tipo de sintaxis antes. Typedef simplemente define un nuevo tipo de nosotros, nos da un sinónimo como cadena era para char *. En este caso, se nos va a dar notación abreviada de manera que el nodo struct puede en su lugar sólo puede escribir como nodo, que es mucho más limpio. Es mucho menos detallado. Dentro de un nodo es aparentemente un int llamada n, y luego un nodo de estructura * lo que significa exactamente lo que queríamos la flechas para significar, un puntero a otra nodo del mismo tipo de datos exacta. Y propongo que podríamos poner en práctica un función de búsqueda de este tipo, que en primera vista podría parecer un poco compleja. Pero vamos a verlo en su contexto. Quiero pasar al aparato aquí. Permítanme abrir un archivo llamado listar cero punto h. Y que sólo contiene la definición que acabo de ver hace un momento para estos datos tipo llamado un nodo. Así que hemos puesto que en un archivo de puntos h. Y en un aparte, a pesar de que esta programa que usted está a punto de ver es no todo lo que complejo, es de hecho convenciones al escribir un programa para poner las cosas como los tipos de datos, para sacar constantes a veces, dentro de su archivo de cabecera y no necesariamente en el archivo de C, sobre todo cuando su programas se hacen más grandes y más grandes, de modo que usted sabe dónde buscar, tanto para documentación en algunos casos, o para lo básico como este, el definición de algún tipo. Si ahora abro la lista de puntos cero c, notar un par de cosas. Incluye unos archivos de cabecera, la mayoría de los cuales hemos visto antes. Incluye su propio archivo de cabecera. Y en un aparte, ¿por qué eso es doble cita aquí, en comparación con el ángulo soportes en la línea que He destacado allí? ESTUDIANTE: [inaudible]. ALTAVOZ 1: Sí, así que es un archivo local. Así que si es un archivo local de su propia aquí en la línea 15, por ejemplo, se utiliza las comillas dobles en vez de los paréntesis angulares. Ahora bien, esto es algo interesante. Nótese que he declarado un mundial variable en este programa en la línea 18 llamó en primer lugar, la idea de esto es va a ser un puntero a la primera nodo en mi lista enlazada, y he inicializa a null, porque he no asignado ningún real nodos por el momento. Así que esto representa, gráficamente, lo que vi hace un momento en la imagen como ese puntero en el extremo a mano izquierda. Así que ahora mismo, ese puntero no tiene una flecha. En su lugar, es nulo. Pero representa lo que será el dirección del primer real nodo en esta lista. Así que he implementado es un mundial porque, como se verá, todo esto programa hace en la vida se implemento una lista enlazada para mí. Ahora tengo un par de prototipos aquí. Decidí implementar características como deleción, inserción, búsqueda y de recorrido - el último sólo estar a pie a través de la lista, la impresión de sus elementos. Y ahora aquí está mi rutina principal. Y no vamos a pasar mucho tiempo en éstas ya que esta es una especie de, ojalá viejo sombrero por ahora. Voy a hacer lo siguiente, mientras el usuario coopera. Así que uno, voy a imprimir salir de este menú. Y he formateado como limpiamente como pude. Si el usuario escribe en uno, para que los medios quieren borrar algo. Si el usuario escribe en dos, que los medios quieren insertar algo. Y así sucesivamente. Voy a continuación, pedirá a continuación, para un comando. Y entonces voy a utilizar GetInt. Así que este es un muy simple de menús interfaz en la que sólo tiene que escribir una asignación de número a uno de esos comandos. Y ahora tengo un interruptor limpio agradable declaración que va a cambiar el cualquiera que sea el usuario escribió pulg Y si ellos escriben uno, voy a llamar a delete y se rompa. Si se escriben dos, voy a llamar inserción y descanso. Y ahora noto que he puesto cada de estos en la misma línea. Esto es sólo una decisión estilística. Normalmente hemos visto algo como este. Pero decidí, francamente, mi programa parecía más fácil de leer porque era sólo cuatro casos a sólo lista así. Totalmente uso legítimo de estilo. Y yo voy a hacer esto siempre y cuando el El usuario no ha escrito cero, lo que me decidido significará que quieren dejar de fumar. Así que ahora doy cuenta de lo que soy vamos a hacer aquí. Voy a liberar a la lista aparentemente. Pero más sobre esto en un momento. Primero vamos a ejecutar este programa. Así que permítanme hacer una terminal más grande ventana, lista slash dot 0. Voy a seguir adelante e inserte por escribir dos, un número como 50, y ahora verás la lista es ahora 50. Y mi texto sólo desplaza un poco. Así que ahora cuenta la lista contiene el número 50. Vamos a hacer otro inserto tomando dos. Vamos a escribir el número como tal. Lista es ahora uno, seguido por 50. Así que esto es sólo una representación textual de la lista. Y vamos a insertar un número más como el número 42, que es de esperar va a terminar en el medio, porque este programa de clases particulares que elementos, ya que los inserta. Así que ahí lo tenemos. Programa Súper simple que podría absolutamente he utilizado una matriz, pero pasaría a estar usando una lista enlazada Sólo para que pueda dinámicamente crecer y reducir su tamaño. Así que echemos un vistazo a la búsqueda, si comando de tres carreras, quiero buscar para, por ejemplo, el número 43. Y nada se encontró al parecer, porque volví ninguna respuesta. Así que vamos a hacer esto de nuevo. Búsqueda. Vamos a buscar el 50, o más bien buscar el 42, que tiene una bonita poco significado sutil. Y he encontrado el sentido de la vida allí. Número 42, si usted no sabe la referencia, Google él. Está bien. Entonces, ¿qué ha hecho este programa para mí? Simplemente me ha permitido insertar este modo a lo largo y búsqueda de elementos. Vamos a avanzar rápidamente, entonces, esa función nos miró a el lunes como un reclamo. Así que esta función, reclamo, busca un elemento en la lista por primera uno, preguntar al usuario y luego llamar GetInt para obtener un int real que desea buscar. Entonces note esto. Voy a crear una variable temporal en línea 188 llama puntero - PTR - podrían haber llamado cualquier cosa. Y es un puntero a un nodo porque he dicho nodo * allí. Y estoy inicializando que sea igual a primero, para que yo efectivamente tengo mi dedo de la mano, por así decirlo, en el mismo primer elemento de la lista. Así que si mi mano derecha aquí es PTR estoy apuntando a lo mismo que la primera está apuntando. Así que ahora de nuevo en el código, ¿qué pasa después - este es un paradigma común cuando se repite sobre una estructura como un lista enlazada. Yo voy a hacer lo siguiente mientras puntero no es igual a null Así, mientras que mi dedo no está apuntando en algún nula valor, si el puntero de flecha n es igual a n. Nos daremos cuenta primero que n es lo que el tecleado por el usuario GetInts llamar aquí. Y puntero de flecha n significa qué? Bueno, si nos remontamos a la imagen aquí, si tengo un dedo apuntando a que primero nodo que contiene nueve, la flecha esencialmente significa que vaya a nodo y agarrar el valor en la posición n, en este caso, el campo de datos llama n. Como acotación al margen - y vimos esto un par de hace semanas, cuando alguien le preguntó - esta sintaxis es nuevo, pero no es así darnos poderes que no ya tienen. ¿Qué era esta frase equivale a utilizar notación de puntos y protagonizar un par de hace semanas cuando nos pelamos espalda esta capa un poco antes de tiempo? ESTUDIANTE: [inaudible]. ALTAVOZ 1: Exactamente, era la estrella, y entonces era punto estrella n, con paréntesis aquí, lo que se ve, Francamente, creo que mucha más críptico de leer. Pero indicador de la estrella, como siempre, medios van allí. ¿Y una vez que estás allí, ¿qué datos qué campo desea acceder? Pues usted utiliza la notación de puntos para el acceso un campo de datos estructuras, y yo específicamente querer n. Francamente, yo diría esto es simplemente más difícil de leer. Es más difícil de recordar dónde salen de los paréntesis, la estrella y todo eso. Así que el mundo adoptó algunas sintáctica azúcar, por así decirlo. Apenas una manera atractiva de decir, esto es equivalente, y quizás más intuitivo. Si el puntero es de hecho un puntero, el flecha notación significa ir allí y encontrar el campo, en este caso llamado n. Así que si lo encuentro, noto lo que hago. Simplemente me imprimo, encontré ciento i, enchufar el valor para ese int. Yo lo llamo el sueño durante un segundo sólo para clase de hacer una pausa en las cosas en la pantalla para dar al usuario un segundo para absorber lo que acaba de suceder. Y entonces me rompo. De lo contrario, ¿qué hago? Actualizo puntero a la igualdad de puntero flecha siguiente. Así que para ser claros, esto significa ir allí, usando mi notación de la vieja escuela. Así que esto sólo significa ir a lo que sea usted está apuntando a que, en el muy primer caso es que estoy señalando a la estructura con nueve en el mismo. Así que he ido allí. Y entonces se entiende la notación de puntos, obtener el valor al siguiente. Pero el valor, a pesar de que se dibuja como un estrecho, es sólo un número. Es una dirección numérica. Así que esta una línea de código, ya sea escrito como éste, el más críptico manera, o así, los poco más manera intuitiva, simplemente significa mover mi mano desde el primer nodo al siguiente, y luego el siguiente, y a continuación, la siguiente, y así sucesivamente. Así que no voy a detenerme en el otro implementaciones de insertar y eliminar y el recorrido, los dos primeros de que son bastante implicados. Y creo que es muy fácil de conseguir perdido al hacerlo verbalmente. Pero lo que podemos hacer aquí es tratar de determinar cómo la mejor manera de hacer esto visualmente. Porque yo propondría que si desee insertar elementos en esta lista existente, que tiene cinco elementos - 9, 17, 22, 26, y 33 - si yo fuera a implementar esto en código, tengo que estudiar la manera de ir haciendo esto. Y yo propondría tomar pasos de bebé por lo que, en este caso me refiero, ¿cuáles son los posibles escenarios que nos podría encontrarse en general? En la aplicación de inserción para un ligado lista, esto sólo pasa a ser un ejemplo concreto de tamaño cinco. Bueno, si usted desea insertar un número, como decir el número uno, y mantener el orden establecido, donde obviamente, hace el número uno de la necesidad de ir en este ejemplo específico? Al igual que al principio. Pero lo interesante no es que si desea insertar una en este lista, qué necesidades puntero especiales ser actualizado aparentemente? En primer lugar. Así que yo diría, este es el primer caso que lo que se quiere tener en cuenta, una escenario que implica insertar al el principio de la lista. Vamos a arrancar tal vez una tan fácil o incluso caso más fácil, relativamente hablando. Supongamos que quiero insertar el el número 35 en el orden establecido. Obviamente pertenece allí. Entonces, ¿qué puntero obviamente va a tienen que actualizarse en ese escenario? Un triple de 34 convirtiéndose no nula pero la dirección de la estructura que contiene el número 35. Así que ese es el caso de dos. Así que ya, yo soy una especie de cuantificación la cantidad de trabajo que tengo que hacer aquí. Y, por último, el caso medio obvio es de hecho, en el medio, si quiero insertar algo así como decir 23, que va entre el 23 y el 26, pero Ahora las cosas se ponen un poco más participar porque lo punteros hay que cambiar? Así 22 obviamente necesita ser cambiado porque no puede apuntar a 26 más. Él tiene que apuntar al nuevo nodo que Voy a tener que destinar llamando malloc o algún equivalente. Pero también necesito que el nuevo nodo, 23 en este caso, para tener su puntero señalando a quién? 26. Y va a ser un orden de las operaciones aquí. Porque si hago esto tontamente, y yo por ejemplo comenzar por el principio de la lista, y mi objetivo es insertar 23. Y compruebo, le pertenece aquí, cerca de las nueve? No. ¿Pertenece aquí, junto a 17? No. ¿Le pertenece a este lugar junto a 22? Sí. Ahora bien, si soy tonto aquí, y no pensando en esto, yo podría asignar mi nuevo nodo para 23. Yo podría actualizar el puntero de el nodo llamado 22, que señala que en el nuevo nodo. Y entonces, ¿qué tengo que actualizar puntero del nuevo nodo que se va? ESTUDIANTE: [inaudible]. ALTAVOZ 1: Exactamente. Señalando a 26. Pero dammit si no tuviera ya actualizo Puntero del 22 al punto en el que este tipo, y Ahora tengo los huérfanos, el resto de la lista, por así decirlo. Así que el fin de las operaciones aquí va a ser importante. Para ello podría robar, decir, seis voluntarios. Y veamos si no podemos hacer esto visualmente en lugar del código se refiere. Y tenemos un poco de estrés encantadora bolas para usted hoy. Bien, ¿qué hay de una, dos, en el espalda - en el extremo allí. tres, cuatro, los dos chicos en la final. Y cinco, seis. Claro. Cinco y seis. Está bien y vamos a venir con ustedes la próxima vez. Muy bien, vamos arriba. Muy bien, ya que estás aquí primero, ¿te gustaría ser el que torpemente en Google Glass aquí? Muy bien, entonces, OK, Glass, grabar un video. Bueno, ya está bueno para ir. Muy bien, así que si ustedes pueden venir aquí, he preparado con antelación algunos números. Muy bien, vamos por aquí. ¿Y por qué no te vas un poco promover de esa manera. Y vamos a ver, ¿cómo te llamas, con el cristal de Google? ESTUDIANTE: Ben. ALTAVOZ 1: Ben? Bueno, Ben, que será la primera, literalmente. Así que vamos a enviarle al final de la etapa. Muy bien, y tu nombre? ESTUDIANTE: Jason. ALTAVOZ 1: Jason, OK tendrás ser el número nueve. Así que si quieres seguir Ben de esa manera. ESTUDIANTE: Jill. ALTAVOZ 1: Jill, vas a ser 17, que si yo hubiera hecho esto más inteligente, que tendría comenzado en el otro extremo. Usted va de esa manera. 22. Y usted es? ESTUDIANTE: María. ALTAVOZ 1: María, que será 22. Y su nombre es? ESTUDIANTE: Chris. ALTAVOZ 1: Chris, podrás 26. Y a continuación, por último. ESTUDIANTE: Diana. ALTAVOZ 1: Diana, usted será 34. Así que vienes por aquí. Muy bien, así que perfecto ordenados ordenar ya. Y vamos a seguir adelante y hacer esto para que podamos realmente - Ben sólo estás buscando tipo de hacia la nada allí. OK, así que vamos a seguir adelante y representan esta utilizando los brazos, al igual que yo, exactamente, ¿qué está pasando. Así que adelante y dense un o dos pies entre ustedes mismos. Y seguir adelante y punto con una mano para quienquiera que debe apuntar a basado en esto. Y si usted es sólo el punto nulo directamente hacia el suelo. OK, así que bien. Así que ahora tenemos una lista enlazada, y me dejó Propongo que voy a jugar el papel de PTR, así que no me molestaré llevar esto alrededor. Y entonces - alguien convención estúpida - usted puede llamar a esto todo lo que quieras - puntero predecesor, puntero pred - es sólo el apodo que dimos en nuestro código de ejemplo para la mano izquierda. La otra parte que va a ser de mantenimiento Saber quién es quién en la siguientes escenarios. Así que supongamos que, en primer lugar, quiero arrancar ese primer ejemplo de inserción, por ejemplo 20, en la lista. Así que voy a necesitar a alguien que encarnar el número 20 para nosotros. Así que tengo que malloc alguien de la audiencia. Vamos arriba. ¿Cómo te llamas? ESTUDIANTE: Brian. ALTAVOZ 1: Brian, de acuerdo, por lo que será el nodo que contiene 20. Muy bien, vamos por aquí. Y, obviamente, donde pertenece Brian? Así, en medio de - en realidad, Espera un minuto. Estamos haciendo esta fuera de orden. Estamos haciendo esto mucho más difícil de lo que debe ser en un principio. Bien, vamos a liberar a Brian y realloc Brian como cinco. OK, así que ahora queremos insertar Brian como cinco. Así que ven aquí al lado Ben sólo por un momento. Y, presumiblemente, puede decir donde esta historia se va. Pero vamos a pensar cuidadosamente acerca de el orden de las operaciones. Y es precisamente esta visual eso va a alinear con ese código de ejemplo. Así que aquí tengo PTR apuntando inicialmente no a Ben, per se, sino en lo que sea valor que contiene, que en este caso es - ¿cuál es tu nombre? ESTUDIANTE: Jason. ALTAVOZ 1: Jason, por lo tanto, Ben y yo estamos señalando a Jason en este momento. Así que ahora tengo que determinar, donde pertenece Brian? Así que lo único que tengo acceso a ahora es su elemento de datos n. Así que voy a comprobar, es Brian menos de Jason? La respuesta es verdadera. ¿Y ahora qué tiene que suceder, en el orden correcto? Necesito actualizar el número de punteros en total en esta historia? Donde mi mano todavía está apuntando a Jason, y su mano - si usted desea poner su mano como, más o menos, me no sé, un signo de interrogación. Bueno, bueno. Muy bien, por lo que tiene algunos candidatos. Cualquiera de Ben, yo o Brian o Jason o cualquier otra persona, que punteros tienen que cambiar? ¿Cuántos en total? OK, así que dos. Mi puntero en realidad no importa ya porque yo soy sólo temporal. Así que es a estos dos chicos, supuestamente, tanto Ben y Brian. Así que permítanme proponer que actualizamos Ben, ya que él es primero. El primer elemento de esta lista ahora va a ser Brian. Así que el punto Ben en Brian. Bien, ¿y ahora qué? ¿Quién se apunta a quién? ESTUDIANTE: [inaudible]. ALTAVOZ 1: Aceptar lo que Brian tiene para apuntar a Jason. Pero he perdido la cuenta de ese puntero? ¿Sé dónde está Jason? ESTUDIANTE: [inaudible]. ALTAVOZ 1: yo, como soy el puntero temporal. Y, presumiblemente, no he cambiado para señalar en el nuevo nodo. Así que simplemente podemos tener punto de Brian en el que estoy señalando. Y ya hemos terminado. Así caso de que uno, la inserción en el principio de la lista. Había dos pasos clave. Uno de ellos, tenemos que actualizar Ben, y luego también tenemos que actualizar Brian. Y entonces yo no tengo que molestar penosamente a través de el resto de la enumerar, porque ya encontramos su ubicación, porque pertenecía a la la izquierda del primer elemento. Muy bien, así que bastante sencillo. De hecho, se siente como que estamos casi haciendo esto demasiado complicado. Así que ahora vamos a arrancar el final de la lista, y ver dónde la complejidad comienza. Así que si ahora, de asignación de la audiencia. ¿Alguien quiere jugar al 55? Muy bien, lo vi primero su mano. Vamos arriba. Sí. ¿Cómo te llamas? ESTUDIANTE: [inaudible]. ALTAVOZ 1: Habata. Bien, vamos arriba. Usted será el número 55. Así que, por supuesto, pertenece al final de la lista. Así que vamos a jugar de nuevo la simulación conmigo siendo el PTR por un momento. Así que estoy primero va a apuntar a lo que apunta a Ben. Los dos estamos apuntando ahora a Brian. Así que 55 no sea inferior a cinco. Así que voy a actualizar mi mismo por apuntando a la siguiente triple de Brian, que ahora es, por supuesto, Jason. 55 no sea inferior a nueve, por lo que Voy a actualizar PTR. Voy a actualizar PTR. Voy a actualizar PTR Me va a actualizar PTR. Y yo voy a - hmm, ¿qué tu nombre? ESTUDIANTE: Diana. ALTAVOZ 1: Diana está señalando, por supuesto, en nulo con la mano izquierda. Así que ¿de dónde viene en realidad Habata pertenecer claramente? A la izquierda, aquí. Entonces, ¿cómo puedo saber que ponerla aquí Creo que he metido la pata. Porque lo que es arte PTR este momento en el tiempo? Null. Así que a pesar de que, visualmente, podemos obviamente ver todos estos chicos aquí en el escenario. Yo no he mantenido un seguimiento de la anterior persona en la lista. Yo no tengo un dedo señalando, en este caso, el número de nodo 34. Así que vamos a empezar en realidad esta vez. Así que ahora realmente necesito una segunda variable local. Y esto es lo que verás en el código de ejemplo C real, en tanto que yo voy, cuando actualizo mi mano derecha para señalar Jason, dejando detrás de Brian, me mejor empezar a usar mi mano izquierda para Actualiza donde yo estaba, de modo que a medida que avanzo a través de esta lista - más torpe de lo que pretendía ahora aquí visualmente - Voy a llegar a la final de la lista. Esta mano es todavía nula, lo cual es bastante inútil, salvo para indicar Estoy claramente al final de la lista, pero ahora por lo menos tengo esta puntero predecesor señalando aquí, así ahora lo que las manos y lo que necesitan punteros ser actualizado? Cuya mano es lo que quieres reconfigurar primero? ESTUDIANTE: [inaudible]. ALTAVOZ 1: OK, así que Diana. ¿Dónde quieres que señalar Diana del puntero de la izquierda en? En 55, presumiblemente, de manera que hemos insertado allí. ¿Y dónde debería ir el 55 de puntero? Presionado, que representa un valor nulo. Y mis manos, en este punto, no lo hacen importa porque no eran más que variables temporales. Así que ahora que hemos terminado. Así que la complejidad adicional allí - y que no es tan difícil de implementar, pero necesitamos una variable secundaria para hacer Asegúrese de que antes de pasar a mi derecho lado, puedo actualizar el valor de mi izquierda mano, puntero pred en este caso, por lo que tengo un indicador de seguimiento hacer un seguimiento de dónde estaba. Ahora, como un aparte, si estás pensando en este a través, esto se siente como si fuera un poco molesto tener que mantener seguimiento de esta mano izquierda. ¿Qué sería de otra solución a este problema han sido? Si has llegado a rediseñar los datos estructura que estamos hablando a través de estos momentos? Si sólo un poco se siente un poco molesto tener, como, dos punteros pasando por la lista, ¿quién más podría han, en un mundo ideal, mantenido información que necesitamos? ¿Sí? ESTUDIANTE: [inaudible]. ALTAVOZ 1: Exactamente. Justo lo que hay realmente una interesante germen de una idea. Y esta idea de un puntero anterior, señalando el elemento anterior. ¿Y si sólo encarnó ese dentro de la propia lista? Y va a ser difícil de visualizar esto sin todo el papel cayendo al suelo. Pero supongamos que estos chicos utilizan tanto de sus manos para tener un anterior puntero, y un indicador de siguiente, con lo que aplicación de lo que vamos a llamar a un doble lista enlazada. Eso me permitiría especie de rebobinado, mucho más fácilmente sin mí, el programador, tener que mantener seguimiento manual - verdaderamente manualmente - de donde había estado previamente en la lista. Así que no vamos a hacer eso. Vamos a mantenerlo simple, porque eso es va a tener un precio, el doble de mucho espacio para los punteros, si quieres una segunda. Pero eso es de hecho una común estructura de datos conocida como una lista doblemente enlazada. Vamos a hacer el último ejemplo aquí y poner estos chicos fuera de su miseria. Así malloc 20. Vamos desde el pasillo allí. Muy bien, ¿cuál es tu nombre? ESTUDIANTE: [inaudible]. ALTAVOZ 1: ¿Cómo dice? ESTUDIANTE: [inaudible]. ALTAVOZ 1: Demeron? Aceptar vamos arriba. Usted será el 20. Usted, evidentemente, va a pertenecen entre el 17 y el 22. Así que vamos a aprender la lección. Voy a empezar puntero señalando a Brian. Y yo voy a tener mi mano izquierda sólo actualizar a Brian como me mudo a Jason, la comprobación hace 20 menos de nueve? No. Es 20 menos de 17? No. Es 20 menos de 22? Sí. Entonces, ¿qué consejos o las manos deben cambiar donde están apuntando ahora? Así que podemos hacer 17 que apunta a los 20. Así que eso está bien. ¿Dónde queremos señalar el puntero ahora? A los 22 años. Y sabemos donde 22 es, de nuevo, gracias a mi puntero temporal. Así que estamos bien allí. Así que debido a esto el almacenamiento temporal He mantenido un seguimiento de dónde es cada uno. Y ahora usted puede ir visualmente en donde al que pertenece, y ahora nos necesita 1, 2, 3, 4, 5, 6, 7, 8, 9 bolas de la tensión, y una ronda de aplausos para estos chicos, si pudiéramos. Muy bien hecho. [Aplausos] ALTAVOZ 1: Muy bien. Y es posible mantener las piezas de papel como recuerdos. Muy bien, entonces, confía en mí que es mucho fácil de caminar a través de eso con los seres humanos que es con código real. Pero lo que encontrará en un momento ahora, es el mismo - oh, gracias. Gracias - es que usted encontrará que los mismos datos estructura, una lista enlazada, puede en realidad ser utilizado como un bloque de construcción para aún más estructuras de datos sofisticadas. Y se dan cuenta demasiado el tema aquí es que que absolutamente hemos introducido más complejidad en la implementación de este algoritmo. Inserción, y si nos fuimos a través de él, supresión y búsqueda, es un poco de más complicado de lo que estaba con una matriz. Pero ganamos algo de dinamismo. Tenemos una estructura de datos de adaptación. Pero, de nuevo, tenemos que pagar un precio de tener alguna complejidad adicional, tanto en su aplicación. Y se nos da el acceso aleatorio. Y para ser honesto, no hay algún buen portaobjetos limpio me puede dar esa dice aquí es por qué una lista enlazada es mejor que una matriz. Y dejar las cosas así. Debido a que el tema recurrente ahora, incluso más aún en las próximas semanas, es que no es necesariamente una respuesta correcta. Es por eso que tenemos el eje por separado de diseñar para los boletines de problemas. Va a ser muy sensible al contexto si desea utilizar estos datos estructura o que uno, y lo hará dependerá de lo que te importa en términos de los recursos y la complejidad. Pero permítanme proponer que los datos ideales estructura, el santo grial, sería algo que es constante de tiempo, independientemente de la cantidad de cosas es dentro de él, ¿no sería increíble si un estructura de datos devuelve respuestas en constante de tiempo. Sí. Esta palabra es en su gran diccionario. O no, esta palabra no es. O tal problema. Bueno vamos a ver si no podemos, al menos, dar un paso en esa dirección. Permítanme proponer una nueva estructura de datos que puede ser utilizado para diferentes cosas, en este caso se llama una tabla hash. Y por lo que estamos realmente de nuevo a mirar en una matriz, en este caso, y algo arbitrariamente, he dibujado esta la tabla de hash como una matriz con una especie de matriz de dos dimensiones - o más bien que está representado aquí como dos matriz bidimensional - pero esto es sólo una matriz de tamaño 26, de tal manera que si nos llame a la mesa de matriz, soporte de mesa cero es el rectángulo en la parte superior. Tabla soporte 25 es el rectángulo en la parte inferior. Y así es como yo podría dibujar un datos estructura en la que quiero para almacenar nombres de las personas. Así por ejemplo, y no voy a señalar a la Todo aquí en la cabeza, si me tenido esta matriz, que ahora voy a llamar a una tabla hash, y esto es de nuevo ubicación cero. Esto aquí es la ubicación uno, y así sucesivamente. Afirmo que quiero utilizar estos datos estructura, por el bien de la discusión, para almacenar nombres de las personas, Alice y Bob y Charlie y otros nombres. Así que pensar en esto ahora como el inicio de, por ejemplo, un diccionario con un montón de palabras. Ellos resultan ser nombres en nuestro ejemplo aquí. Y esto es muy pertinente, tal vez, para la implementación de un corrector ortográfico, como hemos fuerza para la solución seises. Así que si tenemos una matriz de tamaño total de 26 de manera que esta es la ubicación 25a en la parte inferior, y yo sostengo que Alice es la primera palabra en el diccionario de nombres que quiero insertar en la memoria RAM, en esta estructura de datos, donde son instintos que le dice que de Alice nombre debe ir en esta serie? Tenemos 26 opciones. Dónde queremos ponerla? Nosotros la queremos en soporte de cero, ¿no? Una de Alice, vamos a llamar a ese cero. Y B será uno, y C será de dos. Así que vamos a escribir El nombre de Alice aquí. Si a continuación, insertamos Bob, su nombre pasará aquí. Charlie va a ir aquí. Y así sucesivamente a lo largo de esta estructura de datos. Esta es una estructura de datos maravillosa. ¿Por qué? Bueno, ¿qué es el tiempo de ejecución de insertar el nombre de un ser humano en este estructura de datos en este momento? Teniendo en cuenta que esta tabla se implementa, verdaderamente, como una matriz. Bueno, es la constante de tiempo. Es el fin de una. ¿Por qué? Bueno, ¿cómo determinar donde pertenece Alice? Te ves en qué letra de su nombre? El primero. Y se puede llegar, si se trata de una cadena, con sólo mirar cadena soporte de cero. Así el carácter de orden cero de la cadena. Eso es fácil. Hicimos eso en la criptografía Hace asignación semana. Y luego, una vez que sabes que de Alice letra es mayúscula, podemos restar off 65 o la propia capital de A, eso nos da cero. Así que ahora sabemos que Alice pertenece en la posición cero. Y teniendo en cuenta un puntero a estos datos estructura, de algún tipo, hace cuánto tiempo que me lleve a encontrar la ubicación cero en una matriz? A sólo un paso, ¿no es la constante de tiempo por la que el acceso aleatorio propuso fue una característica de una matriz. Así que en resumen, averiguar lo que el índice de el nombre de de Alice es, que es, en este caso, es A, o vamos a resolver que a cero, donde B es uno y C es dos, pensando que fuera es la constante de tiempo. Sólo tengo que mirar en su primera carta, averiguar donde cero es un matriz es también constante de tiempo. Así que técnicamente eso es como dos pasos ahora. Pero eso sigue siendo constante. Así que llamamos a esa gran O de uno, por lo que hemos Alice inserta en esta tabla en constante de tiempo. Pero, por supuesto, estoy siendo ingenuo, ¿no? ¿Qué pasa si hay un Aarón en la clase? O Alicia? O cualquier otro nombre que comience con A. ¿Dónde vamos a poner esa persona, ¿verdad? Quiero decir, ahora mismo sólo hay tres gente en la mesa, así que tal vez debe poner Aaron en la ubicación cero uno dos tres. Bien, yo podría poner una aquí. Pero entonces, si se quiere insertar en David esta lista, ¿a dónde va David? Ahora nuestro sistema comienza a metabolizar abajo, derecha? Porque ahora David termina aquí si Aaron es en realidad aquí. Y por lo que ahora esta todo idea de tener un estructura de datos limpia que nos da inserciones de tiempo constantes ya no es constante de tiempo, porque tengo que comprobar, oh, maldita sea, ya hay alguien trabajando en la ubicación de Alice. Permítame sondear el resto de estos datos estructura, en busca de un lugar para poner alguien como el nombre de Aarón. Y para que también está empezando tomar el tiempo lineal. Por otra parte, si ahora quieres encontrar el Aaron en esta estructura de datos, y cheque, y el nombre de Aarón no está aquí. Lo ideal sería que usted acaba de decir de Aarón no en la estructura de datos. Pero si usted comienza a hacer espacio para Aaron donde debería haber sido un D o un correo, usted, peor de los casos, tiene que comprobar toda la estructura de datos, en cuyo caso se convirtiera en algo lineal en el tamaño de la tabla. Así bien, voy a arreglar esto. El problema aquí es que tuve 26 elementos de esta matriz. Permítanme cambiaré. ¡Vaya. Déjame cambiar de tal manera que en lugar de ser de talla 26 en total, cuenta de la parte inferior índice se va a cambiar a n menos 1. Si 26 es claramente demasiado pequeño para los seres humanos " nombres, porque hay miles de nombres del mundo, vamos a hacer en 100 o 1000 o 10000. Vamos a asignar un espacio mucho más. Bueno, eso no disminuye necesariamente la probabilidad de que no vamos a tener dos personas con nombres que empiecen con A, y así, que iba a tratar de poner un nombres en lugar de cero aún. Siguen yendo a chocar, que significa que todavía necesitamos una solución para poner Alice y Aarón y Alicia y otros nombres que empiecen con A otro lugar. Pero, ¿cuánto de un problema es el siguiente? ¿Cuál es la probabilidad de que tener colisiones en un datos estructura como esta? Bueno, déjame - volveremos a esa pregunta aquí. Y mira cómo podríamos resolverlo primero. Déjame sacar esta propuesta aquí. Lo que acabamos de describir es un algoritmo, una heurística llamada lineal sondeo según el cual, si se trató de insertar algo aquí en estos datos estructura, que se llama una tabla hash, y no hay lugar allí, verdaderamente sondear la estructura de datos cheques, es este disponible? ¿Es esta disponible es esta disponible? Es esta disposición? Y cuando finalmente es, insertar el nombre que la intención original en otro lugar en esa ubicación. Pero en el peor de los casos, el único punto podría ser la parte inferior de los datos estructura, el final de la matriz. Así sondeo lineal, en el peor de los casos, recae en un algoritmo lineal en Aaron, si él pasa a ser insertado última en esta estructura de datos, que podría colisionar con esta primera ubicación, pero luego terminar por la mala suerte en el final. Así que esto no es una constante santo grial tiempo para nosotros. Este enfoque de la inserción de elementos en una estructura de datos llamada un valor hash tabla no parece ser la constante de tiempo al menos no en el caso general. Puede delegar en algo lineal. ¿Y qué si resolvemos las colisiones algo diferente? Así que aquí está una más sofisticada aproximación a lo que es aún denominada tabla hash. Y por hash, como un aparte, lo que Quiero decir es el índice que Me he referido antes. Para discutir algo puede ser considerado como un verbo. Así que si el hash de Alice un nombre, una función hash, por así decirlo, debe devolver un número. En este caso es cero si pertenece a posición cero, uno si ella pertenece al ubicación uno, y así sucesivamente. Así que mi función hash hasta ahora ha sido super simple, sólo mirando el primera letra del nombre de alguien. Pero una función hash toma como entrada de alguna pieza de datos, un cadena, un entero, lo que sea. Y escupe típicamente un número. Y ese número es donde los datos elemento pertenece en una estructura de datos conocido aquí como una tabla hash. Por lo que sólo intuitivamente, se trata de una un contexto ligeramente distinto. En realidad, esto se refiere a un ejemplo involucrando los cumpleaños, donde puede haber tantos como 31 días en el mes. Pero lo que hizo esta persona decide hacer en caso de una colisión? Contexto siendo ahora, no un choque de nombres, pero una colisión de los cumpleaños, si dos personas tienen la misma fecha de nacimiento en el 2 de octubre, por ejemplo. ESTUDIANTE: [inaudible]. ALTAVOZ 1: Sí, así que aquí tenemos el aprovechamiento de las listas enlazadas. Así se ve un poco diferente que dibujamos antes. Pero parece que tenemos a un array en el lado de mano izquierda. Eso es un índice, por ninguna en particular la razón. Pero sigue siendo una matriz. Es una matriz de punteros. Y cada uno de esos elementos, cada uno de los estos círculos o rayas verticales - la raya vertical representando nula - cada uno de estos punteros es aparentemente señalando qué estructura de datos? Una lista enlazada. Así que ahora tenemos la capacidad de codificar directamente en nuestro programa el tamaño de la tabla. En este caso, sabemos que nunca hay más de 31 días en un mes. Tan duro codificando un valor como 31 es razonable en ese contexto. En el contexto de los nombres, de codificación duro 26 no es irrazonable, la gente de sólo nombres comienzan con, por ejemplo, el alfabeto de la A a la participación de Z. Podemos meter a todos en que los datos estructura, siempre que, cuando tenemos una colisión, no ponemos los nombres aquí, nosotros en cambio pensamos en estas células no como cadenas de sí mismos, sino como punteros a, por ejemplo, Alice. Y entonces Javier puede tener otro puntero a otro nombre que comience con A. Y Bob realidad va por aquí. Y si hay otro nombre de partida con B, termina aquí. Y así cada uno de los elementos de este mesa dos, si hemos diseñado este un poco más inteligentemente - vamos - si hemos diseñado este un poco más inteligentemente, ahora se convierte en un dato de adaptación estructura, donde no hay límite duro de la cantidad de elementos que se pueden insertar en ella, porque si usted tiene una colisión, eso está bien. Sólo tienes que ir adelante y añadirlo al lo que vimos hace poco era conocida como una lista enlazada. Bueno hagamos una pausa por un momento. ¿Cuál es la probabilidad de una colisión en el primer lugar? Bien, tal vez soy más de pensar, tal vez Yo soy más de la ingeniería de este problema, porque ¿sabes qué? Sí, puedo llegar a arbitraria ejemplos de la parte superior de mi cabeza, como Allison y Aarón, pero en realidad, dada una distribución uniforme de insumos, es decir algunas inserciones aleatorias en una estructura de datos, lo que realmente es la probabilidad de una colisión? Pues resulta que, en realidad es super alta. Permítanme generalizar este problema es como este. Así que en una habitación de estudiantes n CS50, lo que es la probabilidad de que al menos dos estudiantes en la sala de tener la misma fecha de nacimiento? Así que no hay de qué. algunos Hund - 200, 300 personas aquí y varios cientos de personas en el país hoy en día. Así que si quería que nos preguntemos cuál es la probabilidad de que dos personas en esta sala que tiene el mismo cumpleaños, podemos resolver esto. Y yo pretendo en realidad hay dos las personas con el mismo cumpleaños. Por ejemplo, ¿alguien tiene cumpleaños hoy? Ayer? ¿Mañana? Muy bien, así que se siente como que voy a tener que hacer esto 363 o así más veces a la figura en realidad a cabo si tenemos una colisión. O podríamos hacer esto matemáticamente en lugar de tediosamente haciendo esto. Y proponer lo siguiente. Así que propongo que podríamos modelar el probabilidad de que dos personas tengan el mismo día que la probabilidad de 1 menos la probabilidad de que nadie que tiene el mismo cumpleaños. Así que para conseguir esto, y esto es sólo el forma elegante de escribir esto, para el primera persona en la habitación, él o ella puede tener uno cualquiera de los posibles cumpleaños asumiendo 365 días en el año, con perdón de las personas con el cumpleaños 29 de febrero. Así que la primera persona en esta habitación es gratis para tener cualquier número de cumpleaños de las 365 posibilidades para que que vamos a hacer que 365 dividido por 365, que es uno. La siguiente persona en la sala, si el objetivo es para evitar una colisión, sólo puede tener su cumpleaños sobre cómo muchos días diferentes posibles? 364. Así que el segundo término de esta expresión es esencialmente haciendo que las matemáticas para nosotros restando fuera de una posible día. Y a continuación, el día siguiente, el día siguiente, la día siguiente hasta el número total de personas en la habitación. Y si consideramos a continuación, ¿qué es, entonces, la probabilidad de que no todo el mundo tener cumpleaños únicos, pero una vez más 1 menos que, lo que tenemos es una expresión que puede muy caprichosamente tener este aspecto. Pero es más interesante a ver visualmente. Este es un gráfico donde en el eje x es el número de personas en la habitación, el número de cumpleaños. En el eje y es la probabilidad de una colisión, dos personas que tiene el mismo cumpleaños. Y la comida para llevar de esta curva es que tan pronto como se llega a gustar 40 estudiantes, que están haciendo en un 90% de probabilidad combinatorically de dos personas o más tienen el mismo cumpleaños. Y una vez que llegue a gustar 58 personas es casi el 100% de una ocasión los dos personas en la habitación se va a tener la mismo día, a pesar de que no hay 365 o 366 posibles cubetas y sólo 58 personas en la sala. Sólo estadísticamente es muy probable que obtener las colisiones, que en definitiva motiva esta discusión. Que incluso si conseguimos extravagancias, y empezar a tener estas cadenas, todavía estamos va a tener colisiones. Así que plantea la pregunta, ¿cuál es la costo de hacer inserciones y deleciones en una estructura de datos como este? Pues permítanme proponer - y déjame volver a la pantalla durante aquí - si tenemos n elementos en el lista, por lo que si estamos tratando de insertar n elementos, y tenemos cuántos cubos total de? Digamos 31 cubos en total en el caso de los cumpleaños. ¿Cuál es la longitud máxima de un de estas cadenas potencialmente? Si de nuevo hay 31 posibles cumpleaños en un mes determinado. Y sólo estamos aglutinación todos - En realidad eso es un ejemplo tonto. Vamos a hacer 26 en su lugar. Así que si realmente tienen las personas cuyos nombres Comience con una Z a través, lo que da nos 26 posibilidades. Y estamos utilizando una estructura de datos como el que acabamos de ver, por lo que tenemos una matriz de punteros, cada uno de los cuales apunta a una lista enlazada donde el primera lista están todos con el nombre de Alice. La segunda lista es cada con el Nombre que comienza con A, a partir con B, y así sucesivamente. ¿Cuál es la duración probable de cada una de esas listas si asumimos un bonito y limpio distribución de los nombres de la A a la Z a través de toda la estructura de datos? Hay n personas en la estructura de datos dividido por 26, si están bien repartidas en el conjunto estructura de datos. Así la longitud de cada uno de estos cadenas se n divididos por 26. Pero en notación O grande, ¿qué es eso? ¿Qué es eso en realidad? Así que no deja de ser n, ¿verdad? Debido a que hemos dicho en el pasado, que Ugh se divide por 26. Sí, en realidad es más rápido. Pero en teoría, no es fundamentalmente todo lo que más rápido. Así que no parece que sea todo lo que mucho más cerca de este santo grial. De hecho, esto es sólo el tiempo lineal. Heck, en este punto, ¿por qué no nos sólo tiene que utilizar una lista enlazada enorme? Por qué no nos limitamos a usar una enorme matriz para almacenar los nombres de los todos en la sala? Bueno, ¿hay todavía algo convincente sobre una tabla hash? ¿Hay todavía algo convincente sobre una estructura de datos que se parece a esto? Este. ESTUDIANTE: [inaudible]. ALTAVOZ 1: Correcto, y otra vez si es sólo un algoritmo de tiempo lineal, y un estructura de datos de tiempo lineal, ¿por qué no me simplemente almacenar el nombre de todos en una gran matriz o en una lista enlazada grande? Y dejar de hacer CS mucho más difícil de lo que debe ser? ¿Qué es convincente acerca de esto, incluso aunque me rasqué la saca? ESTUDIANTE: [inaudible]. ALTAVOZ 1: Inserciones no lo son? Caro ya. Así inserciones potencialmente podría todavía ser constante de tiempo, incluso si los datos estructura se parece a esto, una serie de punteros, cada uno de ellos está apuntando a potencialmente una lista enlazada. ¿Cómo puedes lograr constante tiempo de inserción de los nombres? Se adhieren en la parte delantera, la derecha? Si sacrificamos un objetivo de diseño de antes, donde nos queríamos mantener el nombre de todos, por ejemplo, clasificar, o la totalidad de los números en el escenario ordenados, supongamos que tenemos un lista enlazada sin clasificar. Sólo nos cuesta uno o dos pasos, como en el caso de Ben y Brian anteriormente, para insertar un elemento en el principio de la lista. Así que si no nos preocupamos acerca de la ordenación de todo de los nombres que empiecen con A o la totalidad los nombres que comienzan con B, que todavía podemos lograr la inserción de tiempo constante. Ahora, mirando hacia arriba Alice o Bob o cualquier nombre más en general sigue siendo qué? Es grande O de n dividido por 26, en el caso ideal, donde todo el mundo está uniformemente distribuida, donde hay tantos doctores ya que hay Z, que es probablemente poco realista. Pero eso sigue siendo lineal. Pero aquí volvemos al punto ser notación asintótica de teóricamente cierto. Pero en el mundo real, si afirmo que mi programa puede hacer algo 26 veces más rápido que el tuyo, cuyo programa vas a preferir el uso de? La tuya o la mía, que es 26 veces más rápido? Siendo realistas, la persona cuyo es 26 veces más rápido, incluso si teóricamente nuestros algoritmos se ejecutan en el mismo tiempo de ejecución asintótica. Permítanme proponer un diferente solución en conjunto. Y si esto no sopla tu mente, estamos fuera de las estructuras de datos. Así que este es un trie - clase de nombre estúpido. Viene de recuperaciones, y la palabra se escribe trie, t-r-i-e, a causa de recuperación de golf suena como trie. Pero esa es la historia de la palabra trie. Así que un trie es de hecho una especie de árbol, y también es un juego de la palabra. Y aunque usted no puede verlo del todo con esta visualización, un trie es un árbol estructurado, como un árbol de la familia con un antepasado en la parte superior y un montón de nietos y bisnietos como las hojas en la parte inferior. Pero cada nodo en un trie es una matriz. Y está en una matriz - y deje de simplificar demasiado por un momento - es una matriz, en este caso, de tamaño 26, en donde cada nodo de nuevo es una matriz de tamaño 26, donde el elemento de orden cero en ese matriz representa A, y el último elemento en cada uno de tales matriz representa Z. Así que propongo, entonces, que estos datos estructura, conocida como un trie, puede ser utilizado también para almacenar palabras. Nos vimos hace un momento cómo podríamos almacenar palabras, o en este caso, los nombres y nosotros Vimos anteriormente cómo podemos almacenar números, pero si nos centramos en los nombres o cadenas aquí, darse cuenta de lo interesante. Afirmo que el nombre es Maxwell en el interior de esta estructura de datos. ¿Dónde ve usted Maxwell? ESTUDIANTE: [inaudible]. ALTAVOZ 1: A la izquierda. Así que lo que es interesante con estos datos estructura es más bien que tienda la cadena M-A-X-W-E-L-L barra invertida cero, todo contigua, lo que en su lugar lo hace está siguiendo. Si este es un trie como estructura de datos, cada uno de cuyos nodos es de nuevo una matriz, y desea almacenar Maxwell, primero índice y así nodo de la raíz, por lo que a hablar, el primer nodo, en la posición M, la derecha, por lo que más o menos en el centro. Y luego, desde allí, se sigue un Puntero a una nodos secundarios, por así decirlo. Así, en el sentido árbol genealógico, sigue hacia abajo. Y que te llevan a otro nodo A la izquierda, que es sólo otro array. Y luego, si desea almacenar Maxwell, usted encuentra el puntero que representa A, que es este de aquí. Después de ir al siguiente nodo. Y note - es por eso la imagen del un poco engañoso - este nodo mirar minúsculo estupendo. Pero a la derecha de ésta es Y y Z. Es que el autor ha truncado la foto, así que en realidad ver las cosas. De lo contrario, la imagen sería enormemente amplia. Así que ahora usted índice en la ubicación X, a continuación, W, A continuación, E, entonces L, entonces L. Entonces cuál es esta curiosidad? Bueno, si estamos utilizando este tipo de nuevo asumir la forma de almacenar una cadena en un estructura de datos, usted todavía tiene que esencialmente marcar en los datos estructura que una palabra termina aquí. En otras palabras, cada uno de estos nodos de alguna manera tiene que recordar que nosotros de hecho seguido todos estos punteros y están dejando un poco miga de pan en la parte inferior de esta aquí estructura para indicar M-A-X-W-E-L-L es de hecho, en esta estructura de datos. Así que podríamos hacerlo de la siguiente. Cada uno de los nodos de la imagen que acabamos de sierra tiene una, una matriz de tamaño 27. Y es ahora de 27 años, ya que en p establecido seis, haremos realidad le damos un apóstrofe, para que podamos tener nombres como O'Reilly y otros con apóstrofes. Pero la misma idea. Cada uno de esos elementos en el array apunta a una estructura nodo, por lo que sólo un nodo. Así que esto es muy reminiscente de nuestra lista enlazada. Y luego tengo un booleano, que lo voy a hacer palabra llamada, que sólo va a ser cierto si una palabra termina en este nodo en el árbol. Se representa efectivamente la pequeña triángulo que vimos hace un momento. Así que si una palabra termina en ese nodo en el árbol, ese campo palabra será verdad, que es conceptualmente marcando o estamos dibujando este triángulo, sí hay es una palabra aquí. Así que este es un trie. Y ahora la pregunta es, ¿qué es su tiempo de ejecución? ¿Es grande O de n? ¿Es algo más? Bueno, si usted tiene n los nombres de estos datos estructura, Maxwell es sólo uno de ellos, lo que es el tiempo de ejecución de la inserción o la búsqueda de Maxwell? ¿Qué es el tiempo de ejecución de la inserción de Maxwell? Si hay n otros nombres ya en la mesa? ¿Sí? ESTUDIANTE: [inaudible]. ALTAVOZ 1: Sí, es la longitud del nombre, ¿verdad? Así M-a-x-w-e-l-l así que se siente como esto algoritmo es O grande de siete. Ahora, por supuesto, el nombre variará en longitud. Tal vez es un nombre corto. Tal vez sea un nombre más largo. Pero lo que es clave aquí es que es un número constante. Y tal vez en realidad no es constante, Pero Dios, si de manera realista, en un diccionario, es probable que haya algún límite en el número de cartas en un nombre de la persona en un país determinado. Y por lo que podemos asumir que valor es una constante. No sé lo que es. Es probable que sea más grande que creemos que es. Porque siempre hay algún rincón Caso con un nombre largo loco. Así que vamos a llamarlo k, pero sigue siendo un constante, presumiblemente, debido a que cada nombre en el mundo, al menos en un país en particular, es que la longitud o más corto, por lo que es constante. Pero cuando hemos dicho algo es grande O de un valor constante, lo que hay que realmente equivalente a? Eso es realmente la misma cosa diciendo que la constante de tiempo. Ahora estamos como hacer trampa, ¿no? Estamos como el aprovechamiento de alguna teoría aquí para decir que así, el orden de k es Para realmente sólo de uno, y es hora de constante. Pero lo que realmente es. Porque la idea clave aquí es que si tenemos n nombres ya en este estructura de datos, y la insertamos Maxwell, es la cantidad de tiempo que nos lleva a inserte Maxwell en absoluto afectada por la cantidad de otras personas se encuentran en la estructura de datos? No parece ser. Si tuviera un billón más elementos a esta trie, y luego insertar Maxwell, es que en absoluto afectada? No. Y eso es a diferencia de cualquiera de los datos de días estructuras que hemos visto hasta ahora, donde el tiempo de funcionamiento de su algoritmo es completamente independiente de la cantidad material es o no es ya en esa estructura de datos. Y así, con esto le produce ahora es una oportunidad para p conjunto de seis, que se nuevo implicar la implementación de su propia corrector ortográfico, la lectura en 150.000 Es decir, la mejor manera de almacenar esa no es necesariamente evidente. Y aunque he aspirado a encontrar el santo grial, yo no afirman que un trie es. De hecho, una tabla hash puede muy bien llegar a ser mucho más eficiente. Pero esos son sólo - eso es sólo una de las decisiones de diseño usted tendrá que hacer. Pero en el cierre vamos a echar 50 o así segundos para echar un vistazo a lo que las mentiras con antelación la próxima semana y más allá de la transición que de esta línea de comandos mundo si los programas en C para cosas web basado y lenguajes como PHP y JavaScript y la propia Internet, protocolos como HTTP, que tienes se da por sentado por años ahora, y escrito la mayoría de cada día, tal vez, o visto. Y vamos a empezar a pelar la capas de lo que es el Internet. ¿Y cuál es el código que subyace en las herramientas actuales. Así que 50 segundos de este teaser aquí. Te doy Guerreros de la red. [REPRODUCCIÓN DE VÍDEO] -Él vino con un mensaje. Con un protocolo propio. Él vino a un mundo de los servidores de seguridad crueles, routers indiferentes y peligros lejos peor que la muerte. Es rápido. Es fuerte. Es TCPIP. Y tiene su dirección. Warriors of the Net. [VIDEO PLAYBACK FIN] ALTAVOZ 1: Eso es cómo el Internet trabajará a partir de la próxima semana.