实现哈希表的C ++程序
哈希表是一种数据结构，用于存储键值对。哈希表使用哈希函数来计算要插入或搜索元素的数组的索引。
这是一个用于实现哈希表的C++程序。
算法
Begin Initialize the table size T_S to some integer value. Create a structure hashTableEntry to declare key k and value v. Create a class hashMapTable: Create a constructor hashMapTable to create the table. Create a hashFunc() function which return key mod T_S. Create a function Insert() to insert element at a key. Create a function SearchKey() to search element at a key. Create a function Remove() to remove element at a key. Call a destructor hashMapTable to destroy the objects created by the constructor. In main, perform switch operation and enter input as per choice. To insert key and values, call insert(). To search element, call SearchKey(). To remove element, call Remove(). End.
范例程式码
#include<iostream>
#include<cstdlib>
#include<string>
#include<cstdio>
using namespace std;
const int T_S = 200;
class HashTableEntry {
public:
int k;
int v;
HashTableEntry(int k, int v) {
this->k= k;
this->v = v;
}
};
class HashMapTable {
private:
HashTableEntry **t;
public:
HashMapTable() {
t = new HashTableEntry * [T_S];
for (int i = 0; i< T_S; i++) {
t[i] = NULL;
}
}
int HashFunc(int k) {
return k % T_S;
}
void Insert(int k, int v) {
int h = HashFunc(k);
while (t[h] != NULL && t[h]->k != k) {
h = HashFunc(h + 1);
}
if (t[h] != NULL)
delete t[h];
t[h] = new HashTableEntry(k, v);
}
int SearchKey(int k) {
int h = HashFunc(k);
while (t[h] != NULL && t[h]->k != k) {
h = HashFunc(h + 1);
}
if (t[h] == NULL)
return -1;
else
return t[h]->v;
}
void Remove(int k) {
int h = HashFunc(k);
while (t[h] != NULL) {
if (t[h]->k == k)
break;
h = HashFunc(h + 1);
}
if (t[h] == NULL) {
cout<<"No Element found at key "<<k<<endl;
return;
} else {
delete t[h];
}
cout<<"Element Deleted"<<endl;
}
~HashMapTable() {
for (int i = 0; i < T_S; i++) {
if (t[i] != NULL)
delete t[i];
delete[] t;
}
}
};
int main() {
HashMapTable hash;
int k, v;
int c;
while (1) {
cout<<"1.Insert element into the table"<<endl;
cout<<"2.Search element from the key"<<endl;
cout<<"3.Delete element at a key"<<endl;
cout<<"4.Exit"<<endl;
cout<<"Enter your choice: ";
cin>>c;
switch(c) {
case 1:
cout<<"Enter element to be inserted: ";
cin>>v;
cout<<"Enter key at which element to be inserted: ";
cin>>k;
hash.Insert(k, v);
break;
case 2:
cout<<"Enter key of the element to be searched: ";
cin>>k;
if (hash.SearchKey(k) == -1) {
cout<<"No element found at key "<<k<<endl;
continue;
} else {
cout<<"Element at key "<<k<<" : ";
cout<<hash.SearchKey(k)<<endl;
}
break;
case 3:
cout<<"Enter key of the element to be deleted: ";
cin>>k;
hash.Remove(k);
break;
case 4:
exit(1);
default:
cout<<"\nEnter correct option\n";
}
}
return 0;
}输出结果
1.Insert element into the table 2.Search element from the key 3.Delete element at a key 4.Exit Enter your choice: 1 Enter element to be inserted: 1 Enter key at which element to be inserted: 1 1.Insert element into the table 2.Search element from the key 3.Delete element at a key 4.Exit Enter your choice: 1 Enter element to be inserted: 2 Enter key at which element to be inserted: 2 1.Insert element into the table 2.Search element from the key 3.Delete element at a key 4.Exit Enter your choice: 1 Enter element to be inserted: 4 Enter key at which element to be inserted: 5 1.Insert element into the table 2.Search element from the key 3.Delete element at a key 4.Exit Enter your choice: 1 Enter element to be inserted: 7 Enter key at which element to be inserted: 6 1.Insert element into the table 2.Search element from the key 3.Delete element at a key 4.Exit Enter your choice: 2 Enter key of the element to be searched: 7 No element found at key 7 1.Insert element into the table 2.Search element from the key 3.Delete element at a key 4.Exit Enter your choice: 2 Enter key of the element to be searched: 6 Element at key 6 : 7 1.Insert element into the table 2.Search element from the key 3.Delete element at a key 4.Exit Enter your choice: 3 Enter key of the element to be deleted: 1 Element Deleted 1.Insert element into the table 2.Search element from the key 3.Delete element at a key 4.Exit Enter your choice: 4