1、 课课 程程 设设 计计 报报 告告 课程设计名称：数据结构数据结构课程设计课程设计 课程设计题目： 基于基于 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
2、函数的描述函数的描述 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函数的平均查找长度。 建立一个确定的对应关系
3、 f，使每个关键字和结构中的一个唯一的存储位置 相对应。在查找时，只要根据这个对应关系 f找到给定值 K 的像 f（K）所建立的 表即为哈希表。 1.2 功能要求功能要求 1. 用三种方法创建哈希函数，分别为除留取余法，随机数法和分割法。 2. 当哈希地址产生冲突时，利用线性探测再散列和伪随机数探测再散列进行冲 突处理得到新的哈希地址，并存入哈希表中。 3. 给出每个用户名的查找长度和该函数的平均查找长度， 并比较哪种方法最好。 1.3 基本功能基本功能 1. CreateHashList() 建立 Hash函数，并采用两种冲突处理方法进行操作。 2. SearchHash() 查找 Hash
4、表，将用户所输入的信息从 Hash表中调出，并给出查找长度 2 2 系统功能模块结构图 2.1 系统功能结构框图系统功能结构框图 图图 2.1 2.1 系统功能结构框图系统功能结构框图 2.2 系统主要模块的功能说明系统主要模块的功能说明 1. 哈希模块 CreateHashList()； （adr 为哈希地址） 初始化 Hash表，并创建 Hash函数，并将用户姓名添加至 Hash表中。 1) 除留取余法：adr=(DATALISTi.k)%M;（将 DATALISTi.k 所存的 ASCII 码除以 M 取余所得的哈希地址赋给 adr） 2) 随机函数法: srand(DATALISTi.
5、k); int adr=rand()%L;(将 DATALISTi.k 所存的ASCII码作为 种子传入至 srand 函数中，并用 rand 函数产生 L 以内的 随机值为哈希地址赋给 adr) 创建 Hash表 哈希函数模块 （除 留取余） 哈希函数模块 （随 机数法） 哈希函数模块 （分 割法） 冲突处理模块 冲突处理模块 冲突处理模块 冲突处理模块 查找模块 冲突处理模块 冲突处理模块 查找模块 查找模块 3 3) 分割法: change(DATALIST,A,i); int adr=A1*10+A2;( DATALISTi.k 所存的 ASCII 码利用 change()函数分割开，
6、 并去第二个数字和第三个数字作为哈希 地址赋给 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 03 32 60 61 62 71 记录 关键字 (关键字）2 哈希地址（217-29） A I J I0 P1 P2 Q1 Q2 Q3 0100 1100 1200 1160 2061 2062 2161 2162 2
