DPST1091 Revision Linked Lists Exercises

Download most_frequent_list.c here, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/24T3/activities/most_frequent_list/most_frequent_list.c .

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;

}

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

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

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:

cp -n /import/reed/A/dp1091/public_html/24T3/activities/most_frequent_list/most_frequent_list.c .
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 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:

1091 autotest most_frequent_list

Download list_product.c here, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/24T3/activities/list_product/list_product.c .

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;

}

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

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

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

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

1091 autotest list_product

Download list_count_matches.c here, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/24T3/activities/list_count_matches/list_count_matches.c .

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;

}

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

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

}

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

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

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.

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:

1091 autotest list_count_matches

Download list_is_set.c here, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/24T3/activities/list_is_set/list_is_set.c .

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;

}

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

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

Testing

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

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

cp -n /import/reed/A/dp1091/public_html/24T3/activities/list_is_set/list_is_set.c .
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.

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:

1091 autotest list_is_set

Download list_intersection_size.c here, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/24T3/activities/list_intersection_size/list_intersection_size.c .

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;

}

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

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

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:

cp -n /import/reed/A/dp1091/public_html/24T3/activities/list_intersection_size/list_intersection_size.c .
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.

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:

1091 autotest list_intersection_size

Download list_ordered_insert.c here, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/24T3/activities/list_ordered_insert/list_ordered_insert.c .

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

// ordered_insert should create a new node with the specified value,
// and add it to the list such that the list remains in ascending order.
//
// ordered_insert should return the head of the list.
struct node *ordered_insert(struct node *head, int value) {

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

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

ordered_insert is given two parameters: a list that is sorted in ascending order (smallest to largest), and a value to insert into the list. ordered_insert should create a new node that contains this value and insert it into the list, such that it remains in ascending order.

ordered_insert should return the head of the list.

Examples

For example, if the list was

1 -> 3 -> 4 -> 5 -> X

ordered_insert should return a pointer to the first node in the list, as this is still the head of the list (the head was not changed).

The list should then look like:

1 -> 2 -> 3 -> 4 -> 5 -> X

X

ordered_insert should return a pointer to the new node that was created, as it is now the head of the list.

The list should then look like:

10 -> X

Testing

list_ordered_insert.c also contains a main function which allows you to test your ordered_insert function.

This main function:

• takes the first command line argument as the value to insert
• converts the remaining command line arguments to a linked list
• assigns a pointer to the first node in the linked list to head
• calls ordered_insert(head)
• prints the result.

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

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

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

dcc list_ordered_insert.c -o list_ordered_insert
./list_ordered_insert 3   4 5
The new list is: [3, 4, 5]
./list_ordered_insert 5   1 3 7 9
The new list is: [1, 3, 5, 7, 9]
./list_ordered_insert 1
The new list is: [1]

Assumptions/Restrictions/Clarifications

You can assume that the provided list is already in order.

You can assume the provided list does not already contain the value you need to insert.

You can assume that the list will only contain positive integers.

You cannot assume anything about number of nodes in the list: there could be no nodes, or there could be very many nodes in the list.

Your submitted file must contain the function: ordered_insert. You may create additional helper functions if you wish.

ordered_insert should return a pointer to the head of the new list.

ordered_insert should not use arrays.

ordered_insert will need to call malloc.

ordered_insert should not call scanf (or getchar or fgets).

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

1091 autotest list_ordered_insert

Download list_delete_last.c here, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/24T3/activities/list_delete_last/list_delete_last.c .

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

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

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

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

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

delete_last should return a pointer to the new list.

If the list is now empty delete_last should return NULL.

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

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

Testing

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_last(head)
• prints the result.

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

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

cp -n /import/reed/A/dp1091/public_html/24T3/activities/list_delete_last/list_delete_last.c .
dcc list_delete_last.c -o list_delete_last
./list_delete_last 16 7 8 12 13 19 21 12
[16, 7, 8, 12, 13, 19, 21]
./list_delete_last 2 4 6 2 4 6
[2, 4, 6, 2, 4]
./list_delete_last 42
[]
./list_delete_last
[]

Assumptions/Restrictions/Clarifications.

delete_first should not change the data fields of list nodes.

delete_last should not use arrays.

delete_last should not call malloc.

delete_last should not call scanf (or getchar or fgets).

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

1091 autotest list_delete_last

Download list_delete_second_last.c here, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/24T3/activities/list_delete_second_last/list_delete_second_last.c .

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:

1091 autotest list_delete_second_last

Download list_count_last.c here, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/24T3/activities/list_count_last/list_count_last.c .

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;

}

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

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

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

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

cp -n /import/reed/A/dp1091/public_html/24T3/activities/list_count_last/list_count_last.c .
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:

1091 autotest list_count_last

Download list_delete_range.c here, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/24T3/activities/list_delete_range/list_delete_range.c .

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

//
// Given the head of a linked list, deletes all nodes in range `start` to `end`.
// Nodes can be identified by an "index", of which the first node has index 0.
//
// Returns the head of the list afterwards.
//
struct node *delete_range(struct node *head, int start, int end) {
    // TODO: COMPLETE THIS FUNCTION AND CHANGE THIS RETURN
    return NULL;
}

In this exercise, every node in the linked list provided can be thought of as having a "place" in the list. For example, the first node will be at place "1", the second at place "2" and so on. You will be given both a start/end position in which all nodes inbetween (inclusive) are to be deleted.

Examples

dcc list_delete_range.c -o list_delete_range
./list_delete_range
Total numbers: 6
6 5 4 3 2 1
Enter delete range: 2 4
List before: [6, 5, 4, 3, 2, 1]
List after: [6, 5, 1]
./list_delete_range
Total numbers: 10
5 1 10 -1 3 6 -5 3 40 1
Enter delete range: 3 8
List before: [5, 1, 10, -1, 3, 6, -5, 3, 40, 1]
List after: [5, 1, 10, 1]
./list_delete_range
Total numbers: 5
1 2 3 4 5
Enter delete range: 0 2
List before: [1, 2, 3, 4, 5]
List after: [4, 5]
./list_delete_range
Total numbers: 5
1 2 3 4 5
Enter delete range: 0 10
List before: [1, 2, 3, 4, 5]
List after: []

Assumptions/Restrictions/Clarifications

• You will always be given integer inputs
• When considering the each node in the range, their positioning starts at 0
• The range components will always be given such that start < end
• All range components will be non-negative
• The "end" given can be larger than the length of the list
• The entire delete range can be outside of the list. E.g. if a list has 3 nodes, the delete range can still be 10 to 15.

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

1091 autotest list_delete_range

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!

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.

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

1091 autotest list_join_detection

Download list_directions.c here, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/24T3/activities/list_directions/list_directions.c .

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

// Given the `head` of a list, prints the string it contains as well as the
// numbers of lefts/rights taken.
void print_list(struct node *head) {
    // TODO: COMPLETE THIS FUNCTION
}

For this exercise, our linked list is setup in a more unique way. Instead of simply having a next pointer, we have a left and right pointer where the list can traverse in either direction. The struct is defined as below:

struct node {
    struct node *left;
    struct node *right;
    char         data;
};

Every node that exists in the linked list has a pointer to the next node through either their left or right pointers. There is only one path through the list, notably, for any node, at least one of the pointers will be NULL, whereas the other pointer will point at the next node.

The program will be provided with the list by specifying both the data to put in the current node as well as the direction to be taken to the next node. Some example input is provided below:

dcc list_directions.c -o list_directions
./list_directions
Enter list: M L y R W L o L r R d L .

List string:   MyWord.
#Lefts Taken:  4
#Rights Taken: 2

In this example, we specify the data of the current node then which direction we want to head in (either 'L' for left or 'R' for right). We can visualise this list with the diagram below.

Creating this list is taken care of in the provided file. Your job is to output the data of the list as a string and identify how many lefts/rights were taken to traverse the list.

Examples

dcc list_directions.c -o list_directions
./list_directions
Enter list: L L o R n L g R e L r R P R a L t R h L W R i L t R h R T R w L i R s R t R s R A R n L d R T R u L r L n R s

List string:   LongerPathWithTwistsAndTurns
#Lefts Taken:  10
#Rights Taken: 17
./list_directions
Enter list: a L b L c L d L e L f L g L h L i L j L k L l L m L n L o L p L q L r L s L t L u L v L w L x L y L z

List string: abcdefghijklmnopqrstuvwxyz
#Lefts Taken:  25
#Rights Taken: 0

Assumptions/Restrictions/Clarifications

• You will always be given letters as character data for each node
• Each node can only point to 1 other node. That is, either the left/right must be NULL
• Try to separate the problem into two conditions. What do you need to do to traverse left, what do you need to do to traverse right?

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

1091 autotest list_directions

Download list_insert_after_lowest.c here, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/24T3/activities/list_insert_after_lowest/list_insert_after_lowest.c .

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

struct node *insert_after_lowest(struct node *head, int data) {

    // TODO: Insert a new node with the value, 'data' 
    // after the node with the lowest data.

    return NULL;
}

Given a linked list, your task is to insert a new node, with a specific value, after the node with the lowest values in the linked list.

insert_after_lowest is given a pointer to a linked list and the data values that is to be added.

insert_after_lowest should return a pointer to the linked list

This program uses the familiar data type below

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

Only this specific function will be called in marking, the main function is only provided for your testing, however you can create more functions if it is helpful.

insert_after_lowest should find the lowest value in the linked list, and insert a new node directly after it.

For example, if the linked list had the values

Head => [4, 2, 6]

Head => [4, 2, 99, 6]

The below shows the output when the program is run with the example given in the starter code main function.

dcc list_insert_after_lowest.c -o insert_after_lowest
./insert_after_lowest
4 -> 2 -> 6 -> X
4 -> 2 -> 99 -> 6 -> X

Assumptions/Restrictions/Clarifications

• insert_after_lowest should still insert the new node if the list is empty.
• insert_after_lowest should only ever insert ONE node after the first instance of the lowest value, even if there are multiple nodes with the same lowest value.

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

1091 autotest list_insert_after_lowest

Download insert_alternating.c here, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/24T3/activities/list_insert_alternating/insert_alternating.c .

Your task is to write a program which will read values until EOF, and insert these values into a linked list in an alternating order.

Specifically, your program should read integers from the terminal, until EOF, and insert the first value to the head of the list, then the second value is to the tail of the list, then the third value is added to the head of the list etc.

A minimal starter program is given to you, this program should use the familiar data type

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

You may also find the given create_node function helpful in you implementation.

Your program should use the provided print_list function to print the list after EOF is received.

For example, if your program was given the following inputs

1 2 3 4 5

Head => [5, 3, 1, 2, 4]

This is because;

• 1 was added to the head of an empty list
• 2 was added to the tail of the list
• 3 was added to the head of the list
• 4 was added to the tail of the list
• 5 was added to the head of the list

Examples

dcc insert_alternating.c -o insert_alternating
./insert_alternating
1
2
3
4
5

5 -> 3 -> 1 -> 2 -> 4 -> X
./insert_alternating
1
1
1
2
2
3
3

3 -> 2 -> 1 -> 1 -> 1 -> 2 -> 3 -> X
./insert_alternating

X

Your program should be able to accept an unlimited number of values

Your program should print an empty list if no values were inputted

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

1091 autotest list_insert_alternating

Download adjacent_distances.c here, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/24T3/activities/adjacent_distances/adjacent_distances.c .

Your task is to print the Euclidean distance between adjacent coordinates in an array of coordinates.

Specifically, given a 1D array of structs, where each struct contains an x and y coordinate, you need to calculate and print the distance between coordinates stored next to each other in the array.

This program uses the following struct to store coordinates

struct coordinate {
    int x;
    int y;
};

Coordinates are stored in an array of struct coordinates, always of size 5. This can be seen in the starter program. Note; Some example values are given to the array of structs for your testing

struct coordinate array1[SIZE];

For this array of size 5, you must calculate and print the Euclidean distance between coordinates in

• Index 0 & Index 1
• Index 1 & Index 2
• Index 2 & Index 3
• Index 3 & Index 4

The euclidean distance can be calculated using the provided e_dist function in the starter code. This function takes in two struct coordinate and returns the distance between them as a double.

You must implement the function given to you, the function will be called directly in marking and the main function will be ignored. You may create extra function if you find that helpful.

For example, the output of the test input given in the main function, would be

dcc adjacent_distances.c -o adjacent_distances
./adjacent_distances
Dist: 1.414214
Dist: 7.000000
Dist: 9.899495
Dist: 9.219544

Your program must produce this output exactly

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

1091 autotest adjacent_distances

Download list_delete_negatives.c here, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/24T3/activities/list_delete_negatives/list_delete_negatives.c .

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

struct node *delete_negatives(struct node *head) {

    // TODO: Delete any nodes in the linked list 
    // with a data value < 0

    return NULL;
}

Given a linked list, your task is to delete any nodes which have a value strictly less than 0. Any nodes which are deleted must be properly free'd.

This program uses the familiar data type below

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

list_delete_negatives is given a pointer to a linked list.

list_delete_negatives should return a pointer to the head of the linked list.

Only this specific function will be called in marking, the main function is only provided for your testing, however you can create more functions if it is helpful.

Your function should operate normally with an empty linked list.

Your function should not change the list if there are no negative numbers within the list.

You function should not call malloc.

Your function should not have any memory leaks and should pass a leak-check.

For example, if the linked list had the values

Head => [3, 4, -5, 10, -10]

Head => [3, 4, 10]

Additionally, if the linked list had the values

Head => [-2, -2, 6]

Head => [6]

Examples

dcc list_delete_negatives.c -o list_delete_negatives
./list_delete_negatives
4 -> -2 -> 6 -> X
4 -> 6 -> X

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

1091 autotest list_delete_negatives

Download list_delete_duplicates.c here, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/24T3/activities/list_delete_duplicates/list_delete_duplicates.c .

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

struct node *delete_duplicates(struct node *head) {

    // TODO: delete any adjacent duplicate values

    return NULL;
}

Given a linked list, delete any values which are adjacent duplicates in the linked list.

This program uses the familiar data type below

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

delete_duplicates is given a pointer to a linked list.

delete_duplicates should return a pointer to the head of the linked list.

delete_duplicates should only remove duplicate values which are next to each other in the list (adjacent).

delete_duplicates can delete more than 1 successive duplicate value.

delete_duplicates should remove all but the first instance of the value in a set of duplicates, such that the value only appears once in that part of the list.

The same value can appear multiple times in the linked list, provided they are not adjacent.

delete_duplicates can remove the same value multiple times in the list.

See the examples for more details

Example 1

For example, if the linked list had the values

Head => [2, 3, 3, 5, 6]

Head => [2, 3, 5, 6]

Example 2

For example, if the linked list had the values

Head => [10, 11, 11, 11, 11, 12]

Head => [10, 11, 12]

Example 3

For example, if the linked list had the values

Head => [10, 11, 11, 25, 11, 11]

Head => [10, 11, 25, 11]

Only this specific function will be called in marking, the main function is only provided for your testing, however you can create more functions if it is helpful.

Your function should operate normally with an empty linked list.

Your function should not change the list if there are no duplicate numbers within the list.

You function should not call malloc.

Your function should not have any memory leaks and should pass a leak-check.

Examples

dcc list_delete_duplicates.c -o list_delete_duplicates
./list_delete_duplicates
2 -> 4 -> 4 -> 6 -> X
2 -> 4 -> 6 -> X

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

1091 autotest list_delete_duplicates

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

Download list_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_sum/list_sum.c .

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:

1091 autotest list_sum

Download list_count_favourite.c here, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/24T3/activities/list_count_favourite/list_count_favourite.c .

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:

1091 autotest list_count_favourite

Download list_get_nth.c here, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/24T3/activities/list_get_nth/list_get_nth.c .

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:

1091 autotest list_get_nth