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,若查找成功,返回其地址,否则返回
评论0