COMP1511 17s1 Introduction to Programming

### Objectives

In these revision lab exercises you will revise topics relevant to the week 13/14 exam.
• Computation over linked lists.
• Changing 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 `lab13` by typing:

```mkdir lab13
```
Change to this directory by typing:
```cd lab13
```

### Introduction

These revision exercises are designed to prepare you for the mid-session exam.

These revision exercises are not assessable.

They do not get marked.

There is no need to submit them with give.

The file lab13.c is the starting point for the revision 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 node {
struct node *next;
int          data;
};
```

Start by copying lab13.c:

```cp /import/chopin/1/cs1511/public_html/17s1/tlb/13/lab13.c .
```
lab13.c contains five functions which have not been implemented. Your task is to implement these five functions.

### Revision Exercise: Count List Elements Containing Value

lab13.c contains a function with this prototype:

``` int count(int value, struct node *list) ```

Implement count.

count should return the number of nodes in the list containing value.

As usual autotest is available to test your code:

``` ~cs1511/bin/autotest lab13 count
```

### Revision Exercise: Get n-th List element

lab13.c contains a function with this prototype:

``` struct node *get_nth(int n, struct node *head) ```

Implement get_nth.

get_nth should return a pointer to the node in position n in the list.

Position 0 is the first node in the list.

get_nth should return NULL if the list has no n-th node.

As usual autotest is available to test your code:

``` ~cs1511/bin/autotest lab13 get_nth
```

### Revision Exercise: Delete n-th List element

lab13.c contains a function with this prototype:

``` struct node *delete_nth(int n, struct node *head) ```

Implement delete_nth.

delete_nth should delete the node in position n in the list.

delete_nth should free the deleted node.

delete_nth should make no changes if there is no position n in the list.

delete_nth should return the (possibly changed) head of the list.

As usual autotest is available to test your code:

``` ~cs1511/bin/autotest lab13 delete_nth
```

### Revision Exercise: Delete Odd List elements

lab13.c contains a function with this prototype:

``` struct node *delete_odd(struct node *head) ```

Implement delete_odd.

delete_odd should delete all nodes in the list containing odd numbers.

delete_odd should free any deleted nodes.

delete_odd should return the (possibly changed) head of the list.

As usual autotest is available to test your code:

``` ~cs1511/bin/autotest lab13 delete_odd
```

### Revision Exercise: Insert n-th List element

lab13.c contains a function with this prototype:

``` struct node *insert_nth(int n, struct node *new_node, struct node *head) ```

Implement insert_nth.

insert_nth should insert new_node before position n in the list.

Given a position immediately after the last element in the list (n == length of the list) insert_nth should append new_node to the list.

insert_nth should otherwise make no changes if there is no position n in the list.

insert_nth should return the (possibly changed) head of the list.

As usual autotest is available to test your code:

``` ~cs1511/bin/autotest lab13 insert_nth
```

### 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.

Memory must be freed for nodes removed from the list.

### Hints

If you change the first item in a list either by deleting or inserting a new item, you will need to return a new value for the head of a list.

Positions are numbered like array indices. The first node in the list is regarded as being in position 0. The last node in a list of length n is regarded as being in position n - 1.

### Testing Your Functions

The `main` function in `lab13.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 lab13.c -o lab13
./lab13
list = []
> append 4
list = [4]
> append 5
list = [4, 5]
> append 6
list = [4, 5, 6]
> append 7
list = [4, 5, 6, 7]
> append 6
list = [4, 5, 6, 7, 6]
> count 42
count(42) returns 0
list = [4, 5, 6, 7, 6]
> count 5
count(5) returns 1
list = [4, 5, 6, 7, 6]
> count 6
count(6) returns 2
list = [4, 5, 6, 7, 6]
> get_nth 0
get_nth(0) returned a pointer to a node containing 4
list = [4, 5, 6, 7, 6]
> get_nth 42
get_nth(42) returned NULL
list = [4, 5, 6, 7, 6]
> get_nth -1
get_nth(-1) returned NULL
list = [4, 5, 6, 7, 6]
> delete_nth 2
list = [4, 5, 7, 6]
> delete_nth 0
list = [5, 7, 6]
> delete_nth 0
list = [7, 6]
> insert_nth 0
list = [42, 7, 6]
> insert_nth 2
list = [42, 7, 42, 6]
> insert_nth 4
list = [42, 7, 42, 6, 42]
> delete_odd
list = [42, 42, 6, 42]
```
Note the test of insert_nth always insert a node containing 42.

### Submission/Assessment

These revision exercises are not assessable.

They do not get marked.

There is no need to submit them with give.