CS2005 - B Term, 2004
Lab 5
Date: December 1, 2004

Purpose

To gain experience writing recursive functions for linked lists.

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 lab5, and change to that directory. Copy the four files (node1.h, node1.cxx, linktest.cxx, makefile) from /cs/cs2005/labs/lab5 to your directory using this command: 
cp /cs/cs2005/labs/lab5/* .

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
  1. the lists contain the same number of items
  2. 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). There are three base cases for lists_are_equal():
  1. (You figure out the first one. Hint: it returns true)
  2. You're at the end of one list, but have more nodes in the other list (this case returns false)
  3. 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 Run the test program to see if your function works correctly (the name of the executable program is linktest).

Get Credit for this Lab

Sign the attendance sheet.

Turn in the implementation file node1.cxx. Use this command to turn in your file: 

/cs/bin/turnin submit cs2005 lab5 node1.cxx

If you have time left...

Try to make some progress on Homework 4. At this point you should have your framework (functions written as stubs) compiling and building correctly.

There's no lab scheduled for next week.