|
-
September 15th, 2012, 02:58 PM
#1
print sequence data structure
Hello everyone, I want to see if there is anyone who can help me with printing out a sequence data structure. I am using a PC running Windows 7 with Microsoft Visual Studio 2008. This sequence has a dynamic array which stores a value_type which can be any of the built in data types for C++. Initially the sequence is 30 slots long. When the program starts the user starts at the beginning of the sequence by choosing the “!” option from the menu. The user will then insert a number such as 11 by selecting the “I” option (upper or lower case). Then the user will go to the next position in the sequence by selecting the “+” option then insert 22, then go to the next position and insert 33. To show that the numbers are actually in the sequence the user goes back to the beginning of the array by selecting “!” and then select “C” to display the current number of 11. Then the user goes to the next position by selecting “+” and then “C” to display 22 and so forth. At this point the member function called current() works just find , but when trying to print the contents of the entire sequence the program displays garbage. Why?
Code:
// FILE: sequence_test.cpp
// An interactive test program for the new sequence class
#include <cctype> // Provides toupper
#include <iostream> // Provides cout and cin
#include <cstdlib> // Provides EXIT_SUCCESS
#include "sequence2.h" // With value_type defined as double
using namespace std;
using namespace CISP430_A2;
// PROTOTYPES for functions used by this test program:
void print_menu( );
// Postcondition: A menu of choices for this program has been written to cout.
char get_user_command( );
// Postcondition: The user has been prompted to enter a one character command.
// The next character has been read (skipping blanks and newline characters),
// and this character has been returned.
void show_sequence(sequence display);
// Postcondition: The items on display have been printed to cout (one per line).
double get_number( );
// Postcondition: The user has been prompted to enter a real number. The
// number has been read, echoed to the screen, and returned by the function.
int main( )
{
sequence test; // A sequence that we’ll perform tests on
char choice; // A command character entered by the user
cout << "I have initialized an empty sequence of real numbers." << endl;
do
{
print_menu( );
choice = toupper(get_user_command( ));
switch (choice)
{
case '!': test.start( );
break;
case '+': test.advance( );
break;
case '?': if (test.is_item( ))
cout << "There is an item." << endl;
else
cout << "There is no current item." << endl;
break;
case 'C': if (test.is_item( ))
cout << "Current item is: " << test.current( ) << endl;
else
cout << "There is no current item." << endl;
break;
case 'P': show_sequence(test);
break;
case 'S': cout << "Size is " << test.size( ) << '.' << endl;
break;
case 'I': test.insert(get_number( ));
break;
case 'A': test.attach(get_number( ));
break;
case 'R': test.remove_current( );
cout << "The current item has been removed." << endl;
break;
case 'Q': cout << "Ridicule is the best test of truth." << endl;
break;
default: cout << choice << " is invalid." << endl;
}
}
while ((choice != 'Q'));
return EXIT_SUCCESS;
}
void print_menu( )
// Library facilities used: iostream.h
{
cout << endl; // Print blank line before the menu
cout << "The following choices are available: " << endl;
cout << " ! Activate the start( ) function" << endl;
cout << " + Activate the advance( ) function" << endl;
cout << " ? Print the result from the is_item( ) function" << endl;
cout << " C Print the result from the current( ) function" << endl;
cout << " P Print a copy of the entire sequence" << endl;
cout << " S Print the result from the size( ) function" << endl;
cout << " I Insert a new number with the insert(...) function" << endl;
cout << " A Attach a new number with the attach(...) function" << endl;
cout << " R Activate the remove_current( ) function" << endl;
cout << " Q Quit this test program" << endl;
}
char get_user_command( )
// Library facilities used: iostream
{
char command;
cout << "Enter choice: ";
cin >> command; // Input of characters skips blanks and newline character
return command;
}
void show_sequence(sequence display)
// Library facilities used: iostream
{
for (display.start( ); display.is_item( ); display.advance( ) )
{
cout << display.current( ) << endl;
}
}
double get_number( )
// Library facilities used: iostream
{
double result;
cout << "Please enter a real number for the sequence: ";
cin >> result;
cout << result << " has been read." << endl;
return result;
}
Code:
// FILE: sequence1.h
// CLASS PROVIDED: sequence (part of the namespace CISP430_A2)
// There is no implementation file provided for this class since it is
// an exercise from Section 3.2 of "Data Structures and Other Objects Using C++"
//
// TYPEDEFS and MEMBER CONSTANTS for the sequence class:
// typedef ____ value_type
// sequence::value_type is the data type of the items in the sequence. It
// may be any of the C++ built-in types (int, char, etc.), or a class with a
// default constructor, an assignment operator, and a copy constructor.
//
// typedef ____ size_type
// sequence::size_type is the data type of any variable that keeps track of
// how many items are in a sequence.
//
// enum { CAPACITY = 30 };
// CAPACITY is the maximum number of items that a sequence can hold.
//
// CONSTRUCTOR for the sequence class:
// sequence(size_type entry=CAPACITY );
// Postcondition: The sequence has been dynamic allocate memories.
//
//COPY CONSTRUCTOR
// sequence(const sequence& entry)
// Postcondition: The sequence has been created by copying from an existing sequence.
//
// MODIFICATION MEMBER FUNCTIONS for the sequence class:
// void start( )
// Postcondition: The first item on the sequence becomes the current item
// (but if the sequence is empty, then there is no current item).
//
// void advance( )
// Precondition: is_item returns true.
// Postcondition: If the current item was already the last item in the
// sequence, then there is no longer any current item. Otherwise, the new
// current item is the item immediately after the original current item.
//
// void insert(const value_type& entry)
// Precondition: size( ) < CAPACITY. if this is not true then increase the capacity by 10%
// Postcondition: A new copy of entry has been inserted in the sequence
// before the current item. If there was no current item, then the new entry
// has been inserted at the front of the sequence. In either case, the newly
// inserted item is now the current item of the sequence.
//
// void attach(const value_type& entry)
// Precondition: size( ) < CAPACITY.if this is not true then increase the capacity by 10%
// Postcondition: A new copy of entry has been inserted in the sequence after
// the current item. If there was no current item, then the new entry has
// been attached to the end of the sequence. In either case, the newly
// inserted item is now the current item of the sequence.
//
// void remove_current( )
// Precondition: is_item returns true.
// Postcondition: The current item has been removed from the sequence, and the
// item after this (if there is one) is now the new current item.
//
//Operator= overloading
// void sequence::operator =(const sequence&);
// Postcondition: The l-value's sequence object is copy to the r-value
//
// CONSTANT MEMBER FUNCTIONS for the sequence class:
// size_type size( ) const
// Postcondition: The return value is the number of items in the sequence.
//
// bool is_item( ) const
// Postcondition: A true return value indicates that there is a valid
// "current" item that may be retrieved by activating the current
// member function (listed below). A false return value indicates that
// there is no valid current item.
//
// value_type current( ) const
// Precondition: is_item( ) returns true.
// Postcondition: The item returned is the current item in the sequence.
// Destructor
// ~sequence()
// Postcondition: release the memory to the heap
//
// VALUE SEMANTICS for the sequence class:
// Assignments and the copy constructor may be used with sequence objects.
//
//void resize(size_type new_capacity )
//Precondition: new_capacity > used
// Postcondition: new space allocated and old space released
#ifndef SEQUENCE_H
#define SEQUENCE_H
#include <cstdlib> // Provides size_t
namespace CISP430_A2
{
class sequence
{
public:
// TYPEDEFS and MEMBER CONSTANTS
typedef double value_type;
typedef size_t size_type;
enum { CAPACITY = 30 };
// CONSTRUCTOR
sequence(size_type entry = CAPACITY );
// COPY CONSTRUCTOR
sequence(const sequence& entry) ;
// Library facilities used: cstdlib
// MODIFICATION MEMBER FUNCTIONS
void start( );
void advance( );
void insert(const value_type& entry);
void attach(const value_type& entry);
void remove_current( );
void resize(size_type );
void sequence::operator =(const sequence&);
// CONSTANT MEMBER FUNCTIONS
size_type size( ) const;
bool is_item( ) const;
value_type current( ) const;
//Destructor
~sequence() ;
private:
value_type *data;
size_type used;
size_type capacity;
size_type current_index;
};
}
#endif
Code:
/*
filename: sequence2.cpp
author: Derick Elwood
purpose: To implement a sequence data structure
*/
#include <iostream>
#include <math.h> /* supplies isnan(), supplies ceil() */
#include <algorithm> /* supplies copy function */
#include <String.h>
#include "sequence2.h"
#include <new> //required for nothrow new
using namespace std; /* for some reason "copy()" will not be found by the complier without it */
namespace CISP430_A2
{
/* Parametrized Default Constructor */
sequence::sequence(size_type entry)
{
data = new value_type[entry]; //dynamically allocate memory space for 30 elements
used = 0; // initial amount of elements inside the array (empty array)
current_index = 0; //initially the current index should be the first position in the array
capacity = entry;
}/* end default parametrized constructor */
/* Copy Constructor */
sequence::sequence(const sequence& entry)
{
data = new value_type[entry.capacity]; /* copy constructor ensures that the new object will have its own
dynamically allocated memory */
used = entry.used;
current_index = entry.current_index;
}/* end of copy constructor */
/* Destructor */
sequence::~sequence()
{
delete [] data; //free memory for array data
}/* end of destructor */
/* If the sequence is not empty sets the current index to zero, otherwise it does nothing */
void sequence::start()
{
current_index = 0;
}/* end of start function */
/* Test if there is a number at the current index of the array */
bool sequence::is_item() const
{
if(current_index < used)
{
return true;
}
else
{
return false;
}
}/* end of is_item function */
/* will return the current number in the sequence if is_item returns true */
sequence::value_type sequence::current() const
{
if( is_item() )
{
return data[current_index];
}
else
{
return ' '; /* must return any of the built in data types */
}
}/* end of current function */
/* advances the current index by 1 */
void sequence::advance()
{
if( is_item() )
{
current_index++;
}
}/* end of advance function */
/* returns the number of items in the sequence */
sequence::size_type sequence::size() const
{
return used;
}/* end of size function */
void sequence::operator =(const sequence& source) /* the function show_sequence() in sequence_test.cpp (option P) will cause a run time error without checking for self alignment */
{
value_type *new_data;
if(this == &source) /* check for self alignment */
{
return;
}
if(capacity != source.capacity)
{
new_data = new value_type[source.capacity];
delete [] data;
data = new_data;
capacity = source.capacity;
}
used = source.used;
copy(source.data, source.data + used, data);
}/* end of overloaded assignment operator = */
/* Will insert a number into the data array before the current_index */
void sequence::insert(const value_type& entry)
{
double bigCapacity = capacity + (capacity * .1); /* When we increase capacity by 10% this may result in a floating point number */
int roundedUpCapacity;
value_type *newData;
roundedUpCapacity = (int)ceil(bigCapacity); /* Therefore the new capcity may need to be rounded up */
newData = new (nothrow)value_type[roundedUpCapacity];
if(used == 0) /* sequence is empty and there is no current item */
{
data[0] = entry;
used++;
}
else if(used < capacity)
{
if(is_item())
{
for(size_type i = (used - 1); i >= current_index; i--)
{
data[i + 1] = data[i]; /* shifts array elements to the right */
}
}
data[current_index] = entry;
used++;
}
else
{
if(newData != NULL)
{
memcpy(newData, data, roundedUpCapacity);
delete [] data;
data[0] = newData[0];
delete [] newData;
for(size_type i = (used - 1); i >= current_index; i--)
{
data[i + 1] = data[i]; /* shifts array elements to the right */
}
data[current_index] = entry;
used++;
}
else
{
int dummy = 0; //do nothing
}
}
}/* end of function insert */
/* Will insert a number into the data array after the current_index */
void sequence::attach(const value_type& entry)
{
double bigCapacity = capacity + (capacity * .1); /* When we increase capacity by 10% this may result in a floating point number */
int roundedUpCapacity;
value_type *newData;
roundedUpCapacity = (int)ceil(bigCapacity); /* Therefore the new capacity may need to be rounded up */
newData = new (nothrow)value_type[roundedUpCapacity];
if(used == 0) /* sequence is empty and there is no current item */
{
data[0] = entry;
used++;
}
else if(used < capacity)
{
if(is_item())
{ /* Shift all elements in data array one space to the right after the current_index */
for(size_type i = (used - 1); i > current_index; i--)
{
data[i + 1] = data[i];
}
}
data[current_index + 1] = entry;
used++;
}
else
{
if(newData != NULL)
{
memcpy(newData, data, roundedUpCapacity);
delete [] data;
data[0] = newData[0];
delete [] newData;
/* Shift all elements in data array one space to the right after the current_index */
for(size_type i = (used - 1); i > current_index; i--)
{
data[i + 1] = data[i];
}
data[current_index + 1] = entry;
used++;
}
}
}/* end of function attach */
/* The current item has been removed from the sequence, and the item after this (if there is one) is now the
new current item. */
void sequence::remove_current()
{
if( is_item() )
{
for(size_type i = (current_index + 1); i < used; i++ )
{
data[i - 1] = data[i]; /* move array elements one space to the left at the current_index */
}
}
if(used > 0)
{
used--;
}
}/* end of function remove_current */
/* New space allocated and old space released */
void sequence::resize(size_type capacity)
{
if(capacity > used)
{
value_type *newData2;
newData2 = new (nothrow)value_type[capacity];
memcpy(newData2, data, capacity);
delete [] data;
data[0] = newData2[0];
delete [] newData2;
}
}/* end of function resize */
}/* end of namespace CISP430_A2 */
-
September 18th, 2012, 04:10 AM
#2
Re: print sequence data structure
 Originally Posted by andre1011
Hello everyone, I want to see if there is anyone who can help me with printing out a sequence data structure. I am using a PC running Windows 7 with Microsoft Visual Studio 2008.
So have you used the debugger to debug your own code? You are using Visual Studio, and it has one of the best debuggers made for C++ compilers. Use the debugger to single step through your program and identify where things start to break down.
One thing that is absolutely discouraged is this:
Code:
sequence::sequence(const sequence& entry)
{
data = new value_type[entry.capacity]; /* copy constructor ensures that the new object will have its own
dynamically allocated memory */
used = entry.used;
current_index = entry.current_index;
}/* end of copy construct
Your copy constructor makes bogus copies.
That sequence represented by the new object is not a copy of the passed-in sequence, entry. Why are you not copying the elements of the entry sequence into the new data? So now you have a copy that really isn't a copy. See the problem with this?
Once you start to make fake copies, your program is now buggy. The copy constructor has a special purpose, and that is to make an exact copy of the object being passed in. In other words, if I take that new sequence and use it wherever I used the "entry" sequence, that program has to behave exactly the same way, regardless of how I used the original "entry" sequence.
Otherwise, you have two or more objects masquerading as copies, and then all heck breaks loose. The compiler is allowed to make copies whenever it needs to, and by writing copy constructors that do not make real copies places your program in the realm of "undefined behaviour".
Secondly, you do not have an assignment operator coded in addition to the copy constructor. What if you want to assign a sequence to an already existing sequence? Your code does not account for this scenario. Look up the "rule of three" for C++.
Regards,
Paul McKenzie
Last edited by Paul McKenzie; September 18th, 2012 at 04:37 AM.
-
September 21st, 2012, 04:41 PM
#3
Re: print sequence data structure
Thank you, I fixed the copy constructed and the programed worked, thanks a lot!
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|
Reply With Quote