The George Washington University
School of Engineering and Applied Science
Department of Electrical Engineering and Computer Science
CSci 131 -- Algorithms and Data Structures I -- Spring 2001

Project #2
Due Date: start of class, Wednesday, February 21, 2001

In this project you will explore singly-linked lists. The project depends on Chapters 1, 2, 3, and 8.

The package Singly_Linked_Lists provides data structures and a few operations for linked lists with single pointers. The package is stored in 6 files, as follows:

singly_linked_lists.ads
singly_linked_lists.adb
singly_linked_lists-addtoend.adb
singly_linked_lists-addtofront.adb
singly_linked_lists-copy.adb
singly_linked_lists-traverse.adb

Each operation procedure is in a separate file called a subunit.

The program Test_Lists demonstrates these operations. Your project is in several parts:

Part I: Preliminaries:

1. Copy all the files for Singly_Linked_Lists from programs131 into your directory. Compile and run the test program.
2. Copy all the subunit procedures into the package body, and make the necessary changes to compile the body successfully.
3. Recompile and re-run the test program; make sure everything is OK.

Part II: Project Tasks:

1. Add to the package a recursive operation that inserts a new value into a list, in its proper alphabetical position. This operation will have the specification

PROCEDURE InsertInOrder (L: IN OUT List; Word: IN WordType);
This procedure will return without doing anything if the "new" value is already in the list. Develop a test plan for this new procedure, and write a test program that carries out the test plan.
2. Add to the package a recursive operation that deletes a given value from a list. This operation will have the specification

PROCEDURE Delete (L: IN OUT List; Word: IN WordType);
and will return the deleted list node to the storage pool. The procedure will return without doing anything if the value to be deleted is not in the list. Develop a test plan for this new procedure, and write a test program that carries out the test plan.
3. Now add and test an iterative function Merge with this specification:

FUNCTION Merge (L1: List; L2: List) RETURN List;
that returns a third list containing the merger of the two input lists, with no duplicates. Assuming the values in the list are in sequence, this can be done in O(N) time, and you should write your function under that assumption.

What to submit:

• Part I: listing and turnin files demonstrating that this part was completed
• Part II: test plans, listings, and test runs demonstating that this part was completed.

WARNING: