Solved

Please Help...C++ : How to make a singly linked list print in reverse, recursively

Posted on 2004-04-25
6
312 Views
Last Modified: 2008-02-26
Sorry for posting in this in the wrong forum before...

Hi,

I've succesfully created a Queue with a singly linked list and have no problem with writing a function to print out the result in order, but I need to print out the list in reverse order, preferably recursively.  Here is my code.  Thanks in advance.

struct Node{
  int key;
  Node *next;
};

void printInReverse(Node * Head);   //function prototype to print in reverse

int main(){
  Node *header = new Node;
  header->next = NULL;
  Node *back = header;
 int x;  //variable displaying dequeue value
 
 

  for (int i =1; i < 10 ; i ++){   //loop to populate enqueue

  Node * newPtr = new Node;
  newPtr->key = i;
  newPtr->next = NULL;

  if ((header->next == NULL)&&(back == header))
     {
     ((header == 0) && (back == 0))
     header = back = newPtr;
     header->next = back;
     newPtr = 0;
     }
   
  else if((header->next!=NULL) || (back != header))
     //header = back;
       {
       back->next = newPtr;
       back = newPtr;
       newPtr = 0;
              }
     }
// ******END list population*********

// ******BEGIN dequeue *********
     
Node *tmpPtr = new Node;
     tmpPtr = header;

     if (header == back)
       header = back = 0;  //Queue is empty
     if (header != back)
       header = header->next; // header moves to second position

     x = tmpPtr->key;
     tmpPtr = 0;

// ******END dequeue function psuedocode *********

     //more testing ..................................
     cout << x << "= int x" << endl << endl;
     //END testing ...................................


     */
 
         
  printInReverse(header);   // call function to print list in reverse
     
system("pause");
return 0;
  }
// function currently prints in order, not reverse.  Please Help!

// ******BEGIN function to print in reverse*********
void printInReverse(Node *Head)   // this
  {
  if (Head == 0){
       cout << "List is empty." << endl;
       }
    //int count = 0;
     Node *printPtr = new Node;
     
     printPtr = Head;

     while(printPtr != 0)
       {
       
       cout << printPtr->key << endl;
       printPtr = printPtr->next; //advance pointer to next location in list...
       }
 }


// ******END function to print in reverse*********
0
Comment
Question by:r3r
  • 3
  • 2
6 Comments
 
LVL 5

Accepted Solution

by:
dennis_george earned 500 total points
ID: 10915620
Hi,

You are simply printing the data.... you should recursion

I think the following will do it for you..

void printInReverse(Node *Head)   // this
{
      if ( Head == NULL )
      {
            return ;
      } else {
            printInReverse( Head->next ) ;
      }

      printf(" %d  ::", Head->key) ;
}

Dennis
0
 

Author Comment

by:r3r
ID: 10915704
Thanks man, that's awesome.  Works great.  One more question...
Can you explain the last line..

printf(" %d  ::", Head->key) ;

specifically the " %d " part.  The Head->key argument is obvious.  I'm really new to this stuff (like you didn't know that already!!)

Thanks again.. you get 500 big ones!
0
 
LVL 5

Expert Comment

by:dennis_george
ID: 10915716
I think there is many programatic and logical flaw in your code.... I corrected those ... please read the comments I have written in between the code.....

Note :: Never never jump into coding before you design what you want to do.... First take a pen and paper draw diagrams and/or rough algo so that you are clear what and how will you acheive your goal.....

e.g.

Head ---->[]-->[]-->[]-->[]-->[]-->[]-->NULL

Now you want to print it reverse way.....
So check how will you do.... to print it reverse First you have to go at the end then go back....
So devise a method that how will you go at the end and also how will you come back......

Making a software or a program is not how you code but rather how you design and how you provide the solution.

//////////////////////// Your code ///////////////////////////////////////////
struct Node{
  int key;
  Node *next;
};

void printInReverse(Node * Head);   //function prototype to print in reverse

int main()
{
//  Node *header = new Node; // It should not be assigned memory at this stage
      Node *header = NULL;
//  header->next = NULL;
   Node *back = NULL ;
 
//  int x;  //variable displaying dequeue value
 
  for (int i = 1; i < 10 ; i ++){   //loop to populate enqueue
 
        Node * newPtr = new Node;
        newPtr->key = i;
        newPtr->next = NULL;

        if( header == NULL) {              
              header = back = newPtr;       
        } else {              
              back->next = newPtr;
              back = newPtr;
              newPtr = NULL;
        }
  }

// ******END list population*********

// ******BEGIN dequeue *********
     

//  Node *tmpPtr = new Node;  // Never Do this :: Here you are allocating memory for tmpPtr
//  tmpPtr = header;  // And here you are pointing your tmpPtr to header
                              // And Hence earlier memory allocated for tmpPtr is lost...
                              // i.e you cannot free that memory (Memory Leak)

//   Node *tmpPtr = header ;

//     if (header == back)
//       header = back = 0;  //Queue is empty
//     if (header != back)
//       header = header->next; // header moves to second position

//     x = tmpPtr->key;
//     tmpPtr = 0;

// ******END dequeue function psuedocode *********

     //more testing ..................................
//     cout << x << "= int x" << endl << endl;
     //END testing ...................................


         
  printInReverse(header);   // call function to print list in reverse
  printf("\n") ;

  system("pause") ;
 
  return 0;
}
// function currently prints in order, not reverse.  Please Help!

// ******BEGIN function to print in reverse*********

void printInReverse(Node *Head)   // this
{
      if ( Head == NULL )
      {
            return ;
      } else {
            printInReverse( Head->next ) ;
      }

      printf(" %d  ::", Head->key) ;
}


Dennis
0
Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

 
LVL 5

Expert Comment

by:dennis_george
ID: 10915731
Hi,

printf(" %d  ::", Head->key) ;

is similar to

cout << Head->key ;

printf is a function defined in stdio.h // used in C
and cout is used in c++ // defined in iostream.h

Dennis
0
 

Author Comment

by:r3r
ID: 10915775
Thanks again...some of the code was preformated and I couldn't change it, but I don't doubt there is a lot of sloppy logic going on...  I'll study your notes and corrections.  And yes, I have been having problems with memory leaks as well.  
0
 
LVL 12

Expert Comment

by:stefan73
ID: 10916296
Hi r3r,
> print out the list in reverse order, preferably recursively
Smells like what one would do in functional programming :-)

Be aware that the length of a list you can print this way is very limited, since your recursive function needs stack for each recursion.
recursion.

Cheers,
Stefan
0

Featured Post

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In days of old, returning something by value from a function in C++ was necessarily avoided because it would, invariably, involve one or even two copies of the object being created and potentially costly calls to a copy-constructor and destructor. A…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

820 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question