Lista_Linear_I

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

LISTA LINEAR
(parte I)
 
Estrutura de Dados
Uma Lista Linear (LL) é uma seqüência de nodos
 Lista linear 
 Nodos - elementos do mesmo tipo
 Relação de ordem linear (ou total)
 Lista linear 
a
b
c
d
e
Primeiro nodo
Último nodo
Segundo nodo
 Estrutura interna é abstraída
 Pode ter uma complexidade arbitrária
 Enfatizado o conjunto de relações existente
z
d
a
c
b
d
 Estrutura dos nodos 
Uma lista linear é uma coleção de n  0 nodos 
x1, x2, ... , xn, todos do mesmo tipo, cujas propriedades estruturais relevantes envolvem apenas as posições relativas lineares entre nodos:
	n = 0 : lista vazia, apresenta zero nodos
n > 0 : x1 é o primeiro nodo
 xn é o último nodo
1 < k < n : xk é precedido por xk-1 e sucedido por xk+1
 Lista linear: seqüência de 0 ou mais nodos do mesmo tipo
 Definição formal 
 Notas de alunos
 Cadastro de funcionários de uma empresa 
 Itens em estoque em uma empresa 
 Dias da semana
 Vagões de um trem 
 Letras de uma palavra 
 Pessoas esperando ônibus
 Cartas de baralho 
 Precipitações pluviométricas em um mês / dia 
 Exemplos de aplicações com listas
 Operações sobre listas lineares
 Criação de uma lista
 Inserção de um nodo
 Exclusão de um nodo
 Acesso a um nodo
 Destruição de uma lista
Operações básicas:
 Contigüidade física 
 Encadeamento 
Representação física das relações existentes entre os nodos e não aquelas internas a eles
Representação física de uma
lista linear 
Listas lineares
LL implementadas através de contiguidade física
Implementação de LL através de contigüidade física
 Utiliza a seqüencialidade da memória para representar a ordem entre os nodos
Lista linear
Arranjo
Implementação de LL sobre arranjo de 1 dimensão
Características
 todos os elementos do arranjo tem tipo igual
 cada elemento do arranjo é um nodo
 tipo do nodo = tipo do elemento do arranjo
 posição no arranjo representa posição na LL
 acesso direto aos nodos
 natureza dinâmica – inserção / remoção de nodos
 comprimento varia durante aplicação
LL – contiguidade física
L2
L1
L3
L4
L5
L6
L1
L2
L3
L4
L5
L6
1 2 3 4 5 6 
L L
TipoNodo = registro
 Nome: string
 Código: inteiro
 Valor: real
 fim registro
 
TipoLista = arranjo [1 .. N] de TipoNodo
Tipos de dados
Tipos de dados utilizados nos algoritmos
para LL implementada com contiguidade física:
LL – contiguidade física
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L1
L2
L3
L4
L5
5
8
Lista
LL – contiguidade física
Início e final da LL geralmente são diferentes do início e final do arranjo
Início e final da LL
Variáveis para identificar Início e Final da Lista
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L1
L2
L3
L4
L5
5
8
Início
do Arranjo
Final
do Arranjo
Lista
LL – contiguidade física
Início e final da LL geralmente são diferentes do início e final do arranjo
Início e final da LL
Variáveis para identificar Início e Final da Lista
Um mesmo arranjo pode ser utilizado para 
mais de uma lista linear
Mais de uma LL em um arranjo
1
2
4
3
7
6
9
10
LL
IL1
FL2
IA
FA
L1
L2
L1
L2
L3
5
8
IL2
FL1
Lista 1
Lista 2
LL – contiguidade física
 criação da lista
 inserção de um novo nodo
 remoção de um nodo 
 acesso a um nodo
Operações sobre listas lineares
em contiguidade física
Algoritmos
LL – contiguidade física
1
2
4
3
7
6
9
10
LL
5
8
Criação de uma LL vazia 
 Declarar o arranjo
 Inicializar variáveis que guardam início e final da lista
IL = FL = IA-1
IA
FA
LL – contiguidade física
Algoritmo: 
Inicializar LL sobre Arranjo vazio 
LL – contiguidade física
Algoritmo InicializarLLArr 
 Entradas: IA (inteiro)
 Saídas: IL, FL (inteiro)
início
 IL  FL  IA - 1
fim 
Ex: Lista de informações de produtos de uma empresa 
TipoNodo = registro
 Nome: string
 Código: inteiro
 Preço: real
 fim registro 
TipoLista = arranjo [1 .. 10] de TipoNodo
1
2
4
3
7
6
9
10
LL
5
8
IA
FA
Nome
Código
Preço
IL
FL
0
Inserção de um novo nodo 
LL – contiguidade física
 LL já existente
Informar:
 posição (ordem) do novo nodo na LL
 valor do campo de informação do novo nodo
Quando não é possível realizar a inserção:
 posição solicitada fora dos limites da LL existente
 espaço disponível para a LL no arranjo todo preenchido
 
L1
L2
L3
L4
L5
L6
0 1 2 3 4 5 6 7 
L L
IA IL FL FA
Inserção de um novo nodo 
LL – contiguidade física
LL – contiguidade física
Inserção como primeiro nodo da LL 
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L1
L2
L3
L4
L5
L6
5
8
Inserir
no início
LL inicia no início do arranjo
LL – contiguidade física
Inserção como primeiro nodo da LL 
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L1
L2
L3
L4
L5
L6
5
8
1
2
4
3
7
6
9
10
LL
5
8
IA
FA
Inserir
no início
LL inicia no início do arranjo
LL – contiguidade física
Inserção como primeiro nodo da LL 
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L1
L2
L3
L4
L5
L6
5
8
1
2
4
3
7
6
9
10
LL
L1
L2
L3
L4
L5
L6
L7
5
8
IL
FL
IA
FA
Inserir
no início
Novo nodo
LL inicia no início do arranjo
LL – contiguidade física
Inserção como primeiro nodo da LL 
LL não inicia no início do arranjo
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L1
L2
L3
L4
L5
L6
5
8
Inserir
no início
LL – contiguidade física
Inserção como primeiro nodo da LL 
LL não inicia no início do arranjo
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L1
L2
L3
L4
L5
L6
5
8
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L1
L2
L3
L4
L5
L6
L7
5
8
Inserir
no início
Novo nodo
Algoritmo InserirIniLLArr 
 Entradas: LL (TipoLista)
 IA, FA, IL, FL (inteiro)
 InfoNodo (TipoNodo)
 Saídas: LL (TipoLista)
 IL, FL (inteiro)
 Sucesso (lógico)
 Variável auxiliar: Ind (inteiro)
início
 se (IA = IL) e (FA = FL) então {arranjo vazio}
 Sucesso  falso 
 senão 
 início			 
 se IL = 0 então {lista vazia}
 IL  FL  IA 
 senão 
 se IL > IA então {a lista não inicia na primeira posição do arranjo}
 IL  IL-1
 senão 
 início {Deslocar nodos para cima}
 para Ind de FL incr -1 até IL faça
 LL[Ind+1]  LL[Ind]
 FL  FL+1
 fim
 LL[IL]  InfoNodo 
 Sucesso  verdadeiro 	 
 fim
fim 
LL – contiguidade física
Algoritmo: 
Inserir no Inicío de LL implementada sobre Arranjo 
LL – contiguidade física
Inserção como último nodo da LL 
LL não termina no final do arranjo
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L1
L2
L3
L4
L5
L6
5
8
Inserir
no final
LL – contiguidade física
Inserção como último nodo da LL 
LL não termina no final do arranjo
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L1
L2
L3
L4
L5
L6
5
8
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L1
L2
L3
L4
L5
L6
L7
5
8
Inserir
no final
Novo nodo
LL – contiguidade física
Inserção como último nodo da LL 
LL termina no final
do arranjo
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L1
L2
L3
L4
L5
L6
5
8
Inserir
no final
LL – contiguidade física
Inserção como último nodo da LL 
LL termina no final do arranjo
1
2
4
3
7
6
9
10
LL
L1
L2
L3
L4
L5
L6
5
8
1
2
4
3
7
6
9
10
LL
L1
L2
L3
L4
L5
L6
L7
5
8
IL
IA
FL
FA
Inserir
no final
IL
FL
IA
FA
Novo nodo
Algoritmo InserirFimLLArr 
 Entradas: LL (TipoLista)
 IA, FA, IL, FL (inteiro)
 InfoNodo (TipoNodo)
 Saídas: LL (TipoLista)
 IL, FL (inteiro)
 Sucesso (lógico)
 Variável auxiliar: Ind (inteiro)
início
 se (IA = IL) e (FA = FL)
 então Sucesso  falso 
 senão início			 
 se IL = 0 {LISTA VAZIA}
 então IL  FL  IA 
 senão se FL < FA {TEM ESPAÇO ATRÁS}
 então FL  FL+1
 senão início {DESLOCAR NODOS PARA BAIXO}
 para Ind de IL incr 1 até FL faça
 LL[Ind-1]  LL[Ind]
 IL  IL-1
 fim
 LL[FL]  InfoNodo 
 Sucesso  verdadeiro 	 
 fim
fim 
LL – contiguidade física
Algoritmo: 
Inserir no Fim de LL implementada sobre Arranjo 
LL – contiguidade física
Inserção no meio de LL 
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L1
L2
L3
L4
L5
5
8
Inserir
Posição: 3o nodo
LL – contiguidade física
Inserção no meio de LL 
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L1
L2
L3
L4
L5
5
8
1
2
4
3
7
6
9
10
LL
L1
L2
L3
L4
L5
L6
5
8
IL
FL
IA
FA
Inserir
Posição: 3o nodo
Novo nodo
LL – contiguidade física
Algoritmo: 
Inserir em LL implementada sobre Arranjo na Posição K 
Posição K
 K = 1  no início da LL
 K = FL – IL + 2  no final da lista
Caso haja deslocamento
 para cima, caso haja espaço
 senão, para baixo
Sucesso retorna falso quando
 não existe espaço no arranjo para a inserção
 posição inválida para inserção na LL
LL – contiguidade física
Algoritmo: 
Inserir em LL implementada sobre Arranjo na Posição K 
Algoritmo InserirLLArrPosK 
 Entradas: LL (TipoLista)
 IA, FA, IL, FL (inteiro)
 K (inteiro)
 InfoNodo (TipoNodo)
 Saídas: LL (TipoLista)
 IL, FL (inteiro)
 Sucesso (lógico)
 Variável auxiliar: Ind (inteiro)
início
 se (IA = IL e FA = FL) ou (K > FL-IL+2) ou (K  0) ou (IL = 0 e K  1) 
 então Sucesso  falso 
 senão início			 
 se IL = 0
 então IL  FL  IA 
 senão se FL  FA 	
 então início {DESLOCAR NODOS PARA CIMA}
 para Ind de FL incr -1 até IL+K-1 faça
 LL[Ind+1]  LL[Ind]
 FL  FL+1
 fim
 senão início {DESLOCAR NODOS PARA BAIXO}
 para Ind de IL incr 1 até IL+K-2 faça
 LL[Ind-1]  LL[Ind]
 IL  IL - 1
 fim
 LL[IL+K-1]  InfoNodo 
 Sucesso  verdadeiro 	 
 fim
fim 
A posição não poderá ser maior do que o número de nodos da lista antes da inserção
 Otimizar: 
deslocar nodos da metade para o fim se a inserção for na
primeira metade da lista, e da metade para o início se for na segunda metade
 desde que haja espaço no lado considerado
40
20
90
80
70
 
0
1
3
4
2
6
5
7
 
8
 
9
K  3
K > 3
LL – contiguidade física
Algoritmo: 
Inserir em LL implementada sobre Arranjo na Posição K 
LL – contiguidade física
Remoção de um nodo 
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L1
L2
 
L3
L4
L5
5
8
Remover
3o nodo
LL – contiguidade física
Remoção de um nodo 
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L1
L2
 
L3
L4
L5
5
8
1
2
4
3
7
6
9
10
LL
L1
L2
 
L3
 
L4
5
8
IL
FL
IA
FA
Remover
3o nodo
Algoritmo RemoverKLLArr 
 Entradas: LL (TipoLista)
 IL, FL (inteiro)
 K (inteiro)
 Saídas: LL (TipoLista)
 IL, FL (inteiro)
 Sucesso (lógico)
 Variável auxiliar: Ind (inteiro)
início
 se (K  0) ou (K > FL-IL+1) 
 então Sucesso  falso
 senão início 
 para Ind de IL+K-1 incr 1 até FL-1 faça
 LL[Ind]  LL[Ind+1]
 FL  FL-1
 se FL = IL–1 
 então IL  FL  0 
 Sucesso  verdadeiro
 fim
fim 
LL – contiguidade física
Algoritmo: 
Remover nodo de ordem K de LL implementada sobre Arranjo
Acessar para 
Consulta a informações do nodo
Alteração de algum campo de informação do nodo
LL – contiguidade física
Acesso a um nodo 
LL – contiguidade física
Acesso a um nodo 
 O nodo a ser acessado pode ser identificado por
 sua ordem na lista Ex: 2º nodo
 através de seu conteúdo Ex: nodo de conteúdo “D”
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
L1
L2
 
L3
L4
L5
5
8
1
2
4
3
7
6
9
10
LL
IL
FL
IA
FA
A
B
 
C
D
E
5
8
LL – contiguidade física
Algoritmo AcessarKLLArr
 Entradas: LL (TipoLista)
 IL, FL (inteiro)
 K (inteiro)
 Saídas: InfoNodo (TipoNodo)
 Sucesso (lógico)
início
 se (K  0) ou (K > FL-IL+1) ou (IL = 0)
 então Sucesso  falso
 senão início
 InfoNodo  LL[IL+K-1]
 Sucesso  verdadeiro
 fim
fim 
Algoritmo: 
Acessar “k-ésimo” nodo da LL implementada sobre Arranjo
Algoritmo PosValLLArr 
 Entradas: LL (TipoLista)
 IL, FL (inteiro)
 ValBuscado (TipoValor)
 Saída: Posição(inteiro)
 Variáveis auxiliares: 
 I (inteiro)
 Achou (lógico)
início
 Achou  falso
 Posição  0
 I  IL
 enquanto (I  FL) e (não Achou)
 faça se LL[I].Valor = ValBuscado
 então início
 Posição  I
 Achou  verdadeiro
 fim
 senão I  I+1
fim 
TipoNodo = registro
 Valor: inteiro
 Info: TipoInfo
 fim registro 
LL – contiguidade física
Algoritmo: 
Fornece a posição na LL do nodo com um determinado Valor
LL – contiguidade física
Exercícios
Implementar as seguintes operações sobre Listas Lineares com contigüidade física:
 Criação
 Inserção
 Exclusão
 Busca
Utilize:
struct dados {
	int codigo;
	int idade;
}
int vet[10];	
*
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.