Laboratory Exercise on Scheme-like Lists in C

Overview

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

Work Started in Class

Background: Lists in Scheme

The reading for this lab describes box-and-pointer diagrams as a graphical model for lists.

1. Draw box-and-pointer diagrams for each of the following lists:

   ((x) y z)
   (x (y z))
   ((a) b (c ()))
   

Implementing Scheme List Operations

The reading also describes the implementation of lists in C and presents program scheme-lists.c that presents relevant C functions and several test cases.

• The car function returns the contents of the data field in the listNode designated by list. This information is obtainable as first.data.

• For the cdr function, we must choose whether to alter the current list, return a pointer to the tail of the current one, or return a new one. For illustration, we return a pointer to the tail of the current list.

• We implement cons by building a new node and copying relevant information into the data and next fields.

• The listPrint function uses a temporary variable listPtr to move progressively down the list node by node, printing as it goes.

• The listInit function requires that we pass the address of a first pointer. The formal header is

  void listInit (struct Node ** list)

  or equivalently

     void listInit (listType * list)
  

  Assignment of NULL to this address uses the syntax:

     *list = NULL
  

• The listDelete procedure recursively deallocates space for the rest of the list before it uses C's free function to deallocate space for the head of a list.

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 second to this program that returns the data stored in the second element in a list (if present) or an empty string if the list is null or has only one element. 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 your methods.)

   1. Write second using Scheme-like functions car and cdr.
   2. Write second directly with C syntax (involving pointers and structs — no calls to car and cdr).

3. Add a function count which counts how many times a specified item appears on a list. count should have two parameters: the list (of type listType) and the desired item (of type char *) for the search. In writing this code, you should use an iterative approach.

   1. Write count using Scheme-like functions car and cdr.
   2. Write 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.

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 think you get this result?

Homework

5. Add a function last which returns the last item on the list.

   1. Write last using Scheme-like functions car and cdr.
   2. Write 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 first index of the string str in a list. As parameters, it should take a pointer to the list and a string to look for. It should produce i, an integer.

   1. Write getIndex using Scheme-like functions car and cdr.
   2. Write getIndex directly with C syntax (involving pointers and structs).

   Test cases should include circumstances in which:

   • There is a null list.
   • There are no strs in the list.
   • str appears once in the list.
   • strappears more than once in the list.