Week 09 Weekly Test Questions

Linked lists are made up of nodes, which store one element of the list each, as well as the location (in memory) of the next element.

Nodes can store data of any type, but for this week we will be looking at nodes which store integers, which are defined like this:

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

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

cp -n /web/cs1511/20T1/activities/list_length/list_length.c .

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

// Return the length of the linked list pointed by head
int length(struct node *head) {

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

}

Add code to length so that its returns the length of the list.

For example if the linked list contains these 8 elements:

1, 7, 8, 9, 13, 19, 21, 42

length should return 8.

Testing

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 list_length(head)
• prints the result.

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

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

Here is how you use main function allows you to test list_length:

dcc list_length.c -o list_length
./list_length 1 2 4 8 16 32 64 128 256
9
./list_length 2 4 6 5 8 9
6
./list_length 13 15 17 17 18
5
./list_length 42 4
2
./list_length
0

Assumptions/Restrictions/Clarifications.

length should not change the linked list it is given. Your function should not change the next or data fields of list nodes.

length should not use arrays.

length should not call malloc.

length should not call scanf (or getchar or fgets).

length 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 autotest to run some simple automated tests:

1511 autotest list_length

give cs1511 test09_list_length list_length.c

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

cp -n /web/cs1511/20T1/activities/list_delete_last/list_delete_last.c .

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

//
// Delete the last node in list.
// The deleted node is freed.
// The head of the list is returned.
//
struct node *delete_last(struct node *head) {

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

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

Add code to delete_last so that it deletes the last node from list.

delete_last should return a pointer to the new list.

If the list is now empty delete_last should return NULL.

delete_last should call free to free the memory of the node it deletes.

For example if the linked list contains these 8 elements:

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

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

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

Testing

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 delete_last(head)
• prints the result.

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

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

cp -n /web/cs1511/20T1/activities/list_delete_last/list_delete_last.c .
dcc list_delete_last.c -o list_delete_last
./list_delete_last 16 7 8 12 13 19 21 12
[16, 7, 8, 12, 13, 19, 21]
./list_delete_last 2 4 6 2 4 6
[2, 4, 6, 2, 4]
./list_delete_last 42
[]
./list_delete_last
[]

Assumptions/Restrictions/Clarifications.

delete_first should not change the data fields of list nodes.

delete_last should not use arrays.

delete_last should not call malloc.

delete_last should not call scanf (or getchar or fgets).

delete_last 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 autotest to run some simple automated tests:

1511 autotest list_delete_last

give cs1511 test09_list_delete_last list_delete_last.c

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

cp -n /web/cs1511/20T1/activities/list_delete_ordered/list_delete_ordered.c .

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

// Remove any nodes in a list that are higher 
// than the node directly after them.
// Return the head of the list.
// The returned list must have no disorder in it!
struct node *remove_disorder(struct node *head) {
    // WRITE YOUR CODE HERE (you may need to change the line below)
    return head;
}

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

The node struct is a normal linked list node containing an integer.

remove_disorder should take a pointer to the head of a node list and return the head of the node list after it has removed any disorder in the list. A list is considered to have disorder if there are any nodes in it that are higher in value (using the integer data) than the node directly after them.

remove_disorder should remove nodes from the list, but otherwise make no changes to the list itself.

For example if the list of nodes looks like this:

{1, 3, 2}

remove_disorder should return

{1, 2}

However, if the list looks like this:

{2, 4, 5, 1}

remove_disorder should return

{1}

remove_disorder should always return a list with no disorder in it. If any removals cause more disorder, these disordered nodes must also be removed before remove_disorder returns.

Assumptions/Restrictions/Clarifications.

struct node cannot be edited. It must be used as it is.

You may not use arrays in this solution. Arrays are not necessary to complete this task.

You can assume that you'll never receive an empty list of nodes.

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

1511 autotest list_delete_ordered

give cs1511 test09_list_delete_ordered list_delete_ordered.c