Subsecções

18 Arrays

Considere o seguinte programa. Este programa pede ao usuário notas de 4 estudantes, calcula a média e imprime as notas e a média.

   int main()
   {
      int nota0, nota1, nota2, nota3;
      int  media;

      printf("Entre a nota do estudante 0: ");
      scanf("%d", &nota0);
      printf("Entre a nota do estudante 1: ");
      scanf("%d", &nota1);
      printf("Entre a nota do estudante 2: ");
      scanf("%d", &nota2);
      printf("Entre a nota do estudante 3: ");
      scanf("%d", &nota3);

      media = (nota0 + nota1 + nota2 + nota3) / 4;

      printf("Notas: %d %d %d %d\n", nota0, nota1, nota2, nota3);
      printf("Media: %d\n", media);
  }

Este programa é bem simples, mas ele tem um problema. O que acontece se o número de estudantes aumentar ? O programa ficaria muito maior (e feio !!). Imagine o mesmo programa se existissem 100 estudantes.

O que precisamos é uma abstração de dados para agrupar dados relacionados. Este é o objetivo de arrays em C .

Um array é uma coleção de um ou mais objetos, do mesmo tipo, armazenados em endereços adjacentes de memória. Cada objeto é chamado de elemento do array. Da mesma forma que para variáveis simples, damos um nome ao array. O tamanho do array é o seu número de elementos. Cada elemento do array é numerado, usando um inteiro chamado de índice. Em C , a numeração começa com 0 e aumenta de um em um. Assim, o último índice é igual ao número de elementos do array menos um.

Por exemplo, podemos definir um array nota de tamanho 100 para armazenar as notas dos cem estudantes:

  int nota[100];
Quando o compilador encontra esta definição, ele aloca 200 bytes consecutivos de memória (dois bytes - referente a cada int - para cada nota). Cada nota pode ser acessada dando o nome do array e o índice entre colchetes: como nota[0] (para a primeira nota), nota[1] para a segunda nota, e assim por diantes, até a última nota, nota[99].

18.1 Definindo arrays e acessando seus elementos

A definição de arrays é muito parecida com a definição de variáveis. A única diferença é que em array é necessário especificar seu tamanho (quantos elementos ele tem).

Os colchetes [ e ] são usados na definição do tamanho, como mostra os exemplos a seguir:

        int total[5];

        float tamanho[42];

O primeiro exemplo é um array de 5 inteiros (o tipo int) com o nome total. Como a numeração de arrays começa com 0, os elementos da array são numerados 0, 1, 2, 3 e 4.

O segundo exemplo é um array de 42 elementos do tipo float com índices de 0 a 41.

Cada elemento do array total é do tipo inteiro e pode ser usado do mesmo jeito que qualquer variável inteira. Para nos referirmos a um elemento do array, usamos colchetes também ([ e ]). O valor dentro dos colchetes pode ser qualquer expressão do tipo inteiro. Quando um array é definido, armazenamento suficiente (bytes contínuos na memória) são alocados para conter todos os elementos do array.

O nome do array representa um endereço de memória3 constante que aponta para o início do espaço de armazenamento (o primeiro byte do bloco de bytes). O array, como um todo, não tem um valor, mas cada elemento individual tem um valor.

Note na tabela de precedência abaixo que [ ] tem precedência maior que todos os demais operadores.

Operador Associatividade
   
() [] -> . esquerda para direita
! - ++ -- * \& direita para esquerda
* / % esquerda para direita
+ - esquerda para direita
< <= > >= esquerda para direita
== != esquerda para direita
&& esquerda para direita
|| esquerda para direita
= += -= *= /= %= direita para esquerda
, esquerda para direita

Verifique se você entende as sentenças do programa abaixo.

         int i, x, sala, total[5];
         float area;
         float tamanho[42];
 
         x = total[3];

         i = 4;

         total[i] = total[i-1] + total[i-2];

         total[4]++;

         tamanho[17] = 2.71828;

         sala = 3;

         area = tamanho[sala] * tamanho[sala];

         scanf("%f", &tamanho[41]);

Agora, podermos reescrever o programa que calcula a média de uma classe de 4 alunos:

   int main()
   {
      int indice, nota[4], total = 0;

      for (indice = 0; indice < 4; indice++) {
         printf("Entre a nota do estudante %d: ", indice);
         scanf("%d", &nota[indice]);
      }

      printf("Notas:  ");
      for (indice = 0; indice < 4; indice++) {
         printf("%d ", nota[indice]);
         total += nota[indice];
      }
      printf("\nMedia: %d\n", total/4 );
   }

Exemplo de Saída:

   Entre a nota do estudante 0: 93
   Entre a nota do estudante 1: 85
   Entre a nota do estudante 2: 74
   Entre a nota do estudante 3: 100
   Notas:  93 85 74 100
   Media: 88

O programa é consideravelmente mais curto. Note que um & ainda precede o elemento do array passado para o scanf(). Não é necessário usar parênteses porque [] tem maior precedência que &.

O único problema é que ainda não é fácil modificar o programa para cem alunos porque 4 está em vários pontos do programa. Nós podemos usar o #define para manter o tamanho do array como uma constante simbólica ao invés de utilizar uma constante numérica.

   #define ESTUDANTES 4

   int main()
   {
      int nota[ESTUDANTES], indice, total = 0;

      indice = 0;
      while (indice < ESTUDANTES) {
        printf("Entre a nota do estudante %d: ",indice);
        scanf("%d", &nota[indice]);
        indice += 1; /* mesma coisa que "indice = indice + 1" */
      }
      printf("Notas: ");

      indice = 0;
      while (indice < ESTUDANTES) {
        printf("%d ", nota[indice]);
        total = total + nota[indice];
        indice += 1; /* mesma coisa que "indice = indice + 1" */
      }
      printf("\nMedia: %d\n", total / ESTUDANTES );
   }

18.2 Inicialização de arrays

Os arrays podem ser inicializados quando são definidos. Se o array não for inicializado, então ele contem valores indefinidos (também conhecidos como lixo).

Para inicializar um array, um valor para cada elemento deve ser especificado. Estes valores devem estar entre chaves ({ e }) e são separados por vírgula (,). Alguns exemplos:

      int valor[4] = { 1, 42, -13, 273 };

      /* o tamanho do array pode ser omitido */
      int peso[] = { 153, 135, 170 };

No primeiro exemplo, valor é um array de 4 inteiros onde valor[0] e' 1, valor[1] e' 42, valor[2] e' -13, e valor[3] e' 273.

Note que no segundo exemplo, o tamanho do array foi omitido. Neste caso, o compilador calcula o tamanho como sendo o número de elementos listados. Quando um array é definido, se ele não for inicializado, o tamanho do array deve ser especificado. Se o array for inicializado, o tamanho pode ser omitido. O segundo exemplo acima é equivalente a

      int peso[3] = { 153, 135, 170 };

Se o tamanho não for omitido, o número de elementos presentes não deve exceder o tamanho. Se exceder, o compilador gerará uma mensagem de erro. Se houver menos elementos na lista de inicialização, então os elementos dados são usados para inicializar os primeiros elementos do array. Qualquer elemento não inicializado conterá lixo.

Note que este tipo de inicialização só é válido no contexto onde o array é definido. Uma sentença como a seguinte produzirá um erro do compilador, uma vez que arrays só podem ser inicializados quando definidos.

      int erro[5];

      erro = { 2, 4, 6, 8, 10 };      /* ISTO ESTA' ERRADO */

Há mais uma restrição na inicialização de um array. Os valores devem ser todos constantes - nenhuma variável ou expressão é permitida. O seguinte trecho de programa produz um erro porque um dos valores de inicialização é uma variável:

      int x = 21;
      int yy[3] = { 1, 2, x };   /* ISTO ESTA' ERRADO */

18.3 Verificação de Limite

Quando um array é definido, é alocado espaço em memória para conter todos os elementos do array (não mais). O tamanho do array é dado explicitamente escrevendo o tamanho, ou implicitamente, inicializando o array. Embora arrays tenham tamanhos específicos, é possível que um programa tente acessar endereços de memória de elementos fictícios, ou seja, endereços de memória que não pertencem ao array. Isto acontece quando usamos um índice que não esteja entre 0 e n-1 para um array de tamanho n. O compilador não gera nenhum aviso quando isto acontece. Quando executamos um acesso ``fora dos limites'' do array, o resultado pode ser desastroso. Isto siginifica que o programa pode não fazer nada, cancelar a execução, travar o computador, entrar em um loop infinito, etc.

Se você executar uma atribuição a um elemento do array fora do seu limite, você estará escrevendo em um endereço de memória que pode conter algo importante, destruindo-o. Em geral, erros como estes são difíceis de encontrar, já que o programa pode até executar, só que faz algo ``estranho''. Se você estiver usando o Dev-C$++$ , você poderá ver uma mensagem como ``Esta aplicação violou a integridade do sistema devido a execução de uma instrução inválida e será cancelada.''. Não entre em pânico !! Você terá que reinicializar o seu computador e examinar o seu programa cuidadosamente para achar acessos a array fora do seu limite. é claro que ao reinicializar o seu computador, você perderá todo o seu trabalho se não tiver salvado antes. MORAL: depois que seu programa compilar com sucesso, salve o seu programa em disco antes de executá-lo.

Por exemplo, considere o seguinte programa:

    int main()
    {
        int ops[10], i;

        /* Acesso fora dos limites quando i = 10 */
        i = 0;
        while (i <= 10)
        {
            ops[i] = 0;
            i += 1;
        }
    }

Este programa conta de 0 a 10, inicializando cada elemento do array com 0. O problema ocorre quando i tem o valor 10. Neste ponto, o programa coloca 0 em ops[10]. Isto pode produzir resultados indefinidos (e desastrosos) embora o compilador não gere nenhum erro.

18.4 Arrays como argumentos

Para passar um array como argumento (com todos os seus elementos) passamos o nome do array. Considere o exemplo abaixo.

/usr/local/lib/tex/inputs///Programas/array_max.c

Aqui está um exemplo de execução deste programa

   Entre um inteiro: 73
   Entre um inteiro: 85
   Entre um inteiro: 42
   Entre um inteiro: -103
   Entre um inteiro: 15
   O maior e' 85

Em main() a chamada para array\undmax() tem valor como seu argumento, que é copiado para o parâmetro formal a, que é um array de inteiros. Note que o tamanho não foi especificado, somente o nome do array, a. Porém é também correto incluir o tamanho (isto é uma questão de estilo - escolha o que você preferir):

   int array_max(int a[TAMANHO])
   {
     ...
   }

A inclusão do tamanho de um array unidimensional na definição da função é somente por razões de legibilidade (para arrays multi-dimensionais, todas as dimensões exceto a primeira deve ser especificada).

Até este ponto, parece que não há diferença entre passar uma variável simples e um array como argumento para uma função. Mas há uma diferença fundamental: QUANDO PASSAMOS O ARRAY COMO ARGUMENTO, ALTERAÇÕES NO ARRAY FEITAS DENTRO DA FUNÇÃO ALTERAM O CONTEÚDO DO ARRAY PASSADO COMO PARÂMETRO REAL.

Note que isto não acontece quando uma variável simples é passada como argumento. Considere o exemplo seguinte:

/usr/local/lib/tex/inputs///Programas/troca_01.c

A saída deste programa é:

x=10 
v[0]=60 v[1]=70 v[2]=80

O valor da variável x do programa principal não se altera porque como já vimos nas notas de aula 7, quando a função troca é chamada, o valor do argumento real x é avaliado, que é 10, este valor é copiado para o parâmetro formal a da função troca e a função então é executada. O parâmetro a da função é tratada como variável local, portanto quando atribuímos 20 a a, estamos atribuindo 20 a uma variável local. Terminada a função, a execução retorna ao programa principal, que imprime o valor de x, que não foi alterado, ou seja, imprime x=10.

Quando a função troca_vet é chamada, o array v é passado como argumento e ``copiado'' para o parâmetro formal vet. A função é então executada, e os elementos do array são alterados para 60, 70, 80. Como mencionado anteriormente, quando passamos um array como parâmetro, as alterações feitas no array dentro da função alteram o array passado como parâmetro. Portanto, quando a função termina e a execução continua no programa principal com a impressão dos valores dos elementos de v, será impresso 60, 70, 80, os novos valores alterados de dentro da função troca_vet.

Vamos entender por que quando passamos só o nome do array como argumento as alterações afetam o array passado como parâmetro real. Como já mencionamos anteriormente, quando um array é definido, como v no programa principal acima, é alocado espaço suficiente na memória para conter todos os elementos do array. Na ilustração abaixo, são alocados 6 bytes de memória a partir do endereço 1342 para conter o array. O array como um todo não tem um valor, mas cada elemento do array tem (neste caso, foram inicializados com 30, 40, 50). O nome do array, na verdade, contém o endereço onde começa o array, neste caso, o endereço 1342.

Portanto, quando passamos o nome do array como argumento para uma função estamos na realidade passando como argumento o endereço de memória onde começa o array. No exemplo anterior, 1342 é passado como argumento para o parâmetro formal vet da função troca_vet. Portanto, da mesma forma que no caso da variável simples, o valor de v, que é o endereço 1342, é copiado para o parâmetro vet de troca_vet. Então, quando a função troca_vet é executada, vet é um array de elementos do tipo int que começa no endereço 1342. Quando atribuímos o valor 60 a vet[0], estamos atribuindo 60 ao primeiro elemento do array que começa no endereço 1342. Como este é o mesmo endereço onde começa o array v do programa principal, quando a função troca_vet termina, o array v ``enxergará'' o valor dos elementos do array que começa no endereço 1342, que foram alterados pela função.

\includegraphics[scale=0.5]{ptrarr}

Quando passamos variáveis simples como argumento para uma função estamos passando somente o valor da variável, portanto, de dentro da função não é possível saber qual o endereço da variável para poder alterá-la.

Lembre-se que o endereço só é passado para a função quando passamos o array COMO UM TODO (ou seja, o nome do array, sem ser indexado por um elemento). Se passarmos como argumento apenas um elemento do array, o comportamento é o mesmo que se passássemos uma variável simples. Ou seja, o nome do array indexado por um valor entre colchetes refere-se ao valor do elemento do array, enquanto o nome do array sozinho refere-se ao endereço onde começa o array. Assim, no programa abaixo:

/usr/local/lib/tex/inputs///Programas/troca_02.c

A saída do programa é:

v[0]=30 
v[0]=60 v[1]=70 v[2]=80

Outro exemplo: a função inicializaArray abaixo inicializa todos os elementos do array valor com um valor passado como argumento pelo programa principal.

/usr/local/lib/tex/inputs///Programas/inicializa_array.c

Como as alterações feitas por inicializaArray são vistas do programa principal, depois da função inicializaArray ser executada, no programa principal todos os elementos do array valor terão o valor 42.

18.5 Exemplo: pesquisa linear de um array

Pesquisar (procurar) em um array um determinado valor (chamado de chave) é um problema muito comum em programação. Ele tem diversas aplicações. Por exemplo, podemos pesquisar um array de notas para verificar se algum aluno tirou 100 na prova. Há diversos algoritmos de pesquisa: cada um com suas vantagens e desvantagens. Nestas notas de aula, discutiremos um algoritmo simples, chamado de pesquisa linear. A pesquisa é feita usando uma repetição e examinando cada elemento do array a cada repetição e comparando o elemento com a chave que buscamos. A pesquisa termina quando um elemento do array que ``casa'' com a chave é encontrada, ou quando o array todo é percorrido e a chave procurada não é encontrada.

18.5.1 O Problema

Escreva uma função pesquisa\undlinear que tem como argumento de entrada: um array de inteiros a ser pesquisado, o tamanho do array, e uma chave (um valor inteiro) a ser procurado. A função retorna um inteiro: o índice do elemento do array (se a chave for achada) ou -1 caso contrário.
  1. Protótipo:
    int pesquisa_linear(int [], int, int);
    
  2. Definição:
    /usr/local/lib/tex/inputs///Programas/pesquisa_linear.c
    

18.6 Exemplo: somar os elementos de dois arrays

18.6.1 O Problema

Escrever uma função que some dois arrays de floats, do mesmo tamanho. Dar o resultado em um terceiro array.
  1. Protótipo:
      void soma_array( float [], float [], float [], int );
    

  2. Definição de soma\undarray():

    /usr/local/lib/tex/inputs///Programas/soma_array.c
    

18.7 Exemplo: Ordenação de um vetor - Versão 1

Um outro programa muito popular com arrays é ordená-lo de acordo com algum critério. Por exemplo, um array de inteiros pode ser ordenado em ordem crescente ou decrescente. O apresentado a seguir é um algorítmo básico e nem um pouco eficiente, denominado Select sort.

Ele usa o fato simples de comparar cada elemento de um array com o restante deste. Quando se acha o menor, ocorre uma troca de valores entre o elemento sob análise e o outro elemento do array que é o menor.

Por exemplo, se começarmos com um array: 9 5 2 7 3 8 1 4 6, (o primeiro elemento é 9 e o último elemento é 6) isto é o que acontece com os elementos do array depois de cada passagem sobre ele (e consequente troca de valores):

passagem   conteudo do array depois da passagem
~~~~       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
0 -->       9  5  2  7  3  8  1  4  6

1 -->       1  5  2  7  3  8  9  4  6

2 -->       1  2  5  7  3  8  9  4  6

3 -->       1  2  3  7  5  8  9  4  6

4 -->       1  2  3  4  5  8  9  7  6

5 -->       1  2  3  4  5  8  9  7  6

6 -->       1  2  3  4  5  6  9  7  8

7 -->       1  2  3  4  5  6  7  9  8

8 -->       1  2  3  4  5  6  7  8  9

Note que mesmo que se começássemos com um array ordenado de 9 elementos, ainda assim o algoritmo dado faz 8 passagens sobre o array.

18.7.1 Protótipo da função e definição

  1. Protótipo
    void ordena(int [], int);
    
  2. Definicao
    /usr/local/lib/tex/inputs///Programas/ordena_array_02.c
    

18.8 Exemplo: Ordenação de um vetor - Versão 2

O algoritmo abaixo é ligeiramente melhor que o anterior e é chamado Bubble sort. Ele é bastante simples, porém ainda não muito eficiente.

Basicamente, o algoritmo funciona da seguinte forma:

Por exemplo, se começarmos com um array: 9 8 7 6 5 4 3 2 1, (o primeiro elemento é 9 e o último elemento é 1) isto é o que acontece com os elementos do array depois de cada passagem sobre ele (e troca de valores adjacentes):

passagem   conteudo do array depois da passagem
~~~~       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1 -->       1  9  8  7  6  5  4  3  2

2 -->       1  2  9  8  7  6  5  4  3

3 -->       1  2  3  9  8  7  6  5  4

4 -->       1  2  3  4  9  8  7  6  5

5 -->       1  2  3  4  5  9  8  7  6

6 -->       1  2  3  4  5  6  9  8  7

7 -->       1  2  3  4  5  6  7  9  8

8 -->       1  2  3  4  5  6  7  8  9

Note que, também aqui, mesmo que se começássemos com um array ordenado de 9 elementos, ainda assim o algoritmo dado faz 8 passagens sobre o array.

Isto pode ser melhorado da seguinte forma: Antes de começar cada passagem, inicializamos uma variável ordenado com 1. Se durante a passagem uma troca de valores ocorrer, trocamos o valor da variável para 0. Assim, se depois da passagem, o valor da variável continuar sendo 1, isso significa que nenhuma troca ocorreu e que o array está ordenado.

18.8.1 Algoritmo Bubble Sort otimizado

Enquanto o array nao estiver ordenado
  1. inicializar ordenado com 1
  2. comparar pares adjacentes do array
    troque seus valores se estiver fora de ordem
    ordenado = 0.

18.8.2 Protótipo da função e definição

  1. Protótipo
    void ordena(int [], int);
    
  2. Definicao
    /usr/local/lib/tex/inputs///Programas/ordena_array_01.c
    

18.9 Comentários Finais

Neste curso, um dos únicos lugares que veremos o nome do array sem estar indexado é quando passamos o array (como um todo) para uma função. Para outras finalidades, veremos sempre o array indexado. Por exemplo, o seguinte trecho de programa está errado:

  int main(void){
    int arr1[4] = {10, 20, 30, 40};
    int arr2[4];

    arr2 = arr1;       /* ERRADO: NÃO copia arr1 em arr2 */
                       /* tem que copiar elemento por elemento */

    if( arr1 == arr2 ) /* ERRADO: NÃO podemos comparar arrays inteiros */ 
      printf(``X'');   /* tem que comparar elemento por elemento */
}



Notas de rodapé

... memória3
Este valor de endereço de memória é conhecido em C como ponteiro. Este conceito será visto com detalhes nos próximos capítulos.
Armando Luiz Nicolini Delgado
2013-10-21