(完整版)哈希表的设计与实现毕业设计

《(完整版)哈希表的设计与实现毕业设计》由会员分享，可在线阅读，更多相关《(完整版)哈希表的设计与实现毕业设计（29页珍藏版）》请在装配图网上搜索。

1、哈希表的设计与实现摘要哈希表的设计与实现是用Visual C+ 6.0编写的能够实现数据的存储，更新与查找的程序。 它可以方便的进行基本数据信息的输入（如 : 、电话、地址等），查询（按查询. 按电话号查询），删除（运用删除），添加新的数据等。易于管理员进行管理。 本设计使用 VisualC+ 6.0 开发工具利用其提供的各种面向对象的开发工具将数据信息定义在结构体中，运用类实现了对数据不同信息的操作功能。关键字：哈希表 ; Visual C+ 6.0;地址目 录1、题目分析.2、设计思路.2.1问题描述 .2.2基本要求 .2.3数据结构 .3、设计思路 .4、测试的实验结果和测试过程. .

2、4.1详细设计 .4.2屏幕截图 .4.3问题分析： .5、课程设计体会及问题分析. .6、参考文献 .7、源程序清单 .1、题目分析在 21世纪信息时代里，各个机构企业都需要处理一些庞大的重要的数据，而这些数据既需要随时查找还需要随时纪录新的数据。这工作量无疑是巨大，如果用人力去完成，不仅效率底 ，易出错，而且其他各个方面都受到一定的限制，如时间资源等。针对这种情况，应用哈希表来规范化管理这些数据是一个既明知又科学选折。它不但能有效的准确的存储大量数据，还可以根据需要不断的更新与插入新的数据。2、设计思路2.1 问题描述实现本程序需要解决以下几个问题：（1） 如何设计一个结构体数组使该数组中

3、每个元素包含电话号码、用户名、地址。（2） 如何分别以电话号码和用户名为关键字建立哈希表。（3） 如何利用线性探测再散列法解决冲突。（4） 如何实现用哈希法查找并显示给定电话号码的记录。（5） 如何查找并显示给定用户的记录。2.2 基本要求（哈希表的设计与实现的问题）设计哈希表实现电话号码查询系统。设计程序完成以下要求： （ 1）、设每个记录有下列数据项：电话号码、用户名、地址；（ 2）、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；（ 3）、采用再哈希法解决冲突（4）、查找并显示给定电话号码的记录；（ 5）、查找并显示给定用户的记录。要完成以上要求，设计哈希表实现电话号码查询系

4、统。2.3 数据结构本设计涉及到的数据结构为：哈希表。要求输入电话号码、用户名、地址三个信息，并要求分别以电话号码和用户名为关键字进行查找，所以本问题要用到两个哈希函数，进行哈希查找。typedef structchar name20;名字char num20;电话号码char add30;地址Record;Record InfM;辅助数组Record HM; 哈希表3、设计思路主要算法的流程图如下：1、创建辅助数组流程图：2、以为关键字的哈希函数流程图：3、以为关键字创建哈希表流程图：4、以电话号码为关键字的哈希函数流程图：5、以电话号码为关键字创建哈希表流程图：6、以为关键字的哈希表按查找

5、函数流程图：7、以电话号码为关键字的哈希表按号码查找函数流程图：8、以为关键字的哈希表按插入函数流程图：9、以号码为关键字的哈希表按号码插入函数流程图：10、以为关键字的哈希表按删除函数流程图：11、主函数调用函数流程图：4、测试的实验结果和测试过程4.1 详细设计首先定义结构体类型， 在线性探测法中， 每个结构体元素对应一个数组位置，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该数组的元素它由三个域组成：name20num20address30其中 name20 和 num20 是分别为以电话号码和用户名为关键字域（key），存放关键字； address30

6、 为元素的数据域 (data) ，用来存储用户的地址信息。4.2 屏幕截图主界面如图图 11、给出一组测试数据及运行结果如下：输入数据后按散列结果如下：图 2每个元素的哈希地址正是用名字中每个字母的ASCII码值相加再对小于哈希表长的最大素数求余得到的，根据输入数据计算和书上ASCII值计算出结果相比对，数据正确，刚开始老师检查时，觉得我的程序缺少输出哈希地址的步骤，回来后我又加以改进，把哈希地址正常输出。图 3输入数据后按号码散列结果如下：每个元素的哈希地址正是用号码中每个字符的ASCII码值相加再对小于哈希表长的最大素数求余得到的，根据输入数据计算和书上ASCII值计算出结果相比对，数据正

7、确。4.3 问题分析：刚开始调试时运行删除功能时，发现删除元素后，哈希地址也在该位置而却往后移动的元素不能回到该位置，然后我又分析算法，进行改进，现在算法可以在删除元素后将哈希地址在该位置的而又移到后面的元素依次向前移动。5、课程设计体会及问题分析课程设计的过程是艰辛的 , 但是收获确实另人欣喜的 , 这次课程设计我主要是应用我们以前学习的 C语言及 C+中的知识来完成的 , 虽然这个程序功能还很不完善 , 但自己从中却学到了很多东西 . 首先，综合课程设计让我把以前学习到的知识得到巩固和进一步的提高认识，对已有知识有了更进一步的理解和认识，再次，我在课程设计中碰到了很多的问题，我通过查阅相关

8、书籍，资料，通过自己钻研，特别是得到了老师的谆谆教导，老师给予了我很大的帮助，不仅给了我思路上的开阔，还让我认识到了自己对以前所学知识的不足方面。首先 , 综合课程设计让我把以前学习的知识得到了加深与巩固 , 对自己学习的知识有了一次全面的认识 , 也给自己指明了以后复习的重点与方向 , 再次 , 在程序设计中遇到的一些问题 , 我通过查阅资料 , 请教老师与同学 , 提高了自己解决问题的能力。但由于还有很多问题无法解决，导致很多功能不能实现，未能达到预期的目的。随着社会的不断发展 , 计算机在各领域也得到广泛的应用， 同时对软件的要求也越来越高，只有不断的利用新的知识来更新程序，才能满足社会

9、的需求。但是，对于一个初学者来说， 要想编译一个完美的程序是十分困难的。本程序就有许多的不足，以及编译时出现的困难。列如：（ 1）在准备资料时，选取及设计适合的哈希函数，成首要难题，也是整个程序关键。因为在设计哈希函数时，要做到最大的减少冲突，确定在记录的储存位置和他个关键字之间建立一个取得对应关系，使没关键字和结构中的一个惟一的储存位置相对应，这是以个比较复杂的过程。（ 2）冲突是使用哈希表不可避免的问题。对不同的关键字却可能得到同一哈希地址，并且在一般情况下， 冲突只能尽可能避免而不能完全避免。因此，在建造哈希表时不仅要设定以个好的哈希函数，而且要设定一种处理冲突的方法。在泵系统的开发过程

10、中，主要采用了开放地址法中的二次探测法。通过这次课程设计 , 我发现了自身的很多不足 , 在以后的学习中 , 我会不断完善自我 . 不断进取 , 使自己在编程这方面的能力得到更进一步的提高 .6、参考文献1 谭浩强 .C 程序设计（第三版） . 北京：清华大学出版社 .20052刘斌 . 王忠 . 面向对象程序设计Visual C+.北京：清华大学出版社 .20033 严蔚敏 . 吴伟民 . 数据结构（ C语言版） . 北京：清华大学出版社 .20074 谭浩强编著 .C+程序设计 . 北京：清华大学出版社， 2004.5 美S 巴斯计算机算法：设计和分析引论 . 朱洪等译 . 上海：复旦大学

11、出版社 .1985.6 Huddard J R.Prohramming with C+(英文版，第二版 ). 北京：机械工业出版社 .2002.87 陈华生 .CV+程序设计基础 . 江苏：苏州大学出版社 .20027、源程序清单*程序源代码 *#includestdio.);printf(*哈希表*n);printf(*1.创建哈希表*n);printf(*2.按散列*n);printf(*3.按号码散列*n);printf(*0.结束程序*n);printf(*n);printf(请选择您要运行的选项按scanf(%d,&c); *读入选择 *getchar();while(c3);ret

12、urn(c);*(0-3):);返回选择 *int Create(Record HM)创建辅助数组int i;for(i=0;i30;i+)初始化哈希表strcpy(Hi.add,0);strcpy(Hi.num,0);strcpy(Hi.name,0);i=0;char sign;while(sign!=n&sign!=N)printf(请输入名字 n);scanf(%s,Infi.name);printf(请输入号码 n);scanf(%s,Infi.num);printf(请输入地址 n);scanf(%s,Infi.add);printf(ttt还需要继续输入吗 ?(YN);scanf

13、(ttt%c,&sign); *输入判断 *i+;return i;int Hash_name(char name20)以为关键字的哈希函数int i=0;int a=0;while(namei!=0)计算中每个字符的ASCII 码值相加a=a+namei;i+;a=a%29;对小于哈希表的最大素数求余，此处哈希表长为30，对 29 求余return(a);void input_name(Record InfM,int m,Record HM)以为关键字创建哈希表int j,key=0;for(j=0;jm;j+)key=Hash_name(Infj.name);计算哈希地址while(1)i

14、f(strcmp(Hkey.name,NULLKEY)=0)判断该位置是否为空，不为空就把辅助数组中的元素存到该位置strcpy(Hkey.name,Infj.name);strcpy(Hkey.num,Infj.num);strcpy(Hkey.add,Infj.add);break;elsekey+;如果为空，采用线性探测法，将元素后移int Hash_num(char num20)以为关键字的哈希函数int i=0;int b=0;while(numi!=0)计算电话号码中每个字符的ASCII 码值相加b=b+numi;i+;b=b%29;对小于哈希表的最大素数求余，此处哈希表长为30，

15、对 29 求余return(b);void input_num(Record InfM,int m,Record HM)以电话号码为关键字创建哈希表int j,key=0;for(j=0;jm;j+)key=Hash_num(Infj.num);计算哈希地址while(1)if(strcmp(Hkey.num,NULLKEY)=0)判断该位置是否为空，不为空就把辅助数组中的元素存到该位置strcpy(Hkey.name,Infj.name);strcpy(Hkey.num,Infj.num);strcpy(Hkey.add,Infj.add);break;elsekey+;如果为空，采用线性探

16、测法，将元素后移int Search_name(Record H,char name20)以为关键字的哈希表的查找函数int key=0;key=Hash_name(name);计算哈希地址while(strcmp(Hkey.name,name)!=0)如果元素不在该位置，将元素后移再判断key+;if(strcmp(Hkey.name,NULLKEY)=0)遇到空格表示该元素不存在printf(查找名字不存在 !n);return(-1);break;return(key);返回查找到的哈希地址int Search_num(Record H,char num20)以电话号码为关键字的哈希表的

17、查找函数int key=0;key=Hash_num(num);计算哈希地址while(strcmp(num,Hkey.num)!=0)如果元素不在该位置，将元素后移再判断key+;if(strcmp(Hkey.num,NULLKEY)=0)遇到空格表示该元素不存在printf(查找号码不存在 n);return(-1);break;return(key);返回查找到的哈希地址voidInsert_name(RecordHM,charname20,charnum20,charadd30) 以为关键字哈希表的插入函数int key;key=Hash_name(name);计算哈希地址while(

18、1)if(strcmp(Hkey.name,NULLKEY)=0)如果该位置为空，把元素存到该位置strcpy(Hkey.name,name);strcpy(Hkey.num,num);strcpy(Hkey.add,add);break;elsekey+;如果该位置不为空，向后移插入元素voidInsert_num(RecordHM,charname20,charnum20,charadd30) 以电话号码为关键字的哈希表插入函数int key;key=Hash_num(num);计算哈希地址while(1)if(strcmp(Hkey.num,NULLKEY)=0)如果该位置为空，把元素存

19、到该位置strcpy(Hkey.name,name);strcpy(Hkey.num,num);strcpy(Hkey.add,add);break;elsekey+;如果该位置不为空，向后移插入元素void Print_name(Record HM)以为关键字的哈希表的输出函数int i;printf(t哈希地址 t tt号码 tt地址 n);for(i=0;i30;i+)if(strcmp(Hi.name,0)!=0)printf(t%dtt%stt%stt%sn,i,Hi.name,Hi.num,Hi.add);void Print_num(Record HM)以电话号码为关键字的哈希表

20、的输出函数int i;printf(t哈希地址名tt号码 tt地址 n);for(i=0;i30;i+)if(strcmp(Hi.num,0)!=0)printf(t%dtt%stt%stt%sn,i,Hi.name,Hi.num,Hi.add);void Del_name(Record HM,char name20)名为关键字的哈希表的删除函数int key,t=0;设置 tint i,k;key=Hash_name(name);i=key;while(1)为标志位，如果该元素被删除了，把计算哈希地址t 置为1if(strcmp(Hkey.name,name)=0)如果元素存在该位置，将该位

21、置置空t=1;strcpy(Hkey.name,0);strcpy(Hkey.num,0);strcpy(Hkey.add,0);k=key;while(key30)key+;if(Hash_name(Hkey.name)=i)然后将哈希地址在该位置的存在后面的元素依次前移strcpy(Hk.name,Hkey.name);strcpy(Hk.num,Hkey.num);strcpy(Hk.add,Hkey.add);k=key;strcpy(Hkey.name,0);strcpy(Hkey.num,0);strcpy(Hkey.add,0);break;key+;如果元素不在该位置，向后移查

22、找该元素再删除if(t=0)t为 0 表示没有执行删除操作printf(名不存在 !);void Del_num(Record HM,char num20)以电话号码为关键字的哈希表的删除函数int key=0,t=0;设置 t 为标志位，如果该元素被删除了，把t 置为 1key=Hash_num(num);计算哈希地址int i,k;i=key;while(1)if(strcmp(Hkey.num,num)=0)如果元素存在该位置，将该位置置空t=1;strcpy(Hkey.name,0);strcpy(Hkey.num,0);strcpy(Hkey.add,0);k=key;while(k

23、ey30)key+;if(Hash_num(Hkey.num)=i)然后将哈希地址在该位置的存在后面的元素依次前移strcpy(Hk.name,Hkey.name);strcpy(Hk.num,Hkey.num);strcpy(Hk.add,Hkey.add);k=key;strcpy(Hkey.name,0);strcpy(Hkey.num,0);strcpy(Hkey.add,0);break;elsekey+;如果元素不在该位置，向后移查找该元素再删除if(t=0)t为 0 表示没有执行删除操作printf(该号码不存在 !n);void main()主函数char name20,num

24、20;char a020,b020,c030;char a120,b120,c120;int m,i,g;int w,k;int flag=0;while(1)switch(menu_select() )case 1:m=Create(H); 创建辅助数组break;case 2:input_name(Inf,m,H);名为关键字创建哈希表Print_name(H);while(1)flag=0;printf(n);printf(1:查找 n);printf(2:插入 n);printf(3:删除 n);printf(0:返回 n);printf(输入（ 0-3 ）:n);scanf(%d,&

25、g);switch(g)case 1:printf(n请输入要查找的名字：n);scanf(%s,name);k=Search_name(H,name);printf(printf(printf(查找该人的信息是： n);该人名是 :%sn,Hk.name);该人的电话号码是 :%sn,Hk.num);printf(该人的地址是 :%sn,Hk.add);break;case 2:printf(n请输入要插入的信息： n); printf( 插入名是 :);scanf(%s,a0);printf(插入的电话是 :);scanf(%s,b0);printf(插入的地址是 :);scanf(%s,

26、c0);Insert_name(H,a0,b0,c0);printf(插入后的结果:n);Print_name(H);break;case 3:printf(请输入要删除的名字 :n);scanf(%s,name);Del_name(H,name);printf(删除后的信息 :n);Print_name(H);break;case 0:flag=1;break;if(flag=1)break;for(i=0;i30;i+)将哈希表清空strcpy(Hi.add,0);strcpy(Hi.num,0);strcpy(Hi.name,0);break;printf(n);case 3:input

27、_num(Inf,m,H);以电话号码为关键字创建哈希表Print_num(H);while(1)flag=0;printf(n);printf(1:查找 n);printf(2:插入 n);printf(3:删除 n);printf(0:返回 );printf(输入（ 0-3 ）:n);scanf(%d,&g);switch(g)case 1:printf(请输入要查找的号码：n);scanf(%s,num);w=Search_num(H,num);printf(查找该人的信息是： n);printf(该人名是： %sn,Hw.name);printf(该人的电话号码是 :%sn,Hw.nu

28、m);printf(该人的地址是 :%sn,Hw.add);break;case 2:printf(n请输入要插入的信息：n);printf(插入名是 :);scanf(%s,a1);printf(插入的电话是 :);scanf(%s,b1);printf(插入的地址是 :);scanf(%s,c1);Insert_num(H,a1,b1,c1);printf(插入后的结果:n);Print_num(H);break;case 3:printf( 请输入要删除的号码： ); scanf(%s,num);Del_num(H,num);printf(删除后的信息： n);Print_num(H);break;case 0:flag=1;break;if(flag=1)break;for(i=0;i30;i+)将哈希表清空strcpy(Hi.add,0);strcpy(Hi.num,0);strcpy(Hi.name,0);break;case 0:printf(欢迎使用！ );exit(0);break;system(pause);