DAVID J. MALAN: Muy bien. Así que bienvenidos a la primera Postmortem CS50 para un concurso. Pensamos que habíamos inauguramos esta tradición este año. Y esta será una oportunidad caminar a través de la soluciones al concurso. Y vamos a acelerar o reducir la velocidad en base sobre los intereses de los que están aquí. 

Así que usted está probablemente aquí porque eres interesados ​​en cómo usted podría tener o debería haber respondido a algunas de estos problemas. Entonces, ¿por qué no echar un vistazo en esta sección primero? Por eso, conseguir cadenas. Esto le dio tres versiones diferentes de un programa que era, en última instancia, la intención de obtener una cadena de un usuario. Si es o no lo hizo fue izquierda a usted para determinar. 

Y nos preguntamos en la pregunta 0, supongamos que esa versión es 1 compilado y ejecutado. ¿Por qué podría segfault el programa? A primera vista, todas las sugerencias por qué? Sí. 

AUDIENCIA: Así que yo recuerdo haber visto esto en un ejemplo anterior de ver el char * s y viendo la exploración de las s y ver porque es un puntero, ¿cómo afectó lo que ha analizado en? ¿Es S o la dirección de s? 

DAVID J. MALAN: OK. Bueno. Así que, en última instancia, la fuente de cualquier problema presumiblemente va a reducir a esa variable s. Y es de hecho una variable. El tipo de datos de esta variable es char *, lo que significa que va a contener la dirección de un personaje. Y ahí está el discernimiento. Se va a contener la dirección de un carácter o, más en general, la dirección del primer carácter en todo un bloque de caracteres. 

Pero el problema es que s exploración, propósito en vida, se le da una dirección y se le dio un código de formato, como% s, leer una cadena en la parte de memoria en esa dirección. Pero debido a que no hay ningún signo igual antes que punto y coma en la primera línea de código, porque no lo hacemos realidad asignar cualquier memoria con malloc, ya que en realidad no asignar una matriz de un cierto tamaño, todo que está haciendo es leer el usuario de entrada de teclado en algún completa valor de la basura, que es en s por defecto. Así que las probabilidades son que van a segfault si que la dirección no sólo para pasar a ser un valor que se puede, de hecho, escribir. Tan mal no asignar tu recuerdo allí. 

Así que en la pregunta 1, preguntamos, supongamos que la versión 2 es compilado y ejecutado. ¿Por qué podría segfault este programa? Así que éste es menos buggy. Y no hay realmente sólo una manera obvia en el que puede desencadenar una violación de segmento aquí. Y esta es temática. Cada vez que estamos usando c en la memoria, lo que podrías hacer para inducir una violación de segmento con la versión 2? 

AUDIENCIA: Si utiliza esa entrada en una cadena que es más de 49 personajes. 

DAVID J. MALAN: Exactamente. Cada vez que vea algo de longitud fija cuando se trata de una matriz, su radar debe apagarse que esto podría ser problemático si usted no está marcando la límites de una matriz. Y ese es el problema aquí. Todavía estamos usando scanf. Todavía estamos utilizando% s, lo que significa tratar para leer una cadena del usuario. Eso va a ser leído en s, que, en este punto, que es efectivamente el dirección de un trozo de memoria o su equivalente. Es el nombre de un arreglo de personajes de la memoria. 

Pero exactamente eso, si usted lee una cadena eso es más de 49, 49 porque se necesita espacio para la barra invertida 0, usted va a desbordarse ese búfer. Y que podría tener suerte y ser capaz de escribir un carácter 51a, 52a, 53a. Pero en algún momento, el sistema operativo va a decir, no. Esto definitivamente no es la memoria se le permite tocar. Y el programa se va a segfault. 

Así que, la heurística debe ser cualquier tiempo tienes de longitud fija, tiene para asegurarse de que usted está comprobando la longitud de lo que sea que usted está tratando para leer en ella. 

AUDIENCIA: Así que para solucionar eso, usted podría han tenido una declaración de comprobar realmente es la mayor longitud que o menor que? 

DAVID J. MALAN: Por supuesto. Usted sólo tiene una condición que dice que, si el - o mejor dicho, que no necesariamente sabe con antelación el número de caracteres de la usuario va a escribir, porque usted tiene huevo y la gallina. No hasta que hayas leído con scanf Puede usted averiguar cuánto tiempo es. Pero en ese momento, ya es demasiado tarde, porque usted ya ha leído en algún bloque de memoria. Así como un aparte, los evita biblioteca CS50 este tema por completo, el recuerdo mediante el uso de fgetc. Y se lee un carácter a la vez, de puntillas a lo largo, sabiendo que no puede desbordar un personaje si usted lee uno a la vez. 

El problema es con el recuerdo getString es que tenemos que constantemente re-size que parte de la memoria, que es sólo un dolor. Es una gran cantidad de líneas de código para hacer eso. Así que otra posibilidad sería utilizar realmente un primo, por lo de hablar, de scanf. Hay variantes de muchos de estos funciones que realmente comprueban la La longitud del número de caracteres que se puede leer al máximo. Y se podría especificar, no leen más de 50 caracteres. Así que sería otro enfoque, pero menos complaciente de las entradas más grandes. 

Así que la pregunta 2 pregunta: supongamos que la versión 3 es compilado y ejecutado. ¿Por qué podría segfault ese programa? Así que éste es en realidad el mismo responder, aunque se ve un poco más lujoso. Estamos usando malloc, que se siente como nosotros mismos nos estamos dando más opciones. Y luego estamos liberando a que memoria al final. Todavía es sólo 50 bytes de memoria. Así que podríamos todavía tratar de leer en 51, 52, 1000 bytes. Va a segfault para exactamente la misma razón. 

Pero hay otra razón también. ¿Qué otra cosa podría malloc retorno además la dirección de un trozo de memoria? Se podría devolver null. Y porque no estamos comprobando que, podríamos estar haciendo algo estúpido por otra razón, y es que podríamos estar diciendo a scanf, leemos la entrada del usuario desde el teclado 0 en lugar, conocido como nulo. Y eso, también, definitivamente desencadenar una violación de segmento. Así que para el propósito de la prueba, lo haríamos aceptan ninguno de los como razón válida. Uno de ellos es idéntico. Uno de ellos es un poco más matizada. 

Por último, con respecto al programa de uso de la memoria, ¿cómo hacer la versión 2 y versión 3 diferencian? Así, por si sirve de algo, hemos visto una aparentemente interminable suministro de posible respuestas a esta. Y entre las respuestas de la gente, lo que fuimos esperando, pero aceptó otra cosas, era alguna mención de la hecho de que la versión 2 está utilizando la llamada pila. La versión 3 utiliza el montón. Y funcionalmente, esto en realidad no hacer todo lo que gran parte de la diferencia. Al final del día, todavía estamos sólo conseguir 50 bytes de memoria. 

Pero esa fue una de las respuestas posibles que estábamos buscando. Pero ya verás, a medida que sus pruebas de vuelta de la TFS, que hicimos aceptar otras discusiones sobre su usos dispares de memoria también. Pero la pila y el montón habría sido una respuesta fácil para ir con. ¿Alguna pregunta? Te doy Rob. 

ROB BOWDEN: Entonces el problema 4. Esto es en la que había que llenar en el número de bytes de todos estos diferentes tipos utilizados. Así que lo primero que vemos. Asumir una arquitectura de 32 bits, como este aparato CS50. Así que una de las cosas fundamentales acerca Arquitecturas de 32 bits, que nos dice exactamente lo grande que un puntero se va para estar en la arquitectura. 

Así que de inmediato, sabemos que cualquier puntero tipo es de 32-bits o 4 bytes. Así que buscando en esta mesa, un nodo * es un tipo de puntero. Eso va a ser de 4 bytes. Struct nodo *, eso es, literalmente, idéntica a la estrella de nodo. Así que va a ser de 4 bytes. Cadena, por lo que no se ve como un puntero todavía, pero el typedef, una cadena es sólo un char *, que es un tipo de puntero. Así que va a ser de 4 bytes. 

Así que estos tres son los 4 bytes. Ahora, el nodo y el estudiante son un poco más complicado. Así que buscando en el nodo y el estudiante, vemos nodo como un número entero y un puntero. Y el estudiante es de dos punteros dentro de ella. Así, al menos, para nuestro caso aquí, el camino que acabamos de calcular el tamaño de esta estructura se acaba de agregar a todo ese es el interior de la estructura. 

Así que para el nodo, tenemos un número entero, que es 4 bytes. Tenemos un puntero, que es de 4 bytes. Y así un nodo va para ocupar 8 bytes. Y lo mismo para los estudiantes, tenemos un puntero que es 4 bytes y otro puntero que es 4 bytes. Así que eso va a acabar siendo hasta 8 bytes. Así nodo y el estudiante son 8 bytes. Y estos tres son los 4 bytes. Preguntas sobre esto? Sí. 

AUDIENCIA: ¿Es que era una de 64 bits arquitectura, haría que duplicar todos ellos? 

ROB BOWDEN: No lo haría duplicar todos ellos. Así que la arquitectura de 64 bits, que, de nuevo, cambios que lo fundamental de que un puntero es ahora 64 bits. Sí. Así que un puntero es de 8 bytes. Así que estos que eran 4 bytes van a ser de 8 bytes. Un estudiante, que estaba a dos puntos, bueno, ahora que va a ser de 8 bytes, 8 bytes. Se va a hacer 16 bytes. 

Sin embargo, un nodo es todavía 4 bytes. Así que este puntero se va a ser de 8 bytes. Esto es de 4 bytes. Así, un nodo sólo se va a ser de 12 bytes. ¿Alguna otra pregunta sobre que uno? Así que la siguiente, estos son los códigos de estado HTTP. Y había que describir las circunstancias en virtud del cual éstos podrían ser devuelto a usted. un problema que he oído a algunos estudiantes tengo es que trataron de hacer la errores estar en el extremo del cliente. Así que cuando tratamos de hacer la solicitud al servidor, algo va mal de nuestra parte. Pero, en general, estos códigos son siendo devuelto por el servidor. Por lo que queremos averiguar lo que está pasando mal o bien en el servidor que hace que estas cosas sean devueltos. Así que ¿Por qué un servidor devuelve código de estado 200? ¿Alguna idea? 

Sí. Así que algo de éxito la solicitud pasó. Y son capaces de volver lo que me pediste. Así que todo estaba bien. ¿Qué hay de 302 encontrado? Sí. 

AUDIENCIA: El servidor estaba buscando por lo que solicitó. Pero no pudo encontrarlo. Así que hay un error. 

ROB BOWDEN: Así que el camarero fue en busca de lo que querías. Así que buscando aquí, 302 encontrados, que era capaz de encontrarlo. 

AUDIENCIA: Lo siento. Encontrado significa que lo encontré. Lo siento. 

ROB BOWDEN: So 302 Found. El servidor es capaz de encontrar lo que querías. 

AUDIENCIA: Pero no mostrarlo? 

ROB BOWDEN: La diferencia entre este 302 y 200 es que se sabe lo que quiere. Pero no es exactamente donde que le quería preguntar. Así que 302 es una redirección típico. Así que ha solicitado una página. Sabe, oh, quiero devolverte esto. Pero esto es a una dirección URL diferente. Así que bueno, en realidad se quiere que este. 

DAVID J. MALAN: Es una pieza que dijo que dimos ustedes una redirección función que utiliza la función de cabecera que, a su vez, imprimirse ubicación, colon, y luego la URL a la que desea rechazar el usuario. A pesar de que usted no vio 302 explícitamente allí, eso es lo que PHP mágicamente insertar como encabezado diciendo exactamente lo que dijo Rob allí - encontrado. Pero ve aquí en su lugar. 

ROB BOWDEN: OK. ¿Y qué hay 403 forbidden? 

AUDIENCIA: Creo que es que el servidor está diciendo básicamente que el cliente no pueden acceder a la página principal. 

ROB BOWDEN: Así que sí. Bueno, la respuesta típica que eran esperando que es algo así como, los archivos no se chmodded apropiadamente. Eso es probablemente bajo qué circunstancias que los viste. Pero hay una razón por la que el cliente podría ser el culpable aquí. De hecho, hay otro código de estado - 401. Así que estos son muy similares. 

401 es no autorizado. Y 403 está prohibido. Y así no autorizado exclusivamente conseguir si no estás registrado Pero accediendo podría significar que está autorizado. Pero si usted ya está conectado y usted aún no tienen permiso, también se puede obtener prohibido. Así que si estás conectado y no tiene permiso, prohibido también algo que se puede conseguir. 

DAVID J. MALAN: Y el mecanismo por el que estos problemas son generalmente resuelto en el servidor es a través de lo que mando? Chmod, si es, de hecho, un permisos emitir sobre el archivo o directorio. 

ROB BOWDEN: Entonces 404 no encontrado. Sí. Así que a diferencia de 302 en los que no era exactamente donde usted está pidiendo, pero sabe lo que usted quiere, esto, sólo tiene ni idea de lo que quieres. Y usted no está solicitando algo válido. 418 Soy una tetera y luego 500 servidor interno. ¿Entonces por qué te sacaste eso? 

Así segfault - Yo realmente no sé la clasificación estándar para este. Pero si su código PHP tenía algo malo en ello, en teoría, podría en realidad segfault, en cuyo caso, este Error 500 de servidor interno, algo que está mal con su servidor de configuración. O hay un error de sintaxis en el código PHP. O algo malo está pasando. 

DAVID J. MALAN: Vimos segfault entre las respuestas de algunas personas. Y técnicamente, podría suceder. Pero eso sería un PHP, el programa escrito por otras personas, en realidad segfaulted, que sólo si esas personas jodido y escribió código con errores en su intérprete lo haría PHP mismo segfault. Así que, aunque 500 es como una violación de segmento en el espíritu, que es casi siempre el resultado de un problema del archivo de configuración con su servidor web o, como dijo Rob, un error de sintaxis, como tú no la cerró una cotización. O usted perdió un punto y coma en algún sitio. 

AUDIENCIA: Así que para el conjunto de procesadores de traslado, me pensar cuando lo hice una vez que hace clic en el navegador, pero nada ocurrió, lo que llamaron la página en blanco. Pero fue debido al código. Creo que eso fue JavaScript, ¿verdad? 

ROB BOWDEN: Si. 

AUDIENCIA: ¡Ojalá error todavía subir? 

ROB BOWDEN: ¿Así que usted no ha recibido este error porque todo desde la perspectiva del servidor web estaba completamente bien. Pero usted solicitó index.html. Ha solicitado shuttle.js y service.js. Y fue capaz de regresar con éxito para que todas esas cosas - 200. Aceptar. Es sólo cuando el navegador intentó interpretar el código JavaScript que Es como, espera, esto no es error de JavaScript válida. ¿Alguna otra pregunta? Está bien. 

DAVID J. MALAN: Así que la próxima arriba era el número 11. Y 11 fue la más temible para un montón de gente. Así que la cosa más importante a tener en cuenta aquí era que esta era, de hecho, sobre una lista doblemente enlazada. Pero este no era el mismo que el año pasado problema lista doblemente enlazada, que no te dio la advertencia de que la lista podría, de hecho, ser sin clasificar. 

Así que el hecho de que la lista fue sin clasificar y el hecho de que esa palabra era Subrayado no estaba destinado a transmitir que esto es realmente una simplificación de lo contrario habría sido un problema más difícil y una más larga. Así, un error común aquí fue haber puesto solución del año pasado sobre su ser buscapersonas y luego sólo tienes que copiar ciegamente que a medida que la respuesta, que es el derecho responder a una pregunta diferente similares en espíritu. Pero las sutilezas aquí fueron los siguientes. 

Así que uno, hemos declarado y un nodo se define de la manera habitual aquí. Entonces definimos la lista de ser un mundial puntero inicializa en null. Entonces, aparentemente, hay dos funciones tenemos prototipos para aquí, insertar y quitar. Y luego tenemos un código de ejemplo aquí de hacer un montón de inserciones. Y entonces le pedimos que complete el aplicación de inserto a continuación en tales de manera que se inserta en la lista n en tiempo constante, también subrayó, incluso si ya están presentes. 

Así que la belleza de ser capaz de insertar en la constante de tiempo es que implica que usted tiene que insertar el nuevo nodo en el que? En la parte delantera. Así se elimina, por suerte, al menos uno de los casos que requerían incluso más líneas de código, como lo hizo el año pasado e incluso en la clase cuando hablado a través de este tipo de cosas con los humanos y con un poco de pseudo código verbal. Así que en la solución aquí, vamos a pasar por alto a la que acabamos de tener una visual en la pantalla. 

Nótese que estamos haciendo lo siguiente. Y también notar la otra simplificación era que, incluso si se trata de ya presente, por lo que este significa que incluso si el número ya está allí, usted puede basta con insertar a ciegas otra copia de la misma. Y eso, también, estaba destinado a ser un simplificación para que pudiera centrarse, en realidad, algunos de los más parte intelectualmente interesante y no sólo algunos comprobación de errores adicional dado el tiempo limitado. 

Así que en esta solución de la muestra, destinamos un puntero en la mano izquierda lado aquí a un nodo. Ahora, se dan cuenta de que el puntero, como Rob dijo, está a sólo 32 bits. Y que no contiene en realidad una dirección hasta que asignarle la dirección. Y lo hacemos de la mano derecha lado a través de malloc. Al igual que un buen ciudadano, comprobamos que malloc no es, de hecho, null, por lo que no creamos accidentalmente una violación de segmento aquí. Y cada vez que utiliza malloc en la vida, debe ser la comprobación de nulos, no sea usted tiene un error sutil. 

Luego inicializamos que nula por asignando n y el anterior y el siguiente. Y en este caso aquí, que inicializa anterior a nulo, porque esta nueva nodo va a ser el nuevo a partir de mi lista. Así que no va a haber nada antes de ella. Y quiero añadir esencialmente el lista existente al nuevo nodo entorno al lado igual a la lista en sí. Pero no he terminado todavía. Así que si la lista en sí ya existía, y había al menos un nodo ya en el lugar, si esta es la lista aquí y puedo insertar un nuevo nodo de aquí, que asegurarse de que mi ex nodo señala hacia atrás a mi nuevo nodo, porque este es, de nuevo, una lista doblemente enlazada. 

Así que hacemos una comprobación de validez. Si la lista no es nulo, si ya hay uno o más nodos de allí, y luego añadir que de nuevo referencia por así decirlo. Y luego la última cosa que necesitamos que hacer es en realidad la actualización del mundial propia lista de variables para señalar para que el nuevo nodo. Sí. 

AUDIENCIA: En la flecha de puntero [Inaudible] es igual a null, hace que ocuparse de la lista porque la lista es nulo? 

DAVID J. MALAN: Nope. Eso es simplemente que yo sea de forma proactiva cuidado, ya que si este es mi lista original con tal vez algunos más nodos por aquí y estoy insertando mi nodo nuevo por aquí, no va ser nada aquí. Y quiero capturar esa idea estableciendo anterior a nula en el nuevo nodo. Y, presumiblemente, si mi código es correcto y no hay otra forma de insertar nodos distintos de esta función, presumiblemente, incluso si ya tiene lista uno o más nodos en él, presumiblemente el lista, el primer nodo, tendría un puntero previo de null en sí. 

AUDIENCIA: Y sólo un seguimiento. La razón de poner puntero próximos iguales lista sea que estés haciendo el puntero antes mencionados de que está apuntando a la siguiente, supongo - Yo no - simplemente enumera? 

DAVID J. MALAN: Exactamente. Y así vamos realmente a considerar dos casos aquí realmente, a pesar de que la fin vamos a considerar que no es exactamente lo mismo que el código. Pero en un nivel alto, si esto representa la lista y esta es una de 32 bits puntero, el escenario más simple es que éste es nulo por defecto. Y supongamos que quiero insertar el número 50 era el primer número. Así que voy a seguir adelante y asignar un nodo, que se va a contener tres campos - n, anterior y próximo. 

Voy a poner el número 50 aquí, porque esto será n. Este será el próximo. Y esto será anterior. Y así, ¿qué debo hacer en este caso? Bueno, acabo de hacer la línea 1 aquí. Puntero n se hace n. Entonces yo digo, previa deben recibir nulo. Así que esto va a ser nulo. Entonces voy a decir a continuación se va a poner la lista. 

Y esto sólo funciona bien. Esta es nulo. Y lo que estoy diciendo, el nuevo nodo del lado campo debe conseguir lo que sea esto. Así que pone otra nula allí. Y luego la última cosa Lo que hago es comprobar aquí. Si la lista no es igual a null, pero es igual a null, por lo que nos saltamos por completo. Y así, todo lo que hago siguiente es la lista obtiene puntero, que resulta en pictóricamente una imagen así. Así que ese es uno de los escenarios. 

Y el que le preguntabas específicamente es una situación como ésta, donde ya tenemos una lista de un solo nodo. Y si vuelvo en el original planteamiento del problema, la próxima vamos a insertar por ejemplo es de 34, sólo por En aras de la discusión. Así que voy a simplemente convenientemente dibujar eso por aquí. Acabo malloced. Supongamos que estoy comprobando nulo. 

Ahora, yo voy a inicializar n a ser 34. Y esto será n. Este será el próximo. Y esto será anterior. Vamos a asegurarnos de que no lo hice conseguir esto al revés. Llega Anterior primero en la definición. Voy a corregir esto. Esta es anterior. Este es el siguiente. A pesar de que estos son idénticos, vamos a mantenerlo constante. 

Anterior. Este es el siguiente. Así que acabo de malloced mi nota, comprobado para null, asignado 34 en el nodo. Consigue Anterior nulo. Así que eso me da eso. Siguiente consigue lista. Así que la lista es la siguiente. Así que este es el mismo ahora que este dibujo flecha, de manera que apunten a uno en la misma. Y entonces yo estoy comprobando si la lista no es igual a nulo. Y no es este momento. Entonces me voy a hacer la lista anterior pone puntero. 

Así que la lista anterior se PTR. Así que esto tiene el efecto de poner una flecha gráfica aquí. Y eso está poniendo un poco ondulado, líneas. Y luego, por último, actualizo lista para apuntar a puntero. Así que ahora esto apunta a este chico. Y ahora, vamos a hacer una rápida comprobación de validez. 

Aquí está la lista, que es la variable global. El primer nodo es, de hecho, 34, porque Estoy siguiendo la flecha. Y eso es correcto porque quiero insertar al principio de la lista todos los nuevos nodos. Su siguiente campo me lleva a este tipo. Si sigo adelante, me golpeó siguiente es nulo. Así que no hay más lista. Si lo golpeo anterior, lo entiendo copia donde espero. 

Así que todavía hay algunos indicadores, obviamente, para manipular. Pero el hecho de que le dijeran que hacer esto en un tiempo constante que significa que sólo tener un número finito de cosas se le permite hacer. ¿Y cuál es ese número? Puede ser que sea un paso. Podría haber dos. Podría ser 1000 pasos. Pero es finita, lo que significa que no se puede haber algún tipo de bucle pasando aquí, no hay repetición, no hay bucles. Es sólo tiene que ser líneas codificadas de forma rígida de código que tenemos en esta muestra. 

Así que el siguiente problema 12 nos pidió que completar la implementación de remove a continuación de una manera tal que se elimina n de la lista en el tiempo lineal. Así que tienes un poco más margen de maniobra ahora. Usted puede asumir que n, si está presente en la lista, estará presente no más de una vez. Y eso también está destinado a ser un concurso basado- supuesto simplificador, por lo que si se encuentra el número 50 en alguna parte en la lista, no lo hace también tiene que preocuparse acerca de continuar iteración, buscando cada posible copia de 50, lo que acaba de delegar en alguna minucia en un tiempo limitado. 

Así que con remove, éste era sin duda más difícil y más código para escribir. Pero a primera vista, francamente, podría ser algo abrumador y como no hay manera de que usted podría tener llegar a un cuestionario. Pero si nos centramos en las etapas individuales, Esperemos que pronto te herirá de que cada una de estas persona pasos tiene sentido obvio en retrospectiva. Así que vamos a echar un vistazo. 

Así que primero, inicializamos puntero estar lista en sí. Porque quiero que el tiempo lineal, que los medios Voy a tener un poco de bucle. Y una forma común para repetir las nodos de una estructura de lista o cualquier tipo de la estructura iterativa es tomar un puntero a la parte frontal de los datos estructura y entonces simplemente comenzar a actualizar y caminar a tu manera a través de la estructura de datos. Así que voy a hacer exactamente eso. 

Mientras puntero, mi variable temporal, no es igual a nula, vamos a seguir adelante y comprobar. ¿Acaso tengo suerte? Es el campo n en el nodo que estoy actualmente mirando igual a la Número estoy buscando? Y si es así, vamos a hacer algo. Ahora, observe si esta condición rodea la totalidad siguientes líneas de código. Esto es lo único que me importa - la búsqueda de un número en cuestión. Así que no hay otra cosa, lo que simplifica cosas conceptualmente un poco. 

Pero ahora, me di cuenta, y usted podría tener sólo se dio cuenta de esto después de pensar a través de un poco, hay en realidad dos casos aquí. Uno de ellos es en el que el nodo está en el principio de la lista, que es un poco molesto, porque eso es un caso especial, ya que hay que hacer frente con esta cosa, que es la única anomalía. En el resto de la lista, que es la misma cosa. Hay un nodo anterior y siguiente nodo, el nodo anterior, siguiente nodo. Pero este tipo es un poco especial si está al principio. 

Así que si el puntero es igual a la lista en sí, por lo que si estoy en el comienzo de la lista y he encontrado n, necesito que hacer un par de cosas. Uno, tengo que cambiar la lista de apuntar al siguiente campo, 50. Así que supongo que estoy tratando para eliminar 34. Así que este tipo tiene que ir de distancia, en un momento. 

Así que voy a decir, la lista de consigue puntero siguiente. Bueno, esto es puntero. Siguiente señala hacia aquí. Así que esto está cambiando en esta flecha derecha ahora para que apunte a este tipo aquí. Ahora, recuerden, tenemos una variable temporal. Así que no hemos dejado huérfanos de cualquier nodo, porque también tengo este tipo en mi implementación de remove. Así que ahora, si la lista en sí no es nulo, Tengo que arreglar un poco de algo. 

Necesito ahora asegurarse de que esta flecha, que se apunta previamente 50-34, esto tiene que desaparecer, porque si yo estoy tratando de deshacerse de 34 años, 50 tenían mejor no mantiene ninguna tipo de referencia de nuevo a ella como la flecha sugirió. Así que acabo de hacer esta línea. Así que he terminado. Ese caso es en realidad bastante fácil. Cortar la cabeza de la lista es relativamente sencillo. 

Por desgracia, hay una bloque molesto más. Así que ahora, tengo que considerar el caso donde hay algo en el medio. Pero no es demasiado terrible, excepto para la sintaxis de esta manera. Así que si no estoy en el comienzo de la lista, estoy en algún lugar en el medio. Y esta línea aquí está diciendo, inicio en cualquier nodo estás. Ir al campo siguiente del nodo anterior y señalar que en el puntero. 

Vamos a hacer esto gráficamente. Eso se está complicando. Así que si tengo campos anteriores aquí - vamos a hacer esto - siguientes campos aquí. Voy a simplificar mis punteros en lugar de dibujar un montón de cosas de ida y vuelta que se entrecruzan entre sí. Y ahora, vamos a decir que es 1, 2, 3 por el bien de la discusión, incluso sin embargo, que no se alinea con el problema en cuestión. 

Así que aquí está mi lista enlazada. Estoy tratando de quitar las dos de esta versión particular de la historia. Así que he actualizado puntero a apuntar a este tipo. Así que esto es PTR. El señala aquí. Esta es la lista, que existe a nivel mundial, como antes. Y él está señalando aquí no importa qué. Y ahora, estoy tratando de eliminar dos. 

Así que si el puntero está señalando aquí, estoy va a seguir, al parecer, el puntero anterior, lo que me pone en 1. Entonces yo voy a decir que la próxima campo, lo que me lleva a esta caja aquí, va a igual puntero siguiente. Así que si este puntero, esto es el siguiente. Eso significa que esta flecha necesidades para que apunte a este chico. 

Así que lo que esa línea de código tiene sólo hacer es un poco de esto. Y ahora, este es el aspecto de un paso en la dirección correcta. Esencialmente queremos cortar 2 de la media de 1 y 3. Así que tiene sentido que queremos ruta este puntero a su alrededor. Así que esta línea siguiente es comprobar si el puntero siguiente no es nulo, no hay de hecho alguien a la derecha de 2, que significa que también tenemos que hacer un pequeño corte aquí. 

Así que ahora tengo que seguir este puntero y actualizar el puntero anterior sobre este tipo para hacer un poco de un solucionar aquí el punto aquí. Y ahora, esto es visualmente agradable. Es un poco desordenado en que hay nadie apuntando a la 2 más. 2 esté apuntando hacia la izquierda. Y 2 está apuntando a la derecha. Pero él puede hacer lo que quiera, porque él está a punto de ser liberado. Y no importa lo que esos valores son más. 

Lo que es importante es que el restante chicos están encaminando arriba y por debajo de él ahora. Y de hecho, eso es lo que hacemos ahora. Nos puntero libre, lo que significa que le decimos al sistema operativo, son bienvenidos para reclamar esto. Y luego, por último, volvemos. Else implícitamente, si aún no han regresado, tenemos que seguir buscando. Así puntero es igual puntero siguiente sólo significa mover este tipo aquí. Mueva este tipo aquí. Mueva este tipo aquí si, de hecho, no encontramos el número estamos buscando todavía. 

Así que, francamente, se ve completamente abrumadora, creo, en un primer momento vista, sobre todo si usted luchó con esto durante la prueba y luego ver algo como esto. Y usted palmadita en la espalda. Bueno, no hay manera de que pudiera tener llegar a eso en el cuestionario. Pero yo diría, se puede hacer si se rompe hacia abajo en estos individuo casos y sólo a pie a través de él con cuidado, aunque, es cierto, en virtud de circunstancias estresantes. 

Afortunadamente, el panorama hizo todo lo más feliz. Usted puede dibujar esto en cualquier número de maneras. Usted no tiene que hacer el entrecruzamiento cosa aquí. Usted puede hacerlo con recta líneas les gusta esto. Pero la esencia de este problema, en en general, fue darse cuenta de que la derechos en la final debe ser un poco algo como esto, porque constante de tiempo a entender que sigues jamming y se obstruye y se obstruye el nuevos nodos al principio de la lista. ¿Alguna pregunta? Probablemente el más difícil de sin duda las preguntas de codificación. 

AUDIENCIA: Así que es similar a la lista la cabeza en los ejemplos anteriores. 

DAVID J. MALAN: Exactamente, exactamente. Sólo un nombre diferente para una variable global. En todo el mundo, ¿qué? 

ROB BOWDEN: OK. Así que esta es una de las que tenía que escribir el párrafo. Algunas personas escribieron ensayos para esta pregunta. Pero sólo tiene que utilizar estos seis términos para describir lo que sucede cuando intenta contactar facebook.com. Así que voy a hablar a través del proceso utilizando todos estos términos. Así que en nuestro navegador, tecleamos facebook.com y pulse Enter. Así que nuestro navegador se va a construir un HTTP solicitan que se va a enviar a través de algún proceso de Facebook para Facebook nos responda con la HTML de su página. 

Entonces, ¿cuál es el proceso por el que la solicitud HTTP en realidad llega a Facebook? Así que, primero, tenemos que traducir Facebook.com. Así que le dio el nombre Facebook.com, donde realmente hace la petición HTTP que tenga que ir? Así que tenemos que traducir Facebook.com a una dirección IP, que únicamente identifica qué máquina en realidad desea enviar esta solicitud a. Su ordenador portátil dispone de una dirección IP. Cualquier cosa conectada con el Internet tiene una dirección IP. 

Así DNS, Domain Name System, que es lo que va a manejar la traducción desde facebook.com a una dirección IP que que realmente desea ponerse en contacto. Así que entramos en contacto con los servidores DNS y por ejemplo, ¿cuál es facebook.com? Se dice, oh, es la dirección IP 190.212 algo, algo, algo. Está bien. Ahora, sé qué máquina Quiero contactar. 

Así que usted envía su solicitud HTTP a esa máquina. Entonces, ¿cómo llegar a esa máquina? Bueno, la solicitud va desde router para rebotar router. Recuerde el ejemplo de la clase, donde que de hecho vimos la ruta que el paquetes tomaron cuando intentamos para comunicarse. Lo vimos saltar sobre el Atlántico Océano en un momento dado o lo que sea. 

Así que el último puerto plazo. Así que esto es ahora en tu ordenador. Puede tener varias cosas en la actualidad comunicarse con la Internet. Así que puedo estar corriendo, por ejemplo, Skype. Puede que tenga un navegador web de código abierto. Puede que tenga algo que torrenting archivos. Así que todas estas cosas son la comunicación con el Internet de alguna forma. 

Así que cuando el equipo recibe algunos datos de Internet, ¿cómo lo hace saber qué aplicaciones realmente quiere los datos? ¿Cómo sabe si este particular, datos es para el torrenting aplicación en oposición al navegador web? Así que este es el propósito de los puertos en que todas estas aplicaciones tienen reclamó un puerto USB del ordenador. Así que su navegador web dice, hey, Estoy escuchando en el puerto 1000. Y su programa torrenting está diciendo, Estoy escuchando en el puerto 3000. Y Skype dice, estoy usando el puerto 4000. 

Así que cuando usted consigue algunos datos que pertenece a una de estas aplicaciones, los datos está marcado con el puerto que en realidad deben ser enviados a lo largo de. Así que esto dice, oh, yo pertenezco al puerto 1000. Sé que entonces tengo que enviar este junto a mi navegador web. Así que la razón es pertinente en este caso es que los servidores web tienden a escuchar en el puerto 80. Así que cuando me pongo en contacto Facebook.com, estoy la comunicación con un poco de máquina. Pero tengo que decir que el puerto de esa máquina que quiero comunicar. Y los servidores web tienden a ser escuchando en el puerto 80. 

Si quisieran, podrían ponerlo de modo que las listas como en el puerto 7000. Y luego, en un navegador web, lo que pude escribir manualmente Facebook.com: 7000 enviar la solicitud al puerto 7000 del servidor web de Facebook. 

David J. MALAN: Y en este caso, incluso aunque no requerimos que las personas mencionar esto, en este caso, lo que el puerto sería la solicitud en realidad ir a? Inténtelo de nuevo. Exactamente. No busco eso, sino que una sutileza eso es no ninguna, la última. 

ROB BOWDEN: Así que el HTTPS, ya que es escuchar específicamente para el cifrada, es en el puerto 4430. 

Audiencia: Y los correos electrónicos son 25, ¿verdad? 

DAVID J. MALAN: Saliente correos electrónicos, 25, sí. 

ROB BOWDEN: Yo ni siquiera conozco a la mayoría de el - todos los inferiores tienden a ser reservado para las cosas. Creo que todo bajo 1024 está reservado. 

AUDIENCIA: ¿Por qué dijiste 3 era un número equivocado? 

ROB BOWDEN: Porque en una dirección IP, hay cuatro grupos de dígitos. Y son de 0 a 255. Así que 192.168.2.1 es un común dirección IP de la red local. Observe todos los que están a menos de 255. Así que cuando empecé con 300, que no podría tener sido uno de los números. 

DAVID J. MALAN: Pero ese clip tonto de - era que CSI, donde tenían un número que era demasiado grande para la dirección IP. 

ROB BOWDEN: ¿Tiene preguntas sobre esto? El siguiente, el cambio tan completo en tema, pero tenemos este array PHP para las casas en el quad. Y tenemos una lista desordenada. Y queremos imprimir cada elemento de la lista sólo contiene el nombre de la casa. Así que tenemos un bucle foreach. Así que recuerda, la sintaxis es foreach matriz como elemento de la matriz. Así que a través de cada iteración del bucle, casa va a tomar uno de los valores dentro de la matriz. 

En la primera iteración, casa será Cabot Casa. En una segunda iteración, la casa se ser Courier Casa y así sucesivamente. Así que para cada quad como la casa, estamos sólo va a imprimir - también podría haber hecho eco - el elemento de la lista y, a continuación el nombre de la casa y luego cerrar el elemento de la lista. Las llaves son opcionales aquí. 

Y luego también dijimos en la pregunta en sí, no olvide cerrar la desordenada lista de etiquetas. Así que necesitamos para salir del modo PHP con el fin de hacer esto. O podríamos haber hecho eco de la cerrar desordenada lista de etiquetas. 

DAVID J. MALAN: También haría bien aquí han sido la utilización de una vieja escuela de bucle con un $ i = 0 0 y el uso de los recuentos de averiguar la longitud del rayo. Es el peor también, sólo un poco más prolijo. 

AUDIENCIA: Así que si usted iba a [Inaudible], ¿lo haría - Me olvido de lo que el lazo [inaudible] es. ¿Te $ soporte quad i? 

DAVID J. MALAN: Exactamente. Sí, exactamente. 

ROB BOWDEN: ¿Algo más? 

DAVID J. MALAN: Muy bien. Las compensaciones. Así que había montones de respuestas posible para cada uno de estos. Estábamos realmente buscando por algo de peso para un lado positivo y un inconveniente. Y el número 16 pidió, validando los usuarios ' del lado del cliente de entrada, como con JavaScript en lugar de en el servidor, al igual que con PHP. ¿Cuál es una ventaja de haciendo del lado del cliente? 

Bueno, una de las cosas que hemos propuesto es que se reduce la latencia, ya que no tienen que molestarse en contacto con el servidor, que puede tardar unos milisegundos o incluso un par de segundos evitando que y sólo la validación de los usuarios de entrada del lado del cliente por desencadenando un controlador on-presentar y sólo la comprobación, hizo que escriba algo en el nombre? ¿Se escriben algo en dirección de correo electrónico? ¿Eligieron una residencia de el menú desplegable? 

Usted puede darles retroalimentación instantánea usando la computadora gigahertz o lo que tengan que eso es realidad en su escritorio. Así que es sólo un mejor usuario experimentar normalmente. Sin embargo, una desventaja de hacer del lado del cliente validación, si lo haces sin también hacer la validación en el servidor es que más cualquiera que venga de CS50 sabe que sólo se puede enviar cualquier dato que desee a un servidor de cualquier número de maneras. Francamente, en la mayoría de cualquier navegador, puede haga clic en torno a la configuración y justo desactivar JavaScript, lo que haría, por lo tanto, desactivar cualquier forma de la validación. 

Pero también puede ser que recordar que ni siquiera yo hizo algunas cosas arcanas en clase utilizando telnet y en realidad pretendiendo ser un navegador mediante el envío de Get peticiones a un servidor. Y eso ciertamente no es usando cualquiera de JavaScript. Eso sólo me escribir comandos en un teclado. Así que en realidad, cualquier programador en suficiente comodidad con la web y HTTP podría enviar todos los datos que él o ella quiere a un servidor sin validación. Y si su servidor no está también revisando, Por qué me dan un nombre, es esto en realidad una dirección de correo electrónico válida, hizo eligen una residencia de estudiantes, que podría terminar hasta la inserción falsa o simplemente datos en blanco en su base de datos, lo que probablemente No va a ser una buena cosa si que estaba asumiendo que estaba allí. 

Así que esta es una realidad molesta. Pero en, del lado del cliente en general validación es grande. Pero significa el doble de trabajo. Aunque sí existen diversos bibliotecas, bibliotecas de JavaScript para ejemplo, que hacer esto mucho, mucho menos de un dolor de cabeza. Y puede volver a utilizar parte del código del lado del servidor, del lado del cliente. Pero no se dan cuenta de que es típicamente trabajo adicional. Sí. 

AUDIENCIA: Así que si sólo dicho menos seguro - 

DAVID J. MALAN: [Risas] Ugh. Esos son siempre más difícil queridos para adjudicar. 

ROB BOWDEN: Eso haría han sido aceptados. 

DAVID J. MALAN: ¿Qué? 

ROB BOWDEN: he creado este problema. Eso hubiera sido aceptada. 

DAVID J. MALAN: Si. 

AUDIENCIA: Cool. 

ROB BOWDEN: Pero nosotros no aceptamos para el primero - así, lo que estábamos buscando es algo así como que no tiene que comunicarse con el servidor. No aceptamos sólo más rápido. 

AUDIENCIA: ¿Qué pasa con No volver a cargar la página? 

ROB BOWDEN: Si. Esa fue una respuesta aceptada. 

DAVID J. MALAN: Cualquier cosa donde nos sentimos que era más probable que no probable que sabías lo que estabas diciendo que es un duro línea para dibujar a veces. El uso de una lista enlazada lugar de una matriz para mantener un lista de enteros ordenados. Así que un revés que a menudo citamos con vinculadas listas que motivaron su totalidad introducción fue a obtener dinamismo. Pueden crecer. Pueden encogerse. Así que usted no tiene que pasar por el aro para crear en realidad más de memoria con una matriz. O usted no tiene que sólo decir, lo siento, usuario. La matriz se llena. Así que el crecimiento dinámico de la lista. Una desventaja sin embargo de las listas enlazadas? 

AUDIENCIA: Es lineal. Busca en lista enlazada es lineal en lugar de lo que inicie sesión 

DAVID J. MALAN: Exactamente. Buscando en una lista enlazada es lineal, incluso si es ordenada, porque se puede Sólo sigue estos migas de pan, estos punteros, desde el principio de la lista hasta el final. No se puede aprovechar el acceso y al azar, por lo tanto, la búsqueda binaria, aunque sea ordenada, que podría ver con una matriz. Y también hay otro costo. Sí. 

AUDIENCIA: Memoria ineficiente? 

DAVID J. MALAN: Si. Bueno, yo no lo haría necesariamente decir ineficiente. Pero le cuesta más memoria, porque necesita 32 bits para cada nodo para el puntero adicional, en menos para una lista vinculada individualmente. Ahora, si sólo se está almacenando números enteros y va a añadir el puntero, eso es en realidad algo no trivial. Lo que duplica la cantidad de memoria. Pero en realidad, si usted está almacenando una lista enlazada de estructuras que podrían tener 8 bytes, 16 bytes, aún más que eso, tal vez es menos de un costo marginal. Pero es un costo, no obstante. Así que cualquiera de ellos hubiera estado bien como desventajas. 

18. Uso de PHP en lugar de C para escribir un programa de línea de comandos. Así que aquí, a menudo es más rápido usar una lenguaje como PHP o Ruby o Python. Sólo tenemos que abrir de forma rápida un editor de texto. Usted tiene muchas más funciones disponibles para usted. PHP tiene el fregadero de la cocina de las funciones, mientras que en C, tienen muy, muy poco. De hecho, los chicos la conocen por las malas que usted no tiene tablas hash. Usted no ha vinculado las listas. Si quieres ellos, usted tiene que aplicar por sí mismo. 

Así que una ventaja de PHP o en realidad cualquier lenguaje interpretado es la rapidez con el que se puede escribir código. Sin embargo, un inconveniente, hemos visto esto cuando batida rápidamente una Misspeller implementación en conferencia usando PHP, es que el uso de un lenguaje interpretado normalmente es más lenta. Y vimos que demostrable con un aumentar en el tiempo desde 0,3 segundos a 3 segundo, porque de la interpretación que en realidad sucede. 

Otra ventaja es que usted no tiene que compilar. Por lo que también acelera el desarrollo dicho sea de paso, porque usted no tiene dos pasos para ejecutar un programa. Usted sólo tiene uno. Y eso es bastante convincente también. Utilizando una base de datos SQL en lugar de un archivo CSV para almacenar datos. Base de datos por lo que SQL se utiliza para pset7. Archivos CSV que no utilizaron mucho. Pero lo usaste indirectamente en pset7 como así hablando con Yahoo Finance. 

Pero CSV es como un archivo de Excel, pero super simple, donde las columnas son sólo demarcada por comas dentro de un archivo de texto de otro modo. Y el uso de una base de datos SQL es un poco más convincente. Es un aspecto positivo, debido a que obtiene las cosas como seleccionar e insertar y borrar. Y se obtiene, presumiblemente, los índices que MySQL y otras bases de datos, como Oracle, construir para usted en la memoria, lo que significa que su selecto probablemente no es va a ser la parte superior a la inferior lineal. En realidad va a ser algo como búsqueda binaria o algo similares en espíritu. Por lo que son en general más rápido. 

Sin embargo, una desventaja es que es sólo más trabajo. Es más esfuerzo. Usted tiene que entender las bases de datos. Hay que configurarlo. Usted necesita un servidor para ejecutar esa base de datos en. Es necesario comprender cómo configurarlo. Así que estos son sólo estos tipo de compensaciones. Mientras que un archivo CSV, puede crearlo con gedit. Y ya está bueno para ir. No hay complejidad más allá de eso. 

El uso de un trie en lugar de una tabla hash con encadenamiento separado para almacenar una diccionario de palabras que recuerdan de pset5. Así que una intenta de cabeza, en teoría al menos, es lo que? Constante de tiempo, por lo menos si eres hash en cada uno de los individuo letras de una palabra, como usted podría tener para pset5. Eso podría ser cinco, seis hashes valores hash si hay cinco o seis letras de la palabra. Y eso es bastante bueno. Y si hay un límite superior sobre cómo tiempo sus palabras podrían ser, eso es tiempo de hecho asintóticamente constante. 

Mientras que una tabla hash con separada encadenamiento, el problema hay con eso tipo de estructura de datos es que el rendimiento de los algoritmos normalmente depende del número de cosas ya en la estructura de datos. Y eso es sin duda el caso de cadenas, por lo que las cosas más se pone en una tabla hash, cuanto más tiempo los cadenas van, lo que significa que en el peor de los casos caso, lo que podría estar buscando es todo el camino en el extremo de uno de esas cadenas, que efectivamente recae en algo lineal. 

Ahora, en la práctica, podría absolutamente ser el caso que una tabla hash con cadenas es más rápido que un correspondiente aplicación trie. Pero eso es por varias razones, entre los que se intenta utilizar una gran cantidad de memoria que puede, de hecho, las cosas con calma abajo, porque no obtiene buena beneficios de algo que se llama el almacenamiento en caché, donde las cosas que están muy juntos en la memoria se puede acceder a menudo más rápidamente. Y a veces uno se puede topar con una muy buena función hash. Incluso si usted tiene que perder un poco de la memoria, es posible que, de hecho, ser capaz de encontrar las cosas rápido y no tan malo como linealmente. 

Así que en resumen, no era necesariamente Con cualquiera de estos uno o incluso dos cosas específicas que estábamos buscando. Realmente nada convincente como Luces y sombras en general, nos llamó la atención. 

ROB BOWDEN: Así que por el lado bueno, lo hicimos No aceptar en su propio "más rápido". Usted tenía que decir algo al respecto. Incluso si usted ha dicho teóricamente más rápido, sabíamos que clase de entendías que es 0 de 1. Y tabla hash, en teoría, no es 0 de 1. Al mencionar nada sobre el tiempo de ejecución generalmente le pusieron los puntos. Sin embargo, "más rápido", la mayoría de las soluciones de el gran tablero que se fueron intentos objetivamente más lento que las soluciones que eran las tablas hash. Por lo tanto más rápido en y de sí mismo no es realmente cierto. 

DAVID J. MALAN: Dom de dom dom. Probablemente soy el único que se da cuenta de así es como se supone que eso ser pronunciado, ¿verdad? 

ROB BOWDEN: Tuve en realidad ni idea. 

DAVID J. MALAN: Hizo sentido en mi cabeza. 

ROB BOWDEN: Estoy haciendo esto. Aceptar. Así que esta es una de las que tuvo que llamar la el diagrama similar al que podría han visto en exámenes anteriores. Así que vamos a ver en esto. Así que desde el nodo HTML, tenemos dos niños, la cabeza y el cuerpo. Así que Branch - cabeza y el cuerpo. La cabeza tiene una etiqueta de título. Así que tenemos un título. 

Ahora, la única cosa que un montón de gente olvidó es que estos nodos de texto son elementos dentro de este árbol. Así que aquí nos toca dibujarlos como óvalos para diferenciarlos de éstos tipos de nodos. Pero aviso también aquí tenemos la parte superior, en medio y abajo va a terminar siendo los nodos de texto. Así que olvidar aquellos era algo de un error común. 

El cuerpo tiene tres hijos - estos tres divs. Así div, div, div y luego el texto hijos del nodo de esos divs. Eso es prácticamente todo para que las preguntas. 

DAVID J. MALAN: Y vale la pena señalar, a pesar de que no nos detengamos en ellas detalles en el tiempo que gastamos en JavaScript, que el orden sí, en hecho, la materia técnicamente. Así que si la cabeza está antes que el cuerpo de la HTML, a continuación, debería aparecer a la izquierdo del cuerpo en el DOM real. Que la suya es, en general, sólo para tu información, algo que se llama el orden del documento, donde sí importa. Y si estuviera implementando un programa de análisis, un programa que lea HTML en la construcción el árbol en la memoria, para ser honesto, eso es probablemente lo que intuitivamente hacer de todos modos - de arriba hacia abajo, izquierda a derecha. 

ROB BOWDEN: Preguntas sobre eso? ¿Debo hacer lo siguiente? 

DAVID J. MALAN: Seguro. 

ROB BOWDEN: OK. Así que este es el desbordamiento de búfer pregunta ataque. Lo más importante aquí es reconocer, así, ¿cómo podría un truco adversario este programa para que ejecute código arbitrario? , La primera línea de comandos para argv1 argumento a este programa, que puede ser arbitrariamente larga. Pero aquí estamos utilizando memcpy para copiar argv1, que aquí es bar. Estamos pasándolo como argumento. Y por lo que está tomando en la barra de nombre. 

Así que estamos memcpying bar en este tampón c. ¿Cuántos bytes estamos copiando? Bueno sin embargo muchos bytes bar pasa a estar usando, la longitud de ese argumento. Pero c es de sólo 12 bytes de ancho. Así que si escribimos un argumento de línea de comandos eso es más de 12 bytes, estamos va a desbordar esta en particular tampón. Ahora, ¿cómo puede un adversario engañar al programar en la ejecución de código arbitrario? 

Así que recuerde que aquí principal se llama foo. Y así, las llamadas principales foo. Dibujemos esto. Así que tenemos nuestro stack. Y principal tiene un marco de pila en la parte inferior. En algún momento, las llamadas principales foo. Bueno, de inmediato, las llamadas principales foo. Y así foo obtiene su propio marco de pila. 

Ahora, en algún momento, foo va a volver. Y se fue retornos foo, necesitamos saber en qué línea de código dentro de la que principal fueron con el fin de saber dónde debemos retomar en main. Podemos llamar a foo del conjunto montón de diferentes lugares. ¿Cómo sabemos dónde devolver? Bueno, tenemos que almacenar esa parte. 

Así que en algún lugar por aquí, almacenamos donde debemos volver a una vez retornos Foo. Y esta es la dirección de retorno. Entonces, ¿cómo un adversario podría aprovechar de esto es el hecho de que este búfer c se almacena, vamos a decir, aquí es c. Así que tenemos 12 bytes para c. Esta es c. Y este es el anillo de pila de foo. Así que si el usuario malicioso entra más bytes que 12 o entran en un comando argumento de la línea más larga que 12 caracteres, entonces vamos a desbordar el buffer. 

Podemos seguir adelante. Y en algún momento, vamos ahora basta con que empezamos sobrescribir esta dirección de retorno. Así que una vez que sobreescribir la dirección de retorno, esto significa que cuando foo retornos, estamos volviendo a dondequiera que el usuario malicioso está diciendo que por cualquiera que sea el valor de su entrada, por lo caracteres que el usuario introduce. Y por lo que si el usuario malintencionado está siendo particularmente inteligente, que puede tener esta regresar a algún lugar en el printDef función o en algún lugar de la malloc función, en cualquier sitio arbitrario. 

Pero aún más inteligente es lo que si tiene el usuario vuelve a la derecha aquí. Y entonces empiezas a ejecutar éstos como líneas de código. Así que en ese punto, el usuario puede introducir lo que quiere en esta región. Y él tiene el control total sobre su programa. Preguntas sobre esto? Así que la siguiente pregunta es completa la reimplementación de foo de tal manera que ya no es vulnerable. 

Así que hay un par de maneras que podría haber hecho esto. Todavía tenemos c sólo siendo de longitud 12. Podrías haber cambiado esta como parte de su solución. También hemos añadido una comprobación para Seguro de bar no era nulo. Aunque usted no necesita que para el crédito completo. Así que estamos comprobando en primer lugar la longitud de la cadena de la barra. Si es mayor que 12, entonces en realidad no hacer la copia. Así que esa es una forma de arreglarlo. 

Otra manera de arreglarlo es lugar de tener c sólo sea de longitud 12, que lo ser de longitud strlen (bar). Otra manera de arreglarlo es que en realidad sólo volver. Así que si lo que se había deshecho de todos esto, si sólo hubieras eliminado todos líneas de código, se habría conseguido todo el crédito, ya que esta función en realidad no lograr nada. Está copiando la línea de comandos argumento en alguna matriz en su marco de pila local. Y entonces la cosa está regresando. Y sea lo que consumado se ha ido. Así retorno también fue un suficiente forma de obtener el crédito completo. 

DAVID J. MALAN: No es el espíritu de la pregunta, pero aceptable por el spec, no obstante. 

ROB BOWDEN: Preguntas sobre algo de eso? La única cosa que usted por lo menos es necesario haber compilar código. Así que, aunque técnicamente no está vulnerables si su código no compilar, no aceptamos eso. No hay preguntas? Aceptar. 

DAVID J. MALAN: ¿Desea decir que este título? 

ROB BOWDEN: No. 

DAVID J. MALAN: Así que en éste, éste era o bien una buena noticia o mala noticia. Esto es literalmente el mismo problema como el primer cuestionario. Y es casi la misma problema como pset1. Pero se ha simplificado deliberadamente para ser una pirámide más simple, uno que puede ser resuelto con un poco iteración simple. Y en realidad, lo que estaban haciendo en aquí no era tanto la lógica, debido probablemente, a estas alturas, usted es más cómodo de lo que eran en la semana uno por bucles o loops por qué, pero en realidad para desmenuzar que estás un poco a gusto con el noción de que PHP no es sólo acerca de lo que de programación. En realidad, puede ser utilizado como un lenguaje escribir programas de línea de comandos. 

Y, de hecho, eso es lo que estábamos tratando para llamar su atención. Este es un programa de línea de comandos de PHP. Así código C aquí, mientras correcta en C, no corregir para PHP. Pero el código es realmente lo mismo. Si se comparan las soluciones para la Prueba 0 contra la prueba 1, usted encontrará que es casi idéntica, a excepción de algunos signos de dólares y para el ausencia de un tipo de datos. En particular, si echamos un vistazo aquí, verás que iteramos, en este caso, desde el 1 hasta al 7. 

Podríamos haber hecho 0 índice. Pero a veces, creo que es justo mentalmente más fácil pensar en las cosas de 1 a 7. Si quieres una cuadra, luego dos bloques, luego tres, luego punto, punto, punto siete. Hemos j se inicializa a 1 y luego contar con hasta i. Y aquí todo es por lo demás idéntico. Pero, se valoran positivamente un par de cosas. Te damos estas dos líneas, esta primera uno, tontamente llamado como un tinglado para Bang agudo. Y eso sólo se especifica la ruta de acceso, el carpeta, en el que un programa puede ser encontró que desea utilizar interpretar este archivo. 

Y luego la línea después de que, de por supuesto, significa entrar en el modo PHP. Y la línea en la parte inferior significa salir del modo PHP. Y esto funciona, en general, con lenguajes interpretados. Es un poco molesto si usted escribe un programa en un archivo llamado foo.php. Y entonces sus usuarios tienen que simplemente recuerde, OK, para ejecutar este programa, tendrá que escribir "foo.php espacio php." Tipo molesto si no otra cosa. Y también revela que su programa está escrito en PHP, que no es todo que iluminando para el usuario. 

Así que usted puede quitar el archivo. Php en conjunto recordar de conferencia. Y en realidad se puede hacer. / Tal si usted ha chmodded por lo que es ejecutable. Así chmod a + x foo habría hecho eso. Y si además sumamos el tinglado aquí. Pero en realidad, el problema estaba en impresión de algo como esto. No HTML, sin código C sin duda, sólo algunas PHP. Entonces Milo luego regresó en el problema 25. Y en el 25, le dieron la siguiente código de esqueleto, que era un página web muy simple. Y la parte más jugosa HTML-sabio bajó aquí, en el que tenemos en el interior del cuerpo un formulario que tiene el ID único de las entradas dentro de las cuales fue dos entradas, una con una idea del nombre, una con una idea de botón. 

El primero fue el texto de tipo, el segunda de tipo submit. Y así que le dimos, en realidad, más ingredientes de lo que necesitaba, sólo para ustedes tenían opciones con las que para resolver este problema. Usted no estrictamente necesario todas estas identificaciones. Pero le permite resolver de diferentes maneras. Y en la parte superior, observe que el objetivo era desencadenar una ventana como esta - Hola, Milo! - para que aparezca en el navegador usando el super simple, si , la función de alerta no feo. Y así, en última instancia, esto se reduce conceptualmente a la escucha de alguna manera para presentaciones del lado del cliente forma , No en el lado del servidor, de alguna manera responder a esa presentación por agarrando el valor que el usuario ha escrito en el campo de nombre, y luego mostrarla en el cuerpo de una alerta. 

Así que una manera de hacer esto es con jQuery, la cual se ve un poco sintácticamente desconcertante al principio. Usted puede hacer esto con código DOM pura - document.getelement por ID. Pero echemos un vistazo a esta versión. Tengo un par de importantes líneas de primera. Así que uno, tenemos esta línea, que es idéntico a lo que podría haber visto en, creo, form2.html de la clase en la semana 9. Y esto es sólo decir, ejecutar el siguiente código cuando el documento está listo. Esta siendo importante sólo porque Las páginas HTML se leen de arriba a abajo, de izquierda a derecha. 

Y por lo tanto, si usted trata de hacer algo en código aquí hasta cierto DOM elemento, alguna etiqueta HTML, que está abajo aquí, lo estás haciendo muy pronto, porque este tiene ni siquiera se ha leído en la memoria. Así que al decir esto document.ready línea, estamos diciendo: aquí hay algo de código, explorador. Pero no ejecutar esto hasta que el conjunto documento está listo, que es el DOM existe el árbol en la memoria. Éste es un poco más sencillo, si un sintácticamente poco diferente, donde yo estoy diciendo, agarrar el elemento HTML cuyo único identificador es insumos. Eso es lo que la etiqueta de hash denota, el ID único. Y luego te llamo. Enviar. 

Así. Presentar aquí es una función, de lo contrario conocido como un método, que es en el interior del objeto en la mano izquierda lado hay que no me destaco. Así que si usted piensa en los insumos como objeto en memoria - y de hecho lo es. Es un nodo en un árbol - . Presentar medios cuando esta forma con se presenta este ID, ejecutar el siguiente código. No me importa lo que el nombre de la función es que estoy ejecutando. Así que aquí estoy utilizando, como antes, lo que es llamada la función lambda o un función anónima. No es en absoluto intelectual interesante aparte de que no tiene nombre, lo cual está bien si sólo estás nunca va a llamar una vez. Y en el interior no me ocupo en realidad la presentación de la forma. La primera vez que declaro una variable llamado valor. Y entonces ¿cuál es el efecto de esta destacó porción aquí ahora? ¿Qué hace eso a una alto nivel para mí? 

AUDIENCIA: Se pone el valor que el usuario no hizo en el HTML. Se hace que la ID y luego encuentra el valor de la misma. 

DAVID J. MALAN: Exactamente. Se agarra el nodo, cuya única identificador es el nombre. Se obtiene el valor de la misma, la cual es, presumiblemente, lo que el usuario él o ella con tipo. Y luego se almacena en el que variable llamada valor. Como acotación al margen, podría tener también hecho esto un poco diferente. Totalmente aceptable haciendo algo valor mentira var consigue document.getElementById. Y es por eso que es un poco tedioso para no usar jQuery. "Name". Valor. Así que totalmente aceptable. Diferentes maneras de hacer esto. jQuery sólo tiende a ser un poco más conciso y definitivamente más populares entre los programadores. 

Ahora, estoy haciendo un poco de cordura comprobar, ya que en el problema declaración dijimos explícitamente, si el usuario aún no ha escrito su nombrar, no muestran una alerta. Pero usted puede comprobar que, con sólo la comprobación de la cadena vacía para un entre comillas si hay nada realmente allí. Pero si no es igual a entre comillas, Quiero llamar a las alertas. Y lo interesante aquí es que estamos utilizando el operador más, que hace qué en JavaScript? Concatenar. Así que es como operador punto PHPS. La misma idea, una sintaxis ligeramente diferente. Y sólo estoy creando la cadena que que vio en la captura de pantalla - Hola, esto y lo otro. 

Y entonces el último detalle es el siguiente. ¿Por qué puedo devolver falso interior de esta función en el anonimato? 

AUDIENCIA: No hay valor. Te lo pones en forma. Sólo dice, si el valor no es igual a blanco, y luego hacerlo. Había un espacio en blanco en esa comunicación. 

DAVID J. MALAN: OK. Cuidado, sin embargo. No hay nadie más aquí. Y ese falso retorno está fuera del caso de condiciones. Así que esto pone de relieve la línea, devolverá false, ejecuta sin importar lo que cuando se envía el formulario. ¿Qué quiere regresar falsa dentro de este controlador de eventos, como se le llama, el evento en cuestión siendo la sumisión? 

AUDIENCIA: Porque sólo sucede una vez. 

DAVID J. MALAN: Sólo ocurre una vez. No del todo. ¿Sí? 

AUDIENCIA: Se evita que el formulario presentar al comportamiento predeterminado, lo que haría que la recarga de la página. 

DAVID J. MALAN: Exactamente. Así que estoy sobrecargando el término presentar aquí, porque yo estoy diciendo, la forma es que se envía. Pero como usted sugiere, en realidad no es ha presentado en el verdadero camino HTTP. Al hacer clic en Enviar, debido a nuestra manejador onSubmit, estamos interceptando que el envío de formularios por así decirlo. Entonces estamos haciendo lo nuestro con código JavaScript. Pero me estoy volviendo deliberadamente falsa, porque lo que yo no quiero que suceda una fracción de segundo más tarde es para todo el formulario misma que se presentará a la web servidor con pares de valores clave, cambiando la URL a ser algo así como q = gatos o lo que hicimos, por ejemplo, en la clase. No quiero que eso suceda, porque no hay escucha del servidor para este Formulario de envío. Es puramente hecho en código JavaScript. Y es por eso que ni siquiera tenía un atributo de acción en mi forma, porque yo No pretendo que esto alguna vez al servidor. 

Así que ha de ser presentado. Pero estamos interceptando esa forma presentación y prevenir el predeterminado comportamiento, que es en realidad ir hasta el final con el servidor. 

AUDIENCIA: Así que mantenerla en el cliente. 

DAVID J. MALAN: Mantener del lado del cliente es. Exactamente derecha. El siguiente fue mi oh MySQL. 

ROB BOWDEN: OK. Así que esta primera pregunta fue en general difícil para la gente. A pesar de los posteriores fueron mejor. Así que tienes que elegir los datos correctos tipos para ambas de estas columnas. Y ambos tienen algunos cosas sobre ellos que tomar la decisión difícil. Así int no era una válida tipo de número. La razón es que una cuenta de 12 dígitos número, un int no es lo suficientemente grande como para almacenar dígitos en total. Así que una opción válida habría sido un gran int, si por casualidad usted conoce eso. Otra opción podría haber sido un campo de caracteres de longitud 12. Así que cualquiera de ellos hubiera funcionado. Int. no lo haría. 

Ahora, el balance, pensar de nuevo a pset7. Así que usamos específicamente decimal a almacenar el valor de las acciones o - 

DAVID J. MALAN: Efectivo. 

ROB BOWDEN: Efectivo. Se utilizó decimales para almacenar la cantidad de dinero en efectivo que el usuario tiene actualmente. Así que la razón por la que hacemos esto es porque, recuerde, flotadores. No coma flotante en precisión. No se puede almacenar con precisión el dinero en efectivo valores como nos quieren aquí. Así decimal es capaz de precisamente tienda algo que, por ejemplo, dos decimales. Es por eso que el equilibrio, lo queremos ser decimal y no flotar. 

DAVID J. MALAN: Y también, también, aunque que podría haber sido inteligente en otros contextos en que pensar, tal vez esto es una oportunidad para un int. Voy a seguir la pista de cosas en monedas de un centavo. Porque hemos demostrado explícitamente el valor por defecto valor de ser 100.00, que significa que sólo podría ser un int. Y otra sutileza demasiado con el número era que no estaba destinado ser una pregunta con trampa. Pero recordar que un int en MySQL, como en C, al menos en el aparato, es de 32 bits. Y a pesar de que no le esperamos saber exactamente cuántos dígitos que significa, ¿recuerdan que el número más grande puede representar potencialmente con un número de 32 bits es más o menos lo que? 

¿Qué número es lo que siempre decimos? 2 a la 32, que es lo que más o menos? Usted no tiene que saber con precisión. Pero más o menos es de gran ayuda en la vida. Es más o menos 4 mil millones. Así que lo que hemos dicho que un par de veces. Sé que he dicho que un par de veces. Y es más o menos 4 mil millones. Y eso es una buena regla de oro para saber. Si usted tiene 8 bits, 256 es el número mágico. Si usted tiene 32 bits, 4 mil millones más o menos. Así que si usted acaba de escribir una baja de 4 millones de dólares, verás que es menos dígitos que 12, lo que significa que no es claramente suficiente expresividad para capturar una Número de cuenta de 12 dígitos. 

ROB BOWDEN: OK. Así que los otros fueron mejor. Así que supongamos que el banco impone una $ 20 mensuales cuota de mantenimiento en todas las cuentas. Con lo que la consulta SQL podría el banco deducir $ 20 desde cada cuenta, incluso si que resulta en algunos saldos negativos? Así que, básicamente, hay cuatro principales tipos de consultas - insertar, seleccionar, actualizar y eliminar. Entonces, ¿qué pensamos que somos va a utilizar aquí? Actualizar. 

Así que vamos a echar un vistazo. Así que aquí estamos actualizando. ¿Qué tabla estamos actualizando las cuentas? Así que la actualización de las cuentas. Y entonces la sintaxis dice, lo que en cuentas estamos actualizando? Bueno, estamos estableciendo el equilibrio igual a la valor corriente de la balanza de menos 20. Así que esto va a actualizar todas las filas de cuentas, restando $ 20 a partir del balance. 

DAVID J. MALAN: Un error muy común aquí, a pesar de que a veces nos perdonó, era que en realidad tienen código PHP aquí llamando a la función de consulta o poner comillas alrededor de todo lo que no necesitaba estar allí. 

ROB BOWDEN: Recuerde que MySQL es un lenguaje independiente de PHP. Nos pasó a estar escribiendo MySQL en PHP. Y PHP es luego enviarlo al servidor MySQL. Pero usted no necesita PHP con el fin de comunicarse con un servidor MySQL. 

DAVID J. MALAN: Exactamente. Así que no hay variables con signos de dólar debería ser en este contexto. Sólo puede hacer todas las matemáticas dentro de la propia base de datos. 

ROB BOWDEN: OK. Así que la siguiente. ¿Es esto la próxima? Sí. Así que con lo que la consulta SQL podría el banco recuperar los números de cuenta de su clientes más ricos, los que tienen saldos superiores a 1000? Entonces, ¿cuál de los cuatro tipos principales vamos a querer aquí? Seleccione. Así que queremos seleccionar. ¿Qué queremos para seleccionar? Lo que la columna es lo que queremos para seleccionar? Específicamente Querremos para seleccionar el número. Pero si usted dice la estrella, que también aceptado. 

Así que seleccione el número de lo que la tabla? Cuentas. Y entonces la condición que queremos? Dónde equilibrio mayor que 1000. También aceptamos mayor o igual. Una pasada. Con lo que la consulta SQL podría el banco estrecha, es decir, eliminar todas las cuentas que tiene un saldo de $ 0? Entonces, ¿cuál de los cuatro somos va a querer usar? Eliminar. De modo que la sintaxis para eso? Eliminar en lo mesa? Cuentas. Y entonces la condición en la que queremos eliminar - donde el equilibrio es igual a cero. Así que eliminar todas las filas de cuentas donde el equilibrio es cero. Las preguntas sobre cualquiera de ellos? ¿Quieres hacer cola? 

DAVID J. MALAN: guía de cola. Así que en éste, le dimos un poco estructura familiar que hemos explorado un poco en clase junto de estructuras, que era un dato relacionados con la estructura de espíritu. La diferencia aunque con una cola es que teníamos que recordar que de alguna manera estaba en la parte delantera de la cola, en gran parte para que pudiéramos hacer más uso eficiente de la memoria, al menos si estábamos usando una matriz. 

Debido a recordar, si tenemos una matriz, si, por ejemplo, esta es la parte frontal de la cola, si me meto en la cola de aquí, y entonces alguien se interpone en línea detrás de mí, detrás de mí, detrás de mí, y una persona pasa de la raya, que podría, como hemos visto algunos de nuestros recursos humanos voluntarios en la clase, tienen todos cambiar de esta manera. Pero, en general, habiendo cada uno haga algo que no es el mejor uso del tiempo en un programa, ya que significa que su algoritmo se ejecuta en lo tiempo de ejecución asintótica? Es lineal. 

Y siento que eso es un poco estúpido. Si la persona siguiente en la línea es el siguiente persona que se supone que debe ir a la tienda, no todos tienen a moverse juntos. Simplemente deja que esa persona se mesaban cuando llegue el momento, por ejemplo. Así que podemos ahorrar un poco de tiempo allí. Y así, para hacer eso, sin embargo, que los medios que la cabeza de la cola o el frente de la cola va a progresivamente avanzar más y más profundo en la matriz y eventualmente podría realmente envolver alrededor si estamos utilizando un matriz para almacenar el pueblo en esta cola. Así que casi se puede pensar en el matriz como una circular de datos estructura en ese sentido. 

Así que de alguna manera tiene que realizar un seguimiento de la tamaño de la misma o en realidad el final de la misma y luego en el que el principio de que es. Así que proponemos que se declara una de esas colas, llamadas q ella, sólo una letra. Entonces, proponemos que el frente sea inicializado a cero y que el tamaño ser inicializado a cero. 

Así que ahora mismo, no hay nada dentro de esa cola. Y le pedimos que complete el aplicación de puesta en cola a continuación en de tal manera que la función agrega a N Al final de q y luego devuelve true. Pero si q está lleno o negativo, el función debe devolver en su lugar falso. Y les dimos un par de supuestos. Pero en realidad no son funcionalmente relevante, existe sólo que bool, porque, técnicamente, bool no existir en C a menos que incluya un determinado archivo de cabecera. Así que eso fue sólo asegúrese de que no se no es un truco pregunta tipo de cosas. 

Así enqueue, propusimos en la muestra soluciones para implementar de la siguiente manera. Uno, primero revisamos la facilidad, los frutos maduros. Si la cola está llena o el número que usted está tratando de insertar es menos que cero, lo que dijimos en el especificación del problema debe No se permitirá, porque sólo queremos valores no negativos, entonces debería simplemente devolver false inmediatamente. Así que algunos relativamente fácil la comprobación de errores. Si a pesar de que deseas añadir que real número, había que hacer un poco de pensando aquí. Y aquí es donde está un poco molesto mentalmente, porque hay que encontrar la manera de manejar envolvente. 

Sin embargo, el germen de la idea aquí que es de interés para nosotros es que la envolvente menudo implica la aritmética modular y el operador mod, el lado por ciento, donde se puede pasar de un valor mayor de nuevo a cero y luego de uno y dos y tres y luego de vuelta en torno a cero, uno y dos y tres y así sucesivamente una y otra vez. Así que la forma se propone hacer esto es que nosotros queremos índice en la matriz llamada números donde nuestros números enteros mienten. Pero para llegar allí, lo primero que queremos hacer cualquiera que sea el tamaño de la cola es pero a continuación, añadir que cualquiera que sea el frente de la lista es. Y el efecto de esto es que nos pusieran en la posición correcta en la cola y No asuma que la primera persona de la fila es al principio, que él o ella absolutamente podría ser si también fueron cambiando todos. Pero esto es sólo la creación de trabajo para nosotros si tomamos esa ruta en particular. 

Así que podemos mantenerlo relativamente simple. Tenemos que recordar que acabamos de añadido un int a la cola. Y luego simplemente devolvemos cierto. Mientras tanto, en quitar de la cola, le preguntamos usted pueda hacer lo siguiente. Implementar de tal manera que se Retiros de cola, es decir elimina y vuelve, el int en la parte delantera de la cola. Para quitar el int, basta olvidarlo. No es necesario para anular su granito de arena. Así que es todavía realmente allí. Al igual que los datos de un disco duro, sólo estamos ignorando el hecho de que es ahora. Y si q está vacío, deberíamos que la devolverá negativo 1. Así que esto se siente arbitraria. ¿Por qué volver negativo 1 en lugar de la falsa? Sí. 

AUDIENCIA: Q es el almacenamiento de valores positivos. Dado que sólo almacena los valores positivos en el q, negativo es un error. 

DAVID J. MALAN: OK, es cierto. Así que debido a que sólo estamos almacenando positivo valores o cero, entonces está bien para devolver un valor negativo como un centinela valor, un símbolo especial. Pero usted está reescribiendo la historia allí, porque la razón por la que sólo estamos la devolución de valores no negativos es porque queremos tener un valor centinela. Así que, más concretamente, ¿por qué no return false en caso de errores? Sí. 

AUDIENCIA: Has fallado para devolver un entero. 

DAVID J. MALAN: Exactamente. Y aquí es donde se pone C limitante bastante. Si estás diciendo que te vas para devolver un int, tienes para devolver un int. No se puede conseguir la suposición y empezar a devolver un bool o un flotador o un cuerda o algo así. Ahora, por su parte, JavaScript y PHP y algunos otros lenguajes puede, de hecho, has de regresar diferente tipos de valores. Y eso puede ser realmente útil, donde usted podría volver ints positivos, ceros, ints negativos o falsa o nula incluso para significar de error. Pero no tenemos que versatilidad en C. 

Así que con quitar de la cola, lo que proponer que hacer es - 

ROB BOWDEN: Usted puede devolver false. Es sólo que es falso de hash definir falsa a cero. Así que si usted vuelve falsa, usted está volviendo a cero. Y el cero es una cosa válida en nuestra cola, mientras que 1 no es negativo si falsa pasó a ser negativo 1. Pero usted no debe incluso necesitan saber que. 

DAVID J. MALAN: Eso es razón por la que no lo dije. 

ROB BOWDEN: Pero no era cierto que no se puede devolver false. 

DAVID J. MALAN: Seguro. Así que quitar de la cola, notamos que aceptamos anular como argumento. Y eso es porque no estamos pasa nada pulg Sólo queremos eliminar el elemento en la parte delantera de la cola. Entonces, ¿cómo podríamos ir haciendo esto? Bueno, en primer lugar, vamos a hacer esto comprobación de validez rápida. Si el tamaño de la cola es 0, no hay hay trabajo por hacer. Volver negativo 1. Hecho. Así que eso es unas pocas líneas de mi programa. Así que sólo cuatro líneas permanecen. 

Así que aquí me decido a disminuir el tamaño. Y decrementar el tamaño eficaz significa que me estoy olvidando algo está ahí. Pero también tengo que actualizar cuando la parte delantera de los números son. Así que para hacer eso, necesito que hacer dos cosas. Primero tengo que recordar lo que el número es en la parte delantera de la cola, porque tengo que devolver esa cosa. Así que no quiero olvidar accidentalmente al respecto y luego sobrescribirlo. Sólo voy a recordar en un int. 

Y ahora, quiero actualizar q.front a ser q.front 1. Así que si esta fue la primera persona en línea, ahora, quiero hacer más 1 a apuntar a la siguiente persona en la fila. Pero tengo que manejar esa envolvente. Y si la capacidad es una constante global, eso va a permitir que me asegure como señalo a la última persona en line, la operación de módulo traerá me de nuevo a cero en el principio de la cola. Y que maneja la envolvente aquí. Y entonces me dedico a regresar n. 

Ahora bien, estrictamente hablando, no lo hice que declarar n. Yo no tengo que agarrarlo y guárdelo temporalmente, porque el valor es sigue ahí. Así que yo podría hacer lo aritmético a la derecha para devolver el ex jefe de la cola. Pero yo sentía que esto era más claro para tomar realmente el int, lo puso n y, a continuación, devolver ese para mayor claridad, pero no es estrictamente necesario. Psst. Son todos pronunciable en mi cabeza. 

ROB BOWDEN: Así que la primera pregunta es el problema del árbol binario. Así que la primera pregunta es que estamos teniendo en cuenta estos números. Y queremos insertar alguna manera ellos en estos nodos tales que es un válida árbol de búsqueda binaria. Así que la única cosa que hay que recordar acerca de árboles binarios de búsqueda es que no es sólo que la cosa a la izquierda es menos y lo que hay que el derecho es mayor. Tiene que ser que todo el árbol a la izquierda es menor, y todo el árbol a la derecha es mayor. 

Así que si pongo 34 aquí en la parte superior, y luego Puse 20 aquí, así que eso es válido por lo que lejos, porque 34 aquí. 20 va a la izquierda. Así que eso es menos. Pero no puedo luego poner 59 aquí, porque a pesar de que el 59 está a la derecha de los 20, todavía está en el lado izquierdo de 34. Así que con esa limitación en mente, el de manera más fácil probablemente la solución de este problema es sólo una especie de estos números - por lo que el 20, 34, 36, 52, 59, 106. Y a continuación, inserte los de izquierda a derecha. 

Así que 20 va aquí. 34 va aquí. 36 va aquí. 52, 59, 106. Y también se podría haber imaginado con algunos de enchufar y realizar, oh, espera, yo no tengo suficientes números para llenar esto en aquí. Así que tengo que reshift lo que mi nota ruta va a ser. Pero nótese que en los tres finales, si se lee de izquierda a derecha, es en creciente. 

Así que ahora, queremos declarar lo que el estructura va a ser para el nodos de este árbol. Entonces, ¿qué es lo que necesitamos en un árbol binario? Así que tenemos un valor de tipo int, por lo que un valor int. No sé lo que llamamos en la solución - int n. Necesitamos un puntero al hijo izquierdo y un puntero al hijo derecho. Así que va a tener este aspecto. Y va realmente se ven antes ¿cuándo te ligada doblemente al Lista de cosas, así que aviso - Voy a tener que desplazarse todo el camino de vuelta al problema 11. 

Entonces notó que se ve idéntica a ésta, excepto que sólo sucede que llamar a estos diferentes nombres. Todavía tenemos un entero valor y dos punteros. Es sólo que en lugar de tratar el punteros como señalar a la siguiente cosa y lo anterior, estamos tratando los punteros para apuntar a un hijo izquierdo y el hijo derecho. Aceptar. Así que ese es nuestro nodo estructura. Y ahora, la única función que necesitamos aplicar para esto es transversal, que queremos ir por encima del árbol, la impresión los valores del árbol en orden. 

Así que buscando aquí, nos gustaría imprimir a cabo el 20, 34, 36, 52, 59, y 106. ¿Cómo logramos esto? Así que es bastante similar. Si usted vio en el examen pasado el problema que quería imprimir todo el árbol con comas entre todo, en realidad era incluso más fácil que eso. Así que aquí está la solución. Este fue significativamente más fácil si lo hizo de forma recursiva. No sé si alguien ha intentado hacerlo de forma iterativa. 

Pero primero, tenemos nuestro caso base. ¿Y si la raíz es nulo? Entonces sólo vamos a volver. No queremos imprimir nada. Else que vamos a atravesar recursiva hacia abajo. Imprimir todo el subárbol izquierdo. Así que imprimir todo menos que mi valor actual. Y luego voy a imprimir yo mismo. Y luego voy a recurse por mi toda subárbol derecho, por lo que todo mayor que el valor de mi. Y esto va a imprimir a cabo todo en orden. Las preguntas sobre cómo esta realidad logra eso? 

AUDIENCIA: Tengo una pregunta en la [inaudible]. 

ROB BOWDEN: Así que una manera de acercarse a cualquier problema recursivo es sólo pensar sobre él como usted tiene que pensar sobre todos los casos de esquina. Así que consideramos que queremos imprimir todo este árbol. Así que todo lo que vamos a centrarse en es este nodo en particular - 36. Las llamadas recursivas, que pretenden aquellos que sólo trabajan. Así que aquí, esta llamada recursiva a transversal, que sin siquiera pensar al respecto, sólo que atraviesa la izquierda tres, imagino que ya se imprime 20 y 34 para nosotros. Y luego, cuando finalmente recursiva llamar transversal en la derecho, que se imprimirá correctamente 52, 59, y 106 para nosotros. 

Así que teniendo en cuenta que esto puede imprimir 20, 34 y el otro puede imprimir 52, 59, 108, todo lo que necesitamos para ser capaz de hacer es imprimir nosotros mismos en medio de eso. Así que imprimir todo lo que tenemos ante nosotros. Imprimir mismos, por lo que la impresión nodo actual 36, printf regular, y luego imprimir todo después de nosotros. 

DAVID J. MALAN: Aquí es donde la recursividad se pone muy bonito. Es este increíble salto de fe donde usted hace los más pequeños poco de trabajo. Y luego deja que alguien más lo haga el resto. Y que alguien más es, irónicamente, usted. Así que para puntos brownie graves, si se desplaza hacia arriba en las preguntas - 

ROB BOWDEN: En las preguntas? 

DAVID J. MALAN: Y un poco para los números, ¿alguien sabe donde estos números vienen? 

ROB BOWDEN: No tengo ni idea, literalmente. 

DAVID J. MALAN: Aparecen durante todo el concurso. 

AUDIENCIA: ¿Son los mismos números? 

DAVID J. MALAN: Esos números. Un pequeño huevo de Pascua. Así que para aquellos de ustedes viendo en línea en casa, si puede decirnos vía correo electrónico a heads@CS50.net lo que la importancia de estos seis números que se repiten son a lo largo de la prueba 1, vamos a la ducha le con una atención increíble en la final conferencia y una pelota anti-estrés. Niza, sutil. 

ROB Bowden: ¿Unas últimas preguntas sobre cualquier cosa en el concurso?