1、通过要查找的关键字用哈希函数计算出相应的地址来查找人名。通过循环语句调用数组中保存的数据来显示哈希表。三、设计1、数据结构的设计和说明(1)结构体的定义 typedef struct /记录 NA name; NA xuehao; NA tel;Record;录入信息结构体的定义,包含,学号,。typedef struct /哈希表 Record *elemHASHSIZE; /数据元素存储基址 int count; /当前数据元素个数 int size; /当前容量HashTable;哈希表元素的定义,包含数据元素存储基址、数据元素个数、当前容量。2、关键算法的设计(1)的折叠处理 long
2、 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; /折叠处理后的数,用除
3、留余数法构造哈希函数 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; else q=(p-i*i)%HASHSIZE; return UNSUCCESS;void benGetTime();void CreateHash1(HashTable* H,Record* a) /建表,以人的为关键字,建立相应的散列表 int i,p=-1,c,pp; system(cls); /若哈希地址冲突,进行冲突处理
4、 benGetTime(); for(i=0;ielempp!=NULL) pp=collision(p,c); if(ppelempp=&(ai); /求得哈希地址,将信息存入count+;第%d个记录冲突次数为%d。n,i+1,c);n建表完成!n此哈希表容量为%d,当前表存储的记录个数为%d.n,HASHSIZE,H-count);(3)查找哈希表 void SearchHash1(HashTable* H,int c) /在通讯录里查找关键字,若查找成功,显示信息int p,pp;NA str; /c用来记录冲突次数,查找成功时显示冲突次数n请输入要查找记录的: scanf(%s,st
5、r); p=Hash1(str); while(H-=NULL)&(eq(str,H-elempp-name)=-1) if(H-=NULL&eq(str,H-name)=1)n查找成功!n查找过程冲突次数为%d以下是您需要要查找的信息:nn,c);姓 名:%sn学号:%sn:%sn,H-name,H-xuehao,H-tel); else printf(n此人不存在,查找不成功!(4)显示哈希表 void ShowInformation(Record* a) /显示输入的用户信息int i; for( i=0;i+)n第%d个用户信息:n 姓 名:%sn 学号:%sn :,i+1,ai.na
6、me,ai.xuehao,ai.tel);(5)主函数的设计void main(int argc, char* argv)Record aMAXSIZE; int c,flag=1,i=0; HashTable *H; H=(HashTable*)malloc(LEN);HASHSIZE;elemi=NULL;size=HASHSIZE;count=0; while (1) int num;n n 欢迎使用同学通讯录录入查找系统 n 哈希表的设计与实现n 【1】. 添加用户信息 n 【2】. 读取所有用户信息 n 【3】. 以建立哈希表(再哈希法解决冲突) n 【4】. 以建立哈希表(再哈希法
7、解决冲突) n 【5】. 查找并显示给定用户名的记录 n 【6】. 查找并显示给定的记录 n 【7】. 清屏 n 【8】. 保存 n 【9】. 退出程序 n 温馨提示: n .进行5操作前 请先输出3 n .进行6操作前 请先输出4 请输入一个任务选项%d,&num); switch(num) case 1: getin(a); break; case 2: ShowInformation(a); case 3: CreateHash1(H,a); /* 以建立哈希表 */ case 4: CreateHash2(H,a); case 5: SearchHash1(H,c); case 6:
8、SearchHash2(H,c); case 7: Cls(a); case 8: Save(); case 9: return 0; default:你输错了,请重新输入!pause3、模块结构图及各模块的功能:四、源程序清单:#includestdlib.hstring.h#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
9、char NAMAX_SIZE;typedef struct Status eq(NA x,NA y) if(strcmp(x,y)=0) return SUCCESS; else return UNSUCCESS;Status NUM_BER;void getin(Record* a) 输入要添加的个数:NUM_BER); 请输入第%d个记录的:,ai.name);请输入%d个记录的学号:,ai.xuehao);,ai.tel);void ShowInformation(Record* a) void Cls(Record* a)*long fold(NA s) int Hash1(NA s
10、tr) int Hash2(NA str) n = atoi(str);Status collision(int p,int c) void CreateHash1(HashTable* H,Record* a) void SearchHash1(HashTable* H,int c) void benGetTime() SYSTEMTIME sys; GetLocalTime( &sys ); printf( %4d/%02d/%02d %02d:%02d:%02d.%03d n,sys.wYear,sys.wMonth,sys.wDay,sys.wHour,sys.wMinute, sys
11、.wSecond,sys.wMilliseconds);void CreateHash2(HashTable* H,Record* a) p=Hash2(ai.tel);void SearchHash2(HashTable* H,int c) NA tele;int p,pp;,tele); p=Hash2(tele);(eq(tele,H-tel)=-1)eq(tele,H-tel)=1)void Save() FILE *fp; if(fp=fopen(c:test.txt, w)=NULL)nERROR opening customet file fclose(fp);五、测试数据及测试
12、结果:1、主界面2、添加用户信息添加后自动跳转到主界面3、查询所有用户信息(并且自动跳转到主界面)4、以为关键字建立哈希表,查找并显示给定用户名的记录查找用户名heziwen5、清屏功能使用六、课程设计总结及心得体会 : 通过这一周的课程设计,加深我对算法与数据结构这门课程所学容的进一步的理解与掌握;同时,通过对哈希表的设计,使得我将计算机课程所学知识与实际问题很好的相在一起。在这次课程设计中,培养了我开发一个中小型程序的能力。 在课程设计中,出现了蛮多错误的,最多的错误是,提示我的变量i,p等没有进行定义,但是我看了代码确实已经有int i;等代码,然后我将int i;放到清屏函数前就解决了问题。程序最关键的部分就是哈希表的设计,冲突解决,和关键字查找。考虑到会重叠,关键字以来查找时出现的问题,所以加上了一段的折叠处理。用线性探测在散列法进行解决冲突,用除留函数法来构造哈希函数。 在课程设计的过程中我遇到了许多课外的知识,这便促使我去查阅更多的课外资料来充实自己的容,同时学会在面对困难时药耐心的分析它细心地解决它以及通过合作更完美的深入了解剖析它以便的到提高。细心、耐心、求知,是我这次课程设计最大的收获。