Some of the attributes of a state in the United States are its name, capital, ar
ID: 3757702 • Letter: S
Question
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. Carefully examine the format and layout of the information in the data file that is provided.
Part 2:
Use the class hashT as described in the reading section (see the reading resource in the Class Activities worksheet), ‘‘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 (The hashT class file is part of your download above). 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.
Test 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:
/****************************************************************
//
// This class specifies the members to implement a hash table as
// an ADT. It uses quadratic probing to resolve collisions.
//****************************************************************
#include <iostream>
#include <cassert>
using namespace std;
template <class elemType>
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; //number of items in the hash table
int HTSize; //maximum size of the hash table
};
template <class elemType>
void hashT<elemType>::insert(int hashIndex, const elemType& rec)
{
int pCount;
int inc;
pCount = 0;
inc = 1;
while (indexStatusList[hashIndex] == 1
&& HTable[hashIndex] != rec
&& pCount < HTSize / 2)
{
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 << "Error: No duplicates are allowed" << endl;
else
cerr << "Error: The table is full. "
<<"Unable to resolve the collision" << endl;
}
template <class elemType>
void hashT<elemType>::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 < HTSize / 2)
{
pCount++;
hashIndex = (hashIndex + inc ) % HTSize;
inc = inc + 2;
}
if (indexStatusList[hashIndex] == 1 && HTable[hashIndex] == rec )
{
hashIndex = hashIndex;
found = true;
}
else
found = false;
}
template <class elemType>
bool hashT<elemType>::isItemAtEqual(int hashIndex, const elemType& rec) const
{
return(HTable[hashIndex] == rec);
}
template <class elemType>
void hashT<elemType>::retrieve(int hashIndex, elemType& rec) const
{
if (indexStatusList[hashIndex] == 1)
rec = HTable[hashIndex];
}
template <class elemType>
void hashT<elemType>::remove(int hashIndex, const elemType& rec)
{
bool found;
search(hashIndex,rec,found);
if (found)
{
indexStatusList[hashIndex] = -1;
length--;
}
else
cerr << "The item to be deleted is not in the list."
<< endl;
}
template <class elemType>
void hashT<elemType>::print() const
{
for (int i = 0; i < HTSize; i++)
if (indexStatusList[i] != 0)
cout << i << " " << indexStatusList[i]
<< " " << HTable[i] << endl;
}
template <class elemType>
hashT<elemType>::hashT(int size)
{
assert(size > 0);
HTable = new elemType[size];
indexStatusList = new int[size];
length = 0;
HTSize = size;
for (int i = 0; i < size; i++)
indexStatusList[i] = 0;
}
template <class elemType>
hashT<elemType>::~hashT()
{
delete [] HTable;
delete [] indexStatusList;
}
#endif
..........................................
stateInfo.txt
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
Explanation / Answer
#include <iostream>
#include <cassert>
using namespace std;
template <class elemType>
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; //number of items in the hash table
int HTSize; //maximum size of the hash table
};
template <class elemType>
void hashT<elemType>::insert(int hashIndex, const elemType& rec)
{
int pCount;
int inc;
pCount = 0;
inc = 1;
while (indexStatusList[hashIndex] == 1
&& HTable[hashIndex] != rec
&& pCount < HTSize / 2)
{
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 << "Error: No duplicates are allowed" << endl;
else
cerr << "Error: The table is full. "
<<"Unable to resolve the collision" << endl;
}
template <class elemType>
void hashT<elemType>::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 < HTSize / 2)
{
pCount++;
hashIndex = (hashIndex + inc ) % HTSize;
inc = inc + 2;
}
if (indexStatusList[hashIndex] == 1 && HTable[hashIndex] == rec )
{
hashIndex = hashIndex;
found = true;
}
else
found = false;
}
template <class elemType>
bool hashT<elemType>::isItemAtEqual(int hashIndex, const elemType& rec) const
{
return(HTable[hashIndex] == rec);
}
template <class elemType>
void hashT<elemType>::retrieve(int hashIndex, elemType& rec) const
{
if (indexStatusList[hashIndex] == 1)
rec = HTable[hashIndex];
}
template <class elemType>
void hashT<elemType>::remove(int hashIndex, const elemType& rec)
{
bool found;
search(hashIndex,rec,found);
if (found)
{
indexStatusList[hashIndex] = -1;
length--;
}
else
cerr << "The item to be deleted is not in the list."
<< endl;
}
template <class elemType>
void hashT<elemType>::print() const
{
for (int i = 0; i < HTSize; i++)
if (indexStatusList[i] != 0)
cout << i << " " << indexStatusList[i]
<< " " << HTable[i] << endl;
}
template <class elemType>
hashT<elemType>::hashT(int size)
{
assert(size > 0);
HTable = new elemType[size];
indexStatusList = new int[size];
length = 0;
HTSize = size;
for (int i = 0; i < size; i++)
indexStatusList[i] = 0;
}
template <class elemType>
hashT<elemType>::~hashT()
{
delete [] HTable;
delete [] indexStatusList;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.