Jump to content
PsySc0rpi0n

Listas Ligadas Simples - Tentar entender o conceito

Recommended Posts

PsySc0rpi0n

Boas...

Tenho este fim de semana para conseguir entender as listas ligadas.

Eu tenho este code

#include<stdio.h>
#include<stdlib.h>



/* struct */

typedef struct node {
   int value;
   struct node *next;
} NODE;


NODE *create_node(int value)
{
   NODE *new;

   if (!(new =malloc(sizeof(NODE)))) return NULL;
   new->value = value;
   new->next= NULL;

   return new;
}

NODE *append_node(NODE *head, int value)
{
   NODE *new;
   NODE *current_node = head;
   NODE *anterior_node = NULL;

   if((new = create_node(value)) == NULL) return NULL;

   while(current_node != NULL && current_node->value < value)
   {   
    anterior_node = current_node;
    current_node = current_node->next;
   }

   if (anterior_node == NULL)
   {
    new->next = head;
    head = new;
   }
   else
   {
    new->next = current_node;
    anterior_node->next = new;
   }
}

void print_list(NODE *head)
{
   NODE *current_node = head;
   while(current_node != NULL){
    printf("%d\n",current_node->value);
    current_node = current_node->next;
   }
}


int main(void)
{
   NODE *head = create_node(10);


   append_node(head, 20);
   print_list(head);
   return 0;
}

Tenho aqui umas dúvidas...

Coloco o link do ideone para ser mais fácil identificar as linhas a que me estou a referir

http://ideone.com/05LfVK

As variáveis declaradas nas linhas 28 e 29, são ponteiros, certo?

Portanto se me referir a elas como current_node e anterior_node estou a aceder aos respectivos endereços de memória, certo?

E se me referir a elas como current_node->value e anterior_node->value estou a aceder aos conteúdos dos campos das variáveis, certo?

Então o que está a acontecer na linha 35 e 36? Está-se a guardar o endereço de memória de current_node em anterior_node? Ou estamos a falar de conteúdos das variáveis?


Kurt Cobain - Grunge misses you

Nissan GT-R - beast killer

Share this post


Link to post
Share on other sites
Rui Carlos

Nas linhas 35 e 36 estás a avançar uma posição na lista.

current_node->value é o valor (inteiro) armazenado no nodo. Mas em current_node->next (usado na linha 36) tens um apontador para o próximo elemento (repara que o campo next é um apontador). Ou seja, o conteúdo da variável é um endereço de memória.

Share this post


Link to post
Share on other sites
PsySc0rpi0n

Ok, mas tentando representar isto por um rectângulo, podemos dizer que é um rectângulo que tem, entre outros campos, outros dois campos específicos, em que um é o próprio endereço de memória do nó e outro que é o endereço de memória do próximo nó, caso já exista?

Algo deste género?

b4cv.jpg

Depois para correr a lista poderá ser algo deste género?

b7tt.jpg

Ou seja, a linha 35 guarda em 1 o conteúdo para onde aponta 2, ou seja o que existe em 3. E a linha 36 guarda em 3 o conteúdo para onde aponta o 4, ou seja o que existe em 5.

Será que posso imaginar a coisa desta forma?


Kurt Cobain - Grunge misses you

Nissan GT-R - beast killer

Share this post


Link to post
Share on other sites
HappyHippyHippo

listas ligadas simples:

 +-------+   +-------+   +-------+
 | next----->| next----->| next  |
 | dados |   | dados |   | dados |
 +-------+   +-------+   +-------+

o que tens são ponteiros para elementos desta lista

um que aponta para o nó actual e um que apnota para o anterior do actual:

   anterior    actual
     |           |
     v           V
 +-------+   +-------+   +-------+
 | next----->| next----->| next  |
 | dados |   | dados |   | dados |
 +-------+   +-------+   +-------+

Edited by HappyHippyHippo

IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
PsySc0rpi0n

Eu já vi esses esquemas pela net mas não os consigo comparar com o código que tenho visto, por isso tentei fazer um esquema para tentar entender o que está a ser guardado e onde está a ser guardado...

Quero perceber num esquema o que acontece nas linhas 35 e 36 do code...

Na linha 28 guarda-se o CONTEÚDO de head em current_node e depois nas linhas 35 e 36 já estamos a falar apenas de endereços de memória, certo?

Edited by PsySc0rpi0n

Kurt Cobain - Grunge misses you

Nissan GT-R - beast killer

Share this post


Link to post
Share on other sites
Rui Carlos

Na linha 28 guarda-se o CONTEÚDO de head em current_node e depois nas linhas 35 e 36 já estamos a falar apenas de endereços de memória, certo?

current_node->value é o valor (inteiro) armazenado no nodo. Mas em current_node->next (usado na linha 36) tens um apontador para o próximo elemento (repara que o campo next é um apontador).

Share this post


Link to post
Share on other sites
PsySc0rpi0n

Acho que a resposta à minha pergunta é sim.

Depois neste code

if (anterior_node == NULL)
   {
       new->next = head;
       head = new;
   }
   else
   {
       new->next = current_node;
       anterior_node->next = new;
   }

O que é que está a acontecer? Não percebo o significado da condição do if. E não percebo o que está a ser feito no else... Em termos de programação percebo mas em termos de "linguagem corrente" não percebo!

Edited by PsySc0rpi0n

Kurt Cobain - Grunge misses you

Nissan GT-R - beast killer

Share this post


Link to post
Share on other sites
HappyHippyHippo

vamos lá então explicar o código.

primeiro de tudo, tens de contextualizar-lo. para que serve. onde está a ser usado.

antes de mais, tens de perceber que o código está dentro de uma função em que o objectivo é adicionar um novo nó na lista de forma ordenada.

que passos são necessário para fazer esta acção ?

- criar o novo nó

- saber qual a posição da lista onde inserir o novo nó

- dizer ao nó criado que o nó seguinte é o nó na posição que se deseja

- dizer ao nó anterior à posição a ser inserida que o nó seguinte e o nó criado

prontos, desse forma tens a inserção na lista

no entanto existe um caso particular : mas e se a lista estivar vazia ou a posição é a primeira? qual é o nó anterior ?

prontos, agora que sabes que existe um caso particular, basta adaptar o código para que possa verificar se estamos nessa situação.

explicação do código :

/**
* Função que adicionar um novo elemento à lsita de uma forma ordenada
*
* @param hear  Ponteiro para a lista/primeiro elemento da lista ao qual o elemento irá ser adicionado
* @param value Valor que irá ser adicionado à lista
* @return      Ponteiro para a lista à qual o elemento foi adicionado, ou NULL em caso de erro
*/
NODE *append_node(NODE *head, int value)
{
   NODE *new;
   // o estado inicial do ponteiro para o nó actual é apontar para o nó inicial
   NODE *current_node = head;
   // como estamos no nó inicial, não existe nó anterior
   NODE *anterior_node = NULL;

   // criar o nó a ser adicionado à lista
   if((new = create_node(value)) == NULL) return NULL;

   // ciclo de pesquisa pelo primeiro elemento da lista tal que o valor guardado é maior que o valor a ser inserido
   // isto quer dizer que enquanto o nó actual for válido (diferente de NULL)
   // e o valor do nó for menor que o valor a ser inserido
   // a lista irá ser "iterada"
   while(current_node != NULL && current_node->value < value)
   {
           // guardar o ponteiro do nó actual no nó anterior
           anterior_node = current_node;
           // "mover" o actual para o nó seguinte
           current_node = current_node->next;
   }

   // verificar se "existe" nó anterior à posição em que o nó irá ser inserido
   // isto são os casos em que a lista se encontra vazia ou
   // ou todos os elementos da lista contem um valor superior ao valor inserido
   if (anterior_node == NULL)
   {
           // dizer ao nó criado que o seguinte é o nó à cabeça actual
           new->next = head;

           // o nó à cabeça da lista passa a ser o criado
           head = new;

           // não existe anterior, logo não te precisas de preocupar com isso ...
   }
   else
   {
           // só entra neste código se for uma inserção que não seja à cabeça da lista

           // vamos dizer ao nó criado que o seguinte é o nó que se encontra na posição a ser inserido
           new->next = current_node;

           // vamos dizer ao nó anterior que aponta para "current_node" que o nó seguinte agora é o nó criado
           anterior_node->next = new;
   }

   // FALTA O RETURN (MUITO IMPORTANTE) !!!!!
   return head;
}

no entanto, è minha opinião que este método de usar dois ponteiro é mais confusa que o método que costumo usar:

NODE *append_node(NODE *head, int value)
{
 NODE *created;
 NODE *iter = head;

 // criar o novo nó
 if((created = create_node(value)) == NULL) return NULL;

 // se for para inserir à cabeça
 // - lista vazia
 // - valor é inferior ao valor mais inferior da lista (primeiro)
 if (iter == NULL || iter->value > value) {
   // inserir à cabeça da lista
   created->next = head;
   head = created;
 } else {
   // ciclo de pesquisa da posição a inserir o nó
   // enquanto houver um elemento seguinte e esse elemento tiver um valor inferior ao valor a inserir
   while (iter->next != NULL && iter->next->value < value)
     // iterar a lista
     iter = iter->next;

   // iter aponta sempre para o elemento com o maior valor guardado que seja menor que o valor a ser inserido
   // (elemento imediatamente antes da posição a inserir o novo nó)

   // guardar no novo nó que o nó seguinte é o nó que se encontra na posição a ser inserido
   created->next = iter->next;
   // guardar no nó "iter" (anterior à posição) que o nó seguinte é o nó criado
   iter->next = created;
 }

 return head;
}

Edited by HappyHippyHippo
  • Vote 1

IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
PsySc0rpi0n

O exemplo que eu coloquei é da autoria do Mkman...

Em qualquer um dos exemplos, estamos apenas a atribuir às variáveis, endereços de memória, certo?

Diz-me se este vídeo segue os vossos algoritmos, porque parece que é um dos vídeos mais esclarecedores que eu encontrei apesar de ainda não me ter esclarecido a 100%...

https://www.youtube.com/embed/o5wJkJJpKtM?feature=oembed


Kurt Cobain - Grunge misses you

Nissan GT-R - beast killer

Share this post


Link to post
Share on other sites
HappyHippyHippo

metade de vídeo é repetir o que já foi exemplificado.

o uso do C++ é superficial (onde andam as classes ?)

novamente uso o método de usar 2 ponteiros onde 1 bastaria


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
PsySc0rpi0n

Bem, depois de ter estado a analisar este exemplo vou tentar resolver o seguinte exercício de listas ligadas...

Crie um programa que utiliza uma lista ligada de inteiros. A função main deverá ler um conjunto de números positivos, via teclado, que devem ser guardados numa lista ligada. Todos os elementos da lista devem permanecer dispostos por ordem crescente. Quando for inserido um número negativo, o programa deve mostrar o conteúdo da lista ligada!

Primeiro: os números pedidos devem ser armazenados num vector ou deve ser usada apenas uma variável e ir criando a lista, à medida que cada número vai sendo inserido?


Kurt Cobain - Grunge misses you

Nissan GT-R - beast killer

Share this post


Link to post
Share on other sites
HappyHippyHippo

Primeiro: os números pedidos devem ser armazenados num vector ou deve ser usada apenas uma variável e ir criando a lista, à medida que cada número vai sendo inserido?

sinceramente ...

afinal qual o sentido que achas ter as listas ligadas ?


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
PsySc0rpi0n

Ir adicionando nodes à medida que são necessários!!!


Kurt Cobain - Grunge misses you

Nissan GT-R - beast killer

Share this post


Link to post
Share on other sites
PsySc0rpi0n

Bem, para já tenho o seguinte code e quero continuar com pequenos passos...

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

typedef struct{
 int value;
 struct NODE *next;
}NODE;

NODE *CreateNode(int value){
 NODE *newn;

 if((newn = malloc(sizeof(NODE)))== NULL){
   printf("Memory error!\n");
   return NULL;
 }

 newn->value = value;
 newn->next = NULL;

 return newn;
}

NODE *Append_Node(NODE *head, int value){
 NODE *newn,
   *link = head;

 if((newn = CreateNode(value)) == NULL){
   printf("Memory error\n");
   return NULL;
 }

 if(link->value > value){
   newn->next = link;
   link->next = NULL;
 }
 return newn;
}

int main (void) {
 NODE *head;
 int value, ct = 0;

 do{
   printf("Enter a number:\n");
   printf("Enter a negative value to end input!\n");
   scanf("%d", &value);
   if(value >= 0){
  if(++ct == 1)
    head = CreateNode(value);
  else
    Append_Node(head, value);
   }
 }while(value >= 0);

 getchar ();
 return 0;
}

Neste momento quero perceber quais são as coisas que preciso de fazer para construir a função append_node...

Da maneira que tenho o code, não é preciso verificar se já existe algum node ou não, certo? Porque tenho o if que faz essa verificação e usa a função Create_Node para criar um node. Depois que o code passa aqui uma vez, já não passa lá mais, certo?

Há algum problema até agora, no que já está feito?

Edited by PsySc0rpi0n

Kurt Cobain - Grunge misses you

Nissan GT-R - beast killer

Share this post


Link to post
Share on other sites
HappyHippyHippo

que tal compilar e (tentar) corrigir os erros que aparecem ?

dica :

o erro que te vai aparecer é um bocado dissimulado pela permissão do compilador de usar alguns tipos de dados ainda não declarados

se mesmo assim não consegues resolver, tira a porcaria do typedef


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
PsySc0rpi0n

O que não estou a perceber agora é o seguinte:

no teu exemplo da função append_node

NODE *append_node(NODE *head, int value)
{
 NODE *created;
 NODE *iter = head;

 // criar o novo nó
 if((created = create_node(value)) == NULL) return NULL;

 // se for para inserir à cabeça
 // - lista vazia
 // - valor é inferior ao valor mais inferior da lista (primeiro)
 if (iter == NULL || iter->value > value) {
   // inserir à cabeça da lista
   created->next = head;
   head = created;
 } else {
   // ciclo de pesquisa da posição a inserir o nó
   // enquanto houver um elemento seguinte e esse elemento tiver um valor inferior ao valor a inserir
   while (iter->next != NULL && iter->next->value < value)
  // iterar a lista
  iter = iter->next;

   // iter aponta sempre para o elemento com o maior valor guardado que seja menor que o valor a ser inserido
   // (elemento imediatamente antes da posição a inserir o novo nó)

   // guardar no novo nó que o nó seguinte é o nó que se encontra na posição a ser inserido
   created->next = iter->next;
   // guardar no nó "iter" (anterior à posição) que o nó seguinte é o nó criado
   iter->next = created;
 }

 return head;
}

Caso já não seja o primeiro node, o code salta para o else do if, certo? E vai tentar percorrer a lista.

Mas se existir apenas um node, criado pela função Create_Node

NODE *create_node(int value)
{
   NODE *new;

   if (!(new =malloc(sizeof(NODE)))) return NULL;
   new->value = value;
   new->next= NULL;

   return new;
}

Esse node tem NULL no campo "next", certo?

Então como é que, se a lista apenas tiver um node, o while não falha logo na primeira iteracção já que o iter->next == NULL????

que tal compilar e (tentar) corrigir os erros que aparecem ?

dica :

o erro que te vai aparecer é um bocado dissimulado pela permissão do compilador de usar alguns tipos de dados ainda não declarados

se mesmo assim não consegues resolver, tira a porcaria do typedef

O typedef não está a dar problema nenhum...


Kurt Cobain - Grunge misses you

Nissan GT-R - beast killer

Share this post


Link to post
Share on other sites
HappyHippyHippo

O que não estou a perceber agora é o seguinte:

no teu exemplo da função append_node

Caso já não seja o primeiro node, o code salta para o else do if, certo? E vai tentar percorrer a lista.

Mas se existir apenas um node, criado pela função Create_Node

Esse node tem NULL no campo "next", certo?

Então como é que, se a lista apenas tiver um node, o while não falha logo na primeira iteracção já que o iter->next == NULL????

só entra no bloco verdadeiro do if se:

- a lista tiver vazia

- o elemento a inserir tem um valor inferior ao primeiro elemento da lista

agora o teu problema é se a lista só tiver um elemento.

se entrou no else, é porque é para inserir numa posição que não a primeira.

o while vai falhar logo na primeira iteração ? claro que vai, e é essa a intenção !!!

pensa bem no que acontece se a lista só tiver um elemento :

else {
//
//   iter                         created
//    |                              |
//    v                              v
//  +-------+                    +-------+
//  | next------X                | next------X
//  | v(1)  |                    | v(2)  |
//  +-------+                    +-------+

while (iter->next != NULL && iter->next->value < value) // <--------------- (falha porque iter->next == NULL)
    iter = iter->next;

created->next = iter->next; //  <----------------- como iter->next é NULL. fica tudo na mesma

//   iter                         created
//    |                              |
//    v                              v
//  +-------+                    +-------+
//  | next------X                | next------X
//  | v(1)  |                    | v(2)  |
//  +-------+                    +-------+

iter->next = created;

//   iter                         created
//    |                              |
//    v                              v
//  +-------+                    +-------+
//  | next---------------------->| next------X
//  | v(1)  |                    | v(2)  |
//  +-------+                    +-------+

imagina agora que a lista tem dois elementos e é para colocar na segunda posição (depois da primeira)

else {

//   iter                                 created
//    |                                     |
//    v                                     v
//  +-------+    +-------+                +-------+
//  | next------>| next------x            | next------X
//  | v(1)  |    | v(3)  |                | v(2)  |
//  +-------+    +-------+                +-------+

while (iter->next != NULL && iter->next->value < value) // <--------------- (falha porque iter->next->value < value é falso)
   iter = iter->next;

created->next = iter->next;

//   iter                                 created
//    |                                     |
//    v                                     v
//  +-------+    +-------+                +-------+
//  | next------>| next------x            | next----+
//  | v(1)  |    | v(3)  |                | v(2)  | |
//  +-------+    +-------+                +-------+ |
//                  A                               |
//                  |                               |
//                  +-------------------------------+

iter->next = created;

//   iter                                 created
//    |       +----------------------+      |
//    v       |                      |      v
//  +-------+ |  +-------+           |    +-------+
//  | next----+  | next------x       +--->| next----+
//  | v(1)  |    | v(3)  |                | v(2)  | |
//  +-------+    +-------+                +-------+ |
//                  A                               |
//                  |                               |
//                  +-------------------------------+

que como podes ver, é inserir o nó criado logo após ao nó apontado pelo ponteiro "iter"

O typedef não está a dar problema nenhum...

eu não disse que o problema era o typedef, mas o retirar o typedef ajudar-te-á a ver onde está o problema

Edited by HappyHippyHippo
  • Vote 1

IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
PsySc0rpi0n

Esta explicação foi mesmo à prova de burros (eu)... Assim já tive uma percepção melhor de como as coisas funcionam...

Depois hei-de voltar a colocar aqui mais dúvidas.

Agora ainda me faltam 2 exames...


Kurt Cobain - Grunge misses you

Nissan GT-R - beast killer

Share this post


Link to post
Share on other sites
PsySc0rpi0n

Bem, não resisti e tentei fazer umas funções para trabalhar com listas. Como estou a tentar fazer um programa com vários files, não pude testar as funções e queria que me ajudassem a descobrir quais os problemas e como os resolver.

Fica aqui o code

Student *AddNode(){
Student *node = NULL;
if((node = malloc(sizeof(Student))) == NULL){
	printf("Memory Error!\n");
	return NULL;
}
return node;
}


int isEmpty(Student *node){
if(node == NULL)
	return 0;
else
	return 1;
}

void ShowData(Student *node){
pritnf("Student Name: %s\n", node->name);
if(tolower(node->gen) == 'm')
	printf("Student gender: Male\n");
if(tolower(node->gen) == 'f')
	printf("Student gender: Female\n");
else
	printf("Invalid data found!\n");
printf("Weight: %.2f\n", node->weight);
}

void ShowAll(Student *node){
while(node != NULL){
	ShowData(node);
	node = node->next;
}
}


Student *insertNewbg(Student *head){
Student *Newbg, *aux;

aux = head;

if((Newbg = AddNode()) == NULL){
	printf("Error creating new node!\n");
	return NULL;
}

if(aux == NULL){
  Newbg->next = aux;
  head = Newbg;
}
return head;
}


Student *insertNewend(Student *head){
Student *Newend, *aux;

if((Newend = AddNode()) == NULL){
  printf("Memory error!\n");
  return NULL;
}
while(aux->next != NULL){
  aux = aux->next;
}

aux->next = Newend;
return Newend;
}


void FillNode(Student *node){
printf("Enter student name:\n");
CLEAR_INPUT;
fgets(node->name, sizeof(node->name), stdin);
printf("Enter gender:\n");
CLEAR_INPUT;
fgets(node->gender, sizeof(char),stdin);
printf("Enter weight:\n");
CLEAR_INPUT;
fscanf(stdin, "%f", node->weight);
printf("Data saved!\n");
}


Student *DelNode(Student *node, unsigned int number){//ainda está a ser trabalhada
 Student *aux = node, *tmp = NULL;
 //free the first node
 if(number == aux->number){
tmp = aux;
node = aux->next;
free(tmp);
 }
 //free any node but the first and the last
 while(aux->next->next != NULL){
if(number == aux->next->number){
  tmp = aux->next;
  aux = aux->next->next;
  free(tmp);
}
aux = aux->next;
 }
 //free the last node
 if(aux->next->next == NULL){
tmp = aux->next;
aux->next = NULL
free(tmp);
 }
 return node;
}

Edited by PsySc0rpi0n

Kurt Cobain - Grunge misses you

Nissan GT-R - beast killer

Share this post


Link to post
Share on other sites
HappyHippyHippo

estás à espera que eu leia o código todo e faça a função de um compilador ?


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.