Listas lineares
Denise Guliato
Faculdade de Computação – UFU
www.facom.ufu.br/~guliato
Vários slides foram adaptados de Nina Edelwais e Renata Galante
Estrutura de Dados – Série de Livros Didáticos - Informática - UFRGS
Listas lineares
Listas lineares
duplamente encadeadas
Crédito do slide para Nina Edelwais e Renata Galante
Denise Guliato
LL duplamente encadeadas
LL duplamente encadeadas
• Cada nodo tem 2 campos de elo
• A lista pode ser percorrida nas duas direções
Anterior
Info
Próximo
Nodo genérico
PtLista
L1
L2
Crédito do slide para Nina Edelwais e Renata Galante
L3
L4
Denise Guliato
LL duplamente encadeadas
Operações
• Criar e inicializar uma lista
• Inserir novo nodo
• Remover um nodo
Algoritmos
• Consultar um nodo
• Destruir lista
Semelhantes a LL encadeada simples
Tipo de nodo utilizado nos algoritmos:
struct no {
struct no* ant;
int info;
struct no* prox;
}
typedef struct no Lista;
Algoritmo: criar lista circular
Lista* Cria_lista(void)
Lista* Cria_lista(void)
{
return NULL;
}
LL duplamente encadeadas
Inserção de um novo nodo no meio da
lista
Novo nodo
PtLista
L5
L1
L2
PtLista
L4
L3
L5
L1
L2
Crédito do slide para Nina Edelwais e Renata Galante
L3
L4
Denise Guliato
Inserção de um novo nodo no
inicio da lista
PtLista
L5
L1
L2
L4
L3
PtLista
L5
L1
Adaptado de Nina Edelwais e Renata Galante
L2
L3
L4
Denise Guliato
Algoritmo: inserir um nodo no inicio da lista
Lista* Insere_elem(Lista* Ptl,int elem)
Lista* Insere_elem(Lista *Ptl, int elem)
{
Lista *Ptnodo;
Ptnodo = (Lista*)malloc(sizeof(Lista));
if (Ptnodo == NULL)
return Ptl;
Ptnodo->info = elem;
Ptnodo->prox = Ptl;
Ptnodo->ant = NULL;
if(Ptl != NULL)
Ptl->ant = Ptnodo;
Ptl = Ptnodo;
return Ptl;
}
Remoção de novo nodo
PtLista
LL duplamente encadeadas
Remover
A
B
C
D
A
B
C
D
PtLista
Crédito do slide para Nina Edelwais e Renata Galante
Denise Guliato
Algoritmo:Remover
um nodo de LL Duplamente Encadeada
Lista* Remove_elem(Lista *Ptl, int elem)
Lista* Remove_elem(Lista *Ptl, int elem)
{
Lista *atual;
if (Ptl == NULL)
return Ptl;
atual = Ptl;
while (atual != NULL && elem != atual->info)
{
atual = atual->prox;
}
if (atual == NULL)// não achou
return Ptl;
if (atual == Ptl)// primeiro nodo a ser removido
Ptl = atual->prox;
else // nodo removido do meio ou do final da lista
atual->ant->prox = atual->prox;
if (atual->prox != NULL)
atual->prox->ant = atual->ant;
free(atual);
return Ptl;
}
Consulta à lista
LL duplamente encadeadas
• Acesso sempre pelo primeiro nodo da lista
• A lista pode ser percorrida nas duas direções
Adaptado de Nina Edelwais e Renata Galante
Denise Guliato
Algoritmo: Consulta K-esimo nodo da Lista
LL encadeada circular
int Consulta_nodo(Lista Ptl, int pos,int *elem)
int Consulta_nodo(Lista *Ptl, int pos, int *elem)
{
int cont = 1;
Lista *pt;
pt = Ptl;
if (pos <= 0 || pt == NULL)
return 0;
while(pt != NULL && cont < pos)
{
pt=pt->prox;
cont++;
}
if (pt == NULL)
return 0;
else {
*elem=pt->info;
return 1;
}
}
Algoritmo: destruir lista circular
Lista* Libera_lista(Lista *Ptl)
Lista* Libera_lista(Lista *Ptl)
{
Lista
*aux;
while (Ptl!= NULL)
{
aux = Ptl;
Ptl = Ptl->prox;
free(aux);
}
return NULL;
}
lladae2d.h
typedef struct no Lista;
Lista* Cria_lista(void);
Lista* Libera_lista(Lista* Ptl);
int E_vazia(Lista* Ptl);
int E_cheia(Lista* Ptl);
Lista* Insere_elem(Lista* Ptl, int elem);
Lista* Remove_elem(Lista* Ptl, int elem);
int Tamanho_lista(Lista* Ptl);
int Consulta_nodo(Lista* Ptl, int pos, int *elem);
#include <stdio.h>
#include <stdlib.h>
#include "lladae2d.h“
struct no {
struct no* ant;
int info;
struct no* prox;
};
Lista* Cria_lista(void)
{……..}
Lista* Libera_lista(Lista *Ptl)
{…….}
int E_vazia(Lista *Ptl)
{…….}
int E_cheia(Lista *Ptl)
{…….}
Lista* Insere_elem(Lista *Ptl, int elem)
{.......}
Lista* Remove_elem(Lista *Ptl, int elem)
{.......}
int Tamanho_lista(Lista Ptl)
{…….}
int Consulta_nodo(Lista *Ptl, int pos,int *elem)
{……}
lladae2d.c
LL duplamente encadeada circular
Considere uma Lista duplamente
encadeada circular
PtLista
L1
L2
L3
L4
Exercício
Implemente o TAD Lista para a lista circular
duplamente encadeada. Teste no programa do
jogo baseado no problema de Josephus