2 - 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 Faria 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
INTRODUÇÃO
Lista linear ou tabela agrupa informações referentes a um conjunto de elementos que, de alguma forma, se relacionam entre si.
Informações sobre funcionários de uma empresa
Informações sobre nota de compras
Itens de estoque
Notas de alunos
Podemos utilizar vários tipos de dados em uma lista linear
LISTA LINEAR OU TABELA
É um conjunto de n ≥ 0 nós L[1], L[2],..., L[n] tais que suas propriedades estruturais dependem da posição relativa dos nós dentro da sequência linear.
Se n > 0, L[1] é o primeiro nó e L[n] é o último nó
Para 1 < k ≤ n, o nó L[k] é precedido por L[k-1]
OPERAÇÕES
Operações mais frequentes em listas
Busca
Inclusão
Remoção de um determinado elemento
Os algoritmos que as implementem devem ser eficientes!
Outras operações
Alteração de um elemento da lista
Combinação de uma ou mais listas lineares em uma única
Ordenação dos nós segundo um determinado campo
Determinação do primeiro e último nó da lista
CASOS PARTICULARES DE LISTAS
Se as Inserções e remoções são permitidas apenas nas extremidades da listas: deque
Se as Inserções e remoções são permitidas em apenas uma extremidade: a lista é chamada de pilha
Se Inserções são permitidas em uma das extremidades e remoções na outra extremidade: fila
TIPO DE ARMAZENAMENTO
O tipo de armazenamento de uma lista linear pode ser classificado de acordo com a posição relativa (ao lado ou não) na memória de dois nós consecutivos na lista.
Casos:
1° - Alocação Sequencial de Memória
2° - Alocação Encadeada
O tipo de alocação a ser utilizado depende de:
Operações que serão executadas sobre a lista
Número de listas envolvidas na operação
Características particulares dessas listas
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 SEQÜENCIAL
Maneira mais simples de manter uma lista na memória do computador é colocar os nós da lista em posições lado a lado
O endereço real de (j+1) - ésimo elemento da lista se encontra a c unidades adiante do j-ésimo nó, onde c é o número de palavras que o cada nó ocupa
A correspondência entre índice da tabela e endereço real é feita automaticamente pela linguagem de programação
ALOCAÇÃO SEQÜENCIAL
Como a Implementação da alocação sequencial em linguagem de alto nível é realizada com reserva prévia de memória para cada estrutura utilizada, a inserção e a remoção de nós não ocorrem de fato;
 Em vez disso utiliza-se algum tipo de simulação para essas operações (exemplo: variáveis indicando os limites da memória realmente utilizada)
 Por isso a Alocação Sequencial é chamada Alocação Estática
Esse armazenamento sequencial é usado no caso de pilhas e filas porque nessas estruturas, as operações básicas são implementadas de forma eficiente
ALOCAÇÃO SEQÜENCIAL
Alocação Estática - Os dados tem tamanho fixo e estão organizados sequencialmente na memória do computador. Ex. variáveis globais
 Alocação Dinâmica – os dados não precisam ter um tamanho fixo pois pode-se definir para cada dado quanto de memória que desejamos utilizar, por isso vamos alocar espaços de memória (blocos) que não precisam necessariamente estar em forma sequencial, e podemos pedir para alocar/desalocar blocos de memória de acordo com nossa necessidade 
Para poder achar os blocos esparsos na memória usamos as variáveis do tipo ponteiro (indicadores de endereços de memória)
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 SEQUENCIAL
Seja uma lista linear. Cada nó da lista
é formado por campos: armazenam as características distintas dos elementos da lista
possui um identificador (chave)
devem ser distintas para evitar ambiguidade
A chave, quando presente, constitui em um dos campos do nó
LISTAS LINEARES EM ALOCAÇÃO SEQUENCIAL
Os nós da lista podem ser ordenados, ou não, segundo os valores de suas chaves (lista ordenada e não-ordenada)
Seja uma lista linear L com n elementos
Algoritmo 1
Neste algoritmo, para cada elemento, são realizados dois testes:
 i ≤ n e L[i].chave = x
 Apresenta a busca de um nó na lista L conhecendo-se sua chave 
 A variável x - a chave do nó procurado
 A função busca1, informa ao final o índice do nó procurado
Se este não for encontrado, o índice é nulo 
Outro exemplo de algoritmo de busca
A diferença entre os dois é a criação de um novo nó que possui o valor procurado no campo chave, na posição (n+1), assim o algoritmo sempre encontra um nó da tabela com as características desejadas eliminando o teste de final da lista.
Complexidade dos algoritmos de busca
A complexidade do pior caso dos algoritmos apresentamos é O(n), 
O segundo é de execução mais rápida pois no algoritmo 1 a cada iteração correspondem dois testes e no algoritmo 2 apenas um teste.
BUSCA BINÁRIA
Um algoritmo mais eficiente para busca em uma lista ordenada é a busca binária
 A idéia básica do algoritmo é percorrer a tabela como se folheia, por exemplo, uma lista telefônica abandonando as partes do catálogo onde o nome procurado não será encontrado
 Em tabelas, o primeiro nó a ser pesquisado é o que se encontra no meio
 Se a comparação não é positiva, metade da tabela pode ser abandonada na busca pois o valor procurado se encontra ou na metade inferior ou na metade superior.
BUSCA BINÁRIA
BUSCA BINÁRIA – Complexidade do Algoritmo
O pior caso ocorre quando o elemento procurado é o último a ser encontrado ou não é encontrado
A busca prossegue até que a tabela se resuma a um único elemento
Na primeira iteração a dimensão da tabela é n
Na segunda, a dimensão se reduz a n/2
Ao final, a dimensão da tabela é 1
BUSCA BINÁRIA – Complexidade do Algoritmo
1ª. Iteração: a dimensão da tabela é n
2ª. Iteração: a dimensão da tabela é 
3ª. Iteração: a dimensão da tabela é
.....
ma. iteração: a dimensão da tabela é 1
O número de iterações é, no máximo, 
A complexidade da busca binária é O(log n)
INSERÇÃO E REMOÇÃO
Ambas as operações utilizam o procedimento de busca
Inserção: evitar chaves repetidas
Remoção: localizar o nó a ser removido
Algoritmo de inserção: inserção de um nó contido na variável novo de chave x
Algoritmo de remoção: remove o nó com chave x
ALGORITMO DE INSERÇÃO
Inserção de um nó contido na variável novo da chave x.
ALGORITMO DE REMOÇÃO
Efetua a remoção de um nó sendo conhecido um de seus campos, no caso a chave x
CONSIDERAÇÕES PARA AMBOS ALGORITMOS
Listas não ordenadas
A memória disponível tem M posições
M+1 posições: procedimento de busca
Indicação de overflow: inserir elementos em uma lista cheia
Indicação de underflow: remover elementos de uma lista vazia
CONSIDERAÇÕES
A complexidade de ambos algoritmos (inserção e remoção) é O(n)
O algoritmo de inserção é simples, porém depende da busca que tem complexidade O(n)
O algoritmo de remoção, além da busca, em geral efetua movimentação de nós, tornando ainda mais lento
CONSIDERAÇÕES
Uma alternativa para o algoritmo de remoção é efetuar o deslocamento do último elemento da lista para a posição vaga -> sequencia fica alterada
A utilização da busca binária diminui a complexidade da busca, mas não a da inserção ou da remoção. A complexidade dessas operações é determinada pela movimentação dos nós.
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
PILHA
Em geral o armazenamento sequencial de listas é empregado quando as estruturas ao longo do tempo sofrem poucas remoções
e inserções.
Na alocação sequencial de listas genéricas, considera-se sempre a primeira posição da lista no endereço 1 da memória disponível
PILHA
Uma alternativa é a utilização de indicadores especiais (ponteiros) para o acesso a posições selecionadas.
No caso da pilha, apenas um ponteiro precisa ser considerado, o ponteiro topo pois as inserções e remoções são executadas nas extremidades da lista.
Sequencias de operações realizadas numa pilha
Pilha vazia
Topo nulo
PILHA - ALGORÍTMOS
Inserção na Pilha
Remoção da Pilha
Memória disponível
FILA
As filas exigem uma implementação mais elaborada
São necessários dois ponteiros:
Início de fila – f
Retaguarda – r
Para a adição de um elemento: move-se o r
Para a remoção de um elemento: move-se o f
Fila vazia é quando f = r = 0
Após qualquer operação, o ponteiro f sempre tem que ficar indicando o início da fila, e r a retaguarda.
FILA
FILA
A medida que operamos com a fila, sem que haja o seu esvaziamento total, os ponteiros vão sendo incrementados até atingir a última posição de memória disponível.
Quando o ponteiro r atingir a última posição F[M], este poderá saltar para a primeira posição F[1], como em um círculo, caso o ponteiro f não esteja na primeira posição, condição esta que deverá ser detectada como fila cheia.
No algoritmo de inserção, a variável prov armazena temporariamente a posição de memória calculada
Algoritmo de inserção
A variável prov armazena provisoriamente a posição de memória, só sendo movimentado o ponteiro r se a operação for possível
 A inicialização dos ponteiros f e r é f = r = 0
Algoritmo de remoção
Remoção da Fila
FILA - CONSIDERAÇÕES
Os dois ponteiros f e r são inicializados com o valor 0
Nos dois casos (inserção e remoção) podemos considerar como sendo operações com complexidade constante
Em toda inserção na qual o ponteiro r for se deslocar e esta nova posição já estiver sendo ocupada pelo ponteiro f, teremos uma condição de overflow
Seja 1, 2, ..., n uma sequência de elementos que serão inseridos e posteriormente retirados de uma pilha P uma vez cada. A ordem de inclusão dos elementos é 1, 2, ..., n, enquanto a de remoção depende das realizações feitas. 
Ex. n=3, a sequência de operações
Incluir em P -> Incluir em P -> Retirar de P -> Incluir em P -> 
-> Retirar de P -> Retirar de P
produzirá a permutação 2, 3, 1 a partir da entrada 1, 2, 3. Representando por I, R, respectivamente as operações de inserção e remoção da pilha, a permutação 2, 3, 1 pode ser denotada por IIRIRR. 
De um modo geral, uma permutação é chamada admissível quando ela puder ser obtida mediante uma sucessão de inclusões e remoções em uma pilha a partir da permutação 1, 2, ..., n. Assim, por exemplo, a permutação 2, 3, 1 é admissível. Pede-se:
Determinar a permutação correspondente a IIIRRIRR, n=4
Dar um exemplo de permutação não admissível
DEQUE
Criar um algoritmo para as seguintes operações em uma estrutura de dados do tipo DEQUE
Inserir_inicio(x): insere o elemento x no início do deque. Retorna overflow, caso o deque esteja cheio
Inserir_fim(x): insere o elemento x no final do deque. Retorna overflow, caso o deque esteja cheio
Remover_inicio(): remove o elemento no início do deque. Retorna underflow, caso não tenha mais elementos nesta extremidade
Remover_fim(): remove o elemento no final do deque. Retorna underflow, caso não tenha mais elementos nesta extremidade
EXERCÍCIO
Uma palavra é um palíndromo se a sequência de letras que a forma é a mesma, quer seja lida da esquerda para a direita ou a direita para a esquerda. 
Escrever um algoritmo para reconhecer se uma dada palavra é um palíndromo. Escolher a estrutura de dados conveniente para representar a palavra.