| unsortedtype.h#ifndef UNSORTEDTYPE_H_INCLUDED#define UNSORTEDTYPE_H_INCLUDEDtemplate <class ItemType>class UnsortedType{struct NodeType{ItemType info;NodeType* next;};public:UnsortedType();~UnsortedType();bool IsFull();int LengthIs();void MakeEmpty();void RetrieveItem(ItemType&, bool&);void InsertItem(ItemType); void DeleteItem(ItemType); void ResetList();void GetNextItem(ItemType&); private:NodeType* listData;int length;NodeType* currentPos;};#endif // UNSORTEDTYPE_H_INCLUDEDunsortedtype.cpp#include “unsortedtype.h”#include <iostream>using namespace std;template <class ItemType>UnsortedType<ItemType>::UnsortedType() {length = 0;listData = NULL;currentPos = NULL;}template <class ItemType>int UnsortedType<ItemType>::LengthIs() {return length;}template<class ItemType>bool UnsortedType<ItemType>::IsFull() {NodeType* location;try{location = new NodeType;delete location;return false;}catch(bad_alloc& exception){return true;}} | template <class ItemType>void UnsortedType<ItemType>::InsertItem(ItemType item){NodeType* location;location = new NodeType;location->info = item;location->next = listData;listData = location;length++;}template <class ItemType>void UnsortedType<ItemType>::DeleteItem(ItemType item){NodeType* location = listData;NodeType* tempLocation;if (item == listData->info){tempLocation = location;listData = listData->next;}else{while (!(item==(location->next)->info)) location = location->next;tempLocation = location->next;location->next = (location->next)->next; }delete tempLocation;length–;}template <class ItemType>void UnsortedType<ItemType>::RetrieveItem(ItemType& item, bool& found){NodeType* location = listData;bool moreToSearch = (location != NULL); found = false;while (moreToSearch && !found){if (item == location->info)found = true;else{location = location->next;moreToSearch = (location != NULL); }}}template <class ItemType>void UnsortedType<ItemType>::MakeEmpty(){NodeType* tempPtr;while (listData != NULL){tempPtr = listData;listData = listData->next;delete tempPtr;}length = 0;}template <class ItemType>UnsortedType<ItemType>::~UnsortedType(){MakeEmpty();} |
| template <class ItemType>void UnsortedType<ItemType>::ResetList(){currentPos = NULL;}template <class ItemType>void UnsortedType<ItemType>::GetNextItem(ItemType& item){if (currentPos == NULL)currentPos = listData;elsecurrentPos = currentPos->next;item = currentPos->info;} |
Generate the driver file (main.cpp) where you perform the following tasks. Note that you cannot make any change to the header file or the source file.
| Operation to Be Tested and Description of Action | Input Values |
| • You are given two sequences of integers arranged in ascending order. Your task is to combine the sequences into one ascending sequence. In order to get full marks, you have to make sure that the time complexity of combining two sequences is O(N). You can safely assume that no integer will be repeated. Input starts with a positive integer m which specifies the number of elements in the first sequence. Next m values are the elements in the first sequence. The next positive integer n specifies the number of elements in the second sequence. Next n values are the elements in the second sequence. The output is the combined sequence. | 10 1 5 6 10 14 20 25 31 38 40 12 2 4 7 9 16 19 23 24 32 35 36 42 |
| Expected Output | |
| 1 2 4 5 6 7 9 10 14 16 19 20 23 24 25 31 32 35 36 38 40 42 |
EXPERT ANSWER
The required file main.cpp is given below. followed by the sample input and output provided in the problem description. The explanation of the complex section of code is given with the comment lines in the code itself. In case of any query, you can mention it in the comment section.
CODE:
// driver file
#include<iostream>
#include "unsortedtype.cpp"
using namespace std;
int main(){
UnsortedType<int> l1,l2; // made the two list l1 and l2
int m,n;
cout<<"\nInput: ";
cin>>m;
for(int i=0;i<m;i++){ // take the inputs in both list
int data;
cin>>data;
l1.InsertItem(data);
}
cin>>n;
for(int i=0;i<n;i++){
int data;
cin>>data;
l2.InsertItem(data);
}
// please note that insert item function inserts the new node in first position always, so data inserted in ascending
// will be present their in descending order actually, for ex the first node of l1 will contain data 40 (for the given input)
// so in order to store data ascending in final list, we need to insert in descending order
UnsortedType<int> finalList; // now made a final list to store both in ascending order
int item1,item2; // initialized two variables item1 and item2, item1 will contain data of l1 and item 2 contain l2
int len1=0,len2=0; // len1 and len2 are to take record of how many value is still to be inserted in both list at any point
l1.GetNextItem(item1); // get the first item of both list, as they will be the greatest so the max among these need to be inserted first to get final ascending
l2.GetNextItem(item2);
while(len1<l1.LengthIs() && len2<l2.LengthIs()){ // keep adding untill any one of l1 or l2 finishes
if (item1>item2){ // if item1 is greater than add this and increase the counter of len1
finalList.InsertItem(item1);
len1++;
if (len1<l1.LengthIs()) // if len1 is less than length of l1 that means there are remaining elements in l1 so get the next element
l1.GetNextItem(item1);
}else{ // do same if item2 is greater
finalList.InsertItem(item2);
len2++;
if (len2<l2.LengthIs())
l2.GetNextItem(item2);
}
}
while (len1<l1.LengthIs()){ // if l1 is remaining then add all the elements of l1 to final
finalList.InsertItem(item1);
len1++;
if (len1<l1.LengthIs())
l1.GetNextItem(item1);
}
while (len2<l2.LengthIs()){ // if l2 is remaining then add all its element to final, please note that only one while loop will be executed among these two
finalList.InsertItem(item2);
len2++;
if (len2<l2.LengthIs())
l2.GetNextItem(item2);
}
int item;
int i =0;
cout<<"\nOutput: ";
while (i<finalList.LengthIs()){ // now print the final list
finalList.GetNextItem(item);
cout<<item<<" ";
i++;
}
cout<<endl<<endl;
return 0;
}OUTPUT:
Explanation of complexity: There are three while loops in the in which the first one is main(complexity decider), we can see that there are two variables len1 and len2 initialized with 0 and the while loop runs till len1 is less than length of l1 list and len2 is less than length of l2 list, and in the code it is essential that any one of len1 or len2 incremented each time the loop runs, that means the max time it can run is length (l1) + length(l2) which is linear(O(n)) and remaining two while loops are simple they are also in worst case O(n) so total complexity = O(n).