数据结构课程设计散列表的设计与实现.doc

榆林学院14届课程设计 散列表的设计与实现课程设计说明书 学生姓名： 学 号： 院 系： 信息工程学院 专 业： 计算机科学与技术 班 级： 计14本1 指导教师： 答辩时间： 2015 年 12 月 31 日 目录摘要1Abstract2第一章 绪论31. 数据结构简介32. 应用技术领域及范围33.设计的原理、方法和主要内容3第二章 需求分析41. 任务需求42. 功能需求43. 设计目的44. 设计要求4第三章 系统设计61. 设计思想62. 实现方法63. 主要模块64. 系统功能设计6第四章 系统实现及调试81. 系统功能流程82. 功能模块实现及调试9总结11参考文献11摘要散列表的设计与实现所涉及到的操作算法都是以链表或顺序表的基本运算作为基础的，此程序通过通讯录实现，包括建立通讯录，添加记录，查询记录，删除记录，显示记录，修改记录。通过顺序表存储结构实现数据的输入，实现各子程序过程的演示，对异常输入信息报错。 关键字：新建通讯录，添加记录，查询记录，修改记录，删除记录，显示记录，散列表，散列函数，处理冲突AbstractThe design and implementation of the hash table are based on the basic operations of the list or sequence table. This program is implemented by the address book, including the establishment of the address book, adding records, record, delete records, record, modify records. Through sequential table storage structure to achieve data input, to achieve the process of the subroutine, the exception of the input information.  Key words: new address book, add records, record, modify records, delete records, display records, hash table, hash function, handling conflict.第一章 绪论1. 数据结构简介数据结构是计算机程序设计的重要理论设计基础，它不仅是计算机学科的核心课程，而且成为其他理工专业的热门选修课。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。在计算机科学中，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。“数据结构”在计算机科学中是一门综合性的专业基础课。数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。2. 应用技术领域及范围在各个领域，不同的通讯录其功能都是为用户储存信息，查找信息提供方便的有效工具。一个内容全面、功能先进的通讯录对每个用户来说是一个理想的助手。现在，我们通过对散列表和基本操作的学习和理解，以及在掌握线性表等基本运算的基础上，实现对线性表操作。这里我们所做的通讯录则是在数据结构学习之后，利用计算机c程序语言编写的，可以实现数据的新建通讯录，添加记录，查询记录，修改记录，删除记录，显示记录功能的可执行程序。通过它可以进行对联系对象的姓名、地址、电话号码等的记录与查找。当然，该程序设计也有不足之处，我们一定会不断地努力去更正完善。 很多涉及通讯录的操作的算法都是以顺序表操作为基础，通过顺序表的建立，初始化，结点添加、查询与删除的演示，方便在学习中更好的理解顺序表结点的添加、查询、删除的过程。3.设计的原理、方法和主要内容 通讯录原理是我们所学的散列表的设计与实现的应用，并且是在数据老师的指导下编写的源程序。得到了自己所设计的结果。散列表的方法是通过访问key而直接访问存储的value值。它的key - value之间存在一个映射函数，我们可以通过key值和“看不到”的映射函数（散列函数）访问对应的value值。这加快了查找的速度！存放记录的数组称做散列表。散列方法不同于顺序查找、二分查找、二叉排序树及B-树上的查找。它不以关键字的比较为基本操作，采用直接寻址技术 （就是说，它是直接通过key映射映射函数，实现的方式有多种 到内存地址上去的）。 第二章 需求分析1. 任务需求 设计散列表通讯录实现电话号码查找系统2. 功能需求1. 每个记录需要有存储的数据：姓名、电话、地址；2. 从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；3. 采用一定的方法解决冲突；4. 查找并显示给定电话号码的记录；5. 查找并显示给定用户名的记录。6. 【进一步完成内容】1)系统功能的完善；2)设计不同的散列函数，比较冲突率；3)在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。3. 设计目的课程设计是数据结构课程教学必不可缺的一个重要环节，它可加深学生对该课程所学内容的进一步的理解与巩固，是将计算机课程与实际问题相联接的关键步骤。通过课程设计，能够提高学生分析问题、解决问题，从而运用所学知识解决实际问题的能力，因而必须给予足够的重视。4. 设计要求1明确课程设计任务，复习与查阅有关资料。2按要求完成课程设计内容，课程设计报告要求文字和图工整、思路清楚、正确。3应用程序应具有一定的可用性：（1）凡等候用户输入时，给出足够的提示信息，如“Please Select（13）：”提示用户选择。（2）格式明显易懂，配上适当的颜色、声音等辅助效果，能方便地改正输入时的错误，使用户感到方便、好用。（3）有联机求助功能。用户能直接从系统得到必要的提示，不查手册也能解决一些疑难。4程序具有一定的健壮性，不会因为用户的输入错误引起程序运行错误而中断执行：（1）对输入值的类型、大小范围、字符串的长度等，进行正确性检查，对不合法的输入值给出出错信息，指出错误类型，等待重新输入。（2）当可能的回答有多种时，应允许输入任何一种回答。（3）对删除数据应给出警告。第三章 系统设计1. 设计思想要用散列表设计实现电话号码查询系统，对存入的联系人的名字电话以及地址进行存储,并在输入电话号码或姓名后得出此记录的所有信息,要求有菜单界面和清屏功能.首先，此程序，多次用到哈希函数，此处先用除留余数法对折叠后的数构造哈希函数,再用二次探测再散列法建立冲突处理函数解决冲突,再以电话号码和姓名为关键字建立散列表(若哈西地址冲突进行冲突处理),在此之前,必须先用一系列输出函数输出一个菜单.整个程序的设计思路到此结束。2. 实现方法根据系统功能要求，可以将实现方法分为以下步骤： （1）应用系统分析，建立该系统的功能模块框图以及界面的组织和设计；（2）分析系统中的各个数据及它们之间的关系； （3）根据问题描述，设计系统的类层次； （4）完成各个函数的声明； （5）完成各个成员函数的定义； （6）完成系统的应用模块； （7）功能调试；（8）完成系统总结报告。3. 主要模块 键盘输入各人的信息:void getin()； 显示输入的用户信息:void ShowInformation() ；除留余数法构造哈希函数:int Hash1()； 构造把字符串转换成整型数哈希函数:int Hash2()； 冲突处理函数:Status collision()； 以姓名为关键字建表:void CreateHash1()； 以姓名为关键字查表:void SearchHash1()； 以电话号码为关键字建表:void CreateHash2()； 以电话号码为关键字查表:void SearchHash2()； 输出菜单函数:int main()。 4. 系统功能设计定义电话本记录数量（MAXSIZE）、表长（HASHSIZE）、姓名长度（MAX_SIZE）及结构体typedef struct的内容，构造两个哈希函数hash1和hash2.功能示意图如下：录入子系统查询子系统姓名地址号码姓名查找号码查询电话号码管理系统图1 功能示意图图图第四章 系统实现及调试1. 系统功能流程 增加系统功能如下: 添加用户信息; 读取所有用户信息; 以姓名建立哈希表;以电话号码建立哈希表; 查找并显示给定用户名的记录; 查找并显示给定电话号码的记录; 清屏以及保存功能；处理流程示意图如下：图2 处理流程示意图2. 功能模块实现及调试 1） 运用main函数输出电话本信息系统的整体界面，在调试运行后如下：图3 调式运行图2） 利用添加功能void getin(Record* a)实现用户信息的录入，在调试运行后如下：图4 用户信息录入图3） 利用哈希函数CREATEHASH1.2来构造哈希表并用Status collision函数的相应功能来查找并解决冲突：图5 解决冲突和构造哈希表图4） 利用void SearchHash1(HashTable* H,int &c)在通讯录里查找姓名关键字，若查找成功，显示信息，c用来记录冲突次数,查找成功时显示冲突次数：图6 查找姓名关键字的结果和冲突次数截图总结通过这一次的课程设计，我对软件编程的基础数据结构有了更好的理解，知道了数据结构在编程中的作用。同时，也增加了我对学习软件编程的兴趣，为以后的学习打下了好的基础。当然，也加深了我对C语言的理解，懂得了C语言编程的一些重要的知识。对于数据结构和算法，虽然我目前的理解还不深，但是，这次课程设计后，我相信我以后慢慢地会了解的更深。在编写程序设计散列表的设计和应用的代码中，遇到了一些错误，最终，经过我上网查询才解决了。在实际操作过程中犯的一些错误还会有意外的收获，感觉很有意思。在具体操作中对这学期所学的数据结构的理论知识得到巩固，达到设计的基本目的，也发现自己的不足之处，在以后的上机中应更加注意，同时体会到算法应具有的语句简洁，简单易懂，可读性高，使用灵活，执行效率高等特点。计算机编程的学习，主要靠自己的自学，不懂就得去问，找到解决的方法。 参考文献1.严蔚敏. 数据结构（C语言版）. 清华大学出版社. 20022.李庆华.刘秀娟.王春光函数递归调用问题的简化读程方法 -长春大学学报2003,13(3)3.苏仕民.数据结构课程设计 北京：机械工业出版社.20054.Sartaj Sahni. Data Structure, Algorithms, and Application in C+. The McGraw-Hill Company Inc.1998M (第一版) (数据结构、算法与应用C+语言描述.北京:机械工业出版社.19995.Willan Ford,Willian Topp. Data Structures with C+. New Jersey:Prentice Hall Inc, Adivision Simon & Schuster Company,1996M (第一版) (数据结构C+语言描述.北京:清华大学出版社，19976.徐孝凯.数据结构实用教程（C/C+描述）M. (第一版)北京:清华大学出版社.19997.程杰.大话数据结构 北京：清华大学出版社.2011