Listas simplesmente encadeadas
Listas encadeadas em C são estruturas de dados que encadeiam os elementos através de um ponteiro. Elas também possuem uma estrutura dinâmica, ou seja, não precisamos conhecer com antecedência o número de elementos que ela conterá. Nas listas encadeadas, todos os elementos, exceto o último, apontam para o seguinte. Assim, cada elemento é formado por dois componentes: o dado armazenado e a ligação com o elemento seguinte. As listas encadeadas podem ser utilizadas para realizar diversas operações de inserção e eliminação de elementos.
Requisitos
Os requisitos das listas simplesmente encadeadas são os seguintes: os tipos de dados, as estruturas, o uso do typedef, os ponteiros e as funções usuário. Como dito anteriormente, cada elemento da lista está ligado ao seguinte:
Enquanto em uma tabela os elementos estão em sequência na memória, nas listas os elementos estão dispersos e, na memória, a representação deles é aleatória em função do espaço alocado.
O ponteiro seguinte do último elemento deve apontar para NULL (fim da lista). Para acessar um elemento, a lista é varrida desde o início. O ponteiro seguinte permite o deslocamento para o elemento seguinte.
Esse deslocamento ocorre em um único sentido, do primeiro ao último elemento. Se você quiser se deslocar nos dois sentidos, será necessário utilizar uma lista duplamente encadeada.
Construção do modelo de um elemento da lista
Para determinar um elemento da lista, vamos usar o tipo struct. O elemento da lista conterá um campo dado e um ponteiro seguinte. O ponteiro seguinte deve ser do mesmo tipo que o elemento, senão ele não poderá apontar para o elemento. O ponteiro seguinte permitirá o acesso ao próximo elemento.
typedef struct ElementoLista {
char *dado;
struct ElementoLista *seguinte;
}Elemento;
Para controlar a lista, o melhor é salvar certos elementos: o primeiro elemento, o último elemento e o número de elementos. Para tanto, outra estrutura será utilizada. Esse procedimento não é obrigatório, já que você pode utilizar variáveis.
typedef struct ListaDetectada {
elemento *início;
elemento *fim;
int tamanho;
}Lista;
O ponteiro início possui o endereço do primeiro elemento da lista e o ponteiro fim, o endereço do último elemento da lista. A variável tamanho integra o número de elementos.
Seja qual for a posição na lista, os ponteiros início e fim sempre apontarão, respectivamente, para o primeiro e o último elemento. O campo tamanho conterá o número de elementos da lista, seja qual for a operação efetuada na lista.
Operações em listas encadeadas
Para inserção e exclusão de elementos, uma única função é suficiente se ela for desenvolvida corretamente, de acordo com as necessidades. No entanto, lembre-se que esse artigo é puramente didático. É por isso que foi criada uma função para cada operação de inserção e exclusão.
Inicialização
Modelo da função:
void inicialização (Lista *lista);
A operação deve ser executada antes de qualquer outra operação da lista. Ela posiciona os ponteiros início e fim no valor NULL e o tamanho no valor 0.
Função:
void inicialização (Lista *lista){
lista->início = NULL;
lista->fim = NULL;
tamanho = 0;
}
Observação: com o operador ->, a linguagem C/C++ nos garante uma maneira mais simples de escrever o acesso a um atributo através de um ponteiro. Na função anterior, acessamos o atributo início através do ponteiro lista.
Inserção de elemento da lista
A seguir, indicamos as etapas do algoritmo de inserção e o registro dos elementos:
- Declaração dos elementos a ser inseridos;
- Alocação da memória para o novo elemento;
- Preenchimento do conteúdo do campo de dados;
- Atualização dos ponteiros do primeiro e último elemento, se necessário.
Em listas com apenas um elemento, o primeiro e o último elementos são o mesmo. A seguir, descrevemos as diferentes formas de inserção para atualizar o tamanho da lista e adicionar um novo elemento.
Inserção em lista vazia
Modelo da função:
int ins_em_lista_vazia (Lista *lista, char *dado);
A função retorna o valor -1 em caso de falha. Caso contrário, o valor retornado será 0.
Etapas: alocação da memória para o novo elemento, preenchimento do campo de dados do novo elemento, o ponteiro seguinte ao novo elemento aponta para NULL, ponteiros início e fim apontam para o novo elemento e o tamanho da lista é atualizado.
Função:
/* inserção em lista vazia */
int ins_em_lista_vazia (Lista * lista, char *dado){
elemento *novo_elemento;
if ((novo_elemento = (elemento *) malloc (sizeof (elemento))) == NULL)
return -1;
if ((novo_elemento->dado = (char *) malloc (50 * sizeof (char)))
== NULL)
return -1;
strcpy (novo_elemento->dado, dado);
novo_elemento->seguinte = NULL;
lista->início = novo_elemento;
lista->fim = novo_elemento;
lista->tamanho++;
return 0;
}
Inserção no início da lista
Modelo da função:
int ins_início_lista (Lista *lista,char *dado);
A função retorna o valor -1 em caso de falha. Caso contrário, o valor retornado será 0.
Etapas: alocação da memória para o novo elemento, preenchimento do campo de dados do novo elemento, o ponteiro seguinte ao novo elemento aponta para NULL, ponteiro início aponta para o novo elemento, ponteiro fim não muda e o tamanho da lista aumenta em uma unidade.
Função:
/* inserção no início da lista */
int ins_início_lista (Lista * lista, char *dado){
elemento *novo_elemento;
if ((novo_elemento = (elemento *) malloc (sizeof (elemento))) == NULL)
return -1;
if ((novo_elemento->dado = (char *) malloc (50 * sizeof (char)))
== NULL)
return -1;
strcpy (novo_elemento->dado, dado);
novo_elemento->seguinte = lista->início;
lista->início = novo_elemento;
lista->tamanho++;
return 0;
}
Inserção no fim da lista
Modelo da função:
int ins_fim_lista (Lista *lista, elemento *atual, char *dado);
A função retorna o valor -1 em caso de falha. Caso contrário, o valor retornado será 0.
Etapas: alocação da memória para o novo elemento, preenchimento do campo de dados do novo elemento, o ponteiro seguinte ao último elemento aponta para o novo elemento, ponteiro fim aponta para o novo elemento, ponteiro início não muda e o tamanho da lista aumenta em uma unidade.
Função:
/*inserção no fim da lista */
int ins_fim_lista (Lista * lista, elemento * atual, char *dado){
elemento *novo_elemento;
if ((novo_elemento = (elemento *) malloc (sizeof (elemento))) == NULL)
return -1;
if ((novo_elemento->dado = (char *) malloc (50 * sizeof (char)))
== NULL)
return -1;
strcpy (novo_elemento->dado, dado);
atual->seguinte = novo_elemento;
novo_elemento->seguinte = NULL;
lista->fim = novo_elemento;
lista->tamanho++;
return 0;
}
Inserção em outro ponto da lista
Modelo da função:
int ins_lista (Lista *lista, char *dado,int pos);
A função retorna o valor -1 em caso de falha. Caso contrário, o valor retornado será 0.
A inserção será feita depois de uma certa posição ser transformada em argumento na função. A posição indicada não deve ser o último elemento. Nesse caso, é preciso utilizar a função de inserção no fim da lista.
Etapas: alocação da memória para o novo elemento, preenchimento do campo de dados do novo elemento, escolher uma posição na lista (inserção será feita depois da posição escolhida), ponteiro seguinte ao novo elemento indica o endereço do ponteiro seguinte do elemento atual, ponteiro seguinte ao elemento atual aponta para o novo elemento, ponteiros início e fim não mudam, o tamanho aumenta em uma unidade.
Função:
/* inserção na posição solicitada */
int ins_lista (Lista * lista, char *dado, int pos){
if (lista->tamanho < 2)
return -1;
if (pos < 1 || pos >= lista->tamanho)
return -1;
elemento *atual;
elemento *novo_elemento;
int i;
if ((novo_elemento = (elemento *) malloc (sizeof (elemento))) == NULL)
return -1;
if ((novo_elemento->dado = (char *) malloc (50 * sizeof (char)))
== NULL)
return -1;
atual = lista->início;
for (i = 1; i < pos; ++i)
atual = atual->seguinte;
if (atual->seguinte == NULL)
return -1;
strcpy (novo_elemento->dado, dado);
novo_elemento->seguinte = atual->seguinte;
atual->seguinte = novo_elemento;
lista->tamanho++;
return 0;
}
Remoção de um elemento da lista
Veja o algoritmo de remoção de um elemento da lista: uso de ponteiro temporário para salvar o endereço dos elementos a ser removidos, o elemento a ser removido fica depois do elemento atual, o ponteiro seguinte ao elemento atual aponta para o endereço do ponteiro seguinte ao elemento a ser removido, liberar a memória ocupada pelo elemento removido e atualizar o tamanho da lista.
Remoção no início da lista
Modelo da função:
int remov_início (Lista *lista);
A função retorna o valor -1 em caso de falha. Caso contrário, o valor retornado será 0.
Etapas: ponteiro remov_elem conterá o endereço do primeiro elemento, ponteiro início exibirá o segundo elemento e o tamanho da lista perde uma unidade.
Função:
/*Remoção no início da lista */
int remov_início (Lista * lista){
if (lista->tamanho == 0)
return -1;
elemento *remov_elemento;
remov_elemento = lista->início;
lista->início = lista->início->seguinte;
if (lista->tamanho == 1)
lista->fim = NULL;
free (remov_elemento->dado);
free (remov_elemento);
lista->tamanho--;
return 0;
}
Remoção em outro ponto da lista
Modelo da função:
int remov_na_lista (Lista *lista, int pos);
A função retorna o valor -1 em caso de falha. Caso contrário, o valor retornado será 0.
Etapas: ponteiro remov_elem conterá o endereço para o qual aponta o ponteiro seguinte do elemento atual, o ponteiro seguinte do elemento atual apontará para o elemento para o qual aponta o ponteiro seguinte ao elemento depois do elemento atual. Se o elemento atual for o penúltimo elemento, o ponteiro fim deve ser atualizado. O tamanho da lista perde uma unidade
Função:
/* remover elemento após a posição solicitada */
int remov_na_lista (Lista * lista, int pos){
if (lista->tamanho <= 1 || pos < 1 || pos >= lista->tamanho)
return -1;
int i;
elemento *atual;
elemento *remov_elemento;
atual = lista->início;
for (i = 1; i < pos; ++i)
atual = atual->seguinte;
remov_elemento = atual->seguinte;
atual->seguinte = atual->seguinte->seguinte;
if(atual->seguinte == NULL)
lista->fim = atual;
free (remov_elemento->dado);
free (remov_elemento);
lista->tamanho--;
return 0;
}
Exibição da lista
Para exibir a lista inteira, podemos nos posicionar no início da lista (através do ponteiro início). Depois, utilizando o ponteiro seguinte de cada elemento, a lista será exibida do primeiro ao último elemento. A condição de parada é fornecida pelo ponteiro seguinte ao último elemento, cujo valor é NULL.
Função:
/* exibição da lista */
void exibir (Lista * lista){
elemento *atual;
atual = lista->início;
while (atual != NULL){
printf ("%p - %s\n", atual, atual->dado);
atual = atual->seguinte;
}
}
Destruição da lista
Para destruir a lista inteira, utilizaremos o recurso de remoção no início da lista uma vez que o tamanho da lista for maior que zero.
Função:
/* destruir a lista */
void destruir (Lista * lista){
while (lista->tamanho > 0)
remov_início (lista);
}
Exemplo completo
lista.h
/* ---------- lista.h ----------- */
typedef struct ElementoLista
{
char *dado;
struct ElementoLista *seguinte;
} elemento;
typedef struct ListaDetectada
{
elemento *início;
elemento *fim;
int tamanho;
} Lista;
/* inicialização da lista */
void inicialização (Lista * lista);
/* INSERÇÃO */
/*inserção em lista vazia */
int ins_em_lista_vazia (Lista * lista, char *dado);
/* inserção no início da lista */
int ins_início_lista (Lista * lista char *dado);
/* inserção no fim da lista */
int ins_fim_lista (Lista * lista, elemento * atual, char *dado);
/* Inserção em outro lugar */
int ins_lista (Lista * lista, char *dado, int pos);
/* REMOÇÃO */
int remov_início (Lista * lista);
int remov_na_lista (Lista * lista, int pos);
int menu (Lista *lista,int *k);
void exibir (Lista * lista);
void destruir (Lista * lista);
/* -------- FIM lista.h --------- */
lista_function.h
/* ---------- function.h ----------- */
void inicialização (Lista * lista) {
lista->início = NULL;
lista->fim = NULL;
lista->tamanho = 0;
}
/*inserção em lista vazia*/
int ins_em_lista_vazia (Lista * lista, char *dado){
elemento *novo_elemento;
if ((novo_elemento = (elemento *) malloc (sizeof (elemento))) == NULL)
return -1;
if ((novo_elemento->dado = (char *) malloc (50 * sizeof (char))) == NULL)
return -1;
strcpy (novo_elemento->dado, dado);
novo_elemento->seguinte = NULL;
lista->início = novo_elemento;
lista->fim = novo_elemento;
lista->tamanho++;
return 0;
}
/* inserção no início da lista */
int ins_início_lista (Lista * lista, char *dado){
elemento *novo_elemento;
if ((novo_elemento = (elemento *) malloc (sizeof (elemento))) == NULL)
return -1;
if ((novo_elemento->dado = (char *) malloc (50 * sizeof (char))) == NULL)
return -1;
strcpy (novo_elemento->dado, dado);
novo_elemento->seguinte = lista->início;
lista->início = novo_elemento;
lista->tamanho++;
return 0;
}
/*inserção no fim da lista */
int ins_fim_lista (Lista * lista, elemento * atual, char *dado){
elemento *novo_elemento;
if ((novo_elemento = (elemento *) malloc (sizeof (elemento))) == NULL)
return -1;
if ((novo_elemento->dado = (char *) malloc (50 * sizeof (char))) == NULL)
return -1;
strcpy (novo_elemento->dado, dado);
atual->seguinte = novo_elemento;
novo_elemento->seguinte = NULL;
lista->fim = novo_elemento;
lista->tamanho++;
return 0;
}
/* inserção na posição solicitada */
int ins_lista (Lista * lista, char *dado, int pos){
if (lista->tamanho < 2)
return -1;
if (pos < 1 || pos >= lista->tamanho)
return -1;
elemento *atual;
elemento *novo_elemento;
int i;
if ((novo_elemento = (elemento *) malloc (sizeof (elemento))) == NULL)
return -1;
if ((novo_elemento->dado = (char *) malloc (50 * sizeof (char))) == NULL)
return -1;
atual = lista->início;
for (i = 1; i < pos; ++i)
atual= atual->seguinte;
if (atual->seguinte == NULL)
return -1;
strcpy (novo_elemento->dado, dado);
novo_elemento->seguinte = atual->seguinte;
atual->seguinte = novo_elemento;
lista->tamanho++;
return 0;
}
/*Remoção no início da lista */
int remov_início (Lista * lista){
if (lista->tamanho == 0)
return -1;
elemento *remov_elemento;
remov_elemento = lista->início;
lista->início = lista->início->seguinte;
if (lista->tamanho == 1)
lista->fim = NULL;
free (remov_elemento->dado);
free (remov_elemento);
lista->tamanho--;
return 0;
}
/* Remoção de elemento depois da posição solicitada */
int remov_na_lista (Lista * lista, int pos){
if (lista->tamanho <= 1 || pos < 1 || pos >= lista->tamanho)
return -1;
int i;
elemento *atual;
elemento *remov_elemento;
atual = lista->início;
for (i = 1; i < pos; ++i)
atual = atual->seguinte;
remov_elemento = atual->seguinte;
atual->seguinte = atual->seguinte->seguinte;
if(atual->seguinte == NULL) lista->fim = atual;
free (remov_elemento->dado);
free (remov_elemento);
lista->tamanho--;
return 0;
}
/* Exibição da lista */
void exibe (Lista * lista)
{
elemento *atual;
atual = lista->início;
while (atual != NULL){
printf ("%p - %s\n", atual, atual->dado);
atual = atual->seguinte;
}
}
/*Destruir lista */
void destruir (Lista * lista){
while (lista->tamanho > 0)
remov_ início (lista); }
int menu (Lista *lista,int *k){
int selecionar;
printf("********** MENU **********\n");
if (lista->tamanho == 0){
printf ("1. Adição do 1° elemento\n");
printf ("2. Fechar\n");
}else if(lista->tamanho == 1 || *k == 1){
printf ("1. Inserção no início da lista\n");
printf ("2. Inserção no fim da lista\n");
printf ("4. Remoção no início da lista\n");
printf ("6. Destruir a lista\n");
printf ("7. Fechar\n"); }
else {
printf ("1. Inserção no início da lista\n");
printf ("2. Inserção no fim da lista\n");
printf ("3. Inserção após a posição especificada\n");
printf ("4. Remoção no início da lista\n");
printf ("5. Remoção após a posição especificada\n");
printf ("6. Destruir a lista\n");
printf ("7. Fechar\n"); }
printf ("\n\n Selecionar: ");
scanf ("%d", &selecionar);
getchar();
if(lista->tamanho == 0 && selecionar == 2) selecionar = 7;
return selecionar;
}
/* -------- FIM lista_function.h --------- */
lista.c
/* ---------- lista.c ----------- */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "lista.h"
#include "lista_function.h"
int main (void) {
char selecionar;
char *nome;
Lista *lista;
elemento *atual;
if ((lista = (Lista *) malloc (sizeof (Lista))) == NULL)
return -1;
if ((nome = (char *) malloc (50)) == NULL)
return -1;
atual = NULL;
selecionar = 'o';
inicialização (lista);
int pos, k;
while (selecionar != 7){
selecionar = menu (lista, &k);
switch (selecionar){
case 1:
printf ("Inserir um elemento: ");
scanf ("%s", nome);
getchar ();
if (lista->tamanho == 0)
ins_em_lista_vazia (lista, nome);
else ins_início_lista (lista, nome);
printf ("%d elementos:início=%s,fim=%s\n", lista->tamanho, lista->início->dado, lista->fim->dado);
exibe (lista);
break;
case 2:
printf ("Inserir um elemento:");
scanf ("%s", nome);
getchar ();
ins_fim_lista (lista, lista->fim, nome);
printf ("%d elementos:início=%s,fim=%s\n", lista->tamanho, lista->início->dado, lista->fim->dado);
exibe (lista);
break;
case 3:
printf ("Inserir um elemento:");
scanf ("%s", nome);
getchar ();
do{ printf ("Inserir a posição:");
scanf ("%d", &pos); }
while (pos < 1 || pos > lista->tamanho);
getchar ();
if (lista->tamanho == 1 || pos == lista->tamanho){
k = 1;
printf("-----------------------------------------------\n");
printf("/!\\A inserção falhou. Utilize o menu {1|2} /!\\\n");
printf("-----------------------------------------------\n");
break; }
ins_lista (lista, nome, pos);
printf ("%d elementos:início=%s,fim=%s\n", lista->tamanho,
lista->início->dado, lista->fim->dado);
exibe (lista);
break;
case 4:
remov_início (lista);
if (lista->tamanho != 0) printf ("%d elementos:início=%s,fim=%s\n", lista->tamanho, lista->início->dado, lista->fim->dado);
else printf ("lista vazia\n");
exibir (lista);
break;
case 5:
do{ printf ("Inserir a posição: ");
scanf ("%d", &pos); }
while (pos < 1 || pos > lista->tamanho);
getchar ();
remov_na_lista (lista, pos);
if (lista->tamanho != 0)
printf ("%d elementos:início=%s,fim=%s\n", lista->tamanho, lista->início->dado, lista->fim->dado);
else printf ("lista vazia\n");
exibir (lista);
break;
case 6:
destruir (lista);
printf ("A lista foi destruída: %d elementos\n", lista->tamanho); break; }
}
return 0;
}
/* -------- FIM lista.c --------- */
Foto: © Everypixel.
- Lista simplesmente encadeada
- Lista simplesmente encadeada em c - Melhores respostas
- Lista encadeada - Melhores respostas
- Lista duplamente encadeada em c - Dicas -C
- Lista encadeada circular - Dicas -C
- Considere uma lista circular simplesmente encadeada com "n" elementos. após "n - 1" remoções realizadas no final da lista podemos afirmar que: - Fórum Programação
- Lista little alchemy - Dicas -Videogames
- Lista de contatos gmail - Dicas -Gmail
Assine nossa newsletter!
