For the following C++ code, please provide the following... - Justification for
ID: 3825469 • Letter: F
Question
For the following C++ code, please provide the following...
- Justification for selected algorithms.
- Discussion of the time complexity of searching and deleting algorithms in terms
of Big O notation.
- A discussion of the memory efficiency of the used algorithms.
--------------------------- Code--------------------------------------------
#include<iostream>
#include<string>
#include<fstream>
#include <iomanip>
#include <cassert>
using namespace std;
class StateData
{
private:
string myStateName;
string myStateCap;
int myStateUNum;
int myStateJYear;
int myStateAra;
public:
StateData(string myName1 = " ", string capN1 = " ", int uNum1 = 0, int yrN1 = 0, int areaN1 = 0)
{
myStateName = myName1;
myStateCap = capN1;
myStateUNum = uNum1;
myStateJYear = yrN1;
myStateAra = areaN1;
}
string getMyStateName()
{
return myStateName;
}
void setMyStateName(string n)
{
myStateName = n;
}
string getMyStateCap()
{
return myStateCap;
}
void setMyStateCap(string c)
{
myStateCap = c;
}
int getMyStateUNum()
{
return myStateUNum;
}
void setMyStateUNum(int n)
{
myStateUNum = n;
}
int getMyStateJYear()
{
return myStateJYear;
}
void setMyStateJYear(int y)
{
myStateJYear = y;
}
int getMyStateArea()
{
return myStateAra;
}
void setArea(int aa)
{
myStateAra = aa;
}
friend ostream& operator<<(ostream& myOut, StateData& myStateInfo)
{
if (myStateInfo.getMyStateArea() > 0)
{
myOut << myStateInfo.getMyStateName() << " , ";
myOut << myStateInfo.getMyStateCap() << " , ";
myOut << myStateInfo.getMyStateJYear() << ", ";
myOut << myStateInfo.getMyStateUNum() << " , ";
myOut << myStateInfo.getMyStateArea();
}
return myOut;
}
friend istream& operator>>(istream& myIn, StateData& myStateInfo)
{
getline(myIn, myStateInfo.myStateName);
getline(myIn, myStateInfo.myStateCap);
myIn >> myStateInfo.myStateAra >> myStateInfo.myStateJYear >> myStateInfo.myStateUNum;
char myChh;
myIn.get(myChh);
return myIn;
}
StateData& operator=(const StateData& otherStateInfo)
{
myStateName = otherStateInfo.myStateName;
myStateCap = otherStateInfo.myStateCap;
myStateUNum = otherStateInfo.myStateUNum;
myStateJYear = otherStateInfo.myStateJYear;
myStateAra = otherStateInfo.myStateAra;
return *this;
}
//operators overloading
bool operator!=(const StateData& otherStateInfo) const
{
return myStateName != otherStateInfo.myStateName;
}
bool operator==(const StateData& otherStateInfo) const
{
return myStateName == otherStateInfo.myStateName;
}
bool operator>(const StateData& otherStateInfo) const
{
return myStateName > otherStateInfo.myStateName;
}
bool operator>=(const StateData& otherStateInfo) const
{
return myStateName >= otherStateInfo.myStateName;
}
bool operator<(const StateData& otherStateInfo) const
{
return myStateName < otherStateInfo.myStateName;
}
bool operator<=(const StateData& otherStateInfo) const
{
return myStateName <= otherStateInfo.myStateName;
}
};
template <class infoType>
class STATEHASHTABLE
{
private:
infoType *MYHASHTABLE;
int *itemStatus;
int myHashLen;
int myTableSize;
public:
STATEHASHTABLE(int myHashSze= 101)
{
MYHASHTABLE = new infoType[myHashSze];
itemStatus = new int[myHashSze];
for (int kk = 0; kk < myHashSze; kk++) {
itemStatus[kk] = 0;
myTableSize = myHashSze;
myHashLen = 0;
}
}
~STATEHASHTABLE()
{
delete[] MYHASHTABLE;
delete[] itemStatus;
}
int hashFunc(string myStateName);
void displayMystateHashTable() const;
void InsertMyState(int myHashIndx, const infoType& myStateRec);
void getMyState(int myHashIndx, infoType& myStateRec) const;
void searchState(int& myHashIndx, string stateName, bool& myItemFound) const;
bool checkStates(int myHashIndx, const infoType& myStateRec) const;
void clearMyStateInfo(int& myHashIndx, string stateName, bool& myItemFound);
};
template <class infoType>
int STATEHASHTABLE<infoType>::hashFunc(string myStateName)
{
int aa, myHSum;
int len;
aa = 0;
myHSum = 0;
len = myStateName.length();
for (int k = 0; k < 15 - len; k++)
myStateName = myStateName + ' ';
for (int k = 0; k < 5; k++)
{
myHSum = myHSum + static_cast<int>(myStateName[aa]) * 128 * 128
+ static_cast<int>(myStateName[aa + 1]) * 128
+ static_cast<int>(myStateName[aa + 2]);
aa = aa + 3;
}
return myHSum % myTableSize;
}
template <class infoType>
void STATEHASHTABLE<infoType>::InsertMyState(int myHashIndx, const infoType& myStateRec)
{
int incCntt=1;
int myInc=1;
while(itemStatus[myHashIndx] == 1 && incCntt < myTableSize / 2)
{
myHashIndx = (myHashIndx + myInc ) % myTableSize;
myInc = myInc + 2;
incCntt++;
}
if(itemStatus[myHashIndx] != 1)
{
MYHASHTABLE[myHashIndx] = myStateRec;
itemStatus[myHashIndx] = 1;
myHashLen++;
}
else
{
if(MYHASHTABLE[myHashIndx] == myStateRec)
cout<<"Already present"<<endl;
else
cout<<"HASH TABLE FULL"<<endl;
}
}
template <class infoType>
void STATEHASHTABLE<infoType>::searchState(int& myHashIndx, string stateName, bool& myItemFound) const
{
int incCntt=1;
int myInc=1;
while (itemStatus[myHashIndx] != 0 && incCntt < myTableSize / 2)
{
if (MYHASHTABLE[myHashIndx].getMyStateName().compare(stateName) == 0 && itemStatus[myHashIndx] == 1) {
cout<<MYHASHTABLE[myHashIndx]<<endl;
myItemFound = true;
break;
}
myHashIndx = (myHashIndx + myInc) % myTableSize;
incCntt++;
myInc = myInc + 2;
}
}
template <class infoType>
bool STATEHASHTABLE<infoType>::checkStates(int myHashIndx, const infoType& myStateRec) const
{
if (itemStatus[myHashIndx] != 1) {
cout << "EMPTY!" << endl;
return false;
}
return MYHASHTABLE[myHashIndx] == myStateRec;
}
template <class infoType>
void STATEHASHTABLE<infoType>::getMyState(int myHashIndx, infoType& myStateRec) const
{
if (itemStatus[myHashIndx] != 1) {
cout << "EMPTY!" << endl;
}
else
myStateRec = MYHASHTABLE[myHashIndx];
}
template <class infoType>
void STATEHASHTABLE<infoType>::clearMyStateInfo(int& myHashIndx, string stateName, bool& myItemFound)
{
int incCntt=1;
int myInc=1;
while (itemStatus[myHashIndx] != 0 && incCntt < myTableSize / 2)
{
if (MYHASHTABLE[myHashIndx].getMyStateName().compare(stateName) == 0 && itemStatus[myHashIndx] == 1) {
cout<<MYHASHTABLE[myHashIndx]<<endl;
itemStatus[myHashIndx]=0;
myHashLen--;
myItemFound = true;
break;
}
myHashIndx = (myHashIndx + myInc) % myTableSize;
incCntt++;
myInc = myInc + 2;
}
}
template <class infoType>
void STATEHASHTABLE<infoType>::displayMystateHashTable() const
{
for (int kk = 0; kk < myTableSize-1; kk++) {
if (itemStatus[kk] == 1) {
cout << MYHASHTABLE[kk] << endl;
}
}
}
void SearchState()
{
STATEHASHTABLE<StateData> myHashTable(100);
ifstream fID1("Kyles_State_Data.txt");
if(fID1.is_open())
{
StateData myState;
while(fID1)
{
fID1>>myState;
int myIndx=myHashTable.hashFunc(myState.getMyStateName());
myHashTable.InsertMyState(myIndx, myState);
}
fID1.close();
string stateName;
cout<<"Enter myStateName to look into the hash table"<< endl;
cout<<"(Please use Capital letter for first letter of the state)"<< endl;
cout<<"State Name = ";
cin>>stateName;
cout<< endl;
int myIndx=myHashTable.hashFunc(stateName);
bool myItemFound=false;
myHashTable.searchState(myIndx, stateName, myItemFound) ;
if(!myItemFound)
cout<<"Item not Found."<<endl;
}
}
void DeleteState()
{
STATEHASHTABLE<StateData> myHashTable(100);
ifstream fID1("Kyles_State_Data.txt");
if(fID1.is_open())
{
StateData myState;
while(fID1)
{
fID1>>myState;
int myIndx=myHashTable.hashFunc(myState.getMyStateName());
myHashTable.InsertMyState(myIndx, myState);
}
fID1.close();
string stateName;
cout<<"Enter myStateName to delete state info"<< endl;
cout<<"(Please use Capital letter for first letter of the state)"<< endl;
cout<<"State Name = ";
cin>>stateName;
cout<< endl;
int myIndx=myHashTable.hashFunc(stateName);
bool myItemFound=false;
myHashTable.clearMyStateInfo(myIndx, stateName, myItemFound);
cout<<stateName<<" has been deleted from the hash table"<<endl<<endl;
cout<<"Displaying Updated Hash Table:"<<endl;
if(!myItemFound)
cout<<"Item not Found."<<endl;
}
fID1.close();
myHashTable.displayMystateHashTable() ;
}
void DisplayHashTable()
{
STATEHASHTABLE<StateData> myHashTable(100);
ifstream fID1("Kyles_State_Data.txt");
if(fID1.is_open())
{
StateData myState;
while(fID1)
{
fID1>>myState;
int myIndx=myHashTable.hashFunc(myState.getMyStateName());
myHashTable.InsertMyState(myIndx, myState);
}
fID1.close();
myHashTable.displayMystateHashTable() ;
//if(!myItemFound)
//cout<<"Item not Found."<<endl;
}}
int main()
//{
//STATEHASHTABLE<StateData> myHashTable(100);
//ifstream fID1("Kyles_State_Data.txt");
//if(fID1.is_open())
//{
//StateData myState;
//while(fID1)
//{
//fID1>>myState;
//int myIndx=myHashTable.hashFunc(myState.getMyStateName());
//myHashTable.InsertMyState(myIndx, myState);
//}
{
int input;
cout<<"1. SearchState ";
cout<<"2. DeleteState ";
cout<<"3. DisplayHashTable ";
cout<<"Selection: ";
cin>> input;
switch ( input ) {
case 1: // Note the colon, not a semicolon
SearchState();
cout<<endl;
main();
break;
case 2: // Note the colon, not a semicolon
DeleteState();
cout<<endl;
main();
break;
case 3: // Note the colon, not a semicolon
DisplayHashTable();
cout<<endl;
main();
break;
default: // Note the colon, not a semicolon
cout<<"Error, bad input, Try Again ";
cout<<endl;
main();
break;
}
return 0;
}
Explanation / Answer
# include <iostream.h>
# include <conio.h>
class sorting
{
int a[100],n;
public:
void accept()
{
cout<<"ENTER N VALUE ";
cin>>n;
for(int i=0;i<n;i++)
{
cout<<"ENTER "<<i<<" Value ";
cin>>a[i];
}
}
void print()
{
for(int i=0;i<n;i++)
cout<<a[i]<<endl;
}
void sort()
{
int i,j,tmp,limit;
limit=n-1;
for(i=0;i<n-1;i++)
for(j=0;j<limit-i;j++)
if(a[j+1]<a[j])
{
tmp=a[j+1];
a[j+1]=a[j];
a[j]=tmp;
}
}
};
void main()
{
clrscr();
sorting s;
s.accept();
cout<<"The values before sortig "<<endl;
s.print();
s.sort();
cout<<"The values after sorting "<<endl;
s.print();
getch();
}