[REPRODUCCIÓN DE MÚSICA] ANDI Peng: Bienvenidos a la semana 6 de la sección. Nos desviamos de nuestro estándar tiempo de la sección del martes por la tarde a esta hermosa mañana de domingo. Gracias por todo el mundo que me acompañan hoy, pero en serio, una ronda de aplausos. Esa es una muy grande esfuerzo. Casi ni siquiera hago en el tiempo, pero estaba bien. Así que sé que todos ustedes simplemente han llegado a la prueba. En primer lugar, la bienvenida a la otra cara de eso. En segundo lugar, vamos a hablar sobre ello. Hablaremos de la prueba. Hablaremos de cómo que estás haciendo en la clase. Estarás bien. Tengo sus cuestionarios para que al final de aquí, así que si ustedes quieren tener una mirada en ella, totalmente bien. Así que rápidamente antes de comenzar, el orden del día de hoy es el siguiente. Como se puede ver, estamos despido básicamente rápida a través de un montón de estructuras de datos muy, muy, muy rápido. Así que, como tal, no será hoy muy interactiva. Sólo será mi clase de gritos cosas que usted, y si te confundo, si voy demasiado rápido, que me haga saber. No son más que diversos datos estructuras, y como parte del conjunto de procesadores para este próxima semana, podrás se le pregunte para implementar uno de ellos, quizás dos de ellos-- dos de ellas en su conjunto de procesadores. OK, así que sólo voy a comenzar con algunos anuncios. Vamos a repasar pilas y colas más en profundidad que lo que hicimos antes de la prueba. Vamos a repasar unidos lista de nuevo, una vez más, más en profundidad de lo que que teníamos antes de la prueba. Y luego hablaremos de hachís tablas, árboles y tries, que son todos bastante necesario para su conjunto de procesadores. Y luego vamos a repasar algunos consejos útiles para pset5. OK, así que prueba 0. El promedio fue de un 58%. Era muy bajo, y así ustedes todo hizo muy, muy bien, de acuerdo con ese. Más o menos, regla de oro es que si usted es dentro de una desviación estándar de la media sobre todo porque estamos en un menor sección cómodo, estás totalmente bien. Usted está en pista. La vida es buena. Sé que es miedo pensar que Tengo como un 40% en esta prueba. Voy a dejar esta clase. Te lo prometo, no estás va a fallar la clase. Usted es totalmente bien. Para aquellos de ustedes que lo superó la media, impresionante, impresionante, como, en serio bien hecho. Los tengo conmigo. No dude en venir conseguirlos al final de la sección. Déjeme saber si usted tiene cualquiera cuestiones, preguntas con ellas. Si sumamos su calificación mal, háganoslo saber. OK, así pset5, esto es una realidad semana raro para Yale en el sentido que nuestro conjunto de procesadores se debe Miércoles al mediodía incluidos a finales del día, por lo que es en realidad debido teóricamente Martes al mediodía. Probablemente nadie terminó Martes al mediodía. Eso es totalmente bien. Vamos a tener horas de oficina esta noche, así como la noche del lunes. Y todas las secciones de esta semana lo hará en realidad convertirse en talleres, así que siéntete libre para hacer estallar en cualquier sección que desee, y van a estar especie de mini-pset talleres para ayuda en eso. Así que, como tal, esta es la única sección de donde estamos material didáctico. Todas las otras secciones se centrarán exclusivamente en la ayuda para el conjunto de procesadores. ¿Sí? AUDIENCIA: ¿Dónde están las horas de oficina? ANDI Peng: Las horas de oficina esta noche-- oh, buena pregunta. Creo que las horas de oficina esta noche están en el trullo o al Commons. Si marca en línea CS50 y usted va a las horas de oficina, debe haber un horario que dónde todos ellos son dice. Yo sé bien esta noche o mañana es trullo, y creo que podemos tener bienes comunes de la otra noche. No estoy seguro. Buena pregunta. Compruebe en CS50. Cool, preguntas sobre el calendario para la próxima como tres días? Te prometo que ustedes como David dijo, se trata de la parte superior de la colina. Ustedes son casi allí. A sólo tres días más. Llegar allí, y luego todos nos vendremos abajo. Vamos a tener un buen descanso CS-libre. Bienvenido de nuevo. Nos sumergimos en la web programación y desarrollo, cosas que son muy divertido compararon a algunos de los otros conjuntos de procesadores. Y va a ser frío y vamos a tener un montón de diversión. Tendremos más dulces. Lo siento por los dulces. Olvidé dulces. Era una mañana áspera. Así que chicos está casi allí, y estoy muy orgulloso de ustedes. OK, así que apila. Quién amó a la pregunta acerca de Jack y su ropa en el concurso? ¿Nadie? OK eso está bien. Así que, esencialmente como puedas foto de Jack, este chico aquí, le encanta tomar la ropa de la parte superior de la pila, y se pone de nuevo en la pila después de que ha hecho. Así de esta manera, nunca parece estar cada vez a la parte inferior de la apilar en su ropa. Por lo tanto este tipo de describe la estructura de datos básica de cómo se implementa una pila. Esencialmente, pensar en un apilar como cualquier pila de objetos donde poner las cosas en la parte superior, y luego los hace estallar hacia fuera de la parte superior. Así LIFO es el acrónimo que nos gusta al servicio- Last In, First Out. Y así, la última en la parte superior de la pila es el primero que sale. Y así los dos términos nos gusta asociar con eso que se llama empuje y pop. Cuando empujas algo sobre la apilar, y usted hace estallar una copia de seguridad. Así que supongo que esto es una especie de concepto abstracto para aquellos de ustedes que quieren ver como un aplicación real de este en el mundo real. ¿Cuántos de ustedes han escrito un ensayo tal vez como una hora antes de que se debió, y has borrado accidentalmente un enorme parte de ella, como por accidente? Y entonces lo mando hacer que utilizamos para poner de nuevo? Control-Z, sí? Control-Z, por lo que la cantidad de veces que Control-Z ha salvado la vida, ha salvado el culo, cada vez que eso es implementado a través de una pila. Esencialmente toda la información que está en el documento de Word, que es empujado y se metió en la voluntad. Y así, en esencia cada vez que borrar nada, usted hace estallar una copia de seguridad. Y entonces, si usted lo necesita de nuevo, que empujarla, que es lo que hace de Control-C. Y la función mundo tan real de la estructura de datos de lo simple puede ayudarle con su vida cotidiana. Así que un struct es la forma en que que realmente creamos una pila. Escribimos definir estructura, y luego lo llamamos la pila en la parte inferior. Y dentro de la pila, tenemos dos parámetros que esencialmente se puede manipular, así que tenemos carbón capacidad cuerdas estrella. Todo lo que se está haciendo es la creación de una matriz que podemos almacenar lo que quieras el cual podemos determinar su capacidad. La capacidad es la cantidad máxima de artículos que se pueden poner en esta matriz. int size es el contador que mantiene un registro de cuántos elementos son actualmente en la pila. Así entonces podemos perder de vista, A, tanto lo grande la pila real es, y, B, cuánto de esa pila llenamos porque no queremos a desbordarse sobre lo que nuestra capacidad es. Así, por ejemplo, esta hermosa pregunta era en su cuestionario. En esencia, ¿cómo empujamos en la parte superior de una pila. Bastante simple. Si nos fijamos en ella, vamos a caminar a través de este. Si [inaudible] size-- recuerde, siempre que quiere acceder a cualquier parámetro dentro de una estructura, lo hace el nombre de la struct.parameter. En este caso, s es el nombre de nuestro stack. Queremos acceder el tamaño de la misma, por lo que hacemos s.size. Así que, mientras el tamaño no es igual a la capacidad o tan largo ya que es menos de la capacidad, ya sea que trabajar aquí. ¿Quieres acceder al interior de la pila, por lo s.strings, y usted va a poner ese nuevo número que desea insertar en allí. Digamos que vamos a querer inserte int n en la pila, podríamos hacer s.strings, soportes, s.size es igual a n. Debido a que el tamaño es donde nos Actualmente se encuentran en la pila si vamos a empujar en, simplemente accedemos donde el tamaño es, la plenitud actual de la pila, y empujamos la int n en la misma. Y luego queremos asegurarnos de que también estamos incrementando el tamaño de la n, para que podamos hacer un seguimiento de que hemos añade algo extra a la pila. Ahora tenemos un tamaño mayor. ¿Esto aquí tiene sentido todo el mundo, ¿cómo lógicamente funciona? Era una especie de rápido. AUDIENCIA: ¿Puede ir más los s.stringss.strings [s.size] de nuevo? ANDI Peng: Claro, ¿y qué hace s.size Actualmente darnos? AUDIENCIA: Es el tamaño actual. ANDI Peng: Exactamente, por lo que el índice actual que nuestro tamaño es a, y por lo que queremos poner el nuevo número entero que queremos insertar en s.size. ¿Tiene sentido? Debido s.strings, todo lo que es es el nombre de la matriz. Todo lo que es es el acceso a la matriz dentro de nuestra estructura, y por lo que si queremos colocar n en ese índice, sólo podemos acceder a él utilizando soportes s.size. Guay. Muy bien, pop, me Pseudocódigo fuera para ustedes, sino concepto similar. ¿Tiene sentido? Si el tamaño es mayor que cero, entonces usted sabe que usted quiere tomar algo porque si el tamaño no es mayor que cero, entonces usted no tienen nada en la pila. Por lo que sólo desea ejecutar este código, sólo puede pop si hay algo de pop. Así que si el tamaño es mayor de 0, tenemos menos el tamaño. Nos disminuir el tamaño y luego regresamos lo que hay dentro de ella porque haciendo estallar, queremos Acceso todo lo que se almacena en el índice de la parte superior de la pila. Todo tiene sentido? Si te hice chicos escribir esto, ¿Quieres que chicos capaces de escribirlo? OK, ustedes pueden jugar un rato con él. No se preocupe si usted no lo entienden. No tenemos tiempo para codificar hacia fuera hoy porque hemos tiene un montón de estas estructuras que pasar, pero esencialmente pseudocódigo, muy, muy similar a empujar. Sólo tienes que seguir a lo largo de la lógica. Asegúrese de que está accediendo todo el características de su estructura correctamente. ¿Sí? AUDIENCIA: Will estas diapositivas y todo esto sea hoy-ish? ANDI Peng: Siempre, sí. Voy a tratar de poner esto como una hora después. Voy por correo electrónico David, David intentará lo puso como una hora después de esto. OK, así que luego nos adentramos en este otro estructura de datos preciosa llama una cola. Como ustedes pueden ver aquí, un cola, para los británicos entre nosotros, todo lo que es es una línea. Así que al contrario de lo crees que una pila es, una cola es exactamente lo lógicamente usted piensa que es. Se lleva a cabo por las reglas de FIFO, que es First In, First Out. Si usted es el primero una en la línea, usted es el primero que que sale de la línea. Así que lo que nos gusta llamar a este se desencolado y encolar. Si queremos añadir algo a nuestra cola, nos enqueue. Si queremos quitar de la cola, o tomar algo lejos, nos dequeue. Así mismo sentido que estamos tipo de la creación de elementos de tamaño fijo que puede almacenar cierta cosas, sino que también puede cambiar el lugar donde estamos colocando parámetros dentro de ellos sobre la base de qué tipo de funcionalidad que queremos. Así pilas, queríamos la última uno, N para ser el primero en salir. Cola es que queremos lo primero en ser el primero que salió. Así que la de tipo struct definir, como se puede ver, que es un poco diferente de lo que era la pila porque no sólo tenemos que seguir la pista de donde el tamaño es actualmente, también queremos hacer un seguimiento de la cabeza así como en los que actualmente somos. Así que creo que es más fácil si me baso esto. Así que imaginemos que tenemos una cola, así que digamos que la cabeza está aquí. El jefe de la línea, vamos a Basta con decir que es en la actualidad hay, y queremos insertar algo en la cola. Voy a llamar a tamaño esencialmente es lo mismo que la cola, Al final de donde quiera que su cola es. Digamos que el tamaño es justo aquí. Entonces, ¿cómo puede uno factiblemente insertar algo en una cola? ¿Qué índice queremos colocar donde queremos insertar en. Si este es el comienzo de su cola y este es el final de la misma o el tamaño de la misma, ¿dónde estamos que desee agregar el siguiente objeto? AUDIENCIA: [inaudible] ANDI Peng: Exactamente, desea agregar que dependiendo has escrito. O esto es en blanco o que está en blanco. Así que usted quiere agregar que probablemente aquí porque si el tamaño es-- si éstos están llenos, desea añadir aquí mismo, ¿no? Y eso es, aunque muy, muy simple, no es siempre correcta debido a que la principal diferencia entre una cola y una pila es que la cola puede en realidad ser manipulado de modo que los cambios de la cabeza dependiendo de donde desea el comienzo de su señal para comenzar. Y como resultado, su cola También se va a cambiar. Y así que échale un vistazo a este código en este momento. Como también se les pidió que ustedes escribir en el concurso, de puesta en cola. Tal vez vamos a hablar a través de qué la respuesta era lo que era. No podía encajar bastante esta línea en uno, pero esencialmente este pedazo de código debe estar en una sola línea. Pasa como 30 segundos. Echa un vistazo, y ver por qué esta es la manera que lo es. Muy, estructura muy similar, muy, muy estructura similar a la anterior apilar excepto quizá una línea de código. Y que una línea de código determina la funcionalidad. Y lo que realmente diferencia a una cola de una pila. ¿Alguien quiere tomar una puñalada al explicar por qué tienes tengo esta cosa complicada en esta lista? Nos vemos el regreso de nuestro maravillosa módulo amigo. Como ustedes pronto vendrá a reconocer en la programación, casi siempre usted necesita algo para envolver alrededor de cualquier cosa, módulo va a ser la forma de hacerlo. Así que sabiendo eso, no quería que nadie para tratar de explicar esa línea de código? Sí, todas las respuestas son aceptada y bienvenida. AUDIENCIA: ¿Usted está hablando conmigo? ANDI Peng: Sí. AUDIENCIA: ¡Oh, no lo siento. ANDI Peng: OK, así que vamos a caminar a través de este código. Así que cuando usted está tratando de agregar algo en una cola, en la encantadora caso de que el jefe sucede para ser justo aquí, es muy fácil para nosotros que sólo tiene que ir hasta el final insertar algo, ¿no? Pero el punto central de una cola es que el jefe de hecho puede dinámicamente cambiar dependiendo de donde estamos quiere que el comienzo de nuestra q sea, y como tal, la cola También se va a cambiar. Y así, imagino que esto no era la cola, sino que más bien se trataba de la cola. Digamos que la cabeza está aquí. Digamos que nuestra cola se veía así. Si quisiéramos cambiar, donde el comienzo de la línea es, digamos que cambiamos la cabeza de esta manera y tallas Aquí. Ahora queremos añadir algo a esta cola, pero como ustedes pueden ver, que no es tan sencillo como simplemente añadir lo es después de que el tamaño porque entonces nos quedamos sin límites de nuestra gama actual. Cuando queremos añadir realmente está aquí. Esa es la belleza de una cola es que a nosotros, visualmente parece que la línea es la siguiente, pero cuando se almacena en una estructura de datos, dan como como un ciclo. En cierto modo se envuelve alrededor a la parte delantera de la misma manera que una línea también puede envolver todo dependiendo de donde quiera que querer principio de la línea para ser. Y así, si tomamos una mira aquí abajo, vamos a decimos que queríamos crear un función de llamada en cola. Queríamos añadir int n en que q. Si q.size q-- Llamaremos a que nuestros datos structure-- si nuestro queue.size no igual a la capacidad o si que es menos de la capacidad, q.strings es la matriz dentro de nuestro q. Vamos a establecer que igual a q.heads, que está justo aquí, además q.size por el módulo de capacidad, que nos envuelva vuelta por aquí. Así, en este ejemplo, el índice de la cabeza es 1, ¿verdad? El índice de tamaño es 0, 1, 2, 3, 4. Así que podemos hacer 1 más 4 de módulo por nuestra capacidad, que es 5. ¿Qué nos dan? ¿Cuál es el índice que que sale de esto? AUDIENCIA: 0. ANDI Peng: 0, lo que pasa a ser aquí, y así queremos ser capaces para insertar en aquí. Y así esta ecuación aquí especie de tan sólo funciona con cualquier número dependiendo de donde su cabeza y su tamaño son. Si sabes lo que los son las cosas, ya sabes exactamente donde desea insertar todo lo que sea después de su cola. ¿Eso tiene sentido para todo el mundo? Sé la clase de un cerebro sumario sobre todo porque este llegó en las postrimerías de su concurso. Pero esperemos que todo el mundo Ahora puede entender por qué esta solución o esta función es la forma en que lo es. Cualquier persona un poco confuso al respecto? OK. Y ahora, si usted querido quitar de la cola, esta es donde nuestra cabeza sería el cambio porque si tuviéramos que quitar de la cola, no tomamos fuera de la final de la q. Queremos sacar la cabeza, ¿verdad? Así que, como resultado, la cabeza va a cambiar, y es por eso que cuando encolar, tienes que mantener un registro de donde su cabeza y su tamaño han de ser capaz de insertar en la posición correcta. Y así cuando dequeue, También Pseudocódigo a cabo. Siéntase libre si quiere para intentar codificar esta fuera. Usted desea mover la cabeza, ¿verdad? Si quería quitar de la cola, me movería la cabeza otra vez. Esta sería la cabeza. Y nuestro tamaño actual haría restar porque ya no tener cuatro elementos de la matriz. Sólo tenemos tres, y luego queremos para devolver todo lo que se almacena en el interior de la cabeza porque queremos aprovechar esta valor a cabo de manera muy similar a la pila. Sólo usted está tomando desde un lugar diferente, y tienes que volver a asignar el puntero a diferente lugar como un resultado. Lógicamente, todo el mundo sigue? Excelente. OK, así que vamos a hablar un poco más en profundidad sobre listas enlazadas porque van a estar muy, muy valiosa para que en el transcurso de esta semana de conjuntos de procesadores. Listas enlazadas, como ustedes recuerdo, todo lo que son son nodos que son nodos de cierta valores tanto de un valor y un puntero que están unidos entre sí por los punteros. Y por lo que la estructura de cómo creamos un nodo aquí es que tener int n, que es lo el valor en una tienda o cadena de n o lo que quieras llamarlo, la estrella carbón n. Struct estrella nodo, que es el puntero que usted desea tener en cada nodo, usted va a tener que punta puntero hacia la siguiente. Vas a tener la cabeza de una lista enlazada que es va a señalar el resto de los valores así sucesivamente y así sucesivamente hasta llegar finalmente al final. Y este último nodo es sólo ir a no tener un puntero. Se va a apuntar a nulo, y es entonces cuando sabes que has llegado a la final de la lista enlazada es cuando su última puntero no apunta a nada. Así que vamos a ir un poco más en de profundidad con respecto a cómo se haría posiblemente buscar una lista enlazada. Recuerda lo que son algunos de los inconvenientes de las listas enlazadas versos una serie en relación con las búsquedas. Una matriz puede búsqueda binaria, pero por qué no se puede hacer eso en una lista enlazada? AUDIENCIA: Porque están todos conectados, pero no sé muy bien dónde [INAUDIBLE]. ANDI Peng: Sí, exactamente a fin de recordar que la brillantez de un array fue el hecho de que teníamos memoria de acceso aleatorio, donde si quería el valor del índice seis, yo podría decir que el índice de seis, dame ese valor. Y eso es porque las matrices se clasifican en un espacio contiguo de memoria en un solo lugar, mientras que tipo de listas enlazadas se intercalan aleatoriamente por todas partes, y la única manera que usted puede encontrar uno es a través de un puntero que te dice la dirección del lugar en que el próximo nodo es. Y así, como resultado, la única manera de para buscar a través de una lista enlazada es la búsqueda lineal. Porque yo no sé exactamente dónde el valor 12 en la lista enlazada es, Tengo que atravesar la totalidad de esa lista enlazada se por uno desde la cabeza hasta el primer nodo, al segundo nodo, a la tercera nodo, todo el camino hasta que finalmente llegue a donde ese nodo que estoy buscando es. Y así, en este sentido, la búsqueda en una lista enlazada es siempre n. Siempre es n. Siempre en el tiempo lineal. Y por lo que el código en el que implementamos esto, y esto es un poco nuevo para ustedes desde que chicos realmente no han hablado ni nunca punteros visto en la forma de buscar a través de punteros, así que vamos a caminar a través de esta muy, muy lentamente. Así que la búsqueda bool, derecha, imaginemos que queremos para crear una función llamada búsqueda que devuelve true si usted encuentra un valor dentro de la vinculada lista, y devuelve false en caso contrario. Lista de estrellas de nodo es Actualmente sólo el puntero al primer elemento de la lista enlazada. int n es el valor que usted es buscar en esa lista. Así indicador de la estrella nodo es igual a la lista. Eso significa que estamos configurando y la creación de un puntero al primer nodo dentro de la lista. Todo el mundo conmigo? Así que si nos vamos a ir Vuelve aquí, tendría inicializado un puntero que apunta a la cabeza de lo que la lista es. Y luego una vez que llegue aquí, mientras que el puntero no es igual a null, por lo que es el bucle en el que estamos va a ser posteriormente atravesar el resto de nuestra lista porque lo sucede cuando el puntero equivale a nula? Sabemos que tener-- AUDIENCIA: [inaudible] ANDI Peng: Exactamente, así que sabemos que hemos llegado al final de la lista, ¿no? Si vuelves aquí, cada nodo debe estar apuntando a otro nodo y así sucesivamente y así sucesivamente hasta llegar, finalmente, la cola de la lista enlazada, que tiene un puntero que acaba no señala en ningún otro que no. Así que, básicamente, saber que tu lista todavía está allí arriba hasta que el puntero no es igual a nula porque una vez que es igual a null, usted sabe que no hay más cosas. Así que ese es el bucle en el que estamos va a tener la búsqueda real. Y si los pointer-- hacen que vea ese tipo de función saeta en ella? Así que si puntero apunta a n, si el puntero en n es igual es igual a n, lo que significa que si el puntero que eres buscar en el extremo de cada nodo es en realidad igual al valor que estás buscando, entonces desea volver realidad. Así que, básicamente, si usted está en un nodo que tiene el valor que usted está buscando, sabes que has estado capaz de buscar con éxito. De lo contrario, desea establecer el puntero al siguiente nodo. Eso es lo que esa línea aquí está haciendo. Pointer es igual puntero siguiente. Todo el mundo vea cómo eso está trabajando? Y básicamente vas a solo recorrer la totalidad de la lista, restablecer el puntero cada vez hasta que finalmente golpeó el final de la lista. Y usted sabe que no hay más nodos para buscar a través de, y entonces usted puede devolver false porque sabes que, oh, bueno, si yo he sido capaz de buscar a través de la totalidad de la lista. Si en este ejemplo, si quería para buscar el valor de 10, y me pongo a la cabeza, y Yo busco hasta el fondo, y, finalmente, llegué a esto, que un puntero que apunta a null, Sé que, mierda, supongo que 10 no está en esta lista porque no pude encontrarlo. Y estoy al final de la lista. Y en este caso usted sabe Voy a devolver false. Vamos que remojo en un poco. Esta será bastante importante para su conjunto de procesadores. La lógica de que es muy simple, tal vez sintácticamente simplemente implementarlo. ¿Quieren hacer Asegúrese de entender. Guay. OK, así que ¿cómo nos habría la inserción de nodos, la derecha, en una lista porque recuerde ¿cuáles son los qué de los beneficios de tener una lista enlazada frente una matriz en términos de almacenamiento? AUDIENCIA: Es dinámico, así que es más fácil a-- ANDI Peng: Exactamente, por lo que es dinámico, que significa que puede expandirse y contraerse dependiendo de las necesidades del usuario. Y así, en este sentido, no necesitamos a perder la memoria innecesaria porque si yo no sé cuántos valores que quiero a la tienda, que no tiene sentido para mí para crear una matriz debido si quiero almacenar 10 valores y puedo crear una matriz de 1000, que es una gran cantidad de memoria perdida, asignado. Es por eso que queremos utilizar una ligado lista para ser capaz de dinámicamente cambiar o reducir nuestro tamaño. Y por lo que hace la inserción un poco más complicado. Ya que no podemos acceder aleatoriamente elementos la forma en que nos de una matriz. Si quiero insertar un elemento en el séptimo índice, Yo sólo puedo insertarlo en el séptimo índice. En una lista enlazada, no lo hace bastante trabajar con la misma facilidad, y así si queríamos insertar el uno aquí en la lista enlazada, visualmente, es muy fácil de ver. Sólo queremos insertar allí mismo, la derecha en el principio de la lista, justo después de la cabeza. Pero la forma en la que tenemos que reasignar los punteros es un poco complicado o, lógicamente, tiene sentido, pero usted quiere asegurarse de que usted lo tiene completamente abajo porque la última cosa que quiero es volver a asignar un puntero al camino que estamos haciendo aquí. Si eliminar la referencia al puntero de la cabeza a 1, luego, de repente resto de su lista enlazada se pierde porque usted tiene en realidad no creado un nada temporal. Eso se señaló a la 2. Si reasigna el puntero, entonces el resto de su lista está totalmente perdido. Así que quieres ser muy, muy cuidadoso aquí para asignar la primera puntero de lo que quiere insertar en cualquier lugar que quiere, y entonces puede eliminar la referencia al resto de su lista. Así que esto se aplica a cualquier lugar usted está tratando de insertar en. Si desea insertar en el cabeza, si quieres contestar aquí, si desea insertar en Al final, bueno, al final me supongo que lo haría solo tener ningún puntero, pero querrá asegurarse de que usted no lo hace perderá el resto de la lista. Uno siempre quiere asegurarse el nuevo nodo apunte hacia lo que quiere insertar en, y entonces usted puede añadir el encadenamiento. Todo el mundo claro? Esto va a ser uno de los problemas reales. Uno de los problemas de la mayoría de las usted va a tener en su conjunto de procesadores es que usted va a tratar de crear una lista enlazada y las cosas de inserción pero entonces sólo perderá el resto de su lista enlazada. Y tú vas a ser como, no sé por qué está sucediendo esto? Y es un dolor que pasar por y buscar todos sus punteros. Y te garantizo en este conjunto de procesadores, escribir y dibujar estos nodos fuera va a ser muy, muy servicial. Así que usted puede mantener por completo la pista de donde todos sus punteros son, lo que va mal, donde todos los nodos son, lo que tiene que hacer para acceder o insertar o eliminar o cualquiera de ellos. Todo el mundo bien con eso? Guay. Así que si queríamos mirar el código? Oh, no sé si puede ver el-- OK, así en la parte superior de todo lo que es es una función inserto llamado donde queremos insertar int n en la lista enlazada. Vamos a caminar a través de esto. Es una gran cantidad de código, una gran cantidad de nueva sintaxis. Vamos a estar bien. Así que en la parte superior, siempre que sea queremos crear nada ¿qué es lo que tenemos que hacer, especialmente si usted quiero que no se almacena en la pila pero en el montón? Vamos a un malloc, ¿verdad? Así que vamos a crear un puntero. Nodos, puntero, nuevos iguales malloc el tamaño de un nodo porque queremos que el nodo que se creará. Queremos que la cantidad de memoria que un nodo ocupa para ser asignado para el creación del nuevo nodo. Y luego vamos a comprobar para ver si los nuevos iguales es igual a cero. Recuerda lo que dijimos? Hagas lo que malloc, ¿qué debe hacer siempre? Usted debe comprobar siempre para ver si es o no es nulo. Por ejemplo, si su funcionamiento sistema estaba completamente lleno, si no tuviera más memoria en todo y tratas de malloc, volvería nulo para usted. Y por lo que si intenta utilizarlo cuando se estaba apuntando a null, no vas a poder para acceder a esa información. Y así, como tal, hemos querido hacer Asegúrese de que cada vez que estés mallocing, siempre estás comprobando si que la memoria que le ha asignado es nulo. Y si no lo es, entonces podemos mover con el resto de nuestro código. Así que vamos a inicializar el nuevo nodo. Vamos a hacer nueva n es igual a n. Y luego vamos a hacer set nuevo el puntero de nuevo en nulo porque en este momento no lo hacemos quiero nada para que apunte a. No tenemos ni idea de dónde que va a poner usted, y luego, si queremos insertarlo en la cabeza, entonces podemos reasignar el puntero a la cabeza. ¿Todo el mundo sigue la lógica de donde eso está pasando? Todo lo que estamos haciendo es crear una nueva nodo, estableciendo el puntero a null, y luego reasignar a la cabeza si sabemos que queremos para insertarlo en la cabeza. Y entonces la cabeza va a apuntar hacia ese nuevo nodo. Todo el mundo de acuerdo con eso? Así que es un proceso de dos pasos. Hay que asignar primero lo que está creando. Establecer ese puntero a la referencia, y luego puede especie de eliminar la referencia la primera puntero y apunte hacia el nuevo nodo. Dondequiera que usted desea insertarlo, que la lógica va a ser verdad. Es algo así como la asignación de variables temporales. Recuerde, usted tiene para asegurarse de que usted no perder de vista que si estás intercambiando. Usted quiere asegurarse de que usted tiene un variable temporal ese tipo de guarda la pista de donde esa cosa se almacena para que no pierda ningún valor en el curso de como jugar un poco con él. OK, así que el código estará aquí. Ustedes miren después de la sección. Será allí. Así que supongo que lo hace esta diferencia si queríamos para insertar en el medio o al final? ¿Alguien tiene una idea de lo que es la pseudocódigo como la referencia lógica que tomaríamos si queríamos para insertarlo en el medio? Así que si queríamos para insertarlo en el cabeza, todo lo que hacemos es crear un nuevo nodo. Hemos creado el puntero de ese nuevo nodo a cualquiera que sea la cabeza, y luego nos pusimos en la cabeza al nuevo nodo, ¿verdad? Si quisiéramos para insertarlo en el medio de la lista, lo que tendríamos que hacer? AUDIENCIA: Seguiría ser un proceso similar de como la asignación de puntero y luego asignar ese puntero, pero tendríamos que ubicar allí. ANDI Peng: Exactamente, así que exactamente el mismo proceso, excepto usted que localizar el lugar exacto que quiere que el nuevo puntero a entrar en, por lo que si quiero insertar en el medio de ligado películas-- OK, digamos que es nuestra lista enlazada. Si queremos insertar aquí mismo, vamos a crear un nuevo nodo. Vamos a malloc. Vamos a crear un nuevo nodo. Vamos a asignar el puntero de este nodo aquí. Pero el problema que difiere desde donde la cabeza es es que sabíamos exactamente donde la cabeza es. Fue justo en el primero, ¿no? Pero aquí tenemos que seguir la pista de donde estamos insertarlo en. Si estamos insertando nuestra nodo de aquí, tenemos para asegurarse de que la anterior a este nodo es el que reasigna el puntero. Entonces usted tiene que tipo de no perder de vista dos cosas. Si se mantiene la pista de donde esta nodo actualmente está insertando en. También hay que perder de vista donde el nodo anterior de que usted está buscando en También estaba allí. Todo el mundo bien con eso? OK. ¿Qué hay de la inserción en el final? Si yo quería añadir que aquí-- si quería añadir un nuevo nodo a la final de una lista, ¿Cómo podría yo ir haciendo eso? AUDIENCIA: Entonces, en la actualidad, la señaló la última en nulo. ANDI Peng: Sí. Exactamente, así que éste Actualmente se señaló a conocer, y así que supongo que, en este sentido, es muy fácil añadir al final de una lista. Todo lo que tienes que hacer es establecer que igual a null y luego auge. Allí mismo, muy fácil. Muy sencillo. Muy similar a la cabeza, pero lógicamente que querrá asegurarse de que los pasos tomar hacia hacer nada de esto, estás siguiendo. Es muy fácil, en el medio de su código, ponerse al día, oh, tengo tantos punteros. Yo no sé de dónde nada está señalando. Ni siquiera sé qué nodo estoy. ¿Que esta pasando? Relájese, calmarse, tomar una respiración profunda. Dibuja tu lista enlazada. Si dices, sé dónde exactamente Necesito insertar esto en y sé exactamente cómo reasignar mi punteros, mucho, mucho más fácil de imaginar fuera-- mucho, mucho más fácil no perderse en los errores de su código. Todo el mundo de acuerdo con eso? OK. Así que supongo que un concepto que no tenemos realmente hablado hasta ahora, y yo le creo, probablemente no se encontrará mucho yet-- es una especie de concept-- avanzada es que en realidad tenemos un dato estructura llamada una lista doblemente enlazada. Así como ustedes pueden ver, todo lo que estamos haciendo es crear un valor real, un extra puntero en cada uno de nuestros nodos que también apunta al nodo anterior. Así que no sólo tenemos nuestra nodos apuntan a la siguiente. También apuntan a la anterior. Voy a ignorar estos dos ahora. Entonces usted tiene una cadena que puede moverse en ambos sentidos, y entonces es un poco más fácil seguir lógicamente junto. Al igual que aquí, en lugar de no perder de vista, oh, tiene que saber que este nodo es el que tengo que volver a asignar, Yo sólo puedo ir aquí y simplemente tire de la anterior. Entonces sé exactamente dónde es decir, y entonces no tienen que atravesar la totalidad de la lista enlazada. Es un poco más fácil. Pero como tal, tiene una doble la cantidad de punteros, eso es el doble de la cantidad de memoria. Es un montón de consejos para no perder de vista. Es un poco más complejo, pero es un poco más fácil de usar función en lo que estamos tratando de lograr. Así que este tipo de datos estructura totalmente existe, y la estructura de es muy, muy simple, excepto todo lo que está teniendo es decir, en lugar de sólo un puntero al siguiente, usted también tiene un puntero al anterior. Esa es toda la diferencia fue. Todo el mundo bien con eso? Guay. Muy bien, así que ahora estoy pasar muy probablemente como 15 a 20 minutos o el mayor del resto del tiempo en la sección hablando sobre tablas hash. ¿Cuántos de ustedes han leído spec pset5? Muy bien, muy bien. Eso es más alto que el 50% de los normalmente. Esta bien. Así como ustedes verán, eres desafío en pset5 será la de aplicar un diccionario donde se carga más de 140.000 palabras que le demos y corrector ortográfico contra todo el texto. Le daremos al azar piezas de la literatura. Le daremos la Odisea. Le daremos la Ilíada. Le daremos Austin Powers. Y su reto será de deletrear verificación cada palabra en todo de esos diccionarios esencialmente con nuestro corrector ortográfico. Y así hay algunas partes de la creación de este conjunto de procesadores, primero que quieres ser capaz de cargar realidad todas las palabras en su diccionario, y luego quiero ser capaz de revisar la ortografía de todos ellos. Y así, como tal, usted va a requerir una estructura de datos que puede hacer esto rápido y eficientemente y de forma dinámica. Así que supongo que el más fácil manera de hacer esto, probablemente crear una matriz, ¿no? La forma más sencilla de almacenamiento que es puede crear una matriz de 140.000 palabras y acaba de colocar a todos allí y luego atravesar les binario de búsqueda o selecciones o no-- siento que eso clasificación. Puede ordenarlos y luego recorrer los por búsqueda binaria o de búsqueda simplemente lineal y justo finales de las palabras, pero que tiene una enorme cantidad de memoria, y no es muy eficiente. Así que vamos a empezar hablando de formas de hacer nuestro tiempo de funcionamiento más eficiente. Y nuestro objetivo es conseguir constante de tiempo donde es casi como arrays, donde usted tiene acceso instantáneo. Si quería buscar algo, Quiero ser capaz de simplemente, auge, saber exactamente, y tire de ella. Y así una estructura en la cual estaremos volviendo muy cerca para poder acceder a la constante tiempo, este santo grial en la programación de la constante tiempo se llama una tabla hash. Y así David mencionó anteriormente la [Inaudible] un poco en la conferencia, pero vamos a realmente buceo en profundidad esta semana en una pieza que está en relación con cómo una tabla hash funciona. Así que la forma en que un hash obras de mesa, por ejemplo, si quería guardar un montón de palabras, un manojo de palabras en el idioma Inglés, Yo teóricamente podría poner plátano, manzana, kiwi, mango, par, y melón todo en apenas una matriz. Todos ellos podrían encajar y ser encontrar. Sería una especie de dolor de buscar a través de y el acceso, pero la manera más fácil de hacer esto es que podemos crear en realidad una estructura llamada una tabla hash donde hash. Corremos todas nuestras claves a través una función hash, una ecuación, que todos ellos se convierte en una especie de un valor que podemos almacenar en esencialmente un conjunto de lista enlazada. Y aquí, si queríamos para almacenar las palabras en inglés, podríamos potencialmente simplemente, no hacer saber, convertir todas las primeras letras en una especie de un número. Y así, por ejemplo, si quería Un ser sinónimo de apple-- o con el índice de 0, y B a ser sinónimo de 1, podemos tener 26 entradas que solo puede almacenar todas las letras del alfabeto que vamos a empezar con. Y luego podemos tener manzana en el índice de 0. Podemos tener plátano en el índice de 1, el melón en el índice de 2, y así sucesivamente y así sucesivamente. Y así si quería buscar mi hash de mesa y el acceso de la manzana, Sé manzana comienza con una A, y sé exactamente que debe ser y el hash mesa en el índice 0, porque de la función asignada previamente. Así que no sé, somos un programa de usuario, donde se le acusa de no arbitrarily-- arbitrariamente, con intentar pensativo pensar en buenas ecuaciones ser capaz de propagarse a cabo todos sus valores de manera que puedan acceder fácilmente más adelante con como una ecuación que usted, usted mismo, saben. Así, en el sentido de que si quería ir a mango, lo sé, oh, comienza con m. Debe ser en el índice de 12. Yo no tengo que buscar a través de cualquier cosa. Sé exactly-- tan sólo pudiera ir a el índice de 12 y tire de eso. Todo el mundo clara sobre cómo un La función de tabla hash funciona? Es una especie de sólo un conjunto más complejo. Eso es todo lo que es. OK. Así que supongo que nos encontramos este tema de lo que pasa si tiene varias cosas que le dan el mismo índice? Así que decir que nuestra función, todo lo que hizo fue tomar esa primera carta y convertir eso en un 0 respectiva a través de 25 de índice. Eso es totalmente bien si es suficiente con uno de cada uno. Pero el segundo de empezar tener más, eres va a tener lo que se llama una colisión. Así que si trato de insertar enterrar en un hash tabla que ya tiene el plátano en él, lo que va a pasar cuando intenta insertar eso? Las cosas malas porque el plátano que ya existe en el índice que desea almacenarlo en. Berry tipo de es como, ah, ¿qué hago? No sé a dónde ir. ¿Cómo puedo solucionar esto? Y así ustedes harán clase de vemos que hacemos esta cosa difícil donde podemos tipo de realidad crear lista enlazada en nuestras matrices. Y así, la manera más fácil para pensar en esto, todas tabla hash es una variedad de listas enlazadas. Y así, en ese sentido, hay que este hermoso arreglo de apuntadores, y luego cada puntero en ese valor, en ese índice, en realidad puede apuntar a otras cosas. Y por lo que tiene todos estos separada cadenas que salen de una gran variedad. Y aquí, si yo querido insertar baya, Lo sé, OK, voy a la entrada a través de mi función hash. Voy a terminar con el índice de 1, y luego me voy a ser capaz de tener sólo un subconjunto más pequeño de este gigante diccionario de 140.000 palabras. Y entonces puedo simplemente mirar a través de 1/26 de eso. Y así entonces puedo basta con insertar baya ya sea antes o después de plátano ¿en este caso? Después, ¿verdad? Y por lo que vamos a querer insertar este nodo después de plátano, y así vas a insertar a la cola de la lista enlazada. Voy a volver a esta diapositiva anterior, así que ustedes pueden ver cómo función hash funciona. Así función hash es esta ecuación que se está ejecutando la clase de su entrada a través de conseguir lo Índice que desea asignar la directa hacia. Y así, en este ejemplo, todo lo que queríamos que hacer era tomar la primera letra, convertir eso en un índice, entonces nosotros puede almacenar que en nuestra función hash. Todo lo que estamos haciendo aquí es que estamos la conversión de la primera letra. Así KeyKey [0] es sólo la primera letra de cualquier cadena que estamos teniendo, estamos pasando. Estamos convertir eso a superior, y estamos restando por mayúsculas A, así que todo lo que está haciendo nos está dando una serie en el que podemos hash de nuestros valores en. Y luego vamos a volver picadillo TAMAÑO módulo. Sea muy, muy cuidadoso porque, en teoría, aquí su valor hash podría ser infinita. Sólo podría seguir y seguir y seguir. Podría ser algo realmente, muy grande valor, sino porque su tabla hash que usted ha creado solamente cuenta con 26 índices, usted quiere asegurarse de que su modulusing para que no run-- es lo mismo cosa como su queue-- para que no se quede fuera de la parte inferior de la función hash. Usted quiere envolverlo vuelta del mismo modo en [inaudible] cuando que tenía como un muy, gran carta, no quiero que eso basta con ejecutar fuera de la final. Lo mismo aquí, usted quiere asegurarse de no se ejecuta fuera de la final envolviendo alrededor de la parte superior de la tabla. Así que esto es sólo una muy función hash simple. Todo lo que hizo fue tomar la primera carta de cualquiera que sea nuestra entrada era y convertir eso en un índice que podríamos poner en nuestra tabla hash. Sí, y así como he dicho antes, la forma en que resolvemos colisiones en nuestro hash de mesas están teniendo, lo que llamamos, encadenamiento. Así que si usted intenta insertar múltiples palabras que comienzan con la misma cosa, usted va a tener un valor hash. Aguacates y manzana, si tienes ejecutar a través de nuestra función hash, se va a dar la mismo número, el número de 0. Y así, la forma en que resolver esto es que podemos realmente bueno de vincularlos sí a través de listas enlazadas. Y así, en este sentido, ustedes pueden ver tipo de cómo las estructuras de datos que hemos estado estableciendo previamente como una pasa ligado lista tipo de pueden unirse en una sola. Y entonces usted puede crear ahora estructuras de datos más eficientes que puede manejar grandes cantidades de datos, cambiar el tamaño de forma dinámica en función de sus necesidades. Todo el mundo claro? Todo el mundo la clase de clara en lo que sucede aquí? Si quería insert-- lo que es un fruta que empieza con, no sé, B, con excepción de la baya, plátano. AUDIENCIA: Blackberry. ANDI Peng: Blackberry, blackberry. ¿De dónde viene la zarzamora ir aquí? Bueno, en realidad no hemos clasificado esto todavía, pero teóricamente si queríamos tener este en orden alfabético, donde la mora se debe ir? AUDIENCIA: [inaudible] ANDI Peng: Exactamente, después de aquí, ¿no? Pero ya que es muy difícil reorder-- Supongo que depende de ustedes. Ustedes pueden totalmente implementar lo que quieras. La forma más eficiente de hacer esto quizá sería para ordenar tu vinculados una lista en orden alfabético, y así cuando estás insertando cosas, desea para asegurarse de insertarlos en orden alfabético para que luego, cuando esté tratando de buscar ellos, usted no tiene que atravesar todo. Usted sabe exactamente donde que es, y que es más fácil. Pero si que tipo de tener cosas entremezcladas al azar, usted todavía va a tener para atravesar todos modos. Y así, si quería simplemente inserte blackberry aquí y quería buscar que, sé, oh, blackberry debe comenzar con el índice de 1, así que saber instantáneamente sólo la búsqueda en 1. Y entonces puedo clase de recorrer la lista enlazada hasta que llegue a la mora, y entonces-- ¿sí? AUDIENCIA: Si usted está tratando de create-- Supongo que esta es una muy simple de hash función. Y si lo que queríamos hacer múltiples capas de que al igual que, OK, queremos separar en como todas las letras del alfabeto y luego otra vez a como otro conjunto de las letras del alfabeto en que, estamos poniendo como un hash tabla dentro de una tabla hash, o como una función dentro de una función? ¿O es que-- ANDI Peng: Así que su picadillo function-- su tabla hash puede ser tan grande como usted desea. Así que en este sentido, pensé fue muy fácil, muy simple para mí basan sólo una especie en letras de la primera palabra. Y así, sólo hay 26 opciones. Sólo puedo obtener 26 opciones de 0 a 25, ya que sólo puede comenzar de la A a la Z. Pero Si querías añadir, tal vez, una mayor complejidad o más rápido el tiempo de ejecución de su tabla hash, a pesar de todo puede hacer todo tipo de cosas. Usted puede hacer su propio ecuación que le da más distribución en su palabras, entonces cuando usted busca, que va a ser más rápido. Es totalmente de ustedes cómo desea implementar eso. Piense en ello como sólo cubos. Si yo quería tener 26 cubos, voy para ordenar las cosas en esos cubos. Pero yo voy a tener un montón de cosas en cada cubo, así que si usted quiere que sea más rápido y más eficiente, dame cien cubos. Pero entonces usted tiene que encontrar una manera de ordenar las cosas por lo que son en el cubo adecuado deben estar en. Pero luego, cuando en realidad que desee ver en el cubo, que es mucho más rápido porque hay menos cosas en cada cubo. Y así, sí, eso es en realidad el truco para ustedes en pset5 es que podrás el reto de crear sólo todo lo que es el más eficiente función que se pueda imaginar para ser capaz de almacenar y comprobar estos valores. Totalmente de ustedes sin embargo usted quiere hacerlo, pero eso es un muy buen punto. Que el tipo de lógica que quiero empezar a pensar en es, también, por qué no puedo hacer más cubos. Y entonces tengo que buscar menos cosas, y entonces tal vez tener una función de hash diferente. Sí, hay un montón de maneras de hacer esto pset, algunos son más rápidos que otros. Estoy totalmente de ir a ver lo fue rápido los chicos de más rápido voluntad ser capaz de obtener sus funciones para trabajar. OK, todos bien en tablas de encadenamiento y croquetas? En realidad es como un muy simple concepto, si se piensa en ello. Todo lo que es es lo que separa sus entradas son en cubos, clasificarlos, y luego buscar el listas que no está asociada con. Guay. Muy bien, ahora tenemos una especie diferente de estructura de datos que se llama un árbol. Sigamos y hablar de intentos que son claramente diferentes, pero en la misma categoría. Esencialmente, todo es un árbol en lugar de organizar los datos en la forma lineal que una tabla hash que does-- sabemos, tiene una parte superior y una parte inferior y que tipo de enlace fuera de it-- un árbol tiene un superior que se llama a la raíz, y entonces tiene hojas a su alrededor. Y así, todo lo que tienes aquí es sólo el nodo superior que apunta a otros nodos, que los puntos a más nodos, y así sucesivamente y así sucesivamente. Y por lo que sólo tiene ramas de división. Es sólo una forma diferente de organizar datos, y porque lo llamamos un árbol, ustedes solo-- es sólo modelada a buscar un árbol. Es por eso que lo llamamos árboles. Tabla hash se parece a una tabla. Un árbol sólo se parece a un árbol. Todo lo que es es una separada forma de organizar los nodos dependiendo de cuáles son sus necesidades. Así que hay una raíz y entonces usted tiene hojas. La forma en que podemos particular pensar en ello es un árbol binario, un árbol binario es sólo una tipo específico de un árbol donde cada nodo únicos puntos que, en el máximo, otros dos nodos. Y así que aquí tenéis distinta simetría en su árbol que hace que sea más fácil de tipo de mirada en qué valores son porque entonces tener siempre a la izquierda o la derecha. Nunca hay como una tercera izquierda desde la izquierda o cuarto desde la izquierda. Es sólo usted tiene una izquierda y una derecha y usted puede buscar cualquiera de los dos. Y ¿por qué es esto útil? La forma en que esto es útil es que si estás buscando para buscar a través de valores, ¿no? En lugar de implementar binario buscar en una matriz de error, si usted quiere ser capaz de insertar nodos y quitarle nodos a voluntad y también preservar la búsqueda capacidades de búsqueda binaria. Así de esta manera, estamos tipo de tricking-- recordar cuando nos dicho listas enlazadas no puede binario de búsqueda? Estamos especie de la creación de una estructura de datos que trucos que a trabajar. Y las listas porque vinculados son lineales, que sólo enlazan uno después del otro. Podemos tipo de tener diferente tipo de punteros que apuntan a diferentes nodos que nos puede ayudar con la búsqueda. Y aquí, si quería tener un árbol de búsqueda binaria, Yo sé que mi medio si 55. Yo sólo voy a crear ese como mi medio, como mi raíz, y luego me voy a tener valores giran fuera de ella. Así que aquí, si yo voy a buscar el valor de 66, puedo comenzar a los 55. Es 66 mayor que 55? Sí lo es, así que sé que busco mus i n el puntero derecho de este árbol. Voy al 77. OK, es 66 menor o mayor que 77? Es menor que, por lo que sé, oh, que tiene que ser el nodo de la izquierda. Así que aquí estamos tipo de preservación todas las grandes cosas acerca de matrices, así como el cambio de tamaño dinámico de objetos, siendo capaz de insertar y eliminar a voluntad, sin tener que preocuparse por el fijo cantidad de espacio. Todavía conservamos todos esas cosas maravillosas al mismo tiempo ser capaz de preservar la registrar y buscar el tiempo de búsqueda binaria que sólo estábamos previamente capaz de obtener una frase. Estructura de datos fresca, tipo de complejo de implementar, el nodo. Como se puede ver, todo lo que es la estructura del nodo es que usted tiene a la izquierda y un puntero derecho. Eso es todo lo que es. Así que en lugar de sólo que tiene una x o una anterior. Usted tiene una izquierda o una derecha y luego puedes tipo de enlazarlos Sin embargo así lo desea. OK, estamos en realidad va simplemente tomar unos minutos. Así que vamos a volver aquí. Como he dicho anteriormente, Yo como que expliqué la lógica detrás de la forma en que sería buscar a través de esto. Vamos a tratar pseudocoding esto a ver si podemos aplicar el tipo de misma lógica de búsqueda binaria a un tipo diferente de estructura de datos. Si ustedes quieren tomar como una pareja minutos para sólo pensar en esto. OK. Muy bien, voy a en realidad sólo le dan el-- no, hablaremos sobre el pseudocódigo primero. Así que no quiere que nadie para dar una puñalada en lo lo primero que quiere hacer cuando usted está comenzando la búsqueda es? Si estamos buscando el valor de 66, lo que es lo primero que queremos hacer en caso de queremos binario buscar este árbol? AUDIENCIA: ¿Quieres ver a la derecha y buscar izquierda y ver [inaudible] mayor número. ANDI Peng: Sí, exactamente. Así que vamos a mirar a su raíz. Hay un montón de maneras que usted puede llamar que, dicen a su gente nodo padre. Me gusta decir que la raíz porque eso es como la raíz del árbol. Usted va a mirar el nodo raíz, y ya está vamos a ver es 66 mayor que o menor que 55. Y si es mayor que, además, es mayor que, ¿hacia dónde queremos ver? ¿Dónde queremos buscar, ¿no? Queremos buscar la mitad derecha de este árbol. Así tenemos que, convenientemente, un puntero que apunta a la derecha. Y así entonces podemos establecer nuestra nueva raíz para ser 77. Sólo podemos ir a donde quiera el puntero está apuntando. Bueno, oh, aquí estamos empezando a los 77, y podemos simplemente hacer esto de forma recursiva y otra vez. De esta manera, usted clase de tener una función. Usted tiene una manera de buscar que simplemente puede repetir una y otra y otra vez, dependiendo de donde quieres buscar hasta que finalmente llegue al valor que usted está buscando. ¿Tener sentido? Estoy a punto de mostrar que el actual código, y es una gran cantidad de código. No hay necesidad de asuste. Hablaremos a través de él. En realidad no. Eso fue sólo pseudocódigo. OK, eso fue sólo el pseudocódigo, que es un poco complejo, pero es totalmente bien. Todo el mundo siguiendo a lo largo de aquí? Si la raíz es nulo, el regreso falso, porque eso significa que ni siquiera tiene nada allí. Si la raíz n es el valor, por lo que si pasa a ser el que usted está mirando, entonces usted va a devolver true porque sabes que lo has visto. Pero si el valor es menor a raíz de n, eres ir a buscar a la izquierda niño o la hoja izquierda, lo que quieras llamarlo. Y si el valor es mayor que la raíz, usted va a buscar el árbol adecuado, luego simplemente ejecutar la función a través de la búsqueda de nuevo. Y si la raíz es nulo, que esa significa que ha llegado al final? Eso significa que no tiene más más hojas para buscar, entonces usted sabe, oh, supongo que no hay aquí porque después he mirado a través todo el asunto y no está aquí, que sólo podría no estar aquí. ¿Eso tiene sentido para todo el mundo? Así es como la búsqueda binaria preservar las capacidades de listas enlazadas. Fresco, por lo que el segundo tipo de la estructura de datos que ustedes puede probar la aplicación en su conjunto de procesadores, sólo tienes que elegir un método. Pero tal vez un método alternativo para la tabla hash es lo que llamamos un trie. Todo un trie es un tipo específico de árbol que tiene valores que van a otros valores. Así que en lugar de tener un binario árbol en el sentido de que sólo uno Lo puede apuntar a dos, usted puede tener punto de una cosa a muchas, muchas cosas. Usted esencialmente tiene arrays dentro de los cuales se almacenan punteros que apuntan a otras matrices. Así que el nodo de la forma en que definiría un trie es que queremos tener un Boole, c palabra, ¿verdad? Así que el nodo es de Boole como verdadera o falsa, en primer lugar a la cabeza de esa matriz, se trata de una palabra? En segundo lugar, usted quiere tener punteros a lo que el resto de ellos lo son. Un poco complejo, un poco abstracto, pero Voy a explicar lo que todos los medios. Así que aquí, en la parte superior, si tiene un arsenal ya declaró, un nodo donde se tiene una de Boole valor almacenado en la parte delantera que le dice que es esta una palabra? ¿No es esto una palabra? Y entonces usted tiene la resto de su matriz que realmente almacena toda la posibilidades de lo que podría ser. Así, por ejemplo, como en la parte superior que tiene lo primero que dice verdad o falso, sí o no, se trata de una palabra. Y entonces usted tiene de 0 a 26 de las letras que se pueden almacenar. Si quisiera buscar aquí de palo, me voy a la parte superior y busco B. Encuentro B en mi matriz, y por lo que sé, está bien, es B una palabra? B no es una palabra, por lo tanto, Tengo que seguir buscando. Voy de B, y miro a la puntero que apunta hacia B y veo otra gama de información, la misma estructura que teníamos antes. Y aquí-- oh, la próxima carta en la [inaudible] es A. Así que miramos en esa matriz. Nos encontramos con el octavo valor, y luego miramos a ver, oh, bueno, es que una palabra, es B-A una palabra? No es una palabra. Tenemos que seguir buscando. Y así entonces miramos hacia donde el puntero de un puntos, y apunta a otra forma en que tenemos más valor almacenado. Y, finalmente, llegamos a B-A-T, que es una palabra. Y así, la próxima vez se mira, vas para tener el registro de entrada de, sí, esta función booleana es verdadera. Y así, en el sentido de que estamos tipo de tener un árbol con matrices. Así que usted puede clase de búsqueda abajo. En lugar de una función de hash y la asignación de valores de lista enlazada, que sólo puede poner en práctica un trie que busca downwords. Muy, muy complicado las cosas. No es fácil de pensar, porque yo soy como escupir tantas estructuras de datos fuera a ti, pero lo hace a todos tipo de entender cómo funciona la lógica de esto? Vale, guay. Así B-A-T, y luego usted va a buscar. La próxima vez que te vas para ver, oh, bueno, eso es cierto, por lo tanto sé que esto debe ser una palabra. Lo mismo para el zoológico. Así que aquí está la cosa ahora mismo, si querido buscar zoológico, en este momento, Actualmente zoológico no es un palabra en el diccionario porque, como ustedes pueden ver, el primer lugar que tenemos un booleano return true es al final del zoom. Tenemos Z-O-O-M. Y aquí, no en realidad tenemos la palabra, el zoológico, en el diccionario porque esta casilla no está marcada. Así que el equipo no saber que el zoológico es una palabra porque la forma en que hemos almacenada, sólo un zoom aquí en realidad tiene un valor booleano eso se ha convertido cierto. Así que si queremos insertar el palabra, parque zoológico, en nuestro diccionario, ¿cómo podríamos ir haciendo eso? ¿Qué tenemos que hacer para asegurarnos de que nuestro computadora sabe que Z-O-O es una palabra y no es la primera palabra es Z-O-O-M? AUDIENCIA: [inaudible] ANDI Peng: Exactamente, nos querrá asegurarse de que este aquí, que el valor booleano es comprobar fuera de que es verdad. Z-O-O, a continuación, vamos a comprobar que, así que sabemos exactamente, hey, el zoológico es una palabra. Voy a decirle al equipo que es una palabra tan que cuando los controles informáticos, se sabe que el zoológico es una palabra. Debido a recordar todos estos datos estructuras, es muy fácil para nosotros decir, oh, bate de una palabra. Zoo es una palabra. Ampliar una palabra. Pero cuando usted está construyendo él, el equipo tiene ni idea. Así que tienes que decirle exactamente ¿en qué punto se trata de una palabra? ¿En qué punto no es que una palabra? Y ¿en qué momento hacer yo que buscar cosas, y en qué momento qué tengo que ir ahora? Todo el mundo clara de eso? Guay. Y entonces viene la problema de cómo lo haríamos ir sobre la inserción de algo que en realidad no está ahí? Así que digamos que queremos insertar la palabra, baño, en nuestra trie. Como ustedes pueden ver como actualmente todo lo que tenemos ahora es B-A-T, y esta nueva estructura de datos Tenía una pinta que señalado nula porque suponemos que, oh, no hay palabras después de B-A-T, ¿por qué necesitamos para mantener tener las cosas después de que T. Pero el problema surge si hacemos que quiero tener una palabra que viene después del T. Si usted tiene baño, eres va a querer un derecho H. Y así el camino que vamos a hacer eso es vamos a crear un nodo separado. No estamos asignamos cualquier cantidad de la memoria de esta nueva matriz, y vamos a asignar punteros. Vamos a asignar el H, En primer lugar, este nula, vamos a deshacerse de él. Vamos a tener los abajo del punto H. Si vemos una H, queremos que ir a otro lugar. Aquí, podemos entonces marque sí. Si llegamos a una H después de la T, oh, entonces sabemos que se trata de una palabra. El booleana va a volver realidad. Todo el mundo clara sobre cómo sucedió eso? OK. Así que, esencialmente, todos estas estructuras de datos que hemos repasado la actualidad, tengo ido por encima de ellos muy, muy rápidamente y no en mucho detalle, y eso está bien. Una vez que empiece jugar con ella, podrás no perder de vista donde todos los punteros son, lo que está pasando en su estructuras de datos, etcétera. Van a ser muy útil, y le toca a usted chicos para averiguar totalmente cómo desea implementar cosas. Y así pset4, de 5-- oh, eso es incorrecto. Pset5 es faltas de ortografía. Como he dicho antes, usted va a, una vez otra vez, descarga el código fuente de nosotros. No va a haber tres principales Cosas que se descargan. Vas a descargar los diccionarios, kers y textos. Todas esas cosas son son ya sea diccionarios de palabras que queremos que usted compruebe o la prueba de la información que queremos que el corrector ortográfico. Y así los diccionarios damos vas para darle palabras reales que queremos que le permite almacenar de alguna manera en una forma que es más eficiente que una matriz. Y a continuación, los textos son va a ser lo que somos pidiéndole que corrector ortográfico para asegurarse todas las palabras son palabras reales allí. Y así los tres bloques de programas que le daremos se llaman dictionary.c, dictionary.h, y speller.c. Y luego todo se hace dictionary.c lo que se le pide que implementar. Carga palabras. Se explican los controles, y se asegura que todo lo que se ha insertado correctamente. diction.h es sólo un archivo de biblioteca que declara todas esas funciones. Y speller.c, vamos a darle. No es necesario modificar nada de eso. Todo speller.c no es tomar que, lo carga, comprueba la velocidad de la misma, pone a prueba el punto de referencia de como la forma rápidamente que eres capaz de hacer las cosas. Es un corrector ortográfico. Simplemente no te metas con ella, pero que Asegúrese de entender lo que está haciendo. Nosotros usamos una función llamada getrusage que pone a prueba el rendimiento de su hechizo inspector. Todo lo que hace es básicamente probar la tiempo de todo en su diccionario, así que asegúrate de que lo entiendes. Tenga cuidado de no meterse con ella o las demás cosas no funcionarán correctamente. Y la mayor parte de este desafío es para chicos Para modificar realmente dictionary.c. Vamos a darle 140.000 palabras en un diccionario. Vamos a darle un texto archivo que tiene esas palabras, y queremos que usted sea capaz de organizar en una tabla de hash o un trie porque cuando le pedimos que deletrear check-- imaginar si eres hechizo comprobar como la Odisea de Homero. Es como este gran, gran prueba,. Imagínese si todos y cada uno palabra que había que mirar a través de una matriz de 140.000 valores. Eso llevaría para siempre para su máquina para correr. Por eso queremos organizar nuestra datos en estructuras de datos más eficientes como una tabla hash o un trie. Y entonces ustedes pueden clase de cuando se busca el acceso las cosas más fácilmente y con mayor rapidez. Y así que ten cuidado para resolver las colisiones. Vas a tener un montón de palabras de ese comienzo con A. Vas a conseguir un manojo palabras que empezar con B. Hasta que chicos cómo quieres resolverlo. Tal vez hay más función hash eficiente que sólo la primera letra algo, y por lo que toca a usted chicos para hacer la clase de lo que quieras. Tal vez desee agregar todas las letras juntas. Tal vez usted quiere gustaría hacer cosas extrañas para tener en cuenta el número de letras, lo que sea. Hasta que ustedes lo que quieres hacer. Si quieres hacer una tabla hash, si usted Inténtalo de un trie, totalmente de usted. Voy a advertirle delante de tiempo que el trie es típicamente un poco más difícil sólo porque hay mucho más punteros a no perder de vista. Pero totalmente de ustedes. Es mucho más eficiente en la mayoria de los casos. ¿Quieres ser realmente capaz de mantener un registro de todos sus punteros. Como hacer la misma cosa que estaba haciendo aquí. Cuando usted está tratando de insertar valores en una tabla hash o eliminar, asegúrese de que usted es realmente hacer el seguimiento de donde todo es debido es muy fácil porque si yo soy intentar insertar como la palabra, andy. Digamos que es una palabra real, la palabra, andy, en una lista gigante de una palabras. Si lo que pasa es reasignar un mal indicador, oops, ahí va la totalidad de el resto de mi lista enlazada. Ahora, la única palabra que tener es andy, y ahora todas las otras palabras diccionario se han perdido. Y por lo que desea asegurarse de que llevar un registro de todos sus punteros o de lo contrario va a conseguir enormes problemas en su código. Dibuja las cosas con cuidado, paso a paso. Esto hace que sea mucho más fácil de imaginar. Y, por último, que desea ser capaz de probar el rendimiento de su programa en el gran tablero. Si ustedes toman un mira CS50 en este momento, tenemos lo que se llama el gran tablero. Es la hoja de puntuación de los más rápidos deletrear tiempos de cheques a través de todas CS50 en este momento, creo que la parte superior como 10 veces pienso que ocho de ellos son personal. Realmente queremos que ustedes nos ganaron. Todos nosotros estábamos tratando de poner en práctica el código rápido como sea posible. Queremos que ustedes tratan de desafiar nos e implementar más rápido que todos nosotros poder. Y por lo que este es realmente la primera vez que estamos pidiendo a ustedes para hacer un conjunto de procesadores que usted puede hacer realidad en cualquier método quieres. Yo siempre digo, esto es más afín a una solución de la vida real, ¿verdad? Yo digo, hey, necesito que hagas esto. Construir un programa que hace esto por mí. Hazlo como quieras. Sólo sé que quiero ayunar. Ese es su reto para esta semana. Ustedes, que va para darle una tarea. Vamos a darle un desafío. Y luego le toca a ustedes completamente solo averiguar ¿cuál es la más rápida y más forma eficiente para implementar esto. ¿Sí? AUDIENCIA: ¿Estamos autorizados a si Queríamos investigar maneras más rápidas hacer tablas hash en línea, podemos hacer eso y citar el código de otra persona? ANDI Peng: Sí, totalmente bien. Así que si ustedes leen el especificaciones, hay una línea en la especificación que dice que ustedes son totalmente libres a la investigación de hash funciones en lo que son algunos de las funciones de hash más rápidos para ejecutar las cosas como siempre y cuando se cite ese código. Así que algunas personas ya tienen descubierto maneras rápidas de hacer los correctores ortográficos, de rápido formas de almacenar información. Totalmente de ustedes si quiere tomar sólo eso, ¿verdad? Asegúrese de que está citando. El reto aquí realmente que estamos tratando de probar es asegurarse de que usted sabe su manera alrededor de punteros. Por lo que usted implementación la función hash real y dar con igual las matemáticas para hacer eso, ustedes pueden investigar lo que sea métodos en línea que ustedes quieren. ¿Sí? AUDIENCIA: ¿Podemos citar sólo mediante el uso de la [inaudible]? ANDI Peng: Sí. Usted puede simplemente, en su comentario, se puede citar como, oh, tomado de bla, bla, yada, función hash. ¿Alguien tiene alguna pregunta? En realidad breezed en la sección de hoy. Voy a estar aquí para responder a las preguntas también. Además, como ya he dicho, la oficina horas de esta noche y mañana. La especificación de esta semana es en realidad super fácil y super corto de leer. Yo sugeriría tomar una mirada, justo leer a través de la totalidad de la misma. Y Zamyla realidad que camina a través de cada una de las funciones que necesita para implementar, y por lo que es muy, muy claro cómo hacer todo. Sólo para asegurarse de que está hacer el seguimiento de los punteros. Se trata de un conjunto de procesadores muy difícil. No es un reto porque al igual que, oh, los conceptos son mucho más difícil, o usted tiene que aprender tanto nueva sintaxis de la manera que usted hizo por última pset. Este conjunto de procesadores es difícil porque hay tantos punteros, y entonces es muy, muy fácil de una vez usted tiene un error en su código que no pueda encontrar donde ese error es. Y tan completa y absoluta fe en ti chicos sean capaces de superar nuestra [inaudible] ortografía. En realidad no tengo ninguna mina escrita todavía, pero estoy a punto de escribir la mía. Así, mientras que usted está escribiendo el suyo, voy a estar escribiendo la mía. Voy a tratar de hacer mina más rápido que el suyo. Vamos a ver quién tiene el más rápido. Y sí, voy a ver todos ustedes aquí el martes. Voy a correr una especie como un taller conjunto de procesadores. Todas las secciones este semana son talleres PSet, por lo que ustedes tienen muchas oportunidades en busca de ayuda, las horas de oficina como siempre, y realmente espero con interés leer todo el código a sus chicos. Tengo pruebas aquí si chicos quieren venir conseguirlos. Eso es todo.