Aula_09

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
ESTRUTURA DE DADOS – AULA 9
ANITA MACIEL
Rio de Janeiro, 2011
*
*
*
*
Listas Encadeadas
continuação da Aula 8
*
*
FILA
PILHA
Dinâmicas
*
*
1a parte
*
*
As Listas Encadeadas podem ser de
 Encadeamento Simples – cada nó é ligado por um ponteiro, permitindo que ela seja percorrida(cruzada) do primeiro ao último elemento.
 Encadeamento duplo – cada nó é ligado por dois ponteiros. Esse tipo de lista permite um cruzamento igual ao da Lista Simples, mas acrescenta a possibilidade da lista ser percorrida(cruzada) de trás para frente. 
*
*
Encadeadas circulares – onde o último nó é ligado ao primeiro, significando que não existe NULL. 
*
*
Listas de encadeamento simples, normalmente chamadas simplesmente de Listas Encadeadas, são compostas de elementos individuais, cada um ligado por um único ponteiro. Cada elemento consiste de duas partes: um membro de dados e um ponteiro.(LOUDON, K, 2000, p.56) 
*
*
A lista é formada por nós
Se olharmos para este nó, podemos entendê-lo como uma estrutura, visto que ele é formado por dois tipos diferentes, sendo um, necessariamente, ponteiro.
*
*
*
*
“Essa circularidade, no entanto, é permitida em C++”. (DROZDEK, A, 2002, p.68) 
*
*
Criando uma lista de um nó
1) Declarando a struct
*
*
Criando uma lista de um nó
1) Declarando a struct
*
*
2) Criando nó 
Criando uma lista de um nó
*
*
3) Atribuindo valores aos membros 
2) Criando nó 
Criando uma lista de um nó
*
*
3) Atribuindo valores aos membros 
2) Criando nó 
Criando uma lista de um nó
*
*
4) Exibindo 
Criando uma lista de um nó
*
*
4) Exibindo 
Criando uma lista de um nó
*
*
5) Liberando 
4) Exibindo 
Criando uma lista de um nó
*
*
5) Liberando 
4) Exibindo 
Criando uma lista de um nó
*
*
*
*
*
*
 struct nodo
 {
 int num;
 struct nodo *prox;
 }; 
*
*
 struct nodo
 {
 int num;
 struct nodo *prox;
 }; 
 
 //primeiro nó
 nodo *lista=new nodo; 
 lista->num=23;
 lista->prox=NULL; 
*
*
 //segundo nó
 lista->prox=new nodo; 
 lista->prox->num=13;
 lista->prox->prox=NULL; 
*
*
 //segundo nó
 lista->prox=new nodo; 
 lista->prox->num=13;
 lista->prox->prox=NULL;
 
 //terceiro nó
 lista->prox->prox=new nodo; 
 lista->prox->prox->num=15; 
 lista->prox->prox->prox=NULL; 
 
*
*
 //quarto no
 lista->prox->prox->prox=new nodo; 
 lista->prox->prox->prox->num=18; 
 lista->prox->prox->prox->prox=NULL;
 
*
*
*
*
Definindo a struct
*
*
Insere nó na frente
*
*
Insere nó atrás
*
*
Remove nó da frente
*
*
Remove nó do final
*
*
O alvo é procurar o penúltimo para que possa remover o último. Por essa razão, a linha aux->prox->prox estará sempre olhando o próximo do próximo porque se ele não existir, significa que aux->prox é o último.
*
*
Exibe lista
*
*
Substitui valor do Nó
*
*
Conta os nós
*
*
Busca Sequencial
*
*
Desaloca
*
*
2a parte
*
*
Como a Pilha e a Fila são casos particulares da Lista, não introduzi nenhuma outra função. Todas as funções foram as usadas na Lista, respeitando as características das estruturas.
*
*
*
*
*
*
*
*
*
*
*
*
Reveja todos os conceitos desta aula.
Aprimore seus conhecimentos pesquisando no material didático e na bibliografia recomendada (procure na Biblioteca do campus ou na Biblioteca Virtual/ SIA).
Faça todos os exercícios.
*
*
Esteja sempre em contato com seu professor.
Não durma com dúvidas.
Assista a esta aula quantas vezes for necessário.
*
*
*
*