数据结构课程设计报告模板参考分析研究

攀枝花学院数据结构课程设计（论文）题 目：散列表的设计与实现 学生姓名： 刘攀 学 号： 201510803044 所在院(系)： 数学与计算机学院 专 业： 网络工程 班 级： 二班 指 导 教 师： 蒋斌 职称： 副教授 2017年 6 月 28 日攀枝花学院教务处制附件2: 攀枝花学院本科学生课程设计任务书题目散列表的设计与实现1、课程设计的目的1) 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。2) 使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。3） 使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。2、课程设计的内容和要求（包括原始数据、技术要求、工作要求等）【问题描述】设计散列表实现电话号码查找系统。【基本要求】1) 设每个记录有下列数据项：电话号码、用户名、地址；2) 从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；3) 采用一定的方法解决冲突；4) 查找并显示给定电话号码的记录；5) 查找并显示给定用户名的记录。【进一步完成内容】1) 系统功能的完善；2) 设计不同的散列函数，比较冲突率；3) 在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。3、主要参考文献1刘大有等，数据结构（C语言版），高等教育出版社2严蔚敏等，数据结构（C语言版），清华大学出版社3William 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 算法模块设计53.4.1 哈希算法53.5 二次探测再散列54 程序结构及源代码说明64.1程序结构说明64.1.1 哈希函数64.1.2 冲突处理函数64.2程序源码及说明75 程序测试及运行结果说明145.1 主菜单运行界面145.2 各项功能测试145.2.1用户信息录入145.2.2 冲突解决155.2.3 用户查找15总 结16参考文献18做事做实做事做实1 课程设计的目的和意义 数据结构主要介绍一些最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的：(1)了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；(2)初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；(3)提高综合运用所学的理论知识和方法独立分析和解决问题的能力；(4)训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。(5)锻炼动手操作能力，培养我们的创新思维能力。从编写代码，到调试程序，再到运行程序，这是设计的最重要环节，它需要我们用逻辑思维将我们所学知识和实际相结合，并在对方案的分析过程中能够有所创新，从而使运行方案更严谨更简洁。培养好良好的思维，便要将这种思维赋予实践，即动手操作能力。目前，市场上关于计算机运用、计算机软件和电子类相关专业的人才辈出，但毕业生在走进企业公司政府机构或研究单位之后，感觉到缺乏实际开发设计项目的经验，所以我们在课程设计中能够多训练，提高我们将知识融会贯通的能力(6)培养我们严谨治学的态度，以及认清自己学知识、运用知识的能力。不管是编写代码，调试代码，还是运行代码，需要我们严谨的思维和态度去对待，这样才能真正起到此设计的作用。我们也能够在设计中认识到自己对数据结构这门课程学习的欠缺，对以后我们的学习有着很大的指导和帮助。学习课程设计，编写程序，将数据结构和算法相结合，了解到数据结构、算法和程序之间的关系，更学习到数据结构和算法的最佳定位做事做实2 需求分析2.1 需求概述 在各个领域，不同的通讯录其功能都是为用户储存信息，查找信息提供方便的有效工具。一个内容全面、功能先进的通讯录对每个用户来说是一个理想的助手。现在，我们通过对散列表和基本操作的学习和理解，以及在掌握线性表等基本运算的基础上，实现对线性表操作。这里我们所做的通讯录则是在数据结构学习之后，利用计算机c程序语言编写的，可以实现数据的新建通讯录，添加记录，查询记录，修改记录，删除记录，显示记录功能的可执行程序。通过它可以进行对联系对象的姓名、地址、电话号码等的记录与查找。当然，该程序设计也有不足之处，我们一定会不断地努力去更正完善。很多涉及通讯录的操作的算法都是以顺序表操作为基础，通过顺序表的建立，初始化，结点添加、查询与删除的演示，方便在学习中更好的理解顺序表结点的添加、查询、删除的过程2.2 需求环境本课程设计需要的设备为硬件要求和软件配置要求具体要求如下：硬件要求：一台计算机。软件配置：WINDOWS、C/VC+6.0。2.3 功能描述 本次课题是的散列表设计与实现。主要是通过C+语言和数据结构算法实现，主要有以下功能:1.每个记录需要有存储的数据：姓名、电话、地址；2.从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；3.采用一定的方法解决冲突；4.查找并显示给定电话号码的记录；5.查找并显示给定用户名的记录。3 整体设计（方案设计）3.1 系统功能设计定义电话本记录数量（MAXSIZE）、表长（HASHSIZE）、姓名长度(MAX_SIZE)以及结构体typedef struct的内容，构造两个哈希函数hash1和hash2。功能示意图：录入子系统查询子系统姓名地址号码姓名查找号码查询电话号码管理系统图3.1功能示意图3.2 处理功能设计增加系统功能如下: 添加用户信息; 读取所有用户信息; 以姓名建立哈希表;以电话号码建立哈希表; 查找并显示给定用户名的记录; 查找并显示给定电话号码的记录; 清屏以及保存功能；处理流程示意图：开始进入录入系统获得关键字key用Hash1(key)计算地址比较nam_2(d)的值是否和关键字相等输出记录用探查序列d+i*hash2(key)计算（寻找）散列地址结束比较nam_Ht(d)的值是否和关键字相等未找到记录图3.2 处理流程图 3.3 主要模块键盘输入各人的信息:void getin()；显示输入的用户信息:void ShowInformation() ；除留余数法构造哈希函数:int Hash1()；构造把字符串转换成整型数哈希函数:int Hash2()；冲突处理函数:Status collision()；以姓名为关键字建表:void CreateHash1()；以姓名为关键字查表:void SearchHash1()；以电话号码为关键字建表:void CreateHash2()；以电话号码为关键字查表:void SearchHash2()；输出菜单函数:int main()。3.4 算法模块设计3.4.1 哈希算法输入待查找的值即key，即可查找到其对应的值即可。int Hash1(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%HASHSIZE; return m; 3.5 二次探测再散列冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址(即该地址单元为空)为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探查到开放的地址则表明表中无待查的关键字，即查找失败。int i,q;i=c/2+1;while(i=0) return q; else i=c/2+1; else q=(p-i*i)%HASHSIZE; c+; if(q=0) return q; else i=c/2+1;4 程序结构及源代码说明4.1程序结构说明4.1.1 哈希函数将用户名折叠处理，折叠处理后的数，用除留余数法构造哈希函数。建立，代码如下：int Hash1(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%HASHSIZE; return m; 4.1.2 冲突处理函数建立冲突处理函数，采用二次探测再散列法解决冲突，代码如下：tatus collision(int p,int &c) int i,q;i=c/2+1;while(i=0) return q; else i=c/2+1; else q=(p-i*i)%HASHSIZE; c+; if(q=0) return q; else i=c/2+1; return UNSUCCESS;4.2程序源码及说明#include#include#include#include#include #define MAXSIZE 20 /电话薄记录数量 #define MAX_SIZE 20 /人名的最大长度#define HASHSIZE 53 /定义表长 #define SUCCESS 1#define UNSUCCESS -1#define LEN sizeof(HashTable)typedef int Status;typedef char NAMAX_SIZE;typedef struct/记录NA name;NA tel;NA add;Record;typedef struct/哈希表Record *elemHASHSIZE; /数据元素存储基址int count; /当前数据元素个数int size; /当前容量HashTable;Status eq(NA x,NA y)/关键字比较，相等返回SUCCESS；否则返回UNSUCCESSif(strcmp(x,y)=0) return SUCCESS;else return UNSUCCESS;Status NUM_BER; /记录的个数void getin(Record* a)/键盘输入各人的信息coutNUM_BER;int i; for(i=0;iNUM_BER;i+) cout请输入第i+1ai.name; cout请输入第i+1ai.tel; cout请输入第i+1ai.add; /gets(str2);?void ShowInformation(Record* a)/显示输入的用户信息 int i;for( i=0;iNUM_BER;i+) coutn第i+1个用户信息:n 姓 名：ai.namen 电话号码：ai.teln 联系地址：ai.addn; void Cls(Record* a)cout*; system(cls);long fold(NA s)/人名的折叠处理char *p;long sum=0;NA ss;strcpy(ss,s);/复制字符串，不改变原字符串的大小写strupr(ss);/将字符串ss转换为大写形式p=ss;while(*p!=0) sum+=*p+; coutnsum=sum; return sum;int Hash1(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%HASHSIZE; /用除留余数法构造哈希函数return m; /并返回模值Status collision(int p,int &c)/冲突处理函数，采用二次探测再散列法解决冲突int i,q;i=c/2+1;while(i=0) return q; else i=c/2+1; else q=(p-i*i)%HASHSIZE; c+; if(q=0) return q; else i=c/2+1; return UNSUCCESS;void benGetTime();void CreateHash1(HashTable* H,Record* a)/建表，以人的姓名为关键字，建立相应的散列表benGetTime();int i,p=-1,c,pp; for(i=0;ielempp!=NULL) pp=collision(p,c); if(pp0) cout第i+1elempp=&(ai); /求得哈希地址，将信息存入 H-count+; cout第i+1个记录冲突次数为c.n;/需要显示冲突次数时输出coutn建表完成!n此哈希表容量为HASHSIZE,当前表内存储的记录个数为count.n;benGetTime();void SearchHash1(HashTable* H,int &c)/在通讯录里查找姓名关键字，若查找成功，显示信息benGetTime();NA str;coutstr;int p,pp;p=Hash1(str);pp=p;while(H-elempp!=NULL)&(eq(str,H-elempp-name)=-1) pp=collision(p,c);if(H-elempp!=NULL&eq(str,H-elempp-name)=1) coutn查找成功！n查找过程冲突次数为c以下是您需要要查找的信息：nn; cout姓 名：elempp-namen电话号码：elempp-teln联系地址：elempp-addn;else coutn此人不存在，查找不成功!n;benGetTime();void benGetTime()SYSTEMTIME sys; GetLocalTime( &sys ); coutsys.wYearsys.wMonthsys.wDaysys.wHoursys.wMinutesys.wSecondsys.wMilliseconds; void CreateHash2(HashTable* H,Record* a)/建表，以电话号码为关键字， benGetTime();int i,p=-1,c,pp; for(i=0;ielempp!=NULL) pp=collision(p,c); if(pp0) cout第i+1elempp=&(ai); /求得哈希地址，将信息存入 H-count+; cout第i+1个记录冲突次数为c。n;/需要显示冲突次数时输出coutn建表完成!n此哈希表容量为HASHSIZE,当前表内存储的记录个数为count.n;benGetTime();void SearchHash2(HashTable* H,int &c)/在通讯录里查找电话号码关键字，若查找成功，显示信息benGetTime();NA tele;couttele;int p,pp;p=Hash2(tele);pp=p;while(H-elempp!=NULL)&(eq(tele,H-elempp-tel)=-1) pp=collision(p,c);if(H-elempp!=NULL&eq(tele,H-elempp-tel)=1) coutn查找成功！n查找过程冲突次数为c以下是您需要要查找的信息：nn; cout姓 名：elempp-namen电话号码：elempp-teln联系地址：elempp-addn;else coutn此人不存在，查找不成功!n;benGetTime();void Save()FILE *fp;if(fp=fopen(c:test.txt, w)=NULL) printf(nERROR opening customet file);fclose(fp); int main(int argc, char* argv)int c,flag=1;HashTable *H;H=(HashTable*)malloc(LEN);for(int i=0;ielemi=NULL; H-size=HASHSIZE; H-count=0;Record aMAXSIZE;while (1) coutn ; coutn 欢迎使用电话号码查找系统 ; coutn ; coutn 哈希表的设计与实现 ; coutn 【1】. 添加用户信息 ; coutn 【2】. 读取所有用户信息 ; coutn 【3】. 以姓名建立哈希表(再哈希法解决冲突) ; coutn 【4】. 以电话号码建立哈希表(再哈希法解决冲突) ; coutn 【5】. 查找并显示给定用户名的记录 ; coutn 【6】. 查找并显示给定电话号码的记录 ; coutn 【7】. 清屏 ; coutn 【8】. 保存 ; coutn 【9】. 退出程序 ; coutn 温馨提示： ; coutn .进行5操作前 请先输出3 ; coutn .进行6操作前 请先输出4 ; coutn ; coutn; cout; coutnum; switch(num) case 1: getin(a); break; case 2: ShowInformation(a); break; case 3: CreateHash1(H,a); /* 以姓名建立哈希表 */ break; case 4: CreateHash2(H,a); /* 以电话号码建立哈希表 */ break; case 5: c=0; SearchHash1(H,c); break; case 6: c=0; SearchHash2(H,c); break; case 7: Cls(a); break; case 8: Save(); break; case 9: return 0; break; default: cout你输错了，请重新输入!; coutn; system(pause); return 0;5 程序测试及运行结果说明由需求分析可知，散列表的设计与实现主要电话号码查找功能，本程序已调试成功并实现了其功能，其运行结果如下：5.1 主菜单运行界面主菜单运行界面如图.所示：图5.1 主菜单运行界面5.2 各项功能测试5.2.1用户信息录入用户信息录入如图5.2：图5.2用户信息录入5.2.2 冲突解决冲突解决界面如图5.3： 图5.3 冲突解决5.2.3 用户查找用户查找界面如图5.4：图5.4 用户查找总 结数据结构的课程设计是大学时期第二个专业课的课程设计而数据结构这门课也是本学期的一门专业课 经过一个学期对数据结构的学习 应该说对这门课只有初步的认识掌握的并不是那么牢固。不过学期末的课程设计又教会了我该如何简单的去运用数据结构去解决问题。数据结构的算法和之前学习的 c 语言有着一些的区别在设计中不能一味的去用原来的 c 语言去实现算法和函数。 设计时可以为程序定义全局变量也可以为程序定义局部变量全局变量可以让程序看起来比较简洁局部变量虽说比较繁琐但是易懂且避免了一些不必要的错误发生。 在本次课程设计中分别用到了指针和引用两种不同的方式来设计程序两者各有利弊但最终选择指针作为最后版本所用到的。这一次我选择的课程设计题目是散列表的设计和查找可以说经过一个多星期设计不管是通过自己的努力、 查资料还是询问别人该如何做都是让我更加熟悉这一模块的内容掌握了哈希表其中的一些用法比如说折叠法除留余数法解决冲突的线性探测再散列和二次探测再散列等一些实用的方法。 当然这一部分不是只有这么一些内容还包括了其他的建立哈希表以及解决冲突的方法虽然教材中介绍的比较简单但依然包含了更多的知识就像整个数据结构一样一本教材是不可能把所有的知识点都讲到只是给我们介绍了一些基础知识一些可能用到相对来说比较简单的方法来解决遇到的问题这些方法知识对于我们现在处的一个阶段就已经很实用不能因为掌握了这一模块或者是这一本书就认为掌握了数据结构的全部。在课程设计中我很清楚的认识到了自己的不足而自己最大的不足就是少练对一些算法掌握不熟练构造函数时不知该如何使它来符合要求遇到了一些困难的困扰在查阅资料之后才能略微明白这些错误究竟是什么在自己实践操作下也是彻底明白了函数所要求的以及指针运用的错误。 还有一点不足就是基础知识掌握的不牢固此次课程设计又把哈希表部分内容反反复复的看尤其是哈希表的算法将此部分一点一点弄明白才开始动手设计程序。 而在不断地学习和设计中自己也对数据结构产生了浓厚的兴趣了解了它的实用性和可操作性使得程序设计起来不再是那么复杂和繁琐易懂也是它的一个有点。数据结构的课程设计的结束也是代表了这个学期的数据结构的结束当然数据结构这门学问依然充满了吸引力让我们去探索这是一个结束同样也是一个开始掌握好了基础才能更进一步学习和研究。 这一次的课程数据也是给了我一个教训一定要把基础掌握住才能练习才能做设计。数据结构的学习给我其他科目的学习提供了一定帮助杜绝眼高手低边学边练为我接下来几个学期对其他专业课的学习提供了宝贵的经验。这一次两个星期的课程设计给了我足够的时间来让我掌握该部分的知识并且了解到数据结构奥妙所在给了我以后努力学习数据结构的动力程序的成功设计也给了我一定的自信不再害怕自己设计程序时遇到错误而要勇于面对它程序中的错误是一定会被一些简单实用的方法给解决掉。 程序设计完成并且运行无误自己也是对自己感到满意对自己以后学习其他计算机语言也是打下了自信的基础并有了这一次的经历和所获得的经验也是对以后的学习提供了保障。参考文献1数据结构（C语言版），严蔚敏，清华大学出版社，20032数据结构题集，严蔚敏，清华大学出版社，20053数据结构（C语言版），刘大有，高等教育出版社，20044Data Structure with C+，William FordWilliam Topp，清华大学出版社，2003