V22.0201 (sec. 1) - Computer Systems Organization (Honors)

Assignment 6

Write, in C, a set of functions for manipulating linked lists of integers.  The basic building block for these lists will be the pair, consisting of a head (the first integer on the list), and a tail (the remainder of the list, represented by a pointer to the next pair in the list).  We define the type List as a pointer to a pair.  You are to provide the following functions on Lists:
cons(int i, List o)
creates and returns a List with head i and tail o (so the elements of the new list are the element i followed by the elements of o)
head(List o)
if List o is not NULL, returns the head of the List;  if List o is NULL, returns 0
tail(List o)
if List o is not NULL, returns the tail of the List;   if List o is NULL, returns NULL
member(int i, List o)
returns 1 if i is an element of List o, else 0
print(List o)
prints the elements of List o, enclosed in parentheses
Put all these functions in one file. Be sure that your name appears as a comment in your C file.

This assignment is due on December 13th.  There is a penalty of 1/2 point (out of a total of 7 points) for each day late.

Email your C source file to grishman@cs.nyu.edu (not to the grader).  Include your name and "Asgn 6" in the subject line.


The following header file, "list.h", defines the necessary structures and function type signatures.  You should include a copy in your file (i.e., your file will begin with   #include "list.h")

typedef struct pair* List;

struct pair {
 int head;
 List next;
};

List cons (int, List);
int head (List);
List tail (List);
int member (int, List);
void print (List);


Example of using IntVec:

#include <stdio.h>
#include "list.h"

main () {
 List p;
 p = NULL;
 p = cons (1, p);
 printf ("Head of p = %i\n", head(p));        // prints 1
 p = cons (2, p);
 printf ("Head of p = %i\n", head(p));        // prints 2
 printf ("Is 2 in p?  %i\n", member(2, p));   // prints 1
 printf ("Is 3 in p?  %i\n", member(3, p));   // prints 0
 print (p);                                   // prints ( 2  1 )
 print (tail (p));                            // prints ( 1 )
 print (tail (tail (p)));                     // prints ()
}


Additional notes on C for this assignment:

1.  A typedef statement may be used to create new names for data types.  For example,

typedef struct pair* List
means that we can write "List" in the rest of the program instead of "struct pair*" (K & R p. 146).

2.  To allocate (with malloc) a new block for a structure, one has to know how many bytes it takes up.  C provides a function for this, sizeof (type)  (K & R, p. 135).  For example, if X is the name of a structure, sizeof (struct X) returns the number of bytes an instance of this structure occupies.

3.  If p is a pointer to a pair with elements head and next, one can access the head element of the pair with (*p).head or the alternate notation  p->head.