Vetores e Matrizes

Vetores podem ser entendidos como um grupo de posições de memória contíguas relacionadas entre si pelo fato de possuírem o mesmo nome e tipo. Por exemplo, uma declaração da forma 

int   V[10] ;
corresponde a reservar uma área contígua de memória suficiente para armazenar 10 inteiros. Para referenciar uma particular posição ou elemento do vetor, especificamos o nome do vetor e o número da posição do vetor (índice) entre colchetes. Isto é, os 10 elementos do vetor V podem ser referenciados respectivamente por 
V[0] V[1] V[2] V[3] V[4] V[5] V[6] V[7] V[8] V[9]

* O que posso fazer com vetores ?
Cada um dos elementos de um vetor pode ser tratado como uma variável. Assim, são válidas as seguintes operações: 
int   V[10] ;   /* declaração */
int   x ;

V[0] = 10;      /* atribuições */
V[1] = 20 ;
V[2] = 30 ;

x = V[0]+V[1]+V[2] ;  /* operações envolvendo elementos do vetor */

* Índices
Note que os índices do vetor variam de 0 a tamanho-1. O primeiro elemento do vetor V é o V[0] e o último é o V[9].

* Declaração
Na declaração de um vetor, o tamanho deve ser dado por uma constante; nunca por uma variável.

Note também a diferença entre a declaração do vetor e a referência a uma posição do vetor. Por exemplo, no trecho a seguir 

int   V[10] ;   /* declaração */


V[6] = 100 ;    /* atribuição de valor 100 na posição 6 do vetor */
10 significa o tamanho (quantidade de elementos) do vetor, enquanto 6 significa uma posição específica, a sexta posição, no vetor (supondo que as posições começam em 0). Note que não faz sentido fazer referências do tipo V[-1] nem V[10], já que os índices do vetor variam de 0 a 9.

* Char, double
Os elementos de um vetor podem também ser char ou double. 
char    c[10] ;      /* vetor de caracteres */
double  num[100] ;   /* vetor de reais      */

* Para que servem vetores ?
Uma das utilidades é simplificar o trabalho de programação. Suponha por exemplo que o seu programa vai ser utilizado para avaliar o desempenho dos alunos de uma sala de aula. Voce quer contabilizar quantos alunos ficaram com nota entre 0 e 0.99, entre 1 e 1.99, entre 2 e 2.99, e assim por diante, até entre 9 e 9.99 e por fim entre 10 e 10.

Voce poderia ter 11 contadores, nota0, nota1, nota2 e assim por diante até nota10, ou então você pode ter um vetor de 11 posições, cada uma para contabilizar a quantidade de notas correspondentes.

Em outras palavras, em vez de escrever 

  int     nota0, nota1, nota2, nota3, nota4, nota5,
          nota6, nota7, nota8, nota9, nota10 ;
  int     i, nalunos ;
  double  p ;

  nota0 = nota1 = nota2 = nota3 = nota4 = nota5 = 0 ;
  nota6 = nota7 = nota8 = nota9 = nota10 = 0 ;

  scanf{"%d", &nalunos} ;

  for(i=0; i<nalunos; i++) {

    scanf("%lf", &p) ;

    if(0<=p && p<1) nota0++ ;
    if(1<=p && p<2) nota1++ ;
    ...
    if(9<=p && p<10) nota9++ ;
    if(p==10) nota10++ ;
  }
pode-se escrever ``equivalentemente'' o seguinte : 
  int     nota[11] ;
  int     i, nalunos ;
  double  p ;

  for(i=0; i<11; i++) {
    nota[i] = 0 ;
  }

  scanf{"%d", &nalunos} ;

  for(i=0; i<nalunos; i++) {

    scanf("%lf", &p) ;
    nota[(int)p]++ ;
  }

Exemplo: Dado um inteiro positivo n e uma seqüência com n inteiros, imprimir a seqüência na ordem inversa a da leitura. 

#include <stdio.h>
#define MAX 100

int main()
{
  int V[MAX] ;
  int i, n ;

  printf("Qual o tamanho da sequencia ?\n") ;
  scanf("%d", &n) ;
  if(n>MAX) {
    printf("A sequencia e' muito longa.\n") ;
    printf("Ela deve conter no máximo %d elementos\n", MAX) ;
    return 0 ;
  }

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

  for(i=n-1; i>=0 ; i--)
    printf("%d", V[i]) ;

  return 0 ;
}
Observe que no comando scanf(%d", &V[i]) ; voce deve usar o operador & (mais precisamente, &V[i]) pois o scanf vai atribuir o valor lido à posição i do vetor, isto é, à variável V[i], e para isso deve-se passar o endereço da variável V[i].

Já quando queremos imprimir o valor que está na ppsição i do vetor, basta considerarmos a variável V[i]. Assim, o comando printf(%d", V[i]) ; imprime o valor de V[i].


E se a seqüência fosse uma frase (isto é, uma seqüência de caracteres) terminada por ponto ? Como seria o programa ? (Desconsidere o ponto na saída). 

#include <stdio.h>
#define MAX 100

int main()
{
  char c, seq[MAX] ;
  int  i, cont ;

  cont = 0 ;
  printf("Digite uma frase terminada por ponto.\n") ;

  scanf("%c", &c) ;  /* le o primeiro caractere */
  while(c != '.' && cont<MAX) {
    seq[cont] = c ;
    cont++ ;
    scanf("%c", &c) ;  /* le o proximo caractere */
  }
  
  if(c != '.') {  /* encheu o vetor antes de terminar a leitura */
    printf("Seqüência muito longa.") ;
    printf("Deve conter no máximo %d caracteres.\n", MAX) ;
    return 0 ;
  }


  /* imprime a seq. lida, de tras para frente */ 
  for(i=cont-1; i>=0 ; i--)
    printf("%c", seq[i]) ;

  return 0 ;
}


Vetores multi-dimensionais e matrizes

O conceito de vetores pode ser extendido para vetores multi-dimensionais. Em vez de pensarmos em algo linear, com um índice, podemos pensar em estruturas com mais de um índice. Um exemplo simples é a caso das matrizes, que podem ser pensadas como vetores de duas dimensões.

Vejamos como declaramos uma matriz (vetor de duas dimensões) : 

int   M[20][10] ;  /* matriz de inteiros com 20 linhas e 10 colunas */
char  C[5][100] ;  /* matriz de caracteres com 5 linhas e 100 colunas */

Da mesma forma que com os vetores unidimensionais, os índices sempre variam de 0 a tamanho-1.

Posso ter vetores com várias dimensões: 

int   M[20][10][5] ;
int   exemplo[10][20][30][40] ;

A diferença é que precisamos fazer referência a um maior número de índices. Numa matriz M, um elemento na linha i e coluna j deve ser referenciado por M[i][j].

Suponha que é dado uma matriz A de inteiros com m linhas e n colunas. Para imprimir esta matriz, o seguinte trecho de código pode ser utilizado: 

  for(i=0; i<m; i++) {
    for(j=0; j<n; j++)
      printf("%d ", A[i][j]) ;
    printf("\n") ;             /* muda linha apos imprimir linha i */
  }

Voltar para o topo


Passagem de vetores e matrizes como argumento de uma função

* Função que imprime um vetor 
/* imprime os n primeiros elementos do vetor V */
void imp_vetor(int V[MAX], int n)
{
  int i ;

  for(i=0; i<n; i++) {
      printf("%d ", V[i]) ;
  }
}

* Função que imprime uma matriz 
/* imprime os elementos das mxn primeiras posicoes da matriz A */
void imp_vetor(int A[MAX][MAX], int m, int n)
{
  int i, j ;

  for(i=0; i<m; i++) {
    for(j=0; j<n; j++)
      printf("%d ", A[i][j]) ;
    printf("\n") ;             /* muda linha apos imprimir linha i */
  }
}

* Função que lê n inteiros e armazena em um vetor 
/* le n inteiros e armazena no vetor V. Assume que n <= MAX */
void le_vetor(int V[MAX], int n)
{
  int i ;

  for(i=0; i<n; i++) {
    scanf("%d ", &V[i]) ;
  }
}

* Função que lê uma matriz 
/* le uma matriz m x n de inteiros e armazena na matriz A. Assume que
m <= MAX e n <= MAX */
void le_matriz(int A[MAX][MAX], int m, int n)
{
  int i, j ;

  for(i=0; i<m; i++)
    for(j=0; j<n; j++)
      scanf("%d ", &A[i][j]) ;

}

* Para usar essas funções 
/* Exemplo ilustrando como usar as funções acima */
#include <stdio.h>
#define MAX  100

void le_vetor(int V[MAX], int n) ;
void imp_vetor(int V[MAX], int n) ;
void le_matriz(int A[MAX][MAX], int m, int n) ;
void imp_matriz(int A[MAX][MAX], int m, int n) ;

int main() {
  int matriz[MAX][MAX], vetor[MAX] ;
  int m, n, p ;

  printf("Qual o tamanho da sequencia ?\n") ;
  scanf("%d", &p) ;
  if(p > MAX) {
    printf("Sequencia muito longa") ;
    return 0 ;
  }

  printf("Digite a sequencia de inteiros\n") ;
  le_vetor( vetor, p ) ;

  imp_vetor( vetor, p ) ;


  printf("Qual o tamanho da matriz?\n") ;
  scanf("%d %d", &m, &n) ;
  if(m > MAX || n > MAX) {
    printf("Matriz muito grande.") ;
    return 0 ;
  }

  printf("Digite a matriz\n") ;
  le_matriz( matriz, m, n ) ;

  imp_matriz( matriz, m, n ) ;

  return 0 ;
}

Note que, apesar das funções le_vetor e le_matriz alterarem o conteúdo das variáveis vetor e matriz, respectivamente, na chamada da função não foi utilizado o operador de endereço &.

Quando um vetor ou matriz é passado como argumento de uma função, C automaticamente passa o endereço deles. Isso acontece pois vetores ou matrizes são, na verdade, apontadores. Assim, na declaração 

int   V[10] ;   /* declaração */
o valor de V é o endereço do primeiro elemento do vetor, isto é, V e &V[0] são a mesma coisa. Para todos os efeitos, V é um apontador e V[i] pode ser encarado como uma variável comum.

Entendendo um pouco melhor, se eu tiver 

int   V[10] ;   /* declaração */
int   *p ;
as seguintes atribuições são equivalentes : 
   p = V ;
   p = &V[0] ;

Neste ponto, vale a pena reforçarmos o conceito de ponteiros. Lembrem-se que usando ponteiros é possível fazer referência ao conteúdo de alguma posição de memória. Por exemplo, se p é um ponteiro para int, isto é, se 

int   *p ;
então *p é o conteúdo na posição de memória cujo endereço é p. Ou seja, no trecho a seguir, 
int   *p ;
int   x ;

p = 1054 ;
x = *p ;
a variável x recebe o valor que se encontra na posição (endereço) 1054 da memória (claro que deve-se tomar cuidado para que a posição de memória referenciada faça sentido!)

Ponteiros são também, antes de mais nada, variáveis. Logo, podemos ``operar'' com elas. Isto é, podemos fazer p = p + 10;, por exemplo. No entanto, neste caso a operação + não é a operação usual de adição. Se o valor de p é 3000, na aritmética convencional o resultado da operação seria 3010. No entanto, quando um inteiro é adicionado ou subtraído de um ponteiro, o valor do ponteiro não é aumentado ou diminuído por aquele inteiro, mas sim por aquele inteiro vezes o tamanho do objeto apontado pelo apontador.

Por exemplo, supondo que un inteiro ocupa 4 bytes, a operação p = p + 10; quando p vale 3000, resultaria em algo como 3000 + 4*10.

Portanto, a operação p++ não incrementa o valor de p de apenas 1, mas sim de 4. Logo, tome cuidado ao escrever coisas como 

  *p++ ;
achando que está incrementando o valor do elemento apontado por p. O comando acima primeiro incrementa o valor de p (isto é, muda o elemento apontado) e depois referencia o valor apontado. O correto, caso voce queira incrementar o valor do elemento apontado por p, é fazer: 
  (*p)++ ;

Concluindo, da mesma forma que 

   p = V ;     e      p = &V[0] ;
são equivalentes, 
   p = V+3 ;     e    p = &V[3] ;
são equivalentes, e portanto, 
   *(V+3)      e       V[3]
também são equivalentes.

Concluindo: na passagem de variáveis ``comuns'' como argumento para uma função, vimos que podemos passar:

Quando vetores ou matrizes são passadas para uma função, o que é passado são os respectivos endereços. Vetores e matrizes são tratados como ponteiros. Logo, para vetores e matrizes só é possível o segundo caso acima. Isto significa que qualquer alteração no valor do vetor ou da matriz dentro da função alterará o vetor ou a matriz original.


Ordenar uma seqüência

As duas funções abaixo recebem um vetor com n (0< n <= MAX) inteiros e ordenam os números do vetor, isto é, após a execução da função, a seqüência que estava armazenada no vetor fica ordenada.

Ordenação por seleção: o algoritmo realiza n-1 passadas. Após a passada i, garante que o elemento que deveria ocupar a posição i na seqüência ordenada está de fato na posição i do vetor.

Explicando melhor, na primeira passada (i=0), o elemento na posição 0 é comparado sucessivamente com os elementos nas posições 1, 2, até n-1. Sempre que o elemento que se encontra na posição 0 é maior que o elemento V[j] com o qual ele está sendo comparado, ambos trocam de posição. Isto garante que na posição 0 mantenho o menor elemento dentre todos os elementos nas posições de 0 a j. Uma vez que isso é feito até o último elemento da seqüência, quando a primeira passada termina, temos certeza que o menor elemento da seqüência se encontra na posição 0 do vetor. Depois, basta repetir o mesmo processo para o restante do vetor (isto é feito nas passadas 2, 3, 4, até n-2). 

void ordena_por_selecao( int V[MAX], int n)
{
  int i, j, aux ;

  for(i=0; i<n-1; i++)
    for(j=i+1; j<n; j++) 
      if(V[i] > V[j]) {
        aux = V[i] ;
        V[i] = V[j] ;
        V[j] = aux ;
      }
}

Ordenação por bolhas (?) ``Bubble sorting''; Aqui a idéia é que a cada passada os elementos leves (pequenos) vão subir uma posição (vão deslocar em direção ao início do vetor) enquanto os mais pesados vão deslocar em direção ao final do vetor. O algoritmo consiste em compararmos, a cada passada, cada dois elementos subsequentes no vetor e trocá-los de posição sempre que eles estiverem invertidos. 

void ordena_por_bolha( int V[MAX], int n)
{
  int passada, j, aux ;

  for(passada=1; passada<n; passada++)
    for(j=0; j<n-1; j++)
      if(V[j] > V[j+1]) {
        aux = V[j+1] ;
        V[j+1] = V[j] ;
        V[j] = aux ;
      }
}
No algoritmo acima, um elemento grande que se encontra no início do vetor pode ser ``deslocado'' até o final do vetor em uma passada, mas um elemento pequeno que se encontra no final do vetor poderá deslocar no máximo uma posição para a frente (em direção ao início do vetor) em uma passada. Logo, no pior caso serão necessárias n-1 passadas até que o menor elemento que se encontrava na última posição desloque até a posição inicial do vetor.

Em alguns casos, um número menor de passadas pode ser suficiente para termos uma seqüência ordenada no vetor. Tente escrever uma função que evita passadas desnecessárias.

Para aqueles com maior interesse, mais detalhes podem ser encontrados nesta página.


Buscar um elemento numa seqüência

Escreva uma função que recebe um vetor com n (n>0) números reais e também um número real x, e devolve a posição de ocorrência de x no vetor caso ele ocorra e -1 caso ele não ocorra no vetor. Lembre que as posições do vetor variam de 0 a n-1. Suponha que a constante MAX que define o tamanho do vetor está adequadamente definida e que n <= MAX. 

/* funcao que verifica se x ocorre em V. Caso ocorra, devolve
   a posicao de ocorrencia, e caso nao ocorra, devolve -1 */

int  procura( double V[MAX], int n, double x )
{
  int i ;

  for(i=0; i<n; i++)
    if(V[i] == x) return i ;

  return -1 ;
}

Exercícios

* Multiplicação de matrizes
(um programa)
Ou uma função, supondo que MAX está bem definido e que as dimensões das matrizes a serem multiplicadas são m x n e n x p, respectivamente. 
/* função que calcula o produto da matriz A (m x n) pela matriz
   B (n x p) e devolve o produto na matriz C */
 
void produto( int A[MAX][MAX], int B[MAX][MAX], int C[MAX][MAX],
              int m, int n, int p)
{
  int i, j, k ;

  /* funcao resultante C tera' dimensao m x p    */
  /* Assim, o for para o i e o j servem para     */
  /* percorrer cada posicao da matriz resultante */

  for(i=0; i<m; i++)
    for(j=0; j<p; j++) {

      /* Calculo do resultado para a posicao (i,j) :           */
      /* corresponde a soma do produto dos elemento na linha i */ 
      /* da matriz A pelos respectivos elementos na coluna j   */
      /* da matriz B.                                          */

      C[i][j] = 0 ;
      for(k=0; k<n; k++)
        C[i][j] = C[i][j] + A[i][k]*B[k][j] ;
    }

}


MAC 110 - Nina S. T. Hirata, 2001