[REPRODUCCIÓN DE MÚSICA] DAVID J. MALAN: Muy bien. Esto es CS50. Esta es la quinta semana continuó, y nos tener algunas buenas noticias y malas noticias. Así que buena noticia es que CS50 lanza este viernes. Si usted desea unirse a nosotros, dirigirse a la dirección URL habitual aquí. Aún mejor noticia, sin conferencia el próximo lunes 13. Algo menos mejores noticias, cuestionario de cero es el próximo miércoles. Más detalles pueden ser encontrado en este URL aquí. Y en los próximos días estaremos llenando los espacios en blanco con respecto a las habitaciones que habremos reservado. Mejor noticia es que no voy a ser un examen de todo el curso sesión el próximo Lunes por la noche. Estén atentos al curso de sitio web para la ubicación y detalles. Secciones, a pesar de que es un día de fiesta, también se reunirá también. Mejores noticias, conferencia el próximo viernes. Así que esta es una tradición que tener, según el plan de estudios. Solo-- que va a ser increíble. Usted verá cosas como estructuras de datos de tiempo constante y tablas y árboles y tries de patata. Y vamos a hablar de los problemas de cumpleaños. Un montón de cosas espera el próximo viernes. Okay. De todos modos. Así recordamos que hemos sido centrándose en la imagen de lo que está dentro de la memoria de nuestro ordenador. Así, la memoria o la memoria RAM es donde los programas existiendo mientras usted los está corriendo. Si hace doble clic en un icono para ejecutar algún programa o haga doble clic en un icono para abrir algún archivo, está cargada de su disco conducir o unidad de estado sólido en la memoria RAM, memoria de acceso aleatorio, donde vive hasta que se desconecte la alimentación, la tapa del portátil se cierra, o salir del programa. 

Ahora que la memoria, de que es probable que tenga 1 gigabyte estos días, 2 gigabytes, o incluso mucho más, generalmente se presenta para un programa dado en este tipo de rectangular modelo conceptual con lo cual tenemos la pila en la parte inferior y un montón de otras cosas en la parte superior. La cosa en la parte superior que hemos visto en esta imagen antes, pero nunca se habla es el llamado segmento de texto. Segmento de texto es sólo una forma elegante de decir los ceros y unos que componer su programa compilado real. 

Así que al hacer doble clic Microsoft Word en su Mac o PC, o cuando se ejecuta punto slash Mario en un Ordenador con Linux en la ventana de terminal, los ceros y unos que componen Word o Mario se almacenan temporalmente en la memoria RAM de su computadora en el llamado segmento de texto para un programa en particular. Debajo de eso va inicializado y datos sin inicializar. Esto es algo similar a las variables globales, que nosotros no hemos usado muchos de, pero en ocasiones nos hemos tenido variables globales o estáticamente cuerdas definido que está codificado palabras como "hola" que no son tomadas en el usuario desde que están codificados duro en su programa. 

Ahora, abajo en la parte inferior que tener la llamada pila. Y la pila, hasta ahora, hemos estado utilizando para qué tipo de propósitos? Lo que la pila se utiliza? ¿Sí? 

AUDIENCIA: Funciones. 

DAVID J. MALAN: Para las funciones? ¿En qué sentido para las funciones? 

AUDIENCIA: Cuando se llama a una función, el argumentos se copian en la pila. 

DAVID J. MALAN: Exactamente. Cuando se llama a una función, su argumentos se copian en la pila. Así que cualquier X o Y o A o B de la que está pasando en una función están temporalmente poner en la llamada pila, al igual que uno de los Annenberg bandejas de comedor, y también cosas como variables locales. Si su función foo o su canje función tiene variables locales, como la temperatura, los dos terminan en la pila. Ahora, no vamos a hablar demasiado sobre ellos, pero estas variables de entorno en la parte inferior que vimos hace un tiempo cuando Me pelearse en el teclado un día y empecé a acceder a las cosas como argv argv 100 o 1000, sólo elements-- olvido la numbers-- pero eso no se supone que es visitada por mí. Empezamos a ver algunas símbolos de funky en la pantalla. Esos eran los llamados variables de entorno como ajustes globales para mi programa o para mi equipo, no no relacionado con la reciente error que hemos discutido, Shellshock, que ha sido que azota a un buen número de ordenadores. 

Ahora, por último, en el enfoque de hoy vamos a ser en última instancia, en el montón. Esta es otra parte de la memoria. Y fundamentalmente todo esto la memoria es la misma materia. Es el mismo hardware. Somos sólo una especie de el tratamiento de diferentes grupos de bytes para diferentes propósitos. El montón también va a estar donde variables y memoria que usted solicite desde el sistema operativo se almacena temporalmente. 

Pero hay una especie de problema Aquí, como la imagen implica. Tenemos suerte de tener dos barcos a punto de chocar. Porque como se utiliza cada vez más de la pila, y como lo vemos hoy en día adelante, y cuando se utiliza cada vez más de la montón, seguramente las cosas malas pueden suceder. Y, de hecho, podemos inducir que con o sin intención. Así que el drama de suspenso última tiempo era este programa, que no servirá cualquier funcional propósito que no sea para demostrar cómo usted como un tipo malo en realidad puede tomar ventaja de los errores en el programa de alguien y hacerse cargo de un programa o incluso un sistema informático totalidad o servidor. Así que a simple vista brevemente, que notar que la principal en la parte inferior toma en la línea de comandos argumentos, como por argv. Y tiene una llamada a una función f, esencialmente una función sin nombre llama f, y está pasando en argv [1]. 

Así que cualquier palabra que el usuario escribe en al el símbolo detrás del nombre de este programa, y luego esta función arbitraria hasta superior, f, lleva en una cadena, conocido como char *, como hemos empezado a discutir, y que sólo lo llama "bar". Pero podríamos llamarlo nada. Y entonces se declara, en el interior de f, un conjunto de caracteres llamado c-- 12 de estos personajes. 

Ahora, por la historia que estaba contando Hace un momento, cuando en la memoria es c, o son los 12 CHARS va a terminar? Para que quede claro. ¿Sí? 

AUDIENCIA: En la pila. 

DAVID J. MALAN: En la pila. Así que c es una variable local. Estamos pidiendo 12 caracteres o 12 bytes. Esos van a terminar en la llamada pila. Ahora, finalmente, es esta otra función eso es realmente muy útil, pero nosotros no hemos usado realmente nosotros mismos, strncopy. Esto significa copia de cadena, pero sólo n letras, n caracteres. Así n caracteres serán copiado de bar en c. Y ¿cuántos? La longitud de la barra. Así, en otras palabras, que una línea, strncopy, va a copiar prohibir de manera efectiva en al c. 

Ahora, sólo para tipo de anticipar la moraleja de esta historia, lo que es potencialmente problemática aquí? A pesar de que estamos comprobando la longitud del bar y de pasarlo en strncopy, ¿Cuál es su intestino diciendo es todavía roto sobre este programa? ¿Sí? 

AUDIENCIA: No incluye espacio para el carácter nulo. DAVID J. MALAN: No incluye espacio para el carácter nulo. Potencialmente, a diferencia de práctica del pasado que ni siquiera tener tanto como un plus del 1 al acomodar ese carácter nulo. Pero es aún peor que eso. ¿Qué más estamos fallando a hacer? ¿Sí? 

AUDIENCIA: [inaudible] DAVID J. MALAN: Perfect. Duro Hemos codificamos 12 bastante arbitraria. Eso no es tanto la problema, pero el hecho de que ni siquiera estamos comprobando si la longitud de la barra es de menos de 12, en cuyo caso va a ser seguro para ponerlo en la memoria llamado c que hemos asignado. En efecto, si la barra es como 20 caracteres de largo, esta función parece estar copiando 20 personajes de bar en c, por lo tanto teniendo al menos 8 bytes que no debe ser. Esa es la implicación aquí. 

Así que en breve programa, roto. No como una gran cosa. Tal vez usted consigue un error de segmentación. Todos hemos tenido errores en los programas. Todos nosotros podríamos tener errores en los programas en estos momentos. Pero ¿cuál es la implicación? Bueno, aquí está una versión ampliada en de que la imagen de la memoria de mi ordenador. Este es el fondo de mi stack. Y, en efecto, en la parte inferior es lo que hay llamada pila rutina padre, forma elegante de decir que es principal. Así que todo el que llama a la función f que estamos hablando. Así que esta es la parte inferior de la pila. Dirección de retorno es algo nuevo. Siempre ha estado ahí, siempre ha sido en esa foto. Nosotros nunca llamamos la atención sobre él. Porque resulta que la forma c funciona es que cuando una función llama a otra, no sólo los argumentos que función get inserta en la pila, no sólo hacer local de la función variables de quedarse relegados en la pila, algo que se llama una dirección de retorno También consigue poner en la pila. En concreto, si las llamadas principales Foo, principales propia dirección en la memoria, el buey algo, efectivamente consigue poner en la pila de modo que cuando f se hace ejecutarlo sabe dónde para saltar de nuevo a en el texto segmento con el fin de continuar con la ejecución. 

Así que si estamos aquí conceptualmente, en principal, entonces f es llamado. ¿Cómo se sabe que f al control de la mano de vuelta? Bueno, este pequeño miga de pan en rojo aquí, llamado el remite, sólo cheques, lo que es que la dirección del remitente? Oh, déjame saltar de nuevo al principal aquí. Y eso es un poco de una simplificación excesiva, porque los ceros y unos por principales son técnicamente aquí en el segmento de tecnología. Pero esa es la idea. f sólo tiene que saber lo que a donde el control en última instancia se remonta. 

Pero la forma en ordenadores han sentado durante mucho tiempo fuera cosas como las variables locales y argumentos es así. Así que en la parte superior de esta imagen en azul es el marco de pila de f, por lo que todo de la memoria que f específicamente está utilizando. Así que en consecuencia, observe que bar está en esta foto. Bar era su argumento. Y reclamamos que los argumentos a funciones quedarse relegados en la pila. Y C, por supuesto, es También en esta imagen. 

Y sólo para propósitos de notación, cuenta en la esquina superior izquierda es lo que se c soporte 0 y a continuación, un poco hacia la derecha c es el soporte 11. En otras palabras, se puede imaginar que hay una rejilla de bytes allí, primero de los cuales es arriba a la izquierda, parte inferior de las cuales es el último de esos 12 bytes. 

Pero ahora tratar de avanzar rápidamente. ¿Qué va a ocurrir si pasamos en un bar de cadena que es más de c? Y no estamos comprobando si es de hecho más de 12. ¿Qué parte de esta imagen va a conseguir sobreescrito por bytes 0, 1, 2, 3, dot dot dot, 11, y luego malo, 12, 13 a través de 19? ¿Qué va a pasar aquí, si usted deducir del ordenamiento que c abrazadera 0 está en la parte superior y c abrazadera 11 es una especie de abajo a la derecha? ¿Sí? 

AUDIENCIA: Bueno, va sobrescribir el bar char *. 

DAVID J. MALAN: Sí, parece que usted va a sobrescribir char * bar. Y peor aún, si usted envía en un tiempo muy largo cadena, que incluso podría sobrescribir qué? La dirección de retorno. Que a su vez, es igual que un ruta de navegación para decirle al programa donde para ir de nuevo a cuando f se hace la que llama. 

Entonces, ¿qué chicos malos suelen hacer es si se encuentran con un programa que son curiosos si es explotable, con errores de forma que él o ella puede tomar ventaja de ese error, generalmente no reciben esta bien la primera vez. Sólo empezar a enviar, por ejemplo, cadenas aleatorias en su programa, ya sea en el teclado, o francamente que probablemente escribir un pequeño programa que acaba de generan automáticamente las cadenas, y empezar a golpear en su programa el envío de gran cantidad de diferentes insumos en diferentes longitudes. 

Tan pronto como sus errores en el programa, eso es una cosa increíble. Debido a que significa que él o que ha descubierto lo que probablemente es de hecho un error. Y entonces pueden conseguir más inteligente y empezar a centrarse más estrechamente sobre la forma de explotar ese error. En particular, lo que él o ella podría hacer es enviar, en el mejor de los casos, hola. No es gran cosa. Es una cadena que es suficientemente corto. Pero ¿y si él o ella envía, y vamos a generalizar como, ataque code-- tan ceros y los que hacen las cosas como rm-rf, que quitar todo desde el disco duro o enviar spam o atacar de alguna manera la máquina? 

Así que si cada uno de estos letras A sólo representa, conceptualmente, ataque, ataque, ataque, ataque, algunas malas código que alguien más escribió, pero si esa persona es lo suficientemente inteligente no sólo para incluir toda de esos rm-RFS, sino también tener sus últimos bytes ser un número que corresponde a la dirección de su o su propio código de ataque que él o ella pasó en apenas proporcionando en el prompt, se puede engañar a la computadora con eficacia en darse cuenta cuando f se realiza la ejecución, oh, es el momento para que salte de nuevo a la dirección de retorno rojo. Pero debido a que él o ella tiene de alguna manera superpuestas que remite con su propio número, y son lo suficientemente inteligentes haber configurado que número de referencia, ya que ver en el top estupendo esquina izquierda hay, la dirección real en el ordenador de memoria de algunos de su código de ataque, un chico malo puede engañar a la computadora en la ejecución de su propio código. 

Y ese código, de nuevo, puede ser cualquier cosa. Generalmente, se llama código shell, que es justo una forma de decir que no es generalmente algo tan simple como rm-rf. En realidad es algo así como Bash, o un programa que le da o su control de programación para ejecutar cualquier otra cosa que ellos quieren. Así que en resumen, todo esto deriva del simple hecho de que este error en cuestión no comprobación los límites de la matriz. Y debido a la forma en equipos de trabajo es que utilizar la pila de efectivamente, conceptualmente, parte inferior hacia arriba, pero luego los elementos usted empuja en la pila crezca arriba hacia abajo, esto es muy problemático. Ahora, hay maneras de evitar este. Y, francamente, hay lenguas con el que trabajar alrededor de esto. Java es inmune, por ejemplo, a este tema en particular. Porque ellos no te dan consejos. Ellos no te dan direcciones de memoria directa. Así que con este poder que tenemos tocar nada en la memoria queremos que viene, sin duda, un gran riesgo. 

Así que mantener un ojo hacia fuera. Si, francamente, en los meses de o años por venir, en cualquier momento usted lea acerca de cierto tipo de explotación de un programa o un servidor, si usted ve un atisbo de algo como un ataque de desbordamiento de búfer, o desbordamiento de pila es otro tipo de ataque, similar en espíritu, tanto como inspira el sitio web de nombrar, si lo conoce, todo está hablando sólo de rebosar el tamaño de algunos de carácter matriz o alguna variedad más general. Cualquier pregunta, entonces, sobre esto? No intente hacer esto en casa. 

Bien. Así malloc hasta ahora ha sido nuestro nuevo amigo en que podemos asignar memoria que no sabemos necesariamente en adelantamos que queremos lo que no tenemos a codificar en nuestra números de programas como 12. Una vez que el usuario nos dice cuánto datos que él o ella quiere de entrada, podemos malloc que gran parte de la memoria. 

Así malloc resulta, a la medida en que hemos estado usando, explícitamente la última vez, y luego ustedes han estado usando getString para saberlo para varias semanas, todos los de la memoria de malloc proviene de la llamada pila. Y es por eso getString, por ejemplo, puede asignar memoria dinámicamente sin saber lo que eres va a escribir de antemano, que devolver un puntero a la memoria, y que la memoria sigue siendo tuyo para siempre, incluso después GetString rendimientos. Porque recuerdo después de todo lo que el pila está constantemente subiendo y bajando, arriba y abajo. Y tan pronto como va abajo, eso significa que cualquier memoria esta función utilizada debe No ser utilizado por ninguna otra persona. Es valores de basura ahora. 

Pero el montón está aquí arriba. Y lo que es bueno de malloc es que cuando malloc asigna memoria hasta aquí, no está afectada, para la mayor parte, por la pila. Y por lo que cualquier función puede acceder memoria que se ha malloc'd, incluso por una función como getString, incluso después de que se devuelve. 

Ahora, lo contrario de malloc es gratis. Y, en efecto, la regla que que tenga que empezar a adoptar es cualquier, cualquier, cualquier momento usted utiliza malloc debe usted utilizar libre, con el tiempo, en ese mismo puntero. Durante todo este tiempo hemos estado escribiendo con errores, código erróneo, por muchas razones. Pero uno de los cuales ha sido utilizando la biblioteca de CS50, que sí es deliberadamente con errores, se pierde memoria. Cada vez que usted ha llamado getString durante las últimas semanas estamos haciendo la operación sistema, Linux, para la memoria. Y usted nunca una vez dado por ti. Y esto no es, en practicar, una buena cosa. 

Y Valgrind, uno de los herramientas introducidas en el juego de parámetros 4, se trata de ayudar usted ahora encontrar errores como ese. Pero por suerte para Pset 4 no es necesario utilizar la biblioteca CS50 o getString. Así que cualquier error relacionados con la memoria son en última instancia, va a ser la suya. 

Así malloc es algo más que conveniente para este propósito. En realidad, ahora podemos resolver fundamentalmente diferentes problemas, y resolver fundamentalmente los problemas más eficazmente como por la promesa de la semana cero. Hasta el momento esta es la más sexy estructura de datos que hemos tenido. Y por la estructura de los datos que acabo de decir una forma de memoria conceptualizar de una manera que va más allá de sólo decir, este es un int, este es un char. Podemos empezar junto a las cosas de racimo. 

Así que una matriz se veía así. Y lo que fue clave en aproximadamente una array es que te da back-to-back trozos de memoria, cada uno de los cuales va a ser del mismo tipo, int, int, int, int o char, char, char, Char. Pero hay algunas desventajas. Esto por ejemplo, es una matriz de tamaño seis. Supongamos que usted llene esta matriz con seis números y luego, por las razones que sean, el usuario quiere dar que un séptimo número. ¿Dónde lo pusiste? 

¿Cuál es la solución si usted tiene creado una matriz en la pila, por ejemplo, sólo con la semana dos notación que hemos introducido, de corchetes con un número en su interior? Bueno, usted tiene seis los números en estas cajas. ¿Cuáles serían sus instintos? ¿Dónde te gustaría ponerlo? 

AUDIENCIA: [inaudible] 

DAVID J. MALAN: Lo siento? 

AUDIENCIA: Ponlo en el final. 

DAVID J. MALAN: Ponlo en el extremo. Así que un poco más a la derecha, fuera de esta caja de texto. ¿Qué estaría bien, pero resulta que no puede hacer eso. Porque si no lo has pedido para esta parte de la memoria, podría ser por casualidad que esta está siendo utilizado por alguna otra variable por completo. Piense de nuevo una semana o así que cuando nos acostamos los nombres Zamyla y Davin y Gabe de en la memoria. Eran, literalmente, espalda con espalda con espalda. Así que no podemos necesariamente confiar en que cualesquiera de aquí está disponible para que yo use. 

Entonces, ¿qué otra cosa podría hacer? Bueno, una vez que darse cuenta de que necesitará una matriz de tamaño siete, usted podría crear un matriz de tamaño siete después utilice un bucle for o un bucle while, copiarlo en la nueva matriz, y entonces de alguna manera simplemente deshacerse de esta matriz o simplemente deje de usarlo. Pero eso no es particularmente eficiente. En resumen, las matrices no dejan cambiar el tamaño de forma dinámica. 

Así que por un lado se obtiene acceso aleatorio, que es increíble. Debido a que nos permite hacer cosas como divide y vencerás, búsqueda binaria, todo lo cual hemos hablado en la pantalla aquí. Pero se pinta a sí mismo en una esquina. Tan pronto como se golpeó Al final de su matriz, usted tiene que hacer un muy operación costosa o escribir un montón de código que lidiar ahora con ese problema. 

¿Y qué si su lugar, teníamos algo que se llama una lista, o una lista vinculada en particular? ¿Qué pasa si en lugar de tener rectángulos espalda con espalda con espalda, tenemos rectángulos que dejan un poco poco de margen de maniobra en medio de ellos? Y a pesar de que he dibujado este foto o adaptado esta foto de uno de los textos aquí para estar de nuevo a espalda con espalda muy ordenada, en la realidad, uno de esos rectángulos podría ser de hasta aquí en la memoria. Uno de ellos podría estar aquí. Uno de ellos podría estar aquí arriba, aquí, y así sucesivamente. 

Pero lo que si dibujamos, en este caso, las flechas que de alguna manera vincularlos rectángulos juntos? De hecho, hemos visto una técnica encarnación de una flecha. ¿Qué hemos utilizado en los últimos día que, debajo de la campana, es representativa de una flecha? Un puntero, ¿verdad? 

¿Y qué si, en lugar de almacenar sólo los números, como 9, 17, 22, 26, 34, ¿y si no almacenamos sólo un número, pero un puntero junto a cada uno de tales número? Así que al igual que se enhebrar una aguja a través de un manojo entero de la tela, cosas de alguna forma de vinculación juntos, de manera similar puede que con los punteros, como encarnado por flechas aquí, tipo de tejer estos rectángulos individuales por la utilización eficaz de un puntero uno al lado del número que apunta a algunos siguiente número, que señala, a su vez, algunos siguiente número? Así que en otras palabras, lo que si en realidad queríamos para implementar algo como esto? Bien por desgracia, estos rectángulos, al menos el uno con 9, 17, 22, y así sucesivamente, estos ya no son bonitas plazas con números individuales. La parte inferior, rectángulo por debajo de 9, por ejemplo, representa lo que debe ser un puntero, 32 bits. Ahora, todavía no estoy al tanto de cualquier tipo de datos en C que le da no sólo un int pero un puntero por completo. 

Entonces, ¿cuál es la solución si queremos inventar nuestra propia respuesta a esto? ¿Sí? 

AUDIENCIA: [inaudible] 

DAVID J. MALAN: ¿Qué es eso? 

AUDIENCIA: Nueva estructura. 

DAVID J. MALAN: Sí, ¿y por qué Por qué no creamos una nueva estructura, o en C, una estructura? Hemos visto estructuras antes, aunque brevemente, donde nos topamos con una estructura estudiante como éste, que tenía un nombre y una casa. En Pset 3 breakout usted utiliza en su conjunto manojo de GRect structs-- y GOvals que Stanford creado para información de clúster juntos. ¿Y qué si tomamos esta misma idea de las palabras clave "typedef" y "struct" y luego un poco de materia específica del estudiante, y evolucionar esto en lo siguiente: typedef struct node-- y nodo es sólo una ciencia de la computación muy genérico plazo para algo en una estructura de datos, un contenedor en una estructura de datos. Un nodo reclamo va a tener un int n, totalmente sencillo, y luego un poco más críptica, esta segunda línea, el nodo struct * siguiente. Pero en términos menos técnicos, lo que es que la segunda línea de código dentro de las llaves? ¿Sí? 

AUDIENCIA: [inaudible] DAVID J. MALAN: Un puntero a otro nodo. Así que sin duda, la sintaxis un poco críptico. Pero si usted lee literalmente, siguiente es el nombre de una variable. ¿Cuál es su tipo de datos? Es un poco verboso este momento, pero es de tipo struct nodo *. Cada vez que hemos visto algo de la estrella, que significa que es un puntero a ese tipo de datos. Así que la próxima es al parecer un puntero a un nodo de estructura. 

Ahora, ¿qué es un nodo de estructura? Bueno, observa que vea los mismas palabras en la parte superior derecha. Y, en efecto, se ve también la palabra "Nodo" aquí abajo en la parte inferior izquierda. Y esto es en realidad sólo una conveniencia. Tenga en cuenta que en nuestra definición estudiante ahí está la palabra "estudiante" sólo una vez. Y es que un estudiante objeto no era auto-referencial. No hay nada en el interior de un estudiante que tiene que apuntar a otro estudiante, persay. Eso sería una especie de raro en el mundo real. 

Pero con un nodo en una ligado lista, sí queremos un nodo ser referencial a un objeto similar. Y así cuenta del cambio aquí no es sólo lo que está dentro de las llaves. Pero añadimos la palabra "nodo" en la parte superior, así como de añadir a la parte inferior en lugar de "estudiante". Y esto es sólo un detalle técnico de modo que, de nuevo, la estructura de datos puede ser auto-referencial, por lo que un nodo puede apuntar a otra tal nodo. 

Entonces, ¿qué es esta última instancia va a significar para nosotros? Bueno, uno, esto dentro es el contenido de nuestro nodo. Esta cosa aquí, arriba a la derecha, es tan que, de nuevo, podemos referirnos a nosotros mismos. Y luego las cosas más externa, a pesar de que el nodo es un nuevo término, tal vez, que sigue siendo el mismo que los estudiantes y lo que estaba debajo de la capucha en SPL. 

Así que si ahora queríamos empezar la aplicación de esta lista enlazada, ¿cómo podríamos traducir algo como esto para codificar? Bueno, vamos a ver un ejemplo de un programa que en realidad utiliza una lista enlazada. Entre código de distribución de hoy es un programa que se llama Lista Cero. Y si me quedo esta creé un super GUI simple, interfaz gráfica de usuario, pero no deja de ser printf. Y ahora yo mismo he dado unos cuantos menú options-- Eliminar, Insertar, Buscar, y Traverse. Y en Salir. Estas son operaciones comunes en un solo estructura de datos conocida como una lista de enlaces. 

Ahora, Eliminar va a eliminar un número de la lista. Inserte va a añadir un número a la lista. La búsqueda se va a ver de número en la lista. Y travesía es sólo una forma elegante de decir, caminar a través de la lista, imprimirlo, pero eso es todo. No cambie de ninguna manera. 

Así que vamos a probar esto. Vamos a seguir adelante y tipo 2. Y luego voy a insertar el número, por ejemplo 9. Intro. Y ahora mi programa es sólo programada decir, la lista es ahora 9. Ahora, si me voy por delante y no Inserte de nuevo, dejar que me voy por delante y alejar y escribo en 17. Ahora mi lista es 9, entonces de 17 años. Si lo hago inserte de nuevo, vamos a saltar uno. En lugar de 22, de acuerdo con la imagen que hemos estado viendo aquí, déjame ir por delante e inserte el 26 próximo. Así que voy a escribir 26. La lista es la que espero. Pero ahora, sólo para ver si el código va a ser flexible, dejadme que ahora tipo 22, que al menos conceptualmente, si estamos Teniendo esto ordenadas, que es de hecho va a ser otro de los objetivos en este momento, debe ir en entre el 17 y el 26. Así que pulsé Enter. De hecho, eso funciona. Y ahora permítanme insertar el pasado, por la imagen, 34. 

Bien. Así que por ahora déjame estipulo que Borrar y Traverse y Search hacen, de hecho, trabajar. De hecho, si yo corro búsqueda, vamos a buscar el número 22, Enter. Se encontraron 22. Así que eso es lo que esta programa de lista Zero hace. 

Pero lo que realmente está pasando en que implementa esto? Bueno, primero voy a tener, y de hecho Yo tengo, un archivo llamado list0.h. Y en algún lugar existe este línea, typedef, struct nodo, entonces tengo mis llaves, int n, y entonces struct-- cuál es la definición? Struct nodo siguiente. Así que tenemos la estrella. Ahora técnicamente nos metemos en el hábito de dibujar aquí. Es posible que vea los libros de texto y referencias en línea lo hacen allí. Es funcionalmente equivalente. De hecho, este es un poco más típico. Pero voy a ser coherente con lo que que hicimos la última vez y hacemos esto. Y luego, por último, voy a hacer esto. 

Así que en un archivo de cabecera en algún lugar, en list0.h hoy es esta definición struct, y tal vez algunas otras cosas. Mientras tanto, en list0c hay va a ser un par de cosas. Pero vamos a simplemente iniciar y no terminar esto. List0.h es un archivo que quiero incluir en mi archivo C. Y luego, en algún momento me estoy va a tener int, principal, anulará. Y luego voy a tienen algunas cosas por hacer está aquí. Yo también voy a tener una prototipo, como vacío, búsqueda, int, n, cuyo propósito en la vida es para buscar un elemento. Y entonces aquí yo reclamo en el código de hoy, nula búsqueda, int, n, hay punto y coma, pero las llaves abiertas. Y ahora quiero buscar alguna manera un elemento en esta lista. Pero nosotros no tenemos suficiente información en la pantalla todavía. No tengo en realidad representada la propia lista. Así que una manera que podríamos aplicar una lista enlazada en un programa está como que quiero hacer algo como declaran lista enlazada aquí. Para simplificar, voy a hacer este mundial, a pesar de que en general, nos No debería hacer esto demasiado. Pero va a simplificar este ejemplo. Así que quiero declarar una lista enlazada aquí. Ahora, ¿cómo podría yo hacer eso? 

Aquí está la foto de una lista enlazada. Y realmente no me conocer al momento cómo Voy a ir sobre lo que representa tantas cosas con un solo variable en la memoria. Pero pensar de nuevo un momento. Durante todo este tiempo que hemos tenido cuerdas, que luego revelado a ser matrices de personajes, que luego revelado a ser sólo un puntero hasta el primer carácter en una matriz de caracteres eso está terminada en nulo. Así que por esa lógica, y con este foto tipo de sembrar sus pensamientos, lo que necesitamos realmente escribimos en nuestra código para representar una lista enlazada? ¿Qué parte de esta información necesitamos capturar en código C, qué le dirías? ¿Sí? 

AUDIENCIA: Necesitamos un puntero a un nodo. DAVID J. MALAN: Un puntero a un nodo. En particular, lo que haría con su nodo instintos ser mantener un puntero? 

AUDIENCIA: El primer nodo. 

DAVID J. MALAN: Sí, probablemente sólo la primera. Y note, la primera nodo es una forma diferente. Es sólo la mitad del tamaño de la estructura, porque es de hecho sólo un puntero. Así que lo que realmente puede hacer es declarar una lista enlazada sea de nodo de tipo *. Y vamos a llamarlo primero y inicializarlo a null. Así nula, de nuevo, es procedente en la imagen aquí. No sólo se utiliza null como como un especial valor de retorno para cosas como getString y malloc, null es también el cero puntero, la falta de un puntero, si se quiere. Sólo significa que aún no hay nada aquí. Ahora en primer lugar, que hubiera podido llamado a este nada. Yo podría haber llamado "lista" o cualquier número de otras cosas. Pero yo estoy llamando "primero" para que líneas arriba con esta imagen. Así que al igual que una cadena se puede representar con la dirección de su primer byte, por lo que puede una lista enlazada. Y veremos otros datos pueden representar estructuras con sólo un puntero, una flecha de 32 bits, señalando en el primer nodo de la estructura. 

Pero ahora vamos a anticipar un problema. Si yo sólo estoy recordando en mi programa de la dirección del primer nodo, la primera rectángulo en esta estructura de datos, lo que tenía ser mejor el caso sobre el ejecución del resto de mi lista? ¿Qué es un detalle clave que está pasando para asegurar que esto funciona en realidad? Y por "realmente funciona" I decir, como un string, nos deja ir desde el primer carácter en el nombre de Davin a la segunda, a la tercera, a la cuarto, hasta el final, ¿Cómo sabemos cuando estamos al final de una lista enlazada que tiene este aspecto? Cuando es nulo. Y yo he representado este tipo de como como una fuerza ingeniero eléctrico, con la poca tierra símbolo, de todo tipo. Pero eso sólo significa nula en este caso. Usted puede dibujar cualquier número maneras, pero este autor pasado a utilizar este símbolo aquí. 

Mientras estamos encadenando todos estos nodos entre sí, sólo recordar dónde la primera es, siempre como ponemos un símbolo especial en el último nodo de la lista, y usaremos nulo, porque eso es lo que tenemos a nuestra disposición, esta lista es completa. Y aunque yo sólo le dan un puntero a el primer elemento, usted, el programador, sin duda puede acceder al resto de la misma. Pero vamos a dejar que sus mentes pasear un poco, si no lo son ya bastante wandered-- lo que es va a ser el tiempo de ejecución de encontrar nada en esta lista? Maldita sea, es grande O de n, lo cual no es malo, para ser justos. Pero es lineal. Hemos renunciado a lo que característica de arrays moviendo más hacia la imagen de forma dinámica entrelazados o nodos vinculados? Hemos renunciado acceso aleatorio. Una matriz es agradable porque todo matemáticamente ha vuelto a la espalda con espalda con espalda. A pesar de que esta foto se ve bastante, e incluso aunque parece que estos nodos están bien separados, en realidad podrían estar en cualquier parte. Ox1, OX50, Ox123, Ox99, éstos nodos podrían estar en cualquier parte. Debido a malloc hace asignar memoria del montón, pero en cualquier lugar en el montón. Usted no necesariamente sabe que es va a estar espalda con espalda con espalda. Y así esta foto en la realidad de No va a ser bastante esta bonita. 

Así que va a tomar un poco de trabajar para implementar esta función. Así que vamos a poner en práctica la búsqueda ahora. Y vamos a ver una especie de forma inteligente de hacerlo. Así que si yo soy una función de búsqueda y Me dan una variable, entero n a buscar, necesito saber la nueva sintaxis para mirar dentro de una estructura que es señalado, para encontrar n. Así que vamos a hacer esto. 

Así que primero voy a ir adelante y declarar un nodo *. Y yo voy a llamarlo puntero, sólo por convención. Y yo voy a inicializarlo a primera. Y ahora que puedo hacer esto en un número de maneras. Pero me voy a tomar un enfoque común. Mientras puntero no es igual a nula, y eso es una sintaxis válida. Y sólo significa hacer lo siguiente, por lo que siempre y cuando usted no está apuntando a la nada. ¿Qué quiero hacer? 

Si dot puntero n, dejarme volver para que, equals-- igual qué? ¿Qué valor que estoy buscando? El n real que se pasó. Así que aquí está otra de las características de C y muchos idiomas. A pesar de que el nodo de estructura llamada tiene un valor de n, totalmente legítimo tener también un argumento locales o variable llamada n. Porque nosotros también, con los ojos humanos, pueden distinguir que este n es presumiblemente diferente de este n. Debido a que la sintaxis es diferente. Tienes un punto y un puntero, mientras que éste no tiene tal cosa. Así que esto está bien. Eso está bien llamarlos las mismas cosas. 

Si yo te encuentro esto, estoy va a querer hacer algo como anunciamos que nos encontramos n. Y eso se lo dejamos como comentar o código pseudocódigo. Si no, y aquí está la Lo interesante, lo que hago lo que quiero hacer si el nodo actual no se contiene n que me importa? ¿Cómo puedo lograr lo siguiente? Si mi dedo en el momento es PTR, y es que apunta a lo que sea primero está apuntando a, ¿cómo puedo mover mi dedo al siguiente nodo en el código? Bueno, ¿cuál es la ruta de navegación que estamos va a seguir en este caso? AUDIENCIA: [inaudible]. DAVID J. MALAN: Sí, así que la próxima. Así que si vuelvo a mi código aquí, de hecho, estoy va a seguir adelante y decir puntero, que es sólo una variable-- temporal es un nombre raro, ptr, pero es como temp-- Voy a establecer puntero igual a lo que sea puntero es-- y de nuevo, esto va a ser un de errores, para insertar un punto moment-- siguiente. En otras palabras, me voy a tomar mi dedo que está señalando a este nodo aquí y yo voy a decir, ya sabes qué, eche un vistazo a el siguiente campo y mover el dedo para como sea que se señala en. Y esto va a repetir, repetir, repetir. Pero cuando lo hace mi dedo dejar de hacer nada en absoluto? Tan pronto como qué línea de código en patadas? AUDIENCIA: [inaudible] DAVID J. MALAN: Si el punto mientras puntero no es igual a null. En algún momento de mi dedo de va a estar apuntando a nula y yo voy a realizar ese es el final de esta lista. Ahora, esto es un poco mentira piadosa para la simplicidad. Resulta que a pesar de que acaba de enterar esta notación de puntos para estructuras, puntero no es una estructura. ptr es qué? Sólo para ser más quisquillosa. Es un puntero a un nodo. No es un nodo en sí. Si no tuviera la estrella aquí, puntero absolutely-- es un nodo. Esto es como una semana declaración de una variable, a pesar de que la palabra "nodo" es nueva. 

Pero tan pronto como se introduce un estrella, ahora es un puntero a un nodo. Y, por desgracia no se puede utilizar la notación de puntos para un puntero. Usted tiene que usar la flecha notación, que, sorprendentemente, es la primera vez que un pedazo de sintaxis parece intuitivo. Esto se ve, literalmente, como una flecha. Y eso es una buena cosa. Y aquí abajo, literalmente, se parece a una flecha. Así que creo que esa es la la-- no lo hago Creo que estoy demasiado cometer aquí-- I Creo que es la última pieza nueva de la sintaxis que vamos a ver. Y por suerte, es de hecho un poco más intuitivo. 

Ahora, para aquellos de ustedes que podrían preferir la manera antigua, aún puede utilizar la notación de puntos. Pero según Lunes de conversación, primero que tenga que ir allí, ir a ese abordar, y luego acceder al campo. Así que esto también es correcto. Y, francamente, este es un poco más pedante. Usted está literalmente diciendo desreferenciar el puntero e ir allí. Entonces agarra .n, el campo llamado n. Pero, francamente, nadie quiere para escribir o leer esto. Y así el mundo inventó la notación flecha, que es equivalente, idéntico, es sólo el azúcar sintáctica. Así que una forma elegante de decir esto se ve mejor, o se ve más simple. 

Así que ahora me voy a hacer otra cosa. Voy a decir "break" Una vez que he encontró, así que no la guardo en busca de ella. Pero esta es la esencia de una función de búsqueda. Pero es mucho más fácil, en el final, no caminar a través del código. Esta es de hecho la aplicación formal de búsqueda de código de distribución actual. Me atrevo a decir que la inserción no es particularmente divertido caminar por visualmente, ni tampoco eliminar, incluso aunque al final del día se reducen a bastante heurísticas simples. 

Así que vamos a hacer esto. Si Usted humor conmigo aquí, lo hice traer un montón de bolas de estrés. Me trajo un montón de números. Y podríamos conseguir unos pocos voluntarios para representar 9, 17, 20, 22, 29, y 34? Así que, esencialmente todo el mundo quien está aquí hoy. Ese fue uno, dos, tres, cuatro, cinco, seis personas. Y me han pedido que ir-- ver, no una en la parte posterior levanta sus manos. Bueno, uno, dos, tres, cuatro, cinco-- déjame cargar balance-- seis. OK, vamos hasta seis. Necesitaremos otras personas. Trajimos bolas de estrés adicionales. Y si pudiera, para un momento, la línea ustedes justo te gusta esta foto aquí. 

Bien. Vamos a ver, ¿cómo te llamas? 

AUDIENCIA: Andrew. 

DAVID J. MALAN: Andrew, eres el número 9. Encantada de conocerte. Aquí tienes. AUDIENCIA: Jen. DAVID J. MALAN: Jen. David. Número 17. Sí? 

AUDIENCIA: Soy Julia. 

DAVID J. MALAN: Julia, David. Número 20. AUDIENCIA: Cristiano. DAVID J. MALAN: Cristiano, David. Número 22. Y? 

AUDIENCIA: JP. DAVID J. MALAN: JP. Número 29. Así que adelante y obtener en-- Uh oh. Uh oh. Standby. 20. ¿Alguien tiene un marcador? AUDIENCIA: Tengo un Sharpie. DAVID J. MALAN: ¿Tienes un Sharpie? Okay. Y ¿alguien tiene un pedazo de papel? Guarde la conferencia. Venga. AUDIENCIA: lo tenemos. DAVID J. MALAN: lo conseguimos? Muy bien, gracias. Aquí vamos. ¿Era esto de ti? Acabas de salvar el día. Así 29. Bien. Lo escribo mal el 29, pero no está mal. Seguir adelante. Muy bien, te voy a dar su pluma hacia atrás momentáneamente. Así que tenemos a esta gente aquí. Vamos a tener otro. Gabe, ¿quieres jugar el primer elemento en esta lista? Te necesitamos para que apunte a esta buena gente. Así que 9, 17, 20, 22, especie de 29, y luego 34. ¿Perdimos a alguien? Tengo un 34. Dónde hizo-- bien, que quiere ser 34? Bien, vamos hacia arriba, 34. Muy bien, esto será bien vale la pena el clímax. Cuál es tu nombre? 

AUDIENCIA: Peter. 

DAVID J. MALAN: Peter, vamos arriba. Muy bien, así que aquí tiene un todo grupo de nodos. Cada uno de ustedes representa uno de estos rectángulos. Y Gabe, el poco extraño al hombre, representa en primer lugar. Así que su puntero es un poco más pequeño en la pantalla de todos los demás. Y en este caso, cada uno de su izquierda manos va a apuntar hacia abajo o bien, lo cual representa una nula, por lo que sólo la ausencia de un puntero, o que va a estar apuntando en un nodo al lado de usted. 

Así que ahora mismo, si adornas ustedes como la imagen aquí, seguir adelante y punto el uno al otro, con Gabe en particular, apuntando a número 9 para representar la lista. Aceptar, y el número 34, la mano izquierda sólo deben estar apuntando hacia el suelo. 

Aceptar, por lo que esta es la lista enlazada. Así que este es el escenario en cuestión. Y, de hecho, esto es representativo de una clase de problemas que usted puede tratar de resolver con el código. Usted quiere insertar en última instancia un nuevo elemento en la lista. En este caso, vamos a tratar de insertar el número 55. Pero no va a ser diferentes casos a considerar. Y, de hecho, esto va a ser una de la gran imagen comida para llevar aquí, es, ¿cuáles son los diferentes casos. ¿Cuáles son los diferentes si las condiciones o ramas que su programa podría tener? 

Bueno, el número al que está tratando de inserción, que ahora sabemos que ser 55, pero si usted no lo sabía de antemano, me atrevo a decir cae en al menos tres posibles situaciones. ¿Dónde podría ser un nuevo elemento? AUDIENCIA: Y al final o en medio. DAVID J. MALAN: Al final, en el medio, o al principio. Así que yo reclamo que hay al menos tres problemas que tienen que resolver. Vamos a elegir lo que es tal vez posiblemente el más simple uno, cuando el elemento nuevo pertenece al principio. Así que voy a tener bastante código como la búsqueda, que sólo escribí. Y yo voy a tener ptr, que Voy represento aquí con mi dedo, como siempre. 

Y recuerda, ¿qué valor hicimos inicializamos ptr a? Así que hemos inicializado en null inicialmente. Pero entonces ¿qué hicimos una vez que estaban dentro de nuestra función de búsqueda? La fijamos igual al primero, lo que no significa hacer esto. Si fijo ptr igual al primero, lo que debe ser realmente mi mano apuntando a? Derecha. Así que si Gabe y yo vamos ser valores iguales aquí, necesitamos tanto el punto en el número 9. 

Así que este fue el comienzo de nuestra historia. Y ahora esto es sólo sencillo, a pesar de que la sintaxis es nueva. Conceptualmente esto es sólo búsqueda lineal. Is 55, igual a 9? O más bien, digamos menos de 9. Porque yo estoy tratando de averiguar dónde poner 55. Menos de 9, a menos de 17, menos de 20, menos de 22, menos de 29, menos de 34, no. Así que ahora estamos en el caso uno de al menos tres. 

Si quiero insertar 55 por aquí, lo que líneas de necesidad código se ejecutan? ¿Cómo funciona este cuadro de los seres humanos tienen que cambiar? ¿Qué hago con mi mano izquierda? Esto debería ser nula inicialmente, porque estoy en el final de la lista. Y lo que debería ocurrir aquí con Peter, ¿verdad? Él, obviamente, va a apuntar a mí. Así que yo reclamo que hay al menos dos líneas de código en el código de ejemplo a partir de hoy eso va a implementar este escenario de la adición de 55 en la cola. Y podría tener a alguien hop y sólo representan el 55? Muy bien, usted es el nuevo 55. 

Así que ahora lo que si el próximo escenario se presenta, y queremos insertar en el comenzando o la cabeza de esta lista? ¿Y cuál es su nombre, el número 55? 

AUDIENCIA: Jack. 

DAVID J. MALAN: Jack? Bueno, encantado de conocerte. Bienvenido a bordo. Así que ahora vamos a insertar, por ejemplo, el número 5. Aquí está el segundo caso de la tres se nos ocurrió antes. Así que si 5 pertenece al principio, vamos a ver cómo nos encontramos con que fuera. Puedo inicializar mi ptr puntero a número 9 de nuevo. Y me di cuenta, oh, 5 es menor que 9. Así que arreglar esta imagen para nosotros. ¿Qué manos, Gabe o David de o-- ¿cómo se llama el número del 9? 

AUDIENCIA: Jen. 

DAVID J. MALAN: manos-- de Jen cuál de nuestras manos que tenga que cambiar? OK, así que Gabe señala en qué ahora? En mí. Yo soy el nuevo nodo. Así que voy a clase de movimiento aquí para verlo visualmente. Y mientras tanto, ¿qué debo señalar que? Aún donde estoy apuntando. Así que es eso. Así que en realidad una línea de arreglos de código este tema en particular, lo que parece. Muy bien, así que eso es bueno. Y alguien puede ser un marcador de posición para el 5? Vamos arriba. Te llevaremos la próxima vez. 

Muy bien, así que ahora-- y Como acotación al margen, los nombres No voy a hacer mención explícita del derecho Ahora, pred puntero, puntero predecesor y nuevo puntero, que es sólo los nombres dado en el código de ejemplo a los punteros o mis manos, que es una especie de apuntando alrededor. Cuál es tu nombre? 

AUDIENCIA: Christine. 

DAVID J. MALAN: Christine. Bienvenido a bordo. Muy bien, así que vamos a considerar ahora un escenario ligeramente más molesto, por el que quiero insertar algo así como 26 en esto. 20? ¿Qué? Estos son-- buena cosa que tenemos esta pluma. Muy bien, 20. Si alguien puede conseguir otra pieza de papel listo, por si caso-- bien. Oh, interesante. Bueno, esto es un ejemplo de un error de conferencias. Aceptar ¿cuál es tu nombre? AUDIENCIA: Julia. DAVID J. MALAN: Julia, ¿puede estallar y pretender que nunca estuvieron ahí? OK, esto nunca sucedió. Gracias. Así que supongamos que queremos insertar Julia en esta lista enlazada. Ella es la número 20. Y, por supuesto, ella es va a pertenecer al begin-- no apunte a nada todavía. Así que tu mano puede ser tipo de abajo nulo o algún valor basura. Digamos la historia rápida. Estoy señalando en el número 5 de este tiempo. Entonces compruebo 9. Luego reviso 17. Luego reviso 22. Y me doy cuenta, ooh, Julia tiene que ir antes de los 22. Entonces, ¿qué tiene que suceder? ¿Qué manos tienen que cambiar? Julia, la mía, o-- ¿cuál es tu nombre? 

AUDIENCIA: Cristiano. 

DAVID J. MALAN: Cristiano o? 

AUDIENCIA: Andy. 

DAVID J. MALAN: Andy. Cristiano o Andy? Andy tiene que apuntar a? Julia. Bien. Así que Andy, qué quieres apuntar a Julia? Pero espere un minuto. En la historia hasta el momento, Yo soy el tipo de uno a cargo, en el sentido de que puntero es la cosa que es moviéndose a través de la lista. Puede ser que tengamos un nombre para Andy, pero no hay variable llamada Andy. La única otra variable que tenemos es en primer lugar, que está representado por Gabe. 

Así que esto es en realidad la razón por lo tanto Hasta aquí no hemos necesitado esto. Pero ahora en la pantalla no es mencionar de nuevo de puntero pred. Así que permítanme ser más explícito. Si esta es puntero, tuve una mejor ser un poco más inteligente sobre mi iteración. Si no te importa mi pasar por aquí de nuevo, señalando aquí, señalando aquí. Pero déjame tener un puntero pred, puntero predecesor, que es especie de que apunta a la elemento que estaba justo en. Así que cuando voy aquí, ahora mis actualizaciones mano izquierda. Cuando voy allí a mis actualizaciones de la mano izquierda. Y ahora tengo no sólo un puntero a el elemento que va detrás de Julia, Todavía tengo un puntero a Andy, el elemento antes. Así que usted tiene acceso, en esencia, pan rallado, si se quiere, a todos los punteros necesarios. 

Así que si yo estoy apuntando a Andy y yo también estoy apuntando en cristiano, cuyas manos ahora debe ser señalado en otro lugar? Así que Andy ahora puede apuntar a Julia. Julia ahora puede apuntar a Cristiano. Porque ella puede copiar mi puntero de la mano derecha. Y eso te pone con eficacia de nuevo en este lugar aquí. Así que en resumen, a pesar de que esta nos está tomando clase de siempre para actualizar en realidad un lista enlazada, se dan cuenta que las operaciones son relativamente simples. Es de uno, dos, tres líneas de código en última instancia. Pero envuelto alrededor de los líneas de código, presumiblemente, es que efectivamente un poco de lógica hace la pregunta, ¿dónde estamos? ¿Estamos en el comienzo, el medio, o al final? 

Ahora, sin duda hay alguna otra operaciones que podríamos poner en práctica. Y estas fotos aquí sólo representan lo que acabamos de hacer con los seres humanos. ¿Qué pasa con la eliminación? Si quiero, por ejemplo, quitar el número 34 o 55, Puede que tenga el mismo tipo de código, pero voy a necesitar uno o dos pasos. Porque lo que hay de nuevo? Si elimino a alguien al final, como el número 55 y luego 34, lo que también tiene que cambiar como yo que? Tengo que no evict-- ¿cuál es tu nombre? 

AUDIENCIA: Jack. 

DAVID J. MALAN: Jack. Tengo que no sólo evict-- libre Jack, tan literalmente llamar gratis Jack, o al menos el puntero allí también, pero ahora lo que hay que cambiar con Peter? Su mano mejor comienzo que apunta hacia abajo. Porque tan pronto como yo lo llamo gratuito Jack, si sigue apuntando de Pedro en Jack y por lo tanto sigo recorriendo la lista y el acceso este puntero, que es cuando nuestro amigo segmentación de edad criticar realidad podría poner en. Porque nos hemos dado la volver la memoria a Jack. 

Puede permanecer allí torpemente por un momento. Porque tenemos sólo un par operaciones finales a tener en cuenta. Extracción de la cabeza de la lista, o la principio-- y éste de un poco molesto. Porque tenemos que saber que Gabe es una especie de especial en este programa. Porque de hecho, él tiene su propio puntero. Él simplemente no está siendo señaló, como casi todos los demás aquí. 

Así que cuando la cabeza de la lista es eliminado, cuyas manos que tenga que cambiar ahora? ¿Cuál es tu nombre? 

AUDIENCIA: Christine. 

DAVID J. MALAN: Soy horrible en nombres, al parecer. Así Christine y Gabe, cuyas manos necesite cambiar cuando tratamos de eliminar Christine, número 5, de la foto? OK, así que vamos a hacerlo Gabe. Gabe va a apuntar, presumiblemente, en el número 9. Pero lo siguiente que debería ocurrir? AUDIENCIA: Christine debe ser nulo [inaudible]. DAVID J. MALAN: OK, probablemente deberíamos make-- oí "nulo" en algún lugar. AUDIENCIA: Null y liberarla. DAVID J. MALAN: null qué? AUDIENCIA: Null y liberarla. DAVID J. MALAN: Null y liberarla. Así que esto es muy fácil. Y es perfecto que ahora eres una especie de pie allí, que no pertenece. Porque has sido desacoplado de la lista. Has sido efectivamente huérfanos de la lista. Y así nos habíamos mejor llamar gratis ahora Christine de dar ese memoria. De lo contrario, cada vez que eliminar un nodo de la lista que podríamos estar haciendo la lista más corto, pero en realidad no disminuyendo el tamaño en memoria. Y por lo que si estamos añadiendo y añadiendo, añadiendo cosas a la lista, mi equipo podría conseguir más lento y más y más lento, porque me estoy quedando sin memoria, incluso si no estoy realmente usando bytes de Christine de la memoria más. 

Así que al final hay otra escenarios, de la eliminación supuesto-- en el medio, la eliminación al final, como hemos visto. Pero el más interesante reto ahora es va a ser considerar exactamente lo que el tiempo de ejecución es. Así que no sólo se puede mantener un trozos de papel, si, Gabe, que no le importaría dar todos una bola de la tensión. Muchas gracias a nuestra lista enlazada de voluntarios aquí, si pudiera. 

[Aplausos] 

DAVID J. MALAN: Muy bien. Así que un par de analítica preguntas luego, si pudiera. Hemos visto esta notación antes, gran O y omega, límites superiores y cotas inferiores de la tiempo de algún algoritmo se ejecuta. Así que vamos a considerar sólo un par de preguntas. 

Uno, y lo dijimos antes, lo que es la gestión tiempo de búsqueda de un lista en términos de gran O? ¿Qué es un límite superior en el funcionamiento tiempo de búsqueda una lista enlazada tal como se aplica por nuestros voluntarios aquí? Es grande O de n, lineal. Debido a que en el peor de los casos, el elemento, como 55, podríamos estar buscando podríamos estar donde Jack era, todo el camino al final. Y, por desgracia, a diferencia de una matriz no podemos conseguir la suposición este momento. A pesar de todos nuestros seres humanos eran ordenados de elementos pequeños, 5, todo el camino hasta el elemento más grande, 55, que suele ser una buena cosa. ¿Pero qué tiene esa suposición ya no nos permite hacer? AUDIENCIA: [inaudible] DAVID J. MALAN: Diga otra vez? AUDIENCIA: Acceso aleatorio. DAVID J. MALAN: Acceso aleatorio. Y a su vez, eso significa que puede no ya utilizar ceros débil, la intuición, y la evidencia de la utilización de binario buscar y dividir y conquistar. Porque a pesar de que los seres humanos podían obviamente ver que Andy o cristiano fueron más o menos en el medio de la lista, sólo sabemos que como ordenador con una lectura rápida de la lista desde el principio. Así que nos hemos dado hasta que el acceso aleatorio. 

Así que gran O de n ahora es el superior con destino en nuestro tiempo de búsqueda. ¿Qué pasa con el omega de nuestra búsqueda? ¿Cuál es el límite inferior en la búsqueda para algún número en esta lista? AUDIENCIA: [inaudible] DAVID J. MALAN: Diga otra vez? AUDIENCIA: Una. DAVID J. MALAN: Una. Así que el tiempo constante. En el mejor de los casos, Christine es de hecho, al principio de la lista. Y estamos buscando número 5, por lo que la encontró. Así que no es gran cosa. Pero ella tiene que estar en el a partir de la lista en este caso. ¿Qué tal algo como ¿Eliminar? ¿Qué pasa si usted quiere eliminar un elemento? ¿Cuál es el límite superior y el límite inferior sobre la eliminación de algo de un vinculado enumerar? AUDIENCIA: [inaudible] DAVID J. MALAN: Diga otra vez? AUDIENCIA: n. DAVID J. MALAN: n es de hecho, el límite superior. Debido a que en el peor de los casos que tratamos eliminar Jack, como nosotros lo hicimos. Él es todo el camino al final. Nos lleva para siempre, o n pasos para encontrarlo. Así que eso es un límite superior. Eso es lineal, seguro. Y el tiempo el mejor de los casos en ejecución, o los límites inferiores en el mejor de los casos sería constante de tiempo. Porque tal vez tratamos de eliminar Christine, y acabamos de tener suerte ella está en el comienzo. Espera un minuto. Gabe también era en el principio, y también tuvimos que actualizar Gabe. Así que no era sólo un paso. Por lo que es de hecho constante tiempo, en el mejor de los casos, para eliminar el elemento más pequeño? Es, a pesar de que podría ser dos, tres, o incluso 100 líneas de código, si es el mismo número de líneas, no en un bucle, e independiente del tamaño de la lista, por supuesto. Eliminar el elemento en el principio de la lista, incluso si tenemos que hacer frente a Gabe, todavía estamos a tiempo constante. 

Así que esto parece una enorme paso hacia atrás. Y lo que una pérdida de tiempo si, en la primera semana y la semana cero no sólo tuvimos código pseudocódigo pero el código real para poner en práctica algo que es registro base de n, o ingrese, más bien, de n, base 2, en cuanto a su tiempo de ejecución. Así que ¿por qué diablos tendría que desee comenzar usando algo como una lista enlazada? Sí. 

AUDIENCIA: Así que usted puede añadir elementos a la matriz. DAVID J. MALAN: Así que usted puede añadir elementos a la matriz. Y esto también es temático. Y vamos a seguir para ver esto, esta compensación, mucho como hemos visto un trade-off con merge sort. Realmente podríamos acelerar buscar u ordenar, más bien, si nos pasamos un poco más de espacio y tener un trozo adicional de una memoria o una matriz de tipo de combinación. Pero gastamos más espacio, pero nos ahorramos tiempo. En este caso, estamos renunciar a tiempo, pero estamos ganar flexibilidad, dinamismo si se quiere, que es sin duda una característica positiva. 

También nos estamos gastando el espacio. ¿En qué sentido es un ligado enumerar más caro en términos de espacio de una matriz? ¿Dónde está el espacio extra viene? ¿Sí? 

AUDIENCIA: [inaudible] puntero. 

DAVID J. MALAN: Sí, también tienen el puntero. Así que esto es molesto minorly en que ya no soy Yo almacenar sólo un int para representar un int. Estoy almacenando un int y un puntero, que también es de 32 bits. Así que estoy literalmente duplicar la cantidad de espacio involucrado. Así que eso es un trade-off, pero eso es en el caso de int. Supongamos que usted no está almacenando int, pero supongamos que cada uno de estos rectángulos o cada uno de estos seres humanos representaba a una palabra, una palabra en Inglés que podría ser cinco caracteres, 10 personajes, tal vez incluso más. Luego de añadir sólo 32 más bits podría ser menos de gran cosa. 

¿Qué pasaría si cada uno de los estudiantes en la manifestación Estábamos literalmente estructuras estudiantiles que tienen nombres y casas y tal vez números de teléfono y Twitter mangos y similares. Así que todos los campos que empezamos hablando el otro día, mucho menos de un gran problema ya nuestros nodos se ponen más interesantes y grande para gastar, eh, un adicional indicador acaba de vincular entre sí. Pero de hecho, es un trade-off. Y, en efecto, el código es más complejo, ya que tendrás ver con una lectura rápida a través ese ejemplo particular. Pero ¿y si hubiera algún santo grial aquí. ¿Qué pasa si no tomamos un paso hacia atrás, pero un gran paso hacia adelante e implementar un dato estructura a través de la cual puede encontrar elementos como Jack o Christine o cualesquiera otros elementos en esta matriz en la verdadera constante de tiempo? La búsqueda es constante. Eliminar es constante. Inserte es constante. Todas estas operaciones son constantes. Ese sería nuestro santo grial. Y ahí es donde estamos recogerá la próxima vez. Nos vemos entonces.