Thread: My reverse_list function does not work at all.

  1. #1
    Registered User
    Join Date
    Oct 2011
    Posts
    2

    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
    Last edited by T4000; 10-26-2011 at 09:07 PM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Salem View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Except they're implementing list, not stack.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    Oct 2011
    Posts
    2
    My professor wants us to use only pointers for this HW. I cannot use another method besides the one she wants.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote 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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How does this function work?
    By TheWhiffet in forum C Programming
    Replies: 3
    Last Post: 05-10-2011, 07:55 AM
  2. oh, no! my function won't work.
    By student0806 in forum C Programming
    Replies: 5
    Last Post: 09-27-2010, 06:15 PM
  3. cant get my function to work!
    By scaven in forum C Programming
    Replies: 3
    Last Post: 05-08-2003, 03:08 PM
  4. my function doesn't work! it should work
    By Unregistered in forum C Programming
    Replies: 13
    Last Post: 05-02-2002, 02:53 PM
  5. Trying to work with Cin Function
    By ProgrammingDlux in forum C++ Programming
    Replies: 14
    Last Post: 01-24-2002, 03:43 PM

Tags for this Thread