CS2011 Lab 1: List processing in C (1 lab session)

Purpose.

This is an exercise in the invention of algorithms for list processing. You will be required to recall how to write C programs and use recursively defined pointer types.

All the algorithms should be implemented in C. Lists of integers are implemented in C using recursively defined pointer types:

typedef struct cell { int value ; 
                      struct cell *next ;} List ;

You may assume that we deal only with list of integers.

You should use recursively defined functions. The recursive structure should follow that of the type definition, that is it should be in terms of head and tail operations. The general scheme is: test whether the list is empty or not, then (1) decide what to do with the empty list, (2) for a non-empty list, take the head element, decide what to do with it, recursively call the function on the tail and then combine this result with the result of operating on the head.

Instead of repeating many operations with pointers throughout your code, it is better structurally to localise this by implementing simple operations and using these to build more complex operations. This is part of the structuring process called data abstraction that we look at in Exercise 3. For lists, the simple operations you need to implement include

1. `isempty' - tests whether a list is empty
2. `head' - returns the head element
3. `tail' - returns the tail of a list
4. `cons' (for construct) - extends a list by adding a new item at its head position.

The code described in this exercise is found in the file $CS2011/lab1/lists.c. You should copy this over to your filespace to provide an outline program in which you need to insert some function definitions. Call your program file lists.c.

The prototypes (type definitions) for these basic list functions are:

/* Function prototypes */
int     isempty(List *a_list);
int     head(List *a_list);
List*   tail(List *a_list);
List*   cons(int value, List *a_list);

Definitions for these functions (available in the code outline) are given below. Make sure that you understand these, especially the definition of cons in which we first create a new empty cell (using malloc) and then put a data item in it and attach it to the list. You should draw the requisite pictures and if you don't understand then consult a book on C and data types in C.

/* Function definitions*/
int     isempty(List *a_list)
{ return (a_list == NULL);
}

int     head(List *a_list)
{ List return_element;
  if (isempty(a_list))
        { printf("Head of empty list. Stop.\n");
          exit(1);
        }
  return a_list->value;
}

List*   tail(List *a_list)
{ if (isempty(a_list)) return NULL;
  return a_list->next;
}

List*   cons(int value, List *a_list)
{ List *new_element;
  new_element = (List*) malloc(sizeof(List));
  if (new_element == NULL)
        { printf("Insufficient memory in function cons. Stop.\n");
          exit(1);
        }
  new_element->value = value;
  new_element->next = a_list;
  return new_element;
}

You will also need input and output routines for lists. These are provided in the outline code as:

List*   input(void)
{ List *return_list = NULL;
  char input_buffer[10];
  printf("Enter list elements, one per line (Quit by typing Q) :\n");
  do {
        scanf("%s",input_buffer);
        if (input_buffer[0] != 'Q')
                { return_list = cons(atoi(input_buffer), return_list);
                }
     } while (input_buffer[0] != 'Q');
  return return_list;
}

void    output(List *a_list)
{ if (isempty(a_list)) printf("\n");
  else
        { printf("%d  ",head(a_list));
          output(tail(a_list));
        }
}

Make sure you understand how these work - they combine list recursion/iteration with input and output routines. Notice that output lists appear in the reverse order of the items input. You may wish (for no extra marks) to change one of the functions so that the output is in the same order as the input, but this is not necessary for this exercise.

To demonstrate how we use the above functions to do further list processing, consider the simple function calculating the length of a list:

int     length(List *a_list)
{ if (isempty(a_list)) return 0;
  else return ( 1 + length(tail(a_list)) );
}

Compare this with the same definition in SML:

fun length([]) = 0
  | length(x::xs) = 1 + length(xs)

Tasks: Removal of elements from a list

You are required to write definitions of the following functions (in the spaces provided in the sample code) display the programs, explain to a demonstrator how they work, and show them running on suitable examples. The recommended way is to use the basic list functions above to provide tail recursive programs (you may like to compare similar definitions in SML).

There are various operations that involve the removal (or deletion) of elements from a list. Here are three to be implemented.

1. Given an item, delete the first occurrence of it in a list, if it occurs, otherwise return the list unchanged.
   [2 marks]

2. Given an item, delete all occurrences of it in a list, if it occurs, otherwise return the list unchanged.
   [3 marks]

3. Given two lists $s$ and $t$, delete the first occurrence of the head of $s$ from $t$, then starting from this position in $t$ delete the first occurrence of the head of the tail of $s$ from $t$, etc. Thus if $s = [1,2,3,4]$ and $t = [2,5,1,3,2,1,4,3,5]$, the result is $[2,5,3,1,4,5]$.
   [5 marks]