COMP1511 19T1 Revision Linked Lists Sample Solutions

Document Content and Description Below

COMP1511 Revision Linked Lists Sample Solution Linked Lists Sample Solutions COMP1511 19T1 Revision Video: Linked Lists - Prerequisites Linked Lists - Prerequisites Revision Video: Linked Lists ... - Creating and traversing a linked list (Coding) Linked Lists - Creating and traversing a linked list (Coding) Revision Video: Linked List - Sorted Insert Linked List - Sorted Insert09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 2/36 Revision Video: Linked Lists - Adding elements to a Linked List (Coding) Linked Lists - Adding elements to a Linked List (Coding) Revision Video: Linked List - Delete Linked List - Delete09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 3/36 Revision Video: Linked Lists - Deleting elements from a Linked List (Coding) Linked Lists - Deleting elements from a Linked List (Coding) Revision Exercise: Length of a Linked List A linked list is another way of representing a collection of data of the same type. 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/19T1/activities/list_length/list_length.c . Your task is to add code to this function in list_length.c:09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 4/36 // 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; } length is given one argument, head, which is the pointer to the first node in a linked list. 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 list_length.c also contains a main function which allows you to test your length 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_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 return a single integer. 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 use autotest to run some simple automated tests: $ 1511 autotest list_length Autotest Results 99% of 222 students who have autotested list_length.c so far, passed all autotest tests. 99% passed test 1 99% passed test 2 99% passed test 3 99% passed test 409/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 5/36 99% passed test 5 99% passed test 6 Sample solution for list_length.c #include <stdio.h> #include <stdlib.h> #include <assert.h> struct node { struct node *next; int data; }; int length(struct node *head); struct node *strings_to_list(int len, char *strings[]); int main(int argc, char *argv[]) { // create linked list from command line arguments struct node *head = strings_to_list(argc - 1, &argv[1]); int result = length(head); printf("%d\n", result); return 0; } // Return length of a linked list. int length(struct node *head) { int len = 0; struct node *n = head; while (n != NULL) { len = len + 1; n = n->next; } return len; } // create linked list from array of strings struct node *strings_to_list(int len, char *strings[]) { struct node *head = NULL; for (int i = len - 1; i >= 0; i = i - 1) { struct node *n = malloc(sizeof (struct node)); assert(n != NULL); n->next = head; n->data = atoi(strings[i]); head = n; } return head; } Alternative solution for list_length.c #include <stdio.h> #include <assert.h> struct node { struct node *next; int data; }; // Return length of a linked list. int length(struct node *head) { if (head == NULL) { return 0; } return 1 + length(head->next); }09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 6/36 Revision Exercise: Sum the elements in a Linked List Download list_sum.c here, or copy it to your CSE account using the following command: $ cp -n /web/cs1511/19T1/activities/list_sum/list_sum.c . Your task is to add code to this function in list_sum.c: // Return the sum of the elements in the linked list pointed by head int sum(struct node *head) { // PUT YOUR CODE HERE (change the next line!) return 42; } sum is given one argument, head, which is the pointer to the first node in a linked list. Add code to sum so that its returns the sum of the list. For example if the linked list contains these 8 elements: 1, 7, 8, 9, 13, 19, 21, 42 sum should return 120 because 1 + 7 + 8 + 9 + 13 + 19 + 21 + 42 = 120. Testing list_sum.c also contains a main function which allows you to test your sum 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_sum(head) prints the result. Do not change this main function. If you want to change it, you have misread the question. Your list_sum function will be called directly in marking. The main function is only to let you test your list_sum function Here is how you use main function allows you to test list_sum:09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 7/36 $ dcc list_sum.c -o list_sum $ ./list_sum 1 2 4 8 16 32 64 128 256 511 $ ./list_sum 2 4 6 5 8 9 34 $ ./list_sum 13 15 17 17 18 80 $ ./list_sum 42 4 46 $ ./list_sum 0 Assumptions/Restrictions/Clarifications. sum should return a single integer. sum should not change the linked list it is given. Your function should not change the next or data fields of list nodes. sum should not use arrays. sum should not call malloc. sum should not call scanf (or getchar or fgets). sum 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 use autotest to run some simple automated tests: $ 1511 autotest list_sum Autotest Results 100% of 219 students who have autotested list_sum.c so far, passed all autotest tests. Sample solution for list_sum.c09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 8/36 #include <stdio.h> #include <stdlib.h> #include <assert.h> struct node { struct node *next; int data; }; int sum(struct node *head); struct node *strings_to_list(int len, char *strings[]); int main(int argc, char *argv[]) { // create linked list from command line arguments struct node *head = strings_to_list(argc - 1, &argv[1]); int result = sum(head); printf("%d\n", result); return 0; } // Return sum of a linked list. int sum(struct node *head) { int total = 0; struct node *n = head; while (n != NULL) { total = total + n->data; n = n->next; } return total; } // create linked list from array of strings struct node *strings_to_list(int len, char *strings[]) { struct node *head = NULL; for (int i = len - 1; i >= 0; i = i - 1) { struct node *n = malloc(sizeof (struct node)); assert(n != NULL); n->next = head; n->data = atoi(strings[i]); head = n; } return head; } Alternative solution for list_sum.c #include <stdio.h> #include <assert.h> struct node { struct node *next; int data; }; // Return sum of a linked list. int sum(struct node *head) { if (head == NULL) { return 0; } return head->data + sum(head->next); } Revision Exercise: Print the elements in a Linked List09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 9/36 Download list_print.c here, or copy it to your CSE account using the following command: $ cp -n /web/cs1511/19T1/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 Asprintptions/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. When you think your program is working you can use autotest to run some simple automated tests: $ 1511 autotest list_print Autotest Results 100% of 215 students who have autotested list_print.c so far, passed all autotest tests.09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 10/36 Sample solution for list_print.c #include <stdio.h> #include <stdlib.h> #include <assert.h> struct node { struct node *next; int data; }; void print(struct node *head); struct node *strings_to_list(int len, char *strings[]); int main(int argc, char *argv[]) { // create linked list from command line arguments struct node *head = strings_to_list(argc - 1, &argv[1]); print(head); return 0; } // print a linked list in this format: // 17 -> 34 -> 51 -> 68 -> X void print(struct node *head) { struct node *n = head; while (n != NULL) { printf("%d -> ", n->data); n = n->next; } printf("X\n"); } // create linked list from array of strings struct node *strings_to_list(int len, char *strings[]) { struct node *head = NULL; for (int i = len - 1; i >= 0; i = i - 1) { struct node *n = malloc(sizeof (struct node)); assert(n != NULL); n->next = head; n->data = atoi(strings[i]); head = n; } return head; } Alternative solution for list_print.c #include <stdio.h> #include <assert.h> struct node { struct node *next; int data; }; // print a linked list in this format: // 17 -> 34 -> 51 -> 68 -> X void print(struct node *head) { if (head == NULL) { printf("X\n"); } printf("%d -> ", head->data); print(head->next); }09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 11/36 Revision Exercise: Test if a Linked List is Increasing Order Download list_increasing.c here, or copy it to your CSE account using the following command: $ cp -n /web/cs1511/19T1/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 is is increasing order Testing list_increasing.c also contains a main function which allows you to test your increasing 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_increasing(head) 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 Here is how you use main function allows you to test list_increasing:09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 12/36 $ dcc list_increasing.c -o list_increasing $ ./list_increasing 1 2 4 8 16 32 64 128 256 1$ ./list_increasing 2 4 6 5 8 9 0$ ./list_increasing 13 15 17 17 18 19 0$ ./list_increasing 2 4 1$ ./list_increasing 42 1$ ./list_increasing 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. When you think your program is working you can use autotest to run some simple automated tests: $ 1511 autotest list_increasing Autotest Results 92% of 207 students who have autotested list_increasing.c so far, passed all autotest tests. 97% passed test 1 96% passed test 10 96% passed test 2 94% passed test 3 95% passed test 4 97% passed test 5 96% passed test 6 97% passed test 7 96% passed test 8 96% passed test 9 Sample solution for list_increasing.c09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 13/36 #include <stdio.h> #include <stdlib.h> #include <assert.h> struct node { struct node *next; int data; }; int increasing(struct node *head); struct node *strings_to_list(int len, char *strings[]); int main(int argc, char *argv[]) { // create linked list from command line arguments struct node *head = strings_to_list(argc - 1, &argv[1]); int result = increasing(head); printf("%d\n", result); return 0; } // return 1 if values in a linked list are in increasing order, // return 0, otherwise int increasing(struct node *head) { if (head == NULL) { return 1; } struct node *p = head; while (p->next != NULL) { if (p->data >= p->next->data) { return 0; } p = p->next; } return 1; } // create linked list from array of strings struct node *strings_to_list(int len, char *strings[]) { struct node *head = NULL; for (int i = len - 1; i >= 0; i = i - 1) { struct node *n = malloc(sizeof (struct node)); assert(n != NULL); n->next = head; n->data = atoi(strings[i]); head = n; } return head; } Alternative solution for list_increasing.c09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 14/36 #include <stdio.h> #include <assert.h> struct node { struct node *next; int data; }; // return 1 if values in a linked list in increasing order // recursive solution int increasing(struct node *head) { if (head == NULL || head->next == NULL) { return 1; } else if (head->data >= head->next->data) { return 0; } else { return increasing(head->next); } } Revision Exercise: Count Elements Divisible by 17 in Linked List Download list_count_favourite.c here, or copy it to your CSE account using the following command: $ cp -n /web/cs1511/19T1/activities/list_count_favourite/list_count_favourite.c . Your task is to add code to this function in list_count_favourite.c: // Return the number of elements divisible by 17 in the linked list int count_favourite(struct node *head) { // PUT YOUR CODE HERE (change the next line!) return 42; } count_favourite is given one argument, head, which is the pointer to the first node in a linked list. Add code to count_favourite so that its returns the number of elements divisible by 17 in the list. For example if the linked list contains these 8 elements: 51, 7, 8, 9, 34, 19, 34, 42 count_favourite should return 3 because 51, 34 and 34 are divisible by 17. Testing list_count_favourite.c also contains a main function which allows you to test your count_favourite 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_count_favourite(head) prints the result. Do not change this main function. If you want to change it, you have misread the question. Your list_count_favourite function will be called directly in marking. The main function is only to let you test your list_count_favourite function Here is how you use main function allows you to test list_count_favourite:09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 15/36 $ dcc list_count_favourite.c -o list_count_favourite $ ./list_count_favourite 51 7 8 9 34 19 34 42 3$ ./list_count_favourite 2 4 6 5 8 9 0$ ./list_count_favourite 17 34 51 68 85 102 119 136 153 9$ ./list_count_favourite 0 Assumptions/Restrictions/Clarifications. count_favourite should return a single integer. count_favourite should not change the linked list it is given. Your function should not change the next or data fields of list nodes. count_favourite should not use arrays. count_favourite should not call malloc. count_favourite should not call scanf (or getchar or fgets). count_favourite 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 use autotest to run some simple automated tests: $ 1511 autotest list_count_favourite Autotest Results 99% of 193 students who have autotested list_count_favourite.c so far, passed all autotest tests. 99% passed test 1 99% passed test 2 99% passed test 3 99% passed test 4 99% passed test 5 99% passed test 6 Sample solution for list_count_favourite.c09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 16/36 #include <stdio.h> #include <stdlib.h> #include <assert.h> struct node { struct node *next; int data; }; int count_favourite(struct node *head); struct node *strings_to_list(int len, char *strings[]); int main(int argc, char *argv[]) { // create linked list from command line arguments struct node *head = strings_to_list(argc - 1, &argv[1]); int result = count_favourite(head); printf("%d\n", result); return 0; } // Return the number of elements divisible by 17 in the linked list int count_favourite(struct node *head) { int count = 0; struct node *n = head; while (n != NULL) { if (n->data % 17 == 0) { count = count + 1; } n = n->next; } return count; } // create linked list from array of strings struct node *strings_to_list(int len, char *strings[]) { struct node *head = NULL; for (int i = len - 1; i >= 0; i = i - 1) { struct node *n = malloc(sizeof (struct node)); assert(n != NULL); n->next = head; n->data = atoi(strings[i]); head = n; } return head; } Alternative solution for list_count_favourite.c #include <stdio.h> #include <assert.h> struct node { struct node *next; int data; }; // Return the number of elements divisible by 17 in the linked list int count_favourite(struct node *head) { if (head == NULL) { return 0; } return (head->data % 17 == 0) + count_favourite(head->next); }09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 17/36 Revision Exercise: Test if a Value Occurs in Linked List Download list_contains.c here, or copy it to your CSE account using the following command: $ cp -n /web/cs1511/19T1/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 contains should return 8. 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.09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 18/36 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 186 students who have autotested list_contains.c so far, passed all autotest tests. 99% passed test 1 99% passed test 2 98% passed test 3 99% passed test 4 99% passed test 5 99% passed test 6 98% passed test 7 99% passed test 8 99% passed test 9 Sample solution for list_contains.c #include <stdio.h> #include <stdlib.h> #include <assert.h> struct node { struct node *next; int data; }; int contains(int value, struct node *head); struct node *strings_to_list(int len, char *strings[]); int main(int argc, char *argv[]) { if (argc < 2) { fprintf(stderr, "Usage: %s value list-elements\n", argv[0]); return 1; } int value = atoi(argv[1]); // create linked list from command line arguments struct node *head = strings_to_list(argc - 2, &argv[2]); int result = contains(value, head); printf("%d\n", result); return 0; } // Return 1 if value occurs in linked list, 0 otherwise int contains(int value, struct node *head) { struct node *n = head; while (n != NULL) { if (n->data == value) { return 1; } n = n->next; } return 0; } // create linked list from array of strings struct node *strings_to_list(int len, char *strings[]) { struct node *head = NULL; for (int i = len - 1; i >= 0; i = i - 1) { struct node *n = malloc(sizeof (struct node)); assert(n != NULL); n->next = head; n->data = atoi(strings[i]); head = n; } return head; }09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 19/36 Alternative solution for list_contains.c #include <stdio.h> #include <assert.h> struct node { struct node *next; int data; }; // Return 1 if value occurs in linked list, 0 otherwise int contains(int value, struct node *head) { if (head == NULL) { return 0; } return (head->data == value) || contains(value, head->next); }09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 20/36 Revision Exercise: Return Middle Element of Linked List Download list_get_middle.c here, or copy it to your CSE account using the following command: $ cp -n /web/cs1511/19T1/activities/list_get_middle/list_get_middle.c . Your task is to add code to this function in list_get_middle.c: // Return middle element of a linked list // if list contains [6,7,8,9,10] 8 is returned // if a list has even number of elements, first of middle two elements returned // if list contains [1,2,3,4] 2 is returned // list can not be empty int get_middle(struct node *head) { // PUT YOUR CODE HERE (change the next line!) return 42; } get_middle is given one argument, head, which is the pointer to the first node in a linked list. Add code to get_middle so that its returns the middle value of the list. If the list an even number of elements the first of the 2 elements in the middleof the list should be returned. For example if the linked list contains these 8 elements: 1, 7, 8, 9, 13, 19, 21, 42 get_middle should return 9 because 9 and 13 are the middle two elements/ And or example if the linked list contains these 8 elements: 1, 2, 8, 1, 42 get_middle should return 8 because it is the middle element. get_middle can asusme the list is not empty. Testing list_get_middle.c also contains a main function which allows you to test your get_middle 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_get_middle(head) prints the result. Do not change this main function. If you want to change it, you have misread the question. Your list_get_middle function will be called directly in marking. The main function is only to let you test your list_get_middle function Here is how you use main function allows you to test list_get_middle:09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 21/36 $ dcc list_get_middle.c -o list_get_middle $ ./list_get_middle 1 2 4 8 16 32 64 128 256 16 $ ./list_get_middle 2 4 6 5 8 9 6$ ./list_get_middle 13 15 17 19 18 17 $ ./list_get_middle 42 4 42 $ ./list_get_middle 42 42 Assumptions/Restrictions/Clarifications. get_middle should return a single integer. get_middle can assume the list has at least one element. get_middle should not change the linked list it is given. Your function should not change the next or data fields of list nodes. get_middle should not use arrays. get_middle should not call malloc. get_middle should not call scanf (or getchar or fgets). get_middle 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 use autotest to run some simple automated tests: $ 1511 autotest list_get_middle Autotest Results 94% of 187 students who have autotested list_get_middle.c so far, passed all autotest tests. 95% passed test 1 95% passed test 2 95% passed test 3 98% passed test 4 94% passed test 5 Sample solution for list_get_middle.c09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 22/36 #include <stdio.h> #include <stdlib.h> #include <assert.h> struct node { struct node *next; int data; }; int get_middle(struct node *head); int length(struct node *head); struct node *strings_to_list(int len, char *strings[]); int main(int argc, char *argv[]) { // create linked list from command line arguments struct node *head = strings_to_list(argc - 1, &argv[1]); int result = get_middle(head); printf("%d\n", result); return 0; } // Return middle element of a linked list // if list contains [6,7,8,9,10] 8 is returned // if a list has even number of elements, first of middle two elements returned // if list contains [1,2,3,4] 2 is returned // list can not be empty int get_middle(struct node *head) { assert(head != NULL); int len = length(head); int middle = (len - 1)/2; int i = 0; struct node *n = head; while (i < middle) { i = i + 1; n = n->next; } return n->data; } // Return length of a linked list. int length(struct node *head) { int len = 0; struct node *n = head; while (n != NULL) { len = len + 1; n = n->next; } return len; } // create linked list from array of strings struct node *strings_to_list(int len, char *strings[]) { struct node *head = NULL; for (int i = len - 1; i >= 0; i = i - 1) { struct node *n = malloc(sizeof (struct node)); assert(n != NULL); n->next = head; n->data = atoi(strings[i]); head = n; } return head; }09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 23/36 Revision Exercise: Return Nth Element of Linked List Download list_get_nth.c here, or copy it to your CSE account using the following command: $ cp -n /web/cs1511/19T1/activities/list_get_nth/list_get_nth.c . Your task is to add code to this function in list_get_nth.c: // Return the n-th element of linked list. // n == 0 returns first element, n == 1, second element, .... int get_nth(int n, struct node *head) { // PUT YOUR CODE HERE (change the next line!) return 42; } get_nth is given two arguments, an int n and head, which is the pointer to the first node in a linked list. Add code to get_nth so that its returns the n-th element the linked element of the linked 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. get_nth can assume that the list contains at least n + 1 elements. For example if the linked list contains these 8 elements: 1, 7, 8, 9, 13, 19, 21, 42 if n is 1 get_nth should return 7. Testing list_get_nth.c also get_nth a main function which allows you to test your get_nth function. This main function: converts the first command-line argument to n 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_get_nth(n, head) prints the result. Do not change this main function. If you want to change it, you have misread the question. Your list_get_nth function will be called directly in marking. The main function is only to let you test your list_get_nth function Here is how you use main function allows you to test list_get_nth: $ dcc list_get_nth.c -o list_get_nth $ ./list_get_nth 0 5 6 7 8 5$ ./list_get_nth 1 5 6 7 8 6$ ./list_get_nth 2 5 6 7 8 7$ ./list_get_nth 3 5 6 7 8 8$ ./list_get_nth 0 42 42 Assumptions/Restrictions/Clarifications. get_nth should return a singleinteger. get_nth can assume n is non-negative. get_nth can assume the linked list contains at least n + 1 elements. get_nth should not change the linked list it is given. Your function should not change the next or data fields of list nodes.09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 24/36 get_nth should not use arrays. get_nth should not call malloc. get_nth should not call scanf (or getchar or fgets). get_nth 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 use autotest to run some simple automated tests: $ 1511 autotest list_get_nth Autotest Results 98% of 175 students who have autotested list_get_nth.c so far, passed all autotest tests. 99% passed test 1 99% passed test 2 98% passed test 3 99% passed test 4 98% passed test 5 98% passed test 6 98% passed test 7 98% passed test 8 Sample solution for list_get_nth.c09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 25/36 #include <stdio.h> #include <stdlib.h> #include <assert.h> struct node { struct node *next; int data; }; int get_nth(int n, struct node *head); struct node *strings_to_list(int len, char *strings[]); int main(int argc, char *argv[]) { if (argc < 2) { fprintf(stderr, "Usage: %s value list-elements\n", argv[0]); return 1; } int value = atoi(argv[1]); // create linked list from command line arguments struct node *head = strings_to_list(argc - 2, &argv[2]); int result = get_nth(value, head); printf("%d\n", result); return 0; } // Return the n-th element of linked list. // n == 0 returns first element, n == 1, second element, .... int get_nth(int n, struct node *head) { assert(n >= 0); struct node *p = head; int i = n; while (i > 0) { assert(p != NULL); p = p->next; i = i - 1; } return p->data; } // create linked list from array of strings struct node *strings_to_list(int len, char *strings[]) { struct node *head = NULL; for (int i = len - 1; i >= 0; i = i - 1) { struct node *n = malloc(sizeof (struct node)); assert(n != NULL); n->next = head; n->data = atoi(strings[i]); head = n; } return head; } Alternative solution for list_get_nth.c09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 26/36 #include <stdio.h> #include <assert.h> struct node { struct node *next; int data; }; // Return the n-th element of linked list. // n == 0 returns first element, n == 1, second element, .... int get_nth(int n, struct node *head) { assert(head != NULL && n >= 0); if (n == 0) { return head->data; } return get_nth(n - 1, head->next); } Revision Exercise: Insert Item On Front of Linked List Download list_insert_head.c here, or copy it to your CSE account using the following command: $ cp -n /web/cs1511/19T1/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 function09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 27/36 $ 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. When you think your program is working you can use autotest to run some simple automated tests: $ 1511 autotest list_insert_head Autotest Results 100% of 179 students who have autotested list_insert_head.c so far, passed all autotest tests. Sample solution for list_insert_head.c09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 28/36 #include <stdio.h> #include <stdlib.h> #include <assert.h> struct node { struct node *next; int data; }; struct node *insert_head(int value, struct node *head); struct node *create_node(int data, struct node *next); struct node *strings_to_list(int len, char *strings[]); void print_list(struct node *head); int main(int argc, char *argv[]) { if (argc < 2) { fprintf(stderr, "Usage: %s value list-elements\n", argv[0]); return 1; } int value = atoi(argv[1]); // create linked list from command line arguments struct node *head = strings_to_list(argc - 2, &argv[2]); struct node *new_head = insert_head(value, head); print_list(new_head); return 0; } // 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) { struct node *new_node = malloc(sizeof (struct node)); if (new_node == NULL) { fprintf(stderr, "out of memory\n"); exit(1); } new_node->data = value; new_node->next = head; return new_node; } // create linked list from array of strings struct node *strings_to_list(int len, char *strings[]) { struct node *head = NULL; for (int i = len - 1; i >= 0; i = i - 1) { struct node *n = malloc(sizeof (struct node)); assert(n != NULL); n->next = head; n->data = atoi(strings[i]); head = n; } return head; } // print linked list void print_list(struct node *head) { printf("["); for (struct node *n = head; n != NULL; n = n->next) { // If you're getting an error here, // you have returned an invalid list printf("%d", n->data); if (n->next != NULL) { printf(", "); } } printf("]\n"); }09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 29/36 Revision Exercise: Insert Item On End of Linked List Download list_insert_tail.c here, or copy it to your CSE account using the following command: $ cp -n /web/cs1511/19T1/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 start 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. When you think your program is working you can use autotest to run some simple automated tests: $ 1511 autotest list_insert_tail09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 30/36 Autotest Results Sample solution for list_insert_tail.c09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 31/36 struct node *insert_tail(int value, struct node *head); struct node *last(struct node *head); struct node *create_node(int data, struct node *next); struct node *strings_to_list(int len, char *strings[]); void print_list(struct node *head); int main(int argc, char *argv[]) { if (argc < 2) { fprintf(stderr, "Usage: %s value list-elements\n", argv[0]); return 1; } int value = atoi(argv[1]); // create linked list from command line arguments struct node *head = strings_to_list(argc - 2, &argv[2]); struct node *new_head = insert_tail(value, head); print_list(new_head); return 0; } // Add 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) { struct node *new_node = malloc(sizeof (struct node)); if (new_node == NULL) { fprintf(stderr, "out of memory\n"); exit(1); } // create linked list from array of strings struct node *strings_to_list(int len, char *strings[]) {09/05/2019 COMP1511 Revision Linked Lists Sample Solutions struct node *new_node = malloc(sizeof (struct node)); if (new_node == NULL) { fprintf(stderr, "out of memory\n"); exit(1); Revision Exercise: Insert Item at Specified Position in Linked List Download list_insert_nth.c here, or copy it to your CSE account using the following command: $ cp -n /web/cs1511/19T1/activities/list_insert_nth/list_insert_nth.c . } 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 [2] Assumptions/Restrictions/Clarifications.09/05/2019 COMP1511 Revision Linked Lists Sample Solutions https://cgi.cse.unsw.edu.au/~cs1511/19T1/revision/linked_lists/answers 34/36 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. When you think your program is working you can use autotest to run some simple automated tests: $ 1511 autotest list_insert_nth Autotest Results 84% of 158 students who have autotested list_insert_nth.c so far, passed all autotest tests. Sample solution for list_insert_nth.c09/05/2019 COMP1511 Revision Linked Lists Sample Solutions CRICOS Provider 00098G } [Show More]

Last updated: 3 years ago

Preview 1 out of 36 pages