code :

/************************************************** * CS 305 * Lab on linked lists * Implements a linked list of ints and some operations * on the list * Authors: Tammy VanDeGrift, Martin Cenek **************************************************/ #include #include typedef struct nodeTag Node; /* similar to the textbook -- a Node represents one node in the linked list */ struct nodeTag { int num; // value stored in node Node * next; // pointer to next node in list }; // book also defines Node * as NodePtr // A better practice is to use type Node * instead of NodePtr for the reminder // of the pointer type /* function prototypes on linked lists from lecture */ Node * makeNode(int n, Node * nextItem); int length(Node * list); void print(Node * list); void insertTail(int n, Node ** list); Node * find(int n, Node * list); int delete(Node * toDelete, Node ** listPtr); void insertHead(int n, Node ** list); int numPos(Node * list); /* function prototypes on linked lists for lab */ int lengthRec(Node * list); void freeList(Node * list); Node * copyList(Node * list); Node * mergeList(Node * list1, Node * list2); /* main function */ int main(void) { // LAB EXERCISE: update main to test the new functions Node * lst1 = NULL; Node * lst2 = NULL; insertHead(8, &lst1); insertHead(7, &lst1); insertHead(5, &lst1); insertHead(4, &lst1); printf("lst1 length: %d ", length(lst1)); printf("lst1 length (rec): %d ", lengthRec(lst1)); insertHead(25, &lst2); insertHead(21, &lst2); insertHead(20, &lst2); insertHead(15, &lst2); insertHead(13, &lst2); printf("lst2 length: %d ", length(lst2)); printf("lst2 length (rec): %d ", lengthRec(lst2)); Node * mergedList = mergeList(lst1, lst2); freeList(lst1); freeList(lst2); freeList(mergedList); return EXIT_SUCCESS; } /*********** function definitions new for lab *****/ /* lengthRec * parameter -- list * returns the length of the list (# nodes) */ int lengthRec(Node * list) { if(list == NULL) { return 0; } else { // LAB EXERCISE 1: complete this recursive function call return 0; // delete stub } } /* freeList * parameter -- list * frees all nodes in the list */ void freeList(Node * list) { if(list == NULL) { return; } else { // LAB EXERCISE 2: complete the function so that it recursively // frees list->next and then frees the list } } /* copyList * parameter -- list * returns a copy of the list */ Node * copyList(Node * list) { Node * ret = NULL; if(list == NULL) { return NULL; } else { // LAB EXERCISE 3: complete the function so that it makes a new // node and recusively copies the rest of the list // use makeNode, the second argument to makeNode can be a // recursive call to copyList, since copyList returns a pointer // to a Node return NULL; // delete stub } } /* mergeList * parameters: list1 and list 2 * merges the two lists, keeping the values in ascending order * NOTE: only works if list1 and list2 are sorted */ Node * mergeList(Node * list1, Node * list2) { if (list1 == NULL) { return copyList(list2); } else if (list2 == NULL) { return copyList(list1); } else if (list1->num num) { // LAB EXERCISE 4: complete this recursive case to that it makes // a new node and recursively merges the two lists as the // second argument return NULL; // delete stub } else { // LAB EXERCISE 4: complete this recursive case return NULL; // delete stub } } /********************* function definitions from lecture ****/ /* makeNode * parameters -- n (the number to store in the node) * -- nextItem (the next link of the node) * slightly different than textbook version */ Node * makeNode(int n, Node * nextItem) { Node * ret = (Node * ) malloc(sizeof(Node)); ret->num = n; ret->next = nextItem; return ret; } /* length * parameter -- list (the linked list) * returns the length (# nodes) in the linked list * implemented iteratively */ int length(Node * list) { int len = 0; while(list != NULL) { len++; list = list->next; } return len; } /* print * parameter -- list (the linked list) * prints the values of the nodes (in order) of the list */ void print(Node * list) { printf("Linked list contents: "); while(list != NULL) { printf("%d ", list->num); list = list->next; } printf(" "); } /* insertTail * parameters -- n (the value of the node to insert) * -- list (the linked list) * inserts new node at the end with value n * note: this is done by passing the pointer to list, so * when the function returns, the list object that was * passed to this function has been altered */ void insertTail(int n, Node ** listPtr) { Node * list = *listPtr; if(list == NULL) { // create a 1-node list *listPtr = makeNode(n, NULL); return; } while(list != NULL) { if(list->next == NULL) { // insert new node here since we found the last node list->next = makeNode(n, NULL); return; } list = list->next; } } /* find * parameters -- n (the value to search for) * -- list (the linked list) * returns a pointer to the first node found with value n * if no such value is found, returns NULL */ Node * find(int n, Node * list) { while(list != NULL) { if(list->num == n) { return list; } list = list->next; } // no node with value n found return NULL; // or could return list, since list has value NULL } /* delete * parameters -- toDelete (the node to find and delete) * -- listPtr (pointer to the list) * note: must pass listPtr in case the first element of the list * is deleted -- passing the list by reference, so the address * to the first item in the list can get updated if necessary * * returns 0 if no item found and deleted * returns 1 if a node is deleted */ int delete(Node * toDelete, Node ** listPtr) { Node * list = *listPtr; // list is the linked list // case: either toDelete or list is null -- will not be deleting if(toDelete == NULL || list == NULL) { return 0; // indicates no change to the list } // special case: toDelete is first node in list if(toDelete == list) { *listPtr = list->next; // now list->next becomes first node in list // returning new first address via pointer free(toDelete); return 1; // indicates that a node was deleted } // case: need to find toDelete somewhere other than first node in list Node * before = list; list = list->next; while(list != NULL) { if(toDelete == list) { // redo pointers and then free memory before->next = list->next; free(list); return 1; } before = list; // update for next iteration list = list->next; } return 0; // toDelete not found } /* insertHead * parameters -- n (the value of the new node) * -- listPtr (a pointer to the linked list for the insertion) * * inserts the new node at the front of the list */ void insertHead(int n, Node ** listPtr) { // create new node *listPtr = makeNode(n, *listPtr); } /* numPos * parameters -- list (list to search) * * returns the number of positive ints in the list */ int numPos(Node * list) { int countPos = 0; if(list == NULL) { return 0; } while(list != NULL) { if(list->num > 0) { countPos++; } list = list->next; } return countPos; }

Part 2: lengthRec Fix the recursive case 1. Examine the lengthRec function definition. This function is supposed to return the number of nodes in the linked list. An iterative version of length is defined later in the file. This one, however, is supposed to be recursive. Update the "else" case so that it recursively calls lengthRec on list-next and returns this function call plus 1. (one line of code) 2. In the main function, update the code to update the contents of 1stl so that it has 5 nodes where the values of the nodes are in ascending order. 3. In the main function, write the code to update the contents of 1st2 so that it has 8 nodes where the values of the nodes are in ascending order. Have some of these values be the same as values in Istl and have some be different. Print the list. 4. Compile and run your code. gcc -o link_list link_list_lab.c link list If you want to use the debugger, include the -g flag when compiling Part 3: freeList - Fix the recursive case (switch driver) 1. Examine the freeList function. The function should be recursive. It should recursively free list-next and then free the list. (Two lines of code) 2. The function call to free Istl and Ist2 are already in main. Compile and run your code. 3. Why must list-next be free'ed before list? Part 2: lengthRec Fix the recursive case 1. Examine the lengthRec function definition. This function is supposed to return the number of nodes in the linked list. An iterative version of length is defined later in the file. This one, however, is supposed to be recursive. Update the "else" case so that it recursively calls lengthRec on list-next and returns this function call plus 1. (one line of code) 2. In the main function, update the code to update the contents of 1stl so that it has 5 nodes where the values of the nodes are in ascending order. 3. In the main function, write the code to update the contents of 1st2 so that it has 8 nodes where the values of the nodes are in ascending order. Have some of these values be the same as values in Istl and have some be different. Print the list. 4. Compile and run your code. gcc -o link_list link_list_lab.c link list If you want to use the debugger, include the -g flag when compiling Part 3: freeList - Fix the recursive case (switch driver) 1. Examine the freeList function. The function should be recursive. It should recursively free list-next and then free the list. (Two lines of code) 2. The function call to free Istl and Ist2 are already in main. Compile and run your code. 3. Why must list-next be free'ed before list