CPSC 211, Sec 201-203
Spring 2004
Program 3: Implementing a Set ADT with a Linked List in C
INSTRUCTIONS
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 **
Implement an abstract data type Set in C.
The state of the abstract data type is a (mathematical) set
of integers.
Write functions for the following operations
(you will need to include the set being operated on as a parameter):
- 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!
TURN-IN REQUIREMENTS
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.