[REPRODUCCIÓN DE MÚSICA] 

[REPRODUCCIÓN DE VÍDEO] 

-Él está mintiendo. 

-¿Acerca de? 

-No lo sé. 

-¿Entonces que sabemos? 

-Que A las 9:15, Ray Santoya estaba en el cajero automático. -Sí. Así que la pregunta es, ¿qué estaba haciendo a las 9:16? 

-Shooting Milímetro 9 en algo. Tal vez vio al francotirador. 

-O Fue trabajar con él. 

-Espera. Vuelve una. 

-¿Que ves? 

-Lleve Su rostro hasta pantalla completa. 

-Sus Gafas. 

-Hay Una reflexión. 

-Es El equipo de béisbol de Nuevitas. Esa es su logotipo. 

-Y Él está hablando con el que lleva la chaqueta. 

[FIN DE REPRODUCCIÓN] 

DAVID MALAN: De acuerdo. Esto es CS50 y esto es un poco más de [inaudible] con la que estás escarceos con el problema de establecer cuatro. Hoy empezamos a mirar un poco más profundamente en estas cosas llamadas punteros, que aunque es un tema bastante arcano, resulta que se va ser el medio por el cual nos puede empezar a construir y montaje programas mucho más sofisticados. Pero lo hicimos en el pasado miércoles por medio de algunos claymation primero. Así que esto, recordar, es Binky y nosotros lo utilizamos a echar un vistazo a un programa que realmente no hacer nada interesante, pero sí reveló algunos problemas. Así que para empezar hoy, ¿por qué no nos andamos rápidamente a través de algunos de estos pasos, tratar de destilar en términos de humanos exactamente lo que está pasando aquí y por qué esto es malo, y luego seguir adelante y realmente empezar a construir algo con esta técnica? Así que estos fueron los primeros dos líneas en este programa y en términos simples, lo que están haciendo estas dos líneas? Alguien que es razonablemente cómodo con lo que ha declarado en la pantalla? ¿Cuáles son estas dos líneas que hacen? No es todo lo que diferente de semana uno, pero que una novedad símbolo especial. ¿Sí? Volver allí. 

AUDIENCIA: Declarar punteros? DAVID MALAN: Diga otra vez? AUDIENCIA: Declarar punteros? DAVID MALAN: punteros declarar y vamos a refinar un poco más. AUDIENCIA: [inaudible] dirección x y y. DAVID MALAN: Y luego abordar. Así que específicamente lo que estamos haciendo Somos nosotros declaramos dos variables. Estas variables, sin embargo, van ser de tipo int estrella, que significa más específicamente van a almacenar la dirección de un int, respectivamente, x e y. Ahora hay ningún valor? ¿Hay direcciones reales en estos dos variables en este punto en el tiempo? No. Simplemente ha llamados valores de basura. Si en realidad no asigna un variables, lo que fuera en la memoria RAM previamente se va a llenar de ceros y los dos de esas variables. Pero aún no sabemos lo que son y eso es va a ser la clave de por qué Binky perdido la cabeza la semana pasada. 

Así que este era el claymation encarnación de esta por el que usted tiene sólo dos variables pequeñas piezas circulares de arcilla, que puede almacenar variables, pero como las flechas envueltas sugieren, no están realmente apuntando a cualquier lugar conocido per se. Así que tuvimos esta línea, y esto era nuevo la semana pasada, malloc para la memoria asignación, que es sólo una forma elegante de decirle al sistema operativo, Linux o Mac OS o Windows, oye, dame algo de memoria, y todo lo que tiene que contar el sistema operativo es lo que cuando se le pide que para la memoria. No va a cuidar lo que que vas a hacer con él, pero sí es necesario para contar la operación sistema de lo que a través de malloc. ¿Sí? 

AUDIENCIA: ¿Cuánto? DAVID MALAN: ¿Cuánto? ¿Cuánto en bytes, y así, esto, de nuevo, un ejemplo artificial, es sólo decir, dame el tamaño de un int. Ahora, el tamaño de un int es de cuatro bytes o 32 bits. Así que esto es sólo una forma de diciendo, hey, sistema operativo, dame cuatro bytes de memoria que puedo usar a mi disposición, y en concreto, lo que hace retorno malloc respecto a ese trozo de cuatro bytes? AUDIENCIA: Dirección? DAVID MALAN: la dirección. La dirección de ese trozo de cuatro bytes. Exactamente. Y eso es lo que está almacenado en última instancia, en x y por eso no lo hacemos realidad cuidar lo que el número de ese dirección es, si se trata de OX1 o ox2 o alguna dirección hexadecimal críptica. Nos preocupamos pictóricamente que esa variable x es ahora apuntando a que parte de la memoria. Así que la flecha representa un puntero o Más específicamente, una dirección de memoria. Pero, de nuevo, no nos preocupamos por lo general lo que esas direcciones son reales. Ahora, esta línea dice lo que en términos simples? Estrella x consigue 42 punto y coma. ¿Qué significa esto? ¿Quieres ir? No raye el cuello. 

AUDIENCIA: La dirección de x está en el 42. 

DAVID MALAN: La dirección de x es a los 42. No exactamente. Tan cerca, pero no del todo, porque hay la estrella que está anteponiendo esta x. Así que tenemos que ajustar un poco. ¿Sí? 

AUDIENCIA: El valor que el puntero x está apuntando es 42. DAVID MALAN: OK. El valor que el puntero x es apuntando a, digamos, serán 42, o dicho de otra manera, la estrella x dice, ir a cualquier dirección está en x, ya sea 1 Oxford Calle o 33 Oxford Street o OX1 o OX33, cualquiera que sea que dirección numérica es, estrella de x es el desreferencia de x. Así que ir a esa dirección y a continuación, poner el número 42 allí. Así que sería un manera equivalente a decir eso. Así que eso es todo fino y después queremos representar la imagen de la siguiente manera en la que hemos añadido la 42 a la parte de las cuatro bytes en el lado derecho, pero esta línea era donde las cosas salieron mal y la cabeza de Binky apareció en este punto, porque las cosas malas suceden cuando que eliminar la referencia de los valores de basura o eliminar la referencia no válido punteros, y me dicen que no válido porque en este punto en el historia, lo que está dentro de y? ¿Cuál es el valor de y en base en los últimos pasos? ¿Sí? ¿Que es eso? 

AUDIENCIA: Una dirección. DAVID MALAN: Una dirección. Debe ser una dirección pero he inicializado él? Así que no tengo. Entonces, ¿qué se sabe que es de allí? Es sólo un cierto valor de la basura. Podría ser cualquier dirección de cero a 2000000000 si tiene dos gigas de RAM, o cero a 4 millones de dólares si usted tiene tiene cuatro gigabytes de RAM. Es cierto valor de la basura, pero el problema es que el sistema operativo, si no se ha dado que parte de la memoria específica que usted está tratando de ir, es generalmente va a causar lo que hemos visto como un fallo de segmentación. Así que, de hecho, cualquiera de ustedes que tienen luchado en problemas en horario de oficina o en los problemas que más generalmente con tratando de averiguar un fallo de segmentación, eso significa generalmente estás tocando un segmento de la memoria que no debe ser. Estás tocando de memoria que el sistema operativo no tiene le ha permitido tocar, ya sea por ir demasiado lejos en la matriz o a partir de ahora, ya sea es porque usted está tocando memoria que simplemente es un valor de la basura. 

Así que hace la estrella x aquí se tipo de comportamiento indefinido. Usted nunca debe hacerlo porque las probabilidades son, el programa sólo va a chocar, porque usted está diciendo, ir a esta dirección y usted no tiene ninguna idea de dónde que la dirección es en realidad. Así que el sistema operativo es probable va a estrellar su programa como resultado y, de hecho, eso es lo que pasó allí para Binky. Así, en última instancia, Binky fijado este problema con esto. Así que el programa en sí era defectuoso. Pero si usted especie de seguir adelante y ejecutar esta línea en su lugar, y es igual a x sólo significa lo que sea dirección es una x, tambien ponerla en y. 

Y así pictóricamente, tenemos esta representado con dos flechas de x y de y apuntando al mismo lugar. Así semánticamente, x es igual a y porque ambos de aquellos se almacena el mismo dirección, ergo señalando a 42, y ahora, cuando dices estrellas y, vaya a la dirección en y, esto tiene un efecto secundario interesante. Así que la dirección en y es el lo mismo que la dirección de x. Así que si usted dice ir a la dirección en y y cambie el valor a 13, ¿quién más se ve afectado? X es, el punto D, por así decirlo, deberían verse afectados también. 

Y, en efecto, cómo Nick hizo este dibujo en claymation era exactamente eso. A pesar de que seguimos el puntero y, que terminó en el mismo lugar, y por lo que si tuviéramos que imprimir cabo xo pointee de y, entonces podríamos ver el valor de 13. Ahora, digo pointee sea coherente con el vídeo. Programadores, a mi conocimiento, en realidad nunca decir la palabra pointee, lo que es puntiaguda a, pero para la consistencia con el vídeo, se dan cuenta eso es todo lo que era significaba en esa situación. Así que cualquier pregunta sobre claymation o punteros o malloc todavía? ¿No? Correcto. 

Así que sin más preámbulos, vamos a echar un vistazo en donde esto tiene en realidad ha utilizado durante algún tiempo. Así que hemos tenido esta biblioteca CS50 eso tiene todas estas funciones. Hemos utilizado getInt mucho, GetString, Probablemente GetLongLong anterior en mi PSet uno o así, pero lo que ha estado pasando en realidad? Bueno, vamos a echar un vistazo rápido debajo de la campana en un programa que inspira opción te damos la CS50 biblioteca, y de hecho a partir de la semana pasada, empezamos a tomar las ruedas de entrenamiento fuera. Así que esto es ahora ordenadas de la autopsia de lo ha estado sucediendo dentro de la biblioteca CS50, a pesar de que ahora vamos a empezar a moverse lejos de él para la mayoría de los programas. 

Así que este es un programa llamado scanf 0. Es súper corto. Sólo tiene estas líneas, pero introduce una función llamada scanf que estamos en realidad va a ver en un momento dentro de la biblioteca CS50, aunque en una forma ligeramente diferente. Así que este programa en la línea 16 se declara una variable x. Así que me dan cuatro bytes para un int. Ha estado diciendo usuario, número favor y, a continuación, esta es una línea interesante que realidad corbatas juntos la semana pasada y este. Scanf, y luego notan que tarda un cadena de formato, al igual que printf, % i significa un int, y luego se necesita un segundo argumento que se ve un poco funky. Es signo x, y recordar, sólo vimos esto una vez pasada semana. ¿Qué signo x representa? ¿Qué hace el símbolo de unión en C? ¿Sí? 

AUDIENCIA: La dirección de. DAVID MALAN: La dirección de. Así que es todo lo contrario del operador de la estrella, mientras que el operador de la estrella dice, vaya a esta dirección, el operador de signo dice, averiguar el Dirección de esta variable, y por lo que esta es la clave, porque El propósito de scanf en la vida es escanear el usuario de entrada desde el teclado, dependiendo de lo que él o ella tipos y, a continuación, leer la entrada de ese usuario en una variable, pero vio en las últimas dos semanas que esa función de intercambio que intentado sin esfuerzo para poner en práctica se acaba de romper. Recordemos que con la función de intercambio, si nos declaramos A y B como enteros, tuvimos intercambiamos con éxito el dos variables dentro de canje al igual que con la leche y zumo de naranja, pero tan pronto como regresó de intercambio, cuál fue el resultado con respecto axey, los valores originales? Nada. Sí. Nada sucedió ese momento, porque swaps cambian sólo sus copias locales, que es decir, todo esta vez, cada vez que hemos estado pasando en los argumentos a las funciones, estamos de paso copias de esos argumentos. Usted puede hacer con eso lo que quieras con ellos, pero van a tener ninguna efecto sobre los valores originales. Así que esto es problemático si quiero tener una función como scanf en la vida, cuyo propósito es escanear la entrada del usuario desde el teclado y luego llenar los espacios en blanco, por lo que hablar, es decir, dar una variable como x un valor, porque si yo fuera que sólo tiene que pasar x para scanf, si se tiene en cuenta la lógica de la última semana, scanf puede hacer lo que quiera con una copia de x, pero no pudo cambiar permanentemente x menos que demos scanf un mapa del tesoro, por así decirlo, donde x marca el lugar, por lo que pasamos en la dirección de x de manera que scanf puede ir allí y en realidad el cambio el valor de x. Y así, de hecho, todo que este programa hace si hago scanf 0, en mi fuente Directorio de 5m, hacer scanf 0, punto slash scanf, número por favor 50, gracias por el 50. 

Así que no es tan interesante, pero lo que en verdad sucede es que tan pronto como me llamo scanf aquí, el valor de x se está cambiando de forma permanente. Ahora, esto parece agradable y bueno, y de hecho, parece que realmente no necesitamos la biblioteca CS50 en todos los más. Por ejemplo, vamos a correr esto una vez más aquí. Permítanme volver a abrirlo por un segundo. Vamos a tratar un número favor y en vez de decir 50 como antes, digamos que no. OK, eso es un poco raro. OK. Y sólo algunas tonterías aquí. Por lo tanto, no parece manejar situaciones erróneas. Así que tenemos que mínimamente inicio añadiendo un poco de comprobación de errores para asegurarse de que el usuario tiene escrito en un número real como 50, porque las palabras aparentemente mecanografía no se detecta como problemático, pero probablemente debería ser. 

Echemos un vistazo a esta versión ahora que es mi intento de volver a implementar GetString. Si scanf tiene todo esto funcionalidad incorporada, ¿por qué hemos estado coqueteando con ellos ruedas de entrenamiento como GetString? Bueno, aquí es tal vez mi propia versión simple de GetString por el que hace una semana, podría haber dicho: dame una cadena y lo llaman búfer. Hoy, voy a empezar justo diciendo estrellas char, que, recuerdo, es sólo sinónimo. Parece más miedo pero es exactamente lo mismo. Así que me dan un buffer variable llamada eso va a almacenar una cadena, decir la cadena de usuario por favor, y luego, al igual que antes, vamos a tratar de pedir prestado esta lección scanf % s esta vez y luego pasar en tampón. Ahora, una comprobación de validez rápido. Por qué no estoy diciendo ampersand amortiguar esta vez? Deducir del ejemplo anterior. AUDIENCIA: Char estrellas es un puntero. DAVID MALAN: Exactamente, porque esta vez, char estrellas ya es un puntero, una dirección, por definición de esa estrella estar allí. Y si scanf espera una dirección, basta sólo para pasar en tampón. No necesito decir búfer signo. Para los curiosos, podría hacer algo como esto. Habría significado diferente. Esto le daría un puntero a un puntero, que es en realidad una cosa válida en C, pero para ahora, vamos a mantenerlo simple y mantener la historia consistente. Yo sólo voy a pasar tampón y eso es correcto. El problema sin embargo es esto. Déjame ir adelante y ejecutar este programa después de la compilación. Hacer scanf 1. Maldita sea, mi compilador de la captura de mi error. Dame un segundo. Clang. Digamos scanf-1.c. OK. Allá vamos. Lo necesito. Identificación CS50 tiene varios ajustes de configuración que protegen contra ti mismo. Necesitaba desactivar las de corriendo clang manualmente este momento. Así cadena favor. Voy a seguir adelante y escribir en mi mundo hola favorito. OK, nulo. Eso no es lo que he escrito. Así que es indicativo de que algo anda mal. Déjame ir adelante y escribo en una cadena muy larga. Gracias por la nula y no sé si yo voy a ser capaz de estrellarlo. Vamos a intentar un poco de copia pegar y ver si esto ayuda. Sólo tienes que pegar un montón de esto. Es, definitivamente, una más grande cadena de lo habitual. Vamos a realmente escribirlo. No. Maldición. Comando no encontrado. Así que eso no relacionado. Eso es porque me pegué algunos personajes malos, pero esto resulta que no va a funcionar. 

Vamos a intentar una vez más, porque es más divertido si realmente estrellarlo. Vamos escriba esto y ahora, estoy va a copiar una cadena muy larga y ahora vamos a ver si nos puede chocar esta cosa. Note que omití espacios y nuevas líneas y puntos y comas y todos los personajes de funky. Intro. Y ahora la red sólo está siendo lenta. Sostuve la tecla Comando-V demasiado tiempo, con claridad. ¡Maldición! Comando no encontrado. 

OK. Bueno, el punto es no obstante, lo siguiente. Así que lo que realmente está pasando en la presente declaración de tampón estrellas Char en la línea 16? Así que ¿Qué consigo cuando me declaro un puntero? Todo lo que estoy haciendo es un valor de cuatro bytes llamada buffer, pero lo que hay dentro de ella ¿En el momento? Es sólo un cierto valor de la basura. Porque cada vez que declara una variable en C, es sólo un valor de basura, y estamos empezando a viaje por esta realidad. Ahora, cuando te digo scanf, ir a esta dirección y poner lo que el usuario escribe. Si el usuario escribe en hola mundo, bueno, ¿dónde lo pongo? Buffer es un valor de la basura. 

Así que eso es un poco como una flecha eso está señalando quién sabe dónde. A lo mejor es que apunta aquí en mi memoria. Y así, cuando el usuario tipos de hola mundo, el programa trata de poner el cadena hello world barra invertida 0 en esa parte de la memoria. Sin embargo, con alta probabilidad, pero claramente no 100% de probabilidad, el equipo se va a estrellar a continuación el programa porque no se trata la memoria se me permitiera tocar. Así que en resumen, este programa es viciado por exactamente eso. Yo fundamentalmente no estoy haciendo qué? ¿Qué pasos he omitido, al igual que omitimos con el primer ejemplo de Binky? ¿Sí? 

AUDIENCIA: asignación de memoria? 

DAVID MALAN: asignación de memoria. En realidad no he asignado cualquier memoria de esa cadena. Así que podemos arreglar esto en un par de maneras. Uno, podemos mantenerlo simple y de hecho, ahora estás va a comenzar a ver un desdibujamiento de las líneas entre lo una matriz es, lo que es una cadena, lo que es un estrellas char es, lo que es un conjunto de caracteres es. He aquí un segundo ejemplo involucrando cuerdas y notificación todo lo que he hecho en la línea 16 Es decir, en vez de decir ese búfer va a ser un char estrella, un puntero a una parte de la memoria, Voy a dar muy proactiva a mí mismo un tampón durante 16 caracteres, y de hecho, si usted está familiarizado con el término tampón, probablemente del mundo de los videos, donde un video es tampón, tampón, buffering. Bueno, ¿cuál es la conexión aquí? Bueno, Dentro de YouTube y en el interior de los reproductores de vídeo en general, es una matriz eso es más grande que 16. Puede ser que sea una matriz de tamaño de un megabyte, tal vez 10 megabytes, y dentro de esa matriz hace su navegador descargar un montón de bytes, un montón de megabytes de vídeo y el reproductor de vídeo, YouTube o quien es, comienza la lectura de los bytes a partir de ese array, y toda vez que vea la palabra tampón, tampón, eso significa que el jugador tiene llegado al final de esa matriz. La red es tan lento que no tiene rellenar la matriz con más bytes y por lo que está fuera de bits para mostrar al usuario. 

Así búfer es un término adecuado aquí en que es sólo una matriz, un trozo de la memoria. Y esto lo arreglará porque resulta que que se puede tratar como si arrays son direcciones, a pesar de tampón es sólo un símbolo, es un secuencia de caracteres, tampón, eso es útil para mí, el programador, usted puede pasar su nombre alrededor como si se tratara de una puntero, como si fueron la dirección de un trozo de la memoria de 16 caracteres. Así que eso es decir, puedo pasar el scanf exactamente esa palabra y por lo que ahora, si hago este programa, hacer scanf 2, punto slash scanf 2, y el tipo de hola mundo, Enter, que tiempo-- 

Hmm, ¿qué pasó? Cadena favor. ¿Qué hice mal? Hola mundo, tampón. Hola mundo. Ah, ya sé lo que está haciendo. OK. Así que ha leyendo hasta el primer espacio. Así que vamos a engañar por un momento y digo yo sólo quería escribir algo muy larga como esta es una frase larga ese es uno, dos, tres, cuatro, cinco, seis, siete, ocho, nueve, 10, 11, 12, 13, 14, 15, 16. OK. De hecho, es una larga condena. Así que esta frase es más de 16 caracteres y así cuando llegué a Enter, ¿Qué va a pasar? Bueno, en este caso de la búfer de historia, había declarado de ser en realidad un array con 16 caracteres listo para ir. Así que uno, dos, tres, cuatro, cinco, seis, siete, ocho, nueve, 10, 11, 12, 13, 14, 15, 16. Así que 16 caracteres, y ahora, cuando leído en algo como esto es un largo frase, lo que va a suceder es que voy a leer en este es mucho S-E-N-T-E-N-C-E, sentencia. 

Así que esto es deliberadamente una cosa mala que yo seguir escribiendo más allá de la límites de mi matriz, más allá de los límites de mi memoria intermedia. Yo podría tener suerte y el programa mantendrá en marcha y no les importa, pero en términos generales, esta será hecho estrellar mi programa, y es un error en mi codificar el momento me paso allá de los límites de esa matriz, porque yo no sé si es necesariamente va a estrellar o si sólo voy a tener suerte. Así que esto es problemático porque en este caso, no parece funcionar y vamos a tentar a la suerte aquí, a pesar de que el IDE parece tolerar un poco de-- 

Allá vamos. Finalmente. Así que yo soy el único que puede ver esto. Así que acabo de tener un montón de diversión a escribir una frase real muy largo que sin duda superó 16 bytes, porque yo escrito en este largo de varias líneas loco frase y, a continuación, darse cuenta de lo que pasó. El programa trató de imprimirlo y luego obtuvo un fallo de segmentación y fallos de segmentación es cuando sucede algo como esto y el sistema operativo dice no, no puede tocar esa memoria. Vamos a matar el programa completo. 

Así que esto parece problemático. He mejorado el programa mediante el cual por lo menos tener algo de memoria, pero esto parece confinar el GetString función para conseguir cuerdas de cierta extensión finita 16. Así que si quieres apoyar ya sentencias de 16 caracteres, ¿Qué haces? Bueno, se puede aumentar la tamaño de este buffer para 32 o eso parece clase de corto. ¿Por qué no simplemente hacer es 1000, pero hacer retroceder. ¿Cuál es la respuesta intuitiva de sólo evitar este problema haciendo mi búfer más grande, como 1.000 caracteres? Mediante la implementación de GetString de esta manera. Lo que es bueno o malo aquí? ¿Sí? AUDIENCIA: Si enlaza una gran cantidad del espacio y no lo utiliza, entonces no se puede reasignar ese espacio. DAVID MALAN: Por supuesto. Es un desperdicio medida en que si no lo hace realmente necesita 900 de esos bytes y sin embargo, usted está pidiendo 1.000 en total, de todos modos, usted está consumiendo más memoria el ordenador del usuario que usted necesita, y después de todo, algunos de ya has encontrado en la vida que cuando estás corriendo un montón de programas y están comiendo mucha memoria, en realidad esto puede afectar al rendimiento y la experiencia del usuario en la computadora. Así que eso es una especie de solución perezoso, a ciencia cierta, y por el contrario, que no sólo es un desperdicio, qué problema sigue siendo, incluso si hago mi búfer 1000? ¿Sí? 

AUDIENCIA: La cadena es la longitud de 1.001. DAVID MALAN: Exactamente. Si la cadena es la longitud de 1001, usted tiene el mismo problema, y con mi argumento, lo haría justo en ese momento que sea 2000, pero usted no sabe en avanzar en lo grande que debe ser, y, sin embargo, tengo que compilar mi programa antes de dejar que la gente usa y descarga ello. Así que este es exactamente el tipo de cosas que los intentos de la biblioteca CS50 para ayudarnos con y estaremos solamente vista En algunas de la implementación subyacente aquí, pero esto es CS50 dot C. Este es el archivo que ha estado en CS50 IDE todas estas semanas que ha estado usando. Es pre-compilado y que ha estado utilizando de forma automática por la naturaleza de tener el lanzarse L bandera CS50 con estrépito, pero si me desplazo hacia abajo a través de todos estas funciones, aquí está GetString, y sólo para darle un muestra de lo que está pasando, vamos a echar un vistazo rápido a la relativa complejidad. No es un super largo función, pero no lo hicimos hay que pensar seriamente en todo cómo hacer para conseguir cadenas. 

Así que aquí está mi memoria intermedia y yo aparentemente inicializarlo en null. Esto, por supuesto, es el lo mismo que la estrella char, pero decidí en la aplicación de la biblioteca CS50 que si vamos a ser completamente dinámico, No sé de antemano lo grande de una usuarios de cuerda van a querer conseguir. Así que voy a empezar con sólo una cadena vacía y yo voy a construir la mayor cantidad la memoria, ya que necesito para adaptarse a la cadena de usuario y si no tengo suficiente, voy a preguntar el sistema operativo para más memoria. Voy a mover su cadena en un pedazo más grande de la memoria y yo voy a soltar o liberar el insuficientemente gran parte de la memoria y sólo vamos para hacer esto de forma iterativa. 

Así que una rápida mirada, aquí es sólo una variable con la que me voy a llevar un registro de la capacidad de mi buffer. ¿Cuántos bytes puedo encajar? Aquí hay una variable n con que yo voy a seguir un registro de cuántos bytes son realmente en el tampón o que el usuario ha escrito. Si no has visto esto antes, puede especificar que una variable como un int no está firmado, que como su nombre indica, significa que es no negativo, y por qué lo haría Yo nunca quiero molestar especificando que un int no es sólo un int, pero es un int sin firmar? Es un int no negativo. ¿Qué hace el [inaudible] significa? 

AUDIENCIA: Se describe una cantidad de memoria que puede ser [inaudible]. 

DAVID MALAN: Sí. Así que si digo sin firmar, esto es en realidad dándole un bit de memoria adicional y parece un poco tonto, pero si tienen un bit de memoria adicional, que significa que tiene dos veces más valores que puede representar, porque puede ser un 0 o un 1. Así que por defecto, un int puede ser más o menos negativo de 2 mil millones hasta el final hasta positivo 2000000000. Esos son grandes rangos, pero es todavía tipo de desperdicio si sólo se preocupan por tamaños, que acaba de forma intuitiva debe ser no negativo o positivo o 0, pues bien, ¿por qué estás perdiendo 2000000000 posibles valores para los números negativos si nunca vas a usarlos? Así diciendo sin firmar, ahora mi int puede estar entre 0 y aproximadamente 4 mil millones. 

Así que aquí es simplemente un int C por razones no vamos a entrar en un momento como a eso que es un int en lugar de un char, pero aquí es la esencia de lo que está pasando en adelante, y algunos de ustedes podría estar usando, por ejemplo, el función fgetc incluso en PSet de cuatro oa partir de entonces, ya veremos que de nuevo en un problema conjunto de cinco, fgetc es agradable porque como su nombre clase de, clase de arcanamente sugiere, es una función que consigue un personaje y así, lo que es fundamentalmente diferente acerca de lo que estamos haciendo en GetString es que no estamos utilizando scanf de la misma manera. Sólo estamos arrastrándose a lo largo paso a paso más de lo que el usuario ha tecleado, porque siempre podemos asignar un solo char, por lo que siempre se puede de manera segura mirar uno carbón a la vez, y la magia comienza a suceder aquí. Voy a desplazarse hacia abajo para el medio de esta función sólo para presentar brevemente esta función. Al igual que hay un función malloc, hay una función realloc donde realloc le permite reasignar una parte de la memoria y hacerlo más grande o más pequeño. En tanto cuento y con una ola de mi mano para hoy, saber que lo GetString está haciendo es que es una especie del arte de magia de crecer o la reducción de la memoria intermedia como el usuario tipos en su cadena. 

Así que si el usuario escribe una cadena corta, este código sólo se asigna suficiente memoria para adaptarse a la cadena. Si el usuario mantiene la tipificación como lo hice una y otra vez y otra vez, bueno, si el búfer de un principio tan grande y el programa se da cuenta, a Espera un minuto, estoy fuera del espacio, que va a duplicar el tamaño del búfer y luego doblar el tamaño de la memoria intermedia y el código que hace la duplicación, si miramos desde aquí, es sólo por esta inteligente de una sola línea. Es posible que no haya visto esta sintaxis antes, pero si dices estrellas es igual, este es el mismo que diciendo tiempos capacidad 2. Por lo tanto, sólo sigue duplicando la capacidad de la memoria intermedia y luego contando realloc para dar sí que mucho más memoria. 

Ahora, como un aparte, hay son otras funciones en aquí que no vamos a mirar en detalle aparte de mostrar en getInt, usamos GetString en getInt. Comprobamos que no es null, que, recuerdo, es el valor especial que significa algo salió mal. Estamos fuera de la memoria. Mejor comprobar eso. Y volvemos un valor centinela. Pero te remito a los comentarios en cuanto a por qué y luego usamos ese primo de scanf llama sscanf y resulta que scanf sscanf, o cadena, le permite echar un vistazo a la línea que el usuario ha escrito y te deja analizarla esencial y lo que estoy haciendo aquí es que estoy diciendo sscanf, analizar lo que el usuario tiene escrito en y asegúrese de% i, no es un número entero en ella, y no lo haremos entrar en la actualidad exactamente por qué también hay un% c aquí, pero que en pocas palabras permite nos permite detectar si el usuario ha escrito en algo falso después del número. Así que la razón por la que getInt y GetString decirle a reintentar, reintentar, vuelva a intentarlo es porque de todos que el código que hemos escrito, Es una especie de mirar a la entrada del usuario en asegurarse de que es totalmente numérico o se trata de un flotante real valor de puntos o similar, dependiendo de qué valor función que está utilizando. 

¡Menos mal. OK. Eso fue un bocado pero el punto aquí es que la razón por la que tuvimos esas ruedas de capacitación sobre es porque en el nivel más bajo, hay tantas cosas que puede salir mal que queríamos para manejar de forma preventiva esas cosas ciertamente en el primeras semanas de la clase, pero ahora con PSet cuatro y cinco y PSet allá va a ver que es más hasta usted, pero también eres más capaz de resolver ese tipo de problemas tú mismo. ¿Tiene preguntas sobre GetString o getInt? ¿Sí? 

AUDIENCIA: ¿Por qué el doble la capacidad de la memoria intermedia en lugar de simplemente aumentar por la cantidad exacta? 

DAVID MALAN: Buena pregunta. ¿Por qué deberíamos duplicar la capacidad de la memoria intermedia en oposición sólo aumentarla por algún valor constante? Fue una decisión de diseño. Nos decidimos que ya que tiende a ser un poco caro en cuanto a tiempo de pedir el sistema operativo para la memoria, no lo hicimos quiere terminar metiendo una situación para las cadenas grandes que estábamos pidiendo el OS y otra vez y otra vez y otra vez en sucesión rápida para la memoria. Así que decidimos, algo arbitrariamente pero esperamos razonablemente, que, ya sabes qué, vamos a tratar de salir adelante de nosotros mismos y simplemente seguir doblando de manera que minimizamos la cantidad de veces tenemos que llamar a malloc o realloc, pero un fallo total de llamar a falta de saber lo que los usuarios podrían querer escribir. Ambas formas pueden ser discutibles. Podría decirse que buena. 

Así que vamos a echar un vistazo a un par de otros efectos secundarios de la memoria, cosas que pueden salir mal y herramientas que puede utilizar para capturar este tipo de errores. Resulta que todos ustedes, a pesar de que check50 no le ha dicho tanto, se han escrito con errores código desde la semana uno, incluso si todas las pruebas son check50 pasaba, e incluso si usted y su TF son super seguros de que el código funciona como está previsto. El código ha sido buggy o viciado en que todos ustedes, en el uso de la biblioteca CS50, han sido fugas de memoria. Usted ha estado pidiendo el sistema operativo para la memoria en la mayoría de los programas usted ha escrito, pero tienes En realidad nunca dada vuelta. Usted ha llamado GetString y getInt y GetFloat, pero con GetString, tienes Nunca llamada unGetString o Dar Posterior de la secuencia o similares, pero hemos visto GetString que hace asignar memoria por medio de malloc o este realloc función, que es sólo muy similar en espíritu, y, sin embargo, hemos sido preguntar al sistema operativo para la memoria y la memoria una y otra vez pero nunca darle la espalda. 

Ahora, como un aparte, resulta que cuando un programa se cierra, toda la memoria se libera automáticamente. Así que no ha sido un gran negocio. No va a romper el IDE o cosas más despacio, Pero cuando los programas hacen generalmente perder memoria y se están ejecutando durante mucho tiempo. Si alguna vez has visto la pequeña estúpida pelota de playa en Mac OS o el reloj de arena en Windows, donde es una especie de la ralentización o el pensamiento o el pensamiento o realmente comienza para frenar a un rastreo, muy posiblemente podría ser el resultado de una pérdida de memoria. Los programadores que escribieron el software que está utilizando pedir al sistema operativo para la memoria cada pocos minutos, cada hora. Pero si se está ejecutando la software, incluso si es minimizado en su ordenador por horas o días y días, se puede preguntar por más y más la memoria y la realidad nunca usarlo y por lo que su código podría ser, o programas podrían tener fugas de memoria, y si usted comienza a perder memoria, hay menos memoria para otros programas, y el efecto es frenar todo. 

Ahora, esto es, de lejos, uno de los programas más atroces usted tendrá la oportunidad para funcionar en la medida CS50 como su salida es aún más esotérico que sonido metálico de o hacer de o cualquiera de los comandos programas de línea nos hemos quedado antes, pero afortunadamente, incrustado en su salida es algunos consejos muy útiles que será útil tanto para PSet de cuatro o seguramente PConfigure cinco. Así valgrind es una herramienta que se puede utilizar para buscar que no haya fugas de memoria en su programa. Es relativamente fácil de ejecutar. Ejecuta valgrind y luego, incluso aunque es un poco prolijo, tablero comprobación de fugas tablero iguales por completo, y luego puntear tala y el nombre de su programa. Así valgrind entonces ejecutar el programa y al final de su programa corriendo antes de que cierra y le da otro aviso, que va a analizar su programa mientras se ha estado corriendo y dices que has de tener fugas cualquier memoria y mejor aún, tocaste memoria que no pertenecen a usted? No puede coger todo, pero es bastante bueno en la captura de la mayoría de las cosas. 

Así que aquí está un ejemplo de mi haber corrido este programa, que tiene plazo valgrind, en un programa llamado memoria, y me voy para resaltar las líneas que son en última instancia, de interés para nosotros. Así que incluso hay más distracciones que he eliminado de la diapositiva. Pero vamos a ver lo que este programa es capaz de decirnos. Es capaz de decirnos cosas como escritura no válida de tamaño 4. En otras palabras, si se toca la memoria, específicamente 4 bytes de memoria que usted no debe tener, valgrind le puede decir eso. Escritura no válida de tamaño 4. Tocaste cuatro bytes que no debería tener. ¿Dónde se hace eso? Esta es la belleza. La línea de puntos c Memoria 21 es donde se jodido y es por eso que es útil. Al igual que el BGF, puede ayudar señalarle en el error real. 

Ahora, éste es un poco más detallado, si no confuso. 40 Bytes 1 bloques son definitivamente perdido en el registro de la pérdida 1 de 1. ¿Que significa eso? Bueno, sólo significa que usted pidió 40 bytes y nunca se dio vuelta. Usted llamó malloc o llamó GetString y el sistema operativo que 40 bytes, pero nunca se dio liberado o liberada esa memoria, y para ser justos, nunca hemos mostramos cómo devuelves la memoria. Resulta que hay un súper función simple llamada gratuita. Toma un argumento, la cosa desea liberar o dar vuelta, pero 40 bytes, por lo visto, en este programa se han perdido en la línea 20 de la memoria dot c. 

Así que vamos a ver este programa. Es super inútil. Sólo demuestra este error en particular. Así que vamos a echar un vistazo. He aquí los principales y principales, aviso, llamadas una función llamada regresa f cuando. Así que no es tan interesante. ¿Qué hacer f? Note que no se molestó con un prototipo. Quería mantener el código el mínimo posible. Así que puse f anterior principal y eso está bien, sin duda, para programas cortos como este. Así que f no devuelve nada y hace No tome nada, pero que sí hace esto. Declara, al igual que en el ejemplo de Binky, un puntero llamado X que va para almacenar la dirección de un int. Así que ese es el lado izquierdo. En Inglés, ¿cuál es la lado derecho haciendo? Cualquier persona? ¿Qué es este haciendo por nosotros? ¿Sí? 

AUDIENCIA: [inaudible] veces el tamaño de un int que es 10 veces mayor que [inaudible] DAVID MALAN: Bien y permítanme resumir. Así asignar suficiente espacio para 10 enteros o 10, ¿cuál es el tamaño de un int, es cuatro bytes, por lo que 10 veces 4 es 40, por lo que a mano derecha que tengo resaltado es darme 40 bytes y almacenar la dirección del primer byte en x. Y ahora, por último, y aquí es donde este programa está libre de errores, lo que es mal con la línea 21 basa en que la lógica? ¿Qué hay de malo en la línea 21? ¿Sí? AUDIENCIA: Usted no puede índice en x [inaudible]. DAVID MALAN: Sí. Que no debería índice en x el estilo. Así sintácticamente, eso está bien. Lo bueno es, al igual que puede tratar el nombre de una matriz como si fuera un puntero, de manera similar puede tratar a un puntero como si fuera una matriz, y así puedo sintácticamente decir x soporte de algo, x soporte de i, pero el 10 es problemática. ¿Por qué? 

AUDIENCIA: Debido a que no hay dentro. 

DAVID MALAN: No es dentro de esa parte de la memoria. ¿Qué es el valor más grande que debe estar poniendo en esos corchetes? 9, del 0 al 9. Debido a cero de indexación. Así que de 0 a 9 estaría bien. Soporte de 10 no es bueno y pero, recordar, sin embargo, cada vez que Me parece que tratar de hacer CS50 IDE accidente escribiendo en valores falsos, no siempre coopera, y, de hecho, a menudo tener suerte sólo porque el sistema operativo no cuenta de que muy ligeramente pasar algún trozo de la memoria, porque usted se quedó dentro técnicamente su segmento, pero más sobre esto en una clase de sistemas operativos, y así algo como esto podría muy fácilmente pasar desapercibida. Su programa nunca va a estrellar consistentemente pero tal vez en un rato. 

Y así vamos a tratar valgrind en esto, y aquí está donde vamos a llegar abrumado por la salida momentáneamente. Así que la memoria de verificación de fugas valgrind es igual a la memoria barra de puntos completa. Y he aquí por qué te lo prometo esto podría abrumar. Esto es lo que valgrind, esto es lo un programador, algunos años- decidió que sería una buena idea para la salida a parecer. Así que vamos a hacer sentido de esto. Así que todo el camino a la izquierda lado por ninguna buena razón es el ID de proceso del programa acabamos de correr, el identificador único para el programa que acabamos de corrimos. Hemos suprimido que desde la diapositiva, pero hay hay alguna información útil aquí. 

Vamos a desplazarse hasta la parte superior. Aquí es donde empezamos. Así que no es todo lo que mucho de salida. Aquí hay que escribir inválida de tamaño 4 en la línea 21. Bueno, ¿cuál fue la línea 21? Línea 21 era exactamente esto y que tiene sentido que estoy en forma válida escribir 4 bytes porque soy tratando de poner este entero, que podría ser cualquier cosa, que sólo pasa a ser cero, pero estoy tratando de para ponerlo en un lugar que no pertenece a mí. Por otra parte, aquí abajo, 40 bytes en un bloques están definitivamente perdidos en el expediente 1. Eso es porque cuando llamo malloc aquí, yo en realidad nunca liberar la memoria. 

Entonces, ¿cómo podemos solucionar este problema? Déjame ir por delante y ser un poco más seguro y hacer 9 allí y me dejó aquí gratis x. Esta es la nueva función para hoy. Si ahora me vuelva a ejecutar hacer slash dot memoria, vamos a correr valgrind en él de nuevo, maximizar la ventana y pulse Enter. Ahora, es bueno. Entierran las buenas noticias en todo esto de salida. Todos los bloques de montón eran libres. Volveremos a lo que el montón es, pero no hay fugas son posibles. Así que esto es sólo otra herramienta para su caja de herramientas con el que se puede empezar a encuentra ahora los errores así. 

Pero vamos a ver qué más puede salir mal aquí. De transición Vamos ahora a en realidad la solución de un problema. Como acotación al margen, si esto va a aliviar un poco de confusión o de tensión, esto es ahora divertido. Sí. Eso es bastante bueno. Debido a que los punteros son direcciones y direcciones generalmente son por convención escrito con hexadecimal. Ja, ja, esto es gracioso ahora. De todos modos, así que vamos ahora realmente resolver un problema. Este ha sido estupendo, súper bajo nivel hasta el momento, y que en realidad podemos hacer útil cosas con estos detalles de bajo nivel. 

Así que hemos introducido unas semanas Hace la noción de una matriz. Un arsenal era agradable, porque es difícil de limpiar nuestro código porque si queríamos escribir una programa con múltiples estudiantes o múltiples nombres y casas y residencias y colegios y todo eso, podríamos almacenar todo más limpiamente dentro de una matriz. Pero proponer una desventaja de una matriz hasta el momento. Incluso si no has sufrido tú mismo en un programa, simplemente por instinto, lo que es una mala cosa sobre una matriz, tal vez? Oigo algunos murmullos. AUDIENCIA: Es difícil para cambiar el tamaño. DAVID MALAN: Es difícil para cambiar el tamaño. No se puede cambiar el tamaño de una matriz, de hecho, per se en C. Puede asignar otra matriz, mover todo, desde la anterior en el nuevo, y ahora tener algo más de espacio, pero no es como un lenguaje como Java o Python o cualquier número de otra lenguas con las que algunos de ustedes podría ser familiar donde puede simplemente seguir añadiendo cosas hasta la saciedad hasta el final de una matriz. Cuando usted tiene una serie de tamaño 6, que es su tamaño, y tan parecido a la idea anterior que tiene un buffer de un cierto tamaño, tienes que adivinar fuera de la puerta qué tamaño es lo que quieres que sea? Si adivina demasiado grande, estás perdiendo espacio. Si adivina demasiado pequeño, no puede almacenar datos que, por lo menos y sin mucho trabajo. 

Así que hoy, gracias a los punteros, podemos comenzar uniendo nuestra propia aduana estructuras de datos, y en De hecho, aquí es algo que se ve un poco más críptica a primera vista, pero esto es lo que llamaremos una ligado lista, y su nombre tipo de resume ello. Es una lista de números, o en este caso, una lista de números, pero podría ser una lista de cualquier cosa, pero está vinculado entre sí por medio de flechas, y acaba de tomar una conjetura con qué técnica vamos a ser capaces de para coser juntos, algo así como palomitas de maíz con un hilo, una vinculada listas rectángulos aquí? Sus números? ¿Cuál es la característica del lenguaje subyacente? 

AUDIENCIA: Un puntero. 

DAVID MALAN: Un puntero. Así que cada una de estas flechas representa aquí un puntero o simplemente una dirección. En otras palabras, si quiero para almacenar una lista de números, No puedo guardarlo si quiero la capacidad de crecer y encoger mi estructura de datos en una matriz. Así que tengo que tener un poco de más sofisticación, de notar que esta foto tipo de sugiere que si usted acaba de conseguir pequeños hilos conectar todo junto, probablemente no es tan difícil de hacer espacio entre dos de los rectángulos o dos de esos nodos, ya que vamos a empezar llamándolos, poner en un nuevo nodo, y luego con un poco de hilo nuevo, justo deshacerse de los tres nodos juntos, el primero, el último, y el que acaba de insertar en el medio. 

Y de hecho una lista enlazada, a diferencia de una matriz, es dinámico. Puede crecer y puede se encogen y no lo hace tiene que saber o cuidar de antemano cómo cantidad de datos que van a ser el almacenamiento, pero resulta que tenemos que ser un poco cuidado acerca de cómo implementar esto. Así que primero vamos a considerar cómo implementamos uno de estos pequeños rectángulos. Es fácil de implementar un int. Usted acaba de decir int n y después usted consigue 4 bytes para un int, pero ¿cómo puedo obtener un int, llamarlo n, y luego un puntero, vamos a llamarlo siguiente. Podríamos llamar a estos cosas lo que queramos pero necesito una estructura de datos personalizado. ¿Sí? 

AUDIENCIA: Ampersand [inaudible]. 

DAVID MALAN: Así signo que utilizaremos para obtener la dirección de un nodo potencialmente. Pero necesitamos otro función de C con el fin que me diera la posibilidad de crear este rectángulo costumbre, esta costumbre variable si se quiere, en la memoria. AUDIENCIA: Una estructura. DAVID MALAN: Una estructura. Recordemos que la semana pasada, introdujimos estructura, esta palabra clave relativamente simple que nos permite hacer cosas como esta. C no vino con un dato estructura llamada estudiantil. Viene con int y float y carbón y tales, pero no viene con los estudiantes, pero podemos crear un tipo de datos de los estudiantes, una estructura de estudiante, con esta sintaxis Aquí. Y verás esto una y otra vez. Así que no te preocupes por memorizando las palabras clave, pero la palabra clave que es importante es sólo el hecho de que hemos dicho struct y luego lo llamamos estudiante y en el interior del estudiante era un nombre y una casa o una residencia de estudiantes o similares. 

Y lo que ahora hoy, vamos a proponer esto. He añadido algunas palabras, pero si quiero para implementar este rectángulo que es tiene tanto un int y un puntero, sabes qué, yo soy va a declarar una estructura llamada nodo. Soy también, dentro de ella, va a decir que un nodo, este rectángulo, tiene un int y lo vamos a llamar ny tiene un siguiente puntero. Y esto es un poco prolijo, pero si se piensa en ello, las flechas que se encontraban en la imagen Hace un momento son de qué tipo de datos? Donde cada uno de esos flechas está apuntando a qué tipo de estructura de datos? No es simplemente apuntando a un int per se. Se apunta a la Lo rectangular entera y esa cosa rectangular, hemos dicho, se llama un nodo. Y así que tipo de tener que recursivamente definir esta tales que un nodo, diremos, contendrá un int llamada n y un puntero llamado siguiente y el tipo de estructura de datos a la cual que los puntos de puntero es aparentemente va a ser nodo de estructura. 

Así que esto es molesto detallado y acaba de ser pedante, la razón por la que no podemos solo decir esto, que francamente parece mucho más fácil de leer, se debe recordar que C leer cosas de arriba a abajo, de izquierda a derecha. No es hasta que tengamos el punto y coma que en realidad existe el nodo de palabras clave. Así que si queremos tener este tipo de referencia cíclica dentro de los datos estructura, tenemos que hacer esto, donde decimos nodo de estructura en la parte superior, lo que nos da una manera de describir esto ya cosa, entonces dentro decimos nodo de estructura, y luego en la última línea decimos, todo derecho, C, por cierto, simplemente llame a toda esta maldita cosa que un nodo y detener usando la palabra clave struct por completo. Así que esto es sólo una especie de una sintáctica truco que en última instancia nos permite crear algo que se ve exactamente como esta. 

Así que si suponemos ahora que podemos implementar esta cosa en C, cómo hacer que en realidad empezar a atravesar esto? Bueno, de hecho, todo lo que tenemos que hacer es repetir de izquierda a derecha y justo tipo de insertar nodos o eliminar nodos o buscar cosas donde queramos, pero para hacer esto, vamos a seguir adelante y hacer las cosas un poco más real porque este ha sido muy bajo nivel hasta el momento. ¿A alguien le gusta, literalmente, ser el primero? OK. Vamos arriba. ¿Cómo te llamas? 

DAVID: David. DAVID MALAN: David. Encantada de conocerte. Yo también. Correcto. Y necesitamos un número 9. No es tan buena como la primera, tal vez. OK, número 9. Un número 17, por favor. Permítanme volver un poco más lejos. Número 22, por favor, y ¿qué hay de más atrás si puedo ver ninguna mano con toda la luz o no. Alguien se ofreció allí mismo. ¿Quieres venir? Su antebrazo va por la fuerza hacia arriba. OK, 17. 22. 26 se viene abajo. ¿A alguien más que quiera forcefully-- Vamos para arriba. Un voluntario real. 

Así que muy rápidamente, si ustedes podrían arreglar Al igual que ustedes mismos los nodos en la pantalla. Gracias. Y podrás 26. Todas las presentaciones adecuadas y rápidas. Así que soy David y tú también? DAVID: David. DAVID MALAN: ¿Y usted es? JAKE: Jake. SUE: Sue. ALEX: Alex. RAPHAEL: Raphael. TAYLOR: Taylor. DAVID MALAN: Taylor. Excelente. Así que estos son nuestros voluntarios para hoy y seguir adelante y cambiar un poco de esa manera, y sólo seguir adelante y mantener la celebración de sus números como usted o su primer signo y el uso de la mano izquierda, seguir adelante y simplemente aplicar estas flechas, simplemente de modo que la mano izquierda es, literalmente, apuntando a lo que sea, tiene que introducir a, y darle un poco de espacio para que podemos ver visualmente los brazos realidad apuntando, y sólo puede apuntar tipo de en la planta está muy bien. 

Así que aquí tenemos una lista enlazada de uno, dos, tres, cuatro, cinco nodos inicialmente, y note que tenemos este especial puntero al principio quién es clave porque tenemos que seguir la pista de la lista de longitud entera de alguna manera. Estos chicos, a pesar de que uno se queda a derecha, espalda con espalda en la memoria, que en realidad puede estar en cualquier lugar en la memoria del ordenador. Así que estos chicos podrían ser de pie en cualquier lugar en el escenario y eso está bien, siempre y cuando estén realmente apuntando el uno al otro, pero para mantener las cosas limpio y sencillo, vamos a simplemente dibujarlas de izquierda a derecha como esto, pero podría haber brechas masivas entre esos nodos. 

Ahora, si quiero insertar en realidad algunos nuevo valor, vamos a seguir adelante y hacer esto. Tenemos una oportunidad ahora elegir otro nodo. Decir que vamos a empezar con mallocing 55. ¿Alguien importaría ser malloc? OK, vamos para arriba. ¿Cómo te llamas? ARCO IRIS: Arco iris. DAVID MALAN: Arco iris? Correcto. Rainbow Malloc. Vamos arriba. Así que ahora tenemos que preguntarnos a nosotros mismos algorítmicamente donde podemos poner 55. Así que todos sabemos, Obviamente, en la que, probablemente, pertenece, si estamos tratando para mantener este ordenadas y si ustedes podrían tomar uno un paso atrás para que no se caigan el escenario, que sería genial. Así que en realidad, arco iris, empezar de nuevo aquí conmigo, porque como el equipo ahora puede sólo ven una variable a la vez. Así que si este es el primer nodo. Observe que no es un nodo, él es sólo un indicador, y es por eso que ha dibujado para ser sólo el tamaño de un puntero, no uno de esos rectángulos completos. Así que vamos a comprobar en cada iteración es 55 menos de 9? No. Es 55 de menos de 17? No. Menos de 22? Menos de 26? Menos de 34? Y así es, obviamente, Rainbow pertenece al final. Así que para ser claros, y qué era su nombre, Taylor? 

TAYLOR: Taylor. DAVID MALAN: Así que entre Taylor mano izquierda y las manos del arco iris aquí, cuya mano debe apuntar a lo que en Para insertar 55 en esta lista? ¿Qué necesitamos hacer? ¿Sí? 

AUDIENCIA: la mano de Taylor hay que señalar izquierda. 

DAVID MALAN: Exactamente. Así la inserción de un nodo en el final de la lista es bastante simple porque Taylor acaba tiene que señalar, en lugar de en el suelo o lo llamaremos nulo, nula es una especie de ausencia de un puntero o una especial puntero cero, eres va a señalar con su izquierda la mano en el Rainbow y luego del arco iris, donde debe su izquierda Probablemente mano punto? Abajo. No es bueno si la mano es una especie de señalar fuera de aquí o de cualquier tipo en qué dirección. Eso sería considerado un valor de basura, pero si ella apunta a algún valor conocido, vamos a llamar cero o nula, eso está bien porque tenemos un término en este y sabemos que la lista ya está completo. 

Entonces, ¿qué otra caso relativamente simple? ¿Podríamos malloc 5? Vamos arriba. ¿Cómo te llamas? TIFFANY: Tiffany. DAVID MALAN: Lo siento? TIFFANY: Tiffany. DAVID MALAN: Tiffany. Correcto. Tiffany ha sido malloced con el valor 5. Vamos arriba. Éste es relativamente fácil también, pero vamos a considerar el orden de operaciones ahora. Era bastante fácil con Taylor en el extremo. Número 5 es, por supuesto, menos de 9, y por eso tenemos a David, tenemos Tiffany, y cuál era su nombre? 

JAKE: Jake. 

DAVID MALAN: Jake. Tiffany, Jake, y David. Cuya mano debe actualizarse primero? ¿Qué quieres hacer aquí? Hay posibles formas en que un par, pero también hay una o más formas equivocadas. 

AUDIENCIA: Comience con el extremo izquierdo. 

DAVID MALAN: Comience con el extremo izquierdo. ¿Quién es el más a la izquierda aquí, entonces? AUDIENCIA: Primero. 

DAVID MALAN: OK. Así que empieza con la primera y donde hacer desee actualizar las manos de David para ser? AUDIENCIA: Hacia el 5. DAVID MALAN: OK. Así que David, a las cinco en punto o Tiffany aquí y ahora? 

AUDIENCIA: Tiffany apunta al 9? DAVID MALAN: Perfecto, excepto Binky de cabeza sólo un poco se cayó, ¿verdad? Porque lo que tiene de malo esta imagen literalmente? AUDIENCIA: Nada está apuntando. DAVID MALAN: Nada es señalando a Jake ahora. Literalmente Hemos huérfanos 9 y 17, y hemos literalmente filtrado toda esta memoria, porque por actualización de la mano de David primero, eso es bien en la medida en que es correcta señalando en Tiffany ahora, pero si nadie tuvo la previsión para apuntar a Jake, entonces hemos perdido la totalidad de esa lista. Así que vamos a deshacer. Así que fue una buena cosa para tropezar pero vamos a corregir ahora. ¿Qué debemos hacer primero su lugar? ¿Sí? 

AUDIENCIA: Tiffany debe apuntar al 9? DAVID MALAN: No puedo conseguir que cerca de usted. ¿Quién debe apuntar al 9? 

AUDIENCIA: Tiffany. 

DAVID MALAN: De acuerdo. Así Tiffany deberían primer punto en el 9. Así Tiffany debe tomar en un valor idéntico a David, lo que parece redundante por un momento, pero eso está bien, porque ahora, segundo paso, podemos actualizar la mano de David señalar con diamantes, y luego, si nosotros, sólo un poco de limpiar las cosas como si esto es una especie de primaveral, ahora que es una inserción correcta. Así excelente. Así que ahora ya casi estamos allí. Vamos a insertar un último valor como el valor 20. Si pudiéramos malloc un voluntario final? Vamos arriba. Así que éste es un poco más complicado. Pero en realidad, el código somos escribir, aunque verbalmente, es como tener un montón si las condiciones de ahora, ¿verdad? Tuvimos una condición comprobar si pertenece al final, tal vez el principio. Necesitamos algún tipo de lazo para encontrar el punto en el centro. Así que vamos a hacer eso con lo que es su nombre? 

ERIC: Eric. 

DAVID MALAN: Eric? Eric. Encantada de conocerte. Así que tenemos 20. Menos de cinco? No. Menos de nueve? No. Menos de 17? No. OK. Él pertenece aquí y sus nombres son de nuevo? SUE: Sue. DAVID MALAN: Sue. ALEX: Alex. DAVID MALAN: Sue, Alex, y? ERIC: Eric. DAVID MALAN: Eric. Cuyas manos tienen que actualizarse primero? 

AUDIENCIA: Eric. OK. Así que Eric debería apuntar a dónde? A los 22 años. Bien. Y ahora ¿qué sigue? Sue entonces puede apuntar a Eric y ahora, si ustedes solo hacer un poco de espacio, lo cual está bien visualmente, ahora que hemos hecho de la inserción. Así que vamos a considerar ahora una pregunta, pero muchas gracias a nuestros voluntarios. Muy bien hecho. Usted puede mantener esos, si lo desea. Y tenemos un regalo de despedida encantador si que le gusta cada uno para tomar una pelota anti-estrés. Permítanme pasar esto. Entonces, ¿qué es la comida para llevar de todo esto? Esto parece ser increíble en la medida en que tenemos ahora introducido una alternativa a una matriz que no está tan limitado a una matriz de un cierto tamaño fijo. Pueden crecer dinámicamente. 

Pero al igual que hemos visto en semanas pasado, que nunca consiguió nada de forma gratuita, como seguramente hay un trade-off aquí. Así, con un alza de un ligado lista, es este dinamismo? Esta capacidad de crecer y, francamente, podríamos haber hecho de eliminación y podríamos reducir, según sea necesario. ¿Qué precio estamos pagando? El doble de espacio, en primer lugar. Si nos fijamos en la imagen, ya no estoy almacenando una lista de enteros. Estoy almacenar una lista de enteros más punteros. Así que estoy duplicando la cantidad de espacio. Ahora, tal vez eso no es tal una gran cosa 4 bytes, 8 bytes, pero sin duda podría añadir para grandes conjuntos de datos. ¿Cuál es otra desventaja? ¿Sí? 

AUDIENCIA: Tenemos que atravesar ellos uno por uno. DAVID MALAN: Sí. Tenemos que atravesar ellos uno por uno. ¿Sabes qué, nos dimos por vencidos esta super práctica función de corchetes notación, más propiamente conocida como acceso aleatorio, en el que sólo podemos saltar a un elemento individual pero ahora si todavía tenía mis voluntarios aquí, si quería encontrar la número 22, no puedo simplemente saltar al soporte de algo de algo. Tengo que mirar por encima de la lista, y mucho como nuestros ejemplos de búsqueda de forma lineal, para encontrar el número 22. Así que parece que hemos pagado un precio allí. Pero podemos, sin embargo, resolver otros problemas. 

De hecho, permítanme presentarles sólo un par de imágenes. Así que si usted ha sido hasta De Mather Dining Hall recientemente, usted recordará que su pilas de bandejas de este tipo, pedimos prestado estos de Annenberg antes de la clase. Así que esta pila de bandejas, sin embargo, es representativa realidad de una estructura de datos informática. Hay una estructura de datos en ciencias de la computación conocido como una pila que muy bien se presta a exactamente esto visual. Así que si cada una de estas bandejas no es una Bandeja pero al igual que un número y que quería para almacenar números, podría poner un hasta aquí, y pude poner otro aquí abajo, y continuar apilamiento números en la parte superior uno de otro, y lo que es potencialmente útil sobre este es que lo que es la implicación de esta estructura de datos? ¿Qué número puedo sacar primero más conveniente? El más reciente se metió allí. 

Así que esto es lo que llamaríamos en ciencias de la computación una estructura de datos LIFO. Último en entrar primero en salir. Y veremos en poco tiempo por qué que podría ser útil, pero por ahora, basta con considerar la propiedad. Y es un poco estúpido si usted piensa acerca de cómo el comedor hace. Cada vez que las bandejas limpias y poner los más frescos en la parte superior, usted podría tener una previamente limpia pero con el tiempo muy sucio y polvoriento la bandeja en la parte inferior si en realidad nunca llegar al fondo de esa pila, ya que acaba de seguir poniendo el nuevo y los limpios en la parte superior de la misma. Lo mismo podría suceder en un supermercado también. Si usted tiene una vitrina de leche y cada vez CVS o quien obtiene más leche, que acaba empuja las leches ya tiene a la espalda y poner los nuevos en la delantera, usted va a tener algunos bastante desagradable leche en el extremo de la estructura de datos, porque siempre en la parte inferior o equivalentemente siempre en la parte posterior. 

Pero hay otra manera de pensar alineando los datos y, por ejemplo, esta. Si eres una de esas personas que le gusta para alinear las afueras de las tiendas de Apple cuando llega un nuevo producto a cabo, es probable que no se utiliza un datos de la pila estructura porque alejaría a todos los demás que es haciendo cola para comprar un nuevo juguete. Más bien, es probable que estés usando qué tipo de estructura de datos o qué tipo de sistema ¿en el mundo real? Esperemos que sea una línea, o más adecuadamente o más británico-como, una cola. Y resulta que una cola es también un estructura de datos en ciencias de la computación, pero una cola tiene un muy distinta propiedad. No es LIFO. Último en entrar primero en salir. Dios no lo quiera. Es lugar FIFO. Primero en entrar primero en salir. Y eso es una buena cosa por causa de la justicia sin duda cuando se está alineando hasta muy temprano en la mañana. Si llegas primero, querer salir primero también. 

Y así, todos estos datos estructuras, colas y pilas y racimos de otros, resulta que puede pensar en esto como una matriz. Esta es una matriz, tal vez un tamaño fijo 4, pero sería ser algo bueno si pudiéramos acumular bandejas casi infinitamente alto si tener esa cantidad de bandejas o números. Así que tal vez queremos utilizar una lista enlazada aquí, pero la compensación va a ser potencialmente que necesitamos más memoria, toma un poco más de tiempo, pero nosotros no limitar la altura de la pila, mucho como vitrina de Mather podría limitar el tamaño de la pila, y así se trata de decisiones de diseño o opciones disponibles para nosotros en última instancia. Así, con estos datos estructuras, que han empezado ver nuevos límites superiores potencialmente en lo que antes era súper rápido y donde dejaremos de hoy y donde vamos Esperamos llegar es el miércoles, vamos a empezar a mirar un dato estructura que nos permite buscamos a través de los datos en tiempo final de registro de nuevo. Y vimos que, recordemos, en la semana cero y otro con búsqueda binaria o dividir y conquistar. Se va a volver y mejor aún, el santo grial para este miércoles será la de llegar a la estructura de datos que se ejecuta realmente o teóricamente en constante de tiempo, con lo cual no importa cuántos millones o miles de millones de cosas que tenemos en la estructura de datos, lo hará llevarnos constante de tiempo, tal vez un paso o dos pasos o 10 pasos, pero los números constantes de pasos para buscar a través de esa estructura de datos. Ese hecho será el santo grial pero más en que el miércoles. Nos vemos entonces. 

[REPRODUCCIÓN DE MÚSICA]