[Powered by Google Translate] [Artículo 6] [más cómodo]
[Rob Bowden] [Harvard University]
[Esta es CS50.] [CS50.TV]
>> Nos puede dirigirse a nuestra sección de preguntas.
Envié a la dirección del espacio antes.
El principio de la sección de las preguntas-decir
al parecer, no estoy del todo unsick-Es una pregunta muy fácil
de lo que se acaba de valgrind?
¿Qué valgrind hacer?
¿Alguien quiere decir lo valgrind hace?
[Estudiante] comprueba la memoria de fugas.
Sí, valgrind es un corrector de memoria general.
Es, en definitiva, le dice si tiene alguna pérdida de memoria,
que es sobre todo lo que se está usando para porque si quieres
bien en el conjunto de problemas o si desea
conseguir en el gran tablero, es necesario no tener pérdidas de memoria en absoluto,
y en caso de tener una pérdida de memoria que no se puede encontrar,
También tenga en cuenta que cada vez que abra un archivo
y si no lo cierra, eso es una pérdida de memoria.
>> Mucha gente está buscando algún nodo que no están liberando
cuando en realidad, no cerrar el diccionario en el primer paso.
También le indica si usted tiene cualquiera inválido lee o escribe,
lo que significa que si usted trata de establecer un valor
que está más allá del final de la pila y no pasa a la culpa seg
pero valgrind lo coge, ya que en realidad no debería estar escribiendo allí,
y por lo que definitivamente no debería tener ninguno de esos tampoco.
¿Cómo se utiliza Valgrind?
>> Es un problema general de
tipo de ejecutarlo y ver el resultado.
La salida está abrumando un montón de veces.
También hay errores de diversión donde si tienen alguna cosa mal, muy mal
ocurre en un bucle, a continuación, con el tiempo se dice: "Demasiados errores.
Voy a dejar de contar ahora ".
Se trata básicamente de una salida de texto que hay que analizar.
Al final, le dirá cualquier fuga de memoria que tiene,
cuántos bloques, que puede ser útil porque
si se trata de un unfreed bloque, entonces por lo general es más fácil de encontrar
de 1.000 bloques unfreed.
1.000 bloques unfreed probablemente significa que no estás liberando
sus listas enlazadas adecuadamente o algo así.
Eso valgrind.
>> Ahora tenemos nuestra sección de preguntas,
que no es necesario para descargar.
Puede hacer clic en mi nombre y tire hacia arriba en el espacio.
Ahora haga clic en mí.
Revisión 1 será pila, lo que estamos haciendo en primer lugar.
Revisión 2 será cola y Revisión 3 será la lista ligada sencilla.
Partiendo de nuestra pila.
Como se dice aquí, una pila es uno de los más básicos,
estructuras de datos fundamentales de la informática.
El ejemplo prototípico es muy
la pila de bandejas en el comedor.
Es, básicamente, cada vez que se introducen a una pila,
alguien va a decir: "Oh, como una pila de bandejas".
Usted apilar las bandejas de arriba.
Entonces, cuando usted va a tirar una bandeja,
la primera bandeja que está dejándonos arrastrar es el último que se puso en la pila.
La pila también-como dice aquí-
tenemos el segmento de memoria llamada pila.
¿Y por qué se llama la pila?
>> Porque al igual que una estructura de datos pila,
lo empuja y hace estallar los marcos de pila a la pila,
donde los marcos de pila es como una llamada de una función.
Y al igual que una pila, siempre tendrá que volver
a partir de una llamada a la función antes de que pueda ponerse en marcos de pila baja de nuevo.
No se puede tener llamada principal bar llamado foo bar y volver a directamente principal.
Siempre tiene que seguir la pila correcta empujando y haciendo estallar.
Las dos operaciones, como he dicho, son push y pop.
Esos son términos universales.
Usted debe saber push y pop en términos de pilas sin importar lo que pase.
Vamos a ver las colas son un poco diferentes.
En realidad no tienen un término universal, pero push y pop son universales para pilas.
Inserción se acaba de poner en la pila.
Pop es quitar la pila.
Y vemos aquí tenemos nuestra pila struct typedef,
así que tenemos carbón cuerdas **.
No te asustes por cualquier **.
Esto va a terminar siendo una matriz de cadenas
o una matriz de punteros a caracteres, donde
punteros a caracteres tienden a ser cadenas.
No tiene por qué ser cadenas, pero aquí, que van a ser cadenas.
>> Tenemos una matriz de cadenas.
Tenemos un tamaño, que representa cuántos elementos hay actualmente en la pila,
y entonces tenemos la capacidad, que es cómo los elementos que pueden estar en la pila.
La capacidad debe comenzar como algo mayor que 1,
pero el tamaño que va a empezar a 0.
Ahora, hay básicamente tres maneras diferentes que usted puede pensar en una pila.
Bueno, probablemente hay más, pero son las dos formas principales
se puede implementar utilizando una matriz, o se puede implementar utilizando una lista enlazada.
Las listas enlazadas son una especie de trivial de hacer montones de.
Es muy fácil hacer una pila con listas enlazadas,
Así que aquí, vamos a hacer una pila con matrices,
y luego usando arrays, también hay dos maneras de pensar en ello.
Antes, cuando me dijo que tenemos una capacidad de la pila,
por lo que puede encajar un elemento en la pila.
>> La única manera que podría suceder es tan pronto como se golpeó 10 elementos, entonces ya está.
Usted puede saber que hay un límite superior de 10 cosas en el mundo
que nunca tendrá más de 10 cosas en su pila,
en cuyo caso puede tener un límite superior en el tamaño de su stack.
O usted podría tener su stack ser ilimitada,
pero si usted está haciendo un arreglo, lo que significa que cada vez que conectó 10 elementos,
entonces usted va a tener que crecer a 20 elementos, y cuando llegue a 20 elementos,
usted va a tener que hacer crecer su matriz a 30 elementos o elementos 40.
Vas a tener que aumentar la capacidad, que es lo que vamos a hacer aquí.
Cada vez que alcance el tamaño máximo de nuestro stack,
cuando empujamos algo más adelante, vamos a tener que aumentar la capacidad.
Aquí, hemos declarado como empuje empuje bool (char * str).
* Char str es la cadena que estamos impulsando en la pila,
bool y sólo dice si hemos tenido éxito o ha fracasado.
>> ¿Cómo no?
¿Cuál es la única circunstancia que se pueda imaginar
donde nos teníamos que volver falsa?
Si.
[Estudiante] Si es completo y estamos usando una aplicación limitada.
Sí, así que ¿cómo podemos definir-respondió
si está lleno y estamos usando una aplicación limitada.
Entonces sin duda volveremos falsa.
Tan pronto como llegamos a las 10 cosas de la matriz, no podemos encajar 11, por lo que devuelve falso.
¿Y si no tiene límites? Si.
Si no se puede expandir la matriz por alguna razón.
Sí, así que la memoria es un recurso limitado,
y, finalmente, si guardamos las cosas que empujan en la pila una y otra vez,
vamos a tratar de asignar una matriz más grande para encajar
el de mayor capacidad, y malloc o lo que sea que estamos usando se va a devolver false.
Bueno, malloc devolverá null.
>> Recuerde, cada vez que vuelvas a llamar malloc, usted debe comprobar para ver si
devuelve un valor nulo o de lo que es una deducción correcta.
Como queremos tener una pila sin límites,
el único caso que vamos a devolver false si es que tratamos de
aumentar la capacidad y malloc o lo devuelve false.
Luego pop no tiene argumentos,
y devuelve la cadena que está en la parte superior de la pila.
Lo más reciente fue en la pila pop es lo que va a regresar,
y también se elimina de la pila.
Y note que devuelve null si no hay nada en la pila.
Siempre es posible que la pila está vacía.
En Java, si estás acostumbrado a eso, o en otros idiomas,
tratando de hacer estallar de una pila vacía puede provocar una excepción o algo así.
>> Pero en C, null es algo que muchos de los casos, cómo manejar estos problemas.
Volviendo nula es cómo vamos a indicar que la pila estaba vacío.
Hemos proporcionado el código que pondrá a prueba la funcionalidad de su pila, el
implementar push y pop.
Esto no va a haber un montón de código.
Lo haré-en realidad, antes de hacer eso, pista, pista-
si usted no lo ha visto, malloc no es la única función
que asigna memoria en el montón para usted.
Hay una familia de funciones Alloc.
La primera es malloc, que estamos acostumbrados.
Luego está calloc, que hace lo mismo que malloc,
pero va a cero todo para ti.
Si alguna vez has querido poner todo en nulo después mallocing algo
usted debe haber utilizado calloc en primer lugar en vez de escribir
un bucle for para poner en cero el bloque de memoria.
>> Realloc es como malloc y tiene un montón de casos especiales,
pero básicamente lo que hace es realloc
Se tarda un puntero que ya había sido asignado.
Realloc es la función que desee prestar atención a aquí.
Se toma un puntero que ya se habían vuelto de malloc.
Digamos que solicitar a malloc un puntero de 10 bytes.
Luego, más tarde te das cuenta de que querían 20 bytes,
así que llame realloc en ese puntero con 20 bytes,
y realloc copiará automáticamente sobre todas las cosas para usted.
Si usted acaba de llamar a malloc otra vez, como si tuviera un bloque de 10 bytes.
Ahora necesito un bloque de 20 bytes,
así que si malloc 20 bytes, entonces tengo que copiar manualmente durante los 10 bytes de la primera cosa
en lo segundo y luego liberar la primera cosa.
Realloc se encargará de eso por ti.
>> Note la firma va a ser void *,
que se acaba de devolver un puntero al bloque de memoria,
entonces void * ptr.
Usted puede pensar void * como un puntero genérico.
Por lo general, no tiene que tratar con void *,
pero malloc devuelve un void *, y entonces es sólo utilizado como
esto es en realidad va a ser un char *.
La void * anterior que había sido devuelto por malloc
ahora va a pasar a realloc, y luego el tamaño
es el nuevo número de bytes que desea asignar, por lo que su nueva capacidad.
Te voy a dar un par de minutos, y hacerlo en nuestro espacio.
Comience con Revisión 1.
Te voy a parar después de esperar alrededor de tiempo suficiente para aplicar presión,
y luego me voy a dar otro descanso para hacer pop.
Pero en realidad no es que el código mucho a todos.
La mayoría del código es probablemente la materia en expansión, la expansión de la capacidad.
Está bien, no hay presión para estar completamente terminado,
pero siempre y cuando usted se siente como si estuvieras en el camino correcto, eso es bueno.
>> ¿Alguien tiene algún código que se sientan cómodos conmigo tirando hacia arriba?
Sí, lo haré, pero ¿alguien tiene algún código que pueda levantar?
De acuerdo, puede empezar, lo guarda, lo que sea?
Siempre se me olvida ese paso.
Bueno, mirando push,
¿quieres explicar tu código?
[Estudiante] En primer lugar, he aumentado el tamaño.
Supongo que tal vez yo debería tener eso, de todos modos, he aumentado el tamaño,
y veo si es menor que la capacidad.
Y si es inferior a la capacidad, que se añaden al sistema que ya tenemos.
Y si no lo es, yo multiplicar la capacidad por 2,
y reasignar la matriz de cadenas a algo con un tamaño mayor capacidad ahora.
Y si eso no funciona, le digo al usuario y devolver false,
y si está bien, entonces puse la cadena en el nuevo lugar.
>> [Rob B.] Observe también que se utilizó un buen operador de bits aquí
a multiplicar por 2.
Recuerde, desviación a la izquierda siempre va a ser multiplicado por 2.
Desplazamiento a la derecha se divide por 2, siempre y cuando recuerde que esto significa
dividir por 2 como en un número entero dividido por 2.
Puede truncar un 1 aquí o allá.
Pero desplazamiento a la izquierda por una siempre va a ser multiplicado por 2,
a menos que desbordamiento de los límites del número entero, y entonces no será.
Un comentario al margen.
Me gusta hacer, esto no va a cambiar la codificación de cualquier manera que sea,
pero me gustaría hacer algo como esto.
En realidad, se va a hacer un poco más.
Tal vez este no es el caso perfecto para demostrar esto,
pero me gusta segmento que en estos bloques de-
bien, si esto si sucede, entonces yo voy a hacer algo,
y entonces la función se lleva a cabo.
Yo no tenga que desplazarse luego mis ojos todo el camino por la función
para ver lo que pasa después de la otra persona.
Es este caso, si ocurre, entonces simplemente volver.
También tiene el beneficio añadido de todo lo bueno más allá de esta
está desplazado a la izquierda una vez.
Ya no necesito a si alguna vez cerca ridículamente largas filas,
entonces esos 4 bytes puede ayudar, y también es el algo más a la izquierda,
el menor se sienta abrumado si gusta-bueno, tengo que recordar
Actualmente estoy en un bucle while dentro de un interior más de un bucle for.
En cualquier lugar que usted puede hacer este cambio de inmediato, me gusta bastante.
Es totalmente opcional y no se espera de ninguna manera.
>> [Estudiante] ¿Debe existir un tamaño - en la condición de fallo?
La condición de falla aquí es que no realloc, así que sí.
Observe cómo en la condición de fallo, presumiblemente,
a menos que la materia libre más tarde, siempre vamos a fallar
no importa cuántas veces tratamos de empujar algo.
Si seguimos presionando, seguimos incrementando el tamaño,
a pesar de que no está poniendo nada en la pila.
Por lo general, no incrementan el tamaño hasta
después hemos logrado ponerlo en la pila.
Por lo que le hacemos, decimos, ya sea aquí y aquí.
Y entonces, en lugar de decir s.size capacidad ≤, es inferior a la capacidad,
sólo porque nos mudamos dónde estaba todo.
>> Y recuerde, el único lugar que podría devolver false
Es aquí, donde realloc devuelve null,
y si te quedas a recordar error estándar,
tal vez usted podría considerar este caso, una en la que desea imprimir un error estándar,
stderr fprintf así en lugar de imprimir directamente en la salida estándar.
Una vez más, eso no es una expectativa, pero si se trata de un error,
escribir printf, entonces es posible que desee hacer que imprima a un error estándar en lugar de la salida estándar.
>> ¿Alguien tiene algo más que observar? Sí.
[Estudiante] ¿Se puede pasar el [inaudible]?
[Rob B.] Sí, el binariness real de él o sólo lo que es?
[Estudiante] Así lo multiplicas por 2?
[Rob B.] Sí, básicamente.
En tierra binario, siempre tenemos nuestro conjunto de dígitos.
Desplazamiento de esta izquierda por un Básicamente se inserta aquí en el lado derecho.
Volver a esto, sólo recordar que todo en binario
es una potencia de 2, por lo que esto representa 2 al 0,
este 2 a la 1, 2 esta a la 2.
Mediante la inserción de un 0 a un lado ahora mismo, simplemente cambiar todo de nuevo.
Lo que solía ser de 2 a 0 es ahora de 2 a 1, es 2 a la 2.
El lado derecho que insertamos
necesariamente va a ser 0,
lo cual tiene sentido.
Si alguna vez multiplicar un número por 2, que no va a terminar extraño,
por lo que el 2 a 0 el lugar debe ser 0,
y esto es lo que media advertido antes es que si te quedas a pasar
más allá del número de bits en un número entero,
entonces este 1 va a terminar sonando.
Esa es la única preocupación si usted sucede estar tratando con capacidades muy grandes.
Pero en ese momento, entonces usted está tratando con un arsenal de miles de millones de cosas,
que no pudo caber en la memoria de todos modos.
>> Ahora podemos llegar a pop, lo cual es aún más fácil.
Podrías me gusta si te ocurre hacer estallar un montón,
y ahora está a la mitad de la capacidad de nuevo.
Usted podría realloc para reducir la cantidad de memoria que tiene,
pero usted no tiene que preocuparse por eso, por lo que el caso realloc sólo va a ser
creciente memoria, nunca encogimiento memoria,
que va a hacer súper pop fácil.
Ahora colas, que van a ser como pilas,
pero el fin de que se tome las cosas se invierte.
En el ejemplo prototípico de una cola es una línea,
así que supongo que si fueras Inglés, habría dicho
un ejemplo prototípico de una cola es una cola.
Así como una línea, si usted es la primera persona en la fila,
que espera ser la primera persona fuera de la línea.
Si usted es la última persona en la fila, usted va a ser la persona atendida pasado.
A eso le llamamos modelo FIFO, mientras pila era patrón LIFO.
Esas palabras son bastante universal.
>> Al igual que las pilas y no como los arrays, las colas no suelen permitir el acceso a los elementos del medio.
Aquí, una pila, tenemos push y pop.
A continuación, pasamos a los he llamado en cola y quitar de la cola.
También he oído que llama cambio y unshift.
He oído a gente decir push y pop también se aplican a las colas.
He oído a insertar, eliminar,
así push y pop, si usted está hablando de pilas, que está empujando y haciendo estallar.
Si usted está hablando acerca de las colas, se puede escoger las palabras que desea utilizar
para la inserción y eliminación, y no hay consenso sobre lo que debe ser llamado.
Pero aquí, tenemos que poner en cola y quitar de la cola.
Ahora bien, la estructura se ve casi idéntica a la estructura de la pila.
Pero tenemos que hacer un seguimiento de la cabeza.
Supongo que lo dice por aquí, pero ¿por qué necesitamos la cabeza?
Los prototipos son básicamente idénticos a push y pop.
Usted puede pensar en él como push y pop.
La única diferencia es pop vuelve-en lugar de la última, está devolviendo la primera.
2, 1, 3, 4, o algo así.
Y aquí está el principio.
Nuestra cola está completamente lleno, así que hay cuatro elementos que contiene.
El final de nuestra cola es actualmente 2,
y ahora vamos a insertar otra cosa.
>> Cuando queremos insertar ese algo más, lo que hicimos para la versión de pila
Se ampliamos nuestro bloque de memoria.
¿Cuál es el problema con esto?
[Estudiante] Mueve el 2.
Lo que dije antes sobre el extremo de la cola,
esto no tiene sentido que empecemos a 1,
entonces queremos quitar de la cola 1, luego quitar de la cola 3, luego quitar de la cola 4,
a continuación, quitar de la cola 2, a continuación, quitar de la cola de éste.
No podemos usar realloc ahora,
o por lo menos, usted tiene que utilizar realloc de una manera diferente.
Pero es probable que no sólo debe utilizar realloc.
Usted va a tener que copiar manualmente la memoria.
>> Existen dos funciones para copiar la memoria.
Hay memcopy y memmove.
Actualmente estoy leyendo las páginas del manual para ver cuál te va a querer usar.
Bueno, memcopy, la diferencia es
que memcopy y memmove, uno maneja el caso correctamente
donde está copiando en una región que pasa a superponerse a la región
que está copiando.
Memcopy no manejarlo. Memmove hace.
Usted puede pensar en el problema, ya que-
digamos que desea copiar este tipo,
estos cuatro a este tipo otra vez.
Al final, lo que la matriz debe ser similar
después de que la copia es 2, 1, 2, 1, 3, 4, y luego un poco de materia en el extremo.
Pero esto es dependiente del orden en el que realmente copiar,
ya que si no consideramos el hecho de que la región se está copiando en
se superpone a la que estamos copiando de,
entonces podríamos hacer aquí como inicio, copie el 2 en el lugar al que desea ir,
a continuación, pasar a nuestros punteros hacia adelante.
>> Ahora vamos a estar aquí y aquí, y ahora queremos copiar
este tipo a través de este tipo y mover nuestros punteros hacia adelante.
Lo que vamos a terminar recibiendo es de 2, 1, 2, 1, 2, 1
en lugar de la 2, 1, 2, 1, 3, 4 porque
2, 1 hizo caso omiso de la original 3, 4.
Memmove que maneja correctamente.
En este caso, básicamente, sólo utilice siempre memmove
porque se maneja correctamente.
Por lo general, no realiza ninguna peor.
La idea es en lugar de comenzar desde el principio y la copia de esta manera
como lo acaba de hacer aquí, se inicia desde el extremo y lo copia en,
y en ese caso, nunca se puede tener un problema.
No hay pérdida de rendimiento.
Utilice siempre memmove. No te preocupes por memcopy.
Y ahí es donde usted va a tener que memmove por separado
la porción envuelta-en torno de su cola.
No se preocupe si no está completamente terminado.
Esto es más difícil que la pila, empuje, y el pop.
>> ¿Alguien tiene algún código que podríamos trabajar?
Aunque totalmente incompleto?
[Estudiante] Sí, es totalmente incompleto, sin embargo.
Completamente incompleto está bien, siempre y cuando, se puede ahorrar la revisión?
Me olvido de que cada vez.
Bueno, haciendo caso omiso de lo que sucede cuando tenemos que cambiar el tamaño de las cosas.
Ignoran por completo cambio de tamaño.
Explicar este código.
Estoy comprobando en primer lugar si el tamaño es menor que la primera copia de todos
y después de eso, inserto-I + tomar la cabeza de tamaño,
y me aseguro de que se envuelve alrededor de la capacidad de la matriz,
y puedo insertar la nueva cadena en esa posición.
Entonces puedo aumentar el tamaño y devolver true.
>> [Rob B.] Este es definitivamente uno de esos casos en que vas a querer usar mod.
Cualquier tipo de caso en el que ha de envolver alrededor, si te parece envolver alrededor,
el primer pensamiento debe ser mod.
Como una optimización rápida / hacer que el código una línea más corta,
te das cuenta de que la línea inmediatamente después de éste
es sólo el tamaño + +, por lo que se fusionan en esta línea, el tamaño + +.
Ahora aquí abajo, tenemos el caso
en el que no tiene suficiente memoria,
por lo que estamos aumentando nuestra capacidad por 2.
Creo que se puede tener el mismo problema aquí, pero podemos ignorarla ahora,
donde si no para aumentar su capacidad,
entonces usted va a querer disminuir su capacidad de 2 de nuevo.
Otra nota corta es igual que lo puede hacer + =,
también se puede hacer << =.
Casi cualquier cosa puede pasar antes de iguales, + =, | =, + =, << =.
Char * nuevo es nuestro nuevo bloque de memoria.
Oh, por aquí.
>> ¿Qué piensa la gente de la clase de nuestro nuevo bloque de memoria?
[Estudiante] Debe ser char **.
Pensando en nuestra estructura hasta aquí,
cadenas es lo que estamos reasignando.
Estamos haciendo toda una nueva dinámica para el almacenamiento de los elementos de la cola.
Lo que vamos a asignar a las cadenas es lo que estamos mallocing en este momento,
y tan nuevo que va a ser un char **.
Va a ser una matriz de cadenas.
Entonces, ¿cuál es el caso en el que nos vamos a volver falso?
[Estudiante] Deberíamos estar haciendo char *?
[Rob B.] Sí, buena idea.
[Estudiante] ¿Qué fue eso?
[Rob B.] Queríamos hacer tamaño de char * porque ya no somos-
en realidad esto sería un problema muy grande porque sizeof (char) sería 1.
Sizeof char * va a ser 4,
por lo que una gran cantidad de ocasiones en las que estamos tratando enteros,
se tiende a salirse con la suya porque el tamaño de int y el tamaño de int *
en un sistema de 32-bit va a ser la misma cosa.
Pero aquí, sizeof (char) y sizeof (char *) son ahora va a ser la misma cosa.
>> ¿Cuál es la circunstancia en la que volvemos falso?
[Estudiante] Nuevo es nulo.
Sí, si es nuevo es nulo, se devuelve falso,
y me voy a tirar por aquí-
[Estudiante] [inaudible]
[Rob B.] Sí, esto está muy bien.
Usted podría hacer 2 veces la capacidad o la capacidad de un cambio, y sólo entonces la coloque aquí o lo que sea.
Lo haremos como lo teníamos.
Capacidad >> = 1.
Y nunca vamos a tener que preocuparse de perder su lugar el 1
porque te fuiste cambiado por 1, por lo que el 1 de lugar es necesariamente un 0,
tan a la derecha por un cambio, usted todavía va a estar bien.
[Estudiante] ¿Es necesario hacerlo antes del regreso?
[Rob B.] Sí, esto no tiene ningún sentido.
>> Ahora supongamos que vamos a terminar devolviendo true hasta el final.
La forma en que vamos a hacer estas memmoves,
tenemos que tener cuidado con la forma en que ellos lo hacen.
¿Alguien tiene alguna sugerencia de cómo lo hacemos?
Este es nuestro principio.
Inevitablemente, queremos empezar desde el principio otra vez
y cosas de copia en desde allí, 1, 3, 4, 2.
¿Cómo se hace eso?
En primer lugar, tengo que mirar en la página de manual de memmove nuevo.
Memmove, el orden de los argumentos de siempre es importante.
Queremos que nuestro primer destino, la segunda fuente, la tercera tamaño.
Hay una gran cantidad de funciones que revierten origen y destino.
Destino, la fuente tiende a ser algo consistente.
Mover, lo que se lo va a devolver?
Devuelve un puntero al destino, por cualquier razón usted podría querer eso.
Me imagino a leerlo, pero queremos avanzar en nuestro destino.
>> ¿Cuál es nuestro destino va a ser?
[Estudiante] Nuevo.
[Rob B.] Sí, y ¿dónde estamos copiando?
Lo primero que está copiando es este 1, 3, 4.
¿Cuál es el este-1, 3, 4.
¿Cuál es la dirección de este 1?
¿Cuál es la dirección de que 1?
[Estudiante] [inaudible]
[Rob B.] + Cara la dirección del primer elemento.
¿Cómo hacemos para que el primer elemento de la matriz?
[Estudiante] Queue.
[Rob B.] Sí, q.strings.
Recuerde, aquí, nuestra cabeza: 1.
Maldita sea. Yo sólo creo que es por arte de magia-
Aquí, nuestro jefe es 1. Voy a cambiar mi color también.
Y aquí está cuerdas.
Esto, nos puede escribir como lo hicimos aquí
con cabezas + q.strings.
Mucha gente también escribe y q.strings [cabeza].
Esto no es realmente algo menos eficiente.
Se podría pensar en ella como lo está dereferencing y luego obtener la dirección de,
pero el compilador va a traducir a lo que teníamos antes de todos modos, q.strings + cabeza.
De cualquier manera que usted desea pensar en ello.
>> Y cuántos bytes queremos copiar?
[Estudiante] Capacidad - cabeza.
Capacidad - cabeza.
Y entonces siempre se puede escribir un ejemplo
para averiguar si es cierto.
[Estudiante] Tiene que ser dividido por 2 a continuación.
Sí, así que supongo que podría utilizar tamaño.
Todavía tenemos tamaño es-
usando tamaño, que tienen un tamaño igual a 4.
Nuestro tamaño es 4. Nuestra cabeza es 1.
Queremos copiar estos 3 elementos.
Esa es la comprobación de validez de ese tamaño - cabeza está correctamente 3.
Y regresando aquí, como hemos dicho antes,
si utilizamos la capacidad, entonces tendríamos que dividir por 2
porque ya hemos crecido nuestra capacidad, por lo que en su lugar, vamos a utilizar el tamaño.
Que las copias de las porciones.
Ahora, tenemos que copiar la otra parte, la parte que queda de la salida.
>> Eso va a memmove en qué posición?
[Estudiante] más del tamaño - la cabeza.
Sí, por lo que ya ha copiado en el tamaño - bytes de la cabeza,
y por lo tanto donde queremos copiar los bytes restantes es nuevo
y luego el tamaño de menos-bien, el número de bytes que ya hemos copiado pulg
Y entonces, ¿dónde estamos copiando?
[Estudiante] Q.strings [0].
[Rob B.] Sí, q.strings.
Podíamos hacer y q.strings [0].
Esto es significativamente menos frecuente que esto.
Si sólo va a ser 0, entonces usted tiende a ver q.strings.
Ahí es donde estamos copiando.
¿Cuántos bytes qué nos queda para copiar? >> [Estudiante] 10.
Derecha.
[Estudiante] ¿Tenemos que multiplicar 5 - 10 veces el tamaño de los bytes o algo así?
Sí, así es, ¿qué es exactamente donde estamos copiando?
[Estudiante] [inaudible]
¿Cuál es el tipo de cosa que está copiando?
[Estudiante] [inaudible]
Sí, por lo que el char * s que estamos copiando, no sé de dónde los están viniendo.
Bueno, ¿dónde están señalando, como las cuerdas, terminamos empujando a la cola
o enqueuing en la cola.
Cuando los están viniendo, no tenemos ni idea.
Sólo tenemos que perder de vista el char * s mismos.
No queremos copiar tamaño - bytes cabeza.
Queremos copiar tamaño - cabeza char * s,
así que vamos a multiplicarlo por sizeof (char *).
Igual aquí abajo, la cabeza * sizeof (char *).
>> [Estudiante] ¿Qué pasa con [inaudible]?
Este derecho aquí?
[Estudiante] No, más abajo, el tamaño - la cabeza.
[Rob B.] Este derecho aquí?
Aritmética de punteros.
Cómo aritmética de punteros se va a trabajar es
automáticamente se multiplica por el tamaño del tipo que estamos tratando.
Al igual que aquí, nuevo + (tamaño - la cabeza)
es exactamente equivalente a & [size - cabeza] nuevo
hasta que esperamos que funcione correctamente,
ya que si estamos tratando con una matriz int, entonces no lo hacemos índice int-
o si es de un tamaño de 5 y desea que el 4 º elemento, entonces el índice en
int matriz [4].
Usted no-[4] * El tamaño de int.
Eso se maneja de forma automática, y en este caso
es, literalmente, equivalente, por lo que la sintaxis de soporte
es sólo va a ser convertido en esto tan pronto como se compila.
Eso es algo que tienes que tener cuidado de que
al agregar tamaño - cabeza
va a agregar no un byte.
Usted va a añadir un char *, que puede ser una bytes o lo que sea.
>> Otras preguntas?
Está bien, quitar de la cola va a ser más fácil.
Te voy a dar un minuto de implementar.
Oh, y supongo que esta es la misma situación en que
lo que el caso en cola, si estamos enqueuing nulo,
tal vez queremos manejarlo, tal vez no lo hacemos.
No lo volveré a hacer aquí, pero igual que nuestro caso pila.
Si encolar nulo, lo que se quiere es pasar por alto.
¿Alguien tiene algún código que puede levantar?
[Estudiante] Sólo tengo quitar de la cola.
La versión 2 es que-bien.
Usted quiere explicar?
[Estudiante] En primer lugar, asegúrese de que hay algo en la cola
y que el tamaño va a la baja en 1.
Que tiene que hacer eso, y luego que regrese la cabeza
y luego mover la cabeza hacia arriba 1.
Está bien, así que hay un caso de la esquina tenemos que tener en cuenta. Si.
[Estudiante] Si tu cabeza está en el último elemento,
entonces usted no quiere la cabeza para señalar fuera de la matriz.
>> Sí, tan pronto como la cabeza en la final de nuestra matriz,
cuando quitar de la cola, la cabeza debe ser modded nuevo a 0.
Desafortunadamente, no podemos hacer eso en un solo paso.
Creo que la forma en que probablemente solucionarlo es
esto va a ser un char *, lo que estamos regresando,
sea ​​cual sea su nombre de la variable quiere ser.
Entonces queremos mod cabeza por nuestra capacidad
y luego regresar ret.
Mucha gente de aquí se podría hacer-
Este es el caso de-usted ver a la gente hacer si la cabeza
es mayor que la capacidad, hacer la cabeza - la capacidad.
Y eso es sólo trabajar en torno a lo que es mod.
Jefe mod = capacidad es mucho más limpio
de una envoltura alrededor de si la cabeza más grande que la cabeza de capacidad - capacidad.
>> ¿Preguntas?
Bueno, lo último que nos queda es nuestra lista enlazada.
Puede ser utilizado para algunos de los comportamientos lista enlazada si lo has hecho
listas enlazadas en las tablas hash, si se hizo una tabla hash.
Recomiendo hacer una tabla hash.
Es posible que ya han hecho un trie,
sino que trata son más difíciles.
En teoría, son asintóticamente mejor.
Pero basta con ver la gran pizarra,
y trata de no hacer mejor, y ocupan más memoria.
Todo lo relacionado intenta termina siendo peor para un trabajo más.
Es lo que David Malan solución siempre es
¿Siempre posts su solución trie, y vamos a ver donde actualmente está.
Lo que él estaba bajo, David J?
Es n º 18, de modo que no es terriblemente malo,
y que va a ser uno de los mejores intentos que se pueda imaginar
o uno de los mejores trata de un trie.
¿No es siquiera su solución original?
Me siento como trie soluciones tienden a ser más en este rango de uso de memoria RAM.
>> Ve a la parte superior, y el uso de la memoria RAM es de un solo dígito.
Ir hacia el fondo, y luego se empiezan a ver intenta
donde se obtiene el uso de RAM absolutamente masiva,
y tries son más difíciles.
No del todo, pero vale la pena una experiencia educativa si se hizo una.
Lo último es la lista enlazada,
y estas tres cosas, pilas, colas y listas enlazadas,
cualquier cosa futuro lo que haces en la informática
asumirá que tiene familiaridad con estas cosas.
Ellos son tan fundamental para todo.
>> Listas enlazadas, y aquí tenemos una lista ligada simple va a ser nuestra implementación.
¿Qué significa enlace simple en comparación con doblemente enlazada? Sí.
[Estudiante] sólo apunta al siguiente puntero en lugar de los punteros,
como la que le precede y el que le sigue.
Sí, ¿y en formato de imagen, ¿qué he hecho?
Tengo dos cosas. Tengo imagen e imagen.
En formato de imagen, nuestra lista ligada simple,
inevitablemente, tenemos algún tipo de puntero a la cabeza de la lista,
y luego dentro de la lista, sólo tenemos punteros,
y tal vez esto apunta a null.
Va a ser un dibujo típico de una lista ligada sencilla.
Una lista doblemente enlazada, puede ir hacia atrás.
Si te doy un nodo en la lista, entonces necesariamente puede llegar a
cualquier otro nodo en la lista si se trata de una lista doblemente enlazada.
Pero si usted consigue el tercer nodo de la lista y se trata de una lista ligada simple,
hay manera de que nunca va a llegar a los nodos de primera y segunda.
Y hay ventajas e inconvenientes, y uno una evidente
Se le ocupan más tamaño, y hay que perder de vista que estas cosas están apuntando ahora.
Pero sólo se preocupan por enlace simple.
>> Un par de cosas que vamos a tener que implementar.
El nodo typedef struct, int i: struct nodo * siguiente; nodo.
Eso typedef debe ser quemado en sus mentes.
Quiz 1 debe ser como dar un typedef de un nodo de lista enlazada,
y usted debería ser capaz de hacer garabatos que inmediatamente abajo
sin siquiera pensar en ello.
Supongo que un par de preguntas, ¿por qué necesitamos struct aquí?
¿Por qué no podemos decir * nodo?
[Estudiante] [inaudible]
Si.
La única cosa que define un nodo como una cosa
es el propio typedef.
Pero a partir de este momento, cuando estamos como el análisis a través de esta definición de nodo estructura,
no hemos terminado nuestro typedef todavía, así que desde el typedef no ha terminado,
nodo no existe.
Pero struct nodo hace, y este nodo aquí,
esto también podría ser llamado cualquier otra cosa.
Esto podría llamarse n.
Se podría llamar nodo de la lista enlazada.
Se podría llamar cualquier cosa.
Pero este nodo de estructura tiene que ser llamado lo mismo que este nodo de estructura.
Lo que usted llama esto tiene que ser también aquí,
y de modo que también responde al segundo punto de la cuestión
razón por la cual, muchas veces, cuando usted ve las estructuras y typedefs de las estructuras,
podrás ver las estructuras anónimas donde usted acaba de ver typedef struct,
implementación de estructura, diccionario, o lo que sea.
>> ¿Por qué aquí tenemos que decir nodo?
¿Por qué no puede ser una struct anónimo?
Es casi la misma respuesta.
[Estudiante] Es necesario hacer referencia a ella en la estructura.
Sí, dentro de la estructura, es necesario hacer referencia a la propia estructura.
Si usted no da la estructura de un nombre, si es un struct anónimo, no se puede hacer referencia a ella.
Y por último, estos no deben ser todo lo sencillo algo,
y ellos le ayudarán a darse cuenta de que si estás escribiendo esto
que usted está haciendo algo mal si este tipo de cosas no tienen sentido.
Por último, pero no menos importante, ¿por qué tiene esto que ser * struct nodo?
¿Por qué no pueden simplemente ser struct nodo siguiente?
[Estudiante] Puntero a la estructura siguiente.
Eso es inevitable lo que queremos.
¿Por qué no podía ser de struct nodo siguiente?
¿Por qué tiene que ser nodo * siguiente estructura? Si.
[Estudiante] Es como un bucle infinito.
Si.
[Estudiante] Todo sería en uno.
Sí, sólo pensar en lo que haríamos tamaño o algo así.
Tamaño de una estructura es básicamente + o - algún patrón aquí o allá.
Es, básicamente, va a ser la suma de los tamaños de las cosas en la estructura.
Este derecho aquí, sin cambiar nada, el tamaño va a ser fácil.
Tamaño de nodo struct va a ser el tamaño de i + de tamaño próximo.
Tamaño de i va a ser 4. Tamaño de la que viene va a ser 4.
Tamaño de nodo struct va a ser 8.
Si no tenemos el *, pensando en sizeof,
a continuación, sizeof (i) va a ser 4.
Tamaño de nodo struct siguiente va a ser el tamaño de i + tamaño de nodo struct siguiente
+ Tamaño de i + tamaño de struct nodo siguiente.
Sería una recursión infinita de nodos.
Por ello, es así como las cosas tienen que ser.
>> Una vez más, sin duda que memorizar,
o por lo menos lo entiendo bastante que usted puede ser capaz de
razón por lo que debe ser similar.
Las cosas que vamos a querer implementar.
Si la longitud de la lista-
usted podría engañar y mantener en torno a un
longitud global o algo, pero no vamos a hacer eso.
Vamos a contar la longitud de la lista.
Hemos contiene, por lo que, básicamente, como una búsqueda,
así que tenemos una lista enlazada de enteros para ver si este entero está en la lista enlazada.
Anteponer se va a insertar en el comienzo de la lista.
Append se va a insertar al final.
Insert_sorted se va a insertar en la posición de la lista ordenada.
Tipo de Insert_sorted asume que nunca ha utilizado anteponer o anexar en malos pasos.
>> Insert_sorted cuando estás implementando insert_sorted-
digamos que tenemos nuestra lista enlazada.
Esto es lo que actualmente parece, 2, 4, 5.
Quiero insertar 3, así que siempre que la lista en sí ya está ordenado,
es fácil de encontrar en 3 pertenece.
Empiezo a 2.
De acuerdo, 3 es mayor que 2, así que quiero seguir adelante.
Oh, 4 es demasiado grande, así que sé 3 va a ir entre 2 y 4,
y tengo que arreglar los punteros y todas esas cosas.
Pero si no nos utilicen exclusivamente insert_sorted,
como vamos a decir que anteponer 6,
entonces mi lista enlazada se va a convertir esto.
Ahora no tiene sentido, así que para insert_sorted, sólo puede asumir
que la lista está ordenada, a pesar de que existen operaciones
que puede hacer que no se clasifican, y eso es todo.
Encuentre un útil insert-esas son las cosas principales que usted va a tener que poner en práctica.
>> Por ahora, tome un minuto para hacer la longitud y contiene,
y los que deben ser relativamente rápida.
Al acercarse la hora de cierre, por lo que nadie tiene nada para largo o contiene?
Van a ser casi idénticos.
[Estudiante] Longitud.
Vamos a ver, a revisión.
Bien.
Usted quiere explicar?
[Estudiante] Acabo de crear un nodo puntero e inicializarla a la primera, que es nuestra variable global,
y luego compruebo para ver si es nulo, así que no te dan una falla seg y devolver 0 si ese es el caso.
De lo contrario, recorrer, hacer el seguimiento de dentro entera
cuántas veces me he accedido al siguiente elemento de la lista
y en la operación de incremento misma también acceso a ese elemento real,
y entonces yo continuamente hacer el cheque para ver si es nulo,
y si es nulo, entonces se aborta y sólo devuelve el número de elementos que he accedido.
>> [Rob B.] ¿Alguien tiene algún comentario sobre cualquier cosa?
Esto se ve muy bien la corrección sabio.
[Estudiante] No creo que se necesita el nodo == null.
Sí, ¿y si el nodo == 0 devuelve null.
Pero si el nodo == null entonces esta-oh, hay un problema de corrección.
Era justo que estés i volver, pero no es de alcance en estos momentos.
Sólo tiene int i, por lo que = 0.
Pero si el nodo es nulo, entonces yo todavía va a ser 0,
y vamos a devolver 0, por lo que este caso es idéntico.
Otra cosa común es mantener la declaración
de nodo dentro del bucle for.
Se podría decir que-oh, no.
Vamos a mantenerlo como este.
Probablemente me pondría int i = 0 aquí,
entonces el nodo node = * primero aquí.
Y esta es probablemente la forma-deshacerse de esto ahora.
Esta es probablemente la forma en que lo hubiera escrito.
Usted podría también-verlo así.
Esta estructura de bucle aquí
debe ser casi tan natural para ti como para int i = 0
i es menor que la longitud de array i + +.
Si así es como iterar sobre una matriz, así es como recorrer un lista enlazada.
>> Esta debe ser la naturaleza segundos en algún momento.
Con esto en mente, esto va a ser casi lo mismo.
Usted va a querer para iterar sobre una lista enlazada.
Si el nodo-No tengo ni idea de cuál es el valor que se llama.
Nodo i.
Si el valor en el nodo i = return true, y eso es todo.
Tenga en cuenta que la única manera que alguna vez vuelvo falso
si es iterar sobre la lista entera vinculados y nunca devolver true,
así que eso es lo que hace.
Como nota lateral, es probable que no se llega a añadir o anteponer.
>> Última nota rápida.
Si usted ve la palabra clave static, por lo que vamos a decir static int cuenta = 0,
entonces lo que hacemos cuenta + +, básicamente se puede pensar en ella como una variable global,
a pesar de que acabo de decir no es así como vamos a implementar longitud.
Estoy haciendo esto aquí, y luego contar + +.
De cualquier manera que podamos entrar en un nodo en la lista enlazada estamos incrementando nuestra cuenta.
El punto de esto es lo que significa la palabra clave static.
Si sólo tuviera int count = 0 que sería un habitual variable global edad.
¿Qué medios estático int cuenta es que se trata de una variable global de este archivo.
Es imposible para algún otro archivo,
gusta pensar en pset 5, si usted ha comenzado.
Usted tiene tanto speller.c, y usted tiene dictionary.c,
y si lo que declara una cosa global, entonces cualquier cosa en speller.c
Se puede acceder en dictionary.c y viceversa.
Las variables globales son accesibles en cualquier archivo. C,
pero las variables estáticas sólo se puede acceder desde el propio archivo,
así que dentro de corrector ortográfico o en el interior de dictionary.c,
esto es un poco cómo iba a declarar mi variable para el tamaño de mi matriz
o el tamaño de mi número de palabras en el diccionario.
Puesto que no es necesario declarar una variable global que nadie tiene acceso,
En realidad sólo se preocupan por él para mis propios fines.
>> Lo bueno de esto es también la materia colisión nombre completo.
Si algún otro archivo intenta utilizar una variable global llamada recuento, las cosas van mal, muy mal,
por lo que esta bien mantiene las cosas seguras, y sólo se puede acceder a ella,
y nadie más puede hacerlo, y si alguien se declara una variable global llamada recuento
entonces no va a interferir con la variable estática denominada conteo.
Eso es lo que es estático. Es una variable global de archivos.
>> Las preguntas sobre cualquier cosa?
Todo listo. Bye.
[CS50.TV]