As listas ordenadas, são uma abrevação das listas simplesmente encadeadas, onde seguem e exato mesmo conceito de vários elementos que possuem valores e ponteiros apontadores para o elemento seguinte. A única diferenã neste tipo de lista, é que ao serem inseridos novos elementos, esses devem ser comparados com os valores dos elementos já presentes na lista e inseridos levando em consideração se são menores ou maiores, ou seja, a cada novo elemento inserido, sua posição não será apenas no inicio ou no fim, mas sim, dependendo de seu valor, ordenando a lista.
No momento da remoção de elementos, o conceito segue o mesmo, onde o elemento anterior ou seguinte deve substituir a posição do elemento removido. Diante disso, a grande questão está na função de inserção de elementos. Porém, para que seja feito um entendimento completo do funcionamento da lista ordenada, todas as suas funções serão passadas nesse artigo. Portanto, como na lista encadeada, eis os passos de criação da lista:
Como dito anteriormente, um bloco da lista deverá conter 1 elemento e no mínimo 1 ponteiro apontador:
struct elemento{
int valor; //Valor que o elemento terá
struct elemento *prox; //Apontador para a posição X+1
};
typedef struct elemento Elem; //Definição da struct como um tipo abstrato
Perceba que sua implementação é muito simples, pois este será o corpo dos elementos da lista. Porém, saiba que após isso, em seu programa, deverá ser criada a lista como ponteiro desta struct. Isso se dá pelo comando: Elem *lista. Este ponteiro criado será exatamente o que será referênciado nas funções de manipulação da lista.
Este passo fará a criação da lista, que consiste basicamente em setá-la com um valor NULL inicial:
Elem *criarLista(void){
return NULL; //Retorno NULL para algo vazio
}
Algo bem simplório, pois de um forma geral, fará com que o primeiro elemento da lista seja criado, mesmo que não contenha valor algum. Para isso, basta retornar da função o NULL. Perceba que esta função é criada como ponteiro do tipo Elem (struct), ou seja, ela faz referência ao exato ponteiro *lista criado.
Esta função irá verificar se uma lista se encontra ou não vazia (sem elemento algum armazenado). Pode parecer seu uso desnecessário, porém em alguns momentos esta função se mostrará eficiente para algumas implementações como a de exibição da lista. Imagine que com esta função, recursos poderão ser minimizados durante a execução do programa, por exemplo na exibição da lista, a função não precisará executar todo o código caso a lista não tenha elementos certo? Abaixo segue sua implementação:
int listaVazia(Elem *lista){
return (lista == NULL); //Verificação se a lista está nula
}
Basicamente, esta função deverá verificar se a lista é igual a NULL, ou seja, se a lista permanece da mesma forma ue foi criada (sem alteração ou implementação de elemento), procedimento este realizado na função anterior.
Aqui é onde começa a principal diferença da lista ordenada, pois para que seja inserido um elemento, devem haver verificações em meio a lista para em qual posição o elemento será inserido. Diante disso, podem acontecer 3 situações de inserção, onde:
Portanto, 3 verificações devem ser realizadas. Porém, a 1ª e 2ª possuem um mesmo contexto se inserção no início da lista, bastanto então, uma inserção de elemento simples:
int insereOrdenada(Elem **lista, int x){
/*1º Caso, Lista vazia ou 2º Caso, Elemento menor que o primeiro*/
if(vazia(*lista) || x < (*lista)->valor){
Elem *novo;
novo = (Elem *)malloc(sizeof(Elem));
novo->valor = x;
novo->prox = *lista;
(*lista) = novo;
return 1;
}
/*3º Caso, Elemento maior que o primeiro*/
Elem *novo, *aux, *aux2;
aux = *lista;
aux2 = aux->prox;
while(aux2->prox != NULL && valor > aux2->valor){
aux = aux2;
aux2 = aux2->prox;
}
novo = (Elem *)malloc(sizeof(Elem));
novo->valor = x;
aux->prox = novo;
novo->prox = aux2;
return 1;
}
Como dito, basta ser criado um percorredor da lista e seu auxiliar, até que alcancem a última posição (onde não existe elemento com valor maior) ou achar sua posição (onde foi achado um elemento com valor maior). Achada a posição, basta fazer com que esse elemento seja o prox do percorredor e o prox do novo, o auxiliar.
Assim como na inserção de elemento, a remoção se faz um pouco maior que o de listas encadeadas, onde 3 situações também são encontradas. Mas de forma geral, o conceito segue o mesmo, onde um elemento ao ser removido, outro deverá assumir sua posição. Portanto, faz-se necessário o percorrimento da lista com o percorredor e auxiliar. As 3 situações são:
Segue então a função para remoção de elemento da lista ordenada:
int removerOrdenada(Elem **lista, int x){
/*1º Caso, lista vazia*/
if(vazia(*lista)){
return 0;
}
/*2º Caso, remover primeiro elemento*/
if(x == (*lista)->num){
Elem *aux;
aux = *lista;
(*lista) = aux->prox;
free(aux);
}
/*3º Caso, remoção durante a lista*/
Elem *aux, *aux2;
aux = *lista;
aux2 = aux->prox;
while(aux2 != NULL && x > aux2->valor){
aux = aux2;
aux2 = aux2->prox;
}
if(x != NULL && x == aux->valor){
aux = aux2->prox;
free(aux2);
return 1;
}else{
return 0;
}
}
Ou seja, deverá ser criado o percorredor e o auxiliar.
Esta função se torna bem simples, onde basicamente será gerado um loop que percorrerá todos os valores da lista e exibi-los:
int imprimirLista(Elem *lista){
if(listaVazia(lista)){ //Verificação de lista vazia
printf("\n LISTA VAZIA \n");
}else{
Elem *aux; //Percorredor da lista
aux = lista; //Atribuição da própria lista ao percorredor
printf("\n LISTA: ");
while(aux != NULL){ //Loop - parada quando alcançar prox = NULL (último prox da lista)
printf(" - %d",aux->num); //Exibição do elemento
aux = aux->prox; //Andamento do percorredor de posição a posição
}
printf(" - ");
}
return 0;
}
Função esta que possui uma implementação simples, pois basta criar um percorredor que pulará sobre todas as posições da lista e exibir estas posições.
Por fim, a última função que deverá ser implementada é a de liberação da lista, a qual terá o objetivo de ao fim do programa, encerrar a lista e desalocar da memória tudos os elementos que foram alocados. Isto é importante, uma vez que se este procedimento não for realizado, algum lixo pode ficar armazenado na memória, trazendo possíveis problemas nos recursos e processamento da máquina. Para isso, é feito:
int liberarLista(Elem **lista){
if(listaVazia(lista)){ //Verificação de lista vazia
free(lista); //Caso a lista esteja vazia, basta liberá-la
}else{
Elem *aux, *aux2; //Auxiliares que irá percorrer a lista
aux = *lista; //Atribuição da própria lista ao percorredor
while(aux != NULL){ //Loop - parada quando alcançar prox = NULL (último prox da lista)
aux2 = aux->prox; //O auxiliar 2 irá receber o valor do próximo elemento
free(aux); //Liberação do elemento
aux = aux2; //Percorredor receberá o próximo elemento para futuramente liberá-lo.
}
}
}
De forma geral, bastará percorrer toda a lista e sair liberando cada posição dela e para isso, 2 auxiliares deverão ser criados, onde aux será o percorredor e aux2 receberá o valor de prox (o elemento a posição seguinte). Pense que ao excluir uma posição, como saberá qual a próxima se o seu prox também foi excluido? Por isso o uso do aux2. Diante disso, basta excluir o elemento (aux) e fazer com que após isso, ele receba o próximo elemento (armazenado em aux2).