COMP1511 Week 08 Laboratory Exercises

Objectives

working with linked lists

Preparation

Before the lab you should re-read the relevant lecture slides and their accompanying examples.

Getting Started

Create a new directory for this lab called lab08 by typing:

mkdir lab08

Change to this directory by typing:

cd lab08

Exercise: Print out the elements of a Linked List (pair)

This is a pair exercise to complete with your lab partner.

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

cp -n /web/cs1511/19T2/activities/list_print/list_print.c .

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

// print a linked list in this format:
// 17 -> 34 -> 51 -> 68 -> X
void print(struct node *head) {

    // PUT YOUR CODE HERE
}

print is given one argument, head, which is the pointer to the first node in a linked list.

Add code to print so that it prints the elements in the list

For example if the linked list contains these 8 elements:

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

print should print 1 -> 7 -> 8 -> 9 -> 13 -> 19 -> 21 -> 42 -> X

Testing

list_print.c also contains a main function which allows you to test your print 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 list_print(head)

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

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

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

dcc list_print.c -o list_print
./list_print 1 2 4 8 16 32 64 128 256
1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 64 -> 128 -> 256 -> X
./list_print 2 4 6 5 8 9
2 -> 4 -> 6 -> 5 -> 8 -> 9 -> X
./list_print 42 4
42 -> 4 -> X
./list_print 43
43 -> X
./list_print
X

Assumptions/Restrictions/Clarifications.

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

print should not use arrays.

print should not call malloc.

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

Do not change the supplied main function. It will not be tested or marked.

New! You can run an automated code style checker using the following command:

1511 style list_print.c

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

1511 autotest list_print

Autotest Results

98% of 461 students who have autotested list_print.c so far, passed all autotest tests.

99% passed test 1
99% passed test 2
99% passed test 3
99% passed test 4
98% passed test 5
99% passed test 6

When you are finished on this exercise you and your lab partner must both submit your work by running give:

give cs1511 lab08_list_print list_print.c

Note, even though this is a pair exercise, you both must run give from your own account before Monday 29 July 17:00 to obtain the marks for this lab exercise.

Exercise: Insert an element at the head of a Linked List (pair)

This is a pair exercise to complete with your lab partner.

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

cp -n /web/cs1511/19T2/activities/list_insert_head/list_insert_head.c .

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

// Insert a new node containing value at the start of the linked list.
// The head of the new list is returned.
struct node *insert_head(int value, struct node *head) {

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

}

insert_head is given two arguments, value and head. value is an int. head is the pointer to the first node in a linked list.

Add code to insert_head so that it creates a new list node (using malloc) containing value and places it at the start of the list.

insert_head should return a pointer to the new list.

For example if value is 12 and the linked list contains these 3 elements:

16, 7, 8

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

12, 16, 7, 8

Testing

list_insert_head.c also contains a main function which allows you to test your insert_head function.

This main function:

converts the first command-line argument to value
converts the remaining command-line arguments to a linked list
assigns a pointer to the first node in the linked list to head
calls insert_head(value, head)
prints the result.

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

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

dcc list_insert_head.c -o list_insert_head
./list_insert_head 12  16 7 8
[12, 16, 7, 8]
./list_insert_head 42  16
[42, 16]
./list_insert_head 2
[2]

Assumptions/Restrictions/Clarifications.

insert_head should not use arrays.

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

insert_head should not print anything. It should not call printf.

Do not change the supplied main function. It will not be tested or marked.

New! You can run an automated code style checker using the following command:

1511 style list_insert_head.c

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

1511 autotest list_insert_head

Autotest Results

99% of 449 students who have autotested list_insert_head.c so far, passed all autotest tests.

99% passed test 1
99% passed test 2
99% passed test 3
99% passed test 4

When you are finished on this exercise you and your lab partner must both submit your work by running give:

give cs1511 lab08_list_insert_head list_insert_head.c

Note, even though this is a pair exercise, you both must run give from your own account before Monday 29 July 17:00 to obtain the marks for this lab exercise.

Exercise: Insert an element at the tail of a Linked List (pair)

This is a pair exercise to complete with your lab partner.

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

cp -n /web/cs1511/19T2/activities/list_insert_tail/list_insert_tail.c .

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

// Insert a new node containing value at the end of the linked list.
// The head of the new list is returned.
struct node *insert_tail(int value, struct node *head) {

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

}

insert_tail is given two arguments, value and head. value is an int. head is the pointer to the first node in a linked list.

Add code to insert_tail so that it creates a new list node (using malloc) containing value and places it at the end of the list.

insert_tail should return a pointer to the new list.

For example if value is 12 and the linked list contains these 3 elements:

16, 7, 8

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

16, 7, 8, 12

Testing

list_insert_tail.c also contains a main function which allows you to test your insert_tail function.

This main function:

converts the first command-line argument to value
converts the remaining command-line arguments to a linked list
assigns a pointer to the first node in the linked list to head
calls insert_tail(value, head)
prints the result.

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

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

dcc list_insert_tail.c -o list_insert_tail
./list_insert_tail 12  16 7 8
[16, 7, 8, 12]
./list_insert_tail 42  16
[16, 42]
./list_insert_tail 2
[2]

Assumptions/Restrictions/Clarifications.

insert_tail should not use arrays.

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

insert_tail should not print anything. It should not call printf.

Do not change the supplied main function. It will not be tested or marked.

New! You can run an automated code style checker using the following command:

1511 style list_insert_tail.c

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

1511 autotest list_insert_tail

Autotest Results

93% of 430 students who have autotested list_insert_tail.c so far, passed all autotest tests.

95% passed test 1
96% passed test 2
95% passed test 3
95% passed test 4

When you are finished on this exercise you and your lab partner must both submit your work by running give:

give cs1511 lab08_list_insert_tail list_insert_tail.c

Note, even though this is a pair exercise, you both must run give from your own account before Monday 29 July 17:00 to obtain the marks for this lab exercise.

Exercise: Find an element in a Linked List (pair)

This is a pair exercise to complete with your lab partner.

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

cp -n /web/cs1511/19T2/activities/list_contains/list_contains.c .

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

// Return 1 if value occurs in linked list, 0 otherwise
int contains(int value, struct node *head) {

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

}

contains is given two arguments, an int value and head, which is the pointer to the first node in a linked list.

Add code to contains so that its returns 1 if value occurs in the linked and otherwise it returns 0.

For example if the linked list contains these 8 elements:

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

and contains is called with value of 9,

contains should return 1.

Testing

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

This main function:

converts the first command-line argument to value
converts the remaining command-line arguments to a linked list
assigns a pointer to the first node in the linked list to head
calls list_contains(value, head)
prints the result.

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

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

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

dcc list_contains.c -o list_contains
./list_contains 3 1 2 3 4
1
./list_contains 42 1 2 3 4
0
./list_contains 17 15 17 17 18
1
./list_contains 21 15 17 17 18
0
./list_contains 42
0

Assumptions/Restrictions/Clarifications.

contains should return a single integer.

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

contains should not use arrays.

contains should not call malloc.

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

contains should not print anything. It should not call printf.

Do not change the supplied main function. It will not be tested or marked.

New! You can run an automated code style checker using the following command:

1511 style list_contains.c

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

1511 autotest list_contains

Autotest Results

98% of 421 students who have autotested list_contains.c so far, passed all autotest tests.

99% passed test 1
100% passed test 2
99% passed test 3
99% passed test 4
99% passed test 5
99% passed test 6
100% passed test 7
99% passed test 8
98% passed test 9

When you are finished on this exercise you and your lab partner must both submit your work by running give:

give cs1511 lab08_list_contains list_contains.c

Note, even though this is a pair exercise, you both must run give from your own account before Monday 29 July 17:00 to obtain the marks for this lab exercise.

Challenge Exercise: Insert into the nth position in a Linked List (individual)

This is an individual exercise to complete by yourself.

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

cp -n /web/cs1511/19T2/activities/list_insert_nth/list_insert_nth.c .

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

// Insert a new node containing value at position n of the linked list.
// if n == 0, node is inserted at start of list
// if n >= length of list, node is appended at end of list
// The head of the new list is returned.
struct node *insert_nth(int n, int value, struct node *head) {

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

}

insert_nth is given three arguments, n, value and head. n is an int. value is an int. head is the pointer to the first node in a linked list.

Add code to insert_nth so that it creates a new list node (using malloc) containing value and places it before position n of the list.

The elements are counted in the same manner as array elements (zero-based), so the first element in the list is regarded as at position 0, the second element position 1 and so on.

If there are less than n elements in the list, the new list node should be appended to the list.

insert_nth should return a pointer to the new list.

For example if n is 1 and value is 12 and the linked list contains these 3 elements:

16, 7, 8

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

16, 12, 7, 8

Testing

list_insert_nth.c also contains a main function which allows you to test your insert_nth function.

This main function:

converts the first command-line argument to n
converts the second command-line argument to value
converts the remaining command-line arguments to a linked list
assigns a pointer to the first node in the linked list to head
calls insert_nth(n, value, head)
prints the result.

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

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

dcc list_insert_nth.c -o list_insert_nth
./list_insert_nth 0 12  16 7 8
[12, 16, 7, 8]
./list_insert_nth 1 12  16 7 8
[16, 12, 7, 8]
./list_insert_nth 2 12  16 7 8
[16, 7, 12, 8]
./list_insert_nth 3 12  16 7 8
[16, 7, 8, 12]
./list_insert_nth 42 12  16 7 8
[16, 7, 8, 12]
./list_insert_nth 0 16  42
[16, 42]
./list_insert_nth 0 2
[2]
./list_insert_nth 10 2
[2]

Assumptions/Restrictions/Clarifications.

insert_nth should not use arrays.

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

insert_nth should not print anything. It should not call printf.

Do not change the supplied main function. It will not be tested or marked.

New! You can run an automated code style checker using the following command:

1511 style list_insert_nth.c

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

1511 autotest list_insert_nth

Autotest Results

85% of 140 students who have autotested list_insert_nth.c so far, passed all autotest tests.

94% passed test 1
90% passed test 10
93% passed test 11
91% passed test 12
95% passed test 13
92% passed test 14
91% passed test 15
93% passed test 16
91% passed test 17
91% passed test 18
91% passed test 19
90% passed test 2
90% passed test 3
90% passed test 4
94% passed test 5
94% passed test 6
92% passed test 7
92% passed test 8
95% passed test 9

When you are finished working on this exercise you must submit your work by running give:

give cs1511 lab08_list_insert_nth list_insert_nth.c

You must run give before Monday 29 July 17:00 to obtain the marks for this lab exercise. Note, this is an individual exercise, the work you submit with give must be entirely your own.

Challenge Exercise: Reverse a Linked List (individual)

This is an individual exercise to complete by yourself.

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

cp -n /web/cs1511/19T2/activities/list_reverse/list_reverse.c .

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

//
// Place the list pointed to by head into reverse order.
// The head of the list is returned.
//
struct node *reverse(struct node *head) {

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

}

Note list_reverse.c uses the following familiar data type:

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

list_reverse is given one argument, head, which is the pointer to the first node in the linked list.

Add code to reverse which rearranges the list to be in reverse order.

reverse should return a pointer to the new list.

reverse must rearrange the list by changing the next fields of nodes.

reverse must not change the data fields of nodes.

For example if the linked list contains these 8 elements:

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

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

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

Testing

list_reverse.c also contains a main function which allows you to test your list_reverse 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 reverse(head)
prints the result.

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

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

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

Assumptions/Restrictions/Clarifications.

list_reverse should not change the data fields of list nodes.

list_reverse should not use arrays.

list_reverse should not call malloc.

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

list_reverse should not print anything. It should not call printf.

Do not change the supplied main function. It will not be tested or marked.

New! You can run an automated code style checker using the following command:

1511 style list_reverse.c

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

1511 autotest list_reverse

Autotest Results

94% of 78 students who have autotested list_reverse.c so far, passed all autotest tests.

94% passed test 1
94% passed test 2
94% passed test 3
97% passed test 4
96% passed test 5

When you are finished working on this exercise you must submit your work by running give:

give cs1511 lab08_list_reverse list_reverse.c

You must run give before Monday 29 July 17:00 to obtain the marks for this lab exercise. Note, this is an individual exercise, the work you submit with give must be entirely your own.

Submission

When you are finished each exercises make sure you submit your work by running give.

You can run give multiple times. Only your last submission will be marked.

Don't submit any exercises you haven't attempted.

If you are working at home, you may find it more convenient to upload your work via give's web interface.

Remember you have until Monday 29 July 17:00 to submit your work.

You cannot obtain marks by e-mailing lab work to tutors or lecturers.

You check the files you have submitted here

Automarking will be run by the lecturer several days after the submission deadline for the test, using test cases that you haven't seen: different to the test cases autotest runs for you.

(Hint: do your own testing as well as running autotest)

After automarking is run by the lecturer you can view it here the resulting mark will also be available via via give's web interface

Lab Marks

When all components of a lab are automarked you should be able to view the the marks via give's web interface or by running this command on a CSE machine:

1511 classrun -sturec

The lab exercises for each week are worth in total 2 marks.

The best 8 of your 9 lab marks for weeks 2-10 will be summed to give you a mark out of 13. If their sum exceeds 13 - your mark will be capped at 13.

You can obtain full marks for the labs without completing challenge exercises
You can miss 1 lab without affecting your mark.