COMP1721 - Higher Computing 1B

• Manipulating linked lists.

Create a separate directory (lab09 is a good name) for this week's exercises.

Your task is to add two functions to a class used to represented an ordered list of integers.

The file list.c is the starting point for this week's lab exercises.

It contains a struct, list_node, which can be used to represent an ordered sequence of integers. It uses a linked list as its data representation. It is the same struct you have seen in lectures.

You will remember that each element in the list is represented by a list_node struct.

typedef struct list_node list_node;
typedef list_node *linked_list;

struct list_node {
    int       data;
    list_node *next;
};

You have to implement these three functions:

• int length(linked_list list) - return the number of values in the list
• int nth(int index, linked_list list) - return the n-th value in this list
• linked_list reverse(linked_list list) - reverse the nodes in this list

The function nth is the equivalent of the Haskell function !!.

It should return the integer at the indicated position in the list. The first element in the list is regarded as being at position 0.

If the argument to nthElement is not a valid position in this list, it should print a suitable message on standard error.

The function reverse should place the nodes of the list in reverse order. It should not create any new nodes. It should not change the data field of any node. It can only change the next fields of nodes.

The function reverse will require careful thought. It is much more difficult than the first two functions to implement.

You will notice list.c already has the skeletons of the three functions. You have to complete the three functions.

Testing Your Functions

The examples below demonstrate how to use the testing code.

These examples also indicate how your length, nth and reverse functions should behave.

% a.out
list = []
> length
0
list = []
> append 4
list = [4]
> append 5
list = [4, 5]
> append 6
list = [4, 5, 6]
> append 7
list = [4, 5, 6, 7]
> append 8
list = [4, 5, 6, 7, 8]
> length
5
list = [4, 5, 6, 7, 8]
> nth 0
4
list = [4, 5, 6, 7, 8]
> nth 3
7
list = [4, 5, 6, 7, 8]
> nth 5
nth: bad list index 5
0
list = [4, 5, 6, 7, 8]
> reverse
list = [8, 7, 6, 5, 4]

Finished?

After your tutor has checked that your functions are correct and given you the lab mark, you must also submit your answers using give. Here is the command to use:

% /home/cs1721/bin/classrun -give lab09 list.c