Enunciado 1: Inserir um novo elemento num vetor ordenado.
Algoritmo:
1) Pesquisar a posição onde inserir o novo elemento (adaptar o algoritmo de pesquisa sequencial,
de forma a que devolva a posição onde inserir o novo elemento)
2) Realocar memória para mais um elemento do vetor
3) Avançar uma posição todos os elementos do vetor desde a posição de inserção
4) Inserir o novo elemento na posição de inserção
Resolução
1) Pesquisar a posição onde inserir o elemento NovoElem no vector V de tamanho tam
k ← -1 // significa que Elem ainda não foi encontrado em V
i ← 0 // índice dos elementos do vector V
Enquanto (i < tam) e (k = -1) Fazer
Se (V[i] = Elem) então
k ← i
// significa que o NovoElem deve ser inserido na posição i do vetor (antes de um
elemento igual)
senão
Se (V[i] < Elem) então
i←i+1
senão
k ← i;
// significa que o NovoElem deve ser inserido na posição i do vetor
Se (k ≥ 0) então
NovoElem deve ser inserido na posição k
senão
NovoElem deve ser inserido na última posição de V (depois de aumentado o tamanho de V)
Função em C:
int DeterminarPosicaoInsercao (int NovoElem, int V[], int tam)
{
int i = 0, k = -1;
// k = posição onde deve ser inserido o NovoElem
// k= -1 significa que NovoElem deve ser inserido na última posição de V depois do tamanho
deste ter sido aumentado em 1 unidade
while ( (i < tam) && (k == -1) )
if (NovoElem == V[i])
k = i;
else
if (V[i] < NovoElem)
i = i + 1;
else
k = i;
return (k);
}
Função em C para inserir o elemento NovoElem num vetor V de tamanho tam:
int *InserirElementoVetor (int NovoElem, int V[], int *tam)
{
int pos, i;
pos = DeterminarPosicaoInsercao (NovoElem, V, *tam);
*tam = (*tam) + 1;
// Aumentar em 1 unidade o tamanho do vetor V
V = (int *) realloc (*tam, sizeof(int)); // Realocar memória após atualização do tamanho de V
if (pos >= 0) { // Avançar uma posição todos os elementos de V desde posição pos
for (i = *tam-1; i > pos; i--)
V[i] = V[i-1];
else
pos = *tam-1;
V[pos] = NovoElem;
// Inserir NovoElem na posição pos
return (V);
}
Enunciado 2: Remover um elemento de um vetor ordenado.
Algoritmo:
1) Procurar o elemento no vetor.
2) Se o elemento não existe no vetor, TERMINAR.
3) Se o elemento existe no vetor,
a) Devolver a posição onde se encontra o elemento a remover (pos)
b) Recuar 1 posição todos os elementos desde a posição pos até ao último elemento
c) Diminuir o tamanho do vetor em 1 unidade, relocando memória para o vetor considerando
que o seu tamanho foi reduzido em 1 unidade
Função em C para remover o elemento Elem num vetor V de tamanho tam:
int *RemoverElementoVetor (int NovoElem, int V[], int *tam)
{
int pos, i;
// Usar a pesquisa binária iterativa – devolve a posição do elemento (se existir) ou -1 (senão)
pos = PesquisaBinaria (Elem, V, *tam);
if (pos < 0)
return (V); // Como Elem não existe em V, devolver o vetor tal como entrou
else // pos >= 0, logo Elem existe em V na posição pos
{
for (i = pos; i < *tam; i++) // Recuar 1 posição todos os elementos desde a posição pos
V[i] = V[i+1];
*tam = (*tam) - 1; // Diminuir em 1 unidade o tamanho do vetor V
V = (int *) realloc (*tam, sizeof(int)); // Realocar memória após atualização do tamanho de V
return (V); // Devolver o vetor depois de atualizado o seu tamanho
}
}