数据结构课程设计报告模板(参考).docx

攀枝花学院数据结构课程设计（论文）题 目：散列表的设计与实现学生姓名： 刘攀 学 号：201510803044所在院（系）：数学与计算机学院专业：网络工程班级：m指导教师： 蒋斌职称：副教授2017年6月28日攀枝花学院教务处制3整体设计(方案设计)3.1系统功能设计定义电话本记录数量(MAXSTZE)、表长(HASHSIZE)、姓名长度(MAX.STZE) 以及结构体typedef struct的内容，构造两个哈希函数hashl和hash2。功能示意图：3.2处理功能设计增加系统功能如下：添加用户信息；读取所有用户信息；以姓名建立哈希表; 以电话号码建立哈希表；查找并显示给定用户名的记录；查找并显示给定电话号 码的记录；清屏以及保存功能；处理流程示意图：图3. 2处理流程图3.3主要模块键盘输入各人的信息:vcid getinO ；显示输入的用户信息:void ShowInformationO ；除留余数法构造哈希函数:int HashlO；构造把字符串转换成整型数哈希函数:int Hash20 ；冲突处理函数:Status collisionO;以姓名为关键字建表:void CreateHashlO;以姓名为关键字查表:void SearchHashlO;以电活号码为关键字建表:void CrcatcHash2 ；以电话号码为关键字查表:vcid SearchHash2();输出菜单函数:intmain()o3.4算法模块设计哈希算法输入待查找的值即key,即可查找到其对应的值即可。 int Hash 1 (NA str)long n;int m;n 二 fbld(str);m=n%HASHSIZE;return m;int Hash2(NA str)long n;int m;n 二 atoi(str);.m=n%HASHSIZE;return m;3.5二次探测再散列冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。 沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址(即 该地址单元为空)为止(若要插入，在探查到开放的地址，则可将待插入的新结 点存人该地址单元)。查找时探查到开放的地址则表明表中无待查的关键字，即 查找失败。int i,q；i=c/2+l;vhilc(i=0) return q;else i=c/2+l;elseq=(p-i*i)%HASHSIZE;c+;if(q=0) return q;else i=c/2+1;4程序结构及源代码说明4.1程序结构说明哈希函数将用户名折叠处理，折叠处理后的数，用除留余数法构造哈希函数。建立，代码如下：int Hashl(NAstr)int m;n=fold (str);m=n%HASHSIZE;return m;int Hash2(NA str)int m;n = atoi(str);.m=n%HASHSIZE;return m;冲突处理函数建立冲突处理函数，采用二次探测再散列法解决冲突，代码如下:tatus collision(int p,int &c)int i,q；i=c/2+l；while(i=0) return q;else i=c/2+1;elseq=(p-i*i)%HASHSIZE;c+;if(q=0) return q;else i=c/2+l;return UNSUCCESS;4.2程序源码及说明#include#includc#include#includc#include #define MAXSIZE 20 电话薄记录数量#define MAX.SIZE 20人名的最大长度#define HASHSIZE 53定义表长#define SUCCESS 1#define UNSUCCESS -1#define LEN sizeof(HashTable)typcdcf int Status;typedefchar NAMAX_SIZE;typedef struct /i 己录NA name;NA tel;NA add; Record;typedef struct/哈希表Record *clcmHASHSIZE;数据元素存储基址int count;当前数据元素个数int size;当前容量HashTable;Status eq(NAx,NAy)关键字比较，相等返回SUCCESS;否则返回UNSUCCESSif(strcmp (x,y)二二 0)return SUCCESS;Status NUM_BER;记录的个数void gctin(Rccord* a)键盘输入各人的信息cout输入要添加的个数：n”；cinNUM_BER;int i;for(i=0;iai.name;cout”请输入第“vvi+lvv”个记录的电话号码:n”；cinai.tcl;coutvv”请输入第“vvi+lvv”个记录的地址:n”；cinai.add;/gets(str2);?)void Showl n formation (Record* a)显示输入的用户信息int i;for( i 二();ivNUM_BER;i+)coutHn 第Hi+1H个用户信息n 姓 名：”ai.namevv”n 电话号码：”vvai.tclvv”n 联系地址：”vvai.addvv“n”；void Cis (Record* a)coutvv*”；system(clsn);)long fold(N/ s)人名的折叠处理char *p;long sum=();NA ss;strcpy(ss,s);复制字符串，不改变原字符串的大小写 strupr(ss);将字符串ss转换为大写形式 p=ss;while(*p!二0)sum+=*p+;cout,nsum=,sum;return sum;)int Hashl(NA str)哈希函数long n;int m;n=fold(str);/先将用户名进行折叠处理m二n%HASHSIZE;折登处理后的数，用除留余数法构造哈希函数return m; 并返回模值int Hash2(NA str) 哈希函数long n;int m;n = atoi(str);/把字符串转换成整型数m二n%H ASHSIZE;用除留余数法构造哈希函数return m; 并返回模值Status collision(int p,int&c)冲突处理函数，采用二次探测再散列法解决冲突 int i,q;i 二 c/2+1;while(i=()return q;else i=c/2+l;else(q=(p-i*i)%H ASHSIZE;c+;if(q=0) return q;else i=c/2+l;return UNSUCCESS;void benGetTimeO；void CreateHashl(HashTable* H,Record* a)/建表,以人的姓名为关键字,建立相 应的散列表benGetTimeO；int i,p=-l,c,pp;for(i 二()；ivNUM_BHR；i+)c=0;p=Hashl (a i.name);PP 二 P；while(H-elempp!=NULL) pp=collision(p,c);if(pp0)coutv”第”vi+lclcmpp二&(疝);求得哈希地址，将信息存入H-count+;COUtVV”第”VVi+1VV”个记录冲突次数为”VVcVV”.n“；需要显示冲突次数时输 出coutHn建表完成!n此哈希表容量为” vvHASHSIZEvv”,当前表内存储的记录 个数为” vvH-countvv”.n”；benGetTimeO；void SearchHashl(HashTable* H,int &c) 在通讯录里查找姓名关键字，若查找成 功，显示信息 benGetTimeO；NA str;coutstr;int p,pp;p=Hash 1 (str);PP=P；vhilc(H-clcmpp!二 NULL)&(cq(str,H-clcmpp-namc)二二-1)pp 二 collision(p,c);if(H- elem pp !=NULL&eq(str,H-elem pp -name)=1) cout-n查找成功！ n查找过程冲突次数为“vvcvv”.以下是您需要要查找 的信息：nn”；cout姓 名：Mclcmpp-namcn 电话号码： nelempp-telclempp-addvvn”;else coutnn此人不存在，查找不成功!n”；benGetTimeO；void benGetTimeO SYSTEMTIME sys;GetLocalTime( &sys);coutsys.wYearsys.vMonthsys.wDaysys.wHoursys.wMinutesys.wSec ondelempp!=NULL) pp 二 collision(p,c);if(ppvO)8出“第”勺+1”记录无法解决冲突”;需要显示冲突次数时输出continue;无法解决冲突，跳入下一循环附件2:攀枝花学院本科学生课程设计任务书题目散列表的设计与实现1、课程设计的目的1）使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存 储结构和操作实现算法，以及它们在程序中的使用方法。2）使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设 计的能力。3）使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的 基本能力。H-clcmpp=&(ai); 求得哈希地址，将信息存入H-count+;coutvv”第“vvi+lvv”个记录冲突次数为,c,o n”;需要显示冲突次数时 输出coutHn建表完成!n此哈希表容量为” vvHASHSIZEvv”,当前表内存储的记录 个数为” vvH-countvv”.n”；bcnGctTimcO；void SearchHash2(HashTable* H,int &c)在通讯录里查找电话号码关键字，若查 找成功，显示信息benGetTimeO；NA tele;couttele;int p,pp;p=Hash2(tele);PP=P；while(H-elem pp!=NU LL)& (eq(tele,H- elem pp - tel)二二-1)pp=collision(p,c);if(H-clempp!=NULL&cq(tcle,H-cIempp-teI)=l)cout,n查找成功！ n查找过程冲突次数为,c-.以下是您需要要查找 的信息：nnn;cout姓 名：elem pp-namen 电话 号码： nelempp-telelempp-addvvn;)else coutclcm 国二 NULL;H-sizc 二 HASHSIZE;H-count=0;Record aMAXSIZE;while (1)coutncout n p突）I H；coutn1欢迎使用电话号码查找系统 coutMn| | ”； 哈希表的设计与实现* coutvv”n1添加用户信息1coutMn2 读取所有用户信息|，coutn|1；coutn|3 以姓名建立哈希表（再哈希法解决冲突）4 以电话号码建立哈希表（再哈希法解决冲coutn（51 .查找并显示给定用户名的记录1”； coutn1；coutn6.查找并显示给定电话号码的记录71 清屏|coutn |温馨提示:coutn coutn【8】.保存|9.退出程序|coutnI .进行5操作前请先输出3I ， coutnI .进行6操作前请先输出4coutMn 匚= = = = = = : = = =J ”；cout”；coutnum;switch(num)(case 1:getin(a);break;case 2:Showlnfbrmation(a); break;case 3:CreateHashl (H,a); break;/*以姓名建立哈希表*/case 4:CreateHash2(H,a); break;case 5:/*以电话号码建立哈希表*/c=0;Search H ash 1 (H,c);break; case 6- cnpSearch Hash2(=c)；break; case 7:Qs(ak break case 8 savAJ break ease 9- return 0;break;defaun ssaass.sn 鸯莺cou-AA-，n-w sysrcm(-pausc-_)J fum 0;5程序测试及运行结果说明由需求分析可知，散列表的设计与实现主要电话号码查找功能，本程序已调 试成功并实现了其功能，其运行结果如下：5.1主菜单运行界面主菜单运行界面如图5.1所示：欢迎使用电话号码查找系统k 123456789 : 嶷k 123456789 : 嶷k 123456789 : 嶷的息户哈建给给 .i 码示示号显显话葬 ,； -加取姓电存出 一添读财以查杳Is隽哈普信希立定定3 4 出出 1 先先 请请请输入一个任务选项图5.1主菜单运行界面5.2各项功能测试用户信息录入用户信息录入如图5.2:kc . MSDoe tDt.CloOutcXle.C.omo请撤入彳、任另迭项输入55部加的个葬攵，嘉输入隼1个ie求的用户名=清缗入笄乳个记隶的电馆号码x151123*15678沽辎入隼盆个、己隶的:也址.斋林入隼a个记录的用户名=摘第5八年2个3己至的电、苦号码1 3H WHi声偷入隼*仆记次的，也址=oo le图5.2川户信息录入冲突解决冲突解决界面如图5.3:-|g|x|T:vtsual ciMSDev985yPro)ectsDECDebugKC.exe-sum290第2个记录冲芙次数为艮建表完成？此语希表容量为53,当前表内存储的记录个数为2.欢迎使用电话号码查找系统冲 突决QK( i录 法 合 123456789;凌繇请输入一个任务选项图5.3冲突解决用户查找用户查找界面如图5.4:3 T:visual c*MSDev98MyProjectsDECDebugDEC.exe以姓务:zhao电话号码:盛累ecit欢迎使用电话号码查找系统 1.【2】.【3】.【4】.5.【6】.71 .【8】.【9】. 温馨提示：I .进:II .进d *录 尊源 现 码 实 时奎号 计息表哈霍 设信希立定定 的息户哈建给给 春用立码示溟 404号显显 哈话葺 ： 加舞曲存出 添铁队以查查虞退3 4 出出 先先请输入一个任务选项录记冲 夹决 *图5.4用户查找总结数据结构的课程设计是大学时期第二个专业课的课程设计而数据结构这门 课也是本学期的一门专业课经过一个学期对数据结构的学习应该说对这门课 只有初步的认识掌握的并不是那么牢固。不过学期末的课程设计又教会了我该如 何简单的去运用数据结构去解决问题。数据结构的算法和之前学习的C语言有着一些的区别在设计中不能一味的 去用原来的C语言去实现算法和函数。设计时可以为程序定义全局变量也可以 为程序定义局部变量全局变量可以让程序看起来比较简洁局部变量虽说比较繁 琐但是易懂且避免了一些不必要的错误发生。在本次课程设计中分别用到了指 针和引用两种不同的方式来设计程序两者各有利弊但最终选择指针作为最后版 本所用到的。这一次我选择的课程设计题目是散列表的设计和查找可以说经过一个多星 期设计不管是通过自己的努力、查资料还是询问别人该如何做都是让我更加熟 悉这一模块的内容掌握了哈希表其中的一些用法比如说折叠法除留余数法解决 冲突的线性探测再散列和二次探测再散列等一些实用的方法。当然这一部分不是只有这么一些内容还包括了其他的建立哈希表以及解决 冲突的方法虽然教材中介绍的比较简单但依然包含了更多的知识就像整个数据 结构一样一 本教材是不可能把所有的知识点都讲到只是给我们介绍了一些基础 知识一些可能用到相对来说比较简单的方法来解决遇到的问题这些方法知识对 于我们现在处的一个阶段就已经很实用不能因为掌握了这一模块或者是这一本 书就认为掌握了数据结构的全部。在课程设计中我很清楚的认识到了自己的不足而自己最大的不足就是少练 对一些算法掌握不熟练构造函数时不知该如何使它来符合要求遇到了一些困难 的困扰在查阅资料之后才能略微明白这些错误究竟是什么在自己实践操作下也 是彻底明白了函数所要求的以及指针运用的错误。还有一点不足就是基础知识 掌握的不牢固此次课程设计又把哈希表部分内容反反复复的看尤其是哈希表的 算法将此部分一点一点弄明白才开始动手设计程序。而在不断地学习和设计中自己也对数据结构产生了浓厚的兴趣了解了它的 实用性和可操作性使得程序设计起来不再是那么复杂和繁琐易懂也是它的一个 有点。数据结构的课程设计的结束也是代表了这个学期的数据结构的结束当然数 据结构这门学问依然充满了吸引力让我们去探索这是一个结束同样也是一个开 始掌握好了基础才能更进一步学习和研究。这一次的课程数据也是给了我一个教训一定要把基础掌握住才能练习才能 做设计。数据结构的学习给我其他科目的学习提供了一定帮助杜绝眼高手低边学边 练为我接下来儿个学期对其他专业课的学习提供了宝贵的经验。这一次两个星期 的课程设计给了我足够的时间来让我掌握该部分的知识并且了解到数据结构奥 妙所在给了我以后努力学习数据结构的动力程序的成功设计也给了我一定的自 信不再害怕自己设计程序时遇到错误而要勇于面对它程序中的错误是一定会被 一些简单实用的方法给解决掉。程序设计完成并且运行无误自己也是对自己感到满意对自己以后学习其他 计算机语言也是打下了自信的基础并有了这一次的经历和所获得的经验也是对 以后的学习提供了保障。参考文献LU数据结构（C语言版），严蔚敏，清华大学出版社，2003.2 数据结构题集，严蔚敏，清华大学出版社，2005.3 数据结构（C语言版），刘大有，高等教育出版社，2004.4JData Structure with C+, William Ford. William Topp,清华大学出版社, 2003.如有侵权请联系告知删除，感谢你们的配合！2、课程设计的内容和要求（包括原始数据、技术要求、工作要求等）【问题描述】设计散列表实现电话号码查找系统。【基本要求】1）设每个记录有下列数据项：电话号码、用户名、地址；2）从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；3）采用一定的方法解决冲突；4）查找并显示给定电话号码的记录；5）查找并显示给定用户名的记录。【进一步完成内容】1）系统功能的完善；2）设计不同的散列函数，比较冲突率；3）在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查 找长度的变化。3、主要参考文献1 刘大有等，数据结构（C语言版），高等教育出版社2 严蔚敏等，数据结构（C语言版），清华大学出版社3 William Ford, William Topp,Data Structure with C+清华大学出版社4 苏仕华等，数据结构课程设计，机械工业出版社4、课程设计工作进度计划1）分析题目，查阅相关资料：1天;2）算法设计、数据结构设计：1天3）编写代码并调试：1天4）完成课程设计报告：2天指导教师（签字）指导教师（签字）日期年 月 日教研室意见:教研室意见:学生（签字）:接受任务时间：年 月 日注：任务书由指导教师填写。附件3：课程设计（论文）指导教师成绩评定表题目名称评分项目分值得 分评价内涵工作表 现 20%01学习态度6遵守各项纪律，工作刻苫努力，具有良好的科学 工作态度。02科学实践、调研7通过实验、试验、查阅文献、深入生产实践等渠 道获取与课程设计有关的材料。03课题工作量7按期圆满完成规定的任务，工作量饱满。能 力 水 平 35%04综合运用知识的能力10能运用所学知识和技能去发现与解决实际问题， 能正确处理实验数据，能对课题进行理论分析， 得出有价值的结论。05应用文献的能力5能独立查阅相关文献和从事其他调研；能提出并 较好地论述课题的实施方案；有收集、加工各种 信息及获取新知识的能力。06设计（实验）能力，方案 的设计能力5能正确设计实验方案，独立进行装置安装、调试、 操作等实验工作，数据正确、可靠；研究思路清 晰、完整。07计算及计算机应用能力5具有较强的数据运算与处理能力；能运用计算机 进行资料搜集、加工、处理和辅助设计等。08对计算或实验结果的分析 能力（综合分析能力、技 术经济分析能力）10具有较强的数据收集、分析、处理、综合的能力。成 果 质 量 45%09插图（或图纸）质量、篇 幅、设计（论文）规范化 程度5符合本专业相关规范或规定要求；规范化符合本 文件第五条要求。10设计说明书（论文）质量：30综述简练完整，有见解；立论正确，论述充分， 结论严谨合理；实验正确，分析处理科学。11创新10对前人工作有改进或突破，或有独特见解。成绩指 导 教 师 评 语指导教师签名：年 月曰摘要信息社会的高科技，商品经济化的高效益，使计算机的应用已普及到经济和社 会生活的各个领域。计算机虽然与人类的关系愈来愈密切，还有人由于计算机操 作不方便继续用手工劳动。散列表的设计与实现所涉及到的操作算法都是以链表 或顺序表的基本运算作为基础的，此程序通过通讯录实现，包括建立通讯录，添 加记录，查询记录，删除记录，显示记录，修改记录。通过顺序表存储结构实现 数据的输入，实现各子程序过程的演示，对异常输入信息报错。关键字：新建通讯录，散列表，散列函数，处理冲突摘要V1课程设计的目的和意义12需求分析22.1需求概述22.2需求环境22.3功能描述23整体设计（方案设计）33.1系统功能设计33.2处理功能设计33.3主要模块53.4算法模块设计5哈希算法53.5二次探测再散列54程序结构及源代码说明64.1程序结构说明6哈希函数6冲突处理函数64.2程序源码及说明75程序测试及运行结果说明145.1主菜单运行界面145.2各项功能测试14用户信息录入14冲突解决15用户查找15总结16参考文献181课程设计的目的和意义数据结构主要介绍一些最常用的数据结构，阐明各种数据结构内在的 逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算 法，并对算法的效率进行简单的分析和讨论。数据结构是介于数学、计算机软件 和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、 操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程 等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对 它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能 力和专业素质的提高。通过此次课程设计主要达到以下目的：了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能 力；(2) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方 法和技能；(3) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；(4) 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所 应具备的科学的工作方法和作风。(5) 锻炼动手操作能力，培养我们的创新思维能力。从编写代码，到调试程序, 再到运行程序，这是设计的最重要环节，它需要我们用逻辑思维将我们所学知识 和实际相结合，并在对方案的分析过程中能够有所创新，从而使运行方案更严谨 更简洁。培养好良好的思维，便要将这种思维赋予实践，即动手操作能力。目前, 市场上关于计算机运用、计算机软件和电子类相关专业的人才辈出，但毕业生在 走进企业公司政府机构或研究单位之后，感觉到缺乏实际开发设计项R的经验， 所以我们在课程设计中能够多训练，提高我们将知识融会贯通的能力(6) 培养我们严谨治学的态度，以及认清自己学知识、运用知识的能力。不管是编写代码，调试代码，还是运行代码，需要我们严谨的思维和态度去 对待，这样才能真正起到此设计的作用。我们也能够在设计中认识到自己对数据 结构这门课程学习的欠缺，对以后我们的学习有着很大的指导和帮助。学习课 程设计，编写程序，将数据结构和算法相结合，了解到数据结构、算法和程序之 间的关系，更学习到数据结构和算法的最佳定位2需求分析2.1需求概述在各个领域，不同的通讯录其功能都是为用户储存信息，查找信息提供方便的 有效工具。一个内容全面、功能先进的通讯录对每个用户来说是一个理想的助手。 现在，我们通过对散列表和基本操作的学习和理解，以及在掌握线性表等基本运 算的基础上，实现对线性表操作。这里我们所做的通讯录则是在数据结构学习之 后，利用计算机C程序语言编写的，可以实现数据的新建通讯录，添加记录，查 询记录，修改记录，删除记录，显示记录功能的可执行程序。通过它可以进行对 联系对象的姓名、地址、电话号码等的记录与查找。当然，该程序设计也有不足 之处，我们一定会不断地努力去更正完善。很多涉及通讯录的操作的算法都是以顺序表操作为基础，通过顺序表的建立， 初始化，结点添加、查询与删除的演示，方便在学习中更好的理解顺序表结点的 添加、查询、删除的过程2.2需求环境本课程设计需要的设备为硬件要求和软件配置要求具体要求如下： 硬件要求：一台计算机。 软件配置：WINDOWS、C/VC+6.0。2.3功能描述本次课题是的散列表设计与实现。主要是通过C+语言和数据结构算法实现, 主要有以下功能：1. 每个记录需要有存储的数据：姓名、电话、地址；2. 从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；3. 采用一定的方法解决冲突；4. 查找并显示给定电话号码的记录；5. 查找并显示给定用户名的记录。