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

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

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 11 November 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_increasing.c here, or copy it to your CSE account using the following command:

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

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

int increasing(struct node *head) {

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

}

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

Add code to increasing so that its returns 1 if the list is in increasing order - the value of each list element is larger than the element before.

For example if the linked list contains these 8 elements:

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

increasing should return 1 because it is increasing order

Testing

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

This main function:

1. converts the first set of read integers to a linked list,
2. assigns a pointer to the first node in the linked list to head,
3. calls list_increasing(head) and
4. prints the result.

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

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

Examples

dcc list_increasing.c -o list_increasing
./list_increasing
How many numbers in initial list?: 9
1 2 4 8 16 32 64 128 256
1
./list_increasing
How many numbers in initial list?: 6
2 4 6 5 8 9
0
./list_increasing
How many numbers in initial list?: 6
13 15 17 17 18 19
0
./list_increasing
How many numbers in initial list?: 2
2 4
1
./list_increasing
How many numbers in initial list?: 1
42
1
./list_increasing
How many numbers in initial list?: 0
1

Assumptions/Restrictions/Clarifications

• increasing should return a single integer
• increasing should not change the linked list it is given. Your function should not change the next or data fields of list nodes
• increasing should not use arrays
• increasing should not call malloc
• increasing should not call scanf (or getchar or fgets)
• You can assume the linked list only contains positive integers
• increasing 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_increasing.c
    

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

1091 autotest list_increasing

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

give dp1091 lab11_list_increasing list_increasing.c
    

You must run give before Monday 11 November 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 it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/24T3/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 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 11 November 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 it to your CSE account using the following command:

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

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

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 11 November 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 it to your CSE account using the following command:

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

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

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

give dp1091 lab11_lists_diagonal lists_diagonal.c
    

You must run give before Monday 11 November 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.

Copy the program debug_cloud.c from the course account to your directory by typing (make sure you type the dot at the end):

cp ~dp1091/public_html/24T3/activities/debug_remove_nth/debug_remove_nth.c .

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 - https://cgi.cse.unsw.edu.au/~dp1091/23T3/resources/debugging_guide.html

The Task

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

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_second_last 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_second_last 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_second_last 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_second_last 1
What is the position of the node you wish to remove: 0
Original list: [1]
Modified list: []
./debug_remove_second_last 
What is the position of the node you wish to remove: 0
Original list: []
Modified list: []
./debug_remove_second_last 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_second_last 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