Lab 6 - Implementing a recursive function for a linked list

Objectives

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

What you should do...

1. Create a directory to hold the files for Lab 6, and change to that directory now. Copy the three files for Lab 6 (linktool.h, linktool.c, linktest.c) to your directory using the following command (notice there is a space and a period at the end of the command):

         cp /cs/cs2301-b11/labs/lab6/* .
   

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

2. 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.

3. 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.

4. 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.

5. 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.

6. Turn in your makefile and your updated version of linktool.c using the turnin program. The Unix command you should use to submit your files is

   /cs/bin/turnin submit cs2301 LAB6 linktool.c makefile
   

This is the last lab. Good luck with your finals.