Programming Fundamentals

• More complex linked lists
• Practice working with lists of lists

In this week's lab, your tutors will go around the class and give you one on one feedback on some code you have written in a previous week.

Take this as an opportunity to ask any questions you might have about the course content so far!

So, if you would like, have a think about if there is any particular exercise you would like to receive feedback for, or any particular content you would like to ask about.

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.

If you are an online tut-lab student and are interested in trying the final exam environment on a lab machine, please sign up to an existing in-person lab for week 10 via the following event! (If you are an in-person tut-lab student, do not worry about this, as you will experience the exam environment in-person in your Week 10 lab!)

You can sign up via this link: In-Person Practice Exam Sign Up (the access code is "COMP1511").

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

Worth 1 mark(s) in total:

• list_create
• list_increasing
• list_delete_first

Worth 1 mark(s) in total:

• debug_remove_second_last
• list_get_middle
• list_delete_contains_string
• list_delete_highest

Worth 0.5 mark(s) in total:

• lists_diagonal
• musical_chairs

For your interest, but not for marks:

• student_becomes_teacher_week9

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 list_create.c here

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

1511 fetch-activity list_create

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

// Create linked list from argument values
struct node *arguments_to_list(int argc, char *argv[]) {
    // TODO: Complete this function and change the line below
    return NULL;
}

// Free the linked list from memory
void free_list(struct node *head) {
    // TODO: Complete this function
}

Complete the program list_create.c. The program converts command line arguments into a linked list, prints out the linked list, and then frees the linked list. It is your job to complete the function that creates the linked list (arguments_to_list) and the function that frees the linked list (free_list).

Examples

dcc list_create.c -o list_create
./list_create 5 3 2 9 4 1
5 -> 3 -> 2 -> 9 -> 4 -> 1 -> X
./list_create I love this COMP1511 exercise
I -> love -> this -> COMP1511 -> exercise -> X
./list_create 8915 10563 10821 9979 14640 8433 6894 125
8915 -> 10563 -> 10821 -> 9979 -> 14640 -> 8433 -> 6894 -> 125 -> X
./list_create
X

Assumptions/Restrictions/Clarifications

• Any length of command line arguments can be given
• Do not change the supplied main function. Only your arguments_to_list and free_list function will be tested

1511 style list_create.c

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

1511 autotest list_create

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

give cs1511 lab09_list_create list_create.c

You must run give before Monday 11 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.

// Create a list from Command Line Arguments
// list_create.c
//
// This program was written by Morgan Swaak (z5476300)
// on 5/04/24
//
// A program which creates and prints a linked list 
// from command line arguments!

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

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

struct node *arguments_to_list(int argc, char *argv[]);
void free_list(struct node *head);
void print_list(struct node *head);

int main(int argc, char **argv) {
    struct node *head = arguments_to_list(argc, argv);
    print_list(head);
    free_list(head);

    return 0;
}

// Create linked list from argument values
struct node *arguments_to_list(int argc, char *argv[]) {
    if (argc == 1) {
        return NULL;
    }
    struct node *head = malloc(sizeof(struct node));

    struct node *current = head;
    current->data = argv[1];
    current->next = NULL;
    int i = 2;
    while (i < argc) {
        struct node *new = malloc(sizeof(struct node));
        current->next = new;
        new->data = argv[i];
        new->next = NULL;
        current = new;
        i++;
    }
    return head;
}

// Free the linked list from memory
void free_list(struct node *head) {
    struct node *current = head;
    while (current != NULL) {
        struct node *delete = current;
        current = current->next;
        free(delete); 
    }
}

// Print the values of the linked list
void print_list(struct node *head) {
    struct node *current = head;
    while (current != NULL) {
        printf("%s -> ", current->data);
        current = current->next;
    }
    printf("X\n");
}

Download list_increasing.c here

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

1511 fetch-activity list_increasing

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

int increasing(struct node *head) {

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

}

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

Add code to increasing so that its returns 1 if the list is in increasing order - the value of each list element is larger than the element before.

For example if the linked list contains these 8 elements:

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

increasing should return 1 because it is increasing order

Testing

list_increasing.c also contains a main function which allows you to test your increasing 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. calls list_increasing(head) and
4. prints the result.

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

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

Examples

dcc list_increasing.c -o list_increasing
./list_increasing
How many numbers in initial list?: 9
1 2 4 8 16 32 64 128 256
1
./list_increasing
How many numbers in initial list?: 6
2 4 6 5 8 9
0
./list_increasing
How many numbers in initial list?: 6
13 15 17 17 18 19
0
./list_increasing
How many numbers in initial list?: 2
2 4
1
./list_increasing
How many numbers in initial list?: 1
42
1
./list_increasing
How many numbers in initial list?: 0
1

Assumptions/Restrictions/Clarifications

• increasing should return a single integer
• increasing should not change the linked list it is given. Your function should not change the next or data fields of list nodes
• increasing should not use arrays
• increasing should not call malloc
• increasing should not call scanf (or getchar or fgets)
• You can assume the linked list only contains positive integers
• increasing 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_increasing.c

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

1511 autotest list_increasing

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

give cs1511 lab09_list_increasing list_increasing.c

Note, even though this is a pair exercise, you both must run give from your own account before Monday 11 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;
};

int increasing(struct node *head);
struct node *array_to_list(int len, int array[]);

#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);
    }

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

    return 0;
}

// return 1 if values in a linked list are in increasing order,
// return 0, otherwise

int increasing(struct node *head) {
    // If the list is empty, it's considered increasing, so return 1.
    if (head == NULL) {
        return 1;
    }

    // Assume that it is increasing, and look for evidence
    // that proves otherwise.
    int is_increasing = 1;

    struct node *curr = head;
    while (curr->next != NULL) {
        // If this one is not less than the next one,
        // the list definitely isn't increasing
        // (since these two nodes are out of order).
        if (curr->data >= curr->next->data)  {
            is_increasing = 0;
        }
        curr = curr->next;
    }

    // At this point, if is_increasing is still 1, we didn't find
    // any nodes that were out of order.
    //
    // However, if we did find any nodes that were out of order,
    // we set it to 0 in the loop above.
    //
    // So, is_increasing contains the answer to return.
    return is_increasing;
}

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

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

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

int increasing(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 = increasing(head);
    printf("%d\n", result);

    return 0;
}

// return 1 if values in a linked list are in increasing order,
// return 0, otherwise

int increasing(struct node *head) {
    if (head == NULL) {
        return 1;
    }

    struct node *p = head;
    while (p->next != NULL) {
        if (p->data >= p->next->data)  {
            return 0;
        }
        p = p->next;
    }

    return 1;
}


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

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

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

// return 1 if values in a linked list in increasing order
// recursive solution

int increasing(struct node *head) {
    if (head == NULL || head->next == NULL) {
        return 1;
    } else if (head->data >= head->next->data)  {
        return 0;
    } else {
        return increasing(head->next);
    }
}

Download list_delete_first.c here

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

1511 fetch-activity list_delete_first

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

//
// 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) {

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

Note list_delete_first.c uses the following familiar data type:

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

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

Add code to delete_first so that it deletes the first node from list

delete_first should return a pointer to the new first node in the list

If the list is now empty, delete_first should return NULL

delete_first should call free to free the memory of the node it deletes

For example if the linked list contains these 8 elements:

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

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

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

Hint: This task should only require a few lines of code

Testing

list_delete_first.c also contains a main function which allows you to test your delete_first function. It converts the inputs to a linked list, calls delete_first and then prints the result.

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

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

Examples

dcc list_delete_first.c -o list_delete_first
./list_delete_first
Total numbers: 8
16 7 8 12 13 19 21 12
[7, 8, 12, 13, 19, 21, 12]
./list_delete_first
Total numbers: 6
2 4 6 2 4 6
[4, 6, 2, 4, 6]
./list_delete_first
Total numbers: 1
42
[]
./list_delete_first
Total numbers: 0
[]

Assumptions/Restrictions/Clarifications

• delete_first should call free to free the memory for the node it deletes
• delete_first should not change the data fields of list nodes
• delete_first should not use arrays
• delete_first should not call malloc
• delete_first should not call scanf (or getchar or fgets)
• delete_first 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_delete_first.c

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

1511 autotest list_delete_first

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

give cs1511 lab09_list_delete_first list_delete_first.c

You must run give before Monday 11 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_LIST_LEN 100

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

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

int main(void) {
    // get list size
    int list_size;
    printf("Total numbers: ");
    scanf(" %d", &list_size);

    // read in numbers
    int list[MAX_LIST_LEN] = {0};
    int index_count = 0;
    while (index_count < list_size && scanf(" %d", &list[index_count])) {
        index_count++;
    }

    // create linked list from input numbers
    struct node *head = NULL;
    if (index_count > 0) {
        // list has elements
        head = array_to_list(list_size, list);
    }

    struct node *new_head = delete_first(head);
    print_list(new_head);

    return 0;
}

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

// create linked list from array of ints
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--;
    }

    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");
}

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

Download debug_remove_second_last.c here

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

1511 fetch-activity debug_remove_second_last

Debugging Tips!

Some debugging tips for you:

• dcc output - as you run into issues, dcc will point out 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 program takes in a linked list via command line arguments. Then, it attempts to remove the second last element of the list previously created via the delete_second_last function.

For example if the existing list is 1 -> 2 -> 3 -> 4 -> X, after calling the delete_second_last function on the list it becomes1 -> 2 -> 4 -> X. Note, the node containing the value 3 is removed from the list since it is the second last element in the list.

Currently the program has some issues it is your job to figure them out and fix the code.

Note: You should only need to modify the delete_second_last function to fix the program.

Examples

dcc debug_remove_second_last.c -o debug_remove_second_last
./debug_remove_second_last 1 2 3 4 5 6
Original list: [1, 2, 3, 4, 5, 6]
Modified list: [1, 2, 3, 4, 6]
./debug_remove_second_last 1 2 3
Original list: [1, 2, 3]
Modified list: [1, 3]
./debug_remove_second_last 1 2
Original list: [1, 2]
Modified list: [2]
./debug_remove_second_last 1
Original list: [1]
Modified list: []
./debug_remove_second_last 
Original list: []
Modified list: []

Assumptions/Restrictions/Clarifications

• You may assume all command line arguments will be integers

1511 style debug_remove_second_last.c

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

1511 autotest debug_remove_second_last

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

give cs1511 lab09_debug_remove_second_last debug_remove_second_last.c

You must run give before Monday 11 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.

// debug_remove_second_last.c
// This program removes the second last node of a linked list
// Written by Sofia De Bellis (z5418801), on July 2023

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

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


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

// DO NOT CHANGE THIS MAIN FUNCTION
int main(int argc, char *argv[]) {
    // create linked list from command line arguments excluding the program name
    struct node *head = NULL;
    if (argc > 0) {
        // list has elements
        head = array_to_list(argc - 1, &argv[1]);
    }
    printf("Original list: ");
    print_list(head);
    head = delete_second_last(head);
    printf("Modified list: ");
    print_list(head);

    return 0;
}


// Deletes the second last node in a linked list
// The deleted node is freed.
// The head of the list is returned.
struct node *delete_second_last(struct node *head) {
    if (head == NULL) {
        return NULL;
    }

    int list_length = get_list_length(head);

    // new node is head of list
    if (head == NULL || list_length == 1) {
        free(head);
        return NULL;
    } else if (list_length == 2) {
        struct node *temp = head;
        head = head->next;
        free(temp);
        return head;
    }

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

    struct node *temp = current->next;
    current->next = current->next->next;
    free(temp);

    return head;
}

// DO NOT CHANGE THIS FUNCTION
// create linked list from array of strings
struct node *array_to_list(int len, char *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 = atoi(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");
}

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

Download list_get_middle.c here

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

1511 fetch-activity list_get_middle

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

// Return middle element of a linked list
// if list contains [6,7,8,9,10]  8 is returned
// if a list has even number of elements, first of middle two elements returned
// if list contains [1,2,3,4] 2 is returned
// list can not be empty
int get_middle(struct node *head) {

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

}

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

Add code to get_middle so that its returns the middle value of the list. If the list an even number of elements the first of the 2 elements in the middle of the list should be returned.

For example if the linked list contains these 8 elements:

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

get_middle should return 9 because 9 and 13 are the middle two elements

And, for example if the linked list contains these 5 elements:

1, 2, 8, 1, 42

get_middle should return 8 because it is the middle element.

get_middle can assume the list is not empty.

Testing

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

This main function:

1. converts the inputs to a linked list,
2. assigns a pointer to the first node in the linked list to head,
3. calls list_get_middle(head) and
4. prints the result.

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

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

Examples

dcc list_get_middle.c -o list_get_middle
./list_get_middle
How many numbers in initial list?: 9
1 2 4 8 16 32 64 128 256
16
./list_get_middle
How many numbers in initial list?: 6
2 4 6 5 8 9
6
./list_get_middle
How many numbers in initial list?: 5
13 15 17 19 18
17
./list_get_middle
How many numbers in initial list?: 2
42 4
42
./list_get_middle
How many numbers in initial list?: 1
42
42

Assumptions/Restrictions/Clarifications

• get_middle should return a single integer
• get_middle can assume the list has at least one element
• get_middle should not change the linked list it is given Your function should not change the next or data fields of list nodes
• get_middle should not use arrays
• get_middle should not call malloc
• get_middle should not call scanf (or getchar or fgets)
• get_middle 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_get_middle.c

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

1511 autotest list_get_middle

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

give cs1511 lab09_list_get_middle list_get_middle.c

You must run give before Monday 11 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 get_middle(struct node *head);
int length(struct node *head);
struct node *array_to_list(int len, int array[]);

// DO NOT CHANGE THIS MAIN FUNCTION
#define MAX_INIT_LIST_LEN 100
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);
    }

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

    return 0;
}


// Return middle element of a linked list
// if list contains [6,7,8,9,10]  8 is returned
// if a list has even number of elements, first of middle two elements returned
// if list contains [1,2,3,4] 2 is returned
// list can not be empty
int get_middle(struct node *head) {
    assert(head != NULL);
    int len = length(head);
    int middle = (len - 1)/2;

    int i = 0;
    struct node *n = head;
    while (i < middle) {
        i = i + 1;
        n = n->next;
    }
    return n->data;
}

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


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

Download list_delete_contains_string.c here

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

1511 fetch-activity list_delete_contains_string

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

// Delete the first node in the list containing the specific string
// The deleted node is freed.
// If no node contains the specified string, the list is not changed
// The head of the list is returned.
struct node *delete_contains(char string[MAX_SIZE], struct node *head) {
    return NULL;
}

Note list_delete_contains.c uses the following familiar data type:

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

delete_contains is given two argument, value and head.

• data is a string with max size of 100 characters
• head is the pointer to the first node in a linked list

The function is designed to delete the first node in the linked list that contains a specific string.

Add code to delete_contains so that it deletes the first node in the linked list that whose data field equals a specified string and returns a pointer to the new list.

• If data does not occur in the linked list, the list should not be changed.

• If data occurs more than once in the linked list, only the first occurrence should be deleted. Note, if the list is now empty delete_contains should return NULL.

delete_contains should call free to free the memory of the node it deletes.

Testing

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

This main function:

1. takes in command line arguments
2. converts the command line inputs to a linked list,
3. assigns a pointer to the first node in the linked list to head,
4. reads a sstring from standard input and assigns it to data,
5. calls delete_contains(data, head) and
6. prints the result.

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

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

dcc list_delete_contains_string.c -o list_delete_contains_string
./list_delete_contains_string cats sleep 16 to 18 hours per day
Enter a string to delete: cats
[sleep, 16, to, 18, hours, per, day]
./list_delete_contains_string the bumblebee bat is the worlds smallest mammal
Enter a string to delete: bumblebee
[the, bat, is, the, worlds, smallest, mammal]
./list_delete_contains_string
Enter a string to delete: hello
[]
./list_delete_contains_string there are parts of Africa in all four hemispheres
Enter a string to delete: four
[there, are, parts, of, Africa, in, all, hemispheres]
./list_delete_contains_string the most money ever paid for a cow in an auction was 1.3 million dollars
Enter a string to delete: dollars
[the, most, money, ever, paid, for, a, cow, in, an, auction, was, 1.3, million]

Assumptions/Restrictions/Clarifications

• delete_contains should call free to free the memory for the node it deletes
• delete_contains should not change the data fields of list nodes.
• delete_contains should not use arrays.
• delete_contains should not call malloc.
• delete_contains should not call scanf (or getchar or fgets).
• delete_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_delete_contains_string.c

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

1511 autotest list_delete_contains_string

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

give cs1511 lab09_list_delete_contains_string list_delete_contains_string.c

You must run give before Monday 11 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_delete_contains_string.c
// This program removes the node in a linked list matching a given string
// Written by Sofia De Bellis (z5418801), on July 2023

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

#define MAX_SIZE 100

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


struct node *delete_contains(char string[MAX_SIZE], struct node *head);
struct node *array_to_list(int len, char *array[]);
void print_list(struct node *head);

// DO NOT CHANGE THIS MAIN FUNCTION
int main(int argc, char *argv[]) {
    // create linked list from command line arguments excluding the program name
    struct node *head = NULL;
    if (argc > 0) {
        // list has elements
        head = array_to_list(argc - 1, &argv[1]);
    }

    printf("Enter a string to delete: ");
    char string[MAX_SIZE];
    fgets(string, MAX_SIZE, stdin);
    string[strcspn(string, "\n")] = 0;
    struct node *new_head = delete_contains(string, head);
    print_list(new_head);

    return 0;
}


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

struct node *delete_contains(char string[MAX_SIZE], struct node *head) {
    if (head == NULL) {
        // list is empty no node to delete
        return NULL;
    } else if (strcmp(head->data, string) == 0) {
        // deleting the first node
        struct node *new_head = head->next;
        free(head);
        return new_head;
    } else if (head->next == NULL) {
        // first node is the only node
        // first node is definitely not value
        return head;
    }

    struct node *n = head;
    // find node before first node containing i
    while (n->next->next != NULL && strcmp(n->next->data, string) != 0) {
        n = n->next;
    }

    if (strcmp(n->next->data, string) == 0) {
        struct node *new_next = n->next->next;
        free(n->next);
        n->next = new_next;
    }
    return head;
}

// DO NOT CHANGE THIS FUNCTION
// create linked list from array of strings
struct node *array_to_list(int len, char *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;
        strcpy(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("%s", n->data);
        if (n->next != NULL) {
            printf(", ");
        }
        n = n->next;
    }
    printf("]\n");
}

Download list_delete_highest.c here

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

1511 fetch-activity list_delete_highest

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

//
// Delete the node(s) in the list that contain the highest value
// The deleted node(s) are freed.
// The head of the list is returned.
//
struct node *delete_highest(struct node *head) {

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

}

Note list_delete_highest.c uses the following familiar data type:

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

delete_highest is given one argument, head

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

Add code to delete_highest so that it deletes the all nodes in the linked list whose data field are equal to the highest data value in the list

delete_highest should return a pointer to the new list

If the list is now empty delete_highest should return NULL

delete_highest should call free to free the memory of any node it deletes

For example if the linked list contains these 8 elements:

16, 7, 8, 19, 13, 19, 2, 12

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

16, 7, 8, 13, 2, 12

Testing

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

This main function:

1. converts the inputs to a linked list,
2. assigns a pointer to the first node in the linked list to head,
3. calls delete_highest(head) and
4. prints the result.

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

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

Examples

dcc list_delete_highest.c -o list_delete_highest
./list_delete_highest
Total numbers in list: 8
16 7 8 19 13 19 2 12
[16, 7, 8, 13, 2, 12]
./list_delete_highest
Total numbers in list: 5
200 150 27 200 200
[150, 27]
./list_delete_highest
Total numbers in list: 5
4 6 2 4 6
[4, 2, 4]
./list_delete_highest
Total numbers in list: 1
42
[]
./list_delete_highest
Total numbers in list: 0
[]

Assumptions/Restrictions/Clarifications

• delete_highest should call free to free the memory for any nodes it deletes
• delete_highest should not change the data fields of list nodes
• delete_highest should not use arrays
• delete_highest should not call malloc
• delete_highest should not call scanf (or getchar or fgets)
• delete_highest 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_delete_highest.c

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

1511 autotest list_delete_highest

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

give cs1511 lab09_list_delete_highest list_delete_highest.c

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

// List Delete Highest
// Will find the highest value stored in a linked list
// then will delete all occurences of that value
// in the list.

// Marc Chee (cs1511@cse.unsw.edu.au), April 2020

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

#define MAX_LIST_LEN 100
#define MIN_VALUE -1

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

struct node *delete_highest(struct node *head);
int return_highest(struct node *head);
struct node *delete_contains(int value, struct node *head, int *num_removed);
struct node *array_to_list(int len, int array[]);
void print_list(struct node *head);

int main(void) {
    // scan in quantity of numbers
    printf("Total numbers in list: ");
    int list_size;
    scanf(" %d", &list_size);

    // scan numbers into array
    int n_read = 0;
    int numbers_list[MAX_LIST_LEN] = {0};
    while (n_read < list_size && scanf(" %d", &numbers_list[n_read])) {
        n_read++;
    }

    // create linked list from inputs
    struct node *head = array_to_list(n_read, numbers_list);

    struct node *new_head = delete_highest(head);
    print_list(new_head);

    return 0;
}

// deletes all occurences of the highest value
// nodes in a list
// returns the head of the list
struct node *delete_highest(struct node *head) {
    if (head == NULL) {
        return head;
    }
    int highest = return_highest(head);
    
    // keep removing elements until there are none
    // of the highest left
    int num_removed = 1;
    while (num_removed) {
        head = delete_contains(highest, head, &num_removed);
    }
    return head;
}

// returns the highest value in the list
// this function assumes that the list has
// at least one element!
int return_highest(struct node *head) {
    int highest = head->data;
    struct node *current = head->next;
    while (current != NULL) {
        if (current->data > highest) {
            highest = current->data;
        }
        current = current->next;
    }
    return highest;
}

// Delete the first node in the list containing i
// The deleted node is freed.
// If no node contains i, the list is not changed
// num_removed will contain how many elements were removed
// The head of the list is returned.

struct node *delete_contains(int value, struct node *head, int *num_removed) {
    *num_removed = 0;
    if (head == NULL) {
        // list is empty no node to delete
        return NULL;
    } else if (head->data == value) {
        // deleting the first node
        struct node *new_head = head->next;
        free(head);
        *num_removed = 1;
        return new_head;
    } else if (head->next == NULL) {
        // first node is the only node
        // first node is definitely not value
        return head;
    }

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

    if (n->next->data == value) {
        struct node *new_next = n->next->next;
        free(n->next);
        n->next = new_next;
        *num_removed = 1;
    }
    return head;
}

// create linked list from array of ints
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 lists_diagonal.c here

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

1511 fetch-activity lists_diagonal

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

// Treat the linked lists like they're a 2D array
// and return 1 if the first element is repeated
// diagonally through the lists
int has_diagonal(struct list_node *head) {
    return 0;
}

lists_diagonal.c is written using struct node and struct list_node that cannot be changed.

struct node is a normal linked list node while struct list_node is used to make a linked list where each element contains a list of struct nodes.

For this exercise, you will implement the function has_diagonal It should take a pointer to the head of a struct list_node linked list, and check the values of the inner struct node linked list.

Imagine each struct node list as extending out from each struct list_node list (i.e. a 2D linked list). has_diagonal will return 1 if there is a diagonal pattern, and 0 if there isn't.

A diagonal in this exercise means that the first number in the first list is the same as the second number in the second list and the third number in the third list and so on.

For example if the list of lists looks like this:

list_node 0 contains the list {5, 0, 0}
list_node 1 contains the list {0, 5, 0}
list_node 2 contains the list {0, 0, 5}

has_diagonal should return 1 as the number 5 is repeated diagonally down the list of lists:

list_node 0 contains the list {5, 0, 0}
list_node 1 contains the list {0, 5, 0}
list_node 2 contains the list {0, 0, 5}

However, if the list of lists looks like this:

list_node 0 contains the list {5, 0, 0, 0}
list_node 1 contains the list {0, 4, 0, 0}
list_node 2 contains the list {0, 0, 5, 0}
list_node 3 contains the list {0, 0, 0, 5}

has_diagonal should return 0, because the 2nd element of the second list does not equal the value of the first element of the first list:

list_node 0 contains the list {5, 0, 0, 0}
list_node 1 contains the list {0, 4, 0, 0}
list_node 2 contains the list {0, 0, 5, 0}
list_node 3 contains the list {0, 0, 0, 5}

Assumptions/Restrictions/Clarifications

• struct node and struct list_node cannot be edited. They must be used as they are
• You may not use arrays in this solution. Arrays are not necessary to complete this task
• You can assume that you'll never receive an empty list of struct list_nodes
• You can assume that all lists of struct nodes are also not empty
• You can assume that there will always be the same number of struct nodes in each list and that will be the same number of struct list_nodes. That is to say, the 2D grid formed by the lists will always be square
• Your submitted file may contain a main function. It will not be tested or marked

1511 style lists_diagonal.c

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

1511 autotest lists_diagonal

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

give cs1511 lab09_lists_diagonal lists_diagonal.c

You must run give before Monday 11 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>

// Do not edit these structs. You may use them exactly as
// they are but you cannot make changes to them

// A node in a linked list
struct node {
    int data;
    struct node *next;
};

// a list_node in a linked list. Each list_node
// contains a list of nodes.
struct list_node {
    struct node *my_list;
    struct list_node *next;
};

// Treat the linked lists like they're a 2D array
// and return 1 if the first element is repeated
// diagonally through the lists
int has_diagonal(struct list_node *head) {
    int has = 1;
    int i = 0;
    // assuming that we're never getting an empty first list
    int number = head->my_list->data;
    while (head != NULL) {
        int j = 0;
        struct node *n = head->my_list;
        while (n != NULL) {
            if (j == i && n->data != number) {
                // we're at the diagonal and they're not equal
                has = 0;
            }
            n = n->next;
            j++;            
        }
        i++;
        head = head->next;
    }
    return has;
}

// This helper function is for the main below and will
// have no effect on your has_diagonal. It does not
// need to be modified.
struct node *make_list(int a, int b, int c);

// This is a main function which could be used
// to test your has_diagonal function.
// It will not be marked.
// Only your has_diagonal function will be marked.
//
// It's recommended to change the int values in this
// main to test whether your has_diagonal is working.
int main(void) {
    struct list_node *head = malloc(sizeof(struct list_node));
    struct list_node *l = head;
    
    // create the first list
    l->my_list = make_list(5, 0, 0);
    
    // create the second list
    l->next = malloc(sizeof(struct list_node));
    l = l->next;
    l->my_list = make_list(0, 5, 0);
    
    // create the third list
    l->next = malloc(sizeof(struct list_node));
    l = l->next;
    l->my_list = make_list(0, 0, 5);
    l->next = NULL;
    
    printf("The result of has_diagonal is: %d\n", has_diagonal(head));
    
    return 0;
}

struct node *make_list(int a, int b, int c) {
    struct node *head = malloc(sizeof(struct node));
    struct node *n = head;
    n->data = a;
    n->next = malloc(sizeof(struct node));
    n = n->next;
    n->data = b;
    n->next = malloc(sizeof(struct node));
    n = n->next;
    n->data = c;
    n->next = NULL;
    
    return head;
}

Download musical_chairs.c here

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

1511 fetch-activity musical_chairs

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

// Make music for a certain number of turns.
// Each turn of music makes the players move
// one chair along the list.
// After they've moved that many times, the
// first chair in the list is removed, along
// with the person sitting in it.
struct chair *make_music(int turns, struct chair *chairs) {
    // IMPLEMENT THIS FUNCTION
    return chairs;
}

Welcome to the Game of Chairs, where you either win or have your memory freed.

musical_chairs is written using the following structs that cannot be changed:

// player in the game of chairs
struct player {
    char name[MAX_NAME_LENGTH];
};

// A node in a linked list of chairs
struct chair {
    struct player *sitting;
    struct chair *next;
};

The chair struct is a linked list node.

The player struct represents a player that can sit on a chair (represented by the chair's pointer aiming at the player).

make_music is given a pointer to a chair, which is the first element in a list of chairs. It is also given an int turns which represents how many turns of movement there will be before the music stops.

Like the game of Musical Chairs, this program will have players move along the linked list, changing which chair they're sitting in.

In make_music, every player moves turns spaces along the linked list. Anyone who moves off the end of the linked list, should then move to the head of the list, so the players will end up rotating through the list as if it's a loop. This would be similar to if the next of the last chair was aimed at the first chair.

Once all the players have finished moving, the head of the list of chairs is removed. This means both that chair and the player sitting in it are removed from the game. make_music should then print out the name of the player that was removed.

Be careful to make sure you free all memory used in this game!

For example if a list of chairs called thrones looks like this:

throne points at the player named "Spoiler Alert"
throne points at the player named "Eddard Stark"
throne points at the player named "Joffrey Baratheon"
throne points at the player named "Cersei Lannister"
throne points at the player named "Robert Baratheon"

Then the following function is called:

make_music(3, thrones);

The output would be:

Joffrey Baratheon

and the resulting linked list would look like this:

(throne pointed at "Joffrey Baratheon" but was removed)
throne points at the player named "Cersei Lannister"
throne points at the player named "Robert Baratheon"
throne points at the player named "Spoiler Alert"
throne points at the player named "Eddard Stark"

In this list, all the players have moved down 3 chairs and are now sitting in different chairs. Anyone that moved past the end of the chairs was moved back to the top of the list of chairs.

Assumptions/Restrictions/Clarifications

• You can assume the list provided to make_music will not be empty.
• You can assume the number of turns will not be negative.
• struct player and struct chair cannot be edited. They must be used as they are.
• The be_seated function will help you create chairs. It cannot be edited and must be used as it is. You may not use arrays in this solution. Arrays are not necessary to complete this task.
• You must free all memory used in your program. Use dcc --leak-check if you need to check for memory leaks. Autotest will also check your code for leaks
• Your submitted file may contain a main function. It will not be tested or marked.

1511 style musical_chairs.c

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

1511 autotest musical_chairs

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

give cs1511 lab09_musical_chairs musical_chairs.c

You must run give before Monday 11 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>

#define MAX_NAME_LENGTH 100

// Do not edit these structs. You may use them exactly as
// they are but you cannot make changes to them

// player in the game of chairs
struct player {
    char name[MAX_NAME_LENGTH];
};

// A node in a linked list of chairs
struct chair {
    struct player *sitting;
    struct chair *next;
};

// Move the players along to the next chair
// The chairs are acting as a loop, so if 
// a player moves off the end of the list,
// they'll end up back at the start
void move_players(struct chair *chairs) {
    struct chair *c = chairs;
    struct player *unseated = NULL;
    while (c != NULL) {
        struct player *moving = c->sitting;
        c->sitting = unseated;
        unseated = moving;
        c = c->next;
    }
    // the last unseated then goes back to the
    // first chair
    if (chairs != NULL) {
        chairs->sitting = unseated;
    }
}

// Make music for a certain number of turns
// Each turn of music makes the players move
// one chair along the list.
// After they've moved that many times, the
// first chair in the list is removed, along
// with the person sitting in it
struct chair *make_music(int turns, struct chair *chairs) {
    int i = 0;
    while (i < turns) {
        move_players(chairs);
        i++;
    }
    // remove the head!
    struct chair *beheaded = chairs;
    printf("%s\n", beheaded->sitting->name);
    chairs = chairs->next;
    free(beheaded->sitting);
    free(beheaded);
    
    return chairs;
}

// This helper function is only for this main, but
// it may help you to both understand and test this exercise.
// You may use this function for testing, but
// YOU CANNOT CHANGE THIS FUNCTION
struct chair *be_seated(char name[MAX_NAME_LENGTH], struct chair *heir) {
    struct chair *c = malloc(sizeof(struct chair));
    c->sitting = malloc(sizeof(struct player));
    strcpy(c->sitting->name, name);
    c->next = heir;
    return c;
}

// This is a main function which could be used
// to test your make_music function.
// It will not be marked.
// Only your make_music function will be marked.
int main(void) {
    struct chair *thrones = be_seated("Robert Baratheon", NULL);
    thrones = be_seated("Cersei Lannister", thrones);
    thrones = be_seated("Joffrey Baratheon", thrones);
    thrones = be_seated("Eddard Stark", thrones);
    thrones = be_seated("Spoiler Alert", thrones);
        
    thrones = make_music(1, thrones);
    thrones = make_music(3, thrones);
    thrones = make_music(0, thrones);
    thrones = make_music(2, thrones);

    free(thrones->sitting);
    free(thrones);
        
    return 0;
}

Welcome to Week 9 of COMP1511. The end of term is in sight!

If you've come this far in this week's lab, you're probably feeling pretty confident in some aspects of the course! So, why not help yourself and your peers by creating a resource that teaches a concept in COMP1511?

Details

For this exercise, create content that helps teach a concept in COMP1511. This could be a video, a program, a blog, or anything else you can think of.

If you're not sure what to do, chat to your tutor for inspiration!

(When you're done, post your creation on the forum.)[https://edstem.org/au/courses/9913/discussion/]

We may also post some of the resources you share in one place, so everyone can benefit from them!

If you're interested in becoming a tutor for a COMP course, this can also be great practice, as one requirement we have for tutoring applicants is making a short explainer video.

Download debug_remove_nth.c here

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

1511 fetch-activity debug_remove_nth

Note that this exercise is not marked or worth marks!

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 task takes in a linked list via command line arguments. Prompts the user to input the index n of the node which they wish to remove form the list. Then, the program attempts to remove the node at index n via calling the delete_nth function.

For example if the existing list is 1 -> 2 -> 3 -> 4-> X, if the user inputs 2 as the index of the node they wish to delete after calling the delete_nth function on the list is as follows: 1 -> 2 -> 4 -> X. Note, the node containing the value 3 is removed from the list since is the node at index 2 in the original list. Note we start counting indexes from 0.

Currently it has some issues it is your job to figure them out and fix the code. Note, you should only need to modify the delete_nth function to fix the program.

Examples

dcc debug_remove_nth.c -o debug_remove_nth
./debug_remove_nth 1 2 3 4 5 6
What is the position of the node you wish to remove: 2
Original list: [1, 2, 3, 4, 5, 6]
Modified list: [1, 2, 4, 5, 6]
./debug_remove_nth 1 2 3
What is the position of the node you wish to remove: 0
Original list: [1, 2, 3]
Modified list: [2, 3]
./debug_remove_nth 1 2 3 4 5
What is the position of the node you wish to remove: 4
Original list: [1, 2, 3, 4, 5]
Modified list: [1, 2, 3, 4]
./debug_remove_nth 1
What is the position of the node you wish to remove: 0
Original list: [1]
Modified list: []
./debug_remove_nth 
What is the position of the node you wish to remove: 0
Original list: []
Modified list: []
./debug_remove_nth 1 2 3 4
What is the position of the node you wish to remove: 4
Original list: [1, 2, 3, 4]
Index out of range, no node deleted
Modified list: [1, 2, 3, 4]
./debug_remove_nth 1 2 3 4
What is the position of the node you wish to remove: -1
Original list: [1, 2, 3, 4]
Index out of range, no node deleted
Modified list: [1, 2, 3, 4]

Assumptions/Restrictions/Clarifications

• You may assume all command line arguments will be integers
• The function prints Index out of range, no node deleted if the index entered by the user is greater then the legnth of the list. It then also does not modify the list.

Walkthrough

Below is a video walkthrough of this exercise! Make sure to attempt it before watching this video

1511 style debug_remove_nth.c

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

1511 autotest debug_remove_nth

// debug_remove_nth.c
// This program removes the nth node of a linked list
// Written by Sofia De Bellis (z5418801), on July 2023

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

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


struct node *delete_nth(struct node *head, int index);
struct node *array_to_list(int len, char *array[]);
void print_list(struct node *head);
int get_list_length(struct node *head);

// DO NOT CHANGE THIS MAIN FUNCTION
int main(int argc, char *argv[]) {
    // create linked list from command line arguments excluding the program name
    struct node *head = NULL;
    if (argc > 0) {
        // list has elements
        head = array_to_list(argc - 1, &argv[1]);
    }
    int index;
    printf("What is the position of the node you wish to remove: ");
    scanf("%d", &index);
    printf("Original list: ");
    print_list(head);
    head = delete_nth(head, index);
    printf("Modified list: ");
    print_list(head);

    return 0;
}


// Deletes the second last node in a linked list
// The deleted node is freed.
// The head of the list is returned.
struct node *delete_nth(struct node *head, int index) {
    struct node *current = head;

    if (head == NULL) {
        return NULL;
    }

    if (index == 0) {
        struct node *temp = head;
        current = current->next;
        free(temp);
        return current;
    }

    int list_length = get_list_length(head);

    if (index > list_length - 1 || index < 0) {
        printf("Index out of range, no node deleted\n");
        return head;
    }

    int i = 0;
    while (current->next != NULL && i < index - 1) {
        current = current->next;
        i++;
    }

    struct node *temp = current->next;
    current->next = temp->next;
    free(temp);

    return head;
}

// DO NOT CHANGE THIS FUNCTION
// create linked list from array of strings
struct node *array_to_list(int len, char *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 = atoi(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");
}

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

You can run give multiple times. Only your last submission will be marked.

Don't submit any exercises you haven't attempted.

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

Remember you have until Week 10 Monday 20:00 to submit your work.

You cannot obtain marks by e-mailing your code to tutors or lecturers.

You check the files you have submitted here.

Automarking will be run by the lecturer several days after the submission deadline, using test cases different to those autotest runs for you. (Hint: do your own testing as well as running autotest.)

After automarking is run by the lecturer you can view your results here. The resulting mark will also be available via give's web interface.