散列表线性探测查找.docVIP

XXX学院 《计算机软件设计》课程设计（实习）报告 题　目 散列表的线性探测查找 ” 姓 名: 学 号: 专 业: 班 级: 指导教师: 职 称: 计算机与电子工程学院 20年月 题目 参与人员 姓 名 班 级 学 号 设计任务与要求： 作品完成情况： 验收情况： 验收教师签名： 　　　　　　年 月 日 1 课程设计任务与要求 1 1.1 课程设计任务 1 1.2 问题分析 2 2 系统总体设计 2 2.1 数据结构 2 2.2 模块构成 3 2.3 系统组成 3 3 系统详细设计 4 4 系统实现与测试 7 4.1 系统测试 7 4.2 系统测试结果 7 5 课程设计总结 10 参考文献 11 附录 12 1 课程设计任务与要求 课程设计任务 哈希表操作，采用线性探测法处理冲突并查找 课题的目的和任务：根据数据元素的关键字和哈希函数建立哈希表并初始化哈希表，用开放定址法处理冲突，按屏幕输出的功能表选择所需的功能实现用哈希表对数据元素的插入，显示，查找，删除。 初始化哈希表时把elem[MAXSIZE]、elemflag[MAXSIZE]和count分别置0。创建哈希表时按哈希函数创建哈希表，输入数据元素的关键字时，以“0”结束输入且要求关键字为正整数，数据元素个数不允许超过表长MAXSIZE。 输出的形式：根据所选择的哈希表的功能输出相应提示语句和正确结果。 程序的功能：将一组个数不超过哈希表长度的数据元素，按其关键字和哈希函数存入哈希表中，如果产生冲突用开放定址法处理并找出相应的地址。能实现用哈希表对数据元素的插入，显示，查找，删除。 测试数据：maxsize=10 哈希函数：H（key）=key%7 处理冲突方法：开放定址法 Hi=(H(key)+di)%13 i=1,2,3,…,9 1.2 问题分析 哈希表又称散列表。哈希表存储的基本思想是：以数据表中的每个记录的关键字 k为自变量，通过一种函数H(k)计算出函数值。把这个值解释为一块连续存储空间（即数组空间）的单元地址（即下标），将该记录存储到这个单元中。在此称该函数H为哈希函数或散列函数。按这种方法建立的表称为哈希表或散列表。 处理冲突的方法开放寻址法：Hi=(H(key) + di) MOD m, i=1,2,…, k(k=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列，可有下列三种取法： 1.di=1,2,3,…, m-1，称线性探测再散列；2.di=1^2, (-1)^2, 2^2,(-2)^2, (3)^2, …, ±(k)^2,(k=m/2)称二次探测再散列；3.di=伪随机数序列，称伪随机探测再散列。 再散列法：Hi=RHi(key), i=1,2,…,k. RHi均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间； 链地址法（拉链法）：将所有关键字为同义词的记录存储在同一线性链表中；建立一个公共溢出区。 HashTable {数据对象：D1={ai|ai∈elem[MAXSIZE],i=0,1,2,…,0≦n≦MAXSIZE }elem [MAXSIZE]是哈希表中关键字的集合，MAXSIZE为哈希表长。} D2={ai|ai∈elemflag[MAXSIZE]是哈希表中有无关键字的标志的集合，MAXSIZE为哈希表长。} 基本操作：Hash(key) 初始条件：数据元素关键字key已存在 操作结果：根据哈希函数计算相应地址，并返回此地址。 基本操作：InitialHash(HashTable H) 初始条件：哈希表H已存在 操作结果：初始化哈希表把elem[MAXSIZE]、elemflag[MAXSIZE]和count分别置0。 基本操作：SearchHash(HashTable H,int k) 初始条件：哈希表H已存在 操作结果：在开放定址哈希表H中查找关键字为k的元素，若查找成功，并返回SUCCESS；否则返回UNSUCCESS。 基本操作：InsertHash(HashTable H,int e) 初始条件：哈希表H已存在 操作结果：查找不成功时插入数据元素e到开放定址哈希表H中，并返回SUCCESS；否则输出已有此数！插入失败！并返回UNSUCCESS。 基本操作：CreateHash(HashTa