Estrutura de dados II
Carlos Oberdan Rolim
Ciência da Computação
Sistemas de Informação
Revisão
Ponteiros, passagem de
parâmetros para funções,
alocação dinâmica e estruturas
Ponteiros
Ponteiros em Linguagem C
O Que é uma variável?
É uma área da memória do computador onde é armazenado um valor….
Exemplo 1:
int a = 1;  Atribui ao endereço 1000 o valor 1
1000
1
1001
1002
1003
Variável
Posição
a
1000
Ponteiros em Linguagem C
O Que É Um Ponteiro?
Um ponteiro é uma variável que aponta para outra variável. Isto significa
que um ponteiro mantém o endereço de memória de outra variável. Em
outras palavras, o ponteiro não contém um valor no sentido tradicional,
mas sim o endereço de outra variável. Um ponteiro "aponta para" esta
outra variável mantendo uma cópia de seu endereço
Convém dizer que a expressão “apontar para...” significa “armazenar o
endereço de memória de...”
Como um ponteiro contém um endereço, e não um valor, terá duas
partes. O ponteiro contém um endereço e o endereço aponta para um
valor. Há o ponteiro e o valor para o qual ele aponta. Este fato pode
ser um tanto confuso, até você se familiarizar com ele. Superada a etapa
da familiarização, ele se torna extremamente eficaz.
Ponteiros em Linguagem C
Operadores relacionados a Ponteiros:
*(asterisco): informa que uma variável irá armazenar o endereço de outra
variável; ou:
Informa ao computador que vc deseja o valor que está no endereço
armazenado;
- Pode ser lido como “no endereço”
q = *m;
 q recebe o valor armazenado no endereço m
& (e comercial): retorna o endereço de uma variável;
- Pode ser lido como “o endereço de”
m = &count;  m recebe o endereço de count
Ponteiros em Linguagem C
int main() {
int i,j;
int *p;
p = &i;
*p=5;
j=i;
printf(("%d %d %d\n", i, j, *p);
return 0;
}
==> 5 5 5
Operadores de ponteiros
* (asterisco) indica que a variável é um ponteiro
tipo_dado *nome_ponteiro;
Ex:
int x;
int *pi;
/* compilador sabe que pi é ponteiro */
/* pi é um ponteiro para inteiro */
Operadores de ponteiros
o operador “&” quando aplicado sobre uma variável retorna
o seu endereço
Ex:
int x = 10, *pi;
pi = &x;
printf(“&x: %p pi: %p”, &x, pi);
=> &x: 0x03062fd8 pi: 0x03062fd8
Operadores de ponteiros
o operador “*” quando aplicado sobre um ponteiro retorna
o dado apontado
0xABA0
Ex:
tmp_ptr
void main () {
int *tmp_ptr;
int x, y;
x = 10;
tmp_ptr = &x;
y = *tmp_ptr; /* (*tmp_ptr) = 10 */
}
0xABA0
10
x
0xABA2
10
y
Outro exemplo ilustrado
int i;
int *p;
p = &i;
*p=5;
Relembrando...
operador *
declara-se com *
int *x
acessa-se (alterar, modificar, ler) também com *
*x = 10; // atribui o valor 10 ao local apontado pelo ponteiro ‘x’
printf(“%d”, *x); // imprime o valor armazenado no local apontado por
‘x’
observação: strings e vetores funcionam de forma diferente: um vetor ou string é
um ponteiro por definição
operador &
acessa (alterar, modificar, ler) o endereço de uma variável (que é um
ponteiro)
Exemplo de uso
 declara variavel inteiro com
valor 1
int *pt_a;
 declara um ponteiro para um
inteiro
pt_a = &a;
 ponteiro recebe o endereco da
variavel a
printf(“%d”, *pt_a);  imprime o valor apontado pelo
ponteiro
int a = 1;
Ponteiros
ponteiros são variáveis tipadas:
(int *) ≠ (float *) ≠ (char *)
As variaveis ponteiro devem sempre apontar para os tipos
de dados corretos. Uma variavel ponteiro declarada como
apontador de dados inteiros deve sempre apontar para
dados deste tipo.
Ex:
main() {
int *ip, x;
float *fp, z;
ip = &x; /* OK */
fp = &z; /* OK */
ip = &z; /* erro */
fp = &x; /* erro */
}
Ponteiros
espaço ocupado pelas variáveis
Ponteiro aponta para o tamanho segundo seu tipo
1 byte
(int *)
1 byte
(float *)
(char *)
Exemplo de uso
Exemplo:
int a = 1;
int *pt_a;
pt_a = &a;
1000
1
1001
1000
1002
1003
Variável
Posição
a
1000
pt_a
1001
Ponteiros em Linguagem C
Onde usar isto???
Funções!
Alocação Dinâmica
Não sei o tamanho que o vetor precisa ter….!
Não sei o tamanho que cada string precisa ter…
Não sei o tamanho que a matriz precisa ter…
Utilizando Ponteiros
void main() {
int x = 10;
int *pi;
pi = &x; /* *pi == 10 */
(*pi)++; /* *pi == 11 */
printf(“%d”, x);
}
==> 11
ao alterar *pi estamos alterando o conteúdo de x
Utilizando Ponteiros
void main() {
int x = 10;
int *pi, *pj;
pi = &x;
/* *pi == 10 */
pj = pi;
/* *pj == 10 */
(*pi)++;
/* (*pi, *pj, x) == 11 */
(*pj)++;
/* (*pi, *pj, x) == 12 */
printf(“%d”, x);
/* ==> 12 */
printf(“%x”, &pj); /* Endereco de x ==> 0x0c220c */
}
Ponteiros e Strings
Quando imprimimos uma cadeia de caracteres constantes
(string) com printf o que é passado é o ponteiro para a
cadeia.
Printf(“Ola como vai?”);
Dessa forma é possível carregar o endereço da string em um
ponteiro do tipo char
char * lista;
lista = "Ola como vai ?";
printf("%s", lista );
Ponteiros e Strings
Na verdade, strings são arrays de caracteres e podem ser
acessados através de char *
void main ()
{
char str[]=“abcdef”, *pc;
for (pc = str; *pc != ‘\0’; pc++)
putchar(*pc);
}
==> abcdef
o incremento de pc o posiciona sobre o próximo caracter
(byte a byte)
Ponteiros e Strings
Outra forma de mostrar uma string usando laço
char *origem = "testando";
do{
printf("%c ", *origem);
}while (*origem++); /* origem == 0 encerra o laco */
Cuidados com Strings
É comum esquecer de alocar uma área para
armazenamento de caracteres
void main() {
char *pc; char str[] = “Um string”;
strcpy(pc, str); /* erro! pc indeterminado */
...
}
Alocação dinâmica
Alocação dinâmica de memória
Alocação dinâmica x alocação estática
Pode-se alocar dinâmicamente (em tempo de execução) um
espaço de memória para uso com arrays, structs, etc...
int main() {
int *p;
p = (int *) malloc(sizeof(int));
if (p == 0) {
printf("ERRO: Sem memória\n");
return 1;
}
*p = 5;
printf("&d\n", *p);
free(p);
return 0;
}
Aloca de forma dinâmica espaço para um inteiro
Alocação dinâmica de memória
malloc
Utilizamos a função malloc() quando não conseguimos prever a
quantidade de memória que nosso programa irá necessitar.
A função malloc() pode ser utilizada em run time para determinar o
tamanho de um array.
Exemplo
char * p;
p = malloc(50);
free
Libera memória alocada previamente
Exemplo
free(p);
Alocação dinâmica de memória
void main() {
int numero = 10;
int *arranjo;
arranjo=(int *)malloc(numero * sizeof(int));
for (i=0; i < numero; i++) {
arranjo[i] = i;
}
free(arranjo);
}
Aloca de forma dinâmica espaço para um array de inteiros de 10 posições
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
int main() {
int *a;
int i, k, m, min, temp, n;
/* Alocar memória para guardar o array */
printf("Quantos números quer ordenar? ");
scanf("%d", &n);
/* Ordenar o array */
for( k=0; k<=n-1; k++ ) {
/* descobre o índice do mínimo */
min = a[k];
m = k;
for( i=k; i<=n-1; i++ )
if( a[i] < min ){
min = a[i];
m = i;
}
/* troca a[k] com a[m] */
temp = a[k];
a[k] = a[m];
a[m] = temp;
a = (int *) malloc( n * sizeof(int) );
if( a == NULL ) {
printf("ERRO: nao ha memoria.\n");
exit(1);
}
/* Receber os valores a ordenar */
for (i=0; i<n; i++) {
printf("%d.º numero -> ",i+1);
scanf("%d",&a[i]);
}
}
/* Escrever os elementos ordenados */
for( i=0; i<n; i++ )
printf("%d ", a[i]);
printf("\n");
free( a ); /* libertar a memória */
getche();
return 0;
}
Estrutura de Dados Compostos
(Structs)
Definição
Uma estrutura (struct) ou registro em C é uma coleção de um
ou mais valores, agrupados sob um único nome.
Estruturas constituem um recurso importante para organizar
os dados utilizados por um programa graças à possibilidade
de tratar um grupo de valores como uma única variável
Exemplo de uso
struct ponto
{
int x;
int y;
};
struct funcionario
{
int registro;
char nome[30];
char depto[5];
float salario;
};
Exemplo de uso
As declarações de ponto e funcionario, definem os
respectivos tipos de dados, que podem ser utilizados em
declarações de variáveis. Exemplos:
struct ponto p1, p2, p3;
struct funcionario Joao;
Na primeira declaração, estão sendo declaradas as variáveis
p1, p2 e p3 do tipo ponto. Na segunda declaração, é
declarada a variável Joao do tipo funcionário.
Exemplo de uso
Para uma variável do tipo ponto, dizemos que x e y são seus
campos ou membros. Os campos de uma variável podem
ser acessados individualmente como variáveis usando-se o
nome da variável seguido de "." e o nome do campo.
Exemplos:
p1.x = 10;
p1.y = 20;
p2.x = p1.x + 5;
p2.y = p2.y + 5;
Além disso, é possível atribuir a uma estrutura o valor de
outra estrutura do mesmo tipo. Exemplos:
funcionario f = Joao;
p3 = p2;
Estruturas complexas
Os campos de uma estrutura podem ser de qualquer tipo:
tipos simples (int, char, float, etc), vetores, ou até mesmo
estruturas. Exemplo:
struct retangulo {
struct ponto pa;
struct ponto pb;
}
Uso de estruturas com funções
Uma vez que o tipo de uma estrutura foi declarado, é
possível utilizá-lo em outras declarações (variáveis simples,
vetores, funções, etc).
...
struct ponto poligono[10];
...
float dist(ponto p, ponto q) {
int dx = p.x - q.x;
int dy = p.y - q.y;
return sqrt((double)dx*dx + (double)dy*dy);
}
Passagem de estrutura por referência
Uma estrutura pode ser passada como parâmetro por
referência numa função. Quando se usa uma referência
(apontador), o acesso aos campos da mesma é feito através
do operador "->" ao invés de ".". Exemplo:
void moveP(ponto* p, int dx, int dy){
p -> x += dx;
p -> y += dy;
}
...
moveP(&(r -> pa), dx, dy);
moveP(&(r -> pb), dx, dy);
Retornando uma estrutura
Uma função pode ter uma estrutura como valor de retorno
struct ponto constroiPonto(int x, int y){
struct ponto temp;
temp.x = x;
temp.y = y;
return temp;
}
...
struct ponto Origem = constroiPonto(0,0);
Declaração com valores iniciais
Ao declararmos uma estrutura, podemos também definir o
seu valor inicial, de forma análoga a aquela utilizada para
vetores. Exemplos:
struct ponto origem = {0,0};
...
struct ponto trapezio[] = { { 5,5}, {5, 10}, {10,5}, {10,13} };
...
Usando ponteiros com structs
struct data{
int dia;
int mês;
int ano;
};
Definindo uma variável do tipo data
struct data dt;
Definindo um ponteiro para dt
struct data *pdt = &dt;
Fazendo referência a um elemento da estrutura
dt.dia ou (*pdt).dia ou pdt->dia
dt.mes ou (*pdt).mes ou pdt->mês
dt.ano ou (*pdt).ano ou pdt->ano
#include <stdio.h>
typedef struct estrutura{
int valor;
} ESTRUTURA;
Exemplo de programa demonstrando uso
de ponteiro, passagem de parâmetro
para função e estrutura
void incrementa(ESTRUTURA * e){
printf(" Valor --> %i \n", e->valor);
printf(" Valor --> %i \n", (*e).valor); /* outra forma de acessar */
(e->valor)++; /* incrementa valor */
}
int main(){
ESTRUTURA d; /* declara variavel struct */
d.valor = 0;
/* atribui valor inicial */
printf("Antes da funcao --> %d \n", d.valor);
incrementa(&d); /* invoca a funcao */
printf("Apos a funcao --> %d\n", d.valor);
return 0;
}
Alocação dinâmica de estruturas
É preciso armazenar esse endereço
retornado pela malloc num ponteiro
de tipo apropriado
Para alocar um tipo de dado que
ocupa vários bytes, é preciso recorrer
ao operador sizeof, que diz quantos
bytes o tipo especificado tem
Outra forma de declaração
typedef struct tipo_data{
int dia, mes, ano;
} DATA;
Vamos utilizar outra forma de
declaração da struct:
struct tipo_data{
int dia, mes, ano;
};
typedef struct tipo_data DATA;
DATA *d;
d = malloc (sizeof (DATA));
d->dia = 31;
d->mes = 12;
d->ano = 2008;
ATENÇÃO: data é o nome to tipo