数据结构哈希表的设计源代码

#include
#include
#include
#include
#include
#include
using namespace std;
int d[30],i,j;
#define HashList 50 //哈希表的长度；
#define p 47 //H(key)=k%p,p<=50;
#define NameList 30
class student
{
public:
void init_name();
void display_name();
char *p1;
int m;
};
student name[NameList];
void student::init_name()
{

name[0].p1="beitao";
name[1].p1="danglei";
name[2].p1="cuihaiqing";
name[3].p1="lukun";
name[4].p1="qinhao";
name[5].p1="zhanyujia";
name[6].p1="zhaoqingling";
name[7].p1="yangxia";
name[8].p1="yangbingyu";
name[9].p1="tianyi";
name[10].p1="liyali";
name[11].p1="fanxiaohui";
name[12].p1="gaoyang";
name[13].p1="huojianhua";
name[14].p1="wanglu";
name[15].p1="jiangguoqi";
name[16].p1="qianqingwei";
name[17].p1="peishuo";
name[18].p1="zhangmengjuan";
name[19].p1="liudongxue";
name[20].p1="taoxiaohui";
name[21].p1="lisiyi";
name[22].p1="renlinan";
name[23].p1="yinlipeng";
name[24].p1="lipengwei";
name[25].p1="zhanghui";
name[26].p1="zhangtianshuo";
name[27].p1="qizhongyu";
name[28].p1="zhuangxinning";
name[29].p1="mameiling";
for(i=0;i{
char *a=name[i].p1;
int s=0;
for(j=0;*(a+j)!='\0';j++)
{
s+=toascii(*(a+j)); //toascii计算拼音的关键码
}
name[i].m=s;
}

}
void student::display_name()
{
system("cls");
cout<<"\n地址 \t\t 姓名 \t\t关键字\n";
for (i=0;icout<}
class Hash
{
public:
void init_hash();
void display_hashlist();
void find();
char *m;
int n;
int s;
};
Hash hash[HashList];
void Hash::init_hash() //建立哈希表
{
for(i=0;i{
hash[i].m ="\0";
hash[i].n=0;
hash[i].s=0;
}
for(i=0;i{
int sum=1,j=0;
int a=(name[i].m)%p; //除留余数法
if(hash[a].n==0)
{
hash[a].m=name[i].p1;
hash[a].n=name[i].m;
hash[a].s=1;
}
else
{
while(hash[a].n!=0)
{
//再散列法处理冲突
a=(a+d[j++])%HashList;
sum=sum+1;
}
hash[a].m=name[i].p1;
hash[a].n=name[i].m;
hash[a].s=sum;
}
}
}
void Hash::display_hashlist()
{
system("cls");
float ASL=0.0;
cout<<"\n\n地址 \t\t 姓名\t\t关键字 \t 搜索次数\n";//显示的格式
for (i=0;i{
cout<ASL+=hash[i].s;
}
ASL=ASL/NameList; //求得ASL
cout<<"\n\n平均查找长度：ASL="<}
void Hash::find()
{
char name[20]={0}; //注意初始化
int a,s=0;
int sum=1;
cout<<"请输入你要查询的名字:";
scanf("%s",name);
for(i=0;i<20;i++)
{
s+=toascii(name[i]);
}
a=s%p;
i=0;
if(hash[a].n==s&&!strcmp(hash[a].m,name))
{
cout<

键字:"<}
else if(hash[a].n==0)
{
cout<<"没有要查的人!"<}
else
{
while(1)
{
//再散列法处理冲突
a=(a+d[i++])%HashList;
sum=sum+1;
if(hash[a].n==0)
{
cout<<"没有要查的人!"<break;
}
if(hash[a].n==s && !strcmp(hash[a].m,name))
{
cout<break;
}
}
}
}

void main()
{
int i;
srand((int)time(0)); //产生随机数种子
for(i=0;i<30;i++) //用随机函数求得伪随机数列d[i]（在1到50之间）
d[i]=1+(int)(HashList*rand()/(RAND_MAX+1.0)); //RAND_MAX其值最小为32767,最大为2147483647
student a; //学生类的对象
a.init_name(); //初始化姓名的方法
Hash b; //哈希表类的对象
b.init_hash(); //创建哈希表方法
system("color 0b");
while(1)
{
cout<cout<<"\t\t\t 1. 显示姓名表"<cout<<"\t\t\t 2. 显示哈希表"<cout<<"\t\t\t 3. 查找"<cout<<"\t\t\t 4. 退出"<cout<<"\n\t\t 输入你的操作:";
int c;
cin>>c;
switch(c) //根据选择进行判断，直到选择退出时才可以退出
{
case 1:
a.display_name(); // 调用显示学生姓名的方法
break;
case 2:
b.display_hashlist(); //调用显示哈希表的方法
break;
case 3:
b.find();
break;
case 4:
exit(0);
break;
}
}
}