基于Hash表的班级成员管理_数据结构课程设计.doc

沈阳航空航天大学 课课 程程 设设 计计 报报 告告 课程设计名称 数据结构课程设计数据结构课程设计 课程设计题目 基于基于 HashHash 表的班级成员管表的班级成员管 理理 院 系 计算机学院 专 业 班 级 学 号 姓 名 指导教师 沈阳航空航天大学课程设计报告 I 目目 录录 1 题目介绍和功能要求题目介绍和功能要求 1 1 1 题目介绍 1 1 2 功能要求 1 1 3 基本功能 1 2 系统功能模块结构图系统功能模块结构图 2 2 1 系统功能结构框图 2 2 2 系统主要模块的功能说明 2 3 使用的数据结构的描述使用的数据结构的描述 4 3 1 数据结构设计 4 3 2 数据结构用法说明 4 4 函数的描述函数的描述 5 4 1主要函数设计 5 4 2 主要函数流程图 5 5 程序测试和运行的结果程序测试和运行的结果 8 5 1 程序测试 8 5 2 运行结果 9 6 参考文献参考文献 11 附附 录 关键部分程序清单 录 关键部分程序清单 12 沈阳航空航天大学课程设计报告 1 1 题目介绍和功能要求 1 1 题目介绍题目介绍 针对本班成员以姓名为关键字设计一个 Hash 表 使得平均查找长度不超过 R 要求 1 自行设计至少 3 中 Hash 函数 2 每种 Hash 函数采用线性探测再散列和伪随机数探测再散列进行冲突处理 针对本班成员给出每种 Hash 函数的平均查找长度 建立一个确定的对应关系 f 使每个关键字和结构中的一个唯一的存储位置 相对应 在查找时 只要根据这个对应关系 f 找到给定值 K 的像 f K 所建立的 表即为哈希表 1 2 功能要求功能要求 1 用三种方法创建哈希函数 分别为除留取余法 随机数法和分割法 2 当哈希地址产生冲突时 利用线性探测再散列和伪随机数探测再散列进行冲 突处理得到新的哈希地址 并存入哈希表中 3 给出每个用户名的查找长度和该函数的平均查找长度 并比较哪种方法最好 1 3 基本功能基本功能 1 CreateHashList 建立 Hash 函数 并采用两种冲突处理方法进行操作 2 SearchHash 查找 Hash 表 将用户所输入的信息从 Hash 表中调出 并给出查找长度 沈阳航空航天大学课程设计报告 2 2 系统功能模块结构图 2 1 系统功能结构框图系统功能结构框图 创建 Hash 表 哈希函数模块 除留取余 哈希函数模块 随机数法 哈希函数模块 分割法 冲突处理模块冲突处理模块冲突处理模块 冲突处理模块查找模块冲突处理模块冲突处理模块查找模块查找模块 图图 2 12 1 系统功能结构框图系统功能结构框图 2 2 系统主要模块的功能说明系统主要模块的功能说明 1 哈希模块 CreateHashList adr 为哈希地址 初始化 Hash 表 并创建 Hash 函数 并将用户姓名添加至 Hash 表中 1 除留取余法 adr DATALIST i k M 将 DATALIST i k 所存的 ASCII 码除以 M 取余所得的哈希地址赋给 adr 2 随机函数法 srand DATALIST i k int adr rand L 将 DATALIST i k 所存的 ASCII 码作 为种子传入至 srand 函数中 并用 rand 函数产生 L 以内 的随机值为哈希地址赋给 adr 沈阳航空航天大学课程设计报告 3 3 分割法 change DATALIST A i int adr A 1 10 A 2 DATALIST i k 所存的 ASCII 码利用 change 函数分割开 并去第二个数字和第三个数字作为哈希 地址赋给 adr 2 冲突处理模块 1 srand 姓名 ASCII 码 d d rand L M 伪随机探测再散列 2 d d 1 线性探测再散列 3 查找模块 SearchHash 查找用户输入姓名是否在 Hash 表中 给出该姓名的查找长度和该 Hash 函数的平均查找长度 沈阳航空航天大学课程设计报告 4 3 使用的数据结构的描述 3 1 数据结构设计数据结构设计 建立一个确定的对应关系 f 使每个关键字和结构中的一个唯一的存储位置 相对应 在查找时 只要根据这个对应关系 f 找到给定值 K 的像 f K 为存储地 址的结构体数组即为哈希表 哈希表举例 平方取中法 A B C Z 0 1 2 9 01 02 0332 60 61 62 71 记录关键字 关键字 2哈希地址 217 29 A I J I0 P1 P2 Q1 Q2 Q3 0100 1100 1200 1160 2061 2062 2161 2162 2163 0010000 1210000 1440000 1370400 4310541 4314704 4734741 4741304 4745651 010 210 440 370 310 314 734 741 745 表表 3 13 1 哈希表哈希表 3 2 数据结构用法说明数据结构用法说明 取关键字平方后的中间几位为哈希地址 这是一种比较常用的构造哈希函数 的方法 通常在选定哈希函数时不一定能知道关键字的全部情况 取其中哪几位 也不一定合适 而一个数平方后的中间几位数和数的每一位都相关 由此使随即 分布的关键字得到的哈希地址也是随即的 取的位数由表长决定 如表 3 1 列出 了一些标识符及它们的哈希地址 沈阳航空航天大学课程设计报告 5 4 函数的描述 4 1 主要函数设计主要函数设计 1 Input 作用作用 将用户姓名换算成 ASCII 码 2 CreateHashList 作用作用 将用户名输入至哈希表中 并用两种冲突处理方法进行冲突处理 3 SearchHash 作用作用 将用户输入的用户名在哈希表中进行查找 并给出查找结果和查找 长度 和该函数的平均查找长度 4 Print 作用作用 打印出程序的主菜单和界面 5 Change 作用作用 将用户姓名的 ASCII 码分割为多个数字并存入数组中 4 2 主要函数流程图主要函数流程图 1 CreateHashList 沈阳航空航天大学课程设计报告 6 开始 Num 哈希表初始化 哈希函数处理 线性探测再散列冲 突处理后将数据导 入哈希表中 判断冲突 将数据导入哈希表 中 Y N 1 哈希表初始化 哈希函数处理 判断冲突 将数据导入哈希表 中 Y N 伪随机数探测再散 列冲突处理后将数 据导入哈希表中 2 结束 图图 4 2 14 2 1 创建函数流程图创建函数流程图 2 SearchHash 沈阳航空航天大学课程设计报告 7 开始 将姓名转化为 ASCII码 判断是否一样和 哈希表中的数据 Return SUCCESS Y 冲突处理 N 判断是否一样和 哈希表中的数据 Return SUCCESS Y Return UNSUCCESS N 结束 图图 4 2 24 2 2 查找函数流程图查找函数流程图 沈阳航空航天大学课程设计报告 8 5 程序测试和运行的结果 5 1 程序测试程序测试 程序开始菜单 图图 5 1 15 1 1 一号菜单图一号菜单图 输入 1 或者 2 图图 5 1 25 1 2 二号菜单图二号菜单图 输入 1 图图 5 1 35 1 3 查找图查找图 输入 2 图图 5 1 45 1 4 平均查找图平均查找图 沈阳航空航天大学课程设计报告 9 5 2 运行结果运行结果 给出 3 组数据 每组数据 29 个用户名 分别用三种哈希函数和两种冲突处理 方法进行操作 结果如图 1 数据 1 1 除留取余法 一 线性探测再散列 二 伪随机数探测再散列 2 随机数法 一 线性探测再散列 二 伪随机数探测再散列 3 分割法 一 线性探测再散列 二 伪随机数探测再散列 2 数据 2 1 除留取余法 一 线性探测再散列 二 伪随机数探测再散列 2 随机数法 一 线性探测再散列 二 伪随机数探测再散列 3 分割法 一 线性探测再散列 二 伪随机数探测再散列 3 数据 3 1 除留取余法 一 线性探测再散列 二 伪随机数探测再散列 沈阳航空航天大学课程设计报告 10 2 随机数法 一 线性探测再散列 二 伪随机数探测再散列 3 分割法 一 线性探测再散列 二 伪随机数探测再散列 结论 结论 经比较可知 分割法所建立的哈希函数平均查找长度最短 沈阳航空航天大学课程设计报告 11 6 参考文献 1 高富平 张楚 电子商务法 M 北京 北京大学出版社 2002 2 Huang S C Huang Y M Shieh S M Vibration and stability of a rotating shaft containing a transerse crack J J Sound and Vibration 1993 162 3 387 401 3 谭浩强著 C 程序设计 第三版 北京 清华大学出版社 2005 4 数据结构 C 语言版 严蔚敏 吴伟明编著 北京 清华大学出版社 2007 沈阳航空航天大学课程设计报告 12 附 录 关键部分程序清单 include include include define L 50 哈希表的长度 define RAND MAX 10 随机数范围 define M 47 除留取余数值 define NAME NO 29 人名的个数 define SUCCESS 1 define UNSUCESS 0 define ElemType char typedef struct Hash 哈希表 ElemType data int s 查找长度 int k 当前姓名的 ASCII 码 Hash Hash hlist L typedef struct DATE 班级成员 char data 姓名 int k 姓名 ASCII 码 DATA DATE DATALIST NAME NO void input 姓名 结构体数组 初始化 char m int r s0 i DATALIST 0 data hudi DATALIST 1 data lijing DATALIST 2 data peiting DATALIST 3 data yinhang DATALIST 4 data liulu DATALIST 5 data lishengnan DATALIST 6 data cuililong DATALIST 7 data songchongyuan DATALIST 8 data xiejinhua DATALIST 9 data mashuangmin DATALIST 10 data wangjing DATALIST 11 data qiyueyu DATALIST 12 data gaozhiwei DATALIST 13 data fuzedong DATALIST 14 data shidailong 沈阳航空航天大学课程设计报告 13 DATALIST 15 data sujun DATALIST 16 data zhangxinglei DATALIST 17 data liuyang DATALIST 18 data liushuxin DATALIST 19 data fengkunkun DATALIST 20 data suzheng DATALIST 21 data sunjianwei DATALIST 22 data mengbaiyu DATALIST 23 data yushaolong DATALIST 24 data lishaolun DATALIST 25 data zhangkuo DATALIST 26 data wangdanran DATALIST 27 data lizhanying DATALIST 28 data yangjun for i 0 i NAME NO i s0 0 m DATALIST i data for r 0 m r 0 r s0 m r s0 DATALIST i k s0 int CreateHashList 建立哈希表 int i num sum printf 请选择冲突处理方法 n printf 1 线性探测再散列 n printf 2 伪随机数探测再散列 n scanf d switch num case 1 for i 0 i L i 哈希表的初始化 hlist i data hlist i k 0 hlist i s 0 for i 0 i L i sum 0 int adr DATALIST i k M 哈希函数 除留取余 沈阳航空航天大学课程设计报告 14 if i NAME NO break int d adr if hlist adr s 0 hlist adr k DATALIST i k hlist adr data DATALIST i data hlist adr s 1 此处已有数据 else do d d 1 线性探测再散列法处理冲突 sum sum 1 查找次数加 1 while hlist d s 0 hlist d k DATALIST i k hlist d data DATALIST i data hlist d s sum 1 return 1 break case 2 for i 0 i L i 哈希表的初始化 hlist i data hlist i k 0 hlist i s 0 for i 0 iL strlen hlist adr data 0 return UNSUCESS adr adr 1 n if stricmp hlist adr data name 0 k hlist adr s return SUCCESS 沈阳航空航天大学课程设计报告 16 int SearchHash2 char name Hash hlist int k k 为查找次数 伪随机数探测查找 int s0 0 r n 1 n 为初始查找长度 for r 0 name r 0 r s0 name r s0 int adr s0 M if stricmp hlist adr data name 0 k hlist adr s return SUCCESS else while 1 if n L strlen hlist adr data 0 return UNSUCESS srand s0 adr adr rand L M n if stricmp hlist adr data name 0 k hlist adr s return SUCCESS void print printf n printf n printf n printf 哈希表 n printf n printf n printf n printf n 沈阳航空航