[Resolvido] Lista simplesmente Encadeada

[PH_Nikit 0]

pow galera .... eu to com um problema.... eu não to conseguindo fazer a inserção de valores sempre ao fim da lista encadeada.

eu fiz um código ... só q não tá batendo com o q deveria fazer. se alguém puder ajudar eu agradeço .... vlw

 

 

//Código:

 

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

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

typedef struct cel celula;

celula *inicio,*novo;

void inserefim(int valor);
void crialista(void);
void imprime(void);

main()
{
	int valor,i;

	crialista();

	for (i=0;i<5;i++);
	{
		scanf("%d",&valor);
		inserefim(valor);
	}

	imprime();

	system ("pause");
	return 0;
}

void crialista(void)
{
	inicio=NULL;
}

void inserefim(int valor)
{
	celula *p;
	p=inicio;

	if(p!=NULL)
	{
		novo=(celula *)malloc(sizeof(celula));
		novo->conteudo=valor;
		novo->prox=p->prox;
		p->prox=novo;
	}
}


void imprime(void)
{
	celula *p;
	for(p=inicio;p!=NULL;p=p->prox)
	{
			printf("OS VALORES SAO: %d\n",p->conteudo);
	}
}

[Kandrade 7]

Voce terá que percorrer a lista até encontrar o elemento que aponte para NULL.

Esse é o último elemento, então basta fazer com ele aponte para o elemento a ser inserido.

 

void inserefim(int valor){
   celula *p;
   p = inicio;

   novo=(celula *)malloc(sizeof(celula));
   novo->conteudo = valor;
   novo->prox = NULL;

   if(p == NULL){ // primeiro elemento
	   inicio = novo;
   }
   
   else{ // qualquer outro

   }
}

Dentro do else faça o que lhe pedi.

 

http://forum.imasters.com.br/public/style_emoticons/default/thumbsup.gif

[PH_Nikit 0]

Consegui.... vlw Kandrade!!!!!

[Kandrade 7]

Opa, foi nada!

 

http://forum.imasters.com.br/public/style_emoticons/default/thumbsup.gif

 

 

Consegui.... vlw Kandrade!!!!!

[gRoOvE 0]

Voce terá que percorrer a lista até encontrar o elemento que aponte para NULL.

Esse é o último elemento, então basta fazer com ele aponte para o elemento a ser inserido.

 

void inserefim(int valor){
	celula *p;
	p = inicio;
 
	novo=(celula *)malloc(sizeof(celula));
	novo->conteudo = valor;
	novo->prox = NULL;
 
	if(p == NULL){ // primeiro elemento
		inicio = novo;
	}
	
	else{ // qualquer outro
 
	}
 }

Dentro do else faça o que lhe pedi.

 

http://forum.imasters.com.br/public/style_emoticons/default/thumbsup.gif

Está se referindo a qual lista? O elemento que vai apontar pra NULL não vai ser sempre esse "novo->prox = NULL;" ?

[gRoOvE 0]

Quem vai se movimentar ai é só o novo* né?? o inicio* só vai mudar de endereço no primeiro elemento que vai deixar de apontar pra NULL e apontar pro próximo...to com dúvida em como fazer a ligação dos elementos...

[VictorCacciari 42]

Groove,

 

você não está conseguindo ligar os elementos da lista, certo?

não entendi muito bem a sua dúvida.

 

Mas, vamos implementar uma lista encadeada simples, é tranquilo.

estruturas:

typedef struct
{
	int valor;
	struct node *prox;
} node;

para inserir elementos no fim:

void inserir_fim(node* inicio, int item)
{
node *novo = (node*)malloc(sizeof(node));
node *atual;

	atual = inicio;


	novo->valor = item;
	novo->prox = NULL;

	//vamos percorrer a lista toda, até encontrarmos o final dela!
	while (atual->prox != NULL)
	{
		atual = atual->prox;
	}

	//quando encontrarmos o último nó da lista, adiconamos o novo nó.
	atual->prox = novo;
}

ok, ja sabemos adicionar valores na nossa lista...mas ela nem está criada!!!

(essa parte é fácil!)

vamos criar a lista!

 

int main()
{
//vamos então declarar a raiz da lista!
node* root = (node*)malloc(sizeof(node));

	//note que o root não terá valor nenhum, será apenas um ponteiro para o próximo elemento
	root->prox = NULL;
	root->valor = 0;


	//agora ja está tudo feito, temos a lista criada!

	//para adicionar elementos, simplesmente faça:
	inserir_fim(root, 13);
}

para ver a lista:

void printLista(node* inicio)
{
node* atual;

	atual = inicio->prox;

	while (atual != NULL)
	{
		printf("%d armazenado em: %x\n", atual->valor, atual);
		atual = atual->prox;
	}
}

 

era essa a dúvida?

[gRoOvE 0]

Ótimo tuto Victor, vlw brother! Cara, existe mesmo a necessidade de a gente alocar memória pro root ali? Não tem como só apontar ele pra NULL e ir ligando a lista?? Porque na verdade, só vai ser inserido um elemento por vez na lista, logo precisamos alocar memória pra um elemento.

[gRoOvE 0]

Essa alocação de memória pro root tá complicando Victor, to tentando implementar algo pra buscar na lista...Sempre o último elemento não vai ser verificado pq o ponteiro vai apontar para null na vez dele "/

 

void buscarLista(int valor)
{
	node* aux = lista;
	while(aux->proximo != NULL) ///////////while(aux != NULL)
	{
		if(aux->conteudo == valor)
		{
			printf("VALOR ENCONTADO NA LISTA!");
			break;
		}
		aux = aux->proximo;
	}
}

Resolvi, repare a linha comentada...só debugando pra entender mesmo ^^

[VictorCacciari 42]

Se você trocar a linha:

while(aux->proximo != NULL)

por:

 

while(aux != NULL)

ele buscará em todos os elementos.

 

 

O que acontece é que, ao adicionar um elemento ao fim, como eu fiz no post anterior, nós SÓ precisamos encontrar o ultimo elemento, que é precisamente aquele onde "prox" aponta para NULL.

 

Já no caso da busca, o último elemento é importante e o seu valor também é importante, portanto inclua-o na busca!

 

--------------------------

 

Alocar a memória para a raiz é extremamente inportante!

um ponteiro, na maioria das vezes é um int.

 

quando declaramos:

 

node* teste;

 

estamos declarando um valor inteiro, que é um endereço da memória.

 

se não alocarmos a memória nesse endereço, não se pode fazer:

teste->prox, ou teste->valor

 

Afinal, eles ainda não existem!

[gRoOvE 0]

Sim, mas não concorda comigo que nós precisamos alocar memória apenas para um elemento de cada vez? Da pra usar o root apenas pra começar a lista e depois deixar tudo com a função(alocar a memória para os novos elementos e fazer a ligação da lista).

[VictorCacciari 42]

Mas dessa forma teriamos que fazer uma pequena alteração na função.

Poderia ser, por exemplo:

 

void adicionar(node* raiz, int valor)
{
node *curr, *new_nd;

	new_nd = (node*)malloc(sizeof(node));
	new_nd->data = valor;
	new_nd->prox = NULL;
	
	curr = raiz;
	if (!curr) //no caso de raiz ser NULL
	{
		curr = new_nd;
		return;
	}

	while (curr->prox != NULL)
	{
		curr = curr->prox;
	}

	curr->prox = new_nd;

}

E dessa forma, as outras operações com a lista ficarão mais complicadas....

você terá que fazer várias funções do tipo: removeRaiz, mudaRaiz, etc...

 

Eu fiz uma implementação quase completa de uma lista duplamente encadeada, usando templates em C++, se você quiser me mande uma MP.

[gRoOvE 0]

Quero aprender bem lista simples...to tentando fazer a rotina pra excluir aqui, mas não consigo achar o ponto. Só me de umas dicas, não poste o código, tipo eu tenho que tratar 3 situações:

-primeiro elemento excluído;

-qualquer elemento do meio excluído;

-último elemento excluído;

 

To com dificuldade na hora de ligar a lista após excluir, como vou fazer pro elemento anterior ao que foi excluído pular ele e apontar pro próximo?

[VictorCacciari 42]

para exclusão, você precisa de uma função que encontre o nó pai daquele que você quer excluir. O nó que vem exatamente antes.

 

Então pode-se fazer algo do tipo:

//aqui nós vamos encontrar o nó que vem antes daquele que será excluido
//se é aqeuele que vem antes, o sucessor dele é o que queremos!
while (aux->prox != delNode && aux != NULL) //delNode é o endereço do nó a ser excluido
{
	 aux = aux->prox;
}

if (aux == NULL)
{
	 printf("Não encontrei...\n");
	 return;
}

//saltamos um nó...
aux->prox = delNode->prox;

//liberamoa a memória do delNode
free(delNode);

note que, a situação de excluir um nó no meio, e excluir o ultimo nó é exatamente a mesma coisa!

O único nó que recebe um tratamento especial é a raiz.

 

No caso, temos que ver como você trata a raiz da lista para pensar em uma forma de exclui-la.

[gRoOvE 0]

Mas cara, como você vai receber o endereço do nó a ser excluído? Consegui fazer aqui, mas foi bem POG...mas ai a função só recebe o número mesmo. Estou seguindo o mesmo padrão que você explicou acima, o root vai ser sempre 0 não vai? Então não tem porque excluir...

[VictorCacciari 42]

Não cara, na função que eu escrevi acima, ela recebe o endereço do nó a ser excluido, que no caso é a variável delNode.

Como você fez?? posta ai pra darmos uma olhada!

 

Para fazer uma função que recebe o valor do nó, era preciso encontrar em que nó está aquele valor, e então jogar o endereço dele no "delNode"

(eu esqueci de escrever as declarações da função acima, desculpa....

mas aqui vai:

void rmNode(node* start, node* delNode)
{
node* aux = start;

//.... o resto da função...
}

)

 

claro, se nós fizermos do root um nó "dummy", isto é, um nó sem a menor importância, que so serve pra indicar o inicio da lista, não tem sentido nenhum excluir...

Mas esse tipo de lista é meio POG...

Eu acho que vale a pena fazer assim até a pessoa pegar a lógica da coisa, depois tentar uma reimplementação de uma lista "real", onde o root é um nó como qualquer outro.

[gRoOvE 0]

Hm, entendi...mas como você vai passar o endereço do nó a ser excluído pra função, ou seja, como você vai saber o endereço do nó? Fiz assim:

 

void excluirLista(Celula* inicio, int valor) //tem q liberar a memoria do item excluido
{
	Celula* anterior = NULL;
	Celula* proximo = NULL;
	Celula* p = inicio;
	
	while(p != NULL)
	{

		if(p->conteudo == valor)
		{
			proximo = p->proximo;
			free(p);
			inicio = anterior;
			inicio->proximo = proximo;
			return;
		}
		anterior = p;
		p = p->proximo;
	}
}

Esse nó "dummy" seria a lista sem cabeça né? O correto numa lista com cabeça é o root ter um valor real e não zero né? Tipo o primeiro valor a ser inserido vai pro root.

[VictorCacciari 42]

Cara, tua função ta certinha!

para excluir o nó pelo endereço de memória seria:

void excluirLista(Celula* inicio, Celula* del) //tem q liberar a memoria do item excluido
{
//estamos usando menos variáveis dessa vez...
	Celula* p = inicio;
	
	while(p != NULL)
	{

		if(p->proximo == del) //alteração
		{
			p->proximo = del->proximo //estamos pulando o "del"
			free(del);
			return;
		}
		p = p->proximo;
	}
}

Cara, essa pergunta da lista com ou sem cabeça eu não sei te responder....

Eu ACHO que é assim, como você falou, mas a chance de eu estar enganado é grande.

[gRoOvE 0]

Victor não consigo visualizar como usar a exclusão através do endereço do nó...tipo, pelo valor você insere os valores, mostra eles e digita o número que você quer excluir e pelo nó? Qual o sentido de passar o nó? Como fica na prática isso?

 

Referente a lista com/sem cabeça, acredito ser isso mesmo...veja http://www.ime.usp.br/~pf/algoritmos/aulas/lista.html

Abraço!

[VictorCacciari 42]

Groove,

 

você passar um endereço de memória para a exclusão evita a exclusão de valores errados.

imagine uma lista:

12 -> 43 -> 54 -> 01 -> 43 -> 98

 

e você quer excluir APENAS o segundo "43".

 

é mais efetivo passar o endereço de memória.

 

Claro que não é o usuário que digitará o endereço de memória, o usuário digitaria: "43"

o seu código iria descobrir que há dois items com o valor "43", então perguntaria qual o usuário quer excluir, pegaria o endereço de memória desse item e passaria para a função que eu postei ali em cima.

 

Claro que você pode fazer uma adaptação, e tratar esse tipo de exclusão (quando há valores repetidos) de forma diferente.

 

A mudança é infima!

em vez de compararmos valores, comparamos endereços de memória.