哈希表设计
一.问题描述
1 问题描述
针对某个集体(比如你所在的班级)中的“人名”设计一个哈希表,使得平
均查找长度不超过 ,完成相应的建表和查表程序。
2.基本要求
假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有 个,
取平均查找长度的上限为 。哈希函数用除留余数法构造,用伪随机探测再散
列发处理冲突。
二. 需求分析
() 针对某个集体中的人名设计一个哈希表,使得平均查找长度不超过
,完成相应的建立和查表程序。
( ) 人 名 为 汉 语 拼 音 形 式 , 最 长 不 超 过 个 字 符 如 : 庄 双 双
。
() 假设待填入哈希表的人名有 个,平均查找长度的上限为 。哈希
表用除留余数法构造,用伪随机探测在散列法处理冲突。
() 在输入人名过程中能自动识别非法输入,并给与非法输入的反馈信
息要求重新输入。
(5)查找成功时,显示姓名及关键字,并计算和输出查找成功的平均查找长度
三.概要设计
1.为实现上述算法,需要顺序的抽象数据类型。
ADT Hash{
数据对象 D:D 是具有相同特征的数据元素的集合。各数据元素均含有类
型相同,可唯一标识的数据元素的关键字。
数据关系:数据元素同属于一个集合。
基本操作 P:
Creat(&ST,n);
操作结果:构造一个含 n 个数据元素的静态查找表 ST。
Destroy(&ST)
初始条件:静态查找表 ST 存在。
操作结果:销毁表 ST.
Search:( ST,key)
初始条件:静态查找表 ST 存在,key 为和关键字类型相同的定值。
操作结果:若 ST 中存在其关键字等于 key 的数据元素,则函数值
为该数据元素的值或在表中的位置,否则为“空”。
Insert(&h,key)
- 1
- 2
- 3
- 4
前往页