hashT.h. >>>>>>>>>>>>>>>>>>>>>>

#ifndef H_Htable

#define H_Htable

//****************************************************************

// Author: D.S. Malik

//

// This class specifies the members to implement a hash table as

// an ADT. It uses quadratic probing to resolve collisions.

//****************************************************************

#include

#include

using namespace std;

template

class hashT

{

public:

void insert(int hashIndex, const elemType& rec);

//Function to insert an item in the hash table. The first

//parameter specifies the initial hash index of the item to

//be inserted. The item to be inserted is specified by the

//parameter rec.

//Postcondition: If an empty position is found in the hash

// table, rec is inserted and the length is incremented by

// one; otherwise, an appropriate error message is

// displayed.

void search(int& hashIndex, const elemType& rec, bool& found) const;

//Function to determine whether the item specified by the

//parameter rec is in the hash table. The parameter hashIndex

//specifies the initial hash index of rec.

//Postcondition: If rec is found, found is set to true and

// hashIndex specifies the position where rec is found;

// otherwise, found is set to false.

bool isItemAtEqual(int hashIndex, const elemType& rec) const;

//Function to determine whether the item specified by the

//parameter rec is the same as the item in the hash table

//at position hashIndex.

//Postcondition: Returns true if HTable[hashIndex] == rec;

// otherwise, returns false.

void retrieve(int hashIndex, elemType& rec) const;

//Function to retrieve the item at position hashIndex.

//Postcondition: If the table has an item at position

// hashIndex, it is copied into rec.

void remove(int hashIndex, const elemType& rec);

//Function to remove an item from the hash table.

//Postcondition: Given the initial hashIndex, if rec is found

// in the table it is removed; otherwise, an appropriate

// error message is displayed.

void print() const;

//Function to output the data.

hashT(int size = 101);

//constructor

//Postcondition: Create the arrays HTTable and indexStatusList;

// initialize the array indexStatusList to 0; length = 0;

// HTSize = size; and the default array size is 101.

~hashT();

//destructor

//Postcondition: Array HTable and indexStatusList are deleted.

private:

elemType *HTable; //pointer to the hash table

int *indexStatusList; //pointer to the array indicating the

//status of a position in the hash table

int length; /umber of items in the hash table

int HTSize; //maximum size of the hash table

};

template

void hashT::insert(int hashIndex, const elemType& rec)

{

int pCount;

int inc;

pCount = 0;

inc = 1;

while (indexStatusList[hashIndex] == 1

&& HTable[hashIndex] != rec

&& pCount

{

pCount++;

hashIndex = (hashIndex + inc ) % HTSize;

inc = inc + 2;

}

if (indexStatusList[hashIndex] != 1)

{

HTable[hashIndex] = rec;

indexStatusList[hashIndex] = 1;

length++;

}

else if (HTable[hashIndex] == rec)

cerr

else

cerr

}

template

void hashT::search(int& hashIndex, const elemType& rec,

bool& found) const

{

int pCount;

int inc;

pCount = 0;

inc = 1;

while (indexStatusList[hashIndex] != 0

&& HTable[hashIndex] != rec

&& pCount

{

pCount++;

hashIndex = (hashIndex + inc ) % HTSize;

inc = inc + 2;

}

if (indexStatusList[hashIndex] == 1 && HTable[hashIndex] == rec )

{

hashIndex = hashIndex;

found = true;

}

else

found = false;

}

template

bool hashT::isItemAtEqual(int hashIndex, const elemType& rec) const

{

return(HTable[hashIndex] == rec);

}

template

void hashT::retrieve(int hashIndex, elemType& rec) const

{

if (indexStatusList[hashIndex] == 1)

rec = HTable[hashIndex];

}

template

void hashT::remove(int hashIndex, const elemType& rec)

{

bool found;

search(hashIndex,rec,found);

if (found)

{

indexStatusList[hashIndex] = -1;

length--;

}

else

cerr

}

template

void hashT::print() const

{

for (int i = 0; i

if (indexStatusList[i] != 0)

cout

}

template

hashT::hashT(int size)

{

assert(size > 0);

HTable = new elemType[size];

indexStatusList = new int[size];

length = 0;

HTSize = size;

for (int i = 0; i

indexStatusList[i] = 0;

}

template

hashT::~hashT()

{

delete [] HTable;

delete [] indexStatusList;

}

#endif

stateDate.h>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

#include

#include

#include "hashT.h"

using namespace std;

class stateData

{

friend ostream& operator

friend istream& operator>>(istream&, stateData&);

public:

void setStateInfo(string sName, string sCapital,

double stateArea, int yAdm, int oAdm);

void getStateInfo(string& sName, string& sCapital,

double& stateArea, int& yAdm, int& oAdm);

string getStateName();

string getStateCapitalName();

double getArea();

int getYearOfAdmission();

int getOrderOfAdmission();

void printInfo();

bool operator==(const stateData& right) const;

bool operator!=(const stateData& right) const;

private:

string stateName;

string stateCapital;

double stateArea;

int yearOfAdmission;

int orderOfAdmission;

};

test Driver.cpp>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

#include

#include

#include

#include "stateData.h"

#include "hashT.h"

using namespace std;

const int HTSize = 101;

int hashFunc(string name);

int main()

{

hashT stateTable(HTSize);

ifstream infile;

stateData stData;

string stName;

int key;

bool found;

cout

infile.open("states.txt");

for (int i = 1; i

{

infile>>stData;

stName = stData.getStateName();

key = hashFunc(stName);

stateTable.insert(key, stData);

}

stateTable.print();

cout

getline(cin, stName);

cout

key = hashFunc(stName);

stData.setStateInfo(stName,"",0,0,0);

stateTable.search(key, stData, found);

if (found)

cout

else

cout

cout

getline(cin, stName);

cout

key = hashFunc(stName);

stData.setStateInfo(stName,"",0,0,0);

stateTable.remove(key, stData);

stateTable.print();

return 0;

}

int hashFunc(string name)

{

int i, sum;

int len;

i = 0;

sum = 0;

len = name.length();

for (int k = 0; k

name = name + ' '; //increase the length of name to 15 characters

for (int k = 0; k

{

sum = sum + static_cast(name[i]) * 128 * 128

+ static_cast(name[i + 1]) * 128

+ static_cast(name[i + 2]);

i = i + 3;

}

return sum % HTSize;

}

Problems: 1) USA States a. Some of the attributes of a state in the United States are its name, capital, area, year of admission to the union, and the order of admission to the union. Design the class stateData to keep track of the information for a state. Your class must include appropriate functions to manipulate the state's data, such as the functions setStateInfo, getStateInfo, and so on. Also, overload the relational operators to compare two states by their name. For easy input and output, overload the stream operators. Check the stateData.h file. b. Use the class hashT as described in the section: "Hashing: Implementation Using Quadratic Probing," which uses quadratic probing to resolve collision, to create a hash table to keep track of each state's information. Use the state's name as the key to determine the hash address. You may assume that a state's name is a string of no more than 15 characters. Check the hashT.h file. The test driver is provided; it tests your program by searching for and removing certain states from the hash table. You may use the following hash function to determine the hash address of an item int hashFunc (string name) //available in the test driver int i-0, sum-0 len; len -name.length for (int k = 0; k (name [1]) * 128 * 128 + static cast (namei 21); + static cast (name [i + 1] 128 return sum % HTSize; Resources: USA states Application (input file; test driver; stateData.h; hashT.h) Problems: 1) USA States a. Some of the attributes of a state in the United States are its name, capital, area, year of admission to the union, and the order of admission to the union. Design the class stateData to keep track of the information for a state. Your class must include appropriate functions to manipulate the state's data, such as the functions setStateInfo, getStateInfo, and so on. Also, overload the relational operators to compare two states by their name. For easy input and output, overload the stream operators. Check the stateData.h file. b. Use the class hashT as described in the section: "Hashing: Implementation Using Quadratic Probing," which uses quadratic probing to resolve collision, to create a hash table to keep track of each state's information. Use the state's name as the key to determine the hash address. You may assume that a state's name is a string of no more than 15 characters. Check the hashT.h file. The test driver is provided; it tests your program by searching for and removing certain states from the hash table. You may use the following hash function to determine the hash address of an item int hashFunc (string name) //available in the test driver int i-0, sum-0 len; len -name.length for (int k = 0; k (name [1]) * 128 * 128 + static cast (namei 21); + static cast (name [i + 1] 128 return sum % HTSize; Resources: USA states Application (input file; test driver; stateData.h; hashT.h)