[Powered by Google Translate] [Semana 4]
[David J. Malan] [Harvard University]
[Esta é CS50.] [CS50.TV]
>> Todo ben, iso é CS50, e este é o comezo da semana 4,
e este é un dos algoritmos de clasificación máis lenta posible.
Cal era que só asistiu alí?
Que era unha especie de burbulla, en orde grande (n ^ 2) + suma,
e en realidade non son os únicos no mundo parecen saber
que tipo de burbulla é ou seu tempo de execución.
En realidade, esta foi unha entrevista con Eric Schmidt de Google
eo ex senador Barack Obama só uns anos.
>> Agora, o senador, que está aquí en Google,
e eu gusto de pensar a presidencia como unha entrevista de emprego.
Agora, é difícil conseguir un traballo como presidente, e está pasando os rigores agora.
Tamén é difícil conseguir un emprego en Google.
Temos preguntas, e facemos preguntas nosos candidatos,
e este é de Larry David Schwimmer.
Vostedes pensan que eu estou a xogar? É aquí mesmo.
O que é o xeito máis eficaz para clasificar un millón de enteiros de 32 bits?
[Risas]
Ben-
Sinto moito. >> Non, non, non, non.
Eu creo que o bubble sort sería o camiño mal para ir.
>> Imos, que lle dixo iso?
A semana pasada, lembro que tivo un salto de código, polo menos por un día,
e pasaron a concentrarse en algunhas ideas de nivel superior e de resolución de problemas de forma máis xeral
no contexto de investigación e clasificación,
e introduciu algo que non cubrir este nome a semana pasada,
pero a notación asintótica, o Big O, o Omega Grande,
e ás veces a notación Big Theta, e estes eran simplemente formas
de describir o tempo de execución de algoritmos,
canto tempo leva para un algoritmo para ser executado.
>> E ten que se lembrar que falou sobre o tempo de execución en termos de tamaño
da entrada, que xeralmente chamamos n, calquera que sexa o problema pode ser,
onde n é o número de persoas na sala,
o número de páxinas dun libro de teléfono, e comezamos a escribir as cousas
como O (n ^ 2) ou O (n) ou O (n log n),
e mesmo cando as matemáticas non deu moi correcto tan perfectamente
e foi n ² - n / 2, ou algo así
Nós, pola contra, só tirar algúns dos termos de orde máis baixa,
ea motivación alí é que realmente queremos unha
tipo de forma obxectiva avaliar
o desempeño de programas ou o desempeño de algoritmos
que, ao final do día, non ten nada que ver, por exemplo,
coa velocidade do seu ordenador hoxe.
>> Por exemplo, se aplicar bubble sort
ou aplicar merge sort tipo ou selección no ordenador de hoxe,
un ordenador 2 GHz, e executa-lo,
e iso leva algún número de segundos o próximo ano, hai un 3 GHz
ou un ordenador 4 GHz, e podería, entón, afirmar que "Guau, o meu algoritmo
é agora dúas veces máis rápido ", cando en realidade que obviamente non é o caso.
É só o hardware quedou máis rápido, pero o seu ordenador
non, e así nós realmente queremos tirar cousas como
múltiplos de 2 ou múltiplos de 3, cando se trata de describir
quão rápido ou lento como un algoritmo é realmente e concentrarse só
en n ou algún factor º,
algún poder do mesmo, como no caso dos tipos de na última semana.
E lembrar que, coa axuda de merge sort
fomos capaces de facer moito mellor do que o bubble sort e tipo de selección
e tipo de inserción mesmo.
>> Temos ata n log n, e, de novo,
Recordamos que log n xeralmente se refire a algo que crece
máis lentamente entón n, entón n log n, ata agora, era bo
porque era menos ² n.
Pero para acadar n log n con merge sort
cal foi o xerme dunha idea básica que tivemos para alavancar
que tamén alavancou de volta a semana 0?
Coma nós afrontar o problema de ordenación intelixente co merge sort?
Cal foi a clave da comprensión, quizais?
Ninguén.
Ok, imos dar un paso atrás.
Describe merge sort nas súas propias palabras.
Como funciona isto?
Ok, imos remar de volta para 0 semanas.
Ok, si.
[Inaudível-alumno]
Ok, bo, entón dividimos o conxunto de números en dous anacos.
Nós clasificada cada unha destas pezas, e entón fundiuse os,
e vimos esa idea antes de tomar un problema que é tan grande
e cortar-lo nun problema que é tan grande ou tan grande.
>> Teña en conta que do exemplo do libro de teléfono.
Teña en conta que o algoritmo de auto-contador de semanas atrás,
tipo así fundir foi resumida por este pseudocódigo aquí.
Cando está determinado n elementos, primeiro era comprobar a sanidade.
Se n <2, entón non facer nada
porque se n <2, entón n é 0 ou 1, obviamente,
e así se é 0 ou 1 que non hai nada para resolver.
Está feito.
A súa lista xa está trivialmente clasificados.
Pero se non, se ten dous ou máis elementos de ir adiante e división los
en dúas metades, dereita e esquerda.
Ordenar cada unha desas metades, e en seguida, mesturar as metades clasificados.
Pero o problema aquí é que, a primeira vista isto parece que estamos punting.
Esta é unha definición circular na que se eu lle pedín para clasificar estes elementos n
e está me dicindo "Todo ben, todo ben, imos clasificar os elementos n / 2 e n / 2",
entón a miña seguinte pregunta vai ser "Todo ben, como clasificar a n / 2 elementos?"
>> Pero, debido á estrutura do presente programa,
porque non é este o caso base, por así dicir,
Neste caso particular, que di que, se n é <algún valor fixo como 2 retorno inmediato.
Non responder a esta mesma resposta circular.
Este proceso, este ciclicidade acabará.
Se eu lle preguntar "Ordenar estes elementos n", e di: "Moi ben, clasificar estes n / 2",
entón vostede di, "tipo, Fine estes N / 4, n / 8, n/16"
finalmente, vai dividir por un número o suficientemente
que vai ter só un elemento de esquerda, en que punto pode dicir:
"Aquí, aquí é un elemento clasificado único".
A continuación, o brillo deste algoritmo aquí é derivarse do feito de
que unha vez que ten todas estas listas individualmente clasificados,
todos os cales son de tamaño 1, o que parece ser inútil,
unha vez que comezar a fundín-las e mestura-los
construír, finalmente, como Rob fixo no vídeo, finalmente, unha lista ordenada.
>> Pero esa idea vai moito máis alá de clasificación.
Esta é a idea incorporado neste programa coñecido como recursão,
a idea que vostede é un programa,
e para resolver un problema que chama a si mesmo,
ou poñer no contexto de linguaxes de programación é unha función,
e, a fin de resolver un problema, a función de chamar a si mesmo
de novo e de novo e de novo, pero a función
non pode chamar-se infinitas veces.
Finalmente, ten para abaixo para fóra, por así dicir,
e ter algunha condición de base embutida que di
Actualmente deixar de chamar a si mesmo de xeito que todo o proceso
finalmente, de feito parar.
O que isto realmente significa para recurse?
>> Imos ver, si é que podemos facer un exemplo simple, trivial con, digamos,
3 persoas comigo aquí enriba no escenario, se alguén é cómodo.
Un, imos cara arriba, 2 e 3.
Se 3 quere vir ata aquí.
Se queres estar ao meu lado aquí nunha liña, imos supor que o problema na man
é moi trivialmente contar o número de persoas que están aquí.
Pero, francamente, estou canso de todos estes exemplos de conta.
Isto vai levar moito tempo, 1, 2, e punto, punto, punto.
Vai levar unha eternidade.
Eu prefiro só punto este problema completamente coa axuda de-Cal é o seu nome?
Sara. >> Sara, todo ben.
Kelly. >> Kelly e?
>> Willy. >> Willy, Sara, Kelly e Willy.
Agora eu teño a pregunta por alguén
cantas persoas están a este escenario, e eu non teño idea.
Esta é unha lista moi longa, e así en vez diso eu vou facer este truco.
Vou pedir para a persoa ao meu lado para facer a maior parte do traballo,
e unha vez que ela está feita facendo a maioría do traballo
Vou facer o mínimo de traballo posible e só engadir unha
para o que a súa resposta é, entón aquí imos nós.
Xa me preguntaron cantas persoas están no escenario.
Cantas persoas están no escenario á esquerda de ti?
A esquerda de min? >> Ok, pero non enganar.
Isto é bo, iso é correcto, pero si queremos seguir esta lóxica
imos supor que quere igualmente punto este problema á esquerda de ti,
entón en vez de responder directamente ir adiante e pasar a bola.
Ah, cantas persoas están á esquerda de min?
Cantas persoas están á esquerda?
1.
[Risas]
Ok, entón 0, entón o que agora Willy fixo
é vostede volveu a súa resposta neste sentido dicindo 0.
Agora, o que ten que facer? >> 1.
Ok, entón vostede é o 1, entón di: "Todo ben, eu estou indo para engadir un
para calquera conta de Willy era "a 1 + 0.
Vostede está agora 1 para a súa resposta á dereita agora
1. >> E a miña sería 2.
Bo, entón está tomando a resposta anterior 1,
engadindo a cantidade mínima de traballo que quere facer, o que é un.
Vostede agora ten dous, e despois entrega-me que o valor?
3, quero dicir, desculpe, 2.
Bo
>> Ben, tivemos 0 á esquerda.
Entón tivemos un, e entón engadir 2,
e agora está me dando o número 2,
e así que eu estou dicindo, todo ben, unha, 3.
Hai de feito tres persoas que estaban ao meu lado nesta fase,
para que pudéssemos ter feito isto, obviamente, moi lineal,
moi de moda obvio, pero o que realmente facer?
Pegamos un problema de tamaño 3 inicialmente.
A continuación, partiu-se en un problema de tamaño 2,
entón un problema de tamaño 1, e despois, finalmente, se a base
Foi moi, oh, non hai ninguén alí,
momento no que Willy volveu efectivamente unha resposta codificado un par de veces,
ea segunda foi entón borbulhava, borbulhava, borbulhava,
e, a continuación, engadindo a este un un adicional
temos implementado esa idea básica de recursão.
>> Agora, neste caso, realmente non resolver un problema
máis eficazmente, a continuación vimos ata agora.
Pero pense sobre os algoritmos que fixemos no escenario ata o momento.
Tivemos oito anacos de papel no cadro-negro,
en vídeo cando Sean estaba ollando para o número 7, eo que realmente fai?
Ben, el non fixo ningún tipo de dividir e conquistar.
El non fixo ningún tipo de recursão.
Ao contrario, el só fixo este algoritmo lineal.
Pero, cando introduciu a idea de números clasificados no escenario en directo a semana pasada
despois tivemos ese instinto de ir para o medio,
en que punto tivemos unha pequena lista de tamaño 4 ou outra lista de tamaño 4,
e despois tivemos o mesmo problema, por iso, repite, repite, repite.
Noutras palabras, nós recursed.
Moitas grazas aos nosos tres voluntarios aquí para demostrar recursão connosco.
>> Imos ver se non podemos facelo agora un pouco máis concreto,
resolver un problema que de novo podemos facer moi facilmente,
pero imos usalo como un trampolín para a aplicación desta idea básica.
Se eu queira calcular a suma de unha morea de números,
por exemplo, se pasar o número 3,
Eu quero darlle o valor de 3 sigma,
entón a suma de 3 + 2 + 1 + 0.
Eu quero volver a resposta 6,
entón imos implementar esta función sigma, esta función suma
que, unha vez máis, leva a entrada e, a continuación, retorna a suma
dese número ata o final a 0.
Nós poderiamos facelo moi sinxelo, non?
Nós poderiamos facelo con algún tipo de estrutura de loop,
entón deixe-me ir adiante e comezar con iso.
>> Engadir stdio.h.
Deixe-me me meter principal para traballar aquí.
Imos gardalo como sigma.c.
Entón eu vou entrar aquí, e eu vou declarar un int n,
e eu vou facer o seguinte, mentres que o usuario non cooperar.
Mentres o usuario non teña me deu un número positivo
deixe-me ir adiante e levalos para n = GetInt,
e deixe-me dar-lles algunhas instrucións sobre o que facer,
así printf ("enteiro positivo, por favor").
Só algo relativamente simple como este para que no momento en que alcanzou a liña 14
agora temos un número enteiro positivo, presuntamente, no n.
>> Agora imos facer algo con el.
Deixe-me ir adiante e calcular a suma, entón int suma = sigma (n).
Sigma é só suma, entón eu só estou escribindo a na forma máis extravagante.
Imos chamar-lle só sigma alí.
Esa é a suma, e agora eu vou imprimir o resultado,
printf ("A suma é% d \ n" suma).
E entón eu vou volver 0 para unha boa medida.
Fixemos todo o que este programa require, excepto a parte interesante,
que é para realmente implementar a función sigma.
>> Deixe-me ir ata aquí para a parte inferior, e deixe-me declarar función sigma.
Ten que ter unha variable que é do tipo enteiro,
e que tipo de datos que eu quero volver presuntamente de sigma?
Int, porque quero que corresponden as miñas expectativas en liña 15.
Desde aquí, deixe-me ir adiante e aplicar esta
dunha forma bastante simple.
>> Imos adiante e dicir suma int = 0,
e agora eu vou ter un pouco de loop aquí
que vai dicir algo como isto,
é (int i = 0; I <= número; i + +) suma + = i.
E entón eu vou volver suma.
Eu podería ter aplicado este en calquera número de formas.
Eu podería usar un loop while.
Eu podería ter pulado usando a variable de suma, se realmente quería,
pero en definitiva, só temos unha función que se eu non goof declara suma é 0.
A continuación, el itera de 0 encima a través do número,
e en cada iteração engade que o valor actual de suma e retorna suma.
>> Agora, hai unha optimización de leve aquí.
Este é probablemente un paso desperdiçado, pero que así sexa. Isto é bo para agora.
Estamos, polo menos vai ser completa e 0 todo o camiño enriba.
Non é moi difícil e moi sinxelo,
pero acontece que, coa función de sigma temos a mesma oportunidade
como fixemos aquí no escenario.
No escenario nós só contou cantas persoas estaban ó meu lado,
pero en vez diso se queremos contar o número 3 + 2 + 1
en ata 0 poderiamos igualmente punto para unha función
que eu vou describir en vez de ser recursiva.
Aquí imos facer un rápido check sanidade e que seguro que eu non fixen broma.
>> Sei que hai polo menos unha cousa neste programa que eu fixen de malo.
Cando eu bati entrar eu estou indo para obter calquera tipo de berrar comigo?
O que é que eu vou ser chamado sobre?
Si, eu esquezo o prototipo, entón eu estou usando unha función chamada sigma na liña 15,
pero non é declarada ata a liña 22, entón eu mellor forma Proativo subir aquí
e declarar un prototipo, e eu vou dicir int sigma (número enteiro), e é iso.
É aplicada na parte inferior.
>> Ou doutro xeito que eu podería resolver iso,
Eu podería mover a función alí enriba, o que non é malo,
pero polo menos cando os seus programas comezan a estar longo, francamente,
Eu creo que hai algún valor en ter sempre principal na parte superior
para que en que o lector pode abrir o ficheiro e inmediatamente ver
o que o programa está facendo sen ter que buscar por el
buscar que a principal función.
Imos ata a miña ventá de terminal aquí, probe facer sigma facer sigma,
e eu estraguei todo aquí tamén.
Declaración implícita de GetInt función significa que eu esquezo de facer o que máis?
[Inaudível-alumno]
Bo, entón, ao parecer, un erro común, entón imos poñer isto aquí,
cs50.h, e agora imos voltar para a miña xanela de terminal.
>> Vou borrar a pantalla, e eu vou facer reprise sigma.
Parece feita. Déixame correr sigma.
Vou escribir o número 3, e eu tiven 6, de modo que non comprobar un rigoroso
pero polo menos parece estar funcionando, a primeira vista, pero agora imos destruír-la,
e imos realmente aproveitar a idea do recurso, de novo,
nun contexto moi sinxelo, para que, no tempo de algunhas semanas
cando comezar a explorar estruturas máis elegantes de datos de matrices
temos outra ferramenta no conxunto de ferramentas coas que a
manipular estas estruturas de datos, como veremos.
Esta é a visión iterativa, a visión baseada en loop.
>> Deixe-me en vez agora facelo.
Deixe-me dicir que, en vez da suma do número
en ata 0 é realmente o mesmo que
+ Número sigma (número - 1).
Noutras palabras, así como no escenario eu punted cada unha das persoas próximas a min,
e eles, á súa vez, mantivo punting ata que finalmente o fondo do pozo en Willy,
que tivo que regresar unha resposta codificada como 0.
Aquí, agora, estamos tamén punting para sigma
a mesma función que orixinalmente foi chamado, pero o insight clave aquí
é que nós non estamos chamando sigma idéntica.
Nós non estamos pasando no n.
Estamos claramente pasando en número - 1,
así un problema un pouco menor, problema un pouco menor.
>> Desafortunadamente, esta non é unha solución bastante aínda, e antes de corrixir
o que pode ser tan obvia ir menos algúns de vostedes
deixe-me ir adiante e facer executar de novo.
Parece compilar todo ben.
Deixe-me reprise sigma con 6.
Oops, deixe-me reprise sigma con 6.
Nós xa vimos isto antes, aínda que o tempo accidentalmente pasado tamén.
Por que eu recibín esa fallo de segmento enigmática? Si
[Inaudível-alumno]
Non hai ningún caso base, e máis especificamente, o que probablemente pasou?
Este é un síntoma de que o comportamento?
Din que un pouco máis alto.
[Inaudível-alumno]
É un ciclo infinito de forma eficaz, e que o problema con loops infinitos
cando envolven recursão neste caso, unha función de chamada en si,
o que pasa cada vez que chamar a unha función?
Ben, creo que volver a ser como que estableceu a memoria dun ordenador.
Nós dixemos que non hai este anaco de memoria chamado pila que está no fondo,
e cada vez que chamar a unha función de memoria un pouco máis e colocar
sobre esta pila chamada conteñen variábeis locais que función ou parámetros,
por iso, se sigma Chamadas sigma sigma chama sigma
chama sigma de onde vén esa historia remata?
>> Ben, el acabou derrapagens o importe total
de memoria que ten dispoñible para o seu ordenador.
Vostede excedeu o segmento que debería estar dentro,
e ten esa fallo de segmento, o núcleo despexado,
e que o núcleo despexado significa que agora eu teño un arquivo chamado núcleo
que é un arquivo que contén ceros e uns
que, en realidade, no futuro, será útil para diagnóstico.
Se non é obvio para ti, onde o erro é
realmente pode facer un pouco de análise forense, por así dicir,
neste ficheiro dump de memoria, que, de novo, é só unha morea de ceros e uns
que, esencialmente, representa o estado do seu programa na memoria
no momento en que deixou de funcionar deste xeito.
>> A corrección aquí é que non podemos simplemente volver cegamente sigma,
o número + sigma dun problema un pouco menor.
Necesitamos ter algún tipo de caso base aquí,
e cal debe ser o caso base, probablemente, ser?
[Inaudível-alumno]
Ok, se o número é positivo que debe realmente volver iso,
ou dito doutra forma, se o número é, digamos, <= 0
vostede sabe, eu vou adiante e volver 0,
así como Willy fixo, e máis, eu estou indo para adiante
e devolver o presente, por iso non é moito menor do que
que a versión iterativa que instigou o primeiro en utilizar un loop for,
de notar que hai este tipo de elegancia a el.
En vez de regresar algún número e realizando toda a matemática esta
e engadindo as cousas coas variables locais
está no canto dicindo: "Ok, este é un problema super doado,
como o número é <0, deixe-me inmediatamente volver 0. "
>> Non imos molestar de apoio números negativos,
entón eu vou código ríxido o valor 0.
Pero se non, para aplicar esta idea de sumar
todos estes números xuntos, pode efectivamente dar unha pequena mordida
fóra do problema, así como fixemos aquí no escenario,
entón punto o resto do problema para a seguinte persoa,
pero neste caso a persoa próxima é a si mesmo.
É unha función de nome idéntico.
Só pasar un problema cada vez menor e menor de cada vez,
e aínda que non temos cousas moi formalizados en código aquí
iso é o que estaba a suceder na semana 0 co libro de teléfono.
Este é o que estaba acontecendo nas últimas semanas, con Sean
e as súas demostracións de busca de números.
É tomar un problema e división lo novo e de novo.
>> Noutras palabras, hai un xeito de traducir agora
esta construción mundo real, esta construción nivel superior
de dividir e conquistar e facer algo de novo e de novo
no código, entón iso é algo que imos ver de novo ao longo do tempo.
Agora, como un aparte, se vostede é novo para a recursividade ten que polo menos entender agora
por que iso é divertido.
Eu estou indo a ir a google.com,
e eu vou buscar algúns consellos e trucos sobre recursão, entrar.
Diga a persoa ao seu lado, no caso de que non estaban rindo agora.
Quixo dicir recursão?
Quería dicir ah, alí imos nós.
Ok, agora que está o resto de todos.
Un ovo de Pascua pequeno embutido en algún lugar alí en Google.
Como un aparte, un dos enlaces que poñemos na web do curso
por hoxe é só esa reixa de varios algoritmos de ordenación,
algúns dos cales nós miramos a semana pasada, pero o que é agradable sobre esta visualización
como tenta involucrar súa mente en torno a varias cousas relacionadas con algoritmos
saber que pode moi facilmente agora comezar con diferentes tipos de insumos.
As entradas de todos invertidos, as entradas ordenadas na maior parte, as entradas aleatoria e así por diante.
Como tenta, unha vez máis, distinguir estas cousas na súa mente
entender que esa URL na páxina web do curso na páxina de conferencias
pode axudar a razón por medio dalgún destes.
>> Hoxe por fin comezar a solucionar este problema de un tempo atrás,
o que foi que esta función de intercambio simplemente non funciona,
e cal foi o problema fundamental con esta cambio de función,
cuxo obxectivo foi, de novo, para intercambiar un valor aquí e aquí
de tal forma que isto ocorre?
Isto realmente non funciona. Por que?
Si
[Inaudível-alumno]
Exactamente, a explicación a este notan
simplemente foi porque cando chamar funcións en C
e esas funcións reciben argumentos, como a e b aquí,
está pasando en copias de calquera valor que está dando a esta función.
Non está introducindo os valores orixinais propios,
entón vimos isto no contexto buggyc,
buggy3.c, que parecía un pouco algo como isto.
>> Recórdese que tiñamos x e y inicializar con 1 e 2, respectivamente.
A continuación, imprimiu o que eran.
Eu, entón, dixo que eu estaba cambiando-os chamando intercambio de x, y.
Pero o problema era que o intercambio funcionou,
pero só no ámbito da programación propia función.
Así que bateu liña 40 eses valores trocados
foron xogados fóra, e así nada
na función de inicio orixinal foi realmente cambiou en todo,
por iso, se pensas que volta a continuación, como o que iso parece en termos da nosa memoria
este lado esquerdo do consello representa-
e eu vou facer o meu mellor para todo o mundo ver esta-se ese lado esquerdo do consello
representa, por exemplo, a súa memoria RAM, ea pila vai medrar por riba desa forma,
e chamamos unha función como principal, e principal ten dúas variables locais, X e Y,
imos describir aqueles que x aquí, e imos describir estes como y aquí,
e imos poñer en valor 1 e 2, de xeito que este aquí é principal,
e cando chama a principal función de intercambio do sistema operativo
dá a función de intercambio súa faixa propia de memoria na pila,
seu propio cadro na pila, por así dicir.
Tamén aloca 32 bits para estes ints.
Pasa a chamalos a e b, pero iso é totalmente arbitrario.
Podería chamar o que quere, pero o que ocorre cando principal
cambio de nome que leva este 1, coloca unha copia alí, coloca unha copia alí.
>> Hai outra variábel local en cambio, porén, o que chamou? Tmp. >>
Tmp, entón deixe-me dar-me máis 32 bits aquí,
eo que foi que eu fixen nesta función?
Eu dixen tmp int recibe un, entón un ten un, entón eu fixen iso cando xogou por última vez con este exemplo.
Entón un queda b, entón B é 2, e agora iso se fai 2,
e agora b recibe tempo, de xeito temporal é 1,
agora se fai presente b.
Isto é óptimo. Funcionou.
Pero entón, logo que o retorno da función
memoria de intercambio en efecto desaparece de xeito que pode ser reutilizado
por algunha outra función no futuro, e principal é obviamente completamente inalterada.
Necesitamos un xeito de solucionar este problema, fundamentalmente,
e hoxe imos finalmente ter unha forma de facelo a través do cal
podemos introducir algo chamado un punteiro.
Acontece que podemos solucionar este problema
non pasando copias de x e y
pero en vez pasando o que pensas que para a función de cambio?
Si, o que o enderezo?
Nós realmente non temos falado sobre enderezos en moitos detalles,
pero se este cadro representa a memoria do meu ordenador
seguramente poderiamos comezar a numeración dos bytes na miña memoria RAM
e dicir que iso é byte # 1, que é byte # 2, byte # 3,
byte # 4, # byte ... 2000000000 se eu tivera 2 gigabytes de memoria RAM,
para que pudéssemos certamente chegar a algún esquema de numeración arbitraria
para todos os bytes individuais na memoria do meu ordenador.
>> E se en vez cando eu chamo de intercambio
en vez de pasar unha copia de X e Y
por que non me vez pasar o enderezo de x aquí,
o enderezo de y aquí, esencialmente, o enderezo postal
X e Y, porque entón cambiar, se está informado
enderezo na memoria de x e y,
a continuación, cambiar, se adestrou un pouco,
podería potencialmente levar a este enderezo, por así dicir,
x, e cambiar o número alí, entón dirixirse ao enderezo de y,
cambiar o número de alí, mesmo se non está realmente a recibir copias de si mesmo eses valores,
por iso mesmo que nós conversas sobre iso como memoria principal
e memoria este troco como de poderosos e parte perigosa da C
é que calquera función pode tocar en calquera parte da memoria do ordenador,
e este é poderoso que pode facer cousas moi extravagantes con programas de ordenador en C.
Isto é perigoso, porque tamén se pode romper moi facilmente.
En realidade, unha das formas máis comúns para os programas estes días a ser explotado
Non é para un programador para realizar
que el ou ela está permitindo que un conxunto de datos
a ser escrito en un lugar na memoria que non se destinaba.
>> Por exemplo, el ou ela declárase unha matriz de tamaño 10
pero entón accidentalmente intenta poñer 11 bytes en que a matriz de memoria,
e comezar a tocar partes da memoria que non son máis válidos.
Só para contextual iso, algúns de vostedes poden saber que
software moitas veces pídelle a números de serie ou claves de rexistro,
Photoshop Word e e programas como este.
Existen rachaduras, como algúns de vostedes saben, en liña onde podes xirar un pequeno programa,
e listo, máis unha proposta de número de serie.
Como é que funciona?
En moitos casos, estas cousas son simplemente atopar nos ordenadores
segmentos de texto ceros reais do ordenador e entes
onde é que a función onde o número de serie é solicitado,
e substituír ese espazo, ou mentres o programa está a ser executado
pode descubrir onde a clave é almacenado
usar algo chamado un depurador, e pode romper forma de software que.
Isto non quere dicir que este é o noso obxectivo para o próximo par de días,
pero ten moito do mundo real ramificacións.
Isto acontece para involucrar un roubo de software,
pero hai tamén compromiso de máquinas completas.
>> En realidade, cando sitios estes días son explotadas
e comprometida e os datos son filtrada e contrasinal son roubados
que moitas veces se refire á mala xestión da súa memoria,
ou, no caso dos bancos de datos, a incapacidade de prever
entrada de contraditorio, de xeito máis sobre iso nas próximas semanas,
pero por agora só unha previa do sneak de tipo de dano que pode facer
por non entender moi ben como funcionan as cousas debaixo do capó.
Imos sobre a comprensión de por que isto está roto
cunha ferramenta que pode facer-se cada vez máis útil
como os nosos programas se fan máis complexas.
Ata agora, cando tivo un erro no seu programa
como foi preto de depurá-lo?
O que as súas técnicas foi, ata agora, se ensina pola súa TF
ou só autodidacta?
[Estudante] printf.
Printf, así printf probablemente foi o seu amigo en que, se quere ver
o que está a suceder dentro do seu programa
acaba de poñer printf aquí, printf aquí, printf aquí.
Entón executalo, e terá unha morea de cousas na pantalla
que pode usar para, entón, deducir o que realmente está a suceder de malo no seu programa.
>> Printf tende a ser unha cousa moi poderosa,
pero é un proceso moi manual.
Ten que poñer un printf aquí, un printf aquí,
e se colocar-lo dentro dun loop que pode obter de 100 liñas
de saída que entón ten que peneirar.
Non é un mecanismo moi user-friendly ou interactivo para programas de depuración,
pero felices hai alternativas.
Hai un programa, por exemplo, chamada GDB, GNU Debugger,
que é un arcano pouco como usalo.
É un pouco complexo, pero, francamente,
Esta é unha desas cousas que, se pór esta semana e na próxima
a hora extra para entender algo como GDB
vai aforrar probablemente decenas de horas, a longo prazo,
Entón, con iso, deixe-me dar-lle un teaser de como esa cousa funciona.
>> Eu estou na miña xanela de terminal.
Deixe-me ir adiante e compilar este programa, buggy3.
Xa é ata a data.
Deixe-me executa-lo así como fixemos un tempo atrás, e de feito, está roto.
Pero por que isto? Poida que eu estraguei a función de intercambio.
Quizais sexa a e b. Eu non estou moi movendo-os correctamente.
Deixe-me ir adiante e facelo.
En vez de só executar buggy3 déixeme en vez de executar este programa GDB,
e eu vou dicir a el para realizar buggy3,
e eu vou incluír un argumento de liña de comandos,-Tui,
e imos poñer isto en problemas futuros en especificación para lembrar.
E agora esta interface branco e negro apareceu que, de novo,
é un pouco esmagadora no primeiro, porque non é todo isto
información sobre a garantía aquí, pero polo menos hai algo familiar.
Na parte superior da xanela é o código real,
e se eu rolar por aquí, deixe-me ir para arriba do meu arquivo,
e, de feito, hai buggy3.c e observe na parte inferior da ventá
Eu teño ese aviso GDB.
>> Este non é o mesmo que o meu normal, John Harvard ventá.
Este é un aviso de que me vai permitir controlar GDB.
GDB é un depurador.
Un depurador é un programa que lle permite percorrer
execución do seu programa liña a liña por liña,
ao longo do camiño facendo o que quere co programa,
mesmo chamar funcións, ou á procura, máis importante,
en valores de variables varios.
Imos adiante e facelo.
Eu estou indo a ir adiante e escribir run no prompt do GDB,
Entón, observe na parte inferior esquerda da pantalla eu escriba correr,
e eu presione enter, e que o que facer?
É, literalmente, correu meu programa, pero eu realmente non vexo moi continuar aquí
porque eu realmente non teño dixo o depurador
para facer unha pausa nun determinado momento no tempo.
Só escribindo run executa o programa.
Eu realmente non vexo nada. Eu non podo manipulala lo.
>> En vez diso, deixe-me facelo.
Neste ventá GDB déixeme en vez tipo de quebra, entrar.
Isto non é o que eu quería escribir.
Imos ao contrario tipo de quebra de inicio.
Noutras palabras, quero establecer algo chamado un punto de interrupción,
que é apropiadamente chamado porque vai romper ou pausar
execución do seu programa naquel determinado lugar.
Principal é o nome da miña función.
Teña en conta que o GDB é moi intelixente.
El descubriu que acontece principal para comezar a aproximadamente na liña 18
de buggy3.c, e despois observar aquí na esquina superior esquerda
b + é ben próximo á liña 18.
Iso está me lembrar que eu definir un punto de interrupción na liña 18.
Esta vez, cando eu tecleo carreira, eu vou facer o meu programa
ata que chega o punto de interrupción,
para que o programa fará unha pausa para min na liña 18.
Aquí imos nós, executar.
Nada parece acontecer, pero aviso na parte inferior esquerda
programa de partida, buggy3, punto de interrupción nun inicio no buggy3.c liña 18.
¿Que podo facer agora?
>> Repare que eu poida comezar a escribir cousas como impresión,
Non printf, print x, e agora que é estraño.
Os US $ 1 é só unha curiosidade, como veremos
cada vez que imprimir algo que comeza un novo valor R $.
Isto é para que poida referirse a valores anteriores para o caso,
pero por agora o que está me dicindo impresión é que o valor de x, neste punto da historia
é aparentemente 134514032.
O que? Onde foi que mesmo vén?
[Inaudível-alumno]
En realidade, iso é o que imos chamar un valor de lixo, e non falamos sobre iso aínda,
pero a razón que arrincar variables
é, obviamente, para que eles teñan un valor que quere que eles teñan.
Pero o problema é lembrar que pode declarar variables
como eu fixen hai pouco no meu exemplo sigma
sen realmente dándolles un valor.
Teña en conta que o que eu fixen aquí no sigma.
Eu declarei n, pero o valor eu dar?
Ningún, porque eu sabía que nas próximas liñas
GetInt ía coidar do problema de poñer un valor dentro de n.
>> Pero, neste punto da historia da liña 11
e 12 de liña e liña 13 e liña 14
ao longo destas liñas de varias cal é o valor de n?
C simplemente non sabe.
É xeralmente un valor lixo, un número completamente aleatorio
que sobrou esencialmente dalgunha función anterior
sendo executado, así como o seu programa é executado
lembrar que a función recibe, función, función.
Todos estes cadros colocar en memoria, e despois os retorno funcións,
e, así como eu suxerín a goma a súa memoria, finalmente, é reutilizada.
Ben, acontece que esta variable x neste programa
parece contido algún valor lixo como 134514032
dalgunha función anterior, non un que eu escribín.
Podería ser algo que vén de forma eficaz co sistema operativo,
algunha función debaixo do capó.
>> Ok, todo ben, pero imos agora avanzar na seguinte liña.
Se eu escribir "next" no meu GDB pronta e eu bati entrar,
notar que o realce move cara abaixo a liña 19,
pero a implicación lóxica é que a liña 18
xa rematou de executar, entón eu escribir de novo "print x"
I que ver agora un, e de feito, eu fago.
Unha vez máis, as cousas $ é unha forma de lembra-lo GDB
o que a historia de impresións son de que vostede fixo.
Agora déixeme ir adiante e imprimir y, e, de feito, y é un valor tolo, así como,
pero non é gran cousa, porque na liña 19 que estamos a piques de atribuílo lo
o valor 2, entón deixe-me escribir "próximo" de novo.
E agora estamos na liña printf.
Deixe-me facer x impresión.
Deixe-me facer y impresión. Francamente, estou quedando un pouco canso de imprimir este.
Deixe-me no canto tipo "display x" e "y exhibición"
e agora cada vez que eu escribir un comando no futuro
Vou lembrar que é x e y, o que é X e Y, que é x e y.
>> Eu tamén poden, como un aparte, escriba "veciños de información."
Info é un comando especial.
Veciños significa que me amosa as variables locais.
Só no caso de eu esquezo ou esta é unha función, tolo complicado
que eu ou alguén escribiu veciños información vai dicir
que son todas as variables locais dentro desta función local
que pode preocupar se quere bisbilhotar.
Agora, printf está a piques de executar, entón deixe-me ir adiante e só un tipo "próximo".
Porque somos neste ambiente non estamos realmente vendo iso
executar aquí, pero entende que está quedando un pouco mutilado aquí.
Pero teña en conta que está substituíndo a pantalla de alí,
polo tanto, non é un programa perfecto aquí, pero todo ben, porque eu sempre pode fuçar
usando de impresión, se eu queira.
>> Deixe-me preto tipo de novo, e agora aquí é a parte interesante.
Neste punto da historia y é 2, e x 1,
como aquí suxerido, e de novo,
A razón é automaticamente amosar agora é porque eu usei o comando
Mostrar X e Y de exhibición, entón o momento próximo tecleo
na teoría X e Y deben ser trocados.
Agora xa sabemos que non vai ser o caso,
pero imos ver en un momento como podemos mergullar máis fondo para descubrir por que isto é verdade.
A continuación, e, por desgraza, aínda é y 2 e x aínda é un, e podo confirmar tanto.
Imprimir x, y de impresión.
En realidade, ningunha cambio que realmente aconteceu, entón imos comezar de novo isto.
Claramente intercambio é roto.
Imos en vez escriba "Executar" de novo.
Deixe-me dicir que si, que quero para reinicia-lo desde o inicio, entrar.
>> Agora estou de volta para a liña 18.
Agora notar x e y son os valores de lixo novo.
Next, Next, Next, Next.
Se eu estar aburrido eu tamén pode simplemente escribir n para a próxima.
Pode abreviar-lo para o máis curto posible secuencia de caracteres.
Intercambio agora roto.
Imos mergullo, entón en vez de escribir seguinte
agora eu vou escribir paso para que eu estou pisando dentro desta función
para que eu poida atravesalo-la, entón eu acertar paso e despois entrar.
Repare que os saltos destacando máis abaixo no meu programa para a liña 36.
Agora, cales son as variables locais?
Información local.
Nada só porque aínda non chegaran a esta liña,
entón imos adiante e dicir "próximo".
Agora parece que temos tmp tmp impresión.
Valor de lixo, non? Creo que si.
Que tal imprimir unha, imprimir B, 1 e 2?
Nun momento, así como eu escriba seguinte novo
tmp vai asumir un valor de 1, espera-se,
tmp que vai ser asignado o valor dun.
>> Agora imos facer imprimir a, b de impresión,
pero agora imprimir tmp, e é de feito un.
Deixe-me facer a continuación. Deixe-me facer a continuación.
Eu rematar a función de intercambio.
Eu aínda estou dentro dela na liña 40, entón deixe-me imprimir un,
b impresión, e eu non me importa o tmp é.
Parece que intercambio é correcto cando se trata de cambiar a e b.
Pero se eu agora escribir seguinte, eu saltar de volta para a liña 25,
e, por suposto, se eu escribir X e Y de impresión
eles aínda están inalterados, por iso non corrixido o problema.
Pero agora pode diagnóstico con este programa GDB
temos, polo menos, quedou un paso máis preto de comprender
o que está a suceder de malo sen ter que lixo noso código, colocando un printf aquí,
printf aquí, printf aquí e despois executa-lo novo e de novo
tentando descubrir o que está a suceder de malo.
>> Eu estou indo a ir adiante e saír fóra deste conxunto con saia.
Vai entón dicir: "Saír de todos os xeitos?" Si
Agora estou de volta ao meu poder normal, e eu estou feito empregando GDB.
Como un aparte, non utilizar este Tui-bandeira.
En realidade, se omiti-lo ten, esencialmente, a metade inferior da pantalla.
Se eu escriba intervalo principal e executa
Aínda podo correr o meu programa, pero o que vai facer é textualmente
só mostrar-me a unha corrente de liña de cada vez.
O Tui-, interface de usuario textual,
só mostra máis do programa dunha soa vez, o que pode ser un pouco conceptualmente máis fácil.
Pero, en realidade, eu só podo facer a continuación, avanzar, avanzar,
e eu vou ver unha liña de cada vez, e eu realmente quero ver o que está a suceder
Podo tipo de lista para ver unha morea de liñas veciñas.
>> Hai un vídeo que pedimos que ve ao problema define tres
en que Nate abrangue algúns dos meandros do GDB,
e esta é unha desas cousas que, sinceramente, onde algúns dos non-trivial de ti
nunca vai tocar GDB, e que vai ser unha cousa mala
porque literalmente vai acabar gastan máis tempo aínda este semestre
perseguir erros entón tería se pór en que media hora / hora
esta semana e aprendizaxe seguinte para sentirse cómodo co GDB.
Printf era o seu amigo.
GDB debe agora ser o seu amigo.
>> Calquera dúbida sobre o GDB?
E aquí está unha breve lista de algúns dos comandos máis poderosas e útiles.
Si >> É posible imprimir unha cadea?
É posible imprimir unha cadea? Absolutamente.
Non ten que ser só números enteiros.
Unha variable s é unha secuencia de só un tipo de s de impresión.
Ela vai amosar o que é variable de cadea.
[Inaudível-alumno]
El vai che dar o enderezo eo cadea.
Ela vai amosar tanto.
E unha última cousa, só porque estes son bo saber tamén.
Backtrace e armazón, deixe-me mergullo nunha última vez,
programa exactamente o mesmo co GDB.
Deixe-me ir adiante e executar a versión da interface de usuario textual,
romper principal.
Deixe-me ir adiante e executar de novo. Aquí estou.
Agora déixeme ir a continuación, next, next, next, next, paso, entrar.
>> E agora creo que eu son agora, a cambio de propósito, pero eu son así "Porra, cal foi o valor de x?"
Eu non podo facer máis x.
Eu non podo facer y porque eles non están no ámbito.
Eles non están no contexto, pero non hai problema.
Podo escribir backtrace.
Que me mostra todas as funcións que teñan firmado ata este momento.
Teña en conta que o un na parte inferior, de inicio, aliñan con principal
estar no fondo da nosa imaxe aquí.
O feito de que por riba de intercambio é que sexa aliñado con intercambio estar por riba del na memoria aquí,
e se eu queira volver ao inicio temporalmente podo dicir "marco".
Cal é o número? Principal é o marco # 1.
Eu estou indo a ir adiante e dicir "1 cadro".
>> Agora estou de volta na principal, e podo imprimir x, e podo imprimir y,
pero eu non podo imprimir a ou b.
Pero eu podo, se eu digo: "Ok, agarde un minuto. Onde estaba o intercambio?"
Deixe-me ir adiante e dicir "0 cadro."
Agora estou de volta onde eu quero ser, e como un aparte,
hai tamén outros comandos, como se está realmente quedando aburrido dixitación next, next, next, next,
xeralmente pode dicir cousas como "10 next", e que pode percorrer os próximos 10 liñas.
Tamén pode escribir "seguir" cando realmente funciona coa depuración a través dela.
Continuar ha executar o programa sen interrupción ata alcanzar outro punto de interrupción,
en un loop ou máis abaixo no seu programa.
>> Neste caso, continuou ata o final, eo programa saíu normalmente.
Esta é unha maneira extravagante, proceso inferior.
Só o seu programa saíu normalmente.
Máis sobre iso no vídeo e en sesións de depuración para vir.
Isto foi moito.
Imos dar o noso intervalo de 5 minutos aquí, e nós imos volver con structs e arquivos.
>> Se mergullou pset desta semana xa
vostede sabe que usamos no código de distribución,
o código fonte que ofrece a vostede como un punto de partida, algunhas técnicas novas.
En particular, introduciu esta nova contrasinal chamada struct, a estrutura,
para que poidamos crear variables personalizadas de sortes.
Tamén introduciu a noción de ficheiro de entrada de arquivo I / O, e de saída,
e isto é para que poidamos gardar o estado
da súa tarxeta Scramble para un ficheiro en disco
para que os compañeiros de ensino e podo entender
o que está a suceder dentro do seu programa sen ter que manualmente xogar
decenas de xogos de carreira.
Podemos facelo máis automatedly.
>> Esa idea dunha estrutura resolve un problema moi convincente.
Supoña que queremos aplicar algún programa
que dalgunha forma mantén o control da información sobre os alumnos,
e os alumnos poden ter, por exemplo, un número de identificación, o nome
e unha casa nun lugar como Harvard, así que estes son tres pezas de información
queremos manter ao redor, entón deixe-me ir adiante e comezar a escribir un pequeno programa aquí,
incluír stdio.h.
Deixe-me facer inclúen cs50.h.
E entón comezar a miña función principal.
Eu non vou preocupar con calquera argumentos de liña de comandos,
e aquí quero ter un estudante, entón eu vou dicir
un alumno ten un nome, entón eu vou dicir "nome de cadea."
Entón eu vou dicir unha estudante tamén ten un ID, ID para int,
e un alumno ten unha casa, entón eu tamén vou dicir "casa corda".
Entón eu vou pedir un pouco eses máis limpa coma este.
Ok, agora eu teño tres variables que representan un estudante, polo tanto, "un estudante."
>> E agora quero para cubrir eses valores, entón deixe-me ir adiante e dicir algo así como
"ID = 123".
Nome vai quedar David.
Digamos casa vai estar Mather,
e entón eu vou facer algo arbitrariamente como printf ("% s,
cuxa identificación é% d, vive en% s.
E agora, o que quero conectar aquí, un despois do outro?
Nome, ID de casa,; retorno 0.
Ok, a menos que eu estraguei todo en algún lugar aquí
Eu creo que temos un programa moi bo, que almacena un estudante.
Está claro que iso non é todo o que interesante. E se eu queira ter dous alumnos?
Isto non é gran cousa. Eu podo soportar 2 persoas.
Deixe-me ir adiante e destacar iso e ir ata aquí,
e podo dicir "id = 456" para alguén como Rob que vive en Kirkland.
>> Ok, agarde, pero non podo chamalos a mesma cousa,
e parece que vou ter que copiar iso,
entón deixe-me dicir que estas serán as variables de David,
e deixe-me algunhas copias destes para o Rob.
Imos chamar estas Rob, pero iso non vai funcionar agora
porque eu, agarde, imos cambiar-me para id1, name1 e house1.
Rob será de 2, 2.
Eu teño que cambiar isto aquí, aquí, aquí, aquí, aquí, aquí.
Espere, o que pasa con Tommy? Imos facer iso de novo.
Obviamente, se aínda pensa que isto é unha boa forma de facer isto, non é,
para copiar / pegar malo.
Pero nós resolvemos isto hai unha semana.
>> Cal foi a nosa solución, cando quería ter varias instancias do mesmo tipo de datos?
[Os alumnos] Unha matriz.
Unha matriz, entón deixe-me tentar limpar isto.
Deixe-me facer algunhas para min mesmo no cumio, e deixe-me en vez facelo aquí.
Imos chamar esta xente, e ao contrario diso eu vou dicir "IDs int",
e eu estou indo a soportar 3 de nós agora.
Eu vou dicir "nomes de cadea", e eu vou apoia-3 de nós,
e entón eu vou dicir "casas secuencia," e eu vou apoiar a 3.
Agora aquí en lugar de David recibindo as súas propias variables locais
podemos librar deles.
Isto é bo que estamos limpar isto.
Podo, entón, dicir que David vai ser [0] e nomes [0]
e casas [0].
E, a continuación, Rob podemos igualmente aforrar no presente.
Imos poñer iso aquí, entón vai ser arbitrariamente IDs [1].
El vai ser nomes, [1]
e, a continuación, finalmente, casas [1].
>> Aínda un pouco entediante, e agora eu teño que descubrir iso,
entón imos dicir "nomes [0], id [0], casas [0]
e imos pluralizar iso.
IDs, IDs, IDs.
E de novo, eu estou facendo iso, por iso de novo, eu xa estou recorrendo para copiar / pegar de novo,
así as probabilidades son de que hai outra solución aquí.
Eu probablemente pode borrar isto aínda máis con un lazo ou algo así,
Entón, en suma, é un pouco mellor, pero aínda se sente como
Estou recorrendo para copiar / pegar, pero iso, eu afirmo,
non é realmente a solución correcta fundamentalmente porque
E se algún día decidimos que vostede sabe o que?
Realmente debe ser almacenar enderezos de correo-e para David e Rob
e todos os outros neste programa.
Debemos tamén almacenar números de teléfono.
Debemos tamén almacenar números de contacto de urxencia.
Temos todas estas pezas de datos que desexa almacenar,
entón como vai facer sobre iso?
>> Vostede declara outra matriz, na parte superior, e entón engadir manualmente
un enderezo de correo electrónico [0] enderezo, correo electrónico [1]
para David e Rob e así por diante.
Pero hai realmente só unha suposición subxacente a este proxecto
que eu estou a usar o sistema de honra saber que
[I] en cada un dos distintos arrays
Acontece para referirse á mesma persoa,
así [0] no IDs é o número 123,
e eu vou asumir que os nomes [0]
é o nome da mesma persoa e casas [0]
é casa da mesma persoa e así por diante para todas as matrices diferentes que creo.
Pero teña en conta que non hai ningunha conexión fundamentais
entre esas tres pezas de información, identificación, nome e casa,
aínda que a entidade que estamos intentando modelo neste programa non é matrices.
Matrices son exactamente desa forma programática para facelo.
O que realmente queremos para modelar o noso programa é unha persoa
como David, unha persoa como Rob dentro do cal
ou encapsulamento é un nome e número de identificación e unha casa.
>> Será que podemos expresar esa idea de encapsulamento
polo cal unha persoa ten un ID, un nome e unha casa
e non recorrer a este truco realmente que nós só
confiar que algo soporte
refírese a unha mesma persoa humana en cada unha desas matrices diferentes?
Podemos realmente facer iso.
Deixe-me ir enriba principal para agora, e deixe-me crear o meu propio tipo de datos
para realmente por primeira vez.
Usan esta técnica en Scramble,
pero aquí eu estou indo a ir adiante e crear un tipo de datos,
e vostede sabe, eu vou chamalo de estudante ou persoa,
e eu vou usar typedef para definir un tipo.
Eu vou dicir que esta é unha estrutura,
e entón esta estrutura vai ser de estudante tipo, imos dicir,
aínda que sexa un pouco datado agora para min.
Nós imos dicir "int id".
Nós imos dicir "nome de cadea."
Entón, imos dicir "casa corda",
agora ata o final de estas poucas liñas de código
Acabo ensinou bumbum que non existe
un tipo de datos ademais de ints, ademais de cordas, ademais de dúos, ademais de coches alegóricos.
>> A partir deste momento, en vez da liña 11, existe agora un novo tipo de datos chamado estudantes,
e agora podo declarar unha variable alumno en calquera lugar que quero,
entón deixe-me ir ata aquí para a xente.
Agora podo me librar diso, e podo ir de volta para David aquí,
e David podo realmente dicir que David,
podemos literalmente nomear a variable despois de min,
vai ser de estudante tipo.
Isto pode parecer un pouco raro, pero isto non é así tan diferente
de declarar algo como un int ou unha cadea ou unha boia.
Isto só pasa a ser chamado de estudante,
e se eu queira poñer algo dentro desta estrutura
Eu agora teño que usar unha nova peza de sintaxe, pero é moi sinxelo,
david.id = 123, david.name = "David" na capital D,
e david.house = "Mather,"
e agora podo me librar destas cousas aquí.
Repare que temos agora redeseñado noso programa en realidade unha forma moito mellor
en que agora o noso programa reflicte o mundo real.
>> Hai unha noción do mundo real dunha persoa ou dun estudante.
Aquí temos agora unha versión C dunha persoa ou, máis especificamente, un estudante.
Dentro desa persoa son esas características relevantes,
ID, nome e casa, por iso Rob torna-se esencialmente a mesma cousa aquí,
entón estudante Rob, e agora rob.id = 456,
rob.name = "Rob".
O feito de que a variable é chamado Rob é unha especie de sentido.
Poderiamos chamar x ou y ou z.
Nós só nomeou Rob para semanticamente consistente,
pero realmente o nome está dentro do propio campo,
entón agora eu teño iso.
Isto tamén non se sente como o mellor proxecto en que eu codificado David.
Eu codificado Rob.
E eu aínda teño que recorrer a algún copiar e pegar cada vez que quero novas variables.
Ademais, eu teño que dar, ao parecer, cada unha desas variables dun nome,
aínda que eu prefiro describir estas variables
alumnos máis xenericamente como.
>> Agora podemos mesturar as ideas que teñen benvida a traballar ben para nós
e, en vez dicir: "Vostede sabe o que, dáme un estudantes variable chamada,
e imos ter que ser de tamaño 3 ", entón agora podo refinar este aínda máis,
librar-se do David manualmente declarou,
e podo dicir algo en vez como estudantes [0] aquí.
Podo, entón, dicir que os alumnos [0] aquí,
alumnos [0] aquí, e así por diante, e podo saír por aí
e limpar isto para Rob.
Eu tamén podería ir sobre agora quizais engadindo un loop
e usando GetString e GetInt para realmente obter estes valores do usuario.
Eu podería ir sobre como engadir unha constante, porque esta é xeralmente mala práctica
duro código algún número arbitrario como 3 aquí
e lembre que ten que poñer máis de 3 alumnos na mesma.
Probablemente sería mellor usar # define no principio do meu arquivo
e factor que fóra, así, de feito, deixe-me ir adiante e xeneralizar iso.
>> Deixe-me abrir un exemplo que está entre os de hoxe
exemplos de antelación, structs1.
Este é un programa máis completo que utiliza # defínese aquí
e di que imos ter 3 alumnos por defecto.
Aquí estou declarando un valor clase de estudantes,
para unha aula de alumnos, e agora está a usar un loop
só para facer o código un pouco máis elegante, encher a clase
coa entrada do usuario, de xeito iterar a partir de i = 0 encima para os alumnos, que é 3.
E entón eu pedir que o usuario nesta versión
o que é o ID do alumno, e eu fico con GetInt.
Cal é o nome do alumno, e entón eu comezo coa GetString.
O que é a casa do alumno? Recibe o con GetString.
E entón no fondo aquí, eu simplemente decidir cambiar
como eu estou imprimindo estes para fóra, e realmente usar un loop,
E quen son eu imprimir?
De acordo co comentario que eu estou imprimindo calquera en Mather,
e iso para Rob e Tommy e así por diante, en realidade Tommy en Mather.
Tommy e David sería impreso no caso, pero como é que isto funciona?
Nós non vimos esa función antes, pero dar un palpite sobre o que iso fai.
Compara cadeas.
>> É un pouco non obvio como se compara cordas pois verifica-se
se volve 0 que significa que as cordas son iguais.
Se volve a -1 que significa un vén antes do outro en orde alfabética,
e se volve un que significa a palabra outro vén en orde alfabética
antes do outro, e pode buscar en liña ou na páxina do home
para ver exactamente cal é cal, pero todo iso está facendo agora é que está dicindo
o [i]. casa é igual a "Mather"
entón vai adiante e imprimir así e así é en Mather.
Pero aquí está algo que non teña visto antes, e nós imos voltar a este.
Non me lembro de algunha vez ter que facelo en calquera un dos meus programas.
Libre aparentemente referíndose a memoria, liberando memoria,
pero o que a memoria aparentemente estou liberando neste loop na parte inferior do programa?
Parece que eu estou liberando nome dunha persoa
e da casa dunha persoa, pero por que isto?
>> Acontece que todas estas semanas que está a usar GetString
temos está a introducir tipo de un erro en cada un dos seus programas.
GetString pola memoria aloca proxecto para que poida voltar a vostede unha cadea,
como David, ou Rob, e entón pode facer o que quere
con esa secuencia no seu programa porque temos a memoria reservada para ti.
O problema é todo ese tempo cada vez que chamar GetString
nós, os autores de GetString, teñen que chegou a pedir o sistema operativo
para dar un pouco de memoria RAM para esta cadea.
Deixa-nos un pouco de memoria RAM para esta próxima corda.
Deixa-nos un pouco máis de memoria RAM para esta secuencia seguinte.
O que, programador, nunca foron facendo
está nos dando de volta a memoria,
así a estas semanas todos os programas que escribiu
ter o que se chama un salto de memoria en que eles seguen a usar
máis memoria e máis cada vez que chamar GetString, e iso é bo.
Nós deliberadamente facelo nas primeiras semanas, porque non é tan interesante
ter que se preocupar con onde a corda está a benvida.
Todo o que quere é a palabra Rob para volver cando o usuario escribe-lo dentro
>> Pero avanzar agora temos que comezar a estar máis sofisticada sobre iso.
A calquera momento que reservar memoria é mellor, eventualmente, entrega-lo de volta.
En caso contrario, no mundo real no seu Mac ou PC, pode ter ocasionalmente experimentado
síntomas onde o ordenador está a piques de paralizar eventualmente
ou o balón de praia parvo fiación só ocupando o ordenador
toda a atención e non pode facer as cousas.
Isto pode ser explicado por unha serie de erros, pero entre os posibles erros
son cousas chamadas derrames de memoria en que alguén que escribiu ese anaco de software
que está a usar non se lembrar de memoria libre
que el ou ela preguntou o sistema operativo para,
non usar GetString, porque iso é unha cousa CS50, pero usando funcións similares
que piden o sistema operativo para a memoria.
Se vostede ou romper e nunca realmente volver que a memoria
un síntoma de que pode ser un programa que retarda e reduce e retarda
a menos que se lembrar de chamar libre.
>> Nós imos voltar a cando e por que chamaría de libre,
pero imos adiante só para unha boa medida e intente realizar este programa en particular.
Isto foi chamado structs1, entrar.
Deixe-me ir adiante e executar structs1, 123, David Mather,
456, Rob Kirkland, 789,
Tommy Mather, e vemos David en Mather, Tommy en Mather.
Este é só unha proba de sanidade de que o programa está funcionando.
Agora, desgraciadamente, este programa é un pouco frustrante, en que
Eu fixen todo este traballo, eu escriba en nove distintos secuencias, prema Intro,
se dixo que estaba en Mather, pero, obviamente, eu sabía que estaba en Mather, porque eu xa escribiu.
Sería bo que, polo menos, este programa é máis como unha base de datos
e realmente se lembra do que eu escriba
entón eu nunca máis ter que introducir estes rexistros dos alumnos.
Quizais sexa como un sistema registrarial.
>> Podemos facelo empregando esta técnica coñecida como ficheiro de entrada de arquivo I / O, e de saída,
unha forma moi xenérica de dicir calquera momento que quere ler arquivos ou escribir arquivos
pode facelo cun determinado conxunto de funcións.
Deixe-me ir adiante e abrir este structs2.c exemplo,
que é case idéntico, pero imos ver o que fai agora.
No cumio do arquivo eu declaro unha clase de alumnos.
Eu, entón, encher a clase coa entrada do usuario,
para as liñas de código son exactamente como antes.
Entón, se eu rolar aquí eu imprimir os que están en Mather arbitrariamente como antes,
pero esta é unha novidade interesante.
Estas liñas de código son novos, e introdúcense algo aquí,
Arquivo, todas as tapas, e * aquí tamén.
Deixe-me pasar iso aquí, a * por aquí tamén.
>> Esta función non vimos antes, fopen,
pero significa ficheiro aberto, entón imos percorrer estes,
e iso é algo que nós imos voltar a serie de exercicios no futuro,
pero esta liña aquí, esencialmente, abre un arquivo chamado base de datos,
e específicamente ábrese a de tal forma que el pode facer o que con el?
[Inaudível-alumno]
Certo, entón "w" significa só que está dicindo o sistema operativo
abrir este ficheiro de tal forma que eu poida escribir para el.
Eu non quero le-lo. Eu non quero só ollar para el.
Eu quero cambiar isto e engadir cousas potencialmente a el,
eo arquivo vai ser chamado de base de datos.
Isto podería ser chamado nada.
Isto podería ser database.txt. Isto podería ser. DB.
Esta podería ser unha palabra como tal, pero eu arbitrariamente escolleu o nome da base de datos de arquivo.
Este é un exame de sanidade de que imos volver en gran detalle ao longo do tempo,
se fp, para punteiro do ficheiro, non NULL igual significa que todo está ben.
>> Longa historia curta, funcións como fopen ás veces fallan.
Quizais o ficheiro non existe. Quizais estea fóra do espazo de disco.
Quizais non ten permiso para esa carpeta,
por iso, se fopen retorna algo nulo de malo aconteceu.
Por outra banda, se fopen non volver nulo todo está ben
e podo comezar a escribir para este ficheiro.
Aquí está o truco novo.
Este é un loop que está interactuando sobre cada un dos meus alumnos,
e iso parece tan semellante ao que fixemos antes,
pero esta función é un primo do printf chamado fprintf para arquivo printf,
e entender que é diferente en só dous camiños.
Un deles, que comeza con f en vez de p,
pero entón o seu primeiro argumento é aparentemente o que?
[Os alumnos] do arquivo. >> É un arquivo.
Esa cousa chamada FP, que vai finalmente destrinçar o que é un punteiro do ficheiro,
pero por agora FP simplemente representa o arquivo que eu abri,
fprintf así aquí está dicindo imprimir ID de usuario para o ficheiro, non para a pantalla.
Imprimir o nome de usuario para o ficheiro, e non para a pantalla,
a casa para o arquivo, e non para a pantalla, e despois para abaixo aquí, obviamente,
Pecha o ficheiro, e despois para abaixo aquí libre da memoria.
>> A única diferenza entre esta versión ea versión 2 1
é a introdución de fopen e este arquivo con *
e esa noción de fprintf, entón imos ver o que o resultado final é.
Deixe-me ir para a miña xanela de terminal.
Déixame correr structs2, entrar.
Parece que todo está ben. Imos facer novo structs2.
123, David Mather, 456, Rob Kirkland,
789, Tommy Mather, entrar.
Parece que se comportou o mesmo, pero eu fago agora ls
entender o que está no arquivo aquí entre todo o meu código, base de datos,
entón imos abrir ese, ollar gedit de base de datos, e para iso.
Non é o máis sexy de formatos de ficheiro.
É realmente unha peza de liña de datos por liña por liña,
pero aqueles de vostedes que usan arquivos de Excel ou CSV, valores separados por comas,
Eu certamente podería usar fprintf ao contrario quizais facer algo así
para que eu puidese realmente crear o equivalente a un arquivo de Excel
separando as cousas con comas, e non só as novas liñas.
>> Neste caso, se eu tivese usado en vez comas en vez de novas liñas
Eu podería literalmente abrir este ficheiro de base de datos en Excel, se eu, no canto fixo parecer así.
En suma, agora que temos o poder de gardar arquivos
agora podemos comezar a persistencia de datos, mantendo-a en torno de disco
para que poidamos manter a información de novo e de novo.
Teña en conta un par de outras cousas que son agora un pouco máis familiar.
No cume deste arquivo C Temos un typedef
porque queriamos crear un tipo de datos que representa unha palabra,
de xeito que este tipo é chamado de palabra, e dentro desta estrutura
é un pouco afeccionado agora.
Porque é unha palabra composta de, ao parecer, unha matriz?
¿Que é unha palabra só de forma intuitiva?
>> É unha matriz de caracteres.
É unha secuencia de caracteres de costas cara atrás.
Letras en todas as tapas pasa de ser nós arbitrariamente dicir o lonxitude máxima
de calquera palabra no dicionario que estamos usando para Scramble.
Por que eu teño un 1?
O personaxe nulo.
Lembre-se de cando fixemos o exemplo Bananagrams necesitabamos dun valor especial
no fin da palabra, a fin de manter a par
onde as palabras realmente acabou, e como a especificación do conxunto de problemas di
aquí estamos asociando con unha determinada palabra un valor booleano,
unha bandeira, por así dicir, verdadeira ou falsa.
Xa atopou esta palabra xa, porque entendemos
Nós realmente necesitamos un xeito de lembrar non só o que a palabra está no Scramble
pero se está ou non, o ser humano, teñen atopado
de xeito que se non atopa a palabra "o" non pode simplemente escribir o, entra a, entre a, insira
e obter 3 puntos, 3 puntos, 3 puntos, 3 puntos.
Queremos ser capaces de untar esa palabra definindo un bool
a verdade se xa atopou, e é por iso que nós
encapsulado na súa estrutura.
>> Agora, aquí no Scramble hai esa outra struct chamado dicionario.
Ausente aquí é a palabra typedef porque neste caso
necesitabamos para encapsular a idea dun dicionario,
e un dicionario contén unha morea de palabras,
como implicado por esta matriz, e cantas desas palabras están alí?
Ben, calquera que sexa deste tamaño variable chamada di.
Pero só necesitamos un dicionario.
Nós non precisamos dun tipo de datos chamado dicionario.
Nós só necesitamos un deles, por iso acaba en C
que, se non se typedef, acaba de dicir struct, a continuación, dentro das claves
poñer as súas variables, entón poñer o nome.
Este é declarar unha variable chamada dicionario
que se parece con isto.
Por outra banda, estas liñas son a creación dunha estrutura de datos reutilizable chamado palabra
que pode crear varias copias, así como creamos
varias copias de alumnos.
>> O que isto finalmente permitir que fagamos?
Deixe-me volver a, digamos, un exemplo máis simple a partir de tempos máis simple,
e deixe-me abrir-se, por exemplo, compare1.c.
O problema aquí en mans é realmente casca de volta
a capa dunha corda e comezar a sacar esas Rodas pequenas
pois verifícase que unha secuencia de todo este tempo
é como prometemos a semana 1 só un apelido,
un sinónimo da biblioteca CS50 por algo que parece un pouco máis crítico,
char *, e vimos esa estrela antes.
Vímolo no contexto de arquivos.
>> Imos ver agora porque estamos escondendo ese detalle xa hai algún tempo.
Aquí está un arquivo chamado compare1.c,
e, ao parecer, pide ao usuario para dúas cordas, S e T,
e entón intenta comparar esas cordas de igualdade na liña 26,
e se son iguais el di: "Inseriu o mesmo",
e se eles non son iguais el di: "Inseriu cousas distintas."
Deixe-me ir adiante e executar este programa.
Deixe-me ir para o meu directorio de orixe, facer unha compare1. El compilou todo ben.
Déixame correr compare1.
Vou aumentar o zoom, entrar.
Diga algo. OLA.
Eu vou dicir algo novo. OLA.
Eu definitivamente non escriba cousas distintas.
>> Deixe-me tentar de novo. Bye Bye.
En definitiva non é diferente, por iso o que está a suceder aquí?
Ben, o que realmente está a ser comparado en liña 26?
[Inaudível-alumno]
Si, entón dedúcese que unha cadea, tipo de datos, é un tipo de mentira.
Unha cadea é un char *, pero o que é un char *?
A * char, como eles din, é un punteiro,
e un punteiro é efectivamente un enderezo,
suma un lugar na memoria, e se ocorrer de que vostede escriba unha palabra como OLA,
Recordo de discusións pasadas de cordas
Isto é como a palabra OLA.
Lembre que unha palabra como OLA pode ser representado
como unha matriz de caracteres como esta
e despois con un carácter especial ao final chamou o carácter nulo,
como o denota \.
O que é realmente unha cadea?
Nótese que isto é varios anacos de memoria,
e, de feito, o fin do que é coñecido só cando ollar a través de toda a cadea
ollando para o carácter nulo especial.
Pero este é un anaco da memoria a memoria do meu ordenador,
imos arbitrariamente dicir que esa secuencia de só tivo sorte,
e foi colocado no inicio de RAM do meu ordenador.
Este é o byte 0, 1, 2, 3, 4, 5, 6 ...
>> Cando digo algo así como GetString e eu cadea s = GetString
o que realmente está a ser devolto?
Para estas últimas semanas, o que realmente está a ser almacenado en s
non é esa secuencia de per se, pero neste caso o que está a ser almacenado é
o número 0, porque o que realmente fai GetString
é que fisicamente non voltar a cadea.
Que nin sequera realmente ten sentido conceptual.
O que fai de retorno é un número.
Ese número é o enderezo OLA na memoria,
e cadea s, a continuación, se pelar esta capa, cadea non existe realmente.
É só unha simplificación na biblioteca CS50.
>> Isto realmente é algo chamado char *.
Char ten sentido, porque o que é unha palabra, como OLA?
Ben, é unha serie de caracteres, unha serie de personaxes.
Char * significa que o enderezo dun personaxe,
Entón, o que iso supón para voltar a cadea?
Unha forma agradable, sinxelo de retornar unha cadea
é mellor que tentar descubrir como eu volver a 5 ou 6 bytes diferentes
deixe-me volver ao enderezo que byte?
O primeiro.
Noutras palabras, deixe-me dar-lle a dirección dun personaxe na memoria.
Isto é o que representa char *, unha dirección dun único carácter na memoria.
Chama iso é variable.
Tenda en s que determinado enderezo, o que eu dixen é arbitrariamente 0,
só para manter as cousas simples, pero en realidade el é xeralmente un número maior.
>> Espere un minuto.
Se só está me dando o enderezo do primeiro carácter, como sei que o enderezo é
do segundo personaxe, o terceiro, o cuarto eo quinto?
[Inaudível-alumno]
Só sabe que o fin da secuencia é por medio deste truco práctico,
Entón, cando usa algo así como printf, o que printf literalmente toma como argumento,
Recordamos que usan este espazo reservado% s, e entón pasa
a variable que está almacenando unha cadea.
O que realmente está pasando é o enderezo do primeiro carácter desa secuencia.
Printf entón usa un lazo ou bucle while, ao recibir este enderezo,
por exemplo, 0, entón deixe-me facelo agora,
printf ("% s \ n" s);
Cando eu chamo printf ("% s \ n" s), o que realmente estou dando printf con
é o enderezo do primeiro caracter en s, o cal, neste caso, é arbitraria H.
>> Como se sabe exactamente o que printf para amosar na pantalla?
A persoa que aplicou printf aplicou un loop while ou un loop
que di que este personaxe igualar o carácter nulo especial?
Se non, imprimir lo. Que tal un regalo?
Se non imprimir lo, imprimir lo, imprimir lo, imprimir lo.
Oh, este é especial. Interromper a impresión e voltar para o usuario.
E iso é, literalmente, todo o que está a suceder debaixo do capó,
e iso é moita cousa para dixerir, o primeiro día dunha clase,
pero por agora é realmente o alicerce de todo comprensión
que está a suceder dentro da memoria do noso ordenador,
e, finalmente, imos provocar este apart cunha pequena axuda
dun dos nosos amigos en Stanford.
>> Profesor Nick parlante en Stanford fixo esta secuencia marabilloso vídeo
de todo tipo de linguas diferentes que introduciron
Binky este pequeno personaxe Claymation.
A voz que está a piques de escoitar en apenas uns previa segunda
é a dun profesor de Stanford, e está quedando
só 5 ou 6 segundos de que agora,
pero esta é a nota que imos terminar hoxe
e comezar o mércores.
Eu darlle Fun Pointer con Binky, a visualización.
[♪ ♪ Música] [Profesor parlante] Ei, Binky.
Espertar. É hora de diversión punteiro.
[Binky] O que é isto? Máis información sobre punteiros?
Ah, bo!
>> Imos velo o mércores.
[CS50.TV]