>> DAVID MALAN: Muy bien.
Bienvenido de nuevo a CS50.
Este es el comienzo de la semana 8.
Y recordemos que problemas 5 terminado con un poco de un desafío.
Así que asumiendo que usted ha recuperado la totalidad de su Teaching Fellows y fotografías de CA
en el archivo card.raw, usted es elegible que ahora se encuentran todas esas personas, y
un afortunado ganador será regresar a casa con una de estas cosas, el movimiento de salto
dispositivo que se puede utilizar para la final de proyectos, por ejemplo.
>> Este, cada año, lleva a un poco de creepiness.
Y así lo que yo pensé que iba a hacer es compartir con ustedes algunas de las notas que tienen
ido adelante y atrás sobre la lista de personal en los últimos tiempos.
Por ejemplo, anoche, cita fin de la cita, de uno de los del personal
miembros, "Acabo de tener un golpe estudiante a mi puerta para hacer una foto conmigo.
Los acosadores, les digo. "Empezó, bastante descriptivo y luego nos mudamos
a, una hora más tarde, "Yo tenía un estudiante me espera después de la sección
y tenía todos nuestros nombres y fotos en algunas hojas de papel. "Muy bien.
Así organizada, pero no todo lo que todavía espeluznante.
>> Entonces, "Yo estaba fuera de la ciudad este fin de semana, y cuando volví, había uno en
mi
dormitorio ". [Risas]
DAVID MALAN: Próxima cita de un personal miembro ", un estudiante vino a mi casa a las
Somerville a las 4 am de esta mañana. "Next personal: "Yo llegué a mi hotel en San
Francisco y un estudiante estaba esperando mí en el hall de entrada con tres cámaras réflex digitales. "
Tipo de cámara.
"Ni siquiera estoy en el personal de este semestre, pero un estudiante entró a mi casa esta
mañana y registrado todo el asunto con Google Glass. "Y luego, por último,
"Por lo menos 12 personas fueron ávidamente esperando por mí cuando salí de mi
limo, y luego me
despertó. "Muy bien.
Así que entre las fotografías, ya que puede recordar, es este hombre aquí, que os
podría saber como Milo Banana, que vive con Lauren Carvalho, nuestra cabeza
Teaching Fellow.
Milo, Milo, ven aquí chico.
Milo.
Eso sí, él está usando Google Glass, por lo le mostraremos todo esto después.
Así que esto es Milo si usted desea tomar una fotografía con él después.
Si desea buscar a la audiencia allí.
Aceptar.
Eso es bueno metraje.
Bueno, Milo plátano.
Oh, no hagas eso.
>> [Risas]
>> Aceptar.
Así que una palabra a continuación, en lo que se avecina, porque a medida que empezamos a la transición,
esta semana específicamente, de C en un entorno de línea de comandos para PHP y
JavaScript y SQL y HTML y CSS en un entorno basado en web, estaremos
y te equipa con todo el más conocimiento para
potenciales proyectos finales.
Con ese fin, el curso tiene una tradición de la celebración de seminarios que
son sobre temas tangenciales al curso.
Muy relacionado con la programación y para desarrollo de aplicaciones y así sucesivamente, pero
no explorado necesariamente por propio plan de estudios del curso.
>> Así que si usted podría estar interesado en una o más de los seminarios de este año,
registrarse en cs50.net/seminar.
Hay seminarios mayores en cs50.net/seminars.
Y en la lista hasta el momento para este año Web Apps son increíbles con Ruby on
Rails, que es una alternativa lenguaje PHP.
Lingüística Computacional.
Introducción a la IOS, que es el plataforma que se utiliza para el iPhone y el
desarrollo iPad.
JavaScript para Aplicaciones Web, vamos a cubrir eso, sino que en este seminario, que irá
en más detalles.
>> Salto de movimiento, así que en realidad va a tener un poco de de nuestros amigos de Salto Movimiento,
la propia empresa, se unan a nosotros.
Mañana, de hecho, para proporcionar un seminario práctico, si
de interés para usted.
Meteor.js, una técnica alternativa para usando JavaScript no en un navegador,
pero en un servidor.
Node.js, que es en gran medida en ese sentido también.
Diseño elegante Android.
Siendo Android una alternativa muy popular para iOS y Windows Phone
y otras plataformas móviles.
Y Seguridad Active Web Defensa.
>> Así que de hecho, si usted desea a participar en esto, déjame
tome nota de esto.
Estamos muy felices de decir que nuestros amigos de Salto
Movimiento, que es un inicio -
este dispositivo realmente acaba de llegar hace unos meses -
ha donado graciosamente 30 de estos dispositivos a la clase por tantos estudiantes, si
desea pedir prestado el hardware hacia el final del semestre y utilizarlo para
un proyecto final real.
Apoyan a varios idiomas.
Ninguno de ellos C, ninguno de ellos PHP, así realizar uno o más de estos seminarios
podría resultar de interés.
Y todos ellos será filmado en el caso de que usted no es capaz
asistir en persona.
El horario será anunciado a través de correo electrónico a medida que consolidamos habitaciones.
>> Y por último, si usted va a projects.cs.50.net, este es un sitio web
mantenemos cada año que invitemos gente de la comunidad, profesores,
departamentos, personal, y tanto en el exterior del CS50 a
proponer ideas de proyectos.
Actividades de interés para los grupos de estudiantes.
Actividades de interés para los departamentos.
Así que vuelta allí si usted está luchando la incertidumbre en cuanto a lo que
usted le gustaría abordar.
>> Así que la última vez que presentamos una duda estructura de datos más compleja de lo que habíamos
visto en semanas pasado.
Habíamos estado usando arrays bastante felizmente como un útil si
estructura de datos simplista.
Entonces introdujimos estos, que por supuesto están vinculados listas.
Y lo que fue una de las motivaciones para la introducción de esta estructura de datos?
¿Sí?
¿Qué es eso?
>> AUDIENCIA: Dynamic tamaño.
>> DAVID MALAN: Dynamic tamaño.
Así, mientras que en la matriz, lo que tiene que conocer su tamaño con anticipación cuándo
asigna él.
En lista enlazada, no lo sabes tiene que saber eso.
Usted puede simplemente malloc, o más en general, asignar otros
nodo, por así decirlo, cada vez que desee insertar más datos.
Y nodo no ha predeterminado significado.
Es sólo un término genérico que describe algún tipo de contenedor que estamos
utilizando en nuestra estructura de datos para almacenar algún artículo de interés, que en este
caso resultan ser números enteros.
>> Pero siempre hay una solución de compromiso.
Así que llegamos tamaños dinámicos de los datos estructura, pero qué precio pagamos?
¿Cuál es el lado negativo de las listas enlazadas?
¿Sí?
>> AUDIENCIA: Requiere más memoria.
>> DAVID MALAN: Requiere más memoria, ¿cómo exactamente?
>> AUDIENCIA: [inaudible].
>> DAVID MALAN: Exactamente.
Así que ahora que hemos punteros ocupar memoria adicional que previamente
no era necesario, porque la ventaja de una matriz, por supuesto, es que
todo está contigua, de vuelta de espalda con espalda, lo que
le da acceso aleatorio.
Porque sólo mediante el uso de corchetes notación, o más técnicamente puntero
aritmética, adición muy simple, se puede acceder a cualquier
elementos en tiempo constante.
Y de hecho, eso es un poco haciendo alusión a otro precio que estamos pagando con un
lista enlazada.
>> ¿Qué sucede con el tiempo de ejecución de algo así como la búsqueda, si quiero
encontrar algo de valor y en el interior de una lista enlazada?
Lo que se convierte en mi tiempo de ejecución?
Big O de n.
Si se ordena a?
¿Qué pasa si ordenado de la estructura de datos?
¿Puedo hacer algo mejor que grande O de n para la búsqueda?
No, porque en el peor de los casos podría muy bien ser ordenados, pero el número
usted está buscando podría ser grande.
Puede ser que sea el número 100, que que podría pasar a ser todo
la forma en el extremo.
Y debido a que sólo se puede acceder a una ligada lista de esta aplicación por
camino de su primer nodo, eres todavía un poco fuera de suerte.
Usted tiene que atravesar todo el asunto de principio a fin con el fin de encontrar
ese gran valor, como 100.
O, para determinar si es ni siquiera existe.
>> Así que no podemos hacer lo que en un algoritmo de datos estructura que se parece a esto?
No podemos hacer la búsqueda binaria, porque búsqueda binaria requiere que teníamos
de acceso aleatorio.
Podríamos saltar de un lugar a ubicación sin tener que seguir
estas migas de pan en forma de todos estos indicadores.
>> Ahora, ¿cómo implementamos esto?
Bueno, si vamos a la pantalla de aquí, si podemos volver a implementar rápidamente estos datos
estructura -
mi escritura no es tan muy bien aquí, pero lo intentaremos.
Así struct typedef, y lo que hizo que quiere llamar a esta cosa aquí?
Nodo.
Así que voy a que podamos empezar.
Y ahora, ¿qué tiene que estar dentro del la estructura de datos para que individualmente
lista enlazada?
¿Cuántos campos?
>> Así que dos.
Uno de ellos es bastante fácil.
Así int n.
Y podríamos llamar n todo lo que queramos, pero debe ser un int si estamos
la implementación de una lista enlazada para ints.
Y ahora lo que hace el segundo campo tiene que ser?
Struct nodo *.
Así que si lo hago struct nodo *, y luego me puede llamar a esto también lo que yo quiera,
pero para que quede claro que llamaré lo siguiente, ya que hemos estado haciendo.
Y luego voy a cerrar mis llaves.
>> Y ahora, como la última vez, Puse nodo aquí abajo.
Pero si estoy declarando esto es como un nodo, ¿por qué me molesto estar tan
verbose aquí en declarar struct nodo * siguiente, en contraposición
al nodo sólo * siguiente?
¿Sí?
>> AUDIENCIA: [inaudible].
>> DAVID MALAN: Exactamente.
Exactamente.
Debido C realmente te lleva literalmente y sólo ve la definición de nodo
hasta aquí, no se puede referirse a ella aquí.
Así que tenemos esta clase de preventivo declaración aquí, que es reconocidamente
más detallado.
Nodo de estructura, que los medios ahora podemos acceder a ella
en el interior de la estructura de datos.
>> Y en un aparte, porque se trata de cada vez un poco más subjetiva ahora,
la estrella técnicamente puede ir aquí, puede ir aquí, puede
incluso ir en el medio.
Hemos adoptado, en la guía de estilo para el curso, la convención de poner
la estrella junto a los datos escriba, que en este caso,
sería nodo de estructura.
Pero darse cuenta de una gran cantidad de libros de texto y referencias en línea, es posible que de hecho
ver que en el otro lado.
Pero sólo se dan cuenta de que tanto en realidad trabaja y debe ser simplemente
consistente.
>> Está bien.
Así que esa fue nuestra declaración del nodo de estructura.
Pero luego empezamos a hacer más cosas sofisticadas.
Por ejemplo, decidimos introducir algo así como una tabla hash.
Así que aquí es una tabla hash de tamaño n, indexada desde 0 en la parte superior izquierda de n
menos 1 en la parte inferior izquierda.
Esto podría ser un hash mesa para nada.
Pero, ¿qué tipo de cosas qué hablamos sobre el uso de una tabla hash para?
Almacenamiento de qué?
>> Nombres.
Podríamos hacer nombres como hicimos la última vez.
Y realmente, puede almacenar cualquier cosa.
Y vamos a ver esto de nuevo en PHP y JavaScript.
Una tabla hash es una buena especie de Suiza Navaja que le permite almacenar
casi todo lo que quieras dentro de que mediante la asociación de teclas con los valores.
Teclas con valores.
>> Ahora en este caso sencillo, nuestra claves son sólo números.
Estamos implementando un hash tabla como una matriz.
Y así las claves son 0, 1, 2, y así sucesivamente.
Y así, nosotros, como seres humanos, decidió el pasado semana que usted sabe qué, si estamos
va a almacenar nombres, vamos a arbitrariamente, pero bastante razonable,
asumir que Alice, un nombre de A, se acaba de ser indexados en 0.
Y Bob, un nombre de B, se indexará en 1, y así sucesivamente.
Así que tuvimos una correspondencia entre las entradas, que son cadenas, y el hash
lugares, que son números.
>> Por lo tanto ese proceso se conoce generalmente como una función de hash, y usted realmente puede
implementarlo en el código.
Si quisiera aplicar una función hash que hace exactamente lo que
se acaba de describir de la última vez, yo podría declarar una función que toma como
de entrada, por ejemplo -
y vamos a hacer esto en este pantalla aquí.
Si quisiera aplicar un hash función, yo podría decir
algo como esto.
>> Se va a devolver un int.
Va a ser llamado hash, y es va a aceptar como argumento una
cadena, o podemos ser más apropiado ahora, y decir char *, que llamaremos s.
Y entonces todo esta función tiene que ver, en última instancia, es devolver un int.
Ahora, cómo lo hace que el poder no ser tan clara.
Voy a poner en práctica esto sin ninguna forma de comprobación de errores en estos momentos.
Yo sólo voy a decir a ciegas, el retorno lo que esté a escuadra s 0, menos,
digamos, la capital un punto y coma.
>> Totalmente roto.
No es perfecto, porque uno, lo que si s es nulo?
Las cosas malas van a suceder.
Dos, ¿y si la primera letra en este nombre no es una letra mayúscula?
Eso no va a girar bien tampoco.
Puede ser que sea una letra minúscula o no una carta a todos.
Así que totalmente margen de mejora, pero esta es la idea básica.
>> Lo que describimos la semana pasada verbalmente como sólo un proceso de asignación de Alice a
0 y Bob a 1 se puede expresar ciertamente más formulaically como C
funcionar aquí.
Llamé de nuevo hash, toma una cadena como de entrada, y entonces de alguna manera hace algo
con esa entrada para producir una salida.
No muy diferente de nuestra descripción cuadro negro lo que hemos hecho siempre.
No sé cómo podría ser trabajo debajo de la capucha.
>> Para problemas 6, uno de los retos es para que usted decida qué
Será su función hash?
¿Qué va a estar dentro de ese negro caja, y, presumiblemente, va a ser un
poco más interesante que esto, y definitivamente más propenso a errores
comprobar que este particular, aplicación.
>> Pero pueden surgir problemas, ¿verdad?
Si tenemos una estructura de datos como este uno, lo que es uno de los problemas
se puede ejecutar en el transcurso del tiempo a medida que inserta más y más nombres en la
la tabla de hash?
Usted consigue colisiones, ¿verdad?
¿Qué pasa si usted tiene Alice y Aarón, dos personas cuyos nombres sucedido
comenzar con A?
Esto plantea la pregunta, en la que poner la segunda como un nombre?
>> Bueno, tal vez ingenuamente, sólo hay que poner donde Bob pertenece, pero Bob es
tipo de atornillado si intenta inserte su nombre al lado y
no hay sitio para él.
Así que se podría poner Bob dónde está Charlie, y se puede imaginar esto muy rápidamente
delegar en un poco de un desastre.
Algo lineal en el final, donde se sólo hay que buscar todo el asunto
en busca de Alice o Bob o Aaron o Charlie.
>> Así que en lugar hemos propuesto, en lugar de linealmente el sondeo de espacios abiertos
y dejándose los nombres allí, propuesto un enfoque más elegante.
Una tabla hash implementado todavía con un array de índices, pero el tipo de datos de
esos índices ya eran punteros.
Punteros a qué?
Punteros a las listas enlazadas.
>> Porque recordemos que una lista enlazada es en realidad sólo un puntero a un nodo, y
el nodo tiene un campo siguiente, y que el nodo tiene un campo siguiente, y así sucesivamente.
Así que ahora puede pensar en este conjunto de el lado de la mano izquierda de una tabla hash como
que conduce a una lista enlazada.
La ventaja de que es si usted consigue un colisión entre Alice y Aarón,
¿qué hacer con el segunda de estas personas?
Sólo le conceden a la final, o incluso el principio
de esa lista enlazada.
>> Y, de hecho, vamos a través de fideos que por sólo un segundo.
¿Dónde tendría la mayoría del sentido?
Si inserto Alice y ella termina en el primer lugar, entonces yo trato de
inserte el nombre de Aarón, y no hay obviamente una colisión, debo poner
él al principio de la lista enlazada?
Eso es por lo que la primera ubicación, o al final?
>> AUDIENCIA: [inaudible].
>> DAVID MALAN: OK.
He oído que comienza.
¿Por qué al principio?
>> AUDIENCIA: [inaudible].
>> DAVID MALAN: OK.
Es alfabético, por lo que es bueno.
Esa es una buena propiedad.
Se me va a ahorrar un poco de tiempo potencialmente.
No me deja hacer búsqueda binaria, pero podrían al menos ser capaz de romper
de un bucle si me doy cuenta, bueno, estoy camino pasado fueron Aarón sería en este
ordenados lista enlazada.
Yo no tengo que perder el tiempo buscando todo el camino hasta el final.
Así que eso es razonable.
¿Por qué más podría querer insertar el nombre de chocar en la
principio de la lista?
¿Qué es eso?
>> AUDIENCIA: [inaudible].
>> DAVID MALAN: Podría tomar mucho tiempo para llegar a la final de la lista.
Y, de hecho, más y más.
Cuantos más nombres que se insertan comenzar con A, el más largo que
la cadena se va a poner.
Cuanto más tiempo que enlazada lista se va a conseguir.
Así que usted es realmente justo perdiendo el tiempo.
Tal vez usted es mejor de mantener tiempo de inserción constante, gran O de 1,
poniendo siempre el nombre de chocar en el principio de la lista enlazada,
y no preocuparse tanto acerca de la ordenación.
>> ¿Cuál es la mejor respuesta?
No está claro.
Es algo que depende de lo que el distribución es, cuál es el patrón
de los nombres que va a insertar.
No es necesariamente una respuesta obvia.
Pero aquí, de nuevo, es una oportunidad de diseño.
>> Así que a continuación analizamos esta cosa, que es realmente la otra gran oportunidad
de p-set 6.
Y me di cuenta, si no lo ha hecho, Zamyla sumerge en ambos, el hash
mesas y países, en más detalle.
Y el video guía se incrustado en p-establecer especificaciones.
Este era un trie -
T-R-I-E. Y lo que era interesante de esto fue que el tiempo de ejecución
de la búsqueda de un nombre, como Maxwell la última vez, era gran O de qué?
¿Qué es eso?
>> AUDIENCIA: El número de letras.
>> DAVID MALAN: Número de letras.
Escuché dos cosas.
Número de letras y constante de tiempo.
Así que vamos a ir con eso primero.
El número de letras.
Pues bien, esta estructura de datos, recuperación, es como un árbol, un árbol de la familia, cada uno de
cuyos nodos se componen de matrices.
Y esos arreglos son apuntadores a otros tales nodos u otros tales
matrices en el árbol.
>> Así que si queríamos luego determinar si Maxwell está aquí dentro, yo podría ir
a la primera serie, en la parte superior de el árbol, la raíz de la llamada, la parte superior de
trie y, a continuación, siga el puntero del m, entonces el un puntero, entonces x,
w, e, l, l.
Y entonces, cuando veo algún símbolo especial, denotada aquí como un triángulo.
En el código verás que proponemos que implementado como un bool, sólo decir que sí
o no, una palabra se detiene aquí.
>> Bueno, una vez que hemos ido a la M-A-X-W-E-L-L, se siente como siete, tal vez
ocho si vamos un pasado, ocho pasos para encontrar Maxwell.
¿O vamos a llamarlo K. Pero recuerdan el pasado tiempo, sostuve que si hay
realista una longitud máxima en un palabra, como 40 y tantos y tantos personajes, un
longitud máxima implica un valor constante.
Así que en realidad, sí, es técnicamente gran O de 8 o 7, o en realidad gran O de K. Pero
si hay una tapa finito en lo K podría ser, es una constante.
Y lo que es gran O de 1 a el final del día.
>> No en el mundo real.
No cuando usted realmente empezar a ver el reloj como correr de su programa.
Está absolutamente va a ser un poco más lento que verdaderamente constante
tiempo con un solo paso.
Va a ser siete u ocho pasos, pero eso es mucho, mucho mejor
de un algoritmo como el gran O de n que depende del tamaño de lo que hay en el
estructura de datos.
>> Observe el alza aquí es que podemos insertar un millón más nombres en esta
estructura de datos, pero la cantidad de pasos más es que va a llevarnos a encontrar
Maxwell, en ese caso?
Ninguno.
Es afectado.
Y hasta la fecha, no creo que hemos visto un ejemplo de una estructura de datos o un
algoritmo que era completamente afectado por externa
conductas como esas.
Pero esto no puede ser increíble.
Esto no puede ser la única solución para el p-set
>> Y no lo es.
Esto no es necesariamente los datos estructura que debe gravitar hacia,
porque las tablas hash como, equilibrio.
¿Cuál es el precio que se paga aquí?
Memoria.
Quiero decir, este es un atroz cantidad de memoria.
Y no se puede ver bien aquí porque el autor de esta imagen
obviamente truncado todos los arrays, y no estamos viendo un montón de doctores y
B y C de Q y de e Y de y de Z en estas matrices.
Pero están ahí.
>> Cada uno de estos nodos es toda una serie de algunos 26 o más bytes, cada uno de
lo que representa una letra.
27 en nuestro caso, por lo que podemos apoyar apóstrofes en el problema establecido.
Así que esta estructura de datos es realmente, muy densa y amplia.
Y eso solo podría terminar la desaceleración las cosas, o al menos le cuesta un
mucho más espacio.
Pero una vez más, podemos sacar comparaciones aquí.
>> Recordemos hace un tiempo, hemos logrado mucho más emocionante tiempo de funcionamiento en la clasificación
cuando usamos la combinación de estilo, pero el precio que pagamos para lograr n log n de fusión
especie requiere que pasemos más lo que los recursos?
Más espacio.
Necesitábamos una matriz secundaria a copiar a la gente a, al igual que
que hicimos aquí en el escenario.
Así que de nuevo, no hay claros ganadores, pero sólo el diseño subjetiva
decisiones que tomar.
>> Está bien.
Así que ¿qué tal esto?
Cualquier persona reconoce que D-Hall?
Aceptar.
Así que tres de nosotros lo hacemos.
Mather House.
Así que esto es para una cena de Mather.
Apuesto a todos los comedores tienen pilas de bandejas les gusta esto.
Y esto es realmente representativa de algo que hemos
obviamente ya visto.
Lo llamamos literalmente una pila.
Y la pila, en términos de su la memoria de la computadora, es que los datos se
mientras que las funciones están siendo llamados.
>> Por ejemplo, ¿qué tipo de cosas van en la pila con respecto a la
diseño de la memoria que hemos discutido en semana pasado?
¿Qué es eso?
>> AUDIENCIA: Las llamadas a funciones.
>> DAVID MALAN: lo siento.
>> AUDIENCIA: Las llamadas a funciones.
>> DAVID MALAN: Las llamadas a funciones, pero en concreto, lo que hay dentro de cada uno de
esos cuadros?
¿Qué tipo de cosas?
Sí.
Por lo tanto las variables locales.
Cada vez que necesitábamos algo de almacenamiento local, como un argumento, o int i, o int
temp, o lo que sea lo local variable es, hemos estado
poner que en la pila.
Y lo llamamos una pila porque de esa idea de estratificación.
Sólo tipo de partidos con la realidad, el concepto de los mismos.
>> Pero resulta que una pila puede también ser visto como una estructura de datos, una
alternativa a una matriz, una alternativa a una lista enlazada.
Algo conceptualmente más interesante que todavía puede haber
implementado utilizando cualquiera de los cosas, pero es un tipo diferente de
estructura de datos de apoyo, de verdad, sólo dos operaciones.
Pero puedes agregar más de lujo características que éstos.
Pero estos son los fundamentos -
insertar y extraer.
>> Y la idea con una pila es que si yo tenemos aquí, con o sin Annenberg
saber, una bandeja de al lado con el número 9 en él.
Así que sólo un int.
Y quiero llevar este a los datos estructura, que actualmente está vacía.
Considere esto la parte inferior de la pila.
Me gustaría llevar este número 9 en el pila, y ahora es justo ahí.
>> Pero lo interesante de una pila es que si ahora quiero empujar
algún otro valor, como 17, y me empujan esta en la pila, yo voy a hacer
la única cosa intuitiva, sólo voy para ponerlo justo donde nosotros los humanos
se inclina a poner, en la parte superior.
Pero lo que es interesante ahora es, ¿cómo puedo conseguir a las 9?
Usted sabe, yo no lo hago sin algún esfuerzo.
>> Así que lo interesante de una pila es que por diseño,
que es una estructura de datos LIFO.
Manera tonta de describir último en entrar, primero en salir.
Así que el último número de en este momento tenía 17 años.
Así que si quiero hacer estallar algo fuera de la pila, sólo puede ser 17.
Así que hay una orden obligatoria de operaciones aquí, donde el último elemento
en tiene que ser la primera en salir.
De ahí el acrónimo, LIFO.
>> Entonces ¿por qué podría ser esto útil?
¿Son sus contextos en los que había quieren una estructura de datos como este?
Bueno, ha sido sin duda útil interior de una computadora.
Así que los sistemas operativos utilizan claramente esta tipo de estructura de datos para las pilas.
También veremos la misma idea cuando se trata de páginas web.
Así que esta semana y la próxima semana y más allá, y como iniciar la aplicación de web
páginas en un lenguaje llamado HTML, puede realmente utilizar una estructura de datos como
esto para determinar si la página tiene el formato correcto.
Porque vamos a ver todas las páginas web siguen una especie de jerarquía, una escotadura
que la voluntad, al final del día, ser un estructura de árbol debajo de la capucha.
Así que más de eso en sólo un poco.
>> Pero por ahora, vamos a proponer una momento, ¿cómo podemos ir sobre
representa lo que una pila es?
Permítanme proponer que implementamos una pila con código como este.
Así que una pila va a tener dentro de ella dos cosas, una matriz, llamada bandejas,
sólo para estar en consonancia con la demo.
Y cada uno de los elementos de la matriz va a ser un tipo int.
Y la capacidad es de suponer qué?
Porque yo no he escrito el definición completa aquí.
>> Es probablemente la máxima tamaño de la matriz.
Y probablemente declarada como una fuerte definir en la parte superior del archivo, algunos
tipo de constante como lo implica la mera capitalización.
Así que en alguna parte de la capacidad se define como el tamaño máximo posible.
Mientras tanto, en el interior de la estructura de datos conocido como una pila habrá
ser un entero sólo conocido simplemente como tamaño.
>> Así que si yo fuera a representar esta empresa pictóricamente, vamos a suponer que esta
cuadro negro entero representa mi stack.
En el interior de la misma es de dos variables.
Así que voy a señalar a la uno primero como el tamaño.
Y el segundo me voy dibujar como una matriz.
>> Pero sólo para mantener las cosas ordenadas, Normalmente me gustaría llamar una matriz como
esto, pero es un poco agradable si hacemos coincidir la realidad, o
que coincida con el modelo mental.
Así que déjame en vez dibujar la matriz verticalmente, lo que es justo, de nuevo,
interpretación del artista.
Realmente no importa lo que hay debajo del capó.
Y vamos a decir que, por defecto, capacidad va a ser tres.
Así que esta será la posición 0, este será ubicación 1, este
será ubicación 2.
>> Si me soborne con una bola de la tensión, lo haría alguien como para llegar y ejecutar el
abordar aquí por un momento?
Aceptar, vio primero la mano.
Vamos arriba.
Está bien.
Así que creo que es Steven.
Vamos arriba.
Está bien.
>> Pero supongamos ahora que rebobinar hasta el inicial estado del mundo en el que
se acaba de declarar una pila, y es va a tener una capacidad de tres.
Pero el tamaño todavía no se ha determinado.
Bandejas aún no ha sido determinada.
Así que un par de preguntas primero.
Y te voy a dar usted micrófono a lo que puede participar más activamente en esto.
>> Así que lo que está dentro de su tamaño en este momento a tiempo si todo lo que he hecho es
declarado una pila con una línea de código?
>> STEVEN: No mucho.
>> DAVID MALAN: OK, no mucho.
¿Sabemos lo que hay dentro de su tamaño, Cómo podemos saber lo que hay dentro
de esta variedad aquí?
>> STEVEN: Just código aleatorio, ¿verdad?
Just -
>> DAVID MALAN: Sí, voy a llamarlo código, pero al azar -
>> STEVEN: Cosas.
>> DAVID MALAN: Cosas como aleatorio
>> STEVEN: Bits.
>> DAVID MALAN: Bits, ¿verdad?
Así que los valores de la basura, ¿verdad?
Así permutaciones de 0 de y 1.
Los restos de usos anteriores de esta memoria.
Y no se sabe muy bien cuáles son los valores somos, por lo que normalmente los alejaremos
como signos de interrogación.
>> Así que lo primero que estamos presumiblemente va a querer hacer aquí -
y te voy a dar este campo en el interior de ahí el nombre - bandejas.
¿Qué debemos de suponer inicializar tamaño a si queremos
empezar a utilizar esta pila?
>> STEVEN: Bandeja está SUB 3.
>> DAVID MALAN: Entonces, OK.
Para que quede claro, se declara la capacidad en otros lugares como tres.
Y eso es lo que he usado para asignar la matriz.
El tamaño se va a hacer referencia a la cantidad de bandejas están actualmente en la pila.
>> STEVEN: Zero.
>> DAVID MALAN: Por lo tanto, debe ser cero.
Así que adelante, y con cualquier dedo, dibujar un cero en tamaño.
Está bien.
Así que ahora, lo que hay dentro de este aquí, no sabemos.
Estos son en realidad los valores de basura.
Así que podríamos dibujar signos de interrogación, pero vamos a mantener el tablero limpio por ahora
porque no importa lo que hay.
No necesitamos para inicializar la matriz para nada, porque si sabemos que
el tamaño de la pila es cero, bueno, no se debe mirar nada en
esta matriz de todos modos en este punto en el tiempo.
>> Así que ahora supongo que empujo la número 9 en la pila.
¿Cómo debemos actualizar la estructura de datos dentro de este recuadro negro?
¿Qué valores tienen que cambiar?
>> STEVEN: Within -
el tamaño?
>> DAVID MALAN: OK.
Tamaño Debe convertirse en lo que?
>> STEVEN: Tamaño sería uno.
>> DAVID MALAN: OK.
Así que el tamaño debe ser uno.
Así que usted puede hacer esto en un par de maneras.
Te voy a dar, ya que su el dedo es una goma de borrar.
Está bien.
Entonces ahora el dedo es un pincel.
Está bien.
Y ahora ¿qué otra cosa tiene que cambiar, obviamente, en la estructura de datos?
>> STEVEN: Estamos pasando de de abajo hacia arriba a 9.
>> DAVID MALAN: 9.
Bueno, bueno.
Así que todavía no importa lo que está en ubicación de uno o dos, porque son
valores de basura, pero no hay que molestarse buscando allí porque el tamaño es
que nos dice que sólo el primer elemento en realidad es legítima.
Así que ahora me empuje 17 en la lista.
¿Qué pasa con esta imagen?
>> STEVEN: Tamaño Así que va a ir a dos.
>> DAVID MALAN: OK.
Eres eraser -
¡Uy.
Usted es una goma de borrar.
>> STEVEN: Borrador.
>> DAVID MALAN: Eres un cepillo.
>> STEVEN: Brush.
>> DAVID MALAN: OK.
¿Y qué más?
>> STEVEN: Y entonces -
>> DAVID MALAN: Nos empujó 17.
>> STEVEN: Nos pegamos 17 en la parte superior, por lo que -
>> DAVID MALAN: OK, bueno.
>> STEVEN: - caída hacia abajo.
>> DAVID MALAN: Muy bien.
Se está poniendo fácil.
Yo no voy a ayudarle a este momento.
Empuje 22.
>> STEVEN: Hecho.
Convertirse en una goma de borrar.
Me estoy convirtiendo en un cepillo.
Y entonces me estoy poniendo 22.
>> DAVID MALAN: 22.
Excelente.
Así que una vez más.
Ahora voy a empujar en la pila 26.
>> STEVEN: Ooh.
Oh Dios mío.
Realmente me tomó por sorpresa.
>> DAVID MALAN: No lo hiciste ver venir esto?
>> STEVEN: No vi venir esto.
¿Podríamos volver a inicial de la capacidad?
>> DAVID MALAN: Esa es una buena pregunta.
Así que hemos tipo de nosotros mismos pintamos en una esquina aquí.
Realmente no hay ninguna buena por Steven porque hemos asignado este array
estáticamente, por así decirlo, el interior de la estructura de datos.
Y hemos esencialmente codificamos que sea del tamaño de tres.
Así que en realidad no podemos reasignarlo.
>> Podríamos Si regresamos, nos bandejas redefinidos para ser un puntero que
entonces usamos malloc para memoria de la mano de.
Porque si tenemos la memoria de la pila a través de malloc, que
podría entonces liberarlo.
Pero antes de liberarla, podríamos reasignar un pedazo más grande de la memoria,
actualizar el puntero, y así sucesivamente.
Pero por ahora, esto es realmente lo mejor que podemos hacer.
Empuje y pop son presumiblemente van a tener que señalar alguna de error.
>> Así, por ejemplo, nuestra implementación de empuje podría devolver un bool que
previamente devuelto cierto, cierto, cierto.
Pero la cuarta vez, va a tener devuelva false, por ejemplo.
Está bien.
Muy bien hecho.
Felicitaciones.
Te has ganado tu bola de la tensión actual.
>> [Aplausos]
>> STEVEN: Gracias.
>> DAVID MALAN: Gracias.
OK, así que esto parece ser no mucho de un paso adelante, ¿no?
Hemos descrito esta estructura de datos.
Ha sido convincente, ¿no?
Los sistemas operativos gusta.
Al parecer, la web puede hacer uso de este, y otras aplicaciones fijas.
Pero lo que una limitación estúpidos que somos de vuelta a clase de semana dos límites
donde hemos fijado arrays de tamaño.
>> Así que de hecho hay un par de maneras en que podríamos solucionar esto.
Podríamos asignar dinámicamente la matriz, no por la fuerza de codificación como he
hecho aquí, sino que vuelva a declarar esto, para ser claros, como
algo como esto.
Int * bandejas, no decidir en una capacidad todavía.
Pero cuando yo declaro la pila en otros lugares en mi código, podría entonces llamar a malloc,
obtener la dirección de un trozo de memoria, y podría asignar
esa dirección a bandejas.
>> Y luego, porque es sólo un trozo de memoria, podría seguir utilizando cuadrado
notación de corchetes de la manera habitual.
Porque una vez más, hay una especie de este equivalente funcional de matrices y
trozos de memoria que vienen de vuelta de malloc.
Podemos tratar a uno como el otro utilizando la aritmética de punteros o
notación de corchetes.
Así que ese es uno de los enfoques.
>> Pero, ¿cómo más podemos implementar esta misma estructura de datos, potencialmente?
¿Cierto?
Me siento como que acabamos de resolver este problema como hace una semana.
¿Cuál fue la solución a este problema que se encontró con Steven?
Así que las listas enlazadas, derecha.
>> Si el problema es que estamos pintando a nosotros mismos en una esquina por la asignación de
en avance muy poca memoria que a continuación, tener que lidiar de alguna manera con, bueno,
¿por qué no evitar que emitir en total?
¿Por qué no declaran bandejas para ser un puntero a un nodo, ergo una lista enlazada,
y luego simplemente asignar nuevos nodos cada vez que Steven tenía que adaptarse a una
número en la estructura de datos.
>> Así que la imagen tendría que cambiar.
No va a ser tan limpio y tan simple como una matriz de tres enteros.
Ahora que va a ser un puntero a una estructura, y que estructura se va a
tener un entero y un puntero siguiente.
Se va a llevar a través de ese puntero a otro tal estructura a
otro ejemplo de estructura.
Así que el panorama sería realmente ser un poco más desordenado.
Y tendríamos flechas atar todo junto.
>> Pero eso está bien, correcto, porque hemos visto cómo hacer esto.
Y una vez que usted se sienta cómodo implementar algo así como un archivo vinculado
lista, que tendrá que hacer si elegir implementar una tabla hash con
encadenamiento separado para p-set 6, se puede utilizarlo como un bloque de construcción, o un
ingrediente, o arañazos hablar, un procedimiento, algo que se pone, que
creado su propia pieza del rompecabezas que se puede reusar.
Así compensaciones, sino las posibles soluciones que en realidad hemos visto antes.
>> Así que muy a menudo, se ve esto todos los año o dos cuando Apple lanza
algo nuevo, y todos los locos fila afuera de la Manzana
tienda a comprar su marginal actualizar el hardware.
Digo esto, está bien, porque Yo soy una de esas personas.
Entonces, ¿qué tipo de estructura de datos podría representar esta realidad?
>> Bueno, vamos a llamarlo una cola, una línea.
So British diría que es típicamente un cola de todos modos, así que es un nombre bonito.
Y las dos operaciones que una cola apoyará llamaremos un enqueue
funcionamiento y una operación de quitar de la cola, que son similares en
espíritu para insertar y extraer.
Es sólo una especie de diferente en convención, lo que estamos llamando a estos.
Pero para poner en cola algo significa añadir o insertarlo en la estructura de datos.
Para quitar de la cola medios para eliminarlo.
Pero mientras que una pila era un dato LIFO estructura, una cola es una primicia en,
primero en salir estructura de datos.
>> Si usted es la primera persona de la fila, usted será la primera persona en llegar
fuera de la línea y comprar su nuevo dispositivo.
Imagínate lo mal que serían estas personas si Apple en cambio utiliza una pila, para
ejemplo, para implementar la recolección en marcha de su nuevo juguete.
Así que las colas tienen sentido, sin duda, y podemos pensar en todo tipo de
aplicaciones, presumiblemente, para las colas, especialmente cuando se quiere justicia.
Entonces, ¿cómo podríamos aplicar estos como una estructura de datos?
>> Bueno, yo propongo que podría tenga que hacerlo de esta manera.
Así que voy a tener ahora los números.
Así que vamos a mantenerlo simple y no necesariamente hablar en términos de bandejas.
A sólo números que la gente de habidas.
La capacidad se va a, de nuevo, fijar el número total de personas que pueden estar en
esta línea, ya que tres o cualquier otro valor.
>> Pero propongo que necesito para realizar un seguimiento no sólo del tamaño de la
cola, ¿cuántas cosas hay en él.
Así que el tamaño es el tamaño actual, la capacidad de es el tamaño máximo.
Sólo una vez más, la nomenclatura por convención.
¿Por qué necesito un int adicional dentro de una cola para realizar un seguimiento de quién está en
delante de la línea?
¿Por qué tengo que hacer eso en este caso?
>> Bueno, ¿cómo es esta imagen va a cambiar?
Es probable que pueda volver a utilizar más de esta imagen.
Déjame ir adelante y borrar lo que hay aquí.
Vamos a dar esto un poco nombre diferente aquí.
Vamos a deshacernos de los 17, vamos a deshacernos del 9, vamos a deshacernos de los 3.
Y vamos a añadir una cosa más.
Propongo que tengo que hacer un seguimiento de al frente de la lista, que es sólo
va a ser un int también.
Y vamos a mantenerlo simple.
Lista de No vinculado por ahora.
>> Vamos a admitir que vamos a se topan con este límite.
Pero, ¿qué es lo que quiero ver sucederá esta vez?
Así que supongo que sigo adelante y la primera persona aparece en la fila, y
es el número 9.
Tenemos bolas de la tensión.
¿Puedo robar, por ejemplo, dos o tres personas?
Uno, dos, tres?
Vamos arriba.
Desde el frente, porque vamos a hacer esta labor más rápida.
>> Cada uno de ustedes está ahora va a ser un chico de ventilador en línea de Apple.
Usted no va a recibir los equipos de Apple al final de esto, sin embargo.
Está bien.
Así que usted es el número 9, que está número 17, número 22.
Estos son números arbitrarios, como identificaciones estudiantiles o lo que sea.
Y en un momento, vamos a empezar para empezar a añadir cosas.
Y voy a correr el tablero aquí esta vez.
>> Así que en este caso, he inicializa la frente a ser -
En realidad no me importa lo que la delante es, porque el tamaño es cero.
Así que esto puede ser que también acaba de ser un signo de interrogación.
Todos estos son signos de interrogación.
Así que ahora vamos a empezar a ver realmente algunos gente haciendo cola en la tienda.
>> Así que si el número 9, que es el primero a las 5 de la mañana, a seguir adelante y se alinean,
o la noche antes.
Aceptar.
Así que ahora 9 está aquí.
Así es 9 en la parte frontal de la lista.
Así que voy a seguir adelante y actualizar el tamaño de estos datos actual
estructura a no ser 0 más, pero para ser 1.
Me voy a poner 9 en el frente de la lista.
Déjame ir adelante y alternar la pantalla para que podamos ver más allá de nosotros aquí.
>> Y ahora, ¿qué es lo que quiero poner al frente?
Voy a llevar la cuenta de que la frente de la cola en este momento
está en la posición 0.
Porque lo que está al lado va a pasar?
Bueno, supongo que ahora me Enqueue 17 también.
Así que saltar en línea allí.
Y de nuevo, el tipo de puerta a la tienda va a estar aquí.
Así que ahora he añadido 17.
Y a pesar de que estos chicos están bloqueando la pantalla, eso está bien,
porque podemos verlo aquí.
Lo siento.
>> AUDIENCIA: Podemos mover -
>> DAVID MALAN: No, eso está bien.
Es enorme allí.
Así 17 está ahora dentro de la cola.
Necesito actualizar el que campos, aunque ahora?
Bueno, definitivamente tamaño.
¿Y qué hay delante?
Bueno, no.
Frente no debe cambiar, porque a diferencia de una pila, que
quiere mantener la equidad.
Así que si 9 se produjo en primer lugar, queremos 9 para ser el primero en salir de la línea de
y dentro de la tienda.
>> De hecho, vamos a ver eso.
Antes de que nos insertamos 22, vamos a seguir adelante y sacar de la cola 9.
¿Cuál es tu nombre?
>> AUDIENCIA: Jake.
>> DAVID MALAN: Jake va para ser quitado de la cola ahora.
Así que tienes que caminar a la tienda.
Y pretender que la tienda es por allí.
Así que ahora lo que hay - dit-dit-dit!
¿Qué debe ocurrir ahora?
Decisión de diseño.
Así que no es un mal instinto, pero - ¿cuál es tu nombre?
>> AUDIENCIA: David.
>> DAVID MALAN: David.
Entonces, ¿qué hizo David?
Él estaba tratando de arreglar especie de los datos estructura y el movimiento de su ubicación
en antigua ubicación de Jake.
Y eso está bien si estamos dispuestos a aceptar que como una
detalle de implementación.
Pero primero, vamos a actualizar los datos estructura antes de hacer eso.
Porque yo no me está gustando la idea de todo el pueblo el cambio en esta línea.
>> No es gran cosa si David lo hace con un paso, pero una vez más, pensar en volver a
cuando hemos tenido ocho voluntarios en el escenario y lo que hemos hecho, como la inserción
especie, donde tuvimos que empezar mover todos a su alrededor.
Eso hizo caro, ¿no?
Eso me hace temblar sobre Big O de n, gran O de n al cuadrado de nuevo.
No se siente como un resultado ideal.
>> Así que vamos a actualizar esto.
Así que el tamaño de la cola ya no es 2.
Ahora es simplemente 1.
Pero ahora puedo actualizar algo No me actualizo antes, la
frente de la lista.
Yo sólo puedo decir, es que la ubicación 1?
Así que ahora tenemos el valor de basura aquí, valor de la basura aquí, y David en el
medio de esta basura.
Pero la estructura de datos sigue intacta.
>> Y de hecho, yo ni siquiera necesito cambiar ex número de Jake
9, porque a quién le importa.
Tengo suficiente información ahora en el tamaño que sé que hay una persona en
esta cola.
Y sé que esa persona está en la posición 1, no 0.
No estoy contando.
Así 1 también.
De modo que la estructura de datos es aún así está bien.
>> Bueno, ¿qué pasa después?
Vamos a poner en cola -
¿cuál es tu nombre?
>> AUDIENCIA: Callen.
>> DAVID MALAN: Callen.
Vamos a poner en cola un Callen, y 22 se encuentra ahora en la cola.
Así que ahora lo que tiene que cambiar aquí?
Frente no va a cambiar, obviamente.
Tamaño va a cambiar para ser 2 de nuevo.
Y 22 termina aquí, 9 es todavía presente, pero es efectivamente un
valor de la basura ahora.
Es sólo un remanente de Jake pasado.
>> ¿Y ahora qué pasa si Me Dequeue David?
Una última operación, dequeue David.
Podríamos cambiar, pero propongo establezcamos las hacer el menor trabajo posible.
Ahora mi estructura de datos se de nuevo en tamaño de 2 a 1.
Pero la parte delantera de la cola ahora se convierte en 2.
Yo no necesito cambiar estos números por el momento, porque son
sólo los valores de basura.
>> Pero ahora ¿qué pasa?
Supongamos que yo Enqueue mí mismo, 26?
Siento que pertenezco aquí.
Así que estoy siendo en cola.
Así que tipo de pertenezco aquí.
Y aunque no lo hace bastante apreciar esta visualmente en el escenario,
porque tenemos un montón de espacio, lo que debería No estar de pie aquí, ¿por qué?
>> AUDIENCIA: Usted está fuera de los límites.
>> DAVID MALAN: Así es.
Estoy fuera de los límites.
He indexan más allá de la límites de este arreglo.
Realmente debería estar en uno de los tres posibles ubicaciones.
Ahora, ¿dónde está más natural que ir?
Propongo aprovechamos a la semana de un solo truco.
El operador mod, porcentaje.
Porque estoy técnicamente pie en localización 3, pero tengo 3 capacidad mod,
so 3, un signo de porcentaje, 3 -
de capacidad 3.
¿Qué es eso?
¿Qué es lo que queda cuando dividir 3 por 3?
0.
>> Así que eso pone a mí eran Jake era, que en realidad es bueno.
Así que ahora la aplicación de esta cosa va a
ser un poco de dolor de cabeza.
Es realmente una sola línea de dolor de cabeza, de código.
Pero al menos ahora hay basura valoran aquí, pero hay dos
ints legítimos aquí.
Y afirmo que ahora que hemos hecho exactamente lo que tenemos que hacer, siempre y cuando
cambiamos lo de Jake valor iba a ser 26.
>> Ahora tenemos suficiente información todavía para mantener la integridad
de esta estructura de datos.
Todavía estamos un poco fuera de suerte cuando nos desee insertar cuatro o más totales
elementos, pero al menos puedo hacer bastante uso eficiente de esta constante
tiempo, de hecho.
Yo no tengo que preocuparme por el cambio todos, como la inclinación de David era.
>> ¿Tiene preguntas sobre pilas, o esta cola?
>> AUDIENCIA: ¿Es la razón por la cual usted necesita tamaño para que usted sepa
dónde tener a una persona?
>> DAVID MALAN: Exactamente.
Necesito saber el tamaño de la matriz porque tengo que saber exactamente cómo
muchos de estos valores son legítimos, y para que yo pueda encontrar dónde poner
la siguiente persona.
Exactamente.
El tamaño es -
en realidad, no nos actualizamos esto todavía.
Me sumé a 26.
El tamaño es ahora, no 1, sino 2.
Así que ahora esta de hecho me ayuda a encontrar el cabeza de la lista, que no es 0, no
1, pero es 2.
El frente de la lista es de hecho el número 22.
Debido a que llegó en primer lugar, por lo que debería ser admitidos en la tienda antes de mí,
a pesar de que visualmente estoy parado más cerca de la tienda.
>> ¿De acuerdo?
Un aplauso para estos chicos y dejaremos que sacarlos de allí.
>> [Aplausos]
>> DAVID MALAN: podía dejar que a mantener la bandeja.
Pudimos ver lo que ocurre si que quiera, pero tal vez no.
Está bien.
¿Y ahora qué nos deja eso?
Bueno, permítanme proponer que hay un algunas otras estructuras de datos que pudimos
empezar a añadir a nuestro conjunto de herramientas que se en realidad ser muy, muy relevante como
nos sumergimos en materia web.
Que a su vez, tiene algún tipo de conexión a los árboles en la forma de
algo que se llama DOM, documento modelo de objetos.
Pero vamos a ver más de que en poco tiempo.
>> Permítanme proponer por definición que Árbol de llamadas ahora lo que puede ser que sepa como
más de un árbol de la familia, en la que tener algún antepasado en el
raíces del árbol.
A patriarcal o una matriarca en la parte más alta del árbol.
Sin su cónyuge, en este caso.
Pero ahora tenemos lo que llamamos los niños, que son los nodos que cuelgan
fuera el hijo izquierdo o derecho del niño, flechas como se representa aquí.
>> En otras palabras, en una estructura de datos en árbol en el ordenador, un árbol tiene cero
o más nodos.
Si tiene al menos un nodo, eso se llama la raíz.
Son las cosas visualmente que nos basamos en la parte superior.
Y ese nodo, como cualquier otro nodo, puede tener cero, uno, o dos, o tres,
o sin embargo muchos niños la estructura de datos compatible.
En este caso, la raíz, el almacenamiento de la valorar uno, tiene dos hijos, de 2 y 3,
por lo que generalmente llamamos 2 la izquierda infantil y 3 el hijo derecho.
>> Y luego, cuando nos ponemos manos a la 5, 6, y 7, 6 podría ser llamado el hijo del medio.
Si usted tiene cuatro hijos, se vuelve confuso.
Así que dejamos de usar ese tipo de atajo verbal.
Pero no deja de ser un árbol genealógico.
Y las hojas que aquí están los nodos que ellos no tienen hijos.
Se cuelgan de la parte inferior del árbol.
>> Entonces, ¿cómo podríamos implementar un árbol que tiene sólo dos hijos al máximo?
Lo llamaremos un árbol binario.
Bi de nuevo lo que significa dos, en este caso, al igual que con el binario.
Y por lo que puede tener cero, uno, o dos niños como máximo.
>> Yo propongo que implementamos el nodo para esa estructura con un int n,
y luego dos punteros, uno llamado a la izquierda, uno llamado derecha.
Pero esos son sólo agradable convenciones arbitrarias.
Y lo que es bueno ahora, sobre todo si clase de batallado conceptualmente con
recursividad, o pensó que no era realmente una solución a nada,
especialmente si pudiera quedarse sin memoria.
Ahora que estamos hablando de datos estructuras y algoritmos que permiten
nosotros atravesamos y manipularlos, Resulta que la recursividad regresa en
una forma mucho más convincente si no es bello camino.
>> Así que esto que propongo es la implementación de una función de búsqueda.
Dadas dos entradas -
por lo que pensar en esto como un cuadro negro.
Dadas dos entradas, n, un entero, y un puntero a un árbol, un puntero a una
nodo, o realmente la raíz de un árbol, afirman que esta función puede devolver
verdadera o falsa, de que el valor n que está dentro de este árbol.
>> ¿Qué hay dentro de esta caja de negro?
Bueno, cuatro ramas.
El primero sólo comprueba.
Si el árbol es nulo, apenas vuelva falsa.
Si no hay un nodo, no hay n, no hay un número, simplemente return false.
Si, sin embargo, n, el valor que usted está buscando para, es menos de árbol de la flecha N, y
sólo para que quede claro, lo que quiere decir cuando Escribo árbol y luego la flecha
notación, n?
Exactamente.
Significa eliminar la referencia que puntero llama árbol.
Ir allí, y luego entrar de esa nodo y conseguir su campo llamado n.
Y a continuación, comparar el n real que fue pasado a la búsqueda en contra de ella.
>> Así que si n es menor que, el valor de n en el nodo de árbol en sí, bueno,
¿Qué significa eso?
Eso no significa nada a primera vista.
¿Cierto?
Al igual que cuando usted tiene una gran variedad de valores, que te pueden gustar aplicar binario
buscar como una forma de división y conquistar.
Pero, ¿qué hipótesis nos tenemos que hacer de búsqueda binaria para trabajar en absoluto
en la guía telefónica y ejemplos anteriores?
>> Cómo ordenar.
Así que vamos a refinar la definición de árbol aquí no para ser sólo un árbol, lo que puede
tener cualquier número de hijos.
No es sólo un árbol binario, lo que puede tener 0, 1, o 2 como máximo.
Pero, como un árbol de búsqueda binaria, o BST, que es sólo una forma elegante de decir una
árbol binario de tal manera que de cada nodo hijo izquierdo, si está presente, es
menor que el nodo.
Y los niños el derecho de cada nodo, si está presente, es mayor
que el propio nodo.
>> Así que en otras palabras, si usted fuera a dibujar el árbol de salida, todos los números son
cuidadosamente equilibrada como esto para que si usted tiene 55 como la raíz, 33 pueden ir
a su izquierda, ya que es menos de 55.
77 se puede ir a la derecha, porque que es mayor que 55.
Pero ahora fíjense, la misma definición, es una definición recursiva verbalmente,
tiene que solicitar 33.
Hijo izquierdo de 33 debe ser menor que ella, y el derecho del niño de 33 años, de 44 años, debe ser
más grande que él.
>> Así que este es un árbol de búsqueda binaria, y Propongo, con un poco de
recursividad, ahora podemos encontrar n.
Así que si n es menor que el valor de n que es nodo actual, voy a ir
adelante y batea, por así decirlo, y sólo regreso sea cual sea la respuesta es de
la búsqueda de n en el hijo izquierdo del árbol.
Note otra vez, esta función sólo espera una estrella nodo, una
puntero a un nodo.
Así que he aquí yo sólo puedo hacer árbol flecha izquierda, lo que conducirá
me a otro nodo.
Pero, ¿qué es ese nodo?
>> Bueno, de acuerdo con esta declaración, izquierda es sólo un puntero, por lo que sólo
significa que estoy pasando a la función de búsqueda un puntero diferente, a saber
el que representa el árbol de mi hijo izquierdo.
Así pues, en este caso, el puntero a 33, si esta es nuestra entrada de la muestra Mientras tanto, si
n es mayor que el valor de n en la nodo actual en el árbol, entonces estoy
va a seguir adelante y en batea en la otra dirección y simplemente decir, no lo sé
saber si este valor de n está en el árbol, pero sé que si lo es, es por mi
rama derecha, por así decirlo.
Así que déjame llamar recursivamente buscar, pasar una n otra vez, pero que pasa en un
Puntero a mi hijo derecho.
>> En otras palabras, si estoy en la actualidad a 55 y estoy en busca de 99, yo sé que el 99
es mayor que 55, por lo que al igual que yo arranqué hace las semanas de la guía telefónica y nos
que salió bien, del mismo modo somos va a ir a la derecha aquí.
Y yo no sé si es a mi derecha niño, y no lo es, 77 es allí, pero
Sé que es en esa dirección.
Así que llamar a buscar a mi hijo derecho, 77, y dejar que figura búsqueda hacia fuera de
Si hay 99 en este arbitraria ejemplo es realmente allí.
>> Si no, ¿cuál es el último caso?
Si el árbol es nula es uno de los casos.
Si n es menor que la corriente del nodo valor es otro caso.
Si n es mayor que la corriente valor del nodo es un tercer caso.
¿Cuál es la cuarta y última caso?
Creo que estamos fuera de los casos, ¿no?
Debe ser que n está en el nodo actual que estoy en.
>> Así que si yo estoy buscando 55 en este punto en la historia, esa rama de la
árbol volvería realidad.
Así que lo que es interesante aquí es que En realidad, a diferencia de semana pasado, que tipo
de tener dos casos base.
Y no tienen que es todo en la parte superior.
La parte superior es un caso base, porque si el árbol es nulo, no hay nada que hacer.
Simplemente envíe un duro Coded valor false.
>> La rama inferior es una especie de De forma predeterminada, por lo que si hemos comprobado para
null, hemos comprobado si debe ser a la izquierda, pero no debe ser, tenemos
comprobar si se debe estar en lo cierto, pero no debe ser, claramente, tiene que ser
justo donde estamos.
Ese es un caso base.
Así que hay dos casos recursivos intercalado en el medio.
Pero yo podría haber escrito esto en cualquier orden.
Acabo de pensar que tipo de sentía natural comprobar primero para un posible error,
a continuación, compruebe la izquierda, a continuación, compruebe la derecha, luego asumir que usted está en el nodo
en realidad estás buscando.
>> Entonces ¿por qué podría ser esto útil?
Así que resulta -
y que me haga saltar de un teaser aquí lo que está en la web.
Vamos a empezar no es un uso de lenguaje de programación al principio, pero una
lenguaje de marcas.
Un lenguaje de marcado de ser uno que sea similares en espíritu a la programación
lenguaje, pero no te la dan capacidad de expresarse con lógica.
Sólo le da la capacidad de expresarse estructuralmente.
>> ¿Dónde quieres poner algo en la página, la página web?
¿De qué color es lo que quieres que sea?
¿Qué tamaño de la fuente es lo que quieres que sea?
¿Qué palabras en realidad quiera en la página web?
Así que eso es un lenguaje de marcas.
Pero entonces vamos a introducir muy rápidamente JavaScript, lo que es un hecho y derecho
lenguaje de programación.
Sintácticamente muy similares en apariencia a C, pero va a tener algún
agradable, más poderoso, más características de uso fácil.
>> Y una de las frustraciones en este punto en el semestre es que vamos a
pronto aplicar corrector ortográfico en un número mucho menor líneas de código que utilizan otros idiomas
que la propia C permite, pero por razón de pronto vamos a entender.
Esta será la primera de esas páginas web.
Será completamente decepcionante, el primero que hacemos.
Simplemente va a decir hola mundo.
Pero si nunca has visto antes, este es HTML,
HyperText Markup Language.
>> Si usted va a una opción de menú determinado en la mayoría de cualquier navegador, en cualquier página web en
el Internet, usted puede ver el código HTML que algunas personas escribieron a
crear esa página web.
Y probablemente no se ve tan breve o tan limpio como este.
Pero va a seguir el patrón de estos soportes y barras abiertas y
letras y potencialmente números.
>> Pensé que te daría un teaser de lo que será capaz de hacer
después de tomar CS50.
Déjame ir a cs.harvard.edu / rob, nuestra propia página de Rob Bowden.
Él hizo esto por nosotros.
Así que pronto será capaz de hacer eso.
Y también, lo que has oído esta mañana -
lo que has oído esta mañana -
>> [MÚSICA Hamster Dance]
>> - Usted será capaz de hacer esto.
Que nos espera el miércoles.
Nos vemos entonces.
>> [MÚSICA Hamster Dance]
DAVID MALAN: En la próxima CS50 -