AULA 09 - LISTA DUPLAMENTE ENCADEADA

Prévia do material em texto

AULA 09 – LISTA DUPLAMENTE ENCADEACA
*
Lista Duplamente Encadeada
Prof. Leticia Winkler
	É um tipo de lista encadeada que pode ser vazia (NULL) ou que pode ter um ou mais nós, sendo que cada nó possui dois ponteiros: um que aponta para o nó antecessor e outro que aponta para o nó sucessor.
	O importante é que, neste tipo de lista, o ponteiro externo pode apontar para qualquer nó da lista, pois é possível caminhar para a direita ou para a esquerda com igual facilidade.
	Uma lista duplamente encadeada pode ser circular ou não e ainda, pode	estar em ordem (crescente/decrescente) ou não.
primeiro	último
*
Prof. Leticia Winkler
Nó da Lista
Prof. Leticia Winkler
nó
*
	
anterior	
informação	
próximo
Prof. Leticia Winkler
Lista Duplamente Encadeada vs. Lista Simplesmente Encadeada
Prof. Leticia Winkler
*
	Uma primeira vantagem da utilização de lista duplamente encadeada sobre a lista simplesmente encadeada é a maior facilidade para navegação, que na lista duplamente encadeada pode ser feita nos dois sentidos, ou seja, do início para o fim e do fim para o início.
	Isso facilita a realização de operações tais como inclusão e remoção de nós, pois diminui a quantidade de variáveis auxiliares necessárias.
	Se não existe a necessidade de se percorrer a lista de trás para frente, a lista simplesmente encadeada é a mais interessante, pois é mais simples.
Prof. Leticia Winkler
Lista Duplamente Encadeada vs. Lista Simplesmente Encadeada
Prof. Leticia Winkler
primeiro
último
primeiro
atual
atual
*
Prof. Leticia Winkler
Representação do Nó
Prof. Leticia Winkler
	Um nó da lista é representado por uma estrutura (struct), que deverá conter, no mínimo, três campos : um campo com a informação ou dado a ser armazenado e dois ponteiros: um para o próximo nó da lista e outro para o nó anterior.
prox
ant
	É preciso que o primeiro nó seja apontado por um ponteiro, assim como o último, para que assim, a lista possa ser manipulada através de suas diversas operações.
primeiro	último
Prof. Leticia Winkler
Representação do Nó
	struct noDupla { tipo info1; tipo info2;
	...
	(struct) no *nomePonteiro1, *nomePonteiro2;
Prof. Leticia Winkler
};
	Exemplo:
struct noDupla { int dado;
struct noDupla *prox; // ponteiro p/ à direita
struct noDupla *ant;	// ponteiro p/ à esquerda
};
prox
10
ant
Prof. Leticia Winkler
Operações com Listas Duplamente Encadeadas
Prof. Leticia Winkler
*
	Criação
	Inicialização
	Inserção (no início, no fim, após um determinado valor, etc...)
	Percurso (mostrar a lista – de trás para frente; de frente para trás)
	Substituição de um valor por outro
	Remoção (do primeiro nó,	do último nó, de um nó em particular, etc..)
	Busca ou pesquisa de forma sequencial
	Exemplos de aplicações com listas duplamente encadeadas: todos os já mencionados para listas lineares.
Prof. Leticia Winkler
Criação e Inicialização da Lista
Prof. Leticia Winkler
	Declara-se o ponteiro para o primeiro nó da lista e o ponteiro para o último nó da lista. Aqui chamado de l2i e de l2f respectivamente.
// criação
noDupla *l2i; // ponteiro para o primeiro elemento da lista
noDupla *l2f; // ponteiro para o último elemento da lista
l2i = l2f = NULL;	// inicialização
l2i
l2f
*
Prof. Leticia Winkler
Exemplo
Prof. Leticia Winkler
	Construir uma lista com um nó apenas com o valor 10:
novo = new noDupla;
novo->dado = valor; novo->prox = NULL; novo->ant = NULL;
l2i = novo; l2f = novo;
Lista com um
nó apenas
l2f
10
l2i
10
*
Prof. Leticia Winkler
Exemplo
	Inserindo mais um nó na lista (antes do primeiro nó – inserir na frente)
novo = new noDupla;
novo-> dado = 20;
novo-> prox = l2i;
l2f
10
20
l2f
l2i
10
20
l2f
l2i
10
novo	l2i
*
novo
novo
Exemplo
	Inserindo mais um nó na lista (antes do primeiro nó – inserir na frente)
l2i->ant = novo;
l2i = novo;
Lista com
mais um nó
20
l2f
10
novo	l2i
20
l2f
l2i
10
*
Código da Inserção no Início
Prof. Leticia Winkler
*
void inserirInic(int valor) {
// cria um novo no
noDupla *novo = new noDupla;
novo->dado = valor; novo->prox = NULL; novo->ant = NULL;
// inserindo no inicio da lista if (l2i != NULL) {
novo->prox = l2i; l2i->ant = novo;
}
else
l2f = novo; l2i = novo;
}
Prof. Leticia Winkler
Remoção
Prof. Leticia Winkler
*
	Retirada de um nó da lista
	Antes deve-se verificar se a lista não está vazia.
	Como se sabe se uma lista duplamente encadeada está vazia?
Prof. Leticia Winkler
Verificando se a Lista Encadeada está Vazia
Prof. Leticia Winkler
*
	Verifica-se se o ponteiro para o primeiro elemento da lista está apontando para algum nó
if (l2i == NULL) {
cout << "\nLista vazia!!!\n\n";
}
	Ou, usando uma função:
bool estaVazia() { return (l2i == NULL);
}
Prof. Leticia Winkler
Removendo o primeiro da Lista
Prof. Leticia Winkler
*
	Guarda nó a ser removido através de um ponteiro
auxiliar
	Ponteiro para o inicio da lista (primeiro) aponta para o próximo da lista
20
l2f
l2i
10
20
l2f
10
l2i	aux
aux
Prof. Leticia Winkler
Removendo o primeiro da Lista
Prof. Leticia Winkler
*
	Ponteiro anterior do início da lista é aterrado
	Remove nó apontado pelo auxiliar
20
l2i
10
aux	l2f
20
l2i
10
aux	l2f
l2f
l2i
10
Prof. Leticia Winkler
Código da Remoção de um nó do Início
Prof. Leticia Winkler
*
noDupla* removerInic () { noDupla *aux = l2i;
l2i = l2i->prox;
if (l2i == NULL) // se foi removido o ultimo elemento que existia na lista l2f = NULL; // ultimo tb ficara apontando para nada
else
l2i->ant = NULL; return aux;
}
Prof. Leticia Winkler
Percorrer a Lista (mostrar)
Prof. Leticia Winkler
*
	Verifica-se se a lista não está vazia
	Usando um ponteiro auxiliar (aqui chamado de atual) percorre-se a lista a partir do primeiro (l2i)
	Move-se o ponteiro auxiliar pela lista:
atual= atual-> prox;
atual
10
20
40
l2i
30
l2f
atual
10
20
40
l2i
30
l2f
Prof. Leticia Winkler
Código para Percorrer (frente para traz)
Prof. Leticia Winkler
*
void percorrerFrenteTraz () {
noDupla *atual; // ponteiro para percorrer a lista
atual = l2i;
cout << "\nLista => "; while (atual != NULL) {
cout << atual->dado << "\t"; atual = atual->prox;
}
cout << endl;
}
Prof. Leticia Winkler
1 ) Criar um programa para manter uma lista de temas para os trabalhos de uma faculdade. Cada  tema deve ter as seguintes informações:
Nome - char[80]
Descrição - char[400]
	Criar uma estrutura tema para representar um tema de trabalho com os campos acima.
	Criar um ponteiro para estrutura tema para representar uma lista
	O programa deve exibir ao usuário um menu com as opções para:
Incluir um Tema
Remover um Tema
Navegar pelos Temas com opção para ver o próximo tema  e o tema anterior.
Pesquisar um Tema pelo nome
	Sair do Programa
Crie o programa em C com base no exemplo que foi apresentado em aula e no exercício sobre Lista encadeada simples.
COMENTE TODAS AS LINHAS...
*
EXEMPLO UTILIZANDO METODOLOGIA ATIVA - SEGUE A RESPOSTA NA PRÓXIMA PÁGINA
*
#include <stdio.h>
#include <stdlib.h>
struct lista2 {
 int info;
 struct lista2* ant;
 struct lista2* prox;
};
typedef struct lista2 Lista2;
/* inserção no início - Recebe como parametro a lista e o valor inteiro a ser inserido no início da lista */
Lista2* insere (Lista2* l, int v) {
 /* Cria um novo elemento na lista com */
 Lista2* novo = (Lista2*) malloc(sizeof(Lista2));
 /* Preenche o campo info do novo elemento criado com o valor inteiro */
 novo->info = v;
 /* O novo elemento aponta para o inicio da lista. Lembre que a lista na verdade é um ponteiro para o primeiro elemento, assim o novo elemento ao ser incluido no inicio da lista deve apontar para o proximo que é o inicio da lista, ou seja, aquele que era o primeiro elemento da lista anteriormente */
 novo->prox = l;
 /* Como o novo elemento é inserido no inicio da lista, não há elemento anterior. Por isso, armazena a constante NULL no ponteiro que aponta para o elemento anterior*/
 novo->ant = NULL;/* verifica se lista não está vazia */
 if (l != NULL)
 l->ant = novo;
 return novo;
}
/* função consutla: consulta os elementos da lista */
void consulta (Lista2* l) {
 Lista2* p;
 for (p=l; p!=NULL; p=p->prox)
 printf("\n Valor %d ", p->info);
}
/* função busca: busca um elemento na lista */
Lista2* busca (Lista2* l, int v) {
 Lista2* p;
 for (p=l; p!=NULL; p=p->prox)
 if (p->info == v)
 return p;
 return NULL;
 /* não achou o elemento */
}
/* função retira: retira elemento da lista */
Lista2* excluir (Lista2* l, int v) {
 /* Busca o elemento a ser removido da lista */
 Lista2* p = busca(l,v);
 /* se não achou o elemento: retorna lista inalterada */
 if (p == NULL)
 return l;
/* se o elemento a ser retirado da lista for o primeiro elemento da lista entao o primeiro elemento da lista sera o proximo elemento */
 if (l == p) {
 p->prox->ant = NULL;
 l = p->prox;
 }
 else
 /* se o elemento a ser retirado da lista nao for o primeiro da lista entao o elemento anterior deve apontar para o elemento que esta sendo apontado pelo elemento a ser retirado */
 p->ant->prox = p->prox;
 /* Se o elemento a ser retirado nao for o ultimo, entao o proximo elemento deve apontar para o elemento anterior ao elemento a ser retirado */
 if (p->prox != NULL)
 p->prox->ant = p->ant;
 /* Efetivamente remove o elemento da memoria. Note que o elemento já não faz mais parte da lista pois nao e mais referenciado na lista */
 free(p);
 /* Retorna a lista atualizada */
 return l;
}
/* função que verifica o estado da lista: retorno 1 se vazia ou 0 se não vazia*/
int lista_vazia(Lista2 *lista) {
 if(lista == NULL)
 return 1;
 else
 return 0;
}
/*função responsável por criar a lista*/
Lista2* cria(void) {
 return NULL;
}
int main()
{
/* Variaveis para opcao do menu, para o elemento a ser excluido e para o elemento a ser localizado pela busca */
int op, vremover, vbuscar, v;
/* Variavel para apontar para o primeiro elemento da lista */
Lista2 *lista;
/* Cria a lista inicialmente vazia */
lista = cria();
/* Enquanto o usuario nao escolher a opcao 5 para sair do programa, as opções escolhidas sao executadas */
while(op != 5) {
/* Imprime o menu principal do programa */
system("cls");
printf("\nPrograma Para Manipulacao de Listas Duplamente Encadeada");
printf("\n1 - Inserir no Final da Lista");
printf("\n2 - Visualizar Lista");
printf("\n3 - Buscar Elemento na Lista");
printf("\n4 - Excluir Elemento");
printf("\n5 - Sair do Programa");
/* Le a opcao do usuario */
printf("\nEntre com a Opcao Desejada: ");
scanf("%i",&op);
/* Conforme a opção escolhida execuca a funcao solicitada que pode ser para inserir, listar, buscar ou remover um elemento da lista */
switch(op) {
case 1:
printf("\n Entre com o valor: ");
scanf("%d", &v);
lista = insere(lista, v);
break;
case 2:
consulta(lista);
break;
case 3:
printf("Entre com o valor que se deseja buscar: ");
scanf("%d",&vbuscar);
busca(lista,vbuscar);
break;
case 4:
printf("Entre com o valor que deseja remover: ");
scanf("%i",&vremover);
lista = excluir(lista, vremover);
break;
case 5:
exit(1);
}
}
}
*
1. ASCENCIO , Ana Fernanda Gomes; ARAUJO, Graziela Santos. Estrutura de Dados: algoritmos, analise da complexidade e implementações
em Java e C/C++. São Paulo. Pearson. 2010
2. PUGA, Sandra; RISSETTI, Gerson Logica de Programação e Estruturas de Dados - Com Aplicações em Java - 3? Ed. Pearson. 2010.
3. TAMASSIA, Roberto; GOODRICH, Michael T., Estruturas de Dados e Algoritmos em Java [recurso eletrônico, Minha Biblioteca]. Porto
Alegre: Grupo A, 2011.
BIBLIOGRAFIA BÁSICA