1、 数据结构课程设计数据结构课程设计 设计说明书设计说明书 哈希表的实现与应用哈希表的实现与应用 学生姓名 学 号 班 级 成 绩 指导教师 曹记东 2012 2012 年年 3 3 月月 3 3 日日数据结构数据结构课程设计评阅书 题 目 哈希表的实现与应用哈希表的实现与应用 学生姓名 学号 指导教师评语及成绩 成绩： 教师签名： 年 月 日 答辩教师评语及成绩 成绩： 教师签名： 年 月 日 教研室意见 总成绩： 室主任签名： 年 月 日 摘要摘要 随着计算机的普及，社会的信息化不断普及提高，在此课程设计中。设计了一个人员 信息查找系统，本查找系统采用VC+作为软件开发环境，采用本系统可以简
2、单地实现人员信息的 查询，显示所有人员的信息。在编制人员的信息中，具有人员的姓名、联系电话、以及人员的地址。 在插入人员信息中，采用以姓名为关键字插入，实现了哈希值的插入运算。在查询具体人员的信息是 可以采用以姓名为关键查人员信息，也可以采用以号码作为关键字查找人员信息。在用姓名作为关键 字查询信息时采用二次散列法处进行冲突处理，在以电话号码进行人员的信息查找时采用线性探测法 处理冲突。 在界面设设计方面界面清晰，明了。操作简单，易于用户所接受。 关键词：关键词：哈希表;信息查找系统;函数 目录 1 课题描述 1 2 需求分析 2 3 设计概要 2 3.1 系统菜单 2 3.2 各个模块之间调
3、用关系 3 3.3 数据结构描述与定义 4 3.4 各个模块主要算法描述及流程图 5 4 详细设计 11 4.1 程序描述 11 4.2 具体步骤 11 5 程序编码 14 6 程序调试与测试 25 7 结果分析 32 8 总结 33 参考文献 34 1 1 课题描述课题描述 散列表(也叫哈希表),是根据关键码值直接进行访问的数据结构,也就是说,它通过把关键码值映 射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做 散列表。 本课程设计只要完成以下任务： 1）完成哈希表的初始化、哈希函数值的运算、插入元素、查找元素。 2）求出每次哈希表查找的平均查找长度
4、 ASL。 3)利用线形探测和二次探测再散列处理冲突的功能。 2 2 需求分析需求分析 哈希表是用散列表 建立关键码字与其存储位置的对应关系，或者说，由关键码的函数值决定数 据的存储地址，是根据关键码值直接进行访问的数据结构,查找速度极快（O(1)）,查找效率与元素个 数 n 无关！在设计中需要实现哈希表的初始化、插入运算，以及每次查找的哈希表的平均长度 ASL,同 时在设计中要实现用线性探测和二次散列两种方法处理冲突等功能。在建立哈希表中建立的不同哈希 表会有不同的平均长度，同不同的处理冲突方法会有不同的平均查找长度。 3 3 设计概要设计概要 进入主函数,用户输入需要功能代号进入选择选 1
5、:建立用户信息,选。2.显示所有用 户信息。3.以姓名关键字插入用户信息。4。以姓名产生哈希表。5，以号码产生哈希表。 6，以姓名查找关键字。7 以号码查找用户信息。0，退出系统。分别以上述确定的方法分 别以用户名为检索以及以以电话号码将用户信息添加到哈希表。 在查找用户信息时必须先 建立哈希表（先进行 4、5 步骤） 。只需输入用户的姓名或号码就可以查找到用户信息。程 序用结构体存储用户信息， 建立的哈希表方便快速的查找到用户信息。 程序用链表的方式 存储信息以及构造哈希表 具体流程图如下所示: 3.1 功能模块功能模块 图 3.2 菜单系统 查询系统菜单 main() getin() ; 建 立 相应 的用 户信 息 ShowI nform ation()
