Objectives

In this Lab, you will practise:

• Manipulating linked lists.

Preparation

Before the lab you should re-read the relevant lecture slides and their accompanying examples. You should also have read the lab assessment guidelines.

Getting Started

One member of your programming pair should login and run the following commands inside a Linux terminal

Create a new directory for this lab called lab12 by typing:

mkdir lab12

Change to this directory by typing:

cd lab12

Introduction

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

It contains struct node, which is used to store a sequence of integers. This is the same data representation you have seen in lectures.

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

Start by copying lab12.c:

cp /import/chopin/1/cs1511/public_html/17s1/tlb/12/lab12.c .

lab12.c contains four functions which have not been implemented. Your task is to implement these four functions.

Exercise: Delete First Node in List

lab12.c contains a function with this prototype: struct node *delete_first(struct node *list) Implement delete_first.

delete_first should delete the first node from list.

delete_first should return the first_node in the list.

As usual autotest is available to test your code:

 ~cs1511/bin/autotest lab12 delete_first

Exercise: Delete Last Node in List

lab12.c contains a function with this prototype: struct node *delete_last(struct node *list) Implement delete_last.

delete_last should delete the first node from list.

delete_last should return the first_node in the list. As usual autotest is available to test your code:

 ~cs1511/bin/autotest lab12 delete_last

Exercise: Delete First Node in List Containing Specified Value

lab12.c contains a function with this prototype: struct node *delete_contains(int i, struct node *list) Implement delete_contains.

delete_contains should delete the first node from list whose data field contains the value i.

delete_contains should return the first_node in the list.

As usual autotest is available to test your code:

 ~cs1511/bin/autotest lab12 delete_contains

Exercise: Reverse List

lab12.c contains a function with this prototype: struct node *reverse(struct node *list) Implement reverse.

reverse should rearrange the list to be in reverse order.

reverse should return the first_node in the list.

As usual autotest is available to test your code:

 ~cs1511/bin/autotest lab12 reverse

Requirements

Your functions must not create any new nodes.

Your functions must not call malloc.

Your functions must not call create_node.

Your functions must not change the data field of any node.

Your functions may change the next field of nodes.

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.

Hints

If you delete the first item in a list you will need to return a new value for the head of a list.

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

Testing Your Functions

The main function in lab12.c contains code which allows you to test your functions.

The examples below demonstrate how to use the testing code.

These examples also indicate how your functions should behave.

dcc lab12.c -o lab12
./lab12
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]
> delete_first
list = [5, 6, 7, 8]
> delete_last
list = [5, 6, 7]
> delete_first
list = [6, 7]
> delete_last
list = [6]
> delete_first
list = []
> delete_last
list = []
> delete_first
list = []
> append 4
list = [4]
> append 5
list = [4, 5]
> append 5
list = [4, 5, 5]
> append 4
list = [4, 5, 5, 4]
> append 6
list = [4, 5, 5, 4, 6]
> delete_contains 4
list = [5, 5, 4, 6]
> delete_contains 4
list = [5, 5, 6]
> delete_contains 5
list = [5, 6]
> delete_contains 5
list = [6]
> delete_contains 42
list = [6]
> delete_contains 6
list = []
> delete_contains 42
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]
> reverse
list = [8, 7, 6, 5, 4]
> reverse
list = [4, 5, 6, 7, 8]

Challenge Exercises

No challenge exercises this week (maximum grade your tutor will award is A)

Submission/Assessment

When you are satisfied with your work, ask your tutor to assess it. You also need to submit your work electronically by typing (run this command in the lab12 directory):

give cs1511 lab12 lab12.c

Submit the challenge exercises only if you attempt them.

If you are working at home, you may find it more convenient to upload your work via give's web interface.

Remember the lab assessment guidelines - if you don't finish the exercises you can finish them in your own time, submit them by Monday 11:00am using give and ask your tutor to assess them at the start of the following lab.

Either or both members of a programming pair can submit the work (make sure each program lists both of you as authors in the header comment).