INSTRUCTIONS

• Be sure to follow the programming style guide.
• Also follow the testing guide!
• All code, documentation, test plans, etc. must be your own original work. You must also turn in a filled-out copy of the assignment cover page.

PURPOSE

This assignment is to essentially redo Program 1 in C; a few small changes have been made. It will give you practice in programming a linked list and using data abstraction.

PROGRAM REQUIREMENTS

Implement an abstract data type List in C. The state of the abstract data type is a list of integers. Write functions for the following operations (you will need to include the list being operated on as a parameter):

• insertFront(i) - insert integer i at the front of the list
• insertBack(i) - insert integer i at the back of the list
• insertAfter(i1,i2) - insert integer i1 immediately after integer i2 (you figure out what to do if i2 does not appear in the list or appears multiple times).
• deleteFront - delete the integer at the front of the list and return it
• deleteBack - delete the integer at the back of the list and return it
• delete(i) - delete integer i from the list
• isEmpty - returns true if the list is empty and false otherwise
• print - prints out all the integers in the list in order ** new operation **

• insert(i) - insert integer i into the set
• isIn(i) - returns true if integer i is in the set and false otherwise
• delete(i) - deletes integer i from the set
• isEmpty - returns true if the set is empty and false otherwise
• union(T) - T is another set; when this method is called for set S, the result is to add all the elements in T to S. It is your choice what happens to T, but be sure to document it!
• intersect(T) - T is another set; when this method is called for set S, the result is to remove from S every element that is not also in T. It is your choice what happens to T, but be sure to document it!
• print - print out the elements of the set (order is unimportant) ** new operation **

IMPLEMENTATION REQUIREMENTS

• Implement the class List with a doubly-linked list.
• Implement the class Set with a List. Be sure to use information hiding.
• Be sure your program runs on the CS department's Unix machines when compiled with gcc!

Due by 10:20 AM on Wednesday, March 3:

• Turn in your code using the "turnin" program in the CS department Unix machines. (Turnin instructions available here.)
• Turn in the paper testing documentation and cover sheet.