Reading Time: 9 minutes

E cá estamos nós para mais um artigo, este sobre Listas Simplesmente Ligadas, isto quer dizer que apenas é utilizado 1 apontador entre blocos de memória ou seja “entre cada nodo”.




Como se pode observar apenas 1 e 1 só apontador é utilizado para ligar nodos distintos.

Esta é a técnica utilizada em listas simplesmente ligadas, assim que necessário a introdução de mais um valor é criado mais um pedaço de memória (um nodo) e inserido na lista. Vamos então ver a seguir como fazê-lo.

O que é uma lista ligada (linked list)?


Uma lista ligada ou lista encadeada é uma estrutura de dados linear e dinâmica. Ela é composta por blocos que apontam para o próximo elemento da lista. Para “ter” uma lista ligada/encadeada, basta guardar seu primeiro elemento, e seu último elemento aponta para um bloco nulo, exactamente como a representação em cima.

E porquê o uso de listas invés de arrays / vectores?


Visto que um array é representado numa sequência, ou seja ele guarda a informação em blocos de memória sequênciais, poderia surgir o caso em que o número de dados a carregar para memória
fosse suficientemente grande para que coubesse de uma forma sequencial em memória, daí o uso de listas, em que cada pedaço de memória (nodo) é armazenado num “qualquer” lugar em memória e
ligados entre si através de ponteiros/apontadores, algo como observamos na figura em cima.

Fantástico, já sabemos então como funcionam as listas, agora vamos fazer um exercício para ver se ficou bem percebido.


Passos que vamos seguir para a elaboração do pequeno programa:

  • Carregar dados de um ficheiro de texto
  • Elaborar uma função que leia os dados do ficheiro e posteriormente os carregue para memória, ou seja, para a nossa lista
  • Mostrar a lista com os dados carregados

Pois é, são somente estes 3 passos que vamos fazer.

Vamos então começar, o nosso ficheiro vai ter o nome “dados.txt” e vai conter os seguintes dados.

Xavier 18
Ana 22
Pedro 20
Miguel 51
Hugo 37
Mariana 12


Em que do lado esquerdo temos o nome de 6 indivíduos e mais à direita um int que representa a idade do mesmo.

Ok, esta-se mesmo a ver que o ideal é criarmos uma “estrutura”, para que possamos guardar o nome da pessoa, a sua idade e muito importante, um ponteiro para o próximo bloco de memória.

Estou a falar em algo assim:

O 1 nodo contém a informação sobre o Xavier, com o apontador (setinha) para o próximo elemento, para que possamos navegar até ao final da lista e percorrer todas as pessoas, daí a obrigatoriedade dele, senão ficaríamos só com o xavier, como ele não tinha ligação para nenhum lado era nos impossível obter todos os outros.


1º Passo – Construção então da estrutura, em C ficaria:

typedef struct Pessoa{
   char nome[50];
   int idade;
   struct Pessoa *next; // este é o apontador para o próximo nodo 
}PESSOA

Como podemos observar é uma estrutura familiar, contém somente um apontador do tipo de estrutura Pessoa, isto irá servir para ligar a outro bloco de memória do mesmo tipo (Pessoa), neste caso o xavier fica ligado à ana, e assim temos uma lista com 2 elementos.


2º Passo – Vamos passar então a leitura dos dados do ficheiro e à construção da lista ligada.

Vamos então declarar uma função do tipo PESSOA, que é o tipo da nossa estrutura e vamos retornar um apontador, que ficará como a cabeça da lista, ou seja, o primeiro bloco de memória de referência, neste caso o xavier, e é de extrema importância que esse apontador não se desloque até ao final da lista, caso contrário perderemos a ligação do 1º nodo com o 2º e assim em diante, então a solução será, criar um apontador “L” atribuir-lhe logo de inicio o bloco de memória referente ao xavier, e depois sim, em seguida atribuir a outro ponteiro=L e trabalhar com ele ..

O aux é o nosso ponteiro que ficará sempre posicionado no último elemento inserido, assim quando for necessário inserir um próximo é a ele que nos devemos referir.

Neste caso o L ficou preso no xavier ou seja, na cabeça da lista, é o nosso inico da lista, portanto é sempre ele que devemos retornar na função.

  1. //ler do ficheiro os valores e armazena-los em memoria
  2. PESSOA *Ler(){
  3.         PESSOA *L=NULL,*aux;
  4.         FILE *f;
  5.         char buff[50];
  6.         int idade;     
  7.         //abrir o ficheiro de dados
  8.         f=fopen(“dados.txt”,“r”);
  9.         //verificar se o ficheiro existe
  10.         if(f==NULL)
  11.                 return(NULL);
  12.              
  13.          while(fscanf (f, “%st%d”, buff,&idade)!=EOF){
  14.                 //se a lista estiver vazia, inserimos na 1 posicao             
  15.                 if(L==NULL){
  16.                         //reservar memoria do tipo de estruct PESSOA
  17.                         L=(PESSOA*)malloc (1*sizeof(PESSOA));
  18.                         //enviar nome para o nodo criado em memoria    
  19.                         strcpy(L->nome,buff);
  20.                         //enviar idade para nodo criado em memoria
  21.                         L->idade=idade;
  22.                         //declarar “a seta” do proximo nodo a NULL (vazio)
  23.                         L->next=NULL;
  24.                         //a partir de agr o aux e’ a nossa lista (L -> cabeca da lista)
  25.                         aux=L;
  26.                 }
  27.                 else {
  28.                         aux->next=(PESSOA*)malloc (1*sizeof(PESSOA));
  29.                         aux=aux->next;
  30.                         strcpy(aux->nome,buff);
  31.                         aux->idade=idade;
  32.                         aux->next=NULL;
  33.                 }
  34.         }
  35.        
  36.         return(L);
  37. }
Fantástico, já lemos os dados do ficheiro e criamos blocos de memória ligados sequencialmente.

Bem agora só nos falta mostrar os dados da lista.

Como ficaria a função, então, sabemos que o L era a nossa cabeça da lista, então nesse caso só temos de criar uma função do tipo void (onde o retorno é NULL) passamos a lista como parâmetro,
uma cópia de L é criada, e podemos avançar com ele passando nodo a nodo e mostrando os seus dados.


  1. //funcao para mostrar o que existe na lista

  2. void Showlist(PESSOA *L){
  3.         if(L==NULL){
  4.                 printf(“A Lista esta’ vazia!n);
  5.                 return;
  6.         }
  7.         else {
  8.                 //enquanto houver nodos..
  9.                 while(L!=NULL){
  10.                         printf(“Nome: %s  =  idade %dn,L->nome,L->idade);
  11.                         L=L->next;             
  12.                 }
  13.         }
  14.         return;
  15. }


Ora porra, fantástico, já conseguimos ler, carregar para listas ligadas e mostrar o seu conteúdo 🙂

Agora bastava chamar as funções no main e estava prontinho.Notar que a função de leitura poderia ser muito mas muito optimizada, mas traria talvez uma certa confusão, penso que esta é a forma mais fácil e simples.
Deixo então o código dos dois ficheiros, o ficheiro de texto com os dados e o ficheiro com o código em c.

Ficheiro de Texto: (nome: dados.txt)

Xavier 18
Ana 22
Pedro 20
Miguel 51
Hugo 37
Mariana 12


Ficheiro com o Código:

  1. /*#########################################
  2. #      LISTAS SIMPLESMENTE LIGADAS        #
  3. #           @2012 by PEDRO TAVARES        #
  4. #      http://ptavares.blogspot.com       #
  5. #                                         #
  6. #########################################*/
  7. /*bibliotecas*/
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include <string.h>
  11. //definir a estrutura apropriada
  12. typedef struct Pessoa{
  13.         char nome[50];
  14.         int idade;
  15.         struct Pessoa *next;
  16. }PESSOA;
  17. //ler do ficheiro os valores e armazena-los em memoria
  18. PESSOA *Ler(){
  19.         PESSOA *L=NULL,*aux;
  20.         FILE *f;
  21.         char buff[50];
  22.         int idade;     
  23.         //abrir o ficheiro de dados
  24.         f=fopen(“dados.txt”,“r”);
  25.         //verificar se o ficheiro existe
  26.         if(f==NULL)
  27.                 return(NULL);
  28.       
  29.          while(fscanf (f, “%st%d”, buff,&idade)!=EOF){
  30.                 //se a lista estiver vazia, inserimos na 1 posicao             
  31.                 if(L==NULL){
  32.                         //reservar memoria do tipo de estruct PESSOA
  33.                         L=(PESSOA*)malloc (1*sizeof(PESSOA));
  34.                         //enviar nome para o nodo criado em memoria    
  35.                         strcpy(L->nome,buff);
  36.                         //enviar idade para nodo criado em memoria
  37.                         L->idade=idade;
  38.                         //declarar “a seta” do proximo nodo a NULL (vazio)
  39.                         L->next=NULL;
  40.                         //a partir de agr o aux e’ a nossa lista (L -> cabeca da lista)
  41.                         aux=L;
  42.                 }
  43.                 else {           
  44.                         aux->next=(PESSOA*)malloc (1*sizeof(PESSOA));
  45.                         aux=aux->next;
  46.                         strcpy(aux->nome,buff);
  47.                         aux->idade=idade;
  48.                         aux->next=NULL;                 
  49.                 }
  50.         }
  51.        
  52.         return(L);
  53. }
  54. //funcao para mostrar o que existe na lista
  55. void Showlist(PESSOA *L){
  56.         if(L==NULL){
  57.                 printf(“A Lista esta’ vazia!n);
  58.                 return;
  59.         }
  60.         else {
  61.                 //enquanto houver nodos..
  62.                 while(L!=NULL){
  63.                         printf(“Nome: %s  =  idade %dn,L->nome,L->idade);
  64.                         L=L->next;             
  65.                 }
  66.         }
  67.         return;
  68. }
  69. int main(){
  70.        
  71.         //declaracao da lista
  72.         PESSOA *L=NULL;
  73.         //carregar dados para a lista
  74.         L=Ler();
  75.         //mostrar dados da lista.
  76.         printf(“::::::LISTAGEM::::::n);      
  77.         Showlist(L);   
  78.         printf(“::::::FIM LISTAGEM::::::n);
  79.         return (0);
  80. }

Pedro Tavares is a professional in the field of information security, working as an Ethical Hacker, Malware Analyst, Cybersecurity Analyst and also a Security Evangelist. He is also a founding member and Pentester at CSIRT.UBI and founder of the security computer blog seguranca-informatica.pt.

In recent years he has invested in the field of information security, exploring and analyzing a wide range of topics, such as pentesting (Kali Linux), malware, hacking, cybersecurity, IoT and security in computer networks.  He is also Freelance Writer.

Read more here.