Programming Fundamentals

• This page contains extra challenge exercises for week 08.
• These exercises are not compulsory, nor do they provide any marks in the course.
• These exercises are intended for students that want more challenge 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_array_sum.c here

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

1511 fetch-activity list_array_sum

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

//
// Print a linked list given the `head` of that list.
//
// Print occurs in the following format, depending on what nodes exist and
// the values in each array:
//
// #Elements: 3, Elements: [1, 2, 3]
// |
// v
// #Elements: 2, Elements: [1, 2]
// |
// v
// #Elements: 4, Elements: [1, 2, 3, 4]
// |
// v
// X
//
void print_list(struct node *head) {
    // TODO: Implement this function (replace the line below)
    printf("You need to implement the `print_list` function!");
}

//
// 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:

#define MAX_ELEMENTS 100

struct node {
    struct node *next;
    int          n_elements;
    int          data[MAX_ELEMENTS];
};

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:

1511 autotest list_array_sum

Download list_join_detection.c here

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

1511 fetch-activity list_join_detection

Your task is to add code to these functions 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;
}

In this exercise you will scan in values for two different lists and will be asked where to join the second list to the first list.

Here is an example:

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:

1511 autotest list_join_detection