ATP-Aula04-AplicaçõesDeVetores

Prévia do material em texto

Algoritmos e Técnicas de 
Programação
Aula 04: Estruturas de Dados Seqüenciais
(Aplicações de Vetores – Parte I)
Plano de Aula
� Alteração de Vetores
� Permutação de dois Elementos
� Inserção de um Elemento
� Exclusão de um Elemento
� Inversão dos Elementos
� Busca em Vetores
� Busca Seqüencial 
� Busca Seqüencial com Sentinela
� Busca Binária
� Exercícios
Permutação de Dois Elementos
� Permutar (trocar) os elementos Vi e Vj (i ≠ j) requer:
� j e i sejam índices válidos: 
� Em linguagem C ⇒ 0 ≤ i < N e 0 ≤ j < N
� o uso de uma variável auxiliar do mesmo tipo:
int Troca(int v[], int n, int i, int j)
{ int aux;
if (i != j && i >= 0 && i < n && j >= 0 && j < n)
{
aux = v[j];
v[j] = v[i];
v[i] = aux;
return 1;
} else return 0;
}
NOTA: Em C, matrizes são passadas por referência, sempre!
Inserção de um Elemento
� Para inserir um elemento X numa posição k do vetor 
(com capacidade Max), contendo N elementos 
deve-se observar:
� se N < Max, ou seja, se o vetor ainda não está
cheio;
� se a posição é válida (0 ≤ k ≤ N, em C)
� liberar a posição k, movimentando os elementos 
seguintes a k uma posição para frente.
� introduzir X na posição k e incrementar N:
� N← N+1
Inserção de um Elemento
int InsereElemento(int v[], int * n, int max, int k,
int x)
{ 
int i;
if (*n < max && k >= 0 && k <= *n)
{
for (i=*n; i>k; i--)
v[i] = v[i-1];
v[k] = x;
*n = *n+1; // ou (*n)++
return 1;
}
else
return 0;
}
Note que, se k = n, nada é feito/repetido dentro do comando “for”
Exclusão de um Elemento
� Para excluir um elemento numa posição k do 
vetor, contendo N elementos deve-se 
obervar:
� se a posição é válida (0 ≤ k < N)
� movimentar os elementos seguintes a k uma 
posição para trás:
� decrementar N: N← N-1
Exclusão de um Elemento
int ExcluiElemento(int v[], int *n, int k)
{
int i;
if (k >= 0 && k < *n)
{
for (i=k; i<*n-1; i++)
v[i] = v[i+1];
*n = *n-1; // ou (*n)--
return 1;
}
else
return 0;
}
Note que, se o elemento for o último (k = n-1) nada é feito mdentro do 
comando “for”
Inversão dos Elementos
� Inverter a ordem dos N elementos de um vetor V
significa:
� permutar o primeiro com o último elemento
� permutar o segundo com o penúltimo elemento
� etc.
� Uma estratégia simples consiste em:
� inicializar j com a primeira posição (j=0)
� inicializar k com a última posição (k=N-1)
� enquanto j < k faça
� permutar Vj com Vk
� j ← j + 1
� k ← k - 1
Inversão dos Elementos
void InverteVetor(int v[], int n)
{
int j, k;
j = 0;
k = n-1;
while (j < k)
{
Troca(v, &n, j, k); 
j++; 
k--;
}
}
Exercício 1
� Escreva uma função em C que exclua todos os 
elementos pares de um Vetor de N inteiros, 
retornando o número de elementos excluídos
� Dicas:
� um inteiro é par se o resto (operador %) da sua divisão por 
2 é zero
� utilize a função ExcluiElemento vista anteriomente:
� int ExcluiElemento(int v[], int *n, int d)
� Verifique se é possível percorrer o vetor
� do início para o final
� do final para o início
Solução 1
//exclui todos os números pares de um vetor "v" contendo "n"
//inteiros e retorna o número de exclusões.
int ExcluiPares(int v[], int * n)
{
int i, n0;
n0 = *n; //número inicial de elementos
for (i= *n-1; i>=0; i--)
if (v[i] % 2 == 0)
ExcluiElemento(v, n, i); //note que “n” já é ponteiro!
return n0 - *n; //a diferença é o número de exclusões
}
Exercício 2
� Implemente uma função para verificar se os N 
elementos de um Vetor de inteiros estão em 
ordem crescente.
� Dicas:
� se 0 ≤ N ≤ 1, o vetor está ordenado 
� se N ≥ 2, Vi ≤ Vi+1, para i = 0, 1, 2, …, N-2
Solução 2
// v = vetor; n = Número de elementos
int VetorOrdenado(int v[], int n)
{
int i;
for (i = 1; i < n; i++)
if (v[i-1] > v[i]) //fora de ordem -> sai com falso
return 0;
return 1; //nenhum fora de ordem -> sai com verdadeiro
}
Busca Seqüencial (Linear)
� A busca ou pesquisa por um elemento, cuja(s) 
propriedade(s) satisfaça(m) ao(s) argumento(s) de 
pesquisa, é uma tarefa bastante freqüente em 
programas de computador
� Os elementos são pesquisados seqüencialmente, 
um por um, e a busca termina:
� com sucesso, quando um elemento for encontrado 
� sem sucesso, quando acabar o universo de pesquisa
Busca Seqüencial
//“v”: vetor; “n”: No Elementos; “x”: valor procurado
//“pos”: posição do elemento, se encontrado
//retorno: (1 = encontrado, 0 = não encontrado) 
int BuscaSequencial(int v[], int n, int x, int * pos)
{
int i = 0;
while (i < n && x != v[i])
i++;
if (i < n)
{ //elemento encontrado
*pos = i;
return 1;
}
else
return 0;
}
Busca Seqüencial com Sentinela
� Consiste em colocar o elemento procurado 
imediatamente após o final do vetor (posição 
N), funcionando como um sentinela.
� Assim, o elemento sempre será encontrado e 
a 2a condição (x != v[i]) será
necessariamente falsa em algum momento, 
interrompendo o laço enquanto.
� Com isso, a 1a condição (i < n ) pode ser 
removida.
Busca Seqüencial com Sentinela
//“v”: vetor; “n”: No Elementos; “x”: valor procurado
//“pos”: posição do elemento, se encontrado
//retorno: (1 = encontrado, 0 = não encontrado) 
//OBS: “v” DEVE TER pelo menos UMA POSIÇÃO LIVRE!
int BuscaSequencialSent(int v[], int n, int x, int * pos)
{ int i = 0;
v[n] = x; //insere x como sentinela, após o último elem.
while (x != v[i])
i++;
if (i < n)
{
*pos = i;
return 1;
}
else
return 0;
}
Busca Binária em Vetores Ordenados
� Método muito eficiente, mas exige vetor ordenado
� Princípio: Similar ao utilizado quando se procura 
o nome de um assinante em um catálogo 
telefônico impresso:
� O vetor é dividido ao meio e o elemento central é lido
� Em relação ao elemento central, se o valor procurado for
1. =, a busca termina com sucesso: valor encontrado.
2. <, a busca prossegue na primeira metade
3. >, a busca prossegue na segunda metade
� Nos casos 2 e 3, a busca pode terminar com sucesso 
(caso 1), ou sem sucesso, quando não restarem mais 
elementos no universo de procura
Busca Binária: Exemplo 1 – Pesquisar 25
10
1
13
2
25
3
34
4
42
5
57
6
76
8
68
7
81
9
E DM
10
1
13
2
25
3
34
4
E DM
25
3
34
4
E DM
25 < 42⇒
1a metade 
D ← M - 1
25 > 13⇒
2a metade 
E ← M + 1
25 = 25⇒
Valor 
Encontrado!
Busca Binária: Exemplo 2 - Pesquisar 70
10
1
13
2
25
3
34
4
42
5
57
6
76
8
68
7
81
9
E DM
E M
E M
70 > 42⇒
2a metade:
E ← M+1
70 > 68⇒
2a metade:
E ← M+1
70 < 76⇒
1a metade: 
D ← M-1
57
6
76
8
68
7
81
9
D
76
8
81
9
D
E
E > D ⇒ impossível continuar:
o valor 70 não foi encontrado!
76
87
D
Busca Binária: Eficiência
� A cada busca, o número de elementos (N) é divido 
ao meio:
� 1a busca: N1 = N / 2
� 2a busca: N2 = N1 / 2 = N / 22 = N / 4
� 3a busca: N3 = N2 / 2 = N / 23 = N / 8
� 4a busca: N4 = N3 / 23 = N / 24 = N / 16
� ………..
� k-ésima busca: Nk= (Nk-1 / 2k-1) / 2 = N / 2k
� A busca termina quando o espaço de procura se 
reduz a um elemento, ou seja, quando Nk= 1:
Busca Binária: Eficiência
� Para se saber o número máximo (k), de buscas 
(iterações), basta resolver a equação:
� A busca binária é tem eficiência logaritmica:
� N = 103 (mil) elementos ⇒ 10 buscas
� N = 106 (milhão) elementos ⇒ 20 buscas
� N = 109 (bilhão) elementos ⇒ 30 buscas
 
1 2 2 lg 2 lg lg 2 lg
2
lg
log 1
k k k
k
N N N N k N
k N
k N
≤ ≤ ≥ ≥ ≥
≥
= + 
⇒ ⇒

⇒ ⇒
Busca Binária: Implementações
� A busca binária pode ser implemetada de forma 
recursiva ou iterativa, como qualquer algoritmo!� por ter uma visível natureza recursiva, sua 
implementação recursiva é ligeiramente mais fácil 
que a equivalente iterativa. 
� Além de encontrar ou não um elemento, uma 
implementação robusta deve retornar:
� a posição da 1a ocorrência, se o elemento for repetido. 
� a posição onde elemento deveria estar.
� Mesmo em bons livros, mas sobretudo na internet:
� são poucas as implementações iterativas robustas
� são raras as implementações recursivas robustas.
Busca Binária: PseudoCódigo
// V: Vetor ordenado
// e: limite esq. (inferior)
// d: limire dir. (superior)
// x: valor procurado
// pos: posição da 1a ocorr.
// retorno: verd = encontrado!
função PesqBin (V : Vetor; 
e, d : inteiro;
x : inteiro; 
PorRef Pos: inteiro): lógico
declare 
m : inteiro
Res : lógico
início
Res ← Falso
enquanto e ≤ d faça
m ← (e + d) div 2
se x > V[m] então
e ← m + 1
senão
d ← m - 1
se x = V[m] então
Res ← Verdadeiro
fim_se
fim_se
fim_enquanto
Pos ← e
retorne Res
fim