数据结构程序课程设计—散列表的设计与实现.doc
XXXXXX学院计算机类课程设计报告课程名称：数据结构程序设计课程设计题目： 散列表的设计与实现姓 名：系：计算机系专 业：计算机科学与技术年 级：08级学 号：指导教师：职 称：2010年 6 月26日XXXXXXXXXXX计算机类课程设计结果评定序号评 定 项 目分值得分1选题合理、目的明确102设计方案正确，具有可行性、创新性203程序运行结果正确204态度认真、学习刻苦、遵守纪律155设计报告的规范化、参考文献充分（不少于5篇）106答辩：思路清晰，语言表达准确，概念清楚、正确25最后得分指导老师（签名）日期年 月 日目 录1课程设计的目的42课程设计的要求43课程设计报告内容44课题分析 ·····················································125.课题设计结果及体会···············································146参考文献15散列表的设计与实现1.课程设计的目的掌握数据结构的基础技术，学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，应用相关知识设计设散列表实现电话号码查找系统。2.课程设计的要求1)设每个记录有下列数据项：电话号码、用户名、地址；2)从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；3)采用一定的方法解决冲突；4)查找并显示给定电话号码的记录；5)查找并显示给定用户名的记录。【进一步完成内容】1)系统功能的完善；2)设计不同的散列函数，比较冲突率；3)在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。3.课程设计报告内容程序代码#include<stdio.h>#include<stdlib.h>#include<string>#include <windows.h>#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 struct/记录NA name;NA tel;NA add;Record;typedef struct/哈希表Record *elemHASHSIZE; /数据元素存储基址int count; /当前数据元素个数int size; /当前容量HashTable;Status eq(NA x,NA y)/关键字比较，相等返回SUCCESS；否则返回UNSUCCESSif(strcmp(x,y)=0) return SUCCESS;else return UNSUCCESS;Status NUM_BER; /记录的个数void getin(Record* a)/键盘输入各人的信息printf("输入要添加的个数：n");scanf("%d",&NUM_BER);int i; for(i=0;i<NUM_BER;i+) printf("请输入第%d个记录的用户名:n",i+1); scanf("%s",ai.name); printf("请输入%d个记录的电话号码:n",i+1); scanf("%s",ai.tel); printf("请输入第%d个记录的地址:n",i+1); scanf("%s",ai.add); /gets(str2);?void ShowInformation(Record* a)/显示输入的用户信息 int i;for( i=0;i<NUM_BER;i+) printf("n第%d个用户信息:n 姓 名：%sn 电话号码：%sn 联系地址：%sn",i+1,ai.name,ai.tel,ai.add); void Cls(Record* a)printf("*"); system("cls");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;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<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)/建表，以人的姓名为关键字，建立相应的散列表 /若哈希地址冲突，进行冲突处理benGetTime();int i,p=-1,c,pp; for(i=0;i<NUM_BER;i+) c=0; p=Hash1(ai.name); 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",HASHSIZE,H->count);benGetTime();void SearchHash1(HashTable* H,int &c)/在通讯录里查找姓名关键字，若查找成功，显示信息 /c用来记录冲突次数,查找成功时显示冲突次数benGetTime();NA str;printf("n请输入要查找记录的姓名：n");scanf("%s",str);int p,pp;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->tel,H->elempp->add);else printf("n此人不存在，查找不成功!n");benGetTime();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.wSecond,sys.wMilliseconds); void CreateHash2(HashTable* H,Record* a)/建表，以电话号码为关键字，建立相应的散列表 /若哈希地址冲突，进行冲突处理benGetTime();int i,p=-1,c,pp; for(i=0;i<NUM_BER;i+) c=0; p=Hash2(ai.tel); 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",HASHSIZE,H->count);benGetTime();void SearchHash2(HashTable* H,int &c)/在通讯录里查找电话号码关键字，若查找成功，显示信息 /c用来记录冲突次数,查找成功时显示冲突次数benGetTime();NA tele;printf("n请输入要查找记录的电话号码：n");scanf("%s",tele);int p,pp;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查找过程冲突次数为%d以下是您需要要查找的信息：nn",c); printf("姓 名：%sn电话号码：%sn联系地址：%sn",H->elempp->name,H->elempp->tel,H->elempp->add);else printf("n此人不存在，查找不成功!n");benGetTime();void Save()FILE *fp;if(fp=fopen("c:test.txt", "w")=NULL) printf("nERROR opening customet file");fclose(fp); int main(int argc, char* argv)int c,flag=1;HashTable *H;H=(HashTable*)malloc(LEN);for(int i=0;i<HASHSIZE;i+) H->elemi=NULL; H->size=HASHSIZE; H->count=0;Record aMAXSIZE;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"); int num; 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: printf("你输错了，请重新输入!"); printf("n"); system("pause");return 0;4.课题分析：（具体通过截图表现） 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("请输入一个任务选项>>>");以上是具体整个操作过程，体现了我们整个的操作需要。从定义哈希表，再通过输入的数据处理在这过程中的冲突，达到我们的最基本的功能要求，实现我们设计的目的。5设计结果(点击才会出现截图)及体会通过这次数据结构的编程题目，使我对C+语言有了更深的了解，明白了在C+中数据的流动和转移方法。从最初的不知道从何入手到最后编写程序的完成，虽然耗费了我们一定的时间跟精力，但同时我们也收获硕果累累，一方面使我对函数的运用有了更加深刻的了解，对面向对象语言更深层次的掌握和应用。在初始编程的过程中，出现了许多的错误，但通过改正，借阅书本，对程序的运行方式有了进一步体会。6参考文献严蔚敏、吴伟民编，数据结构（C语言版），清华大学出版社，2009年9月出版。严蔚敏、吴伟民、米宁编，数据结构题集（C语言版），清华大学出版社，2009年4月出版。
