Programming Fundamentals

• This page contains additional revision exercises for week 08.
• These exercises are not compulsory, nor do they provide any marks in the course.
• You cannot submit any of these exercises, however autotests are available for them (Command included at bottom of each exercise).

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

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

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

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

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

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

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

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

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

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