哈希表的设计与实现

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

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

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

4、涉及到的数据结构为：哈希表。要求输入电话号码、用户名、地址三个信息，并要求分别以电话号码和用户名为关键字进行查找，所以本问题要用到两个哈希函数，进行哈希查找。typedefstructcharname20;/名字charnum20;/电话号码charadd30;/地址Record;RecordInfM;/辅助数组RecordHM;/哈希表3、设计思路主要算法的流程图如下:1、创建辅助数组流程图:N结束4、以电话号码为关键字的哈希函数流程图:3、5、7、以姓名为关键字的哈希表按姓名查找函数流程图:7、以电话号码为关键字的哈希表按号码查找函数流程图:9、以姓名为关键字的哈希表按姓名插入函数流程图:

5、9、以号码为关键字的哈希表按号码插入函数流程图:10、以姓名为关键字的哈希表按姓名删除函数流程图:key+11、主函数调用函数流程图:4、测试的实验结果和测试过程4.1 详细设计首先定义结构体类型，在线性探测法中，每个结构体元素对应一个数组位置，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该数组的元素它由三个域组成：name20num20address30其中name20和num20是分别为以电话号码和用户名为关键字域（key）,存放关键字；address30为元素的数据域（data）,用来存储用户的地址信4.2 屏幕截图主界面如图图11、给出一组测试数据及运

6、行结果如下:输入数据后按姓名散列结果如下：图2每个元素的哈希地址正是用名字中每个字母的ASCII码值相加再对小于哈希表长的最大素数求余得到的，根据输入数据计算和书上ASCII值计算出结果相比对，数据正确，刚开始老师检查时，觉得我的程序缺少输出哈希地址的步骤，回来后我又加以改进，把哈希地址正常输出。1"OWC+6,0COMMONMSDEV98BINDebvg3.eKF"I口I'入 玲硼找人除叫输入数据后按号码散列结果如下：每个元素的哈希地址正是用号码中每个字符的ASCII码值相加再对小于哈希表长的最大素数求余得到的，根据输入数据计算和书上ASCII值计算出结果相比对，

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

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

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

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

11、V+S序设计基础.江苏：苏州大学出版社.20027、源程序清单*程序源代码*#include<stdio.h>#include<string.h>#include<stdlib.h>#defineM30#defineNULLKEY"0"typedefstructcharname20;charnum20;charadd30;Record;RecordInfM;/定义辅助数组为全局变量RecordHM;/定义哈希表为全局变量intmenu_select()/*菜单函数*/intc;dosystem("cls");/*运行前

12、清屏*/printf("*哈希表printf("*创建哈希表按姓名散列按号码散列0. 结 束 程 序printf("*1.*n");printf("*2.*n");printf("*3.*n");printf("*n");printf("*n");printf("请选择您要运行的选项按(0-3):");scanf("%d",&c);/*读入选择*/getchar();while(c<0|c>3);return(c);

13、/*返回选择*/intCreate(RecordHM)/创建辅助数组inti;for(i=0;i<30;i+)/初始化哈希表strcpy(Hi.add,"0");strcpy(Hi.num,"0");strcpy(H,"0");i=0;charsign;while(sign!='n'&&sign!='N')printf("请输入名字n");scanf("%s",I);printf("请输入号码n"

14、;);scanf("%s",Infi.num);printf("请输入地址n");scanf("%s",Infi.add);printf("ttt还需要继续输入吗?(Y/N)");scanf("ttt%c",&sign);/*输入判断*/i+;returni;intHash_name(charname20)/以姓名为关键字的哈希函数inti=0;inta=0;while(namei!='0')/计算姓名中每个字符的ASCII码值相加a=a+namei;i+;a=a%29;

15、对小于哈希表的最大素数求余，此处哈希表长为30,对29求余return(a);voidinput_name(RecordInfM,intm,RecordHM)/以姓名为关键字创建哈希表intj,key=0;for(j=0;j<m;j+)key=Hash_name(I);/计算哈希地址while(1)if(strcmp(H,NULLKEY)=0)/判断该位置是否为空，不为空就把辅助数组中的元素存到该位置strcpy(H,I);strcpy(Hkey.num,Infj.num);strcpy(Hkey.add,Infj.add)

16、;break;elsekey+;/如果为空，采用线性探测法，将元素后移intHash_num(charnum20)/以姓名为关键字的哈希函数inti=0;intb=0;while(numi!='0')/计算电话号码中每个字符的ASCII码值相加b=b+numi;i+;b=b%29;对小于哈希表的最大素数求余，此处哈希表长为30,对29求余return(b);voidinput_num(RecordInfM,intm,RecordHM)/以电话号码为关键字创建哈希表intj,key=0;for(j=0;j<m;j+)key=Hash_num(Infj.num);/计算哈希地

17、址while(1)if(strcmp(Hkey.num,NULLKEY)=0)/判断该位置是否为空，不为空就把辅助数组中的元素存到该位置strcpy(H,I);strcpy(Hkey.num,Infj.num);strcpy(Hkey.add,Infj.add);break;elsekey+;/如果为空，采用线性探测法，将元素后移intSearch_name(RecordH,charname20)/以姓名为关键字的哈希表的查找函数intkey=0;key=Hash_name(name);/计算哈希地址while(strcmp(H,name)!=0

18、)/如果元素不在该位置，将元素后移再判断key+;if(strcmp(H,NULLKEY)=0)/遇到空格表示该元素不存在printf("查找名字不存在!n");return(-1);break;return(key);/返回查找到的哈希地址intSearch_num(RecordH,charnum20)/以电话号码为关键字的哈希表的查找函数intkey=0;key=Hash_num(num);/计算哈希地址while(strcmp(num,Hkey.num)!=0)/如果元素不在该位置，将元素后移再判断key+;if(strcmp(Hkey.num,NUL

19、LKEY)=0)/遇到空格表示该元素不存在printf("查找号码不存在n");return(-1);break;return(key);/返回查找到的哈希地址voidInsert_name(RecordHM,charname20,charnum20,charadd30)/以姓名为关键字哈希表的插入函数intkey;key=Hash_name(name);/计算哈希地址while(1)if(strcmp(H,NULLKEY)=0)/如果该位置为空，把元素存到该位置strcpy(H,name);strcpy(Hkey.num,num);strc

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

21、后移插入元素voidPrint_name(RecordHM)/以姓名为关键字的哈希表的输出函数inti;printf("t哈希地址t姓名tt号码tt地址n");for(i=0;i<30;i+)if(strcmp(H,"0")!=0)printf("t%dtt%stt%stt%sn",i,H,Hi.num,Hi.add);voidPrint_num(RecordHM)/以电话号码为关键字的哈希表的输出函数inti;printf("t哈希地址t姓名tt号码tt地址n");for(i=0;i

22、<30;i+)if(strcmp(Hi.num,"0")!=0)printf("t%dtt%stt%stt%sn",i,H,Hi.num,Hi.add);voidDel_name(RecordHM,charname20)/以姓名为关键字的哈希表的删除函数int key,t=0;/设置t为标志位，如果该元素被删除了，把t置为1inti,k;key=Hash_name(name);/计算哈希地址i=key;while(1)if(strcmp(H,name)=0)/如果元素存在该位置，将该位置置空t=1;strcpy(Hkey

23、.name,"0");strcpy(Hkey.num,"0");strcpy(Hkey.add,"0");k=key;while(key<30)key+;if(Hash_name(H)=i)/然后将哈希地址在该位置的存在后面的元素依次前移strcpy(H,H);strcpy(Hk.num,Hkey.num);strcpy(Hk.add,Hkey.add);k=key;strcpy(H,"0");strcpy(Hkey.num,"0"

24、;);strcpy(Hkey.add,"0");break;key+;/如果元素不在该位置，向后移查找该元素再删除if(t=0)/t为0表示没有执行删除操作printf("该姓名不存在!");voidDel_num(RecordHM,charnum20)/以电话号码为关键字的哈希表的删除函数intkey=0,t=0;/设置t为标志位，如果该元素被删除了，把t置为1key=Hash_num(num);/计算哈希地址inti,k;i=key;while(1)if(strcmp(Hkey.num,num)=0)/如果元素存在该位置，将该位置置空t=1;strc

25、py(H,"0");strcpy(Hkey.num,"0");strcpy(Hkey.add,"0");k=key;while(key<30)key+;if(Hash_num(Hkey.num)=i)/然后将哈希地址在该位置的存在后面的元素依次前移strcpy(H,H);strcpy(Hk.num,Hkey.num);strcpy(Hk.add,Hkey.add);k=key;strcpy(H,"0");strcpy(Hkey.num,"0

26、");strcpy(Hkey.add,"0");break;elsekey+;/如果元素不在该位置，向后移查找该元素再删除if(t=0)/t为0表示没有执行删除操作printf("该号码不存在!n");voidmain()/主函数charname20,num20;chara020,b020,c030;chara120,b120,c120;intm,i,g;intw,k;intflag=0;while(1)switch(menu_select()case 1:m=Create(H);/创建辅助数组break;case 2:input_name(I

27、nf,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",&g);switch(g)case 1:printf("n请输入要查找的名字：n");scanf("%s&q

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

29、");scanf("%s",b0);printf("插入的地址是:");scanf("%s",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;case0:flag=1;break;if(flag=1)break;将哈希表清空Hi.add,"0");Hi.num,"0");H,"0");for(i=0;i<30;i+)/strcpy(strcpy(strcpy(break;printf("n");case3:input_num(Inf,m,H);/以电话号码为关键字创建哈希表Print_num(H);while(1)flag=0;printf("n");printf("1:查找n");printf(&q