//HashT.h #ifndef H_Htable #define H_Htable //**********************************
ID: 3712744 • Letter: #
Question
//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 <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
//test driver #include <iostream> #include <fstream> #include <string> #include "stateData.h" #include "hashT.h"
using namespace std;
const int HTSize = 101;
int hashFunc(string name);
int main() { hashT<stateData> stateTable(HTSize);
ifstream infile;
stateData stData;
string stName; int key; bool found;
cout << "Processing data" << endl;
infile.open("states.txt");
for (int i = 1; i <= 50; i++) { infile>>stData; stName = stData.getStateName(); key = hashFunc(stName); stateTable.insert(key, stData); }
stateTable.print();
cout << "Enter the name of the state to be searched: "; getline(cin, stName); cout << endl;
key = hashFunc(stName); stData.setStateInfo(stName,"",0,0,0); stateTable.search(key, stData, found);
if (found) cout << "Item found in the list" << endl; else cout << "Item not in the list." << endl;
cout << "Enter the name of the state to be deleted: "; getline(cin, stName); cout << endl;
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 < 15-len; k++) name = name + ' '; //increase the length of name to 15 characters
for (int k = 0; k < 5; k++) { sum = sum + static_cast<int>(name[i]) * 128 * 128 + static_cast<int>(name[i + 1]) * 128 + static_cast<int>(name[i + 2]); i = i + 3; }
return sum % HTSize; } #include <iostream> #include <fstream> #include <string> #include "stateData.h" #include "hashT.h"
using namespace std;
const int HTSize = 101;
int hashFunc(string name);
int main() { hashT<stateData> stateTable(HTSize);
ifstream infile;
stateData stData;
string stName; int key; bool found;
cout << "Processing data" << endl;
infile.open("states.txt");
for (int i = 1; i <= 50; i++) { infile>>stData; stName = stData.getStateName(); key = hashFunc(stName); stateTable.insert(key, stData); }
stateTable.print();
cout << "Enter the name of the state to be searched: "; getline(cin, stName); cout << endl;
key = hashFunc(stName); stData.setStateInfo(stName,"",0,0,0); stateTable.search(key, stData, found);
if (found) cout << "Item found in the list" << endl; else cout << "Item not in the list." << endl;
cout << "Enter the name of the state to be deleted: "; getline(cin, stName); cout << endl;
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 < 15-len; k++) name = name + ' '; //increase the length of name to 15 characters
for (int k = 0; k < 5; k++) { sum = sum + static_cast<int>(name[i]) * 128 * 128 + static_cast<int>(name[i + 1]) * 128 + static_cast<int>(name[i + 2]); i = i + 3; }
return sum % HTSize; }
//statedata.h #include <iostream> #include <string> #include "hashT.h"
using namespace std;
class stateData { friend ostream& operator<<(ostream&, const stateData&); 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; }; #include <iostream> #include <string> #include "hashT.h"
using namespace std;
class stateData { friend ostream& operator<<(ostream&, const stateData&); 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 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>
#include <fstream>
#include "orderedArrayListType.h"
#include "hashT.h"
#include "stateData.h"
using namespace std;
void part2();
int main()
{
part2();
};
void part2() {
cout << " ============================|Problem 2|======================================= " << endl;
hashT<stateData> stateHash(101);
cout << "Opening file..." << endl;
ifstream infile;
infile.open("state_data.txt");
assert(infile.is_open());
cout << "Creating hash from file..." << endl;
while (infile)
{
stateData newState;
infile >> newState;
int stateIndex = stateHash.hashFunc(newState.getName());
stateHash.insert(stateIndex, newState);
}
infile.close();
bool found1;
int hashIndex;
string stateName;
stateData searchState;
cout << "Search the hash, Type the name of a state: ";
cin >> stateName;
hashIndex = stateHash.hashFunc(stateName);
searchState = stateData(stateName);
stateHash.search(hashIndex, searchState, found1);
if (found1 && stateHash.isItemAtEqual(hashIndex, searchState))
{
cout << "Success!" << endl;
stateHash.retrieve(hashIndex, searchState);
cout << searchState << endl;
}
else
{
cout << "Not Found!" << endl;
}
cout << "REMOVING STATE" << endl;
stateHash.remove(hashIndex, searchState);
bool found2;
stateHash.search(hashIndex, searchState, found2);
if (found2 && stateHash.isItemAtEqual(hashIndex,searchState))
{
cout << "Failed to remove state." << endl;
cout << searchState << endl;
}
else
{
cout << "Successfully removed state." << endl;
cout << "Printing States" << endl;
cout << setw(15) << left << "Name: " << " | ";
cout << setw(15) << left << "Capital: " << " | ";
cout << setw(15) << left << "Joined Union: "<< " | ";
cout << setw(15) << left << "Join Number: "<< " | ";
cout << setw(15) << left << "Area: " << endl;
stateHash.print();
}
}
stateData.h
#include <string>
#include <iostream>
#include <iomanip>
using namespace std;
class stateData {
private:
string name;
string capital;
int unionNum;
int year;
int area;
public:
string getName() { return name; }
void setName(string n) { name = n; }
string getCapital() { return capital; }
void setCapital(string c) { capital = c; }
int getUnionNum() { return unionNum; }
void setUnionNum(int n) { unionNum = n; }
int getYear() { return year; }
void setYear(int y) { year = y; }
int getArea() { return area; }
void setArea(int a) { area = a; }
stateData(string iname = " ", string icap = " ", int inum = 0, int iyear = 0, int iarea = 0) {
name = iname;
capital = icap;
unionNum = inum;
year = iyear;
area = iarea;
}
friend ostream& operator<<(ostream& out, stateData& state)
{
if (state.getArea() > 0)
{
out << setw(15) << right << state.getName()<< " | ";
out << setw(15) << right << state.getCapital()<< " | ";
out << setw(15) << right << state.getYear()<< " | ";
out << setw(15) << right << state.getUnionNum()<< " | ";
out << setw(15) << right << state.getArea();
}
return out;
}
friend istream& operator>>(istream& in, stateData& state)
{
char ch;
getline(in, state.name);
getline(in, state.capital);
in >> state.area >> state.year >> state.unionNum;
in.get(ch);
return in;
}
stateData& operator=(const stateData& other)
{
name = other.name;
capital = other.capital;
unionNum = other.unionNum;
year = other.year;
area = other.area;
return *this;
}
bool operator==(const stateData& other)const{ return name == other.name;}
bool operator!=(const stateData& other)const{ return name != other.name;}
bool operator>=(const stateData& other)const{ return name> = other.name;}
bool operator>(const stateData& other) const{ return name> other.name; }
bool operator<=(const stateData& other)const{ return name< = other.name;}
bool operator<(const stateData& other) const{ return name< other.name; }
};
orderedArrayListType.h
#ifndef H_OrderedListType
#define H_OrderedListType
#include <iostream>
#include "arrayListType.h"
using namespace std;
template<class elemType>
class orderedArrayListType: public arrayListType<elemType>
{
public:
void insertOrd(const elemType&);
void fill();
int binarySearch(const elemType& item) const;
int binaryWithSeqSearch(const elemType& item)const;
orderedArrayListType(int size = 100);
};
template <class elemType>
void orderedArrayListType<elemType>::insertOrd(const elemType& item)
{
int first = 0;
int last = length - 1;
int mid;
bool found = false;
if (length == 0)
{
list[0] = item;
length++;
}
else if (length == maxSize)
cerr << "Cannot insert into a full list." << endl;
else
{
while (first <= last && !found)
{
mid = (first + last) / 2;
if (list[mid] == item)
found = true;
else if (list[mid] > item)
last = mid - 1;
else
first = mid + 1;
}
if (found)
cerr << "The insert item is already in the list. "
<< "Duplicates are not allowed." << endl;
else
{
if (list[mid] < item)
mid++;
insertAt(mid, item);
}
}
}
template<class elemType>
int orderedArrayListType<elemType>::binaryWithSeqSearch
(const elemType& item) const
{
int first = 0;
int last = length - 1;
int mid;
bool found = false;
int count = 0;
while (first <= last && !found)
{
mid = (first + last) / 2;
count++;
if (list[mid] == item)
found = true;
else if (list[mid] > item)
last = mid - 1;
else
first = mid + 1;
if (last - first <= 15)
{
for (int i = first; i <= last; i++)
{
count++;
if (list[i] == item)
{
found = true;
break;
}
}
break;
}
}
cout << "Binary search with sequential comparisons: "<< count << endl;
if (found)
return mid;
else
return -1;
}
template<class elemType>
int orderedArrayListType<elemType>::binarySearch
(const elemType& item) const
{
int first = 0;
int last = length - 1;
int mid;
bool found = false;
int count = 0;
count = 2;
while (first <= last && !found)
{
mid = (first + last) / 2;
count++;
if (list[mid] == item)
found = true;
else if (list[mid] > item)
last = mid - 1;
else
first = mid + 1;
}
cout << "Binary search comparisons: " << count << endl;
if (found)
return mid;
else
return -1;
}
template<class elemType>
orderedArrayListType<elemType>::orderedArrayListType(int size)
: arrayListType<elemType>(size)
{
}
template<class elemType>
void orderedArrayListType<elemType> :: fill()
{
int seed = 47;
int multiplier = 2743;
int addOn = 5923;
while (listSize() < maxListSize())
{
insertOrd(seed);
seed = int((seed * multiplier + addOn) % 100000);
}
}
#endif
arrayListType.h
#ifndef H_arrayListType
#define H_arrayListType
#include <iostream>
#include <cassert>
using namespace std;
template <class elemType>
class arrayListType
{
public:
const arrayListType<elemType>& operator=
(const arrayListType<elemType>&);
bool isEmpty() const;
bool isFull() const;
int listSize() const;
int maxListSize() const;
void print() const;
bool isItemAtEqual(int location, const elemType& item) const;
void insertAt(int location, const elemType& insertItem);
void insertEnd(const elemType& insertItem);
void removeAt(int location);
void retrieveAt(int location, elemType& retItem) const;
void replaceAt(int location, const elemType& repItem);
void clearList();
int seqSearch(const elemType& item) const;
void insert(const elemType& insertItem);
void remove(const elemType& removeItem);
arrayListType(int size = 100);
arrayListType(const arrayListType<elemType>& otherList);
~arrayListType();
protected:
elemType *list;
int length;
int maxSize;
};
template <class elemType>
bool arrayListType<elemType>::isEmpty() const
{
return (length == 0);
}
template <class elemType>
bool arrayListType<elemType>::isFull() const
{
return (length == maxSize);
}
template <class elemType>
int arrayListType<elemType>::listSize() const
{
return length;
}
template <class elemType>
int arrayListType<elemType>::maxListSize() const
{
return maxSize;
}
template <class elemType>
void arrayListType<elemType>::print() const
{
for (int i = 0; i < length; i++)
cout << list[i] << " ";
cout << endl;
}
template <class elemType>
bool arrayListType<elemType>::isItemAtEqual
(int location, const elemType& item) const
{
return(list[location] == item);
}
template <class elemType>
void arrayListType<elemType>::insertAt
(int location, const elemType& insertItem)
{
if (location < 0 || location >= maxSize)
cerr << "The position of the item to be inserted "
<< "is out of range" << endl;
else if (length >= maxSize)
cerr << "Cannot insert in a full list" << endl;
else
{
for (int i = length; i > location; i--)
list[i] = list[i - 1];
list[location] = insertItem;
length++;
}
}
template <class elemType>
void arrayListType<elemType>::insertEnd(const elemType& insertItem)
{
if (length >= maxSize)
cerr << "Cannot insert in a full list" << endl;
else
{
list[length] = insertItem;
length++;
}
}
template <class elemType>
void arrayListType<elemType>::removeAt(int location)
{
if (location < 0 || location >= length)
cerr << "The location of the item to be removed "
<< "is out of range" << endl;
else
{
for (int i = location; i < length - 1; i++)
list[i] = list[i+1];
length--;
}
}
template <class elemType>
void arrayListType<elemType>::retrieveAt
(int location, elemType& retItem) const
{
if (location < 0 || location >= length)
cerr << "The location of the item to be retrieved is "
<< "out of range." << endl;
else
retItem = list[location];
}
template <class elemType>
void arrayListType<elemType>::replaceAt
(int location, const elemType& repItem)
{
if (location < 0 || location >= length)
cerr << "The location of the item to be replaced is "
<< "out of range." << endl;
else
list[location] = repItem;
}
template <class elemType>
void arrayListType<elemType>::clearList()
{
length = 0;
}
template <class elemType>
int arrayListType<elemType>::seqSearch(const elemType& item) const
{
int loc;
bool found = false;
int count = 0;
for (loc = 0; loc < length; loc++) {
count++;
if (list[loc] == item)
{
found = true;
break;
}
}
cout << "Sequential search comparisons" << count<< endl;
if (found)
return loc;
else
return -1;
}
template <class elemType>
void arrayListType<elemType>::insert(const elemType& insertItem)
{
int loc;
if (length == 0)
list[length++] = insertItem;
else if (length == maxSize)
cerr << "Cannot insert in a full list." << endl;
else
{
loc = seqSearch(insertItem);
if (loc == -1)
list[length++] = insertItem;
else
cerr << "the item to be inserted is already in "
<< "the list. No duplicates are allowed." << endl;
}
}
template<class elemType>
void arrayListType<elemType>::remove(const elemType& removeItem)
{
int loc;
if (length == 0)
cerr << "Cannot delete from an empty list." << endl;
else
{
loc = seqSearch(removeItem);
if (loc != -1)
removeAt(loc);
else
cout << "The item to be deleted is not in the list."
<< endl;
}
}
template <class elemType>
arrayListType<elemType>::arrayListType(int size)
{
if (size < 0)
{
cerr << "The array size must be positive. Creating "
<< "an array of size 100. " << endl;
maxSize = 100;
}
else
maxSize = size;
length = 0;
list = new elemType[maxSize];
assert(list != NULL);
}
template <class elemType>
arrayListType<elemType>::~arrayListType()
{
delete [] list;
}
template <class elemType>
arrayListType<elemType>::arrayListType
(const arrayListType<elemType>& otherList)
{
maxSize = otherList.maxSize;
length = otherList.length;
list = new elemType[maxSize];
assert(list != NULL);
for (int j = 0; j < length; j++)
list [j] = otherList.list[j];
}
template <class elemType>
const arrayListType<elemType>& arrayListType<elemType>::operator=
(const arrayListType<elemType>& otherList)
{
if (this != &otherList)
{
delete [] list;
maxSize = otherList.maxSize;
length = otherList.length;
list = new elemType[maxSize];
assert(list != NULL);
for (int i = 0; i < length; i++)
list[i] = otherList.list[i];
}
return *this;
}
#endif
hashT.h
#ifndef H_Htable
#define H_Htable
#include <iostream>
#include <cassert>
using namespace std;
template <class elemType>
class hashT
{
public:
void insert(int hashIndex, const elemType& rec);
void search(int& hashIndex, const elemType& rec, bool& found) const;
bool isItemAtEqual(int hashIndex, const elemType& rec) const;
void retrieve(int hashIndex, elemType& rec) const;
void remove(int hashIndex, const elemType& rec);
void print() const;
int hashFunc(string name);
hashT(int size = 101);
~hashT();
private:
elemType *HTable;
int *indexStatusList;
int length;
int HTSize;
};
template <class elemType>
int hashT<elemType>::hashFunc(string name)
{
int i, sum;
int len;
i = 0;
sum = 0;
len = name.length();
for (int k = 0; k < 15 - len; k++)
name = name + ' ';
for (int k = 0; k < 5; k++)
{
sum = sum + static_cast<int>(name[i]) * 128 * 128
+ static_cast<int>(name[i + 1]) * 128
+ static_cast<int>(name[i + 2]);
i = i + 3;
}
return sum % HTSize;
}
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 (HTable[hashIndex] == rec && indexStatusList[hashIndex] == 1) {
found == true;
}
else {
found == false;
}
}
template <class elemType>
bool hashT<elemType>::isItemAtEqual(int hashIndex, const elemType& rec) const
{
if (indexStatusList[hashIndex] != 1)
{
cout << "No Item at location!" << endl;
return false;
}
else
{
return HTable[hashIndex] == rec;
}
}
template <class elemType>
void hashT<elemType>::retrieve(int hashIndex, elemType& rec) const
{
if (indexStatusList[hashIndex] != 1)
{
cout << "No Item at location!" << endl;
}
else
{
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
{
cout << "Item is missing." << endl;
}
}
template <class elemType>
void hashT<elemType>::print() const
{
for (int i = 0; i < HTSize; i++)
{
if (indexStatusList[i] == 1)
{
cout << HTable[i] << endl;
}
}
}
template <class elemType>
hashT<elemType>::hashT(int size)
{
HTable = new elemType[size];
indexStatusList = new int[size];
HTSize = size;
length = 0;
for (int i = 0; i < size; i++)
{
indexStatusList[i] = 0;
}
}
template <class elemType>
hashT<elemType>::~hashT()
{
delete[] HTable;
delete[] indexStatusList;
}
#endif
state_data.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
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.