Comp 121 – Introduction to Data Structures

Comp 121 – Introduction to Data Structures. Spring 2000

Programming Assignment 1 -- Due September 25, 2000

An implementation of the list abstract data type (ADT) as a linked list is detailed in Section 3.2.3 of your textbook (Figures 3.6 – 3.15 contains almost the complete code). This implementation involves the use of two additional classes –a ListItr class, and a ListNode class. Our objective is to modify this implementation to obtain one that does not make use of the ListIter class. Rather than the List class interface defined in Figure 3.8, we will support the following interface:

template <class Object>

class List

{

public:

List(); //constructor

List(const List & rhs); // copy constructor

~List(); //destructor

bool isEmpty() const; //is the list empty?

void makeEmpty(); // make the list empty

void insert(const Object & x, int p); //insert x into the list at position p //(precondition: there are at least p-1 elements in the list)

int find(constant Object & x) const; //return the position at which x occurs in //the list – return –1 if x is not in the list

void remove(const Object & x); //delete x from the list if x is present; do nothing //if x is not present

friend ostream & operator<< <Object> (ostream & os, List<Object> & L);

// "cout << L" should cause the contents of L, separated by commas, to be printed on //the standard output (assume that << is overloaded appropriately for class Object)

const List & operator= (const List & rhs); // operator assignment

private:

ListNode<Object> *header;

};

You are to provide a complete working implementation of this interface. You may use any of the code provided in the text, but be sure to unambiguously attribute all such use – to fail to do so is to violate the honor code.

Rules for submitting this (and future) programs:

You are not permitted to work in groups – all your work must be your own, and you must attest to this in a signed comment that begins each program – failure to do so results in your program not being graded.

Include a complete listing of all your code, input files, and output files

Your code must be appropriately commented --- if we don’t understand your code with reasonable effort, you get no credit for it.

Include a test plan detailing how you tested your program, and why you believe it is correct.

Include a (neatly typed – not handwritten) design plan and some general comments on the structure and layout of your assignment.

All of the above should be placed in an envelope with your name and student-ID on the outside, and submitted at the beginning of class on the due date. Submissions will not be accepted after 10 minutes have elapsed from the start of class – no late submissions will be accepted without documented reasons.