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
Lista encadeada
circular
LL encadeada circular
LL encadeada circular
PtLista
L1
L2
L3
L4
• Elo do último nodo indica endereço do primeiro
• Lista pode ser percorrida a partir de qualquer nodo
• Lista com 1 só nodo: elo do nodo aponta para ele mesmo
PtLista
L1
Crédito do slide para Nina Edelwais e Renata Galante
Denise Guliato
Operações básicas
• Criar uma lista
• Inserir novo nodo
• Remover um nodo
• Consulta um nodo
• Destruir lista
LL encadeada circular
Algoritmos
Semelhantes a LL encadeada simples
Crédito do slide para Nina Edelwais e Renata Galante
Denise Guliato
Algoritmo: criar lista circular
Lista* Cria_lista(void)
Lista* Cria_lista(void)
{
return NULL;
}
Inserção de um novo nodo
LL encadeada circular
• Definir a posição de inserção
• Alocar o novo nodo
• Preencher com valor
• Encadear adequadamente
Crédito do slide para Nina Edelwais e Renata Galante
Denise Guliato
Inserção de um novo nodo num
dos extremos da lista
Inserir um nodo em uma lista circular vazia
Ptlista
Ptlista
L1
Inserção de um novo nodo num
dos extremos da lista
Onde inserir ????
Inserção de um novo nodo no inicio da lista
Ptlista
L1
L2
L3
L4
L1
L2
L3
L4
Ptlista
Inserção de um novo nodo num
dos extremos da lista
Onde inserir ????
Inserção de um novo nodo no final da lista
Ptlista
L1
L2
L3
L4
Ptlista
L1
L2
L3
L4
Algoritmo: inserir um nodo no final da lista
Lista* Insere_elem(Lista* Ptl,int elem)
Lista* Insere_elem(Lista* Ptl, int elem)
{
Lista *Ptnodo, *aux;
Ptnodo = (Lista*)malloc(sizeof(struct no));
if (Ptnodo == NULL)
return Ptl;
Ptnodo->info = elem;
if (Ptl == NULL) // lista vazia
{
Ptl = Ptnodo;
Ptnodo->prox = Ptl;
}
else //lista nao esta vazia,insere no final
{
aux = Ptl;
while (aux->prox != Ptl)
aux = aux->prox;
Ptnodo->prox = Ptl;
aux->prox = Ptnodo;
}
return Ptl;
}
LL encadeada circular
Remoção de um nodo
• Localizar posição do nodo
• Adequar encadeamentos
• Liberar nodo
Remover
PtLista
L1
L2
L3
L1
L2
L4
L4
PtLista
Crédito do slide para Nina Edelwais e Renata Galante
Denise Guliato
Remoção de um nodo
Remover nodo de uma lista vazia
Ptlista
NÃO É POSSÍVEL
Remoção de um nodo
Remover nodo de uma lista vazia
Ptlista
NÃO É POSSÍVEL
Remover o nodo de uma lista com um único nodo
Ptlista
L1
Ptlista
Remoção de um nodo
Remover o primeiro nodo de uma lista qualquer
Remover
PtLista
L1
L2
L3
L2
L3
L4
L4
PtLista
slide adaptado de Nina Edelwais e Renata Galante
Denise Guliato
Remoção de um nodo
Remover o nodo qualquer de uma lista
Remover
PtLista
L1
L2
L3
L1
L2
L4
L4
PtLista
Slide adaptado de Nina Edelwais e Renata Galante
Denise Guliato
Remoção de um nodo
• Caso 1: lista vazia
• Caso 2:nodo a ser removido é o primeiro e único da
lista
• Caso 3:nodo a ser removido é o primeiro mas não é o
único
• Caso 4:nodo a ser removido é qualquer outro nodo
da lista
Algoritmo:
Remover um nodo de LL Encadeada Circular dado o elem
Lista* Remove_elem(Lista *Ptl, int elem)
Lista* Remove_elem(Lista* Ptl, int elem)
{
Lista *ant,*atual,*aux;
if (Ptl == NULL) //lista vazia
return Ptl;
atual = Ptl;
ant = NULL;
while (atual->prox != Ptl && atual->info != elem)
{
ant = atual;
atual = atual->prox;
}
//continua
Algoritmo (cont):
Remover nodo de LL Encadeada Circular dado o elem
if (atual->info == elem)
{
if (ant == NULL) //primeiro nodo sera removido
{
aux=Ptl;
while (aux->prox != Ptl)
aux = aux->prox; //aux aponta para o ultimo nodo da lista
if (aux == Ptl) //eh primeiro e o ultimo
Ptl = NULL;
else {
// eh o primeiro mas nao o ultimo
Ptl = atual->prox;
aux->prox = Ptl;
}
}
else ant->prox = atual->prox;
free(atual);
}
}
return Ptl;
LL encadeada circular
Consulta nodo da lista
• Iniciar sempre acessando primeiro nodo da lista
• Seguir acessando de acordo com campos de elo
• Para quando encontrar novamente o primeiro nodo da lista
PtLista
L1
Crédito do slide para Nina Edelwais e Renata Galante
L2
L3
L4
L5
Denise Guliato
Algoritmo: Consulta K-esimo nodo da Lista
int Consulta_nodo(Lista *Ptl, int pos, int*elem)
int Consulta_nodo(Lista* Ptl, int pos, int *elem)
{
int cont;
Lista *pt;
if( Ptl == NULL || pos <= 0)
return 0;
cont = 1;
pt = Ptl;
while(pt->prox != Ptl && cont < pos)
{
pt=pt->prox;
cont++;
}
if (cont == pos)
{
*elem = pt->info;
return 1;
}
else return 0;
}
Algoritmo: destruir lista circular
Lista* Libera_lista(Lista *Ptl)
Lista* Libera_lista(Lista* Ptl)
{
Lista *pt, *aux;
if (Ptl == NULL)
return NULL;
pt = Ptl;
while (pt->prox != Ptl)
{
aux = pt;
pt = pt->prox;
free(aux);
}
free(pt);
return NULL; // Ptl = NULL; return Ptl;
}
Algoritmo: destruir lista circular
int Tamanho_lista(Lista *Ptl)
int Tamanho_lista(Lista* Ptl)
{
Lista *pt;
int cont;
if (Ptl == NULL)
return 0;
pt = Ptl;
cont = 1;
while (pt->prox != Ptl)
{
pt = pt->prox;
cont++;
}
return cont;
}
Lista encadeada circular
• Podemos melhorar o custo computacional da
inserção?
• Como?
• Fazendo Ptl apontar para o ultimo nodo da
lista circular
Lista encadeada circular
• Ptlista aponta para o último nodo da lista:
Ptlista
L1
L2
L3
L4
Algoritmo: inserir um nodo no final da lista
Lista* Insere_elem(Lista* Ptl,int elem)
Lista* Insere_elem(Lista* Ptl, int elem)
{
Lista *Ptnodo;
Ptnodo = (Lista*)malloc(sizeof(struct no));
if (Ptnodo == NULL)
return Ptl;
Ptnodo->info = elem;
if (Ptl == NULL) // lista vazia
{
Ptl = Ptnodo;
Ptnodo->prox = Ptl;
}
else //lista nao esta vazia
{
Ptnodo->prox = Ptl->prox;
Ptl->prox = Ptnodo;
Ptl = Ptnodo;
}
return Ptl;
}
Lista encadeada circular
• Como ficaria a função de remoção???
Algoritmo:
Remover um nodo de LL Encadeada Circular dado o elem
int Remove_elem(Lista *Ptl, int elem)
Lista* Remove_elem(Lista* Ptl, int elem)
{
Lista *ant,*atual,*aux;
if (Ptl == NULL) //lista vazia
return Ptl;
atual = Ptl->prox;
ant = Ptl;
while (atual!= Ptl && atual->info != elem)
{
ant = atual;
atual = atual->prox;
}
}
if (atual->info == elem)
{
if (atual == ant) //único nodo
Ptl = NULL;
else {
ant->prox = atual->prox;
if (atual == Ptl) //ultimo nodo a ser removido
Ptl = ant;
}
free(atual);
}
return Ptl;
Algoritmo (cont):
Remover nodo de LL Encadeada Circular dado o elem
Exercício
(baseado no problema de Josephus)
Considere o seguinte jogo:
N pessoas identificadas por um nome e um número
inteiro estão sentadas em círculo, organizadas
aleatoriamente. Um número é sorterado no
intervalo [1,N]. A pessoa associada a este número
sai do círculo. Um novo número é sorteado.
Contando da pessoa seguinte àquela que saiu, a
enésima pessoa sai do círculo. O sorteio continua
até que reste apenas uma pessoa.
Exercício para entregar
Faça um programa que, usando a lladaec.h,
forme o circulo de pessoas, lembrando que
são N pessoas sentadas aleatoriamente.
Sorteie, a cada iteração um número, e retire
uma pessoa do círculo, conforme as regras do
jogo. A cada saída, grave em disco a posição e
o numero de quem saiu.
No final do jogo, grave o nome e o número da
pessoa que sobrou e indique seu premio ou
castigo.