Lab 5 - Implementing a recursive function for a linked list

Objectives

• to gain more practice in creating a makefile for a project that is composed of multiple files
• to write a recursive function
• to be able to write a function for a linked list

What you should do...

1. Sign the attendance sheet.

2. Create a directory in your CCC account to hold your Lab 5 files, and change to that directory. Download and unzip the files for Lab 5 from the following URL:

   http://www.cs.wpi.edu/~cs2301/common/lab5.zip

   If you now list the files in your directory, you should see entries for linktool.h, linktool.c, and linktest.c.

3. The sourcefiles linktool.c and linktest.c contain these include directives:

   linktool.c 
             #include "linktool.h"
   
   linktest.c
             #include "linktool.h"
   

   Using this information, create a makefile to generate an executable program called linktest. Compile your program by running make.

4. Run the program. It lets you create two linked lists of integers. The only function that isn't implemented yet is the one that checks to see if the two lists are equal (you'll be implementing that function shortly; for now, it's just implemented as a stub). Play with the program for a few minutes so that you understand how it works.

5. Now you should implement the function that determines if the two lists are equal. You will find the pre- and post-conditions and the prototype for lists_are_equal() in linktool.h. 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 lists are the same

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

   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.

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

7. Turn in your makefile and your updated version of linktool.c using the web-based turnin program.

There's no lab next week (April 17) - enjoy the shortened week. Lab 6 will be given on Wednesday, April 24.