Recursive delete problems

**Victor Bazarov** · Jul 19 '05, 03:34 PM

Re: Recursive delete problems

"Andrew Edwards" <edwardsac@spam freeusa.com> wrote...[color=blue]
> 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<DT>:: cRemove()[/color]

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 deleteListTailF irst(ListNode *plistnode)
{
if (plistnode->next != NULL)
deleteListTailF irst(plistnode->next); // recurse

deleteAllDataIn (plistnode); // non-recursive part
}

I recommend scrapping your solution and rewriting it afresh.

Victor

**Alf P. Steinbach** · Jul 19 '05, 03:34 PM

Re: Recursive delete problems

On Sat, 19 Jul 2003 19:57:00 GMT, "Andrew Edwards" <edwardsac@spam freeusa.com> wrote:
[color=blue]
>The following function results in an infinite loop! After 5+ hours of
>debugging, I am still unable to decipher what I am incorrectly.[/color]

The question is then, what exactly are you trying to achieve?

Details do matter.

[color=blue]
> Any assistance is greatly appreciated.
>
>Thanks in advance,
>Andrew
>
>==========>Cod e<==========
>
>//--------------------------------------------------------------------
>//
>// Recursive cRemove() function implemented in In-lab Exercise 3
>//
>//--------------------------------------------------------------------
>
>template < class DT >
>void List<DT>:: cRemove()[/color]

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.

[color=blue]
>// 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;
>}[/color]

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.

[color=blue]
>
>// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
>
>template < class DT >
>void List<DT>:: cRemoveSub ( ListNode<DT>*& p )
>
>// Recursive partner to the cRemove() function.
>
>{
> ListNode<DT>* delete_node;
> ListNode<DT>* prior_node;
>
> if ( p == NULL )
> {
> return;
> }
> else if ((p->dataItem == 'c' || p->dataItem == 'C') && (p == head))[/color]

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.

[color=blue]
> {
> delete_node = p;
> head = p = p->next;[/color]

Such multiple assignments are evil.

[color=blue]
> 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_nod e->next->dataItem != 'c' &&
> prior_node->next->dataItem != 'C')
> {
> prior_node = prior_node->next;
> }[/color]

What's this supposed to accomplish, except an infinite loop?

[color=blue]
> delete delete_node;
> prior_node->next = p;
> cRemoveSub(p);
> }
> else if (p->next == 0)
> {
> delete p;[/color]

And what's the purpose of this?

[color=blue]
> p = 0;
> }
> else
> {
> cout << "Else: " << '[' << p->dataItem
> << "]->[" << p->next->dataItem << ']' << endl;[/color]

This looks like debugging/trace output.

[color=blue]
> cRemoveSub(p->next);[/color]

As a general rule, don't manipulate data structures in debugging code.

[color=blue]
> }
>}[/color]

Here's one way to recursively delete all nodes containing a given
letter (case-independent) in a singly linked zero-terminated list:

char toUpper( char c )
{
return static_cast<cha r>(
std::toupper( static_cast<uns igned char>( c ) )
);
}

void deleteNodes( Node*& pHead, char upperCaseCh )
{
"Store pointer to rest of list in local variable pTail"
if( toUpper( pHead->value ) == upperCaseCh )
{
"Delete the head node"
}
"Recursivel y delete the rest of the list"
}

You should not translate the pseudo-code to more than 4 statements.

In "real" C++ code consider using standard library containers
such as e.g. std::list instead.

**Andrew Edwards** · Jul 19 '05, 03:34 PM

Re: Recursive delete problems

"Alf P. Steinbach" <alfps@start.no > wrote:
[color=blue]
> The question is then, what exactly are you trying to achieve?
>
> Details do matter.
>[/color]

I'm trying to remove all occurrences of the character 'c' from list.

**Andrew Edwards** · Jul 19 '05, 03:34 PM

Re: Recursive delete problems

"Alf P. Steinbach" <alfps@start.no > wrote:
[color=blue]
> 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.
>[/color]

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.
[color=blue]
>
> 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.
>[/color]

Again, the interface is predesigned and cannot be changed.
[color=blue]
> 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.
>[/color]

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.

[color=blue]
> Such multiple assignments are evil.[/color]

Point taken!
[color=blue]
>
> What's this supposed to accomplish, except an infinite loop?
>[/color]

It's supposed to remove the character from the "middle" of the list.
[color=blue]
> And what's the purpose of this?[/color]

Delete the character if it's at the end of the list.

[color=blue]
> This looks like debugging/trace output.[/color]
<snip>[color=blue]
> As a general rule, don't manipulate data structures in debugging code.[/color]

What is the best way to do debugging? I have a text editor and Borland's C++
Builder commandlinetool s v5.5.1. I'm new to programming so my art of
debugging is severely underdeveloped.

**Victor Bazarov** · Jul 19 '05, 03:34 PM

Re: Recursive delete problems

"Andrew Edwards" <edwardsac@spam freeusa.com> wrote...[color=blue]
>
> "Victor Bazarov" <v.Abazarov@att Abi.com> wrote:
>[color=green]
> > Well, without seeing what 'List<>' is I wouldn't dare to recommend
> > anything.[/color]
>
> Here are the two constructors I use:
>
> template < class DT >
> ListNode<DT>:: ListNode ( const DT& initData, ListNode* nextPtr )
> : dataItem(initDa ta)
> , next(nextPtr)
> {
> }
>
> template < class DT >
> List<DT>:: List(int ignored)
> // Constructor. Creates and empty list. The argument is provided
> // for call compatability with the array implementation and is
> // ignored.
> {
> cursor = head = NULL;
> }
>
>[color=green]
> > However, the usual scheme for deleting a singly-linked list is:[/color]
>
> Note that I'm not trying to delete the list. I can do that. I'm trying to
> remove all occurrences of 'c' from the list.[/color]

Sorry, I must have misunderstood. Why do you need recursion, then?
Just traverse the list and extract all the 'c' elements. Here is
pseudocode:

void removeFromList( ListNode* p, ListNode* pprev)
{
if (pprev)
pprev->next = p->next;
delete p;
}

void removeFromListA llThatHave(cons t ValueType& value)
{
while (head && head->getValue() == value) // remove the head
{
ListNode* newhead = head->next;
removeFromList( head, 0);
head = newhead;
}

if (head) // something remains in the list
{
ListNode* p = head;
while (p->next)
{
if (p->next->getValue() == value)
removeFromList( p->next, p);
else
p = p->next;
}
}
}

I think that should do it...

Victor

**Andrew Edwards** · Jul 19 '05, 03:34 PM

Re: Recursive delete problems

"Victor Bazarov" <v.Abazarov@att Abi.com> wrote:
[color=blue]
> Sorry, I must have misunderstood. Why do you need recursion, then?[/color]

Using iteration over recursion is not an option. This must be done with
recursion.

**David White** · Jul 19 '05, 03:34 PM

Re: Recursive delete problems

"Andrew Edwards" <edwardsac@spam freeusa.com> wrote in message
news:gohSa.2539 58$_w.9882522@t wister.southeas t.rr.com...[color=blue]
> 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<DT>:: 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<DT>:: cRemoveSub ( ListNode<DT>*& p )
>
> // Recursive partner to the cRemove() function.
>
> {
> ListNode<DT>* delete_node;
> ListNode<DT>* 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;[/color]

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.
[color=blue]
> prior_node = head;
> while(prior_nod e->next->dataItem != 'c' &&
> prior_node->next->dataItem != 'C')
> {
> prior_node = prior_node->next;
> }[/color]

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.
[color=blue]
> delete delete_node;
> prior_node->next = p;
> cRemoveSub(p);
> }
> else if (p->next == 0)
> {
> delete p;[/color]

Here you are deleting the tail node whether it has a 'c' or not.
[color=blue]
> p = 0;
> }
> else
> {
> cout << "Else: " << '[' << p->dataItem
> << "]->[" << p->next->dataItem << ']' << endl;
> cRemoveSub(p->next);
> }
> }
>[/color]

DW

**Stuart Golodetz** · Jul 19 '05, 03:35 PM

Re: Recursive delete problems

Andrew Edwards <edwardsac@spam freeusa.com> wrote in message
news:jniSa.3135 68$jp.8343317@t wister.southeas t.rr.com...[color=blue]
>
> "Victor Bazarov" <v.Abazarov@att Abi.com> wrote:
>[color=green]
> > Sorry, I must have misunderstood. Why do you need recursion, then?[/color]
>
> Using iteration over recursion is not an option. This must be done with
> recursion.[/color]

void List::remove_no de(node *n, node *parent) // private member
function
{
if(parent) parent->next = n->next;
else m_head = n->next;
delete n;
}

void List::remove_al l_with_value(co nst value_type& val) // public member
function
{
remove_all_with _value_recurse( val, m_head, NULL);
}

void List::remove_al l_with_value_re curse(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.

Recursive delete problems

Recursive delete problems

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment