[REPRODUCCIÓN DE MÚSICA]
ALTAVOZ 1: De acuerdo.
Todo el mundo la bienvenida de nuevo a la sección.
Espero que todos ustedes estén con éxito recuperado de su concurso
desde la semana pasada.
Sé que es un poco loco a veces.
Como decía antes, si estás dentro de la desviación estándar,
realmente no te preocupes por eso, sobre todo para una sección menos cómodo.
Eso es donde debe estar.
>> Si lo hizo muy bien, entonces impresionante.
Felicitaciones a usted.
Y si usted siente que necesita un poco más de ayuda, por favor
no dude en llegar a cualquiera de los TFS.
Todos estamos aquí para ayudar.
>> Es por eso que enseñamos.
Es por eso que estoy aquí todos los lunes para usted chicos y en la oficina horas los jueves.
Así que por favor no dude en hacérmelo saber si usted está preocupado acerca de cualquier cosa
o si hay algo en el concurso que realmente te gustaría abordar.
>> Así que el orden del día de hoy es todo acerca de las estructuras de datos.
Algunos de éstos son sólo va a ser justo para ayudarle a familiarizarse con ellas.
¿Alguna vez no puede aplicar en esta clase.
Algunos de ellos se quiere, como para su conjunto de procesadores ortografía.
>> Usted tiene su opción entre tablas hash y tries.
Así que sin duda nos vamos sobre aquellos.
Va a ser, sin duda más de clase de una sección de alto nivel hoy en día, sin embargo,
porque hay una gran cantidad de ellos, y si entramos en los detalles de implementación
en todos ellos, que no lo haría incluso conseguir a través de las listas enlazadas
y tal vez un poco de tablas hash.
>> Así que tengan paciencia conmigo.
No vamos a estar haciendo tanto de codificación de este tiempo.
Si usted tiene alguna pregunta acerca de ella o si desea verlo en práctica
o probarlo por ti mismo, Sin duda, recomiendo
ir a study.cs50.net, que tiene ejemplos de todos estos.
Tendrá mis presentaciones en PowerPoint con las notas que nos
tienden a usar, así como algo de programación ejercicios, sobre todo para las cosas
como listas enlazadas y binario árboles pilas y señales.
Tan poco nivel más alto, lo que podría ser bueno para ustedes.
>> Así que con eso, vamos a empezar.
Y también, concursos sí--.
Creo que la mayoría de ustedes que están en mi sección tiene sus pruebas,
pero nadie viene en o alguna razón usted no hacerlo, están aquí mismo en la parte delantera.
>> Así vinculado listas.
Sé que este tipo de va antes de hacer una copia de su cuestionario.
Eso fue la semana anterior que nos enteramos de esto.
Pero en este caso, sólo tendremos que ir un poco más en profundidad.
>> ¿Entonces por qué podríamos elegir un lista enlazada a través de una matriz?
¿Qué los distingue?
¿Sí?
>> AUDIENCIA: Usted puede ampliar una vinculada listar versus tamaño fijo de una matriz.
ALTAVOZ 1: Derecho.
Una matriz ha fijado tamaño mientras que una lista enlazada tiene un tamaño variable.
Así que si no sabemos cómo mucho que queremos almacenar,
una lista enlazada nos da una gran manera de hacer eso porque podemos simplemente
añadir en otro nodo y añadir en otro nodo y agregar en otro nodo.
Pero lo que podría ser una solución de compromiso?
¿Alguien recuerda el trade-off entre matrices y listas enlazadas?
Mmhmm?
>> AUDIENCIA: Usted tiene que ir a través de todo el camino
a través de la lista enlazada encontrar un elemento en una lista.
En una matriz, se puede simplemente encontrar un elemento.
>> ALTAVOZ 1: Derecho.
Así que con arrays--
>> AUDIENCIA: [inaudible].
>> ALTAVOZ 1: Con los arreglos, tenemos lo que se llama acceso aleatorio.
Significa que si queremos lo que es nunca el quinto punto de la lista
o el quinto punto de nuestra matriz, que sólo puede agarrarlo.
Si se trata de una lista enlazada, tenemos para recorrer, ¿no?
Así que el acceso a un elemento en una matriz es la constante de tiempo,
mientras que con una lista enlazada que lo haría más probable es que el tiempo lineal porque a lo mejor
nuestro elemento es todo el camino al final.
Tenemos que buscar a través de todo.
Así, con todos estos datos estructuras que vamos
a pasar un poco más de tiempo en, ¿cuáles son los puntos positivos y negativos.
¿Cuándo podríamos querer utilizar uno sobre el otro?
Y eso es algo de la Lo más grande para llevar.
>> Así que tenemos aquí la definición de un nodo.
Es como uno de los elementos nuestra lista enlazada, ¿verdad?
Así que estamos todos familiarizados con nuestras estructuras typedef,
que nos fuimos en la revisión última vez.
Era básicamente la creación de otro tipo de datos que podríamos utilizar.
>> Y en este caso, es algún nodo que se celebrará en algún entero.
Y entonces ¿cuál es la segunda parte aquí?
Cualquier persona?
>> AUDIENCIA: [inaudible].
>> ALTAVOZ 1: Sí.
Es un puntero al siguiente nodo.
Así que esto se debe en realidad estar aquí arriba.
Esto es un puntero del tipo de nodo a la siguiente cosa.
Y eso es lo que abarca nuestra nodo.
Enfriar.
>> Muy bien, así que con la búsqueda, ya que estábamos sólo decir antes de la mano, si estás
ir a buscar a través de, usted tiene que repetir en realidad
a través de su lista enlazada.
Así que si estamos buscando el número 9, empezaríamos a nuestra cabeza
y que nos señala al principio de nuestra lista enlazada, ¿verdad?
Y decimos, bien, lo hace nodo contiene el número 9?
¿No?
>> Muy bien, vaya a la siguiente.
Síguelo.
¿Contiene el número 9?
No.
Siga el siguiente.
>> Así que tenemos que recorrer en realidad a través de nuestra lista enlazada.
No podemos ir directamente a donde 9 es.
Y si ustedes realmente quiere ver algunos pseudo-código allá arriba.
Tenemos alguna función de búsqueda aquí que toma en-- ¿qué se necesita en?
Qué piensas?
Tan fácil uno.
Qué es esto?
AUDIENCIA: [inaudible].
ALTAVOZ 1: El número que estamos buscando.
Derecha?
¿Y qué sería esto correspondería a?
Es un puntero a?
>> AUDIENCIA: Un nodo.
>> ALTAVOZ 1: Un nodo a la lista que estamos viendo, ¿no?
Así que tenemos algunos nodos son puntero aquí.
Este es un punto que va a realmente recorrer nuestra lista.
Nos propusimos que igual a la lista porque eso es sólo
estableciendo que igual a la comenzar de nuestra lista enlazada.
>> Y si bien no es NULL, mientras que todavía tenemos cosas en nuestra lista,
comprobar para ver si ese nodo tiene el número que estamos buscando.
Devuelve verdadero.
De lo contrario, actualizarla, ¿no?
>> Si es NULL, salimos de nuestra while y return false
porque eso significa que no hemos encontrado.
¿Todo el mundo consigue cómo funciona?
Okay.
>> Así que con la inserción, se tener tres formas diferentes.
Puede anteponer, puede anexar y se puede insertar en surtido.
En este caso, estamos vamos a hacer un prefijo.
¿Alguien sabe cómo los tres casos pueden ser diferentes?
>> Así que anteponer significa que se pone que en la parte delantera de su lista.
Así que eso significaría que no importa lo que su nodo es, no importa
lo que el valor es, vas para ponerlo aquí delante, ¿de acuerdo?
Va a ser la primera elemento en su lista.
>> Si anexa que, va para ir a la parte de atrás de su lista.
Y se insertan en surtidos significa que eres va a poner realmente en el lugar
donde mantiene su lista enlazada ordenada.
Una vez más, cómo se utiliza esos y cuando se utiliza
ellos variarán dependiendo de su caso.
Si no necesita ser ordenados, anteponga tiende
a ser lo que la mayoría de la gente utilizar porque no lo hace
tener que pasar por toda la lista para encontrar el final para agregarlo en, ¿verdad?
Usted sólo puede pegarlo directamente.
>> Así que vamos a ir a través de un inserción 1 en este momento.
Así que una cosa que voy a Recomiendo altamente a este conjunto de procesadores
es dibujar las cosas, como siempre.
Es muy importante que actualice sus punteros en el orden correcto
porque si ellos actualizar un poco fuera de lugar,
usted va a terminar perder partes de su lista.
>> Así, por ejemplo, en este caso, estamos contando la cabeza a punto justo a 1.
Si sólo hacemos sin guardar este 1,
no tenemos idea de lo que 1 debe apuntar a ahora
porque hemos perdido lo que la cabeza señaló.
Así que una cosa que hay que recordar cuando estás haciendo un prepend
es salvar lo que el puntos de la cabeza a la primera,
a continuación, volver a asignar, y luego actualizar lo que su nuevo nodo debería apuntar.
En este caso, esta es una manera de hacerlo.
>> Así que si hubiéramos hecho así en el que sólo reasignados cabeza,
perdemos básicamente nuestra lista completa, ¿no?
Una forma de hacerlo es tener un punto de siguiente y, a continuación, tener la cabeza a punto 1.
O usted puede hacer algo así como el el almacenamiento temporal, la cual hablé sobre.
>> Pero la reasignación de su punteros en el orden correcto
va a ser muy, muy importante para este conjunto de procesadores.
De lo contrario, usted va a tener un hash mesa o una oportunidad que sólo va a ser
sólo una parte de las palabras que usted quieren y luego you're-- mmhmm?
AUDIENCIA: ¿Cuál fue el temporal Lo almacenamiento que hablabas?
ALTAVOZ 1: El almacenamiento temporal.
Así que, básicamente, otra manera usted puede hacer esto
se guarde la cabeza de algo, como almacenarlo la variable temporal.
Asigne a 1 y a continuación, actualice 1 para señalar
a lo que la cabeza utiliza para apuntar.
De esta manera es obviamente más elegante, ya que
no necesitan un valor temporal, pero sólo ofrecer otra manera de hacerlo.
Y que en realidad tienen algo de código para esto.
Así, por lista enlazada, nos en realidad tienen algo de código.
Así que insertar aquí, esto se anteponiendo.
Así que esto entra en él a la cabeza.
>> Así que lo primero, es necesario crear su nuevo nodo, por supuesto,
y compruebe que no NULL.
Siempre bueno.
Y entonces usted necesita para asignar los valores.
Cada vez que se crea un nuevo nodo, no saben lo que está apuntando a la siguiente,
por lo que desea inicializarlo a NULL.
Si no terminan apuntando a algo otra cosa, se reasignó y que está bien.
Si es lo primero en la lista, que necesita
para señalar a NULL porque ese es el final de la lista.
>> Así que para insertarlo, vemos aquí se asigna el siguiente valor de nuestro nodo
a ser lo que es la cabeza, que es lo que teníamos aquí.
Eso es lo que acabamos de hacer.
Y entonces estamos asignando la cabeza a punto a nuestro nuevo nodo, porque recuerde,
nueva alguna puntero a un nodo, y eso es exactamente lo que es la cabeza.
Eso es exactamente por eso que tener esta flecha de acceso.
Fresco?
Mmhmm?
>> AUDIENCIA: ¿Tenemos que inicializar nuevo junto a NULL en primer lugar,
o podemos simplemente inicializarlo a la cabeza?
>> ALTAVOZ 1: Nuevo próxima necesita ser NULL para comenzar
porque usted no sabe donde va a ser.
Además, esto es una especie de Al igual que un paradigma.
Se configura igual a NULL sólo para hacer Asegúrese de que todas las bases están cubiertas
antes de hacer cualquier cambio de destino de manera que usted siempre tiene la garantía de que así será
estar apuntando a un valor específico frente como un valor de la basura.
Porque, sí, asignamos nuevo siguiente de forma automática,
pero es más como un buena práctica inicializarlo
de esa manera y luego reasignar.
>> OK, así doblemente enlazada listas ahora.
¿Qué pensamos?
Lo que es diferente con doblemente enlazada listas?
>> Así que en nuestras listas enlazadas, podemos sólo se mueven en una dirección, ¿no?
Sólo tenemos al lado.
Sólo podemos seguir adelante.
>> Con una lista doblemente enlazada, también podemos mover hacia atrás.
Así que no sólo tenemos la número que queremos almacenar,
tenemos donde apunta a la siguiente y en el que sólo venimos.
Así que esto permite algunos mejor recorrido.
>> Así nodos doblemente enlazados, muy similar, ¿no?
La única diferencia es que ahora tener un lado y una anterior.
Es la única diferencia.
>> Así que si tuviéramos que anteponer o append-- nosotros no tienen ningún código para esto aquí--
pero si usted fuera a tratar de insertarlo, lo importante
es lo que necesita para hacer asegurarse de que está asignando
tanto su anterior y su siguiente puntero correctamente.
Así que en este caso, lo haría no sólo inicializar siguiente,
inicializar anterior.
Si estamos a la cabeza de la lista, no sólo hacer que la cabeza igual nueva,
pero debe nuestro nuevo anterior apuntar a la cabeza, ¿verdad?
>> Esa es la única diferencia.
Y si quieres más práctica con estos con listas enlazadas, con inserción,
con la supresión, con inserción en una lista de surtido,
por favor visite study.cs50.net.
Hay un montón de grandes ejercicios.
Lo recomiendo.
Ojalá hubiéramos tenido tiempo para ir a través de ellos pero hay una gran cantidad de estructuras de datos
conseguir a través.
>> Aceptar, por lo que las tablas hash.
Este es probablemente el más poco útil para el conjunto de procesadores
aquí porque usted va a ser la implementación de uno de estos, o un intento.
Me gusta mucho las tablas hash.
Son bastante fresco.
>> Así que, básicamente, lo que que pasa es una tabla hash
es cuando realmente necesitamos rápida inserción, eliminación y búsqueda.
Esas son las cosas que estamos priorizando en una tabla hash.
Pueden ser bastante grande, pero como veremos con tries,
hay cosas que son mucho más grandes.
>> Pero, básicamente, todo un hash tabla es una función hash
que te dice que cubo para poner cada uno de sus datos, cada uno de sus elementos en.
Una forma simple de pensar en una tabla hash es que es sólo cubos de cosas,
¿verdad?
Así que cuando usted está ordenando las cosas por como la primera letra de su nombre,
que es algo así como una tabla hash.
>> Así que si yo fuera a grupo de chicos es en grupos de todo el que de nombre comienza
con A por aquí, o quien sea el cumpleaños es en enero, febrero, marzo,
lo que sea, que es efectivamente la creación de una tabla hash.
Es sólo la creación de cubos que ordenar los elementos en
para que usted pueda encontrarlos más fácil.
Así de esta manera cuando necesito para encontrar uno de ustedes,
Yo no tengo que buscar a través de cada uno de sus nombres.
Yo puedo ser como, oh, yo sé que El cumpleaños de Danielle es en--
AUDIENCIA: --April.
ALTAVOZ 1: abril.
Así que me veo en mi abril cubo, y con un poco de suerte,
ella será la única en la que hay y mi tiempo era constante en ese sentido,
mientras que si tengo que buscar a través de un montón de gente,
que va a tomar mucho más tiempo.
Así tablas hash son realmente sólo cubos.
Una forma sencilla de pensar en ellos.
>> Así que una cosa muy importante sobre una tabla hash es una función hash.
Así que las cosas que acabo de hablar, al igual que su primera letra de su nombre
o su mes de cumpleaños, estas son ideas que
realmente correlacionar a una función hash.
Es sólo una manera de decidir qué usted balde es EL elemento entra en, ¿de acuerdo?
Así que para este conjunto de procesadores, puede mirar hacia arriba casi cualquier función hash que desea.
>> No tiene que ser la suya.
Hay algunos realmente fresco fuera hay que hacer todo tipo de loco matemáticas.
Y si usted desea hacer su corrector ortográfico súper rápido,
Sin duda, mirar en uno de esos.
>> Pero también la hay los simples, como el cómputo
la suma de las palabras, como cada letra tiene un número.
Calcule la suma.
Que determina el cubo.
También tienen las más fáciles que son al igual que todos los de un aquí,
todos los de la B es aquí.
Cualquiera de esos.
>> Básicamente, sólo se le dice que índice de la matriz de su elemento debe entrar.
Sólo decidir el bucket-- todo es una función de hash es.
Así que aquí tenemos un ejemplo que es sólo la primera letra de la cadena
que me estaba hablando.
>> Así que tienes un poco de hash que es sólo la primera letra de la cadena de menos A,
que le dará un poco de número entre 0 y 25.
Y lo que quieres hacer es asegurarse de que esto representa
el tamaño de su picadillo table-- cuántos cubos hay.
Con muchos de estos funciones hash, que son
va a ser la devolución de valores que podrían estar muy por encima del número de cubos
que usted realmente tiene en su tabla hash,
por lo que necesita para hacer Seguro y mod por aquellos.
De lo contrario, va a decir, oh, debe ser en balde 5000
pero sólo tiene 30 cubos en su tabla hash.
Y, por supuesto, todos sabemos que es va a dar lugar a algunos errores de locos.
Así que asegúrese de mod por el tamaño de la tabla hash.
Enfriar.
Así colisiones.
¿Están todos bien hasta ahora?
Mmhmm?
>> AUDIENCIA: ¿Por qué se devolver un valor tan masiva?
>> ALTAVOZ 1: Dependiendo del algoritmo que su función hash utiliza.
Algunos de ellos lo hará multiplicación loco.
Y es todo sobre conseguir una distribución uniforme,
por lo que hacen algunos realmente locuras a veces.
Eso es todo.
Algo más?
Okay.
>> Así colisiones.
Básicamente, como he dicho antes, en el mejor de los casos,
cualquier cubo miro en es va a tener una cosa,
así que no tengo que mirar a todos, ¿verdad?
Yo bien sé que está ahí o es no, y eso es lo que realmente queremos.
Pero si tenemos decenas de miles de los puntos de datos y menos de ese número
de cubos, que vamos a tener colisiones donde finalmente algo
se va a tener que terminar en un cubo que ya cuenta con un elemento.
>> Así que la pregunta es, ¿qué Qué hacemos en ese caso?
¿Qué hacemos?
Ya tenemos algo allí?
¿Nos echamos un vistazo?
>> No.
Tenemos que mantener los dos.
Así que la forma en que suelen hacerlo es lo que?
¿Cuál es la estructura de datos que acabamos de hablar?
AUDIENCIA: lista Vinculado.
ALTAVOZ 1: Una lista enlazada.
Así que ahora, en lugar de cada uno de estos cubos sólo tener un elemento,
que va a contener una lista enlazada de los elementos que fueron ordenada en ella.
Bueno, no todo el mundo clase de esa idea?
Debido a que no podíamos tener una matriz porque no sabemos cuántas cosas
van a estar ahí.
Una lista enlazada nos permite tener sólo el número exacto que
se hash en ese cubo, ¿verdad?
>> Así sondeo lineal es básicamente esta idea--
es una manera de hacer frente a una colisión.
Lo que puede hacer es si, en este caso, baya fue ordenada en 1
y ya tenemos algo ahí, sólo
seguir bajando hasta a encontrar una ranura vacía.
Esa es una manera de manejar la situación.
La otra manera de manejar que es con lo que acabamos de
called-- el vinculado lista se llama encadenamiento.
>> Así que esta idea funciona si su tabla hash usted piensa
es mucho mayor que su conjunto de datos o si
quieren tratar de minimizar el encadenamiento hasta que sea absolutamente necesario.
Así que una cosa es lineal sondeo obviamente significa
que su función hash no es tan útil
porque vas a terminar con su función hash, llegando a un punto,
le LINEAL sondea hasta algún lugar que está disponible.
Pero ahora, por supuesto, cualquier cosa otra cosa que termina allí,
usted va a tener que buscar incluso más abajo.
>> Y hay mucho más expensas de búsqueda que
entra en la introducción de un elemento en su tabla hash ahora, ¿verdad?
Y ahora cuando vas y tratas de encontrar baya de nuevo, vas a hash de ella,
y que va a decir, oh, mira en el cubo 1,
y no va a ser en cubo 1, por lo que es
va a tener que atravesar por el resto de estos.
Así que a veces es útil, pero en la mayoría de los casos,
vamos a decir que El encadenamiento es lo que quieres hacer.
>> Así que hablamos de esto antes.
Me puse un poco por delante de mí mismo.
Pero el encadenamiento es básicamente que cada cubo en su tabla hash
es sólo una lista enlazada.
>> Así que de otra manera, o más técnico manera, pensar en una tabla hash
es que es sólo un arreglo de las listas enlazadas, que
cuando usted está escribiendo su diccionario y usted está tratando de cargarlo,
pensar en ello como una variedad de listas enlazadas
hará que sea mucho más fácil para inicializar.
>> AUDIENCIA: Así tabla hash tiene un tamaño predeterminado,
como un [inaudible] de cubos?
>> ALTAVOZ 1: Derecho.
Por lo tanto, tiene un número determinado de cubos que determine--
que ustedes deben sentirse libre para jugar.
Puede ser muy bien a ver qué pasa
a medida que cambia su número de cubos.
Pero sí, tiene una establecer el número de cubos.
Lo que le permite ajustar como muchos elementos que usted necesita
es este encadenamiento separado donde han vinculado las listas en cada cubo.
Esto significa que su tabla hash será exactamente el tamaño
que usted necesita que sea, ¿no?
Ese es todo el punto de las listas enlazadas.
Enfriar.
>> Así que todo el mundo bien allí?
Bien.
Ah.
¿Qué acaba de suceder?
Realmente ahora.
Supongo que alguien me está matando.
>> Aceptar que vamos a entrar en tries, que son un poco loco.
Me gusta tablas hash.
Creo que son muy cool.
Tries son frescas, también.
>> Así que ¿alguien recuerda lo que es una oportunidad?
Usted debería haber ido más brevemente en la conferencia?
¿Te acuerdas de clase de cómo funciona?
AUDIENCIA: Sólo estoy asintiendo que nos fuimos por encima.
ALTAVOZ 1: Nosotros vamos sobre ella.
Bueno, realmente vamos a ir sobre ella ahora es lo que estamos diciendo.
>> AUDIENCIA: Eso es para un árbol de recuperación.
>> ALTAVOZ 1: Sí.
Es un árbol de la recuperación.
Impresionante.
Así que una cosa a notar aquí es que nosotros están mirando a caracteres individuales
aquí, ¿verdad?
>> Así que antes con nuestra función de hash, que estaban mirando las palabras en su conjunto,
y ahora estamos buscando más a los personajes, ¿no?
Así que tenemos Maxwell aquí y Mendel.
Así que, básicamente, un try-- una manera de pensar de esto es que todos los niveles aquí
es una serie de letras.
Así que este es su nodo raíz aquí, ¿verdad?
Esto tiene todos los caracteres de la alfabeto para el inicio de cada palabra.
>> Y lo que quieres hacer es por ejemplo, OK, tenemos alguna palabra M.
Vamos a buscar a Maxwell, por lo que vamos a los puntos M. y M a un todo
otro una matriz en la que cada palabra, mientras haya
es una palabra que tiene un como la segunda carta,
siempre y cuando no hay una palabra que tiene B como la segunda carta,
que tendrá un puntero ir a algún lado array.
>> Probablemente no es un palabra que MP algo,
por lo que en la posición P en este matriz, que sólo sería NULL.
Se diría, está bien, no hay una palabra que ha seguido de una M P, ¿de acuerdo?
Así que si lo pensamos bien, cada una de estas cosas más pequeñas
es en realidad uno de ellos grandes conjuntos de la A a la Z.
Así que lo que podría ser una de las cosas que es una especie de inconveniente de una oportunidad?
>> AUDIENCIA: Una gran cantidad de memoria.
>> ALTAVOZ 1: Es una tonelada de memoria, ¿verdad?
Cada uno de estos bloques aquí representa 26 espacios, 26 elemento de la matriz.
Así que intenta conseguir espacio increíblemente pesado.
>> Pero ellos son muy rápidos.
Tan increíblemente rápido, pero realmente espacio ineficiente.
Tipo de tener que averiguar a cuál de ellos desea.
Estos son realmente fresco para su conjunto de procesadores, pero sí tener una gran cantidad de memoria,
por lo que el comercio fuera.
¿Sí?
>> AUDIENCIA: ¿Sería posible la creación de una oportunidad y luego
una vez que tenga toda la datos en él que usted need--
No sé si eso tiene sentido.
Me va a deshacer de todo el Caracteres NULL, pero a continuación,
usted no sería capaz de indexar ellos--
>> ALTAVOZ 1: Usted todavía los necesitan.
>> AUDIENCIA: - de la misma manera cada vez.
ALTAVOZ 1: Sí.
Usted necesita los caracteres NULL para que Cómo saber si no hay una palabra allí.
Ben no tienes algo que quieres?
Okay.
Muy bien, así que vamos para ir un poco más
en los detalles técnicos detrás un tratar de trabajar a través de un ejemplo.
>> Aceptar, por lo que esta es la misma cosa.
Mientras que en una lista enlazada, nuestra principal tipo de-- ¿cuál es la palabra que quiero? -
como la construcción de bloque era un nodo.
En una oportunidad, también tenemos un nodo, pero se define de manera diferente.
>> Así que tenemos algunos bool que representa si una palabra en realidad
existe en esta ubicación, y luego tenemos algo de variedad aquí-- o más bien,
este es un puntero a una serie de 27 caracteres.
Y esto es para, en este caso, esta 27-- Estoy seguro de que todos ustedes son como, espero,
hay 26 letras en el alfabeto.
¿Por qué tenemos 27?
>> Así que dependiendo de la forma de implementar esto,
esto es de un conjunto de procesadores que permitió apóstrofes.
Así que por eso el uno extra.
También tendrá en algunos casos, el terminador nulo
se incluye como una de las personajes que prohibe ser,
y eso es lo que verifican ver si es el final de la palabra.
Si estás interesado, visita Vídeo de Kevin en study.cs50,
así como Wikipedia tiene algunos buenos recursos allí.
>> Pero vamos a ir a través de sólo un poco de cómo se puede trabajar a través de un try
si te dan una.
Así que tenemos un super sencillo aquí que tiene la palabra "bat" y "zoom" en ellos.
Y como vemos aquí, este pequeño espacio aquí
representa nuestra bool que dice, sí, esta es una palabra.
Y entonces esto tiene nuestra matrices de caracteres, ¿no?
>> Así que vamos a ir a través de la búsqueda de "murciélago" en este intento.
Así que comience por la parte superior, a la derecha?
Y sabemos que B corresponde a el segundo índice, el segundo elemento
en esta matriz, debido a y b.
Así que aproximadamente el segundo.
>> Y dice, bien, fresco, se sigue que en la siguiente matriz, ya que si recordamos,
no es que cada uno de estos en realidad contiene el elemento.
Cada una de estas matrices contiene un puntero, ¿verdad?
Es una distinción importante que hacer.
>> Sé que esto va a ser: tries son muy difícil de conseguir en la primera vez,
por lo que incluso si este es el segunda o tercera vez
y es todavía tipo de parecer difícil,
Te prometo que si vas reloj la mañana de nuevo a corto,
es probable que va a hacer mucho más sentido.
Se necesita mucho para digerir.
Todavía a veces soy como, espera, lo que es una oportunidad?
¿Cómo utilizo esto?
>> Así que hemos B en este caso, que es nuestro segundo índice.
Si tuviéramos, por ejemplo, o c d o cualquier otra letra,
tenemos que mapear que volver al índice de nuestra matriz que que corresponde a.
Así que tomaríamos como rchar y sólo restar de una a Localizar en un mapa en 0 a 25.
Todo el mundo bien cómo mapear nuestros personajes?
Okay.
>> Así que vamos a la segunda, y que ver que, sí, no es NULL.
Podemos pasar a esta nueva matriz.
Así que pasamos a esta próxima serie aquí.
>> Y decimos, bien, ahora nos que tenga que ver si a es aquí.
Es un valor nulo o lo hace realmente avanzar?
Así que una se mueve realmente hacia adelante en esta serie.
Y decimos, OK, t es nuestra última carta.
Así que vamos a la t en el índice.
Y luego nos movemos hacia adelante porque no hay otro.
Y éste dice básicamente que, sí, se dice que hay una palabra aquí--
que si usted sigue este camino, usted ha llegado
en una palabra, que sabemos que es "murciélago".
¿Sí?
>> AUDIENCIA: ¿Es normal tener que como el índice 0 y luego tener una especie en 1
o para que al final?
>> ALTAVOZ 1: No.
Así que si miramos hacia atrás en nuestra declaración aquí, es un bool,
por lo que es su propio elemento en su nodo.
Así que no es parte de la matriz.
Enfriar.
Así que cuando terminemos nuestra palabra y estamos en esta matriz, lo que queremos hacer
es hacer un cheque por esta es una palabra.
Y en este caso, sería volver sí.
>> Así que en ese sentido, sabemos que "zoo" - que conocemos como seres humanos que "zoo" es una palabra,
¿verdad?
Pero se trate de aquí sería decir, no, no lo es.
Y diría que debido a que no han designado como una palabra aquí.
A pesar de que podemos atravesar a través de esta matriz,
este intento diría que no, zoológico no está en su diccionario
porque nosotros no tenemos designada como tal.
>> Así que una manera de hacerlo que-- oh, lo siento, esta.
Así que en este caso, "zoo" no es una palabra, pero está en nuestro intento.
Pero en éste, decimos que queremos que introducir la palabra "baño", lo que sucede
es que seguimos through-- b, a, t.
Estamos en esta matriz, y vamos a buscar h.
>> En este caso, cuando mirar el puntero en h,
está apuntando a NULL, ¿de acuerdo?
Así que a menos que sea explícitamente apuntando a otra matriz,
usted asume que todos los punteros en esta matriz están apuntando a null.
Así pues, en este caso, h está apuntando para anular lo que no podemos hacer nada,
por lo que también sería volver falsa, "baño" no es aquí.
Así que ahora estamos en realidad va a ir a través de
¿cómo podemos realmente decir que "zoo" es en nuestro intento.
¿Cómo nos insertamos "zoo" en nuestro intento?
Así que de la misma manera que comenzamos con nuestra lista enlazada, que comienzan en la raíz.
En caso de duda, comience en la raíz de estas cosas.
>> Y vamos a decir, OK, z.
existe z en esto, y lo hace.
Así que usted está de pasar a su siguiente serie, ¿de acuerdo?
Y a continuación, en la siguiente, decimos, bien, sí existe o?
Lo hace.
Esto de nuevo.
>> Y así, en nuestro próximo uno, que hemos dicho, Aceptar, "zoo" ya existe aquí.
Todo lo que necesitamos hacer es establecer esta igualdad a la verdadera, que no es una palabra allí.
Si hubieras seguido todo hasta antes de ese punto,
se trata de una palabra, por lo que sólo configurarlo igual a tales.
¿Sí?
>> AUDIENCIA: Entonces sí que significa que "ba" es una palabra también?
>> ALTAVOZ 1: No.
Así que en este caso, "ba" obtendríamos aquí, diríamos que es una palabra,
y aún sería no.
¿De acuerdo?
Mmhmm?
>> AUDIENCIA: Así que una vez que se trata de una palabra y dice que sí, entonces
contendrá ir al m?
>> ALTAVOZ 1: Así que esto tiene que ver con-- va a cargar esto en.
Usted dice "zoo" es una palabra.
Cuando usted va a check-- como, digamos que usted quiere decir,
existe "zoo" en este diccionario?
Sólo vas a buscar "zoológico" y después comprobar para ver si se trata de una palabra.
Nunca vas a moverse a través de m porque eso no es
lo que estás buscando.
>> Así que si realmente queríamos añadir "baño" en este intento,
que íbamos a hacer lo mismo como lo hicimos con "zoo"
excepto veríamos que cuando nos tratar de llegar a h, que no existe.
Así que usted puede pensar en esto como tratando para agregar un nuevo nodo en una lista enlazada,
por lo que tendríamos que añadir otro una de estas matrices, como tal.
Y entonces lo que hacemos es apenas fijamos el h elemento de esta matriz que apunta a esto.
>> Y entonces, ¿qué íbamos a querer hacer aquí?
Añádelo igual a verdadero porque es una palabra.
Enfriar.
Lo sé.
Intentos no son las más emocionantes.
Confía en mí, lo sé.
>> Así que una cosa que se da cuenta con tries, Yo dije, son muy eficientes.
Así que hemos visto que llevar hasta una tonelada de espacio.
Están un poco confuso.
Así que ¿por qué habríamos nunca utilizar estos?
Utilizamos estos porque son increíblemente eficiente.
>> Así que si estás buscando alguna vez una palabra, usted es sólo
limitada por la longitud de la palabra.
Así que si usted está buscando un palabra que tiene una longitud de cinco,
usted está solo nunca va a tener que hacer en la mayoría de los cinco comparaciones, ¿de acuerdo?
Por lo tanto, hace que sea básicamente una constante.
Al igual que la inserción y búsqueda son básicamente constante de tiempo.
>> Así que si alguna vez se puede obtener algo en el tiempo constante,
eso es tan bueno como se pone.
No puede ser mejor que constante de tiempo para estas cosas.
Así que ese es uno de los enormes ventajas de intentos.
>> Pero es un montón de espacio.
Así que tipo de tener que decidir lo que es más importante para ti.
Y en los ordenadores de hoy en día, la espacio que una oportunidad puede tomar hasta
tal vez no afecta que mucho, pero tal vez
usted está tratando con algo que tiene mucho, mucho más las cosas,
y una oportunidad simplemente no es razonable.
¿Sí?
>> AUDIENCIA: Espere, por lo que tiene 26 letras en cada uno?
>> ALTAVOZ 1: Mmhmm.
Sí, usted tiene 26.
Usted tiene algunos es marcador de palabra y después usted tiene 26 punteros en cada uno.
Y están point--
>> AUDIENCIA: Y cada 26, es lo que cada uno tiene 26?
>> ALTAVOZ 1: Sí.
Y es por eso, que pueda ver, se expande muy rápidamente.
Bien.
Así que vamos a entrar en los árboles, que Me siento como es más fácil y probablemente
ser un pequeño respiro de tries allí.
Así que espero que la mayoría de ustedes han visto un árbol antes.
No como el bonito los exteriores, que yo
no sé si alguien se fue al aire libre recientemente.
Fui recolección de manzanas este fin de semana, y, ¡oh, Dios mío, que era preciosa.
Yo no sabía hojas podría mirar que bonita.
>> Así que esto es sólo un árbol, ¿no?
Es sólo un poco de nodo, y apunta a un montón de otros nodos.
Como se ve aquí, este es tipo de un tema recurrente.
Los nodos que apunta a los nodos es una especie de la esencia de muchas estructuras de datos.
Sólo depende de la forma en que tienen ellos señalan el uno al otro
y cómo atravesamos a través de ellos y la forma en que
insertar las cosas que determina sus diferentes características.
>> Así que sólo algunos de los términos, que he usado antes.
Así que la raíz es lo que está en la parte superior.
que es donde siempre empezamos.
Usted puede pensar en él como la cabeza también.
Pero para los árboles, tendemos a se refieren a ella como la raíz.
>> Cualquier cosa en la parte inferior aquí-- en el muy, muy bottom--
son considerados hojas.
Por lo tanto, va de la mano con la Lo árbol entero, ¿no?
Las hojas son en los bordes de su árbol.
>> Y luego también tenemos un par de términos para hablar de nodos de relación
el uno al otro.
Así que tenemos los padres, hijos y hermanos.
Así pues, en este caso, 3 es el matriz de 5, 6, y 7.
Así que el padre es lo que es un paso por encima de lo que sea que estés
en referencia a, por lo que sólo como un árbol genealógico.
Con suerte, esto es todo un poco poco más intuitivo que los intentos.
>> Los hermanos son cualquiera que tenga el mismo padre, ¿verdad?
Están en el mismo nivel aquí.
Y entonces, como yo diciendo, los niños son sólo
lo que es un paso por debajo el nodo en cuestión, ¿de acuerdo?
Enfriar.
Así, un árbol binario.
¿Alguien puede aventurar una respuesta en uno de las características del árbol binario?
>> AUDIENCIA: Max dos hojas.
>> ALTAVOZ 1: Derecho.
Así máximo de dos hojas.
Así que en esto antes, tuvimos éste que tenía tres, pero en un árbol binario,
Tiene un máximo de dos hijos por los padres, ¿no?
Hay otro característica interesante.
¿Alguien sabe que?
Árbol binario.
>> Así que un árbol binario tendrá todo en el-- éste no es sorted--
pero en un árbol binario ordenado, todo a la derecha
es mayor que la de los padres, y todo a la izquierda
es menor que la de los padres.
Y eso ha sido un concurso cuestión que, por lo bueno saber.
Así que la forma en que definimos esto, una vez más, tenemos otro nodo.
Esto se ve muy similar a lo que?
Doblemente
>> AUDIENCIA: Vinculado listas
>> ALTAVOZ 1: Una lista enlazada doble, ¿no?
Así que si reemplazamos este con anterior y siguiente,
esto sería una lista doblemente enlazada.
Pero en este caso, en realidad tener a la izquierda y la derecha y eso es todo.
De lo contrario, es exactamente el mismo.
Todavía tenemos el elemento que usted está buscando,
y sólo hay dos punteros ir a lo que se viene.
Sí, así binario árbol de búsqueda.
Si nos damos cuenta, todo en el aquí es mayor no sea:
o todo inmediatamente a la derecha aquí
es mayor que, todo aquí es inferior.
>> Así que si tuviéramos que buscar a través, que debe mirar muy cerca de búsqueda binaria
aquí, ¿verdad?
Excepto que en vez de mirar a la mitad de la matriz,
sólo estamos buscando, ya sea en la izquierda lado o del lado derecho del árbol.
Así que se pone un poco más simple, creo.
>> Así que si su raíz es NULL, obviamente es sólo falsa.
Y si está allí, obviamente, es la verdad.
Si es menor que, buscamos la izquierda.
Si es mayor que, buscamos la derecha.
Es exactamente igual que la búsqueda binaria, sólo una estructura de datos diferente
que estamos usando.
En lugar de una matriz, es sólo un árbol binario.
>> Aceptar, pilas.
Y también, parece que podría tener un poco de tiempo.
Si lo hacemos, estoy feliz de ir sobre cualquiera de esto otra vez.
OK, así que pilas.
¿Alguien recuerda lo que stacks-- cualquier característica de una pila?
>> Aceptar, por lo que la mayoría de nosotros, creo, comer en el comedor halls--
tanto como es posible que no les gusta.
Pero, obviamente, se puede pensar en una pila literalmente, al igual que una pila de bandejas
o una pila de cosas.
Y lo que es importante es darse cuenta de que es
algo-- la característica que nosotros llamamos por-- es LIFO.
¿Alguien sabe lo que eso representa?
Mmhmm?
>> AUDIENCIA: último en entrar, primero en salir.
>> ALTAVOZ 1: Derecha, último en entrar, primero en salir.
Así que si sabemos, si estamos apilando cosas arriba, la cosa más fácil de agarrar off--
y tal vez el único que puede tomar fuera si nuestra pila es grande enough--
es que elemento superior.
Así que cualquier cosa se puso en last-- como vemos aquí,
lo que fue empujado en la mayoría recently-- es
va a ser el primero cosa que nos pop fuera, ¿de acuerdo?
>> Así que lo que tenemos aquí es otro struct typedef.
Esto es realmente sólo como un Curso acelerado en la estructura de datos,
así que hay un montón lanzada contra ustedes.
Lo sé.
Así otra struct.
Yay para estructuras.
>> Y en este caso, se trata de algún puntero a una matriz que tiene una cierta capacidad.
Así que esto representa nuestra pila aquí, al igual que nuestra gama actual
eso es la celebración de nuestros elementos.
Y entonces aquí tenemos algo de tamaño.
>> Y por lo general, que desea conservar pista de cuán grande es su pila es
porque lo que va a permitir usted pueda hacer es si usted sabe el tamaño,
que le permite decir, Bien, ¿estoy en capacidad?
¿Puedo añadir algo más?
Y también te dice donde la parte superior de la pila
es por lo que usted sabe lo que en realidad puede despegar.
Y eso es en realidad va a ser un poco más claro aquí.
>> Así, por empuje, una cosa, si usted fueron nunca para aplicar empuje,
como yo estaba diciendo, su pila tiene un tamaño limitado, ¿verdad?
Nuestra gama tenía alguna capacidad.
Es una matriz.
Es un tamaño fijo, por lo que necesitamos asegurarse de que no estamos poniendo más
en nuestra gama de lo que en realidad tienen espacio para.
>> Así que cuando usted está creando un empuje función, lo primero que haces es decir, OK,
¿tengo espacio en mi pila?
Porque si no lo hago, lo siento, No puedo guardar el elemento.
Si lo hago, entonces usted desea almacenar en la parte superior de la pila, ¿no?
>> Y es por eso que tenemos hacer un seguimiento de nuestro tamaño.
Si no mantenemos un registro de nuestro tamaño, no sabemos dónde ponerlo.
No sabemos cuántas cosas están en nuestra gama ya.
Al igual que, obviamente, hay formas que tal vez usted podría hacerlo.
Usted podría inicializar todo a NULL y luego comprobar si la última NULL,
pero una cosa mucho más fácil es simplemente decir, OK, no perder de vista el tamaño.
Al igual que yo sé que tengo cuatro elementos en mi matriz, por lo que la siguiente cosa
que nos ponemos, estamos va a almacenar en el índice 4.
Y entonces, por supuesto, esto significa que usted ha empujado con éxito algo
en su pila, desee aumentar el tamaño
para que usted sepa donde usted está tan que usted puede empujar más cosas sobre.
>> Así que si estamos tratando de hacer estallar algo fuera de la pila,
lo que podría ser la primera cosa que queremos comprobar?
Usted está tratando de tomar algo fuera de su pila.
¿Estás seguro de que hay algo en su pila?
No.
Entonces, ¿qué podríamos querer comprobar?
>> AUDIENCIA: [inaudible].
ALTAVOZ 1: Verifique el tamaño?
Tamaño.
Así que queremos comprobar para ver si nuestro tamaño es mayor que 0, ¿de acuerdo?
Y si lo es, entonces queremos disminuir nuestro tamaño por 0 y volver eso.
¿Por qué?
>> En la primera estábamos empujar, nos empujamos
en tamaño y tamaño entonces actualizado.
En este caso, estamos decrementar el tamaño y luego quitárselo, desplumado que
de nuestra matriz.
¿Por qué podríamos hacer eso?
Así que si tengo una cosa en mi pila, lo que sería el tamaño de mi en ese momento?
1.
>> ¿Y dónde está el elemento 1 se almacena?
¿A qué índice?
AUDIENCIA: 0.
ALTAVOZ 1: 0.
Así que en este caso, Siempre que tenga que hacer sure--
en lugar de regresar tamaño de menos 1, ya que
sabe que es nuestro elemento va a ser almacenado en un menor
cualquiera que sea nuestro tamaño es, esta sólo se ocupa de ella.
Es una manera un poco más elegante.
Y acabamos nuestra decrementamos tamaño y luego regresar tamaño.
Mmhmm?
>> AUDIENCIA: Creo que sólo en general, ¿por qué esta estructura de datos
ser beneficioso?
>> ALTAVOZ 1: Depende de su contexto.
Así que para algunos de la teoría, si está trabajando con-- Aceptar,
déjame ver si hay un uno beneficioso que es beneficioso para más de fuera
de CS.
Con pilas, cualquier momento usted necesita hacer un seguimiento de algo que
es el más recientemente añadido es cuando usted va a querer usar una pila.
>> Y no puedo pensar en una buena ejemplo de eso en este momento.
Pero cada vez que el más reciente Lo que es más importante para usted,
que es cuando una pila va a ser de utilidad.
Estoy tratando de pensar si hay un buen año para esto.
Si pienso en un buen ejemplo en la siguiente 20 minutos, que sin duda le dirá.
>> Pero en general, si hay algo, como he dicho más, donde más reciente
es más importante, eso es donde una pila entra en juego.
Mientras que las colas son un poco lo contrario.
Y todos los pequeños perros.
¿No es genial, ¿verdad?
Me siento como que debería sólo hay un video conejito
justo en el medio de sección para ustedes
porque esta es una sección intensa.
>> Así que una cola.
Básicamente una cola es como una línea.
Ustedes Estoy seguro de que este uso cotidiano, al igual que en nuestros comedores.
Así que tenemos que ir en y tener en nuestras bandejas, estoy
Seguro que tienes que esperar en línea para deslizar o conseguir su comida.
>> Así que la diferencia aquí es que esto es FIFO.
Así que si LIFO la última en entrar, primero cabo, FIFO es primero en entrar, primero en salir.
Así que aquí es donde lo que pones el primero es el más importante.
Así que si estabas esperando en un line-- ¿verdad
imagínese si usted fue a ir a buscar el nuevo iPhone
y era una pila donde el última persona de la fila lo consiguió en primer lugar,
personas matarían entre sí.
>> Así FIFO, estamos todos muy familiar con en el mundo real aquí,
y todo tiene que ver con la realidad especie de recreación de toda esta línea
y colas estructura.
Así que mientras que con la pila, tenemos empuje y el pop.
Con una cola, tenemos enqueue y quitar de la cola.
Así que, básicamente, significa enqueue lo puso en la parte trasera,
y medios dequeue toman fuera de la parte delantera.
Así que nuestra estructura de datos es un poco más complicado.
Tenemos un segundo que hay que seguir la pista.
>> Así que sin la cabeza, este es exactamente una pila, ¿no?
Esta es la misma estructura que una pila.
Lo único diferente es que ahora tener esta cabeza, que ¿qué te parece
se va a realizar un seguimiento de?
>> AUDIENCIA: El primero.
>> ALTAVOZ 1: Derecho, la Lo primero que nos pusimos en.
El jefe de nuestra cola.
El que es primero en la fila.
Muy bien, así que si lo hacemos en cola.
Una vez más, con cualquiera de estas estructuras de datos,
ya que estamos tratando con una matriz, tenemos que comprobar si tenemos espacio.
>> Esto es algo así como diciéndome ustedes, si se abre un archivo,
usted necesita para comprobar nula.
Con cualquiera de estas pilas y las colas, que necesitan
para ver si hay espacio porque somos tratar con una matriz de tamaño fijo,
como vemos aquí-- 0, 1 todo hasta 5.
Así que lo que hacemos en ese caso es cheque para ver si todavía tenemos espacio.
Es nuestro tamaño menor que la capacidad?
>> Si es así, tenemos que lo conserve en su la cola y actualizamos nuestro tamaño.
Entonces, ¿cuál podría ser la cola en este caso?
No está escrito explícitamente.
¿Cómo podríamos almacenarla?
¿Cuál sería la cola?
>> Así que vamos a caminar a través de este ejemplo.
Así que esta es una matriz de tamaño 6, ¿no?
Y tenemos en este momento, nuestro tamaño es 5.
Y cuando lo ponemos en, va para entrar en el quinto índice, ¿no?
Así que almacenar en la cola.
>> Otra forma de escribir cola haría sólo sea ​​nuestro arsenal en el índice de tamaño, ¿no?
Este es el tamaño 5.
Lo siguiente que se va a ir a 5.
Fresco?
Okay.
Se pone un poco más complicado cuando empezamos a jugar con la cabeza.
¿Sí?
>> AUDIENCIA: ¿Significa que tenemos que habría declarado una matriz que
fue cinco elementos de largo y entonces estamos añadiendo en él?
>> ALTAVOZ 1: No.
Así pues, en este caso, se trata de una pila.
Este sería declarado como una matriz de tamaño 6.
Y en este caso, sólo hay una plaza de izquierda.
>> Aceptar, por lo que una cosa es en este caso, si nuestra cabeza está en 0,
entonces sólo podemos añadir que en del mismo tamaño.
Pero se pone un poco más complicado porque en realidad,
no tienen una diapositiva para esto, así que voy
para dibujar una porque no es tan sencillo una vez que
empezar a deshacerse de las cosas.
Así que mientras que con una pila para que sólo tenga
que preocuparse por lo que el tamaño es cuando va a añadir algo sobre,
con una cola también tiene que hacer Asegúrese de que su cabeza se contabiliza,
porque una cosa divertida acerca de las colas es que si usted no está en capacidad,
en realidad se puede hacer que sea envolver alrededor.
>> Aceptar, por lo que uno cosa-- oh, esto es terrible tiza.
Una cosa a tener en cuenta es el caso.
Haremos sólo cinco.
OK, así que vamos a dicen que la cabeza está aquí.
Esta es 0, 1, 2, 3, 4.
>> La cabeza está ahí, y por favor tenga cosas en ellos.
Y queremos añadir algo, ¿no?
Así que lo que necesitamos saber es que la cabeza es siempre
va a mover de un lado a entonces bucle alrededor, ¿de acuerdo?
>> Así que esta cola dispone de espacio, ¿no?
Tiene espacio en el principio, clase de lo contrario de esto.
Así que lo que tenemos que hacer es que que calcular la cola.
Si usted sabe que su la cabeza no se ha movido, cola
es sólo su matriz en el índice del tamaño.
>> Pero en realidad, si usted está utilizando una cola, su cabeza, probablemente se está actualizando.
Así que lo que hay que hacer es realmente calcular la cola.
Así que lo que hacemos es la siguiente fórmula aquí, que voy a dejarte
chicos piensan acerca de, y entonces vamos a hablar de ello.
Así que esta es la capacidad.
>> Así que esto lo hará realidad le dará una forma de hacerlo.
Debido a que en este caso, ¿qué?
Nuestra cabeza está en 1, nuestro tamaño es 4.
Si mod que por 5, obtenemos 0, que es donde debe ingresar la misma.
>> Así que en el siguiente caso, si tuviéramos que hacer esto,
decimos, OK, vamos a quitar de la cola algo.
Nos dequeue esto.
Tomamos un vistazo a este elemento, ¿no?
>> Y ahora nuestra cabeza está señalando aquí, y queremos añadir en otra cosa.
Esta es básicamente la parte de atrás de nuestra línea, ¿verdad?
Las colas pueden envolver alrededor de la matriz.
Esa es una de las principales diferencias.
Pilas, usted no puede hacer esto.
>> Con las colas, se puede porque todo lo que importa
es que usted sabe lo que se añadió más recientemente.
Ya que todo va a ser añadido en esta dirección hacia la izquierda, en este caso,
y luego envolver alrededor, usted puede seguir poniendo en nuevos elementos
en la parte delantera de la matriz porque no es realmente
la parte delantera de la matriz más.
Usted puede pensar en el inicio de la matriz como cuando la cabeza es en realidad.
>> Así que esta fórmula es cómo calcular su cola.
¿Eso tiene sentido?
Okay.
Aceptar, quitar de la cola, y luego ustedes tienen 10 minutos
en hacer cualquier preguntas aclaratorias que quieres, porque sé que es una locura.
>> Muy bien, por lo que en la misma manera-- No sé si ustedes se dio cuenta,
pero CS tiene que ver con los patrones.
Las cosas son más o menos la mismo, sólo con pequeños retoques.
Así mismo aquí.
Tenemos que comprobar para ver si en realidad tienen algo en nuestra cola, ¿no?
Diga, OK, es nuestro tamaño mayor que 0?
Enfriar.
>> Si lo hacemos, entonces nos movemos nuestra cabeza, que es lo que acaba de demostrarse aquí.
Actualizamos nuestra cabeza para ser uno más.
Y luego nos decrementamos nuestra tamaño y devolver el elemento.
>> Hay mucho más concreto código en study.cs50.net,
y yo recomiendo ir a través de él si tienes tiempo,
incluso si es sólo un pseudo-código.
Y si ustedes quieren hablar a través de que conmigo uno a uno, por favor me deja
saber.
Yo estaría encantado de.
Las estructuras de datos, si usted toma CS 124, podrás
saben que las estructuras de datos se ponen muy diversión y esto recién empieza.
>> Así que sé que es difícil.
Está bien.
Luchamos.
Yo todavía lo hago.
Así que no te preocupes demasiado por ello.
>> Pero eso es básicamente su Curso acelerado en las estructuras de datos.
Sé que es mucho.
¿Hay algo que nos le gustaría ir otra vez?
Cualquier cosa que queremos hablar a través de?
¿Sí?
>> AUDIENCIA: Para ese ejemplo, por lo que la nueva cola es a 0 sobre eso?
ALTAVOZ 1: Sí.
AUDIENCIA: OK.
Así que ir a través de, tendrías 1 más 4 o--
>> ALTAVOZ 1: Por lo que estaban diciendo, cuando queremos ir a hacer esto otra vez?
AUDIENCIA: Sí.
Así que si estás calculando fuera-- dónde están que el cálculo de la cola de en eso?
>> ALTAVOZ 1: Así que la cola Estaba en-- cambié esto.
Así que en este ejemplo aquí, esto era la matriz que estamos viendo, ¿de acuerdo?
Así que tenemos cosas en 1, 2, 3, y 4.
Así que tenemos nuestra cabeza es igual a 1 en este punto, y nuestro tamaño es igual a 4
en este punto, ¿no?
>> Usted acepta que todo es el caso?
Así que hacemos la cabeza, más el tamaño, lo que nos da 5, y luego nos MOD por 5.
Obtenemos 0, lo que nos dice que 0 es ¿dónde está nuestra cola, donde tenemos espacio.
>> AUDIENCIA: ¿Qué es un casquillo?
>> ALTAVOZ 1: La capacidad.
Lo siento.
Así que ese es el tamaño de su arsenal.
¿Sí?
>> AUDIENCIA: [inaudible] antes volvemos el elemento?
>> ALTAVOZ 1: Así que movemos el dirigirse o volver el momento?
Así que si nos movemos uno, disminuir el tamaño?
Espere.
Definitivamente me olvidé otra.
No importa.
No hay otra fórmula.
Sí, usted quiere volver la cabeza y luego se movió hacia atrás.
>> AUDIENCIA: OK, porque en este punto, la cabeza estaba a 0,
y luego desea volver el índice 0 y luego hacer la cabeza 1?
>> ALTAVOZ 1: Derecho.
Creo que hay otra fórmula algo así como esto.
Yo no lo tengo en la parte superior de mi cabeza como No quiero darte la equivocada.
Pero creo que es perfectamente válido por ejemplo, Aceptar, guarde este element-- lo que sea
elemento de cabeza es-- decrementar su tamaño, mover su cabeza otra vez, y el retorno
cualquiera que sea ese elemento es.
Eso es perfectamente válido.
Okay.
Siento que esto no es como el most-- no estás
va a salir de aquí como, sí, ya sé intentos.
Lo tengo todo.
Eso está bien.
Prometo.
Pero las estructuras de datos son algo que que se necesita una gran cantidad de tiempo para acostumbrarse.
Probablemente uno de los más difíciles las cosas, creo que, en el curso.
>> Así que definitivamente toma repetición y mirando at-- I
No sabía realmente listas enlazadas hasta que me hice demasiado con ellos,
de la misma manera que no lo hice realmente entender punteros
hasta que me he tenido que enseñarla para dos años y hacer mis propios conjuntos de procesadores con él.
Se necesita mucho de la reiteración y el tiempo.
Y, finalmente, será de tipo clic.
>> Pero mientras tanto, si usted tiene tipo de una comprensión de alto nivel de lo que
éstos hacen, sus pros y que es lo que cons--
que realmente tienden a enfatizar, especialmente en el curso de introducción.
Al igual que, ¿por qué habríamos de utilizar una oportunidad más de una matriz?
Al igual que, ¿cuáles son los aspectos positivos y negativos de cada uno de esos?
>> Y la comprensión de las ventajas y desventajas entre cada una de estas estructuras
es lo que es mucho más importante en este momento.
Puede haber un loco o dos preguntas que es
va a pedir que aplicar empuje o implementar pop o de puesta en cola y quitar de la cola.
Pero en su mayor parte, teniendo que mayor comprensión de nivel y más
de una comprensión intuitiva es más importante que en realidad
ser capaz de ponerlo en práctica.
>> Sería realmente impresionante si todos ustedes podría salir e ir implementar un intento,
pero entendemos que no es necesariamente lo más razonable en este momento.
Pero usted puede en su conjunto de procesadores, si quieres para, a continuación, que obtendrá la práctica,
y luego tal vez usted realmente entenderlo.
¿Sí?
>> AUDIENCIA: OK, así que cuáles son nos referimos a utilizar en el conjunto de procesadores?
¿Tengo que usar uno de ellos?
ALTAVOZ 1: Sí.
Así que usted tiene su opción.
Supongo que en este caso, podemos hablar del conjunto de procesadores un poco
porque me encontré a través de estos.
Así que en su conjunto de procesadores, que tenga su elección de intentos o tablas hash.
Algunas personas intentarán y el uso de filtros de floración,
pero los que técnicamente no son correctas.
Debido a su naturaleza probabilística, dan falsos positivos veces.
Son mirada fresca en, sin embargo.
Muy recomendable buscar en ellos al menos.
Pero usted tiene su opción entre una tabla hash y una oportunidad.
Y eso va a ser donde se carga en su diccionario.
>> Y tú tendrás que elegir su función hash,
tendrá que elegir el número de cubos que tiene, y que variará.
Al igual que si usted tiene más cubos, tal vez que va a correr más rápido.
Pero tal vez usted está perdiendo una gran cantidad de espacio de esa manera, sin embargo.
Tienes que entenderlo.
Mmhmm?
>> AUDIENCIA: Usted dijo antes que podemos utilizar otras funciones hash,
que nosotros no tenemos que crear una función hash?
>> ALTAVOZ 1: Sí, correcto.
Así que, literalmente, de su función de control, como google "función hash"
y buscar algunos más fresco.
No se espera construir sus propias funciones hash.
La gente pasa su tesis sobre estas cosas.
>> Así que no te preocupes por la construcción de su propia.
Encontrar una línea para empezar.
Algunos de ellos hay que manipular un poco
para hacer tipos de retorno seguro coinciden y todo eso, así que en principio,
Yo recomiendo usar algo muy fácil que tal vez sólo
hashes en la primera letra.
Y a continuación, una vez que tenga que trabajar, la incorporación de una función hash más fresco.
Mmhmm?
>> AUDIENCIA: ¿Quieres probar un ser o eficiente, pero sólo más difícil, como--
>> ALTAVOZ 1: Así que un intento, creo, es intuitivamente difícil de implementar
pero es muy rápido.
Sin embargo, ocupa más espacio.
Una vez más, puede optimizar tanto de los de diferentes maneras y hay maneras a--
AUDIENCIA: ¿Cómo estamos calificados en esto?
¿Se matter--
>> ALTAVOZ 1: Así que tú eres clasifican de manera normal.
Usted va a ser clasificado en el diseño.
Sea cual sea la forma en que lo hace, usted quiere asegúrese de que es tan elegante como puede ser
y lo más eficiente posible.
Pero si usted elige un try o hachís mesa, mientras funciona,
estamos contentos con eso.
Y si utiliza algo que hashes en la primera letra, eso está bien,
como tal vez como-diseño inteligente.
También estamos llegando a la punto en este semester--
No sé si usted chicos noticed-- si estás
grados PSet declinan un poco debido al diseño y otras cosas,
que está perfectamente bien.
Se está haciendo a un punto en que su los programas son cada vez más complicado.
Hay más lugares se puede mejorar.
>> Así que es perfectamente normal.
No es que usted es haciendo peor en su conjunto de procesadores.
Es sólo que estamos siendo más duro para usted ahora.
Así que todo el mundo está sintiendo.
Acabo califiqué todos sus conjuntos de procesadores.
Sé que todo el mundo está sintiendo.
>> Así que no te preocupes por eso.
Y si usted tiene alguna pregunta sobre conjuntos de procesadores anteriores o maneras en que puede mejorar,
Trato y comento lo específico lugares, pero a veces ya es tarde
y me canso.
¿Hay otras cosas sobre estructuras de datos?
Estoy seguro de que los chicos realmente no quiero hablar de ellos nunca más,
pero si hay, estoy feliz de ir sobre ellos, así como cualquier cosa
de conferencia el pasado semana o la semana pasada.
>> Sé que la semana pasada fue todo examen, por lo que podemos haber saltado alguna opinión
de conferencia.
¿Alguna otra pregunta que puedo responder?
Bien, bien.
Bueno, ustedes salir 15 minutos antes.
>> Espero que esto era semi-útil, al menos, y voy a ver ustedes la próxima semana,
o las horas de oficina Jueves.
¿Hay solicitudes de aperitivos para la semana que viene, que es la cosa?
Porque me olvidé de caramelo hoy.
Y he traído dulces último semana, pero que era el Día de Colón,
por lo que no eran como seis personas que tenía cuatro bolsas de dulces a sí mismos.
Puedo traer Starbursts de nuevo si lo desea.
Starbursts?
Bien, suena bien.
Que tengan un buen día, chicos.