数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究C++ 程序实现带有二次探查的哈希表
哈希表是一种用于存储键值对的数据结构。哈希表通过哈希函数计算元素插入或查找时位于数组中的索引。二次探查是开放寻址哈希表中的一种冲突解决技术。它的操作方法是使用二次多项式取哈希索引，然后递加其值，直到找到一个空的槽位。
此程序是 C++ 程序，用于实现带二次探查的哈希表。
算法
用于搜索键值
Begin Declare function SearchKey(int k, HashTable *ht) int pos = HashFunc(k, ht->s) intialize collisions = 0 while (ht->t[pos].info != Emp and ht->t[pos].e != k) pos = pos + 2 * ++collisions -1 if (pos >= ht->s) pos = pos - ht->s return pos End.
用于插入
Begin Declare function Insert(int k, HashTable *ht) int pos = SearchKey(k, ht) if (ht->t[pos].info != Legi) ht->t[pos].info = Legi ht->t[pos].e = k End.
用于显示
Begin Declare function display(HashTable *ht) for (int i = 0; i < ht->s; i++) int value = ht->t[i].e if (!value) print"Position: " print the current position Print" Element: Null" else print"Position: " print the current position Print" Element: " Print the element. End.
用于重新哈希函数
Begin Declare function Rehash(HashTable *ht) int s = ht->s HashTableEntry *t= ht->t ht= initiateTable(2 * s) for (int i = 0; i < s; i++) if (t[i].info == Legi) Insert(t[i].e, ht) free(t) return ht End. Source Code:
示例代码
#include <iostream>
#include <cstdlib>
#define T_S 10
using namespace std;
enum EntryType {
Legi, Emp, Del};
struct HashTableEntry {
int e;
enum EntryType info;
};
struct HashTable {
int s;
HashTableEntry *t;
};
bool isPrime (int n) {
if (n == 2 || n == 3)
return true;
if (n == 1 || n % 2 == 0)
return false;
for (int i = 3; i * i <= n; i += 2)
if (n % i == 0)
return false;
return true;
}
int nextPrime(int n) {
if (n <= 0)
n == 3;
if (n % 2 == 0)
n++;
for (; !isPrime( n ); n += 2);
return n;
}
int HashFunc(int k, int s) {
return k % s;
}
HashTable *initiateTable(int s) {
HashTable *ht;
if (s < T_S) {
cout<<"Table Size is Too Small"<<endl;
return NULL;
}
ht= new HashTable;
if (ht == NULL) {
cout<<"Out of Space"<<endl;
return NULL;
}
ht->s = nextPrime(s);
ht->t = new HashTableEntry [ht->s];
if (ht->t == NULL) {
cout<<"Table Size is Too Small"<<endl;
return NULL;
}
for (int i = 0; i < ht->s; i++) {
ht->t[i].info = Emp;
ht->t[i].e = NULL;
}
return ht;
}
int SearchKey(int k, HashTable *ht) {
int pos = HashFunc(k, ht->s);
int collisions = 0;
while (ht->t[pos].info != Emp && ht->t[pos].e != k) {
pos = pos + 2 * ++collisions -1;
if (pos >= ht->s)
pos = pos - ht->s;
}
return pos;
}
void Insert(int k, HashTable *ht) {
int pos = SearchKey(k, ht);
if (ht->t[pos].info != Legi) {
ht->t[pos].info = Legi;
ht->t[pos].e = k;
}
}
HashTable *Rehash(HashTable *ht) {
int s = ht->s;
HashTableEntry *t= ht->t;
ht= initiateTable(2 * s);
for (int i = 0; i < s; i++) {
if (t[i].info == Legi)
Insert(t[i].e, ht);
}
free(t);
return ht;
}
void display(HashTable *ht) {
for (int i = 0; i < ht->s; i++) {
int value = ht->t[i].e;
if (!value)
cout<<"Position: "<<i + 1<<" Element: Null"<<endl;
else
cout<<"Position: "<<i + 1<<" Element: "<<value<<endl;
}
}
int main() {
int v, s, pos, i = 1;
int c;
HashTable *ht;
while(1) {
cout<<"1.Initialize size of the table"<<endl;
cout<<"2.Insert element into the table"<<endl;
cout<<"3.Display Hash Table"<<endl;
cout<<"4.Rehash The Table"<<endl;
cout<<"5.Exit"<<endl;
cout<<"Enter your choice: ";
cin>>c;
switch(c) {
case 1:
cout<<"Enter size of the Hash Table: ";
cin>>s;
ht = initiateTable(s);
cout<<"Size of Hash Table: "<<nextPrime(s);
break;
case 2:
if (i > ht->s) {
cout<<"Table is Full, Rehash the table"<<endl;
continue;
}
cout<<"Enter element to be inserted: ";
cin>>v;
Insert(v, ht);
i++;
break;
case 3:
display(ht);
break;
case 4:
ht = Rehash(ht);
break;
case 5:
exit(1);
default:
cout<<"\nEnter correct option\n";
}
}
return 0;
}输出
1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 1 Enter size of the Hash Table: 4 Table Size is Too Small Size of Hash Table: 51.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 1 Enter size of the Hash Table: 10 Size of Hash Table: 111.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 1 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 2 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 3 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 4 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 5 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 6 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 7 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 8 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 9 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 10 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 11 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Table is Full, Rehash the table 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 3 Position: 1 Element: 11 Position: 2 Element: 1 Position: 3 Element: 2 Position: 4 Element: 3 Position: 5 Element: 4 Position: 6 Element: 5 Position: 7 Element: 6 Position: 8 Element: 7 Position: 9 Element: 8 Position: 10 Element: 9 Position: 11 Element: 10 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 4 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 3 Position: 1 Element: Null Position: 2 Element: 1 Position: 3 Element: 2 Position: 4 Element: 3 Position: 5 Element: 4 Position: 6 Element: 5 Position: 7 Element: 6 Position: 8 Element: 7 Position: 9 Element: 8 Position: 10 Element: 9 Position: 11 Element: 10 Position: 12 Element: 11 Position: 13 Element: Null Position: 14 Element: Null Position: 15 Element: Null Position: 16 Element: Null Position: 17 Element: Null Position: 18 Element: Null Position: 19 Element: Null Position: 20 Element: Null Position: 21 Element: Null Position: 22 Element: Null Position: 23 Element: Null 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 20 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 5
更新于：2019 年 7 月 30 日
2 千 + 次观看
广告