数据结构程序课程设计—散列表的设计与实现.doc

1、目 录1课程设计的目的42课程设计的要求43课程设计报告内容44课题分析 125.课题设计结果及体会146参考文献15散列表的设计与实现1.课程设计的目的掌握数据结构的基础技术，学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，应用相关知识设计设散列表实现电话号码查找系统。2.课程设计的要求1)设每个记录有下列数据项：电话号码、用户名、地址；2)从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；3)采用一定的方法解决冲突；4)查找并显示给定电话号码的记录；5)查找并显示给定用户名的记录。【进一步完成内容】1)系统功能的完善；2)设

2、计不同的散列函数，比较冲突率；3)在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。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;typed

3、ef 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

4、(输入要添加的个数：n);scanf(%d,&NUM_BER);int i; for(i=0;iNUM_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;iNUM_BER;i+) printf(n第%d个用户信息:n 姓 名

5、：%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

6、);/先将用户名进行折叠处理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

7、=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;ielempp!=NULL) pp=collision(p,c);if(ppelempp=&(ai); /求得哈希地址，将信息存入H-count+;printf(第%d个记录冲突次数为%d。n,i+1,c);/需要显示冲突次数时输出printf(n

8、建表完成!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(

9、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.w

10、Year,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;ielempp!=NULL) pp=collision(p,c);if(ppelempp=&(ai); /求得哈希地址，将信息存入H-count+;printf(第%d个记录冲突次数为%d。n,i+1,c);/

11、需要显示冲突次数时输出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

12、)=-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 cust

13、omet file);fclose(fp); int main(int argc, char* argv)int c,flag=1;HashTable *H;H=(HashTable*)malloc(LEN);for(int i=0;ielemi=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】. 读取所有用户信息 );pr

14、intf(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(请输入一个任务选项)

15、;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(

16、);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】. 以电话号码建立哈希表(再哈希法

17、解决冲突) );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(请输入一个任务选项);以上是具体整个操作过程，体现了我们整个的操作需要。从定义哈希表，再通过输入的数据处理在这过程中的冲突，达到我们的最基本的功

18、能要求，实现我们设计的目的。5设计结果(点击才会出现截图)及体会通过这次数据结构的编程题目，使我对C+语言有了更深的了解，明白了在C+中数据的流动和转移方法。从最初的不知道从何入手到最后编写程序的完成，虽然耗费了我们一定的时间跟精力，但同时我们也收获硕果累累，一方面使我对函数的运用有了更加深刻的了解，对面向对象语言更深层次的掌握和应用。在初始编程的过程中，出现了许多的错误，但通过改正，借阅书本，对程序的运行方式有了进一步体会。6参考文献严蔚敏、吴伟民编，数据结构（C语言版），清华大学出版社，2009年9月出版。严蔚敏、吴伟民、米宁编，数据结构题集（C语言版），清华大学出版社，2009年4月出版。