COMP1511 18s2

Week-09 Laboratory Exercises

Topics

Exercise-01: Return How Many Even Numbers are in a Linked List (individual)

Sample solution for count_even_list.c 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

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

int count_even(struct node *head);
struct node *strings_to_list(int len, char *strings[]);

int main(int argc, char *argv[]) {
    // create linked list from command line arguments
    struct node *head = strings_to_list(argc - 1, &argv[1]);

    int result = count_even(head);
    printf("%d\n", result);

    return 0;
}

// return the number of even values in a linked list
int count_even(struct node *head) {
    int num_even = 0;
    struct node *p = head;
    while (p != NULL) {
        if (p->data % 2 == 0) {
            num_even = num_even + 1;
        }
        p = p->next;
    }
    return num_even;
}

// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
    struct node *head = NULL;
    for (int i = len - 1; i >= 0; i = i - 1) {
        struct node *n = malloc(sizeof (struct node));
        assert(n != NULL);
        n->next = head;
        n->data = atoi(strings[i]);
        head = n;
    }
    return head;
}
Alternative solution for count_even_list.c 
#include <stdio.h>

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

// return the number of even values in a linked list
// cute, recursive solution
int count_even(struct node *head) {
    if (head == NULL) {
        return 0;
    } else {
        return (head->data % 2) + count_even(head->next);
    }
}

Exercise-02: Delete First Element of a Linked List (individual)

Sample solution for list_delete_first.c 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

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

struct node *delete_first(struct node *head);
struct node *strings_to_list(int len, char *strings[]);
void print_list(struct node *head);

int main(int argc, char *argv[]) {
    // create linked list from command line arguments
    struct node *head = strings_to_list(argc - 1, &argv[1]);

    struct node *new_head = delete_first(head);
    print_list(new_head);

    return 0;
}

// Delete the first node in list.
// The deleted node is freed.
// The head of the list is returned.

struct node *delete_first(struct node *head) {
    if (head == NULL) {
        // list is empty no node to delete
        return NULL;
    }
    struct node *new_head = head->next;
    free(head);
    return new_head;
}

// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
    struct node *head = NULL;
    for (int i = len - 1; i >= 0; i = i - 1) {
        struct node *n = malloc(sizeof (struct node));
        assert(n != NULL);
        n->next = head;
        n->data = atoi(strings[i]);
        head = n;
    }
    return head;
}

// print linked list
void print_list(struct node *head) {
    printf("[");

    for (struct node *n = head; n != NULL; n = n->next) {
        // If you're getting an error here,
        // you have returned an invalid list
         printf("%d", n->data);
         if (n->next != NULL) {
            printf(", ");
        }
    }
    printf("]\n");
}

Exercise-03: Delete First Element Containing A Value from a Linked List (pair)

Sample solution for list_delete_contains.c 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

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

struct node *delete_contains(int value, struct node *head);
struct node *strings_to_list(int len, char *strings[]);
void print_list(struct node *head);

int main(int argc, char *argv[]) {
    if (argc < 2) {
        fprintf(stderr, "Usage: %s value list-elements\n", argv[0]);
        return 1;
    }
    int value = atoi(argv[1]);
    // create linked list from command line arguments
    struct node *head = strings_to_list(argc - 2, &argv[2]);

    struct node *new_head = delete_contains(value, head);
    print_list(new_head);

    return 0;
}


// Delete the first node in the list containing i
// The deleted node is freed.
// If no node contains i, the list is not changed
// The head of the list is returned.

struct node *delete_contains(int value, struct node *head) {
    if (head == NULL) {
        // list is empty no node to delete
        return NULL;
    }
    if (head->data == value) {
        struct node *new_head = head->next;
        free(head);
        return new_head;
    }
    if (head->next == NULL) {
        return head;
    }

    struct node *n = head;
    // find node before first node containing i
    while (n->next->next != NULL && n->next->data != value) {
        n = n->next;
    }

    if (n->next->data == value) {
        struct node *new_next = n->next->next;
        free(n->next);
        n->next = new_next;
    }
    return head;
}

// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
    struct node *head = NULL;
    for (int i = len - 1; i >= 0; i = i - 1) {
        struct node *n = malloc(sizeof (struct node));
        assert(n != NULL);
        n->next = head;
        n->data = atoi(strings[i]);
        head = n;
    }
    return head;
}

// print linked list
void print_list(struct node *head) {
    printf("[");

    for (struct node *n = head; n != NULL; n = n->next) {
        // If you're getting an error here,
        // you have returned an invalid list
         printf("%d", n->data);
         if (n->next != NULL) {
            printf(", ");
        }
    }
    printf("]\n");
}
Alternative solution for list_delete_contains.c 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

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


// Delete the first node in list the containing value - recursive version
// The deleted node is freed.
// If no node contains i, the list is not changed
// The head of the list is returned.

struct node *delete_contains(int value, struct node *head) {
    if (head == NULL) {
        return NULL;
    }
    if (head->data == value) {
        struct node *new_head = head->next;
        free(head);
        return new_head;
    }
    head->next = delete_contains(value, head->next);
    return head;
}

Exercise-04: Remove Consecutive Repeated Values From List (pair)

Sample solution for list_delete_repeated.c 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

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

struct node *delete_repeated(struct node *head);
struct node *strings_to_list(int len, char *strings[]);
void print_list(struct node *head);

int main(int argc, char *argv[]) {
    // create linked list from command line arguments
    struct node *head = strings_to_list(argc - 1, argv + 1);

    struct node *new_head = delete_repeated(head);
    print_list(new_head);

    return 0;
}


// Delete any consecutive repeated values from a linked list - recursive version.
// Deleted nodes are freed.
// The head of the list is returned.

struct node *delete_repeated(struct node *head) {
    if (head == NULL || head->next == NULL) {
        // list of length < 2 does not need to be changed
        return head;
    }

    struct node *p = head;
    while (p->next != NULL) {
        if (p->data == p->next->data) {
            struct node *repeated = p->next;
            p->next = p->next->next;
            free(repeated);
        } else {
            p = p->next;
        }
    }

    return head;
}

// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
    struct node *head = NULL;
    for (int i = len - 1; i >= 0; i = i - 1) {
        struct node *n = malloc(sizeof (struct node));
        assert(n != NULL);
        n->next = head;
        n->data = atoi(strings[i]);
        head = n;
    }
    return head;
}

// print linked list
void print_list(struct node *head) {
    printf("[");

    for (struct node *n = head; n != NULL; n = n->next) {
        // If you're getting an error here,
        // you have returned an invalid list
         printf("%d", n->data);
         if (n->next != NULL) {
            printf(", ");
        }
    }
    printf("]\n");
}
Alternative solution for list_delete_repeated.c 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

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


// Delete any consecutive repeated values from a linked list - recursive version.
// Deleted nodes are freed.
// The head of the list is returned.

struct node *delete_repeated(struct node *head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    if (head->data == head->next->data) {
        struct node *new_head = delete_repeated(head->next);
        free(head);
        return new_head;
    }
    head->next = delete_repeated(head->next);
    return head;
}

Exercise-05: Challenge Exercise: Reverse a Linked List (individual) [Challenge Exercise]

Sample solution for list_reverse.c 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

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

struct node *reverse(struct node *head);
struct node *strings_to_list(int len, char *strings[]);
void print_list(struct node *head);

int main(int argc, char *argv[]) {
    // create linked list from command line arguments
    struct node *head = strings_to_list(argc - 1, &argv[1]);

    struct node *new_head = reverse(head);
    print_list(new_head);

    return 0;
}

// Place the list into reverse order.
// The head of the list is returned.

struct node *reverse(struct node *head) {
    if (head == NULL) {
        return NULL;
    }
    struct node *previous = NULL;
    struct node *x = head;
    while (x != NULL) {
        struct node *y = x->next;
        x->next = previous;
        previous = x;
        x = y;
    }
    return previous;
}

// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
    struct node *head = NULL;
    for (int i = len - 1; i >= 0; i = i - 1) {
        struct node *n = malloc(sizeof (struct node));
        assert(n != NULL);
        n->next = head;
        n->data = atoi(strings[i]);
        head = n;
    }
    return head;
}

// print linked list
void print_list(struct node *head) {
    printf("[");

    for (struct node *n = head; n != NULL; n = n->next) {
        // If you're getting an error here,
        // you have returned an invalid list
         printf("%d", n->data);
         if (n->next != NULL) {
            printf(", ");
        }
    }
    printf("]\n");
}
Alternative solution for list_reverse.c 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

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

// Place the list into reverse order.
// The head of the list is returned.

struct node *reverse(struct node *head) {
    // lists of 0 or 1 node don't need to be changed
    if (head == NULL || head->next == NULL) {
        return head;
    }

    //reverse rest of list
    struct node *new_head = reverse(head->next);

    // head->next will be the last element in the reversed rest of list
    // append head to it
    head->next->next = head;
    head->next = NULL;

    return new_head;
}