//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

//test driver

#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;

}

//statedata.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;

};

//states.text

New Hampshire

Concord

9304 1788 9

Massachusetts

Boston

8257 1788 6

Vermont

Montpelier

9609 1791 14

Rhode Island

Providence

1214 1790 13

Connecticut

Hartford

5009 1788 5

Maine

Augusta

33215 1820 23

New York

Albany

49576 1788 11

Pennsylvania

Harrisburg

45333 1787 2

Delaware

Dover

2057 1787 1

Maryland

Annapolis

10577 1788 7

Washington

Olympia

68192 1889 42

Oregon

Salem

96981 1859 33

Virginia

Richmond

40815 1788 10

North Carolina

Raleigh

52586 1789 12

South Carolina

Columbia

31055 1788 8

Georgia

Atlanta

58876 1788 4

New Jersey

Trenton

7836 1787 3

Hawaii

Honolulu

6450 1959 50

Iowa

Des Moines

56290 1846 29

Florida

Tallahassee

58560 1845 27

Tennessee

Nashville

42244 1796 16

Michigan

Lansing

58216 1837 26

Ohio

Columbus

41222 1803 17

Wyoming

Cheyenne

97914 1890 44

Colorado

Denver

104247 1876 38

Nebraska

Lincoln

77227 1867 37

Wisconsin

Madison

56154 1848 30

South Dakota

Pierre

77047 1889 39

Alabama

Montgomery

51609 1819 22

Mississippi

Jackson

47716 1817 20

Louisiana

Baton Rouge

48523 1812 18

Arkansas

Little Rock

53104 1836 25

Missouri

Jefferson City

69686 1821 24

Kentuckey

Frankfort

40395 1792 15

Minnesota

Saint Paul

84068 1858 32

North Dakota

Bismark

70665 1889 41

Kansas

Topeka

82264 1861 34

Oklahoma

Oklahoma City

69919 1907 46

Texas

Austin

267338 1845 28

New Mexico

Santa Fe

121666 1912 47

Arizona

Phoenix

113909 1912 48

Utah

Sakt Lake City

84916 1896 45

Nevada

Carson City

110540 1864 36

Idaho

Boise

83557 1890 43

West Virginia

Charleston

24181 1863 35

California

Sacramento

158706 1850 31

Alaska

Juneau

586412 1959 49

Indiana

Indianapolis

36291 1816 19

Illinois

Springfield

56400 1818 21

Montana

Helena

147138 1889 41

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. ing hashh rImi n I int hashFunc (string name) 7/available in the test driver int 1-0, sum-0: lena lennae.ength or (int k0: k15-len: k) ame name/increase the length of the name to 15 characters for (intk-0: k (name [ 128128 static castcint> (namei 21) + static castcint> (nameli +11)128 13 return sum HTS ize ; Resources: USA states Application (input file; test driver; stateData.h; hashT.h)