- 31 Mar, 2021
- 0 Comments
- 4 Mins Read
sequence.cpp and sequence.h Part 1 and Part 2 /AN
Part 1
Introduction
There’s one thing from the reading that I want to clarify. It’s true that “List” is a well-established ADT in Computer Science, but the authors tend to discuss the “List” ADT as if the specification given in the text is also well-established, as if every time you see a List ADT it will have the same specification. Although “List” is a well-established ADT, the precise List ADT specifications vary widely. The Standard Template Library has a “list” container. I suggest that you take a few moments to look it over. You can see a description and list of member functions at http://www.cplusplus.com/reference/list/list/. You will see that the operations defined there are quite different from the ones in the text.
Assignment 7.1 [15 points]
No documentation (commenting) is required for this assignment.
This assignment is based on an assignment from “Data Structures and Other Objects Using C ” by Michael Main and Walter Savitch.
Use linked lists to implement a Sequence class that stores int values.
Specification
The specification of the class is below. There are 9 member functions (not counting the big 3) and 2 types to define. The idea behind this class is that there will be an internal iterator, i.e., an iterator that the client cannot access, but that the class itself manages. For example, if we have a Sequence object named s, we would use s.start() to set the iterator to the beginning of the list, and s.advance() to move the iterator to the next node in the list.
(I’m making the analogy to iterators as a way to help you understand the point of what we are doing. If trying to think in terms of iterators is confusing, just forget about iterators and focus on following the specification below.)
What Is Due This Week
This is the first part of a two part assignment. In the next assignment you will be adding additional member functions to the class that you create in this assignment. I think this first part of the assignment is easier than the second part, so you may want to try to get an early start on next week’s assignment. For this week, you are required to implement all of these functions except for attach() and remove_current(). You are also not required to implement the big-3.
Although we will just be testing your class using int values in the Sequence, you should define a value_type so that a programmer could easily edit the class to make it a Sequence that stores some other type of value. Note the Sequence is not a templated class.
Note: you should use assert() to halt execution if any of the preconditions below are not true
typedef ____ value_type;
typedef ____ size_type;
Sequence();
// postcondition: The Sequence has been initialized to an empty Sequence.
void start();
// postcondition: The first item in 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);
// 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. In either case, the new item is now the current item of the Sequence.
void attach(const value_type& entry);
// Not required this week
// 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 new item is now the current item of the Sequence.
void remove_current();
// Not required this week
// Precondition: is_item returns true.
// Postcondition: The current item has been removed from the Sequence. If the item removed
// was the last item in the Sequence, then there is now no current item. Otherwise, the item
// that was after the removed item is now the current item.
size_type size() const;
// Postcondition: Returns 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 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 current item in the Sequence is returned.
Also, your class should be placed in a namespace “cs_sequence”.
Here is an example of a simple client program, to give you an idea about how sequences might be used. You can also use this to test your class, but it’s far from exhaustive. Keep in mind as you write your class that you should test each member function after you write it.
int main() {