Adelina

Estruturas de Dados

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