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

福建工课程课程：算法与数据结构题目哈希表专业：网络工程班级：xxxxxx班座号：xxxxxxxxxxxx姓名：xxxxxxx2011 年 12 月 31日实验题目：哈希表一、要解决的问题针对同班同学信息设计一个通讯录，学生信息有姓名，学号，电话号码等。以学生姓名为关键字设计哈希 表，并完成相应的建表和查表程序。基本要求：姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或 链地址法处理冲突；在查找的过程中给出比较的次数。完成按姓名查询的操作。运行的环境：Microsoft Visual C+ 6.0二、算法基本思想描述设计一个哈希表（哈希表内的元素为自定义的结构体）用来存放待填入的30个人名，人名为中国姓名的汉 语拼音形式，用除留余数法构造哈希函数，用线性探查法解决哈希冲突。建立哈希表并且将其显示出来。通过要 查找的关键字用哈希函数计算出相应的地址来查找人名。通过循环语句调用数组中保存的数据来显示哈希表。三、设计1、数据结构的设计和说明（1）结构体的定义typedef struct/记录NA name;NA xuehao;NA tel;Record; 录入信息结构体的定义，包含姓名，学号，电话号码。 typedef struct/哈希表Record *elemHASHSIZE;/数据元素存储基址int count;/当前数据元素个数int size;/ 当前容量HashTable; 哈希表元素的定义，包含数据元素存储基址、数据元素个数、当前容量。2、关键算法的设计(1)姓名的折叠处理long fold(NA s)/人名的折叠处理char *p;long sum=0;NA ss;strcpy(ss,s);/复制字符串，不改变原字符串的大小写strupr(ss);/将字符串 ss 转换为大写形式p=ss;while(*p!=0)sum+=*p+; printf(nsum=%d,sum);return sum;(2)建立哈希表1、用除留余数法构建哈希函数 2、用线性探测再散列法处理冲突 int Hash1(NA str) /哈希函数long n;int m;n=fold(str);/先将用户名进行折叠处理m=n%HASHSIZE;/折叠处理后的数，用除留余数法构造哈希函数return m;/并返回模值Status collision(int p,int c)/冲突处理函数，采用二次探测再散列法解决冲突int i,q;i=c/2+1;while(i=0) return q;else i=c/2+1;elseq=(p-i*i)%HASHSIZE;c+;if(q=0) return q;else i=c/2+1;return UNSUCCESS;void benGetTime();void CreateHash1(HashTable* H,Record* a) int i,p=-1,c,pp;system(cls); benGetTime();for(i=0;ielempp!=NULL) pp=collision(p,c);if(ppelempp=&(ai);H-count+;printf(第d个记录冲突次数为d。n,i+1,c);/建表，以人的姓名为关键字，建立相应的散列表/若哈希地址冲突，进行冲突处理/需要显示冲突次数时输出/无法解决冲突，跳入下一循环/求得哈希地址，将信息存入/需要显示冲突次数时输出printf(n建表完成!n此哈希表容量为%d，当前表内存储的记录个数为d.n,HASHSIZE,H-count); benGetTime();(3)查找哈希表void SearchHash1(HashTable* H,int c) int p,pp;NA str;system(cls);benGetTime();printf(n请输入要查找记录的姓名：n); scanf(%s,str);/在通讯录里查找姓名关键字，若查找成功，显示信息/c 用来记录冲突次数,查找成功时显示冲突次数p=Hash1(str);pp=p;while(H-elempp!=NULL)&(eq(str,H-elempp-name)=-1)pp=collision(p,c);if(H-elempp!=NULL&eq(str,H-elempp-name)=1)printf(n查找成功！ n查找过程冲突次数为d.以下是您需要要查找的信息：nn,c);printf(姓 名：%sn 学号：%sn 电话号码：sn,H-elempp-name,H-elempp-xuehao,H-elempp-tel);else printf(n此人不存在，查找不成功!n);benGetTime();(4)显示哈希表void ShowInformation(Record* a)/显示输入的用户信息int i;for( i=0;iNUM_BER;i+) printf(n第小个用户信息:n姓(5)主函数的设计名：sn 学号：sn 电话号码：sn,i+l,ai.name,ai.xuehao,ai.tel);void main(int argc, char* argv) Record aMAXSIZE;int c,flag=l,i=0;HashTable *H;H=(HashTable*)malloc(LEN);for(i=0;ielemi=NULL;H-size=HASHSIZE;H-count=0;while (l) int num;printf(n printf(n printf(n printf(n printf(n printf(n printf(n printf(n printf(n printf(n printf(n printf(n printf(n printf(n printf(n printf(n);printf(”请输入一个任务选项); printf(n);scanf(%d,&num););欢迎使用同学通讯录录入查找系统哈希表的设计与实现);【l】.添加用户信息【2】.读取所有用户信息【3】.以姓名建立哈希表(再哈希法解决冲突););););【4】.以电话号码建立哈希表(再哈希法解决冲突) );【5】.查找并显示给定用户名的记录【6】.查找并显示给定电话号码的记录【7】.清屏【8】.保存【9】.退出程序温馨提示：I 进行5操作前请先输出3II 进行6操作前请先输出4););););););););switch(num)case l:getin(a);break;case 2:ShowInformation(a); break;case 3:CreateHashl(H,a); /* 以姓名建立哈希表 */ break;case 4:CreateHash2(H,a); /* 以电话号码建立哈希表 */case 5:c=0;SearchHash1(H,c);break;case 6:c=0;SearchHash2(H,c);break;case 7:Cls(a);break;case 8:Save();break;case 9:return 0;break;default:printf(你输错了，请重新输入!); printf(n);system(pause);return 0;3、模块结构图及各模块的功能：四、源程序清单：#include#include#include#include #define MAXSIZE 20#define MAX_SIZE 20#define HASHSIZE 53#define SUCCESS 1#define UNSUCCESS -1#define LEN sizeof(HashTable)typedef int Status;typedef char NAMAX_SIZE;typedef structNA name;NA xuehao;NA tel;Record;typedef struct Record *elemHASHSIZE; int count;int size;HashTable;Status eq(NA x,NA y) if(strcmp(x,y)=0)return SUCCESS;else return UNSUCCESS; Status NUM_BER; void getin(Record* a) int i;system(cls);printf(输入要添加的个数：n); scanf(%d,&NUM_BER);for(i=0;iNUM_BER;i+)printf (请输入第%d个记录的姓名：n,i+l); scanf(%s,ai.name);prin tf(请输入%小个记录的学号:n,i+l); scanf(%s,ai.xuehao);prin tf(请输入第%d个记录的电话号码:n,i+l); scanf(%s,ai.tel); void ShowInformation(Record* a)int i;system(cls);for( i=0;iNUM_BER;i+)名 ： %sn 学 号 ： %sn 电 话 号printf(n 第 %d 个 用 户 信 息 :n 姓 码： %sn,i+1,ai.name,ai.xuehao,ai.tel); void Cls(Record* a)printf(*); system(cls);long fold(NA s) char *p;long sum=0;NA ss;strcpy(ss,s); strupr(ss);p=ss; while(*p!=0)sum+=*p+; printf(nsum=%d,sum);return sum;int Hash1(NA str)long n;int m;n=fold(str);m=n%HASHSIZE;return m;int Hash2(NA str)long n;int m;n = atoi(str);m=n%HASHSIZE;return m;Status collision(int p,int c)int i,q;i=c/2+1;while(i=0) return q;else i=c/2+1;elseq=(p-i*i)%HASHSIZE;c+;if(q=0) return q;else i=c/2+1;return UNSUCCESS;void benGetTime();void CreateHash1(HashTable* H,Record* a) int i,p=-1,c,pp;system(cls);benGetTime();for(i=0;ielempp!=NULL) pp=collision(p,c);if(ppelempp=&(ai);H-count+;printf(第%d个记录冲突次数为%d。n,i+l,c);printf (n建表完成!n此哈希表容量为%d,当前表内存储的记录个数为%d.n,HASHSIZE,H-count); benGetTime();void SearchHash1(HashTable* H,int c)int p,pp;NA str; system(cls);benGetTime();printf(n请输入要查找记录的姓名：n);scanf(%s,str);p=Hash1(str);pp=p; while(H-elempp!=NULL)&(eq(str,H-elempp-name)=-1)pp=collision(p,c);if(H-elempp!=NULL&eq(str,H-elempp-name)=1)printf (n查找成功！ n查找过程冲突次数为%宀.以下是您需要要查找的信息：nn,c);printf( 姓名 ： %sn 学 号 ： %sn 电 话 号码： %sn,H-elempp-name,H-elempp-xuehao,H-elempp-tel);else prin tf(n此人不存在，查找不成功!n);benGetTime();void benGetTime()SYSTEMTIME sys;GetLocalTime( &sys );printf(%4d/%02d/%02d%02d:%02d:%02d.%03dn,sys.wYear,sys.wMonth,sys.wDay,sys.wHour,sys.wMinute, sys.wSecond,sys.wMilliseconds);void CreateHash2(HashTable* H,Record* a) int i,p=-1,c,pp;benGetTime();for(i=0;iNUM_BER;i+)c=0;p=Hash2(ai.tel);pp=p;while(H-elempp!=NULL) pp=collision(p,c);if(ppelempp=&(ai);H-count+;printf(第%d个记录冲突次数为%d。n,i+l,c);prin tf (n建表完成!n此哈希表容量为%小，当前表内存储的记录个数为%d.n,HASHSIZE,H-coun t) benGetTime();void SearchHash2(HashTable* H,int c)NA tele;int p,pp;system(cls);benGetTime();printf(n请输入要查找记录的电话号码：n);scanf(%s,tele);p=Hash2(tele);pp=p;while(H-elempp!=NULL)&(eq(tele,H-elempp-tel)=-1)pp=collision(p,c);if(H-elempp!=NULL&eq(tele,H-elempp-tel)=1)printf (n查找成功！ n查找过程冲突次数为%宀.以下是您需要要查找的信息：nn,c);话号printf( 姓名 ： %sn 学 号 ： %sn 电码： %sn,H-elempp-name,H-elempp-xuehao,H-elempp-tel);else prin tf(n此人不存在，查找不成功!n);benGetTime();void Save()FILE *fp;if(fp=fopen(c:test.txt, w)=NULL)printf(nERROR opening customet file);fclose(fp);void main(int argc, char* argv)Record aMAXSIZE;int c,flag=1,i=0;HashTable *H;H=(HashTable*)malloc(LEN);for(i=0;iHASHSIZE;i+)H-elemi=NULL;H-size=HASHSIZE;H-count=0;while (1) int num;printf(nprintf(nprintf(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(nI .进彳丁5操作前请先输出3)printf(nII.进行6操作前请先输出4)printf(n);prin tf(请输入一个任务选项)； printf(n);scanf(%d,&num);switch(num)case 1:getin(a);break;case 2:ShowInformation(a); break;case 3:CreateHash1(H,a); break;case 4:CreateHash2(H,a); break;case 5:c=0;SearchHash1(H,c); break;case 6:c=0;SearchHash2(H,c); break;case 7:Cls(a);break;case 8:Save();break;case 9:return 0;break;default:prin tf(你输错了，请重新输入!)； printf(n);system(pause);return 0;五、测试数据及测试结果：1、主界面2、添加用户信息添加后自动跳转到主界面3、查询所有用户信息(并且自动跳转到主界面)4、以姓名为关键字建立哈希表，查找并显示给定用户名的记录查找用户名heziwen5、清屏功能使用六、课程设计总结及心得体会 ：通过这一周的课程设计，加深我对算法与数据结构这门课程所学内容的进一步的理解与 掌握；同时，通过对哈希表的设计，使得我将计算机课程所学知识与实际问题很好的相链接在一 起。在这次课程设计中，培养了我开发一个中小型程序的能力。在课程设计中，出现了蛮多错误的，最多的错误是，提示我的变量i, p等没有进行定义，但 是我看了代码确实已经有int i;等代码，然后我将int i;放到清屏函数前就解决了问题。程序最关键 的部分就是哈希表的设计，冲突解决，和关键字查找。考虑到姓名会重叠，关键字以姓名来查找 时出现的问题，所以加上了一段姓名的折叠处理。用线性探测在散列法进行解决冲突，用除留函 数法来构造哈希函数。在课程设计的过程中我遇到了许多课外的知识，这便促使我去查阅更多的课外资料来充实自 己的内容，同时学会在面对困难时药耐心的分析它细心地解决它以及通过合作更完美的深入了解 剖析它以便的到提高。细心、耐心、求知，是我这次课程设计最大的收获。