Revisão de C: Ponteiros e funções (recursivas e iterativas)

Links Relacionados: DAS5102 Fundamentos da Estrutura da Informação

Ponteiros e Funções

Funções ou sub-rotinas são parcelas de código que podem ser invocadas a partir do programa principal ou até mesmo por outras sub-rotinas. Elas têm como objetivo a execução de uma tarefa específica. Funções são também criadas por motivos de modularização, uma vez que a mesma função pode ser utilizada por diversos programas. Finalmente, a utilização de funções é uma forma eficiente de organizar o código fonte, separando do programa principal partes funcionais do código com objetivos claros e bem definidos.

Funções em C apresentam a seguinte forma geral:

1<tipo> <nome_funcao>(<tipo> <parametro>) 
2{ 
3   //código da função 
4}

Figura 1 – forma geral de uma função em C

Adicionalmente, funções podem possuir mais de um parâmetro. Para tal, basta declaramos os parâmetros adicionais acompanhados de seus tipos dentro dos parênteses, Parâmetros adicionais devem ser separados por vírgula.

Argumentos podem ser passados para uma função de duas formas distintas:

• Passagem de parâmetros por valor;
• Passagem de parâmetros por referência.

Comparação entre passagem de parâmetros por valor e por referência

Parâmetros Por Valor	Parâmetros Por Referência
Uma cópia da variável é feita e armazenada na pilha	Nenhuma cópia da variável e feita
Ideal para casos em que o tamanho da variável é pequeno	Ideal para casos em que o valor original da variável deve ser alterado por uma função
Quando a variável é grande (arrays) o consumo de memória na pilha pode ser proibitivo	Requer cuidado adicional em se manipular os argumentos da função
Torna a chamada de funções lenta dependendo do tamanho dos argumentos	Chamada de função é sempre rápida

Figura 2 – comparação entre passagem de parâmetros por valor e por referência.

A utilização de ponteiros é a maneira pela qual a linguagem C passa parâmetros para uma função por referência. Existem diversas situações nas quais a passagem de parâmetros por referência pode ser desejada (veja figura 2).

Em C, parâmetros são passados por referência utilizando ponteiros. Ao atribuir uma variável ponteiro como parâmetro de uma função o que é feito realmente é atribuir o endereço da variável. Desta forma, nenhuma cópia da variável é feita na pilha do programa, mas sim, a variável original é utilizada.

<tipo> <nome_funcao>(<tipo> *<parametro>) 
{ 
  //código da função 
}

Figura 3 – forma geral de uma função em C, parâmetros são passados por referência.

Existem várias situações onde a passagem de parâmetros por referência para funções são desejáveis:

• Quando a quantidade de dados a ser passada como referência é muito grande;
• Quando desejamos que a função altere o valor de uma variável ou estrutura de dados existente no escopo do programa que invoca a função;
• Quando a função a ser chamada deve executar rapidamente.

Observe o programa exemplo apresentado na figura 4. Neste pequeno programa pode-se observar o funcionamento da passagem de parâmetros por referência. Observe que o endereço da variável valor deve ser passado, e observe que ao utilizarmos a variável val na função incrementaValor devemos referenciá-la usando a notação de ponteiros e não diretamente.

 1#include <stdio.h>
 2
 3void incrementaValor(int *val);
 4
 5void main( void )
 6{
 7    int valor = 100;
 8    incrementaValor(&valor);
 9    printf("%d",valor);
10}
11
12void incrementaValor(int *val)
13{
14    //val = val + 1; //porque isso não funciona?
15    //*val = *val + 1;
16    (*val)++;
17}

Figura 4 – código exemplo para passagem de parâmetros por referência

Alocação Dinâmica de Memória

Alocação dinâmica de memória é o meio pelo qual um programa pode obter memória enquanto está em execução.

• Variáveis globais e locais têm espaço alocado em tempo de compilação;
• Parâmetros de funções têm espaço alocado na pilha.

 1#include <stdio.h>
 2#include <stdlib.h>
 3//#include <conio.h>
 4int main()
 5{
 6    char texto[10];
 7    short idades[10];
 8    int indices[10];
 9    float porcentagens[10];
10    double fatores[10];
11    printf ("\n\nDado char: %d byte", sizeof(char));
12    printf ("\nEspaco para 'char texto [10]': %d bytes",sizeof(texto));
13    printf ("\n\nDado short: %d bytes",sizeof(short));
14    printf ("\nEspaco para 'short idades [10]': %d bytes",sizeof(idades));
15    printf ("\n\nDado int: %d bytes",sizeof(int));
16    printf ("\nEspaco para 'int indices [10]': %d bytes",sizeof(indices));
17    printf ("\nEspaco para 'int indices [10]': %d bytes",sizeof(indices));
18    printf ("\n\nDado float: %d bytes",sizeof(float));
19    printf ("\nEspaco para 'float porcentagens [10]': %d b ytes",sizeof(porcentagens));
20    printf ("\n\nDado double: %d bytes", sizeof(double));
21    printf ("\nEspaco para 'double fatores [10]': %d bytes",sizeof(fatores));
22    //getch();
23    return 0;
24}

Figura 5 – código para a determinação do tamanho em bytes dos tipos nativos.

Alocação dinâmica obtém memória da heap, que é essencialmente a parte livre da memória alocada para o processo.

Alocação dinâmica em C é controlada basicamente por duas funções:

• malloc( ) – obtém memória da heap. Retorna um ponteiro do tipo void para a primeira posição de memória alocada, ou NULL em caso de falha.
• free( ) – libera memória previamente alocada para uso posterior. Recebe como parâmetro um ponteiro para a parte da memória a ser liberada.

As funções malloc e free são definidas na biblioteca <stdlib.h>. Seus protótipos são:

1void *malloc(size_t numero_de_bytes); 
2void free( void *p );

É muito importante testar se uma chamada de malloc foi ou não bem sucedida. Similarmente, deve-se sempre tomar cuidado em passar para a função free um ponteiro para uma região de memória que foi alocada. A utilização de um ponteiro inválido pode vir a acarretar sérios problemas (geralmente ocorrerá um erro de “segmentation fault”, o que fará com que o programa seja interrompido).

1char *p; 
2p = malloc( 1000 ); // obtem 1000 bytes

 1#include <stdio.h> 
 2#include <stdlib.h> 
 3main () 
 4{ 
 5    int *p, a, i; 
 6    // ... 
 7    p=(int *)malloc(a*sizeof(int)); 
 8    if (!p)
 9    { 
10        printf ("** Erro: Memória Insuficiente **"); 
11        exit (1); 
12    } 
13    for (i=0; i<a ; i++)
14    {
15        p[i] = i*i;
16    }
17}

Recursão

Recursão é um conceito fundamental em matemática e ciências da computação. Em programação uma função é dita recursiva se ele chama a si mesma, e em matemática, funções recursivas são funções definidas em termos delas mesmas.

O exemplo mais clássico de funções recursivas é a função fatorial.

N! = N*(N-1)!

1int fatorial (int N)
2{ 
3    if (N==0) return 1; 
4    return N * fatorial(N-1); 
5}

Um dos quesitos mais importantes no que se refere a funções recursivas é a chamada condição de parada. A condição de parada é a forma pela qual a função recursiva para de se chamar a si mesma. Sem uma condição de parada, funções recursivas podem entrar em um loop infinito, uma situação muito similar ao exemplo a seguir:

1while(1)
2{ 
3    //código do laço 
4}

Funções recursivas provêm o programador de uma maneira intuitiva para modelar muitos problemas. No entanto, funções recursivas fazem uso extensivo da pilha de chamada de funções. Se não bem dimensionadas, elas podem induzir um erro chamado Stack Overflow que acontece quando o espaço reservado para a pilha de chamadas de função é superado.

Exercícios

1. Crie um programa que leia n idades (inteiras),armazene -as e depois mostre-as. O valor de n será informado pelo usuário. Crie funções e procedimentos para realizar as tarefas.

 1#include <stdio.h> 
 2#include <stdlib.h> 
 3
 4int criarvetor (int n); 
 5void lervetor (int n); 
 6void mostrarvetor (int n); 
 7
 8int *idades; // ponteiro utilizado na alocação
 9
10int criarvetor (int n)
11{ 
12    idades = (int*) malloc ((n)* sizeof(int)); // alocação 
13    if (idades == NULL)
14    { 
15        printf ("\nErro reservando memoria"); 
16        return 0; 
17    } 
18    return 1; 
19}
20
21void lervetor (int n)
22{ 
23    int i, *cont = idades; 
24    for (i = 0;i < n; i++)
25    { 
26        printf ("\nDigite o elemento %d ", i + 1); 
27        scanf ("%d",cont++); 
28    } 
29}
30
31void mostrarvetor (int n) 
32{ 
33    int i, *cont = idades; 
34    for (i = 0; i < n; i++)
35    { 
36        printf ("\nO elemento %d eh %d ",i + 1, *cont++); 
37    } 
38}
39
40int main()
41{  
42    int n; 
43    printf ("\n Quantas idades deseja cadastrar ? ");
44    scanf ("%d",&n); 
45    if (criarvetor(n))
46    { 
47        lervetor(n); 
48        mostrarvetor(n);
49        free (idades); // Liberar memória alocada 
50    }
51    return 0;
52}

2. Explique a diferença entre alocação estática e alocação dinâmica de memória.

3. Explique a função que o ponteiro tem na alocação dinâmica.

4. Faça um programa para alocar espaço para colocar o nome do usuário (30 caracteres). Se conseguir alocar, leia esta string e mostre-a ao contrário.

5. As funções recursivas tem uma demanda maior de memória. Por que?

6. O que significa size_t ?

7. Em qual biblioteca (.h) fica o sizeof ?

8. Qual a utilidade do sizeof no tocante a portabilidade ?

9. Construa um programa que leia da entrada padrão o número de linhas e de colunas de uma matriz de floats, aloque espaço dinamicamente para esta e a inicialize, com valores fornecidos pelo usuário, através da entrada padrão. Ao final o programa deve retornar a matriz na saída padrão com layout apropriado.

10. Crie uma biblioteca de funções que gerencie a alocação dinâmica de vetores. Para alocação do vetor a biblioteca deve, ter a seguintes função:

1int aloca(int*  &ptr, int tam)
2{   
3    // aloca um vetor de 'tam' inteiros, retornando 1 se foi possível alocar e 0 se não foi
4    // o parâmentro 'ptr' deve retornar com o apontador para a área alocada 
5}

11. Usando sobrecarga de funções, crie uma rotina com o mesmo nome da anterior, que aloque vetores de floats.

12. Crie funções para preencher os elementos de vetor com um certo valor. Para varrer o vetor, não utilize índices, use apenas aritmética de ponteiros. Faça isto para os vetores de inteiros e de reais.

1void preenche(int* vet, int tam, int n)
2{ 
3    // atribui a todos os elementos do vetor 'vet' o valor 'n' 
4    // não use índices. Use apenas aritmética de ponteiros. 
5}

13. Crie funções para imprimir os elementos de vetor. Para varrer o vetor, não utilize índices, use apenas aritmética de ponteiros. Faça isto para os vetores de inteiros e de reais.

Roteiro

Objetivos

• Revisar a passagem de parâmetros por referência para funções;
• Revisar os métodos de iteração e recursão.

Exercício 1

Crie um arquivo chamado malloc_free.c utilizando um editor de textos padrão (vi, pico, xemacs, gedit) e digite o seguinte programa:

 1#include <stdio.h>
 2#include <stdlib.h>
 3
 4int main( void )
 5{
 6    int numInteiros = 0;
 7    int *pInt, *pIntInit;
 8    int tempInt;
 9    int count;
10    printf( "Digite o numero de inteiros a ser lido:" );
11    scanf( "%d", &numInteiros );
12    if ( !(pInt = malloc( numInteiros * sizeof(int))))
13    {
14        printf("sem memória!\n");
15        exit( 1 );
16    }
17    pIntInit = pInt;
18    for(count = 0; count < numInteiros; count++)
19    {
20        printf( "\n Digite o inteiro [%d]:",count );
21        scanf( "%d", &tempInt );
22        *pInt = tempInt;
23        pInt++;
24    }
25    int acc = 0;
26    pInt = pIntInit;
27    for(count = 0; count < numInteiros; count++)
28    {
29        acc = acc + *pInt;
30        pInt++;
31    }
32    printf("%d", acc);
33    free( pIntInit ); // libera a memória alocada dinâmicamente
34    pIntInit = pInt = NULL;
35    exit( 0 );
36}

Como compilar o programa

gcc malloc_free.c –o malloc_free 

Atividades

a) Escreva uma função que receba o vetor de inteiros “pInt” passado como parâmetro e inverta a ordem dos números; (DICA, gere uma cópia temporária do vetor de inteiros );

b) Escreva uma função que receba o vetor de inteiros “pInt” passado como parâmetro por referência e substitua todos os números do vetor pelas seus quadrados.

Exercício 2

Crie um programa que leia do usuário um número. Este número deve ser maior que 0 e menor que 20. Em seguida o programa deve calcular a série de Fibonacci deste número. Todos os elementos da série de Fibonacci devem ser salvos em um vetor alocado dinamicamente.