下面分享关于哈希系统开发的一些代码,包括系统组成、关联以及系统开发过程,有需求或者问题欢迎留言、咨询。
include<stdio.h>
include
include<conio.h>
using namespace std;
define HASH_LEN 50 //哈希表的长度
define M 47 //随机数
intNAME_NO=34; //城市名的个数
typedef struct
{
char*py; //名字的拼音
intk; //拼音所对应的整数
}NAME;
NAME NameList[HASH_LEN]; //全局变量NAME
typedef struct //哈希表
{
char*py; //名字的拼音
intk; //拼音所对应的整数
intsi; //查找长度
}HASH;
HASH HashList[HASH_LEN]; //全局变量HASH
void InitNameList() //姓名(结构体数组)初始化
{
char*f;
intr,s0,i;
NameList[0].py="harbin";
NameList[1].py="shijiazhuang";
NameList[2].py="lanzhou";
NameList[3].py="kunming";
NameList[4].py="chengdu";
NameList[5].py="changchun";
NameList[6].py="shenyang";
NameList[7].py="xining";
NameList[8].py="xian";
NameList[9].py="zhengzhou";
NameList[10].py="jinan";
NameList[11].py="taiyuan";
NameList[12].py="hefei";
NameList[13].py="wuhan";
NameList[14].py="changsha";
NameList[15].py="nanjing";
NameList[16].py="guiyang";
NameList[17].py="nanning";
NameList[18].py="hangzhou";
NameList[19].py="nanchang";
NameList[20].py="guangzhou";
NameList[21].py="fuzhou";
NameList[22].py="taipei";
NameList[23].py="haikou";
NameList[24].py="huhhot";
NameList[25].py="yinchuan";
NameList[26].py="urumqi";
NameList[27].py="lahsa";
NameList[28].py="macau";
NameList[29].py="beijing";
NameList[30].py="shanghai";
NameList[31].py="hongkong";
NameList[32].py="tianjin";
NameList[33].py="chongqing";
for (i=0;i<NAME_NO;i++)
{
s0=0;
f=NameList[i].py;
for (r=0;*(f+r)!='\0';r++)
/ 方法:将字符串的各个字符所对应的ASCII码相加,所得的整数做为哈希表的关键字/
s0=*(f+r)+s0;
NameList[i].k=s0;
}
}
void CreateHashList() //建立哈希表
{
inti;
for (i=0; i<HASH_LEN;i++)
{
HashList[i].py="";
HashList[i].k=0;
HashList[i].si=0;
}
for (i=0;i<HASH_LEN;i++)
{
intsum=0;
intadr=(NameList[i].k)%M; //哈希函数
intd=adr;
if(HashList[adr].si==0) //如果不冲突
{
HashList[adr].k=NameList[i].k;
HashList[adr].py=NameList[i].py;
HashList[adr].si=1;
}
else //冲突
{
do
{
d=(d+NameList[i].k%10+1)%M; //伪随机探测再散列法处理冲突
sum=sum+1; //查找次数加1
}while (HashList[d].k!=0);
HashList[d].k=NameList[i].k;
HashList[d].py=NameList[i].py;
HashList[d].si=sum+1;
}
}
}
intFindList() //查找
{
charname[20]={0};
ints0=0,r,sum=1,adr,d;
printf("\n请输入城市名称:");
scanf("%s",name);
for (r=0;r<20;r++) //求出姓名的拼音所对应的整数(关键字)
s0+=name[r];
adr=s0%M; //使用哈希函数
d=adr;
if(HashList[adr].k==s0) //分3种情况进行判断
{
printf("\n名称:%s 关键字:%d 查找长度为: 1",HashList[d].py,s0);
cout<<endl;
return 0;
}
else if (HashList[adr].k==0)
{
printf("无此记录!");
cout<<endl;
return 1;
}
else
{
intg=0;
do
{
d=(d+s0%10+1)%M; //伪随机探测再散列法处理冲突
sum=sum+1;
if (HashList[d].k==0)
{
printf("无此记录! ");
cout<<endl;
g=1;
return 1;
}
if (HashList[d].k==s0)
{
printf("\n名称:%s 关键字:%d 查找长度为:%d",HashList[d].py,s0,sum);
cout<<endl;
g=1;
return 0;
}
}while(g==0);
}
}
void Display() // 显示哈希表
{
inti;
floataverage=0;
for(i=0; i<HASH_LEN; i++)
{
if(HashList[i].k%M==0)
HashList[i].py="";
}
printf("\n\n地址\t关键字\t\t搜索长度\tH(key)\t 名称\n"); //显示的格式
for(i=0; i<HASH_LEN; i++)
{
printf("%d ",i);
printf("\t%d ",HashList[i].k);
printf("\t\t%d ",HashList[i].si);
printf("\t\t%d ",HashList[i].k%M);
printf("\t %s ",HashList[i].py);
//cout<<" "<<HashList[i].py<<endl;
printf("\n");
//cout<<i<<" "<<HashList[i].k<<" "<<HashList[i].si<<" "<<HashList[i].k%M<<" "<<HashList[i].py<<endl;
}
for (i=0;i<HASH_LEN;i++)
average+=HashList[i].si;
average/=NAME_NO;
printf("\n\n平均查找长度:ASL(%d)=%f \n\n",NAME_NO,average);
}
void DeleteList()
{
charname[20]={0};
ints0=0,r,sum=1,adr,d;
printf("\n请输入城市名称:");
scanf("%s",name);
for (r=0;r<20;r++) //求出姓名的拼音所对应的整数(关键字)
s0+=name[r];
adr=s0%M; //使用哈希函数
d=adr;
if(HashList[adr].k==s0) //分3种情况进行判断
{
printf("\n名称:%s 关键字:%d 查找长度为: 1",HashList[d].py,s0);
cout<<endl;
cout<<"删除成功!"<<endl;
s0=0;
HashList[d].py=""; //名字的拼音
HashList[d].k=0; //拼音所对应的整数
HashList[d].si=0;
}
else if (HashList[adr].k==0)
printf("无此记录!无法执行删除操作!");
else
{
intg=0;
do
{
d=(d+s0%10+1)%M; //伪随机探测再散列法处理冲突
sum=sum+1;
if (HashList[d].k==0)
{
printf("无此记录!无法执行删除操作!");
g=1;
}
if (HashList[d].k==s0)
{
printf("\n名称:%s 关键字:%d 查找长度为:%d",HashList[d].py,s0,sum);
cout<<endl;
cout<<"已删除成功!"<<endl;
s0=0;
HashList[d].py=""; //名字的拼音
HashList[d].k=0; //拼音所对应的整数
HashList[d].si=0;
//Display();
g=1;
}
}while(g==0);
}
}
void EnterList()
{
/*char name[20]={0};
int s0=0,r,sum=1,adr,d,h;
printf("\n请输入姓名的拼音:");
scanf("%s",name);
for (r=0;r<20;r++) //求出姓名的拼音所对应的整数(关键字)
s0+=name[r];*/
charst[20];
char*xin;
xin=st;
ints0=0,r,sum=1,adr,d,h;
printf("\n请输入城市名称的拼音:");
cin>>xin;
//cout<<xin<<endl;
for (r=0;*(xin+r)!='\0';r++)
{
/ 方法:将字符串的各个字符所对应的ASCII码相加,所得的整数做为哈希表的关键字/
s0=(int)(*(xin+r))+s0;
}
//cout<<s0<<endl;
adr=s0%M; //使用哈希函数
d=adr;
if(HashList[adr].k==s0) //分3种情况进行判断
{
printf("\n名称:%s 关键字:%d 查找长度为: 1",HashList[d].py,s0);
cout<<endl;
cout<<"已存在于表中,无需插入!"<<endl;
}
else if (HashList[d].k==0)
{
printf("插入成功!");
HashList[d].py=xin;
HashList[d].k=s0;
HashList[d].si=1;
h=1;
cout<<endl;
}
else
{
intg=0,h=0;
do
{
d=(d+s0%10+1)%M; //伪随机探测再散列法处理冲突
sum=sum+1;
if (HashList[d].k==0)
{
printf("插入成功!");
HashList[d].py=xin;
HashList[d].k=s0;
HashList[d].si=sum;
h=1;
cout<<endl;
g=1;
}
if (HashList[d].k==s0)
{
printf("\n名称:%s 关键字:%d 查找长度为:%d",HashList[d].py,s0,sum);
cout<<endl;
cout<<"已存在于表中,无需插入!"<<endl;
g=1;
}
}while(g==0);
}
if(h==0)
return;
else
{
NAME_NO++;
NameList[NAME_NO-1].py=xin;
intsum=0;
intadr=(NameList[NAME_NO-1].k)%M; //哈希函数
intd=adr;
if(HashList[adr].si==0) //如果不冲突
{
HashList[adr].k=NameList[NAME_NO-1].k;
HashList[adr].py=NameList[NAME_NO-1].py;
HashList[adr].si=1;
}
else //冲突
{
do
{
d=(d+NameList[NAME_NO-1].k%10+1)%M; //伪随机探测再散列法处理冲突
sum=sum+1; //查找次数加1
}while (HashList[d].k!=0);
HashList[d].k=NameList[NAME_NO-1].k;
HashList[d].py=NameList[NAME_NO-1].py;
HashList[d].si=sum+1;
}
}
}
void main()
{
charch1;
printf("\n 哈希表\n");
printf(" -------------------------------------------\n");
printf(" | D. 显示哈希表 |\n");
printf(" | F. 查找 |\n");
printf(" | S. 删除 |\n");
printf(" | E. 插入 |\n");
printf(" | Q. 退出 |\n");
printf(" -------------------------------------------\n");
InitNameList();
CreateHashList ();
while(1)
{
printf("\n Option-:");
fflush(stdin);
ch1=getchar();
if (ch1=='D'||ch1=='d')
Display();
else if (ch1=='F'||ch1=='f')
FindList();
else if (ch1=='S'||ch1=='s')
DeleteList();
else if (ch1=='E'||ch1=='e')
EnterList();
else if (ch1=='Q'||ch1=='q')
return;
else
{
printf("\n请输入正确的选择!");
}
}
}