我正在做一个关于使用向量的开放寻址哈希表的项目。该项目的一个方面是使用模板来允许用户定义向量的类型。我已经实现了模板,如果我在编译之前创建一个对象,它就可以工作,但是我不知道如何让用户在运行时决定类型。
该程序是面向对象的,并且必须将类型传递给构造函数。起初我认为简单的 if 语句会起作用,但后来我了解到这不起作用。谁能帮我解决这个问题?谢谢
#include <iostream>
#include <string>
#include <vector>
using namespace std;
template <class T>
class OpenHash
{
private:
vector <T> hashTab;
vector <int> emptyCheck;
int hashF(string);
public:
OpenHash(int);
int getVectorCap();
int addRecord (T);
int sizeHash();
int find(T);
int printHash();
int deleteEntry(T);
};
template <class T>
OpenHash<T>::OpenHash(int vecSize)
{
hashTab.clear();
hashTab.resize(vecSize);
emptyCheck.resize(vecSize);
for (int i=0; i < emptyCheck.capacity(); i++)
{
emptyCheck.at(i) = 0;
}
}
template <class T>
int OpenHash<T>::getVectorCap()
{
int cap = hashTab.capacity();
int capE = emptyCheck.capacity();
cout << cap << capE;
return 0;
}
template <class T>
int OpenHash<T>::hashF (string key)
{
int ascii = 0, hasVal = 0;
for (int i = 0; i < key.size(); i++)
{
ascii += key[i];
}
hasVal = ascii % hashTab.capacity();
return hasVal;
}
template <class T>
int OpenHash<T>::addRecord(T key)
{
if (sizeHash() == emptyCheck.size())
{
cout << "Your hash table is full cannot add any more records" << endl;
}
else
{
bool findPos = false;
for (int j=0; j<hashTab.capacity(); j++)
{
if (hashTab.at(j) == key)
{
cout << "Element ready exists in hashtable" << endl;
return 0;
}
}
int hashVal = hashF(key);
for (int i=hashVal; i<emptyCheck.capacity(); i++)
{
if (emptyCheck.at(i) == 0)
{
hashTab.at(i) = key;
emptyCheck.at(i) = 1;
cout << "Element added at" << '[' << i << ']' << endl;
findPos = true;
return 0;
}
else
{
cout << "Collision probing through..." << endl;
}
}
if (findPos == false)
{
for (int x=0; x<emptyCheck.capacity(); x++)
{
if (emptyCheck.at(x) == 0)
{
hashTab.at(x) = key;
emptyCheck.at(x) = 1;
cout << "Element added at" << '[' << x << ']' << endl;
findPos=true;
return 0;
}
}
cout << "Element could not be added" << endl;
}
}
return 1;
}
template <class T>
int OpenHash<T>::sizeHash()
{
int elementsFilled = 0;
for (int i = 0; i<emptyCheck.capacity(); i++)
{
if (emptyCheck.at(i) != 0)
{
elementsFilled++;
}
}
return elementsFilled;
}
template <class T>
int OpenHash<T>::find(T key)
{
int hashVal = hashF(key);
bool findLoop = false;
for (int i=hashVal; i < hashTab.capacity(); i++)
{
if (hashTab.at(i) == key && emptyCheck.at(i) == 1)
{
cout << "Element found at position: " << '[' << i << ']' << endl;
cout << key << endl;
findLoop = true;
return 0;
}
else
{
cout << "Element not found at position! Probing through..." << endl;
}
}
if (findLoop == false)
{
for (int j = 0; j < hashTab.capacity(); j++)
{
if (hashTab.at(j) == key && emptyCheck.at(j) != 0)
{
cout << "Element found at position: " << '[' << j << ']' << endl;
cout << key << endl;
findLoop = true;
return 0;
}
}
cout << "Entry not found" << endl;
}
return 1;
}
template <class T>
int OpenHash<T>::deleteEntry(T toDel)
{
int hashVal = hashF(toDel);
bool foundDel = false;
for (int i = hashVal; i<hashTab.capacity(); i++)
{
if (hashTab.at(i) == toDel)
{
emptyCheck.at(i) = 0;
foundDel = true;
cout << "Entry deleted!" << endl;
return 0;
}
}
if (foundDel == false)
{
for (int j=0; j<hashTab.capacity(); j++)
{
if (hashTab.at(j) == toDel)
{
emptyCheck.at(j) = 0;
foundDel = true;
cout << "Entry deleted!" << endl;
return 0;
}
}
cout << "The member to delete was not found" << endl;
}
return 1;
}
template <class T>
int OpenHash<T>::printHash()
{
if (sizeHash() == 0)
{
cout << "No elements filled to print!" << endl;
}
for (int i=0; i<emptyCheck.capacity(); i++)
{
if (emptyCheck.at(i) != 0)
{
cout << "Record at:" << '[' << i << ']' << hashTab.at(i) << endl;
}
}
return 0;
}
int main ()
{
cout << "Please input the size of your HashTable" << endl;
int vecSize = 0;
cin >> vecSize;
OpenHash<string> newTable(vecSize);
bool menu = true;
char choice;
while (menu == true)
{
cout << "Welcome to the open address hash table program, please input your choice:" << endl;
cin >> choice;
if (choice == 'a')
{
cout << "Please type in the record you wish to add:" << endl;
string rec;
getline(cin, rec);
newTable.addRecord(rec);
}
if (choice == 's')
{
cout << "Number of elements filled: " << newTable.sizeHash() << endl;
}
if (choice == 'f')
{
cout << "Please enter the string you wish to find" << endl;
string key;
getline(cin, key)
newTable.find(key);
}
if (choice == 'p')
{
cout << "Printing table..." << endl;
newTable.printHash();
}
if (choice == 'd')
{
cout << "Please input the item you wish to delete:" << endl;
string toDel;
getline(cin, toDel)
newTable.deleteEntry(toDel);
}
if (choice == 'x')
{
cout << "Thankyou" << endl;
menu = false;
}
}
return 0;
}