We help IT Professionals succeed at work.

Recursive call on linked list

windyw
windyw asked
on
238 Views
Last Modified: 2012-05-04
Hi,

The problem Im having is that I need to traverse a linked list of integer data and total all data in the list and store it in a  node on the same list. Ive been working at this for awhile now and am at a loss.

I have know trouble doing this if Im using a separate int varible to store the total from the list.

Any help would be appreciated!

Here's the code that Ive done so far:

void Add(ptr* LList)
{
   Curr = LList;
   ptr* Total;
   Total = new data;

    if(Curr != NULL)
    {
       Total->data = Curr->data;
       Add(Curr->Next);
     }

   cout << Total->Data;
}

Thanks,

windyw
Comment
Watch Question

Commented:
one way you could do this is like this:

typedef struct  {
int val;
int total;
mystuff  *next;
mystuff   *prev;
} mystuff;

mystuff  *list;

inside the program,

while (list!=NULL)
{
   if (list->prev!=NULL)
   {
      list->total=list->prev->val;    /* Not first node */
      /* add another node here,  */
   }
   else  
   {
       list->total=list->val;  /* first node  */
      /* add node here */
   }

}

Commented:
This part should be:

  if (list->prev!=NULL)
       {
          list->total=list->prev->val + list->prev->total;    /* Not first node */
          /* add another node here,  */

       }


NOT:
  if (list->prev!=NULL)
       {
          list->total=list->prev->val;    /* Not first node */
          /* add another node here,  */
       }

Author

Commented:
It does need to be a recursive call!

Commented:
Since this is for an assignment we cannot provide a complete solution.  To do so would be a violation of the customer service agreement we all agreed to.   But we can provide help.  We can answer SPECIFIC questions.  We can look at your work and ofter reasonable suggestions.  

Commented:
You first problem is that a recursive design often involves 2 functions and you have only one (Add())  You need two functions.  The first function is the one that "starts the ball rolling".  It is not recursive.   it calls the 2nd function, which is recursive,  to perform a task (like calculate the total) and then when recursion stops, execution returns to the first function so it can use the result.  

Second problem: the recursive function must operate on a node in the list.  It will be passed a node (pointer) and will calculate the total of that node and all the nodes after it.

Third problem.  The recursive function must return a value.  In this case the value will be the total of the nodes in the list from the node it was called for to the end..

Does this get you started?

Author

Commented:
Adjusted points to 100

Commented:
Do you have any questions or do you have some code to post that we can look at?

Author

Commented:
Ive been trying to accomplish this own my own for some time now without success and Iam not wanting any one to do this for me. Iam simply wanting a suggested approach to solving the problem.
Commented:
Unlock this solution and get a sample of our free trial.
(No credit card required)
UNLOCK SOLUTION

Commented:
rbr, this is for an assigment!!!!  You can be removed from EE for unethical behavior.  Think before you answer.

windyw, the recursive solution rbr presents is really not the best way.  You are better of using two functions, one of which is recursive and does the calculation. and the other which prints the results..  You can then return values usign the regular "return" statement rather than having to pass them back with a pointer.
Unlock the solution to this question.
Thanks for using Experts Exchange.

Please provide your email to receive a sample view!

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.