Upload
paulo-jansen
View
249
Download
0
Embed Size (px)
Citation preview
8/15/2019 Estruturas de dados. Listas duplamente encadeadas
1/16
1
Lista Encadeada CircularLista DuplamenteEncadeada
8/15/2019 Estruturas de dados. Listas duplamente encadeadas
2/16
2
Relembrando listasencadeadasUm nó em uma Lista Encadeada possui
basicamente dois itens:– ponteiro para o próximo
– informação armazenada
Caso a informação não seja um dado simples:criar vários campos um para cada informação
Ex!: códi"o preço e #uantidade de um produto
8/15/2019 Estruturas de dados. Listas duplamente encadeadas
3/16
3
Relembrando listasencadeadas
t$pedef struct tp_no %int cod&'oat preco&
int #uant&struct tp_no (prox&
) TPLISTA&
TPLISTA (lista&!!!lista*+cod,-&lista*+preco,-.!/&
lista*+#uant,0.&
8/15/2019 Estruturas de dados. Listas duplamente encadeadas
4/16
4
Listas Circulares1 2ltimo elemento tem como próximo o primeiro
elemento da lista formando um ciclo3til #uando:
– a busca 4 feita a partir de #ual#uer elemento– não 5á ordenação na lista
6 ri"or não existe 7primeiro7 ou 72ltimo7 6inda 4 necessário #ue exista um ponteiro para al"um
elemento para a localização da lista– por convenção refer8ncia do primeiro ou do 2ltimo
lista 4 1 8 5
8/15/2019 Estruturas de dados. Listas duplamente encadeadas
5/16
5
Listagem
void lista"em 9tplista (t %
tplista (p,t&if 9t;,d7 p*+info&p,p*+prox&
) ?5ile 9p;,t&else
printf97Lista Circular vazia;7&)
8/15/2019 Estruturas de dados. Listas duplamente encadeadas
6/16
6
Lista Circular
=nserção@Aemoção@
8/15/2019 Estruturas de dados. Listas duplamente encadeadas
7/16
7
Lista Duplamente Encadeada
3til #uando 4 preciso percorrer a listana ordem inversa
Aemoção de um elemento não precisa"uardar anterior
Aemoção de um elemento cujoponteiro 4 informado não precisarpercorrer a Bla toda
Um conjunto maior de li"açesprecisam ser atualizadas
8/15/2019 Estruturas de dados. Listas duplamente encadeadas
8/16
8
Cada nó possui dois ponteiros: um para oelemento anterior e outro para o próximoelemento 9ant e prox
proxant
a b c d
lista
Lista Duplamente Encadeada
8/15/2019 Estruturas de dados. Listas duplamente encadeadas
9/16
9
Listas DuplamenteEncadeada
t$pedef int tpitem&
t$pedef struct tpDno %
tpitem info&struct tpDno (ant&struct tpDno (prox&
) tplista&
tplista (lista&
8/15/2019 Estruturas de dados. Listas duplamente encadeadas
10/16
10
Busca e Listagem
usca e Lista"em:
Códi"o i"ual ao #ue 4 utilizado paraa Lista Fimplesmente Encadeada
8/15/2019 Estruturas de dados. Listas duplamente encadeadas
11/16
11
Inserção no Incio
b e h
lista
a
1 novo elemento 4 encadeado no inGcio dalista
1 seu próximo passa a ser o anti"o primeiroelemento e o seu anterior 4
8/15/2019 Estruturas de dados. Listas duplamente encadeadas
12/16
12
Inserção
int insere!tplista ""t# tpitem e$%
tplista "no&o'
no&o ( aloca!$'
i) !*no&o$
return +'
no&o,-in)o ( e'
no&o ,- ant ( ./LL'
no&o ,- pro0 ( "t'
i) !!"t$ *( ./LL$ !"t$ ,- ant ( no&o'
"t ( no&o'
return 1'
2
8/15/2019 Estruturas de dados. Listas duplamente encadeadas
13/16
13
Remoção
6 remoção 4 mais trabal5osa pois 4preciso acertar a cadeia nos doissentidos
Em compensação pode*se retirar umelemento con5ecendo*se apenas oponteiro para ele
Utiliza*se uma função de busca paralocalizar o elemento e em se"uida oencadeamento 4 ajustado
6o Bnal o elemento 4 liberado
8/15/2019 Estruturas de dados. Listas duplamente encadeadas
14/16
14
Remoção Fendo p o ponteiro para o elemento a ser
excluGdo se o elemento estiver no meio dalista devemos fazer:
p*+ant*+prox , p*+prox&p*+prox*+ant , p*+ant&
Caso o elemento esteja em um extremo dalista existem outras condiçes:– se p for o primeiro não se pode referenciar p*
+ant pois ele 4
8/15/2019 Estruturas de dados. Listas duplamente encadeadas
15/16
15
Remoção
e h
lista
a b
e h
lista
a b
p
p
8/15/2019 Estruturas de dados. Listas duplamente encadeadas
16/16
17
Cada nó possui dois ponteiros: um para oelemento anterior e outro para o próximoelemento 9ant e prox
1 anterior do primeiro 4 o 2ltimo e opróximo do 2ltimo 4 o primeiro
a b c d
lista
Lista Duplamente Encadeada eCircular