[Powered by Google Translate] [Semana 6] [David J. Malan] [Harvard University] [Esta es CS50.] [CS50.TV] 

Esto es CS50, y este es el comienzo de la Semana 6, así que un par de nuevas herramientas ya están disponibles para que usted pueda aprovechar, el primero de los cuales se llama CS50 estilo. Lo más probable es que si eres como yo o cualquiera de los compañeros docentes, de lo que has visto un programa cuyo estilo se parece un poco algo como esto. Tal vez usted comience a cortar algunas esquinas a altas horas de la noche, o va a lidiar con él más tarde, y luego un TF o CA viene en horario de oficina. Entonces es difícil para nosotros leer. Pues bien, este código es sintácticamente correcta, y compilarlo voluntad, y se ejecutará en realidad. Pero definitivamente no es un 5 por estilo. 

Pero ahora, si nos adentramos en este directorio here- y note que tengo conditions2.c- y me encuentro con este nuevo comando, style50, en esta conditions2.c archivo, Intro, cuenta de que me ha informado de que ha sido estilizada. Gedit cuenta de que el archivo ha sido cambiado en el disco, y si hago clic en recargar, todos sus problemas se han automatizado. [Aplauso] Esa es una de las cosas que hicimos este fin de semana. Reconocemos que es imperfecto, porque hay algo de código que simplemente no será capaz de estilizar perfectamente, pero se dan cuenta esto es ahora una herramienta que puede aprovechar aunque sólo sea para poner en orden algunos de los aparatos más equivocadamente colocado llaves y similares. 

Pero ahora es más convincente CS50 Check. Con CS50 cheque, usted puede realizar las pruebas de regularidad mismos en su propio código que los becarios de enseñanza son capaces de hacerlo. Esta es una utilidad de línea de comandos que viene ahora en el aparato tan pronto como lo hace un update50 como por pset 4 especificaciones, y lo utiliza esencialmente como este. Ejecuta el comando check50. Luego se pasa un argumento de línea de comandos, o más generalmente conocido como un interruptor o una bandera. En general, las cosas que tienen guiones se llama un interruptor a un programa de línea de comandos, por lo que-c especifica los cheques que desea ejecutar. 

Las pruebas que desea ejecutar se identifican individualmente por esta cadena, 2012/pset4/resize. En otras palabras, eso es sólo una cadena arbitraria pero única que utilizamos para identificar de forma exclusiva las pruebas 4 pset de corrección. Y entonces se especifica una lista separada por espacios de los archivos que desea cargar para CS50 Check para su análisis. Por ejemplo, si entro en mi solución aquí para resize.c- permítanme abrir un terminal más grande de ventana y sigo adelante y ejecutar digamos check50-c 2012/pset4/resize, y luego seguir adelante y especificar los nombres de los archivos, resize.c, a continuación, pulse la tecla Enter, se comprime, que se carga, se comprueba, y me acaba de fallar un montón de pruebas. El que está en rojo en la parte superior izquierda que dice resize.c y bmp existir. Esa era la prueba. Esa fue la pregunta que nos hacíamos. Y es triste porque la respuesta era falsa. El texto en blanco debajo de ella dice espera bmp.h de existir, y eso es simplemente mi culpa. Me olvidé de subir, así que tengo que subir ambos archivos, resize.c y bmp.h. Pero ahora noten todas las otras pruebas son de color amarillo porque no se han ejecutado, por lo que la cara sonriente es vertical porque no es ni alegre ni triste, pero tenemos que corregir ese problema en rojo antes de que esos otros controles se ejecutará. 

Vamos a arreglar esto. Permítanme hacer un zoom hacia fuera y volver a ejecutar esta, esta vez con bmp.h también en la línea de comandos, escriba, y ahora, si todo va bien, que va a revisar y volver a consecuencia de aguantar la respiración- todo verde, lo que significa que estoy haciendo realmente bien en pset 4 hasta el momento. Usted puede ver y deducir del texto descriptivo aquí exactamente qué es lo que probamos. Probamos primero qué los archivos existen? Hemos probado entonces se compila resize.c? Luego probamos no cambiar su tamaño un BMP de 1x1 píxeles cuando n, el factor de cambio de tamaño, es 1. Ahora, si usted no tiene idea de lo que n es que una vez que exploramos pset 4, sino que simplemente es un simple control para asegurarse de que usted no es el cambio de tamaño una imagen en absoluto si el factor de cambio de tamaño 1. Si, por el contrario, cambia el tamaño de un píxel de 1x1 para un 1x1 2x2 píxeles a BMP correctamente cuando n es 2, entonces similarmente, mina de forma consiguiente. 

En definitiva, se pretende, uno, tomar el cruce los dedos fuera de la ecuación adecuada para usted antes de presentar su conjunto de procesadores. Usted sabrá exactamente lo que su TF pronto sabrá cuando usted va sobre la presentación de algunos de estos conjuntos de problemas, y también la motivación pedagógica es realmente poner la oportunidad delante de ti para que cuando se conoce a priori que no hay errores en el código y pruebas que no se pasan, usted puede poner en más tiempo efectivo por adelantado para resolver esos problemas en lugar de perder puntos, obtener retroalimentación de su TF, y luego, "Ahh," como yo debería haber imaginado. Ahora por lo menos hay una herramienta para ayudarle a encontrar eso. No va a señalar que el error es, pero le dirá lo que es un síntoma de la misma. 

Ahora se dan cuenta que las pruebas no son necesariamente exhaustivas. El hecho de que usted recibe una pantalla llena de caras sonrientes verde no significa que su código es perfecto, pero significa que ha pasado ciertas pruebas prescritas por la especificación. A veces no nos dará a conocer los cheques. Por ejemplo, whodunit, uno de los aspectos del conjunto de procesadores 4, es un poco decepcionante si le damos la respuesta en cuanto a lo que es, y hay un número de maneras de revelar que la persona está en que el ruido rojo. La especificación siempre se especificarán en el futuro para pset 5 en adelante qué controles existen para ti. Se dará cuenta de que hay esta URL blanco en la parte inferior. Por ahora, esto es sólo la salida de diagnóstico. Si vas a visitar esa URL, tendrás un montón de mensajes crípticos locos, que le invitamos a mirar a través, pero es sobre todo para el personal para que podamos diagnosticar y depurar errores en check50 sí mismo. 

Sin preámbulos, vamos a pasar a donde lo dejamos. CS50 biblioteca tomamos por sentado durante algunas semanas, pero la semana pasada, empezamos quitando una de las capas de la misma. Empezamos poniendo a un lado cadena en favor de lo que en su lugar? [Los estudiantes] Char. * Char, que ha sido un char * todo este tiempo, pero ahora no tenemos que fingir que es una cadena de datos actual tipo. Más bien, ha sido un sinónimo de tipo de char *, y una cadena es una secuencia de caracteres, ¿por qué tiene sentido para representar cadenas como char * s? ¿Qué hace un char * representan en el contexto de este concepto de una cadena? Si. >> [Estudiante] El primer carácter. Bueno, el primer carácter, pero no es el primer carácter. Son los-[Los estudiantes] Dirección. Bien, la dirección del primer carácter. Todo lo que es necesario para representar una cadena en la memoria de una computadora es sólo la dirección única de su byte muy primero. Usted ni siquiera tiene que saber cuánto tiempo es porque ¿cómo puede usted darse cuenta de eso dinámicamente? [Estudiante] longitud de cadena. Usted puede llamar longitud de la cadena, excelente, pero ¿cómo funciona la cadena de longitud? ¿Qué hacer? Si. [Estudiante] Sigue adelante hasta que llegue el carácter nulo. Sí, exacto, simplemente itera con un bucle for, while, lo de * hasta el final, y el final está representado por \ 0, el carácter nul llamada, nul, que no debe confundirse con un valor nulo, que es un puntero, que entrará en la conversación de nuevo hoy. 

Nos desprendió una capa de getInt, y luego echó un vistazo a GetString, y recordar que esas dos funciones, o en realidad, GetString, utilizaba una determinada función para analizar en realidad, es decir, leer y analizar, la entrada del usuario. ¿Y cuál era esa nueva función? Scanf o sscanf. En realidad, viene en sabores diferentes. Hay scanf, hay sscanf, hay fscanf. Por ahora, sin embargo, vamos a centrarnos en la más fácilmente ilustrado, y déjame seguir adelante y abrir el aparato un archivo de este tipo, scanf1.c. Este es un programa super simple, sino que hace algo que nunca hemos hecho sin la ayuda de la biblioteca CS50. Esto consigue un int de un usuario. ¿Cómo funciona? Pues bien, en la línea 16 allí, cuenta de que declaramos una x int llamado, y en este momento de la historia, ¿cuál es el valor de x? [Respuesta de los estudiantes inaudible] [David M.] Claro, quién sabe, algún valor potencialmente basura, por lo que en el 17, que acabamos de indicar al usuario dame un número, por favor, y el paso 18 es donde se pone interesante. Scanf parece pedir prestada una idea de printf en que utiliza estos códigos de formato entre comillas. D% es por supuesto un número decimal. Pero ¿por qué estoy pasando & x en lugar de x sólo? El primero es la correcta. Si. [Respuesta de los estudiantes inaudible] Exactamente, si el objetivo de este programa, al igual que el getInt función en sí misma, es conseguir un int por parte del usuario que puede pasar funciones todas las variables que quiero, pero si no pasarlos por referencia o por dirección o puntero, todos sinónimos para los propósitos actuales, luego de que la función no tiene la capacidad de cambiar el contenido de esa variable. Esto pasaría en una copia al igual que la versión con errores de swap que ya hemos hablado un par de veces ahora. 

Pero en cambio, al hacer & x, estoy literalmente pasando en qué? [Estudiante] La dirección. >> La dirección de x. Es como dibujar un mapa para la función llamada scanf y diciendo aquí, estas son indicaciones de cómo un trozo de memoria en el ordenador que se puede ir almacenar algún entero pulg Para sscanf hacer ahora que qué operador, qué pedazo de sintaxis se va a tener que usar aunque no podemos verlo porque alguien escribió esta función? En otras palabras - ¿qué es eso? [Estudiante] X leer. Va a ser un poco de lectura, pero sólo con respecto a x aquí. Si scanf se está pasando la dirección de x, sintácticamente, qué operador está obligado a existir en alguna parte dentro de la aplicación, de manera que scanf scanf en realidad se puede escribir un número de 2 a esa dirección? Sí, así que el archivo *. Recordemos que el * es nuestro operador para deshacer referencias, que esencialmente significa ir allí. 

Una vez que haya sido entregada una dirección, como es el caso aquí, scanf es, probablemente-si en realidad se veía alrededor de su código fuente- hace * x o el equivalente de ir realmente a esa dirección y poner algo de valor allí. Ahora, en cuanto a cómo scanf tiene entrada desde el teclado, vamos a agitar nuestras manos para hoy. Simplemente asume que el sistema operativo permite hablar sscanf para el teclado del usuario, pero en este punto ahora en línea 19, cuando simplemente imprimir x, que parece ser el caso scanf que ha puesto en int x. Así es exactamente como funciona scanf, y recordar la semana pasada así es exactamente como GetString y getInt y su otra familia de funciones en última instancia, funciona, aunque con una ligera variación como sscanf, lo que significa escanear una cadena en lugar del teclado. Pero echemos un vistazo a una variación poco de esto. En scanf2, realmente jodido. Lo que está mal, y yo voy a ocultar el comentario que explica tanto- lo que está mal con este programa, la versión 2? Sea lo más técnica posible este momento. Se ve bastante bien. Está muy bien marcada, pero- bien, ¿qué vamos a podar hasta más cortas preguntas? Línea 16. ¿Cuál es la línea 16 hace en Inglés precisa pero técnica? Conseguir un poco incómodo. Sí, Michael. [Estudiante] Se señala a la primera letra de una cadena. 

Bueno, cerca. Permítanme que ajustar un poco. Refiriéndose a la primera letra de una cadena, se declara una variable llamada búfer que apunte a la dirección primera de una cadena, o más bien, que se señalan más específicamente a un char. Tenga en cuenta que no es en realidad apunta a ninguna parte porque no hay ningún operador de asignación. No hay ningún signo de igual, así que todo lo que estamos haciendo es asignar el búfer llamado variable. Le pasa a ser de 32 bits, ya que es un puntero, y el contenido del buffer presumiblemente eventualmente contendrá la dirección de un char, pero por ahora, lo que contiene buffer? Sólo un poco falso, quién sabe, un poco de basura valor, porque no se ha inicializado explícitamente, por lo que no se debe asumir nada. Bien, ahora la línea 17 es-¿qué significa hacer la línea 17? Tal vez eso se calentará esto. Se imprime una cadena, ¿no? Imprime cadena por favor. 

La línea 18 es una especie de familiar ahora en que acabamos de ver una variación de esta pero con un código de formato diferente, por lo que en la línea 18, le estamos diciendo aquí scanf es la dirección de un trozo de memoria. Quiero que suene en una cadena, como se deduce de% s, pero el problema es que no hemos hecho un par de cosas aquí. ¿Cuál es uno de los problemas? [Estudiante] Está tratando de eliminar la referencia a un puntero nulo. Bueno, punteros nulos o simplemente desconoce lo contrario. Estás entregando scanf una dirección, pero que acaba de decir hace un momento que esa dirección es un valor basura porque en realidad no nos asignarla a nada, y por lo que estamos diciendo scanf disponible nos puso una cuerda aquí, pero no sabemos dónde está aquí todavía, por lo que no se han asignado para la memoria buffer. Por otra parte, lo que tampoco son aún contando scanf? Supongamos que se trataba de un trozo de memoria, y no era un valor basura, pero todavía no estás diciendo scanf algo importante. [Estudiante] Cuando en realidad, el símbolo de unión. Ampersand, por lo que en este caso, está bien. Debido a tope ya se ha declarado como un apuntador con la pieza * de sintaxis, no es necesario utilizar ampersand porque ya es una dirección, pero creo que lo escucharon aquí. [Estudiante] ¿Cómo es de grande? Bueno, no estamos diciendo scanf lo grande que es este tampón, lo que significa que incluso si tampón eran un puntero, estamos diciendo scanf, poner una cadena aquí, pero aquí podría ser 2 bytes, que puede ser de 10 bytes, que podría ser un megabyte. Scanf tiene ni idea, y porque se trata de un trozo de memoria presumiblemente, no es una cadena aún. No es más que una cadena una vez que escribir caracteres y un 0 \ a que buena parte de la memoria. Ahora es sólo un poco de buena parte de la memoria. Scanf no se sabe cuando dejar de escribir a esa dirección. 

Si usted recuerda algunos ejemplos en el pasado en el que se escriben al azar en el teclado tratando de desbordar un buffer, y hablamos el viernes sobre exactamente eso. Si un adversario de alguna manera inyecta en su programa una palabra mucho más grande u oración o frase luego que esperabas puede invadir un trozo de memoria, que puede tener consecuencias negativas, como hacerse cargo de todo el programa en sí. Tenemos que arreglar esto de alguna manera. Permítanme hacer un zoom hacia fuera y entrar en la versión 3 de este programa. Eso es un poco mejor. En esta versión, notará la diferencia. En la línea 16, estoy otra vez que se declara una variable llamada búfer, pero ¿qué pasa ahora? Es un conjunto de 16 caracteres. Esto es bueno porque significa que ahora puedo decir scanf aquí es un pedazo real de memoria. Casi se puede pensar en arrays como punteros ahora, a pesar de que no son realmente equivalentes. Ellos se comportan de manera diferente en diferentes contextos. Pero es cierto que búfer hace referencia 16 caracteres contiguos porque eso es lo que una matriz es y ha sido durante algunas semanas. 

He aquí, yo estoy diciendo scanf aquí hay un trozo de memoria. Esta vez, es en realidad una parte de la memoria, pero ¿por qué es este programa todavía explotable? ¿Qué hay de malo todavía? Lo he dicho dame 16 bytes pero- [Estudiante] ¿Y si se escribe en más de 16? Exactamente, ¿qué pasa si el usuario escribe en 17 caracteres o caracteres 1700? De hecho, vamos a ver si no se tropiece con este error ahora. Es mejor, pero no es perfecto. Déjenme seguir adelante y hacer funcionar scanf3 para compilar este programa. Déjame correr scanf3, String por favor: hola, y parece que estamos bien. Voy a tratar uno ligeramente más largo, hola. Bueno, vamos a hacerlo hola ¿cómo estás hoy, Enter. Conseguir tipo de suerte aquí, vamos a decir hola cómo estás. Maldita sea. Muy bien, así que tuvimos suerte. Vamos a ver si podemos arreglar esto. No, no va a dejar que me copia. Vamos a intentarlo de nuevo. De acuerdo, espera. Vamos a ver cuánto tiempo puede pretender concentrar sin dejar de hacer esto. Maldita sea. Eso es bastante apropiado, en realidad. Ahí vamos. Punto de hecho. 

Esto, embarazoso aunque también es, también es una de las fuentes de gran confusión al escribir programas que tienen errores, ya que se manifiestan sólo de vez en cuando a veces. La realidad es que incluso si el código está completamente roto, sólo podría ser completamente roto de vez en cuando porque a veces, lo que pasa es esencialmente el sistema operativo asigna un poco más de memoria de lo que realmente necesita por cualquier razón, y para que nadie más está usando la memoria inmediatamente después de su trozo de 16 caracteres, así que si vas a 17, 18, 19, lo que sea, no es una gran cosa. Ahora, el equipo, incluso si no choque en ese punto, eventualmente podría utilizar el byte número 17 o 18 o 19 años para otra cosa, momento en el que los datos que usted puso en su lugar, aunque sea excesivamente largo, va a ser sobrescrito potencialmente por alguna otra función. No necesariamente va a permanecer intacta, pero no necesariamente causará un fallo seg. Pero en este caso, finalmente me proporcionó suficientes caracteres que esencialmente superado mi segmento de la memoria, y bam, el sistema operativo, dijo: "Lo siento, eso no es culpa bueno, segmentación". 

Y ahora vamos a ver si lo que queda aquí en mi directorio cuenta de que tengo este archivo aquí, el núcleo. Tenga en cuenta que esto se volvió a pedir un volcado de memoria. Básicamente se trata de un archivo que contiene el contenido de la memoria del programa en el punto en el que se estrelló, y sólo para probar un pequeño ejemplo aquí déjame entrar aquí y ejecutar gdb en scanf3 y especifique un tercer argumento llamado núcleo, y notar aquí que si la lista de códigos, vamos a ser capaces, como de costumbre con gdb para empezar a caminar a través de este programa, y puedo correr y tan pronto como me golpeó, como paso con el comando en gdb- tan pronto como llegué a la línea potencialmente con errores después de escribir en una cadena enorme, Voy a ser capaz de identificar realmente aquí. Más sobre esto, sin embargo, en la sección en términos de volcados de memoria y similar, de manera que en realidad se puede hurgar en el interior del volcado de memoria y ver en qué línea del programa que falló. Cualquier pregunta entonces sobre indicadores y sobre las direcciones? Porque hoy en adelante, vamos a empezar a dar por sentado que estas cosas existen y sabemos exactamente lo que son. Sí. 

[Estudiante] ¿Cómo es que usted no tiene que poner un signo al lado de la parte- Buena pregunta. ¿Cómo llego no tenía que poner un signo al lado de la matriz de caracteres como lo hice anteriormente con la mayoría de nuestros ejemplos? La respuesta corta es arrays son un poco especial. Casi se puede pensar como un amortiguador en realidad ser una dirección, y da la casualidad de ser el caso que la notación de corchetes es una conveniencia para que podamos entrar en soporte 0, soporte 1, soporte 2, sin tener que utilizar la notación *. Eso es un poco de una mentira piadosa porque arrays y punteros son, de hecho, un poco diferente, pero pueden a menudo, pero no siempre se usan de forma intercambiable. En resumen, cuando una función espera un puntero a un bloque de memoria, usted puede pasar una dirección que fue devuelto por malloc, y vamos a ver malloc nuevo antes de tiempo, o puede pasar el nombre de una matriz. Usted no tiene que hacer arreglos con ampersand porque ya están esencialmente como direcciones. Esa es la única excepción. Los corchetes hacen especiales. 

¿Podría poner un signo al lado del buffer? No en este caso. Eso no funcionaría porque, de nuevo, este caso de esquina donde las matrices no son realmente muy direcciones. Pero tal vez volveremos a que en poco tiempo con otros ejemplos. Vamos a tratar de resolver un problema. Tenemos una estructura de datos que hemos estado utilizando desde hace algún tiempo se conoce como una matriz. El caso en cuestión, eso es lo que acabamos de tener. Pero matrices tienen algunos upsides y desventajas. Las matrices son agradables por qué? ¿Qué es una cosa que se quiere-en la medida en que te gusta matrices-acerca de las matrices? ¿Qué es conveniente acerca de ellos? ¿Qué es convincente? ¿Por qué los introducimos en el primer lugar? Si. [Estudiante] Se puede almacenar una gran cantidad de datos, y usted no tiene que usar una cosa entera. Puede utilizar una sección. Bueno, con un arsenal que puede almacenar una gran cantidad de datos, y no necesariamente tiene que utilizar todo eso, así que usted puede overallocate, que podría ser conveniente si usted no sabe de antemano cuántos de algo que esperar. 

GetString es un ejemplo perfecto. GetString, escrito por nosotros, no tiene idea de cómo chars que cabe esperar, por lo que el hecho de que se puede asignar trozos de memoria contigua es bueno. Las matrices también resolver un problema que vimos un par de semanas ahora donde el código empieza a delegar en algo muy mal diseñado. Recordemos que he creado una estructura estudiante llamado David, y entonces que era en realidad una alternativa, sin embargo, a tener un nombre de variable llamada y otra variable llamada, creo, casa, y otra variable llamada identificación porque en esa historia que entonces quería introducir algo más Al igual que Rob en el programa, por lo que luego decidí esperar un minuto, Tengo que cambiar el nombre de estas variables. Vamos a llamar a la mía nombre1, ID1, house1. Vamos a llamar a Rob nombre2, casa2, ID2. Pero espera un momento, ¿qué pasa con Tommy? Luego tuvimos tres variables más. Hemos introducido algún otro, cuatro conjuntos de variables. El mundo comenzó a causar problemas muy rápidamente, por lo que introdujo las estructuras, y lo que es atractivo en una estructura? ¿Qué hace un struct C permiten hacer? Es muy difícil hoy en día. ¿Qué? >> [Respuesta de los estudiantes inaudible] Sí, en concreto, typedef permite crear un nuevo tipo de datos, y estructura, la palabra clave struct, le permite encapsular piezas relacionadas conceptualmente de datos, junto y después de eso los llaman algo así como un estudiante. 

Eso fue bueno, porque ahora podemos modelar especie mucho más conceptualmente coherente la noción de un estudiante en una variable en lugar de tener una forma arbitraria para una cadena, una para un ID, y así sucesivamente. Las matrices son agradables porque nos permite comenzar a limpiar nuestro código. Pero lo que es un inconveniente ahora de una matriz? Lo que no puede hacer? Si. [Estudiante] Usted tiene que saber lo grande que es. Usted tiene que saber lo grande que es, así que es un tipo de dolor. Aquellos de ustedes que tienen experiencia previa en programación saben que en una gran cantidad de idiomas, como Java, usted puede pedir un trozo de memoria, en concreto una matriz, lo grande que eres, con una longitud, posición económica, por así decirlo, y eso es muy conveniente. En C, ni siquiera se puede llamar strlen en una matriz genérica porque strlen, como la palabra lo indica, es sólo para cuerdas, y se puede calcular la longitud de una cadena a causa de esta convención humana de tener un 0 \, sino una matriz, más genéricamente, es sólo una parte de la memoria. Si se trata de una matriz de enteros, no va a ser algo de carácter especial al final te espera. Hay que recordar la longitud de una matriz. Otro aspecto negativo de una matriz levantado la cabeza en GetString sí mismo. ¿Cuál es otra desventaja de una matriz? Señor, sólo tú y yo hoy. [Respuesta de los estudiantes inaudible] >> ¿Es qué? Ha declarado en la pila. De acuerdo, declaró en la pila. ¿Por qué no te gusta? [Estudiante] Debido a que se reutilizan. Se reutilizan. Bueno, si se utiliza una matriz para asignar memoria, no se puede, por ejemplo, volver porque está en la pila. Bueno, eso es una desventaja. ¿Y otra con una matriz? Una vez que lo asigne, eres un poco jodido si necesita más espacio que la matriz tiene. 

A continuación presentamos, recordar, malloc, que nos dio la capacidad de asignar dinámicamente la memoria. Pero ¿y si intentamos un mundo totalmente diferente? ¿Qué pasa si queremos resolver un par de esos problemas así que en vez, mi pluma se ha dormido aquí- ¿Y si en vez quería crear esencialmente un mundo que ya no es así? Esta es una matriz, y, por supuesto, este tipo de se deteriora una vez que se pulsa el final de la matriz, y ahora ya no tiene espacio para otro número entero u otro carácter. ¿Qué pasaría si una especie de forma preventiva decir así, ¿por qué no relajarse Este requisito de que todos estos pedazos de memoria sean contiguos espalda con espalda, y por qué no, cuando necesito un int o char a, me acaba de dar espacio para una de ellas? Y cuando necesito otro, dame otro espacio, y cuando necesito otro, dame otro espacio. La ventaja de que ahora es que si alguien más toma la memoria por aquí, nada del otro mundo. Me quedo con este trozo adicional de memoria aquí y después de éste. 

Ahora, el único problema aquí es que este casi se siente como si tuviera un montón de diferentes variables. Esto se siente como cinco diferentes variables potencialmente. Pero ¿y si nos roban una idea de las cadenas de alguna manera en que podamos vincular estas cosas conceptualmente, y lo que si me hizo esto? Este es mi flecha muy mal dibujado. Pero supongamos que cada uno de estos trozos de la memoria señaló a la otra, y este chico, que no tiene hermanos, a su derecha, no tiene ninguna flecha tales. Esto es de hecho lo que se llama una lista enlazada. Esta es una nueva estructura de datos que nos permite asignar un bloque de memoria, luego otro, luego otro, luego otro, cada vez que queramos durante un programa, y ​​recordamos que todos están de alguna manera relacionados con literalmente encadenar juntos, y lo hicimos aquí gráficamente con una flecha. Pero en el código, ¿cuál sería el mecanismo a través del cual usted puede conectar de alguna manera, casi como Scratch, un fragmento a otro pedazo? Podríamos utilizar un puntero, ¿verdad? Porque, en realidad la flecha que va desde la plaza superior izquierda, este tipo aquí a esta, podría contener dentro de este cuadrado no sólo algunos enteros, no sólo algunos char, pero lo que si realmente asignados un poco más de espacio para que ahora, cada uno de mis pedazos de la memoria, a pesar de que esto va a costar, ahora se ve un poco más rectangular donde uno de los trozos de memoria se utiliza para un número, como el número 1, y luego, si este chico almacena el número 2, este fragmento otro de memoria se utiliza para una flecha, o más concretamente, un puntero. Y supongo que guardar el número 3 por aquí mientras yo uso esto para apuntar a ese tipo, y ahora este tipo, vamos a suponer que sólo quiere tres pedazos tales de la memoria. Voy a dibujar una línea a través de eso, lo que indica nulo. No hay un carácter adicional. 

De hecho, así es como podemos ir sobre la aplicación algo que se llama una lista enlazada. Una lista enlazada es una estructura de datos nueva, y es un paso adelante hacia mucho más elegantes estructuras de datos que comienzan a resolver problemas a lo largo de las líneas de los problemas de tipo Facebook y Google problemas de tipo donde hay enormes conjuntos de datos, y ya no se corta para almacenar todo contigua y usar algo como búsqueda lineal o incluso algo como búsqueda binaria. ¿Quieres aún mejores tiempos de carrera. De hecho, uno de los santos griales hablaremos más adelante esta semana o la próxima es un algoritmo cuyo tiempo de ejecución es constante. En otras palabras, siempre se toma la misma cantidad de tiempo, sin importar lo grande que es la entrada, y que de hecho sería convincente, incluso más que algo logarítmica. ¿Qué es esto en la pantalla aquí? Cada uno de los rectángulos es exactamente lo que acaba de dibujar a mano. Pero lo que todo el camino de la izquierda es una variable especial. Va a ser un único puntero porque el gotcha una con una lista enlazada, como se llaman estas cosas, es que usted tiene que colgar en un extremo de la lista enlazada. 

Al igual que con una cadena, usted tiene que saber la dirección del primer carácter. Mismo trato para las listas enlazadas. Usted tiene que saber la dirección del primer fragmento de memoria porque a partir de allí, se puede llegar a cualquier otro. Lo malo. ¿Qué precio estamos pagando por esta versatilidad de tener una dinámica estructura de datos importante que si alguna vez necesita más memoria, está bien, sólo asignar un pedazo más y dibujar un puntero de la vieja a la nueva cola de la lista? Si. [Estudiante] Se necesita espacio de aproximadamente dos veces más. Se necesita espacio doble, así que eso es definitivamente una desventaja, ya que hemos visto este equilibrio entre antes de tiempo y espacio y flexibilidad donde por ahora, no necesitamos 32 bits para cada uno de estos números. Realmente necesitamos 64, 32 para el número y 32 para el puntero. Pero bueno, tengo 2 GB de RAM. Un aumento de 32 bits aquí y aquí no parece tan grande de un acuerdo. Sin embargo, para los conjuntos de datos de gran tamaño, que sin duda se suma a, literalmente, el doble. ¿Cuál es otra desventaja ahora, o qué función le damos para arriba, si representamos listas de cosas con una lista enlazada y no una matriz? [Estudiante] No se puede recorrer hacia atrás. No se puede recorrer hacia atrás, así que eres un poco jodidos si tu te vas de izquierda a derecha utilizando un bucle o un bucle while y entonces te das cuenta, "Oh, yo quiero ir de nuevo al principio de la lista." No es posible porque estos punteros sólo van de izquierda a derecha, como indican las flechas. 

Ahora, usted puede recordar el principio de la lista con otra variable, pero eso es una complejidad a tener en cuenta. Una matriz, no importa lo lejos que vaya, siempre puede hacer menos, menos, menos, menos y vuelve de donde viniste. ¿Cuál es otra desventaja aquí? Si. [Pregunta estudiante inaudible] Podría, por lo que ha hecho que acaba de proponer una estructura de datos llamada lista doblemente enlazada, y, de hecho, debería agregar otro puntero a cada uno de estos rectángulos que va la otra dirección, la ventaja de que Ahora se puede recorrer de ida y vuelta, la desventaja de que ahora se está utilizando tres veces más memoria que usamos para y también añadir complejidad en términos del código que tiene que escribir para hacerlo bien. Pero todos estos son quizás las compensaciones razonables, si la inversión es más importante. Si. [Estudiante] Tampoco se puede tener una lista enlazada 2D. Bueno, realmente no se puede tener una lista 2D vinculado. Podrías. No es tan fácil como una matriz. Al igual que una matriz, hacer corchete abierto, soporte cerrado, soporte abierto, cerrado soporte, y se obtiene una estructura de 2 dimensiones. Se podría implementar una lista de 2 dimensiones vinculadas Si lo hace, como usted propone-un tercer indicador para cada una de estas cosas, y si piensas en otra lista que le llega estilo 3D de la pantalla para todos nosotros, que es otra cadena de algún tipo. Podríamos hacerlo, pero no es tan simple como escribir apertura de corchetes, corchetes. Si. [Pregunta estudiante inaudible] Bien, así que esto es un truco real. 

Estos algoritmos que hemos suspirado otra vez, como oh, búsqueda binaria, usted puede buscar en una matriz de números en el tablero o una libreta de teléfonos mucho más rápidamente si utiliza divide y vencerás y un algoritmo de búsqueda binaria, pero la búsqueda binario requiere dos supuestos. Uno de ellos, que los datos fueron ordenados. Ahora, probablemente pueda mantener esta resuelto, así que tal vez eso no es una preocupación, pero también supone la búsqueda binaria que tenía acceso aleatorio a la lista de números, y una gran variedad le permite tener acceso al azar, y por el acceso aleatorio, Quiero decir que si te dan una serie, ¿cuánto tiempo le toma para llegar al soporte de 0? Una operación, usted sólo tiene que utilizar [0] y ya está ahí. ¿Cuántos pasos se necesitan para llegar a la ubicación 10? Un paso, usted sólo tiene que ir a [10] y que estás ahí. Por el contrario, ¿cómo se consigue que el entero 10 en una lista enlazada? Hay que empezar por el principio, ya que sólo está recordando el comienzo de una lista enlazada, al igual que una cadena se recuerda por la dirección de su primer carácter, y al ver que int 10a o que el carácter 10 º en una cadena, usted tiene que buscar toda la maldita cosa. 

Una vez más, no vamos a resolver todos nuestros problemas. Estamos introduciendo otros nuevos, pero realmente depende de lo que estés tratando de diseñar para. En cuanto a la aplicación de la presente, se puede pedir prestada una idea de que la estructura de los estudiantes. La sintaxis es muy similar, excepto que ahora, la idea es un poco más abstracto que la casa y el nombre y DNI. Pero yo propongo que podría tener una estructura de datos en C que se llama nodo, como la última palabra en la diapositiva indica, dentro de un nodo, y un nodo es un contenedor genérico en ciencias de la computación. Por lo general se dibuja como un círculo o un cuadrado o un rectángulo como lo hemos hecho. Y en esta estructura de datos, tenemos un entero, n, por lo que es el número que desea almacenar. Pero ¿qué es esta segunda línea, struct nodo * siguiente? ¿Por qué es correcto o qué papel desempeña esa cosa, aunque es un poco críptico, a primera vista? Si. [Respuesta de los estudiantes inaudible] Exactamente, por lo que el tipo de botín * que es un puntero de algún tipo. El nombre de este puntero es arbitrariamente próximo, pero nos podría haber llamado cualquier cosa que queramos, pero ¿qué tiene esto puntero a punto? [Estudiante] Otro nodo. >> Exactamente, apunta a otro nodo tal. 

Ahora, esto es una especie de curiosidad de C. Recordemos que C es leído por un compilador arriba a abajo, de izquierda a derecha, lo que significa que si, esto es un poco diferente de lo que hemos hecho con el estudiante. Cuando definimos un estudiante, que en realidad no puso una palabra allí. Simplemente dijo typedef. Luego tuvimos id int nombre, cadena, cadena de casa, y luego estudiante en la parte inferior de la estructura. Esta declaración es un poco diferente, ya que, de nuevo, el compilador de C es un poco tonto. Es sólo va a leer de arriba a abajo, así que si llega a la 2 ª línea aquí donde se declara próximo y lo ve, oh, aquí está una variable llamada siguiente. Es un puntero a un nodo de estructura. El compilador se va a dar cuenta lo que es un nodo de estructura? Nunca he oído hablar de esto antes, porque el nodo de palabra de otro modo no podría aparecer hasta la parte inferior, por lo que es esta redundancia. Tienes que decir struct nodo aquí, que luego se puede acortar más tarde gracias a typedef aquí abajo, pero es porque estamos haciendo referencia a la estructura en sí misma en el interior de la estructura. Ese es el gotcha nadie allí. 

Algunos problemas interesantes van a surgir. Tenemos una lista de números. ¿Cómo insertar en ella? ¿Cómo podemos buscarla? ¿Cómo borrar de ella? Sobre todo ahora que tenemos que manejar todos estos consejos. Usted pensó que eran punteros especie de alucinante cuando tenía uno de ellos tratando de leer un int a ella. Ahora tenemos que manipular la pena una lista entera. ¿Por qué no nos tomamos nuestro hijo de 5 minutos de descanso aquí, y luego voy a traer algunas personas al escenario para hacer exactamente eso. 

C es mucho más divertido cuando es representada. Que literalmente quiere ser el primero? Muy bien, vamos arriba. Usted está en primer lugar. ¿Quién quiere ser 9? Bueno, 9. ¿Qué hay de 9? 17? Una camarilla poco aquí. 22 y 26 en la fila delantera. Y entonces ¿qué hay alguien por ahí que se la mira. Usted es 34. Bueno, de 34 años, vamos arriba. En primer lugar está allá. Bueno, los cuatro de ustedes. ¿Y quién le decimos a 9? ¿Quién es nuestro 9? ¿Quién realmente quiere ser 9? Muy bien, vamos, a las 9. Aquí vamos. 34, nos encontraremos allí. La primera parte es haceros ver así. 26, 22, 17, bueno. Si puedes soportar a un lado, porque nos vamos a malloc en un momento. 

Bueno, bueno. Está bien, excelente, así que vamos a hacerle un par de preguntas. Y en realidad, ¿cuál es tu nombre? >> Anita. Anita, está bien, ven aquí. Anita va a ayudarnos a resolver un tipo de pregunta bastante simple en principio, que es ¿cómo encontrar si un valor está en la lista? Ahora, noten que la primera, representada aquí por Lucas, es un poco diferente, por lo que su papel es deliberadamente de lado porque no es tan alto y no ocupa tantos bits, a pesar de que técnicamente tiene el mismo tamaño de papel que acaba de girar. Pero es un poco diferente, ya que tiene sólo 32 bits para un puntero, y todos estos chicos son de 64 bits, la mitad de los cuales es el número, la mitad de los cuales es un puntero. Sin embargo, el puntero no se representa, por lo tanto si ustedes podrían torpemente use la mano izquierda para apuntar a la persona a tu lado. Y tú eres el número 34. ¿Cuál es tu nombre? Ari. Ari, por lo que en realidad, mantenga el papel en la mano derecha y la mano izquierda va hacia abajo. Usted declara nula la izquierda. 

Ahora nuestra imagen humana es muy consistente. Esto es realmente cómo funcionan los punteros. Y si se puede arrugar un poco esta manera así que no estoy en tu camino. Anita aquí, me encontrará el número 22, pero suponen una restricción de los seres humanos no soporta hojas de papel, pero esta es una lista, y sólo tiene Lucas para empezar porque es, literalmente, el primer indicador. Supongamos que usted mismo es un puntero, y por lo que también tienen la capacidad de apuntar a algo. ¿Por qué no empezar por señalar exactamente lo que Lucas está señalando? Bueno, y déjame promulgar esto por aquí. Sólo por el bien de la discusión, deja que tire hacia arriba una página en blanco aquí. ¿Cómo se escribe tu nombre? >> Anita. Bueno, Anita. Digamos nodo * anita = lucas. Bueno, no os llama lucas. Deberíamos llamar a usted primero. ¿Por qué es de hecho compatible con la realidad aquí? Uno, en primer lugar ya existe. En primer lugar se ha asignado presumiblemente en algún lugar por aquí. Nodo * primero, y se ha asignado una lista de alguna manera. No sé cómo sucedió. Eso ocurrió antes de que empezara la clase. Esta lista vinculada de los seres humanos ha sido creada. Y ahora, en este momento de la historia, todo esto sucede en Facebook, aparentemente después- en este punto de la historia, Anita se ha inicializado a ser igual al primero, lo que no significa que los puntos de Anita en Lucas. Más bien, apunta a lo que apunta a porque la misma dirección que está dentro de los 32 bits - Lucas 1, 2, 3 - es ahora también en el interior de Anita 32 bits - 1, 2, 3. 

Encuentre ahora 22. ¿Cómo haría usted para hacer esto? ¿Qué es ese punto? >> Para lo que sea. Señale lo que sea, así que adelante y representarlo lo mejor que puedes aquí. Bien, bien, y ahora usted está señalando, ¿cuál es tu nombre con 22? Ramon. >> Ramón, por lo que Ramón es la celebración de 22. Ahora ha hecho un cheque. ¿Tiene Ramon == 22, y si es así, por ejemplo, se puede volver realidad. Permítanme, mientras estos chicos están aquí algo torpemente- déjame hacer algo rápidamente como bool encontrar. Voy a seguir adelante y decir (lista de nodos *, int n). Estaré de vuelta con ustedes. Sólo tengo que escribir algo de código. Y ahora voy a seguir adelante y hacer esto, el nodo * anita list =. Y voy a seguir adelante y decir while (anita! = NULL). 

La metáfora aquí es conseguir un poco estirado, pero al mismo tiempo (anita! = NULL), ¿qué es lo que quiero hacer? Necesito alguna manera de hacer referencia a el entero que Anita está señalando. En el pasado, cuando tuvimos estructuras, que es un nodo, hemos utilizado la notación de puntos, y nos diría algo así como anita.n, pero el problema aquí es que Anita no es una estructura en sí. ¿Qué es? Ella es un puntero, así que realmente, si queremos usar esta notación punto- y esto va a parecer un poco críptico deliberadamente- tenemos que hacer algo como ir a mano izquierda lo que Anita está apuntando a y luego el campo llamado n. Anita es un puntero, pero lo que es * anita? ¿Qué encuentras cuando vas a lo que Anita está señalando? Una estructura, un nodo, y una retirada nodo,, tiene un campo llamado n porque ha, recuerdan, estos dos campos, próximos y N, que vimos hace un momento aquí. 

Para imitar este hecho en el código, podríamos hacer esto y decir if ((* anita). == n n), la n que yo estoy buscando. Observe que la función se aprobó en el número que me importa. Entonces puedo seguir adelante y hacer algo como verdadero retorno. Si no, si ese no es el caso, ¿qué es lo que quiero hacer? ¿Cómo traduzco para codificar lo que Anita hizo intuitivamente a pie a través de la lista? ¿Qué debo hacer aquí para simular Anita dar ese paso a la izquierda, ese paso hacia la izquierda? [Respuesta de los estudiantes inaudible] >> ¿Qué es eso? [Respuesta de los estudiantes inaudible] Bueno, no es una mala idea, pero en el pasado, cuando hayamos hecho esto, hemos hecho anita + + porque eso aumentaría el número 1 a Anita, que normalmente apuntar a la siguiente persona, al igual que Ramón, o la persona a su lado, o la persona a su lado de la línea. Pero eso no es muy bueno, porque lo que aquí está esta cosa parece en la memoria? No es eso. Tenemos que desactivar eso. Parece que este en la memoria, y aunque he dibujado 1 y 2 y 3 cerca uno del otro, si realmente simular que esta-can chicos, sin dejar de apuntar a la misma gente, Puede que algunos de ustedes dar un paso atrás al azar, algunos de ustedes un paso adelante al azar? 

Este desorden es todavía una lista enlazada, pero estos chicos pueden estar en cualquier lugar en la memoria, así anita + + no va a funcionar eso? Lo que está en posición anita + +? Quién sabe. Es otro valor que el que pasa es que se interpone entre todos estos nodos de azar porque no estamos usando una matriz. Hemos asignado cada uno de estos nodos de forma individual. Bueno, si ustedes mismos pueden limpiar de nuevo. Permítanme proponer que en lugar de anita + +, que en vez hacer anita se- bien, ¿por qué no nos vamos a lo que Anita está señalando y luego hacer. después? En otras palabras, vamos a Ramón, que está sosteniendo el número 22, y entonces. siguiente es como si Anita se copia el puntero izquierdo. Pero ella no quiso ir más allá de Ramón porque encontramos 22. Pero esa sería la idea. Ahora, esto es un lío espantoso. Honestamente, nadie va a recordar esta sintaxis, y por suerte, en realidad es un poco deliberada-oh, no vio lo que escribí. Esto sería más convincente si pudiera. Voila! 

Detrás de las escenas, estaba resolviendo el problema de esta manera. Anita, para dar el paso a la izquierda, en primer lugar, que te vayas a la dirección que Anita está apuntando a y en la que se encuentra no sólo n, que acaba de comprobar para efectos de comparación, pero también se encuentra próximo - en este caso, Ramon mano izquierda apuntando al siguiente nodo en la lista. Pero este es el lío espantoso al que me he referido antes, pero resulta que C nos permite simplificar esto. En lugar de escribir (* anita), se puede en lugar de simplemente escribir anita-> n, y es exactamente lo mismo funcionalmente, pero es mucho más intuitivo, y es mucho más coherente con la imagen que hemos venido señalando todo este tiempo utilizando flechas. 

Por último, ¿qué es lo que tenemos que hacer al final de este programa? Hay una línea de código restante. Volver ¿qué? Falso, porque si llegamos a través de todo el ciclo while y Anita es, de hecho, null, eso significa que ella fue todo el camino hasta el final de la lista donde ella señalaba, ¿cuál es tu nombre? Mano izquierda Ari. >> Ari, que es nulo. Anita es ahora nula, y me doy cuenta de que usted está aquí de pie con torpeza en el limbo porque me estoy yendo por un monólogo aquí, pero te involucran de nuevo en un momento. Anita es nulo en ese punto de la historia, por lo que el bucle while termina, y tenemos que volver falsa, porque si ella tiene todo el camino a puntero nulo Ari entonces no había un número que buscó en la lista. Podemos limpiar esto también, pero esta es una aplicación muy buena entonces de una función de recorrido, una función para encontrar una lista enlazada. Aún búsqueda lineal, pero no es tan simple como un puntero + + + + o una variable i porque ahora no podemos adivinar donde cada uno de estos nodos están en la memoria. Tenemos que seguir literalmente el rastro de migas de pan o, más específicamente, punteros, para ir de un nodo a otro. 

Ahora vamos a probar con la otra. Anita, ¿quieres volver aquí? ¿Por qué no seguir adelante y asignar a otra persona de la audiencia? Malloc-¿cómo te llamas? >> Rebecca. Rebecca. Rebecca ha sido malloced de la audiencia, y ella está almacenando el número 55. Y el objetivo que nos ocupa ahora es que Anita para insertar Rebecca a la lista enlazada aquí en su lugar apropiado. Ven aquí un momento. Yo he hecho algo como esto. He hecho * nodo. ¿Y cuál es tu nombre? Rebecca. >> Rebecca, está bien. Rebecca se malloc (sizeof (nodo)). Al igual que hemos destinado cosas como los estudiantes y otras cosas en el pasado, necesitamos el tamaño del nodo, por lo que Rebecca ahora está señalando en qué? Rebecca tiene dos campos dentro de ella, uno de los cuales es 55. Vamos a hacer lo que, rebecca-> = 55. Pero entonces rebecca-> siguiente debe ser-como ahora, con la mano es una especie de ¿quién sabe? Está apuntando a un cierto valor basura, así que ¿por qué no hacer una buena medida que por lo menos hacer esto para que la mano izquierda está ahora a su lado. Ahora Anita, a partir de aquí. Hay que Rebecca se le hayan asignado. Seguir adelante y encontrar dónde debemos poner Rebecca. Bien, muy bien. Bueno, bueno, y ahora necesitamos que nos proporcione un poco de dirección, por lo que ha llegado a Ari. Su mano izquierda es nulo, pero Rebecca pertenece claramente a la derecha, así que ¿cómo hemos de modificar esta lista enlazada con el fin de insertar Rebecca en el lugar apropiado? Si usted puede literalmente mover las manos de la gente de izquierda en torno a como sea necesario, vamos a arreglar el problema de esa manera. Bueno, bueno, y mientras tanto, la mano izquierda de Rebecca es ahora a su lado. 

Eso fue demasiado fácil. Vamos a tratar de asignar-estamos casi listos, 20. Muy bien, vamos arriba. 20 ha sido asignado, así que voy a seguir adelante y decir otra vez aquí que acabamos de hacer saad nodo *. Tenemos malloc (sizeof (nodo)). A continuación, hacer la misma sintaxis exacta como lo hicimos antes para 20, y yo haré lo siguiente = NULL, y ahora le toca a Anita que se inserta en la lista enlazada, si pudieras jugar ese mismo papel exacto. Ejecutar. Bien, bien. Ahora piensa detenidamente antes de empezar a mover las manos izquierda alrededor. Usted tiene, con mucho, el papel más difícil hoy en día. Cuya mano se movió por primera vez? Bueno, espera, estoy escuchando algunos no. Si algunas personas cortésmente le gustaría ayudar a resolver una situación difícil aquí. Cuya mano izquierda debe ser actualizado primero, tal vez? Si. [Estudiante] Saad. Bueno, Saad, ¿por qué, entonces? [Respuesta de los estudiantes inaudible] Bien, porque si nos movemos, ¿cuál es tu nombre? >> Marshall. Marshall, si movemos la mano primero y diez en null, ahora hemos literalmente huérfanos a cuatro personas en esta lista porque era lo único que señala en el Ramón y todo el mundo a la izquierda, por lo que la actualización primer indicador era malo. Vamos a deshacer eso. Bueno, y ahora seguir adelante y mover la mano izquierda apuntando al adecuado Ramon. Esto se siente un poco redundante. Ahora hay dos personas apuntando a Ramón, pero eso está bien porque ahora qué otra manera podemos actualizar la lista? Lo que por otra parte se tiene que mover? Muy bien, ahora hemos perdido la memoria? No, todo va bien, vamos a ver si no podemos romper una vez más. 

Mallocing por última vez, el número 5. Todo el camino de vuelta, vamos hacia abajo. Es muy emocionante. [Aplauso] ¿Cuál es tu nombre? >> Ron. Ron, está bien, está malloced como el número 5. Acabamos de ejecutar código que es casi idéntica a estos con un nombre diferente. Excelente. Ahora, Anita, buena suerte insertar el número 5 en la lista ahora. Bueno, ¿y? Muy bien, así que esto es realmente el tercero de los tres casos totales. Primero tuvimos a alguien en la final, Rebecca. Luego tuvimos a alguien en el medio. Ahora tenemos a alguien en el comienzo, y en este ejemplo, que ahora tenía que actualizar Lucas por primera vez porque el primer elemento en la lista ahora tiene que apuntar a un nuevo nodo, que, a su vez, se señala en el número de nodo 9. 

Esta fue una demostración enormemente difícil, estoy seguro, por lo que un gran aplauso para estos chicos si pudieras. Muy bien hecho. Eso es todo. Usted puede guardar sus trozos de papel como un poco de memoria. Resulta que haciendo esto en el código no es tan simple como mover las manos en torno a y apuntando los punteros en diferentes cosas. Pero darse cuenta de que cuando llegue el momento de poner en práctica algo así como una lista enlazada o una variante del mismo, si te centras en realidad estos fundamentos básicos, los problemas de tamaño de un bocado que tengo que averiguar, ¿es esta mano o la mano de esto, darse cuenta de que lo que es un programa bastante complejo puede, de hecho, ser reducido a elementos básicos bastante simples como este. 

Vamos a tomar las cosas en una dirección más sofisticado aún. Ahora tenemos la noción de la lista enlazada. También tenemos, gracias a la sugerencia de volver allí, una lista doblemente enlazada, que se ve casi lo mismo, pero ahora tenemos dos punteros dentro de la estructura en vez de uno, y probablemente podríamos llamar los punteros anterior y siguiente o hacia la izquierda o hacia la derecha, pero, de hecho, la necesidad de dos de ellos. El código debería ser un poco más complicado. Anita habría tenido que hacer más trabajo aquí en el escenario. Pero sin duda podríamos poner en práctica ese tipo de estructura. En términos de tiempo de ejecución, sin embargo, ¿cuál sería el tiempo de ejecución para Anita de encontrar un número n en una lista enlazada ahora? Aún así gran O de n, así que no es mejor que la búsqueda lineal. No podemos hacer una búsqueda binaria, aunque, de nuevo. ¿Por qué fue así? No se puede saltar alrededor. A pesar de que, obviamente, ver todos los humanos en el escenario, y Anita podría haberlo eyeballed y dijo: "Aquí está la mitad de la lista," ella no sabe que si ella fuera el programa de ordenador porque lo único que tenía que aferrarse a al comienzo del escenario fue Lucas, que fue el primer indicador. Ella necesariamente tendría que seguir esos vínculos, contando su camino hasta que encontró aproximadamente la mitad, y aun así, ella no va a saber cuando ella llegó a la mitad a menos que ella va todo el camino hasta el final para saber cuántos son, luego da marcha atrás, y eso también sería difícil a menos que usted tenía una lista doblemente enlazada de algún tipo. 

Solución de problemas hoy, pero introduciendo otros. ¿Qué pasa con una estructura de datos completamente diferente? Esta es una fotografía de las bandejas en Mather House, y en este caso, tenemos una estructura de datos también hemos de tipo ya se ha hablando. Hablamos de una pila en el contexto de la memoria, y que es una especie de llamado porque deliberadamente una pila en los términos de la memoria es efectivamente una estructura de datos que tiene más cosas y más capas en la parte superior de la misma. Pero lo interesante de una pila, como es el caso en la realidad, es que es un tipo especial de estructura de datos. Es una estructura de datos mediante el cual el primer elemento de es el último elemento fuera. Si es la primera bandeja que se pone en la pila, que va a ser desgraciadamente la última bandeja a ser retirado de la pila, y eso no es necesariamente algo bueno. Por el contrario, se puede pensar que al revés, es el último de los primeros en salir. 

Ahora, ¿algún escenario vienen a la mente las que tener una pila estructura de datos donde se tiene que la propiedad el último en entrar, primero en salir, es realmente convincente? ¿Eso es bueno? ¿Eso es malo? Es definitivamente algo malo si las bandejas no eran todos idénticos y todos eran diferentes colores especiales o lo que sea, y el color que quiero es todo el camino en la parte inferior. Por supuesto, usted no puede conseguir que, sin gran esfuerzo. Hay que empezar por la parte superior y trabaje hacia abajo. Del mismo modo, ¿qué pasaría si usted fuera uno de esos chicos del ventilador que espera toda la noche tratando de conseguir un iPhone y comarca en un lugar como este? ¿No sería agradable si la tienda de Apple eran una estructura de datos de la pila? Yay? Nay? Sólo es bueno para las personas que aparecen en el último minuto y luego se sacó de la cola. Y de hecho, el hecho de que estaba inclinado de manera que decir cola en realidad es consistente con lo que podríamos llamar este tipo de estructura de datos, una realidad en donde el orden no importa, y desea que el primero en ser el primero en salir aunque sólo sea por el bien de la justicia humana. Por lo general, voy a llamar a eso una estructura de datos cola. 

Resulta que además de las listas enlazadas, podemos empezar a usar estas mismas ideas básicas y empezar a crear nuevos y diferentes tipos de soluciones a los problemas. Por ejemplo, en el caso de una pila, que podría representar una pila utilizando una estructura de datos como este, me gustaría proponer. En este caso, he declarado una estructura, y lo he dicho en el interior de esta estructura es una matriz de números y después una variable llamada, y yo voy a llamar a esto una pila. Ahora, ¿por qué esta realidad? En el caso de una pila, podría sacar esto de manera efectiva en la pantalla como una matriz. Aquí está mi stack. Esos son mis números. Y vamos a dibujar como esto, esto, esto, esto, esto. Y luego tengo algún miembro de datos distinto aquí, que se denomina tamaño, por lo que este es el tamaño, y esto es números, y colectivamente, el iPad entero aquí representa una estructura de pila. Ahora, por defecto, el tamaño presumiblemente tiene que ser inicializado a 0, y lo que hay dentro de la matriz de números inicialmente cuando por primera vez asignar una matriz? Garbage. ¿Quién sabe? Y en realidad no importa. No importa si es 1, 2, 3, 4, 5, completamente al azar por la mala suerte almacenada en la estructura de mi porque mientras yo sé que el tamaño de la pila es 0, entonces sé programación, no se ven en ninguno de los elementos de la matriz. No importa lo que hay. No mires a ellos, como sería la implicación de un tamaño de 0. 

Pero supongamos ahora sigo adelante e inserte algo en la pila. Quiero insertar el número 5, por lo que poner aquí el número 5, y luego lo pongo aquí abajo? Ahora realmente poner 1 para el tamaño, y ahora la pila es de tamaño 1. ¿Qué pasa si sigo adelante y añadir el número, digamos, 7 después? Esto luego se actualiza a 2, y luego haremos 9, y luego esta se actualiza a 3. Pero ahora la característica interesante de esta pila es que Se supone que debo quitar el elemento que si quiero hacer estallar algo fuera de la pila, por así decirlo? 9 sería lo primero que debe ir. ¿Cómo debe cambiar la imagen si quiero sacar un elemento de la pila, Al igual que una bandeja en Mather? Si. >> [Estudiante] Fijar el tamaño a 2. Exactamente, lo único que hacer es ajustar el tamaño a 2, y lo hago con la matriz? Yo no tengo que hacer nada. Podría, sólo para ser anal, poner un 0 o -1 allí o algo para significar que este no es un valor de fiar, pero eso no importa porque Puedo grabar fuera de la propia matriz cuánto tiempo es para que yo sepa solo se ve en los dos primeros elementos de esta matriz. Ahora, si me voy y agregar el número 8 de esta serie, ¿cómo cambiar la imagen a continuación? Esto se convierte en 8, y esto se convierte en 3. Voy a cortar algunas esquinas aquí. Ahora tenemos 5, 7, 8, y estamos de vuelta a un tamaño de 3. Esto es bastante fácil de implementar, pero ¿cuándo vamos a lamentar esta decisión de diseño? ¿Cuando las cosas empiezan a ir mal, muy mal? Si. [Respuesta de los estudiantes inaudible] Cuando desee volver atrás y obtener el primer elemento que usted pone adentro 

Resulta aquí a pesar de que una pila es una matriz debajo de la capucha, estas estructuras de datos que hemos comenzado hablando también se conoce generalmente como estructuras abstractas de datos por lo que la forma en que se implementen es completamente en este punto. Una estructura de datos como una pila que se supone para añadir soporte operaciones como de empuje, que empuja una bandeja en la pila, y el pop, que elimina un elemento de la pila, y eso es todo. Si se va a descargar código de otra persona que ya ha implementado eso que se llama una pila, esa persona habría escrito sólo dos funciones para usted, empuje y pop, cuyo único propósito en la vida sería hacer exactamente eso. Usted o él o ella quien implementó este programa habría sido enteramente el que decide cómo implementar la semántica de empujar y hacer estallar debajo de la capucha o la funcionalidad de empujar y hacer estallar. Y he tomado una decisión un tanto miope aquí mediante la implementación de mi stack con esta estructura de datos simple ¿por qué? Cuando se hace esta ruptura estructura de datos? ¿En qué momento tengo que devolver un error cuando el usuario llama a push, por ejemplo? [Estudiante] Si no hay más espacio. Exactamente, si hay espacio no más, si me he excedido la capacidad, que es todo en mayúsculas, ya que sugiere que se trata de una especie de constante global. Bueno, entonces me voy a tener que decir: "Lo siento, no puedo empujar otro valor en la pila ", al igual que en Mather. 

En algún momento, van a llegar a la parte superior de ese armario pequeño. No hay más espacio o la capacidad de la pila, momento en el que hay algún tipo de error. Tienen que poner el elemento en otro lugar, la bandeja en otro lugar, o nada en absoluto. Ahora, con una cola, podríamos aplicar un poco diferente. Una cola es un poco diferente en que debajo de la campana, se puede implementar como una matriz, pero ¿por qué, en este caso, estoy proponiendo tener también un elemento de cabeza que representa la cabeza de la lista, al frente de la lista, la primera persona en la fila en la tienda de Apple, además de tamaño? ¿Por qué necesito una pieza adicional de los datos en esta lista? Piense en lo que los números se si he elaborado la siguiente manera. Supongamos que esta es ahora una cola en lugar de una pila, con la diferencia-al igual que la tienda de Apple-cola es justo. La primera persona en línea al comienzo de la lista, el número 5 en este caso, él o ella se va a dejar en la primera tienda. Vamos a hacer eso. Supongamos que este es el estado de mi cola en este momento en el tiempo, y ahora la tienda de Apple se abre y la primera persona, número 5, es conducido a la tienda. ¿Cómo puedo cambiar la imagen ahora que he de-cola la primera persona en la parte delantera de la línea? ¿Qué es eso? >> [Estudiante] Cambie la cola. Cambie la cabeza, así que 5 desaparece. En realidad, es como si-la mejor manera de hacer esto? En realidad, es como si este hombre desaparece. ¿Cuál sería el número 7 en hacer una tienda real? Se daría un paso adelante muy importante. 

Pero ¿qué hemos llegado a apreciar lo que se refiere a las matrices y moviendo cosas de sitio? Eso es un poco de una pérdida de tiempo, ¿verdad? ¿Por qué tienes que ser tan anal como para tener la primera persona en el inicio de la línea en físicamente el inicio de la porción de la memoria? Eso es completamente innecesario. ¿Por qué? ¿Qué podría yo recuerde en su lugar? >> [Inaudible respuesta de los estudiantes] Exactamente, yo sólo podía recordar con esta cabeza de miembro de datos adicional que ahora la cabeza de la lista ya no es 0, lo que era hace un momento. Ahora en realidad es el número 1. De esta manera, consigo una optimización leve. El hecho de que he de-cola a alguien de línea al inicio de la línea en la tienda de Apple no significa que todo el mundo tiene que cambiar, lo que recuerdo es una operación lineal. Yo en cambio constante pueden pasar tiempo solo y lograr entonces una respuesta mucho más rápida. Pero el precio que estoy pagando es lo que ganar que el rendimiento adicional y no tener que cambiar todo el mundo? Si. >> [Inaudible respuesta de los estudiantes] Puede agregar más personas, bueno, ese problema es ortogonal al hecho de que no estamos cambiando la gente a su alrededor. Todavía es una matriz, por lo que si no cambiamos todos o no- Oh, ya veo lo que quieres decir, está bien. En realidad, estoy de acuerdo con lo que dices en que es casi como si estamos ahora nunca va a utilizar el inicio de esta serie ya porque si me quito 5, entonces me quito 7. Pero yo sólo poner a la gente a la derecha. 

Se siente como que estoy perdiendo el espacio, y con el tiempo mi cola se desintegra en la nada, por lo que sólo podría tener envolvente personas, y podríamos pensar en esta serie realmente como una especie de estructura circular, pero lo usamos operador en C para hacer ese tipo de envolvente? [Respuesta de los estudiantes inaudible] >> El operador de módulo. Sería un poco molesto para pensar en cómo se hace la envolvente, pero podríamos hacerlo, y podríamos empezar a poner a las personas en lo que fue el frente de la línea, pero sólo recuerda con esta variable cabeza que la cabeza real de la línea es en realidad. ¿Y si, por el contrario, nuestro objetivo en última instancia, sin embargo, fue a buscar números, como lo hicimos aquí en el escenario con Anita, pero realmente quieren lo mejor de todos estos mundos? Queremos más sofisticación que permite array porque queremos que la capacidad de crecer de forma dinámica la estructura de datos. Pero no quiero tener que recurrir a algo que hemos señalado en la primera conferencia no fue un algoritmo óptimo, que de búsqueda lineal. Resulta que se puede, de hecho, lograr o al menos cerca de la constante de tiempo, por lo que alguien como Anita, si se configura la estructura de datos para no ser una lista enlazada, de no ser una pila, para no ser una cola, podría, de hecho, llegar a una estructura de datos que le permite mirar las cosas, incluso palabras, no sólo números, en lo que llamaremos constante de tiempo. 

Y de hecho, mirando hacia adelante, uno de los conjuntos de procesadores de esta clase es casi siempre una implementación de un comprobador de ortografía, mediante el cual te damos otra vez algunas palabras inglesas 150.000 y el objetivo es cargar en la memoria de aquellos y rápidamente ser capaces de responder a las preguntas de la forma esta palabra se escribe correctamente? Y realmente sería un asco si tiene que recorrer los 150.000 palabras para contestar a eso. Pero, de hecho, veremos que podemos hacer en un tiempo muy, muy rápido. Y va a implicar algo aplicación llamada tabla hash, y aunque a primera vista esta cosa llamada tabla hash se va a vamos a alcanzar estos tiempos súper rápidos de respuesta, resulta que existe de hecho un problema. Cuando llega el momento de poner en práctica esta cosa llamada de nuevo, lo estoy haciendo de nuevo. Yo soy el único aquí. Cuando llega el momento de la aplicación de esta cosa llamada tabla hash, vamos a tener que tomar una decisión. ¿Qué tan grande debe ser esa cosa en realidad? Y cuando empezamos a insertar números en esta tabla hash, ¿cómo vamos a guardarlos de forma que podamos volver a salir tan rápido como nos las dieron en? Pero ya veremos dentro de poco, que esta cuestión de cuando es el cumpleaños de todos en la clase será muy afín. Resulta que en esta sala, tenemos unos pocos cientos de personas, así que las probabilidades de que dos de nosotros tenemos el mismo cumpleaños es probablemente bastante alto. ¿Qué pasa si sólo había 40 de nosotros en esta sala? ¿Cuáles son las probabilidades de que dos personas tengan el mismo cumpleaños? [Los estudiantes] Más del 50%. Si, más de 50%. De hecho, hasta me trajo una carta. Resulta que-y esto es realmente sólo un adelanto de vista previa si sólo hay 58 de nosotros en esta sala, la probabilidad de que 2 de nosotros tengan el mismo cumpleaños es enormemente alto, casi el 100%, y eso va a causar una gran cantidad de daño para nosotros el miércoles. 

Dicho esto, vamos a levantar la sesión aquí. Nos vemos el miércoles. [Aplauso] [CS50.TV]