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

课程设计任务书2010 2010 学年第 1 学期学生姓名： 吴浪 专业班级： 09网络工程 指导教师 刘志远 工作部门： 计算机学院 一、课程设计题目 哈希表及其应用二、课程设计内容建立一个小型信息管理系统（可以是图书、人事、学生、物资、商品等任何信息管理系统）。要求：1.使用哈希查找表存储信息；2.实现查找、插入、删除、统计、输出等功能；三、进度安排1初步完成总体设计，搭好框架；2完成最低要求：尝试使用多种哈希函数和冲突解决方法，并通过实际运行测试给出自己的评价四、基本要求1界面友好，函数功能要划分好2程序要加必要的注释3要提供程序测试方案 教研室主任签名： 年 月 日目 录1 概述42 设计目的43 设计功能说明44 详细设计说明55 流程图56 程序代码67 程序运行结果158 总结19参考文献 19成绩评定表 201 概述数据结构是一门理论性强、思维抽象、难度较大的课程，是基础课和专业课之间的桥梁，只有进行实际操作，将理论应用于实际中，才能确实掌握书中的知识点。通过课程设计，不仅可以加深学生对数据结构基本概念的了解，巩固学习成果，还能够提高实际动手能力。为学生后继课程的学习打下良好的基础。2 设计目的数据结构课程设计是在教学实践基础上进行的一次大型实验，也是对该课程所学理论知识的深化和提高。因此，要求学生能综合应用所学知识，设计与制造出具有较复杂功能的应用系统，并且在实验的基本技能方面上进行一次全面的训练。通过程序的编译掌握对程序的调试方法及思想，并且让学生学会使用一些编程技巧。促使学生养成良好的编程习惯。1.使学生能够较全面地巩固和应用课堂中所学的的基本理论和程序设计方法，能够较熟练地完成程序的设计和调试。 2.培养学生综合运用所学知识独立完成程序课题的能力。3.培养学生勇于探索、严谨推理、实事求是、有错必改，用实践来检验理论，全方位考虑问题等科学技术人员应具有的素质。4提高学生对工作认真负责、一丝不苟，对同学团结友爱，协作攻关的基本素质。5.培养学生从资料文献、科学实验中获得知识的能力，提高学生从别人经验中找到解决问题的新途径的悟性，初步培养工程意识和创新能力。6.对学生掌握知识的深度、运用理论去处理问题的能力、实验能力、课程设计能力、书面及口头表达能力进行考核。3 设计功能分析本设计的功能如下：1、利用哈希函数来实现一个小型信息管理系统，其中信息包含用户名，地址，电话等。2、能添加用户信息，并能保存该信息。3、查询管理系统中的信息：可通过姓名查找，也可通过电话查找等两种方式。4、能散列管理系统中的信息,保存信息等功能。4 详细设计说明哈希表是一种重要的存储方式，也是一种常见的检索方法。其基本思想是将关系码的值作为自变量，通过一定的函数关系计算出对应的函数值，把这个数值解释为结点的存储地址，将结点存入计算得到存储地址所对应的存储单元。检索时采用检索关键码的方法。(1) 假定每个记录有下列数据项：用户名、电话号码、地址。(2) 初始记录为空，通过不断添加记录，并保存到数据文件telphone.txt 中。 (3) 分别采用线性和平方探测解决冲突。(4) 查找并显示给定电话号码的记录；查找并显示给定用户名的记录。开始5 流程图建立哈希表退出显示输出结果删除添加记录号码姓名平方线性查找选择操作 6 程序代码#include #include #include #include using namespace std;#define Maxsize 57 struct recordchar name20;char tel20;char add20;typedef record *precord;struct HashTable int elemMaxsize; /存放数组a的下标int count;typedef HashTable * pHashTable;int Number; /统计当前数组a中的记录总数void Getdata(precord a) /从文件telphone.txt中读取数据存放到数组a Number=0;ifstream infile(telphone.txt,ios:in|ios:binary);if(!infile) cout文件打开失败!n; exit(1);while(!infile.eof() & infile.get()!=EOF) /文件不为空并且文件指针没有指到结束符infile.seekg(Number*sizeof(aNumber),ios:beg); /定位文件指针infile.read(char *)&aNumber,sizeof(aNumber);Number+;infile.close();void Add(precord a) /添加记录 int i,num;cout当前文件内已有Number条记录n;coutnum;ofstream ofile(telphone.txt,ios:app);if(!ofile) cout文件打开失败!; exit(1); for(i=0;inum;i+)cout请输入第Number+1个人的姓名aNumber.name; cout请输入第Number+1个人的电话aNumber.tel; cout请输入第Number+1个人的地址aNumber.add; ofile.seekp(ios:end);ofile.write(char *)&aNumber,sizeof(aNumber);Number+;ofile.close();void Print(precord a) /显示所有记录 int i;for(i=0;iNumber;i+)cout 姓名:ai.name;cout 电话:ai.tel;cout 地址:ai.addendl;int Hash(char str) /除留取余 long val=0;char p20,*p1;strcpy(p,str);p1=p;while(*p1!=0)val=val+*p1+; /将字符串中的所有字符对应的ASCII值相加return(val%Maxsize);int derter; /线性增量int Line_Sollution(int address) /采用线性探测解决冲突 derter+;if(derter=Maxsize) return(-1);else return(address+derter)%Maxsize);int n;int Square_Sollution(int address) /采用平方探测法解决冲突 int j;derter+;if(derter=Maxsize) return -1;n=n*(-1);j=(int(pow(float)derter,2)*n+address)%Maxsize;return(j);void Init_Hash(pHashTable h) /初始化哈希表 int i;for(i=0;ielemi=-1;int menu;void Creathash_Name(pHashTable h,precord a)/以员工姓名为关键字创建哈希表cout -n;cout 1-以线性探测建表n;cout 2-以平方探测建表n;cout -n;int i,address;coutmenu;Init_Hash(h);for(i=0;ielemaddress!=-1)if(menu=1) address=Line_Sollution(address);else address=Square_Sollution(address);if(address=-1) break;if(address!=-1) h-elemaddress=i; h-count+;cout姓名哈希表已成功建立!n;void Search_Name(pHashTable h,precord a) /查找并显示指定姓名的记录 coutnam;address=Hash(nam);derter=0;n=-1;while(h-elemaddress!=-1 & strcmp(nam,ah-elemaddress.name)!=0) if(menu=1) address=Line_Sollution(address);else address=Square_Sollution(address);i+;if(address=-1) break;if(h-elemaddress!=-1 & strcmp(nam,ah-elemaddress.name)=0) cout你要查找的信息为:n;cout 姓名:elemaddress.nameendl;cout 电话:elemaddress.telendl;cout 地址:elemaddress.addendl;cout比较次数为iendl;else cout无此姓名,查找失败!;void Creathash_tel(pHashTable h,precord a) /以电话号为关键字创建哈希表cout -n;cout 1-以线性探测建表n;cout 2-以平方探测建表n;cout -n;int i,address;coutmenu;Init_Hash(h);for(i=0;ielemaddress!=-1)if(menu=1) address=Line_Sollution(address);else address=Square_Sollution(address);if(address=-1) break;if(address!=-1) h-elemaddress=i; h-count+;cout电话号码哈希表已成功建立!n;void Search_tel(pHashTable h,precord a)/查找并显示指定电话号的记录 couttelphone;address=Hash(telphone);derter=0; n=-1; /初始化线性增量while(h-elemaddress!=-1& strcmp(telphone,ah-elemaddress.tel)!=0) if(menu=1) address=Line_Sollution(address);else address=Square_Sollution(address);i+;if(address=-1) break;if(h-elemaddress!=-1 & strcmp(telphone,ah-elemaddress.tel)=0) cout你要查找的信息为:n;cout 姓名:elemaddress.nameendl;cout 电话:elemaddress.telendl;cout 地址:elemaddress.addendl;cout比较次数为iendl;else cout无此电话,查找失败!;void Delet(pHashTable h,precord a)cout -n;cout 1-按电话号码删除n;cout 2-按姓名删除n;cout -n;int m;coutm;if(m=1)couttelphone;address=Hash(telphone);derter=0; n=-1; /初始化线性增量while(h-elemaddress!=-1 & strcmp(telphone,ah-elemaddress.tel)!=0) if(menu=1) address=Line_Sollution(address);else address=Square_Sollution(address);if(address=-1) break;if(h-elemaddress!=-1& strcmp(telphone,ah-elemaddress.tel)=0)j=h-elemaddress;h-elemaddress=-1;for (i=j;iNumber-1;i+)strcpy(ai.name,ai+1.name);strcpy(ai.tel,ai+1.tel);strcpy(ai.add,ai+1.add);Number=Number-1;if(m=2)coutnam;address=Hash(nam);derter=0;n=-1;while(h-elemaddress!=-1 & strcmp(nam,ah-elemaddress.name)!=0) if(menu=1) address=Line_Sollution(address);else address=Square_Sollution(address);i+;if(address=-1) break;if(h-elemaddress!=-1 & strcmp(nam,ah-elemaddress.name)=0) j=h-elemaddress;h-elemaddress=-1;for (i=j;iNumber-1;i+)strcpy(ai.name,ai+1.name);strcpy(ai.tel,ai+1.tel);strcpy(ai.add,ai+1.add);Number=Number-1;void Menu() /功能菜单函数coutendl;cout 员工管理查询系统n;coutn;cout n;cout 1-添加 n; cout 2-显示所有 n; cout 3-以姓名建立哈希表 n; cout 4-以电话号码建立哈希表 n; cout 5-按员工姓名查找 n; cout 6-按电话号码查找 n; cout 7-删除员工信息 n;cout 0-退出 n; cout n;cout 使用说明:n;cout 1.添加新纪录后,如要进行查找请先进行3或4操作n;cout 2.按员工姓名查找之前,请先进行3操作建立用户名哈希表n;cout 3.按电话号码查找之前,请先进行4操作建立电话号码哈希表n;void exit() int i;for(i=1;i=4;i+)coutendl;cout n;cout n;cout 员 工 管 理 查 询 系 统 n;cout n;cout 谢 谢 您 的 使 用 ! n;cout n;cout n;system(pause);int main() record aMaxsize;pHashTable H=new HashTable;Getdata(a); /将文件中的数据读入到数组a中system(color BD);start:Menu();coutmenu1;switch(menu1) case 0:system(cls);exit();break;case 1:Add(a);system(pause);system(cls);goto start;break;case 2:Print(a);system(pause);system(cls);goto start;break;case3:Creathash_Name(H,a);system(pause);system(cls);goto start;break;case4:Creathash_tel(H,a);system(pause);system(cls);goto start;break;case5:Search_Name(H,a);system(pause);system(cls);goto start;break;case 6:Search_tel(H,a);system(pause);system(cls);goto start;break;case 7:Delet(H,a);system(pause);system(cls);goto start;break;default:cout请输入正确的操作选项!n;system(cls);goto start;break;return 0;7 程序运行结果主界面 添加记录显示所有 建立哈希表查找删除退出8 总结 数据结构是计算机学科非常重要的一门必修课程，它与计算机其他课程都有密切联系，具有独特的承上启下的重要位置。同时数据结构还是一门实践性极强的理论技术基础课。这次数据结构课程设计为我们提供了与众不同的学习方法和学习机会，让我们从被动授学转变为主动求学，从死记硬背的模式中脱离出来，转变为在实践中学习。 在实际的上机操作过程中，不仅是让我们了解数据结构的理论知识，更重要的是培养解决实际问题的能力，所以相信通过此次实习可以提高我们分析设计能力和编程能力，为后续课程的学习及实践打下良好的基础。参考文献1 苏仕民.数据结构课程设计 北京：机械工业出版社.20052 C+面向对象程序设计教程/陈维兴，林小茶编著 北京：清华大学出版社，2009.63 C语言版/严蔚敏，吴伟民 北京:清华大学出版社，20074 徐孝凯.数据结构实用教程（C/C+描述）M. (第一版)北京:清华大学出版社.19995 陈慧南.数据结构（使用C+语言描述）M. (第一版)南京:东南大学出版社.20016 殷人昆,陶永雷,谢若阳等.数据结构（用面向对象方法与C+描述）M. (第一版)北京:清华大学出版社.1999数据结构 课程设计成绩评定表姓 名吴浪性 别男专业班级网络工程课程设计题目：哈希表及其应用课程设计答辩或质疑记录：1、请简单概括一下你对哈希查找的理解 哈希查找就是在记录的存储位置和他的关键字之间建立一个确定的对应关系f，使每个关键字和结构中的一个唯一的存储位置相对应，在查找是只要根据这个对应关系f找到对应的像f(K)即可。2、程序解决哈希冲突的方法 考虑到算法的时间复杂度，减小查找次数，程序采用了两种解决哈希冲突的方法，线性探测和平方探测，可任选其一。成绩评定依据：最终评定成绩（以优、良、中、及格、不及格评定） 指导教师签字： 年 月 日