[Powered by Google Translate] [Review] [0 Quiz]
>> [Lexi Ross, Tommy MacWilliam, Lucas Freitas, José Ong] [Harvard University]
>> [Esta é CS50.] [CS50.TV]
>> Ei, todo mundo.
Bem-vindo à sessão de revisão para Quiz 0, o que está a ter lugar esta quarta-feira.
O que vamos fazer hoje à noite, eu estou com três TFs outros,
e juntos vamos passar por uma revisão do que fizemos no curso até o momento.
Não vai ser 100% completa, mas deve dar-lhe uma idéia melhor
do que você já tem para baixo e que você ainda precisa estudar antes de quarta-feira.
E sinta-se livre para levantar a mão com perguntas como estamos indo,
mas tenha em mente que nós também vamos ter um pouco de tempo no fim-
se acabar com alguns minutos de sobra para fazer perguntas gerais,
de modo manter isso em mente, e por isso estamos indo para começar no início com a Semana 0.
>> [Questionário 0 comentário!] [Parte 0] [Lexi Ross] Mas antes de fazer isso, vamos falar sobre
a logística do quiz.
>> [Logística] [quiz ocorre na quarta-feira 10/10, em vez da palestra]
>> [(Veja http://cdn.cs50.net/2012/fall/quizzes/0/about0.pdf para mais detalhes)] É quarta-feira, 10 de outubro.
>> Isso é nesta quarta-feira, e se você vai para este URL aqui,
que também é acessível a partir de CS50.net-há um link para ele-
você pode ver informações sobre onde ir com base em
seu sobrenome ou filiação escola, bem como
fala sobre exatamente o que o teste irá cobrir e os tipos de perguntas que você vai conseguir.
Tenha em mente que você também vai ter a oportunidade de rever para responder ao teste na seção,
para que seus TFs deve ir sobre alguns problemas da prática,
e essa é outra boa chance de ver onde você ainda precisa estudar para o quiz.
Vamos começar no início com Bytes 'n' bits.
Lembre-se um pouco é apenas um 0 ou um 1,
e um byte é uma coleção de oito desses bits.
Vamos olhar para esta coleção de bits aqui.
Devemos ser capazes de descobrir quantos bits existem.
Onde contamos há apenas 8 deles, oito 0 ou 1 unidades.
E desde há 8 bits, que é 1 byte,
e vamos convertê-lo em hexadecimal.
Hexadecimal é base 16, e é muito fácil de se converter
um número em binário, que é o que é, para um número em hexadecimal.
Tudo o que fazemos é olhar para grupos de 4,
e convertê-los para o dígito hexadecimal apropriado.
Começamos com o grupo mais à direita de 4, portanto, 0011.
Isso vai ser um 1 e um 2, para juntos, que faz 3.
E então, vamos olhar para o outro bloco de 4.
1101. Isso vai ser um 1, um 4, e um 8.
Juntos que vai ser 13, o que torna D.
E vamos lembrar que em hexadecimal que não basta ir de 0 a 9.
Vamos 0 a F, então depois de 9, 10 corresponde a A,
11 a B, et cetera, onde F é 15.
Aqui 13 é um D,
de modo a convertê-lo para decimal tudo o que fazemos é realmente
tratar cada posição como uma potência de 2.
Isso é um 1, um 2, zero 4s, zero 8s, uma 16, et cetera,
e é um pouco difícil de calcular em sua cabeça, mas se formos para o próximo slide
podemos ver a resposta para isso.
>> Essencialmente nós estamos indo em frente de volta para a esquerda,
e nós estamos multiplicando cada dígito pela potência correspondente de 2.
E lembre-se, para hexadecimal denotamos estes números com 0x no início
para que não se confunda com um número decimal.
Continuando, esta é uma tabela ASCII,
eo que nós usamos ASCII para é mapear a partir de caracteres para valores numéricos.
Lembre-se no pset criptografia que fez uso extensivo da tabela ASCII
a fim de utilizar vários métodos de criptografia,
o César e a cifra de Vigenère, para converter letras diferentes
em uma string de acordo com a chave dada pelo usuário.
Vamos olhar um pouco de matemática ASCII.
Olhando para 'P' + 1, na forma de caracteres, que seria Q,
e lembre-se que '5 '≠ 5.
E como exatamente podemos converter entre essas duas formas?
Não é realmente muito difícil.
A fim de obter 5 subtraímos '0 '
porque há cinco lugares entre o '0 'eo '5'.
A fim de ir por outro caminho que acabamos de adicionar a 0,
por isso é uma espécie de como aritmética regular.
Basta lembrar que quando algo tem aspas em torno dele é um personagem
e, portanto, corresponde a um valor na tabela ASCII.
Movendo-se para temas mais gerais da ciência de computadores.
Aprendemos que um algoritmo é e como usar a programação
para implementar algoritmos.
Alguns exemplos de algoritmos são algo realmente simples como
verificar se um número é par ou ímpar.
Para que lembrar que mod o número por 2 e verificar se o resultado é 0.
Se assim for, é mesmo. Se não, é estranho.
E isso é um exemplo de um algoritmo muito básico.
>> Um pouco de um mais um envolvido é de busca binária,
que nós falaremos sobre mais tarde na sessão de revisão.
E a programação é o termo que usamos para tomar um algoritmo
e convertê-lo para codificar o computador possa ler.
2 exemplos de programação Scratch,
que é o que nós fizemos na Semana 0.
Mesmo que nós realmente não digitar o código é uma forma de implementar
Nesse algoritmo, o qual está a imprimir os números 1-10,
e aqui podemos fazer o mesmo na linguagem de programação C.
Estes são funcionalmente equivalentes, apenas escrito em diferentes línguas ou de sintaxe.
Em seguida, aprendeu sobre expressões booleanas,
e um booleano é um valor que é verdadeiro ou falso,
e expressões aqui muitas vezes booleanos
ir para dentro de condições, por isso, se (x ≤ 5),
bem, nós já definido x = 5, de modo que condição vai avaliar para true.
E se é verdade, qualquer código que está abaixo da condição
vai ser avaliada pelo computador, de modo que a corda que vai ser impresso
para a saída padrão, ea condição prazo
refere-se a tudo o que está dentro dos parênteses da declaração se.
Lembre-se de todos os operadores.
Lembre-se de && e | | quando estamos tentando combinar duas ou mais condições,
= Não == para verificar se duas coisas são iguais.
Lembre-se que é = para atribuição enquanto == é um operador booleano.
≤, ≥ e depois o final 2 são auto-explicativos.
Uma revisão geral da lógica booleana aqui.
E expressões booleanas também são importantes em loops,
que nós vamos passar por cima agora.
Nós aprendemos sobre três tipos de loops até agora em CS50, por enquanto, e fazer enquanto.
E é importante saber que, embora para a maioria dos fins
nós podemos realmente usar qualquer tipo de loop geralmente
existem certos tipos de propósitos ou padrões comuns
na programação que, especificamente, chamar para um desses laços
que tornam o. mais eficiente ou elegante para codificá-lo dessa forma
Vamos falar sobre o que cada um desses ciclos tende a ser usado para mais freqüência.
>> Em um loop que geralmente já sabe quantas vezes queremos interagir.
Isso é o que nós colocamos na condição.
Para i = 0, i <10, por exemplo.
Nós já sabemos que queremos fazer algo 10 vezes.
Agora, para um loop while, geralmente não necessariamente
Sabe quantas vezes queremos que o laço seja executado.
Mas nós sabemos que algum tipo de condição que nós queremos que ele
sempre ser verdadeiro ou ser sempre falso.
Por exemplo, enquanto que é definido.
Vamos dizer que é uma variável booleana.
Enquanto isso é verdade que queremos o código para avaliar,
assim um pouco mais extensível, um pouco mais geral do que um loop,
mas nenhum por laço pode também ser convertido a um loop.
Finalmente, fazer loops while, que pode ser o mais complicado de compreender de imediato,
são usados ​​frequentemente quando queremos avaliar o primeiro código
antes da primeira vez que verificar a condição.
Um caso de uso comum para um fazer loop while
é quando você deseja obter a entrada do usuário, e você sabe que você quer perguntar ao usuário
para a entrada de pelo menos uma vez, mas se eles não dão a você uma boa entrada de imediato
você quer continuar fazendo até que eles dão-lhe a boa entrada.
Esse é o uso mais comum de um loop Do While,
e vamos olhar para a estrutura real de estes laços.
Eles normalmente sempre tendem a seguir esses padrões.
>> No laço para dentro de você ter 3 componentes:
inicialização, tipicamente algo como int i = 0, onde i é o contador,
condição, onde nós queremos dizer para executar este ciclo enquanto a essa condição ainda permanece,
como i <10, e depois, finalmente, atualização, que é como incrementar
a variável de contador em cada ponto do ciclo.
Uma coisa comum para ver que há é apenas i + +,
o que significa incrementar i por uma de cada vez.
Você também pode fazer algo como i + = 2,
o que significa adicionar 2 a i cada vez que você passar pelo loop.
E então a fazer isso apenas se refere a qualquer código que realmente é executado como parte do ciclo.
E para um loop while, desta vez nós realmente temos a inicialização fora do circuito,
assim, por exemplo, vamos dizer que estamos a tentar fazer o mesmo tipo de loop como acabei de descrever.
Diríamos int i = 0 antes do laço começa.
Então poderíamos dizer enquanto i <10 fazer isso,
assim o mesmo bloco de código como antes,
e desta vez a parte de atualização do código, por exemplo, i + +,
realmente vai dentro do loop.
E, finalmente, para um fazer enquanto, é semelhante ao do loop while,
mas temos que lembrar que o código irá avaliar uma vez
antes a condição é verificada, por isso faz muito mais sentido
se você olhar para ele, a fim de cima para baixo.
Em um, fazer enquanto o código loop avalia antes mesmo de olhar para a condição, enquanto
enquanto que um loop while, ele verifica primeiro.
Demonstrações e variáveis.
Quando queremos criar uma nova variável que primeiro pretende para o inicializar.
>> Por exemplo, a barra int inicializa a barra variável,
mas não dar-lhe um valor, então o que é o valor bar agora?
Nós não sabemos.
Pode ser um valor de lixo que foi previamente armazenado na memória de lá,
e nós não queremos usar essa variável
até que, na verdade, dar-lhe um valor,
para que declará-lo aqui.
Em seguida, inicializar para ser 42 abaixo.
Agora, é claro, sabemos que isso pode ser feito em uma única linha, bar int = 42.
Mas só para ficar claro as várias etapas que estão em curso,
a declaração e inicialização estão acontecendo separadamente aqui.
Isso acontece em uma única etapa, e na próxima, int baz = bar + 1,
esta declaração abaixo, que baz incrementos, para que no final do bloco de código
se fôssemos para imprimir o valor de baz seria 44
porque declarar e inicializar que seja uma barra de>,
e então incrementá-lo mais uma vez com o + +.
Nós fomos sobre isso brevemente bonito, mas é bom ter um general
compreensão do que tópicos e eventos são.
Nós principalmente, fez isso em Scratch,
para que você possa pensar em tópicos como várias seqüências de código
executando ao mesmo tempo.
Na verdade, ele provavelmente não está funcionando, ao mesmo tempo,
mas uma espécie de abstratamente podemos pensar nisso dessa forma.
>> No Scratch, por exemplo, tivemos os vários sprites.
Poderia ser de execução de código diferentes ao mesmo tempo.
Um deles poderia ser a pé, enquanto o outro está dizendo algo
em uma parte diferente da tela.
Os eventos são uma outra maneira de separar a lógica
entre os diferentes elementos do seu código,
e em Scratch fomos capazes de simular eventos usando o Broadcast,
e que é, na verdade, quando eu receber, não quando eu ouço,
mas, essencialmente, é uma forma de transmitir informações
a partir de um sprite para o outro.
Por exemplo, você pode querer transmitir ao longo do jogo,
e quando outro sprite recebe ao longo do jogo,
ele responde de uma certa maneira.
É um modelo importante para compreender para a programação.
Só para ir durante a semana básica 0, o que já sabemos, até agora,
vamos olhar para este programa C simples.
O texto pode ser um pouco pequeno, a partir daqui, mas eu vou passar por isso muito rápido.
Estamos incluindo dois arquivos de cabeçalho no topo, cs50.h e stdio.h.
Estamos então a definição de um limite constante chamado a ser 100.
Estamos em seguida, implementar a nossa função principal.
Uma vez que não usar argumentos de linha de comando aqui, precisamos colocar vazio
como os argumentos para principal.
Vemos int acima principal. Esse é o tipo de retorno, portanto, retornar 0 na parte inferior.
E estamos usando CS50 função de biblioteca obter int
para pedir ao usuário para a entrada, e armazená-lo nesta variável x,
Assim, declaramos x acima, e inicializá-lo com x = GetInt.
>> Em seguida, verifique se o usuário nos deu uma boa entrada.
Se é LIMITE ≥ queremos retornar um código de erro de 1 e imprimir uma mensagem de erro.
E, finalmente, a entrada se o usuário tem nos dado boa
vamos fazer a quadratura do número e imprima o resultado.
Só para ter certeza de que aqueles casa hit todos
você pode ver os rótulos de diferentes partes do código aqui.
Mencionei constantes, arquivos de cabeçalho.
Oh, int x. Certifique-se de lembrar que é uma variável local.
Isso contrasta de uma variável global, o que nós vamos falar sobre
um pouco mais tarde na sessão de revisão,
e estamos chamando a função de biblioteca printf,
Portanto, se não havia incluído o arquivo de cabeçalho stdio.h
não seria capaz de chamar printf.
E acredito que a seta que foi cortada aqui está apontando para o% d,
que é uma cadeia de formatação no printf.
Diz imprimir essa variável como um número% d.
E é isso para a Semana 0.
Agora Lucas vai continuar.
Ei, pessoal. Meu nome é Lucas.
Eu sou um estudante de segundo ano da melhor casa no campus, Mather,
e eu vou falar um pouco sobre a semana 1 e 2,1.
[Semana 1 e 2,1!] [Lucas Freitas]
Como Lexi estava dizendo, quando começamos a traduzir o seu código a partir do zero para C
uma das coisas que percebemos é que você não pode simplesmente
escrever seu código e executá-lo usando uma bandeira verde mais.
Na verdade, você tem que usar algumas medidas para tornar o seu programa C
tornar-se um arquivo executável.
Basicamente o que você faz quando você está escrevendo um programa é que
você traduzir sua idéia em uma linguagem que um compilador pode entender,
Então, quando você está escrevendo um programa em C
o que você está fazendo é realmente escrever algo que o compilador vai entender,
e, em seguida, o compilador vai traduzir esse código
em algo que o computador vai entender.
>> E a coisa é, o seu computador é realmente muito burro.
O seu computador só pode entender 0s e 1s,
Então, na verdade nos primeiros computadores pessoas geralmente programados
usando 0s e 1s, mas não mais, graças a Deus.
Não temos que memorizar seqüências de 0s e 1s
para um loop ou de loop de tempo e assim por diante.
É por isso que temos um compilador.
O que um compilador faz é, basicamente, traduz o código C,
no nosso caso, para uma linguagem que o computador vai entender,
que é o código objeto, eo compilador que estamos usando
é chamado de bumbum, por isso esta é, na verdade, o símbolo para o bumbum.
Quando você tem o seu programa, você tem que fazer duas coisas.
Primeiro, você tem de compilar o seu programa, e então você está indo para executar o seu programa.
Para compilar seu programa que você tem um monte de opções para fazer isso.
O primeiro é fazer program.c bumbum
em qual programa é o nome do seu programa.
Neste caso, você pode ver que eles estão apenas dizendo "Ei, compilar meu programa."
Você não está dizendo "Eu quero este nome para o meu programa", ou qualquer coisa.
>> A segunda opção é dar um nome para o seu programa.
Você pode dizer clang-o e, em seguida, o nome que você quiser
o arquivo executável para ser nomeado como e depois program.c.
E você também pode fazer fazer programa, e ver como nos primeiros dois casos
Eu coloquei. C, e no terceiro eu só tenho programas?
Sim, você realmente não deve colocar. C quando você usa fazer.
Caso contrário, o compilador é, na verdade, vai gritar com você.
E também, eu não sei se vocês lembram,
mas muitas vezes também usamos-lcs50 ou lm.
Isso é chamado de ligação.
Ele apenas informa o compilador que você vai usar essas bibliotecas ali,
por isso, se você quiser usar cs50.h você realmente tem que digitar
clang program.c-lcs50.
Se você não fizer isso, o compilador não vai saber
que você está usando essas funções em cs50.h.
E quando você quer executar o programa você tem duas opções.
Se você fez program.c clang você não dar um nome para o seu programa.
Você tem que executá-lo usando. A.out /.
A.out é um nome padrão que bumbum dá o seu programa se você não dar-lhe um nome.
Caso contrário, você vai fazer. Programa / se você deu um nome para o seu programa,
e também se você fez o nome do programa que o programa vai ficar
já está indo para ser programado o mesmo nome que o arquivo c.
Então nós conversamos sobre os tipos de dados e dados.
>> Basicamente tipos de dados são a mesma coisa que eles usam pequenas caixas
para armazenar valores, por isso os tipos de dados são, na verdade, apenas como Pokémons.
Eles vêm em todos os tamanhos e tipos.
Eu não sei se essa analogia faz sentido.
O tamanho dos dados, na verdade, depende da arquitetura da máquina.
Todos os tamanhos de dados que eu vou mostrar aqui
são, na verdade, para uma máquina de 32 bits, que é o caso do nosso dispositivo,
mas se você está realmente codificação do seu Mac ou do Windows também
Provavelmente você vai ter uma máquina de 64 bits,
para lembrar que os tamanhos de dados que eu vou mostrar aqui
são para a máquina de 32 bits.
O primeiro que vimos foi um int,
que é bastante simples.
Você usa int para armazenar um número inteiro.
Vimos também o caráter, o char.
Se você quiser usar uma carta ou um pequeno símbolo que você provavelmente vai usar um char.
Um char tem 1 byte, o que significa 8 bits, como Lexi disse.
Basicamente, temos uma tabela ASCII que tem 256
combinações possíveis de 0s e 1s,
e então, quando você digitar um caractere que vai traduzir
o caráter que as entradas lhe um número que você tem na tabela ASCII, como Lexi disse.
Temos também a bóia, que usamos para armazenar números decimais.
Se você quer escolher 3,14, por exemplo, você vai usar um flutuador
ou um casal que tem mais precisão.
Uma bóia tem 4 bytes.
A dupla tem 8 bytes, então a única diferença é a precisão.
Temos também um comprimento que é usado para inteiros,
e você pode ver por uma máquina de 32-bit de um int e um long têm o mesmo tamanho,
por isso não faz muito sentido usar um longa em uma máquina de 32 bits.
>> Mas se você estiver usando um computador Mac e 64-bit, na verdade, uma longa tem tamanho 8,
por isso realmente depende da arquitetura.
Para a máquina de 32 bits, não faz sentido usar um longa de verdade.
E, em seguida, um tempo longo, por outro lado, tem 8 bytes,
por isso é muito bom se você quiser ter um número inteiro mais.
E, finalmente, temos string, que é na verdade um char *,
que é um ponteiro para uma char.
É muito fácil pensar que o tamanho da cadeia vai ser como
o número de caracteres que você tem lá,
mas, na verdade, * o char-se
tem o tamanho de um ponteiro para uma char, que é de 4 bytes.
O tamanho de uma char * é 4 bytes.
Não importa se você tem uma pequena palavra ou uma letra ou qualquer coisa.
Vai ser de 4 bytes.
Nós também aprendemos um pouco sobre o elenco,
Então, como você pode ver, se você tiver, por exemplo, um programa que diz
int x = 3 e, em seguida printf ("% d", x / 2)
vocês sabem o que vai imprimir na tela?
>> Alguém? >> [Os alunos] 2.
1. >> 1, sim.
Quando você faz 3/2 vai obter 1,5,
mas já que estamos usando um inteiro que vai ignorar a parte decimal,
e você vai ter um.
Se você não quer que isso aconteça o que você pode fazer, por exemplo,
é declarar um float y = x.
Então x que costumavam ser três agora vai ser 3,000 em y.
E então você pode imprimir o y / 2.
Na verdade, eu deveria ter um 2. lá.
Ele vai fazer 3.00/2.00,
e você está indo para obter 1,5.
E temos essa f 0,2 apenas para pedir 2 unidades decimais da parte decimal.
Se você tem 0,3 f que vai ter, na verdade, 1.500.
Se for 2, vai ser 1,50.
Nós também temos esse caso aqui.
Se você fizer float x = 3,14 e então você x printf
você está indo para obter 3.14.
E se você fizer x = int de x,
o que significa tratar x como um int e imprimir x agora
você vai ter 3,00.
Isso faz sentido?
Porque você é primeiro tratar x como um número inteiro, então você está ignorando a parte decimal,
e então você está imprimindo x.
E, finalmente, você também pode fazer isso,
int x = 65, e então você declarar um char c = x,
e então se você imprimir o c você realmente está indo para obter
Um, então basicamente o que você está fazendo aqui
está traduzindo o inteiro para o personagem,
assim como a tabela ASCII faz.
Também falamos sobre operadores matemáticos.
A maioria deles são bastante simples, de modo +, -, *, /,
e também falamos sobre mod, que é o resto da divisão de dois números.
Se tiver 10% 3, por exemplo,
significa dividir 10 por 3, e que é a parte restante?
Vai ser 1, por isso é realmente muito útil para um monte de programas.
Para Vigenère e César eu tenho certeza que todos vocês utilizado mod.
Sobre operadores matemáticos, ter muito cuidado ao combinar * e /.
>> Por exemplo, se você faz (3/2) * 2 o que você vai conseguir?
[Os alunos] 2.
É, 2, por 3/2 vai ser igual a 1,5,
mas uma vez que você está fazendo operações entre dois números inteiros
na verdade você está indo só para considerar um,
e 1 * 2 vai ser 2, que deve ter muito, muito cuidado
ao fazer aritmética com inteiros porque
você pode ter que 2 = 3, nesse caso.
E também ter muito cuidado com a precedência.
Normalmente deve usar parênteses para ter certeza de que você sabe o que você está fazendo.
Alguns atalhos úteis, é claro, é um i + + ou i + = 1
ou usando + =.
Isso é a mesma coisa que fazer i = i + 1.
Você também pode fazer i - ou i - = 1,
que é a mesma coisa que i = i -1,
algo que vocês usam um monte de loops, pelo menos.
Além disso, para *, se você usar * = e se você, por exemplo,
i * = 2 é a mesma coisa que dizer i = i * 2,
ea mesma coisa para a divisão.
Se você fizer i / = 2 é a mesma coisa que i = i / 2.
>> Agora sobre funções.
Vocês aprenderam que funções são uma estratégia muito boa para salvar código
enquanto você está programando, então se você quiser executar a mesma tarefa
no código de novo e de novo, provavelmente você quiser usar uma função
só assim você não tem que copiar e colar o código uma e outra vez.
Na verdade, a principal é uma função, e quando eu mostrar-lhe o formato de uma função
você vai ver que é bastante óbvio.
Nós também usamos funções de algumas bibliotecas,
por exemplo, printf, Getin, que é a partir da biblioteca de CS50,
e outras funções como toupper.
Todas essas funções são realmente implementadas em outras bibliotecas,
e quando você colocar esses arquivos tether no início de seu programa
você está dizendo que você pode por favor me dar o código para essas funções
então eu não tenho que implementá-las por mim mesmo?
E você também pode escrever suas próprias funções, então quando você começar a programar
você percebe que as bibliotecas não têm todas as funções que você precisa.
Para o pset passado, por exemplo, nós escrevemos desenhar, scramble, e de pesquisa,
e é muito, muito importante para ser capaz de escrever funções
porque eles são úteis, e usá-los o tempo todo na programação,
e ele salva um monte de código.
O formato de uma função é esta.
Temos tipo de retorno no início. Qual é o tipo de retorno?
É apenas quando a função vai retornar.
Se você tem uma função, por exemplo, fatorial,
que se vai calcular uma fatorial de um número inteiro,
provavelmente ele vai retornar um inteiro também.
Em seguida, o tipo de retorno vai ser int.
Printf realmente tem um tipo de retorno void
porque você não está retornando nada.
Você está apenas imprimir coisas na tela
e sair da função depois.
Então você tem o nome da função que você pode escolher.
Você deve ser um pouco razoável, como não escolher um nome como xyz
ou como X2F.
Tente fazer-se um nome que faz sentido.
>> Por exemplo, se é fatorial, dizem fatorial.
Se é uma função que vai desenhar alguma coisa, chame-o desenhar.
E depois temos os parâmetros, que são também chamados de argumentos,
que são como os recursos que a sua função precisa
a partir do seu código para executar sua tarefa.
Se você quiser calcular o fatorial de um número
provavelmente você precisa ter um número para calcular um fatorial.
Um dos argumentos que você vai ter é o próprio número.
E então ele vai fazer algo e retornar o valor no final
a menos que seja uma função void.
Vamos ver um exemplo.
Se eu quiser escrever uma função que soma todos os números em um array de inteiros,
em primeiro lugar, o tipo de retorno vai ser int
porque eu tenho um array de inteiros.
E então eu vou ter o nome da função como sumArray,
e então ele vai levar o próprio array, para nums int
e então o comprimento da matriz, então eu sei quantos números eu tenho que somar.
Então eu tenho que inicializar uma quantia variável chamada, por exemplo, para 0,
e cada vez que vejo um elemento na matriz Devo acrescentar que a soma, então eu fiz um loop.
Assim como disse Lexi, você int i = 0, i comprimento <e i + +.
E para cada elemento da matriz que fiz soma + = nums [i],
e depois voltei a soma, por isso é muito simples, e poupa um monte de código
se você estiver usando esta função um monte de vezes.
Então demos uma olhada em condições.
Temos if, else e else if.
Vamos ver o que é a diferença entre aqueles.
Dê uma olhada nestes dois códigos. Qual é a diferença entre eles?
O primeiro tem, basicamente os códigos quero que você diga
se um número é +, -, ou 0.
O primeiro diz se é> 0, então é positivo.
Se é = a 0, é 0, e se for <0, então é negativo.
>> E o outro está fazendo if, else if, else.
A diferença entre os dois é que este está indo realmente para
verificar se> 0, <0 = 0 ou três vezes,
por isso, se você tem o número 2, por exemplo, ele vai vir aqui e dizer
if (x> 0), e ele vai dizer que sim, então eu imprimir positivo.
Mas mesmo que eu sei que é> 0 e não vai ser 0 ou <0
Eu ainda vou fazer é 0, é <0,
então eu estou indo realmente dentro de ifs que eu não tinha que
porque eu já sei que não vai satisfazer qualquer uma dessas condições.
Eu posso usar o if, else if, else comunicado.
Ele basicamente diz que se x = 0 eu imprimir o positivo.
Se não for, eu vou também testar isto.
Se for 2, não vou fazer isso.
Basicamente, se eu tinha x = 2, você diria
if (x> 0), sim, para imprimir esta.
Agora que eu sei que é> 0 e que satisfeito o primeiro se
Eu não estou indo para executar este código.
O código é executado mais rápido, na verdade, três vezes mais rápido se você usar isso.
Também soubemos e e ou.
Eu não vou passar por isso porque Lexi já falamos sobre eles.
É apenas o && e operador | |.
>> A única coisa que eu vou dizer é ter cuidado quando você tem três condições.
Use parênteses porque é muito confuso quando você tem uma condição
e um outro, ou um outro.
Use parênteses apenas para ter certeza de que suas condições de fazer sentido
porque, nesse caso, por exemplo, você pode imaginar que
que poderia ser a primeira condição e um ou o outro
ou as duas condições combinadas em uma e
ou o terceiro, então tome cuidado.
E, finalmente, nós falamos sobre opções.
Um switch é muito útil quando você tem uma variável.
Vamos dizer que você tem uma variável como n
que podem ser 0, 1, ou 2, e para cada um desses casos
você está indo para executar uma tarefa.
Você pode dizer mudar a variável, e indica que
o valor é, então, como valor1 eu vou fazer isso,
e então eu quebrar, o que significa que eu não vou olhar para qualquer dos outros casos
porque nós já convencido de que caso
e, em seguida, valor2 e assim por diante, e também pode ter um interruptor padrão.
Isso significa que se ela não satisfaz qualquer dos casos que eu tive
que eu vou fazer outra coisa, mas isso é opcional.
Isso é tudo para mim. Agora vamos ter Tommy.
Tudo bem, isso vai ser Semana 3-ish.
Estes são alguns dos temas que vamos cobrindo, cripto, escopo, matrizes, et cetera.
Apenas uma palavra rápida sobre criptografia. Nós não estamos indo para martelar esta casa.
>> Fizemos isso em pset 2, mas para o quiz certeza que você sabe a diferença
entre a cifra de César ea cifra de Vigenère,
como ambos os trabalhos cifras e como é para criptografar
e descriptografar o texto usando esses dois códigos.
Lembre-se, a cifra de César simplesmente gira cada personagem com o mesmo valor,
certificando-se de mod pelo número de letras no alfabeto.
E a cifra de Vigenère, por outro lado, cada roda de caracteres
por um montante diferente, então ao invés de dizer
a cada rodada caracteres por 3 Vigenère irá girar cada personagem
por uma quantidade diferente dependendo de alguma palavra-chave
onde cada letra da palavra-chave representa uma quantidade diferente
para girar o texto claro por.
Vamos primeiro falar sobre escopo de variáveis.
Existem dois tipos diferentes de variáveis.
Temos variáveis ​​locais, e estes vão ser definidos
fora do principal ou fora de qualquer função ou bloco,
e estas estarão acessíveis em qualquer lugar em seu programa.
Se você tem uma função e em que função é um loop while
a grande variável global é acessível em qualquer lugar.
Uma variável local, por outro lado, é delimitado para o lugar onde ele está definido.
>> Se você tem uma função aqui, por exemplo, temos esta função g,
e dentro de g existe uma variável aqui chamada y,
e isso significa que esta é uma variável local.
Mesmo que esta variável é chamada y
e esta variável é chamado Y estas duas funções
não tenho idéia do que cada um dos outros locais são variáveis.
Por outro lado, aqui, dizemos int x = 5,
e isso está fora do escopo de qualquer função.
É fora do escopo do principal, por isso esta é uma variável global.
Isso significa que dentro destas duas funções, quando eu digo - x ou x + +
Eu estou acessando o mesmo x y em que este e este y são variáveis ​​diferentes.
Essa é a diferença entre uma variável global e uma variável local.
Tanto quanto design está em causa, às vezes, é provavelmente uma idéia melhor
para manter variáveis ​​locais sempre que você puder
já que ter um monte de variáveis ​​globais pode ficar muito confuso.
Se você tem um monte de funções modificando tudo a mesma coisa
você pode esquecer o que se esta função acidentalmente modifica este global,
e esta outra função não sabe sobre isso,
e que o faz ficar muito confuso como você obtém mais de código.
Mantendo variáveis ​​locais sempre que você puder
é projeto apenas bom.
Matrizes, lembre-se, são simplesmente listas de elementos do mesmo tipo.
Dentro de IC não pode ter uma lista como 1, 2,0, Olá.
Nós simplesmente não pode fazer isso.
>> Quando declarar uma matriz em C de todos os elementos têm de ser do mesmo tipo.
Aqui eu tenho um conjunto de 3 números inteiros.
Aqui eu tenho o comprimento da matriz, mas se eu estou declarando-o nesta sintaxe
onde eu especificar que todos os elementos estão tecnicamente eu não preciso deste 3.
O compilador é inteligente o suficiente para descobrir o quão grande a matriz deve ser.
Agora quando eu quiser obter ou definir o valor de uma matriz
esta é a sintaxe para fazer isso.
Isto irá efectivamente modificar o segundo elemento da matriz porque, lembrar,
numeração começa em 0, não em 1.
Se eu quero ler esse valor eu posso dizer algo como int x = array [1].
Ou se eu quiser definir esse valor, como eu estou fazendo aqui,
Posso dizer array [1] = 4.
Esse tempo acessar elementos pelo seu índice
ou a sua posição, ou quando eles estão na matriz,
e que a lista começa em 0.
Também podemos ter matrizes de matrizes,
e isso é chamado de matriz multi-dimensional.
Quando temos um array multi-dimensional
isso significa que podemos ter algo como linhas e colunas,
e esta é apenas uma maneira de visualizar isso ou pensar sobre isso.
Quando eu tenho um array multi-dimensional que significa que eu vou começar a precisar
mais do que um índice, porque se eu tiver uma grade
apenas dizendo o que linha você está em não nos dá um número.
Isso é realmente só vai dar-nos uma lista de números.
Vamos dizer que eu tenho essa matriz aqui.
Eu tenho uma matriz chamada de grade, e eu estou dizendo que é duas linhas e três colunas,
e por isso esta é uma maneira de visualizar isso.
Quando eu digo que eu quero começar o elemento em [1] [2]
isso significa que, porque estes são linhas e depois colunas
Eu vou pular para a linha 1 desde que eu disse um.
>> Então eu vou vir aqui para a coluna 2, e eu estou indo para obter o valor 6.
Faz sentido?
Arrays multi-dimensionais, lembre-se, são tecnicamente apenas uma matriz de matrizes.
Podemos ter matrizes de matrizes de matrizes.
Podemos continuar, mas realmente uma maneira de pensar
como isso está sendo colocado para fora eo que está acontecendo é para visualizá-lo
em uma grade como este.
Quando passar matrizes para funções, eles vão se comportar
um pouco diferente do que quando passar variáveis ​​para funções regulares
como passar um int ou um float.
Quando passamos em um tipo int ou char ou qualquer um desses outros dados
nós apenas deu uma olhada se a função modifica
o valor da variável que a mudança não vai propagar-se
para a função de chamada.
Com uma matriz, por outro lado, que acontecerá.
Se eu passar em um array para alguma função e que função altera alguns dos elementos,
quando eu voltar-se para a função que a chamou
minha matriz é agora vai ser diferente, eo vocabulário para que
é arrays são passados ​​por referência, como veremos mais tarde.
Isso está relacionado à forma como o trabalho ponteiros, onde esses tipos de dados básicos,
por outro lado, são passados ​​por valor.
>> Podemos pensar que, como fazer uma cópia de alguma variável e depois passar na cópia.
Não importa o que fazemos com essa variável.
A função de chamada não vai estar ciente de que ele foi alterado.
Matrizes são apenas um pouco diferente a esse respeito.
Por exemplo, como acabamos de ver, a principal é simplesmente uma função
que pode tomar dois argumentos.
O primeiro argumento para a função principal é argc, ou o número de argumentos,
eo segundo argumento é chamado argv,
e esses são os valores reais de tais argumentos.
Vamos dizer que eu tenho um programa chamado this.c,
e eu digo fazer isso, e eu estou indo para executar isso na linha de comando.
Agora, para passar alguns argumentos para o meu programa chamado isso,
Eu poderia dizer algo como. / Este é cs 50.
Isto é o que nós imaginamos David a fazer todos os dias no terminal.
Mas agora, a função principal no interior do referido programa
tem estes valores, assim argc é 4.
Ele pode ser um pouco confuso, porque realmente estamos apenas passando é cs 50.
Isso é apenas 3.
Mas lembre-se que o primeiro elemento de argv ou o primeiro argumento
é o nome da própria função.
Então isso significa que temos quatro coisas aqui,
eo primeiro elemento é que vai ser. / isso.
E isso vai ser representado como uma string.
Em seguida, os restantes elementos são o que digitado após o nome do programa.
Assim como um aparte, como nós, provavelmente, viu em pset 2,
lembre-se que a seqüência de 50 é a 50 ≠ inteiro.
Portanto, não podemos dizer algo como, 'int x = argv 3.'
>> Isso só não vai fazer sentido, porque esta é uma string, e este é um número inteiro.
Então, se você quer converter entre o 2, lembre-se, nós vamos
têm essa função mágica chamada atoi.
Que recebe uma string e retorna o inteiro representado dentro dessa seqüência.
Então, isso é um erro fácil de fazer no quiz,
só de pensar que este será automaticamente o tipo correto.
Mas só sei que estes serão sempre cordas
mesmo se a cadeia contém apenas um número inteiro ou um personagem ou uma bóia.
Então, agora vamos falar sobre o tempo de execução.
Quando temos todos esses algoritmos que fazer todas essas coisas loucas,
torna-se muito útil para a pergunta: "Quanto tempo eles levaram?"
Nós representamos que com algo chamado de notação assintótica.
Então isso significa que - bem, vamos dizer que dar o nosso algoritmo
alguma entrada muito, muito, muito grande.
Queremos fazer a pergunta: "Quanto tempo vai levar?
Quantas medidas irá tomar nosso algoritmo para executar
como uma função do tamanho da entrada? "
Assim, a primeira forma que podemos descrever o tempo de execução é com grande O.
E este é o nosso tempo de execução de pior caso.
Portanto, se queremos classificar um array, e nós damos o nosso algoritmo de uma matriz
que está em ordem decrescente, quando deveria estar em ordem ascendente,
que vai ser o pior caso.
Este é o nosso limite superior no tempo máximo de nosso algoritmo irá tomar.
Por outro lado, este Ω vai descrever melhor caso tempo de execução.
Então, se nós damos uma matriz já classificados para um algoritmo de classificação,
quanto tempo vai demorar para resolver isso?
E este, em seguida, descreve um limite inferior no tempo de execução.
Então, aqui são apenas algumas palavras que descrevem algumas vezes comuns em execução.
Estes são, em ordem crescente.
O tempo mais rápido em execução que temos é chamado constante.
>> Isso significa que não importa quantos elementos damos o nosso algoritmo,
não importa quão grande é a nossa matriz, a triagem
ou fazendo o que estamos fazendo para a matriz sempre terá a mesma quantidade de tempo.
Assim, podemos representar que apenas com um 1, o qual é uma constante.
Nós também olhou em tempo de execução logarítmica.
Portanto, algo como busca binária é logarítmica,
onde vamos cortar o problema pela metade o tempo todo
e depois as coisas só ficam mais de lá.
E se você está sempre escrevendo um O de qualquer algoritmo de fatorial,
provavelmente você não deve considerar este como o seu trabalho do dia.
Ao comparar tempos de execução é importante manter em mente essas coisas.
Então, se eu tenho um algoritmo que é O (n), e mais alguém
tem um algoritmo de O (2n) estes são realmente assintoticamente equivalente.
Então, se nós imaginarmos n para ser um número grande como Eleventy bilhões:
Então, quando estamos comparando Eleventy bilhões para algo como Eleventy bilhões + 3,
de repente que três realmente não faz uma grande diferença mais.
É por isso que nós vamos começar a considerar essas coisas equivalentes.
Então, coisas como essas constantes aqui, há 2 x este, ou a adição de 3,
estes são apenas constantes, e estes vão cair para cima.
É por isso que todos os 3 destes tempos de execução são o mesmo que dizer que eles são O (n).
Da mesma forma, se temos dois tempos de execução de outros, digamos O (n ³ + 2n ²), podemos adicionar
+ N, + 7, e depois temos um outro tempo de execução que é apenas O (n ³).
Novamente, estes são a mesma coisa, porque estes - estes não são os mesmos.
Estas são as mesmas coisas, me desculpe. Então, esses são os mesmos, porque
este ³ n vai dominar este ² 2n.
>> O que não é a mesma coisa é se ter executado tempos como O (n ³) e O (n ²)
porque este ³ n é muito maior do que isto n ².
Então, se temos expoentes, de repente, isso começa com a matéria,
mas quando estamos lidando apenas com fatores como estamos aqui,
então não vai importar, porque eles estão indo só para cair fora.
Vamos dar uma olhada em alguns dos algoritmos que temos visto até agora
e falar sobre o seu tempo de execução.
A primeira maneira de olhar para um número em uma lista, o que vimos, foi busca linear.
Ea implementação da busca linear é super simples.
Nós só temos uma lista, e vamos olhar para cada elemento na lista
até encontrar o número que estamos procurando.
Então, o que significa que na pior das hipóteses, este O (n).
E o pior caso aqui poderia ser se o elemento é
o último elemento, em seguida, usando busca linear, temos de olhar para cada elemento
até chegarmos ao último, a fim de saber que era realmente na lista.
Nós não podemos simplesmente desistir no meio e dizer: "É, provavelmente, não existe."
Com a busca linear temos de olhar para a coisa toda.
O tempo de funcionamento melhor caso, por outro lado, é constante
porque, no melhor caso, o elemento que estamos procurando é apenas o primeiro da lista.
Por isso, vai nos levar exatamente o passo 1, não importa quão grande a lista é
se nós estamos olhando para o primeiro elemento de cada vez.
>> Então, quando você pesquisa, lembre-se, não exige que a nossa lista de ser classificado.
Porque nós estamos indo simplesmente para olhar sobre cada elemento, e isso realmente não importa
que ordem os elementos estão dentro
Um algoritmo de busca mais inteligente é algo como pesquisa binária.
Lembre-se, a implementação de busca binária é quando você vai
manter a olhar para o meio da lista.
E porque estamos a olhar para o meio, é necessário que a lista é ordenada
ou então nós não sabemos onde o meio é, e temos que olhar por cima
toda a lista de encontrá-lo, e então em que ponto nós estamos apenas perdendo tempo.
Então, se temos uma lista ordenada e encontramos a meio, vamos comparar a média
ao elemento que estamos procurando.
Se for muito alto, então podemos esquecer a metade direita
porque sabemos que, se o nosso elemento já é muito alta
e tudo para a direita deste elemento é ainda maior,
então não precisa olhar mais lá.
Onde, por outro lado, se o nosso elemento é muito baixa,
sabemos tudo para a esquerda do elemento que é também demasiado baixa,
por isso realmente não faz sentido olhar para lá, também.
Dessa forma, a cada passo e cada vez que olhar para o ponto médio da lista,
vamos cortar pela metade o nosso problema, porque de repente sabemos
um monte de números que não podem ser o que estamos procurando.
>> Em pseudocódigo este seria algo parecido com isso,
e porque estamos cortando a lista pela metade a cada momento,
nossas pior caso de execução de saltos no tempo linear para logarítmica.
Então, de repente, temos log-in passos para encontrar um elemento em uma lista.
O tempo de execução de melhor caso, no entanto, ainda é constante
porque agora, vamos apenas dizer que o elemento que estamos procurando é
sempre meio exato da lista original.
Assim, podemos aumentar a nossa lista tão grande como nós queremos, mas se o elemento que estamos procurando é no meio,
então ele só vai nos levar um passo.
Então é por isso que estamos O (log n) e Ω (1) ou constante.
Vamos rodar busca binária nesta lista.
Então, vamos dizer que nós estamos olhando para o elemento 164.
A primeira coisa que vamos fazer é encontrar o ponto médio desta lista.
O que acontece é que o ponto médio vai cair entre estes dois números,
então vamos arbitrariamente dizer, toda vez que o ponto médio cai entre dois números,
vamos arredondar para cima.
Nós só precisamos ter certeza de que fazemos isso a cada passo do caminho.
Então, vamos arredondar para cima, e nós vamos dizer que 161 é o meio de nossa lista.
Então, 161 <164, e todos os elementos para a esquerda de 161
também é <164, então sabemos que isso não vai nos ajudar em tudo
para começar a olhar para aqui porque o elemento que estamos procurando não pode estar lá.
Então o que podemos fazer é que podemos esquecer que metade toda esquerda da lista,
e agora considerar apenas a partir da direita da frente 161.
>> Então, novamente, este é o ponto médio; vamos arredondar para cima.
Agora 175 é muito grande.
Então, nós sabemos que não vai ajudar-nos a olhar aqui ou aqui,
assim que nós podemos apenas jogar isso fora, e, eventualmente, vamos acertar o 164.
Quaisquer dúvidas em busca binária?
Vamos passar de busca através de uma lista já classificada
para realmente tomar uma lista de números em qualquer ordem
e fazer essa lista em ordem crescente.
O primeiro algoritmo vimos foi chamado bubble sort.
E esta seria mais simples dos algoritmos que vimos.
Espécie de bolha, diz que quando os dois elementos dentro da lista estão fora do lugar,
ou seja, há um maior número à esquerda de um número mais baixo,
então nós estamos indo para trocá-los, porque isso significa que a lista será
"Mais ordenadas" do que era antes.
E nós apenas estamos indo para continuar este processo de novo e de novo e de novo
até que finalmente o tipo elementos de bolha para sua localização correta e temos uma lista classificada.
>> O tempo de execução deste vai ser O (n ²). Por quê?
Bem, porque na pior das hipóteses, vamos tomar todos os elementos, e
vamos acabar comparando-a com todos os outros elementos da lista.
Mas, na melhor das hipóteses, temos uma lista já classificados, tipo de bolha
só vai passar por uma vez, dizer "Nope. eu não fazer qualquer troca, assim que eu sou feito."
Então, nós temos um tempo melhor caso de execução de Ω (n).
Vamos correr espécie de bolha em uma lista.
Ou primeiro, vamos olhar para alguns pseudocódigo muito rapidamente.
Queremos dizer que queremos acompanhar, em cada iteração do loop,
manter o controle da existência ou não mudamos todos os elementos.
Assim, a razão para isso é que nós vamos parar quando não trocaram todos os elementos.
Então, no início de nosso laço não ter trocado nada, então vamos dizer que é falso.
Agora, vamos percorrer a lista e comparar elemento i ao elemento i + 1
e se for o caso em que existe um maior número à esquerda de um número menor,
então nós estamos indo só para trocá-los.
>> E então, vamos lembrar que nós trocamos um elemento.
Isso significa que temos de percorrer a lista pelo menos uma vez mais
porque a condição em que se parou é quando toda a lista é já classificados,
o que significa que não tenha feito qualquer troca.
É por isso que a nossa condição aqui é "enquanto alguns elementos foram trocados."
Então, agora vamos olhar para esta rodando em uma lista.
Eu tenho a lista 5,0,1,6,4.
Espécie de bolha vai começar todo o caminho à esquerda, e vai para comparar
os elementos i, de modo 0 a i + 1, que é o elemento 1.
Vai dizer, bem 5> 0, mas agora 5 é para a esquerda,
então eu preciso trocar o 5 eo 0.
Quando eu trocá-los, de repente, eu recebo esta lista diferente.
Agora 5> 1, então nós estamos indo para trocá-los.
5 não é> 6, portanto, não precisa fazer nada aqui.
Mas 6> 4, por isso precisamos trocar.
Mais uma vez, temos de percorrer toda a lista para, eventualmente, descobrir
que estes estão fora de ordem, nós trocá-los,
e neste momento temos de percorrer a lista uma vez mais
para se certificar de que tudo está no seu fim, e neste tipo de bolha ponto de terminar.
Um algoritmo diferente para a tomada de alguns elementos e classificá-los é uma espécie de seleção.
A idéia por trás tipo de seleção é que nós vamos construir uma parte classificada da lista
Um elemento de cada vez.
>> E a maneira como vamos fazer isso é através da construção de segmento esquerdo da lista.
E, basicamente, cada - em cada etapa, vamos levar o menor elemento que nos resta
que não tenha sido resolvido ainda, e nós estamos indo para movê-lo para que o segmento classificado.
Isso significa que precisamos continuamente encontrar o elemento mínimo indiferenciados
e levar esse elemento mínimo e trocá-lo com o que
mais à esquerda elemento que não está classificada.
O tempo de execução deste vai ser O (n ²), porque no pior caso
precisamos comparar cada elemento de qualquer outro elemento.
Porque nós estamos dizendo que, se começar na metade esquerda da lista, precisamos
que passar por todo o segmento da direita para encontrar o menor elemento.
E então, mais uma vez, temos de passar por cima de todo o segmento direito e
continuar mais que uma e outra e outra vez.
Isso vai ser ² n. Nós vamos precisar de um circuito para dentro de outro loop
o que sugere ² n.
No pensamento melhor caso, vamos dizer que nós dar-lhe uma lista já classificados;
nós realmente não fazer melhor do que ² n.
Porque tipo de seleção não tem forma de saber que
o elemento mínimo é apenas a acontecer de eu estar olhando.
Ele ainda precisa ter certeza de que este é realmente o mínimo.
>> E a única maneira de ter certeza de que é o mínimo, usando esse algoritmo,
é olhar para cada elemento novo.
Então, realmente, se você der a ele - se você der tipo de seleção uma lista já classificados,
ele não vai fazer nada melhor do que dar-lhe uma lista que não é classificado ainda.
By the way, se acontecer de ser o caso de que algo é O (algo)
eo ômega de algo, podemos dizer de forma mais sucinta que é θ de algo.
Então, se você ver que chegar em qualquer lugar, isso é o que significa apenas.
>> Se algo é theta de n ², é tanto grande O (n ²) e Ω (n ²).
Então, o melhor caso e pior caso, não faz diferença,
o algoritmo vai fazer a mesma coisa o tempo todo.
Então é isso que pseudocódigo para tipo de seleção pode parecer.
Estamos basicamente vai dizer que eu quero iterar sobre a lista
da esquerda para a direita, e em cada iteração do loop, eu estou indo para mover
o elemento mínimo para esta porção da lista ordenada.
E uma vez que eu passo alguma coisa lá, eu nunca precisa olhar para esse elemento novamente.
Porque assim que eu trocar um elemento para o segmento esquerdo da lista, está classificada
porque estamos fazendo tudo em ordem crescente, usando mínimos.
Então nós dissemos, tudo bem, estamos na posição i, e nós precisamos de olhar para todos os elementos
para a direita de i, a fim de encontrar o mínimo.
Assim, isto significa que quer olhar de i + 1 para o fim da lista.
E agora, se o elemento que nós estamos procurando é a menos do que o nosso mínimo até agora,
que, lembre-se, estamos começando a fora mínimo a ser apenas
qualquer elemento que estamos atualmente, eu vou assumir que é o mínimo.
Se eu encontrar um elemento que é menor do que isso, então eu vou dizer, ok,
bem, eu encontrei um novo mínimo.
Eu vou lembrar de onde esse mínimo era.
>> Então, agora, depois de já ter passado por esse segmento direito indiferenciados,
Eu posso dizer que eu vou trocar o elemento mínimo com o elemento que está na posição i.
Que vai construir a minha lista, minha porção classificada da lista da esquerda para a direita,
e não precisar olhar para um elemento novo, uma vez que é nessa porção.
Uma vez que tenhamos trocado ele.
Então, vamos executar tipo de seleção na lista.
O elemento de azul aqui vai ser a i, e o elemento vermelho vai ser o elemento mínimo.
Então eu começa todo o caminho à esquerda da lista, de modo a 5.
Agora precisamos encontrar o elemento mínimo indiferenciados.
Assim, dizemos 0 <5, então 0 é o meu novo mínimo.
>> Mas eu não posso parar por aí, porque, embora possamos reconhecer que 0 é o menor,
que precisamos para executar através de todos os outros elementos da lista para ter certeza.
Então, um é maior, 6 é maior, 4 é maior.
Isso significa que, depois de olhar para todos esses elementos, eu já determinou 0 é o menor.
Então, eu vou trocar o 5 eo 0.
Uma vez eu trocar isso, eu estou indo para obter uma nova lista, e eu sei que eu nunca precisa olhar para isso 0 novamente
porque uma vez eu troquei, eu classificados por ele e estamos a fazer.
Agora, acontece que o elemento azul é novamente a 5,
e que precisa de olhar para o 1, a 6 e a 4 para determinar que um
é o menor elemento mínimo, então vamos trocar o 1 eo 5.
Mais uma vez, temos de olhar - comparar a 5 para o 6 e 4,
e vamos trocar o 4 eo 5, e, finalmente, comparar
os números 2 e trocá-los até chegar a nossa lista de classificados.
Qualquer dúvida sobre tipo de seleção?
Okay. Vamos passar para o último tópico aqui, e que é a recursividade.
>> Recursão, lembre-se, é essa coisa meta realmente onde uma função
repetidamente chama a si mesmo.
Então, em algum ponto, enquanto a nossa fuction é repetidamente chamando-se,
é preciso haver algum ponto em que paramos de nos chamar.
Porque se nós não fizermos isso, então vamos apenas continuar a fazer isso para sempre
e nosso programa é só não vai terminar.
Chamamos essa condição no caso base.
E o caso base diz, ao invés de chamar uma função de novo,
Eu só vou retornar algum valor.
Portanto, uma vez que já retornou um valor, nós paramos de nos chamar,
eo resto dos convites que fizemos até agora também pode retornar.
O oposto do caso base é o caso recursivo.
E isto é quando queremos fazer uma outra chamada para a função que estamos atualmente dentro
E nós provavelmente, embora nem sempre, quer usar argumentos diferentes.
>> Então, se temos uma função chamada f, ef chamado apenas de tomar um argumento,
e nós continuamos chamando f (1), f (1), f (1), e isso só acontece que
o argumento cai em um caso recursivo, estamos ainda nunca vai parar.
Mesmo se tivermos um caso base, precisamos ter certeza de que, eventualmente, vamos bater esse caso base.
Nós não apenas manter permanecer neste caso recursivo.
Geralmente, quando chamamos a nós mesmos, provavelmente vamos ter um argumento diferente a cada vez.
Aqui é uma função muito simples recursiva.
Então, isso vai calcular o fatorial de um número.
Lá em cima, aqui temos o nosso caso base.
No caso em que n ≤ 1, nós não vamos chamar fatorial novamente.
Nós vamos parar, estamos apenas indo para retornar algum valor.
Se isso não é verdade, então nós estamos indo para acertar nosso caso recursivo.
Note-se aqui que não estamos apenas chamando fatorial (n), porque isso não seria muito útil.
Nós vamos chamar fatorial de outra coisa.
>> E assim você pode ver, eventualmente, se passar um algo fatorial (5) ou,
vamos chamar fatorial (4) e assim por diante, e, eventualmente, vamos bater este cenário de base.
Portanto, este parece ser bom. Vamos ver o que acontece quando nós realmente executar este.
Esta é a pilha, e vamos dizer que principal vai chamar esta função com um argumento (4).
Portanto, uma vez fatorial vê e = 4, fatorial irá se identificar.
Agora, de repente, temos fatorial (3).
Então, essas funções vão continuar crescendo até finalmente chegarmos nosso caso base.
Neste ponto, o valor de retorno é o retorno (nx o valor de retorno deste),
o valor de retorno é nx valor o retorno deste.
Eventualmente precisamos acertar algum número.
No topo aqui, dizemos retorno 1.
Isso significa que uma vez que voltar esse número, podemos pop esta na pilha.
Portanto, este fatorial (1) é feito.
Quando um retorna, esse fatoriais (1) retorna, esse retorno a 1.
O valor de retorno a isso, lembre-se, foi nx o valor de retorno deste.
Então, de repente, esse cara sabe que eu quero voltar 2.
>> Então lembre-se, retornar o valor desta é apenas nx o valor de retorno aqui.
Então agora podemos dizer 3 x 2, e, finalmente, aqui podemos dizer
isso é apenas vai ser 4 x 3 x 2.
E uma vez que ele retorna, nós descer a um único inteiro dentro da principal.
Qualquer dúvida sobre recursão?
Tudo bem. Portanto, não há mais tempo para perguntas, no final,
mas agora Joseph cobrirá os tópicos restantes.
>> [Joseph Ong] Tudo bem. Portanto, agora que nós já conversamos sobre recursões,
vamos falar um pouco sobre o que é merge sort.
Merge sort é basicamente uma outra maneira de ordenar uma lista de números.
E como ele funciona é, com merge sort você tem uma lista, eo que fazemos é
dizemos, vamos dividir isso em duas metades.
Vamos primeiro executar merge sort novamente na metade esquerda,
Então vamos correr merge sort na metade direita,
e que nos dá agora duas metades que são classificados, e agora vamos combinar essas metades juntas.
É um pouco difícil de ver sem um exemplo, por isso vamos percorrer as propostas e ver o que acontece.
Então você começa com esta lista, que dividi-lo em duas metades.
Corremos merge sort na metade esquerda primeiro.
Então essa é a metade esquerda, e agora nós executá-los através desta lista novamente
que é passado para merge sort, e então olhamos, mais uma vez,
no lado esquerdo da lista e corremos merge sort sobre ele.
Agora, temos até uma lista de números 2,
e agora a metade esquerda é apenas um elemento de comprimento, e não podemos
dividir uma lista que é apenas um elemento no meio, de modo que acabamos de dizer, uma vez que temos 50,
que é apenas um elemento, já está classificado.
>> Uma vez que estamos a fazer com que, nós podemos ver que nós podemos
passar para a metade direita da lista,
e 3 também é classificado, e agora que as duas metades desta lista são classificados
podemos juntar esses números juntos novamente.
Assim, analisamos 50 e 3, 3 é menor do que 50, de modo que vai em primeiro lugar e, em seguida, 50 vem dentro
Agora, isso é feito, nós voltar-se a essa lista e tipo é meia direita.
42 é seu número próprio, por isso já está classificada.
Então agora nós comparar estes 2 e 3 é menor do que 42, de modo que é colocado em primeiro lugar,
agora com 42 anos é colocado, e 50 é colocado dentro
Agora, que está classificado, que percorrer todo o caminho de volta ao topo, 1337 e 15.
Bem, nós agora olhar para a metade esquerda da lista; 1337 é, por si só por isso é classificado e mesmo com 15.
Então agora nós combinar esses dois números para ordenar que a lista original, 15 <1,337,
assim vai em primeiro lugar, então 1337 vai dentro
E agora nós classificamos as duas metades da lista original em cima.
E tudo o que temos a fazer é combinar estes.
Nós olhamos para os 2 primeiros números desta lista, 3 <15, então ele vai para a matriz de classificação em primeiro lugar.
15 <42, assim que vai dentro Agora, 42 <1337, que vai dentro
50 <1,337, de modo que vai dentro e perceber que nós só teve dois números fora desta lista.
Portanto, não estamos apenas alternando entre as duas listas.
Estamos apenas olhando para o início, e nós estamos levando o elemento
que é menor e, em seguida, colocá-lo em nossa matriz.
Agora nós mesclou todas as metades e estamos a fazer.
>> Qualquer dúvida sobre merge sort? Sim?
[Estudante] Se for dividir em grupos diferentes, por que eles não apenas dividi-lo uma vez
e você tem 3 e 2 em um grupo? [Resto do ininteligível questão]
A razão - então a questão é, por que não podemos simplesmente juntá-las em que o primeiro passo depois de tê-los?
A razão que nós podemos fazer isso, inicie os elementos mais à esquerda de ambos os lados,
e depois tome a menor e colocá-lo em, é que sabemos que esses
listas individuais estão em ordens classificados.
Então, se eu estou olhando para os elementos mais à esquerda de ambas as metades,
Eu sei que eles vão ser os menores elementos dessas listas.
Para que eu possa colocá-los em pontos menor elemento desta lista grande.
Por outro lado, se eu olhar para as duas listas no segundo nível por lá,
50, 3, 42, 1337 e 15, aqueles que não são classificados.
Então, se eu olhar para 50 e 1337, eu vou colocar 50 em minha primeira lista.
Mas isso não faz muito sentido, porque 3 é o menor elemento de todos aqueles.
Então, a única razão que podemos fazer este passo combinando é porque nossas listas já estão classificados.
É por isso que nós temos que começar todo o caminho até o fundo
porque quando temos apenas um único número, você sabe que um único número
em si já é uma lista ordenada.
>> Alguma pergunta? Não?
Complexidade? Bem, você pode ver que em cada etapa há números finais,
e podemos dividir uma lista em meia log n vezes,
que é onde nós começamos este log n x n complexidade.
E você vai ver o melhor caso para merge sort é n log n, e isso só acontece
que o pior caso, ou o Ω lá, também é n log n.
Algo para se manter em mente.
Seguindo em frente, vamos ir para algum arquivo de super básica I / O.
Se você olhou para Scramble, você vai notar que tivemos algum tipo de sistema
onde você pode gravar em um arquivo de log, se você ler o código.
Vamos ver como você pode fazer isso.
Bem, temos fprintf, que você pode pensar em como apenas printf,
mas apenas a impressão para um arquivo em vez disso, e, portanto, o F no início.
Este tipo de código até aqui, o que ele faz é, como você deve ter visto em Scramble,
ele passa por sua impressão matriz de 2 dimensões fora de linha em linha quais são os números.
Neste caso, printf imprime ao seu terminal ou o que chamamos a saída padrão de seção.
>> E agora, neste caso, tudo o que temos a fazer é substituir printf com fprintf,
dizer o que arquivo que você deseja imprimir, e, neste caso, apenas imprime-lo para o arquivo
em vez de mostrá-lo ao seu terminal.
Bem, então, que levanta a questão: Onde é que vamos conseguir esse tipo de arquivo, certo?
Passamos login nesse fuction fprintf mas não tínhamos idéia de onde ele veio.
Bem, no início do código, o que teve foi este pedaço de código aqui,
que basicamente diz que o arquivo aberto chama log.txt.
O que fazer depois disso é que temos que ter certeza de que o arquivo está realmente aberta com êxito.
Por isso, pode falhar por várias razões, você não tem espaço suficiente no seu computador, por exemplo.
Por isso é sempre importante antes de fazer qualquer operação com o arquivo
que verificar se o arquivo foi aberto com sucesso.
Então, o que que um, isso é um argumento para fopen, bem, podemos abrir um arquivo de muitas maneiras.
O que podemos fazer é, podemos passá-lo w, o que significa substituir o arquivo, se ele sair já,
Podemos passar um a, que acrescente ao final do arquivo, em vez de ignorá-los,
ou podemos especificar r, o que significa, vamos abrir o arquivo como somente leitura.
Então, se o programa tenta fazer as alterações para o arquivo,
gritar com eles e não deixá-los fazer isso.
Finalmente, uma vez que é feito com o arquivo, feito que faz operações sobre ela,
precisamos ter certeza de que feche o arquivo.
E assim, no final de seu programa, que vai passá-los novamente
este arquivo que você abriu, e apenas o fechar.
Então isso é algo importante que você tem que ter certeza que você faz.
Então lembre-se que você pode abrir um arquivo, então você pode escrever para o arquivo,
fazer operações no arquivo, mas então você tem que fechar o arquivo no final.
>> Qualquer dúvida sobre arquivo básico I / O? Sim?
[Pergunta do estudante, ininteligível]
Aqui. A questão é: onde é que este arquivo log.txt aparecer?
Bem, se você apenas dar-lhe log.txt, cria-lo no mesmo diretório que o executável.
Então, se você está - >> [pergunta Estudante, ininteligível]
Sim. Na mesma pasta, ou no mesmo diretório, como lhe chamam.
Agora memória, pilha, pilha e.
Então, como é a memória definidos no computador?
Bem, você pode imaginar a memória como uma espécie de este bloco aqui.
E na memória, temos o que é chamado de pilha preso lá, ea pilha que está lá embaixo.
E a pilha cresce para baixo e a pilha cresce para cima.
Assim como Tommy mencionado - oh, bem, e nós temos esses outros quatro segmentos que eu vou chegar em um segundo -
Como Tommy disse anteriormente, você sabe como se chamam as suas funções e chamar uns aos outros?
Constroem-se este tipo de quadro de pilha.
Bem, se as chamadas principais foo, foo é colocado na pilha.
Foo chama bar, bar de conseguir colocar na pilha, e que é colocado na pilha depois.
E como eles retornam, cada um se retirado da pilha.
O que cada um desses locais e memória segurar?
Pois bem, a parte superior, que é o segmento de texto, contém o próprio programa.
Assim, o código de máquina, que está lá, uma vez que você compilar o seu programa.
Em seguida, qualquer inicializado variáveis ​​globais.
>> Então você tem variáveis ​​globais em seu programa, e você diz assim, a = 5,
que é colocado no segmento, e logo abaixo que,
você tem quaisquer dados não inicializados global, que é apenas um INT,
mas você não dizer que é igual a nada.
Perceber estes são variáveis ​​globais, por isso eles estão fora de principal.
Então isso significa que todas as variáveis ​​globais que são declarados, mas não são inicializados.
Então, o que está no monte? Memória alocada usando malloc, que nós vamos chegar a um pouco.
E, finalmente, com a pilha que você tem todas as variáveis ​​locais
e todas as funções que se pode chamar de qualquer de seus parâmetros.
A última coisa, você realmente não tem que saber que as variáveis ​​de ambiente fazer,
mas sempre que você executar o programa, não é algo associado, como
este é o nome de usuário da pessoa que executou o programa.
E isso vai ser uma espécie de na parte inferior.
Em termos de endereços de memória, que são valores hexadecimais,
os valores no início topo a 0, e vão até o fim para o fundo.
Neste caso, se você estiver no sistema de 32 bits,
o endereço na parte inferior vai ser 0x, seguido por af, porque é 32 bits,
que é de 8 bytes, e neste caso corresponde a 8 bytes de 8 dígitos hexadecimais.
Então aqui você vai ter, como, 0xffffff, e até lá você vai ter 0.
Então, o que são ponteiros? Alguns de vocês podem não ter coberto este na seção anterior.
mas conseguimos passar por isso na palestra, para um ponteiro é apenas um tipo de dados
quais as lojas, em vez de algum tipo de valor como 50, ele armazena o endereço de algum local na memória.
Como que a memória [ininteligível].
Portanto, neste caso, o que temos é, temos um ponteiro para um inteiro ou um int *,
e que contém este endereço hexadecimal de 0xDEADBEEF.
>> Então o que temos é, agora, este ponteiro aponta em algum local na memória,
e isso é só um, o valor de 50 é neste local de memória.
Em alguns sistemas de 32 bits, em todos os sistemas de 32 bits, os ponteiros levar até 32 pedaços ou 4 bytes.
Mas, por exemplo, em um sistema de 64 bits, os ponteiros são 64 bits.
Então, isso é algo que você vai querer manter em mente.
Então, em um sistema de ponta-bit, um ponteiro é bits de longo prazo.
Os ponteiros são uma coisa difícil de digerir sem coisas extras,
então vamos passar um exemplo de alocação dinâmica de memória.
O alocação dinâmica de memória faz por você, ou o que chamamos de malloc,
ele permite que você alocar algum tipo de dados fora do set.
Portanto, este tipo de dados é mais permanente para a duração do programa.
Porque, como você sabe, se você declarar x dentro de uma função, e que retorna de função,
você já não tem acesso aos dados que foram armazenados em x.
O que vamos fazer ponteiros é que vamos armazenar valores de memória ou loja
em um segmento diferente de memória, ou seja, a pilha.
Agora, depois voltamos para fora da função, desde que temos um ponteiro
para esse local na memória, então o que podemos fazer é que podemos apenas olhar para os valores lá.
Vejamos um exemplo: Este é o nosso layout de memória novamente.
E nós temos essa função, principal.
O que ele faz é - bem, tão simples, certo -? Int x = 5, que é apenas uma variável na pilha na principal.
>> Por outro lado, agora vamos declarar um ponteiro que chama os giveMeThreeInts função.
E agora vamos para essa função e criar um novo quadro de pilha para ele.
No entanto, neste quadro de pilha, nós declaramos temp * int,
que em mallocs três inteiros para nós.
Assim o tamanho de int nos dará quantos bytes int este é,
malloc e dá-nos que muitos bytes de espaço na pilha.
Portanto, neste caso, criamos espaço suficiente para três números inteiros,
ea pilha é lá em cima, que é por isso que eu o tirei mais acima.
Assim que estiver pronto, nós voltamos aqui, você só precisa de 3 ints voltou,
e retorna o endereço, no caso em que mais de que a memória é.
E nós definir ponteiro = interruptor, e até lá temos apenas um ponteiro outro.
Mas o que os retornos de função é empilhado aqui, e desaparece.
Então temporário desaparece, mas ainda manter o endereço de onde
esses três inteiros estão dentro da rede.
Portanto, neste conjunto, os ponteiros são escopo localmente para o quadro empilhados,
mas a memória a que se referem é no heap.
>> Isso faz sentido?
[Estudante] Pode repetir? >> [Joseph] Sim.
Então, se eu voltar um pouco, você vê que temporário alocado
alguma memória na pilha lá em cima.
Então, quando essa função, retorna giveMeThreeInts, esta pilha aqui vai desaparecer.
E com ele qualquer das variáveis, neste caso, este ponteiro que foi alocado no quadro empilhado.
Isso vai desaparecer, mas desde que voltou de temperatura
e partimos ponteiro = temp, o ponteiro agora vai apontar a mesma memória de localização como temperatura foi.
Então, agora, apesar de perder temp, esse ponteiro local,
nós ainda manter o endereço de memória do que estava apontando para dentro do que o ponteiro variável.
Perguntas? Isso pode ser uma espécie de tema confuso se você não ter ido mais em seção.
Podemos, seu TF vai certamente passar por isso e é claro que podemos responder a perguntas
no final da sessão de revisão para este.
Mas esta é uma espécie de um tema complexo, e eu tenho mais exemplos que vão aparecer
que vai ajudar a esclarecer o que realmente são os ponteiros.
>> Neste caso, os ponteiros são equivalentes às matrizes,
então eu só posso usar esse ponteiro como a mesma coisa que uma matriz int.
Então, eu estou indexação em 0, e mudando o primeiro número inteiro a 1,
alterar o segundo inteiro de 2, e o número inteiro 3 a 3.
Então, mais em ponteiros. Bem, lembro Binky.
Neste caso temos atribuído um ponteiro, ou declaramos um ponteiro,
mas, inicialmente, quando eu acabara de declarar um ponteiro, ele não está apontando para qualquer lugar na memória.
É apenas valores de lixo no interior da mesma.
Então eu não tenho idéia de onde este ponteiro está apontando.
Ele tem um endereço que é apenas preenchido com 0 e 1, onde ele foi inicialmente declarado.
Eu não posso fazer nada com isso até eu chamar malloc sobre ele
e então ele me dá um pouco de espaço na pilha onde eu possa colocar valores dentro.
Então, novamente, eu não sei o que está dentro dessa memória.
Então a primeira coisa que tenho a fazer é verificar se o sistema tinha memória suficiente
para me dar de volta um número inteiro em primeiro lugar, que é por isso que eu estou fazendo essa verificação.
Se o ponteiro é nulo, o que significa que não têm espaço suficiente ou algum outro erro ocorreu,
assim que eu deveria sair do meu programa.
Mas se ele fez sucesso, agora eu posso usar esse ponteiro
eo que faz é ponteiro * segue-se que o endereço é
para onde esse valor é, e define-a igual a 1.
Então, aqui, estamos verificando se a memória existia.
>> Uma vez que você sabe que ela existe, você pode colocar nele
qual o valor que você quer colocar nele, neste caso 1.
Uma vez que estamos a fazer com ele, você precisa de libertar esse ponteiro
porque nós precisamos voltar ao sistema que a memória que você pediu, em primeiro lugar.
Como o computador não sabe quando estamos a fazer com ele.
Neste caso, estamos explicitamente dizendo que, ok, estamos a fazer com que a memória.
Se algum outro processo precisa dele, algum outro programa precisa dele, sinta-se livre para ir em frente e levá-la.
O que também pode fazer é que podemos obter apenas o endereço de variáveis ​​locais no conjunto.
Então x int é dentro do quadro de empilhados principal.
E quando usamos este comercial, este e operador, o que faz é
leva x, e x é apenas alguns dados na memória, mas não tem um endereço.
Ele está situado em algum lugar. Então, chamando & x, o que isto significa é que nos dá o endereço de x.
Ao fazer isso, estamos fazendo ponto ponteiro para onde x é na memória.
Agora só faço algo como * x, vamos obter 5 de volta.
A estrela é chamada dereferencing-lo.
Você segue o endereço e você terá o valor dele lá armazenados.
>> Alguma pergunta? Sim?
[Estudante] Se você não fizer a coisa três pontas, ela ainda compilar?
Sim. Se você não fizer a coisa de 3 pontos, ele ainda vai compilar,
mas eu vou mostrar o que acontece em um segundo, e sem fazer isso,
isso é o que chamamos de vazamento de memória. Você não está dando ao sistema
apoiar sua memória, por isso depois de um tempo o programa vai acumular
memória que ele não está usando, e nada mais pode usá-lo.
Se você já viu o Firefox com 1,5 milhão de kilobytes em seu computador,
no gerenciador de tarefas, é o que está acontecendo.
Você tem um vazamento de memória no programa que não está segurando.
Assim como o ponteiro trabalho aritmética?
Bem, a aritmética de ponteiro é uma espécie de indexação como em uma matriz.
Neste caso, eu tenho um ponteiro, eo que eu faço é fazer ponto ponteiro para o primeiro elemento
Esta série de três números inteiros que eu alocados.
Então agora o que eu faço, o ponteiro estrela só muda o primeiro elemento da lista.
Estrela ponteiro 1 pontos aqui.
Então ponteiro está aqui, é um ponteiro aqui, ponteiro 2 é aqui.
>> Então, basta adicionar 1 é a mesma coisa que se mover ao longo desta matriz.
O que fazemos é, quando fazemos um ponteiro de obter o endereço aqui,
e, a fim de obter o valor aqui, você coloca uma estrela no de toda a expressão
para cancelar a referência dela.
Assim, neste caso, eu estou definindo a primeira posição nesta matriz a 1,
segundo local a 2, e a terceira posição 3.
Então o que eu estou fazendo aqui é que eu estou imprimindo nosso ponteiro 1,
que só me dá 2.
Agora estou incrementando ponteiro, para que o ponteiro é igual a um ponteiro,
que se move para a frente.
E agora, se eu imprimir um ponteiro, ponteiro 1 é agora 3,
que neste caso é impressa 3.
E a fim de algo livre, o ponteiro que eu dou
deve estar apontando para o início da matriz, que eu voltei do malloc.
Assim, neste caso, se eu fosse chamar três aqui, isso não seria certo,
porque é no meio da matriz.
Eu tenho que subtrair para chegar ao local original
o ponto inicial antes que eu possa libertá-lo.
Então, aqui está um exemplo mais complicado.
Neste caso, estamos alocando sete caracteres em uma matriz de caracteres.
>> E, neste caso, o que estamos fazendo é que estamos looping sobre o 6 primeiro deles,
e estamos colocando-a Z.
Assim, para i = 0, i> 6, i + +,
Assim, o ponteiro + i vai apenas dar-nos, neste caso,
ponteiro, ponteiro 1, 2 ponteiro, ponteiro 3, e assim por diante e assim por diante no circuito.
O que ele vai fazer é que fica esse endereço, dereferences-lo para obter o valor,
e muda o valor que para um Z.
Então, no final lembrar que isto é uma string, certo?
Todas as cordas têm de terminar com o caractere nulo de terminação.
Então, o que eu faço é no ponteiro 6 eu coloquei o caráter terminador nulo dentro
E agora o que estou fazendo aqui, basicamente, está a implementar printf para uma string, certo?
>> Então, quando é que printf agora, quando ela atingir o final de uma string?
Quando ela atinge o caractere nulo de terminação.
Assim, neste caso, os meus ponteiro pontos originais para o início desta matriz.
Eu imprimir o primeiro caractere fora. Eu movê-lo sobre uma.
Eu imprimir esse personagem para fora. Eu movê-lo mais.
E eu continuo fazendo isso até eu chegar ao fim.
E agora o ponteiro * final será dereference isso e obter o caractere nulo de terminação de volta.
E por isso o meu loop while é executado somente quando esse valor não é o caractere nulo de terminação.
Então, agora eu sair fora deste circuito.
E assim se eu subtrair 6 deste ponteiro,
Eu voltar todo o caminho até o início.
Lembre-se, eu estou fazendo isso porque eu tenho que ir para o início, a fim de libertá-la.
>> Então, eu sei que foi muito. Alguma pergunta?
Por favor, sim?
[Ininteligível questão Estudante]
Você pode dizer que mais alto? Desculpe.
[Estudante] No último slide direito antes de você libertou o ponteiro,
onde você estava realmente alterando o valor do ponteiro?
[Joseph] Então, aqui. >> [Estudante] Ah, ok.
[Joseph] Então, eu tenho um ponteiro menos menos, direito,
o que move a coisa de volta um, e então eu libertá-lo,
porque este ponteiro tem de ser apontado para o início da matriz.
[Estudante] Mas isso não seria necessário se tivesse parado após essa linha.
[Joseph] Então, se eu tinha parado depois disso, isso seria considerado um vazamento de memória,
porque eu não executar o livre.
[Estudante] I [ininteligível] após as três primeiras linhas em que você tinha um ponteiro [ininteligível].
[Joseph] Uh-huh. Então, qual é a pergunta lá?
Desculpe. Não, não. Vai, vai, por favor.
[Estudante] Então, você não está alterando o valor de ponteiros.
Você não teria que fazer ponteiro menos de menos.
[Joseph] Sim, exatamente.
Então, quando eu faço um ponteiro e ponteiro 2,
Eu não estou fazendo um ponteiro igual ponteiro.
Assim, o ponteiro apenas permanece apontando para o início da matriz.
É só quando eu faço mais, mais que define o valor de volta para dentro do ponteiro,
que realmente move este junto.
Tudo bem.
Mais perguntas?
>> Mais uma vez, se este for do tipo esmagador, este será coberto na sessão.
Pergunte ao seu companheiro de ensino sobre isso, e podemos responder a perguntas no final.
E, geralmente, não gostam de fazer essa coisa de menos.
Isso tem que exigir-me manter a par de quanto eu deslocamento na matriz.
Portanto, em geral, este é apenas para explicar como funciona a aritmética de ponteiro.
Mas o que nós normalmente gosto de fazer é que nós gostamos de criar uma cópia do ponteiro,
e depois nós vamos utilizar essa cópia, quando estamos nos movendo em torno do fio.
Então, nestes caso, você usar a cópia para imprimir toda a cadeia,
mas não temos que fazer como ponteiro menos 6 ou manter o controle de quanto nos mudamos isso,
apenas porque sabemos que o nosso ponto original ainda apontou para o início da lista
e tudo o que foi alterado esta cópia.
Portanto, em geral, alterar cópias do ponteiro original.
Não tente a sorte de como - não alterar cópias originais.
Tentando alterar apenas cópias de seu original.
Então, você percebe quando passamos a string em printf
você não tem que colocar uma estrela na frente dele, como fizemos com todos os dereferences outros, certo?
Então, se você imprimir o s% toda cadeia de espera é um endereço,
e, neste caso, um ponteiro ou, neste caso, como um conjunto de caracteres.
>> Caracteres, char * s, e matrizes são a mesma coisa.
Ponteiro é para personagens, e matrizes de caráter são a mesma coisa.
E assim, tudo o que temos que fazer é passar em ponteiro.
Não temos de passar em como ponteiro * ou qualquer coisa assim.
Então, matrizes e ponteiros são a mesma coisa.
Quando você está fazendo algo como x [y] aqui por uma matriz,
o que está fazendo sob o capô é que está dizendo, tudo bem, é uma matriz de caracteres,
por isso é um ponteiro.
E assim x são a mesma coisa,
e assim o que ele faz é acrescenta y para x,
que é a mesma coisa que avançar na memória muito.
E agora x + y nos dá algum tipo de endereço,
e cancelar o endereço ou siga a seta
a onde que a localização na memória é e obtemos o valor de que a localização na memória.
Então, assim que estes dois são exatamente a mesma coisa.
É apenas um açúcar sintático.
Eles fazem a mesma coisa. Eles são apenas sintática diferentes para cada outro.
>> Então, o que pode dar errado com ponteiros? Como, muito. Okay. Então, as coisas ruins.
Algumas coisas ruins que você pode fazer não está verificando se a sua chamada malloc retorna nulo, certo?
Neste caso, eu estou pedindo o sistema para me dar - o que é esse número?
Como 2 bilhões de vezes 4, porque o tamanho de um inteiro é 4 bytes.
Estou perguntando isso para como 8 mil milhões de bytes.
É claro que meu computador não vai ser capaz de me dar isso de volta muita memória.
E nós não verificar se este é nulo, por isso, quando tentamos excluir a referência que lá -
siga a seta para onde ele vai - não temos essa memória.
Isto é o que chamamos de dereferencing um ponteiro nulo.
E isso essencialmente faz com que você segfault.
Esta é uma das maneiras que você pode segfault.
Outras coisas ruins que você pode fazer - oh bem.
Que foi dereferencing um ponteiro nulo. Okay.
Outras coisas ruins - bem, para fixar que você acabou de colocar um cheque lá
que verifica se o ponteiro é nulo
e sair do programa, se acontece que malloc retorna um ponteiro nulo.
Esse é o cômico xkcd. As pessoas entendem agora. Mais ou menos.
>> Assim, memória. E eu fui por isso.
Nós estamos chamando malloc em um loop, mas cada vez que chamar malloc
estamos perdendo a noção de onde este ponteiro está apontando,
porque estamos a sobrepor-lo.
Assim, a chamada inicial para malloc me dá memória aqui.
Meus ponteiros ponteiro para este.
Agora, eu não liberá-lo, então agora eu chamar malloc novamente.
Agora ele aponta aqui. Agora, a minha memória está apontando aqui.
Apontando aqui. Apontando aqui.
Mas eu perdi o controle dos endereços de toda a memória aqui que eu alocado.
E agora eu não tenho qualquer referência a eles mais.
Então, eu não posso libertá-los fora deste circuito.
E assim, a fim de corrigir algo como isso,
se você esquecer de memória livre e você receber esse vazamento de memória,
Você tem que liberar a memória dentro deste ciclo, uma vez que você fez com ele.
Bem, isso é o que acontece. Eu sei que muitos de vocês odeiam isso.
Mas agora - yay! Você começa como 44.000 kilobytes.
Assim, é libertar-lo no final do ciclo,
e que vai apenas liberar a memória de cada vez.
Essencialmente, o programa não tem um vazamento de memória mais.
>> E agora outra coisa que você pode fazer é liberar memória que você pediu duas vezes.
Neste caso, algo malloc, você muda o seu valor.
Você libertá-lo uma vez, porque você disse que estava feito com ele.
Mas, então, libertou-lo novamente.
Isso é algo que é muito ruim.
Ele não vai inicialmente segfault,
mas depois de um tempo o que isso faz é dupla liberação corrompe a sua estrutura de pilha,
e você vai aprender um pouco mais sobre isso, se você optar por ter uma aula de como CS61.
Mas, essencialmente, depois de um tempo o computador vai ficar confuso
sobre o que posições de memória onde e onde é armazenado -
onde os dados são armazenados na memória.
E assim liberar um ponteiro duas vezes é uma coisa ruim que você não quer fazer.
>> Outras coisas que podem dar errado não está usando sizeof.
Então, neste caso, você malloc 8 bytes,
e isso é a mesma coisa que dois inteiros, certo?
Então, isso é perfeitamente seguro, mas é ele?
Bem, como Lucas falou em diferentes arquiteturas,
inteiros são de comprimentos diferentes.
Então, o aparelho que você está usando, inteiros são cerca de 4 bytes,
mas em algum outro sistema que pode ser de 8 bytes ou eles podem ser de 16 bytes.
Então, se eu usar esse número aqui,
este programa pode funcionar no aparelho,
mas não vai alocar memória suficiente em algum outro sistema.
Neste caso, é isso que o operador sizeof é usado para.
Quando chamamos sizeof (int), o que isso faz é
nos dá o tamanho de um inteiro no sistema que o programa está em execução.
Assim, neste caso, sizeof (int) retornará 4 sobre algo como o aparelho,
e agora essa vontade 4 * 2, que é de 8,
que é apenas a quantidade de espaço necessário para dois inteiros.
Em um sistema diferente, se um int é como 16 bytes ou 8 bytes,
ele só vai retornar bytes suficientes para armazenar essa quantidade.
>> E, finalmente, estruturas.
Então, se você quiser armazenar uma placa de sudoku na memória, como podemos fazer isso?
Você pode pensar como uma variável para a primeira coisa,
uma variável para a segunda coisa, uma variável para a terceira coisa,
uma variável para a quarta coisa - ruim, certo?
Então, uma melhoria que você pode fazer em cima deste é fazer um 9 x 9 matriz.
Isso é bom, mas o que se quis associar outras coisas com a placa de sudoku
gosto do que a dificuldade do conselho é,
ou, por exemplo, o que é a sua pontuação, ou quanto tempo ele é levado para resolver este fórum?
Bem, o que você pode fazer é que você pode criar uma estrutura.
O que eu estou dizendo basicamente é que eu estou definindo essa estrutura aqui,
e estou definindo um bordo sudoku que consiste de uma placa que é de 9 x 9.
>> E o que tem isso tem ponteiros para o nome do nível.
Ele também tem X e Y, que são as coordenadas de onde estou agora.
Ele também tem o tempo gasto [ininteligível], e tem o número total de jogadas que eu introduzidos até ao momento.
E por isso, neste caso, eu posso agrupar um monte de dados em apenas uma estrutura
em vez de tê-lo como voar em torno de como as diferentes variáveis
que eu realmente não posso acompanhar.
E isto nos permite ter apenas uma sintaxe agradável para tipo de referenciar coisas diferentes dentro desta estrutura.
Eu só posso fazer board.board, e tenho a placa sudoku volta.
Board.level, eu recebo como é duro.
Board.x e board.y me dar as coordenadas de onde eu poderia estar na placa.
E assim eu estou acessando o que chamamos de campos na estrutura.
Isto define sudokuBoard, que é um tipo que eu tenho.
E agora estamos aqui. Eu tenho uma variável chamada "placa" de sudokuBoard tipo.
E agora eu posso acessar todos os campos que compõem esta estrutura aqui.
>> Qualquer dúvida sobre estruturas? Sim?
[Estudante] Para int x, y, você declarou tanto em uma linha? >> [Joseph] Uh-huh.
[Estudante] Então, você poderia apenas fazer isso com todos eles?
Gosta em x, y vezes vírgula que o total?
[Joseph] Sim, você definitivamente poderia fazer isso, mas a razão de eu colocar x e y na mesma linha -
ea questão é por isso que podemos simplesmente fazer isso na mesma linha?
Por que não vamos apenas colocar todos estes na mesma linha é
x e y são relacionados uns com os outros,
e este é apenas estilisticamente mais correto, em certo sentido,
porque é o agrupamento de duas coisas na mesma linha
esse tipo de como se relacionam com o mesmo.
E eu só dividir estes separados. É só uma coisa de estilo.
Funcionalmente, não faz diferença alguma.
Quaisquer outras perguntas sobre estruturas?
Você pode definir uma Pokédex com uma estrutura.
Um Pokémon tem um número e tem uma letra, um proprietário, um tipo.
E então, se você tem uma série de Pokémon, você pode fazer uma Pokédex, certo?
Ok, legal. Assim, questões sobre estruturas. Essas são relacionadas às structs.
>> Finalmente, GDB. O que o GDB deixar você fazer? Ele permite que você depurar o programa.
E se você não tiver usado o GDB, eu seria recomendado assistir o curta
e só vai sobre o GDB é, como você trabalha com ele, como você pode usá-lo,
e testá-lo em um programa.
E assim o GDB permite fazer é que permite pausar a [ininteligível] se o seu programa
e uma linha de prática.
Por exemplo, eu quero fazer uma pausa durante a execução como a linha 3 do meu programa,
E enquanto eu estou na linha 3 eu possa imprimir todos os valores que estão lá.
E então o que nós chamamos como pausar em uma linha
é nós chamamos isso de colocar um ponto de interrupção na linha que
e então nós podemos imprimir as variáveis ​​no estado do programa na época.
>> Podemos, então, a partir daí percorrer o programa de linha-a-linha.
E então podemos olhar para o estado da pilha no momento.
E assim, a fim de usar o GDB, o que fazemos é que chamamos de bumbum no arquivo C,
mas temos que passar a bandeira ggdb.
E uma vez que estamos a fazer com que apenas executar o gdb no arquivo de saída resultante.
E para que você obtenha uma massa como de texto como este,
mas realmente tudo que você precisa fazer é digitar comandos no início.
Quebrar principal coloca um ponto de interrupção na principal.
Lista de 400 lista as linhas de código em torno da linha 400.
E assim, neste caso, você pode apenas olhar ao redor e dizer, oh,
Quero definir um ponto de interrupção na linha 397, que é esta linha,
e, em seguida, o programa é executado em que passo e que vai quebrar.
Vai parar lá, e você pode imprimir, por exemplo, o valor de baixa ou alta.
E assim há um monte de comandos que você precisa saber,
e este slideshow vai subir no site,
por isso, se você quiser apenas fazer referência a estes ou como colocá-los em suas cábulas, sinta-se livre.
>> Cool. Isso foi Quiz Revisão 0, e vamos ficar por aqui, se você tiver alguma dúvida.
Tudo bem.
>> [Aplausos]
>> [CS50.TV]