Adelina
Profa. Gustavo Willam Pereira
Créditos: Profa. Juliana Pinheiro Campos
ESTRUTURAS DE DADOS
Listas encadeadas com descritor
Lista com cabeça e rabo
Listas circulares
Listas duplamente encadeadas
Listas de tipos estruturados
ESTRUTURAS DE DADOS
Listas encadeadas com descritor
Problemas da lista simplesmente encadeada:
• Descobrir o número de elementos na lista.
• Descobrir o último elemento da lista.
Estes problemas podem ser resolvidos usando um descritor.
Um descritor contém informações que tornam algumas operações mais eficientes.
ESTRUTURAS DE DADOS
Listas encadeadas com descritor
Primeiro
n
Último
NULL
0
Primeiro
n
Lista vazia
NULL
Último
3
Lista com 3 elementos 2
4
6
ESTRUTURAS DE DADOS
Listas encadeadas com descritor typedef struct nodo { int item; struct nodo* prox;
} Nodo; typedef struct lista {
Nodo *prim; int size;
Nodo *ult;
}Lista;
ESTRUTURAS DE DADOS
Listas encadeadas com descritor
Funções implementadas em sala:
Lista* criarLista()
Nodo* first(Lista* l)
Nodo* last(Lista* l)
Nodo* find(Lista* l, int it) int retrieve(Nodo* p) int insert(Lista* l, int it, Nodo* p) int remover(Lista* l, Nodo* p)
Nodo* next(Lista*l, Nodo* p)
Nodo* previous(Lista* l, Nodo* p) void print(Lista* l) unsigned int length(Lista* l) void destruirLista(Lista* l)
ESTRUTURAS DE DADOS
Listas com cabeça e cauda
Na implementação de listas encadeadas pode ser interessante criar nós extras conhecidos como sentinelas.
No caso das listas com cabeça e cauda temos um nó extra no início da lista (cabeça) e um nó extra no final da lista (cauda).
O conteúdo desses nós é irrelevante.
ESTRUTURAS DE DADOS
Listas com cabeça e cauda
Lista vazia
Cabeça
Lista com 2 elementos Cauda
5
Cabeça
7
Cauda
ESTRUTURAS DE DADOS
Listas com cabeça e cauda
A vantagem de usar esses nós extras é que eles simplificam o código, eliminando