学士学位论文--哈希表的设计与实现.doc

哈希表的设计与实现哈希表的设计与实现摘 要哈希表的设计与实现是用Visual C+ 6.0编写的能够实现数据的存储，更新与查找的程序。它可以方便的进行基本数据信息的输入（如:姓名、电话、地址等），查询（按姓名查询.按电话号查询），删除（运用姓名删除），添加新的数据等。易于管理员进行管理。本设计使用Visual C+ 6.0开发工具利用其提供的各种面向对象的开发工具将数据信息定义在结构体中，运用类实现了对数据不同信息的操作功能。关键字：哈希表; Visual C+ 6.0; 地址1目 录1、题目分析32、设计思路32.1问题描述32.2基本要求32.3数据结构33、设计思路44、测试的实验结果和测试过程114.1详细设计114.2屏幕截图114.3问题分析：135、课程设计体会及问题分析136、参考文献147、源程序清单141、 题目分析在21世纪信息时代里，各个机构企业都需要处理一些庞大的重要的数据，而这些数据既需要随时查找还需要随时纪录新的数据。这工作量无疑是巨大，如果用人力去完成，不仅效率底，易出错，而且其他各个方面都受到一定的限制，如时间资源等。针对这种情况，应用哈希表来规范化管理这些数据是一个既明知又科学选折。它不但能有效的准确的存储大量数据，还可以根据需要不断的更新与插入新的数据。2、设计思路2.1问题描述实现本程序需要解决以下几个问题：（1） 如何设计一个结构体数组使该数组中每个元素包含电话号码、用户名、地址。（2） 如何分别以电话号码和用户名为关键字建立哈希表。（3） 如何利用线性探测再散列法解决冲突。（4） 如何实现用哈希法查找并显示给定电话号码的记录。（5） 如何查找并显示给定用户的记录。2.2基本要求（哈希表的设计与实现的问题）设计哈希表实现电话号码查询系统。设计程序完成以下要求：（1）、设每个记录有下列数据项：电话号码、用户名、地址；（2）、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；（3）、采用再哈希法解决冲突（4）、查找并显示给定电话号码的记录；（5）、查找并显示给定用户的记录。要完成以上要求，设计哈希表实现电话号码查询系统。2.3数据结构本设计涉及到的数据结构为：哈希表。要求输入电话号码、用户名、地址三个信息，并要求分别以电话号码和用户名为关键字进行查找，所以本问题要用到两个哈希函数，进行哈希查找。typedef struct char name20;/名字char num20;/电话号码char add30;/地址Record;Record InfM;/辅助数组Record HM;/哈希表3、设计思路 主要算法的流程图如下：1、创建辅助数组流程图： 开始初始化哈希表往辅助数组输入元素N结束Y结束并返回数组元素总数选择Y/N 2、以姓名为关键字的哈希函数流程图：开始取整形数据0赋给ai从0开始取numi!=0a=a+(int)(namei)a=a%29结束i+3、以姓名为关键字创建哈希表流程图：开始j从0开始elsekey+计算以姓名为关键字的哈希地址keyif(strcmp(Hkey.name,NULLKEY)=0)将辅助数组中的元素存入哈希表结束4、以电话号码为关键字的哈希函数流程图：开始取整形数据0赋给bi从0开始取numi!=0i+b=b+(int)(namei)b=b%29结束5、以电话号码为关键字创建哈希表流程图：开始j从0开始计算以电话号码为关键字的哈希地址keyif(strcmp(Hkey.num,NULLKEY)=0)将辅助数组中的元素存入哈希表elsekey+结束6、以姓名为关键字的哈希表按姓名查找函数流程图：查找名字不存在return(key);结束开始调用Hash_namewhile(strcmp(Hkey.name,name)!=0)key+if(strcmp(Hkey.name,NULLKEY)=0)7、以电话号码为关键字的哈希表按号码查找函数流程图：查找号码不存在return(key);结束开始调用Hash_numwhile(strcmp(Hkey.num,num)!=0)key+if(strcmp(Hkey.num,NULLKEY)=0)8、以姓名为关键字的哈希表按姓名插入函数流程图：开始调用Hash_nameif(strcmp(Hkey.name,NULLKEY)=0)else key+while(1)将数据以姓名为关键字插入哈希表结束 9、以号码为关键字的哈希表按号码插入函数流程图：开始调用Hash_numif(strcmp(Hkey.num,NULLKEY)=0)else key+while(1)将数据以号码为关键字插入哈希表结束10、以姓名为关键字的哈希表按姓名删除函数流程图：开始调用Hash_name,计算下标key，记录key为iif(strcmp(Hkey.name,name)=0)while(1)key+在以姓名为关键字的哈希表中删除数据，标志位赋1结束while(key30)key+将存放在后面的下标为i的元素依次向前移动 11、主函数调用函数流程图：开始选择1调用Create创建辅助数组选择2以姓名为关键字创建哈希表input_name选择3以号码为关键字创建哈希表input_num 选择0退出选择0退出选择0退出选择1查找，调用Search_name函数选择2插入，调用Insert_name函数选择3删除，调用Del_name函数选择1查找，调用Search_num函数选择2插入，调用Insert_num函数选择3删除，调用Del_num函数4、测试的实验结果和测试过程4.1详细设计 首先定义结构体类型，在线性探测法中，每个结构体元素对应一个数组位置，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该数组的元素它由三个域组成：name20num20address30其中name20和num20是分别为以电话号码和用户名为关键字域（key），存放关键字；address30为元素的数据域(data)，用来存储用户的地址信息。4.2屏幕截图主界面如图图11、给出一组测试数据及运行结果如下：输入数据后按姓名散列结果如下：图2每个元素的哈希地址正是用名字中每个字母的ASCII码值相加再对小于哈希表长的最大素数求余得到的，根据输入数据计算和书上ASCII值计算出结果相比对，数据正确，刚开始老师检查时，觉得我的程序缺少输出哈希地址的步骤，回来后我又加以改进，把哈希地址正常输出。图3输入数据后按号码散列结果如下：每个元素的哈希地址正是用号码中每个字符的ASCII码值相加再对小于哈希表长的最大素数求余得到的，根据输入数据计算和书上ASCII值计算出结果相比对，数据正确。4.3问题分析：刚开始调试时运行删除功能时，发现删除元素后，哈希地址也在该位置而却往后移动的元素不能回到该位置，然后我又分析算法，进行改进，现在算法可以在删除元素后将哈希地址在该位置的而又移到后面的元素依次向前移动。5、课程设计体会及问题分析课程设计的过程是艰辛的,但是收获确实另人欣喜的,这次课程设计我主要是应用我们以前学习的C语言及C+中的知识来完成的,虽然这个程序功能还很不完善,但自己从中却学到了很多东西.首先，综合课程设计让我把以前学习到的知识得到巩固和进一步的提高认识，对已有知识有了更进一步的理解和认识，再次，我在课程设计中碰到了很多的问题，我通过查阅相关书籍，资料，通过自己钻研，特别是得到了老师的谆谆教导，老师给予了我很大的帮助，不仅给了我思路上的开阔，还让我认识到了自己对以前所学知识的不足方面。首先,综合课程设计让我把以前学习的知识得到了加深与巩固,对自己学习的知识有了一次全面的认识,也给自己指明了以后复习的重点与方向,再次,在程序设计中遇到的一些问题,我通过查阅资料,请教老师与同学,提高了自己解决问题的能力。但由于还有很多问题无法解决，导致很多功能不能实现，未能达到预期的目的。 随着社会的不断发展,计算机在各领域也得到广泛的应用，同时对软件的要求也越来越高，只有不断的利用新的知识来更新程序，才能满足社会的需求。但是，对于一个初学者来说，要想编译一个完美的程序是十分困难的。本程序就有许多的不足，以及编译时出现的困难。列如：（1）在准备资料时，选取及设计适合的哈希函数，成首要难题，也是整个程序关键。因为在设计哈希函数时，要做到最大的减少冲突，确定在记录的储存位置和他个关键字之间建立一个取得对应关系，使没关键字和结构中的一个惟一的储存位置相对应，这是以个比较复杂的过程。（2）冲突是使用哈希表不可避免的问题。对不同的关键字却可能得到同一哈希地址，并且在一般情况下，冲突只能尽可能避免而不能完全避免。因此，在建造哈希表时不仅要设定以个好的哈希函数，而且要设定一种处理冲突的方法。在泵系统的开发过程中，主要采用了开放地址法中的二次探测法。通过这次课程设计,我发现了自身的很多不足,在以后的学习中,我会不断完善自我.不断进取,使自己在编程这方面的能力得到更进一步的提高.6、参考文献1 谭浩强.C程序设计（第三版）.北京：清华大学出版社.20052 刘斌.王忠.面向对象程序设计 Visual C+.北京：清华大学出版社.20033 严蔚敏.吴伟民.数据结构（C语言版）.北京：清华大学出版社.20074 谭浩强编著.C+程序设计.北京：清华大学出版社，2004.5 美S巴斯计算机算法：设计和分析引论.朱洪等译.上海：复旦大学出版社.1985.6 Huddard J R.Prohramming with C+(英文版，第二版).北京：机械工业出版社.2002.87 陈华生.CV+程序设计基础.江苏：苏州大学出版社.20027、源程序清单*程序源代码*#include#include#include#define M 30#define NULLKEY 0typedef struct char name20;char num20;char add30;Record;Record InfM;/定义辅助数组为全局变量Record HM;/定义哈希表为全局变量int menu_select() /*菜单函数*/ int c; do system(cls); /*运行前清屏*/printf( *n); printf( * 哈希表 *n); printf( * 1. 创建哈希表 *n); printf( * 2. 按姓名散列 *n); printf( * 3. 按号码散列 *n); printf( * 0. 结束程序 *n); printf( *n); printf(请选择您要运行的选项按(0-3):); scanf(%d,&c); /*读入选择*/getchar(); while(c3); return(c); /*返回选择*/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还需要继续输入吗?(Y/N); scanf(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) if(strcmp(Hkey.name,NULLKEY)=0)/判断该位置是否为空，不为空就把辅助数组中的元素存到该位置 strcpy(Hkey.name,Infj.name); strcpy(Hkey.num,Infj.num); strcpy(Hkey.add,Infj.add); break; else key+;/如果为空，采用线性探测法，将元素后移 int Hash_num(char num20)/以姓名为关键字的哈希函数int i=0;int b=0;while(numi!=0)/计算电话号码中每个字符的ASCII码值相加b=b+numi;i+;b=b%29;/对小于哈希表的最大素数求余，此处哈希表长为30，对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; else key+;/如果为空，采用线性探测法，将元素后移 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)/以电话号码为关键字的哈希表的查找函数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);/返回查找到的哈希地址void Insert_name(Record HM,char name20,char num20,char add30)/以姓名为关键字哈希表的插入函数int key;key=Hash_name(name);/计算哈希地址while(1) if(strcmp(Hkey.name,NULLKEY)=0)/如果该位置为空，把元素存到该位置 strcpy(Hkey.name,name); strcpy(Hkey.num,num); strcpy(Hkey.add,add); break; else key+;/如果该位置不为空，向后移插入元素 void Insert_num(Record HM,char name20,char num20,char add30)/以电话号码为关键字的哈希表插入函数int key;key=Hash_num(num);/计算哈希地址while(1) if(strcmp(Hkey.num,NULLKEY)=0)/如果该位置为空，把元素存到该位置 strcpy(Hkey.name,name); strcpy(Hkey.num,num); strcpy(Hkey.add,add); break; else key+;/如果该位置不为空，向后移插入元素 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)/以电话号码为关键字的哈希表的输出函数int i;printf(t哈希地址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;/设置t为标志位，如果该元素被删除了，把t置为1int i,k; key=Hash_name(name);/计算哈希地址 i=key;while(1) if(strcmp(Hkey.name,name)=0)/如果元素存在该位置，将该位置置空 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+; /如果元素不在该位置，向后移查找该元素再删除 if(t=0)/t为0表示没有执行删除操作 printf(该姓名不存在!); void Del_num(Record HM,char num20)/以电话号码为关键字的哈希表的删除函数int key=0,t=0;/设置t为标志位，如果该元素被删除了，把t置为1 key=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(key30) 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; else key+; /如果元素不在该位置，向后移查找该元素再删除 if(t=0)/t为0表示没有执行删除操作 printf(该号码不存在!n); void main()/主函数char name20,num20;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,&g); switch(g) case 1: printf(n请输入要查找的名字：n); scanf(%s,name); k=Search_name(H,name); printf(查找该人的信息是：n); printf(该人的姓名是:%sn,Hk.name); printf(该人的电话号码是:%sn,Hk.num); printf(该人的地址是:%sn,Hk.add); break; case 2: printf(n请输入要插入的信息：n); printf(插入的姓名是:); scanf(%s,a0); printf(插入的电话是:); 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; 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_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.num); 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_