Estruturas de Dados - Tipo Abstrato de Dados - Listas - Parte 2 (Dibio)

Prévia do material em texto

dibio@unb.br
Roteiro
 Listas Encadeadas 
 Variações
 Simples, Duplas, Circulares
 Tipo Abstrato de Dados (TAD) para Variações
 Exemplo com Listas Heterogêneas em C
dibio@unb.br
Listas Encadeadas
● Para cada novo elemento no conjunto aloca­se um 
espaço de memória para armazená­lo;
● Junto com a informação de cada elemento guarda­
se um ponteiro para o próximo elemento da lista;
● Um vantagem (por exemplo) de uma lista sobre 
um vetor ocorre quando necessita­se inserir ou 
retirar um elemento no meio (intermediário), pois 
na lista não é necessário deslocar todos os outros 
elementos na operação.  
dibio@unb.br
Variações de Listas Encadeadas
dibio@unb.br
Listas Circulares
● Estrutura do nó da lista é idêntica a da lista simples;
● Não se faz distinção para primeiro e último nó da lista;
● Para testar se a lista foi totalmente percorrida deve­se 
guardar o endereço do primeiro nó lido e comparar com 
o endereço do nó sendo lido;
● ex. lista circular: (Uso em conjuntos cíclicos, e.g. 
geométricos)
dibio@unb.br
Exemplo função TAD Lista Circular
● Impressão de uma lista circular
dibio@unb.br
Exercícios para casa
● Escreva uma função em C para inserir um 
elemento em uma lista circular
● Escreva uma função em C para retirar um 
elemento em uma lista circular
dibio@unb.br
Listas Duplas
dibio@unb.br
Listas Duplas
dibio@unb.br
Exemplo função TAD Listas Duplas
dibio@unb.br
Ex: Busca de elemento
dibio@unb.br
Ex: Retirada de elemento
dibio@unb.br
Ex: Retirada de elemento
dibio@unb.br
Listas Circulares Duplamente 
Encadeadas
dibio@unb.br
Ex: Função TAD para L. Circ. Dup. 
(Impressão no sentido inverso)
dibio@unb.br
Exercícios para casa
● Escreva uma função TAD em C para uma inserir 
um elemento em uma lista duplamente encadeada
● Escreva uma função TAD em C para uma retirar 
um elemento em uma lista duplamente encadeada
dibio@unb.br
Exemplo: Lista de tipos 
estruturados heterogêneos
dibio@unb.br
Ex: Alocando um nó na lista 
dibio@unb.br
Ex: Alocando um nó na lista 
dibio@unb.br
Ex: Lista Heterogênea
dibio@unb.br
Ex: Lista Heterogênea 
(Representação)
dibio@unb.br
Ex: Lista Heterogênea 
(Representação)
dibio@unb.br
Ex: Lista Heterogênea 
dibio@unb.br
Ex: Nós com retângulos
dibio@unb.br
Ex: Nós com triângulos
dibio@unb.br
Ex: Nós com círculos
dibio@unb.br
Ex: enumerando tipos criados
dibio@unb.br
Ex: Cálculo de área
dibio@unb.br
Ex: Cálculo de elemento com maior área
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28