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

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

#include <stdio.h>
#include <stdlib.h>

#define SIZE 5

struct passenger {
    double height;
    int num_bags;
};

int main(void) {

    struct passenger my_array[SIZE];
    
    for(int i = 0; i < SIZE; i++) {
        printf("Enter height & number of bags: ");
        scanf("%lf %d", &my_array[i].height, &my_array[i].num_bags);
    }

    double filter_height;
    printf("Select height: ");
    scanf("%lf", &filter_height);

    int count = 0;
    for (int i = 0; i < SIZE; i++) {
        if (my_array[i].height >= filter_height) {
            count += my_array[i].num_bags;
        }
    }

    printf("Total of %d bags from people over %lf\n", count, filter_height);


    return 0;
}

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

#include <stdio.h>
#include <stdlib.h>

#define SIZE 5

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

int main(void) {

    int array1[SIZE][SIZE] = {{0, 3, 2, 5, 2},
                            {2, 1, 5, 1, 1},    // == 10
                            {4, 4, 7, 7, 0},
                            {10, 0, 0, 0, 0},   // == 10
                            {0, 0, 0, 0 ,0}};

    printf("%d rows had a sum of 10\n", find_totals(array1, SIZE));

    return 0;
}

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

    int count = 0;

    for (int row = 0; row < size; row++) {

        int row_total = 0;
        for (int col = 0; col < size; col++) {
            row_total += arr[row][col];
        }

        if (row_total == 10) {
            count++; 
        }
    }

    return count;
}

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

#include <stdio.h>
#include <stdlib.h>

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

// Provided Functions
struct node *create_node(int data);
struct node *insert_at_head(struct node *head, int data);
void print_list(struct node *head);

// Your functions
struct node *insert_after_lowest(struct node *head, int data);

// Solution Functions
int find_lowest(struct node *head);

int main(void) {

    struct node *head = insert_at_head(NULL, 6);
    head = insert_at_head(head, 2);
    head = insert_at_head(head, 4);
    
    print_list(head);
    head = insert_after_lowest(head, 99);
    print_list(head);
    
    return 0;
}

// Mallocs a new node and returns a pointer to it
struct node *create_node(int data) {
    struct node *new_node = malloc(sizeof(struct node));
    new_node->next = NULL;
    new_node->data = data;
    return new_node;
}

// Inserts at the head of a linked list
// Returns a pointer to the new head of the list
struct node *insert_at_head(struct node *head, int data) {
    struct node *new_node = create_node(data);
    new_node->next = head;
    return new_node;
}

// Prints a linked list
void print_list(struct node *head) {
    struct node *curr = head;
    while (curr != NULL) {
        printf("%d -> ", curr->data);
        curr = curr->next;
    }
    printf("X\n");
}

// Inserts a new node after the node with the 
// lowest data in the list
struct node *insert_after_lowest(struct node *head, int data) {

    // If list is empty, insert at the head
    if (head == NULL) {
        return insert_at_head(NULL, data);
    }

    int min_val = find_lowest(head);

    struct node *curr = head;
    while (curr != NULL) {
        if (curr->data == min_val) {
            struct node *new = create_node(data);
            new->next = curr->next;
            curr->next = new;
            return head;
        }
        curr = curr->next;
    }

    return head;
}

// ASSUMES LIST IS NOT NULL
int find_lowest(struct node *head) {

    struct node *curr = head;
    int min = curr->data;

    while (curr != NULL) {

        if (curr->data < min) {
            min = curr->data;
        }

        curr = curr->next;
    }

    return min;
}

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

#include <stdio.h>
#include <stdlib.h>

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

// Provided Functions
struct node *create_node(int data);
void print_list(struct node *head);

// Your functions
struct node *insert_at_head(struct node *head, int data);
struct node *insert_after_lowest(struct node *head, int data);
struct node *insert_at_tail(struct node *head, int data);


int main(void) {

    struct node *head = NULL;

    int count = 0;
    int data = 0;
    while(scanf("%d", &data) == 1) {
        if (count % 2 == 0) {
            head = insert_at_head(head, data);
        } else {
            head = insert_at_tail(head, data);
        }
        count++;
    }

    print_list(head);
    
    return 0;
}

// Mallocs a new node and returns a pointer to it
struct node *create_node(int data) {
    struct node *new_node = malloc(sizeof(struct node));
    new_node->next = NULL;
    new_node->data = data;
    return new_node;
}

// Inserts at the head of a linked list
// Returns a pointer to the new head of the list
struct node *insert_at_head(struct node *head, int data) {
    struct node *new_node = create_node(data);
    new_node->next = head;
    return new_node;
}

// Inserts at the tail of the linked list
// Returns a pointer to the head of the list
struct node *insert_at_tail(struct node *head, int data) {
    struct node *new_node = create_node(data);

    if (head == NULL) {
        return new_node;
    }

    struct node *curr = head;
    while (curr->next != NULL) {
        curr = curr->next;
    }

    curr->next = new_node;

    return head;

}

// Prints a linked list
void print_list(struct node *head) {
    struct node *curr = head;
    while (curr != NULL) {
        printf("%d -> ", curr->data);
        curr = curr->next;
    }
    printf("X\n");
}

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

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define SIZE 5

struct coordinate {
    int x;
    int y;
};

double e_dist(struct coordinate p0, struct coordinate p1);
void adjacent_distances(struct coordinate arr[SIZE], int size);

int main(void) {

    // Only your function is called during testing
    // Any changes in this main function will not
    // be used in testing

    struct coordinate array1[SIZE] = {{.x = 1, .y = 1},
                                        {.x = 2, .y = 2},
                                        {.x = 9, .y = 2},
                                        {.x = 2, .y = 9},
                                        {.x = 0, .y = 0}};

    adjacent_distances(array1, SIZE);

    return 0;
}

void adjacent_distances(struct coordinate arr[SIZE], int size) {
    for (int i = 0; i < (size - 1); i++) {
        printf("Dist: %lf\n", e_dist(arr[i], arr[i+1]));
    }    
}

double e_dist(struct coordinate p0, struct coordinate p1) {

    return sqrt((p1.x - p0.x)*(p1.x - p0.x)*1.0 +  (p1.y - p0.y)*(p1.y - p0.y)*1.0);
}

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

#include <stdio.h>
#include <stdlib.h>

#define SIZE 5

void print_array(int arr[SIZE][SIZE], int size);
void clamp_max(int arr[SIZE][SIZE], int size, int max);

int main(void) {

    int array1[SIZE][SIZE] = {{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}};

    printf("Before:\n");
    print_array(array1, SIZE);

    clamp_max(array1, SIZE, 10);

    printf("After:\n");
    print_array(array1, SIZE);

    return 0;
}

void clamp_max(int arr[SIZE][SIZE], int size, int max) {
    for (int row = 0; row < size; row++) {
        for (int col = 0; col < size; col++) {
            if (arr[row][col] > max) {
                arr[row][col] = max;
            }
        }
    }
}

void print_array(int arr[SIZE][SIZE], int size) {
    for (int row = 0; row < size; row++) {
        for (int col = 0; col < size; col++) {
            printf("%3d ", arr[row][col]);
        }
        printf("\n");
    }
}

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

#include <stdio.h>
#include <stdlib.h>

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

// Provided Functions
struct node *create_node(int data);
struct node *insert_at_head(struct node *head, int data);
void print_list(struct node *head);

// Your functions
struct node *delete_negatives(struct node *head);

// Solution Functions
int find_lowest(struct node *head);

int main(void) {

    struct node *head = insert_at_head(NULL, 6);
    head = insert_at_head(head, -2);
    head = insert_at_head(head, 4);
    
    print_list(head);
    head = delete_negatives(head);
    print_list(head);
    
    return 0;
}

// Mallocs a new node and returns a pointer to it
struct node *create_node(int data) {
    struct node *new_node = malloc(sizeof(struct node));
    new_node->next = NULL;
    new_node->data = data;
    return new_node;
}

// Inserts at the head of a linked list
// Returns a pointer to the new head of the list
struct node *insert_at_head(struct node *head, int data) {
    struct node *new_node = create_node(data);
    new_node->next = head;
    return new_node;
}

// Prints a linked list
void print_list(struct node *head) {
    struct node *curr = head;
    while (curr != NULL) {
        printf("%d -> ", curr->data);
        curr = curr->next;
    }
    printf("X\n");
}


struct node *delete_negatives(struct node *head) {

    if (head == NULL) {
        return NULL;
    }

    struct node *prev = NULL;
    struct node *curr = head; 

    while (curr != NULL) {

        if (curr->data < 0) {
            struct node *to_del = curr;
            
            // is it the head?
            if (prev == NULL) {
                curr = curr->next;
                head = curr;
                free(to_del);
                
            } else {
                prev->next = curr->next;
                curr = curr->next;
                free(to_del);
            }

        } else {
            prev = curr;
            curr = curr->next;
        }
    }

    return head;
}

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

#include <stdio.h>
#include <stdlib.h>

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

// Provided Functions
struct node *create_node(int data);
struct node *insert_at_head(struct node *head, int data);
void print_list(struct node *head);

// Your functions
struct node *delete_duplicates(struct node *head);

// Solution Functions
int find_lowest(struct node *head);

int main(void) {

    struct node *head = insert_at_head(NULL, 6);
    head = insert_at_head(head, 4);
    head = insert_at_head(head, 4);
    head = insert_at_head(head, 2);
    
    print_list(head);
    head = delete_duplicates(head);
    print_list(head);
    
    return 0;
}

// Mallocs a new node and returns a pointer to it
struct node *create_node(int data) {
    struct node *new_node = malloc(sizeof(struct node));
    new_node->next = NULL;
    new_node->data = data;
    return new_node;
}

// Inserts at the head of a linked list
// Returns a pointer to the new head of the list
struct node *insert_at_head(struct node *head, int data) {
    struct node *new_node = create_node(data);
    new_node->next = head;
    return new_node;
}

// Prints a linked list
void print_list(struct node *head) {
    struct node *curr = head;
    while (curr != NULL) {
        printf("%d -> ", curr->data);
        curr = curr->next;
    }
    printf("X\n");
}


struct node *delete_duplicates(struct node *head) {

    if (head == NULL) {
        return NULL;
    }

    struct node *curr = head; 

    while (curr != NULL && curr->next != NULL) {

        if (curr->data == curr->next->data) {

            struct node *to_del = curr->next;
            curr->next = curr->next->next;
            free(to_del);
        } else {
            curr = curr->next;   
        }
    }

    return head;
}