Projeto de Algoritmos  |  Linguagem C  |  Índice  |  English

Vetores

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 determinado 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 queremos armazenar n números inteiros num vetor v.  O espaço ocupado pelo vetor na memória pode ter sido criado pela declaração

int v[N];

sendo N uma constante (possivelmente uma macro definida por um #define).  Se os números forem armazenados nas posições 0, 1, … , n-1, 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

Busca

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

Uma solução desse problema é um algoritmo que recebe os valores de x, n, v e devolve um índice k.  Somos imediatamente confrontados por uma decisão de projeto: que coisa nosso algoritmo deve devolver se não existir k tal que v[k] == x?  Em outras palavras, o que nosso algoritmo deve fazer se a instância do problema não tiver solução?

Nossa decisão de projeto: devolva -1 se a instância não tem solução. Esta é uma boa convenção 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;
}

É fácil verificar que a função está correta.  A função também é eficiente e elegante: ela não perde tempo à toa, não tem instruções nem variáveis desnecessárias, e não trata de casos especiais (como, por exemplo, o caso n == 0) em separado.

Um código igualmente correto, eficiente e elegante pode ser escrito com um 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 funçõ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 muito 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 funçã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 funções parecem razoáveis à primeira vista, mas estão simplesmente 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 correta:  k >= 0 && v[k] != x.)

Funçã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 funçã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 o vetor não está cheio e portanto há espaço para a sentinela.)

Exercícios 2

Busca recursiva

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

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 tanto mais tempo quanto menor for k.)

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

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

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

Inserção

Dado um vetor de números v[0..n-1], queremos inserir um novo número x entre os elementos de índices k-1 e k.  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 x 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 as 
// posições k-1 e k do vetor v[0..n-1] 
// supondo 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 e quando quero inserir no fim!

Para inserir um novo elemento com valor 999 entre as posições 50 e 51 (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 as 
// posições k-1 e k do vetor v[0..n-1] 
// supondo 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

Busca e remoção

Considere agora uma combinação dos problemas de busca e remoção. Suponha que queremos remover todos os elementos nulos do vetor  v[0 .. n-1].  É claro que o problema faz sentido com qualquer n ≥ 0 (o caso em que n == 0 é trivial).  Por exemplo, se n vale 7 e v[0..6] é

11 22 0 0 33 0 44

então o vetor resultante deve ser  11 22 33 44 . 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 solução elegante e eficiente do problema:

// 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.

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;  // ruim...
   }
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. Ao contrário da versão anterior, ela 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. É essencial 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

Exercícios 7: desafios