"A Computação se apoia sobre três pernas:
a correção, a eficiência e a elegância."
—prof. Imre Simon

Remoção e inserção em vetor

Imagine uma "fila" [não se trata de uma fila no sentido técnico] de candidatos a transplante de algum órgão. Quando surge um doador, algum candidato na parte inicial da "fila" (não necessariamente o primeiro, porque há restrições de compatibilidade) é atendido. Às vezes um candidato sai da "fila" porque morre antes de ser atendido. Novos candidatos podem ser acrescentados à "fila" (não necessariamente ao final da "fila", se o candidato tiver um bom "padrinho").  Nosso problema: manter a "fila" atualizada.   Temos aí um exemplo de estrutura dinâmica: uma estrutura que aumenta e diminui, de maneira imprevisível, ao longo do tempo.

O problema pode ser formulado abstratamente da seguinte maneira. Suponha que um vetor (= array)  v  foi declarado como

int v[MAX];

sendo MAX uma constante definida por um #define.  Digamos que v abriga uma seqüência

v[0] , . . . , v[n-1] .

É óbvio que devemos ter  0 ≤ n ≤ MAX. Se n é igual a 0 então a seqüência está vazia. Se n é igual a MAX, a seqüência está cheia.

Suponha que a seqüência v[0], . . . ,v[n-1] sofre inserção de novos elementos e remoção de elementos antigos. Como administrar essas operações?

Remoção

Digamos que quero remover o elemento de índice k.  É claro que isso só faz sentido se 0 ≤ k < n;  em particular, não faz sentido se a seqüência estiver vazia.

// Esta função recebe 0 <= k < n e remove 
// o elemento v[k] do vetor v[0..n-1].
// A função devolve o novo valor de n.

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

Veja que maravilha: tudo funciona bem até mesmo quando k é igual a n-1 e quando k é igual a 0. Por outro lado, veja que desagradável: é preciso deslocar (= copiar para outro lugar) muitos elementos da seqüência. Se k for muito menor que n, a função pode levar muuuuuuuito tempo para completar o serviço. [Veremos em outra página uma estrutura de dados que não tem esse defeito.]

Para remover o elemento de índice 51 (estou supondo que 51 < n) basta dizer

   n = remover (51, n, v);

É um bom exercício escrever uma versão recursiva de remover. O tamanho do problema é medido pela diferença n-k; o problema é pequeno se n-k vale 1; portanto, a base da recursão é o caso em que k vale n-1.

// A função remover2 recebe 0 <= k < n e
// remove o elemento v[k] do vetor v.
// A função devolve o novo valor de n.

int remover2 (int k, int n, int v[]) {
   if (k == n-1) return n - 1;
   else {
      v[k] = v[k+1];
      return remover2 (k+1, n, v); 
   }
}

(Que acontece se trocarmos "if (k == n-1)" por "if (k < n)"?)

Exercícios

Inserção

Suponha que quero inserir um novo elemento x entre v[k-1] e v[k]. É óbvio que isso faz sentido quando 1 ≤ k ≤ n-1. Também faz sentido quando k é igual a 0 (insere no início) e quando k é igual a n (insere no fim). Em suma, faz sentido quando e somente quando 0 ≤ k ≤ n.

É claro que você só deve inserir se tiver certeza de que a estrutura não está cheia, caso contrário a fila transborda (= overflows). Portanto, verifique a desigualdade n+1 ≤ MAX antes de chamar a função.

// Esta função insere x entre v[k-1] e v[k]
// no vetor v[0..n-1]. Ela supõe apenas que
// 0 <= k <= n.  A função devolve o novo 
// valor de n.

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

Veja como inserir funciona bem até mesmo quando quero inserir no início e até mesmo quando quero inserir no fim! Por outro lado veja que desagradável: é preciso deslocar muitos elementos da seqüência. Dependendo do valor de k, a função pode levar muuuuuuito tempo para completar o serviço.

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

   n = inserir (51, 999, n, v);

É um bom exercício escrever uma versão recursiva de inserir:

// Recebe 0 <= k <= n e insere x entre v[k-1] e v[k] 
// no vetor v[0..n-1].  A função devolve o novo valor
// de n.

int inserir2 (int k, int x, int n, int v[]) 
{
   if (k == n) {
      v[n] = x;
      return n + 1;
   }
   else {
      int y;
      y = v[k]; v[k] = x;
      return inserir2 (k+1, y, n, v);
   }
}

Exercícios

Busca e remoção

Eis uma generalização do problema da remoção. Suponha que queremos remover todos os elemento nulos da seqüência v[0], . . . ,v[n-1]. Exemplo: Se n vale 7 e

v  vale  333,222,0,0,444,0,333

então a função deve fazer n = 4 e transformar v em 333,222,444,333.

É claro que o problema faz sentido para qualquer n ≥ 0. Qualquer função que resolva nosso problema deve dizer qual o novo valor de n depois da remoção dos zeros:

// A função tirazeros elimina todos os elementos nulos 
// de v[0..n-1]. Ela supõe 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, j;
   i = 0;
   for (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++;".)   No início de cada iteração temos a 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[1..j-1] original

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

Eis uma versão pior, torta, que depende da restrição artificial n ≤ 1000, desperdiça espaço e desperdiça tempo.

// Recebe n <= 1000 e elimina os zeros de v[0..n-1].
   int vv[1000], i = 0, j;
   for (j = 0; j < n; ++j)  vv[j] = v[j]; /* ineficiente */
   for (j = 0; j < n; ++j) 
      if (vv[j] != 0) v[i++] = vv[j];
   return i;

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

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

Eis uma versão deselegante e ineficiente (a inicialização desnecessária de j é a menor das bobagens):

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

Esta versão é ineficiente porque a instrução v[j] = v[j+1] é repetida um número excessivo de vezes pois não copia v[j+1] para o seu lugar definitivo. Para melhor sentir a ineficiência, 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!

Eis uma versão ainda mais deselegante e ineficiente. O "if (i < n" supérfluo é a menor das bobagens; a alteração do valor de i dentro do for controlado por i é uma péssima maneira de conseguir o efeito desejado.

   int i, j;
   for (i = 0; i < n; ++i) 
      if (i < n && 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.

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

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

// A função tira0 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 tira0 (int n, int v[])
{
   if (n == 0) return 0;
   m = tira0 (n - 1, v);
   if (v[n-1] == 0) return m;
   v[m] = v[n-1];
   return m + 1;
}

Eis uma versão recursiva que é 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 tira0ineficiente (int k, int n, int v[])
{
   int i;
   if (k == n) return n;
   if (v[k] != 0) 
      return tira0ineficiente (k+1, n, v);
   for (i = k; i < n-1; ++i) v[i] = v[i+1];
   return tira0ineficiente (k, n-1, v);
}

Às vezes a versão recursiva de uma função exige parâmetros adicionais, como aconteceu acima 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 mal-concebida.)

Exercícios