CS1XC3-Assignment 6 Linked Lists Solved

Write a C program that manipulates linked lists. 

 Requirements
As starter code for this assignment, use the C code contained in as6_starter_code.zip file found on Avenue to Learn accompanying this assignment.

This starter code contains the same linked list type used in lectures and labs, and the same set of functions for working with linked lists that we created together in lecture and lab.  The starter code also contains the following function declarations:

 

// Functions to implement (merge_sorted_lists is a bonus, it is not required) void add_lists(Node *list1, Node *list2); 

Node *duplicate_list(Node *head); 

Node *efficient_delete_match(Node *head, int delete_value, int *num_deleted); Node *merge_sorted_lists(Node *list1, Node *list2); 

 

This assignment requires you to implement the add_lists, duplicate_list and

efficient_delete_match functions; requirements are described below.  The merge_sorted_lists function is an optional bonus that you can choose to complete or not, it is not required for full marks.  Test code is provided in the main function to help you determine when your function is working correctly, and to clarify any confusion about the requirements provided below.

The function add_lists should add the value of each node contained in the same position in the lists together and store the result as the new value of list1’s node at that position.  If list1 is shorter than list2 or vice versa, than for nodes past the shorter of the two lists no addition needs to occur (and list1 should remain the same for these nodes).  Use recursion to create this function (though not required, the function body can be created with 3 lines of code).

The function duplicate_list should create a new list on the heap that is a duplicate of the input list provided as an argument.  The duplicate list should have the same number of nodes as the input list, and each node at each position in the list should have the same value as the node in the input list at that position in the input list.  The function should return a pointer to the head of this new list.

The function efficient_delete_match should delete any nodes from the list that have a value matching the argument delete_value and it should count the number of deletions that have occurred with num_deleted (a pass-by-reference parameter).  The function should return a pointer to the (potentially different) head of the resulting list (which could even be NULL/empty).  The function should result in the same resulting list, and same num_deleted value, as the delete_all_matches function that we created in-class.   

However the delete_all_matches function was inefficient... it works by repeatedly calling delete_first_match until no matches are found.  The delete_first_match function traverses the list until the first match is found, and so if we repeatedly call the function, we are traversing the list again and again.  Your efficient_delete_match function should traverse the list only once.  You can use multiple loops in your code if like, perhaps traversing a portion of the list, and then another portion of the list, but your code should not repeatedly traverse the same elements of the list.  The delete_duplicates function may be helpful as inspiration for how to achieve this.  As a result, the performance should be vastly improved compared to delete_all_matches, and test code is provided to demonstrate this.

You can use any of the functions we created in lecture and in lab to help you create the above functions.

 

Bonus – 
You can optionally create the merge_sorted_lists function too for up to 10 bonus marks.  This function should accept two sorted lists as input (sorted from lowest to highest values).  The function should return a pointer to a list that has been created by merging and connecting the nodes in the two lists to form a new list that is also sorted from lowest to highest.  The new list should contain all of the nodes that are in both lists, what should be different is how the nodes point to each other in order to form one merged list.   

The function should not create any nodes (i.e. create a new list on the heap entirely using the values from the two previous lists).  No new nodes should be created on the heap.  The pointers of the existing lists should be re-arranged to form one new merged list that is ordered from lowest to highest.