As listas duplamente encadeadas são estruturas de dados semelhantes às listas simplesmente encadeadas. No entanto, em comparação com as listas simplesmente encadeadas a conexão entre os elementos é feita através de dois ponteiros (um que aponta para o elemento anterior, e o outro, para o seguinte).
Assim como na lista encadeada, esta lista começa com Struct e Ponteiro, vamos iniciar nossa programação.
-Código:
# include <stdio.h>
# include <conio.h>
# include <stdlib.h>
# include <string.h>
# include <malloc.h>
struct elemento {
struct elemento *ant; // Ponteiro que irá apontar para a posição anterior.
int dados; // Variável que irá conter os dados digitados.
struct elemento *prox; // Ponteiro que irá apontar para a próxima posição.
};
int li_liberada=0; // Variável que irá informar se a lista está criada.
typedef struct elemento *Lista; // Definimos o nome da struct para Lista.
----- FUNÇÕES -----
Cria_Lista - Função que começa a lista.
-Código:
Lista* cria_Lista(int liberada){
if (liberada != 0){
puts("Ja existe uma Lista criada");
getche();
return NULL;
}else{
Lista *li = (Lista*) malloc (sizeof(Lista)); // Aloca espaço de memória para lista.
if (li == NULL){
puts("Nao foi possivel criar a lista por falta de espaço");
} else{
*li = NULL; // Conteúdo de lista é nulo.
printf("\nLista Criada apontando para %p", li);
li_liberada = 1; // Informamos que existe uma lista criada.
}
getche();
return li;
}
}
Libera_Lista - Função que deleta todos os itens da lista.
-Código:
int libera_Lista(Lista *li){
if (li != NULL){ // Caso exista uma lista criada.
elemento *no; // Ponteiro Nó Criado.
while ((*li) != NULL){ // Enquanto Conteúdo de lista for diferente de nulo.
no = *li; // Nó aponta para lista.
*li = (*li)->prox; // Conteúdo de lista recebe Conteúdo Próximo.
free(no); // Liberamos o Nó.
}
li = NULL; // Definimos a lista como nula.
free(li); // Liberamos a lista.
li_liberada = 0; // Informamos que não existe lista criada.
return 1;
}else{
return 0;
}
}
Tamanho_Lista - Função que informa o tamanho atual da lista.
-Código:
int tamanho_Lista(Lista *li){
if (li == NULL) // Caso a lista seja nula.
return 0;
if (*li == NULL) // Caso a lista seja nula.
return -1;
int cont = 0;
elemento *no = *li; // Nó recebe Lista.
while(no != NULL){ // Enquanto Nó não for Nulo.
cont++; // Contador Aumenta.
no = no->prox; // Nó aponta para Próximo Nó.
}
return cont;
}
Lista_Vazia - Função que informa se a lista está vazia.
-Código:
int lista_vazia(Lista *li){
if (li == NULL)
return 1;
if (*li == NULL)
return 2;
return 0;
}
Insere_Lista_Inicio - Função que insere um item no inicio da lista.
-Código:
int insere_Lista_inicio(Lista *li, int al){
if (li == NULL) // Caso lista seja Nula.
return 0;
elemento *no = (elemento*) malloc (sizeof(elemento)); // Aloca espaço para lista.
if (no == NULL) // Caso Nó for nulo.
return 2;
no->dados = al; // Nó->Dados recebe al.
no->prox = (*li); // Nó->Próximo recebe lista.
no->ant = NULL; // Nó->Anterior recebe Nulo.
if (*li != NULL){ // Caso Lista não seja Nula.
(*li)->ant = no; // Lista Anterior recebe Nó.
}
*li = no; // Lista Recebe Nó.
return 1;
}
Insere_Lista_Final - Função que insere um item no final da lista.
-Código:
int insere_Lista_final(Lista *li, int al){
if (li == NULL) // Caso lista seja nula.
return 0;
elemento *no = (elemento*) malloc (sizeof(elemento)); // Aloca espaço para lista.
if (no == NULL) // Caso Nó for Nulo.
return 2;
no->dados = al; // Nó->Dados Recebe Al.
no->prox = NULL; // Próximo Nó recebe Nulo.
if ((*li) == NULL){ // Caso lista for Nula.
no->ant = NULL; // Nó->Anterior recebe Nulo.
*li = no; // Lista recebe Nó.
}else{
elemento *aux = *li; // Ponteiro Auxiliar recebe lista.
while (aux->prox != NULL){ // Enquanto Próximo Auxiliar for diferente de Nulo.
aux = aux->prox; // Auxiliar Aponta para Próximo Auxiliar.
}
aux->prox = no; // Próximo Auxiliar Aponta para Nó.
no->ant = aux; // Nó Anterior Aponta para Auxiliar.
}
return 1;
}
Insere_Lista_Ordenada - Função que insere um item no meio da lista.
-Código:
int insere_Lista_ordenada(Lista *li, int al){
if (li == NULL) // Caso lista seja nula.
return 0;
elemento *no = (elemento*) malloc (sizeof(elemento)); // Aloca espaço para Lista.
if (no == NULL) // Caso Nó seja Nulo.
return 2;
no->dados = al; // Nó->Dados recebe Al.
if (lista_vazia(li)){ // Caso Lista seja Vazia.
no->prox = NULL; // Próximo Nó recebe Nulo.
no->ant = NULL; // Nó Anterior recebe Nulo.
*li = no; // Lista recebe Nó.
return 1;
}else{
elemento *ante, *atual = *li; // Cria-se Ponteiro Ante e Atual, Atual recebe Lista.
while (atual != NULL && atual->dados < al){ // Enquanto Atual for Diferente de Nulo e Atual->Dados for Menor que Al.
ante = atual; // Ante aponta para atual.
atual = atual->prox; // Atual aponta para Próximo Atual.
}
if (atual == *li){ // Caso atual seja igual a lista.
no->ant = NULL; // Nó Anterior recebe Nulo.
(*li)->ant = no; // Lista Anterior recebe Nó.
no->prox = (*li); // Próximo Nó recebe Lista.
*li = no; // Lista recebe Nó.
}else{
no->prox = ante->prox; // Próximo Nó aponta para Próximo Ante.
no->ant = ante; // Nó Anterior aponta para Ante.
ante->prox = no; // Próximo Ante aponta para nó.
if (atual != NULL){ // Caso atual seja diferente de nulo.
atual->ant = no; // Atual Anterior aponta para nó.
}
}
}
return 1;
}
Remove_Lista_Inicio - Função que remove o item que está no inicio da lista.
-Código:
int remove_Lista_inicio(Lista *li){
if (li == NULL) // Caso lista seja nula.
return 0;
if ((*li) == NULL) // Caso lista seja nula.
return 2;
printf("%p", li);
getche();
elemento *no = *li; // Nó recebe Lista.
*li = no->prox; // Lista Recebe Próximo Nó.
if (no->prox != NULL){ // Caso Próximo Nó Não seja Nulo.
no->prox->ant = NULL; // Próximo Nó Anterior recebe Nulo.
}
free(no); // Liberamos Nó.
return 1;
}
Remove_Lista_Final - Função que remove o item que está no final da lista.
-Código:
int remove_Lista_final(Lista *li){
if (li == NULL) // Caso lista seja nula.
return 0;
if ((*li) == NULL) // Caso lista seja nula.
return 2;
printf("%p", li);
getche();
elemento *no = *li; // Nó recebe Lista.
while(no->prox != NULL){ // Enquanto Próximo Nó não for Nulo.
no = no->prox; // Nó aponta para Próximo Nó.
}
if (no->ant == NULL){ // Caso Nó Anterior for igual a Nulo.
*li = no->prox; // Lista recebe Próximo Nó.
}else{
no->ant->prox = NULL; // Próximo Nó Anterior Recebe Nulo.
}
free(no); // Liberamos Nó.
return 1;
}
Remove_Lista_Matricula - Função que remove um item específico da lista.
-Código:
int remove_Lista_matricula(Lista *li, int mat){
if (li == NULL) // Caso lista seja nula.
return 0;
elemento *no = *li; // Nó recebe Lista.
while(no !=NULL && no->dados != mat){ // Enquanto Nó não for Nulo e Nó->Dados for diferente de mat.
no = no->prox; // Nó aponta para Próximo Nó.
}
if (no == NULL) // Caso Nó seja igual a Nulo.
return 2;
printf("%p", li);
getche();
if (no->ant == NULL){ // Caso Nó Anterior seja igual a Nulo.
*li = no->prox; // Lista recebe Próximo Nó.
}else{
no->ant->prox = no->prox; // Próximo Nó Anterior aponta para Próximo Nó.
}
if (no->prox != NULL){ // Caso Próximo Nó não for Nulo.
no->prox->ant = no->ant; // Próximo Nó Anterior aponta para Nó Anterior.
}
free(no); // Liberamos Nó.
return 1;
}
Consulta_Lista_Posição - Função que consulta um item pela sua posição.
-Código:
int consulta_Lista_posicao(Lista *li, int pos, int al){
if (li == NULL || pos <=0) // Caso a lista seja nula ou Posição menor ou igual a 0.
return 0;
elemento *no = *li; // Nó recebe Lista.
int i = 1;
while(no != NULL && i < pos){ // Enquanto Nó não for nulo e I for menor que Pos.
no = no->prox; // Nó aponta para Próximo Nó.
i++; // Contado Aumenta.
}
if (no == NULL){
return 0;
}else{
al = no->dados; // Al aponta para Nó->Dados.
printf("\n%i", al);
getche();
}
return 1;
}
Consulta_Lista_Matricula - Função que consulta a posição do item pelo item.
-Código:
int consulta_Lista_matricula(Lista *li, int mat, int al){
if (li == NULL) // Caso lista seja nula.
return 0;
elemento *no = *li;
while(no != NULL && no->dados != mat){ // Enquanto Nó for diferente de Nulo e Nó->Dados é diferente de mat.
no = no->prox; // Nó aponta para Próximo Nó.
}
if (no == NULL){
return 0;
}else{
al = no->dados; // Al aponta para Nó->Dados.
printf("\n%i", al);
getche();
}
return 1;
}
Agora que já fizemos todas as funções necessárias podemos começar a brincar com essa lista, porém antes é preciso criar o código principal. Irei colocar abaixo um código principal com as variáveis básicas para a Lista funcionar.
Agora que já fizemos todas as funções necessárias podemos começar a brincar com essa lista, porém antes é preciso criar o código principal. Irei colocar abaixo um código principal com as variáveis básicas para a Lista funcionar.
-Código:
int main(){
Lista *li = NULL; // Arnazema o topo da Lista
int z=0, x, Final; // Retorno das funções
int dados;
li = cria_Lista(li_liberada);
}
Caso queira o arquivo C já com o código completo e utilizando todas as funções, só entrar neste link: http://boo-box.link/2DG4P
Referências:
http://br.ccm.net/faq/10254-lista-duplamente-encadeada (Acessado em 01/09/2016)
http://web.unipar.br/~piffer/2Serie(Estrutura)/3bim/13_Exemplo_Lista-dinamica_dupla.cpp (Acessado em 01/09/2016)
http://web.unipar.br/~piffer/2Serie(Estrutura)/3bim/13_Exemplo_Lista-dinamica_dupla.cpp (Acessado em 01/09/2016)
Nenhum comentário:
Postar um comentário