Download list_get_middle.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_middle/list_get_middle.c .

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

// Return middle element of a linked list
// if list contains [6,7,8,9,10]  8 is returned
// if a list has even number of elements, first of middle two elements returned
// if list contains [1,2,3,4] 2 is returned
// list can not be empty
int get_middle(struct node *head) {

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

}

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

Add code to get_middle so that its returns the middle value of the list. If the list an even number of elements the first of the 2 elements in the middle of the list should be returned.

For example if the linked list contains these 8 elements:

1, 7, 8, 9, 13, 19, 21, 42

get_middle should return 9 because 9 and 13 are the middle two elements

And, for example if the linked list contains these 5 elements:

1, 2, 8, 1, 42

get_middle should return 8 because it is the middle element.

get_middle can assume the list is not empty.

Testing

list_get_middle.c also contains a main function which allows you to test your get_middle function.

This main function:

1. converts the inputs to a linked list,
2. assigns a pointer to the first node in the linked list to head,
3. calls list_get_middle(head) and
4. prints the result.

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

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

Examples

dcc list_get_middle.c -o list_get_middle
./list_get_middle
How many numbers in initial list?: 9
1 2 4 8 16 32 64 128 256
16
./list_get_middle
How many numbers in initial list?: 6
2 4 6 5 8 9
6
./list_get_middle
How many numbers in initial list?: 5
13 15 17 19 18
17
./list_get_middle
How many numbers in initial list?: 2
42 4
42
./list_get_middle
How many numbers in initial list?: 1
42
42

Assumptions/Restrictions/Clarifications

• get_middle should return a single integer
• get_middle can assume the list has at least one element
• get_middle should not change the linked list it is given Your function should not change the next or data fields of list nodes
• get_middle should not use arrays
• get_middle should not call malloc
• get_middle should not call scanf (or getchar or fgets)
• get_middle should not print anything. It should not call printf
• Do not change the supplied main function. It will not be tested or marked

1091 style list_get_middle.c
    

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

1091 autotest list_get_middle

When you are finished working on this exercise, you must submit your work by running give:

give dp1091 lab12_list_get_middle list_get_middle.c
    

You must run give before Monday 18 November 09:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

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

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

Complete the program list_create.c. The program converts command line arguments into a linked list, prints out the linked list, and then frees the linked list. It is your job to complete the function that creates the linked list (arguments_to_list) and the function that frees the linked list (free_list).

Examples

dcc list_create.c -o list_create
./list_create 5 3 2 9 4 1
5 -> 3 -> 2 -> 9 -> 4 -> 1 -> X
./list_create I love this COMP1511 exercise!!
I -> love -> this -> COMP1511 -> exercise!! -> X
./list_create 8915 10563 10821 9979 14640 8433 6894 125
8915 -> 10563 -> 10821 -> 9979 -> 14640 -> 8433 -> 6894 -> 125 -> X
./list_create
X

Assumptions/Restrictions/Clarifications

• Any length of command line arguments can be given
• Do not change the supplied main function. Only your arguments_to_list and free_list function will be tested

1091 style list_create.c
    

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

1091 autotest list_create

When you are finished working on this exercise, you must submit your work by running give:

give dp1091 lab12_list_create list_create.c
    

You must run give before Monday 18 November 09:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

Download list_delete_contains_string.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_contains_string/list_delete_contains_string.c .

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

// Delete the first node in the list containing the specific string
// The deleted node is freed.
// If no node contains the specified string, the list is not changed
// The head of the list is returned.
struct node *delete_contains(char string[MAX_SIZE], struct node *head) {
    return NULL;
}

Note list_delete_contains_string.c uses the following familiar data type:

struct node {
    struct node *next;
    char        data[MAX_SIZE];
};

delete_contains is given two argument, value and head.

• data is a string with max size of 100 characters
• head is the pointer to the first node in a linked list

The function is designed to delete the first node in the linked list that contains a specific string.

Add code to delete_contains so that it deletes the first node in the linked list that whose data field equals a specified string and returns a pointer to the new list.

• If data does not occur in the linked list, the list should not be changed.

• If data occurs more than once in the linked list, only the first occurrence should be deleted. Note, if the list is now empty delete_contains should return NULL.

delete_contains should call free to free the memory of the node it deletes.

Testing

list_delete_contains.c also contains a main function which allows you to test your delete_contains function.

This main function:

1. takes in command line arguments
2. converts the command line inputs to a linked list,
3. assigns a pointer to the first node in the linked list to head,
4. reads a sstring from standard input and assigns it to data,
5. calls delete_contains(data, head) and
6. prints the result.

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

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

dcc list_delete_contains_string.c -o list_delete_contains_string
./list_delete_contains_string cats sleep 16 to 18 hours per day
Enter a string to delete: cats
[sleep, 16, to, 18, hours, per, day]
./list_delete_contains_string the bumblebee bat is the worlds smallest mammal
Enter a string to delete: bumblebee
[the, bat, is, the, worlds, smallest, mammal]
./list_delete_contains_string
Enter a string to delete: hello
[]
./list_delete_contains_string there are parts of Africa in all four hemispheres
Enter a string to delete: four
[there, are, parts, of, Africa, in, all, hemispheres]
./list_delete_contains_string the most money ever paid for a cow in an auction was 1.3 million dollars
Enter a string to delete: dollars
[the, most, money, ever, paid, for, a, cow, in, an, auction, was, 1.3, million]

Assumptions/Restrictions/Clarifications

• delete_contains should call free to free the memory for the node it deletes
• delete_contains should not change the data fields of list nodes.
• delete_contains should not use arrays.
• delete_contains should not call malloc.
• delete_contains should not call scanf (or getchar or fgets).
• delete_contains should not print anything. It should not call printf.
• Do not change the supplied main function. It will not be tested or marked.

1091 style list_delete_contains_string.c
    

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

1091 autotest list_delete_contains_string

When you are finished working on this exercise, you must submit your work by running give:

give dp1091 lab12_list_delete_contains_string list_delete_contains_string.c
    

You must run give before Monday 18 November 09:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

Download list_delete_highest.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_highest/list_delete_highest.c .

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

//
// Delete the node(s) in the list that contain the highest value
// The deleted node(s) are freed.
// The head of the list is returned.
//
struct node *delete_highest(struct node *head) {

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

}

Note list_delete_highest.c uses the following familiar data type:

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

delete_highest is given one argument, head

• head is the pointer to the first node in a linked list

Add code to delete_highest so that it deletes the all nodes in the linked list whose data field are equal to the highest data value in the list

delete_highest should return a pointer to the new list

If the list is now empty delete_highest should return NULL

delete_highest should call free to free the memory of any node it deletes

For example if the linked list contains these 8 elements:

16, 7, 8, 19, 13, 19, 2, 12

delete_highest should return a pointer to a list with these elements:

16, 7, 8, 13, 2, 12

Testing

list_delete_highest.c also contains a main function which allows you to test your delete_highest function

This main function:

1. converts the inputs to a linked list,
2. assigns a pointer to the first node in the linked list to head,
3. calls delete_highest(head) and
4. prints the result.

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

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

Examples

dcc list_delete_highest.c -o list_delete_highest
./list_delete_highest
Total numbers in list: 8
16 7 8 19 13 19 2 12
[16, 7, 8, 13, 2, 12]
./list_delete_highest
Total numbers in list: 5
200 150 27 200 200
[150, 27]
./list_delete_highest
Total numbers in list: 5
4 6 2 4 6
[4, 2, 4]
./list_delete_highest
Total numbers in list: 1
42
[]
./list_delete_highest
Total numbers in list: 0
[]

Assumptions/Restrictions/Clarifications

• delete_highest should call free to free the memory for any nodes it deletes
• delete_highest should not change the data fields of list nodes
• delete_highest should not use arrays
• delete_highest should not call malloc
• delete_highest should not call scanf (or getchar or fgets)
• delete_highest should not print anything. It should not call printf

Do not change the supplied main function. It will not be tested or marked.

1091 style list_delete_highest.c
    

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

1091 autotest list_delete_highest

When you are finished working on this exercise, you must submit your work by running give:

give dp1091 lab12_list_delete_highest list_delete_highest.c
    

You must run give before Monday 18 November 09:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

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

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

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

// Make music for a certain number of turns.
// Each turn of music makes the players move
// one chair along the list.
// After they've moved that many times, the
// first chair in the list is removed, along
// with the person sitting in it.
struct chair *make_music(int turns, struct chair *chairs) {
    // IMPLEMENT THIS FUNCTION
    return chairs;
}

Welcome to the Game of Chairs, where you either win or have your memory freed.

musical_chairs is written using the following structs that cannot be changed:

// player in the game of chairs
struct player {
    char name[MAX_NAME_LENGTH];
};

// A node in a linked list of chairs
struct chair {
    struct player *sitting;
    struct chair *next;
};

The chair struct is a linked list node.

The player struct represents a player that can sit on a chair (represented by the chair's pointer aiming at the player).

make_music is given a pointer to a chair, which is the first element in a list of chairs. It is also given an int turns which represents how many turns of movement there will be before the music stops.

Like the game of Musical Chairs, this program will have players move along the linked list, changing which chair they're sitting in.

In make_music, every player moves turns spaces along the linked list. Anyone who moves off the end of the linked list, should then move to the head of the list, so the players will end up rotating through the list as if it's a loop. This would be similar to if the next of the last chair was aimed at the first chair.

Once all the players have finished moving, the head of the list of chairs is removed. This means both that chair and the player sitting in it are removed from the game. make_music should then print out the name of the player that was removed.

Be careful to make sure you free all memory used in this game!

For example if a list of chairs called thrones looks like this:

throne points at the player named "Spoiler Alert"
throne points at the player named "Eddard Stark"
throne points at the player named "Joffrey Baratheon"
throne points at the player named "Cersei Lannister"
throne points at the player named "Robert Baratheon"

Then the following function is called:

make_music(3, thrones);

The output would be:

Joffrey Baratheon

and the resulting linked list would look like this:

(throne pointed at "Joffrey Baratheon" but was removed)
throne points at the player named "Cersei Lannister"
throne points at the player named "Robert Baratheon"
throne points at the player named "Spoiler Alert"
throne points at the player named "Eddard Stark"

In this list, all the players have moved down 3 chairs and are now sitting in different chairs. Anyone that moved past the end of the chairs was moved back to the top of the list of chairs.

Assumptions/Restrictions/Clarifications

• You can assume the list provided to make_music will not be empty.
• You can assume the number of turns will not be negative.
• struct player and struct chair cannot be edited. They must be used as they are.
• The be_seated function will help you create chairs. It cannot be edited and must be used as it is. You may not use arrays in this solution. Arrays are not necessary to complete this task.
• You must free all memory used in your program. Use dcc --leak-check if you need to check for memory leaks. Autotest will also check your code for leaks
• Your submitted file may contain a main function. It will not be tested or marked.

1091 style musical_chairs.c
    

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

1091 autotest musical_chairs

When you are finished working on this exercise, you must submit your work by running give:

give dp1091 lab12_musical_chairs musical_chairs.c
    

You must run give before Monday 18 November 09:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

Copy the program debug_remove_second_last.c from the course account to your directory by typing (make sure you type the dot at the end):

cp ~dp1091/public_html/24T3/activities/debug_remove_second_last/debug_remove_second_last.c .

Note that this exercise is not marked or worth marks!

Debugging Tips!

Some debugging tips for you:

• dcc output - as you run into issues, dcc will point you to where the errors are. Remember that dcc gives you the line number the issue is on, and will give some sort of explanation. Make sure you read everything dcc gives you. Sometimes we get “errors carried forward”, so find your first error, fix that, then recompile.
• print statements - sometimes it can be handy to see if the flow of your code puts you in the spot you expect it to be (ie. inside the right if statement, or going through a loop the correct amount of times). A quick way you can check this is by putting print statements in your code for testing purposes, like "the value of x is %d and y is %d". This lets you check that you got against what you expected.
• DPST1091 debugging guide - https://cgi.cse.unsw.edu.au/~dp1091/24T3/resources/debugging_guide.html

The Task

This task takes in a linked list via command line arguments. Then, it attempt to remove the second last element of the list previously created via the delete_second_last.

For example if the existing list is 1 -> 2 -> 3 -> 4-> X, after calling the delete_second_last function on the list the list is as follows: 1 -> 2 -> 4 -> X. Note, the node containing the value 3 is removed from the list since it is the second last element in the list.

Currently it has some issues it is your job to figure them out and fix the code. Note, you should only need to modify the delete_second_last function to fix the program.

Examples

dcc debug_remove_second_last.c -o debug_remove_second_last
./debug_remove_second_last 1 2 3 4 5 6
Original list: [1, 2, 3, 4, 5, 6]
Modified list: [1, 2, 3, 4, 6]
./debug_remove_second_last 1 2 3
Original list: [1, 2, 3]
Modified list: [1, 3]
./debug_remove_second_last 1 2
Original list: [1, 2]
Modified list: [2]
./debug_remove_second_last 1
Original list: [1]
Modified list: []
./debug_remove_second_last 
Original list: []
Modified list: []

Assumptions/Restrictions/Clarifications

• You may assume all command line arguments will be integers

1091 style debug_remove_second_last.c
    

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

1091 autotest debug_remove_second_last