linked list problem

if13121 · #1 09-Nov-2004, 23:10

This is my list declaration

CPP / C++ / C Code:

#define Nil NULL
#define info(P) (P)->info
#define next(P) (P)->next
#define First(L)((L).First)


typedef int infotype;
typedef struct tElmtlist *address;
typedef struct tElmtlist
{
	infotype info;
	address next;
}Elmtlist;


typedef struct
{
	address First;
}List;

i have this procedure:

CPP / C++ / C Code:

void DeleteLast(List * L,infotype * X)
/*is : list not empty
 fs : last Element  list deleted. X save its value*/
{
	address Last,Prev;
	Last = First(*L);
	Prev = Nil;
	First(*L)=Last;
	while (next(Last) != Nil)
	{	Prev = Last;
		Last = next(Last);
	}
	*X = info(Last);
	next(Prev) = Nil;
}

why if i changed the procedure become:

CPP / C++ / C Code:

void DeleteLast(List * L,infotype * X)
{
	address Last;
	Last = First(*L);
	First(*L)=Last;
	while (next(Last) != Nil)
	{	Last = next(Last);
	}
	*X = info(Last);
	Last = Nil;
}

the procedure not work when i print all list element i still have last element

if13121 · #2 09-Nov-2004, 23:50

another question:
P is a pointer
is there any diffrences between
free(P); with P = NULL;

dsmith · #3 10-Nov-2004, 07:08

Hi if13121. I will take a look at your question and see if I can come up with something. However, it is very important that you start using the code tags to post your code. It makes it very difficult to read your code without them and therefore you may not be getting anyone responding.

It is very simple to do. Simply enclose your c code between [c] and [/c] tags. If that doesn't make sense, hit the reply button on your first post and you will see how I editted your post with these markup codes.

This will be a big help to me, but more importantly to you as more people will take the time to read your posts (help me to help you...

)

Thanks!

dsmith · #4 10-Nov-2004, 07:27

Quote:

Originally Posted by if13121

another question:
P is a pointer
is there any diffrences between
free(P); with P = NULL;

Yes, most definitely.

with free(P) what you are doing is releasing the memory that had been allocated for P back into the memory pool for future use.

By setting P to NULL, you do not free this memory. The only time that you should do this, is when you haven't allocated memory for P and you want it marked to know that. This is actually a good idea as a call to free(P) will fail if the memory is not allocated unless, P points to NULL.

nkhambal · #5 10-Nov-2004, 11:56

Hi,

Pls show us how you are calling "DeleteLast()" in parent function and how you are passing the values and how those values are declared. This will give us more insite on problem. Also, if you can post the sample output of your code when you run it for deleting, that would be great.

Thanks,

nkhambal · #6 10-Nov-2004, 12:27

Hi,

I developed the parent function using my own idea. It worked for me.Following is the code for my parent function main(). I modified the return type of your DeleteLast() function to return true or false based on sucess or failure. This is not a final solution. This is just to give some idea about it.

CPP / C++ / C Code:

typedef enum {
	FALSE,
	TRUE
} boolean;

boolean DeleteLast(List * L,infotype * X)
{
  address Last;
  Last = First(*L);
  //First(*L)=Last;
  if (Last==Nil)
  {
	  return FALSE;
  }
  while (next(Last) != Nil)
  {  Last = next(Last);
  }
  *X = info(Last);
  printf("\nX:= %d\n",*X);
  Last = Nil;
  return TRUE;
}

int main()
{
	boolean result;
	List list;
	infotype x;

	list.First->info=10;
	list.First->next=NULL;

	if (DeleteLast(&list,&x)==TRUE)
	{
		printf("\nSucess\n");
	} else {
		printf("\nFailure\n");
	}

	return 0;
}

It could be the problem with the way your are passing the values in parent function. Just a guess.

Following is my output

Quote:

X:= 10

Sucess

Thanks,

P.S. Use lots of printf() in your code for debugging purpose. Its a good tool to understand the flow of your program and pin point the location in your code where its not working.

if13121 · #7 10-Nov-2004, 21:01

Quote:

Originally Posted by dsmith

Yes, most definitely.

with free(P) what you are doing is releasing the memory that had been allocated for P back into the memory pool for future use.

By setting P to NULL, you do not free this memory. The only time that you should do this, is when you haven't allocated memory for P and you want it marked to know that. This is actually a good idea as a call to free(P) will fail if the memory is not allocated unless, P points to NULL.

if I assign null to a pointer, does it mean that every other pointer that points to the same location as that pointer pointed to will become null?

if13121 · #8 10-Nov-2004, 21:40

Quote:

Originally Posted by nkhambal

Hi,

Pls show us how you are calling "DeleteLast()" in parent function and how you are passing the values and how those values are declared. This will give us more insite on problem. Also, if you can post the sample output of your code when you run it for deleting, that would be great.

Thanks,

this is the program:

CPP / C++ / C Code:

/*File : flist.h*/

#include <stdlib.h>
#define Nil NULL
#define info(P) (P)->info
#define next(P) (P)->next
#define First(L)((L).First)

typedef int infotype;
typedef struct tElmtlist *address;
typedef struct tElmtlist
{
	infotype info;
	address next;
}Elmtlist;


typedef struct
{
	address First;
}List;

/*prototype*/

void CreateList(List * L);
address Alokasi(infotype X);
void InsFirst(List * L,address P);
void InsVFirst(List * L,infotype X);
void DeleteLast(List * L,  infotype * X);
int NbElmtList(List L);
void PrintList(List L);
void ReadList(List *L);




/*File : flist.c*/
/*body prototype */
#include "flist.h"

void CreateList(List * L)
/*create empty list */
{First(*L) = Nil;}
address Alokasi(infotype X)

{	address P;
	P = (address)malloc(sizeof (Elmtlist));
	/*address kan sudah pointer*/
	if(P != Nil)/*ALokasi berhasil*/
	{
		info(P) = X;
		next(P) = Nil;
	}
		return P;
}
void InsFirst(List * L,address P)
{
	next(P) = First(*L);
	First(*L)= P;
}

void InsVFirst(List * L,infotype X)
{
	address P;
	P = Alokasi(X);
	if (P != Nil)
	{InsFirst(L,P);}
}

void DeleteLast(List * L,infotype * X)
/*is : list not empty*/
/*fs : last Element  list deleted. X save its value*/
{
	address Last,Prev;
	Last = First(*L);
	Prev = Nil;
	First(*L)=Last;
	while (next(Last) != Nil)
	{	Prev = Last;
		Last = next(Last);
	}
	*X = info(Last);
	next(Prev) = Nil;
}


/*===========read and write operation===============*/
int NbElmtList(List L)
/*return  nb of  elemen list*/
{	address P;
	int Nb = 1;
	P  = First(L);
	while(P != Nil){
	P = next(P);
	Nb++;
	}
	return Nb;
}

void ReadList(List * L)
/*insert element list from user input*/
{
	infotype X;	
	printf("input  int to list (using insert first) ended it with  999:\n");
	while(X != 999)
	{	printf("input :");
		scanf("%d",&X);
		if (X != 999)
		{InsVFirst(L,X);}
		else
		{printf("finish input element list\n");}
	}
}

void PrintList(List L)
/*display all element list */
{	address P;
	int i,NbList;
	P = (First(L));
	NbList  = NbElmtList(L);
	for (i = 1;i < NbList;i++)
	{			
		printf("%d\n",info(P));
		if (P == Nil)printf("finish print list\n");
		else P = next(P);
	}
} 

/*File : mlist.c*/
#include "flist.h"
int main()
{	
	List L;
	infotype Z;
	CreateList(&L);
	address P,Q,R;
	ReadList(&L);
	PrintList(L);
	printf("delete last\n");
	DeleteLast(&L,&Z);
	printf("elemen deleted = %d\n",Z);
	PrintList(L);
	return 0;
}

that program work
when i changed function DeleteLast above
become:

CPP / C++ / C Code:

void DeleteLast(List * L,infotype * X)
{
address Last;
Last = First(*L);
First(*L)=Last;
while (next(Last) != Nil)
{Last = next(Last);
}
*X = info(Last);
Last = Nil;
}

it is not work Why???

dsmith · #9 11-Nov-2004, 06:35

Quote:

Originally Posted by if13121

if I assign null to a pointer, does it mean that every other pointer that points to the same location as that pointer pointed to will become null?

No. When you sent a pointer to NULL, you are just pointing it to nothing. The memory that you have defined at that position stays allocated with the same value, etc.

Here is a little program that may explain it better.

CPP / C++ / C Code:

int main(){

	int*	p;		//Undefined where it points to
	int*	q;		//Undefined where it points to.

	p = (int*) malloc(sizeof(int));		//p now points to a new memory address.
	*p = 100;							//The value at that address has been set to 100
	printf("*p = %d (p = %ld)\n",*p,p);		//Check p
	q = p;									//Set q to point to p
	printf("*q = %d (q = %ld)\n",*q,q);		//Check q
	p = 0;									//Set p to null

	printf("*p is undefined (segfault if you try!) (p = %ld)\n",p);		//Check p
	printf("*q = %d (q = %ld)\n",*q,q);		//Check q

	free(q);

	return 0;
}

HTH.

nkhambal · #10 11-Nov-2004, 12:27

It still prints the deleted value because you are not updating tail of list when you delete the last item in the list. It still keeps pointing to the allocated memory. The previous node to the last is still pointing to the last node. You are only NULL terminating the last node. You still need to update previous node to the last to point to NULL so that your print function stops there (after hitting NULL).

Also your earlier DeleteLast() function could cause a memory leak becuase in DeleteLast() you are only printing out the last value not freeing it. Memory is not released by the program as it is supposed to be, after deleting the element. But since you are not actually deleting and freeing the memory , you are safe cause that part of memory is still owned by your program. But its a waste since you are no longer going to refer to it. Otherwise you could have seen the crash.

I have updated your DeleteLast() function to incorporate the above required changes.

CPP / C++ / C Code:

void DeleteLast(List * L,infotype * X)
{
address Last,Prev;
Last = First(*L);
First(*L)=Last;
while (next(Last) != Nil)
{
	Prev=Last;
	Last = next(Last);
}
*X = info(Last);
next(Prev)=Nil;
free(Last);
Last=Prev;
}

Following is the output I got when I compiled and ran the program with above function changes.

Quote:

[root@linux snoopy]# ./iflist1
input int to list (using insert first) ended it with 999:
input :10
input :20
input :30
input :40
input :50
input :999
finish input element list
50
40
30
20
10
delete last
elemen deleted = 10
50
40
30
20
[root@linux snoopy]#

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Problem with the function creating updating a linked list	nkhambal	C Programming Language	3	28-Oct-2004 20:45
bus error in linked list	picknicker187	C Programming Language	2	08-Oct-2004 10:44
Insert problem in Linked list	Kay Chan	C Programming Language	1	03-Sep-2004 17:06
Insert problem in linked list with two function code	Kay Chan	C++ Forum	1	03-Sep-2004 09:52
help on linked lists any1?????	nick4	C Programming Language	1	17-May-2004 09:32