A08 - Lista Circular

Prévia do material em texto

Tipo de Dados Lista
Lista Circular
ESTRUTURA DE DADOS
Objetivos de Aprendizagem
 Reconhecer o conceito de circular, 
identificando suas peculiaridades;
 Examinar as principais diferenças para 
uma lista simplesmente encadeada;
 Construir uma lista circular a partir do 
entendimento do conceito;
 Analisar operações que compõem uma 
lista circular.
Agenda
 Conceitos;
 Aplicação prática.
Operações
 Construção da lista;
 Inserção de um nó;
 Remoção de um nó;
 Percurso por todos os 
nós;
 Busca de um nó 
◦ consultar e/ou alterar;
 Obter cópia de uma lista
 Determinar o total de nós 
da lista;
 Ordenar os nós da lista;
 Destruição da lista
 Inversão de uma lista;
 E outras
Realizando em Linguagem C
Listas Lineares encadeadas Circular
 Suponha uma estrutura para os seguintes dados:
typedef struct no{
int idade;
char nome[50]; 
struct no *proximo = NULL;
} nodo;
idade
nome
*proximo
nodo
Isto não é uma variável apenas 
Um tipo (identificador alternativo) 
para estrutura no
Listas Lineares encadeadas Circular
 Inicializando um ponteiro
nodo *cabeca = NULL; 
cabeca
Nulo ou 
vazio
Listas Lineares encadeadas Circular
 Criando um nodo para a lista
nodo *cabeca = (nodo *) malloc (sizeof(nodo));
cabeca
.....
*proximo=largato
Lixo
Listas Lineares encadeadas Circular
 Criando um novo nodo
nodo *noatual = NULL; 
nodo *novono = NULL;
*noatual
*novono
Listas Lineares encadeadas Circular
 Se cabeça diferente de NULL
noatual = cabeca;
*cabeca
...
*proximo=NULL*noatual
Listas Lineares encadeadas Circular
 Criando um novo nodo para encadear
novono = (nodo*) malloc(sizeof(nodo));
*novono
...
*proximo=largato
Listas Lineares encadeadas Circular
 Encadeando o novono
novono->... = ...
novono->proximo = NULL;
noatual->proximo = novono;
*cabeca
....
*proximo=NULL
noatual *novono
....
*proximo=noatual
Listas Lineares encadeadas Circular
 Encadeando o novono
novono->... = ...
novono->proximo = (*cabeca)...;
noatual->proximo = novono;
*cabeca
...
*proximo=(*cabeca)->proximo
noatual
*novono ...
*proximo=novono
Conclusão
 Na representação por encadeamento, 
acrescenta-se a cada elemento da lista 
apontadores que garantem a precedência 
entre os elementos
 Vantagens
Inserção e remoção mais rápida
Uso mais racional da memória disponível
 Desvantagens
Tamanho (espaço ocupado na memória) de um nó 
é maior do que em um vetor (array)
Ruim para listas com poucos elementos
Exercícios de Fixação
 Implementem em casa o seguinte problema:
◦ Faça um arquivo de cabeçalho que contenha os 
seguintes dados:
typedef struct nodo{
int idade;
char nome[50];
struct nodo *prox;
}no;
E as seguintes operações:
 Criar nodos;
 Inserir nodos
 E Imprimir nodos
Tipo de Dados Lista
Lista Circular
ESTRUTURA DE DADOS