C / C++ Listas simplesmente encadeadas

[fiodumal]

Venho fazer esse tutorial pois tive que estudar bastante esse assunto e digamos que achei bastante chato e confuso quando comecei, pois não tem muito material com explicação decente por ai, objetivo não é explicar tudo, mas explicar o necessário de forma clara e fácil.

Existem muitos tipois de listas, mas hoje estarei focando a lista simplesmente encadeada, que pode ser também conhecido por fila simplesmente encadeada.

Farei o possível para ficar fácil de entender e não muito grande o tópico.

O que são essas filas?
São estruturas de dados e o acesso feito nos elementos dessas estruturas são feitos através de ponteiros.

A alocação de memória dessas listas são feitas durante a execução do programa.

Por quê tem o nome de encadeadas?
Pois como o nome já diz, os elementos da lista são encadeados nos proximos elementos, sendo assim uma lista de elementos contínuos, mas tem um porém, apesar dos elementos ser contínuos, a alocação de memória não será necessariamente contínuo.
Ex: Primeiro elemento está alocado no endereço de memória 0x00000001, o segundo elemento dessa lista não precisa estar alocado no endereço 0x00000002, pois como já dito, o acesso é feito através do endereço de memória e não propriamente da sequencia delas.

O ponteiro do ultimo elemento da lista, SEMPRE deverá apontar para NULL, indicando dessa forma o fim de nossa lista.

A construção de uma lista encadeada ficaria parecido com isso:

struct lista 
{ 
   int elemento; 
   struct lista *proximo; 
}; 
typedef struct lista LISTA;  

No código acima criamos um elemento do tipo int, onde ficará armazenado os valores de nossa lista, e criamos um ponteiro para a estrutura que será usado para apontar para o próximo elemento, e o typedef é para não precisarmos mais utilizar (struct lista) e sim apenas (LISTA) podendo por o nome que quiser.

Para iniciar uma lista, basta apenas colocar o ponteiro para apontar para NULL.
Exemplo:

void start(lista *ptr) 
{ 
    (*ptr).proximo = NULL; 
}  

Lembrando também que quando se trata se estruturas, pode-se usar 2 métodos de ponteiros:

(*ptr).proximo = NULL;
ou
ptr -> proximo = NULL;

Ambos estão corretos.


O básico e o necessário à saber de listas encadeadas é isso, agora estarei postando uma lista pronta, que fiz como trabalho da faculdade, toda comentada e de fácil entendimento.

#include <stdio.h> 
#include <stdlib.h> 
 
struct lista  
{ 
    int number; 
    struct lista *proximo; 
}; 
typedef struct lista lista; 
 
int     menu(void); 
void    show(lista *p); 
int     vazio(lista *p); 
void    reset(lista *p); 
void     start(lista *p); 
void     addlast(lista *p); 
void    addfirst(lista *p); 
void     option(lista *p, int a); 
 
int main() 
{ 
    int op; 
     
    lista *p = (lista *) malloc(sizeof(lista)); //aloca o ponteiro p em algum endereço de memória disponível, se der falha, retorna NULL 
    if( p == NULL ) // comparação para ver se o ponteiro foi alocado 
    { 
        printf("Sem espaco na memoria."); 
        exit(1); // caso não foi alocado, ele encerra o programa 
    } 
     
    start(p); // inicia a lista 
     
    do //loop no menu, até o numero 0 for escolhido, que será o término do programa. 
    { 
        op = menu(); // chama o menu na variavel op 
        option(p,op); // chama a função option com o ponteiro p e variavel op, retornando o valor inteiro, escolhido no menu pelo usuário. 
    }while(op); // se op for diferente de 0 o loop continua 
     
    free(p); // após sair do loop, ele libera a memória alocada do ponteiro p 
    return 0; // finaliza o programa. 
} 
 
void start(lista *p) 
{ 
    (*p).proximo = NULL; // responsável para iniciar a lista 
} 
 
void addfirst(lista *p) // function para adicionar um elemento no começo da lista 
{ 
    lista *new = (lista *) malloc(sizeof(lista)); //aloca o ponteiro p em algum endereço de memória disponível, se der falha, retorna NULL 
     
    if( new == NULL ) // comparação para ver se o ponteiro foi alocado 
    { 
        printf("Sem espaco na memoria."); 
        exit(1); // caso não foi alocado, ele encerra o programa 
    } 
     
    printf("digite novo valor:"); 
    scanf("%d", &(*new).number); //pega valor digitado pelo usuário e coloca na variável number (elemento da lista) apontado pelo ponteiro new 
         
    lista *old = (*p).proximo; // cria um novo ponteiro para a struct, posicionando ele para o início da lista, para nao perdermos a referencia do começo. 
    (*p).proximo = new; // aponta o começo da lista para new, colocando o valor digitado no começo da lista. 
    (*new).proximo = old; // e então apontamos o novo que agora é o primeiro elemento, para o antigo que era o primeiro, mas agora é o segundo. 
} 
 
void addlast(lista *p) 
{ 
    lista *new = (lista *) malloc(sizeof(lista)); //aloca o ponteiro p em algum endereço de memória disponível, se der falha, retorna NULL 
     
    if( new == NULL ) // comparação para ver se o ponteiro foi alocado 
    { 
        printf("Sem espaco na memoria."); 
        exit(1); // caso não foi alocado, ele encerra o programa 
    } 
     
    printf("digite novo valor :"); 
    scanf("%d", &(*new).number); // pega valor digitado ppelo usuário e coloca na variável number (elemento da lista) apontado pelo ponteiro new 
    (*new).proximo = NULL; // como a regra da lista é o ultimo elemento apontar para NULL, e esse é nosso ultimo elemento, entao o proximo é NULL. 
     
    if( vazio(p) ) // verifica se o retorno da função vazio eh igual a 1 
    { 
        (*p).proximo = new; // caso for igual a 1, significa que a lista é vazia, desse modo, o primeiro elemento também será o ultimo. 
    } 
    else 
    { 
        lista *temp = (*p).proximo; // criamos um ponteiro temp para a estrutura lista, posicionando ele para o começo da lista. 
         
        while( (*temp).proximo != NULL ) // loop ativo enquanto o proximo elemento for diferente de null 
        { 
            temp = (*temp).proximo; //procurando o ultimo elemento, passando por todos elementos da lista 
        }  
         
        (*temp).proximo = new; // quando o proximo elemento for null, saíra do loop, e será o ultimo elemento da lista, entao criamos o novo elemento. 
    } 
} 
 
int vazio(lista *p) 
{ 
    if( (*p).proximo == NULL ) // verifica se a lista é vazia, se for retorna 1, caso contrario retorna 0 
        return 1; 
    else 
        return 0; 
} 
 
void show(lista *p) // mostrar os elementos da lista 
{ 
    if( vazio(p) ) // verifica se a lista é vazia, se for a função vazio retorna 1 
    { 
        printf("Lista vazia.\n"); 
        return ; 
    } 
     
    lista *temp = (*p).proximo; // criamos um ponteiro temp da estrututa lista, posicionando para inicio da lista 
     
    while( temp != NULL ) // loop ativo enquanto ponteiro temp for diferente de NULL 
    { 
        printf("%4d",(*temp).number); // mostra o valor do elemento number, apontado pelo ponteiro temp 
        temp = (*temp).proximo; // temp aponta para proximo elemento, até imprimir todos na tela. 
    } 
    printf("\n\n"); 
} 
 
void option(lista *p, int a) // opções do menu 
{ 
    switch(a) 
    { 
        case 0: //se numero digitado no menu for 0, chama a função reset, liberando a memória alocada e terminando o programa. 
            reset(p);  
            break; 
         
        case 1: // se numero digitado no menu for 1, chama a função addfirst para adicionar um elemento no começo da lista 
            addfirst(p); 
            break; 
         
        case 2: // se numero digitado no menu for 1, chama a função addlast para adicionar um elemento no fim da lista. 
            addlast(p); 
            break; 
         
        case 3: // se numero digitado no menu for 1, chama a função show, imprimindo na tela todos elementos da lista. 
            show(p); 
            break; 
         
        case 4: // se numero digitado no menu for 1, chama a função start que seria o mesmo de iniciar novamente a lista, zerando a mesma. 
            start(p); 
            break; 
    } 
} 
 
int menu() // menu retornando valor inteiro digitado pelo usuario 
{ 
    int a; 
     
    printf("Escolha um numero para a opcao desejada: \n"); 
    printf("0 - Sair\n"); 
    printf("1 - Adicionar elemento no começo da lista\n"); 
    printf("2 - Adicionar elemento no final da lista\n"); 
    printf("3 - Mostrar a lista\n"); 
    printf("4 - resetar a lista\n\n"); 
    printf("opcao: "); 
    scanf("%d",&a); 
     
    return a; 
} 
 
void reset(lista *p) // função para liberar memória alocada na lista. 
{ 
    if(!vazio(p)){ // verifica se a lista tem elementos (vazio(p) == 0) 
        lista *atual,*proximov; // criamos 2 ponteiros para a estrutura lista 
         
        atual = (*p).proximo; // posicionamos o ponteiro atual para o inicio da lista. 
        while( atual != NULL ) // loop ativo enquanto o proximo elemento apontado pelo ponteiro n for null (enquanto n for null não é o fim da lista). 
        { 
            proximov = (*atual).proximo; // ponteiro proximov guarda o endereço do proximo elemento. 
            free(atual); // libera o endereço do elemento atual. 
            atual = proximov; // ponteiro atual pega o endereço do proximo elemento, fazendo isso com todos até chegar em NULL e terminando a lista. 
        } 
    } 
}  

Qualquer dúvida, poste ai e quando eu ver estarei respondendo.

[Anon_Pingeon]

Parabéns

Muito útil , como você diz não tem muito material com explicação decente