Week 08 Extra Exercises
Information
- This page contains extra 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).
Exercise
(●●◌)
:
List Array Sum
Download list_array_sum.c here, or copy it to your CSE account using the following command:
cp -n /import/reed/A/dp1091/public_html/24T3/activities/list_array_sum/list_array_sum.c .
Your task is to add code to this function in list_array_sum.c:
//
// Sum up all the array values in all nodes of a linked list provided by `head`.
//
// For example, if there are 3 nodes with arrays [1, 2, 3], [1, 2], [-3, 1]
// then this function should return 1 + 2 + 3 + 1 + 2 - 3 + 1 = 7
//
int total_list_sum(struct node *head) {
// TODO: Implement this function (replace the line below)
return 42;
}
In this exercise, you are provided a linked list with more complex data attached to each node:
INTERNAL ERROR MISSING FILE: "/import/reed/A/dp1091/public_html/24T3/public/activities/list_array_sum/struct_definition."
What this means is that every node in the linked list will contain a certain
number of integers, stored in an array data
. The number of actual integers
stored in the array is identified by n_elements
.
In this exercise, we have already provided you with the code to generate and populate the linked list.
Your job is to fill in the functions defined above. The print_list()
will
print out the linked list in a nice format and the total_list_sum()
will
find the total sum of the linked list by adding up each element in every
array of every node.
Examples
dcc list_array_sum.c -o list_array_sum ./list_array_sum How many array elements for this node? 2 Enter elements: 5 9 How many array elements for this node? 4 Enter elements: 1 4 7 10 How many array elements for this node? 1 Enter elements: 3 How many array elements for this node? Linked List: #Elements: 2, Elements: [5, 9] | v #Elements: 4, Elements: [1, 4, 7, 10] | v #Elements: 1, Elements: [3] | v X Sum: 39 ./list_array_sum How many array elements for this node? 5 Enter elements: -4 3 10 -4 0 How many array elements for this node? 2 Enter elements: 1 -1 How many array elements for this node? 10 Enter elements: -5 -4 -3 -2 -1 0 1 1 1 1 How many array elements for this node? 1 Enter elements: -3 How many array elements for this node? Linked list: #Elements: 5, Elements: [-4, 3, 10, -4, 0] | v #Elements: 2, Elements: [1, -1] | v #Elements: 10, Elements: [-5, -4, -3, -2, -1, 0, 1, 1, 1, 1] | v #Elements: 1, Elements: [-3] | v X Sum: -9 ./list_array_sum How many array elements for this node? 3 Enter elements: 0 0 0 How many array elements for this node? 2 Enter elements: 0 0 How many array elements for this node? 5 Enter elements: 0 0 0 0 0 How many array elements for this node? Linked list: #Elements: 3, Elements: [0, 0, 0] | v #Elements: 2, Elements: [0, 0] | v #Elements: 5, Elements: [0, 0, 0, 0, 0] | v X Sum: 0 ./list_array_sum How many array elements for this node? 0 Enter elements: How many array elements for this node? 3 Enter elements: 1 2 3 How many array elements for this node? 0 Enter elements: How many array elements for this node? 0 Enter elements: How many array elements for this node? 5 Enter elements: -1 4 -5 10 0 How many array elements for this node? Linked list: #Elements: 0, Elements: [] | v #Elements: 3, Elements: [1, 2, 3] | v #Elements: 0, Elements: [] | v #Elements: 0, Elements: [] | v #Elements: 5, Elements: [-1, 4, -5, 10, 0] | v X Sum: 14
Assumptions/Restrictions/Clarifications
- Only change the functions specified in the question
- You can assume that the length provided for all arrays are non-negative
- You can assume that the length provided for all the array will never exceed
100
- Think about how you can find the sum of an array in a single node, then try to do this for every node
When you think your program is working,
you can use autotest
to run some simple automated tests:
1091 autotest list_array_sum
Exercise
(●●●)
:
List Join Detection
Download list_join_detection.c here, or copy it to your CSE account using the following command:
cp -n /import/reed/A/dp1091/public_html/24T3/activities/list_join_detection/list_join_detection.c .
Your task is to add code to this function in list_join_detection.c:
//
// Gets the index relative to `second_list` where `first_list` and
// `second_list` join together.
//
// Returns this index if found, otherwise return -1
//
int join_detection_point(struct node *first_list, struct node *second_list) {
// TODO: Implement this function (And delete the line below)
return -1;
}
dcc list_join_detection.c -o list_join_detection ./list_join_detection Enter first list: 1 2 3 4 5 Enter second list: 6 7 8 9 Which node of list 1 will the end of list 2 point at? 2 These lists join at node 4 of the second list!In this example we have two lists `first_list` and `second_list`. However, the end of `second_list` is pointing into `first_list`. This is what we're interested in and is what we specify in the third line of input. When `2` was input, the end of the second list will point at node 2 of the first list (we are counting the first node as node 0). The last line of output is what your function will be implementing. That is, the first node in the second_list that also exists in the first_list. Please note that looking at the input should make it very obvious when this occurs as you know what the second list looks like. However, inside the function you will not have this luxury, as all the pointers have been setup for both lists. As a result, you are given the final versions of both lists and need to determine where they join. ### Examples
dcc list_join_detection.c -o list_join_detection ./list_join_detection Enter first list: 1 6 -10 4 3 50 20 6 Enter second list: 0 0 5 4 1 -10 3 4 6 9 10 3 6 20 Which node of list 1 will the end of list 2 point at? 5 These lists join at node 14 of the second list! ./list_join_detection Enter first list: 0 5 2 10 Enter second list: 1 3 Which node of list 1 will the end of list 2 point at? 7 These lists do not join at all.### Assumptions/Restrictions/Clarifications - You will always be provided valid input - Providing any index for `first_list` that does not exist means that `second_list` will never point into it - You should return `-1` if the two lists do not join - You cannot use the values of nodes to determine if they are in both lists. This because two nodes can have the same value. How could you check if both lists point at the same node at a certain point?
When you think your program is working,
you can use autotest
to run some simple automated tests:
1091 autotest list_join_detection