JASON HIRSCHHORN: Bienvenidos a todos a la Sección Siete. Estamos en la séptima semana del curso. Y este próximo Jueves es Halloween, así que estoy vestido como una calabaza. Yo no podía agacharse y poner en mis zapatos, así que es por eso que estoy sólo el uso de calcetines. Asimismo, no llevo nada debajo esto, así que no puedo quitarlo si es distraer a usted. Me disculpo de antemano por ello. No es necesario imaginar ¿qué está pasando. Yo llevo calzoncillos. Así que está todo bien. 

Tengo una historia más larga de por qué estoy vestido como una calabaza, pero yo voy a guardar para más adelante en esta sección porque yo quiero empezar. Tenemos un montón de cosas interesantes para repasar esta semana. La mayoría de ellos se refieren directamente a este conjunto de problemas de la semana, las faltas de ortografía. Vamos a ir sobre ligado listas y tablas hash para toda la sección. Pongo esta lista cada semana, una lista de recursos para usted para ayudarle con el material de este curso. Si en una pérdida o si busca alguna obtener más información, echa un vistazo a uno de estos recursos. 

Una vez más, es pset6 faltas de ortografía, conjunto de procesadores de esta semana. Y también te anima, y ​​yo animaros, utilizar algún otro recursos específicamente para este conjunto de procesadores. En particular, los tres que he enumerado en la pantalla - gdb, que hemos estado familiarizados con y estado utilizando desde hace un tiempo, es va a ser de mucha ayuda esta semana. Así que puse que hasta aquí. Pero cada vez que se trabaja con C, siempre se debe utilizar gdb para depurar los programas. Esta semana también valgrind. ¿Alguien sabe lo que valgrind hace? 

AUDIENCIA: Comprueba si hay fugas de memoria? 

JASON HIRSCHHORN: Valgrind cheques para las pérdidas de memoria. Así que si algo malloc en su programa, estás pidiendo memoria. Al final de su programa, usted tiene para escribir libre de todo lo que has malloced para dar la memoria. Si no escribes libre al final y su programa llega a una conclusión, todo automáticamente ser liberado. Y para los pequeños programas, que es No es gran cosa. Pero si usted está escribiendo un rodaje más largo programa que no se cierra, necesariamente, en un par de minutos o un par de segundos, a continuación, pérdidas de memoria puede convertirse en un gran negocio. 

Así que para pset6, la expectativa es que usted tendrá pérdidas de memoria cero con su programa. Para comprobar si hay fugas de memoria, valgrind ejecutar y te voy a dar algunas buenas salida que le permite saber si o no todo era gratis. Practicaremos con él más adelante hoy, con suerte. 

Por último, el comando diff. Ha utilizado algo similar a ella en pset5 con la herramienta vistazo. Le ha permitido observar el interior. También usaste diff, también, por el problema establece especificaciones. Pero en que permite comparar dos archivos. Se podría comparar el archivo de mapa de bits y info encabezados de una solución personal y su solución en pset5 si opta por utilizarlo. Dif. le permitirá hacer eso, también. Puede comparar la respuesta correcta para El problema de esta semana establece en su respuesta y ver si se alinee o ver dónde están los errores. 

Así que estos son tres buenas herramientas que usted debe utilizar para esta semana, y Definitivamente revisar su programa de con estas tres herramientas antes de dar vuelta pulg Una vez más, como ya he mencionado todas las semanas, si tiene alguna reacción para mí - tanto positiva y constructiva - no dude en dirigirse a la página web en la parte inferior de esta diapositiva y la entrada allí. Realmente aprecio cualquier y todos los comentarios. Y si me das las cosas específicas que Que puedo hacer para mejorar o que soy haciendo así que me gustaría Continúo, me tomo muy a pecho y realmente se esfuerzan para escuchar para su regeneración. No puedo prometer que voy a hacer todo, sin embargo, como llevar una calabaza disfraz cada semana. 

Así que vamos a pasar la mayor parte de sección, como ya he dicho, hablando de listas enlazadas y tablas hash, que será directamente aplicable a la problema establecido esta semana. Las listas enlazadas vamos a repasar relativamente rápidamente, porque hemos pasado un poco justo de tiempo de ir sobre ella en la sección. Y así vamos a llegar directamente a la problemas de codificación para listas enlazadas. Y luego, al final vamos a hablar de tablas hash y cómo se aplican a este Problema de la semana. 

Usted ha visto este código antes. Esta es una estructura, y que está definiendo algo nuevo llamado nodo. Y dentro de un nodo no es un entero aquí y allá es un puntero a otro nodo. Hemos visto esto antes. Esto ha estado subiendo de un par de semanas ahora. Combina los punteros, que hemos estado trabajar con, y estructuras, que permiten nos permite combinar dos diferentes cosas en un solo tipo de datos. 

Hay mucho que hacer en la pantalla. Pero todo esto debe ser relativamente familiarizado con usted. En la primera línea, que declarar un nuevo nodo. Y luego, dentro de ese nuevo nodo, me puse el número entero en ese nodo a uno. Vemos en la siguiente línea que estoy haciendo un printf comando, pero he atenuados el comando printf porque la verdad parte importante es esta línea aquí - new_node.n. ¿Qué significa el punto? 

AUDIENCIA: Vaya al nodo y evaluar el valor de n para ello. 

JASON HIRSCHHORN: Eso es exactamente correcto. Dot significa acceder a la parte n de este nuevo nodo. Esta línea siguiente hace qué? Michael. 

AUDIENCIA: Se crea otro nodo que se apunte al nuevo nodo. 

JASON HIRSCHHORN: Así que no hace crear un nuevo nodo. Se crea un qué? 

AUDIENCIA: Un puntero. 

JASON HIRSCHHORN: Un puntero a un nodo, según lo indicado por este nodo * aquí. Por lo tanto, crea un puntero a un nodo. Y qué nodo se lo apunta a, Michael? 

AUDIENCIA: Nuevo nodo? 

JASON HIRSCHHORN: Nuevo nodo. Y está apuntando allí porque hemos dado que la dirección del nuevo nodo. Y ahora en esta línea vemos dos maneras diferentes de expresar la misma cosa. Y yo quería señalar cómo estos dos cosas son lo mismo. En la primera línea, que eliminar la referencia el puntero. Así que vamos al nodo. Eso es lo que significa esta estrella. Hemos visto que antes con los punteros. Ir a ese nodo. Eso está en paréntesis. Y a continuación, acceder a través del operador de punto el elemento n de ese nodo. 

Así que eso tomar la sintaxis vimos aquí y ahora usarla con un puntero. Por supuesto, se pone un poco ocupado si usted está escribiendo esos paréntesis - esa estrella y ese punto. Se pone un poco ocupado. Así que tenemos un poco de azúcar sintáctica. Y esta línea aquí - ptr_node-> n. Que hace exactamente lo mismo. Así que esas dos líneas de código son equivalente y lo hará exactamente lo mismo. 

Pero yo quería señalar los antes de ir más lejos para que usted entienda que realmente esta cosa aquí es sólo el azúcar sintáctica para eliminación de referencias el puntero y luego ir a la parte n de esa estructura. ¿Una pregunta sobre esta diapositiva? Aceptar. 

Así que vamos a ir a través de un par de las operaciones que se pueden hacer en listas enlazadas. Una lista enlazada, el recuerdo, es una serie de nodos que apuntan el uno al otro. Y por lo general, comenzamos con un puntero llamado la cabeza, por lo general, que apunta a lo primero en la lista. Así que en la primera línea aquí, tener primero el original L. Así que esa cosa que se pueda imaginar - esto texto aquí se puede pensar en como sólo el puntero hemos almacenado en alguna parte que los puntos para el primer elemento. Y en esta lista enlazada tenemos cuatro nodos. Cada nodo es una caja grande. La caja más grande dentro de la gran caja es la parte entera. Y luego tenemos una parte puntero. 

Estas cajas no están dibujados a escala debido a lo grande que es un entero en bytes? ¿Qué tan grande ahora? Cuatro. Y qué tan grande es un puntero? Cuatro. Así que en realidad, si tuviéramos que dibujar esto es a escala ambas cajas sería el mismo tamaño. En este caso, queremos insertar algo a la lista enlazada. Así que usted puede ver aquí abajo estamos insertando cinco Atravesamos a través de la lista enlazada, donde encontrará cinco va, y luego insertarlo. 

Vamos a romper eso y van un poco más lentamente. Voy a señalar a la junta. Así que tenemos nuestro nodo cinco que hemos creado en mallocs. ¿Por qué se está riendo de todo el mundo? Es broma. Aceptar. Así que hemos malloced cinco. Hemos creado este nodo en otro lugar. Nosotros lo tenemos listo para ir. Empezamos en la parte frontal de nuestra lista con dos. Y queremos insertar de una manera ordenada. 

Así que si vemos a dos y queremos poner en cinco, ¿qué hacemos cuando vemos algo menos que nosotros? ¿Qué? Queremos insertar cinco en este lista enlazada, manteniéndolo ordenado. Vemos el número dos. Entonces, ¿qué hacemos? Marcus? 

AUDIENCIA: Llame al puntero al siguiente nodo. 

JASON HIRSCHHORN: ¿Y por qué nos vamos a la siguiente? 

AUDIENCIA: Porque es la siguiente nodo de la lista. Y sólo se sabe que otra ubicación. 

JASON HIRSCHHORN: Y cinco es mayor de dos, en particular. Porque queremos mantenerla ordenada. Así cinco es mayor que dos. Así que pasamos a la siguiente. Y ahora llegamos a cuatro. ¿Y qué pasa cuando lleguemos a cuatro? 

El cinco es mayor que cuatro. Así que seguimos adelante. Y ahora estamos a las seis. ¿Y qué es lo que vemos a las seis? Sí, Carlos? 

AUDIENCIA: Six es mayor que cinco. 

JASON HIRSCHHORN: Six es mayor que cinco. Así que ahí es donde queremos para insertar cinco. Sin embargo, tenga en cuenta que si nos sólo tienen un puntero aquí - este es nuestro puntero extra que es atravesando por la lista. Y estamos apuntando a seis. Hemos perdido la pista de lo viene antes de las seis. Así que si queremos insertar algo en esta lista mantenerla ordenada, que probablemente necesitará el número de punteros? 

AUDIENCIA: Dos. 

JASON Hirschhorn: Dos. Uno para realizar un seguimiento de la corriente uno y uno para realizar un seguimiento de la anterior. Esta es sólo una lista vinculada individualmente. Sólo va en una dirección. Si tuviéramos una lista doblemente enlazada, donde todo apuntaba a la cosa después de ella y la cosa antes de que, a continuación, no tendríamos necesidad de hacer eso. Pero en este caso no queremos perder un seguimiento de lo que hubo antes de nosotros en caso de tenemos que insertar cinco en alguna parte en el medio. Digamos que Insertamos nueve. ¿Qué pasaría cuando llegamos a las ocho? 

AUDIENCIA: Usted tendría que conseguir que el punto nulo. En lugar de tener punto nulo tendrías para agregar un elemento y luego tener que apunte a nueve. 

JASON Hirschhorn: Exactamente. Así que tenemos ocho. Llegamos al final de la lista debido a esto apunta a null. Y ahora, en lugar de tener que apunte a nula tenemos que apunte a nuestro nuevo nodo. Y ponemos el puntero en nuestro nuevo nodo en null. ¿Alguien tiene alguna pregunta acerca de la inserción? ¿Qué pasa si no se preocupan por mantener la lista ordenada? 

AUDIENCIA: Stick it en el principio o al final. 

JASON Hirschhorn: Pegúela en al principio o al final. ¿Cuál debemos hacer? Bobby? ¿Por qué al final? 

AUDIENCIA: Debido a que el principio ya está lleno. 

JASON Hirschhorn: OK. El comienzo ya está lleno. ¿Quién quiere argumentar en contra de Bobby. Marcus. 

AUDIENCIA: Bueno, usted probablemente querrá pegarlo al principio porque de lo contrario si usted lo pone en final que tendría que recorrer toda la lista. 

JASON Hirschhorn: Exactamente. Así que si estamos pensando en el tiempo de ejecución, la tiempo de ejecución de la inserción en el extremo sería n, el tamaño de este. ¿Cuál es el tiempo de ejecución de O de inserción por el principio? Constante de tiempo. Así que si usted no se preocupan por mantener algo ordenada, mucho mejor que sólo insertar al principio de esta lista. Y eso se puede hacer en tiempo constante. 

Aceptar. Operación siguiente se encontró que otros - hemos redactaron del búsqueda. Pero vamos a mirar a través de la lista enlazada por algún objeto. Ustedes han visto el código de buscar antes en la conferencia. Pero que tipo de sólo hicimos con insertar, o al menos la inserción algo ordenada. Te ves a través, pasando por el nodo nodo, hasta que encuentre el número que usted está buscando. ¿Qué sucede si usted llega a el final de la lista? Digamos que yo estoy buscando a las nueve y me llegar al final de la lista. ¿Qué hacemos? 

AUDIENCIA: Volver falso? 

JASON Hirschhorn: Regresa falso. No nos encontrará. Si llega al final de la lista y que no encontró el número al que está buscando, no está allí. ¿Una pregunta sobre encontrar? Si se trataba de una lista ordenada, lo que haría ser diferente para nuestra búsqueda? Sí. 

AUDIENCIA: Se encontraría el primer valor es mayor que el usted está buscando y a continuación, devolver false. 

JASON Hirschhorn: Exactamente. Así que si se trata de una lista ordenada, si llegamos a algo que es más grande que lo que estamos buscando, nosotros no necesitamos seguir adelante hasta el final de la lista. Podemos en ese punto return false porque no vamos a encontrar. La pregunta es ahora, hemos hablado de mantener listas enlazadas ordenados, manteniéndolos sin clasificar. Eso va a ser algo que te probablemente va a tener que pensar en cuando un problema de codificación establecido cinco si elegir una tabla hash con separada enfoque de encadenamiento, que hablaremos más tarde. 

Pero ¿vale la pena mantener la lista ordenada y luego ser capaz de tener tal vez Búsquedas más rápidas? ¿O es mejor para insertar rápidamente algo en tiempo de ejecución constante, pero luego tener más tiempo buscando? Eso es un compromiso justo ahí que llegar a decidir qué es lo más apropiado para su problema específico. Y no es necesariamente una respuesta toda la razón. Pero sin duda es una decisión que usted obtiene de hacer, y probablemente bueno para defender que en, digamos, un comentario o dos por qué que eligió una sobre la otra. 

Por último, la eliminación. Hemos visto borrar. Es similar a la búsqueda. Buscamos el elemento. Digamos que estamos tratando de eliminar seis. Así nos encontramos con seis aquí. Lo que tenemos que asegurarnos de que hacer es que todo lo que está apuntando a seis - como vemos en el paso dos aquí abajo - lo que sea que apunta a seis necesidades a saltar seis ahora y cambiar para cualquiera que sea seis está apuntando. No queremos dejar huérfano vez el resto de nuestra lista por el olvido para establecer que puntero anterior. Y a continuación, a veces, dependiendo en el programa, ellos sólo eliminar este nodo completo. A veces usted querrá volver el valor que está en este nodo. Así es como la supresión de las obras. ¿Tiene preguntas sobre eliminar? 

AUDIENCIA: Así que si usted va a borrar él, sería simplemente usar gratis porque presumiblemente se malloced? 

JASON Hirschhorn: Si desea liberar algo que es exactamente correcto y usted malloced ella. Digamos que queríamos volver a este valor. Podríamos volver seis y luego libre este nodo y conexión de llamadas en él. O es probable que llamaríamos libre primero y luego regresar seis. 

Aceptar. Así que vamos a pasar a la práctica de codificación. Vamos a codificar tres funciones. La primera se llama insert_node. Así que tienes el código que te envié, y si estás viendo esto más adelante se puede acceder al código en linked.c en el sitio web CS50. Pero en linked.c, hay algo de código esqueleto que ya está ha escrito para usted. Y luego hay un par de funciones que necesita para escribir. 

En primer lugar vamos a escribir insert_node. ¿Y qué hace insert_node es decir inserta un entero. Y usted está dando el número entero en una lista enlazada. Y, en particular, es necesario para mantener la lista ordenada desde el más pequeño al más grande. Además, usted no quiere inserte los duplicados. Por último, como se puede ver insert_node devuelve un bool. Así que se supone que debes saber al usuario si o no el inserto era éxito devolviendo verdadero o falso. Al final de este programa - y para esta etapa no es necesario que preocuparse por la liberación de cualquier cosa. Así que todo lo que estamos haciendo es tomando un entero e insertándolo en una lista. 

Eso es lo que te estoy pidiendo que hagas ahora. Una vez más, en el linked.c, que se todos tienen, es el código de esqueleto. Y hay que ver hacia el fondo la declaración de la función de la muestra. Sin embargo, antes de entrar en la codificación que en C, yo le animo a ir a través de los pasos que hemos estado la práctica de cada semana. Nosotros ya hemos pasado por una foto de esto. Así que usted debe tener algún conocimiento de cómo funciona esto. Pero me animo a escribir algunos pseudocódigo antes de sumergirse pulg Y vamos a repasar pseudocódigo como un grupo. Y una vez que has escrito tu pseudocódigo, y una vez que hemos escrito nuestra pseudocódigo como grupo, puede entrar en la codificación en C. 

Como un mano a mano, la función insert_node es probablemente el más difícil de los tres que vamos a escribir porque añadido algunas restricciones adicionales para su programación, en particular, que no vas a insertar cualquier duplicados y que la lista debe permanecer ordenado. Así que este es un programa no trivial que usted necesita para codificar. ¿Y por qué no te llevas seis y cincuenta y cinco minutos, para simplemente trabajar en el pseudocódigo y el código. Y luego vamos a empezar ir como un grupo. Una vez más, si usted tiene alguna pregunta sólo levantar la mano y voy a entrar en razón. . 

Nosotros también, en general hacemos estos - o yo no te digo explícitamente puede trabajar con la gente. Pero, obviamente, yo le animo, si tiene preguntas, pedir al vecino sentado a tu lado o incluso trabajar con alguien más si quieres. Este no tiene que ser un individuo actividad silenciosa. 

Vamos a empezar con la escritura de algunos pseudocódigo en el tablero. ¿Quién me puede dar la primera línea de pseudocódigo para este programa? Para esta función, en lugar - insert_node. Alden? 

AUDIENCIA: Así que lo primero que hice fue crear un nuevo puntero al nodo y yo inicializa lo que apunta a la misma cosa que la lista está señalando. 

JASON Hirschhorn: OK. Así que va a crear un nuevo puntero a la lista, no para el nodo. 

AUDIENCIA: Así es. Sí. 

JASON Hirschhorn: OK. Y entonces, ¿qué es lo que queremos hacer? ¿Qué hay después de eso? ¿Qué pasa con el nodo? No tenemos un nodo. Sólo tenemos un valor. Si queremos insertar un nodo, lo que hace que necesita hacer primero antes de que podamos siquiera pensar insertarlo? 

AUDIENCIA: Oh, lo siento. tenemos que malloc espacio para un nodo. 

JASON Hirschhorn: Excelente. Vamos a hacer - Aceptar. No se puede llegar tan alto. Aceptar. Vamos a ir hacia abajo, y luego estamos usando dos columnas. No puedo ir a que - Aceptar. Crear un nuevo nodo. Puede crear otro puntero a la lista o simplemente puede utilizar la lista, tal como existe. Usted realmente no necesita hacer eso. 

Así que creamos un nuevo nodo. Grande. Eso es lo que hacemos en primer lugar. ¿Qué sigue? 

AUDIENCIA: Espere. ¿Hay que crear un nuevo nodo ahora o debemos esperar para asegurarse de que no hay duplicados del nodo en la lista antes de que nos lo creamos? 

JASON Hirschhorn: Buena pregunta. Vamos a sostener que para más adelante porque el mayor parte del tiempo estaremos creando un nuevo nodo. Así que vamos a seguir eso aquí. Pero esa es una buena pregunta. Si creamos y nos encontramos un duplicado, lo que debe que hacemos antes de regresar? 

AUDIENCIA: liberarlo. 

JASON Hirschhorn: Si. Probablemente liberarlo. Aceptar. ¿Qué hacemos después de que crear un nuevo nodo? Annie? 

AUDIENCIA: Ponemos la número en el nodo? 

JASON Hirschhorn: Exactamente. Ponemos el número - que malloc espacio. Voy a dejar que todo en una sola línea. Pero tienes razón. Nos malloc espacio, y luego ponemos el número pulg Incluso podemos establecer el puntero parte de ella en null. Eso es exactamente correcto. Y entonces ¿qué pasa después de eso? Dibujamos la imagen en el tablero. Entonces, ¿qué hacemos? 

AUDIENCIA: Vamos a través de la lista. 

JASON Hirschhorn: Ir a través de la lista. Aceptar. ¿Y qué vamos a comprobar en cada nodo. Kurt, ¿qué es lo comprobamos para en cada nodo? 

AUDIENCIA: Ver si el valor de n de ese nodo es mayor que el valor de n de nuestro nodo. 

JASON Hirschhorn: OK. Yo voy a hacer - Sí, está bien. Así que es n - Yo voy a decir si el valor es mayor de este nodo, entonces, ¿qué hacemos? 

AUDIENCIA: Bueno, entonces nos insertamos lo correcto antes de eso. 

JASON Hirschhorn: OK. Así que si es mayor que este, entonces queremos insertar. Pero queremos insertar justo antes de porque nosotros también necesitamos ser hacer el seguimiento y, a continuación, de lo que era antes. Así que insertar antes. Así que es probable que perdimos algo anteriormente. Probablemente necesitemos estar manteniendo un seguimiento de lo que está pasando. Pero vamos a llegar allí. Entonces, ¿qué valor es inferior? Kurt, ¿qué hacemos si valor es menor que? 

AUDIENCIA: A continuación, sólo seguir adelante a menos que sea el último. 

JASON Hirschhorn: eso me gusta. Así que ir al siguiente nodo. A menos que sea el último - es probable que estamos comprobando que en los términos de una condición. Pero sí, el próximo nodo. Y eso no baje mucho, así que vamos a pasar por aquí. Pero si - ¿Todos pueden ver esto? Si somos iguales, ¿qué hacemos? Si el valor que estamos tratando de insertar es igual al valor de este nodo? ¿Sí? 

AUDIENCIA: [inaudible]. 

JASON Hirschhorn: Si. Dada esta - Marcus tiene razón. Podríamos haber hecho tal vez algo diferente. Pero teniendo en cuenta que hemos creado, aquí debemos liberar y luego regresar. Oh boy. ¿Así está mejor? ¿Cómo es eso? Aceptar. Gratis y entonces, ¿qué hacemos nosotros devolver, [inaudible]? Aceptar. ¿Nos estamos perdiendo algo? Entonces, ¿dónde hacer el seguimiento del nodo antes? 

AUDIENCIA: Creo que sería ir después de crear un nuevo nodo. 

JASON Hirschhorn: OK. Así que al principio probablemente vamos - sí, podemos crear un puntero a una nueva nodo, como un puntero de nodo anterior y un puntero nodo actual. Así que vamos a insertar eso aquí. Crear actual y anterior punteros a los nodos. Pero ¿cuándo nos ajustamos los punteros? ¿Dónde lo hacemos en el código? Jeff? 

AUDIENCIA: - condiciones de valor? 

JASON Hirschhorn: ¿Qué uno en particular? 

AUDIENCIA: Estoy confundido. Si el valor es superior a este nodo, ¿eso no significa que usted quiere ir al siguiente nodo? 

JASON HIRSCHHORN: Así que si nuestro valor es mayor que el valor de este nodo. 

AUDIENCIA: Sí, entonces lo que quiere ir más abajo de la línea, ¿no? 

JASON HIRSCHHORN: Así es. Así que no insertamos aquí. Si el valor es inferior a este nodo, a continuación, vamos al siguiente nodo - o entonces insertar antes. 

AUDIENCIA: Espera, que es este nodo y que es el valor? 

JASON HIRSCHHORN: Buena pregunta. Valor por esta definición de función es lo que se nos da. Así que el valor es el número que se nos da. Así que si el valor es menor que este nodo, necesitamos tiempo para insertar. Si el valor es superior a este nodo, vamos al siguiente nodo. Y volviendo a la pregunta original, sin embargo, donde - 

AUDIENCIA: Si el valor es mayor de este nodo. 

JASON HIRSCHHORN: Y así ¿qué hacemos aquí? Sweet. Eso es correcto. Yo sólo voy a escribir punteros de actualización. Pero eso sí, con la actual usted desea actualizar a apuntar a la siguiente. Cualquier otra cosa que se está perdiendo? Así que voy a escribir esto código en gedit. Y mientras hago esto, usted puede tener una par de minutos más para trabajar en la codificación esta en C. 

Así que tengo que ingresar el pseudocódigo. Una nota rápida antes de empezar. Puede que no seamos capaces de completamente terminar esto en todo tres de estas funciones. Hay soluciones correctas a los que voy a enviar por correo electrónico a ustedes después de la sección, y lo hará se publicarán en CS50.net. Así que no os animo a ir a buscar en las secciones. Te animo a que intente resolverlo usted poseer, y luego usar el la práctica problemas para comprobar sus respuestas. Todas ellas han sido diseñadas para cerca relacionarse y cumplir con lo lo que tienes que hacer en el conjunto de problemas. Así que te animo a practicar este por su cuenta y luego usar el código para compruebe sus respuestas. Porque quiero seguir adelante para discutir mesas en algún punto de la sección. Así que podríamos no conseguir en todo momento. Pero vamos a hacer lo más que podamos ahora. 

Aceptar. Comencemos. Asam, ¿cómo creamos un nuevo nodo? 

AUDIENCIA: Usted struct *. 

JASON HIRSCHHORN: Así que tener que hasta aquí. Oh, lo siento. ¿Decías struct *. 

AUDIENCIA: Y luego [? tipo?] nodo o nodo c. 

JASON HIRSCHHORN: OK. Voy a llamarlo new_node para que podamos permanecer constante. 

AUDIENCIA: Y usted desea establecer que a la cabeza, el primer nodo. 

JASON HIRSCHHORN: OK. Así que ahora esta apuntando a - por lo que este no ha creado un nuevo nodo aún. Esto es sólo apunta a la primer nodo en la lista. ¿Cómo se crea un nuevo nodo? Si necesito espacio para crear un nuevo nodo. Malloc. Y qué tan grande? 

AUDIENCIA: El tamaño de la estructura. 

JASON HIRSCHHORN: El tamaño de la estructura. Y ¿cuál es la estructura llamada? 

AUDIENCIA: Nodo? 

JASON HIRSCHHORN: Nodo. Así malloc (sizeof (nodo)); nos da el espacio. Y es esta línea - una cosa es incorrecto en esta línea. Es new_node un puntero a una estructura? Es un nombre genérico. Qué es - nodo, exactamente. Es un nodo *. Y, ¿qué hacemos después que malloc algo, Asan? ¿Qué es lo primero que vamos a hacer? ¿Qué pasa si no funciona? 

AUDIENCIA: Oh, compruebe si apunta al nodo? 

JASON HIRSCHHORN: Exactamente. Así que si usted new_node iguales iguales nulo, ¿qué hacemos? Esto devuelve un bool, esta función. Exactamente. Se ve bien. Cualquier cosa para agregar ahí? Vamos a añadir cosas al final. Pero que hasta el momento se ve bien. Crear indicadores actuales y anteriores. Michael, ¿cómo puedo hacer esto? 

AUDIENCIA: Usted tendría hacer un nodo *. Tendrías que lo hace a uno para new_node pero para la nodos que ya tienen. 

JASON HIRSCHHORN: OK. Así que el nodo actual estamos en. Voy a llamar a ese curr. Está bien. Hemos decidido que queremos mantener dos, porque tenemos que saber lo que hay antes de ella. ¿Qué son inicializadas a? 

AUDIENCIA: Su valor en nuestra lista. 

JASON HIRSCHHORN: Entonces, ¿cuál es el Lo primero en nuestra lista? O, ¿cómo sabemos que el a partir de nuestra lista es? 

AUDIENCIA: ¿No se aprobó en la función de? 

JASON HIRSCHHORN: Así es. Se aprobó en aquí. Así que si se pasa a la función, la inicio de la lista, ¿qué debemos establecer corriente igual a? 

AUDIENCIA: Lista. 

JASON HIRSCHHORN: Lista. Eso es exactamente correcto. Ahora que tiene la dirección de el principio de nuestra lista. Y ¿qué pasa con previa? 

AUDIENCIA: Lista menos uno? 

JASON HIRSCHHORN: No nada antes de ella. Entonces, ¿qué podemos hacer para significar nada? 

AUDIENCIA: Nulo. 

JASON HIRSCHHORN: Si. Eso suena como una buena idea. Perfect. Gracias. Ir a través de la lista. Constantino, ¿cuánto tiempo vamos que pasar por la lista? 

AUDIENCIA: hasta llegar a nulo. 

JASON HIRSCHHORN: OK. Así que si, mientras que, para el bucle. ¿Qué estamos haciendo? 

AUDIENCIA: Tal vez un bucle? 

JASON HIRSCHHORN: Vamos a hacer un bucle for. Aceptar. 

AUDIENCIA: Y decimos por - hasta que el puntero actual no es igual a nulo. 

JASON HIRSCHHORN: Así que si conocemos la condiciones, ¿cómo podemos escribir un bucle con sede fuera esa condición. ¿Qué clase de un bucle debemos utilizar? 

AUDIENCIA: While. 

JASON HIRSCHHORN: Si. Eso tiene más sentido con base fuera de lo que dijiste. Si sólo queremos ir a que lo haría sólo sé que cosa, tendría sentido hacer un bucle while. Mientras que la corriente no es igual a null, si el valor es inferior a este nodo. Akshar, dame de esa línea. 

AUDIENCIA: Si current-> n n menos de su valor. O revertir eso. Cambie esa franja. 

JASON HIRSCHHORN: Lo siento. 

AUDIENCIA: Cambie el soporte. 

JASON HIRSCHHORN: Así que si es mayor que el valor. Porque eso es confuso con la comente anteriormente, voy a hacer eso. Pero sí. Si nuestro valor es menor que este nodo, ¿qué hacemos? Oh. Lo tengo aquí mismo. Insertar antes. Aceptar. ¿Cómo hacemos eso? 

AUDIENCIA: ¿Sigue siendo mi? 

JASON HIRSCHHORN: Si. 

AUDIENCIA: Usted - new_node-> siguiente. 

JASON HIRSCHHORN: Entonces, ¿qué que va a ser igual? 

AUDIENCIA: Va a la misma corriente. 

JASON HIRSCHHORN: Exactamente. Y así, el otro - lo que más necesitamos para actualizar? 

AUDIENCIA: Compruebe si el pasado es igual a nulo. 

JASON HIRSCHHORN: Si prev - por lo que si es igual prev nulo. 

AUDIENCIA: Eso significa que va para convertirse en la cabeza. 

JASON HIRSCHHORN: Eso significa se ha convertido en la cabeza. Entonces, ¿qué hacemos? 

AUDIENCIA: Hacemos la cabeza es igual new_node. 

JASON HIRSCHHORN: Head iguales new_node. ¿Y por qué la cabeza aquí, no lista? 

AUDIENCIA: Debido a que la cabeza es un mundial variable, que es el punto de partida. 

JASON HIRSCHHORN: Sweet. Aceptar. Y - 

AUDIENCIA: Entonces, ¿los demás prev-> siguiente es igual new_node. Y luego puede volver realidad. 

JASON HIRSCHHORN: ¿Dónde nos pusimos fin new_node? 

AUDIENCIA: yo - Me puse de que al comienzo. 

JASON HIRSCHHORN: Entonces, ¿qué línea? 

AUDIENCIA: Después de la sentencia if comprobar si se sabe. 

JASON HIRSCHHORN: ¿Aquí mismo? 

AUDIENCIA: Haría new_node-> n igual valor. 

JASON HIRSCHHORN: Suena bien. Probablemente tiene sentido - no lo hacemos necesita saber lo que la lista que estamos en porque sólo estamos tratando con una sola lista. Por lo tanto una mejor declaración de la función de esto es sólo para deshacerse de este por completo y sólo tiene que insertar un valor en la cabeza. Ni siquiera necesitamos saber lo lista que estamos metidos Pero voy a mantener todo por ahora y luego cambiar a la actualización las diapositivas y código. Así que se ve bien, por ahora. Si el valor - que puede hacer esta línea? Si - ¿qué hacemos aquí, Noah. 

AUDIENCIA: Si el valor es mayor de curr-> n - 

JASON HIRSCHHORN: ¿Cómo vamos al siguiente nodo? 

AUDIENCIA: Curr-> n es igual a new_node. 

JASON HIRSCHHORN: Entonces n es qué parte de la estructura? El número entero. Y new_node es un puntero a un nodo. Entonces, ¿qué parte de curr debemos actualizar? Si no es n, entonces ¿cuál es la otra parte? Noé, ¿cuál es la otra parte. 

AUDIENCIA: Oh, la próxima. 

JASON HIRSCHHORN: A continuación, exactamente. Exactamente. Siguiente es la correcta. Y lo que más necesitamos actualizar, Noah? 

AUDIENCIA: Los punteros. 

JASON HIRSCHHORN: Así actualizamos actual. 

AUDIENCIA: Anterior-> siguiente. 

JASON HIRSCHHORN: Si. Bien, vamos a hacer una pausa. ¿Quién nos puede ayudar? Manu, ¿qué debemos hacer? 

AUDIENCIA: Hay que establecer es igual a curr-> siguiente. Pero hacer eso antes de la línea anterior. 

JASON HIRSCHHORN: OK. ¿Algo más? Akshar. 

AUDIENCIA: Creo que no estás la intención de cambiar curr-> siguiente. Creo que estás destinado a hacer iguales curr curr-> siguiente para ir al siguiente nodo. 

JASON HIRSCHHORN: Lo siento, ¿dónde? ¿En qué línea? Esta línea? 

AUDIENCIA: Si. Hacer curr equivale curr-> siguiente. 

JASON HIRSCHHORN: Así que eso es correcto porque la corriente es una puntero a un nodo. Y queremos que apunte a la siguiente nodo de lo que está recibiendo en la actualidad señalado. Curr en sí tiene un siguiente. Pero si tuviéramos que actualizar curr.next, nos sería la actualización de la nota real en sí, no donde esta puntero señalaba. ¿Qué pasa con esta línea, sin embargo. Avi? 

AUDIENCIA: Anterior-> siguiente es igual curr. 

JASON HIRSCHHORN: Así que de nuevo, en caso anterior es un puntero a un nodo, anterior-> siguiente es la puntero actual en el nodo. Así que esta sería la actualización de una puntero en un nodo para curr. No queremos poner al día un puntero en un nodo. Queremos poner al día anterior. Entonces, ¿cómo hacemos eso? 

AUDIENCIA: Sólo se prev. 

JASON HIRSCHHORN: Así es. Anterior es un puntero a un nodo. Ahora vamos a cambiar a un nuevo puntero a un nodo. Aceptar Movámonos hacia abajo. Finalmente, esta última condición. Jeff, ¿qué hacemos aquí? 

AUDIENCIA: Si el valor es igual a curr-> n. 

JASON HIRSCHHORN: Lo siento. ¡Oh Dios mío. ¿Qué? Valor == curr-> n. ¿Qué hacemos? 

AUDIENCIA: Usted sería liberar a nuestros new_node, y luego te volverías falsa. 

JASON HIRSCHHORN: Esto es lo que que hemos escrito hasta ahora. ¿Alguien tiene algo añadir antes de que hagamos? Aceptar. Vamos a intentarlo. El control puede llegar a la final de una función no nula. Avi, ¿qué está pasando? 

AUDIENCIA: ¿Se supone que poner de retorno cierto fuera del bucle while? 

JASON HIRSCHHORN: No sé. ¿Me quieres? 

AUDIENCIA: No importa. No. 

JASON HIRSCHHORN: Akshar? 

AUDIENCIA: Creo que la intención de poner return false al final del bucle while. 

JASON HIRSCHHORN: Entonces, ¿dónde Qué quieres que vaya? 

AUDIENCIA: Al igual que fuera del bucle while. Así que si sale del bucle while que los medios que ha llegado al final y no ha pasado nada. 

JASON HIRSCHHORN: OK. Así que, ¿qué hacemos aquí? 

AUDIENCIA: Usted vuelve falsa allí también. 

JASON HIRSCHHORN: Oh, hacerlo en ambos lugares? 

AUDIENCIA: Si. 

JASON HIRSCHHORN: OK. ¿Hay que ir? ¡Oh Dios mío. Lo siento. Pido disculpas por la pantalla. Es un poco flipando en nosotros. Así que debes elegir una opción. Cero, por el código, se cierra el programa. Uno inserta algo. Vamos a insertar tres. El inserto no tuvo éxito. Voy a imprimir. Yo no tengo nada. Aceptar. Tal vez eso era sólo una casualidad. Inserte uno. No éxito. Aceptar. Vamos a ejecutar a través de GDB muy rápido para comprobar lo que está pasando. 

Recuerde gdb. / El nombre de su programa nos mete en el BGF. ¿Es que una gran cantidad de manejar? El intermitente? Probablemente. Cierra los ojos y tomar un poco de profundidad respiraciones si te cansas de ver las cosas. Estoy en el BGF. ¿Qué es lo primero que hago en GDB? Tenemos que averiguar ¿qué está pasando aquí. Vamos a ver. Tenemos seis minutos de la figura lo que está pasando. Romper principal. Y entonces, ¿qué hago? Carlos? Ejecutar. Aceptar. Vamos a escoger una opción. ¿Y qué tiene N hacer? Siguiente. Sí. 

AUDIENCIA: ¿No lo dices - qué no me dijiste que la cabeza, que era inicializa en null al principio. Pero pensé que habías dicho que estaba bien. 

JASON HIRSCHHORN: Vamos - vamos a ver en GDB, y luego vamos a volver. Pero parece que usted ya tiene algunas ideas sobre lo que está pasando. Así que queremos insertar algo. Aceptar. Hemos insertar. Por favor ingrese un int. Nosotros insertaremos tres. Y entonces estoy en esta línea. ¿Cómo hago para iniciar la depuración la inserción de la función conocida? ¡Oh Dios mío. Eso es un montón. ¿Eso enloqueciendo mucho? 

AUDIENCIA: Oh, murió. 

JASON HIRSCHHORN: Acabo lo sacó. Aceptar. 

AUDIENCIA: Tal vez sea el otro extremo del cable. 

JASON HIRSCHHORN: Wow. Así que la conclusión - ¿qué le dijiste? 

AUDIENCIA: Dije que la ironía de la técnica dificultades en esta clase. 

JASON HIRSCHHORN: Lo sé. Si tan sólo tuviera el control sobre esa parte. [Inaudible] Eso suena muy bien. ¿Por qué no empezar a pensar en los chicos lo que podríamos haber hecho mal, y vamos a estar de vuelta en 90 segundos. 

Avica, voy a preguntarle cómo ir insert_node interior para depurarlo. Así que aquí es donde nos dejó la última vez. ¿Cómo me voy adentro insert_node, Avica, examinar lo que está pasando? ¿Qué comando GDB? Pausa no me llevaría en su interior. ¿Lo sabe Marquise? 

AUDIENCIA: ¿Qué? 

JASON HIRSCHHORN: ¿Qué comando GDB Yo uso para ir dentro de esta función? 

AUDIENCIA: Step? 

JASON HIRSCHHORN: Paso a través de S. Eso me lleva dentro. Aceptar. New_node mallocing algo de espacio. Todo eso parece que va. Vamos a examinar new_node. Se puso un poco de dirección de memoria. Vamos a ver - eso es todo lo correcto. Así que todo lo que aquí parece estar funcionando correctamente. 

AUDIENCIA: ¿Cuál es la diferencia entre P y la pantalla? 

JASON HIRSCHHORN: P corresponde a la impresión. Y por lo que se está preguntando cuál es la diferencia entre eso y esto? En este caso, nada. Pero generalmente hay algunas diferencias. Y usted debe buscar en el manual de GDB. Pero en este caso, nada. Tenemos la tendencia a utilizar la impresión, sin embargo, porque nosotros no tenemos que hacer mucho más que imprimir un solo valor. 

Aceptar. Así que estamos en la línea 80 de nuestro código, estableciendo nodo * curr igual a lista. Vamos a imprimimos curr. Es igual a la lista. Sweet. Espere. Es igual a algo. Eso no me parece correcto. Eso es. Es porque en GDB, bien, si que es la línea que está en él aún no se ha ejecutado. Así que hay que escribir en realidad siguiente para ejecutar la línea de antes de ver sus resultados. Así que aquí estamos. Simplemente ejecuta esta línea, anterior equivale a nula. Así que de nuevo, si imprimimos anterior no vamos a ver nada raro. Pero si realmente ejecutan a que línea, entonces veremos que esa línea funcionó. 

Así que tenemos curr. Esos son los dos buenos. ¿Cierto? Ahora estamos en esta línea aquí. Mientras curr no es igual a nulo. Bueno, lo que hace curr iguales? Acabamos de ver que igualó nulo. Imprimimos a cabo. Voy a imprimir hacia fuera otra vez. Así es que mientras que bucle va a ejecutar? 

AUDIENCIA: No. 

JASON HIRSCHHORN: Así que cuando he escrito que línea, verá que saltó todo el camino hasta la parte inferior, devolverá false. Y luego vamos a devolver false y volver a nuestro programa y finalmente, imprimir, como vimos, el inserto no tuvo éxito. Por lo tanto, nadie tiene alguna idea sobre lo que que tenemos que hacer para arreglar esto? Voy a esperar hasta que vea un par de manos suben. No ejecutamos esto. Tenga en cuenta que esta fue la primera Lo que estábamos haciendo. Yo no voy a hacer un par. Voy a hacer algunos. Debido a que un par significa dos. Voy a esperar por más de dos. 

La primera inserción, corr, por defecto es igual a nulo. Y este ciclo sólo se ejecuta si curr no es nulo. Entonces, ¿cómo puedo solucionar esto? Veo tres manos. Voy a esperar por más de tres. Marcus, ¿qué te parece? 

AUDIENCIA: Bueno, si usted lo necesita ejecutar más de una vez, sólo cambiarlo a un bucle do-while. 

JASON HIRSCHHORN: OK. ¿Será que resolver nuestro problema, sin embargo? 

AUDIENCIA: En este caso no, porque de el hecho de que la lista está vacía. Así que es probable que sólo necesita añadir una declaración de que si se sale del bucle entonces usted tiene que estar al final de la la lista, momento en el que usted sólo puede insertarlo. 

JASON HIRSCHHORN: eso me gusta. Eso tiene sentido. Si se sale del bucle - porque va a devolver false aquí. Así que si se sale del bucle, entonces estamos en Al final de la lista, o tal vez el inicio de una lista si no hay nada en , lo que es lo mismo que el final. Así que ahora queremos insertar algo aquí. Entonces, ¿cómo ese código mira, Marcus? 

AUDIENCIA: Si ya tienes el nodo malloced, usted podría decir new_node-> siguiente es igual a nula porque tiene que ser al final. O new_node-> siguiente es igual a nulo. 

JASON HIRSCHHORN: OK. Lo siento. New_node-> siguiente es igual a nula porque estamos en el final. Eso no lo puso pulg ¿Cómo nos ponemos en la lista? Derecha. Eso es sólo la creación es igual a. No, ¿cómo en realidad lo puso en la lista? Lo que apunta a la final de la lista? 

AUDIENCIA: Head. 

JASON HIRSCHHORN: ¿Lo sientes? 

AUDIENCIA: Head está apuntando al final de la lista. 

JASON HIRSCHHORN: Si no hay nada en la lista, la cabeza está apuntando a la final de la lista. Así que eso funcionará para la primera inserción. ¿Qué pasa si hay un par las cosas en la lista? Que no queremos establecer cabeza igual a new_node. ¿Qué es lo que queremos hacer allí? ¿Sí? Probablemente anterior. ¿Funcionará? Recordemos que anterior es sólo un puntero a un nodo. Y anterior es una variable local. Así que esta línea creará una variable local, anterior, igual o señalando a este nuevo nodo. Eso no va a poner realmente se en la lista, sin embargo. ¿Cómo nos ponemos en nuestra lista? Akchar? 

AUDIENCIA: Creo que hacer actual-> siguiente. 

JASON HIRSCHHORN: OK. curr-> siguiente. Así que de nuevo, la única razón por la que estamos abajo aquí es lo que hace de corriente igual? 

AUDIENCIA: igual a nulo. 

JASON HIRSCHHORN: Y así lo que pasa si lo hacemos nula-> next? ¿Qué va a conseguir? Conseguiremos un fallo de segmentación. 

AUDIENCIA: Do curr equivale a nula. 

JASON HIRSCHHORN: Eso es lo mismo como anterior, sin embargo, porque no hay una variable local que estamos estableciendo igual a este nuevo nodo. Volvamos a nuestra imagen de insertar algo. Digamos que estamos insertando al final de la lista, por lo que aquí. Tenemos un puntero actual que es apuntando a null y un punto anterior eso apunta a 8. Entonces, ¿qué tenemos que actualizar, Avi? 

AUDIENCIA: Anterior-> siguiente? 

JASON HIRSCHHORN: Anterior-> siguiente es lo que queremos poner al día a causa de que en realidad se inserta en el final de la lista. Todavía tenemos un bicho, sin embargo, que vamos a ejecutar en. ¿Qué es ese bicho? ¿Sí? 

AUDIENCIA: Se va a volver falsa en este caso? 

JASON HIRSCHHORN: Oh, es que se va a devolver false. Pero hay otro bug. Así que tendremos que poner a cambio verdadero. 

AUDIENCIA: Lo anterior sigue igual nulo en la parte superior de la lista? 

JASON HIRSCHHORN: Todavía Así anterior es igual a nulo desde el principio. Entonces, ¿cómo podemos superar eso? ¿Sí? 

AUDIENCIA: Creo que se puede hacer una verificación antes de que el bucle while para ver si es una lista vacía. 

JASON HIRSCHHORN: OK. Así que vamos a ir aquí. Haga una revisión. Si - 

AUDIENCIA: Así que si la cabeza es igual a es igual a nulo. 

JASON HIRSCHHORN: Si la cabeza es igual a es igual a nula - que nos dirá si se trata de una lista vacía. 

AUDIENCIA: Y entonces usted hacer la cabeza es igual a nuevo. 

JASON HIRSCHHORN: Head iguales new_node? Y ¿qué más tenemos que hacer? 

AUDIENCIA: Y luego puede volver realidad. 

JASON HIRSCHHORN: No del todo. Nos falta un paso. 

AUDIENCIA: New_node siguiente tiene que apuntar a null. 

JASON HIRSCHHORN: Exactamente, Alden. Y entonces podemos devolver true. Aceptar. Pero sigue siendo una buena idea de hacer las cosas al final de la lista, ¿no? Está bien. Todavía podríamos conseguir realmente al final de la lista. Así es este código bien si estamos en el final de la lista y hay algunos las cosas en la lista? ¿Cierto? Debido a que todavía tenemos idea de Marcus. Podemos salir de este bucle, porque estamos en el final de la lista. Entonces, ¿todavía queremos este código aquí abajo? 

AUDIENCIA: Si. 

JASON HIRSCHHORN: Si. Y ¿qué es lo que tenemos que cambiar esto? Verdadero. ¿Suena bien a todo el mundo hasta el momento? ¿Alguien tiene alguna - Avi, ¿tienes algo que añadir? 

AUDIENCIA: No. 

JASON HIRSCHHORN: OK. Así que hemos hecho un par de cambios. Hemos hecho esta comprobación antes de que fuimos para una lista vacía. Así que nos hemos ocupado de una lista vacía. Y aquí nos ocupamos de la inserción algo al final de la lista. Así que parece que esta toma de bucle while cuidado de las cosas en el medio, en algún lugar de la lista si hay son las cosas en la lista. 

Aceptar. Corramos este programa de nuevo. No éxito. 

AUDIENCIA: Usted no lo hacen. 

JASON HIRSCHHORN: Oh, Yo no lo hice. Buen punto, Michael. Vamos a añadir una marca vinculada. Línea 87 hay un error. Línea 87. Alden, esta fue la línea que me diste. ¿Qué pasa? 

AUDIENCIA: Tiene que ser null. 

JASON HIRSCHHORN: Excelente. Exactamente derecha. Debe ser nulo. Vamos a hacer de nuevo. Compilar. Aceptar. Vamos a insertar tres. El inserto fue exitosa. Vamos a imprimir hacia fuera. Oh, si tan sólo pudiéramos comprobar. Pero no hemos hecho lo imprimir función todavía. Nos adentraremos en otra cosa. ¿Qué debemos entrar? 

AUDIENCIA: Siete. 

JASON HIRSCHHORN: Seven? 

AUDIENCIA: Si. 

JASON HIRSCHHORN: Tenemos una falla seg. Así que nos dieron una, pero claramente no puede conseguir dos. Es 05:07. Así que podemos depurar este durante tres minutos. Pero yo voy a dejarnos aquí y pasar a tablas hash. Pero, de nuevo, las respuestas de este código Voy a enviar por correo electrónico a usted en un momento. Estamos muy cerca de ella. Yo le animo a descubrir ¿qué está pasando aquí y arreglarlo. Así que voy a por correo electrónico este código como así más la solución - probablemente la solución más adelante. En primer lugar este código. 

La otra cosa que quiero hacer antes de que final es que no hemos liberado a nada. Así que quiero que le muestre lo valgrind parece. Si corremos límites valgrind en nuestro programa. / enlazado. Una vez más, de acuerdo con esta diapositiva, nos debe ejecutar valgrind con algún tipo de opción, en este caso - Fuga-check = full. Así que vamos a escribir valgrind - Fuga-check = full. Así que esto va a funcionar valgrind en nuestro programa. Y ahora el programa realmente funciona. Así que vamos a ejecutarlo como antes, poner algo pulg Me voy a poner en tres. Eso funciona. No voy a tratar de poner en algo más porque vamos a conseguir un falso seg en ese caso. Así que sólo voy a dejar de fumar. 

Y ahora que se ve aquí abajo fugas y resumen montón. Estas son las cosas buenas que desea revisar. Así que el resumen del montón - dice, en uso en la salida - ocho bytes en un bloque. Ese bloque es el nodo que malloced. Michael, dijo antes de un nodo es de ocho picaduras porque tiene el número entero y el puntero. Así que ese es nuestro nodo. Y luego dice que usamos malloc siete veces y nos liberamos algo en seis ocasiones. Pero nunca se llama libre, así que no tengo idea de lo que está hablando. 

Pero baste decir que cuando su programa se ejecuta, malloc se está llamando en algunos otros lugares que no es necesario preocuparse. Así malloc probablemente fue llamado en algunos lugares. Nosotros no tenemos que preocuparnos dónde. Pero esto es realmente nosotros. Esta primera línea es nosotros. Salimos de ese bloque. Y se puede ver que aquí en el resumen de fugas. Aún alcanzable - ocho bytes en un bloque. Eso significa que la memoria - hemos escapado ese recuerdo. Definitivamente perdido - algo se pierde para siempre. En general, no lo harás ver nada allí. Todavía puede llegar es generalmente donde verás las cosas, donde querrá que mirar para ver qué código debe usted se han liberado pero se olvidó de liberar. 

Y luego, si este no era el caso, si lo hiciéramos todo gratis, podemos comprobar eso. Vamos a ejecutar el programa no poner en cualquier cosa. Usted verá aquí en uso en la salida - cero bytes en cero bloques. Eso significa que ya no tenía nada cuando este programa se cierra. Así que antes de dar vuelta en pset6, valgrind ejecutar y asegúrese de que usted no tiene cualquier pérdidas de memoria en su programa. Si usted tiene alguna pregunta con valgrind, no dude en acercarse. Pero esto es cómo lo usa. Muy sencillo - si usted tener en uso en la salida - cualquier byte en cualquier bloque. 

Así que estábamos trabajando en el nodo de inserción. Tenía otras dos funciones aquí - imprimir los nodos y los nodos libres. Una vez más, se trata de funciones que son va a ser bueno para que practiques ya que le ayudará no sólo con estos ejercicios de muestra, sino también en el conjunto de problemas. Se corresponden en muy de cerca a las cosas usted va a tener que hacer en el establece problema. Pero yo quiero estar seguro Tocamos todo. Y las tablas hash también son cruciales para lo que estamos haciendo en la sección de este semana - o en el conjunto de problemas. 

Así que vamos a terminar la sección hablando de las tablas hash. Si usted nota que hice una pequeña tabla hash. Eso no es lo que estamos hablando sobre, sin embargo. Estamos hablando de un diferente tipo de tablas hash. Y en el fondo, una tabla hash no es más que una gama más una función hash. Vamos a hablar un poco sólo para asegúrese de que todo el mundo entiende lo que es un función hash es. Y te estoy diciendo ahora que es nada más que dos cosas - una matriz y una función hash. Y estos son los pasos a través de que esta opera. 

Ahí está nuestra matriz. Ahí está nuestra función. En particular, las funciones de hash necesitan hacer un par de cosas con esto. Voy a hablar específicamente acerca establece este problema. Probablemente va a tomar en una cadena. Y ¿qué va a volver? ¿Qué tipo de datos? Alden? Devuelva su función hash? Un entero. Así que esto es lo que el hash tabla consta de - una mesa en forma de matriz y una función de hash. ¿Cómo funciona? Funciona en tres pasos. Le damos una clave. En este caso, vamos a darle una cadena. Llamamos a la función hash por el paso uno en la llave y obtenemos un valor. 

En concreto, vamos a decir obtenemos un número entero. Ese número entero, no son muy específicos límites a lo que puede ser entero. En este ejemplo, nuestra matriz es de tamaño tres. Entonces, ¿qué números puede ser ese entero. ¿Cuál es el rango de valores válidos para ese entero, el tipo de retorno de esta función hash? Cero, uno y dos. El punto de la función hash es averiguar el lugar de la matriz donde la llave va. Sólo hay tres posibles lugares aquí - cero, uno, o dos. Así que esta función mejor retorno cero, uno, o dos. Algunos indice válida en este array. 

Y a continuación, dependiendo de donde vuelve, se puede ver que hay antena abierta entre paréntesis el valor. Ahí es donde ponemos la clave. Así que tiramos a la calabaza, salgamos cero. En conjunto soporte 0, ponemos calabaza. Nos tiramos en los gatos, tenemos a uno. Ponemos en un gato. Ponemos en araña. Salimos dos. Ponemos araña en conjunto soporte de dos. Sería muy bueno si funcionó de esa manera. Pero, por desgracia, como veremos, que es un poco más complicado. 

Antes de llegar allí, cualquier pregunta sobre este básico puesta a punto de una tabla hash? Esta es una imagen de exactamente lo que dibujamos en el tablero. Pero ya lo dibujamos en el tablero, me No voy a entrar en ella aún más. Esencialmente, las llaves, el cuadro negro de magia - o en este caso, la caja verde azulado - de un función hash los pone en cubos. Y en este ejemplo estamos no poner el nombre. Estamos poniendo el teléfono asociado número del nombre en el cubo. Pero muy bien podría simplemente poner el nombre en el cubo. 

Esto es sólo una imagen de lo que dibujamos en el tablero. Tenemos dificultades potenciales, sin embargo. Y hay dos en particular Las diapositivas que quiero ir. La primera de ellas es de aproximadamente una función hash. Así que hice la pregunta, ¿qué hace una buena función hash? Le doy dos respuestas. La primera es que es determinista. En el contexto de las funciones de hash, ¿qué significa esto? ¿Sí? 

AUDIENCIA: Puede encontrar el índice constante de tiempo? 

JASON HIRSCHHORN: Que no es lo que significa. Pero eso es una buena suposición. ¿Alguien más tiene una conjetura a lo que esto significa? Que una buena función hash es determinista? Annie? 

AUDIENCIA: Que una tecla sólo se puede asignar a un lugar en la tabla hash. 

JASON HIRSCHHORN: Eso es exactamente correcto. Cada vez que usted pone en la calabaza, siempre devuelve cero. Si usted pone en la calabaza y el hachís la función devuelve cero, pero tiene un probabilidad de volver algo más mayor que cero - así que tal vez puede devolver uno a veces o otras dos veces - eso no es una buena función hash. Tienes toda la razón. Su función hash debe devolver el mismo número entero exacto, en este caso, por la misma cadena exacta. 

Tal vez devuelve el mismo número entero exacto para la misma cadena exacta independientemente de la capitalización. Pero en ese caso es todavía determinista porque varias cosas se asignan en el mismo valor. Eso está bien. Mientras que sólo hay una de salida para una entrada dada. 

Aceptar. La segunda cosa es que devuelve índices válidos. Trajimos hasta que antes. Esta función hash - oh boy - una función hash debe volver índices válidos. Así lo dicen - vamos a volver a este ejemplo. Mi función hash cuenta hasta las letras de la palabra. Esa es la función hash. Y vuelve ese entero. Así que si tengo la palabra A, es va a devolver uno. Y se va a poner una aquí. ¿Qué pasa si me pongo en la palabra murciélago? Se va a devolver tres. ¿A dónde va murciélago? 

No encaja. Pero tiene que ir a alguna parte. Este es mi tabla hash después de todo, y todo tiene que ir a alguna parte. Entonces, ¿dónde debe ir murciélago? ¿Alguna idea? Conjeturas? Las buenas conjeturas? 

AUDIENCIA: Zero. 

JASON HIRSCHHORN: ¿Por qué cero? 

AUDIENCIA: Porque tres modulo tres es igual a cero? 

JASON HIRSCHHORN: Triple módulo de tres es cero. Esa es una gran suposición, y eso es correcto. Así que en este caso se debe Probablemente vaya a cero. Así que una buena manera de asegurarse de que este hash función sólo devuelve índices válidos se al modulo que por el tamaño de la tabla. Si Modulo Sea lo vuelve por tres, siempre se va a conseguir algo entre cero, uno y dos. Y si esto siempre devuelve siete, y siempre Modulo por tres, eres siempre va a conseguir lo mismo. 

Por lo que es aún determinista si MODULO. Pero eso va a asegurar que usted nunca conseguir algo - una industria no válido. Generalmente, módulo que debería ocurrir dentro de su función de hash. Así que usted no tiene que preocuparse por esto. Sólo puede asegurarse de que este es un indice válida. ¿Tiene preguntas sobre este potencial escollo? 

Aceptar. Y ahí vamos. Siguiente error potencial y esta es la grande. ¿Qué pasa si dos claves mapa en el mismo valor? Así que hay dos maneras de manejar esto. La primera se llama lineal sondeo, que estoy No voy a ir otra vez. Pero usted debe estar familiarizado con la forma que funciona y lo que es eso. 

El segundo, voy a ir más ya que es el que muchos la gente probablemente va a terminar de decidir para usar en su conjunto de problemas. Por supuesto, usted no tiene que hacerlo. Sin embargo, para el conjunto de problemas, muchas personas tienden a optar por crear una tabla hash con encadenamiento separado para implementar su diccionario. Así que vamos a ir más de lo que significa para crear una tabla hash con encadenamiento separado. 

Así que me puse en calabaza. Devuelve cero. Y puse calabaza aquí. Entonces me puse en - lo que es otra cosa con temas de Halloween? 

AUDIENCIA: Candy. 

JASON HIRSCHHORN: caramelo! Eso es un gran uno. Puse en los dulces y caramelos También me da cero. ¿Qué hago? ¿Alguna idea? Debido a que toda la clase de sabe lo encadenamiento separado es. Así que cualquier idea de qué hacer? Sí. 

AUDIENCIA: Poner la cadena realidad en la tabla hash. 

JASON HIRSCHHORN: Así que vamos a dibujar la buena idea aquí. Aceptar. 

AUDIENCIA: Tener la tabla hash [Inaudible] el puntero que apunta a el principio de una lista. Y luego han calabaza ser el primer valor en esa lista y dulces vinculado ser el segundo valor en esa lista enlazada. 

JASON HIRSCHHORN: OK. Marcus, que era excepcional. Voy a romper eso. Marcus está diciendo que no sobrescribir calabaza. Eso sería malo. No poner el caramelo en otro lugar. Vamos a poner a ambos en cero. Pero vamos a hacer frente a poniéndolos a cero la creación de una lista en cero. Y vamos a crear una lista de todo lo que se asigna a cero. Y la mejor manera que hemos aprendido para crear una lista que puede crecer y encoger dinámica no está dentro otra matriz. Así que no es una matriz multi-dimensional. Pero basta con crear una lista enlazada. 

Así que lo que él propuso - Voy a conseguir un nuevo - es crear una matriz con punteros, una matriz de punteros. Aceptar. Cualquier idea o sugerencia de lo que el tipo de de estos indicadores debería ser? Marcus? 

AUDIENCIA: Punteros a - 

JASON HIRSCHHORN: Debido a que usted dijo una lista enlazada, así - 

AUDIENCIA: punteros de nodo? 

JASON HIRSCHHORN: Punteros de nodo. Si las cosas en nuestra vinculados lista de nodos son entonces debe ser punteros de nodo. ¿Y qué es lo que equivalen a un principio? 

AUDIENCIA: Nulo. 

JASON HIRSCHHORN: Nulo. Así que no es lo nuestro vacío. Vuelve calabaza cero. ¿Qué hacemos? Camina conmigo a través de él? En realidad, Marcus ya me dio. Alguien más me caminar a través de él. ¿Qué hacemos cuando - esto se ve muy similar a lo que estábamos haciendo. Avi. 

AUDIENCIA: Me voy a tomar una conjetura. Así que cuando usted consigue el caramelo. 

JASON HIRSCHHORN: Si. Bueno, tenemos calabaza. Vamos a nuestra primera. Tenemos calabaza. 

AUDIENCIA: OK. Vuelve calabaza cero. Así lo pones en eso. O en realidad, lo pones en la lista enlazada. 

JASON HIRSCHHORN: ¿Cómo lo puso en la lista enlazada? 

AUDIENCIA: ¡Oh, la sintaxis actual? 

JASON HIRSCHHORN: Sólo hay que pasar - decir más. ¿Qué hacemos? 

AUDIENCIA: Sólo hay que insertar como el primer nodo. 

JASON HIRSCHHORN: OK. Así que tenemos nuestro nodo, calabaza. Y ahora ¿cómo lo introduzco? 

AUDIENCIA: Usted asigna en el puntero. 

JASON HIRSCHHORN: ¿Qué puntero? 

AUDIENCIA: El indicador en cero. 

JASON HIRSCHHORN: Entonces, ¿dónde hace este punto? 

AUDIENCIA: Para nulo en estos momentos. 

JASON HIRSCHHORN: Bueno, está apuntando a null. Pero me voy a poner en la calabaza. Entonces, ¿dónde debería apuntar? 

AUDIENCIA: Para calabaza. 

JASON HIRSCHHORN: Para calabaza. Exactamente. Así que esto apunta a la calabaza. Y ¿de dónde viene este puntero en el punto de calabaza? A 

AUDIENCIA: Nulo. 

JASON HIRSCHHORN: null. Exactamente. Así que sólo nos insertamos algo a la lista enlazada. Acabamos de escribir el código para hacer esto. Casi casi nos lo completamente agrietado. Ahora insertamos el caramelo. Nuestro dulces también tiende a cero. Entonces, ¿qué hacemos con los dulces? 

AUDIENCIA: Depende de si No estamos tratando de resolverlo. 

JASON HIRSCHHORN: Eso es exactamente correcto. Depende de si es o no que estamos tratando de solucionar el problema. Vamos a suponer que no estamos va a solucionar el problema. 

AUDIENCIA: Pues bien, como hemos comentado antes, es más sencillo sólo para ponerlo desde el principio por lo que el puntero de cero puntos a los dulces. 

JASON HIRSCHHORN: OK. Espera. Déjame crear dulces aquí. Así que este puntero - 

AUDIENCIA: Sí, ahora debe apuntar a los dulces. Luego que el puntero de punto de caramelo para la calabaza. 

JASON HIRSCHHORN: ¿Así? Y decimos que tenemos otra cosa para asignar a cero? 

AUDIENCIA: Bueno, usted acaba de hacer lo mismo? 

JASON HIRSCHHORN: Hacer lo mismo. Así que en este caso, si no lo hacemos quieren mantener lo resuelto que Suena bastante simple. Tomamos el puntero en el indice dada por nuestra función hash. Tenemos que apuntan a nuestro nuevo nodo. Y entonces lo que estaba señalando previamente - en este caso nulo, en el segundo caso calabaza - que, sea lo que está señalando anteriormente, se añade en el siguiente de nuestro nuevo nodo. Estamos insertando algo en el comienzo. De hecho, esto es mucho más simple que tratando de mantener la lista ordenada. Pero, de nuevo, la búsqueda será más complicado aquí. Siempre tendremos que ir hasta el final. 

Aceptar. ¿Una pregunta sobre encadenamiento separado? ¿Cómo funciona? Por favor, pregunte ahora. Tengo muchas ganas de asegurarse de que todos los entender esto antes de que nos dirigimos. 

AUDIENCIA: ¿Por qué te pones de calabaza y los dulces en el mismo parte de la tabla hash? 

JASON HIRSCHHORN: Buena pregunta. ¿Por qué los ponemos en la misma parte de la tabla hash? Bueno, en este caso nuestra función hash devuelve cero para los dos. Así que tienen que ir en cero indice porque ahí es donde vamos a buscarlos si alguna vez querer mirar para arriba. Una vez más, con un enfoque de sondeo lineal nosotros no pondríamos a los dos al cero. Pero en el enfoque de la cadena independiente, nos vamos a poner a ambos en cero a continuación, crear una lista de cero. 

Y no queremos sobrescribir calabaza simplemente por eso, porque entonces vamos a asumir que la calabaza era nunca insertado. Si acabamos de tener una cosa en la ubicación que sería malo. Entonces no habría oportunidad de nosotros - si hemos tenido un duplicado, entonces sería simplemente borrar nuestro valor inicial. Así que por eso hacemos este enfoque. ¿O es por eso que elegimos - pero de nuevo, eligió el enfoque de encadenamiento separado, que hay muchos otros enfoques uno puede elegir. ¿Responde esto a su pregunta? 

Aceptar. Carlos. Sondeo lineal implicaría - si encontramos una colisión a cero, se vería en el punto siguiente para ver si que estaba abierto y lo puso allí. Y entonces nos miramos en el siguiente deporte y ver si estaba abierto y lo puso allí. Así nos encontramos con la siguiente disposición lugar abierto y lo puso allí. ¿Alguna otra pregunta? Sí, Avi. 

AUDIENCIA: Como seguimiento a eso, ¿qué quiere decir el próximo acto? En la tabla hash o en una lista enlazada. 

JASON HIRSCHHORN: Para lineal programación, no hay listas enlazadas. El siguiente punto en la tabla hash. 

AUDIENCIA: OK. Así que la tabla hash sería inicializado al tamaño - como el número de cadenas que estuviera insertando? 

JASON HIRSCHHORN: Lo harías quiero que sea muy grande. Sí. Aquí está una foto de lo que acaba de dibujar en el tablero. Una vez más, tenemos una colisión aquí. en 152. Y verás que hemos creado una lista enlazada fuera de ella. Una vez más, la tabla hash encadenamiento separado enfoque no es el que usted tienen que tomar para establecer los problemas seis, pero es una que mucha los estudiantes tienden a tomar. Así que en ese sentido, vamos a hablar brevemente antes de que nos dirigimos a cabo sobre el problema de las seis, y luego voy a compartir con ustedes una historia. Tenemos tres minutos. 

Problema seis set. Usted tiene cuatro funciones - carga, comprobar, el tamaño y descarga. Load - bueno, hemos estado yendo sobre carga en este momento. Dibujamos la carga en el tablero. E incluso nos empezamos a codificar una gran cantidad de insertar en una lista enlazada. Así que la carga no es mucho más que lo que hemos estado haciendo. 

Descubre que es una vez que haya algo cargado. Es el mismo proceso que este. Las mismas dos primeras partes donde usted lanza algo dentro de la función hash y obtener su valor. Pero ahora no estamos de insertarlo. Ahora estamos buscando. He escrito el código de ejemplo para encontrar algo en una lista enlazada. Os animo a practicar eso. Pero intuitivamente encontrar algo que se bastante similar a la inserción de algo. De hecho, nos hizo un dibujo de la búsqueda algo en una lista enlazada, moviéndose a través hasta que llegamos a la final. Y si llegamos a la final y no podía encuentra, entonces no está allí. Así que eso es cheque, esencialmente. 

Siguiente es el tamaño. Vamos a saltar tamaño. Finalmente has descargar. Unload es que no hemos elaborado en la pizarra o aún codificada. Pero me animo a probar a programarlo en nuestra muestra ejemplo de lista enlazada. Pero descargar intuitiva es similar a la libre - o que quiero decir es similar a comprobar. Excepto por el momento cada vez que usted va a través, no estas seleccionando a ver si usted tiene su valor allí. Pero usted está tomando ese nodo y liberándola, esencialmente. Eso es lo que descarga te pide que hagas. Todo lo libre que ha malloced. Así que vas a través de toda la lista de nuevo, pasando por todo el hash mesa de nuevo. Esta vez no marca para ver lo que hay allí. Sólo liberar lo que hay. 

Y finalmente tamaño. Tamaño debe ser implementado. Si no se implementa el tamaño - Voy a decirlo de esta manera. Si no se implementa tamaño exactamente una línea de código que incluye el volver declaración, usted es haciendo tamaño incorrectamente. Así que asegúrese de que el tamaño, para el diseño completo puntos, lo estás haciendo exactamente en un línea de código, incluyendo la sentencia return. 

Y no las maletas, sin embargo, Akchar. Eager Beaver. Quería dar las gracias chicos por venir a la sección. Tenga un feliz Halloween. Este es mi disfraz. Llevaré este jueves si te veo en horario de oficina. Y si eres curioso acerca un poco más fondo para este traje, se sienten libre de visitar la sección 2011 para una historia sobre por qué estoy vistiendo el traje de calabaza. Y es una historia triste. Así que asegúrese de que tiene algunos tejidos cercanos. Pero en eso, si usted tiene cualquier preguntas que me quedaré por aquí fuera después de la sección. Buena suerte en problema seises. Y como siempre, si tiene alguna preguntas, que me haga saber.