Programming Fundamentals

• working with structs and pointers
• introducing linked lists
• using memory allocation

Help sessions are running this week!

These are one of the best ways for you to get one on one help with a tutor for any course content (including Lab Exercises and Assignments).

For the dates and times of the help sessions, see the Help Session Timetable.

To join a help session, or for more information, see the COMP(1511|1911) Help Session Microsoft Teams.

For face-to-face help sessions, the lab map can be found here. If help sessions are running in other buildings you can use Lost on Campus to help you find them.

The following is a list of all the activities available to complete this week...

Worth 1 mark(s) in total:

• mallocd_array
• list_print
• list_length
• list_insert_head
• debug_insert_second_last

Worth 1 mark(s) in total:

• list_contains
• list_insert_tail
• list_get_nth_v2
• list_insert_nth

Worth 0.5 mark(s) in total:

• lock_picking
• list_reverse

For your interest, but not for marks:

• student_becomes_teacher

Problem sets are capped at 15 marks (there are 4 possible bonus marks from the three-dot exercises that can bring you up to a total of 15 if you missed out on any other marks in the one- or two-dot exercises).

Completing just the one and two-dot exercises every week can give you the full 15 marks needed in this component.

For more details, see the course outline.

Before the lab you should re-read the relevant lecture slides and their accompanying examples.

When attempting the following exercises, make sure to read the whole exercise, including any hints and assumptions that may make the exercise easier.

Download mallocd_array.c here

Or, copy these file(s) to your CSE account using the following command:

1511 fetch-activity mallocd_array

Your task is to add code to these functions in mallocd_array.c:

// A function which scans in `size` integers and stores them into a 
// malloc'd array.
// returns: a pointer to the malloc'd array
int *scan_array(int size) {
    // TODO: 1. create a MALLOC'd array of size `size`

    // TODO: 2. Loop through and scan values into the array.

    // TODO 3.delete the following line and return the array.
    return NULL;
}

// Given an integer array and it's size, 
// returns the sum of all elements inside the array, divided by the size of the
// array.
double calculate_average(int *array, int size) {
    
    // TODO calculate the sum of the array.

    return 0;
}

Complete the C program, mallocd_array.c.

The main function has already been written for you. You must not modify it in any way.

Examples

dcc mallocd_array.c -o mallocd_array
./mallocd_array
Enter size: 5
Enter 5 integers:
1
2
3
4
5
The average of all values in the array is: 3.00
./mallocd_array
Enter size: 1
Enter 1 integers:
10
The average of all values in the array is: 10.00
./mallocd_array
Enter size: 3
Enter 3 integers:
5
-4
-3
The average of all values in the array is: -0.67

Assumptions/Restrictions/Clarifications

• You do not need to handle memory leaks for this exercise. i.e. You should not call free
• All inputs be of the correct type

1511 style mallocd_array.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest mallocd_array

When you are finished working on this exercise, you must submit your work by running give:

give cs1511 lab08_mallocd_array mallocd_array.c

You must run give before Monday 04 November 20:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

// Written by lorenzo lee solano
// June, 2022

#include <stdio.h>
#include <stdlib.h>

//////////////// DO NOT CHANGE ANY OF THE CODE BELOW HERE //////////////////
int *scan_array(int size);
double calculate_average(int *array, int size);

int main (void) {

    int size;
    printf("Enter size: ");
    scanf(" %d", &size);
    if (size <= 0) {
        printf("Invalid Size\n");
        return 1;
    }

    printf("Enter %d integers:\n", size);
    int *array = scan_array(size);

    printf("The average of all values in the array is: %.2lf\n", 
           calculate_average(array, size));

    return 0;
}
//////////////// DO NOT CHANGE ANY OF THE CODE ABOVE HERE //////////////////

////////////////////////////////////////////////////////////////////////////
///////////////////// ONLY WRITE CODE BELOW HERE ///////////////////////////
////////////////////////////////////////////////////////////////////////////

// A function which scans in `size` integers and stores them into a 
// malloc'd array.
// returns: a pointer to the malloc'd array
int *scan_array(int size) {
    int i = 0;
    int *array = malloc(sizeof(int) * size);
    while (i < size) {
        scanf(" %d", &array[i]);
        i++;
    }

    return array;
}

// Given an integer array and it's size, 
// returns the sum of all elements inside the array, divided by the size of the
// array.
double calculate_average(int *array, int size) {
    int i = 0;
    int sum = 0;
    while (i < size ) {
        sum += array[i];
        i++;
    }
    return 1.0 * sum/size;
}

////////////////////////////////////////////////////////////////////////////
///////////////////// ONLY WRITE CODE ABOVE HERE ///////////////////////////
////////////////////////////////////////////////////////////////////////////

Download list_print.c here

Or, copy these file(s) to your CSE account using the following command:

1511 fetch-activity list_print

Your task is to add code to this function in list_print.c:

// print a linked list in this format:
// 17 -> 34 -> 51 -> 68 -> X
void print(struct node *head) {

    // PUT YOUR CODE HERE
}

print is given one argument, head, which is the pointer to the first node in a linked list.

Your program will be supplied up to 50 integers, which will be put into a linked list that is passed to the print.

Add code to print so that it prints the elements in the list.

For example, if the linked list contains these 8 elements:

1, 7, 8, 9, 13, 19, 21, 42

print should print

1 -> 7 -> 8 -> 9 -> 13 -> 19 -> 21 -> 42 -> X

(including the X)

Testing

list_print.c also contains a main function which allows you to test your print function.

This main function:

• converts the input from terminal into a linked list
• assigns a pointer to the first node in the linked list to head
• calls list_print(head)

Do not change this function. If you want to change it, you have misread the question.

Your list_print function will be called directly in marking. The main function is only to let you test your list_print function.

Examples

dcc list_print.c -o list_print
./list_print
1 2 4 8 16 32 64 128 256

1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 64 -> 128 -> 256 -> X
./list_print
2 4 6 5 8 9

2 -> 4 -> 6 -> 5 -> 8 -> 9 -> X
./list_print
42 4

42 -> 4 -> X
./list_print
43

43 -> X
./list_print

X

Assumptions/Restrictions/Clarifications

• You can assume the input will never be more than 50 integers.
• print should not change the linked list it is given. Your function should not change the next or data fields of list nodes.
• print should not use arrays.
• print should not call malloc.
• print should not call scanf (or getchar or fgets).
• Do not change the supplied main function. It will not be tested or marked.

1511 style list_print.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest list_print

When you are finished working on this exercise, you must submit your work by running give:

give cs1511 lab08_list_print list_print.c

You must run give before Monday 04 November 20:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define MAX_LEN 50

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

void print(struct node *head);
struct node *array_to_list(int len, int num_array[]);

int main(void) {
    // create linked list from input
    int input_arr[MAX_LEN] = {0};
    int total_num = 0;
    int input_num;
    while (scanf(" %d", &input_num) == 1) {
        input_arr[total_num] = input_num;
        total_num++;
    }
    struct node *head = array_to_list(total_num, input_arr);

    print(head);

    return 0;
}

// Solution \/
////////////////////////////////////////////////////////////////////////////////
//  print a linked list in this format:
// 17 -> 34 -> 51 -> 68 -> X
void print(struct node *head) {
    struct node *n = head;
    while (n != NULL) {
        printf("%d -> ", n->data);
        n = n->next;
    }
    printf("X\n");
}
////////////////////////////////////////////////////////////////////////////////

// create linked list from array of strings
struct node *array_to_list(int len, int num_array[]) {
    struct node *head = NULL;
    for (int i = len - 1; i >= 0; i = i - 1) {
        struct node *n = malloc(sizeof(struct node));
        assert(n != NULL);
        n->next = head;
        n->data = num_array[i];
        head = n;
    }
    return head;
}

Download list_length.c here

Or, copy these file(s) to your CSE account using the following command:

1511 fetch-activity list_length

Your task is to add code to this function in list_length.c:

// Return the length of the linked list pointed by head
int length(struct node *head) {

    // PUT YOUR CODE HERE (change the next line!)
    return 42;

}

For this exercise, you will be given a linked list nodes containing integers, shown below.

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

Your job is to complete the length function.

length is given one argument, head, which is the pointer to the first node in a linked list.

Add code to length so that its returns the length of the list.

For example if the linked list contains these 8 elements:

1, 7, 8, 9, 13, 19, 21, 42

length should return 8.

Testing

list_length.c also contains a main function which allows you to test your length function.

This main function:

1. scans in number of items in the list, and its values; to create a linked list,
2. assigns a pointer to the first node in the linked list to head,
3. calls list_length(head), then
4. prints the result.

Do not change this function. If you want to change it, you have misread the question.

Your list_length function will be called directly in marking. The main function is only to let you test your list_length function

Examples

dcc list_length.c -o list_length
./list_length 
How many numbers in initial list?: 9
1 2 3 6 5 4 9 9 0
Counted 9 elements in linked list.
./list_length
How many numbers in initial list?: 6
1 2 3 6 5 4
Counted 6 elements in linked list.
./list_length
How many numbers in initial list?: 5
1 2 3 4 5
Counted 5 elements in linked list.
./list_length 
How many numbers in initial list?: 2
42 4
Counted 2 elements in linked list.
./list_length
How many numbers in initial list?: 0
Counted 0 elements in linked list.

Assumptions/Restrictions/Clarifications

• length should return a single integer
• length should not change the linked list it is given
• Your function should not change the next or data fields of list nodes
• length should not use arrays
• length should not call malloc
• length should not call scanf (or getchar or fgets)
• length should not print anything. It should not call printf
• Do not change the supplied main function. It will not be tested or marked

1511 style list_length.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest list_length

When you are finished working on this exercise, you must submit your work by running give:

give cs1511 lab08_list_length list_length.c

You must run give before Monday 04 November 20:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

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

int length(struct node *head);
struct node *strings_to_list(int len, char *strings[]);

int main(int argc, char *argv[]) {
    // create linked list from command line arguments
    struct node *head = strings_to_list(argc - 1, &argv[1]);

    int result = length(head);
    printf("%d\n", result);

    return 0;
}

// Return length of a linked list.
int length(struct node *head) {
    int len = 0;
    struct node *n = head;
    while (n != NULL) {
        len = len + 1;
        n = n->next;
    }
    return len;
}


// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
    struct node *head = NULL;
    for (int i = len - 1; i >= 0; i = i - 1) {
        struct node *n = malloc(sizeof(struct node));
        assert(n != NULL);
        n->next = head;
        n->data = atoi(strings[i]);
        head = n;
    }
    return head;
}

Download list_insert_head.c here

Or, copy these file(s) to your CSE account using the following command:

1511 fetch-activity list_insert_head

Your task is to add code to this function in list_insert_head.c:

// WRITE YOUR CODE INSIDE HERE ONLY!!!
// Insert a new node containing value at the start of the linked list.
// The head of the new list is returned.
struct node *insert_head(int value, struct node *head) {

    // PUT YOUR CODE HERE (change the next line!)
    return NULL;

}

insert_head is given two arguments, value and head.

• value is an int
• head is the pointer to the first node in a linked list

Add code to insert_head so that it creates a new list node (using malloc) containing value and places it at the start of the list.

insert_head should return a pointer to the new list.

For example if value is 12 and the linked list contains these 3 elements:

16, 7, 8

insert_head should return a pointer to a list with these elements:

12, 16, 7, 8

Testing

list_insert_head.c also contains a main function which allows you to test your insert_head function.

This main function:

1. converts the first set of read integers to a linked list,
2. assigns a pointer to the first node in the linked list to head
3. reads another single integer from standard input and assigns it to value
4. calls insert_head(value, head)
5. prints the result.

Do not change this function. If you want to change it, you have misread the question.

Your insert_head function will be called directly in marking. The main function is only to let you test your insert_head function

dcc list_insert_head.c -o list_insert_head
./list_insert_head
How many numbers in initial list?: 3
16 7 8
Enter number to insert to head: 
12
[12, 16, 7, 8]
./list_insert_head
How many numbers in initial list?: 1
16
Enter number to insert to head: 
42
[42, 16]
./list_insert_head
How many numbers in initial list?: 0
Enter number to insert to head: 
2
[2]

Assumptions/Restrictions/Clarifications

• insert_head should not use arrays
• insert_head should not call scanf (or getchar or fgets)
• insert_head should not print anything. It should not call printf
• Do not change the supplied main function. It will not be tested or marked

1511 style list_insert_head.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest list_insert_head

When you are finished working on this exercise, you must submit your work by running give:

give cs1511 lab08_list_insert_head list_insert_head.c

You must run give before Monday 04 November 20:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

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

struct node *insert_head(int value, struct node *head);
struct node *array_to_list(int len, int array[]);
void print_list(struct node *head);

// DO NOT CHANGE THIS MAIN FUNCTION
#define MAX_INIT_LIST_LEN 100
int main() {
    // Need to read in a number of ints into an array
    printf("How many numbers in initial list?: ");
    int list_size = 0;
    scanf("%d", &list_size);
    int initial_elems[MAX_INIT_LIST_LEN] = {0};
    int n_read = 0;
    while (n_read < list_size && scanf("%d", &initial_elems[n_read])) {
        n_read++;
    }

    // create linked list from first set of inputs
    struct node *head = NULL;
    if (n_read > 0) {
        // list has elements
        head = array_to_list(n_read, initial_elems);
    }

    printf("Enter number to insert to head: ");
    int value = 0;
    scanf("%d", &value);
    struct node *new_head = insert_head(value, head);
    print_list(new_head);

    return 0;
}

// WRITE YOUR CODE INSIDE HERE ONLY!!!
// Insert a new node containing value at the start of the linked list.
// The head of the new list is returned.
struct node *insert_head(int value, struct node *head) {
    struct node *new_node = malloc(sizeof(struct node));
    if (new_node == NULL) {
        fprintf(stderr, "out of memory\n");
        exit(1);
    }
    new_node->data = value;
    new_node->next = head;
    return new_node;
}


// DO NOT CHANGE THIS FUNCTION
// create linked list from array of strings
struct node *array_to_list(int len, int array[]) {
    struct node *head = NULL;
    int i = len - 1;
    while (i >= 0) {
        struct node *n = malloc(sizeof(struct node));
        assert(n != NULL);
        n->next = head;
        n->data = array[i];
        head = n;
        i -= 1;
    }   
    return head;
}

// DO NOT CHANGE THIS FUNCTION
// print linked list
void print_list(struct node *head) {
    printf("[");    
    struct node *n = head;
    while (n != NULL) {
        // If you're getting an error here,
        // you have returned an invalid list
        printf("%d", n->data);
        if (n->next != NULL) {
            printf(", ");
        }
        n = n->next;
    }
    printf("]\n");
}

Download debug_insert_second_last.c here

Or, copy these file(s) to your CSE account using the following command:

1511 fetch-activity debug_insert_second_last

Debugging Tips!

Some debugging tips for you:

• dcc output - as you run into issues, dcc will point you to where the errors are. Remember that dcc gives you the line number the issue is on, and will give some sort of explanation. Make sure you read everything dcc gives you. Sometimes we get “errors carried forward”, so find your first error, fix that, then recompile.
• print statements - sometimes it can be handy to see if the flow of your code puts you in the spot you expect it to be (ie. inside the right if statement, or going through a loop the correct amount of times). A quick way you can check this is by putting print statements in your code for testing purposes, like "the value of x is %d and y is %d". This lets you check that you got against what you expected.
• COMP1511 debugging guide

The Task

This exercise takes in the length of a linked list, followed by the elements of the list. Then it takes in a single value to be inserted as the second last node of the list previously created.

For example if the existing list is 1 -> 2 -> 3 -> X and a node with value 4 is being inserted, after insertion the list is as follows: 1 -> 2 -> 4 -> 3 -> X. Note, the node containging the value 4 is inserted before the node containing the value 3 since the node containing the value 3 is at the tail (i.e the last node) of the list since it points at null.

Currently it has some issues when attempting to insert the value as the second last node in the list - it is your job to figure them out and fix the code.

Examples

dcc debug_insert_second_last.c -o debug_insert_second_last
./debug_insert_second_last
How many numbers in initial list?: 3
1 2 3
Enter the value to insert: 4
[1, 2, 4, 3]
./debug_insert_second_last
How many numbers in initial list?: 6
5 2 9 10 4 7
Enter the value to insert: 0
[5, 2, 9, 10, 4, 0, 7]
./debug_insert_second_last
How many numbers in initial list?: 1
23
Enter the value to insert: 5
[5, 23]
./debug_insert_second_last
How many numbers in initial list?: 0
Enter the value to insert: 4
[4]

Assumptions/Restrictions/Clarifications

• You do not need to edit the main(), array_to_list(), print_list() or get_list_length() functions.

1511 style debug_insert_second_last.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest debug_insert_second_last

When you are finished working on this exercise, you must submit your work by running give:

give cs1511 lab08_debug_insert_second_last debug_insert_second_last.c

You must run give before Monday 04 November 20:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

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

#define MAX_INIT_LIST_LEN 100

struct node *insert_second_last(int value, struct node *head);
struct node *create_node(int data, struct node *next);
struct node *array_to_list(int len, int array[]);
void print_list(struct node *head);
int get_list_length(struct node *head);

int main(void) {
    // Need to read in a number of ints into an array
    printf("How many numbers in initial list?: ");
    int list_size = 0;
    scanf("%d", &list_size);
    int initial_elems[MAX_INIT_LIST_LEN] = {0};
    int n_read = 0;
    while (n_read < list_size && scanf("%d", &initial_elems[n_read])) {
        n_read++;
    }

    // create linked list from first set of inputs
    struct node *head = NULL;
    if (n_read > 0) {
        // list has elements
        head = array_to_list(n_read, initial_elems);
    }

    printf("Enter the value to insert: ");
    int value;
    scanf("%d", &value);

    struct node *new_head = insert_second_last(value, head);
    print_list(new_head);

    return 0;
}

// DO NOT EDIT
// Gets the length of a linked lists
int get_list_length(struct node *head) {
    int length = 0;
    struct node *current = head;
    while (current != NULL) {
        length++;
        current = current->next;
    }
    return length;
}

// Insert a new node containing value at the second last position of the linked list.
// The head of the new list is returned.
struct node *insert_second_last(int value, struct node *head) {
    struct node *new_node = malloc(sizeof(struct node));
    new_node->data = value;
    new_node->next = NULL;

    int list_length = get_list_length(head);

    // new node is head of list
    if (head == NULL || list_length == 1) {
        new_node->next = head;
        return new_node;
    }

    struct node *p = head;
    int i = 1;
    while (p->next != NULL && i < (list_length - 1) ) {
        p = p->next;
        i++;
    }
    new_node->next = p->next;
    p->next = new_node;
    return head;
}

// DO NOT EDIT
// create linked list from array of strings
struct node *array_to_list(int len, int array[]) {
    struct node *head = NULL;
    int i = len - 1;
    while (i >= 0) {
        struct node *n = malloc(sizeof(struct node));
        n->next = head;
        n->data = array[i];
        head = n;
        i -= 1;
    }   
    return head;
}

// DO NOT EDIT
// print linked list
void print_list(struct node *head) {
    printf("[");    
    struct node *n = head;
    while (n != NULL) {
        // If you're getting an error here,
        // you have returned an invalid list
        printf("%d", n->data);
        if (n->next != NULL) {
            printf(", ");
        }
        n = n->next;
    }
    printf("]\n");
}

Download list_contains.c here

Or, copy these file(s) to your CSE account using the following command:

1511 fetch-activity list_contains

Your task is to add code to this function in list_contains.c:

// Return 1 if value occurs in linked list, 0 otherwise
int contains(char *value, struct node *head) {

    // PUT YOUR CODE HERE (change the next line!)
    return 42;
}

contains is given two arguments, a string value and head which is the pointer to the first node in a linked list.

Add code to contains so that it returns 1 if value occurs in the linked list and otherwise it returns 0.

For example if the linked list contains these 7 elements:

"mozzarella" "pepperoni" "basil" "ham" "tomato bacon" "cheesy-crust" "bocconcini"

and contains is called with value of "mozzarella",

contains should return 1.

Testing

list_contains.c also contains a main function which allows you to test your contains function.

This main function:

1. Asks for how many strings will be in our list,
2. reads in and converts that n many strings to a linked list,
3. assigns a pointer to the first node in the linked list to head,
4. reads another single string from standard input and assigns it to value.
5. calls list_contains(value, head) and
6. prints the result.

Do not change this function. If you want to change it, you have misread the question.

Your list_contains function will be called directly in marking. The main function is only to let you test your list_contains function

Examples

dcc list_contains.c -o list_contains
./list_contains
How many strings in initial list?: 4
pepperoni
ham
basil
capsicum
Enter word to check contained: basil
1
./list_contains
How many strings in initial list?: 4
pepperoni
ham
basil
capsicum
Enter word to check contained: mozzarella
0
./list_contains 
How many strings in initial list?: 4
chicken
mushroom
mushroom
pizza-sauce
Enter word to check contained: mushroom
1
./list_contains
How many strings in initial list?: 4
tomato
bacon
capsicum
mushroom
Enter word to check contained: pepperoni
0
./list_contains
How many strings in initial list?: 0
Enter word to check contained: tomato
0

Assumptions/Restrictions/Clarifications

• String matching is case sensitive. "Tomato" does not match "tomato". No strings will have the space character in them
• contains should return a single integer.
• contains should not change the linked list it is given. Your function should not change the next or data fields of list nodes.
• contains should not use arrays.
• contains should not call malloc.
• contains should not call scanf (or getchar or fgets).
• contains should not print anything. It should not call printf.
• Do not change the supplied main function. It will not be tested or marked.

1511 style list_contains.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest list_contains

When you are finished working on this exercise, you must submit your work by running give:

give cs1511 lab08_list_contains list_contains.c

You must run give before Monday 04 November 20:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define MAX_STRING_SIZE 1024
#define MAX_STRINGS 50

struct node {
    struct node *next;
    char         data[MAX_STRING_SIZE];
};

int contains(char *value, struct node *head);
struct node *strings_to_list(int len, char *strings[]);
void remove_newline(char *string);

// DO NOT CHANGE THIS MAIN FUNCTION


int main(void) {
    // Need to read in a number of ints into an array
    printf("How many strings in initial list?: ");
    int list_size = 0;
    scanf("%d ", &list_size);
    char *initial_elems[MAX_STRINGS] = {NULL};

    int i = 0;
    while (i < list_size) {
        //Allocate string:
        char *string = malloc(sizeof(char) * MAX_STRING_SIZE);
        // scan string
        fgets(string, MAX_STRING_SIZE, stdin);
        remove_newline(string);

        initial_elems[i] = string;
        i++;
    }

    printf("Enter word to check contained: ");

    // Read in word to check that contained inside
    char value[MAX_STRING_SIZE] = {'\0'};
    fgets(value, MAX_STRING_SIZE, stdin);
    remove_newline(value);

    // create linked list from inputs
    struct node *head = NULL;
    if (list_size > 0) {
        // list has elements
        head = strings_to_list(list_size, initial_elems);
    }

    int result = contains(value, head);
    printf("%d\n", result);

    return 0;
}




// Return 1 if value occurs in linked list, 0 otherwise
int contains(char *value, struct node *head) {
    struct node *curr = head;
    while (curr != NULL && strcmp(curr->data, value) != 0) {
        curr = curr->next;
    }

    if (curr == NULL) {
        return 0;
    }
    return 1;
}


// DO NOT CHANGE THIS FUNCTION
// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
    struct node *head = NULL;
    int i = len - 1;
    while (i >= 0) {
        struct node *n = malloc(sizeof(struct node));
        assert(n != NULL);
        n->next = head;
        strcpy(n->data, strings[i]);
        head = n;
        i -= 1;
    }   
    return head;
}

// Strips newline off the end of a string.
void remove_newline(char *string) {
    int len = strlen(string);

    if (len > 0 && string[len - 1] == '\n') {
        string[len - 1] = '\0';
    }
}

Download list_insert_tail.c here

Or, copy these file(s) to your CSE account using the following command:

1511 fetch-activity list_insert_tail

Your task is to add code to this function in list_insert_tail.c:

// Insert a new node containing value at the end of the linked list.
// Parameters:
//      `int value`         : The value to insert.
//      `struct list *list` : a struct * containing the head pointer of the 
//      linked list.
void insert_tail(int value, struct list *list) {
    // PUT YOUR CODE HERE
}

insert_tail is given two arguments:

• value is an int
• list is the pointer to a struct list which contains
• the head (a pointer to the first node) of the linked list

Add code to insert_tail so that it creates a new list node (using malloc) containing value and places it at the end of the list.

insert_tail should return nothing.

For example if value is 12 and the linked list contains these 3 elements:

16, 7, 8

insert_tail should modify the linked list so that it now has these elements:

16, 7, 8, 12

Testing

list_insert_tail.c also contains a main function which allows you to test your insert_tail function.

This main function:

1. Asks for the size of the initial linked list
2. converts the first set of scanned inputs to a linked list
3. stores the first node of the linked list in a struct list.
4. reads a single integer from standard input and assigns it to value
5. calls insert_tail(value, list)
6. prints the result.

Do not change this main function. If you want to change it, you have misread the question.

Your insert_tail function will be called directly in marking. The main function is only to let you test your insert_tail function

Examples

dcc list_insert_tail.c -o list_insert_tail
./list_insert_tail
How many numbers in initial list?: 3
16 7 8
Enter value to insert: 12
[16, 7, 8, 12]
./list_insert_tail
How many numbers in initial list?: 1
16
Enter value to insert: 42
[16, 42]
./list_insert_tail
How many numbers in initial list?: 0
Enter value to insert: 2
[2]

Assumptions/Restrictions/Clarifications

• insert_tail should not use arrays
• insert_tail should not call scanf (or getchar or fgets)
• insert_tail should not print anything. It should not call printf
• Do not change the supplied main function. It will not be tested or marked

1511 style list_insert_tail.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest list_insert_tail

When you are finished working on this exercise, you must submit your work by running give:

give cs1511 lab08_list_insert_tail list_insert_tail.c

You must run give before Monday 04 November 20:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// DO NOT CHANGE THESE STRUCTS
struct list {
    struct node *head;
};

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

void insert_tail(int value, struct list *list);
struct list *array_to_list(int len, int array[]);
void print_list(struct list *list);

struct node *last(struct node *head);
struct node *create_node(int data, struct node *next);

// DO NOT CHANGE THIS MAIN FUNCTION
#define MAX_INIT_LIST_LEN 100
int main() {
    // Need to read in a number of ints into an array
    printf("How many numbers in initial list?: ");
    int list_size = 0;
    scanf("%d", &list_size);
    int initial_elems[MAX_INIT_LIST_LEN] = {0};
    int n_read = 0;
    while (n_read < list_size && scanf("%d", &initial_elems[n_read])) {
        n_read++;
    }

    // create linked list from first set of inputs
    struct list *list = NULL;
        // list has elements
    list = array_to_list(n_read, initial_elems);


    printf("Enter value to insert: ");
    int value;
    scanf("%d", &value);
    insert_tail(value, list);
    print_list(list);

    return 0;
}


void insert_tail(int value, struct list *list) {
    struct node *new_node = malloc(sizeof(struct node));
    if (new_node == NULL) {
        fprintf(stderr, "out of memory\n");
        exit(1);
    }
    new_node->data = value;
    new_node->next = NULL;

    // empty list is a special case
    // new node is now the head of the now 1 element list
    if (list->head == NULL) {
        list->head = new_node;
    } else {
        struct node *l = last(list->head);
        l->next = new_node;

    }
}

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


// DO NOT CHANGE THIS FUNCTION
// create linked list from array of strings
struct list *array_to_list(int len, int array[]) {
    struct node *head = NULL;
    int i = len - 1;
    while (i >= 0) {
        struct node *n = malloc(sizeof(struct node));
        assert(n != NULL);
        n->next = head;
        n->data = array[i];
        head = n;
        i -= 1;
    }

    struct list *list = malloc(sizeof(struct list));
    list->head = head;
    return list;
}

// DO NOT CHANGE THIS FUNCTION
// print linked list
void print_list(struct list *list) {
    printf("[");    
    struct node *n = list->head;
    while (n != NULL) {
        // If you're getting an error here,
        // you have returned an invalid list
        printf("%d", n->data);
        if (n->next != NULL) {
            printf(", ");
        }
        n = n->next;
    }
    printf("]\n");
}

Download list_get_nth_v2.c here

Or, copy these file(s) to your CSE account using the following command:

1511 fetch-activity list_get_nth_v2

Your task is to complete the program list_get_nth_v2.c. This will be achieved by completing the get_nth function. The program will ask the user to input the length of a linked list and the number of elements it contains. It will then ask for an nth element. The elements are counted in the same manner as array elements (zero-based), so the first element in the list is regarded as n = 0, the second element as n = 1 and so on. In the case where there is no nth element in the list, an error message should be printed out.

Examples

dcc list_get_nth_v2.c -o list_get_nth_v2
./list_get_nth_v2
How many elements in the list: 5
5 2 6 1 6

Which nth element would you like to find: 0
The nth value is 5!
./list_get_nth_v2
How many elements in the list: 6
1 2 3 4 5 6

Which nth element would you like to find: 7
ERROR: no nth element in list.

Assumptions/Restrictions/Clarifications

• The list will always have at least one element.
• The nth value will always be a whole number >= 0.
• Correct number of elements will always be given.

1511 style list_get_nth_v2.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest list_get_nth_v2

When you are finished working on this exercise, you must submit your work by running give:

give cs1511 lab08_list_get_nth_v2 list_get_nth_v2.c

You must run give before Monday 04 November 20:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

// List get nth
// list_get_nth.c
//
// This program was written by Morgan Swaak (z5476300)
// on 31-03-2024
//
// Prints the nth element in a linked list

#include <stdio.h>
#include <stdlib.h>

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

void create_list(struct node *head);
void get_nth(struct node *head, int n);
void delete_list(struct node *head);

// calls the functions for code to operate
int main(void) {
    struct node *head = malloc(sizeof(struct node));
    create_list(head);

    int n;
    printf("Which nth element would you like to find: ");
    scanf("%d", &n);
    get_nth(head, n);

    delete_list(head);
    return 0;
}

// finds the nth element of a linked list
void get_nth(struct node *head, int n) {
    struct node *current = head;
    while (current != NULL && n >= 0) {
        if (n == 0) {
            printf("The nth value is %d!\n", current->data);
        }
        n--;
        current = current->next;
    }

    if (current == NULL && n >= 0) {
        printf("ERROR: no nth element in list.\n");
    }
}


// creates a linked list
void create_list(struct node *head) {
    int num_elements;
    printf("How many elements in the list: ");
    scanf("%d", &num_elements);
    struct node *current = head;

    //always at least one element in list
    int data;
    scanf("%d", &data);
    current->data = data;

    int i = 1;
    while (i < num_elements) {
        current->next = malloc(sizeof(struct node));
        current = current->next;
        scanf("%d", &data);
        current->data = data;
        i++;
    }
    current->next = NULL;
    printf("\n");
}

// frees all the memory associated with the linked list
void delete_list(struct node *head) {
    struct node *current = head;
    while (current != NULL) {
        struct node *delete = current;
        current = current->next;
        free(delete);
    }
}

Download list_insert_nth.c here

Or, copy these file(s) to your CSE account using the following command:

1511 fetch-activity list_insert_nth

Your task is to add code to this function in list_insert_nth.c:

// Insert a new node containing value at position n of the linked list.
// if n == 0, node is inserted at start of list
// if n >= length of list, node is appended at end of list
// The head of the new list is returned.
struct node *insert_nth(int n, int value, struct node *head) {
    // PUT YOUR CODE HERE! CHANGE THE NEXT LINES!
    return NULL;
}

insert_nth is given three arguments, n value and head

• n is an int.
• value is an int.
• head is the pointer to the first node in a linked list.

Add code to insert_nth so that it creates a new list node (using malloc) containing value and places it before position n of the list.

The elements are counted in the same manner as array elements (zero-based), so the first element in the list is regarded as at position 0, the second element position 1 and so on.

If there are less than n elements in the list, the new list node should be appended to the end of the list.

insert_nth should return a pointer to the new list.

For example if n is 1 and value is 12 and the linked list contains these 3 elements:

16, 7, 8

insert_nth should return a pointer to a list with these elements:

16, 12, 7, 8

Testing

list_insert_nth.c also contains a main function which allows you to test your insert_nth function.

This main function:

1. Asks for the size of the linked list,
2. asks for standard input to convert to a linked list,
3. assigns a pointer to the first node in the linked list to head,
4. reads an integer from standard input and assigns it to n,
5. reads a second integer from standard input and assigns it to value
6. calls insert_nth(n, value, head) and
7. prints the result.

Do not change this function. If you want to change it, you have misread the question.

Your insert_nth function will be called directly in marking. The main function is only to let you test your insert_nth function

dcc list_insert_nth.c -o list_insert_nth
./list_insert_nth
How many numbers in initial list?: 3
16 7 8
Enter position and value to insert: 0 12
[12, 16, 7, 8]
./list_insert_nth
How many numbers in initial list?: 3
16 7 8
Enter position and value to insert: 1 12
[16, 12, 7, 8]
./list_insert_nth
How many numbers in initial list?: 3
16 7 8
Enter position and value to insert: 2 12
[16, 7, 12, 8]
./list_insert_nth
How many numbers in initial list?: 3
16 7 8
Enter position and value to insert: 3 12
[16, 7, 8, 12]
./list_insert_nth
How many numbers in initial list?: 3
16 7 8
Enter position and value to insert: 42 12
[16, 7, 8, 12]
./list_insert_nth
How many numbers in initial list?: 1
42
Enter position and value to insert: 0 16
[16, 42]
./list_insert_nth
How many numbers in initial list?: 0
Enter position and value to insert: 0 2
[2]
./list_insert_nth
How many numbers in initial list?: 0
Enter position and value to insert: 10 2
[2]

Assumptions/Restrictions/Clarifications

• insert_nth should not use arrays.
• insert_nth should not call scanf (or getchar or fgets).
• insert_nth should not print anything. It should not call printf.
• The n provided will always be non-negative
• Do not change the supplied main function. It will not be tested or marked.

1511 style list_insert_nth.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest list_insert_nth

When you are finished working on this exercise, you and your lab partner must both submit your work by running give:

give cs1511 lab08_list_insert_nth list_insert_nth.c

Note, even though this is a pair exercise, you both must run give from your own account before Monday 04 November 20:00 to obtain the marks for this lab exercise.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

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

struct node *insert_nth(int n, int value, struct node *head);
struct node *array_to_list(int len, int array[]);
void print_list(struct node *head);

// DO NOT CHANGE THIS MAIN FUNCTION
#define MAX_INIT_LIST_LEN 100
int main() {
    // Need to read in a number of ints into an array
    printf("How many numbers in initial list?: ");
    int list_size = 0;
    scanf("%d", &list_size);
    int initial_elems[MAX_INIT_LIST_LEN] = {0};
    int n_read = 0;
    while (n_read < list_size && scanf("%d", &initial_elems[n_read])) {
        n_read++;
    }

    // create linked list from first set of inputs
    struct node *head = NULL;
    if (n_read > 0) {
        // list has elements
        head = array_to_list(n_read, initial_elems);
    }

    printf("Enter position and value to insert: ");
    int n;
    scanf("%d", &n);
    int value;
    scanf("%d", &value);

    struct node *new_head = insert_nth(n, value, head);
    print_list(new_head);

    return 0;
}


// Insert a new node containing value at position n of the linked list.
// if n == 0, node is inserted at start of list
// if n >= length of list, node is appended at end of list
// The head of the new list is returned.
struct node *insert_nth(int n, int value, struct node *head) {
    struct node *new_node = malloc(sizeof(struct node));
    if (new_node == NULL) {
        fprintf(stderr, "out of memory\n");
        exit(1);
    }
    new_node->data = value;

    // new node is head of list
    if (head == NULL || n == 0) {
        new_node->next = head;
        return new_node;
    }

    int i = n - 1;
    struct node *p = head;
    while (p->next != NULL && i > 0) {
        p = p->next;
        i = i - 1;
    }
    new_node->next = p->next;
    p->next = new_node;
    return head;
}



// DO NOT CHANGE THIS FUNCTION
// create linked list from array of strings
struct node *array_to_list(int len, int array[]) {
    struct node *head = NULL;
    int i = len - 1;
    while (i >= 0) {
        struct node *n = malloc(sizeof(struct node));
        assert(n != NULL);
        n->next = head;
        n->data = array[i];
        head = n;
        i -= 1;
    }   
    return head;
}

// print linked list
void print_list(struct node *head) {
    printf("[");    
    struct node *n = head;
    while (n != NULL) {
        // If you're getting an error here,
        // you have returned an invalid list
        printf("%d", n->data);
        if (n->next != NULL) {
            printf(", ");
        }
        n = n->next;
    }
    printf("]\n");
}

Download lock_picking.c here

Or, copy these file(s) to your CSE account using the following command:

1511 fetch-activity lock_picking

You have been provided with some starter code in lock_picking.c. In this activity you will complete the function pick_lock.

A mathematician has devised a way to break AES-256 encryption. In order to protect this secret they've hidden it in a drawer protected by a lock they believe is so hard to break that only they can solve it. The lock consists of two dials with numbers. To unlock the draw the dials must be rotated so that both dials have the same number at the top. This number at the top will be the solution. However, this must be done in the least number of moves possible otherwise the drawer does not unlock.

If there are multiple ways for the dials to reach the minimum number of moves:

1. Dial 1 should have the least moves possible.
2. The dial should prioritise rotating right over rotating left.

For example if there are 3 possible solutions including:

• Dial 1 (5 moves) Dial 2 (1 move)
• Dial 1 (4 moves) Dial 2 (2 moves)
• Dial 1 (1 move) Dial 2 (8 moves) The one that should be chosen as the solution is Dial 1 (4 moves) Dial 2 (2 moves). This is as 4 < 5 and even though the third option only has 1 move, the total moves (1 + 8) is greater than option 2 (4 + 2).

When entering the input for the dial, it starts at the top number and moves around the disk clockwise (moving to the right). For example if the input for the first dial was 5 3 6 2 1 7 6 12 and the second dial was 7 6 2 here is an example of how these disks would look like and how to solve them:

Examples

dcc lock_picking.c -o lock_picking
./lock_picking
How many numbers in the dial: 8
5 3 6 2 1 7 6 12
How many numbers in the dial: 3
7 6 2

Solution = 6
Dial 1: turn 2 step(s) to the right.
Dial 2: turn 1 step(s) to the left.
dcc lock_picking.c -o lock_picking
./lock_picking
How many numbers in the dial: 5
1 2 3 4 5
How many numbers in the dial: 6
5 4 3 2 1 6

Solution = 5
Dial 1: turn 1 step(s) to the right.
Dial 2: don't turn.
dcc lock_picking.c -o lock_picking
./lock_picking
How many numbers in the dial: 1
3
How many numbers in the dial: 1
5

Error: Lock is impossible to solve!

Assumptions/Restrictions/Clarifications

• Dials can have the same number multiple times.
• Both dials will always contain at least one number.
• The dial can be of any length.

1511 style lock_picking.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest lock_picking

When you are finished working on this exercise, you must submit your work by running give:

give cs1511 lab08_lock_picking lock_picking.c

You must run give before Monday 04 November 20:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

// dial Picking
// dial_picking.c
//
// This program was written by Morgan Swaak (z5476300)
// on 21/03/24
//
// A program used to find the quickest way to break the mathematician's lock!

#include <stdio.h>
#include <stdlib.h>

#define FALSE 0
#define TRUE 1

enum direction {
    NONE,
    RIGHT,
    LEFT
};

struct dial {
    struct number *start;
};

struct number {
    int value;
    struct number *right;
    struct number *left;
};

struct result {
    // found is used to say if a result has been found
    int found;
    // distance is how many rotations needed
    int distance;
    // stores the value found (number on disk)
    int value;
    // stores the direction of the rotations
    enum direction direction;
};

void initalise_dial(struct dial *dial);
void free_dial(struct dial *dial);
void pick_lock(struct dial *dial_1, struct dial *dial_2);
int dial_length(struct dial *dial);
struct result find(struct dial *dial, int value);
void print_dial(struct result result, int dial_num);
void get_result(
    enum direction direction, 
    int length, 
    struct result *best_dial_1, 
    struct result *best_dial_2,
    struct dial *dial_1,
    struct dial *dial_2
);

// main function that runs code
int main(void) {
    struct dial *dial_1 = malloc(sizeof(struct dial));
    struct dial *dial_2 = malloc(sizeof(struct dial));
    initalise_dial(dial_1);
    initalise_dial(dial_2);

    pick_lock(dial_1, dial_2);

    free_dial(dial_1);
    free_dial(dial_2);
    return 0;
}

// function that prints out the correct solution to the lock
void pick_lock(struct dial *dial_1, struct dial *dial_2) {
    int length_1 = dial_length(dial_1);
    int current_direction = NONE;
    // stores the path taken by dial 1 for best path
    struct result best_dial_1;
    best_dial_1.found = FALSE;
    // stores the path taken by dial 2 for the best path
    struct result best_dial_2;
    best_dial_2.found = FALSE;

    // first check case no direction
    struct result dial_2_result = find(dial_2, dial_1->start->value);

    best_dial_2 = dial_2_result;

    if (dial_2_result.found == TRUE) {
        best_dial_2 = dial_2_result;
        best_dial_1.found = TRUE;
        best_dial_1.distance = 0;
        best_dial_1.direction = NONE;
        best_dial_1.value = dial_1->start->value;
    }

    // now check left case
    get_result(LEFT, length_1, &best_dial_1, &best_dial_2, dial_1, dial_2);

    // now check right case
    get_result(RIGHT, length_1, &best_dial_1, &best_dial_2, dial_1, dial_2);

    //now print best result
    printf("\n");
    if (best_dial_1.found == FALSE) {
        printf("Error: Lock is impossible to solve!\n");
    } else {
        printf("Solution = %d\n", best_dial_1.value);
        print_dial(best_dial_1, 1);
        print_dial(best_dial_2, 2);
    }
}

//searches through both dials to try find the best solution
void get_result(
    enum direction direction, 
    int length, 
    struct result *best_dial_1, 
    struct result *best_dial_2,
    struct dial *dial_1,
    struct dial *dial_2
) {
    struct number *current = dial_1->start;
    struct result dial_1_result;
    dial_1_result.direction = RIGHT;
    int i = 0;
    while (i < length / 2) {
        i ++;
        if (direction == RIGHT) {
            // as rotating right means moving left in the list
            current = current->left;
        } else if (direction == LEFT) {
            // as rotating left means moving right in the list
            current = current->right;
        }
        dial_1_result.distance = i;
        dial_1_result.value = current->value;
        // checks dial 2 for current value, if found the result will be set to 
        // true and distance to how many rotations needed
        struct result dial_2_result = find(dial_2, current->value);
        if ((dial_2_result.found == TRUE && 
            ((dial_2_result.distance + dial_1_result.distance) 
            < (best_dial_1->distance + best_dial_2->distance)))
            || (best_dial_1->found == FALSE && dial_2_result.found == TRUE)
        ) {
            dial_1_result.found = TRUE;
            *best_dial_1 = dial_1_result;
            *best_dial_2 = dial_2_result;
        }
    }
}

//function that prints the solution to the lock
void print_dial(struct result result, int dial_num) {
    if (result.direction == NONE) {
        printf("Dial %d: don't turn.\n", dial_num);
    } else if (result.direction == RIGHT) {
        printf("Dial %d: turn %d step(s) to the right.\n", dial_num, result.distance);
    } else if (result.direction == LEFT) {
        printf("Dial %d: turn %d step(s) to the left.\n", dial_num, result.distance);
    }
}

//returns the shortest distance to the value in a dial
struct result find(struct dial *dial, int value) {
    struct result best_result;
    best_result.found = FALSE;
    best_result.value = value;
    int length = dial_length(dial);
    struct number *start = dial->start;

    //case at start
    if (start->value == value) {
        best_result.found = TRUE;
        best_result.direction = NONE;
        best_result.distance = 0;
        return best_result;
    }

    //right case
    struct number *current = start;
    int i = 0;
    while (i < length / 2 && best_result.found == FALSE) {
        current = current->left;
        i ++;
        if (current->value == value) {
            best_result.direction = RIGHT;
            best_result.found = TRUE;
            best_result.distance = i;
        } 
    }

    //left case
    int distance = i;
    current = start;
    i = 0;
    while (i < distance) {
        current = current->right;
        i ++;
        if (current->value == value && 
            (best_result.found == FALSE || i < best_result.distance)
        ) {
            best_result.direction = LEFT;
            best_result.found = TRUE;
            best_result.distance = i;
            break;
        }
    }
    return best_result;
}

//returns how many numbers a dial contains
int dial_length(struct dial *dial) {
    int length = 1;
    struct number *start = dial->start;
    struct number *current = start;
    current = current->right;
    while (current != start) {
        length++;
        current = current->right;
    }
    return length;
}

//initialises a dial
void initalise_dial(struct dial *dial) {
    int num_numbers;
    printf("How many numbers in the dial: ");
    scanf("%d", &num_numbers);
    struct number *current = malloc(sizeof(struct number));
    int value;
    scanf("%d", &value);
    current->value = value;
    int i = 1;
    //add to start of dial
    dial->start = current;
    while (i < num_numbers) {
        //assign value to new node
        struct number *previous = current;
        current = malloc(sizeof(struct number));
        scanf("%d", &value);
        current->value = value;
        //attach to previous
        previous->right = current;
        current->left = previous;
        i++;
    }
    current->right = dial->start;
    dial->start->left = current;
}

//frees all the data associated with a dial (and the dial itself)
void free_dial(struct dial *dial) {
    struct number *start = dial->start;
    struct number *current = start;
    struct number *to_delete = current;
    current = current->right;
    free(to_delete);
    while (current != start) {
        to_delete = current;
        current = current->right;
        free(to_delete);
    }
    free(dial);
}

Download list_reverse.c here

Or, copy these file(s) to your CSE account using the following command:

1511 fetch-activity list_reverse

Your task is to add code to this function in list_reverse.c:

//
// Place the list pointed to by head into reverse order.
// The head of the list is returned.
//
struct node *reverse(struct node *head) {

    // PUT YOUR CODE HERE (change the next line!)
    return NULL;

}

Note list_reverse.c uses the following familiar data type:

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

list_reverse is given one argument, head which is the pointer to the first node in the linked list.

Add code to reverse which rearranges the list to be in reverse order.

reverse should return a pointer to the new list.

reverse must rearrange the list by changing the next fields of nodes.

reverse must not change the data fields of nodes.

For example if the linked list contains these 8 elements:

16, 7, 8, 12, 13, 19, 21, 12

reverse should return a pointer to a list with these elements:

12, 21, 19, 13, 12, 8, 7, 16

Testing

list_reverse.c also contains a main function which allows you to test your list_reverse function.

This main function:

• takes in the size of the linked list,
• converts the input numbers to a linked list,
• assigns a pointer to the first node in the linked list to head,
• calls reverse(head) and
• prints the result.

Do not change this function. If you want to change it, you have misread the question.

Your list_reverse function will be called directly in marking. The main function is only to let you test your list_reverse function

Examples

dcc list_reverse.c -o list_reverse
./list_reverse
How many numbers in list?: 8
16 7 8 12 13 19 21 12
[12, 21, 19, 13, 12, 8, 7, 16]
./list_reverse
How many numbers in list?: 6
2 4 6 2 4 6
[6, 4, 2, 6, 4, 2]
./list_reverse 42
How many numbers in list?: 1
42
[42]
./list_reverse
How many numbers in list?: 0
[]

Assumptions/Restrictions/Clarifications

• list_reverse should not change the data fields of list nodes
• list_reverse should not use arrays
• list_reverse should not call malloc
• list_reverse should not call scanf (or getchar or fgets)
• list_reverse should not print anything. It should not call printf
• Do not change the supplied main function. It will not be tested or marked

1511 style list_reverse.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest list_reverse

When you are finished working on this exercise, you must submit your work by running give:

give cs1511 lab08_list_reverse list_reverse.c

You must run give before Week 9 Monday 20:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

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

struct node *reverse(struct node *head);
struct node *array_to_list(int len, int array[]);
void print_list(struct node *head);

// DO NOT CHANGE THIS MAIN FUNCTION
#define MAX_INIT_LIST_LEN 100
int main() {
    // Need to read in a number of ints into an array
    printf("How many numbers in list?: ");
    int list_size = 0;
    scanf("%d", &list_size);
    int initial_elems[MAX_INIT_LIST_LEN] = {0};
    int n_read = 0;
    while (n_read < list_size && scanf("%d", &initial_elems[n_read])) {
        n_read++;
    }

    // create linked list from first set of inputs
    struct node *head = NULL;
    if (n_read > 0) {
        // list has elements
        head = array_to_list(n_read, initial_elems);
    }
    
    struct node *new_head = reverse(head);
    print_list(new_head);

    return 0;
}

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

// DO NOT CHANGE THIS FUNCTION
// create linked list from array of strings
struct node *array_to_list(int len, int array[]) {
    struct node *head = NULL;
    int i = len - 1;
    while (i >= 0) {
        struct node *n = malloc(sizeof(struct node));
        assert(n != NULL);
        n->next = head;
        n->data = array[i];
        head = n;
        i -= 1;
    }   
    return head;
}

// print linked list
void print_list(struct node *head) {
    printf("[");

    for (struct node *n = head; n != NULL; n = n->next) {
        // If you're getting an error here,
        // you have returned an invalid list
        printf("%d", n->data);
        if (n->next != NULL) {
            printf(", ");
        }
    }
    printf("]\n");
}