哈希表应用实例
#ifndef _HashTest_H_#define _HashTest_H_#define NAME_NO 30#define HASH_LENGTH 50#define M 50;typedef struct { char *py; //名字的拼音int k; //拼音所对应的整数}NAME;typedef struct //哈希表{ char *py; //名字的拼音int k; //拼音所对应的整数int si; //查找长度}HASH;#endif
4：主要算法设计
（1）姓名（结构体数组）初始化
名字以拼音的形式够成字符串，将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字。
void InitNameList() { char *f; int r,s0,i; NameList[0].py="chenliang";//陈亮 NameList[1].py="chenyuanhao";//陈元浩 NameList[2].py="chengwenliang";//程文亮 NameList[3].py="dinglei";//丁磊 NameList[4].py="fenghanzao";//冯汉枣 NameList[5].py="fuzongkai";//付宗楷 NameList[6].py="hujingbin";//胡劲斌 NameList[7].py="huangjianwu";//黄建武 NameList[8].py="lailaifa";//赖来发 NameList[9].py="lijiahao";//李嘉豪 NameList[10].py="liangxiaocong";//梁晓聪 NameList[11].py="linchunhua";//林春华 NameList[12].py="liujianhui";//刘建辉 NameList[13].py="luzhijian";//卢志健 NameList[14].py="luonan";//罗楠 NameList[15].py="quegaoxiang";//阙高翔 NameList[16].py="sugan";//苏淦 NameList[17].py="suzhiqiang";//苏志强 NameList[18].py="taojiayang";//陶嘉阳 NameList[19].py="wujiawen";//吴嘉文 NameList[20].py="xiaozhuomin";//肖卓明 NameList[21].py="xujinfeng"; //许金峰 NameList[22].py="yanghaichun";//杨海春 NameList[23].py="yeweixiong";//叶维雄 NameList[24].py="zengwei";//曾玮 NameList[25].py="zhengyongbin";//郑雍斌 NameList[26].py="zhongminghua";//钟明华 NameList[27].py="chenliyan";//陈利燕 NameList[28].py="liuxiaohui";//刘晓慧 NameList[29].py="panjinmei";//潘金梅 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;} }(2) 建立哈希表
用除留余数法构建哈希函数，用伪随机探测再散列法处理冲突
void CreateHashList() {int i; for(i=0; i<HASH_LENGTH;i++) { HashList[i].py="";HashList[i].k=0;HashList[i].si=0;} for(i=0;i<HASH_LENGTH;i++){ int sum=0; int adr=(NameList[i].k)%M;//哈希函数 int d=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;}}}(3) 查找哈希表
在哈希表中进行查找，输出查找的结果和关键字，并计算和输出查找成功的平均查找长度
void FindList() //查找 {char name[20]={0}; int s0=0,r,sum=1,adr,d; printf("请输入姓名的拼音:"); 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); else if (HashList[adr].k==0) printf("无此记录!"); else{ int g=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); g=1; }}while(g==0); } }(4) 显示哈希表
void Display() {int i;float average=0;printf("\n地址\t关键字\t\t搜索长度\tH(key)\t 姓名\n"); //显示的格式for(i=0; i<50; i++){ printf("%d ",i); printf("\t%d ",HashList[i].k);printf("\t\t%d ",HashList[i].si);printf("\t\t%d ",HashList[i].k%30);printf("\t %s ",HashList[i].py);printf("\n");}for(i=0;i<HASH_LENGTH;i++)average+=HashList[i].si; average/=NAME_NO;pri(5) 主函数
void main(){char ch1;InitNameList(); CreateHashList (); do{printf("D. 显示哈希表\nF. 查找\nQ. 退出\n请选择： ");cin>>&ch1;switch(ch1){case 'D':Display(); cout<<endl;break;case 'F':FindList();cout<<endl;break;case 'Q':exit(0);}cout<<"come on !(y/n):";cin>>&ch1;}while(ch1!='n'); }