Lista Ligada – C

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:

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

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

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