散列表的设计与实现

#includestdio.h#includestdlib.h#includestring#includewindows.h#defineMAXSIZE20#defineMAX_SIZE20#defineHASHSIZE53#defineSUCCESS1#defineUNSUCCESS-1#defineLENsizeof(HashTable)typedefintStatus;typedefcharNA[MAX_SIZE];typedefstruct{NAname;NAtel;NAadd;}Record;typedefstruct{Record*elem[HASHSIZE];intcount;intsize;}HashTable;Statuseq(NAx,NAy){if(strcmp(x,y)==0)returnSUCCESS;elsereturnUNSUCCESS;}StatusNUM_BER;voidgetin(Record*a){printf(输入要添加的个数：\n);scanf(%d,&NUM_BER);inti;for(i=0;iNUM_BER;i++){printf(请输入第%d个记录的用户名:\n,i+1);scanf(%s,a[i].name);printf(请输入%d个记录的电话号码:\n,i+1);scanf(%s,a[i].tel);printf(请输入第%d个记录的地址:\n,i+1);scanf(%s,a[i].add);}}voidShowInformation(Record*a){inti;for(i=0;iNUM_BER;i++)printf(\n第%d个用户信息:\n姓名：%s\n电话号码：%s\n联系地址：%s\n,i+1,a[i].name,a[i].tel,a[i].add);}voidCls(Record*a){printf(*);system(cls);}longfold(NAs){//人名的折叠处理char*p;longsum=0;NAss;strcpy(ss,s);strupr(ss);p=ss;while(*p!='\0')sum+=*p++;printf(\nsum====================%d,sum);returnsum;}intHash1(NAstr){//哈希函数longn;intm;n=fold(str);//先将用户名进行折叠处理m=n%HASHSIZE;returnm;}intHash2(NAstr){//哈希函数longn;intm;n=atoi(str);//把字符串转换成整型数.m=n%HASHSIZE;returnm;//并返回模值}Statuscollision(intp,int&c){//冲突处理函数，inti,q;i=c/2+1;while(iHASHSIZE){if(c%2==0){c++;q=(p+i*i)%HASHSIZE;if(q=0)returnq;elsei=c/2+1;}else{q=(p-i*i)%HASHSIZE;c++;if(q=0)returnq;elsei=c/2+1;}}returnUNSUCCESS;}voidbenGetTime();voidCreateHash1(HashTable*H,Record*a){benGetTime();inti,p=-1,c,pp;for(i=0;iNUM_BER;i++){c=0;p=Hash1(a[i].name);pp=p;while(H-elem[pp]!=NULL){pp=collision(p,c);if(pp0){printf(第%d记录无法解决冲突,i+1);continue;}}H-elem[pp]=&(a[i]);H-count++;printf(第%d个记录冲突次数为%d。\n,i+1,c);//需要显示冲突次数时输出}printf(\n建表完成!\n此哈希表容量为%d,当前表内存储的记录个数为%d.\n,HASHSIZE,H-count);benGetTime();}voidSearchHash1(HashTable*H,int&c){benGetTime();NAstr;printf(\n请输入要查找记录的姓名：\n);scanf(%s,str);intp,pp;p=Hash1(str);pp=p;while((H-elem[pp]!=NULL)&&(eq(str,H-elem[pp]-name)==-1))pp=collision(p,c);if(H-elem[pp]!=NULL&&eq(str,H-elem[pp]-name)==1){printf(\n查找成功！\n查找过程冲突次数为%d．以下是您需要要查找的信息：\n\n,c);printf(姓名：%s\n电话号码：%s\n联系地址：%s\n,H-elem[pp]-name,H-elem[pp]-tel,H-elem[pp]-add);}elseprintf(\n此人不存在，查找不成功!\n);benGetTime();}voidbenGetTime(){SYSTEMTIMEsys;GetLocalTime(&sys);printf(%4d/%02d/%02d%02d:%02d:%02d.%03d\n,sys.wYear,sys.wMonth,sys.wDay,sys.wHour,sys.wMinute,sys.wSecond,sys.wMilliseconds);}voidCreateHash2(HashTable*H,Record*a){benGetTime();inti,p=-1,c,pp;for(i=0;iNUM_BER;i++){c=0;p=Hash2(a[i].tel);pp=p;while(H-elem[pp]!=NULL){pp=collision(p,c);if(pp0){printf(第%d记录无法解决冲突,i+1);//需要显示冲突次数时输出continue;}}H-elem[pp]=&(a[i]);H-count++;printf(第%d个记录冲突次数为%d。\n,i+1,c);//需要显示冲突次数时输出}printf(\n建表完成!\n此哈希表容量为%d,当前表内存储的记录个数为%d.\n,HASHSIZE,H-count);benGetTime();}voidSearchHash2(HashTable*H,int&c){benGetTime();NAtele;printf(\n请输入要查找记录的电话号码：\n);scanf(%s,tele);intp,pp;p=Hash2(tele);pp=p;while((H-elem[pp]!=NULL)&&(eq(tele,H-elem[pp]-tel)==-1))pp=collision(p,c);if(H-elem[pp]!=NULL&&eq(tele,H-elem[pp]-tel)==1){printf(\n查找成功！\n查找过程冲突次数为%d．以下是您需要要查找的信息：\n\n,c);printf(姓名：%s\n电话号码：%s\n联系地址：%s\n,H-elem[pp]-name,H-elem[pp]-tel,H-elem[pp]-add);}elseprintf(\n此人不存在，查找不成功!\n);benGetTime();}voidSave(){FILE*fp;if((fp=fopen(c:\test.txt,w))==NULL){printf(\nERRORopeningcustometfile);}fclose(fp);}intmain(intargc,char*argv[]){intc,flag=1;HashTable*H;H=(HashTable*)malloc(LEN);for(inti=0;iHASHSIZE;i++)H-elem[i]=NULL;H-size=HASHSIZE;H-count=0;Recorda[MAXSIZE];while(1){printf(\n┏━━━━━━━━━━━━━┓);printf(\n┃欢迎使用电话号码查找系统┃);printf(\n┏〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┓);printf(\n┃★★★★★★★哈希表的设计与实现★★★★★★★┃);printf(\n┃【1】.添加用户信息┃);printf(\n┃【2】.读取所有用户信息┃);printf(\n┃【3】.以姓名建立哈希表(再哈希法解决冲突)┃);printf(\n┃【4】.以电话号码建立哈希表(再哈希法解决冲突)┃);printf(\n┃【5】.查找并显示给定用户名的记录┃);printf(\n┃【6】.查找并显示给定电话号码的记录┃);printf(\n┃【7】.清屏┃);printf(\n┃【8】.保存┃);printf(\n┃【9】.退出程序┃);printf(\n┃温馨提示：┃);printf(\n┃Ⅰ.进行5操作前请先输出3┃);printf(\n┃Ⅱ.进行6操作前请先输出4┃);printf(\n┗〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┛);printf(\n);printf(请输入一个任务选项);printf(\n);intnum;scanf(%d,&num);switch(num){case1:getin(a);break;case2:ShowInformation(a);break;case3:CreateHash1(H,a);/*以姓名建立哈希表*/break;case4:CreateHash2(H,a);/*以电话号码建立哈希表*/break;case5:c=0;SearchHash1(H,c);break;case6:c=0;SearchHash2(H,c);break;case7:Cls(a);break;case8:Save();break;case9:return0;break;default:printf(你输错了，请重新输入!);printf(\n);}}system(pause);return0;}