C RSS C RSS

Seg Fault ~ Linked List Delete

Reply

•
•
Join Date: Nov 2005
Posts: 8
Reputation: Mistro116 is an unknown quantity at this point 
Solved Threads: 0
Mistro116 Mistro116 is offline Offline
Newbie Poster

Seg Fault ~ Linked List Delete

 
0
  #1
Dec 12th, 2005
Hello, I get the following seg fault error when I try to delete the last node of the list. Does anyone know why? My delete function and high level function are included below: The seg fault only occurs when the if value in BeginQuizFirstTry detecting that CheckAnswer is not true or = 0. Can anyone tell me why this seg faults?

C Syntax (Toggle Plain Text) 
  1. int Delete (NODEPTR *headPtr, char *target)
  2. {
  3.    /*  Node pointers that reference the previous node
  4.        and the current node in the list.               */
  5.    NODEPTR prev = NULL, curr = NULL;
  6.  
  7.    /*  Check to see if the list is empty.  */
  8.    if (IsEmpty (*headPtr))
  9.    {
  10.       /*  Display an appropriate message indicating that
  11. 	  deleting from the list was not accomplished
  12. 	  because the list is empty.                      */
  13.       fprintf (stderr, "Unable to delete from an empty list.\n\n");
  14.  
  15.       /*  If the list is empty, return the integer value
  16. 	  of -1, indicating that the question, char
  17. 	  *target, was not successfully deleted from the
  18. 	  list.                                           */
  19.       return (-1);
  20.    }
  21.    /*  Traverse the list until the target value is found.  */
  22.    else
  23.    {
  24.       /*  Initialize the node pointer referencing a previous
  25. 	  node in the list to NULL.                           */
  26.       prev = NULL;
  27.  
  28.       /*  Set the node pointer referencing a current node to
  29. 	  the head of the list.                               */
  30.       curr = *headPtr;
  31.  
  32.       /*  First check to see if the question, char *target,
  33. 	  that we want to delete is stored in the first
  34. 	  node in the list, because this would require
  35. 	  *headPtr to be modified.                           */
  36.       if (strcmp ((*headPtr) -> data.question, target) == 0)
  37.       { 
  38. 	 /*  If the question, char *target, is stored in the
  39. 	     first node in the list, change the head of the
  40. 	     list to start at the node pointer referencing
  41. 	     the current node's next pointer.                 */
  42. 	 *headPtr = curr -> next;
  43.  
  44. 	 /*  Delete and free the memory that was being used
  45. 	     to store the question, char *target, in the
  46. 	     first node of the list.                         */
  47. 	 free (curr);
  48.  
  49. 	 /*  If the question, char *target, was freed and
  50. 	     deleted, return the integer value of 1,
  51. 	  indicating that the question was successfully
  52. 	  deleted from the list.                         */
  53. 	 return (1);
  54.       }
  55.       /*  Otherwise, traverse through the list to find the
  56. 	  question, char *target, to be deleted.            */
  57.       else
  58.       {
  59. 	 /*  Traverse the list if the node pointer
  60. 	     referencing the current node in the list is not
  61. 	     equal to NULL and the node pointer referencing
  62. 	     the current node in the list is not storing the
  63. 	     question, char *target, in the data portion of
  64. 	     its node.                                        */
  65. 	 while ((curr != NULL) &&
  66. 		(strcmp (curr -> data.question, target) != 0))
  67. 	 {
  68. 	    /*  Traverse the list.  */
  69. 	    prev = curr;
  70. 	    curr = curr -> next;
  71. 	 }
  72.  
  73. 	 /*  If the node pointer refencing the current node in
  74. 	     the list not equal to NULL, then the question,
  75. 	     char *target, was found.                           */
  76. 	 if (curr != NULL)
  77. 	 {
  78. 	    /*  Change the next pointer of the previous node,
  79. 		in order to avoid a broken list.               */
  80. 	    prev -> next = curr -> next;
  81.  
  82. 	    /*  Delete and free the memory that was being used
  83. 		to store the question, char *target, in this
  84. 		node of the list.                               */
  85. 	    free (curr);
  86.  
  87. 	    /*  If the question, char *target, was freed and
  88. 		deleted, return the integer value of 1,
  89. 		indicating that the question was successfully
  90. 		deleted from the list.                         */
  91. 	    return (1);
  92. 	 }
  93. 	 /*  Otherwise, the question, char *target, was not
  94. 	     found in the list.                              */
  95. 	 else
  96. 	 {
  97. 	    /*  If the question, char *target, was not found
  98. 		in the list, return the integer value of -1,
  99. 		indicating that the question was not
  100. 		successfully deleted from the list.           */
  101. 	    return (-1);
  102. 	 }
  103.       }
  104.    }
  105. }
  106.  
  107. int BeginQuizFirstTry (NODEPTR *headListPtr1,
  108. 		       NODEPTR *headListPtr2,
  109. 		       int numberOfTotalQuestions)
  110. {
  111.    /*  A node pointer that will reference the current node
  112.        in the list, starting with the head pointer of the
  113.        first list.                                          */
  114.    NODEPTR curr = *headListPtr1;
  115.  
  116.    /*  A node pointer that will reference a temporary node
  117.        in the list, which will be used for inserting nodes
  118.        into the second list.                                */
  119.    NODEPTR temp;
  120.  
  121.    /*  An array of characters, or a string, which will hold
  122.        the answer that the user inputted for the given
  123.        question that he/she was being asked during the quiz.  */
  124.    char questionAnswer [NUMBEROFANSWERCHARACTERS];
  125.  
  126.    /*  An integer counter variable that will be used to
  127.        label each of the questions in the quiz.          */
  128.    int questionCounter = 0;
  129.  
  130.    /*  An integer counter variable that will be used to
  131.        count the number of questions that the user answered
  132.        correctly during his/her trial of taking the quiz.    */
  133.    int correctAnswerCounter = 0;
  134.  
  135.    /*  A QUIZ structure that will be used to insert each
  136.        question from the first list, into the second list.  */
  137.    QUIZ insertedQuestion;
  138.  
  139.    /*  A float variable that will be used to store the
  140.        user's percentage of correct answers during the
  141.        user's first trial of taking the quiz.           */
  142.    float scoreTrial1;
  143.  
  144.    /*  Display a message indicating that the quiz has
  145.        begun for the user.                             */
  146.    printf ("Here are your questions. Good luck !!!\n\n");
  147.  
  148.    /*  Traverse the list until the end.  */
  149.    while (curr != NULL)
  150.    {
  151.       /*  Increment questionCounter each time a new question
  152. 	  from the quiz is presented to the user.             */
  153.       questionCounter++;
  154.  
  155.       /*  Display each of the questions in the quiz to the
  156. 	  user.                                             */
  157.       printf ("   %d. ", questionCounter);
  158.       DisplayQuestion (curr);
  159.  
  160.       /*  Read in the user's answer for each of the questions
  161. 	  in the quiz.                                         */
  162.       scanf ("%s", questionAnswer);
  163.  
  164.       /*  If the user's answer is not correct, then delete it
  165. 	  from the first list and insert it into the second
  166. 	  list.                                                */
  167.       if (CheckAnswer (curr, questionAnswer,
  168. 		       &correctAnswerCounter) != 1)
  169.       {
  170. 	 /*  Copy the original question and correct answer that
  171. 	     the user was just being asked into the QUIZ structure,
  172. 	     insertedQuestion.                                       */
  173. 	 strcpy (insertedQuestion.question, curr -> data.question);
  174. 	 strcpy (insertedQuestion.answer, curr -> data.answer);
  175.  
  176. 	 /*  Create enough space in memory for a temporary node
  177. 	     that will be inserted into the second list.         */
  178. 	 temp = CreateNode ();
  179.  
  180. 	 /*  Store the contents of the original question and
  181. 	     correct answer that the user was just being asked
  182. 	     into the data portion of the temporary node that
  183. 	     was just created.                                  */
  184. 	 SetData (temp, insertedQuestion);
  185.  
  186. 	 /*  Insert the temporary node into the second list.  */
  187. 	 Insert (headListPtr2, temp);
  188.  
  189. 	 /*  Free the memory that was used to create the temporary
  190. 	     node.                                                  */
  191. 	 free (temp);
  192.  
  193. 	 /*  Set the node pointer referencing the current node
  194. 	     (the current question in the quiz) to point to the
  195. 	     next node in the list, or the next question in the
  196. 	     quiz.                                               */
  197. 	 curr = curr -> next;
  198.  
  199. 	    /*  Delete the question and its correct answer,
  200. 		which was just asked to the user, from the first
  201. 		list.                                             */
  202. 	    Delete (headListPtr1, insertedQuestion.question);
  203.       }
  204.       else
  205.       {
  206. 	 /*  Set the node pointer referencing the current node
  207. 	     (the current question in the quiz) to point to the
  208. 	     next node in the list, or the next question in the
  209. 	     quiz.                                               */
  210. 	 curr = curr -> next;
  211.       }
  212.    }
  213.  
  214.    /*  Calculate the user's percentage of questions that were
  215.        answered correctly during the first trial of the quiz.  */
  216.    scoreTrial1 = CalculateScore ((float)correctAnswerCounter,
  217. 				 (float)numberOfTotalQuestions);
  218.  
  219.    /*  Display the user's score and tell him/her to retry the
  220.        questions that were answered incorrectly.               */
  221.    printf ("Your score is  %.2f%%\n", scoreTrial1);
  222.    printf ("Improve your score by repeating the ones you missed.\n\n\n");
  223.  
  224.    /*  Return the number of questions that were answered
  225.        correctly by the user during this trial so that the
  226.        score can be recalculated in the second trial.       */
  227.    return correctAnswerCounter;
  228. }

Thanks in advance,
Mistro116
Reply With Quote Quick reply to this message  
•
•
Join Date: May 2004
Posts: 178
Reputation: jim mcnamara is on a distinguished road 
Solved Threads: 10
jim mcnamara jim mcnamara is offline Offline
Junior Poster

Re: Seg Fault ~ Linked List Delete

 
0
  #2
Dec 12th, 2005
After a ver quick look, I think that you overwrote a pointer - having it point to a bogus address.

malloc works (It's called Doug Lea malloc which is the basis for many versions of malloc) kinda like this:
C Syntax (Toggle Plain Text) 
  1. typedef
  2. union
  3. {
  4.     ptrdiff_t malloc_size;
  5.     void *ptr;
  6. } malloc_t;
The malloc routine returns ptr to your program. When you call free later on, it assumes there is a value in the address immediately "underneath" the pointer. And that it is the same value you started with. Well, if ptr was changed, the value under it could be 0xfffffff, or literally anything else. When free tries to work with the block referenced by ptr, it bumps into memory your process does not own because:

1. ptr references memory you don't own or is read-only
2. malloc_size is the forcing free to reference memory you don't own or is read-only.
Reply With Quote Quick reply to this message  
•
•
Join Date: Nov 2005
Posts: 8
Reputation: Mistro116 is an unknown quantity at this point 
Solved Threads: 0
Mistro116 Mistro116 is offline Offline
Newbie Poster

Re: Seg Fault ~ Linked List Delete

 
0
  #3
Dec 12th, 2005
•
•
•
•
Originally Posted by jim mcnamara
After a ver quick look, I think that you overwrote a pointer - having it point to a bogus address.

malloc works (It's called Doug Lea malloc which is the basis for many versions of malloc) kinda like this:
C Syntax (Toggle Plain Text) 
  1. typedef
  2. union
  3. {
  4.     ptrdiff_t malloc_size;
  5.     void *ptr;
  6. } malloc_t;
The malloc routine returns ptr to your program. When you call free later on, it assumes there is a value in the address immediately "underneath" the pointer. And that it is the same value you started with. Well, if ptr was changed, the value under it could be 0xfffffff, or literally anything else. When free tries to work with the block referenced by ptr, it bumps into memory your process does not own because:

1. ptr references memory you don't own or is read-only
2. malloc_size is the forcing free to reference memory you don't own or is read-only.
Thanks, but that has nothing to do with my function. I've malloc'd the data for the node, the pointer is returned fine. That's not the problem. The problem is the segmentation fault at the end of the list. I've come up with some new code, using this delete function.

Can anyone tell me why this doesn't delete the items in the list are wrong when CheckAnswer is evaluated:

C Syntax (Toggle Plain Text) 
  1. int BeginQuizFirstTrial (NODEPTR *headListPtr1,
  2. 			 NODEPTR *headListPtr2,
  3. 			 int numberOfTotalQuestions)
  4. {
  5.    /*  A node pointer that will reference the current node
  6.        in the list, starting with the head pointer of the
  7.        first list.                                          */
  8.    NODEPTR curr = *headListPtr1;
  9.  
  10.    /*  A node pointer that will reference a temporary node
  11.        in the list, which will be used for inserting nodes
  12.        into the second list.                                */
  13.    NODEPTR temp;
  14.  
  15.    /*  An array of characters, or a string, which will hold
  16.        the answer that the user inputted for the given
  17.        question that he/she was being asked during the quiz.  */
  18.    char questionAnswer [NUMBEROFANSWERCHARACTERS];
  19.  
  20.    /*  An integer counter variable that will be used to
  21.        label each of the questions in the quiz.          */
  22.    int questionCounter = 0;
  23.  
  24.    /*  An integer counter variable that will be used to
  25.        count the number of questions that the user answered
  26.        correctly during his/her trial of taking the quiz.    */
  27.    int correctAnswerCounter = 0;
  28.  
  29.    /*  A QUIZ structure that will be used to insert each
  30.        question from the first list, into the second list.  */
  31.    QUIZ insertedQuestion;
  32.  
  33.    /*  A float variable that will be used to store the
  34.        user's percentage of correct answers during the
  35.        user's first trial of taking the quiz.           */
  36.    float scoreTrial1;
  37.  
  38.    /*  Display a message indicating that the quiz has
  39.        begun for the user.                             */
  40.    printf ("Here are your questions. Good luck !!!\n\n");
  41.  
  42.    /*  Traverse the list until the end.  */
  43.    while (curr != NULL)
  44.    {
  45.       /*  Increment questionCounter each time a new question
  46. 	  from the quiz is presented to the user.             */
  47.       questionCounter++;
  48.  
  49.       /*  Display each of the questions in the quiz to the
  50. 	  user.                                             */
  51.       printf ("   %d. ", questionCounter);
  52.       DisplayQuestion (curr);
  53.  
  54.       /*  Read in the user's answer for each of the questions
  55. 	  in the quiz.                                         */
  56.       scanf ("%s", questionAnswer);
  57.  
  58.       /*  If the user's answer is not correct, then delete it
  59. 	  from the first list and insert it into the second
  60. 	  list.                                                */
  61.       if (CheckAnswer (curr, questionAnswer,
  62. 		       &correctAnswerCounter) != 1)
  63.       {
  64. 	 /*  Copy the original question and correct answer that
  65. 	     the user was just being asked into the QUIZ structure,
  66. 	     insertedQuestion.                                       */
  67. 	 strcpy (insertedQuestion.question, curr -> data.question);
  68. 	 strcpy (insertedQuestion.answer, curr -> data.answer);
  69.  
  70. 	 /*  Create enough space in memory for a temporary node
  71. 	     that will be inserted into the second list.         */
  72. 	 temp = CreateNode ();
  73.  
  74. 	 /*  Store the contents of the original question and
  75. 	     correct answer that the user was just being asked
  76. 	     into the data portion of the temporary node that
  77. 	     was just created.                                  */
  78. 	 SetData (temp, insertedQuestion);
  79.  
  80. 	 /*  Insert the temporary node into the second list.  */
  81. 	 Insert (headListPtr2, temp);
  82.  
  83. 	 /*  Set the node pointer referencing the current node
  84. 	     (the current question in the quiz) to point to the
  85. 	     next node in the list, or the next question in the
  86. 	     quiz.                                               */
  87. 	 curr = curr -> next;
  88.  
  89. 	 /*  Make sure the node pointer referencing the current
  90. 	     node (the current question in the quiz) contains
  91. 	     a node and is not beyond the end of the first list.  */
  92. 	 if (curr != NULL && curr -> next != NULL)
  93. 	 {
  94.  
  95. 	    /*  Delete the question and its correct answer,
  96. 		which was just asked to the user, from the first
  97. 		list.                                             */
  98. 	    Delete (headListPtr1, insertedQuestion.question);
  99. 	 }
  100.       }
  101.       else
  102.       {
  103. 	 /*  Set the node pointer referencing the current node
  104. 	     (the current question in the quiz) to point to the
  105. 	     next node in the list, or the next question in the
  106. 	     quiz.                                               */
  107. 	 curr = curr -> next;
  108.       }
  109.    }
  110.  
  111.    /*  Destroy the first list and all of its contents, and free
  112.        all of the memory that was allocated to store the node
  113.        data once the user has been asked all of the questions in
  114.        the quiz read from the data file containing the original
  115.        list of questions and correct answers.                     */
  116.    DestroyList (headListPtr1);
  117.  
  118.    /*  Calculate the user's percentage of questions that were
  119.        answered correctly during the first trial of the quiz.  */
  120.    scoreTrial1 = CalculateScore ((float)correctAnswerCounter,
  121. 				 (float)numberOfTotalQuestions);
  122.  
  123.    /*  Display the user's score and tell him/her to retry the
  124.        questions that were answered incorrectly.               */
  125.    printf ("Your score is   %.2f%%\n", scoreTrial1);
  126.    printf ("Improve your score by repeating the ones you missed.\n\n\n");
  127.  
  128.    /*  Return the number of questions that were answered
  129.        correctly by the user during this trial so that the
  130.        score can be recalculated in the second trial.       */
  131.    return correctAnswerCounter;
  132. }

Thanks though,

Mistro116
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
This thread is more than three months old.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Similar Threads
Other Threads in the C Forum
Thread Tools Search this Thread



#include * adobe ansi api array asterisks binarysearch centimeter changingto char character cm copyimagefile cprogramme creafecopyofanytypeoffileinc createcopyoffile csyntax database directory dynamic execv feet fgets file fork frequency function getlasterror getlogicaldrivestrin givemetehcodez global grade graphics gtkgcurlcompiling gtkwinlinux hacking highest histogram include incrementoperators infiniteloop input interest kernel keyboard kilometer linked linkedlist linux linuxsegmentationfault list locate logical_drives looping loopinsideloop. lowest match matrix meter microsoft mqqueue number odf opendocumentformat owf pattern pdf performance pointer posix probleminc process program programming radix recursion recv repetition research reversing scanf segmentationfault sequential shape single socket socketprograming standard string systemcall threads turboc unix user voidmain() wab whythiscodecausesegmentationfault windows.h windowsapi
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC