Pesquisa sequencial

(Exercício 6.5 das folhas)

Dados:

• uma variável indexada vec com size valores (e.g. inteiros);
• um valor qualquer val

Queremos:

• testar se val ocorre em vec
• resultado sim/não (1/0)

Pesquisa sequencial (2)

int ocorre(int vec[], int size, int val) {
    for(int i = 0; i < size; i++) {
       if(vec[i] == val)
           return 1; // encontrou
    }
    return 0;    // não encontrou
}

Alternativa

• Retornar o índice e não apenas sim/não
• Podemos usar um índice inválido se não ocorre
  • e.g. retornar -1 se não ocorre

Pesquisa sequencial (alternativa)

int pesquisa(int vec[], int size, int val) {
    for(int i = 0; i < size; i++) {
       if(vec[i] == val)
           return i; // encontrou
    }
    return -1;    // não encontrou
}

Eliminar repetidos

Dado: uma variável indexada vec de inteiros

Queremos:

• eliminar ocorrências repetidas em vec
• deixar ficar apenas a primeira ocorrência de cada valor

{2, 3, 4}          ->  {2, 3, 4}
{2, 3, 2, 2, 4, 2} ->  {2, 3, 4}
{4, 3, 2, 2, 4}    ->  {4, 3, 2}
{3, 3, 3}          ->  {3}

Eliminar repetidos (2)

• O tamanho da sequência final é sempre menor ou igual ao tamanho da sequência original
• Logo: podemos re-utilizar o espaço da variável indexada original

Eliminar repetidos (3)

Vamos definir uma função

   int elimrep(int vec[], int size);

cujo resultado será o número \(k\) de valores distintos na variável indexada vec.

Além disso, modificamos vec:

• o segmento inicial de \(k\) valores tem todos os valores da sequência sem repetidos;
• os restantes valores não são modificados.

Eliminar repetidos (3)

Exemplo

int a[7] = {2, 3, 3, 2, 4, 3, 5};
k = elimrep(a, 7);
// a[] :  {2, 3, 4, 5, 4, 3, 5}
// k   :  4

Eliminar repetidos (4)

Variáveis

vec

variável indexada para eliminar repetidos

size

tamanho de vec (número de valores)

i

índice do próximo valor (possívelmente repetido)

k

número de valores diferentes já encontrados

Eliminar repetidos (5)

int elimrep(int vec[], int size) {
   int i, k = 0;
   // i: índice do próximo valor 
   // k: número de valores distintos
   for(i = 0; i < size; i++) {
      int val = vec[i];
      if(!ocorre(vec, k, val)) {
           // encontramos um novo valor
           // distinto dos anteriores
         vec[k++] = val;
      }
   }
   return k;
}

Invariantes

\[ \scriptsize \overbrace{\begin{array}{|c|c|c|} \hline \texttt{v[0]} & \cdots & \texttt{v[k-1]} \\ \hline \end{array}}^{\text{sem repetidos}} \overbrace{\begin{array}{|c|c|c|c|c|} \hline \texttt{v[k]} & \cdots &\texttt{v[i]}&\cdots & \texttt{v[size-1]} \\ \hline \end{array}}^{\text{?}} \]

1. A sequência \(\texttt{vec[0]}, \ldots, \texttt{vec[k-1]}\) não tem repetidos
2. O conjunto \[ \{\texttt{vec[0]}, \ldots, \texttt{vec[i-1]}\} \] é igual a \[ \{\texttt{vec[0]}, \ldots, \texttt{vec[k-1]}\} \]