Programming Fundamentals

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

Download list_count_even.c here

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

1511 fetch-activity list_count_even

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

// return the number of even values in a linked list
int count_even(struct node *head) {

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

}

Note list_count_even.c uses the following familiar data type:

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

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

Add code to count_even so that its returns the number of even values in the linked list.

For example if the linked list contains these 8 elements:

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

count_even should return 4, because these 4 elements are even:

16, 8, 12, 12

Testing

list_count_even.c also contains a main function which allows you to test your count_even 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 count_even(head).
• prints the result.

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

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

Examples

Here is how you use main function to test count_even:

dcc list_count_even.c -o list_count_even
./list_count_even 16 7 8 12 13 19 21 12
4
./list_count_even 2 4 6 2 4 6
6
./list_count_even 3 5 7 11 13 15 17 19 23 29
0
./list_count_even 2 4 8 16 32 64 128 256
8
./list_count_even
0

Assumptions/Restrictions/Clarifications

• An even number is divisible by 2.

• count_even should return a single integer.

• count_even should not change the linked list it is given.

• Your function should not change the next or data fields of list nodes.

• count_even should not use arrays.

• count_even should not call malloc.

• count_even should not call scanf (or getchar or fgets).

• You can assume the linked list only contains positive integers.

• count_even 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_even

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_clist_count_favouriteount_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_count_matches.c here

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

1511 fetch-activity list_count_matches

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

// Return the number of matches in the two lists, i.e. the number of
// values which occur at the same position in both linked lists.
int count_matches(struct node *head1, struct node *head2) {

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

}

Note list_count_matches.c uses the following familiar data type:

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

Your task is to add code to this function count_matches.

count_matches is given two arguments, head1 and head2, which are pointers to the first node of linked lists.

Add code to count_matches so that returns a count of how many places the two lists have the same value in the same position.

For example, if the two lists contain these values:

1, 4, 1, 5, 9, 2, 1, 8
1, 1, 8, 2, 9, 5

count_matches should return 2 because both lists have the same value (1) at position 0 and the same value (9) at position 4.

Note: the lists may be any length and the two lengths may be unequal.

Testing

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

This main function:

• uses a command line argument of "-" to separate the values for two linked lists.
• converts the command-line arguments before the "-" to a linked list.
• assigns a pointer to the first node in the linked list to head1.
• converts the command-line arguments after the "-" to a linked list.
• assigns a pointer to the first node in the linked list tohead2.
• calls count_matches(head1, head2).
• prints the result.

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

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

Examples

Here is how the main function allows you to test count_matches:

dcc -o list_count_matches list_count_matches.c
./list_count_matches 3 1 4 - 2 7 1 8 3
0
./list_count_matches 1 2 3 4 - 2 1 3 8
1
./list_count_matches 5 5 6 5 - 6 5 5 5
2
./list_count_matches 3 5 7 - 3 5 19 7 23 29
2
./list_count_matches 1 2 3 4 5 6 - 3 2 1
1
./list_count_matches - 1 2 3 4
0
./list_count_matches 4 3 2 1 -
0
./list_count_matches -
0

Assumptions/Restrictions/Clarifications

• count_matches should return a single integer.

• The linked lists may be of unequal lengths.

• The linked lists may be any length.

• Either or both linked lists may be empty (contain no elements).

• count_matches should not change the linked lists it is given.

• Your function should not change the next or data fields of list nodes.

• count_matches should not use arrays.

• count_matches should not call malloc.

• count_matches should not call scanf (or getchar or fgets).

• count_matches 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_matches

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_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_count_last.c here

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

1511 fetch-activity list_count_last

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

// return the number of values in a linked list equal to the
// last value in that linked list.
int count_last(struct node *head) {

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

}

Note list_count_last.c uses the following familiar data type:

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

count_last is given one argument, head, which is the pointer to the first node in a linked list. You are guaranteed the list will not be empty.

Add code to count_last so that its returns the number of values which are the same as the last value in the list.

For example if the linked list contains these 8 values:

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

count_last should return 3, because 12 is the last value, and 12 occurs 3 times in the list (including the last number).

Testing

list_count_last.c also contains a main function which allows you to test your count_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 count_last(head).
• prints the result.

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

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

Examples

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

dcc list_count_last.c -o list_count_last
./list_count_last 16 12 8 12 13 19 21 12
3
./list_count_last 2 4 6 2 4 6
2
./list_count_last 3 5 7 11 13 15 17 19 23 29
1
./list_count_last 2 2 2 3 2
4

Assumptions/Restrictions/Clarifications.

• count_last will never receive a linked list with no nodes. That is, the head will never be NULL
• count_last should return a single integer.
• count_last should not change the linked list it is given.
• Your function should not change the next or data fields of list nodes.
• count_last should not use arrays.
• count_last should not call malloc.
• count_last should not call scanf (or getchar or fgets).
• count_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_count_last

Download list_intersection_size.c here

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

1511 fetch-activity list_intersection_size

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

// return the number of values which occur in both linked lists
// no value is repeated in either list
int intersection_size(struct node *head1, struct node *head2) {

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

}

Note list_intersection_size.c uses the following familiar data type:

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

intersection_size is given two arguments, head1 and head2, which are pointers to the first node of linked lists.

Add code to intersection_size so that its returns the number of values that occur in both linked list.

Assume no value occurs more than once in either linked list.

For example, if the two lists contain these values:

3, 1, 4
2, 7, 1, 8, 3

intersection_size should return 2, because these 2 elements occur in both lists:

1, 3

Testing

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

This main function:

• uses a command line argument of "-" to separate the values for two linked lists.
• converts the command-line arguments before the "-" to a linked list.
• assigns a pointer to the first node in the linked list to head1.
• converts the command-line arguments after the "-" to a linked list.
• assigns a pointer to the first node in the linked list to head2.
• calls intersection_size(head1, head2).
• prints the result.

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

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

Here is how the main function allows you to test intersection_size:

dcc list_intersection_size.c -o list_intersection_size
./list_intersection_size 3 1 4 - 2 7 1 8 3
2
./list_intersection_size 16 7 8 12 - 13 19 21 12
1
./list_intersection_size 2 4 6 - 2 4 6
3
./list_intersection_size 3 5 7 11 13 - 15 17 19 23 29
0
./list_intersection_size 1 2 3 4 - 3 2 1
3
./list_intersection_size - 1 2 3 4
0
./list_intersection_size 4 3 2 1 -
0
./list_intersection_size -
0

Assumptions/Restrictions/Clarifications.

• intersection_size should return a single integer.
• No value will occur more than once in either linked list.
• intersection_size should not change the linked lists it is given.
• Your function should not change the next or data fields of list nodes.
• intersection_size should not use arrays.
• intersection_size should not call malloc.
• intersection_size should not call scanf (or getchar or fgets).
• intersection_size 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_intersection_size

Download list_is_set.c here

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

1511 fetch-activity list_is_set

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

// return 1 if the list is a set
int is_set(struct node *head) {

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

}

Note list_is_set.c uses the following familiar data type:

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

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

Add code to is_set so that its returns 1 if the list is a set, and 0 otherwise.

A 'set' is defined as a list that does not repeat an element.

For example if the linked list contains these 8 elements:

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

is_set should return 0, because the element 12 occurs twice.

For example if the linked list contains these 4 elements:

16, 8, 12, 13

is_set should return 1, because none of the elements occur more than once.

Testing

list_is_set.c also contains a main function which allows you to test your is_set 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 is_set(head).
• prints the result.

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

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

Examples

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

dcc list_is_set.c -o list_is_set
./list_is_set 16 7 8 12 13 19 21 12
4
./list_is_set 2 4 6 2 4 6
6
./list_is_set 3 5 7 11 13 15 17 19 23 29
0
./list_is_set 2 4 8 16 32 64 128 256
8
./list_is_set
0

Assumptions/Restrictions/Clarifications.

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

Download list_product.c here

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

1511 fetch-activity list_product

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

// product should return the sum of the elements in list1 multiplied by 
// the corresponding element in list2
// if one list is longer than the other, the extra list elements are ignored 
int product(struct node *head1, struct node *head2) {

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

}

Note list_product.c uses the following familiar data type:

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

product is given two arguments, head1 and head2, which are pointers to the first node of linked lists.

product should return the sum of the elements in the first list multiplied by the corresponding element in the second list.

If one list is longer than the other, the extra elements should be ignored.

For example, if the two lists contain these values:

list1: 3, 1, 4, 1, 5, 9

list2: 2, 7, 9

product should return 49, because 3 * 2 + 1 * 7 + 4 * 9 = 49 .

For example, if the two lists contain these values:

list1: 2, 7

list2: 4, 42, 4242, 4242, 4242424242

product should return 302, because 2 * 4 + 7 * 42 = 302.

Testing

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

This main function:

• uses a command line argument of "-" to separate the values for two linked lists.
• converts the command-line arguments before the "-" to a linked list
• assigns a pointer to the first node in the linked list to head1
• converts the command-line arguments after the "-" to a linked list
• assigns a pointer to the first node in the linked list to head2
• calls product(head1, head2)
• prints the result.

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

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

Examples

Here is how the main function allows you to test product:

dcc list_product.c -o list_product
./list_product 3 1 4 1 5 9 - 2 7 9 8
57
./list_product 16 7 8 12 - 13 19 21 12
653
./list_product 2 4 6 - 42
84
./list_product - 1 2 3 4
0
./list_product 4 3 2 1 -
0
./list_product -
0

Assumptions/Restrictions/Clarifications.

• The lists may be different lengths.
• The data fields of the lists may contain any integer.
• product should return only a single integer.
• product should not change the linked lists it is given.
• product should not change the next or data fields of list nodes.
• product should not use arrays.
• product should not call malloc.
• product should not call scanf (or getchar or fgets).
• product should not print anything. It should not call printf.

Do not change the definition of struct node.

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_product

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

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

1511 fetch-activity most_frequent_list

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

// return the value which occurs most frequently in a linked list
// if several values are equally most frequent
// the value that occurs earliest in the list is returned
int most_frequent(struct node *head) {

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

}

Note most_frequent_list.c uses the following familiar data type:

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

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

Add code to most_frequent so that its returns the most frequently occurring value in the linked list.

For example if the linked list contains these 8 elements:

655 10 204 8192 76 38 204 43912 204

most_frequent should return 204, because it is the most frequently occurring integer -- it appears 3 times.

For example if the linked list contains these 8 elements:

7 8 12 3 12 3 8

most_frequent should return 8.

There is a tie for most frequently occurring integer - 3, 8 and 12 all occur twice.

8 occurred first in the list so it should be returned.

You are not permitted to use arrays or malloc in your function.

Testing

most_frequent_list.c also contains a main function which allows you to test your most_frequent 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 most_frequent(head).
• prints the result.

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

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

Here is how you the main function allows you to test most_frequent:

dcc most_frequent_list.c -o most_frequent_list
./most_frequent_list 655 10 204 8192 76 38 204 43912 204
204
./most_frequent_list 5 4 6 5 4 6
5
./most_frequent_list 3 5 7 11 13 15 3 17 19 23 29 13 3
3

Assumptions/Restrictions/Clarifications.

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