CSci 581-01: Special Topics in Computer Science
Object-Oriented Design & Programming
Fall Semester 1997

Assignment #1
Due Midnight, Monday, 8 September

Tasks

1. The abstract data type List is informally defined below. Give a more formal description similar to those given in the handout on Data Abstraction. That is, give the sets involved and the signatures and semantics of the operations. (You may, if you wish, state the signatures and semantics together as I did for the Day ADT in the handout.) Divide the operations into constructors, mutators, accessors, and destructors.

2. Using an imperative language (e.g., C or Pascal) with which you are familiar, implement the List abstract data type as a set of subprograms. Since you are to implement an abstract data type, not just a single abstract data structure, your package should allow the creation of multiple instances of the List type. If you use C++ or another object-oriented language, do not use the class construct; the purpose of this task is to review techniques for implementing ADTs in traditional imperative languages.

   Issues to consider: What is the nature of the "items" to be stored in the list? (For example, can you create lists of integers, lists of records, etc.?) How do you represent the list internally (e.g., as an array, a dynamically allocated linked list structure, etc.)? How can you dynamically create, use, and destroy multiple instances of the list ADT? Do your mutators change the instance's state or do they create modified copies?

   Test and document your package carefully. The subprograms that make up the List package should be clearly noted and separated from the framework needed to test the package.

   Please submit a paper listing of your source code. Also submit a listing showing your testing of the package.

Abstract Data Type List

The ADT List represents lists (or sequences) of items. List includes the following operations:

createList

takes a number (as an argument) and produces a new empty list capable of holding the given number of items.

destroyList

takes a list and "destroys" it, releasing the resources used.

prepend

takes an item and a list and adds the item to the head of the list (i.e., ahead of the previous elements of the list).

append

takes an item and a list and adds the item to the end of the list (i.e., behind the previous elements of the list).

head

takes a list and returns the item at the head of the list (without modifying the list).

decapitate

takes a list and removes the item at the head of the list.

length

takes a list and returns the number of items in the list.

isEmptyList

takes a list and returns true if and only if the list is empty (i.e., contains no items).

isFullList

takes a list and returns true if and only if the list is full (i.e., contains no space for additional items).

concat

takes two lists and attaches the contents of the second list on the end of the first list.

UP to CSci 581 Assignments page?