99
23/11/12 Estrutura de Dados II 1 TCC0216 Estrutura de Dados II Revisão - Ponteiros e Alocação Dinâmica Prof. José Viterbo

Aula 2 - Linguagem C - Ponteiros e Alocação Dinâmica.pdf

Embed Size (px)

Citation preview

  • 23/11/12 Estrutura de Dados II 1

    TCC0216 Estrutura de Dados II

    Reviso - Ponteiros e Alocao Dinmica

    Prof. Jos Viterbo

  • 23/11/12 Estrutura de Dados II 2

    Tpicos Principais

    Vetores Exemplos de manipulao de vetores Ponteiros Vetores x Ponteiros Alocao dinmica Tipos estruturados Ponteiros para tipos estruturados

  • 23/11/12 Estrutura de Dados II 3

    Vetores Oferecem um mecanismo que permite

    armazenar um conjunto de valores na memria do computador. Este mecanismo permite ler os valores e armazen-

    los na memria. Posteriormente, estes valores podem ser livremente

    processados de forma eficiente, pois j esto na memria do computador.

  • 23/11/12 Estrutura de Dados II 4

    Vetores Podemos armazenar um conjunto de valores na

    memria do computador atravs do uso de vetores (arrays, em ingls): O vetor a forma mais simples de organizarmos

    dados na memria do computador.

    Com vetores, os valores so armazenados na memria do computador em seqncia, um aps o outro, e podemos livremente acessar qualquer valor do conjunto.

  • 23/11/12 Estrutura de Dados II 5

    Declarao de vetores Na linguagem C, quando declaramos um vetor

    (conceito anlogo ao de declarao de uma varivel simples) devemos informar a dimenso do vetor, isto , o nmero mximo de elementos que poder ser armazenado no espao de memria que reservado para o vetor.

    Devemos tambm informar o tipo dos valores que sero armazenados no vetor (por exemplo, int, float ou double). Num vetor, s podemos armazenar valores de um mesmo tipo.

  • 23/11/12 Estrutura de Dados II 6

    Declarao de vetores int x[10];

    Esta declarao reserva um espao de memria para armazenar 10 valores inteiros e este espao de memria referenciado pelo nome x.

    Inicializao de algumas posies do vetor x: x[0] = 5; x[1] = 11; x[4] = 0; x[9] = 3;

  • 23/11/12 Estrutura de Dados II 7

    Declarao de vetores int a, b[20]; /* declara uma varivel simples e um vetor */ float c[10]; /* declara um vetor */ double d[30], e, f[5]; /* declara dois vetores e uma varivel simples */

    Declara e j inicializa: int v[5] = {12, 5, 34, 32, 9};

    Declara e j inicializa (o tamanho fica definido a partir do nmero de elementos declarados): float u[ ] = {1. 5, 3.3, 4.2};

  • 23/11/12 Estrutura de Dados II 8

    Vetores exemplo: imprimindo valores

    #include

    int main (void){ int i; float v[6] = {2.3, 5.4, 1.0, 7.6, 8.8, 3.9}; for (i=0; i

  • 23/11/12 Estrutura de Dados II 9

    Vetores exemplo: mdia dos valores

    #include

    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

  • 23/11/12 Estrutura de Dados II 10

    Vetores exemplo: clculo da mdia e varincia

    Agora que conhecemos como trabalhar com vetores podemos ter um algoritmo que calcula a mdia e a varincia de um conjunto de valores armazenados em um arquivo.

  • 23/11/12 Estrutura de Dados II 11

    Vetores exemplo: clculo da mdia e varincia

    Vamos ler os valores das notas de um arquivo, armazen-los em um vetor e fazer o clculo da mdia e da varincia.

  • 23/11/12 Estrutura de Dados II 12

    Vetores exemplo: clculo da mdia e varincia

    #include int main (void){ int i; int n; /* nmero de notas lidas */ float m; /* mdia dos valores */ float v; /* varincia dos valores */ float notas[50]; /* vetor com as notas */

    scanf("%d", &n); /* le numero de notas (50) { printf("Tamanho invalido\n"); return 0; } /* L valores do teclado e armazena no vetor */ for(i=0, i

  • 23/11/12 Estrutura de Dados II 13

    Vetores exemplo: clculo da mdia e varincia

    ...

    /* Calcula mdia dos valores */ m = 0.0; for (i=0; i

  • 23/11/12 Estrutura de Dados II 14

    Ponteirosint main ( void ){ int a, b; int *p; p = &a; *p = 2; printf(" %d ", a); p = &b; b = a + 2; printf(" %d ", *p); return 0;}

    imprime o valor 2 e o valor...

  • 23/11/12 Estrutura de Dados II 15

    - Operadores usados com Ponteiros

    Operador unrio & (endereo de)Operador unrio * (contedo de)

    Ponteiros

  • 23/11/12 Estrutura de Dados II 16

    Ponteirosint main ( void ){ int a; int *p=&a; *p = 2; printf(" %d ", a); return 0;}

    imprime o valor 2

  • 23/11/12 Estrutura de Dados II 17

    Ponteiros: cuidados

    erro na atribuio *p=3 utiliza a memria apontada por p para armazenar o valor 3,

    sem que p tivesse sido inicializada, logo

    armazena 3 num espao de memria desconhecido

    int main ( void ){ int a, b, *p; a = 2; *p = 3; b = a + (*p); printf(" %d ", b); return 0;}

  • 23/11/12 Estrutura de Dados II 18

    Ponteiros Aplicao: funes que mudam valores de variveis de outras

    #include

    void troca(int a, int b);

    int main (void){

    int a=10, b=20;troca(a,b);printf(" a=%d b=%d\n",a,b);

    }

    void troca(int x, int y) {int tmp=y;y=x;x=tmp;

    } a=10 b=20Press any key to continue

  • 23/11/12 Estrutura de Dados II 19

    #include

    void troca(int a, int b);

    int main (void){

    int a=10, b=20;troca(a,b);printf(" a=%d b=%d\n",a,b);

    }

    void troca(int x, int y) {int tmp=y;y=x;x=tmp;

    }

    1020

    Pilha de memria

    ab

    main7000

    7004

    7008

    7012

    7016

    7020

    Ponteiros Aplicao: funes que mudam valores de variveis de outras

  • 23/11/12 Estrutura de Dados II 20

    #include

    void troca(int a, int b);

    int main (void){

    int a=10, b=20;troca(a,b);printf(" a=%d b=%d\n",a,b);

    }

    void troca(int x, int y) {int tmp=y;y=x;x=tmp;

    }

    1020102020

    Pilha de memria

    ab

    main7000

    7004

    7008

    7012

    7016

    7020

    xy

    troca

    tmp

    Ponteiros Aplicao: funes que mudam valores de variveis de outras

  • 23/11/12 Estrutura de Dados II 21

    #include

    void troca(int a, int b);

    int main (void){

    int a=10, b=20;troca(a,b);printf(" a=%d b=%d\n",a,b);

    }

    void troca(int x, int y) {int tmp=y;y=x;x=tmp;

    }

    1020101020

    Pilha de memria

    ab

    main7000

    7004

    7008

    7012

    7016

    7020

    xy

    troca

    tmp

    Ponteiros Aplicao: funes que mudam valores de variveis de outras

  • 23/11/12 Estrutura de Dados II 22

    #include

    void troca(int a, int b);

    int main (void){

    int a=10, b=20;troca(a,b);printf(" a=%d b=%d\n",a,b);

    }

    void troca(int x, int y) {int tmp=y;y=x;x=tmp;

    }

    1020201020

    Pilha de memria

    ab

    main7000

    7004

    7008

    7012

    7016

    7020

    xy

    troca

    tmp

    Ponteiros Aplicao: funes que mudam valores de variveis de outras

  • 23/11/12 Estrutura de Dados II 23

    #include

    void troca(int a, int b);

    int main (void){

    int a=10, b=20;troca(a,b);printf(" a=%d b=%d\n",a,b);

    }

    void troca(int x, int y) {int tmp=y;y=x;x=tmp;

    }

    1020

    Pilha de memria

    ab

    main7000

    7004

    7008

    7012

    7016

    7020

    Ponteiros Aplicao: funes que mudam valores de variveis de outras

  • 23/11/12 Estrutura de Dados II 24

    Ponteiros - Aplicao

    Passagem de ponteiros para funes: funo g chama funo f

    f no pode alterar diretamente valores de variveis de g, porm

    se g passar para f os valores dos endereos de memria onde as variveis de g esto armazenadas, f pode alterar, indiretamente, os valores das variveis de g

  • 23/11/12 Estrutura de Dados II 25

    #include

    void troca(int *pa, int *pb);

    int main (void){

    int a=10, b=20;troca(&a,&b);printf(" a=%d b=%d\n",a,b);

    }

    void troca(int *pa, int *pb) {int tmp=*pb;*pb=*pa;*pa=tmp;

    } a=20 b=10Press any key to continue

    Ponteiros Aplicao: funes que mudam valores de variveis de outras

  • 23/11/12 Estrutura de Dados II 26

    #include

    void troca(int *pa, int *pb);

    int main (void){

    int a=10, b=20;troca(&a,&b);printf(" a=%d b=%d\n",a,b);

    }

    void troca(int *pa, int *pb) {int tmp=*pb;*pb=*pa;*pa=tmp;

    }

    1020

    Pilha de memria

    ab

    main7000

    7004

    7008

    7012

    7016

    7020

    Ponteiros Aplicao: funes que mudam valores de variveis de outras

  • 23/11/12 Estrutura de Dados II 27

    #include

    void troca(int *pa, int *pb);

    int main (void){

    int a=10, b=20;troca(&a,&b);printf(" a=%d b=%d\n",a,b);

    }

    void troca(int *pa, int *pb) {int tmp=*pb;*pb=*pa;*pa=tmp;

    }

    1020

    70007004

    -

    Pilha de memria

    ab

    main7000

    7004

    7008

    7012

    7016

    7020

    papb

    troca

    tmp

    Ponteiros Aplicao: funes que mudam valores de variveis de outras

  • 23/11/12 Estrutura de Dados II 28

    #include

    void troca(int *pa, int *pb);

    int main (void){

    int a=10, b=20;troca(&a,&b);printf(" a=%d b=%d\n",a,b);

    }

    void troca(int *pa, int *pb) {int tmp=*pb;*pb=*pa;*pa=tmp;

    }

    1020

    70007004

    20

    Pilha de memria

    ab

    main7000

    7004

    7008

    7012

    7016

    7020

    papb

    troca

    tmp

    Ponteiros Aplicao: funes que mudam valores de variveis de outras

  • 23/11/12 Estrutura de Dados II 29

    #include

    void troca(int *pa, int *pb);

    int main (void){

    int a=10, b=20;troca(&a,&b);printf(" a=%d b=%d\n",a,b);

    }

    void troca(int *pa, int *pb) {int tmp=*pb;*pb=*pa;*pa=tmp;

    }

    1010

    70007004

    20

    Pilha de memria

    ab

    main7000

    7004

    7008

    7012

    7016

    7020

    papb

    troca

    tmp

    Ponteiros Aplicao: funes que mudam valores de variveis de outras

  • 23/11/12 Estrutura de Dados II 30

    #include

    void troca(int *pa, int *pb);

    int main (void){

    int a=10, b=20;troca(&a,&b);printf(" a=%d b=%d\n",a,b);

    }

    void troca(int *pa, int *pb) {int tmp=*pb;*pb=*pa;*pa=tmp;

    }

    2010

    70007004

    20

    Pilha de memria

    ab

    main7000

    7004

    7008

    7012

    7016

    7020

    papb

    troca

    tmp

    Ponteiros Aplicao: funes que mudam valores de variveis de outras

  • 23/11/12 Estrutura de Dados II 31

    #include

    void troca(int *pa, int *pb);

    int main (void){

    int a=10, b=20;troca(&a,&b);printf(" a=%d b=%d\n",a,b);

    }

    void troca(int *pa, int *pb) {int tmp=*pb;*pb=*pa;*pa=tmp;

    }

    2010

    Pilha de memria

    ab

    main7000

    7004

    7008

    7012

    7016

    7020

    a=20 b=10Press any key to continue

    Ponteiros Aplicao: funes que mudam valores de variveis de outras

  • 23/11/12 Estrutura de Dados II 32

    13579

    1113

    v[0] 104108

    112

    116

    120

    124

    128

    132

    136

    140

    v[1]v[2]v[3]v[4]v[5]v[6]

    int v[7]={1,3,5,7,9,11,13};int i;

    int v[7];int i;

    for (i=0; i

  • 23/11/12 Estrutura de Dados II 33

    13579

    1113

    v[0] 104108

    112

    116

    120

    124

    128

    132

    136

    140

    v[1]v[2]v[3]v[4]v[5]v[6]

    int v[7]={1,3,5,7,9,11,13};int i;

    int v[7];int i;

    for (i=0; i

  • 23/11/12 Estrutura de Dados II 34

    Vetores e Ponteiros

    int v[7];

    Quem v?

    v um ponteiro de valor constante que aponta para o primeiro elemento do vetor de inteiros!

    13579

    1113

    v 104108

    112

    116

    120

    124

    128

    132

    136

    140

  • 23/11/12 Estrutura de Dados II 35

    Vetores e Aritmtica de Ponteiros

    int v[7];

    v+i aponta para v[i]!

    13579

    1113

    104

    108

    112

    116

    120

    124

    128

    132

    136

    140

    v+0 v+1 v+2 v+3 v+4 v+5 v+6

    scanf(%d,&v[i]); scanf(%d,v+i);

    Ou seja:

    *(v+i)=3; v[i]=3;

  • 23/11/12 Estrutura de Dados II 36

    Passagem de vetor para funo: consiste em passar o endereo da primeira posio do

    vetor

    funo deve ter parmetro do tipo ponteiro para armazenar valor

    passar um vetor para uma funo equivalente apassar o endereo inicial do vetor

    elementos do vetor no so copiados para a funo

    argumento copiado apenas o endereo do primeiro elemento

    Exemplo: chamada funo passando vetor de int

    funo deve ter um parmetro do tipo int *

    Vetores e Ponteiros

  • 23/11/12 Estrutura de Dados II 37

    /* Clculo da mdia e da varincia de n reais (segunda verso) */

    #include

    /* Funo para clculo da mdia */float media (int n, float* v){ int i; float s = 0.0; for (i = 0; i < n; i++) s += v[i]; return s/n;}

    parmetro do tipo ponteiro para float

    Vetores e Ponteiros - Passagem de vetor para funo

  • 23/11/12 Estrutura de Dados II 38

    /* Funo para clculo da varincia */float variancia (int n, float* v, float m){ int i; float s = 0.0; for (i = 0; i < n; i++) s += (v[i] - m) * (v[i] - m); return s/n; }

    Vetores e Ponteiros - Passagem de vetor para funo

  • 23/11/12 Estrutura de Dados II 39

    #define MAX 10

    int main ( void ){ float med, var, v[MAX], int i;

    /* leitura dos valores */ for ( i = 0; i < MAX; i++ ) { scanf("%f", &v[i]); } med = media(MAX,v); var = variancia(MAX,v,med); printf ( "Media = %f Variancia = %f \n", med, var); return 0;}

    Vetores e Ponteiros - Passagem de vetor para funo

  • 23/11/12 Estrutura de Dados II 40

    funo pode alterar os valores dos elementos do vetor pois recebe o endereo do primeiro elemento do vetor (e no os elementos propriamente ditos) Exemplo:

    funo incrementando todos os elementos de uma unidade

    Vetores e Ponteiros - Passagem de vetor para funo

  • 23/11/12 Estrutura de Dados II 41

    /* Incrementa elementos de um vetor */void incr_vetor ( int n, int *v ){ int i; for (i = 0; i < n; i++) v[i]++;}

    Vetores e Ponteiros - Passagem de vetor para funo

    int main ( void ){ int a[ ] = {1, 3, 5}; incr_vetor(3, a); printf("%d %d %d \n", a[0], a[1], a[2]); return 0;}

    sada do programa ser 2 4 6

  • 23/11/12 Estrutura de Dados II 42

    Vetores e Ponteiros - Exerccio

    Escreva uma funo que recebe dois vetores de tamanho n e um terceiro vetor de tamanho 2n. Ao chamar a funo os elementos dos vetores de tamanho n so inseridos de modo intercalado no vetor de tamanho 2n.

  • 23/11/12 Estrutura de Dados II 43

    /* Intercala elementos de um vetor */#include void une_intercalado ( int n, int *u, int *v, int *z ){ int i; for (i = 0; i < n; i++) { z[2*i] = u[i]; z[2*i+1] = v[i]; }}

    int main ( void ){ int a[ ] = {1, 3, 5}; int b[ ] = {2, 4, 6}; int c[6]; int i; une_intercalado(3, a, b, c); for (i = 0; i < 6; i++) printf("%d\n", c[i]); return 0;}

  • 23/11/12 Estrutura de Dados II 44

    Alocao Dinmica Uso da memria:

    uso de variveis globais (e estticas): espao reservado para uma varivel global existe

    enquanto o programa estiver sendo executado

    uso de variveis locais: espao existe apenas enquanto a funo que declarou a varivel

    est sendo executada

    liberado para outros usos quando a execuo da funo termina

    variveis globais ou locais podem ser simples ou vetores: para vetor, necessrio informar o nmero mximo de elementos

    pois o compilador precisa calcular o espao a ser reservado

  • 23/11/12 Estrutura de Dados II 45

    Alocao Dinmica

    Uso da memria: alocao dinmica:

    espao de memria requisitado em tempo de execuo

    espao permanece reservado at que seja explicitamente liberado

    depois de liberado, espao estar disponibilizado para outros usos e no pode mais ser acessado

    espao alocado e no liberado explicitamente, ser automaticamente liberado ao final da execuo

  • 23/11/12 Estrutura de Dados II 46

    Alocao Dinmica Uso da memria:

    memria esttica: cdigo do programa

    variveis globais

    variveis estticas

    memria dinmica: variveis alocadas

    dinamicamente

    memria livre

    variveis locais

    Cdigo do programaVariveis globais e

    Variveis estticasVariveis alocadas

    dinamicamente

    Memria livre

    Variveis locais

    (Pilha de execuo)

    mem

    ria esttica

    mem

    riadinm

    ica

  • 23/11/12 Estrutura de Dados II 47

    Alocao Dinmica Uso da memria:

    alocao dinmica de memria: usa a memria livre se o espao de memria livre for

    menor que o espao requisitado, a alocao no feita e o programa pode prever tratamento de erro

    pilha de execuo: utilizada para alocar memria

    quando ocorre chamada de funo: sistema reserva o espao

    para as variveis locais da funo quando a funo termina,

    espao liberado (desempilhado)

    se a pilha tentar crescer mais do que o espao disponvel existente, programa abortado com erro

    Cdigo do programaVariveis globais e

    Variveis estticasVariveis alocadas

    dinamicamente

    Memria livre

    Variveis locais

    (Pilha de execuo)

    mem

    ria esttica

    mem

    ria esttica

  • 23/11/12 Estrutura de Dados II 48

    Alocao Dinmica

    Funes da biblioteca padro stdlib.h contm uma srie de funes pr-definidas:

    funes para tratar alocao dinmica de memria constantes pr-definidas ....

  • 23/11/12 Estrutura de Dados II 49

    Alocao Dinmica

    void * malloc(int num_bytes);

    void free(void * p);

  • 23/11/12 Estrutura de Dados II 50

    Alocao Dinmica Funo malloc:

    recebe como parmetro o nmero de bytes que se deseja alocar retorna um ponteiro genrico para o endereo inicial da rea de

    memria alocada, se houver espao livre: ponteiro genrico representado por void* ponteiro convertido automaticamente para o tipo apropriado ponteiro pode ser convertido explicitamente

    retorna um endereo nulo, se no houver espao livre: representado pelo smbolo NULL

    Funo sizeof: retorna o nmero de bytes ocupado por um tipo

    funo free: recebe como parmetro o ponteiro da memria a ser liberada

    a funo free deve receber um endereo de memria que tenha sido alocado dinamicamente

  • 23/11/12 Estrutura de Dados II 51

    Alocao Dinmica

    Exemplo: alocao dinmica de um vetor de inteiros

    com 10 elementos malloc retorna o endereo da rea alocada para

    armazenar valores inteiros ponteiro de inteiro recebe endereo inicial do

    espao alocado

    int *v;v = (int *) malloc(10*sizeof(int));

  • 23/11/12 Estrutura de Dados II 52

    Alocao Dinmica

    Exemplo (cont.):v = (int *) malloc(10*sizeof(int));

    1 - Declarao: int *v

    v

    Abre-se espao na pilha parao ponteiro (varivel local)

    2 - Comando: v = (int *) malloc (10*sizeof(int))Reserva espao de memria da rea livree atribui endereo varivel

    v

    504

    Cdigo doPrograma

    VariveisGlobais e Estticas

    -

    Livre

    Cdigo doPrograma

    VariveisGlobais e Estticas

    504

    Livre

    40 bytes

    1 - Declarao: int *v

    v

    Abre-se espao na pilha parao ponteiro (varivel local)

    2 - Comando: v = (int *) malloc (10*sizeof(int))Reserva espao de memria da rea livree atribui endereo varivel

    v

    504

    Cdigo doPrograma

    VariveisGlobais e Estticas

    -

    Livre

    Cdigo doPrograma

    VariveisGlobais e Estticas

    -

    Livre

    Cdigo doPrograma

    VariveisGlobais e Estticas

    504

    Livre

    40 bytes

  • 23/11/12 Estrutura de Dados II 53

    Alocao Dinmica

    Exemplo (cont.): v armazena endereo inicial de uma rea

    contnua de memria suficiente para armazenar 10 valores inteiros

    v pode ser tratado como um vetor declarado estaticamente

    v aponta para o inicio da rea alocada v[0] acessa o espao para o primeiro elemento v[1] acessa o segundo .... at v[9]

  • 23/11/12 Estrutura de Dados II 54

    Alocao Dinmica

    Exemplo (cont.): tratamento de erro aps chamada a malloc

    imprime mensagem de erro aborta o programa (com a funo exit)

    v = (int*) malloc(10*sizeof(int));if (v==NULL){ printf("Memoria insuficiente.\n"); exit(1); /* aborta o programa e retorna 1 para o sist. operacional */}

    free(v);

  • 23/11/12 Estrutura de Dados II 55

    #include

    int main ( void ){ float *v; float med, var; int i,n;

    printf("Entre n e depois os valores\n"); scanf("%d",&n); v = (float *) malloc(n*sizeof(float)); if (v==NULL) { printf(Falta memoria\n); exit(1); }

    for ( i = 0; i < n; i++ ) scanf("%f", &v[i]);

    med = media(n,v); var = variancia(n,v,med);

    printf ( "Media = %f Variancia = %f \n", med, var); free(v); return 0;}

  • 23/11/12 Estrutura de Dados II 56

    Ateno: Vetores Locais a Funes

    rea de memria de uma varivel local: s existe enquanto a funo que declara a varivel

    estiver sendo executada

    requer cuidado quando da utilizao de vetores locais dentro de funes

    Exemplo: produto vetorial de dois vetores u e v em 3D,

    representados pelas trs componentes x, y, e z

    uv= { u y v zv y uz , uz v xvz ux , ux v yvx u y }

  • 23/11/12 Estrutura de Dados II 57

    varivel p declarada localmente: rea de memria que a varivel p ocupa deixa de ser vlida

    quando a funo prod_vetorial termina

    funo que chama prod_vetorial no pode acessar a rea apontada pelo valor retornado

    float* prod_vetorial (float* u, float* v){ float p[3]; p[0] = u[1]*v[2] v[1]*u[2]; p[1] = u[2]*v[0] v[2]*u[0]; p[2] = u[0]*v[1] v[0]*u[1]; return p; }

    Vetor Declarado Localmente

  • 23/11/12 Estrutura de Dados II 58

    varivel p recebe endereo inicial da rea alocada dinamicamente rea de memria para a qual a varivel p aponta permanece vlida mesmo aps o

    trmino da funo prod_vetorial;

    a varivel p ser destruda aps o trmino da funo prod_vetorial;

    funo que chama prod_vetorial pode acessar a rea apontada pelo valor retornado

    problema - alocao dinmica para cada chamada da funo: ineficiente do ponto de vista computacional

    requer que a funo que chama seja responsvel pela liberao do espao

    float* prod_vetorial (float* u, float* v){ float *p = (float*) malloc(3*sizeof(float)); p[0] = u[1]*v[2] v[1]*u[2]; p[1] = u[2]*v[0] v[2]*u[0]; p[2] = u[0]*v[1] v[0]*u[1]; return p;}

    Vetor Alocado Dinaminamente

  • 23/11/12 Estrutura de Dados II 59

    void prod_vetorial (float* u, float* v, float* p){ p[0] = u[1]*v[2] v[1]*u[2]; p[1] = u[2]*v[0] v[2]*u[0]; p[2] = u[0]*v[1] v[0]*u[1];}

    Vetor Alocado Previamente

    espao de memria para o resultado passado pela funo que chama:

    funo prod_vetorial recebe trs vetores, dois vetores com dados de entrada

    um vetor para armazenar o resultado

    soluo mais adequada pois no envolve alocao dinmica

  • 23/11/12 Estrutura de Dados II 60

    Exerccio

    Escreva uma funo que recebe dois vetores de inteiros v1 e v2 de tamanho n e cria um novo vetor vetor de tamanho 2n, no qual os elementos do vetor v1 aparecem no incio e os do vetor v2 aparecem concatenados ao final. A funo deve retornar o ponteiros para o novo vetor alocado dinamicamente.

    int* concatena(int *v1, int *v2, int n);

  • 23/11/12 Estrutura de Dados II 61

    Tipo Estrutura: Motivao

    Motivao: manipulao de dados compostos ou

    estruturados Exemplos:

    ponto no espao bidimensional representado por duas coordenadas (x e y),

    mas tratado como um nico objeto (ou tipo)

    dados associados a aluno: aluno representado pelo seu

    nome, nmero de matrcula, endereo, etc ., estruturados em um nico objeto (ou tipo)

    YX

    Ponto

    ComplNo

    RuaEndMatr

    NomeAluno

  • 23/11/12 Estrutura de Dados II 62

    Tipo Estrutura: outra forma

    Tipo estrutura: tipo de dado com campos compostos de tipos

    mais simples elementos acessados atravs do operador de

    acesso ponto(.) struct ponto /* declara ponto do tipo struct */{ float x; float y;};...int main( ) { struct ponto p; /* declara p como varivel do tipo struct ponto */ ... p.x = 10.0; /* acessa os elementos de ponto */ p.y = 5.0+p.x;

  • 23/11/12 Estrutura de Dados II 63

    Tipo Estrutura: Exemplo /* Captura e imprime as coordenadas de um ponto qualquer */#include struct ponto { float x; float y;};int main (void){ struct ponto p; printf("Digite as coordenadas do ponto(x y): "); scanf("%f %f", &p.x, &p.y); printf("O ponto fornecido foi: (%.2f,%.2f)\n", p.x, p.y); return 0;}

    Basta escrever &p.x em lugar de &(p.x).O operador de acesso ao campo da estrutura tem precedncia sobre o operador endereo de

  • 23/11/12 Estrutura de Dados II 64

    Passagem de estruturas por valor para funes

    anloga passagem de variveis simples

    funo recebe toda a estrutura como parmetro: funo acessa a cpia da estrutura na pilha

    funo no altera os valores dos campos da estrutura original

    operao pode ser custosa se a estrutura for muito grande

    /* funo que imprime as coordenadas do ponto */void imprime (struct ponto p){ printf("O ponto fornecido foi: (%.2f,%.2f)\n", p.x, p.y);}

  • 23/11/12 Estrutura de Dados II 65

    Estuturas como valor de retorno/* Captura e imprime as coordenadas de um ponto qualquer */#include struct ponto { float x; float y; };

    struct ponto le(void){ struct ponto tmp; printf("Digite as coordenadas do ponto(x y): "); scanf("%f %f", &tmp.x, &tmp.y); return tmp;}

    int main (void){ struct ponto p=le(); printf("O ponto fornecido foi: (%.2f,%.2f)\n", p.x, p.y); return 0;}

  • 23/11/12 Estrutura de Dados II 66

    Definio de Novos Tipos typedef

    permite criar nomes de tipos

    til para abreviar nomes de tipos e para tratar tipos complexos

    UChar o tipo char sem sinal

    Vetor um tipo que representa um vetor de quatro elementos

    typedef unsigned char UChar;typedef float Vetor[4];Vetor v; /* exemplo de declarao usando Vetor */...v[0] = 3;

  • 23/11/12 Estrutura de Dados II 67

    Definio de Novos Tipos typedef

    Exemplo: definio de nomes de tipos para as estruturas

    ponto representa uma estrutura com 2 campos do tipo float Ponto representa a estrutura ponto PPonto representa o tipo ponteiro para a estrutura ponto

    struct ponto { float x; float y;};typedef struct ponto Ponto; typedef struct ponto *PPonto;

  • 23/11/12 Estrutura de Dados II 68

    Definio de Novos Tipos typedef

    Exemplo: (definio utilizando um s typedef)

    ponto representa uma estrutura com 2 campos do tipo float

    Ponto representa a estrutura ponto

    PPonto representa o tipo ponteiro para a estrutura Ponto

    struct ponto { float x; float y;};

    typedef struct ponto Ponto, *PPonto;

  • 23/11/12 Estrutura de Dados II 69

    Definio de Novos Tipos typedef

    Exemplo: (definio em um comando s)

    ponto representa uma estrutura com 2 campos do tipo float

    Ponto representa a estrutura ponto

    typedef struct ponto { float x; float y;} Ponto;

  • 23/11/12 Estrutura de Dados II 70

    Aninhamento de Estruturas Aninhamento de estruturas:

    campos de uma estrutura podem ser outras estruturas

    Exemplo: definio de Crculo usando Ponto

    struct circulo { Ponto p; /* centro do crculo */ float r; /* raio do crculo */};typedef struct circulo Circulo;

  • 23/11/12 Estrutura de Dados II 71

    /* Funo para a calcular distncia entre 2 pontos:entrada: ponteiros para os pontossada: distncia correspondente

    */float distancia (Ponto p, Ponto q){ float d=sqrt((q.x-p.x)*(q.x-p.x)+(q.y - p.y)*(q.y - p.y)); return d;}/* Funo para determinar se um ponto est ou no dentro de um crculo:

    entrada: ponteiros para um crculo e para um pontosada: 1 = ponto dentro do crculo

    0 = ponto fora do crculo */int interior (Circulo c, Ponto p){ float d = distancia(c.p, p); return (d < c.r);}

    p : valor do ponto

    clculo da distncia:

    sqrt da biblioteca math.hd=( x2x1 )2+( y 2 y1 )2

    c.p : valor do centro de c

    Aninhamento de Estruturas

  • 23/11/12 Estrutura de Dados II 72

    #include #include typedef struct ponto { float x; float y;} Ponto;typedef struct circulo { Ponto p; /* centro do crculo */ float r; /* raio do crculo */} Circulo;int main (void){ Circulo c; Ponto p; printf("Digite as coordenadas do centro e o raio do circulo:\n"); scanf("%f %f %f", &c.p.x, &c.p.y, &c.r); printf("Digite as coordenadas do ponto:\n"); scanf("%f %f", &p.x, &p.y); printf("Pertence ao interior = %d\n", interior(c,p)); return 0;}

    Aninhamento de Estruturas

  • 23/11/12 Estrutura de Dados II 73

    Vetores de Estruturas Exemplo:

    funo para calcular o centro geomtrico de conjunto de pontos

    entrada: vetor de estruturas definindo o conjunto de pontos

    sada: centro geomtrico, dado por:

    x= x i

    ny= y i

    n

  • 23/11/12 Estrutura de Dados II 74

    Vetores de Estruturas

    funo retornando estrutura: para estruturas pequenas, este recurso facilita o uso da funo

    para estruturas grandes, a cpia do valor de retorno pode ser cara

    Ponto centro_geom (int n, Ponto v[]){ int i; Ponto p = {0.0f, 0.0f}; /* declara e inicializa ponto */ for (i=0; i

  • 23/11/12 Estrutura de Dados II 75

    Vetores de Estruturas Exemplo:

    funo para calcular a rea de um polgono plano delimitado por uma seqncia de n pontos

    a rea do polgono a soma das reas dos trapzios formados pelos lados do polgono e o eixo x

    a rea do trapzio definido pela aresta que vai do ponto pi ao ponto pi+1 dada por:

    algumas reas so negativas as reas externas ao polgono so anuladas se a seqncia de pontos do polgono

    for dada em sentido anti-horrio, a rea ter valor negativo e a rea do polgono o valor absoluto do resultado da soma.

    x

    pipi+1

    yi yi+1

    xi xi+1

    y

    a=( xi+1x i )( y i+1 +y i) /2

  • 23/11/12 Estrutura de Dados II 76

    Vetores de Estruturas

    fabs funo definida em math.h retorna o valor absoluto de um valor real

    float area (int n, Ponto* p){ int i, j; float a = 0; for (i=0; i

  • 23/11/12 Estrutura de Dados II 77

    Tipo Estrutura: ponteiro para estruturas

    Ponteiros para estruturas: acesso ao valor de um campo x de uma varivel estrutura p: p.x acesso ao valor de um campo x de uma varivel ponteiro pp: pp->x acesso ao endereo do campo x de uma varivel ponteiro pp: &pp->x

    struct ponto p;struct ponto *pp=&p;...(*pp).x = 12.0; /* formas equivalentes de acessar o valor de um campo x */ pp->x = 12.0;p.x = 12.0;(&p)->x =12.0;

  • 23/11/12 Estrutura de Dados II 78

    struct ponto { float x; float y;};

    int main ( ) { struct ponto p = { 10,20}; struct ponto *pp=&p; ...} 10

    20

    Pilha de memria

    xy

    main 70007004

    7008

    7012

    7016

    7020

    p

    Qual o valor de ?p.y

    pp.xpp->x

    (&p)->x&(pp->y)

    &(p.y)

    Tipo Estrutura: ponteiro para estruturas

  • 23/11/12 Estrutura de Dados II 79

    Passagem de estruturas por referncia para funo apenas o ponteiro da estrutura passado, mesmo que

    no seja necessrio alterar os valores dos campos dentro da funo

    /* funo que imprima as coordenadas do ponto */void imprime (struct ponto* pp){ printf("O ponto fornecido foi: (%.2f,%.2f)\n", pp->x, pp->y); }void captura (struct ponto* pp){ printf("Digite as coordenadas do ponto(x y): "); scanf("%f %f", &pp->x, &pp->y);}int main (void){ struct ponto p; captura(&p); imprime(&p); return 0; }

    Tipo Estrutura: ponteiro para estruturas

  • 23/11/12 Estrutura de Dados II 80

    Alocao dinmica de estruturas tamanho do espao de memria alocado dinamicamente

    dado pelo operador sizeof aplicado sobre o tipo estrutura

    funo malloc retorna o endereo do espao alocado, que ento convertido para o tipo ponteiro da estrutura

    struct ponto* p;p = (struct ponto*) malloc (sizeof(struct ponto));...p->x = 12.0;...free(p);

    Tipo Estrutura: ponteiro para estruturas

  • 23/11/12 Estrutura de Dados II 81

    Exemplo: tabela com dados de alunos, organizada em um vetor

    dados de cada aluno:

    matrcula: nmero inteiro

    nome: cadeia com at 80 caracteres

    endereo: cadeia com at 120 caracteres

    telefone: cadeia com at 20 caracteres

    Tipo Estrutura: vetores de ponteiros para estruturas

  • 23/11/12 Estrutura de Dados II 82

    Soluo 1: Aluno

    estrutura ocupando pelo menos 4+81+121+21 = 227 Bytes

    tab vetor de Aluno

    representa um desperdcio significativo de memria, se o nmero de alunos for bem inferior ao mximo estimado

    struct aluno { int mat; char nome[81]; char end[121]; char tel[21];};

    typedef struct aluno Aluno;

    #define MAX 100Aluno tab[MAX];

    Tipo Estrutura: vetores de ponteiros para estruturas

  • 23/11/12 Estrutura de Dados II 83

    Soluo 2 (usada no que se segue): tab

    vetor de ponteiros para Aluno

    elemento do vetor ocupa espao de um ponteiro

    alocao dos dados de um aluno no vetor: nova cpia da estrutura Aluno alocada dinamicamente

    endereo da cpia armazenada no vetor de ponteiros

    posio vazia do vetor: valor o ponteiro nulo

    struct aluno { int mat; char nome[81]; char end[121]; char tel[21];};typedef struct aluno Aluno;#define MAX 100Aluno* tab[MAX];

    Tipo Estrutura: vetores de ponteiros para estruturas

  • 23/11/12 Estrutura de Dados II 84

    Inicializa - funo para inicializar a tabela: recebe um vetor de ponteiros

    (parmetro deve ser do tipo ponteiro para ponteiro)

    atribui NULL a todos os elementos da tabela

    void inicializa (int n, Aluno** tab){ int i; for (i=0; i

  • 23/11/12 Estrutura de Dados II 85

    Preenche - funo para armazenar novo aluno na tabela: recebe a posio onde os dados sero armazenados

    dados so fornecidos via teclado, se a posio da tabela estiver vazia, funo aloca nova estrutura, caso contrrio, funo atualiza a estrutura j apontada pelo ponteiro

    void preenche (Aluno** tab, int i){ if (tab[i]==NULL) tab[i] = (Aluno*)malloc(sizeof(Aluno)); printf("Entre com a matricula:"); scanf("%d", &tab[i]->mat); ...}

    Tipo Estrutura: vetores de ponteiros para estruturas

  • 23/11/12 Estrutura de Dados II 86

    Retira - funo para remover os dados de um aluno da tabela: recebe a posio da tabela a ser liberada

    libera espao de mmria utilizado para os dados do aluno

    void retira (Aluno** tab, int i){ if (tab[i] != NULL) { free(tab[i]); tab[i] = NULL; /* indica que na posio no mais existe dado */ }}

    Tipo Estrutura: vetores de ponteiros para estruturas

  • 23/11/12 Estrutura de Dados II 87

    Imprime - funo para imprimir os dados de um aluno da tabela: recebe a posio da tabela a ser impressa

    void imprime (Aluno** tab, int i){ if (tab[i] != NULL) { printf("Matrcula: %d\n, tab[i]->mat); printf("Nome: %s\n, tab[i]->nome); printf("Endereo: %s\n, tab[i]->end); printf("Telefone: %s\n, tab[i]->tel); }}

    Tipo Estrutura: vetores de ponteiros para estruturas

  • 23/11/12 Estrutura de Dados II 88

    Imprime_tudo - funo para imprimir todos os dados da tabela: recebe o tamanho da tabela e a prpria tabela

    void imprime_tudo (int n, Aluno** tab){ int i; for (i=0; i

  • 23/11/12 Estrutura de Dados II 89

    Programa de teste

    #include int main (void){ Aluno* tab[10]; inicializa(10,tab); preenche(tab,0); preenche(tab,1); preenche(tab,2); imprime_tudo(10,tab); retira(tab,0); retira(tab,1); retira(tab,2); return 0;}

    Tipo Estrutura: vetores de ponteiros para estruturas

  • 23/11/12 Estrutura de Dados II 90

    Exemplo 2 (tarefa no laboratrio): uma universidade utiliza um sistema informatizado para controlar os

    candidatos ao seu curso de Informtica. As informaes referentes aos candidatos so mantidas em dados estruturados do tipo Candidato, descrito a seguir:

    struct data { int dia, mes, ano; }; typedef struct data Data;

    struct candidato { int inscr; char nome[51]; float nota; Data *nasc; }; typedef struct candidato Cand;

    Tipo Estrutura: vetores de ponteiros para estruturas

  • 23/11/12 Estrutura de Dados II 91

    Funo para alocar dinamicamente e inicializar um vetor de ponteiros:

    recebe o tamanho do vetor de ponteiros como parmetro

    Aloca o novo vetor dinamicamente e verifica se est OK

    atribui NULL a todos os elementos do vetor

    Retorna o ponteiro para o novo vetor (deve ser do tipo ponteiro para ponteiro para Cand)

    Cand** cria_vetor (int n){ int i; Cand** vet = (Cand**) malloc(n*sizeof(Cand*)); if(vet!=NULL) for (i=0; i

  • 23/11/12 Estrutura de Dados II 92

    Funo que cria e preenche uma nova varivel do tipo Data recebe os valores que sero armazenados

    Aloca dinamicamente uma nova varivel do tipo Data

    Preenche os valores da varivel

    Retorna um ponteiro para a nova varivel

    Data* cria_data(int dia, int mes, int ano){ Data* p = (Data*) malloc(sizeof(Data)); if(p!=NULL) { p->dia = dia; p->mes = mes; p->ano = ano; } return p;}

    Tipo Estrutura: vetores de ponteiros para estruturas

  • 23/11/12 Estrutura de Dados II 93

    Funo que cria e preenche uma nova varivel do tipo Cand recebe os valores que sero armazenados

    Aloca dinamicamente uma nova varivel do tipo Cand

    Preenche os valores da varivel

    Retorna um ponteiro para a nova varivel

    Cand* cria_candidato(int inscr, char* nome, float nota, int dia, int mes, int ano){ Cand* p = (Cand*) malloc(sizeof(Cand)); if(p!=NULL) { p->inscr = inscr; strcpy(p->nome, nome); p->nota = nota; p->nasc = cria_data(dia, mes, ano); } return p;}

    E se cria_datano conseguiralocar uma novavarivel?

    Tipo Estrutura: vetores de ponteiros para estruturas

  • 23/11/12 Estrutura de Dados II 94

    Cand* cria_candidato(int inscr, char* nome, float nota, int dia, int mes, int ano){ Cand* p = (Cand*) malloc(sizeof(Cand)); if(p!=NULL) { p->inscr = inscr; strcpy(p->nome, nome); p->nota = nota; p->nasc = cria_data(dia, mes, ano); if(p->nasc == NULL) { free(p); p = NULL; } } return p;}

    Tipo Estrutura: vetores de ponteiros para estruturas

  • 23/11/12 Estrutura de Dados II 95

    Funo para imprimir os dados armazenados em um vetor: recebe o ponteiro para o vetor e o seu tamanho

    void imprime_vetor(int n, Cand** vet){ int i; for(i=0; inome); printf("Nota: %.1f\n, vet[i]->nota); printf("Data de nascimento: %2d/%2d/%2d\n\n, vet[i]->nasc->dia, vet[i]->nasc->mes, vet[i]->nasc->ano); } }}

    Tipo Estrutura: vetores de ponteiros para estruturas

  • 23/11/12 Estrutura de Dados II 96

    Funo para liberar todo o espao de memria alocado: recebe o ponteiro para o vetor e o seu tamanho

    void imprime_libera(int n, Cand** vet){ int i; for(i=0; inasc); free(vet[i]); } free(vet);}

    Tipo Estrutura: vetores de ponteiros para estruturas

  • 23/11/12 Estrutura de Dados II 97

    Programa de teste

    #include int main (void){ Cand** v = novo_vetor(3); if (v==NULL) { printf(Memoria insuficiente\n); return 1; } v[0]=novo_candidato(123,Joao Silva,9.3,10,11,1980); v[1]=novo_candidato(124,Ana Souza,9.5,2,8,1975); v[2]=novo_candidato(125,Pedro Santos,7.5,1,5,1982); imprime_vetor(3,v); libera_vetor(3,v); return 0;}

    Tipo Estrutura: vetores de ponteiros para estruturas

  • 23/11/12 Estrutura de Dados II 98

    Referncias

    Waldemar Celes, Renato Cerqueira, Jos Lucas Rangel, Introduo a Estruturas de Dados, Editora Campus (2004)

    Captulo 5 Vetores e alocao dinmica

    Captulo 8 Tipos estruturados

  • 23/11/12 Estrutura de Dados II 99

    Material adaptado por Jos Viterbo Filho a partir dos slides elaborados por

    Marco Antonio Casanova e Marcelo Gattass para o curso de Estrutura de

    Dados para Engenharia, da PUC-Rio. Com base no livro Introduo a

    Estruturas de Dados, de Waldemar Celes, Renato Cerqueira e Jos Lucas

    Rangel, Editora Campus (2004).

    Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Slide 71Slide 72Slide 73Slide 74Slide 75Slide 76Slide 77Slide 78Slide 79Slide 80Slide 81Slide 82Slide 83Slide 84Slide 85Slide 86Slide 87Slide 88Slide 89Slide 90Slide 91Slide 92Slide 93Slide 94Slide 95Slide 96Slide 97Slide 98Slide 99