Aula13_Listas_Encadeadas_Ciruclares_Listas_Duplamente_Encadeadas

Prévia do material em texto

Listas Encadeadas Circulares e Listas Duplamente
Encadeadas
Professor:
Silvio Luiz Bragatto Boss
e-mail:
silvioboss@utfpr.edu.br
Universidade Tecnolo´gica Federal do Parana´ - UTFPR
Coordenac¸a˜o de Informa´tica - COINF
Curso de Engenharia de Computac¸a˜o
Disciplina de Estrutura de Dados I
Lista Encadeada Circular Lista Duplamente Encadeada
Suma´rio
1 Lista Encadeada Circular
2 Lista Duplamente Encadeada
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Lista Encadeada Circular Lista Duplamente Encadeada
Listas Encadeadas Circulares
O u´ltimo elemento tem como pro´ximo o primeiro elemento da
lista, formando um ciclo
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Lista Encadeada Circular Lista Duplamente Encadeada
Listas Encadeadas Circulares
O u´ltimo elemento tem como pro´ximo o primeiro elemento da
lista, formando um ciclo
Quando utilizar:
a busca e´ feita a partir de qualquer elemento;
na˜o ha´ ordenac¸a˜o na lista.
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Lista Encadeada Circular Lista Duplamente Encadeada
Listas Encadeadas Circulares
O u´ltimo elemento tem como pro´ximo o primeiro elemento da
lista, formando um ciclo
Quando utilizar:
a busca e´ feita a partir de qualquer elemento;
na˜o ha´ ordenac¸a˜o na lista.
A princ´ıpio na˜o existe primeiro ou u´ltimo no´.
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Lista Encadeada Circular Lista Duplamente Encadeada
Listas Encadeadas Circulares
O u´ltimo elemento tem como pro´ximo o primeiro elemento da
lista, formando um ciclo
Quando utilizar:
a busca e´ feita a partir de qualquer elemento;
na˜o ha´ ordenac¸a˜o na lista.
A princ´ıpio na˜o existe primeiro ou u´ltimo no´.
Ainda e´ necessa´rio que exista ponteiros auxiliares.
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Lista Encadeada Circular Lista Duplamente Encadeada
Listas Encadeadas Circulares
O u´ltimo elemento tem como pro´ximo o primeiro elemento da
lista, formando um ciclo
Quando utilizar:
a busca e´ feita a partir de qualquer elemento;
na˜o ha´ ordenac¸a˜o na lista.
A princ´ıpio na˜o existe primeiro ou u´ltimo no´.
Ainda e´ necessa´rio que exista ponteiros auxiliares.
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Lista Encadeada Circular Lista Duplamente Encadeada
Listas Duplamente Encadeadas
U´til quando e´ preciso percorrer a lista na ordem inversa
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Lista Encadeada Circular Lista Duplamente Encadeada
Listas Duplamente Encadeadas
U´til quando e´ preciso percorrer a lista na ordem inversa
Remoc¸a˜o de um elemento na˜o precisa guardar anterior
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Lista Encadeada Circular Lista Duplamente Encadeada
Listas Duplamente Encadeadas
U´til quando e´ preciso percorrer a lista na ordem inversa
Remoc¸a˜o de um elemento na˜o precisa guardar anterior
Um conjunto maior de ligac¸o˜es precisam ser atualizadas
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Lista Encadeada Circular Lista Duplamente Encadeada
Listas Duplamente Encadeadas
Cada no´ possui dois ponteiros: um para o elemento anterior e
outro para o pro´ximo elemento (ant e prox).
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Lista Encadeada Circular Lista Duplamente Encadeada
Listas Duplamente Encadeadas
Cada no´ possui dois ponteiros: um para o elemento anterior e
outro para o pro´ximo elemento (ant e prox).
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Lista Encadeada Circular Lista Duplamente Encadeada
Listas Duplamente Encadeadas
Declarac¸a˜o da estrutura de uma lista duplamente encadeada
typedef struct NoTag{
int info;
struct NoTag *ant;
struct NoTag *prox;
}no;
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Lista Encadeada Circular Lista Duplamente Encadeada
Listas Duplamente Encadeadas
Inserc¸a˜o de um No´ no Inicio da Lista
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Lista Encadeada Circular Lista Duplamente Encadeada
Listas Duplamente Encadeadas
Insere novo no´ na lista
Aloca um novo no´ e,
Copia a informac¸a˜o desejada para o campo info do novo no´.
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Lista Encadeada Circular Lista Duplamente Encadeada
Listas Duplamente Encadeadas
Insere novo no´ na lista
Se a lista estiver vazia enta˜o:
O ponteiro externo aponte para o novo no´;
Os membros ant e prox recebem nullo.
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Lista Encadeada Circular Lista Duplamente Encadeada
Listas Duplamente Encadeadas
Insere novo no´ na lista
Fac¸a com que:
O membro ant receba nullo e,
O membro prox receba o enderec¸o do ponteiro externo L.
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Lista Encadeada Circular Lista Duplamente Encadeada
Listas Duplamente Encadeadas
Insere novo no´ na lista
Fac¸a com que, o membro ant do no´ apontado pelo ponteiro
externo, aponte para o novo no´.
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Lista Encadeada Circular Lista Duplamente Encadeada
Listas Duplamente Encadeadas
Insere novo no´ na lista
Fac¸a com que, o ponteiro externo aponte para o novo no´.
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Lista Encadeada Circular Lista Duplamente Encadeada
Listas Duplamente Encadeadas
Remove um no´ na lista
Se a lista na˜o estiver vazia e na˜o tiver apenas um no´ na lista,
enta˜o:
Declare um ponteiro p e fac¸a com que ele aponte para o
primeiro no´ da lista.
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Lista Encadeada Circular Lista Duplamente Encadeada
Listas Duplamente Encadeadas
Remove um no´ na lista
Fac¸a com que, o ponteiro externo aponte para o segundo no´
da lista.
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Lista Encadeada Circular Lista Duplamente Encadeada
Listas Duplamente Encadeadas
Remove um no´ na lista
Fac¸a com que, o membro ant do segundo no´ receba nullo.
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Lista Encadeada Circular Lista Duplamente Encadeada
Listas Duplamente Encadeadas
Remove um no´ na lista
Libere espac¸o do no´ apontado por p.
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX