440,948 Members | 1,595 Online
Need help? Post your question and get tips & solutions from a community of 440,948 IT Pros & Developers. It's quick & easy.

Recursive delete problems

 P: n/a The following function results in an infinite loop! After 5+ hours of debugging, I am still unable to decipher what I am incorrectly. Any assistance is greatly appreciated. Thanks in advance, Andrew ==========>Code<========== //-------------------------------------------------------------------- // // Recursive cRemove() function implemented in In-lab Exercise 3 // //-------------------------------------------------------------------- template < class DT > void List
:: cRemove() // Recursively removes all occurrences of the character 'c' from a list // of characters. Moves cursor to the beginning of the list. { cRemoveSub(head); cursor = head; } // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - template < class DT > void List
:: cRemoveSub ( ListNode
*& p ) // Recursive partner to the cRemove() function. { ListNode
* delete_node; ListNode
* prior_node; if ( p == NULL ) { return; } else if ((p->dataItem == 'c' || p->dataItem == 'C') && (p == head)) { delete_node = p; head = p = p->next; delete delete_node; cRemoveSub(p); } else if ((p->dataItem == 'c' || p->dataItem == 'C') && (p->next != 0)) { delete_node = p; p = p->next; prior_node = head; while(prior_node->next->dataItem != 'c' && prior_node->next->dataItem != 'C') { prior_node = prior_node->next; } delete delete_node; prior_node->next = p; cRemoveSub(p); } else if (p->next == 0) { delete p; p = 0; } else { cout << "Else: " << '[' << p->dataItem << "]->[" << p->next->dataItem << ']' << endl; cRemoveSub(p->next); } } Jul 19 '05 #1
8 Replies

 P: n/a "Andrew Edwards" wrote... The following function results in an infinite loop! After 5+ hours of debugging, I am still unable to decipher what I am incorrectly. Any assistance is greatly appreciated. Thanks in advance, Andrew ==========>Code<========== //-------------------------------------------------------------------- // // Recursive cRemove() function implemented in In-lab Exercise 3 // //-------------------------------------------------------------------- template < class DT > void List
:: cRemove() Well, without seeing what 'List<>' is I wouldn't dare to recommend anything. However, the usual scheme for deleting a singly-linked list is: void deleteListTailFirst(ListNode *plistnode) { if (plistnode->next != NULL) deleteListTailFirst(plistnode->next); // recurse deleteAllDataIn(plistnode); // non-recursive part } I recommend scrapping your solution and rewriting it afresh. Victor Jul 19 '05 #2

 P: n/a On Sat, 19 Jul 2003 19:57:00 GMT, "Andrew Edwards" wrote: The following function results in an infinite loop! After 5+ hours ofdebugging, I am still unable to decipher what I am incorrectly. The question is then, what exactly are you trying to achieve? Details do matter. Any assistance is greatly appreciated.Thanks in advance,Andrew==========>Code<==========//--------------------------------------------------------------------//// Recursive cRemove() function implemented in In-lab Exercise 3////--------------------------------------------------------------------template < class DT >void List
:: cRemove() The name "cRemove" is not very suggestive of what this routine is intended to achieve. When you can express something in code instead of comment(s), preferentially choose to express it in code. The compiler can't check comments, and they're not apparent where the routine is used. // Recursively removes all occurrences of the character 'c' from a list// of characters. Moves cursor to the beginning of the list.{ cRemoveSub(head); cursor = head;} Having a cursor (in more general terms, an iterator) built-in in the list abstraction isn't necessarily a good idea. In some cases it might make sense, for example if there should never be more than exactly one iterator. // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -template < class DT >void List
:: cRemoveSub ( ListNode
*& p )// Recursive partner to the cRemove() function.{ ListNode
* delete_node; ListNode

 P: n/a "Alf P. Steinbach" wrote: The question is then, what exactly are you trying to achieve? Details do matter. I'm trying to remove all occurrences of the character 'c' from list. Jul 19 '05 #4

 P: n/a "Alf P. Steinbach" wrote: The name "cRemove" is not very suggestive of what this routine is intended to achieve. When you can express something in code instead of comment(s), preferentially choose to express it in code. The compiler can't check comments, and they're not apparent where the routine is used. Quite understandable! The function names and list interface, however, are not my decision. They cannot be changed because there is test code already written with these names to which I have no access. Having a cursor (in more general terms, an iterator) built-in in the list abstraction isn't necessarily a good idea. In some cases it might make sense, for example if there should never be more than exactly one iterator. Again, the interface is predesigned and cannot be changed. Here's the start of your problems. This routine should absolutely not have to bother with 'head' and other external things. It should just delete nodes. In addition, consider using a function that returns the uppercase of a given character. I'm trying to remove all occurrence of 'c' or 'C' form the list. That, I thought, requires that I begin at the head of the list. Such multiple assignments are evil. Point taken! What's this supposed to accomplish, except an infinite loop? It's supposed to remove the character from the "middle" of the list. And what's the purpose of this? Delete the character if it's at the end of the list. This looks like debugging/trace output. As a general rule, don't manipulate data structures in debugging code. What is the best way to do debugging? I have a text editor and Borland's C++ Builder commandlinetools v5.5.1. I'm new to programming so my art of debugging is severely underdeveloped. Jul 19 '05 #5

 P: n/a "Andrew Edwards" wrote... "Victor Bazarov" wrote: Well, without seeing what 'List<>' is I wouldn't dare to recommend anything. Here are the two constructors I use: template < class DT > ListNode
:: ListNode ( const DT& initData, ListNode* nextPtr ) : dataItem(initData) , next(nextPtr) { } template < class DT > List

 P: n/a "Victor Bazarov" wrote: Sorry, I must have misunderstood. Why do you need recursion, then? Using iteration over recursion is not an option. This must be done with recursion. Jul 19 '05 #7

 P: n/a "Andrew Edwards" wrote in message news:go*********************@twister.southeast.rr. com... The following function results in an infinite loop! After 5+ hours of debugging, I am still unable to decipher what I am incorrectly. Any assistance is greatly appreciated. Thanks in advance, Andrew ==========>Code<========== //-------------------------------------------------------------------- // // Recursive cRemove() function implemented in In-lab Exercise 3 // //-------------------------------------------------------------------- template < class DT > void List
:: cRemove() // Recursively removes all occurrences of the character 'c' from a list // of characters. Moves cursor to the beginning of the list. { cRemoveSub(head); cursor = head; } // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - template < class DT > void List
:: cRemoveSub ( ListNode
*& p ) // Recursive partner to the cRemove() function. { ListNode
* delete_node; ListNode
* prior_node; if ( p == NULL ) { return; } else if ((p->dataItem == 'c' || p->dataItem == 'C') && (p == head)) { delete_node = p; head = p = p->next; delete delete_node; cRemoveSub(p); } else if ((p->dataItem == 'c' || p->dataItem == 'C') && (p->next != 0)) { delete_node = p; p = p->next; The above line changes either 'head' or the 'next' member of a node, because 'p' is a reference to one of those. This means that you have inadvertently taken the node with the 'c' out of the list. prior_node = head; while(prior_node->next->dataItem != 'c' && prior_node->next->dataItem != 'C') { prior_node = prior_node->next; } The reference problem causes this loop to find the the second node with a 'c'. If there isn't one it will just fly off into space. delete delete_node; prior_node->next = p; cRemoveSub(p); } else if (p->next == 0) { delete p; Here you are deleting the tail node whether it has a 'c' or not. p = 0; } else { cout << "Else: " << '[' << p->dataItem << "]->[" << p->next->dataItem << ']' << endl; cRemoveSub(p->next); } } DW Jul 19 '05 #8

 P: n/a Andrew Edwards wrote in message news:jn*********************@twister.southeast.rr. com... "Victor Bazarov" wrote: Sorry, I must have misunderstood. Why do you need recursion, then? Using iteration over recursion is not an option. This must be done with recursion. void List::remove_node(node *n, node *parent) // private member function { if(parent) parent->next = n->next; else m_head = n->next; delete n; } void List::remove_all_with_value(const value_type& val) // public member function { remove_all_with_value_recurse(val, m_head, NULL); } void List::remove_all_with_value_recurse(const value_type& val, node *n, node *parent) // private member function { assert(n != NULL); if(n->next) remove_all_with_value_recurse(n->next, n); if(n->val == val) remove_node(n, parent); } I think this works (I haven't got access to a compiler for a couple of days so checking it is problematic). I've skipped all the usual template stuff to make it easier to understand. HTH, Stuart. Jul 19 '05 #9