课程设计(论文)任务书软件学院学院软件工程专业班一、课程设计(论文)题目：通讯录管理系统的设计与实现——哈希表二、课程设计(论文)工作自2016 年 1 月 4 日起至 2016 年 1 月 10 日止三、课程设计(论文) 地点: 软件测试中心（北区测试二室）四、课程设计(论文)内容要求：1．本课程设计的目的⑴训练学生灵活应用所学数据结构知识，独立完成问题分析，结合课程的理论知识，编写程序求解指定问题；⑵初步掌握软件开发过程的问题分析、系统设计、编码、测试等基本方法和技能；⑶提高综合运用所学的理论知识和方法独立分析和解决问题的能力，巩固、深化学生的理论知识，提升编程水平。
2．课程设计的任务及要求1）基本要求：⑴要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编写上机程序和上机调试等若干步骤完成题目，最终写出完整的报告；⑵在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率；⑶程序设计语言推荐使用C/C++，程序书写规范，源程序需加必要的注释；⑷每位同学需提交可独立运行的程序和规范的课程设计报告。
2）课程设计论文编写要求⑴理论设计部分以课程设计论文的形式提交，格式必须按照课程设计论文标准格式进行书写和装订；⑵课程设计报告包括中文目录、设计任务、需求分析、概要设计、详细设计、编码实现、调试分析、课设总结、谢辞、参考文献、附录等；⑶设计部分应包含系统功能模块图，调试分析应包括运行截图等。
3）课程设计评分标准：⑴学习态度：10分；⑵系统设计：20分；⑶编程调试：20分；⑷回答问题：20分；⑸论文撰写：30分。
⑴严蔚敏李冬梅吴伟民著.数据结构(C语言版)[M]. 人民邮电出版社. 2015.2⑵李春葆. 数据结构教程上机实验指导[M]. 清华大学出版社. 2013.1⑶何钦铭,冯燕等. 数据结构课程设计[M]. 浙江大学出版社. 2007.85）课程设计进度安排⑴准备阶段（4学时）：选择设计题目、了解设计目的要求、查阅相关资料；⑵程序模块设计分析阶段（4学时）：程序概要设计、详细设计；⑶代码编写调试阶段（8学时）：程序模块代码编写、调试、测试；⑷撰写论文阶段（4学时）：总结课程设计任务和设计内容，撰写课程设计论文。
学生签名：2016 年 1 月4 日6）课程设计题目具体要求：任务：利用哈希表完成通讯录的一般性管理工作：(1) 添加信息；(2) 显示信息：可以按照手机或联系人的姓名拼音排序显示；(3) 查找：用名字和手机号分别作为查找的依据，进行查找；(4) 编辑信息；(5) 删除信息；(6) 保存到文件；要求：(1)每条记录至少包括姓名、手机、QQ、电子邮箱、城市、邮编等信息。
(2)界面友好，演示程序以用户和计算机的对话方式进行，可反复操作。
课程设计(论文)评审意见（1）学习态度（10分）：优（）、良（）、中（）、一般（）、差（）；（2）系统设计（20分）：优（）、良（）、中（）、一般（）、差（）；（3）编程调试（20分）：优（）、良（）、中（）、一般（）、差（）；（4）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（5）论文撰写（30分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性及考勤是否降等级：是（）、否（）评阅人：职称：讲师2016 年1 月12 日目录一.设计任务------------------------------------------------------------------------------- 1二.需求分析------------------------------------------------------------------------------- 1三.系统设计------------------------------------------------------------------------------- 2四.编码实现------------------------------------------------------------------------------- 6五.调试分析------------------------------------------------------------------------------- 10六.课设总结------------------------------------------------------------------------------- 15七.谢辞------------------------------------------------------------------------------------- 15八.参考文献-------------------------------------------------------------------------------- 15一、设计任务通讯录管理系统的设计与实现——哈希表任务：利用哈希表完成通讯录的一般性管理工作：(1)添加信息；(2)显示信息：可以按照手机或联系人的姓名拼音排序显示；(3)查找：用名字和手机号分别作为查找的依据，进行查找；(4)编辑信息；(5)删除信息；(6)保存到文件；要求：(1)每条记录至少包括姓名、手机、QQ、电子邮箱、城市、邮编等信息。
(2)界面友好，演示程序以用户和计算机的对话方式进行，可反复操作。
二、需求分析本问题的关键和难点在于如何解决散列的问题。
由于结点的个数无法的知，并且如果采用线性探测法散列算法，删除结点会引起“信息丢失”的问题。
所以采用链地址法散列算法。
采用拉链法，当出现同义词冲突时，使用链表结构把同义词链接在一起，即同义词的存储地址不是散列表中其他的空地址。
首先，解决的是定义链表结点，在拉链法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成.name[16] 、num[11]和address[20]都是char浮点型，输入输出都只能是浮点型的。
采用拉链法，其中的所有同义词构成一个单链表，再由一个表头结点指向这个单链表的第一个结点。
这些表头结点组成一个一维数组，即哈希表。
数组元素的下标对应由散列函数求出的散列地址。
其次，设计散列函数，本程序需要设计两个散列函数才能解决问题，程序需要分别为以电话号码和用户名为关键字建立哈希表。
所以要分别以用户名、号码为关键字建立两个散列函数，对于以号码为关键字的散列函数，是将十一个数字全部相加，然后对20求余。
得到的数作为地址。
对于以用户名为关键字的散列函数，是将所有字母的ASCLL 码值相加，然后对20求余。
再次，需要实现添加结点的功能，则其中必须包括一个输入结点信息、添加结点的函数；需要实现查找函数，则必须包括一个查找结点的函数；需要对文件进行保存，则必需要包括保存文件函数。
还需要包括一个主菜单和一个主函数。
三、系统设计在拉链法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成，链地址法结点结构如图：name[16] num[11] address[20] next其中name[16]和num[11]是分别为以电话号码和用户名为关键字域，存放关键字；address[20] 为结点的数据域，用来存储用户的地址。
Next指针是用来指向下一个结点的地址。
主要算法的流程图如下：初始化散列链表（1）并为其动态分配内存空间初始化散列链表（2）并为其动态分配内存空间Hash：SASH2:Apend()FIND:首先定义结点结构体类型，在拉链法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成，链地址法结点结构如图：name[16] num[11] a ddress[20] next其中name[16]和num[11]是分别为以电话号码和用户名为关键字域，存放关键字；address[20]为结点的数据域，用来存储用户的地址。
next指针是用来指向下一个结点的地址。
#include<fstream> 用来输入/输出文件流类包含的文件是fstream。
unsigned int key 和unsigned int key2由于题目要求分别以电话号码和用户名为关键字，所以在此设计两个关键字。
其次，设计两个hash（）函数，以电话号码为关键字建立哈希函数hash(char num[11])。
哈希函数的主旨是将电话号码的十一位数字全部加起来，然后在对20求余。
将计算出来的数作为该结点的地址赋给key。
以用户名为关键字建立哈希函数hash2(char name[8])。
利用强制类型转换，将用户名的每一个字母的ASCLL码值相加并且除以20后的余数。
将计算出来的数作为该结点的地址赋给key2。
再次，建立结点，并添加结点，利用拉链法解决冲突。
建立结点应包括动态申请内存空间。
向结点中输入信息。
同时将结点中的next指针等于null。
添加结点，首先需要利用哈希函数计算出地址即关键字，其次将该结点插入以关键字为地址的链表后，当然由于分别以用户名和电话号码为关键字，所以分两种情况，如果以用户名为关键字则调用void hash2(char name[8])函数，并且将结点插入对应的散列链表中，如果以电话号码为关键字则调用void hash(char num[11])函数，并且将结点插入对应的散列链表中。
并且，需要两个建立散列链表的函数，分别动态申请一定的空间，用于动态申请散列链表。
void create()用来动态创建以电话号码为关键字的链表数组，void create2()用来动态创建以用户名为关键字的链表数组。
同样，需要两个显示链表的函数，利用for循环和while语句将表中信息按要求输出来。
想要实现查找功能，同样需要两个查找函数，无论以用户名还是以电话号码为关键字，首先，都需要利用hash函数来计算出地址。
再依次对比，如果是以电话号码为关键字，比较其电话号码是否相同，如果相同则输出该结点的所有信息，如果以用户名为关键字，则比较用户名是否相同，如果相同则输出该结点的所有信息。
如果找不到与之对应相同的，则输出“无记录”。
同时需要一个保存文件的函数，利用一个for循环，当用hash函数计算的地址，在链表的动态申请的数组范围之内，则创建一个文件流对象，并将结点信息保存在该文件中。