数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会学
时装
法学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
更新于: 30-7-2019
20K+ 浏览
广告