Enunciado:
Determinar e remover todos os elementos de um vetor ordenado, com valores superiores a E1 e
inferiores ou iguais a E2.
Algoritmo:
1) Pesquisar a posição do menor elemento do vetor que é superior a E1 – seja k1
2) Pesquisar a posição do maior elemento do vetor que é inferior ou igual a E2 – seja k2
3) Determinar o número de elementos que estão nas condições descritas no enunciado
4) Remover todos os elementos do vetor entre as posições k1 e k2
5) Atualizar o tamanho do vetor
Resolução
1) Pesquisar a posição do menor elemento do vetor V de tamanho N superior a Elem
k ← -1 // significa que todos os elementos do vetor V são inferiores ou iguais a Elem
i ← 0 // índice dos elementos do vetor V
Enquanto (i < N) e (k = -1) Fazer
Se (V[i] > Elem) então
k←i
// significa que o menor elemento de V superior a Elem encontra-se na posição i
senão
i←i+1
Se (k ≥ 0) então
O menor elemento de V superior a Elem encontra-se na posição k
senão
Todos os elementos de V são inferiores ou iguais a Elem
Função em C:
int PosicaoMenorElementoSuperiorElem (int Elem, int V[], int N)
{
int i = 0, k = -1;
// k = posição do menor elemento de V superior a Elem
// k= -1 significa que todos os elementos de V são inferiores ou iguais a Elem
while ( (i < N) && (k == -1) )
if (V[i] > Elem)
k = i;
else
i = i + 1;
return (k);
}
Remover todos os elementos do vetor V de tamanho N superiores a E1 e inferiores ou
iguais a E2.
Versão 1: usar a mesma função implementada para os passos 1) e 2)
int *RemoverElementosVetorEntreE1E2 (int E1, int E2, int V[], int *N)
{
int k1, k2, numR, i;
k1 = PosicaoMenorElementoSuperiorElem(E1, V, *N);
if (k1 == -1)
// todos os elementos de V são inferiores ou iguais a E1
return (V);
k2 = PosicaoMenorElementoSuperiorElem(E2, V, *N);
if (k2 == -1)
// todos os elementos de V são inferiores ou iguais a E2
k2 = N-1;
else
if (k2 == 0)
// todos os elementos são superiores a E2
return (V);
else
k2 = k2-1;
// o maior elemento de V inferior ou igual a E2 está uma posição atrás de k2
// Determinar o número de elementos entre as posições k1 e k2
numR = k2 – k1 + 1;
for (i = k1; i < N-numR; i++)
V[i] = V[i+numR];
*N = (*N) - numR;
// Diminuir em numR unidades o tamanho do vetor V
V = (int *) realloc (V, (*N)*sizeof(int));
// Realocar memória após atualização do tamanho de V
return (V);
}
2) Pesquisar a posição do maior elemento do vetor V de tamanho N inferior ou igual a Elem
k ← -1 // significa que todos os elementos do vetor V são superiores a Elem
i ← N-1 // iniciar a pesquisa pela última posição do vetor (que é o maior deles) e
// pesquisar para trás até encontrar o primeiro elemento inferior ou igual a Elem
Enquanto (i >= 0) e (k = -1) Fazer
Se (V[i] <= Elem) então
k←i
// o maior elemento de V inferior ou igual a Elem encontra-se na posição i
senão
i←i-1
Se (k ≥ 0) então
O maior elemento de V inferior ou igual a Elem encontra-se na posição k
senão
Todos os elementos de V são superiores a Elem
Função em C:
int PosicaoMaiorElementoInferiorElem (int Elem, int V[], int N)
{
int i = N-1, k = -1;
// k = posição do maior elemento de V inferior ou igual a Elem
// k= -1 significa que todos os elementos de V são superiores a Elem
while ( (i >= 0) && (k == -1) )
if (V[i] <= Elem)
k = i;
else
i = i - 1;
return (k);
}
Remover todos os elementos do vetor V de tamanho N superiores a E1 e inferiores ou
iguais a E2.
Versão 2: usar as 2 funções implementadas para os passos 1) e 2)
int *RemoverElementosVetorEntreE1E2 (int E1, int E2, int V[], int *N)
{
int k1, k2, numR, i;
k1 = PosicaoMenorElementoSuperiorElem(E1, V, *N);
if (k1 == -1)
// todos os elementos de V são inferiores ou iguais a E1
return (V);
k2 = PosicaoMaiorElementoInferiorElem(E2, V, *N);
if (k2 == -1)
// todos os elementos de V são superiores a E2
return (V);
// Determinar o número de elementos entre as posições k1 e k2
numR = k2 – k1 + 1;
for (i = k1; i < N-numR; i++)
V[i] = V[i+numR];
*N = (*N) - numR;
// Diminuir em numR unidades o tamanho do vetor V
V = (int *) realloc (V, (*N)*sizeof(int));
return (V);
}
// Realocar memória após atualização do tamanho de V