Programming Forums
User Name Password Register
 

RSS Feed
FORUM INDEX | TODAY'S POSTS | UNANSWERED THREADS | ADVANCED SEARCH

Reply
 
Thread Tools Display Modes
Old Dec 13th, 2007, 6:00 PM   #1
Brent
Highly Adaptive Penguin
 
Brent's Avatar
 
Join Date: May 2005
Location: United States
Posts: 249
Rep Power: 4 Brent is on a distinguished road
Linked List problem - Deleting a node
I have created a simple Linked List. The list stores a username, a IP address associated with the username, and a socket associated with the username. Most of the functions I have created for it work fine except the del() function. I wanted this function to delete a node, but it doesn't delete the node. Could someone show me where I went wrong?


Using OpenWatcom compiler on Windows XP.

Here is the code:

c Syntax (Toggle Plain Text) 
  1. #ifndef LIST_H
  2. #define LIST_H
  3.  
  4. struct user
  5. {
  6. 	char uname[50];
  7. 	char address[15];
  8. 	int socket;
  9. 	user *next;
  10. };
  11.  
  12. user *head_ptr;
  13. user *current_ptr;
  14.  
  15.  
  16. void move_current_to_end()
  17. {
  18. 	current_ptr=head_ptr;
  19.  
  20. 	while(current_ptr->next!=NULL)
  21. 	{
  22. 		current_ptr=current_ptr->next;
  23. 	}
  24. }
  25.  
  26.  
  27. void add_user(char *name, char *addr, int sock)
  28. {
  29. 	user *new_rec_ptr;
  30.  
  31. 	new_rec_ptr=new user;
  32.  
  33. 	strcpy(new_rec_ptr->uname,name);
  34. 	strcpy(new_rec_ptr->address,addr);
  35. 	new_rec_ptr->socket=sock;
  36.  
  37. 	move_current_to_end();
  38. 	current_ptr->next=new_rec_ptr;
  39. }
  40.  
  41.  
  42.  
  43.  
  44. void disp()
  45. {
  46. 	current_ptr=head_ptr;
  47. 	cout<<"--USERS--ONLINE--\n";
  48. 	do
  49. 	{
  50. 		cout<<"-----------------------\n";
  51. 		cout<<"username: "<<current_ptr->uname<<endl;
  52. 		cout<<"IP: "<<current_ptr->address<<endl;
  53. 		cout<<"socket: "<<current_ptr->socket<<endl;
  54. 		cout<<"-----------------------\n";
  55. 	}while(current_ptr!=NULL);
  56. }
  57.  
  58. void del(char *name)
  59. {
  60. 	//user *temp_ptr;
  61.  
  62. 	current_ptr=head_ptr;
  63.  
  64. 	while(current_ptr!=NULL)
  65. 	{
  66. 		if(strcmp(current_ptr->uname,name)==0)
  67. 		{
  68. 			delete [] current_ptr;
  69. 			//current_ptr=temp_ptr;
  70. 			break;
  71.  
  72.  
  73. 		}	
  74. 		else
  75. 		{
  76. 			current_ptr=current_ptr->next;	
  77. 		}
  78. 	}
  79.  
  80. }
  81.  
  82. int search(char *name)
  83. {  
  84.     current_ptr=head_ptr;
  85.  
  86.     while(current_ptr != NULL)
  87.     {
  88. 		if(strcmp(current_ptr->uname,name)==0)
  89. 		{       
  90. 			return -1;		
  91. 		}
  92. 		else
  93. 		{
  94. 			current_ptr=current_ptr->next;
  95. 		}
  96.     }
  97.  
  98. 	return -2;
  99. }
  100.  
  101. #endif
Brent is offline   Reply With Quote
Old Dec 13th, 2007, 8:33 PM   #2
peaceofpi
hi: for(;;) goto hi;
 
peaceofpi's Avatar
 
Join Date: Jun 2006
Posts: 86
Rep Power: 3 peaceofpi is on a distinguished road
Send a message via AIM to peaceofpi Send a message via MSN to peaceofpi
Re: Linked List problem - Deleting a node
Quote:
OpenWatcom compiler
lolwhat

Tip: This is the C forum.
__________________
How do you play Religious Roulette?
Stand around in a circle and blaspheme till someone gets struck by lightning.
peaceofpi is offline   Reply With Quote
Old Dec 13th, 2007, 9:21 PM   #3
Jimbo
Battle Programmer
 
Jimbo's Avatar
 
Join Date: Feb 2006
Location: Bellevue, WA, USA
Posts: 747
Rep Power: 3 Jimbo is on a distinguished road
Re: Linked List problem - Deleting a node
The textbook response to linked list problems is to draw it out on paper, then walk through your code on said paper and see what happens. Your problem is fairly easy if you're looking at a picture. Hint: you're breaking the chain instead of removing a link.

Side note about style: using a global variable for current_ptr is a poor practice. Your code would be better if you declared a local variable in each function where you iterate over the list.
__________________
<insert disclaimer here>
<insert shameless plug for Visual Studio here>
Jimbo is offline   Reply With Quote
Old Dec 13th, 2007, 11:16 PM   #4
WaltP
Programmer
 
Join Date: Oct 2007
Posts: 39
Rep Power: 0 WaltP is on a distinguished road
Re: Linked List problem - Deleting a node
Quote:
Originally Posted by peaceofpi View Post
Quote:
OpenWatcom compiler
lolwhat

Tip: This is the C forum.
Yeah, and he posted C code, didn't he? And he's compiling with the Open Watcom C++/Fortran compiler.
WaltP is offline   Reply With Quote
Old Dec 13th, 2007, 11:41 PM   #5
Sane
Programming Guru
 
Sane's Avatar
 
Join Date: Apr 2005
Posts: 1,799
Rep Power: 5 Sane will become famous soon enough
Re: Linked List problem - Deleting a node
peaceofpi was most likely referring to the author's use of cout (part of the C++ standard) and the "new" operator (C++ only), among other possible inconsistencies with C.
Sane is offline   Reply With Quote
Old Dec 14th, 2007, 1:30 AM   #6
Salem
Programmer
 
Join Date: Nov 2007
Posts: 33
Rep Power: 0 Salem is on a distinguished road
Re: Linked List problem - Deleting a node
> Could someone show me where I went wrong?
Well you had a linked list which looked like this
(Toggle Plain Text) 
+=====+      +=====+      +=====+      +=====+      +=====+            
|  A  |----->|  B  |----->|  C  |----->|  D  |----->|  E  |----->NULL
+=====+      +=====+      +=====+      +=====+      +=====+

What you should end up with, after deleting 'D' is
(Toggle Plain Text) 
+=====+      +=====+      +=====+      +=====+            
|  A  |----->|  B  |----->|  C  |----->|  E  |----->NULL
+=====+      +=====+      +=====+      +=====+

But instead, you've got
(Toggle Plain Text) 
+=====+      +=====+      +=====+      
|  A  |----->|  B  |----->|  C  |----->junk
+=====+      +=====+      +=====+

You can't just blow away the node you want to delete, you need to repair the pointer chain to jump over the node you're going to delete, before you delete it.

You also need some extra care when the node being deleted is also the head node in the list.
__________________
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
Salem is offline   Reply With Quote
Old Dec 14th, 2007, 5:46 AM   #7
grumpy
Programming Guru
 
grumpy's Avatar
 
Join Date: Jun 2005
Location: Adelaide, South Australia
Posts: 1,198
Rep Power: 5 grumpy is on a distinguished road
Re: Linked List problem - Deleting a node
Sorry, Salem, you missed the real problem ...

There is also a problem that will emerge when creating the list. head_ptr is never initialised so it points to anything valid (i.e. a data structure). The first call to add_user will therefore introduce undefined behaviour. The code that creates a struct pointed at by current is fine, although it stores the address of the created struct in a local variable. Then move_current_to_end() is called, which does;
(Toggle Plain Text) 
current_ptr=head_ptr;
while(current_ptr->next!=NULL)
{
    current_ptr=current_ptr->next;
}
which is chock full of undefined behaviour since head_ptr has never been initialised..... if current_ptr does not point at anything valid, accessing the value of current_ptr->next yields undefined behaviour.
grumpy is offline   Reply With Quote
Old Dec 15th, 2007, 1:11 PM   #8
Brent
Highly Adaptive Penguin
 
Brent's Avatar
 
Join Date: May 2005
Location: United States
Posts: 249
Rep Power: 4 Brent is on a distinguished road
Re: Linked List problem - Deleting a node
Ok, I have revised the code a bit, and I still having problems with the del() function.


c++ Syntax (Toggle Plain Text) 
  1. #ifndef LIST_H
  2. #define LIST_H
  3.  
  4. struct user
  5. {
  6. 	char uname[50];
  7. 	char address[15];
  8. 	int socket;
  9. 	user *next;
  10. };
  11.  
  12. user *head_ptr;
  13. user *current_ptr;
  14.  
  15.  
  16. void move_current_to_end()
  17. {
  18. 	current_ptr=head_ptr;
  19.  
  20. 	while(current_ptr->next!=NULL)
  21. 	{
  22. 		current_ptr=current_ptr->next;
  23. 	}
  24. }
  25.  
  26.  
  27. //initializes linked list with some junk values
  28. void init()     
  29. {
  30. 	head_ptr = new user;
  31.  
  32. 	strcpy(head_ptr->uname, "BEGIN");
  33. 	strcpy(head_ptr->address, "0.0.0.0");
  34. 	head_ptr->socket = 0;
  35. 	head_ptr->next = NULL;
  36. }
  37.  
  38. void add_user(char *name, char *addr, int sock)
  39. {
  40. 	user *new_rec_ptr;
  41.  
  42. 	new_rec_ptr=new user;
  43.  
  44. 	strcpy(new_rec_ptr->uname,name);
  45. 	strcpy(new_rec_ptr->address,addr);
  46. 	new_rec_ptr->socket=sock;
  47.  
  48. 	move_current_to_end();
  49. 	current_ptr->next=new_rec_ptr;
  50. }
  51.  
  52.  
  53.  
  54.  
  55. void disp()
  56. {
  57. 	current_ptr=head_ptr;
  58. 	cout<<"--USERS--ONLINE--\n";
  59. 	do
  60. 	{
  61. 		cout<<"-----------------------\n";
  62. 		cout<<"username: "<<current_ptr->uname<<endl;
  63. 		cout<<"IP: "<<current_ptr->address<<endl;
  64. 		cout<<"socket: "<<current_ptr->socket<<endl;
  65. 		cout<<"-----------------------\n";
  66.                 current_ptr=current_ptr->next;
  67. 	}while(current_ptr!=NULL);
  68. }
  69.  
  70. void del(char *name)
  71. {
  72. 	user *temp_ptr;
  73.  
  74. 	current_ptr=head_ptr;
  75.  
  76. 	while(current_ptr!=NULL)
  77. 	{
  78. 		if(strcmp(current_ptr->uname,name)==0)
  79. 		{
  80. 			temp_ptr=current_ptr->next; //store node after current
  81. 			delete current_ptr;  //delete current node
  82. 			current_ptr=temp_ptr;   //set current to temp
  83.  
  84. 			break;
  85. 		}	
  86. 		else
  87. 		{
  88. 			current_ptr=current_ptr->next;	
  89. 		}
  90. 	}
  91.  
  92. }
  93.  
  94. int search(char *name)
  95. {  
  96.     current_ptr=head_ptr;
  97.  
  98.     while(current_ptr != NULL)
  99.     {
  100. 		if(strcmp(current_ptr->uname,name)==0)
  101. 		{       
  102. 			return -1;		
  103. 		}
  104. 		else
  105. 		{
  106. 			current_ptr=current_ptr->next;
  107. 		}
  108.     }
  109.  
  110. 	return -2;
  111. }
  112.  
  113.  
  114. #endif
Brent is offline   Reply With Quote
Old Dec 15th, 2007, 9:12 PM   #9
WaltP
Programmer
 
Join Date: Oct 2007
Posts: 39
Rep Power: 0 WaltP is on a distinguished road
Re: Linked List problem - Deleting a node
You need to keep track of the last_ptr. Then when you delete, last_ptr.next is loaded with current_ptr.next before you delete current_ptr.
WaltP is offline   Reply With Quote
Old Dec 16th, 2007, 3:39 PM   #10
Brent
Highly Adaptive Penguin
 
Brent's Avatar
 
Join Date: May 2005
Location: United States
Posts: 249
Rep Power: 4 Brent is on a distinguished road
Re: Linked List problem - Deleting a node
Thanks for all of the help, I finally got it to work. Here is the code:

c++ Syntax (Toggle Plain Text) 
  1. #ifndef LIST_H
  2. #define LIST_H
  3.  
  4. #include<string>
  5. #include<iostream>
  6.  
  7. struct user
  8. {
  9. 	char uname[50];
  10. 	char address[15];
  11. 	int socket;
  12. 	user *next;
  13. };
  14.  
  15. user *head_ptr;
  16. user *current_ptr;
  17.  
  18.  
  19.  
  20. void move_current_to_end()
  21. {
  22. 	current_ptr=head_ptr;
  23.  
  24. 	while(current_ptr->next!=NULL)
  25. 	{
  26. 		current_ptr=current_ptr->next;
  27. 	}
  28. }
  29.  
  30. void init()
  31. {
  32. 	head_ptr = new user;
  33.  
  34. 	//head_ptr->next = NULL;
  35. }
  36.  
  37. void add_user(char *name, char *addr, int sock)
  38. {		
  39. 	user *new_rec_ptr;
  40.  
  41. 	new_rec_ptr=new user;
  42. 	if(new_rec_ptr!=NULL)
  43.     {
  44. 		strcpy(new_rec_ptr->uname,name);
  45. 		strcpy(new_rec_ptr->address,addr);
  46. 		new_rec_ptr->socket=sock;	
  47. 		move_current_to_end();
  48. 		current_ptr->next=new_rec_ptr;
  49. 	}
  50. 	else
  51. 	{
  52. 		cout<<"memory error, new user cannot be added\n";
  53. 	}
  54. }
  55.  
  56.  
  57.  
  58.  
  59. void disp()
  60. {
  61. 	current_ptr=head_ptr;
  62. 	cout<<"--USERS--ONLINE--\n";
  63. 	do
  64. 	{
  65. 		cout<<"-----------------------\n";
  66. 		cout<<"username: "<<current_ptr->uname<<endl;
  67. 		cout<<"IP: "<<current_ptr->address<<endl;
  68. 		cout<<"socket: "<<current_ptr->socket<<endl;
  69. 		cout<<"-----------------------\n";
  70. 		current_ptr=current_ptr->next;
  71. 	}while(current_ptr!=NULL);
  72. }
  73.  
  74.  
  75. void delete_from_head()
  76. {
  77.     current_ptr=head_ptr;
  78.     if(head_ptr->next==NULL)
  79.     {
  80.         head_ptr=current_ptr->next;
  81.     }
  82.     else
  83.     {
  84.         head_ptr=NULL;
  85.     }
  86.     delete current_ptr;
  87. }
  88.  
  89. void delete_from_end(user *previous_ptr)
  90. {
  91.     delete current_ptr;
  92.     previous_ptr->next=NULL;
  93.     current_ptr=head_ptr;
  94. }       
  95.  
  96. void delete_from_middle(user *previous_ptr)
  97. {
  98.     previous_ptr->next=current_ptr->next;
  99.     delete current_ptr;
  100.     current_ptr=head_ptr;
  101. }
  102.  
  103. void delete_node(user *previous_ptr)
  104. {
  105.     if(current_ptr==head_ptr)
  106.     {
  107.         delete_from_head();
  108.     }
  109.     else
  110.     {
  111.         if(current_ptr->next==NULL)
  112.         {
  113.             delete_from_end(previous_ptr);
  114.         }
  115.         else
  116.         {
  117.             delete_from_middle(previous_ptr);
  118.         }
  119.     }
  120. }
  121.  
  122.  
  123. void del(char *name)
  124. {
  125. 	user *prev_ptr;
  126.  
  127. 	prev_ptr=NULL;
  128. 	current_ptr=head_ptr;
  129.  
  130.  
  131. 	while((strcmp(current_ptr->uname, name)!=0)&&(current_ptr!=NULL))
  132.     {
  133.         prev_ptr=current_ptr;
  134.         current_ptr=current_ptr->next;
  135.     }
  136.  
  137.     if(current_ptr!=NULL)
  138.     {
  139.         delete_node(prev_ptr);
  140.     }
  141. }
  142.  
  143.  
  144.  
  145.  
  146.  
  147. int search(char *name)
  148. {  
  149.     current_ptr=head_ptr;
  150.  
  151.     while(current_ptr != NULL)
  152.     {
  153. 		if(strcmp(current_ptr->uname,name)==0)
  154. 		{       
  155. 			return -1;		
  156. 		}
  157. 		else
  158. 		{
  159. 			current_ptr=current_ptr->next;
  160. 		}
  161.     }
  162.  
  163. 	return -2;
  164. }
  165.  
  166.  
  167. #endif
Brent is offline   Reply With Quote
Reply

Bookmarks

« Previous Thread in Forum | Next Thread in Forum »

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes
Linear Mode Linear Mode

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
linked list problems bl00dninja C++ 6 Feb 17th, 2008 10:30 AM
linked list keep getting extra node kruptof C++ 10 Dec 22nd, 2006 10:44 PM
Linked List problem Berto C 3 Apr 4th, 2005 6:24 AM
airport Log program using 3D linked List : problem reading from file gemini_shooter C++ 0 Mar 2nd, 2005 4:12 PM
string problem when passing in linked list quantz C++ 0 Feb 27th, 2005 10:11 AM


Contact Us - DaniWeb IT Discussion Community - Privacy Statement - Top


DaniWeb IT Discussion Community
All times are GMT -5. The time now is 1:51 AM.

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC