INF1005: Programação 1
Vetores e Ponteiros
Tópicos Principais
• Declaração e Inicialização de Vetores
• Exemplos de Manipulação de Vetores
• Ponteiros
• Passagem de Vetores e Ponteiros para
Funções
• Busca em Vetores
Introdução
• Vetores são um mecanismo que nos
permite armazenar um conjunto de valores
na memória do computador
• O vetor é uma fileira de variáveis de
mesmo tipo que ocupa uma região
contínua de memória.
Introdução
Um vetor de inteiros
3
1
9
5
1
Declaração de Vetores
• Para declarar um vetor, precisamos
especificar o tipo das variáveis do vetor
(um vetor só pode armazenar um tipo de
variável) e o tamanho do vetor.
Declaração de Vetores
tipo nome_vetor[tamanho];
• Para declarar um vetor, precisamos
especificar o tipo das variáveis do vetor
(um vetor só pode armazenar um tipo de
variável) e o tamanho do vetor.
Declaração de Vetores
int nome_vetor[5];
?
?
?
?
?
A declaração acima reserva um
espaço na memória para 5 inteiros
Declaração de Vetores
int nome_vetor[5];
?
?
?
?
Esse espaço de memória é
acessado através da palavra
nome_vetor
?
Declaração de Vetores
int nome_vetor[5];
?
?
?
?
?
Todas as variáveis do vetor
inicialmente possuem valores
não relevantes para a aplicação
Inicializando posições
do vetor
int nome_vetor[5];
0
1
2
3
4
?
?
?
?
?
Inicializando posições
do vetor
int nome_vetor[5];
0
1
2
3
4
5
?
?
?
?
nome_vetor[0] = 5;
Inicializando posições
do vetor
int nome_vetor[5];
0
1
2
3
4
5
?
?
7
?
nome_vetor[0] = 5;
nome_vetor[3] = 7;
Inicializando posições
do vetor
int nome_vetor[5];
0
1
2
3
4
5
2
?
7
?
nome_vetor[0] = 5;
nome_vetor[3] = 7;
nome_vetor[1] = 2;
Inicializando posições
do vetor
int nome_vetor[5];
0
1
2
3
4
5
2
3
7
?
nome_vetor[0] = 5;
nome_vetor[1] = 2;
nome_vetor[3] = 7;
nome_vetor[2] = 3;
Exemplos de
Declaração
• int a, b[20];
• float c[10];
• double d[30], e, f[5];
Exemplos de
Declaração
• int a, b[20];
• float c[10];
• double d[30], e, f[5];
Declara um inteiro e um
vetor de inteiros de
20 posições
Exemplos de
Declaração
• int a, b[20];
• float c[10];
• double d[30], e, f[5];
Declara um vetor de
variáveis de tipo float
de 10 posições
Exemplos de
Declaração
• int a, b[20];
• float c[10];
• double d[30], e, f[5];
Declara um vetor de
30 posições,
uma variável e outro
vetor de 5 posições.
Todas as variáveis são
do tipo double.
Exemplo de Declaração
com Inicialização
int v[5] = {12, 5, 34, 32, 9};
0
1
2
3
4
12
5
34
32
9
Exemplos
• Imprimindo valores de um vetor
• Somatório
• Calculando média e variância
• Histograma
• Polinômios
Imprimindo valores de
um vetor
#include <stdio.h>
int main (void)
{
int i;
float v[6] = {2.3, 5.4, 1.0, 7.6, 8.8, 3.9};
for (i=0; i<6; i++) {
printf("%f", v[i]);
}
return 0;
}
Somatório
#include <stdio.h>
int main (void)
{
int i;
float s = 0.0;
float v[6] = {2.3, 5.4, 1.0, 7.6, 8.8, 3.9};
for (i=0; i<6; i++) {
s = s + v[i];
}
printf("%f", s);
return 0;
}
Calculando Média e
Variância
• Média
• Variância
Calculando média e
variância
#include <stdio.h>
int main (void)
{
int i;
float m = 0.0, var = 0.0;
float v[6] = {2.3, 5.4, 1.0, 7.6, 8.8, 3.9};
for (i=0; i<6; i++) {
m = m + v[i];
}
m = m / 6;
for(i=0; i<6; i++) {
var = var + (v[i] - m) * (v[i] - m);
}
var = var / 6;
return 0;
}
Histograma
• Um histograma
mostra a
distribuição de
valores em um
conjunto
Histograma
• Problema: Queremos calcular o histograma
das notas dos alunos em uma prova
(quantos notas estão entre 0.0 e 1.0, 1.0 e
2.0, etc).
Histograma
/*
n: numero de notas em v --- v: notas --- min: nota minima
max: nota maxima --- ni: numero de intervalos no histograma --- h: histograma
*/
void histograma (int n, float v[ ], float min, float max, int ni, float h[ ])
{
int i, j;
float delta = (max - min) / ni;
/* inicializa vetor de histograma */
for (i=0; i<ni; i++) {
h[i] = 0;
}
/* calcula número de ocorrências em cada intervalo */
for (j=0; j<n; j++) {
i = (int) ((v[j]-min) / delta);
if (i == ni) {
i = ni-1;
}
h[i]++;
}
/* calcula freqüência */
for (i=0; i<ni; i++) {
h[i] = h[i] / n;
}
}
Polinômios
• Um polinômio é uma função matemática
definida por:
• Onde a0, a1, ..., ag são números reais
denominados coeficientes do polinômio e
g é um número inteiro que representa o
grau do polinômio
Polinômios
• Podemos usar vetores para representá-los
2x3 + 8x + 5
5
8
0
2
Avaliação de
Polinômios
• Avaliar um polinômio significa calcular o
valor númerico do polinômio para um
determinado x (y = a(x)).
Avaliação de
Polinômios
número de
coeficientes
coeficientes
Igualdade de
Polinômios
• Dois polinômios de mesmo grau são iguais
se todos os seus coeficientes de mesmo
grau forem iguais
Igualdade de
Polinômios
int igualdade (int n, float a[ ], float b[ ])
{
int i;
for (i=0; i<n; i++) {
if (a[i] != b[i]) {
return 0;
}
}
return 1;
}
Soma de Polinômios
• A soma de dois polinômios de mesmo grau
é dada por:
• Que matematicamente é expressa por:
Soma de Polinômios
entrada
saída
Derivada de Polinômio
• Se um polinômio possui grau g, sua
derivada tem grau g-1 e pode ser
expressada por:
• Os termos da derivada são expressos por:
Derivada de Polinômio
Produto de Polinômios
• O produto de dois polinômios de grau g
gera outro polinômio de grau 2g.
Produto de Polinômios
• Exemplo:
- (1 + 2x + 3x ) * (2 + 3x + 4x )
- v[0] = 1 * 2
- v[1] = 1*3 + 2*2
- v[2] = 1*4 + 2*3 + 3*2
- v[3] = 2*4 + 3*3
- v[4] = 3*4
2
2
Produto de Polinômios
• Como o grau do polinômio de saída é 2g e
sabemos que n, número de coeficientes do
polinômio de entrada, é igual a g+1, o
número de coeficientes do vetor de saída
é:
2g+1 = 2(n-1)+1 = 2n-1
Produto de Polinômios
void produto(int n, float a[], float b[], float c[]) {
int i, j;
int m = 2*n - 1;
for (i = 0; i < m; i++) {
c[i] = 0.0;
}
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
c[i+j] += a[i] * b[j];
}
}
}
Ponteiros
• Ponteiros são variáveis que armazenam
endereços de memória.
Ponteiros
Variável Endereço Conteúdo
int main (void){
int a;
int *p;
p = &a;
*p = 2;
return 0;
}
a
0
?
p
4
?
8
12
Ponteiros
Variável Endereço Conteúdo
int main (void){
int a;
int *p;
p = &a;
*p = 2;
return 0;
}
variável
ponteiro para
int
a
0
?
p
4
?
8
12
Ponteiros
Variável Endereço Conteúdo
int main (void){
int a;
int *p;
p = &a;
*p = 2;
return 0;
}
a
0
?
p
4
0
8
12
Ponteiros
Variável Endereço Conteúdo
int main (void){
int a;
int *p;
p = &a;
*p = 2;
return 0;
}
a
0
2
p
4
0
8
12
Operadores usados
com Ponteiros
• Operador unário & (“endereço de”)
• Operador unário * (“conteúdo de”)
Operadores usados
com Ponteiros
int main (void){
int a;
int *p;
p = &a;
*p = 2;
return 0;
}
int main (void){
int a;
int *p = &a;
*p = 2;
return 0;
}
Cuidados ao usar
ponteiros
int main ( void ) {
int a, b, *p;
a = 2;
*p = 3;
b = a + (*p);
printf(" %d ", b);
return 0;
}
Cuidados ao usar
ponteiros
int main ( void ) {
int a, b, *p;
a = 2;
*p = 3;
b = a + (*p);
printf(" %d ", b);
return 0;
}
3 é escrito
em uma área
de memória
desconhecida
Aritmética de
Ponteiros
• Se p é um ponteiro para uma variável,
então a expressão p+1 gera o endereço
necessário para acessar uma variável de
mesmo tipo adjacente.
Aritmética de
Ponteiros
Variável Endereço Conteúdo
int main (void){
int v[2];
int *p;
p = v;
p = p + 1;
*p = 5;
return 0;
}
v[0]
0
?
v[1]
4
?
p
8
?
12
Aritmética de
Ponteiros
Variável Endereço Conteúdo
int main (void){
int v[2];
int *p;
p = v;
p = p + 1;
*p = 5;
return 0;
}
v[0]
0
?
v[1]
4
?
p
8
0
12
Aritmética de
Ponteiros
Variável Endereço Conteúdo
int main (void){
int v[2];
int *p;
p = v;
p = p + 1;
*p = 5;
return 0;
}
v[0]
0
?
v[1]
4
?
p
8
4
12
Aritmética de
Ponteiros
Variável Endereço Conteúdo
int main (void){
int v[2];
int *p;
p = v;
p = p + 1;
*p = 5;
return 0;
}
v[0]
0
?
v[1]
4
5
p
8
4
12
Relação entre vetores e
ponteiros
• Um ponteiro é uma variável capaz de
armazenar um endereço de memória
qualquer.
• O nome de um vetor é um endereço fixo
de memória.
Relação entre vetores e
ponteiros
para um vetor a
a[i]
*(a + i)
é equivalente a
Relação entre vetores e
ponteiros
#include <stdio.h>
#include <stdio.h>
int main (void)
{
int i;
float v[6] = {2.3, 5.4, 1.0,
7.6, 8.8, 3.9};
int main (void)
{
int i;
float v[6] = {2.3, 5.4, 1.0,
7.6, 8.8, 3.9};
}
for (i=0; i<6; i++) {
printf("%f", v[i]);
}
for (i=0; i<6; i++) {
printf("%f", *(v + i));
}
return 0;
return 0;
}
Passagem de Vetores e
Ponteiros para Funções
• Nós podemos passar vetores e ponteiros
como parâmetros para funções.
• Isso permite que dentro de uma função,
sejam alteradas variáveis de outras funções.
Passagem de Vetores e
Ponteiros para Funções
int main (void)
{
int i;
float vet[6] = {2.3, 5.4, 1.0,
7.6, 8.8, 3.9};
float m;
m = calculaMedia(vet, 6);
zerar(vet, 6);
return 0;
}
float calculaMedia(float v[], int n)
{
float m = 0.0f;
int i;
for(i = 0 ; i < n ; i++) {
m += v[i];
}
m /= n;
return m;
}
void zerar(float v[], int n) {
int i;
for(i = 0 ; i < n ; i++) {
v[i] = 0;
}
}
Passagem de Vetores e
Ponteiros para Funções
void zerar(float[] v, int n) {
int i;
for(i = 0 ; i < n ; i++) {
v[i] = 0;
}
}
int main (void)
{
int i;
float vet[6] = {2.3, 5.4, 1.0,
7.6, 8.8, 3.9};
float m;
m = calculaMedia(vet, 6);
zerar(vet, 6);
return 0;
}
v possui o mesmo
endereço de vet
Passagem de Vetores e
Ponteiros para Funções
• Problema: Queremos criar uma função que
troca dois valores passados para ela.
Passagem de Vetores e
Ponteiros para Funções
#include <stdio.h>
void troca(int* pa, int* pb) {
int tmp=*pb;
*pb=*pa;
*pa=tmp;
}
int main (void) {
int a=10, b=20;
troca(&a,&b);
}
Passagem de Vetores e
Ponteiros para Funções
#include <stdio.h>
void troca(int* pa, int* pb) {
int tmp=*pb;
*pb=*pa;
*pa=tmp;
}
int main (void) {
int a=10, b=20;
troca(&a,&b);
}
Passagem de Vetores e
Ponteiros para Funções
#include <stdio.h>
void troca(int* pa, int* pb) {
int tmp=*pb;
*pb=*pa;
*pa=tmp;
}
int main (void) {
int a=10, b=20;
troca(&a,&b);
}
Passagem de Vetores e
Ponteiros para Funções
#include <stdio.h>
void troca(int* pa, int* pb) {
int tmp=*pb;
*pb=*pa;
*pa=tmp;
}
int main (void) {
int a=10, b=20;
troca(&a,&b);
}
Passagem de Vetores e
Ponteiros para Funções
#include <stdio.h>
void troca(int* pa, int* pb) {
int tmp=*pb;
*pb=*pa;
*pa=tmp;
}
int main (void) {
int a=10, b=20;
troca(&a,&b);
}
Busca em Vetores
• Problema: Implemente uma função que
busca por um inteiro em um vetor de
inteiros.
Busca em Vetores
int busca(int n, int[] vet, int elem) {
int i;
for(i = 0 ; i < n ; i++) {
if(vet[i] == elem) {
return i;
}
}
return -1;
}
Busca em Vetores
int busca_ord(int n, int[] vet, int elem) {
int i;
for(i = 0 ; i < n ; i++) {
if(vet[i]) {
return i;
}
else if(vet[i] > elem) {
return -1;
}
}
return -1;
}
Referências
•
Waldemar Celes, Renato Cerqueira, José
Lucas Rangel, Introdução a Estrutura de Dados,
Editora Campus (2004).
•
Capítulo 4 - Ponteiros e Endereços de
Variáveis
Waldemar Celes e Roberto Ierusalimschy,
Apostila de Programação.
-
Capítulo 7 - Vetores.