ALTAVOZ 1: Muy bien, así que esto es CS50 Este es el final de la quinta semana. Y recordar que la última vez que empezado a buscar en los datos más elegante estructuras que comenzaron a resolver problemas, que comenzaron a introducir nuevos problemas, pero la clave de este Era el tipo de roscado que empezado a hacer desde un nodo a otro. Así que este supuesto es una lista simplemente enlazada. Y por separado vinculados, Quiero decir que hay una sola hilo entre cada uno de esos nodos. Resulta que usted puede hacer más elegante cosas como listas doblemente enlazadas por el que usted tiene una flecha va en ambas direcciones, lo cual puede ayudar con ciertas eficiencias. Pero esto soluciona el problema? ¿Qué problema se resuelve esto? ¿Por qué nos importa el lunes? ¿Por qué, en teoría, nos cuidamos el lunes? ¿Qué hace? 

AUDIENCIA: dinámicamente Podemos cambiar su tamaño. 

ALTAVOZ 1: OK, por lo que podemos dinámicamente cambiar su tamaño. Bien hecho ambos. Así que usted puede cambiar el tamaño de forma dinámica este estructura de datos, mientras que una matriz, recuerdo, usted tiene que saber un priori la cantidad de espacio que desea y si usted necesita un poco más espacio, eres la clase de suerte. Tienes que crear una nueva matriz entera. Tienes que mover todo su datos de uno a otro, finalmente liberar la matriz de edad si se puede, y luego proceder. Lo cual se siente muy costoso y muy ineficientes, y de hecho puede ser. Pero esto no es todo lo bueno. Nosotros pagamos un precio, lo que fue uno de los precios más obvias pagar mediante el uso de una lista enlazada? 

AUDIENCIA: Tenemos que usar doble espacio para cada uno. ALTAVOZ 1: Sí, por lo que necesitamos al menos el doble de espacio. De hecho, me di cuenta de esta imagen incluso un poco engañoso, porque el IDE CS50 en muchos moderna computadoras, un puntero o una dirección no es, de hecho, cuatro bytes. Es muy a menudo éstos días ocho bytes, que significa la parte inferior más rectángulos hay en la realidad son una especie de doble de grande como lo que he dibujado, lo que significa que está utilizando tres veces más espacio que podríamos tener de otra manera. Ahora, al mismo tiempo, estamos sin dejar de hablar bytes, ¿verdad? No estamos hablando necesariamente megabytes o gigabytes, a menos que estas estructuras de datos se hacen grandes. 

Y por eso hoy empezamos a considerar cómo podríamos explorar los datos más eficientemente si en hecho de que los datos se hace más grande. Pero vamos a tratar de canonicalize las operaciones de la primera que se puede hacer en estos tipos de estructuras de datos. Así que algo como un ligada lista general apoya operaciones como borrar, insertar y buscar. Y lo que quiero decir con eso? Eso sólo significa que por lo general, si la gente está utilizando lista enlazada, ellos o alguien más ha implementado funciones como borrar, insertar, y la búsqueda, por lo que puede realmente hacer algo útil con la estructura de datos. Así que vamos a echar un vistazo rápido en cómo podríamos aplicar algo de código para una lista enlazada de la siguiente manera. 

Así que esto es sólo algo de código C, ni siquiera un programa completo que realmente me azotaron rápidamente. No es en línea en la distribución código, porque no va a funcionar realmente. Pero noto que tengo justo con un comentario dijo, punto punto punto, hay algo allí, dot dot dot, algo allí. Y vamos a mirar ¿cuáles son las partes jugosas. Así que en la línea tres, recordemos que esto es ahora nos propusimos declarar un nodo última tiempo, uno de esos objetos rectangulares. Tiene un int que llamaremos N, pero podríamos llamarlo nada, y luego una estrella struct nodo llamado siguiente. Y sólo para que quede claro, que segundos línea, en la línea seis, ¿qué es eso? ¿Qué está haciendo para nosotros? Porque sin duda se ve más críptica que nuestras variables habituales. 

AUDIENCIA: Se hace que se mueva más de una. 

ALTAVOZ 1: Se hace que se mueva más de una. Y para ser más precisos, almacenará la dirección del nodo que está destinado a ser semánticamente al lado de él, ¿verdad? Por lo tanto, no va a mover necesariamente nada. Es sólo va a almacenar un valor, que es va a ser la dirección de algún otro nodo, y es por eso que hemos dicho struct estrella de nodo, que denota la estrella un puntero o una dirección. OK, así que ahora si asumir que tenemos esta N disponible para nosotros, y vamos a asumir que alguien más tiene insertado un montón de números enteros en una lista enlazada. Y esa lista enlazada es apuntada por algún momento una llamada lista de variables que es aprobada en aquí como un parámetro, cómo hago para línea 14 implementación de búsqueda? En otras palabras, si me estoy poniendo en práctica función cuyo propósito en la vida es tomar un int y luego el a partir de una lista enlazada, que es un puntero a la lista enlazada. Como primera, que creo que David era nuestra voluntaria el lunes él estaba señalando todo vinculado la lista, es como si estamos pasando David como nuestra discusión aquí. ¿Cómo hacemos para atravesar esta lista? Bueno, resulta que a pesar de que punteros son relativamente nuevo ahora a nosotros, podemos hacer esto relativamente sin rodeos. 

Voy a seguir adelante y declarar una variable temporal que por convención es sólo ir para ser llamado puntero o PTR, pero se le puede llamar lo que quieras. Y yo voy a inicializar al comienzo de la lista. Así que usted puede clase de pensar en esto como yo la maestra, el otro día, tipo de apuntando a alguien entre nuestros seres humanos como voluntarios. Así que soy una variable temporal que es simplemente apuntando a lo mismo que nuestro coincidentemente nombrado voluntario David también estaba señalando. Ahora bien, aunque es puntero no es nulo, porque recuerdo que nulo es un valor especial centinela la demarca el final de la lista, así que mientras yo no estoy apuntando a la suelo como nuestra última voluntario fue, vamos a seguir adelante y haga lo siguiente. Si pointer-- y ahora que tipo de deseo a hacer lo que hicimos con el estudiante structure-- si dot puntero próximo equals-- más bien, si dot puntero N es igual es igual a la variable N, la argumento que ha sido aprobada en, entonces quiero seguir adelante y decir volver realidad. He encontrado el número N interior uno de los nodos de mi lista enlazada. Pero el punto ya no funciona en este contexto, porque puntero, PTR, es de hecho un puntero, una dirección, que en realidad puede maravillosamente utilizar finalmente una pieza de sintaxis ese tipo de marcas sentido intuitivo y realidad utilizar una flecha aquí, lo que significa pasar de esa dirección al entero más allá en. Así que es muy similar en espíritu para el operador punto, sino porque puntero no es un puntero y no una propia estructura real, sólo tiene que utilizar la flecha. 

Así que si el nodo actual que yo, el variable temporal, estoy apuntando a ¿no es N, ¿qué es lo que quiero hacer? Pues bien, con mis voluntarios humanos que tuvimos aquí el otro día, si mi primer ser humano no es el que yo quiere, y tal vez el segundo humano no es el que yo quiero, y el tercero, que que mantener físicamente en movimiento. Al igual que ¿cómo me paso a través de una lista? Cuando tuvimos una matriz, acaba de hacer como si plus plus. Pero en este caso, basta con hacer puntero, consigue, puntero, al lado. En otras palabras, el campo siguiente es como todas las manos izquierdas que nuestros voluntarios humanos el lunes estaban usando para señalar en algún otro nodo. Esas fueron sus siguientes vecinos. 

Así que si quiero dar un paso a través de esta lista, No puedo hacer yo plus plus más, Yo en cambio tengo que decir Yo, puntero, va para igualar cualquiera que sea el siguiente campo es, el siguiente campo es, el siguiente campo es, tras todas esas manos izquierdas que teníamos en el escenario que señala para algunos valores posteriores. Y si me pongo a través toda esa iteración, y, finalmente, me golpeó nula no tener Encontré N sin embargo, acabo de regresar falsa. Así que de nuevo, todo lo que estamos haciendo aquí, según la imagen hace un momento, está empezando señalando en el a partir de la lista de suponer. Y entonces puedo comprobar, es el valor Busco igual a nueve? Si es así, vuelvo verdadera y he terminado. Si no, puedo actualizar mi mano, También conocido como puntero, al punto en el lugar de la próxima flecha y a continuación, la ubicación de la próxima flecha, y el siguiente. Simplemente estoy caminando a través de esta matriz. 

Así que de nuevo, a quién le importa? Al igual que lo es este ingrediente para? Bueno, recordemos que introdujimos la noción de una pila, que es un tipo abstracto de datos en la medida en que es no es una cosa C, no es una cosa CS50, es una idea abstracta, esta idea de apilar cosas en la parte superior de unos a otros que se pueden implementar en racimos de diferentes maneras. Y una manera que propusimos fue con una matriz o con una lista enlazada. Y resulta que canónicamente, un pila compatible con al menos dos operaciones. Y las palabras de moda son de empuje, a empujar algo en la pila, como una nueva bandeja en el comedor, o el pop, lo que significa para eliminar el más elevado bandeja de la pila en el comedor pasillo, y luego tal vez algunos otras operaciones también. Entonces, ¿cómo podríamos definir la estructura que ahora estamos llamando a una pila? 

Bueno, tenemos todo lo necesario sintaxis a nuestra disposición en C. digo, darme una definición de tipo de una estructura interior de una pila, Yo voy a decir es una matriz, de un toda montón de números y luego el tamaño. En otras palabras, si quiero para implementar esta en el código, déjame ir y sólo un poco dibujar lo que esto está diciendo. Así que esto está diciendo, dame un estructura que tiene una matriz, y yo no sé lo que es la capacidad, al parecer es una constante que tengo definidos en otro lugar, y eso está bien. Pero supongo que es sólo uno, dos, tres, cuatro, cinco. Así capacidad es de 5. Este elemento interior de mi estructura se llamará números. Y entonces yo necesito uno otra variable aparentemente llamada tamaño que en un principio me voy estipular se inicializa a cero. Si no hay nada en la pila, el tamaño es cero, y es los valores de basura en números. No tengo idea de lo que hay allí por el momento. 

Así que si quiero empujar algo en la pila, Supongo que yo llamo la función de empuje, y Digo empujar 50, como el número 50, donde propondría Señalo que en esta serie? Hay cinco posibles respuestas diferentes. ¿Dónde quiere empujar el número 50? Si el objetivo aquí, de nuevo, llamar al la función de empuje, pasar en una discusión de 50, ¿dónde lo pongo? Cinco posible-- 20% de probabilidad de adivinar correctamente. ¿Sí? 

AUDIENCIA: Extremo derecho. 

ALTAVOZ 1: Extremo derecho. En la actualidad existe una probabilidad del 25% de adivinar correctamente. Así que eso sería realmente bien. Por convención, lo diré con una matriz, estaríamos en general comenzará a la izquierda, Pero podríamos sin duda comenzará a las de la derecha. Así que el alerón aquí sería que soy probablemente va a sacar, a la izquierda, al igual que en una matriz normal donde Empiezo a ir a la izquierda a la derecha. Pero si se puede dar la vuelta la aritmética, bien. Es que no es convencional. OK, tengo que hacer una más cambio embargo. Ahora que lo he empujado algo en la pila, ¿qué sigue? 

Muy bien, tengo que incrementar el tamaño. Así que déjame ir por delante y justo actualizar esta, que era cero. Y en lugar ahora, me voy poner en valor uno. Y ahora supongo empujo otra número en la pila, al igual que 51. Bueno, tengo que hacer una más el cambio, que es hasta el tamaño dos. Y luego supongo empujo una más número en la pila como 61, ahora tengo que actualizar el tamaño de una más tiempo, y obtener el valor 3 como el tamaño. Y ahora supongo que yo llamo pop. Ahora pop, por convención, no tiene un argumento. Con una pila, la totalidad punto de la metáfora de la bandeja es que usted no tiene la discreción para ir a buscar esa bandeja, todo lo que puede hacer se abrirá el de más arriba de la pila, porque sí. Eso es lo que hace esta estructura de datos. 

Así que por esa lógica si dicen pop, lo que sale? Así que 61. Así que lo que realmente es el ordenador va a hacer en la memoria? ¿Qué hace mi código tiene que hacer? ¿Qué propondría usted cambiamos en la pantalla? ¿Qué debe cambiar? ¿Apenado? Así que nos deshacemos de 61. Así que definitivamente puedo hacer eso. Y puedo deshacerme de 61. Y entonces, ¿qué otra el cambio tiene que suceder? Tamaño probablemente tiene que volver a dos. Y así está bien. Pero espere un minuto, tamaño Hace un momento tenía tres años. Vamos a hacer una comprobación de validez rápido. ¿Cómo sabemos que estamos quería deshacerse del 61? Debido a que estamos haciendo estallar. Y así tengo este segundo tamaño de la propiedad. 

Espera un minuto, estoy pensando en volver a la segunda semana cuando empezamos a hablar de arrays, donde esto era lugar de cero, esta era la ubicación uno, esta era la ubicación dos, esto es la ubicación tres, cuatro, parece que el relación entre el tamaño y el elemento que quiero quitar de la matriz parece ser lo que? Tamaño menos uno. Y así es como los humanos sabemos 61 que ocurra primero. ¿Cómo está el equipo va a saber? Cuando su código, en el que, probablemente, quiere hacer tamaño de menos uno, por lo menos uno de tres es de dos, y que significa que queremos deshacernos de 61. Y entonces podemos efectivamente actualizar el tamaño de modo que el tamaño ahora va de tres a dos. Y sólo para ser pedante, voy proponer que he terminado, ¿no? Usted propuso intuitivamente correctamente Debo deshacerme de 61. Pero no tienen que tipo de tipo de deshecho de 61? Me he olvidado de manera efectiva que en realidad existe. Y pensar en volver a PSET4, si has leído el artículo sobre medicina forense, el PDF que teníamos que ustedes leer, o leerá esta semana para PSET4. Recordemos que esto es en realidad afín a toda la idea de la informática forense. Lo que un equipo generalmente hace es simplemente se olvida dónde está algo, pero no entra y al igual que tratar de arañar hacia fuera o anulación esos bits con ceros y unos o algún otro patrón aleatorio a menos que usted mismo lo hacen deliberadamente. Por lo que su intuición era Muy bien, vamos a deshacernos de 61. Pero en realidad, no tenemos que preocuparse. Sólo tenemos que olvidar que que está ahí cambiando nuestro tamaño. 

Ahora hay un problema con esta pila. Si sigo empujando cosas en la pila, lo que es Obviamente va a pasar en tan sólo unos pocos momentos de tiempo? Vamos a quedarse sin espacio. ¿Y qué hacemos? Estamos tipo de jodidos. Esta aplicación no permite nos redimensionar la matriz, porque el uso de esta sintaxis, si pensar de nuevo a la segunda semana, una vez que se ha declarado el tamaño de un array, no hemos visto un mecanismo aún cuando usted puede cambiar el tamaño de la matriz. Y de hecho C no tiene esa característica. Si dices dame cinco NTHS, los llaman números, eso es todo lo que vas a conseguirlo. Así que vamos a hacer ahora a partir del lunes, tenemos la capacidad de expresar una solución sin embargo, sólo tenemos que ajustar la definición de nuestra pila de no haber algún conjunto modificable, pero sólo para almacenar una dirección. 

Ahora ¿por qué es esto? Ahora sólo tenemos que estar cómodo con el hecho de que cuando mi programa se ejecuta, Estoy presumiblemente va a tiene que pedir a la humana, la cantidad de números es lo que quieres para almacenar? Así que la entrada tiene que venir de alguna parte. Pero una vez que sé que número, entonces yo puedo solo utilizar lo que funciona para dar mí una parte de la memoria? Puedo usar malloc. Y puedo decir cualquier número de bytes quiero volver por estos NTHS. Y todo lo que tengo para almacenar en los números variable de aquí dentro de esta estructura debería ser qué? Lo que en realidad sucede en el números en este escenario? Sí, un puntero a la primera byte de ese trozo de memoria, o más específicamente, la dirección de del primero de esos bytes. No importa si es uno byte o mil millones de bytes, Sólo tengo que preocuparse por el primero. Porque ¿qué garantías malloc y mis garantías del sistema operativo, es que la parte de la memoria de E conseguir, que va a ser contiguos. No va a haber lagunas. Así que si yo he pedido 50 bytes o 1.000 bytes, están todos van a ser espalda con espalda con espalda. Y siempre que me acuerdo de qué tan grande, ¿cómo tanto que pedí, todo lo que necesito saber es la primera dirección. 

Así que ahora tenemos la capacidad de código. Aunque, va a llevarnos más tiempo para escribir esto, podríamos ahora reasignar ese recuerdo por simplemente almacenar una dirección diferente allí si queremos una más grande o incluso un trozo más pequeño de la memoria. Así que aquí a un fuera de comercio. Ahora llegamos dinamismo. Todavía tenemos contigüidad que estoy afirmando. Debido a malloc nos dará una parte contigua de la memoria. Pero esto va a ser un dolor en el cuello para nosotros, el programador, codificar realmente para arriba. Es sólo más trabajo. Necesitamos código similar a lo que era golpeando a cabo hace un momento. Muy factible, pero añade complejidad. Y así que el tiempo desarrollador, programador el tiempo es otro recurso que podamos necesitar para pasar un poco de tiempo para conseguir nuevas características. Y luego, por supuesto, hay una cola. No vamos a entrar en esto una en mucho detalle. Pero es muy similar en espíritu. Yo podría implementar una cola, y sus operaciones correspondientes, enqueue o quitar de la cola, como agregar o quitar, es sólo una forma más elegante de decirlo, enqueue o quitar de la cola, como sigue. Sólo me puedo dar una estructura que de nuevo tiene matriz de un número, que de nuevo tiene un tamaño, pero ¿por qué hago Ahora necesito hacer un seguimiento de la parte delantera de la cola? Yo no necesito saber el frente de mi pila. Bueno, si yo de nuevo por un queue-- vamos sólo difícil codificar como teniendo como de cinco enteros en aquí potencialmente. Así que este es cero, uno, dos, tres, cuatro. Esto va a ser números llamados de nuevo. Y esto se llamará tamaño. 

¿Por qué es no suficiente tener el tamaño justo? Bueno, vamos a empujar esos mismos números en. Así que pushed-- I en cola, o empujado. Ahora voy a poner en cola 50, y luego 51, y después de 61 años, y dot dot dot. Así que eso es enqueue. Yo en cola 50, luego 51, luego 61. Y eso se ve idéntica a una pila hasta el momento, sin que yo lo necesito para hacer un cambio. Necesito actualizar este tamaño, así que voy de cero a uno a dos y cincuenta y ocho ahora. ¿Cómo puedo quitar de la cola? ¿Qué sucede con dequeue? ¿Quién debe salir esta lista primero si se trata de la línea en la tienda de Apple? Así que 50. Así que es un poco más difícil esta vez. Mientras que la última vez fue super simplemente fácil de hacer tamaño de menos uno, Llego al final de mi serie efectiva donde los números son, elimina 61. Pero yo no quiero quitar 61. Quiero aprovechar 50 años, que estaba allí en 5:00 a la línea para el nuevo iPhone o lo que sea. Y así, para deshacerme de 50, me no sólo puede hacer esto, ¿verdad? Puedo tachar 50. Pero acabamos de decir nos no tienen que ser tan anal para ganarse u ocultar los datos. Sólo podemos olvidar dónde está. 

Pero si cambio de tamaño ahora dos, es esta información suficiente saber lo que está pasando en mi cola? En realidad no. Al igual que mi tamaño es dos, pero ¿Dónde comienza la cola, especialmente si todavía tengo esos mismos números en la memoria. 50, 51, 61. Así que tengo que recordar ahora en la parte delantera es. Y así como me propuse arriba allí, vamos Acabamos de llamada Frente enésimo, cuya inicial valor debe haber sido lo que? Cero, sólo el comienzo de la lista. Pero ahora, además de decremento el tamaño, sólo incrementa el frente. Ahora aquí hay otro problema. Así que una vez que sigo yendo. Supongamos que este es el número de como 121, 124, y luego, maldita sea, Estoy fuera de espacio. Pero espere un minuto, yo no lo soy. Así que en este punto de la historia, supongamos que el tamaño es uno, dos, tres, cuatro, así que supongo que la tamaño es cuatro, el frente es uno, por lo que es 51 en la parte delantera. Quiero poner otro número aquí, pero, maldita sea, me he quedado sin espacio. Pero yo no soy realmente, ¿verdad? ¿Dónde podría poner un poco valor adicional, al igual que 171? Sólo Sí, pude tipo de volver por allí, ¿verdad? Y luego cruzar la 50, o simplemente sobrescribir con 171. Y si usted se está preguntando por qué nuestros números llegaron tan al azar, éstos son comúnmente tomadas equipo cursos de ciencias en Harvard después CS50. Pero eso era una buena optimización, porque ahora no estoy perdiendo espacio. Todavía tengo que recordar lo grande que es total. Es cinco en total. Porque no quiero empezar a sobrescribir 51. Así que ahora estoy todavía sin espacio, por lo que el mismo problema que antes. Pero se puede ver cómo ahora en el código, es probable que que escribir un poco más complejidad para hacer que eso suceda. Y de hecho, lo que el operador en C, probablemente vamos a que mágicamente hace esto la circularidad? Sí, el operador de módulo, el signo de porcentaje. Entonces, ¿qué es una especie de fresco sobre una cola, a pesar de que seguimos matrices de dibujo ya que estas líneas rectas como, si usted tipo de pensar en esto como curva alrededor como un círculo, entonces sólo intuitivamente que tipo de trabajos mentales Creo que un poco más limpia. Usted todavía tiene que poner en práctica ese modelo mental en código. Así que no es tan difícil, en última instancia, para poner en práctica, pero todavía perdemos la size-- más bien, la capacidad de cambiar el tamaño, a menos que hagamos esto. 

Tenemos que deshacernos de la matriz, se reemplazarlo con un único puntero, y luego en algún lugar de mi código tengo Una llamada lo que funciona para crear realidad la matriz de números llamados? Malloc, o algunos similares función, exactamente. ¿Tiene preguntas sobre pilas o colas. ¿Sí? Buena pregunta. Lo módulo usarías aquí. Así que en general, cuando se utiliza mod, que lo haría con el tamaño de la estructura de datos entera. Así que algo así como cinco o capacidad, si es constante, es probablemente involucrados. Pero sólo haciendo módulo de cinco probablemente no es suficiente, porque necesitamos saber qué tenemos envolver alrededor de aquí o aquí o aquí. Así que usted es probablemente también va a querer involucrar el tamaño de la cosa, o la variable frente también. Así que es sólo por esta relativamente expresión aritmética simple, pero módulo sería el ingrediente clave. 

Así cortometraje si se quiere. Una animación que algunos gente de otra universidad armamos que hemos adaptada para esta discusión. Se trata de Jack el aprendizaje de la hechos acerca de las colas y estadísticas. 

PELÍCULA: Érase una vez, había un tipo llamado Jack. Cuando se trataba de hacer amigos, Jack no tiene una habilidad especial. Así que Jack fue a hablar con el más chico popular que sabía. Fue a Lou y le preguntó: ¿Qué hago? Lou vio que su amigo estaba muy angustiado. Bueno, él comenzó, justo mira cómo estás vestida. ¿No tienes nada de ropa con una mirada diferente? Sí, dijo Jack. Claro que si. Ven a mi casa y Voy a mostrarles a ustedes. Así se fueron a Jack. Y Jack mostró el cuadro de Lou donde guardaba todas sus camisas, y sus pantalones y los calcetines. Lou dijo: Veo que tienes toda la ropa en una pila. ¿Por qué no te pones un poco de demás de vez en cuando? 

Jack dijo, bueno, cuando yo quitar la ropa y calcetines, Yo les lavo y puse a la basura en la caja. Luego viene la siguiente mañana, y hasta me salto. Voy a la caja y obtengo mi ropa de la parte superior. Lou se dio cuenta rápidamente el problema con Jack. Mantuvo ropa, CDs, y los libros de la pila. Cuando llegó a algo para leer o llevar, él elegiría el libro superior o ropa interior. Luego, cuando terminó, lo pondría de vuelta. Volver iría, en la parte superior de la pila. Yo sé la solución, dijo un Loud triunfante. Tienes que aprender a empiece a usar una cola. Lou tomó la ropa de Jack y los colgó en el armario. Y cuando él había vaciado la caja, él simplemente lo tiró. 

Luego dijo, ahora Jack, al final de el día, poner la ropa a la izquierda cuando se los pone lejos. Entonces mañana por la mañana cuando se ver el sol, ponerse la ropa a la derecha, desde el final de la línea. ¿No lo ves? dijo Lou. Será tan agradable. Te llevas todo una vez antes de que te pones algo dos veces. Y con todo, en las colas en su armario y estante, Jack empezó a sentir muy seguro de sí mismo. Todo gracias a Lou y su maravillosa cola. ALTAVOZ 1: Muy bien, es adorable. Así que lo que ha sido realmente va de debajo de la campana ahora? Que tenemos punteros, que tenemos malloc, que tenemos la capacidad de crear trozos de memoria para nosotros mismos dinámicamente. Así que esta es una imagen que nos vislumbrado el otro día. Nosotros realmente no moramos en ella, pero esta imagen ha estado sucediendo por debajo el capó desde hace semanas. Y por lo que esta representa, simplemente un rectángulo que hemos dibujado, la memoria del equipo. Y tal vez su computadora, o CS50 Identificación, tiene un gigabyte de memoria o la memoria RAM o dos gigabytes o cuatro. En realidad no importa. Su sistema operativo Windows o Mac OS o Linux, esencialmente le permite a su programa a pensar que tiene acceso a la totalidad de la memoria del equipo, a pesar de que podría estar ejecutando varios programas a la vez. Así que en realidad, que no funciona muy bien. Pero es una especie de ilusión dado a todos sus programas. Así que si usted tenía dos gigas de RAM, este Es así como el equipo podría pensar en él. 

Ahora es coincidencia que uno de ellos cosas, uno de estos segmentos de memoria, se llama una pila. Y, en efecto cualquier momento hasta el momento en la escritura de código que ha llamado función, por ejemplo principal. Recuerdo que cada vez que tengo la memoria del ordenador dibujado, Siempre me baso tipo de medio de un rectángulo aquí y no te molestes en hablar sobre lo que está arriba. Porque cuando principal se llama, yo reclamo que se obtiene de este trozo de la memoria que pasa por aquí. Y si una función principal llamado como swap, así canje va aquí. Y resulta, eso es donde está terminando. En algo que se llama una pila dentro de la memoria del equipo. Ahora, al final del día, esto es sólo aborda. Es como cero bytes, byte uno, byte 2 mil millones. Pero si se piensa en ello como este objeto rectangular, todo lo que estamos haciendo todos los tiempo que llamamos una función es capas de un nuevo segmento de memoria. Estamos dando a esa función una rebanada de su propia memoria para trabajar. 

Y recuerda ahora que esto es importante. Porque si tenemos algo así como de intercambio y dos variables locales como A y B y cambiamos los valores de uno y dos a dos y uno, el recuerdo que cuando regresa de intercambio, es como si este pedazo de la memoria simplemente se ha ido. En realidad, sigue siendo hay forense. Y algo todavía está realmente allí. Pero conceptualmente, es como aunque ha desaparecido por completo. Y así principal no sabe cualquiera de los trabajos que se hizo en esa función de intercambio, a menos que en realidad pasó en los argumentos de puntero o de referencia. Ahora, la solución fundamental a ese problema de intercambio es pasar las cosas en su dirección. Pero resulta que, también, lo que es estado pasando por encima de esa parte del rectángulo de todo este tiempo es sin embargo, hay más memoria hasta allí. Y cuando dinámicamente asignar memoria, ya sea en el interior de GetString, que que hemos estado haciendo para usted en el CS50 biblioteca, o si ustedes llamar a malloc y pedir el sistema operativo de un trozo de memoria, que no viene de la pila. Viene de otro lugar en la memoria de su computadora eso se llama el montón. Y eso no es nada diferente. Es la misma memoria RAM. Es la misma memoria. Es sólo la memoria RAM que es hasta allí en vez de aquí. 

Y así, ¿qué significa eso? Bueno, si el equipo tiene una cantidad finita de memoria y la pila está creciendo, por lo que hablar, y el montón, de acuerdo a esta flecha, está creciendo hacia abajo. En otras palabras, cada vez que se llama a malloc, que está siendo dado una rebanada de la memoria desde arriba, entonces tal vez un poco más bajo, luego un poco inferior, cada vez que se llama a malloc, el montón, es el uso, es una especie de crecimiento, creciendo más y más a lo que? La pila. Así que ¿esto parece una buena idea? Quiero decir, cuando en realidad no es clara ¿qué otra cosa se puede hacer si solamente tienen una cantidad finita de memoria. Pero esto es seguramente malo. Esos dos flechas están en una Curso acelerado por el otro. 

Y resulta que los malos, la gente que son particularmente bueno con la programación, y tratando de introducirse en los ordenadores, puede explotar esta realidad. De hecho, vamos a considerar un pequeño fragmento. Así que este es un ejemplo, usted puede leer acerca con más detalle en la Wikipedia. Te indicamos en el artículo si curiosa. Pero hay un ataque general conocido como desbordamiento de búfer que ha existido durante tanto tiempo como los humanos han tenido la capacidad de manipular la memoria del ordenador, especialmente en C. Así que este es un programa muy arbitraria, pero vamos a leer desde abajo hacia arriba. Principal en estrella ARGC carbón argv. Así que es un programa que toma argumentos de la línea de comandos. Y todo principal no parecer es llamar una función, lo llaman F para la simplicidad. Y que pasa en qué? Argv de uno. Por lo tanto, pasa a la F lo la palabra es que el usuario escribió en el indicador después de la El nombre del programa en absoluto. Tanto como César o Vigenére, que se puede recordar haciendo con argv. 

Entonces, ¿qué es F? F lleva en una cadena como único argumento, También conocido como una estrella char, misma cosa, como una cadena. Y se llama arbitrariamente bar en este ejemplo. Y luego carbón c 12, sólo en términos sencillos, lo que es carbón c soporte 12 haciendo por nosotros? ¿Qué se hace? La asignación de memoria, específicamente 12 bytes para 12 caracteres. Exactamente. Y luego la última línea, revolver y copia, usted probablemente no se ve. Esta es una copia de cadena función cuyo propósito en la vida es copiar su segundo argumento en su primer argumento, pero sólo hasta una cierto número de bytes. Así que el tercer argumento dice, cuantos bytes debe copiar? La longitud de la barra, cualquiera que sea el usuario escribió en. Y el contenido de bar, esa cadena, son copia en la memoria apuntada en al C. 

Así que esto parece un poco estúpido, y lo es. Es un ejemplo artificial, pero es representativa de una clase de vectores de ataque, una manera de atacar a un programa. Todo está bien y bueno si el usuario tipos en una palabra que es 11 caracteres o menos, además de la barra invertida cero. ¿Qué pasa si el usuario escribe en más de 11 o 12 o 20 o 50 caracteres? ¿Cuál es este programa va a hacer? Culpa Potencialmente seg. Está yendo copiar ciegamente todo lo que en la barra de arriba a su longitud, que es literalmente todo en el bar, en la dirección apuntando a C. Pero C sólo se ha dado de manera preventiva como de 12 bytes. Pero no hay ninguna comprobación adicional. No hay, si las condiciones. No hay ninguna comprobación de errores aquí. 

Y así lo que este programa es vamos a hacer es a ciegas copiar una cosa a la otra. Y así, si trazamos este como una imagen, aquí está Sólo una pequeña porción del espacio de memoria. Así que notamos en la parte inferior, que tener la barra de variable local. Así que ese puntero que va a almacén-- más bien que el argumento local que es va a almacenar la barra de cadena. Y luego tan solo por encima de ella en una pila, porque cada vez que pides para la memoria en la pila, va un poco por encima de ella ilustrado, aviso de que tenemos 12 bytes allí. El superior izquierdo es el soporte C cero y la parte inferior derecha es C soporte de 11. Así es como las computadoras va a sentar a cabo. Así que sólo intuitivamente, si la barra tiene más de 12 caracteres en total, incluyendo la barra invertida cero, ¿dónde está el 12 o el soporte de C 12 a ir? O más bien ¿dónde está el día 12 carácter o el carácter 13, el carácter centésima ir para terminar en la foto? ¿Arriba o abajo? 

Claro, porque a pesar de que la propia pila crece hacia arriba, una vez que haya puesto cosas en ello, por razones de diseño, pone la memoria de arriba a abajo. Así que si usted tiene más de 12 bytes, usted va a empezar a sobrescribir bar. Eso sí que es un error, pero es no realmente un gran acuerdo. Pero es una gran cosa, porque no hay más cosas que están pasando en la memoria. Así que aquí está cómo podríamos poner hola, para ser claros. Si he escrito en hola en el indicador. Barra invertida cero H-E-L-L-O, termina dentro esos 12 bytes, y estamos super seguro. Todo está bien. Pero si escribo algo más largo, que es potencialmente va a arrastrarse en el espacio bar. Pero peor aún, resulta fuera de todo este tiempo, a pesar de que nunca hemos hablado de ella, la pila se utiliza para otras cosas. No son sólo las variables locales. 

C es un lenguaje de nivel muy bajo. Y es una especie de secreto usa la pila también recordar cuando un función se llama, lo que la dirección es de la función anterior, por lo que puede saltar de nuevo a esa función. Así que cuando las llamadas principales intercambian, entre las cosas insertan en la pila no son sólo intercambia variables locales, o sus argumentos, también empujaron en secreto en la pila tal como se representa por la rebanada rojo aquí, es la dirección del principal físicamente en la memoria de su computadora, de modo que cuando se hace de intercambio, el ordenador sabe que tengo que volver a la principal y terminar la ejecución de la función principal. Así que esto es peligroso ahora, porque si el usuario escribe así más de hola, de tal manera que clobbers la entrada del usuario o sobrescribe esa sección roja, lógicamente si del ordenador sólo va a asumir ciegamente que los bytes en esa rebanada rojo son la dirección a la que debe devolver, ¿y si el adversario es lo suficientemente inteligente o la suerte de poner una secuencia de bytes hay que se parece a una dirección, pero es la dirección de código que él o ella quiere que el equipo para ejecutar en lugar de principal? 

En otras palabras, si lo que el usuario está escribiendo en el indicador, no es sólo algo como inocua hola, pero en realidad es un código que es equivalente eliminar todos los archivos de este usuario? O enviar por correo electrónico su contraseña a mí? O iniciar el registro de su pulsaciones de teclado, ¿verdad? Hay un camino, vamos a estipulan hoy, que podían escribir no solo hola mundial o su nombre, que podían esencialmente Aconteció en código, ceros y queridos, que el ordenador errores tanto de código y una dirección. Así que aunque algo abstracto, si el usuario escribe lo suficientemente código acusatorio que vamos a generalizar aquí A. A es ataque o adversarios. Así las cosas simplemente malo. No importa el números o los ceros o unos hoy en día, de modo que usted termina sobrescribir esa sección roja, notar que secuencia de bytes. O 835 C cero ocho cero. Y ahora como artículo de Wikipedia aquí ha propuesto, si ahora de empezar etiquetado de los bytes en su equipo de la memoria, lo que el artículo de Wikipedia es proponiendo es que, ¿qué pasa si la dirección de ese byte superior izquierda es 80 C 0 3508. 

En otras palabras, si el malo de la película es lo suficientemente inteligente con su código para poner en realidad un número aquí que corresponde a la dirección del código él o ella inyecta en el equipo, puede engañar a la computadora a hacer cualquier cosa. La eliminación de archivos, correo electrónico cosas, olfateando su tráfico, literalmente, cualquier cosa podría ser inyectada en el ordenador. Y así un desbordamiento de búfer ataque en su núcleo es sólo un estúpido, estúpido primordial de una matriz que no tienen sus límites comprobados. Y esto es lo que es super peligroso ya la vez súper poderoso en C es que nosotros tenemos de hecho acceso a cualquier lugar de la memoria. Todo depende de nosotros, los programadores, que escriben el código original para comprobar la longitud de cualquier maldito matrices que estamos manipulando. Así que para que quede claro, ¿cuál es la solución? Si rodamos de nuevo a este código, no sólo debe cambiar la longitud de la barra, lo que más debo revisaré? ¿Qué más debo hacer para prevenir este ataque por completo? No quiero decir simplemente ciegamente que copie tantos bytes como es la longitud de la barra. Quiero decir, copiar como muchos bytes como están en la barra hasta el asignado memoria, o 12 como máximo. Así que necesito algún tipo de condición if que hace comprobar la longitud de la barra, pero si es superior a 12, sólo dura código 12 como la distancia máxima posible. De lo contrario, el tampón de llamada ataque de desbordamiento puede suceder. En la parte inferior de las diapositivas, si tienes curiosidad para leer más es el artículo original real si quieres echar un vistazo. 

Pero ahora, entre los precios pagados aquí fue ineficiencias. Así que fue una rápida bajo nivel vistazo a lo que pueden surgir problemas ahora que tener acceso a la memoria del ordenador. Pero otro problema que ya tropezado el lunes era sólo la ineficacia de una lista enlazada. Estamos de vuelta a tiempo lineal. Ya no tenemos una matriz contigua. No tenemos acceso aleatorio. No podemos usar la notación de corchetes. Literalmente, hay que utilizar un bucle while como la que yo escribí hace un momento. Pero el lunes, reclamamos que podemos colarse de nuevo en el ámbito de la eficiencia lograr algo que es logarítmica, tal vez, o mejor aún, tal vez incluso algo que es la llamada constante de tiempo. Entonces, ¿cómo podemos hacer que al utilizar estos nuevos herramientas, estas direcciones, estos indicadores, y roscado cosas de nosotros mismos? Bueno, supongamos que aquí, se trata de un grupo de los números que queremos almacenar en un estructura de datos y búsqueda eficiente. Sin duda nos podemos retroceder a la semana dos, tirar estos en una matriz, y la búsqueda de ellos mediante la búsqueda binaria. Divide y conquistarás. Y, de hecho, que escribió búsqueda binaria en PSET3, donde se implementó el programa de búsqueda. Pero sabes que. Hay una especie de más forma inteligente de hacerlo. Es un poco más sofisticado y tal vez nos permite ver qué binaria búsqueda es mucho más rápido. En primer lugar, vamos a introducir la noción de un árbol. Que a pesar de que en árboles realidad tipo de creciendo así, en el mundo de la informática la ciencia que tipo de crecer hacia abajo como un árbol de familia, donde usted tiene sus abuelos o bisabuelos o lo que sea en la parte superior, el patriarca y la matriarca de la familia, sólo uno denominada raíz, nodo, por debajo cuales son sus hijos, por debajo del cual son sus hijos, o sus descendientes en general. Y cualquiera colgando la parte inferior de la familia árbol, además de ser el más joven de la familia, también puede ser sólo genéricamente llamado las hojas del árbol. 

Así que esto es sólo un montón de palabras y definiciones de algo que se llama un árbol en equipo la ciencia, como un árbol genealógico. Pero hay encarnaciones más elegantes de árboles, uno de los cuales se llama un árbol de búsqueda binario. Y usted puede clase de tomadura de pelo aparte lo que hace esta cosa. Bueno, es binario en qué sentido? ¿De dónde viene el binario viene de aquí? ¿Apenado? No es tanto un bien o. Es más que cada uno de los nodos no tiene más de dos hijos, como vemos aquí. En general, un tree-- y sus padres y abuelos puede tener tantos hijos o nietos, ya que realmente quieren, y así, por ejemplo, no tenemos tres los niños fuera de ese nodo mano derecha, pero en un árbol binario, un nodo tiene cero, uno o dos hijos como máximo. Y eso es una buena propiedad, porque si está coronada por dos, vamos a ser capaces de obtener un poco de base de registro de dos acción pasando aquí en última instancia. Así que tenemos algo logarítmica. Pero más sobre esto en un momento. Búsqueda árbol significa que los números son dispuesto de tal manera que el hijo izquierdo de valor es mayor que la raíz. Y su hijo derecho es más grande que la raíz. En otras palabras, si usted toma alguno de los linfáticos, los círculos en esta imagen, y mira a su izquierda niño y su hijo derecho, el primero debe ser inferior a, la segunda debe ser mayor que. Así cordura comprobar 55. Se niño dejado es 33. Es menos. 55, su hijo derecho es 77. Es mayor que. Y eso es una definición recursiva. Podríamos revisar cada uno de los nodos y el mismo patrón obstaculicen. 

Así que lo que es bueno en un árbol binario de búsqueda, es que uno, podemos ponerlo en práctica con una estructura, al igual que este. Y a pesar de que estamos lanzando un montón de estructuras en su, son un tanto intuitiva ahora con suerte. La sintaxis es aún arcana a ciencia cierta, pero el contenido de un nodo en este context-- y guardamos usando el nodo palabra, si se trata de un rectángulo en la pantalla o un círculo, que es sólo un poco de contenedor genérico, en este caso de un árbol, como el que se vimos, necesitamos un número entero en cada uno de los nodos y entonces necesito dos punteros apuntando al hijo izquierdo y el hijo derecho, respectivamente. Así que esa es la forma en que podría implementar que en una estructura. ¿Y cómo podría yo poner en práctica en el código? Bueno, vamos a echar un rápido mirar a este pequeño ejemplo. No es funcional, pero he copiado y pegado esa estructura. Y si mi función para un binario árbol de búsqueda se llama búsqueda, y esto tiene dos argumentos, un N entero y un puntero a un nodo, por lo que un puntero al árbol o un puntero a la raíz de un árbol, cómo hago para la búsqueda de N? Bueno, en primer lugar, porque soy tratar con punteros, Yo voy a hacer una comprobación de validez. Si es igual a los iguales árbol nulo, es N en este árbol o no en este árbol? No puede ser, ¿verdad? Si estoy pasado nulo, no hay nada allí. Puede ser que también acaba de ciegamente decir return false. Si me das nada, seguramente no puede encontrar cualquier número N. Entonces, ¿qué más podría yo ¿revisalo ahora? Yo voy a decir así más si N es menos de lo que está en el nodo del árbol que he estado entregué valor N. En otras palabras, si el número estoy buscando, N, es menor que el nodo que estoy mirando. Y el nodo estoy buscando por lo que se llama árbol, y recordar del ejemplo anterior para obtener el valor de un puntero, Utilizo la notación flecha. Así que si n es menor que el árbol flecha N, quiero ir conceptualmente izquierda. ¿Cómo puedo expresar searching fui? Para que quede claro, si esto es la imagen en cuestión, y me han pasado esa superior arrow eso está apuntando hacia abajo. Esa es mi puntero del árbol. Estoy apuntando a la raíz del árbol. Y estoy buscando por ejemplo, para el número 44, de manera arbitraria. Es 44 menor o mayor que 55 obviamente? Así que es menos. Y por lo que esta condición se aplica si. Así conceptualmente, lo que es lo que quiero buscar siguiente si estoy buscando 44? ¿Sí? 

Exactamente, quiero buscar el hijo izquierdo, o el sub-árbol de la izquierda de esta imagen. Y, de hecho, me dejó a través la imagen aquí abajo por un momento, ya que No puedo arañar esto. Si empiezo aquí a 55, y Sé que el valor 44 Yo estoy buscando es a la izquierda, es una especie de como arrancar la guía telefónica en medio o desgarrar el árbol por la mitad. Yo ya no tengo que preocuparse todo este medio del árbol. Y, sin embargo, curiosamente, en términos de la estructura, esta cosa aquí que comienza con 33, que la propia es un árbol de búsqueda binaria. Dije la palabra recurrente antes porque de hecho esta es una estructura de datos que por definición es recursiva. Es posible que tenga un árbol que es esto grande, pero cada uno de sus hijos representa un árbol un poco más pequeño. En lugar de que sea el abuelo o la abuela, ahora es sólo madre o-- No puedo no decir-- mamá o papá, eso sería raro. En lugar de los dos niños allí sería como hermano y hermana. Una nueva generación del árbol genealógico. Pero estructuralmente, es la misma idea. Y resulta que tengo una función con el que puedo buscar una búsqueda binaria árbol. Se llama búsqueda. Busco N en árbol de flecha izquierda else if N es mayor que el valor que soy actualmente. 55 en la historia hace un momento. Tengo una función llamada búsqueda que puedo simplemente N pasar esto y buscar de forma recursiva el sub-árbol y acaba de retorno sea ​​cual sea la respuesta. Else Tengo un poco de caso base final aquí. 

¿Cuál es el último caso? Árbol es o bien nulo. El valor o yo estoy buscando es menos de lo que o mayor que la o igual a ella. Y yo podría decir igual iguales, pero lógicamente es equivalente a sólo decir más aquí. Tan cierto es lo que encuentro algo. Así que espero que este es un Incluso ejemplo más convincente que la función sigma estúpido hicimos un par de conferencias espalda, donde era tan fácil de usar un bucle para contar todos los números de un a N. Aquí, con una estructura de datos que en sí es de forma recursiva Definimos y recursiva atraídos, ahora tener la capacidad de expresarnos en el código que sí es recursivo. Así que este es el mismo código exacto aquí. 

Entonces, ¿qué otros problemas podemos resolver? Así que un rápido paso de distancia de árboles para un momento. Aquí es, digamos, la bandera alemana. Y hay claramente una patrón para este indicador. Y hay un montón de banderas del mundo que son tan simple como esto en términos de sus colores y patrones. Pero supongamos que este se almacena como una GIF o JPEG, o mapa de bits o un ping, cualquier formato de archivo gráfico con el que está familiarizado, algunos de los cuales estamos jugando con en PSET4. Esto no parece que vale la pena para almacenar pixel negro, pixel negro, pixel negro, punto, punto, punto, un montón de píxeles negros para la primera línea de exploración, o fila, a continuación, en su conjunto montón de la misma, entonces un manojo entero de la misma, y ​​luego una toda montón de píxeles rojos, píxeles rojos, píxeles rojos, a continuación, en su conjunto montón de píxeles de color amarillo, amarillo, ¿verdad? 

Hay tal ineficiencia aquí. ¿Cómo haría usted intuitivamente comprimir la bandera alemana si su aplicación como un archivo? Al igual que lo que la información no podemos nosotros molestarse almacenar en el disco con el fin para disminuir el tamaño de nuestro archivo de como un megabyte a un kilobyte, algo más pequeño? En donde se encuentra la redundancia aquí para ser claro? ¿Qué podrías hacer? ¿Sí? Exactamente. ¿Por qué no en lugar de recordar el color de cada píxel darn al igual que lo está haciendo en PSET4 con el formato de archivo de mapa de bits, ¿por qué no acaba de Representas a la columna de la izquierda de píxeles, por ejemplo un montón de píxeles negros, un grupo de color rojo, y un montón de amarillo, y luego simplemente alguna manera codificar el idea de la repetición de este 100 veces o repetir esto 1.000 veces? Donde 100 o 1000 es sólo un número entero, por lo que puede conseguir lejos con apenas un solo número en lugar de cientos o miles píxeles de adicionales. Y de hecho, así es como nos podría comprimir la bandera alemana. Y Ahora ¿qué pasa con la bandera francesa? Y un poco de algún tipo de ejercicio mental, que la bandera se puede comprimir más en el disco? La bandera alemana o los franceses bandera, si tomamos este enfoque? La bandera alemana, porque hay redundancia más horizontal. Y por diseño, muchos archivos gráfico formatos de hecho funcionan como líneas de escaneo horizontalmente. Podrían trabajar verticalmente, justo la humanidad Hace años decidido que vamos a en general, pensar en fila cosas por fila en lugar de la columna por columna. Así que de hecho si fueras para mirar el archivo tamaño de una bandera alemana y francesa bandera, siempre que la resolución es el mismo, el mismo ancho y la altura, éste aquí va a ser más grande, porque usted tener que repetir tres veces. Tiene que especificar azul, repita a ti mismo, blanco, repita usted mismo, rojo, te repitas. No se puede ir todo el camino a la derecha. Y como un aparte, para hacer borrar la compresión está en todas partes, si éstas son cuatro cuadros de un video-- usted podría recordar que una película o vídeo es generalmente como 29 o 30 fotogramas por segundo. Es como un pequeño libro de tapa donde simplemente ver la imagen, imagen, imagen, imagen, imagen acaba muy rápido por lo que parece los actores de la pantalla están moviendo. Aquí está un abejorro en la parte superior de un ramo de flores. Y a pesar de que podría ser una especie de difícil de ver a simple vista, lo único que se mueve en esta película es la abeja. 

¿Cuál es mudo sobre el almacenamiento vídeo sin comprimir? Es un poco una pérdida para almacenar vídeo como cuatro imágenes casi idénticas que difieren sólo en la medida en que la abeja es. Usted puede tirar más de esa información y sólo recordar, por ejemplo, el primer fotograma y la última trama, fotogramas clave si ha Alguna vez has oído la palabra, y acaba de almacenar en el medio, donde la abeja es. Y usted no tiene que almacenar la totalidad de la rosa, y el azul, y el valores verdes también. Así que esto es para decir sólo eso compresión está en todas partes. Es una técnica que utilizamos a menudo o dar por hecho estos días. 

Pero, ¿cómo comprimir texto? ¿Cómo usted va sobre la compresión de texto? Bueno, cada uno de los personajes de ASCII es un byte, u ocho bits. Y eso es un poco tonto, ¿no? Debido a que es probable que el tipo A y E y I y O y U mucho más de las veces como W o Q o Z, dependiendo del idioma en el que estás escribiendo, sin duda. Y ¿por qué estamos usando ocho bits para cada letra, incluidos los menos letras populares, ¿verdad? ¿Por qué no utilizar menos bits para las letras súper populares E igual, las cosas que adivinen primero en la Rueda de la Fortuna, y utilizar más bits para las letras menos populares? ¿Por qué? Debido a que sólo vamos a utilizarlos con menos frecuencia. 

Bueno, resulta que no tienen habido intentos de hacer esto. Y si usted recuerda de grado la escuela o el instituto, el código Morse. Código Morse tiene puntos y guiones que pueden ser transmitida a lo largo de un alambre como sonidos o señales de algún tipo. Pero el código Morse es un super limpio. Es una especie de un sistema binario en que tiene puntos o guiones. Pero si usted ve, por ejemplo, dos puntos. O si usted piensa de nuevo al operador quien va como bip, bip, bip, pitido, golpear un poco el gatillo que transmite una señal, si, el destinatario, recibe de dos puntos, ¿qué mensaje han recibido? Completamente arbitraria. 

¿YO? ¿YO? O lo que sobre-- o yo? Tal vez fue sólo dos a la derecha de E? Así que hay este problema de decodabilidad con Morse código, con lo que a menos que el persona que envía el mensaje de que en realidad entra en pausa para usted puede clasificar de ver o escuchar los espacios entre las letras, que no es suficiente sólo para enviar un flujo de ceros y unos, o puntos y rayas, porque no hay ambigüedad. E es un solo punto, por lo que si ver dos puntos o escuchar dos puntos, tal vez es dos E de o tal vez es uno I. Así que necesitamos un sistema que es un poco más inteligente que eso. Así que un hombre llamado Huffman años Hace ocurrió exactamente esto. Así que sólo vamos para tomar una rápida mirada la forma en que los árboles son pertinentes a este. Supongamos que se trata de algún estúpido mensaje que desea enviar, compuesta de ir del punto A, B, C de D's y E de, pero hay una gran cantidad de redundancia aquí. No está destinado a ser Inglés. No está encriptada. Es sólo un estúpido mensaje con un montón de repetición. Así que si usted realmente contar toda la Atléticos, B, C de, D's, y E de, aquí está la frecuencia. 20% de las cartas son A de hasta un 45% de las cartas son de E, y otros tres frecuencias. Contamos allí manualmente y acaba de hacer los cálculos. 

Así resulta que Huffman, hace algún tiempo, dio cuenta de que, ya sabes lo que, si empiezo edificio un árbol, o el bosque de los árboles, si se quiere, de la siguiente manera, puedo hacer lo siguiente. Voy a dar un nodo para cada uno de las cartas que me importan y yo voy a almacenar dentro de ese nodo las frecuencias como punto flotante valor, o usted podría utilizar una N, también, pero nosotros sólo usaremos un flotador aquí. Y el algoritmo que propuso es que usted tomar este bosque de un solo nodo árboles, árboles tan super cortos, y empezar a conectar con nuevos grupos, nuevos padres, si se quiere. Y lo hace mediante la elección del dos frecuencias más pequeños a la vez. Así que tomé el 10% y 10%. Creo un nuevo nodo. Y que yo llamo el nuevo nodo 20%. 

¿Qué dos nodos combino después? Es un poco ambigua. Así que hay algunos casos de esquina a considerar, pero para mantener las cosas bastante, Voy a elegir 20% - Yo ahora ignoro los niños. Voy a elegir 20% y 15% y dibuja dos nuevas aristas. Y ahora que dos nodos Cómo puedo lógicamente combino? No haga caso de todos los niños, todos los nietos, basta con ver las raíces ahora. ¿Con cuál de dos nodos vinculo juntos? Punto dos y 0,35. Así que permítanme dibujar dos nuevas aristas. Y entonces yo sólo tengo uno izquierdo. Así que aquí está un árbol. Y se ha elaborado deliberadamente mirar especie de bonito, de notar que los bordes tienen También ha etiquetado cero y uno. Así que todos los bordes izquierdos son cero arbitrariamente, pero consistente. Todos los bordes derechos son queridos. 

Y así lo Hoffman propone es, si usted quiere representar una B, en lugar de representar el número 66 como un archivo ASCII que es ocho bits enteros, ¿sabes qué, tienda sólo el patrón cero, cero, cero, cero, porque ese es el camino de mi árbol, árbol del Sr. Huffman, a la hoja de la raíz. Si desea almacenar un E, por el contrario, no lo hagas enviar ocho bits que representan una E. En su lugar, envíe qué patrón de bits? Uno. Y lo que es bueno de esto es que E es la letra más popular, y está utilizando el código más corto para ello. El siguiente más popular carta parece que fue A. Y así la cantidad de bits no se propone utilizar para eso? Cero uno. 

Y como está implementado ya que este árbol, por ahora déjame estipulo que hay sin ambigüedad como en Morse código, porque todo el cartas que te importan están en el extremo de estos bordes. Así que eso es sólo una aplicación de un árbol. Esta es-- y voy onda mi mano en este cómo podría aplicar esto como una estructura C. Sólo tenemos que combinar un símbolo, como un char, y la frecuencia en la izquierda y la derecha. Pero echemos un vistazo a las dos ejemplos finales que Tú llegar a ser muy familiarizado con después cuestionario de cero en un problema fijó cinco. 

Así que no es la estructura de datos conocida como una tabla hash. Y una tabla hash es una especie de enfriar en que tiene cubos. Y supongo que hay cuatro cubos aquí, sólo cuatro espacios en blanco. Aquí hay una baraja de cartas, y aquí está club, espada, club, diamante, club, diamantes, clubes, diamantes, clubs-- por lo que este es el azar. Corazones, Hearts-- así que estoy bucketizing todas las entradas aquí. Y a las necesidades de la tabla de hash mirar a su entrada, y luego ponerlo en un determinado colocar sobre la base de lo que se ve. Es un algoritmo. Y yo estaba usando un super algoritmo visual simple. La parte más dura de la que era recordando cuáles eran las fotos. Y luego está cuatro cosas totales. 

Ahora las pilas estaban creciendo, lo que es una cosa diseño deliberado aquí. Pero ¿qué otra cosa podía hacer? Así que en realidad aquí tenemos una montón de viejos libros del examen de la escuela. Supongamos que un grupo de nombres de los estudiantes son de aquí. Aquí hay una tabla hash más grande. En lugar de cuatro cubos, He, digamos 26. Y no queríamos ir prestado 26 cosas de fuera [? Annenberg?], Por lo que aquí es de cinco que representan A hasta la Z. Y si yo ver a un estudiante cuyo nombre comienza con A, Voy a poner su cuestionario allí. Si alguien empieza con C, allá, A-- realidad, no quería hacer eso. B pasa por aquí. Así que tengo A y B y C. Y Ahora aquí está otro estudiante A. Pero si esta tabla hash es implementado con una matriz, Soy una especie de jodido en este punto, ¿no? Yo como que necesito poner esto en alguna parte. 

Así que una manera de que pueda resolver esto es, todo derecho, A está ocupada, B está ocupado, C está ocupado. Voy a ponerlo en D. Así que en primero, tengo acceso instantáneo al azar a cada uno de los cubos para los estudiantes. Pero ahora es una especie de degeneró en algo lineal, porque si quiero buscar a alguien cuyo nombre comienza con A, puedo comprobar aquí. Pero si esto no es el A estudiante que estoy buscando, Yo como que tengo que empezar a comprobar los cubos, porque lo que hice era una especie de forma lineal sondear la estructura de datos. Una forma estúpida de decir basta con ver para la primera abertura disponible, y poner como un plan B, por así decirlo, o plan D en este caso, el valor en esa ubicación. Esto es justo lo que si ha tiene 26 ubicaciones y no hay estudiantes con el nombre de Q o Z, o algo así que, al menos que esté utilizando el espacio. 

Pero ya hemos visto más soluciones inteligentes aquí, ¿verdad? ¿Qué haría usted en su lugar si usted tiene un accidente? Si dos personas tienen el nombre de A, lo que haría han sido más inteligente o más solución intuitiva que sólo poner una donde se supone que D a ser? ¿Por qué no sólo tiene que ir afuera [? Annenberg?], como malloc, otro nodo, lo puso aquí y, a continuación, poner que un estudiante aquí. Así que básicamente tengo algún tipo de una matriz, o tal vez con más elegancia que a nosotros empezando a ver una lista enlazada. 

Y así una tabla hash es una estructura que podría tener un aspecto como este, pero más inteligentemente, algo llamado encadenamiento separado, por el que una tabla hash simplemente es una matriz, cada uno de cuyos elementos no es un número, es en sí mismo una lista enlazada. Así que usted obtenga acceso súper rápido decidir dónde hash de su valor a. Al igual que con el ejemplo de las tarjetas, Hice decisiones muy rápidas. Corazones va aquí, los diamantes va aquí. Lo mismo digo, A va aquí, D va aquí, B va aquí. Así super rápido look-ups, y si le sucede a ejecutar en un caso colisiones en el que tienes, dos las personas con el mismo nombre, bueno, entonces que acaba de empezar que los une. Y tal vez mantenerlos ordenados por orden alfabético, tal vez usted no lo hace. Pero al menos ahora tenemos el dinamismo. Así, por un lado tenemos súper rápido constante de tiempo, y el tipo de tiempo lineal involucrados si estas listas enlazadas empezar a ser un poco larga. 

Así que esta clase de tonto, Hace años broma geek. Al CS50 hack-a-thon, cuando los estudiantes del check in, algunos TF o CA cada año piensa que es gracioso que aguantar una señal de este tipo, donde se acaba significa que si su nombre comienza con A, ve por este camino. Si su nombre comienza con una B, vaya esto-- OK, es curioso tal vez más tarde en el semestre. Pero hay otra manera de hacer esto, también. Vuelve a eso. 

Así que hay esta estructura. Y esta es nuestra última estructura para hoy, que es algo que se llama un trie. T-R-I-E, que por alguna razón es corta para la recuperación, pero que se llama trie. Así que un trie es otro interesante amalgama de muchas de estas ideas. Es un árbol, lo que hemos visto antes. No es un árbol de búsqueda binaria. Es un árbol con cualquier número de hijos, pero cada uno de los niños en un trie es una matriz. Una matriz de tamaño, digamos, 26 o tal vez 27 si quieres apoyar nombres con guiones o apóstrofos en los nombres de las personas. 

Y lo que esta es una estructura de datos. Y si se mira desde arriba a abajo, como si mirar el nodo superior allí, M, es que apunta a lo más a la izquierda allí, que luego es A, X, W, E, L, L. Esto es sólo una estructura de datos que de forma arbitraria es almacenar nombres de las personas. Y Maxwell se almacena con sólo seguir un camino de matriz a matriz a matriz. Pero lo que es sorprendente de un trie es que, mientras que una lista enlazada e incluso una matriz, el mejor que hemos conseguido es tiempo lineal o logarítmica tiempo buscando a alguien. En esta estructura de datos de un trie, si mi estructura de datos tiene un nombre en ella y estoy en busca de Maxwell, estoy ir a buscarlo rápidamente. Yo sólo busco M-A-X-W-E-L-L. Si esta estructura de datos, por el contrario, si N es un millón, si hay una millón de nombres en esta estructura de datos, Maxwell todavía va a ser detectable después de sólo M-A-X-W-E-L-L pasos. Y los pasos David-- D-A-V-me-D. En otras palabras, mediante la construcción una estructura de datos que es conseguido todos estos arrays, todos los cuales ellos apoyan de acceso aleatorio, Puedo empezar a buscar de la gente nombre usando una cantidad de tiempo que es proporcional a no el número de las cosas en la estructura de datos, como un millón de nombres existentes. La cantidad de tiempo que me lleva a encontrar M-A-X-W-E-L-L en esta estructura de datos se proporcional no a la tamaño de la estructura de datos, pero a la longitud del nombre. Y realista el nombres que están mirando hacia arriba Nunca van a estar loco de largo. Tal vez alguien tiene un carácter 10 nombre, nombre de 20 caracteres. Ciertamente es finita, ¿verdad? No es un ser humano en la Tierra que tiene el nombre más largo posible, pero ese nombre es una constante longitud de valor, ¿no? Es no varía en ningún sentido. Así de esta manera, tenemos logrado una estructura de datos es decir constante de tiempo de consulta. Sin embargo, toma una serie de medidas dependiendo de la longitud de la entrada, pero no el número del nombre en la estructura de datos. Así que si duplicamos el número de nombres el año que viene a partir de un mil millones a dos mil millones, hallazgo Maxwell va a tomar el mismo número exacto de siete pasos para encontrarlo. Y así parece que hemos logrado nuestro santo grial de tiempo de ejecución. 

Así que un par de anunciar. Cuestionario cero se acerca. Más sobre esto en la página web del curso durante el próximo par de días. Lunes de lecture-- Es un día de fiesta aquí en Harvard el lunes. No está en New Haven, así que estamos tomando la clase a New Haven de la conferencia el lunes. Todo será filmado y transmitido en vivo como siempre, pero vamos a terminar hoy con un clip de 30 segundos llamados "Pensamientos profundos" por Daven Farnham, que se inspiró el año pasado por Sábado "Pensamientos profundos" de Night Live por Jack práctico, que Ahora debe tener sentido. 

CINE: Y ahora, "Deep Pensamientos "de Daven Farnham. Tabla de picadillo. 

ALTAVOZ 1: Muy bien, eso es todo por ahora. Nos vemos la semana que viene. 

DOUG: Para ver en acción. Así que vamos a echar un vistazo a eso ahora mismo. Así que aquí tenemos una matriz sin clasificar. 

IAN: Doug, ¿puedes seguir adelante y reinicio esto por sólo un segundo, por favor. De acuerdo, las cámaras están rodando, por lo acción cada vez que esté listo, Doug, ¿de acuerdo? DOUG: Muy bien, así que lo que tenemos aquí es una serie sin clasificar. Y he coloreé todos los elementos rojo para indicar que es, de hecho, sin clasificar. Así que recordemos que la primera cosa que hacemos es clasificamos la mitad izquierda de la matriz. Luego clasificamos la derecha medio de la matriz. Y ya-da, ya-da, ya-da, les funden. Y tenemos una gama completamente ordenado. Así es como fusionar tipo de obras. 

IAN: Espera, espera, espera, cortar, cortar, cortar, cortar. Doug, no puedes simplemente ya-da, ya-da, ya-da, su camino a través de combinación de clase. 

DOUG: Me acaba de hacer. Está bien. Somos buenos para ir. Sigamos la rodadura. Así que de todos modos, 

IAN: Usted tiene que explicar más plenamente que eso. Eso no es suficiente. DOUG: Ian, no lo hacemos que tenga que volver a uno. Está bien. Así que de todos modos, si seguimos con merge-- Ian, estamos en medio de la filmación. 

IAN: Lo sé. Y no podemos simplemente ya-da, ya-da, ya-da, a través de todo el proceso. Usted tiene que explicar cómo el Ambas partes quedan fusionadas juntas. 

DOUG: Pero ya hemos explicó cómo los dos sides-- 

IAN: Usted acaba mostrará ellos una matriz de mezcla. DOUG: Ellos conocen el proceso. Ellos están bien. Hemos pasado más de diez veces. 

IAN: Usted acaba de saltar por encima de ella. Vamos a volver a uno, ¿no es así ya-da, ya-da sobre él. Muy bien, de nuevo a uno. 

DOUG: Tengo que volver a través de todas las diapositivas? Dios mío. Es como la sexta vez, Ian. Está bien. 

IAN: De acuerdo. ¿Estás listo? Excelente. Acción.