Slides 1

Prévia do material em texto

Revisão
Universidade de São Paulo
Instituto de Ciências Matemáticas e de Computação
Departamento de Ciências de Computação
Rodrigo Fernandes de Mello
http://www.icmc.usp.br/~mello
mello@icmc.usp.br
   
Algoritmo
● Definição de Algoritmo:
● Procedimento  computacional  bem  definido  que  recebe 
valores de entrada e produz valores de sa ída
● Sequencia de passos computacionais que transformam uma 
entrada em uma saída
● Exemplos usualmente vistos em ICC 1:
● Como trocar uma lâmpada?
● Como trocar um pneu de um veículo?
● Como fazer um bolo?
   
Algoritmo
● Exemplos:
● Calcular a potência dada uma base e um expoente
● Calcular os números da sequencia de Fibonacci
● Calcular uma série
● Atenção:
● Montar inicialmente pseudocódigo
● Produzir código fonte
● Compilar (Indicação de Uso: Compilador GCC sobre Linux):
              gcc ­pg ­o programa programa.c
● Utilizar gprof:
              gprof programa
● O  site  http://virtualboximages.com/  tem  máquinas  virtuais  Linux 
disponíveis  para  Virtual  Box:  Ubuntu,  CentOS,  Sabayon,  Debian, 
LinuxMint, OpenSUSE, etc.
   
Relembrar
● Estruturas/Conceitos comumente utilizados em programa ção:
● Declaração de variáveis
● While
● Do­While
● If
● Switch
● Declaração de Funcões:
– A funcão main
– Escrevendo funções
● Passagem de parâmetros:
– Por valor
– Por referência
   
Relembrar
● Estruturas/Conceitos comumente utilizados em programa ção:
● Vetores:
– Unidimensionais
– N­Dimensionais
● Ponteiros
● Outros:
– Escrita e Leitura em Arquivos
– Macros
– Struct
– Union
– Typedef
   
Relembrar
● Conceitos Essenciais e Ponteiros
#include <stdio.h>
int main(int argc, char *argv[ ]) {
int i;
return 0;
}
i 0x0001
   
Relembrar
● Conceitos Essenciais e Ponteiros
10#include <stdio.h>
int main(int argc, char *argv[ ]) {
int i;
i = 10;
return 0;
}
i 0x0001
   
Relembrar
● Conceitos Essenciais e Ponteiros
● Quantos bytes tem a variável i? 10
#include <stdio.h>
int main(int argc, char *argv[ ]) {
int i;
i = 10;
printf(“%d bytes\n”, sizeof(i));
return 0;
}
i 0x0001
   
Relembrar
● Conceitos Essenciais e Ponteiros
● Quantos bytes tem a variável i?
● Essa variável tem 4 bytes
● Como cada posição de memória
                       tem 1 byte, então...
#include <stdio.h>
int main(int argc, char *argv[ ]) {
int i;
i = 10;
printf(“%d bytes\n”, sizeof(i));
return 0;
}
 i 0x0001
 0x0002
 0x0003
 0x0004
   
Relembrar
● Conceitos Essenciais e Ponteiros
● Essa variável tem 4 bytes
● Mas como o computador armazena
                   um valor nessa variável?
● Mas como nosso computador armazena?
 i 0x0001
 0x0002
 0x0003
 0x0004
Little Endian Big Endian
4.o 3.o 2.o 1.o 1.o 2.o 3.o 4.o
Há dois padrões de armazenamento de Inteiros
   
Relembrar
● Conceitos Essenciais e Ponteiros
● Essa variável tem 4 bytes
● Mas como o computador armazena
                   um valor nessa variável?
● Mas como nosso computador armazena?
● Intel   Little Endian→
● Sun Microsystems   Big Endian→
● Ou seja, depende do padrão adotado pelo fabricante!
 i 0x0001
 0x0002
 0x0003
 0x0004
Little Endian Big Endian
4.o 3.o 2.o 1.o 1.o 2.o 3.o 4.o
Há dois padrões de armazenamento de Inteiros
   
Relembrar
● Mais importante é verificar!!!
● Façamos um código para isso
● Testar com vários valores inteiros
● Usar ponteiros para isso...
– Comecar com ponteiro do tipo int
– Continuar com ponteiro do tipo char
● Tudo isso que vimos é válido para máquinas de 
32 bits
● O que significa isso?
● Testar em máquinas de 64 bits
● Como fica?
 i 0x0001
 0x0002
 0x0003
 0x0004
   
Relembrar
● MUITO IMPORTANTE:
● O tipo de um ponteiro define como ele irá percorrer (ou mais 
formalmente, endereçar) a memória
● Ao  incrementarmos  o  ponteiro  abaixo  em  uma  unidade, 
incrementamos 4 unidades em  termos de endereço para o 
qual o ponteiro irá apontar
                    int *p
● Ao  incrementarmos  o  ponteiro  abaixo  em  uma  unidade, 
incrementamos  1  unidade  em  termos  de  endereço  para  o 
qual o ponteiro irá apontar
                    char *p
   
Relembrar
● Como fica a memória para o código
     a seguir? i 0x00000001
 0x00000002
 0x00000003
 0x00000004
#include <stdio.h>
int main(int argc, char *argv[ ]) {
int i = 10;
 int *p = &i;
return 0;
}
0x01
0x00
0x00
0x00
 p 0x00000005
 0x00000006
 0x00000007
 0x00000008
Supondo um computador de 32 bits
O qual pode enderecar até 2 elevado a 32 
palavras de memória
Em que cada palavra assumimos como 1 
Byte → total de 4,294,967,296 bytes = 4 GB
   
Relembrar
● Como fica a memória para o código
     a seguir? i 0x00000001
 0x00000002
 0x00000003
 0x00000004
#include <stdio.h>
int main(int argc, char *argv[ ]) {
int i = 10;
 char *p = (char *) &i;
return 0;
}
0x01
0x00
0x00
0x00
 p 0x00000005
 0x00000006
 0x00000007
 0x00000008
Supondo um computador de 32 bits
O qual pode enderecar até 2 elevado a 32 
palavras de memória
Em que cada palavra assumimos como 1 
Byte → total de 4,294,967,296 bytes = 4 GB
   
Relembrar
● Podemos percorrer com um ponteiro outras variáveis?
● Sim
● Para isso é importante conhecer o tamanho de cada tipo após 
alocado na memória:
● 1 char ocupa quanto?
● 1 int?
● 1 long?
● 1 short?
● 1 float?
● 1 double?
   
Relembrar
● Floats  e  Doubles  são  armazenados  de  maneira  diferente  de 
inteiros
   
Relembrar
● Mas como uma cadeia de caracteres (string)  é armazenada na 
memória?
'T'str 0x0001
'e'
's'
't'
 0x0002
 0x0003
 0x0004
'e' 0x0005
'\0' 0x0006
Strings são armazenadas de maneira 
contígua na memória
Os caracteres são armazenados na 
mesma ordem em que ocorrem na 
cadeia de caracteres
O caracter '\0' indica fim da string
Se não houvesse esse caracter, 
precisaríamos de outra variável 
inteira para guardar o tamanho da 
string → ocuparia mais memória!
   
Relembrar
● Mas como uma cadeia de caracteres (string)  é armazenada na 
memória?
'T'str 0x0001
'e'
's'
't'
 0x0002
 0x0003
 0x0004
'e' 0x0005
'\0' 0x0006
Cada caracter tem um valor 
numérico
Palavra de memória não guarda o 
caracter, mas sim seu valor 
numérico
Resta convertermos de número para 
caracter
Algo que é feito, por exemplo, 
pela máscara %c e %s na 
linguagem C
   
Relembrar
● Mas como uma cadeia de caracteres (string)  é armazenada na 
memória?
'T'str 0x0001
'e'
's'
't'
 0x0002
 0x0003
 0x0004
'e' 0x0005
'\0' 0x0006
Há padrões para conversão de 
caracteres em valores inteiros e 
vice-versa:
O mais comumente utilizado é 
o ASCII (American Standard 
Code for Information 
Interchange)
   
Relembrar
● Mas como uma cadeia de caracteres (string)  é armazenada na 
memória?
'T'str 0x0001
'e'
's'
't'
 0x0002
 0x0003
 0x0004
'e' 0x0005
'\0' 0x0006
Como fazemos a contagem de 
caracteres de uma String?
Isso permite treinarmos 
ponteiros!
   
Relembrar
● Mas como uma cadeia de caracteres (string)  é armazenada na 
memória?
'T'str 0x0001
'e'
's'
't'
 0x0002
 0x0003
 0x0004
'e' 0x0005
'\0' 0x0006
Como copiamos uma cadeia de 
caracteres constante para uma 
região da memória?
Isso permite treinarmos 
ponteiros!
   
Relembrar
● Mas como uma cadeia de caracteres (string)  é armazenada na 
memória?
'T'str 0x0001
'e'
's'
't'
 0x0002
 0x0003
 0x0004
'e' 0x0005
'\0' 0x0006
Como concatenamos uma cadeia de 
caracteres constante com uma outra 
string?
Isso permite treinarmos 
ponteiros!
   
Relembrar
● Relembrar alocação dinâmica de memória:
● malloc / realloc / free
● Exemplos:
● Usuário digita valores e mantemos em um vetor
– Iniciar com vetor de tamanho fixo
– Incrementar vetor usando malloc / free
– Incrementar vetor usando realloc● Leitura  de  caracteres  do  teclado  e  armazenamento  em 
string apenas com tamanho necessário
   
Relembrar
● Como  funciona  ponteiro  de 
ponteiro?
● Útil para:
– montarmos,  por  exemplo, 
listas de nomes de pessoas
– “Quebrar”  uma  string  em 
função  de  um  caracter 
separador
'O' 0x0001
'i'
'\0'
'B'
 0x0002
 0x0003
 0x0004
'y' 0x0005
'e' 0x0006
'\0'
char *p1 char *p2
char **ponteiro    
Relembrar
● Como funciona ponteiro de ponteiro?
● Útil para:
– Criarmos um editor de textos
– montarmos, por exemplo, listas de nomes de pessoas
– “Quebrar”  uma  string  em  função  de  um  caracter 
separador
● Implementar  a  função  explode(str,  sep)  que  retorna  as 
substrings contidas na string str separadas por sep
   
Relembrar
● Como funcionam ponteiros para funções?
● Podemos apontar para uma função tal como uma variável
● Isso é possível, pois o código de uma função também está 
na memória e, portanto, tem um endereço
● Para que é útil?
– Sistemas operacionais como Linux, Windows, etc. usam 
para colocar programas em execução
– Podemos “chamar” uma função usando outro nome
   
Relembrar
● Relembrar leitura e escrita em arquivos:
● Arquivo texto
● Arquivo binário
   
Relembrar
● Macros:
– Criar uma macro para soma
– Criar uma macro para multiplicação:
● Simples
● Bit Shift (multiplicação por 2)
– Criar uma macro para divisão:
● Simples
● Bit Shift (divisão por 2)
   
Relembrar
● Relembrar leitura e escrita em arquivos:
● Struct
– São registros
– Criar um struct para armazenar dados de uma pessoa
● Typedef
– Definir um novo nome para um tipo primitivo
– Definir um nome para um struct
   
Exercícios
● Implemente  um  editor  de  textos  que  recebe  um  par ágrafo 
digitado e o armazena usando ponteiro para ponteiros
● Leia um arquivo texto, a cada final de linha, adicione a linha lida 
na estrutura de ponteiro para ponteiros
● Implemente  uma  função  substituir(str1,  str2,  str3)  que 
procura pela string str2 dentro da string str1. Ao encontrar str2, 
substitui sua ocorrência por str3
● Leia todo o conteúdo de um arquivo texto e o armazene todo o 
conteúdo em um ponteiro para char, ou seja, char *
● Deve­se  utilizar  realloc  para  que  reservemos  apenas  a 
quantidade de memória que necessitamos
   
Exercícios
● Ler  valores  reais  armazenados  em  um  arquivo  texto  e 
armazená­los em uma estrutura double *
● Após ler todos os números, realizar:
– O somatório deles
– O produtório deles