Week 09 Extra Exercises

• This page contains extra 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 are available for them (Command included at bottom of each exercise).

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

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

1091 autotest sudoku

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