hw9starter.cpp Parts.txt P-28690 A 45 19.34 P-34050 B 16 18.99 P-11245 D 45 0.93

Question

hw9starter.cpp
Parts.txt
P-28690 A 45 19.34 P-34050 B 16 18.99 P-11245 D 45 0.93 P-27969 C 2 12.52 P-34512 B 2 69.17 P-20491 B 32 43.2 P-14518 D 9 5.56 P-17243 A 7 69.19 P-19780 A 33 44.66 P-28061 A 38 117.29 P-22844 D 10 0.5 P-23975 D 5 6.84 P-37542 B 39 26.43 P-29182 A 11 26.83 For this homework, write a program that implements searching and sorting functionality on the data contained in the parts.txt file located on Canvas under Week 10 homework. Each row of this file is comprised of four related pieces of data: 1) part number; 2) class; 3) on-hand inventory (number of parts); and 4) cost. Use the starter code hw9starter.cpp, also listed under Week 10 homework, to read in the parts.txt file. Compile the starter code and make sure the program generates the message "Parts file read successfully!" If it doesn't, double check where your copy of the file resides and make sure the function readFile0 is reading from that location. . After the file has been read in, we will be working with the string vector vecPartNum only. The remaining three vectors may be ignored. In your program, implement the following functions: 1. mergeSort0 The pseudocode for this sort function is discussed in Lecture 19 from Wed. 10/25. Note that mergeSort0 requires an additional function merge0 2. linearSearch The code for a linear sequential search with early exit is discussed in Lecture 18 from Mon. 10/23. You may also modify the linearSearch0 function detailed in Chapter 8 (pp. 465) to work with a string vector 3. binarySearch0 The code for a binary search function is given in the course text in Chapter 8 (pp. 497). There are already function prototypes and stubs given in the starter code. If you do not have the course text, then implement your own version of each function in order to perform a linear sequential search with early exit and a binary search on a sorted string vector. Make sure that each search function displays the number of loops performed during the respective search. Implement a user-input loop in your code to continually prompt the user for a search key until a sentinel value of your choice is entered. Perform a binary and linear search of the vecPartNum string vector using the user specified key. Make sure to report the index where a search key was found, or that it was not found. A sample program exec ution is shown in the figure on the next page. For full credit on this assignment, make sure to include: 1. Fully implemented mergeSort0, merge0, linearSearch0, and binarySearch0 functions.

Explanation / Answer

#include<iostream>
#include<fstream>
#include<string>
#include<vector>

using namespace std;

// Function prototype
bool readFile(vector<string> &, vector<char> &, vector<int> &, vector<double> &);
void mergeSort(vector<string> &, vector<char> &, vector<int> &, vector<double> &, int, int);
void merge(vector<string> &, vector<char> &, vector<int> &, vector<double> &, int, int, int);
int binarySearch(const vector<string> &, string);
int linearSearch(const vector<string> &, string);

// Program entry point
int main()
{
// Define several vectors to hold parts information
vector<string> vecPartNumber;
vector<char> vecClass;
vector<int> vecOHB;
vector<double> vecCost;

// First, read in parts file and report the status
bool bFileOK = readFile(vecPartNumber, vecClass, vecOHB, vecCost);
// Checks whether file is opened successfully or not
if(bFileOK)
{
cout<<" Parts file read successfully!";

// Add sort part number vector
mergeSort(vecPartNumber, vecClass, vecOHB, vecCost, 0, vecPartNumber.size() - 1);
// Loops till end of vecPartNumber
for(int i = 0; i < vecPartNumber.size(); i++)
{
// Displays the information
cout<<" "<<vecPartNumber[i]<<" "<<vecClass[i]<<" "<<vecOHB[i]<<" "<<vecCost[i];
} // End of for loop
}// End of if condition
// Otherwise display error message unable to open the file
else
{
cout<<" Unable to read parts file!";
}// End of else

// As long as the file was read successfully, do the user-input loop to continually compare searches
if(bFileOK)
{
string stKey;
int nRet = -1;
// Loops till stKey is not -1
do
{
// Accepts the search key
cout<<" Enter the search query: ";
cin>>stKey;

// Perform both a binary and linear search here based on the user-defined key
// make sure both functions return the number of iterations
if(stKey != "-1")
{
// Calls the function for binary search
cout<<" Performs binary search.....";
nRet = binarySearch(vecPartNumber, stKey);
// Checks the return result if it is not -1 displays the index position
if(nRet != -1)
cout<<" Part found at index "<<nRet;
// Otherwise not found
else
cout<<" Part not found";

// Calls the function for linear search
cout<<" Performing linear search.....";
nRet = linearSearch(vecPartNumber, stKey);
// Checks the return result if it is not -1 displays the index position
if(nRet != -1)
cout<<" Part found at index "<<nRet;
// Otherwise not found
else
cout<<" Part not found";
}// End of inner if condition
}while(stKey != "-1");
}// End of outer if condition
return 0;
}// End of function

// Performs binary search with given key on the specified vector
int binarySearch(const vector<string> &name, string key)
{
// Loop through each element of the input vector until key is found or size limit is reached
int nLoop = 0;
int return_val = -1;
//Local variable to store starting , end and middle index position of the array
int Beg, End, Mid;
//Initializes the variables to zero
Beg = 0;
//Set the end to length of the array minus one because the starting index position of the array is zero
End = name.size();
//Loops till begin is less than or equals to end position
while(Beg <= End)
{
// Increase the counter for number of iteration
nLoop++;
//Calculates the mid index position
Mid = (Beg + End) / 2;
//Checks if the search number is equal to array mid index position value
if(key == name[Mid])
{
return_val = Mid;
break;
}//End of if condition
//Checks if the search number is less than the array mid index position value
else if(key < name[Mid])
//Set the end to mid minus one because mid index position is already considered above
//Array is sorted in ascending order so number is available in the second half part of the array
End = Mid - 1;
//Otherwise the search number is greater than the array mid index position value
else
//Set the beginning to mid plus one because mid index position is already considered above
//Array is sorted in ascending order so number is available in the first half part of the array
Beg = Mid + 1;
}//End of while loop

// Report the number of loops performed
cout<<" Search complete in: "<<nLoop<<" iterations.";
return return_val;
}// End of function

// Performs sequential search with given key on the specified vector
int linearSearch(const vector<string> &pn, string key)
{
// Set up index variable, return value, and boolean test variable
int i = 0, return_val;
bool found = false;

// Loop through each element of the input vector until key is found or size limit is reached
int nLoop = 0;
// Loops till end of pn
while(!found && i < pn.size() && key >= pn[i])
{
// Increase the counter for number of iteration
nLoop++;
// Checks if the key value is equals to the pn i index position value
if(key == pn[i])
// Set true to found
found = true;
// Otherwise increase the loop control variable i by one
else
i++;
}// End of while loop

// Report the number of loops performed
cout<<" Search complete in: "<<nLoop<<" iterations.";

// Determine the appropriate return value
if(found)
return_val = i;
else
return_val = -1;

return return_val;
}// End of function

// Read in the parts file and report status of read
bool readFile(vector<string> & vecNumber, vector<char> &vecClass, vector<int> &vecOHB, vector<double> &vecCost)
{
// Return value
bool bRet = false;

//Starts with the fresh set of vectors
vecNumber.clear();
vecClass.clear();
vecOHB.clear();
vecCost.clear();

// File stream variable
ifstream fin;

// Open the parts file
fin.open("Parts1.txt");

// Check that it opened properly
if(fin.is_open())
{
// Set true to bRect
bRet = true;
}

// No need to read the file if it was not opened!
string tmpNum;
char tmpClass;
int tmpOHB;
double tmpCost;
// If bRect is true file is success fully opened start reading
if(bRet)
{
// Loops till end of the file
do
{
// Read the contents of file and stores it in the variable
fin>>tmpNum;
// Push the variable data to the vector
vecNumber.push_back(tmpNum);
fin>>tmpClass;
vecClass.push_back(tmpClass);
fin>>tmpOHB;
vecOHB.push_back(tmpOHB);
fin>>tmpCost;
vecCost.push_back(tmpCost);
}while(!fin.eof());
}// End of if condition
// Close the file and return the status of the file open
fin.close();
return bRet;
}// End of function

// Perform merge sort on an input vectors
// v for vecNumber, vc for vectorClass, ohb for vecOHB, co for vecCost,
// start for starting position of vector and end for ending position of vector
void mergeSort(vector<string> &v, vector<char> &vc, vector<int> &ohb, vector<double> &co, int start, int end)
{
// Checks if start is less then end
if (start < end)
{
// Same as (l+r)/2, but avoids overflow for large l and h
int mid = start + (end - start) / 2;

// Sort first and second halves
mergeSort(v, vc, ohb, co, start, mid);
mergeSort(v, vc, ohb, co, mid + 1, end);
// Calls the function to merge the halves
merge(v, vc, ohb, co, start, mid, end);
}// End of if condition
}// End of function

// Perform a merge between left and right sub array
// v for vecNumber, vc for vectorClass, ohb for vecOHB, co for vecCost,
// start for starting position of vector, mid for middle position of vector and end for ending position of vector
void merge(vector<string> &v, vector<char> &vc, vector<int> &ohb, vector<double> &co, int start, int mid, int end)
{
int i, j, k;
int n1 = mid - start + 1;
int n2 = end - mid;

// Creates temporary arrays
string LNum[n1], RNum[n2];
char LClass[n1], RClass[n2];
int LOHB[n1], ROHB[n2];
double LCost[n1], RCost[n2];

// Copy data to temporary arrays left and right sub array
// Loops till n1
for (i = 0; i < n1; i++)
{
LNum[i] = v[start + i];
LClass[i] = vc[start + i];
LOHB[i] = ohb[start + i];
LCost[i] = co[start + i];
}// End of for loop
// Loops till n2
for (j = 0; j < n2; j++)
{
RNum[j] = v[mid + 1 + j];
RClass[j] = vc[mid + 1 + j];
ROHB[j] = ohb[mid + 1 + j];
RCost[j] = co[mid + 1 + j];
}// End of for loop

// Merge the temp arrays back into v[l..r]
i = 0; // Initial index of first sub-array
j = 0; // Initial index of second sub-array
k = start; // Initial index of merged sub-array
// Loops till i is less than n1 and j is less than n2
while (i < n1 && j < n2)
{
// Checks if the left array part number value at index position i is less than or equals to the right array part number value
if (LNum[i] <= RNum[j])
{
// Store the array contents i index position value in the respective vectors k index position which is start
v[k] = LNum[i];
vc[k] = LClass[i];
ohb[k] = LOHB[i];
co[k] = LCost[i];
// Increase the counter i by one
i++;
}// End of if condition
// Otherwise
else
{
// Store the array contents j index position value in the respective vectors k index position which is start
v[k] = RNum[j];
vc[k] = RClass[j];
ohb[k] = ROHB[j];
co[k] = RCost[j];
// Increase the counter j by one
j++;
}// End of else
// Increase the counter k by one
k++;
}// End of while

// Copy the remaining elements of Left arrays, if any
while (i < n1)
{
// Store the array contents i index position value in the respective vectors k index position which is start
v[k] = LNum[i];
vc[k] = LClass[i];
ohb[k] = LOHB[i];
co[k] = LCost[i];
// Increase the counter i by one
i++;
// Increase the counter k by one
k++;
}// End of while

// Copy the remaining elements of R[], if there are any
while (j < n2)
{
// Store the array contents j index position value in the respective vectors k index position which is start
v[k] = RNum[j];
vc[k] = RClass[j];
ohb[k] = ROHB[j];
co[k] = RCost[j];
// Increase the counter j by one
j++;
// Increase the counter k by one
k++;
}// End of while
}// End of method

Sample Run:

Parts file read successfully!
P-11245 D 45 0.93
P-14518 D 9 5.56
P-17243 A 7 69.19
P-19780 A 33 44.66
P-20491 B 32 43.2
P-22844 D 10 0.5
P-23975 D 5 6.84
P-27969 C 2 12.52
P-28061 A 38 117.29
P-28690 A 45 19.34
P-29182 A 11 26.83
P-34050 B 16 18.99
P-34512 B 2 69.17
P-37542 B 39 26.43
Enter the search query: P-11245

Performs binary search..... Search complete in: 4 iterations.
Part found at index 0
Performing linear search..... Search complete in: 1 iterations.
Part found at index 0
Enter the search query: P-2245

Performs binary search..... Search complete in: 4 iterations.
Part not found
Performing linear search..... Search complete in: 5 iterations.
Part not found
Enter the search query: P-28609

Performs binary search..... Search complete in: 4 iterations.
Part not found
Performing linear search..... Search complete in: 9 iterations.
Part not found
Enter the search query: P-37542

Performs binary search..... Search complete in: 3 iterations.
Part found at index 13
Performing linear search..... Search complete in: 14 iterations.
Part found at index 13
Enter the search query: -1

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.