[Powered by Google Translate] [Semana 4]
[David J. Malan] [Harvard University]
[Esta es CS50.] [CS50.TV]
>> Muy bien, esto es CS50, y este es el comienzo de la semana 4,
y este es uno de los algoritmos de ordenación más lenta posible.
¿Cuál era lo que acabo de ver allí?
Eso era una especie de burbuja, para gran O (n ^ 2) + resumen,
y de hecho no somos los únicos en este mundo parece saber
qué tipo burbuja o es su tiempo de ejecución.
En efecto, se trataba de una entrevista con Eric Schmidt de Google
y el ex senador Barack Obama sólo unos pocos años atrás.
>> Ahora, el senador, que está aquí en Google,
y me gusta pensar en la presidencia como una entrevista de trabajo.
Ahora, es difícil conseguir un trabajo como presidente, y usted va a través de los rigores ahora.
También es difícil conseguir un trabajo en Google.
Tenemos preguntas, y le pedimos a nuestras preguntas candidatos,
y éste es el de Larry Schwimmer.
Ustedes piensan que estoy bromeando? Está justo aquí.
¿Cuál es la forma más eficiente para ordenar un millón de enteros de 32 bits?
[Risas]
Well-
Lo siento. >> No, no, no, no.
Creo que el ordenamiento de burbuja sería el camino equivocado.
>> Vamos, ¿quién le dijo eso?
La semana pasada recordar que tomamos un descanso de código, al menos por un día,
y comenzó a concentrarse en algunas ideas de alto nivel y resolución de problemas de manera más general
en el contexto de búsqueda y clasificación,
y hemos introducido algo que no teníamos una palmada este nombre en la semana pasada,
pero notación asintótica, el Big O, el Omega Big,
ya veces la notación grande Theta, y estos eran simplemente formas
de describir el tiempo de ejecución de algoritmos,
la cantidad de tiempo que le toma a un algoritmo para ejecutar.
>> Y usted puede recordar que usted habló sobre el tiempo de ejecución en función del tamaño
de la entrada, que generalmente llamamos n, sea cual sea el problema que sea,
donde n es el número de personas en la habitación,
el número de páginas de un libro de teléfono, y nos pusimos a escribir las cosas
como O (n ^ 2) u O (n) o O (n log n),
e incluso cuando las matemáticas no tuvo los resultados esperados con tanta perfección
y fue n ² - n / 2 o algo por el estilo
que en cambio sólo tirar algunos de los términos de orden inferior,
y la motivación no es que de verdad queremos un
especie de manera objetiva de evaluar
el desempeño de los programas o el rendimiento de los algoritmos
que al final del día no tiene nada que hacer, por ejemplo,
con la velocidad de su equipo hoy.
>> Por ejemplo, si implementa la ordenación de burbuja,
o implementar fusionar sort sort o selección en el ordenador de hoy,
un equipo de 2 GHz, y que lo ejecute,
y se necesita un cierto número de segundos, el año que viene hay un 3 GHz
o un ordenador de 4 GHz, y usted puede entonces afirmar que "Wow, mi algoritmo
Ahora es el doble de rápido ", cuando en realidad eso no es obviamente el caso.
Es sólo el hardware se ha vuelto más rápido, pero el equipo
no tiene, y lo que realmente quieren deshacerse de cosas como
múltiplos de 2 o múltiplos de 3, cuando se trata de describir
qué tan rápido o lento como un algoritmo es justo y realmente se centran
en n o algún factor del mismo,
algo de energía de los mismos como en el caso de las clases de la semana pasada.
Y recordar que, con la ayuda de la especie de mezcla
hemos sido capaces de hacerlo mucho mejor que la ordenación de burbuja y ordenamiento por selección
e incluso la inserción de clasificación.
>> Nos pusimos manos a la n log n, y otra vez,
Recordemos que log n generalmente se refiere a algo que crece
más lentamente n, por lo que n log n hasta el momento era bueno
porque era menos de ² n.
Pero para lograr n log n con una especie de mezcla
lo que fue el germen de una idea básica de que teníamos que aprovechar
que también aprovechó de nuevo en la semana 0?
¿Cómo abordamos el problema de clasificación inteligente con una especie de mezcla?
¿Cuál fue la idea clave, tal vez?
Cualquier persona en absoluto.
Bueno, vamos a dar un paso atrás.
Describir merge sort en sus propias palabras.
¿Cómo funciona?
Bueno, vamos a remar de nuevo a 0 la semana.
Bueno, sí.
[Inaudible-alumno]
Bueno, bueno, así que divide el conjunto de los números en 2 piezas.
Hemos clasificado cada una de esas piezas, y luego los fusionaron,
y hemos visto esta idea antes de tomar un problema que es tan grande
y picando para arriba en un problema que es tan grande o grande esto.
>> Recordemos el ejemplo guía telefónica.
Recordemos el algoritmo de auto-conteo de semanas atrás,
especie para fusionar fue resumido por este pseudocódigo aquí.
Cuando te dan n elementos, primero fue comprobación de validez.
Si n <2, entonces no hago nada en absoluto
porque si n <2 entonces n es 0 o 1, obviamente,
y lo que si es 0 o 1, no hay nada que ordenar.
Eso es todo.
La lista ya está trivialmente ordenado.
Pero por lo demás, si tienes dos o más elementos que adelante y dividirlos
en 2 mitades, izquierda y derecha.
Clasifique cada una de esas mitades, y luego fusionar las dos mitades ordenadas.
Pero el problema aquí es que a primera vista esto parece que estamos batea.
Esta es una definición circular en que si yo he pedido que ordenar estos n elementos
y que me estás diciendo "Está bien, está bien, vamos a ordenar los elementos n / 2 yn aquellos / 2"
entonces mi pregunta viene va a ser "bien, ¿cómo clasificar el n / 2 elementos?"
>> Pero debido a la estructura de este programa,
porque no es este el caso base, por así decirlo,
este caso especial que dice que si n es <un valor fijo como 2 vuelta inmediatamente.
No responda con esa respuesta circular mismo.
Este proceso, esta ciclicidad finalmente terminará.
Si te pregunto "Sort estos n elementos," y usted dice: "Está bien, ordenar estos n / 2"
entonces dices, "una especie bien, estos n / 4, n / 8, N/16,"
eventualmente podrás dividir por un número suficientemente grande
que tendrá sólo un elemento de la izquierda, momento en que se puede decir,
"Aquí, aquí hay un elemento ordenados simple".
A continuación, la brillantez de este algoritmo aquí es derivar del hecho
que una vez que tenga todas estas listas individualmente ordenados,
todos los cuales son de tamaño 1, que parece ser inútil,
una vez que inicie su fusión y la fusión
construir el edificio finalmente como Rob hizo en el video finalmente una lista ordenada.
>> Pero esta idea se extiende mucho más allá de la clasificación.
Existe esta idea incrustada en este programa se conoce como recursión,
por lo que la idea es un programa,
y para resolver algún problema que te llame,
o poner en el contexto de los lenguajes de programación que están en función,
y con el fin de resolver un problema, la función llama a sí mismo
una y otra vez y otra vez, pero la función
no puede llamarse a sí mismo infinitas veces.
Finalmente, tiene hasta llegar al fondo, por así decirlo,
y tienen alguna condición de base rígida que dice
en este punto, dejar de llamar a ti mismo para que todo el proceso
Por último es de hecho detener.
¿Qué significa esto en realidad, a recurse?
>> Vamos a ver si podemos hacer un ejemplo simple, trivial con, digamos,
3 personas conmigo hasta aquí en el escenario, si alguien se sienta cómodo.
1, vamos arriba, 2 y 3.
3 Si quieren venir aquí.
Si quieres estar a mi lado aquí en una línea, supongamos que el problema en cuestión
es muy trivial contar el número de personas que están aquí.
Pero, francamente, estoy cansado de todos estos ejemplos de conteo.
Esto va a tomar algún tiempo, 1, 2, y punto, punto, punto.
Esto va a tardar una eternidad.
Prefiero punt este problema en conjunto con la ayuda de cual es tu nombre?
Sara. >> Sara, está bien.
Kelly. >> Kelly y?
>> Willy. >> Willy, Sara, Kelly, y Willy.
Ahora mismo me he hecho la pregunta por alguien
número de personas que estén en esta etapa, y no tengo ni idea.
Esta es una lista muy larga, por lo que en lugar de eso voy a hacer este truco.
Voy a pedir a la persona a mi lado para hacer la mayor parte de la obra,
y una vez que se lleva a cabo haciendo la mayoría del trabajo
Voy a hacer la menor cantidad de trabajo posible y sólo tiene que añadir un
a lo que su respuesta es, así que aquí vamos.
Me han preguntado cuántas personas hay en el escenario.
¿Cuántas personas hay en el escenario a la izquierda de usted?
La izquierda de mí? >> Está bien, pero no hagas trampa.
Eso es bueno, eso es correcto, pero si queremos seguir esta lógica
vamos a suponer que usted desea de manera similar a despejar este problema a la izquierda de usted,
así que en lugar de contestar directamente adelante, sólo tiene que pasar la pelota.
Oh, cuántas personas hay a la izquierda de mí?
¿Cuántas personas hay a la izquierda?
1.
[Risas]
Bien, 0, así que lo que ha hecho ahora Willy
se ha vuelto su respuesta diciendo esta dirección 0.
Ahora, ¿qué debe hacer? >> 1.
Bien, así que usted es el 1, por lo que dicen: "Está bien, voy a añadir un
a cualquier número de Willy era, "así 1 + 0.
Usted es ahora 1 por lo que su respuesta a la derecha es ahora
1. >> Y el mío sería 2.
Bueno, por lo que está tomando la respuesta anterior de 1,
la adición de la cantidad mínima de trabajo que quiere hacer, que es +1.
Ahora tiene 2, y luego la mano que me valor?
3, es decir, lo siento, 2.
Bueno.
>> Bueno, tuvimos 0 a la izquierda.
Luego tuvimos una, y luego añadimos 2,
y ahora me estás dando el número 2,
y por lo que estoy diciendo, bueno, +1, 3.
Hay en realidad tres personas de pie junto a mí en esta etapa,
así que podría haber hecho esto, obviamente, muy lineal,
en gran medida de la manera obvia, pero ¿qué hacemos realmente?
Tomamos un problema de tamaño 3 inicialmente.
A continuación, se rompió en un problema de tamaño 2,
entonces un problema de tamaño 1 y, a continuación, finalmente, el caso base
Fue muy, oh, no hay nadie allí,
momento en el que Willy volvió efectivamente una respuesta codificada de un par de veces,
y el segundo se hizo burbujear luego hacia arriba, brotaba, burbujeaba,
y luego añadiendo en éste adicional 1
hemos implementado esta idea básica de la recursividad.
>> Ahora, en este caso, realmente no resolver un problema
cualquier forma más eficaz entonces que hemos visto hasta el momento.
Pero piensa en los algoritmos que hemos hecho en el escenario hasta el momento.
Tuvimos a 8 hojas de papel en la pizarra,
En el vídeo cuando Sean estaba buscando el número 7, y ¿qué hizo realmente?
Bueno, él no hizo ningún tipo de divide y vencerás.
Él no hizo ningún tipo de recursión.
Más bien, él acaba de hacer este algoritmo lineal.
Sin embargo, cuando se introdujo la idea de números ordenados en el escenario en vivo la semana pasada
luego tuvimos ese instinto de ir hacia el centro,
momento en el que teníamos una lista más pequeña de tamaño 4 o otra lista de tamaño 4,
y luego tuvimos el mismo problema, por lo que repite, repite, repite.
En otras palabras, recursed.
Muchas gracias a nuestros 3 voluntarios aquí para demostrar la recursividad con nosotros.
>> Vamos a ver si podemos hacer esto ahora concretar un poco más,
la solución de un problema que una vez más podemos hacer con bastante facilidad,
pero vamos a utilizar como punto de partida para la aplicación de esta idea básica.
Si desea calcular la suma de un montón de números,
por ejemplo, si se pasa en el número 3,
Quiero darle el valor de sigma 3,
por lo que la suma de 3 + 2 + 1 + 0.
Quiero volver a la respuesta 6,
así que vamos a implementar esta función sigma, esta función suma
que, de nuevo, toma en entrada y, a continuación devuelve la suma
de ese número todo el camino hacia abajo a 0.
Podríamos hacer esto bastante simple, ¿no?
Podemos hacer esto con algún tipo de estructura de bucle,
así que voy a seguir adelante y que esto empiece.
>> Incluir stdio.h.
Déjame entrar en principal para trabajar aquí.
Vamos a guardar esto como sigma.c.
Entonces me voy a ir de aquí, y voy a declarar un int n,
y yo voy a hacer lo siguiente mientras el usuario no cooperar.
Mientras el usuario no me ha dado un número positivo
déjame ir delante y le pedirá que para n = getInt,
y déjame darles algunas instrucciones en cuanto a qué hacer,
así printf ("entero positivo por favor").
Sólo es algo relativamente sencillo como éste, así que para cuando llegamos a la línea 14
ahora tenemos un número entero positivo, presumiblemente en el n.
>> Ahora vamos a hacer algo con él.
Déjame ir por delante y calcular la suma, por lo que int suma = sigma (n).
Sigma es sólo la suma, así que estoy escribiendo en la forma más elegante.
Vamos a llamarlo sigma allí.
Esa es la suma, y ​​ahora me voy a imprimir el resultado,
printf ("La suma es% d \ n", suma).
Y luego voy a devolver 0 para una buena medida.
Hemos hecho todo lo que este programa requiere excepto la parte interesante,
que es para aplicar en la práctica la función de sigma.
>> Déjame aquí abajo a la parte inferior, y déjame declarar función sigma.
Tiene que tomar una variable es de tipo entero,
y qué tipo de datos es lo que quiero volver presumiblemente de sigma?
Int, porque quiero que mis expectativas en la línea 15.
En aquí déjame seguir adelante y poner en práctica este
de una manera bastante sencilla.
>> Vamos a seguir adelante y decir: int suma = 0,
y ahora me voy a ir a tomar un poco de bucle aquí
que va a decir algo como esto,
for (int i = 0; I <= número, i + +) suma + = i.
Y luego me voy a volver suma.
Que podría haber implementado este en cualquier número de maneras.
Podría haber usado un bucle while.
Podría haber omitido usando la variable suma si realmente quería,
pero en fin, solo tenemos una función que si no lo hacía bobo declara suma es 0.
Entonces se repite desde 0 a arriba a través del número,
y en cada iteración se añade que el valor actual de suma y luego devuelve suma.
>> Ahora, hay una ligera optimización de aquí.
Esto es probablemente un paso perdido, pero que así sea. Eso está bien por ahora.
Estamos por lo menos ser exhaustivo y va todo el camino de 0 en adelante.
No es muy duro y directo bonito,
pero resulta que con la función sigma tenemos la misma oportunidad
como lo hicimos aquí en el escenario.
En el escenario que acabamos de contar cuántas personas estaban a mi lado,
pero en cambio si queremos contar el número 3 + 2 + 1
hacia abajo a 0 pudimos similar punt a una función
que en lugar describiremos como recursivo.
Aquí vamos a hacer un juicio rápido comprobar y asegurarse de que no me bobo.
>> Sé que hay al menos una cosa en este programa que me hizo mal.
Cuando llegué a entrar voy a conseguir cualquier tipo de gritarme?
¿Qué voy a gritar en esto?
Sí, se me olvidó el prototipo, así que estoy usando una función llamada sigma en la línea 15,
pero no se declaró hasta la línea 22, así que mejor manera proactiva subir aquí
y declarar un prototipo, y voy a decir sigma int (int numero), y eso es todo.
Se implementa en la parte inferior.
>> U otra manera de que pudiera resolver esto,
Podía mover la función hasta allí, lo cual no es malo,
pero por lo menos cuando los programas comienzan a hacer larga, francamente,
Creo que hay algo de valor en tener siempre principal en la parte superior
para que en el lector puede abrir el archivo y ver inmediatamente
lo que está haciendo el programa sin tener que buscar a través de ella
buscando que la función principal.
Vamos a ir a mi ventana de terminal aquí, trate de hacer sigma sigma hacer,
y metí la pata aquí también.
Declaración implícita de la función getInt significa que me haya olvidado de hacer lo otro?
[Inaudible-alumno]
Bueno, por lo que al parecer un error muy común, así que vamos a poner esto aquí,
cs50.h, y ahora vamos a volver a mi ventana de terminal.
>> Voy a borrar la pantalla, y voy a hacer volver a ejecutar sigma.
Parece que se ha compilado. Permítanme ahora se ejecutan sigma.
Voy a escribir el número 3, y me dieron 6, así que no es un cheque riguroso,
pero al menos parece estar funcionando a primera vista, pero ahora vamos a destrozar,
y vamos a aprovechar realmente la idea de la repetición, de nuevo,
en un contexto muy simple, así que dentro de unas semanas
cuando empezamos a explorar más elegantes estructuras de datos de arrays
tenemos otra herramienta en la caja de herramientas con las que
manipular las estructuras de datos, como veremos.
Este es el enfoque iterativo, el enfoque basado en bucle.
>> Permítanme ahora hacer esta vez.
Permítanme decir que en lugar de la suma del número de
abajo a 0 es realmente la misma cosa que
número + sigma (número - 1).
En otras palabras, al igual que en el escenario me pateó a cada una de las personas junto a mí,
y ellos a su vez mantiene patear hasta que finalmente tocó fondo en Willy,
quien tuvo que regresar una respuesta codificada como 0.
Aquí ahora estamos igualmente batea para sigma
la misma función que fue llamado originalmente, pero aquí la idea clave
es que no estamos llamando sigma idéntica.
No estamos de paso en el n.
Estamos pasando claramente en número - 1,
por lo que un problema un poco más pequeño, ligeramente más pequeño problema.
>> Desafortunadamente, esto no es del todo una solución, sin embargo, y antes de fijar
lo que podría saltar tan evidente en algunos de ustedes
déjame seguir adelante y volver a ejecutar hacer.
Parece que compile bien.
Permítanme volver a ejecutar sigma con 6.
¡Vaya, déjame volver a ejecutar sigma con 6.
Hemos visto esto antes, aunque sea accidentalmente tiempo pasado también.
¿Por qué me sale este error de segmentación críptico? Si.
[Inaudible-alumno]
No hay caso base, y más específicamente, lo que probablemente sucedió?
Este es un síntoma de lo que el comportamiento?
Digamos que un poco más fuerte.
[Inaudible-alumno]
Es un bucle infinito eficazmente, y el problema con los bucles infinitos
cuando implican recursión en este caso, una función que se hace llamar,
lo que ocurre cada vez que se llama a una función?
Bueno, piense en la forma en que expuso la memoria en una computadora.
Hemos dicho que hay esta cantidad de memoria llamado la pila que está en el fondo,
y cada vez que se llama a una función de memoria un poco más se puso
en esta pila de llamada que contiene las variables locales de dicha función o parámetros,
por lo que si sigma sigma sigma Las llamadas llama sigma
llama sigma donde termina esta historia?
>> Bueno, con el tiempo los excesos de la cantidad total
de memoria que tiene disponible en su ordenador.
Usted invadir el segmento que se supone que debes permanecer en el interior,
y se obtiene este error de segmentación, el núcleo de dumping,
y qué core dumped significa es que ahora tengo un archivo llamado núcleo
que es un archivo que contiene ceros y unos
que en realidad en el futuro será útil para el diagnóstico.
Si no te resulta obvio que su error es
en realidad se puede hacer un poco de análisis forense, por así decirlo,
en el archivo volcado de memoria, que, de nuevo, es sólo un montón de ceros y unos
que en esencia representa el estado de su programa en la memoria
el momento en que cayó de esta manera.
>> La solución aquí es que no podemos volver a ciegas sigma,
el número sigma + de un problema un poco más pequeño.
Tenemos que tener algún tipo de caso base aquí,
y lo que el caso base probablemente ser?
[Inaudible-alumno]
Está bien, siempre y cuando el número es positivo que en realidad debería devolver esto,
o dicho de otra manera, si el número es, por ejemplo, <= a 0
Sabes qué, voy a seguir adelante y devolver 0,
al igual que Willy lo hizo, y otra cosa, yo voy a seguir adelante
y devolver este, por lo que no es mucho más corto
que la versión iterativa que fustigó primero usando un bucle for,
notar que hay este tipo de elegancia a la misma.
En lugar de devolver un número y realizar toda esta matemática
y la adición de las cosas con las variables locales
vez que estés diciendo: "Bueno, si esto es un problema fácil de super,
al igual que el número es <0, déjame inmediatamente devolverá 0. "
>> No vamos a molestar apoyo números negativos,
así que voy a codificar el valor de 0.
Pero por lo demás, para poner en práctica esta idea de sumar
todos estos números juntos que efectivamente puede tomar un bocado pequeño
para salir del problema, al igual que lo hicimos aquí en el escenario,
entonces batea el resto del problema a la siguiente persona,
pero en este caso la siguiente persona es uno mismo.
Se trata de una función con el mismo nombre.
Sólo tienes que pasar un problema cada vez más pequeños y más pequeños cada vez,
ya pesar de que no tienen las cosas muy formalizados en el código aquí
esto es exactamente lo que estaba pasando en la semana 0 con la guía telefónica.
Esto es exactamente lo que estaba sucediendo en las últimas semanas con Sean
y con nuestras demostraciones de la búsqueda de números.
Se trata de tomar un problema y dividiéndolo una y otra vez.
>> En otras palabras, hay una manera de traducir ahora
esta construcción del mundo real, esta construcción de alto nivel
de dividir y conquistar y hacer algo una y otra vez
en el código, así que esto es algo que vamos a ver una vez más con el tiempo.
Ahora, en un aparte, si eres nuevo en la recursividad al menos debe entender ahora
por qué esto es divertido.
Voy a ir a google.com,
y yo voy a buscar algunos consejos y trucos sobre la recursividad, introduzca.
Dile a la persona a tu lado si no estuvieran riendo ahora.
¿Te refieres a la recursividad?
Quizás quiso decir-ah, ahí vamos.
Bien, ahora que está el resto de todo el mundo.
Un poco huevo de Pascua incrustado en algún lugar en Google.
Como acotación al margen, uno de los enlaces que ponemos en la página web del curso
de hoy es precisamente esta red de varios algoritmos de ordenación,
algunas de las cuales vimos la semana pasada, pero lo bueno de esta visualización
a medida que tratan de envolver su mente alrededor de varias cosas relacionadas con algoritmos
Sabía que puede muy fácilmente ahora comenzar con diferentes tipos de entradas.
Las entradas de todos invertida, sobre todo las entradas ordenadas, las entradas al azar y así sucesivamente.
Al intentar, una vez más, distinguir estas cosas en tu mente
darse cuenta de que esta dirección URL en la página web de la asignatura en la página de Conferencias
podría ayudarle a razonar a través de algunos de ellos.
>> Hoy finalmente podemos resolver este problema desde hace un tiempo,
que era que esta función de intercambio no funcionó,
y cuál fue el problema fundamental con este canje función,
cuyo objetivo fue, de nuevo, para intercambiar un valor aquí y aquí
de tal manera que esto sucede?
Esto en realidad no funciona. ¿Por qué?
Si.
[Inaudible-alumno]
Exactamente, la explicación de este bugginess
simplemente porque cuando se llama a funciones en C
y esas funciones tomar argumentos, como ayb aquí,
está de paso en las copias de cualquier valor que estamos ofreciendo a esa función.
Usted no está proporcionando los valores originales ellos mismos,
así que vimos esto en el contexto de buggyc,
buggy3.c, que parecía un poco algo como esto.
>> Recordemos que teníamos x e y inicializa a 1 y 2, respectivamente.
A continuación, imprime lo que eran.
Entonces me dijo que yo los estaba llamando intercambio swap de x, y.
Pero el problema era que el intercambio de trabajo,
pero sólo en el ámbito de aplicación de la propia permuta funcionar.
Tan pronto como llegamos a la línea 40 los valores intercambiados
fueron desechados, y por lo tanto nada
en la función original fue cambiado realmente en absoluto,
entonces si le parece entonces que el aspecto que tiene en términos de nuestra memoria
si esta parte izquierda de la placa representa-
y voy a hacer mi mejor esfuerzo para que todos la vean esto: si esta parte izquierda de la tabla
representa, por ejemplo, la memoria RAM, y la pila se va a crecer en esta forma,
y llamamos a una función como principal y principal tiene 2 variables locales, x e y,
vamos a describir a aquellos que x aquí, y vamos a describirlos como y aquí,
y vamos a poner en los valores 1 y 2, por lo que esta aquí es principal,
y cuando se llama a la función principal de intercambio del sistema operativo
da la función de intercambio en su propia franja de memoria en la pila,
su propio marco en la pila, por así decirlo.
También asigna 32 bits para estos enteros.
Le pasa a llamarlos a y b, pero eso es totalmente arbitraria.
Podría haber llamado lo que quiera, pero lo que sucede cuando principal
intercambio de llamadas es que toma este 1, pone una copia allí, pone una copia allí.
>> Hay una otra variable local en swap, sin embargo, llama qué? Tmp. >>
Tmp, así que me doy otros 32 bits de aquí,
¿y qué hago en esta función?
Dije int tmp recibe una, por lo que tiene 1, así que lo hice la última vez que jugó con este ejemplo.
A continuación, se pone a b, entonces b es 2, por lo que ahora esto se convierte en 2,
y ahora llega b temp, temp así es 1,
por lo que ahora se convierte en este b.
Eso es genial. Funcionó.
Pero tan pronto como la función devuelve
de intercambio de memoria de forma eficaz desaparece para que pueda ser reutilizado
por alguna otra función en el futuro, y principal es obviamente completamente inalterado.
Necesitamos una manera de resolver este problema fundamental,
y hoy por fin voy a tener una manera de hacer esto mediante el cual
podemos introducir algo que se llama un puntero.
Resulta que podemos resolver este problema
no pasando en copias de x e y
pero no por lo que pasa en, ¿crees que, a la función de intercambio?
Sí, ¿qué pasa con la dirección?
Realmente no hemos hablado acerca de las direcciones en mucho detalle,
pero si esto pizarra representa la memoria de mi computadora
sin duda podríamos empezar a numerar los bytes de RAM en mi
y decir que este es el byte # 1, este es el byte # 2, # 3 byte,
byte # 4, # byte ... 2 millones de dólares si tengo 2 GB de RAM,
por lo que sin duda podría llegar a algún esquema de numeración arbitrario
para todos los bytes individuales en la memoria de mi ordenador.
>> ¿Qué pasa si en lugar cuando llamo intercambio
en lugar de pasar copias de x e y
¿por qué no en lugar de pasar la dirección de x aquí,
la dirección de y aquí, esencialmente la dirección postal
de x e y porque luego de intercambio, si está informado
de la dirección en la memoria de x e y,
luego de intercambio, si lo entrenó un poco,
que potencialmente podría conducir a esa dirección, por así decirlo,
x, y cambiar el número allí, luego en coche a la dirección de y,
cambiar el número allí, aunque en realidad no obtener copias de él mismo esos valores,
así que, aunque ya hablamos de esto como memoria principal
y este swap como la memoria de los poderosos y la parte peligrosa de C
es que cualquier función puede tocar cualquier parte de la memoria del ordenador,
y esto es de gran alcance en la que se pueden hacer cosas muy elegantes con programas de computadora en C.
Esto es peligroso porque también se puede meter la pata muy fácilmente.
De hecho, una de las formas más comunes para los programas de estos días para ser explotados
todavía no es para un programador para realizar
que él o ella está permitiendo un dato
para ser escrita en una ubicación de memoria que no se pretendía.
>> Por ejemplo, él o ella declara una matriz de tamaño 10
pero, accidentalmente, trata de poner 11 bytes en la matriz de la memoria,
y empiezas a tocar partes de la memoria que ya no son válidos.
Sólo para este contexto, algunos de ustedes sabrán que
software a menudo le pide los números de serie o claves de registro,
Photoshop y Word y programas como este.
Existen grietas, como algunos de ustedes saben, en línea donde usted puede ejecutar un pequeño programa,
y listo, no pedir más de un número de serie.
¿Cómo es que funciona?
En muchos casos, estas cosas son simplemente encontrar en los ordenadores
segmentos de texto en ceros reales de la computadora y seres
¿dónde está esa función en la que se solicita el número de serie,
y sobrescribir ese espacio, o mientras el programa se está ejecutando
usted puede averiguar donde la clave se almacena
usando algo llamado un depurador, y se puede agrietar software de esa manera.
Esto no quiere decir que este es nuestro objetivo para el próximo par de días,
pero tiene muy reales ramificaciones.
Que uno le sucede a implicar el robo de software,
pero también hay compromiso de las máquinas enteras.
>> De hecho, cuando estos sitios web día son explotados
y comprometida y los datos se filtraron y contraseñas robadas se
muy a menudo se relaciona con la mala gestión de la memoria,
o, en el caso de bases de datos, falta de anticipación
entrada contradicción, por lo que más en que en las próximas semanas,
pero por ahora sólo un adelanto de la clase de daño que se puede hacer
por no bastante entender cómo funcionan las cosas debajo de la capucha.
Vamos a ir sobre la comprensión de por qué esto está roto
con una herramienta que se hará más y más útil
ya que nuestros programas se vuelven más complejos.
Hasta ahora cuando se ha tenido un error en su programa
¿cómo ha ido depurando sobre él?
¿Cuáles han sido tus técnicas hasta el momento, ya sea impartido por el TF
o simplemente autodidacta?
[Estudiante] printf.
Printf, así printf probablemente ha sido su amigo en que si usted quiere ver
lo que está sucediendo dentro de su programa de
usted acaba de poner printf aquí, printf aquí, printf aquí.
A continuación, ejecutarlo, y te dan un montón de cosas en la pantalla
que se puede utilizar para deducir entonces lo que realmente está pasando mal en su programa.
>> Printf tiende a ser algo muy poderoso,
pero es un proceso muy manual.
Tienes que poner un printf aquí, un printf aquí,
y si lo pones dentro de un bucle podría obtener 100 líneas
de salida que usted entonces tiene que tamizar a través.
No es un mecanismo muy fácil de usar o interactivos para los programas de depuración,
pero por suerte existe alternativas.
Hay un programa, por ejemplo, llama GDB, el depurador de GNU,
que es un arcano muy poco en cómo lo usa.
Es un poco complejo, pero, francamente,
esta es una de esas cosas que si usted pone en esta semana y la próxima
la hora extra a entender algo como GDB
que le ahorrará probablemente decenas de horas en el largo plazo,
Así que con eso, te voy a dar un adelanto de cómo funciona esto.
>> Estoy en mi ventana de terminal.
Déjenme seguir adelante y compilar este programa, buggy3.
Ya está actualizado.
Déjame correr tal como lo hicimos hace un tiempo, y de hecho, está rota.
Pero ¿por qué es esto? Tal vez lo arruiné la función de intercambio.
Tal vez es a y b. No estoy muy a moverse correctamente.
Déjame ir adelante y hacerlo.
En lugar de simplemente correr buggy3 déjame en lugar de ejecutar este programa de GDB,
y yo lo voy a decir a ejecutar buggy3,
y voy a incluir un parámetro de línea de comandos,-tui,
y vamos a poner esto en futuros problemas de especificación para recordar.
Y ahora esta interfaz en blanco y negro que apareció, de nuevo,
Es un poco abrumador al principio, porque hay toda esta
información sobre la garantía aquí, pero al menos hay algo familiar.
En la parte superior de la ventana es mi código actual,
y si me desplazo hasta aquí permítanme desplazarse a la parte superior de mi archivo,
y, de hecho, hay buggy3.c y observe en la parte inferior de esta ventana
Tengo este mensaje GDB.
>> Este no es el mismo que mi normal del sistema John Harvard.
Este es un mensaje que va a permitir que controle GDB.
GDB es un depurador.
Un depurador es un programa que le permite caminar a través de
ejecución de su programa de línea a línea por línea,
en el camino haciendo lo que quieras con el programa,
incluso llamar a funciones, o en busca, sobre todo,
en valores de las variables de diversos.
Vamos a seguir adelante y hacer esto.
Voy a seguir adelante y escribir en carrera en el símbolo del BGF,
por lo notará en la parte inferior izquierda de la pantalla que he escrito correr,
y he pulsa enter, y qué hizo eso?
Es, literalmente, corriendo mi programa, pero que en realidad no veo mucho ir de aquí
porque yo no lo he dicho el depurador
para hacer una pausa en un momento particular en el tiempo.
Simplemente escribiendo run ejecuta el programa.
Yo en realidad no veo nada. No lo puedo manipular.
>> En su lugar vamos a hacer esto.
En este mensaje GDB déjame en vez escriba break, entrar.
Eso no es lo que quise escribir.
En lugar de eso escribir ruptura principal.
En otras palabras, quiero hablar de algo que se llama un punto de interrupción,
que se nombra conveniente porque va a romper o hacer una pausa
ejecución de su programa en ese lugar en particular.
Principal es el nombre de mi función.
Tenga en cuenta que GDB es muy inteligente.
Se descubrió que la principal pasa a comenzar aproximadamente en la línea 18
de buggy3.c y observe aquí, en la parte superior izquierda
+ b es justo al lado de la línea 18.
Eso me recuerda que he puesto un punto de interrupción en la línea 18.
Esta vez, cuando yo escriba run, me voy a correr mi programa
hasta que llegue a ese punto de ruptura,
por lo que el programa hará una pausa para mí en la línea 18.
Aquí vamos, corre.
Nada parece haber pasado, pero dejó aviso en la parte inferior
programa de inicio, buggy3, 1 en punto de interrupción en la línea principal buggy3.c 18.
¿Qué puedo hacer ahora?
>> Note que puede empezar a escribir cosas como la impresión,
No printf, print x, y eso sí que es raro.
Los $ 1 es sólo una curiosidad, como veremos
cada vez que imprima algo que se obtiene un nuevo valor $.
Eso es lo que se puede hacer referencia a los valores anteriores por si acaso,
pero por ahora lo que me está diciendo impresión es que el valor de x en este punto de la historia
es aparentemente 134514032.
¿Qué? ¿De dónde vino que incluso viene?
[Inaudible-alumno]
De hecho, esto es lo que vamos a llamar a un valor basura, y nosotros no hemos hablado de esto, sin embargo,
pero la razón por la que inicializar las variables
obviamente para que tengan algún valor que desea que tengan.
Pero el problema es recordar que usted puede declarar variables
como lo hice hace un momento en mi ejemplo sigma
sin llegar a dar un valor.
Recordemos lo que hice aquí en sigma.
Declaré n, pero ¿qué valor tenía lo doy?
Ninguna, porque sabía que en las próximas líneas
GetInt se ocuparía del problema de poner un valor dentro de n.
>> Pero en este punto de la historia de la línea 11
y la línea 12 y la línea 13 y la línea 14
a lo largo de esas líneas de varios cuál es el valor de n?
En C simplemente no lo sé.
Por lo general es un valor basura, un número completamente al azar
que sobra esencialmente de alguna función anterior
después de haber sido ejecutado, así como su programa se ejecuta
Recordemos que la función tiene función, la función, la función.
Todos estos marcos de conseguir poner en la memoria y luego los devuelven las funciones,
y al igual que sugerí con la goma de borrar su memoria es eventualmente reutilizados.
Bueno, lo que pasa es que esta variable x en este programa
parece haber contenido algún valor como basura 134514032
de alguna función anterior, no uno que yo escribí.
Podría ser algo que viene efectivamente con el sistema operativo,
alguna función debajo de la capucha.
>> Está bien, está bien, pero ahora vamos a pasar a la siguiente línea.
Si escribo "siguiente" en mi GDB rápido y llegué a entrar,
cuenta de que el selector se desplaza hasta la línea 19,
sino la consecuencia lógica es que la línea 18
ha terminado de ejecutarse, por lo que si vuelvo a escribir "print x"
Ahora deberá ver 1, y de hecho, así es.
Una vez más, las cosas $ es una forma de GDB le recuerda
lo que la historia de las impresiones son que usted ha hecho.
Ahora voy a seguir adelante e imprimir y, de hecho, y es un valor loco también,
pero no es gran cosa ya que en la línea 19 estamos a punto de ceder
el valor 2, así que voy a escribir "Siguiente" de nuevo.
Y ahora estamos en la línea printf.
Permítanme hacer x impresión.
Déjame hacer y de impresión. Francamente, estoy un poco cansado de la impresión de este.
Déjame en vez escribir "x pantalla" y "y la pantalla",
y ahora cada vez que escriba un comando en el futuro
Voy a recordar lo que es x e y, lo que es x e y, lo que es x e y.
>> También puedo, en un aparte, escriba "locales de información."
Info es una orden especial.
Los locales significa que me muestra las variables locales.
Sólo en caso de olvido o se trata de una función loco y complicado
que yo o alguien más escribió lugareños información le dirá
¿cuáles son las variables locales dentro de esta función local
que es posible que se preocupan por si quieres curiosear.
Ahora, printf está a punto de ejecutar, así que voy a seguir adelante y sólo tienes que escribir "siguiente".
Porque estamos en este entorno no estamos realmente viendo
ejecutar hasta aquí, pero note que está haciendo un poco destrozado aquí.
Pero note que está anulando la pantalla hay,
así que no es un programa perfecto aquí, pero eso está bien, porque siempre puedo hurgar
mediante impresión si quiero.
>> Déjame escribir al lado de nuevo, y ahora viene la parte interesante.
En este punto de la historia y es 2, y x es 1,
como se sugiere aquí, y de nuevo,
la razón de esto es automáticamente mostrando ahora es porque he utilizado el comando
display x e y visualización, por lo que el momento de tipo I siguiente
en teoría x e y deben convertirse intercambian.
Ahora, ya sabemos que no va a ser el caso,
pero ya veremos dentro de un momento cómo podemos profundizar más para entender por qué eso es cierto.
A continuación, y por desgracia, y es todavía 2 yx sigue siendo 1, y puedo confirmar lo mismo.
Imprimir x, imprimir y.
De hecho, ningún intercambio que realmente ha sucedido, así que vamos a empezar esta vez.
Claramente intercambio está roto.
En lugar de eso escribe "Ejecutar" de nuevo.
Permítanme decir que sí, quiero que reiniciar desde el principio, entrar.
>> Ahora estoy de vuelta para arriba en la línea 18.
Ahora note x e y son valores de basura de nuevo.
Siguiente, siguiente, siguiente, siguiente.
Si me aburro yo también puedo simplemente escriba n para el próximo.
Se puede abreviar con la secuencia más corta posible de caracteres.
Intercambiar está roto.
Vamos a bucear, así que en vez de teclear siguiente,
ahora voy a escribir lo que paso Estoy caminando dentro de esta función
para que yo pueda caminar a través de él, así que me golpeó paso y luego entra.
Tenga en cuenta que los saltos que destacan más abajo en mi programa a la línea 36.
Ahora, ¿cuáles son las variables locales?
Información de los locales.
No hay nada todavía porque no hemos llegado a esa línea,
así que vamos a seguir adelante y decir "siguiente".
Ahora parece que tenemos tmp tmp impresión.
Valor basura, ¿no? Creo que sí.
¿Qué tal una impresión, impresión b, 1 y 2?
En un momento, en cuanto me escriba de nuevo al lado
tmp va a tener un valor de 1, con suerte,
tmp porque va a ser asignado el valor de a.
>> Ahora vamos a hacer imprimir a, b, impresión,
pero ahora imprimir tmp, y es de hecho 1.
Déjame hacer a continuación. Déjame hacer a continuación.
He terminado la función de intercambio.
Estoy aún dentro de la misma en la línea 40, así que me imprima una,
print b, y no me importa lo que tmp es.
Parece intercambio es correcto cuando se trata de intercambio de a y b.
Pero si ahora introducido a continuación, salto de nuevo a la línea 25,
y por supuesto, si escribo en x e y de impresión
siguen siendo sin cambios, por lo que no han solucionado el problema.
Sin embargo, el diagnóstico ahora tal vez con este programa GDB
hemos conseguido al menos un paso más cerca de entender
lo que va mal sin necesidad de basura nuestro código por poner un printf aquí,
printf aquí, printf aquí y luego se ejecuta una y otra vez
tratando de averiguar lo que va mal.
>> Voy a seguir adelante y dejar fuera de este conjunto con dejar de fumar.
Esto va a decir a continuación, "Salir de todos modos?" Sí.
Ahora estoy de vuelta en mi sistema normal, y he terminado con GDB.
Como acotación al margen, no es necesario utilizar esta bandera-tui.
De hecho, si lo omite obtener esencialmente la mitad inferior de la pantalla.
Si a continuación, escriba ruptura principal y ejecute
Todavía puedo ejecutar mi programa, pero lo que hará es más textual
sólo me muestra la línea actual a la vez.
El tui-, la interfaz de usuario textual,
sólo le muestra más del programa a la vez, que es probablemente un poco conceptualmente más fácil.
Pero, en realidad, sólo se puede hacer siguiente, siguiente, siguiente,
y voy a ver una línea a la vez, y si realmente quieres ver lo que está pasando
Me puede escribir la lista y ver un montón de líneas vecinas.
>> Hay un video que le hemos pedido que usted mira para boletines de problemas 3
en la que Nate se tratan algunas de las complejidades de GDB,
y esta es una de esas cosas, de verdad, donde un porcentaje no trivial de que
nunca tocará GDB, y eso será algo malo
porque, literalmente, usted terminará gastando más tiempo a finales de este semestre
persiguiendo a los bichos entonces usted tendría si usted pone en esa media hora / hora
esta semana y el aprendizaje junto a sentirse cómodo con GDB.
Printf era su amigo.
GDB ahora debe ser su amigo.
>> ¿Tiene preguntas sobre GDB?
Y aquí está una lista rápida de algunos de los comandos más poderosos y útiles.
Si. >> ¿Puede imprimir una cadena?
¿Puede imprimir una cadena? Por supuesto.
No tiene por qué ser sólo números enteros.
Si una variable s es una cadena que sólo tiene que escribir s de impresión.
Se le mostrará lo que es variable de cadena.
[Inaudible-alumno]
Se le dará la dirección y la propia cadena.
Se mostrará a los dos.
Y una última cosa, sólo porque se trata de un buen saber demasiado.
Backtrace y el marco, déjame sumergirse en esta última vez,
mismo programa con GDB.
Déjenme seguir adelante y ejecutar la versión de la interfaz de usuario textual,
romper principal.
Déjenme seguir adelante y correr de nuevo. Aquí estoy.
Ahora voy a ir a siguiente, siguiente, siguiente, siguiente, siguiente, paso, entrar.
>> Y ahora supongo que ahora estoy en intercambio deliberadamente, pero yo soy como "Maldita sea, ¿cuál era el valor de x?"
No puedo hacer x más.
No puedo hacerlo y porque no están en su alcance.
No están en su contexto, pero no hay problema.
Puedo escribir backtrace.
Esto me muestra todas las funciones que se han realizado hasta este punto en el tiempo.
Observe que la una en la parte inferior, la principal, se alinea con principal
estar en el fondo de nuestra imagen aquí.
El hecho de que está por encima de canje que se alinee con el canje de estar por encima de ella en la memoria aquí,
y si quiero volver a principal temporalmente lo que puedo decir "marco".
¿Qué número? Principal es el cuadro n º 1.
Voy a seguir adelante y decir "cuadro 1".
>> Ahora estoy de vuelta en main, y puedo imprimir x, y puedo imprimir y,
pero no puedo imprimir a o b.
Pero puedo si digo: "Bueno, espere un minuto. ¿Dónde estaba el canje?"
Déjenme seguir adelante y decir "0 marco".
Ahora estoy de vuelta donde quiero estar, y en un aparte,
hay otros comandos también, como si realmente estás consiguiendo mecanografiar aburrido siguiente, siguiente, siguiente, siguiente,
por lo general, se puede decir cosas como "el próximo 10", y que pasará por los siguientes 10 líneas.
También puede escribir "continuar" cuando realmente harto de caminar a través de ella.
Continuar se ejecutará el programa sin interrupción hasta que llega a otro punto de interrupción,
ya sea en un bucle o más abajo en su programa.
>> En este caso se continuó hasta el final, y el programa sale normalmente.
Esta es una forma elegante, proceso inferior.
Sólo su programa terminó normalmente.
Más sobre esto en el video y en la depuración de las sesiones por venir.
Eso era mucho.
Vamos a tomar nuestro hijo de 5 minutos de descanso aquí, y vamos a volver con las estructuras y los archivos.
>> Si ha buceado en conjunto de procesadores de esta semana ya
usted sabrá que utilizamos en el código de distribución,
la fuente de código que le proporcionamos a usted como un punto de partida, algunas técnicas nuevas.
En particular, hemos introducido esta nueva palabra clave se llama estructura, la estructura,
de manera que podamos crear variables personalizadas de todo tipo.
También introdujo la noción de archivo del archivo de entrada de E / S y de salida,
y esto es lo que podemos guardar el estado
de su tablero Scramble en un archivo en disco
para que los compañeros docentes y comprendo
lo que está sucediendo dentro de su programa sin tener que jugar de forma manual
decenas de juegos de pelea.
Podemos hacer esto más automatizadamente.
>> Esta idea de una estructura resuelve un problema bastante convincente.
Supongamos que queremos implementar algún programa
que de alguna manera hace un seguimiento de la información sobre los estudiantes,
y los estudiantes podrían tener, por ejemplo, una identificación, un nombre
y una casa en un lugar como Harvard, así que estos son tres piezas de información
queremos mantener a su alrededor, así que déjame seguir adelante y empezar a escribir un pequeño programa aquí,
incluir stdio.h.
Déjame hacer incluir cs50.h.
Y luego empezar mi función principal.
No me molestaré con los argumentos de línea de comandos,
y aquí quiero tener un estudiante, así que voy a decir
un estudiante tiene un nombre, así que voy a decir "nombre de cadena."
Entonces yo voy a decir un estudiante también tiene un ID, id int así,
y un estudiante tiene una casa, así que también voy a decir "casa de cuerda".
Entonces voy a pedir este un poco más limpia de esta manera.
Bien, ahora tengo 3 variables con las que representan a un estudiante, por lo que "un estudiante".
>> Y ahora quiero llenar estos valores, así que voy a seguir adelante y decir algo como
"Id = 123".
Nombre se va a poner a David.
Digamos que la casa se va a poner Mather,
y luego me voy a hacer algo arbitrariamente como printf ("% s,
cuyo identificador es% d, vive en% s.
Y ahora, ¿qué es lo que quiero conectar aquí, una después de la otra?
Nombre, id, casa, devuelve 0.
Bueno, a menos que metí la pata en alguna parte aquí
Creo que tenemos un programa muy bueno que almacena un estudiante.
Por supuesto, esto no es tan interesante. ¿Y si quiero tener 2 estudiantes?
Eso no es gran cosa. Puedo soportar 2 personas.
Déjenme seguir adelante y poner de relieve este y bajar aquí,
y lo que puedo decir "id = 456" para alguien como Rob que vive en Kirkland.
>> Bueno, espera, pero no puedo llamar a estos lo mismo,
y parece que voy a tener que copiar esto,
así que permítanme decir que estos serán variables de David,
y me dejas algunas copias de estos para Rob.
Llamaremos a estos Rob, pero esto no va a funcionar ahora
porque he-espera, vamos a cambiar a id1, nombre1 y house1.
Rob será 2, 2.
Tengo que cambiar esto aquí, aquí, aquí, aquí, aquí, aquí.
Espera, ¿qué pasa con Tommy? Vamos a hacer esto de nuevo.
Obviamente, si usted todavía piensa que esto es una buena manera de hacer esto, no lo es,
así copiar / pegar mal.
Pero hemos resuelto este hace una semana.
>> ¿Cuál era nuestra solución cuando queríamos tener varias instancias del mismo tipo de datos?
[Los estudiantes] Matriz.
Una matriz, así que vamos a tratar de limpiar esto.
Quiero dejar algo de espacio para mí mismo en la parte superior, y déjame hacer esto en lugar aquí.
Llamaremos a estas personas, y en su lugar voy a decir "ids int"
y yo voy a apoyar a 3 de nosotros por ahora.
Voy a decir "nombres de cadena," y voy a apoyar a 3 de nosotros,
y luego voy a decir "casas de cuerda", y yo voy a apoyar a tres de nosotros.
Ahora aquí en lugar de David obtener sus propias variables locales
podemos deshacernos de ellos.
Eso se siente bien que estamos limpiando esto.
Entonces puedo decir que David va a ser [0] y nombres [0]
y casas [0].
Y luego tenemos a Rob similar puede ahorrar en esto.
Vamos a poner esto aquí, así que va a ser arbitrariamente ids [1].
Él va a ser nombres [1],
y luego, por último, las casas [1].
>> Todavía un poco tedioso, y ahora tengo que resolver esto,
así que vamos a decir "nombres [0], id [0], casas [0],
y vamos a pluralizar esto.
Ids, IDS, IDS.
Y de nuevo, lo estoy haciendo, así que de nuevo, ya estoy recurriendo a copiar / pegar de nuevo,
lo más probable es que hay otra solución aquí.
Es probable que pueda limpiar esto más lejos con un bucle o algo así,
Así que en resumen, es un poco mejor, pero todavía se siente como
Estoy recurriendo a copiar / pegar, pero incluso esto, sostengo,
es realmente no es fundamentalmente la solución adecuada porque
¿Y si en algún momento decidimos que usted sabe qué?
En realidad, deberíamos haber estado almacenando las direcciones de email de David y Rob
y todos los demás en este programa.
También hay que guardar los números de teléfono.
También hay que guardar los números de contacto de emergencia.
Tenemos todas estas piezas de datos que desea almacenar,
Entonces, ¿cómo hace usted para hacer eso?
>> Usted declara otra matriz en la parte superior, a continuación, agregar manualmente
una dirección de correo electrónico [0], la dirección de correo electrónico [1]
para David y Rob y así sucesivamente.
Pero no hay realmente sólo una suposición subyacente en este diseño
que estoy usando el sistema de honor saber que
[I] en cada uno de los varios arrays
que pasa es que se refieren a la misma persona,
por lo que [0] en ids es el número 123,
y voy a asumir que los nombres [0]
es la misma persona el nombre y casas [0]
es la casa de la misma persona y así sucesivamente para todos los arrays diferentes que crean.
Pero nótese que no hay vínculo fundamental
entre los 3 pedazos de información, id, nombre y la casa,
a pesar de que la entidad que estamos tratando de modelar en este programa no es arrays.
Las matrices son precisamente de esta manera programática de hacerlo.
Lo que realmente queremos para modelar en nuestro programa es una persona
al igual que David, una persona como Rob dentro de los cuales
o encapsulación es un nombre y una ID y una casa.
>> ¿Podemos de alguna manera expresar esta idea de la encapsulación
mediante el cual una persona tiene una identidad, un nombre y una casa
y no recurrir a este truco por el que realmente nos
Confiamos en que algo soporte
se refiere a la misma entidad humana en cada uno de estos conjuntos dispares?
De hecho, podemos hacer esto.
Déjame ir más importante por ahora, y me deja crear mi propio tipo de datos
realmente por primera vez.
Se utilizó esta técnica en Scramble,
pero aquí voy a seguir adelante y crear un tipo de datos,
y sabes qué, yo voy a llamarlo estudiante o persona,
y yo voy a usar typedef para definir un tipo.
Voy a decir que se trata de una estructura,
y luego esta estructura va a ser de estudiante tipo, vamos a decir,
aunque es un poco anticuado ahora para mí.
Diremos "int id."
Vamos a decir "nombre de cadena."
Entonces vamos a decir "casa de Cuerdas",
por lo que ahora el final de estas líneas de código
Acabo enseñado sonido metálico que existe
además de un tipo de datos enteros, además de cuerdas, además de dobles, además de carrozas.
>> A partir de este momento en la línea de tiempo de 11, ahora hay un nuevo tipo de datos llamado a los estudiantes,
y ahora puedo declarar una variable de estudiante en cualquier lugar que desee,
así que me baje aquí a la gente.
Ahora puedo deshacerme de esto, y puedo ir de nuevo a David aquí,
y David realmente puedo decir que David,
literalmente podemos nombrar la variable de mí mismo,
va a ser de tipo estudiantil.
Esto puede parecer un poco extraño, pero esto no es tan diferente
de declarar algo como un entero o una cadena o un flotador.
Lo que pasa a llamarse estudiante ahora,
y si quiero poner algo dentro de esta estructura
Ahora tengo que usar una nueva pieza de sintaxis, pero es bastante sencillo,
david.id = 123, david.name = "David" en la capital de D,
y david.house = "Mather,"
y ahora puedo deshacerme de esta cosa aquí.
Notificación ahora hemos rediseñado nuestro programa en realidad una forma mucho mejor
en que ahora nuestro programa refleja el mundo real.
>> Hay una noción real de una persona o un estudiante.
Aquí tenemos ahora una versión C de una persona o más específicamente un estudiante.
En el interior de esa persona son estas características pertinentes,
ID, nombre y casa, así que Rob se convierte esencialmente la misma cosa aquí abajo,
estudiante para robar, y ahora rob.id = 456,
rob.name = "Rob".
El hecho de que la variable se llama Rob es una especie de sentido.
Podríamos haberlo llamado x o y o z.
Nos llamó a Rob a ser semánticamente consistente,
pero en realidad el nombre es dentro de ese mismo campo,
así que ahora tengo esto.
Esto también no se siente como el mejor diseño que he codificado David.
He codificado Rob.
Y todavía tengo que recurrir a alguna copia y pega cada vez que quiero nuevas variables.
Por otra parte, tengo que darle al parecer cada una de estas variables un nombre,
aunque yo preferiría describir estas variables
estudiantes más genéricamente.
>> Ahora podemos combinar las ideas que han estado trabajando bien para nosotros
y en lugar de decir: "¿Sabes qué, dame unos estudiantes llamados variables,
y vamos a tener que ser de tamaño 3 ", por lo que ahora puede refinar más a fondo,
deshacerse del manual declaró David,
y que en su lugar puede decir algo así como estudiantes [0] aquí.
Entonces puedo decir que los estudiantes [0] aquí,
estudiantes [0] aquí, y así sucesivamente, y me puede dar la vuelta
y limpiar eso para Rob.
Yo también podría ir Y ahora tal vez añadiendo un bucle
y el uso de GetString y getInt para conseguir realmente estos valores por parte del usuario.
Podría seguir acerca de cómo agregar una constante porque esto es generalmente una mala práctica
para codificar un número arbitrario como 3 aquí
y entonces sólo recuerda que debes elegir un máximo de 3 alumnos en el mismo.
Probablemente sería mejor usar # define en la parte superior de mi archivo
y el factor de que fuera, así que en realidad, déjame seguir adelante y generalizar esto.
>> Permítanme abrir un ejemplo que se encuentra entre la actual
ejemplos de antelación, structs1.
Se trata de un programa más completo que utiliza # define aquí
y dice que vamos a tener 3 estudiantes por defecto.
Aquí estoy declarando un valor de clase de los estudiantes,
por lo que un salón de clases de los estudiantes, y ahora estoy usando un bucle
sólo para hacer el código un poco más elegante, popular la clase
con la entrada del usuario, de modo iterar desde i = 0 en hasta estudiantes, que es 3.
Y entonces pedir al usuario en esta versión
¿cuál es el ID del estudiante, y lo consigue con getInt.
¿Cuál es el nombre del estudiante, y luego me pongo con GetString.
¿Qué es la casa del estudiante? Lo entiendo con GetString.
Y luego al final aquí me decidí a cambiar
cómo estoy imprimiendo estos y utilizar realmente un bucle,
¿Y quién soy yo imprimir?
De acuerdo con el comentario que estoy imprimiendo a nadie en Mather,
y eso es todo lo que Rob y Tommy y así sucesivamente en realidad-de Tommy en Mather.
Tommy y David se imprimiría en este caso, pero, ¿cómo funciona esto?
No hemos visto a esta función antes, pero tomar una conjetura en cuanto a lo que hace.
Compara cadenas.
>> Es un poco no es evidente cómo se compara cadenas porque resulta
si devuelve 0, que significa que las cadenas son iguales.
Si devuelve un -1 significa que uno viene alfabéticamente antes que el otro,
y si devuelve una palabra que significa el otro viene alfabéticamente
antes que el otro, y se puede ver en línea o en la página de manual
para ver exactamente dónde está el que, pero todo esto está haciendo ahora es lo que está diciendo
si el [i]. casa es igual a "Mather"
a continuación, seguir adelante e imprimir esto y lo otro está en Mather.
Pero esto es algo que no hemos visto antes, y volveremos a ello.
Yo no recuerdo haber tenido que hacer esto en cualquiera de mis programas.
Gratuito aparentemente en referencia a la memoria, liberando la memoria,
pero lo que la memoria me estoy liberando al parecer en este bucle en la parte inferior de este programa?
Parece que me estoy liberando a nombre de una persona
y la casa de una persona, pero ¿por qué es eso?
>> Resulta que todas estas semanas que he estado usando GetString
hemos ido introduciendo tipo de un error en cada uno de sus programas.
GetString por diseño asigna memoria para que pueda volver a que una cadena,
como David, o Rob, y entonces puede hacer lo que quieras
con esa cadena en su programa, ya que hemos reservado la memoria para usted.
El problema es que todo este tiempo cada vez que llame GetString
Nosotros, los autores de GetString, han estado solicitando al sistema operativo
para darnos un poco de RAM para esta cadena.
Danos un poco de RAM para esta cadena siguiente.
Danos un poco más RAM para esta cadena siguiente.
Lo que usted, el programador, nunca han estado haciendo
que nos está dando de nuevo la memoria,
por lo que para estas semanas todos los programas que has escrito
han tenido lo que se llama un salto memoria por el que seguir usando
más memoria y más cada vez que llame GetString, y eso está bien.
Nos deliberadamente hacer que en las primeras semanas, porque no es tan interesante
tener que preocuparse de donde la cadena está viniendo.
Todo lo que quiero es la palabra Rob volver cuando el usuario lo tipos pulg
>> Pero avanzar ahora tenemos que comenzar a conseguir más sofisticado acerca de esto.
Cada vez que asignar memoria será mejor que eventualmente devolver.
De lo contrario, en el mundo real en tu Mac o PC que pueda tener de vez en cuando con experiencia
síntomas de que su equipo está a punto de paralizarse eventualmente
o la pelota de playa estúpido giro se acaba de ocupar la computadora de
atención entera y no puedes hacer las cosas.
Eso puede ser explicado por cualquier número de bugs, pero entre los posibles errores
son cosas que se llaman pérdidas de memoria mediante el cual una persona que escribió ese pedazo de software
que está utilizando no recordaba para liberar memoria
que él o ella le pidió al sistema operativo para,
no usar GetString, porque eso es una cosa CS50, pero utilizando funciones similares
que piden que el sistema operativo para la memoria.
Si usted o meten la pata y que en realidad nunca regresar memoria
un síntoma de que puede ser que un programa se ralentiza y retarda y reduce la velocidad
a menos que usted recuerde llamar gratis.
>> Volveremos a cuándo y por qué se llama libre,
pero vamos a seguir adelante sólo por si acaso y tratar de ejecutar este programa en particular.
Esto fue llamado structs1, introduzca.
Déjenme seguir adelante y ejecutar structs1, 123, David Mather,
456, Rob Kirkland, 789,
Tommy Mather, y vemos a David en Mather, de Tommy en Mather.
Esto es sólo una prueba de cordura poco que el programa está funcionando.
Ahora, por desgracia, este programa es un poco frustrante que
Hice todo ese trabajo, escribí en 9 diferentes cuerdas, pulsa enter,
se le dijo que estaba en Mather, pero obviamente yo sabía que estaba en Mather ya porque lo escribió.
Sería bueno si al menos este programa se parece más a una base de datos
y que en realidad recuerda lo que he escrito en
así que nunca más tenga que introducir estos registros estudiantiles.
Tal vez es como un sistema registrarial.
>> Podemos hacer esto usando esta técnica conocida como entrada de archivo del archivo de E / S y de salida,
una manera muy genérica de decir en cualquier momento que desee leer o escribir archivos de los archivos
usted puede hacer esto con un cierto conjunto de funciones.
Déjenme seguir adelante y abrir este structs2.c ejemplo,
que es casi idéntico, pero vamos a ver lo que hace ahora.
En la parte superior del archivo que declarar una clase de estudiantes.
I a continuación, rellenar la clase con la entrada del usuario,
por lo que esas líneas de código son exactamente como antes.
Entonces, si me desplazo hasta aquí puedo imprimir todos los que están en Mather arbitrariamente como antes,
pero esta es una nueva característica interesante.
Estas líneas de código son nuevos, e introducen algo aquí,
De archivos, todo en mayúsculas, y tiene * aquí también.
Permítanme pasar esto aquí, a * por aquí también.
>> Esta función no hemos visto antes, fopen,
pero significa abrir el archivo, así que vamos a leerlo a través de ellos,
y esto es algo que vamos a volver en conjuntos de procesadores futuros,
pero esta línea aquí esencialmente abre un archivo llamado base de datos,
y, específicamente, se abre de tal manera que puede hacer lo que a él?
[Inaudible-alumno]
Bien, entonces "w" sólo significa que está diciendo al sistema operativo
abrir este archivo de tal manera que yo pueda escribir en él.
No quiero que lo lea. Yo no quiero mirar sólo a él.
Quiero cambiar y agregar cosas potencialmente a la misma,
y el archivo se va a llamar base de datos.
Esto podría llamarse cualquier cosa.
Esto podría ser database.txt. Esto podría ser. Db.
Esto podría ser una palabra como foo, pero arbitrariamente escogió el nombre de la base de datos de archivo.
Esta es una prueba de cordura poco que volveremos en detalle en el tiempo,
si da, para el puntero de archivo, no significa NULL igual que todo está bien.
>> Larga historia corta, funciona como fopen veces fallan.
Tal vez el archivo no existe. Tal vez te has quedado sin espacio de disco.
Tal vez usted no tiene permiso para esa carpeta,
por lo que si fopen devuelve algo nulo malo ha pasado.
Por el contrario, si no devuelve fopen nulo todo está bien
y puedo empezar a escribir en este archivo.
He aquí un truco nuevo.
Se trata de un bucle para que se itera sobre cada uno de mis estudiantes,
y esto se ve muy similar a lo que hemos hecho antes,
pero esta función es un primo de la llamada printf printf fprintf para archivo,
y nota que es diferente en tan sólo 2 maneras.
Uno de ellos, que comienza con F en lugar de p,
pero luego su primer argumento es aparentemente lo que?
[Los estudiantes] del archivo. >> Se trata de un archivo.
Esta cosa llamada fp, que finalmente va a separar lo que es un apuntador de archivo,
pero por ahora simplemente fp representa el archivo que he abierto,
fprintf aquí para imprimir esta diciendo ID del usuario en el archivo, no a la pantalla.
Imprimir el nombre del usuario en el fichero, no a la pantalla,
la casa en el archivo, no a la pantalla, y luego aquí, obviamente,
cerrar el archivo, y luego hacia abajo aquí libremente la memoria.
>> La única diferencia entre esta versión y la versión 2 1
es la introducción de fopen y este archivo como *
y esta noción de fprintf, así que vamos a ver lo que el resultado final es.
Déjame ir a mi ventana de terminal.
Déjame correr structs2, introduzca.
Parece que todo está bien. Vamos a volver a ejecutar structs2.
123, David Mather, 456, Rob Kirkland,
789, Tommy Mather, introduzca.
Parece que se comportaban de la misma, pero si ahora hago ls
cuenta de lo que está en el archivo aquí entre toda mi código, base de datos,
así que vamos a abrir esa, gedit de base de datos, y ver eso.
No es la más sexy de formatos de archivo.
Realmente es un pedazo de línea de datos por línea por línea,
pero aquellos de ustedes que usan archivos de Excel o CSV, valores separados por comas,
Ciertamente podría haber utilizado fprintf hacer en su lugar tal vez algo como esto
por lo que yo podía crear el equivalente de un archivo de Excel
al separar con comas cosas, no sólo las nuevas líneas.
>> En este caso, si hubiera utilizado en lugar comas en lugar de líneas nuevas
Yo, literalmente, podría abrir el archivo de base de datos en Excel si en cambio lo hizo ver como esto.
En resumen, ahora que tenemos el poder para escribir en archivos
ahora podemos empezar a datos persistentes, manteniéndolo alrededor del disco
para que podamos mantener la información en torno a una y otra vez.
Tenga en cuenta un par de cosas más que ahora son un poco más familiar.
En la parte superior de este archivo C tenemos un typedef
porque queríamos crear un tipo de datos que representa una palabra,
por lo que este tipo se denomina palabra, y en el interior de esta estructura
que es un poco más de lujo ahora.
¿Por qué es una palabra compuesta de parecer una matriz?
¿Qué es una palabra que sólo intuitivamente?
>> Es una serie de caracteres.
Es una secuencia de caracteres espalda con espalda con espalda.
Letras en mayúsculas resulta ser arbitrariamente decir la longitud máxima
de cualquier palabra en el diccionario que está utilizando para Scramble.
¿Por qué tengo un +1?
El carácter nulo.
Recordemos cuando hicimos el ejemplo Bananagrams necesitábamos un valor especial
al final de la palabra con el fin de seguir la pista
de donde las palabras en realidad terminó, y como la especificación del conjunto de problema, dice
aquí estamos asociando con una palabra dada un valor boolean,
una bandera, por así decirlo, cierta o falsa.
¿Has encontrado ya esta palabra, porque nos damos cuenta de
Realmente necesitamos una manera de recordar no sólo lo que una palabra está en Scramble
pero si no es así, lo humano, lo he encontrado
así que si usted encuentra la palabra "the" No se puede escribir el, entrar, el, entrar, la, introduzca
y obtener 3 puntos, 3 puntos, 3 puntos, 3 puntos.
Queremos ser capaces de poner en lista negra la palabra mediante el establecimiento de un bool
en true si ya lo has encontrado, y por eso nos
encapsulada en esta estructura.
>> Ahora, aquí en Scramble hay esta otra estructura llamada diccionario.
En ausencia de aquí es la palabra typedef porque en este caso
necesitábamos para encapsular la idea de un diccionario,
y un diccionario contiene un montón de palabras,
como se deduce de esta matriz, y cuántas de esas palabras hay?
Bueno, sea este tamaño variable llamada dice.
Pero sólo tenemos un diccionario.
No necesitamos un tipo de datos llamado diccionario.
Sólo tenemos uno de ellos, por lo que resulta en C
que si no dices typedef, que acaba de decir struct, a continuación, dentro de las llaves
usted pone sus variables, a continuación, poner el nombre.
Esto se declara una variable denominada diccionario
que se parece a esto.
Por el contrario, estas líneas están creando una estructura de datos reutilizable llamado palabra
que se pueden crear múltiples copias de, al igual que hemos creado
varias copias de los estudiantes.
>> ¿Qué significa este último término nos permite hacer?
Déjame volver en, digamos, un ejemplo más simple de tiempos más sencillos,
y me dejó abrir, digamos, compare1.c.
El problema en cuestión es en realidad pelar
la capa de una cadena y empezar a despegar estas ruedas de entrenamiento
porque resulta que una cadena todo este tiempo
es como prometimos en la semana 1 realmente sólo un apodo,
un sinónimo de la biblioteca CS50 para algo que se parece un poco más críptico,
char *, y hemos visto esta estrella antes.
Lo vimos en el contexto de los archivos.
>> Ahora vamos a ver por qué hemos estado ocultando este detalle desde hace algún tiempo.
Aquí hay un archivo llamado compare1.c,
y, al parecer, le pide al usuario 2 cadenas, s y t,
y luego se trata de comparar esas cadenas para la igualdad en la línea 26,
y si son iguales se dice, "Usted escribió la misma cosa"
y si no somos iguales dice: "Ha escrito cosas diferentes".
Déjenme seguir adelante y ejecutar este programa.
Déjame ir a mi directorio de origen, haga una compare1. Se compila bien.
Déjame correr compare1.
Voy a acercar, introducir.
Diga algo. HELLO.
Voy a decir algo nuevo. HELLO.
Sin duda alguna no escriba cosas diferentes.
>> Déjame intentarlo de nuevo. BYE BYE.
Definitivamente no es diferente, así que lo que está pasando aquí?
Bueno, lo que realmente se comparan en la línea 26?
[Inaudible-alumno]
Sí, por lo que resulta que una cadena, tipo de datos, es una especie de mentira piadosa.
Una cadena es un char *, pero lo que es un char *?
Un char *, como se dice, es un puntero,
y un puntero es una dirección efectiva,
suma una ubicación en la memoria, y, si por casualidad usted ha escrito en una palabra como HOLA
Recuerdo las discusiones anteriores de cadenas
esto es como la palabra HOLA.
Recuerde que una palabra como HOLA se puede representar
como una serie de personajes como este
y luego con un carácter especial en el extremo llamado el carácter nulo,
como la denota \.
¿Qué es en realidad una cadena?
Observe que este es varios fragmentos de memoria,
y, de hecho, al final de ella sólo se conoce una vez que mirar a través de toda la cadena
buscando el carácter nulo especial.
Pero si esto es un trozo de memoria de la memoria de mi ordenador,
vamos a decir arbitrariamente que esta cadena sólo tuvimos suerte,
y se quedó colocado en el comienzo mismo de la RAM de mi ordenador.
Este byte es 0, 1, 2, 3, 4, 5, 6 ...
>> Cuando digo algo como GetString y hago string s = GetString
lo que realmente se devuelve?
Para estas últimas semanas, lo que realmente está siendo almacenado en s
no es esta cadena per se, pero en este caso es lo que se está almacenado
el número 0, porque lo que en realidad hace GetString
es que no físicamente devolver una cadena.
Eso no tiene mucho sentido conceptual.
Lo que hace de retorno es un número.
Ese número es la dirección de HOLA en la memoria,
y la cadena de s entonces, si pelar esta capa, la cadena no existe realmente.
No es más que una simplificación en la biblioteca CS50.
>> Esto realmente es algo que se llama char *.
Char tiene sentido porque ¿qué es una palabra, como HOLA?
Bueno, es una serie de caracteres, una serie de caracteres.
Char * significa que la dirección de un personaje,
así que, ¿qué significa para devolver una cadena?
Una manera agradable y sencilla de devolver una cadena
es más bien que tratar de averiguar cómo vuelvo a 5 o 6 bytes diferentes
permítanme volver a la dirección de la cual byte?
La primera de ellas.
En otras palabras, te voy a dar la dirección de un personaje en la memoria.
Eso es lo que representa char *, la dirección de un único carácter en la memoria.
Llame a esa variable s.
Conservar en esa dirección particular s, lo que me dijo es arbitrariamente 0,
sólo para mantener las cosas simples, pero en realidad es por lo general un número más grande.
>> Espera un minuto.
Si sólo me da la dirección del primer carácter, ¿cómo puedo saber cuál es la dirección es
el segundo carácter, la tercera, la cuarta y quinta de la?
[Inaudible-alumno]
Sólo se sabe dónde está el final de la cadena es por medio de este truco muy útil,
así que cuando usted usa algo como printf, lo que printf, literalmente, toma como argumento,
Recordamos que usamos este marcador de posición% s, y luego se pasa en
la variable que se almacena una cadena.
Lo que en realidad pasa es la dirección del primer carácter de la cadena.
Printf continuación, utiliza un bucle for o un bucle while como reciba la citada dirección,
por ejemplo, 0, así que voy a hacer esto ahora,
printf ("% s \ n", s);
Cuando llamo printf ("% s \ n", s); lo que realmente estoy proporcionando con printf
es la dirección del primer carácter en s, que en este caso es arbitrario H.
>> ¿Cómo printf saber qué es exactamente lo que se mostrará en la pantalla?
La persona que implementó printf implementado un bucle while o un bucle for
que dice que este personaje es igual al carácter nulo especial?
Si no, lo imprima. ¿Qué tal este?
Si no se imprime, imprimir, imprimir, imprimirla.
Oh, éste es especial. La impresión se detiene y devuelve al usuario.
Y eso es literalmente todo lo que ha estado sucediendo por debajo de la campana,
y eso es mucho para digerir en el primer día de clase,
pero por ahora es realmente la piedra angular de todo entendimiento
que ha estado sucediendo dentro de la memoria de nuestro ordenador,
y, finalmente, vamos a molestar a este aparte con un poco de ayuda
de uno de nuestros amigos de Stanford.
>> El profesor Nick Parlante de Stanford ha hecho esta secuencia maravilloso video
de todo tipo de lenguas diferentes que introdujeron
este Claymation poco Binky carácter.
La voz que usted está a punto de escuchar un adelanto en apenas pocos segundos sneak
es el de un profesor de Stanford, y usted está recibiendo
sólo 5 o 6 segundos de esto ahora mismo,
pero esta es la nota en la que vamos a celebrar hoy
y comenzará el miércoles.
Te doy Fun puntero con Binky, la vista previa.
[♪ ♪ Music] [Profesor Parlante] Hey, Binky.
Despierta. Es tiempo para la diversión puntero.
[Binky] ¿Qué es eso? Aprenda acerca de los punteros?
Oh, qué bien!
>> Nos vemos el miércoles.
[CS50.TV]