Link list Query

Reply

Join Date: Mar 2006
Posts: 4
Reputation: debugger is an unknown quantity at this point 
Solved Threads: 0
debugger debugger is offline Offline
Newbie Poster

Link list Query

 
0
  #1
Mar 24th, 2006
I am trying to delete the first node in the singly link list but cant seem to do so? My Code is below... Could someone please suggest something.
thanks.
This program has an enqueue function which works.
*p is a pointer to a node which has been allocated using malloc.
The descriptions are given below for reference.
typedef struct Node
{
int element;
struct Node *next;
} Node;

typedef struct Queue
{
Node *front;
Node *rear;
} Queue;

Now this is the function I am having problems with.

int q_dequeue ( Queue *theQ, int *value)
{
Node *p;

if( theQ -> front == NULL)
{
printf ("Queue is empty. Cannot dequeue.\n");
return 0;
}

p = theQ -> front;
*value = p -> element;

if(theQ -> front != NULL && theQ -> rear == NULL)
{
theQ -> front = NULL;
theQ -> rear = NULL;
free(p);
}
else
{
theQ -> front = p -> next;
free(p);
}

return 1;
}
Reply With Quote Quick reply to this message  
Join Date: Dec 2005
Posts: 5,850
Reputation: Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute 
Solved Threads: 749
Team Colleague
Salem's Avatar
Salem Salem is offline Offline
Void main'ers are DOOMed

Re: Link list Query

 
0
  #2
Mar 25th, 2006
Well that seems to be OK in itself.
Perhaps the problem is with the way you create the queue in the first place, and this is just where you notice that it doesn't work.

Post some more code please.

PS.
Use the [code][/code] tags when posting code.
Reply With Quote Quick reply to this message  
Join Date: Mar 2006
Posts: 4
Reputation: debugger is an unknown quantity at this point 
Solved Threads: 0
debugger debugger is offline Offline
Newbie Poster

Re: Link list Query

 
0
  #3
Mar 25th, 2006
Originally Posted by Salem
Well that seems to be OK in itself.
Perhaps the problem is with the way you create the queue in the first place, and this is just where you notice that it doesn't work.

Post some more code please.

PS.
Use the [code][/code] tags when posting code.
Here is the whole code: Please Help
  1. /*
  2.  * queue.c
  3.  */
  4. #include <stdlib.h>
  5. #include<stdio.h>
  6. #include "queue.h"
  7.  
  8.  
  9. /*
  10.  * Initialize the queue. Must be called before any other
  11.  * queue function
  12.  */
  13. void q_init ( Queue *theQ )
  14. {
  15. theQ -> front = NULL;
  16. theQ -> rear = NULL;
  17. }
  18.  
  19. /*
  20.  * Add value to the back of the queue
  21.  * returns 1 on success, 0 on failure
  22.  */
  23. int q_enqueue ( Queue *theQ, int value )
  24. {
  25. Node *p = (Node *)malloc(sizeof(Node));
  26.  
  27. if(!p)
  28. {
  29. printf("Malloc Failed.\n");
  30. return 0;
  31. }
  32. else
  33. {
  34. //make the element of the new node = value
  35. p -> element = value;
  36. p -> next = NULL;
  37. }
  38.  
  39. if(theQ -> front == NULL) //change where the front and rear
  40. { //pointers point
  41. theQ -> front = p;
  42. theQ -> rear = p -> next;
  43. }
  44. else
  45. {
  46. theQ -> rear = p;
  47. theQ -> front -> next = theQ -> rear;
  48. }
  49. return 1;
  50. }
  51.  
  52. /*
  53.  * Remove the first element from the queue
  54.  * returns 1 on success, 0 on failure
  55.  */
  56. int q_dequeue ( Queue *theQ, int *value)
  57. {
  58. Node *p;
  59.  
  60. if( theQ -> front == NULL)
  61. {
  62. printf ("Queue is empty. Cannot dequeue.\n");
  63. return 0;
  64. }
  65.  
  66. p = theQ -> front;
  67. *value = p -> element;
  68.  
  69. if(theQ -> front == theQ -> rear)
  70. {
  71. theQ -> front = NULL;
  72. theQ -> rear = NULL;
  73. free(p -> element);
  74. free(p);
  75. }
  76.  
  77. else
  78. {
  79. theQ -> front = p -> next;
  80. free(p -> element);
  81. free(p);
  82. }
  83. return 1;
  84. }
  85.  
  86. /*
  87.  * Is the queue empty?
  88.  * returns 1 if the queue is empty, 0 otherwise
  89.  */
  90. int q_isEmpty ( Queue *theQ )
  91. {
  92. if(theQ -> front == NULL)
  93. {
  94. //printf ("Queue is empty.\n");
  95. return 1;
  96. }
  97. else
  98. {
  99. return 0;
  100. }
  101. }

Other files used to implement this code:

  1. /*
  2.  * queue.h
  3.  */
  4. #ifndef __QUEUE_H__
  5. #define __QUEUE_H__
  6.  
  7. /*
  8.  * This structure holds the individual nodes
  9.  * in the queue structure
  10.  */
  11. typedef struct Node
  12. {
  13. int element;
  14. struct Node *next;
  15. } Node;
  16.  
  17. /*
  18.  * This is the actual Queue. Notice there
  19.  * are two Node pointers. One points to
  20.  * the front of the queue and one points to
  21.  * the rear of the queue
  22.  */
  23. typedef struct Queue
  24. {
  25. Node *front;
  26. Node *rear;
  27. } Queue;
  28.  
  29. /*
  30.  * Initialize the queue. Must be called before any other
  31.  * queue function
  32.  */
  33. void q_init ( Queue *theQ );
  34.  
  35. /*
  36.  * Add value to the back of the queue
  37.  * returns 1 on success, 0 on failure
  38.  */
  39. int q_enqueue ( Queue *theQ, int value );
  40.  
  41. /*
  42.  * Remove the first element from the queue
  43.  * returns 1 on success, 0 on failure
  44.  */
  45. int q_dequeue ( Queue *theQ, int *value);
  46.  
  47. /*
  48.  * Is the queue empty?
  49.  * returns 1 if the queue is empty, 0 otherwise
  50.  */
  51. int q_isEmpty ( Queue *theQ );
  52.  
  53. #endif


This is my test file:
  1. /*
  2.  * queuetest.c
  3.  */
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include "queue.h"
  7.  
  8. int main ( )
  9. {
  10. /* Here are two different ways to create a queue.
  11. * the first one allocates the queue on the stack, so we
  12. * need to pass the address of this queue to the q_ methods
  13. *
  14. * The second one uses a pointer, and allocates storage for the
  15. * queue dynamically. This means we have to call free on the
  16. * pointer to deallocate the memory.
  17. */
  18. Queue q1;
  19. Queue *q2 = (Queue *)malloc (sizeof(Queue));
  20. Queue *q3 = (Queue *)malloc (sizeof(Queue));
  21. int i, j, passed;
  22.  
  23. if (!q2 || !q3)
  24. {
  25. printf ("Failed allocation.\n");
  26. return 0;
  27. }
  28.  
  29. q_init (&q1); /* Note the use of the & operator */
  30. q_init (q2);
  31. q_init (q3);
  32.  
  33. /*
  34. * Make sure that newly created queues are empty
  35. */
  36. if (q_isEmpty(&q1))
  37. printf ("Test 1 passed. Queue is empty.\n");
  38. else
  39. printf ("Test 1 failed. Newly created queue is not empty\n");
  40.  
  41. if (q_isEmpty(q2))
  42. printf ("Test 2 passed. Queue is empty.\n");
  43. else
  44. printf ("Test 2 failed. Newly created queue is not empty\n");
  45.  
  46. /*
  47. * Enqueue 1000 integers and verify that the values
  48. * are dequeued in the correct order
  49. */
  50. passed = 1;
  51. for ( i = 0; i < 1000; i++ )
  52. {
  53. if ( !q_enqueue(&q1, i) )
  54. {
  55. passed = 0;
  56. break;
  57. }
  58. }
  59. if (passed)
  60. {
  61. for ( i = 0; i < 1000; i++ )
  62. {
  63. int val;
  64. if (!q_dequeue (&q1, &val) )
  65. {
  66. passed = 0;
  67. break;
  68. }
  69. if ( val != i )
  70. {
  71. passed = 0;
  72. break;
  73. }
  74. }
  75. if (passed)
  76. printf ("Test 3 passed. Enqueue and Dequeue\n");
  77. else
  78. printf ("Test 3 failed. Dequeue\n");
  79. }
  80. else
  81. {
  82. printf ("Test 3 failed. Didn't enqueue.\n");
  83. }
  84.  
  85. /*
  86. * enqueue 1 item, then dequeue it.
  87. * then enqueue two more items and dequeue them.
  88. * then verify the queue is empty.
  89. */
  90. if (q_enqueue (q2, 7))
  91. {
  92. if (q_isEmpty(q2))
  93. {
  94. printf ("Test 4 failed. empty after enqueue\n");
  95. }
  96. else
  97. {
  98. int val;
  99. if (q_dequeue(q2, &val))
  100. {
  101. if (val == 7)
  102. {
  103. if (q_enqueue(q2, 9))
  104. {
  105. if (q_enqueue(q2, 11))
  106. {
  107. int val1, val2;
  108.  
  109. if (q_dequeue(q2,&val1))
  110. {
  111. if (q_dequeue(q2,&val2))
  112. {
  113. if (val1 == 9 && val2 == 11 && q_isEmpty(q2) )
  114. {
  115. printf ("Test 4 passed.\n");
  116. }
  117. else
  118. {
  119. printf ("Test 4 failed. 9 & 11\n");
  120. }
  121. }
  122. else
  123. {
  124. printf ("Test 4 failed. dequeue 11\n");
  125. }
  126. }
  127. else
  128. {
  129. printf ("Test 4 failed. dequeue 9.\n");
  130. }
  131. }
  132. else
  133. {
  134. printf("Test 4 failed. enqueue 11\n");
  135. }
  136. }
  137. else
  138. {
  139. printf ("Test 4 failed. enqueue 9\n");
  140. }
  141. }
  142. else
  143. {
  144. printf ("Test 4 failed. dequeue != 7\n");
  145. }
  146. }
  147. else
  148. {
  149. printf("Test 4 failed. dequeue 7\n");
  150. }
  151. }
  152. }
  153. else
  154. {
  155. printf ("Test 4 failed. enqueue 7.\n");
  156. }
  157.  
  158. if (q_isEmpty(q3))
  159. printf ("Test 5 passed. Queue is empty.\n");
  160. else
  161. printf ("Test 5 failed. Newly created queue is not empty\n");
  162.  
  163. passed = 1;
  164. for ( i = 0; i < 10; i++ )
  165. {
  166. q_enqueue(q3, i);
  167. }
  168.  
  169. for ( j = 0; j < 5; j++ )
  170. {
  171. int val;
  172. if ( !q_dequeue (q3, &val) )
  173. {
  174. passed = 0;
  175. }
  176. else
  177. {
  178. if ( val != j )
  179. {
  180. passed = 0;
  181. break;
  182. }
  183. }
  184. }
  185.  
  186. if ( passed )
  187. {
  188. int val;
  189.  
  190. for ( i = 10; i < 20; i++ )
  191. {
  192. q_enqueue ( q3, i);
  193. }
  194. for ( j = 5; j < 20 ; j++ )
  195. {
  196. if ( !q_dequeue (q3, &val))
  197. {
  198. passed = 0;
  199. break;
  200. }
  201. else
  202. {
  203. if ( val != j )
  204. {
  205. passed = 0;
  206. break;
  207. }
  208. }
  209. }
  210. }
  211.  
  212. if ( passed )
  213. printf ("Test 6 passed.\n");
  214. else
  215. printf ("Test 6 failed.\n");
  216.  
  217. /* Not technically required since we're about to end the program
  218. * but it is a good habit to free any memory you malloc
  219. */
  220. free(q2);
  221. free(q3);
  222. return 0;
  223. }
Reply With Quote Quick reply to this message  
Reply

This thread is more than three months old.
Perhaps start a new thread instead?
Message:


Thread Tools Search this Thread



About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC