For this assignment you will make a Recursion class with two

For this assignment you will make a Recursion class with two recursive member functions.

a) Implement the recursive binSearchRec algorithmn.

Sort by year then call a recursive function to do a binary search which lists out all vehicle information for a user input year.

then

Sort by make then call a recursive function to do a binary search which lists out all vehicle information for a user input make.

then

Sort by model then call a recursive function to do a binary search which lists out all vehicle information for a user input model.

Then do these same 3 Searches for an input (year, make, model), but use loops instead of a recursive function.

b)Implement a member function with the same functional requirements, except instead of a recursive member function, use an iterative (non-recursive) binarySearchIter. Your iterative function should produce the same results as your recursive function.

This c++ language

Can someone help me on this problem?

Solution

Code:

#include<iostream>
#include<string>
#include<vector>
#include<fstream>
using namespace std;
#include<stdlib.h>

struct vehicle
{
int year;
string make;
string model;
};

class BinSearch{

string fileName;
vector<vehicle> veh;

public:

BinSearch(string& fn){ fileName.assign(fn);

}

void binSearchRec(int year);
void binRecSearch(int year,int first,int last);
void binSearchIter(int year);

void readFile();
void print();
void sort();

};

void BinSearch::readFile()
{
vehicle v;

std::fstream ifs;
ifs.open(this->fileName.c_str());

if(!ifs.is_open()){
   cout<<\"Error in opening file\"<<endl;
   return;
}

string str;

while(!ifs.eof()){

  
   ifs>>str;

   if(str!=\"|\")
   {
       v.year=atoi(str.c_str());
       ifs>>v.make;
       ifs>>v.model;
       this->veh.push_back(v);
   }
}

ifs.close();

}

void BinSearch::sort()
{

int size=this->veh.size();

vehicle tmp;
for(int i=0;i<size-1;i++)
{
   for(int j=0;j<size-i-1;j++)
   {
       if(this->veh[j].year > this->veh[j+1].year)
       {
           tmp.year=this->veh[j].year;
           tmp.make=this->veh[j].make;
           tmp.model=this->veh[j].model;

           this->veh[j].year=this->veh[j+1].year;
           this->veh[j].make=this->veh[j+1].make;
           this->veh[j].model=this->veh[j+1].model;
          
          
           this->veh[j+1].year=tmp.year;
           this->veh[j+1].make=tmp.make;
           this->veh[j+1].model=tmp.model;
       }
   }
}

}
void BinSearch::print(){

for(vector<vehicle>::iterator iter=this->veh.begin();iter!=this->veh.end();iter++)
{
   cout<<\"Year:\"<<iter->year<<endl;
   cout<<\"Make:\"<<iter->make<<endl;
   cout<<\"Model:\"<<iter->model<<endl;
   cout<<\"*******************************\"<<endl;
}

}

void BinSearch::binSearchIter(int year){

int size=this->veh.size();
int first=0;
int last=size;
int middle=(first+last)/2;

cout<<\"Middle:\"<<middle<<endl;

while(first<=last){

   if(year>this->veh[middle].year)
   {
       first=middle;
   }
   else if(year<this->veh[middle].year)
   {
       last=middle;
   }
   else if(year==this->veh[middle].year)
   {
       cout<<\"Year found\"<<endl;
       cout<<\"Year:\"<<year<<endl;
       cout<<\"Make:\"<<this->veh[middle].make<<endl;
       cout<<\"Model:\"<<this->veh[middle].model<<endl;
      return;  
   }
   middle=(first+last)/2;
}

if(first>last) cout<<\"Not found\"<<endl;
  
}

void BinSearch::binSearchRec(int year)
{

int first=0;
int last=this->veh.size();

binRecSearch(year,first,last);
}

void BinSearch::binRecSearch(int year,int first,int last)
{

int middle=(first+last)/2;

if(this->veh[middle].year==year) {
       cout<<\"Year found\"<<endl;
       cout<<\"Year:\"<<year<<endl;
       cout<<\"Make:\"<<this->veh[middle].make<<endl;
       cout<<\"Model:\"<<this->veh[middle].model<<endl;
   }
else if(year < this->veh[middle].year)
{
   binRecSearch(year,first,middle);
}
else if(year > this->veh[middle].year)
   binRecSearch(year,middle,last);
else
{
   cout<<\"Element not found\"<<endl;
   return;
}
}

int main(void)
{

string fn(\"vehicle.txt\");
BinSearch bin(fn);

bin.readFile();
//bin.print();
bin.sort();
/*cout<<\"====================================\"<<endl;
cout<<\"After Sort:\"<<endl;
cout<<\"====================================\"<<endl;
bin.print();
*/
bin.print();
bin.binSearchIter(2012);
bin.binSearchRec(2012);
return 0;
}

vehicle.txt:

2010 Ford Escape | 2014 BMW 328xi | 2014 BMW 428xi | 2012 FordFusion SE | 2014 Lamborghini Gallardo |

Output:

Year:2010
Make:Ford
Model:Escape
*******************************
Year:2012
Make:FordFusion
Model:SE
*******************************
Year:2014
Make:BMW
Model:328xi
*******************************
Year:2014
Make:BMW
Model:428xi
*******************************
Year:2014
Make:Lamborghini
Model:Gallardo
*******************************
Middle:2
Year found
Year:2012
Make:FordFusion
Model:SE
Year found
Year:2012
Make:FordFusion
Model:SE