#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
#define N 20
#define M 50
using namespace std;
typedef struct hashnode //哈希表结点
{
int length; //结点中的字符串ASCII和
int times; //查找次数
int locate; //通过哈希函数求得得哈希表地址
char name[N]; //姓名字符串
}hashnode;
int d[M];
hashnode node[M];
int collision(int k,int count,int m) //处理地址冲突的函数
{
int hi;
hi=(k+d[count])%m;
return hi;
}
int sturnd(char string[]) //求出字符串的ASCII码值的总和
{
int count,l,len;
count=0;
len=strlen(string);
for(l=1;l<=len;l++)
count=count+string[l-1];
return count;
}
int hash(int k,int m) //利用哈希函数计算关键字在哈希表中的位置
{
int hk;
hk=k%m;
return hk;
}
int isprime(int d) //判断素数的函数，用来寻找满足条件的哈希表表长
{
int a,b;
a=d/2;
for(b=2;b<=a;b++)
if(d%b==0)
return 0;
if(b>=a)
return 1;
}
int main()
{
int m,n,i,k,p,q,c,max,f,number;
float find,asl;
char *cd;
cd=(char *)malloc(N*sizeof(char)); //存放字符串的临时变量
while(cout<<"请输入最大查找上限:")
{
cin>>max;
cout<<"请输入总人数:";
cin>>n;
number=n;
f=(int)n/(1.0-1.0/(2*max-1)); // 线性探测在散列查找成功的近似
while(!isprime(f)) //计算满足最大查找上限的表长，且表长为素数。
f++;
m=f; //m极为所除的余数 m为 表长
for(i=1;i<m;i++) //对线性查找数组赋初值
d[i]=i;
for(i=0;i<m;i++) //对哈希表赋初值
node[i].times=0; // //代表查找次数
cout<<"请输入姓名:"<<endl;
getchar();
while(n!=0) //依次对输入的字符串（人名）进行转换ASCII码并计算出在哈希表中位置并存储
{
gets(cd);
k=sturnd(cd); //k值相当于计算出的结果
p=hash(k,m); //p相当于余数
q=p;
c=1; //c代表比较的次数
while(node[q].times!=0) //当存放地址出现冲突时，利用线性探索再散列的方法寻找下一存放地址
{
q=collision(p,c,m); //处理地址冲突的函数
c++;
}
strcpy(node[q].name,cd); //将信息存放到哈希表中
node[q].length=k;
node[q].times=c;
node[q].locate=p;
n--;
}
find=0.0; //初始化
cout<<"请显示结果:"<<endl;
for(i=0;i<m;i++)
{
find=find+node[i].times; //计算最大查找上限
if(node[i].times!=0)
cout<<i<<" "<<node[i].length<<" "<<node[i].times<<" "<<node[i].locate<<" "<<node[i].name<<endl;
else
cout<<i<<endl;
}
asl=find/number; //平均查找长度为
cout<<"请输出平均查找长度:"<<endl;
cout<<"ASL="<<asl<<endl; //输出平均查找长度
}
system("pause");
return 0;
}
