Prof. Ruan Delgado Gomes

GComPI - IFPB Campina Grande

Arrays, Ponteiros e Strings

1 - Arrays

Existem problemas em que é necessário armazenar e processar um conjunto (possivelmente grande) de valores do mesmo tipo. Por exemplo, considere um programa que leia da entrada 1000 valores reais e depois informe a quantidade de valores acima da média. Para resolver esse problema, é necessário armazenar os 1000 valores, calcular a média aritmética desses 1000 valores, e por fim verificar quantos desses 1000 valores são maiores que a média que foi calculada. Utilizando apenas os conhecimentos que foram discutidos até o momento neste material, nós precisaríamos declarar 1000 variáveis e depois escrever milhares de linhas de código para conseguir ler da entrada os 1000 valores, calcular a média aritmética e verificar quantos valores são maiores que a média. Naturalmente, essa é uma solução que demandaria muito tempo e teria grande probabilidade de apresentar erros. O código a seguir ilustra de maneira compacta como seria essa solução pouco inteligente para o problema.

#include <stdio.h>
int main() {
	double v1,v2,v3...v1000;
	double media;
	int qtd = 0;
	scanf("%lf",&v1);
	scanf("%lf",&v2);
	... // mais 997 linhas
	scanf("%lf",&v1000);
	media = (V1 + V2 + V3 +...+v1000)/1000;
	if(v1 > media) qtd++;
	if(v2 > media) qtd++;
	... // mais 997 linhas
	if(v1000 > media) qtd++;
	printf("%d\n",qtd);
	return 0;
}

Felizmente, as linguagens de programação geralmente oferecem algum mecanismo para declararmos um grande conjunto de variáveis de um mesmo tipo utilizando pouco código. Também é possível manipular esse conjunto de valores utilizando estruturas de repetição, quando o mesmo processamento é realizado em todos os valores do conjunto, como é o caso do exemplo mostrado. Em C existe o conceito de array, que consiste em um conjunto de elementos de um mesmo tipo.

Para declarar um array, precisamos informar o tipo dos elementos que serão armazenados dentro do array e a quantidade de elementos, seguindo a sintaxe mostrada a seguir:

<tipo> <nome_do_array> [quantidade_de_elementos];

O código a seguir mostra alguns exemplos de declaração e manipulação de arrays.

#include <stdio.h>
int main() {
	char nome[50];
	double notas[4];
	scanf("%s", nome);
	scanf("%lf", & notas[0]);
	scanf("%lf", & notas[1]);
	scanf("%lf", & notas[2]);
	scanf("%lf", & notas[3]);
	double media = (notas[0] + notas[1] + notas[2] + notas[3])/4;
	printf("A media de %s foi %lf\n", nome, media);
	return 0;
}

Neste exemplo de código são declarados dois arrays. O primeiro é um array de char com 50 elementos, ou seja, uma string de até 49 caracteres (o último elemento é reservado para um caractere especial que indica o final da string). No Capítulo 1 já foi mostrado como declarar, ler e escrever strings em C. O segundo é um array de valores reais (double), que representa um conjunto de notas. No código do exemplo, quatro notas são lidas da entrada, além do nome do aluno, e é calculada a média aritmética das quatro notas que são armazenadas dentro do array.

1.1 - Acessando elementos do array

Para acessar ou modificar os valores armazenados em um array, deve-se indexa-lo; ou seja, informar qual a posição do elemento dentro do array que se deseja acessar ou modificar. Em C, considerando um array de N elementos, ele pode ser indexado nas posições entre 0 e N-1. Por exemplo, o array notas, do código mostrado anteriormente, só pode ser indexado entre 0 e 3, uma vez que ele possui 4 elementos.

A indexação fora dos limites causa um erro em tempo de execução (runtime error); ou seja, um erro que só ocorre durante a execução do programa, mas não é identificado em tempo de compilação. Isso pode ser perigoso, pois um mesmo programa pode executar várias vezes sem apresentar erro, mas apresentar erro para um caso de teste específico. Portanto, sempre que realizar a indexação de um array em um trecho de código, analise se existe a possibilidade de haver indexação fora dos limites, especialmente quando o valor do índice for oriundo de algum cálculo realizado anteriormente e que depende de valores fornecidos pela entrada. Nesse caso, deve-se analisar o intervalo de valores permitidos para a entrada e verificar se em algum caso o cálculo resulta em um valor de índice inválido. Nesses casos, deve-se corrigir o código que calcula o índice ou realizar um tratamento para só permitir o acesso ao array quando o índice calculado for válido.

Voltando ao exemplo do início da seção, se quisermos ler 1000 valores da entrada de um mesmo tipo, podemos declara-los como um array de 1000 elementos. Além disso, podemos usar uma repetição para ler todos os elementos da entrada. Quando usamos a estrutura de repetição for, por exemplo, em geral é usado um contador, que é incrementado em cada repetição, e serve para contar a quantidade de repetições já realizadas e indicar o momento em que o loop deve encerrar (por meio de uma condição). Esse contador pode ser usado para indexar os elementos do array em cada repetição, de modo que para cada iteração do loop um elemento diferente do array é acessado. O código a seguir mostra a implementação do problema de motivação (ou seja, ler 1000 valores reais e informar quantos estão acima da média) utilizando array e repetição para acessar e processar os elementos do array.

#include <stdio.h>
#define SIZE 1000

int main() {
    double val[SIZE];
    double media = 0;
    int i = 0;
    for(i = 0; i < SIZE; i++) {
        scanf("%lf", &val[i]);
        media += val[i];
    }
    media = media/SIZE;
    int qtd = 0;
    for(i = 0; i < SIZE; i++) {
        if(val[i] > media) qtd++;
    }
    printf("Quantidade de valores acima da media: %d\n",qtd);
    return 0;
}

No exemplo, a variável i, que é usada para contar a quantidade de repetições, também é usada para indexar o array. Perceba que o i sempre começa com o valor 0 e possui o valor SIZE-1 na última repetição, sendo que SIZE é uma constante que define o tamanho do array (ver segunda linha de código). Dessa forma, em cada iteração do for, um elemento diferente do array é acessado. Utilizando uma constante para definir o tamanho do array, como no exemplo mostrado, é possível modificar esse programa para funcionar com arrayes de tamanhos diferentes de forma mais rápida, bastando apenas modificar o valor da constante na linha 2. Caso não fosse utilizada essa estratégia, qualquer mudança no tamanho do array iria requerer modificações em todas as linhas que usam o tamanho do array (i.e. linhas 5, 8, 12 e 14).

1.2 - Acesso a Elementos da Vizinhança em um Array

Em alguns problemas, é necessário realizar um tratamento diferenciado para os elementos que se localizam nas extremidades do array. Isso ocorre quando é necessário acessar elementos da vizinhança (anteriores ou posteriores) de cada elemento do array para realizar algum processamento. O problema é que o primeiro elemento não possui elemento anterior e o último elemento não possui elemento posterior. Portanto, usualmente a solução desses problemas pode levar a um acesso ilegal ao array à medida em que se processa os elementos próximos das extremidades.

Considere o seguinte problema como exemplo: faça um programa que leia da entrada 10 valores inteiros e armazene-os em um array. Posteriormente, verifique quantos elementos do array possuem valor menor que o seu sucessor no array. Por exemplo, para a entrada a seguir:

2 3 5 4 6 7 6 3 7 1

Seria fornecida a saída:

5 valores menores que o sucessor

Perceba que, de fato, apenas 5 valores são menores que seus sucessores, no caso de teste fornecido (i.e. 2, 3, 4, 6 e 3). A solução para esse problema é mostrada no código a seguir:

#include <stdio.h>
#define SIZE 10

int main() {
    int vet[SIZE];
    int i;
    for(i = 0; i < SIZE; i++) {
        scanf("%d",&vet[i]);
    } 
    int qtd = 0;
    for(i = 0; i < SIZE; i++) {
        if(i < SIZE-1) {
            if(vet[i] < vet[i+1]) qtd++;
        }
    }
    printf("%d valores menores que o sucessor\n", qtd);
    return 0;
}

Note que dentro do for que verifica se os elementos do array são menores que os seus sucessores, a verificação só ocorre quando i < SIZE-1. Isso impede de executar o código que compara um elemento com seu sucessor (vet[i] < vet[i+1]) quando o i é igual a SIZE-1; ou seja, quando se está acessando o último elemento do array. Se essa comparação fosse executada para esse caso, ao indexar com o array com i+1, seria realizado um acesso fora dos limites do array, o que poderia causar um erro em tempo de execução.

Agora considere outro problema de exemplo: faça um programa que leia da entrada 10 valores inteiros e armazene-os em um array. Posteriormente, verifique quantos elementos do array possuem valor menor que a soma dos dois elementos posteriores. Para esse problema, deve-se considerar que o conjunto de valores possui uma organização circular; ou seja, o elemento posterior do último elemento do array é o primeiro elemento do array. Por exemplo, considerando um array de 10 elementos, os dois elementos posteriores ao elemento da posição 8 são os elementos das posições 9 e 0, e os dois elementos posteriores ao elemento da posição 9 (última posição do array) são os elementos das posições 0 e 1 (primeiro e segundo elementos do array).

Para a entrada a seguir:

2 3 5 4 1 0 6 4 7 1

Seria fornecida a saída:

7 elementos menores que a soma dos dois sucessores

Como exercício, avalie o caso de teste de entrada e verifique quais são os 7 valores que são menores que a soma dos seus dois sucessores, para garantir que o problema foi bem compreendido. A solução para esse problema é mostrada no código a seguir:

#include <stdio.h>
#define SIZE 10

int main() {
    int vet[SIZE];
    int i;
    for(i = 0; i < SIZE; i++) {
        scanf("%d",&vet[i]);
    }
    int qtd = 0;
    for(i = 0; i < SIZE; i++) {
        if(i == SIZE-2) { //penultimo elemento
            if(vet[i] < (vet[i+1] + vet[0])) qtd++;
        }
        else if(i == SIZE-1) { //ultimo elemento
            if(vet[i] < (vet[0] + vet[1])) qtd++;
        }
        else { //caso geral
            if(vet[i] < (vet[i+1] + vet[i+2])) qtd++;
        }
    }
    printf("%d elementos menores que a soma dos dois sucessores\n",qtd);
    return 0;
}

Note que nesse caso foi necessário tratar de forma individual dois casos especiais, o caso de acesso ao penúltimo elemento e o caso de acesso ao último elemento do array. Todos os outros elementos entram no caso geral. Uma solução mais elegante para esse problema é mostrada a seguir, usando o operador módulo (resto de divisão). Fica como exercício para o aluno a simulação desse código para verificar como ele funciona.

#include <stdio.h>
#define SIZE 10

int main() {
    int vet[SIZE];
    int i;
    for(i = 0; i < SIZE; i++) {
        scanf("%d",&vet[i]);
    }
    
    int qtd = 0;
    for(i = 0; i < SIZE; i++) {
        int i1 = (i+1)%SIZE;
        int i2 = (i+2)%SIZE;
        if(vet[i] < (vet[i1] + vet[i2])) qtd++;
    }
    printf("%d elementos menores que a soma dos dois sucessores\n",qtd);
    return 0;
}

Exercícios no beecrowd

Resolver os seguintes problemas no beecrowd, usando a linguagem de programação C:

• 1245 -- Botas Perdidas -- link
• 1533 -- Detetive Watson -- link
• 1171 -- Frequência de Números -- link
• 1089 -- Loop Musical -- link
• 2248 -- Estágio -- link
• 1225 -- Coral Perfeito -- link
• 1107 -- Escultura à Laser -- link
• 1125 -- Fórmula 1 -- link

2 - Ponteiros

Toda variável declarada dentro de um código representa um local de memória alocado para armazenar valores de um determinado tipo. A memória é dividida em posições de memória que podem ser alocadas e cada posição de memória possui um endereço. Quando se declara uma variável, o seu identificador abstrai o seu endereço, de modo que o programador pode salvar valores e ler valores de um determinado local de memória a partir do seu identificador. A Figura 1 representa de maneira conceitual a memória principal de um computador. (obs: alguns detalhes são omitidos ou simplificados nessa representação, como o tamanho dos blocos de memória, alinhamento etc. No entanto, é suficiente para entender o conceito de ponteiro a ser apresentado).

As variáveis com identificadores A, B, C e D são do tipo int. Perceba que cada variável possui um endereço correspondente, listado na parte de baixo (os endereços de memória usualmente são representados em hexadecimal). Por exemplo, o endereço da variável A é 0x01 e o endereço da variável D é 0x07.

Em C, assim como em outras linguagens de programação, existe um tipo especial de dados, denominado ponteiro, que pode armazenar o endereço de posições de memória; ou seja, o endereço físico de outras variáveis. Para declarar um ponteiro de um determinado tipo, usa-se a seguinte sintaxe:

<tipo>  *<identificador_do_ponteiro> ;

Deve-se definir o tipo da variável que o ponteiro é capaz de referenciar e usa-se * seguido do identificador do ponteiro. Por exemplo, considere a declaração a seguir:

float *pR;

Nesse caso, um ponteiro denominado pR é declarado e pR é capaz de armazenar o endereço e referenciar variáveis do tipo float.

No trecho de código a seguir são exemplificadas a declaração e a utilização de ponteiros. No exemplo, são declaradas quatro variáveis do tipo int (A, B, C e D) e três ponteiros para int (pA, pB, pC).

#include<stdio.h>

int main() {
    int A, B, C, D;
    int *pA, *pB, *pC;  //int * declara um ponteiro para int
   
    A = 30;
    B = 25;
    C = 5;
    D = 15;
    
    pA = &A; //&A retorna o endereço de A
    pB = &B;
    pC = &C;
    
    //* é usado pra acessar a variável apontada por um ponteiro
    printf("Soma de A + B: %d\n", (A+B));
    printf("Soma de A + B: %d\n", (*pA+B));
    printf("Soma de A + B: %d\n", (*pA+*pB));

    return 0;
}               

As variáveis pA, pB e pC armazenam posições de memória utilizadas para armazenar valores inteiros (do tipo int). É importante notar que ao serem declarados, os ponteiros não apontam necessariamente para um endereço de memória válido. Em C existe uma constante, denominada NULL, que indica que um ponteiro está nulo, ou seja, não aponta para qualquer posição de memória.

Perceba que o código apresentado no exemplo corresponde exatamente à situação de memória representada pela Figura 1. Foram atribuídos os valores 30, 25, 5 e 15 às variáveis A, B, C e D , respectivamente. Após isso, temos o comando pA = &A. O operador & retorna o endereço de memória de uma variável. Dessa forma, esse comando atribui ao ponteiro pA o endereço de memória da variável A. Como podemos ver na figura, o endereço da variável A é igual a 0x01; ou seja, após esse comando pA passa a armazenar o valor 0x01. Nos comandos seguintes pB passa a armazenar o endereço da variável B (igual a 0x02) e pC passa a armazenar o endereço da variável C (igual a 0x03). Esses endereços colocados na figura são apenas um exemplo. Na prática não se sabe de antemão qual será o local da memória onde uma variável vai ser alocada. No entanto, em geral não é necessário saber o valor do endereço de memória de uma variável, uma vez que é possível obter esse valor por meio do operador &.

Também é possível acessar o valor que está armazenado no local de memória apontado por um ponteiro. Por exemplo, como pA aponta para o endereço de memória de A, podemos utilizar um operador para acessar o valor armazenado em A a partir de pA. Para acessar o valor armazenado no local apontado por um ponteiro, utilizamos o operador * (chamado de operador de desreferência), antes do identificador do ponteiro. Por exemplo, *pA retorna o valor armazenado pela variável A, uma vez que pA contém o endereço de A; ou seja, *pA vai retornar o valor 30 no nosso exemplo. Dessa forma, perceba que em nosso exemplo as três saídas do final são equivalentes, de modo que a saída desse programa será:

Soma de A + B: 55
Soma de A + B: 55
Soma de A + B: 55

Nessa seção foi apresentado apenas o conceito de ponteiro e a sintaxe básica para declaração e operação com ponteiros. Mais na frente a utilidade dos ponteiros será melhor esclarecida, mais especificamente para alocação dinâmica de memória, passagem de parâmetros de funções por referência e para a implementação de estruturas de dados dinâmicas.

3 - Strings