Aula6 - Lista

Prévia do material em texto

Listas 
 
 
Prof: Ekler Paulino de Mattos 
ekler.mattos@gmail.com 
CPCX/UFMS 
Agenda 
 
 
 
 
 
 
 
 
• Listas lineares: 
– Algoritmos estruturas de armazenamento. 
 
 
 
 
Listas Lineares 
 
 
 
 
• Tipo mais simples de estrutura de dados. 
 
 
 
• Agrupam informações referentes a um conjunto de elementos 
que, de alguma forma, se relacionam entre si. 
 
 
 
• Pode constituir de inúmeros tipos de dados. 
 
 
 
 
Listas Lineares 
 
 
 
 
• Definição: 
– Conjunto de nós L1,L2,…,Ln, com n > 0, tal que: 
– se n > 0, L1 é o primeiro nó da lista; 
– para 1 < k ≤ n, o nó Lk é precedido por Lk−1. 
 
• Operações mais freqüentes: inserção, remoção e busca de 
elementos. 
 
• Casos particulares de listas: filas e pilhas. 
 
• Tipos de armazenamento: sequencial e encadeada. 
 
 
 
 
Listas Lineares (Alocação sequencial) 
 
 
 
 
– Usa bloco de memória (vetor) com tamanho pré-definido 
(alocação estática). 
 
– Operações simuladas através de índices. 
 
– Pode exigir movimentação de dados na memória. 
 
– Desvantagens: 
– Pode fazer uso desnecessário de memória. 
 
 
 
Listas Lineares (Alocação sequencial) 
 
 
 
 
• Busca linear (O(n)) ou busca binária (O(lg n)). 
 
• Inserção e remoção utilizam a busca. 
 
• O espaço disponível corresponde ao tamanho do vetor. 
 
• Pode haver overflow (buffer cheio) ou underflow (buffer vazio). 
 
• Existem variações nos algoritmos de inserção e remoção que 
dependem da organização interna dos elementos da lista. 
 
Listas Lineares (Alocação sequencial) 
 
 
 
 
 
 
 
n = 8 
índice = 
Listas Lineares (Alocação encadeada) 
 
 
 
Alocação encadeada: 
– Aloca pequenas porções de memória (nós), sempre que 
necessário (alocação dinâmica). 
 
– Operações simuladas através de ponteiros (não há 
movimentação de dados). 
 
– Uso mais eficiente de memória. 
 
– Exige espaço de memória adicional para armazenamento de 
ponteiros. 
 
Listas Lineares (Alocação encadeada) 
 
 
 
 
• Posições de memória são alocadas e desalocadas 
dinamicamente. 
 
• Disposição aleatória de dados na memória (ligação por 
ponteiros). 
 
• Vantagens e desvantagens dependem da aplicação. 
– Que tipo de alocação devemos usar quando... 
– Conhecemos o número de elementos da lista? 
– Quando vamos tratar mais de uma lista? 
– Fazemos acessos freqüentes a um elemento k específico? 
Listas Lineares (Alocação encadeada) 
 
 
 
Lista simplesmente encadeada: 
 
 
Objeto 
Listas Lineares 
 
 
 
Lista simplesmente encadeada: 
 
 
• Busca; 
• Inserção; 
• Edição; 
• Remoção; 
 
 
Listas Lineares (Alocação encadeada) 
 
 
 
Lista simplesmente encadeada: 
 
• Busca: é feita de forma linear, ou seja, é percorrido toda a lista 
até que o elemento procurado seja encontrado. 
 
 
 
 
Listas Lineares (Alocação encadeada) 
 
 
 
Lista simplesmente encadeada: - Impressão: 
 
• ptlista: lista encadeada.. 
• pont: elemento corrente da lista. 
Listas Lineares (Alocação encadeada) 
 
 
 
Lista simplesmente encadeada: 
 
• Busca: é feita de forma linear, ou seja, é percorrido toda a lista 
até que o elemento procurado seja encontrado. 
 
 
 
 
Listas Lineares (Alocação encadeada) 
 
 
 
Lista simplesmente encadeada: - Busca ordenada: 
 
 
 
• ptlista: lista encadeada. 
• ant e ptr: percorrem a lista respectivamente. 
• pont: armazena o elemento encontrado. 
Listas Lineares (Alocação encadeada) 
 
 
 
Lista simplesmente encadeada: 
 
• Busca: é feita de forma linear, ou seja, é percorrido toda a lista 
até que o elemento procurado seja encontrado. 
 
 
 
 
ptlista 
ant 
ptr 
11 
Listas Lineares (Alocação encadeada) 
 
 
 
Lista simplesmente encadeada: 
 
• Busca: é feita de forma linear, ou seja, é percorrido toda a lista 
até que o elemento procurado seja encontrado. 
 
 
 
 
ptlista 
ant ptr 
11 
Listas Lineares (Alocação encadeada) 
 
 
 
Lista simplesmente encadeada: 
 
• Busca: é feita de forma linear, ou seja, é percorrido toda a lista 
até que o elemento procurado seja encontrado. 
 
 
 
 
ptlista 
ant ptr 
11 
Listas Lineares (Alocação encadeada) 
 
 
 
Lista simplesmente encadeada: 
 
• Busca: é feita de forma linear, ou seja, é percorrido toda a lista 
até que o elemento procurado seja encontrado. 
 
 
 
 
ptlista 
ant ptr 
11 
Listas Lineares (Alocação encadeada) 
 
 
 
Lista simplesmente encadeada: 
 
• Busca: é feita de forma linear, ou seja, é percorrido toda a lista 
até que o elemento procurado seja encontrado. 
 
 
 
 
ptlista 
ant ptr 
11 
Listas Lineares (Alocação encadeada) 
 
 
 
Lista simplesmente encadeada: - Busca ordenada: 
 
 
 
 
 
Complexidade: O(n), onde n representa o número de nós da lista. 
 
Listas Lineares (Alocação encadeada) 
 
 
 
Lista simplesmente encadeada: 
 
 
• Inserção: Pode ser no início, meio e fim de uma lista. 
– É executado o algoritmo de busca até encontrar a posição correta de 
inserção do novo elemento. 
 
 
 
ant ptr 
Listas Lineares (Alocação encadeada) 
 
 
 
Lista simplesmente encadeada: - Inserção: 
 
Listas Lineares (Alocação encadeada) 
 
 
 
Lista simplesmente encadeada: - Inserção: 
 
 
 
 
 
Complexidade: É em virtude da busca… O(n), onde n representa o 
número de nós da lista. 
 
Listas Lineares (Alocação encadeada) 
 
 
 
Lista simplesmente encadeada: 
 
 
• Remoção: Pode ser no início, meio e fim de uma lista. 
– É executado o algoritmo de busca até encontrar o elemento a ser 
removido. 
 
 
 
Listas Lineares (Alocação encadeada) 
 
 
 
Lista simplesmente encadeada: - Remoção: 
Remoção do nó apontado por pont na lista. 
(Utilizando o algoritmo: busca-enc) 
 
Listas Lineares (Alocação encadeada) 
 
 
 
Lista simplesmente encadeada: - Remoção: 
 
 
 
 
 
Complexidade: É em virtude da busca… O(n), onde n representa o 
número de nós da lista. 
 
Fila 
 
 
 
Lista simplesmente encadeada: 
 
– É um tipo de Lista. 
 
– Restrição: “Primeiro a entrar é o primeiro a sair.” 
 
– - FIFO (First in first out). 
 
– Inserção de um nó é feito sempre no fim da lista. 
 
– Remoção de um nó só pode ser feito no início. 
 
 
Fila 
 
 
 
Lista simplesmente encadeada: - Enfileira 
 
 Fila vazia: inicio = fim = null 
01 Função Enfileira(inicio, fim, novachave) 
02 Ocupar(ptr); 
03 ptr ↑ .chave := novachave 
04 ptr ↑ .prox := null 
05 se (fim ≠ null) então 
06 fim ↑ .prox := ptr 
07 fim := ptr 
08 senão 
09 inicio := fim := ptr 
10 fimse 
11 fim 
Fila 
 
 
 
Lista simplesmente encadeada: - Desenfileira 
 
 
Fila vazia: inicio = fim = null 
01 Função Desenfileira(inicio, fim, recup) 
02 se (inicio ≠ null) então 
03 ptr := inicio 
04 inicio := inicio ↑ .prox 
05 se (inicio = null) então 
06 fim := null 
07 fimse 
08 recup := ptr ↑ .chave 
09 Desalocar(ptr) 
10 senão 
11 Imprima (“Underflow") 
12 fimse 
13 fim 
Pilha 
 
 
 
Lista simplesmente encadeada: 
 
– É um tipode Lista. 
 
– Restrição: “Primeio a entrar é o último a sair.” 
 
– Inserção de um nó é feito sempre no fim da lista. 
 
– Remoção de um nó sempre é feito no fim da lista. 
 
 
Pilha 
 
 
 
Lista simplesmente encadeada: - inserção: 
01 Pilha vazia: topo = null 
02 Função Empilha(topo, novachave) 
03 Ocupar(ptr); % solicitar nó 
04 ptr ↑ .chave := novachave % inicializar nó 
05 ptr ↑ .prox := topo 
06 topo := ptr % acertar pilha 
07 fim 
Pilha 
 
 
 
Lista simplesmente encadeada: - remoção: 
01 Função Desempilha(topo, recup) 
02 se (topo ≠ null) então 
03 ptr := topo % acertar pilha 
04 topo := topo ↑ .prox 
05 recup := ptr ↑ .chave % utilizar nó 
06 desalocar(ptr) % devolver nó 
07 senão 
08 Imprima (“Underflow") 
09 fimse 
10 fim 
Pilhas e Filas 
 
 
 
 
 
 
 
 
Complexidade: É em torno de algoritmos de manipulação de filas e 
pilhas é constante, ou seja, O(1), uma vez que buscas não são 
empregadas. 
 
Listas Lineares (Java x C++) 
 
 
 
Alocação encadeada: 
 
– C/C++ 
• Possui acesso direto a memória (ponteiros). 
• O endereço de um nó é via ponteiros. 
 
 
– Java 
• O desenvolvedor não tem acesso direto a memória. 
• É feito de forma transparente. 
• Ponteiro é feito através de referência a através de objetos. 
 
Listas Lineares (Java) 
 
 
 
• Java 
 
 
• Possui estruturas de listas fila e pilhas. 
 
 
 
 
• Interface java.util.ArrayList. 
 
Listas Lineares (Exercícios) 
 
 
 
• 1 - Crie uma lista ordenada que faça as seguintes operações: 
– Adicione: 1, 3, 4, 5, 4, 10. 
– Remove: 4, 
– Remove:10, 
– Adicione: 45. 
– Remove: 1. 
 
• 2 – Crie uma Fila que faça as operações do exercício 1. 
– Obs: Respeite as condições da estrutura. 
– Adicione: 1, 3, 4, 5, 4, 10. 
– Remove: 1, 3, 4 
– Adicione: 20. 
– Remove: 5. 
 
Listas Lineares (Exercícios) 
 
 
 
• 3 – Crie uma Pilha que faça as operações do exercício 1. 
– Obs: Respeite as condições da estrutura. 
– Adicione: 1, 3, 4, 5, 4, 10. 
– Remove, remove remove, adicione 10, remove, adicione 50, adicione 
90. 
 
 
 
Listas Circulares 
 
 
 
Lista Circulares: 
 
– Altera estrutura física da lista simplesmente encadeada, 
 fazendo o último nó da lista apontar para o primeiro elemento. 
 
– Principal vantagem: operação de busca mais eficiente. 
 
– Critério de parada deixa de ser o teste de final de lista. 
 
– Solução: comparar com endereço do nó em que se inicia a 
busca, ou seja, o nó cabeça. 
Listas Circulares 
 
 
 
Lista Circulares: 
 
Listas Circulares 
 
 
 
Lista Circulares: 
 
 Função BuscaCircular(x, ant, pont) 
 ant := ptlista 
 ptlista ↑.chave := x 
 pont := ptlista ↑.prox 
 enquanto (pont ↑.chave < x) faça 
 ant := pont 
 pont := pont ↑.prox 
 fimenquanto 
 se (pont ≠ ptlista) E (pont.chave = ptlista.chave) então 
 "chave localizada" 
 senão "chave não localizada" 
 fimse 
 
 Fim 
Listas Duplamente Encadeadas 
 
 
 
Lista Circulares: 
• Até então o percurso na lista era feito em um único sentido… 
 
• Listas duplamente encadeadas permitem realizar o percurso na 
lista em dois sentidos. 
 
• No nó: Nova referência (ponteiro). 
– Campo próx – referência para o próximo nó da lista. 
– Campo ant - referência para o nó anterior da lista. 
 
• Vantagens: 
– Não necessita reprocessar a lista inteira para fazer uma nova 
pesquisa. 
 
 
Listas Duplamente Encadeadas 
 
 
 
Listas circulares duplamente encadeadas: 
 
 
• Aplicações: 
– Listas não circulares e listas sem nó-cabeça podem também ser 
duplamente encadeadas. 
 
 
 
– Busca, Inserção e remoções em listas ordenadas são muito simples. 
 
 
Listas Duplamente Encadeadas 
 
 
 
Listas circulares duplamente encadeadas: 
 
Listas Duplamente Encadeadas 
 
 
 
Listas circulares duplamente encadeadas: - Busca duplamente 
encadeada ordenada. 
 
01 função buscaDup(x) 
02 ultimo := ptlista ↑.ant 
03 se (x <= ultimo ↑.chave) então 
04 pont := ptlista ↑.prox 
05 enquanto (pont ↑.chave < x) faça 
06 pont := pont ↑.prox 
07 fimenquanto 
08 buscaDup := pont 
09 senão buscaDup := ptlista 
10 fimse 
11 fim 
Listas Duplamente Encadeadas 
 
 
 
Listas circulares duplamente encadeadas: - Inserção 
1 2 4 7 
3 
pt 
ptrlista 
pont 
Listas Duplamente Encadeadas 
 
 
 
Listas circulares duplamente encadeadas: - Inserção 
pont := buscaDup(x) 
se (pont = ptlista ou pont.chave ≠ x) então 
 anterior := pont ↑.ant 
 ocupar(pt) %solicitar nó 
 pt ↑.info := novo-valor %inializar nó 
 pt ↑.chave := x 
 pt ↑.ant := anterior 
 pt ↑.post := pont 
 anterior.post := pt 
 pont ↑.ant := pt 
senão "elemento já se encontra na lista" 
fimse 
Listas Duplamente Encadeadas 
 
 
 
Listas circulares duplamente encadeadas: - remoção 
Listas Duplamente Encadeadas 
 
 
 
Listas circulares duplamente encadeadas: - remoção 
pont := buscaDup(x) 
se (pont ≠ ptlista e pont ↑.chave = x) então 
 anterior := pont ↑.ant 
 posterior := pont ↑.post 
 anterior ↑.post := posterior % acertar lista 
 posterior ↑.ant := anterior 
 valor-recuperado := pont ↑.info % utilizar nó 
 desocupar(pont) % devolver nó 
senão "elemento não se encontra na lista" 
fimse 
 
Listas Lineares (Exercícios) 
 
 
 
• Utilizando os algoritmos de: 
– Lista simplesmente encadeadas. 
– Lista circular. 
– Lista duplamente encadeadas. 
 
 
• 1 - Crie uma lista ordenada que faça as seguintes operações: 
– Adicione: 1, 3, 4, 5, 4, 10. 
– Remove: 4, 
– Remove:10, 
– Adicione: 45, 15. 
– Remove: 1, 4. 
Listas Lineares (Exercícios) 
 
 
 
• Utilizando os algoritmos de Fila e Pilha… 
• 2 – Crie uma Fila que faça as operações: 
– Adicione: 1, 3, 4, 5, 4, 10. 
– Remove: 1, 3, 4 
– Adicione: 20. 
– Remove: 5. 
 
 
• 3 – Crie uma Pilha que faça as operações: 
– Adicione: 1, 3, 4, 5, 4, 10. 
– Remove, remove remove, adicione 10, remove, adicione 50, adicione 
90, adicione 15, adicione 15, remove.