[Powered by Google Translate] [Semana 6, continuación] [David J. Malan] [Harvard University] [Esta es CS50.] [CS50.TV] Esto es CS50 y este es el fin de semana 6. Así CS50x, uno de los primeros cursos de Harvard que participan en la iniciativa EDX de hecho debutó este pasado lunes. Si a usted le gustaría echar un vistazo a lo que otros en Internet están siguiendo junto con, usted puede dirigirse a x.cs50.net. Eso le redirigirá al lugar apropiado en edx.org, que era donde este y otros cursos del MIT y Berkeley ahora vivimos. Usted tendrá que registrarse para obtener una cuenta, usted encontrará que el material es en gran parte el mismo como usted ha tenido este semestre, aunque un par de semanas con retraso, ya que tener todo listo. Pero lo que los estudiantes en CS50x ahora se ve es una interfaz bastante como éste. Esto, por ejemplo, es Zamyla liderando el conjunto de problemas paso a paso para 0. Al iniciar la sesión en edx.org, un estudiante CS50x ve el tipo de cosas usted esperaría ver en un curso: la conferencia para el lunes, conferencia para el miércoles, varios cortometrajes, los boletines de problemas, los tutoriales, archivos PDF. Además, como usted ve aquí, las traducciones automáticas de las transcripciones inglés al chino, japonés, españoles, italianos, y un montón de otras lenguas que sin duda será imperfecta tal como las desplegar mediante programación con algo que se llama una API, o interfaz de programación de aplicaciones, desde Google que nos permite convertir Inglés a otros idiomas. Pero gracias al maravilloso espíritu de algunos voluntarios más de cien, personas al azar en la Internet que han ofrecido amablemente a participar en este proyecto, que poco a poco va a mejorar la calidad de las traducciones haciendo que los humanos corregir los errores que nuestros equipos han hecho. Así que resulta que había unos cuantos estudiantes más aparecer el lunes de lo que inicialmente se esperaba. De hecho, ahora CS50x cuenta con 100.000 personas a lo largo de los siguientes en casa. Entonces se da cuenta que todos somos parte de esta clase inaugural de hacer este curso en ciencias de la computación educación en general, de manera más amplia y accesible. Y la realidad es ahora, con algunos de estos cursos en línea masivos, todos ellos comienzan con estos números muy altos, como parece que hemos hecho aquí. Pero el objetivo, en última instancia, por CS50x es realmente hacer que la gente como muchos hasta la meta como sea posible. Por su diseño, CS50x va a ser ofrecido desde el pasado lunes hasta el 15 de abril de 2013, por lo que las personas que tienen compromisos escolares en otras partes, trabajo, familia, otros conflictos y similares, tienen un poco más de flexibilidad con la que sumergirse en este curso, que, basta con decir, es bastante ambiciosa hecho si sólo en el transcurso de tan sólo tres meses durante un semestre normal. Sin embargo, estos estudiantes serán hacer frente a los boletines de problemas mismos, viendo el mismo contenido, tener acceso a los mismos pantalones cortos y similares. Así que darse cuenta de que todos somos verdaderamente juntos en esto. Y uno de los objetivos finales de CS50x no es sólo para la gente como muchos a la línea de meta y darles este nuevo entendimiento de la informática y la programación, sino también para hacer que esta experiencia compartida. Una de las características definitorias de 50 en el campus, así lo esperamos, ha sido este tipo de experiencia común, para bien o para mal, a veces, pero teniendo estas personas se vuelvan hacia la izquierda y hacia la derecha, y horas de oficina y el hackathon y la feria. Es un poco más difícil que hacerlo en persona con amigos en línea, pero CS50x concluirá en abril con la primera CS50 Expo, que será una adaptación en línea de nuestra idea de la feria donde estos miles de estudiantes de todo serán invitados a presentar un 1 - a 2 minutos de video, ya sea un screencast de su proyecto final o video de ellos agitando hola y hablando de su proyecto y le demos, al igual que sus predecesores han hecho aquí en el campus de la feria, de modo que por el final del semestre, se espera tener una exposición mundial de los proyectos de los estudiantes CS50x 'finales, muy parecida a la que le espera este mes de diciembre en el campus. Así que más en que en los próximos meses. Con 100.000 estudiantes, sin embargo, viene la necesidad de un CAS poco más. Teniendo en cuenta que ustedes están abriendo el camino aquí y tomando CS50 varias semanas antes del lanzamiento de este material a la gente en EDX, damos cuenta de que le encantaría participar ya que muchos de nuestros estudiantes como sea posible en esta iniciativa, tanto durante el semestre de invierno, así como esta y la próxima primavera. Así que si usted desea participar en CS50x, particularmente en unirse a CS50x tratar, la versión de EDX CS50 Discutir, que muchos de ustedes se han estado utilizando en el campus, el tablón de anuncios en línea, por favor cabeza a esa URL, vamos a saber quién eres, porque nos encantaría construir un equipo de estudiantes y profesores y el personal por igual en el campus que están simplemente jugando bien y ayudando. Y cuando ven a una cuestión que es familiar para ellos, que escuche un estudiante informar algún error en alguna parte ahí fuera en algún país en Internet, y que suena una campana, ya que también tenía ese mismo número en su d-hall hace algún tiempo, es de esperar entonces usted puede meter su cuchara y compartir su propia experiencia. Así que por favor participar si usted quisiera. Cursos de ciencias de la computación en la Universidad de Harvard tiene un poco de una tradición, CS50 entre ellos, de tener un poco de ropa, algo de ropa, que se puede llevar con orgullo al final del semestre, diciendo muy orgulloso de que haya terminado CS50 y tomó CS50 y similares, y siempre tratamos de involucrar a los estudiantes en este proceso tanto como sea posible, mediante el cual invitamos, en esta época del semestre, los estudiantes a presentar sus diseños el uso de Photoshop, o cualquier herramienta de selección que desea utilizar si eres un diseñador, a presentar sus diseños para camisetas y sudaderas y sombrillas y pañuelos para perros pequeños que ahora tenemos y similares. Y todo es entonces - los ganadores de cada año después se exhibió en la página web de la asignatura en store.cs50.net. Todo lo que se vende a un costo allí, pero el sitio web sólo en sí funciona y permite a las personas elegir los colores y diseños que les gustan. Así que pensé que acabábamos de compartir algunos de los diseños del año pasado que estaban en el sitio web, además de este de aquí, que es una tradición anual. "Cada día estoy Seg Faultn" fue una de las presentaciones del año pasado, que todavía se encuentra allí para antiguos alumnos. Hemos tenido este ", CS50, Established 1989". Uno de nuestros Bowdens, Rob, era muy popular el año pasado. "Equipo de Bowden" nació, este diseño fue presentado, entre los más vendidos. Al igual que este de aquí. Mucha gente tenía "fiebre Bowden", de acuerdo a los registros de ventas. Darse cuenta de lo que ahora podría ser el diseño de ahí, en Internet. Más detalles sobre este problema en el siguiente establece por venir. Una de las herramientas más: usted ha tenido alguna exposición y espero que ahora algo de experiencia práctica con GDB, que es, por supuesto, un depurador y permite manipular su programa a un nivel bastante bajo, haciendo que tipo de cosas? ¿Qué GDB permiten hacer? ¿Sí? Dame algo. [Respuesta Estudiantil, ininteligible] Bueno. Entre en la función, por lo que no sólo hay que escribir run y tienen el golpe programa a través de su totalidad, la impresión de las cosas en la salida estándar. Más bien, usted puede caminar a través de línea por línea, ya sea escribiendo próximo a ir línea por línea a línea o paso a sumergirse en una función, típicamente uno que usted escribió. ¿Qué más hace el BGF le permiten hacer? ¿Sí? [Respuesta Estudiantil, ininteligible] Imprimir variables. Así que si usted quiere hacer un poco de introspección dentro de su programa de sin tener que recurrir a escribir sentencias printf por todo el lugar, usted puede imprimir una variable o mostrar una variable. ¿Qué más se puede hacer con un depurador GDB como? [Respuesta Estudiantil, ininteligible] Exactamente. Puede establecer puntos de interrupción, se puede decir que la ejecución descanso en la función principal o la función foo. Se puede decir que la ejecución de descanso en la línea 123. Y los puntos de interrupción son una técnica muy poderosa porque si usted tiene una idea general de dónde está su problema probablemente es, usted no tiene que perder tiempo pasando a través de la totalidad del programa. Usted puede esencialmente saltar allí y comience a escribir - paso a paso a través de él con el paso o el siguiente o similar. Pero el problema con algo como GDB es que te ayuda, los recursos humanos, encontrar sus problemas y encontrar sus errores. No necesariamente encontrarlos tanto por ti. Así se introdujo el style50 otro día, que es una herramienta de línea de comandos corto que trata de estilizar su código un poco más limpio que tú, el ser humano, podría haber hecho. Pero eso, también, es en realidad una cosa estética. Pero resulta que hay esta otra herramienta llamada Valgrind que es un poco más arcano de usar. Su salida es atrozmente críptico a primera vista. Pero es maravillosamente útil, sobre todo ahora que estamos en la parte del término donde vas a empezar a usar malloc y la asignación de memoria dinámica. Las cosas pueden ir muy, muy mal rápidamente. Porque si usted se olvida de liberar su memoria, o deja de hacer referencia alguna puntero NULL, o deja de hacer referencia alguna puntero de basura, lo que suele ser el síntoma de que los resultados? Seg culpa. Y se obtiene el archivo base de una cierta cantidad de kilobytes o megabytes que representa el estado de la memoria del programa, cuando se estrelló, pero en última instancia, su programa seg fallas, falla de segmentación, lo que significa que algo malo ha pasado casi siempre relacionados a un error relacionado con la memoria que usted ha hecho en alguna parte. Así Valgrind ayuda a encontrar cosas como esta. Es una herramienta que se ejecuta, como GDB, después de haber compilado el programa, pero en lugar de ejecutar el programa directamente, se corre Valgrind y se pasa a su programa, tal como lo hace con GDB. Ahora, el uso, para obtener el mejor tipo de salida, es un poco largo, así que ahí lo alto de la pantalla verás Valgrind-v. "-V" casi universalmente significa detallado cuando usted está utilizando programas en un equipo Linux. Por lo tanto, significa escupir más datos que usted puede ser que de forma predeterminada. "- Comprobar fugas = full." Esto es sólo decir cheque por todas las posibles pérdidas de memoria, errores que pude haber hecho. Esto, también, es un paradigma común con los programas de Linux. En general, si usted tiene un argumento de línea de comandos que es un "switch", que se supone que para cambiar el comportamiento del programa, y ​​es una sola letra, es-v, pero si eso cambia, sólo por el diseño del programador, es una palabra completa o una serie de palabras, el argumento de línea de comandos se inicia con -. Estos son sólo convenciones humanas, pero las vas a ver cada vez más. Y luego, finalmente, "a.out" es el nombre arbitrario para el programa en este ejemplo en particular. Y aquí está una salida representativa. Antes de ver lo que esto significa, déjame ir a un fragmento de código por aquí. Y déjame mover esta fuera del camino, muy pronto, y vamos a echar un vistazo a memory.c, que es este pequeño ejemplo aquí. Así que en este programa, quiero hacer un zoom sobre las funciones y preguntas. Tenemos una función principal que llama a una función, f, y entonces, ¿qué f proceder a hacer, en Inglés un poco técnico? ¿Qué hace f proceder a hacer? ¿Qué voy a empezar con la línea 20, y la ubicación de la estrella, no importa, pero sólo voy a ser coherentes con la última conferencia. ¿Cuál es la línea 20 es para nosotros? En el lado de mano izquierda. Vamos a descomponer aún más. Int * x: ¿qué hacer? Bien. Se declara un puntero, y ahora vamos a ser aún más técnico. ¿Qué quiere decir, muy concretamente, para declarar un puntero? ¿Alguien más? ¿Sí? [Respuesta Estudiantil, ininteligible] Demasiado lejos. Así que usted está leyendo al lado derecho del signo igual. Vamos a centrarnos sólo en el lado izquierdo, justo en int * x. Esto significa "declarar" un puntero, pero ahora vamos a bucear más profundo a esa definición. ¿Qué quiere decir concretamente, técnicamente significa? ¿Sí? [Respuesta Estudiantil, ininteligible] Bien. Se está preparando para guardar una dirección en la memoria. Bueno. Y vamos a tomar un paso más allá, es declarar una variable, x, que es de 32 bits. Y yo sé que es de 32 bits porque -? No es porque es un int, porque es un puntero en este caso. La coincidencia de que es uno y el mismo con un int, pero el hecho de que no es la estrella no significa que es un puntero y en el aparato, como con muchos equipos, pero no todos, los punteros son de 32 bits. El hardware más moderno, como los últimos Macs, los últimos ordenadores, puede tener punteros de 64 bits, pero en el aparato, estas cosas son de 32 bits. Así que vamos a estandarizar en eso. Más concretamente, la historia va como sigue: Nosotros "declarar" un puntero, lo que quiere decir eso? Nos preparamos para almacenar una dirección de memoria. ¿Qué significa eso? Creamos una variable llamada x que ocupa 32 bits que pronto va a almacenar la dirección de un número entero. Y eso es probablemente tan precisos como podamos. Está bien avanzar a simplificar el mundo y decir declarar un puntero llamado x. Declara un puntero, pero darse cuenta y entender lo que realmente está pasando incluso en tan sólo esos pocos caracteres. Ahora, éste es casi un poco más fácil, aunque es una expresión más larga. Entonces, ¿qué está haciendo esto, eso es resaltada ahora: "malloc (10 * sizeof (int));" ¿Sí? [Respuesta Estudiantil, ininteligible] Bueno. Y lo voy a llevar allí. Se asigna una porción de memoria para diez enteros. Y ahora vamos a bucear un poco más profundo, es la asignación de una parte de la memoria para diez enteros. Lo que se malloc luego regresar? La dirección de ese bloque, o, más concretamente, la dirección del primer byte de ese bloque. ¿Cómo entonces soy el programador, para saber dónde está ese pedazo de fines de memoria? Yo sé que es contigua. Malloc, por definición, le dará una parte contigua de la memoria. No hay espacios en blanco. Usted tiene acceso a todos los bytes en ese pedazo, espalda con espalda con espalda, pero ¿cómo puedo saber dónde está el final de este trozo de memoria es? Cuando se utiliza malloc? [Respuesta Estudiantil, ininteligible] Bueno. No lo sabes. Usted tiene que recordar. Tengo que recordar que usé el valor 10, y ni siquiera parecen haber hecho eso aquí. Sin embargo, la responsabilidad recae enteramente sobre mí. Strlen, que nos hemos vuelto un poco dependientes de las cadenas, sólo funciona a causa de esta convención de tener \ 0 o este carácter especial nul, NUL, al final de una cadena. Eso no se sostiene por unos trozos arbitrarios de la memoria. Todo depende de usted. Así que la línea 20, a continuación, asigna un trozo de memoria que puede almacenar diez números enteros, y almacena la dirección del primer byte de ese bloque de memoria en la variable x se llama. Ergo, que es un puntero. Así que la línea 21, por desgracia, fue un error. Pero primero, ¿qué está haciendo? Está diciendo tienda en el lugar 10, 0 indexado, del bloque de memoria llamado x el valor 0. Así cuenta un par de cosas están sucediendo. A pesar de que x es un puntero, recuperará un par de semanas que todavía se puede utilizar la notación cuadrada estilo-matriz soporte. Porque eso es realmente taquigrafía notación para la aritmética de punteros más críptico de futuro. donde íbamos a hacer algo como esto: Tome la dirección x, mueva más de 10 puntos, a continuación, ir allí a cualquier dirección se almacena en esa ubicación. Pero, francamente, esto no es más atroz de leer y sentirse cómodo con. Así que el mundo suele utilizar los corchetes sólo porque es mucho más amigable para leer. Pero eso es lo que realmente está pasando debajo de la campana; x es una dirección no una matriz, per se. Así que este es el almacenamiento de 0 en lugar 10 en x. ¿Por qué es esto malo? ¿Sí? [Respuesta Estudiantil, ininteligible] Exactamente. Sólo nos asignaron diez enteros, pero contamos desde 0 al programar en C, por lo que tiene acceso a la 0 1 2 3 4 5 6 7 8 9, pero no 10. Así que, o el programa va a culpa seg o no lo es. Sin embargo, no se sabe muy bien, lo que es una especie de comportamiento no determinista. Realmente depende de si tenemos suerte. Si resulta que el sistema operativo no le importa si utilizo ese byte extra, a pesar de que no lo ha dado a mí, mi programa no se puede bloquear. Es crudo, tiene fallos, pero es posible que no vea ese síntoma, o puede que lo veo de vez en cuando. Pero la realidad es que el error es, de hecho, existe. Y es realmente problemático si usted ha escrito un programa que quieres ser correcta, que ha vendido el programa que la gente está utilizando que cada de vez en cuando se bloquea porque, por supuesto, esto no es bueno. De hecho, si usted tiene un teléfono Android o un iPhone y descargar aplicaciones en estos días, si usted ha tenido alguna vez una aplicación para dejar de fumar justo, de repente desaparece, que es casi siempre el resultado de algún problema relacionado con la memoria, por lo que el programador pata y anula la referencia de un puntero que él o ella no debe tener, y el resultado de iOS o Android es matar sólo el programa completo en lugar de los comportamientos de riesgo definidos o algún tipo de compromiso de seguridad. Hay un error en este otro programa aparte de éste. ¿Qué más he cagado en este programa? Yo no he practicado lo que he predicado. ¿Sí? [Respuesta Estudiantil, ininteligible] Bueno. No he liberado la memoria. Así que la regla de oro ahora tiene que ser en cualquier momento de llamar malloc, debe llamar libre cuando haya terminado de usar esa memoria. Ahora, cuando iba yo a querer liberar esta memoria? Probablemente, asumiendo esta primera línea era correcta, me gustaría hacerlo aquí. Porque yo no podría, por ejemplo, lo hacen aquí. ¿Por qué? Justo fuera de su alcance. Así que, aunque estamos hablando de punteros, esta es una semana 2 o 3 cuestión, donde x es sólo un alcance dentro de las llaves donde se declaró. Así que definitivamente no se puede liberar allí. Mi única oportunidad de liberarlo es más o menos después de la línea 21. Este es un programa bastante sencillo, era bastante fácil una vez que tipo de envolvió su mente en torno a lo que el programa está haciendo, dónde están los errores eran. E incluso si usted no lo vi al principio, esperamos que sea un poco obvio ahora que estos errores son bastante fácil de resolver y hacer fácilmente. Pero cuando un programa tiene más de 12 líneas de largo, que es 50 líneas, 100 líneas de largo, caminando por el código línea por línea, pensar en ello, lógicamente, Es posible, pero no muy divertido de hacer, constantemente en busca de errores, y también es difícil de hacer, y es por eso que una herramienta como Valgrind existe. Déjenme seguir adelante y hacer esto: déjame abrir la ventana de terminal, Y no me basta con ejecutar la memoria, porque la memoria parece estar bien. Estoy teniendo suerte. Que va a byte adicional al final de la matriz no parece ser demasiado problemático. Pero me deja, no obstante, hacer una comprobación de validez, lo cual significa para comprobar si es o no es realmente correcto. Así que vamos a hacer valgrind-v - Fuga-check = completo, y luego el nombre del programa en este caso es la memoria, no a.out. Así que déjame ir adelante y hacerlo. Pulse Enter. Querido Dios. Esta es su salida, y esto es lo que he aludido antes. Pero, si aprendes a leer a través de todos los disparates aquí, la mayor parte de esta producción es sólo de diagnóstico que no es tan interesante. Lo que el ojo realmente quiere estar buscando es cualquier mención de error o no válido. Palabras que sugieren problemas. Y, de hecho, vamos a ver lo que va mal aquí abajo. Tengo un resumen de algún tipo, "en uso en la salida:. 40 bytes en bloques de 1" No estoy realmente seguro de lo que un bloque es todavía, pero 40 bytes en realidad se siente como si pudiera averiguar dónde que viene. 40 bytes. ¿Por qué son de 40 bytes en uso en la salida? Y más concretamente, si nos desplazamos hasta aquí, ¿por qué he perdido definitivamente 40 bytes? ¿Sí? [Respuesta Estudiantil, ininteligible] Perfect. Sí, exactamente. Había diez números enteros, y cada uno de ellos es el tamaño de 4, o 32 bits, así que he perdido 40 bytes precisamente porque, como usted propone, no he llamado libre. Eso es un error, y ahora vamos a mirar hacia abajo un poco más y ver al lado de este, "No válido escribir de tamaño 4". Ahora, ¿qué es esto? Esta dirección se expresa lo que la notación de base, al parecer? Esto es hexadecimal, y cada vez que ve un número que comienza con 0x, significa hexadecimal, lo que hicimos allá por, creo, conjunto de procesadores 0 en la sección de preguntas, que era sólo para hacer un ejercicio de calentamiento, la conversión de decimal a hexadecimal a binario y así sucesivamente. Hexadecimal, sólo por convención humana, generalmente se utiliza para representar los punteros o, más generalmente, se dirige. Es sólo una convención, porque es un poco más fácil de leer, que es un poco más compacto que algo como decimal, y binario es inútil para la mayoría de los seres humanos para su uso. ¿Y ahora qué quiere decir esto? Bueno, parece que hay una escritura no válido de tamaño 4 en la línea 21 de memory.c. Así que vamos a volver a la línea 21, y de hecho, es que de escritura no válido. Así Valgrind no se va a celebrar por completo mi mano y me diga lo que la solución es, pero se detecta que estoy haciendo una escritura válida. Estoy tocando 4 bytes que no debe ser, y al parecer eso es porque, como usted ha señalado, estoy haciendo [10] en lugar de [9] máximamente o [0] o algo intermedio. Con Valgrind, se dan cuenta en cualquier momento que ahora estamos escribiendo un programa que utiliza punteros y utiliza la memoria, y malloc más específicamente, definitivamente entrar en el hábito de correr tanto tiempo pero muy fácil de copiar y pegar comandos de Valgrind para ver si hay algunos errores en ese país. Y va a ser abrumador cada vez que ves la salida, pero sólo a través de analizar visualmente la totalidad del producto y ver si usted ve las menciones de errores o advertencias o inválida o perdida. Las palabras que suenan como te equivocaste en alguna parte. Así que darse cuenta de que es una nueva herramienta en su caja de herramientas. Ahora el lunes, tuvimos un montón de gente viene hasta aquí y representar la noción de una lista enlazada. Y presentamos la lista enlazada como una solución a cuál es el problema? ¿Sí? [Respuesta Estudiantil, ininteligible] Bueno. Las matrices no pueden tener memoria que se agrega a ellos. Si asigna una matriz de tamaño 10, eso es todo lo que hay. Usted puede llamar a una función como realloc si inicialmente llamada malloc, y que puede tratar de crecer la matriz si no hay espacio hacia el final de ella que nadie más está usando, y si no hay, se acaba de encontrar un pedazo más grande a otro lugar. Pero entonces se copiará todos esos bytes en la nueva matriz. Esto suena como una solución muy correcta. ¿Por qué es poco atractivo? Quiero decir que funciona, los seres humanos han resuelto este problema. ¿Por qué tenemos que resolver el lunes con listas enlazadas? ¿Sí? [Respuesta Estudiantil, ininteligible] Podría tomar mucho tiempo. De hecho, cada vez que usted está llamando malloc o calloc o realloc, que es una más, cualquier usted tiempo, el programa, están hablando con el sistema operativo, que tienden a frenar el programa de abajo. Y si usted está haciendo este tipo de cosas en los bucles, en realidad está ralentizando. No vas a notar esto para el más simple de "Hello World" programas de tipo, pero en programas mucho más grandes, haciendo que el sistema operativo y otra vez para la memoria o dar de nuevo una y otra vez no suele ser una buena cosa. Además, es sólo una especie de intelectual - es una completa pérdida de tiempo. ¿Por qué asignar más memoria y más, el riesgo de copiar todo en la nueva matriz, si usted tiene una alternativa que le permite asignar memoria sólo lo que realmente necesita? Así que hay ventajas y desventajas en aquí. Una de las ventajas es que ahora tenemos dinamismo. No importa donde los trozos de memoria son que son gratuitas, Sólo puede ordenar de crear estas migas de pan a través de punteros para encadenar mi lista entera unidos entre sí. Pero me pagar al menos un precio. ¿Qué tengo que renunciar a obtener listas enlazadas? ¿Sí? [Respuesta Estudiantil, ininteligible] Bueno. Usted necesita más memoria. Ahora necesito espacio para estos indicadores, y en el caso de esta super lista enlazada simple que sólo está tratando de almacenar enteros, que son 4 bytes, seguimos diciendo así, un puntero es de 4 bytes, por lo que ahora hemos duplicado literalmente la cantidad de memoria que necesita sólo para almacenar esta lista. Pero una vez más, se trata de un compromiso constante en la informática entre el tiempo y el espacio y el desarrollo, el esfuerzo y otros recursos. ¿Cuál es otra desventaja de usar una lista enlazada? ¿Sí? [Respuesta Estudiantil, ininteligible] Bueno. No es tan fácil de acceder. Ya no podemos aprovechar semana 0 principios como dividir y conquistar. Y más específicamente, la búsqueda binaria. Porque a pesar de que los seres humanos puede ver más o menos donde la mitad de esta lista es, el equipo sólo sabe que esta lista enlazada comienza en la dirección llamado primero. Y eso es 0x123 o algo por el estilo. Y la única manera que el programa puede encontrar el elemento central en realidad es buscar toda la lista. Y aun así, literalmente, tiene que buscar en toda la lista porque incluso una vez que llegue el elemento central siguiendo los punteros, te, el programa, no tienen idea de cuánto tiempo esta lista es, en potencia, hasta llegar a la final de la misma, y ​​¿cómo saber programación que estamos al final de una lista enlazada? Hay un puntero NULL especial, por lo que una vez más, una convención. En lugar de utilizar este puntero, definitivamente no queremos que sea un valor basura apuntando en algún lugar fuera del escenario, queremos que sea la mano hacia abajo, NULL, así que tenemos este término en esta estructura de datos para que sepamos dónde termina. ¿Qué pasa si queremos manipular esto? Hicimos la mayor parte de esto visualmente, y con los seres humanos, pero lo que si queremos hacer una inserción? Así que la lista original de 9, 17, 20, 22, 29, 34. ¿Y si luego quería malloc espacio para el número 55, un nodo para ello, y luego queremos insertar 55 en la lista al igual que hicimos el lunes? ¿Cómo podemos hacer esto? Bueno, Anita se acercó y ella caminó esencialmente la lista. Ella comenzó en el primer elemento, luego el siguiente, el siguiente, el siguiente, el siguiente, el siguiente. Por último golpeó la mano izquierda hasta el fondo y se dio cuenta oh, este es NULL. Entonces, ¿qué manipulación de punteros que había que hacer? La persona que estaba en el extremo, número 34, necesitaba su mano izquierda levantada para señalar a los 55, 55 necesitaban su brazo izquierdo hacia abajo para ser el nuevo terminador NULL. Hecho. Bastante fácil de insertar 55 en una lista ordenada. ¿Y cómo podría este aspecto? Déjenme seguir adelante y abrir algunos ejemplo de código aquí. Voy a abrir gedit, y me dejó abrir dos archivos primero. Uno de ellos es list1.h, y permítanme recordarles que este era el trozo de código que se utilizó para representar un nodo. Un nodo tiene tanto un llamado int n y un puntero próximo llamado que simplemente apunta a lo siguiente en la lista. Que se encuentra ahora en un archivo. H. ¿Por qué? Hay una convención, y no se han aprovechado de esto una cantidad enorme de nosotros mismos, pero la persona que escribió funciones printf y otros dio como regalo al mundo todas esas funciones al escribir un archivo llamado stdio.h. Y luego está string.h, y luego está Map.h, y no todos estos archivos h que se puede haber visto o utilizado durante el término escrito por otras personas. Normalmente, en los. Archivos h son únicas cosas como typedefs o declaraciones de tipos personalizados o declaraciones de constantes. No poner las implementaciones funciones 'en los archivos de cabecera. Se pone, en cambio, sólo sus prototipos. Pones las cosas que quieres compartir con el mundo lo que necesitan con el fin de compilar su código. Así que para entrar en este hábito, decidimos hacer lo mismo. No hay mucho en list1.h, pero hemos puesto algo que podría ser de interés para las personas en el mundo que quieren utilizar nuestra aplicación lista enlazada. Ahora, en list1.c, no voy a ir a través de todo este asunto porque es un poco largo, este programa, pero vamos a ejecutarlo realmente rápido en el indicador. Permítanme compilar list1, déjame a continuación, ejecute list1, y lo que veremos es hemos simulado un programa pequeño y sencillo aquí que va a permitir a mí para agregar y quitar los números de una lista. Así que vamos a seguir adelante y me escriba 3 para la opción de menú 3. Quiero insertar el número - de dejar hacer el primer número, que tenía 9 años, y ahora me dicen que la lista es ahora 9. Déjame ir adelante y hacerlo otra inserción, por lo que llegué a la opción de menú 3. ¿A qué número desea insertar? 17. Intro. Y voy a hacer uno más. Permítanme introducir el número 22. Así que tenemos el comienzo de la lista enlazada que teníamos en forma de diapositivas hace un momento. ¿Cómo es esta inserción sucediendo realmente? En efecto, 22 se encuentra ahora en el final de la lista. Así que la historia nos dice en el escenario el lunes y volver a tapar justo ahora en realidad debe estar sucediendo en el código. Vamos a echar un vistazo. Permítanme baje este archivo. Vamos a pasar por alto algunas de las funciones, pero vamos a ir a, por ejemplo, la función de inserción. Vamos a ver cómo hacemos para insertar un nuevo nodo en la lista enlazada. ¿Dónde está la lista declarado? Bueno, vamos a recorrer todo el camino hasta la parte superior, y note que mi lista enlazada es esencialmente declarada como único puntero es NULL inicialmente. Así que estoy utilizando una variable global aquí, que en general hemos predicado contra porque hace que su código un poco complicado de mantener, es una especie de perezoso, por lo general, pero no es perezoso y no es malo y no es malo si solo propósito de su programa en la vida es para simular una lista enlazada. Que es exactamente lo que estamos haciendo. Así que en lugar de declarar esto en principal y luego tener que pasar a todas las funciones hemos escrito en este programa, en lugar realizar oh, vamos a hacerla global porque todo el propósito de este programa es demostrar una y sólo una lista enlazada. Así que se siente bien. Aquí están mis prototipos, y no vamos a ir a través de todos ellos, pero escribí una función de eliminación, una función de búsqueda, una función de inserción, y una función de desplazamiento. Pero ahora vamos a ir de nuevo a la función de inserción y ver cómo se trabaja aquí. Insert está en línea - aquí vamos. Insertar. Así que no tiene ningún argumento, porque vamos a pedir el usuario dentro de esta función para el número que desee insertar. Pero antes, nos preparamos para darles un poco de espacio. Esta es una especie de copiar y pegar desde el otro ejemplo. En ese caso, le estaban asignando un int, esta vez estamos asignando un nodo. Yo no me acuerdo cuántos bytes de un nodo es, pero eso está bien. Sizeof puede darse cuenta de eso por mí. Y ¿por qué estoy comprobando NULL en la línea 120? ¿Qué podría salir mal en la línea 119? ¿Sí? [Respuesta Estudiantil, ininteligible] Bueno. Sólo podría darse el caso de que le he pedido demasiada memoria o que algo anda mal y el sistema operativo no tiene suficientes bytes para darme, por lo que señala tanto al devolver NULL, y si no comprueban que y yo ciegamente proceder a utilizar la dirección devuelta, puede ser NULL. Podría ser algún valor desconocido, no es una buena cosa a menos que yo - en realidad no será un valor desconocido. Puede ser NULL, por lo que no quiero para abusar de ella y arriesgarse a dereferencing ella. Si eso sucede, yo acabo de volver y vamos a fingir que no he tenido ningún recuerdo en absoluto. De lo contrario, le digo al usuario darme un número para insertar, que llamo nuestra getInt viejo amigo, y ésta era la nueva sintaxis se introdujo el lunes. 'Newptr-> n' significa tomar la dirección que le dieron por malloc que representa el primer byte de un objeto nuevo nodo, y luego ir al campo llamado n. Una pregunta de la trivia poco: Esto es equivalente a lo que la línea más críptica de código? ¿Cómo podría yo haber escrito esto? ¿Quieres tomar una puñalada? [Respuesta Estudiantil, ininteligible] Bueno. Usando el n., Pero no es tan simple como esto. ¿Qué es lo primero que hacer? [Respuesta Estudiantil, ininteligible] Bueno. Tengo que hacer newptr.n *. Así que esto nos dice nuevo puntero es obviamente una dirección. ¿Por qué? Debido a que fue devuelto por malloc. El newptr * diciendo "ir allí" y luego una vez que estás allí, entonces usted puede utilizar el más familiar. n, pero esto sólo se ve un poco feo, sobre todo si los seres humanos se van a elaborar indicadores con flechas todo el tiempo, el mundo se ha estandarizado en esta notación flecha, que hace exactamente lo mismo. Por lo que sólo utilice la opción -> notación cuando la cosa de la izquierda es un puntero. De lo contrario, si se trata de una estructura real, utilice el n.. Y luego esto: ¿Por qué inicializar newptr-> siguiente a NULL? No queremos que una mano izquierda colgando fuera de la final de la etapa. Queremos que apunta hacia abajo, lo que significa que al final de esta lista podría ser en este nodo, así que mejor asegurarse de que es NULL. Y, en general, la inicialización de las variables o de sus miembros de datos y estructuras a algo que es sólo una buena práctica. Dejar simplemente basura existen y seguirán existiendo generalmente te mete en problemas si usted se olvida de hacer algo en el futuro. Aquí hay unos pocos casos. Esto, de nuevo, es la función de inserción, y lo primero que comprobar es si la variable llamada en primer lugar, esa variable global es NULL, que significa que no hay lista enlazada. No hemos introducido ningún número, por lo que es trivial para insertar este número actual en la lista, ya que sólo pertenece al comienzo de la lista. Así que esto fue cuando Anita estaba de pie allí sola, pretendiendo no había nadie más por aquí en el escenario hasta que nos asignaron un nodo, entonces podría levantar la mano por primera vez, si todo el mundo había llegado a la etapa después de ella el lunes. Ahora aquí, este es un pequeño jaque que tengo que decir si el nuevo nodo de valor de n es siguiente, lo que significa ir a la estructura que está siendo apuntado por newptr, así que aquí estamos, ir allí. A continuación, en la flecha que está diciendo obtener el siguiente campo y haga el signo = está diciendo qué valor colocar allí? El valor que se encontraba en primer lugar; qué valor estaba en primer lugar? En primer lugar se señala en este nodo, por lo que significa esto ahora debe apuntar a este nodo. En otras palabras, aunque lo que parece un lío ridículo con mi letra, ¿qué es una idea simple de mover sólo alrededor de estas flechas se traduce a código con sólo este trazador de líneas. Guarde lo que está en primer lugar en el siguiente campo y luego actualizar lo primero que realmente es. Vamos a seguir adelante y avance rápido a través de algo de esto, y que busque sólo en esta inserción cola por ahora. Supongamos que llego al punto en que me parece que el siguiente campo de un nodo es NULL. Y en este punto de la historia, un detalle que me estoy pasando por alto es que he introducido otro puntero hasta aquí en la línea 142, el puntero predecesor. Esencialmente, en este momento de la historia, una vez que la lista se hace larga, Yo como que tenga que caminar con dos dedos porque si voy demasiado lejos, Recuerdo que en una sola lista larga duración, no se puede volver atrás. Así que esta idea de predptr es mi dedo izquierdo, y newptr - no newptr. Otro indicador que está aquí es mi otro dedo, y yo soy sólo un poco de caminar en la lista. Es por eso que existe. Pero vamos a considerar sólo uno de los casos más simples aquí. Si el campo al lado de ese puntero es NULL, ¿cuál es la implicación lógica? Si usted está atravesando esta lista y te encuentras con un puntero NULL? Usted está en el final de la lista, por lo que el código para agregar este elemento a continuación, un adicional es un género de lo intuitivo tomará ese nodo cuya próxima puntero es NULL, así que esto es actualmente NULL, y cambiarlo, sin embargo, es la dirección del nuevo nodo. Así que estamos dibujando en el código de la flecha que dibujamos en el escenario por levantar la mano izquierda de una persona. Y el caso que voy a agitar las manos menos por ahora, sólo porque creo que es fácil perderse cuando lo hacemos en este tipo de entorno, es la comprobación de inserción en la parte media de la lista. Pero sólo intuitivamente, lo que debe suceder si usted quiere averiguar donde algún número debe colocarse en el centro es que tienes que caminar con más de un dedo, más de un puntero, averiguar donde debe estar por comprobar es el elemento La actual, y una vez que encuentre ese lugar, entonces usted tiene que hacer este tipo de juego de la cáscara en la que se mueven alrededor de los punteros con mucho cuidado. Y esa respuesta, si lo desea a la razón a través de esto en casa por su cuenta, se reduce sólo a estas dos líneas de código, pero el orden de las líneas es súper importante. Porque si se le cae la mano de alguien y levantar otra persona en el orden equivocado, una vez más, que podría terminar dejando huérfanos a la lista. Para resumir conceptualmente más, la inserción de la cola es relativamente sencillo. La inserción en la cabeza es también relativamente sencillo, pero hay que actualizar un puntero adicional en esta ocasión para exprimir el número 5 en la lista aquí, y luego introducirse en el medio implica un esfuerzo aún más, para insertar cuidadosamente el número 20 en su ubicación correcta, que es entre 17 y 22. Así que hay que hacer algo como tener el nuevo nodo de 20 puntos a 22, y, a continuación, puntero que nodo necesita ser actualizado por última? Es 17 que en realidad insertarlo. Así que de nuevo, voy a aplazar el código real para que la aplicación particular. A primera vista, es un poco abrumador, pero no deja de ser un bucle infinito que está lazo, lazo, lazo, lazo, y romper tan pronto como se golpeó el puntero NULL, momento en el que usted puede hacer la inserción requerida. Esto, entonces, es el representante código vinculado inserción lista. Eso fue un poco mucho, y se siente como que hemos resuelto un problema, pero hemos introducido un otro conjunto. Francamente, nos hemos pasado todo este tiempo en gran O y Ω y el tiempo de funcionamiento, tratando de resolver los problemas más rápidamente, y aquí estamos dando un gran paso hacia atrás, se siente. Y, sin embargo, si el objetivo es almacenar los datos, se siente como el Santo Grial, como dijimos el lunes, sería realmente para guardar las cosas al instante. En efecto, supongamos que hemos hecho la lista a un lado por un momento vinculado y que en vez introducido el concepto de una mesa. Y vamos a pensar en una mesa por un momento como una matriz. Esta matriz y este caso aquí tiene unos 26 elementos, del 0 al 25, y supongo que necesitaba un poco pedazo de almacenamiento para los nombres: Alice y Bob y Charlie y similares. Y se necesita algún tipo de estructura de datos para almacenar esos nombres. Bueno, podrías usar algo como una lista enlazada y se podía caminar por la lista de insertar Alice antes de que Bob y Charlie después de que Bob y así sucesivamente. Y, de hecho, si usted quiere ver un código como el que en un aparte, Sabemos que en list2.h, hacemos exactamente eso. No vamos a entrar a través de este código, pero esto es una variante del ejemplo primero que introduce una estructura que hayamos visto antes estudiante llamado, y entonces lo que realmente almacena en la lista enlazada es un puntero a una estructura estudiante en lugar de un número entero pequeño y sencillo, n. Así que darse cuenta de que hay código hay que implica cadenas reales, pero si el objetivo que nos ocupa realmente ahora es abordar el problema de la eficiencia, ¿No sería bueno si se nos da un objeto llamado Alice, queremos ponerla en el lugar adecuado en una estructura de datos, se siente como que sería muy agradable para poner sólo Alice, cuyo nombre comienza con A, en la primera ubicación. Y Bob, cuyo nombre empieza por B, en la segunda ubicación. Con una matriz, o vamos a empezar a llamar a una mesa, una tabla hash en que, podemos hacer exactamente eso. Si nos dan un nombre como Alice, una cadena como Alice, ¿dónde poner A-l-i-c-e? Necesitamos un hueristic. Necesitamos una función para tomar alguna entrada como Alicia y devolver una respuesta: "Pon Alice en este lugar." Y esta función, este cuadro de negro, se va a llamar una función hash. Una función hash es algo que toma una entrada, como "Alice", y vuelve a la que, por lo general, la ubicación numérica en alguna estructura de datos donde Alice pertenece. En este caso, nuestra función de hash debe ser relativamente simple. Nuestra función hash debe decir, si se le da "Alice", que personaje me debe importar? La primera de ellas. Así que miro a [0], y luego me dicen si [0] es un personaje, devuelva el número 0. Si es B, devolverá 1. Si se trata de C, volver 2, y así sucesivamente. Todos índice 0, y que me permita insertar Alice y Bob y Charlie y así sucesivamente en esta estructura de datos. Pero hay un problema. ¿Y si Anita viene otra vez? ¿Dónde ponemos Anita? Su nombre también empieza con la letra A, y se siente como que hemos hecho un lío aún mayor de este problema. Ahora tenemos la inserción inmediata, inserción constante de tiempo, en una estructura de datos en vez de peor caso lineal, pero ¿qué podemos hacer con Anita en este caso? ¿Cuáles son las dos opciones, ¿en serio? ¿Sí? [Respuesta Estudiantil, ininteligible] Bueno, por lo que podríamos tener otra dimensión. Eso es bueno. Así que podemos construir cosas en 3D como hablamos verbalmente el lunes. Podríamos añadir otro acceso aquí, pero supongo que no, estoy tratando de mantener esto simple. El objetivo general aquí es tener inmediato acceso en tiempo constante, de modo que está agregar demasiada complejidad. ¿Cuáles son las otras opciones cuando se trata de insertar Anita en esta estructura de datos? ¿Sí? [Respuesta Estudiantil, ininteligible] Bueno. Así que nos podíamos mover todos los demás hacia abajo, como Charlie codazos por Bob y Alice, y luego ponemos Anita donde ella realmente quiere ser. Por supuesto, ahora, no hay un efecto secundario de esto. Esta estructura de datos es probablemente útil no porque queremos insertar la gente una vez sino porque queremos comprobar si estás allí más tarde si queremos imprimir todos los nombres en la estructura de datos. Vamos a hacer algo con estos datos con el tiempo. Así que ahora tengo clase de jodido Alice, que ya no está donde se supone que debe ser. Ni Bob ni es Charlie. Así que tal vez esta no es una idea tan buena. Pero en realidad, esta es una opción. Podríamos pasar a todo el mundo, o diablos, Anita llegó tarde al juego, ¿por qué no acaba de poner Anita aquí no, aquí no, aquí no, vamos a ponerla un poco más abajo en la lista. Pero el problema comienza a delegar de nuevo. Usted puede ser capaz de encontrar al instante Alice, basada en su nombre. Y Bob instante, y Charlie. Pero luego buscar Anita, y ya ves, hmm, Alice se encuentra en el camino. Bueno, déjame ver por debajo de Alice. Bob no es Anita. Charlie no es Anita. Oh, no es Anita. Y si continúa esa línea de la lógica hasta el final, ¿cuál es el tiempo de ejecución del peor caso de encontrar o insertar Anita en esta nueva estructura de datos? Es O (n), ¿no? Debido a que en el peor de los casos, no es Alice, Bob, Charlie. . . todo el camino a alguien que se llama "Y", por lo que sólo hay un lugar a la izquierda. Afortunadamente, no tenemos a nadie llamado "Z", así que pusimos Anita en la parte inferior. Realmente no hemos resuelto ese problema. Así que tal vez es necesario introducir esta tercera dimensión. Y resulta que, si estamos de introducir esta tercera dimensión, no podemos hacer esto perfectamente, pero el Santo Grial se va a conseguir constante de tiempo de inserción y las inserciones dinámicos de modo que no tenemos que codificar una matriz de tamaño 26. Podemos insertar tantos nombres como queramos, pero vamos a tomar nuestro hijo de 5 minutos de descanso aquí y luego hacerlo correctamente. Está bien. Puse la historia hasta bastante artificial no por la elección de Alice y Bob y Charlie y Anita, cuyo nombre fue, obviamente, va a chocar con Alice. Pero la pregunta que terminó el lunes con es cuán probable es que se podrían obtener este tipo de colisiones? En otras palabras, si empezamos a utilizar esta estructura tabular, que es en realidad una matriz, en este caso de 26 sitios, ¿Y si en vez nuestras entradas están uniformemente distribuidos? No es artificialmente Alice y Bob y Charlie y David, y así sucesivamente por orden alfabético, está distribuida uniformemente sobre la A a la Z. Tal vez sólo tendremos que tener suerte y que no vamos a tener dos A o B de dos con una probabilidad muy alta, pero como alguien ha señalado, si se generalizó este problema y no hacer 0 a 25 pero, por ejemplo, de 0 a 364 o 65 años, a menudo el número de días en un año típico, y la pregunta, "¿Cuál es la probabilidad de que dos de nosotros en esta sala tienen el mismo cumpleaños?" Dicho de otra manera, ¿cuál es la probabilidad de que dos de nosotros tiene un nombre que comienza con A? El tipo de pregunta es la misma, pero este espacio de direcciones, este espacio de búsqueda, es más grande en el caso de cumpleaños, porque tenemos más de tantos días en el año que las letras del alfabeto. ¿Cuál es la probabilidad de una colisión? Bueno, podemos pensar en esto por averiguar las matemáticas en sentido contrario. ¿Cuál es la probabilidad de colisiones no? Pues bien, esta expresión aquí dice que lo que es la probabilidad si hay una sola persona en este salón, que celebra su cumpleaños único? Es 100%. Porque si hay una sola persona en la habitación, su cumpleaños puede ser cualquiera de los 365 días del año. Así que las opciones de 365/365 me da un valor de 1. Así que la probabilidad de que se trate en el momento es sólo 1. Pero si hay una segunda persona en la habitación, ¿cuál es la probabilidad de que su cumpleaños es diferente? Sólo hay 364 días posibles, haciendo caso omiso de los años bisiestos, para su cumpleaños no chocar con las otras personas. Así que 364/365. Si una tercera persona entra, es 363/365, y así sucesivamente. Así que seguimos multiplicando estas fracciones, que son cada vez más pequeños, para averiguar cuál es la probabilidad de que todos nosotros tenemos cumpleaños únicos? Pero podemos, por supuesto, acaba de tomar esa respuesta y darle la vuelta alrededor y hacer 1 menos todo eso, una expresión que finalmente va a conseguir si te acuerdas de la parte posterior de sus libros de matemáticas, se ve un poco de algo como esto, que es mucho más fácil de interpretar gráficamente. Y aquí tiene este gráfico en el eje x el número de cumpleaños, o el número de personas con cumpleaños, y sobre el eje y es la probabilidad de una coincidencia. Y lo que esto quiere decir es que si usted tiene, digamos, incluso, vamos a elegir algo así como 22, 23. Si hay 22 o 23 personas en la sala, la probabilidad de que dos de esas pocas personas van a tener el mismo cumpleaños en realidad es súper alta, combinatoria. 50% de probabilidad de que en una clase de sólo 22 personas, un seminario, prácticamente, 2 de esas personas van a tener el mismo cumpleaños. Porque hay muchas maneras en que usted puede tener el mismo cumpleaños. Peor aún, si nos fijamos en la parte derecha de la tabla, por el tiempo que tiene una clase con 58 estudiantes en el mismo, la probabilidad de que dos personas que tienen un alto cumpleaños es super, super, cerca del 100%. Ahora, eso es una especie de hecho de la diversión de la vida real. Pero las implicaciones, ahora, por las estructuras de datos y almacenamiento de información significa que sólo suponiendo que tiene un bonito, limpio distribución uniforme de los datos y tiene una amplia lo suficientemente grande para un montón de cosas no significa que usted va a hacer que la gente en lugares únicos. Vas a tener colisiones. Así que esta noción de hashing, como se le llama, teniendo una entrada como "Alice" y el masaje de alguna manera y luego volver a una respuesta como 0 ó 1 ó 2. Volviendo un poco de la salida de función que está plagada de esta probabilidad de colisión. ¿Cómo podemos manejar esas colisiones? Pues bien, en el primer caso, podemos tomar la idea que se sugiere. Sólo podemos cambiar a todo el mundo, o tal vez, un poco más simple, en lugar de todo el mundo se mueven más, vamos a mover Anita a la parte inferior del sitio disponible. Así que si Alice se encuentra en 0, Bob está en 1, Charlie está en 2, sólo tendremos que poner Anita del punto 3. Y esta es una técnica en la estructura de datos llamada sondeo lineal. Lineal porque estás caminando esta línea, y usted es una especie de sondeo para los puntos disponibles en la estructura de datos. Por supuesto, esto se convirtiera en O (n). Si la estructura de datos es muy completo, hay 25 personas en lo que ya, y entonces Anita llega, ella termina en lo que sería la ubicación Z, y eso está bien. Ella todavía le queda, y podemos encontrarla más tarde. Pero esto es contrario al objetivo de acelerar las cosas. Entonces, ¿qué pasaría si en vez introducida esta tercera dimensión? Esta técnica se denomina generalmente encadenamiento separado, o que tiene cadenas. Y lo que una tabla hash es, esta estructura tabular, la tabla es sólo un conjunto de punteros. Pero lo que los punteros señalar es conjetura qué? Una lista enlazada. ¿Y qué si tomamos lo mejor de ambos mundos? Nosotros usamos arrays para los índices iniciales en la estructura de datos por lo que al instante se puede ir a [0] [1], [30] o así sucesivamente, pero para que tengamos un poco de flexibilidad y podemos encajar Anita y Alice y Adam y cualquier otro Un nombre, en lugar de dejar que el otro eje crecer arbitrariamente. Y por último, a partir del lunes, tienen esa capacidad expresiva con lista enlazada. Se puede cultivar una estructura de datos arbitraria. Como alternativa, podríamos hacer una enorme variedad 2-dimensional, pero eso va a ser una situación terrible si una de las filas de una matriz 2-dimensional no es lo suficientemente grande como para que la persona adicional cuyo nombre pasa a comenzar con A. Dios nos libre de tener que reasignar un enorme 2-dimensional estructura sólo porque hay tantas personas nombradas A, especialmente cuando hay tan pocas personas nombradas algo Z. Es sólo va a ser una estructura de datos muy escasos. Así que no es perfecto, por cualquier medio, pero ahora al menos tenemos la capacidad para encontrar al instante en que Alice o Anita pertenece, al menos en términos del eje vertical, y entonces sólo tenemos que decidir dónde poner Anita o Alicia en el país de esta lista vinculada. Si no se preocupan por resolver las cosas, con qué rapidez podemos insertar Alice en una estructura como esta? Es tiempo constante. Nos índice en [0], y si no hay uno, Alice va al comienzo de la lista vinculada. Pero eso no es un gran negocio. Porque si Anita luego viene un cierto número de pasos más adelante, ¿de dónde Anita pertenece? Bueno, [0]. Programación orientada a objetos. Alice se encuentra en esa lista enlazada. Pero si no te importa la clasificación de estos nombres, que sólo puede moverse a través de Alice, insertar Anita, pero incluso eso es la constante de tiempo. Incluso si no hay Alice y Adam y todos estos otros nombres A, en realidad no es que cambiando físicamente. ¿Por qué? Debido a que acabamos de hacer aquí con lista enlazada, quién sabe fueron estos nodos son de todos modos? Todo lo que tienes que hacer es mover el pan rallado. Mueva las flechas alrededor, usted no tiene que mover físicamente los datos alrededor. Así que podemos insertar Anita, en ese caso, al instante. Constante de tiempo. Así que tenemos tiempo constante de búsqueda, y la constante de tiempo de inserción de alguien como Anita. Pero especie de simplificar en exceso el mundo. ¿Y si más adelante desea encontrar a Alice? ¿Y si más adelante desea encontrar a Alice? ¿Cuántos pasos se que va a tomar? [Respuesta Estudiantil, ininteligible] Exactamente. El número de personas antes de que Alicia en el país de la lista enlazada. Así que no es del todo perfecto, porque nuestra estructura de datos, una vez más, tiene este acceso vertical y entonces tiene estas listas enlazadas que cuelgan - en realidad, no hay que dibujarlo una matriz. Ha estas listas enlazadas colgando de ella que se parece un poco algo como esto. Pero el problema es que si Alice y Adam y todos estos otros nombres un terminan más y más allá, encontrar a alguien podría acabar teniendo un montón de pasos, bcause tienes que recorrer la lista enlazada, que es una operación lineal. Así que en realidad, entonces, el tiempo de inserción en última instancia es O (n), donde n es el número de elementos en la lista. Dividido por, vamos arbitrariamente llamamos m, donde m es el número de listas enlazadas que tenemos en este eje vertical. En otras palabras, si realmente suponen una distribución uniforme de los nombres, totalmente irreal. Obviamente hay más de unas cartas que otros. Pero si suponemos por el momento una distribución uniforme, y tenemos n personas en total, y las cadenas de m totales disponibles para nosotros, entonces la longitud de cada una de estas cadenas bastante simplemente va a ser el total, n dividido por el número de cadenas. Entonces n / m. Pero aquí es donde podemos ser matemáticamente todo listo. m es una constante, ya que hay un número fijo de éstos. Usted va a declarar el array al principio, y no estamos cambiando el tamaño del eje vertical. Por definición, que permanece fijo. Es sólo el eje horizontal, por así decirlo, eso está cambiando. Así que, técnicamente, es una constante. Así que ahora, el tiempo de inserción es más o menos O (n). Así que no se siente todo lo que mucho mejor. Pero, ¿qué es la verdad? Bueno, todo este tiempo, durante semanas, que hemos estado diciendo O (n ²). O (n), 2 x n ², - n, dividido por 2. . . ech. Es sólo ² n. Pero ahora, en esta parte del semestre, podemos empezar a hablar sobre el mundo real otra vez. Y n / m es absolutamente más rápido que sólo n solo. Si usted tiene mil nombres, y les rompen en cubos múltiples de modo que sólo tiene diez nombres en cada una de estas cadenas, buscando absolutamente diez cosas que va a ser más rápido que un millar de cosas. Y así, uno de los conjuntos de problemas futuros va a desafiar a pensar exactamente que a pesar de que, sí, asintóticamente y matemáticamente, esto es sólo lineal, que aspira, en general, cuando se trata de encontrar las cosas. En realidad, va a ser más rápido que el porque de este divisor. Así que hay de nuevo va a ser este trade-off y este conflicto entre la teoría y la realidad, y uno de los mandos comenzará a girar en este punto en el semestre es más bien la única realidad como una especie de preparación para la final semster, como se presenta el mundo de la programación web, donde realmente, el rendimiento va a contar porque los usuarios van a comienza a sentir y apreciar las malas decisiones de diseño. Entonces, ¿cómo usted va sobre la implementación de un vinculado - una tabla hash con 31 elementos? Y el ejemplo anterior fue arbitrariamente los cumpleaños. Si alguien tiene un cumpleaños el 1 de enero o el 1 de febrero, las pondremos en este cubo. Si se trata de 02 de enero, 2 de febrero, 2 de marzo, los vamos a poner en este cubo. Es por eso que tenía 31 años. ¿Cómo se declara una tabla hash? Puede ser muy simple, mesa * nodo es mi nombre arbitrario para él, [31]. Esto me da 31 punteros a nodos, y que me permite tener 31 punteros a listas enlazadas incluso si esas cadenas son inicialmente NULL. ¿Qué es lo que quiero hacer si quiero guardar "Alice", "Bob", "Charlie"? Bueno, tenemos que envolver las cosas en una estructura porque necesitamos Alice para que apunte a Bob, para que apunte a Charlie, y así sucesivamente. No podemos tener los nombres solos, por lo que podría crear una nueva estructura llamada nodo aquí. ¿Qué es un nodo real? ¿Qué es un nodo en esta nueva lista ligada? Lo primero, llamado palabra, es el nombre de la persona. LONGITUD, presumiblemente, se refiere a la longitud máxima del nombre de un ser humano, sea ​​lo que sea, 20, 30, 40 personajes en casos extremos locos, y uno es para qué? Es sólo el carácter NULL extra, \ 0. Así que este nodo está terminando "algo" dentro de sí misma, sino que también declara un puntero llamado próximo para que podamos cadena Alice a Bob a Charlie y así sucesivamente. Puede ser NULL, pero no necesariamente tiene que ser. Cualquier pregunta sobre estas tablas hash? ¿Sí? [Estudiante que hace la pregunta, ininteligible] Matriz - buena pregunta. ¿Por qué es esta palabra char en una matriz en lugar de sólo char *? En este ejemplo un tanto arbitrario, no quiero tener que recurrir a malloc para cada uno de los nombres originales. Yo quería declarar una cantidad máxima de memoria para la cadena para que yo pudiera copiar en la estructura Alice \ 0 y no tener que lidiar con malloc y libre y similares. Pero podría hacerlo si quería ser más conscientes del uso del espacio. Buena pregunta. Así que vamos a tratar de generalizar lejos de este y enfocar el resto de hoy en estructuras de datos más generalmente y otros problemas que se pueden resolver utilizando los mismos fundamentos a pesar de que las estructuras de datos se pueden diferir en sus pormenores. Así que resulta en ciencias de la computación, los árboles son muy comunes. Y se puede pensar en una especie de árbol como un árbol genealógico, donde hay algunas raíces, algunos matriarca o patriarca, abuela o el abuelo o la espalda antes, debajo de la cual son mamá y papá o hermanos diferentes o similares. Así que una estructura de árbol tiene nodos y tiene hijos, normalmente 0 o más hijos de cada nodo. Y algunos de la jerga que usted ve en este dibujo aquí es cualquiera de los hijos o nietos pequeños en los bordes que no tienen flechas que emanan de ellos, esas son las hojas llamados, y cualquier persona en el interior es un nodo interno, se le puede llamar cualquier cosa por el estilo. Sin embargo, esta estructura es bastante común. Éste es un poco arbitraria. Tenemos un niño de la izquierda, tenemos tres hijos a la derecha, dos niños en la parte inferior izquierda. Así que podemos tener diferentes árboles de tamaño, pero si empezamos a normalizar las cosas, y se puede recordar este vídeo de Patricio, en la búsqueda binaria de un corto anterior búsqueda en línea, binario no tiene que ser implementado con una matriz o trozos de papel en una pizarra. Supongamos que desea almacenar los números en una estructura de datos más sofisticada. Se puede crear un árbol como éste. Podría tener un nodo declara en C, y que el nodo puede tener al menos dos elementos de su interior. Uno de ellos es el número que desea almacenar, y el otro es - bueno, necesitamos uno más. Los otros son sus hijos. Así que aquí está otra estructura de datos. Esta vez, un nodo se define como el almacenamiento de un número n y luego dos punteros, hijo izquierdo y el hijo derecho. Y no son arbitrarias. Lo que es interesante acerca de este árbol? ¿Cuál es el patrón en la forma en que hemos establecido esto o cómo Patrick se presenta en su video? Es bastante obvio que hay una clasificación que pasa aquí, pero ¿cuál es la regla simple? ¿Sí? [Respuesta Estudiantil, ininteligible] Perfecto. Si usted echa un vistazo a esto, verá los números pequeños a la izquierda, los grandes números de la izquierda, pero eso es cierto para cada nodo. Para cada nodo, su hijo izquierdo menor que él, y su hijo mayor derecho que él. Lo que esto significa es que si quiero buscar en esta estructura de datos para, por ejemplo, el número 44, Tengo que empezar desde la raíz, porque al igual que con todas estas estructuras de datos más complejas ahora, sólo tenemos un puntero a una sola cosa, el principio. Y en este caso, el principio es la raíz. No es el extremo izquierdo, que es la raíz de esta estructura. Así que veo aquí es de 55 años, y estoy buscando 44. En qué dirección quiero ir? Bueno, yo quiero ir a la izquierda, porque, obviamente, a la derecha va a ser demasiado grande. Así que notar aquí, estás de suerte conceptualmente cortar el árbol por la mitad porque nunca vas abajo a la derecha. Así que ahora me iré de la 55 a la 33. Es demasiado pequeño de un número. Estoy buscando a 44, pero ahora sé que si 44 es en este árbol, puedo ir, obviamente, a la derecha. Así que de nuevo, estoy podando el árbol por la mitad. Es casi idéntico conceptualmente a la guía telefónica. Es idéntico a lo que hicimos con los papeles en la pizarra, pero es una estructura más sofisticada que nos permite hacer realidad este divide y vencerás por diseño del algoritmo, y, de hecho, que atraviesa una estructura como esta - gritos. Atravesando una estructura como esta, donde es sólo "ir por este camino o ir por ese camino" significa todo el código que se inclinó a su mente en un primer momento, al ponerla en la sección o caminar a través de él en casa, para la búsqueda binaria, utilizando recursión o iteración, es un dolor en el cuello. Busque el elemento central, a continuación, hacer su redondeo hacia arriba o hacia abajo. Hay una belleza en esto porque ahora podemos utilizar la recursividad de nuevo, pero mucho más limpia. De hecho, si usted está en el número 55 y que desea encontrar 44, usted va a la izquierda en este caso, entonces, ¿qué hace usted? Usted corre el mismo algoritmo exacto. Se comprueba el valor del nodo, vaya a la izquierda oa la derecha. A continuación, compruebe el valor del nodo, vaya a la izquierda oa la derecha. Esto se adapta perfectamente a la recursividad. Así que, aunque en el pasado hemos hecho algunos ejemplos bastante arbitrarias que implican recursión que no tenía por qué ser recursivo, con stuctures de datos, especialmente los árboles, es una perfecta aplicación de esta idea de tener un problema, contracción, y luego resolver el mismo tipo de, pero más pequeño programa,. Así que hay otra estructura de datos que podemos introducir. Éste está diseñado a primera vista, parecer críptico, pero esto es increíble. Así que esta es una estructura de datos llamada trie, trie, que se hereda de la recuperación de palabras, que no se pronuncia re-try-val, pero eso es lo que el mundo llama a estas cosas. Trata. T-r-i-e. Se trata de una estructura de árbol de algún tipo, pero cada uno de los nodos en un trie parece ser qué? Y esto es un poco engañoso, ya que es una especie de abreviado. Pero parece que cada nodo en este trie es en realidad una matriz. Y a pesar de que el autor de este diagrama no lo ha demostrado, en este caso, este trie es una estructura de datos cuyo propósito en la vida es para almacenar palabras como A-l-i-c-e o B-o b-. Y la forma en que estos datos almacena Alice y Bob y Charlie y Anita y demás Se utiliza una matriz para almacenar el cual Alicia en el país de un trie, se comienza en el nodo raíz que se parece a una matriz, y que ha sido escrito en notación abreviada. El autor omite abcdefg porque no había nombres con eso. Ellos sólo mostró M y P y T, pero en este caso, vamos a pasar lejos de Alice y Bob y Charlie a algunos nombres que están aquí. Maxwell es en realidad en este diagrama. Entonces, ¿cómo hizo el autor tienda M-a-x-w-e-l-l? Él o ella empezó en el nodo raíz, y se fue a [M], de modo más o menos 13, la 13 ª posición en la matriz. Luego, desde allí, hay un puntero. Un puntero que lleva a otra matriz. A partir de ahí el autor indexada en esa matriz en la posición A, como se muestra en la parte superior izquierda hay, y entonces él o ella siguió a ese puntero a otra matriz, y se fue al puntero en la ubicación X. Luego, en la siguiente ubicación matriz W, E, L, L, y así sucesivamente, y, por último, vamos a tratar de poner en realidad una imagen a esta. ¿Cómo es un nodo como en el código? Un nodo en un trie contiene una matriz de punteros a más nodos. Pero también hay que ser algún tipo de valor booleano, por lo menos en esta implementación. Sucede que me llaman is_word. ¿Por qué? Porque cuando vas a insertar Maxwell, usted no está insertando nada en esta estructura de datos. No estás escribiendo M. No estás escribiendo X. Todo lo que estamos haciendo es seguir punteros. El puntero que representa M, entonces el puntero que representa A, a continuación, el puntero que representa X, entonces W, E, L, L, pero lo que hay que hacer al final es una especie de ir, pasar, llegué a este lugar. Había una palabra que termina aquí, en la estructura de datos. Entonces, ¿qué es realmente un trie llena y el autor eligió para representar estas estaciones terminales con pequeños triángulos. Esto sólo significa que el hecho de este triángulo está aquí, este valor booleano de true significa que si usted va hacia atrás en el árbol, lo que significa una palabra llamada Maxwell está en esto. Pero la palabra foo, por ejemplo, no está en el árbol, porque si me pongo en el nodo raíz hasta aquí en la parte superior, No hay ningún indicador f, o no puntero, puntero o no. Foo no es un nombre en este diccionario. Pero por el contrario, Turing, t-u-r-i-n-g. Una vez más, no almacenar o u t o r i o n o o g. Pero lo hice tienda en esta estructura de datos un valor de verdadero camino aquí en este nodo - en el árbol estableciendo este valor booleano de is_word en true. Así que un trie es una especie de esta estructura meta muy interesante, donde usted no está realmente almacenar las palabras mismas de este tipo de diccionario. Para que quede claro, sólo estás almacenando sí o no, hay una palabra que termina aquí. Ahora, ¿cuál es la implicación? Si tiene 150.000 palabras en un diccionario que usted está tratando de almacenar en la memoria usando algo como una lista enlazada, usted va a tener 150.000 nodos en la lista enlazada. Y encontrar una de esas palabras alfabéticamente podría tomar O (n) tiempo. El tiempo lineal. Pero en el caso aquí de un trie, ¿cuál es el tiempo de duración de la búsqueda de una palabra? Resulta que la belleza aquí es que incluso si usted tiene ya 149.999 palabras en este diccionario, tal como se aplica con esta estructura de datos, ¿cuánto tiempo se tarda en encontrar o insertar una persona más en eso, como Alice, Alice? Bueno, es sólo 5, tal vez 6 pasos para el carácter final. Debido a que el presense de otros nombres en la estructura no ponerse en el camino de la inserción de Alice. Por otra parte, la búsqueda de Alice vez hay 150.000 palabras en este diccionario no ponerse en su camino de búsqueda de Alice en absoluto, porque Alice es. . . . . aquí, porque me encontré con un valor booleano. Y si no hay valor booleano verdadero, entonces Alicia no está en esta estructura de datos de palabras. En otras palabras, el tiempo de ejecución de encontrar cosas y la inserción de las cosas en este nuevo estructura de datos del trie es de O - no es n. Debido a que el presense de 150.000 personas no tiene efecto en Alice, parece. Así que vamos a llamarlo k, donde k es la longitud máxima de una palabra en Inglés que es típicamente no más de 20-algo caracteres. Así que k es una constante. Así que el Santo Grial parece que hemos encontrado ahora es la de un tiempo trie, constante para las inserciones, para las búsquedas, para las deleciones. Debido a que el número de cosas que ya están en la estructura, que ni siquiera son físicamente allí. Una vez más, son sólo una especie de marcado, sí o no, no tiene impacto en su tiempo de funcionamiento futuro. Pero tiene que haber una trampa, de lo contrario no habría perdido tanto tiempo en todas estas estructuras de datos sólo para finalmente llegar a la un secreto que es increíble. Entonces, ¿qué precio estamos pagando para alcanzar esta grandeza en esta lista? Espacio. Esta cosa es enorme. Y la razón de que el autor no lo presentamos aquí, note que todas estas cosas que se parecen a las matrices, no sacó el resto del árbol, el resto de la trie, porque no son sólo relevantes para la historia. Pero todos estos ganglios son super amplia, y cada nodo en el árbol de toma 26 o en realidad, podría ser 27 caracteres porque en este caso yo estaba con espacio para que el apóstrofe para que podamos tener palabras apostrofó. En este caso, se trata de amplias gamas. Así que, aunque no están picutured, esto toma una cantidad masiva de RAM. Lo que podría estar bien, especilly en hardware moderno, pero esa es la compensación. Tenemos menos tiempo por el gasto de más espacio. Entonces, ¿dónde está todo esto va a ir? Bueno, vamos a hacer - vamos a ver aquí. Vamos a hacer un salto a este tipo aquí. Lo creas o no, tan divertido como C ha sido por algún tiempo, estamos llegando a un punto en el semestre en que es el momento de hacer la transición a las cosas más modernas. Las cosas en un nivel superior. Y a pesar de que durante el próximo par de semanas todavía nos siguen nos sumergimos en el mundo de los punteros y la gestión de memoria para conseguir que la comodidad con la que se puede construir, el final del juego es en última instancia a introducir, irónicamente, no esta lengua. Pasaremos, como 10 minutos hablando sobre HTML. Todos HTML es un lenguaje de marcas, y lo que es un lenguaje de marcas Es esta serie de corchetes abiertos y cerrados soportes que dicen "hacer esta audaz" "Hacer esto" cursiva "hacer esta centrada. No es todo lo que intelectualmente interesante, pero es muy útil. Y sin duda es omnipresente en estos días. Pero lo que es de gran alcance sobre el mundo de HTML y programación web en general, está construyendo cosas dinámicas, escribir código en lenguajes como PHP o Python o Ruby o Java o C #. En definitiva, sea cual sea su idioma de elección es, y generar HTML dinámicamente. Generación de algo llamado CSS dinámicamente. Hojas de estilo en cascada, que es también la estética. Y así, a pesar de que, hoy en día, si voy a algún sitio web Google.com como el familiar, y voy a ver, desarrollador, ver código fuente, lo que tal vez usted ha hecho antes, pero vamos a ver el código fuente, esto probablemente se ve bastante críptico. Pero este es el código subyacente que implementa Google.com. En la parte delantera. Y en realidad todo esto es materia estética suave y esponjosa. Este es el CSS aquí. Si mantengo el desplazamiento hacia abajo vamos a conseguir algunas cosas con códigos de color. Esto es HTML. Código de Google parece un lío, pero si realmente abrir una ventana diferente, podemos ver cierta estructura a esta. Si abro esto, notar aquí, que es un poco más legible. Vamos a ver dentro de poco esta etiqueta, [palabra] es una etiqueta, HTML, cabeza, cuerpo, div, la escritura, el área de texto, la anchura, centrada, div. Y esto es también una especie de misterioso aspecto a primera vista, pero todo este lío sigue ciertos patrones y los patrones repetibles, de modo que una vez que tengamos los fundamentos abajo, usted será capaz de escribir código como este y luego manipular código como este usando otro lenguaje, llamado JavaScript. Y JavaScript es un lenguaje que se ejecuta dentro de un navegador hoy que utilizamos en los cursos de la Universidad de Harvard, por supuesto, comprar la herramienta que utiliza Google maps para darle un montón de dinamismo, Facebook te da para mostrar actualizaciones instantáneas de estado, Twitter se utiliza para mostrar mensajes de twitter instante. Todo esto, comenzaremos a sumergirnos pulg Pero para llegar allí, tenemos que entender un poco sobre el Internet. El vídeo aquí es sólo un minuto de duración, y vamos a suponer por ahora esto es, de hecho, cómo funciona Internet como un teaser de lo que está por venir. Te doy "Guerreros de la Red". [♫ ♫ música lenta coro] [Narrador] Él vino con un mensaje. Con un protocolo de todos los suyos. [♫ ♫ música electrónica más rápida] Él vino a un mundo de firewalls fresco, despreocupado routers, y los peligros mucho peores que la muerte. Es rápido. Es fuerte. Él es TCP / IP, y tiene su domicilio. Los guerreros de la red. [Malan] La semana que viene, entonces. La Internet. Programación web. Esto es CS50. [CS50.TV]