[Powered by Google Translate] [Sección 6: menos cómodo]
[Nate Hardison] [Harvard University]
[Esta es CS50.] [CS50.TV]
Está bien. Bienvenidos a la sección 6.
Esta semana, vamos a estar hablando de estructuras de datos en la sección,
sobre todo porque el problema de esta semana establece en spellr
hace un montón de exploración diferente estructura de datos.
Hay un montón de maneras diferentes que usted puede ir con el conjunto de problemas,
y las estructuras de datos más le conocemos, las cosas más interesantes que puedes hacer.
>> Así que vamos a empezar. En primer lugar vamos a hablar de las pilas,
los datos de la pila y la cola de estructuras que vamos a hablar.
Las pilas y las colas son realmente útiles cuando empezamos a hablar de los gráficos,
que no vamos a hacer mucho de estos momentos.
Pero son muy buenos para entender una de las grandes estructuras de datos fundamentales de la CS.
La descripción de la especificación conjunto de problemas,
si tirar de él hacia arriba, habla de las pilas como afín a
la pila de bandejas de comidas que usted tiene en la cafetería a los comedores
donde cuando el personal del comedor viene y pone las bandejas de salir a cenar después de haberlos limpiado,
que apilarlos uno encima del otro.
Y luego, cuando los niños vienen a buscar comida,
tiran las bandejas de salida, primero el uno y luego la de abajo, y luego la de abajo de eso.
Así que, en efecto, la primera bandeja que el personal del comedor poner es el último que se ha despegado.
El último que el personal del comedor poner es el primero que se lo llevan fuera para la cena.
En el conjunto de especificaciones problema, que se puede descargar si no lo ha hecho,
hablamos de modelado de una pila stucture datos utilizando este tipo de estructura.
>> Así que lo que tenemos aquí, esto es similar a lo que se presentó en la conferencia,
excepto en la conferencia se presentaron con este enteros en lugar de char * s.
Esto va a ser una pila que almacena qué?
Daniel? ¿Qué estamos almacenando en esta pila?
[Daniel] Strings? >> Estamos almacenar las cadenas en esta pila, exactamente.
Todo lo que debe tener para crear una pila es una matriz
de una capacidad particular, que en este caso,
capacidad va a ser todo en mayúsculas porque es una constante.
Y a continuación, además de la matriz, todo lo que necesita para seguir es el tamaño actual de la matriz.
Una cosa para notar aquí que es una especie de fresco
es que estamos creando la estructura de datos apiladas una encima de otra estructura de datos, la matriz.
Hay diferentes maneras de implementar pilas.
No lo vamos a hacer todavía, pero espero que después de hacer los problemas de lista vinculada,
verás lo fácil que es implementar una pila en la parte superior de una lista enlazada también.
Pero por ahora, vamos a atenernos a las matrices.
Así que de nuevo, todo lo que necesitamos es una matriz y sólo tenemos que seguir el tamaño de la matriz.
[Sam] Lo siento, ¿cómo es que usted dijo que la pila está por encima de las cuerdas?
A mí me parece que las cadenas están dentro de la pila.
[Hardison] Yeah. Estamos creando, estamos dando nuestra amplia estructura de datos -
esa es una gran pregunta. Entonces la pregunta es ¿por qué, por las personas que están viendo esta línea,
¿por qué estamos diciendo que la pila está por encima de las cuerdas,
porque aquí parece que las cuerdas están en el interior de la pila?
Lo cual es totalmente el caso.
Lo que me refería es que tenemos una estructura de datos array.
Tenemos una matriz de char * s, esta matriz de cadenas,
y que se va a añadir a la que con el fin de crear la estructura de datos apilados.
>> Así que una pila es un poco más complejo que una matriz.
Podemos utilizar una matriz para construir una pila.
Así que ahí es donde decimos que la pila se construye en la parte superior de una matriz.
Del mismo modo, como he dicho antes, podemos construir una pila en la parte superior de una lista enlazada.
En lugar de utilizar una matriz para mantener nuestros elementos,
podemos utilizar una lista enlazada para mantener nuestros elementos y construir la pila de alrededor de eso.
Vamos a ver un par de ejemplos, mirando algo de código,
para ver lo que realmente está pasando aquí.
A la izquierda, he tirado lo que struct pila se vería en la memoria
si la capacidad se definieron # para ser cuatro.
Tenemos nuestros cuatro elementos de matriz char *.
Tenemos cadenas [0], las cadenas [1], las cadenas [2], cadenas [3],
y luego de que el espacio para nuestro pasado entero tamaño.
¿Tiene esto sentido? Bien.
Esto es lo que pasa si lo que hago en la derecha,
que será mi código, es declarar sólo una estructura, una estructura apilada llamado s.
Esto es lo que tenemos. Establece esta huella en la memoria.
La primera pregunta aquí es ¿cuáles son los contenidos de esta estructura de pila?
Ahora mismo no son nada, pero no son totalmente nada.
Son este tipo de basura. No tenemos idea de lo que hay en ellos.
Cuando declaramos s de pila, sólo estamos tirando abajo que en la parte superior de la memoria.
Es algo así como declarar int i, y no lo inicializa.
Usted no sabe lo que hay allí. Usted puede leer lo que hay allí,
pero tal vez no sea muy servicial.
Una de las cosas que desea recordar siempre que hacer es inicializar lo que necesita ser inicializado.
En este caso, vamos a inicializar el tamaño sea cero,
porque eso va a llegar a ser muy importante para nosotros.
Podríamos seguir adelante e iniciar todos los punteros, todo el s * char,
a ser algún valor comprensible, probablemente nulo.
Pero no es totalmente necesario que hagamos eso.
>> Ahora, las dos operaciones principales sobre las pilas de verdad?
Alguien se acuerda de la conferencia que lo que usted hace con las pilas? ¿Sí?
[Stella] Empujando y haciendo estallar? >> Exactamente.
Empujando y haciendo estallar son las dos operaciones principales de pilas.
¿Y qué empuje hacer? >> Se pone algo en la parte superior
de la pila, y luego saltan lo quita.
[Hardison] Exactamente. Así empujando empuja algo en la parte superior de la pila.
Es como el personal del comedor poniendo una bandeja de comida en el mostrador.
Y hacer estallar está tomando una bandeja de cena de la pila.
Vamos a ver un par de ejemplos de lo que sucede
cuando empujamos las cosas en la pila.
Si fuéramos a empujar la cadena 'hola' a nuestro stack,
esto es lo que nuestro diagrama se vería ahora.
Vea lo que sucede?
Nos introduce en el primer elemento de nuestra amplia cuerdas
y nos subió nuestro conteo tamaño es 1.
Así que si nos fijamos en la diferencia entre las dos correderas, aquí fue de 0, esto es antes de la inserción.
Aquí está después de la inserción.
Antes de la inserción, después de la inserción.
Y ahora tenemos un elemento de nuestra pila.
Es la cadena "hola", y eso es todo.
Todo lo demás en la matriz, en nuestro array de cadenas, sigue siendo basura.
No lo hemos inicializado.
Digamos que empujar otra cadena a nuestro stack.
Vamos a empujar "mundo" en este momento.
Así que usted puede ver "mundo" aquí va encima de "hola",
y el recuento de tamaño sube a 2.
Ahora podemos empujar "CS50", y que va a ir en la parte superior de nuevo.
Si retrocedemos, se puede ver cómo estamos llevando las cosas en la parte superior de la pila.
Y ahora llegamos al pop.
Cuando nos fuimos algo fuera de la pila, ¿qué pasó?
¿Alguien ve la diferencia? Es muy sutil.
[Estudiante] El tamaño. >> Sí, el tamaño cambiado.
>> ¿Qué más se puede esperar para el cambio?
[Estudiantes] Las cuerdas, también. >> Derecho. Las cuerdas también.
Resulta que cuando lo haces de esta manera,
porque no estamos copiando los elementos en nuestro stack,
que en realidad no tiene que hacer nada, sólo podemos utilizar el tamaño
hacer un seguimiento de la cantidad de cosas en nuestra amplia
para que cuando aparezca de nuevo, de nuevo sólo disminuir nuestro tamaño a 1.
No hay necesidad de ir en realidad en y sobreescribir cualquier cosa.
Un poco funky.
Resulta que solemos dejar las cosas solo porque es menos trabajo para nosotros.
Si no tenemos que volver atrás y sobrescribir algo, entonces ¿por qué hacerlo?
Así, cuando aparezca el doble de la pila, lo único que hace es disminuir el tamaño de un par de veces.
Y una vez más, esto es sólo porque no estamos copiando cosas en nuestro stack.
¿Sí? Ir por delante.
[Estudiante, ininteligible] >> Y entonces, ¿qué sucede cuando usted empuja algo nuevo?
Cuando se pulsa algo nuevo, ¿adónde va?
¿A dónde va, Basil? En cadenas >> [1]? >> Derecho.
¿Por qué no ir en cadenas [3]?
[Basil] Debido a que se olvidó de que había algo en las cadenas [1] y [2]?
[Hardison] Exactamente. Nuestra pila, en esencia, "se olvidó" que se aferra a cualquier cosa
en las cadenas [1] o cadenas [2], así que cuando nos empujan "woot"
sólo pone eso en el elemento en cadenas [1].
¿Hay alguna pregunta sobre cómo funciona esto, a un nivel básico?
[Sam] Así que esto no es de ninguna manera dinámica, en términos de cantidad
o en términos del tamaño de la pila?
[Hardison] Exactamente. Esto es - el punto era que no se trataba de una pila dinámica growning.
Esta es una pila que puede contener, como máximo, cuatro char * s, en la mayoría de cuatro cosas.
Si fuéramos a tratar de empujar una quinta cosa, ¿qué cree usted que debería ocurrir?
[Los estudiantes], ininteligibles
[Hardison] Exactamente. Hay una serie de cosas que podrían suceder.
Posiblemente podría seg culpa, dependiendo de lo que eran -
¿cómo es exactamente lo que estaban ejecutando el back-end.
Puede sobrescribir. Podría tener que desbordamiento de búfer que hablamos en clase.
¿Cuál sería la cosa más obvia que puede ser sobreescrita
si tratamos de empujar algo extra en nuestra pila?
Así que usted ha mencionado un desbordamiento de búfer.
¿Cuál podría ser la cosa que se escriben sobre o pisoteó
si nos desbordó accidentalmente al tratar de empujar una cosa extra?
[Daniel, ininteligible] >> Posible.
Pero inicialmente, lo que podría ocurrir? ¿Qué pasa si tratamos de empujar una cuarta cosa?
Puede sobrescribir el tamaño, al menos con este esquema de memoria que tenemos.
>> En la especificación conjunto de problemas, que es lo que vamos a estar implementando hoy en día,
lo que quiero hacer es devolver false.
Nuestro método de empuje se va a devolver un valor booleano,
y que el valor booleano será verdadera si el empuje éxito
y falso si no podemos empujar más nada porque la pila está llena.
Vamos a ver un poco de ese código en estos momentos.
Esta es nuestra función push.
Nuestra función push para una pila se va a tomar en la cadena para poner en la pila.
Se va a devolver true si la cadena fue empujado con éxito
de otra manera en la pila y lo falso.
¿Alguna sugerencia sobre lo que podría ser una buena cosa primero que debemos hacer aquí?
[Sam] Si el tamaño es igual a la capacidad de devolver false entonces?
[Hardison] Bingo. Buen trabajo.
Si el tamaño es la capacidad, vamos a devolver false.
No podemos poner nada más en nuestra pila.
De lo contrario, queremos poner algo en la parte superior de la pila.
¿Qué es "la parte superior de la pila," inicialmente?
[Daniel] Tamaño 0? Tamaño >> 0.
¿Cuál es la parte superior de la pila después hay una cosa en la pila? Missy, ¿sabes?
[Missy] Una. Tamaño >> es uno, exactamente. Usted mantener la adición al tamaño,
y cada vez que se está poniendo en el nuevo elemento en el tamaño del índice en la matriz.
Lo podemos hacer con ese tipo de una sola línea, si eso tiene sentido.
Así que tenemos nuestra matriz de cadenas, vamos a acceder a él en el índice de tamaño,
y sólo vamos a guardar nuestro char * en ese país.
Nótese cómo hay ninguna copia cuerda pasando aquí,
no asignación dinámica de la memoria?
Y luego Missy criado lo que ahora tenemos que hacer,
porque hemos guardado la cadena en el lugar apropiado en la matriz,
y ella me dijo que había que aumentar el tamaño de una forma que estamos listos para la siguiente pulsación.
Así que podemos hacer eso con s.size + +.
En este punto, hemos empujado a nuestra matriz. ¿Qué es lo último que tenemos que hacer?
[Estudiante] Devuelve true. >> Volver verdad.
Así que es bastante simple, un código bastante simple. No demasiado.
Una vez que ha envuelto la cabeza en torno a cómo funciona la pila,
esto es bastante sencillo de implementar.
>> Ahora, la siguiente parte de esta está apareciendo una cadena de la pila.
Voy a dar ustedes algo de tiempo para trabajar en esto un poco.
Es casi esencialmente lo contrario de lo que hemos hecho aquí en empuje.
Lo que he hecho es en realidad - oops.
He arrancado un aparato por aquí, y en el aparato,
He tirado el problema conjunto 5 especificación.
Si el zoom aquí, podemos ver que estoy en cdn.cs50.net/2012/fall/psets/pset5.pdf.
¿Han descargado el código que se encuentra aquí, section6.zip?
Está bien. Si usted no ha hecho esto, haz lo otro en este momento, muy rápido.
Lo haré en mi ventana de terminal.
De hecho, me lo hizo aquí. Si.
Sí, Sam? >> Tengo una pregunta acerca de por qué le dijiste s.string 's soportes de tamaño = str?
¿Cuál es str? Es el definido antes en alguna parte, o - oh, en la char * str?
[Hardison] Sí, exactamente. Ese fue el argumento. >> Oh, está bien. Lo siento.
[Hardison] Estamos especificar la cadena de empujar pulg
La otra cuestión que pueda surgir que realmente no hablar de aquí fue
se daba por sentado que tuvimos esta variable llamada s
que era en su alcance y accesible para nosotros.
Nos dieron por sentado que era este s struct pila.
Así que mirando hacia atrás en el código de inserción,
se puede ver que estamos haciendo cosas con esta cadena que quedó aprobada en
pero luego, de repente, estamos accediendo s.size, al igual que, ¿de dónde provienen de s?
En el código que vamos a ver en el archivo de la sección
y entonces las cosas que usted hará en su problema se pone,
hemos hecho nuestra pila struct una variable global
para que podamos tener acceso a ella en todas nuestras funciones diferentes
sin tener que pasar manualmente alrededor y pasarlo por referencia,
hacer todo ese tipo de cosas a ella.
Sólo estamos engañando un poco, si se quiere, para hacer las cosas mejor.
Y eso es algo que estamos haciendo aquí porque es por diversión, es más fácil.
A menudo, usted verá la gente hace esto si tienen una estructura de datos grande
que está siendo operado dentro de su programa.
>> Vamos a ir de nuevo hacia el aparato.
¿Todos con éxito obtener el section6.zip?
Todo el mundo lo descomprima usando section6.zip descomprimir?
Si usted entra en la sección 6 del directorio -
aah, por todo el lugar -
y una lista de lo que hay aquí, se ve que tienes tres archivos diferentes. c.
Usted tiene una cola, una sll, que es la lista simplemente enlazada, y una pila.
Si usted abre stack.c,
se puede ver que tenemos esta estructura definida por nosotros,
la estructura exacta que acabamos de hablar en las diapositivas.
Tenemos nuestra variable global de la pila,
tenemos nuestra función push,
y luego tenemos nuestra función pop.
Voy a poner el código para hacer retroceder a la diapositiva aquí,
pero lo que me gustaría que ustedes hacen es, a lo mejor de su capacidad,
ir y poner en práctica la función pop.
Una vez que haya puesto en práctica, puede compilar con make esta pila,
a continuación, ejecute el archivo ejecutable pila resultante,
y que se extenderá todo este código de prueba aquí que está en principal.
Y principal se encarga realmente de hacer el push y pop llamadas
y asegurarse de que todo va a través de todo derecho.
También se inicializa el tamaño de la pila aquí
por lo que no tiene que preocuparse de que la inicialización.
Se puede suponer que ha sido correctamente inicializado
en el momento en que acceda a ella en la función pop.
¿Eso tiene sentido?
Así que aquí vamos. Ahí está el código de inserción.
Voy a daros 5 o 10 minutos.
Y si usted tiene alguna pregunta en el ínterin mientras estás codificación,
por favor pregunte en voz alta.
Así que si se llega a un punto de estancamiento, solo pregunte.
Déjame saber, que todo el mundo sabe.
Trabaje con su vecino también.
[Daniel] Estamos implementación pop en este momento? >> Just pop.
Aunque usted puede copiar la aplicación de empuje si desea
de modo que la prueba funcionará.
Debido a que es difícil probar que las cosas se en -
o, es difícil de probar cosas que hacen estallar fuera de una pila si no hay nada en la pila, para empezar.
>> ¿Qué es el pop supone que se repitan? El elemento de la parte superior de la pila.
Se supone que para obtener el elemento fuera de la parte superior de la pila
y luego disminuir el tamaño de la pila,
y ahora que ha perdido el elemento en la parte superior.
Y luego que devuelva el elemento en la parte superior.
[Estudiante, ininteligible]
[Hardison] Entonces, ¿qué pasa si se hace eso? [Estudiante, ininteligible]
Lo que termina pasando es que estás probablemente para acceder a cualquiera de los dos
un elemento que no se ha inicializado todavía, por lo que su cálculo
de donde el último elemento es está apagado.
Así que aquí, si te fijas, en el impulso, estamos accediendo cadenas en el elemento s.size
porque se trata de un nuevo índice.
Es el nuevo tope de la pila.
Mientras que en el pop, s.size va a ser el siguiente espacio,
El espacio que hay en la parte superior de todos los elementos de la pila.
De modo que el elemento de más arriba no es s.size,
sino más bien, es por debajo de él.
>> La otra cosa que hacer cuando - en el pop,
se le tiene que disminuir el tamaño.
Si usted recuerda de nuevo a nuestro pequeño diagrama aquí,
en realidad, lo único que vimos sucediendo cuando llamamos pop
era que este tamaño disminuido, primero a 2, y luego a 1.
Luego, cuando empujó un nuevo elemento en adelante, seguiría en el lugar adecuado.
[Basil] Si el s.size es 2, entonces ¿no sería ir al elemento 2,
y luego que te gustaría hacer estallar ese elemento fuera?
Así que si nos fuimos a - >> Así que echemos un vistazo a esto de nuevo.
Si esta es nuestra pila en este momento
y llamamos pop,
en qué índice es el elemento de más arriba?
[Basil] A los 2, pero va a aparecer 3. >> Derecho.
Así que ahí es donde nuestro tamaño es 3, pero queremos que aparezca el elemento en el índice 2.
Es ese tipo típico de apagado por una que usted tiene con el cero de la indexación de arrays.
Así que usted quiere meter el tercer elemento, pero el tercer elemento no está en el índice 3.
Y la razón por la que no tienes que hacer eso menos 1 cuando estamos empujando
se debe a que en estos momentos, te das cuenta de que el elemento de más arriba,
si eran para empujar algo más en la pila en este punto,
nos gustaría que empujarla en el índice 3.
Y da la casualidad de que el tamaño y los índices alineados cuando usted está empujando.
>> ¿Quién tiene una implementación de la pila de trabajo?
Tienes un montón de trabajo uno. ¿Tiene pop trabajando todavía?
[Daniel] Sí. Creo que sí.
Programa >> está corriendo y no seg fallamiento, se está imprimiendo?
¿Se imprimirá el "éxito" cuando se ejecuta?
Si. Hacer apilar, ejecutarlo, si imprime el "éxito" y no va boom,
entonces todo está bien.
Está bien. Vamos a repasar el aparato muy rápido,
y vamos a caminar a través de este.
Si nos fijamos en lo que está pasando aquí con el pop,
Daniel, ¿qué fue lo primero que hiciste?
[Daniel] Si s.size es mayor que 0.
[Hardison] Bueno. ¿Y por qué has hecho eso?
[Daniel] Para asegurarse de que había algo dentro de la pila.
[Hardison] Derecho. ¿Quieres poner a prueba para asegurarse de que s.size es mayor que 0;
de lo contrario, ¿qué quieres que pase?
[Daniel] null retorno? Nulo >> Retorno, exactamente.
Así que si s.size es mayor que 0. Entonces, ¿qué vamos a hacer?
¿Qué hacemos si la pila no está vacía?
[Stella] Usted disminuir el tamaño? >> Usted disminuir el tamaño, está bien.
Entonces, ¿cómo hiciste eso? >> S.size--.
[Hardison] Great. Y entonces, ¿qué hiciste?
[Stella] Y entonces me dijo que el regreso s.string [s.size].
[Hardison] Great.
De lo contrario, devuelve null. Sí, Sam?
[Sam] ¿Por qué no lo necesita para ser s.size + 1?
[Hardison] Plus 1? Sí >>. >> Lo tengo.
[Sam] pensé porque usted toma con 1,
entonces usted va a regresar no es el que ellos pidieron.
[Hardison] Y esto era justo lo que estábamos hablando con todo este tema de 0 índices.
Así que si amplía aquí.
Si nos fijamos en este tipo aquí, se puede ver que cuando el pop,
estamos haciendo estallar el elemento de índice 2.
>> Por lo tanto, disminuir el tamaño de nuestra primera, entonces nuestro tamaño coincide con nuestro índice.
Si no disminuir el tamaño de la primera, entonces tenemos que ver tamaño -1 y decremento.
Grande. ¿Todo bien?
¿Tiene preguntas sobre esto?
Hay un número de formas diferentes de escribir esto.
De hecho, podemos hacer algo todavía - podemos hacer una sola línea.
Podemos hacer una declaración de una línea.
Así que en realidad puede disminuir antes de que volvamos a hacerlo.
Así que poner el - antes de la s.size.
Eso hace que la línea realmente denso.
Cuando la diferencia entre el -. S tamaño y s.size--
es que este sufijo - lo llaman porque el sufijo - viene después de la s.size--
significa que s.size se evalúa a los efectos de encontrar el índice
como lo es en la actualidad cuando se ejecuta esta línea,
y luego esto - que sucede después de la línea se ejecuta.
Después de que el elemento en s.size índice se accede.
Y eso no es lo que queremos, porque queremos que el decremento que suceda primero.
Othewise, vamos a estar accediendo a la matriz, efectivamente, fuera del campo.
Vamos a estar accediendo al elemento superior a la que realmente desea acceder.
Sí, Sam? >> ¿Es más rápido y usa menos memoria RAM para hacer en una sola línea o no?
[Hardison] Honestamente, realmente depende.
[Sam, ininteligible] >> Sí, depende. Usted puede hacer trucos de compilación
para obtener el compilador de reconocer que, por lo general, me imagino.
>> Para ello hemos mencionado un poco sobre estas cosas optimización del compilador
que se puede hacer en la recopilación,
y ese es el tipo de cosa que un compilador puede ser capaz de entender,
como oh, hey, tal vez pueda hacer todo esto en una sola operación,
en oposición a la carga de la variable en tamaño de RAM,
decreciendo, almacenándolo a salir, y luego vuelva a cargar
para procesar el resto de esta operación.
Pero por lo general, no, este no es el tipo de cosas
que va a hacer su programa mucho más rápido.
¿Alguna pregunta más sobre las pilas?
>> Así que empujar y hacer estallar. Si ustedes quieren probar la edición pirata informático,
lo que hemos hecho en la edición pirata es en realidad ido
e hicieron de esta pila de crecer de forma dinámica.
El reto no es principalmente aquí en la función push,
para encontrar la manera de hacer crecer esa matriz
a medida que seguir empujando más y más elementos en la pila.
En realidad no es un código adicional en exceso.
Sólo una llamada a - usted tiene que recordar para conseguir las llamadas a malloc ahí correctamente,
y luego averiguar cuándo va a llamar realloc.
Eso es un reto divertido si te interesa.
>> Pero por el momento, vamos a seguir adelante, y vamos a hablar de las colas.
Desplácese por aquí.
La cola es un hermano cerca de la pila.
Así que en la pila, las cosas que se pusieron en última
fueron las primeras cosas para luego ser recuperados.
Tenemos este último en entrar, primero en salir, o UEPS, hacer el pedido.
Mientras que en la cola, como era de esperar a partir de cuando se está de pie en la fila,
la primera persona que entra en la línea, lo primero que debe entrar en la cola,
es lo primero que se recupera de la cola.
Las colas también se utiliza a menudo cuando estamos tratando con gráficos,
como hemos hablado brevemente con pilas,
y las colas también son útiles para un montón de otras cosas.
Una cosa que surge a menudo está tratando de mantener, por ejemplo,
una lista ordenada de elementos.
Y usted puede hacer esto con una matriz. Puede mantener una lista ordenada de las cosas en una matriz,
pero en los que se complica es entonces siempre hay que encontrar
el lugar adecuado para insertar la siguiente cosa.
Así que si usted tiene una matriz de números, del 1 al 10,
y luego desea ampliar eso a todos los números de 1 a 100,
y que está recibiendo estos números en orden aleatorio y tratando de mantener todo
ordenados a medida que avanza, usted termina encima de tener que hacer un montón de cambio.
Con ciertos tipos de colas y ciertos tipos de estructuras de datos subyacentes,
en realidad se puede mantener bastante simple.
Usted no tiene que añadir algo y luego barajar la cosa entera cada vez.
Tampoco hay que hacer un montón de desplazamiento de los elementos internos a la redonda.
Cuando nos fijamos en una cola, se ve que - también en queue.c en el código de sección -
la estructura que le hemos dado es muy similar a la estructura que le dio para una pila.
>> Hay una excepción a esto, y que una excepción
es que tenemos este entero adicional llama la cabeza,
y la cabeza aquí es para hacer el seguimiento de la cabeza de la cola,
o el primer elemento en la cola.
Con una pila, hemos sido capaces de hacer un seguimiento de los elementos que estábamos a punto de recuperar,
o la parte superior de la pila, utilizando sólo el tamaño,
mientras que con una cola, vamos a tener que lidiar con los extremos opuestos.
Estamos tratando de virar las cosas en al final, pero luego regresan las cosas de frente.
Así que efectivamente, con la cabeza, que tiene el índice del principio de la cola,
y el tamaño nos da el índice del final de la cola
para que podamos recuperar las cosas de la cabeza y añadir cosas a la cola.
Mientras que con la pila, sólo estábamos nunca tratar con la parte superior de la pila.
Nunca tuvimos que acceder a la parte inferior de la pila.
Sólo añade cosas a la cima y tomó las cosas fuera de la parte superior
así que no necesito ese campo adicional en el interior de nuestro struct.
¿Eso generalmente tiene sentido?
Está bien. Sí, Charlotte? [Charlotte, ininteligible]
[Hardison] Eso es una gran pregunta, y que fue el que ocurrió en la conferencia.
Tal vez caminando a través de algunos ejemplos que ilustran por qué
no queremos usar cadenas [0] como la cabeza de la cola.
>> Así que imaginen que tenemos nuestra cola, vamos a llamarlo cola.
Al principio, cuando acabo de instancia,
cuando acabamos de lo declarado, no hemos inicializado nada.
Es todo basura. Así que, por supuesto, queremos asegurarnos de que inicializar
tanto el tamaño y los campos de cabeza a ser 0, algo razonable.
También podríamos seguir adelante y nulos los elementos en nuestra cola.
Y para hacer este ajuste diagrama, note que ahora nuestra cola sólo puede contener tres elementos;
mientras que nuestra pila podría tener cuatro, nuestra cola sólo puede tener tres.
Y eso es sólo para hacer el ajuste diagrama.
Lo primero que sucede aquí es que encolar la cadena "hola".
Y al igual que hicimos con la pila, nada terriblemente diferente aquí,
tiramos la cuerda de las cuerdas [0] y aumentar nuestro tamaño en 1.
Nos encolar "bye", consigue poner.
Por lo tanto esto se parece a una pila en su mayor parte.
Empezamos aquí, nuevo elemento, el elemento nuevo, el tamaño sigue subiendo.
¿Qué sucede en este momento en el que queremos quitar de la cola algo?
Cuando queremos quitar de la cola, que es el elemento que queremos quitar de la cola?
[Basil] Strings [0]. >> Cero. Exactamente, Basil.
Queremos deshacernos de la primera cadena, este "hola".
Entonces, ¿cuál era la otra cosa que ha cambiado?
Aviso cuando nos fuimos algo fuera de la pila, que acaba de cambiar el tamaño,
pero en este caso, tenemos un par de cosas que cambian.
No sólo el cambio de tamaño, pero los cambios de cabeza.
Esto va de nuevo a punto de Charlotte antes:
¿por qué tenemos esta cabeza también?
¿Tiene sentido ahora, Charlotte? Tipo de >>.
[Hardison] Algo así? ¿Y qué pasó cuando nos quita de la cola?
¿Qué hizo la cabeza hacer eso ahora es interesante?
[Charlotte] Oh, porque cambió - está bien. Ya veo.
Debido a que la cabeza - donde la cabeza apunta a los cambios en términos de la ubicación.
Ya no es siempre el índice cero. >> Sí, exactamente.
Lo que sucedió fue desencolado si el elemento de alta
se hizo y no teníamos este campo de la cabeza
porque siempre estábamos llamando a esta cadena a 0 Índice de la cabeza de nuestra cola,
entonces tendríamos que pasar el resto de la cola hacia abajo.
Tendríamos que cambiar "bye" de en cadenas [1] para las cadenas [0].
Y las cadenas [2] hasta llegar a las cadenas [1].
Y tendríamos que hacer esto por toda la lista de elementos,
todo el conjunto de elementos.
Y cuando hacemos esto con una matriz, que se pone muy costoso.
Así que aquí, no es una gran cosa. Sólo tenemos tres elementos de nuestra matriz.
Pero si tuviéramos una cola de un millar de elementos o un millón de elementos,
y luego, de repente, empezamos a hacer un montón de quitar de la cola llama a todos en un bucle,
las cosas realmente van a disminuir a medida que se desplaza por todo constantemente.
Ya sabes, cambiar por 1, por un cambio, cambio por 1, cambio en 1.
En su lugar, se utiliza esta cabeza, lo llamamos un "puntero", aunque en realidad no es un puntero
en sentido estricto, no es un tipo de puntero.
No es un * int o char * ni nada de eso.
Pero se señala o indica el jefe de nuestra cola. ¿Sí?
>> [Estudiante] ¿Cómo quitar de la cola saber hacer estallar justo al lado de lo que está a la cabeza?
[Hardison] ¿Cómo quitar de la cola saber cómo hacer estallar todo lo que está en la cabeza? Derecho >>, sí.
>> Lo que está viendo es simplemente cualquiera que sea el campo de cabecera se establece en.
Así que en este primer caso, si miramos aquí mismo,
nuestra cabeza es 0, 0 índice. >> Derecho.
[Hardison] Tan sólo dice bien, bien, el elemento en el índice 0, la cadena "hola",
Es el elemento a la cabeza de nuestra cola.
Así que vamos a quitar de la cola de ese tipo.
Y eso va a ser el elemento que se devuelve al llamador.
Sí, Saad? >> Así que la cabeza, básicamente, establece la - a donde vas a índice?
Ese es el comienzo de la misma? Sí >>. >> Okay.
[Hardison] Eso es convertirse en el nuevo comienzo de nuestra matriz.
Así que cuando usted quitar de la cola algo, todo lo que tienes que hacer es acceder al elemento en el índice q.head,
y que será el elemento que desea quitar de la cola.
Usted también tiene que disminuir el tamaño.
Vamos a ver un poco en donde las cosas se ponen un poco difícil con esto.
Nos quitar de la cola, y ahora, si nos encolar nuevamente,
¿dónde encolar?
¿De dónde viene el elemento siguiente ir en nuestra cola?
Digamos que queremos poner en cola la cadena "CS".
En qué índice se ha ido? [Los estudiantes] Strings [2]. >> Dos.
¿Por qué no 2 y 0?
[Basil] Porque ahora la cabeza es 1, por lo que es como el inicio de la lista?
[Hardison] Derecho. Y lo que indica el final de la lista?
¿De qué estábamos usando para indicar el final de nuestra cola?
La cabeza es la cabeza de nuestra cola, el principio de nuestra cola.
¿Cuál es el fin de nuestra cola? [Los estudiantes] tamaño. >> Tamaño, exactamente.
Así que nuestros nuevos elementos a ir en tamaño, y los elementos que tomamos de salir en cabeza.
Al poner en cola el siguiente elemento, lo estamos poniendo a tamaño.
[Estudiante] Antes de poner eso en si, el tamaño era de 1, ¿no?
[Hardison] Derecho. Así que no bastante en tamaño. Tamaño + no, +1, pero la cabeza +.
Debido a que cambió todo por la cantidad cabeza.
Así que aquí, ahora tenemos una cola de tamaño 1 que comienza en el índice 1.
La cola es de índice 2. ¿Sí?
>> [Estudiante] ¿Qué sucede cuando usted dequeue cadenas [0], y las ranuras de las cuerdas en la memoria
sólo se vacían, en el fondo, o simplemente olvidado?
[Hardison] Yeah. En este sentido, nos estamos olvidando.
Si estuviéramos almacenar copias de ellos -
muchas estructuras de datos a menudo se almacenan sus propias copias de los elementos
de modo que la persona que gestiona la estructura de datos no tiene que preocuparse
sobre el que todos los punteros se dirige.
La estructura de datos se aferra a todo, se aferra a todas las copias,
para asegurarse de que todo lo que persiste adecuadamente.
Sin embargo, en este caso, estas estructuras de datos sólo, por simplicidad,
no están haciendo copias de todo lo que estamos almacenando en ellos.
[Estudiante] Por lo tanto se trata de una serie continua de -? Sí >>.
Si miramos hacia atrás en lo que fue la definición de esta estructura, lo es.
Es sólo un conjunto estándar como se ha visto,
una matriz de char * s.
¿Eso - >> Sí, me estaba preguntando
si finalmente se quedará sin memoria, hasta cierto punto,
si usted tiene todos estos lugares vacíos en la matriz?
[Hardison] Sí, eso es un buen punto.
>> Si nos fijamos en lo que ha ocurrido ahora en este momento,
hemos llenado nuestra cola, como se ve.
Pero en realidad no hemos llenado nuestra cola
porque tenemos una cola que es talla 2, pero comienza en el índice 1,
porque ahí es donde nuestro puntero cabeza.
Como usted decía, ese elemento en cadenas [0], en el índice 0, no está realmente allí.
No está en nuestra cola más.
Simplemente no se molestó en entrar y escribir sobre ella cuando lo quite de la cola.
Así que, aunque parece que nos hemos quedado sin memoria, que realmente no tienen.
Ese lugar está disponible para nuestro uso.
El comportamiento apropiado, si fuéramos a tratar de quitar de la cola y la primera cosa
como "adiós", que debería salir despedida fuera.
Ahora nuestro cola empieza en el índice 2 y es de tamaño 1.
Y ahora, si tratamos de poner en cola algo más, digamos 50,
50 años deben ir en este punto en el índice 0
porque todavía disponible para nosotros. Sí, Saad?
[Saad] ¿Esto sucederá de forma automática?
[Hardison] No pasa absolutamente automáticamente. Hay que hacer las cuentas
para hacer que funcione, pero en esencia lo que hemos hecho es que hemos acaba de terminar su alrededor.
[Saad] Y está bien si este tiene un agujero en el medio de ella?
[Hardison] Lo es si podemos hacer que las matemáticas funcionan de manera adecuada.
>> Y resulta que eso no es realmente tan difícil de hacer con el operador mod.
Así que al igual que hicimos con César y el material criptográfico,
utilizando mod, podemos hacer las cosas para envolver y seguir adelante
alrededor y alrededor y alrededor con nuestra cola,
mantener ese puntero cabeza se mueve alrededor.
Observe que el tamaño está respetando siempre el número de elementos en realidad dentro de la cola.
Y es sólo el puntero de cabeza que se mantiene en bicicleta a través.
Si nos fijamos en lo que sucedió aquí, si nos remontamos al principio,
y que acaba de ver lo que sucede en la cabeza
cuando encolar algo, no pasó nada en la cabeza.
Cuando en cola otra cosa, no pasó nada en la cabeza.
Tan pronto como se quita de la cola algo, la cabeza se incrementa en uno.
Tenemos algo en cola, no pasa nada en la cabeza.
Al quitar de la cola algo, de repente la cabeza se incrementa.
Cuando encolar algo, no pasa nada a la cabeza.
>> ¿Qué pasaría en este momento si tuviéramos que quitar de la cola algo nuevo?
¿Alguna idea? ¿Qué le pasaría a la cabeza?
¿Qué debe pasar con la cabeza
si tuviéramos que quitar de la cola algo más?
La cabeza ahora mismo está en el índice 2,
lo que significa que la cabeza de la cola es strings [2].
[Estudiante] Lo cual devuelve 0? >> Se debe volver a 0. Se debe envolver la vuelta, exactamente.
Hasta ahora, cada vez que se llama quitar de la cola, hemos estado agregando uno a la cabeza,
añadir uno a la cabeza, agregar uno a la cabeza, agregar uno a la cabeza.
Tan pronto como el puntero de cabeza llega al último índice en nuestra matriz,
entonces tenemos que concluir la vuelta al principio, vuelve a 0.
[Charlotte] ¿Qué determina la capacidad de la cola en una pila?
[Hardison] En este caso, sólo hemos estado utilizando una constante # define. >> Okay.
[Hardison] en el archivo actual. C, se puede ir en barro y con él un poco
y hacerlo tan grande o tan pequeño como usted quiera.
[Charlotte] Así que cuando usted está haciendo una cola, ¿cómo hacer que el equipo sabe
el tamaño que desea que la pila sea?
[Hardison] Eso es una gran pregunta.
Hay un par de maneras. Una de ellas es simplemente definir por adelantado
y decir que esto va a ser una cola que tiene 4 elementos o elementos 50 o 10.000.
La otra forma es hacer lo que la gente de edición de hackers están haciendo
y crear funciones para que su cola crece dinámicamente a medida que se añaden más cosas pulg
>> [Charlotte] Así que para ir con la primera opción, lo que la sintaxis se utiliza
para decirle al programa cuál es el tamaño de la cola?
[Hardison] Ah. Así que vamos a salir de esto.
Todavía estoy en stack.c aquí, así que sólo voy a desplazarse hasta la parte superior aquí.
¿Puedes ver esto aquí? Este es el # define capacidad 10.
Y esto es casi exactamente la misma sintaxis que tenemos para la cola.
Excepto en la cola, tenemos que struct campo adicional aquí.
[Charlotte] Oh, pensé que la capacidad de decir la capacidad de la cadena.
[Hardison] Ah. >> Esta es la longitud máxima de la palabra. >> Lo tengo.
Si. La capacidad aquí - que es un gran punto.
Y esto es algo que es difícil
porque lo que hemos declarado aquí es una matriz de char * s.
Una matriz de punteros.
Este es un arreglo de caracteres.
Esto es probablemente lo que he visto cuando he estado declarando sus buffers para el archivo de E / S,
cuando usted ha sido la creación de cadenas de forma manual en la pila.
Sin embargo, lo que tenemos aquí es una matriz de char * s.
Así que es una matriz de punteros.
En realidad, si se amplía hacia fuera y vemos lo que está pasando aquí
en la presentación, se ve que los elementos reales, los datos de carácter
no se almacena dentro de la propia matriz.
¿Qué está almacenada dentro de nuestra amplia aquí son punteros a los datos de caracteres.
Bien. Así hemos visto cómo el tamaño de la cola es igual que con la pila,
el tamaño respeta siempre el número de elementos actualmente en la cola.
Después de hacer 2 pone en cola, el tamaño es 2.
Después de hacer una dequeue el tamaño es ahora 1.
Después de hacer otro en cola el tamaño es una copia de seguridad a 2.
Así, el tamaño definitivamente respete el número de elementos en la cola,
y luego la cabeza sólo sigue el ciclismo.
Va de 0-1-2, 0-1-2, 0-1-2.
Y cada vez que llamamos a quitar de la cola, el puntero de cabeza se incrementa al índice siguiente.
Y si la cabeza está a punto de pasar, se vuelve de nuevo a 0.
Así que con eso, podemos escribir la función de quitar de la cola.
Y vamos a salir de la función de puesta en cola para ustedes para poner en práctica en su lugar.
>> Al quitar de la cola un elemento de nuestra cola,
¿qué fue lo primero que hizo Daniel cuando comenzamos a escribir la función pop para pilas?
Quiero oír de alguien que no ha hablado todavía.
Vamos a ver, Saad, ¿te acuerdas de lo que Daniel hizo lo que la primera cosa cuando escribió pop?
[Saad] No se, fue - >> Probó por algo.
[Saad] Si el tamaño es mayor que 0. >> Exactamente.
¿Y qué era que las pruebas de?
[Saad] Eso estaba probando para ver si hay algo en el interior de la matriz.
[Hardison] Yeah. Exactamente. Por lo que no puede hacer estallar cualquier cosa fuera de la pila si está vacío.
Del mismo modo, no se puede quitar de la cola desde una cola si está vacío.
¿Qué es lo primero que debemos hacer en nuestra función de quitar de la cola aquí, ¿te parece?
[Saad] Si el tamaño es mayor que 0? Sí >>.
En este caso, he hecho sólo una prueba para ver si es 0.
Si es 0, se puede devolver null.
Pero la lógica misma.
Y vamos a seguir con esto.
Si el tamaño no es 0, ¿dónde está el elemento que desea quitar de la cola?
[Saad] A la cabeza? >> Exactamente.
Sólo podemos sacar el primer elemento de nuestra cola
mediante el acceso al elemento en la cabeza.
Nada loco.
Después de eso, ¿qué debemos hacer? ¿Qué tiene que pasar?
¿Cuál era la otra cosa que hemos hablado en quitar de la cola?
Dos cosas tienen que ocurrir, porque nuestra cola ha cambiado.
[Daniel] Reducir el tamaño. >> Tenemos que reducir el tamaño y aumentar la cabeza? Exactamente.
Para aumentar la cabeza, no podemos simplemente a ciegas aumentan la cabeza, recuerda.
No podemos hacer queue.head + +.
Tenemos que incluir también este mod por la capacidad.
¿Y por qué mod por la capacidad, Stella?
[Stella] Porque tiene que envolver. >> Exactamente.
Nos mod por la capacidad, ya que tiene que envolver alrededor de nuevo a 0.
Así que ahora, en este punto, podemos hacer lo que dijo Daniel.
Podemos disminuir el tamaño.
Y entonces sólo puede devolver el elemento que estaba en la parte superior de la cola.
Se parece un poco al principio gnarly. Es posible que tenga una pregunta. ¿Cómo dice?
>> [Sam] ¿Por qué es primero en la parte superior de la cola? ¿De dónde viene eso?
[Hardison] Viene de la cuarta línea de la parte inferior.
Después de realizar pruebas para asegurarse de que nuestra cola no está vacía,
nos retiramos char * primero, sacar el elemento que está sentado en el índice cabeza
de nuestra matriz, de nuestra amplia cuerdas, llamada >> y que por primera vez?
[Hardison] Y lo llamamos primero. Si.
Sólo para dar seguimiento a eso, ¿por qué crees que teníamos que hacer eso?
[Sam] Cada primero se acaban de volver q.strings [q.head]? Sí >>.
>> Porque estamos haciendo este cambio de la q.head con la función mod,
y no hay manera de hacerlo dentro de la línea de retorno también.
[Hardison] Exactamente. Usted es el clavo. Sam está totalmente en el clavo.
La razón por la que tuvo que retirarse el primer elemento de nuestra cola y almacenarlo en una variable
se debe a que esta línea donde habíamos q.head justo,
ahí está el operador mod en que no es algo que podamos hacer
y que tenga efecto en la cabeza sin - en una sola línea.
Así que en realidad tenemos que sacar al primer elemento, a continuación, ajuste la cabeza,
ajustar el tamaño, y luego devolver el elemento que nos retiramos.
Y esto es algo que veremos surgir más tarde con
listas enlazadas, como jugar con ellos.
A menudo, cuando usted está liberando o la eliminación de las listas enlazadas
es necesario recordar el siguiente elemento, el puntero siguiente de una lista enlazada
antes de disponer de la actual.
Porque de otra manera de deshacerse de la información de lo que queda en la lista.
Ahora, si usted va a su dispositivo, se abre queue.c--x de esto.
Así que si abro queue.c, déjame zoom aquí,
verás que tiene un archivo de aspecto similar.
De aspecto similar al archivo de lo que teníamos antes con stack.c.
Tenemos nuestra estructura de cola definida tal y como vimos en las diapositivas.
>> Tenemos nuestra función en cola que es para que usted pueda hacer.
Y tenemos la función de quitar de la cola aquí.
La función de quitar de la cola en el archivo no se ha implementado,
pero lo voy a poner de nuevo en el PowerPoint para que pueda escribirlo, si lo desea.
Así que para los próximos 5 minutos más o menos, ustedes trabajan en enqueue
que es casi lo contrario de quitar de la cola.
Usted no tiene que ajustar la cabeza cuando estás encolamos, pero ¿qué tiene que ajustar?
Tamaño. Así que cuando en cola, la cabeza se mantiene intacto, el tamaño se cambia.
Pero se necesita un poco de - usted tendrá que jugar con ese mod
de averiguar exactamente lo que el índice del elemento nuevo debe insertarse al.
Así que voy a dar a ustedes un poco, poner quitar de la cola de nuevo en la diapositiva,
y como ustedes tienen preguntas, les gritan para que podamos
todos hablan de ellos como grupo.
Además, con el tamaño que no - al ajustar el tamaño, siempre puedes hacer solo -
Qué tiene que mod el tamaño cada vez? [Daniel] >> No. Usted no tiene que mod del tamaño, claro.
Debido a que el tamaño siempre, si TU ESTAS - asumiendo que usted está manejando las cosas adecuadamente,
el tamaño siempre será de entre 0 y 3.
¿Dónde hay que mod cuando estás haciendo en cola?
[Estudiante] Sólo para la cabeza. >> Solo para la cabeza, exactamente.
¿Y por qué tienes que mod en absoluto en enqueue?
Cuando se trata de una situación en la que tendría que mod?
[Estudiante] Si tienes cosas en espacios, como en los espacios 1 y 2,
y entonces tenía que añadir algo a 0.
[Hardison] Sí, exactamente. Así que si su cabeza es puntero en el final,
o si el tamaño de su cabeza es más grande, o más bien, se va a envolver alrededor de la cola.
>> Así que en esta situación que tenemos aquí en la diapositiva en este momento,
si quiero poner en cola algo en este momento,
queremos poner en cola algo en el índice 0.
Así que si nos fijamos en que el 50 va y me llama enqueue 50,
y sale allí abajo en la parte inferior. Va en índice 0.
Sustituye a la 'hola' que fue quitado de la cola ya.
[Daniel] No se cuida de que en quitar de la cola ya?
¿Por qué hacer algo con la cabeza puesta en cola?
[Hardison] Oh, así que no estamos modificando la cabeza, lo siento.
Pero usted tiene que utilizar el operador mod cuando se está accediendo
el elemento que desea poner en cola cuando se está accediendo
el siguiente elemento en la cola.
[Basil] Yo no lo hice, y me dieron el "éxito" en ese país.
[Daniel] Oh, entiendo lo que estás diciendo.
[Hardison] Así que didn't - usted acaba de hacer en q.size?
[Basil] Yeah. Acabo de cambiar lados, yo no hice nada con la cabeza.
[Hardison] En realidad no tiene que restablecer la cabeza para ser cualquier cosa,
pero cuando se índice en la matriz cuerdas,
de hecho tienes que seguir adelante y calcular donde el elemento siguiente es,
porque withe la pila, el siguiente elemento de la pila siempre fue
en el índice correspondiente al tamaño.
Si echamos la vista atrás hacia nuestra función push pila,
siempre podemos desembolsar en nuestro elemento nuevo a la derecha en el tamaño del índice.
Mientras que con la cola, no podemos hacer eso
porque si estamos en esta situación,
si tenemos en cola 50 nuestra cadena de nuevo a la derecha en cadenas [1]
que no queremos hacer.
Queremos tener la nueva cadena va en el índice 0.
>> ¿Alguien - ¿Sí? [Estudiante] Tengo una pregunta, pero no es realmente relacionados.
¿Qué significa cuando alguien se llama algo así como puntero pred?
¿Cuál es la abreviatura de ese nombre? Sé que es sólo un nombre.
[Hardison] Pred puntero? Vamos a ver. ¿En qué contexto?
[Estudiante] Era para la inserción. Te puedo preguntar después si quieres
porque no es realmente relacionados, pero sólo I -
[Hardison] Desde el código de inserción de David de conferencia?
Podemos lograr eso y hablar de eso.
Hablaremos de eso después, una vez que lleguemos a listas enlazadas.
>> Así que vamos muy rápido vistazo a lo que la función de puesta en cola parece.
¿Qué fue lo primero que la gente trató de hacer en su línea de puesta en cola? En esta cola?
Al igual que lo que hiciste por pila empujando.
¿Qué hiciste, Stella?
[Stella, ininteligible]
[Hardison] Exactamente. Si (q.size CAPACIDAD ==) -
Tengo que poner mis llaves en el lugar correcto - devuelve falso.
Acercar un poco. Bien.
Ahora, ¿qué es lo siguiente que tenemos que hacer?
Al igual que con la pila, y se inserta en el lugar correcto.
Y lo que era el lugar adecuado para insertar eso?
Con la pila era tamaño del índice, con esto no es exactamente eso.
[Daniel] Tengo q.head--o - q.strings >>? >> Yeah.
q.strings [+ q.head q.size mod CAPACIDAD]?
[Hardison] Es probable que quiera poner entre paréntesis esta
por lo que estamos recibiendo la adecuada prioridad y por lo que es cleart a todo el mundo.
Y establece que la igualdad? >> Para str? >> Para str. Grande.
Y ahora, ¿qué es lo último que tenemos que hacer?
Al igual que hicimos en la pila. >> Incrementar el tamaño? >> Incrementar el tamaño.
Boom. Y luego, ya que el código de arranque sólo devuelve false de forma predeterminada,
queremos cambiar esta propiedad a true si todo va a través y todo va bien.
Está bien. Eso es un montón de información para la sección.
No estamos muy encima. Queremos hablar muy rápido sobre simplemente enlazada listas.
Voy a poner esto para que podamos volver a ella más tarde.
Pero volvamos a nuestra presentación por unos pocos más diapositivas.
Así enqueue es TODO, ahora lo hemos hecho.
>> Ahora echemos un vistazo a simplemente enlazada listas.
Hablamos de estos un poco más en clase.
¿Cuántos de ustedes vieron la demostración en la que había gente
torpemente señalando a cada uno de los otros números y explotación? >> Yo estaba en eso.
>> ¿Qué piensan ustedes? ¿Eso, espero que desmitificar estos poco un poco?
Con una lista, resulta que nos ocupamos de este tipo que vamos a llamar a un nodo.
Mientras que con la cola y pila que nos tomamos las estructuras que nos llaman a la cola en la pila,
teníamos estas nueva cola en los tipos de pila,
aquí una lista está realmente formado por un grupo de nodos.
De la misma manera que las cadenas son más que un montón de caracteres todos alineados uno al lado del otro.
Una lista enlazada es sólo un nodo y nodo a otro ya otro nodo y el nodo a otro.
Y en lugar de romper todos los nodos entre sí y su almacenamiento contigua
todos uno al lado del otro en la memoria,
teniendo este puntero siguiente nos permite almacenar los nodos donde sea, al azar.
Y a continuación, tipo de alambre a todos juntos para señalar de una a la siguiente.
>> ¿Y cuál fue la gran ventaja que esto tiene sobre una matriz?
Durante todo el almacenamiento contigua justo pegado uno al lado del otro?
¿Te acuerdas? ¿Sí? Asignación dinámica de memoria >>?
>> Asignación dinámica de memoria en qué sentido?
[Estudiante] En que se puede seguir haciendo más grande y usted no tiene que mover el conjunto completo?
[Hardison] Exactamente. Así que con una matriz, cuando usted quiere poner un nuevo elemento en el medio de ella,
usted tiene que cambiar todo para hacer espacio.
Y como hablamos con la cola,
es por eso que mantener ese puntero cabeza,
por lo que no estamos cambiando constantemente las cosas.
Debido a que resulta caro si tienes una gran variedad
y que está constantemente haciendo estas inserciones aleatorias.
Mientras que con una lista, lo único que tienes que hacer es tirar en un nuevo nodo,
ajustar los punteros, y ya está.
¿Qué mierda sobre esto?
Aparte del hecho de que no es tan fácil de trabajar como una matriz? ¿Sí?
[Daniel] Bueno, creo que es mucho más difícil tener acceso a un elemento específico de la lista enlazada?
[Hardison] No se puede saltar a un elemento arbitrario en el medio de tu lista enlazada.
¿Cómo se tiene que hacer en su lugar? >> Usted tiene que recorrer toda la cosa.
[Hardison] Yeah. Usted tiene que ir a través de uno en uno, uno a la vez.
Es un enorme - es un dolor.
¿Cuál es la otra - no hay otra caída a esto.
[Basil] No se puede ir hacia adelante y hacia atrás? Tienes que ir a una dirección?
[Hardison] Yeah. Entonces, ¿cómo resolver esto, algunas veces?
[Basil] doblemente enlazada listas? >> Exactamente. Hay listas doblemente enlazadas.
Hay también - lo siento?
>> [Sam] ¿Es eso lo mismo que usar lo que pred -
Acabo de recordar, ¿no es lo que la cosa pred sirve?
¿No es en el medio y doblemente solos?
Mirada [Hardison] Vamos a qué es exactamente lo que estaba haciendo.
Así que aquí vamos. Aquí está la lista de códigos.
Aquí tenemos predptr, aquí. ¿Es esto lo que estabas hablando?
Así que esta fue - que ha liberando una lista y que está tratando de almacenar un puntero a él.
Esta no es la doblemente, ligada simple-listas.
Podemos hablar más sobre esto más adelante ya que se habla de la liberación de la lista
y quiero mostrar algunas otras cosas primero.
pero es igual - es recordar el valor de ptr
[Estudiante] Oh, es puntero precedente? Sí >>.
Así que entonces sí puede incrementar ptr antes de entonces libre predptr lo es.
Porque no podemos gratis ptr y luego llamar a ptr = ptr siguiente, ¿no?
Eso sería malo.
Así que vamos a ver, de nuevo a este hombre.
>> La otra cosa mala acerca de las listas es que, si bien con una serie
sólo tenemos todos los elementos mismos apilados uno junto al otro,
aquí también hemos introducido este puntero.
Así que hay una porción adicional de memoria que estamos teniendo que utilizar
para cada elemento que se está almacenando en nuestra lista.
Tenemos la flexibilidad, pero tiene un costo.
Viene con el costo de tiempo,
y viene con este coste de memoria también.
Tiempo en el sentido de que ahora tenemos que ir a través de cada elemento de la matriz
para encontrar el índice de uno a 10, o que habría sido índice 10 en una matriz.
>> Sólo muy rápido, cuando nos diagrama cabo estas listas,
normalmente nos aferramos a la cabeza de la lista o el primer indicador de la lista
y cuenta que este es un puntero verdadero.
Está a sólo 4 bytes. No es un nodo en sí.
Así que ya ves que no tiene ningún valor int en ella, ningún puntero siguiente en el mismo.
Es, literalmente, sólo un puntero.
Se va a apuntar a algo que es una struct nodo actual.
[Sam] Puntero llamado nodo? >> Esta es - no. Este es un puntero a algo de tipo nodo.
Es un puntero a una estructura de nodo. >> Oh, está bien.
Diagrama sobre el código de la izquierda, a la derecha.
Podemos ponerlo en null, lo que es una buena manera de empezar.
Cuando lo diagrama, o bien escribir como nulo o se pone una línea a través de él de esa manera.
>> Una de las maneras más fáciles para trabajar con listas,
y les pedimos hacer las dos cosas anteponer y anexar a ver las diferencias entre los dos,
pero anteponiendo es definitivamente más fácil.
Cuando se antepone, aquí es donde usted - cuando usted prepend (7),
vas y crear la estructura de nodo
y se establece primero en señalarlo, porque ahora, ya que se antepone,
que va a estar al principio de la lista.
Si prepend (3), que crea otro nodo, pero 3 ahora viene antes de las 7.
Así que básicamente estás llevando las cosas a nuestra lista.
Ahora, usted puede ver que anteponer, a veces lo llaman empujar,
porque usted está empujando un nuevo elemento en su lista.
También es fácil de borrar en la parte delantera de una lista.
Así que la gente suele llamar a ese pop.
Y de esa forma, se puede emular una pila utilizando una lista enlazada.
Whoops. Lo siento, ahora estamos entrando en anexados. Así que aquí estamos antepuesto (7), ahora prepend (3).
Si se antepone otra cosa en esta lista, si se antepone (4),
entonces tendríamos 4 y luego 3 y luego 7.
Entonces podríamos pop y quitar 4, quitar 3, retire 7.
A menudo, la forma más intuitiva de pensar en esto es con anexados.
Así que he diagramado lo que se vería con añadir aquí.
En este sentido, añade (7) no se ve diferente
porque sólo hay un elemento en la lista.
Y añadiendo (3) lo pone al final.
Tal vez usted puede ver ahora el truco con append
es que desde que sólo sabe dónde está el principio de la lista es,
para anexar a una lista de lo que tienes que caminar todo el camino a través de la lista
para llegar a la final, detener, a continuación, crear el nodo y todo plunk abajo.
Cablear todas las cosas.
Así que con prefijo, como se acaba de copiar a través de este muy rápido,
cuando se antepone a una lista, que es bastante simple.
>> Usted hace su nuevo nodo, implican alguna asignación de memoria dinámica.
Así que aquí estamos haciendo un struct nodo usando malloc.
Así que estamos usando malloc, ya que va a dejar de lado la memoria por nosotros para más adelante
porque no queremos que esto - queremos que esta memoria a persistir durante mucho tiempo.
Y tenemos un puntero al espacio en la memoria que acaba de ser asignado.
Utilizamos tamaño del nodo, no concretamos los campos.
No generar manualmente el número de bytes,
en lugar de eso usar sizeof para que sepamos que estamos recibiendo la cantidad adecuada de bytes.
Nos aseguramos de probar que nuestra llamada malloc éxito.
Esto es algo que quiero hacer en general.
En las máquinas modernas, quedando sin memoria no es algo que es fácil
a menos que la asignación de un montón de cosas y hacer una lista enorme,
pero si usted está construyendo cosas para, por ejemplo, como un iPhone o Android an,
que tienen recursos limitados de memoria, especialmente si usted está haciendo algo intenso.
Así que es bueno tener en la práctica.
>> Tenga en cuenta que he usado un par de funciones diferentes aquí
que usted ha visto que son una especie de nuevo.
Así fprintf es como printf
excepto su primer argumento es la corriente a la que desea imprimir.
En este caso, queremos imprimir en la cadena de error estándar
que es diferente de la outStream estándar.
Por defecto se muestra en el mismo lugar.
También imprime a la terminal, pero se puede -
utilizando los comandos que ha aprendido acerca de las técnicas de redireccionamiento,
que aprendimos en vídeo de Tommy como conjunto de problemas 4, puede dirigirla
a las diferentes áreas, a continuación, salir, aquí, sale de su programa.
Básicamente se trata de como volver a principal,
excepto que utilizamos salida porque aquí retorno no hará nada.
No estamos en principal, por lo que regresa no se salga del programa como nosotros queremos.
Por eso, utilizamos la función de salida y darle un código de error.
Entonces aquí nos pusimos campo del nuevo nodo de valor, su campo i sea igual a i, y luego lo cablear.
Hemos establecido puntero siguiente del nuevo nodo para señalar a la primera,
y luego primera ahora apuntará al nuevo nodo.
Estas primeras líneas de código, en realidad estamos construyendo el nuevo nodo.
No las dos últimas líneas de esta función, pero los primeros.
En realidad se puede extraer en una función, en una función auxiliar.
Eso es muchas veces lo que hago es que me tire en una función,
Yo lo llamo algo como nodo de generación,
y que mantiene la función prepend bastante pequeño, es sólo 3 líneas a continuación.
Hago una llamada a mi función de nodo de generación, y entonces todo alambre hacia arriba.
>> La última cosa que quiero mostrarte,
y voy a dejar que hagas append y todo eso por su cuenta,
es la forma de iterar sobre una lista.
Hay un montón de maneras diferentes para iterar sobre una lista.
En este caso, vamos a calcular la longitud de una lista.
Así que empezamos con longitud = 0.
Esto es muy similar a la escritura strlen para una cadena.
Esto es lo que quiero mostrar, para este circuito aquí.
Se parece un poco cobarde, no es el típico int i = 0, i <lo que sea, i + +.
En su lugar, está la inicialización de nuestra variable n como el comienzo de la lista.
Y entonces, mientras la variable iterador no es nulo, es seguir adelante.
Esto se debe a que, por convención, el final de la lista será nulo.
Y a continuación, para incrementar, en lugar de hacer + +,
el equivalente lista vinculada de + + es n = n-> siguiente.
>> Voy a dejar de llenar los vacíos aquí porque estamos fuera de tiempo.
Pero hay que tener esto en mente a medida que trabaja en conjuntos de procesadores tus spellr.
Las listas enlazadas, si está implementando una tabla hash,
sin duda vendrá en muy práctico.
Y tener este idioma para recorrer las cosas van a hacer la vida mucho más fácil, con suerte.
Cualquier pregunta, rápidamente?
[Sam] ¿Va a enviar el terminado sll y sc?
[Hardison] Yeah. Voy a enviar diapositivas terminadas y la pila completa sll y queue.cs.
[CS50.TV]