Programming Fundamentals

Download list_count_consecutive.c here

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

1511 fetch-activity list_count_consecutive

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

// TODO: FIX THIS FUNCTION
// Counts the number of consecutive items in a list
// e.g. [2, 3, 2, 5, 4] has 3 consecutive occurances
int count_consecutive(struct node *head) {

    int n_consec = 0;

    struct node *curr = head;
    struct node *prev = NULL;
    while (curr != NULL) {
        // checking to see if previous and current and consecutive.
        if (prev - curr == 1 || prev - curr == -1) {
            n_consec++;
        }

        curr = curr->next;
        prev = prev->next;
    }
    return n_consec;
}

Your job is to fix the function count_consecutive(). Currenty it nearly works, but has some bugs in it

The function should take in a head of a list, and count the number of time two adjacent values in the list are consecutive. In other words, it counts the number of times that a pair of values that are next to each other are 1 value apart

It should return the number of consecutive occurances in the list

When doing this exercise, try to identify what bugs the program had (and how to fix it) instead of just rewriting the program

dcc list_consecutive.c -o list_consecutive
./list_consecutive
How many numbers in initial list?: 
3
1 2 3
There is/are 2 consecutive occurances.
./list_consecutive
How many numbers in initial list?: 
5
1 2 4 5 4
There is/are 3 consecutive occurances.
./list_consecutive
How many numbers in initial list?: 
1
6
There is/are 0 consecutive occurances.
./list_consecutive
How many numbers in initial list?: 
0
There is/are 0 consecutive occurances.

Assumptions/Restrictions/Clarifications

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

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

1511 autotest list_count_consecutive

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

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

int count_consecutive(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);
    }

    int n_consec = count_consecutive(head);
    printf("There is/are %d consecutive occurances.\n", n_consec);

    return 0;
}

// TODO: FIX THIS FUNCTION
// Counts the number of consecutive items in a list
// e.g. [2, 3, 2, 5, 4] has 3 consecutive occurances
int count_consecutive(struct node *head) {

    int n_consec = 0;

    if (head == NULL || head->next == NULL) {
        return 0;
    }

    struct node *curr = head->next;
    struct node *prev = head;
    while (curr != NULL) {
        if (prev->data - curr->data == 1 ||
            prev->data - curr->data == -1) {

            n_consec++;
        }

        prev = curr;
        curr = curr->next;
    }
    return n_consec;
}

// 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 list_sum.c here

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

1511 fetch-activity list_sum

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

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

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

}

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

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

For example if the linked list contains these 8 elements:

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

sum should return 120 because 1 + 7 + 8 + 9 + 13 + 19 + 21 + 42 = 120

Testing

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

This main function:

• converts the command-line arguments to a linked list
• assigns a pointer to the first node in the linked list to head
• calls list_sum(head)
• prints the result.

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

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

Here is how you use main function allows you to test list_sum:

dcc list_sum.c -o list_sum
./list_sum 1 2 4 8 16 32 64 128 256
511
./list_sum 2 4 6 5 8 9
34
./list_sum 13 15 17 17 18
80
./list_sum 42 4
46
./list_sum
0

Assumptions/Restrictions/Clarifications

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

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

1511 autotest list_sum

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

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

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

    return 0;
}

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


// 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 sum of a linked list.
int sum(struct node *head) {
    if (head == NULL) {
        return 0;
    }
    return head->data + sum(head->next);
}

Download list_count_favourite.c here

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

1511 fetch-activity list_count_favourite

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

// Return the number of elements divisible by 17 in the linked list
int count_favourite(struct node *head) {

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

}

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

Add code to count_favourite so that its returns the number of elements divisible by 17 in the list.

For example if the linked list contains these 8 elements:

51, 7, 8, 9, 34, 19, 34, 42

count_favourite should return 3 because 51, 34 and 34 are divisible by 17.

Testing

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

This main function:

• converts the command-line arguments to a linked list
• assigns a pointer to the first node in the linked list to head
• calls list_count_favourite(head)
• prints the result.

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

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

Examples

Here is how you use main function allows you to test list_count_favourite:

dcc list_count_favourite.c -o list_count_favourite
./list_count_favourite 51 7 8 9 34 19 34 42
3
./list_count_favourite 2 4 6 5 8 9
0
./list_count_favourite 17 34 51 68 85 102 119 136 153
9
./list_count_favourite
0

Assumptions/Restrictions/Clarifications

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

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

1511 autotest list_count_favourite

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

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

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

    return 0;
}

// Return the number of elements divisible by 17 in the linked list
int count_favourite(struct node *head) {
    int count = 0;
    struct node *n = head;
    while (n != NULL) {
        if (n->data % 17 == 0) {
            count = count + 1;
        }
        n = n->next;
    }
    return count;
}


// 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 the number of elements divisible by 17 in the linked list
int count_favourite(struct node *head) {
    if (head == NULL) {
        return 0;
    }
    return (head->data % 17 == 0) + count_favourite(head->next);
}

Download list_get_nth.c here

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

1511 fetch-activity list_get_nth

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

// Return the n-th element of linked list.
// n == 0 returns first element, n == 1, second element, ....
int get_nth(int n, struct node *head) {

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

}

get_nth is given two arguments, an int n and head, which is the pointer to the first node in a linked list.

Add code to get_nth so that its returns the n-th element the linked element of the linked 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.

get_nth can assume that the list contains at least n + 1 elements.

For example if the linked list contains these 8 elements:

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

if n is 1, get_nth should return 7.

Testing

list_get_nth.c also get_nth a main function which allows you to test your get_nth function.

This main function:

• converts the first command-line argument to n
• converts the remaining command-line arguments to a linked list
• assigns a pointer to the first node in the linked list to head
• calls list_get_nth(n, head)
• prints the result.

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

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

Examples

Here is how you use main function allows you to test list_get_nth:

dcc list_get_nth.c -o list_get_nth
./list_get_nth 0  5 6 7 8
5
./list_get_nth 1  5 6 7 8
6
./list_get_nth 2  5 6 7 8
7
./list_get_nth 3  5 6 7 8
8
./list_get_nth 0  42
42

Assumptions/Restrictions/Clarifications

• get_nth should return a single integer.
• get_nth can assume n is non-negative.
• get_nth can assume the linked list contains at least n + 1 elements.
• get_nth should not change the linked list it is given.
• Your function should not change the next or data fields of list nodes.
• get_nth should not use arrays.
• get_nth should not call malloc.
• get_nth should not call scanf (or getchar or fgets).
• get_nth should not print anything. It should not call printf.
• Do not change the supplied main function. It will not be tested or marked.

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

1511 autotest list_get_nth

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

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

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

int main(int argc, char *argv[]) {
    if (argc < 2) {
        fprintf(stderr, "Usage: %s value list-elements\n", argv[0]);
        return 1;
    }

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

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

    return 0;
}

// Return the n-th element of linked list.
// n == 0 returns first element, n == 1, second element, ....
int get_nth(int n, struct node *head) {
    assert(n >= 0);
    struct node *p = head;
    int i = n;
    while (i > 0) {
        assert(p != NULL);
        p = p->next;
        i = i - 1;
    }
    assert(p != NULL);
    return p->data;
}


// 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 the n-th element of linked list.
// n == 0 returns first element, n == 1, second element, ....
int get_nth(int n, struct node *head) {
    assert(head != NULL && n >= 0);
    if (n == 0) {
        return head->data;
    }
    return get_nth(n - 1, head->next);
}

Download array_print_pointer.c here

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

1511 fetch-activity array_print_pointer

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

// Assumes that the pointer is aimed at one of the array elements.
void array_print_pointer(int nums[LENGTH], int *last) {
    printf("I should output some elements of the array.\n");
}

The above file array_print_pointer.c contains a function array_print_pointer, which should print out the elements of an array from the first element up to and including the element referenced by the pointer "last", which is an input to the function.

Each element printed should be followed by a space.

For this exercise, your task is to complete this function.

Note: you must not modify the array within the array_print_pointer function. You should only read the values in the array, not change them.

Note: All the arrays you are given will be of a fixed length, 10, which is defined as a constant.

Note: You can assume that the pointer "last" given as input to the function will always contain the address of one of the elements of the list.

The file also contains a main function which you can use to help test your array_print_pointer function. It has an example test case.

This main function will not be marked -- you must write all of your code in the array_print_pointer function.

You may modify the main function if you wish (e.g. to add further tests), but only the array_print_pointer function will be marked.

Once your program is working, the output from the provided test in the main function should be:

dcc -o array_print_pointer array_print_pointer.c 
./array_print_pointer 
1 2 3 4 5 6 

This diagram represents what the example above may look like in memory. In this diagram the computer placed the array starting at address 0xFFFF FF80, but this will almost certainly not be where it is placed when you run the program so do not use this address in your code.

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

1511 autotest array_print_pointer

// COMP1511 Array Print Pointer
// Print out the contents of an array, starting
// from index 0 and ending by printing out
// a particular element that is also being
// pointed at by a given pointer

// Marc Chee, March 2020

#include <stdio.h>

#define LENGTH 10

void array_print_pointer(int nums[LENGTH], int *last);

// This is a simple main function that you can use to test your array_print_pointer
// function.
// It will not be marked - only your array_print_pointer function will be marked.
//
// Note: the autotest does not call this main function!
// It calls your array_print_pointer function directly.
// Any changes that you make to this main function will not affect the autotests.

int main(int argc, char *argv[]){
   int nums[LENGTH] = {1,2,3,4,5,6,7,8,9,10};
   int *last = &nums[5];

   //Pass in the address of the sum and product variables
   array_print_pointer(nums, last);

   return 0;
}

// Print an array from the beginning until it reaches
// a pointer. Assumes that the pointer is aimed at one
// of the array elements.
void array_print_pointer(int nums[LENGTH], int *last) {
    int i = 0;
    int stop = 0;
    while (stop == 0 && i < LENGTH) { // printed i numbers
        printf("%d ", nums[i]);
        if (&nums[i] == last) { // last is aimed at nums[i]
            stop = 1;
        }
        i++;
    }
}

Download split_sum.c here

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

1511 fetch-activity split_sum

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

/**
 * The array is split into two parts by the index passed in so 
 * the first part has indexes until the index non-inclusive and 
 * the second part has indexes including the index till the end of the array.
 * This function finds the sum of the first part and puts it into the first sum,
 * and finds the sum of the second part and puts it into the second sum.
 *
 * Takes in 
 * the array "array", 
 * the array's length "length", 
 * the index that splits the array into two parts "index", 
 * a pointer to where the value of the first part of the array's sum should be 
 * placed "first_sum" and 
 * a pointer to where the value of the second part of the array's sum should be 
 * placed "second_sum".
 *
 * Returns nothing.
 */
void split_sum(int array[], int length, int index, int *first_sum, int *second_sum) {

    // TODO complete this function

    return;
}

In this exercise you will be asked to sum two parts of an array and store the results at two given addresses.

You will implement the split_sum function, which takes five arguments: array, length, index, first_sum and second_sum. You should sum the array's values from the start of the array up to (but not including) the index given and put the result into first_sum, and then sum the array's values from the index till the end of the array and put the result into second_sum.

Examples

dcc split_sum.c -o split_sum
./split_sum
Enter length: 3
Enter array values: 11 2 3
Enter index: 1
First sum: 11
Second sum: 5
./split_sum
Enter length: 6
Enter array values: 1 2 3 4 5 6
Enter index: 4
First sum: 10
Second sum: 11
./split_sum
Enter length: 7
Enter array values: 12 45 24 57 10 8 12
Enter index: 2
First sum: 57
Second sum: 111

Assumptions/Restrictions/Clarifications

• You may assume the index given is between 0 and the length of the array inclusive.
• You may assume you always receive valid inputs.
• Hint: The sum of an empty array is 0.

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

1511 autotest split_sum

#include <stdio.h>

#define MAX_SIZE 100

/**
 * The array is split into two parts by the index passed in so 
 * the first part has indexes until the index non-inclusive and 
 * the second part has indexes including the index till the end of the array.
 * This function finds the sum of the first part and puts it into the first sum,
 * and finds the sum of the second part and puts it into the second sum.
 *
 * Takes in 
 * the array "array", 
 * the array's length "length", 
 * the index that splits the array into two parts "index", 
 * a pointer to where the value of the first part of the array's sum should be 
 * placed "first_sum" and 
 * a pointer to where the value of the second part of the array's sum should be 
 * placed "second_sum".
 *
 * Returns nothing.
 */
void split_sum(int array[], int length, int index, int *first_sum, int *second_sum) {

    // Gets the first sum of the array
    int i = 0;
    int sum = 0;
    while (i < index) {
        sum += array[i];
        i += 1;
    }
    *first_sum = sum;

    // Gets the second sum of the array
    sum = 0;
    while (i < length) {
        sum += array[i];
        i += 1;
    }
    *second_sum = sum;

    return;
}

/**
 * This is a simple main function that you can use to test your 
 * split_sum function.
 * It will not be marked - only your split_sum function will be marked.
 *
 * Note: The autotest does not call this main function!
 * It calls your split_sum function directly.
 * Any changes that you make to this main function will not affect the autotests.
 */
int main(void) {

    printf("Enter length: ");
    int length;
    scanf("%d", &length);

    printf("Enter array values: ");
    int i = 0;
    int array[MAX_SIZE] = {0};
    while (i < length) {
        scanf("%d", &array[i]);
        i += 1;
    }

    printf("Enter index: ");
    int index;
    scanf("%d", &index);
    
    int first_sum;
    int second_sum;
    split_sum(array, length, index, &first_sum, &second_sum);

    printf("First sum: %d\n", first_sum);
    printf("Second sum: %d\n", second_sum);

    return 0;
}

Download list_delete_second_last.c here

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

1511 fetch-activity list_delete_second_last

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

//
// Delete the second last node in the list.
// The deleted node is freed.
// The head of the list is returned.
//
struct node *delete_second_last(struct node *head) {

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

Note list_delete_second_last.c uses the following familiar data type:

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

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

Add code to delete_second_last so that it deletes the second last node from list.

delete_second_last should return a pointer to the new list.

If the list is empty, delete_second_last should return NULL.

If the list has exactly one element, delete_second_last should return that one element unchanged.

delete_second_last 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_second_last should return a pointer to a list with these elements:

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

Testing

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

This main function:

• converts the command-line arguments to a linked list
• assigns a pointer to the first node in the linked list to head
• calls delete_second_last(head)
• prints the result.

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

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

Examples

dcc list_delete_second_last.c -o list_delete_second_last
./list_delete_second_last 16 7 8 12 13 19 21 12
[16, 7, 8, 12, 13, 19, 12]
./list_delete_second_last 2 4 6 2 4 6
[2, 4, 6, 2, 6]
./list_delete_second_last 42
[42]
./list_delete_second_last
[]

Assumptions/Restrictions/Clarifications

• delete_second_last should call free to free the memory for the node it deletes
• delete_second_last should not change the data fields of list nodes.
• delete_second_last should not use arrays.
• delete_second_last should not call malloc.
• delete_second_last should not call scanf (or getchar or fgets).
• delete_second_last should not print anything. It should not call printf.
• Do not change the supplied main function. It will not be tested or marked.

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

1511 autotest list_delete_second_last

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

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

struct node *delete_second_last(struct node *head);
struct node *strings_to_list(int len, char *strings[]);
void print_list(struct node *head);

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

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

    return 0;
}

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

struct node *delete_second_last(struct node *head) {
    if (head == NULL || head->next == NULL) {
        // list is empty no node to delete
        return head;
    }
    if (head->next->next == NULL) {
        struct node *tmp = head->next;
        free(head);
        return tmp;
    }
    struct node *n = head;
    // find second last node in list
    while (n->next->next->next != NULL) {
        n = n->next;
    }
    struct node *tmp = n->next;
    n->next = n->next->next;
    free(tmp);

    return head;
}

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

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

Download list_split.c here

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

1511 fetch-activity list_split

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

// Given a list with at least one node, and exactly one 0,
// split the list into a list with everything before the 0,
// and a list with the 0 and everything after.
// Return a malloced split_list struct with each of these lists.
struct split_list *split(struct node *head) {

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

}

Note list_split.c uses the following familiar data type:

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

As well as this new datatype:

struct split_list {
    struct node *before;
    struct node *after;
};

split is given one argument, head. head is the pointer to the first node in a linked list. That linked list will contain at least one node, and exactly one of those nodes will have data 0.

Add code to split so that it splits the given list into two smaller lists, one linked list that contains all the nodes before the 0; and one linked list that contains the 0, and any following nodes.

split should return a malloced split_list struct.

If the zero is the first node, it should return a split_list struct with before = NULL.

If the zero is the last node, it should return a split_list struct with after being a pointer to that zero.

For example if the linked list contains these 8 elements:

16, 7, 8, 19, 0, 19, 2, 12

split should return a pointer to a split_list struct with before pointing to:

16, 7, 8, 19

And after pointing to:

0, 19, 2, 12

Testing

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

This main function:

• converts the command-line arguments to a linked list
• assigns a pointer to the first node in the linked list to head
• calls split(head)
• prints the result.

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

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

dcc list_split.c -o list_split
./list_split 0 1 2 3
split([0, 1, 2, 3])
before = []
after = [0, 1, 2, 3]
./list_split 5 3 -1 1 0
split([5, 3, -1, 1, 0])
before = [5, 3, -1, 1]
after = [0]
./list_split 1 2 -3 -4 0 -4 3 -2 1
split([1, 2, -3, -4, 0, -4, 3, -2, 1])
before = [1, 2, -3, -4]
after = [0, -4, 3, -2, 1]

Assumptions/Restrictions/Clarifications

• split should not free any memory.
• split should not change the data fields of list nodes.
• split should not use arrays.
• split will need to call malloc exactly once.
• split should not call scanf (or getchar or fgets).
• split should not print anything. It should not call printf.
• You do not need to change the supplied main function. It will not be tested or marked.

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

1511 autotest list_split

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

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

struct split_list {
    struct node *before;
    struct node *after;
};

struct split_list *split(struct node *head);
struct node *strings_to_list(int len, char *strings[]);
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
    struct node *head = strings_to_list(argc - 1, &argv[1]);

    struct split_list *list_split = split(head);
    printf("before = ");
    print_list(list_split->before);
    printf("after = ");
    print_list(list_split->after);

    return 0;
}


// Given a list with exactly one 0 in it, split
// the list into a list with everything before the 0,
// and a list with the 0 and everything after.
// Return a malloced split_list struct with each of these lists.
struct split_list *split(struct node *head) {
    struct split_list *list_split = malloc(sizeof(struct split_list));
    list_split->before = NULL;
    list_split->after = NULL;
    if (head->data == 0) {
        list_split->after = head;
        return list_split;
    } else {
        list_split->before = head;
        struct node *curr = head;

        while (curr->next != NULL) {
            if (curr->next->data == 0) {
                list_split->after = curr->next;
                curr->next = NULL;
                return list_split;
            }
            curr = curr->next;
        }
    }

    return NULL;

}


// 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;
        n->data = atoi(strings[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 list_get_nth_last.c here

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

1511 fetch-activity list_get_nth_last

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

// Return the n-th last element of linked list.
// n == 1 returns last element, n == 2, second last element, ....
int get_nth_last(int n, struct node *head) {

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

}

get_nth_last is given two arguments, an int n and head, which is the pointer to the first node in a linked list.

Add code to get_nth_last so that its returns the n-th last element the linked element of the linked list.

The elements are counted backwards, so the last element is element 1; the second last element is element 2.

get_nth_last can assume that the list contains at least n elements.

For example if the linked list contains these 8 elements:

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

if n is 2 get_nth_last should return 21.

Testing

list_get_nth_last.c also get_nth_last a main function which allows you to test your get_nth_last function.

This main function:

• converts the first command-line argument to n
• converts the remaining command-line arguments to a linked list
• assigns a pointer to the first node in the linked list to head
• calls list_get_nth_last(n, head)
• prints the result.

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

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

Examples

Here is how you use main function allows you to test list_get_nth_last

dcc list_get_nth_last.c -o list_get_nth_last
./list_get_nth_last 1  5 6 7 8
8
./list_get_nth_last 2  5 6 7 8
7
./list_get_nth_last 3  5 6 7 8
6
./list_get_nth_last 4  5 6 7 8
5
./list_get_nth_last 1  42
42

Assumptions/Restrictions/Clarifications

• get_nth-last should return a single integer.
• get_nth-last can assume n is non-negative.
• get_nth-last can assume the linked list contains at least n elements.
• get_nth-last should not change the linked list it is given. Your function should not change the next or data fields of list nodes.
• get_nth-last should not use arrays.
• get_nth-last should not call malloc.
• get_nth-last should not call scanf (or getchar or fgets).
• get_nth-last should not print anything. It should not call printf.
• Do not change the supplied main function. It will not be tested or marked.

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

1511 autotest list_get_nth_last

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

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

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

int main(int argc, char *argv[]) {
    if (argc < 2) {
        fprintf(stderr, "Usage: %s value list-elements\n", argv[0]);
        return 1;
    }
    int value = atoi(argv[1]);
    // create linked list from command line arguments
    struct node *head = strings_to_list(argc - 2, &argv[2]);

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

    return 0;
}

// Return the n-th to last element of linked list.
// n == 1 returns last element, n == 2, second last element, ....
int get_nth_last(int n, struct node *head) {
    assert(n >= 0);
    struct node *p = head;
    int len = 0;
    struct node *c = head;
    while (c) {
        len++;
        c = c->next;
    }
    int i = len - n;
    while (i > 0) {
        assert(p != NULL);
        p = p->next;
        i = i - 1;
    }
    return p->data;
}


// 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_delete_ordered.c here

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

1511 fetch-activity list_delete_ordered

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

// Remove any nodes in a list that are higher 
// than the node directly after them.
// Return the head of the list.
// The returned list must have no disorder in it!
struct node *remove_disorder(struct node *head) {
    // WRITE YOUR CODE HERE (you may need to change the line below)
    return head;
}

remove_disorder is written using the following struct that cannot be changed:

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

The node struct is a normal linked list node containing an integer.

remove_disorder should take a pointer to the head of a node list and return the head of the node list after it has removed any disorder in the list. A list is considered to have disorder if there are any nodes in it that are higher in value (using the integer data) than the node directly after them.

remove_disorder should remove nodes from the list, making sure to reconnect the list back together if for example a node from the middle of the list is removed for being disordered.

For example if the list of nodes looks like this:

{1, 3, 2}

remove_disorder should return the head of the list, with 3 now removed

{1, 2}

However, if the list looks like this:

{2, 4, 5, 1}

remove_disorder should return the head of the list

{1}

The 5 is definitely removed for being higher than the 1. After that, the 4 is then disordered because it is now next to the 1 and higher than it. Then, the 2 must be removed because it will be next to the 1 and higher than it.

Assumptions/Restrictions/Clarifications

• struct node cannot be edited. It must be used as it is.
• 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 nodes.

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

1511 autotest list_delete_ordered

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

// Do not edit this struct. You may use it exactly as
// it is but you cannot make changes to it

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

// ADD ANY FUNCTION DECLARATIONS YOU WISH TO USE HERE

// Remove any nodes in a list that are higher 
// than the node directly after them.
// Return the head of the list.
// The returned list must have no disorder in it!
struct node *remove_disorder(struct node *head) {
    int exit = 0;
    
    while (!exit) {
        struct node *prev = NULL;
        struct node *remNode = head;

        // find a node that needs to be removed
        while (remNode != NULL && remNode->next != NULL && remNode->data <= remNode->next->data) {
            prev = remNode;
            remNode = remNode->next;
        }
        // remove that node if it was found
        if (remNode != NULL && remNode->next != NULL) {
            if (prev == NULL) {
                // remNode is the first element of the list
                head = remNode->next;
            } else {
                prev->next = remNode->next;
            }
            free(remNode);
        } else {
            // there was no node to remove, which means the list
            // has no disorder
            exit = 1;
        }
    }    
    return head;
}

// These helper functions are for the main below and will
// have no effect on your remove_disorder. They do not
// need to be modified.
struct node *make_list(int a, int b, int c);
void printList(struct node *head);

// This is a main function which could be used
// to test your remove_disorder function.
// It will not be marked.
// Only your remove_disorder function will be marked.
//
// It's recommended to change the int values in this
// main to test whether your remove_disorder is working.
int main(void) {
    // test an ordered list
    struct node *ordered = make_list(1, 2, 3);
    ordered = remove_disorder(ordered);
    printList(ordered);
    
    // test removing one element out of order
    ordered = make_list(1, 3, 2);
    ordered = remove_disorder(ordered);
    printList(ordered);
    
    // test a completely disordered list
    ordered = make_list(3, 2, 1);
    ordered = remove_disorder(ordered);
    printList(ordered);

    // test with the first removal causing more disorder
    ordered = make_list(2, 3, 1);
    ordered = remove_disorder(ordered);
    printList(ordered);
        
    return 0;
}

// A simple function to make a linked list with 3 elements
// This function is purely for the main above
// You will be tested with lists that are more and less
// than 3 elements long
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;
}

void printList(struct node *head) {
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}
// ADD ANY FUNCTION DEFINITIONS YOU WISH TO USE HERE