Week 08 Extra Sample Solutions

//
// Program to print out a linked list where each node contains an array of
// values then print out the total sum of these values.
//
// Written by Rory Golledge (z5308772) on 03-04-2022
//

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

#define MAX_ELEMENTS 100

struct node {
    struct node *next;
    int          n_elements;
    int          data[MAX_ELEMENTS];
};

int total_list_sum(struct node *head);
struct node *new_node(int n_elements);
void print_list(struct node *head);

// DO NOT CHANGE THIS MAIN FUNCTION

int main(void) {
    struct node *head = NULL;
    struct node *tail = NULL;

    int n_array_elements;
    printf("How many array elements for this node? ");
    while (scanf("%d", &n_array_elements) == 1) {
        printf("Enter elements: ");

        struct node *node = new_node(n_array_elements);

        // If node is the first, we point the head at it. Otherwise, we add
        // the node after the tail.
        if (head == NULL) {
            head = node;
            tail = node;
        } else {
            tail->next = node;
            tail = node;
        }

        printf("\nHow many array elements for this node? ");
    }
    printf("\n");

    print_list(head);
    printf("Sum: %d\n", total_list_sum(head));

    return 0;
}


//
// Print a linked list given the `head` of that list.
//
// Print occurs in the following format, depending on what nodes exist and
// the values in each array:
//
// #Elements: 3, Elements: [1, 2, 3]
// |
// v
// #Elements: 2, Elements: [1, 2]
// |
// v
// #Elements: 4, Elements: [1, 2, 3, 4]
// |
// v
// X
//
void print_list(struct node *head) {
    printf("Linked list:\n");
    struct node *current_node = head;
    while (current_node != NULL) {
        printf(
            "#Elements: %d, Elements: [",
            current_node->n_elements
        );
        int i = 0;
        while (i < current_node->n_elements) {
            printf("%d", current_node->data[i]);
            if (i < current_node->n_elements - 1) {
                printf(", ");
            }
            i++;
        }
        printf("]\n|\nv\n");
        current_node = current_node->next;
    }
    printf("X\n");
}

//
// 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) {
    int sum = 0;
    struct node *current_node = head;
    while (current_node != NULL) {
        int i = 0;
        while (i < current_node->n_elements) {
            sum += current_node->data[i];
            i++;
        }
        current_node = current_node->next;
    }

    return sum;
}


// DO NOT CHANGE THIS FUNCTION
// create a new node and fills array elements equal to the `n_elements` provided
struct node *new_node(int n_elements) {
    struct node *node = malloc(sizeof(struct node));

    node->n_elements = n_elements;
    node->next = NULL;

    int element_index = 0;
    // Loop and add all elements to array of new node.
    while (
        element_index < n_elements &&
        scanf("%d", &node->data[element_index]) == 1
    ) {
        element_index++;
    }

    // If this assertion fails, then the required number of elements were not
    // scanned in.
    assert(element_index == n_elements);

    return node;
}

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

#define MAX_INPUT_STRING_LENGTH 1024

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

int join_detection_point(struct node *first_list, struct node *second_list);
struct node *scan_in_list();
struct node *string_to_list(char *string);

// DO NOT CHANGE THIS MAIN FUNCTION

int main(void) {
    printf("Enter first list: ");
    struct node *first_list = scan_in_list();
    printf("Enter second list: ");
    struct node *second_list = scan_in_list();
    if (second_list == NULL) {
        printf("The second list will always have at least 1 element.\n");
        return 1;
    }

    printf("Which node of list 1 will the end of list 2 point at? ");
    int node_index;
    scanf("%d", &node_index);

    // Find the node we need the end of the second list to point at.
    struct node *current_node = first_list;
    int counter = 0;
    while (current_node != NULL && counter != node_index) {
        current_node = current_node->next;
        counter++;
    }

    // Find the last node of the second list to join them together
    struct node *last_node = second_list;
    while (last_node->next != NULL) {
        last_node = last_node->next;
    }

    last_node->next = current_node;

    int res = join_detection_point(first_list, second_list);
    if (res == -1) {
        printf("These lists do not join at all.\n");
    } else {
        printf("These lists join at node %d of the second list!\n", res);
    }

    return 0;
}

//
// Gets the index relative to `second_list` where `first_list` and
// `second_list` share a node.
//
// Returns this index if found, otherwise return -1
//
int join_detection_point(struct node *first_list, struct node *second_list) {
    int point = -1;

    struct node *second_list_curr = second_list;
    int second_list_index = 0;
    while (second_list_curr != NULL && point == -1) {
        struct node *first_list_curr = first_list;
        while (first_list_curr != NULL && point == -1) {
            // Compare the addresses of every pair of nodes in list 1 and 2.
            // The first time they are equal is the point where the lists
            // joined.
            if (first_list_curr == second_list_curr) {
                point = second_list_index;
            }
            first_list_curr = first_list_curr->next;
        }

        second_list_curr = second_list_curr->next;
        second_list_index++;
    }

    return point;
}

// DO NOT CHANGE THIS FUNCTION
// Handles input/output to scan in a list
struct node *scan_in_list() {
    char inputs[MAX_INPUT_STRING_LENGTH];
    char *input_res = fgets(inputs, MAX_INPUT_STRING_LENGTH, stdin);

    // create linked list input line
    struct node *head = NULL;
    if (input_res != NULL) {
        // Remove newline off string
        if (inputs[strlen(inputs) - 1] == '\n') {
            inputs[strlen(inputs) - 1] = '\0';
        }
        
        // Make sure all elements are valid
        int i = 0;
        // Flag for whether string is valid. An empty string is not valid and
        // initial value is based off that.
        int valid_string = strlen(inputs) > 0;
        while (valid_string && inputs[i] != '\0') {
            // Strings can only contain numbers/spaces
            if ((inputs[i] < '0' || inputs[i] > '9') && inputs[i] != ' ' && inputs[i] != '-') {
                printf("%c\n", inputs[i]);
                valid_string = 0;
            }
            i++;
        }
        
        if (valid_string) {
            head = string_to_list(inputs);
        }
    }

    return head;
}

// DO NOT CHANGE THIS FUNCTION
// create linked list from string of ints
struct node *string_to_list(char *string) {
    struct node *head = NULL;
    struct node *tail = NULL;

    char *token = strtok(string, " ");

    while (token != NULL) {
        struct node *n = malloc(sizeof (struct node));
        assert(n != NULL);
        n->next = NULL;
        n->data = atoi(token);
        if (head == NULL) {
            head = n;
            tail = n;
        } else {
            tail->next = n;
            tail = n;
        }

        token = strtok(NULL, " ");
    }   

    return head;
}