3 - LISTAS LINEARES

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

DEQ/EE3 – FUNDAMENTOS DA ESTRUTURA DA INFORMAÇÃO
Departamento de Engenharia Química
Universidade Estadual de Maringá
Prof. Leonardo F. Costa
LISTAS LINEARES
Introdução
Alocação Sequencial
Listas Lineares em Alocação Sequencial
Pilhas e Filas
Alocação Encadeada
Listas Lineares em Alocação Encadeada
Alocação de Espaço de Tamanho Variável
ALOCAÇÃO ENCADEADA
Neste caso, os dados de uma estrutura não são alocados estaticamente na memória.
Também conhecido como alocação dinâmica, as posições de memória são alocadas/desalocadas a medida que são necessárias/dispensadas.
ALOCAÇÃO ENCADEADA
É necessário o acréscimo de um campo a cada nó; 
Esse campo é aquele que indica o endereço do próximo nó da lista
Na alocação encadeada, os nós de uma lista encontram-se aleatoriamente dispostos na memória e são interligados por ponteiros, que indicam a posição do próximo elemento da tabela.
ALOCAÇÃO ENCADEADA
ALOCAÇÃO SEQUENCIAL
ALOCAÇÃO ENCADEADA x ALOCAÇÃO SEQUENCIAL
Exige mais MEMÓRIA pois gasta um campo a mais (ponteiro)
Ela é mais conveniente quando manipula-se duas ou mais listas 
Acesso ao k-ésimo elemento é mais rápido na alocação sequencial
ALOCAÇÃO ENCADEADA x ALOCAÇÃO SEQUENCIAL
Se nessa lista são feitas inserções e remoções, há necessidade de encontrar novas posições de memória para armazenamento e liberar outras que possam ser reutilizadas posteriormente;
Um algoritmo para gerenciar as posições de memória é necessário;
Por isso deve-se criar uma lista especial chamada Lista de Espaço Disponível (LED)
LED – Lista de Espaço Disponível
Esta lista contém posições de memória ainda não utilizadas ou dispensadas após sua utilização.
A implementação da LED pode ser feita de duas formas
Com o dimensionamento de um único vetor de nós M simulando a memória total disponível:
LED – Lista de Espaço Disponível
O endereço do nó corresponde ao índice de uma posição do vetor
Com isso tem-se o controle total das posições ocupadas e livres 
A princípio como a memória se acha totalmente disponível, todos os seus nós são encadeados na LED;
A variável ponteiro vago se refere ao topo da estrutura.
LED – Lista de Espaço Disponível
Para inicializar uma LED são necessários os seguintes passos:
Os campos ponteiros dos nós são encadeados sequencialmente.
 O ponteiro vago é inicializado com o endereço do primeiro nó da lista que foi encadeada no primeiro passo
O campo ponteiro do último nó recebe o valor l, indicando fim da lista
LED - Algorítmos
Busca de um nó na LED
Devolução de um nó à LED
LED – Pascal e C
Em Pascal, utilizamos
new(pt)
dispose(pt)
Em C, utilizamos: 
Node *pt = malloc(sizeof(Node))
free (pt)
Em C++, utilizamos
pt = new(node)
delete(pt)
LISTAS LINEARES
Introdução
Alocação Sequencial
Listas Lineares em Alocação Sequencial
Pilhas e Filas
Alocação Encadeada
Listas Lineares em Alocação Encadeada
Alocação de Espaço de Tamanho Variável
LISTAS LINEARES EM ALOCAÇÃO ENCADEADA
Qualquer estrutura, inclusive listas, que seja armazenada em alocação encadeada requer o uso de um ponteiro que indique o endereço do primeiro nó.
O percurso de uma lista é feito então a partir deste ponteiro
A idéia consiste em seguir consecutivamente pelos endereços existentes no campo que indica o próximo nó, da mesma forma que na alocação sequencial se acrescentava uma unidade ao índice do percurso
O algorítmo abaixo apresenta o percurso para impressão do campo info de uma lista, sendo ptlista o ponteiro para o primeiro nó
LISTAS LINEARES EM ALOCAÇÃO ENCADEADA
Na maioria das estrutura de dados, o algoritmo de busca deve ser eficiente, pois é utilizado nas operações de inserção, remoção e outras operações.
Nas listas lineares em alocação encadeada, faremos uma pequena variação na estrutura de armazenamento: a criação de um nó especial, chamado nó-cabeça, nunca removido, que passa a ser o nó indicado pelo ponteiro de início de lista (ptlista)
LISTAS LINEARES EM ALOCAÇÃO ENCADEADA
Esta alteração visa a simplificação nos procedimentos de inserção e remoção, evitando testes especiais para verificar se o nó desejado é o primeiro da lista
Busca em uma lista ordenada em alocação encadeada
Nó-cabeça: ptlista
Chave procurada: x
O parâmetro pont retorna apontando para o elemento procurado
O parâmetro ant retorna o elemento anterior ao procurado
Caso não seja encontrado, pont aponta para l e ant continua indicando o elemento anterior ao último pesquisado
Busca em uma lista ordenada em alocação encadeada
Como o algoritmo estabelece um percurso pela tabela, sua complexidade é O(n), sendo n o número de nós da lista
Inserção e Remoção em uma lista ordenada em alocação encadeada
Após a realização de busca, as operações de inserção e remoção em uma lista encadeada são triviais
Há 3 fases a serem cumpridas:
A comunicação com a LED
O acesso ao campo de informação do nó
Acerto da estrutura
Inserção de um nó com novo-valor após o nó apontado por ant
Remoção de um nó apontado por pont
PILHAS E FILAS
Como casos particulares, algumas modificações são necessárias para implementar operações eficientes em pilhas e filas.
No caso de pilhas, consideramos listas simplesmente encadeadas, sem nó-cabeça.
O topo da pilha é o primeiro nó da lista, apontado por topo
Se a pilha estiver vazia, então topo = l
Filas exigem duas variáveis ponteiro
início: que aponta para o primeiro nó da lista
fim: aponta para o último nó da lista
Se a fila estiver vazia, então início = fim = l
Inserção na pilha
Remoção da pilha
Inserção na fila
Remoção da fila
PILHAS E FILAS
As complexidades dos algorítmos de manipulação de filas e pilhas são constantes, ou seja, O(1), uma vez que buscas não são empregadas
Ordenação por Distribuição
Seja uma lista L, composta de n chaves, cada qual representada por um número inteiro numa base b > 1. O problema consiste em ordenar esta lista.
O algorítmo utiliza b filas, denotadas por Fi, 0 ≤ i ≤ b-1.
Seja d o comprimento máximo da representação das chaves na base b
Ordenação por Distribuição
A primeira iteração destaca, em cada nó, o dígito menos significativo da representação b-ária de cada chave. Se este for igual a k, a chave correspondente será inserida na fila Fk.
Ao terminar o percurso da tabela, esta se encontra distribuída pelas filas, que devem então ser concatenadas em sequência, isto é, F0, F1, F2, ..., Fn-1
Para esta tabela, já disposta numa ordem diferente da original, o processo deve ser repetido levando-se em consideração o segundo dígito da representação, e assim sucessivamente.
Ordenação por Distribuição: b=10 e d=2
Ordenação por Distribuição: b=10 e d=2
Algorítmo de Ordenação por distribuição
A notação Fk <= L[j] significa a inserção na fila Fk do elemento localizado em L[j]
L[j] <= Fk representa a remoção de um elemento da fila Fk e seu armazenamento em L[j]
A lista L contém os elementos a serem ordenados 
Supõe-se que as filas Fi tenham sido inicializadas como vazias
Algorítmo de Ordenação por distribuição