[Tutorial] Lista Encadeada Circular

[José Enésio 4]

Olá gurizada que tá pegando C para avacalhar e entusiastas Czistas que pretendem trabalhar com isso no futuro!

Hoje estarei postando um tutorial sobre C sobre uma coisa que com certeza algum dia você vai se deparar: a Lista Encadeada Circular!

Desenvolvi um código suficientemente bãummm com as principais funções que uma lista encadeada deve ter. Todos os códigos foram desenvolvidos por mim, portanto você que faz ou vai fazer faculdade provavelmente vai ver com seu professor alguma implementação diferente do código mais eficiente; mas o código que desenvolvi aqui é suficientemente bãummm como eu disse, e o interessante é que funciona. É interessante você tirar um tempo para fazer como eu: ter uma idéia, e desenvolvê-la do zero, com suas idéias. Isso ajuda na hora que você precisar ter prática com a lógica. Pense em um algoritmo; pesquise sobre o que ele é; tente fazê-lo sem ajuda de outros. Se você já conhece um código eficiente o suficiente, seja bem-vindo a postar o seu código! Porém não vou mudar nada no tutorial já que não vai dar para lembrar de todos os fóruns onde vou postar isso para mudar depois!

 

Bom voltando ao interessante:

O que é uma lista encadeada circular?

Bom você provavelmente já deve saber o que é uma lista encadeada, se não sabe, é uma lista de objetos que possui dados e um ponteiro que aponta para o próximo elemento da lista. Na lista encadeada cráááássica, o ponteiro de próximo do último elemento aponta para NULL. Na lista encadeada circular, o último elemento aponta para o primeiro. Tá bom titio já sei o que é uma lista encadeada mas e na hora de declarar a estrutura de dados como eu faço pra encadeada?

É a mesma coisa! Olha só:

 

 

struct ListaC
{
	int data;
	struct ListaC *prox;
};

typedef struct ListaC listac;

Isso já é suficiente para criar uma lista encadeada circular que guarda inteiros!

 

Bom, vamos então desenvolver as principais funções que precisamos para uma lista encadeada. Seriam essas aqui:

cria(), escreve(), insere(), procura(), deleta(), destroi().

 

cria()

 

A função cria só serve mesmo pra inicializar a lista com um elemento mesmo. Agiliza o trabalho de alocar memória, definir o dado e definir o próximo elemento para si mesmo.

A função em si é bem simples:

 

listac* cria(int data)
{
	listac* retorno = (listac*) malloc(sizeof(listac));
	retorno->data = data;
	retorno->prox = retorno;
	return retorno;
}

 

escreve()

 

A função escreve serve para imprimir todos os membros da nossa lista encadeada. Ela deve realizar um loop por toda a lista e só parar quando o loop estiver de volta ao primeiro elemento. Aí está mais um elemento onde operações nas listas circulares diferem: para as listas circulares, agora usamos um loop do while e paramos quando o elemento auxiliar for igual à lista. Podemos usar um loop for aux = lista->prox também, mas optei pelo do while.

 

CODE

void escreve(listac* lista)

{

if(lista == NULL)

{

printf("Lista vazia!");

return;

} //não podemos nos esquecer dos casos onde a lista está vazia, para não dar erros de memória!

listac* loop = lista;

do

{

printf("%d\n", loop->data);

loop = loop->prox;

} while(loop != lista);

}

 

insere()

 

Para inserir um elemento ao final de uma lista circular, precisamos primeiro encontrar o último elemento, o elemento onde prox = lista. Sabendo disso, alocamos memória para prox ser um novo elemento, definimos o dado do prox e o prox do prox para lista. Veja só minha implementação:

CODE

void insere(listac* lista, int data)

{

if(lista == NULL) return;

listac* loop;

for(loop = lista; loop->prox != lista; loop = loop->prox); //acha o último elemento!!!

loop = loop->prox = (listac*) malloc(sizeof(listac));

loop->data = data;

loop->prox = lista;

loop = NULL;

}

 

procura()

 

Na função de procura, realizamos um loop por toda a lista, e se encontrarmos um elemento cujo dado corresponda ao que estamos procurando, retornamos tal elemento. Optei por adicionar aqui também uma opção para contar quantos elementos tem... como a função retorna uma lista e nossas listas guardam um inteiro, então optei por criar uma lista nova e definir nela o valor dos elementos contados e retorná-la... matamos dois coelhos em uma cajada só hehe

Lá vai:

CODE

//optei por chamar assim os parâmetros para contar ou retornar o elemento:

#define LEC_SEARCH_SINGLE 0

#define LEC_SEARCH_COUNT 1

 

//no caso passamos eles no terceiro parâmetro... ou passamos só 0 e 1, tanto faz.

listac* procura(listac* lista, int find, int params)

{

if(lista == NULL) return NULL; //nunca se esquecer de verificar se está vazia para não ocorrerem erros na hora de executar!

listac *loop = lista;

listac *resposta;

int contador = 0;

do

{

if(loop->data == find)

{

if(params == LEC_SEARCH_SINGLE)

{

return loop; //achou o elemento que precisava!

}

contador++;

}

loop = loop->prox;

} while(loop != lista);

resposta = cria(contador);

return resposta;

}

 

deleta()

 

Para a função deleta, precisamos ter um pouquinho mais de cuidado já que pode ser que eu queira deletar o primeiro elemento... aí temos que mudar a lista para começar do segundo elemento, e o último elemento tem que apontar para o segundo! O código então fica um pouquinho mais extenso... Para deletar um elemento, apontamos o elemento anterior para o próximo e liberamos a memória ocupada por ele.

CODE

listac* deleta(listac* lista, listac* elemento)

{

if(lista == NULL || elemento == NULL) return; //se a lista é vazia, não vamos perder tempo nem obter erros depois!

if(elemento == lista && lista->prox == lista)

{ //se a lista só tem um elemento e queremos apagar esse elemento...

free(lista);

lista = NULL;

return NULL; //apagamos logo o troço e retornamos NULL. Sem chupitz.

}

listac* loop = lista;

if(elemento == lista && lista->prox != lista)

{ //se queremos deletar o primeiro elemento e a lista tem mais elementos

for(; loop->prox != lista; loop = loop->prox);

loop->prox = lista->prox; //precisamos fazer com que o último elemento aponte para o segundo

listac* temp = lista;

lista = lista->prox; //precisamos fazer com que nosso ponteiro da lista aponte para o segundo elemento e salvamos o primeiro em buffer

free(temp);

temp = loop = NULL; //só então limpamos os dados

return lista; //para retornar a nossa nova lista

}

do

{

if(loop->prox == elemento)

{ //pesquisamos pelo elemento, quando achamos, deletamos ele e saímos

loop->prox = elemento->prox;

free(elemento);

elemento = NULL;

break;

}

loop = loop->prox;

} while(loop != lista);

loop = NULL;

return lista; //e retornamos a nossa nova lista

}

 

destroi()

 

Destrói? Destruir a lista o que é isso? Bom essa função que eu adoro usar serve para limpar todos os dados armazenados na lista, isto é, serve para limpar todos os elementos da lista e liberar a memória ocupada por eles. Aqui começaremos apagando do segundo membro em diante, para só então apagar o primeiro para finalizar. Fazemos isso para poder realizar a verificação do último elemento (elemento->prox == primeiro) sem medo.

CODE

void destroi(listac* lista)

{

if(lista == NULL) return; //se a lista é vazia, não perdemos tempo

listac *loop = lista->prox, *deleta;

while(loop != lista)

{ //vamos deletando os elementos da lista até só sobrar o primeiro

deleta = loop;

loop = loop->prox;

free(deleta);

deleta = NULL;

}

free(lista); //então deletamos o primeiro

lista = loop = NULL;

}

É isso aí gurizada! Isso já é o suficiente para brincar com as listas! Espero que tenham gostado, até a próxima!

[Silas Martins 0]

Belo tutorial bem trabalhado e detalhado.

Ficou 10

[Kandrade 7]

Ficou legal mesmo.

 

Parabéns!!