Vetores

. . . there is a huge difference
between working programs and good programs.
A good program not only works,
but is easy to read and maintain.


— P. A. Darnell, Ph. E. Margolis,
Software Engineering in C

Programs must be written for people to read,
and incidentally for machines to execute.

— H. Abelson, G. Sussman,
The Structure and Interpretation of Computer Programs

A Computação anda sobre três pernas:
a correção, a eficiência e a elegância.

— prof. Imre Simon

Um vetor, ou arranjo (= array), é uma estrutura de dados que armazena uma sequência de objetos, todos do mesmo tipo, em posições consecutivas da memória RAM (= random access memory) do computador.  Essa estrutura permite acesso aleatório: qualquer elemento do vetor pode ser alcançado diretamente, sem passar pelos elementos anteriores (o décimo elemento, por exemplo, pode ser alcançado sem que seja necessário passar antes pelo primeiro, segundo, etc., nono elementos).

Como procurar um objeto em um vetor?  Como inserir um novo objeto no vetor?  Como remover um elemento do vetor?  Esses problemas serão usados como pretexto para exibir exemplos de algoritmos e para ilustrar os conceitos de correção, eficiência e elegância de código. Os três problemas — busca, inserção e remoção — reaparecerão, em outros contextos, em muitas páginas deste sítio.

Imagine que temos uma lista de n números armazenada num vetor v. O espaço ocupado pelo vetor pode ter sido criado pela declaração

int v[N];

sendo N uma constante (possivelmente uma macro definida por um #define).  Se a lista de números está armazenada nas posições 0, 1, … , n-1 do vetor, diremos que

v[0..n-1]  é um vetor de inteiros.

É claro que devemos ter 0 ≤ n ≤ N. Se n == 0, o vetor v[0..n-1] está vazio. Se n == N, o vetor está cheio.

Exercícios 1

  1. [Sedgewick 3.11]  Diga (sem usar o computador) qual o conteúdo do vetor  v  depois das seguintes instruções.
    int v[99];
    for (i = 0; i < 99; ++i) v[i] = 98 - i;
    for (i = 0; i < 99; ++i) v[i] = v[v[i]];
    
  2. Inversão.  Suponha que um vetor v[1..n] contém uma permutação de 1..n. Escreva uma função que inverta essa permutação:  se v[i] == j no vetor original, queremos ter v[j] == i no fim da execução da função.

Dado um inteiro x e um vetor v[0..n-1] de inteiros, o problema da busca (= search problem) consiste em encontrar x em v, ou seja, encontrar um índice k tal que v[k] == x.

0   0               n-1    
443 222 555 111 333 444 555 666 888 777 888 999
x   v

É preciso começar com uma decisão de projeto: que fazer com as instâncias do problema que não têm solução?  Ou seja, que fazer se x não está no vetor?  Adotaremos a convenção de devolver -1 nesses casos; essa convenção é apropriada pois -1 não pertence ao conjunto 0..n-1 de índices válidos.  Para implementar essa convenção, convém varrer o vetor do fim para o começo:

// A função recebe x, n >= 0 e v e devolve
// um índice k em 0..n-1 tal que x == v[k]. 
// Se tal k não existe, devolve -1.

int
busca (int x, int n, int v[])
{
   int k;
   k = n-1;
   while (k >= 0 && v[k] != x) 
      k -= 1;
   return k;
}

Observe que a função está correta mesmo quando n == 0.  Observe como a função é eficiente e elegante: não perde tempo à toa, não tem instruções nem variáveis desnecessárias, e não trata de casos especiais em separado.

Um código igualmente correto, eficiente e elegante pode ser escrito com for no lugar do while:

   for (int k = n-1; k >= 0; --k) 
      if (v[k] == x) return k;
   return -1; 

Maus exemplos.  Para fazer contraste com a função busca acima, eis algumas soluções deselegantes, ineficientes ou incorretas. A primeira, muito popular, usa uma variável booleana de passagem, ou de sinalização:

   int achou = 0, k = n-1;
   while (k >= 0 && achou == 0) { // deselegante
      if (v[k] == x) achou = 1;   // deselegante
      else k -= 1;
   }
   return k;

A segunda, também bastante popular, trata do vetor vazio em separado, sem necessidade:

   if (n == 0) return -1; // deselegante
   else {
      int k = n-1;
      while (k >= 0 && v[k] != x) k -= 1;
      return k; 
   } 

A próxima solução é ineficiente (pois continua calculando depois de ter encontrado uma solução) e deselegante (pois inicializa uma variável desnecessariamente):

   int k = 0;                 // deselegante
   int sol = -1;
   for (k = n-1; k >= 0; --k) // ineficiente
      if (v[k] == x) sol = k; // deselegante
   return sol; 

Algumas soluções parecem razoáveis à primeira vista, mas estão erradas. No seguinte exemplo, a última iteração comete o erro de examinar v[-1]:

   int k = n-1;
   while (v[k] != x && k >= 0) // errado!
      k -= 1;
   return k;

(As comparações deveriam ter sido feitas na ordem corretak >= 0 && v[k] != x.)

Solução com sentinela.  Podemos tomar uma decisão de projeto diferente e devolver n, em lugar de -1, se x não estiver em v[0..n-1].  Nesse caso, é melhor percorrer o vetor do começo para o fim:

   int k = 0;
   while (k < n && v[k] != x)
      k += 1;
   return k; 

A solução ficaria ainda melhor se usássemos uma sentinela para evitar as repetidas comparações de k com n:

   v[n] = x;  // sentinela
   int k = 0;
   while (v[k] != x)
      k += 1;
   return k;

(Estamos supondo aqui que n < N e portanto há espaço para a sentinela.)

Exercícios 2

  1. Qual o invariante do processo iterativo na função busca?  [Solução.]
  2. Critique a seguinte versão da função busca:
    int k = 0;
    while (k < n && v[k] != x) k += 1;
    if (v[k] == x) return k;
    else return -1; 
    
  3. Critique a seguinte versão da função busca:
    int sol;
    for (k = 0; k < n; ++k) {
       if (v[k] == x) sol = k;
       else sol = -1; }
    return sol;
    
  4. Versão booleana.  Escreva uma função que receba x, v e n e devolva 1 se x está em v[0..n-1] e 0 em caso contrário.
  5. Máximo.  A função abaixo promete encontrar o valor de um elemento máximo de v[0..n-1]. A função cumpre a promessa?
    int maxi (int n, int v[]) {       
       int m = v[0];
       for (int j = 1; j < n; ++j)
          if (v[j-1] < v[j]) m = v[j];
       return m;
    }
    
  6. Máximo.  A seguinte função promete calcular o valor de um elemento máximo de um vetor v[0..n-1]. O problema faz sentido quando n vale 0? A função está correta?
    int maximo (int n, int v[]) { 
       int x = v[0];
       for (int j = 1; j < n; j += 1)
          if (x < v[j]) x = v[j];
       return x;
    }
    

    Faz sentido trocar  x = v[0]  por  x = 0, como fazem alguns programadores descuidados?  Faz sentido trocar  x = v[0]  por  x = INT_MIN?  Faz sentido trocar  x < v[j]  por  x <= v[j]?  [Veja uma solução parcial.]

  7. Segmento máximo de zeros.  Escreva uma função que calcule o comprimento do mais longo segmento de zeros em um vetor de números inteiros. Procure examinar o menor número possível de elementos do vetor.

Eis uma solução recursiva (veja a página Recursão e algoritmos recursivos) do problema da busca:

// Recebe x, n >= 0 e v e devolve k
// tal que 0 <= k < n e v[k] == x. 
// Se tal k não existe, devolve -1

int busca_r (int x, int n, int v[]) {
   if (n == 0) return -1;
   if (x == v[n-1]) return n-1;
   return busca_r (x, n-1, v);
}

Como isso funciona?  O número de elementos relevantes de v é n. Se n é 0 então v[0..n-1] é vazio e portanto x não está em v[0..n-1]. Agora suponha que n > 0; nesse caso, x está em v[0..n-1] se e somente se

x é igual a v[n-1]  ou  x está em v[0..n-2].

Resumindo: o código reduz a instância que busca x em v[0..n-1] à instância que busca x em v[0..n-2].

Mau exemplo.  A seguinte alternativa para a função busca_r é muito deselegante. Ela coloca o caso n == 1 na base da recursão e com isso complica as coisas sem necessidade. (Além disso, só funciona se n ≥ 1.)

int feio (int x, int n, int v[]) {
   if (n == 1) {               // deselegante
      if (x == v[0]) return 0; // deselegante
      else return -1;
   }
   if (x == v[n-1]) return n-1;
   return feio (x, n-1, v);
}

Exercícios 3

  1. Suponha que o vetor v[0..n-1] tem dois ou mais elementos iguais a x.  Qual deles será apontado pela função busca_r?
  2. Quantas comparações entre x e elementos do vetor v a função busca_r faz?
  3. Critique a seguinte variante da função busca_r:
    int busc_r (int x, int n, int v[]) {
       if (n == 0) return -1;
       int k = busc_r (x, n-1, v);
       if (k != -1) return k;
       if (x == v[n-1]) return n-1;
       return -1; }
    
  4. Critique a seguinte variante da função busca_r:
    int busc (int x, int n, int v[]) {
       if (v[n-1] == x) return n-1;
       else return busc (x, n-1, v); }
    
  5. Critique a seguinte variante da função busca_r:
    int busc (int x, int n, int v[]) {
       if (v[n-1] == x || n == 0) return n-1;
       else return busc (x, n-1, v); }
    
  6. Escreva uma função recursiva que receba um inteiro x, um vetor v e índices a e z e devolva um índice k no conjunto a..z-1 tal que  v[k] == x;   se tal k não existe, devolva a-1.

Remoção

Digamos que quero remover o elemento de índice k do vetor v[0..n-1]. Para isso, basta deslocar o segmento v[k+1..n-1] do vetor para as posições k..n-2.  Por exemplo, o resultado da remoção do elemento de índice 3 do vetor  0 11 22 33 44 55  é o vetor  0 11 22 44 55.  É claro que o problema faz sentido se e somente se 0 ≤ k < n.

A seguinte função resolve o problema e devolve o valor do elemento removido:

// Esta função recebe um vetor v[0..n-1]
// e um índice k tal que 0 <= k < n.
// Ela devolve v[k] e remove esse
// elemento do vetor.

int
remove (int k, int n, int v[])
{
   int x = v[k];
   for (int j = k+1; j < n; ++j)  
      v[j-1] = v[j];
   return x;
}

Note como tudo funciona bem até mesmo quando k vale n-1 e quando k vale 0.  (Mas é claro que a remoção haverá de consumir um bom tempo se k por muito menor que n.)

Como usar a função?  Para remover o elemento de índice 51 de v[0..n-1], por exemplo, basta dizer

   x = remove (51, n, v);
   n -= 1; // atualiza o valor de n

(Estou supondo que 51 < n, é claro.)

Versão recursiva.  É um bom exercício escrever uma versão recursiva de remove. O tamanho de uma instância do problema é medido pela diferença n-k e a instância é considerada pequena se n-k vale 1. Portanto, a base da recursão é o caso em que k vale n-1.

// Esta função recebe um vetor v[0..n-1]
// e um índice k tal que 0 <= k < n.
// Ela devolve v[k] e remove esse
// elemento do vetor.

int remove_r (int k, int n, int v[]) {
   int x = v[k];
   if (k < n-1) {
      int y = remove_r (k+1, n, v); 
      v[k] = y;
   }
   return x;
}

[Carlos A. Estombelo-Montesco mostrou que uma versão anterior dessa função estava errada.]

Exercícios 4

  1. Que acontece se trocarmos v[j-1] = v[j] por v[j] = v[j+1] no código da função remove?
  2. Critique as seguintes versões de remove:
    for (j = n-1; j > k; --j)  
       v[j-1] = v[j];
    
    for (j = k+1; j < n; ++j)  
       v[j-1] = v[j];
    v[n-1] = 0;
    
    if (k < n - 1) 
       for (j = k+1; j < n; ++j)  
          v[j-1] = v[j];
    
  3. Escreva uma versão da função remove que cuide de decrementar o valor de n depois da remoção. (Sugestão: Passe o endereço da variável n à função remove.)
  4. Discuta a seguinte versão de remove_r:
    int remove_r2 (int k, int n, int v[]) {
       int x = v[k];
       if (k < n-1) {
          remove_r2 (k, n-1, v);
          v[n-2] = v[n-1]; }
       return x; }
    
  5. Rediscuta o problema da remoção sob condições mais gerais: Suponha que a parte relevante do vetor é v[a..z-1]; para remove v[k], puxe v[k+1..z-1] para a esquerda ou empurre v[a..k-1] para a direita, dependendo de qual das alternativas for mais barata.  (E não esqueça de atualizar os valores de az.)

Inserção

Suponha que quero inserir um novo número x entre os elementos cujos índices são k-1k em um vetor v[0..n-1].  Isso faz sentido não só quando 1 ≤ k ≤ n-1 como também quando k vale 0 (insere no início) e quando k vale n (insere no fim). Em suma, faz sentido para qualquer k no conjunto 0..n.

É claro que você só deve inserir se tiver certeza de que o vetor não está cheio; caso contrário, teremos um transbordamento (= overflow). Portanto, certifique-se de que n+1 ≤ N antes de chamar a função.

// Esta função insere x entre v[k-1]
// e v[k] no vetor v[0..n-1] para
// qualquer k tal que 0 <= k <= n.

void
insere (int k, int x, int n, int v[])
{
   for (int j = n; j > k; --j)  
      v[j] = v[j-1];
   v[k] = x;
} 

Note como insere funciona bem até mesmo quando quero inserir no início do vetor ou quando quero inserir no fim!

Para inserir um novo elemento com valor 999 entre as posições 5051 (estou supondo que 51 ≤ n) basta dizer

   insere (51, 999, n, v);
   n++;  // atualiza n

Versão recursiva.  É um bom exercício escrever uma versão recursiva de insere:

// Esta função insere x entre v[k-1]
// e v[k] no vetor v[0..n-1] para
// qualquer k tal que 0 <= k <= n.

void insere_r (int k, int x, int n, int v[]) {
   if (k == n)  v[n] = x;
   else {
      v[n] = v[n-1];
      insere_r (k, x, n - 1, v);
   }
}

Exercícios 5

  1. Escreva uma função que insira x entre v[k] e v[k+1]. Escreva também a documentação correta da função.
  2. Escreva uma versão da função insere que cuide de incrementar o valor de n depois da inserção. (Sugestão: Passe o endereço da variável n à função insere.)
  3. Discuta a seguinte versão de insere_r:
    int insere_r2 (int k, int x, int n, int v[]) {
       if (k == n) {
          v[n] = x;
          return n + 1; }
       else {
          int y = v[k];
          v[k] = x;
          return insere_r2 (k+1, y, n, v); } }
    
  4. Rediscuta o problema da inserção sob condições mais gerais: Suponha que a parte relevante do vetor v é v[a..z-1]; para inserir x entre v[k-1] e v[k] você tem duas opções: empurrar v[k..z-1] para a direita ou puxar v[a..k-1] para a esquerda; escolha a opção mais eficiente.  (E não esqueça de atualizar os valores de az.)

Busca e remoção

Considere agora uma combinação dos problemas de busca e remoção. Suponha que queremos remover todos os elementos nulos da sequência v[0], … , v[n-1].  É claro que o problema faz sentido com qualquer n0 (o caso em que n vale 0 é trivial).  Exemplo: Se

v   vale   33 22 0 0 44 0 33

a função deve transformar v em  33 22 44 33. Embora o enunciado do problema não peça isso explicitamente, vamos exigir que a função devolva o número de elementos do vetor depois da remoção dos zeros. 

Eis uma função elegante e eficiente para o poblema:

// Esta função elimina todos os
// elementos nulos de v[0..n-1].
// Supõe apenas que n >= 0. A função
// deixa o resultado em v[0..i-1]
// e devolve i.
    
int
tirazeros (int n, int v[])
{
   int i = 0;
   for (int j = 0; j < n; ++j)  
      if (v[j] != 0) 
         v[i++] = v[j];
   return i;
}

(A instrução  v[i++] = v[j]  tem o mesmo efeito que  v[i] = v[j]; i += 1.)   No início de cada iteração temos o seguinte invariante:   v[0..i-1]  é o vetor que resulta da remoção dos zeros de  v[0..j-1];  é claro que i ≤ j.

0         i     j       n
999 999 999 999 999 000 999 000 999 000 999 000 999
versão sem zeros do
v[0..j-1] original
lixo

Note como a coisa funciona bem até mesmo quando n vale 0. Também funciona bem quando o vetor dado não tem zero algum. Também funciona bem quando o vetor dado só tem zeros.

Para remover os elementos nulos de um vetor v[0..n-1], basta dizer

n = tirazeros (n, v);

Maus exemplos.  Eis uma versão pior, que desperdiça espaço (pois usa um vetor auxiliar de n elementos):

int vv[1000], i = 0;
for (int j = 0; j < n; ++j) 
   if (v[j] != 0) vv[i++] = v[j];
for (int j = 0; j < i; ++j)  
   v[j] = vv[j];
return i;

Eis uma versão que está simplesmente errada (por que?):

for (int i = 0; i < n; ++i) 
   if (v[i] == 0) {
      for (int j = i; j+1 < n; ++j)  
         v[j] = v[j+1];
      n -= 1;
   }
return n; 

Segue mais uma versão deselegante e ineficiente. Esta versão é ineficiente porque a instrução v[j] = v[j+1] é repetida um número excessivo de vezes, uma vez que não copia v[j+1] para o seu lugar definitivo:

int i = 0;
while (i < n) {
   if (v[i] != 0)  i += 1;
   else {
      for (int j = i; j+1 < n; ++j)  
         v[j] = v[j+1];
      --n;
   } 
}
return n; 

Para melhor sentir a ineficiência desta versão, considere o seguinte exemplo. Suponha que n é 100 e que todos os elementos de v exceto v[99] são nulos. A versão acima copia elementos de v de um lugar para outro 4950 vezes enquanto a primeira versão de tirazeros faz isso uma só vez!

Segue uma versão ainda mais deselegante e ineficiente.  A alteração do valor de i dentro do for controlado por i é uma péssima maneira de obter o efeito desejado.  Além disso, a variável j é inicializada desnecessariamente e a condição i < n-1 no if é supérflua.

int j = 0;
for (int i = 0; i < n; ++i) 
   if (i < n-1 && v[i] == 0) {
      for (j = i; j+1 < n; ++j)  
         v[j] = v[j+1];
      --n;
      --i; 
   }
return n; 

A versão seguinte não é mais eficiente que a anterior, mas pelo menos não é tão torta:

for (int i = n-1; i >= 0; --i)
   if (v[i] == 0) {
      for (int j = i; j < n-1; ++j) 
         v[j] = v[j+1];
      --n;
   }
return n;

Versão recursiva.  Para terminar, eis uma versão recursiva de tirazeros. Note como a instrução v[m] = v[n-1] coloca v[n-1] no seu lugar definitivo.

// A função tirazeros_r elimina todos
// os elementos nulos de v[0..n-1].
// A função deixa o resultado em 
// v[0..i-1] e devolve i.
    
int tirazeros_r (int n, int v[]) {
   if (n == 0) return 0;
   int m = tirazeros_r (n - 1, v);
   if (v[n-1] == 0) return m;
   v[m] = v[n-1];
   return m + 1;
}

Segue uma versão torta e ineficiente. Ela é ineficiente porque, ao contrário da versão anterior, não coloca cada elemento do vetor no seu lugar definitivo de uma só vez.  (Note que há duas chamadas recursivas da função e que as duas chamadas têm forma diferente. Mau sinal!)

// Recebe 0 <= k <= n e elimina os zeros
// de v[k..n-1]. O vetor sem os zeros terá
// a forma v[k..m-1]. A função devolve o
// valor de m.

int ineficiente (int k, int n, int v[]) {
   if (k == n) return n;
   if (v[k] != 0) 
      return ineficiente (k+1, n, v);
   for (int i = k; i < n-1; ++i) v[i] = v[i+1];
   return ineficiente (k, n-1, v);
}

Às vezes a versão recursiva de uma função exige parâmetros adicionais, como aconteceu aqui com o parâmetro k. É fundamental explicar ao usuário, como fizemos acima, qual o papel do parâmetro adicional.  (Mas é claro que nem a melhor das explicações pode tornar boa uma função malconcebida.)

Exercícios 6

  1. Critique a seguinte função. Ela promete eliminar os zeros de v[0..n-1], deixar o resultado em v[0..m-1] e devolver m.
    int tira0 (int n, int v[]) {
       int z = 0;
       for (int i = 0; i < n; ++i) {
          if (v[i] == 0) z += 1;
          v[i-z] = v[i]; }
       return n - z; }
    
  2. Critique a seguinte função. Ela promete eliminar os zeros de v[0..n-1], deixar o resultado em v[0..m-1] e devolver m.
    int tira0 (int n, int v[]) {
       int z = 0;
       for (int i = 0; i < n - z; ++i) {
          if (v[i] == 0) {
             z += 1;
             for (int k = i; k < n - z; ++k) 
                v[k] = v[k+1];
             --i; } }
       return n - z; }
    
  3. Escreva uma função que remova de v[a..z-1] todos os elementos que têm um dado valor y.
  4. ★ Escreva uma função recursiva que apague todos os # de um vetor c[0..n-1] de caracteres ASCII.   Exemplo: Se n vale 7 e o vetor contém   a b c # # d #   então o resultado deve ser   a b c d .
  5. ★ Escreva uma função que receba duas strings ASCII, strdel, e apague de str todos os bytes que estão em del. Por exemplo, se str é  "aaa*$-bbb#ccc*"  e del é  "$#*",  o estado final de str deve se  "aaa-bbbccc".  Escreva uma função eficiente que resolva o problema. Sua função não deve alocar nenhum vetor novo.
  6. Pequena Aplicação.  Escreva um programa para administrar uma coleção de números digitados pelo usuário. A coleção pode conter mais de uma cópia de um mesmo número. O usuário pode inserir novos números na coleção e remover números que já estão lá. A coleção é armazenada em ordem crescente.  Se o usuário digitar
    i 222
    

    (seguido de ) o número 222 é inserido na coleção.  Se digitar

    r 333
    

    o número 333 é removido da coleção (se esse número não estiver na coleção, o comando é ignorado).  Depois de cada inserção ou remoção, o programa deve exibir a coleção. Se o usuário digitar qualquer outro caractere que não 'i' ou 'r', a execução do programa termina.  [Solução.]

Exercícios 7: desafios

  1. Problema de Josephus.  Imagine uma roda de n pessoas. Suponha que as pessoas estão numeradas de 1n no sentido horário. Começando com a pessoa de número 1, percorra a roda no sentido horário e elimine cada m-ésima pessoa enquanto a roda tiver duas ou mais pessoas. Qual o número do sobrevivente? 
  2. Segmento constante.  Digamos que um segmento v[i..j] de um vetor v[0..n-1] é constante se todos os seus elementos têm o mesmo valor.  Escreva uma função simples e eficiente que calcule o comprimento de um segmento constante de comprimento máximo de um vetor v[0..n-1].
  3. Subsequência.  Um subvetor de um vetor v é o que sobra depois que alguns dos elementos de v são apagados.  (Por exemplo,  12 13 10 3  é um subvetor de  11 12 13 11 10 9 7 3 3  mas não de  11 12 10 11 13 9 7 3 3.)  Escreva uma função eficiente que decida se x[0..m-1] é subvetor de v[0..n-1].
  4. Subsequência crescente máxima.  Um subvetor de um vetor v é o que sobra depois que alguns dos elementos de v são apagados.  Escreva uma função eficiente que determine um subvetor crescente de comprimento máximo de um vetor v[0..n-1].
  5. Segmento de soma máxima.  A soma de um vetor v[i..k] é o número v[i] + v[i+1] + ... + v[k].  A altura de um vetor v[1..n] é a soma de um segmento não vazio de v[1..n] que tenha soma máxima.   Em outras palavras, a altura de v[1..n] é a maior soma da forma v[i] + v[i+1] + ... + v[k] com 1 ≤ i ≤ k ≤ n.  Escreva uma função eficiente que calcule a altura de um vetor v[1..n] de números inteiros. Use o algoritmo mais eficiente que puder.   Exemplo: Um dos segmentos do vetor  20 -30 15 -10 30 -20 -30 30  tem soma 15 - 10 + 30 = 35.  Existe algum segmento com soma maior que 35?  
  6. Soma de dois elementos distantes.  Dado um vetor v[0..n-1] de números e um inteiro d tal que 0 ≤ d ≤ n-1 encontrar o maior número da forma v[i] + v[j] com j - i ≥ d.

Perguntas e respostas