My reverse_list function does not work at all.

Hi there,

I created a reverse_list function but it does not work at all. I already spent hours on it, trying to figure out the problem, but still. I am using Dev-C++. here is part of the program (sorry, it is a little long!). Any help will be really appreciated. Thanks again!

Code:

#include<stdlib.h>
#include<iostream>




using std::cin;
using std::cout;
using std::endl;


 #include "linkedList.h"    // header file 
#include "listException.h"
 
#include "ListIndexOutOfRangeException.h"
 
 
#ifndef LIST_H
#define LIST_H




using namespace std;




 
List::List():size(0),head(NULL)
 {
 }
 
List::List(const List& aList)
   : size(aList.size)
 {
   if (aList.head == NULL)
       head = NULL;  // original list is empty
 
  else
   {  // copy first node
       head = new ListNode;
       head->item = aList.head->item;
 
      // copy rest of list
       ListNode *newPtr = head;  // new list pointer
       // newPtr points to last node in new list
       // origPtr points to nodes in original list
       for (ListNode *origPtr = aList.head->next;
   origPtr != NULL;
   origPtr = origPtr->next)
       {  newPtr->next = new ListNode;
         newPtr = newPtr->next;
 newPtr->item = origPtr->item;
       }  // end for
 
      newPtr->next = NULL;
   }  // end if
 }  // end copy constructor
 
List::~List()
 {
   while (!isEmpty())
       remove(1);
 }  // end destructor
 


const List& List:: operator = (const List& rhs)
{
    
}


 
bool List::isEmpty() const
 {
   return size == 0;
 }  // end isEmpty
 
int List::getLength(int size) const
 {
   return size;
 }  // end getLength
 
List::ListNode *List::find(int index) const
 {
   if ( (index < 1) || (index > getLength(size)) )
       return NULL;
 
  else  // count from the beginning of the list.
   {  ListNode *cur = head;
       for (int skip = 1; skip < index; ++skip)
         cur = cur->next;
       return cur;
   }  // end if
 }  // end find
 
void List::retrieve(int index,
                     ListItemType& dataItem) const
   throw(ListIndexOutOfRangeException)
 {
   if ( (index < 1) || (index > getLength(size)) )
       throw ListIndexOutOfRangeException(
 "ListIndexOutOfRangeException: retrieve index out of range");
   else
   {  // get pointer to node, then data in node
       ListNode *cur = find(index);
       dataItem = cur->item;
   }  // end if
 }  // end retrieve
 


 
void List::insert(int index, const ListItemType& newItem)
   throw(ListIndexOutOfRangeException, ListException)
 {
   int newLength = getLength(size) + 1;
 
  if ( (index < 1) || (index > newLength) )
       throw ListIndexOutOfRangeException(
 "ListIndexOutOfRangeException: insert index out of range");
   else
   {  // try to create new node and place newItem in it
       try
       {
 ListNode *newPtr = new ListNode;
 size = newLength;
 newPtr->item = newItem;
 
// attach new node to list
 if (index == 1)
 {  // insert new node at beginning of list
     newPtr->next = head;
     head = newPtr;
 }
 else
 {  ListNode *prev = find(index-1);
             // insert new node after node
             // to which prev points
             newPtr->next = prev->next;
     prev->next = newPtr;
 }  // end if
       }  // end try
       catch (bad_alloc e)
       {
 throw ListException(
     "ListException: memory allocation failed on insert");
       }  // end catch
   }  // end if
 
 
 }  // end insert
 
void List::remove(int index) throw(ListIndexOutOfRangeException)
 {
   ListNode *cur;
 
  if ( (index < 1) || (index > getLength(size)))
       throw ListIndexOutOfRangeException(
 "ListIndexOutOfRangeException: remove index out of range");
   else
   {  --size;
       if (index == 1)
       {  // delete the first node from the list
         cur = head;  // save pointer to node
         head = head->next;
       }
 
      else
       {  ListNode *prev = find(index - 1);
         // delete the node after the node to which prev points
         cur = prev->next;  // save pointer to node
         prev->next = cur->next;
       }  // end if
 
      // return node to system
       cur->next = NULL;
       delete cur;
       cur = NULL;
   }  // end if
 }  // end remove
 
 
                                    
 void List::print_list()
 {
    ListNode *cur; ListNode *reverse; 
    for(cur=head; cur!=NULL;cur=cur->next)
    
    cout<<"  "<<cur->item<<endl;  
    print_list_reverse(head);
    reverse_list(head);
    
    
 }
  
 List::ListNode *List::print_list_reverse(ListNode *head)
   {
      ListNode *cur;
      if(head->next==NULL)//if there is only one item...
       {cur=head;    //the curent pointer points on it and...
        cout<<" cur=head  "<<cur->item<<endl;  //the item is displayed
       }   
       else if(head->next!=NULL)  //otherwise if there are more than one item...
       {
          cur=print_list_reverse(head->next); //current pointer gets the memory address the next item
          head->next->next=head;   
          cout<<" cur=head! "<<head->item<<endl;  //display the current item
       }
      
  }  
   
List::ListNode *List::reverse_list(ListNode *head)
 {  
    ListNode *a=NULL;
    ListNode *b=NULL;
    ListNode *c=NULL;
  
    a=head, b=NULL;
    
    while(a!=NULL)
    {
      c=b, b=a, a=a->next;
      b->next=c;       
    }
    head=b;
}


int main()
{       
         
    List l;
    int index1=1;  int size1; int item;
    cout<<"how many items do you want to enter?"<<endl;
    cin>>size1;
if (size1>0)
 {  
    do
    {
       cout<<"now, enter your  item "<<endl;
       cin>>item;
       l.insert(index1, item);
       index1++;
    }
   while(index1<=size1);
   
    cout<<"display all items "<<endl;
  l.print_list();
    
 
 }
 else
       cout<<"good Bye!"<<endl;
    
   return 0; 
}


 #endif

Rather than trying to be clever with pointers, why not write reverse in terms of remove() and insert()

Remove the tail element of the old list, and insert it at the head of the new list.

Originally Posted by Salem

Rather than trying to be clever with pointers, why not write reverse in terms of remove() and insert()

Remove the tail element of the old list, and insert it at the head of the new list.

You mean remove the head element and insert it as the head element of the new list.

This mimics the classic push and pop way of doing it:

Code:

while (!oldList.Empty())
   newList.push(oldList.pop());
swap(newList, oldList);

There, that's actual code that will reverse a list in 3 lines of code, provided the extremely simple push, pop, and swap methods are provided. I highly recommend implementing those, in fact IMHO they are a far higher priority than any insert or remove methods, which arguably shouldn't even be part of a linked-list container.

Except they're implementing list, not stack.

My professor wants us to use only pointers for this HW. I cannot use another method besides the one she wants.

Originally Posted by T4000

My professor wants us to use only pointers for this HW. I cannot use another method besides the one she wants.

That's fine. Use pointers (and in fact it is hard to do without them at some level) for the underlying functions which you then use to implement reverse_list.