Create a new directory for this lab called lab13
by typing:
mkdir lab13Change to this directory by typing:
cd lab13
These revision exercises are not assessable.
They do not get marked.
There is no need to submit them with give.
The file lab13.c is the starting point for the revision exercises.
It contains struct node, which is used to store a sequence of integers. This is the same data representation you have seen in lectures.
struct node { struct node *next; int data; };
Start by copying lab13.c:
cp /import/adams/A/cs1511/public_html/17s1/tlb/13/lab13.c .lab13.c contains five functions which have not been implemented. Your task is to implement these five functions.
int count(int value, struct node *list)
Implement count.
count should return the number of nodes in the list containing value.
As usual autotest is available to test your code:
~cs1511/bin/autotest lab13 count
count
int count(int value, struct node *head) { int how_many = 0; struct node *p = head; while (p != NULL) { if (p->data == value) { how_many++; } p = p->next; } return how_many; }A recursive solution for
count
int count(int value, struct node *head) { if (head == NULL) { return 0; } if (head->data == value) { return 1 + count(value, head->next); } else { return count(value, head->next); } }Less readable but more concise recursive solution for count. Check your understanding of C by figuring out how it works.
int count1(int value, struct node *head) { if (head == NULL) { return 0; } else { return ((head->data == value) + count(value, head->next)); } }Very concise version that uses C's ternary operator. Much less readable.
int count2(int value, struct node *head) { return (head == NULL) ? 0 : ((head->data == value) + count(value, head->next)); }
struct node *get_nth(int n, struct node *head)
Implement get_nth.
get_nth should return a pointer to the node in position n in the list.
Position 0 is the first node in the list.
get_nth should return NULL if the list has no n-th node.
As usual autotest is available to test your code:
~cs1511/bin/autotest lab13 get_nth
get_nth
struct node *get_nth(int n, struct node *head) { int position = 0; struct node *p = head; while (p != NULL) { if (position == n) { return p; } p = p->next; position++; } return NULL; }A recursive solution for
get_nth
struct node *get_nth(int n, struct node *head) { if (head == NULL) { return NULL; } if (n == 0) { return head; } return get_nth(n - 1, head->next); }
struct node *delete_nth(int n, struct node *head)
Implement delete_nth.
delete_nth should delete the node in position n in the list.
delete_nth should free the deleted node.
delete_nth should make no changes if there is no position n in the list.
delete_nth should return the (possibly changed) head of the list.
As usual autotest is available to test your code:
~cs1511/bin/autotest lab13 delete_nth
delete_nth
struct node *delete_nth(int n, struct node *head) { if (head == NULL) { return NULL; } if (n == 0) { struct node *new_head = head->next; free(head); return new_head; } int position = 0; struct node *p = head; // find node in position n - 1 while (p->next != NULL) { if (position == n - 1) { struct node *new_next = p->next->next; free(p->next); p->next = new_next; return head; } p = p->next; position++; } return head; }A recursive solution for
delete_nth
struct node *delete_nth(int n, struct node *head) { if (head == NULL) { return NULL; } if (n == 0) { struct node *new_head = head->next; free(head); return new_head; } head->next = delete_nth(n - 1, head->next); return head; }
struct node *delete_odd(struct node *head)
Implement delete_odd.
delete_odd should delete all nodes in the list containing odd numbers.
delete_odd should free any deleted nodes.
delete_odd should return the (possibly changed) head of the list.
As usual autotest is available to test your code:
delete_odd
struct node *delete_odd(struct node *head) { if (head == NULL) { return NULL; } if (head->data % 2 == 1) { struct node *new_head = delete_odd(head->next); free(head); return new_head; } struct node *p = head; while (p->next != NULL) { if (p->next->data % 2 == 1) { struct node *new_next = p->next->next; free(p->next); p->next = new_next; } else { p = p->next; } } return head; }A recursive solution for
delete_odd
struct node *delete_odd(struct node *head) { if (head == NULL) { // list is empty no node to delete return NULL; } if (head->data % 2 == 1) { struct node *new_head = delete_odd(head->next); free(head); return new_head; } head->next = delete_odd(head->next); return head; }
~cs1511/bin/autotest lab13 delete_odd
struct node *insert_nth(int n, struct node *new_node, struct node *head)
Implement insert_nth.
insert_nth should insert new_node before position n in the list.
Given a position immediately after the last element in the list (n == length of the list) insert_nth should append new_node to the list.
insert_nth should otherwise make no changes if there is no position n in the list.
insert_nth should return the (possibly changed) head of the list.
As usual autotest is available to test your code:
~cs1511/bin/autotest lab13 insert_nth
insert_nth
struct node *insert_nth(int n, struct node *new_node, struct node *head) { // insert node at start of list if (n == 0) { new_node->next = head; return new_node; } if (head == NULL) { return NULL; } int position = 0; struct node *p = head; // find node in position n - 1 while (p->next != NULL) { if (position == n - 1) { // insert new_node after node in position n -1 new_node->next = p->next; p->next = new_node; return head; } p = p->next; position++; } // append node to end of list if (position == n - 1) { p->next = new_node; new_node->next = NULL; } return head; }A recursive solution for
insert_nthh
struct node *insert_nth(int n, struct node *new_node, struct node *head) { if (n == 0) { new_node->next = head; return new_node; } if (head == NULL) { return NULL; } head->next = insert_nth(n - 1, new_node, head->next); return head; }
create_node
.
Your functions must not change the data
field of any node.
Your functions may change the next
field of nodes.
Memory must be freed for nodes removed from the list.
Positions are numbered like array indices. The first node in the list is regarded as being in position 0. The last node in a list of length n is regarded as being in position n - 1.
main
function in lab13.c
contains code which allows you to
test your functions.
The examples below demonstrate how to use the testing code.
These examples also indicate how your functions should behave.
dcc lab13.c -o lab13 ./lab13 list = [] > append 4 list = [4] > append 5 list = [4, 5] > append 6 list = [4, 5, 6] > append 7 list = [4, 5, 6, 7] > append 6 list = [4, 5, 6, 7, 6] > count 42 count(42) returns 0 list = [4, 5, 6, 7, 6] > count 5 count(5) returns 1 list = [4, 5, 6, 7, 6] > count 6 count(6) returns 2 list = [4, 5, 6, 7, 6] > get_nth 0 get_nth(0) returned a pointer to a node containing 4 list = [4, 5, 6, 7, 6] > get_nth 42 get_nth(42) returned NULL list = [4, 5, 6, 7, 6] > get_nth -1 get_nth(-1) returned NULL list = [4, 5, 6, 7, 6] > delete_nth 2 list = [4, 5, 7, 6] > delete_nth 0 list = [5, 7, 6] > delete_nth 0 list = [7, 6] > insert_nth 0 list = [42, 7, 6] > insert_nth 2 list = [42, 7, 42, 6] > insert_nth 4 list = [42, 7, 42, 6, 42] > delete_odd list = [42, 42, 6, 42]Note the test of insert_nth always insert a node containing 42.
lab13.c
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> struct node { struct node *next; int data; }; // Return number of nodes in the list containing value. int count(int value, struct node *head) { int how_many = 0; struct node *p = head; while (p != NULL) { if (p->data == value) { how_many++; } p = p->next; } return how_many; } // Return a pointer to the node in position n in the list. // Position 0 is the first node in the list. // Return NULL if the list has no n-th node. struct node *get_nth(int n, struct node *head) { int position = 0; struct node *p = head; while (p != NULL) { if (position == n) { return p; } p = p->next; position++; } return NULL; } // Delete the node in position n in the list. // the deleted node is freed. // The first node in the list is in position 0. // Do nothing if there is no position n in the list. // The head of the list is returned. struct node *delete_nth(int n, struct node *head) { if (head == NULL) { return NULL; } if (n == 0) { struct node *new_head = head->next; free(head); return new_head; } int position = 0; struct node *p = head; // find node in position n - 1 while (p->next != NULL) { if (position == n - 1) { struct node *new_next = p->next->next; free(p->next); p->next = new_next; return head; } p = p->next; position++; } return head; } // Delete all nodes in the list containing odd numbers. // Any deleted nodes are freed. // The head of the list is returned. struct node *delete_odd(struct node *head) { if (head == NULL) { return NULL; } if (head->data % 2 == 1) { struct node *new_head = delete_odd(head->next); free(head); return new_head; } struct node *p = head; while (p->next != NULL) { if (p->next->data % 2 == 1) { struct node *new_next = p->next->next; free(p->next); p->next = new_next; } else { p = p->next; } } return head; } // Insert new_node before position n in the list. // The first node in the list is in position 0. // If n == length of the list, new_node is appended to list. // Otherwise do nothing if there is no position n in the list. // The head of the list is returned. struct node *insert_nth(int n, struct node *new_node, struct node *head) { // insert node at start of list if (n == 0) { new_node->next = head; return new_node; } if (head == NULL) { return NULL; } int position = 0; struct node *p = head; // find node in position n - 1 while (p->next != NULL) { if (position == n - 1) { // insert new_node after node in position n -1 new_node->next = p->next; p->next = new_node; return head; } p = p->next; position++; } // append node to end of list if (position == n - 1) { p->next = new_node; new_node->next = NULL; } return head; } // THE CODE BELOW HERE IS TO TEST YOUR FUNCTIONS // DO NOT CHANGE IT void print_list(struct node *head); struct node *reverse(struct node *list); struct node *create_node(int data, struct node *next); int length(struct node *head); struct node *last(struct node *head); struct node *append(struct node *head, int value); void free_list(struct node *head); static void check_list(struct node *head, char *name, int original_list_length, struct node *original_nodes[], int original_data_fields[]); #define MAX_LINE 4096 // simple main function to test delete_first, delete_last, delete_contains, reverse int main(int argc, char *argv[]) { char line[MAX_LINE]; struct node *list_head = NULL; while (1) { // save state of of list so we can check student functions // only perform permitted operations int list_length = length(list_head); struct node *nodes[list_length+1]; // ensure non-zero length for VLA int data[list_length+1]; int j = 0; struct node *n = list_head; while (n != NULL) { nodes[j] = n; data[j] = n->data; n = n->next; j++; } printf("list = "); print_list(list_head); printf("\n"); printf("> "); if (fgets(line, MAX_LINE, stdin) == NULL) { // free memory even though program is exiting // so we can check for memory not freed by other functions // by running dcc --leak-check free_list(list_head); return 0; } int i = 0; while (isalpha(line[i]) || line[i] == '_') { i++; } int argument = atoi(&line[i]); line[i] = '\0'; if (strcmp(line, "append") == 0) { list_head = append(list_head, argument); continue; // need to skip check_list } else if (strcmp(line, "count") == 0) { printf("count(%d) returns %d\n", argument, count(argument, list_head)); } else if (strcmp(line, "get_nth") == 0) { struct node *n = get_nth(argument, list_head); if (n == NULL) { printf("get_nth(%d) returned NULL\n", argument); } else { printf("get_nth(%d) returned a pointer to a node containing %d\n", argument, n->data); } } else if (strcmp(line, "delete_nth") == 0) { list_head = delete_nth(argument, list_head); } else if (strcmp(line, "insert_nth") == 0) { // insert a node containing 42 struct node *new_node = create_node(42, NULL); list_head = insert_nth(argument, new_node, list_head); // include new node in nodes given to check_list nodes[list_length] = new_node; data[list_length] = new_node->data; list_length++; } else if (strcmp(line, "delete_odd") == 0) { list_head = delete_odd(list_head); } else if (strcmp(line, "") != 0) { printf("Unknown command: '%s'\n", line); } check_list(list_head, "returned list", list_length, nodes, data); } } // print contents of list in Python syntax void print_list(struct node *head) { printf("["); for (struct node *n = head; n != NULL; n = n->next) { printf("%d", n->data); if (n->next != NULL) { printf(", "); } } printf("]"); } // return pointer to last node in list // NULL is returned if list is empty struct node *last(struct node *head) { if (head == NULL || head->next == NULL) { return head; } return last(head->next); } int length(struct node *head) { int len = 0; for (struct node *n = head; n != NULL; n = n->next) { len++; } return len; } // create a new list node containing value // and append it to end of list struct node *append(struct node *head, int value) { // new node will be last in list, so next field is NULL struct node *n = create_node(value, NULL); if (head == NULL) { // new node is now head of the list return n; } else { // change next field of last list node // from NULL to new node last(head)->next = n; /* append node to list */ return head; } } // Create a new struct node containing the specified data, // and next fields, return a pointer to the new struct node. struct node *create_node(int data, struct node *next) { struct node *n; n = malloc(sizeof (struct node)); if (n == NULL) { fprintf(stderr, "out of memory\n"); exit(1); } n->data = data; n->next = next; return n; } void free_list(struct node *head) { if (head != NULL) { free_list(head->next); free(head); } } // You are not expected to understand the following code. // It uses complex internal compiler features to // print informative messages for student errors. // detect clang address-sanitizer #ifdef __has_feature #if __has_feature(address_sanitizer) // clang address-sanitizer #define HAVE_ASAN #endif #endif // detect gcc address-sanitizer #ifdef __SANITIZE_ADDRESS__ #define HAVE_ASAN #endif #ifdef HAVE_ASAN #include <sanitizer/asan_interface.h> #include <stdint.h> #include <string.h> // return NULL if p appears to be a valid pointer to a malloc'ed region of size size // otherwise return string describing pointer static char *check_address_is_heap_pointer(void *p, size_t size) { if (!p) return NULL; if ((sizeof(p) == 8 && (uintptr_t)p == 0xbebebebebebebebe) || (sizeof(p) == 4 && (uintptr_t)p == 0xbebebebe)) return "uninitialized"; if (__asan_region_is_poisoned(p, size)) return "invalid"; char name[8]; // unused but required by __asan_locate_address void *region_address; size_t region_size; if (strcmp(__asan_locate_address(p, name, sizeof name, ®ion_address, ®ion_size), "heap") != 0) return "invalid (not from malloc)"; return NULL; } // Use address-sanitizer and other methods to detect invalid pointers in a malloc'ed linked list // name should be a string describing the list // If original_nodes != NULL then every node is checked to ensure it is the array original_nodes // If original_data_fields != NULL then every data field is checked to see if matches the element // of original_data_fields at the same index as it node appears in original_nodes // original_nodes and original_data_fields should be of length original_list_length static void check_list(struct node *head, char *name, int original_list_length, struct node *original_nodes[], int original_data_fields[]) { char *pointer_description; if ((pointer_description = check_address_is_heap_pointer(head, sizeof *head))) { fprintf(stderr, "\nError: the head of %s is %s (%p)\n", name, pointer_description, head); exit(1); } int position = 0; for (struct node *n = head; n != NULL; n = n->next, position++) { // If you're getting an error here, // you have returned an invalid list int error = 0; if ((unsigned)n->data == 0xbebebebe) { fprintf(stderr, "Error: %s is invalid.\n", name); fprintf(stderr, " The data field of node %d is uninitialized.\n", position); error = 1; } if ((pointer_description = check_address_is_heap_pointer(n->next, sizeof *(n->next)))) { if (!error) fprintf(stderr, "Error: %s is invalid.\n", name); fprintf(stderr, " The next field of node %d is %s (%p).\n", position, pointer_description, n->next); error = 1; } if (error) { if (position) { fprintf(stderr, " The data fields of nodes 0..%d in the list contain: [", position); for (struct node *m = head; m != n; m = m->next) { fprintf(stderr, "%d, ", m->data); } fprintf(stderr, "%d]\n", n->data); } exit(1); } int position1 = 0; for (struct node *o = head;; o = o->next, position1++) { if (o == n->next) { if (position == position1) { fprintf(stderr, "Error: %s is invalid.\n", name); fprintf(stderr, " The next field of node %d points to itself\n", position); } else { fprintf(stderr, "Error: %s is invalid.\n", name); fprintf(stderr, " The next field of node %d points to node %d.\n", position, position1); fprintf(stderr, " In other words, %s is circular.\n", name); } exit(1); } if (o == n) break; } if (original_list_length && original_nodes) { int i; for (i = 0; i < original_list_length; i++) { if (original_nodes[i] == n) break; } if (i == original_list_length) { fprintf(stderr, "Error: %s is invalid.\n", name); fprintf(stderr, " The node in position %d is not in the list it was given.\n", position); fprintf(stderr, " Do not create new nodes with malloc\n"); exit(1); } if (original_data_fields && original_data_fields[i] != n->data) { fprintf(stderr, "Error: %s is invalid.\n", name); fprintf(stderr, " The node in position %d data field has been changed from %d to %d.\n", position, original_data_fields[i], n->data); fprintf(stderr, " Do not change the data fields of nodes\n"); exit(1); } } } } #else static void check_list(struct node *head, char *name, int original_list_length, struct node *original_nodes[], int original_data_fields[]) { } #endifA complete recursive solution for
lab13.c
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> struct node { struct node *next; int data; }; // Return number of nodes in the list containing value. int count(int value, struct node *head) { if (head == NULL) { return 0; } if (head->data == value) { return 1 + count(value, head->next); } else { return count(value, head->next); } } // less readable but more concise version of count // check your understanding of C by figuring out how it works int count1(int value, struct node *head) { if (head == NULL) { return 0; } else { return ((head->data == value) + count(value, head->next)); } } // a very concise version that uses C's ternary operator // much less readable int count2(int value, struct node *head) { return (head == NULL) ? 0 : ((head->data == value) + count(value, head->next)); } // Return a pointer to the node in position n in the list. // Position 0 is the first node in the list. // Return NULL if the list has no n-th node. struct node *get_nth(int n, struct node *head) { if (head == NULL) { return NULL; } if (n == 0) { return head; } return get_nth(n - 1, head->next); } // Delete the node in position n in the list. // the deleted node is freed. // The first node in the list is in position 0. // Do nothing if there is no position n in the list. // The head of the list is returned. struct node *delete_nth(int n, struct node *head) { if (head == NULL) { return NULL; } if (n == 0) { struct node *new_head = head->next; free(head); return new_head; } head->next = delete_nth(n - 1, head->next); return head; } // Delete all nodes in the list containing odd numbers. // Any deleted nodes are freed. // The head of the list is returned. struct node *delete_odd(struct node *head) { if (head == NULL) { // list is empty no node to delete return NULL; } if (head->data % 2 == 1) { struct node *new_head = delete_odd(head->next); free(head); return new_head; } head->next = delete_odd(head->next); return head; } // Insert new_node before position n in the list. // The first node in the list is in position 0. // If n == length of the list, new_node is appended to list. // Otherwise do nothing if there is no position n in the list. // The head of the list is returned. struct node *insert_nth(int n, struct node *new_node, struct node *head) { if (n == 0) { new_node->next = head; return new_node; } if (head == NULL) { return NULL; } head->next = insert_nth(n - 1, new_node, head->next); return head; } // THE CODE BELOW HERE IS TO TEST YOUR FUNCTIONS // DO NOT CHANGE IT void print_list(struct node *head); struct node *reverse(struct node *list); struct node *create_node(int data, struct node *next); int length(struct node *head); struct node *last(struct node *head); struct node *append(struct node *head, int value); void free_list(struct node *head); static void check_list(struct node *head, char *name, int original_list_length, struct node *original_nodes[], int original_data_fields[]); #define MAX_LINE 4096 // simple main function to test delete_first, delete_last, delete_contains, reverse int main(int argc, char *argv[]) { char line[MAX_LINE]; struct node *list_head = NULL; while (1) { // save state of of list so we can check student functions // only perform permitted operations int list_length = length(list_head); struct node *nodes[list_length+1]; // ensure non-zero length for VLA int data[list_length+1]; int j = 0; struct node *n = list_head; while (n != NULL) { nodes[j] = n; data[j] = n->data; n = n->next; j++; } printf("list = "); print_list(list_head); printf("\n"); printf("> "); if (fgets(line, MAX_LINE, stdin) == NULL) { // free memory even though program is exiting // so we can check for memory not freed by other functions // by running dcc --leak-check free_list(list_head); return 0; } int i = 0; while (isalpha(line[i]) || line[i] == '_') { i++; } int argument = atoi(&line[i]); line[i] = '\0'; if (strcmp(line, "append") == 0) { list_head = append(list_head, argument); continue; // need to skip check_list } else if (strcmp(line, "count") == 0) { printf("count(%d) returns %d\n", argument, count(argument, list_head)); } else if (strcmp(line, "get_nth") == 0) { struct node *n = get_nth(argument, list_head); if (n == NULL) { printf("get_nth(%d) returned NULL\n", argument); } else { printf("get_nth(%d) returned a pointer to a node containing %d\n", argument, n->data); } } else if (strcmp(line, "delete_nth") == 0) { list_head = delete_nth(argument, list_head); } else if (strcmp(line, "insert_nth") == 0) { // insert a node containing 42 struct node *new_node = create_node(42, NULL); list_head = insert_nth(argument, new_node, list_head); // include new node in nodes given to check_list nodes[list_length] = new_node; data[list_length] = new_node->data; list_length++; } else if (strcmp(line, "delete_odd") == 0) { list_head = delete_odd(list_head); } else if (strcmp(line, "") != 0) { printf("Unknown command: '%s'\n", line); } check_list(list_head, "returned list", list_length, nodes, data); } } // print contents of list in Python syntax void print_list(struct node *head) { printf("["); for (struct node *n = head; n != NULL; n = n->next) { printf("%d", n->data); if (n->next != NULL) { printf(", "); } } printf("]"); } // return pointer to last node in list // NULL is returned if list is empty struct node *last(struct node *head) { if (head == NULL || head->next == NULL) { return head; } return last(head->next); } // return length of list int length(struct node *head) { if (head == NULL) { return 0; } return 1 + length(head->next); } // create a new list node containing value // and append it to end of list struct node *append(struct node *head, int value) { // new node will be last in list, so next field is NULL struct node *n = create_node(value, NULL); if (head == NULL) { // new node is now head of the list return n; } else { // change next field of last list node // from NULL to new node last(head)->next = n; /* append node to list */ return head; } } // Create a new struct node containing the specified data, // and next fields, return a pointer to the new struct node. struct node *create_node(int data, struct node *next) { struct node *n; n = malloc(sizeof (struct node)); if (n == NULL) { fprintf(stderr, "out of memory\n"); exit(1); } n->data = data; n->next = next; return n; } void free_list(struct node *head) { if (head != NULL) { free_list(head->next); free(head); } } // You are not expected to understand the following code. // It uses complex internal compiler features to // print informative messages for student errors. // detect clang address-sanitizer #ifdef __has_feature #if __has_feature(address_sanitizer) // clang address-sanitizer #define HAVE_ASAN #endif #endif // detect gcc address-sanitizer #ifdef __SANITIZE_ADDRESS__ #define HAVE_ASAN #endif #ifdef HAVE_ASAN #include <sanitizer/asan_interface.h> #include <stdint.h> #include <string.h> // return NULL if p appears to be a valid pointer to a malloc'ed region of size size // otherwise return string describing pointer static char *check_address_is_heap_pointer(void *p, size_t size) { if (!p) return NULL; if ((sizeof(p) == 8 && (uintptr_t)p == 0xbebebebebebebebe) || (sizeof(p) == 4 && (uintptr_t)p == 0xbebebebe)) return "uninitialized"; if (__asan_region_is_poisoned(p, size)) return "invalid"; char name[8]; // unused but required by __asan_locate_address void *region_address; size_t region_size; if (strcmp(__asan_locate_address(p, name, sizeof name, ®ion_address, ®ion_size), "heap") != 0) return "invalid (not from malloc)"; return NULL; } // Use address-sanitizer and other methods to detect invalid pointers in a malloc'ed linked list // name should be a string describing the list // If original_nodes != NULL then every node is checked to ensure it is the array original_nodes // If original_data_fields != NULL then every data field is checked to see if matches the element // of original_data_fields at the same index as it node appears in original_nodes // original_nodes and original_data_fields should be of length original_list_length static void check_list(struct node *head, char *name, int original_list_length, struct node *original_nodes[], int original_data_fields[]) { char *pointer_description; if ((pointer_description = check_address_is_heap_pointer(head, sizeof *head))) { fprintf(stderr, "\nError: the head of %s is %s (%p)\n", name, pointer_description, head); exit(1); } int position = 0; for (struct node *n = head; n != NULL; n = n->next, position++) { // If you're getting an error here, // you have returned an invalid list int error = 0; if ((unsigned)n->data == 0xbebebebe) { fprintf(stderr, "Error: %s is invalid.\n", name); fprintf(stderr, " The data field of node %d is uninitialized.\n", position); error = 1; } if ((pointer_description = check_address_is_heap_pointer(n->next, sizeof *(n->next)))) { if (!error) fprintf(stderr, "Error: %s is invalid.\n", name); fprintf(stderr, " The next field of node %d is %s (%p).\n", position, pointer_description, n->next); error = 1; } if (error) { if (position) { fprintf(stderr, " The data fields of nodes 0..%d in the list contain: [", position); for (struct node *m = head; m != n; m = m->next) { fprintf(stderr, "%d, ", m->data); } fprintf(stderr, "%d]\n", n->data); } exit(1); } int position1 = 0; for (struct node *o = head;; o = o->next, position1++) { if (o == n->next) { if (position == position1) { fprintf(stderr, "Error: %s is invalid.\n", name); fprintf(stderr, " The next field of node %d points to itself\n", position); } else { fprintf(stderr, "Error: %s is invalid.\n", name); fprintf(stderr, " The next field of node %d points to node %d.\n", position, position1); fprintf(stderr, " In other words, %s is circular.\n", name); } exit(1); } if (o == n) break; } if (original_list_length && original_nodes) { int i; for (i = 0; i < original_list_length; i++) { if (original_nodes[i] == n) break; } if (i == original_list_length) { fprintf(stderr, "Error: %s is invalid.\n", name); fprintf(stderr, " The node in position %d is not in the list it was given.\n", position); fprintf(stderr, " Do not create new nodes with malloc\n"); exit(1); } if (original_data_fields && original_data_fields[i] != n->data) { fprintf(stderr, "Error: %s is invalid.\n", name); fprintf(stderr, " The node in position %d data field has been changed from %d to %d.\n", position, original_data_fields[i], n->data); fprintf(stderr, " Do not change the data fields of nodes\n"); exit(1); } } } } #else static void check_list(struct node *head, char *name, int original_list_length, struct node *original_nodes[], int original_data_fields[]) { } #endif
They do not get marked.
There is no need to submit them with give.