Lista_Linear_Duplamente_Encadeada

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

AULA 3
LISTA LINEAR
 
Estrutura de Dados
Listas lineares
Listas lineares 	encadeadas
 Ordem dos nodos da lista definida por informação contido em cada nodo
 Ordem independe da posição física dos nodos
 contiguidade lógica dos nodos na LL
Campo de elo
 contido em cada nodo
 informa qual o próximo nodo da lista
LL encadeada
LL encadeada
LL encadeada
Requisitos para LL encadeada
 Ponteiro para o primeiro nodo da lista
 Encadeamento entre os nodos através de campo de elo
 Indicação de final de lista
PtLista
Info Elo
Nodo genérico
LL encadeada
Operações básicas
 Criar e inicializar uma lista
 Inserir novo nodo
 Remover um nodo
 Acessar um nodo
 Destruir lista
Algoritmos
Tipos de dados utilizados nos algoritmos:
TipoPtNodo = TipoNodo
TipoNodo = registro
 Info: TipoInfoNodo
 Elo : TipoPtNodo
 fim registro
LL encadeada
Criação de LL encadeada
 Inicializar apontador do início da lista em endereço nulo
 Lista inicialmente vazia
PtLista
Endereço nulo
Algoritmo: 
Inicializar LL Encadeada
Algoritmo InicializarLLEnc 
 Entradas: -
 Saída: PtLista (TipoPtNodo)
início
 PtLista  nulo
fim 
LL encadeada
LL encadeada
Inserção de um novo nodo
 Alocar o novo nodo
 Preencher com valor
 Encadear na posição solicitada
 No início da lista (primeiro nodo)
 No final da lista (último nodo)
 No meio da lista
PtLista
L2
L4
L3
PtLista
L1
Novo nodo
LL encadeada
Inserção no início de LL encadeada
Algoritmo InserirIniLLEnc
 Entradas: PtLista (TipoPtNodo)
 Dados (TipoInfoNodo)
 Saídas: PtLista (TipoPtNodo)
 Sucesso (lógico)
 Variável auxiliar: Pt (TipoPtNodo)
início
 alocar(Pt)
 se Pt = nulo 
 então Sucesso  falso 
 senão início 
 Sucesso  verdadeiro
 Pt.Info  Dados
 Pt.Elo  PtLista 
 PtLista  Pt
 fim
fim 
Algoritmo: 
Inserir nodo Início de LL Encadeada
LL encadeada
Algoritmo: 
Inserir nodo Início de LL Encadeada
LL encadeada
PASCAL
Function InserirIniLLEnc 
 (var PtLista: TipoPtNodo; Dados: TipoInfoNodo): boolean;
var Pt: TipoPtNodo;
begin
 new(Pt);
 if Pt = nil 
 then InserirIniLLEnc := false 
 else begin 
 Pt^.Info := Dados;
 Pt^.Elo := PtLista; 
 PtLista := Pt;
 InserirIniLLEnc := true;
 end;
end;
LL encadeada
Inserção no final de LL encadeada
PtLista
L2
L4
L3
PtLista
L1
Novo nodo
Percorrer a lista a partir do primeiro nodo até o final
Algoritmo InserirFimLLEnc 
 Entradas: PtLista (TipoPtNodo)
 Dados (TipoInfoNodo)
 Saídas: PtLista (TipoPtNodo)
 Sucesso (lógico)
 Variáveis auxiliares: P1, P2 (TipoPtNodo)
início
 alocar(P1)
 se P1 = nulo
 então Sucesso  falso
 senão início
 Sucesso  verdadeiro
 P1.Info  Dados
 P1.Elo  nulo
 se PtLista = nulo
 então PtLista  P1 
 senão início
 P2  PtLista
 enquanto P2.Elo  nulo
 faça P2  P2.Elo
 P2.Elo  P1
 fim
 fim
fim 
Algoritmo: 
Inserir nodo no Fim de LL Encadeada
LL encadeada
LL encadeada
Inserção no meio de LL encadeada
L1
L3
L2
L1
L2
L4
L3
PtLista
PtLista
 Novo nodo
Percorrer a lista a partir do primeiro nodo até a posição de inserção
Algoritmo InserirKLLEnc
 Entradas: PtLista (TipoPtNodo)	
 K (inteiro)		
 Dados (TipoInfoNodo) 
 Saídas: PtLista (TipoPtNodo)
 Sucesso (lógico)
 Variáveis auxiliares: PAnt, PtNovo (TipoPtNodo)
início
 alocar(PtNovo)
 se PtNovo = nulo
 então Sucesso  falso
 senão se ((PtLista = nulo) e (K  1)) ou (K < 1)
 então início
 liberar(PtNovo)
 Sucesso  falso
 fim
 senão se K = 1
 então início 
 PtNovo.Info  Dados
 PtNovo.Elo  PtLista
 PtLista  PtNovo
 Sucesso  verdadeiro
 fim
 { senão início SEGUE }
Algoritmo: Inserir nodo na K-ésima posição de LL Encadeada
 senão início
 PtAnt  PtLista
 enquanto (PtAnt.Elo  nulo) e (K > 2)
 faça início
 PtAnt  PtAnt.Elo
 K  K - 1
 fim
 se K > 2
 então início
 liberar(PtNovo)
 Sucesso  falso
 fim
 senão início
 PtNovo.Info  Dados
 PtNovo.Elo  PtAnt.Elo
 PtAnt.Elo  PtNovo
 Sucesso  verdadeiro
 fim
 fim
fim 
Algoritmo (cont): 
Inserir nodo na K-ésima posição de LL Encadeada
LL encadeada
Remoção de um nodo
 Localizar o nodo a ser removido
 Atualizar encadeamento da lista
 Liberar espaço ocupado pelo nodo
 Se for o último nodo da lista  lista fica vazia
 Atualizar apontador da lista para endereço nulo
LL encadeada
Remoção de um nodo
L1
L2
L4
L3
PtLista
L1
L2
L3
PtLista
Nodo a ser removido
Algoritmo RemoverKLLEnc 
 Entradas: PtLista (TipoPtNodo)
 K (inteiro) 
 Saídas: PtLista (TipoPtNodo)
 Sucesso (lógico)
 Variáveis auxiliares: PtAnt, PtK (TipoPtNodo)
início
 se K < 1 
 então Sucesso  falso
 senão início
 PtK  PtLista
 PtAnt  nulo
 enquanto (PtK  nulo) e (K > 1)
 faça início
 K  K-1
 PtAnt  PtK
 PtK  PtK.Elo
 fim
 se PtK = nulo
 então Sucesso  falso
 senão início
 se PtK = PtLista
 então PtLista  PtLista.Elo
 senão PtAnt.Elo  PtK.Elo 
 liberar(PtK)
 Sucesso  verdadeiro
fim fim fim
Algoritmo: Remover nodo da K-ésima posição de LL Encadeada
LL encadeada
Acesso a um nodo
 Nodos não podem ser acessados diretamente
 Percorrer a lista até encontrar o nodo buscado
 Nodo identificado por 
 sua posição na lista
 conteúdo
Algoritmo: Acessar K-ésimo nodo de LL Encadeada
Algoritmo AcessarKLLEnc 
 Entradas: PtLista (TipoPtNodo)
 K (inteiro)
 Saída: PtK (TipoPtNodo)
início
 se (K < 1) ou (PtLista = nulo)
 então PtK  nulo
 senão início
 PtK  PtLista
 enquanto (PtK  nulo) e (K > 1)
 faça início
 K  K-1
 PtK  PtK.Elo
 fim
 se K > 1
 então PtK  nulo
 fim
 fim 
LL encadeada
Destruir lista
 Percorrer lista a partir do primeiro nodo
 Liberar todos os nodos da lista
 Apontador para início da lista recebe endereço nulo
Algoritmo: 
Destruir LL Encadeada
Algoritmo DestruirLLEnc 
 Entrada: PtLista (TipoPtNodo)
 Saída: PtLista (TipoPtNodo)
 Variável auxiliar: Pt (TipoPtNodo)
begin
 enquanto PtLista  nulo
 faça início
 Pt  PtLista
 PtLista  PtLista.Elo
 liberar(Pt)
 fim
 liberar(PtLista)
fim 
LL encadeada
Listas lineares
Lista encadeada circular
LL encadeada circular
LL encadeada circular
L1
L2
L4
L3
PtLista
 Elo do último nodo indica endereço do primeiro
 Lista pode ser percorrida a partir de qualquer nodo
 Lista com 1 só nodo: elo do nodo aponta para ele mesmo
L1
PtLista
LL encadeada circular
Operações básicas
 Criar uma lista
 Inserir novo nodo
 Remover um nodo
 Acessar um nodo
 Destruir lista
Algoritmos
Semelhantes a LL encadeada simples
Inserção de um novo nodo
 Localizar posição de inserção
 Alocar o novo nodo
 Preencher com valor
 Encadear adequadamente
LL encadeada circular
L1
L2
L4
L3
PtLista
L5
Algoritmo InserirKLLEncCir 
 Entradas: PtLista (TipoPtNodo)
 K (inteiro)
 Dados (TipoInfoNodo)
 Saídas: PtLista (TipoPtNodo)
 Sucesso (lógico)
 Variáveis auxiliares: PtAnt, PtNovo (TipoPtNodo)
início
 alocar(PtNovo)
 se PtNovo = nulo
 então Sucesso  falso
 senão se ((PtLista = nulo) e (K
 1)) ou (K < 1)
 então início
 liberar(PtNovo)
 Sucesso  falso
 fim
 senão início
 Sucesso  verdadeiro
 PtNovo.Info  Dados
 se K = 1 {INSERE COMO PRIMEIRO}
 { então início SEGUE }
Algoritmo: 
Inserir K-ésimo nodo em LL Encadeada Circular
LL encadeada circular
 então início
 se PtLista = nulo 
 então PtNovo.Elo  PtNovo
 senão início
 PtAnt  PtLista
 enquanto PtAnt.Elo  PtLista
 faça PtAnt  PtAnt.Elo
 PtNovo.Elo  PtLista
 PtAnt.Elo  PtNovo
 fim
 PtLista  PtNovo
 fim
 senão início
 PtAnt  PtLista
 enquanto (PtAnt.Elo  PtLista) e (K > 2)
 faça início
 PtAnt  PtAnt.Elo
 K  K - 1
 fim
 se K > 2 {ORDEM FORA DA LISTA}
 então início
 liberar(PtNovo)
 Sucesso  falso
 fim
 senão início
 PtNovo.Info  Dados {INSERE NO MEIO}
 PtNovo.Elo  PtAnt.Elo
 PtAnt.Elo  PtNovo
fim fim fim fim
Algoritmo (cont): Inserir K-ésimo nodo em LL Encadeada Circular
Remoção de um nodo
LL encadeada circular
L1
L2
L4
L3
PtLista
L1
L2
L3
PtLista
Remover
 Localizar posição do nodo
 Adequar encadeamentos
 Liberar nodo
Algoritmo RemoverKLLEncCir 
 Entradas: PtLista (TipoPtNodo)
 K (inteiro)
 Saídas: PtLista (TipoPtNodo)
 Sucesso (lógico)
 Variáveis auxiliares: PtAnt, PtK (TipoPtNodo)
início
 se (K < 1) ou (PtLista = nulo)
 então Sucesso  falso
 senão início
 Sucesso  verdadeiro
 se K = 1		
 então se PtLista.Elo = PtLista
 então início
 liberar(PtLista)
 PtLista  nulo
 fim
 senão início
 PtAnt  PtLista
 enquanto PtAnt.Elo  PtLista
 faça PtAnt  PtAnt.Elo
 PtAnt.Elo  PtLista.Elo
 liberar(PtLista)
 PtLista  PtAnt.Elo
 fim
 { senão início SEGUE } 
Algoritmo: Remover K-ésimo nodo de LL Encadeada Circular
 senão início
 PtAnt  PtLista
 enquanto (PtAnt.Elo  PtLista) e (K > 2)
 faça início
 PtAnt  PtAnt.Elo
 K  K - 1
 fim
 se PtAnt.Elo = PtLista {ORDEM FORA DA LISTA}
 então Sucesso  falso
 senão início
 PtK  PtAnt.Elo
 PtAnt.Elo  PtK.Elo
 liberar(PtK)
 fim
 fim
 fim
fim 
Algoritmo (cont): Remover K-ésimo nodo de LL Encadeada Circular
LL encadeada circular
Acesso à lista
LL encadeada circular
 Iniciar sempre acessando primeiro nodo da lista
 Seguir acessando de acordo com campos de elo
 Para quando encontrar novamente o primeiro nodo da lista
L1
L2
L4
L3
PtLista
L5
 A seguir: algoritmo que acessa todos os nodos de uma LL encadeada circular, imprimindo o campo de informação de todos os nodos acessados 
 
Algoritmo ImprimirLLEncCir 
 Entrada: PtLista (TipoPtNodo)
 Saídas: -
 Variável auxiliar: PtAux (TipoPtNodo)
início
 se PtLista = nulo
 então escrever(´Lista vazia!´)
 senão início
 PtAux  PtLista
 repita 
 escrever(PtAux.Info)
 PtAux  PtAux.Elo
 até que PtAux = PtLista 
 fim
fim 
Algoritmo: 
Imprimir conteúdos de LL Encadeada Circular
LL encadeada circular
LL encadeada circular
Listas lineares
Listas lineares duplamente encadeadas
LL duplamente encadeadas
PtLista
L1
L2
L3
L4
 Cada nodo tem 2 campos de elo
 A lista pode ser percorrida nas duas direções
LL duplamente encadeadas
Anterior Info Próximo
Nodo genérico
LL duplamente encadeadas
Operações
 Criar e inicializar uma lista
 Inserir novo nodo
 Remover um nodo
 Acessar um nodo
 Destruir lista
Algoritmos
Semelhantes a LL encadeada simples
Tipo de nodo utilizado nos algoritmos:
TipoNodo = registro
 Ant: TipoPtNodo
 Info: TipoInfoNodo
 Prox: TipoPtNodo
	 fim registro
LL duplamente encadeadas
Inserção de um novo nodo
PtLista
PtLista
 Novo nodo
L1
L2
L3
L4
L4
L5
L2
L1
L3
Algoritmo InserirKLLDupEnc 
 Entradas: PtLista (TipoPtNodo) 
 K (inteiro) 
 Dados (TipoInfoNodo)
 Saídas: PtLista (TipoPtNodo)
 Sucesso (lógico)
 Variáveis auxiliares: PtAnt, PtNovo (TipoPtNodo)
início
 alocar(PtNovo)
 se PtNovo = nulo
 então Sucesso  falso
 senão se ((PtLista = nulo) e (K  1)) ou (K < 1)
 então início
 liberar(PtNovo)
 Sucesso  falso
 fim
 senão se K = 1
 então início 
 PtNovo.Info  Dados
 PtNovo.Prox  PtLista
 se PtLista <> nulo
 então PtLista.Ant  PtNovo
 PtNovo.Ant  nulo
 PtLista  PtNovo
 Sucesso  verdadeiro
 fim
 { senão início SEGUE }
Algoritmo: Inserir K-ésimo nodo em LL Duplamente Encadeada
 senão início
 PtAnt  PtLista
 enquanto (PtAnt.Prox  nulo) e (K > 2)
 faça início
 PtAnt  PtAnt.Prox
 K  K - 1
 fim
 se K > 2
 então início
 liberar(PtNovo)
 Sucesso  falso
 fim
 senão início
 PtNovo.Info  Dados
 PtNovo.Prox  PtAnt.Prox
 PtNovo.Ant  PtAnt
 PtAnt.Prox  PtNovo
 if PtNovo.Prox <> nulo
 then PtNovo.Prox.Ant  PtNovo
 Sucesso  verdadeiro
 fim
 fim
fim 
Algoritmo (cont): Inserir K-ésimo nodo em LL Duplamente Encadeada
LL duplamente encadeadas
Remoção de novo nodo
A
B
PtLista
C
D
A
B
PtLista
C
D
Remover
Algoritmo RemoverKLLDupEnc 
 Entradas: PtLista (TipoPtNodo) Saídas: PtLista (TipoPtNodo)
 K (inteiro) Sucesso (lógico)
 Variável auxiliar: PtK (TipoPtNodo)
início
 se ((PtLista = nulo) e (K  1)) ou (K < 1) 
 então Sucesso  falso
 senão início
 PtK  PtLista
 enquanto (PtK  nulo) e (K > 1)
 faça início
 K  K-1
 PtK  PtK.Prox
 fim
 se PtK = nulo
 então Sucesso  falso
 senão início
 Sucesso  verdadeiro
 se PtK = PtLista
 então início
 PtLista.Ant  nulo
 PtLista  PtLista.Prox
 fim
 senão início
 PtK.Ant.Prox  PtK.Prox
 se PtK.Prox <> nulo
 então PtK.Prox.Ant  PtK.Ant
 liberar(PtK)
fim fim fim fim
Algoritmo: Remover K-ésimo nodo em LL Duplamente Encadeada
LL duplamente encadeadas
Acesso à lista
 Acesso sempre pelo primeiro nodo da lista
 Depois a lista pode ser percorrida nas duas direções
 Exemplo a seguir: 
Imprimir conteúdo da lista, do final para o início
Algoritmo ImprimirLLDupEncInv 
 Entrada: PtLista (TipoPtNodo)
 Saídas: -
 Variável
auxiliar: PtAux (TipoPtNodo)
início
 se PtLista = nulo
 então escrever(´Lista vazia !´)
 senão início
 PtAux  PtLista
 enquanto PtAux.Prox  nulo 
 faça PtAuxPtAux.Prox 
 enquanto PtAux  PtLista
 faça início
 escrever(PtAux.Info)
 PtAux  PtAux.Ant
 fim
 escrever(PtAux.Info) 
 fim
fim 
Algoritmo: 
Imprimir LL Duplamente Encadeada em ordem Invertida
LL duplamente encadeadas
Listas lineares
Lista duplamente encadeada circular
LL duplamente encadeada circular
Lista duplamente encadeada circular
PtLista
L1
L2
L3
L4
Operações
 Criar uma lista
 Inserir novo nodo
 Remover um nodo
 Acessar um nodo
 Destruir lista
Algoritmos
Semelhantes a LL encadeada simples
LL duplamente encadeada circular
PtLista
L1
L2
L3
L4
Inserção de um novo nodo
LL duplamente encadeada circular
PtLista
No início
No final
PtLista
L2
L3
L4
L5
L1
PtLista
L2
L3
L4
L5
L1
LL duplamente encadeada circular
No meio – 3ª posição
PtLista
L2
L3
L4
L5
L1
PtLista
L1
L2
L3
L4
Inserção de um novo nodo
PtLista
Algoritmo InserirFimLLDupEncCir 
 Entradas: PtLista (TipoPtNodo)
 Dados (TipoInfoNodo)
 Saídas: PtLista (TipoPtNodo)
 Sucesso (lógico)
 Variável auxiliar: PtNovo (TipoPtNodo)
início
 alocar(PtNovo)
 se PtNovo = nulo
 então Sucesso  falso
 senão início
 Sucesso  verdadeiro 
 PtNovo.Info  Dados
 se PtLista = nulo
 então início 
 PtNovo.Prox  PtNovo
 PtNovo.Ant  PtNovo
 PtLista  PtNovo
 fim
 senão início
 Ptnovo.Ant  PtLista.Ant
 PtNovo.Prox  PtLista
 PtLista.Ant.Prox  PtNovo
 PtLista.Ant  PtNovo
fim fim fim
Algoritmo: Inserir um nodo no Final de LL Duplamente 
Encadeada Circular
Remoção de um nodo
LL duplamente encadeada circular
PtLista
L1
L2
L3
L4
Remover 2º nodo
PtLista
L1
L2
L3
L1
L2
L3
L4
PtLista
Algoritmo: Remover um nodo no Final de LL Duplamente 
Encadeada Circular
Algoritmo RemoverUltLLDupEncCir 
 Entradas: PtLista (TipoPtNodo)
 Saídas: PtLista (TipoPtNodo)
 Sucesso (lógico)
 Variável auxiliar: PtAux (TipoPtNodo)
início
 se PtLista = nulo
 então Sucesso  falso
 senão início
 Sucesso  verdadeiro
 PtAux  PtLista.Ant
 se PtLista.Prox = PtLista 
 então PtLista  nulo
 senão início
 PtLista.Ant  PtAux.Ant
 PtAux.Ant.Prox  PtLista
 fim
 liberar(PtAux)
 fim
fim 
*
Quando desejamos resolver um problema através de um programa utilizando o computador a primeira providência que devemos tomar é a de elaborar o algoritmo mais adequado para o programa. Para cada programa desenvolvido na disciplina de algoritmos vocês conceberam um algoritmo antes de implementar o mesmo.
A eficiência do algoritmo vai depender da disposição dos dados, ou elementos que servem de base para a resolução do problema, na memória. Quando maior for a facilidade o computador achar na memória estes dados, maior será a eficiência do programa.
Para entender a relação entre eficiência e algoritmo vamos ver o exemplo da agenda telefônica. Supondo que freqüentemente utilizamos a agenda telefônica para descobrir o número de telefone de nossos conhecidos, é conveniente dispor de uma relação dos números, organizada na agenda. Se a organização for feita por ordem alfabética, a agenda de fato ajuda. Se, porém, organizássemos nossa agenda pela ordem de altura das pessoas, com raras exceções, a agenda se tornaria difícil de manusear.
Se soubermos organizar a nossa agenda de forma a tornar a busca de um número de telefone bastante facilitada, então, estaremos executando a tarefa de busca de forma eficiente.