Lista_Linear_II

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

LISTA LINEAR
(parte II)
 
Estrutura de Dados
Listas lineares
LL implementadas por contiguidade física com descritor
Descritor contém diversas informações sobre a lista linear :
 localização da lista na arranjo (índices)
 acesso – índice de alguns nodos
 estrutura da lista, como número de nodos
 conteúdo
 ...
6
7
8
9
10
3
4
5
1
2
11
12
13
4
2
5
1
7
9
6
7
4
3
8
LL – contiguidade física com descritor
Decritor de uma LL 
Descritor
1
2
4
3
7
6
9
10
LL
7
9
2
 5
 1
4
5
8
2
1
5
4
3
8
6
 7
 4
3
Comprimento da lista
Último nodo
Primeiro nodo
Nodo com menor valor
Nodo com maior valor
DescrLL
LL – contiguidade física com descritor
Exemplo de descritor
LL – contiguidade física com descritor
Acesso a LL com descritor
TipoNodo = registro
 Valor: inteiro
 Info: TipoInfo
 fim registro 
 Sempre através das informações contidas no descritor
LL[DescrLL [1]].Info – informação contida no primeiro nodo da lista
LL[DescrLL [2]].Valor – Valor contido no último nodo da lista
LL[DescrLL [5]].Valor – maior Valor contido na lista
DescrLL [3] – comprimento da lista. A informação está contida diretamente no descritor, não sendo necessário percorrer a lista para obter seu comprimento
2
1
5
4
3
8
6
 7
 4
3
Comprimento da lista
Último nodo
Primeiro nodo
Nodo com menor valor
Nodo com maior valor
DescrLL
TipoDescritor = 
 arranjo [1..5] de inteiros
Ex 1:
LL – contiguidade física com descritor
Acesso a LL com descritor
TipoNodo = registro
 Valor: inteiro
 Info: TipoInfo
 fim registro 
LL[DL.IL].Info – informação contida no primeiro nodo da lista;
LL[DL.FL].Valor – Valor contido no último nodo da lista;
DL.MaiorValor – maior valor contido no campo Valor de todos os nodos da lista. 
FL
IL
3
8
4
MaiorValor
Índice do maior valor da lista
Final da lista
Início da lista
DescrLL
TipoDescritor = 
 registro
 IL: inteiro
 FL: inteiro
 MaiorValor: inteiro
 fim registro
Ex 2:
6
7
8
9
10
3
4
5
1
2
11
12
13
4
2
5
1
7
9
LL – contiguidade física com descritor
Descritor utilizado nos algoritmos
TipoDescr = registro
 IA : inteiro
 IL : inteiro
 N : inteiro
 FL : inteiro
 FA : inteiro
 fim registro
IL
IA
FA
FL
1
3
6
 8
 13
N
Comprimento da lista
Início da lista
Início do arranjo
Final da lista
Final do arranjo
DescrLL
6
7
8
9
10
3
4
5
1
2
11
12
13
4
2
5
1
7
9
Descritor informando espaço disponível para a lista no arranjo
IA
IL
N
FA
FL
6
X
DLista
LL – contiguidade física com descritor
9
IA
IL
N
FA
FL
18
20
5
24
24
10
11
4
17
14
14
15
16
17
18
11
12
13
10
19
20
21
Duas LL implementadas sobre o mesmo arranjo, com descritores
IA
IL
N
FA
FL
22
23
24
25
26
27
Espaço para L1
Espaço para L2
LL – contiguidade física com descritor
 Inicializar lista
 Inserir nodo (início / meio / final)
 Remover nodo (início / meio / final)
 Localizar determinado nodo
Algoritmos para operações em LL com descritores - contigüidade física
LL – contiguidade física com descritor
LL – contiguidade física com descritor
Criação de LL vazia com descritor
11
12
14
13
17
16
19
20
LL
15
18
IL
IA
FA
FL
11
0
0
 0
 20
N
DL
IL
IA
FA
FL
11
10
0
 10
 20
N
DL
(Opção 1)
(Opção 2)
2 estratégias
LL – contiguidade física com descritor
Algoritmo: 
Inicializar LL sobre Arranjo com Descritor
Algoritmo InicLLArrDescr 
 Entradas: DL (TipoDescr)
 IniArea, FimArea (inteiro)
 Saída: DL (TipoDescr)
início
 DL.IL  0
 DL.FL  0
 DL.N  0
 DL.IA  IniArea
 DL.FA  FimArea
fim 
IA
IL
N
FA
FL
23
11
13
18
6
Inserir novo nodo
LL com descritor - contigüidade física
No início
16
17
18
19
20
13
14
15
11
12
21
22
23
A
No final
LL – contiguidade física com descritor
LL – contiguidade física com descritor
Inserção no início da lista
IL
IA
FA
FL
1
3
4
 6
 10
N
DL
1
2
4
3
7
6
9
10
LL
 
 
5
8
IL
IA
FA
FL
1
2
5
 6
 10
N
DL
1
2
4
3
7
6
9
10
LL
 
 
5
8
Inserir
no início
Novo nodo
Valores alterados 
no descritor
LL – contiguidade física com descritor
Inserção no início com deslocamento
IL
IA
FA
FL
1
1
5
 5
 10
N
DL
1
2
4
3
7
6
9
10
LL
 
 
5
8
IL
IA
FA
FL
1
6
 6
 10
N
DL
1
2
4
3
7
6
9
10
LL
 
 
5
8
1
Inserir
no início
Novo nodo
Valores alterados 
no descritor
LL – contiguidade física com descritor
Inserção no final da lista
IL
IA
FA
FL
1
3
4
 6
 10
N
DL
1
2
4
3
7
6
9
10
LL
 
 
5
8
IL
IA
FA
FL
1
3
5
 7
 10
N
DL
1
2
4
3
7
6
9
10
LL
 
 
5
8
Inserir
no final
Novo nodo
Valores alterados 
no descritor
LL – contiguidade física com descritor
Inserção no final com deslocamento
IL
IA
FA
FL
1
6
5
 10
 10
N
DL
1
2
4
3
7
6
9
10
LL
 
 
5
8
IL
IA
FA
FL
5
6
 10
 10
N
DL
1
2
4
3
7
6
9
10
LL
 
 
5
8
1
Inserir
no final
Novo nodo
Valores alterados 
no descritor
LL – contiguidade física com descritor
Inserção no meio da lista
IL
IA
FA
FL
1
3
5
 7
 10
N
DL
1
2
4
3
7
6
9
10
LL
 
 
5
8
IL
IA
FA
FL
3
6
 8
 10
N
DL
1
2
4
3
7
6
9
10
LL
 
 
5
8
1
Inserir
como 3º nodo
Novo nodo
Valores alterados 
no descritor
FL = FA  deslocar para frente
Algoritmo: Insere em LL sobre Arranjo com Descritor na posição K
Algoritmo InserirLLArrDesc 
 Entradas: LL (TipoLista) Saídas: LL (TipoLista)
 DL (TipoDescr) DL (TipoDescr)
 Pos (inteiro) Info (TipoNodo) 
 Variáveis auxiliares: Sucesso (lógico)
 K (inteiro)
 IndPos (inteiro)
início
 se (DL.N = DL.FA-DL.IA+1) ou (Pos > DL.N+1) ou (Pos < 1) 
 então Sucesso  falso
 senão início 
 Sucesso  verdadeiro
 DL.N  DL.N + 1
 se Pos = 1 {INSERIR NO INÍCIO}
 então início 
 se DL.N = 1
 então início
 DL.IL  (DL.FA-DL.IA+1) div 2
 DL.FL  DL.IL
 fim
 senão se DL.IL > DL.IA
 então DL.IL  DL.IL-1 
 senão início 
 para K de DL.FL até DL.IL incr-1 faça
 LL[K+1]  LL[K]
 DL.FL  DL.FL+1
 fim
 LL[DL.IL]  Info
 fim
 { senão se Pos = DL.N {INSERIR COMO ÚLTIMO} SEGUE }
 senão se Pos = DL.N {INSERIR COMO ÚLTIMO}
 então início 
 se DL.FL < DL.FA
 então DL.FL  DL.FL+1
 senão início
 para K de DL.IL até DL.FL faça
 LL[K-1]  LL[K]
 DL.IL  DL.IL-1
 fim
 LL[DL.FL]  Info
 fim 
 senão início {INSERIR NO MEIO}
 se DL.FL < DL.FA
 então início
 IndPos  DL.IL+Pos-1
 para K de DL.FL até IndPos incr-1 faça
 LL[K+1]  LL[K]
 DL.FL  DL.FL+1
 fim
 senão início
 IndPos  DL.IL+Pos-2
 para K de DL.IL até IndPos faça 
 LL[K-1]  LL[K]
 DL.IL  DL.IL–1
 fim
 LL[IndPos]  Info
 fim
 fim 
fim 
Algoritmo (cont): Inicializa LL sobre Arranjo com Descritor
LL – contiguidade física com descritor
Remoção de um nodo
IA
IL
N
FA
FL
23
11
13
18
6
Deslocamento
OU
Inserção do início da LL
LL – contiguidade física com descritor
IL
IA
FA
FL
1
2
5
 6
 10
N
DL
1
2
4
3
7
6
9
10
LL
 
 
5
8
IL
IA
FA
FL
1
3
4
 6
 10
N
DL
1
2
4
3
7
6
9
10
LL
 
 
5
8
Remover
o primeiro
Valores alterados 
no descritor
LL – contiguidade física com descritor
Remoção do final da lista
IL
IA
FA
FL
1
3
4
 6
 10
N
DL
1
2
4
3
7
6
9
10
LL
 
 
5
8
IL
IA
FA
FL
1
3
3
 5
 10
N
DL
1
2
4
3
7
6
9
10
LL
 
 
5
8
Remover
o último
Valores alterados 
no descritor
LL – contiguidade física com descritor
Remoção no meio da lista
IL
IA
FA
FL
1
3
5
 7
 10
N
DL
1
2
4
3
7
6
9
10
LL
 
 
5
8
IL
IA
FA
FL
4
4
 7
 10
N
DL
1
2
4
3
7
6
9
10
LL
 
 
5
8
1
Remover
2º nodo
Valores alterados 
no descritor
LL – contiguidade física com descritor
Remoção resultando em LL vazia
IL
IA
FA
FL
1
4
1
 4
 10
N
DL
1
2
4
3
7
6
9
10
LL
 
 
5
8
IL
IA
FA
FL
0
0
 0
 10
N
DL
1
2
4
3
7
6
9
10
LL
 
 
5
8
1
Remover
nodo
Valores alterados 
no descritor
LL – contiguidade física com descritor
Algoritmo: 
Remover k-ésimo nodo de LL sobre Arranjo com Descritor
Algoritmo RemoverKLLArrDesc
 Entradas: LL (TipoLista)
 DL (TipoDescr)
 K (inteiro)
 Saídas: LL (TipoLista)
 DL (TipoDescr)
 Sucesso (lógico)
 Variável auxiliar: Ind (inteiro) 
início
 se (K  0) ou (K > DL.N) 
 então Sucesso  falso
 senão início
 Sucesso  verdadeiro
 para Ind de DL.IL+K-1 até DL.FL-1 faça
 LL[Ind]  LL[Ind+1]
 DL.FL  DL.FL-1
 DL.N  DL.N-1
 se DL.FL = DL.IL–1 
 então DL.IL  DL.FL  0
 fim
fim 
LL – contiguidade física com descritor
Acesso a um nodo da lista
Nodo identificado por:
 sua posição na lista – k-ésimo nodo
 campo de informação
LL – contiguidade física com descritor
Algoritmo: 
Acessar k-ésimo nodo de LL sobre Arranjo com Descritor
Algoritmo AcessarKLLArrDesc 
 Entradas: LL (TipoLista)
 DL (TipoDescr)
 K (inteiro)
 Saídas: InfoNodo (TipoNodo)
 Sucesso (lógico)
início
 se (K  0) ou (K > DL.FL-DL.IL+1) ou (DL.N = 0)
 então Sucesso  falso
 senão início
 InfoNodo  LL[DL.IL+K-1]
 Sucesso  verdadeiro
 fim
fim 
LL – contiguidade física com descritor
Algoritmo: 
Informar Posição do nodo com determinado Valor 
em LL sobre Arranjo com Descritor
Algoritmo PosValLLArrDesc 
 Entradas: LL (TipoLista)
 DL (TipoDescr)
 ValBuscado (TipoValor)
 Saída: Posição (inteiro)
 Variáveis auxiliares: 
 I (inteiro) 
 Achou (lógico)
início
 Achou  falso
 Posição  0
 I  DL.IL
 enquanto (I  DL.FL) e (não Achou)
 faça se LL[I].Valor = Val
 então início
 Posição  I
 Achou  verdadeiro
 fim
 senão I  I+1
fim 
Listas lineares
LL com ocupação circular do arranjo
LL – ocupação circular do arranjo
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L3
L4
L5
L6
L1
L2
5
8
Início da LL
Final da LL
LL com ocupação circular do arranjo
 Inicializar lista
 Inserir nodo (início / meio / final)
 Remover nodo (início / meio / final)
 Localizar determinado nodo
LL – ocupação circular do arranjo
Operações
Igual a quando não é feita a ocupação circular do arranjo
LL – ocupação circular do arranjo
Inserção de um novo nodo
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L3
L4
L5
L6
L1
L2
5
8
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L4
L5
L6
L7
L1
L2
L3
5
8
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L3
L4
L5
L6
L1
L2
5
8
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L3
L4
L5
L6
L7
L1
L2
5
8
No final
No início
LL – ocupação circular do arranjo
Inserção de um novo nodo
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L3
L4
L5
L6
L1
L2
5
8
1
2
4
3
7
6
9
10
LL
L3
L4
L5
L6
L7
L1
L2
5
8
IL
FL
IA
FA
Inserir como
5º nodo da LL
Novo nodo
No meio
Algoritmo InserirLLCirArrPosK 
 Entradas: LL (TipoLista) Saídas: LL (TipoLista)
 IA, FA, IL, FL (inteiro) IL, FL (inteiro)
 K (inteiro) Sucesso (lógico)
 InfoNodo (TipoNodo)
 Variáveis auxiliares: Ind, N, Pos (inteiro) 
início
 se IL = 0 {LISTA VAZIA}
 então N  0
 senão se IL  FL
 então N  FL-IL+1 
 senão N  (FA-IL+1) + (FL-IA+1)
 se (N = FA-IA+1) ou (K > N+1) ou (K < 1) ou (N=0 e K1) 
 então Sucesso  falso
 senão início	
 se (N = 0)
 então início {PRIMEIRO NODO}
 Pos  IA
 IL  FL  IA
 fim 
 senão início
 se (IL+K-1  FA)
 então Pos  IL+K-1
 senão Pos  (IA-1) + (K - (FA-IL+1))
 se K = 1 {INSERÇÃO NO INÍCIO}
 então se IL > IA
 então início 
 Pos  IL-1
 IL  IL-1
 fim
 senão início 
 IL  FA
 Pos  FA
 fim
 { senão se K = N+1 {INSERÇÃO NO FINAL} SEGUE}
Algoritmo: Inserir nodo na Posição K da LL Circular sobre Arranjo
 senão se K = N+1 {INSERÇÃO NO FINAL} 
 então se Pos = FL+1 
 então FL  FL+1
 senão FL  IA 
 senão {INSERÇÃO NO MEIO}
 se (IL  FL) e (FL < FA)
 ou (IL > FL) e (Pos < IL)
 então início
 para Ind de FL incr-1 até Pos faça
 LL[Ind+1]  LL[Ind]
 FL  FL+1
 fim
 senão início 
 se FL  FA
 então para Ind de FL incr-1 até IA
 faça LL[Ind+1]  LL[Ind] 
 LL[IA]  LL[FA]
 para Ind de FA-1 incr-1 até Pos
 faça LL[Ind+1]  LL[Ind]
 se FL = FA
 então FL  IA
 senão FL  FL+1
 fim fim
 LL[Pos]  InfoNodo 
 Sucesso  verdadeiro 	 
fim fim
Algoritmo (cont): Inserir nodo Posição K da LL Circular sobre Arranjo
LL – ocupação circular do arranjo
Remoção de um nodo
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L3
L4
L5
L6
L1
L2
5
8
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L2
L3
L4
57
L1
5
8
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L3
L4
L5
L6
L1
L2
5
8
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L3
L4
L5
L1
L2
5
8
No final
No início
LL – ocupação circular do arranjo
Remoção de um nodo
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L3
L4
L5
L6
L1
L2
5
8
1
2
4
3
7
6
9
10
LL
L3
L4
L5
L1
L2
5
8
IL
FL
IA
FA
Remover
4º nodo da LL
No meio
Algoritmo: Remover nodo da Posição K da LL Circular sobre Arranjo
Algoritmo RemoverKLLCirArr 
 Entradas: LL (TipoLista)
 IA, FA, IL, FL (inteiro)
 K (inteiro)
 InfoNodo (TipoNodo)
 Saídas: LL (TipoLista)
 IL, FL (inteiro)
 Sucesso (lógico)
 Variáveis auxiliares: Ind, N, Pos (inteiro) 
início
 se IL = 0 {LISTA VAZIA}
 então N  0
 senão se IL  FL
 então N  FL-IL+1 
 senão N  (FA-IL+1) + (FL-IA+1)
 se (N = 0) ou (K  0) ou (K > N) 
 então Sucesso  falso
 senão início 
 se N = 1 {REMOÇÃO DO ÚNICO}
 então IL  FL  0
 senão se K = 1 {REMOÇÃO DO PRIMEIRO}
 então se IL < FA
 então IL  IL+1
 senão IL  IA
 { senão se K = N {REMOÇÃO DO ÚLTIMO} SEGUE }
Algoritmo (cont): Remover nodo Posição K da LL Circular sobre Arranjo
 senão se K = N {REMOÇÃO DO ÚLTIMO}
 então se FL = IA
 então FL  FA
 senão FL  FL-1
 senão início {REMOÇÃO NO MEIO}
 se (IL+K-1  FA)
 então Pos  IL+K-1
 senão Pos  IA + (K - (FA-IL+1)-1)
 se (IL < FL) ou ((IL>FL) e (K>=FA-IL+2))
 então início
 para Ind de Pos até FL-1
faça LL[Ind]  LL[Ind+1]
 FL  FL-1
 fim
 senão início 
 para Ind de Pos+1 até FA
 faça LL[Ind-1]  LL[Ind]
 LL[FA]  LL[IA]
 se FL  IA
 então para Ind de IA+1 até FL
 faça LL[Ind-1]  LL[Ind]
 se FL = IA
 então FL  FA
 senão FL  FL-1
 fim
 fim
 Sucesso  verdadeiro
 fim
fim 
LL – ocupação circular do arranjo
Acesso a um novo nodo
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
C
L3
D
L4
E
L5
F
L6
A
L1
B
L2
5
8
 Acessar 3º nodo da lista
 Acessar nodo com informação C 
Algoritmo: Acessar k-ésimo nodo da LL Circular sobre Arranjo
Algoritmo AcessarKLLCirArr 
 Entradas: LL (TipoLista)
 IA, FA, IL, FL (inteiro)
 K (inteiro)
 Saídas: InfoNodo (TipoNodo)
 Sucesso (lógico)
 Variáveis auxiliares: N, Pos (inteiro) 
início
 se IL = 0 {LISTA VAZIA}
 então N  0
 senão se IL  FL
 então N  FL-IL+1 
 senão N  (FA-IL+1) + (FL-IA+1)
 se (N = 0) ou (K  0) ou (K > N)
 então Sucesso  falso
 senão início 
 se (IL+K-1  FA)
 então Pos  IL+K-1
 senão Pos  IA + (K - (FA-IL+1)-1)
 InfoNodo  LL[Pos]
 Sucesso  verdadeiro
 fim
fim 
Algoritmo: Fornecer Posição de Valor na LL Circular sobre Arranjo
Algoritmo PosValLLCirArr 
 Entradas: LL (TipoLista) Saída: Posição (inteiro)
 IA, FA, IL, FL (inteiro) Variáveis auxiliares: 
 ValBuscado (TipoValor) N, I (inteiro)
 Achou, Sair (lógico) 
início
 Achou  falso
 Posição  0
 se IL = 0 {LISTA VAZIA}
 então N  0
 senão se IL  FL
 então N  FL-IL+1 
 senão N  (FA-IL+1) + (FL-IA+1)
 se N  0
 então início
 I  IL
 Sair  falso
 enquanto (não Achou) e (não Sair)
 faça se LL[I].Valor = Val
 então início
 Posição  I
 Achou  verdadeiro
 fim
 senão se I = FL 
 então Sair  verdadeiro
 senão se I  FA
 então I  I+1
 senão I  IA
fim fim
LL – contiguidade física
Exercícios
Dada uma lista seqüencial de registros, cada registro possui a seguinte estrutura: Código da Matrícula, Nome, Código do curso. Considere que a lista é composta por 5000 registros e o vetor possui capacidade para 7000 registros. Esta lista está ordenada por código de Matrícula. Faça o algoritmo para deletar um ou mais registros. A chave para deleção é o nome do aluno e se existir mais de um aluno com o mesmo nome todos deverão ser deletados. 
LL – contiguidade física
Exercícios
Exibir o conteúdo dos nodos de uma lista com N elementos
Remover todos os elementos duplicados de uma lista com até 10 elementos
*
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.