数据结构课程设计--哈希表实验报告

福建工程学院课程设计课程：算法与数据结构题目：哈希表专业：网络工程班级：xxxxxx班座号：xxxxxxxxxxxx姓名：xxxxxxx2011年12月31日实验题目：哈希表一、要解决的问题针对同班同学信息设计一个通讯录，学生信息有姓名，学号，电话号码等。以学生姓名为关键字设计哈希表，并完成相应的建表和查表程序。基本要求：姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。完成按姓名查询的操作。运行的环境：MicrosoftVisualC++6.0二、算法基本思想描述设计一个哈希表（哈希表内的元素为自定义的结构体）用来存放待填入的30个人名，人名为中国姓名的汉语拼音形式，用除留余数法构造哈希函数，用线性探查法解决哈希冲突。建立哈希表并且将其显示出来。通过要查找的关键字用哈希函数计算出相应的地址来查找人名。通过循环语句调用数组中保存的数据来显示哈希表。三、设计1、数据结构的设计和说明（1）结构体的定义typedefstruct//记录{NAname;NAxuehao;NAtel;}Record;录入信息结构体的定义，包含姓名，学号，电话号码。typedefstruct//哈希表{Record*elem[HASHSIZE];//数据元素存储基址intcount;//当前数据元素个数intsize;//当前容量}HashTable;哈希表元素的定义，包含数据元素存储基址、数据元素个数、当前容量。2、关键算法的设计（1）姓名的折叠处理longfold(NAs)//人名的折叠处理{char*p;longsum=0;NAss;strcpy(ss,s);//复制字符串，不改变原字符串的大小写strupr(ss);//将字符串ss转换为大写形式p=ss;while(*p!='\0')sum+=*p++;printf(\nsum====================%d,sum);returnsum;}（2）建立哈希表1、用除留余数法构建哈希函数2、用线性探测再散列法处理冲突intHash1(NAstr)//哈希函数{longn;intm;n=fold(str);//先将用户名进行折叠处理m=n%HASHSIZE;//折叠处理后的数，用除留余数法构造哈希函数returnm;//并返回模值}Statuscollision(intp,intc)//冲突处理函数，采用二次探测再散列法解决冲突{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)//建表，以人的姓名为关键字，建立相应的散列表{inti,p=-1,c,pp;system(cls);//若哈希地址冲突，进行冲突处理benGetTime();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();}（3）查找哈希表voidSearchHash1(HashTable*H,intc)//在通讯录里查找姓名关键字，若查找成功，显示信息{intp,pp;NAstr;system(cls);//c用来记录冲突次数,查找成功时显示冲突次数benGetTime();printf(\n请输入要查找记录的姓名：\n);scanf(%s,str);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]-xuehao,H-elem[pp]-tel);}elseprintf(\n此人不存在，查找不成功!\n);benGetTime();}（4）显示哈希表voidShowInformation(Record*a)//显示输入的用户信息{inti;system(cls);for(i=0;iNUM_BER;i++)printf(\n第%d个用户信息:\n姓名：%s\n学号：%s\n电话号码：%s\n,i+1,a[i].name,a[i].xuehao,a[i].tel);}（5）主函数的设计voidmain(intargc,char*argv[]){Recorda[MAXSIZE];intc,flag=1,i=0;HashTable*H;H=(HashTable*)malloc(LEN);for(i=0;iHASHSIZE;i++){H-elem[i]=NULL;H-size=HASHSIZE;H-count=0;}while(1){intnum;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(请输入一个任务选项);printf(\n);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;}3、模块结构图及各模块的功能：四、源程序清单：#includestdio.h#includestdlib.h#includestring.h#includewindows.h#defineMAXSIZE20#defineMAX_SIZE20#defineHASHSIZE53#defineSUCCESS1#defineUNSUCCESS-1#defineLENsizeof(HashTable)typedefintStatus;typedefcharNA[MAX_SIZE];typedefstruct{NAname;NAxuehao;NAtel;}Record;typedefstruct{Record*elem[HASHSIZE];intcount;intsize;}HashTable;Statuseq(NAx,NAy){if(strcmp(x,y)==0)returnSUCCESS;elsereturnUNSUCCESS;}StatusNUM_BER;voidgetin(Record*a){inti;system(cls);printf(输入要添加的个数：\n);scanf(%d,&NUM_BER);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].xuehao);printf(请输入第%d个记录的电话号码:\n,i+1);scanf(%s,a[i].tel);}}voidShowInformation(Record*a){inti;system(cls);for(i=0;iNUM_BER;i++)printf(\n第%d个用户信息:\n姓名：%s\n学号：%s\n电话号码：%s\n,i+1,a[i].name,a[i].xuehao,a[i].tel);}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,intc){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){inti,p=-1,c,pp;system(cls);benGetTime();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();}voidSearchH