CS2005 - D Term, 2004
Laboratory 4
Date: April 14, 2004

Purpose

To gain experience writing recursive functions.

Problem

You are to write a recursive boolean function lists_are_equal() that returns true if two linked lists are equal, and false otherwise.

Preliminaries

Make a new directory for lab4, and change to that directory. Copy the four files (node1.h, node1.cxx, linktest.cxx, makefile) from /cs/cs2005/labs/lab4 to your directory using this command:

cp /cs/cs2005/labs/lab4/* .

Discussion

You will see the prototype for lists_are_equal() in node1.h:

bool lists_are_equal(node* head1, node* head2);

What does it mean for two lists to be equal? We will define equality to mean that

the lists contain the same number of items
the data values in corresponding positions in the list are the same

You need to write the function lists_are_equal() and put your solution in node1.cxx (you will find a stub for the function at the end of node1.cxx). Your solution must be recursive. You should define the base cases first (the cases that will stop the recursive calls and return true or false to the calling function). What are the base cases for lists_are_equal()? There are three of them:

(You figure out the first one. Hint: it returns true)
You're at the end of one list, but have more nodes in the other list (this case returns false)
You find a mismatch (two unequal items) in a pair of nodes (this also returns false)

Once you have defined the base cases, you should then define the general (recursive) case. Remember, you want each successive recursive call to reduce the "size" of your problem.

Once you have written the function, use make to compile the test program linktest. Run the test program to see if your function works correctly.

Get Credit for this Lab

Sign the attendance sheet.
Turn in the implementation file node1.cxx. The command you should use to turnin your file is:
```
/cs/bin/turnin submit cs2005 lab4 node1.cxx
```