". . . there is a huge difference between programs that merely work
and programs that are well-engineered,
just as there is a huge difference
between a log thrown over a river and a well-engineered bridge."

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

"Any fool can write code that a computer can understand.
Good programmers write code that humans can understand."
— Martin Fowler, Refactoring: Improving the Design of Existing Code

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

Vetores

Um vetor (= array) é uma estrutura de dados que armazena uma sequência de objetos, todos do mesmo tipo, em posições consecutivas da memória.  Esta página estuda os problemas de procurar um objeto em um vetor, inserir um novo objeto no vetor e remover um elemento do vetor.  Estes problemas servem de pretexto para exibir exemplos de algoritmos recursivos e para ilustrar os conceitos de correção, eficiência e elegância de algoritmos. Os três problemas — busca, inserção e remoção — reaparecerão, em outros contextos, nos demais capítulos.

Imagine que temos uma longa lista de números (de telefones, por exemplo) armazenada num vetor v. O espaço reservado para o vetor pode ter sido criado pela declaração

   int v[N];

sendo N uma constante (possivelmente 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.

Busca

Dado um inteiro x e um vetor v[0..n-1] de inteiros, o problema da busca consiste em encontrar x em v, ou seja,

encontrar um índice k tal que v[k] == x.

O problema faz sentido com qualquer n ≥ 0. Se n é 0, o vetor é vazio e portanto essa instância do problema não tem solução.

		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 se x não está no vetor? Adotaremos a convenção de devolver -1 nesse caso (observe que -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 como a função é eficiente e elegante. Ela funciona corretamente mesmo quando o vetor está vazio, ou seja, quando n vale 0.  O código poderia ter sido escrito com for no lugar de while:

        int k;
        for (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 mas deselegante, usa uma variável booleana "de passagem":

   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 mas são incorretas. No exemplo abaixo, 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;

A ordem correta das comparações é  (k >= 0 && v[k] != x).

Solução com sentinela.  Poderíamos 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, faria mais sentido 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 o grande número de comparações de k com n:

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

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

Exercícios

Busca recursiva

Eis uma solução recursiva do problema de 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 a coisa 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].

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

Remoção

Digamos que quero remover o elemento de índice k do vetor v[0..n-1]. Mais precisamente, quero remover o elemento que está na posição de índice k e fazer com que o vetor resultante tenha índices 0..n-2.  (Por exemplo, o resultado da remoção do elemento que está na posição 3 do vetor 000,111,222,333,444,555 é o vetor 000,111,222,444,555.)  É claro que o problema só faz sentido se 0 ≤ k < n;  em particular, não faz sentido se o vetor estiver vazio.  A seguinte função faz a remoção e devolve o número de elementos do vetor resultante:

// 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 remove( 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 exemplo, para remover o elemento de índice 51 (estou supondo que 51 < n) basta dizer

   n = remove( 51, n, v);

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

// A 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 remove_r( int k, int n, int v[]) 
{
   if (k == n-1) return n - 1;
   else {
      v[k] = v[k+1];
      return remove_r( 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 estrutura transborda (= overflows). Portanto, verifique a desigualdade 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]. Ela supõe apenas que
// 0 <= k <= n.  A função devolve o novo 
// valor de n.

int insere( 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 insere funciona bem até mesmo quando quero inserir no início e até mesmo quando quero inserir no fim!  Por exemplo, para inserir um novo elemento com valor 999 entre as posições 50 e 51 (estou supondo que 51 ≤ n) basta dizer

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

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

// 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 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);
   }
   return n+1;
}

Exercícios

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]. 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 += 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

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.

Maus exemplos.  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 obter o efeito desejado.

   int i, j;
   for (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.

   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;

Versão recursiva.  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[])
{
   int m;
   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 malconcebida.)

Exercícios