3. An Unsorted Type ADT is to be extended by the addition of function SplitLists, which has the following specifications:
Function: Divides list into two lists according to the key of item.
Preconditions: list has been initialized and is not empty.
Postconditions: list1 contains all the items of list whose keys are less than or equal to items key; list2 contains all the items of list whose keys are greater than items key.
Implement SplitLists as a linked member function of the Unsorted List ADT
5. The specifications for the Unsorted List ADT state that the item to be deleted is in the list.
a. Rewrite the specification for DeleteItem so that the list is unchanged if the item to be deleted is not in the list.
b. Implement DeleteItem as specified in (a) using an array-based.
c. Rewrite the specification for DeleteItem so that all copies of the item to be deleted are removed if they exist.
d. Implement DeleteItem as specified in (c) using an array-based.
6. Redo Exercise 5(b) and 5(d), using a linked implementation.
4. Write a client function that merges two instances of the Sorted list ADT using the following specification:
Function: Merge two sorted lists into a third sorted list.
Precoditions: list1 and list2 have been initialized and are sorted by key using function ComparedTo; list1 and list2 do not have any keys in common.
Postconditions: result is a sorted list that contains all of the items from list1 and list2.
a. Write the prototype for MergeLists.
c. Write the function definition, using a linked implementation.
d. Describe the algorithm in terms of Big-O.
7. The specifications for the Sorted List ADT state that the item to be deleted is in the list.
a. Rewrite the specification for DeleteItem so that the list is unchanged if the item to be deleted is not in the list.
b. Implement DeleteItem as specified in (a) using an array-based.
c. Implement DeleteItem as specified in (a) using a linked implementation.
d. Rewrite the specification for DeleteItem so that all copies of the item to be deleted are removed if they exist.
e. Implement DeleteItem as specified in (d) using an array-based.
f. Implement DeleteItem as specified in (d) using a linked implementation.
18. Implement the following specification for a client Boolean function that returns true if two stacks are identical and false otherwise.
37. Implement the following specification for an integer function in the client program that return the number of items in a queue. The queue is unchanged.
Function: Determines the number of items in the queue.
Precondition: queue has been initialized.
Postcondition: queue in unchanged; Function value = number of items in queue.