数据结构课程设计-哈希表及其应用

1/20学号：200940420108课程设计题目哈希表及其应用教学院计算机学院专业09网络工程班级09网络工程（1）班姓名吴浪指导教师刘志远年月日2/20课程设计任务书2010～2010学年第1学期学生姓名：吴浪专业班级：09网络工程指导教师刘志远工作部门：计算机学院一、课程设计题目哈希表及其应用二、课程设计内容建立一个小型信息管理系统（可以是图书、人事、学生、物资、商品等任何信息管理系统）。要求：1.使用哈希查找表存储信息；2.实现查找、插入、删除、统计、输出等功能；三、进度安排1．初步完成总体设计，搭好框架；2．完成最低要求：尝试使用多种哈希函数和冲突解决方法，并通过实际运行测试给出自己的评价四、基本要求1．界面友好，函数功能要划分好2．程序要加必要的注释3．要提供程序测试方案教研室主任签名：年月日3/20目录1概述………………………………………………………………………42设计目的…………………………………………………………………43设计功能说明……………………………………………………………44详细设计说明……………………………………………………………55流程图……………………………………………………………………56程序代码…………………………………………………………………67程序运行结果……………………………………………………………158总结………………………………………………………………………19参考文献……………………………………………………………………19成绩评定表…………………………………………………………………204/201概述数据结构是一门理论性强、思维抽象、难度较大的课程，是基础课和专业课之间的桥梁，只有进行实际操作，将理论应用于实际中，才能确实掌握书中的知识点。通过课程设计，不仅可以加深学生对数据结构基本概念的了解，巩固学习成果，还能够提高实际动手能力。为学生后继课程的学习打下良好的基础。2设计目的《数据结构》课程设计是在教学实践基础上进行的一次大型实验，也是对该课程所学理论知识的深化和提高。因此，要求学生能综合应用所学知识，设计与制造出具有较复杂功能的应用系统，并且在实验的基本技能方面上进行一次全面的训练。通过程序的编译掌握对程序的调试方法及思想，并且让学生学会使用一些编程技巧。促使学生养成良好的编程习惯。1.使学生能够较全面地巩固和应用课堂中所学的的基本理论和程序设计方法，能够较熟练地完成程序的设计和调试。2.培养学生综合运用所学知识独立完成程序课题的能力。3.培养学生勇于探索、严谨推理、实事求是、有错必改，用实践来检验理论，全方位考虑问题等科学技术人员应具有的素质。4．提高学生对工作认真负责、一丝不苟，对同学团结友爱，协作攻关的基本素质。5.培养学生从资料文献、科学实验中获得知识的能力，提高学生从别人经验中找到解决问题的新途径的悟性，初步培养工程意识和创新能力。6.对学生掌握知识的深度、运用理论去处理问题的能力、实验能力、课程设计能力、书面及口头表达能力进行考核。3设计功能分析本设计的功能如下：1、利用哈希函数来实现一个小型信息管理系统，其中信息包含用户名，地址，电话等。2、能添加用户信息，并能保存该信息。3、查询管理系统中的信息：可通过姓名查找，也可通过电话查找等两种方式。5/204、能散列管理系统中的信息,保存信息等功能。4详细设计说明哈希表是一种重要的存储方式，也是一种常见的检索方法。其基本思想是将关系码的值作为自变量，通过一定的函数关系计算出对应的函数值，把这个数值解释为结点的存储地址，将结点存入计算得到存储地址所对应的存储单元。检索时采用检索关键码的方法。(1)假定每个记录有下列数据项：用户名、电话号码、地址。(2)初始记录为空，通过不断添加记录，并保存到数据文件telphone.txt中。(3)分别采用线性和平方探测解决冲突。(4)查找并显示给定电话号码的记录；查找并显示给定用户名的记录。5流程图选择操作添加记录建立哈希表查找线性号码姓名平方显示输出结果删除退出开始6/206程序代码#includestdlib.h#includefstream#includeiostream#includecmathusingnamespacestd;#defineMaxsize57structrecord{charname[20];chartel[20];charadd[20];};typedefrecord*precord;structHashTable{intelem[Maxsize];//存放数组a[]的下标intcount;};typedefHashTable*pHashTable;intNumber;//统计当前数组a[]中的记录总数voidGetdata(precorda)//从文件telphone.txt中读取数据存放到数组a[]{Number=0;ifstreaminfile(telphone.txt,ios::in|ios::binary);if(!infile){cout文件打开失败!\n;exit(1);}while(!infile.eof()&&infile.get()!=EOF)//文件不为空并且文件指针没有指到结束符{infile.seekg(Number*sizeof(a[Number]),ios::beg);//定位文件指针infile.read((char*)&a[Number],sizeof(a[Number]));Number++;}infile.close();}voidAdd(precorda)//添加记录{inti,num;cout当前文件内已有Number条记录\n;cout请输入添加的个数:;7/20cinnum;ofstreamofile(telphone.txt,ios::app);if(!ofile){cout文件打开失败!;exit(1);}for(i=0;inum;i++){cout请输入第Number+1个人的姓名endl;cina[Number].name;cout请输入第Number+1个人的电话endl;cina[Number].tel;cout请输入第Number+1个人的地址endl;cina[Number].add;ofile.seekp(ios::end);ofile.write((char*)&a[Number],sizeof(a[Number]));Number++;}ofile.close();}voidPrint(precorda)//显示所有记录{inti;for(i=0;iNumber;i++){cout姓名:a[i].name;cout电话:a[i].tel;cout地址:a[i].addendl;}}intHash(charstr[])//除留取余{longval=0;charp[20],*p1;strcpy(p,str);p1=p;while(*p1!='\0')val=val+*p1++;//将字符串中的所有字符对应的ASCII值相加return(val%Maxsize);}intderter;//线性增量intLine_Sollution(intaddress)//采用线性探测解决冲突8/20{derter++;if(derter==Maxsize)return(-1);elsereturn((address+derter)%Maxsize);}intn;intSquare_Sollution(intaddress)//采用平方探测法解决冲突{intj;derter++;if(derter==Maxsize)return-1;n=n*(-1);j=(int(pow((float)derter,2))*n+address)%Maxsize;return(j);}voidInit_Hash(pHashTableh)//初始化哈希表{inti;for(i=0;iMaxsize;i++)h-elem[i]=-1;}intmenu;voidCreathash_Name(pHashTableh,precorda)//以员工姓名为关键字创建哈希表{cout------------------------------------------------------------------------\n;cout1----以线性探测建表\n;cout2----以平方探测建表\n;cout------------------------------------------------------------------------\n;inti,address;cout请选择:;cinmenu;9/20Init_Hash(h);for(i=0;iNumber;i++){derter=0;n=-1;address=Hash(a[i].name);while(h-elem[address]!=-1){if(menu==1)address=Line_Sollution(address);elseaddress=Square_Sollution(address);if(address==-1)break;}if(address!=-1){h-elem[address]=i;h-count++;}}cout姓名哈希表已成功建立!\n;}voidSearch_Name(pHashTableh,precorda)//查找并显示指定姓名的记录{cout请输入要查找的姓名:;charnam[20];intaddress,i=1;cinnam;address=Hash(nam);derter=0;n=-1;while(h-elem[address]!=-1&&strcmp(nam,a[h-elem[address]].name)!=0){if(menu==1)address=Line_Sollution(address);elseaddress=Square_Sollution(address);i++;if(address==-1)break;}if(h-elem[address]!=-1&&strcmp(nam,a[h-elem[address]].name)==0){cout你要查找的信息为:\n;cout姓名:a[h-elem[address]].nameendl;cout电话:a[h-elem[address]].telendl;cout地址:a[h-elem[address]].addendl;cout比较次数为iendl;}elsecout无此姓名,查找失败!;}10/20voidCreathash_tel(pHashTableh,precorda)//以电话号为关键字创建哈希表{cout---------------------------------------------------------\n;cout1----以线性探测建表\n;cout2----以平方探测建表\n;cout---------------------------------------------------------\n;inti,address;cout请选择:;cinmenu;Init_Hash(h);for(i=0;iNumber;i++){derter=0;n=-1;address=Hash(a[i].tel);while(h-elem[address]!=-1){if(menu==1)address=Line_Sollution(address);elseaddress=Square_Sollution(address);if(addres