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
