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:
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:
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.
Qualquer dúvida, poste ai e quando eu ver estarei respondendo.
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:
Código PHP:
struct lista
{
int elemento;
struct lista *proximo;
};
typedef struct lista LISTA;
Para iniciar uma lista, basta apenas colocar o ponteiro para apontar para NULL.
Exemplo:
Código PHP:
void start(lista *ptr)
{
(*ptr).proximo = NULL;
}
(*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.
Código PHP:
#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.
}
}
}
Comment