CS211 Data Structures
Modified from projects of Chapter 4 at
www.cs.colorado.edu/~main/projects/
of Data Structures and Other Objects Using C++ by Michael Main and Walter Savitch
The Assignment:
You will implement and test a revised sequence class that uses a dynamic array to store the items.
Purposes:
Ensure that you can write a small class that uses a dynamic array as a private member variable.
Before Starting:
Read all of Chapter 4.
Due Date:
Monday, October 15. If you have problems, late work will be accepted on Tuesday with no penalties. Late work may be submitted on Wednesday with 5% penalty. No work will be accepted after Wednesday.
How to Turn In:
Pack your files in a WinZip file (Windows) or tar file (Unix). Attach the file in your email with "CS211 Assignment 3" in your message Subject line, send it to me.
Files that you must write and turn in (Please do not turn in other files!!):
Other files that you may find helpful (but you do not need to turn in):
#include "sequence1.h"
to
#include "sequence2.h"
And change the
statement
using namespace main_savitch_3
to
using namespace main_savitch_4
Your sequence class for this assignment will differ from the your previous sequence in the following ways:
Start by declaring the new sequence's private member variables in sequence2.h. This should include the dynamic array (which is declared as a pointer to a value_type). You will also need two size_type variables to keep track of the number of items in the sequence and the total size of the dynamic array. After you've declared your member variables, write an invariant for the top of sequence2.cxx.
Many of the features of this class are similar to the bag class from Section 4.3, so start by thoroughly reading Section 4.3 and pay attention to new features such as how the sequence differs from a bag. Also the implementation of some of the functions are almost the same as in Part 1. Once again, do your work in small pieces. For example, my first version of the sequence had only a constructor, start, insert, advance, and current. My other member functions started out as stubs.
Use the interactive test program and the debugger to track down errors in your implementation. If you have an error, do not start making changes until you have identified the cause of the error.
The ability to initialize and use a static member constant within the class definition is a relatively new feature. If you have an older compiler (for example, Visual C++ 6.0) that does not support static const members, then you may use
enum {DEFAULT_CAPACITY = 30};
instead of
static const size_type DEFAULT_CAPACITY = 30;
After this definition, the name bag::DEFAULT_CAPACITY is defined to have the integer value 30. Although this is not the intended use of an enum definition, the result is the same as using a static member constant.
When a member functions needs to increase the size of the dynamic array, it
is a good idea to increase that size by at least 10% (rather than by just one
item).
You may wish to provide some additional useful member
functions, such as
(1) Operators + and +=.. For + operator, x+y contains all the items of x,
followed by all the items in y. The statement x += y appends all the items in y
to the end of what's already in x.
(2) Operator []. For a sequence x, we would like to be able to refer to the
individual items using the usual C++ notation for arrays. For example, if x has
three items, then we want to be able to write x[0], x[1] and x[2] to access
these three items. The use of the square brackets is called the subscript
operator. The subscript operator may be overloaded as a member function, with
the prototype shown here as part of the sequence class:
class sequence
{
public:
...
value_type operator[](size_type index) const;
...
};
The only parameter is the index of the item we want to retrieve. The implementation of this member function should check that the index is valid, and then return the specified item.