[Resolvido] Inserir em uma Lista Simplesmente Encadeada

[Débora de Oliveira 0]

Pessoal, meu programa está dando erro, o exercício é o seguinte:

 

1) Implemente a função Lista *insere(Lista *l, int valor, int pos) que insere o elemento valor

na posição pos da lista simplesmente encadeada. Para isso, um novo nó deve ser alocado e ligado aos demais. O

valor de pos é um número, que ser for 2, por exemplo, indica que o novo nó alocado será o segundo nó da lista.

 

O erro do meu programa é que quando ele insere na posição que pede os elementos anteriores 'somem' por exemplo

 

Coloquei valores na lista com um for só para testar, minha lista tem os seguintes valores

 

6 5 4 3 2 1 0

 

Digito a posição e o valor que quero inserir:

4 8

 

Aparece como resposta:

 

8 2 1 0

 

Ele insere na posição 4 mas perde os elemntos anteriores, não consigo saber o motivo, e o que fiz de errado, se puderem m ajudar eu agradeço!!

 

Obrigada.

 

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

struct lista{
	   int info;
	   struct lista*prox;
};
typedef lista Lista;

//função cria
Lista* cria(void){
	   return NULL;
}
//função insere
Lista* insere(Lista* l,int i){
	   Lista* novo=(Lista*)malloc(sizeof(Lista));
	   novo->info=i;
	   novo->prox=l;
	   return novo;
}



Lista* insere_pos(Lista *l, int valor, int pos){
	  int cont=1; //é a posição do primeiro elemento da lista encadeada
	  Lista*p=l;
	  Lista* novo=(Lista*)malloc(sizeof(Lista));
	  while (cont!=pos){	 //testa se é igual a posição que ele quer inserir
			p=p->prox;
			cont++;
	  }
	  novo->info=valor;
	  novo->prox=p->prox;
	  return novo;
}

void imprime(Lista* l){
	   while (l!=NULL){
			 printf("%d",l->info);
			 l=l->prox;
	   }
}

			 
int main(){
	int i,pos,valor;
	Lista*l;
	l=cria();
	for (i=0;i<7;i++)
		l=insere(l,i);
	imprime(l);
	
	printf("\nDigite a posição que você quer inserir e o seu valor\n");
	scanf("%d %d",&pos,&valor);
	l=insere_pos(l,valor,pos);
	imprime(l);
}

[_Isis_ 202]

você tem que usar REALLOC ao inves de malloc p/ inserir.

[Débora de Oliveira 0]

Tentei e deu erro...

eu mudaria o malloc para realloc assim? e apenas nessa função insere_pos certo?

 

Lista* insere_pos(Lista *l, int valor, int pos){
	  int cont=1; //é a posição do primeiro elemento da lista encadeada
	  Lista*p=l;
	  Lista* novo=(Lista*)realloc(*novo,sizeof(Lista));  // mudado para realloc
	  while (cont!=pos){//testa se é igual a posição que ele quer inserir
			p=p->prox;
			cont++;
	  }
	  novo->info=valor;
	  novo->prox=p->prox;
	  return novo;
}

 

O erro é o seguinte:

In function `Lista* insere_pos(Lista*, int, int)':

convert `lista' to `void*' for argument `1' to `void* realloc(void*, size_t)'

 

Acho que é pq na função que coloco o realloc precisa ser void.. só que o professor disse que tem q usar os parametros q ele deu

 

Lista* insere_pos(Lista *l, int valor, int pos)

 

eu não posso colocar void nessa função... está certa a minha função realloc?????

 

 

Obrigada pela ajuda.

[_Isis_ 202]

O que o "insere" faz? Ele coloca no inicio da lista ou no final?

 

void * é ponteiro genérico.Dá erro porque você está tentando realocar uma variável no lugar de colocar um ponteiro p/ variável.

[José Enésio 4]

Já vi:

 

Faz assim: continue com o código que você tem no seu primeiro post.

 

Agora só falta mudar uma coisa:

 

Lista* insere_pos(Lista *l, int valor, int pos){

int cont=1; //é a posição do primeiro elemento da lista encadeada

Lista*p=l;

Lista* novo=(Lista*)malloc(sizeof(Lista));

while (cont!=pos){ //testa se é igual a posição que ele quer inserir

p=p->prox;

cont++;

}

novo->info=valor;

novo->prox=p->prox;

p->prox = novo;

return l;

}

O que faltava:

Tava retornando o novo elemento, aí não ia mostrar desde o início, tem que retornar o primeiro ou a "lista que é passada por parâmetro". Mude na função insere normal também, troque return novo por return l.

Também tava faltando definir o elemento "anterior" pra apontar pro novo elemento. Aí sim, gateou uma gambiarra ali no meio e juntou as coisas.

 

PS. Acho desnecessário retornar a lista na função. A lista sendo passada como ponteiro pra função já é o suficiente pras mudanças ocorrerem na lista na função e ser afetada no main. Aí ao invés de fazer l = insere_pos(l, valor, pos), pode só chamar a função normalemente insere_pos(l, valor, pos).

 

Falou maninho!

[_Isis_ 202]

Dá uma olha em outro post: o cara tava tendo problemas com isso. Se não retornar, o realloc muda o endereço e você perde ele.

[José Enésio 4]

Dá uma olha em outro post: o cara tava tendo problemas com isso. Se não retornar, o realloc muda o endereço e você perde ele.

O código que eu usei é o do primeiro post que não usa realloc. Testei e funcionou direitinho aqui.

[_Isis_ 202]

Não usa realloc e também não usa free. Fazendo assim o código fica cheio de leaks quando você coloca a inserção num loop.

 

--4558-- REDIR: 0x40a58c0 (free) redirected to 0x4023ac0 (free)

==4558==

==4558== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 3 from 1)

--4558--

--4558-- supp: 3 dl-hack3-1

==4558== malloc/free: in use at exit: 120 bytes in 15 blocks.

==4558== malloc/free: 15 allocs, 0 frees, 120 bytes allocated.

==4558==

==4558== searching for pointers to 15 not-freed blocks.

==4558== checked 53,516 bytes.

==4558==

==4558== 48 bytes in 6 blocks are indirectly lost in loss record 1 of 3

==4558== at 0x4024D5E: malloc (in /usr/lib/valgrind/x86-linux/vgpreload_memcheck.so)

==4558== by 0x804848F: insere (insere_lista_bug.c:19)

==4558== by 0x8048571: main (insere_lista_bug.c:55)

==4558==

==4558==

==4558== 120 (8 direct, 112 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 3

==4558== at 0x4024D5E: malloc (in /usr/lib/valgrind/x86-linux/vgpreload_memcheck.so)

==4558== by 0x804848F: insere (insere_lista_bug.c:19)

==4558== by 0x8048571: main (insere_lista_bug.c:55)

==4558==

==4558==

==4558== 64 bytes in 8 blocks are indirectly lost in loss record 3 of 3

==4558== at 0x4024D5E: malloc (in /usr/lib/valgrind/x86-linux/vgpreload_memcheck.so)

==4558== by 0x80484C7: insere_pos (insere_lista_bug.c:30)

==4558== by 0x80485CF: main (insere_lista_bug.c:62)

==4558==

==4558== LEAK SUMMARY:

==4558== definitely lost: 8 bytes in 1 blocks.

==4558== indirectly lost: 112 bytes in 14 blocks.

==4558== possibly lost: 0 bytes in 0 blocks.

==4558== still reachable: 0 bytes in 0 blocks.

==4558== suppressed: 0 bytes in 0 blocks.

 

"Por cima", existem dois jeitos de se fazer isso: não utilizando a notação de array e abusando de somas e sizeof ou mantendo uma variável inteira Tamanho p/ percorrer a memória como um array (até onde eu sei,isso dispensa o campo próximo na struct e transforma a lista ligada em uma sequencia de ponteiros para inteiros na memoria).

 

#include <stdio.h>
#include <stdlib.h>
#define CHECKNULL(PTR) ( if (PTR == NULL) return NULL )
int tamanho;

int* cria(void){
tamanho = 0;
return (int*) malloc(0);
}


int* insere(int* l,int i){
int* novo=(int*)realloc(l,sizeof(int)*(tamanho+1));
   CHECKNULL(novo);
novo[tamanho]=i;
tamanho++;
return novo;
}

int* insere_pos(int *l, int valor, int pos){
if (pos <= tamanho) {
	int* novo=(int*)realloc(l,sizeof(int)*(tamanho+1));
		   CHECKNULL(novo);
	tamanho++;
	for(int inicio = tamanho;inicio>pos;inicio--)
		novo[inicio] = novo[inicio-1];
	novo[pos] = valor;
	return novo;
}
return l;
}

void imprime(int* l) {
for (int indice=0;indice < tamanho;indice++)
	printf("%d  ",l[indice]);
puts("");
}

 

Se é p/ mexer com ponteiros mesmo,o negócio ficaria mais ou menos assim:

 

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

struct lista{
int info;
struct lista *prox;
};

typedef struct lista Lista;
int tamanho;

Lista* cria(void){
tamanho = 0;
return (Lista*) malloc(0);
}

void imprime(Lista* l) {
Lista * PTR = l;
while(PTR != NULL) {
	printf("%d ",PTR->info);
	PTR = PTR->prox;
}
puts("");
}


Lista* insere(Lista* l,int i){
Lista* novo=(Lista*)realloc(l,sizeof(Lista)*(tamanho+1));
if (novo == NULL) return NULL;

(novo+tamanho*sizeof(Lista))->info = i;
if (tamanho >=1)
	(novo+(tamanho-1)*sizeof(Lista))->prox = novo+tamanho*sizeof(Lista);

(novo+tamanho*sizeof(Lista))->prox = NULL;
tamanho++;
return novo;
}


Lista* insere_pos(Lista *l, int valor, int pos){
if (pos >= 0) {
	Lista* novo=(Lista*)realloc(l,sizeof(Lista)*(tamanho+1));
	if (novo == NULL) return NULL;

	(novo+tamanho*sizeof(Lista))->prox = NULL;
	(novo+(tamanho-1)*sizeof(Lista))->prox = novo+tamanho*sizeof(Lista);

	for(int inicio = tamanho;inicio>pos;inicio--)
		(novo+inicio*sizeof(Lista))->info = (novo+(inicio-1)*sizeof(Lista))->info;
	(novo+pos*sizeof(Lista))->info = valor;

	for(int inicio = tamanho-1;inicio>=0;inicio--)
		(novo+inicio*sizeof(Lista))->prox = novo+(inicio+1)*sizeof(Lista);

	tamanho++;
	return novo;
}
return l;
}

[José Enésio 4]

Desisto; não sei onde você acha esses programas free pra detectar memory leaks...

[_Isis_ 202]

qq tem?

[José Enésio 4]

Pesquisei no google, ou é pra linux, ou é trial... Não acho um pra mim aqui...

[_Isis_ 202]

Valgrind.

Tem umas bibliotecas que dá p/ usar : dmalloc, njamd, mpatrol e a própria glibc.

O gcc tem uns patches que fazem isso mas não sei se já foram incorporados.

[José Enésio 4]

Esse aí parece que não funfa no windows aqui...

O ruim é que os que funcionam, só tem trial...

Bom, acho que o certo seria deixar esse assunto de lado, depois pergunto pro quizatenom, valeu!

[Débora de Oliveira 0]

Pessoal descupe a demora, é q tive mtas provas e n deu tempo d entrar na net.. mas eu fiz o que o José Enésio disse e deu certo

 

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

 

Lista* insere_pos(Lista *l, int valor, int pos){

int cont=1; //é a posição do primeiro elemento da lista encadeada

Lista*p=l;

Lista* novo=(Lista*)malloc(sizeof(Lista));

while (cont!=pos){ //testa se é igual a posição que ele quer inserir

p=p->prox;

cont++;

}

novo->info=valor;

novo->prox=p->prox;

p->prox = novo;

return l;

}