Scheme-like Lists in C

Goals

This lab applies ideas of box-and-pointer representations and provides practice using Scheme and C syntax to work within lists in C.

Exercises

1. Copy program scheme-lists.c to your account, compile it, and run it. This program will serve as the basis for the remaining steps of this lab. Be sure to ask about any sections you do not understand.
2. Add a function cadr to this program that returns the data stored in the second element in a list. Since the data field for a node stores an array of characters (i.e., a string), the return type of this function should be char *. (In this exercise and the subsequent ones, you will want to add lines to main to test each of your methods.)
   1. First, write cadr using the Scheme-like functions car and cdr.
   2. Next, rewrite cadr directly with C syntax (involving pointers and structs—no calls to car and cdr).
   3. Use assert to verify the precondition that such element exists (that is, the list has a second item).
3. Add a function count which counts how many times a specified item appears on a list. count should have two parameters: the list (a parameter of type const node_t *) and the desired item (of type const char *) for the search. In writing this code, you should use an iterative approach with a loop (rather than recursion).
   1. First, write count using Scheme-like functions car and cdr.
   2. Next, rewrite count directly with C syntax (involving pointers and structs).
   Be sure to test your code to see if it works for a null list and that it works for lists of various lengths and contents.
4. The program scheme-lists.c deallocates all nodes for d's list and also sets d to NULL. However, listDelete would not affect variables a, b, c, or e. For these variables, the nodes have been deallocated, but the variables still refer to the old memory locations. (Thus, the program sets each of these variables to NULL explicitly.)
   1. What happens if try to print list c or d immediately after the statement listDelete(&d); (before the NULL assignments)?
   2. Why do you get this result?
5. Add a function last that returns the last item on the list.
   1. First, write last using Scheme-like functions car and cdr.
   2. Next, rewrite last directly with C syntax (involving pointers and structs).
   Be sure to test your function to see if it works for a null list, for a list with only one element, and for a list which has more than one element.
6. Add a function getIndex that finds the index of the first occurence of the string str in a list, returning -1 if no string in the list matches str. For example, if the first node's string matches, a 0 should be returned. If the cadr matches, a 1 should be returned, etc. As parameters, getIndex should take a pointer to the list and a string to look for, and the function should return an integer.
   1. First, write getIndex using Scheme-like functions car and cdr.
   2. Next, rewrite getIndex directly with C syntax (involving pointers and structs).
   Test cases should include circumstances in which:
   • The list is null.
   • There are no matching strings in the list.
   • A matching string appears once in the list.
   • A matching string appears more than once in the list.

For those with extra time

7. Traditionally, the function last, which you wrote in Exercise 5, might be called rac (because it's sort of a "reverse" of the Scheme function car). Write a companion function rdc, that returns a new list with all but the last item of the original list (hence, it's a sort of "reverse" of cdr).

   Note: In order to preserve the original list, you will need to construct an entirely new set of nodes and copy their contents as you traverse the list.