COMP1511 17s1 Introduction to Programming

### Objectives

In this Lab, you will practise:

### 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
```
An iterative solution for `delete_first`
```struct node *delete_first(struct node *head) {
// list is empty no node to delete
return NULL;
}
}

```
A recursive solution for `delete_first`
```struct node *delete_first(struct node *head) {
return NULL;
}
}

```

### 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
```
An iterative solution for `delete_last`
```struct node *delete_last(struct node *head) {
// list is empty no node to delete
return NULL;
}
// list has one node, head is now NULL
return NULL;
}
// find second last node in list
while (n->next->next != NULL) {
n = n->next;
}
free(n->next);
n->next = NULL;
}

```
A recursive solution for `delete_last`
```struct node *delete_last(struct node *head) {
return NULL;
}
// list has one node, head is now NULL
return NULL;
}
}

```

### 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
```
An iterative solution for `delete_contains`
```struct node *delete_contains(int i, struct node *head) {
// list is empty no node to delete
return NULL;
}
}
}

// find node before first node containing i
while (n->next->next != NULL && n->next->data != i) {
n = n->next;
}

if (n->next->data == i) {
struct node *new_next = n->next->next;
free(n->next);
n->next = new_next;
}
}

```
A recursive solution for `delete_contains`
```struct node *delete_contains(int i, struct node *head) {
return NULL;
}
}
}

```

### 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
```
An iterative solution for `reverse`
```struct node *reverse(struct node *head) {
return NULL;
}
struct node *previous = NULL;
while (x != NULL) {
struct node *y = x->next;
x->next = previous;
previous = x;
x = y;
}
return previous;
}

```
A recursive solution for `reverse`
```struct node *reverse(struct node *head) {
// lists of 0 or 1 node don't need to be changed
}

//reverse rest of list

// head->next will be the last element in the reversed rest of list

}

```

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

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]
```

A complete iterative solution for `lab12.c`
```#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

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

// Delete the first node in list.
// The deleted node is freed.
// The head of the list is returned.

struct node *delete_first(struct node *head) {
// list is empty no node to delete
return NULL;
}
}

// Delete the last node in list.
// The deleted node is freed.
// The head of the list is returned.

struct node *delete_last(struct node *head) {
// list is empty no node to delete
return NULL;
}
// list has one node, head is now NULL
return NULL;
}
// find second last node in list
while (n->next->next != NULL) {
n = n->next;
}
free(n->next);
n->next = NULL;
}

// Delete the first node in the containing i
// The deleted node is freed.
// If no node contains i, the list is not changed
// The head of the list is returned.

struct node *delete_contains(int i, struct node *head) {
// list is empty no node to delete
return NULL;
}
}
}

// find node before first node containing i
while (n->next->next != NULL && n->next->data != i) {
n = n->next;
}

if (n->next->data == i) {
struct node *new_next = n->next->next;
free(n->next);
n->next = new_next;
}
}

// Place the list into reverse order.
// The head of the list is returned.

struct node *reverse(struct node *head) {
return NULL;
}
struct node *previous = NULL;
while (x != NULL) {
struct node *y = x->next;
x->next = previous;
previous = x;
x = y;
}
return previous;
}

// THE CODE BELOW HERE IS TO TEST YOUR FUNCTIONS
// DO NOT CHANGE IT

struct node *create_node(int data, struct node *next);
struct node *append(struct node *head, int value);
static void check_list(struct node *head, char *name, int original_list_length, struct node *original_nodes[], int original_data_fields[]);

#define MAX_LINE 4096

// simple main function to test delete_first, delete_last, delete_contains, reverse

int
main(int argc, char *argv[]) {
char line[MAX_LINE];

while (1) {
// save state of of list so we can check student functions
// only perform permitted operations
struct node *nodes[list_length+1]; // ensure non-zero length for VLA
int data[list_length+1];
int j = 0;
while (n != NULL) {
nodes[j] = n;
data[j] = n->data;
n = n->next;
j++;
}

printf("list = ");
printf("\n");

printf("> ");
if (fgets(line, MAX_LINE, stdin) == NULL) {
// free memory even though program is exiting
// so we can check for memory not freed by other functions
// by running dcc --leak-check
return 0;
}

int i = 0;
while (isalpha(line[i]) || line[i] == '_') {
i++;
}
int argument = atoi(&line[i]);
line[i] = '\0';

if (strcmp(line, "append") == 0) {
continue; // need to skip check_list
} else if (strcmp(line, "delete_first") == 0) {
} else if (strcmp(line, "delete_last") == 0) {
} else if (strcmp(line, "delete_contains") == 0) {
} else if (strcmp(line, "reverse") == 0) {
} else if (strcmp(line, "") != 0) {
printf("Unknown command: '%s'\n", line);
}

check_list(list_head, "returned list", list_length, nodes, data);
}
}

// print contents of list in Python syntax

printf("[");
for (struct node *n = head; n != NULL; n = n->next) {
printf("%d", n->data);
if (n->next != NULL) {
printf(", ");
}
}
printf("]");
}

// return pointer to last node in list
// NULL is returned if list is empty

struct node *last(struct node *head) {
return NULL;
}

while (n->next != NULL) {
n = n->next;
}
return n;
}

// return length of list

int len = 0;
for (struct node *n = head; n != NULL; n = n->next) {
len++;
}
return len;
}

// create a new list node containing value
// and append it to end of list

struct node *append(struct node *head, int value) {
// new node will be last in list, so next field is NULL
struct node *n =  create_node(value, NULL);
// new node is now  head of the list
return n;
} else {
// change next field of last list node
// from NULL to new node
last(head)->next = n;  /* append node to list */
}
}

// Create a new struct node containing the specified data,
// and next fields, return a pointer to the new struct node.

struct node *create_node(int data, struct node *next) {
struct node *n;

n = malloc(sizeof (struct node));
if (n == NULL) {
fprintf(stderr, "out of memory\n");
exit(1);
}
n->data = data;
n->next = next;
return n;
}

while (n != NULL) {
struct node *next_node = n->next;
free(n);
n = next_node;
}
}

// You are not expected to understand the following code.
// It uses complex internal compiler features to
// print informative messages for student errors.

#ifdef __has_feature
#define HAVE_ASAN
#endif
#endif

#define HAVE_ASAN
#endif

#ifdef HAVE_ASAN
#include <sanitizer/asan_interface.h>
#include <stdint.h>
#include <string.h>

// return NULL if p appears to be a valid pointer to a malloc'ed region of size size
// otherwise return string describing pointer

static char *check_address_is_heap_pointer(void *p, size_t size) {
if (!p)
return NULL;
if ((sizeof(p) == 8 && (uintptr_t)p == 0xbebebebebebebebe) || (sizeof(p) == 4 && (uintptr_t)p == 0xbebebebe))
return "uninitialized";
if (__asan_region_is_poisoned(p, size))
return "invalid";
char name[8]; // unused but required by __asan_locate_address
size_t region_size;
return "invalid (not from malloc)";
return NULL;
}

// Use address-sanitizer and other methods to detect invalid pointers in a malloc'ed linked list
// name should be a string describing the list
// If original_nodes != NULL then every node is checked to ensure it is the array original_nodes
// If original_data_fields != NULL then every data field is checked to see if matches the element
// of original_data_fields at the same index as it node appears in original_nodes
// original_nodes and original_data_fields should be of length original_list_length

static void check_list(struct node *head, char *name, int original_list_length, struct node *original_nodes[], int original_data_fields[]) {
char *pointer_description;
fprintf(stderr, "\nError: the head of %s is %s (%p)\n", name, pointer_description, head);
exit(1);
}
int position = 0;
for (struct node *n = head; n != NULL; n = n->next, position++) {
// If you're getting an error here,
// you have returned an invalid list
int error = 0;
if ((unsigned)n->data == 0xbebebebe) {
fprintf(stderr, "Error: %s is invalid.\n", name);
fprintf(stderr, "       The data field of node %d is uninitialized.\n", position);
error = 1;
}
if ((pointer_description = check_address_is_heap_pointer(n->next, sizeof *(n->next)))) {
if (!error)
fprintf(stderr, "Error: %s is invalid.\n", name);
fprintf(stderr, "       The next field of node %d is %s (%p).\n", position, pointer_description, n->next);
error = 1;
}
if (error) {
if (position) {
fprintf(stderr, "       The data fields of nodes 0..%d in the list contain: [", position);
for (struct node *m = head; m != n; m = m->next) {
fprintf(stderr, "%d, ", m->data);
}
fprintf(stderr, "%d]\n", n->data);
}
exit(1);
}

int position1 = 0;
for (struct node *o = head;; o = o->next, position1++) {
if (o == n->next) {
if (position == position1) {
fprintf(stderr, "Error: %s is invalid.\n", name);
fprintf(stderr, "       The next field of node %d points to itself\n", position);
} else  {
fprintf(stderr, "Error: %s is invalid.\n", name);
fprintf(stderr, "       The next field of node %d points to node %d.\n", position, position1);
fprintf(stderr, "       In other words, %s is circular.\n", name);
}
exit(1);
}
if (o == n)
break;
}

if (original_list_length && original_nodes) {
int i;
for (i = 0; i < original_list_length; i++) {
if (original_nodes[i] == n)
break;
}

if (i == original_list_length) {
fprintf(stderr, "Error: %s is invalid.\n", name);
fprintf(stderr, "       The node in position %d is not in the list it was given.\n", position);
fprintf(stderr, "       Do not create new nodes with malloc\n");
exit(1);
}

if (original_data_fields && original_data_fields[i] != n->data) {
fprintf(stderr, "Error: %s is invalid.\n", name);
fprintf(stderr, "       The node in position %d data field has been changed from %d to %d.\n", position, original_data_fields[i], n->data);
fprintf(stderr, "       Do not change the data fields of nodes\n");
exit(1);
}
}
}
}
#else
static void check_list(struct node *head, char *name, int original_list_length, struct node *original_nodes[], int original_data_fields[]) {
}
#endif

```
A complete recursive solution for `lab12.c`
```#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

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

struct node *delete_contains(int i, struct node *head);
struct node *reverse(struct node *list);

// Delete the first node in list.
// The deleted node is freed.
// The head of the list is returned.

struct node *delete_first(struct node *head) {
return NULL;
}
}

// Delete the last node in list.
// The deleted node is freed.
// The head of the list is returned.

struct node *delete_last(struct node *head) {
return NULL;
}
// list has one node, head is now NULL
return NULL;
}
}

// Delete the first node in the containing i
// The deleted node is freed.
// If no node contains i, the list is not changed
// The head of the list is returned.

struct node *delete_contains(int i, struct node *head) {
return NULL;
}
}
}

// Place the list into reverse order.
// The head of the list is returned.

struct node *reverse(struct node *head) {
// lists of 0 or 1 node don't need to be changed
}

//reverse rest of list

// head->next will be the last element in the reversed rest of list

}

// THE CODE BELOW HERE IS TO TEST YOUR FUNCTIONS
// DO NOT CHANGE IT

struct node *create_node(int data, struct node *next);
struct node *append(struct node *head, int value);
static void check_list(struct node *head, char *name, int original_list_length, struct node *original_nodes[], int original_data_fields[]);
#define MAX_LINE 4096

// simple main function to test delete_first, delete_last, delete_contains, reverse

int
main(int argc, char *argv[]) {
char line[MAX_LINE];

while (1) {
// save state of of list so we can check student functions
// only perform permitted operations
struct node *nodes[list_length+1]; // ensure non-zero length for VLA
int data[list_length+1];
int j = 0;
while (n != NULL) {
nodes[j] = n;
data[j] = n->data;
n = n->next;
j++;
}

printf("list = ");
printf("\n");

printf("> ");
if (fgets(line, MAX_LINE, stdin) == NULL) {
// free memory even though program is exiting
// so we can check for memory not freed by other functions
// by running dcc --leak-check
return 0;
}

int i = 0;
while (isalpha(line[i]) || line[i] == '_') {
i++;
}
int argument = atoi(&line[i]);
line[i] = '\0';

if (strcmp(line, "append") == 0) {
continue; // need to skip check_list
} else if (strcmp(line, "delete_first") == 0) {
} else if (strcmp(line, "delete_last") == 0) {
} else if (strcmp(line, "delete_contains") == 0) {
} else if (strcmp(line, "reverse") == 0) {
} else if (strcmp(line, "") != 0) {
printf("Unknown command: '%s'\n", line);
}

check_list(list_head, "returned list", list_length, nodes, data);
}
}

// print contents of list in Python syntax

printf("[");
for (struct node *n = head; n != NULL; n = n->next) {
printf("%d", n->data);
if (n->next != NULL) {
printf(", ");
}
}
printf("]");
}

// return pointer to last node in list
// NULL is returned if list is empty

struct node *last(struct node *head) {
}
}

// return length of list

return 0;
}
}

// create a new list node containing value
// and append it to end of list

struct node *append(struct node *head, int value) {
// new node will be last in list, so next field is NULL
struct node *n =  create_node(value, NULL);
// new node is now  head of the list
return n;
} else {
// change next field of last list node
// from NULL to new node
last(head)->next = n;  /* append node to list */
}
}

// Create a new struct node containing the specified data,
// and next fields, return a pointer to the new struct node.

struct node *create_node(int data, struct node *next) {
struct node *n;

n = malloc(sizeof (struct node));
if (n == NULL) {
fprintf(stderr, "out of memory\n");
exit(1);
}
n->data = data;
n->next = next;
return n;
}

}
}

// You are not expected to understand the following code.
// It uses complex internal compiler features to
// print informative messages for student errors.

#ifdef __has_feature
#define HAVE_ASAN
#endif
#endif

#define HAVE_ASAN
#endif

#ifdef HAVE_ASAN
#include <sanitizer/asan_interface.h>
#include <stdint.h>
#include <string.h>

// return NULL if p appears to be a valid pointer to a malloc'ed region of size size
// otherwise return string describing pointer

static char *check_address_is_heap_pointer(void *p, size_t size) {
if (!p)
return NULL;
if ((sizeof(p) == 8 && (uintptr_t)p == 0xbebebebebebebebe) || (sizeof(p) == 4 && (uintptr_t)p == 0xbebebebe))
return "uninitialized";
if (__asan_region_is_poisoned(p, size))
return "invalid";
char name[8]; // unused but required by __asan_locate_address
size_t region_size;
return "invalid (not from malloc)";
return NULL;
}

// Use address-sanitizer and other methods to detect invalid pointers in a malloc'ed linked list
// name should be a string describing the list
// If original_nodes != NULL then every node is checked to ensure it is the array original_nodes
// If original_data_fields != NULL then every data field is checked to see if matches the element
// of original_data_fields at the same index as it node appears in original_nodes
// original_nodes and original_data_fields should be of length original_list_length

static void check_list(struct node *head, char *name, int original_list_length, struct node *original_nodes[], int original_data_fields[]) {
char *pointer_description;
fprintf(stderr, "\nError: the head of %s is %s (%p)\n", name, pointer_description, head);
exit(1);
}
int position = 0;
for (struct node *n = head; n != NULL; n = n->next, position++) {
// If you're getting an error here,
// you have returned an invalid list
int error = 0;
if ((unsigned)n->data == 0xbebebebe) {
fprintf(stderr, "Error: %s is invalid.\n", name);
fprintf(stderr, "       The data field of node %d is uninitialized.\n", position);
error = 1;
}
if ((pointer_description = check_address_is_heap_pointer(n->next, sizeof *(n->next)))) {
if (!error)
fprintf(stderr, "Error: %s is invalid.\n", name);
fprintf(stderr, "       The next field of node %d is %s (%p).\n", position, pointer_description, n->next);
error = 1;
}
if (error) {
if (position) {
fprintf(stderr, "       The data fields of nodes 0..%d in the list contain: [", position);
for (struct node *m = head; m != n; m = m->next) {
fprintf(stderr, "%d, ", m->data);
}
fprintf(stderr, "%d]\n", n->data);
}
exit(1);
}

int position1 = 0;
for (struct node *o = head;; o = o->next, position1++) {
if (o == n->next) {
if (position == position1) {
fprintf(stderr, "Error: %s is invalid.\n", name);
fprintf(stderr, "       The next field of node %d points to itself\n", position);
} else  {
fprintf(stderr, "Error: %s is invalid.\n", name);
fprintf(stderr, "       The next field of node %d points to node %d.\n", position, position1);
fprintf(stderr, "       In other words, %s is circular.\n", name);
}
exit(1);
}
if (o == n)
break;
}

if (original_list_length && original_nodes) {
int i;
for (i = 0; i < original_list_length; i++) {
if (original_nodes[i] == n)
break;
}

if (i == original_list_length) {
fprintf(stderr, "Error: %s is invalid.\n", name);
fprintf(stderr, "       The node in position %d is not in the list it was given.\n", position);
fprintf(stderr, "       Do not create new nodes with malloc\n");
exit(1);
}

if (original_data_fields && original_data_fields[i] != n->data) {
fprintf(stderr, "Error: %s is invalid.\n", name);
fprintf(stderr, "       The node in position %d data field has been changed from %d to %d.\n", position, original_data_fields[i], n->data);
fprintf(stderr, "       Do not change the data fields of nodes\n");
exit(1);
}
}
}
}
#else
static void check_list(struct node *head, char *name, int original_list_length, struct node *original_nodes[], int original_data_fields[]) {
}
#endif

```

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