Apostila Lista Circular

Prévia do material em texto

14/04/2016 
1 
Estrutura de Dados 
 
Lista Circular 
Profa. Dra. Jaqueline Brigladori Pugliesi 
Lista Circular 
 Uma lista encadeada circular é uma 
lista encadeada cujo último elemento 
aponta para o primeiro. 
 Vantagem: cada elemento é acessível 
a partir de qualquer outro. 
 Numa lista circular, não faz mais 
sentido se falar em primeiro ou último 
elemento. 
Profa. Dra. Jaqueline Brigladori Pugliesi 
14/04/2016 
2 
Lista Circular 
 Porém, deve-se saber, durante um 
percurso na lista, se já ocorreu uma 
volta completa, para evitar loops 
infinitos. 
 Para isso, assume-se a existência de 
um registro especial, chamado 
Cabeça de lista, cujo campo de 
informação não pertence ao conjunto 
de elementos da lista (pode servir de 
sentinela numa busca). 
Profa. Dra. Jaqueline Brigladori Pugliesi 
Lista Circular 
Profa. Dra. Jaqueline Brigladori Pugliesi 
8 10 
Cabeça 
12 
14/04/2016 
3 
Lista Circular 
 Então, não se verifica o final de lista 
como: 
 (p->prox == NULL) ou 
(p == NULL) 
 
 Mas sim se p, que começou em 
cabeca->prox, retornou à cabeca 
 
Profa. Dra. Jaqueline Brigladori Pugliesi 
Função para inserir um elemento no 
início da lista. 
void insere_inicio(struct no *cabeca, int x){ 
 struct no *p; 
 if((p=malloc(sizeof(struct no))) == NULL){ 
 printf("Erro alocacao de memoria!"); 
 } 
 else{ 
 p->info = x; 
 p->prox = cabeca->prox; 
 cabeca->prox = p; 
 } 
} 
Profa. Dra. Jaqueline Brigladori Pugliesi 
14/04/2016 
4 
Função para imprimir uma lista. 
void imprimir(struct no *cabeca) { 
 struct no *p; 
 p = cabeca->prox; 
 while(p != cabeca){ 
 printf("%d ", p->info); 
 p = p->prox; 
 } 
} 
Profa. Dra. Jaqueline Brigladori Pugliesi 
Função que busca um elemento em 
lista circular não ordenada. 
void busca_circular(struct no *cabeca, int x) 
{ 
 struct no *p; 
 cabeca->info = x; 
 p = cabeca->prox; 
 while(p->info != x) 
 p = p->prox; 
 if(p == cabeca) 
 printf("Elemento não encontrado!\n"); 
 else 
 printf("Elemento encontrado!\n"); 
} 
 
Profa. Dra. Jaqueline Brigladori Pugliesi 
14/04/2016 
5 
Exercícios 
 Fazer as seguintes funções para lista 
circular (com sentinela): 
◦ Remover o primeiro elemento da lista e 
retornar o valor. 
◦ Contar o número de elementos da lista. 
◦ Remover um dado elemento da lista, 
fornecido pelo usuário. 
◦ Concatenar duas listas circulares. 
 
Profa. Dra. Jaqueline Brigladori Pugliesi 
FIM 
Profa. Dra. Jaqueline Brigladori Pugliesi