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

1、精选优质文档-倾情为你奉上福 建 工 程 学 院课 程 设 计课程： 算法与数据结构 题目： 哈希表 专业： 网络工程 班级： xxxxxx班 座号： xxxxxxxxxxxx 姓名： xxxxxxx 2011年 12 月 31 日实验题目：哈希表一、 要解决的问题 针对同班同学信息设计一个通讯录，学生信息有姓名，学号，电话号码等。以学生姓名为关键字设计哈希表，并完成相应的建表和查表程序。 基本要求：姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。完成按姓名查询的操作。 运行的环境：Microsoft Vis

2、ual C+ 6.0二、算法基本思想描述 设计一个哈希表（哈希表内的元素为自定义的结构体）用来存放待填入的30个人名，人名为中国姓名的汉语拼音形式，用除留余数法构造哈希函数，用线性探查法解决哈希冲突。建立哈希表并且将其显示出来。通过要查找的关键字用哈希函数计算出相应的地址来查找人名。通过循环语句调用数组中保存的数据来显示哈希表。三、设计1、数据结构的设计和说明（1）结构体的定义 typedef struct /记录 NA name; NA xuehao; NA tel;Record;录入信息结构体的定义，包含姓名，学号，电话号码。typedef struct /哈希表 Record *elem

3、HASHSIZE; /数据元素存储基址 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",su

4、m); 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<HASHSIZE) if(c%2=0) c+; q=(p+i*i)%HASHSIZE; if

5、(q>=0) return q; else i=c/2+1; else q=(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;i<NUM_BER;i+) c=0;

6、p=Hash1(); pp=p; while(H->elempp!=NULL) pp=collision(p,c); if(pp<0) printf("第%d记录无法解决冲突",i+1); /需要显示冲突次数时输出 continue; /无法解决冲突，跳入下一循环 H->elempp=&(ai); /求得哈希地址，将信息存入 H->count+; printf("第%d个记录冲突次数为%d。n",i+1,c); /需要显示冲突次数时输出 printf("n建表完成!n此哈希表容量为%d,当前表内存储

7、的记录个数为%d.n",HASHSIZE,H->count); benGetTime();（3）查找哈希表 void SearchHash1(HashTable* H,int c) /在通讯录里查找姓名关键字，若查找成功，显示信息int p,pp;NA str; system("cls"); /c用来记录冲突次数,查找成功时显示冲突次数 benGetTime(); printf("n请输入要查找记录的姓名：n"); scanf("%s",str); p=Hash1(str); pp=p; while(H->ele

8、mpp!=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->t

9、el); else printf("n此人不存在，查找不成功!n"); benGetTime();（4）显示哈希表 void ShowInformation(Record* a) /显示输入的用户信息int i; system("cls"); for( i=0;i<NUM_BER;i+) printf("n第%d个用户信息:n 姓 名：%sn 学号：%sn 电话号码：%sn",i+1,,ai.xuehao,ai.tel);（5）主函数的设计void main(int argc, char* argv)Record

10、aMAXSIZE; int c,flag=1,i=0; HashTable *H; H=(HashTable*)malloc(LEN); for(i=0;i<HASHSIZE;i+) H->elemi=NULL; H->size=HASHSIZE; H->count=0; while (1) int num; printf("n "); printf("n 欢迎使用同学通讯录录入查找系统 "); printf("n 哈希表的设计与实现"); printf("n 【1】. 添加用户信息 ");

11、 printf("n 【2】. 读取所有用户信息 "); printf("n 【3】. 以姓名建立哈希表(再哈希法解决冲突) "); printf("n 【4】. 以电话号码建立哈希表(再哈希法解决冲突) "); printf("n 【5】. 查找并显示给定用户名的记录 "); printf("n 【6】. 查找并显示给定电话号码的记录 "); printf("n 【7】. 清屏 "); printf("n 【8】. 保存 "); printf("

12、;n 【9】. 退出程序 "); printf("n 温馨提示： "); printf("n .进行5操作前 请先输出3 "); printf("n .进行6操作前 请先输出4 "); printf("n"); printf("请输入一个任务选项>>>"); printf("n"); scanf("%d",&num); switch(num) case 1: getin(a); break; case 2: ShowIn

13、formation(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: printf("你输错了，请重新输入!&

14、quot;); printf("n"); system("pause"); return 0;3、模块结构图及各模块的功能： 四、源程序清单： #include<stdio.h>#include<stdlib.h>#include<string.h>#include <windows.h>#define MAXSIZE 20 #define MAX_SIZE 20 #define HASHSIZE 53 #define SUCCESS 1#define UNSUCCESS -1#define LEN siz

15、eof(HashTable)typedef int Status;typedef char NAMAX_SIZE;typedef struct NA 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; syst

16、em("cls"); printf("输入要添加的个数：n"); scanf("%d",&NUM_BER); for(i=0;i<NUM_BER;i+) printf("请输入第%d个记录的姓名:n",i+1); scanf("%s",); printf("请输入%d个记录的学号:n",i+1); scanf("%s",ai.xuehao); printf("请输入第%d个记录的电话号码:n",i+1); s

17、canf("%s",ai.tel); void ShowInformation(Record* a) int i; system("cls"); for( i=0;i<NUM_BER;i+) printf("n第%d个用户信息:n 姓 名：%sn 学号：%sn 电话号码：%sn",i+1,,ai.xuehao,ai.tel);void Cls(Record* a) printf("*"); system("cls");long fold(NA s) char *p; long

18、 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

19、i,q; i=c/2+1; while(i<HASHSIZE) if(c%2=0) c+; q=(p+i*i)%HASHSIZE; if(q>=0) return q; else i=c/2+1; else q=(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()

20、; for(i=0;i<NUM_BER;i+) c=0; p=Hash1(); pp=p; while(H->elempp!=NULL) pp=collision(p,c); if(pp<0) printf("第%d记录无法解决冲突",i+1); continue; H->elempp=&(ai); H->count+; printf("第%d个记录冲突次数为%d。n",i+1,c); printf("n建表完成!n此哈希表容量为%d,当前表内存储的记录个数为%d.n",HASHSI

21、ZE,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-

22、>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();void benGetTime() SY

23、STEMTIME sys; 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);void CreateHash2(HashTable* H,Record* a) int i,p=-1,c,pp; benGetTime(); for(i=0;i<NUM_BER;i+) c=0; p=Hash2(ai.tel); p

24、p=p; while(H->elempp!=NULL) pp=collision(p,c); if(pp<0) printf("第%d记录无法解决冲突",i+1); continue; H->elempp=&(ai); H->count+; printf("第%d个记录冲突次数为%d。n",i+1,c); printf("n建表完成!n此哈希表容量为%d,当前表内存储的记录个数为%d.n",HASHSIZE,H->count); benGetTime();void SearchHash2(Hash

25、Table* 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

26、->tel)=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();void Save() FILE *fp; if(fp=fopen("c:test.txt", "w&

27、quot;)=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;i<HASHSIZE;i+) H->elemi=NULL; H->size=HASHSIZE; H->count=0; while (1) int num; printf("n "

28、;); printf("n 欢迎使用同学通讯录录入查找系统 "); printf("n 哈希表的设计与实现"); printf("n 【1】. 添加用户信息 "); printf("n 【2】. 读取所有用户信息 "); printf("n 【3】. 以姓名建立哈希表(再哈希法解决冲突) "); printf("n 【4】. 以电话号码建立哈希表(再哈希法解决冲突) "); printf("n 【5】. 查找并显示给定用户名的记录 "); printf(&

29、quot;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