Question

Class SortedList

{

Public:

SortedType();

int getLength(); //returns size of the list

void putItem(Itemtype item); //inserts an item

Itemtype getNextItem(); //returns the next item pointed by the index

void deleteItem(Itemtype item) //deletes a specified item

Private:

int length; //length of the list

Nodetype* listData //head of the list

Nodetype* currentPos; //current pointer to the list

}

Class Itemtype

{

Public:

Itemtype();

int getValue();// returns the value

Private:

int value;

}

struct Nodetype

{

Itemtype info;

Nodetype* next;

}

Add a member function Merge() that has the following precondition and postcondition

1) Precondition: list2 that has been initialized and not empty

2) Postcondition: Insert all the elements to the current list from list2 . Analyze its time complexity in terms of n which is the number of elements in the list2

Answer 1

Sourcecode :

class ExtendedSortedList:public SortedList {

public:

bool isThere(Itemtype item) {

Nodetype temp = listData;

while (temp->next != NULL) {

if (temp->getValue() == item) {

return true;

}

}

return false;

}

};

Time Complexity:

In the worst case (when the element is present at the end), this function takes O time.

Answer 2

1.

Method to be Copied:

//Implement the function
void SortedType::Merge(SortedType list2)
{
   //define the tempp node
   SortedType tempnode();
   //initialize the temp nodes
   NodeType* list1temp = listData;
   //Initalized the list2
   NodeType* list2temp = list2.listData;
   //declare local variable
   int i = 0;
   //check wether the nodes are null or not
   //Repeat the loop until nodes are null
   while (list1temp != NULL && list2.list2temp != NULL)
   {
       //check wether the value is greater than or not
       //if the element is greater in the list1
       if (list1temp->info.getValue() > list2.tmepPtr2->info.getValue())
       {
           //if index is 0
           //merge tge nodes and set the index to next index
           //to add the element
           if (i == 0)
           {
               tempnode.listData = list2.listData;
               tempnode.currentPos = tempnode.listData;
               list2temp = list2temp->next;
               //increment the index
               i++
           }
           //Otherwise the increment the index
           else
           {
               //set the next current node to the second list
               tempnode.currentPos->next = list2temp;
               tempnode.currentPos = tempnode.currentPos->next;
               list2temp = list2temp->next;
               i++;
           }
       }
       //if the element is lesser than the element in the element in the
       //second list then set the data to the end of the list
       else
       {
           if (i == 0)
           {
               tempnode.listData = listData;
               tempnode.currentPos = tempnode.listData;
               list1temp = list1temp->next;
               i++
           }
           else {
               tempnode.currentPos->next = list1temp;
               tempnode.currentPos = tempnode.currentPos->next;
               list1temp = list1temp->next;
               i++;
           }
       }
   }
   //If the list1 elements have more elements of list 2
   while (list1temp != NULL)
   {
       //IF list1 has more element than list2
       tempnode.currentPos->next = list1temp;
       tempnode.currentPos = tempnode.currentPos->next;
       list1temp = list1temp->next;
       i++;
   }
   //If the list2 elements have more elements of list1
   while (list2temp != NULL)
   {
       //IF list2 has more element than list2
       tempnode.currentPos->next = list2temp;
       //set the pointer to the next element
       tempnode.currentPos = tempnode.currentPos->next;
       list2temp = list2temp->next;
       //increment the index
       i++;
   }
   //decrement the length of the temp node
   tempnode.length = --i;
   *this = tempnode;
}