Lista Encadeada

Lista Encadeada

by Marlon Ribas Vismari -
Number of replies: 8
Olá professor / monitor.

Fiz uma lista encadeada, mas ela só está exibindo 1 elemento (último da lista). Vocês podem analisar e ver se tem algo errado?

Considere uma lista encadeada com cabeça.

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

struct celula{
int conteudo;
struct celula *prox;
};

typedef struct celula lista;

/* Função que insere uma célula (no final) em uma lista */
void Insere (int x, lista *p)
{
lista *nova;
nova = malloc (sizeof(lista));
nova->conteudo = x;
nova->prox = NULL;
p->prox = nova;
}


/* Função imprime lista com cabeça */
void ShowList(lista *lst){
lista *p;
int i;
for(p = lst->prox, i = 1; p != NULL; p = p->prox, i++){ printf("Elemento (%d): %d\n", i, p->conteudo); }
}

int main()
{

lista *list;

list = malloc(sizeof(lista));
list->prox = NULL;

Insere(1, list);
Insere(2, list);
Insere(3, list);
ShowList(list);

return(0);
}



Obrigado novamente!

In reply to Marlon Ribas Vismari

Re: Lista Encadeada

by Andre Manoel -
Marlon, acredito que a função insere está inserindo sempre na primeira posição da lista, por isso a lista tem sempre 1 elemento.

Acho que antes de fazer p->prox = nova; você teria de avançar p até o fim da lista com while (p->prox != NULL) p = p->prox;

Não tenho certeza, mas acho que é isso! Por favor alguém me corrija se falei besteira...
In reply to Andre Manoel

Re: Lista Encadeada

by Rebeca Bayeh -
Concordo! Só uma observação (me corrijam se eu estiver errada também!)... Usando o while do Antonio, a cada etapa p = p->prox então quem tem que ser diferente de NULL é o p, não o p->prox .
In reply to Marlon Ribas Vismari

Re: Lista Encadeada

by Natan Costa Lima -
Inserir no comeco da lista nao eh um problema (é o certo geralmente), o único sintoma disso, seria a lista ficar com os elementos ao contrário.

/* Função que insere uma célula (no final) em uma lista */
void Insere (int x, lista *p)
{
lista *nova;
nova = malloc (sizeof(lista));
nova->conteudo = x;
nova->prox = NULL;// AQUI está o erro
p->prox = nova;
}

deveria ser algo como:

void Insere (int x, lista *p)
{
lista *nova;
nova = malloc (sizeof(lista));
nova->conteudo = x;
nova->prox = p->prox;
p->prox = nova;
}

In reply to Natan Costa Lima

Re: Lista Encadeada

by Marlon Ribas Vismari -
Natan,
esse Insere eu vi no livro do Paulo Feofiloff.

Antonio, eu acho que você deve estar certo. Vou testar aqui e posto pro resultado smile

Valeu pessoal!
In reply to Marlon Ribas Vismari

Re: Lista Encadeada

by Natan Costa Lima -
Vim olhar no site do Professor Feofiloff e achei esta funcao:
// Esta função insere uma nova celula em uma
// lista encadeada. A nova celula tem conteudo
// x e é inserida entre a celula apontada por
// p e a seguinte. Supõe-se que p != NULL.

void insere (int x, celula *p)
{
 celula *nova;
 nova = mallocX (sizeof (celula));
 nova->conteudo = x;
 nova->prox = p->prox;
 p->prox = nova;
}

Que é igual a minha com a correcao que eu fiz.
Acho q vc deve ter visto errado no livro. =)

fonte:
http://www.ime.usp.br/~pf/algoritmos/aulas/lista.html

In reply to Natan Costa Lima

Re: Lista Encadeada

by Natan Costa Lima -
Percebi que vc quer inserir no final.

Se você precisa inserir sempre no final, a melhor idéia é guardar um ponteiro
para o último elemento da lista, e não fazer o laco que o Antonio sugeriu.
sempre que inserir alguém vc atualiza este ponteiro.


In reply to Natan Costa Lima

Re: Lista Encadeada

by Marlon Ribas Vismari -
Natan, obrigado pela resposta novamente.

Como eu poderia fazer esse ponteiro? Poderia me dar um exemplo?

A ideia do Antônio funcionou (Obrigado). O problema é com listas muito grandes. Percorrer tudo até chegar o final não seria uma boa ideia.

Valeu galera!
In reply to Marlon Ribas Vismari

Re: Lista Encadeada

by Natan Costa Lima -
O problema é com listas muito grandes.
Esse é exatamente o problema.


O jeito que eu disse é simples. No caso aí de cima sua lista tinha uma cabeca.

Além da cabeca, ela passará a ter uma cauda(um ponteiro para o último nó).

ai no insere vo fará algo como:
*(cauda)->prox = novo;
*cauda = novo; //atualizando aqui seu ponteiro


pense um pouco no resto do código, é um bom exercício.