哈希查找数据结构实验报告

1 南昌航空大学实验报告 课程名称： 数据结构 实验名称： 实验九 查找 班 级： 学生姓名： 学号： 指导教师评定： 签 名 : 题目：编程实现哈希表的造表和查找算法。 要求：用除留余数法构造哈希函数，用二次探测再散列解决冲突。 一、 需求分析 1. 用户可以根据自己的需求输入一个顺序表（哈希表） 2. 通过用除留余数法构造哈希函数，并用开放地址的二次探测再散列解决冲突。 3. 在经过排序后显示该哈希表。 4. 程序执行的命令包括： （ 1）创建哈希表 （ 2）输出哈希表 （ 3）二次探测再散列解决冲突 二、概要设计 ⒈ 为实现上述算法，需要顺序表的抽象数据类型： ADT Hash { 数据对象D： D 是具有相同特征的数据元素的集合。各数据元素均含有类型相同，可唯一标识数据元素的关键字。 数据关系R：数据元素同属一个集合。 基本操作P: Creathash(&h) 操作结果：构造一个具有n 个数据元素的哈希查找表h。 destroyhash(&h) 初始条件：哈希查找表h 存在。 操作结果：销毁哈希查找表h。 displayhash（ h） 初始条件：哈希查找表h 存在。 操作结果：显示哈希查找表h。 hash(h， &k) 初始条件：哈希查找表h 存在。 操作结果：通过除留余数法得到地址用k 返回。 hash2 (i， &k) 初始条件：哈希查找表h 存在存在，i 是除留余数法得到的地址。 操作结果：返回二次探测再散列解决冲突得到的地址k。 search (h， key) 初始条件：哈希查找表h 存在。 操作结果：查找表h 中的key，若查找成功，返回其地址，否则返回 2 -1 insert (&h， key) 初始条件：哈希查找表h 存在。 操作结果：若表h 中没有key，则在h 中插入key。 search1(h, key,&p) 初始条件：哈希查找表h 存在。 操作结果：在表h 中查找key，若没有，则返回p 的插入的地址，否则返回-1。 }ADT Hash 2. 本程序有三个模块： ⑴ 主程序模块 main(){ 初始化； { 接受命令； 显示结果； ｝ ｝ ⑵ 创建hash 表的模块：主要建立一个哈希表； ⑶解决冲突模块：利用开放地址的二次探测再散列解决冲突； (4)输出哈希表模块：显示已创建哈希表。 三、详细设计 ⒈元素类型，结点类型 typedef struct { int key; }keytype; typedef struct { keytype elem[100]; int length; /*当前的长度*/ int size; /*哈希表的总长*/ }hashtable; /*全局变量*/ int a=0,b=0; /*哈希函数*/...