MC102MN

Introdução a Algoritmos e programação de computadores

Aula VII, vetores

O modelo de memória de vetores

Até agora, em C, todos os tipos de variáveis que manipulamos eram tipos básicos. Esses tipos tem a propriedade de que eles são copiados sempre. Por exemplo, se você faz

a = 2;
b = a;
a += 1;
printtf("%d", b);
você vai ver 2, e não 3. Com vetores, a coisa fica um pouco mais complexa e precisamos de mais distinções para entender o que está acontecendo.

Antes de eu explicar tudo, no entanto, vou explicar como se declara um vetor. Digamos que temos um tipo de dados chamado <tipo>. Um vetor de 10 elementos de dados do tipo <tipo> chamado v se declara:

<tipo> v[10];

Os elementos desse vetor, então, serão

v[0], v[1], v[2], v[3], v[4], v[5], v[6], v[7], v[8] e v[1]
Notem que o primeiro é o de índice 0 e o último é o 9. O compilador c não te avisa se você fizer
v[-1] = v[10];
mas isso acessa posições aleatórias da memória e gera bugs muito complicados de se corrigir. Veremos um exemplo mais tarde.
  • Vetores não são copiados automaticamente

    Valores simples como int, float, char, etc, em C, tem um status diferente de vetores. Além dos valores serem imutáveis, eles são copiados quando são passados como parâmetro para uma função. Ou seja, se fazemos

    int f(int x) {
      x += 1;
      return x;
    }
    
    int main(int argc, char *argv[]) {
      int i = 0;
      f(i);
      printf("%d\n", i);
      return 0;
    }
    
    veremos que o valor impresso de i é 0. Já vetores são passados "por referência", o que significa que todos os usos daquele valor vão poder modificá-lo. Então se convertermos o código acima para vetores, temos que
    int f(int x[1]) {
      x[0] += 1;
      return x[0];
    }
    
    int main(int argc, char *argv[]) {
      int i[1];
      i[0] = 0;
      f(i);
      printf("%d\n", i[0]);
      return 0;
    }
    
    o valor impresso será 1. Isso é feito porque vetores em C podem ser arbitrariamente grandes (eu rotineiramente uso vetores que ocupam mais de 1G de memória RAM), e copiá-los para passar para uma função deixaria o programa lento demais. Então a primeira diferença entre vetores e variáveis é que vetores são modificáveis por outras funções, enquanto variáveis não.
  • Vetores não podem ser retornados

    Outra diferença importante é a seguinte: vetores não podem ser retornados. Quando o compilador C vê a declaração de um vetor, o espaço para guardar aqueles valores é criado na "tabela de variáveis" daquela execução (que nem criamos uma tabela quando fazemos o teste de mesa), que é apagada quando saímos da função. Então o código seguinte é válido:

    void f1(int x[10]) {
      printf("%d", x[5]);
    }
    void f2() {
      int x[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
      f1(x);
    }
    
    mas não o seguinte:
    int f2[10]() {
      int x[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
      return x;
    }
    void f1() {
      int x[10] = f2();
    }
    
    já que, assim que sairmos da função f2, a tabela dela será invalidada. C não vai apagar a tabela, então você pode, teoricamente, usar aqueles valores ainda, só que esses valores serão sobrescritos pela próxima função que você executar, que vai criar sua tabela no lugar onde estava aquela última tabela.
  • Vetores corrompem memória facilmente

    Por exemplo, em vários compiladores, o seguinte código

     int a = 1;
     int b[5];
     int c = 2;
     int i;         
     for (i = 0; i <= 5; ++i) {
       b[i] = -1; 
       printf("%d %d %d\n", a, c, i);
     }
    
    tem um laço infinito, já que o compilador pode colocar a variável i logo depois da variável b, e aí acessar
    b[2]
    
    corrompe o valor de i. No meu computador, esse programa imprime
    1 2 0
    1 2 1
    1 2 2
    1 2 3
    1 2 4
    1 2 -1
    
    infinitas vezes até eu interrompê-lo.
  • Qual o jeito correto de acessar vetores

    Digamos que você declarou um vetor com 10 elementos. O melhor jeito de acessar todos os elementos desse vetor é usando um for,

    int vetor[10], i;
    for (i = 0; i < 10; ++i)
    
    que testa como < 10, e não <= 10.

Como usar vetores em C

Por agora, o melhor jeito de pensar em vetores em C é pensá-los como listas de valores de tamanho fixo. Depois relaxaremos essas suposições e aprenderemos a como fazer vetores de tamanho variável, que podem ser retornados de funções, como copiar vetores, etc. O programa a seguir é um exemplo, e calcula o a e o b da regressão linear a partir de 10 pontos x,y passados como parâmetros:

void lstsq(double x[10], double y[10]) {
  double a, b, sxy = 0, sx = 0;
  double sy = 0, sx2 = 0, mx = 0, my = 0;
  int i;
  for (i = 0; i < 10; ++i) {
    sx += x[i];
    sy += y[i];
    sx2 += x[i]*x[i];
    sxy += x[i]*y[i];
  }
  mx = sx/10;
  my = sy/10;
  b = (sxy - (sx*sy/10))/(sx2-(sx*sx)/10);
  a = my-b*mx;
  printf("%lf %lf\n", a, b);
}

Um jeito de usar vetores para retornar vários valores de uma função

Como vetores podem ser modificados em C, podemos fazer o seguinte:

int eq2grau(double a, double b, double c, double res[2]) {
  double delta = b*b-4*a*c;
  if (a == 0) {
    return -1;
  }
  if (delta < 0) {
    return -2;
  }
  res[0] = (-b+sqrt(delta))/(2*a);
  res[1] = (-b-sqrt(delta))/(2*a);
  return 0;
}

E a função que chamar pode passar esse vetor de resultados e depois usar, checando se o valor retornado for zero (caso contrário ocorreu algum erro).

Footnotes:

1 FOOTNOTE DEFINITION NOT FOUND: 9

2 FOOTNOTE DEFINITION NOT FOUND: 5

Author: Alexandre Tachard Passos <alexandre.tp@gmail.com>

Date: 2010-08-21 13:08:17 BRT

HTML generated by org-mode 6.21b in emacs 23