实验内容：
采用除留余数法实现哈希表的创建，任意采用一种处理冲突的方法解决冲突，计算哈希表的平均查找长度。编程实现以下功能：
已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)，哈希函数定义为：H(key)=key MOD 13, 哈希表长为m=16。实现该哈希表的散列，并计算平均查找长度（设每个记录的查找概率相等）。
（1）哈希表定义为定长的数组结构；
（2）使用线性探测再散列或链地址法解决冲突；
（3）散列完成后在屏幕上输出数组内容或链表；
（4）输出等概率查找下的平均查找长度；
（5）完成散列后，输入关键字完成查找操作，要分别测试查找成功与查找不成功两种情况。
算法设计思路
1.建造哈希结构
#define m 16//哈希表的长度
typedef struct {
int date;//关键字
int cent=0;//来表示表内是否含有数据
int flag=0;//用来控制递归
}HashTable[m];
int sum=0;//用来计算平均查找长度
2.私下根据哈希函数将关键字存放
3.线性探测解决冲突
void CreateHash(HashTable &Hash,int x)//线性探测散列
{
int y = x % 13;//H(key)=key MOD 13
int flag = 1;
while(flag){
if (Hash[y].cent == 0)//判断是否已经存入数据
{
Hash[y].date = x;
Hash[y].cent = 1;
flag = 0;
sum++;
}
y++;
}
}
4.折半查找法
void Search(HashTable Hash,int key)//搜查关键词
{
int min = 0;
int max = m;
int t = key % 13;//key应该存放的位置
while(min<=max)
{
int mid = (max + min) / 2;
if (t == (Hash[mid].date)%13&&key==Hash[mid].date)
{
cout << "查找成功：" << mid << endl;
return;
}
else if (t > (Hash[mid].date % 13))
{
min = mid;
}
else { max = mid; }
}
cout << "无目标值：" << endl;
return;
}
全部源代码
#include
using namespace std;
#define m 16//哈希表的长度
typedef struct {
int date;//关键字
int cent=0;//来表示表内是否含有数据
}HashTable[m];
int sum=0;//用来计算平均查找长度
void CreateHash(HashTable &Hash,int x)//线性探测散列
{
int y = x % 13;//H(key)=key MOD 13
int flag = 1;
while(flag){
if (Hash[y].cent == 0)//判断是否已经存入数据
{
Hash[y].date = x;
Hash[y].cent = 1;
flag = 0;
sum++;
}
y++;
}
}
void Search(HashTable Hash,int key)//搜查关键词
{
int min = 0;
int max = m;
int t = key % 13;//key应该存放的位置
while (min <= max)
{
int mid = (max + min) / 2;
if (t == (Hash[mid].date) % 13 && key == Hash[mid].date)
{
cout << "查找成功：" << mid << endl;
return;
}
else if (t > (Hash[mid].date % 13))
{
min = mid;
}
else { max = mid; }
}
cout << "无目标值：" << endl;
return;
}
int main()
{
HashTable Hash;
int n = 12;
cout << "请输入存放的关键字：" << endl;
while (n--)
{
int x;
cin >> x;
CreateHash(Hash, x);
}
cout << "散列完成后的数组内容:" << endl;
for (int i = 0; i < m; i++)
{
cout << Hash[i].date << " ";
}
cout << "\n";
cout << "请输入要查找的关键字：" << endl;
int k;
cin >> k;
Search(Hash, k);
return 0;
}
运行截图
精彩内容
发表评论