Programming Fundamentals

• This page contains additional revision exercises for week 10.
• These exercises are not compulsory, nor do they provide any marks in the course.
• You cannot submit any of these exercises, however autotests may be available for some them (Command included at bottom of each exercise if applicable).

Copy the file(s) for this exercise to your CSE account using the following command:

1511 fetch-revision 11

Follow the instructions in pokemon.c to create some struct pokemon. The level_up() function should be passed a pointer and should increase the level of the pokemon at that address.

No autotests are provided for this question.

Examples

dcc pokemon.c -o pokemon
./pokemon
charmander is level 5.
wartortle is level 16.
charmander is now level 6!
wartortle is now level 20!

Assumptions/Restrictions/Clarifications

• This program does not take in any input from the terminal

Copy the file(s) for this exercise to your CSE account using the following command:

1511 fetch-revision 11

Complete the function array_reverse in array_reverse.c which takes in an array and reverses the order of elements in that array. array_reverse does not return anything, so you will not be able to create a new array and return that. Instead, you will need to edit the values of the array you receive.

The input for this function is provided in the main function.

No autotests are provided for this question.

Examples

dcc array_reverse.c -o array_reverse
./array_reverse
6
5
4
3
2
1

Assumptions/Restrictions/Clarifications

• The given array should be edited directly.
• The function should not return anything.
• This program does not take in any input from the terminal

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

1511 autotest array_reverse

Copy the file(s) for this exercise to your CSE account using the following command:

1511 fetch-revision 11

Complete the function count_frequency in count_frequency.c, which takes in an array of ints and prints out how many times each number appears in the array.

The input for this function is provided in the main function.

No autotests are provided for this question.

Examples

dcc count_frequency.c -o count_frequency
./count_frequency
The number 5 came up 2 times.
The number 3 came up 2 times.
The number 8 came up 1 times.
The number 6 came up 1 times.

Assumptions/Restrictions/Clarifications

• The count for each number should only be printed once.
• This program does not take in any input from the terminal

Copy the file(s) for this exercise to your CSE account using the following command:

1511 fetch-revision 11

Complete the function combine_words() in words.c which takes in 2 linked lists of equal length, and combines the strings at the same position into a single string, and returns a new list of these combined strings. E.g. if the first string in the first list is "hello" and the first string in the second list is "world", the new list's first string should be "hello world"

The input for this function is provided in the main function.

No autotests are provided for this question.

Examples

dcc words.c -o words
./words
hello world
world hello
cheese pizza

Assumptions/Restrictions/Clarifications

• The combined string should be stored in the same position as the strings it was made from
• This program does not take in any input from the terminal

Copy the file(s) for this exercise to your CSE account using the following command:

1511 fetch-revision 11

Given a program words.c which takes in bubble tea orders and save them as a 2D linked list, your task is to complete the free_shop function to free all the malloc'd elements at the end of the bubble tea program. You can compile your program with --leak-check to check if all malloc'd memory has been freed.

These following commands have been implemented in the starter code:

• v prints out the bubble tea orders (base only)
• p places an order by appending a new order to the bubble tea list, in the format: [tea base] [sugar] [ice] [toppings] where toppings can continue to be scanned until 0 is input. Toppings should also be stored in a linked list
• d grabs the details of a specified position; its sugar, ice, and all toppings

If you want to implement the commands yourself for practice, feel free to start from scratch rather than using the starter code.

No autotests are provided for this question.

Examples

dcc words.c -o words
./words
Welcome to the Bubble Tea Shop!

What would you like to do?
v: view orders
p: place an order
d: get the details of an order

v
No orders!!!

What would you like to do?
v: view orders
p: place an order
d: get the details of an order

p 1 2 3 4 3 2 1 0

What would you like to do?
v: view orders
p: place an order
d: get the details of an order

v
1. Green Tea

What would you like to do?
v: view orders
p: place an order
d: get the details of an order

d 1
Sugar: 2
Ice: 3
The toppings in this bubble tea are:
Grass Jelly
Red Bean
Lychee Jelly
Pearls

What would you like to do?
v: view orders
p: place an order
d: get the details of an order

d 2
Invalid order number

What would you like to do?
v: view orders
p: place an order
d: get the details of an order



Thanks for visiting!

Assumptions/Restrictions/Clarifications

• All of the bubble tea shop functionality has been implemented for you. Your task is to complete the free_shop function
• When using the p command, toppings can be scanned in until 0 is input.

Copy the file(s) for this exercise to your CSE account using the following command:

1511 fetch-revision 11

Complete the program merge_lists.c which takes 2 lists with elements in ascending order, and combines those lists while preserving the ascending order.

The input for this function is provided in the main function.

No autotests are provided for this question.

Examples

dcc merge_lists.c -o merge_lists
./merge_lists
List 1:
0 -> 5 -> 40 -> X
List 2:
1 -> 3 -> 10 -> 100 -> X
Merged List:
0 -> 1 -> 3 -> 5 -> 10 -> 40 -> 100 -> X

Assumptions/Restrictions/Clarifications

• The 2 given lists are not necessarily the the same length.
• The elements of the new list should be in ascending order.
• This program does not take in any input from the terminal

Download list_reverse.c here

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

1511 fetch-activity list_reverse

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

//
// Place the list pointed to by head into reverse order.
// The head of the list is returned.
//
struct node *reverse(struct node *head) {

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

}

Note list_reverse.c uses the following familiar data type:

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

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

Add code to reverse which rearranges the list to be in reverse order.

reverse should return a pointer to the new list.

reverse must rearrange the list by changing the next fields of nodes.

reverse must not change the data fields of nodes.

For example if the linked list contains these 8 elements:

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

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

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

Testing

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

This main function:

• takes in the size of the linked list,
• converts the input numbers to a linked list,
• assigns a pointer to the first node in the linked list to head,
• calls reverse(head) and
• prints the result.

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

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

Examples

dcc list_reverse.c -o list_reverse
./list_reverse
How many numbers in list?: 8
16 7 8 12 13 19 21 12
[12, 21, 19, 13, 12, 8, 7, 16]
./list_reverse
How many numbers in list?: 6
2 4 6 2 4 6
[6, 4, 2, 6, 4, 2]
./list_reverse 42
How many numbers in list?: 1
42
[42]
./list_reverse
How many numbers in list?: 0
[]

Assumptions/Restrictions/Clarifications

• list_reverse should not change the data fields of list nodes
• list_reverse should not use arrays
• list_reverse should not call malloc
• list_reverse should not call scanf (or getchar or fgets)
• list_reverse 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:

1511 autotest list_reverse

Download filter_list.c here

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

1511 fetch-activity filter_list

Your task is to write a program to find the number of bags from people over a specified height.

More specifically, your program should do the following.

1. Scan in 5 pairs of height and number of bags, and store these pairs in an array of structs
2. Ask the user for a minimum height to filter by
3. Find the number of bags, from people who were greater than or equal to that height

This program has some starter code which includes the following struct.

struct passenger {
    double height;
    int num_bags;
};

The starter code also creates an array for you to store data in.

struct passenger my_array[SIZE];

Examples

dcc filter_list.c -o filter_list
./filter_list
Enter height & number of bags: 150.0 1
Enter height & number of bags: 160.0 2
Enter height & number of bags: 170.0 3
Enter height & number of bags: 180.0 1
Enter height & number of bags: 190.0 2
Select height: 170.0
Total of 6 bags from people over 170.000000
./filter_list
Enter height & number of bags: 150.0 1
Enter height & number of bags: 160.0 1
Enter height & number of bags: 170.0 1
Enter height & number of bags: 180.0 1
Enter height & number of bags: 190.0 1
Select height: 200.0
Total of 0 bags from people over 200.000000

Assumptions/Restrictions/Clarifications

• Your program should match the output shown above exactly.
• You can assume you will always be given the correct data type during input.
• You can assume a height is always a positive and non-zero number.
• You can assume the number of bags is non-negative.
• Your program should still work when a person has no baggage.

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

1511 autotest filter_list

Download find_totals.c here

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

1511 fetch-activity find_totals

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

int find_totals(int arr[SIZE][SIZE], int size) {

    // TODO: Find the number of rows with a 
    // sum equal to exactly 10

    return 0;
}

Given a 2d arrays of integers, your task is to find the number of rows where the sum of the integers equates to exactly 10.

You can assume the given array is always of size 5

You can assume the array always has the same number of rows and columns (The array is always square)

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

For example, if the following 2D array was given

The output should be exactly

dcc find_totals.c -o find_totals
./find_totals
2 rows had a sum of 10

This output is becasue rows 2 and 3 each have a sum of exactly 10.

Your function should work when there are arrays with no rows equal to 10.

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

1511 autotest find_totals

Download list_insert_after_lowest.c here

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

1511 fetch-activity list_insert_after_lowest

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]

And the function was asked to add the value 99, the list after modification would look as the following

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

1511 autotest list_insert_after_lowest

Download list_insert_alternating.c here

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

1511 fetch-activity list_insert_alternating

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

The resultant linked list should be as follows

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:

1511 autotest list_insert_alternating

Download adjacent_distances.c here

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

1511 fetch-activity adjacent_distances

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

void adjacent_distances(struct coordinate arr[SIZE], int size) {
    // TODO: Print the distances between adjacent coordinates

    // Your function should NOT return anything
    // Your function SHOULD print the distances
}

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:

1511 autotest adjacent_distances

Download array_clamping_max.c here

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

1511 fetch-activity array_clamping_max

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

void clamp_max(int arr[SIZE][SIZE], int size, int max) {
    // TODO: Make sure all values are <= max
    // Change any values that are > max
}

Given a 2D array of integers and a maximium value, you must make sure all values within the 2D array are less than or equal to that maximium value. If a value is greater than the max value, you should change the value to be equal to the max value.

For example if the given array was as follows, and the max value was set to 10

Then the array should be changed to be

Your function will be called directly in marking, any changes in the main function will not be used. You may use additional functions if you find it helpful.

You can assume the array is always square and the size is always 5.

The array values given can be any valid integer.

You are not required to print the array, this is handled separately.

You are only required to implement the clamp_max function.

Examples

dcc adjacent_distances.c -o adjacent_distances
./adjacent_distances
Before:
  9   3   2   5   2 
  2  12   5   1  11 
  4   4   7   7   6 
 10   0   4  15   0 
  2   9   0   4   0 
After:
  9   3   2   5   2 
  2  10   5   1  10 
  4   4   7   7   6 
 10   0   4  10   0 
  2   9   0   4   0 

Your program must produce this output exactly

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

1511 autotest array_clamping_max

Download list_delete_negatives.c here

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

1511 fetch-activity list_delete_negatives

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]

Your function should return a pointer to a linked list with the following values

Head => [3, 4, 10]

Additionally, if the linked list had the values

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

Your function should return a pointer to a linked list with the following values

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:

1511 autotest list_delete_negatives

Download list_delete_duplicates.c here

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

1511 fetch-activity list_delete_duplicates

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]

After removing duplicates, the list would become

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

Example 2

For example, if the linked list had the values

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

After removing duplicates, the list would become

Head => [10, 11, 12]

Example 3

For example, if the linked list had the values

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

After removing duplicates, the list would become

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:

1511 autotest list_delete_duplicates