Listas simplesmente encadeadas

Setembro 2017


LISTAS SIMPLESMENTE ENCADEADAS


Requisitos

tipos de dados
As estruturas
O uso do typedef
Os ponteiros
As funções do usuário

As listas encadeadas podem ser usadas quando várias operações de inserção/remoção de elementos se fazem necessárias.

Definição

As listas encadeadas são estruturas de dados semelhantes às tabelas, exceto que o acesso a um elemento não é feito por índice mas através de um ponteiro. .
A alocação da memória é feita durante a execução. Em uma lista, os elementos são contíguos no que se refere ao encadeamento.

No entanto, em comparação com as tabelas, onde os elementos ficam contíguos na memória, os elementos de uma lista ficam espalhados na memória. A conexão entre os elementos se realiza por um ponteiro. Na verdade, na memória é aleatória, dependendo do espaço alocado.

O ponteiro "seguinte" ao último elemento deve dirigir para o NULL (o fim da lista), e ara acessar um elemento, a lista é varrida começando do topo, o ponteiro "seguinte" permite o deslocamento para o elemento seguinte. O deslocamento se faz em um único sentido, do primeiro para o último elemento. Se você quiser deslocar nos dois sentidos (para frente/para trás) use as listas duplamente encadeadas.

A construção do protótipo de um elemento da lista

Para determinar um elemento da lista vamos nos servir do tipo struct. O elemento da lista conterá um campo dado, um ponteiro "seguinte". O ponteiro "seguinte" deve ser igual que o elemento, se não ele não poderá indicar para o elemento. O ponteiro "seguinte" permitirá o acesso ao próximo elemento.

typedef struct ElementoLista {
char *dado;
struct ElementoLista *"seguinte";
}elemento;


Para o controle da lista é melhor salvar certos elementos: o primeiro e o último bem como o número de elementos. Para fazer isso, usaremos outra estrutura (isto não é obrigatório, as variáveis podem ser usadas).
Veja a sua composição:

typedef struct ListaDetectada {
elemento *início;
elemento *fim;
int tamanho;
}Liste;


O ponteiro de início abrigará o endereço do primeiro elemento da lista e o ponteiro de fim vai abrigar 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 de início e fim sempre apontarão, respectivamente, para o primeiro e o último elemento. O campo tamanho vai conter o número de elementos da lista, seja qual for a operação efetuada na lista.

Operações em listas encadeadas

Para a inserção e a exclusão, uma única função é suficiente, se ela foi desenvolvida corretamente, de acordo com as necessidades. No entanto, lembrem-se que este artigo é puramente didático. É por isso que foi criada uma função para cada operação de inserção e exclusão.

Inicialização

Protótipo da função:
void inicialização (Lista *lista);

A operação deve ser executada antes de qualquer outra operação da lista. Ela inicializa o ponteiro de início e de fim com o NULL, e oTamanho com o valor 0.

A função

void inicialização (Liste *liste){
liste->início = NULL;
liste->fim = NULL;
tamanho = 0;
}

Inserção de um elemento da lista

Veja o algoritmo de inserção e backup dos elementos:


Declaração dos elementos a serem inseridos
Alocação da memória para o novo elemento
Preenchimento do conteúdo do campo de dados
Atualização dos ponteiros para o 1° e o último elemento, si necessário.
Particularidade: em uma lista com apenas um elemento, o primeiro também é o último.
Atualização do Tamanho lista

Para adicionar um elemento na lista, existem várias soluções:
1.integração
2. Inserção no início da lista
3. Inserção no fim da lista
4. Inserção em outro lugar da lista

Inserção em uma liste vazia

Protótipo da função:
int ins_na_lista_vazia (Lista *lista, char *dado);

A função retorna -1 em caso de falha, se não ela retorna 0.

Passos:
Alocação da memória para o novo elemento
Preenchimento do campo de dados do novo elemento
O ponteiro "seguinte" do novo elemento dirigir-se-á para NULL
Os ponteiros de início e de fim indicarão o novo elemento
O tamanho é atualizado

[Image: http://www.commentcamarche.net/faq/images/0-lQg6lQKF-l-ins-liste-vazia-s-.png|500px|]

A função

/* inserção em uma liste vazia */
int ins_em_uma_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;
liste->início = novo_elemento;
liste->fim = novo_elemento;
liste->tamanho++;
return 0;
}

Inserção no início da lista

Protótipo da função:
int ins_início_liste (Liste *liste,char *dado);

A função é exibida uma nova vez -1 em caso de falha, caso contrário ela retorna 0.


Passos:

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 o 1° elemento
O ponteiro de início aponta para o novo elemento
O ponteiro de fim não muda
O tamanho é incrementado

[Image: http://www.commentcamarche.net/faq/images/0-WGCuL0sT-l-ins-início-s-.png|500px|]

A 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

Protótipo da função:
int ins_fim_lista (Lista *lista, elemento *em andamento, char *dado);

A função retorna -1 em caso de falha, se não ela retorna 0.

Passos:
Alocação da memória para o novo elemento
Preenchimento do campo de dados do novo elemento
O ponteiro "seguinte" ao último elemento indicará o novo elemento
O ponteiro de fim aponta para o novo elemento
O ponteiro de início não muda
O tamanho é incrementado


A função

/*inserção no fim da lista */
int ins_fim_lista (Lista * lista, elemento * em andamento, 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);
em andamento->"seguinte" = novo_elemento;
novo_elemento->"seguinte" = NULL;
liste->fim = novo_elemento;
liste->tamanho++;
return 0;
}

Inserção em outro lugar da lista

Protótipo da função:
int ins_lista (Lista *lista, char *dado,int pos);

Volta a função -1 em caso de falha, se não ela vem em 0.

A inserção será feita depois de uma certa posição transformada em argumento na função.
A posição indicada não deve ser o último elemento. Neste caso, é preciso utilizar a função de inserção no fim da lista.

Passos:
Alocação da memória para o novo elemento
Preenchimento do campo de dados do novo elemento
Selecionar de uma posição na lista (a inserção será feita depois da posição escolhida)
O ponteiro "seguinte" ao novo elemento indica o endereço do ponteiro “seguinte" do elemento em andamento. (Uma explicação meio enrolada, esperando que a imagem os ajude a compreender melhor)
O ponteiro "seguinte" ao elemento inacabado mostra o novo elemento
Os ponteiros de início e fim não mudam
O tamanho é incrementado de uma unidade


A função

/* inserção na posição solicitada */
int ins_lista (Lista * lista, char *dado, int pos){
if (liste->tamanho < 2)
return -1;
if (pos < 1 || pos >= lista->tamanho)
return -1;
elemento *em andamento;
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;
em andamento = lista->início;
for (i = 1; i < pos; ++i)
em andamento = em andamento->"seguinte";
if (em andamento->"seguinte" == NULL)
return -1;
strcpy (novo_elemento->dado, dado);
novo_elemento->"seguinte" = em andamento->"seguinte";
em andamento->"seguinte" = novo_elemento;
liste->tamanho++;
return 0;
}

Remoção de um elemento da lista

Veja o algoritmo de remoção de um elemento da lista:


O ponteiro temporário para salvar o endereço dos elementos a serem removidos.
O elemento a ser removido se encontra depois do elemento em andamento.
Fazer o ponteiro "seguinte" ao elemento em andamento apontar para o endereço do ponteiro "seguinte" ao elemento a ser removido.
Liberar a memória ocupada pelo elemento removido.
Atualizar o tamanho da lista.
Para remover um elemento da lista existem várias soluções:
1.Supressão no início da lista
2. Remoção em outro lugar da lista

Remoção no início da lista

Protótipo da função :
int remov_início (Lista *lista);

A função retorna -1 em caso de falha, se não ela retorna 0.
Passos:
O ponteiro remov_elem terá o endereço do 1° elemento
O ponteiro início mostrará o 2° elemento
O tamanho da lista será decrementado de um elemento

[Image: http://www.commentcamarche.net/faq/images/0-a5HGHbQl-l-remov-início-s-.png|335px|]

A função

/*Supressão no início da lista */
int remov_início (Lista * lista){
if (liste->tamanho == 0)
return -1;
elemento *remov_elemento;
remov_elemento = lista->início;
lista->início = lista->início->"seguinte";
if (liste->tamanho == 1)
lista->fim = NULL;
free (remov_elemento->dado);
free (remov_elemento);
lista->tamanho--;
return 0;
}

Remoção em outro lugar da lista

Protótipo da função :
int remov_na_lista (Lista *lista, int pos);

A função retorna -1 em caso de falha, se não ela retorna 0.

Passos:

O ponteiro remov_elem terá o endereço para o qual aponta o ponteiro "seguinte" do elemento em andamento
O ponteiro "seguinte" do elemento em andamento indicará para o elemento para o qual aponta o ponteiro "seguinte" ao elemento que segue o elemento em andamento da lista
Se o elemento em andamento for o penúltimo elemento, o ponteiro de fim deve ser atualizado
O tamanho da lista será decrementado de um elemento

[Image: http://www.commentcamarche.net/faq/images/0-rgZ0f0EP-l-remov-apres-pos-s-.png|489px|]

[Image: http://www.commentcamarche.net/faq/images/0-l0FD7klQ-l-remov-apres-avantdernier-s-.png|493px|]

A função

/* remover um elemento após a posição solicitada */
int remov_na_lista (Lista * lista, int pos){
if (liste->tamanho <= 1 || pos < 1 || pos >= lista->tamanho)
return -1;
int i;
elemento *em andamento;
elemento *remov_elemento;
em andamento = lista->início;

for (i = 1; i < pos; ++i)
em andamento = em andamento->"seguinte";
remov_elemento = em andamento->"seguinte";
em andamento->"seguinte" = em andamento->"seguinte"->"seguinte";
if(em andamento->"seguinte" == NULL)
lista->fim = em andamento;
free (remov_elemento->dado);
free (remov_elemento);
lista->tamanho--;
return 0;
}

Visualização da lista

Para exibir a lista inteira nós podemos nos posicionar no início da lista (o ponteiro de início o permitirá). Depois, utilizando o ponteiro "seguinte" de cada elemento, a lista será vista do 1° ao último elemento. A restrição de parada é fornecida pelo ponteiro seguinteao último elemento que equivale ao NULL.

A função

/* a maostragem da lista */
void exibirá (Lista * lista){
elemento *em andamento;
em andamento = lista->início;
while (em andamento != NULL){
printf ("%p - %s\n", em andamento, em andamento->dado);
em andamento = em andamento->"seguinte";
}
}

Destruição da lista

Para destruir a lista inteira, utilizei aSupressão no início da lista enquanto o tamanho for maior que zero.

A 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;
} Liste;

/* inicialização da lista */
void inicialização (Lista * lista);

/* INSERÇÃO */

/*integração */
int ins_na_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 * em andamento, 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 *liste,int *k);
void visualiza (Lista * lista);
void destruir (Lista * lista);
/* -------- FIM lista.h --------- */

lista_function.h


/***************************\
  • lista_function.h * \***************************/ void inicialização (Lista * lista) { lista->início = NULL; lista->fim = NULL; lista->tamanho = 0; } /*integração */ int ins_na_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; liste->início = novo_elemento; liste->fim = novo_elemento; liste->tamanho++; return 0; } /* inserção no início da liste */ 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 * em andamento, 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); em andamento->"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 *em andamento; 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; em andamento = lista->início; for (i = 1; i < pos; ++i) em andamento = em andamento->"seguinte"; if (em andamento->"seguinte" == NULL) return -1; strcpy (novo_elemento->dado, dado); novo_elemento->"seguinte" = em andamento->"seguinte"; em andamento->"seguinte" = novo_elemento; liste->tamanho++; return 0; } /*Supressão no início da lista */ int remov_início (Lista * lista){ if (liste->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; } /* Remover um elemento depois da posição solicitada */ int remov_na_lista (Lista * lista, int pos){ if (liste->tamanho <= 1 || pos < 1 || pos >= lista->tamanho) return -1; int i; elemento *em andamento; elemento *remov_elemento; em andamento = lista->início; for (i = 1; i < pos; ++i) em andamento = em andamento->"seguinte"; remov_elemento = em andamento->"seguinte"; em andamento->"seguinte" = em andamento->"seguinte"->"seguinte"; if(em andamento->"seguinte" == NULL) lista->fim = em andamento; free (remov_elemento->dado); free (remov_elemento); lista->tamanho--; return 0; } /* exibição da lista */ void mostra (Lista * lista){ elemento *em andamento; em andamento = lista->início; while (em andamento != NULL){ printf ("%p - %s\n", em andamento, em andamento->dado); em andamento = em andamento->"seguinte"; } } /* desfazer a lista */ void desconstruir(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(liste->tamanho == 1 || *k == 1){ printf ("1. Adição no início da lista\n"); printf ("2. Adiçã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. Adição no início da lista\n"); printf ("2. Adição no fim da lista\n"); printf ("3. Adiçã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 liste\n"); printf ("7. Fechar\n"); } printf ("\n\nFaça sua selecionar : "); scanf ("%d", &selecionar); getchar(); if(liste->tamanho == 0 && selecionar == 2) selecionar = 7; return selecionar; } /* -------- FIN 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 *em andamento; if ((lista = (Lista *) malloc (sizeof (Lista))) == NULL) return -1; if ((nome = (char *) malloc (50)) == NULL) return -1; em andamento = NULL; selecionar = 'o'; inicialização (lista); int pos, k; while (selecionar != 7){ selecionar = menu (lista, &k); switch (selecionar){ casa 1: printf ("Entre um elemento : "); scanf ("%s", nome); getchar (); if (lista->tamanho == 0) ins_na_lista_vazia (lista, nome); else ins_início_lista (lista, nome); printf ("%d elementos:início=%s,fim=%s\n", liste->tamanho, liste->início->dado, liste->fim->dado); exibe (lista); break; case 2: printf ("Entre 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 (liste); break; case 3: printf ("Entre um elemento:"); scanf ("%s", nome); getchar (); do{ printf ("Entre a posição:"); scanf ("%d", &pos); } while (pos < 1 || pos > lista->tamanho); getchar (); if (liste->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"); exibe (lista); break; case 5: do{ printf ("Entre 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"); exibe (lista); break; case 6: destruir (lista); printf ("a lista foi destruída: %d elementos\n", lista->tamanho); break; } } return 0; }

Veja também

As listas duplamente encadeadas
As listas circulares
As pilhas
As filas

Veja também

Artigo original publicado por Carlos-vialfa. Tradução feita por pintuda. Última modificação: 6 de outubro de 2016 às 10:10 por ninha25.
Este documento, intitulado 'Listas simplesmente encadeadas', está disponível sob a licença Creative Commons. Você pode copiar e/ou modificar o conteúdo desta página com base nas condições estipuladas pela licença. Não se esqueça de creditar o CCM (br.ccm.net) ao utilizar este artigo.