Jump to content

inserir valor - listas ligadas


jpedro20
 Share

Recommended Posts

Boa noite,

Esta é uma pergunta mais direccionada ao Localhost mas se souberem responder também podem.

Estava a ver no blogue a inserção de um valor em listas ligadas.

typedef struct Lista {
  int key;
  struct Lista *next;
}List;

List * addList(List *head, int value) {
  List *new = (List *) malloc(sizeof(List));
  new->key = value;
  new->next = NULL;
  if(!head) {
     head = new;
     return head;
  }
  head->next = new;
  return head->next;
}

Não estou a perceber o caso em que temos 2 valores na lista e queremos inserir um terceiro. Supostamente head contem os 2 valores da lista e no head->next insere o terceiro. Mas depois não retornas apenas o terceiro? Podias explicar? E também se a cabeça for nula ele insere o valor na cabeça  e depois volta a inserir o valor no head->next?

PS: Não estou a dizer que está mal... apenas quero perceber melhor 😄 E se não quiseres que faça aqui referência diz que eu apago o tópico

Desde já obrigado.

Cumprimentos

Link to comment
Share on other sites

E também se a cabeça for nula ele insere o valor na cabeça  e depois volta a inserir o valor no head->next?

Não, porque depois do "head = new" há um return, portanto esse código não é executado.

Mas esse código não funciona bem, se o objectivo é adicionar um novo nó a uma lista passada por "head". Devia procurar o último elemento da lista (aquele cujo next seja NULL) e acrescentar aí o novo nó.

Supostamente head contem os 2 valores da lista e no head->next insere o terceiro.

Não. head é um nó com um valor. head->next é o segundo. head->next->next o terceiro, etc.

❝The idea that I can be presented with a problem, set out to logically solve it with the tools at hand, and wind up with a program that could not be legally used because someone else followed the same logical steps some years ago and filed for a patent on it is horrifying.❞- John Carmack on software patents

A list  of command line apps

Link to comment
Share on other sites

IceBrain: O código funciona bem, só foi um pouco de confusão com os nomes.

Para que não restem dúvidas deixo o código todo:

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

typedef struct Lista {
  int key;
  struct Lista *next;
}List;

List * addList(List *head, int value) {
  List *new = (List *) malloc(sizeof(List));
  new->key = value;
  new->next = NULL;
  if(!head) {
     head = new;
     return head;
  }
  head->next = new;
  return head->next;
}

List *findList(List *head, int value) {
  List *find = head;
  while(find && find->key != value) {
     find = find->next;
  }
  if(!find) return NULL;
  return find;
}

List * deleteList(List *head, int value) {
  List *find = head;
  List *aux = NULL;
  if(head->key == value) {
     aux = head->next;
     free(head);
     return aux;
  }
  while(find && find->next->key != value) find = find->next;
  aux = find->next;
  find->next = aux->next;
  free(aux);
  return head;
}

int main(void) {
  List *head = NULL, *tail = NULL;
  tail = addList(tail,10);
  head = tail;
  tail = addList(tail,20);
  tail = addList(tail,30);
  tail = findList(head,40);
  if(tail) printf("Valor encontrado: %i\n", tail->key);
  else printf("Valor não encontrado\n");
  head = deleteList(head,10);
  while(head) {
    printf("Value: %i\n", head->key);
    head = head->next;
  }
  return 0;
}

Ah, só pûs o nome head porque essa função tanto serve para inicializar a lista como para adicionar um elemento.

here since 2009

Link to comment
Share on other sites

Agora para o jpedro20.

Basicamente, e sem me querer alongar muito, eu no primeiro caso (em que a lista está vazia) verifico isso mesmo, se head, que na verdade é o fim da lista, está a NULL, se estiver crio nela mesma um novo nó, se não estiver significa que a lista já tem elementos e crio na head->next. Não te esqueças que naquele if tem um return, ou seja, não continua com a execução do código.

Tenta criar uma lista de chamadas (pequena, com 3 ou 4 elementos) e vai vendo "à mão" como é que se procede, segue o código linha a linha.

here since 2009

Link to comment
Share on other sites

Sim vou fazer isso. Desculpa qualquer confusão criada. Estava aqui a inserir elementos para uma lista mas só conseguia fazer recursivamente. Estava a tentar fazer dessa forma mas não estava a perceber. Vou analisar melhor.

EDIT: só uma coisa... Quando vou procurar o nó que é nulo e inserir lá o valor, como retorno os valores anteriores juntamente com o que acabei de alocar? (quero inserir no fim da lista)

Link to comment
Share on other sites

Eu acho esse addList pouco intuitivo: pede a head mas tens na realidade que lhe dar a cauda da lista (tail). Devia procurar por ele o último elemento, não obrigar o utilizador a fazê-lo.

❝The idea that I can be presented with a problem, set out to logically solve it with the tools at hand, and wind up with a program that could not be legally used because someone else followed the same logical steps some years ago and filed for a patent on it is horrifying.❞- John Carmack on software patents

A list  of command line apps

Link to comment
Share on other sites

Imagina que tenho um método que recebe uma lista, e que deve acrescentar um inteiro "random" à lista (que pode já ter mais elementos.

A assinatura do método é:

function addrandom(List *mylist);

Para poderes fazer isto com essa função, terás que fazer:

function addrandom(List *mylist) {
//encontrar o último elemento:
List *elem = mylist;
while(elem->next != NULL)
    elem = elem->next;

addList(elem, rand() % 10+1);

Enquanto eu devia poder fazer só:

function addrandom(List *mylist) {
   addList(mylist, rand() % 10+1);
} 

❝The idea that I can be presented with a problem, set out to logically solve it with the tools at hand, and wind up with a program that could not be legally used because someone else followed the same logical steps some years ago and filed for a patent on it is horrifying.❞- John Carmack on software patents

A list  of command line apps

Link to comment
Share on other sites

Já reparaste que eu tenho sempre controlo de uma variável que contém o final da lista? Ou seja, é estupido enviar para essa função a cabeça da lista quando tenho o final da mesma.

Já para não falar na perda de performance se fizeres da maneira que falas. Vou-te dar um exemplo concreto, tu para fazer um BFS precisas de uma queue, se de cada vez que fosses a adicionar à queue um elemento tivesses de a percorrer toda o teu BFS perdia grande parte da sua eficiência.

Só mesmo para completar, se reparares na minha função eu estou sempre a retornar o final da lista, ou seja, o utilizador só tem mesmo de chamar a função de adição e depois chamar essa addrandom com o retorno.

Ficaria assim:

List *addrandom(List *tail) {
  return addList(tail,rand() % 10+1);
}

int main(void) {
  List *tail = NULL;
  tail = addList(tail,10);
  tail = addrandom(tail);
}

E esse teu exemplo é redundante, para adicionar um valor aleatório bastava fazer:

tail = addList(tail,rand() % 10+1);

here since 2009

Link to comment
Share on other sites

Mas então tens que guardar sempre a head (para poderes aceder ao elementos todos) e a tail (para poderes adicionar).

Mais valia fazeres uma nova estrutura:

typedef struct ListNode {
  int key;
  struct ListNode *next;
}ListNode;

typedef struct List {
  ListNode *head;
  ListNode *tail;
}List;

Assim, podes fazer:

List *mylist = NULL;

addList(mylist, 10);

addrandom(mylist);

etc. sem perder performance nem andar com várias variáveis.

❝The idea that I can be presented with a problem, set out to logically solve it with the tools at hand, and wind up with a program that could not be legally used because someone else followed the same logical steps some years ago and filed for a patent on it is horrifying.❞- John Carmack on software patents

A list  of command line apps

Link to comment
Share on other sites

Realmente o nome não é nada intuitivo. Também fiquei perdido com os primeiros posts. O nome da função deveria ser algo tipo ReplaceAfter, porque o que faz é inserir um nó após o nó passado como 1º argumento, existindo ou não um nesse sítio, o que também é perigoso porque pode originar uma leak. E o 1º parâmetro nunca deveria ser chamado head, senão, ao ver-se a lista de parâmetros, a ideia que fica é que deve ser passado o 1º elemento da lista.

Desaparecido.

Link to comment
Share on other sites

Acho que a melhor maneira é sem dúvida ter sempre um ponteiro para o inicio e para o fim da lista, óbvio que podemos ter uma estrutura com esses dois ponteiros.

É óbvio também que em vez de passar por valor o final da lista podia passar por referência e assim o utilizador não tem de se preocupar em estar sempre a receber o retorno da função.

Para finalizar, já expliquei o porquê de ter dado aquele nome ao ponteiro, mas se isso causa assim tanta confusão eu posso mudar e voltar a postar o código, sem problema.

here since 2009

Link to comment
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
 Share

×
×
  • 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.