Lab 6 — Implementing a Recursive Function for a Linked List

Wednesday, December 10, 2008

Objectives

· to gain more practice writing recursive functions;

· to be able to write a function for a linked list;

· to gain more practice with makefiles.

Note: don’t worry if you can’t finish the entire lab exercise. Use turnin to turn in as much as you’ve completed before you leave the lab. Make sure you finish the rest of the lab on your own time.

Getting Started

1. Sign the attendance sheet.

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

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

Your directory should now contain the files linktool.h, linktool.c, and linktest.c.

3. Create a makefile to generate an executable program called linktest. Note that both linktool.c and linktest.c include the file linktool.h, so your makefile must reflect this dependency. 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. Currently, that function is only a stub. Play with the program for a few minutes so that you understand how it works.

5. Implement the function lists_are_equal() by filling in the body for the stub at the end of the file linktool.c. You will find the prototype for lists_are_equal(), along with its pre- and post-conditions, in linktool.h. This function “compares” two lists to see if they are equal. By equality, we mean

· the two lists contain the same number of items, and

· the data values in corresponding positions in the lists are the same

Your function must be recursive! It must address both the base case and the general case. The base case is the case that stops the recursion — i.e., when you know the answer and don’t have to look farther down either list. There are three obvious base cases:–

· you are at the end of both lists, and the data values are the same;

· you are at the end of one list, but the other list is longer; or

· you find a mismatch of the data values of two corresponding items.

Once you have defined the base cases, you should write the general case — i.e., the recursive case that calls lists_are_equal() again. Note that this call should reduce the size of the problem.

6. Once you have written your function, use make to rebuild the test program linktest again. Run linktest to see if your function works correctly. Use the debugger gdb to debug it, if necessary.

7. Turn in your files using the turnin program. The Linux command you should use to submit your files is

/cs/bin/turnin submit cs2301 lab6 *.c *.h makefile

This is the last lab of the term. Good luck with your finals!