Week 11 Laboratory Exercises

• using linked lists to store real-world data
• more advanced linked list operations

This lab is worth a total of 1.4 marks and consists of the following activities:

Lab exercises are capped at 15 marks. For more details, see the course outline.

Download list_delete_first.c here

Or, copy these file(s) to your CSE account using the following command:

1091 fetch-activity list_delete_first

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

//
// 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) {

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

Note list_delete_first.c uses the following familiar data type:

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

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

Add code to delete_first so that it deletes the first node from list

delete_first should return a pointer to the new first node in the list

If the list is now empty, delete_first should return NULL

delete_first 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_first should return a pointer to a list with these elements:

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

Hint: This task should only require a few lines of code

Testing

list_delete_first.c also contains a main function which allows you to test your delete_first function. It converts the inputs to a linked list, calls delete_first and then prints the result.

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

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

Examples

dcc list_delete_first.c -o list_delete_first
./list_delete_first
Total numbers: 8
16 7 8 12 13 19 21 12
[7, 8, 12, 13, 19, 21, 12]
./list_delete_first
Total numbers: 6
2 4 6 2 4 6
[4, 6, 2, 4, 6]
./list_delete_first
Total numbers: 1
42
[]
./list_delete_first
Total numbers: 0
[]

Assumptions/Restrictions/Clarifications

• delete_first should call free to free the memory for the node it deletes
• delete_first should not change the data fields of list nodes
• delete_first should not use arrays
• delete_first should not call malloc
• delete_first should not call scanf (or getchar or fgets)
• delete_first should not print anything. It should not call printf
• Do not change the supplied main function. It will not be tested or marked

1091 style list_delete_first.c

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

1091 autotest list_delete_first

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

give dp1091 lab11_list_delete_first list_delete_first.c

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

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

cp -n /import/reed/A/dp1091/public_html/26T1/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 /import/reed/A/dp1091/public_html/26T1/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.

1091 style list_delete_last.c

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

1091 autotest list_delete_last

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

give dp1091 lab11_list_delete_last list_delete_last.c

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

Download list_insert_nth.c here

Or, copy these file(s) to your CSE account using the following command:

1091 fetch-activity list_insert_nth

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 LINES!
    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 end of 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:

1. Asks for the size of the linked list,
2. asks for standard input to convert to a linked list,
3. assigns a pointer to the first node in the linked list to head,
4. reads an integer from standard input and assigns it to n,
5. reads a second integer from standard input and assigns it to value
6. calls insert_nth(n, value, head) and
7. prints the result.

Do not change this 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
How many numbers in initial list?: 3
16 7 8
Enter position and value to insert: 0 12
[12, 16, 7, 8]
./list_insert_nth
How many numbers in initial list?: 3
16 7 8
Enter position and value to insert: 1 12
[16, 12, 7, 8]
./list_insert_nth
How many numbers in initial list?: 3
16 7 8
Enter position and value to insert: 2 12
[16, 7, 12, 8]
./list_insert_nth
How many numbers in initial list?: 3
16 7 8
Enter position and value to insert: 3 12
[16, 7, 8, 12]
./list_insert_nth
How many numbers in initial list?: 3
16 7 8
Enter position and value to insert: 42 12
[16, 7, 8, 12]
./list_insert_nth
How many numbers in initial list?: 1
42
Enter position and value to insert: 0 16
[16, 42]
./list_insert_nth
How many numbers in initial list?: 0
Enter position and value to insert: 0 2
[2]
./list_insert_nth
How many numbers in initial list?: 0
Enter position and value to insert: 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.
• The n provided will always be non-negative
• Do not change the supplied main function. It will not be tested or marked.

1091 style list_insert_nth.c

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

1091 autotest list_insert_nth

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

give dp1091 lab11_list_insert_nth list_insert_nth.c

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

Download list_get_nth_v2.c here

Or, copy these file(s) to your CSE account using the following command:

1091 fetch-activity list_get_nth_v2

Your task is to complete the program list_get_nth_v2.c. This will be achieved by completing the get_nth function. The program will ask the user to input the length of a linked list and the number of elements it contains. It will then ask for an nth element. The elements are counted in the same manner as array elements (zero-based), so the first element in the list is regarded as n = 0, the second element as n = 1 and so on. In the case where there is no nth element in the list, an error message should be printed out.

Examples

dcc list_get_nth_v2.c -o list_get_nth_v2
./list_get_nth_v2
How many elements in the list: 5
5 2 6 1 6

Which nth element would you like to find: 0
The nth value is 5!
./list_get_nth_v2
How many elements in the list: 6
1 2 3 4 5 6

Which nth element would you like to find: 7
ERROR: no nth element in list.

Assumptions/Restrictions/Clarifications

• The list will always have at least one element.
• The nth value will always be a whole number >= 0.
• Correct number of elements will always be given.

1091 style list_get_nth_v2.c

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

1091 autotest list_get_nth_v2

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

give dp1091 lab11_list_get_nth_v2 list_get_nth_v2.c

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

Download lists_diagonal.c here

Or, copy these file(s) to your CSE account using the following command:

1091 fetch-activity lists_diagonal

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

// Treat the linked lists like they're a 2D array
// and return 1 if the first element is repeated
// diagonally through the lists
int has_diagonal(struct list_node *head) {
    return 0;
}

lists_diagonal.c is written using struct node and struct list_node that cannot be changed.

struct node is a normal linked list node while struct list_node is used to make a linked list where each element contains a list of struct nodes.

For this exercise, you will implement the function has_diagonal It should take a pointer to the head of a struct list_node linked list, and check the values of the inner struct node linked list.

Imagine each struct node list as extending out from each struct list_node list (i.e. a 2D linked list). has_diagonal will return 1 if there is a diagonal pattern, and 0 if there isn't.

A diagonal in this exercise means that the first number in the first list is the same as the second number in the second list and the third number in the third list and so on.

For example if the list of lists looks like this:

list_node 0 contains the list {5, 0, 0}
list_node 1 contains the list {0, 5, 0}
list_node 2 contains the list {0, 0, 5}

has_diagonal should return 1 as the number 5 is repeated diagonally down the list of lists:

list_node 0 contains the list {5, 0, 0}
list_node 1 contains the list {0, 5, 0}
list_node 2 contains the list {0, 0, 5}

However, if the list of lists looks like this:

list_node 0 contains the list {5, 0, 0, 0}
list_node 1 contains the list {0, 4, 0, 0}
list_node 2 contains the list {0, 0, 5, 0}
list_node 3 contains the list {0, 0, 0, 5}

has_diagonal should return 0, because the 2nd element of the second list does not equal the value of the first element of the first list:

list_node 0 contains the list {5, 0, 0, 0}
list_node 1 contains the list {0, 4, 0, 0}
list_node 2 contains the list {0, 0, 5, 0}
list_node 3 contains the list {0, 0, 0, 5}

Assumptions/Restrictions/Clarifications

• struct node and struct list_node cannot be edited. They must be used as they are
• 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 struct list_nodes
• You can assume that all lists of struct nodes are also not empty
• You can assume that there will always be the same number of struct nodes in each list and that will be the same number of struct list_nodes. That is to say, the 2D grid formed by the lists will always be square
• Your submitted file may contain a main function. It will not be tested or marked

1091 style lists_diagonal.c

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

1091 autotest lists_diagonal

Download debug_remove_nth.c here

Or, copy these file(s) to your CSE account using the following command:

1091 fetch-activity debug_remove_nth

Note that this exercise is not marked or worth marks!

Debugging Tips!

Some debugging tips for you:

• dcc output - as you run into issues, dcc will point you to where the errors are. Remember that dcc gives you the line number the issue is on, and will give some sort of explanation. Make sure you read everything dcc gives you. Sometimes we get “errors carried forward”, so find your first error, fix that, then recompile.
• print statements - sometimes it can be handy to see if the flow of your code puts you in the spot you expect it to be (ie. inside the right if statement, or going through a loop the correct amount of times). A quick way you can check this is by putting print statements in your code for testing purposes, like "the value of x is %d and y is %d". This lets you check that you got against what you expected.
• DPST1091 debugging guide

The Task

This task takes in a linked list via command line arguments. Prompts the user to input the index n of the node which they wish to remove form the list. Then, the program attempts to remove the node at index n via calling the delete_nth function.

For example if the existing list is 1 -> 2 -> 3 -> 4 -> X, if the user inputs 2 as the index of the node they wish to delete after calling the delete_nth function on the list is as follows: 1 -> 2 -> 4 -> X. Note, the node containing the value 3 is removed from the list since is the node at index 2 in the original list. Note we start counting indexes from 0.

Currently it has some issues it is your job to figure them out and fix the code. Note, you should only need to modify the delete_nth function to fix the program.

Examples

dcc debug_remove_nth.c -o debug_remove_nth
./debug_remove_nth 1 2 3 4 5 6
What is the position of the node you wish to remove: 2
Original list: [1, 2, 3, 4, 5, 6]
Modified list: [1, 2, 4, 5, 6]
./debug_remove_nth 1 2 3
What is the position of the node you wish to remove: 0
Original list: [1, 2, 3]
Modified list: [2, 3]
./debug_remove_nth 1 2 3 4 5
What is the position of the node you wish to remove: 4
Original list: [1, 2, 3, 4, 5]
Modified list: [1, 2, 3, 4]
./debug_remove_nth 1
What is the position of the node you wish to remove: 0
Original list: [1]
Modified list: []
./debug_remove_nth 
What is the position of the node you wish to remove: 0
Original list: []
Modified list: []
./debug_remove_nth 1 2 3 4
What is the position of the node you wish to remove: 4
Original list: [1, 2, 3, 4]
Index out of range, no node deleted
Modified list: [1, 2, 3, 4]
./debug_remove_nth 1 2 3 4
What is the position of the node you wish to remove: -1
Original list: [1, 2, 3, 4]
Index out of range, no node deleted
Modified list: [1, 2, 3, 4]

Assumptions/Restrictions/Clarifications

• You may assume all command line arguments will be integers
• The function prints Index out of range, no node deleted if the index entered by the user is greater then the legnth of the list. It then also does not modify the list.

1091 style debug_remove_nth.c

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

1091 autotest debug_remove_nth

This week during lab class, you will be divided into small groups and assigned an activity from this week to give a short presentation on (2–5 minutes per group).

There is no give or autotest for the group presentation.

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 Week 12 Monday 9:00am to submit your work.

You cannot obtain marks by e-mailing your code 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, using test cases different to those autotest runs for you. (Hint: do your own testing as well as running autotest.)

After automarking is run by the lecturer you can view your results here. The resulting mark will also be available 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:

1091 classrun -sturec

✨ Help Us Improve Your Learning Experience ✨

Your feedback helps us understand what’s working well and what might need improvement. This quick, anonymous check-in has just two questions and takes less than a minute to complete.

Please answer honestly — your input makes a real difference.