Aula 5 Lista Dinamica circular

Prévia do material em texto

Aula
Estrutura de dados
Listas ligada dinâmica circular
Prof. Cenez Araújo de Rezende
Unifor
Universidade de Fortaleza
Fortaleza/CE, Brasil
 
Agenda
- Listas dinâmica ligada circular
 
Listas ligada dinâmica circular
Aula
 4
Estrutura de dados
Lista ligada circular
● É uma extensão da lista dinâmica simples
– É circular, pois o último elemento aponta para 
o primeiro
– Possui nó cabeça: um elemento inicial que 
marca o inicio da lista
– Ponteiro para nó cabeça
– Elementos indicam sucessores, onde o último 
tem como sucessor o nó cabeça
 5
Estrutura de dados
Lista ligada circular
● Como funciona?
cabeca
3020
6
6420
2020
4060
10
2020
5290
9
4060
6420
8
5290
2020
3020
 6
Estrutura de dados
Lista ligada circular
● Exclusão do 9?
cabeca
3020
6
6420
2020
4060
10
2020
5290
9
4060
6420
8
5290
2020
3020
 7
Estrutura de dados
Lista ligada circular
● Inserir o 1?
cabeca
3020
6
6420
2020
4060
10
2020
6420
8
4060
2020
3020
 8
Estrutura de dados
Lista ligada circular
● Inserir o 1?
cabeca
3020
6
6420
2020
4060
10
2020
6420
8
4060
2020
5290
5290
1
3020
 9
Estrutura de dados
Lista ligada circular
● Estrutura
#include <stdio.h>
#include <malloc.h>
#define false 0
#define true 1
typedef int bool;
typedef int KEY;
typedef struct {
KEY chave;
} REGISTRO;
typedef struct aux {
REGISTRO reg;
struct aux* prox;
} ELEMENTO, *PONT;
typedef struct {
PONT cabeca;
} LISTA;
 10
Estrutura de dados
Lista ligada circular
● Iniciar
– Cria-se o nó cabeça
– Cabeça se aponta
● Nó cabeça tem o prox apontando para ele 
mesmo
typedef struct {
KEY chave;
} REGISTRO;
typedef struct aux {
REGISTRO reg;
struct aux* prox;
} ELEMENTO, *PONT;
typedef struct {
PONT cabeca;
} LISTA;
 11
Estrutura de dados
Lista ligada circular
● Iniciar
typedef struct {
KEY chave;
} REGISTRO;
typedef struct aux {
REGISTRO reg;
struct aux* prox;
} ELEMENTO, *PONT;
typedef struct {
PONT cabeca;
} LISTA;
void initialize(LISTA *l){
l->cabeca = (PONT) malloc(sizeof(ELEMENTO));
l->cabeca->prox = l->cabeca;
}
 12
Estrutura de dados
Lista ligada circular
● Contar
– Como não existe variável “qtd”, teremos que 
percorrer toda a estrutura para contar
– Nó cabeça não é visto como elemento válido 
para contagem. Ou seja, não entra na conta
typedef struct {
KEY chave;
} REGISTRO;
typedef struct aux {
REGISTRO reg;
struct aux* prox;
} ELEMENTO, *PONT;
typedef struct {
PONT cabeca;
} LISTA;
 13
Estrutura de dados
Lista ligada circular
● Contar
typedef struct {
KEY chave;
} REGISTRO;
typedef struct aux {
REGISTRO reg;
struct aux* prox;
} ELEMENTO, *PONT;
typedef struct {
PONT cabeca;
} LISTA;
int count(LISTA *l){
PONT fim = l->cabeca->prox;
int tamanho = 0;
while(fim != l->cabeca) {
tamanho++;
fim = fim->prox;
}
return tamanho;
}
 14
Estrutura de dados
Lista ligada circular
● Imprimir
typedef struct {
KEY chave;
} REGISTRO;
typedef struct aux {
REGISTRO reg;
struct aux* prox;
} ELEMENTO, *PONT;
typedef struct {
PONT cabeca;
} LISTA;
int print(LISTA *l){
PONT fim = l->cabeca->prox;
printf("Lista: ");
while(fim != l->cabeca) {
printf("%i ", fim->reg.chave);
fim = fim->prox;
}
printf("\n");
}
 15
Estrutura de dados
Lista ligada circular
● Busca
– Utiliza-se o nó cabeça como sentinela
● Isso significa que cabeça guardará 
temporariamente um valor de chave para 
auxiliar na busca, já que ele não atua como 
elemento válido
typedef struct {
KEY chave;
} REGISTRO;
typedef struct aux {
REGISTRO reg;
struct aux* prox;
} ELEMENTO, *PONT;
typedef struct {
PONT cabeca;
} LISTA;
 16
Estrutura de dados
Lista ligada circular
● Busca
typedef struct {
KEY chave;
} REGISTRO;
typedef struct aux {
REGISTRO reg;
struct aux* prox;
} ELEMENTO, *PONT;
typedef struct {
PONT cabeca;
} LISTA;
PONT buscaSentinela(LISTA *l, KEY chave) {
PONT pos = l->cabeca->prox;
l->cabeca->reg.chave = chave; //sentinela guarda chave
while(pos->reg.chave != chave) pos = pos->prox;
if(pos != l->cabeca) return pos;
return NULL;
}
 17
Estrutura de dados
Lista ligada circular
● Busca considerando lista ordenada
typedef struct {
KEY chave;
} REGISTRO;
typedef struct aux {
REGISTRO reg;
struct aux* prox;
} ELEMENTO, *PONT;
typedef struct {
PONT cabeca;
} LISTA;
PONT buscaSentinela(LISTA *l, KEY chave) {
PONT pos = l->cabeca->prox;
l->cabeca->reg.chave = chave; //sentinela guarda chave
while(pos->reg.chave != chave) pos = pos->prox;
if(pos != l->cabeca) return pos;
return NULL;
}
PONT buscaSentinelaComOrdem(LISTA *l, KEY chave) {
PONT pos = l->cabeca->prox;
l->cabeca->reg.chave = chave; //sentinela guarda chave
while(pos->reg.chave < chave) pos = pos->prox;
if(pos != l→cabeca && pos->reg.chave==chave) return pos;
return NULL;
}
Só altera-se aqui
 18
Estrutura de dados
Lista ligada circular
● Inserção de chave
– Vamos inserir em ordem
– Sem chaves duplicadas
– Identificar local de inserção
● Entre quais elementos o novo elemento 
estará?
– Alocar endereço para novo elemento
– É necessário conhecer predecessor
typedef struct {
KEY chave;
} REGISTRO;
typedef struct aux {
REGISTRO reg;
struct aux* prox;
} ELEMENTO, *PONT;
typedef struct {
PONT cabeca;
} LISTA;
 19
Estrutura de dados
Lista ligada circular
● Inserção de chave
– Usaremos nossa função auxiliar
● buscaAtualAnt(...)
● Útil para ordem
typedef struct {
KEY chave;
} REGISTRO;
typedef struct aux {
REGISTRO reg;
struct aux* prox;
} ELEMENTO, *PONT;
typedef struct {
PONT cabeca;
} LISTA;
 20
Estrutura de dados
Lista ligada circular
● Inserção de chave
typedef struct {
KEY chave;
} REGISTRO;
typedef struct aux {
REGISTRO reg;
struct aux* prox;
} ELEMENTO, *PONT;
typedef struct {
PONT cabeca;
} LISTA;
PONT buscaAtualAnt(LISTA *l, KEY chave, PONT *ant){
*ant = l->cabeca;
PONT atual = l->cabeca->prox;
l->cabeca->reg.chave = chave;
while (atual->reg.chave < chave) {
*ant = atual;
atual = atual->prox;
}
if (atual!=l->cabeca && atual->reg.chave==chave) return atual;
return NULL;
}
bool addEmOrdem(LISTA *l, REGISTRO reg) {
PONT ant, i;
i = buscaAtualAnt(l, reg.chave, &ant);
if(i!=NULL) return false;//já existe na lista
i = (PONT) malloc(sizeof(ELEMENTO));
i->reg = reg;
i->prox = ant->prox;
ant->prox = i;
return true;
}
 21
Estrutura de dados
Lista ligada circular
● Inserção de chave
typedef struct {
KEY chave;
} REGISTRO;
typedef struct aux {
REGISTRO reg;
struct aux* prox;
} ELEMENTO, *PONT;
typedef struct {
PONT cabeca;
} LISTA;
PONT buscaAtualAnt(LISTA *l, KEY chave, PONT *ant){
*ant = l->cabeca;
PONT atual = l->cabeca->prox;
l->cabeca->reg.chave = chave;
while (atual->reg.chave < chave) {
*ant = atual;
atual = atual->prox;
}
if (atual!=l->cabeca && atual->reg.chave==chave) return atual;
return NULL;
}
bool addEmOrdem(LISTA *l, REGISTRO reg) {
PONT ant, i;
i = buscaAtualAnt(l, reg.chave, &ant);
if(i!=NULL) return false;//já existe na lista
i = (PONT) malloc(sizeof(ELEMENTO));
i->reg = reg;
i->prox = ant->prox;
ant->prox = i;
return true;
}
 22
Estrutura de dados
Lista ligada circular
● Inserção de chave
typedef struct {
KEY chave;
} REGISTRO;
typedef struct aux {
REGISTRO reg;
struct aux* prox;
} ELEMENTO, *PONT;
typedef struct {
PONT cabeca;
} LISTA;
PONT buscaAtualAnt(LISTA *l, KEY chave, PONT *ant){
*ant = l->cabeca;
PONT atual= l->cabeca->prox;
l->cabeca->reg.chave = chave;
while (atual->reg.chave < chave) {
*ant = atual;
atual = atual->prox;
}
if (atual!=l->cabeca && atual->reg.chave==chave) return atual;
return NULL;
}
bool addEmOrdem(LISTA *l, REGISTRO reg) {
PONT ant, i;
i = buscaAtualAnt(l, reg.chave, &ant);
if(i!=NULL) return false;//já existe na lista
i = (PONT) malloc(sizeof(ELEMENTO));
i->reg = reg;
i->prox = ant->prox;
ant->prox = i;
return true;
}
 23
Estrutura de dados
Lista ligada circular
● Inserção de chave
typedef struct {
KEY chave;
} REGISTRO;
typedef struct aux {
REGISTRO reg;
struct aux* prox;
} ELEMENTO, *PONT;
typedef struct {
PONT cabeca;
} LISTA;
PONT buscaAtualAnt(LISTA *l, KEY chave, PONT *ant){
*ant = l->cabeca;
PONT atual = l->cabeca->prox;
l->cabeca->reg.chave = chave;
while (atual->reg.chave < chave) {
*ant = atual;
atual = atual->prox;
}
if (atual!=l->cabeca && atual->reg.chave==chave) return atual;
return NULL;
}
bool addEmOrdem(LISTA *l, REGISTRO reg) {
PONT ant, i;
i = buscaAtualAnt(l, reg.chave, &ant);
if(i!=NULL) return false;//já existe na lista
i = (PONT) malloc(sizeof(ELEMENTO));
i->reg = reg;
i->prox = ant->prox;
ant->prox = i;
return true;
}
 24
Estrutura de dados
Lista ligada circular
● Inserção de chave
typedef struct {
KEY chave;
} REGISTRO;
typedef struct aux {
REGISTRO reg;
struct aux* prox;
} ELEMENTO, *PONT;
typedef struct {
PONT cabeca;
} LISTA;
PONT buscaAtualAnt(LISTA *l, KEY chave, PONT *ant){
*ant = l->cabeca;
PONT atual = l->cabeca->prox;
l->cabeca->reg.chave = chave;
while (atual->reg.chave < chave) {
*ant = atual;
atual = atual->prox;
}
if (atual!=l->cabeca && atual->reg.chave==chave) return atual;
return NULL;
}
bool addEmOrdem(LISTA *l, REGISTRO reg) {
PONT ant, i;
i = buscaAtualAnt(l, reg.chave, &ant);
if(i!=NULL) return false;//já existe na lista
i = (PONT) malloc(sizeof(ELEMENTO));
i->reg = reg;
i->prox = ant->prox;
ant->prox = i;
return true;
}
 25
Estrutura de dados
Lista ligada circular
● Inserção de chave
typedef struct {
KEY chave;
} REGISTRO;
typedef struct aux {
REGISTRO reg;
struct aux* prox;
} ELEMENTO, *PONT;
typedef struct {
PONT cabeca;
} LISTA;
PONT buscaAtualAnt(LISTA *l, KEY chave, PONT *ant){
*ant = l->cabeca;
PONT atual = l->cabeca->prox;
l->cabeca->reg.chave = chave;
while (atual->reg.chave < chave) {
*ant = atual;
atual = atual->prox;
}
if (atual!=l->cabeca && atual->reg.chave==chave) return atual;
return NULL;
}
bool addEmOrdem(LISTA *l, REGISTRO reg) {
PONT ant, i;
i = buscaAtualAnt(l, reg.chave, &ant);
if(i!=NULL) return false;//já existe na lista
i = (PONT) malloc(sizeof(ELEMENTO));
i->reg = reg;
i->prox = ant->prox;
ant->prox = i;
return true;
}
 26
Estrutura de dados
Lista ligada circular
● Inserção de chave
typedef struct {
KEY chave;
} REGISTRO;
typedef struct aux {
REGISTRO reg;
struct aux* prox;
} ELEMENTO, *PONT;
typedef struct {
PONT cabeca;
} LISTA;
PONT buscaAtualAnt(LISTA *l, KEY chave, PONT *ant){
*ant = l->cabeca;
PONT atual = l->cabeca->prox;
l->cabeca->reg.chave = chave;
while (atual->reg.chave < chave) {
*ant = atual;
atual = atual->prox;
}
if (atual!=l->cabeca && atual->reg.chave==chave) return atual;
return NULL;
}
bool addEmOrdem(LISTA *l, REGISTRO reg) {
PONT ant, i;
i = buscaAtualAnt(l, reg.chave, &ant);
if(i!=NULL) return false;//já existe na lista
i = (PONT) malloc(sizeof(ELEMENTO));
i->reg = reg;
i->prox = ant->prox;
ant->prox = i;
return true;
}
 27
Estrutura de dados
Lista ligada circular
● Inserção de chave
typedef struct {
KEY chave;
} REGISTRO;
typedef struct aux {
REGISTRO reg;
struct aux* prox;
} ELEMENTO, *PONT;
typedef struct {
PONT cabeca;
} LISTA;
PONT buscaAtualAnt(LISTA *l, KEY chave, PONT *ant){
*ant = l->cabeca;
PONT atual = l->cabeca->prox;
l->cabeca->reg.chave = chave;
while (atual->reg.chave < chave) {
*ant = atual;
atual = atual->prox;
}
if (atual!=l->cabeca && atual->reg.chave==chave) return atual;
return NULL;
}
bool addEmOrdem(LISTA *l, REGISTRO reg) {
PONT ant, i;
i = buscaAtualAnt(l, reg.chave, &ant);
if(i!=NULL) return false;//já existe na lista
i = (PONT) malloc(sizeof(ELEMENTO));
i->reg = reg;
i->prox = ant->prox;
ant->prox = i;
return true;
}
 28
Estrutura de dados
Lista ligada circular
● Exclusão
– Verificar se existe elemento pela chave
– Caso exista, excluir e acertar ponteiros
● Retorna true
– Caso não exista
● Retorna false
– É necessário saber quem é o antecessor
typedef struct {
KEY chave;
} REGISTRO;
typedef struct aux {
REGISTRO reg;
struct aux* prox;
} ELEMENTO, *PONT;
typedef struct {
PONT cabeca;
} LISTA;
 29
Estrutura de dados
Lista ligada circular
● Exclusão
typedef struct {
KEY chave;
} REGISTRO;
typedef struct aux {
REGISTRO reg;
struct aux* prox;
} ELEMENTO, *PONT;
typedef struct {
PONT cabeca;
} LISTA;
bool excluir(LISTA *l, KEY chave) {
PONT ant, i;
i = buscaAtualAnt(l, chave, &ant);
if(i == NULL) return false;
ant->prox = i->prox;
free(i);
return true;
}
 30
Estrutura de dados
Lista ligada circular
● Reinicializar
– Excluir TODOS os elementos válidos
– Atualizar o “prox” do nó cabeça
typedef struct {
KEY chave;
} REGISTRO;
typedef struct aux {
REGISTRO reg;
struct aux* prox;
} ELEMENTO, *PONT;
typedef struct {
PONT cabeca;
} LISTA;
 31
Estrutura de dados
Lista ligada circular
● Reinicializar
typedef struct {
KEY chave;
} REGISTRO;
typedef struct aux {
REGISTRO reg;
struct aux* prox;
} ELEMENTO, *PONT;
typedef struct {
PONT cabeca;
} LISTA;void reinicializar(LISTA *l) {
PONT fim = l->cabeca->prox;
while(fim != l->cabeca) {
PONT apagar = fim;
fim = fim->prox;
free(apagar);
}
l->cabeca->prox = l->cabeca;
}
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31