Computer Science City College of New York
CSc21200 Data Structures
Programming Assignment 4 (Chapter 5) - Revised sequence
with the Linked List Toolkit
Adapted from Data Structures and Other Objects Using C++
by Michael Main and
- The Assignment:
- You will implement and test a revised sequence class that uses a
linked list to store the items.
- Ensure that you can write a small class that uses the linked
toolkit to create and manipulate a linked list.
- Before Starting:
- Read all of Chapter 5, with particular attention to Sections 5.3
- Due Date:
- Wednesday, October 28, 2009.
If you have problems,
will be accepted on Friday with no penalties. Late work may be
submitted on Saturday or Sunday with 5% penalty per day. No work will
be accepted after Sunday.
- How to Turn In:
- Pack your files in ONE WinZip file (Windows) or
ONE tar file (Unix). Attach the file in your email with "CSC212
Assignment 4" in your message Subject line, send it to Wai
Khoo ( WKhoo@gc.cuny.edu
- Files that you must write and turn in:
- sequence3.h: The header file for the new sequence
class. Actually, you don't have to write much of this file. Just start
with our version and add your name and
other information at the top. If some of your member functions are
implemented as inline functions, then you may put those implementations
in this file too. By the way, you
might want to compare this header file with your first sequence header
file (sequence1.h) , and second sequence
file (sequence2.h). The linked list version
no longer has a CAPACITY constant nor a DEFAULT_CAPACITY constant
the items are stored on a linked list instead of an array.
- sequence3.cxx: The implementation file for the new
sequence class. You will write all of this file, which will have the
the sequence class, the implementations of all the member functions of
sequence class, and the Big-Os of these functions.
- node1.h and node1.cxx: Copy these files to your
subdirectory. They contain the linked list toolkit from Section 5.2.
You may use these
files without changing them. However we only provide the documentation
the function list_piece (see Self-Test Exercise 17 on page 239). You
need to write an implementation of this function if you are going to
it in writing your copy constructor and overloading your assignment
If you do make changes, please turn them in.
- Other files that you may find helpful:
is the same interactive test program that you used with the earlier
sequences. This is exactly what we expect for the information
hiding of the class - the users do not need to know how the class is
implemented ( both the
member variables and the functions) as far as the interfaces (the
of the member functions) remain the same. So if you want to use
test program with the new sequence, the only thing you need to do is to
copy it to your directory and open it with your editor. Then change the
using namespace main_savitch_3;
using namespace main_savitch_5;
- seq_ex3.cxx: A non-interactive test
that will be used to grade the correctness of your new sequence class.
points given by the program will only be served as a reference; we ar
to look into your code and your analysis ( in the form of comment
for actual grading.
The sequence Class Using a Linked List
Your sequence class for this assignment will differ from the your
previous sequence in the following ways:
Discussion of the Assignment
Start by declaring the new sequence's private member variables in
sequence3.h. You might try declaring these variables yourself, and then
compare your solution
with the suggestion in Section 5.4.
- The sequence's items are now stored on a linked list. The head
pointer of the linked list is a private member variable of the sequence
class. I suggest that you also have a tail pointer as an additional
private member variable of the sequence class. The reason for the tail
pointer is explained in Section 5.4 of the textbook.
- Because you are dynamically allocation memory within your
sequence class, you will need to define a copy constructor, an
assignment operator, and a destructor. You need to pay special
attention to the value semantics of your new sequence class - you need
not only to make a copy of the linked list, but also need to place the
node pointers correctly. Please refer to page 260 for more detailed
discussions on the value semantics.
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.
Design a sequence class using a linked list could be little bit more
complicated than using an array. Therefore, I recommend you to draw an
example linked list such as the one shown in page 260 of the textbook
when you are writing code for each member function. Always remember to
show all the member variables in order to remind you making
proper changes of them. You need to
place the cursor and the precursor at various locations, head, tail and
other places. Note that the sequence could be empty, and cursor and/or
could be NULL, even when the sequence is NOT empty. With the help of
drawings, jobs will be much easier!
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. If
you come to me for help, we will always ask you to do the
For those working in the Unix operating system: Spend some time
writing your make file. A correct Unix makefile will save you time.
that each compilation command in the make file has a TAB as the first
In order to insert a TAB using emacs, type Ctrl-Q and then press the
key. Or, if you are working from a modem where the TAB key is disabled,
- Show us the invariant that describes how your private member
variables implement the sequence class.
- Use the debugger to show us the problem!
ESCAPE x quoted-insert RETURN TAB
Run Time Analysis of the sequence classes and grading rules
We will use the number of items in a bag as the input size n.
Please give the Big-O of each function in your implementation, and
with the corresponding functions of the sequence using a dynamic array.
should write the time analysis in the comment lines of each
function. The breakdowns of points (of 100) will be the
Basis points (70) if your implementation passes the seq_ex3 test
Invariant of the class (5 points)
Run time analysis (10 points)
Other implementation details (15 points)
( email@example.com ),