[Powered by Google Translate] [Semana 4]
[David J. Malan] [Harvard University]
[Esta é CS50.] [CS50.TV]
>> Tudo bem, isso é CS50, e este é o começo da semana 4,
e este é um dos algoritmos de classificação mais lenta possível.
Qual era que apenas assistiu lá?
Que era uma espécie de bolha, em ordem grande O (n ^ 2) + soma,
e na verdade não são os únicos no mundo a parecem saber
que tipo de bolha é ou seu tempo de execução.
Na verdade, esta foi uma entrevista com Eric Schmidt, do Google
eo ex-senador Barack Obama apenas alguns anos atrás.
>> Agora, o senador, que está aqui no Google,
e eu gosto de pensar a presidência como uma entrevista de emprego.
Agora, é difícil conseguir um trabalho como presidente, e você está passando os rigores agora.
Também é difícil conseguir um emprego no Google.
Nós temos perguntas, e fazemos perguntas nossos candidatos,
e este é de Larry David Schwimmer.
Vocês pensam que eu estou brincando? É aqui mesmo.
O que é a maneira mais eficiente para classificar um milhão de inteiros de 32 bits?
[Risos]
Bem-
Sinto muito. >> Não, não, não, não.
Eu acho que o bubble sort seria o caminho errado para ir.
>> Vamos, que lhe disse isso?
Na semana passada, lembro que teve uma quebra de código, pelo menos por um dia,
e passaram a se concentrar em algumas idéias de nível superior e de resolução de problemas de modo mais geral
no contexto de pesquisa e classificação,
e introduziu algo que não tapa este nome na semana passada,
mas a notação assintótica, o Big O, o Omega Grande,
e às vezes a notação Big Theta, e estes eram simplesmente formas
de descrever o tempo de execução de algoritmos,
quanto tempo leva para um algoritmo para ser executado.
>> E você deve se lembrar que você falou sobre o tempo de execução em termos de tamanho
da entrada, que geralmente chamamos de n, qualquer que seja o problema pode ser,
onde n é o número de pessoas na sala,
o número de páginas de um livro de telefone, e começamos a escrever as coisas
como O (n ^ 2) ou O (n) ou O (n log n),
e mesmo quando a matemática não deu muito certo tão perfeitamente
e foi n ² - n / 2, ou algo assim
nós, ao invés, apenas jogar fora alguns dos termos de ordem mais baixa,
ea motivação lá é que realmente queremos uma
tipo de forma objetiva de avaliar
o desempenho de programas ou o desempenho de algoritmos
que, no final do dia, nada tem a ver, por exemplo,
com a velocidade de seu computador hoje.
>> Por exemplo, se você implementar bubble sort
ou você implementar merge sort tipo ou seleção no computador de hoje,
um computador 2 GHz, e executá-lo,
e isso leva algum número de segundos, no próximo ano, há um 3 GHz
ou um computador 4 GHz, e você poderia, então, afirmar que "Uau, meu algoritmo
é agora duas vezes mais rápido ", quando na realidade que obviamente não é o caso.
É só o hardware ficou mais rápido, mas o seu computador
não tem, e assim nós realmente queremos jogar fora coisas como
múltiplos de 2 ou múltiplos de 3, quando se trata de descrever
quão rápido ou lento como um algoritmo é realmente e se concentrar apenas
em n ou algum factor º,
algum poder do mesmo, como no caso dos tipos de na última semana.
E lembrar que, com a ajuda de merge sort
fomos capazes de fazer muito melhor do que o bubble sort e tipo de seleção
e tipo de inserção mesmo.
>> Temos até n log n, e, novamente,
Recordamos que log n geralmente se refere a algo que cresce
mais lentamente então n, então n log n, até agora, era bom
porque era menos de ² n.
Mas para alcançar n log n com merge sort
qual foi o germe de uma idéia básica que tivemos para alavancar
que também alavancou de volta na semana 0?
Como nós enfrentar o problema de ordenação inteligente com merge sort?
Qual foi a chave da compreensão, talvez?
Ninguém.
Ok, vamos dar um passo atrás.
Descreva merge sort em suas próprias palavras.
Como isso funciona?
Ok, vamos remar de volta para 0 semanas.
Ok, sim.
[Inaudível-aluno]
Ok, bom, então dividimos o conjunto de números em dois pedaços.
Nós classificada cada uma dessas peças, e então fundiu-os,
e temos visto essa idéia antes de tomar um problema que é tão grande
e cortar-lo em um problema que é tão grande ou tão grande.
>> Lembre-se do exemplo do livro de telefone.
Lembre-se o algoritmo de auto-contagem de semanas atrás,
tipo assim fundir foi resumida por este pseudocódigo aqui.
Quando você está determinado n elementos, primeiro era verificar a sanidade.
Se n <2, então não fazer nada
porque se n <2, então n é 0 ou 1, obviamente,
e assim se é 0 ou 1 não há nada para resolver.
Você está feito.
Sua lista já está trivialmente classificados.
Mas caso contrário, se você tem dois ou mais elementos de ir em frente e dividi-los
em duas metades, direita e esquerda.
Classificar cada uma dessas metades, e em seguida, mesclar as metades classificados.
Mas o problema aqui é que, à primeira vista isso parece que estamos punting.
Esta é uma definição circular em que se eu lhe pedi para classificar estes elementos n
e você está me dizendo "Tudo bem, tudo bem, vamos classificar os elementos n / 2 e os n / 2",
então minha próxima pergunta vai ser "Tudo bem, como você classificar a n / 2 elementos?"
>> Mas, devido à estrutura do presente programa,
porque não é este o caso base, por assim dizer,
Neste caso especial, que diz que, se n é <algum valor fixo como 2 retorno imediato.
Não responderemos com esta mesma resposta circular.
Este processo, este ciclicidade acabará.
Se eu lhe perguntar "Classificar estes elementos n", e você diz: "Muito bem, classificar estes n / 2",
então você diz, "tipo, Fine estes n / 4, n / 8, n/16"
eventualmente, você vai dividir por um número grande o suficiente
que você vai ter apenas um elemento de esquerda, em que ponto você pode dizer:
"Aqui, aqui é um elemento classificado único".
Em seguida, o brilho deste algoritmo aqui é derivar do fato de
que uma vez que você tem todas estas listas individualmente classificados,
todos os quais são de tamanho 1, o que parece ser inútil,
uma vez que você começar a fundi-las e mesclá-los
você construir, finalmente, como Rob fez no vídeo, finalmente, uma lista ordenada.
>> Mas essa idéia vai muito além de classificação.
Esta é a idéia incorporado neste programa conhecido como recursão,
a idéia em que você é um programa,
e para resolver algum problema que chama a si mesmo,
ou colocar no contexto de linguagens de programação você é uma função,
e, a fim de resolver um problema, você a função de chamar a si mesmo
de novo e de novo e de novo, mas a função
não pode chamar-se infinitas vezes.
Eventualmente, você tem para baixo para fora, por assim dizer,
e ter alguma condição de base embutida que diz
neste momento parar de chamar a si mesmo de modo que todo o processo
finalmente, se de fato parar.
O que isso realmente significa, para recurse?
>> Vamos ver, se é que podemos fazer um exemplo simples, trivial com, digamos,
3 pessoas comigo aqui em cima no palco, se alguém é confortável.
Um, vamos para cima, 2 e 3.
Se você 3 quer vir até aqui.
Se você quer estar ao meu lado aqui em uma linha, vamos supor que o problema na mão
é muito trivialmente contar o número de pessoas que estão aqui.
Mas, francamente, estou cansado de todos esses exemplos de contagem.
Isso vai levar algum tempo, 1, 2, e ponto, ponto, ponto.
Vai demorar uma eternidade.
Eu prefiro apenas punt este problema completamente com a ajuda de-qual é o seu nome?
Sara. >> Sara, tudo bem.
Kelly. >> Kelly e?
>> Willy. >> Willy, Sara, Kelly e Willy.
Agora eu tenho a pergunta por alguém
quantas pessoas estão-se neste palco, e eu não tenho idéia.
Esta é uma lista muito longa, e assim ao invés disso eu vou fazer este truque.
Eu vou pedir para a pessoa ao meu lado para fazer a maior parte do trabalho,
e uma vez que ela é feita fazendo a maioria do trabalho
Eu vou fazer o mínimo de trabalho possível e apenas adicionar uma
para o que a sua resposta é, então aqui vamos nós.
Já me perguntaram quantas pessoas estão no palco.
Quantas pessoas estão no palco à esquerda de você?
A esquerda de mim? >> Ok, mas não enganar.
Isso é bom, isso é correto, mas se queremos continuar esta lógica
vamos supor que você quer igualmente punt este problema à esquerda de você,
então ao invés de responder diretamente ir em frente e passar a bola.
Ah, quantas pessoas estão à esquerda de mim?
Quantas pessoas estão para a esquerda?
1.
[Risos]
Ok, então 0, então o que agora Willy fez
é você voltou a sua resposta neste sentido dizendo 0.
Agora, o que você deve fazer? >> 1.
Ok, então você é o 1, então você diz: "Tudo bem, eu estou indo para adicionar um
para qualquer contagem de Willy era, "para 1 + 0.
Você está agora 1 para a sua resposta para a direita é agora
1. >> E a minha seria 2.
Bom, então você está tomando a resposta anterior de 1,
adicionando a quantidade mínima de trabalho que você quer fazer, o que é um.
Você agora tem dois, e você em seguida, entregá-me qual o valor?
3, eu quero dizer, desculpe, 2.
Bom.
>> Bem, nós tivemos 0 para a esquerda.
Então nós tivemos um, e então adicionar 2,
e agora você está me dando o número 2,
e assim que eu estou dizendo, tudo bem, uma, 3.
Há de fato três pessoas que estavam ao meu lado nesta fase,
para que pudéssemos ter feito isso, obviamente, muito linear,
muito na moda óbvio, mas o que realmente fazer?
Pegamos um problema de tamanho 3 inicialmente.
Em seguida, partiu-se em um problema de tamanho 2,
então um problema de tamanho 1 e, em seguida, finalmente, caso a base
Foi muito, oh, não há ninguém lá,
altura em que Willy voltou efetivamente uma resposta codificado um par de vezes,
ea segunda foi então borbulhava, borbulhava, borbulhava,
e, em seguida, adicionando a este um um adicional
temos implementado essa idéia básica de recursão.
>> Agora, neste caso, realmente não resolver um problema
mais eficazmente, em seguida temos visto até agora.
Mas pense sobre os algoritmos que fizemos no palco até o momento.
Tivemos oito pedaços de papel no quadro-negro,
em vídeo quando Sean estava olhando para o número 7, eo que ele realmente faz?
Bem, ele não fez qualquer tipo de dividir e conquistar.
Ele não fez qualquer tipo de recursão.
Ao contrário, ele só fez este algoritmo linear.
Mas, quando introduziu a idéia de números classificados no palco ao vivo na semana passada
depois tivemos esse instinto de ir para o meio,
em que ponto nós tivemos uma pequena lista de tamanho 4 ou outra lista de tamanho 4,
e depois tivemos o mesmo problema, por isso, repete, repete, repete.
Em outras palavras, nós recursed.
Muito obrigado aos nossos três voluntários aqui para demonstrar recursão conosco.
>> Vamos ver se não podemos fazer isso agora um pouco mais concreto,
resolver um problema que novamente podemos fazer muito facilmente,
mas vamos usá-lo como um trampolim para a aplicação desta ideia básica.
Se eu quiser calcular a soma de um monte de números,
por exemplo, se você passar o número 3,
Eu quero dar-lhe o valor de 3 sigma,
então a soma de 3 + 2 + 1 + 0.
Eu quero voltar a resposta 6,
então vamos implementar esta função sigma, esta função soma
que, mais uma vez, leva a entrada e, em seguida, retorna a soma
desse número até o fim a 0.
Nós poderíamos fazer isso bastante simples, certo?
Nós poderíamos fazer isso com algum tipo de estrutura de loop,
então deixe-me ir em frente e começar com isso.
>> Incluir stdio.h.
Deixe-me me meter principal para trabalhar aqui.
Vamos guardá-lo como sigma.c.
Então eu vou entrar aqui, e eu vou declarar um int n,
e eu vou fazer o seguinte, enquanto o usuário não cooperar.
Enquanto o usuário não tenha me dado um número positivo
deixe-me ir em frente e levá-los para n = GetInt,
e deixe-me dar-lhes algumas instruções sobre o que fazer,
assim printf ("inteiro positivo, por favor").
Apenas algo relativamente simples como este para que no momento em que atingiu a linha 14
agora temos um número inteiro positivo, presumivelmente, no n.
>> Agora vamos fazer algo com ele.
Deixe-me ir em frente e calcular a soma, então int soma = sigma (n).
Sigma é apenas soma, então eu só estou escrevendo-a na forma mais extravagante.
Vamos chamar-lhe apenas sigma lá.
Essa é a soma, e agora eu vou imprimir o resultado,
printf ("A soma é% d \ n" soma).
E então eu vou retornar 0 para uma boa medida.
Fizemos tudo o que este programa requer, exceto a parte interessante,
que é para realmente implementar a função sigma.
>> Deixe-me ir até aqui para a parte inferior, e deixe-me declarar função sigma.
Tem que ter uma variável que é do tipo inteiro,
e que tipo de dados que eu quero voltar presumivelmente de sigma?
Int, porque eu quero que corresponder as minhas expectativas na linha 15.
Em aqui, deixe-me ir em frente e implementar esta
de uma forma bastante simples.
>> Vamos em frente e dizer soma int = 0,
e agora eu vou ter um pouco de loop aqui
que vai dizer algo como isso,
for (int i = 0; I <= número; i + +) soma + = i.
E então eu vou voltar soma.
Eu poderia ter implementado este em qualquer número de maneiras.
Eu poderia ter usado um loop while.
Eu poderia ter pulado usando a variável de soma, se eu realmente queria,
mas em suma, só temos uma função que se eu não goof declara soma é 0.
Em seguida, ele itera de 0 em cima através do número,
e em cada iteração acrescenta que o valor atual de soma e retorna soma.
>> Agora, há uma otimização de leve aqui.
Este é provavelmente um passo desperdiçado, mas que assim seja. Isso é bom para agora.
Estamos pelo menos vai ser completa e 0 todo o caminho em cima.
Não é muito difícil e bastante simples,
mas acontece que, com a função de sigma temos a mesma oportunidade
como fizemos aqui no palco.
No palco nós apenas contou quantas pessoas estavam ao meu lado,
mas em vez disso se quisermos contar o número 3 + 2 + 1
em até 0 poderíamos igualmente punt para uma função
que eu vou descrever em vez de ser recursiva.
Aqui vamos fazer um rápido check sanidade e ter certeza que eu não fiz brincadeira.
>> Eu sei que há pelo menos uma coisa neste programa que eu fiz de errado.
Quando eu bati entrar eu estou indo para obter qualquer tipo de gritar comigo?
O que é que eu vou ser gritado sobre?
Sim, eu esqueci o protótipo, então eu estou usando uma função chamada sigma na linha 15,
mas não é declarada até a linha 22, então eu melhor forma proativa subir aqui
e declarar um protótipo, e eu vou dizer int sigma (número inteiro), e é isso.
É implementada na parte inferior.
>> Ou de outra maneira que eu poderia resolver isso,
Eu poderia mover a função lá em cima, o que não é ruim,
mas pelo menos quando seus programas começam a ficar longo, francamente,
Eu acho que há algum valor em ter sempre principal no topo
para que você em que o leitor pode abrir o arquivo e logo em seguida ver
o que o programa está fazendo sem ter que procurar por ele
procurando que a principal função.
Vamos até a minha janela de terminal aqui, tente fazer sigma fazer sigma,
e eu estraguei tudo aqui também.
Declaração implícita de GetInt função significa que eu esqueci de fazer o que mais?
[Inaudível-aluno]
Bom, então, aparentemente, um erro comum, então vamos colocar isso aqui,
cs50.h, e agora vamos voltar para a minha janela de terminal.
>> Eu vou limpar a tela, e eu vou fazer reprise sigma.
Parece ter compilado. Deixa-me correr sigma.
Eu vou digitar o número 3, e eu tive 6, de modo que não verificar um rigoroso
mas pelo menos ele parece estar funcionando, à primeira vista, mas agora vamos destruí-la,
e vamos realmente alavancar a idéia de recursividade, de novo,
em um contexto muito simples, para que, no tempo de algumas semanas
quando começar a explorar estruturas mais elegantes de dados de matrizes
temos outra ferramenta no conjunto de ferramentas com as quais a
manipular essas estruturas de dados, como veremos.
Esta é a abordagem iterativa, a abordagem baseada em loop.
>> Deixe-me em vez agora fazer isso.
Deixe-me dizer que, em vez da soma do número
em até 0 é realmente a mesma coisa que
+ número sigma (número - 1).
Em outras palavras, assim como no palco eu punted a cada uma das pessoas próximas a mim,
e eles, por sua vez, manteve punting até que finalmente ao fundo do poço em Willy,
que teve de retornar uma resposta codificada como 0.
Aqui, agora, estamos igualmente punting para sigma
a mesma função que originalmente foi chamado, mas o insight chave aqui
é que nós não estamos chamando sigma idêntica.
Nós não estamos passando no n.
Nós estamos claramente passando em número - 1,
assim um problema um pouco menor, problema um pouco menor.
>> Infelizmente, esta não é uma solução bastante ainda, e antes de corrigir
o que pode ser tão óbvia saltar menos alguns de vocês
deixe-me ir em frente e fazer executar novamente.
Parece compilar tudo bem.
Deixe-me reprise sigma com 6.
Opa, deixe-me reprise sigma com 6.
Nós já vimos isso antes, embora o tempo acidentalmente passado também.
Por que eu recebo essa falha de segmentação enigmática? Sim.
[Inaudível-aluno]
Não há nenhum caso base, e mais especificamente, o que provavelmente aconteceu?
Este é um sintoma de que o comportamento?
Dizem que um pouco mais alto.
[Inaudível-aluno]
É um ciclo infinito de forma eficaz, e que o problema com loops infinitos
quando envolvem recursão neste caso, uma função de chamada em si,
o que acontece cada vez que você chamar uma função?
Bem, acho que voltar a ser como que estabeleceu a memória de um computador.
Nós dissemos que não há este pedaço de memória chamado de pilha que está no fundo,
e cada vez que você chamar uma função de memória um pouco mais é colocado
sobre esta pilha chamada contendo variáveis ​​locais que função ou parâmetros,
por isso, se sigma Chamadas sigma sigma chama sigma
chama sigma de onde vem essa história termina?
>> Bem, ele acabou derrapagens o montante total
de memória que você tem disponível para o seu computador.
Você ultrapassou o segmento que você deveria ficar dentro,
e você tem essa falha de segmentação, o núcleo despejado,
e que do núcleo despejado significa é que agora eu tenho um arquivo chamado núcleo
que é um arquivo contendo zeros e uns
que, na verdade, no futuro, será útil para diagnóstico.
Se não é óbvio para você, onde o bug é
você pode realmente fazer um pouco de análise forense, por assim dizer,
neste arquivo dump de memória, que, novamente, é apenas um monte de zeros e uns
que, essencialmente, representa o estado de seu programa na memória
no momento em que deixou de funcionar desta maneira.
>> A correção aqui é que não podemos simplesmente voltar cegamente sigma,
o número + sigma de um problema um pouco menor.
Nós precisamos ter algum tipo de caso base aqui,
e qual deve ser o caso base, provavelmente, ser?
[Inaudível-aluno]
Ok, desde que o número é positivo que deve realmente voltar isso,
ou dito de outra forma, se o número é, digamos, <= a 0
você sabe, eu vou em frente e retornar 0,
bem como Willy fez, e mais, eu estou indo para a frente
e devolver o presente, por isso não é muito menor do que
do que a versão iterativa que instigou o primeiro a utilizar um loop for,
de notar que há este tipo de elegância a ele.
Em vez de retornar algum número e realizando toda a matemática esta
e adicionando as coisas com as variáveis ​​locais
você está em vez dizendo: "Ok, se este é um problema super fácil,
como o número é <0, deixe-me imediatamente retornar 0. "
>> Nós não vamos incomodar de apoio números negativos,
então eu vou código rígido o valor de 0.
Mas caso contrário, para implementar esta idéia de somar
todos estes números juntos, você pode efetivamente dar uma pequena mordida
fora do problema, assim como fizemos aqui no palco,
então punt o resto do problema para a próxima pessoa,
mas neste caso a pessoa próxima é a si mesmo.
É uma função de nome idêntico.
Apenas passar um problema cada vez menor e menor de cada vez,
e mesmo que não temos coisas muito formalizados em código aqui
isso é exatamente o que estava acontecendo na semana 0 com o livro de telefone.
Este é exatamente o que estava acontecendo nas últimas semanas, com Sean
e com as nossas demonstrações de busca de números.
É tomar um problema e dividi-lo novamente e novamente.
>> Em outras palavras, há uma maneira de traduzir agora
esta construção mundo real, esta construção nível superior
de dividir e conquistar e fazer algo de novo e de novo
no código, então isso é algo que vamos ver novamente ao longo do tempo.
Agora, como um aparte, se você é novo para a recursividade você deve pelo menos entender agora
por que isso é engraçado.
Eu estou indo para ir a google.com,
e eu vou procurar algumas dicas e truques sobre recursão, entrar.
Diga a pessoa ao seu lado, se eles não estavam rindo agora.
Você quis dizer recursão?
Queria dizer-ah, lá vamos nós.
Ok, agora que está o resto de todos.
Um ovo de Páscoa pequeno embutido em algum lugar lá no Google.
Como um aparte, um dos links que colocamos no site do curso
por hoje é só essa grade de vários algoritmos de ordenação,
alguns dos quais nós olhamos na semana passada, mas o que é agradável sobre esta visualização
como você tenta envolver sua mente em torno de várias coisas relacionadas a algoritmos
saber que você pode muito facilmente agora começar com diferentes tipos de insumos.
As entradas de todos invertidos, as entradas ordenadas na maior parte, as entradas aleatória e assim por diante.
Como você tenta, mais uma vez, distinguir estas coisas em sua mente
perceber que essa URL no site do curso na página de Palestras
pode ajudá-lo a razão por meio de algum desses.
>> Hoje nós finalmente começar a resolver este problema de um tempo atrás,
o que foi que esta função swap simplesmente não funciona,
e qual foi o problema fundamental com esta troca de função,
cujo objetivo foi, novamente, para trocar um valor aqui e aqui
de tal forma que isso acontece?
Isso realmente não funciona. Por quê?
Sim.
[Inaudível-aluno]
Exatamente, a explicação para este notam
simplesmente foi porque quando você chamar funções em C
e essas funções recebem argumentos, como a e b aqui,
você está passando em cópias de qualquer valor que você está fornecendo a essa função.
Você não está fornecendo os valores originais próprios,
então vimos isso no contexto de buggyc,
buggy3.c, que parecia um pouco algo como isto.
>> Recorde-se que tínhamos x e y inicializado com 1 e 2, respectivamente.
Em seguida, imprimiu o que eles eram.
Eu, então, disse que eu estava trocando-os chamando troca de x, y.
Mas o problema era que a troca funcionou,
mas apenas no âmbito da permuta própria função.
Assim que bateu linha 40 esses valores trocados
foram jogados fora, e assim nada
na função de principal original foi realmente mudou em tudo,
por isso, se você acha que volta em seguida, como o que isso parece em termos de nossa memória
se este lado esquerdo do conselho representa-
e eu vou fazer o meu melhor para todo mundo ver esta-se esse lado esquerdo do conselho
representa, por exemplo, a sua memória RAM, ea pilha vai crescer em cima dessa forma,
e chamamos uma função como principal, e principal tem duas variáveis ​​locais, X e Y,
vamos descrever aqueles que x aqui, e vamos descrever estes como y aqui,
e vamos colocar em valores 1 e 2, de modo que este aqui é principal,
e quando chama a principal função de troca do sistema operacional
dá a função swap sua faixa própria de memória na pilha,
seu próprio quadro na pilha, por assim dizer.
Também aloca 32 bits para estes ints.
Acontece a chamá-los a e b, mas isso é totalmente arbitrário.
Poderia ter chamado o que quer, mas o que acontece quando principal
troca de chamadas é que leva este 1, coloca uma cópia lá, coloca uma cópia lá.
>> Há uma outra variável local em troca, porém, o que chamou? Tmp. >>
Tmp, então deixe-me dar-me mais 32 bits aqui,
eo que foi que eu fiz nesta função?
Eu disse tmp int recebe um, então um tem um, então eu fiz isso quando jogou pela última vez com este exemplo.
Então um fica b, então b é 2, e agora isso se torna 2,
e agora b recebe temp, de modo temporário é 1,
agora se torna presente b.
Isso é ótimo. Funcionou.
Mas então, logo que o retorno da função
memória swap efectivamente desaparece de modo que ele pode ser reutilizado
por alguma outra função no futuro, e principal é obviamente completamente inalterada.
Precisamos de uma maneira de resolver este problema, fundamentalmente,
e hoje nós vamos finalmente ter uma maneira de fazer isso através do qual
podemos introduzir algo chamado um ponteiro.
Acontece que podemos resolver este problema
não passando em cópias de x e y
mas em vez passando o que, você acha que, para a função de troca?
Sim, o que o endereço?
Nós realmente não temos falado sobre endereços em muitos detalhes,
mas se este quadro representa a memória do meu computador
certamente poderíamos iniciar a numeração dos bytes na minha memória RAM
e dizer que isso é byte # 1, este é byte # 2, byte # 3,
byte # 4, # byte ... 2000000000 se eu tiver 2 gigabytes de memória RAM,
para que pudéssemos certamente chegar a algum esquema de numeração arbitrária
para todos os bytes individuais na memória do meu computador.
>> E se em vez quando eu chamo de swap
em vez de passar em cópias de x e y
por que não me vez passar o endereço de x aqui,
o endereço de y aqui, essencialmente, o endereço postal
de X e Y, porque então trocar, se ele está informado
do endereço na memória de x e y,
em seguida, trocar, se treinou um pouco,
ele poderia potencialmente levar a esse endereço, por assim dizer,
x, e alterar o número lá, então dirigir para o endereço de y,
alterar o número de lá, mesmo se não estiver realmente recebendo cópias de si mesmo esses valores,
por isso mesmo que nós conversamos sobre isso como memória principal
e memória esta troca como sendo de poderosos e parte perigosa da C
é que qualquer função pode tocar em qualquer parte da memória do computador,
e este é poderoso em que você pode fazer coisas muito extravagantes com programas de computador em C.
Isso é perigoso, porque você também pode estragar muito facilmente.
Na verdade, uma das formas mais comuns para os programas estes dias a ser explorado
ainda não é para um programador para realizar
que ele ou ela está permitindo que um conjunto de dados
a ser escrito em um local na memória que não se destinava.
>> Por exemplo, ele ou ela declara uma matriz de tamanho 10
mas então acidentalmente tenta colocar 11 bytes em que a matriz de memória,
e você começar a tocar partes da memória que não são mais válidos.
Só para contextual isso, alguns de vocês podem saber que
software muitas vezes pede-lhe para números de série ou chaves de registro,
Photoshop Word e e programas como este.
Existem rachaduras, como alguns de vocês sabem, on-line onde você pode rodar um pequeno programa,
e pronto, mais um pedido de número de série.
Como é que funciona?
Em muitos casos, essas coisas são simplesmente encontrar nos computadores
segmentos de texto em zeros reais do computador e entes
onde é que a função onde o número de série é solicitado,
e você substituir esse espaço, ou enquanto o programa está sendo executado
você pode descobrir onde a chave é armazenado
usando algo chamado um depurador, e você pode quebrar maneira de software que.
Isso não quer dizer que este é o nosso objetivo para o próximo par de dias,
mas tem muito do mundo real ramificações.
Isso acontece para envolver um roubo de software,
mas há também comprometimento de máquinas inteiras.
>> Na verdade, quando sites estes dias são exploradas
e comprometida e os dados são vazou e senhas são roubados
isso muitas vezes se refere à má gestão de sua memória,
ou, no caso dos bancos de dados, a incapacidade de prever
entrada de contraditório, de modo mais sobre isso nas próximas semanas,
mas por agora apenas uma prévia do sneak de o tipo de dano que você pode fazer
por não entender muito bem como funcionam as coisas debaixo do capô.
Vamos sobre a compreensão de por que isso está quebrado
com uma ferramenta que irá tornar-se cada vez mais útil
como os nossos programas se tornam mais complexas.
Até agora, quando você teve um bug em seu programa
como você foi cerca de depurá-lo?
O que suas técnicas sido, até agora, se ensinado por seu TF
ou apenas autodidata?
[Estudante] printf.
Printf, assim printf provavelmente foi o seu amigo em que, se você quer ver
o que está acontecendo dentro do seu programa
você acabou de colocar printf aqui, printf aqui, printf aqui.
Então você executá-lo, e você terá um monte de coisas na tela
que você pode usar para, então, deduzir o que realmente está acontecendo de errado em seu programa.
>> Printf tende a ser uma coisa muito poderosa,
mas é um processo muito manual.
Você tem que colocar um printf aqui, um printf aqui,
e se você colocá-lo dentro de um loop que você pode obter de 100 linhas
de saída que então você tem que peneirar.
Não é um mecanismo muito user-friendly ou interativo para programas de depuração,
mas felizmente existe alternativas.
Há um programa, por exemplo, chamada GDB, o GNU Debugger,
que é um arcano pouco em como usá-lo.
É um pouco complexo, mas, francamente,
esta é uma daquelas coisas que, se você colocar nesta semana e na próxima
a hora extra para entender algo como GDB
você vai economizar provavelmente dezenas de horas, a longo prazo,
Então, com isso, deixe-me dar-lhe um teaser de como essa coisa funciona.
>> Eu estou na minha janela de terminal.
Deixe-me ir em frente e compilar este programa, buggy3.
Já é até à data.
Deixe-me executá-lo assim como fizemos um tempo atrás, e de fato, está quebrado.
Mas por que isso? Talvez eu estraguei a função swap.
Talvez seja a e b. Eu não estou muito movendo-os corretamente.
Deixe-me ir em frente e fazer isso.
Ao invés de apenas executar buggy3 deixe-me em vez de executar este programa GDB,
e eu vou dizer a ele para executar buggy3,
e eu vou incluir um argumento de linha de comando,-tui,
e vamos colocar isso em problemas futuros em especificação para lembrar.
E agora esta interface preto e branco apareceu que, novamente,
é um pouco esmagadora na primeira porque não é tudo isso
informações sobre a garantia aqui, mas pelo menos há algo familiar.
Na parte superior da janela é o código real,
e se eu rolar por aqui, deixe-me ir para o topo do meu arquivo,
e, de fato, há buggy3.c e observe na parte inferior da janela
Eu tenho esse aviso GDB.
>> Este não é o mesmo que o meu normal, John Harvard prompt.
Este é um aviso de que vai me permitir controlar GDB.
GDB é um depurador.
Um depurador é um programa que lhe permite percorrer
execução de seu programa linha a linha por linha,
ao longo do caminho fazendo o que quiser com o programa,
mesmo chamar funções, ou à procura, mais importante,
em valores de variáveis ​​vário.
Vamos em frente e fazer isso.
Eu estou indo para ir em frente e digitar run no prompt do GDB,
Então, observe na parte inferior esquerda da tela eu digitei correr,
e eu aperte enter, e que o que fazer?
É, literalmente, correu meu programa, mas eu realmente não vejo muito continuar aqui
porque eu realmente não tenho disse o depurador
para fazer uma pausa em um determinado momento no tempo.
Apenas digitando run executa o programa.
Eu realmente não vejo nada. Eu não posso manipulá-lo.
>> Em vez disso, deixe-me fazer isso.
Neste prompt GDB deixe-me em vez tipo de quebra, entrar.
Isso não é o que eu quis escrever.
Vamos ao invés tipo de quebra principal.
Em outras palavras, eu quero definir algo chamado um ponto de interrupção,
que é apropriadamente chamado porque ele vai quebrar ou pausar
execução de seu programa naquele determinado lugar.
Principal é o nome da minha função.
Observe que o GDB é muito inteligente.
Ele descobriu que acontece principal para começar a aproximadamente na linha 18
de buggy3.c, e depois observar aqui no canto superior esquerdo
b + é bem próximo à linha 18.
Isso está me lembrando que eu definir um ponto de interrupção na linha 18.
Desta vez, quando eu digito corrida, eu vou executar o meu programa
até que ela atinge ponto de interrupção,
para que o programa fará uma pausa para mim na linha 18.
Aqui vamos nós, correr.
Nada parece ter acontecido, mas aviso no canto inferior esquerdo
programa de partida, buggy3, ponto de interrupção em um principal no buggy3.c linha 18.
O que posso fazer agora?
>> Repare que eu possa começar a escrever coisas como impressão,
Não printf, print x, e agora que é estranho.
Os US $ 1 é apenas uma curiosidade, como veremos
cada vez que você imprimir algo que você começa um novo valor R $.
Isso é para que você possa se referir a valores anteriores para o caso,
mas por agora o que está me dizendo impressão é que o valor de x, neste ponto da história
é aparentemente 134514032.
O quê? Onde foi que mesmo vem?
[Inaudível-aluno]
Na verdade, isso é o que vamos chamar um valor de lixo, e nós não falamos sobre isso ainda,
mas a razão que você inicializar variáveis
é, obviamente, para que eles tenham algum valor que você quer que eles tenham.
Mas o problema é lembrar que você pode declarar variáveis
como eu fiz há pouco no meu exemplo sigma
sem realmente dando-lhes um valor.
Lembre-se o que eu fiz aqui no sigma.
Eu declarei n, mas o valor eu dar?
Nenhum, porque eu sabia que nas próximas linhas
GetInt iria cuidar do problema de colocar um valor dentro de n.
>> Mas, neste ponto da história da linha 11
e 12 de linha e linha 13 e linha 14
ao longo dessas linhas de várias qual é o valor de n?
Em C você simplesmente não sabe.
É geralmente algum valor lixo, um número completamente aleatório
que sobrou essencialmente de alguma função anterior
tendo sido executado, assim como seu programa é executado
lembrar que a função recebe, função, função.
Todos esses quadros se colocar em memória, e depois aqueles retorno funções,
e, assim como eu sugeri com a borracha a sua memória, eventualmente, é reutilizada.
Bem, acontece que esta variável x neste programa
parece ter contido algum valor lixo como 134514032
de alguma função anterior, não um que eu escrevi.
Poderia ser algo que vem de forma eficaz com o sistema operativo,
alguma função debaixo do capô.
>> Ok, tudo bem, mas vamos agora avançar para a próxima linha.
Se eu digitar "next" no meu GDB pronta e eu bati entrar,
notar que o realce move para baixo a linha 19,
mas a implicação lógica é que a linha 18
já terminou de executar, então se eu digitar novamente "print x"
I deve ver agora uma, e na verdade, eu faço.
Mais uma vez, as coisas $ é uma forma de lembrá-lo GDB
o que a história de impressões são de que você fez.
Agora deixe-me ir em frente e imprimir y, e, na verdade, y é um valor louco, bem como,
mas não é grande coisa, porque na linha 19 que estamos prestes a atribuí-lo
o valor 2, então deixe-me escrever "próximo" novamente.
E agora estamos na linha printf.
Deixe-me fazer x impressão.
Deixe-me fazer y impressão. Francamente, estou ficando um pouco cansado de imprimir este.
Deixe-me em vez tipo "display x" e "y exibição"
e agora cada vez que eu digitar um comando no futuro
Eu vou ser lembrado de que é x e y, o que é X e Y, o que é x e y.
>> Eu também podem, como um aparte, digite "moradores de informação."
Info é um comando especial.
Moradores significa que ele me mostra as variáveis ​​locais.
Apenas no caso de eu esquecer ou esta é uma função, louco complicado
que eu ou alguém escreveu moradores informações vai dizer
que são todas as variáveis ​​locais dentro desta função local
que você pode preocupar se você quiser bisbilhotar.
Agora, printf está prestes a executar, então deixe-me ir em frente e apenas um tipo "próximo".
Porque nós somos neste ambiente não estamos realmente vendo isso
executar aqui, mas percebe que está ficando um pouco mutilado aqui.
Mas note que está substituindo o ecrã de lá,
portanto, não é um programa perfeito aqui, mas tudo bem, porque eu sempre pode fuçar
usando de impressão, se eu quiser.
>> Deixe-me próximo tipo de novo, e agora aqui é a parte interessante.
Neste ponto na história y é 2, e x é 1,
como aqui sugerido, e de novo,
A razão é automaticamente exibir agora é porque eu usei o comando
display x e y de exibição, então o momento próximo digito
na teoria X e Y devem ser trocados.
Agora, já sabemos que não vai ser o caso,
mas vamos ver em um momento como podemos mergulhar mais fundo para descobrir por que isso é verdade.
Em seguida, e, infelizmente, ainda é y 2 e x ainda é um, e posso confirmar tanto.
Print x, y de impressão.
Na verdade, nenhuma troca que realmente aconteceu, então vamos recomeçar isso.
Claramente swap é quebrado.
Vamos em vez digite "Executar" novamente.
Deixe-me dizer que sim, que eu quero para reiniciá-lo desde o início, entrar.
>> Agora estou de volta para a linha 18.
Agora notar x e y são os valores de lixo novo.
Next, next, next, next.
Se eu ficar entediado eu também pode simplesmente digitar n para a próxima.
Você pode abreviar-lo para o mais curto possível seqüência de caracteres.
Swap é agora quebrado.
Vamos mergulhar, então ao invés de digitar seguinte,
agora eu vou escrever passo para que eu estou pisando dentro desta função
para que eu possa atravessá-la, então eu acertar passo e depois entrar.
Repare que os saltos destacando mais para baixo no meu programa para a linha 36.
Agora, quais são as variáveis ​​locais?
Informações locais.
Nada apenas porque ainda não tenha chegado a essa linha,
então vamos em frente e dizer "próximo".
Agora parece que temos tmp tmp impressão.
Valor de lixo, certo? Acho que sim.
Que tal imprimir uma, imprimir b, 1 e 2?
Em um momento, assim como eu escreva seguinte novamente
tmp vai assumir um valor de 1, espera-se,
tmp porque vai ser atribuído o valor de um.
>> Agora vamos fazer imprimir a, b de impressão,
mas agora imprimir tmp, e é de fato um.
Deixe-me fazer a seguir. Deixe-me fazer a seguir.
Eu terminei a função swap.
Eu ainda estou dentro dela na linha 40, então deixe-me imprimir um,
b impressão, e eu não me importo com o tmp é.
Parece que swap é correto quando se trata de trocar a e b.
Mas se eu agora digitar seguinte, eu pular de volta para a linha 25,
e, claro, se eu digitar x e y de impressão
eles ainda estão inalterados, por isso não ter corrigido o problema.
Mas agora talvez diagnóstico com este programa GDB
temos, pelo menos, ficou um passo mais perto de compreender
o que está acontecendo de errado sem ter que lixo nosso código, colocando um printf aqui,
printf aqui, printf aqui e depois executá-lo novamente e novamente
tentando descobrir o que está acontecendo de errado.
>> Eu estou indo para ir em frente e sair fora deste conjunto com saia.
Vai então dizer: "Sair mesmo assim?" Sim.
Agora estou de volta ao meu prompt normal, e eu estou feito usando GDB.
Como um aparte, você não precisa usar este tui-bandeira.
Na verdade, se você omiti-lo você tem, essencialmente, a metade inferior da tela.
Se eu digite intervalo principal e execute
Ainda posso correr o meu programa, mas o que ele vai fazer é mais textualmente
apenas mostrar-me a uma corrente de linha de cada vez.
O tui-, interface de usuário textual,
apenas mostra mais do programa de uma só vez, o que é provavelmente um pouco conceitualmente mais fácil.
Mas, na verdade, eu só posso fazer em seguida, avançar, avançar,
e eu vou ver uma linha de cada vez, e se eu realmente quero ver o que está acontecendo
Eu posso tipo de lista e ver um monte de linhas vizinhas.
>> Há um vídeo que pedimos que você vê para o problema define três
em que Nate abrange alguns dos meandros do GDB,
e esta é uma daquelas coisas que, sinceramente, onde alguns dos não-trivial de você
nunca vai tocar GDB, e que vai ser uma coisa ruim
porque literalmente você vai acabar gastando mais tempo ainda este semestre
perseguir erros então você teria se você colocar em que meia hora / hora
esta semana e aprendizagem seguinte para se sentir confortável com o GDB.
Printf era seu amigo.
GDB deve agora ser seu amigo.
>> Qualquer dúvida sobre o GDB?
E aqui está uma breve lista de alguns dos comandos mais poderosas e úteis.
Sim. >> É possível imprimir uma string?
É possível imprimir uma string? Absolutamente.
Ele não tem que ser apenas números inteiros.
Se uma variável s é uma seqüência de apenas um tipo de s de impressão.
Ela vai mostrar o que é variável de cadeia.
[Inaudível-aluno]
Ele vai te dar o endereço eo string.
Ela vai mostrar tanto.
E uma última coisa, só porque estes são bom saber também.
Backtrace e armação, deixe-me mergulhar em uma última vez,
programa exatamente o mesmo com o GDB.
Deixe-me ir em frente e correr a versão de interface de usuário textual,
quebrar principal.
Deixe-me ir em frente e correr novamente. Aqui estou.
Agora deixe-me ir em seguida, next, next, next, next, passo, entrar.
>> E agora acho que eu sou agora, em troca de propósito, mas eu sou assim "Porra, qual foi o valor de x?"
Eu não posso fazer mais x.
Eu não posso fazer y porque eles não estão no escopo.
Eles não estão no contexto, mas não há problema.
Eu posso digitar backtrace.
Que me mostra todas as funções que tenham firmado até este momento.
Observe que o um na parte inferior, principal, alinha com principal
estar no fundo da nossa imagem aqui.
O fato de que acima de swap é que seja alinhado com swap estar acima dele na memória aqui,
e se eu quiser voltar ao principal temporariamente posso dizer "frame".
Qual o número? Principal é o quadro # 1.
Eu estou indo para ir em frente e dizer "1 quadro".
>> Agora estou de volta na principal, e eu posso imprimir x, e eu posso imprimir y,
mas eu não posso imprimir a ou b.
Mas eu posso, se eu digo: "Ok, espere um minuto. Onde estava o swap?"
Deixe-me ir em frente e dizer "0 quadro."
Agora estou de volta onde eu quero ser, e como um aparte,
há também outros comandos, como se você está realmente ficando entediado digitação next, next, next, next,
geralmente você pode dizer coisas como "10 next", e que irá percorrer os próximos 10 linhas.
Você também pode escrever "continuar" quando você realmente se alimentado com a depuração através dela.
Continuar irá executar o programa sem interrupção até atingir outro ponto de interrupção,
se em um loop ou mais abaixo em seu programa.
>> Neste caso, continuou até o fim, eo programa saiu normalmente.
Esta é uma maneira extravagante, processo inferior.
Apenas seu programa saiu normalmente.
Mais sobre isso no vídeo e em sessões de depuração para vir.
Isso foi muito.
Vamos dar o nosso intervalo de 5 minutos aqui, e nós vamos voltar com structs e ficheiros.
>> Se você mergulhou pset desta semana já
você sabe que nós usamos no código de distribuição,
o código-fonte que oferecemos a você como um ponto de partida, algumas técnicas novas.
Em particular, introduziu esta nova palavra-chave chamada struct, para a estrutura,
para que possamos criar variáveis ​​personalizadas de sortes.
Nós também introduziu a noção de arquivo de entrada de arquivo I / O, e de saída,
e isto é para que possamos salvar o estado
de sua placa Scramble para um arquivo em disco
para que os companheiros de ensino e posso entender
o que está acontecendo dentro do seu programa sem ter que manualmente jogar
dezenas de jogos de corrida.
Podemos fazer isso mais automatedly.
>> Essa idéia de uma estrutura resolve um problema bastante convincente.
Suponha que queremos implementar algum programa
que de alguma forma mantém o controle das informações sobre os alunos,
e os alunos podem ter, por exemplo, um ID, um nome
e uma casa em um lugar como Harvard, assim que estes são três peças de informação
queremos manter ao redor, então deixe-me ir em frente e começar a escrever um pequeno programa aqui,
incluir stdio.h.
Deixe-me fazer incluem cs50.h.
E então começar a minha função principal.
Eu não vou preocupar com quaisquer argumentos de linha de comando,
e aqui eu quero ter um estudante, então eu vou dizer
um aluno tem um nome, então eu vou dizer "nome de cadeia."
Então eu vou dizer uma estudante também tem um ID, ID para int,
e um aluno tem uma casa, então eu também vou dizer "casa corda".
Então eu vou pedir um pouco esses mais limpa como este.
Ok, agora eu tenho três variáveis ​​com que representam um estudante, portanto, "um estudante."
>> E agora eu quero para preencher esses valores, então deixe-me ir em frente e dizer algo como
"ID = 123".
Nome vai ficar David.
Digamos casa vai ficar Mather,
e então eu vou fazer algo arbitrariamente como printf ("% s,
cuja identificação é% d, vive em% s.
E agora, o que eu quero ligar aqui, um após o outro?
Nome, ID de casa,; retorno 0.
Ok, a menos que eu estraguei tudo em algum lugar aqui
Eu acho que nós temos um programa muito bom, que armazena um estudante.
É claro que isso não é tudo o que interessante. E se eu quiser ter dois alunos?
Isso não é grande coisa. Eu posso suportar 2 pessoas.
Deixe-me ir em frente e destacar isso e ir até aqui,
e posso dizer "id = 456" para alguém como Rob que mora em Kirkland.
>> Ok, espere, mas não posso chamá-los a mesma coisa,
e parece que vou ter que copiar isso,
então deixe-me dizer que estas serão as variáveis ​​de Davi,
e deixe-me algumas cópias destes para o Rob.
Vamos chamar essas Rob, mas isso não vai funcionar agora
porque eu, espere, vamos mudar-me para id1, name1 e house1.
Rob será de 2, 2.
Eu tenho que mudar isso aqui, aqui, aqui, aqui, aqui, aqui.
Espere, o que acontece com Tommy? Vamos fazer isso de novo.
Obviamente, se você ainda acha que isso é uma boa maneira de fazer isso, não é,
para copiar / colar ruim.
Mas nós resolvemos isso há uma semana.
>> Qual foi a nossa solução, quando queria ter várias instâncias do mesmo tipo de dados?
[Os alunos] Uma matriz.
Uma matriz, então deixe-me tentar limpar isso.
Deixe-me fazer algumas para mim mesmo no topo, e deixe-me em vez fazer isso aqui.
Vamos chamar essas pessoas, e ao invés disso eu vou dizer "ids int",
e eu estou indo para suportar 3 de nós agora.
Eu vou dizer "nomes de cadeia", e eu vou apoiá-3 de nós,
e então eu vou dizer "casas seqüência," e eu vou apoiar a 3.
Agora aqui em lugar de Davi recebendo suas próprias variáveis ​​locais
podemos nos livrar deles.
Isso é bom que estamos limpar isso.
Posso, então, dizer que David vai ser [0] e nomes [0]
e casas [0].
E, em seguida, Rob podemos igualmente economizar no presente.
Vamos colocar isso aqui, então ele vai ser arbitrariamente ids [1].
Ele vai ser nomes [1],
e, em seguida, finalmente, casas [1].
>> Ainda um pouco entediante, e agora eu tenho que descobrir isso,
então vamos dizer "nomes [0], id [0], casas [0],
e vamos pluralizar isso.
Ids, ids, ids.
E novamente, eu estou fazendo isso, por isso novamente, eu já estou recorrendo para copiar / colar de novo,
assim as probabilidades são de que há uma outra solução aqui.
Eu provavelmente pode limpar isso ainda mais com um laço ou algo assim,
Então, em suma, é um pouco melhor, mas ainda se sente como
Estou recorrendo para copiar / colar, mas mesmo isso, eu afirmo,
não é realmente a solução certa fundamentalmente porque
E se algum dia decidirmos que você sabe o que?
Realmente deve ter sido armazenar endereços de e-mail para David e Rob
e todos os outros neste programa.
Devemos também armazenar números de telefone.
Devemos também armazenar números de contato de emergência.
Nós temos todas essas peças de dados que deseja armazenar,
então como você vai fazer sobre isso?
>> Você declara uma outra matriz, na parte superior, e então você adicionar manualmente
um endereço de e-mail [0] endereço, e-mail [1]
para David e Rob e assim por diante.
Mas há realmente apenas uma suposição subjacente a este projeto
que eu estou usando o sistema de honra saber que
[I] em cada um dos vários arrays
Acontece para se referir à mesma pessoa,
assim [0] no IDS é o número 123,
e eu vou assumir que os nomes [0]
é o nome da mesma pessoa e casas [0]
é casa da mesma pessoa e assim por diante para todas as matrizes diferentes que crio.
Mas note que não há nenhuma ligação fundamentais
entre essas três peças de informação, identificação, nome e casa,
mesmo que a entidade que estamos tentando modelo neste programa não é matrizes.
Matrizes são exatamente dessa forma programática de fazer isso.
O que realmente queremos para modelar em nosso programa é uma pessoa
como Davi, uma pessoa como Rob dentro do qual
ou encapsulamento é um nome e ID e uma casa.
>> Será que podemos expressar essa idéia de encapsulamento
pelo qual uma pessoa tem um ID, um nome e uma casa
e não recorrer a este truque realmente qual nós apenas
confiar que algo suporte
refere-se a uma mesma pessoa humana em cada uma dessas matrizes diferentes?
Nós podemos realmente fazer isso.
Deixe-me ir acima principal para agora, e deixe-me criar o meu próprio tipo de dados
para realmente pela primeira vez.
Usamos esta técnica em Scramble,
mas aqui eu estou indo para ir em frente e criar um tipo de dados,
e você sabe, eu vou chamá-lo de estudante ou pessoa,
e eu vou usar typedef para definir um tipo.
Eu vou dizer que esta é uma estrutura,
e então esta estrutura vai ser de estudante tipo, vamos dizer,
mesmo que seja um pouco datado agora para mim.
Nós vamos dizer "int id".
Nós vamos dizer "nome de cadeia."
Então, vamos dizer "casa corda",
agora até o final de estas poucas linhas de código
Acabo ensinou bumbum que não existe
um tipo de dados além de ints, além de cordas, além de duplas, além de carros alegóricos.
>> A partir deste momento, em vez da linha 11, existe agora um novo tipo de dados chamado estudantes,
e agora eu posso declarar uma variável aluno em qualquer lugar que eu quero,
então deixe-me ir até aqui para as pessoas.
Agora eu posso me livrar disso, e eu posso ir de volta para David aqui,
e para David eu posso realmente dizer que David,
podemos literalmente nomear a variável depois de mim,
vai ser de estudante tipo.
Isso pode parecer um pouco estranho, mas isto não é assim tão diferente
de declarar algo como um int ou uma string ou uma bóia.
Isso só acontece a ser chamado de estudante,
e se eu quiser colocar algo dentro desta estrutura
Eu agora tenho que usar uma nova peça de sintaxe, mas é bastante simples,
david.id = 123, david.name = "David" na capital D,
e david.house = "Mather,"
e agora eu posso me livrar dessas coisas aqui.
Repare que temos agora redesenhado nosso programa em realmente uma maneira muito melhor
em que agora o nosso programa espelha o mundo real.
>> Há uma noção do mundo real de uma pessoa ou um estudante.
Aqui nós temos agora uma versão C de uma pessoa ou, mais especificamente, um estudante.
Dentro dessa pessoa são essas características relevantes,
ID, nome e casa, por isso Rob torna-se essencialmente a mesma coisa aqui,
então estudante Rob, e agora rob.id = 456,
rob.name = "Rob".
O fato de que a variável é chamado Rob é uma espécie de sentido.
Poderíamos ter chamado x ou y ou z.
Nós só nomeou Rob para ser semanticamente consistente,
mas realmente o nome está dentro do próprio campo,
então agora eu tenho isso.
Isso também não se sente como o melhor projeto em que eu codificado David.
Eu codificado Rob.
E eu ainda tenho que recorrer a algum copiar e colar cada vez que eu quero novas variáveis.
Além disso, eu tenho que dar, aparentemente, cada uma dessas variáveis ​​de um nome,
mesmo que eu prefiro descrever essas variáveis
alunos mais genericamente como.
>> Agora podemos mesclar as ideias que têm vindo a trabalhar bem para nós
e, em vez dizer: "Você sabe o que, dá-me um estudantes variável chamada,
e vamos ter que ser de tamanho 3 ", então agora eu posso refinar este ainda mais,
livrar-se do David manualmente declarou,
e eu posso dizer alguma coisa em vez como estudantes [0] aqui.
Posso, então, dizer que os alunos [0] aqui,
alunos [0] aqui, e assim por diante, e eu posso sair por aí
e limpar isso para Rob.
Eu também poderia ir sobre agora talvez adicionando um loop
e usando GetString e GetInt para realmente obter esses valores do usuário.
Eu poderia ir sobre como adicionar uma constante, porque esta é geralmente má prática
rígido código algum número arbitrário como 3 aqui
e lembre-se que você deve colocar mais de 3 alunos na mesma.
Provavelmente seria melhor usar # define no topo do meu arquivo
e fator que fora, assim, de fato, deixe-me ir em frente e generalizar isso.
>> Deixe-me abrir um exemplo que está entre os de hoje
exemplos de antecedência, structs1.
Este é um programa mais completo que utiliza # define-se aqui
e diz que vamos ter 3 alunos por padrão.
Aqui eu estou declarando um valor classe de estudantes,
para uma sala de aula de alunos, e agora estou usando um loop
apenas para tornar o código um pouco mais elegante, preencher a classe
com a entrada do usuário, de modo iterar a partir de i = 0 em cima para os alunos, que é 3.
E então eu solicitar que o usuário nesta versão
o que é o ID do aluno, e eu fico com GetInt.
Qual é o nome do aluno, e então eu começo com GetString.
O que é a casa do aluno? Recebo-o com GetString.
E então no fundo aqui, eu simplesmente decidi mudar
como eu estou imprimindo estes para fora e realmente usar um loop,
E quem sou eu imprimir?
De acordo com o comentário que eu estou imprimindo qualquer um em Mather,
e é isso para Rob e Tommy e assim por diante, na verdade Tommy em Mather.
Tommy e David seria impresso no caso, mas como é que isto funciona?
Nós não vimos essa função antes, mas dar um palpite sobre o que isso faz.
Compara strings.
>> É um pouco não-óbvio como ele se compara cordas pois verifica-se
se ele retorna 0 que significa que as cordas são iguais.
Se ela retorna a -1 que significa um vem antes do outro em ordem alfabética,
e se ele retorna um que significa a palavra outro vem em ordem alfabética
antes do outro, e você pode procurar on-line ou na página do homem
para ver exatamente qual é qual, mas tudo isso está fazendo agora é que está dizendo
se o [i]. casa é igual a "Mather"
então vá em frente e imprimir assim e assim é em Mather.
Mas aqui está algo que não tenha visto antes, e nós vamos voltar a este.
Não me lembro de alguma vez ter que fazer isso em qualquer um dos meus programas.
Livre é, aparentemente referindo-se a memória, liberando memória,
mas o que a memória aparentemente estou liberando neste loop na parte inferior do programa?
Parece que eu estou liberando nome de uma pessoa
e da casa de uma pessoa, mas por que isso?
>> Acontece que todas essas semanas que você está usando GetString
temos vindo a introduzir tipo de um bug em cada um de seus programas.
GetString pela memória aloca projeto para que ele possa retornar a você uma string,
como Davi, ou Rob, e então você pode fazer o que quiser
com essa seqüência em seu programa porque temos a memória reservada para você.
O problema é todo esse tempo a cada vez que você chamar GetString
nós, os autores de GetString, têm vindo a pedir o sistema operacional
para nos dar um pouco de memória RAM para esta cadeia.
Dê-nos um pouco de memória RAM para esta próxima corda.
Dê-nos um pouco mais de memória RAM para essa seqüência seguinte.
O que você, programador, nunca foram fazendo
está nos dando de volta a memória,
assim para estas várias semanas todos os programas que você escreveu
ter o que é chamado um salto de memória em que eles continuam usando
mais memória e mais a cada vez que você chamar GetString, e isso é bom.
Nós deliberadamente fazer isso nas primeiras semanas, porque não é tão interessante
ter que se preocupar com onde a corda está vindo.
Tudo que você quer é a palavra Rob para voltar quando o usuário digita-lo dentro
>> Mas avançar agora temos de começar a ficar mais sofisticada sobre isso.
A qualquer momento que alocar memória é melhor, eventualmente, entregá-lo de volta.
Caso contrário, no mundo real no seu Mac ou PC, você pode ter ocasionalmente experiente
sintomas onde o computador está a ponto de paralisar eventualmente
ou a bola de praia estúpido fiação está apenas ocupando o do computador
toda a atenção e você não pode fazer as coisas.
Isso pode ser explicado por uma série de bugs, mas entre os possíveis erros
são coisas chamadas vazamentos de memória em que alguém que escreveu esse pedaço de software
que você está usando não se lembrar de memória livre
que ele ou ela perguntou o sistema operacional para,
não usar GetString, porque isso é uma coisa CS50, mas usando funções similares
que pedem o sistema operacional para a memória.
Se você ou estragar e nunca realmente voltar que a memória
um sintoma de que pode ser um programa que retarda e reduz e retarda
a menos que você se lembrar de chamar livre.
>> Nós vamos voltar para quando e por que você chamaria de livre,
mas vamos em frente apenas para uma boa medida e tente executar este programa em particular.
Isto foi chamado structs1, entrar.
Deixe-me ir em frente e correr structs1, 123, David Mather,
456, Rob Kirkland, 789,
Tommy Mather, e vemos Davi em Mather, Tommy em Mather.
Este é apenas um teste de sanidade de que o programa está funcionando.
Agora, infelizmente, este programa é um pouco frustrante, em que
Eu fiz todo esse trabalho, eu digitei em nove diferentes seqüências, aperte enter,
foi dito que estava em Mather, mas, obviamente, eu sabia que estava em Mather, porque eu já digitou.
Seria bom se, pelo menos, este programa é mais como um banco de dados
e ele realmente se lembra do que eu ter digitado
então eu nunca mais ter de introduzir estes registros dos alunos.
Talvez seja como um sistema registrarial.
>> Podemos fazer isso usando esta técnica conhecida como arquivo de entrada de arquivo I / O, e de saída,
uma forma muito genérica de dizer qualquer momento que você quer ler arquivos ou escrever arquivos
você pode fazer isso com um determinado conjunto de funções.
Deixe-me ir em frente e abrir este structs2.c exemplo,
que é quase idêntico, mas vamos ver o que ele faz agora.
No topo do arquivo eu declaro uma classe de alunos.
Eu, então, preencher a classe com a entrada do usuário,
para as linhas de código são exatamente como antes.
Então, se eu rolar aqui eu imprimir todos os que estão em Mather arbitrariamente como antes,
mas esta é uma novidade interessante.
Estas linhas de código são novos, e eles introduzem algo aqui,
Arquivo, todas as tampas, e tem * aqui também.
Deixe-me passar isso aqui, a * por aqui também.
>> Esta função não vimos antes, fopen,
mas significa arquivo aberto, então vamos percorrer estes,
e isso é algo que nós vamos voltar a Série de Exercícios no futuro,
mas esta linha aqui, essencialmente, abre um arquivo chamado banco de dados,
e especificamente abre-a de tal forma que ele pode fazer o que com ele?
[Inaudível-aluno]
Certo, então "w" significa apenas que ele está dizendo o sistema operacional
abrir este arquivo de tal forma que eu possa escrever para ele.
Eu não quero lê-lo. Eu não quero só olhar para ele.
Eu quero mudar isso e adicionar coisas potencialmente a ele,
eo arquivo vai ser chamado de banco de dados.
Isto poderia ser chamado nada.
Isto poderia ser database.txt. Isto poderia ser. Db.
Esta poderia ser uma palavra como tal, mas eu arbitrariamente escolheu o nome do banco de dados de arquivo.
Este é um teste de sanidade de que vamos voltar a em grande detalhe ao longo do tempo,
se fp, para ponteiro de arquivo, não NULL igual significa que tudo está bem.
>> Longa história curta, funções como fopen às vezes falham.
Talvez o arquivo não existe. Talvez você esteja fora do espaço de disco.
Talvez você não tem permissão para essa pasta,
por isso, se fopen retorna algo nulo de ruim aconteceu.
Por outro lado, se fopen não retornar nulo tudo está bem
e eu posso começar a escrever para este arquivo.
Aqui está um truque novo.
Este é um loop de que está interagindo sobre cada um dos meus alunos,
e isso parece tão semelhante ao que fizemos antes,
mas esta função é um primo do printf chamado fprintf para arquivo printf,
e perceber que é diferente em apenas dois caminhos.
Um deles, que começa com f em vez de p,
mas então seu primeiro argumento é aparentemente o que?
[Os alunos] do arquivo. >> É um arquivo.
Essa coisa chamada fp, que vai finalmente destrinçar o que é um ponteiro de arquivo,
mas por agora fp simplesmente representa o arquivo que eu abri,
fprintf assim aqui está dizendo imprimir ID do usuário para o arquivo, não para a tela.
Imprimir o nome do usuário para o arquivo, e não para a tela,
a casa para o arquivo, e não para a tela, e depois para baixo aqui, obviamente,
feche o arquivo, e depois para baixo aqui livre da memória.
>> A única diferença entre esta versão ea versão 2 1
é a introdução de fopen e este arquivo com *
e essa noção de fprintf, então vamos ver o que o resultado final é.
Deixe-me ir para a minha janela de terminal.
Deixa-me correr structs2, entrar.
Parece que tudo está bem. Vamos executar novamente structs2.
123, David Mather, 456, Rob Kirkland,
789, Tommy Mather, entrar.
Parece que ele se comportou o mesmo, mas se eu faço agora ls
perceber o que está no arquivo aqui entre todo o meu código, banco de dados,
então vamos abrir esse, olhar gedit de banco de dados, e para isso.
Não é o mais sexy de formatos de arquivo.
É realmente um pedaço de linha de dados por linha por linha,
mas aqueles de vocês que usam arquivos do Excel ou CSV, valores separados por vírgula,
Eu certamente poderia ter usado fprintf ao invés talvez fazer algo assim
para que eu pudesse realmente criar o equivalente a um arquivo do Excel
separando as coisas com vírgulas, e não apenas as novas linhas.
>> Neste caso, se eu tivesse usado em vez vírgulas em vez de novas linhas
Eu poderia literalmente abrir este arquivo de banco de dados no Excel, se eu, em vez fez parecer assim.
Em suma, agora que temos o poder de gravar arquivos
agora podemos começar a persistência de dados, mantendo-a em torno de disco
para que possamos manter as informações de novo e de novo.
Observe um par de outras coisas que são agora um pouco mais familiar.
No topo deste arquivo C temos um typedef
porque queríamos criar um tipo de dados que representa uma palavra,
de modo que este tipo é chamado de palavra, e dentro desta estrutura
é um pouco amador agora.
Porque é uma palavra composta de, aparentemente, uma matriz?
O que é uma palavra apenas de forma intuitiva?
>> É uma matriz de caracteres.
É uma sequência de caracteres de costas para trás.
Letras em todas as tampas acontece de ser nós arbitrariamente dizer o comprimento máximo
de qualquer palavra no dicionário que estamos usando para Scramble.
Por que eu tenho um 1?
O personagem nulo.
Lembre-se de quando nós fizemos o exemplo Bananagrams precisávamos de um valor especial
no fim da palavra, a fim de manter a par
de onde as palavras realmente acabou, e como a especificação do conjunto de problemas diz
aqui estamos associando com uma determinada palavra um valor booleano,
uma bandeira, por assim dizer, verdadeira ou falsa.
Você já encontrou esta palavra já, porque percebemos
nós realmente precisamos de uma maneira de lembrar não só o que a palavra está no Scramble
mas se está ou não, o ser humano, têm encontrado
de modo que se você não encontrar a palavra "o" você não pode simplesmente digitar o, entra, a, entre, a, insira
e obter 3 pontos, 3 pontos, 3 pontos, 3 pontos.
Queremos ser capazes de barrar essa palavra definindo um bool
a verdade se você já encontrou, e é por isso que nós
encapsulado em sua estrutura.
>> Agora, aqui no Scramble há essa outra struct chamado dicionário.
Ausente aqui é a palavra typedef porque neste caso
precisávamos para encapsular a idéia de um dicionário,
e um dicionário contém um monte de palavras,
como implicado por esta matriz, e quantas dessas palavras estão lá?
Bem, qualquer que seja deste tamanho variável chamada diz.
Mas só precisamos de um dicionário.
Nós não precisamos de um tipo de dados chamado dicionário.
Nós só precisamos de um deles, por isso acaba em C
que, se você não diz typedef, você acabou de dizer struct, em seguida, dentro das chaves
você colocar suas variáveis, então você colocar o nome.
Este é declarar uma variável chamada dicionário
que se parece com isso.
Por outro lado, estas linhas são a criação de uma estrutura de dados reutilizável chamado palavra
que você pode criar várias cópias, assim como nós criamos
várias cópias de alunos.
>> O que isso finalmente permitir que façamos?
Deixe-me voltar para, digamos, um exemplo mais simples a partir de tempos mais simples,
e deixe-me abrir-se, digamos, compare1.c.
O problema aqui em mãos é realmente casca de volta
a camada de uma corda e começar a tirar essas rodinhas
pois verifica-se que uma seqüência de todo esse tempo
é como prometemos na semana 1 apenas um apelido,
um sinônimo da biblioteca CS50 por algo que parece um pouco mais crítico,
char *, e vimos essa estrela antes.
Vimo-lo no contexto de arquivos.
>> Vamos ver agora porque estamos escondendo esse detalhe já há algum tempo.
Aqui está um arquivo chamado compare1.c,
e, aparentemente, pede ao usuário para duas cordas, s e t,
e então ele tenta comparar essas cordas de igualdade na linha 26,
e se eles são iguais ele diz: "Você digitou a mesma coisa",
e se eles não são iguais ele diz: "Você digitou coisas diferentes."
Deixe-me ir em frente e executar este programa.
Deixe-me ir para o meu diretório de origem, fazer uma compare1. Ele compilou tudo bem.
Deixa-me correr compare1.
Eu vou aumentar o zoom, entrar.
Diga alguma coisa. OLÁ.
Eu vou dizer algo de novo. OLÁ.
Eu definitivamente não escreva coisas diferentes.
>> Deixe-me tentar de novo. BYE BYE.
Definitivamente não é diferente, por isso o que está acontecendo aqui?
Bem, o que realmente está sendo comparado na linha 26?
[Inaudível-aluno]
Sim, então verifica-se que uma string, tipo de dados, é um tipo de mentira.
Uma string é um char *, mas o que é um char *?
A * char, como eles dizem, é um ponteiro,
e um ponteiro é efetivamente um endereço,
soma um local na memória, e se acontecer de você ter digitado uma palavra como OLÁ,
lembro de discussões passadas de cordas
isto é como a palavra OLÁ.
Lembre-se que uma palavra como OLÁ pode ser representado
como uma matriz de caracteres como esta
e depois com um caractere especial no final chamou o caractere nulo,
como o denota \.
O que é realmente uma cadeia?
Note-se que isto é vários pedaços de memória,
e, de fato, o fim do que é conhecido somente quando você olhar através de toda a cadeia
olhando para o caractere nulo especial.
Mas se este é um pedaço da memória da memória do meu computador,
vamos arbitrariamente dizer que essa seqüência de apenas teve sorte,
e ele foi colocado no início de RAM do meu computador.
Este é o byte 0, 1, 2, 3, 4, 5, 6 ...
>> Quando eu digo algo como GetString e eu string s = GetString
o que realmente está sendo devolvido?
Para estas últimas semanas, o que realmente está sendo armazenado em s
não é essa seqüência de per se, mas neste caso o que está sendo armazenado é
o número 0, porque o que realmente faz GetString
é que fisicamente não retornar uma string.
Que nem sequer realmente faz sentido conceitual.
O que ele faz de retorno é um número.
Esse número é o endereço da OLÁ na memória,
e string s, em seguida, se descascar esta camada, cadeia não existe realmente.
É apenas uma simplificação na biblioteca CS50.
>> Isso realmente é algo chamado char *.
Char faz sentido, porque o que é uma palavra, como OLÁ?
Bem, é uma série de caracteres, uma série de personagens.
Char * significa que o endereço de um personagem,
Então, o que isso significa para retornar uma string?
Uma forma agradável, simples de retornar uma string
é melhor do que tentar descobrir como eu voltar para 5 ou 6 bytes diferentes
deixe-me voltar para o endereço que byte?
O primeiro.
Em outras palavras, deixe-me dar-lhe o endereço de um personagem na memória.
Isso é o que representa char *, o endereço de um único caractere na memória.
Chame isso é variável.
Loja em s que determinado endereço, o que eu disse é arbitrariamente 0,
apenas para manter as coisas simples, mas na realidade ele é geralmente um número maior.
>> Espere um minuto.
Se você só está me dando o endereço do primeiro caractere, como eu sei que o endereço é
do segundo personagem, o terceiro, o quarto eo quinto?
[Inaudível-aluno]
Você só sabe que o fim da seqüência é por meio deste truque prático,
Então, quando você usar algo como printf, o que printf literalmente toma como argumento,
Recordamos que usamos este espaço reservado% s, e então você passa
a variável que está armazenando uma string.
O que realmente está passando é o endereço do primeiro caractere dessa seqüência.
Printf então usa um laço ou um loop while, ao receber esse endereço,
por exemplo, 0, então deixe-me fazer isso agora,
printf ("% s \ n", s);
Quando eu chamo printf ("% s \ n", s), o que eu realmente estou fornecendo printf com
é o endereço do primeiro caracter em s, o qual, neste caso, é arbitrária H.
>> Como se sabe exatamente o que printf para exibir na tela?
A pessoa que implementou printf implementou um loop while ou um loop
que diz que este personagem igualar o caractere nulo especial?
Se não, imprimi-lo. Que tal um presente?
Se não imprimi-lo, imprimi-lo, imprimi-lo, imprimi-lo.
Oh, este é especial. Interromper a impressão e retornar para o utilizador.
E isso é, literalmente, tudo o que está acontecendo debaixo do capô,
e isso é muita coisa para digerir, no primeiro dia de uma classe,
mas por agora é realmente o alicerce de tudo compreensão
que está acontecendo dentro da memória do nosso computador,
e, finalmente, nós vamos provocar este apart com uma pequena ajuda
de um de nossos amigos em Stanford.
>> Professor Nick Parlante em Stanford fez esta seqüência maravilhoso vídeo
de todos os tipos de línguas diferentes que introduziram
Binky este pequeno personagem Claymation.
A voz que você está prestes a ouvir em apenas alguns prévia segunda
é a de um professor de Stanford, e você está ficando
apenas 5 ou 6 segundos de isso agora,
mas esta é a nota em que vamos concluir hoje
e começar na quarta-feira.
Eu dar-lhe Fun Pointer com Binky, a visualização.
[♪ ♪ Música] [Professor Parlante] Ei, Binky.
Acordar. É hora de diversão ponteiro.
[Binky] O que é isso? Saiba mais sobre ponteiros?
Ah, bom!
>> Vamos vê-lo na quarta-feira.
[CS50.TV]