Upload
leinylson-fontinele
View
166
Download
2
Embed Size (px)
Citation preview
# Estrutura de Dados #Aula 12 – Listas Duplamente Encadeadas
Prof. Leinylson Fontinele Pereira
Na aula anterior...
Listas Circulares
16:37 Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Introdução
16:37 3 Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
O que vamos aprender?
Listas Duplamente Encadeadas# Propriedades
# Operações fundamentais
16:37 Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Vamos começar?
16:37 5 Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Lista Encadeada... relembrando
16:37
Cada elemento é tratado como um ponteiro que é alocadodinamicamente, a medida que os dados são inseridos.
Para guardar o primeiro elemento, utilizamos um ponteiropara ponteiro
Assim, fica fácil mudar quem está no início da lista mudandoo conteúdo do ponteiro para ponteiro.
Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Listas Simplesmente Encadeadas
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Listas Simplesmente Encadeadas
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
struct alunos{
char nome[100];
int idade;
alunos *proximo;
}*lista_alunos;
char nome[100];
int idade;
"Aluno 1"
20
alunos *proximo;
char nome[100];
int idade;
"Aluno 2"
21
alunos *proximo;
char nome[100];
int idade;
"Aluno 3"
23
alunos *proximo;
NULL
Estrutura “alunos”.
Próximo elemento da lista.
16:37
Lista Duplamente Encadeada
Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Funcionamento de um Vetor.....
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
0 9
int vetor_numeros[10] = {0,1,2,3,4,5,6,7,8,9};
5
Índice 0 Índice 5Índice - 1 Índice + 1
4 6 ......
Índice 9
Anterior Próximo
Lista Duplamente Encadeada
16:37
Tipo de lista onde cada elemento aponta para o seu sucessor eantecessor na lista
Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Açãoanterior
Lista Duplamente Encadeada
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
typedef struct noh {
int
info;
struct noh *ant;
struct noh *prox;
} tipoNode;
Lista Duplamente Encadeada
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
struct alunos{
char nome[100];
int idade;
alunos *proximo;
alunos *anterior;
}*lista_alunos;
Ponteiro para o
próximo nó.
Ponteiro para o nó
anterior.
Lista Duplamente Encadeada
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
char nome[100];
int idade;
"Aluno 1"
20
alunos *proximo;
char nome[100];
int idade;
"Aluno 2"
21
char nome[100];
int idade;
"Aluno 3"
23
NULL
struct alunos{
char nome[100];
int idade;
alunos *proximo;
alunos *anterior;
}*lista_alunos;
alunos *anterior;
alunos *proximo; alunos *proximo;
alunos *anterior; alunos *anterior;
NULL
Ponteiro para o próximo nó. Ponteiro para o nó anterior.
Lista Duplamente Encadeada
16:37
Vantagens
Melhor utilização dos recursos de memória
Não precisa movimentar os elementos nasoperações de inserção e remoção
Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Lista Duplamente Encadeada
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Lista Duplamente Encadeada
16:37
Desvantagens
Acesso indireto aos elementos
Necessidade de percorrer a lista para acessarum elemento
Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Lista Duplamente Encadeada
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Lista Duplamente Encadeada
16:37
Quando utilizar? Não há necessidade de garantir um espaço mínimo para a
execução do aplicativo
Inserção/remoção em lista ordenada são as operaçõesmais frequentes
Necessidade de acessar informação de um elementoantecessor
Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Outros tipos de listas
16:37
Uma vez entendidas as listas encadeadasbásicas, você pode “inventar” muitos outros tiposde listas encadeadas
Por exemplo, você pode construir uma listaencadeada circular, em que a última célula apontapara a primeira.
Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Concluindo...
16:37 21 Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Nesta aula aprendemos... Listas Duplamente Encadeadas
# Propriedades
# Operações fundamentais
16:37 Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Material: https://sites.google.com/site/leinylsonuespi
16:37
Material baseado nas aulas de:
Listas Duplamente Encadeadas, Prof. Thomás da Costa
Listas Encadeadas, Prof. Me. Claudio Benossi
Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Prática
16:37 25
As aulas práticas foram baseadas no material de
Linguagem C Descomplicada , Dr. André R. Backes.
Disponível em: https://programacaodescomplicada.wordpress.com/
e Thomás da Costa em seu GitHub
Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Lista Duplamente Encadeada: exemplo
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Inserindo e listando alunos numa lista duplamente encadeada
Lista Duplamente Encadeada: exemplo
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Lista Duplamente Encadeada
16:37
ListaDinEncadDupla.h
Os protótipos das funções
O tipo de dado armazenado na lista
O ponteiro lista
Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Lista Duplamente Encadeada
16:37
ListaDinEncadDupla.c
O tipo de dados lista
Implementar as suas funções
Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
16:37 30
Definindo a Lista
Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Definindo a Lista
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
16:37 32
Criando a Lista
Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Criando a Lista
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
16:37 34
Destruindo a Lista
Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Destruindo a Lista
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Destruindo a Lista
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
16:37 37
Tamanho da Lista
Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Tamanho da Lista
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Tamanho da Lista
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
16:37 40
A Lista está Cheia?
Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
A Lista está Cheia?
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
16:37 42
A Lista está Vazia?
Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
A Lista está Vazia?
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
16:37 44
Inserindo na Lista
Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Inserindo na Lista
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Inserindo numa Lista Vazia
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Inserindo no Início da Lista
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Inserindo no Início da Lista
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Inserindo no Final da Lista
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Inserindo no Final da Lista
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Inserindo de Forma Ordenada na Lista
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Inserindo de Forma Ordenada na Lista
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Inserindo de Forma Ordenada na Lista
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
16:37 54
Remoção na Lista
Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Observações sobre Remoção
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Remoção do Início da Lista
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Remoção do Início da Lista
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Remoção do Início da Lista
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Remoção do Meio da Lista
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Remoção do Meio da Lista
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Remoção do Meio da Lista
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Remoção do Final da Lista
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Remoção do Final da Lista
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Remoção do Final da Lista
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
16:37 65
Consulta na Lista
Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Consulta na Lista
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Consulta pela Posição na Lista
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas
Consulta pelo Conteúdo da Lista
16:37Estrutura de Dados: Aula 12 – Listas Duplamente Encadeadas