3 - Listas Lineares Sequenciais Ordenadas

Prévia do material em texto

Aula 3 
Listas Lineares Sequenciais Ordenadas 
 
prof Leticia Winkler 
 
1 
Listas Lineares Sequenciais Ordenadas 
 Elementos da lista estão dispostos num vetor (contíguos na 
memória) e ordenado de acordo com alguma informação 
 A ordenação pode ser crescente ou decrescente 
 Exemplo: 
 Ordenados crescente por nome 
 
 
 
 Ordenados decrescente pelo resultado 
 
Prof. Leticia Winkler 2 
Bia 8.5 Ana 5.5 Leo 7.5 Ruy 10.0 
Bia 8.5 Ana 5.5 Leo 7.5 Ruy 10.0 
Observações 
 Operação de inicialização, fundamental antes de 
qualquer outra operação; 
 Verificação se a lista está vazia ou cheia, não mudam se 
a lista está ou não ordenada; 
 Pode–se fazer uma busca seqüencial em uma lista já 
ordenada; 
 Normalmente a operação de busca mais apropriada em 
uma lista ordenada é a busca Binária; 
 A inserção, remoção em uma lista ordenada é 
diferente, já que a ordenação dos elementos deve ser 
mantida após estas operações. 
Prof. Leticia Winkler 3 
Criação da Lista 
 Supondo uma lista de números reais. 
 A criação da lista se constitui na operação de declaração 
das variáveis que descrevem a lista. 
float v[10]; // lista propriamente dita – capacidade de 10 elementos 
int n; // quantidade de elementos existentes em v 
 
Prof. Leticia Winkler 4 
... 
0 1 2 3 ... 9 8 7 6 
Inicialização da Lista 
 Numa Lista Linear Sequencial a inicialização se 
constitui em atribuir 0 a quantidade de elementos 
existente na lista (indicada pela variável n) 
n = 0; 
 
Prof. Leticia Winkler 5 
... 
0 1 2 3 ... 9 8 7 6 
Inserção mantendo a Ordem 
 Consiste em adicionar um valor no vetor, mantendo a 
ordem existente e ajustando o total de elementos. 
 Só pode ocorrer, no entanto, se a lista não estiver cheia. 
 Protótipo: 
void inserirEmOrdem(float [], float , int &, int); 
 Chamada na main: 
cout << “Digite um valor para inserção ordenada : “; 
cin >> valor; 
inserirEmOrdem(v,valor,n,10); 
 
Prof. Leticia Winkler 6 
Mecanismo de Inserção 
 Supondo a lista ordenada, onde n == 6 (existem 6 elementos): 
 
 
 Deseja-se inserir o valor 4.5 
 Verifica-se se a lista está cheia, caso positivo, não pode inserir; 
senão 
 Inicia a comparação do 4.5 com o elemento da posição zero, depois 
com o da posição 1, e assim por diante, até se encontrar um valor 
maior que 4.5, que ocorrerá na posição 4 (esta será a posição de 
inserção do 4.5) 
 
 
Prof. Leticia Winkler 7 
1.5 2.7 3.6 
0 1 2 3 
4.7 5.9 
4 5 6 7 
4.1 
8 9 
1.5 2.7 3.6 
0 1 2 3 
4.7 5.9 
4 5 6 7 
4.1 
8 9 
Mecanismo de Inserção 
 Desloca-se os elementos para direita, a partir da última 
posição (no exemplo, é a posição 5) para posição 
seguinte, até a posição de inserção do 4.5 (posição 4) 
 
Prof. Leticia Winkler 8 
1.5 2.7 3.6 
0 1 2 3 
4.7 5.9 
4 5 6 7 
4.1 
8 9 
1.5 2.7 3.6 
0 1 2 3 
4.7 5.9 
4 5 6 7 
4.1 
8 9 
5.9 
Mecanismo de Inserção 
 Continua o deslocamento até chegar a posição de 
inserção do 4,5 – posição 4 
Prof. Leticia Winkler 9 
1.5 2.7 3.6 
0 1 2 3 
4.7 5.9 
4 5 6 7 
4.1 
8 9 
1.5 2.7 3.6 
0 1 2 3 
4.7 4.7 
4 5 6 7 
4.1 
8 9 
5.9 
5.9 
Posição de inserção do 4.5 
Mecanismo de Inserção 
 Insere o 4.5 
 
 
 
 
 Atualiza a quantidade de elementos da lista (passa a 
ser 7) 
n++; 
 
Prof. Leticia Winkler 10 
1.5 2.7 3.6 
0 1 2 3 
4.5 4.7 
4 5 6 7 
4.1 
8 9 
5.9 
Código da Função para Inserir em Ordem 
void inserirEmOrdem(float v[], float valor, int &n, int tam) { 
 int i, posicao; 
 if (n == tam) { // testa se o vetor está cheio 
 cout << "ERRO : Lista cheia." << endl; 
 return; // sai da função sem retornar valor algum 
 } 
 if (n==0) { 
 posicao = 0; 
 } 
 else { 
 // Procura a posição de inserção 
 i = 0; 
 while (valor > v[i] && i < n) 
 i++; 
 posicao = i; // armazena a posição onde o valor será inserido 
 // Desloca os elementos, mantendo a ordem 
 for (i = n; i > posicao; i--) 
 v[i] = v[i-1]; 
 } 
 // Insere na posição de inserção 
 v[posicao] = valor; 
 n++; // Incrementa a quantidade de nós na lista 
} Prof. Leticia Winkler 11 
Busca Binária 
 Consiste em fazer uma busca em um vetor já ordenado 
 
 
 
 Esta operação será implementada por uma função que retornará o 
índice do elemento (sucesso na busca) ou -1 (fracasso na busca). 
 Protótipo: 
void buscaBinaria(float v[], float valor,int n); 
 Chamada na main: 
cout << “Digite um valor para busca: “; 
cin >> valor; 
posicao = buscaBinaria(v,valor,n); 
 
Prof. Leticia Winkler 12 
1.5 2.7 3.6 
0 1 2 3 
4.5 4.7 5.9 
4 5 6 7 
4.1 
8 9 
Mecanismo da Busca Binária 
 Supondo-se que deseja-se buscar o valor 4.7 no vetor 
 
 
 Divide-se o espaço de busca ao meio e verifica-se, 
comparando o valor de busca (no exemplo 4.7) com o 
elemento do meio da lista. 
Prof. Leticia Winkler 13 
1.5 2.7 3.6 
0 1 2 3 
4.5 4.7 5.9 
4 5 6 7 
4.1 
8 9 
1.5 2.7 3.6 
0 1 2 3 
4.5 4.7 5.9 
4 5 6 7 
4.1 
8 9 
meio 
Espaço de busca 
Mecanismo da Busca Binária 
 
 
 
 
 
 
 
 
 
 Se a chave de busca (valor procurado) é igual ao valor central do vetor (meio) – 
a busca termina com sucesso 
 Se a chave de busca (valor procurado) é menor que o valor central do vetor 
(meio) – a busca continua na primeira metade do vetor 
 Se a chave de busca (valor procurado) é maior que o valor central do vetor 
(meio) – a busca continua na segunda metade do vetor 
 No Exemplo, a busca continua na segunda metade do vetor. 
 
Prof. Leticia Winkler 14 
1.5 2.7 3.6 
0 1 2 3 
4.5 4.7 5.9 
4 5 6 7 
4.1 
8 9 
meio 
Espaço de busca 
2ª metade 1ª metade 
Comparações: 1a 
Mecanismo da Busca Binária 
 
 
 
 
 
 
 Se a chave de busca (valor procurado) é igual ao valor central do vetor (meio) – a busca 
termina com sucesso 
 Se a chave de busca (valor procurado) é menor que o valor central do vetor (meio) – a 
busca continua na primeira metade do vetor 
 Se a chave de busca (valor procurado) é maior que o valor central do vetor (meio) – a 
busca continua na segunda metade do vetor 
 O processo se repete até que o elemento seja encontrado – a posição, onde o elemento foi encontrado, 
é retornada 
 Ou, até que o espaço de busca termine (busca acaba sem sucesso) – o valor -1 é retornado (posição 
inválida) – indica que o valor procurado não foi encontrado. 
 No Exemplo, a busca termina com sucesso e o valor 5 (posição do vetor onde o elemento 
foi encontrado) é retornado como resposta pela função que realiza a busca binária. 
Prof. Leticia Winkler 15 
4.5 5.6 
4 5 6 
meio 
4.7? 
Comparações: 2a 
4.7 
Espaço de busca 
Código da Função da Busca Binária 
int buscaBinaria(float v[], float valor, int n) { 
 int ini = 0, // inicializa o início do intervalo para a busca 
 fim = n -1, // inicializa o fim da intervalo 
 meio; // armazenará o índice do meio do intervalo 
 while (ini <= fim) { 
 meio = (ini + fim)/2; // determina o meio do intervalo 
 if (v[meio] == valor) 
 return meio; // achou o valor na área de índice meio 
 if (valor < v[meio]) 
 fim = meio -1; 
 else 
 ini = meio+1; 
 } 
 return -1; // não achou o valor no vetor 
} 
Prof. Leticia Winkler 16 
Busca Sequencial X Busca Binária 
 Supondo-se o vetor: 
 
 
 Na busca binária para localizar o 4.7 são realizadas 2 
comparações 
 Na busca sequencial seriam 6 comparações para 
localizar o valor 4.7 
 
Prof. Leticia Winkler 17 
1.5 2.7 3.6 4.1 
0 1 2 3 
4.5 4.7 5.9 
4 5 6 
4.7? 
Busca Sequencial X Busca Binária 
 Busca por um registro entre 1000 
 Busca Binária 
 complexidade: O(log n) 
 pior caso: (maior inteiro imediatamente menor que (log n)) + 1 
comparações= 10 comparações, ou seja, 10 acessos a disco. 
 Busca Sequencial 
 complexidade: O(n) 
 pior caso: 1000 
 em média: 500 
 A busca binária é mais eficiente na maioria dos casos (mais 
veloz) 
 A busca seqüencial tem a vantagem de poder ser aplicada a 
qualquer vetor (no sentido de não haver obrigatoriedade dos 
elementos do vetor vetor terem que estar ordenados). 
Prof. Leticia Winkler 18 
Remoção mantendo Ordem 
 Consiste em retirar um valor do vetor, mantendo a ordem 
existente e ajustando o total de elementos. 
 Só pode ocorrer, no entanto, se a lista não estiver vazia. 
 Caso ocorra a remoção, o total de elementos da lista deve 
ser decrementado. 
 Protótipo: 
void removerEmOrdem(float [], float , int &); 
 Chamada na main: 
cout << “Digite o valor a ser removido: “; 
cin >> valor; 
removerEmOrdem(v,valor,n); 
Prof. Leticia Winkler 19 
Mecanismo de Remoção 
 Supondo a lista ordenada, onde n == 7 (existem 7 elementos): 
 
 
 
 Deseja-se remover o valor 3.6 
 Verifica-se se a lista está vazia, caso positivo, não pode retirar; senão 
 Realiza-se uma busca do valor 3.6 para se obter a posição onde o 3.6 
está na lista (no exemplo, posição 2). 
 Pode-se realizar a busca binária, já que o vetor está ordenado 
 Deve-se verificar se o valor foi encontrado 
 No exemplo seria encontrado o valor 2 
Prof. Leticia Winkler 20 
1.5 2.7 3.6 4.1 
0 1 2 3 9 8 
4.5 4.7 5.9 
4 5 6 7 
Mecanismo de Remoção 
 Atualiza-se a quantidade de elementos da lista: 
n--; (no exemplo n passa a ser 6) 
 A partir da posição seguinte do elemento a ser 
removido, até o final, move-se os elementos para 
posição anterior 
 
Prof. Leticia Winkler 21 
1.5 2.7 3.6 4.1 
0 1 2 3 9 8 
4.5 4.7 5.9 
4 5 6 7 
1.5 2.7 4.1 4.1 
0 1 2 3 9 8 
4.5 4.7 5.9 
4 5 6 7 
Mecanismo de Remoção 
Prof. Leticia Winkler 22 
1.5 2.7 4.1 4.1 
0 1 2 3 9 8 
4.5 4.7 5.9 
4 5 6 7 
1.5 2.7 4.1 4.5 
0 1 2 3 9 8 
4.5 4.7 5.9 
4 5 6 7 
Mecanismo de Remoção 
Prof. Leticia Winkler 23 
1.5 2.7 4.1 4.5 
0 1 2 3 9 8 
4.5 4.7 5.9 
4 5 6 7 
1.5 2.7 4.1 4.5 
0 1 2 3 9 8 
4.7 4.7 5.9 
4 5 6 7 
Mecanismo de Remoção 
Prof. Leticia Winkler 24 
1.5 2.7 4.1 4.5 
0 1 2 3 9 8 
4.7 4.7 5.9 
4 5 6 7 
1.5 2.7 4.1 4.5 
0 1 2 3 9 8 
4.7 5.9 5.9 
4 5 6 7 
N == 6 
Código da Função para Remover em Ordem 
void removerEmOrdem(float v[], float valor, int &n) { 
 int i, posicao; 
 if (n == 0) { // testa se o vetor está vazio 
 cout << “ERRO : Lista vazia.” << endl; 
 return; // abandona a função removerEmOrdem – sem retorno de valor 
 } 
 //chamada para a busca binaria 
 posicao = buscaBinaria(v,valor,n); 
 if (posicao < 0) { 
 cout << “ERRO : Elemento não encontrado.” << endl; 
 return; // abandona a função removerEmOrdem – sem retorno de valor 
 } 
 // decrementa a quantidade de elementos da lista 
 n--; 
 // desloca os elementos, ajustando a lista 
 for (i = posicao; i < n; i++) 
 v[i] = v[i+1]; 
 } Prof. Leticia Winkler 25 
Prof. Leticia Winkler 26 
Ordenar 
 Ordenar é o ato de se colocar os elementos de uma 
seqüência, em uma dada relação de ordem entre si, de 
acordo com um critério pré-estabelecido. 
 Crescente 
 Decrescente 
 O termo técnico em inglês para ordenar é sort, cuja 
tradução literal é classificar. 
 Métodos (mais simples): 
 Troca ou Bolha – Bubblesort 
 Inserção – Insertion Sort 
 Seleção – Selection Sort 
 
Prof. Leticia Winkler 27 
Bubblesort 
 A idéia é percorrer o vetor diversas vezes e a cada 
passagem, fazer flutuar para o topo o menor elemento 
da sequência. 
 Essa movimentação lembra a forma como as bolhas em 
um tanque de água procuram seu próprio nível. 
 Percorre várias vezes o vetor de maneira seqüencial 
(passos). Em cada passo, 
 compara cada elemento no vetor com o seu sucessor (v[i] 
com v[i+1]) e 
 troca o conteúdo das posições em análise, caso não 
estejam na ordem desejada. 
Prof. Leticia Winkler 28 
Mecanismo do Bubblesort 
 Supondo o vetor de valores inteiros, que se deseja colocar em ordem 
crescente: 
 
 
 Iniciando da posição 0 (zero) do vetor, compara o elemento com o seu 
sucessor: 
 Compara o 53 com o 25 (posição 0 com a posição 1) 
 Se estiver na ordem desejada, não faz nada e passa para posição seguinte 
 Senão, troca os dois entre si 
 Não estão na ordem desejada, então troca 
 
 
 Continua a comparação (posição 1 com a posição 2) 
Prof. Leticia Winkler 29 
53 25 46 32 23 37 41 17 10 
25 53 46 32 23 37 41 17 10 
Mecanismo do Bubblesort 
 
 
 Compara o 53 com o 46 
 Não estão na ordem desejada – troca 
 
 
 Compara o 53 com o 32 
 Não estão na ordem desejada – troca 
 
Prof. Leticia Winkler 30 
25 53 46 32 23 37 41 17 10 
25 46 53 32 23 37 41 17 10 
25 46 32 53 23 37 41 17 10 
Mecanismo do Bubblesort 
 
 
 Compara o 53 com o 23 
 Não estão na ordem desejada – troca 
 
 
 Compara o 53 com o 37 
 Não estão na ordem desejada – troca 
 
Prof. Leticia Winkler 31 
25 46 32 23 53 37 41 17 10 
25 46 32 53 23 37 41 17 10 
25 46 32 23 37 53 41 17 10 
Mecanismo do Bubblesort 
 
 
 Compara o 53 com o 41 
 Não estão na ordem desejada – troca 
 
 
 Compara o 53 com o 17 
 Não estão na ordem desejada – troca 
 
Prof. Leticia Winkler 32 
25 46 32 23 37 41 53 17 10 
25 46 32 23 37 53 41 17 10 
25 46 32 23 37 41 17 53 10 
Mecanismo do Bubblesort 
 
 Compara o 53 com o 10 
 Não estão na ordem desejada – troca 
 
 Terminou o espaço do vetor. Está Ordenado? Não! 
 Mas o maior elemento ficou na última posição. 
 
 
 Recomeça, excluindo a última posição 
Prof. Leticia Winkler 33 
25 46 32 23 37 41 17 53 10 
25 46 32 23 37 41 17 10 53 
25 46 32 23 37 41 17 10 53 
Mecanismo do Bubblesort 
 
 
 Ordenação OK – não faz nada, passa para próxima 
posição 
 
 
 troca 
 
Prof. Leticia Winkler 34 
25 46 32 23 37 41 17 10 53 
25 46 32 23 37 41 17 10 53 
25 32 46 23 37 41 17 10 53 
Mecanismo do Bubblesort 
Prof. Leticia Winkler 35 
25 32 46 23 37 41 17 10 53 
25 32 23 46 37 41 17 10 53 
25 32 23 37 46 41 17 10 53 
25 32 23 37 41 46 17 10 53 
25 32 23 37 41 17 46 10 53 
25 32 23 37 41 17 10 46 53 
Mecanismo do Bubblesort 
Prof. Leticia Winkler 36 
25 32 23 37 41 17 10 46 53 
25 32 23 37 41 17 10 46 53 
25 23 32 37 41 17 10 46 53 
25 23 32 37 41 17 10 46 53 
25 23 32 37 41 17 10 46 53 
25 23 32 37 17 41 10 46 53 
Mecanismo do Bubblesort 
 
 
 
 Recomeça 
Prof. Leticia Winkler 37 
25 23 32 37 17 10 41 46 53 
25 23 32 37 17 41 10 46 53 
25 23 32 37 17 10 41 46 53 
23 25 32 37 17 10 41 46 53 
23 25 32 37 17 10 41 46 53 
Mecanismo do Bubblesort 
 
 
 
 
 
 Recomeça 
Prof. Leticia Winkler 38 
23 25 32 37 17 10 41 46 53 
23 25 32 17 37 10 41 46 53 
23 25 32 17 10 37 41 46 53 
23 25 32 17 10 37 41 46 53 
23 25 32 17 10 37 41 46 53 
Mecanismo do Bubblesort 
 
 
 
 
 
 Recomeça 
Prof. Leticia Winkler 39 
23 25 32 17 10 37 41 46 53 
23 25 17 32 10 37 41 46 53 
23 25 17 10 32 37 41 46 53 
23 25 17 10 32 37 41 46 53 
23 25 17 10 32 37 41 46 53 
Mecanismo do Bubblesort 
 
 
 
 Recomeça 
Prof. Leticia Winkler 40 
23 17 25 10 32 37 41 46 53 
23 17 10 25 32 37 41 46 53 
23 17 10 25 32 37 41 46 53 
17 23 10 25 32 37 41 46 53 
17 10 23 25 32 37 41 46 53 
Mecanismo do Bubblesort 
 Recomeça 
 
 
 
 
 VETOR ORDENADO!!! 
Prof. Leticia Winkler 41 
17 10 23 25 32 37 41 46 53 
10 17 23 25 32 37 41 46 53 
Código do Bubblesort 
void ordenarBolha(float v[], int n) { // n é o no. de elementos em v 
 int i , // índice 
 aux, // auxiliar para troca 
 trocou = true, 
 fim = n – 1; 
 
 while (trocou) { 
 trocou = false; // sinaliza que é falso que trocou 
 for (i = 0; i < fim;i++) { 
 if (v[i] > v[i+1]) { 
 aux = v[i]; 
 v[i] = v[i+1]; 
 v[i+1] = aux; 
 trocou = true; // sinaliza que é verdadeiro que trocou 
 } // fim if 
 } // fim for 
 fim--; // decrementa o fim 
 } 
 } 
 
Prof. Leticia Winkler 42 
Exercício #1 
 Faça um programa que declare uma lista sequencial de 
tamanho 10 para armazenar valores inteiros. Esta lista deve 
ser ordenada decrescentemente. Seu programa deve 
apresentar um menu com opções para: 
 Inserção de dados na lista 
 Remoção de dados da lista 
 Busca de um determinado valor na lista 
 Percorrer a lista 
 Obs: 
 Para cada operação deve ser criada uma função. 
 Observe que a manipulação de valores deve manter a lista 
ordenada decrescentemente. 
 Utilize a busca binária para procurar um valor dentro da lista 
Prof. Leticia Winkler 43