09. Listas

Prévia do material em texto

Ju
d
so
n
 S
an
to
s 
S
an
ti
ag
o
LISTAS
Alocação Seqüencial
Objetivos da Aula
Conhercer a estrutura de dados lista e seus 
principais algoritmos de manipulação
Alocação Sequencial
Listas ordenadas e não ordenadas
Busca, inserção e remoção em listas
Busca binária em listas ordenadas
Introdução
 Um programa de computador trabalha 
essencialmente com o armazenamento e a 
manipulação de dados
 Editores de texto
 Planilhas
 Editores de imagem
 Editores de vídeo
 Leitores de Correio Eletrônico
 Jogos
Introdução
 Algumas tarefas comumente feitas sobre os 
dados armazenados incluem:
 Inserção de novos dados
 Remoção de dados antigos
 Busca por dados 
 Listagem dos dados armazenados
 A eficiência dessas operações esta 
diretamente relacionada com a forma como 
os dados foram armazenados na memória
Introdução
 Existem muitas formas de organizar e 
manipular dados na memória
Listas Sequenciais
PilhasÁrvores
38 54 88 90 69
38 54 88 90 69 38
54
88
90
69
Listas Encadeadas
Introdução
 A organização mais comum é a seqüencial 
00100110
00001100
00110110
01011000
00011010
01011010
00001111
01000101
Dados organizados em 
posições consecutivas de 
memória
38 12 54 88 26 90 15 69
Dados organizados
logicamente como uma 
seqüencia
0xCB20
0xCB21
0xCB22
0xCB23
0xCB24
0xCB25
0xCB26
0xCB27
Introdução
 Em linguagem de programação C/C++, uma 
organização seqüencial pode ser obtida 
facilmente com o uso de vetores
00100110
00001100
00110110
01011000
00011010
01011010
00001111
01000101
Dados
na 
memória
38 12 54 88 26 90 15 69
Dados organizados
logicamente como uma 
seqüencia
int vet[8] = {28,12,54,88,26,90,15};
0xCB20
0xCB21
0xCB22
0xCB23
0xCB24
0xCB25
0xCB26
0xCB27
Introdução
 Diferentes estruturas de dados usam uma 
organização sequencial
 Lista
 Fila
 Pilha
 O que diferencia e define estas estrutura de 
dados são as operações de manipulação dos 
dados
Lista
 A Lista possui as seguintes características:
 Utiliza a organização sequencial de dados
 Define as seguintes operações:
 Inserção†
 Remoção†
 Busca
† De tal forma que elementos podem ser inseridos ou 
removidos de qualquer lugar da lista
Lista
 Listas podem ser construídas para armazenar 
qualquer tipo de informação
 Lista de valores inteiros
 Lista de caracteres
 Lista de compras no supermercado
 Lista de alunos de estrutura de dados
...
0 1 2 3 4 5 6 n
Lista
 Normalmente cada elemento de uma lista é 
formado por vários campos de dados
 Cada elemento da lista possui um 
identificador único ou chave
 Para evitar ambigüidades, todas as chaves 
devem ser distintas
812 425 654784 890 125 411658 ...
0 1 2 3 4 5 6 n
matricula
nome
nota8.8
joão
890
Lista
 Em linguagem C/C++ utiliza-se um registro
para definir os elementos de uma lista
struct aluno 
{
int matricula;
char nome[40];
float nota;
};
812 425 654784 890 125 411658 ...
0 1 2 3 4 5 6 n
matricula
nome
nota8.8
joão
890
Lista
 A lista é criada usando um vetor de registros 
(estático ou dinâmico)
struct aluno 
{
int matricula;
char nome[40];
float nota;
};
int main (void)
{
aluno lista[8];
...
lista[4].matricula = 890;
strcpy(lista[4].nome, "João");
lista[4].nota = 8.8;
...
}
812 425 654784 890 125 411658
0 1 2 3 4 5 6 7
matricula
nome
nota8.8
joão
890
Lista
 Em uma lista linear os elementos podem se 
encontrar ordenados, ou não ordenados, 
segundo os valores das chaves
 Listas ordenadas
 Listas não ordenadas
812 425 654784 890 125 411658
0 1 2 3 4 5 6 7
matricula
nome
nota8.8
joão
890
125 411 654425 658 784 890812
0 1 2 3 4 5 6 7
Algoritmos para Listas
 Os operações básicas em listas lineares são:
 Busca
 Inserção
 Remoção
 Outras operações:
 Combinação 
 Ordenação
 Etc.
Algoritmos de Busca
 O algoritmo abaixo apresenta a busca de um 
elemento na lista L, conhecendo-se sua chave
Algoritmo: Busca de um elemento na lista L
função busca1(x)
i = 0
busca = -1
enquanto i < n faça
se L[i].chave == x então
busca = i % chave encontrada
i = n+1 % encerra a repetição
senão
i = i+1 % continua a busca
Algoritmos de Busca
 A implementação da função busca em C/C++:
int busca1(int lista[], int tam, int x)
{
int i = 0;
int busca = -1;
while (i < tam)
{
if (lista[i].chave == x)
{
busca = i; // chave encontrada
i = tam + 1; // encerra repetição
} else {
i = i + 1; // continua a busca
}
}
return busca;
}
Algoritmos de Busca
 O algoritmo de busca realiza dois testes para 
cada elemento da lista: i < n e L[i].chave == x
 Existe uma forma de melhorar a eficiência
deste algoritmo?
Algoritmo: Busca de um elemento na lista L
função busca1(x)
i = 1
busca = 0
enquanto i ≤ n faça
se L[i].chave = x então
busca = i % chave encontrada
i = n+1 % encerra a repetição
senão
i = i+1 % continua a busca
Algoritmos de Busca
 O novo algoritmo coloca a chave procurada
na primeira posição vaga da lista. Isso 
elimina a necessidade de um dos testes.
Algoritmo: Busca de um elemento na lista L
função busca2(x)
L[n].chave = x
i = 0
enquanto L[i].chave ≠ x faça
i = i+1
se i ≠ n então
busca = i % chave encontrada
senão
busca = -1 % chave inexistente
Algoritmos de Busca
 Os algoritmos retornam a posição do 
elemento buscado ou -1, caso o elemento 
não esteja presente
 A complexidade dos dois algoritmos é O(n)
 Se o elemento buscado não estiver na lista, 
ambos algoritmos percorrerão a lista inteira
 Entretanto o segundo executa mais rápido 
por fazer um teste a menos no loop principal
Algoritmos de Busca
 Quando a lista está ordenada pode-se tirar 
proveito desse fato
 Se o número procurado não está na lista não 
é preciso percorrer a lista até o fim
124 241 657457 675 741 851742
Ex.: buscar a chave 500 na lista ordenada
Busca encerra aqui
Algoritmos de Busca
 Busca em uma lista ordenada
Algoritmo: Busca de um elemento na lista ordenada L
função busca-ord(x)
L[n].chave = x
i = 0
enquanto L[i].chave < x faça
i = i+1
se i == n ou L[i].chave ≠ x então
busca = -1 % chave inexistente
senão
busca = i % chave encontrada
Algoritmos de Busca
 A complexidade do algoritmo de busca para 
listas ordenadas é o mesmo O(n)
 A maior eficiência do algoritmo vai aparecer 
no caso médio, quando o elemento buscado 
não estiver na lista
 É possível ter um algoritmo mais eficiente 
para a busca em listas ordenadas?
 Dica: pensar em como buscamos um nome na 
lista telefônica
Busca Binária
 A idéia da busca binária é começar buscando 
pelo meio da lista
 Se o elemento buscado estiver à direita do 
ponto médio, não precisamos buscar na sua 
metade esquerda
 A cada passo reduz-se o espaço de busca pela 
metade
 A complexidade da busca binária é O(log n)
Busca Binária
 Busca em uma lista ordenada
Algoritmo: Busca binária em uma lista ordenada L
função busca-bin(x)
inf = 0; sup = n-1
busca = -1
enquanto inf ≤ sup faça
| meio = (inf + sup) / 2 
| se L[meio].chave == x então
| | busca = meio % chave encontrada
| | inf = sup + 1 % encerra repetição
| senão
| | se L[meio].chave < x então
| | | inf = meio + 1
| | senão
| | | sup = meio -1
└ └ └
Algoritmo de Inserção
 O algoritmo de inserção utiliza o algoritmo de 
busca para verificar se a chave já existe
Algoritmo: Inserçãona lista não ordenada L
função insere(x)
se n < M então
| se busca(x) == -1 então
| | L[n] = x
| | n = n + 1
| senão
| | "elemento já está presente"
senão
| "a lista está cheia"
Algoritmo de Inserção
 Implementação da inserção em C/C++:
void insere(int lista[], int tam, int & n, int x)
{
if (n < tam)
{
if (busca(lista, tam, x) == -1)
{
lista[n] = x;
n = n + 1;
} 
else
cout << "elemento já está presente" << endl;
} 
else 
cout << "lista cheia" << endl; 
}
Algoritmo de Remoção
 O algoritmo de remoção utiliza o algoritmo 
de busca para verificar se a chave já existe
Algoritmo: Remoção de um nó da lista L
função remove(x)
se n ≠ 0 então
| indice = busca(x)
| se indice ≠ -1 então
| | removido = L[indice]
| | para i = indice até n-2 faça
| | | L[i] = L[i+1]
| | n = n -1 % lista diminui em uma unidade
| senão
| | "elemento não se encontra na lista"
senão
| "a lista está vazia"
Algoritmo de Remoção
 Uma alternativa para o algoritmo de remoção 
é efetuar o deslocamento do último elemento 
da lista para a posição vaga
 A seqüencia de elementos fica alterada, só 
pode ser usado em listas não ordenadas
 Exercícios: 
 Construir o algoritmo alternativo de remoção
 Construir o algoritmo de inserção para listas 
ordenadas
Conclusão
 A lista é uma estrutura de dados obtida pela 
organização sequencial de dados na memória 
do computador
 As listas podem ser mantidas ordenadas ou 
não ordenadas pelo valor de sua chave
 As principais operações sobre listas são:
 Busca 
 Inserção 
 Remoção
Conclusão
 Os algoritmos mais eficientes para listas são:
 Busca: 
 Busca binária para listas ordenadas
 Busca2 para listas não ordenadas
 Inserção 
 Inserção sempre no final para listas não ordenadas
 Inserção baseada na busca para listas ordenadas
 Remoção
 A remoção convencional para listas ordenadas
 O algoritmo alternativo para listas não ordenadas