7 Replies - 804 Views - Last Post: 14 October 2012 - 03:56 PM Rate Topic: -----

#1 BenedictRM  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 24-August 12

Pop function causing program to crash

Posted 12 October 2012 - 02:36 PM

Hey all,
So I am working on a circular queue as a linked list implementation and I am having some trouble getting my pop function to function with out causing my test program to crash. It is possible that my rear_ptr for the list is not maintaining the location of the front of the list, but from what I can tell it is. Here is the code giving me trouble, I have included the three functions (push, pop, and front) being utilized in the test program I included as well:

//Function to view data at front of list
    template <class Item>
    Item queue<Item>::front( ) const
    // Library facilities used: cassert
    {
        assert(!empty( ));
                          
        return rear_ptr -> data( );
    }
    
    //Function to pop items from front of list
    template <class Item>
    void queue<Item>::pop( )
    // Library facilities used: cassert, node2.h
    {
        assert(!empty( ));	            
               
        //New temporary node to delete queue node after pop
        node <Item>* delete_ptr;
        delete_ptr = rear_ptr -> link();
        
        //Deleting from a single node queue
        if (count <= 1)
        {
             //Rear_ptr is now null because linked list's final node will be deleted
             rear_ptr = NULL;            
        }
        
            else
            {
                 rear_ptr = rear_ptr ->link();
            }
        
        delete delete_ptr;
        count--;                       
    }
    
    //Function to push items to rear of queue
    template <class Item>
    void queue<Item>::push(const Item& entry)
    // Library facilities used: node2.h
    {
        //New pointer to hold first position in queue
        node <Item>* frnt_position;
        
        if (empty( ))
        {   // Insert first entry using rear pointer
            list_head_insert(rear_ptr, entry);
            frnt_position = rear_ptr;          
        }
            
            else
            {   // Insert an entry that is not the first.
                node<Item> *temp;
                temp = new node<Item> (entry, rear_ptr -> link());
                
            }
        
        //Set rear pointer so now it should point to new node which points to first item in list
        rear_ptr -> set_link(frnt_position); 
        
        ++count;
    }


Test Prog:
#include "queue3.h"    // Provides the circular linked-list queue
#include <iostream>
#include <fstream>
#include <string>

using namespace std;
using namespace main_savitch_6B;
int main(int argc, char *argv[])

// Create a queue and add some values to it
    queue<string> testQueue1;      
    testQueue1.push("Testing...");
    testQueue1.push("One...");
    testQueue1.push("Two...");
    testQueue1.push("Three...");
    testQueue1.push("Four...");
    // Demonstrate the the size function works
    cout << "\nNumber of items in first Queue: " << testQueue1.size() << endl;  
    // Demonstrate the copy constructor
    queue<string> testQueue2(testQueue1);
    cout << "Number of items in copied Queue: " << testQueue2.size() << endl; 
    
    // Exercise front, pop and empty
    cout << "\nValues in first queue: " << endl;
    
    while(!testQueue1.empty())
    {
        cout << testQueue1.front();
        testQueue1.pop();
    }
    cout << endl;
 cout << "*************************************"<< endl;
    cout << "End of Homework Seven Solution" << endl;
    cout << "*************************************" << endl;
    system("Pause");
}


The program crashes at the while loop:
while(!testQueue1.empty())
    {
        cout << testQueue1.front();
        testQueue1.pop();
    }


Any recommendations on how to get this working are appreciated, thanks!

Is This A Good Question/Topic? 0
  • +

Replies To: Pop function causing program to crash

#2 jimblumberg  Icon User is online

  • member icon


Reputation: 4232
  • View blog
  • Posts: 13,297
  • Joined: 25-December 09

Re: Pop function causing program to crash

Posted 12 October 2012 - 02:53 PM

First I don't recommend using the "using namespace std;" clause since you seem to be using your own queue class instead of std::queue.

Next I suggest you run this program through your debugger, it will show you exactly where it detects the error and allow you to view the variables at the time of the crash. And then you should be able to back trace the problem.

Jim
Was This Post Helpful? 0
  • +
  • -

#3 BenedictRM  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 24-August 12

Re: Pop function causing program to crash

Posted 12 October 2012 - 03:44 PM

I don't really have a choice with the namespace std, that's just a grading program I need to use to check my answer to the assignment. When I debug my code, it prompts a window saying "your project does not have debugging information, do you want to enable debugging and rebuild your project?" No matter how often I click 'yes' it keeps prompting the same message, so I can't use the debugger it seems. Is there a fix to this?
Was This Post Helpful? 0
  • +
  • -

#4 jimblumberg  Icon User is online

  • member icon


Reputation: 4232
  • View blog
  • Posts: 13,297
  • Joined: 25-December 09

Re: Pop function causing program to crash

Posted 12 October 2012 - 04:15 PM

What compiler and version are you using? How did you create your project? How are you compiling your program?

Jim
Was This Post Helpful? 0
  • +
  • -

#5 BenedictRM  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 24-August 12

Re: Pop function causing program to crash

Posted 12 October 2012 - 09:12 PM

It's Dev C++ vers. 4.9.9.2, it's a console application project, and I compile the the whole project at once (not sure exactly what you mean by how I compile it), I just go to the Execute tab, and compile.
Was This Post Helpful? 0
  • +
  • -

#6 BenedictRM  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 24-August 12

Re: Pop function causing program to crash

Posted 14 October 2012 - 01:57 PM

Ok, I've asked around and for future reference to anyone reading this, basically the debugger in Dev C++ vers. 4.9.9.2 has a really hard time debugging templates. Normally I would have done this project as an ordinary cxx file then converted it to a template, but my project called for converting the already built template.
Was This Post Helpful? 0
  • +
  • -

#7 BenedictRM  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 24-August 12

Re: Pop function causing program to crash

Posted 14 October 2012 - 03:09 PM

Hey all, so I've been working all week on a project to convert a linear linked list as a queue to a circular linked list. I can't seem to figure out why my program keeps crashing when the test program calls my function for pop(). From what I can tell, only pop is causing a crash, but it is also possible I got something mixed up in my copy constructor as well. And help is greatly appreciated (code below). Also I can't change the test program, that is an assigned program to test the queue class.

Queue Header
#ifndef MAIN_SAVITCH_QUEUE3_H     // Prevent duplicate definition
#define MAIN_SAVITCH_QUEUE3_H
#include <cstdlib>   // Provides std::size_t
#include "node2.h"   // Node template class

namespace main_savitch_6B
{
    template <class Item>
    class queue
    {
        public:
              // TYPEDEFS 
              typedef std::size_t size_type;
              typedef Item value_type;
              // CONSTRUCTORS and DESTRUCTOR
              queue( );
    	      queue(const queue<Item>& source);
    	      ~queue( );
              // MODIFICATION MEMBER FUNCTIONS
              void pop( );
              void push(const Item& entry);
    	      void operator =(const queue<Item>& source);
              // CONSTANT MEMBER FUNCTIONS
              bool empty( ) const { return (count == 0); }
    	      size_type size( ) const {return count;}
              Item front( ) const;
        private:
              main_savitch_6B::node<Item> *rear_ptr; //Rear ptr that simultaniously points to the rear and head pointers
              size_type count; // Total number of items in the queue
    };
}
#include "queue3.template" // Include the implementation     
#endif


Queue Template
// TEMPLATE CLASS IMPLEMENTED: Queue<Item> (see queue3.h for documentation)
// This file is included in the header file, and not compiled separately.
// INVARIANT for the Queue class:
//   1. The items in the queue are stored in a linked list, with the front of
//      the queue stored at the final node which links to the front node circularly, 
//      and the rear of the queue stored at the rear node.
//      
//   2. The member variable rear_ptr is the head pointer of the linked list of
//      items and links circulary to the final node as well. For an empty list, we don't care
//      what's stored in rear_ptr.

#include <cassert>   // Provides assert
#include "node2.h"   // Node template class

namespace main_savitch_6B
{
    //Default constructor
    template <class Item>
    queue<Item>::queue( )
    {      
        rear_ptr = NULL;
        count = 0;
    }
       
    //Copy Constructor
    template <class Item>
    queue<Item>::queue(const queue<Item>& source)
    // Library facilities used: node2.h
	{
        //Counter to keep track of copied items
        int counter = 0;
        
        if (this == &source) // Handle self-assignment
        {    
            return;
        }    
        
             if (empty())
             {
                  return;
             }     
                  
                  else
                  {                                         
                       //Create from_ptr to point to first item in source queue
                       main_savitch_6B::node<Item>* from_ptr = source.rear_ptr->link(); 
     	               
  	                   //Create a node with a pointer to start copying data from source queue
  	                   //Setting new node's link field to NULL as data can't be added until more nodes are created
                       rear_ptr = new node<Item>(from_ptr->data(), NULL); 
                      
                       //New pointer to hold first position in list so we know when we can terminate copying source queue
  	                   main_savitch_6B::node <Item>* frnt_position = rear_ptr;
                       	                   
  	                   //Copy data one at a time inserting at rear
  	                   do
  	                   {
                              //Create a new node with next data value and temporarily link to NULL pointer
                              main_savitch_6B::node<Item>* temp = new node<Item>(from_ptr->data(), NULL);         
                         
                              //Link rear_ptr node to new temp node address
                              rear_ptr = new node<Item>(from_ptr->data(), temp);
                         
                              //Update rear_ptr to point to node that has been added
                              rear_ptr = temp;
                          
                              //Advance the counter by one
                              ++counter;
                         
                                   //Check if we are at end of list to prevent queue underflow error, move front ptr forward in link()
                                   if(counter != source.size())
                                   {
                                       from_ptr -> link();
                                   }
                             
                                        //At end of source queue, set rear_ptr to frnt_position to make queue circular
                                        else
                                        {
                                             rear_ptr -> set_link(frnt_position);    
                                        }
                              
                       } while (counter != source.size());                      
                       
                       count = source.count;
                  }              
    }
    
    //Destructor
    template <class Item>
    queue<Item>::~queue( )
    {
        //New pointer to hold current position in list
        main_savitch_6B::node <Item> *position = rear_ptr -> link();
                
        while (rear_ptr != position)
        {
             //Pointer to delete nodes
             main_savitch_6B::node<Item> *remove_ptr;
             
             remove_ptr = rear_ptr;
	         rear_ptr = rear_ptr -> link();
	         delete remove_ptr;            
        }     
    }

    //Overloaded comparisson operator
    template <class Item>
    void queue<Item>::operator =(const queue<Item>& source)
    // Library facilities used: node2.h
    {
        int counter = 0;
        
        if (this == &source) // Handle self-assignment
        {    
            return;
        }    
        
             if (empty())
             {
                  return;
             }     
                  else
                  {                                         
                        //Create from_ptr to point to first item in source queue
                       main_savitch_6B::node<Item>* from_ptr = source.rear_ptr->link(); 
     	               
  	                   //Create a node with a pointer to start copying data from source queue
  	                   //Setting new node's link field to NULL as data can't be added until more nodes are created
                       rear_ptr = new node<Item>(from_ptr->data(), NULL); 
                      
                       //New pointer to hold first position in list so we know when we can terminate copying source queue
  	                   main_savitch_6B::node <Item>* frnt_position = rear_ptr;
                       	                   
  	                   //Copy data one at a time inserting at rear
  	                   do
  	                   {
                              //Create a new node with next data value and temporarily link to NULL pointer
                              main_savitch_6B::node<Item>* temp = new node<Item>(from_ptr->data(), NULL);         
                         
                              //Link rear_ptr node to new temp node address
                              rear_ptr = new node<Item>(from_ptr->data(), temp);
                         
                              //Update rear_ptr to point to node that has been added
                              rear_ptr = temp;
                          
                              //Advance the counter by one
                              ++counter;
                         
                                   //Check if we are at end of list to prevent queue underflow error, move front ptr forward in link()
                                   if(counter != source.size())
                                   {
                                       from_ptr -> link();
                                   }
                             
                                        //At end of source queue, set rear_ptr to frnt_position to make queue circular
                                        else
                                        {
                                             rear_ptr -> set_link(frnt_position);    
                                        }
                              
                       } while (counter != source.size());                      
                       
                       count = source.count;
                  }              
    }
    
    //Function to view data at front of list
    template <class Item>
    Item queue<Item>::front( ) const
    // Library facilities used: cassert
    {
        assert(!empty( ));                         
        
        //Create from_ptr to point to first item in queue
        main_savitch_6B::node<Item>* from_ptr = rear_ptr->link();
               
        return from_ptr -> data( );
    }
   
    //Function to pop items from front of list
    template <class Item>
    void queue<Item>::pop( )
    // Library facilities used: cassert, node2.h
    {
        assert(!empty( ));	            
        
        //New temporary node to delete queue node after pop
        main_savitch_6B::node<Item>* delete_ptr = rear_ptr -> link(); 
                       
        //Deleting from a single node queue
        if (delete_ptr -> link() == rear_ptr)
        {
             //Rear_ptr is now null because linked list's final node will be deleted
             rear_ptr = NULL;            
        }
        
            else
            {                
                 //Setting rear_ptr to front of list
                 rear_ptr = rear_ptr -> link();
            }
        //delete popped node
        delete delete_ptr;
        
        --count;                       
    }
        
    //Function to push items to rear of queue
    template <class Item>
    void queue<Item>::push(const Item& entry)
    // Library facilities used: node2.h
    {                                    
        //New pointer to hold first position in queue
        main_savitch_6B::node <Item>* frnt_position;
        
        if (empty( ))
        {                         
            // Insert first entry using rear pointer                                    
            list_head_insert(rear_ptr, entry);                                                       
                                                            
            //Setting frnt_position to what should be the front node                       
            frnt_position = new node<Item> (entry, rear_ptr);                                                               
        }
            
            else 
            {                  
                // Insert an entry that is not the first.
                main_savitch_6B::node<Item> *temp;
                temp = new node<Item> (entry, rear_ptr -> link());                                                                      
                
                //Link rear_ptr node to new temp node address
                rear_ptr = new node<Item>(entry, temp);
                
                //Update rear_ptr to point to node that has been added
                rear_ptr = temp;                         
            }
        
        //Set rear pointer so now it should point to first item in list keeping queue circular
        rear_ptr -> set_link(frnt_position);       
                
        ++count;                       
    }

}//End of implementation


Node header
#ifndef MAIN_SAVITCH_NODE2_H  
#define MAIN_SAVITCH_NODE2_H
#include <cstdlib>   // Provides NULL and size_t
#include <iterator>  // Provides iterator and forward_iterator_tag

namespace main_savitch_6B
{
    template <class Item>
    class node
    {
    public:
        // TYPEDEF
        typedef Item value_type;
        // CONSTRUCTOR
        node(const Item& init_data=Item( ), node* init_link=NULL)
            { data_field = init_data; link_field = init_link; }
        // MODIFICATION MEMBER FUNCTIONS
        Item& data( ) { return data_field; }
        node* link( ) { return link_field; }
        void set_data(const Item& new_data) { data_field = new_data; }
        void set_link(node* new_link) { link_field = new_link; }
        // CONST MEMBER FUNCTIONS
        const Item& data( ) const { return data_field; }
        const node* link( ) const { return link_field; }
    private:
        Item data_field;
        node *link_field;
    };

    // FUNCTIONS to manipulate a linked list:
    template <class Item>
    void list_clear(node<Item>*& head_ptr);

    template <class Item>
    void list_copy
        (const node<Item>* source_ptr, node<Item>*& head_ptr, node<Item>*& tail_ptr);

    template <class Item>
    void list_head_insert(node<Item>*& head_ptr, const Item& entry); 

    template <class Item>
    void list_head_remove(node<Item>*& head_ptr);

    template <class Item>
    void list_insert(node<Item>* previous_ptr, const Item& entry);
 
    template <class Item>
	std::size_t list_length(const node<Item>* head_ptr);

    template <class NodePtr, class SizeType>
    NodePtr list_locate(NodePtr head_ptr, SizeType position);

    template <class Item>
    void list_remove(node<Item>* previous_ptr);
   
    template <class NodePtr, class Item>
    NodePtr list_search(NodePtr head_ptr, const Item& target);

    // FORWARD ITERATORS to step through the nodes of a linked list
    // A node_iterator of can change the underlying linked list through the
    // * operator, so it may not be used with a const node. The
    // node_const_iterator cannot change the underlying linked list
    // through the * operator, so it may be used with a const node.
    // WARNING:
    // This classes use std::iterator as its base class;
    // Older compilers that do not support the std::iterator class can
    // delete everything after the word iterator in the second line:

    template <class Item>
    class node_iterator
    : public std::iterator<std::forward_iterator_tag, Item>
    {
    public:
    	node_iterator(node<Item>* initial = NULL)
	    { current = initial; }
	Item& operator *( ) const
	    { return current->data( ); }
	node_iterator& operator ++( ) // Prefix ++
	    { 
		current = current->link( );
		return *this;
	    }
	node_iterator operator ++(int) // Postfix ++
	    {
		node_iterator original(current);
		current = current->link( );
		return original;      	  
	    }
	bool operator ==(const node_iterator other) const
	    { return current == other.current; }
	bool operator !=(const node_iterator other) const
	    { return current != other.current; }
    private:
	node<Item>* current;
    };

    template <class Item>
    class const_node_iterator
    : public std::iterator<std::forward_iterator_tag, const Item>
    {
    public:
    	const_node_iterator(const node<Item>* initial = NULL)
	    { current = initial; }
	const Item& operator *( ) const
	    { return current->data( ); }
	const_node_iterator& operator ++( ) // Prefix ++
	    {
		current = current->link( );
		return *this;
	    }
	const_node_iterator operator ++(int) // Postfix ++
	    {
		const_node_iterator original(current);
		current = current->link( );
		return original;
	    }
	bool operator ==(const const_node_iterator other) const
	    { return current == other.current; }
	bool operator !=(const const_node_iterator other) const
	    { return current != other.current; }
    private:
	const node<Item>* current;
    };

}

#include "node2.template"
#endif


Node Template
// IMPLEMENTS: The functions of the node template class and the
// linked list toolkit (see node2.h for documentation).
//
// NOTE:
//   Since node is a template class, this file is included in node2.h.
//   Therefore, we should not put any using directives in this file.
//
// INVARIANT for the node class:
//   The data of a node is stored in data_field, and the link in link_field.

#include <cassert>    // Provides assert
#include <cstdlib>    // Provides NULL and size_t

namespace main_savitch_6B
{
    template <class Item>
    void list_clear(node<Item>*& head_ptr)
    // Library facilities used: cstdlib
    {
	while (head_ptr != NULL)
	    list_head_remove(head_ptr);
    }


    template <class Item>
    void list_copy(const node<Item>* source_ptr, node<Item>*& head_ptr, node<Item>*& tail_ptr) 
    // Library facilities used: cstdlib
    {
	head_ptr = NULL;
	tail_ptr = NULL;

	// Handle the case of the empty list
	if (source_ptr == NULL)
	    return;	

	// Make the head node for the newly created list, and put data in it
	list_head_insert(head_ptr, source_ptr->data( ));
	tail_ptr = head_ptr; 
	
	// Copy rest of the nodes one at a time, adding at the tail of new list
       source_ptr = source_ptr->link( ); 
        while (source_ptr != NULL)
	{
	    list_insert(tail_ptr, source_ptr->data( ));
	    tail_ptr = tail_ptr->link( );
	    source_ptr = source_ptr->link( );
	}
    }
 
    
    template <class Item>
    void list_head_insert(node<Item>*& head_ptr, const Item& entry)
    {
	head_ptr = new node<Item>(entry, head_ptr);
    }


    template <class Item>
    void list_head_remove(node<Item>*& head_ptr)
    {
	node<Item> *remove_ptr;

	remove_ptr = head_ptr;
	head_ptr = head_ptr->link( );
	delete remove_ptr;
    }


    template <class Item>
    void list_insert(node<Item>* previous_ptr, const Item& entry) 
    {
	node<Item> *insert_ptr;
    
	insert_ptr = new node<Item>(entry, previous_ptr->link( ));
	previous_ptr->set_link(insert_ptr);
    }


    template <class Item>
    std::size_t list_length(const node<Item>* head_ptr)
    // Library facilities used: cstdlib
    {
	const node<Item> *cursor;
	std::size_t answer;
	
	answer = 0;
	for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
	    ++answer;
	
	return answer;
    }


    template <class NodePtr, class SizeType>
    NodePtr list_locate(NodePtr head_ptr, SizeType position) 
    // Library facilities used: cassert, cstdlib
    {
	NodePtr cursor;
	SizeType i;
    
	assert(0 < position);
	cursor = head_ptr;
	for (i = 1; (i < position) && (cursor != NULL); ++i)
	    cursor = cursor->link( );
	return cursor;
    }


    template <class Item>
    void list_remove(node<Item>* previous_ptr)
    {
	node<Item> *remove_ptr;

	remove_ptr = previous_ptr->link( );
	previous_ptr->set_link(remove_ptr->link( ));
	delete remove_ptr;
    }


    template <class NodePtr, class Item>
    NodePtr list_search(NodePtr head_ptr, const Item& target) 
    // Library facilities used: cstdlib
    {
	NodePtr cursor;
	
	for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
	    if (target == cursor->data( ))
		return cursor;
	return NULL;
    }
}


Test Program:
#include "queue3.h"    // Provides the circular linked-list queue
#include <iostream>
#include <fstream>
#include <string>

using namespace std;
using namespace main_savitch_6B;
int main(int argc, char *argv[])
{
    cout << "*************************************";
    cout << "\nCSC-161 Homework Seven Solution\n";
    cout << "*************************************";
    
    // Create a queue and add some values to it
    queue<string> testQueue1;      
    testQueue1.push("Testing...");     
    testQueue1.push("One...");   
    testQueue1.push("Two...");   
    testQueue1.push("Three..."); 
    testQueue1.push("Four...");
    
    
    // Demonstrate the the size function works
    cout << "\nNumber of items in first Queue: " << testQueue1.size() << endl;  
    // Demonstrate the copy constructor
    queue<string> testQueue2(testQueue1);
    cout << "Number of items in copied Queue: " << testQueue2.size() << endl; 
    cout<< testQueue2.front()<<endl;
    // Exercise front, pop and empty
    cout << "\nValues in first queue: " << endl;
    
    while(!testQueue1.empty())
    {
        cout << testQueue1.front();
        testQueue1.pop();
    }
    
    cout << endl;
    
    // Exercise the second queue
    for (; testQueue2.size() > 1; testQueue2.pop()); 
    testQueue2.push("Five...");
    testQueue2.push("Six...");
    testQueue2.push("Seven...");
    testQueue2.push("Eight...");
    cout << "\nUpdated size of second Queue: " << testQueue2.size() << endl;
    cout << "\nValues in second queue: " << endl;
    while(!testQueue2.empty())
    {
        cout << testQueue2.front();
        testQueue2.pop();
    }
    cout << endl << endl;

    cout << "*************************************"<< endl;
    cout << "End of Solution" << endl;
    cout << "*************************************" << endl;
    system("Pause");
}

Was This Post Helpful? 0
  • +
  • -

#8 jimblumberg  Icon User is online

  • member icon


Reputation: 4232
  • View blog
  • Posts: 13,297
  • Joined: 25-December 09

Re: Pop function causing program to crash

Posted 14 October 2012 - 03:56 PM

Please don't open a new topic for an existing problem. Topics merged.

Jim
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1