DPST1091 Revision Malloc Sample Solutions

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

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

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

// Given a list with at least one node, and exactly one 0,
// split the list into a list with everything before the 0,
// and a list with the 0 and everything after.
// Return a malloced split_list struct with each of these lists.
struct split_list *split(struct node *head) {

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

}

Note list_split.c uses the following familiar data type:

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

As well as this new datatype:

struct split_list {
    struct node *before;
    struct node *after;
};

split is given one argument, head. head is the pointer to the first node in a linked list. That linked list will contain at least one node, and exactly one of those nodes will have data 0.

Add code to split so that it splits the given list into two smaller lists, one linked list that contains all the nodes before the 0; and one linked list that contains the 0, and any following nodes.

split should return a malloced split_list struct.

If the zero is the first node, it should return a split_list struct with before = NULL.

If the zero is the last node, it should return a split_list struct with after being a pointer to that zero.

For example if the linked list contains these 8 elements:

16, 7, 8, 19, 0, 19, 2, 12

split should return a pointer to a split_list struct with before pointing to:

16, 7, 8, 19

And after pointing to:

0, 19, 2, 12

Testing

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

This main function:

• converts the command-line arguments to a linked list
• assigns a pointer to the first node in the linked list to head
• calls split(head)
• prints the result.

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

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

dcc list_split.c -o list_split
./list_split 0 1 2 3
split([0, 1, 2, 3])
before = []
after = [0, 1, 2, 3]
./list_split 5 3 -1 1 0
split([5, 3, -1, 1, 0])
before = [5, 3, -1, 1]
after = [0]
./list_split 1 2 -3 -4 0 -4 3 -2 1
split([1, 2, -3, -4, 0, -4, 3, -2, 1])
before = [1, 2, -3, -4]
after = [0, -4, 3, -2, 1]

Assumptions/Restrictions/Clarifications

• split should not free any memory.
• split should not change the data fields of list nodes.
• split should not use arrays.
• split will need to call malloc exactly once.
• split should not call scanf (or getchar or fgets).
• split should not print anything. It should not call printf.
• You do not need to 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:

1091 autotest list_split

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

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

struct split_list {
    struct node *before;
    struct node *after;
};

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

// DO NOT CHANGE THIS MAIN FUNCTION

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

    struct split_list *list_split = split(head);
    printf("before = ");
    print_list(list_split->before);
    printf("after = ");
    print_list(list_split->after);

    return 0;
}


// Given a list with exactly one 0 in it, split
// the list into a list with everything before the 0,
// and a list with the 0 and everything after.
// Return a malloced split_list struct with each of these lists.
struct split_list *split(struct node *head) {
    struct split_list *list_split = malloc(sizeof(struct split_list));
    list_split->before = NULL;
    list_split->after = NULL;
    if (head->data == 0) {
        list_split->after = head;
        return list_split;
    } else {
        list_split->before = head;
        struct node *curr = head;

        while (curr->next != NULL) {
            if (curr->next->data == 0) {
                list_split->after = curr->next;
                curr->next = NULL;
                return list_split;
            }
            curr = curr->next;
        }
    }

    return NULL;

}


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

// DO NOT CHANGE THIS FUNCTION
// print linked list
void print_list(struct node *head) {
    printf("[");    
    struct node *n = head;
    while (n != NULL) {
        // If you're getting an error here,
        // you have returned an invalid list
        printf("%d", n->data);
        if (n->next != NULL) {
            printf(", ");
        }
        n = n->next;
    }
    printf("]\n");
}