COMP1511 Week 12 Laboratory Sample Solutions

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/adams/A/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) {
    if (head == NULL) {
        // list is empty no node to delete
        return NULL;
    }
    struct node *new_head = head->next;
    free(head);
    return new_head;
}

A recursive solution for delete_first

struct node *delete_first(struct node *head) {
    if (head == NULL) {
        return NULL;
    }
    struct node *new_head = head->next;
    free(head);
    return new_head;
}

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

A recursive solution for delete_last

struct node *delete_last(struct node *head) {
    if (head == NULL) {
        return NULL;
    }
    if (head->next == NULL) {
        // list has one node, head is now NULL
        free(head);
        return NULL;
    }
    head->next = delete_last(head->next);
    return head;
}

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) {
    if (head == NULL) {
        // list is empty no node to delete
        return NULL;
    }
    if (head->data == i) {
        struct node *new_head = head->next;
        free(head);
        return new_head;
    }
    if (head->next == NULL) {
        return head;
    }

    struct node *n = head;
    // 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;
    }
    return head;
}

A recursive solution for delete_contains

struct node *delete_contains(int i, struct node *head) {
    if (head == NULL) {
        return NULL;
    }
    if (head->data == i) {
        struct node *new_head = head->next;
        free(head);
        return new_head;
    }
    head->next = delete_contains(i, head->next);
    return head;
}

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) {
    if (head == NULL) {
        return NULL;
    }
    struct node *previous = NULL;
    struct node *x = head;
    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
    if (head == NULL || head->next == NULL) {
        return head;
    }

    //reverse rest of list
    struct node *new_head = reverse(head->next);

    // head->next will be the last element in the reversed rest of list
    // append head to it
    head->next->next = head;
    head->next = NULL;

    return new_head;
}

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]

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) {
    if (head == NULL) {
        // list is empty no node to delete
        return NULL;
    }
    struct node *new_head = head->next;
    free(head);
    return new_head;
}

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

// 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) {
    if (head == NULL) {
        // list is empty no node to delete
        return NULL;
    }
    if (head->data == i) {
        struct node *new_head = head->next;
        free(head);
        return new_head;
    }
    if (head->next == NULL) {
        return head;
    }

    struct node *n = head;
    // 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;
    }
    return head;
}

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

struct node *reverse(struct node *head) {
    if (head == NULL) {
        return NULL;
    }
    struct node *previous = NULL;
    struct node *x = head;
    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

void print_list(struct node *head);
struct node *create_node(int data, struct node *next);
struct node *last(struct node *head);
int length(struct node *head);
struct node *append(struct node *head, int value);
void free_list(struct node *head);
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];
    struct node *list_head = NULL;

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

        printf("list = ");
        print_list(list_head);
        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
            free_list(list_head);
            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) {
            list_head = append(list_head, argument);
            continue; // need to skip check_list
        } else if (strcmp(line, "delete_first") == 0) {
            list_head = delete_first(list_head);
        } else if (strcmp(line, "delete_last") == 0) {
            list_head = delete_last(list_head);
        } else if (strcmp(line, "delete_contains") == 0) {
            list_head = delete_contains(argument, list_head);
        } else if (strcmp(line, "reverse") == 0) {
            list_head = reverse(list_head);
        } 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

void print_list(struct node *head) {
    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) {
    if (head == NULL) {
        return NULL;
    }

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

// return length of list

int length(struct node *head) {
    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);
    if (head == 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 */
        return head;
    }
}

// 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;
}

void free_list(struct node *head) {
    struct node *n = head;
    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.

// detect clang address-sanitizer
#ifdef __has_feature
#if __has_feature(address_sanitizer)
// clang address-sanitizer
#define HAVE_ASAN
#endif
#endif

// detect gcc address-sanitizer
#ifdef __SANITIZE_ADDRESS__
#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
    void *region_address;
    size_t region_size;
    if (strcmp(__asan_locate_address(p, name, sizeof name, &region_address, &region_size), "heap") != 0)
        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;
    if ((pointer_description = check_address_is_heap_pointer(head, sizeof *head))) {
        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_first(struct node *head);
struct node *delete_last(struct node *head);
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) {
    if (head == NULL) {
        return NULL;
    }
    struct node *new_head = head->next;
    free(head);
    return new_head;
}

// 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) {
    if (head == NULL) {
        return NULL;
    }
    if (head->next == NULL) {
        // list has one node, head is now NULL
        free(head);
        return NULL;
    }
    head->next = delete_last(head->next);
    return head;
}

// 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) {
    if (head == NULL) {
        return NULL;
    }
    if (head->data == i) {
        struct node *new_head = head->next;
        free(head);
        return new_head;
    }
    head->next = delete_contains(i, head->next);
    return head;
}

// 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
    if (head == NULL || head->next == NULL) {
        return head;
    }

    //reverse rest of list
    struct node *new_head = reverse(head->next);

    // head->next will be the last element in the reversed rest of list
    // append head to it
    head->next->next = head;
    head->next = NULL;

    return new_head;
}

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

void print_list(struct node *head);
struct node *create_node(int data, struct node *next);
struct node *last(struct node *head);
int length(struct node *head);
struct node *append(struct node *head, int value);
void free_list(struct node *head);
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];
    struct node *list_head = NULL;

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

        printf("list = ");
        print_list(list_head);
        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
            free_list(list_head);
            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) {
            list_head = append(list_head, argument);
            continue; // need to skip check_list
        } else if (strcmp(line, "delete_first") == 0) {
            list_head = delete_first(list_head);
        } else if (strcmp(line, "delete_last") == 0) {
            list_head = delete_last(list_head);
        } else if (strcmp(line, "delete_contains") == 0) {
            list_head = delete_contains(argument, list_head);
        } else if (strcmp(line, "reverse") == 0) {
            list_head = reverse(list_head);
        } 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

void print_list(struct node *head) {
    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) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    return last(head->next);
}

// return length of list

int length(struct node *head) {
    if (head == NULL) {
        return 0;
    }
    return 1 + length(head->next);
}

// 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);
    if (head == 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 */
        return head;
    }
}

// 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;
}

void free_list(struct node *head) {
    if (head != NULL) {
        free_list(head->next);
        free(head);
    }
}

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

// detect clang address-sanitizer
#ifdef __has_feature
#if __has_feature(address_sanitizer)
// clang address-sanitizer
#define HAVE_ASAN
#endif
#endif

// detect gcc address-sanitizer
#ifdef __SANITIZE_ADDRESS__
#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
    void *region_address;
    size_t region_size;
    if (strcmp(__asan_locate_address(p, name, sizeof name, &region_address, &region_size), "heap") != 0)
        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;
    if ((pointer_description = check_address_is_heap_pointer(head, sizeof *head))) {
        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).